[freetype2] hdmx-advances 7ee90a6 5/5: [truetype] Binary search through `hdmx` records.

[Werner Lemberg]

branch: hdmx-advances
commit 7ee90a6f70ff19bcf4c373bc2876aa2d6b7dd065
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.
    
    * 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.
---
 include/freetype/internal/tttypes.h |  6 ++---
 src/truetype/ttpload.c              | 48 ++++++++++++++++++++++++-------------
 2 files changed, 35 insertions(+), 19 deletions(-)

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..fe01618 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_UInt   min         = 0;
+    FT_UInt   max         = face->hdmx_record_count;
+    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 )
+    while ( min < max )
+    {
+      mid = ( min + max ) >> 1;
+
+      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;
   }