[pcf] Replace charmap implementation.

PCF comes with charmap lookup table, aka PCF encodings.  Using it
directly makes FT_Get_Char_Index and FT_Get_Next_Char 4-5 times
faster than the original BDF-like binary searches.

* src/pcf/pcf.h (PCF_EncodingRec): Removed.
(PCF_FaceRec): Remove `nencodings' and `encodings'.
* src/pcf/pcfdrivr.c (pcf_cmap_char_{index,next}): Replaced.
* src/pcf/pcfread.c (pcf_get_encodings): Store data differently.

4 files changed, 87 insertions, 120 deletions

diff --git a/ChangeLog b/ChangeLog
index ecf6d9d45..38c792a95 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2018-09-20  Alexei Podtelezhnikov  <apodtele@gmail.com>
+
+	[pcf] Replace charmap implementation.
+
+	PCF comes with charmap lookup table, aka PCF encodings.  Using it
+	directly makes FT_Get_Char_Index and FT_Get_Next_Char 4-5 times
+	faster than the original BDF-like binary searches.
+
+	* src/pcf/pcf.h (PCF_EncodingRec): Removed.
+	(PCF_FaceRec): Remove `nencodings' and `encodings'.
+	* src/pcf/pcfdrivr.c (pcf_cmap_char_{index,next}): Replaced.
+	* src/pcf/pcfread.c (pcf_get_encodings): Store data differently.
+
 2018-09-20  Werner Lemberg  <wl@gnu.org>
 
 	[base] Remove unused function `FT_GlyphLoader_CopyPoints'.
@@ -9,7 +22,7 @@
 
 	[pcf] Prepare to replace charmap implementation.
 
-	* src/pcf/pcf.h (PCF_Face): Updated to include...
+	* src/pcf/pcf.h (PCF_FaceRec): Updated to include...
 	(PCF_EncRec): ... this new structure to store charmap geometry.
 
 	* src/pcf/pcfread.c (pcf_get_encodings): Store charmap geometry.
diff --git a/src/pcf/pcf.h b/src/pcf/pcf.h
index 8b94782c2..529dd3adf 100644
--- a/src/pcf/pcf.h
+++ b/src/pcf/pcf.h
@@ -112,7 +112,7 @@ FT_BEGIN_HEADER
     FT_UShort   lastRow;
     FT_UShort   defaultChar;
 
-    FT_UShort*  offset;  /* unused yet */
+    FT_UShort*  offset;
 
   } PCF_EncRec, *PCF_Enc;
 
@@ -141,38 +141,28 @@ FT_BEGIN_HEADER
    * This file uses X11 terminology for PCF data; an `encoding' in X11 speak
    * is the same as a `character code' in FreeType speak.
    */
-  typedef struct  PCF_EncodingRec_
-  {
-    FT_ULong   enc;
-    FT_UShort  glyph;  /* an index into PCF_Face's `metrics' array */
-
-  } PCF_EncodingRec, *PCF_Encoding;
-
-
   typedef struct  PCF_FaceRec_
   {
-    FT_FaceRec     root;
+    FT_FaceRec    root;
 
-    FT_StreamRec   comp_stream;
-    FT_Stream      comp_source;
+    FT_StreamRec  comp_stream;
+    FT_Stream     comp_source;
 
-    char*          charset_encoding;
-    char*          charset_registry;
+    char*         charset_encoding;
+    char*         charset_registry;
 
-    PCF_TocRec     toc;
-    PCF_AccelRec   accel;
+    PCF_TocRec    toc;
+    PCF_AccelRec  accel;
 
-    int            nprops;
-    PCF_Property   properties;
+    int           nprops;
+    PCF_Property  properties;
 
-    FT_ULong       nmetrics;
-    PCF_Metric     metrics;
-    FT_ULong       nencodings;
-    PCF_Encoding   encodings;
+    FT_ULong      nmetrics;
+    PCF_Metric    metrics;
 
-    PCF_EncRec     enc;
+    PCF_EncRec    enc;
 
-    FT_ULong       bitmapsFormat;
+    FT_ULong      bitmapsFormat;
 
   } PCF_FaceRec, *PCF_Face;
 
diff --git a/src/pcf/pcfdrivr.c b/src/pcf/pcfdrivr.c
index 33d83d397..54bbb9d11 100644
--- a/src/pcf/pcfdrivr.c
+++ b/src/pcf/pcfdrivr.c
@@ -69,9 +69,8 @@ THE SOFTWARE.
    */
   typedef struct  PCF_CMapRec_
   {
-    FT_CMapRec    root;
-    FT_ULong      num_encodings;
-    PCF_Encoding  encodings;
+    FT_CMapRec  root;
+    PCF_Enc     enc;
 
   } PCF_CMapRec, *PCF_CMap;
 
