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 static int ROmap();             /* allocate entire map Read Only */
  44 static Status ROorRWcell();     /* allocate a cell, prefer Read Only */
  45 static Status RWcell();         /* allocate a cell Read Write */
  46 static int compare();           /* for quicksort */
  47 static Status contiguous();     /* find contiguous sequence of cells */
  48 static void free_cells();       /* frees resources before quitting */
  49 static Status readonly_map();   /* create a map in a RO visual type */
  50 static Status readwrite_map();  /* create a map in a RW visual type */
  51
  52 #define lowbit(x) ((x) & (~(x) + 1))
  53 #define TRUEMATCH(mult,max,mask) \
  54     (colormap->max * colormap->mult <= vinfo->mask && \
  55     lowbit(vinfo->mask) == colormap->mult)
  56
  57 /*
  58  * To create any one colormap which is described by an XStandardColormap
  59  * structure, use XmuCreateColormap().
  60  *
  61  * Return 0 on failure, non-zero on success.
  62  * Resources created by this function are not made permanent.
  63  * No argument error checking is provided.  Use at your own risk.
  64  *
  65  * All colormaps are created with read only allocations, with the exception
  66  * of read only allocations of colors in the default map or otherwise
  67  * which fail to return the expected pixel value, and these are individually
  68  * defined as read/write allocations.  This is done so that all the cells
  69  * defined in the default map are contiguous, for use in image processing.
  70  * This typically happens with White and Black in the default map.
  71  *
  72  * Colormaps of static visuals are considered to be successfully created if
  73  * the map of the static visual matches the definition given in the
  74  * standard colormap structure.
  75  */
  76
  77 Status XmuCreateColormap(dpy, colormap)
  78 Display *dpy;                   /* specifies the connection under
  79                                  * which the map is created */
  80 XStandardColormap *colormap;    /* specifies the map to be created,
  81                                  * and returns, particularly if the
  82                                  * map is created as a subset of the
  83                                  * default colormap of the screen,
  84                                  * the base_pixel of the map.
  85                                  */
  86 {
  87         XVisualInfo vinfo_template;     /* template visual information */
  88         XVisualInfo *vinfo;     /* matching visual information */
  89         XVisualInfo *vpointer;  /* for freeing the entire list */
  90         long vinfo_mask;        /* specifies the visual mask value */
  91         int n;                  /* number of matching visuals */
  92         int status;
  93
  94         vinfo_template.visualid = colormap->visualid;
  95         vinfo_mask = VisualIDMask;
  96         if ((vinfo = XGetVisualInfo(dpy, vinfo_mask, &vinfo_template, &n)) == NULL)
  97                 return 0;
  98
  99         /* A visual id may be valid on multiple screens.  Also, there may
 100          * be multiple visuals with identical visual ids at different depths.
 101          * If the colormap is the Default Colormap, use the Default Visual.
 102          * Otherwise, arbitrarily, use the deepest visual.
 103          */
 104         vpointer = vinfo;
 105         if (n > 1) {
 106                 register int i;
 107                 register int screen_number;
 108                 Bool def_cmap;
 109
 110                 def_cmap = False;
 111                 for (screen_number = ScreenCount(dpy); --screen_number >= 0;)
 112                         if (colormap->colormap == DefaultColormap(dpy, screen_number)) {
 113                                 def_cmap = True;
 114                                 break;
 115                         }
 116
 117                 if (def_cmap) {
 118                         for (i = 0; i < n; i++, vinfo++) {
 119                                 if (vinfo->visual == DefaultVisual(dpy, screen_number))
 120                                         break;
 121                         }
 122                 } else {
 123                         unsigned int maxdepth = 0;
 124                         XVisualInfo *v = vinfo;
 125
 126                         for (i = 0; i < n; i++, vinfo++)
 127                                 if (vinfo->depth > maxdepth) {
 128                                         maxdepth = vinfo->depth;
 129                                         v = vinfo;
 130                                 }
 131                         vinfo = v;
 132                 }
 133         }
 134
 135         if (vinfo->class == PseudoColor || vinfo->class == DirectColor || vinfo->class == GrayScale)
 136                 status = readwrite_map(dpy, vinfo, colormap);
 137         else if (vinfo->class == TrueColor)
 138                 status = TRUEMATCH(red_mult, red_max, red_mask) &&
 139                     TRUEMATCH(green_mult, green_max, green_mask) && TRUEMATCH(blue_mult, blue_max, blue_mask);
 140         else
 141                 status = readonly_map(dpy, vinfo, colormap);
 142
 143         XFree((char *)vpointer);
 144         return status;
 145 }
 146
 147 /****************************************************************************/
 148 static Status readwrite_map(dpy, vinfo, colormap)
 149 Display *dpy;
 150 XVisualInfo *vinfo;
 151 XStandardColormap *colormap;
 152 {
 153         register unsigned long i, n;    /* index counters */
 154         int ncolors;            /* number of colors to be defined */
 155         int npixels;            /* number of pixels allocated R/W */
 156         int first_index;        /* first index of pixels to use */
 157         int remainder;          /* first index of remainder */
 158         XColor color;           /* the definition of a color */
 159         unsigned long *pixels;  /* array of colormap pixels */
 160         unsigned long delta;
 161
 162         /* Determine ncolors, the number of colors to be defined.
 163          * Insure that 1 < ncolors <= the colormap size.
 164          */
 165         if (vinfo->class == DirectColor) {
 166                 ncolors = colormap->red_max;
 167                 if (colormap->green_max > ncolors)
 168                         ncolors = colormap->green_max;
 169                 if (colormap->blue_max > ncolors)
 170                         ncolors = colormap->blue_max;
 171                 ncolors++;
 172                 delta = lowbit(vinfo->red_mask) + lowbit(vinfo->green_mask) + lowbit(vinfo->blue_mask);
 173         } else {
 174                 ncolors = colormap->red_max * colormap->red_mult +
 175                     colormap->green_max * colormap->green_mult + colormap->blue_max * colormap->blue_mult + 1;
 176                 delta = 1;
 177         }
 178         if (ncolors <= 1 || ncolors > vinfo->colormap_size)
 179                 return 0;
 180
 181         /* Allocate Read/Write as much of the colormap as we can possibly get.
 182          * Then insure that the pixels we were allocated are given in
 183          * monotonically increasing order, using a quicksort.  Next, insure
 184          * that our allocation includes a subset of contiguous pixels at least
 185          * as long as the number of colors to be defined.  Now we know that
 186          * these conditions are met:
 187          *  1) There are no free cells in the colormap.
 188          *  2) We have a contiguous sequence of pixels, monotonically
 189          *     increasing, of length >= the number of colors requested.
 190          *
 191          * One cell at a time, we will free, compute the next color value,
 192          * then allocate read only.  This takes a long time.
 193          * This is done to insure that cells are allocated read only in the
 194          * contiguous order which we prefer.  If the server has a choice of
 195          * cells to grant to an allocation request, the server may give us any
 196          * cell, so that is why we do these slow gymnastics.
 197          */
 198
 199         if ((pixels = (unsigned long *)calloc((unsigned)vinfo->colormap_size, sizeof(unsigned long))) == NULL)
 200                 return 0;
 201
 202         if ((npixels = ROmap(dpy, colormap->colormap, pixels, vinfo->colormap_size, ncolors)) == 0) {
 203                 free((char *)pixels);
 204                 return 0;
 205         }
 206
 207         qsort((char *)pixels, npixels, sizeof(unsigned long), compare);
 208
 209         if (!contiguous(pixels, npixels, ncolors, delta, &first_index, &remainder)) {
 210                 /* can't find enough contiguous cells, give up */
 211                 XFreeColors(dpy, colormap->colormap, pixels, npixels, (unsigned long)0);
 212                 free((char *)pixels);
 213                 return 0;
 214         }
 215         colormap->base_pixel = pixels[first_index];
 216
 217         /* construct a gray map */
 218         if (colormap->red_mult == 1 && colormap->green_mult == 1 && colormap->blue_mult == 1)
 219                 for (n = colormap->base_pixel, i = 0; i < ncolors; i++, n += delta) {
 220                         color.pixel = n;
 221                         color.blue = color.green = color.red =
 222                             (unsigned short)((i * 65535) / (colormap->red_max +
 223                                                             colormap->green_max + colormap->blue_max));
 224
 225                         if (!ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color, first_index + i))
 226                                 return 0;
 227                 }
 228
 229         /* construct a red ramp map */
 230         else if (colormap->green_max == 0 && colormap->blue_max == 0)
 231                 for (n = colormap->base_pixel, i = 0; i < ncolors; i++, n += delta) {
 232                         color.pixel = n;
 233                         color.red = (unsigned short)((i * 65535) / colormap->red_max);
 234                         color.green = color.blue = 0;
 235
 236                         if (!ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color, first_index + i))
 237                                 return 0;
 238                 }
 239
 240         /* construct a green ramp map */
 241         else if (colormap->red_max == 0 && colormap->blue_max == 0)
 242                 for (n = colormap->base_pixel, i = 0; i < ncolors; i++, n += delta) {
 243                         color.pixel = n;
 244                         color.green = (unsigned short)((i * 65535) / colormap->green_max);
 245                         color.red = color.blue = 0;
 246
 247                         if (!ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color, first_index + i))
 248                                 return 0;
 249                 }
 250
 251         /* construct a blue ramp map */
 252         else if (colormap->red_max == 0 && colormap->green_max == 0)
 253                 for (n = colormap->base_pixel, i = 0; i < ncolors; i++, n += delta) {
 254                         color.pixel = n;
 255                         color.blue = (unsigned short)((i * 65535) / colormap->blue_max);
 256                         color.red = color.green = 0;
 257
 258                         if (!ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color, first_index + i))
 259                                 return 0;
 260                 }
 261
 262         /* construct a standard red green blue cube map */
 263         else {
 264 #define calc(max,mult) (((n / colormap->mult) % \
 265     (colormap->max + 1)) * 65535) / colormap->max
 266
 267                 for (n = 0, i = 0; i < ncolors; i++, n += delta) {
 268                         color.pixel = n + colormap->base_pixel;
 269                         color.red = calc(red_max, red_mult);
 270                         color.green = calc(green_max, green_mult);
 271                         color.blue = calc(blue_max, blue_mult);
 272                         if (!ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color, first_index + i))
 273                                 return 0;
 274                 }
 275 #undef calc
 276         }
 277         /* We have a read-only map defined.  Now free unused cells,
 278          * first those occuring before the contiguous sequence begins,
 279          * then any following the contiguous sequence.
 280          */
 281
 282         if (first_index)
 283                 XFreeColors(dpy, colormap->colormap, pixels, first_index, (unsigned long)0);
 284         if (remainder)
 285                 XFreeColors(dpy, colormap->colormap,
 286                             &(pixels[first_index + ncolors]), remainder, (unsigned long)0);
 287
 288         free((char *)pixels);
 289         return 1;
 290 }
 291
 292 /****************************************************************************/
 293 static int ROmap(dpy, cmap, pixels, m, n)
 294 Display *dpy;                   /* the X server connection */
 295 Colormap cmap;                  /* specifies colormap ID */
 296 unsigned long pixels[];         /* returns pixel allocations */
 297 int m;                          /* specifies colormap size */
 298 int n;                          /* specifies number of colors */
 299 {
 300         register int p;
 301
 302         /* first try to allocate the entire colormap */
 303         if (XAllocColorCells(dpy, cmap, 1, (unsigned long *)NULL, (unsigned)0, pixels, (unsigned)m))
 304                 return m;
 305
 306         /* Allocate all available cells in the colormap, using a binary
 307          * algorithm to discover how many cells we can allocate in the colormap.
 308          */
 309         m--;
 310         while (n <= m) {
 311                 p = n + ((m - n + 1) / 2);
 312                 if (XAllocColorCells(dpy, cmap, 1, (unsigned long *)NULL, (unsigned)0, pixels, (unsigned)p)) {
 313                         if (p == m)
 314                                 return p;
 315                         else {
 316                                 XFreeColors(dpy, cmap, pixels, p, (unsigned long)0);
 317                                 n = p;
 318                         }
 319                 } else
 320                         m = p - 1;
 321         }
 322         return 0;
 323 }
 324
 325 /****************************************************************************/
 326 static Status contiguous(pixels, npixels, ncolors, delta, first, rem)
 327 unsigned long pixels[];         /* specifies allocated pixels */
 328 int npixels;                    /* specifies count of alloc'd pixels */
 329 int ncolors;                    /* specifies needed sequence length */
 330 unsigned long delta;            /* between pixels */
 331 int *first;                     /* returns first index of sequence */
 332 int *rem;                       /* returns first index after sequence,
 333                                  * or 0, if none follow */
 334 {
 335         register int i = 1;     /* walking index into the pixel array */
 336         register int count = 1; /* length of sequence discovered so far */
 337
 338         *first = 0;
 339         if (npixels == ncolors) {
 340                 *rem = 0;
 341                 return 1;
 342         }
 343         *rem = npixels - 1;
 344         while (count < ncolors && ncolors - count <= *rem) {
 345                 if (pixels[i - 1] + delta == pixels[i])
 346                         count++;
 347                 else {
 348                         count = 1;
 349                         *first = i;
 350                 }
 351                 i++;
 352                 (*rem)--;
 353         }
 354         if (count != ncolors)
 355                 return 0;
 356         return 1;
 357 }
 358
 359 /****************************************************************************/
 360 static Status ROorRWcell(dpy, cmap, pixels, npixels, color, p)
 361 Display *dpy;
 362 Colormap cmap;
 363 unsigned long pixels[];
 364 int npixels;
 365 XColor *color;
 366 unsigned long p;
 367 {
 368         unsigned long pixel;
 369         XColor request;
 370
 371         /* Free the read/write allocation of one cell in the colormap.
 372          * Request a read only allocation of one cell in the colormap.
 373          * If the read only allocation cannot be granted, give up, because
 374          * there must be no free cells in the colormap.
 375          * If the read only allocation is granted, but gives us a cell which
 376          * is not the one that we just freed, it is probably the case that
 377          * we are trying allocate White or Black or some other color which
 378          * already has a read-only allocation in the map.  So we try to
 379          * allocate the previously freed cell with a read/write allocation,
 380          * because we want contiguous cells for image processing algorithms.
 381          */
 382
 383         pixel = color->pixel;
 384         request.red = color->red;
 385         request.green = color->green;
 386         request.blue = color->blue;
 387
 388         XFreeColors(dpy, cmap, &pixel, 1, (unsigned long)0);
 389         if (!XAllocColor(dpy, cmap, color)
 390             || (color->pixel != pixel && (!RWcell(dpy, cmap, color, &request, &pixel)))) {
 391                 free_cells(dpy, cmap, pixels, npixels, (int)p);
 392                 return 0;
 393         }
 394         return 1;
 395 }
 396
 397 /****************************************************************************/
 398 static void free_cells(dpy, cmap, pixels, npixels, p)
 399 Display *dpy;
 400 Colormap cmap;
 401 unsigned long pixels[];         /* to be freed */
 402 int npixels;                    /* original number allocated */
 403 int p;
 404 {
 405         /* One of the npixels allocated has already been freed.
 406          * p is the index of the freed pixel.
 407          * First free the pixels preceeding p, and there are p of them;
 408          * then free the pixels following p, there are npixels - p - 1 of them.
 409          */
 410         XFreeColors(dpy, cmap, pixels, p, (unsigned long)0);
 411         XFreeColors(dpy, cmap, &(pixels[p + 1]), npixels - p - 1, (unsigned long)0);
 412         free((char *)pixels);
 413 }
 414
 415 /****************************************************************************/
 416 static Status RWcell(dpy, cmap, color, request, pixel)
 417 Display *dpy;
 418 Colormap cmap;
 419 XColor *color;
 420 XColor *request;
 421 unsigned long *pixel;
 422 {
 423         unsigned long n = *pixel;
 424
 425         XFreeColors(dpy, cmap, &(color->pixel), 1, (unsigned long)0);
 426         if (!XAllocColorCells(dpy, cmap, (Bool) 0, (unsigned long *)NULL, (unsigned)0, pixel, (unsigned)1))
 427                 return 0;
 428         if (*pixel != n) {
 429                 XFreeColors(dpy, cmap, pixel, 1, (unsigned long)0);
 430                 return 0;
 431         }
 432         color->pixel = *pixel;
 433         color->flags = DoRed | DoGreen | DoBlue;
 434         color->red = request->red;
 435         color->green = request->green;
 436         color->blue = request->blue;
 437         XStoreColors(dpy, cmap, color, 1);
 438         return 1;
 439 }
 440
 441 /****************************************************************************/
 442 static int compare(e1, e2)
 443 unsigned long *e1, *e2;
 444 {
 445         if (*e1 < *e2)
 446                 return -1;
 447         if (*e1 > *e2)
 448                 return 1;
 449         return 0;
 450 }
 451
 452 /****************************************************************************/
 453 static Status readonly_map(dpy, vinfo, colormap)
 454 Display *dpy;
 455 XVisualInfo *vinfo;
 456 XStandardColormap *colormap;
 457 {
 458         int i, last_pixel;
 459         XColor color;
 460
 461         last_pixel = (colormap->red_max + 1) * (colormap->green_max + 1) *
 462             (colormap->blue_max + 1) + colormap->base_pixel - 1;
 463
 464         for (i = colormap->base_pixel; i <= last_pixel; i++) {
 465
 466                 color.pixel = (unsigned long)i;
 467                 color.red = (unsigned short)
 468                     (((i / colormap->red_mult) * 65535) / colormap->red_max);
 469
 470                 if (vinfo->class == StaticColor) {
 471                         color.green = (unsigned short)
 472                             ((((i / colormap->green_mult) % (colormap->green_max + 1)) *
 473                               65535) / colormap->green_max);
 474                         color.blue = (unsigned short)
 475                             (((i % colormap->green_mult) * 65535) / colormap->blue_max);
 476                 } else          /* vinfo->class == GrayScale, old style allocation XXX */
 477                         color.green = color.blue = color.red;
 478
 479                 XAllocColor(dpy, colormap->colormap, &color);
 480                 if (color.pixel != (unsigned long)i)
 481                         return 0;
 482         }
 483         return 1;
 484 }