1 /* $XConsortium: CrCmap.c,v 1.6 94/04/17 20:15:53 rws Exp $ */
2
3 /*
4
5 Copyright (c) 1989 X Consortium
6
7 Permission is hereby granted, free of charge, to any person obtaining a copy
8 of this software and associated documentation files (the "Software"), to deal
9 in the Software without restriction, including without limitation the rights
10 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 copies of the Software, and to permit persons to whom the Software is
12 furnished to do so, subject to the following conditions:
13
14 The above copyright notice and this permission notice shall be included in
15 all copies or substantial portions of the Software.
16
17 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
21 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23
24 Except as contained in this notice, the name of the X Consortium shall not be
25 used in advertising or otherwise to promote the sale, use or other dealings
26 in this Software without prior written authorization from the X Consortium.
27
28 */
29
30 /*
31 * Author: Donna Converse, MIT X Consortium
32 */
33
34 /*
35 * CreateCmap.c - given a standard colormap description, make the map.
36 */
37
38 #include <stdio.h>
39 #include <X11/Xlib.h>
40 #include <X11/Xutil.h>
41 #include <stdlib.h>
42
43 static int ROmap(); /* allocate entire map Read Only */
44 static Status ROorRWcell(); /* allocate a cell, prefer Read Only */
45 static Status RWcell(); /* allocate a cell Read Write */
46 static int compare(); /* for quicksort */
47 static Status contiguous(); /* find contiguous sequence of cells */
48 static void free_cells(); /* frees resources before quitting */
49 static Status readonly_map(); /* create a map in a RO visual type */
50 static Status readwrite_map(); /* create a map in a RW visual type */
51
52 #define lowbit(x) ((x) & (~(x) + 1))
53 #define TRUEMATCH(mult,max,mask) \
54 (colormap->max * colormap->mult <= vinfo->mask && \
55 lowbit(vinfo->mask) == colormap->mult)
56
57 /*
58 * To create any one colormap which is described by an XStandardColormap
59 * structure, use XmuCreateColormap().
60 *
61 * Return 0 on failure, non-zero on success.
62 * Resources created by this function are not made permanent.
63 * No argument error checking is provided. Use at your own risk.
64 *
65 * All colormaps are created with read only allocations, with the exception
66 * of read only allocations of colors in the default map or otherwise
67 * which fail to return the expected pixel value, and these are individually
68 * defined as read/write allocations. This is done so that all the cells
69 * defined in the default map are contiguous, for use in image processing.
70 * This typically happens with White and Black in the default map.
71 *
72 * Colormaps of static visuals are considered to be successfully created if
73 * the map of the static visual matches the definition given in the
74 * standard colormap structure.
75 */
76
XmuCreateColormap(dpy,colormap)77 Status XmuCreateColormap(dpy, colormap)
78 Display *dpy; /* specifies the connection under
79 * which the map is created */
80 XStandardColormap *colormap; /* specifies the map to be created,
81 * and returns, particularly if the
82 * map is created as a subset of the
83 * default colormap of the screen,
84 * the base_pixel of the map.
85 */
86 {
87 XVisualInfo vinfo_template; /* template visual information */
88 XVisualInfo *vinfo; /* matching visual information */
89 XVisualInfo *vpointer; /* for freeing the entire list */
90 long vinfo_mask; /* specifies the visual mask value */
91 int n; /* number of matching visuals */
92 int status;
93
94 vinfo_template.visualid = colormap->visualid;
95 vinfo_mask = VisualIDMask;
96 if ((vinfo = XGetVisualInfo(dpy, vinfo_mask, &vinfo_template, &n)) == NULL)
97 return 0;
98
99 /* A visual id may be valid on multiple screens. Also, there may
100 * be multiple visuals with identical visual ids at different depths.
101 * If the colormap is the Default Colormap, use the Default Visual.
102 * Otherwise, arbitrarily, use the deepest visual.
103 */
104 vpointer = vinfo;
105 if (n > 1)
106 {
107 register int i;
108 register int screen_number;
109 Bool def_cmap;
110
111 def_cmap = False;
112 for (screen_number = ScreenCount(dpy); --screen_number >= 0; )
113 if (colormap->colormap == DefaultColormap(dpy, screen_number)) {
114 def_cmap = True;
115 break;
116 }
117
118 if (def_cmap) {
119 for (i=0; i < n; i++, vinfo++) {
120 if (vinfo->visual == DefaultVisual(dpy, screen_number))
121 break;
122 }
123 } else {
124 unsigned int maxdepth = 0;
125 XVisualInfo *v;
126
127 for (i=0; i < n; i++, vinfo++)
128 if (vinfo->depth > maxdepth) {
129 maxdepth = vinfo->depth;
130 v = vinfo;
131 }
132 vinfo = v;
133 }
134 }
135
136 if (vinfo->class == PseudoColor || vinfo->class == DirectColor ||
137 vinfo->class == GrayScale)
138 status = readwrite_map(dpy, vinfo, colormap);
139 else if (vinfo->class == TrueColor)
140 status = TRUEMATCH(red_mult, red_max, red_mask) &&
141 TRUEMATCH(green_mult, green_max, green_mask) &&
142 TRUEMATCH(blue_mult, blue_max, blue_mask);
143 else
144 status = readonly_map(dpy, vinfo, colormap);
145
146 XFree((char *) vpointer);
147 return status;
148 }
149
150 /****************************************************************************/
readwrite_map(dpy,vinfo,colormap)151 static Status readwrite_map(dpy, vinfo, colormap)
152 Display *dpy;
153 XVisualInfo *vinfo;
154 XStandardColormap *colormap;
155 {
156 register unsigned long i, n; /* index counters */
157 int ncolors; /* number of colors to be defined */
158 int npixels; /* number of pixels allocated R/W */
159 int first_index; /* first index of pixels to use */
160 int remainder; /* first index of remainder */
161 XColor color; /* the definition of a color */
162 unsigned long *pixels; /* array of colormap pixels */
163 unsigned long delta;
164
165
166 /* Determine ncolors, the number of colors to be defined.
167 * Insure that 1 < ncolors <= the colormap size.
168 */
169 if (vinfo->class == DirectColor) {
170 ncolors = colormap->red_max;
171 if (colormap->green_max > ncolors)
172 ncolors = colormap->green_max;
173 if (colormap->blue_max > ncolors)
174 ncolors = colormap->blue_max;
175 ncolors++;
176 delta = lowbit(vinfo->red_mask) +
177 lowbit(vinfo->green_mask) +
178 lowbit(vinfo->blue_mask);
179 } else {
180 ncolors = colormap->red_max * colormap->red_mult +
181 colormap->green_max * colormap->green_mult +
182 colormap->blue_max * colormap->blue_mult + 1;
183 delta = 1;
184 }
185 if (ncolors <= 1 || ncolors > vinfo->colormap_size) return 0;
186
187 /* Allocate Read/Write as much of the colormap as we can possibly get.
188 * Then insure that the pixels we were allocated are given in
189 * monotonically increasing order, using a quicksort. Next, insure
190 * that our allocation includes a subset of contiguous pixels at least
191 * as long as the number of colors to be defined. Now we know that
192 * these conditions are met:
193 * 1) There are no free cells in the colormap.
194 * 2) We have a contiguous sequence of pixels, monotonically
195 * increasing, of length >= the number of colors requested.
196 *
197 * One cell at a time, we will free, compute the next color value,
198 * then allocate read only. This takes a long time.
199 * This is done to insure that cells are allocated read only in the
200 * contiguous order which we prefer. If the server has a choice of
201 * cells to grant to an allocation request, the server may give us any
202 * cell, so that is why we do these slow gymnastics.
203 */
204
205 if ((pixels = (unsigned long *) calloc((unsigned) vinfo->colormap_size,
206 sizeof(unsigned long))) == NULL)
207 return 0;
208
209 if ((npixels = ROmap(dpy, colormap->colormap, pixels,
210 vinfo->colormap_size, ncolors)) == 0) {
211 free((char *) pixels);
212 return 0;
213 }
214
215 qsort((char *) pixels, npixels, sizeof(unsigned long), compare);
216
217 if (!contiguous(pixels, npixels, ncolors, delta, &first_index, &remainder))
218 {
219 /* can't find enough contiguous cells, give up */
220 XFreeColors(dpy, colormap->colormap, pixels, npixels,
221 (unsigned long) 0);
222 free((char *) pixels);
223 return 0;
224 }
225 colormap->base_pixel = pixels[first_index];
226
227 /* construct a gray map */
228 if (colormap->red_mult == 1 && colormap->green_mult == 1 &&
229 colormap->blue_mult == 1)
230 for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
231 {
232 color.pixel = n;
233 color.blue = color.green = color.red =
234 (unsigned short) ((i * 65535) / (colormap->red_max +
235 colormap->green_max +
236 colormap->blue_max));
237
238 if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
239 first_index + i))
240 return 0;
241 }
242
243 /* construct a red ramp map */
244 else if (colormap->green_max == 0 && colormap->blue_max == 0)
245 for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
246 {
247 color.pixel = n;
248 color.red = (unsigned short) ((i * 65535) / colormap->red_max);
249 color.green = color.blue = 0;
250
251 if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
252 first_index + i))
253 return 0;
254 }
255
256 /* construct a green ramp map */
257 else if (colormap->red_max == 0 && colormap->blue_max == 0)
258 for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
259 {
260 color.pixel = n;
261 color.green = (unsigned short) ((i * 65535) / colormap->green_max);
262 color.red = color.blue = 0;
263
264 if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
265 first_index + i))
266 return 0;
267 }
268
269 /* construct a blue ramp map */
270 else if (colormap->red_max == 0 && colormap->green_max == 0)
271 for (n=colormap->base_pixel, i=0; i < ncolors; i++, n += delta)
272 {
273 color.pixel = n;
274 color.blue = (unsigned short) ((i * 65535) / colormap->blue_max);
275 color.red = color.green = 0;
276
277 if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
278 first_index + i))
279 return 0;
280 }
281
282 /* construct a standard red green blue cube map */
283 else
284 {
285 #define calc(max,mult) (((n / colormap->mult) % \
286 (colormap->max + 1)) * 65535) / colormap->max
287
288 for (n=0, i=0; i < ncolors; i++, n += delta)
289 {
290 color.pixel = n + colormap->base_pixel;
291 color.red = calc(red_max, red_mult);
292 color.green = calc(green_max, green_mult);
293 color.blue = calc(blue_max, blue_mult);
294 if (! ROorRWcell(dpy, colormap->colormap, pixels, npixels, &color,
295 first_index + i))
296 return 0;
297 }
298 #undef calc
299 }
300 /* We have a read-only map defined. Now free unused cells,
301 * first those occurring before the contiguous sequence begins,
302 * then any following the contiguous sequence.
303 */
304
305 if (first_index)
306 XFreeColors(dpy, colormap->colormap, pixels, first_index,
307 (unsigned long) 0);
308 if (remainder)
309 XFreeColors(dpy, colormap->colormap,
310 &(pixels[first_index + ncolors]), remainder,
311 (unsigned long) 0);
312
313 free((char *) pixels);
314 return 1;
315 }
316
317
318 /****************************************************************************/
ROmap(dpy,cmap,pixels,m,n)319 static int ROmap(dpy, cmap, pixels, m, n)
320 Display *dpy; /* the X server connection */
321 Colormap cmap; /* specifies colormap ID */
322 unsigned long pixels[]; /* returns pixel allocations */
323 int m; /* specifies colormap size */
324 int n; /* specifies number of colors */
325 {
326 register int p;
327
328 /* first try to allocate the entire colormap */
329 if (XAllocColorCells(dpy, cmap, 1, (unsigned long *) NULL,
330 (unsigned) 0, pixels, (unsigned) m))
331 return m;
332
333 /* Allocate all available cells in the colormap, using a binary
334 * algorithm to discover how many cells we can allocate in the colormap.
335 */
336 m--;
337 while (n <= m) {
338 p = n + ((m - n + 1) / 2);
339 if (XAllocColorCells(dpy, cmap, 1, (unsigned long *) NULL,
340 (unsigned) 0, pixels, (unsigned) p)) {
341 if (p == m)
342 return p;
343 else {
344 XFreeColors(dpy, cmap, pixels, p, (unsigned long) 0);
345 n = p;
346 }
347 }
348 else
349 m = p - 1;
350 }
351 return 0;
352 }
353
354
355 /****************************************************************************/
contiguous(pixels,npixels,ncolors,delta,first,rem)356 static Status contiguous(pixels, npixels, ncolors, delta, first, rem)
357 unsigned long pixels[]; /* specifies allocated pixels */
358 int npixels; /* specifies count of alloc'd pixels */
359 int ncolors; /* specifies needed sequence length */
360 unsigned long delta; /* between pixels */
361 int *first; /* returns first index of sequence */
362 int *rem; /* returns first index after sequence,
363 * or 0, if none follow */
364 {
365 register int i = 1; /* walking index into the pixel array */
366 register int count = 1; /* length of sequence discovered so far */
367
368 *first = 0;
369 if (npixels == ncolors) {
370 *rem = 0;
371 return 1;
372 }
373 *rem = npixels - 1;
374 while (count < ncolors && ncolors - count <= *rem)
375 {
376 if (pixels[i-1] + delta == pixels[i])
377 count++;
378 else {
379 count = 1;
380 *first = i;
381 }
382 i++;
383 (*rem)--;
384 }
385 if (count != ncolors)
386 return 0;
387 return 1;
388 }
389
390
391 /****************************************************************************/
ROorRWcell(dpy,cmap,pixels,npixels,color,p)392 static Status ROorRWcell(dpy, cmap, pixels, npixels, color, p)
393 Display *dpy;
394 Colormap cmap;
395 unsigned long pixels[];
396 int npixels;
397 XColor *color;
398 unsigned long p;
399 {
400 unsigned long pixel;
401 XColor request;
402
403 /* Free the read/write allocation of one cell in the colormap.
404 * Request a read only allocation of one cell in the colormap.
405 * If the read only allocation cannot be granted, give up, because
406 * there must be no free cells in the colormap.
407 * If the read only allocation is granted, but gives us a cell which
408 * is not the one that we just freed, it is probably the case that
409 * we are trying allocate White or Black or some other color which
410 * already has a read-only allocation in the map. So we try to
411 * allocate the previously freed cell with a read/write allocation,
412 * because we want contiguous cells for image processing algorithms.
413 */
414
415 pixel = color->pixel;
416 request.red = color->red;
417 request.green = color->green;
418 request.blue = color->blue;
419
420 XFreeColors(dpy, cmap, &pixel, 1, (unsigned long) 0);
421 if (! XAllocColor(dpy, cmap, color)
422 || (color->pixel != pixel &&
423 (!RWcell(dpy, cmap, color, &request, &pixel))))
424 {
425 free_cells(dpy, cmap, pixels, npixels, (int)p);
426 return 0;
427 }
428 return 1;
429 }
430
431
432 /****************************************************************************/
free_cells(dpy,cmap,pixels,npixels,p)433 static void free_cells(dpy, cmap, pixels, npixels, p)
434 Display *dpy;
435 Colormap cmap;
436 unsigned long pixels[]; /* to be freed */
437 int npixels; /* original number allocated */
438 int p;
439 {
440 /* One of the npixels allocated has already been freed.
441 * p is the index of the freed pixel.
442 * First free the pixels preceding p, and there are p of them;
443 * then free the pixels following p, there are npixels - p - 1 of them.
444 */
445 XFreeColors(dpy, cmap, pixels, p, (unsigned long) 0);
446 XFreeColors(dpy, cmap, &(pixels[p+1]), npixels - p - 1, (unsigned long) 0);
447 free((char *) pixels);
448 }
449
450
451 /****************************************************************************/
RWcell(dpy,cmap,color,request,pixel)452 static Status RWcell(dpy, cmap, color, request, pixel)
453 Display *dpy;
454 Colormap cmap;
455 XColor *color;
456 XColor *request;
457 unsigned long *pixel;
458 {
459 unsigned long n = *pixel;
460
461 XFreeColors(dpy, cmap, &(color->pixel), 1, (unsigned long)0);
462 if (! XAllocColorCells(dpy, cmap, (Bool) 0, (unsigned long *) NULL,
463 (unsigned) 0, pixel, (unsigned) 1))
464 return 0;
465 if (*pixel != n)
466 {
467 XFreeColors(dpy, cmap, pixel, 1, (unsigned long) 0);
468 return 0;
469 }
470 color->pixel = *pixel;
471 color->flags = DoRed | DoGreen | DoBlue;
472 color->red = request->red;
473 color->green = request->green;
474 color->blue = request->blue;
475 XStoreColors(dpy, cmap, color, 1);
476 return 1;
477 }
478
479
480 /****************************************************************************/
compare(e1,e2)481 static int compare(e1, e2)
482 unsigned long *e1, *e2;
483 {
484 if (*e1 < *e2) return -1;
485 if (*e1 > *e2) return 1;
486 return 0;
487 }
488
489
490 /****************************************************************************/
readonly_map(dpy,vinfo,colormap)491 static Status readonly_map(dpy, vinfo, colormap)
492 Display *dpy;
493 XVisualInfo *vinfo;
494 XStandardColormap *colormap;
495 {
496 int i, last_pixel;
497 XColor color;
498
499 last_pixel = (colormap->red_max + 1) * (colormap->green_max + 1) *
500 (colormap->blue_max + 1) + colormap->base_pixel - 1;
501
502 for(i=colormap->base_pixel; i <= last_pixel; i++) {
503
504 color.pixel = (unsigned long) i;
505 color.red = (unsigned short)
506 (((i/colormap->red_mult) * 65535) / colormap->red_max);
507
508 if (vinfo->class == StaticColor) {
509 color.green = (unsigned short)
510 ((((i/colormap->green_mult) % (colormap->green_max + 1)) *
511 65535) / colormap->green_max);
512 color.blue = (unsigned short)
513 (((i%colormap->green_mult) * 65535) / colormap->blue_max);
514 }
515 else /* vinfo->class == GrayScale, old style allocation XXX */
516 color.green = color.blue = color.red;
517
518 XAllocColor(dpy, colormap->colormap, &color);
519 if (color.pixel != (unsigned long) i)
520 return 0;
521 }
522 return 1;
523 }
524