← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/vnc4/gutsy

« back to all changes in this revision

Viewing changes to unix/xc/programs/Xserver/mi/mipolyutil.c

  • Committer: Bazaar Package Importer
  • Author(s): Ola Lundqvist
  • Date: 2006-05-15 20:35:17 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20060515203517-l4lre1ku942mn26k
Tags: 4.1.1+X4.3.0-10
* Correction of critical security issue. Thanks to Martin Kogler
  <e9925248@student.tuwien.ac.at> that informed me about the issue,
  and provided the patch.
  This flaw was originally found by Steve Wiseman of intelliadmin.com.
* Applied patch from Javier Kohen <jkohen@users.sourceforge.net> that
  inform the user that only 8 first characters of the password will
  actually be used when typing more than 8 characters, closes:
  #355619.

Show diffs side-by-side

added added

removed removed

Lines of Context:
unix/xc/programs/Xserver/mi/mipolyutil.c
 
1
/* $XFree86: xc/programs/Xserver/mi/mipolyutil.c,v 1.9 2001/12/14 20:00:26 dawes Exp $ */
 
2
/***********************************************************
 
3
 
 
4
Copyright 1987, 1998  The Open Group
 
5
 
 
6
Permission to use, copy, modify, distribute, and sell this software and its
 
7
documentation for any purpose is hereby granted without fee, provided that
 
8
the above copyright notice appear in all copies and that both that
 
9
copyright notice and this permission notice appear in supporting
 
10
documentation.
 
11
 
 
12
The above copyright notice and this permission notice shall be included in
 
13
all copies or substantial portions of the Software.
 
14
 
 
15
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 
16
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 
17
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 
18
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
 
19
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 
20
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 
21
 
 
22
Except as contained in this notice, the name of The Open Group shall not be
 
23
used in advertising or otherwise to promote the sale, use or other dealings
 
24
in this Software without prior written authorization from The Open Group.
 
25
 
 
26
 
 
27
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
 
28
 
 
29
                        All Rights Reserved
 
30
 
 
31
Permission to use, copy, modify, and distribute this software and its 
 
32
documentation for any purpose and without fee is hereby granted, 
 
33
provided that the above copyright notice appear in all copies and that
 
34
both that copyright notice and this permission notice appear in 
 
35
supporting documentation, and that the name of Digital not be
 
36
used in advertising or publicity pertaining to distribution of the
 
37
software without specific, written prior permission.  
 
38
 
 
39
DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 
40
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
 
41
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
 
42
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
 
43
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
 
44
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 
45
SOFTWARE.
 
46
 
 
47
******************************************************************/
 
48
/* $Xorg: mipolyutil.c,v 1.4 2001/02/09 02:05:21 xorgcvs Exp $ */
 
49
#include "miscstruct.h"
 
50
#include "gc.h"
 
51
#include "miscanfill.h"
 
52
#include "mipoly.h"
 
53
#include "misc.h"       /* MAXINT */
 
54
 
 
55
/*
 
56
 *     fillUtils.c
 
57
 *
 
58
 *     Written by Brian Kelleher;  Oct. 1985
 
59
 *
 
60
 *     This module contains all of the utility functions
 
61
 *     needed to scan convert a polygon.
 
62
 *
 
63
 */
 
64
 
 
65
/*
 
66
 *     InsertEdgeInET
 
67
 *
 
68
 *     Insert the given edge into the edge table.
 
69
 *     First we must find the correct bucket in the
 
70
 *     Edge table, then find the right slot in the
 
71
 *     bucket.  Finally, we can insert it.
 
72
 *
 
73
 */
 
74
Bool
 
75
miInsertEdgeInET(ET, ETE, scanline, SLLBlock, iSLLBlock)
 
76
    EdgeTable *ET;
 
77
    EdgeTableEntry *ETE;
 
78
    int scanline;
 
79
    ScanLineListBlock **SLLBlock;
 
80
    int *iSLLBlock;
 
