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