kc3-lang/freetype

diff --git a/ChangeLog b/ChangeLog
index ee6928b..ecfd6ad 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,25 @@
+2003-05-07  David Turner  <david@freetype.org>
+
+	* src/autohint/ahglyph.c (ah_setup_uv): Exchange `for' loop and
+	`switch' statement to make it run faster.
+	(ah_outline_compute_segments): Reset `segment->score' and
+	`segment->link'.
+	(ah_outline_link_segments): Provide alternative code which does
+	the same but runs much faster.
+	Handle major direction also.
+	(ah_outline_compute_edges): Scale `edge_distance_threshold' down
+	after rounding instead of scaling comparison value in loop.
+
+	* src/autohint/ahhint.c (ah_hinter_align_stong_points): Provide
+	alternative code which runs faster.
+	Handle `before->scale == 0'.
+
+	* src/autohint/ahtypes.h (AH_SegmentRec): Move some fields down.
+	(AH_EdgeRec): Move some fields in structure.
+	New field `scale'.
+
+	* src/sfnt/ttcmap0.c (tt_cmap4_char_next): Use binary search.
+
 2003-05-02  Werner Lemberg  <wl@gnu.org>
 
 	* src/autohint/ahoptim.c (LOG): Renamed to...
diff --git a/src/autohint/ahglyph.c b/src/autohint/ahglyph.c
index de8bab4..91f3b72 100644
--- a/src/autohint/ahglyph.c
+++ b/src/autohint/ahglyph.c
@@ -641,48 +641,70 @@
     AH_Point  point_limit = point + outline->num_points;
 
 
-    for ( ; point < point_limit; point++ )
+    switch ( source )
     {
-      FT_Pos  u, v;
+    case AH_UV_FXY:
+      for ( ; point < point_limit; point++ )
+      {
+        point->u = point->fx;
+        point->v = point->fy;
+      }
+      break;
+
+    case AH_UV_FYX:
+      for ( ; point < point_limit; point++ )
+      {
+        point->u = point->fy;
+        point->v = point->fx;
+      }
+      break;
+
+    case AH_UV_OXY:
+      for ( ; point < point_limit; point++ )
+      {
+        point->u = point->ox;
+        point->v = point->oy;
+      }
+      break;
+
+    case AH_UV_OYX:
+      for ( ; point < point_limit; point++ )
+      {
+        point->u = point->oy;
+        point->v = point->ox;
+      }
+      break;
+
+    case AH_UV_YX:
+      for ( ; point < point_limit; point++ )
+      {
+        point->u = point->y;
+        point->v = point->x;
+      }
+      break;
+
+    case AH_UV_OX:
+      for ( ; point < point_limit; point++ )
+      {
+        point->u = point->x;
+        point->v = point->ox;
+      }
+      break;
 
+    case AH_UV_OY:
+      for ( ; point < point_limit; point++ )
+      {
+        point->u = point->y;
+        point->v = point->oy;
+      }
+      break;
 
-      switch ( source )
+    default:
+      for ( ; point < point_limit; point++ )
       {
-      case AH_UV_FXY:
-        u = point->fx;
-        v = point->fy;
-        break;
-      case AH_UV_FYX:
-        u = point->fy;
-        v = point->fx;
-        break;
-      case AH_UV_OXY:
-        u = point->ox;
-        v = point->oy;
-        break;
-      case AH_UV_OYX:
-        u = point->oy;
-        v = point->ox;
-        break;
-      case AH_UV_YX:
-        u = point->y;
-        v = point->x;
-        break;
-      case AH_UV_OX:
-        u = point->x;
-        v = point->ox;
-        break;
-      case AH_UV_OY:
-        u = point->y;
-        v = point->oy;
-        break;
-      default:
-        u = point->x;
-        v = point->y;
-        break;
+        point->u = point->x;
+        point->v = point->y;
       }
-      point->u = u;
-      point->v = v;
     }
   }
 
@@ -950,6 +972,8 @@
             segment->first    = point;
             segment->last     = point;
             segment->contour  = contour;
+            segment->score    = 32000;
+            segment->link     = NULL;
             on_edge           = 1;
 
 #ifdef AH_HINT_METRICS
@@ -975,8 +999,8 @@
         AH_Point  point       =  outline->points;
         AH_Point  point_limit =  point + outline->num_points;
 
-        FT_Pos    min_pos     =  32000;
-        FT_Pos    max_pos     = -32000;
+        FT_Pos    min_pos =  32000;
+        FT_Pos    max_pos = -32000;
 
 
         min_point = 0;
@@ -1011,6 +1035,8 @@
           segment->first = min_point;
           segment->last  = min_point;
           segment->pos   = min_pos;
+          segment->score = 32000;
+          segment->link  = NULL;
 
           num_segments++;
           segment++;
@@ -1027,6 +1053,8 @@
           segment->first = max_point;
           segment->last  = max_point;
           segment->pos   = max_pos;
+          segment->score = 32000;
+          segment->link  = NULL;
 
           num_segments++;
           segment++;
@@ -1047,22 +1075,22 @@
   FT_LOCAL_DEF( void )
   ah_outline_link_segments( AH_Outline  outline )
   {
-    AH_Segment  segments;
-    AH_Segment  segment_limit;
-    int         dimension;
-
+    AH_Segment    segments;
+    AH_Segment    segment_limit;
+    AH_Direction  major_dir;
+    int           dimension;
 
-    ah_setup_uv( outline, AH_UV_FYX );
 
     segments      = outline->horz_segments;
     segment_limit = segments + outline->num_hsegments;
+    major_dir     = outline->horz_major_dir;
 
     for ( dimension = 1; dimension >= 0; dimension-- )
     {
       AH_Segment  seg1;
       AH_Segment  seg2;
 
-
+#if 0
       /* now compare each segment to the others */
       for ( seg1 = segments; seg1 < segment_limit; seg1++ )
       {
@@ -1079,7 +1107,7 @@
         if ( best_segment )
           best_score = seg1->score;
         else
-          best_score = 32000;
+          best_score = +32000;
 
         for ( seg2 = segments; seg2 < segment_limit; seg2++ )
           if ( seg1 != seg2 && seg1->dir + seg2->dir == 0 )
@@ -1134,28 +1162,86 @@
         {
           seg1->link  = best_segment;
           seg1->score = best_score;
-
           best_segment->num_linked++;
         }
+      }
+#endif /* 0 */
 
-      } /* edges 1 */
+#if 1
+      /* the following code does the same, but much faster! */
+
+      /* now compare each segment to the others */
+      for ( seg1 = segments; seg1 < segment_limit; seg1++ )
+      {
+        /* the fake segments are introduced to hint the metrics -- */
+        /* we must never link them to anything                     */
+        if ( seg1->first == seg1->last || seg1->dir != major_dir )
+          continue;
+
+        for ( seg2 = segments; seg2 < segment_limit; seg2++ )
+          if ( seg2 != seg1 && seg1->dir + seg2->dir == 0 )
+          {
+            FT_Pos  pos1 = seg1->pos;
+            FT_Pos  pos2 = seg2->pos;
+            FT_Pos  dist = pos2 - pos1;
+
+
+            if ( dist < 0 )
+              continue;
+
+            {
+              FT_Pos  min = seg1->min_coord;
+              FT_Pos  max = seg1->max_coord;
+              FT_Pos  len, score;
+
+
+              if ( min < seg2->min_coord )
+                min = seg2->min_coord;
+
+              if ( max > seg2->max_coord )
+                max = seg2->max_coord;
+
+              len = max - min;
+              if ( len >= 8 )
+              {
+                score = dist + 3000 / len;
+
+                if ( score < seg1->score )
+                {
+                  seg1->score = score;
+                  seg1->link  = seg2;
+                }
+
+                if ( score < seg2->score )
+                {
+                  seg2->score = score;
+                  seg2->link  = seg1;
+                }
+              }
+            }
+          }
+      }
+#endif /* 1 */
 
       /* now, compute the `serif' segments */
       for ( seg1 = segments; seg1 < segment_limit; seg1++ )
       {
         seg2 = seg1->link;
 
-        if ( seg2 && seg2->link != seg1 )
+        if ( seg2 )
         {
-          seg1->link  = 0;
-          seg1->serif = seg2->link;
+          seg2->num_linked++;
+          if ( seg2->link != seg1 )
+          {
+            seg1->link  = 0;
+            seg1->serif = seg2->link;
+          }
         }
       }
 
