src/CmapAlloc.c

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