81
{
 
82
    register EdgeTableEntry *start, *prev;
 
83
    register ScanLineList *pSLL, *pPrevSLL;
 
84
    ScanLineListBlock *tmpSLLBlock;
 
85
 
 
86
    /*
 
87
     * find the right bucket to put the edge into
 
88
     */
 
89
    pPrevSLL = &ET->scanlines;
 
90
    pSLL = pPrevSLL->next;
 
91
    while (pSLL && (pSLL->scanline < scanline)) 
 
92
    {
 
93
        pPrevSLL = pSLL;
 
94
        pSLL = pSLL->next;
 
95
    }
 
96
 
 
97
    /*
 
98
     * reassign pSLL (pointer to ScanLineList) if necessary
 
99
     */
 
100
    if ((!pSLL) || (pSLL->scanline > scanline)) 
 
101
    {
 
102
        if (*iSLLBlock > SLLSPERBLOCK-1) 
 
103
        {
 
104
            tmpSLLBlock = 
 
105
                  (ScanLineListBlock *)xalloc(sizeof(ScanLineListBlock));
 
106
            if (!tmpSLLBlock)
 
107
                return FALSE;
 
108
            (*SLLBlock)->next = tmpSLLBlock;
 
109
            tmpSLLBlock->next = (ScanLineListBlock *)NULL;
 
110
            *SLLBlock = tmpSLLBlock;
 
111
            *iSLLBlock = 0;
 
112
        }
 
113
        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
 
114
 
 
115
        pSLL->next = pPrevSLL->next;
 
116
        pSLL->edgelist = (EdgeTableEntry *)NULL;
 
117
        pPrevSLL->next = pSLL;
 
118
    }
 
119
    pSLL->scanline = scanline;
 
120
 
 
121
    /*
 
122
     * now insert the edge in the right bucket
 
123
     */
 
124
    prev = (EdgeTableEntry *)NULL;
 
125
    start = pSLL->edgelist;
 
126
    while (start && (start->bres.minor < ETE->bres.minor)) 
 
127
    {
 
128
        prev = start;
 
129
        start = start->next;
 
130
    }
 
131
    ETE->next = start;
 
132
 
 
133
    if (prev)
 
134
        prev->next = ETE;
 
135
    else
 
136
        pSLL->edgelist = ETE;
 
137
    return TRUE;
 
138
}
 
139
 
 
140
/*
 
141
 *     CreateEdgeTable
 
142
 *
 
143
 *     This routine creates the edge table for
 
144
 *     scan converting polygons. 
 
145
 *     The Edge Table (ET) looks like:
 
146
 *
 
147
 *    EdgeTable
 
148
 *     --------
 
149
 *    |  ymax  |        ScanLineLists
 
150
 *    |scanline|-->------------>-------------->...
 
151
 *     --------   |scanline|   |scanline|
 
152
 *                |edgelist|   |edgelist|
 
153
 *                ---------    ---------
 
154
 *                    |             |
 
155
 *                    |             |
 
156
 *                    V             V
 
157
 *              list of ETEs   list of ETEs
 
158
 *
 
159
 *     where ETE is an EdgeTableEntry data structure,
 
160
 *     and there is one ScanLineList per scanline at
 
161
 *     which an edge is initially entered.
 
162
 *
 
163
 */
 
164
 
 
165
Bool
 
166
miCreateETandAET(count, pts, ET, AET, pETEs, pSLLBlock)
 
167
    register int count;
 
168
    register DDXPointPtr pts;
 
169
    EdgeTable *ET;
 
170
    EdgeTableEntry *AET;
 
171
    register EdgeTableEntry *pETEs;
 
172
    ScanLineListBlock   *pSLLBlock;
 
