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        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 */
173static Pixel
174FindBestColor(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 */
202static Pixel
203FindBestGray(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
227Bool
228miInitIndexed(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
306void
307miCloseIndexed(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
315void
316miUpdateIndexed(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