source: trunk/poppler/fontconfig-2.3.2-os2/src/fccharset.c @ 2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 15 years ago

First import

File size: 28.0 KB
Line 
1/*
2 * $RCSId: xc/lib/fontconfig/src/fccharset.c,v 1.18 2002/08/22 07:36:44 keithp Exp $
3 *
4 * Copyright © 2001 Keith Packard
5 *
6 * Permission to use, copy, modify, distribute, and sell this software and its
7 * documentation for any purpose is hereby granted without fee, provided that
8 * the above copyright notice appear in all copies and that both that
9 * copyright notice and this permission notice appear in supporting
10 * documentation, and that the name of Keith Packard not be used in
11 * advertising or publicity pertaining to distribution of the software without
12 * specific, written prior permission.  Keith Packard makes no
13 * representations about the suitability of this software for any purpose.  It
14 * is provided "as is" without express or implied warranty.
15 *
16 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
18 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
19 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
20 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
21 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
22 * PERFORMANCE OF THIS SOFTWARE.
23 */
24
25#include <stdlib.h>
26#include "fcint.h"
27
28/* #define CHECK */
29
30/* #define CHATTY */
31
32FcCharSet *
33FcCharSetCreate (void)
34{
35    FcCharSet   *fcs;
36
37    fcs = (FcCharSet *) malloc (sizeof (FcCharSet));
38    if (!fcs)
39        return 0;
40    FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
41    fcs->ref = 1;
42    fcs->num = 0;
43    fcs->leaves = 0;
44    fcs->numbers = 0;
45    return fcs;
46}
47
48FcCharSet *
49FcCharSetNew (void);
50   
51FcCharSet *
52FcCharSetNew (void)
53{
54    return FcCharSetCreate ();
55}
56
57
58void
59FcCharSetDestroy (FcCharSet *fcs)
60{
61    int i;
62    if (fcs->ref == FC_REF_CONSTANT)
63        return;
64    if (--fcs->ref > 0)
65        return;
66    for (i = 0; i < fcs->num; i++)
67    {
68        FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
69        free (fcs->leaves[i]);
70    }
71    if (fcs->leaves)
72    {
73        FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
74        free (fcs->leaves);
75    }
76    if (fcs->numbers)
77    {
78        FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
79        free (fcs->numbers);
80    }
81    FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
82    free (fcs);
83}
84
85/*
86 * Locate the leaf containing the specified char, return
87 * its index if it exists, otherwise return negative of
88 * the (position + 1) where it should be inserted
89 */
90
91static int
92FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
93{
94    FcChar16            *numbers = fcs->numbers;
95    FcChar16            page;
96    int                 low = 0;
97    int                 high = fcs->num - 1;
98
99    if (!numbers)
100        return -1;
101    ucs4 >>= 8;
102    while (low <= high)
103    {
104        int mid = (low + high) >> 1;
105        page = numbers[mid];
106        if (page == ucs4)
107            return mid;
108        if (page < ucs4)
109            low = mid + 1;
110        else
111            high = mid - 1;
112    }
113    if (high < 0 || (high < fcs->num && numbers[high] < ucs4))
114        high++;
115    return -(high + 1);
116}
117
118static FcCharLeaf *
119FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
120{
121    int pos = FcCharSetFindLeafPos (fcs, ucs4);
122    if (pos >= 0)
123        return fcs->leaves[pos];
124    return 0;
125}
126
127static FcBool
128FcCharSetPutLeaf (FcCharSet     *fcs, 
129                  FcChar32      ucs4,
130                  FcCharLeaf    *leaf, 
131                  int           pos)
132{
133    FcCharLeaf  **leaves;
134    FcChar16    *numbers;
135
136    ucs4 >>= 8;
137    if (ucs4 >= 0x10000)
138        return FcFalse;
139    if (!fcs->leaves)
140        leaves = malloc (sizeof (FcCharLeaf *));
141    else
142        leaves = realloc (fcs->leaves, (fcs->num + 1) * sizeof (FcCharLeaf *));
143    if (!leaves)
144        return FcFalse;
145    if (fcs->num)
146        FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
147    FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcCharLeaf *));
148    fcs->leaves = leaves;
149    if (!fcs->numbers)
150        numbers = malloc (sizeof (FcChar16));
151    else
152        numbers = realloc (fcs->numbers, (fcs->num + 1) * sizeof (FcChar16));
153    if (!numbers)
154        return FcFalse;
155    if (fcs->num)
156        FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
157    FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcChar16));
158    fcs->numbers = numbers;
159   
160    memmove (fcs->leaves + pos + 1, fcs->leaves + pos, 
161             (fcs->num - pos) * sizeof (FcCharLeaf *));
162    memmove (fcs->numbers + pos + 1, fcs->numbers + pos,
163             (fcs->num - pos) * sizeof (FcChar16));
164    fcs->numbers[pos] = (FcChar16) ucs4;
165    fcs->leaves[pos] = leaf;
166    fcs->num++;
167    return FcTrue;
168}
169
170/*
171 * Locate the leaf containing the specified char, creating it
172 * if desired
173 */
174
175FcCharLeaf *
176FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
177{
178    int                 pos;
179    FcCharLeaf          *leaf;
180
181    pos = FcCharSetFindLeafPos (fcs, ucs4);
182    if (pos >= 0)
183        return fcs->leaves[pos];
184   
185    leaf = calloc (1, sizeof (FcCharLeaf));
186    if (!leaf)
187        return 0;
188   
189    pos = -pos - 1;
190    if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
191    {
192        free (leaf);
193        return 0;
194    }
195    FcMemAlloc (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
196    return leaf;
197}
198
199static FcBool
200FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
201{
202    int             pos;
203
204    pos = FcCharSetFindLeafPos (fcs, ucs4);
205    if (pos >= 0)
206    {
207        FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
208        free (fcs->leaves[pos]);
209        fcs->leaves[pos] = leaf;
210        return FcTrue;
211    }
212    pos = -pos - 1;
213    return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
214}
215
216FcBool
217FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
218{
219    FcCharLeaf  *leaf;
220    FcChar32    *b;
221   
222    if (fcs->ref == FC_REF_CONSTANT)
223        return FcFalse;
224    leaf = FcCharSetFindLeafCreate (fcs, ucs4);
225    if (!leaf)
226        return FcFalse;
227    b = &leaf->map[(ucs4 & 0xff) >> 5];
228    *b |= (1 << (ucs4 & 0x1f));
229    return FcTrue;
230}
231
232/*
233 * An iterator for the leaves of a charset
234 */
235
236typedef struct _fcCharSetIter {
237    FcCharLeaf      *leaf;
238    FcChar32        ucs4;
239    int             pos;
240} FcCharSetIter;
241
242/*
243 * Set iter->leaf to the leaf containing iter->ucs4 or higher
244 */
245
246static void
247FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
248{
249    int             pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
250
251    if (pos < 0)
252    {
253        pos = -pos - 1;
254        if (pos == fcs->num)
255        {
256            iter->ucs4 = ~0;
257            iter->leaf = 0;
258            return;
259        }
260        iter->ucs4 = (FcChar32) fcs->numbers[pos] << 8;
261    }
262    iter->leaf = fcs->leaves[pos];
263    iter->pos = pos;
264#ifdef CHATTY
265    printf ("set %08x: %08x\n", iter->ucs4, (FcChar32) iter->leaf);
266#endif
267}
268
269static void
270FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
271{
272    int pos = iter->pos + 1;
273    if (pos >= fcs->num)
274    {
275        iter->ucs4 = ~0;
276        iter->leaf = 0;
277    }
278    else
279    {
280        iter->ucs4 = (FcChar32) fcs->numbers[pos] << 8;
281        iter->leaf = fcs->leaves[pos];
282        iter->pos = pos;
283    }
284}
285
286#ifdef CHATTY
287static void
288FcCharSetDump (const FcCharSet *fcs)
289{
290    int         pos;
291
292    printf ("fcs %08x:\n", (FcChar32) fcs);
293    for (pos = 0; pos < fcs->num; pos++)
294    {
295        FcCharLeaf      *leaf = fcs->leaves[pos];
296        FcChar32        ucs4 = (FcChar32) fcs->numbers[pos] << 8;
297       
298        printf ("    %08x: %08x\n", ucs4, (FcChar32) leaf);
299    }
300}
301#endif
302
303static void
304FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
305{
306#ifdef CHATTY
307    FcCharSetDump (fcs);
308#endif
309    iter->ucs4 = 0;
310    FcCharSetIterSet (fcs, iter);
311}
312
313FcCharSet *
314FcCharSetCopy (FcCharSet *src)
315{
316    if (src->ref != FC_REF_CONSTANT)
317        src->ref++;
318    return src;
319}
320
321FcBool
322FcCharSetEqual (const FcCharSet *a, const FcCharSet *b)
323{
324    FcCharSetIter   ai, bi;
325    int             i;
326   
327    if (a == b)
328        return FcTrue;
329    for (FcCharSetIterStart (a, &ai), FcCharSetIterStart (b, &bi);
330         ai.leaf && bi.leaf;
331         FcCharSetIterNext (a, &ai), FcCharSetIterNext (b, &bi))
332    {
333        if (ai.ucs4 != bi.ucs4)
334            return FcFalse;
335        for (i = 0; i < 256/32; i++)
336            if (ai.leaf->map[i] != bi.leaf->map[i])
337                return FcFalse;
338    }
339    return ai.leaf == bi.leaf;
340}
341
342static FcBool
343FcCharSetAddLeaf (FcCharSet     *fcs,
344                  FcChar32      ucs4,
345                  FcCharLeaf    *leaf)
346{
347    FcCharLeaf   *new = FcCharSetFindLeafCreate (fcs, ucs4);
348    if (!new)
349        return FcFalse;
350    *new = *leaf;
351    return FcTrue;
352}
353
354static FcCharSet *
355FcCharSetOperate (const FcCharSet   *a,
356                  const FcCharSet   *b,
357                  FcBool            (*overlap) (FcCharLeaf          *result,
358                                                const FcCharLeaf    *al,
359                                                const FcCharLeaf    *bl),
360                  FcBool        aonly,
361                  FcBool        bonly)
362{
363    FcCharSet       *fcs;
364    FcCharSetIter   ai, bi;
365
366    fcs = FcCharSetCreate ();
367    if (!fcs)
368        goto bail0;
369    FcCharSetIterStart (a, &ai);
370    FcCharSetIterStart (b, &bi);
371    while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
372    {
373        if (ai.ucs4 < bi.ucs4)
374        {
375            if (aonly)
376            {
377                if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
378                    goto bail1;
379                FcCharSetIterNext (a, &ai);
380            }
381            else
382            {
383                ai.ucs4 = bi.ucs4;
384                FcCharSetIterSet (a, &ai);
385            }
386        }
387        else if (bi.ucs4 < ai.ucs4 )
388        {
389            if (bonly)
390            {
391                if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
392                    goto bail1;
393                FcCharSetIterNext (b, &bi);
394            }
395            else
396            {
397                bi.ucs4 = ai.ucs4;
398                FcCharSetIterSet (b, &bi);
399            }
400        }
401        else
402        {
403            FcCharLeaf  leaf;
404
405            if ((*overlap) (&leaf, ai.leaf, bi.leaf))
406            {
407                if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
408                    goto bail1;
409            }
410            FcCharSetIterNext (a, &ai);
411            FcCharSetIterNext (b, &bi);
412        }
413    }
414    return fcs;
415bail1:
416    FcCharSetDestroy (fcs);
417bail0:
418    return 0;
419}
420
421static FcBool
422FcCharSetIntersectLeaf (FcCharLeaf *result,
423                        const FcCharLeaf *al,
424                        const FcCharLeaf *bl)
425{
426    int     i;
427    FcBool  nonempty = FcFalse;
428
429    for (i = 0; i < 256/32; i++)
430        if ((result->map[i] = al->map[i] & bl->map[i]))
431            nonempty = FcTrue;
432    return nonempty;
433}
434
435FcCharSet *
436FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
437{
438    return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
439}
440
441static FcBool
442FcCharSetUnionLeaf (FcCharLeaf *result,
443                    const FcCharLeaf *al,
444                    const FcCharLeaf *bl)
445{
446    int i;
447
448    for (i = 0; i < 256/32; i++)
449        result->map[i] = al->map[i] | bl->map[i];
450    return FcTrue;
451}
452
453FcCharSet *
454FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
455{
456    return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
457}
458
459static FcBool
460FcCharSetSubtractLeaf (FcCharLeaf *result,
461                       const FcCharLeaf *al,
462                       const FcCharLeaf *bl)
463{
464    int     i;
465    FcBool  nonempty = FcFalse;
466
467    for (i = 0; i < 256/32; i++)
468        if ((result->map[i] = al->map[i] & ~bl->map[i]))
469            nonempty = FcTrue;
470    return nonempty;
471}
472
473FcCharSet *
474FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
475{
476    return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
477}
478
479FcBool
480FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
481{
482    FcCharLeaf  *leaf = FcCharSetFindLeaf (fcs, ucs4);
483    if (!leaf)
484        return FcFalse;
485    return (leaf->map[(ucs4 & 0xff) >> 5] & (1 << (ucs4 & 0x1f))) != 0;
486}
487
488static FcChar32
489FcCharSetPopCount (FcChar32 c1)
490{
491    /* hackmem 169 */
492    FcChar32    c2 = (c1 >> 1) & 033333333333;
493    c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
494    return (((c2 + (c2 >> 3)) & 030707070707) % 077);
495}
496
497FcChar32
498FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b)
499{
500    FcCharSetIter   ai, bi;
501    FcChar32        count = 0;
502   
503    FcCharSetIterStart (a, &ai);
504    FcCharSetIterStart (b, &bi);
505    while (ai.leaf && bi.leaf)
506    {
507        if (ai.ucs4 == bi.ucs4)
508        {
509            FcChar32    *am = ai.leaf->map;
510            FcChar32    *bm = bi.leaf->map;
511            int         i = 256/32;
512            while (i--)
513                count += FcCharSetPopCount (*am++ & *bm++);
514            FcCharSetIterNext (a, &ai);
515        } 
516        else if (ai.ucs4 < bi.ucs4)
517        {
518            ai.ucs4 = bi.ucs4;
519            FcCharSetIterSet (a, &ai);
520        }
521        if (bi.ucs4 < ai.ucs4)
522        {
523            bi.ucs4 = ai.ucs4;
524            FcCharSetIterSet (b, &bi);
525        }
526    }
527    return count;
528}
529
530FcChar32
531FcCharSetCount (const FcCharSet *a)
532{
533    FcCharSetIter   ai;
534    FcChar32        count = 0;
535   
536    for (FcCharSetIterStart (a, &ai); ai.leaf; FcCharSetIterNext (a, &ai))
537    {
538        int                 i = 256/32;
539        FcChar32            *am = ai.leaf->map;
540
541        while (i--)
542            count += FcCharSetPopCount (*am++);
543    }
544    return count;
545}
546
547FcChar32
548FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
549{
550    FcCharSetIter   ai, bi;
551    FcChar32        count = 0;
552   
553    FcCharSetIterStart (a, &ai);
554    FcCharSetIterStart (b, &bi);
555    while (ai.leaf)
556    {
557        if (ai.ucs4 <= bi.ucs4)
558        {
559            FcChar32    *am = ai.leaf->map;
560            int         i = 256/32;
561            if (ai.ucs4 == bi.ucs4)
562            {
563                FcChar32        *bm = bi.leaf->map;;
564                while (i--)
565                    count += FcCharSetPopCount (*am++ & ~*bm++);
566            }
567            else
568            {
569                while (i--)
570                    count += FcCharSetPopCount (*am++);
571            }
572            FcCharSetIterNext (a, &ai);
573        }
574        else if (bi.leaf)
575        {
576            bi.ucs4 = ai.ucs4;
577            FcCharSetIterSet (b, &bi);
578        }
579    }
580    return count;
581}
582
583/*
584 * return FcTrue iff a is a subset of b
585 */
586FcBool
587FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
588{
589    int         ai, bi;
590    FcChar16    an, bn;
591   
592    if (a == b) return FcTrue;
593    bi = 0;
594    ai = 0;
595    while (ai < a->num && bi < b->num)
596    {
597        an = a->numbers[ai];
598        bn = b->numbers[bi];
599        /*
600         * Check matching pages
601         */
602        if (an == bn)
603        {
604            FcChar32    *am = a->leaves[ai]->map;
605            FcChar32    *bm = b->leaves[bi]->map;
606           
607            if (am != bm)
608            {
609                int     i = 256/32;
610                /*
611                 * Does am have any bits not in bm?
612                 */
613                while (i--)
614                    if (*am++ & ~*bm++)
615                        return FcFalse;
616            }
617            ai++;
618            bi++;
619        }
620        /*
621         * Does a have any pages not in b?
622         */
623        else if (an < bn)
624            return FcFalse;
625        else
626        {
627            int     low = bi + 1;
628            int     high = b->num - 1;
629
630            /*
631             * Search for page 'an' in 'b'
632             */
633            while (low <= high)
634            {
635                int mid = (low + high) >> 1;
636                bn = b->numbers[mid];
637                if (bn == an)
638                {
639                    high = mid;
640                    break;
641                }
642                if (bn < an)
643                    low = mid + 1;
644                else
645                    high = mid - 1;
646            }
647            bi = high;
648            while (bi < b->num && b->numbers[bi] < an)
649                bi++;
650        }
651    }
652    /*
653     * did we look at every page?
654     */
655    return ai >= a->num;
656}
657
658/*
659 * These two functions efficiently walk the entire charmap for
660 * other software (like pango) that want their own copy
661 */
662
663FcChar32
664FcCharSetNextPage (const FcCharSet  *a, 
665                   FcChar32         map[FC_CHARSET_MAP_SIZE],
666                   FcChar32         *next)
667{
668    FcCharSetIter   ai;
669    FcChar32        page;
670
671    ai.ucs4 = *next;
672    FcCharSetIterSet (a, &ai);
673    if (!ai.leaf)
674        return FC_CHARSET_DONE;
675   
676    /*
677     * Save current information
678     */
679    page = ai.ucs4;
680    memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
681    /*
682     * Step to next page
683     */
684    FcCharSetIterNext (a, &ai);
685    *next = ai.ucs4;
686
687    return page;
688}
689
690FcChar32
691FcCharSetFirstPage (const FcCharSet *a, 
692                    FcChar32        map[FC_CHARSET_MAP_SIZE],
693                    FcChar32        *next)
694{
695    *next = 0;
696    return FcCharSetNextPage (a, map, next);
697}
698
699/*
700 * old coverage API, rather hard to use correctly
701 */
702FcChar32
703FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result);
704   
705FcChar32
706FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
707{
708    FcCharSetIter   ai;
709
710    ai.ucs4 = page;
711    FcCharSetIterSet (a, &ai);
712    if (!ai.leaf)
713    {
714        memset (result, '\0', 256 / 8);
715        page = 0;
716    }
717    else
718    {
719        memcpy (result, ai.leaf->map, sizeof (ai.leaf->map));
720        FcCharSetIterNext (a, &ai);
721        page = ai.ucs4;
722    }
723    return page;
724}
725
726/*
727 * ASCII representation of charsets.
728 *
729 * Each leaf is represented as 9 32-bit values, the code of the first character followed
730 * by 8 32 bit values for the leaf itself.  Each value is encoded as 5 ASCII characters,
731 * only 85 different values are used to avoid control characters as well as the other
732 * characters used to encode font names.  85**5 > 2^32 so things work out, but
733 * it's not exactly human readable output.  As a special case, 0 is encoded as a space
734 */
735
736static const unsigned char      charToValue[256] = {
737    /*     "" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
738    /*   "\b" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
739    /* "\020" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
740    /* "\030" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
741    /*    " " */ 0xff,  0x00,  0xff,  0x01,  0x02,  0x03,  0x04,  0xff, 
742    /*    "(" */ 0x05,  0x06,  0x07,  0x08,  0xff,  0xff,  0x09,  0x0a, 
743    /*    "0" */ 0x0b,  0x0c,  0x0d,  0x0e,  0x0f,  0x10,  0x11,  0x12, 
744    /*    "8" */ 0x13,  0x14,  0xff,  0x15,  0x16,  0xff,  0x17,  0x18, 
745    /*    "@" */ 0x19,  0x1a,  0x1b,  0x1c,  0x1d,  0x1e,  0x1f,  0x20, 
746    /*    "H" */ 0x21,  0x22,  0x23,  0x24,  0x25,  0x26,  0x27,  0x28, 
747    /*    "P" */ 0x29,  0x2a,  0x2b,  0x2c,  0x2d,  0x2e,  0x2f,  0x30, 
748    /*    "X" */ 0x31,  0x32,  0x33,  0x34,  0xff,  0x35,  0x36,  0xff, 
749    /*    "`" */ 0xff,  0x37,  0x38,  0x39,  0x3a,  0x3b,  0x3c,  0x3d, 
750    /*    "h" */ 0x3e,  0x3f,  0x40,  0x41,  0x42,  0x43,  0x44,  0x45, 
751    /*    "p" */ 0x46,  0x47,  0x48,  0x49,  0x4a,  0x4b,  0x4c,  0x4d, 
752    /*    "x" */ 0x4e,  0x4f,  0x50,  0x51,  0x52,  0x53,  0x54,  0xff, 
753    /* "\200" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
754    /* "\210" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
755    /* "\220" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
756    /* "\230" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
757    /* "\240" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
758    /* "\250" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
759    /* "\260" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
760    /* "\270" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
761    /* "\300" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
762    /* "\310" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
763    /* "\320" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
764    /* "\330" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
765    /* "\340" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
766    /* "\350" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
767    /* "\360" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
768    /* "\370" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff, 
769};
770
771static const FcChar8 valueToChar[0x55] = {
772    /* 0x00 */ '!', '#', '$', '%', '&', '(', ')', '*',
773    /* 0x08 */ '+', '.', '/', '0', '1', '2', '3', '4',
774    /* 0x10 */ '5', '6', '7', '8', '9', ';', '<', '>',
775    /* 0x18 */ '?', '@', 'A', 'B', 'C', 'D', 'E', 'F',
776    /* 0x20 */ 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
777    /* 0x28 */ 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
778    /* 0x30 */ 'W', 'X', 'Y', 'Z', '[', ']', '^', 'a',
779    /* 0x38 */ 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
780    /* 0x40 */ 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
781    /* 0x48 */ 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
782    /* 0x50 */ 'z', '{', '|', '}', '~',
783};
784
785static FcChar8 *
786FcCharSetParseValue (FcChar8 *string, FcChar32 *value)
787{
788    int         i;
789    FcChar32    v;
790    FcChar32    c;
791   
792    if (*string == ' ')
793    {
794        v = 0;
795        string++;
796    }
797    else
798    {
799        v = 0;
800        for (i = 0; i < 5; i++)
801        {
802            if (!(c = (FcChar32) (unsigned char) *string++))
803                return 0;
804            c = charToValue[c];
805            if (c == 0xff)
806                return 0;
807            v = v * 85 + c;
808        }
809    }
810    *value = v;
811    return string;
812}
813
814static FcBool
815FcCharSetUnparseValue (FcStrBuf *buf, FcChar32 value)
816{
817    int     i;
818    if (value == 0)
819    {
820        return FcStrBufChar (buf, ' ');
821    }
822    else
823    {
824        FcChar8 string[6];
825        FcChar8 *s = string + 5;
826        string[5] = '\0';
827        for (i = 0; i < 5; i++)
828        {
829            *--s = valueToChar[value % 85];
830            value /= 85;
831        }
832        for (i = 0; i < 5; i++)
833            if (!FcStrBufChar (buf, *s++))
834                return FcFalse;
835    }
836    return FcTrue;
837}
838
839typedef struct _FcCharLeafEnt FcCharLeafEnt;
840
841struct _FcCharLeafEnt {
842    FcCharLeafEnt   *next;
843    FcChar32        hash;
844    FcCharLeaf      leaf;
845};
846
847#define FC_CHAR_LEAF_BLOCK      (4096 / sizeof (FcCharLeafEnt))
848static FcCharLeafEnt **FcCharLeafBlocks;
849static int FcCharLeafBlockCount;
850
851static FcCharLeafEnt *
852FcCharLeafEntCreate (void)
853{
854    static FcCharLeafEnt    *block;
855    static int              remain;
856
857    if (!remain)
858    {
859        FcCharLeafEnt **newBlocks;
860
861        FcCharLeafBlockCount++;
862        newBlocks = realloc (FcCharLeafBlocks, FcCharLeafBlockCount * sizeof (FcCharLeafEnt *));
863        if (!newBlocks)
864            return 0;
865        FcCharLeafBlocks = newBlocks;
866        block = FcCharLeafBlocks[FcCharLeafBlockCount-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
867        if (!block)
868            return 0;
869        FcMemAlloc (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
870        remain = FC_CHAR_LEAF_BLOCK;
871    }
872    remain--;
873    return block++;
874}
875
876#define FC_CHAR_LEAF_HASH_SIZE  257
877
878static FcChar32
879FcCharLeafHash (FcCharLeaf *leaf)
880{
881    FcChar32    hash = 0;
882    int         i;
883
884    for (i = 0; i < 256/32; i++)
885        hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
886    return hash;
887}
888
889static int      FcCharLeafTotal;
890static int      FcCharLeafUsed;
891
892static FcCharLeafEnt    *FcCharLeafHashTable[FC_CHAR_LEAF_HASH_SIZE];
893
894static FcCharLeaf *
895FcCharSetFreezeLeaf (FcCharLeaf *leaf)
896{
897    FcChar32                    hash = FcCharLeafHash (leaf);
898    FcCharLeafEnt               **bucket = &FcCharLeafHashTable[hash % FC_CHAR_LEAF_HASH_SIZE];
899    FcCharLeafEnt               *ent;
900   
901    FcCharLeafTotal++;
902    for (ent = *bucket; ent; ent = ent->next)
903    {
904        if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
905            return &ent->leaf;
906    }
907
908    ent = FcCharLeafEntCreate();
909    if (!ent)
910        return 0;
911    FcCharLeafUsed++;
912    ent->leaf = *leaf;
913    ent->hash = hash;
914    ent->next = *bucket;
915    *bucket = ent;
916    return &ent->leaf;
917}
918
919static void
920FcCharSetThawAllLeaf (void)
921{
922    int i;
923
924    for (i = 0; i < FC_CHAR_LEAF_HASH_SIZE; i++)
925        FcCharLeafHashTable[i] = 0;
926
927    FcCharLeafTotal = 0;
928    FcCharLeafUsed = 0;
929
930    for (i = 0; i < FcCharLeafBlockCount; i++)
931        free (FcCharLeafBlocks[i]);
932
933    free (FcCharLeafBlocks);
934    FcCharLeafBlocks = 0;
935    FcCharLeafBlockCount = 0;
936}
937
938typedef struct _FcCharSetEnt FcCharSetEnt;
939
940struct _FcCharSetEnt {
941    FcCharSetEnt        *next;
942    FcChar32            hash;
943    FcCharSet           set;
944};
945
946#define FC_CHAR_SET_HASH_SIZE    67
947
948static FcChar32
949FcCharSetHash (FcCharSet *fcs)
950{
951    FcChar32    hash = 0;
952    FcChar32    *p;
953    int         i;
954
955    /* hash in leaves */
956    p = (FcChar32 *) fcs->leaves;
957    for (i = 0; i < fcs->num * sizeof (FcCharLeaf *) / sizeof (FcChar32); i++)
958        hash = ((hash << 1) | (hash >> 31)) ^ *p++;
959    /* hash in numbers */
960    for (i = 0; i < fcs->num; i++)
961        hash = ((hash << 1) | (hash >> 31)) ^ fcs->numbers[i];
962    return hash;
963}
964
965static int      FcCharSetTotal;
966static int      FcCharSetUsed;
967static int      FcCharSetTotalEnts, FcCharSetUsedEnts;
968
969static FcCharSetEnt     *FcCharSetHashTable[FC_CHAR_SET_HASH_SIZE];
970
971static FcCharSet *
972FcCharSetFreezeBase (FcCharSet *fcs)
973{
974    FcChar32            hash = FcCharSetHash (fcs);
975    FcCharSetEnt        **bucket = &FcCharSetHashTable[hash % FC_CHAR_SET_HASH_SIZE];
976    FcCharSetEnt        *ent;
977    int                 size;
978
979    FcCharSetTotal++;
980    FcCharSetTotalEnts += fcs->num;
981    for (ent = *bucket; ent; ent = ent->next)
982    {
983        if (ent->hash == hash &&
984            ent->set.num == fcs->num &&
985            !memcmp (ent->set.leaves, fcs->leaves,
986                     fcs->num * sizeof (FcCharLeaf *)) &&
987            !memcmp (ent->set.numbers, fcs->numbers,
988                     fcs->num * sizeof (FcChar16)))
989        {
990            return &ent->set;
991        }
992    }
993
994    size = (sizeof (FcCharSetEnt) +
995            fcs->num * sizeof (FcCharLeaf *) +
996            fcs->num * sizeof (FcChar16));
997    ent = malloc (size);
998    if (!ent)
999        return 0;
1000    FcMemAlloc (FC_MEM_CHARSET, size);
1001    FcCharSetUsed++;
1002    FcCharSetUsedEnts += fcs->num;
1003   
1004    ent->set.ref = FC_REF_CONSTANT;
1005    ent->set.num = fcs->num;
1006    if (fcs->num)
1007    {
1008        ent->set.leaves = (FcCharLeaf **) (ent + 1);
1009        ent->set.numbers = (FcChar16 *) (ent->set.leaves + fcs->num);
1010        memcpy (ent->set.leaves, fcs->leaves, fcs->num * sizeof (FcCharLeaf *));
1011        memcpy (ent->set.numbers, fcs->numbers, fcs->num * sizeof (FcChar16));
1012    }
1013    else
1014    {
1015        ent->set.leaves = 0;
1016        ent->set.numbers = 0;
1017    }
1018
1019    ent->hash = hash;
1020    ent->next = *bucket;
1021    *bucket = ent;
1022    return &ent->set;
1023}
1024
1025void
1026FcCharSetThawAll (void)
1027{
1028    int i;
1029    FcCharSetEnt        *ent, *next;
1030
1031    for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1032    {
1033        for (ent = FcCharSetHashTable[i]; ent; ent = next)
1034        {
1035            next = ent->next;
1036            free (ent);
1037        }
1038        FcCharSetHashTable[i] = 0;
1039    }
1040
1041    FcCharSetTotal = 0;
1042    FcCharSetTotalEnts = 0;
1043    FcCharSetUsed = 0;
1044    FcCharSetUsedEnts = 0;
1045
1046    FcCharSetThawAllLeaf ();
1047}
1048
1049FcCharSet *
1050FcCharSetFreeze (FcCharSet *fcs)
1051{
1052    FcCharSet   *b;
1053    FcCharSet   *n = 0;
1054    FcCharLeaf  *l;
1055    int         i;
1056
1057    b = FcCharSetCreate ();
1058    if (!b)
1059        goto bail0;
1060    for (i = 0; i < fcs->num; i++)
1061    {
1062        l = FcCharSetFreezeLeaf (fcs->leaves[i]);
1063        if (!l)
1064            goto bail1;
1065        if (!FcCharSetInsertLeaf (b, fcs->numbers[i] << 8, l))
1066            goto bail1;
1067    }
1068    n = FcCharSetFreezeBase (b);
1069bail1:
1070    if (b->leaves)
1071    {
1072        FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *));
1073        free (b->leaves);
1074    }
1075    if (b->numbers)
1076    {
1077        FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16));
1078        free (b->numbers);
1079    }
1080    FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1081    free (b);
1082bail0:
1083    return n;
1084}
1085
1086FcCharSet *
1087FcNameParseCharSet (FcChar8 *string)
1088{
1089    FcCharSet   *c, *n = 0;
1090    FcChar32    ucs4;
1091    FcCharLeaf  *leaf;
1092    FcCharLeaf  temp;
1093    FcChar32    bits;
1094    int         i;
1095
1096    c = FcCharSetCreate ();
1097    if (!c)
1098        goto bail0;
1099    while (*string)
1100    {
1101        string = FcCharSetParseValue (string, &ucs4);
1102        if (!string)
1103            goto bail1;
1104        bits = 0;
1105        for (i = 0; i < 256/32; i++)
1106        {
1107            string = FcCharSetParseValue (string, &temp.map[i]);
1108            if (!string)
1109                goto bail1;
1110            bits |= temp.map[i];
1111        }
1112        if (bits)
1113        {
1114            leaf = FcCharSetFreezeLeaf (&temp);
1115            if (!leaf)
1116                goto bail1;
1117            if (!FcCharSetInsertLeaf (c, ucs4, leaf))
1118                goto bail1;
1119        }
1120    }
1121#ifdef CHATTY
1122    printf ("          %8s %8s %8s %8s\n", "total", "totalmem", "new", "newmem");
1123    printf ("Leaves:   %8d %8d %8d %8d\n",
1124            FcCharLeafTotal, sizeof (FcCharLeaf) * FcCharLeafTotal,
1125            FcCharLeafUsed, sizeof (FcCharLeaf) * FcCharLeafUsed);
1126    printf ("Charsets: %8d %8d %8d %8d\n",
1127            FcCharSetTotal, sizeof (FcCharSet) * FcCharSetTotal,
1128            FcCharSetUsed, sizeof (FcCharSet) * FcCharSetUsed);
1129    printf ("Tables:   %8d %8d %8d %8d\n",
1130            FcCharSetTotalEnts, FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
1131            FcCharSetUsedEnts, FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
1132    printf ("Total:    %8s %8d %8s %8d\n", 
1133            "", 
1134            sizeof (FcCharLeaf) * FcCharLeafTotal +
1135            sizeof (FcCharSet) * FcCharSetTotal +
1136            FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
1137            "",
1138            sizeof (FcCharLeaf) * FcCharLeafUsed +
1139            sizeof (FcCharSet) * FcCharSetUsed +
1140            FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
1141#endif
1142    n = FcCharSetFreezeBase (c);
1143bail1:
1144    if (c->leaves)
1145    {
1146        FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
1147        free (c->leaves);
1148    }
1149    if (c->numbers)
1150    {
1151        FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
1152        free (c->numbers);
1153    }
1154    FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1155    free (c);
1156bail0:
1157    return n;
1158}
1159
1160FcBool
1161FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
1162{
1163    FcCharSetIter   ci;
1164    int             i;
1165#ifdef CHECK
1166    int             len = buf->len;
1167#endif
1168
1169    for (FcCharSetIterStart (c, &ci);
1170         ci.leaf;
1171         FcCharSetIterNext (c, &ci))
1172    {
1173        if (!FcCharSetUnparseValue (buf, ci.ucs4))
1174            return FcFalse;
1175        for (i = 0; i < 256/32; i++)
1176            if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
1177                return FcFalse;
1178    }
1179#ifdef CHECK
1180    {
1181        FcCharSet       *check;
1182        FcChar32        missing;
1183        FcCharSetIter   ci, checki;
1184       
1185        /* null terminate for parser */
1186        FcStrBufChar (buf, '\0');
1187        /* step back over null for life after test */
1188        buf->len--;
1189        check = FcNameParseCharSet (buf->buf + len);
1190        FcCharSetIterStart (c, &ci);
1191        FcCharSetIterStart (check, &checki);
1192        while (ci.leaf || checki.leaf)
1193        {
1194            if (ci.ucs4 < checki.ucs4)
1195            {
1196                printf ("Missing leaf node at 0x%x\n", ci.ucs4);
1197                FcCharSetIterNext (c, &ci);
1198            }
1199            else if (checki.ucs4 < ci.ucs4)
1200            {
1201                printf ("Extra leaf node at 0x%x\n", checki.ucs4);
1202                FcCharSetIterNext (check, &checki);
1203            }
1204            else
1205            {
1206                int         i = 256/32;
1207                FcChar32    *cm = ci.leaf->map;
1208                FcChar32    *checkm = checki.leaf->map;
1209
1210                for (i = 0; i < 256; i += 32)
1211                {
1212                    if (*cm != *checkm)
1213                        printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
1214                                ci.ucs4 + i, *cm, *checkm);
1215                    cm++;
1216                    checkm++;
1217                }
1218                FcCharSetIterNext (c, &ci);
1219                FcCharSetIterNext (check, &checki);
1220            }
1221        }
1222        if ((missing = FcCharSetSubtractCount (c, check)))
1223            printf ("%d missing in reparsed result\n", missing);
1224        if ((missing = FcCharSetSubtractCount (check, c)))
1225            printf ("%d extra in reparsed result\n", missing);
1226        FcCharSetDestroy (check);
1227    }
1228#endif
1229   
1230    return FcTrue;
1231}
Note: See TracBrowser for help on using the repository browser.