[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Devel] patch: faster auto-hinter
|
From: |
David Turner |
|
Subject: |
[Devel] patch: faster auto-hinter |
|
Date: |
Tue, 06 May 2003 18:10:48 +0200 |
|
User-agent: |
Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.3) Gecko/20030312 |
Hello,
here's a small patch to make the FreeType auto-hinter about 35%
faster, especially with Asian fonts which contain a lot of stems.
(this means 20% faster glyph loading on average for such fonts).
the effect on Latin fonts is smaller, since they contain less
stem segments and edges.
this is a preliminary work before the inclusion of Firefly's
"improvements" for CJK glyphs.
Werner, could you commit it to the CVS repository ?. I currently
don't have Internet access at my home :-(
Cheers,
- David Turner
- The FreeType Project (www.freetype.org)
PS: For reference, "ftbench -b a XXXXX" reports the
following numbers on a Sun Ultra 5 (400Mhz):
font file: before after:
cjk2.ttf 468 us/glyph 377 us/glyph
arial.ttf 231 us/glyph 210 us/glyph
results may vary depending on your architecture. The
speed increase is much less on a 1.5 GHz Pentium 4,
but I really care about the low end of the spectrum :-)
--
This message and any attachments (the "message") is intended solely for the
addressees and is confidential. If you receive this message in error, please
delete it and immediately notify the sender.
Any use not in accordance with its purpose, any dissemination or disclosure,
either whole or partial, is prohibited except formal approval.
The E-Mail transmission can not guarantee the integrity of this message.
CANAL+TECHNOLOGIES will not therefore be liable for the message if modified.
diff -urN freetype2/src/autohint/ahglyph.c freetype2-opt/src/autohint/ahglyph.c
--- freetype2/src/autohint/ahglyph.c Sat May 3 06:47:02 2003
+++ freetype2-opt/src/autohint/ahglyph.c Tue May 6 17:16:21 2003
@@ -640,49 +640,84 @@
AH_Point point = outline->points;
AH_Point point_limit = point + outline->num_points;
-
- for ( ; point < point_limit; point++ )
+ switch ( source )
{
- FT_Pos u, v;
-
-
- switch ( source )
- {
case AH_UV_FXY:
- u = point->fx;
- v = point->fy;
+ {
+ for ( ; point < point_limit; point++ )
+ {
+ point->u = point->fx;
+ point->v = point->fy;
+ }
+ }
break;
+
case AH_UV_FYX:
- u = point->fy;
- v = point->fx;
+ {
+ for ( ; point < point_limit; point++ )
+ {
+ point->u = point->fy;
+ point->v = point->fx;
+ }
+ }
break;
+
case AH_UV_OXY:
- u = point->ox;
- v = point->oy;
+ {
+ for ( ; point < point_limit; point++ )
+ {
+ point->u = point->ox;
+ point->v = point->oy;
+ }
+ }
break;
+
case AH_UV_OYX:
- u = point->oy;
- v = point->ox;
+ {
+ for ( ; point < point_limit; point++ )
+ {
+ point->u = point->oy;
+ point->v = point->ox;
+ }
+ }
break;
+
case AH_UV_YX:
- u = point->y;
- v = point->x;
+ {
+ for ( ; point < point_limit; point++ )
+ {
+ point->u = point->y;
+ point->v = point->x;
+ }
+ }
break;
+
case AH_UV_OX:
- u = point->x;
- v = point->ox;
+ {
+ for ( ; point < point_limit; point++ )
+ {
+ point->u = point->x;
+ point->v = point->ox;
+ }
+ }
break;
+
case AH_UV_OY:
- u = point->y;
- v = point->oy;
+ {
+ for ( ; point < point_limit; point++ )
+ {
+ point->u = point->y;
+ point->v = point->oy;
+ }
+ }
break;
+
default:
- u = point->x;
- v = point->y;
- break;
- }
- point->u = u;
- point->v = v;
+ for ( ; point < point_limit; point++ )
+ {
+ point->u = point->x;
+ point->v = point->y;
+ }
}
}
@@ -950,6 +985,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 +1012,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 +1048,8 @@
segment->first = min_point;
segment->last = min_point;
segment->pos = min_pos;
+ segment->score = 32000;
+ segment->link = NULL;
num_segments++;
segment++;
@@ -1027,6 +1066,8 @@
segment->first = max_point;
segment->last = max_point;
segment->pos = max_pos;
+ segment->score = 32000;
+ segment->link = NULL;
num_segments++;
segment++;
@@ -1047,22 +1088,21 @@
FT_LOCAL_DEF( void )
ah_outline_link_segments( AH_Outline outline )
{
- AH_Segment segments;
- AH_Segment segment_limit;
- int dimension;
-
-
- ah_setup_uv( outline, AH_UV_FYX );
+ AH_Segment segments;
+ AH_Segment segment_limit;
+ AH_Direction major_dir;
+ int dimension;
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 +1119,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 )
@@ -1123,40 +1163,100 @@
if ( score < best_score )
{
- best_score = score;
+ best_score = score;
best_segment = seg2;
}
}
}
}
- if ( best_segment )
- {
- seg1->link = best_segment;
- seg1->score = best_score;
+ if ( best_segment )
+ {
+ seg1->link = best_segment;
+ seg1->score = best_score;
+ best_segment->num_linked++;
+ }
+ }
+#endif
- best_segment->num_linked++;
- }
+#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;
- } /* edges 1 */
+ 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
/* 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;
}
+
+ /* fprintf( stderr, "*%d ", compares ); */
}
@@ -1208,6 +1308,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 +1327,6 @@
if ( dist < 0 )
dist = -dist;
- dist = FT_MulFix( dist, scale );
if ( dist < edge_distance_threshold )
{
found = edge;
@@ -1262,7 +1364,6 @@
edge->last = seg;
}
}
-
*p_num_edges = (FT_Int)( edge_limit - edges );
@@ -1280,6 +1381,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 removing this loop and setting
+ * the "edge" field of each segment directly in the
+ * code aboce. For some reason, it slows down execution
+ * speed ... on a Sun
+ */
for ( edge = edges; edge < edge_limit; edge++ )
{
seg = edge->first;
diff -urN freetype2/src/autohint/ahhint.c freetype2-opt/src/autohint/ahhint.c
--- freetype2/src/autohint/ahhint.c Sat May 3 22:13:47 2003
+++ freetype2-opt/src/autohint/ahhint.c Tue May 6 17:19:12 2003
@@ -884,6 +884,50 @@
goto Store_Point;
}
+
+#if 1
+ {
+ FT_UInt min, max, mid;
+ AH_Edge edge;
+ 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're 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 /* !O */
/* otherwise, interpolate the point in between */
{
AH_Edge before = 0;
@@ -914,11 +958,14 @@
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 /* !O */
Store_Point:
diff -urN freetype2/src/autohint/ahtypes.h freetype2-opt/src/autohint/ahtypes.h
--- freetype2/src/autohint/ahtypes.h Sat May 3 22:13:48 2003
+++ freetype2-opt/src/autohint/ahtypes.h Mon May 5 17:02:37 2003
@@ -271,11 +271,6 @@
{
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,11 @@
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;
@@ -330,22 +330,23 @@
/* */
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 -urN freetype2/src/sfnt/ttcmap0.c freetype2-opt/src/sfnt/ttcmap0.c
--- freetype2/src/sfnt/ttcmap0.c Wed Apr 23 21:48:24 2003
+++ freetype2-opt/src/sfnt/ttcmap0.c Tue May 6 17:11:09 2003
@@ -778,7 +778,6 @@
FT_UInt max = num_segs2 >> 1;
FT_UInt mid, start, end, offset;
-
while ( min < max )
{
mid = ( min + max ) >> 1;
@@ -789,10 +788,8 @@
if ( code < start )
max = mid;
-
else if ( code > end )
min = mid + 1;
-
else
{
/* we found the segment */
@@ -881,25 +878,115 @@
{
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 (;;)
{
+ /* Some fonts have more than 170 segments in their charmaps! */
+ /* We changed this function to use a more efficient binary */
+ /* search */
FT_UInt offset, n;
FT_Int delta;
+ FT_UInt min = 0;
+ FT_UInt max = num_segs2 >> 1;
+ FT_UInt mid, start, end;
+ FT_UInt hi, lo;
+
+ /* we begin by finding the segment whose 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-0 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;
p = table + 14; /* ends table */
q = table + 16 + num_segs2; /* starts table */
@@ -952,14 +1039,13 @@
goto Exit;
}
}
-
/* loop to next trial charcode */
if ( code >= 0xFFFFU )
break;
code++;
}
- return (FT_UInt)result;
+#endif
Exit:
*pchar_code = result;
- [Devel] patch: faster auto-hinter,
David Turner <=