173
{
 
174
    register DDXPointPtr top, bottom;
 
175
    register DDXPointPtr PrevPt, CurrPt;
 
176
    int iSLLBlock = 0;
 
177
 
 
178
    int dy;
 
179
 
 
180
    if (count < 2)  return TRUE;
 
181
 
 
182
    /*
 
183
     *  initialize the Active Edge Table
 
184
     */
 
185
    AET->next = (EdgeTableEntry *)NULL;
 
186
    AET->back = (EdgeTableEntry *)NULL;
 
187
    AET->nextWETE = (EdgeTableEntry *)NULL;
 
188
    AET->bres.minor = MININT;
 
189
 
 
190
    /*
 
191
     *  initialize the Edge Table.
 
192
     */
 
193
    ET->scanlines.next = (ScanLineList *)NULL;
 
194
    ET->ymax = MININT;
 
195
    ET->ymin = MAXINT;
 
196
    pSLLBlock->next = (ScanLineListBlock *)NULL;
 
197
 
 
198
    PrevPt = &pts[count-1];
 
199
 
 
200
    /*
 
201
     *  for each vertex in the array of points.
 
202
     *  In this loop we are dealing with two vertices at
 
203
     *  a time -- these make up one edge of the polygon.
 
204
     */
 
205
    while (count--) 
 
206
    {
 
207
        CurrPt = pts++;
 
208
 
 
209
        /*
 
210
         *  find out which point is above and which is below.
 
211
         */
 
212
        if (PrevPt->y > CurrPt->y) 
 
213
        {
 
214
            bottom = PrevPt, top = CurrPt;
 
215
            pETEs->ClockWise = 0;
 
216
        }
 
217
        else 
 
218
        {
 
219
            bottom = CurrPt, top = PrevPt;
 
220
            pETEs->ClockWise = 1;
 
221
        }
 
222
 
 
223
        /*
 
224
         * don't add horizontal edges to the Edge table.
 
225
         */
 
226
        if (bottom->y != top->y) 
 
227
        {
 
228
            pETEs->ymax = bottom->y-1;  /* -1 so we don't get last scanline */
 
229
 
 
230
            /*
 
231
             *  initialize integer edge algorithm
 
232
             */
 
233
            dy = bottom->y - top->y;
 
234
            BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
 
235
 
 
236
            if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock))
 
237
            {
 
238
                miFreeStorage(pSLLBlock->next);
 
239
                return FALSE;
 
240
            }
 
241
 
 
242
            ET->ymax = max(ET->ymax, PrevPt->y);
 
243
            ET->ymin = min(ET->ymin, PrevPt->y);
 
244
            pETEs++;
 
245
        }
 
246
 
 
247
        PrevPt = CurrPt;
 
248
    }
 
249
    return TRUE;
 
250
}
 
251
 
 
252
/*
 
253
 *     loadAET
 
254
 *
 
255
 *     This routine moves EdgeTableEntries from the
 
256
 *     EdgeTable into the Active Edge Table,
 
257
 *     leaving them sorted by smaller x coordinate.
 
258
 *
 
259
 */
 
260
 
 
261
void
 
262
miloadAET(AET, ETEs)
 
263
    register EdgeTableEntry *AET, *ETEs;
 
264
{
 
265
    register EdgeTableEntry *pPrevAET;
 
266
    register EdgeTableEntry *tmp;
 
267
 
 
268
    pPrevAET = AET;
 
269
    AET = AET->next;
 
270
    while (ETEs) 
 
271
    {
 
272
        while (AET && (AET->bres.minor < ETEs->bres.minor)) 
 
273
        {
 
274
            pPrevAET = AET;
 
275
            AET = AET->next;
 
276
        }
 
277
        tmp = ETEs->next;
 
278
        ETEs->next = AET;
 
279
        if (AET)
 
280
            AET->back = ETEs;
 
281
        ETEs->back = pPrevAET;
 
282
        pPrevAET->next = ETEs;
 
283
        pPrevAET = ETEs;
 
284
 
 
285
        ETEs = tmp;
 
286
    }
 
287
}
 
