diff options
author | Alexei Podtelezhnikov <apodtele@gmail.com> | 2022-11-06 13:12:47 -0500 |
---|---|---|
committer | Alexei Podtelezhnikov <apodtele@gmail.com> | 2022-11-06 13:12:47 -0500 |
commit | 6139f2b647cd7b432da3877714befbbf7515e607 (patch) | |
tree | a33733df7a6ca803500ed63c6cccd3b4c51bc4ea /src/psnames/psmodule.c | |
parent | ae4eb996ab1ed43a52fac19461de3bdcaf1a1742 (diff) | |
download | freetype2-6139f2b647cd7b432da3877714befbbf7515e607.tar.gz |
[bdf, pfr, psnames] Accelarate charmap searches.
The binary searches within charmaps can be accelerated because they
often contain dense continuous blocks of character codes. Within such
blocks, you can predict matches based on misses. This method has been
deployed in `bdf` since 0f122fef34; we only refactor it there. We now
use it in `pfr` and `psnames`, which speeds up the unicode charmap
access by about 50% in PFR and Type 1 fonts.
* src/bdf/bdfdrivr.c (bdf_cmap_char_{index,next}): Refactor.
* src/pfr/pfrcmap.c (pfr_cmap_char_{index,next}): Predict `mid` based
on the mismatch distance.
* src/psnames/psmodule.c (ps_unicodes_char_{index,next}): Ditto.
Diffstat (limited to 'src/psnames/psmodule.c')
-rw-r--r-- | src/psnames/psmodule.c | 31 |
1 files changed, 17 insertions, 14 deletions
diff --git a/src/psnames/psmodule.c b/src/psnames/psmodule.c index e7d51e950..4730d8bf0 100644 --- a/src/psnames/psmodule.c +++ b/src/psnames/psmodule.c @@ -412,21 +412,18 @@ ps_unicodes_char_index( PS_Unicodes table, FT_UInt32 unicode ) { - PS_UniMap *min, *max, *mid, *result = NULL; + PS_UniMap *result = NULL; + PS_UniMap *min = table->maps; + PS_UniMap *max = min + table->num_maps; + PS_UniMap *mid = min + ( ( max - min ) >> 1 ); /* Perform a binary search on the table. */ - - min = table->maps; - max = min + table->num_maps - 1; - - while ( min <= max ) + while ( min < max ) { FT_UInt32 base_glyph; - mid = min + ( ( max - min ) >> 1 ); - if ( mid->unicode == unicode ) { result = mid; @@ -438,13 +435,15 @@ if ( base_glyph == unicode ) result = mid; /* remember match but continue search for base glyph */ - if ( min == max ) - break; - if ( base_glyph < unicode ) min = mid + 1; else - max = mid - 1; + max = mid; + + /* reasonable prediction in a continuous block */ + mid += unicode - base_glyph; + if ( mid >= max || mid < min ) + mid = min + ( ( max - min ) >> 1 ); } if ( result ) @@ -465,14 +464,13 @@ { FT_UInt min = 0; FT_UInt max = table->num_maps; - FT_UInt mid; + FT_UInt mid = min + ( ( max - min ) >> 1 ); PS_UniMap* map; FT_UInt32 base_glyph; while ( min < max ) { - mid = min + ( ( max - min ) >> 1 ); map = table->maps + mid; if ( map->unicode == char_code ) @@ -490,6 +488,11 @@ min = mid + 1; else max = mid; + + /* reasonable prediction in a continuous block */ + mid += char_code - base_glyph; + if ( mid >= max || mid < min ) + mid = min + ( max - min ) / 2; } if ( result ) |