src/third_party/freetype2/src/src/sfnt/ttcmap.c

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