wrlib/CrCmap.c

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