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	(sizeof(glyphHashSets)/sizeof(glyphHashSets[0]))
82
83static const CARD8	glyphDepths[GlyphFormatNum] = { 1, 4, 8, 16, 32 };
84
85static GlyphHashRec	globalGlyphs[GlyphFormatNum];
86
87void
88GlyphUninit (ScreenPtr pScreen)
89{
90    PictureScreenPtr ps = GetPictureScreen (pScreen);
91    GlyphPtr	     glyph;
92    int		     fdepth, i;
93    int		     scrno = pScreen->myNum;
94
95    for (fdepth = 0; fdepth < GlyphFormatNum; fdepth++)
96    {
97	if (!globalGlyphs[fdepth].hashSet)
98	    continue;
99
100	for (i = 0; i < globalGlyphs[fdepth].hashSet->size; i++)
101	{
102	    glyph = globalGlyphs[fdepth].table[i].glyph;
103	    if (glyph && glyph != DeletedGlyph)
104	    {
105		if (GlyphPicture(glyph)[scrno])
106		{
107		    FreePicture ((pointer) GlyphPicture (glyph)[scrno], 0);
108		    GlyphPicture(glyph)[scrno] = NULL;
109		}
110		(*ps->UnrealizeGlyph) (pScreen, glyph);
111	    }
112	}
113    }
114}
115
116GlyphHashSetPtr
117FindGlyphHashSet (CARD32 filled)
118{
119    int	i;
120
121    for (i = 0; i < NGLYPHHASHSETS; i++)
122	if (glyphHashSets[i].entries >= filled)
123	    return &glyphHashSets[i];
124    return 0;
125}
126
127GlyphRefPtr
128FindGlyphRef (GlyphHashPtr	hash,
129	      CARD32		signature,
130	      Bool		match,
131	      unsigned char	sha1[20])
132{
133    CARD32	elt, step, s;
134    GlyphPtr	glyph;
135    GlyphRefPtr	table, gr, del;
136    CARD32	tableSize = hash->hashSet->size;
137
138    table = hash->table;
139    elt = signature % tableSize;
140    step = 0;
141    del = 0;
142    for (;;)
143    {
144	gr = &table[elt];
145	s = gr->signature;
146	glyph = gr->glyph;
147	if (!glyph)
148	{
149	    if (del)
150		gr = del;
151	    break;
152	}
153	if (glyph == DeletedGlyph)
154	{
155	    if (!del)
156		del = gr;
157	    else if (gr == del)
158		break;
159	}
160	else if (s == signature &&
161		 (!match ||
162		  memcmp (glyph->sha1, sha1, 20) == 0))
163	{
164	    break;
165	}
166	if (!step)
167	{
168	    step = signature % hash->hashSet->rehash;
169	    if (!step)
170		step = 1;
171	}
172	elt += step;
173	if (elt >= tableSize)
174	    elt -= tableSize;
175    }
176    return gr;
177}
178
179int
180HashGlyph (xGlyphInfo    *gi,
181	   CARD8	 *bits,
182	   unsigned long size,
183	   unsigned char sha1[20])
184{
185    void *ctx = x_sha1_init();
186    int success;
187
188    if (!ctx)
189	return BadAlloc;
190
191    success = x_sha1_update(ctx, gi, sizeof(xGlyphInfo));
192    if (!success)
193	return BadAlloc;
194    success = x_sha1_update(ctx, bits, size);
195    if (!success)
196	return BadAlloc;
197    success = x_sha1_final(ctx, sha1);
198    if (!success)
199	return BadAlloc;
200    return Success;
201}
202
203GlyphPtr
204FindGlyphByHash (unsigned char sha1[20], int format)
205{
206    GlyphRefPtr gr;
207    CARD32 signature = *(CARD32 *) sha1;
208
209    if (!globalGlyphs[format].hashSet)
210	return NULL;
211
212    gr = FindGlyphRef (&globalGlyphs[format],
213		       signature, TRUE, sha1);
214
215    if (gr->glyph && gr->glyph != DeletedGlyph)
216	return gr->glyph;
217    else
218	return NULL;
219}
220
221#ifdef CHECK_DUPLICATES
222void
223DuplicateRef (GlyphPtr glyph, char *where)
224{
225    ErrorF ("Duplicate Glyph 0x%x from %s\n", glyph, where);
226}
227
228void
229CheckDuplicates (GlyphHashPtr hash, char *where)
230{
231    GlyphPtr	g;
232    int		i, j;
233
234    for (i = 0; i < hash->hashSet->size; i++)
235    {
236	g = hash->table[i].glyph;
237	if (!g || g == DeletedGlyph)
238	    continue;
239	for (j = i + 1; j < hash->hashSet->size; j++)
240	    if (hash->table[j].glyph == g)
241		DuplicateRef (g, where);
242    }
243}
244#else
245#define CheckDuplicates(a,b)
246#define DuplicateRef(a,b)
247#endif
248
249static void
250FreeGlyphPicture(GlyphPtr glyph)
251{
252    PictureScreenPtr ps;
253    int i;
254
255    for (i = 0; i < screenInfo.numScreens; i++)
256    {
257        ScreenPtr pScreen = screenInfo.screens[i];
258
259        if (GlyphPicture(glyph)[i])
260            FreePicture ((pointer) GlyphPicture (glyph)[i], 0);
261
262        ps = GetPictureScreenIfSet (pScreen);
263        if (ps)
264            (*ps->UnrealizeGlyph) (pScreen, glyph);
265    }
266}
267
268
269void
270FreeGlyph (GlyphPtr glyph, int format)
271{
272    CheckDuplicates (&globalGlyphs[format], "FreeGlyph");
273    if (--glyph->refcnt == 0)
274    {
275	GlyphRefPtr      gr;
276	int	         i;
277	int	         first;
278	CARD32		 signature;
279
280	first = -1;
281	for (i = 0; i < globalGlyphs[format].hashSet->size; i++)
282	    if (globalGlyphs[format].table[i].glyph == glyph)
283	    {
284		if (first != -1)
285		    DuplicateRef (glyph, "FreeGlyph check");
286		first = i;
287	    }
288
289	signature = *(CARD32 *) glyph->sha1;
290	gr = FindGlyphRef (&globalGlyphs[format], signature,
291			   TRUE, glyph->sha1);
292	if (gr - globalGlyphs[format].table != first)
293	    DuplicateRef (glyph, "Found wrong one");
294	if (gr->glyph && gr->glyph != DeletedGlyph)
295	{
296	    gr->glyph = DeletedGlyph;
297	    gr->signature = 0;
298	    globalGlyphs[format].tableEntries--;
299	}
300
301	FreeGlyphPicture(glyph);
302	dixFreeObjectWithPrivates(glyph, PRIVATE_GLYPH);
303    }
304}
305
306void
307AddGlyph (GlyphSetPtr glyphSet, GlyphPtr glyph, Glyph id)
308{
309    GlyphRefPtr	    gr;
310    CARD32	    signature;
311
312    CheckDuplicates (&globalGlyphs[glyphSet->fdepth], "AddGlyph top global");
313    /* Locate existing matching glyph */
314    signature = *(CARD32 *) glyph->sha1;
315    gr = FindGlyphRef (&globalGlyphs[glyphSet->fdepth], signature,
316		       TRUE, glyph->sha1);
317    if (gr->glyph && gr->glyph != DeletedGlyph && gr->glyph != glyph)
318    {
319	FreeGlyphPicture(glyph);
320	dixFreeObjectWithPrivates(glyph, PRIVATE_GLYPH);
321	glyph = gr->glyph;
322    }
323    else if (gr->glyph != glyph)
324    {
325	gr->glyph = glyph;
326	gr->signature = signature;
327	globalGlyphs[glyphSet->fdepth].tableEntries++;
328    }
329
330    /* Insert/replace glyphset value */
331    gr = FindGlyphRef (&glyphSet->hash, id, FALSE, 0);
332    ++glyph->refcnt;
333    if (gr->glyph && gr->glyph != DeletedGlyph)
334	FreeGlyph (gr->glyph, glyphSet->fdepth);
335    else
336	glyphSet->hash.tableEntries++;
337    gr->glyph = glyph;
338    gr->signature = id;
339    CheckDuplicates (&globalGlyphs[glyphSet->fdepth], "AddGlyph bottom");
340}
341
342Bool
343DeleteGlyph (GlyphSetPtr glyphSet, Glyph id)
344{
345    GlyphRefPtr     gr;
346    GlyphPtr	    glyph;
347
348    gr = FindGlyphRef (&glyphSet->hash, id, FALSE, 0);
349    glyph = gr->glyph;
350    if (glyph && glyph != DeletedGlyph)
351    {
352	gr->glyph = DeletedGlyph;
353	glyphSet->hash.tableEntries--;
354	FreeGlyph (glyph, glyphSet->fdepth);
355	return TRUE;
356    }
357    return FALSE;
358}
359
360GlyphPtr
361FindGlyph (GlyphSetPtr glyphSet, Glyph id)
362{
363    GlyphPtr        glyph;
364
365    glyph = FindGlyphRef (&glyphSet->hash, id, FALSE, 0)->glyph;
366    if (glyph == DeletedGlyph)
367	glyph = 0;
368    return glyph;
369}
370
371GlyphPtr
372AllocateGlyph (xGlyphInfo *gi, int fdepth)
373{
374    PictureScreenPtr ps;
375    int		     size;
376    GlyphPtr	     glyph;
377    int		     i;
378    int		     head_size;
379
380    head_size = sizeof (GlyphRec) + screenInfo.numScreens * sizeof (PicturePtr);
381    size = (head_size + dixPrivatesSize(PRIVATE_GLYPH));
382    glyph = (GlyphPtr) malloc (size);
383    if (!glyph)
384	return 0;
385    glyph->refcnt = 0;
386    glyph->size = size + sizeof (xGlyphInfo);
387    glyph->info = *gi;
388    dixInitPrivates(glyph, (char *) glyph + head_size, PRIVATE_GLYPH);
389
390    for (i = 0; i < screenInfo.numScreens; i++)
391    {
392	GlyphPicture(glyph)[i] = NULL;
393	ps = GetPictureScreenIfSet (screenInfo.screens[i]);
394
395	if (ps)
396	{
397	    if (!(*ps->RealizeGlyph) (screenInfo.screens[i], glyph))
398		goto bail;
399	}
400    }
401
402    return glyph;
403
404bail:
405    while (i--)
406    {
407	ps = GetPictureScreenIfSet (screenInfo.screens[i]);
408	if (ps)
409	    (*ps->UnrealizeGlyph) (screenInfo.screens[i], glyph);
410    }
411
412    dixFreeObjectWithPrivates(glyph, PRIVATE_GLYPH);
413    return 0;
414}
415
416Bool
417AllocateGlyphHash (GlyphHashPtr hash, GlyphHashSetPtr hashSet)
418{
419    hash->table = calloc(hashSet->size, sizeof (GlyphRefRec));
420    if (!hash->table)
421	return FALSE;
422    hash->hashSet = hashSet;
423    hash->tableEntries = 0;
424    return TRUE;
425}
426
427Bool
428ResizeGlyphHash (GlyphHashPtr hash, CARD32 change, Bool global)
429{
430    CARD32	    tableEntries;
431    GlyphHashSetPtr hashSet;
432    GlyphHashRec    newHash;
433    GlyphRefPtr	    gr;
434    GlyphPtr	    glyph;
435    int		    i;
436    int		    oldSize;
437    CARD32	    s;
438
439    tableEntries = hash->tableEntries + change;
440    hashSet = FindGlyphHashSet (tableEntries);
441    if (hashSet == hash->hashSet)
442	return TRUE;
443    if (global)
444	CheckDuplicates (hash, "ResizeGlyphHash top");
445    if (!AllocateGlyphHash (&newHash, hashSet))
446	return FALSE;
447    if (hash->table)
448    {
449	oldSize = hash->hashSet->size;
450	for (i = 0; i < oldSize; i++)
451	{
452	    glyph = hash->table[i].glyph;
453	    if (glyph && glyph != DeletedGlyph)
454	    {
455		s = hash->table[i].signature;
456		gr = FindGlyphRef (&newHash, s, global, glyph->sha1);
457		gr->signature = s;
458		gr->glyph = glyph;
459		++newHash.tableEntries;
460	    }
461	}
462	free(hash->table);
463    }
464    *hash = newHash;
465    if (global)
466	CheckDuplicates (hash, "ResizeGlyphHash bottom");
467    return TRUE;
468}
469
470Bool
471ResizeGlyphSet (GlyphSetPtr glyphSet, CARD32 change)
472{
473    return (ResizeGlyphHash (&glyphSet->hash, change, FALSE) &&
474	    ResizeGlyphHash (&globalGlyphs[glyphSet->fdepth], change, TRUE));
475}
476
477GlyphSetPtr
478AllocateGlyphSet (int fdepth, PictFormatPtr format)
479{
480    GlyphSetPtr	glyphSet;
481
482    if (!globalGlyphs[fdepth].hashSet)
483    {
484	if (!AllocateGlyphHash (&globalGlyphs[fdepth], &glyphHashSets[0]))
485	    return FALSE;
486    }
487
488    glyphSet = dixAllocateObjectWithPrivates(GlyphSetRec, PRIVATE_GLYPHSET);
489    if (!glyphSet)
490	return FALSE;
491
492    if (!AllocateGlyphHash (&glyphSet->hash, &glyphHashSets[0]))
493    {
494	free(glyphSet);
495	return FALSE;
496    }
497    glyphSet->refcnt = 1;
498    glyphSet->fdepth = fdepth;
499    glyphSet->format = format;
500    return glyphSet;
501}
502
503int
504FreeGlyphSet (pointer	value,
505	      XID       gid)
506{
507    GlyphSetPtr	glyphSet = (GlyphSetPtr) value;
508
509    if (--glyphSet->refcnt == 0)
510    {
511	CARD32	    i, tableSize = glyphSet->hash.hashSet->size;
512	GlyphRefPtr table = glyphSet->hash.table;
513	GlyphPtr    glyph;
514
515	for (i = 0; i < tableSize; i++)
516	{
517	    glyph = table[i].glyph;
518	    if (glyph && glyph != DeletedGlyph)
519		FreeGlyph (glyph, glyphSet->fdepth);
520	}
521	if (!globalGlyphs[glyphSet->fdepth].tableEntries)
522	{
523	    free(globalGlyphs[glyphSet->fdepth].table);
524	    globalGlyphs[glyphSet->fdepth].table = 0;
525	    globalGlyphs[glyphSet->fdepth].hashSet = 0;
526	}
527	else
528	    ResizeGlyphHash (&globalGlyphs[glyphSet->fdepth], 0, TRUE);
529	free(table);
530	dixFreeObjectWithPrivates(glyphSet, PRIVATE_GLYPHSET);
531    }
532    return Success;
533}
534
535static void
536GlyphExtents (int		nlist,
537		GlyphListPtr	list,
538		GlyphPtr	*glyphs,
539		BoxPtr		extents)
540{
541    int		x1, x2, y1, y2;
542    int		n;
543    GlyphPtr	glyph;
544    int		x, y;
545
546    x = 0;
547    y = 0;
548    extents->x1 = MAXSHORT;
549    extents->x2 = MINSHORT;
550    extents->y1 = MAXSHORT;
551    extents->y2 = MINSHORT;
552    while (nlist--)
553    {
554	x += list->xOff;
555	y += list->yOff;
556	n = list->len;
557	list++;
558	while (n--)
559	{
560	    glyph = *glyphs++;
561	    x1 = x - glyph->info.x;
562	    if (x1 < MINSHORT)
563		x1 = MINSHORT;
564	    y1 = y - glyph->info.y;
565	    if (y1 < MINSHORT)
566		y1 = MINSHORT;
567	    x2 = x1 + glyph->info.width;
568	    if (x2 > MAXSHORT)
569		x2 = MAXSHORT;
570	    y2 = y1 + glyph->info.height;
571	    if (y2 > MAXSHORT)
572		y2 = MAXSHORT;
573	    if (x1 < extents->x1)
574		extents->x1 = x1;
575	    if (x2 > extents->x2)
576		extents->x2 = x2;
577	    if (y1 < extents->y1)
578		extents->y1 = y1;
579	    if (y2 > extents->y2)
580		extents->y2 = y2;
581	    x += glyph->info.xOff;
582	    y += glyph->info.yOff;
583	}
584    }
585}
586
587#define NeedsComponent(f) (PICT_FORMAT_A(f) != 0 && PICT_FORMAT_RGB(f) != 0)
588
589void
590CompositeGlyphs (CARD8		op,
591		 PicturePtr	pSrc,
592		 PicturePtr	pDst,
593		 PictFormatPtr	maskFormat,
594		 INT16		xSrc,
595		 INT16		ySrc,
596		 int		nlist,
597		 GlyphListPtr	lists,
598		 GlyphPtr	*glyphs)
599{
600    PictureScreenPtr	ps = GetPictureScreen(pDst->pDrawable->pScreen);
601
602    ValidatePicture (pSrc);
603    ValidatePicture (pDst);
604    (*ps->Glyphs) (op, pSrc, pDst, maskFormat, xSrc, ySrc, nlist, lists, glyphs);
605}
606
607Bool
608miRealizeGlyph (ScreenPtr pScreen,
609		GlyphPtr  glyph)
610{
611    return TRUE;
612}
613
614void
615miUnrealizeGlyph (ScreenPtr pScreen,
616		  GlyphPtr  glyph)
617{
618}
619
620void
621miGlyphs (CARD8		op,
622	  PicturePtr	pSrc,
623	  PicturePtr	pDst,
624	  PictFormatPtr	maskFormat,
625	  INT16		xSrc,
626	  INT16		ySrc,
627	  int		nlist,
628	  GlyphListPtr	list,
629	  GlyphPtr	*glyphs)
630{
631    PicturePtr	pPicture;
632    PixmapPtr   pMaskPixmap = 0;
633    PicturePtr  pMask;
634    ScreenPtr   pScreen = pDst->pDrawable->pScreen;
635    int		width = 0, height = 0;
636    int		x, y;
637    int		xDst = list->xOff, yDst = list->yOff;
638    int		n;
639    GlyphPtr	glyph;
640    int		error;
641    BoxRec	extents = {0, 0, 0, 0};
642    CARD32	component_alpha;
643
644    if (maskFormat)
645    {
646	GCPtr	    pGC;
647	xRectangle  rect;
648
649	GlyphExtents (nlist, list, glyphs, &extents);
650
651	if (extents.x2 <= extents.x1 || extents.y2 <= extents.y1)
652	    return;
653	width = extents.x2 - extents.x1;
654	height = extents.y2 - extents.y1;
655	pMaskPixmap = (*pScreen->CreatePixmap) (pScreen, width, height,
656						maskFormat->depth,
657						CREATE_PIXMAP_USAGE_SCRATCH);
658	if (!pMaskPixmap)
659	    return;
660	component_alpha = NeedsComponent(maskFormat->format);
661	pMask = CreatePicture (0, &pMaskPixmap->drawable,
662			       maskFormat, CPComponentAlpha, &component_alpha,
663			       serverClient, &error);
664	if (!pMask)
665	{
666	    (*pScreen->DestroyPixmap) (pMaskPixmap);
667	    return;
668	}
669	pGC = GetScratchGC (pMaskPixmap->drawable.depth, pScreen);
670	ValidateGC (&pMaskPixmap->drawable, pGC);
671	rect.x = 0;
672	rect.y = 0;
673	rect.width = width;
674	rect.height = height;
675	(*pGC->ops->PolyFillRect) (&pMaskPixmap->drawable, pGC, 1, &rect);
676	FreeScratchGC (pGC);
677	x = -extents.x1;
678	y = -extents.y1;
679    }
680    else
681    {
682	pMask = pDst;
683	x = 0;
684	y = 0;
685    }
686    while (nlist--)
687    {
688	x += list->xOff;
689	y += list->yOff;
690	n = list->len;
691	while (n--)
692	{
693	    glyph = *glyphs++;
694	    pPicture = GlyphPicture (glyph)[pScreen->myNum];
695
696	    if (pPicture)
697	    {
698		if (maskFormat)
699		{
700			CompositePicture (PictOpAdd,
701					  pPicture,
702					  None,
703					  pMask,
704					  0, 0,
705					  0, 0,
706					  x - glyph->info.x,
707					  y - glyph->info.y,
708					  glyph->info.width,
709					  glyph->info.height);
710		}
711		else
712		{
713		    CompositePicture (op,
714				      pSrc,
715				      pPicture,
716				      pDst,
717				      xSrc + (x - glyph->info.x) - xDst,
718				      ySrc + (y - glyph->info.y) - yDst,
719				      0, 0,
720				      x - glyph->info.x,
721				      y - glyph->info.y,
722				      glyph->info.width,
723				      glyph->info.height);
724		}
725	    }
726
727	    x += glyph->info.xOff;
728	    y += glyph->info.yOff;
729	}
730	list++;
731    }
732    if (maskFormat)
733    {
734	x = extents.x1;
735	y = extents.y1;
736	CompositePicture (op,
737			  pSrc,
738			  pMask,
739			  pDst,
740			  xSrc + x - xDst,
741			  ySrc + y - yDst,
742			  0, 0,
743			  x, y,
744			  width, height);
745	FreePicture ((pointer) pMask, (XID) 0);
746	(*pScreen->DestroyPixmap) (pMaskPixmap);
747    }
748}
749