-      ah_setup_uv( outline, AH_UV_FXY );
-
       segments      = outline->vert_segments;
       segment_limit = segments + outline->num_vsegments;
+      major_dir     = outline->vert_major_dir;
     }
   }
 
@@ -1208,6 +1294,9 @@
       if ( edge_distance_threshold > 64 / 4 )
         edge_distance_threshold = 64 / 4;
 
+      edge_distance_threshold = FT_DivFix( edge_distance_threshold,
+                                           scale );
+
       edge_limit = edges;
       for ( seg = segments; seg < segment_limit; seg++ )
       {
@@ -1224,7 +1313,6 @@
           if ( dist < 0 )
             dist = -dist;
 
-          dist = FT_MulFix( dist, scale );
           if ( dist < edge_distance_threshold )
           {
             found = edge;
@@ -1262,7 +1350,6 @@
           edge->last            = seg;
         }
       }
-
       *p_num_edges = (FT_Int)( edge_limit - edges );
 
 
@@ -1280,6 +1367,12 @@
 
       /* first of all, set the `edge' field in each segment -- this is */
       /* required in order to compute edge links                       */
+
+      /* Note that I've tried to remove this loop, setting
+       * the "edge" field of each segment directly in the
+       * code above.  For some reason, it slows down execution
+       * speed -- on a Sun.
+       */
       for ( edge = edges; edge < edge_limit; edge++ )
       {
         seg = edge->first;
diff --git a/src/autohint/ahhint.c b/src/autohint/ahhint.c
index c172340..7f3cf65 100644
--- a/src/autohint/ahhint.c
+++ b/src/autohint/ahhint.c
@@ -884,6 +884,51 @@
             goto Store_Point;
           }
 
