source: trunk/poppler/freetype-2.1.10/src/sfnt/ttkern.c @ 2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 15 years ago

First import

File size: 11.7 KB
Line 
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 */
Note: See TracBrowser for help on using the repository browser.