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