@@ -86,8 +85,7 @@ THE SOFTWARE.
     FT_UNUSED( init_data );
 
 
-    cmap->num_encodings = face->nencodings;
-    cmap->encodings     = face->encodings;
+    cmap->enc = &face->enc;
 
     return FT_Err_Ok;
   }
@@ -99,8 +97,7 @@ THE SOFTWARE.
     PCF_CMap  cmap = (PCF_CMap)pcfcmap;
 
 
-    cmap->encodings     = NULL;
-    cmap->num_encodings = 0;
+    cmap->enc = NULL;
   }
 
 
@@ -108,36 +105,26 @@ THE SOFTWARE.
   pcf_cmap_char_index( FT_CMap    pcfcmap,  /* PCF_CMap */
                        FT_UInt32  charcode )
   {
-    PCF_CMap      cmap      = (PCF_CMap)pcfcmap;
-    PCF_Encoding  encodings = cmap->encodings;
-    FT_ULong      min, max, mid;
-    FT_UInt       result    = 0;
+    PCF_CMap   cmap = (PCF_CMap)pcfcmap;
+    PCF_Enc    enc  = cmap->enc;
+    FT_UShort  charcodeRow;
+    FT_UShort  charcodeCol;
 
 
-    min = 0;
-    max = cmap->num_encodings;
+    if ( charcode > (FT_UInt32)( enc->lastRow  * 256 + enc->lastCol  ) ||
+         charcode < (FT_UInt32)( enc->firstRow * 256 + enc->firstCol ) )
+      return 0;
 
-    while ( min < max )
-    {
-      FT_ULong  code;
-
-
-      mid  = ( min + max ) >> 1;
-      code = encodings[mid].enc;
-
-      if ( charcode == code )
-      {
-        result = encodings[mid].glyph;
-        break;
-      }
+    charcodeRow = (FT_UShort)( charcode >> 8 );
+    charcodeCol = (FT_UShort)( charcode & 0xFF );
 
-      if ( charcode < code )
-        max = mid;
-      else
-        min = mid + 1;
-    }
+    if ( charcodeCol < enc->firstCol ||
+         charcodeCol > enc->lastCol  )
+      return 0;
 
-    return result;
+    return (FT_UInt)enc->offset[ ( charcodeRow - enc->firstRow ) *
+                                 ( enc->lastCol - enc->firstCol + 1 ) +
+                                   charcodeCol - enc->firstCol          ];
   }
 
 
@@ -145,52 +132,42 @@ THE SOFTWARE.
   pcf_cmap_char_next( FT_CMap    pcfcmap,   /* PCF_CMap */
                       FT_UInt32  *acharcode )
   {
-    PCF_CMap      cmap      = (PCF_CMap)pcfcmap;
-    PCF_Encoding  encodings = cmap->encodings;
-    FT_ULong      min, max, mid;
-    FT_ULong      charcode  = *acharcode + 1;
-    FT_UInt       result    = 0;
+    PCF_CMap   cmap      = (PCF_CMap)pcfcmap;
+    PCF_Enc    enc       = cmap->enc;
+    FT_UInt32  charcode  = *acharcode;
+    FT_UShort  charcodeRow;
+    FT_UShort  charcodeCol;
+    FT_Int     result = 0;
 
 
-    min = 0;
-    max = cmap->num_encodings;
-
-    while ( min < max )
+    while ( charcode < (FT_UInt32)( enc->lastRow * 256 + enc->lastCol ) )
     {
-      FT_ULong  code;
+      charcode++;
 
+      if ( charcode < (FT_UInt32)( enc->firstRow * 256 + enc->firstCol ) )
+        charcode = (FT_UInt32)( enc->firstRow * 256 + enc->firstCol );
 
-      mid  = ( min + max ) >> 1;
-      code = encodings[mid].enc;
+      charcodeRow = (FT_UShort)( charcode >> 8 );
+      charcodeCol = (FT_UShort)( charcode & 0xFF );
 
-      if ( charcode == code )
+      if ( charcodeCol < enc->firstCol )
+        charcodeCol = enc->firstCol;
+      else if ( charcodeCol > enc->lastCol )
       {
-        result = encodings[mid].glyph;
-        goto Exit;
+        charcodeRow++;
+        charcodeCol = enc->firstCol;
       }
 
-      if ( charcode < code )
-        max = mid;
-      else
-        min = mid + 1;
-    }
+      charcode = (FT_UInt32)( charcodeRow * 256 + charcodeCol );
 
-    charcode = 0;
-    if ( min < cmap->num_encodings )
-    {
-      charcode = encodings[min].enc;
-      result   = encodings[min].glyph;
+      result = (FT_UInt)enc->offset[ ( charcodeRow - enc->firstRow ) *
+                                     ( enc->lastCol - enc->firstCol + 1 ) +
+                                       charcodeCol - enc->firstCol          ];
+      if ( result != 0xFFFFU )
+        break;
     }
 
-  Exit:
-    if ( charcode > 0xFFFFFFFFUL )
-    {
-      FT_TRACE1(( "pcf_cmap_char_next: charcode 0x%x > 32bit API" ));
-      *acharcode = 0;
-      /* XXX: result should be changed to indicate an overflow error */
-    }
-    else
-      *acharcode = (FT_UInt32)charcode;
+    *acharcode = charcode;
 
     return result;
   }
