miindex.c revision 05b261ec 
1/*
2 *
3 * Copyright © 2001 Keith Packard, member of The XFree86 Project, Inc.
4 *
5 * Permission to use, copy, modify, distribute, and sell this software and its
6 * documentation for any purpose is hereby granted without fee, provided that
7 * the above copyright notice appear in all copies and that both that
8 * copyright notice and this permission notice appear in supporting
9 * documentation, and that the name of Keith Packard not be used in
10 * advertising or publicity pertaining to distribution of the software without
11 * specific, written prior permission.  Keith Packard makes no
12 * representations about the suitability of this software for any purpose.  It
13 * is provided "as is" without express or implied warranty.
14 *
15 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
17 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
18 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
19 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
20 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
21 * PERFORMANCE OF THIS SOFTWARE.
22 */
23
24#ifdef HAVE_DIX_CONFIG_H
25#include <dix-config.h>
26#endif
27
28#ifndef _MIINDEX_H_
29#define _MIINDEX_H_
30
31#include "scrnintstr.h"
32#include "gcstruct.h"
33#include "pixmapstr.h"
34#include "windowstr.h"
35#include "mi.h"
36#include "picturestr.h"
37#include "mipict.h"
38#include "colormapst.h"
39
40#define NUM_CUBE_LEVELS	4
41#define NUM_GRAY_LEVELS	13
42
43static Bool
44miBuildRenderColormap (ColormapPtr  pColormap, Pixel *pixels, int *nump)
45{
46    int		r, g, b;
47    unsigned short  red, green, blue;
48    Pixel	pixel;
49    Bool	used[MI_MAX_INDEXED];
50    int		needed;
51    int		policy;
52    int		cube, gray;
53    int		i, n;
54
55    if (pColormap->mid != pColormap->pScreen->defColormap)
56    {
57	policy = PictureCmapPolicyAll;
58    }
59    else
60    {
61	int	avail = pColormap->pVisual->ColormapEntries;
62	policy = PictureCmapPolicy;
63	if (policy == PictureCmapPolicyDefault)
64	{
65	    if (avail >= 256 && (pColormap->pVisual->class|DynamicClass) == PseudoColor)
66		policy = PictureCmapPolicyColor;
67	    else if (avail >= 64)
68		policy = PictureCmapPolicyGray;
69	    else
70		policy = PictureCmapPolicyMono;
71	}
72    }
73    /*
74     * Make sure enough cells are free for the chosen policy
75     */
76    for (;;)
77    {
78	switch (policy) {
79	case PictureCmapPolicyAll:
80	    needed = 0;
81	    break;
82	case PictureCmapPolicyColor:
83	    needed = 71;
84	    break;
85	case PictureCmapPolicyGray:
86	    needed = 11;
87	    break;
88	case PictureCmapPolicyMono:
89	default:
90	    needed = 0;
91	    break;
92	}
93	if (needed <= pColormap->freeRed)
94	    break;
95	policy--;
96    }
97
98    /*
99     * Compute size of cube and gray ramps
100     */
101    cube = gray = 0;
102    switch (policy) {
103    case PictureCmapPolicyAll:
104	/*
105	 * Allocate as big a cube as possible
106	 */
107	if ((pColormap->pVisual->class|DynamicClass) == PseudoColor)
108	{
109	    for (cube = 1; cube * cube * cube < pColormap->pVisual->ColormapEntries; cube++)
110		;
111	    cube--;
112	    if (cube == 1)
113		cube = 0;
114	}
115	else
116	    cube = 0;
117	/*
118	 * Figure out how many gray levels to use so that they
119	 * line up neatly with the cube
120	 */
121	if (cube)
122	{
123	    needed = pColormap->pVisual->ColormapEntries - (cube*cube*cube);
124	    /* levels to fill in with */
125	    gray = needed / (cube - 1);
126	    /* total levels */
127	    gray = (gray + 1) * (cube - 1) + 1;
128	}
129	else
130	    gray = pColormap->pVisual->ColormapEntries;
131	break;
132
133    case PictureCmapPolicyColor:
134	cube = NUM_CUBE_LEVELS;
135	/* fall through ... */
136    case PictureCmapPolicyGray:
137	gray = NUM_GRAY_LEVELS;
138	break;
139    case PictureCmapPolicyMono:
140    default:
141	gray = 2;
142	break;
143    }
144
145    memset (used, '\0', pColormap->pVisual->ColormapEntries * sizeof (Bool));
146    for (r = 0; r < cube; r++)
147	for (g = 0; g < cube; g++)
148	    for (b = 0; b < cube; b++)
149	    {
150		red = (r * 65535 + (cube-1)/2) / (cube - 1);
151		green = (g * 65535 + (cube-1)/2) / (cube - 1);
152		blue = (b * 65535 + (cube-1)/2) / (cube - 1);
153		if (AllocColor (pColormap, &red, &green,
154				&blue, &pixel, 0) != Success)
155		    return FALSE;
156		used[pixel] = TRUE;
157	    }
158    for (g = 0; g < gray; g++)
159    {
160	red = green = blue = (g * 65535 + (gray-1)/2) / (gray - 1);
161	if (AllocColor (pColormap, &red, &green, &blue, &pixel, 0) != Success)
162	    return FALSE;
163	used[pixel] = TRUE;
164    }
165    n = 0;
166    for (i = 0; i < pColormap->pVisual->ColormapEntries; i++)
167	if (used[i])
168	    pixels[n++] = i;
169
170    *nump = n;
171
172    return TRUE;
173}
174
175/* 0 <= red, green, blue < 32 */
176static Pixel
177FindBestColor (miIndexedPtr pIndexed, Pixel *pixels, int num,
178	       int red, int green, int blue)
179{
180    Pixel   best = pixels[0];
181    int	    bestDist = 1 << 30;
182    int	    dist;
183    int	    dr, dg, db;
184    while (num--)
185    {
186	Pixel	pixel = *pixels++;
187	CARD32	v = pIndexed->rgba[pixel];
188
189	dr = ((v >> 19) & 0x1f);
190	dg = ((v >> 11) & 0x1f);
191	db = ((v >> 3) & 0x1f);
192	dr = dr - red;
193	dg = dg - green;
194	db = db - blue;
195	dist = dr * dr + dg * dg + db * db;
196	if (dist < bestDist)
197	{
198	    bestDist = dist;
199	    best = pixel;
200	}
201    }
202    return best;
203}
204
205/* 0 <= gray < 32768 */
206static Pixel
207FindBestGray (miIndexedPtr pIndexed, Pixel *pixels, int num, int gray)
208{
209    Pixel   best = pixels[0];
210    int	    bestDist = 1 << 30;
211    int	    dist;
212    int	    dr;
213    int	    r;
214
215    while (num--)
216    {
217	Pixel   pixel = *pixels++;
218	CARD32	v = pIndexed->rgba[pixel];
219
220	r = v & 0xff;
221	r = r | (r << 8);
222	dr = gray - (r >> 1);
223	dist = dr * dr;
224	if (dist < bestDist)
225	{
226	    bestDist = dist;
227	    best = pixel;
228	}
229    }
230    return best;
231}
232
233Bool
234miInitIndexed (ScreenPtr	pScreen,
235	       PictFormatPtr	pFormat)
236{
237    ColormapPtr	    pColormap = pFormat->index.pColormap;
238    VisualPtr	    pVisual = pColormap->pVisual;
239    miIndexedPtr    pIndexed;
240    Pixel	    pixels[MI_MAX_INDEXED];
241    xrgb	    rgb[MI_MAX_INDEXED];
242    int		    num;
243    int		    i;
244    Pixel	    p, r, g, b;
245
246    if (pVisual->ColormapEntries > MI_MAX_INDEXED)
247	return FALSE;
248
249    if (pVisual->class & DynamicClass)
250    {
251	if (!miBuildRenderColormap (pColormap, pixels, &num))
252	    return FALSE;
253    }
254    else
255    {
256	num = pVisual->ColormapEntries;
257	for (p = 0; p < num; p++)
258	    pixels[p] = p;
259    }
260
261    pIndexed = xalloc (sizeof (miIndexedRec));
262    if (!pIndexed)
263	return FALSE;
264
265    pFormat->index.nvalues = num;
266    pFormat->index.pValues = xalloc (num * sizeof (xIndexValue));
267    if (!pFormat->index.pValues)
268    {
269	xfree (pIndexed);
270	return FALSE;
271    }
272
273
274    /*
275     * Build mapping from pixel value to ARGB
276     */
277    QueryColors (pColormap, num, pixels, rgb);
278    for (i = 0; i < num; i++)
279    {
280	p = pixels[i];
281	pFormat->index.pValues[i].pixel = p;
282	pFormat->index.pValues[i].red   = rgb[i].red;
283	pFormat->index.pValues[i].green = rgb[i].green;
284	pFormat->index.pValues[i].blue  = rgb[i].blue;
285	pFormat->index.pValues[i].alpha = 0xffff;
286	pIndexed->rgba[p] = (0xff000000 |
287			     ((rgb[i].red   & 0xff00) << 8) |
288			     ((rgb[i].green & 0xff00)     ) |
289			     ((rgb[i].blue  & 0xff00) >> 8));
290    }
291
292    /*
293     * Build mapping from RGB to pixel value.  This could probably be
294     * done a bit quicker...
295     */
296    switch (pVisual->class | DynamicClass) {
297    case GrayScale:
298	pIndexed->color = FALSE;
299	for (r = 0; r < 32768; r++)
300	    pIndexed->ent[r] = FindBestGray (pIndexed, pixels, num, r);
301	break;
302    case PseudoColor:
303	pIndexed->color = TRUE;
304	p = 0;
305	for (r = 0; r < 32; r++)
306	    for (g = 0; g < 32; g++)
307		for (b = 0; b < 32; b++)
308		{
309		    pIndexed->ent[p] = FindBestColor (pIndexed, pixels, num,
310						      r, g, b);
311		    p++;
312		}
313	break;
314    }
315    pFormat->index.devPrivate = pIndexed;
316    return TRUE;
317}
318
319void
320miCloseIndexed (ScreenPtr	pScreen,
321		PictFormatPtr	pFormat)
322{
323    if (pFormat->index.devPrivate)
324    {
325	xfree (pFormat->index.devPrivate);
326	pFormat->index.devPrivate = 0;
327    }
328    if (pFormat->index.pValues)
329    {
330	xfree (pFormat->index.pValues);
331	pFormat->index.pValues = 0;
332    }
333}
334
335void
336miUpdateIndexed (ScreenPtr	pScreen,
337		 PictFormatPtr	pFormat,
338		 int		ndef,
339		 xColorItem	*pdef)
340{
341    miIndexedPtr pIndexed = pFormat->index.devPrivate;
342
343    if (pIndexed)
344    {
345	while (ndef--)
346	{
347	    pIndexed->rgba[pdef->pixel] = (0xff000000 |
348					   ((pdef->red   & 0xff00) << 8) |
349					   ((pdef->green & 0xff00)     ) |
350					   ((pdef->blue  & 0xff00) >> 8));
351	    pdef++;
352	}
353    }
354}
355
356#endif /* _MIINDEX_H_ */
357