288
 
 
289
/*
 
290
 *     computeWAET
 
291
 *
 
292
 *     This routine links the AET by the
 
293
 *     nextWETE (winding EdgeTableEntry) link for
 
294
 *     use by the winding number rule.  The final 
 
295
 *     Active Edge Table (AET) might look something
 
296
 *     like:
 
297
 *
 
298
 *     AET
 
299
 *     ----------  ---------   ---------
 
300
 *     |ymax    |  |ymax    |  |ymax    | 
 
301
 *     | ...    |  |...     |  |...     |
 
302
 *     |next    |->|next    |->|next    |->...
 
303
 *     |nextWETE|  |nextWETE|  |nextWETE|
 
304
 *     ---------   ---------   ^--------
 
305
 *         |                   |       |
 
306
 *         V------------------->       V---> ...
 
307
 *
 
308
 */
 
309
void
 
310
micomputeWAET(AET)
 
311
    register EdgeTableEntry *AET;
 
312
{
 
313
    register EdgeTableEntry *pWETE;
 
314
    register int inside = 1;
 
315
    register int isInside = 0;
 
316
 
 
317
    AET->nextWETE = (EdgeTableEntry *)NULL;
 
318
    pWETE = AET;
 
319
    AET = AET->next;
 
320
    while (AET) 
 
321
    {
 
322
        if (AET->ClockWise)
 
323
            isInside++;
 
324
        else
 
325
            isInside--;
 
326
 
 
327
        if ((!inside && !isInside) ||
 
328
            ( inside &&  isInside)) 
 
329
        {
 
330
            pWETE->nextWETE = AET;
 
331
            pWETE = AET;
 
332
            inside = !inside;
 
333
        }
 
334
        AET = AET->next;
 
335
    }
 
336
    pWETE->nextWETE = (EdgeTableEntry *)NULL;
 
337
}
 
338
 
 
339
/*
 
340
 *     InsertionSort
 
341
 *
 
342
 *     Just a simple insertion sort using
 
343
 *     pointers and back pointers to sort the Active
 
344
 *     Edge Table.
 
345
 *
 
346
 */
 
347
 
 
348
int
 
349
miInsertionSort(AET)
 
350
    register EdgeTableEntry *AET;
 
351
{
 
352
    register EdgeTableEntry *pETEchase;
 
353
    register EdgeTableEntry *pETEinsert;
 
354
    register EdgeTableEntry *pETEchaseBackTMP;
 
355
    register int changed = 0;
 
356
 
 
357
    AET = AET->next;
 
358
    while (AET) 
 
359
    {
 
360
        pETEinsert = AET;
 
361
        pETEchase = AET;
 
362
        while (pETEchase->back->bres.minor > AET->bres.minor)
 
363
            pETEchase = pETEchase->back;
 
364
 
 
365
        AET = AET->next;
 
366
        if (pETEchase != pETEinsert) 
 
367
        {
 
368
            pETEchaseBackTMP = pETEchase->back;
 
369
            pETEinsert->back->next = AET;
 
370
            if (AET)
 
371
                AET->back = pETEinsert->back;
 
372
            pETEinsert->next = pETEchase;
 
373
            pETEchase->back->next = pETEinsert;
 
374
            pETEchase->back = pETEinsert;
 
375
            pETEinsert->back = pETEchaseBackTMP;
 
376
            changed = 1;
 
377
        }
 
378
    }
 
379
    return(changed);
 
380
}
 
381
 
 
382
/*
 
383
 *     Clean up our act.
 
384
 */
 
385
void
 
386
miFreeStorage(pSLLBlock)
 
387
    register ScanLineListBlock   *pSLLBlock;
 
388
{
 
389
    register ScanLineListBlock   *tmpSLLBlock;
 
390
 
 
391
    while (pSLLBlock) 
 
392
    {
 
393
        tmpSLLBlock = pSLLBlock->next;
 
394
        xfree(pSLLBlock);
 
395
        pSLLBlock = tmpSLLBlock;
 
396
    }
 
397
}