-/*
- * Author: Donna Converse, MIT X Consortium
- */
-
-#include <X11/Xlib.h>
-#include <X11/Xatom.h>
-#include <X11/Xutil.h>
-#include <X11/Xmu/StdCmap.h>
-#include <stdio.h>
-
-#define lowbit(x) ((x) & (~(x) + 1))
-
-/*
- * Prototypes
- */
-static void best_allocation(XVisualInfo*, unsigned long*, unsigned long*,
- unsigned long*);
-static int default_allocation(XVisualInfo*, unsigned long*,
- unsigned long*, unsigned long*);
-static void gray_allocation(int, unsigned long*, unsigned long*,
- unsigned long*);
-static int icbrt(int);
-static int icbrt_with_bits(int, int);
-static int icbrt_with_guess(int, int);
-
-/* To determine the best allocation of reds, greens, and blues in a
- * standard colormap, use XmuGetColormapAllocation.
- * vinfo specifies visual information for a chosen visual
- * property specifies one of the standard colormap property names
- * red_max returns maximum red value
- * green_max returns maximum green value
- * blue_max returns maximum blue value
- *
- * XmuGetColormapAllocation returns 0 on failure, non-zero on success.
- * It is assumed that the visual is appropriate for the colormap property.
- */
-
-Status
-XmuGetColormapAllocation(XVisualInfo *vinfo, Atom property,
- unsigned long *red_max,
- unsigned long *green_max,
- unsigned long *blue_max)
-{
- Status status = 1;
-
- if (vinfo->colormap_size <= 2)
- return 0;
-
- switch (property)
- {
- case XA_RGB_DEFAULT_MAP:
- status = default_allocation(vinfo, red_max, green_max, blue_max);
- break;
- case XA_RGB_BEST_MAP:
- best_allocation(vinfo, red_max, green_max, blue_max);
- break;
- case XA_RGB_GRAY_MAP:
- gray_allocation(vinfo->colormap_size, red_max, green_max, blue_max);
- break;
- case XA_RGB_RED_MAP:
- *red_max = vinfo->colormap_size - 1;
- *green_max = *blue_max = 0;
- break;
- case XA_RGB_GREEN_MAP:
- *green_max = vinfo->colormap_size - 1;
- *red_max = *blue_max = 0;
- break;
- case XA_RGB_BLUE_MAP:
- *blue_max = vinfo->colormap_size - 1;
- *red_max = *green_max = 0;
- break;
- default:
- status = 0;
- }
- return status;
-}
-
-/****************************************************************************/
-/* Determine the appropriate color allocations of a gray scale.
- *
- * Keith Packard, MIT X Consortium
- */
-
-static void
-gray_allocation(int n, unsigned long *red_max, unsigned long *green_max,
- unsigned long *blue_max)
-{
- *red_max = (n * 30) / 100;
- *green_max = (n * 59) / 100;
- *blue_max = (n * 11) / 100;
- *green_max += ((n - 1) - (*red_max + *green_max + *blue_max));
-}
-
-/****************************************************************************/
-/* Determine an appropriate color allocation for the RGB_DEFAULT_MAP.
- * If a map has less than a minimum number of definable entries, we do not
- * produce an allocation for an RGB_DEFAULT_MAP.
- *
- * For 16 planes, the default colormap will have 27 each RGB; for 12 planes,
- * 12 each. For 8 planes, let n = the number of colormap entries, which may
- * be 256 or 254. Then, maximum red value = floor(cube_root(n - 125)) - 1.
- * Maximum green and maximum blue values are identical to maximum red.
- * This leaves at least 125 cells which clients can allocate.
- *
- * Return 0 if an allocation has been determined, non-zero otherwise.
- */
-
-static int
-default_allocation(XVisualInfo *vinfo, unsigned long *red,
- unsigned long *green, unsigned long *blue)
-{
- int ngrays; /* number of gray cells */
-
- switch (vinfo->c_class)
- {
- case PseudoColor:
-
- if (vinfo->colormap_size > 65000)
- /* intended for displays with 16 planes */
- *red = *green = *blue = (unsigned long) 27;
- else if (vinfo->colormap_size > 4000)
- /* intended for displays with 12 planes */
- *red = *green = *blue = (unsigned long) 12;
- else if (vinfo->colormap_size < 250)
- return 0;
- else
- /* intended for displays with 8 planes */
- *red = *green = *blue = (unsigned long)
- (icbrt(vinfo->colormap_size - 125) - 1);
- break;
-
- case DirectColor:
-
- if (vinfo->colormap_size < 10)
- return 0;
- *red = *green = *blue = vinfo->colormap_size / 2 - 1;
- break;
-
- case TrueColor:
-
- *red = vinfo->red_mask / lowbit(vinfo->red_mask);
- *green = vinfo->green_mask / lowbit(vinfo->green_mask);
- *blue = vinfo->blue_mask / lowbit(vinfo->blue_mask);
- break;
-
- case GrayScale:
-
- if (vinfo->colormap_size > 65000)
- ngrays = 4096;
- else if (vinfo->colormap_size > 4000)
- ngrays = 512;
- else if (vinfo->colormap_size < 250)
- return 0;
- else
- ngrays = 12;
- gray_allocation(ngrays, red, green, blue);
- break;
-
- default:
- return 0;
- }
- return 1;
-}
-
-/****************************************************************************/
-/* Determine an appropriate color allocation for the RGB_BEST_MAP.
- *
- * For a DirectColor or TrueColor visual, the allocation is determined
- * by the red_mask, green_mask, and blue_mask members of the visual info.
- *
- * Otherwise, if the colormap size is an integral power of 2, determine
- * the allocation according to the number of bits given to each color,
- * with green getting more than red, and red more than blue, if there
- * are to be inequities in the distribution. If the colormap size is
- * not an integral power of 2, let n = the number of colormap entries.
- * Then maximum red value = floor(cube_root(n)) - 1;
- * maximum blue value = floor(cube_root(n)) - 1;
- * maximum green value = n / ((# red values) * (# blue values)) - 1;
- * Which, on a GPX, allows for 252 entries in the best map, out of 254
- * defineable colormap entries.
- */
-
-static void
-best_allocation(XVisualInfo *vinfo, unsigned long *red, unsigned long *green,
- unsigned long *blue)
-{
-
- if (vinfo->c_class == DirectColor || vinfo->c_class == TrueColor)
- {
- *red = vinfo->red_mask;
- while ((*red & 01) == 0)
- *red >>= 1;
- *green = vinfo->green_mask;
- while ((*green & 01) == 0)
- *green >>=1;
- *blue = vinfo->blue_mask;
- while ((*blue & 01) == 0)
- *blue >>= 1;
- }
- else
- {
- register int bits, n;
-
- /* Determine n such that n is the least integral power of 2 which is
- * greater than or equal to the number of entries in the colormap.
- */
- n = 1;
- bits = 0;
- while (vinfo->colormap_size > n)
- {
- n = n << 1;
- bits++;
- }
-
- /* If the number of entries in the colormap is a power of 2, determine
- * the allocation by "dealing" the bits, first to green, then red, then
- * blue. If not, find the maximum integral red, green, and blue values
- * which, when multiplied together, do not exceed the number of
-
- * colormap entries.
- */
- if (n == vinfo->colormap_size)
- {
- register int r, g, b;
- b = bits / 3;
- g = b + ((bits % 3) ? 1 : 0);
- r = b + (((bits % 3) == 2) ? 1 : 0);
- *red = 1 << r;
- *green = 1 << g;
- *blue = 1 << b;
- }
- else
- {
- *red = icbrt_with_bits(vinfo->colormap_size, bits);
- *blue = *red;
- *green = (vinfo->colormap_size / ((*red) * (*blue)));
- }
- (*red)--;
- (*green)--;
- (*blue)--;
- }
- return;
-}
-
-/*
- * integer cube roots by Newton's method
- *
- * Stephen Gildea, MIT X Consortium, July 1991
- */
-
-static int
-icbrt(int a)
-{
- register int bits = 0;
- register unsigned n = a;
-
- while (n)
- {
- bits++;
- n >>= 1;
- }
- return icbrt_with_bits(a, bits);
-}
-
-
-static int
-icbrt_with_bits(int a, int bits)
- /* bits - log 2 of a */
-{
- return icbrt_with_guess(a, a>>2*bits/3);
-}
-
-#ifdef _X_ROOT_STATS
-int icbrt_loopcount;
-#endif
-
-/* Newton's Method: x_n+1 = x_n - ( f(x_n) / f'(x_n) ) */
-
-/* for cube roots, x^3 - a = 0, x_new = x - 1/3 (x - a/x^2) */
-
-/*
- * Quick and dirty cube roots. Nothing fancy here, just Newton's method.
- * Only works for positive integers (since that's all we need).
- * We actually return floor(cbrt(a)) because that's what we need here, too.
- */
-
-static int
-icbrt_with_guess(int a, int guess)
-{
- register int delta;
-
-#ifdef _X_ROOT_STATS
- icbrt_loopcount = 0;
-#endif
- if (a <= 0)
- return 0;
- if (guess < 1)
- guess = 1;
-
- do {
-#ifdef _X_ROOT_STATS
- icbrt_loopcount++;
-#endif
- delta = (guess - a/(guess*guess))/3;
-#ifdef DEBUG
- printf("pass %d: guess=%d, delta=%d\n", icbrt_loopcount, guess, delta);
-#endif
- guess -= delta;
- } while (delta != 0);
-
- if (guess*guess*guess > a)
- guess--;
-
- return guess;
-}
-
-
-/* $Xorg: StdCmap.c,v 1.4 2001/02/09 02:03:53 xorgcvs Exp $ */
-
-/*
-
-Copyright 1989, 1998 The Open Group
-
-Permission to use, copy, modify, distribute, and sell this software and its
-documentation for any purpose is hereby granted without fee, provided that
-the above copyright notice appear in all copies and that both that
-copyright notice and this permission notice appear in supporting
-documentation.
-
-The above copyright notice and this permission notice shall be included in
-all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
-AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
-CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-
-Except as contained in this notice, the name of The Open Group shall not be
-used in advertising or otherwise to promote the sale, use or other dealings
-in this Software without prior written authorization from The Open Group.
-
-*/
-/* $XFree86: xc/lib/Xmu/StdCmap.c,v 1.6 2001/12/14 19:55:48 dawes Exp $ */
-
-/*
- * Author: Donna Converse, MIT X Consortium
- */
-
-#include <stdio.h>
-#include <X11/Xlib.h>
-#include <X11/Xatom.h>
-#include <X11/Xutil.h>
-#include <X11/Xmu/StdCmap.h>
-
-#define lowbit(x) ((x) & (~(x) + 1))
-
-/*
- * Prototypes
- */
-/* argument restrictions */
-static Status valid_args(XVisualInfo*, unsigned long, unsigned long,
- unsigned long, Atom);
-
-/*
- * To create any one standard colormap, use XmuStandardColormap().
- *
- * Create a standard colormap for the given screen, visualid, and visual
- * depth, with the given red, green, and blue maximum values, with the
- * given standard property name. Return a pointer to an XStandardColormap
- * structure which describes the newly created colormap, upon success.
- * Upon failure, return NULL.
- *
- * XmuStandardColormap() calls XmuCreateColormap() to create the map.
- *
- * Resources created by this function are not made permanent; that is the
- * caller's responsibility.
- */
-
-XStandardColormap *
-XmuStandardColormap(Display *dpy, int screen, VisualID visualid,
- unsigned int depth, Atom property, Colormap cmap,
- unsigned long red_max, unsigned long green_max,
- unsigned long blue_max)
- /*
- * dpy - specifies X server connection
- * screen - specifies display screen
- * visualid - identifies the visual type
- * depth - identifies the visual type
- * property - a standard colormap property
- * cmap - specifies colormap ID or None
- * red_max, green_max, blue_max - allocations
- */
-{
- XStandardColormap *stdcmap;
- Status status;
- XVisualInfo vinfo_template, *vinfo;
- long vinfo_mask;
- int n;
-
- /* Match the required visual information to an actual visual */
- vinfo_template.visualid = visualid;
- vinfo_template.screen = screen;
- vinfo_template.depth = depth;
- vinfo_mask = VisualIDMask | VisualScreenMask | VisualDepthMask;
- if ((vinfo = XGetVisualInfo(dpy, vinfo_mask, &vinfo_template, &n)) == NULL)
- return 0;
-
- /* Check the validity of the combination of visual characteristics,
- * allocation, and colormap property. Create an XStandardColormap
- * structure.
- */
-
- if (! valid_args(vinfo, red_max, green_max, blue_max, property)
- || ((stdcmap = XAllocStandardColormap()) == NULL)) {
- XFree((char *) vinfo);
- return 0;
- }
-
- /* Fill in the XStandardColormap structure */
-
- if (cmap == DefaultColormap(dpy, screen)) {
- /* Allocating out of the default map, cannot use XFreeColormap() */
- Window win = XCreateWindow(dpy, RootWindow(dpy, screen), 1, 1, 1, 1,
- 0, 0, InputOnly, vinfo->visual,
- (unsigned long) 0,
- (XSetWindowAttributes *)NULL);
- stdcmap->killid = (XID) XCreatePixmap(dpy, win, 1, 1, depth);
- XDestroyWindow(dpy, win);
- stdcmap->colormap = cmap;
- } else {
- stdcmap->killid = ReleaseByFreeingColormap;
- stdcmap->colormap = XCreateColormap(dpy, RootWindow(dpy, screen),
- vinfo->visual, AllocNone);
- }
- stdcmap->red_max = red_max;
- stdcmap->green_max = green_max;
- stdcmap->blue_max = blue_max;
- if (property == XA_RGB_GRAY_MAP)
- stdcmap->red_mult = stdcmap->green_mult = stdcmap->blue_mult = 1;
- else if (vinfo->c_class == TrueColor || vinfo->c_class == DirectColor) {
- stdcmap->red_mult = lowbit(vinfo->red_mask);
- stdcmap->green_mult = lowbit(vinfo->green_mask);
- stdcmap->blue_mult = lowbit(vinfo->blue_mask);
- } else {
- stdcmap->red_mult = (red_max > 0)
- ? (green_max + 1) * (blue_max + 1) : 0;
- stdcmap->green_mult = (green_max > 0) ? blue_max + 1 : 0;
- stdcmap->blue_mult = (blue_max > 0) ? 1 : 0;
- }
- stdcmap->base_pixel = 0; /* base pixel may change */
- stdcmap->visualid = vinfo->visualid;
-
- /* Make the colormap */
-
- status = XmuCreateColormap(dpy, stdcmap);
-
- /* Clean up */
-
- XFree((char *) vinfo);
- if (!status) {
-
- /* Free the colormap or the pixmap, if we created one */
- if (stdcmap->killid == ReleaseByFreeingColormap)
- XFreeColormap(dpy, stdcmap->colormap);
- else if (stdcmap->killid != None)
- XFreePixmap(dpy, stdcmap->killid);
-
- XFree((char *) stdcmap);
- return (XStandardColormap *) NULL;
- }
- return stdcmap;
-}
-
-/****************************************************************************/
-static Status
-valid_args(XVisualInfo *vinfo, unsigned long red_max, unsigned long green_max,
- unsigned long blue_max, Atom property)
- /*
- * vinfo - specifies visual
- * red_max, green_max, blue_max - specifies alloc
- * property - specifies property name
- */
-{
- unsigned long ncolors; /* number of colors requested */
-
- /* Determine that the number of colors requested is <= map size */
-
- if ((vinfo->c_class == DirectColor) || (vinfo->c_class == TrueColor)) {
- unsigned long mask;
-
- mask = vinfo->red_mask;
- while (!(mask & 1))
- mask >>= 1;
- if (red_max > mask)
- return 0;
- mask = vinfo->green_mask;
- while (!(mask & 1))
- mask >>= 1;
- if (green_max > mask)
- return 0;
- mask = vinfo->blue_mask;
- while (!(mask & 1))
- mask >>= 1;
- if (blue_max > mask)
- return 0;
- } else if (property == XA_RGB_GRAY_MAP) {
- ncolors = red_max + green_max + blue_max + 1;
- if (ncolors > vinfo->colormap_size)
- return 0;
- } else {
- ncolors = (red_max + 1) * (green_max + 1) * (blue_max + 1);
- if (ncolors > vinfo->colormap_size)
- return 0;
- }
-
- /* Determine that the allocation and visual make sense for the property */
-
- switch (property)
- {
- case XA_RGB_DEFAULT_MAP:
- if (red_max == 0 || green_max == 0 || blue_max == 0)
- return 0;
- break;
- case XA_RGB_RED_MAP:
- if (red_max == 0)
- return 0;
- break;
- case XA_RGB_GREEN_MAP:
- if (green_max == 0)
- return 0;
- break;
- case XA_RGB_BLUE_MAP:
- if (blue_max == 0)
- return 0;
- break;
- case XA_RGB_BEST_MAP:
- if (red_max == 0 || green_max == 0 || blue_max == 0)
- return 0;
- break;
- case XA_RGB_GRAY_MAP:
- if (red_max == 0 || blue_max == 0 || green_max == 0)
- return 0;
- break;
- default:
- return 0;
- }
- return 1;
-}
-
-
-/* $Xorg: CrCmap.c,v 1.4 2001/02/09 02:03:51 xorgcvs Exp $ */
-
-/*
-
-Copyright 1989, 1998 The Open Group
-
-Permission to use, copy, modify, distribute, and sell this software and its
-documentation for any purpose is hereby granted without fee, provided that
-the above copyright notice appear in all copies and that both that
-copyright notice and this permission notice appear in supporting
-documentation.
-
-The above copyright notice and this permission notice shall be included in
-all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
-AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
-CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-
-Except as contained in this notice, the name of The Open Group shall not be
-used in advertising or otherwise to promote the sale, use or other dealings
-in this Software without prior written authorization from The Open Group.
-
-*/
-/* $XFree86: xc/lib/Xmu/CrCmap.c,v 3.7 2001/12/14 19:55:36 dawes Exp $ */
-
-/*
- * Author: Donna Converse, MIT X Consortium
- */
-
-/*
- * CreateCmap.c - given a standard colormap description, make the map.
- */
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <X11/Xlib.h>
-#include <X11/Xutil.h>
-#include <X11/Xmu/StdCmap.h>
-
-/*
- * Prototypes
- */
-/* allocate entire map Read Only */
-static int ROmap(Display*, Colormap, unsigned long[], int, int);
-
-/* allocate a cell, prefer Read Only */
-static Status ROorRWcell(Display*, Colormap, unsigned long[], int,
- XColor*, unsigned long);
-
-/* allocate a cell Read Write */
-static Status RWcell(Display*, Colormap, XColor*, XColor*, unsigned long*);
-
-/* for quicksort */
-static int compare(_Xconst void*, _Xconst void*);
-
-/* find contiguous sequence of cells */
-static Status contiguous(unsigned long[], int, int, unsigned long, int*, int*);
-
-/* frees resources before quitting */
-static void free_cells(Display*, Colormap, unsigned long[], int, int);
-
-/* create a map in a RO visual type */
-static Status readonly_map(Display*, XVisualInfo*, XStandardColormap*);
-
-/* create a map in a RW visual type */
-static Status readwrite_map(Display*, XVisualInfo*, XStandardColormap*);
-
-#define lowbit(x) ((x) & (~(x) + 1))
-#define TRUEMATCH(mult,max,mask) \
- (colormap->max * colormap->mult <= vinfo->mask && \
- lowbit(vinfo->mask) == colormap->mult)
-
-/*
- * To create any one colormap which is described by an XStandardColormap
- * structure, use XmuCreateColormap().
- *
- * Return 0 on failure, non-zero on success.
- * Resources created by this function are not made permanent.
- * No argument error checking is provided. Use at your own risk.
- *
- * All colormaps are created with read only allocations, with the exception
- * of read only allocations of colors in the default map or otherwise
- * which fail to return the expected pixel value, and these are individually
- * defined as read/write allocations. This is done so that all the cells
- * defined in the default map are contiguous, for use in image processing.
- * This typically happens with White and Black in the default map.
- *
- * Colormaps of static visuals are considered to be successfully created if
- * the map of the static visual matches the definition given in the
- * standard colormap structure.
- */
-
-Status
-XmuCreateColormap(Display *dpy, XStandardColormap *colormap)
- /* dpy - specifies the connection under which the map is created
- * colormap - specifies the map to be created, and returns, particularly
- * if the map is created as a subset of the default colormap
- * of the screen, the base_pixel of the map.
- */
-{
- XVisualInfo vinfo_template; /* template visual information */
- XVisualInfo *vinfo; /* matching visual information */
- XVisualInfo *vpointer; /* for freeing the entire list */
- long vinfo_mask; /* specifies the visual mask value */
- int n; /* number of matching visuals */
- int status;
-
- vinfo_template.visualid = colormap->visualid;
- vinfo_mask = VisualIDMask;
- if ((vinfo = XGetVisualInfo(dpy, vinfo_mask, &vinfo_template, &n)) == NULL)
- return 0;
-
- /* A visual id may be valid on multiple screens. Also, there may
- * be multiple visuals with identical visual ids at different depths.
- * If the colormap is the Default Colormap, use the Default Visual.
- * Otherwise, arbitrarily, use the deepest visual.
- */
- vpointer = vinfo;
- if (n > 1)
- {
- register int i;
- register int screen_number;
- Bool def_cmap;
-
- def_cmap = False;
- for (screen_number = ScreenCount(dpy); --screen_number >= 0; )
- if (colormap->colormap == DefaultColormap(dpy, screen_number)) {
- def_cmap = True;
- break;
- }
-
- if (def_cmap) {
- for (i=0; i < n; i++, vinfo++) {
- if (vinfo->visual == DefaultVisual(dpy, screen_number))
- break;
- }
- } else {
- int maxdepth = 0;
- XVisualInfo *v = NULL;
-
- for (i=0; i < n; i++, vinfo++)
- if (vinfo->depth > maxdepth) {
- maxdepth = vinfo->depth;
- v = vinfo;
- }
- vinfo = v;
- }
- }
-
- if (vinfo->c_class == PseudoColor || vinfo->c_class == DirectColor ||
- vinfo->c_class == GrayScale)
- status = readwrite_map(dpy, vinfo, colormap);
- else if (vinfo->c_class == TrueColor)
- status = TRUEMATCH(red_mult, red_max, red_mask) &&
- TRUEMATCH(green_mult, green_max, green_mask) &&
- TRUEMATCH(blue_mult, blue_max, blue_mask);
- else
- status = readonly_map(dpy, vinfo, colormap);
-
- XFree((char *) vpointer);
- return status;
-}
-
-/****************************************************************************/
-static Status
-readwrite_map(Display *dpy, XVisualInfo *vinfo, XStandardColormap *colormap)
-{
- register unsigned long i, n; /* index counters */
- unsigned long ncolors; /* number of colors to be defined */
- int npixels; /* number of pixels allocated R/W */
- int first_index; /* first index of pixels to use */
- int remainder; /* first index of remainder */
- XColor color; /* the definition of a color */
- unsigned long *pixels; /* array of colormap pixels */
- unsigned long delta;
-
-
- /* Determine ncolors, the number of colors to be defined.
- * Insure that 1 < ncolors <= the colormap size.
- */
- if (vinfo->c_class == DirectColor) {
- ncolors = colormap->red_max;
- if (colormap->green_max > ncolors)
- ncolors = colormap->green_max;
- if (colormap->blue_max > ncolors)
- ncolors = colormap->blue_max;
- ncolors++;
- delta = lowbit(vinfo->red_mask) +
- lowbit(vinfo->green_mask) +
- lowbit(vinfo->blue_mask);
- } else {
- ncolors = colormap->red_max * colormap->red_mult +
- colormap->green_max * colormap->green_mult +
- colormap->blue_max * colormap->blue_mult + 1;
- delta = 1;
- }
- if (ncolors <= 1 || (int) ncolors > vinfo->colormap_size) return 0;
-
- /* Allocate Read/Write as much of the colormap as we can possibly get.
- * Then insure that the pixels we were allocated are given in
- * monotonically increasing order, using a quicksort. Next, insure
- * that our allocation includes a subset of contiguous pixels at least
- * as long as the number of colors to be defined. Now we know that
- * these conditions are met:
- * 1) There are no free cells in the colormap.
- * 2) We have a contiguous sequence of pixels, monotonically
- * increasing, of length >= the number of colors requested.
- *
- * One cell at a time, we will free, compute the next color value,
- * then allocate read only. This takes a long time.
- * This is done to insure that cells are allocated read only in the
- * contiguous order which we prefer. If the server has a choice of
- * cells to grant to an allocation request, the server may give us any
- * cell, so that is why we do these slow gymnastics.
- */
-
- if ((pixels = (unsigned long *) calloc((unsigned) vinfo->colormap_size,
- sizeof(unsigned long))) == NULL)
- return 0;
-
- if ((npixels = ROmap(dpy, colormap->colormap, pixels,
- vinfo->colormap_size, ncolors)) == 0) {
- free((char *) pixels);
- return 0;
- }
-
- qsort((char *) pixels, npixels, sizeof(unsigned long), compare);
-
- if (!contiguous(pixels, npixels, ncolors, delta, &first_index, &remainder))
- {
- /* can't find enough contiguous cells, give up */
- XFreeColors(dpy, colormap->colormap, pixels, npixels,
- (unsigned long) 0);
- free((char *) pixels);
- return 0;
- }
- colormap->base_pixel = pixels[first_index];
-
- /* construct a gray map */
- if (colormap->red_mult == 1 && colormap->green_mult == 1 &&
- colormap->blue_mult == 1)
- for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
- {
- color.pixel = n;
- color.blue = color.green = color.red =
- (unsigned short) ((i * 65535) / (colormap->red_max +
- colormap->green_max +
- colormap->blue_max));
-
- if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
- first_index + i))
- return 0;
- }
-
- /* construct a red ramp map */
- else if (colormap->green_max == 0 && colormap->blue_max == 0)
- for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
- {
- color.pixel = n;
- color.red = (unsigned short) ((i * 65535) / colormap->red_max);
- color.green = color.blue = 0;
-
- if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
- first_index + i))
- return 0;
- }
-
- /* construct a green ramp map */
- else if (colormap->red_max == 0 && colormap->blue_max == 0)
- for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
- {
- color.pixel = n;
- color.green = (unsigned short) ((i * 65535) / colormap->green_max);
- color.red = color.blue = 0;
-
- if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
- first_index + i))
- return 0;
- }
-
- /* construct a blue ramp map */
- else if (colormap->red_max == 0 && colormap->green_max == 0)
- for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
- {
- color.pixel = n;
- color.blue = (unsigned short) ((i * 65535) / colormap->blue_max);
- color.red = color.green = 0;
-
- if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
- first_index + i))
- return 0;
- }
-
- /* construct a standard red green blue cube map */
- else
- {
-#define calc(max,mult) (((n / colormap->mult) % \
- (colormap->max + 1)) * 65535) / colormap->max
-
- for (n=0, i=0; i < ncolors; i++, n += delta)
- {
- color.pixel = n + colormap->base_pixel;
- color.red = calc(red_max, red_mult);
- color.green = calc(green_max, green_mult);
- color.blue = calc(blue_max, blue_mult);
- if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
- first_index + i))
- return 0;
- }
-#undef calc
- }
- /* We have a read-only map defined. Now free unused cells,
- * first those occuring before the contiguous sequence begins,
- * then any following the contiguous sequence.
- */
-
- if (first_index)
- XFreeColors(dpy, colormap->colormap, pixels, first_index,
- (unsigned long) 0);
- if (remainder)
- XFreeColors(dpy, colormap->colormap,
- &(pixels[first_index + ncolors]), remainder,
- (unsigned long) 0);
-
- free((char *) pixels);
- return 1;
-}
-
-
-/****************************************************************************/
-static int
-ROmap(Display *dpy, Colormap cmap, unsigned long pixels[], int m, int n)
- /*
- * dpy - the X server connection
- * cmap - specifies colormap ID
- * pixels - returns pixel allocations
- * m - specifies colormap size
- * n - specifies number of colors
- */
-{
- register int p;
-
- /* first try to allocate the entire colormap */
- if (XAllocColorCells(dpy, cmap, 1, (unsigned long *) NULL,
- (unsigned) 0, pixels, (unsigned) m))
- return m;
-
- /* Allocate all available cells in the colormap, using a binary
- * algorithm to discover how many cells we can allocate in the colormap.
- */
- m--;
- while (n <= m) {
- p = n + ((m - n + 1) / 2);
- if (XAllocColorCells(dpy, cmap, 1, (unsigned long *) NULL,
- (unsigned) 0, pixels, (unsigned) p)) {
- if (p == m)
- return p;
- else {
- XFreeColors(dpy, cmap, pixels, p, (unsigned long) 0);
- n = p;
- }
- }
- else
- m = p - 1;
- }
- return 0;
-}
-
-
-/****************************************************************************/
-static Status
-contiguous(unsigned long pixels[], int npixels, int ncolors,
- unsigned long delta, int *first, int *rem)
- /* pixels - specifies allocated pixels
- * npixels - specifies count of alloc'd pixels
- * ncolors - specifies needed sequence length
- * delta - between pixels
- * first - returns first index of sequence
- * rem - returns first index after sequence, or 0, if none follow
- */
-{
- register int i = 1; /* walking index into the pixel array */
- register int count = 1; /* length of sequence discovered so far */
-
- *first = 0;
- if (npixels == ncolors) {
- *rem = 0;
- return 1;
- }
- *rem = npixels - 1;
- while (count < ncolors && ncolors - count <= *rem)
- {
- if (pixels[i-1] + delta == pixels[i])
- count++;
- else {
- count = 1;
- *first = i;
- }
- i++;
- (*rem)--;
- }
- if (count != ncolors)
- return 0;
- return 1;
-}
-
-
-/****************************************************************************/
-static Status
-ROorRWcell(Display *dpy, Colormap cmap, unsigned long pixels[],
- int npixels, XColor *color, unsigned long p)
-{
- unsigned long pixel;
- XColor request;
-
- /* Free the read/write allocation of one cell in the colormap.
- * Request a read only allocation of one cell in the colormap.
- * If the read only allocation cannot be granted, give up, because
- * there must be no free cells in the colormap.
- * If the read only allocation is granted, but gives us a cell which
- * is not the one that we just freed, it is probably the case that
- * we are trying allocate White or Black or some other color which
- * already has a read-only allocation in the map. So we try to
- * allocate the previously freed cell with a read/write allocation,
- * because we want contiguous cells for image processing algorithms.
- */
-
- pixel = color->pixel;
- request.red = color->red;
- request.green = color->green;
- request.blue = color->blue;
-
- XFreeColors(dpy, cmap, &pixel, 1, (unsigned long) 0);
- if (! XAllocColor(dpy, cmap, color)
- || (color->pixel != pixel &&
- (!RWcell(dpy, cmap, color, &request, &pixel))))
- {
- free_cells(dpy, cmap, pixels, npixels, (int)p);
- return 0;
- }
- return 1;
-}
-
-
-/****************************************************************************/
-static void
-free_cells(Display *dpy, Colormap cmap, unsigned long pixels[],
- int npixels, int p)
- /*
- * pixels - to be freed
- * npixels - original number allocated
- */
-{
- /* One of the npixels allocated has already been freed.
- * p is the index of the freed pixel.
- * First free the pixels preceeding p, and there are p of them;
- * then free the pixels following p, there are npixels - p - 1 of them.
- */
- XFreeColors(dpy, cmap, pixels, p, (unsigned long) 0);
- XFreeColors(dpy, cmap, &(pixels[p+1]), npixels - p - 1, (unsigned long) 0);
- free((char *) pixels);
-}
-
-
-/****************************************************************************/
-static Status
-RWcell(Display *dpy, Colormap cmap, XColor *color, XColor *request,
- unsigned long *pixel)
-{
- unsigned long n = *pixel;
-
- XFreeColors(dpy, cmap, &(color->pixel), 1, (unsigned long)0);
- if (! XAllocColorCells(dpy, cmap, (Bool) 0, (unsigned long *) NULL,
- (unsigned) 0, pixel, (unsigned) 1))
- return 0;
- if (*pixel != n)
- {
- XFreeColors(dpy, cmap, pixel, 1, (unsigned long) 0);
- return 0;
- }
- color->pixel = *pixel;
- color->flags = DoRed | DoGreen | DoBlue;
- color->red = request->red;
- color->green = request->green;
- color->blue = request->blue;
- XStoreColors(dpy, cmap, color, 1);
- return 1;
-}
-
-
-/****************************************************************************/
-static int
-compare(_Xconst void *e1, _Xconst void *e2)
-{
- return ((int)(*(long *)e1 - *(long *)e2));
-}
-
-
-/****************************************************************************/
-static Status
-readonly_map(Display *dpy, XVisualInfo *vinfo, XStandardColormap *colormap)
-{
- int i, last_pixel;
- XColor color;
-
- last_pixel = (colormap->red_max + 1) * (colormap->green_max + 1) *
- (colormap->blue_max + 1) + colormap->base_pixel - 1;
-
- for(i=colormap->base_pixel; i <= last_pixel; i++) {
-
- color.pixel = (unsigned long) i;
- color.red = (unsigned short)
- (((i/colormap->red_mult) * 65535) / colormap->red_max);
-
- if (vinfo->c_class == StaticColor) {
- color.green = (unsigned short)
- ((((i/colormap->green_mult) % (colormap->green_max + 1)) *
- 65535) / colormap->green_max);
- color.blue = (unsigned short)
- (((i%colormap->green_mult) * 65535) / colormap->blue_max);
- }
- else /* vinfo->c_class == GrayScale, old style allocation XXX */
- color.green = color.blue = color.red;
-
- XAllocColor(dpy, colormap->colormap, &color);
- if (color.pixel != (unsigned long) i)
- return 0;