glyph.c revision 875c6e4f 
1/*
2 *
3 * Copyright © 2000 SuSE, 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 SuSE not be used in advertising or
10 * publicity pertaining to distribution of the software without specific,
11 * written prior permission.  SuSE makes no representations about the
12 * suitability of this software for any purpose.  It is provided "as is"
13 * without express or implied warranty.
14 *
15 * SuSE DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL SuSE
17 * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
18 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
19 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
20 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 *
22 * Author:  Keith Packard, SuSE, Inc.
23 */
24
25#ifdef HAVE_DIX_CONFIG_H
26#include <dix-config.h>
27#endif
28
29#include "xsha1.h"
30
31#include "misc.h"
32#include "scrnintstr.h"
33#include "os.h"
34#include "regionstr.h"
35#include "validate.h"
36#include "windowstr.h"
37#include "input.h"
38#include "resource.h"
39#include "colormapst.h"
40#include "cursorstr.h"
41#include "dixstruct.h"
42#include "gcstruct.h"
43#include "servermd.h"
44#include "picturestr.h"
45#include "glyphstr.h"
46#include "mipict.h"
47
48/*
49 * From Knuth -- a good choice for hash/rehash values is p, p-2 where
50 * p and p-2 are both prime.  These tables are sized to have an extra 10%
51 * free to avoid exponential performance degradation as the hash table fills
52 */
53static GlyphHashSetRec glyphHashSets[] = {
54    {32, 43, 41},
55    {64, 73, 71},
56    {128, 151, 149},
57    {256, 283, 281},
58    {512, 571, 569},
59    {1024, 1153, 1151},
60    {2048, 2269, 2267},
61    {4096, 4519, 4517},
62    {8192, 9013, 9011},
63    {16384, 18043, 18041},
64    {32768, 36109, 36107},
65    {65536, 72091, 72089},
66    {131072, 144409, 144407},
67    {262144, 288361, 288359},
68    {524288, 576883, 576881},
69    {1048576, 1153459, 1153457},
70    {2097152, 2307163, 2307161},
71    {4194304, 4613893, 4613891},
72    {8388608, 9227641, 9227639},
73    {16777216, 18455029, 18455027},
74    {33554432, 36911011, 36911009},
75    {67108864, 73819861, 73819859},
76    {134217728, 147639589, 147639587},
77    {268435456, 295279081, 295279079},
78    {536870912, 590559793, 590559791}
79};
80
81#define NGLYPHHASHSETS	ARRAY_SIZE(glyphHashSets)
82
83static GlyphHashRec globalGlyphs[GlyphFormatNum];
84
85void
86GlyphUninit(ScreenPtr pScreen)
87{
88    PictureScreenPtr ps = GetPictureScreen(pScreen);
89    GlyphPtr glyph;
90    int fdepth, i;
91
92    for (fdepth = 0; fdepth < GlyphFormatNum; fdepth++) {
93        if (!globalGlyphs[fdepth].hashSet)
94            continue;
95
96        for (i = 0; i < globalGlyphs[fdepth].hashSet->size; i++) {
97            glyph = globalGlyphs[fdepth].table[i].glyph;
98            if (glyph && glyph != DeletedGlyph) {
99                if (GetGlyphPicture(glyph, pScreen)) {
100                    FreePicture((void *) GetGlyphPicture(glyph, pScreen), 0);
101                    SetGlyphPicture(glyph, pScreen, NULL);
102                }
103                (*ps->UnrealizeGlyph) (pScreen, glyph);
104            }
105        }
106    }
107}
108
109static GlyphHashSetPtr
110FindGlyphHashSet(CARD32 filled)
111{
112    int i;
113
114    for (i = 0; i < NGLYPHHASHSETS; i++)
115        if (glyphHashSets[i].entries >= filled)
116            return &glyphHashSets[i];
117    return 0;
118}
119
120static GlyphRefPtr
121FindGlyphRef(GlyphHashPtr hash,
122             CARD32 signature, Bool match, unsigned char sha1[20])
123{
124    CARD32 elt, step, s;
125    GlyphPtr glyph;
126    GlyphRefPtr table, gr, del;
127    CARD32 tableSize = hash->hashSet->size;
128
129    table = hash->table;
130    elt = signature % tableSize;
131    step = 0;
132    del = 0;
133    for (;;) {
134        gr = &table[elt];
135        s = gr->signature;
136        glyph = gr->glyph;
137        if (!glyph) {
138            if (del)
139                gr = del;
140            break;
141        }
142        if (glyph == DeletedGlyph) {
143            if (!del)
144                del = gr;
145            else if (gr == del)
146                break;
147        }
148        else if (s == signature &&
149                 (!match || memcmp(glyph->sha1, sha1, 20) == 0)) {
150            break;
151        }
152        if (!step) {
153            step = signature % hash->hashSet->rehash;
154            if (!step)
155                step = 1;
156        }
157        elt += step;
158        if (elt >= tableSize)
159            elt -= tableSize;
160    }
161    return gr;
162}
163
164int
165HashGlyph(xGlyphInfo * gi,
166          CARD8 *bits, unsigned long size, unsigned char sha1[20])
167{
168    void *ctx = x_sha1_init();
169    int success;
170
171    if (!ctx)
172        return BadAlloc;
173
174    success = x_sha1_update(ctx, gi, sizeof(xGlyphInfo));
175    if (!success)
176        return BadAlloc;
177    success = x_sha1_update(ctx, bits, size);
178    if (!success)
179        return BadAlloc;
180    success = x_sha1_final(ctx, sha1);
181    if (!success)
182        return BadAlloc;
183    return Success;
184}
185
186GlyphPtr
187FindGlyphByHash(unsigned char sha1[20], int format)
188{
189    GlyphRefPtr gr;
190    CARD32 signature = *(CARD32 *) sha1;
191
192    if (!globalGlyphs[format].hashSet)
193        return NULL;
194
195    gr = FindGlyphRef(&globalGlyphs[format], signature, TRUE, sha1);
196
197    if (gr->glyph && gr->glyph != DeletedGlyph)
198        return gr->glyph;
199    else
200        return NULL;
201}
202
203#ifdef CHECK_DUPLICATES
204void
205DuplicateRef(GlyphPtr glyph, char *where)
206{
207    ErrorF("Duplicate Glyph 0x%x from %s\n", glyph, where);
208}
209
210void
211CheckDuplicates(GlyphHashPtr hash, char *where)
212{
213    GlyphPtr g;
214    int i, j;
215
216    for (i = 0; i < hash->hashSet->size; i++) {
217        g = hash->table[i].glyph;
218        if (!g || g == DeletedGlyph)
219            continue;
220        for (j = i + 1; j < hash->hashSet->size; j++)
221            if (hash->table[j].glyph == g)
222                DuplicateRef(g, where);
223    }
224}
225#else
226#define CheckDuplicates(a,b)
227#define DuplicateRef(a,b)
228#endif
229
230static void
231FreeGlyphPicture(GlyphPtr glyph)
232{
233    PictureScreenPtr ps;
234    int i;
235
236    for (i = 0; i < screenInfo.numScreens; i++) {
237        ScreenPtr pScreen = screenInfo.screens[i];
238
239        if (GetGlyphPicture(glyph, pScreen))
240            FreePicture((void *) GetGlyphPicture(glyph, pScreen), 0);
241
242        ps = GetPictureScreenIfSet(pScreen);
243        if (ps)
244            (*ps->UnrealizeGlyph) (pScreen, glyph);
245    }
246}
247
248void
249FreeGlyph(GlyphPtr glyph, int format)
250{
251    CheckDuplicates(&globalGlyphs[format], "FreeGlyph");
252    BUG_RETURN(glyph->refcnt == 0);
253    if (--glyph->refcnt == 0) {
254        GlyphRefPtr gr;
255        int i;
256        int first;
257        CARD32 signature;
258
259        first = -1;
260        for (i = 0; i < globalGlyphs[format].hashSet->size; i++)
261            if (globalGlyphs[format].table[i].glyph == glyph) {
262                if (first != -1)
263                    DuplicateRef(glyph, "FreeGlyph check");
264                first = i;
265            }
266
267        signature = *(CARD32 *) glyph->sha1;
268        gr = FindGlyphRef(&globalGlyphs[format], signature, TRUE, glyph->sha1);
269        if (gr - globalGlyphs[format].table != first)
270            DuplicateRef(glyph, "Found wrong one");
271        if (gr->glyph && gr->glyph != DeletedGlyph) {
272            gr->glyph = DeletedGlyph;
273            gr->signature = 0;
274            globalGlyphs[format].tableEntries--;
275        }
276
277        FreeGlyphPicture(glyph);
278        dixFreeObjectWithPrivates(glyph, PRIVATE_GLYPH);
279    }
280}
281
282void
283AddGlyph(GlyphSetPtr glyphSet, GlyphPtr glyph, Glyph id)
284{
285    GlyphRefPtr gr;
286    CARD32 signature;
287
288    CheckDuplicates(&globalGlyphs[glyphSet->fdepth], "AddGlyph top global");
289    /* Locate existing matching glyph */
290    signature = *(CARD32 *) glyph->sha1;
291    gr = FindGlyphRef(&globalGlyphs[glyphSet->fdepth], signature,
292                      TRUE, glyph->sha1);
293    if (gr->glyph && gr->glyph != DeletedGlyph && gr->glyph != glyph) {
294        glyph = gr->glyph;
295    }
296    else if (gr->glyph != glyph) {
297        gr->glyph = glyph;
298        gr->signature = signature;
299        globalGlyphs[glyphSet->fdepth].tableEntries++;
300    }
301
302    /* Insert/replace glyphset value */
303    gr = FindGlyphRef(&glyphSet->hash, id, FALSE, 0);
304    ++glyph->refcnt;
305    if (gr->glyph && gr->glyph != DeletedGlyph)
306        FreeGlyph(gr->glyph, glyphSet->fdepth);
307    else
308        glyphSet->hash.tableEntries++;
309    gr->glyph = glyph;
310    gr->signature = id;
311    CheckDuplicates(&globalGlyphs[glyphSet->fdepth], "AddGlyph bottom");
312}
313
314Bool
315DeleteGlyph(GlyphSetPtr glyphSet, Glyph id)
316{
317    GlyphRefPtr gr;
318    GlyphPtr glyph;
319
320    gr = FindGlyphRef(&glyphSet->hash, id, FALSE, 0);
321    glyph = gr->glyph;
322    if (glyph && glyph != DeletedGlyph) {
323        gr->glyph = DeletedGlyph;
324        glyphSet->hash.tableEntries--;
325        FreeGlyph(glyph, glyphSet->fdepth);
326        return TRUE;
327    }
328    return FALSE;
329}
330
331GlyphPtr
332FindGlyph(GlyphSetPtr glyphSet, Glyph id)
333{
334    GlyphPtr glyph;
335
336    glyph = FindGlyphRef(&glyphSet->hash, id, FALSE, 0)->glyph;
337    if (glyph == DeletedGlyph)
338        glyph = 0;
339    return glyph;
340}
341
342GlyphPtr
343AllocateGlyph(xGlyphInfo * gi, int fdepth)
344{
345    PictureScreenPtr ps;
346    int size;
347    GlyphPtr glyph;
348    int i;
349    int head_size;
350
351    head_size = sizeof(GlyphRec) + screenInfo.numScreens * sizeof(PicturePtr);
352    size = (head_size + dixPrivatesSize(PRIVATE_GLYPH));
353    glyph = (GlyphPtr) malloc(size);
354    if (!glyph)
355        return 0;
356    glyph->refcnt = 1;
357    glyph->size = size + sizeof(xGlyphInfo);
358    glyph->info = *gi;
359    dixInitPrivates(glyph, (char *) glyph + head_size, PRIVATE_GLYPH);
360
361    for (i = 0; i < screenInfo.numScreens; i++) {
362        ScreenPtr pScreen = screenInfo.screens[i];
363        SetGlyphPicture(glyph, pScreen, NULL);
364        ps = GetPictureScreenIfSet(pScreen);
365
366        if (ps) {
367            if (!(*ps->RealizeGlyph) (pScreen, glyph))
368                goto bail;
369        }
370    }
371
372    return glyph;
373
374 bail:
375    while (i--) {
376        ps = GetPictureScreenIfSet(screenInfo.screens[i]);
377        if (ps)
378            (*ps->UnrealizeGlyph) (screenInfo.screens[i], glyph);
379    }
380
381    dixFreeObjectWithPrivates(glyph, PRIVATE_GLYPH);
382    return 0;
383}
384
385static Bool
386AllocateGlyphHash(GlyphHashPtr hash, GlyphHashSetPtr hashSet)
387{
388    hash->table = calloc(hashSet->size, sizeof(GlyphRefRec));
389    if (!hash->table)
390        return FALSE;
391    hash->hashSet = hashSet;
392    hash->tableEntries = 0;
393    return TRUE;
394}
395
396static Bool
397ResizeGlyphHash(GlyphHashPtr hash, CARD32 change, Bool global)
398{
399    CARD32 tableEntries;
400    GlyphHashSetPtr hashSet;
401    GlyphHashRec newHash;
402    GlyphRefPtr gr;
403    GlyphPtr glyph;
404    int i;
405    int oldSize;
406    CARD32 s;
407
408    tableEntries = hash->tableEntries + change;
409    hashSet = FindGlyphHashSet(tableEntries);
410    if (hashSet == hash->hashSet)
411        return TRUE;
412    if (global)
413        CheckDuplicates(hash, "ResizeGlyphHash top");
414    if (!AllocateGlyphHash(&newHash, hashSet))
415        return FALSE;
416    if (hash->table) {
417        oldSize = hash->hashSet->size;
418        for (i = 0; i < oldSize; i++) {
419            glyph = hash->table[i].glyph;
420            if (glyph && glyph != DeletedGlyph) {
421                s = hash->table[i].signature;
422                gr = FindGlyphRef(&newHash, s, global, glyph->sha1);
423
424                gr->signature = s;
425                gr->glyph = glyph;
426                ++newHash.tableEntries;
427            }
428        }
429        free(hash->table);
430    }
431    *hash = newHash;
432    if (global)
433        CheckDuplicates(hash, "ResizeGlyphHash bottom");
434    return TRUE;
435}
436
437Bool
438ResizeGlyphSet(GlyphSetPtr glyphSet, CARD32 change)
439{
440    return (ResizeGlyphHash(&glyphSet->hash, change, FALSE) &&
441            ResizeGlyphHash(&globalGlyphs[glyphSet->fdepth], change, TRUE));
442}
443
444GlyphSetPtr
445AllocateGlyphSet(int fdepth, PictFormatPtr format)
446{
447    GlyphSetPtr glyphSet;
448
449    if (!globalGlyphs[fdepth].hashSet) {
450        if (!AllocateGlyphHash(&globalGlyphs[fdepth], &glyphHashSets[0]))
451            return FALSE;
452    }
453
454    glyphSet = dixAllocateObjectWithPrivates(GlyphSetRec, PRIVATE_GLYPHSET);
455    if (!glyphSet)
456        return FALSE;
457
458    if (!AllocateGlyphHash(&glyphSet->hash, &glyphHashSets[0])) {
459        free(glyphSet);
460        return FALSE;
461    }
462    glyphSet->refcnt = 1;
463    glyphSet->fdepth = fdepth;
464    glyphSet->format = format;
465    return glyphSet;
466}
467
468int
469FreeGlyphSet(void *value, XID gid)
470{
471    GlyphSetPtr glyphSet = (GlyphSetPtr) value;
472
473    if (--glyphSet->refcnt == 0) {
474        CARD32 i, tableSize = glyphSet->hash.hashSet->size;
475        GlyphRefPtr table = glyphSet->hash.table;
476        GlyphPtr glyph;
477
478        for (i = 0; i < tableSize; i++) {
479            glyph = table[i].glyph;
480            if (glyph && glyph != DeletedGlyph)
481                FreeGlyph(glyph, glyphSet->fdepth);
482        }
483        if (!globalGlyphs[glyphSet->fdepth].tableEntries) {
484            free(globalGlyphs[glyphSet->fdepth].table);
485            globalGlyphs[glyphSet->fdepth].table = 0;
486            globalGlyphs[glyphSet->fdepth].hashSet = 0;
487        }
488        else
489            ResizeGlyphHash(&globalGlyphs[glyphSet->fdepth], 0, TRUE);
490        free(table);
491        dixFreeObjectWithPrivates(glyphSet, PRIVATE_GLYPHSET);
492    }
493    return Success;
494}
495
496static void
497GlyphExtents(int nlist, GlyphListPtr list, GlyphPtr * glyphs, BoxPtr extents)
498{
499    int x1, x2, y1, y2;
500    int n;
501    GlyphPtr glyph;
502    int x, y;
503
504    x = 0;
505    y = 0;
506    extents->x1 = MAXSHORT;
507    extents->x2 = MINSHORT;
508    extents->y1 = MAXSHORT;
509    extents->y2 = MINSHORT;
510    while (nlist--) {
511        x += list->xOff;
512        y += list->yOff;
513        n = list->len;
514        list++;
515        while (n--) {
516            glyph = *glyphs++;
517            x1 = x - glyph->info.x;
518            if (x1 < MINSHORT)
519                x1 = MINSHORT;
520            y1 = y - glyph->info.y;
521            if (y1 < MINSHORT)
522                y1 = MINSHORT;
523            x2 = x1 + glyph->info.width;
524            if (x2 > MAXSHORT)
525                x2 = MAXSHORT;
526            y2 = y1 + glyph->info.height;
527            if (y2 > MAXSHORT)
528                y2 = MAXSHORT;
529            if (x1 < extents->x1)
530                extents->x1 = x1;
531            if (x2 > extents->x2)
532                extents->x2 = x2;
533            if (y1 < extents->y1)
534                extents->y1 = y1;
535            if (y2 > extents->y2)
536                extents->y2 = y2;
537            x += glyph->info.xOff;
538            y += glyph->info.yOff;
539        }
540    }
541}
542
543#define NeedsComponent(f) (PICT_FORMAT_A(f) != 0 && PICT_FORMAT_RGB(f) != 0)
544
545void
546CompositeGlyphs(CARD8 op,
547                PicturePtr pSrc,
548                PicturePtr pDst,
549                PictFormatPtr maskFormat,
550                INT16 xSrc,
551                INT16 ySrc, int nlist, GlyphListPtr lists, GlyphPtr * glyphs)
552{
553    PictureScreenPtr ps = GetPictureScreen(pDst->pDrawable->pScreen);
554
555    ValidatePicture(pSrc);
556    ValidatePicture(pDst);
557    (*ps->Glyphs) (op, pSrc, pDst, maskFormat, xSrc, ySrc, nlist, lists,
558                   glyphs);
559}
560
561Bool
562miRealizeGlyph(ScreenPtr pScreen, GlyphPtr glyph)
563{
564    return TRUE;
565}
566
567void
568miUnrealizeGlyph(ScreenPtr pScreen, GlyphPtr glyph)
569{
570}
571
572void
573miGlyphs(CARD8 op,
574         PicturePtr pSrc,
575         PicturePtr pDst,
576         PictFormatPtr maskFormat,
577         INT16 xSrc,
578         INT16 ySrc, int nlist, GlyphListPtr list, GlyphPtr * glyphs)
579{
580    PicturePtr pPicture;
581    PixmapPtr pMaskPixmap = 0;
582    PicturePtr pMask;
583    ScreenPtr pScreen = pDst->pDrawable->pScreen;
584    int width = 0, height = 0;
585    int x, y;
586    int xDst = list->xOff, yDst = list->yOff;
587    int n;
588    GlyphPtr glyph;
589    int error;
590    BoxRec extents = { 0, 0, 0, 0 };
591    CARD32 component_alpha;
592
593    if (maskFormat) {
594        GCPtr pGC;
595        xRectangle rect;
596
597        GlyphExtents(nlist, list, glyphs, &extents);
598
599        if (extents.x2 <= extents.x1 || extents.y2 <= extents.y1)
600            return;
601        width = extents.x2 - extents.x1;
602        height = extents.y2 - extents.y1;
603        pMaskPixmap = (*pScreen->CreatePixmap) (pScreen, width, height,
604                                                maskFormat->depth,
605                                                CREATE_PIXMAP_USAGE_SCRATCH);
606        if (!pMaskPixmap)
607            return;
608        component_alpha = NeedsComponent(maskFormat->format);
609        pMask = CreatePicture(0, &pMaskPixmap->drawable,
610                              maskFormat, CPComponentAlpha, &component_alpha,
611                              serverClient, &error);
612        if (!pMask) {
613            (*pScreen->DestroyPixmap) (pMaskPixmap);
614            return;
615        }
616        pGC = GetScratchGC(pMaskPixmap->drawable.depth, pScreen);
617        ValidateGC(&pMaskPixmap->drawable, pGC);
618        rect.x = 0;
619        rect.y = 0;
620        rect.width = width;
621        rect.height = height;
622        (*pGC->ops->PolyFillRect) (&pMaskPixmap->drawable, pGC, 1, &rect);
623        FreeScratchGC(pGC);
624        x = -extents.x1;
625        y = -extents.y1;
626    }
627    else {
628        pMask = pDst;
629        x = 0;
630        y = 0;
631    }
632    while (nlist--) {
633        x += list->xOff;
634        y += list->yOff;
635        n = list->len;
636        while (n--) {
637            glyph = *glyphs++;
638            pPicture = GetGlyphPicture(glyph, pScreen);
639
640            if (pPicture) {
641                if (maskFormat) {
642                    CompositePicture(PictOpAdd,
643                                     pPicture,
644                                     None,
645                                     pMask,
646                                     0, 0,
647                                     0, 0,
648                                     x - glyph->info.x,
649                                     y - glyph->info.y,
650                                     glyph->info.width, glyph->info.height);
651                }
652                else {
653                    CompositePicture(op,
654                                     pSrc,
655                                     pPicture,
656                                     pDst,
657                                     xSrc + (x - glyph->info.x) - xDst,
658                                     ySrc + (y - glyph->info.y) - yDst,
659                                     0, 0,
660                                     x - glyph->info.x,
661                                     y - glyph->info.y,
662                                     glyph->info.width, glyph->info.height);
663                }
664            }
665
666            x += glyph->info.xOff;
667            y += glyph->info.yOff;
668        }
669        list++;
670    }
671    if (maskFormat) {
672        x = extents.x1;
673        y = extents.y1;
674        CompositePicture(op,
675                         pSrc,
676                         pMask,
677                         pDst,
678                         xSrc + x - xDst,
679                         ySrc + y - yDst, 0, 0, x, y, width, height);
680        FreePicture((void *) pMask, (XID) 0);
681        (*pScreen->DestroyPixmap) (pMaskPixmap);
682    }
683}
684
685PicturePtr GetGlyphPicture(GlyphPtr glyph, ScreenPtr pScreen)
686{
687    if (pScreen->isGPU)
688        return NULL;
689    return GlyphPicture(glyph)[pScreen->myNum];
690}
691
692void SetGlyphPicture(GlyphPtr glyph, ScreenPtr pScreen, PicturePtr picture)
693{
694    GlyphPicture(glyph)[pScreen->myNum] = picture;
695}
696