ref: bf40e92dea52ae9e5720f142bc1aa2746691ae87
parent: 110fc56beadee6a9414edff34222a54555b3a490
author: Werner Lemberg <[email protected]>
date: Wed May 7 06:21:13 EDT 2003
* 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.
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,25 @@
+2003-05-07 David Turner <[email protected]>
+
+ * 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 <[email protected]>
* src/autohint/ahoptim.c (LOG): Renamed to...
--- 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;
- switch ( source )
+ case AH_UV_OXY:
+ 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->ox;
+ point->v = point->oy;
}
- point->u = u;
- point->v = v;
+ 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;
+
+ default:
+ for ( ; point < point_limit; point++ )
+ {+ point->u = point->x;
+ point->v = point->y;
+ }
}
}
@@ -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,15 +1075,15 @@
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-- )
{@@ -1062,7 +1090,7 @@
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;
--- 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,11 +959,15 @@
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:
--- a/src/autohint/ahtypes.h
+++ b/src/autohint/ahtypes.h
@@ -244,13 +244,6 @@
/* */
/* 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 @@
/* */
/* 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_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 @@
/* 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 @@
/* */
/* 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;
--- 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,26 +879,119 @@
{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 */
q = table + 16 + num_segs2; /* starts table */
@@ -952,7 +1043,6 @@
goto Exit;
}
}
-
/* loop to next trial charcode */
if ( code >= 0xFFFFU )
break;
@@ -959,7 +1049,8 @@
code++;
}
- return (FT_UInt)result;
+
+#endif /* !1 */
Exit:
*pchar_code = result;