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-2018 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 = FT_THROW( 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, format;
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 + 8 )
103        break;
104
105      p_next += length;
106
107      if ( p_next > p_limit )  /* handle broken table */
108        p_next = p_limit;
109
110      format = coverage >> 8;
111
112      /* we currently only support format 0 kerning tables */
113      if ( format != 0 )
114        goto NextTable;
115
116      /* only use horizontal kerning tables */
117      if ( ( coverage & 3U ) != 0x0001 ||
118           p + 8 > p_next              )
119        goto NextTable;
120
121      num_pairs = FT_NEXT_USHORT( p );
122      p        += 6;
123
124      if ( ( p_next - p ) < 6 * (int)num_pairs ) /* handle broken count */
125        num_pairs = (FT_UInt)( ( p_next - p ) / 6 );
126
127      avail |= mask;
128
129      /*
130       *  Now check whether the pairs in this table are ordered.
131       *  We then can use binary search.
132       */
133      if ( num_pairs > 0 )
134      {
135        FT_ULong  count;
136        FT_ULong  old_pair;
137
138
139        old_pair = FT_NEXT_ULONG( p );
140        p       += 2;
141
142        for ( count = num_pairs - 1; count > 0; count-- )
143        {
144          FT_UInt32  cur_pair;
145
146
147          cur_pair = FT_NEXT_ULONG( p );
148          if ( cur_pair <= old_pair )
149            break;
150
151          p += 2;
152          old_pair = cur_pair;
153        }
154
155        if ( count == 0 )
156          ordered |= mask;
157      }
158
159    NextTable:
160      p = p_next;
161    }
162
163    face->num_kern_tables = nn;
164    face->kern_avail_bits = avail;
165    face->kern_order_bits = ordered;
166
167  Exit:
168    return error;
169  }
170
171
172  FT_LOCAL_DEF( void )
173  tt_face_done_kern( TT_Face  face )
174  {
175    FT_Stream  stream = face->root.stream;
176
177
178    FT_FRAME_RELEASE( face->kern_table );
179    face->kern_table_size = 0;
180    face->num_kern_tables = 0;
181    face->kern_avail_bits = 0;
182    face->kern_order_bits = 0;
183  }
184
185
186  FT_LOCAL_DEF( FT_Int )
187  tt_face_get_kerning( TT_Face  face,
188                       FT_UInt  left_glyph,
189                       FT_UInt  right_glyph )
190  {
191    FT_Int    result = 0;
192    FT_UInt   count, mask;
193    FT_Byte*  p       = face->kern_table;
194    FT_Byte*  p_limit = p + face->kern_table_size;
195
196
197    p   += 4;
198    mask = 0x0001;
199
200    for ( count = face->num_kern_tables;
201          count > 0 && p + 6 <= p_limit;
202          count--, mask <<= 1 )
203    {
204      FT_Byte* base     = p;
205      FT_Byte* next;
206      FT_UInt  version  = FT_NEXT_USHORT( p );
207      FT_UInt  length   = FT_NEXT_USHORT( p );
208      FT_UInt  coverage = FT_NEXT_USHORT( p );
209      FT_UInt  num_pairs;
210      FT_Int   value    = 0;
211
212      FT_UNUSED( version );
213
214
215      next = base + length;
216
217      if ( next > p_limit )  /* handle broken table */
218        next = p_limit;
219
220      if ( ( face->kern_avail_bits & mask ) == 0 )
221        goto NextTable;
222
223      FT_ASSERT( p + 8 <= next ); /* tested in tt_face_load_kern */
224
225      num_pairs = FT_NEXT_USHORT( p );
226      p        += 6;
227
228      if ( ( next - p ) < 6 * (int)num_pairs )  /* handle broken count  */
229        num_pairs = (FT_UInt)( ( next - p ) / 6 );
230
231      switch ( coverage >> 8 )
232      {
233      case 0:
234        {
235          FT_ULong  key0 = TT_KERN_INDEX( left_glyph, right_glyph );
236
237
238          if ( face->kern_order_bits & mask )   /* binary search */
239          {
240            FT_UInt   min = 0;
241            FT_UInt   max = num_pairs;
242
243
244            while ( min < max )
245            {
246              FT_UInt   mid = ( min + max ) >> 1;
247              FT_Byte*  q   = p + 6 * mid;
248              FT_ULong  key;
249
250
251              key = FT_NEXT_ULONG( q );
252
253              if ( key == key0 )
254              {
255                value = FT_PEEK_SHORT( q );
256                goto Found;
257              }
258              if ( key < key0 )
259                min = mid + 1;
260              else
261                max = mid;
262            }
263          }
264          else /* linear search */
265          {
266            FT_UInt  count2;
267
268
269            for ( count2 = num_pairs; count2 > 0; count2-- )
270            {
271              FT_ULong  key = FT_NEXT_ULONG( p );
272
273
274              if ( key == key0 )
275              {
276                value = FT_PEEK_SHORT( p );
277                goto Found;
278              }
279              p += 2;
280            }
281          }
282        }
283        break;
284
285       /*
286        *  We don't support format 2 because we haven't seen a single font
287        *  using it in real life...
288        */
289
290      default:
291        ;
292      }
293
294      goto NextTable;
295
296    Found:
297      if ( coverage & 8 ) /* override or add */
298        result = value;
299      else
300        result += value;
301
302    NextTable:
303      p = next;
304    }
305
306    return result;
307  }
308
309#undef TT_KERN_INDEX
310
311/* END */
312