+#if 1
+          {
+            FT_UInt  min, max, mid;
+            FT_Pos   fpos;
+
+
+            /* find enclosing edges */
+            min = 0;
+            max = edge_limit - edges;
+
+            while ( min < max )
+            {
+              mid  = ( max + min ) >> 1;
+              edge = edges + mid;
+              fpos = edge->fpos;
+
+              if ( u < fpos )
+                max = mid;
+              else if ( u > fpos )
+                min = mid + 1;
+              else
+              {
+                /* we are on the edge */
+                u = edge->pos;
+                goto Store_Point;
+              }
+            }
+
+            {
+              AH_Edge  before = edges + min - 1;
+              AH_Edge  after  = edges + min + 0;
+
+
+              /* assert( before && after && before != after ) */
+              if ( before->scale == 0 )
+                before->scale = FT_DivFix( after->pos - before->pos,
+                                           after->fpos - before->fpos );
+
+              u = before->pos + FT_MulFix( fu - before->fpos,
+                                           before->scale );
+            }
+          }
+
+#else /* !0 */
+
           /* otherwise, interpolate the point in between */
           {
             AH_Edge  before = 0;
@@ -914,12 +959,16 @@
               after = edge;
             }
 
-            /* assert( before && after && before != after ) */
-            u = before->pos + FT_MulDiv( fu - before->fpos,
-                                         after->pos - before->pos,
-                                         after->fpos - before->fpos );
+            if ( before->scale == 0 )
+              before->scale = FT_DivFix( after->pos - before->pos,
+                                        after->fpos - before->fpos );
+
+            u = before->pos + FT_MulFix( fu - before->fpos,
+                                        before->scale );
           }
 
+#endif /* !0 */
+
         Store_Point:
 
           /* save the point position */
diff --git a/src/autohint/ahtypes.h b/src/autohint/ahtypes.h
index 07ec37d..5ad62ba 100644
--- a/src/autohint/ahtypes.h
+++ b/src/autohint/ahtypes.h
@@ -244,13 +244,6 @@ FT_BEGIN_HEADER
   /*                                                                       */
   /*    dir        :: The segment direction.                               */
   /*                                                                       */
-  /*    first      :: The first point in the segment.                      */
-  /*                                                                       */
-  /*    last       :: The last point in the segment.                       */
-  /*                                                                       */
-  /*    contour    :: A pointer to the first point of the segment's        */
-  /*                  contour.                                             */
-  /*                                                                       */
   /*    min_coord  :: The minimum coordinate of the segment.               */
   /*                                                                       */
   /*    max_coord  :: The maximum coordinate of the segment.               */
