CmapAlloc.c revision 53bb355a 
1/*
2
3Copyright 1989, 1994, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in 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 */
45static void best_allocation(XVisualInfo*, unsigned long*, unsigned long*,
46			    unsigned long*);
47static int default_allocation(XVisualInfo*, unsigned long*,
48			      unsigned long*, unsigned long*);
49static void gray_allocation(int, unsigned long*, unsigned long*,
50			    unsigned long*);
51static int icbrt(int);
52static int icbrt_with_bits(int, int);
53static 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
67Status
68XmuGetColormapAllocation(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
113static void
114gray_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
137static int
138default_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 * definable colormap entries.
209 */
210
211static void
212best_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
279static int
280icbrt(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
294static int
295icbrt_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
302int 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
315static int
316icbrt_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}
344