wrlib/CmapAlloc.c

   1 /* $XConsortium: CmapAlloc.c,v 1.9 94/04/17 20:15:52 rws Exp $ */
   2
   3 /*
   4
   5 Copyright (c) 1989, 1994  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 #include <X11/Xlib.h>
  35 #include <X11/Xatom.h>
  36 #include <X11/Xutil.h>
  37 #include <stdio.h>
  38
  39 #define lowbit(x) ((x) & (~(x) + 1))
  40
  41 static int default_allocation();
  42 static void best_allocation();
  43 static void gray_allocation();
  44 static int icbrt();
  45 static int icbrt_with_bits();
  46 static int icbrt_with_guess();
  47
  48 /* To determine the best allocation of reds, greens, and blues in a
  49  * standard colormap, use XmuGetColormapAllocation.
  50  *      vinfo           specifies visual information for a chosen visual
  51  *      property        specifies one of the standard colormap property names
  52  *      red_max         returns maximum red value
  53  *      green_max       returns maximum green value
  54  *      blue_max        returns maximum blue value
  55  *
  56  * XmuGetColormapAllocation returns 0 on failure, non-zero on success.
  57  * It is assumed that the visual is appropriate for the colormap property.
  58  */
  59
  60 Status XmuGetColormapAllocation(vinfo, property, red_max, green_max, blue_max)
  61     XVisualInfo         *vinfo;
  62     Atom                property;
  63     unsigned long       *red_max, *green_max, *blue_max;
  64 {
  65     Status      status = 1;
  66
  67     if (vinfo->colormap_size <= 2)
  68         return 0;
  69
  70     switch (property)
  71     {
  72       case XA_RGB_DEFAULT_MAP:
  73         status = default_allocation(vinfo, red_max, green_max, blue_max);
  74         break;
  75       case XA_RGB_BEST_MAP:
  76         best_allocation(vinfo, red_max, green_max, blue_max);
  77         break;
  78       case XA_RGB_GRAY_MAP:
  79         gray_allocation(vinfo->colormap_size, red_max, green_max, blue_max);
  80         break;
  81       case XA_RGB_RED_MAP:
  82         *red_max = vinfo->colormap_size - 1;
  83         *green_max = *blue_max = 0;
  84         break;
  85       case XA_RGB_GREEN_MAP:
  86         *green_max = vinfo->colormap_size - 1;
  87         *red_max = *blue_max = 0;
  88         break;
  89       case XA_RGB_BLUE_MAP:
  90         *blue_max = vinfo->colormap_size - 1;
  91         *red_max = *green_max = 0;
  92         break;
  93       default:
  94         status = 0;
  95     }
  96     return status;
  97 }
  98
  99 /****************************************************************************/
 100 /* Determine the appropriate color allocations of a gray scale.
 101  *
 102  * Keith Packard, MIT X Consortium
 103  */
 104
 105 static void gray_allocation(n, red_max, green_max, blue_max)
 106     int         n;      /* the number of cells of the gray scale */
 107     unsigned long *red_max, *green_max, *blue_max;
 108 {
 109     *red_max = (n * 30) / 100;
 110     *green_max = (n * 59) / 100;
 111     *blue_max = (n * 11) / 100;
 112     *green_max += ((n - 1) - (*red_max + *green_max + *blue_max));
 113 }
 114
 115 /****************************************************************************/
 116 /* Determine an appropriate color allocation for the RGB_DEFAULT_MAP.
 117  * If a map has less than a minimum number of definable entries, we do not
 118  * produce an allocation for an RGB_DEFAULT_MAP.
 119  *
 120  * For 16 planes, the default colormap will have 27 each RGB; for 12 planes,
 121  * 12 each.  For 8 planes, let n = the number of colormap entries, which may
 122  * be 256 or 254.  Then, maximum red value = floor(cube_root(n - 125)) - 1.
 123  * Maximum green and maximum blue values are identical to maximum red.
 124  * This leaves at least 125 cells which clients can allocate.
 125  *
 126  * Return 0 if an allocation has been determined, non-zero otherwise.
 127  */
 128
 129 static int default_allocation(vinfo, red, green, blue)
 130     XVisualInfo         *vinfo;
 131     unsigned long       *red, *green, *blue;
 132 {
 133     int                 ngrays;         /* number of gray cells */
 134
 135     switch (vinfo->class) {
 136       case PseudoColor:
 137
 138         if (vinfo->colormap_size > 65000)
 139             /* intended for displays with 16 planes */
 140             *red = *green = *blue = (unsigned long) 27;
 141         else if (vinfo->colormap_size > 4000)
 142             /* intended for displays with 12 planes */
 143             *red = *green = *blue = (unsigned long) 12;
 144         else if (vinfo->colormap_size < 250)
 145             return 0;
 146         else
 147             /* intended for displays with 8 planes */
 148             *red = *green = *blue = (unsigned long)
 149                 (icbrt(vinfo->colormap_size - 125) - 1);
 150         break;
 151
 152       case DirectColor:
 153
 154         if (vinfo->colormap_size < 10)
 155             return 0;
 156         *red = *green = *blue = vinfo->colormap_size / 2 - 1;
 157         break;
 158
 159       case TrueColor:
 160
 161         *red = vinfo->red_mask / lowbit(vinfo->red_mask);
 162         *green = vinfo->green_mask / lowbit(vinfo->green_mask);
 163         *blue = vinfo->blue_mask / lowbit(vinfo->blue_mask);
 164         break;
 165
 166       case GrayScale:
 167
 168         if (vinfo->colormap_size > 65000)
 169             ngrays = 4096;
 170         else if (vinfo->colormap_size > 4000)
 171             ngrays = 512;
 172         else if (vinfo->colormap_size < 250)
 173             return 0;
 174         else
 175             ngrays = 12;
 176         gray_allocation(ngrays, red, green, blue);
 177         break;
 178
 179       default:
 180         return 0;
 181     }
 182     return 1;
 183 }
 184
 185 /****************************************************************************/
 186 /* Determine an appropriate color allocation for the RGB_BEST_MAP.
 187  *
 188  * For a DirectColor or TrueColor visual, the allocation is determined
 189  * by the red_mask, green_mask, and blue_mask members of the visual info.
 190  *
 191  * Otherwise, if the colormap size is an integral power of 2, determine
 192  * the allocation according to the number of bits given to each color,
 193  * with green getting more than red, and red more than blue, if there
 194  * are to be inequities in the distribution.  If the colormap size is
 195  * not an integral power of 2, let n = the number of colormap entries.
 196  * Then maximum red value = floor(cube_root(n)) - 1;
 197  *      maximum blue value = floor(cube_root(n)) - 1;
 198  *      maximum green value = n / ((# red values) * (# blue values)) - 1;
 199  * Which, on a GPX, allows for 252 entries in the best map, out of 254
 200  * defineable colormap entries.
 201  */
 202
 203 static void best_allocation(vinfo, red, green, blue)
 204     XVisualInfo         *vinfo;
 205     unsigned long       *red, *green, *blue;
 206 {
 207
 208     if (vinfo->class == DirectColor ||  vinfo->class == TrueColor)
 209     {
 210         *red = vinfo->red_mask;
 211         while ((*red & 01) == 0)
 212             *red >>= 1;
 213         *green = vinfo->green_mask;
 214         while ((*green & 01) == 0)
 215             *green >>=1;
 216         *blue = vinfo->blue_mask;
 217         while ((*blue & 01) == 0)
 218             *blue >>= 1;
 219     }
 220     else
 221     {
 222         register int bits, n;
 223
 224         /* Determine n such that n is the least integral power of 2 which is
 225          * greater than or equal to the number of entries in the colormap.
 226          */
 227         n = 1;
 228         bits = 0;
 229         while (vinfo->colormap_size > n)
 230         {
 231             n = n << 1;
 232             bits++;
 233         }
 234
 235         /* If the number of entries in the colormap is a power of 2, determine
 236          * the allocation by "dealing" the bits, first to green, then red, then
 237          * blue.  If not, find the maximum integral red, green, and blue values
 238          * which, when multiplied together, do not exceed the number of
 239
 240          * colormap entries.
 241          */
 242         if (n == vinfo->colormap_size)
 243         {
 244             register int r, g, b;
 245             b = bits / 3;
 246             g = b + ((bits % 3) ? 1 : 0);
 247             r = b + (((bits % 3) == 2) ? 1 : 0);
 248             *red = 1 << r;
 249             *green = 1 << g;
 250             *blue = 1 << b;
 251         }
 252         else
 253         {
 254             *red = icbrt_with_bits(vinfo->colormap_size, bits);
 255             *blue = *red;
 256             *green = (vinfo->colormap_size / ((*red) * (*blue)));
 257         }
 258         (*red)--;
 259         (*green)--;
 260         (*blue)--;
 261     }
 262     return;
 263 }
 264
 265 /*
 266  * integer cube roots by Newton's method
 267  *
 268  * Stephen Gildea, MIT X Consortium, July 1991
 269  */
 270
 271 static int icbrt(a)             /* integer cube root */
 272     int a;
 273 {
 274     register int bits = 0;
 275     register unsigned n = a;
 276
 277     while (n)
 278     {
 279         bits++;
 280         n >>= 1;
 281     }
 282     return icbrt_with_bits(a, bits);
 283 }
 284
 285
 286 static int icbrt_with_bits(a, bits)
 287     int a;
 288     int bits;                   /* log 2 of a */
 289 {
 290     return icbrt_with_guess(a, a>>2*bits/3);
 291 }
 292
 293 #ifdef DEBUG
 294 int icbrt_loopcount;
 295 #endif
 296
 297 /* Newton's Method:  x_n+1 = x_n - ( f(x_n) / f'(x_n) ) */
 298
 299 /* for cube roots, x^3 - a = 0,  x_new = x - 1/3 (x - a/x^2) */
 300
 301 /*
 302  * Quick and dirty cube roots.  Nothing fancy here, just Newton's method.
 303  * Only works for positive integers (since that's all we need).
 304  * We actually return floor(cbrt(a)) because that's what we need here, too.
 305  */
 306
 307 static int icbrt_with_guess(a, guess)
 308     int a, guess;
 309 {
 310     register int delta;
 311
 312 #ifdef DEBUG
 313     icbrt_loopcount = 0;
 314 #endif
 315     if (a <= 0)
 316         return 0;
 317     if (guess < 1)
 318         guess = 1;
 319
 320     do {
 321 #ifdef DEBUG
 322         icbrt_loopcount++;
 323 #endif
 324         delta = (guess - a/(guess*guess))/3;
 325 #ifdef DEBUG
 326         printf("pass %d: guess=%d, delta=%d\n", icbrt_loopcount, guess, delta);
 327 #endif
 328         guess -= delta;
 329     } while (delta != 0);
 330
 331     if (guess*guess*guess > a)
 332         guess--;
 333
 334     return guess;
 335 }