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 
43 static Bool
miBuildRenderColormap(ColormapPtr pColormap,Pixel * pixels,int * nump)44 miBuildRenderColormap(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         policy = PictureCmapPolicyAll;
57     }
58     else {
59         int avail = pColormap->pVisual->ColormapEntries;
60 
61         policy = PictureCmapPolicy;
62         if (policy == PictureCmapPolicyDefault) {
63             if (avail >= 256 &&
64                 (pColormap->pVisual->class | DynamicClass) == PseudoColor)
65                 policy = PictureCmapPolicyColor;
66             else if (avail >= 64)
67                 policy = PictureCmapPolicyGray;
68             else
69                 policy = PictureCmapPolicyMono;
70         }
71     }
72     /*
73      * Make sure enough cells are free for the chosen policy
74      */
75     for (;;) {
76         switch (policy) {
77         case PictureCmapPolicyAll:
78             needed = 0;
79             break;
80         case PictureCmapPolicyColor:
81             needed = 71;
82             break;
83         case PictureCmapPolicyGray:
84             needed = 11;
85             break;
86         case PictureCmapPolicyMono:
87         default:
88             needed = 0;
89             break;
90         }
91         if (needed <= pColormap->freeRed)
92             break;
93         policy--;
94     }
95 
96     /*
97      * Compute size of cube and gray ramps
98      */
99     cube = gray = 0;
100     switch (policy) {
101     case PictureCmapPolicyAll:
102         /*
103          * Allocate as big a cube as possible
104          */
105         if ((pColormap->pVisual->class | DynamicClass) == PseudoColor) {
106             for (cube = 1;
107                  cube * cube * cube < pColormap->pVisual->ColormapEntries;
108                  cube++);
109             cube--;
110             if (cube == 1)
111                 cube = 0;
112         }
113         else
114             cube = 0;
115         /*
116          * Figure out how many gray levels to use so that they
117          * line up neatly with the cube
118          */
119         if (cube) {
120             needed = pColormap->pVisual->ColormapEntries - (cube * cube * cube);
121             /* levels to fill in with */
122             gray = needed / (cube - 1);
123             /* total levels */
124             gray = (gray + 1) * (cube - 1) + 1;
125         }
126         else
127             gray = pColormap->pVisual->ColormapEntries;
128         break;
129 
130     case PictureCmapPolicyColor:
131         cube = NUM_CUBE_LEVELS;
132         /* fall through ... */
133     case PictureCmapPolicyGray:
134         gray = NUM_GRAY_LEVELS;
135         break;
136     case PictureCmapPolicyMono:
137     default:
138         gray = 2;
139         break;
140     }
141 
142     memset(used, '\0', pColormap->pVisual->ColormapEntries * sizeof(Bool));
143     for (r = 0; r < cube; r++)
144         for (g = 0; g < cube; g++)
145             for (b = 0; b < cube; b++) {
146                 pixel = 0;
147                 red = (r * 65535 + (cube - 1) / 2) / (cube - 1);
148                 green = (g * 65535 + (cube - 1) / 2) / (cube - 1);
149                 blue = (b * 65535 + (cube - 1) / 2) / (cube - 1);
150                 if (AllocColor(pColormap, &red, &green,
151                                &blue, &pixel, 0) != Success)
152                     return FALSE;
153                 used[pixel] = TRUE;
154             }
155     for (g = 0; g < gray; g++) {
156         pixel = 0;
157         red = green = blue = (g * 65535 + (gray - 1) / 2) / (gray - 1);
158         if (AllocColor(pColormap, &red, &green, &blue, &pixel, 0) != Success)
159             return FALSE;
160         used[pixel] = TRUE;
161     }
162     n = 0;
163     for (i = 0; i < pColormap->pVisual->ColormapEntries; i++)
164         if (used[i])
165             pixels[n++] = i;
166 
167     *nump = n;
168 
169     return TRUE;
170 }
171 
172 /* 0 <= red, green, blue < 32 */
173 static Pixel
FindBestColor(miIndexedPtr pIndexed,Pixel * pixels,int num,int red,int green,int blue)174 FindBestColor(miIndexedPtr pIndexed, Pixel * pixels, int num,
175               int red, int green, int blue)
176 {
177     Pixel best = pixels[0];
178     int bestDist = 1 << 30;
179     int dist;
180     int dr, dg, db;
181 
182     while (num--) {
183         Pixel pixel = *pixels++;
184         CARD32 v = pIndexed->rgba[pixel];
185 
186         dr = ((v >> 19) & 0x1f);
187         dg = ((v >> 11) & 0x1f);
188         db = ((v >> 3) & 0x1f);
189         dr = dr - red;
190         dg = dg - green;
191         db = db - blue;
192         dist = dr * dr + dg * dg + db * db;
193         if (dist < bestDist) {
194             bestDist = dist;
195             best = pixel;
196         }
197     }
198     return best;
199 }
200 
201 /* 0 <= gray < 32768 */
202 static Pixel
FindBestGray(miIndexedPtr pIndexed,Pixel * pixels,int num,int gray)203 FindBestGray(miIndexedPtr pIndexed, Pixel * pixels, int num, int gray)
204 {
205     Pixel best = pixels[0];
206     int bestDist = 1 << 30;
207     int dist;
208     int dr;
209     int r;
210 
211     while (num--) {
212         Pixel pixel = *pixels++;
213         CARD32 v = pIndexed->rgba[pixel];
214 
215         r = v & 0xff;
216         r = r | (r << 8);
217         dr = gray - (r >> 1);
218         dist = dr * dr;
219         if (dist < bestDist) {
220             bestDist = dist;
221             best = pixel;
222         }
223     }
224     return best;
225 }
226 
227 Bool
miInitIndexed(ScreenPtr pScreen,PictFormatPtr pFormat)228 miInitIndexed(ScreenPtr pScreen, PictFormatPtr pFormat)
229 {
230     ColormapPtr pColormap = pFormat->index.pColormap;
231     VisualPtr pVisual = pColormap->pVisual;
232     miIndexedPtr pIndexed;
233     Pixel pixels[MI_MAX_INDEXED];
234     xrgb rgb[MI_MAX_INDEXED];
235     int num;
236     int i;
237     Pixel p, r, g, b;
238 
239     if (pVisual->ColormapEntries > MI_MAX_INDEXED)
240         return FALSE;
241 
242     if (pVisual->class & DynamicClass) {
243         if (!miBuildRenderColormap(pColormap, pixels, &num))
244             return FALSE;
245     }
246     else {
247         num = pVisual->ColormapEntries;
248         for (p = 0; p < num; p++)
249             pixels[p] = p;
250     }
251 
252     pIndexed = malloc(sizeof(miIndexedRec));
253     if (!pIndexed)
254         return FALSE;
255 
256     pFormat->index.nvalues = num;
257     pFormat->index.pValues = xallocarray(num, sizeof(xIndexValue));
258     if (!pFormat->index.pValues) {
259         free(pIndexed);
260         return FALSE;
261     }
262 
263     /*
264      * Build mapping from pixel value to ARGB
265      */
266     QueryColors(pColormap, num, pixels, rgb, serverClient);
267     for (i = 0; i < num; i++) {
268         p = pixels[i];
269         pFormat->index.pValues[i].pixel = p;
270         pFormat->index.pValues[i].red = rgb[i].red;
271         pFormat->index.pValues[i].green = rgb[i].green;
272         pFormat->index.pValues[i].blue = rgb[i].blue;
273         pFormat->index.pValues[i].alpha = 0xffff;
274         pIndexed->rgba[p] = (0xff000000 |
275                              ((rgb[i].red & 0xff00) << 8) |
276                              ((rgb[i].green & 0xff00)) |
277                              ((rgb[i].blue & 0xff00) >> 8));
278     }
279 
280     /*
281      * Build mapping from RGB to pixel value.  This could probably be
282      * done a bit quicker...
283      */
284     switch (pVisual->class | DynamicClass) {
285     case GrayScale:
286         pIndexed->color = FALSE;
287         for (r = 0; r < 32768; r++)
288             pIndexed->ent[r] = FindBestGray(pIndexed, pixels, num, r);
289         break;
290     case PseudoColor:
291         pIndexed->color = TRUE;
292         p = 0;
293         for (r = 0; r < 32; r++)
294             for (g = 0; g < 32; g++)
295                 for (b = 0; b < 32; b++) {
296                     pIndexed->ent[p] = FindBestColor(pIndexed, pixels, num,
297                                                      r, g, b);
298                     p++;
299                 }
300         break;
301     }
302     pFormat->index.devPrivate = pIndexed;
303     return TRUE;
304 }
305 
306 void
miCloseIndexed(ScreenPtr pScreen,PictFormatPtr pFormat)307 miCloseIndexed(ScreenPtr pScreen, PictFormatPtr pFormat)
308 {
309     free(pFormat->index.devPrivate);
310     pFormat->index.devPrivate = NULL;
311     free(pFormat->index.pValues);
312     pFormat->index.pValues = NULL;
313 }
314 
315 void
miUpdateIndexed(ScreenPtr pScreen,PictFormatPtr pFormat,int ndef,xColorItem * pdef)316 miUpdateIndexed(ScreenPtr pScreen,
317                 PictFormatPtr pFormat, int ndef, xColorItem * pdef)
318 {
319     miIndexedPtr pIndexed = pFormat->index.devPrivate;
320 
321     if (pIndexed) {
322         while (ndef--) {
323             pIndexed->rgba[pdef->pixel] = (0xff000000 |
324                                            ((pdef->red & 0xff00) << 8) |
325                                            ((pdef->green & 0xff00)) |
326                                            ((pdef->blue & 0xff00) >> 8));
327             pdef++;
328         }
329     }
330 }
331 
332 #endif                          /* _MIINDEX_H_ */
333