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