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