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