@@ -221,8 +198,8 @@ THE SOFTWARE.
 
     memory = FT_FACE_MEMORY( face );
 
-    FT_FREE( face->encodings );
     FT_FREE( face->metrics );
+    FT_FREE( face->enc.offset );
 
     /* free properties */
     if ( face->properties )
diff --git a/src/pcf/pcfread.c b/src/pcf/pcfread.c
index d2f59f2d1..71143ecfb 100644
--- a/src/pcf/pcfread.c
+++ b/src/pcf/pcfread.c
@@ -974,17 +974,16 @@ THE SOFTWARE.
   pcf_get_encodings( FT_Stream  stream,
                      PCF_Face   face )
   {
-    FT_Error      error;
-    FT_Memory     memory = FT_FACE( face )->memory;
-    FT_ULong      format, size;
-    PCF_Enc       enc = &face->enc;
-    FT_ULong      nencoding;
-    FT_UShort     defaultCharRow, defaultCharCol;
-    FT_UShort     encodingOffset, defaultCharEncodingOffset;
-    FT_UShort     i, j;
-    FT_Byte*      pos;
-    FT_ULong      k;
-    PCF_Encoding  encoding = NULL;
+    FT_Error    error;
+    FT_Memory   memory = FT_FACE( face )->memory;
+    FT_ULong    format, size;
+    PCF_Enc     enc = &face->enc;
+    FT_ULong    nencoding;
+    FT_UShort*  offset;
+    FT_UShort   defaultCharRow, defaultCharCol;
+    FT_UShort   encodingOffset, defaultCharEncodingOffset;
+    FT_UShort   i, j;
+    FT_Byte*    pos;
 
 
     error = pcf_seek_to_table_type( stream,
@@ -1036,7 +1035,7 @@ THE SOFTWARE.
     nencoding = (FT_ULong)( enc->lastCol - enc->firstCol + 1 ) *
                 (FT_ULong)( enc->lastRow - enc->firstRow + 1 );
 
-    if ( FT_NEW_ARRAY( encoding, nencoding ) )
+    if ( FT_NEW_ARRAY( enc->offset, nencoding ) )
       goto Bail;
 
     error = FT_Stream_EnterFrame( stream, 2 * nencoding );
@@ -1098,7 +1097,7 @@ THE SOFTWARE.
       face->metrics[0]                         = tmp;
     }
 
-    k = 0;
+    offset = enc->offset;
     for ( i = enc->firstRow; i <= enc->lastRow; i++ )
     {
       for ( j = enc->firstCol; j <= enc->lastCol; j++ )
@@ -1118,29 +1117,17 @@ THE SOFTWARE.
             encodingOffset = 0;
           else if ( encodingOffset == 0 )
             encodingOffset = defaultCharEncodingOffset;
-
-          encoding[k].enc   = i * 256U + j;
-          encoding[k].glyph = encodingOffset;
-
-          FT_TRACE5(( "  code %u (0x%04X): idx %u\n",
-                      encoding[k].enc, encoding[k].enc, encoding[k].glyph ));
-
-          k++;
         }
+
+        *offset++ = encodingOffset;
       }
     }
     FT_Stream_ExitFrame( stream );
 
-    if ( FT_RENEW_ARRAY( encoding, nencoding, k ) )
-      goto Exit;
-
-    face->nencodings = k;
-    face->encodings  = encoding;
-
     return error;
 
   Exit:
-    FT_FREE( encoding );
+    FT_FREE( enc->offset );
 
   Bail:
     return error;