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 */
318