glyph.c revision 05b261ec
105b261ecSmrg/*
205b261ecSmrg *
305b261ecSmrg * Copyright © 2000 SuSE, Inc.
405b261ecSmrg *
505b261ecSmrg * Permission to use, copy, modify, distribute, and sell this software and its
605b261ecSmrg * documentation for any purpose is hereby granted without fee, provided that
705b261ecSmrg * the above copyright notice appear in all copies and that both that
805b261ecSmrg * copyright notice and this permission notice appear in supporting
905b261ecSmrg * documentation, and that the name of SuSE not be used in advertising or
1005b261ecSmrg * publicity pertaining to distribution of the software without specific,
1105b261ecSmrg * written prior permission.  SuSE makes no representations about the
1205b261ecSmrg * suitability of this software for any purpose.  It is provided "as is"
1305b261ecSmrg * without express or implied warranty.
1405b261ecSmrg *
1505b261ecSmrg * SuSE DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
1605b261ecSmrg * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL SuSE
1705b261ecSmrg * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
1805b261ecSmrg * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
1905b261ecSmrg * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
2005b261ecSmrg * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
2105b261ecSmrg *
2205b261ecSmrg * Author:  Keith Packard, SuSE, Inc.
2305b261ecSmrg */
2405b261ecSmrg
2505b261ecSmrg#ifdef HAVE_DIX_CONFIG_H
2605b261ecSmrg#include <dix-config.h>
2705b261ecSmrg#endif
2805b261ecSmrg
2905b261ecSmrg#include "misc.h"
3005b261ecSmrg#include "scrnintstr.h"
3105b261ecSmrg#include "os.h"
3205b261ecSmrg#include "regionstr.h"
3305b261ecSmrg#include "validate.h"
3405b261ecSmrg#include "windowstr.h"
3505b261ecSmrg#include "input.h"
3605b261ecSmrg#include "resource.h"
3705b261ecSmrg#include "colormapst.h"
3805b261ecSmrg#include "cursorstr.h"
3905b261ecSmrg#include "dixstruct.h"
4005b261ecSmrg#include "gcstruct.h"
4105b261ecSmrg#include "servermd.h"
4205b261ecSmrg#include "picturestr.h"
4305b261ecSmrg#include "glyphstr.h"
4405b261ecSmrg
4505b261ecSmrg#if HAVE_STDINT_H
4605b261ecSmrg#include <stdint.h>
4705b261ecSmrg#elif !defined(UINT32_MAX)
4805b261ecSmrg#define UINT32_MAX 0xffffffffU
4905b261ecSmrg#endif
5005b261ecSmrg
5105b261ecSmrg/*
5205b261ecSmrg * From Knuth -- a good choice for hash/rehash values is p, p-2 where
5305b261ecSmrg * p and p-2 are both prime.  These tables are sized to have an extra 10%
5405b261ecSmrg * free to avoid exponential performance degradation as the hash table fills
5505b261ecSmrg */
5605b261ecSmrgstatic GlyphHashSetRec glyphHashSets[] = {
5705b261ecSmrg    { 32,		43,		41        },
5805b261ecSmrg    { 64,		73,		71        },
5905b261ecSmrg    { 128,		151,		149       },
6005b261ecSmrg    { 256,		283,		281       },
6105b261ecSmrg    { 512,		571,		569       },
6205b261ecSmrg    { 1024,		1153,		1151      },
6305b261ecSmrg    { 2048,		2269,		2267      },
6405b261ecSmrg    { 4096,		4519,		4517      },
6505b261ecSmrg    { 8192,		9013,		9011      },
6605b261ecSmrg    { 16384,		18043,		18041     },
6705b261ecSmrg    { 32768,		36109,		36107     },
6805b261ecSmrg    { 65536,		72091,		72089     },
6905b261ecSmrg    { 131072,		144409,		144407    },
7005b261ecSmrg    { 262144,		288361,		288359    },
7105b261ecSmrg    { 524288,		576883,		576881    },
7205b261ecSmrg    { 1048576,		1153459,	1153457   },
7305b261ecSmrg    { 2097152,		2307163,	2307161   },
7405b261ecSmrg    { 4194304,		4613893,	4613891   },
7505b261ecSmrg    { 8388608,		9227641,	9227639   },
7605b261ecSmrg    { 16777216,		18455029,	18455027  },
7705b261ecSmrg    { 33554432,		36911011,	36911009  },
7805b261ecSmrg    { 67108864,		73819861,	73819859  },
7905b261ecSmrg    { 134217728,	147639589,	147639587 },
8005b261ecSmrg    { 268435456,	295279081,	295279079 },
8105b261ecSmrg    { 536870912,	590559793,	590559791 }
8205b261ecSmrg};
8305b261ecSmrg
8405b261ecSmrg#define NGLYPHHASHSETS	(sizeof(glyphHashSets)/sizeof(glyphHashSets[0]))
8505b261ecSmrg
8605b261ecSmrgstatic const CARD8	glyphDepths[GlyphFormatNum] = { 1, 4, 8, 16, 32 };
8705b261ecSmrg
8805b261ecSmrgstatic GlyphHashRec	globalGlyphs[GlyphFormatNum];
8905b261ecSmrg
9005b261ecSmrgstatic int	globalTotalGlyphPrivateSize = 0;
9105b261ecSmrg
9205b261ecSmrgstatic int	glyphPrivateCount = 0;
9305b261ecSmrg
9405b261ecSmrgvoid
9505b261ecSmrgResetGlyphPrivates (void)
9605b261ecSmrg{
9705b261ecSmrg    glyphPrivateCount = 0;
9805b261ecSmrg}
9905b261ecSmrg
10005b261ecSmrgint
10105b261ecSmrgAllocateGlyphPrivateIndex (void)
10205b261ecSmrg{
10305b261ecSmrg    return glyphPrivateCount++;
10405b261ecSmrg}
10505b261ecSmrg
10605b261ecSmrgBool
10705b261ecSmrgAllocateGlyphPrivate (ScreenPtr pScreen,
10805b261ecSmrg		      int	index2,
10905b261ecSmrg		      unsigned	amount)
11005b261ecSmrg{
11105b261ecSmrg    PictureScreenPtr ps;
11205b261ecSmrg    unsigned	     oldamount;
11305b261ecSmrg
11405b261ecSmrg    ps = GetPictureScreenIfSet (pScreen);
11505b261ecSmrg    if (!ps)
11605b261ecSmrg	return FALSE;
11705b261ecSmrg
11805b261ecSmrg    /* Round up sizes for proper alignment */
11905b261ecSmrg    amount = ((amount + (sizeof (DevUnion) - 1)) / sizeof (DevUnion)) *
12005b261ecSmrg	sizeof (DevUnion);
12105b261ecSmrg
12205b261ecSmrg    if (index2 >= ps->glyphPrivateLen)
12305b261ecSmrg    {
12405b261ecSmrg	unsigned *nsizes;
12505b261ecSmrg	nsizes = (unsigned *) xrealloc (ps->glyphPrivateSizes,
12605b261ecSmrg					(index2 + 1) * sizeof (unsigned));
12705b261ecSmrg	if (!nsizes)
12805b261ecSmrg	    return FALSE;
12905b261ecSmrg
13005b261ecSmrg	while (ps->glyphPrivateLen <= index2)
13105b261ecSmrg	{
13205b261ecSmrg	    nsizes[ps->glyphPrivateLen++] = 0;
13305b261ecSmrg	    ps->totalGlyphPrivateSize += sizeof (DevUnion);
13405b261ecSmrg	}
13505b261ecSmrg	ps->glyphPrivateSizes = nsizes;
13605b261ecSmrg    }
13705b261ecSmrg    oldamount = ps->glyphPrivateSizes[index2];
13805b261ecSmrg    if (amount > oldamount)
13905b261ecSmrg    {
14005b261ecSmrg	ps->glyphPrivateSizes[index2] = amount;
14105b261ecSmrg	ps->totalGlyphPrivateSize += (amount - oldamount);
14205b261ecSmrg    }
14305b261ecSmrg    ps->totalGlyphPrivateSize = BitmapBytePad (ps->totalGlyphPrivateSize * 8);
14405b261ecSmrg
14505b261ecSmrg    return TRUE;
14605b261ecSmrg}
14705b261ecSmrg
14805b261ecSmrgstatic void
14905b261ecSmrgSetGlyphScreenPrivateOffsets (void)
15005b261ecSmrg{
15105b261ecSmrg    PictureScreenPtr ps;
15205b261ecSmrg    int		     offset = 0;
15305b261ecSmrg    int		     i;
15405b261ecSmrg
15505b261ecSmrg    for (i = 0; i < screenInfo.numScreens; i++)
15605b261ecSmrg    {
15705b261ecSmrg	ps = GetPictureScreenIfSet (screenInfo.screens[i]);
15805b261ecSmrg	if (ps && ps->totalGlyphPrivateSize)
15905b261ecSmrg	{
16005b261ecSmrg	    ps->glyphPrivateOffset = offset;
16105b261ecSmrg	    offset += ps->totalGlyphPrivateSize / sizeof (DevUnion);
16205b261ecSmrg	}
16305b261ecSmrg    }
16405b261ecSmrg}
16505b261ecSmrg
16605b261ecSmrgstatic void
16705b261ecSmrgSetGlyphPrivatePointers (GlyphPtr glyph)
16805b261ecSmrg{
16905b261ecSmrg    PictureScreenPtr ps;
17005b261ecSmrg    int		     i;
17105b261ecSmrg    char	     *ptr;
17205b261ecSmrg    DevUnion         *ppriv;
17305b261ecSmrg    unsigned         *sizes;
17405b261ecSmrg    unsigned         size;
17505b261ecSmrg    int		     len;
17605b261ecSmrg
17705b261ecSmrg    for (i = 0; i < screenInfo.numScreens; i++)
17805b261ecSmrg    {
17905b261ecSmrg	ps = GetPictureScreenIfSet (screenInfo.screens[i]);
18005b261ecSmrg	if (ps && ps->totalGlyphPrivateSize)
18105b261ecSmrg	{
18205b261ecSmrg	    ppriv = glyph->devPrivates + ps->glyphPrivateOffset;
18305b261ecSmrg	    sizes = ps->glyphPrivateSizes;
18405b261ecSmrg	    ptr = (char *) (ppriv + ps->glyphPrivateLen);
18505b261ecSmrg	    for (len = ps->glyphPrivateLen; --len >= 0; ppriv++, sizes++)
18605b261ecSmrg	    {
18705b261ecSmrg		if ((size = *sizes) != 0)
18805b261ecSmrg		{
18905b261ecSmrg		    ppriv->ptr = (pointer) ptr;
19005b261ecSmrg		    ptr += size;
19105b261ecSmrg		}
19205b261ecSmrg		else
19305b261ecSmrg		    ppriv->ptr = (pointer) 0;
19405b261ecSmrg	    }
19505b261ecSmrg	}
19605b261ecSmrg    }
19705b261ecSmrg}
19805b261ecSmrg
19905b261ecSmrgstatic Bool
20005b261ecSmrgReallocGlobalGlyphPrivate (GlyphPtr glyph)
20105b261ecSmrg{
20205b261ecSmrg    PictureScreenPtr ps;
20305b261ecSmrg    DevUnion         *devPrivates;
20405b261ecSmrg    char	     *ptr;
20505b261ecSmrg    int		     i;
20605b261ecSmrg
20705b261ecSmrg    devPrivates = xalloc (globalTotalGlyphPrivateSize);
20805b261ecSmrg    if (!devPrivates)
20905b261ecSmrg	return FALSE;
21005b261ecSmrg
21105b261ecSmrg    ptr = (char *) devPrivates;
21205b261ecSmrg    for (i = 0; i < screenInfo.numScreens; i++)
21305b261ecSmrg    {
21405b261ecSmrg	ps = GetPictureScreenIfSet (screenInfo.screens[i]);
21505b261ecSmrg	if (ps && ps->totalGlyphPrivateSize)
21605b261ecSmrg	{
21705b261ecSmrg	    if (ps->glyphPrivateOffset != -1)
21805b261ecSmrg	    {
21905b261ecSmrg		memcpy (ptr, glyph->devPrivates + ps->glyphPrivateOffset,
22005b261ecSmrg			ps->totalGlyphPrivateSize);
22105b261ecSmrg	    }
22205b261ecSmrg	    else if (ps->totalGlyphPrivateSize)
22305b261ecSmrg	    {
22405b261ecSmrg		memset (ptr, 0, ps->totalGlyphPrivateSize);
22505b261ecSmrg	    }
22605b261ecSmrg
22705b261ecSmrg	    ptr += ps->totalGlyphPrivateSize;
22805b261ecSmrg	}
22905b261ecSmrg    }
23005b261ecSmrg
23105b261ecSmrg    if (glyph->devPrivates)
23205b261ecSmrg	xfree (glyph->devPrivates);
23305b261ecSmrg
23405b261ecSmrg    glyph->devPrivates = devPrivates;
23505b261ecSmrg
23605b261ecSmrg    return TRUE;
23705b261ecSmrg}
23805b261ecSmrg
23905b261ecSmrgBool
24005b261ecSmrgGlyphInit (ScreenPtr pScreen)
24105b261ecSmrg{
24205b261ecSmrg    PictureScreenPtr ps = GetPictureScreen (pScreen);
24305b261ecSmrg
24405b261ecSmrg    ps->totalGlyphPrivateSize = 0;
24505b261ecSmrg    ps->glyphPrivateSizes = 0;
24605b261ecSmrg    ps->glyphPrivateLen = 0;
24705b261ecSmrg    ps->glyphPrivateOffset = -1;
24805b261ecSmrg
24905b261ecSmrg    return TRUE;
25005b261ecSmrg}
25105b261ecSmrg
25205b261ecSmrgBool
25305b261ecSmrgGlyphFinishInit (ScreenPtr pScreen)
25405b261ecSmrg{
25505b261ecSmrg    PictureScreenPtr ps = GetPictureScreen (pScreen);
25605b261ecSmrg
25705b261ecSmrg    if (ps->totalGlyphPrivateSize)
25805b261ecSmrg    {
25905b261ecSmrg	GlyphPtr glyph;
26005b261ecSmrg	int	 fdepth, i;
26105b261ecSmrg
26205b261ecSmrg	globalTotalGlyphPrivateSize += ps->totalGlyphPrivateSize;
26305b261ecSmrg
26405b261ecSmrg	for (fdepth = 0; fdepth < GlyphFormatNum; fdepth++)
26505b261ecSmrg	{
26605b261ecSmrg	    if (!globalGlyphs[fdepth].hashSet)
26705b261ecSmrg		continue;
26805b261ecSmrg
26905b261ecSmrg	    for (i = 0; i < globalGlyphs[fdepth].hashSet->size; i++)
27005b261ecSmrg	    {
27105b261ecSmrg		glyph = globalGlyphs[fdepth].table[i].glyph;
27205b261ecSmrg		if (glyph && glyph != DeletedGlyph)
27305b261ecSmrg		{
27405b261ecSmrg		    if (!ReallocGlobalGlyphPrivate (glyph))
27505b261ecSmrg			return FALSE;
27605b261ecSmrg		}
27705b261ecSmrg	    }
27805b261ecSmrg	}
27905b261ecSmrg
28005b261ecSmrg	SetGlyphScreenPrivateOffsets ();
28105b261ecSmrg
28205b261ecSmrg	for (fdepth = 0; fdepth < GlyphFormatNum; fdepth++)
28305b261ecSmrg	{
28405b261ecSmrg	    if (!globalGlyphs[fdepth].hashSet)
28505b261ecSmrg		continue;
28605b261ecSmrg
28705b261ecSmrg	    for (i = 0; i < globalGlyphs[fdepth].hashSet->size; i++)
28805b261ecSmrg	    {
28905b261ecSmrg		glyph = globalGlyphs[fdepth].table[i].glyph;
29005b261ecSmrg		if (glyph && glyph != DeletedGlyph)
29105b261ecSmrg		{
29205b261ecSmrg		    SetGlyphPrivatePointers (glyph);
29305b261ecSmrg
29405b261ecSmrg		    if (!(*ps->RealizeGlyph) (pScreen, glyph))
29505b261ecSmrg			return FALSE;
29605b261ecSmrg		}
29705b261ecSmrg	    }
29805b261ecSmrg	}
29905b261ecSmrg    }
30005b261ecSmrg    else
30105b261ecSmrg	ps->glyphPrivateOffset = 0;
30205b261ecSmrg
30305b261ecSmrg    return TRUE;
30405b261ecSmrg}
30505b261ecSmrg
30605b261ecSmrgvoid
30705b261ecSmrgGlyphUninit (ScreenPtr pScreen)
30805b261ecSmrg{
30905b261ecSmrg    PictureScreenPtr ps = GetPictureScreen (pScreen);
31005b261ecSmrg    GlyphPtr	     glyph;
31105b261ecSmrg    int		     fdepth, i;
31205b261ecSmrg
31305b261ecSmrg    globalTotalGlyphPrivateSize -= ps->totalGlyphPrivateSize;
31405b261ecSmrg
31505b261ecSmrg    for (fdepth = 0; fdepth < GlyphFormatNum; fdepth++)
31605b261ecSmrg    {
31705b261ecSmrg	if (!globalGlyphs[fdepth].hashSet)
31805b261ecSmrg	    continue;
31905b261ecSmrg
32005b261ecSmrg	for (i = 0; i < globalGlyphs[fdepth].hashSet->size; i++)
32105b261ecSmrg	{
32205b261ecSmrg	    glyph = globalGlyphs[fdepth].table[i].glyph;
32305b261ecSmrg	    if (glyph && glyph != DeletedGlyph)
32405b261ecSmrg	    {
32505b261ecSmrg		(*ps->UnrealizeGlyph) (pScreen, glyph);
32605b261ecSmrg
32705b261ecSmrg		if (globalTotalGlyphPrivateSize)
32805b261ecSmrg		{
32905b261ecSmrg		    if (!ReallocGlobalGlyphPrivate (glyph))
33005b261ecSmrg			return;
33105b261ecSmrg		}
33205b261ecSmrg		else
33305b261ecSmrg		{
33405b261ecSmrg		    if (glyph->devPrivates)
33505b261ecSmrg			xfree (glyph->devPrivates);
33605b261ecSmrg		    glyph->devPrivates = NULL;
33705b261ecSmrg		}
33805b261ecSmrg	    }
33905b261ecSmrg	}
34005b261ecSmrg    }
34105b261ecSmrg
34205b261ecSmrg    if (globalTotalGlyphPrivateSize)
34305b261ecSmrg	SetGlyphScreenPrivateOffsets ();
34405b261ecSmrg
34505b261ecSmrg    for (fdepth = 0; fdepth < GlyphFormatNum; fdepth++)
34605b261ecSmrg    {
34705b261ecSmrg	if (!globalGlyphs[fdepth].hashSet)
34805b261ecSmrg	    continue;
34905b261ecSmrg
35005b261ecSmrg	for (i = 0; i < globalGlyphs[fdepth].hashSet->size; i++)
35105b261ecSmrg	{
35205b261ecSmrg	    glyph = globalGlyphs[fdepth].table[i].glyph;
35305b261ecSmrg	    if (glyph && glyph != DeletedGlyph)
35405b261ecSmrg	    {
35505b261ecSmrg		if (globalTotalGlyphPrivateSize)
35605b261ecSmrg		    SetGlyphPrivatePointers (glyph);
35705b261ecSmrg	    }
35805b261ecSmrg	}
35905b261ecSmrg    }
36005b261ecSmrg
36105b261ecSmrg    if (ps->glyphPrivateSizes)
36205b261ecSmrg	xfree (ps->glyphPrivateSizes);
36305b261ecSmrg}
36405b261ecSmrg
36505b261ecSmrgGlyphHashSetPtr
36605b261ecSmrgFindGlyphHashSet (CARD32 filled)
36705b261ecSmrg{
36805b261ecSmrg    int	i;
36905b261ecSmrg
37005b261ecSmrg    for (i = 0; i < NGLYPHHASHSETS; i++)
37105b261ecSmrg	if (glyphHashSets[i].entries >= filled)
37205b261ecSmrg	    return &glyphHashSets[i];
37305b261ecSmrg    return 0;
37405b261ecSmrg}
37505b261ecSmrg
37605b261ecSmrgstatic int _GlyphSetPrivateAllocateIndex = 0;
37705b261ecSmrg
37805b261ecSmrgint
37905b261ecSmrgAllocateGlyphSetPrivateIndex (void)
38005b261ecSmrg{
38105b261ecSmrg    return _GlyphSetPrivateAllocateIndex++;
38205b261ecSmrg}
38305b261ecSmrg
38405b261ecSmrgvoid
38505b261ecSmrgResetGlyphSetPrivateIndex (void)
38605b261ecSmrg{
38705b261ecSmrg    _GlyphSetPrivateAllocateIndex = 0;
38805b261ecSmrg}
38905b261ecSmrg
39005b261ecSmrgBool
39105b261ecSmrg_GlyphSetSetNewPrivate (GlyphSetPtr glyphSet, int n, pointer ptr)
39205b261ecSmrg{
39305b261ecSmrg    pointer *new;
39405b261ecSmrg
39505b261ecSmrg    if (n > glyphSet->maxPrivate) {
39605b261ecSmrg	if (glyphSet->devPrivates &&
39705b261ecSmrg	    glyphSet->devPrivates != (pointer)(&glyphSet[1])) {
39805b261ecSmrg	    new = (pointer *) xrealloc (glyphSet->devPrivates,
39905b261ecSmrg					(n + 1) * sizeof (pointer));
40005b261ecSmrg	    if (!new)
40105b261ecSmrg		return FALSE;
40205b261ecSmrg	} else {
40305b261ecSmrg	    new = (pointer *) xalloc ((n + 1) * sizeof (pointer));
40405b261ecSmrg	    if (!new)
40505b261ecSmrg		return FALSE;
40605b261ecSmrg	    if (glyphSet->devPrivates)
40705b261ecSmrg		memcpy (new,
40805b261ecSmrg			glyphSet->devPrivates,
40905b261ecSmrg			(glyphSet->maxPrivate + 1) * sizeof (pointer));
41005b261ecSmrg	}
41105b261ecSmrg	glyphSet->devPrivates = new;
41205b261ecSmrg	/* Zero out new, uninitialize privates */
41305b261ecSmrg	while (++glyphSet->maxPrivate < n)
41405b261ecSmrg	    glyphSet->devPrivates[glyphSet->maxPrivate] = (pointer)0;
41505b261ecSmrg    }
41605b261ecSmrg    glyphSet->devPrivates[n] = ptr;
41705b261ecSmrg    return TRUE;
41805b261ecSmrg}
41905b261ecSmrg
42005b261ecSmrgGlyphRefPtr
42105b261ecSmrgFindGlyphRef (GlyphHashPtr hash, CARD32 signature, Bool match, GlyphPtr compare)
42205b261ecSmrg{
42305b261ecSmrg    CARD32	elt, step, s;
42405b261ecSmrg    GlyphPtr	glyph;
42505b261ecSmrg    GlyphRefPtr	table, gr, del;
42605b261ecSmrg    CARD32	tableSize = hash->hashSet->size;
42705b261ecSmrg
42805b261ecSmrg    table = hash->table;
42905b261ecSmrg    elt = signature % tableSize;
43005b261ecSmrg    step = 0;
43105b261ecSmrg    del = 0;
43205b261ecSmrg    for (;;)
43305b261ecSmrg    {
43405b261ecSmrg	gr = &table[elt];
43505b261ecSmrg	s = gr->signature;
43605b261ecSmrg	glyph = gr->glyph;
43705b261ecSmrg	if (!glyph)
43805b261ecSmrg	{
43905b261ecSmrg	    if (del)
44005b261ecSmrg		gr = del;
44105b261ecSmrg	    break;
44205b261ecSmrg	}
44305b261ecSmrg	if (glyph == DeletedGlyph)
44405b261ecSmrg	{
44505b261ecSmrg	    if (!del)
44605b261ecSmrg		del = gr;
44705b261ecSmrg	    else if (gr == del)
44805b261ecSmrg		break;
44905b261ecSmrg	}
45005b261ecSmrg	else if (s == signature &&
45105b261ecSmrg		 (!match ||
45205b261ecSmrg		  memcmp (&compare->info, &glyph->info, compare->size) == 0))
45305b261ecSmrg	{
45405b261ecSmrg	    break;
45505b261ecSmrg	}
45605b261ecSmrg	if (!step)
45705b261ecSmrg	{
45805b261ecSmrg	    step = signature % hash->hashSet->rehash;
45905b261ecSmrg	    if (!step)
46005b261ecSmrg		step = 1;
46105b261ecSmrg	}
46205b261ecSmrg	elt += step;
46305b261ecSmrg	if (elt >= tableSize)
46405b261ecSmrg	    elt -= tableSize;
46505b261ecSmrg    }
46605b261ecSmrg    return gr;
46705b261ecSmrg}
46805b261ecSmrg
46905b261ecSmrgCARD32
47005b261ecSmrgHashGlyph (GlyphPtr glyph)
47105b261ecSmrg{
47205b261ecSmrg    CARD32  *bits = (CARD32 *) &(glyph->info);
47305b261ecSmrg    CARD32  hash;
47405b261ecSmrg    int	    n = glyph->size / sizeof (CARD32);
47505b261ecSmrg
47605b261ecSmrg    hash = 0;
47705b261ecSmrg    while (n--)
47805b261ecSmrg	hash ^= *bits++;
47905b261ecSmrg    return hash;
48005b261ecSmrg}
48105b261ecSmrg
48205b261ecSmrg#ifdef CHECK_DUPLICATES
48305b261ecSmrgvoid
48405b261ecSmrgDuplicateRef (GlyphPtr glyph, char *where)
48505b261ecSmrg{
48605b261ecSmrg    ErrorF ("Duplicate Glyph 0x%x from %s\n", glyph, where);
48705b261ecSmrg}
48805b261ecSmrg
48905b261ecSmrgvoid
49005b261ecSmrgCheckDuplicates (GlyphHashPtr hash, char *where)
49105b261ecSmrg{
49205b261ecSmrg    GlyphPtr	g;
49305b261ecSmrg    int		i, j;
49405b261ecSmrg
49505b261ecSmrg    for (i = 0; i < hash->hashSet->size; i++)
49605b261ecSmrg    {
49705b261ecSmrg	g = hash->table[i].glyph;
49805b261ecSmrg	if (!g || g == DeletedGlyph)
49905b261ecSmrg	    continue;
50005b261ecSmrg	for (j = i + 1; j < hash->hashSet->size; j++)
50105b261ecSmrg	    if (hash->table[j].glyph == g)
50205b261ecSmrg		DuplicateRef (g, where);
50305b261ecSmrg    }
50405b261ecSmrg}
50505b261ecSmrg#else
50605b261ecSmrg#define CheckDuplicates(a,b)
50705b261ecSmrg#define DuplicateRef(a,b)
50805b261ecSmrg#endif
50905b261ecSmrg
51005b261ecSmrgvoid
51105b261ecSmrgFreeGlyph (GlyphPtr glyph, int format)
51205b261ecSmrg{
51305b261ecSmrg    CheckDuplicates (&globalGlyphs[format], "FreeGlyph");
51405b261ecSmrg    if (--glyph->refcnt == 0)
51505b261ecSmrg    {
51605b261ecSmrg	PictureScreenPtr ps;
51705b261ecSmrg	GlyphRefPtr      gr;
51805b261ecSmrg	int	         i;
51905b261ecSmrg	int	         first;
52005b261ecSmrg
52105b261ecSmrg	first = -1;
52205b261ecSmrg	for (i = 0; i < globalGlyphs[format].hashSet->size; i++)
52305b261ecSmrg	    if (globalGlyphs[format].table[i].glyph == glyph)
52405b261ecSmrg	    {
52505b261ecSmrg		if (first != -1)
52605b261ecSmrg		    DuplicateRef (glyph, "FreeGlyph check");
52705b261ecSmrg		first = i;
52805b261ecSmrg	    }
52905b261ecSmrg
53005b261ecSmrg	gr = FindGlyphRef (&globalGlyphs[format],
53105b261ecSmrg			   HashGlyph (glyph), TRUE, glyph);
53205b261ecSmrg	if (gr - globalGlyphs[format].table != first)
53305b261ecSmrg	    DuplicateRef (glyph, "Found wrong one");
53405b261ecSmrg	if (gr->glyph && gr->glyph != DeletedGlyph)
53505b261ecSmrg	{
53605b261ecSmrg	    gr->glyph = DeletedGlyph;
53705b261ecSmrg	    gr->signature = 0;
53805b261ecSmrg	    globalGlyphs[format].tableEntries--;
53905b261ecSmrg	}
54005b261ecSmrg
54105b261ecSmrg	for (i = 0; i < screenInfo.numScreens; i++)
54205b261ecSmrg	{
54305b261ecSmrg	    ps = GetPictureScreenIfSet (screenInfo.screens[i]);
54405b261ecSmrg	    if (ps)
54505b261ecSmrg		(*ps->UnrealizeGlyph) (screenInfo.screens[i], glyph);
54605b261ecSmrg	}
54705b261ecSmrg
54805b261ecSmrg	if (glyph->devPrivates)
54905b261ecSmrg	    xfree (glyph->devPrivates);
55005b261ecSmrg	xfree (glyph);
55105b261ecSmrg    }
55205b261ecSmrg}
55305b261ecSmrg
55405b261ecSmrgvoid
55505b261ecSmrgAddGlyph (GlyphSetPtr glyphSet, GlyphPtr glyph, Glyph id)
55605b261ecSmrg{
55705b261ecSmrg    GlyphRefPtr	    gr;
55805b261ecSmrg    CARD32	    hash;
55905b261ecSmrg
56005b261ecSmrg    CheckDuplicates (&globalGlyphs[glyphSet->fdepth], "AddGlyph top global");
56105b261ecSmrg    /* Locate existing matching glyph */
56205b261ecSmrg    hash = HashGlyph (glyph);
56305b261ecSmrg    gr = FindGlyphRef (&globalGlyphs[glyphSet->fdepth], hash, TRUE, glyph);
56405b261ecSmrg    if (gr->glyph && gr->glyph != DeletedGlyph)
56505b261ecSmrg    {
56605b261ecSmrg	PictureScreenPtr ps;
56705b261ecSmrg	int              i;
56805b261ecSmrg
56905b261ecSmrg	for (i = 0; i < screenInfo.numScreens; i++)
57005b261ecSmrg	{
57105b261ecSmrg	    ps = GetPictureScreenIfSet (screenInfo.screens[i]);
57205b261ecSmrg	    if (ps)
57305b261ecSmrg		(*ps->UnrealizeGlyph) (screenInfo.screens[i], glyph);
57405b261ecSmrg	}
57505b261ecSmrg	if (glyph->devPrivates)
57605b261ecSmrg	    xfree (glyph->devPrivates);
57705b261ecSmrg	xfree (glyph);
57805b261ecSmrg	glyph = gr->glyph;
57905b261ecSmrg    }
58005b261ecSmrg    else
58105b261ecSmrg    {
58205b261ecSmrg	gr->glyph = glyph;
58305b261ecSmrg	gr->signature = hash;
58405b261ecSmrg	globalGlyphs[glyphSet->fdepth].tableEntries++;
58505b261ecSmrg    }
58605b261ecSmrg
58705b261ecSmrg    /* Insert/replace glyphset value */
58805b261ecSmrg    gr = FindGlyphRef (&glyphSet->hash, id, FALSE, 0);
58905b261ecSmrg    ++glyph->refcnt;
59005b261ecSmrg    if (gr->glyph && gr->glyph != DeletedGlyph)
59105b261ecSmrg	FreeGlyph (gr->glyph, glyphSet->fdepth);
59205b261ecSmrg    else
59305b261ecSmrg	glyphSet->hash.tableEntries++;
59405b261ecSmrg    gr->glyph = glyph;
59505b261ecSmrg    gr->signature = id;
59605b261ecSmrg    CheckDuplicates (&globalGlyphs[glyphSet->fdepth], "AddGlyph bottom");
59705b261ecSmrg}
59805b261ecSmrg
59905b261ecSmrgBool
60005b261ecSmrgDeleteGlyph (GlyphSetPtr glyphSet, Glyph id)
60105b261ecSmrg{
60205b261ecSmrg    GlyphRefPtr     gr;
60305b261ecSmrg    GlyphPtr	    glyph;
60405b261ecSmrg
60505b261ecSmrg    gr = FindGlyphRef (&glyphSet->hash, id, FALSE, 0);
60605b261ecSmrg    glyph = gr->glyph;
60705b261ecSmrg    if (glyph && glyph != DeletedGlyph)
60805b261ecSmrg    {
60905b261ecSmrg	gr->glyph = DeletedGlyph;
61005b261ecSmrg	glyphSet->hash.tableEntries--;
61105b261ecSmrg	FreeGlyph (glyph, glyphSet->fdepth);
61205b261ecSmrg	return TRUE;
61305b261ecSmrg    }
61405b261ecSmrg    return FALSE;
61505b261ecSmrg}
61605b261ecSmrg
61705b261ecSmrgGlyphPtr
61805b261ecSmrgFindGlyph (GlyphSetPtr glyphSet, Glyph id)
61905b261ecSmrg{
62005b261ecSmrg    GlyphPtr        glyph;
62105b261ecSmrg
62205b261ecSmrg    glyph = FindGlyphRef (&glyphSet->hash, id, FALSE, 0)->glyph;
62305b261ecSmrg    if (glyph == DeletedGlyph)
62405b261ecSmrg	glyph = 0;
62505b261ecSmrg    return glyph;
62605b261ecSmrg}
62705b261ecSmrg
62805b261ecSmrgGlyphPtr
62905b261ecSmrgAllocateGlyph (xGlyphInfo *gi, int fdepth)
63005b261ecSmrg{
63105b261ecSmrg    PictureScreenPtr ps;
63205b261ecSmrg    int		     size;
63305b261ecSmrg    GlyphPtr	     glyph;
63405b261ecSmrg    int		     i;
63505b261ecSmrg    size_t	     padded_width;
63605b261ecSmrg
63705b261ecSmrg    padded_width = PixmapBytePad (gi->width, glyphDepths[fdepth]);
63805b261ecSmrg    if (gi->height && padded_width > (UINT32_MAX - sizeof(GlyphRec))/gi->height)
63905b261ecSmrg	return 0;
64005b261ecSmrg    size = gi->height * padded_width;
64105b261ecSmrg    glyph = (GlyphPtr) xalloc (size + sizeof (GlyphRec));
64205b261ecSmrg    if (!glyph)
64305b261ecSmrg	return 0;
64405b261ecSmrg    glyph->refcnt = 0;
64505b261ecSmrg    glyph->size = size + sizeof (xGlyphInfo);
64605b261ecSmrg    glyph->info = *gi;
64705b261ecSmrg
64805b261ecSmrg    if (globalTotalGlyphPrivateSize)
64905b261ecSmrg    {
65005b261ecSmrg	glyph->devPrivates = xalloc (globalTotalGlyphPrivateSize);
65105b261ecSmrg	if (!glyph->devPrivates)
65205b261ecSmrg	    return 0;
65305b261ecSmrg
65405b261ecSmrg	SetGlyphPrivatePointers (glyph);
65505b261ecSmrg    } else
65605b261ecSmrg	glyph->devPrivates = NULL;
65705b261ecSmrg
65805b261ecSmrg    for (i = 0; i < screenInfo.numScreens; i++)
65905b261ecSmrg    {
66005b261ecSmrg	ps = GetPictureScreenIfSet (screenInfo.screens[i]);
66105b261ecSmrg	if (ps)
66205b261ecSmrg	{
66305b261ecSmrg	    if (!(*ps->RealizeGlyph) (screenInfo.screens[i], glyph))
66405b261ecSmrg	    {
66505b261ecSmrg		while (i--)
66605b261ecSmrg		{
66705b261ecSmrg		    ps = GetPictureScreenIfSet (screenInfo.screens[i]);
66805b261ecSmrg		    if (ps)
66905b261ecSmrg			(*ps->UnrealizeGlyph) (screenInfo.screens[i], glyph);
67005b261ecSmrg		}
67105b261ecSmrg
67205b261ecSmrg		if (glyph->devPrivates)
67305b261ecSmrg		    xfree (glyph->devPrivates);
67405b261ecSmrg		xfree (glyph);
67505b261ecSmrg		return 0;
67605b261ecSmrg	    }
67705b261ecSmrg	}
67805b261ecSmrg    }
67905b261ecSmrg
68005b261ecSmrg    return glyph;
68105b261ecSmrg}
68205b261ecSmrg
68305b261ecSmrgBool
68405b261ecSmrgAllocateGlyphHash (GlyphHashPtr hash, GlyphHashSetPtr hashSet)
68505b261ecSmrg{
68605b261ecSmrg    hash->table = (GlyphRefPtr) xalloc (hashSet->size * sizeof (GlyphRefRec));
68705b261ecSmrg    if (!hash->table)
68805b261ecSmrg	return FALSE;
68905b261ecSmrg    memset (hash->table, 0, hashSet->size * sizeof (GlyphRefRec));
69005b261ecSmrg    hash->hashSet = hashSet;
69105b261ecSmrg    hash->tableEntries = 0;
69205b261ecSmrg    return TRUE;
69305b261ecSmrg}
69405b261ecSmrg
69505b261ecSmrgBool
69605b261ecSmrgResizeGlyphHash (GlyphHashPtr hash, CARD32 change, Bool global)
69705b261ecSmrg{
69805b261ecSmrg    CARD32	    tableEntries;
69905b261ecSmrg    GlyphHashSetPtr hashSet;
70005b261ecSmrg    GlyphHashRec    newHash;
70105b261ecSmrg    GlyphRefPtr	    gr;
70205b261ecSmrg    GlyphPtr	    glyph;
70305b261ecSmrg    int		    i;
70405b261ecSmrg    int		    oldSize;
70505b261ecSmrg    CARD32	    s;
70605b261ecSmrg
70705b261ecSmrg    tableEntries = hash->tableEntries + change;
70805b261ecSmrg    hashSet = FindGlyphHashSet (tableEntries);
70905b261ecSmrg    if (hashSet == hash->hashSet)
71005b261ecSmrg	return TRUE;
71105b261ecSmrg    if (global)
71205b261ecSmrg	CheckDuplicates (hash, "ResizeGlyphHash top");
71305b261ecSmrg    if (!AllocateGlyphHash (&newHash, hashSet))
71405b261ecSmrg	return FALSE;
71505b261ecSmrg    if (hash->table)
71605b261ecSmrg    {
71705b261ecSmrg	oldSize = hash->hashSet->size;
71805b261ecSmrg	for (i = 0; i < oldSize; i++)
71905b261ecSmrg	{
72005b261ecSmrg	    glyph = hash->table[i].glyph;
72105b261ecSmrg	    if (glyph && glyph != DeletedGlyph)
72205b261ecSmrg	    {
72305b261ecSmrg		s = hash->table[i].signature;
72405b261ecSmrg		gr = FindGlyphRef (&newHash, s, global, glyph);
72505b261ecSmrg		gr->signature = s;
72605b261ecSmrg		gr->glyph = glyph;
72705b261ecSmrg		++newHash.tableEntries;
72805b261ecSmrg	    }
72905b261ecSmrg	}
73005b261ecSmrg	xfree (hash->table);
73105b261ecSmrg    }
73205b261ecSmrg    *hash = newHash;
73305b261ecSmrg    if (global)
73405b261ecSmrg	CheckDuplicates (hash, "ResizeGlyphHash bottom");
73505b261ecSmrg    return TRUE;
73605b261ecSmrg}
73705b261ecSmrg
73805b261ecSmrgBool
73905b261ecSmrgResizeGlyphSet (GlyphSetPtr glyphSet, CARD32 change)
74005b261ecSmrg{
74105b261ecSmrg    return (ResizeGlyphHash (&glyphSet->hash, change, FALSE) &&
74205b261ecSmrg	    ResizeGlyphHash (&globalGlyphs[glyphSet->fdepth], change, TRUE));
74305b261ecSmrg}
74405b261ecSmrg
74505b261ecSmrgGlyphSetPtr
74605b261ecSmrgAllocateGlyphSet (int fdepth, PictFormatPtr format)
74705b261ecSmrg{
74805b261ecSmrg    GlyphSetPtr	glyphSet;
74905b261ecSmrg    int size;
75005b261ecSmrg
75105b261ecSmrg    if (!globalGlyphs[fdepth].hashSet)
75205b261ecSmrg    {
75305b261ecSmrg	if (!AllocateGlyphHash (&globalGlyphs[fdepth], &glyphHashSets[0]))
75405b261ecSmrg	    return FALSE;
75505b261ecSmrg    }
75605b261ecSmrg
75705b261ecSmrg    size = (sizeof (GlyphSetRec) +
75805b261ecSmrg	    (sizeof (pointer) * _GlyphSetPrivateAllocateIndex));
75905b261ecSmrg    glyphSet = xalloc (size);
76005b261ecSmrg    if (!glyphSet)
76105b261ecSmrg	return FALSE;
76205b261ecSmrg    bzero((char *)glyphSet, size);
76305b261ecSmrg    glyphSet->maxPrivate = _GlyphSetPrivateAllocateIndex - 1;
76405b261ecSmrg    if (_GlyphSetPrivateAllocateIndex)
76505b261ecSmrg	glyphSet->devPrivates = (pointer)(&glyphSet[1]);
76605b261ecSmrg
76705b261ecSmrg    if (!AllocateGlyphHash (&glyphSet->hash, &glyphHashSets[0]))
76805b261ecSmrg    {
76905b261ecSmrg	xfree (glyphSet);
77005b261ecSmrg	return FALSE;
77105b261ecSmrg    }
77205b261ecSmrg    glyphSet->refcnt = 1;
77305b261ecSmrg    glyphSet->fdepth = fdepth;
77405b261ecSmrg    glyphSet->format = format;
77505b261ecSmrg    return glyphSet;
77605b261ecSmrg}
77705b261ecSmrg
77805b261ecSmrgint
77905b261ecSmrgFreeGlyphSet (pointer	value,
78005b261ecSmrg	      XID       gid)
78105b261ecSmrg{
78205b261ecSmrg    GlyphSetPtr	glyphSet = (GlyphSetPtr) value;
78305b261ecSmrg
78405b261ecSmrg    if (--glyphSet->refcnt == 0)
78505b261ecSmrg    {
78605b261ecSmrg	CARD32	    i, tableSize = glyphSet->hash.hashSet->size;
78705b261ecSmrg	GlyphRefPtr table = glyphSet->hash.table;
78805b261ecSmrg	GlyphPtr    glyph;
78905b261ecSmrg
79005b261ecSmrg	for (i = 0; i < tableSize; i++)
79105b261ecSmrg	{
79205b261ecSmrg	    glyph = table[i].glyph;
79305b261ecSmrg	    if (glyph && glyph != DeletedGlyph)
79405b261ecSmrg		FreeGlyph (glyph, glyphSet->fdepth);
79505b261ecSmrg	}
79605b261ecSmrg	if (!globalGlyphs[glyphSet->fdepth].tableEntries)
79705b261ecSmrg	{
79805b261ecSmrg	    xfree (globalGlyphs[glyphSet->fdepth].table);
79905b261ecSmrg	    globalGlyphs[glyphSet->fdepth].table = 0;
80005b261ecSmrg	    globalGlyphs[glyphSet->fdepth].hashSet = 0;
80105b261ecSmrg	}
80205b261ecSmrg	else
80305b261ecSmrg	    ResizeGlyphHash (&globalGlyphs[glyphSet->fdepth], 0, TRUE);
80405b261ecSmrg	xfree (table);
80505b261ecSmrg
80605b261ecSmrg	if (glyphSet->devPrivates &&
80705b261ecSmrg	    glyphSet->devPrivates != (pointer)(&glyphSet[1]))
80805b261ecSmrg	    xfree(glyphSet->devPrivates);
80905b261ecSmrg
81005b261ecSmrg	xfree (glyphSet);
81105b261ecSmrg    }
81205b261ecSmrg    return Success;
81305b261ecSmrg}
814