ref: 08b7ad4418df8c81f0822c5f1edb6332cfa046a8
parent: 7504e48eaa5ceb61159d10d0c2ebbb64986c0a3f
author: David Turner <[email protected]>
date: Fri Jun 7 16:07:44 EDT 2002
* include/freetype/cache/ftccache.h, src/cache/ftccache.c,
src/cache/ftccache.i, src/cache/ftcsbits.c: adding various
experimental optimisations to the cache manager
* src/type42/t42parse.c: removing duplicate function
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
2002-06-07 Graham Asher <[email protected]>
+ * include/freetype/cache/ftccache.h, src/cache/ftccache.c,
+ src/cache/ftccache.i, src/cache/ftcsbits.c: adding various
+ experimental optimisations to the cache manager
+
+ * src/type42/t42parse.c: removing duplicate function
+
* src/base/ftobjs.c (FT_Render_Glyph_Internal): changed definition
from FT_EXPORT_DEF to FT_BASE_DEF
--- a/include/freetype/cache/ftccache.h
+++ b/include/freetype/cache/ftccache.h
@@ -20,6 +20,12 @@
#define __FTCCACHE_H__
+/* define to allow cache lookup inlining */
+#undef FTC_CACHE_USE_INLINE
+
+/* define to use linear hash table */
+#undef FTC_CACHE_USE_LINEAR_HASHING
+
FT_BEGIN_HEADER
/* handle to cache object */
@@ -174,8 +180,14 @@
FT_UInt cache_index; /* in manager's table */
FT_Pointer cache_data; /* used by cache node methods */
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+ FT_UFast p;
+ FT_UFast mask;
+ FT_Long slack;
+#else
FT_UFast nodes;
FT_UFast size;
+#endif
FTC_Node* buckets;
FT_LruList_ClassRec family_class;
@@ -289,7 +301,6 @@
FTC_Node *anode );
/* */
-
FT_END_HEADER
--- a/src/cache/ftccache.c
+++ b/src/cache/ftccache.c
@@ -23,7 +23,22 @@
#include "ftcerror.h"
+/* define for level-1 optimisations */
+#undef OPT1
+
+
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
+#define FTC_HASH_MAX_LOAD 2
+#define FTC_HASH_MIN_LOAD 1
+#define FTC_HASH_SUB_LOAD (FTC_HASH_MAX_LOAD-FTC_HASH_MIN_LOAD)
+
+/* this one _must_ be a power of 2 !! */
+#define FTC_HASH_INITIAL_SIZE 8
+
+#endif /* FTC_CACHE_USE_LINEAR_HASHING */
+
/*************************************************************************/
/*************************************************************************/
/***** *****/
@@ -59,11 +74,13 @@
if ( first )
{- node->mru_prev = first->mru_prev;
+ FTC_Node last = first->mru_prev;
+
+ node->mru_prev = last;
node->mru_next = first;
- first->mru_prev->mru_next = node;
- first->mru_prev = node;
+ last->mru_next = node;
+ first->mru_prev = node;
}
else
{@@ -114,13 +131,105 @@
if ( node != first )
{- ftc_node_mru_unlink( node, manager );
- ftc_node_mru_link( node, manager );
+ FTC_Node prev = node->mru_prev;
+ FTC_Node next = node->mru_next;
+ FTC_Node last = first->mru_prev;
+
+ prev->mru_next = next;
+ next->mru_prev = prev;
+
+ node->mru_next = first;
+ node->mru_prev = last;
+ first->mru_prev = node;
+ last->mru_next = node;
+
+ manager->nodes_list = node;
}
}
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
/* remove a node from its cache's hash table */
+ static FT_Error
+ ftc_node_hash_unlink( FTC_Node node,
+ FTC_Cache cache )
+ {+ FT_Error error = 0;
+ FTC_Node *pnode;
+ FT_UInt index, num_buckets;
+
+ index = (FT_UInt)( node->hash & cache->mask );
+ if ( index < cache->p )
+ index = (FT_UInt)( node->hash & (2*cache->mask+1) );
+
+ pnode = cache->buckets + index;
+
+ for (;;)
+ {+ if ( *pnode == NULL )
+ {+ FT_ERROR(( "FreeType.cache.hash_unlink: unknown node!\n" ));
+ return 0;
+ }
+
+ if ( *pnode == node )
+ {+ *pnode = node->link;
+ node->link = NULL;
+ break;
+ }
+
+ pnode = &(*pnode)->link;
+ }
+
+ num_buckets = ( cache->p + cache->mask + 1) ;
+
+ if ( ++ cache->slack > (FT_Long)num_buckets*FTC_HASH_SUB_LOAD )
+ {+ FT_UInt p = cache->p;
+ FT_UInt mask = cache->mask;
+ FT_UInt old_index = p + mask;
+ FTC_Node* pold;
+
+ FT_ASSERT( old_index >= FTC_HASH_INITIAL_SIZE );
+
+ if ( p == 0 )
+ {+ FT_Memory memory = cache->memory;
+
+
+ cache->mask >>= 1;
+ p = cache->mask;
+
+ if ( FT_RENEW_ARRAY( cache->buckets, (mask+1)*2, (mask) ) )
+ {+ FT_ERROR(( "FreeType.cache.hash_unlink: couldn't shunk buckets !\n" ));
+ goto Exit;
+ }
+ }
+ else
+ p--;
+
+ pnode = cache->buckets + p;
+ while ( *pnode )
+ pnode = &(*pnode)->link;
+
+ pold = cache->buckets + old_index;
+ *pnode = *pold;
+ *pold = NULL;
+
+ cache->slack -= FTC_HASH_MAX_LOAD;
+ cache->p = p;
+ }
+
+ Exit:
+ return error;
+ }
+
+#else /* !FTC_CACHE_USE_LINEAR_HASHING */
+
+ /* remove a node from its cache's hash table */
static void
ftc_node_hash_unlink( FTC_Node node,
FTC_Cache cache )
@@ -127,7 +236,6 @@
{FTC_Node *pnode = cache->buckets + ( node->hash % cache->size );
-
for (;;)
{if ( *pnode == NULL )
@@ -149,8 +257,83 @@
}
}
+#endif /* !FTC_CACHE_USE_LINEAR_HASHING */
+
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
/* add a node to the "top" of its cache's hash table */
+ static FT_Error
+ ftc_node_hash_link( FTC_Node node,
+ FTC_Cache cache )
+ {+ FTC_Node *pnode;
+ FT_UInt index;
+ FT_Error error = 0;
+
+ index = (FT_UInt)( node->hash & cache->mask );
+ if ( index < cache->p )
+ index = (FT_UInt)( node->hash & (2*cache->mask+1) );
+
+ pnode = cache->buckets + index;
+
+ node->link = *pnode;
+ *pnode = node;
+
+ if ( --cache->slack < 0 )
+ {+ FT_UInt p = cache->p;
+ FT_UInt mask = cache->mask;
+ FTC_Node new_list;
+
+ /* split a single bucket */
+ new_list = NULL;
+ pnode = cache->buckets + p;
+ for (;;)
+ {+ node = *pnode;
+ if ( node == NULL )
+ break;
+
+ if ( node->hash & (mask+1) )
+ {+ *pnode = node->link;
+ node->link = new_list;
+ new_list = node;
+ }
+ else
+ pnode = &node->link;
+ }
+
+ cache->buckets[ p + mask + 1 ] = new_list;
+
+ cache->slack += FTC_HASH_MAX_LOAD;
+
+ if ( p >= mask )
+ {+ FT_Memory memory = cache->memory;
+
+
+ if ( FT_RENEW_ARRAY( cache->buckets, (mask+1)*2, (mask+1)*4 ) )
+ {+ FT_ERROR(( "FreeType.cache.hash_unlink: couldn't expand buckets !\n" ));
+ goto Exit;
+ }
+
+ cache->mask = 2*mask + 1;
+ cache->p = 0;
+ }
+ else
+ cache->p = p + 1;
+ }
+
+ Exit:
+ return error;
+ }
+
+#else /* !FTC_CACHE_USE_LINEAR_HASHING */
+
+ /* add a node to the "top" of its cache's hash table */
static void
ftc_node_hash_link( FTC_Node node,
FTC_Cache cache )
@@ -157,7 +340,6 @@
{FTC_Node *pnode = cache->buckets + ( node->hash % cache->size );
-
node->link = *pnode;
*pnode = node;
@@ -164,7 +346,10 @@
cache->nodes++;
}
+#endif /* !FTC_CACHE_USE_LINEAR_HASHING */
+
+
/* remove a node from the cache manager */
FT_EXPORT_DEF( void )
ftc_node_destroy( FTC_Node node,
@@ -276,6 +461,11 @@
/*************************************************************************/
/*************************************************************************/
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
+
+#else /* !FTC_CACHE_USE_LINEAR_HASHING */
+
#define FTC_PRIMES_MIN 7
#define FTC_PRIMES_MAX 13845163
@@ -388,6 +578,7 @@
}
}
+#endif /* !FTC_CACHE_USE_LINEAR_HASHING */
FT_EXPORT_DEF( FT_Error )
ftc_cache_init( FTC_Cache cache )
@@ -397,6 +588,16 @@
FT_Error error;
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+
+ cache->p = 0;
+ cache->mask = FTC_HASH_INITIAL_SIZE-1;
+ cache->slack = FTC_HASH_INITIAL_SIZE*FTC_HASH_MAX_LOAD;
+
+ if ( FT_NEW_ARRAY( cache->buckets, FTC_HASH_INITIAL_SIZE*2 ) )
+ goto Exit;
+
+#else /* !FTC_CACHE_USE_LINEAR_HASHING */
cache->nodes = 0;
cache->size = FTC_PRIMES_MIN;
@@ -403,6 +604,8 @@
if ( FT_NEW_ARRAY( cache->buckets, cache->size ) )
goto Exit;
+#endif /* !FTC_CACHE_USE_LINEAR_HASHING */
+
/* now, initialize the lru list of families for this cache */
if ( clazz->family_size > 0 )
{@@ -442,9 +645,15 @@
FTC_Cache_Class clazz = cache->clazz;
FTC_Manager manager = cache->manager;
FT_UFast i;
+ FT_UInt count;
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+ count = cache->p + cache->mask + 1;
+#else
+ count = cache->size;
+#endif
- for ( i = 0; i < cache->size; i++ )
+ for ( i = 0; i < count; i++ )
{FTC_Node *pnode = cache->buckets + i, next, node = *pnode;
@@ -469,8 +678,11 @@
cache->buckets[i] = NULL;
}
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+ cache->p = 0;
+#else
cache->nodes = 0;
-
+#endif
/* destroy the families */
if ( cache->families )
FT_LruList_Reset( cache->families );
@@ -489,7 +701,12 @@
ftc_cache_clear( cache );
FT_FREE( cache->buckets );
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+ cache->mask = 0;
+ cache->slack = 0;
+#else
cache->size = 0;
+#endif
if ( cache->families )
{@@ -508,7 +725,7 @@
FTC_Query query,
FTC_Node *anode )
{- FT_Error error;
+ FT_Error error = 0;
FT_LruNode lru;
@@ -520,14 +737,69 @@
query->hash = 0;
query->family = NULL;
+#ifdef OPT1
+ {+ /* first of all, find the relevant family */
+ FT_LruList list = cache->families;
+ FT_LruNode fam, *pfam;
+ FT_LruNode_CompareFunc compare = list->clazz->node_compare;
+
+ pfam = &list->nodes;
+ for (;;)
+ {+ fam = *pfam;
+ if ( fam == NULL )
+ {+ error = FT_LruList_Lookup( list, query, &lru );
+ if ( error )
+ goto Exit;
+
+ goto Skip;
+ }
+
+ if ( compare( fam, query, list->data ) )
+ break;
+
+ pfam = &fam->next;
+ }
+
+ FT_ASSERT( fam != NULL );
+
+ /* move to top of list when needed */
+ if ( fam != list->nodes )
+ {+ *pfam = fam->next;
+ fam->next = list->nodes;
+ list->nodes = fam;
+ }
+
+ lru = fam;
+
+ Skip:
+ }
+#else
error = FT_LruList_Lookup( cache->families, query, &lru );
if ( !error )
+#endif
{FTC_Family family = (FTC_Family) lru;
FT_UFast hash = query->hash;
- FTC_Node* bucket = cache->buckets + (hash % cache->size);
+ FTC_Node* bucket;
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+ FT_UInt index;
+
+ index = hash & cache->mask;
+ if ( index < cache->p )
+ index = hash & (cache->mask*2+1);
+
+ bucket = cache->buckets + index;
+#else
+ bucket = cache->buckets + (hash % cache->size);
+#endif
+
+
if ( query->family != family ||
family->fam_index >= cache->manager->families.size )
{@@ -551,8 +823,14 @@
if ( node == NULL )
break;
+#ifdef OPT1
+ if ( node->hash == hash &&
+ (FT_UInt)node->fam_index == family->fam_index &&
+ compare( node, query, cache ) )
+#else
if ( (FT_UInt)node->fam_index == family->fam_index &&
compare( node, query, cache ) )
+#endif
{/* move to head of bucket list */
if ( pnode != bucket )
@@ -596,7 +874,18 @@
goto Exit;
}
+#ifdef FTC_CACHE_USE_LINEAR_HASHING
+ error = ftc_node_hash_link( node, cache );
+ if ( error )
+ {+ clazz->node_done( node, cache );
+ FT_FREE( node );
+ goto Exit;
+ }
+#else
ftc_node_hash_link( node, cache );
+#endif
+
ftc_node_mru_link( node, cache->manager );
cache->manager->cur_weight += clazz->node_weight( node, cache );
@@ -609,9 +898,11 @@
node->ref_count--;
}
+#ifndef FTC_CACHE_USE_LINEAR_HASHING
/* try to resize the hash table if appropriate */
if ( FTC_CACHE_RESIZE_TEST( cache ) )
ftc_cache_resize( cache );
+#endif
*anode = node;
}
--- a/src/cache/ftcsbits.c
+++ b/src/cache/ftcsbits.c
@@ -63,8 +63,8 @@
FTC_ImageDesc desc;
} FTC_SBitFamilyRec;
-
-
+
+
#define FTC_SBIT_FAMILY( x ) ( (FTC_SBitFamily)( x ) )
#define FTC_SBIT_FAMILY_MEMORY( x ) FTC_GLYPH_FAMILY_MEMORY( &( x )->cset )
@@ -462,6 +462,23 @@
/* documentation is in ftcsbits.h */
+#ifdef FTC_CACHE_USE_INLINE
+
+# define GEN_CACHE_FAMILY_COMPARE(f,q,c) \
+ ftc_sbit_family_compare( (FTC_SBitFamily)(f), (FTC_SBitQuery)(q) )
+
+# define GEN_CACHE_NODE_COMPARE(n,q,c) \
+ ftc_sbit_node_compare( (FTC_SBitNode)(n), (FTC_SBitQuery)(q), c )
+
+# define GEN_CACHE_LOOKUP ftc_sbit_cache_lookup
+# include "ftccache.i"
+
+#else /* !FTC_CACHE_USE_INLINE */
+
+# define ftc_sbit_cache_lookup ftc_cache_lookup
+
+#endif /* !FTC_CACHE_USE_INLINE */
+
FT_EXPORT_DEF( FT_Error )
FTC_SBitCache_Lookup( FTC_SBitCache cache,
FTC_ImageDesc* desc,
@@ -486,9 +503,9 @@
squery.gquery.gindex = gindex;
squery.desc = *desc;
- error = ftc_cache_lookup( FTC_CACHE( cache ),
- FTC_QUERY( &squery ),
- (FTC_Node*)&node );
+ error = ftc_sbit_cache_lookup( FTC_CACHE( cache ),
+ FTC_QUERY( &squery ),
+ (FTC_Node*)&node );
if ( !error )
{*ansbit = node->sbits + ( gindex - FTC_GLYPH_NODE( node )->item_start );
@@ -520,11 +537,11 @@
FTC_SBit *ansbit )
{FTC_ImageDesc desc0;
-
+
if ( !desc )
return FTC_Err_Invalid_Argument;
-
+
desc0.font = desc->font;
desc0.type = (FT_UInt32)desc->image_type;
--- a/src/type42/t42parse.c
+++ b/src/type42/t42parse.c
@@ -970,114 +970,3 @@
}
- FT_LOCAL_DEF( FT_Error )
- T42_Open_Face( T42_Face face )
- {- T42_LoaderRec loader;
- T42_Parser parser;
- T1_Font type1 = &face->type1;
- FT_Memory memory = face->root.memory;
- FT_Error error;
-
- PSAux_Service psaux = (PSAux_Service)face->psaux;
-
-
- t42_loader_init( &loader, face );
-
- parser = &loader.parser;
-
- if ( FT_ALLOC( face->ttf_data, 12 ) )
- goto Exit;
-
- error = t42_parser_init( parser,
- face->root.stream,
- memory,
- psaux);
- if ( error )
- goto Exit;
-
- error = t42_parse_dict( face, &loader, parser->base_dict, parser->base_len );
-
- if ( type1->font_type != 42 )
- {- error = FT_Err_Unknown_File_Format;
- goto Exit;
- }
-
- /* now, propagate the charstrings and glyphnames tables */
- /* to the Type1 data */
- type1->num_glyphs = loader.num_glyphs;
-
- if ( !loader.charstrings.init ) {- FT_ERROR(( "T42_Open_Face: no charstrings array in face!\n" ));
- error = FT_Err_Invalid_File_Format;
- }
-
- loader.charstrings.init = 0;
- type1->charstrings_block = loader.charstrings.block;
- type1->charstrings = loader.charstrings.elements;
- type1->charstrings_len = loader.charstrings.lengths;
-
- /* we copy the glyph names `block' and `elements' fields; */
- /* the `lengths' field must be released later */
- type1->glyph_names_block = loader.glyph_names.block;
- type1->glyph_names = (FT_String**)loader.glyph_names.elements;
- loader.glyph_names.block = 0;
- loader.glyph_names.elements = 0;
-
- /* we must now build type1.encoding when we have a custom array */
- if ( type1->encoding_type == T1_ENCODING_TYPE_ARRAY )
- {- FT_Int charcode, idx, min_char, max_char;
- FT_Byte* char_name;
- FT_Byte* glyph_name;
-
-
- /* OK, we do the following: for each element in the encoding */
- /* table, look up the index of the glyph having the same name */
- /* as defined in the CharStrings array. */
- /* The index is then stored in type1.encoding.char_index, and */
- /* the name in type1.encoding.char_name */
-
- min_char = +32000;
- max_char = -32000;
-
- charcode = 0;
- for ( ; charcode < loader.encoding_table.max_elems; charcode++ )
- {- type1->encoding.char_index[charcode] = 0;
- type1->encoding.char_name [charcode] = (char *)".notdef";
-
- char_name = loader.encoding_table.elements[charcode];
- if ( char_name )
- for ( idx = 0; idx < type1->num_glyphs; idx++ )
- {- glyph_name = (FT_Byte*)type1->glyph_names[idx];
- if ( ft_strcmp( (const char*)char_name,
- (const char*)glyph_name ) == 0 )
- {- type1->encoding.char_index[charcode] = (FT_UShort)idx;
- type1->encoding.char_name [charcode] = (char*)glyph_name;
-
- /* Change min/max encoded char only if glyph name is */
- /* not /.notdef */
- if ( ft_strcmp( (const char*)".notdef",
- (const char*)glyph_name ) != 0 )
- {- if ( charcode < min_char ) min_char = charcode;
- if ( charcode > max_char ) max_char = charcode;
- }
- break;
- }
- }
- }
- type1->encoding.code_first = min_char;
- type1->encoding.code_last = max_char;
- type1->encoding.num_chars = loader.num_chars;
- }
-
- Exit:
- t42_loader_done( &loader );
- return error;
- }
-