1/***************************************************************************/
2/* */
3/* afhints.c */
4/* */
5/* Auto-fitter hinting routines (body). */
6/* */
7/* Copyright 2003-2018 by */
8/* David Turner, Robert Wilhelm, and Werner Lemberg. */
9/* */
10/* This file is part of the FreeType project, and may only be used, */
11/* modified, and distributed under the terms of the FreeType project */
12/* license, LICENSE.TXT. By continuing to use, modify, or distribute */
13/* this file you indicate that you have read the license and */
14/* understand and accept it fully. */
15/* */
16/***************************************************************************/
17
18
19#include "afhints.h"
20#include "aferrors.h"
21#include FT_INTERNAL_CALC_H
22#include FT_INTERNAL_DEBUG_H
23
24
25 /*************************************************************************/
26 /* */
27 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
28 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
29 /* messages during execution. */
30 /* */
31#undef FT_COMPONENT
32#define FT_COMPONENT trace_afhints
33
34
35 /* Get new segment for given axis. */
36
37 FT_LOCAL_DEF( FT_Error )
38 af_axis_hints_new_segment( AF_AxisHints axis,
39 FT_Memory memory,
40 AF_Segment *asegment )
41 {
42 FT_Error error = FT_Err_Ok;
43 AF_Segment segment = NULL;
44
45
46 if ( axis->num_segments < AF_SEGMENTS_EMBEDDED )
47 {
48 if ( !axis->segments )
49 {
50 axis->segments = axis->embedded.segments;
51 axis->max_segments = AF_SEGMENTS_EMBEDDED;
52 }
53 }
54 else if ( axis->num_segments >= axis->max_segments )
55 {
56 FT_Int old_max = axis->max_segments;
57 FT_Int new_max = old_max;
58 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *segment ) );
59
60
61 if ( old_max >= big_max )
62 {
63 error = FT_THROW( Out_Of_Memory );
64 goto Exit;
65 }
66
67 new_max += ( new_max >> 2 ) + 4;
68 if ( new_max < old_max || new_max > big_max )
69 new_max = big_max;
70
71 if ( axis->segments == axis->embedded.segments )
72 {
73 if ( FT_NEW_ARRAY( axis->segments, new_max ) )
74 goto Exit;
75 ft_memcpy( axis->segments, axis->embedded.segments,
76 sizeof ( axis->embedded.segments ) );
77 }
78 else
79 {
80 if ( FT_RENEW_ARRAY( axis->segments, old_max, new_max ) )
81 goto Exit;
82 }
83
84 axis->max_segments = new_max;
85 }
86
87 segment = axis->segments + axis->num_segments++;
88
89 Exit:
90 *asegment = segment;
91 return error;
92 }
93
94
95 /* Get new edge for given axis, direction, and position, */
96 /* without initializing the edge itself. */
97
98 FT_LOCAL( FT_Error )
99 af_axis_hints_new_edge( AF_AxisHints axis,
100 FT_Int fpos,
101 AF_Direction dir,
102 FT_Bool top_to_bottom_hinting,
103 FT_Memory memory,
104 AF_Edge *anedge )
105 {
106 FT_Error error = FT_Err_Ok;
107 AF_Edge edge = NULL;
108 AF_Edge edges;
109
110
111 if ( axis->num_edges < AF_EDGES_EMBEDDED )
112 {
113 if ( !axis->edges )
114 {
115 axis->edges = axis->embedded.edges;
116 axis->max_edges = AF_EDGES_EMBEDDED;
117 }
118 }
119 else if ( axis->num_edges >= axis->max_edges )
120 {
121 FT_Int old_max = axis->max_edges;
122 FT_Int new_max = old_max;
123 FT_Int big_max = (FT_Int)( FT_INT_MAX / sizeof ( *edge ) );
124
125
126 if ( old_max >= big_max )
127 {
128 error = FT_THROW( Out_Of_Memory );
129 goto Exit;
130 }
131
132 new_max += ( new_max >> 2 ) + 4;
133 if ( new_max < old_max || new_max > big_max )
134 new_max = big_max;
135
136 if ( axis->edges == axis->embedded.edges )
137 {
138 if ( FT_NEW_ARRAY( axis->edges, new_max ) )
139 goto Exit;
140 ft_memcpy( axis->edges, axis->embedded.edges,
141 sizeof ( axis->embedded.edges ) );
142 }
143 else
144 {
145 if ( FT_RENEW_ARRAY( axis->edges, old_max, new_max ) )
146 goto Exit;
147 }
148
149 axis->max_edges = new_max;
150 }
151
152 edges = axis->edges;
153 edge = edges + axis->num_edges;
154
155 while ( edge > edges )
156 {
157 if ( top_to_bottom_hinting ? ( edge[-1].fpos > fpos )
158 : ( edge[-1].fpos < fpos ) )
159 break;
160
161 /* we want the edge with same position and minor direction */
162 /* to appear before those in the major one in the list */
163 if ( edge[-1].fpos == fpos && dir == axis->major_dir )
164 break;
165
166 edge[0] = edge[-1];
167 edge--;
168 }
169
170 axis->num_edges++;
171
172 Exit:
173 *anedge = edge;
174 return error;
175 }
176
177
178#ifdef FT_DEBUG_AUTOFIT
179
180#include FT_CONFIG_STANDARD_LIBRARY_H
181
182 /* The dump functions are used in the `ftgrid' demo program, too. */
183#define AF_DUMP( varformat ) \
184 do \
185 { \
186 if ( to_stdout ) \
187 printf varformat; \
188 else \
189 FT_TRACE7( varformat ); \
190 } while ( 0 )
191
192
193 static const char*
194 af_dir_str( AF_Direction dir )
195 {
196 const char* result;
197
198
199 switch ( dir )
200 {
201 case AF_DIR_UP:
202 result = "up";
203 break;
204 case AF_DIR_DOWN:
205 result = "down";
206 break;
207 case AF_DIR_LEFT:
208 result = "left";
209 break;
210 case AF_DIR_RIGHT:
211 result = "right";
212 break;
213 default:
214 result = "none";
215 }
216
217 return result;
218 }
219
220
221#define AF_INDEX_NUM( ptr, base ) (int)( (ptr) ? ( (ptr) - (base) ) : -1 )
222
223
224 static char*
225 af_print_idx( char* p,
226 int idx )
227 {
228 if ( idx == -1 )
229 {
230 p[0] = '-';
231 p[1] = '-';
232 p[2] = '\0';
233 }
234 else
235 ft_sprintf( p, "%d", idx );
236
237 return p;
238 }
239
240
241 static int
242 af_get_segment_index( AF_GlyphHints hints,
243 int point_idx,
244 int dimension )
245 {
246 AF_AxisHints axis = &hints->axis[dimension];
247 AF_Point point = hints->points + point_idx;
248 AF_Segment segments = axis->segments;
249 AF_Segment limit = segments + axis->num_segments;
250 AF_Segment segment;
251
252
253 for ( segment = segments; segment < limit; segment++ )
254 {
255 if ( segment->first <= segment->last )
256 {
257 if ( point >= segment->first && point <= segment->last )
258 break;
259 }
260 else
261 {
262 AF_Point p = segment->first;
263
264
265 for (;;)
266 {
267 if ( point == p )
268 goto Exit;
269
270 if ( p == segment->last )
271 break;
272
273 p = p->next;
274 }
275 }
276 }
277
278 Exit:
279 if ( segment == limit )
280 return -1;
281
282 return (int)( segment - segments );
283 }
284
285
286 static int
287 af_get_edge_index( AF_GlyphHints hints,
288 int segment_idx,
289 int dimension )
290 {
291 AF_AxisHints axis = &hints->axis[dimension];
292 AF_Edge edges = axis->edges;
293 AF_Segment segment = axis->segments + segment_idx;
294
295
296 return segment_idx == -1 ? -1 : AF_INDEX_NUM( segment->edge, edges );
297 }
298
299
300#ifdef __cplusplus
301 extern "C" {
302#endif
303 void
304 af_glyph_hints_dump_points( AF_GlyphHints hints,
305 FT_Bool to_stdout )
306 {
307 AF_Point points = hints->points;
308 AF_Point limit = points + hints->num_points;
309 AF_Point* contour = hints->contours;
310 AF_Point* climit = contour + hints->num_contours;
311 AF_Point point;
312
313
314 AF_DUMP(( "Table of points:\n" ));
315
316 if ( hints->num_points )
317 {
318 AF_DUMP(( " index hedge hseg vedge vseg flags "
319 /* " XXXXX XXXXX XXXXX XXXXX XXXXX XXXXXX" */
320 " xorg yorg xscale yscale xfit yfit" ));
321 /* " XXXXX XXXXX XXXX.XX XXXX.XX XXXX.XX XXXX.XX" */
322 }
323 else
324 AF_DUMP(( " (none)\n" ));
325
326 for ( point = points; point < limit; point++ )
327 {
328 int point_idx = AF_INDEX_NUM( point, points );
329 int segment_idx_0 = af_get_segment_index( hints, point_idx, 0 );
330 int segment_idx_1 = af_get_segment_index( hints, point_idx, 1 );
331
332 char buf1[16], buf2[16], buf3[16], buf4[16];
333
334
335 /* insert extra newline at the beginning of a contour */
336 if ( contour < climit && *contour == point )
337 {
338 AF_DUMP(( "\n" ));
339 contour++;
340 }
341
342 AF_DUMP(( " %5d %5s %5s %5s %5s %s"
343 " %5d %5d %7.2f %7.2f %7.2f %7.2f\n",
344 point_idx,
345 af_print_idx( buf1,
346 af_get_edge_index( hints, segment_idx_1, 1 ) ),
347 af_print_idx( buf2, segment_idx_1 ),
348 af_print_idx( buf3,
349 af_get_edge_index( hints, segment_idx_0, 0 ) ),
350 af_print_idx( buf4, segment_idx_0 ),
351 ( point->flags & AF_FLAG_NEAR )
352 ? " near "
353 : ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
354 ? " weak "
355 : "strong",
356
357 point->fx,
358 point->fy,
359 point->ox / 64.0,
360 point->oy / 64.0,
361 point->x / 64.0,
362 point->y / 64.0 ));
363 }
364 AF_DUMP(( "\n" ));
365 }
366#ifdef __cplusplus
367 }
368#endif
369
370
371 static const char*
372 af_edge_flags_to_string( FT_UInt flags )
373 {
374 static char temp[32];
375 int pos = 0;
376
377
378 if ( flags & AF_EDGE_ROUND )
379 {
380 ft_memcpy( temp + pos, "round", 5 );
381 pos += 5;
382 }
383 if ( flags & AF_EDGE_SERIF )
384 {
385 if ( pos > 0 )
386 temp[pos++] = ' ';
387 ft_memcpy( temp + pos, "serif", 5 );
388 pos += 5;
389 }
390 if ( pos == 0 )
391 return "normal";
392
393 temp[pos] = '\0';
394
395 return temp;
396 }
397
398
399 /* Dump the array of linked segments. */
400
401#ifdef __cplusplus
402 extern "C" {
403#endif
404 void
405 af_glyph_hints_dump_segments( AF_GlyphHints hints,
406 FT_Bool to_stdout )
407 {
408 FT_Int dimension;
409
410
411 for ( dimension = 1; dimension >= 0; dimension-- )
412 {
413 AF_AxisHints axis = &hints->axis[dimension];
414 AF_Point points = hints->points;
415 AF_Edge edges = axis->edges;
416 AF_Segment segments = axis->segments;
417 AF_Segment limit = segments + axis->num_segments;
418 AF_Segment seg;
419
420 char buf1[16], buf2[16], buf3[16];
421
422
423 AF_DUMP(( "Table of %s segments:\n",
424 dimension == AF_DIMENSION_HORZ ? "vertical"
425 : "horizontal" ));
426 if ( axis->num_segments )
427 {
428 AF_DUMP(( " index pos delta dir from to "
429 /* " XXXXX XXXXX XXXXX XXXXX XXXX XXXX" */
430 " link serif edge"
431 /* " XXXX XXXXX XXXX" */
432 " height extra flags\n" ));
433 /* " XXXXXX XXXXX XXXXXXXXXXX" */
434 }
435 else
436 AF_DUMP(( " (none)\n" ));
437
438 for ( seg = segments; seg < limit; seg++ )
439 AF_DUMP(( " %5d %5d %5d %5s %4d %4d"
440 " %4s %5s %4s"
441 " %6d %5d %11s\n",
442 AF_INDEX_NUM( seg, segments ),
443 seg->pos,
444 seg->delta,
445 af_dir_str( (AF_Direction)seg->dir ),
446 AF_INDEX_NUM( seg->first, points ),
447 AF_INDEX_NUM( seg->last, points ),
448
449 af_print_idx( buf1, AF_INDEX_NUM( seg->link, segments ) ),
450 af_print_idx( buf2, AF_INDEX_NUM( seg->serif, segments ) ),
451 af_print_idx( buf3, AF_INDEX_NUM( seg->edge, edges ) ),
452
453 seg->height,
454 seg->height - ( seg->max_coord - seg->min_coord ),
455 af_edge_flags_to_string( seg->flags ) ));
456 AF_DUMP(( "\n" ));
457 }
458 }
459#ifdef __cplusplus
460 }
461#endif
462
463
464 /* Fetch number of segments. */
465
466#ifdef __cplusplus
467 extern "C" {
468#endif
469 FT_Error
470 af_glyph_hints_get_num_segments( AF_GlyphHints hints,
471 FT_Int dimension,
472 FT_Int* num_segments )
473 {
474 AF_Dimension dim;
475 AF_AxisHints axis;
476
477
478 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT;
479
480 axis = &hints->axis[dim];
481 *num_segments = axis->num_segments;
482
483 return FT_Err_Ok;
484 }
485#ifdef __cplusplus
486 }
487#endif
488
489
490 /* Fetch offset of segments into user supplied offset array. */
491
492#ifdef __cplusplus
493 extern "C" {
494#endif
495 FT_Error
496 af_glyph_hints_get_segment_offset( AF_GlyphHints hints,
497 FT_Int dimension,
498 FT_Int idx,
499 FT_Pos *offset,
500 FT_Bool *is_blue,
501 FT_Pos *blue_offset )
502 {
503 AF_Dimension dim;
504 AF_AxisHints axis;
505 AF_Segment seg;
506
507
508 if ( !offset )
509 return FT_THROW( Invalid_Argument );
510
511 dim = ( dimension == 0 ) ? AF_DIMENSION_HORZ : AF_DIMENSION_VERT;
512
513 axis = &hints->axis[dim];
514
515 if ( idx < 0 || idx >= axis->num_segments )
516 return FT_THROW( Invalid_Argument );
517
518 seg = &axis->segments[idx];
519 *offset = ( dim == AF_DIMENSION_HORZ ) ? seg->first->fx
520 : seg->first->fy;
521 if ( seg->edge )
522 *is_blue = (FT_Bool)( seg->edge->blue_edge != 0 );
523 else
524 *is_blue = FALSE;
525
526 if ( *is_blue )
527 *blue_offset = seg->edge->blue_edge->org;
528 else
529 *blue_offset = 0;
530
531 return FT_Err_Ok;
532 }
533#ifdef __cplusplus
534 }
535#endif
536
537
538 /* Dump the array of linked edges. */
539
540#ifdef __cplusplus
541 extern "C" {
542#endif
543 void
544 af_glyph_hints_dump_edges( AF_GlyphHints hints,
545 FT_Bool to_stdout )
546 {
547 FT_Int dimension;
548
549
550 for ( dimension = 1; dimension >= 0; dimension-- )
551 {
552 AF_AxisHints axis = &hints->axis[dimension];
553 AF_Edge edges = axis->edges;
554 AF_Edge limit = edges + axis->num_edges;
555 AF_Edge edge;
556
557 char buf1[16], buf2[16];
558
559
560 /*
561 * note: AF_DIMENSION_HORZ corresponds to _vertical_ edges
562 * since they have a constant X coordinate.
563 */
564 if ( dimension == AF_DIMENSION_HORZ )
565 AF_DUMP(( "Table of %s edges (1px=%.2fu, 10u=%.2fpx):\n",
566 "vertical",
567 65536.0 * 64.0 / hints->x_scale,
568 10.0 * hints->x_scale / 65536.0 / 64.0 ));
569 else
570 AF_DUMP(( "Table of %s edges (1px=%.2fu, 10u=%.2fpx):\n",
571 "horizontal",
572 65536.0 * 64.0 / hints->y_scale,
573 10.0 * hints->y_scale / 65536.0 / 64.0 ));
574
575 if ( axis->num_edges )
576 {
577 AF_DUMP(( " index pos dir link serif"
578 /* " XXXXX XXXX.XX XXXXX XXXX XXXXX" */
579 " blue opos pos flags\n" ));
580 /* " X XXXX.XX XXXX.XX XXXXXXXXXXX" */
581 }
582 else
583 AF_DUMP(( " (none)\n" ));
584
585 for ( edge = edges; edge < limit; edge++ )
586 AF_DUMP(( " %5d %7.2f %5s %4s %5s"
587 " %c %7.2f %7.2f %11s\n",
588 AF_INDEX_NUM( edge, edges ),
589 (int)edge->opos / 64.0,
590 af_dir_str( (AF_Direction)edge->dir ),
591 af_print_idx( buf1, AF_INDEX_NUM( edge->link, edges ) ),
592 af_print_idx( buf2, AF_INDEX_NUM( edge->serif, edges ) ),
593
594 edge->blue_edge ? 'y' : 'n',
595 edge->opos / 64.0,
596 edge->pos / 64.0,
597 af_edge_flags_to_string( edge->flags ) ));
598 AF_DUMP(( "\n" ));
599 }
600 }
601#ifdef __cplusplus
602 }
603#endif
604
605#undef AF_DUMP
606
607#endif /* !FT_DEBUG_AUTOFIT */
608
609
610 /* Compute the direction value of a given vector. */
611
612 FT_LOCAL_DEF( AF_Direction )
613 af_direction_compute( FT_Pos dx,
614 FT_Pos dy )
615 {
616 FT_Pos ll, ss; /* long and short arm lengths */
617 AF_Direction dir; /* candidate direction */
618
619
620 if ( dy >= dx )
621 {
622 if ( dy >= -dx )
623 {
624 dir = AF_DIR_UP;
625 ll = dy;
626 ss = dx;
627 }
628 else
629 {
630 dir = AF_DIR_LEFT;
631 ll = -dx;
632 ss = dy;
633 }
634 }
635 else /* dy < dx */
636 {
637 if ( dy >= -dx )
638 {
639 dir = AF_DIR_RIGHT;
640 ll = dx;
641 ss = dy;
642 }
643 else
644 {
645 dir = AF_DIR_DOWN;
646 ll = -dy;
647 ss = dx;
648 }
649 }
650
651 /* return no direction if arm lengths do not differ enough */
652 /* (value 14 is heuristic, corresponding to approx. 4.1 degrees) */
653 /* the long arm is never negative */
654 if ( ll <= 14 * FT_ABS( ss ) )
655 dir = AF_DIR_NONE;
656
657 return dir;
658 }
659
660
661 FT_LOCAL_DEF( void )
662 af_glyph_hints_init( AF_GlyphHints hints,
663 FT_Memory memory )
664 {
665 /* no need to initialize the embedded items */
666 FT_MEM_ZERO( hints, sizeof ( *hints ) - sizeof ( hints->embedded ) );
667 hints->memory = memory;
668 }
669
670
671 FT_LOCAL_DEF( void )
672 af_glyph_hints_done( AF_GlyphHints hints )
673 {
674 FT_Memory memory;
675 int dim;
676
677
678 if ( !( hints && hints->memory ) )
679 return;
680
681 memory = hints->memory;
682
683 /*
684 * note that we don't need to free the segment and edge
685 * buffers since they are really within the hints->points array
686 */
687 for ( dim = 0; dim < AF_DIMENSION_MAX; dim++ )
688 {
689 AF_AxisHints axis = &hints->axis[dim];
690
691
692 axis->num_segments = 0;
693 axis->max_segments = 0;
694 if ( axis->segments != axis->embedded.segments )
695 FT_FREE( axis->segments );
696
697 axis->num_edges = 0;
698 axis->max_edges = 0;
699 if ( axis->edges != axis->embedded.edges )
700 FT_FREE( axis->edges );
701 }
702
703 if ( hints->contours != hints->embedded.contours )
704 FT_FREE( hints->contours );
705 hints->max_contours = 0;
706 hints->num_contours = 0;
707
708 if ( hints->points != hints->embedded.points )
709 FT_FREE( hints->points );
710 hints->max_points = 0;
711 hints->num_points = 0;
712
713 hints->memory = NULL;
714 }
715
716
717 /* Reset metrics. */
718
719 FT_LOCAL_DEF( void )
720 af_glyph_hints_rescale( AF_GlyphHints hints,
721 AF_StyleMetrics metrics )
722 {
723 hints->metrics = metrics;
724 hints->scaler_flags = metrics->scaler.flags;
725 }
726
727
728 /* Recompute all AF_Point in AF_GlyphHints from the definitions */
729 /* in a source outline. */
730
731 FT_LOCAL_DEF( FT_Error )
732 af_glyph_hints_reload( AF_GlyphHints hints,
733 FT_Outline* outline )
734 {
735 FT_Error error = FT_Err_Ok;
736 AF_Point points;
737 FT_UInt old_max, new_max;
738 FT_Fixed x_scale = hints->x_scale;
739 FT_Fixed y_scale = hints->y_scale;
740 FT_Pos x_delta = hints->x_delta;
741 FT_Pos y_delta = hints->y_delta;
742 FT_Memory memory = hints->memory;
743
744
745 hints->num_points = 0;
746 hints->num_contours = 0;
747
748 hints->axis[0].num_segments = 0;
749 hints->axis[0].num_edges = 0;
750 hints->axis[1].num_segments = 0;
751 hints->axis[1].num_edges = 0;
752
753 /* first of all, reallocate the contours array if necessary */
754 new_max = (FT_UInt)outline->n_contours;
755 old_max = (FT_UInt)hints->max_contours;
756
757 if ( new_max <= AF_CONTOURS_EMBEDDED )
758 {
759 if ( !hints->contours )
760 {
761 hints->contours = hints->embedded.contours;
762 hints->max_contours = AF_CONTOURS_EMBEDDED;
763 }
764 }
765 else if ( new_max > old_max )
766 {
767 if ( hints->contours == hints->embedded.contours )
768 hints->contours = NULL;
769
770 new_max = ( new_max + 3 ) & ~3U; /* round up to a multiple of 4 */
771
772 if ( FT_RENEW_ARRAY( hints->contours, old_max, new_max ) )
773 goto Exit;
774
775 hints->max_contours = (FT_Int)new_max;
776 }
777
778 /*
779 * then reallocate the points arrays if necessary --
780 * note that we reserve two additional point positions, used to
781 * hint metrics appropriately
782 */
783 new_max = (FT_UInt)( outline->n_points + 2 );
784 old_max = (FT_UInt)hints->max_points;
785
786 if ( new_max <= AF_POINTS_EMBEDDED )
787 {
788 if ( !hints->points )
789 {
790 hints->points = hints->embedded.points;
791 hints->max_points = AF_POINTS_EMBEDDED;
792 }
793 }
794 else if ( new_max > old_max )
795 {
796 if ( hints->points == hints->embedded.points )
797 hints->points = NULL;
798
799 new_max = ( new_max + 2 + 7 ) & ~7U; /* round up to a multiple of 8 */
800
801 if ( FT_RENEW_ARRAY( hints->points, old_max, new_max ) )
802 goto Exit;
803
804 hints->max_points = (FT_Int)new_max;
805 }
806
807 hints->num_points = outline->n_points;
808 hints->num_contours = outline->n_contours;
809
810 /* We can't rely on the value of `FT_Outline.flags' to know the fill */
811 /* direction used for a glyph, given that some fonts are broken (e.g., */
812 /* the Arphic ones). We thus recompute it each time we need to. */
813 /* */
814 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_UP;
815 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_LEFT;
816
817 if ( FT_Outline_Get_Orientation( outline ) == FT_ORIENTATION_POSTSCRIPT )
818 {
819 hints->axis[AF_DIMENSION_HORZ].major_dir = AF_DIR_DOWN;
820 hints->axis[AF_DIMENSION_VERT].major_dir = AF_DIR_RIGHT;
821 }
822
823 hints->x_scale = x_scale;
824 hints->y_scale = y_scale;
825 hints->x_delta = x_delta;
826 hints->y_delta = y_delta;
827
828 hints->xmin_delta = 0;
829 hints->xmax_delta = 0;
830
831 points = hints->points;
832 if ( hints->num_points == 0 )
833 goto Exit;
834
835 {
836 AF_Point point;
837 AF_Point point_limit = points + hints->num_points;
838
839 /* value 20 in `near_limit' is heuristic */
840 FT_UInt units_per_em = hints->metrics->scaler.face->units_per_EM;
841 FT_Int near_limit = 20 * units_per_em / 2048;
842
843
844 /* compute coordinates & Bezier flags, next and prev */
845 {
846 FT_Vector* vec = outline->points;
847 char* tag = outline->tags;
848 FT_Short endpoint = outline->contours[0];
849 AF_Point end = points + endpoint;
850 AF_Point prev = end;
851 FT_Int contour_index = 0;
852
853
854 for ( point = points; point < point_limit; point++, vec++, tag++ )
855 {
856 FT_Pos out_x, out_y;
857
858
859 point->in_dir = (FT_Char)AF_DIR_NONE;
860 point->out_dir = (FT_Char)AF_DIR_NONE;
861
862 point->fx = (FT_Short)vec->x;
863 point->fy = (FT_Short)vec->y;
864 point->ox = point->x = FT_MulFix( vec->x, x_scale ) + x_delta;
865 point->oy = point->y = FT_MulFix( vec->y, y_scale ) + y_delta;
866
867 end->fx = (FT_Short)outline->points[endpoint].x;
868 end->fy = (FT_Short)outline->points[endpoint].y;
869
870 switch ( FT_CURVE_TAG( *tag ) )
871 {
872 case FT_CURVE_TAG_CONIC:
873 point->flags = AF_FLAG_CONIC;
874 break;
875 case FT_CURVE_TAG_CUBIC:
876 point->flags = AF_FLAG_CUBIC;
877 break;
878 default:
879 point->flags = AF_FLAG_NONE;
880 }
881
882 out_x = point->fx - prev->fx;
883 out_y = point->fy - prev->fy;
884
885 if ( FT_ABS( out_x ) + FT_ABS( out_y ) < near_limit )
886 prev->flags |= AF_FLAG_NEAR;
887
888 point->prev = prev;
889 prev->next = point;
890 prev = point;
891
892 if ( point == end )
893 {
894 if ( ++contour_index < outline->n_contours )
895 {
896 endpoint = outline->contours[contour_index];
897 end = points + endpoint;
898 prev = end;
899 }
900 }
901 }
902 }
903
904 /* set up the contours array */
905 {
906 AF_Point* contour = hints->contours;
907 AF_Point* contour_limit = contour + hints->num_contours;
908 short* end = outline->contours;
909 short idx = 0;
910
911
912 for ( ; contour < contour_limit; contour++, end++ )
913 {
914 contour[0] = points + idx;
915 idx = (short)( end[0] + 1 );
916 }
917 }
918
919 {
920 /*
921 * Compute directions of `in' and `out' vectors.
922 *
923 * Note that distances between points that are very near to each
924 * other are accumulated. In other words, the auto-hinter either
925 * prepends the small vectors between near points to the first
926 * non-near vector, or the sum of small vector lengths exceeds a
927 * threshold, thus `grouping' the small vectors. All intermediate
928 * points are tagged as weak; the directions are adjusted also to
929 * be equal to the accumulated one.
930 */
931
932 FT_Int near_limit2 = 2 * near_limit - 1;
933
934 AF_Point* contour;
935 AF_Point* contour_limit = hints->contours + hints->num_contours;
936
937
938 for ( contour = hints->contours; contour < contour_limit; contour++ )
939 {
940 AF_Point first = *contour;
941 AF_Point next, prev, curr;
942
943 FT_Pos out_x, out_y;
944
945
946 /* since the first point of a contour could be part of a */
947 /* series of near points, go backwards to find the first */
948 /* non-near point and adjust `first' */
949
950 point = first;
951 prev = first->prev;
952
953 while ( prev != first )
954 {
955 out_x = point->fx - prev->fx;
956 out_y = point->fy - prev->fy;
957
958 /*
959 * We use Taxicab metrics to measure the vector length.
960 *
961 * Note that the accumulated distances so far could have the
962 * opposite direction of the distance measured here. For this
963 * reason we use `near_limit2' for the comparison to get a
964 * non-near point even in the worst case.
965 */
966 if ( FT_ABS( out_x ) + FT_ABS( out_y ) >= near_limit2 )
967 break;
968
969 point = prev;
970 prev = prev->prev;
971 }
972
973 /* adjust first point */
974 first = point;
975
976 /* now loop over all points of the contour to get */
977 /* `in' and `out' vector directions */
978
979 curr = first;
980
981 /*
982 * We abuse the `u' and `v' fields to store index deltas to the
983 * next and previous non-near point, respectively.
984 *
985 * To avoid problems with not having non-near points, we point to
986 * `first' by default as the next non-near point.
987 *
988 */
989 curr->u = (FT_Pos)( first - curr );
990 first->v = -curr->u;
991
992 out_x = 0;
993 out_y = 0;
994
995 next = first;
996 do
997 {
998 AF_Direction out_dir;
999
1000
1001 point = next;
1002 next = point->next;
1003
1004 out_x += next->fx - point->fx;
1005 out_y += next->fy - point->fy;
1006
1007 if ( FT_ABS( out_x ) + FT_ABS( out_y ) < near_limit )
1008 {
1009 next->flags |= AF_FLAG_WEAK_INTERPOLATION;
1010 continue;
1011 }
1012
1013 curr->u = (FT_Pos)( next - curr );
1014 next->v = -curr->u;
1015
1016 out_dir = af_direction_compute( out_x, out_y );
1017
1018 /* adjust directions for all points inbetween; */
1019 /* the loop also updates position of `curr' */
1020 curr->out_dir = (FT_Char)out_dir;
1021 for ( curr = curr->next; curr != next; curr = curr->next )
1022 {
1023 curr->in_dir = (FT_Char)out_dir;
1024 curr->out_dir = (FT_Char)out_dir;
1025 }
1026 next->in_dir = (FT_Char)out_dir;
1027
1028 curr->u = (FT_Pos)( first - curr );
1029 first->v = -curr->u;
1030
1031 out_x = 0;
1032 out_y = 0;
1033
1034 } while ( next != first );
1035 }
1036
1037 /*
1038 * The next step is to `simplify' an outline's topology so that we
1039 * can identify local extrema more reliably: A series of
1040 * non-horizontal or non-vertical vectors pointing into the same
1041 * quadrant are handled as a single, long vector. From a
1042 * topological point of the view, the intermediate points are of no
1043 * interest and thus tagged as weak.
1044 */
1045
1046 for ( point = points; point < point_limit; point++ )
1047 {
1048 if ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
1049 continue;
1050
1051 if ( point->in_dir == AF_DIR_NONE &&
1052 point->out_dir == AF_DIR_NONE )
1053 {
1054 /* check whether both vectors point into the same quadrant */
1055
1056 FT_Pos in_x, in_y;
1057 FT_Pos out_x, out_y;
1058
1059 AF_Point next_u = point + point->u;
1060 AF_Point prev_v = point + point->v;
1061
1062
1063 in_x = point->fx - prev_v->fx;
1064 in_y = point->fy - prev_v->fy;
1065
1066 out_x = next_u->fx - point->fx;
1067 out_y = next_u->fy - point->fy;
1068
1069 if ( ( in_x ^ out_x ) >= 0 && ( in_y ^ out_y ) >= 0 )
1070 {
1071 /* yes, so tag current point as weak */
1072 /* and update index deltas */
1073
1074 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
1075
1076 prev_v->u = (FT_Pos)( next_u - prev_v );
1077 next_u->v = -prev_v->u;
1078 }
1079 }
1080 }
1081
1082 /*
1083 * Finally, check for remaining weak points. Everything else not
1084 * collected in edges so far is then implicitly classified as strong
1085 * points.
1086 */
1087
1088 for ( point = points; point < point_limit; point++ )
1089 {
1090 if ( point->flags & AF_FLAG_WEAK_INTERPOLATION )
1091 continue;
1092
1093 if ( point->flags & AF_FLAG_CONTROL )
1094 {
1095 /* control points are always weak */
1096 Is_Weak_Point:
1097 point->flags |= AF_FLAG_WEAK_INTERPOLATION;
1098 }
1099 else if ( point->out_dir == point->in_dir )
1100 {
1101 if ( point->out_dir != AF_DIR_NONE )
1102 {
1103 /* current point lies on a horizontal or */
1104 /* vertical segment (but doesn't start or end it) */
1105 goto Is_Weak_Point;
1106 }
1107
1108 {
1109 AF_Point next_u = point + point->u;
1110 AF_Point prev_v = point + point->v;
1111
1112
1113 if ( ft_corner_is_flat( point->fx - prev_v->fx,
1114 point->fy - prev_v->fy,
1115 next_u->fx - point->fx,
1116 next_u->fy - point->fy ) )
1117 {
1118 /* either the `in' or the `out' vector is much more */
1119 /* dominant than the other one, so tag current point */
1120 /* as weak and update index deltas */
1121
1122 prev_v->u = (FT_Pos)( next_u - prev_v );
1123 next_u->v = -prev_v->u;
1124
1125 goto Is_Weak_Point;
1126 }
1127 }
1128 }
1129 else if ( point->in_dir == -point->out_dir )
1130 {
1131 /* current point forms a spike */
1132 goto Is_Weak_Point;
1133 }
1134 }
1135 }
1136 }
1137
1138 Exit:
1139 return error;
1140 }
1141
1142
1143 /* Store the hinted outline in an FT_Outline structure. */
1144
1145 FT_LOCAL_DEF( void )
1146 af_glyph_hints_save( AF_GlyphHints hints,
1147 FT_Outline* outline )
1148 {
1149 AF_Point point = hints->points;
1150 AF_Point limit = point + hints->num_points;
1151 FT_Vector* vec = outline->points;
1152 char* tag = outline->tags;
1153
1154
1155 for ( ; point < limit; point++, vec++, tag++ )
1156 {
1157 vec->x = point->x;
1158 vec->y = point->y;
1159
1160 if ( point->flags & AF_FLAG_CONIC )
1161 tag[0] = FT_CURVE_TAG_CONIC;
1162 else if ( point->flags & AF_FLAG_CUBIC )
1163 tag[0] = FT_CURVE_TAG_CUBIC;
1164 else
1165 tag[0] = FT_CURVE_TAG_ON;
1166 }
1167 }
1168
1169
1170 /****************************************************************
1171 *
1172 * EDGE POINT GRID-FITTING
1173 *
1174 ****************************************************************/
1175
1176
1177 /* Align all points of an edge to the same coordinate value, */
1178 /* either horizontally or vertically. */
1179
1180 FT_LOCAL_DEF( void )
1181 af_glyph_hints_align_edge_points( AF_GlyphHints hints,
1182 AF_Dimension dim )
1183 {
1184 AF_AxisHints axis = & hints->axis[dim];
1185 AF_Segment segments = axis->segments;
1186 AF_Segment segment_limit = segments + axis->num_segments;
1187 AF_Segment seg;
1188
1189
1190 if ( dim == AF_DIMENSION_HORZ )
1191 {
1192 for ( seg = segments; seg < segment_limit; seg++ )
1193 {
1194 AF_Edge edge = seg->edge;
1195 AF_Point point, first, last;
1196
1197
1198 if ( !edge )
1199 continue;
1200
1201 first = seg->first;
1202 last = seg->last;
1203 point = first;
1204 for (;;)
1205 {
1206 point->x = edge->pos;
1207 point->flags |= AF_FLAG_TOUCH_X;
1208
1209 if ( point == last )
1210 break;
1211
1212 point = point->next;
1213 }
1214 }
1215 }
1216 else
1217 {
1218 for ( seg = segments; seg < segment_limit; seg++ )
1219 {
1220 AF_Edge edge = seg->edge;
1221 AF_Point point, first, last;
1222
1223
1224 if ( !edge )
1225 continue;
1226
1227 first = seg->first;
1228 last = seg->last;
1229 point = first;
1230 for (;;)
1231 {
1232 point->y = edge->pos;
1233 point->flags |= AF_FLAG_TOUCH_Y;
1234
1235 if ( point == last )
1236 break;
1237
1238 point = point->next;
1239 }
1240 }
1241 }
1242 }
1243
1244
1245 /****************************************************************
1246 *
1247 * STRONG POINT INTERPOLATION
1248 *
1249 ****************************************************************/
1250
1251
1252 /* Hint the strong points -- this is equivalent to the TrueType `IP' */
1253 /* hinting instruction. */
1254
1255 FT_LOCAL_DEF( void )
1256 af_glyph_hints_align_strong_points( AF_GlyphHints hints,
1257 AF_Dimension dim )
1258 {
1259 AF_Point points = hints->points;
1260 AF_Point point_limit = points + hints->num_points;
1261 AF_AxisHints axis = &hints->axis[dim];
1262 AF_Edge edges = axis->edges;
1263 AF_Edge edge_limit = edges + axis->num_edges;
1264 FT_UInt touch_flag;
1265
1266
1267 if ( dim == AF_DIMENSION_HORZ )
1268 touch_flag = AF_FLAG_TOUCH_X;
1269 else
1270 touch_flag = AF_FLAG_TOUCH_Y;
1271
1272 if ( edges < edge_limit )
1273 {
1274 AF_Point point;
1275 AF_Edge edge;
1276
1277
1278 for ( point = points; point < point_limit; point++ )
1279 {
1280 FT_Pos u, ou, fu; /* point position */
1281 FT_Pos delta;
1282
1283
1284 if ( point->flags & touch_flag )
1285 continue;
1286
1287 /* if this point is candidate to weak interpolation, we */
1288 /* interpolate it after all strong points have been processed */
1289
1290 if ( ( point->flags & AF_FLAG_WEAK_INTERPOLATION ) )
1291 continue;
1292
1293 if ( dim == AF_DIMENSION_VERT )
1294 {
1295 u = point->fy;
1296 ou = point->oy;
1297 }
1298 else
1299 {
1300 u = point->fx;
1301 ou = point->ox;
1302 }
1303
1304 fu = u;
1305
1306 /* is the point before the first edge? */
1307 edge = edges;
1308 delta = edge->fpos - u;
1309 if ( delta >= 0 )
1310 {
1311 u = edge->pos - ( edge->opos - ou );
1312 goto Store_Point;
1313 }
1314
1315 /* is the point after the last edge? */
1316 edge = edge_limit - 1;
1317 delta = u - edge->fpos;
1318 if ( delta >= 0 )
1319 {
1320 u = edge->pos + ( ou - edge->opos );
1321 goto Store_Point;
1322 }
1323
1324 {
1325 FT_PtrDist min, max, mid;
1326 FT_Pos fpos;
1327
1328
1329 /* find enclosing edges */
1330 min = 0;
1331 max = edge_limit - edges;
1332
1333#if 1
1334 /* for a small number of edges, a linear search is better */
1335 if ( max <= 8 )
1336 {
1337 FT_PtrDist nn;
1338
1339
1340 for ( nn = 0; nn < max; nn++ )
1341 if ( edges[nn].fpos >= u )
1342 break;
1343
1344 if ( edges[nn].fpos == u )
1345 {
1346 u = edges[nn].pos;
1347 goto Store_Point;
1348 }
1349 min = nn;
1350 }
1351 else
1352#endif
1353 while ( min < max )
1354 {
1355 mid = ( max + min ) >> 1;
1356 edge = edges + mid;
1357 fpos = edge->fpos;
1358
1359 if ( u < fpos )
1360 max = mid;
1361 else if ( u > fpos )
1362 min = mid + 1;
1363 else
1364 {
1365 /* we are on the edge */
1366 u = edge->pos;
1367 goto Store_Point;
1368 }
1369 }
1370
1371 /* point is not on an edge */
1372 {
1373 AF_Edge before = edges + min - 1;
1374 AF_Edge after = edges + min + 0;
1375
1376
1377 /* assert( before && after && before != after ) */
1378 if ( before->scale == 0 )
1379 before->scale = FT_DivFix( after->pos - before->pos,
1380 after->fpos - before->fpos );
1381
1382 u = before->pos + FT_MulFix( fu - before->fpos,
1383 before->scale );
1384 }
1385 }
1386
1387 Store_Point:
1388 /* save the point position */
1389 if ( dim == AF_DIMENSION_HORZ )
1390 point->x = u;
1391 else
1392 point->y = u;
1393
1394 point->flags |= touch_flag;
1395 }
1396 }
1397 }
1398
1399
1400 /****************************************************************
1401 *
1402 * WEAK POINT INTERPOLATION
1403 *
1404 ****************************************************************/
1405
1406
1407 /* Shift the original coordinates of all points between `p1' and */
1408 /* `p2' to get hinted coordinates, using the same difference as */
1409 /* given by `ref'. */
1410
1411 static void
1412 af_iup_shift( AF_Point p1,
1413 AF_Point p2,
1414 AF_Point ref )
1415 {
1416 AF_Point p;
1417 FT_Pos delta = ref->u - ref->v;
1418
1419
1420 if ( delta == 0 )
1421 return;
1422
1423 for ( p = p1; p < ref; p++ )
1424 p->u = p->v + delta;
1425
1426 for ( p = ref + 1; p <= p2; p++ )
1427 p->u = p->v + delta;
1428 }
1429
1430
1431 /* Interpolate the original coordinates of all points between `p1' and */
1432 /* `p2' to get hinted coordinates, using `ref1' and `ref2' as the */
1433 /* reference points. The `u' and `v' members are the current and */
1434 /* original coordinate values, respectively. */
1435 /* */
1436 /* Details can be found in the TrueType bytecode specification. */
1437
1438 static void
1439 af_iup_interp( AF_Point p1,
1440 AF_Point p2,
1441 AF_Point ref1,
1442 AF_Point ref2 )
1443 {
1444 AF_Point p;
1445 FT_Pos u, v1, v2, u1, u2, d1, d2;
1446
1447
1448 if ( p1 > p2 )
1449 return;
1450
1451 if ( ref1->v > ref2->v )
1452 {
1453 p = ref1;
1454 ref1 = ref2;
1455 ref2 = p;
1456 }
1457
1458 v1 = ref1->v;
1459 v2 = ref2->v;
1460 u1 = ref1->u;
1461 u2 = ref2->u;
1462 d1 = u1 - v1;
1463 d2 = u2 - v2;
1464
1465 if ( u1 == u2 || v1 == v2 )
1466 {
1467 for ( p = p1; p <= p2; p++ )
1468 {
1469 u = p->v;
1470
1471 if ( u <= v1 )
1472 u += d1;
1473 else if ( u >= v2 )
1474 u += d2;
1475 else
1476 u = u1;
1477
1478 p->u = u;
1479 }
1480 }
1481 else
1482 {
1483 FT_Fixed scale = FT_DivFix( u2 - u1, v2 - v1 );
1484
1485
1486 for ( p = p1; p <= p2; p++ )
1487 {
1488 u = p->v;
1489
1490 if ( u <= v1 )
1491 u += d1;
1492 else if ( u >= v2 )
1493 u += d2;
1494 else
1495 u = u1 + FT_MulFix( u - v1, scale );
1496
1497 p->u = u;
1498 }
1499 }
1500 }
1501
1502
1503 /* Hint the weak points -- this is equivalent to the TrueType `IUP' */
1504 /* hinting instruction. */
1505
1506 FT_LOCAL_DEF( void )
1507 af_glyph_hints_align_weak_points( AF_GlyphHints hints,
1508 AF_Dimension dim )
1509 {
1510 AF_Point points = hints->points;
1511 AF_Point point_limit = points + hints->num_points;
1512 AF_Point* contour = hints->contours;
1513 AF_Point* contour_limit = contour + hints->num_contours;
1514 FT_UInt touch_flag;
1515 AF_Point point;
1516 AF_Point end_point;
1517 AF_Point first_point;
1518
1519
1520 /* PASS 1: Move segment points to edge positions */
1521
1522 if ( dim == AF_DIMENSION_HORZ )
1523 {
1524 touch_flag = AF_FLAG_TOUCH_X;
1525
1526 for ( point = points; point < point_limit; point++ )
1527 {
1528 point->u = point->x;
1529 point->v = point->ox;
1530 }
1531 }
1532 else
1533 {
1534 touch_flag = AF_FLAG_TOUCH_Y;
1535
1536 for ( point = points; point < point_limit; point++ )
1537 {
1538 point->u = point->y;
1539 point->v = point->oy;
1540 }
1541 }
1542
1543 for ( ; contour < contour_limit; contour++ )
1544 {
1545 AF_Point first_touched, last_touched;
1546
1547
1548 point = *contour;
1549 end_point = point->prev;
1550 first_point = point;
1551
1552 /* find first touched point */
1553 for (;;)
1554 {
1555 if ( point > end_point ) /* no touched point in contour */
1556 goto NextContour;
1557
1558 if ( point->flags & touch_flag )
1559 break;
1560
1561 point++;
1562 }
1563
1564 first_touched = point;
1565
1566 for (;;)
1567 {
1568 FT_ASSERT( point <= end_point &&
1569 ( point->flags & touch_flag ) != 0 );
1570
1571 /* skip any touched neighbours */
1572 while ( point < end_point &&
1573 ( point[1].flags & touch_flag ) != 0 )
1574 point++;
1575
1576 last_touched = point;
1577
1578 /* find the next touched point, if any */
1579 point++;
1580 for (;;)
1581 {
1582 if ( point > end_point )
1583 goto EndContour;
1584
1585 if ( ( point->flags & touch_flag ) != 0 )
1586 break;
1587
1588 point++;
1589 }
1590
1591 /* interpolate between last_touched and point */
1592 af_iup_interp( last_touched + 1, point - 1,
1593 last_touched, point );
1594 }
1595
1596 EndContour:
1597 /* special case: only one point was touched */
1598 if ( last_touched == first_touched )
1599 af_iup_shift( first_point, end_point, first_touched );
1600
1601 else /* interpolate the last part */
1602 {
1603 if ( last_touched < end_point )
1604 af_iup_interp( last_touched + 1, end_point,
1605 last_touched, first_touched );
1606
1607 if ( first_touched > points )
1608 af_iup_interp( first_point, first_touched - 1,
1609 last_touched, first_touched );
1610 }
1611
1612 NextContour:
1613 ;
1614 }
1615
1616 /* now save the interpolated values back to x/y */
1617 if ( dim == AF_DIMENSION_HORZ )
1618 {
1619 for ( point = points; point < point_limit; point++ )
1620 point->x = point->u;
1621 }
1622 else
1623 {
1624 for ( point = points; point < point_limit; point++ )
1625 point->y = point->u;
1626 }
1627 }
1628
1629
1630#ifdef AF_CONFIG_OPTION_USE_WARPER
1631
1632 /* Apply (small) warp scale and warp delta for given dimension. */
1633
1634 FT_LOCAL_DEF( void )
1635 af_glyph_hints_scale_dim( AF_GlyphHints hints,
1636 AF_Dimension dim,
1637 FT_Fixed scale,
1638 FT_Pos delta )
1639 {
1640 AF_Point points = hints->points;
1641 AF_Point points_limit = points + hints->num_points;
1642 AF_Point point;
1643
1644
1645 if ( dim == AF_DIMENSION_HORZ )
1646 {
1647 for ( point = points; point < points_limit; point++ )
1648 point->x = FT_MulFix( point->fx, scale ) + delta;
1649 }
1650 else
1651 {
1652 for ( point = points; point < points_limit; point++ )
1653 point->y = FT_MulFix( point->fy, scale ) + delta;
1654 }
1655 }
1656
1657#endif /* AF_CONFIG_OPTION_USE_WARPER */
1658
1659/* END */
1660