sdk-world v2026.11.05
PS2 SDK - world tier (copyleft-allowed, non-essential packages)
Loading...
Searching...
No Matches
pshalgo.c
1/****************************************************************************
2 *
3 * pshalgo.c
4 *
5 * PostScript hinting algorithm (body).
6 *
7 * Copyright (C) 2001-2025 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 <freetype/internal/ftobjs.h>
20#include <freetype/internal/ftdebug.h>
21#include <freetype/internal/ftcalc.h>
22#include "pshalgo.h"
23
24#include "pshnterr.h"
25
26
27#undef FT_COMPONENT
28#define FT_COMPONENT pshalgo
29
30
31#ifdef DEBUG_HINTER
32 PSH_Hint_Table ps_debug_hint_table = NULL;
33 PSH_HintFunc ps_debug_hint_func = NULL;
34 PSH_Glyph ps_debug_glyph = NULL;
35#endif
36
37
38#define COMPUTE_INFLEXS /* compute inflection points to optimize `S' */
39 /* and similar glyphs */
40
41
42 /*************************************************************************/
43 /*************************************************************************/
44 /***** *****/
45 /***** BASIC HINTS RECORDINGS *****/
46 /***** *****/
47 /*************************************************************************/
48 /*************************************************************************/
49
50 /* return true if two stem hints overlap */
51 static FT_Int
52 psh_hint_overlap( PSH_Hint hint1,
53 PSH_Hint hint2 )
54 {
55 return ADD_INT( hint1->org_pos, hint1->org_len ) >= hint2->org_pos &&
56 ADD_INT( hint2->org_pos, hint2->org_len ) >= hint1->org_pos;
57 }
58
59
60 /* destroy hints table */
61 static void
62 psh_hint_table_done( PSH_Hint_Table table,
63 FT_Memory memory )
64 {
65 FT_FREE( table->zones );
66 table->num_zones = 0;
67 table->zone = NULL;
68
69 FT_FREE( table->sort );
70 FT_FREE( table->hints );
71 table->num_hints = 0;
72 table->max_hints = 0;
73 table->sort_global = NULL;
74 }
75
76
77 /* deactivate all hints in a table */
78 static void
79 psh_hint_table_deactivate( PSH_Hint_Table table )
80 {
81 FT_UInt count = table->max_hints;
82 PSH_Hint hint = table->hints;
83
84
85 for ( ; count > 0; count--, hint++ )
86 {
87 psh_hint_deactivate( hint );
88 hint->order = -1;
89 }
90 }
91
92
93 /* internal function to record a new hint */
94 static void
95 psh_hint_table_record( PSH_Hint_Table table,
96 FT_UInt idx )
97 {
98 PSH_Hint hint = table->hints + idx;
99
100
101 if ( idx >= table->max_hints )
102 {
103 FT_TRACE0(( "psh_hint_table_record: invalid hint index %u\n", idx ));
104 return;
105 }
106
107 /* ignore active hints */
108 if ( psh_hint_is_active( hint ) )
109 return;
110
111 psh_hint_activate( hint );
112
113 /* now scan the current active hint set to check */
114 /* whether `hint' overlaps with another hint */
115 {
116 PSH_Hint* sorted = table->sort_global;
117 FT_UInt count = table->num_hints;
118 PSH_Hint hint2;
119
120
121 hint->parent = NULL;
122 for ( ; count > 0; count--, sorted++ )
123 {
124 hint2 = sorted[0];
125
126 if ( psh_hint_overlap( hint, hint2 ) )
127 {
128 hint->parent = hint2;
129 break;
130 }
131 }
132 }
133
134 if ( table->num_hints < table->max_hints )
135 table->sort_global[table->num_hints++] = hint;
136 else
137 FT_TRACE0(( "psh_hint_table_record: too many sorted hints! BUG!\n" ));
138 }
139
140
141 static void
142 psh_hint_table_record_mask( PSH_Hint_Table table,
143 PS_Mask hint_mask )
144 {
145 FT_Int mask = 0, val = 0;
146 FT_Byte* cursor = hint_mask->bytes;
147 FT_UInt idx, limit;
148
149
150 limit = hint_mask->num_bits;
151
152 for ( idx = 0; idx < limit; idx++ )
153 {
154 if ( mask == 0 )
155 {
156 val = *cursor++;
157 mask = 0x80;
158 }
159
160 if ( val & mask )
161 psh_hint_table_record( table, idx );
162
163 mask >>= 1;
164 }
165 }
166
167
168 /* create hints table */
169 static FT_Error
170 psh_hint_table_init( PSH_Hint_Table table,
171 PS_Hint_Table hints,
172 PS_Mask_Table hint_masks,
173 PS_Mask_Table counter_masks,
174 FT_Memory memory )
175 {
176 FT_UInt count;
177 FT_Error error;
178
179 FT_UNUSED( counter_masks );
180
181
182 count = hints->num_hints;
183
184 /* allocate our tables */
185 if ( FT_QNEW_ARRAY( table->sort, 2 * count ) ||
186 FT_QNEW_ARRAY( table->hints, count ) ||
187 FT_QNEW_ARRAY( table->zones, 2 * count + 1 ) )
188 goto Exit;
189
190 table->max_hints = count;
191 table->sort_global = FT_OFFSET( table->sort, count );
192 table->num_hints = 0;
193 table->num_zones = 0;
194 table->zone = NULL;
195
196 /* initialize the `table->hints' array */
197 {
198 PSH_Hint write = table->hints;
199 PS_Hint read = hints->hints;
200
201
202 for ( ; count > 0; count--, write++, read++ )
203 {
204 write->org_pos = read->pos;
205 write->org_len = read->len;
206 write->flags = read->flags;
207 }
208 }
209
210 /* we now need to determine the initial `parent' stems; first */
211 /* activate the hints that are given by the initial hint masks */
212 if ( hint_masks )
213 {
214 PS_Mask mask = hint_masks->masks;
215
216
217 count = hint_masks->num_masks;
218 table->hint_masks = hint_masks;
219
220 for ( ; count > 0; count--, mask++ )
221 psh_hint_table_record_mask( table, mask );
222 }
223
224 /* finally, do a linear parse in case some hints were left alone */
225 if ( table->num_hints != table->max_hints )
226 {
227 FT_UInt idx;
228
229
230 FT_TRACE0(( "psh_hint_table_init: missing/incorrect hint masks\n" ));
231
232 count = table->max_hints;
233 for ( idx = 0; idx < count; idx++ )
234 psh_hint_table_record( table, idx );
235 }
236
237 Exit:
238 return error;
239 }
240
241
242 static void
243 psh_hint_table_activate_mask( PSH_Hint_Table table,
244 PS_Mask hint_mask )
245 {
246 FT_Int mask = 0, val = 0;
247 FT_Byte* cursor = hint_mask->bytes;
248 FT_UInt idx, limit, count;
249
250
251 limit = hint_mask->num_bits;
252 count = 0;
253
254 psh_hint_table_deactivate( table );
255
256 for ( idx = 0; idx < limit; idx++ )
257 {
258 if ( mask == 0 )
259 {
260 val = *cursor++;
261 mask = 0x80;
262 }
263
264 if ( val & mask )
265 {
266 PSH_Hint hint = &table->hints[idx];
267
268
269 if ( !psh_hint_is_active( hint ) )
270 {
271 FT_UInt count2;
272
273#if 0
274 PSH_Hint* sort = table->sort;
275 PSH_Hint hint2;
276
277
278 for ( count2 = count; count2 > 0; count2--, sort++ )
279 {
280 hint2 = sort[0];
281 if ( psh_hint_overlap( hint, hint2 ) )
282 FT_TRACE0(( "psh_hint_table_activate_mask:"
283 " found overlapping hints\n" ))
284 }
285#else
286 count2 = 0;
287#endif
288
289 if ( count2 == 0 )
290 {
291 psh_hint_activate( hint );
292 if ( count < table->max_hints )
293 table->sort[count++] = hint;
294 else
295 FT_TRACE0(( "psh_hint_tableactivate_mask:"
296 " too many active hints\n" ));
297 }
298 }
299 }
300
301 mask >>= 1;
302 }
303 table->num_hints = count;
304
305 /* now, sort the hints; they are guaranteed to not overlap */
306 /* so we can compare their "org_pos" field directly */
307 {
308 FT_UInt i1, i2;
309 PSH_Hint hint1, hint2;
310 PSH_Hint* sort = table->sort;
311
312
313 /* a simple bubble sort will do, since in 99% of cases, the hints */
314 /* will be already sorted -- and the sort will be linear */
315 for ( i1 = 1; i1 < count; i1++ )
316 {
317 hint1 = sort[i1];
318 /* this loop stops when i2 wraps around after reaching 0 */
319 for ( i2 = i1 - 1; i2 < i1; i2-- )
320 {
321 hint2 = sort[i2];
322
323 if ( hint2->org_pos < hint1->org_pos )
324 break;
325
326 sort[i2 + 1] = hint2;
327 sort[i2] = hint1;
328 }
329 }
330 }
331 }
332
333
334 /*************************************************************************/
335 /*************************************************************************/
336 /***** *****/
337 /***** HINTS GRID-FITTING AND OPTIMIZATION *****/
338 /***** *****/
339 /*************************************************************************/
340 /*************************************************************************/
341
342#if 1
343 static FT_Pos
344 psh_dimension_quantize_len( PSH_Dimension dim,
345 FT_Pos len,
346 FT_Bool do_snapping )
347 {
348 if ( len <= 64 )
349 len = 64;
350 else
351 {
352 FT_Pos delta = len - dim->stdw.widths[0].cur;
353
354
355 if ( delta < 0 )
356 delta = -delta;
357
358 if ( delta < 40 )
359 {
360 len = dim->stdw.widths[0].cur;
361 if ( len < 48 )
362 len = 48;
363 }
364
365 if ( len < 3 * 64 )
366 {
367 delta = ( len & 63 );
368 len &= -64;
369
370 if ( delta < 10 )
371 len += delta;
372
373 else if ( delta < 32 )
374 len += 10;
375
376 else if ( delta < 54 )
377 len += 54;
378
379 else
380 len += delta;
381 }
382 else
383 len = FT_PIX_ROUND( len );
384 }
385
386 if ( do_snapping )
387 len = FT_PIX_ROUND( len );
388
389 return len;
390 }
391#endif /* 0 */
392
393
394#ifdef DEBUG_HINTER
395
396 static void
397 ps_simple_scale( PSH_Hint_Table table,
398 FT_Fixed scale,
399 FT_Fixed delta,
400 FT_Int dimension )
401 {
402 FT_UInt count;
403
404
405 for ( count = 0; count < table->max_hints; count++ )
406 {
407 PSH_Hint hint = table->hints + count;
408
409
410 hint->cur_pos = FT_MulFix( hint->org_pos, scale ) + delta;
411 hint->cur_len = FT_MulFix( hint->org_len, scale );
412
413 if ( ps_debug_hint_func )
414 ps_debug_hint_func( hint, dimension );
415 }
416 }
417
418#endif /* DEBUG_HINTER */
419
420
421 static FT_Fixed
422 psh_hint_snap_stem_side_delta( FT_Fixed pos,
423 FT_Fixed len )
424 {
425 FT_Fixed delta1 = FT_PIX_ROUND( pos ) - pos;
426 FT_Fixed delta2 = FT_PIX_ROUND( pos + len ) - pos - len;
427
428
429 if ( FT_ABS( delta1 ) <= FT_ABS( delta2 ) )
430 return delta1;
431 else
432 return delta2;
433 }
434
435
436 static void
437 psh_hint_align( PSH_Hint hint,
438 PSH_Globals globals,
439 FT_Int dimension,
440 PSH_Glyph glyph )
441 {
442 PSH_Dimension dim = &globals->dimension[dimension];
443 FT_Fixed scale = dim->scale_mult;
444 FT_Fixed delta = dim->scale_delta;
445
446
447 if ( !psh_hint_is_fitted( hint ) )
448 {
449 FT_Pos pos = FT_MulFix( hint->org_pos, scale ) + delta;
450 FT_Pos len = FT_MulFix( hint->org_len, scale );
451
452 FT_Int do_snapping;
453 FT_Pos fit_len;
454 PSH_AlignmentRec align;
455
456
457 /* ignore stem alignments when requested through the hint flags */
458 if ( ( dimension == 0 && !glyph->do_horz_hints ) ||
459 ( dimension == 1 && !glyph->do_vert_hints ) )
460 {
461 hint->cur_pos = pos;
462 hint->cur_len = len;
463
464 psh_hint_set_fitted( hint );
465 return;
466 }
467
468 /* perform stem snapping when requested - this is necessary
469 * for monochrome and LCD hinting modes only
470 */
471 do_snapping = ( dimension == 0 && glyph->do_horz_snapping ) ||
472 ( dimension == 1 && glyph->do_vert_snapping );
473
474 hint->cur_len = fit_len = len;
475
476 /* check blue zones for horizontal stems */
477 align.align = PSH_BLUE_ALIGN_NONE;
478 align.align_bot = align.align_top = 0;
479
480 if ( dimension == 1 )
481 psh_blues_snap_stem( &globals->blues,
482 ADD_INT( hint->org_pos, hint->org_len ),
483 hint->org_pos,
484 &align );
485
486 switch ( align.align )
487 {
488 case PSH_BLUE_ALIGN_TOP:
489 /* the top of the stem is aligned against a blue zone */
490 hint->cur_pos = align.align_top - fit_len;
491 break;
492
493 case PSH_BLUE_ALIGN_BOT:
494 /* the bottom of the stem is aligned against a blue zone */
495 hint->cur_pos = align.align_bot;
496 break;
497
498 case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT:
499 /* both edges of the stem are aligned against blue zones */
500 hint->cur_pos = align.align_bot;
501 hint->cur_len = align.align_top - align.align_bot;
502 break;
503
504 default:
505 {
506 PSH_Hint parent = hint->parent;
507
508
509 if ( parent )
510 {
511 FT_Pos par_org_center, par_cur_center;
512 FT_Pos cur_org_center, cur_delta;
513
514
515 /* ensure that parent is already fitted */
516 if ( !psh_hint_is_fitted( parent ) )
517 psh_hint_align( parent, globals, dimension, glyph );
518
519 /* keep original relation between hints, that is, use the */
520 /* scaled distance between the centers of the hints to */
521 /* compute the new position */
522 par_org_center = parent->org_pos + ( parent->org_len >> 1 );
523 par_cur_center = parent->cur_pos + ( parent->cur_len >> 1 );
524 cur_org_center = hint->org_pos + ( hint->org_len >> 1 );
525
526 cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );
527 pos = par_cur_center + cur_delta - ( len >> 1 );
528 }
529
530 hint->cur_pos = pos;
531 hint->cur_len = fit_len;
532
533 /* Stem adjustment tries to snap stem widths to standard
534 * ones. This is important to prevent unpleasant rounding
535 * artefacts.
536 */
537 if ( glyph->do_stem_adjust )
538 {
539 if ( len <= 64 )
540 {
541 /* the stem is less than one pixel; we will center it
542 * around the nearest pixel center
543 */
544 if ( len >= 32 )
545 {
546 /* This is a special case where we also widen the stem
547 * and align it to the pixel grid.
548 *
549 * stem_center = pos + (len/2)
550 * nearest_pixel_center = FT_ROUND(stem_center-32)+32
551 * new_pos = nearest_pixel_center-32
552 * = FT_ROUND(stem_center-32)
553 * = FT_FLOOR(stem_center-32+32)
554 * = FT_FLOOR(stem_center)
555 * new_len = 64
556 */
557 pos = FT_PIX_FLOOR( pos + ( len >> 1 ) );
558 len = 64;
559 }
560 else if ( len > 0 )
561 {
562 /* This is a very small stem; we simply align it to the
563 * pixel grid, trying to find the minimum displacement.
564 *
565 * left = pos
566 * right = pos + len
567 * left_nearest_edge = ROUND(pos)
568 * right_nearest_edge = ROUND(right)
569 *
570 * if ( ABS(left_nearest_edge - left) <=
571 * ABS(right_nearest_edge - right) )
572 * new_pos = left
573 * else
574 * new_pos = right
575 */
576 FT_Pos left_nearest = FT_PIX_ROUND( pos );
577 FT_Pos right_nearest = FT_PIX_ROUND( pos + len );
578 FT_Pos left_disp = left_nearest - pos;
579 FT_Pos right_disp = right_nearest - ( pos + len );
580
581
582 if ( left_disp < 0 )
583 left_disp = -left_disp;
584 if ( right_disp < 0 )
585 right_disp = -right_disp;
586 if ( left_disp <= right_disp )
587 pos = left_nearest;
588 else
589 pos = right_nearest;
590 }
591 else
592 {
593 /* this is a ghost stem; we simply round it */
594 pos = FT_PIX_ROUND( pos );
595 }
596 }
597 else
598 {
599 len = psh_dimension_quantize_len( dim, len, 0 );
600 }
601 }
602
603 /* now that we have a good hinted stem width, try to position */
604 /* the stem along a pixel grid integer coordinate */
605 hint->cur_pos = pos + psh_hint_snap_stem_side_delta( pos, len );
606 hint->cur_len = len;
607 }
608 }
609
610 if ( do_snapping )
611 {
612 pos = hint->cur_pos;
613 len = hint->cur_len;
614
615 if ( len < 64 )
616 len = 64;
617 else
618 len = FT_PIX_ROUND( len );
619
620 switch ( align.align )
621 {
622 case PSH_BLUE_ALIGN_TOP:
623 hint->cur_pos = align.align_top - len;
624 hint->cur_len = len;
625 break;
626
627 case PSH_BLUE_ALIGN_BOT:
628 hint->cur_len = len;
629 break;
630
631 case PSH_BLUE_ALIGN_BOT | PSH_BLUE_ALIGN_TOP:
632 /* don't touch */
633 break;
634
635
636 default:
637 hint->cur_len = len;
638 if ( len & 64 )
639 pos = FT_PIX_FLOOR( pos + ( len >> 1 ) ) + 32;
640 else
641 pos = FT_PIX_ROUND( pos + ( len >> 1 ) );
642
643 hint->cur_pos = pos - ( len >> 1 );
644 hint->cur_len = len;
645 }
646 }
647
648 psh_hint_set_fitted( hint );
649
650#ifdef DEBUG_HINTER
651 if ( ps_debug_hint_func )
652 ps_debug_hint_func( hint, dimension );
653#endif
654 }
655 }
656
657
658#if 0 /* not used for now, experimental */
659
660 /*
661 * A variant to perform "light" hinting (i.e. FT_RENDER_MODE_LIGHT)
662 * of stems
663 */
664 static void
665 psh_hint_align_light( PSH_Hint hint,
666 PSH_Globals globals,
667 FT_Int dimension,
668 PSH_Glyph glyph )
669 {
670 PSH_Dimension dim = &globals->dimension[dimension];
671 FT_Fixed scale = dim->scale_mult;
672 FT_Fixed delta = dim->scale_delta;
673
674
675 if ( !psh_hint_is_fitted( hint ) )
676 {
677 FT_Pos pos = FT_MulFix( hint->org_pos, scale ) + delta;
678 FT_Pos len = FT_MulFix( hint->org_len, scale );
679
680 FT_Pos fit_len;
681
682 PSH_AlignmentRec align;
683
684
685 /* ignore stem alignments when requested through the hint flags */
686 if ( ( dimension == 0 && !glyph->do_horz_hints ) ||
687 ( dimension == 1 && !glyph->do_vert_hints ) )
688 {
689 hint->cur_pos = pos;
690 hint->cur_len = len;
691
692 psh_hint_set_fitted( hint );
693 return;
694 }
695
696 fit_len = len;
697
698 hint->cur_len = fit_len;
699
700 /* check blue zones for horizontal stems */
701 align.align = PSH_BLUE_ALIGN_NONE;
702 align.align_bot = align.align_top = 0;
703
704 if ( dimension == 1 )
705 psh_blues_snap_stem( &globals->blues,
706 ADD_INT( hint->org_pos, hint->org_len ),
707 hint->org_pos,
708 &align );
709
710 switch ( align.align )
711 {
712 case PSH_BLUE_ALIGN_TOP:
713 /* the top of the stem is aligned against a blue zone */
714 hint->cur_pos = align.align_top - fit_len;
715 break;
716
717 case PSH_BLUE_ALIGN_BOT:
718 /* the bottom of the stem is aligned against a blue zone */
719 hint->cur_pos = align.align_bot;
720 break;
721
722 case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT:
723 /* both edges of the stem are aligned against blue zones */
724 hint->cur_pos = align.align_bot;
725 hint->cur_len = align.align_top - align.align_bot;
726 break;
727
728 default:
729 {
730 PSH_Hint parent = hint->parent;
731
732
733 if ( parent )
734 {
735 FT_Pos par_org_center, par_cur_center;
736 FT_Pos cur_org_center, cur_delta;
737
738
739 /* ensure that parent is already fitted */
740 if ( !psh_hint_is_fitted( parent ) )
741 psh_hint_align_light( parent, globals, dimension, glyph );
742
743 par_org_center = parent->org_pos + ( parent->org_len / 2 );
744 par_cur_center = parent->cur_pos + ( parent->cur_len / 2 );
745 cur_org_center = hint->org_pos + ( hint->org_len / 2 );
746
747 cur_delta = FT_MulFix( cur_org_center - par_org_center, scale );
748 pos = par_cur_center + cur_delta - ( len >> 1 );
749 }
750
751 /* Stems less than one pixel wide are easy -- we want to
752 * make them as dark as possible, so they must fall within
753 * one pixel. If the stem is split between two pixels
754 * then snap the edge that is nearer to the pixel boundary
755 * to the pixel boundary.
756 */
757 if ( len <= 64 )
758 {
759 if ( ( pos + len + 63 ) / 64 != pos / 64 + 1 )
760 pos += psh_hint_snap_stem_side_delta ( pos, len );
761 }
762
763 /* Position stems other to minimize the amount of mid-grays.
764 * There are, in general, two positions that do this,
765 * illustrated as A) and B) below.
766 *
767 * + + + +
768 *
769 * A) |--------------------------------|
770 * B) |--------------------------------|
771 * C) |--------------------------------|
772 *
773 * Position A) (split the excess stem equally) should be better
774 * for stems of width N + f where f < 0.5.
775 *
776 * Position B) (split the deficiency equally) should be better
777 * for stems of width N + f where f > 0.5.
778 *
779 * It turns out though that minimizing the total number of lit
780 * pixels is also important, so position C), with one edge
781 * aligned with a pixel boundary is actually preferable
782 * to A). There are also more possible positions for C) than
783 * for A) or B), so it involves less distortion of the overall
784 * character shape.
785 */
786 else /* len > 64 */
787 {
788 FT_Fixed frac_len = len & 63;
789 FT_Fixed center = pos + ( len >> 1 );
790 FT_Fixed delta_a, delta_b;
791
792
793 if ( ( len / 64 ) & 1 )
794 {
795 delta_a = FT_PIX_FLOOR( center ) + 32 - center;
796 delta_b = FT_PIX_ROUND( center ) - center;
797 }
798 else
799 {
800 delta_a = FT_PIX_ROUND( center ) - center;
801 delta_b = FT_PIX_FLOOR( center ) + 32 - center;
802 }
803
804 /* We choose between B) and C) above based on the amount
805 * of fractional stem width; for small amounts, choose
806 * C) always, for large amounts, B) always, and inbetween,
807 * pick whichever one involves less stem movement.
808 */
809 if ( frac_len < 32 )
810 {
811 pos += psh_hint_snap_stem_side_delta ( pos, len );
812 }
813 else if ( frac_len < 48 )
814 {
815 FT_Fixed side_delta = psh_hint_snap_stem_side_delta ( pos,
816 len );
817
818 if ( FT_ABS( side_delta ) < FT_ABS( delta_b ) )
819 pos += side_delta;
820 else
821 pos += delta_b;
822 }
823 else
824 {
825 pos += delta_b;
826 }
827 }
828
829 hint->cur_pos = pos;
830 }
831 } /* switch */
832
833 psh_hint_set_fitted( hint );
834
835#ifdef DEBUG_HINTER
836 if ( ps_debug_hint_func )
837 ps_debug_hint_func( hint, dimension );
838#endif
839 }
840 }
841
842#endif /* 0 */
843
844
845 static void
846 psh_hint_table_align_hints( PSH_Hint_Table table,
847 PSH_Globals globals,
848 FT_Int dimension,
849 PSH_Glyph glyph )
850 {
851 PSH_Hint hint;
852 FT_UInt count;
853
854#ifdef DEBUG_HINTER
855
856 PSH_Dimension dim = &globals->dimension[dimension];
857 FT_Fixed scale = dim->scale_mult;
858 FT_Fixed delta = dim->scale_delta;
859
860
861 if ( ps_debug_no_vert_hints && dimension == 0 )
862 {
863 ps_simple_scale( table, scale, delta, dimension );
864 return;
865 }
866
867 if ( ps_debug_no_horz_hints && dimension == 1 )
868 {
869 ps_simple_scale( table, scale, delta, dimension );
870 return;
871 }
872
873#endif /* DEBUG_HINTER */
874
875 hint = table->hints;
876 count = table->max_hints;
877
878 for ( ; count > 0; count--, hint++ )
879 psh_hint_align( hint, globals, dimension, glyph );
880 }
881
882
883 /*************************************************************************/
884 /*************************************************************************/
885 /***** *****/
886 /***** POINTS INTERPOLATION ROUTINES *****/
887 /***** *****/
888 /*************************************************************************/
889 /*************************************************************************/
890
891#define xxDEBUG_ZONES
892
893
894#ifdef DEBUG_ZONES
895
896#include FT_CONFIG_STANDARD_LIBRARY_H
897
898 static void
899 psh_print_zone( PSH_Zone zone )
900 {
901 printf( "zone [scale,delta,min,max] = [%.5f,%.2f,%d,%d]\n",
902 zone->scale / 65536.0,
903 zone->delta / 64.0,
904 zone->min,
905 zone->max );
906 }
907
908#endif /* DEBUG_ZONES */
909
910
911 /*************************************************************************/
912 /*************************************************************************/
913 /***** *****/
914 /***** HINTER GLYPH MANAGEMENT *****/
915 /***** *****/
916 /*************************************************************************/
917 /*************************************************************************/
918
919#define psh_corner_is_flat ft_corner_is_flat
920#define psh_corner_orientation ft_corner_orientation
921
922
923#ifdef COMPUTE_INFLEXS
924
925 /* compute all inflex points in a given glyph */
926 static void
927 psh_glyph_compute_inflections( PSH_Glyph glyph )
928 {
929 FT_UInt n;
930
931
932 for ( n = 0; n < glyph->num_contours; n++ )
933 {
934 PSH_Point first, start, end, before, after;
935 FT_Pos in_x, in_y, out_x, out_y;
936 FT_Int orient_prev, orient_cur;
937 FT_Int finished = 0;
938
939
940 /* we need at least 4 points to create an inflection point */
941 if ( glyph->contours[n].count < 4 )
942 continue;
943
944 /* compute first segment in contour */
945 first = glyph->contours[n].start;
946
947 start = end = first;
948 do
949 {
950 end = end->next;
951 if ( end == first )
952 goto Skip;
953
954 in_x = end->org_u - start->org_u;
955 in_y = end->org_v - start->org_v;
956
957 } while ( in_x == 0 && in_y == 0 );
958
959 /* extend the segment start whenever possible */
960 before = start;
961 do
962 {
963 do
964 {
965 start = before;
966 before = before->prev;
967 if ( before == first )
968 goto Skip;
969
970 out_x = start->org_u - before->org_u;
971 out_y = start->org_v - before->org_v;
972
973 } while ( out_x == 0 && out_y == 0 );
974
975 orient_prev = psh_corner_orientation( in_x, in_y, out_x, out_y );
976
977 } while ( orient_prev == 0 );
978
979 first = start;
980 in_x = out_x;
981 in_y = out_y;
982
983 /* now, process all segments in the contour */
984 do
985 {
986 /* first, extend current segment's end whenever possible */
987 after = end;
988 do
989 {
990 do
991 {
992 end = after;
993 after = after->next;
994 if ( after == first )
995 finished = 1;
996
997 out_x = after->org_u - end->org_u;
998 out_y = after->org_v - end->org_v;
999
1000 } while ( out_x == 0 && out_y == 0 );
1001
1002 orient_cur = psh_corner_orientation( in_x, in_y, out_x, out_y );
1003
1004 } while ( orient_cur == 0 );
1005
1006 if ( ( orient_cur ^ orient_prev ) < 0 )
1007 {
1008 do
1009 {
1010 psh_point_set_inflex( start );
1011 start = start->next;
1012 }
1013 while ( start != end );
1014
1015 psh_point_set_inflex( start );
1016 }
1017
1018 start = end;
1019 end = after;
1020 orient_prev = orient_cur;
1021 in_x = out_x;
1022 in_y = out_y;
1023
1024 } while ( !finished );
1025
1026 Skip:
1027 ;
1028 }
1029 }
1030
1031#endif /* COMPUTE_INFLEXS */
1032
1033
1034 static void
1035 psh_glyph_done( PSH_Glyph glyph )
1036 {
1037 FT_Memory memory = glyph->memory;
1038
1039
1040 psh_hint_table_done( &glyph->hint_tables[1], memory );
1041 psh_hint_table_done( &glyph->hint_tables[0], memory );
1042
1043 FT_FREE( glyph->points );
1044 FT_FREE( glyph->contours );
1045
1046 glyph->num_points = 0;
1047 glyph->num_contours = 0;
1048
1049 glyph->memory = NULL;
1050 }
1051
1052
1053 static PSH_Dir
1054 psh_compute_dir( FT_Pos dx,
1055 FT_Pos dy )
1056 {
1057 FT_Pos ax, ay;
1058 PSH_Dir result = PSH_DIR_NONE;
1059
1060
1061 ax = FT_ABS( dx );
1062 ay = FT_ABS( dy );
1063
1064 if ( ay * 12 < ax )
1065 {
1066 /* |dy| <<< |dx| means a near-horizontal segment */
1067 result = ( dx >= 0 ) ? PSH_DIR_RIGHT : PSH_DIR_LEFT;
1068 }
1069 else if ( ax * 12 < ay )
1070 {
1071 /* |dx| <<< |dy| means a near-vertical segment */
1072 result = ( dy >= 0 ) ? PSH_DIR_UP : PSH_DIR_DOWN;
1073 }
1074
1075 return result;
1076 }
1077
1078
1079 /* load outline point coordinates into hinter glyph */
1080 static void
1081 psh_glyph_load_points( PSH_Glyph glyph,
1082 FT_Int dimension )
1083 {
1084 FT_Vector* vec = glyph->outline->points;
1085 PSH_Point point = glyph->points;
1086 FT_UInt count = glyph->num_points;
1087
1088
1089 for ( ; count > 0; count--, point++, vec++ )
1090 {
1091 point->flags2 = 0;
1092 point->hint = NULL;
1093 if ( dimension == 0 )
1094 {
1095 point->org_u = vec->x;
1096 point->org_v = vec->y;
1097 }
1098 else
1099 {
1100 point->org_u = vec->y;
1101 point->org_v = vec->x;
1102 }
1103
1104#ifdef DEBUG_HINTER
1105 point->org_x = vec->x;
1106 point->org_y = vec->y;
1107#endif
1108
1109 }
1110 }
1111
1112
1113 /* save hinted point coordinates back to outline */
1114 static void
1115 psh_glyph_save_points( PSH_Glyph glyph,
1116 FT_Int dimension )
1117 {
1118 FT_UInt n;
1119 PSH_Point point = glyph->points;
1120 FT_Vector* vec = glyph->outline->points;
1121 FT_Byte* tags = glyph->outline->tags;
1122
1123
1124 for ( n = 0; n < glyph->num_points; n++ )
1125 {
1126 if ( dimension == 0 )
1127 vec[n].x = point->cur_u;
1128 else
1129 vec[n].y = point->cur_u;
1130
1131 if ( psh_point_is_strong( point ) )
1132 tags[n] |= (char)( ( dimension == 0 ) ? 32 : 64 );
1133
1134#ifdef DEBUG_HINTER
1135
1136 if ( dimension == 0 )
1137 {
1138 point->cur_x = point->cur_u;
1139 point->flags_x = point->flags2 | point->flags;
1140 }
1141 else
1142 {
1143 point->cur_y = point->cur_u;
1144 point->flags_y = point->flags2 | point->flags;
1145 }
1146
1147#endif
1148
1149 point++;
1150 }
1151 }
1152
1153
1154 static FT_Error
1155 psh_glyph_init( PSH_Glyph glyph,
1156 FT_Outline* outline,
1157 PS_Hints ps_hints,
1158 PSH_Globals globals )
1159 {
1160 FT_Error error;
1161 FT_Memory memory;
1162
1163
1164 /* clear all fields */
1165 FT_ZERO( glyph );
1166
1167 memory = glyph->memory = globals->memory;
1168
1169 /* allocate and setup points + contours arrays */
1170 if ( FT_QNEW_ARRAY( glyph->points, outline->n_points ) ||
1171 FT_QNEW_ARRAY( glyph->contours, outline->n_contours ) )
1172 goto Exit;
1173
1174 glyph->num_points = outline->n_points;
1175 glyph->num_contours = outline->n_contours;
1176
1177 {
1178 FT_UInt first = 0, next, n;
1179 PSH_Point points = glyph->points;
1180 PSH_Contour contour = glyph->contours;
1181
1182
1183 for ( n = 0; n < glyph->num_contours; n++ )
1184 {
1185 FT_UInt count;
1186 PSH_Point point;
1187
1188
1189 next = outline->contours[n] + 1;
1190 count = next - first;
1191
1192 contour->start = points + first;
1193 contour->count = count;
1194
1195 if ( count > 0 )
1196 {
1197 point = points + first;
1198
1199 point->prev = points + next - 1;
1200 point->contour = contour;
1201
1202 for ( ; count > 1; count-- )
1203 {
1204 point[0].next = point + 1;
1205 point[1].prev = point;
1206 point++;
1207 point->contour = contour;
1208 }
1209 point->next = points + first;
1210 }
1211
1212 contour++;
1213 first = next;
1214 }
1215 }
1216
1217 {
1218 PSH_Point points = glyph->points;
1219 PSH_Point point = points;
1220 FT_Vector* vec = outline->points;
1221 FT_UInt n;
1222
1223
1224 for ( n = 0; n < glyph->num_points; n++, point++ )
1225 {
1226 FT_Int n_prev = (FT_Int)( point->prev - points );
1227 FT_Int n_next = (FT_Int)( point->next - points );
1228 FT_Pos dxi, dyi, dxo, dyo;
1229
1230
1231 point->flags = 0;
1232 if ( !( outline->tags[n] & FT_CURVE_TAG_ON ) )
1233 psh_point_set_off( point );
1234
1235 dxi = vec[n].x - vec[n_prev].x;
1236 dyi = vec[n].y - vec[n_prev].y;
1237
1238 point->dir_in = psh_compute_dir( dxi, dyi );
1239
1240 dxo = vec[n_next].x - vec[n].x;
1241 dyo = vec[n_next].y - vec[n].y;
1242
1243 point->dir_out = psh_compute_dir( dxo, dyo );
1244
1245 /* detect smooth points */
1246 if ( psh_point_is_off( point ) )
1247 psh_point_set_smooth( point );
1248
1249 else if ( point->dir_in == point->dir_out )
1250 {
1251 if ( point->dir_out != PSH_DIR_NONE ||
1252 psh_corner_is_flat( dxi, dyi, dxo, dyo ) )
1253 psh_point_set_smooth( point );
1254 }
1255 }
1256 }
1257
1258 glyph->outline = outline;
1259 glyph->globals = globals;
1260
1261#ifdef COMPUTE_INFLEXS
1262 psh_glyph_load_points( glyph, 0 );
1263 psh_glyph_compute_inflections( glyph );
1264#endif /* COMPUTE_INFLEXS */
1265
1266 /* now deal with hints tables */
1267 error = psh_hint_table_init( &glyph->hint_tables [0],
1268 &ps_hints->dimension[0].hints,
1269 &ps_hints->dimension[0].masks,
1270 &ps_hints->dimension[0].counters,
1271 memory );
1272 if ( error )
1273 goto Exit;
1274
1275 error = psh_hint_table_init( &glyph->hint_tables [1],
1276 &ps_hints->dimension[1].hints,
1277 &ps_hints->dimension[1].masks,
1278 &ps_hints->dimension[1].counters,
1279 memory );
1280 if ( error )
1281 goto Exit;
1282
1283 Exit:
1284 return error;
1285 }
1286
1287
1288 /* compute all extrema in a glyph for a given dimension */
1289 static void
1290 psh_glyph_compute_extrema( PSH_Glyph glyph )
1291 {
1292 FT_UInt n;
1293
1294
1295 /* first of all, compute all local extrema */
1296 for ( n = 0; n < glyph->num_contours; n++ )
1297 {
1298 PSH_Point first = glyph->contours[n].start;
1299 PSH_Point point, before, after;
1300
1301
1302 if ( glyph->contours[n].count == 0 )
1303 continue;
1304
1305 point = first;
1306 before = point;
1307
1308 do
1309 {
1310 before = before->prev;
1311 if ( before == first )
1312 goto Skip;
1313
1314 } while ( before->org_u == point->org_u );
1315
1316 first = point = before->next;
1317
1318 for (;;)
1319 {
1320 after = point;
1321 do
1322 {
1323 after = after->next;
1324 if ( after == first )
1325 goto Next;
1326
1327 } while ( after->org_u == point->org_u );
1328
1329 if ( before->org_u < point->org_u )
1330 {
1331 if ( after->org_u < point->org_u )
1332 {
1333 /* local maximum */
1334 goto Extremum;
1335 }
1336 }
1337 else /* before->org_u > point->org_u */
1338 {
1339 if ( after->org_u > point->org_u )
1340 {
1341 /* local minimum */
1342 Extremum:
1343 do
1344 {
1345 psh_point_set_extremum( point );
1346 point = point->next;
1347
1348 } while ( point != after );
1349 }
1350 }
1351
1352 before = after->prev;
1353 point = after;
1354
1355 } /* for */
1356
1357 Next:
1358 ;
1359 }
1360
1361 /* for each extremum, determine its direction along the */
1362 /* orthogonal axis */
1363 for ( n = 0; n < glyph->num_points; n++ )
1364 {
1365 PSH_Point point, before, after;
1366
1367
1368 point = &glyph->points[n];
1369 before = point;
1370 after = point;
1371
1372 if ( psh_point_is_extremum( point ) )
1373 {
1374 do
1375 {
1376 before = before->prev;
1377 if ( before == point )
1378 goto Skip;
1379
1380 } while ( before->org_v == point->org_v );
1381
1382 do
1383 {
1384 after = after->next;
1385 if ( after == point )
1386 goto Skip;
1387
1388 } while ( after->org_v == point->org_v );
1389 }
1390
1391 if ( before->org_v < point->org_v &&
1392 after->org_v > point->org_v )
1393 {
1394 psh_point_set_positive( point );
1395 }
1396 else if ( before->org_v > point->org_v &&
1397 after->org_v < point->org_v )
1398 {
1399 psh_point_set_negative( point );
1400 }
1401
1402 Skip:
1403 ;
1404 }
1405 }
1406
1407
1408 /* the min and max are based on contour orientation and fill rule */
1409 static void
1410 psh_hint_table_find_strong_points( PSH_Hint_Table table,
1411 PSH_Point point,
1412 FT_UInt count,
1413 FT_Int threshold,
1414 PSH_Dir major_dir )
1415 {
1416 PSH_Hint* sort = table->sort;
1417 FT_UInt num_hints = table->num_hints;
1418
1419
1420 for ( ; count > 0; count--, point++ )
1421 {
1422 PSH_Dir point_dir;
1423 FT_Pos org_u = point->org_u;
1424
1425
1426 if ( psh_point_is_strong( point ) )
1427 continue;
1428
1429 point_dir =
1430 (PSH_Dir)( ( point->dir_in | point->dir_out ) & major_dir );
1431
1432 if ( point_dir & ( PSH_DIR_DOWN | PSH_DIR_RIGHT ) )
1433 {
1434 FT_UInt nn;
1435
1436
1437 for ( nn = 0; nn < num_hints; nn++ )
1438 {
1439 PSH_Hint hint = sort[nn];
1440 FT_Pos d = org_u - hint->org_pos;
1441
1442
1443 if ( d < threshold && -d < threshold )
1444 {
1445 psh_point_set_strong( point );
1446 point->flags2 |= PSH_POINT_EDGE_MIN;
1447 point->hint = hint;
1448 break;
1449 }
1450 }
1451 }
1452 else if ( point_dir & ( PSH_DIR_UP | PSH_DIR_LEFT ) )
1453 {
1454 FT_UInt nn;
1455
1456
1457 for ( nn = 0; nn < num_hints; nn++ )
1458 {
1459 PSH_Hint hint = sort[nn];
1460 FT_Pos d = org_u - hint->org_pos - hint->org_len;
1461
1462
1463 if ( d < threshold && -d < threshold )
1464 {
1465 psh_point_set_strong( point );
1466 point->flags2 |= PSH_POINT_EDGE_MAX;
1467 point->hint = hint;
1468 break;
1469 }
1470 }
1471 }
1472
1473#if 1
1474 else if ( psh_point_is_extremum( point ) )
1475 {
1476 /* treat extrema as special cases for stem edge alignment */
1477 FT_UInt nn, min_flag, max_flag;
1478
1479
1480 if ( major_dir == PSH_DIR_HORIZONTAL )
1481 {
1482 min_flag = PSH_POINT_POSITIVE;
1483 max_flag = PSH_POINT_NEGATIVE;
1484 }
1485 else
1486 {
1487 min_flag = PSH_POINT_NEGATIVE;
1488 max_flag = PSH_POINT_POSITIVE;
1489 }
1490
1491 if ( point->flags2 & min_flag )
1492 {
1493 for ( nn = 0; nn < num_hints; nn++ )
1494 {
1495 PSH_Hint hint = sort[nn];
1496 FT_Pos d = org_u - hint->org_pos;
1497
1498
1499 if ( d < threshold && -d < threshold )
1500 {
1501 point->flags2 |= PSH_POINT_EDGE_MIN;
1502 point->hint = hint;
1503 psh_point_set_strong( point );
1504 break;
1505 }
1506 }
1507 }
1508 else if ( point->flags2 & max_flag )
1509 {
1510 for ( nn = 0; nn < num_hints; nn++ )
1511 {
1512 PSH_Hint hint = sort[nn];
1513 FT_Pos d = org_u - hint->org_pos - hint->org_len;
1514
1515
1516 if ( d < threshold && -d < threshold )
1517 {
1518 point->flags2 |= PSH_POINT_EDGE_MAX;
1519 point->hint = hint;
1520 psh_point_set_strong( point );
1521 break;
1522 }
1523 }
1524 }
1525
1526 if ( !point->hint )
1527 {
1528 for ( nn = 0; nn < num_hints; nn++ )
1529 {
1530 PSH_Hint hint = sort[nn];
1531
1532
1533 if ( org_u >= hint->org_pos &&
1534 org_u <= ADD_INT( hint->org_pos, hint->org_len ) )
1535 {
1536 point->hint = hint;
1537 break;
1538 }
1539 }
1540 }
1541 }
1542
1543#endif /* 1 */
1544 }
1545 }
1546
1547
1548 /* the accepted shift for strong points in fractional pixels */
1549#define PSH_STRONG_THRESHOLD 32
1550
1551 /* the maximum shift value in font units tuned to distinguish */
1552 /* between stems and serifs in URW+ font collection */
1553#define PSH_STRONG_THRESHOLD_MAXIMUM 12
1554
1555
1556 /* find strong points in a glyph */
1557 static void
1558 psh_glyph_find_strong_points( PSH_Glyph glyph,
1559 FT_Int dimension )
1560 {
1561 /* a point is `strong' if it is located on a stem edge and */
1562 /* has an `in' or `out' tangent parallel to the hint's direction */
1563
1564 PSH_Hint_Table table = &glyph->hint_tables[dimension];
1565 PS_Mask mask = table->hint_masks->masks;
1566 FT_UInt num_masks = table->hint_masks->num_masks;
1567 FT_UInt first = 0;
1568 PSH_Dir major_dir = ( dimension == 0 ) ? PSH_DIR_VERTICAL
1569 : PSH_DIR_HORIZONTAL;
1570 PSH_Dimension dim = &glyph->globals->dimension[dimension];
1571 FT_Fixed scale = dim->scale_mult;
1572 FT_Int threshold;
1573
1574
1575 threshold = (FT_Int)FT_DivFix( PSH_STRONG_THRESHOLD, scale );
1576 if ( threshold > PSH_STRONG_THRESHOLD_MAXIMUM )
1577 threshold = PSH_STRONG_THRESHOLD_MAXIMUM;
1578
1579 /* process secondary hints to `selected' points */
1580 if ( num_masks > 1 && glyph->num_points > 0 )
1581 {
1582 /* the `endchar' op can reduce the number of points */
1583 first = mask->end_point > glyph->num_points
1584 ? glyph->num_points
1585 : mask->end_point;
1586 mask++;
1587 for ( ; num_masks > 1; num_masks--, mask++ )
1588 {
1589 FT_UInt next = FT_MIN( mask->end_point, glyph->num_points );
1590
1591
1592 if ( next > first )
1593 {
1594 FT_UInt count = next - first;
1595 PSH_Point point = glyph->points + first;
1596
1597
1598 psh_hint_table_activate_mask( table, mask );
1599
1600 psh_hint_table_find_strong_points( table, point, count,
1601 threshold, major_dir );
1602 }
1603 first = next;
1604 }
1605 }
1606
1607 /* process primary hints for all points */
1608 if ( num_masks == 1 )
1609 {
1610 FT_UInt count = glyph->num_points;
1611 PSH_Point point = glyph->points;
1612
1613
1614 psh_hint_table_activate_mask( table, table->hint_masks->masks );
1615
1616 psh_hint_table_find_strong_points( table, point, count,
1617 threshold, major_dir );
1618 }
1619
1620 /* now, certain points may have been attached to a hint and */
1621 /* not marked as strong; update their flags then */
1622 {
1623 FT_UInt count = glyph->num_points;
1624 PSH_Point point = glyph->points;
1625
1626
1627 for ( ; count > 0; count--, point++ )
1628 if ( point->hint && !psh_point_is_strong( point ) )
1629 psh_point_set_strong( point );
1630 }
1631 }
1632
1633
1634 /* find points in a glyph which are in a blue zone and have `in' or */
1635 /* `out' tangents parallel to the horizontal axis */
1636 static void
1637 psh_glyph_find_blue_points( PSH_Blues blues,
1638 PSH_Glyph glyph )
1639 {
1640 PSH_Blue_Table table;
1641 PSH_Blue_Zone zone;
1642 FT_UInt glyph_count = glyph->num_points;
1643 FT_UInt blue_count;
1644 PSH_Point point = glyph->points;
1645
1646
1647 for ( ; glyph_count > 0; glyph_count--, point++ )
1648 {
1649 FT_Pos y;
1650
1651
1652 /* check tangents */
1653 if ( !( point->dir_in & PSH_DIR_HORIZONTAL ) &&
1654 !( point->dir_out & PSH_DIR_HORIZONTAL ) )
1655 continue;
1656
1657 /* skip strong points */
1658 if ( psh_point_is_strong( point ) )
1659 continue;
1660
1661 y = point->org_u;
1662
1663 /* look up top zones */
1664 table = &blues->normal_top;
1665 blue_count = table->count;
1666 zone = table->zones;
1667
1668 for ( ; blue_count > 0; blue_count--, zone++ )
1669 {
1670 FT_Pos delta = y - zone->org_bottom;
1671
1672
1673 if ( delta < -blues->blue_fuzz )
1674 break;
1675
1676 if ( y <= zone->org_top + blues->blue_fuzz )
1677 if ( blues->no_overshoots || delta <= blues->blue_threshold )
1678 {
1679 point->cur_u = zone->cur_bottom;
1680 psh_point_set_strong( point );
1681 psh_point_set_fitted( point );
1682 }
1683 }
1684
1685 /* look up bottom zones */
1686 table = &blues->normal_bottom;
1687 blue_count = table->count;
1688 zone = table->zones + blue_count - 1;
1689
1690 for ( ; blue_count > 0; blue_count--, zone-- )
1691 {
1692 FT_Pos delta = zone->org_top - y;
1693
1694
1695 if ( delta < -blues->blue_fuzz )
1696 break;
1697
1698 if ( y >= zone->org_bottom - blues->blue_fuzz )
1699 if ( blues->no_overshoots || delta < blues->blue_threshold )
1700 {
1701 point->cur_u = zone->cur_top;
1702 psh_point_set_strong( point );
1703 psh_point_set_fitted( point );
1704 }
1705 }
1706 }
1707 }
1708
1709
1710 /* interpolate strong points with the help of hinted coordinates */
1711 static void
1712 psh_glyph_interpolate_strong_points( PSH_Glyph glyph,
1713 FT_Int dimension )
1714 {
1715 PSH_Dimension dim = &glyph->globals->dimension[dimension];
1716 FT_Fixed scale = dim->scale_mult;
1717
1718 FT_UInt count = glyph->num_points;
1719 PSH_Point point = glyph->points;
1720
1721
1722 for ( ; count > 0; count--, point++ )
1723 {
1724 PSH_Hint hint = point->hint;
1725
1726
1727 if ( hint )
1728 {
1729 FT_Pos delta;
1730
1731
1732 if ( psh_point_is_edge_min( point ) )
1733 point->cur_u = hint->cur_pos;
1734
1735 else if ( psh_point_is_edge_max( point ) )
1736 point->cur_u = hint->cur_pos + hint->cur_len;
1737
1738 else
1739 {
1740 delta = point->org_u - hint->org_pos;
1741
1742 if ( delta <= 0 )
1743 point->cur_u = hint->cur_pos + FT_MulFix( delta, scale );
1744
1745 else if ( delta >= hint->org_len )
1746 point->cur_u = hint->cur_pos + hint->cur_len +
1747 FT_MulFix( delta - hint->org_len, scale );
1748
1749 else /* hint->org_len > 0 */
1750 point->cur_u = hint->cur_pos +
1751 FT_MulDiv( delta, hint->cur_len,
1752 hint->org_len );
1753 }
1754 psh_point_set_fitted( point );
1755 }
1756 }
1757 }
1758
1759
1760#define PSH_MAX_STRONG_INTERNAL 16
1761
1762 static void
1763 psh_glyph_interpolate_normal_points( PSH_Glyph glyph,
1764 FT_Int dimension )
1765 {
1766
1767#if 1
1768 /* first technique: a point is strong if it is a local extremum */
1769
1770 PSH_Dimension dim = &glyph->globals->dimension[dimension];
1771 FT_Fixed scale = dim->scale_mult;
1772 FT_Memory memory = glyph->memory;
1773
1774 PSH_Point* strongs = NULL;
1775 PSH_Point strongs_0[PSH_MAX_STRONG_INTERNAL];
1776 FT_UInt num_strongs = 0;
1777
1778 PSH_Point points = glyph->points;
1779 PSH_Point points_end = points + glyph->num_points;
1780 PSH_Point point;
1781
1782
1783 /* first count the number of strong points */
1784 for ( point = points; point < points_end; point++ )
1785 {
1786 if ( psh_point_is_strong( point ) )
1787 num_strongs++;
1788 }
1789
1790 if ( num_strongs == 0 ) /* nothing to do here */
1791 return;
1792
1793 /* allocate an array to store a list of points, */
1794 /* stored in increasing org_u order */
1795 if ( num_strongs <= PSH_MAX_STRONG_INTERNAL )
1796 strongs = strongs_0;
1797 else
1798 {
1799 FT_Error error;
1800
1801
1802 if ( FT_QNEW_ARRAY( strongs, num_strongs ) )
1803 return;
1804 }
1805
1806 num_strongs = 0;
1807 for ( point = points; point < points_end; point++ )
1808 {
1809 PSH_Point* insert;
1810
1811
1812 if ( !psh_point_is_strong( point ) )
1813 continue;
1814
1815 for ( insert = strongs + num_strongs; insert > strongs; insert-- )
1816 {
1817 if ( insert[-1]->org_u <= point->org_u )
1818 break;
1819
1820 insert[0] = insert[-1];
1821 }
1822 insert[0] = point;
1823 num_strongs++;
1824 }
1825
1826 /* now try to interpolate all normal points */
1827 for ( point = points; point < points_end; point++ )
1828 {
1829 if ( psh_point_is_strong( point ) )
1830 continue;
1831
1832 /* sometimes, some local extrema are smooth points */
1833 if ( psh_point_is_smooth( point ) )
1834 {
1835 if ( point->dir_in == PSH_DIR_NONE ||
1836 point->dir_in != point->dir_out )
1837 continue;
1838
1839 if ( !psh_point_is_extremum( point ) &&
1840 !psh_point_is_inflex( point ) )
1841 continue;
1842
1843 point->flags &= ~PSH_POINT_SMOOTH;
1844 }
1845
1846 /* find best enclosing point coordinates then interpolate */
1847 {
1848 PSH_Point before, after;
1849 FT_UInt nn;
1850
1851
1852 for ( nn = 0; nn < num_strongs; nn++ )
1853 if ( strongs[nn]->org_u > point->org_u )
1854 break;
1855
1856 if ( nn == 0 ) /* point before the first strong point */
1857 {
1858 after = strongs[0];
1859
1860 point->cur_u = after->cur_u +
1861 FT_MulFix( point->org_u - after->org_u,
1862 scale );
1863 }
1864 else
1865 {
1866 before = strongs[nn - 1];
1867
1868 for ( nn = num_strongs; nn > 0; nn-- )
1869 if ( strongs[nn - 1]->org_u < point->org_u )
1870 break;
1871
1872 if ( nn == num_strongs ) /* point is after last strong point */
1873 {
1874 before = strongs[nn - 1];
1875
1876 point->cur_u = before->cur_u +
1877 FT_MulFix( point->org_u - before->org_u,
1878 scale );
1879 }
1880 else
1881 {
1882 FT_Pos u;
1883
1884
1885 after = strongs[nn];
1886
1887 /* now interpolate point between before and after */
1888 u = point->org_u;
1889
1890 if ( u == before->org_u )
1891 point->cur_u = before->cur_u;
1892
1893 else if ( u == after->org_u )
1894 point->cur_u = after->cur_u;
1895
1896 else
1897 point->cur_u = before->cur_u +
1898 FT_MulDiv( u - before->org_u,
1899 after->cur_u - before->cur_u,
1900 after->org_u - before->org_u );
1901 }
1902 }
1903 psh_point_set_fitted( point );
1904 }
1905 }
1906
1907 if ( strongs != strongs_0 )
1908 FT_FREE( strongs );
1909
1910#endif /* 1 */
1911
1912 }
1913
1914
1915 /* interpolate other points */
1916 static void
1917 psh_glyph_interpolate_other_points( PSH_Glyph glyph,
1918 FT_Int dimension )
1919 {
1920 PSH_Dimension dim = &glyph->globals->dimension[dimension];
1921 FT_Fixed scale = dim->scale_mult;
1922 FT_Fixed delta = dim->scale_delta;
1923 PSH_Contour contour = glyph->contours;
1924 FT_UInt num_contours = glyph->num_contours;
1925
1926
1927 for ( ; num_contours > 0; num_contours--, contour++ )
1928 {
1929 PSH_Point start = contour->start;
1930 PSH_Point first, next, point;
1931 FT_UInt fit_count;
1932
1933
1934 /* count the number of strong points in this contour */
1935 next = start + contour->count;
1936 fit_count = 0;
1937 first = NULL;
1938
1939 for ( point = start; point < next; point++ )
1940 if ( psh_point_is_fitted( point ) )
1941 {
1942 if ( !first )
1943 first = point;
1944
1945 fit_count++;
1946 }
1947
1948 /* if there are less than 2 fitted points in the contour, we */
1949 /* simply scale and eventually translate the contour points */
1950 if ( fit_count < 2 )
1951 {
1952 if ( fit_count == 1 )
1953 delta = first->cur_u - FT_MulFix( first->org_u, scale );
1954
1955 for ( point = start; point < next; point++ )
1956 if ( point != first )
1957 point->cur_u = FT_MulFix( point->org_u, scale ) + delta;
1958
1959 goto Next_Contour;
1960 }
1961
1962 /* there are more than 2 strong points in this contour; we */
1963 /* need to interpolate weak points between them */
1964 start = first;
1965 do
1966 {
1967 /* skip consecutive fitted points */
1968 for (;;)
1969 {
1970 next = first->next;
1971 if ( next == start )
1972 goto Next_Contour;
1973
1974 if ( !psh_point_is_fitted( next ) )
1975 break;
1976
1977 first = next;
1978 }
1979
1980 /* find next fitted point after unfitted one */
1981 for (;;)
1982 {
1983 next = next->next;
1984 if ( psh_point_is_fitted( next ) )
1985 break;
1986 }
1987
1988 /* now interpolate between them */
1989 {
1990 FT_Pos org_a, org_ab, cur_a, cur_ab;
1991 FT_Pos org_c, org_ac, cur_c;
1992 FT_Fixed scale_ab;
1993
1994
1995 if ( first->org_u <= next->org_u )
1996 {
1997 org_a = first->org_u;
1998 cur_a = first->cur_u;
1999 org_ab = next->org_u - org_a;
2000 cur_ab = next->cur_u - cur_a;
2001 }
2002 else
2003 {
2004 org_a = next->org_u;
2005 cur_a = next->cur_u;
2006 org_ab = first->org_u - org_a;
2007 cur_ab = first->cur_u - cur_a;
2008 }
2009
2010 scale_ab = 0x10000L;
2011 if ( org_ab > 0 )
2012 scale_ab = FT_DivFix( cur_ab, org_ab );
2013
2014 point = first->next;
2015 do
2016 {
2017 org_c = point->org_u;
2018 org_ac = org_c - org_a;
2019
2020 if ( org_ac <= 0 )
2021 {
2022 /* on the left of the interpolation zone */
2023 cur_c = cur_a + FT_MulFix( org_ac, scale );
2024 }
2025 else if ( org_ac >= org_ab )
2026 {
2027 /* on the right on the interpolation zone */
2028 cur_c = cur_a + cur_ab + FT_MulFix( org_ac - org_ab, scale );
2029 }
2030 else
2031 {
2032 /* within the interpolation zone */
2033 cur_c = cur_a + FT_MulFix( org_ac, scale_ab );
2034 }
2035
2036 point->cur_u = cur_c;
2037
2038 point = point->next;
2039
2040 } while ( point != next );
2041 }
2042
2043 /* keep going until all points in the contours have been processed */
2044 first = next;
2045
2046 } while ( first != start );
2047
2048 Next_Contour:
2049 ;
2050 }
2051 }
2052
2053
2054 /*************************************************************************/
2055 /*************************************************************************/
2056 /***** *****/
2057 /***** HIGH-LEVEL INTERFACE *****/
2058 /***** *****/
2059 /*************************************************************************/
2060 /*************************************************************************/
2061
2062 FT_Error
2063 ps_hints_apply( PS_Hints ps_hints,
2064 FT_Outline* outline,
2065 PSH_Globals globals,
2066 FT_Render_Mode hint_mode )
2067 {
2068 PSH_GlyphRec glyphrec;
2069 PSH_Glyph glyph = &glyphrec;
2070 FT_Error error;
2071#ifdef DEBUG_HINTER
2072 FT_Memory memory;
2073#endif
2074 FT_Int dimension;
2075
2076
2077 /* something to do? */
2078 if ( outline->n_points == 0 || outline->n_contours == 0 )
2079 return FT_Err_Ok;
2080
2081#ifdef DEBUG_HINTER
2082
2083 memory = globals->memory;
2084
2085 if ( ps_debug_glyph )
2086 {
2087 psh_glyph_done( ps_debug_glyph );
2088 FT_FREE( ps_debug_glyph );
2089 }
2090
2091 if ( FT_NEW( glyph ) )
2092 return error;
2093
2094 ps_debug_glyph = glyph;
2095
2096#endif /* DEBUG_HINTER */
2097
2098 error = psh_glyph_init( glyph, outline, ps_hints, globals );
2099 if ( error )
2100 goto Exit;
2101
2102 /* try to optimize the y_scale so that the top of non-capital letters
2103 * is aligned on a pixel boundary whenever possible
2104 */
2105 {
2106 PSH_Dimension dim_x = &glyph->globals->dimension[0];
2107 PSH_Dimension dim_y = &glyph->globals->dimension[1];
2108
2109 FT_Fixed x_scale = dim_x->scale_mult;
2110 FT_Fixed y_scale = dim_y->scale_mult;
2111
2112 FT_Fixed old_x_scale = x_scale;
2113 FT_Fixed old_y_scale = y_scale;
2114
2115 FT_Fixed scaled = 0;
2116 FT_Fixed fitted = 0;
2117
2118 FT_Bool rescale = FALSE;
2119
2120
2121 if ( globals->blues.normal_top.count )
2122 {
2123 scaled = FT_MulFix( globals->blues.normal_top.zones->org_ref, y_scale );
2124 fitted = FT_PIX_ROUND( scaled );
2125 }
2126
2127 if ( fitted != 0 && scaled != fitted )
2128 {
2129 rescale = TRUE;
2130
2131 y_scale = FT_MulDiv( y_scale, fitted, scaled );
2132
2133 if ( fitted < scaled )
2134 x_scale -= x_scale / 50;
2135
2136 psh_globals_set_scale( glyph->globals, x_scale, y_scale, 0, 0 );
2137 }
2138
2139 glyph->do_horz_hints = 1;
2140 glyph->do_vert_hints = 1;
2141
2142 glyph->do_horz_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO ||
2143 hint_mode == FT_RENDER_MODE_LCD );
2144
2145 glyph->do_vert_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO ||
2146 hint_mode == FT_RENDER_MODE_LCD_V );
2147
2148 glyph->do_stem_adjust = FT_BOOL( hint_mode != FT_RENDER_MODE_LIGHT );
2149
2150 for ( dimension = 0; dimension < 2; dimension++ )
2151 {
2152 /* load outline coordinates into glyph */
2153 psh_glyph_load_points( glyph, dimension );
2154
2155 /* compute local extrema */
2156 psh_glyph_compute_extrema( glyph );
2157
2158 /* compute aligned stem/hints positions */
2159 psh_hint_table_align_hints( &glyph->hint_tables[dimension],
2160 glyph->globals,
2161 dimension,
2162 glyph );
2163
2164 /* find strong points, align them, then interpolate others */
2165 psh_glyph_find_strong_points( glyph, dimension );
2166 if ( dimension == 1 )
2167 psh_glyph_find_blue_points( &globals->blues, glyph );
2168 psh_glyph_interpolate_strong_points( glyph, dimension );
2169 psh_glyph_interpolate_normal_points( glyph, dimension );
2170 psh_glyph_interpolate_other_points( glyph, dimension );
2171
2172 /* save hinted coordinates back to outline */
2173 psh_glyph_save_points( glyph, dimension );
2174
2175 if ( rescale )
2176 psh_globals_set_scale( glyph->globals,
2177 old_x_scale, old_y_scale, 0, 0 );
2178 }
2179 }
2180
2181 Exit:
2182
2183#ifndef DEBUG_HINTER
2184 psh_glyph_done( glyph );
2185#endif
2186
2187 return error;
2188 }
2189
2190
2191/* END */