ref: d8776b3439160dad0d02b19dbcd0cccc28045cc5
dir: /src/sfnt/ttkern.c/
/***************************************************************************/
/* */
/* ttkern.c */
/* */
/* Load the basic TrueType kerning table. This doesn't handle */
/* kerning data within the GPOS table at the moment. */
/* */
/* Copyright 1996-2001, 2002, 2003, 2004, 2005 by */
/* David Turner, Robert Wilhelm, and Werner Lemberg. */
/* */
/* This file is part of the FreeType project, and may only be used, */
/* modified, and distributed under the terms of the FreeType project */
/* license, LICENSE.TXT. By continuing to use, modify, or distribute */
/* this file you indicate that you have read the license and */
/* understand and accept it fully. */
/* */
/***************************************************************************/
#include <ft2build.h>
#include FT_INTERNAL_DEBUG_H
#include FT_INTERNAL_STREAM_H
#include FT_TRUETYPE_TAGS_H
#include "ttkern.h"
#include "ttload.h"
#include "sferrors.h"
/*************************************************************************/
/* */
/* The macro FT_COMPONENT is used in trace mode. It is an implicit */
/* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
/* messages during execution. */
/* */
#undef FT_COMPONENT
#define FT_COMPONENT trace_ttkern
#undef TT_KERN_INDEX
#define TT_KERN_INDEX( g1, g2 ) ( ( (FT_ULong)(g1) << 16 ) | (g2) )
#ifdef FT_OPTIMIZE_MEMORY
FT_LOCAL_DEF( FT_Error )
tt_face_load_kern( TT_Face face,
FT_Stream stream )
{
FT_Error error;
FT_ULong table_size;
FT_Byte* p;
FT_Byte* p_limit;
FT_UInt nn, num_tables;
FT_UInt32 avail = 0, ordered = 0;
/* the kern table is optional; exit silently if it is missing */
error = face->goto_table( face, TTAG_kern, stream, &table_size );
if ( error )
goto Exit;
if ( table_size < 4 ) /* the case of a malformed table */
{
FT_ERROR(( "kerning table is too small - ignored\n" ));
error = SFNT_Err_Table_Missing;
goto Exit;
}
if ( FT_FRAME_EXTRACT( table_size, face->kern_table ) )
{
FT_ERROR(( "could not extract kerning table\n" ));
goto Exit;
}
face->kern_table_size = table_size;
p = face->kern_table;
p_limit = p + table_size;
p += 2; /* skip version */
num_tables = FT_NEXT_USHORT( p );
if ( num_tables > 32 ) /* we only support up to 32 sub-tables */
num_tables = 32;
for ( nn = 0; nn < num_tables; nn++ )
{
FT_UInt num_pairs, version, length, coverage;
FT_Byte* p_next;
FT_UInt32 mask = 1UL << nn;
if ( p + 6 > p_limit )
break;
p_next = p;
version = FT_NEXT_USHORT( p );
length = FT_NEXT_USHORT( p );
coverage = FT_NEXT_USHORT( p );
if ( length <= 6 )
break;
p_next += length;
/* only use horizontal kerning tables */
if ( ( coverage & ~8 ) != 0x0001 ||
p + 8 > p_limit )
goto NextTable;
num_pairs = FT_NEXT_USHORT( p );
p += 6;
if ( p + 6 * num_pairs > p_limit )
goto NextTable;
avail |= mask;
/*
* Now check whether the pairs in this table are ordered.
* We then can use binary search.
*/
if ( num_pairs > 0 )
{
FT_UInt count;
FT_UInt old_pair;
old_pair = FT_NEXT_ULONG( p );
p += 2;
for ( count = num_pairs - 1; count > 0; count-- )
{
FT_UInt32 cur_pair;
cur_pair = FT_NEXT_ULONG( p );
if ( cur_pair <= old_pair )
break;
p += 2;
old_pair = cur_pair;
}
if ( count == 0 )
ordered |= mask;
}
NextTable:
p = p_next;
}
face->num_kern_tables = nn;
face->kern_avail_bits = avail;
face->kern_order_bits = ordered;
Exit:
return error;
}
FT_LOCAL_DEF( void )
tt_face_done_kern( TT_Face face )
{
FT_Stream stream = face->root.stream;
FT_FRAME_RELEASE( face->kern_table );
face->kern_table_size = 0;
face->num_kern_tables = 0;
face->kern_avail_bits = 0;
face->kern_order_bits = 0;
}
FT_LOCAL_DEF( FT_Int )
tt_face_get_kerning( TT_Face face,
FT_UInt left_glyph,
FT_UInt right_glyph )
{
FT_Int result = 0;
FT_UInt count, mask = 1;
FT_Byte* p = face->kern_table;
p += 4;
mask = 0x0001;
for ( count = face->num_kern_tables; count > 0; count--, mask <<= 1 )
{
FT_Byte* base = p;
FT_Byte* next = base;
FT_UInt version = FT_NEXT_USHORT( p );
FT_UInt length = FT_NEXT_USHORT( p );
FT_UInt coverage = FT_NEXT_USHORT( p );
FT_Int value = 0;
FT_UNUSED( version );
next = base + length;
if ( ( face->kern_avail_bits & mask ) == 0 )
goto NextTable;
if ( p + 8 > next )
goto NextTable;
switch ( coverage >> 8 )
{
case 0:
{
FT_UInt num_pairs = FT_NEXT_USHORT( p );
FT_ULong key0 = TT_KERN_INDEX( left_glyph, right_glyph );
p += 6;
if ( face->kern_order_bits & mask ) /* binary search */
{
FT_UInt min = 0;
FT_UInt max = num_pairs;
while ( min < max )
{
FT_UInt mid = ( min + max ) >> 1;
FT_Byte* q = p + 6 * mid;
FT_ULong key;
key = FT_NEXT_ULONG( q );
if ( key == key0 )
{
value = FT_PEEK_SHORT( q );
goto Found;
}
if ( key < key0 )
min = mid + 1;
else
max = mid;
}
}
else /* linear search */
{
for ( count = num_pairs; count > 0; count-- )
{
FT_ULong key = FT_NEXT_ULONG( p );
if ( key == key0 )
{
value = FT_PEEK_SHORT( p );
goto Found;
}
p += 2;
}
}
}
break;
/*
* We don't support format 2 because we've never seen a single font
* using it in real life...
*/
default:
;
}
goto NextTable;
Found:
if ( coverage & 8 ) /* overide or add */
result = value;
else
result += value;
NextTable:
p = next;
}
return result;
}
#else /* !OPTIMIZE_MEMORY */
FT_CALLBACK_DEF( int )
tt_kern_pair_compare( const void* a,
const void* b );
FT_LOCAL_DEF( FT_Error )
tt_face_load_kern( TT_Face face,
FT_Stream stream )
{
FT_Error error;
FT_Memory memory = stream->memory;
FT_UInt n, num_tables;
/* the kern table is optional; exit silently if it is missing */
error = face->goto_table( face, TTAG_kern, stream, 0 );
if ( error )
return SFNT_Err_Ok;
if ( FT_FRAME_ENTER( 4L ) )
goto Exit;
(void)FT_GET_USHORT(); /* version */
num_tables = FT_GET_USHORT();
FT_FRAME_EXIT();
for ( n = 0; n < num_tables; n++ )
{
FT_UInt coverage;
FT_UInt length;
if ( FT_FRAME_ENTER( 6L ) )
goto Exit;
(void)FT_GET_USHORT(); /* version */
length = FT_GET_USHORT() - 6; /* substract header length */
coverage = FT_GET_USHORT();
FT_FRAME_EXIT();
if ( coverage == 0x0001 )
{
FT_UInt num_pairs;
TT_Kern0_Pair pair;
TT_Kern0_Pair limit;
/* found a horizontal format 0 kerning table! */
if ( FT_FRAME_ENTER( 8L ) )
goto Exit;
num_pairs = FT_GET_USHORT();
/* skip the rest */
FT_FRAME_EXIT();
/* allocate array of kerning pairs */
if ( FT_QNEW_ARRAY( face->kern_pairs, num_pairs ) ||
FT_FRAME_ENTER( 6L * num_pairs ) )
goto Exit;
pair = face->kern_pairs;
limit = pair + num_pairs;
for ( ; pair < limit; pair++ )
{
pair->left = FT_GET_USHORT();
pair->right = FT_GET_USHORT();
pair->value = FT_GET_USHORT();
}
FT_FRAME_EXIT();
face->num_kern_pairs = num_pairs;
face->kern_table_index = n;
/* ensure that the kerning pair table is sorted (yes, some */
/* fonts have unsorted tables!) */
if ( num_pairs > 0 )
{
TT_Kern0_Pair pair0 = face->kern_pairs;
FT_ULong prev = TT_KERN_INDEX( pair0->left, pair0->right );
for ( pair0++; pair0 < limit; pair0++ )
{
FT_ULong next = TT_KERN_INDEX( pair0->left, pair0->right );
if ( next < prev )
goto SortIt;
prev = next;
}
goto Exit;
SortIt:
ft_qsort( (void*)face->kern_pairs, (int)num_pairs,
sizeof ( TT_Kern0_PairRec ), tt_kern_pair_compare );
}
goto Exit;
}
if ( FT_STREAM_SKIP( length ) )
goto Exit;
}
/* no kern table found -- doesn't matter */
face->kern_table_index = -1;
face->num_kern_pairs = 0;
face->kern_pairs = NULL;
Exit:
return error;
}
FT_CALLBACK_DEF( int )
tt_kern_pair_compare( const void* a,
const void* b )
{
TT_Kern0_Pair pair1 = (TT_Kern0_Pair)a;
TT_Kern0_Pair pair2 = (TT_Kern0_Pair)b;
FT_ULong index1 = TT_KERN_INDEX( pair1->left, pair1->right );
FT_ULong index2 = TT_KERN_INDEX( pair2->left, pair2->right );
return index1 < index2 ? -1
: ( index1 > index2 ? 1
: 0 );
}
FT_LOCAL_DEF( void )
tt_face_done_kern( TT_Face face )
{
FT_Memory memory = face->root.stream->memory;
FT_FREE( face->kern_pairs );
face->num_kern_pairs = 0;
}
FT_LOCAL_DEF( FT_Int )
tt_face_get_kerning( TT_Face face,
FT_UInt left_glyph,
FT_UInt right_glyph )
{
FT_Int result = 0;
TT_Kern0_Pair pair;
if ( face && face->kern_pairs )
{
/* there are some kerning pairs in this font file! */
FT_ULong search_tag = TT_KERN_INDEX( left_glyph, right_glyph );
FT_Long left, right;
left = 0;
right = face->num_kern_pairs - 1;
while ( left <= right )
{
FT_Long middle = left + ( ( right - left ) >> 1 );
FT_ULong cur_pair;
pair = face->kern_pairs + middle;
cur_pair = TT_KERN_INDEX( pair->left, pair->right );
if ( cur_pair == search_tag )
goto Found;
if ( cur_pair < search_tag )
left = middle + 1;
else
right = middle - 1;
}
}
Exit:
return result;
Found:
result = pair->value;
goto Exit;
}
#endif /* !OPTIMIZE_MEMORY */
#undef TT_KERN_INDEX
/* END */