src/CrCmap.c

   1 /*
   2
   3 Copyright 1989, 1998  The Open Group
   4
   5 Permission to use, copy, modify, distribute, and sell this software and its
   6 documentation for any purpose is hereby granted without fee, provided that
   7 the above copyright notice appear in all copies and that both that
   8 copyright notice and this permission notice appear in supporting
   9 documentation.
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  18 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  19 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  20
  21 Except as contained in this notice, the name of The Open Group shall not be
  22 used in advertising or otherwise to promote the sale, use or other dealings
  23 in this Software without prior written authorization from The Open Group.
  24
  25 */
  26
  27 /*
  28  * Author:  Donna Converse, MIT X Consortium
  29  */
  30
  31 /*
  32  * CreateCmap.c - given a standard colormap description, make the map.
  33  */
  34
  35 #ifdef HAVE_CONFIG_H
  36 #include <config.h>
  37 #endif
  38 #include <stdio.h>
  39 #include <stdlib.h>
  40 #include <X11/Xlib.h>
  41 #include <X11/Xutil.h>
  42 #include <X11/Xmu/StdCmap.h>
  43
  44 /*
  45  * Prototypes
  46  */
  47 /* allocate entire map Read Only */
  48 static int ROmap(Display*, Colormap, unsigned long[], int, int);
  49
  50 /* allocate a cell, prefer Read Only */
  51 static Status ROorRWcell(Display*, Colormap, unsigned long[], int,
  52                          XColor*, unsigned long);
  53
  54 /* allocate a cell Read Write */
  55 static Status RWcell(Display*, Colormap, XColor*, XColor*, unsigned long*);
  56
  57 /* for quicksort */
  58 static int compare(_Xconst void*, _Xconst void*);
  59
  60 /* find contiguous sequence of cells */
  61 static Status contiguous(unsigned long[], int, int, unsigned long, int*, int*);
  62
  63 /* frees resources before quitting */
  64 static void free_cells(Display*, Colormap, unsigned long[], int, int);
  65
  66 /* create a map in a RO visual type */
  67 static Status readonly_map(Display*, XVisualInfo*, XStandardColormap*);
  68
  69 /* create a map in a RW visual type */
  70 static Status readwrite_map(Display*, XVisualInfo*, XStandardColormap*);
  71
  72 #define lowbit(x) ((x) & (~(x) + 1))
  73 #define TRUEMATCH(mult,max,mask) \
  74     (colormap->max * colormap->mult <= vinfo->mask && \
  75      lowbit(vinfo->mask) == colormap->mult)
  76
  77 /*
  78  * To create any one colormap which is described by an XStandardColormap
  79  * structure, use XmuCreateColormap().
  80  *
  81  * Return 0 on failure, non-zero on success.
  82  * Resources created by this function are not made permanent.
  83  * No argument error checking is provided.  Use at your own risk.
  84  *
  85  * All colormaps are created with read only allocations, with the exception
  86  * of read only allocations of colors in the default map or otherwise
  87  * which fail to return the expected pixel value, and these are individually
  88  * defined as read/write allocations.  This is done so that all the cells
  89  * defined in the default map are contiguous, for use in image processing.
  90  * This typically happens with White and Black in the default map.
  91  *
  92  * Colormaps of static visuals are considered to be successfully created if
  93  * the map of the static visual matches the definition given in the
  94  * standard colormap structure.
  95  */
  96
  97 Status
  98 XmuCreateColormap(Display *dpy, XStandardColormap *colormap)
  99      /* dpy      - specifies the connection under which the map is created
 100       * colormap - specifies the map to be created, and returns, particularly
 101       *            if the map is created as a subset of the default colormap
 102       *            of the screen, the base_pixel of the map.
 103                                          */
 104 {
 105     XVisualInfo         vinfo_template; /* template visual information */
 106     XVisualInfo         *vinfo;         /* matching visual information */
 107     XVisualInfo         *vpointer;      /* for freeing the entire list */
 108     long                vinfo_mask;     /* specifies the visual mask value */
 109     int                 n;              /* number of matching visuals */
 110     int                 status;
 111
 112     vinfo_template.visualid = colormap->visualid;
 113     vinfo_mask = VisualIDMask;
 114     if ((vinfo = XGetVisualInfo(dpy, vinfo_mask, &vinfo_template, &n)) == NULL)
 115         return 0;
 116
 117     /* A visual id may be valid on multiple screens.  Also, there may
 118      * be multiple visuals with identical visual ids at different depths.
 119      * If the colormap is the Default Colormap, use the Default Visual.
 120      * Otherwise, arbitrarily, use the deepest visual.
 121      */
 122     vpointer = vinfo;
 123     if (n > 1)
 124     {
 125         register int    i;
 126         register int    screen_number;
 127         Bool            def_cmap;
 128
 129         def_cmap = False;
 130         for (screen_number = ScreenCount(dpy); --screen_number >= 0; )
 131             if (colormap->colormap == DefaultColormap(dpy, screen_number)) {
 132                 def_cmap = True;
 133                 break;
 134             }
 135
 136         if (def_cmap) {
 137             for (i=0; i < n; i++, vinfo++) {
 138                 if (vinfo->visual == DefaultVisual(dpy, screen_number))
 139                         break;
 140             }
 141         } else {
 142             int                 maxdepth = 0;
 143             XVisualInfo         *v = NULL;
 144
 145             for (i=0; i < n; i++, vinfo++)
 146                 if (vinfo->depth > maxdepth) {
 147                     maxdepth = vinfo->depth;
 148                     v = vinfo;
 149                 }
 150             vinfo = v;
 151         }
 152     }
 153
 154     if (vinfo->class == PseudoColor || vinfo->class == DirectColor ||
 155         vinfo->class == GrayScale)
 156         status = readwrite_map(dpy, vinfo, colormap);
 157     else if (vinfo->class == TrueColor)
 158         status = TRUEMATCH(red_mult, red_max, red_mask) &&
 159                  TRUEMATCH(green_mult, green_max, green_mask) &&
 160                  TRUEMATCH(blue_mult, blue_max, blue_mask);
 161     else
 162         status = readonly_map(dpy, vinfo, colormap);
 163
 164     XFree((char *) vpointer);
 165     return status;
 166 }
 167
 168 /****************************************************************************/
 169 static Status
 170 readwrite_map(Display *dpy, XVisualInfo *vinfo, XStandardColormap *colormap)
 171 {
 172     register unsigned long i, n;        /* index counters */
 173     unsigned long       ncolors;        /* number of colors to be defined */
 174     int                 npixels;        /* number of pixels allocated R/W */
 175     int                 first_index;    /* first index of pixels to use */
 176     int                 remainder;      /* first index of remainder */
 177     XColor              color;          /* the definition of a color */
 178     unsigned long       *pixels;        /* array of colormap pixels */
 179     unsigned long       delta;
 180
 181
 182     /* Determine ncolors, the number of colors to be defined.
 183      * Insure that 1 < ncolors <= the colormap size.
 184      */
 185     if (vinfo->class == DirectColor) {
 186         ncolors = colormap->red_max;
 187         if (colormap->green_max > ncolors)
 188             ncolors = colormap->green_max;
 189         if (colormap->blue_max > ncolors)
 190             ncolors = colormap->blue_max;
 191         ncolors++;
 192         delta = lowbit(vinfo->red_mask) +
 193                 lowbit(vinfo->green_mask) +
 194                 lowbit(vinfo->blue_mask);
 195     } else {
 196         ncolors = colormap->red_max * colormap->red_mult +
 197                   colormap->green_max * colormap->green_mult +
 198                   colormap->blue_max * colormap->blue_mult + 1;
 199         delta = 1;
 200     }
 201     if (ncolors <= 1 || (int) ncolors > vinfo->colormap_size)   return 0;
 202
 203     /* Allocate Read/Write as much of the colormap as we can possibly get.
 204      * Then insure that the pixels we were allocated are given in
 205      * monotonically increasing order, using a quicksort.  Next, insure
 206      * that our allocation includes a subset of contiguous pixels at least
 207      * as long as the number of colors to be defined.  Now we know that
 208      * these conditions are met:
 209      *  1) There are no free cells in the colormap.
 210      *  2) We have a contiguous sequence of pixels, monotonically
 211      *     increasing, of length >= the number of colors requested.
 212      *
 213      * One cell at a time, we will free, compute the next color value,
 214      * then allocate read only.  This takes a long time.
 215      * This is done to insure that cells are allocated read only in the
 216      * contiguous order which we prefer.  If the server has a choice of
 217      * cells to grant to an allocation request, the server may give us any
 218      * cell, so that is why we do these slow gymnastics.
 219      */
 220
 221     if ((pixels = (unsigned long *) calloc((unsigned) vinfo->colormap_size,
 222                                       sizeof(unsigned long))) == NULL)
 223         return 0;
 224
 225     if ((npixels = ROmap(dpy, colormap->colormap, pixels,
 226                            vinfo->colormap_size, ncolors)) == 0) {
 227         free((char *) pixels);
 228         return 0;
 229     }
 230
 231     qsort((char *) pixels, npixels, sizeof(unsigned long), compare);
 232
 233     if (!contiguous(pixels, npixels, ncolors, delta, &first_index, &remainder))
 234     {
 235         /* can't find enough contiguous cells, give up */
 236         XFreeColors(dpy, colormap->colormap, pixels, npixels,
 237                     (unsigned long) 0);
 238         free((char *) pixels);
 239         return 0;
 240     }
 241     colormap->base_pixel = pixels[first_index];
 242
 243     /* construct a gray map */
 244     if (colormap->red_mult == 1 && colormap->green_mult == 1 &&
 245         colormap->blue_mult == 1)
 246         for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
 247         {
 248             color.pixel = n;
 249             color.blue = color.green = color.red =
 250                 (unsigned short) ((i * 65535) / (colormap->red_max +
 251                                                  colormap->green_max +
 252                                                  colormap->blue_max));
 253
 254             if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
 255                              first_index + i))
 256                 return 0;
 257         }
 258
 259     /* construct a red ramp map */
 260     else if (colormap->green_max == 0 && colormap->blue_max == 0)
 261         for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
 262         {
 263             color.pixel = n;
 264             color.red = (unsigned short) ((i * 65535) / colormap->red_max);
 265             color.green = color.blue = 0;
 266
 267             if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
 268                              first_index + i))
 269                 return 0;
 270         }
 271
 272     /* construct a green ramp map */
 273     else if (colormap->red_max == 0 && colormap->blue_max == 0)
 274         for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
 275         {
 276             color.pixel = n;
 277             color.green = (unsigned short) ((i * 65535) / colormap->green_max);
 278             color.red = color.blue = 0;
 279
 280             if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
 281                              first_index + i))
 282                 return 0;
 283         }
 284
 285     /* construct a blue ramp map */
 286     else if (colormap->red_max == 0 && colormap->green_max == 0)
 287         for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
 288         {
 289             color.pixel = n;
 290             color.blue = (unsigned short) ((i * 65535) / colormap->blue_max);
 291             color.red = color.green = 0;
 292
 293             if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
 294                              first_index + i))
 295                 return 0;
 296         }
 297
 298     /* construct a standard red green blue cube map */
 299     else
 300     {
 301 #define calc(max,mult) (((n / colormap->mult) % \
 302                          (colormap->max + 1)) * 65535) / colormap->max
 303
 304         for (n=0, i=0; i < ncolors; i++, n += delta)
 305         {
 306             color.pixel = n + colormap->base_pixel;
 307             color.red = calc(red_max, red_mult);
 308             color.green = calc(green_max, green_mult);
 309             color.blue = calc(blue_max, blue_mult);
 310             if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
 311                              first_index + i))
 312                 return 0;
 313         }
 314 #undef calc
 315     }
 316     /* We have a read-only map defined.  Now free unused cells,
 317      * first those occuring before the contiguous sequence begins,
 318      * then any following the contiguous sequence.
 319      */
 320
 321     if (first_index)
 322         XFreeColors(dpy, colormap->colormap, pixels, first_index,
 323                     (unsigned long) 0);
 324     if (remainder)
 325         XFreeColors(dpy, colormap->colormap,
 326                     &(pixels[first_index + ncolors]), remainder,
 327                     (unsigned long) 0);
 328
 329     free((char *) pixels);
 330     return 1;
 331 }
 332
 333
 334 /****************************************************************************/
 335 static int
 336 ROmap(Display *dpy, Colormap cmap, unsigned long pixels[], int m, int n)
 337      /*
 338       * dpy     - the X server connection
 339       * cmap    - specifies colormap ID
 340       * pixels  - returns pixel allocations
 341       * m       - specifies colormap size
 342       * n       - specifies number of colors
 343       */
 344 {
 345     register int        p;
 346
 347     /* first try to allocate the entire colormap */
 348     if (XAllocColorCells(dpy, cmap, 1, (unsigned long *) NULL,
 349                          (unsigned) 0, pixels, (unsigned) m))
 350         return m;
 351
 352     /* Allocate all available cells in the colormap, using a binary
 353      * algorithm to discover how many cells we can allocate in the colormap.
 354      */
 355     m--;
 356     while (n <= m) {
 357         p = n + ((m - n + 1) / 2);
 358         if (XAllocColorCells(dpy, cmap, 1, (unsigned long *) NULL,
 359                              (unsigned) 0, pixels, (unsigned) p)) {
 360             if (p == m)
 361                 return p;
 362             else {
 363                 XFreeColors(dpy, cmap, pixels, p, (unsigned long) 0);
 364                 n = p;
 365             }
 366         }
 367         else
 368             m = p - 1;
 369     }
 370     return 0;
 371 }
 372
 373
 374 /****************************************************************************/
 375 static Status
 376 contiguous(unsigned long pixels[], int npixels, int ncolors,
 377            unsigned long delta, int *first, int *rem)
 378      /* pixels  - specifies allocated pixels
 379       * npixels - specifies count of alloc'd pixels
 380       * ncolors - specifies needed sequence length
 381       * delta   - between pixels
 382       * first   - returns first index of sequence
 383       * rem     - returns first index after sequence, or 0, if none follow
 384       */
 385 {
 386     register int i = 1;         /* walking index into the pixel array */
 387     register int count = 1;     /* length of sequence discovered so far */
 388
 389     *first = 0;
 390     if (npixels == ncolors) {
 391         *rem = 0;
 392         return 1;
 393     }
 394     *rem = npixels - 1;
 395     while (count < ncolors && ncolors - count <= *rem)
 396     {
 397         if (pixels[i-1] + delta == pixels[i])
 398             count++;
 399         else {
 400             count = 1;
 401             *first = i;
 402         }
 403         i++;
 404         (*rem)--;
 405     }
 406     if (count != ncolors)
 407         return 0;
 408     return 1;
 409 }
 410
 411
 412 /****************************************************************************/
 413 static Status
 414 ROorRWcell(Display *dpy, Colormap cmap, unsigned long pixels[],
 415            int npixels, XColor *color, unsigned long p)
 416 {
 417     unsigned long       pixel;
 418     XColor              request;
 419
 420     /* Free the read/write allocation of one cell in the colormap.
 421      * Request a read only allocation of one cell in the colormap.
 422      * If the read only allocation cannot be granted, give up, because
 423      * there must be no free cells in the colormap.
 424      * If the read only allocation is granted, but gives us a cell which
 425      * is not the one that we just freed, it is probably the case that
 426      * we are trying allocate White or Black or some other color which
 427      * already has a read-only allocation in the map.  So we try to
 428      * allocate the previously freed cell with a read/write allocation,
 429      * because we want contiguous cells for image processing algorithms.
 430      */
 431
 432     pixel = color->pixel;
 433     request.red = color->red;
 434     request.green = color->green;
 435     request.blue = color->blue;
 436
 437     XFreeColors(dpy, cmap, &pixel, 1, (unsigned long) 0);
 438     if (! XAllocColor(dpy, cmap, color)
 439         || (color->pixel != pixel &&
 440             (!RWcell(dpy, cmap, color, &request, &pixel))))
 441     {
 442         free_cells(dpy, cmap, pixels, npixels, (int)p);
 443         return 0;
 444     }
 445     return 1;
 446 }
 447
 448
 449 /****************************************************************************/
 450 static void
 451 free_cells(Display *dpy, Colormap cmap, unsigned long pixels[],
 452            int npixels, int p)
 453      /*
 454       * pixels  - to be freed
 455       * npixels - original number allocated
 456       */
 457 {
 458     /* One of the npixels allocated has already been freed.
 459      * p is the index of the freed pixel.
 460      * First free the pixels preceeding p, and there are p of them;
 461      * then free the pixels following p, there are npixels - p - 1 of them.
 462      */
 463     XFreeColors(dpy, cmap, pixels, p, (unsigned long) 0);
 464     XFreeColors(dpy, cmap, &(pixels[p+1]), npixels - p - 1, (unsigned long) 0);
 465     free((char *) pixels);
 466 }
 467
 468
 469 /****************************************************************************/
 470 static Status
 471 RWcell(Display *dpy, Colormap cmap, XColor *color, XColor *request,
 472        unsigned long *pixel)
 473 {
 474     unsigned long       n = *pixel;
 475
 476     XFreeColors(dpy, cmap, &(color->pixel), 1, (unsigned long)0);
 477     if (! XAllocColorCells(dpy, cmap, (Bool) 0, (unsigned long *) NULL,
 478                            (unsigned) 0, pixel, (unsigned) 1))
 479         return 0;
 480     if (*pixel != n)
 481     {
 482         XFreeColors(dpy, cmap, pixel, 1, (unsigned long) 0);
 483         return 0;
 484     }
 485     color->pixel = *pixel;
 486     color->flags = DoRed | DoGreen | DoBlue;
 487     color->red = request->red;
 488     color->green = request->green;
 489     color->blue = request->blue;
 490     XStoreColors(dpy, cmap, color, 1);
 491     return 1;
 492 }
 493
 494
 495 /****************************************************************************/
 496 static int
 497 compare(_Xconst void *e1, _Xconst void *e2)
 498 {
 499   return ((int)(*(_Xconst long *)e1 - *(_Xconst long *)e2));
 500 }
 501
 502
 503 /****************************************************************************/
 504 static Status
 505 readonly_map(Display *dpy, XVisualInfo *vinfo, XStandardColormap *colormap)
 506 {
 507     int                 i, last_pixel;
 508     XColor              color;
 509
 510     last_pixel = (colormap->red_max + 1) * (colormap->green_max + 1) *
 511         (colormap->blue_max + 1) + colormap->base_pixel - 1;
 512
 513     for(i=colormap->base_pixel; i <= last_pixel; i++) {
 514
 515         color.pixel = (unsigned long) i;
 516         color.red = (unsigned short)
 517             (((i/colormap->red_mult) * 65535) / colormap->red_max);
 518
 519         if (vinfo->class == StaticColor) {
 520             color.green = (unsigned short)
 521                 ((((i/colormap->green_mult) % (colormap->green_max + 1)) *
 522                   65535) / colormap->green_max);
 523             color.blue = (unsigned short)
 524                 (((i%colormap->green_mult) * 65535) / colormap->blue_max);
 525         }
 526         else    /* vinfo->class == GrayScale, old style allocation XXX */
 527             color.green = color.blue = color.red;
 528
 529         XAllocColor(dpy, colormap->colormap, &color);
 530         if (color.pixel != (unsigned long) i)
 531             return 0;
 532     }
 533     return 1;
 534 }