@@ -267,15 +260,17 @@ FT_BEGIN_HEADER
   /*                                                                       */
   /*    score      :: Used to score the segment when selecting them.       */
   /*                                                                       */
+  /*    first      :: The first point in the segment.                      */
+  /*                                                                       */
+  /*    last       :: The last point in the segment.                       */
+  /*                                                                       */
+  /*    contour    :: A pointer to the first point of the segment's        */
+  /*                  contour.                                             */
+  /*                                                                       */
   typedef struct  AH_SegmentRec_
   {
     AH_Edge_Flags  flags;
     AH_Direction   dir;
-
-    AH_Point       first;       /* first point in edge segment             */
-    AH_Point       last;        /* last point in edge segment              */
-    AH_Point*      contour;     /* ptr to first point of segment's contour */
-
     FT_Pos         pos;         /* position of segment           */
     FT_Pos         min_coord;   /* minimum coordinate of segment */
     FT_Pos         max_coord;   /* maximum coordinate of segment */
@@ -288,6 +283,10 @@ FT_BEGIN_HEADER
     FT_Pos         num_linked;  /* number of linked segments  */
     FT_Pos         score;
 
+    AH_Point       first;       /* first point in edge segment             */
+    AH_Point       last;        /* last point in edge segment              */
+    AH_Point*      contour;     /* ptr to first point of segment's contour */
+
   } AH_SegmentRec;
 
 
@@ -302,19 +301,22 @@ FT_BEGIN_HEADER
   /*    located on it.                                                     */
   /*                                                                       */
   /* <Fields>                                                              */
-  /*    flags      :: The segment edge flags (straight, rounded, etc.).    */
+  /*    fpos       :: The original edge position in font units.            */
   /*                                                                       */
-  /*    dir        :: The main segment direction on this edge.             */
+  /*    opos       :: The original scaled edge position.                   */
   /*                                                                       */
-  /*    first      :: The first edge segment.                              */
+  /*    pos        :: The hinted edge position.                            */
   /*                                                                       */
-  /*    last       :: The last edge segment.                               */
+  /*    flags      :: The segment edge flags (straight, rounded, etc.).    */
   /*                                                                       */
-  /*    fpos       :: The original edge position in font units.            */
+  /*    dir        :: The main segment direction on this edge.             */
   /*                                                                       */
-  /*    opos       :: The original scaled edge position.                   */
+  /*    scale      :: Scaling factor between original and hinted edge      */
+  /*                  positions.                                           */
   /*                                                                       */
-  /*    pos        :: The hinted edge position.                            */
+  /*    blue_edge  :: Indicate the blue zone edge this edge is related to. */
+  /*                  Only set for some of the horizontal edges in a latin */
+  /*                  font.                                                */
   /*                                                                       */
   /*    link       :: The linked edge.                                     */
   /*                                                                       */
@@ -324,28 +326,30 @@ FT_BEGIN_HEADER
   /*                                                                       */
   /*    score      :: Used to score the edge when selecting them.          */
   /*                                                                       */
-  /*    blue_edge  :: Indicate the blue zone edge this edge is related to. */
-  /*                  Only set for some of the horizontal edges in a latin */
-  /*                  font.                                                */
+  /*    first      :: The first edge segment.                              */
+  /*                                                                       */
+  /*    last       :: The last edge segment.                               */
   /*                                                                       */
   typedef struct  AH_EdgeRec_
   {
-    AH_Edge_Flags  flags;
-    AH_Direction   dir;
-
-    AH_Segment     first;
-    AH_Segment     last;
-
     FT_Pos         fpos;
     FT_Pos         opos;
     FT_Pos         pos;
 
+    AH_Edge_Flags  flags;
+    AH_Direction   dir;
+    FT_Fixed       scale;
+    FT_Pos*        blue_edge;
+
     AH_Edge        link;
     AH_Edge        serif;
     FT_Int         num_linked;
 
     FT_Int         score;
-    FT_Pos*        blue_edge;
+
+    AH_Segment     first;
+    AH_Segment     last;
+
 
   } AH_EdgeRec;
 
