reactos/lib/freetype/src/sfnt/ttkern.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ttkern.c                                                               */
   4 /*                                                                         */
   5 /*    Load the basic TrueType kerning table.  This doesn't handle          */
   6 /*    kerning data within the GPOS table at the moment.                    */
   7 /*                                                                         */
   8 /*  Copyright 1996-2001, 2002, 2003, 2004, 2005 by                         */
   9 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
  10 /*                                                                         */
  11 /*  This file is part of the FreeType project, and may only be used,       */
  12 /*  modified, and distributed under the terms of the FreeType project      */
  13 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
  14 /*  this file you indicate that you have read the license and              */
  15 /*  understand and accept it fully.                                        */
  16 /*                                                                         */
  17 /***************************************************************************/
  18
  19
  20 #include <ft2build.h>
  21 #include FT_INTERNAL_DEBUG_H
  22 #include FT_INTERNAL_STREAM_H
  23 #include FT_TRUETYPE_TAGS_H
  24 #include "ttkern.h"
  25 #include "ttload.h"
  26
  27 #include "sferrors.h"
  28
  29
  30   /*************************************************************************/
  31   /*                                                                       */
  32   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
  33   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
  34   /* messages during execution.                                            */
  35   /*                                                                       */
  36 #undef  FT_COMPONENT
  37 #define FT_COMPONENT  trace_ttkern
  38
  39
  40 #undef  TT_KERN_INDEX
  41 #define TT_KERN_INDEX( g1, g2 )  ( ( (FT_ULong)(g1) << 16 ) | (g2) )
  42
  43
  44 #ifdef FT_OPTIMIZE_MEMORY
  45
  46   FT_LOCAL_DEF( FT_Error )
  47   tt_face_load_kern( TT_Face    face,
  48                      FT_Stream  stream )
  49   {
  50     FT_Error   error;
  51     FT_ULong   table_size;
  52     FT_Byte*   p;
  53     FT_Byte*   p_limit;
  54     FT_UInt    nn, num_tables;
  55     FT_UInt32  avail = 0, ordered = 0;
  56
  57
  58     /* the kern table is optional; exit silently if it is missing */
  59     error = face->goto_table( face, TTAG_kern, stream, &table_size );
  60     if ( error )
  61       goto Exit;
  62
  63     if ( table_size < 4 )  /* the case of a malformed table */
  64     {
  65       FT_ERROR(( "kerning table is too small - ignored\n" ));
  66       error = SFNT_Err_Table_Missing;
  67       goto Exit;
  68     }
  69
  70     if ( FT_FRAME_EXTRACT( table_size, face->kern_table ) )
  71     {
  72       FT_ERROR(( "could not extract kerning table\n" ));
  73       goto Exit;
  74     }
  75
  76     face->kern_table_size = table_size;
  77
  78     p       = face->kern_table;
  79     p_limit = p + table_size;
  80
  81     p         += 2; /* skip version */
  82     num_tables = FT_NEXT_USHORT( p );
  83
  84     if ( num_tables > 32 ) /* we only support up to 32 sub-tables */
  85       num_tables = 32;
  86
  87     for ( nn = 0; nn < num_tables; nn++ )
  88     {
  89       FT_UInt    num_pairs, version, length, coverage;
  90       FT_Byte*   p_next;
  91       FT_UInt32  mask = 1UL << nn;
  92
  93
  94       if ( p + 6 > p_limit )
  95         break;
  96
  97       p_next = p;
  98
  99       version  = FT_NEXT_USHORT( p );
 100       length   = FT_NEXT_USHORT( p );
 101       coverage = FT_NEXT_USHORT( p );
 102
 103       if ( length <= 6 )
 104         break;
 105
 106       p_next += length;
 107
 108       /* only use horizontal kerning tables */
 109       if ( ( coverage & ~8 ) != 0x0001 ||
 110            p + 8 > p_limit             )
 111         goto NextTable;
 112
 113       num_pairs = FT_NEXT_USHORT( p );
 114       p        += 6;
 115
 116       if ( p + 6 * num_pairs > p_limit )
 117         goto NextTable;
 118
 119       avail |= mask;
 120
 121       /*
 122        *  Now check whether the pairs in this table are ordered.
 123        *  We then can use binary search.
 124        */
 125       if ( num_pairs > 0 )
 126       {
 127         FT_UInt  count;
 128         FT_UInt  old_pair;
 129
 130
 131         old_pair = FT_NEXT_ULONG( p );
 132         p       += 2;
 133
 134         for ( count = num_pairs - 1; count > 0; count-- )
 135         {
 136           FT_UInt32  cur_pair;
 137
 138
 139           cur_pair = FT_NEXT_ULONG( p );
 140           if ( cur_pair <= old_pair )
 141             break;
 142
 143           p += 2;
 144           old_pair = cur_pair;
 145         }
 146
 147         if ( count == 0 )
 148           ordered |= mask;
 149       }
 150
 151     NextTable:
 152       p = p_next;
 153     }
 154
 155     face->num_kern_tables = nn;
 156     face->kern_avail_bits = avail;
 157     face->kern_order_bits = ordered;
 158
 159   Exit:
 160     return error;
 161   }
 162
 163
 164   FT_LOCAL_DEF( void )
 165   tt_face_done_kern( TT_Face  face )
 166   {
 167     FT_Stream  stream = face->root.stream;
 168
 169
 170     FT_FRAME_RELEASE( face->kern_table );
 171     face->kern_table_size = 0;
 172     face->num_kern_tables = 0;
 173     face->kern_avail_bits = 0;
 174     face->kern_order_bits = 0;
 175   }
 176
 177
 178   FT_LOCAL_DEF( FT_Int )
 179   tt_face_get_kerning( TT_Face  face,
 180                        FT_UInt  left_glyph,
 181                        FT_UInt  right_glyph )
 182   {
 183     FT_Int    result = 0;
 184     FT_UInt   count, mask = 1;
 185     FT_Byte*  p       = face->kern_table;
 186
 187
 188     p   += 4;
 189     mask = 0x0001;
 190
 191     for ( count = face->num_kern_tables; count > 0; count--, mask <<= 1 )
 192     {
 193       FT_Byte* base     = p;
 194       FT_Byte* next     = base;
 195       FT_UInt  version  = FT_NEXT_USHORT( p );
 196       FT_UInt  length   = FT_NEXT_USHORT( p );
 197       FT_UInt  coverage = FT_NEXT_USHORT( p );
 198       FT_Int   value    = 0;
 199
 200       FT_UNUSED( version );
 201
 202
 203       next = base + length;
 204
 205       if ( ( face->kern_avail_bits & mask ) == 0 )
 206         goto NextTable;
 207
 208       if ( p + 8 > next )
 209         goto NextTable;
 210
 211       switch ( coverage >> 8 )
 212       {
 213       case 0:
 214         {
 215           FT_UInt   num_pairs = FT_NEXT_USHORT( p );
 216           FT_ULong  key0      = TT_KERN_INDEX( left_glyph, right_glyph );
 217
 218
 219           p += 6;
 220
 221           if ( face->kern_order_bits & mask )   /* binary search */
 222           {
 223             FT_UInt   min = 0;
 224             FT_UInt   max = num_pairs;
 225
 226
 227             while ( min < max )
 228             {
 229               FT_UInt   mid = ( min + max ) >> 1;
 230               FT_Byte*  q   = p + 6 * mid;
 231               FT_ULong  key;
 232
 233
 234               key = FT_NEXT_ULONG( q );
 235
 236               if ( key == key0 )
 237               {
 238                 value = FT_PEEK_SHORT( q );
 239                 goto Found;
 240               }
 241               if ( key < key0 )
 242                 min = mid + 1;
 243               else
 244                 max = mid;
 245             }
 246           }
 247           else /* linear search */
 248           {
 249             for ( count = num_pairs; count > 0; count-- )
 250             {
 251               FT_ULong  key = FT_NEXT_ULONG( p );
 252
 253
 254               if ( key == key0 )
 255               {
 256                 value = FT_PEEK_SHORT( p );
 257                 goto Found;
 258               }
 259               p += 2;
 260             }
 261           }
 262         }
 263         break;
 264
 265        /*
 266         *  We don't support format 2 because we've never seen a single font
 267         *  using it in real life...
 268         */
 269
 270       default:
 271         ;
 272       }
 273
 274       goto NextTable;
 275
 276     Found:
 277       if ( coverage & 8 ) /* overide or add */
 278         result = value;
 279       else
 280         result += value;
 281
 282     NextTable:
 283       p = next;
 284     }
 285
 286     return result;
 287   }
 288
 289 #else /* !OPTIMIZE_MEMORY */
 290
 291   FT_CALLBACK_DEF( int )
 292   tt_kern_pair_compare( const void*  a,
 293                         const void*  b );
 294
 295
 296   FT_LOCAL_DEF( FT_Error )
 297   tt_face_load_kern( TT_Face    face,
 298                      FT_Stream  stream )
 299   {
 300     FT_Error   error;
 301     FT_Memory  memory = stream->memory;
 302
 303     FT_UInt    n, num_tables;
 304
 305
 306     /* the kern table is optional; exit silently if it is missing */
 307     error = face->goto_table( face, TTAG_kern, stream, 0 );
 308     if ( error )
 309       return SFNT_Err_Ok;
 310
 311     if ( FT_FRAME_ENTER( 4L ) )
 312       goto Exit;
 313
 314     (void)FT_GET_USHORT();         /* version */
 315     num_tables = FT_GET_USHORT();
 316
 317     FT_FRAME_EXIT();
 318
 319     for ( n = 0; n < num_tables; n++ )
 320     {
 321       FT_UInt  coverage;
 322       FT_UInt  length;
 323
 324
 325       if ( FT_FRAME_ENTER( 6L ) )
 326         goto Exit;
 327
 328       (void)FT_GET_USHORT();           /* version                 */
 329       length   = FT_GET_USHORT() - 6;  /* substract header length */
 330       coverage = FT_GET_USHORT();
 331
 332       FT_FRAME_EXIT();
 333
 334       if ( coverage == 0x0001 )
 335       {
 336         FT_UInt        num_pairs;
 337         TT_Kern0_Pair  pair;
 338         TT_Kern0_Pair  limit;
 339
 340
 341         /* found a horizontal format 0 kerning table! */
 342         if ( FT_FRAME_ENTER( 8L ) )
 343           goto Exit;
 344
 345         num_pairs = FT_GET_USHORT();
 346
 347         /* skip the rest */
 348
 349         FT_FRAME_EXIT();
 350
 351         /* allocate array of kerning pairs */
 352         if ( FT_QNEW_ARRAY( face->kern_pairs, num_pairs ) ||
 353              FT_FRAME_ENTER( 6L * num_pairs )             )
 354           goto Exit;
 355
 356         pair  = face->kern_pairs;
 357         limit = pair + num_pairs;
 358         for ( ; pair < limit; pair++ )
 359         {
 360           pair->left  = FT_GET_USHORT();
 361           pair->right = FT_GET_USHORT();
 362           pair->value = FT_GET_USHORT();
 363         }
 364
 365         FT_FRAME_EXIT();
 366
 367         face->num_kern_pairs   = num_pairs;
 368         face->kern_table_index = n;
 369
 370         /* ensure that the kerning pair table is sorted (yes, some */
 371         /* fonts have unsorted tables!)                            */
 372
 373         if ( num_pairs > 0 )
 374         {
 375           TT_Kern0_Pair  pair0 = face->kern_pairs;
 376           FT_ULong       prev  = TT_KERN_INDEX( pair0->left, pair0->right );
 377
 378
 379           for ( pair0++; pair0 < limit; pair0++ )
 380           {
 381             FT_ULong  next = TT_KERN_INDEX( pair0->left, pair0->right );
 382
 383
 384             if ( next < prev )
 385               goto SortIt;
 386
 387             prev = next;
 388           }
 389           goto Exit;
 390
 391         SortIt:
 392           ft_qsort( (void*)face->kern_pairs, (int)num_pairs,
 393                     sizeof ( TT_Kern0_PairRec ), tt_kern_pair_compare );
 394         }
 395
 396         goto Exit;
 397       }
 398
 399       if ( FT_STREAM_SKIP( length ) )
 400         goto Exit;
 401     }
 402
 403     /* no kern table found -- doesn't matter */
 404     face->kern_table_index = -1;
 405     face->num_kern_pairs   = 0;
 406     face->kern_pairs       = NULL;
 407
 408   Exit:
 409     return error;
 410   }
 411
 412
 413   FT_CALLBACK_DEF( int )
 414   tt_kern_pair_compare( const void*  a,
 415                         const void*  b )
 416   {
 417     TT_Kern0_Pair  pair1 = (TT_Kern0_Pair)a;
 418     TT_Kern0_Pair  pair2 = (TT_Kern0_Pair)b;
 419
 420     FT_ULong  index1 = TT_KERN_INDEX( pair1->left, pair1->right );
 421     FT_ULong  index2 = TT_KERN_INDEX( pair2->left, pair2->right );
 422
 423     return index1 < index2 ? -1
 424                            : ( index1 > index2 ? 1
 425                                                : 0 );
 426   }
 427
 428
 429   FT_LOCAL_DEF( void )
 430   tt_face_done_kern( TT_Face  face )
 431   {
 432     FT_Memory  memory = face->root.stream->memory;
 433
 434
 435     FT_FREE( face->kern_pairs );
 436     face->num_kern_pairs = 0;
 437   }
 438
 439
 440   FT_LOCAL_DEF( FT_Int )
 441   tt_face_get_kerning( TT_Face  face,
 442                        FT_UInt  left_glyph,
 443                        FT_UInt  right_glyph )
 444   {
 445     FT_Int         result = 0;
 446     TT_Kern0_Pair  pair;
 447
 448
 449     if ( face && face->kern_pairs )
 450     {
 451       /* there are some kerning pairs in this font file! */
 452       FT_ULong  search_tag = TT_KERN_INDEX( left_glyph, right_glyph );
 453       FT_Long   left, right;
 454
 455
 456       left  = 0;
 457       right = face->num_kern_pairs - 1;
 458
 459       while ( left <= right )
 460       {
 461         FT_Long   middle = left + ( ( right - left ) >> 1 );
 462         FT_ULong  cur_pair;
 463
 464
 465         pair     = face->kern_pairs + middle;
 466         cur_pair = TT_KERN_INDEX( pair->left, pair->right );
 467
 468         if ( cur_pair == search_tag )
 469           goto Found;
 470
 471         if ( cur_pair < search_tag )
 472           left = middle + 1;
 473         else
 474           right = middle - 1;
 475       }
 476     }
 477
 478   Exit:
 479     return result;
 480
 481   Found:
 482     result = pair->value;
 483     goto Exit;
 484   }
 485
 486 #endif /* !OPTIMIZE_MEMORY */
 487
 488
 489 #undef TT_KERN_INDEX
 490
 491 /* END */