Commit 7add5b2bcb2794b8f9dacdcd2e732835140adefd
2021-12-11T22:54:06
[truetype] Binary search through the `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. * include/freetype/internal/tttypes.h (TT_FaceRec): Store the `hdmx` record pointers sorted by ppem instead of ppem's themselves. * src/truetype/ttpload.c (tt_face_load_hdmx): Prudently sort records. (tt_face_get_device_metrics): Implement binary search to retrieve advances.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
diff --git a/include/freetype/internal/tttypes.h b/include/freetype/internal/tttypes.h
index fcd97cf..286f14f 100644
--- a/include/freetype/internal/tttypes.h
+++ b/include/freetype/internal/tttypes.h
@@ -1390,8 +1390,8 @@ FT_BEGIN_HEADER
* hdmx_record_size ::
* The size of a single hdmx record.
*
- * hdmx_record_sizes ::
- * An array holding the ppem sizes available in the 'hdmx' table.
+ * hdmx_records ::
+ * A array of pointers to the 'hdmx' table records sorted by ppem.
*
* sbit_table ::
* A pointer to the font's embedded bitmap location table.
@@ -1605,7 +1605,7 @@ FT_BEGIN_HEADER
FT_ULong hdmx_table_size;
FT_UInt hdmx_record_count;
FT_ULong hdmx_record_size;
- FT_Byte* hdmx_record_sizes;
+ FT_Byte** hdmx_records;
FT_Byte* sbit_table;
FT_ULong sbit_table_size;
diff --git a/src/truetype/ttpload.c b/src/truetype/ttpload.c
index 71db75a..3c9b00a 100644
--- a/src/truetype/ttpload.c
+++ b/src/truetype/ttpload.c
@@ -498,6 +498,14 @@
}
+ FT_COMPARE_DEF( int )
+ compare_ppem( const void* a,
+ const void* b )
+ {
+ return **(FT_Byte**)a - **(FT_Byte**)b;
+ }
+
+
/**************************************************************************
*
* @Function:
@@ -574,20 +582,21 @@
goto Fail;
}
- if ( FT_QNEW_ARRAY( face->hdmx_record_sizes, num_records ) )
+ if ( FT_QNEW_ARRAY( face->hdmx_records, num_records ) )
goto Fail;
- /* XXX: We do not check if the records are sorted by ppem */
- /* and cannot use binary search later. */
for ( nn = 0; nn < num_records; nn++ )
{
if ( p + record_size > limit )
break;
-
- face->hdmx_record_sizes[nn] = p[0];
- p += record_size;
+ face->hdmx_records[nn] = p;
+ p += record_size;
}
+ /* The records must be already sorted by ppem but it does not */
+ /* hurt to make sure so that the binary search works later. */
+ ft_qsort( face->hdmx_records, nn, sizeof ( FT_Byte* ), compare_ppem );
+
face->hdmx_record_count = nn;
face->hdmx_table_size = table_size;
face->hdmx_record_size = record_size;
@@ -611,7 +620,7 @@
FT_Memory memory = stream->memory;
- FT_FREE( face->hdmx_record_sizes );
+ FT_FREE( face->hdmx_records );
FT_FRAME_RELEASE( face->hdmx_table );
}
@@ -619,27 +628,34 @@
/**************************************************************************
*
* 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 binary 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_Byte* result = NULL;
- FT_ULong record_size = face->hdmx_record_size;
- FT_Byte* record = FT_OFFSET( face->hdmx_table, 8 );
+ FT_UInt min = 0;
+ FT_UInt max = face->hdmx_record_count;
+ FT_UInt mid;
+ FT_Byte* result = NULL;
+
+ while ( min < max )
+ {
+ mid = ( min + max ) >> 1;
- for ( nn = 0; nn < face->hdmx_record_count; nn++ )
- if ( face->hdmx_record_sizes[nn] == ppem )
+ if ( face->hdmx_records[mid][0] > ppem )
+ max = mid;
+ else if ( face->hdmx_records[mid][0] < ppem )
+ min = mid + 1;
+ else
{
- gindex += 2;
- if ( gindex < record_size )
- result = record + nn * record_size + gindex;
+ result = face->hdmx_records[mid] + 2 + gindex;
break;
}
+ }
return result;
}