[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[freetype2] hdmx-advances 2d2b903: [truetype] Binary search through `hdm
From: |
Werner Lemberg |
Subject: |
[freetype2] hdmx-advances 2d2b903: [truetype] Binary search through `hdmx` records. |
Date: |
Sat, 27 Nov 2021 22:47:14 -0500 (EST) |
branch: hdmx-advances
commit 2d2b9033765f3d879badedad8ea17933fc0c00e0
Author: Alexei Podtelezhnikov <apodtele@gmail.com>
Commit: Alexei Podtelezhnikov <apodtele@gmail.com>
[truetype] Binary search through `hdmx` records.
The `hdmx` table is supposed to be sorted by ppem size, which
enables binary search. We also drop the check for the sufficient
length of the record because it is now enforced when the table
is loaded.
* src/truetype/ttpload.c (tt_face_get_device_metrics): Implement
binary search to retrieve advances.
---
src/truetype/ttpload.c | 27 ++++++++++++++++++---------
1 file changed, 18 insertions(+), 9 deletions(-)
diff --git a/src/truetype/ttpload.c b/src/truetype/ttpload.c
index 71db75a..c4a966d 100644
--- a/src/truetype/ttpload.c
+++ b/src/truetype/ttpload.c
@@ -577,8 +577,8 @@
if ( FT_QNEW_ARRAY( face->hdmx_record_sizes, num_records ) )
goto Fail;
- /* XXX: We do not check if the records are sorted by ppem */
- /* and cannot use binary search later. */
+ /* XXX: We do not check if the records are sorted by ppem but */
+ /* we use binary search later, which would not work otherwise. */
for ( nn = 0; nn < num_records; nn++ )
{
if ( p + record_size > limit )
@@ -619,27 +619,36 @@
/**************************************************************************
*
* Return the advance width table for a given pixel size if it is found
- * in the font's `hdmx' table (if any).
+ * in the font's `hdmx' table (if any). The records must be sorted for
+ * the biniry search to work properly.
*/
FT_LOCAL_DEF( FT_Byte* )
tt_face_get_device_metrics( TT_Face face,
FT_UInt ppem,
FT_UInt gindex )
{
- FT_UInt nn;
+ FT_UInt min = 0;
+ FT_UInt max = face->hdmx_record_count - 1;
+ FT_UInt mid;
FT_Byte* result = NULL;
FT_ULong record_size = face->hdmx_record_size;
FT_Byte* record = FT_OFFSET( face->hdmx_table, 8 );
- for ( nn = 0; nn < face->hdmx_record_count; nn++ )
- if ( face->hdmx_record_sizes[nn] == ppem )
+ do
+ {
+ mid = ( min + max ) >> 1;
+
+ if ( face->hdmx_record_sizes[mid] > ppem )
+ max = mid - 1;
+ else if ( face->hdmx_record_sizes[mid] < ppem )
+ min = mid + 1;
+ else
{
- gindex += 2;
- if ( gindex < record_size )
- result = record + nn * record_size + gindex;
+ result = record + mid * record_size + gindex + 2;
break;
}
+ } while ( max >= min );
return result;
}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [freetype2] hdmx-advances 2d2b903: [truetype] Binary search through `hdmx` records.,
Werner Lemberg <=