1/***********************************************************
2
3Copyright 1987, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in this Software without prior written authorization from The Open Group.
24
25Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
26
27                        All Rights Reserved
28
29Permission to use, copy, modify, and distribute this software and its
30documentation for any purpose and without fee is hereby granted,
31provided that the above copyright notice appear in all copies and that
32both that copyright notice and this permission notice appear in
33supporting documentation, and that the name of Digital not be
34used in advertising or publicity pertaining to distribution of the
35software without specific, written prior permission.
36
37DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
38ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
39DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
40ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
41WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
42ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
43SOFTWARE.
44
45******************************************************************/
46
47#ifdef HAVE_DIX_CONFIG_H
48#include <dix-config.h>
49#endif
50
51#include <X11/X.h>
52#include <X11/Xproto.h>
53#include <stdio.h>
54#include <string.h>
55#include <strings.h>
56#include "misc.h"
57#include "dix.h"
58#include "dixstruct.h"
59#include "colormapst.h"
60#include "os.h"
61#include "scrnintstr.h"
62#include "resource.h"
63#include "windowstr.h"
64#include "privates.h"
65#include "xace.h"
66
67typedef int (*ColorCompareProcPtr) (EntryPtr /*pent */ ,
68                                    xrgb * /*prgb */ );
69
70static Pixel FindBestPixel(EntryPtr /*pentFirst */ ,
71                           int /*size */ ,
72                           xrgb * /*prgb */ ,
73                           int  /*channel */
74    );
75
76static int AllComp(EntryPtr /*pent */ ,
77                   xrgb *       /*prgb */
78    );
79
80static int RedComp(EntryPtr /*pent */ ,
81                   xrgb *       /*prgb */
82    );
83
84static int GreenComp(EntryPtr /*pent */ ,
85                     xrgb *     /*prgb */
86    );
87
88static int BlueComp(EntryPtr /*pent */ ,
89                    xrgb *      /*prgb */
90    );
91
92static void FreePixels(ColormapPtr /*pmap */ ,
93                       int      /*client */
94    );
95
96static void CopyFree(int /*channel */ ,
97                     int /*client */ ,
98                     ColormapPtr /*pmapSrc */ ,
99                     ColormapPtr        /*pmapDst */
100    );
101
102static void FreeCell(ColormapPtr /*pmap */ ,
103                     Pixel /*i */ ,
104                     int        /*channel */
105    );
106
107static void UpdateColors(ColormapPtr    /*pmap */
108    );
109
110static int AllocDirect(int /*client */ ,
111                       ColormapPtr /*pmap */ ,
112                       int /*c */ ,
113                       int /*r */ ,
114                       int /*g */ ,
115                       int /*b */ ,
116                       Bool /*contig */ ,
117                       Pixel * /*pixels */ ,
118                       Pixel * /*prmask */ ,
119                       Pixel * /*pgmask */ ,
120                       Pixel *  /*pbmask */
121    );
122
123static int AllocPseudo(int /*client */ ,
124                       ColormapPtr /*pmap */ ,
125                       int /*c */ ,
126                       int /*r */ ,
127                       Bool /*contig */ ,
128                       Pixel * /*pixels */ ,
129                       Pixel * /*pmask */ ,
130                       Pixel ** /*pppixFirst */
131    );
132
133static Bool AllocCP(ColormapPtr /*pmap */ ,
134                    EntryPtr /*pentFirst */ ,
135                    int /*count */ ,
136                    int /*planes */ ,
137                    Bool /*contig */ ,
138                    Pixel * /*pixels */ ,
139                    Pixel *     /*pMask */
140    );
141
142static Bool AllocShared(ColormapPtr /*pmap */ ,
143                        Pixel * /*ppix */ ,
144                        int /*c */ ,
145                        int /*r */ ,
146                        int /*g */ ,
147                        int /*b */ ,
148                        Pixel /*rmask */ ,
149                        Pixel /*gmask */ ,
150                        Pixel /*bmask */ ,
151                        Pixel * /*ppixFirst */
152    );
153
154static int FreeCo(ColormapPtr /*pmap */ ,
155                  int /*client */ ,
156                  int /*color */ ,
157                  int /*npixIn */ ,
158                  Pixel * /*ppixIn */ ,
159                  Pixel         /*mask */
160    );
161
162static int TellNoMap(WindowPtr /*pwin */ ,
163                     Colormap * /*pmid */
164    );
165
166static void FindColorInRootCmap(ColormapPtr /* pmap */ ,
167                                EntryPtr /* pentFirst */ ,
168                                int /* size */ ,
169                                xrgb * /* prgb */ ,
170                                Pixel * /* pPixel */ ,
171                                int /* channel */ ,
172                                ColorCompareProcPtr     /* comp */
173    );
174
175#define NUMRED(vis) ((vis->redMask >> vis->offsetRed) + 1)
176#define NUMGREEN(vis) ((vis->greenMask >> vis->offsetGreen) + 1)
177#define NUMBLUE(vis) ((vis->blueMask >> vis->offsetBlue) + 1)
178#if COMPOSITE
179#define ALPHAMASK(vis)	((vis)->nplanes < 32 ? 0 : \
180			 (CARD32) ~((vis)->redMask|(vis)->greenMask|(vis)->blueMask))
181#else
182#define ALPHAMASK(vis)	0
183#endif
184
185#define RGBMASK(vis) (vis->redMask | vis->greenMask | vis->blueMask | ALPHAMASK(vis))
186
187/* GetNextBitsOrBreak(bits, mask, base)  --
188 * (Suggestion: First read the macro, then read this explanation.
189 *
190 * Either generate the next value to OR in to a pixel or break out of this
191 * while loop
192 *
193 * This macro is used when we're trying to generate all 2^n combinations of
194 * bits in mask.  What we're doing here is counting in binary, except that
195 * the bits we use to count may not be contiguous.  This macro will be
196 * called 2^n times, returning a different value in bits each time. Then
197 * it will cause us to break out of a surrounding loop. (It will always be
198 * called from within a while loop.)
199 * On call: mask is the value we want to find all the combinations for
200 * base has 1 bit set where the least significant bit of mask is set
201 *
202 * For example,if mask is 01010, base should be 0010 and we count like this:
203 * 00010 (see this isn't so hard),
204 *     then we add base to bits and get 0100. (bits & ~mask) is (0100 & 0100) so
205 *      we add that to bits getting (0100 + 0100) =
206 * 01000 for our next value.
207 *      then we add 0010 to get
208 * 01010 and we're done (easy as 1, 2, 3)
209 */
210#define GetNextBitsOrBreak(bits, mask, base)	\
211	    if((bits) == (mask)) 		\
212		break;		 		\
213	    (bits) += (base);		 	\
214	    while((bits) & ~(mask))		\
215		(bits) += ((bits) & ~(mask));
216/* ID of server as client */
217#define SERVER_ID	0
218
219typedef struct _colorResource {
220    Colormap mid;
221    int client;
222} colorResource;
223
224/* Invariants:
225 * refcnt == 0 means entry is empty
226 * refcnt > 0 means entry is useable by many clients, so it can't be changed
227 * refcnt == AllocPrivate means entry owned by one client only
228 * fShared should only be set if refcnt == AllocPrivate, and only in red map
229 */
230
231/**
232 * Create and initialize the color map
233 *
234 * \param mid    resource to use for this colormap
235 * \param alloc  1 iff all entries are allocated writable
236 */
237int
238CreateColormap(Colormap mid, ScreenPtr pScreen, VisualPtr pVisual,
239               ColormapPtr *ppcmap, int alloc, int client)
240{
241    int class, size;
242    unsigned long sizebytes;
243    ColormapPtr pmap;
244    EntryPtr pent;
245    int i;
246    Pixel *ppix, **pptr;
247
248    class = pVisual->class;
249    if (!(class & DynamicClass) && (alloc != AllocNone) &&
250        (client != SERVER_ID))
251        return BadMatch;
252
253    size = pVisual->ColormapEntries;
254    sizebytes = (size * sizeof(Entry)) +
255        (LimitClients * sizeof(Pixel *)) + (LimitClients * sizeof(int));
256    if ((class | DynamicClass) == DirectColor)
257        sizebytes *= 3;
258    sizebytes += sizeof(ColormapRec);
259    if (mid == pScreen->defColormap) {
260        pmap = malloc(sizebytes);
261        if (!pmap)
262            return BadAlloc;
263        if (!dixAllocatePrivates(&pmap->devPrivates, PRIVATE_COLORMAP)) {
264            free(pmap);
265            return BadAlloc;
266        }
267    }
268    else {
269        pmap = _dixAllocateObjectWithPrivates(sizebytes, sizebytes,
270                                              offsetof(ColormapRec,
271                                                       devPrivates),
272                                              PRIVATE_COLORMAP);
273        if (!pmap)
274            return BadAlloc;
275    }
276    pmap->red = (EntryPtr) ((char *) pmap + sizeof(ColormapRec));
277    sizebytes = size * sizeof(Entry);
278    pmap->clientPixelsRed = (Pixel **) ((char *) pmap->red + sizebytes);
279    pmap->numPixelsRed = (int *) ((char *) pmap->clientPixelsRed +
280                                  (LimitClients * sizeof(Pixel *)));
281    pmap->mid = mid;
282    pmap->flags = 0;            /* start out with all flags clear */
283    if (mid == pScreen->defColormap)
284        pmap->flags |= IsDefault;
285    pmap->pScreen = pScreen;
286    pmap->pVisual = pVisual;
287    pmap->class = class;
288    if ((class | DynamicClass) == DirectColor)
289        size = NUMRED(pVisual);
290    pmap->freeRed = size;
291    memset((char *) pmap->red, 0, (int) sizebytes);
292    memset((char *) pmap->numPixelsRed, 0, LimitClients * sizeof(int));
293    for (pptr = &pmap->clientPixelsRed[LimitClients];
294         --pptr >= pmap->clientPixelsRed;)
295        *pptr = (Pixel *) NULL;
296    if (alloc == AllocAll) {
297        if (class & DynamicClass)
298            pmap->flags |= AllAllocated;
299        for (pent = &pmap->red[size - 1]; pent >= pmap->red; pent--)
300            pent->refcnt = AllocPrivate;
301        pmap->freeRed = 0;
302        ppix = xallocarray(size, sizeof(Pixel));
303        if (!ppix) {
304            free(pmap);
305            return BadAlloc;
306        }
307        pmap->clientPixelsRed[client] = ppix;
308        for (i = 0; i < size; i++)
309            ppix[i] = i;
310        pmap->numPixelsRed[client] = size;
311    }
312
313    if ((class | DynamicClass) == DirectColor) {
314        pmap->freeGreen = NUMGREEN(pVisual);
315        pmap->green = (EntryPtr) ((char *) pmap->numPixelsRed +
316                                  (LimitClients * sizeof(int)));
317        pmap->clientPixelsGreen = (Pixel **) ((char *) pmap->green + sizebytes);
318        pmap->numPixelsGreen = (int *) ((char *) pmap->clientPixelsGreen +
319                                        (LimitClients * sizeof(Pixel *)));
320        pmap->freeBlue = NUMBLUE(pVisual);
321        pmap->blue = (EntryPtr) ((char *) pmap->numPixelsGreen +
322                                 (LimitClients * sizeof(int)));
323        pmap->clientPixelsBlue = (Pixel **) ((char *) pmap->blue + sizebytes);
324        pmap->numPixelsBlue = (int *) ((char *) pmap->clientPixelsBlue +
325                                       (LimitClients * sizeof(Pixel *)));
326
327        memset((char *) pmap->green, 0, (int) sizebytes);
328        memset((char *) pmap->blue, 0, (int) sizebytes);
329
330        memmove((char *) pmap->clientPixelsGreen,
331                (char *) pmap->clientPixelsRed, LimitClients * sizeof(Pixel *));
332        memmove((char *) pmap->clientPixelsBlue,
333                (char *) pmap->clientPixelsRed, LimitClients * sizeof(Pixel *));
334        memset((char *) pmap->numPixelsGreen, 0, LimitClients * sizeof(int));
335        memset((char *) pmap->numPixelsBlue, 0, LimitClients * sizeof(int));
336
337        /* If every cell is allocated, mark its refcnt */
338        if (alloc == AllocAll) {
339            size = pmap->freeGreen;
340            for (pent = &pmap->green[size - 1]; pent >= pmap->green; pent--)
341                pent->refcnt = AllocPrivate;
342            pmap->freeGreen = 0;
343            ppix = xallocarray(size, sizeof(Pixel));
344            if (!ppix) {
345                free(pmap->clientPixelsRed[client]);
346                free(pmap);
347                return BadAlloc;
348            }
349            pmap->clientPixelsGreen[client] = ppix;
350            for (i = 0; i < size; i++)
351                ppix[i] = i;
352            pmap->numPixelsGreen[client] = size;
353
354            size = pmap->freeBlue;
355            for (pent = &pmap->blue[size - 1]; pent >= pmap->blue; pent--)
356                pent->refcnt = AllocPrivate;
357            pmap->freeBlue = 0;
358            ppix = xallocarray(size, sizeof(Pixel));
359            if (!ppix) {
360                free(pmap->clientPixelsGreen[client]);
361                free(pmap->clientPixelsRed[client]);
362                free(pmap);
363                return BadAlloc;
364            }
365            pmap->clientPixelsBlue[client] = ppix;
366            for (i = 0; i < size; i++)
367                ppix[i] = i;
368            pmap->numPixelsBlue[client] = size;
369        }
370    }
371    pmap->flags |= BeingCreated;
372
373    if (!AddResource(mid, RT_COLORMAP, (void *) pmap))
374        return BadAlloc;
375
376    /*
377     * Security creation/labeling check
378     */
379    i = XaceHook(XACE_RESOURCE_ACCESS, clients[client], mid, RT_COLORMAP,
380                 pmap, RT_NONE, NULL, DixCreateAccess);
381    if (i != Success) {
382        FreeResource(mid, RT_NONE);
383        return i;
384    }
385
386    /* If the device wants a chance to initialize the colormap in any way,
387     * this is it.  In specific, if this is a Static colormap, this is the
388     * time to fill in the colormap's values */
389    if (!(*pScreen->CreateColormap) (pmap)) {
390        FreeResource(mid, RT_NONE);
391        return BadAlloc;
392    }
393    pmap->flags &= ~BeingCreated;
394    *ppcmap = pmap;
395    return Success;
396}
397
398/**
399 *
400 * \param value  must conform to DeleteType
401 */
402int
403FreeColormap(void *value, XID mid)
404{
405    int i;
406    EntryPtr pent;
407    ColormapPtr pmap = (ColormapPtr) value;
408
409    if (CLIENT_ID(mid) != SERVER_ID) {
410        (*pmap->pScreen->UninstallColormap) (pmap);
411        WalkTree(pmap->pScreen, (VisitWindowProcPtr) TellNoMap, (void *) &mid);
412    }
413
414    /* This is the device's chance to undo anything it needs to, especially
415     * to free any storage it allocated */
416    (*pmap->pScreen->DestroyColormap) (pmap);
417
418    if (pmap->clientPixelsRed) {
419        for (i = 0; i < LimitClients; i++)
420            free(pmap->clientPixelsRed[i]);
421    }
422
423    if ((pmap->class == PseudoColor) || (pmap->class == GrayScale)) {
424        for (pent = &pmap->red[pmap->pVisual->ColormapEntries - 1];
425             pent >= pmap->red; pent--) {
426            if (pent->fShared) {
427                if (--pent->co.shco.red->refcnt == 0)
428                    free(pent->co.shco.red);
429                if (--pent->co.shco.green->refcnt == 0)
430                    free(pent->co.shco.green);
431                if (--pent->co.shco.blue->refcnt == 0)
432                    free(pent->co.shco.blue);
433            }
434        }
435    }
436    if ((pmap->class | DynamicClass) == DirectColor) {
437        for (i = 0; i < LimitClients; i++) {
438            free(pmap->clientPixelsGreen[i]);
439            free(pmap->clientPixelsBlue[i]);
440        }
441    }
442
443    if (pmap->flags & IsDefault) {
444        dixFreePrivates(pmap->devPrivates, PRIVATE_COLORMAP);
445        free(pmap);
446    }
447    else
448        dixFreeObjectWithPrivates(pmap, PRIVATE_COLORMAP);
449    return Success;
450}
451
452/* Tell window that pmid has disappeared */
453static int
454TellNoMap(WindowPtr pwin, Colormap * pmid)
455{
456    if (wColormap(pwin) == *pmid) {
457        /* This should be call to DeliverEvent */
458        xEvent xE = {
459            .u.colormap.window = pwin->drawable.id,
460            .u.colormap.colormap = None,
461            .u.colormap.new = TRUE,
462            .u.colormap.state = ColormapUninstalled
463        };
464        xE.u.u.type = ColormapNotify;
465#ifdef PANORAMIX
466        if (noPanoramiXExtension || !pwin->drawable.pScreen->myNum)
467#endif
468            DeliverEvents(pwin, &xE, 1, (WindowPtr) NULL);
469        if (pwin->optional) {
470            pwin->optional->colormap = None;
471            CheckWindowOptionalNeed(pwin);
472        }
473    }
474
475    return WT_WALKCHILDREN;
476}
477
478/* Tell window that pmid got uninstalled */
479int
480TellLostMap(WindowPtr pwin, void *value)
481{
482    Colormap *pmid = (Colormap *) value;
483
484#ifdef PANORAMIX
485    if (!noPanoramiXExtension && pwin->drawable.pScreen->myNum)
486        return WT_STOPWALKING;
487#endif
488    if (wColormap(pwin) == *pmid) {
489        /* This should be call to DeliverEvent */
490        xEvent xE = {
491            .u.colormap.window = pwin->drawable.id,
492            .u.colormap.colormap = *pmid,
493            .u.colormap.new = FALSE,
494            .u.colormap.state = ColormapUninstalled
495        };
496        xE.u.u.type = ColormapNotify;
497        DeliverEvents(pwin, &xE, 1, (WindowPtr) NULL);
498    }
499
500    return WT_WALKCHILDREN;
501}
502
503/* Tell window that pmid got installed */
504int
505TellGainedMap(WindowPtr pwin, void *value)
506{
507    Colormap *pmid = (Colormap *) value;
508
509#ifdef PANORAMIX
510    if (!noPanoramiXExtension && pwin->drawable.pScreen->myNum)
511        return WT_STOPWALKING;
512#endif
513    if (wColormap(pwin) == *pmid) {
514        /* This should be call to DeliverEvent */
515        xEvent xE = {
516            .u.colormap.window = pwin->drawable.id,
517            .u.colormap.colormap = *pmid,
518            .u.colormap.new = FALSE,
519            .u.colormap.state = ColormapInstalled
520        };
521        xE.u.u.type = ColormapNotify;
522        DeliverEvents(pwin, &xE, 1, (WindowPtr) NULL);
523    }
524
525    return WT_WALKCHILDREN;
526}
527
528int
529CopyColormapAndFree(Colormap mid, ColormapPtr pSrc, int client)
530{
531    ColormapPtr pmap = (ColormapPtr) NULL;
532    int result, alloc, size;
533    Colormap midSrc;
534    ScreenPtr pScreen;
535    VisualPtr pVisual;
536
537    pScreen = pSrc->pScreen;
538    pVisual = pSrc->pVisual;
539    midSrc = pSrc->mid;
540    alloc = ((pSrc->flags & AllAllocated) && CLIENT_ID(midSrc) == client) ?
541        AllocAll : AllocNone;
542    size = pVisual->ColormapEntries;
543
544    /* If the create returns non-0, it failed */
545    result = CreateColormap(mid, pScreen, pVisual, &pmap, alloc, client);
546    if (result != Success)
547        return result;
548    if (alloc == AllocAll) {
549        memmove((char *) pmap->red, (char *) pSrc->red, size * sizeof(Entry));
550        if ((pmap->class | DynamicClass) == DirectColor) {
551            memmove((char *) pmap->green, (char *) pSrc->green,
552                    size * sizeof(Entry));
553            memmove((char *) pmap->blue, (char *) pSrc->blue,
554                    size * sizeof(Entry));
555        }
556        pSrc->flags &= ~AllAllocated;
557        FreePixels(pSrc, client);
558        UpdateColors(pmap);
559        return Success;
560    }
561
562    CopyFree(REDMAP, client, pSrc, pmap);
563    if ((pmap->class | DynamicClass) == DirectColor) {
564        CopyFree(GREENMAP, client, pSrc, pmap);
565        CopyFree(BLUEMAP, client, pSrc, pmap);
566    }
567    if (pmap->class & DynamicClass)
568        UpdateColors(pmap);
569    /* XXX should worry about removing any RT_CMAPENTRY resource */
570    return Success;
571}
572
573/* Helper routine for freeing large numbers of cells from a map */
574static void
575CopyFree(int channel, int client, ColormapPtr pmapSrc, ColormapPtr pmapDst)
576{
577    int z, npix;
578    EntryPtr pentSrcFirst, pentDstFirst;
579    EntryPtr pentSrc, pentDst;
580    Pixel *ppix;
581    int nalloc;
582
583    switch (channel) {
584    default:         /* so compiler can see that everything gets initialized */
585    case REDMAP:
586        ppix = (pmapSrc->clientPixelsRed)[client];
587        npix = (pmapSrc->numPixelsRed)[client];
588        pentSrcFirst = pmapSrc->red;
589        pentDstFirst = pmapDst->red;
590        break;
591    case GREENMAP:
592        ppix = (pmapSrc->clientPixelsGreen)[client];
593        npix = (pmapSrc->numPixelsGreen)[client];
594        pentSrcFirst = pmapSrc->green;
595        pentDstFirst = pmapDst->green;
596        break;
597    case BLUEMAP:
598        ppix = (pmapSrc->clientPixelsBlue)[client];
599        npix = (pmapSrc->numPixelsBlue)[client];
600        pentSrcFirst = pmapSrc->blue;
601        pentDstFirst = pmapDst->blue;
602        break;
603    }
604    nalloc = 0;
605    if (pmapSrc->class & DynamicClass) {
606        for (z = npix; --z >= 0; ppix++) {
607            /* Copy entries */
608            pentSrc = pentSrcFirst + *ppix;
609            pentDst = pentDstFirst + *ppix;
610            if (pentDst->refcnt > 0) {
611                pentDst->refcnt++;
612            }
613            else {
614                *pentDst = *pentSrc;
615                nalloc++;
616                if (pentSrc->refcnt > 0)
617                    pentDst->refcnt = 1;
618                else
619                    pentSrc->fShared = FALSE;
620            }
621            FreeCell(pmapSrc, *ppix, channel);
622        }
623    }
624
625    /* Note that FreeCell has already fixed pmapSrc->free{Color} */
626    switch (channel) {
627    case REDMAP:
628        pmapDst->freeRed -= nalloc;
629        (pmapDst->clientPixelsRed)[client] = (pmapSrc->clientPixelsRed)[client];
630        (pmapSrc->clientPixelsRed)[client] = (Pixel *) NULL;
631        (pmapDst->numPixelsRed)[client] = (pmapSrc->numPixelsRed)[client];
632        (pmapSrc->numPixelsRed)[client] = 0;
633        break;
634    case GREENMAP:
635        pmapDst->freeGreen -= nalloc;
636        (pmapDst->clientPixelsGreen)[client] =
637            (pmapSrc->clientPixelsGreen)[client];
638        (pmapSrc->clientPixelsGreen)[client] = (Pixel *) NULL;
639        (pmapDst->numPixelsGreen)[client] = (pmapSrc->numPixelsGreen)[client];
640        (pmapSrc->numPixelsGreen)[client] = 0;
641        break;
642    case BLUEMAP:
643        pmapDst->freeBlue -= nalloc;
644        pmapDst->clientPixelsBlue[client] = pmapSrc->clientPixelsBlue[client];
645        pmapSrc->clientPixelsBlue[client] = (Pixel *) NULL;
646        pmapDst->numPixelsBlue[client] = pmapSrc->numPixelsBlue[client];
647        pmapSrc->numPixelsBlue[client] = 0;
648        break;
649    }
650}
651
652/* Free the ith entry in a color map.  Must handle freeing of
653 * colors allocated through AllocColorPlanes */
654static void
655FreeCell(ColormapPtr pmap, Pixel i, int channel)
656{
657    EntryPtr pent;
658    int *pCount;
659
660    switch (channel) {
661    default:         /* so compiler can see that everything gets initialized */
662    case PSEUDOMAP:
663    case REDMAP:
664        pent = (EntryPtr) &pmap->red[i];
665        pCount = &pmap->freeRed;
666        break;
667    case GREENMAP:
668        pent = (EntryPtr) &pmap->green[i];
669        pCount = &pmap->freeGreen;
670        break;
671    case BLUEMAP:
672        pent = (EntryPtr) &pmap->blue[i];
673        pCount = &pmap->freeBlue;
674        break;
675    }
676    /* If it's not privately allocated and it's not time to free it, just
677     * decrement the count */
678    if (pent->refcnt > 1)
679        pent->refcnt--;
680    else {
681        /* If the color type is shared, find the sharedcolor. If decremented
682         * refcnt is 0, free the shared cell. */
683        if (pent->fShared) {
684            if (--pent->co.shco.red->refcnt == 0)
685                free(pent->co.shco.red);
686            if (--pent->co.shco.green->refcnt == 0)
687                free(pent->co.shco.green);
688            if (--pent->co.shco.blue->refcnt == 0)
689                free(pent->co.shco.blue);
690            pent->fShared = FALSE;
691        }
692        pent->refcnt = 0;
693        *pCount += 1;
694    }
695}
696
697static void
698UpdateColors(ColormapPtr pmap)
699{
700    xColorItem *defs;
701    xColorItem *pdef;
702    EntryPtr pent;
703    VisualPtr pVisual;
704    int i, n, size;
705
706    pVisual = pmap->pVisual;
707    size = pVisual->ColormapEntries;
708    defs = xallocarray(size, sizeof(xColorItem));
709    if (!defs)
710        return;
711    n = 0;
712    pdef = defs;
713    if (pmap->class == DirectColor) {
714        for (i = 0; i < size; i++) {
715            if (!pmap->red[i].refcnt &&
716                !pmap->green[i].refcnt && !pmap->blue[i].refcnt)
717                continue;
718            pdef->pixel = ((Pixel) i << pVisual->offsetRed) |
719                ((Pixel) i << pVisual->offsetGreen) |
720                ((Pixel) i << pVisual->offsetBlue);
721            pdef->red = pmap->red[i].co.local.red;
722            pdef->green = pmap->green[i].co.local.green;
723            pdef->blue = pmap->blue[i].co.local.blue;
724            pdef->flags = DoRed | DoGreen | DoBlue;
725            pdef++;
726            n++;
727        }
728    }
729    else {
730        for (i = 0, pent = pmap->red; i < size; i++, pent++) {
731            if (!pent->refcnt)
732                continue;
733            pdef->pixel = i;
734            if (pent->fShared) {
735                pdef->red = pent->co.shco.red->color;
736                pdef->green = pent->co.shco.green->color;
737                pdef->blue = pent->co.shco.blue->color;
738            }
739            else {
740                pdef->red = pent->co.local.red;
741                pdef->green = pent->co.local.green;
742                pdef->blue = pent->co.local.blue;
743            }
744            pdef->flags = DoRed | DoGreen | DoBlue;
745            pdef++;
746            n++;
747        }
748    }
749    if (n)
750        (*pmap->pScreen->StoreColors) (pmap, n, defs);
751    free(defs);
752}
753
754/* Tries to find a color in pmap that exactly matches the one requested in prgb
755 * if it can't it allocates one.
756 * Starts looking at pentFirst + *pPixel, so if you want a specific pixel,
757 * load *pPixel with that value, otherwise set it to 0
758 */
759static int
760FindColor(ColormapPtr pmap, EntryPtr pentFirst, int size, xrgb * prgb,
761          Pixel * pPixel, int channel, int client, ColorCompareProcPtr comp)
762{
763    EntryPtr pent;
764    Bool foundFree;
765    Pixel pixel, Free = 0;
766    int npix, count, *nump = NULL;
767    Pixel **pixp = NULL, *ppix;
768    xColorItem def;
769
770    foundFree = FALSE;
771
772    if ((pixel = *pPixel) >= size)
773        pixel = 0;
774    /* see if there is a match, and also look for a free entry */
775    for (pent = pentFirst + pixel, count = size; --count >= 0;) {
776        if (pent->refcnt > 0) {
777            if ((*comp) (pent, prgb)) {
778                if (client >= 0)
779                    pent->refcnt++;
780                *pPixel = pixel;
781                switch (channel) {
782                case REDMAP:
783                    *pPixel <<= pmap->pVisual->offsetRed;
784                case PSEUDOMAP:
785                    break;
786                case GREENMAP:
787                    *pPixel <<= pmap->pVisual->offsetGreen;
788                    break;
789                case BLUEMAP:
790                    *pPixel <<= pmap->pVisual->offsetBlue;
791                    break;
792                }
793                goto gotit;
794            }
795        }
796        else if (!foundFree && pent->refcnt == 0) {
797            Free = pixel;
798            foundFree = TRUE;
799            /* If we're initializing the colormap, then we are looking for
800             * the first free cell we can find, not to minimize the number
801             * of entries we use.  So don't look any further. */
802            if (pmap->flags & BeingCreated)
803                break;
804        }
805        pixel++;
806        if (pixel >= size) {
807            pent = pentFirst;
808            pixel = 0;
809        }
810        else
811            pent++;
812    }
813
814    /* If we got here, we didn't find a match.  If we also didn't find
815     * a free entry, we're out of luck.  Otherwise, we'll usurp a free
816     * entry and fill it in */
817    if (!foundFree)
818        return BadAlloc;
819    pent = pentFirst + Free;
820    pent->fShared = FALSE;
821    pent->refcnt = (client >= 0) ? 1 : AllocTemporary;
822
823    switch (channel) {
824    case PSEUDOMAP:
825        pent->co.local.red = prgb->red;
826        pent->co.local.green = prgb->green;
827        pent->co.local.blue = prgb->blue;
828        def.red = prgb->red;
829        def.green = prgb->green;
830        def.blue = prgb->blue;
831        def.flags = (DoRed | DoGreen | DoBlue);
832        if (client >= 0)
833            pmap->freeRed--;
834        def.pixel = Free;
835        break;
836
837    case REDMAP:
838        pent->co.local.red = prgb->red;
839        def.red = prgb->red;
840        def.green = pmap->green[0].co.local.green;
841        def.blue = pmap->blue[0].co.local.blue;
842        def.flags = DoRed;
843        if (client >= 0)
844            pmap->freeRed--;
845        def.pixel = Free << pmap->pVisual->offsetRed;
846        break;
847
848    case GREENMAP:
849        pent->co.local.green = prgb->green;
850        def.red = pmap->red[0].co.local.red;
851        def.green = prgb->green;
852        def.blue = pmap->blue[0].co.local.blue;
853        def.flags = DoGreen;
854        if (client >= 0)
855            pmap->freeGreen--;
856        def.pixel = Free << pmap->pVisual->offsetGreen;
857        break;
858
859    case BLUEMAP:
860        pent->co.local.blue = prgb->blue;
861        def.red = pmap->red[0].co.local.red;
862        def.green = pmap->green[0].co.local.green;
863        def.blue = prgb->blue;
864        def.flags = DoBlue;
865        if (client >= 0)
866            pmap->freeBlue--;
867        def.pixel = Free << pmap->pVisual->offsetBlue;
868        break;
869    }
870    (*pmap->pScreen->StoreColors) (pmap, 1, &def);
871    pixel = Free;
872    *pPixel = def.pixel;
873
874 gotit:
875    if (pmap->flags & BeingCreated || client == -1)
876        return Success;
877    /* Now remember the pixel, for freeing later */
878    switch (channel) {
879    case PSEUDOMAP:
880    case REDMAP:
881        nump = pmap->numPixelsRed;
882        pixp = pmap->clientPixelsRed;
883        break;
884
885    case GREENMAP:
886        nump = pmap->numPixelsGreen;
887        pixp = pmap->clientPixelsGreen;
888        break;
889
890    case BLUEMAP:
891        nump = pmap->numPixelsBlue;
892        pixp = pmap->clientPixelsBlue;
893        break;
894    }
895    npix = nump[client];
896    ppix = reallocarray(pixp[client], npix + 1, sizeof(Pixel));
897    if (!ppix) {
898        pent->refcnt--;
899        if (!pent->fShared)
900            switch (channel) {
901            case PSEUDOMAP:
902            case REDMAP:
903                pmap->freeRed++;
904                break;
905            case GREENMAP:
906                pmap->freeGreen++;
907                break;
908            case BLUEMAP:
909                pmap->freeBlue++;
910                break;
911            }
912        return BadAlloc;
913    }
914    ppix[npix] = pixel;
915    pixp[client] = ppix;
916    nump[client]++;
917
918    return Success;
919}
920
921/* Get a read-only color from a ColorMap (probably slow for large maps)
922 * Returns by changing the value in pred, pgreen, pblue and pPix
923 */
924int
925AllocColor(ColormapPtr pmap,
926           unsigned short *pred, unsigned short *pgreen, unsigned short *pblue,
927           Pixel * pPix, int client)
928{
929    Pixel pixR, pixG, pixB;
930    int entries;
931    xrgb rgb;
932    int class;
933    VisualPtr pVisual;
934    int npix;
935    Pixel *ppix;
936
937    pVisual = pmap->pVisual;
938    (*pmap->pScreen->ResolveColor) (pred, pgreen, pblue, pVisual);
939    rgb.red = *pred;
940    rgb.green = *pgreen;
941    rgb.blue = *pblue;
942    class = pmap->class;
943    entries = pVisual->ColormapEntries;
944
945    /* If the colormap is being created, then we want to be able to change
946     * the colormap, even if it's a static type. Otherwise, we'd never be
947     * able to initialize static colormaps
948     */
949    if (pmap->flags & BeingCreated)
950        class |= DynamicClass;
951
952    /* If this is one of the static storage classes, and we're not initializing
953     * it, the best we can do is to find the closest color entry to the
954     * requested one and return that.
955     */
956    switch (class) {
957    case StaticColor:
958    case StaticGray:
959        /* Look up all three components in the same pmap */
960        *pPix = pixR = FindBestPixel(pmap->red, entries, &rgb, PSEUDOMAP);
961        *pred = pmap->red[pixR].co.local.red;
962        *pgreen = pmap->red[pixR].co.local.green;
963        *pblue = pmap->red[pixR].co.local.blue;
964        npix = pmap->numPixelsRed[client];
965        ppix = reallocarray(pmap->clientPixelsRed[client],
966                            npix + 1, sizeof(Pixel));
967        if (!ppix)
968            return BadAlloc;
969        ppix[npix] = pixR;
970        pmap->clientPixelsRed[client] = ppix;
971        pmap->numPixelsRed[client]++;
972        break;
973
974    case TrueColor:
975        /* Look up each component in its own map, then OR them together */
976        pixR = FindBestPixel(pmap->red, NUMRED(pVisual), &rgb, REDMAP);
977        pixG = FindBestPixel(pmap->green, NUMGREEN(pVisual), &rgb, GREENMAP);
978        pixB = FindBestPixel(pmap->blue, NUMBLUE(pVisual), &rgb, BLUEMAP);
979        *pPix = (pixR << pVisual->offsetRed) |
980            (pixG << pVisual->offsetGreen) |
981            (pixB << pVisual->offsetBlue) | ALPHAMASK(pVisual);
982
983        *pred = pmap->red[pixR].co.local.red;
984        *pgreen = pmap->green[pixG].co.local.green;
985        *pblue = pmap->blue[pixB].co.local.blue;
986        npix = pmap->numPixelsRed[client];
987        ppix = reallocarray(pmap->clientPixelsRed[client],
988                            npix + 1, sizeof(Pixel));
989        if (!ppix)
990            return BadAlloc;
991        ppix[npix] = pixR;
992        pmap->clientPixelsRed[client] = ppix;
993        npix = pmap->numPixelsGreen[client];
994        ppix = reallocarray(pmap->clientPixelsGreen[client],
995                            npix + 1, sizeof(Pixel));
996        if (!ppix)
997            return BadAlloc;
998        ppix[npix] = pixG;
999        pmap->clientPixelsGreen[client] = ppix;
1000        npix = pmap->numPixelsBlue[client];
1001        ppix = reallocarray(pmap->clientPixelsBlue[client],
1002                            npix + 1, sizeof(Pixel));
1003        if (!ppix)
1004            return BadAlloc;
1005        ppix[npix] = pixB;
1006        pmap->clientPixelsBlue[client] = ppix;
1007        pmap->numPixelsRed[client]++;
1008        pmap->numPixelsGreen[client]++;
1009        pmap->numPixelsBlue[client]++;
1010        break;
1011
1012    case GrayScale:
1013    case PseudoColor:
1014        if (pmap->mid != pmap->pScreen->defColormap &&
1015            pmap->pVisual->vid == pmap->pScreen->rootVisual) {
1016            ColormapPtr prootmap;
1017
1018            dixLookupResourceByType((void **) &prootmap,
1019                                    pmap->pScreen->defColormap, RT_COLORMAP,
1020                                    clients[client], DixReadAccess);
1021
1022            if (pmap->class == prootmap->class)
1023                FindColorInRootCmap(prootmap, prootmap->red, entries, &rgb,
1024                                    pPix, PSEUDOMAP, AllComp);
1025        }
1026        if (FindColor(pmap, pmap->red, entries, &rgb, pPix, PSEUDOMAP,
1027                      client, AllComp) != Success)
1028            return BadAlloc;
1029        break;
1030
1031    case DirectColor:
1032        if (pmap->mid != pmap->pScreen->defColormap &&
1033            pmap->pVisual->vid == pmap->pScreen->rootVisual) {
1034            ColormapPtr prootmap;
1035
1036            dixLookupResourceByType((void **) &prootmap,
1037                                    pmap->pScreen->defColormap, RT_COLORMAP,
1038                                    clients[client], DixReadAccess);
1039
1040            if (pmap->class == prootmap->class) {
1041                pixR = (*pPix & pVisual->redMask) >> pVisual->offsetRed;
1042                FindColorInRootCmap(prootmap, prootmap->red, entries, &rgb,
1043                                    &pixR, REDMAP, RedComp);
1044                pixG = (*pPix & pVisual->greenMask) >> pVisual->offsetGreen;
1045                FindColorInRootCmap(prootmap, prootmap->green, entries, &rgb,
1046                                    &pixG, GREENMAP, GreenComp);
1047                pixB = (*pPix & pVisual->blueMask) >> pVisual->offsetBlue;
1048                FindColorInRootCmap(prootmap, prootmap->blue, entries, &rgb,
1049                                    &pixB, BLUEMAP, BlueComp);
1050                *pPix = pixR | pixG | pixB;
1051            }
1052        }
1053
1054        pixR = (*pPix & pVisual->redMask) >> pVisual->offsetRed;
1055        if (FindColor(pmap, pmap->red, NUMRED(pVisual), &rgb, &pixR, REDMAP,
1056                      client, RedComp) != Success)
1057            return BadAlloc;
1058        pixG = (*pPix & pVisual->greenMask) >> pVisual->offsetGreen;
1059        if (FindColor(pmap, pmap->green, NUMGREEN(pVisual), &rgb, &pixG,
1060                      GREENMAP, client, GreenComp) != Success) {
1061            (void) FreeCo(pmap, client, REDMAP, 1, &pixR, (Pixel) 0);
1062            return BadAlloc;
1063        }
1064        pixB = (*pPix & pVisual->blueMask) >> pVisual->offsetBlue;
1065        if (FindColor(pmap, pmap->blue, NUMBLUE(pVisual), &rgb, &pixB, BLUEMAP,
1066                      client, BlueComp) != Success) {
1067            (void) FreeCo(pmap, client, GREENMAP, 1, &pixG, (Pixel) 0);
1068            (void) FreeCo(pmap, client, REDMAP, 1, &pixR, (Pixel) 0);
1069            return BadAlloc;
1070        }
1071        *pPix = pixR | pixG | pixB | ALPHAMASK(pVisual);
1072
1073        break;
1074    }
1075
1076    /* if this is the client's first pixel in this colormap, tell the
1077     * resource manager that the client has pixels in this colormap which
1078     * should be freed when the client dies */
1079    if ((pmap->numPixelsRed[client] == 1) &&
1080        (CLIENT_ID(pmap->mid) != client) && !(pmap->flags & BeingCreated)) {
1081        colorResource *pcr;
1082
1083        pcr = malloc(sizeof(colorResource));
1084        if (!pcr) {
1085            (void) FreeColors(pmap, client, 1, pPix, (Pixel) 0);
1086            return BadAlloc;
1087        }
1088        pcr->mid = pmap->mid;
1089        pcr->client = client;
1090        if (!AddResource(FakeClientID(client), RT_CMAPENTRY, (void *) pcr))
1091            return BadAlloc;
1092    }
1093    return Success;
1094}
1095
1096/*
1097 * FakeAllocColor -- fake an AllocColor request by
1098 * returning a free pixel if available, otherwise returning
1099 * the closest matching pixel.  This is used by the mi
1100 * software sprite code to recolor cursors.  A nice side-effect
1101 * is that this routine will never return failure.
1102 */
1103
1104void
1105FakeAllocColor(ColormapPtr pmap, xColorItem * item)
1106{
1107    Pixel pixR, pixG, pixB;
1108    Pixel temp;
1109    int entries;
1110    xrgb rgb;
1111    int class;
1112    VisualPtr pVisual;
1113
1114    pVisual = pmap->pVisual;
1115    rgb.red = item->red;
1116    rgb.green = item->green;
1117    rgb.blue = item->blue;
1118    (*pmap->pScreen->ResolveColor) (&rgb.red, &rgb.green, &rgb.blue, pVisual);
1119    class = pmap->class;
1120    entries = pVisual->ColormapEntries;
1121
1122    switch (class) {
1123    case GrayScale:
1124    case PseudoColor:
1125        temp = 0;
1126        item->pixel = 0;
1127        if (FindColor(pmap, pmap->red, entries, &rgb, &temp, PSEUDOMAP,
1128                      -1, AllComp) == Success) {
1129            item->pixel = temp;
1130            break;
1131        }
1132        /* fall through ... */
1133    case StaticColor:
1134    case StaticGray:
1135        item->pixel = FindBestPixel(pmap->red, entries, &rgb, PSEUDOMAP);
1136        break;
1137
1138    case DirectColor:
1139        /* Look up each component in its own map, then OR them together */
1140        pixR = (item->pixel & pVisual->redMask) >> pVisual->offsetRed;
1141        pixG = (item->pixel & pVisual->greenMask) >> pVisual->offsetGreen;
1142        pixB = (item->pixel & pVisual->blueMask) >> pVisual->offsetBlue;
1143        if (FindColor(pmap, pmap->red, NUMRED(pVisual), &rgb, &pixR, REDMAP,
1144                      -1, RedComp) != Success)
1145            pixR = FindBestPixel(pmap->red, NUMRED(pVisual), &rgb, REDMAP)
1146                << pVisual->offsetRed;
1147        if (FindColor(pmap, pmap->green, NUMGREEN(pVisual), &rgb, &pixG,
1148                      GREENMAP, -1, GreenComp) != Success)
1149            pixG = FindBestPixel(pmap->green, NUMGREEN(pVisual), &rgb,
1150                                 GREENMAP) << pVisual->offsetGreen;
1151        if (FindColor(pmap, pmap->blue, NUMBLUE(pVisual), &rgb, &pixB, BLUEMAP,
1152                      -1, BlueComp) != Success)
1153            pixB = FindBestPixel(pmap->blue, NUMBLUE(pVisual), &rgb, BLUEMAP)
1154                << pVisual->offsetBlue;
1155        item->pixel = pixR | pixG | pixB;
1156        break;
1157
1158    case TrueColor:
1159        /* Look up each component in its own map, then OR them together */
1160        pixR = FindBestPixel(pmap->red, NUMRED(pVisual), &rgb, REDMAP);
1161        pixG = FindBestPixel(pmap->green, NUMGREEN(pVisual), &rgb, GREENMAP);
1162        pixB = FindBestPixel(pmap->blue, NUMBLUE(pVisual), &rgb, BLUEMAP);
1163        item->pixel = (pixR << pVisual->offsetRed) |
1164            (pixG << pVisual->offsetGreen) | (pixB << pVisual->offsetBlue);
1165        break;
1166    }
1167}
1168
1169/* free a pixel value obtained from FakeAllocColor */
1170void
1171FakeFreeColor(ColormapPtr pmap, Pixel pixel)
1172{
1173    VisualPtr pVisual;
1174    Pixel pixR, pixG, pixB;
1175
1176    switch (pmap->class) {
1177    case GrayScale:
1178    case PseudoColor:
1179        if (pmap->red[pixel].refcnt == AllocTemporary)
1180            pmap->red[pixel].refcnt = 0;
1181        break;
1182    case DirectColor:
1183        pVisual = pmap->pVisual;
1184        pixR = (pixel & pVisual->redMask) >> pVisual->offsetRed;
1185        pixG = (pixel & pVisual->greenMask) >> pVisual->offsetGreen;
1186        pixB = (pixel & pVisual->blueMask) >> pVisual->offsetBlue;
1187        if (pmap->red[pixR].refcnt == AllocTemporary)
1188            pmap->red[pixR].refcnt = 0;
1189        if (pmap->green[pixG].refcnt == AllocTemporary)
1190            pmap->green[pixG].refcnt = 0;
1191        if (pmap->blue[pixB].refcnt == AllocTemporary)
1192            pmap->blue[pixB].refcnt = 0;
1193        break;
1194    }
1195}
1196
1197typedef unsigned short BigNumUpper;
1198typedef unsigned long BigNumLower;
1199
1200#define BIGNUMLOWERBITS	24
1201#define BIGNUMUPPERBITS	16
1202#define BIGNUMLOWER (1 << BIGNUMLOWERBITS)
1203#define BIGNUMUPPER (1 << BIGNUMUPPERBITS)
1204#define UPPERPART(i)	((i) >> BIGNUMLOWERBITS)
1205#define LOWERPART(i)	((i) & (BIGNUMLOWER - 1))
1206
1207typedef struct _bignum {
1208    BigNumUpper upper;
1209    BigNumLower lower;
1210} BigNumRec, *BigNumPtr;
1211
1212#define BigNumGreater(x,y) (((x)->upper > (y)->upper) ||\
1213			    ((x)->upper == (y)->upper && (x)->lower > (y)->lower))
1214
1215#define UnsignedToBigNum(u,r)	(((r)->upper = UPPERPART(u)), \
1216				 ((r)->lower = LOWERPART(u)))
1217
1218#define MaxBigNum(r)		(((r)->upper = BIGNUMUPPER-1), \
1219				 ((r)->lower = BIGNUMLOWER-1))
1220
1221static void
1222BigNumAdd(BigNumPtr x, BigNumPtr y, BigNumPtr r)
1223{
1224    BigNumLower lower, carry = 0;
1225
1226    lower = x->lower + y->lower;
1227    if (lower >= BIGNUMLOWER) {
1228        lower -= BIGNUMLOWER;
1229        carry = 1;
1230    }
1231    r->lower = lower;
1232    r->upper = x->upper + y->upper + carry;
1233}
1234
1235static Pixel
1236FindBestPixel(EntryPtr pentFirst, int size, xrgb * prgb, int channel)
1237{
1238    EntryPtr pent;
1239    Pixel pixel, final;
1240    long dr, dg, db;
1241    unsigned long sq;
1242    BigNumRec minval, sum, temp;
1243
1244    final = 0;
1245    MaxBigNum(&minval);
1246    /* look for the minimal difference */
1247    for (pent = pentFirst, pixel = 0; pixel < size; pent++, pixel++) {
1248        dr = dg = db = 0;
1249        switch (channel) {
1250        case PSEUDOMAP:
1251            dg = (long) pent->co.local.green - prgb->green;
1252            db = (long) pent->co.local.blue - prgb->blue;
1253            /* fallthrough */
1254        case REDMAP:
1255            dr = (long) pent->co.local.red - prgb->red;
1256            break;
1257        case GREENMAP:
1258            dg = (long) pent->co.local.green - prgb->green;
1259            break;
1260        case BLUEMAP:
1261            db = (long) pent->co.local.blue - prgb->blue;
1262            break;
1263        }
1264        sq = dr * dr;
1265        UnsignedToBigNum(sq, &sum);
1266        sq = dg * dg;
1267        UnsignedToBigNum(sq, &temp);
1268        BigNumAdd(&sum, &temp, &sum);
1269        sq = db * db;
1270        UnsignedToBigNum(sq, &temp);
1271        BigNumAdd(&sum, &temp, &sum);
1272        if (BigNumGreater(&minval, &sum)) {
1273            final = pixel;
1274            minval = sum;
1275        }
1276    }
1277    return final;
1278}
1279
1280static void
1281FindColorInRootCmap(ColormapPtr pmap, EntryPtr pentFirst, int size,
1282                    xrgb * prgb, Pixel * pPixel, int channel,
1283                    ColorCompareProcPtr comp)
1284{
1285    EntryPtr pent;
1286    Pixel pixel;
1287    int count;
1288
1289    if ((pixel = *pPixel) >= size)
1290        pixel = 0;
1291    for (pent = pentFirst + pixel, count = size; --count >= 0; pent++, pixel++) {
1292        if (pent->refcnt > 0 && (*comp) (pent, prgb)) {
1293            switch (channel) {
1294            case REDMAP:
1295                pixel <<= pmap->pVisual->offsetRed;
1296                break;
1297            case GREENMAP:
1298                pixel <<= pmap->pVisual->offsetGreen;
1299                break;
1300            case BLUEMAP:
1301                pixel <<= pmap->pVisual->offsetBlue;
1302                break;
1303            default:           /* PSEUDOMAP */
1304                break;
1305            }
1306            *pPixel = pixel;
1307        }
1308    }
1309}
1310
1311/* Comparison functions -- passed to FindColor to determine if an
1312 * entry is already the color we're looking for or not */
1313static int
1314AllComp(EntryPtr pent, xrgb * prgb)
1315{
1316    if ((pent->co.local.red == prgb->red) &&
1317        (pent->co.local.green == prgb->green) &&
1318        (pent->co.local.blue == prgb->blue))
1319        return 1;
1320    return 0;
1321}
1322
1323static int
1324RedComp(EntryPtr pent, xrgb * prgb)
1325{
1326    if (pent->co.local.red == prgb->red)
1327        return 1;
1328    return 0;
1329}
1330
1331static int
1332GreenComp(EntryPtr pent, xrgb * prgb)
1333{
1334    if (pent->co.local.green == prgb->green)
1335        return 1;
1336    return 0;
1337}
1338
1339static int
1340BlueComp(EntryPtr pent, xrgb * prgb)
1341{
1342    if (pent->co.local.blue == prgb->blue)
1343        return 1;
1344    return 0;
1345}
1346
1347/* Read the color value of a cell */
1348
1349int
1350QueryColors(ColormapPtr pmap, int count, Pixel * ppixIn, xrgb * prgbList,
1351            ClientPtr client)
1352{
1353    Pixel *ppix, pixel;
1354    xrgb *prgb;
1355    VisualPtr pVisual;
1356    EntryPtr pent;
1357    Pixel i;
1358    int errVal = Success;
1359
1360    pVisual = pmap->pVisual;
1361    if ((pmap->class | DynamicClass) == DirectColor) {
1362        int numred, numgreen, numblue;
1363        Pixel rgbbad;
1364
1365        numred = NUMRED(pVisual);
1366        numgreen = NUMGREEN(pVisual);
1367        numblue = NUMBLUE(pVisual);
1368        rgbbad = ~RGBMASK(pVisual);
1369        for (ppix = ppixIn, prgb = prgbList; --count >= 0; ppix++, prgb++) {
1370            pixel = *ppix;
1371            if (pixel & rgbbad) {
1372                client->errorValue = pixel;
1373                errVal = BadValue;
1374                continue;
1375            }
1376            i = (pixel & pVisual->redMask) >> pVisual->offsetRed;
1377            if (i >= numred) {
1378                client->errorValue = pixel;
1379                errVal = BadValue;
1380                continue;
1381            }
1382            prgb->red = pmap->red[i].co.local.red;
1383            i = (pixel & pVisual->greenMask) >> pVisual->offsetGreen;
1384            if (i >= numgreen) {
1385                client->errorValue = pixel;
1386                errVal = BadValue;
1387                continue;
1388            }
1389            prgb->green = pmap->green[i].co.local.green;
1390            i = (pixel & pVisual->blueMask) >> pVisual->offsetBlue;
1391            if (i >= numblue) {
1392                client->errorValue = pixel;
1393                errVal = BadValue;
1394                continue;
1395            }
1396            prgb->blue = pmap->blue[i].co.local.blue;
1397        }
1398    }
1399    else {
1400        for (ppix = ppixIn, prgb = prgbList; --count >= 0; ppix++, prgb++) {
1401            pixel = *ppix;
1402            if (pixel >= pVisual->ColormapEntries) {
1403                client->errorValue = pixel;
1404                errVal = BadValue;
1405            }
1406            else {
1407                pent = (EntryPtr) &pmap->red[pixel];
1408                if (pent->fShared) {
1409                    prgb->red = pent->co.shco.red->color;
1410                    prgb->green = pent->co.shco.green->color;
1411                    prgb->blue = pent->co.shco.blue->color;
1412                }
1413                else {
1414                    prgb->red = pent->co.local.red;
1415                    prgb->green = pent->co.local.green;
1416                    prgb->blue = pent->co.local.blue;
1417                }
1418            }
1419        }
1420    }
1421    return errVal;
1422}
1423
1424static void
1425FreePixels(ColormapPtr pmap, int client)
1426{
1427    Pixel *ppix, *ppixStart;
1428    int n;
1429    int class;
1430
1431    class = pmap->class;
1432    ppixStart = pmap->clientPixelsRed[client];
1433    if (class & DynamicClass) {
1434        n = pmap->numPixelsRed[client];
1435        for (ppix = ppixStart; --n >= 0;) {
1436            FreeCell(pmap, *ppix, REDMAP);
1437            ppix++;
1438        }
1439    }
1440
1441    free(ppixStart);
1442    pmap->clientPixelsRed[client] = (Pixel *) NULL;
1443    pmap->numPixelsRed[client] = 0;
1444    if ((class | DynamicClass) == DirectColor) {
1445        ppixStart = pmap->clientPixelsGreen[client];
1446        if (class & DynamicClass)
1447            for (ppix = ppixStart, n = pmap->numPixelsGreen[client]; --n >= 0;)
1448                FreeCell(pmap, *ppix++, GREENMAP);
1449        free(ppixStart);
1450        pmap->clientPixelsGreen[client] = (Pixel *) NULL;
1451        pmap->numPixelsGreen[client] = 0;
1452
1453        ppixStart = pmap->clientPixelsBlue[client];
1454        if (class & DynamicClass)
1455            for (ppix = ppixStart, n = pmap->numPixelsBlue[client]; --n >= 0;)
1456                FreeCell(pmap, *ppix++, BLUEMAP);
1457        free(ppixStart);
1458        pmap->clientPixelsBlue[client] = (Pixel *) NULL;
1459        pmap->numPixelsBlue[client] = 0;
1460    }
1461}
1462
1463/**
1464 * Frees all of a client's colors and cells.
1465 *
1466 *  \param value  must conform to DeleteType
1467 *  \unused fakeid
1468 */
1469int
1470FreeClientPixels(void *value, XID fakeid)
1471{
1472    void *pmap;
1473    colorResource *pcr = value;
1474    int rc;
1475
1476    rc = dixLookupResourceByType(&pmap, pcr->mid, RT_COLORMAP, serverClient,
1477                                 DixRemoveAccess);
1478    if (rc == Success)
1479        FreePixels((ColormapPtr) pmap, pcr->client);
1480    free(pcr);
1481    return Success;
1482}
1483
1484int
1485AllocColorCells(int client, ColormapPtr pmap, int colors, int planes,
1486                Bool contig, Pixel * ppix, Pixel * masks)
1487{
1488    Pixel rmask, gmask, bmask, *ppixFirst, r, g, b;
1489    int n, class;
1490    int ok;
1491    int oldcount;
1492    colorResource *pcr = (colorResource *) NULL;
1493
1494    class = pmap->class;
1495    if (!(class & DynamicClass))
1496        return BadAlloc;        /* Shouldn't try on this type */
1497    oldcount = pmap->numPixelsRed[client];
1498    if (pmap->class == DirectColor)
1499        oldcount += pmap->numPixelsGreen[client] + pmap->numPixelsBlue[client];
1500    if (!oldcount && (CLIENT_ID(pmap->mid) != client)) {
1501        pcr = malloc(sizeof(colorResource));
1502        if (!pcr)
1503            return BadAlloc;
1504    }
1505
1506    if (pmap->class == DirectColor) {
1507        ok = AllocDirect(client, pmap, colors, planes, planes, planes,
1508                         contig, ppix, &rmask, &gmask, &bmask);
1509        if (ok == Success) {
1510            for (r = g = b = 1, n = planes; --n >= 0; r += r, g += g, b += b) {
1511                while (!(rmask & r))
1512                    r += r;
1513                while (!(gmask & g))
1514                    g += g;
1515                while (!(bmask & b))
1516                    b += b;
1517                *masks++ = r | g | b;
1518            }
1519        }
1520    }
1521    else {
1522        ok = AllocPseudo(client, pmap, colors, planes, contig, ppix, &rmask,
1523                         &ppixFirst);
1524        if (ok == Success) {
1525            for (r = 1, n = planes; --n >= 0; r += r) {
1526                while (!(rmask & r))
1527                    r += r;
1528                *masks++ = r;
1529            }
1530        }
1531    }
1532
1533    /* if this is the client's first pixels in this colormap, tell the
1534     * resource manager that the client has pixels in this colormap which
1535     * should be freed when the client dies */
1536    if ((ok == Success) && pcr) {
1537        pcr->mid = pmap->mid;
1538        pcr->client = client;
1539        if (!AddResource(FakeClientID(client), RT_CMAPENTRY, (void *) pcr))
1540            ok = BadAlloc;
1541    }
1542    else
1543        free(pcr);
1544
1545    return ok;
1546}
1547
1548int
1549AllocColorPlanes(int client, ColormapPtr pmap, int colors,
1550                 int r, int g, int b, Bool contig, Pixel * pixels,
1551                 Pixel * prmask, Pixel * pgmask, Pixel * pbmask)
1552{
1553    int ok;
1554    Pixel mask, *ppixFirst;
1555    Pixel shift;
1556    int i;
1557    int class;
1558    int oldcount;
1559    colorResource *pcr = (colorResource *) NULL;
1560
1561    class = pmap->class;
1562    if (!(class & DynamicClass))
1563        return BadAlloc;        /* Shouldn't try on this type */
1564    oldcount = pmap->numPixelsRed[client];
1565    if (class == DirectColor)
1566        oldcount += pmap->numPixelsGreen[client] + pmap->numPixelsBlue[client];
1567    if (!oldcount && (CLIENT_ID(pmap->mid) != client)) {
1568        pcr = malloc(sizeof(colorResource));
1569        if (!pcr)
1570            return BadAlloc;
1571    }
1572
1573    if (class == DirectColor) {
1574        ok = AllocDirect(client, pmap, colors, r, g, b, contig, pixels,
1575                         prmask, pgmask, pbmask);
1576    }
1577    else {
1578        /* Allocate the proper pixels */
1579        /* XXX This is sort of bad, because of contig is set, we force all
1580         * r + g + b bits to be contiguous.  Should only force contiguity
1581         * per mask
1582         */
1583        ok = AllocPseudo(client, pmap, colors, r + g + b, contig, pixels,
1584                         &mask, &ppixFirst);
1585
1586        if (ok == Success) {
1587            /* now split that mask into three */
1588            *prmask = *pgmask = *pbmask = 0;
1589            shift = 1;
1590            for (i = r; --i >= 0; shift += shift) {
1591                while (!(mask & shift))
1592                    shift += shift;
1593                *prmask |= shift;
1594            }
1595            for (i = g; --i >= 0; shift += shift) {
1596                while (!(mask & shift))
1597                    shift += shift;
1598                *pgmask |= shift;
1599            }
1600            for (i = b; --i >= 0; shift += shift) {
1601                while (!(mask & shift))
1602                    shift += shift;
1603                *pbmask |= shift;
1604            }
1605
1606            /* set up the shared color cells */
1607            if (!AllocShared(pmap, pixels, colors, r, g, b,
1608                             *prmask, *pgmask, *pbmask, ppixFirst)) {
1609                (void) FreeColors(pmap, client, colors, pixels, mask);
1610                ok = BadAlloc;
1611            }
1612        }
1613    }
1614
1615    /* if this is the client's first pixels in this colormap, tell the
1616     * resource manager that the client has pixels in this colormap which
1617     * should be freed when the client dies */
1618    if ((ok == Success) && pcr) {
1619        pcr->mid = pmap->mid;
1620        pcr->client = client;
1621        if (!AddResource(FakeClientID(client), RT_CMAPENTRY, (void *) pcr))
1622            ok = BadAlloc;
1623    }
1624    else
1625        free(pcr);
1626
1627    return ok;
1628}
1629
1630static int
1631AllocDirect(int client, ColormapPtr pmap, int c, int r, int g, int b,
1632            Bool contig, Pixel * pixels, Pixel * prmask, Pixel * pgmask,
1633            Pixel * pbmask)
1634{
1635    Pixel *ppixRed, *ppixGreen, *ppixBlue;
1636    Pixel *ppix, *pDst, *p;
1637    int npix, npixR, npixG, npixB;
1638    Bool okR, okG, okB;
1639    Pixel *rpix = 0, *gpix = 0, *bpix = 0;
1640
1641    npixR = c << r;
1642    npixG = c << g;
1643    npixB = c << b;
1644    if ((r >= 32) || (g >= 32) || (b >= 32) ||
1645        (npixR > pmap->freeRed) || (npixR < c) ||
1646        (npixG > pmap->freeGreen) || (npixG < c) ||
1647        (npixB > pmap->freeBlue) || (npixB < c))
1648        return BadAlloc;
1649
1650    /* start out with empty pixels */
1651    for (p = pixels; p < pixels + c; p++)
1652        *p = 0;
1653
1654    ppixRed = xallocarray(npixR, sizeof(Pixel));
1655    ppixGreen = xallocarray(npixG, sizeof(Pixel));
1656    ppixBlue = xallocarray(npixB, sizeof(Pixel));
1657    if (!ppixRed || !ppixGreen || !ppixBlue) {
1658        free(ppixBlue);
1659        free(ppixGreen);
1660        free(ppixRed);
1661        return BadAlloc;
1662    }
1663
1664    okR = AllocCP(pmap, pmap->red, c, r, contig, ppixRed, prmask);
1665    okG = AllocCP(pmap, pmap->green, c, g, contig, ppixGreen, pgmask);
1666    okB = AllocCP(pmap, pmap->blue, c, b, contig, ppixBlue, pbmask);
1667
1668    if (okR && okG && okB) {
1669        rpix = reallocarray(pmap->clientPixelsRed[client],
1670                            pmap->numPixelsRed[client] + (c << r),
1671                            sizeof(Pixel));
1672        if (rpix)
1673            pmap->clientPixelsRed[client] = rpix;
1674        gpix = reallocarray(pmap->clientPixelsGreen[client],
1675                            pmap->numPixelsGreen[client] + (c << g),
1676                            sizeof(Pixel));
1677        if (gpix)
1678            pmap->clientPixelsGreen[client] = gpix;
1679        bpix = reallocarray(pmap->clientPixelsBlue[client],
1680                            pmap->numPixelsBlue[client] + (c << b),
1681                            sizeof(Pixel));
1682        if (bpix)
1683            pmap->clientPixelsBlue[client] = bpix;
1684    }
1685
1686    if (!okR || !okG || !okB || !rpix || !gpix || !bpix) {
1687        if (okR)
1688            for (ppix = ppixRed, npix = npixR; --npix >= 0; ppix++)
1689                pmap->red[*ppix].refcnt = 0;
1690        if (okG)
1691            for (ppix = ppixGreen, npix = npixG; --npix >= 0; ppix++)
1692                pmap->green[*ppix].refcnt = 0;
1693        if (okB)
1694            for (ppix = ppixBlue, npix = npixB; --npix >= 0; ppix++)
1695                pmap->blue[*ppix].refcnt = 0;
1696        free(ppixBlue);
1697        free(ppixGreen);
1698        free(ppixRed);
1699        return BadAlloc;
1700    }
1701
1702    *prmask <<= pmap->pVisual->offsetRed;
1703    *pgmask <<= pmap->pVisual->offsetGreen;
1704    *pbmask <<= pmap->pVisual->offsetBlue;
1705
1706    ppix = rpix + pmap->numPixelsRed[client];
1707    for (pDst = pixels, p = ppixRed; p < ppixRed + npixR; p++) {
1708        *ppix++ = *p;
1709        if (p < ppixRed + c)
1710            *pDst++ |= *p << pmap->pVisual->offsetRed;
1711    }
1712    pmap->numPixelsRed[client] += npixR;
1713    pmap->freeRed -= npixR;
1714
1715    ppix = gpix + pmap->numPixelsGreen[client];
1716    for (pDst = pixels, p = ppixGreen; p < ppixGreen + npixG; p++) {
1717        *ppix++ = *p;
1718        if (p < ppixGreen + c)
1719            *pDst++ |= *p << pmap->pVisual->offsetGreen;
1720    }
1721    pmap->numPixelsGreen[client] += npixG;
1722    pmap->freeGreen -= npixG;
1723
1724    ppix = bpix + pmap->numPixelsBlue[client];
1725    for (pDst = pixels, p = ppixBlue; p < ppixBlue + npixB; p++) {
1726        *ppix++ = *p;
1727        if (p < ppixBlue + c)
1728            *pDst++ |= *p << pmap->pVisual->offsetBlue;
1729    }
1730    pmap->numPixelsBlue[client] += npixB;
1731    pmap->freeBlue -= npixB;
1732
1733    for (pDst = pixels; pDst < pixels + c; pDst++)
1734        *pDst |= ALPHAMASK(pmap->pVisual);
1735
1736    free(ppixBlue);
1737    free(ppixGreen);
1738    free(ppixRed);
1739
1740    return Success;
1741}
1742
1743static int
1744AllocPseudo(int client, ColormapPtr pmap, int c, int r, Bool contig,
1745            Pixel * pixels, Pixel * pmask, Pixel ** pppixFirst)
1746{
1747    Pixel *ppix, *p, *pDst, *ppixTemp;
1748    int npix;
1749    Bool ok;
1750
1751    npix = c << r;
1752    if ((r >= 32) || (npix > pmap->freeRed) || (npix < c))
1753        return BadAlloc;
1754    if (!(ppixTemp = xallocarray(npix, sizeof(Pixel))))
1755        return BadAlloc;
1756    ok = AllocCP(pmap, pmap->red, c, r, contig, ppixTemp, pmask);
1757
1758    if (ok) {
1759
1760        /* all the allocated pixels are added to the client pixel list,
1761         * but only the unique ones are returned to the client */
1762        ppix = reallocarray(pmap->clientPixelsRed[client],
1763                            pmap->numPixelsRed[client] + npix, sizeof(Pixel));
1764        if (!ppix) {
1765            for (p = ppixTemp; p < ppixTemp + npix; p++)
1766                pmap->red[*p].refcnt = 0;
1767            free(ppixTemp);
1768            return BadAlloc;
1769        }
1770        pmap->clientPixelsRed[client] = ppix;
1771        ppix += pmap->numPixelsRed[client];
1772        *pppixFirst = ppix;
1773        pDst = pixels;
1774        for (p = ppixTemp; p < ppixTemp + npix; p++) {
1775            *ppix++ = *p;
1776            if (p < ppixTemp + c)
1777                *pDst++ = *p;
1778        }
1779        pmap->numPixelsRed[client] += npix;
1780        pmap->freeRed -= npix;
1781    }
1782    free(ppixTemp);
1783    return ok ? Success : BadAlloc;
1784}
1785
1786/* Allocates count << planes pixels from colormap pmap for client. If
1787 * contig, then the plane mask is made of consecutive bits.  Returns
1788 * all count << pixels in the array pixels. The first count of those
1789 * pixels are the unique pixels.  *pMask has the mask to Or with the
1790 * unique pixels to get the rest of them.
1791 *
1792 * Returns True iff all pixels could be allocated
1793 * All cells allocated will have refcnt set to AllocPrivate and shared to FALSE
1794 * (see AllocShared for why we care)
1795 */
1796static Bool
1797AllocCP(ColormapPtr pmap, EntryPtr pentFirst, int count, int planes,
1798        Bool contig, Pixel * pixels, Pixel * pMask)
1799{
1800    EntryPtr ent;
1801    Pixel pixel, base, entries, maxp, save;
1802    int dplanes, found;
1803    Pixel *ppix;
1804    Pixel mask;
1805    Pixel finalmask;
1806
1807    dplanes = pmap->pVisual->nplanes;
1808
1809    /* Easy case.  Allocate pixels only */
1810    if (planes == 0) {
1811        /* allocate writable entries */
1812        ppix = pixels;
1813        ent = pentFirst;
1814        pixel = 0;
1815        while (--count >= 0) {
1816            /* Just find count unallocated cells */
1817            while (ent->refcnt) {
1818                ent++;
1819                pixel++;
1820            }
1821            ent->refcnt = AllocPrivate;
1822            *ppix++ = pixel;
1823            ent->fShared = FALSE;
1824        }
1825        *pMask = 0;
1826        return TRUE;
1827    }
1828    else if (planes > dplanes) {
1829        return FALSE;
1830    }
1831
1832    /* General case count pixels * 2 ^ planes cells to be allocated */
1833
1834    /* make room for new pixels */
1835    ent = pentFirst;
1836
1837    /* first try for contiguous planes, since it's fastest */
1838    for (mask = (((Pixel) 1) << planes) - 1, base = 1, dplanes -= (planes - 1);
1839         --dplanes >= 0; mask += mask, base += base) {
1840        ppix = pixels;
1841        found = 0;
1842        pixel = 0;
1843        entries = pmap->pVisual->ColormapEntries - mask;
1844        while (pixel < entries) {
1845            save = pixel;
1846            maxp = pixel + mask + base;
1847            /* check if all are free */
1848            while (pixel != maxp && ent[pixel].refcnt == 0)
1849                pixel += base;
1850            if (pixel == maxp) {
1851                /* this one works */
1852                *ppix++ = save;
1853                found++;
1854                if (found == count) {
1855                    /* found enough, allocate them all */
1856                    while (--count >= 0) {
1857                        pixel = pixels[count];
1858                        maxp = pixel + mask;
1859                        while (1) {
1860                            ent[pixel].refcnt = AllocPrivate;
1861                            ent[pixel].fShared = FALSE;
1862                            if (pixel == maxp)
1863                                break;
1864                            pixel += base;
1865                            *ppix++ = pixel;
1866                        }
1867                    }
1868                    *pMask = mask;
1869                    return TRUE;
1870                }
1871            }
1872            pixel = save + 1;
1873            if (pixel & mask)
1874                pixel += mask;
1875        }
1876    }
1877
1878    dplanes = pmap->pVisual->nplanes;
1879    if (contig || planes == 1 || dplanes < 3)
1880        return FALSE;
1881
1882    /* this will be very slow for large maps, need a better algorithm */
1883
1884    /*
1885       we can generate the smallest and largest numbers that fits in dplanes
1886       bits and contain exactly planes bits set as follows. First, we need to
1887       check that it is possible to generate such a mask at all.
1888       (Non-contiguous masks need one more bit than contiguous masks). Then
1889       the smallest such mask consists of the rightmost planes-1 bits set, then
1890       a zero, then a one in position planes + 1. The formula is
1891       (3 << (planes-1)) -1
1892       The largest such masks consists of the leftmost planes-1 bits set, then
1893       a zero, then a one bit in position dplanes-planes-1. If dplanes is
1894       smaller than 32 (the number of bits in a word) then the formula is:
1895       (1<<dplanes) - (1<<(dplanes-planes+1) + (1<<dplanes-planes-1)
1896       If dplanes = 32, then we can't calculate (1<<dplanes) and we have
1897       to use:
1898       ( (1<<(planes-1)) - 1) << (dplanes-planes+1) + (1<<(dplanes-planes-1))
1899
1900       << Thank you, Loretta>>>
1901
1902     */
1903
1904    finalmask =
1905        (((((Pixel) 1) << (planes - 1)) - 1) << (dplanes - planes + 1)) +
1906        (((Pixel) 1) << (dplanes - planes - 1));
1907    for (mask = (((Pixel) 3) << (planes - 1)) - 1; mask <= finalmask; mask++) {
1908        /* next 3 magic statements count number of ones (HAKMEM #169) */
1909        pixel = (mask >> 1) & 033333333333;
1910        pixel = mask - pixel - ((pixel >> 1) & 033333333333);
1911        if ((((pixel + (pixel >> 3)) & 030707070707) % 077) != planes)
1912            continue;
1913        ppix = pixels;
1914        found = 0;
1915        entries = pmap->pVisual->ColormapEntries - mask;
1916        base = lowbit(mask);
1917        for (pixel = 0; pixel < entries; pixel++) {
1918            if (pixel & mask)
1919                continue;
1920            maxp = 0;
1921            /* check if all are free */
1922            while (ent[pixel + maxp].refcnt == 0) {
1923                GetNextBitsOrBreak(maxp, mask, base);
1924            }
1925            if ((maxp < mask) || (ent[pixel + mask].refcnt != 0))
1926                continue;
1927            /* this one works */
1928            *ppix++ = pixel;
1929            found++;
1930            if (found < count)
1931                continue;
1932            /* found enough, allocate them all */
1933            while (--count >= 0) {
1934                pixel = (pixels)[count];
1935                maxp = 0;
1936                while (1) {
1937                    ent[pixel + maxp].refcnt = AllocPrivate;
1938                    ent[pixel + maxp].fShared = FALSE;
1939                    GetNextBitsOrBreak(maxp, mask, base);
1940                    *ppix++ = pixel + maxp;
1941                }
1942            }
1943
1944            *pMask = mask;
1945            return TRUE;
1946        }
1947    }
1948    return FALSE;
1949}
1950
1951/**
1952 *
1953 *  \param ppixFirst  First of the client's new pixels
1954 */
1955static Bool
1956AllocShared(ColormapPtr pmap, Pixel * ppix, int c, int r, int g, int b,
1957            Pixel rmask, Pixel gmask, Pixel bmask, Pixel * ppixFirst)
1958{
1959    Pixel *pptr, *cptr;
1960    int npix, z, npixClientNew, npixShared;
1961    Pixel basemask, base, bits, common;
1962    SHAREDCOLOR *pshared, **ppshared, **psharedList;
1963
1964    npixClientNew = c << (r + g + b);
1965    npixShared = (c << r) + (c << g) + (c << b);
1966    psharedList = xallocarray(npixShared, sizeof(SHAREDCOLOR *));
1967    if (!psharedList)
1968        return FALSE;
1969    ppshared = psharedList;
1970    for (z = npixShared; --z >= 0;) {
1971        if (!(ppshared[z] = malloc(sizeof(SHAREDCOLOR)))) {
1972            for (z++; z < npixShared; z++)
1973                free(ppshared[z]);
1974            free(psharedList);
1975            return FALSE;
1976        }
1977    }
1978    for (pptr = ppix, npix = c; --npix >= 0; pptr++) {
1979        basemask = ~(gmask | bmask);
1980        common = *pptr & basemask;
1981        if (rmask) {
1982            bits = 0;
1983            base = lowbit(rmask);
1984            while (1) {
1985                pshared = *ppshared++;
1986                pshared->refcnt = 1 << (g + b);
1987                for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++) {
1988                    if ((*cptr & basemask) == (common | bits)) {
1989                        pmap->red[*cptr].fShared = TRUE;
1990                        pmap->red[*cptr].co.shco.red = pshared;
1991                    }
1992                }
1993                GetNextBitsOrBreak(bits, rmask, base);
1994            }
1995        }
1996        else {
1997            pshared = *ppshared++;
1998            pshared->refcnt = 1 << (g + b);
1999            for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++) {
2000                if ((*cptr & basemask) == common) {
2001                    pmap->red[*cptr].fShared = TRUE;
2002                    pmap->red[*cptr].co.shco.red = pshared;
2003                }
2004            }
2005        }
2006        basemask = ~(rmask | bmask);
2007        common = *pptr & basemask;
2008        if (gmask) {
2009            bits = 0;
2010            base = lowbit(gmask);
2011            while (1) {
2012                pshared = *ppshared++;
2013                pshared->refcnt = 1 << (r + b);
2014                for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++) {
2015                    if ((*cptr & basemask) == (common | bits)) {
2016                        pmap->red[*cptr].co.shco.green = pshared;
2017                    }
2018                }
2019                GetNextBitsOrBreak(bits, gmask, base);
2020            }
2021        }
2022        else {
2023            pshared = *ppshared++;
2024            pshared->refcnt = 1 << (g + b);
2025            for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++) {
2026                if ((*cptr & basemask) == common) {
2027                    pmap->red[*cptr].co.shco.green = pshared;
2028                }
2029            }
2030        }
2031        basemask = ~(rmask | gmask);
2032        common = *pptr & basemask;
2033        if (bmask) {
2034            bits = 0;
2035            base = lowbit(bmask);
2036            while (1) {
2037                pshared = *ppshared++;
2038                pshared->refcnt = 1 << (r + g);
2039                for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++) {
2040                    if ((*cptr & basemask) == (common | bits)) {
2041                        pmap->red[*cptr].co.shco.blue = pshared;
2042                    }
2043                }
2044                GetNextBitsOrBreak(bits, bmask, base);
2045            }
2046        }
2047        else {
2048            pshared = *ppshared++;
2049            pshared->refcnt = 1 << (g + b);
2050            for (cptr = ppixFirst, z = npixClientNew; --z >= 0; cptr++) {
2051                if ((*cptr & basemask) == common) {
2052                    pmap->red[*cptr].co.shco.blue = pshared;
2053                }
2054            }
2055        }
2056    }
2057    free(psharedList);
2058    return TRUE;
2059}
2060
2061/** FreeColors
2062 * Free colors and/or cells (probably slow for large numbers)
2063 */
2064int
2065FreeColors(ColormapPtr pmap, int client, int count, Pixel * pixels, Pixel mask)
2066{
2067    int rval, result, class;
2068    Pixel rmask;
2069
2070    class = pmap->class;
2071    if (pmap->flags & AllAllocated)
2072        return BadAccess;
2073    if ((class | DynamicClass) == DirectColor) {
2074        rmask = mask & RGBMASK(pmap->pVisual);
2075        result = FreeCo(pmap, client, REDMAP, count, pixels,
2076                        mask & pmap->pVisual->redMask);
2077        /* If any of the three calls fails, we must report that, if more
2078         * than one fails, it's ok that we report the last one */
2079        rval = FreeCo(pmap, client, GREENMAP, count, pixels,
2080                      mask & pmap->pVisual->greenMask);
2081        if (rval != Success)
2082            result = rval;
2083        rval = FreeCo(pmap, client, BLUEMAP, count, pixels,
2084                      mask & pmap->pVisual->blueMask);
2085        if (rval != Success)
2086            result = rval;
2087    }
2088    else {
2089        rmask = mask & ((((Pixel) 1) << pmap->pVisual->nplanes) - 1);
2090        result = FreeCo(pmap, client, PSEUDOMAP, count, pixels, rmask);
2091    }
2092    if ((mask != rmask) && count) {
2093        clients[client]->errorValue = *pixels | mask;
2094        result = BadValue;
2095    }
2096    /* XXX should worry about removing any RT_CMAPENTRY resource */
2097    return result;
2098}
2099
2100/**
2101 * Helper for FreeColors -- frees all combinations of *newpixels and mask bits
2102 * which the client has allocated in channel colormap cells of pmap.
2103 * doesn't change newpixels if it doesn't need to
2104 *
2105 *  \param pmap   which colormap head
2106 *  \param color  which sub-map, eg, RED, BLUE, PSEUDO
2107 *  \param npixIn number of pixels passed in
2108 *  \param ppixIn number of base pixels
2109 *  \param mask   mask client gave us
2110 */
2111static int
2112FreeCo(ColormapPtr pmap, int client, int color, int npixIn, Pixel * ppixIn,
2113       Pixel mask)
2114{
2115    Pixel *ppixClient, pixTest;
2116    int npixClient, npixNew, npix;
2117    Pixel bits, base, cmask, rgbbad;
2118    Pixel *pptr, *cptr;
2119    int n, zapped;
2120    int errVal = Success;
2121    int offset, numents;
2122
2123    if (npixIn == 0)
2124        return errVal;
2125    bits = 0;
2126    zapped = 0;
2127    base = lowbit(mask);
2128
2129    switch (color) {
2130    case REDMAP:
2131        cmask = pmap->pVisual->redMask;
2132        rgbbad = ~RGBMASK(pmap->pVisual);
2133        offset = pmap->pVisual->offsetRed;
2134        numents = (cmask >> offset) + 1;
2135        ppixClient = pmap->clientPixelsRed[client];
2136        npixClient = pmap->numPixelsRed[client];
2137        break;
2138    case GREENMAP:
2139        cmask = pmap->pVisual->greenMask;
2140        rgbbad = ~RGBMASK(pmap->pVisual);
2141        offset = pmap->pVisual->offsetGreen;
2142        numents = (cmask >> offset) + 1;
2143        ppixClient = pmap->clientPixelsGreen[client];
2144        npixClient = pmap->numPixelsGreen[client];
2145        break;
2146    case BLUEMAP:
2147        cmask = pmap->pVisual->blueMask;
2148        rgbbad = ~RGBMASK(pmap->pVisual);
2149        offset = pmap->pVisual->offsetBlue;
2150        numents = (cmask >> offset) + 1;
2151        ppixClient = pmap->clientPixelsBlue[client];
2152        npixClient = pmap->numPixelsBlue[client];
2153        break;
2154    default:        /* so compiler can see that everything gets initialized */
2155    case PSEUDOMAP:
2156        cmask = ~((Pixel) 0);
2157        rgbbad = 0;
2158        offset = 0;
2159        numents = pmap->pVisual->ColormapEntries;
2160        ppixClient = pmap->clientPixelsRed[client];
2161        npixClient = pmap->numPixelsRed[client];
2162        break;
2163    }
2164
2165    /* zap all pixels which match */
2166    while (1) {
2167        /* go through pixel list */
2168        for (pptr = ppixIn, n = npixIn; --n >= 0; pptr++) {
2169            pixTest = ((*pptr | bits) & cmask) >> offset;
2170            if ((pixTest >= numents) || (*pptr & rgbbad)) {
2171                clients[client]->errorValue = *pptr | bits;
2172                errVal = BadValue;
2173                continue;
2174            }
2175
2176            /* find match in client list */
2177            for (cptr = ppixClient, npix = npixClient;
2178                 --npix >= 0 && *cptr != pixTest; cptr++);
2179
2180            if (npix >= 0) {
2181                if (pmap->class & DynamicClass) {
2182                    FreeCell(pmap, pixTest, color);
2183                }
2184                *cptr = ~((Pixel) 0);
2185                zapped++;
2186            }
2187            else
2188                errVal = BadAccess;
2189        }
2190        /* generate next bits value */
2191        GetNextBitsOrBreak(bits, mask, base);
2192    }
2193
2194    /* delete freed pixels from client pixel list */
2195    if (zapped) {
2196        npixNew = npixClient - zapped;
2197        if (npixNew) {
2198            /* Since the list can only get smaller, we can do a copy in
2199             * place and then realloc to a smaller size */
2200            pptr = cptr = ppixClient;
2201
2202            /* If we have all the new pixels, we don't have to examine the
2203             * rest of the old ones */
2204            for (npix = 0; npix < npixNew; cptr++) {
2205                if (*cptr != ~((Pixel) 0)) {
2206                    *pptr++ = *cptr;
2207                    npix++;
2208                }
2209            }
2210            pptr = reallocarray(ppixClient, npixNew, sizeof(Pixel));
2211            if (pptr)
2212                ppixClient = pptr;
2213            npixClient = npixNew;
2214        }
2215        else {
2216            npixClient = 0;
2217            free(ppixClient);
2218            ppixClient = (Pixel *) NULL;
2219        }
2220        switch (color) {
2221        case PSEUDOMAP:
2222        case REDMAP:
2223            pmap->clientPixelsRed[client] = ppixClient;
2224            pmap->numPixelsRed[client] = npixClient;
2225            break;
2226        case GREENMAP:
2227            pmap->clientPixelsGreen[client] = ppixClient;
2228            pmap->numPixelsGreen[client] = npixClient;
2229            break;
2230        case BLUEMAP:
2231            pmap->clientPixelsBlue[client] = ppixClient;
2232            pmap->numPixelsBlue[client] = npixClient;
2233            break;
2234        }
2235    }
2236    return errVal;
2237}
2238
2239/* Redefine color values */
2240int
2241StoreColors(ColormapPtr pmap, int count, xColorItem * defs, ClientPtr client)
2242{
2243    Pixel pix;
2244    xColorItem *pdef;
2245    EntryPtr pent, pentT, pentLast;
2246    VisualPtr pVisual;
2247    SHAREDCOLOR *pred, *pgreen, *pblue;
2248    int n, ChgRed, ChgGreen, ChgBlue, idef;
2249    int class, errVal = Success;
2250    int ok;
2251
2252    class = pmap->class;
2253    if (!(class & DynamicClass) && !(pmap->flags & BeingCreated)) {
2254        return BadAccess;
2255    }
2256    pVisual = pmap->pVisual;
2257
2258    idef = 0;
2259    if ((class | DynamicClass) == DirectColor) {
2260        int numred, numgreen, numblue;
2261        Pixel rgbbad;
2262
2263        numred = NUMRED(pVisual);
2264        numgreen = NUMGREEN(pVisual);
2265        numblue = NUMBLUE(pVisual);
2266        rgbbad = ~RGBMASK(pVisual);
2267        for (pdef = defs, n = 0; n < count; pdef++, n++) {
2268            ok = TRUE;
2269            (*pmap->pScreen->ResolveColor)
2270                (&pdef->red, &pdef->green, &pdef->blue, pmap->pVisual);
2271
2272            if (pdef->pixel & rgbbad) {
2273                errVal = BadValue;
2274                client->errorValue = pdef->pixel;
2275                continue;
2276            }
2277            pix = (pdef->pixel & pVisual->redMask) >> pVisual->offsetRed;
2278            if (pix >= numred) {
2279                errVal = BadValue;
2280                ok = FALSE;
2281            }
2282            else if (pmap->red[pix].refcnt != AllocPrivate) {
2283                errVal = BadAccess;
2284                ok = FALSE;
2285            }
2286            else if (pdef->flags & DoRed) {
2287                pmap->red[pix].co.local.red = pdef->red;
2288            }
2289            else {
2290                pdef->red = pmap->red[pix].co.local.red;
2291            }
2292
2293            pix = (pdef->pixel & pVisual->greenMask) >> pVisual->offsetGreen;
2294            if (pix >= numgreen) {
2295                errVal = BadValue;
2296                ok = FALSE;
2297            }
2298            else if (pmap->green[pix].refcnt != AllocPrivate) {
2299                errVal = BadAccess;
2300                ok = FALSE;
2301            }
2302            else if (pdef->flags & DoGreen) {
2303                pmap->green[pix].co.local.green = pdef->green;
2304            }
2305            else {
2306                pdef->green = pmap->green[pix].co.local.green;
2307            }
2308
2309            pix = (pdef->pixel & pVisual->blueMask) >> pVisual->offsetBlue;
2310            if (pix >= numblue) {
2311                errVal = BadValue;
2312                ok = FALSE;
2313            }
2314            else if (pmap->blue[pix].refcnt != AllocPrivate) {
2315                errVal = BadAccess;
2316                ok = FALSE;
2317            }
2318            else if (pdef->flags & DoBlue) {
2319                pmap->blue[pix].co.local.blue = pdef->blue;
2320            }
2321            else {
2322                pdef->blue = pmap->blue[pix].co.local.blue;
2323            }
2324            /* If this is an o.k. entry, then it gets added to the list
2325             * to be sent to the hardware.  If not, skip it.  Once we've
2326             * skipped one, we have to copy all the others.
2327             */
2328            if (ok) {
2329                if (idef != n)
2330                    defs[idef] = defs[n];
2331                idef++;
2332            }
2333            else
2334                client->errorValue = pdef->pixel;
2335        }
2336    }
2337    else {
2338        for (pdef = defs, n = 0; n < count; pdef++, n++) {
2339
2340            ok = TRUE;
2341            if (pdef->pixel >= pVisual->ColormapEntries) {
2342                client->errorValue = pdef->pixel;
2343                errVal = BadValue;
2344                ok = FALSE;
2345            }
2346            else if (pmap->red[pdef->pixel].refcnt != AllocPrivate) {
2347                errVal = BadAccess;
2348                ok = FALSE;
2349            }
2350
2351            /* If this is an o.k. entry, then it gets added to the list
2352             * to be sent to the hardware.  If not, skip it.  Once we've
2353             * skipped one, we have to copy all the others.
2354             */
2355            if (ok) {
2356                if (idef != n)
2357                    defs[idef] = defs[n];
2358                idef++;
2359            }
2360            else
2361                continue;
2362
2363            (*pmap->pScreen->ResolveColor)
2364                (&pdef->red, &pdef->green, &pdef->blue, pmap->pVisual);
2365
2366            pent = &pmap->red[pdef->pixel];
2367
2368            if (pdef->flags & DoRed) {
2369                if (pent->fShared) {
2370                    pent->co.shco.red->color = pdef->red;
2371                    if (pent->co.shco.red->refcnt > 1)
2372                        ok = FALSE;
2373                }
2374                else
2375                    pent->co.local.red = pdef->red;
2376            }
2377            else {
2378                if (pent->fShared)
2379                    pdef->red = pent->co.shco.red->color;
2380                else
2381                    pdef->red = pent->co.local.red;
2382            }
2383            if (pdef->flags & DoGreen) {
2384                if (pent->fShared) {
2385                    pent->co.shco.green->color = pdef->green;
2386                    if (pent->co.shco.green->refcnt > 1)
2387                        ok = FALSE;
2388                }
2389                else
2390                    pent->co.local.green = pdef->green;
2391            }
2392            else {
2393                if (pent->fShared)
2394                    pdef->green = pent->co.shco.green->color;
2395                else
2396                    pdef->green = pent->co.local.green;
2397            }
2398            if (pdef->flags & DoBlue) {
2399                if (pent->fShared) {
2400                    pent->co.shco.blue->color = pdef->blue;
2401                    if (pent->co.shco.blue->refcnt > 1)
2402                        ok = FALSE;
2403                }
2404                else
2405                    pent->co.local.blue = pdef->blue;
2406            }
2407            else {
2408                if (pent->fShared)
2409                    pdef->blue = pent->co.shco.blue->color;
2410                else
2411                    pdef->blue = pent->co.local.blue;
2412            }
2413
2414            if (!ok) {
2415                /* have to run through the colormap and change anybody who
2416                 * shares this value */
2417                pred = pent->co.shco.red;
2418                pgreen = pent->co.shco.green;
2419                pblue = pent->co.shco.blue;
2420                ChgRed = pdef->flags & DoRed;
2421                ChgGreen = pdef->flags & DoGreen;
2422                ChgBlue = pdef->flags & DoBlue;
2423                pentLast = pmap->red + pVisual->ColormapEntries;
2424
2425                for (pentT = pmap->red; pentT < pentLast; pentT++) {
2426                    if (pentT->fShared && (pentT != pent)) {
2427                        xColorItem defChg;
2428
2429                        /* There are, alas, devices in this world too dumb
2430                         * to read their own hardware colormaps.  Sick, but
2431                         * true.  So we're going to be really nice and load
2432                         * the xColorItem with the proper value for all the
2433                         * fields.  We will only set the flags for those
2434                         * fields that actually change.  Smart devices can
2435                         * arrange to change only those fields.  Dumb devices
2436                         * can rest assured that we have provided for them,
2437                         * and can change all three fields */
2438
2439                        defChg.flags = 0;
2440                        if (ChgRed && pentT->co.shco.red == pred) {
2441                            defChg.flags |= DoRed;
2442                        }
2443                        if (ChgGreen && pentT->co.shco.green == pgreen) {
2444                            defChg.flags |= DoGreen;
2445                        }
2446                        if (ChgBlue && pentT->co.shco.blue == pblue) {
2447                            defChg.flags |= DoBlue;
2448                        }
2449                        if (defChg.flags != 0) {
2450                            defChg.pixel = pentT - pmap->red;
2451                            defChg.red = pentT->co.shco.red->color;
2452                            defChg.green = pentT->co.shco.green->color;
2453                            defChg.blue = pentT->co.shco.blue->color;
2454                            (*pmap->pScreen->StoreColors) (pmap, 1, &defChg);
2455                        }
2456                    }
2457                }
2458
2459            }
2460        }
2461    }
2462    /* Note that we use idef, the count of acceptable entries, and not
2463     * count, the count of proposed entries */
2464    if (idef != 0)
2465        (*pmap->pScreen->StoreColors) (pmap, idef, defs);
2466    return errVal;
2467}
2468
2469int
2470IsMapInstalled(Colormap map, WindowPtr pWin)
2471{
2472    Colormap *pmaps;
2473    int imap, nummaps, found;
2474
2475    pmaps = xallocarray(pWin->drawable.pScreen->maxInstalledCmaps,
2476                        sizeof(Colormap));
2477    if (!pmaps)
2478        return FALSE;
2479    nummaps = (*pWin->drawable.pScreen->ListInstalledColormaps)
2480        (pWin->drawable.pScreen, pmaps);
2481    found = FALSE;
2482    for (imap = 0; imap < nummaps; imap++) {
2483        if (pmaps[imap] == map) {
2484            found = TRUE;
2485            break;
2486        }
2487    }
2488    free(pmaps);
2489    return found;
2490}
2491
2492struct colormap_lookup_data {
2493    ScreenPtr pScreen;
2494    VisualPtr visuals;
2495};
2496
2497static void
2498_colormap_find_resource(void *value, XID id, void *cdata)
2499{
2500    struct colormap_lookup_data *cmap_data = cdata;
2501    VisualPtr visuals = cmap_data->visuals;
2502    ScreenPtr pScreen = cmap_data->pScreen;
2503    ColormapPtr cmap = value;
2504    int j;
2505
2506    if (pScreen != cmap->pScreen)
2507        return;
2508
2509    j = cmap->pVisual - pScreen->visuals;
2510    cmap->pVisual = &visuals[j];
2511}
2512
2513/* something has realloced the visuals, instead of breaking
2514   ABI fix it up here - glx and composite did this wrong */
2515Bool
2516ResizeVisualArray(ScreenPtr pScreen, int new_visual_count, DepthPtr depth)
2517{
2518    struct colormap_lookup_data cdata;
2519    int numVisuals;
2520    VisualPtr visuals;
2521    XID *vids, vid;
2522    int first_new_vid, first_new_visual, i;
2523
2524    first_new_vid = depth->numVids;
2525    first_new_visual = pScreen->numVisuals;
2526
2527    vids = reallocarray(depth->vids, depth->numVids + new_visual_count,
2528                        sizeof(XID));
2529    if (!vids)
2530        return FALSE;
2531
2532    /* its realloced now no going back if we fail the next one */
2533    depth->vids = vids;
2534
2535    numVisuals = pScreen->numVisuals + new_visual_count;
2536    visuals = reallocarray(pScreen->visuals, numVisuals, sizeof(VisualRec));
2537    if (!visuals) {
2538        return FALSE;
2539    }
2540
2541    cdata.visuals = visuals;
2542    cdata.pScreen = pScreen;
2543    FindClientResourcesByType(serverClient, RT_COLORMAP,
2544                              _colormap_find_resource, &cdata);
2545
2546    pScreen->visuals = visuals;
2547
2548    for (i = 0; i < new_visual_count; i++) {
2549        vid = FakeClientID(0);
2550        pScreen->visuals[first_new_visual + i].vid = vid;
2551        vids[first_new_vid + i] = vid;
2552    }
2553
2554    depth->numVids += new_visual_count;
2555    pScreen->numVisuals += new_visual_count;
2556
2557    return TRUE;
2558}
2559