Undo an old change in freetype to account for size of USHORT
[pdfium.git] / core / src / fxge / fx_freetype / fxft2.5.01 / src / sfnt / ttcmap.c
1 /***************************************************************************/
2 /*                                                                         */
3 /*  ttcmap.c                                                               */
4 /*                                                                         */
5 /*    TrueType character mapping table (cmap) support (body).              */
6 /*                                                                         */
7 /*  Copyright 2002-2010, 2012, 2013 by                                     */
8 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
9 /*                                                                         */
10 /*  This file is part of the FreeType project, and may only be used,       */
11 /*  modified, and distributed under the terms of the FreeType project      */
12 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
13 /*  this file you indicate that you have read the license and              */
14 /*  understand and accept it fully.                                        */
15 /*                                                                         */
16 /***************************************************************************/
17
18
19 #include "../../include/ft2build.h"
20 #include "../../include/freetype/internal/ftdebug.h"
21
22 #include "sferrors.h"           /* must come before FT_INTERNAL_VALIDATE_H */
23
24 #include "../../include/freetype/internal/ftvalid.h"
25 #include "../../include/freetype/internal/ftstream.h"
26 #include "ttload.h"
27 #include "ttcmap.h"
28 #include "sfntpic.h"
29
30
31   /*************************************************************************/
32   /*                                                                       */
33   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
34   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
35   /* messages during execution.                                            */
36   /*                                                                       */
37 #undef  FT_COMPONENT
38 #define FT_COMPONENT  trace_ttcmap
39
40
41 #define TT_PEEK_SHORT   FT_PEEK_SHORT
42 #define TT_PEEK_USHORT  FT_PEEK_USHORT
43 #define TT_PEEK_UINT24  FT_PEEK_UOFF3
44 #define TT_PEEK_LONG    FT_PEEK_LONG
45 #define TT_PEEK_ULONG   FT_PEEK_ULONG
46
47 #define TT_NEXT_SHORT   FT_NEXT_SHORT
48 #define TT_NEXT_USHORT  FT_NEXT_USHORT
49 #define TT_NEXT_UINT24  FT_NEXT_UOFF3
50 #define TT_NEXT_LONG    FT_NEXT_LONG
51 #define TT_NEXT_ULONG   FT_NEXT_ULONG
52
53
54   FT_CALLBACK_DEF( FT_Error )
55   tt_cmap_init( TT_CMap   cmap,
56                 FT_Byte*  table )
57   {
58     cmap->data = table;
59     return FT_Err_Ok;
60   }
61
62
63   /*************************************************************************/
64   /*************************************************************************/
65   /*****                                                               *****/
66   /*****                           FORMAT 0                            *****/
67   /*****                                                               *****/
68   /*************************************************************************/
69   /*************************************************************************/
70
71   /*************************************************************************/
72   /*                                                                       */
73   /* TABLE OVERVIEW                                                        */
74   /* --------------                                                        */
75   /*                                                                       */
76   /*   NAME        OFFSET         TYPE          DESCRIPTION                */
77   /*                                                                       */
78   /*   format      0              USHORT        must be 0                  */
79   /*   length      2              USHORT        table length in bytes      */
80   /*   language    4              USHORT        Mac language code          */
81   /*   glyph_ids   6              BYTE[256]     array of glyph indices     */
82   /*               262                                                     */
83   /*                                                                       */
84
85 #ifdef TT_CONFIG_CMAP_FORMAT_0
86
87   FT_CALLBACK_DEF( FT_Error )
88   tt_cmap0_validate( FT_Byte*      table,
89                      FT_Validator  valid )
90   {
91     FT_Byte*  p      = table + 2;
92     FT_UInt   length = TT_NEXT_USHORT( p );
93
94
95     if ( table + length > valid->limit || length < 262 )
96       FT_INVALID_TOO_SHORT;
97
98     /* check glyph indices whenever necessary */
99     if ( valid->level >= FT_VALIDATE_TIGHT )
100     {
101       FT_UInt  n, idx;
102
103
104       p = table + 6;
105       for ( n = 0; n < 256; n++ )
106       {
107         idx = *p++;
108         if ( idx >= TT_VALID_GLYPH_COUNT( valid ) )
109           FT_INVALID_GLYPH_ID;
110       }
111     }
112
113     return FT_Err_Ok;
114   }
115
116
117   FT_CALLBACK_DEF( FT_UInt )
118   tt_cmap0_char_index( TT_CMap    cmap,
119                        FT_UInt32  char_code )
120   {
121     FT_Byte*  table = cmap->data;
122
123
124     return char_code < 256 ? table[6 + char_code] : 0;
125   }
126
127
128   FT_CALLBACK_DEF( FT_UInt32 )
129   tt_cmap0_char_next( TT_CMap     cmap,
130                       FT_UInt32  *pchar_code )
131   {
132     FT_Byte*   table    = cmap->data;
133     FT_UInt32  charcode = *pchar_code;
134     FT_UInt32  result   = 0;
135     FT_UInt    gindex   = 0;
136
137
138     table += 6;  /* go to glyph IDs */
139     while ( ++charcode < 256 )
140     {
141       gindex = table[charcode];
142       if ( gindex != 0 )
143       {
144         result = charcode;
145         break;
146       }
147     }
148
149     *pchar_code = result;
150     return gindex;
151   }
152
153
154   FT_CALLBACK_DEF( FT_Error )
155   tt_cmap0_get_info( TT_CMap       cmap,
156                      TT_CMapInfo  *cmap_info )
157   {
158     FT_Byte*  p = cmap->data + 4;
159
160
161     cmap_info->format   = 0;
162     cmap_info->language = (FT_ULong)TT_PEEK_USHORT( p );
163
164     return FT_Err_Ok;
165   }
166
167
168   FT_DEFINE_TT_CMAP(
169     tt_cmap0_class_rec,
170     sizeof ( TT_CMapRec ),
171
172     (FT_CMap_InitFunc)     tt_cmap_init,
173     (FT_CMap_DoneFunc)     NULL,
174     (FT_CMap_CharIndexFunc)tt_cmap0_char_index,
175     (FT_CMap_CharNextFunc) tt_cmap0_char_next,
176
177     NULL,
178     NULL,
179     NULL,
180     NULL,
181     NULL,
182
183     0,
184     (TT_CMap_ValidateFunc)tt_cmap0_validate,
185     (TT_CMap_Info_GetFunc)tt_cmap0_get_info )
186
187 #endif /* TT_CONFIG_CMAP_FORMAT_0 */
188
189
190   /*************************************************************************/
191   /*************************************************************************/
192   /*****                                                               *****/
193   /*****                          FORMAT 2                             *****/
194   /*****                                                               *****/
195   /***** This is used for certain CJK encodings that encode text in a  *****/
196   /***** mixed 8/16 bits encoding along the following lines:           *****/
197   /*****                                                               *****/
198   /***** * Certain byte values correspond to an 8-bit character code   *****/
199   /*****   (typically in the range 0..127 for ASCII compatibility).    *****/
200   /*****                                                               *****/
201   /***** * Certain byte values signal the first byte of a 2-byte       *****/
202   /*****   character code (but these values are also valid as the      *****/
203   /*****   second byte of a 2-byte character).                         *****/
204   /*****                                                               *****/
205   /***** The following charmap lookup and iteration functions all      *****/
206   /***** assume that the value "charcode" correspond to following:     *****/
207   /*****                                                               *****/
208   /*****   - For one byte characters, "charcode" is simply the         *****/
209   /*****     character code.                                           *****/
210   /*****                                                               *****/
211   /*****   - For two byte characters, "charcode" is the 2-byte         *****/
212   /*****     character code in big endian format.  More exactly:       *****/
213   /*****                                                               *****/
214   /*****       (charcode >> 8)    is the first byte value              *****/
215   /*****       (charcode & 0xFF)  is the second byte value             *****/
216   /*****                                                               *****/
217   /***** Note that not all values of "charcode" are valid according    *****/
218   /***** to these rules, and the function moderately check the         *****/
219   /***** arguments.                                                    *****/
220   /*****                                                               *****/
221   /*************************************************************************/
222   /*************************************************************************/
223
224   /*************************************************************************/
225   /*                                                                       */
226   /* TABLE OVERVIEW                                                        */
227   /* --------------                                                        */
228   /*                                                                       */
229   /*   NAME        OFFSET         TYPE            DESCRIPTION              */
230   /*                                                                       */
231   /*   format      0              USHORT          must be 2                */
232   /*   length      2              USHORT          table length in bytes    */
233   /*   language    4              USHORT          Mac language code        */
234   /*   keys        6              USHORT[256]     sub-header keys          */
235   /*   subs        518            SUBHEAD[NSUBS]  sub-headers array        */
236   /*   glyph_ids   518+NSUB*8     USHORT[]        glyph ID array           */
237   /*                                                                       */
238   /* The `keys' table is used to map charcode high-bytes to sub-headers.   */
239   /* The value of `NSUBS' is the number of sub-headers defined in the      */
240   /* table and is computed by finding the maximum of the `keys' table.     */
241   /*                                                                       */
242   /* Note that for any n, `keys[n]' is a byte offset within the `subs'     */
243   /* table, i.e., it is the corresponding sub-header index multiplied      */
244   /* by 8.                                                                 */
245   /*                                                                       */
246   /* Each sub-header has the following format:                             */
247   /*                                                                       */
248   /*   NAME        OFFSET      TYPE            DESCRIPTION                 */
249   /*                                                                       */
250   /*   first       0           USHORT          first valid low-byte        */
251   /*   count       2           USHORT          number of valid low-bytes   */
252   /*   delta       4           SHORT           see below                   */
253   /*   offset      6           USHORT          see below                   */
254   /*                                                                       */
255   /* A sub-header defines, for each high-byte, the range of valid          */
256   /* low-bytes within the charmap.  Note that the range defined by `first' */
257   /* and `count' must be completely included in the interval [0..255]      */
258   /* according to the specification.                                       */
259   /*                                                                       */
260   /* If a character code is contained within a given sub-header, then      */
261   /* mapping it to a glyph index is done as follows:                       */
262   /*                                                                       */
263   /* * The value of `offset' is read.  This is a _byte_ distance from the  */
264   /*   location of the `offset' field itself into a slice of the           */
265   /*   `glyph_ids' table.  Let's call it `slice' (it is a USHORT[] too).   */
266   /*                                                                       */
267   /* * The value `slice[char.lo - first]' is read.  If it is 0, there is   */
268   /*   no glyph for the charcode.  Otherwise, the value of `delta' is      */
269   /*   added to it (modulo 65536) to form a new glyph index.               */
270   /*                                                                       */
271   /* It is up to the validation routine to check that all offsets fall     */
272   /* within the glyph IDs table (and not within the `subs' table itself or */
273   /* outside of the CMap).                                                 */
274   /*                                                                       */
275
276 #ifdef TT_CONFIG_CMAP_FORMAT_2
277
278   FT_CALLBACK_DEF( FT_Error )
279   tt_cmap2_validate( FT_Byte*      table,
280                      FT_Validator  valid )
281   {
282     FT_Byte*  p      = table + 2;           /* skip format */
283     FT_UInt   length = TT_PEEK_USHORT( p );
284     FT_UInt   n, max_subs;
285     FT_Byte*  keys;                         /* keys table */
286     FT_Byte*  subs;                         /* sub-headers */
287     FT_Byte*  glyph_ids;                    /* glyph ID array */
288
289
290     if ( table + length > valid->limit || length < 6 + 512 )
291       FT_INVALID_TOO_SHORT;
292
293     keys = table + 6;
294
295     /* parse keys to compute sub-headers count */
296     p        = keys;
297     max_subs = 0;
298     for ( n = 0; n < 256; n++ )
299     {
300       FT_UInt  idx = TT_NEXT_USHORT( p );
301
302
303       /* value must be multiple of 8 */
304       if ( valid->level >= FT_VALIDATE_PARANOID && ( idx & 7 ) != 0 )
305         FT_INVALID_DATA;
306
307       idx >>= 3;
308
309       if ( idx > max_subs )
310         max_subs = idx;
311     }
312
313     FT_ASSERT( p == table + 518 );
314
315     subs      = p;
316     glyph_ids = subs + (max_subs + 1) * 8;
317     if ( glyph_ids > valid->limit )
318       FT_INVALID_TOO_SHORT;
319
320     /* parse sub-headers */
321     for ( n = 0; n <= max_subs; n++ )
322     {
323       FT_UInt   first_code, code_count, offset;
324       FT_Int    delta;
325       FT_Byte*  ids;
326
327
328       first_code = TT_NEXT_USHORT( p );
329       code_count = TT_NEXT_USHORT( p );
330       delta      = TT_NEXT_SHORT( p );
331       offset     = TT_NEXT_USHORT( p );
332
333       /* many Dynalab fonts have empty sub-headers */
334       if ( code_count == 0 )
335         continue;
336
337       /* check range within 0..255 */
338       if ( valid->level >= FT_VALIDATE_PARANOID )
339       {
340         if ( first_code >= 256 || first_code + code_count > 256 )
341           FT_INVALID_DATA;
342       }
343
344       /* check offset */
345       if ( offset != 0 )
346       {
347         ids = p - 2 + offset;
348         if ( ids < glyph_ids || ids + code_count*2 > table + length )
349           FT_INVALID_OFFSET;
350
351         /* check glyph IDs */
352         if ( valid->level >= FT_VALIDATE_TIGHT )
353         {
354           FT_Byte*  limit = p + code_count * 2;
355           FT_UInt   idx;
356
357
358           for ( ; p < limit; )
359           {
360             idx = TT_NEXT_USHORT( p );
361             if ( idx != 0 )
362             {
363               idx = ( idx + delta ) & 0xFFFFU;
364               if ( idx >= TT_VALID_GLYPH_COUNT( valid ) )
365                 FT_INVALID_GLYPH_ID;
366             }
367           }
368         }
369       }
370     }
371
372     return FT_Err_Ok;
373   }
374
375
376   /* return sub header corresponding to a given character code */
377   /* NULL on invalid charcode                                  */
378   static FT_Byte*
379   tt_cmap2_get_subheader( FT_Byte*   table,
380                           FT_UInt32  char_code )
381   {
382     FT_Byte*  result = NULL;
383
384
385     if ( char_code < 0x10000UL )
386     {
387       FT_UInt   char_lo = (FT_UInt)( char_code & 0xFF );
388       FT_UInt   char_hi = (FT_UInt)( char_code >> 8 );
389       FT_Byte*  p       = table + 6;    /* keys table */
390       FT_Byte*  subs    = table + 518;  /* subheaders table */
391       FT_Byte*  sub;
392
393
394       if ( char_hi == 0 )
395       {
396         /* an 8-bit character code -- we use subHeader 0 in this case */
397         /* to test whether the character code is in the charmap       */
398         /*                                                            */
399         sub = subs;  /* jump to first sub-header */
400
401         /* check that the sub-header for this byte is 0, which */
402         /* indicates that it is really a valid one-byte value  */
403         /* Otherwise, return 0                                 */
404         /*                                                     */
405         p += char_lo * 2;
406         if ( TT_PEEK_USHORT( p ) != 0 )
407           goto Exit;
408       }
409       else
410       {
411         /* a 16-bit character code */
412
413         /* jump to key entry  */
414         p  += char_hi * 2;
415         /* jump to sub-header */
416         sub = subs + ( FT_PAD_FLOOR( TT_PEEK_USHORT( p ), 8 ) );
417
418         /* check that the high byte isn't a valid one-byte value */
419         if ( sub == subs )
420           goto Exit;
421       }
422       result = sub;
423     }
424   Exit:
425     return result;
426   }
427
428
429   FT_CALLBACK_DEF( FT_UInt )
430   tt_cmap2_char_index( TT_CMap    cmap,
431                        FT_UInt32  char_code )
432   {
433     FT_Byte*  table   = cmap->data;
434     FT_UInt   result  = 0;
435     FT_Byte*  subheader;
436
437
438     subheader = tt_cmap2_get_subheader( table, char_code );
439     if ( subheader )
440     {
441       FT_Byte*  p   = subheader;
442       FT_UInt   idx = (FT_UInt)(char_code & 0xFF);
443       FT_UInt   start, count;
444       FT_Int    delta;
445       FT_UInt   offset;
446
447
448       start  = TT_NEXT_USHORT( p );
449       count  = TT_NEXT_USHORT( p );
450       delta  = TT_NEXT_SHORT ( p );
451       offset = TT_PEEK_USHORT( p );
452
453       idx -= start;
454       if ( idx < count && offset != 0 )
455       {
456         p  += offset + 2 * idx;
457         idx = TT_PEEK_USHORT( p );
458
459         if ( idx != 0 )
460           result = (FT_UInt)( idx + delta ) & 0xFFFFU;
461       }
462     }
463     return result;
464   }
465
466
467   FT_CALLBACK_DEF( FT_UInt32 )
468   tt_cmap2_char_next( TT_CMap     cmap,
469                       FT_UInt32  *pcharcode )
470   {
471     FT_Byte*   table    = cmap->data;
472     FT_UInt    gindex   = 0;
473     FT_UInt32  result   = 0;
474     FT_UInt32  charcode = *pcharcode + 1;
475     FT_Byte*   subheader;
476
477
478     while ( charcode < 0x10000UL )
479     {
480       subheader = tt_cmap2_get_subheader( table, charcode );
481       if ( subheader )
482       {
483         FT_Byte*  p       = subheader;
484         FT_UInt   start   = TT_NEXT_USHORT( p );
485         FT_UInt   count   = TT_NEXT_USHORT( p );
486         FT_Int    delta   = TT_NEXT_SHORT ( p );
487         FT_UInt   offset  = TT_PEEK_USHORT( p );
488         FT_UInt   char_lo = (FT_UInt)( charcode & 0xFF );
489         FT_UInt   pos, idx;
490
491
492         if ( offset == 0 )
493           goto Next_SubHeader;
494
495         if ( char_lo < start )
496         {
497           char_lo = start;
498           pos     = 0;
499         }
500         else
501           pos = (FT_UInt)( char_lo - start );
502
503         p       += offset + pos * 2;
504         charcode = FT_PAD_FLOOR( charcode, 256 ) + char_lo;
505
506         for ( ; pos < count; pos++, charcode++ )
507         {
508           idx = TT_NEXT_USHORT( p );
509
510           if ( idx != 0 )
511           {
512             gindex = ( idx + delta ) & 0xFFFFU;
513             if ( gindex != 0 )
514             {
515               result = charcode;
516               goto Exit;
517             }
518           }
519         }
520       }
521
522       /* jump to next sub-header, i.e. higher byte value */
523     Next_SubHeader:
524       charcode = FT_PAD_FLOOR( charcode, 256 ) + 256;
525     }
526
527   Exit:
528     *pcharcode = result;
529
530     return gindex;
531   }
532
533
534   FT_CALLBACK_DEF( FT_Error )
535   tt_cmap2_get_info( TT_CMap       cmap,
536                      TT_CMapInfo  *cmap_info )
537   {
538     FT_Byte*  p = cmap->data + 4;
539
540
541     cmap_info->format   = 2;
542     cmap_info->language = (FT_ULong)TT_PEEK_USHORT( p );
543
544     return FT_Err_Ok;
545   }
546
547
548   FT_DEFINE_TT_CMAP(
549     tt_cmap2_class_rec,
550     sizeof ( TT_CMapRec ),
551
552     (FT_CMap_InitFunc)     tt_cmap_init,
553     (FT_CMap_DoneFunc)     NULL,
554     (FT_CMap_CharIndexFunc)tt_cmap2_char_index,
555     (FT_CMap_CharNextFunc) tt_cmap2_char_next,
556
557     NULL,
558     NULL,
559     NULL,
560     NULL,
561     NULL,
562
563     2,
564     (TT_CMap_ValidateFunc)tt_cmap2_validate,
565     (TT_CMap_Info_GetFunc)tt_cmap2_get_info )
566
567 #endif /* TT_CONFIG_CMAP_FORMAT_2 */
568
569
570   /*************************************************************************/
571   /*************************************************************************/
572   /*****                                                               *****/
573   /*****                           FORMAT 4                            *****/
574   /*****                                                               *****/
575   /*************************************************************************/
576   /*************************************************************************/
577
578   /*************************************************************************/
579   /*                                                                       */
580   /* TABLE OVERVIEW                                                        */
581   /* --------------                                                        */
582   /*                                                                       */
583   /*   NAME          OFFSET         TYPE              DESCRIPTION          */
584   /*                                                                       */
585   /*   format        0              USHORT            must be 4            */
586   /*   length        2              USHORT            table length         */
587   /*                                                  in bytes             */
588   /*   language      4              USHORT            Mac language code    */
589   /*                                                                       */
590   /*   segCountX2    6              USHORT            2*NUM_SEGS           */
591   /*   searchRange   8              USHORT            2*(1 << LOG_SEGS)    */
592   /*   entrySelector 10             USHORT            LOG_SEGS             */
593   /*   rangeShift    12             USHORT            segCountX2 -         */
594   /*                                                    searchRange        */
595   /*                                                                       */
596   /*   endCount      14             USHORT[NUM_SEGS]  end charcode for     */
597   /*                                                  each segment; last   */
598   /*                                                  is 0xFFFF            */
599   /*                                                                       */
600   /*   pad           14+NUM_SEGS*2  USHORT            padding              */
601   /*                                                                       */
602   /*   startCount    16+NUM_SEGS*2  USHORT[NUM_SEGS]  first charcode for   */
603   /*                                                  each segment         */
604   /*                                                                       */
605   /*   idDelta       16+NUM_SEGS*4  SHORT[NUM_SEGS]   delta for each       */
606   /*                                                  segment              */
607   /*   idOffset      16+NUM_SEGS*6  SHORT[NUM_SEGS]   range offset for     */
608   /*                                                  each segment; can be */
609   /*                                                  zero                 */
610   /*                                                                       */
611   /*   glyphIds      16+NUM_SEGS*8  USHORT[]          array of glyph ID    */
612   /*                                                  ranges               */
613   /*                                                                       */
614   /* Character codes are modelled by a series of ordered (increasing)      */
615   /* intervals called segments.  Each segment has start and end codes,     */
616   /* provided by the `startCount' and `endCount' arrays.  Segments must    */
617   /* not overlap, and the last segment should always contain the value     */
618   /* 0xFFFF for `endCount'.                                                */
619   /*                                                                       */
620   /* The fields `searchRange', `entrySelector' and `rangeShift' are better */
621   /* ignored (they are traces of over-engineering in the TrueType          */
622   /* specification).                                                       */
623   /*                                                                       */
624   /* Each segment also has a signed `delta', as well as an optional offset */
625   /* within the `glyphIds' table.                                          */
626   /*                                                                       */
627   /* If a segment's idOffset is 0, the glyph index corresponding to any    */
628   /* charcode within the segment is obtained by adding the value of        */
629   /* `idDelta' directly to the charcode, modulo 65536.                     */
630   /*                                                                       */
631   /* Otherwise, a glyph index is taken from the glyph IDs sub-array for    */
632   /* the segment, and the value of `idDelta' is added to it.               */
633   /*                                                                       */
634   /*                                                                       */
635   /* Finally, note that a lot of fonts contain an invalid last segment,    */
636   /* where `start' and `end' are correctly set to 0xFFFF but both `delta'  */
637   /* and `offset' are incorrect (e.g., `opens___.ttf' which comes with     */
638   /* OpenOffice.org).  We need special code to deal with them correctly.   */
639   /*                                                                       */
640
641 #ifdef TT_CONFIG_CMAP_FORMAT_4
642
643   typedef struct  TT_CMap4Rec_
644   {
645     TT_CMapRec  cmap;
646     FT_UInt32   cur_charcode;   /* current charcode */
647     FT_UInt     cur_gindex;     /* current glyph index */
648
649     FT_UInt     num_ranges;
650     FT_UInt     cur_range;
651     FT_UInt     cur_start;
652     FT_UInt     cur_end;
653     FT_Int      cur_delta;
654     FT_Byte*    cur_values;
655
656   } TT_CMap4Rec, *TT_CMap4;
657
658
659   FT_CALLBACK_DEF( FT_Error )
660   tt_cmap4_init( TT_CMap4  cmap,
661                  FT_Byte*  table )
662   {
663     FT_Byte*  p;
664
665
666     cmap->cmap.data    = table;
667
668     p                  = table + 6;
669     cmap->num_ranges   = FT_PEEK_USHORT( p ) >> 1;
670     cmap->cur_charcode = (FT_UInt32)0xFFFFFFFFUL;
671     cmap->cur_gindex   = 0;
672
673     return FT_Err_Ok;
674   }
675
676
677   static FT_Int
678   tt_cmap4_set_range( TT_CMap4  cmap,
679                       FT_UInt   range_index )
680   {
681     FT_Byte*  table = cmap->cmap.data;
682     FT_Byte*  p;
683     FT_UInt   num_ranges = cmap->num_ranges;
684
685
686     while ( range_index < num_ranges )
687     {
688       FT_UInt  offset;
689
690
691       p             = table + 14 + range_index * 2;
692       cmap->cur_end = FT_PEEK_USHORT( p );
693
694       p              += 2 + num_ranges * 2;
695       cmap->cur_start = FT_PEEK_USHORT( p );
696
697       p              += num_ranges * 2;
698       cmap->cur_delta = FT_PEEK_SHORT( p );
699
700       p     += num_ranges * 2;
701       offset = FT_PEEK_USHORT( p );
702
703       /* some fonts have an incorrect last segment; */
704       /* we have to catch it                        */
705       if ( range_index     >= num_ranges - 1 &&
706            cmap->cur_start == 0xFFFFU        &&
707            cmap->cur_end   == 0xFFFFU        )
708       {
709         TT_Face   face  = (TT_Face)cmap->cmap.cmap.charmap.face;
710         FT_Byte*  limit = face->cmap_table + face->cmap_size;
711
712
713         if ( offset && p + offset + 2 > limit )
714         {
715           cmap->cur_delta = 1;
716           offset          = 0;
717         }
718       }
719
720       if ( offset != 0xFFFFU )
721       {
722         cmap->cur_values = offset ? p + offset : NULL;
723         cmap->cur_range  = range_index;
724         return 0;
725       }
726
727       /* we skip empty segments */
728       range_index++;
729     }
730
731     return -1;
732   }
733
734
735   /* search the index of the charcode next to cmap->cur_charcode; */
736   /* caller should call tt_cmap4_set_range with proper range      */
737   /* before calling this function                                 */
738   /*                                                              */
739   static void
740   tt_cmap4_next( TT_CMap4  cmap )
741   {
742     FT_UInt  charcode;
743
744
745     if ( cmap->cur_charcode >= 0xFFFFUL )
746       goto Fail;
747
748     charcode = (FT_UInt)cmap->cur_charcode + 1;
749
750     if ( charcode < cmap->cur_start )
751       charcode = cmap->cur_start;
752
753     for ( ;; )
754     {
755       FT_Byte*  values = cmap->cur_values;
756       FT_UInt   end    = cmap->cur_end;
757       FT_Int    delta  = cmap->cur_delta;
758
759
760       if ( charcode <= end )
761       {
762         if ( values )
763         {
764           FT_Byte*  p = values + 2 * ( charcode - cmap->cur_start );
765
766
767           do
768           {
769             FT_UInt  gindex = FT_NEXT_USHORT( p );
770
771
772             if ( gindex != 0 )
773             {
774               gindex = (FT_UInt)( ( gindex + delta ) & 0xFFFFU );
775               if ( gindex != 0 )
776               {
777                 cmap->cur_charcode = charcode;
778                 cmap->cur_gindex   = gindex;
779                 return;
780               }
781             }
782           } while ( ++charcode <= end );
783         }
784         else
785         {
786           do
787           {
788             FT_UInt  gindex = (FT_UInt)( ( charcode + delta ) & 0xFFFFU );
789
790
791             if ( gindex != 0 )
792             {
793               cmap->cur_charcode = charcode;
794               cmap->cur_gindex   = gindex;
795               return;
796             }
797           } while ( ++charcode <= end );
798         }
799       }
800
801       /* we need to find another range */
802       if ( tt_cmap4_set_range( cmap, cmap->cur_range + 1 ) < 0 )
803         break;
804
805       if ( charcode < cmap->cur_start )
806         charcode = cmap->cur_start;
807     }
808
809   Fail:
810     cmap->cur_charcode = (FT_UInt32)0xFFFFFFFFUL;
811     cmap->cur_gindex   = 0;
812   }
813
814
815   FT_CALLBACK_DEF( FT_Error )
816   tt_cmap4_validate( FT_Byte*      table,
817                      FT_Validator  valid )
818   {
819     FT_Byte*  p      = table + 2;               /* skip format */
820     FT_UInt   length = TT_NEXT_USHORT( p );
821     FT_Byte   *ends, *starts, *offsets, *deltas, *glyph_ids;
822     FT_UInt   num_segs;
823     FT_Error  error = FT_Err_Ok;
824
825
826     if ( length < 16 )
827       FT_INVALID_TOO_SHORT;
828
829     /* in certain fonts, the `length' field is invalid and goes */
830     /* out of bound.  We try to correct this here...            */
831     if ( table + length > valid->limit )
832     {
833       if ( valid->level >= FT_VALIDATE_TIGHT )
834         FT_INVALID_TOO_SHORT;
835
836       length = (FT_UInt)( valid->limit - table );
837     }
838
839     p        = table + 6;
840     num_segs = TT_NEXT_USHORT( p );   /* read segCountX2 */
841
842     if ( valid->level >= FT_VALIDATE_PARANOID )
843     {
844       /* check that we have an even value here */
845       if ( num_segs & 1 )
846         FT_INVALID_DATA;
847     }
848
849     num_segs /= 2;
850
851     if ( length < 16 + num_segs * 2 * 4 )
852       FT_INVALID_TOO_SHORT;
853
854     /* check the search parameters - even though we never use them */
855     /*                                                             */
856     if ( valid->level >= FT_VALIDATE_PARANOID )
857     {
858       /* check the values of `searchRange', `entrySelector', `rangeShift' */
859       FT_UInt  search_range   = TT_NEXT_USHORT( p );
860       FT_UInt  entry_selector = TT_NEXT_USHORT( p );
861       FT_UInt  range_shift    = TT_NEXT_USHORT( p );
862
863
864       if ( ( search_range | range_shift ) & 1 )  /* must be even values */
865         FT_INVALID_DATA;
866
867       search_range /= 2;
868       range_shift  /= 2;
869
870       /* `search range' is the greatest power of 2 that is <= num_segs */
871
872       if ( search_range                > num_segs                 ||
873            search_range * 2            < num_segs                 ||
874            search_range + range_shift != num_segs                 ||
875            search_range               != ( 1U << entry_selector ) )
876         FT_INVALID_DATA;
877     }
878
879     ends      = table   + 14;
880     starts    = table   + 16 + num_segs * 2;
881     deltas    = starts  + num_segs * 2;
882     offsets   = deltas  + num_segs * 2;
883     glyph_ids = offsets + num_segs * 2;
884
885     /* check last segment; its end count value must be 0xFFFF */
886     if ( valid->level >= FT_VALIDATE_PARANOID )
887     {
888       p = ends + ( num_segs - 1 ) * 2;
889       if ( TT_PEEK_USHORT( p ) != 0xFFFFU )
890         FT_INVALID_DATA;
891     }
892
893     {
894       FT_UInt   start, end, offset, n;
895       FT_UInt   last_start = 0, last_end = 0;
896       FT_Int    delta;
897       FT_Byte*  p_start   = starts;
898       FT_Byte*  p_end     = ends;
899       FT_Byte*  p_delta   = deltas;
900       FT_Byte*  p_offset  = offsets;
901
902
903       for ( n = 0; n < num_segs; n++ )
904       {
905         p      = p_offset;
906         start  = TT_NEXT_USHORT( p_start );
907         end    = TT_NEXT_USHORT( p_end );
908         delta  = TT_NEXT_SHORT( p_delta );
909         offset = TT_NEXT_USHORT( p_offset );
910
911         if ( start > end )
912           FT_INVALID_DATA;
913
914         /* this test should be performed at default validation level; */
915         /* unfortunately, some popular Asian fonts have overlapping   */
916         /* ranges in their charmaps                                   */
917         /*                                                            */
918         if ( start <= last_end && n > 0 )
919         {
920           if ( valid->level >= FT_VALIDATE_TIGHT )
921             FT_INVALID_DATA;
922           else
923           {
924             /* allow overlapping segments, provided their start points */
925             /* and end points, respectively, are in ascending order    */
926             /*                                                         */
927             if ( last_start > start || last_end > end )
928               error |= TT_CMAP_FLAG_UNSORTED;
929             else
930               error |= TT_CMAP_FLAG_OVERLAPPING;
931           }
932         }
933
934         if ( offset && offset != 0xFFFFU )
935         {
936           p += offset;  /* start of glyph ID array */
937
938           /* check that we point within the glyph IDs table only */
939           if ( valid->level >= FT_VALIDATE_TIGHT )
940           {
941             if ( p < glyph_ids                                ||
942                  p + ( end - start + 1 ) * 2 > table + length )
943               FT_INVALID_DATA;
944           }
945           /* Some fonts handle the last segment incorrectly.  In */
946           /* theory, 0xFFFF might point to an ordinary glyph --  */
947           /* a cmap 4 is versatile and could be used for any     */
948           /* encoding, not only Unicode.  However, reality shows */
949           /* that far too many fonts are sloppy and incorrectly  */
950           /* set all fields but `start' and `end' for the last   */
951           /* segment if it contains only a single character.     */
952           /*                                                     */
953           /* We thus omit the test here, delaying it to the      */
954           /* routines which actually access the cmap.            */
955           else if ( n != num_segs - 1                       ||
956                     !( start == 0xFFFFU && end == 0xFFFFU ) )
957           {
958             if ( p < glyph_ids                              ||
959                  p + ( end - start + 1 ) * 2 > valid->limit )
960               FT_INVALID_DATA;
961           }
962
963           /* check glyph indices within the segment range */
964           if ( valid->level >= FT_VALIDATE_TIGHT )
965           {
966             FT_UInt  i, idx;
967
968
969             for ( i = start; i < end; i++ )
970             {
971               idx = FT_NEXT_USHORT( p );
972               if ( idx != 0 )
973               {
974                 idx = (FT_UInt)( idx + delta ) & 0xFFFFU;
975
976                 if ( idx >= TT_VALID_GLYPH_COUNT( valid ) )
977                   FT_INVALID_GLYPH_ID;
978               }
979             }
980           }
981         }
982         else if ( offset == 0xFFFFU )
983         {
984           /* some fonts (erroneously?) use a range offset of 0xFFFF */
985           /* to mean missing glyph in cmap table                    */
986           /*                                                        */
987           if ( valid->level >= FT_VALIDATE_PARANOID    ||
988                n != num_segs - 1                       ||
989                !( start == 0xFFFFU && end == 0xFFFFU ) )
990             FT_INVALID_DATA;
991         }
992
993         last_start = start;
994         last_end   = end;
995       }
996     }
997
998     return error;
999   }
1000
1001
1002   static FT_UInt
1003   tt_cmap4_char_map_linear( TT_CMap     cmap,
1004                             FT_UInt32*  pcharcode,
1005                             FT_Bool     next )
1006   {
1007     FT_UInt    num_segs2, start, end, offset;
1008     FT_Int     delta;
1009     FT_UInt    i, num_segs;
1010     FT_UInt32  charcode = *pcharcode;
1011     FT_UInt    gindex   = 0;
1012     FT_Byte*   p;
1013
1014
1015     p = cmap->data + 6;
1016     num_segs2 = FT_PAD_FLOOR( TT_PEEK_USHORT( p ), 2 );
1017
1018     num_segs = num_segs2 >> 1;
1019
1020     if ( !num_segs )
1021       return 0;
1022
1023     if ( next )
1024       charcode++;
1025
1026     /* linear search */
1027     for ( ; charcode <= 0xFFFFU; charcode++ )
1028     {
1029       FT_Byte*  q;
1030
1031
1032       p = cmap->data + 14;               /* ends table   */
1033       q = cmap->data + 16 + num_segs2;   /* starts table */
1034
1035       for ( i = 0; i < num_segs; i++ )
1036       {
1037         end   = TT_NEXT_USHORT( p );
1038         start = TT_NEXT_USHORT( q );
1039
1040         if ( charcode >= start && charcode <= end )
1041         {
1042           p       = q - 2 + num_segs2;
1043           delta   = TT_PEEK_SHORT( p );
1044           p      += num_segs2;
1045           offset  = TT_PEEK_USHORT( p );
1046
1047           /* some fonts have an incorrect last segment; */
1048           /* we have to catch it                        */
1049           if ( i >= num_segs - 1                  &&
1050                start == 0xFFFFU && end == 0xFFFFU )
1051           {
1052             TT_Face   face  = (TT_Face)cmap->cmap.charmap.face;
1053             FT_Byte*  limit = face->cmap_table + face->cmap_size;
1054
1055
1056             if ( offset && p + offset + 2 > limit )
1057             {
1058               delta  = 1;
1059               offset = 0;
1060             }
1061           }
1062
1063           if ( offset == 0xFFFFU )
1064             continue;
1065
1066           if ( offset )
1067           {
1068             p += offset + ( charcode - start ) * 2;
1069             gindex = TT_PEEK_USHORT( p );
1070             if ( gindex != 0 )
1071               gindex = (FT_UInt)( gindex + delta ) & 0xFFFFU;
1072           }
1073           else
1074             gindex = (FT_UInt)( charcode + delta ) & 0xFFFFU;
1075
1076           break;
1077         }
1078       }
1079
1080       if ( !next || gindex )
1081         break;
1082     }
1083
1084     if ( next && gindex )
1085       *pcharcode = charcode;
1086
1087     return gindex;
1088   }
1089
1090
1091   static FT_UInt
1092   tt_cmap4_char_map_binary( TT_CMap     cmap,
1093                             FT_UInt32*  pcharcode,
1094                             FT_Bool     next )
1095   {
1096     FT_UInt   num_segs2, start, end, offset;
1097     FT_Int    delta;
1098     FT_UInt   max, min, mid, num_segs;
1099     FT_UInt   charcode = (FT_UInt)*pcharcode;
1100     FT_UInt   gindex   = 0;
1101     FT_Byte*  p;
1102
1103
1104     p = cmap->data + 6;
1105     num_segs2 = FT_PAD_FLOOR( TT_PEEK_USHORT( p ), 2 );
1106
1107     if ( !num_segs2 )
1108       return 0;
1109
1110     num_segs = num_segs2 >> 1;
1111
1112     /* make compiler happy */
1113     mid = num_segs;
1114     end = 0xFFFFU;
1115
1116     if ( next )
1117       charcode++;
1118
1119     min = 0;
1120     max = num_segs;
1121
1122     /* binary search */
1123     while ( min < max )
1124     {
1125       mid    = ( min + max ) >> 1;
1126       p      = cmap->data + 14 + mid * 2;
1127       end    = TT_PEEK_USHORT( p );
1128       p     += 2 + num_segs2;
1129       start  = TT_PEEK_USHORT( p );
1130
1131       if ( charcode < start )
1132         max = mid;
1133       else if ( charcode > end )
1134         min = mid + 1;
1135       else
1136       {
1137         p     += num_segs2;
1138         delta  = TT_PEEK_SHORT( p );
1139         p     += num_segs2;
1140         offset = TT_PEEK_USHORT( p );
1141
1142         /* some fonts have an incorrect last segment; */
1143         /* we have to catch it                        */
1144         if ( mid >= num_segs - 1                &&
1145              start == 0xFFFFU && end == 0xFFFFU )
1146         {
1147           TT_Face   face  = (TT_Face)cmap->cmap.charmap.face;
1148           FT_Byte*  limit = face->cmap_table + face->cmap_size;
1149
1150
1151           if ( offset && p + offset + 2 > limit )
1152           {
1153             delta  = 1;
1154             offset = 0;
1155           }
1156         }
1157
1158         /* search the first segment containing `charcode' */
1159         if ( cmap->flags & TT_CMAP_FLAG_OVERLAPPING )
1160         {
1161           FT_UInt  i;
1162
1163
1164           /* call the current segment `max' */
1165           max = mid;
1166
1167           if ( offset == 0xFFFFU )
1168             mid = max + 1;
1169
1170           /* search in segments before the current segment */
1171           for ( i = max ; i > 0; i-- )
1172           {
1173             FT_UInt   prev_end;
1174             FT_Byte*  old_p;
1175
1176
1177             old_p    = p;
1178             p        = cmap->data + 14 + ( i - 1 ) * 2;
1179             prev_end = TT_PEEK_USHORT( p );
1180
1181             if ( charcode > prev_end )
1182             {
1183               p = old_p;
1184               break;
1185             }
1186
1187             end    = prev_end;
1188             p     += 2 + num_segs2;
1189             start  = TT_PEEK_USHORT( p );
1190             p     += num_segs2;
1191             delta  = TT_PEEK_SHORT( p );
1192             p     += num_segs2;
1193             offset = TT_PEEK_USHORT( p );
1194
1195             if ( offset != 0xFFFFU )
1196               mid = i - 1;
1197           }
1198
1199           /* no luck */
1200           if ( mid == max + 1 )
1201           {
1202             if ( i != max )
1203             {
1204               p      = cmap->data + 14 + max * 2;
1205               end    = TT_PEEK_USHORT( p );
1206               p     += 2 + num_segs2;
1207               start  = TT_PEEK_USHORT( p );
1208               p     += num_segs2;
1209               delta  = TT_PEEK_SHORT( p );
1210               p     += num_segs2;
1211               offset = TT_PEEK_USHORT( p );
1212             }
1213
1214             mid = max;
1215
1216             /* search in segments after the current segment */
1217             for ( i = max + 1; i < num_segs; i++ )
1218             {
1219               FT_UInt  next_end, next_start;
1220
1221
1222               p          = cmap->data + 14 + i * 2;
1223               next_end   = TT_PEEK_USHORT( p );
1224               p         += 2 + num_segs2;
1225               next_start = TT_PEEK_USHORT( p );
1226
1227               if ( charcode < next_start )
1228                 break;
1229
1230               end    = next_end;
1231               start  = next_start;
1232               p     += num_segs2;
1233               delta  = TT_PEEK_SHORT( p );
1234               p     += num_segs2;
1235               offset = TT_PEEK_USHORT( p );
1236
1237               if ( offset != 0xFFFFU )
1238                 mid = i;
1239             }
1240             i--;
1241
1242             /* still no luck */
1243             if ( mid == max )
1244             {
1245               mid = i;
1246
1247               break;
1248             }
1249           }
1250
1251           /* end, start, delta, and offset are for the i'th segment */
1252           if ( mid != i )
1253           {
1254             p      = cmap->data + 14 + mid * 2;
1255             end    = TT_PEEK_USHORT( p );
1256             p     += 2 + num_segs2;
1257             start  = TT_PEEK_USHORT( p );
1258             p     += num_segs2;
1259             delta  = TT_PEEK_SHORT( p );
1260             p     += num_segs2;
1261             offset = TT_PEEK_USHORT( p );
1262           }
1263         }
1264         else
1265         {
1266           if ( offset == 0xFFFFU )
1267             break;
1268         }
1269
1270         if ( offset )
1271         {
1272           p += offset + ( charcode - start ) * 2;
1273           gindex = TT_PEEK_USHORT( p );
1274           if ( gindex != 0 )
1275             gindex = (FT_UInt)( gindex + delta ) & 0xFFFFU;
1276         }
1277         else
1278           gindex = (FT_UInt)( charcode + delta ) & 0xFFFFU;
1279
1280         break;
1281       }
1282     }
1283
1284     if ( next )
1285     {
1286       TT_CMap4  cmap4 = (TT_CMap4)cmap;
1287
1288
1289       /* if `charcode' is not in any segment, then `mid' is */
1290       /* the segment nearest to `charcode'                  */
1291       /*                                                    */
1292
1293       if ( charcode > end )
1294       {
1295         mid++;
1296         if ( mid == num_segs )
1297           return 0;
1298       }
1299
1300       if ( tt_cmap4_set_range( cmap4, mid ) )
1301       {
1302         if ( gindex )
1303           *pcharcode = charcode;
1304       }
1305       else
1306       {
1307         cmap4->cur_charcode = charcode;
1308
1309         if ( gindex )
1310           cmap4->cur_gindex = gindex;
1311         else
1312         {
1313           cmap4->cur_charcode = charcode;
1314           tt_cmap4_next( cmap4 );
1315           gindex = cmap4->cur_gindex;
1316         }
1317
1318         if ( gindex )
1319           *pcharcode = cmap4->cur_charcode;
1320       }
1321     }
1322
1323     return gindex;
1324   }
1325
1326
1327   FT_CALLBACK_DEF( FT_UInt )
1328   tt_cmap4_char_index( TT_CMap    cmap,
1329                        FT_UInt32  char_code )
1330   {
1331     if ( char_code >= 0x10000UL )
1332       return 0;
1333
1334     if ( cmap->flags & TT_CMAP_FLAG_UNSORTED )
1335       return tt_cmap4_char_map_linear( cmap, &char_code, 0 );
1336     else
1337       return tt_cmap4_char_map_binary( cmap, &char_code, 0 );
1338   }
1339
1340
1341   FT_CALLBACK_DEF( FT_UInt32 )
1342   tt_cmap4_char_next( TT_CMap     cmap,
1343                       FT_UInt32  *pchar_code )
1344   {
1345     FT_UInt  gindex;
1346
1347
1348     if ( *pchar_code >= 0xFFFFU )
1349       return 0;
1350
1351     if ( cmap->flags & TT_CMAP_FLAG_UNSORTED )
1352       gindex = tt_cmap4_char_map_linear( cmap, pchar_code, 1 );
1353     else
1354     {
1355       TT_CMap4  cmap4 = (TT_CMap4)cmap;
1356
1357
1358       /* no need to search */
1359       if ( *pchar_code == cmap4->cur_charcode )
1360       {
1361         tt_cmap4_next( cmap4 );
1362         gindex = cmap4->cur_gindex;
1363         if ( gindex )
1364           *pchar_code = cmap4->cur_charcode;
1365       }
1366       else
1367         gindex = tt_cmap4_char_map_binary( cmap, pchar_code, 1 );
1368     }
1369
1370     return gindex;
1371   }
1372
1373
1374   FT_CALLBACK_DEF( FT_Error )
1375   tt_cmap4_get_info( TT_CMap       cmap,
1376                      TT_CMapInfo  *cmap_info )
1377   {
1378     FT_Byte*  p = cmap->data + 4;
1379
1380
1381     cmap_info->format   = 4;
1382     cmap_info->language = (FT_ULong)TT_PEEK_USHORT( p );
1383
1384     return FT_Err_Ok;
1385   }
1386
1387
1388   FT_DEFINE_TT_CMAP(
1389     tt_cmap4_class_rec,
1390     sizeof ( TT_CMap4Rec ),
1391     (FT_CMap_InitFunc)     tt_cmap4_init,
1392     (FT_CMap_DoneFunc)     NULL,
1393     (FT_CMap_CharIndexFunc)tt_cmap4_char_index,
1394     (FT_CMap_CharNextFunc) tt_cmap4_char_next,
1395
1396     NULL,
1397     NULL,
1398     NULL,
1399     NULL,
1400     NULL,
1401
1402     4,
1403     (TT_CMap_ValidateFunc)tt_cmap4_validate,
1404     (TT_CMap_Info_GetFunc)tt_cmap4_get_info )
1405
1406 #endif /* TT_CONFIG_CMAP_FORMAT_4 */
1407
1408
1409   /*************************************************************************/
1410   /*************************************************************************/
1411   /*****                                                               *****/
1412   /*****                          FORMAT 6                             *****/
1413   /*****                                                               *****/
1414   /*************************************************************************/
1415   /*************************************************************************/
1416
1417   /*************************************************************************/
1418   /*                                                                       */
1419   /* TABLE OVERVIEW                                                        */
1420   /* --------------                                                        */
1421   /*                                                                       */
1422   /*   NAME        OFFSET          TYPE             DESCRIPTION            */
1423   /*                                                                       */
1424   /*   format       0              USHORT           must be 4              */
1425   /*   length       2              USHORT           table length in bytes  */
1426   /*   language     4              USHORT           Mac language code      */
1427   /*                                                                       */
1428   /*   first        6              USHORT           first segment code     */
1429   /*   count        8              USHORT           segment size in chars  */
1430   /*   glyphIds     10             USHORT[count]    glyph IDs              */
1431   /*                                                                       */
1432   /* A very simplified segment mapping.                                    */
1433   /*                                                                       */
1434
1435 #ifdef TT_CONFIG_CMAP_FORMAT_6
1436
1437   FT_CALLBACK_DEF( FT_Error )
1438   tt_cmap6_validate( FT_Byte*      table,
1439                      FT_Validator  valid )
1440   {
1441     FT_Byte*  p;
1442     FT_UInt   length, count;
1443
1444
1445     if ( table + 10 > valid->limit )
1446       FT_INVALID_TOO_SHORT;
1447
1448     p      = table + 2;
1449     length = TT_NEXT_USHORT( p );
1450
1451     p      = table + 8;             /* skip language and start index */
1452     count  = TT_NEXT_USHORT( p );
1453
1454     if ( table + length > valid->limit || length < 10 + count * 2 )
1455       FT_INVALID_TOO_SHORT;
1456
1457     /* check glyph indices */
1458     if ( valid->level >= FT_VALIDATE_TIGHT )
1459     {
1460       FT_UInt  gindex;
1461
1462
1463       for ( ; count > 0; count-- )
1464       {
1465         gindex = TT_NEXT_USHORT( p );
1466         if ( gindex >= TT_VALID_GLYPH_COUNT( valid ) )
1467           FT_INVALID_GLYPH_ID;
1468       }
1469     }
1470
1471     return FT_Err_Ok;
1472   }
1473
1474
1475   FT_CALLBACK_DEF( FT_UInt )
1476   tt_cmap6_char_index( TT_CMap    cmap,
1477                        FT_UInt32  char_code )
1478   {
1479     FT_Byte*  table  = cmap->data;
1480     FT_UInt   result = 0;
1481     FT_Byte*  p      = table + 6;
1482     FT_UInt   start  = TT_NEXT_USHORT( p );
1483     FT_UInt   count  = TT_NEXT_USHORT( p );
1484     FT_UInt   idx    = (FT_UInt)( char_code - start );
1485
1486
1487     if ( idx < count )
1488     {
1489       p += 2 * idx;
1490       result = TT_PEEK_USHORT( p );
1491     }
1492     return result;
1493   }
1494
1495
1496   FT_CALLBACK_DEF( FT_UInt32 )
1497   tt_cmap6_char_next( TT_CMap     cmap,
1498                       FT_UInt32  *pchar_code )
1499   {
1500     FT_Byte*   table     = cmap->data;
1501     FT_UInt32  result    = 0;
1502     FT_UInt32  char_code = *pchar_code + 1;
1503     FT_UInt    gindex    = 0;
1504
1505     FT_Byte*   p         = table + 6;
1506     FT_UInt    start     = TT_NEXT_USHORT( p );
1507     FT_UInt    count     = TT_NEXT_USHORT( p );
1508     FT_UInt    idx;
1509
1510
1511     if ( char_code >= 0x10000UL )
1512       goto Exit;
1513
1514     if ( char_code < start )
1515       char_code = start;
1516
1517     idx = (FT_UInt)( char_code - start );
1518     p  += 2 * idx;
1519
1520     for ( ; idx < count; idx++ )
1521     {
1522       gindex = TT_NEXT_USHORT( p );
1523       if ( gindex != 0 )
1524       {
1525         result = char_code;
1526         break;
1527       }
1528       char_code++;
1529     }
1530
1531   Exit:
1532     *pchar_code = result;
1533     return gindex;
1534   }
1535
1536
1537   FT_CALLBACK_DEF( FT_Error )
1538   tt_cmap6_get_info( TT_CMap       cmap,
1539                      TT_CMapInfo  *cmap_info )
1540   {
1541     FT_Byte*  p = cmap->data + 4;
1542
1543
1544     cmap_info->format   = 6;
1545     cmap_info->language = (FT_ULong)TT_PEEK_USHORT( p );
1546
1547     return FT_Err_Ok;
1548   }
1549
1550
1551   FT_DEFINE_TT_CMAP(
1552     tt_cmap6_class_rec,
1553     sizeof ( TT_CMapRec ),
1554
1555     (FT_CMap_InitFunc)     tt_cmap_init,
1556     (FT_CMap_DoneFunc)     NULL,
1557     (FT_CMap_CharIndexFunc)tt_cmap6_char_index,
1558     (FT_CMap_CharNextFunc) tt_cmap6_char_next,
1559
1560     NULL,
1561     NULL,
1562     NULL,
1563     NULL,
1564     NULL,
1565
1566     6,
1567     (TT_CMap_ValidateFunc)tt_cmap6_validate,
1568     (TT_CMap_Info_GetFunc)tt_cmap6_get_info )
1569
1570 #endif /* TT_CONFIG_CMAP_FORMAT_6 */
1571
1572
1573   /*************************************************************************/
1574   /*************************************************************************/
1575   /*****                                                               *****/
1576   /*****                          FORMAT 8                             *****/
1577   /*****                                                               *****/
1578   /***** It is hard to completely understand what the OpenType spec    *****/
1579   /***** says about this format, but here is my conclusion.            *****/
1580   /*****                                                               *****/
1581   /***** The purpose of this format is to easily map UTF-16 text to    *****/
1582   /***** glyph indices.  Basically, the `char_code' must be in one of  *****/
1583   /***** the following formats:                                        *****/
1584   /*****                                                               *****/
1585   /*****   - A 16-bit value that isn't part of the Unicode Surrogates  *****/
1586   /*****     Area (i.e. U+D800-U+DFFF).                                *****/
1587   /*****                                                               *****/
1588   /*****   - A 32-bit value, made of two surrogate values, i.e.. if    *****/
1589   /*****     `char_code = (char_hi << 16) | char_lo', then both        *****/
1590   /*****     `char_hi' and `char_lo' must be in the Surrogates Area.   *****/
1591   /*****      Area.                                                    *****/
1592   /*****                                                               *****/
1593   /***** The `is32' table embedded in the charmap indicates whether a  *****/
1594   /***** given 16-bit value is in the surrogates area or not.          *****/
1595   /*****                                                               *****/
1596   /***** So, for any given `char_code', we can assert the following:   *****/
1597   /*****                                                               *****/
1598   /*****   If `char_hi == 0' then we must have `is32[char_lo] == 0'.   *****/
1599   /*****                                                               *****/
1600   /*****   If `char_hi != 0' then we must have both                    *****/
1601   /*****   `is32[char_hi] != 0' and `is32[char_lo] != 0'.              *****/
1602   /*****                                                               *****/
1603   /*************************************************************************/
1604   /*************************************************************************/
1605
1606   /*************************************************************************/
1607   /*                                                                       */
1608   /* TABLE OVERVIEW                                                        */
1609   /* --------------                                                        */
1610   /*                                                                       */
1611   /*   NAME        OFFSET         TYPE        DESCRIPTION                  */
1612   /*                                                                       */
1613   /*   format      0              USHORT      must be 8                    */
1614   /*   reserved    2              USHORT      reserved                     */
1615   /*   length      4              ULONG       length in bytes              */
1616   /*   language    8              ULONG       Mac language code            */
1617   /*   is32        12             BYTE[8192]  32-bitness bitmap            */
1618   /*   count       8204           ULONG       number of groups             */
1619   /*                                                                       */
1620   /* This header is followed by `count' groups of the following format:    */
1621   /*                                                                       */
1622   /*   start       0              ULONG       first charcode               */
1623   /*   end         4              ULONG       last charcode                */
1624   /*   startId     8              ULONG       start glyph ID for the group */
1625   /*                                                                       */
1626
1627 #ifdef TT_CONFIG_CMAP_FORMAT_8
1628
1629   FT_CALLBACK_DEF( FT_Error )
1630   tt_cmap8_validate( FT_Byte*      table,
1631                      FT_Validator  valid )
1632   {
1633     FT_Byte*   p = table + 4;
1634     FT_Byte*   is32;
1635     FT_UInt32  length;
1636     FT_UInt32  num_groups;
1637
1638
1639     if ( table + 16 + 8192 > valid->limit )
1640       FT_INVALID_TOO_SHORT;
1641
1642     length = TT_NEXT_ULONG( p );
1643     if ( length > (FT_UInt32)( valid->limit - table ) || length < 8192 + 16 )
1644       FT_INVALID_TOO_SHORT;
1645
1646     is32       = table + 12;
1647     p          = is32  + 8192;          /* skip `is32' array */
1648     num_groups = TT_NEXT_ULONG( p );
1649
1650     if ( p + num_groups * 12 > valid->limit )
1651       FT_INVALID_TOO_SHORT;
1652
1653     /* check groups, they must be in increasing order */
1654     {
1655       FT_UInt32  n, start, end, start_id, count, last = 0;
1656
1657
1658       for ( n = 0; n < num_groups; n++ )
1659       {
1660         FT_UInt   hi, lo;
1661
1662
1663         start    = TT_NEXT_ULONG( p );
1664         end      = TT_NEXT_ULONG( p );
1665         start_id = TT_NEXT_ULONG( p );
1666
1667         if ( start > end )
1668           FT_INVALID_DATA;
1669
1670         if ( n > 0 && start <= last )
1671           FT_INVALID_DATA;
1672
1673         if ( valid->level >= FT_VALIDATE_TIGHT )
1674         {
1675           if ( start_id + end - start >= TT_VALID_GLYPH_COUNT( valid ) )
1676             FT_INVALID_GLYPH_ID;
1677
1678           count = (FT_UInt32)( end - start + 1 );
1679
1680           if ( start & ~0xFFFFU )
1681           {
1682             /* start_hi != 0; check that is32[i] is 1 for each i in */
1683             /* the `hi' and `lo' of the range [start..end]          */
1684             for ( ; count > 0; count--, start++ )
1685             {
1686               hi = (FT_UInt)( start >> 16 );
1687               lo = (FT_UInt)( start & 0xFFFFU );
1688
1689               if ( (is32[hi >> 3] & ( 0x80 >> ( hi & 7 ) ) ) == 0 )
1690                 FT_INVALID_DATA;
1691
1692               if ( (is32[lo >> 3] & ( 0x80 >> ( lo & 7 ) ) ) == 0 )
1693                 FT_INVALID_DATA;
1694             }
1695           }
1696           else
1697           {
1698             /* start_hi == 0; check that is32[i] is 0 for each i in */
1699             /* the range [start..end]                               */
1700
1701             /* end_hi cannot be != 0! */
1702             if ( end & ~0xFFFFU )
1703               FT_INVALID_DATA;
1704
1705             for ( ; count > 0; count--, start++ )
1706             {
1707               lo = (FT_UInt)( start & 0xFFFFU );
1708
1709               if ( (is32[lo >> 3] & ( 0x80 >> ( lo & 7 ) ) ) != 0 )
1710                 FT_INVALID_DATA;
1711             }
1712           }
1713         }
1714
1715         last = end;
1716       }
1717     }
1718
1719     return FT_Err_Ok;
1720   }
1721
1722
1723   FT_CALLBACK_DEF( FT_UInt )
1724   tt_cmap8_char_index( TT_CMap    cmap,
1725                        FT_UInt32  char_code )
1726   {
1727     FT_Byte*   table      = cmap->data;
1728     FT_UInt    result     = 0;
1729     FT_Byte*   p          = table + 8204;
1730     FT_UInt32  num_groups = TT_NEXT_ULONG( p );
1731     FT_UInt32  start, end, start_id;
1732
1733
1734     for ( ; num_groups > 0; num_groups-- )
1735     {
1736       start    = TT_NEXT_ULONG( p );
1737       end      = TT_NEXT_ULONG( p );
1738       start_id = TT_NEXT_ULONG( p );
1739
1740       if ( char_code < start )
1741         break;
1742
1743       if ( char_code <= end )
1744       {
1745         result = (FT_UInt)( start_id + char_code - start );
1746         break;
1747       }
1748     }
1749     return result;
1750   }
1751
1752
1753   FT_CALLBACK_DEF( FT_UInt32 )
1754   tt_cmap8_char_next( TT_CMap     cmap,
1755                       FT_UInt32  *pchar_code )
1756   {
1757     FT_UInt32  result     = 0;
1758     FT_UInt32  char_code  = *pchar_code + 1;
1759     FT_UInt    gindex     = 0;
1760     FT_Byte*   table      = cmap->data;
1761     FT_Byte*   p          = table + 8204;
1762     FT_UInt32  num_groups = TT_NEXT_ULONG( p );
1763     FT_UInt32  start, end, start_id;
1764
1765
1766     p = table + 8208;
1767
1768     for ( ; num_groups > 0; num_groups-- )
1769     {
1770       start    = TT_NEXT_ULONG( p );
1771       end      = TT_NEXT_ULONG( p );
1772       start_id = TT_NEXT_ULONG( p );
1773
1774       if ( char_code < start )
1775         char_code = start;
1776
1777       if ( char_code <= end )
1778       {
1779         gindex = (FT_UInt)( char_code - start + start_id );
1780         if ( gindex != 0 )
1781         {
1782           result = char_code;
1783           goto Exit;
1784         }
1785       }
1786     }
1787
1788   Exit:
1789     *pchar_code = result;
1790     return gindex;
1791   }
1792
1793
1794   FT_CALLBACK_DEF( FT_Error )
1795   tt_cmap8_get_info( TT_CMap       cmap,
1796                      TT_CMapInfo  *cmap_info )
1797   {
1798     FT_Byte*  p = cmap->data + 8;
1799
1800
1801     cmap_info->format   = 8;
1802     cmap_info->language = (FT_ULong)TT_PEEK_ULONG( p );
1803
1804     return FT_Err_Ok;
1805   }
1806
1807
1808   FT_DEFINE_TT_CMAP(
1809     tt_cmap8_class_rec,
1810     sizeof ( TT_CMapRec ),
1811
1812     (FT_CMap_InitFunc)     tt_cmap_init,
1813     (FT_CMap_DoneFunc)     NULL,
1814     (FT_CMap_CharIndexFunc)tt_cmap8_char_index,
1815     (FT_CMap_CharNextFunc) tt_cmap8_char_next,
1816
1817     NULL,
1818     NULL,
1819     NULL,
1820     NULL,
1821     NULL,
1822
1823     8,
1824     (TT_CMap_ValidateFunc)tt_cmap8_validate,
1825     (TT_CMap_Info_GetFunc)tt_cmap8_get_info )
1826
1827 #endif /* TT_CONFIG_CMAP_FORMAT_8 */
1828
1829
1830   /*************************************************************************/
1831   /*************************************************************************/
1832   /*****                                                               *****/
1833   /*****                          FORMAT 10                            *****/
1834   /*****                                                               *****/
1835   /*************************************************************************/
1836   /*************************************************************************/
1837
1838   /*************************************************************************/
1839   /*                                                                       */
1840   /* TABLE OVERVIEW                                                        */
1841   /* --------------                                                        */
1842   /*                                                                       */
1843   /*   NAME      OFFSET  TYPE               DESCRIPTION                    */
1844   /*                                                                       */
1845   /*   format     0      USHORT             must be 10                     */
1846   /*   reserved   2      USHORT             reserved                       */
1847   /*   length     4      ULONG              length in bytes                */
1848   /*   language   8      ULONG              Mac language code              */
1849   /*                                                                       */
1850   /*   start     12      ULONG              first char in range            */
1851   /*   count     16      ULONG              number of chars in range       */
1852   /*   glyphIds  20      USHORT[count]      glyph indices covered          */
1853   /*                                                                       */
1854
1855 #ifdef TT_CONFIG_CMAP_FORMAT_10
1856
1857   FT_CALLBACK_DEF( FT_Error )
1858   tt_cmap10_validate( FT_Byte*      table,
1859                       FT_Validator  valid )
1860   {
1861     FT_Byte*  p = table + 4;
1862     FT_ULong  length, count;
1863
1864
1865     if ( table + 20 > valid->limit )
1866       FT_INVALID_TOO_SHORT;
1867
1868     length = TT_NEXT_ULONG( p );
1869     p      = table + 16;
1870     count  = TT_NEXT_ULONG( p );
1871
1872     if ( length > (FT_ULong)( valid->limit - table ) ||
1873          length < 20 + count * 2                     )
1874       FT_INVALID_TOO_SHORT;
1875
1876     /* check glyph indices */
1877     if ( valid->level >= FT_VALIDATE_TIGHT )
1878     {
1879       FT_UInt  gindex;
1880
1881
1882       for ( ; count > 0; count-- )
1883       {
1884         gindex = TT_NEXT_USHORT( p );
1885         if ( gindex >= TT_VALID_GLYPH_COUNT( valid ) )
1886           FT_INVALID_GLYPH_ID;
1887       }
1888     }
1889
1890     return FT_Err_Ok;
1891   }
1892
1893
1894   FT_CALLBACK_DEF( FT_UInt )
1895   tt_cmap10_char_index( TT_CMap    cmap,
1896                         FT_UInt32  char_code )
1897   {
1898     FT_Byte*   table  = cmap->data;
1899     FT_UInt    result = 0;
1900     FT_Byte*   p      = table + 12;
1901     FT_UInt32  start  = TT_NEXT_ULONG( p );
1902     FT_UInt32  count  = TT_NEXT_ULONG( p );
1903     FT_UInt32  idx    = (FT_ULong)( char_code - start );
1904
1905
1906     if ( idx < count )
1907     {
1908       p     += 2 * idx;
1909       result = TT_PEEK_USHORT( p );
1910     }
1911     return result;
1912   }
1913
1914
1915   FT_CALLBACK_DEF( FT_UInt32 )
1916   tt_cmap10_char_next( TT_CMap     cmap,
1917                        FT_UInt32  *pchar_code )
1918   {
1919     FT_Byte*   table     = cmap->data;
1920     FT_UInt32  char_code = *pchar_code + 1;
1921     FT_UInt    gindex    = 0;
1922     FT_Byte*   p         = table + 12;
1923     FT_UInt32  start     = TT_NEXT_ULONG( p );
1924     FT_UInt32  count     = TT_NEXT_ULONG( p );
1925     FT_UInt32  idx;
1926
1927
1928     if ( char_code < start )
1929       char_code = start;
1930
1931     idx = (FT_UInt32)( char_code - start );
1932     p  += 2 * idx;
1933
1934     for ( ; idx < count; idx++ )
1935     {
1936       gindex = TT_NEXT_USHORT( p );
1937       if ( gindex != 0 )
1938         break;
1939       char_code++;
1940     }
1941
1942     *pchar_code = char_code;
1943     return gindex;
1944   }
1945
1946
1947   FT_CALLBACK_DEF( FT_Error )
1948   tt_cmap10_get_info( TT_CMap       cmap,
1949                       TT_CMapInfo  *cmap_info )
1950   {
1951     FT_Byte*  p = cmap->data + 8;
1952
1953
1954     cmap_info->format   = 10;
1955     cmap_info->language = (FT_ULong)TT_PEEK_ULONG( p );
1956
1957     return FT_Err_Ok;
1958   }
1959
1960
1961   FT_DEFINE_TT_CMAP(
1962     tt_cmap10_class_rec,
1963     sizeof ( TT_CMapRec ),
1964
1965     (FT_CMap_InitFunc)     tt_cmap_init,
1966     (FT_CMap_DoneFunc)     NULL,
1967     (FT_CMap_CharIndexFunc)tt_cmap10_char_index,
1968     (FT_CMap_CharNextFunc) tt_cmap10_char_next,
1969
1970     NULL,
1971     NULL,
1972     NULL,
1973     NULL,
1974     NULL,
1975
1976     10,
1977     (TT_CMap_ValidateFunc)tt_cmap10_validate,
1978     (TT_CMap_Info_GetFunc)tt_cmap10_get_info )
1979
1980 #endif /* TT_CONFIG_CMAP_FORMAT_10 */
1981
1982
1983   /*************************************************************************/
1984   /*************************************************************************/
1985   /*****                                                               *****/
1986   /*****                          FORMAT 12                            *****/
1987   /*****                                                               *****/
1988   /*************************************************************************/
1989   /*************************************************************************/
1990
1991   /*************************************************************************/
1992   /*                                                                       */
1993   /* TABLE OVERVIEW                                                        */
1994   /* --------------                                                        */
1995   /*                                                                       */
1996   /*   NAME        OFFSET     TYPE       DESCRIPTION                       */
1997   /*                                                                       */
1998   /*   format      0          USHORT     must be 12                        */
1999   /*   reserved    2          USHORT     reserved                          */
2000   /*   length      4          ULONG      length in bytes                   */
2001   /*   language    8          ULONG      Mac language code                 */
2002   /*   count       12         ULONG      number of groups                  */
2003   /*               16                                                      */
2004   /*                                                                       */
2005   /* This header is followed by `count' groups of the following format:    */
2006   /*                                                                       */
2007   /*   start       0          ULONG      first charcode                    */
2008   /*   end         4          ULONG      last charcode                     */
2009   /*   startId     8          ULONG      start glyph ID for the group      */
2010   /*                                                                       */
2011
2012 #ifdef TT_CONFIG_CMAP_FORMAT_12
2013
2014   typedef struct  TT_CMap12Rec_
2015   {
2016     TT_CMapRec  cmap;
2017     FT_Bool     valid;
2018     FT_ULong    cur_charcode;
2019     FT_UInt     cur_gindex;
2020     FT_ULong    cur_group;
2021     FT_ULong    num_groups;
2022
2023   } TT_CMap12Rec, *TT_CMap12;
2024
2025
2026   FT_CALLBACK_DEF( FT_Error )
2027   tt_cmap12_init( TT_CMap12  cmap,
2028                   FT_Byte*   table )
2029   {
2030     cmap->cmap.data  = table;
2031
2032     table           += 12;
2033     cmap->num_groups = FT_PEEK_ULONG( table );
2034
2035     cmap->valid      = 0;
2036
2037     return FT_Err_Ok;
2038   }
2039
2040
2041   FT_CALLBACK_DEF( FT_Error )
2042   tt_cmap12_validate( FT_Byte*      table,
2043                       FT_Validator  valid )
2044   {
2045     FT_Byte*   p;
2046     FT_ULong   length;
2047     FT_ULong   num_groups;
2048
2049
2050     if ( table + 16 > valid->limit )
2051       FT_INVALID_TOO_SHORT;
2052
2053     p      = table + 4;
2054     length = TT_NEXT_ULONG( p );
2055
2056     p          = table + 12;
2057     num_groups = TT_NEXT_ULONG( p );
2058
2059     if ( length > (FT_ULong)( valid->limit - table ) ||
2060          length < 16 + 12 * num_groups               )
2061       FT_INVALID_TOO_SHORT;
2062
2063     /* check groups, they must be in increasing order */
2064     {
2065       FT_ULong  n, start, end, start_id, last = 0;
2066
2067
2068       for ( n = 0; n < num_groups; n++ )
2069       {
2070         start    = TT_NEXT_ULONG( p );
2071         end      = TT_NEXT_ULONG( p );
2072         start_id = TT_NEXT_ULONG( p );
2073
2074         if ( start > end )
2075           FT_INVALID_DATA;
2076
2077         if ( n > 0 && start <= last )
2078           FT_INVALID_DATA;
2079
2080         if ( valid->level >= FT_VALIDATE_TIGHT )
2081         {
2082           if ( start_id + end - start >= TT_VALID_GLYPH_COUNT( valid ) )
2083             FT_INVALID_GLYPH_ID;
2084         }
2085
2086         last = end;
2087       }
2088     }
2089
2090     return FT_Err_Ok;
2091   }
2092
2093
2094   /* search the index of the charcode next to cmap->cur_charcode */
2095   /* cmap->cur_group should be set up properly by caller         */
2096   /*                                                             */
2097   static void
2098   tt_cmap12_next( TT_CMap12  cmap )
2099   {
2100     FT_Byte*  p;
2101     FT_ULong  start, end, start_id, char_code;
2102     FT_ULong  n;
2103     FT_UInt   gindex;
2104
2105
2106     if ( cmap->cur_charcode >= 0xFFFFFFFFUL )
2107       goto Fail;
2108
2109     char_code = cmap->cur_charcode + 1;
2110
2111     n = cmap->cur_group;
2112
2113     for ( n = cmap->cur_group; n < cmap->num_groups; n++ )
2114     {
2115       p        = cmap->cmap.data + 16 + 12 * n;
2116       start    = TT_NEXT_ULONG( p );
2117       end      = TT_NEXT_ULONG( p );
2118       start_id = TT_PEEK_ULONG( p );
2119
2120       if ( char_code < start )
2121         char_code = start;
2122
2123       for ( ; char_code <= end; char_code++ )
2124       {
2125         gindex = (FT_UInt)( start_id + char_code - start );
2126
2127         if ( gindex )
2128         {
2129           cmap->cur_charcode = char_code;;
2130           cmap->cur_gindex   = gindex;
2131           cmap->cur_group    = n;
2132
2133           return;
2134         }
2135       }
2136     }
2137
2138   Fail:
2139     cmap->valid = 0;
2140   }
2141
2142
2143   static FT_UInt
2144   tt_cmap12_char_map_binary( TT_CMap     cmap,
2145                              FT_UInt32*  pchar_code,
2146                              FT_Bool     next )
2147   {
2148     FT_UInt    gindex     = 0;
2149     FT_Byte*   p          = cmap->data + 12;
2150     FT_UInt32  num_groups = TT_PEEK_ULONG( p );
2151     FT_UInt32  char_code  = *pchar_code;
2152     FT_UInt32  start, end, start_id;
2153     FT_UInt32  max, min, mid;
2154
2155
2156     if ( !num_groups )
2157       return 0;
2158
2159     /* make compiler happy */
2160     mid = num_groups;
2161     end = 0xFFFFFFFFUL;
2162
2163     if ( next )
2164       char_code++;
2165
2166     min = 0;
2167     max = num_groups;
2168
2169     /* binary search */
2170     while ( min < max )
2171     {
2172       mid = ( min + max ) >> 1;
2173       p   = cmap->data + 16 + 12 * mid;
2174
2175       start = TT_NEXT_ULONG( p );
2176       end   = TT_NEXT_ULONG( p );
2177
2178       if ( char_code < start )
2179         max = mid;
2180       else if ( char_code > end )
2181         min = mid + 1;
2182       else
2183       {
2184         start_id = TT_PEEK_ULONG( p );
2185         gindex = (FT_UInt)( start_id + char_code - start );
2186
2187         break;
2188       }
2189     }
2190
2191     if ( next )
2192     {
2193       TT_CMap12  cmap12 = (TT_CMap12)cmap;
2194
2195
2196       /* if `char_code' is not in any group, then `mid' is */
2197       /* the group nearest to `char_code'                  */
2198       /*                                                   */
2199
2200       if ( char_code > end )
2201       {
2202         mid++;
2203         if ( mid == num_groups )
2204           return 0;
2205       }
2206
2207       cmap12->valid        = 1;
2208       cmap12->cur_charcode = char_code;
2209       cmap12->cur_group    = mid;
2210
2211       if ( !gindex )
2212       {
2213         tt_cmap12_next( cmap12 );
2214
2215         if ( cmap12->valid )
2216           gindex = cmap12->cur_gindex;
2217       }
2218       else
2219         cmap12->cur_gindex = gindex;
2220
2221       if ( gindex )
2222         *pchar_code = cmap12->cur_charcode;
2223     }
2224
2225     return gindex;
2226   }
2227
2228
2229   FT_CALLBACK_DEF( FT_UInt )
2230   tt_cmap12_char_index( TT_CMap    cmap,
2231                         FT_UInt32  char_code )
2232   {
2233     return tt_cmap12_char_map_binary( cmap, &char_code, 0 );
2234   }
2235
2236
2237   FT_CALLBACK_DEF( FT_UInt32 )
2238   tt_cmap12_char_next( TT_CMap     cmap,
2239                        FT_UInt32  *pchar_code )
2240   {
2241     TT_CMap12  cmap12 = (TT_CMap12)cmap;
2242     FT_ULong   gindex;
2243
2244
2245     if ( cmap12->cur_charcode >= 0xFFFFFFFFUL )
2246       return 0;
2247
2248     /* no need to search */
2249     if ( cmap12->valid && cmap12->cur_charcode == *pchar_code )
2250     {
2251       tt_cmap12_next( cmap12 );
2252       if ( cmap12->valid )
2253       {
2254         gindex = cmap12->cur_gindex;
2255
2256         /* XXX: check cur_charcode overflow is expected */
2257         if ( gindex )
2258           *pchar_code = (FT_UInt32)cmap12->cur_charcode;
2259       }
2260       else
2261         gindex = 0;
2262     }
2263     else
2264       gindex = tt_cmap12_char_map_binary( cmap, pchar_code, 1 );
2265
2266     /* XXX: check gindex overflow is expected */
2267     return (FT_UInt32)gindex;
2268   }
2269
2270
2271   FT_CALLBACK_DEF( FT_Error )
2272   tt_cmap12_get_info( TT_CMap       cmap,
2273                       TT_CMapInfo  *cmap_info )
2274   {
2275     FT_Byte*  p = cmap->data + 8;
2276
2277
2278     cmap_info->format   = 12;
2279     cmap_info->language = (FT_ULong)TT_PEEK_ULONG( p );
2280
2281     return FT_Err_Ok;
2282   }
2283
2284
2285   FT_DEFINE_TT_CMAP(
2286     tt_cmap12_class_rec,
2287     sizeof ( TT_CMap12Rec ),
2288
2289     (FT_CMap_InitFunc)     tt_cmap12_init,
2290     (FT_CMap_DoneFunc)     NULL,
2291     (FT_CMap_CharIndexFunc)tt_cmap12_char_index,
2292     (FT_CMap_CharNextFunc) tt_cmap12_char_next,
2293
2294     NULL,
2295     NULL,
2296     NULL,
2297     NULL,
2298     NULL,
2299
2300     12,
2301     (TT_CMap_ValidateFunc)tt_cmap12_validate,
2302     (TT_CMap_Info_GetFunc)tt_cmap12_get_info )
2303
2304 #endif /* TT_CONFIG_CMAP_FORMAT_12 */
2305
2306
2307   /*************************************************************************/
2308   /*************************************************************************/
2309   /*****                                                               *****/
2310   /*****                          FORMAT 13                            *****/
2311   /*****                                                               *****/
2312   /*************************************************************************/
2313   /*************************************************************************/
2314
2315   /*************************************************************************/
2316   /*                                                                       */
2317   /* TABLE OVERVIEW                                                        */
2318   /* --------------                                                        */
2319   /*                                                                       */
2320   /*   NAME        OFFSET     TYPE       DESCRIPTION                       */
2321   /*                                                                       */
2322   /*   format      0          USHORT     must be 13                        */
2323   /*   reserved    2          USHORT     reserved                          */
2324   /*   length      4          ULONG      length in bytes                   */
2325   /*   language    8          ULONG      Mac language code                 */
2326   /*   count       12         ULONG      number of groups                  */
2327   /*               16                                                      */
2328   /*                                                                       */
2329   /* This header is followed by `count' groups of the following format:    */
2330   /*                                                                       */
2331   /*   start       0          ULONG      first charcode                    */
2332   /*   end         4          ULONG      last charcode                     */
2333   /*   glyphId     8          ULONG      glyph ID for the whole group      */
2334   /*                                                                       */
2335
2336 #ifdef TT_CONFIG_CMAP_FORMAT_13
2337
2338   typedef struct  TT_CMap13Rec_
2339   {
2340     TT_CMapRec  cmap;
2341     FT_Bool     valid;
2342     FT_ULong    cur_charcode;
2343     FT_UInt     cur_gindex;
2344     FT_ULong    cur_group;
2345     FT_ULong    num_groups;
2346
2347   } TT_CMap13Rec, *TT_CMap13;
2348
2349
2350   FT_CALLBACK_DEF( FT_Error )
2351   tt_cmap13_init( TT_CMap13  cmap,
2352                   FT_Byte*   table )
2353   {
2354     cmap->cmap.data  = table;
2355
2356     table           += 12;
2357     cmap->num_groups = FT_PEEK_ULONG( table );
2358
2359     cmap->valid      = 0;
2360
2361     return FT_Err_Ok;
2362   }
2363
2364
2365   FT_CALLBACK_DEF( FT_Error )
2366   tt_cmap13_validate( FT_Byte*      table,
2367                       FT_Validator  valid )
2368   {
2369     FT_Byte*  p;
2370     FT_ULong  length;
2371     FT_ULong  num_groups;
2372
2373
2374     if ( table + 16 > valid->limit )
2375       FT_INVALID_TOO_SHORT;
2376
2377     p      = table + 4;
2378     length = TT_NEXT_ULONG( p );
2379
2380     p          = table + 12;
2381     num_groups = TT_NEXT_ULONG( p );
2382
2383     if ( length > (FT_ULong)( valid->limit - table ) ||
2384          length < 16 + 12 * num_groups               )
2385       FT_INVALID_TOO_SHORT;
2386
2387     /* check groups, they must be in increasing order */
2388     {
2389       FT_ULong  n, start, end, glyph_id, last = 0;
2390
2391
2392       for ( n = 0; n < num_groups; n++ )
2393       {
2394         start    = TT_NEXT_ULONG( p );
2395         end      = TT_NEXT_ULONG( p );
2396         glyph_id = TT_NEXT_ULONG( p );
2397
2398         if ( start > end )
2399           FT_INVALID_DATA;
2400
2401         if ( n > 0 && start <= last )
2402           FT_INVALID_DATA;
2403
2404         if ( valid->level >= FT_VALIDATE_TIGHT )
2405         {
2406           if ( glyph_id >= TT_VALID_GLYPH_COUNT( valid ) )
2407             FT_INVALID_GLYPH_ID;
2408         }
2409
2410         last = end;
2411       }
2412     }
2413
2414     return FT_Err_Ok;
2415   }
2416
2417
2418   /* search the index of the charcode next to cmap->cur_charcode */
2419   /* cmap->cur_group should be set up properly by caller         */
2420   /*                                                             */
2421   static void
2422   tt_cmap13_next( TT_CMap13  cmap )
2423   {
2424     FT_Byte*  p;
2425     FT_ULong  start, end, glyph_id, char_code;
2426     FT_ULong  n;
2427     FT_UInt   gindex;
2428
2429
2430     if ( cmap->cur_charcode >= 0xFFFFFFFFUL )
2431       goto Fail;
2432
2433     char_code = cmap->cur_charcode + 1;
2434
2435     n = cmap->cur_group;
2436
2437     for ( n = cmap->cur_group; n < cmap->num_groups; n++ )
2438     {
2439       p        = cmap->cmap.data + 16 + 12 * n;
2440       start    = TT_NEXT_ULONG( p );
2441       end      = TT_NEXT_ULONG( p );
2442       glyph_id = TT_PEEK_ULONG( p );
2443
2444       if ( char_code < start )
2445         char_code = start;
2446
2447       if ( char_code <= end )
2448       {
2449         gindex = (FT_UInt)glyph_id;
2450
2451         if ( gindex )
2452         {
2453           cmap->cur_charcode = char_code;;
2454           cmap->cur_gindex   = gindex;
2455           cmap->cur_group    = n;
2456
2457           return;
2458         }
2459       }
2460     }
2461
2462   Fail:
2463     cmap->valid = 0;
2464   }
2465
2466
2467   static FT_UInt
2468   tt_cmap13_char_map_binary( TT_CMap     cmap,
2469                              FT_UInt32*  pchar_code,
2470                              FT_Bool     next )
2471   {
2472     FT_UInt    gindex     = 0;
2473     FT_Byte*   p          = cmap->data + 12;
2474     FT_UInt32  num_groups = TT_PEEK_ULONG( p );
2475     FT_UInt32  char_code  = *pchar_code;
2476     FT_UInt32  start, end;
2477     FT_UInt32  max, min, mid;
2478
2479
2480     if ( !num_groups )
2481       return 0;
2482
2483     /* make compiler happy */
2484     mid = num_groups;
2485     end = 0xFFFFFFFFUL;
2486
2487     if ( next )
2488       char_code++;
2489
2490     min = 0;
2491     max = num_groups;
2492
2493     /* binary search */
2494     while ( min < max )
2495     {
2496       mid = ( min + max ) >> 1;
2497       p   = cmap->data + 16 + 12 * mid;
2498
2499       start = TT_NEXT_ULONG( p );
2500       end   = TT_NEXT_ULONG( p );
2501
2502       if ( char_code < start )
2503         max = mid;
2504       else if ( char_code > end )
2505         min = mid + 1;
2506       else
2507       {
2508         gindex = (FT_UInt)TT_PEEK_ULONG( p );
2509
2510         break;
2511       }
2512     }
2513
2514     if ( next )
2515     {
2516       TT_CMap13  cmap13 = (TT_CMap13)cmap;
2517
2518
2519       /* if `char_code' is not in any group, then `mid' is */
2520       /* the group nearest to `char_code'                  */
2521
2522       if ( char_code > end )
2523       {
2524         mid++;
2525         if ( mid == num_groups )
2526           return 0;
2527       }
2528
2529       cmap13->valid        = 1;
2530       cmap13->cur_charcode = char_code;
2531       cmap13->cur_group    = mid;
2532
2533       if ( !gindex )
2534       {
2535         tt_cmap13_next( cmap13 );
2536
2537         if ( cmap13->valid )
2538           gindex = cmap13->cur_gindex;
2539       }
2540       else
2541         cmap13->cur_gindex = gindex;
2542
2543       if ( gindex )
2544         *pchar_code = cmap13->cur_charcode;
2545     }
2546
2547     return gindex;
2548   }
2549
2550
2551   FT_CALLBACK_DEF( FT_UInt )
2552   tt_cmap13_char_index( TT_CMap    cmap,
2553                         FT_UInt32  char_code )
2554   {
2555     return tt_cmap13_char_map_binary( cmap, &char_code, 0 );
2556   }
2557
2558
2559   FT_CALLBACK_DEF( FT_UInt32 )
2560   tt_cmap13_char_next( TT_CMap     cmap,
2561                        FT_UInt32  *pchar_code )
2562   {
2563     TT_CMap13  cmap13 = (TT_CMap13)cmap;
2564     FT_UInt    gindex;
2565
2566
2567     if ( cmap13->cur_charcode >= 0xFFFFFFFFUL )
2568       return 0;
2569
2570     /* no need to search */
2571     if ( cmap13->valid && cmap13->cur_charcode == *pchar_code )
2572     {
2573       tt_cmap13_next( cmap13 );
2574       if ( cmap13->valid )
2575       {
2576         gindex = cmap13->cur_gindex;
2577         if ( gindex )
2578           *pchar_code = cmap13->cur_charcode;
2579       }
2580       else
2581         gindex = 0;
2582     }
2583     else
2584       gindex = tt_cmap13_char_map_binary( cmap, pchar_code, 1 );
2585
2586     return gindex;
2587   }
2588
2589
2590   FT_CALLBACK_DEF( FT_Error )
2591   tt_cmap13_get_info( TT_CMap       cmap,
2592                       TT_CMapInfo  *cmap_info )
2593   {
2594     FT_Byte*  p = cmap->data + 8;
2595
2596
2597     cmap_info->format   = 13;
2598     cmap_info->language = (FT_ULong)TT_PEEK_ULONG( p );
2599
2600     return FT_Err_Ok;
2601   }
2602
2603
2604   FT_DEFINE_TT_CMAP(
2605     tt_cmap13_class_rec,
2606     sizeof ( TT_CMap13Rec ),
2607
2608     (FT_CMap_InitFunc)     tt_cmap13_init,
2609     (FT_CMap_DoneFunc)     NULL,
2610     (FT_CMap_CharIndexFunc)tt_cmap13_char_index,
2611     (FT_CMap_CharNextFunc) tt_cmap13_char_next,
2612
2613     NULL,
2614     NULL,
2615     NULL,
2616     NULL,
2617     NULL,
2618
2619     13,
2620     (TT_CMap_ValidateFunc)tt_cmap13_validate,
2621     (TT_CMap_Info_GetFunc)tt_cmap13_get_info )
2622
2623 #endif /* TT_CONFIG_CMAP_FORMAT_13 */
2624
2625
2626   /*************************************************************************/
2627   /*************************************************************************/
2628   /*****                                                               *****/
2629   /*****                           FORMAT 14                           *****/
2630   /*****                                                               *****/
2631   /*************************************************************************/
2632   /*************************************************************************/
2633
2634   /*************************************************************************/
2635   /*                                                                       */
2636   /* TABLE OVERVIEW                                                        */
2637   /* --------------                                                        */
2638   /*                                                                       */
2639   /*   NAME         OFFSET  TYPE    DESCRIPTION                            */
2640   /*                                                                       */
2641   /*   format         0     USHORT  must be 14                             */
2642   /*   length         2     ULONG   table length in bytes                  */
2643   /*   numSelector    6     ULONG   number of variation sel. records       */
2644   /*                                                                       */
2645   /* Followed by numSelector records, each of which looks like             */
2646   /*                                                                       */
2647   /*   varSelector    0     UINT24  Unicode codepoint of sel.              */
2648   /*   defaultOff     3     ULONG   offset to a default UVS table          */
2649   /*                                describing any variants to be found in */
2650   /*                                the normal Unicode subtable.           */
2651   /*   nonDefOff      7     ULONG   offset to a non-default UVS table      */
2652   /*                                describing any variants not in the     */
2653   /*                                standard cmap, with GIDs here          */
2654   /* (either offset may be 0 NULL)                                         */
2655   /*                                                                       */
2656   /* Selectors are sorted by code point.                                   */
2657   /*                                                                       */
2658   /* A default Unicode Variation Selector (UVS) subtable is just a list of */
2659   /* ranges of code points which are to be found in the standard cmap.  No */
2660   /* glyph IDs (GIDs) here.                                                */
2661   /*                                                                       */
2662   /*   numRanges      0     ULONG   number of ranges following             */
2663   /*                                                                       */
2664   /* A range looks like                                                    */
2665   /*                                                                       */
2666   /*   uniStart       0     UINT24  code point of the first character in   */
2667   /*                                this range                             */
2668   /*   additionalCnt  3     UBYTE   count of additional characters in this */
2669   /*                                range (zero means a range of a single  */
2670   /*                                character)                             */
2671   /*                                                                       */
2672   /* Ranges are sorted by `uniStart'.                                      */
2673   /*                                                                       */
2674   /* A non-default Unicode Variation Selector (UVS) subtable is a list of  */
2675   /* mappings from codepoint to GID.                                       */
2676   /*                                                                       */
2677   /*   numMappings    0     ULONG   number of mappings                     */
2678   /*                                                                       */
2679   /* A range looks like                                                    */
2680   /*                                                                       */
2681   /*   uniStart       0     UINT24  code point of the first character in   */
2682   /*                                this range                             */
2683   /*   GID            3     USHORT  and its GID                            */
2684   /*                                                                       */
2685   /* Ranges are sorted by `uniStart'.                                      */
2686
2687 #ifdef TT_CONFIG_CMAP_FORMAT_14
2688
2689   typedef struct  TT_CMap14Rec_
2690   {
2691     TT_CMapRec  cmap;
2692     FT_ULong    num_selectors;
2693
2694     /* This array is used to store the results of various
2695      * cmap 14 query functions.  The data is overwritten
2696      * on each call to these functions.
2697      */
2698     FT_UInt32   max_results;
2699     FT_UInt32*  results;
2700     FT_Memory   memory;
2701
2702   } TT_CMap14Rec, *TT_CMap14;
2703
2704
2705   FT_CALLBACK_DEF( void )
2706   tt_cmap14_done( TT_CMap14  cmap )
2707   {
2708     FT_Memory  memory = cmap->memory;
2709
2710
2711     cmap->max_results = 0;
2712     if ( memory != NULL && cmap->results != NULL )
2713       FT_FREE( cmap->results );
2714   }
2715
2716
2717   static FT_Error
2718   tt_cmap14_ensure( TT_CMap14  cmap,
2719                     FT_UInt32  num_results,
2720                     FT_Memory  memory )
2721   {
2722     FT_UInt32  old_max = cmap->max_results;
2723     FT_Error   error   = FT_Err_Ok;
2724
2725
2726     if ( num_results > cmap->max_results )
2727     {
2728        cmap->memory = memory;
2729
2730        if ( FT_QRENEW_ARRAY( cmap->results, old_max, num_results ) )
2731          return error;
2732
2733        cmap->max_results = num_results;
2734     }
2735
2736     return error;
2737   }
2738
2739
2740   FT_CALLBACK_DEF( FT_Error )
2741   tt_cmap14_init( TT_CMap14  cmap,
2742                   FT_Byte*   table )
2743   {
2744     cmap->cmap.data = table;
2745
2746     table               += 6;
2747     cmap->num_selectors  = FT_PEEK_ULONG( table );
2748     cmap->max_results    = 0;
2749     cmap->results        = NULL;
2750
2751     return FT_Err_Ok;
2752   }
2753
2754
2755   FT_CALLBACK_DEF( FT_Error )
2756   tt_cmap14_validate( FT_Byte*      table,
2757                       FT_Validator  valid )
2758   {
2759     FT_Byte*  p             = table + 2;
2760     FT_ULong  length        = TT_NEXT_ULONG( p );
2761     FT_ULong  num_selectors = TT_NEXT_ULONG( p );
2762
2763
2764     if ( length > (FT_ULong)( valid->limit - table ) ||
2765          length < 10 + 11 * num_selectors            )
2766       FT_INVALID_TOO_SHORT;
2767
2768     /* check selectors, they must be in increasing order */
2769     {
2770       /* we start lastVarSel at 1 because a variant selector value of 0
2771        * isn't valid.
2772        */
2773       FT_ULong  n, lastVarSel = 1;
2774
2775
2776       for ( n = 0; n < num_selectors; n++ )
2777       {
2778         FT_ULong  varSel    = TT_NEXT_UINT24( p );
2779         FT_ULong  defOff    = TT_NEXT_ULONG( p );
2780         FT_ULong  nondefOff = TT_NEXT_ULONG( p );
2781
2782
2783         if ( defOff >= length || nondefOff >= length )
2784           FT_INVALID_TOO_SHORT;
2785
2786         if ( varSel < lastVarSel )
2787           FT_INVALID_DATA;
2788
2789         lastVarSel = varSel + 1;
2790
2791         /* check the default table (these glyphs should be reached     */
2792         /* through the normal Unicode cmap, no GIDs, just check order) */
2793         if ( defOff != 0 )
2794         {
2795           FT_Byte*  defp      = table + defOff;
2796           FT_ULong  numRanges = TT_NEXT_ULONG( defp );
2797           FT_ULong  i;
2798           FT_ULong  lastBase  = 0;
2799
2800
2801           if ( defp + numRanges * 4 > valid->limit )
2802             FT_INVALID_TOO_SHORT;
2803
2804           for ( i = 0; i < numRanges; ++i )
2805           {
2806             FT_ULong  base = TT_NEXT_UINT24( defp );
2807             FT_ULong  cnt  = FT_NEXT_BYTE( defp );
2808
2809
2810             if ( base + cnt >= 0x110000UL )              /* end of Unicode */
2811               FT_INVALID_DATA;
2812
2813             if ( base < lastBase )
2814               FT_INVALID_DATA;
2815
2816             lastBase = base + cnt + 1U;
2817           }
2818         }
2819
2820         /* and the non-default table (these glyphs are specified here) */
2821         if ( nondefOff != 0 )
2822         {
2823           FT_Byte*  ndp         = table + nondefOff;
2824           FT_ULong  numMappings = TT_NEXT_ULONG( ndp );
2825           FT_ULong  i, lastUni  = 0;
2826
2827
2828           if ( numMappings * 4 > (FT_ULong)( valid->limit - ndp ) )
2829             FT_INVALID_TOO_SHORT;
2830
2831           for ( i = 0; i < numMappings; ++i )
2832           {
2833             FT_ULong  uni = TT_NEXT_UINT24( ndp );
2834             FT_ULong  gid = TT_NEXT_USHORT( ndp );
2835
2836
2837             if ( uni >= 0x110000UL )                     /* end of Unicode */
2838               FT_INVALID_DATA;
2839
2840             if ( uni < lastUni )
2841               FT_INVALID_DATA;
2842
2843             lastUni = uni + 1U;
2844
2845             if ( valid->level >= FT_VALIDATE_TIGHT    &&
2846                  gid >= TT_VALID_GLYPH_COUNT( valid ) )
2847               FT_INVALID_GLYPH_ID;
2848           }
2849         }
2850       }
2851     }
2852
2853     return FT_Err_Ok;
2854   }
2855
2856
2857   FT_CALLBACK_DEF( FT_UInt )
2858   tt_cmap14_char_index( TT_CMap    cmap,
2859                         FT_UInt32  char_code )
2860   {
2861     FT_UNUSED( cmap );
2862     FT_UNUSED( char_code );
2863
2864     /* This can't happen */
2865     return 0;
2866   }
2867
2868
2869   FT_CALLBACK_DEF( FT_UInt32 )
2870   tt_cmap14_char_next( TT_CMap     cmap,
2871                        FT_UInt32  *pchar_code )
2872   {
2873     FT_UNUSED( cmap );
2874
2875     /* This can't happen */
2876     *pchar_code = 0;
2877     return 0;
2878   }
2879
2880
2881   FT_CALLBACK_DEF( FT_Error )
2882   tt_cmap14_get_info( TT_CMap       cmap,
2883                       TT_CMapInfo  *cmap_info )
2884   {
2885     FT_UNUSED( cmap );
2886
2887     cmap_info->format   = 14;
2888     /* subtable 14 does not define a language field */
2889     cmap_info->language = 0xFFFFFFFFUL;
2890
2891     return FT_Err_Ok;
2892   }
2893
2894
2895   static FT_UInt
2896   tt_cmap14_char_map_def_binary( FT_Byte    *base,
2897                                  FT_UInt32   char_code )
2898   {
2899     FT_UInt32  numRanges = TT_PEEK_ULONG( base );
2900     FT_UInt32  max, min;
2901
2902
2903     min = 0;
2904     max = numRanges;
2905
2906     base += 4;
2907
2908     /* binary search */
2909     while ( min < max )
2910     {
2911       FT_UInt32  mid   = ( min + max ) >> 1;
2912       FT_Byte*   p     = base + 4 * mid;
2913       FT_ULong   start = TT_NEXT_UINT24( p );
2914       FT_UInt    cnt   = FT_NEXT_BYTE( p );
2915
2916
2917       if ( char_code < start )
2918         max = mid;
2919       else if ( char_code > start+cnt )
2920         min = mid + 1;
2921       else
2922         return TRUE;
2923     }
2924
2925     return FALSE;
2926   }
2927
2928
2929   static FT_UInt
2930   tt_cmap14_char_map_nondef_binary( FT_Byte    *base,
2931                                     FT_UInt32   char_code )
2932   {
2933     FT_UInt32  numMappings = TT_PEEK_ULONG( base );
2934     FT_UInt32  max, min;
2935
2936
2937     min = 0;
2938     max = numMappings;
2939
2940     base += 4;
2941
2942     /* binary search */
2943     while ( min < max )
2944     {
2945       FT_UInt32  mid = ( min + max ) >> 1;
2946       FT_Byte*   p   = base + 5 * mid;
2947       FT_UInt32  uni = (FT_UInt32)TT_NEXT_UINT24( p );
2948
2949
2950       if ( char_code < uni )
2951         max = mid;
2952       else if ( char_code > uni )
2953         min = mid + 1;
2954       else
2955         return TT_PEEK_USHORT( p );
2956     }
2957
2958     return 0;
2959   }
2960
2961
2962   static FT_Byte*
2963   tt_cmap14_find_variant( FT_Byte    *base,
2964                           FT_UInt32   variantCode )
2965   {
2966     FT_UInt32  numVar = TT_PEEK_ULONG( base );
2967     FT_UInt32  max, min;
2968
2969
2970     min = 0;
2971     max = numVar;
2972
2973     base += 4;
2974
2975     /* binary search */
2976     while ( min < max )
2977     {
2978       FT_UInt32  mid    = ( min + max ) >> 1;
2979       FT_Byte*   p      = base + 11 * mid;
2980       FT_ULong   varSel = TT_NEXT_UINT24( p );
2981
2982
2983       if ( variantCode < varSel )
2984         max = mid;
2985       else if ( variantCode > varSel )
2986         min = mid + 1;
2987       else
2988         return p;
2989     }
2990
2991     return NULL;
2992   }
2993
2994
2995   FT_CALLBACK_DEF( FT_UInt )
2996   tt_cmap14_char_var_index( TT_CMap    cmap,
2997                             TT_CMap    ucmap,
2998                             FT_UInt32  charcode,
2999                             FT_UInt32  variantSelector )
3000   {
3001     FT_Byte*  p = tt_cmap14_find_variant( cmap->data + 6, variantSelector );
3002     FT_ULong  defOff;
3003     FT_ULong  nondefOff;
3004
3005
3006     if ( !p )
3007       return 0;
3008
3009     defOff    = TT_NEXT_ULONG( p );
3010     nondefOff = TT_PEEK_ULONG( p );
3011
3012     if ( defOff != 0                                                    &&
3013          tt_cmap14_char_map_def_binary( cmap->data + defOff, charcode ) )
3014     {
3015       /* This is the default variant of this charcode.  GID not stored */
3016       /* here; stored in the normal Unicode charmap instead.           */
3017       return ucmap->cmap.clazz->char_index( &ucmap->cmap, charcode );
3018     }
3019
3020     if ( nondefOff != 0 )
3021       return tt_cmap14_char_map_nondef_binary( cmap->data + nondefOff,
3022                                                charcode );
3023
3024     return 0;
3025   }
3026
3027
3028   FT_CALLBACK_DEF( FT_Int )
3029   tt_cmap14_char_var_isdefault( TT_CMap    cmap,
3030                                 FT_UInt32  charcode,
3031                                 FT_UInt32  variantSelector )
3032   {
3033     FT_Byte*  p = tt_cmap14_find_variant( cmap->data + 6, variantSelector );
3034     FT_ULong  defOff;
3035     FT_ULong  nondefOff;
3036
3037
3038     if ( !p )
3039       return -1;
3040
3041     defOff    = TT_NEXT_ULONG( p );
3042     nondefOff = TT_NEXT_ULONG( p );
3043
3044     if ( defOff != 0                                                    &&
3045          tt_cmap14_char_map_def_binary( cmap->data + defOff, charcode ) )
3046       return 1;
3047
3048     if ( nondefOff != 0                                            &&
3049          tt_cmap14_char_map_nondef_binary( cmap->data + nondefOff,
3050                                            charcode ) != 0         )
3051       return 0;
3052
3053     return -1;
3054   }
3055
3056
3057   FT_CALLBACK_DEF( FT_UInt32* )
3058   tt_cmap14_variants( TT_CMap    cmap,
3059                       FT_Memory  memory )
3060   {
3061     TT_CMap14   cmap14 = (TT_CMap14)cmap;
3062     FT_UInt32   count  = cmap14->num_selectors;
3063     FT_Byte*    p      = cmap->data + 10;
3064     FT_UInt32*  result;
3065     FT_UInt32   i;
3066
3067
3068     if ( tt_cmap14_ensure( cmap14, ( count + 1 ), memory ) )
3069       return NULL;
3070
3071