home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / X / mit / lib / Xmu / CmapAlloc.c.orig < prev    next >
Encoding:
Text File  |  1991-07-19  |  8.7 KB  |  312 lines
  1. /*
  2.  * $XConsortium: CmapAlloc.c,v 1.4 91/07/19 16:36:50 gildea Exp $
  3.  * 
  4.  * Copyright 1989 by the Massachusetts Institute of Technology
  5.  *
  6.  * Permission to use, copy, modify, and distribute this software and its
  7.  * documentation for any purpose and without fee is hereby granted, provided 
  8.  * that the above copyright notice appear in all copies and that both that 
  9.  * copyright notice and this permission notice appear in supporting 
  10.  * documentation, and that the name of M.I.T. not be used in advertising
  11.  * or publicity pertaining to distribution of the software without specific, 
  12.  * written prior permission. M.I.T. makes no representations about the 
  13.  * suitability of this software for any purpose.  It is provided "as is"
  14.  * without express or implied warranty.
  15.  *
  16.  * M.I.T. DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
  17.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL M.I.T.
  18.  * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  19.  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
  20.  * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  21.  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  22.  *
  23.  * Author:  Donna Converse, MIT X Consortium
  24.  */
  25.  
  26. #include <X11/Xlib.h>
  27. #include <X11/Xatom.h>
  28. #include <X11/Xutil.h>
  29. #include <stdio.h>
  30.  
  31. static int default_allocation();
  32. static void best_allocation();
  33. static void gray_allocation();
  34. static int icbrt();
  35. static int icbrt_with_bits();
  36. static int icbrt_with_guess();
  37.  
  38. /* To determine the best allocation of reds, greens, and blues in a 
  39.  * standard colormap, use XmuGetColormapAllocation.
  40.  *     vinfo        specifies visual information for a chosen visual
  41.  *    property    specifies one of the standard colormap property names
  42.  *     red_max        returns maximum red value 
  43.  *      green_max    returns maximum green value
  44.  *     blue_max    returns maximum blue value
  45.  *
  46.  * XmuGetColormapAllocation returns 0 on failure, non-zero on success.
  47.  * It is assumed that the visual is appropriate for the colormap property.
  48.  */
  49.  
  50. Status XmuGetColormapAllocation(vinfo, property, red_max, green_max, blue_max)
  51.     XVisualInfo        *vinfo;
  52.     Atom        property;
  53.     unsigned long    *red_max, *green_max, *blue_max;
  54. {
  55.     Status     status = 1;
  56.  
  57.     if (vinfo->colormap_size <= 2)
  58.     return 0;
  59.  
  60.     switch (property)
  61.     {
  62.       case XA_RGB_DEFAULT_MAP:
  63.     status = default_allocation(vinfo, red_max, green_max, blue_max);
  64.     break;
  65.       case XA_RGB_BEST_MAP:
  66.     best_allocation(vinfo, red_max, green_max, blue_max);
  67.     break;
  68.       case XA_RGB_GRAY_MAP:
  69.     gray_allocation(vinfo->colormap_size, red_max, green_max, blue_max);
  70.     break;
  71.       case XA_RGB_RED_MAP:
  72.     *red_max = vinfo->colormap_size - 1;
  73.     *green_max = *blue_max = 0;
  74.     break;
  75.       case XA_RGB_GREEN_MAP:
  76.     *green_max = vinfo->colormap_size - 1;
  77.     *red_max = *blue_max = 0;
  78.     break;
  79.       case XA_RGB_BLUE_MAP:
  80.     *blue_max = vinfo->colormap_size - 1;
  81.     *red_max = *green_max = 0;
  82.     break;
  83.       default:
  84.     status = 0;
  85.     }
  86.     return status;
  87. }
  88.  
  89. /****************************************************************************/
  90. /* Determine the appropriate color allocations of a gray scale.
  91.  *
  92.  * Keith Packard, MIT X Consortium
  93.  */
  94.  
  95. static void gray_allocation(n, red_max, green_max, blue_max)
  96.     int        n;    /* the number of cells of the gray scale */
  97.     unsigned long *red_max, *green_max, *blue_max;
  98. {
  99.     *red_max = (n * 30) / 100;
  100.     *green_max = (n * 59) / 100; 
  101.     *blue_max = (n * 11) / 100; 
  102.     *green_max += ((n - 1) - (*red_max + *green_max + *blue_max));
  103. }
  104.  
  105. /****************************************************************************/
  106. /* Determine an appropriate color allocation for the RGB_DEFAULT_MAP.
  107.  * If a map has less than a minimum number of definable entries, we do not
  108.  * produce an allocation for an RGB_DEFAULT_MAP.  
  109.  *
  110.  * For 24 planes, the default colormap will have 64 reds, 64 greens, and 64
  111.  * blues.  For 8 planes, let n = the number of colormap entries, which may
  112.  * be 256 or 254.  Then, maximum red value = floor(cube_root(n - 125)) - 1.
  113.  * Maximum green and maximum blue values are identical to maximum red.
  114.  * This leaves at least 125 cells which clients can allocate.
  115.  *
  116.  * Return 0 if an allocation has been determined, non-zero otherwise.
  117.  */
  118.  
  119. static int default_allocation(vinfo, red, green, blue)
  120.     XVisualInfo        *vinfo;
  121.     unsigned long    *red, *green, *blue;
  122. {
  123.     int            ngrays;        /* number of gray cells */
  124.  
  125.     if (vinfo->colormap_size < 250)    /* skip it */
  126.     return 0;
  127.  
  128.     switch (vinfo->class) {
  129.       case PseudoColor:
  130.       case DirectColor:
  131.  
  132.     if (vinfo->colormap_size > 500000)
  133.         /* intended for displays with 24 planes */
  134.         *red = *green = *blue = (unsigned long) 63;
  135.     else if (vinfo->colormap_size > 4000)
  136.         /* intended for displays with 12 planes */
  137.         *red = *green = *blue = (unsigned long) 12;
  138.     else
  139.         /* intended for displays with 8 planes */
  140.         *red = *green = *blue = (unsigned long)
  141.         (icbrt(vinfo->colormap_size - 125) - 1);
  142.     break;
  143.  
  144.       case GrayScale:
  145.  
  146.     if (vinfo->colormap_size > 5000000)
  147.         ngrays = 4096;
  148.     else if (vinfo->colormap_size > 4000)
  149.         ngrays = 512;
  150.     else
  151.         ngrays = 12;
  152.     gray_allocation(ngrays, red, green, blue);
  153.     break;
  154.     
  155.       default:
  156.     return 0;
  157.     }
  158.     return 1;
  159. }
  160.  
  161. /****************************************************************************/
  162. /* Determine an appropriate color allocation for the RGB_BEST_MAP.
  163.  *
  164.  * For a DirectColor or TrueColor visual, the allocation is determined
  165.  * by the red_mask, green_mask, and blue_mask members of the visual info.
  166.  *
  167.  * Otherwise, if the colormap size is an integral power of 2, determine
  168.  * the allocation according to the number of bits given to each color,
  169.  * with green getting more than red, and red more than blue, if there
  170.  * are to be inequities in the distribution.  If the colormap size is
  171.  * not an integral power of 2, let n = the number of colormap entries.
  172.  * Then maximum red value = floor(cube_root(n)) - 1;
  173.  *     maximum blue value = floor(cube_root(n)) - 1;
  174.  *    maximum green value = n / ((# red values) * (# blue values)) - 1;
  175.  * Which, on a GPX, allows for 252 entries in the best map, out of 254
  176.  * defineable colormap entries.
  177.  */
  178.  
  179. static void best_allocation(vinfo, red, green, blue)
  180.     XVisualInfo        *vinfo;
  181.     unsigned long    *red, *green, *blue;
  182. {
  183.  
  184.     if (vinfo->class == DirectColor ||    vinfo->class == TrueColor)
  185.     {
  186.     *red = vinfo->red_mask;
  187.     while ((*red & 01) == 0)
  188.         *red >>= 1;
  189.     *green = vinfo->green_mask;
  190.     while ((*green & 01) == 0)
  191.         *green >>=1;
  192.     *blue = vinfo->blue_mask;
  193.     while ((*blue & 01) == 0)
  194.         *blue >>= 1;
  195.     }
  196.     else
  197.     {
  198.     register int bits, n;
  199.     
  200.     /* Determine n such that n is the least integral power of 2 which is
  201.      * greater than or equal to the number of entries in the colormap.
  202.          */
  203.     n = 1;
  204.     bits = 0;
  205.     while (vinfo->colormap_size > n)
  206.     {
  207.         n = n << 1;
  208.         bits++;
  209.     }
  210.     
  211.     /* If the number of entries in the colormap is a power of 2, determine
  212.      * the allocation by "dealing" the bits, first to green, then red, then
  213.      * blue.  If not, find the maximum integral red, green, and blue values
  214.      * which, when multiplied together, do not exceed the number of 
  215.  
  216.      * colormap entries.
  217.      */
  218.     if (n == vinfo->colormap_size)
  219.     {
  220.         register int r, g, b;
  221.         b = bits / 3;
  222.         g = b + ((bits % 3) ? 1 : 0);
  223.         r = b + (((bits % 3) == 2) ? 1 : 0);
  224.         *red = 1 << r;
  225.         *green = 1 << g;
  226.         *blue = 1 << b;
  227.     }
  228.     else
  229.     {
  230.         *red = icbrt_with_bits(vinfo->colormap_size, bits);
  231.         *blue = *red;    
  232.         *green = (vinfo->colormap_size / ((*red) * (*blue)));
  233.     }
  234.     (*red)--;
  235.     (*green)--;
  236.     (*blue)--;
  237.     }
  238.     return;
  239. }
  240.  
  241. /*
  242.  * integer cube roots by Newton's method
  243.  *
  244.  * Stephen Gildea, MIT X Consortium, July 1991
  245.  */
  246.  
  247. static int icbrt(a)        /* integer cube root */
  248.     int a;
  249. {
  250.     register int bits = 0;
  251.     register unsigned n = a;
  252.  
  253.     while (n)
  254.     {
  255.     bits++;
  256.     n >>= 1;
  257.     }
  258.     return icbrt_with_bits(a, bits);
  259. }
  260.  
  261.  
  262. static int icbrt_with_bits(a, bits)
  263.     int a;
  264.     int bits;            /* log 2 of a */
  265. {
  266.     return icbrt_with_guess(a, a>>2*bits/3);
  267. }
  268.  
  269. #ifdef _X_ROOT_STATS
  270. int icbrt_loopcount;
  271. #endif
  272.  
  273. /* Newton's Method:  x_n+1 = x_n - ( f(x_n) / f'(x_n) ) */
  274.  
  275. /* for cube roots, x^3 - a = 0,  x_new = x - 1/3 (x - a/x^2) */
  276.  
  277. /*
  278.  * Quick and dirty cube roots.  Nothing fancy here, just Newton's method.
  279.  * Only works for positive integers (since that's all we need).
  280.  * We actually return floor(cbrt(a)) because that's what we need here, too.
  281.  */
  282.  
  283. static int icbrt_with_guess(a, guess)
  284.     int a, guess;
  285. {
  286.     register int delta;
  287.  
  288. #ifdef _X_ROOT_STATS
  289.     icbrt_loopcount = 0;
  290. #endif
  291.     if (a <= 0)
  292.     return 0;
  293.     if (guess < 1)
  294.     guess = 1;
  295.  
  296.     do {
  297. #ifdef _X_ROOT_STATS
  298.     icbrt_loopcount++;
  299. #endif
  300.     delta = (guess - a/(guess*guess))/3;
  301. #ifdef DEBUG
  302.     printf("pass %d: guess=%d, delta=%d\n", icbrt_loopcount, guess, delta);
  303. #endif
  304.     guess -= delta;
  305.     } while (delta != 0);
  306.  
  307.     if (guess*guess*guess > a)
  308.     guess--;
  309.  
  310.     return guess;
  311. }
  312.