[freetype2] hdmx-advances 2d2b903: [truetype] Binary search through `hdmx` records.

[Werner Lemberg]

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;
   }