lib/3rdparty/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, 2006, 2007 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   FT_LOCAL_DEF( FT_Error )
  45   tt_face_load_kern( TT_Face    face,
  46                      FT_Stream  stream )
  47   {
  48     FT_Error   error;
  49     FT_ULong   table_size;
  50     FT_Byte*   p;
  51     FT_Byte*   p_limit;
  52     FT_UInt    nn, num_tables;
  53     FT_UInt32  avail = 0, ordered = 0;
  54
  55
  56     /* the kern table is optional; exit silently if it is missing */
  57     error = face->goto_table( face, TTAG_kern, stream, &table_size );
  58     if ( error )
  59       goto Exit;
  60
  61     if ( table_size < 4 )  /* the case of a malformed table */
  62     {
  63       FT_ERROR(( "kerning table is too small - ignored\n" ));
  64       error = SFNT_Err_Table_Missing;
  65       goto Exit;
  66     }
  67
  68     if ( FT_FRAME_EXTRACT( table_size, face->kern_table ) )
  69     {
  70       FT_ERROR(( "could not extract kerning table\n" ));
  71       goto Exit;
  72     }
  73
  74     face->kern_table_size = table_size;
  75
  76     p       = face->kern_table;
  77     p_limit = p + table_size;
  78
  79     p         += 2; /* skip version */
  80     num_tables = FT_NEXT_USHORT( p );
  81
  82     if ( num_tables > 32 ) /* we only support up to 32 sub-tables */
  83       num_tables = 32;
  84
  85     for ( nn = 0; nn < num_tables; nn++ )
  86     {
  87       FT_UInt    num_pairs, length, coverage;
  88       FT_Byte*   p_next;
  89       FT_UInt32  mask = 1UL << nn;
  90
  91
  92       if ( p + 6 > p_limit )
  93         break;
  94
  95       p_next = p;
  96
  97       p += 2; /* skip version */
  98       length   = FT_NEXT_USHORT( p );
  99       coverage = FT_NEXT_USHORT( p );
 100
 101       if ( length <= 6 )
 102         break;
 103
 104       p_next += length;
 105
 106       /* only use horizontal kerning tables */
 107       if ( ( coverage & ~8 ) != 0x0001 ||
 108            p + 8 > p_limit             )
 109         goto NextTable;
 110
 111       num_pairs = FT_NEXT_USHORT( p );
 112       p        += 6;
 113
 114       if ( p + 6 * num_pairs > p_limit )
 115         goto NextTable;
 116
 117       avail |= mask;
 118
 119       /*
 120        *  Now check whether the pairs in this table are ordered.
 121        *  We then can use binary search.
 122        */
 123       if ( num_pairs > 0 )
 124       {
 125         FT_UInt  count;
 126         FT_UInt  old_pair;
 127
 128
 129         old_pair = FT_NEXT_ULONG( p );
 130         p       += 2;
 131
 132         for ( count = num_pairs - 1; count > 0; count-- )
 133         {
 134           FT_UInt32  cur_pair;
 135
 136
 137           cur_pair = FT_NEXT_ULONG( p );
 138           if ( cur_pair <= old_pair )
 139             break;
 140
 141           p += 2;
 142           old_pair = cur_pair;
 143         }
 144
 145         if ( count == 0 )
 146           ordered |= mask;
 147       }
 148
 149     NextTable:
 150       p = p_next;
 151     }
 152
 153     face->num_kern_tables = nn;
 154     face->kern_avail_bits = avail;
 155     face->kern_order_bits = ordered;
 156
 157   Exit:
 158     return error;
 159   }
 160
 161
 162   FT_LOCAL_DEF( void )
 163   tt_face_done_kern( TT_Face  face )
 164   {
 165     FT_Stream  stream = face->root.stream;
 166
 167
 168     FT_FRAME_RELEASE( face->kern_table );
 169     face->kern_table_size = 0;
 170     face->num_kern_tables = 0;
 171     face->kern_avail_bits = 0;
 172     face->kern_order_bits = 0;
 173   }
 174
 175
 176   FT_LOCAL_DEF( FT_Int )
 177   tt_face_get_kerning( TT_Face  face,
 178                        FT_UInt  left_glyph,
 179                        FT_UInt  right_glyph )
 180   {
 181     FT_Int    result = 0;
 182     FT_UInt   count, mask = 1;
 183     FT_Byte*  p       = face->kern_table;
 184
 185
 186     p   += 4;
 187     mask = 0x0001;
 188
 189     for ( count = face->num_kern_tables; count > 0; count--, mask <<= 1 )
 190     {
 191       FT_Byte* base     = p;
 192       FT_Byte* next     = base;
 193       FT_UInt  version  = FT_NEXT_USHORT( p );
 194       FT_UInt  length   = FT_NEXT_USHORT( p );
 195       FT_UInt  coverage = FT_NEXT_USHORT( p );
 196       FT_Int   value    = 0;
 197
 198       FT_UNUSED( version );
 199
 200
 201       next = base + length;
 202
 203       if ( ( face->kern_avail_bits & mask ) == 0 )
 204         goto NextTable;
 205
 206       if ( p + 8 > next )
 207         goto NextTable;
 208
 209       switch ( coverage >> 8 )
 210       {
 211       case 0:
 212         {
 213           FT_UInt   num_pairs = FT_NEXT_USHORT( p );
 214           FT_ULong  key0      = TT_KERN_INDEX( left_glyph, right_glyph );
 215
 216
 217           p += 6;
 218
 219           if ( face->kern_order_bits & mask )   /* binary search */
 220           {
 221             FT_UInt   min = 0;
 222             FT_UInt   max = num_pairs;
 223
 224
 225             while ( min < max )
 226             {
 227               FT_UInt   mid = ( min + max ) >> 1;
 228               FT_Byte*  q   = p + 6 * mid;
 229               FT_ULong  key;
 230
 231
 232               key = FT_NEXT_ULONG( q );
 233
 234               if ( key == key0 )
 235               {
 236                 value = FT_PEEK_SHORT( q );
 237                 goto Found;
 238               }
 239               if ( key < key0 )
 240                 min = mid + 1;
 241               else
 242                 max = mid;
 243             }
 244           }
 245           else /* linear search */
 246           {
 247             FT_UInt  count2;
 248
 249
 250             for ( count2 = num_pairs; count2 > 0; count2-- )
 251             {
 252               FT_ULong  key = FT_NEXT_ULONG( p );
 253
 254
 255               if ( key == key0 )
 256               {
 257                 value = FT_PEEK_SHORT( p );
 258                 goto Found;
 259               }
 260               p += 2;
 261             }
 262           }
 263         }
 264         break;
 265
 266        /*
 267         *  We don't support format 2 because we haven't seen a single font
 268         *  using it in real life...
 269         */
 270
 271       default:
 272         ;
 273       }
 274
 275       goto NextTable;
 276
 277     Found:
 278       if ( coverage & 8 ) /* override or add */
 279         result = value;
 280       else
 281         result += value;
 282
 283     NextTable:
 284       p = next;
 285     }
 286
 287     return result;
 288   }
 289
 290 #undef TT_KERN_INDEX
 291
 292 /* END */