diff --git a/src/sfnt/ttcmap0.c b/src/sfnt/ttcmap0.c
index d87aed8..b458302 100644
--- a/src/sfnt/ttcmap0.c
+++ b/src/sfnt/ttcmap0.c
@@ -789,10 +789,8 @@
 
           if ( code < start )
             max = mid;
-
           else if ( code > end )
             min = mid + 1;
-
           else
           {
             /* we found the segment */
@@ -881,24 +879,117 @@
   {
     FT_Byte*   table     = cmap->data;
     FT_UInt32  result    = 0;
-    FT_UInt32  char_code = *pchar_code + 1;
     FT_UInt    gindex    = 0;
+    FT_UInt32  char_code = *pchar_code;
     FT_Byte*   p;
-    FT_Byte*   q;
     FT_UInt    code, num_segs2;
 
 
-    if ( char_code >= 0x10000UL )
+    if ( char_code >= 0xFFFFUL )
       goto Exit;
 
-    code      = (FT_UInt)char_code;
+    code      = (FT_UInt)char_code + 1;
     p         = table + 6;
     num_segs2 = TT_PEEK_USHORT(p) & -2;  /* ensure even-ness */
 
+#if 1
+
     for (;;)
     {
-      FT_UInt  offset, n;
+      /* Some fonts have more than 170 segments in their charmaps! */
+      /* We changed this function to use a more efficient binary   */
+      /* search                                                    */
+      FT_UInt  offset;
       FT_Int   delta;
+      FT_UInt  min = 0;
+      FT_UInt  max = num_segs2 >> 1;
+      FT_UInt  mid, start, end;
+      FT_UInt  hi;
+
+
+      /* we begin by finding the segment which end is
+         closer to our code point */
+      hi = 0;
+      while ( min < max )
+      {
+        mid = ( min + max ) >> 1;
+        p   = table + 14 + mid * 2;
+        end = TT_PEEK_USHORT( p );
+
+        if ( end < code )
+          min = mid + 1;
+        else
+        {
+          hi  = mid;
+          max = mid;
+        }
+      }
+
+      if ( hi > max )
+      {
+        /* the point is behind the last segment;
+           we will exit right now */
+        goto Exit;
+      }
+
+      p   = table + 14 + hi * 2;
+      end = TT_PEEK_USHORT( p );
+
+      p    += 2 + num_segs2;
+      start = TT_PEEK_USHORT( p );
+
+      if ( code < start )
+        code = start;
+
+      p    += num_segs2;
+      delta = TT_PEEK_USHORT( p );
+
+      p     += num_segs2;
+      offset = TT_PEEK_USHORT( p );
+
+      if ( offset != 0 && offset != 0xFFFFU )
+      {
+        /* parse the glyph ids array for non-zero index */
+        p += offset + ( code - start ) * 2;
+        while ( code <= end )
+        {
+          gindex = TT_NEXT_USHORT( p );
+          if ( gindex != 0 )
+          {
+            gindex = (FT_UInt)( gindex + delta ) & 0xFFFFU;
+            if ( gindex != 0 )
+            {
+              result = code;
+              goto Exit;
+            }
+          }
+          code++;
+        }
+      }
+      else if ( offset == 0xFFFFU )
+      {
+        /* an offset of 0xFFFF means an empty glyph in certain fonts! */
+        code = end + 1;
+      }
+      else  /* offset == 0 */
+      {
+        gindex = (FT_UInt)( code + delta ) & 0xFFFFU;
+        if ( gindex != 0 )
+        {
+          result = code;
+          goto Exit;
+        }
+        code++;
+      }
+    }
+
+#else   /* old code -- kept for reference */
+
+    for ( ;; )
+    {
+      FT_UInt   offset, n;
+      FT_Int    delta;
+      FT_Byte*  q;
 
 
       p = table + 14;              /* ends table  */
@@ -952,14 +1043,14 @@
           goto Exit;
         }
       }
-
       /* loop to next trial charcode */
       if ( code >= 0xFFFFU )
         break;
 
       code++;
     }
-    return (FT_UInt)result;
+
+#endif /* !1 */
 
   Exit:
     *pchar_code = result;