1 /**************************************************************************** 2 * 3 * pshalgo.c 4 * 5 * PostScript hinting algorithm (body). 6 * 7 * Copyright 2001-2018 by 8 * David Turner, Robert Wilhelm, and Werner Lemberg. 9 * 10 * This file is part of the FreeType project, and may only be used 11 * modified and distributed under the terms of the FreeType project 12 * license, LICENSE.TXT. By continuing to use, modify, or distribute 13 * this file you indicate that you have read the license and 14 * understand and accept it fully. 15 * 16 */ 17 18 19 #include <ft2build.h> 20 #include FT_INTERNAL_OBJECTS_H 21 #include FT_INTERNAL_DEBUG_H 22 #include FT_INTERNAL_CALC_H 23 #include "pshalgo.h" 24 25 #include "pshnterr.h" 26 27 28 #undef FT_COMPONENT 29 #define FT_COMPONENT trace_pshalgo 30 31 32 #ifdef DEBUG_HINTER 33 PSH_Hint_Table ps_debug_hint_table = NULL; 34 PSH_HintFunc ps_debug_hint_func = NULL; 35 PSH_Glyph ps_debug_glyph = NULL; 36 #endif 37 38 39 #define COMPUTE_INFLEXS /* compute inflection points to optimize `S' */ 40 /* and similar glyphs */ 41 42 43 /*************************************************************************/ 44 /*************************************************************************/ 45 /***** *****/ 46 /***** BASIC HINTS RECORDINGS *****/ 47 /***** *****/ 48 /*************************************************************************/ 49 /*************************************************************************/ 50 51 /* return true if two stem hints overlap */ 52 static FT_Int psh_hint_overlap(PSH_Hint hint1,PSH_Hint hint2)53 psh_hint_overlap( PSH_Hint hint1, 54 PSH_Hint hint2 ) 55 { 56 return hint1->org_pos + hint1->org_len >= hint2->org_pos && 57 hint2->org_pos + hint2->org_len >= hint1->org_pos; 58 } 59 60 61 /* destroy hints table */ 62 static void psh_hint_table_done(PSH_Hint_Table table,FT_Memory memory)63 psh_hint_table_done( PSH_Hint_Table table, 64 FT_Memory memory ) 65 { 66 FT_FREE( table->zones ); 67 table->num_zones = 0; 68 table->zone = NULL; 69 70 FT_FREE( table->sort ); 71 FT_FREE( table->hints ); 72 table->num_hints = 0; 73 table->max_hints = 0; 74 table->sort_global = NULL; 75 } 76 77 78 /* deactivate all hints in a table */ 79 static void psh_hint_table_deactivate(PSH_Hint_Table table)80 psh_hint_table_deactivate( PSH_Hint_Table table ) 81 { 82 FT_UInt count = table->max_hints; 83 PSH_Hint hint = table->hints; 84 85 86 for ( ; count > 0; count--, hint++ ) 87 { 88 psh_hint_deactivate( hint ); 89 hint->order = -1; 90 } 91 } 92 93 94 /* internal function to record a new hint */ 95 static void psh_hint_table_record(PSH_Hint_Table table,FT_UInt idx)96 psh_hint_table_record( PSH_Hint_Table table, 97 FT_UInt idx ) 98 { 99 PSH_Hint hint = table->hints + idx; 100 101 102 if ( idx >= table->max_hints ) 103 { 104 FT_TRACE0(( "psh_hint_table_record: invalid hint index %d\n", idx )); 105 return; 106 } 107 108 /* ignore active hints */ 109 if ( psh_hint_is_active( hint ) ) 110 return; 111 112 psh_hint_activate( hint ); 113 114 /* now scan the current active hint set to check */ 115 /* whether `hint' overlaps with another hint */ 116 { 117 PSH_Hint* sorted = table->sort_global; 118 FT_UInt count = table->num_hints; 119 PSH_Hint hint2; 120 121 122 hint->parent = NULL; 123 for ( ; count > 0; count--, sorted++ ) 124 { 125 hint2 = sorted[0]; 126 127 if ( psh_hint_overlap( hint, hint2 ) ) 128 { 129 hint->parent = hint2; 130 break; 131 } 132 } 133 } 134 135 if ( table->num_hints < table->max_hints ) 136 table->sort_global[table->num_hints++] = hint; 137 else 138 FT_TRACE0(( "psh_hint_table_record: too many sorted hints! BUG!\n" )); 139 } 140 141 142 static void psh_hint_table_record_mask(PSH_Hint_Table table,PS_Mask hint_mask)143 psh_hint_table_record_mask( PSH_Hint_Table table, 144 PS_Mask hint_mask ) 145 { 146 FT_Int mask = 0, val = 0; 147 FT_Byte* cursor = hint_mask->bytes; 148 FT_UInt idx, limit; 149 150 151 limit = hint_mask->num_bits; 152 153 for ( idx = 0; idx < limit; idx++ ) 154 { 155 if ( mask == 0 ) 156 { 157 val = *cursor++; 158 mask = 0x80; 159 } 160 161 if ( val & mask ) 162 psh_hint_table_record( table, idx ); 163 164 mask >>= 1; 165 } 166 } 167 168 169 /* create hints table */ 170 static FT_Error psh_hint_table_init(PSH_Hint_Table table,PS_Hint_Table hints,PS_Mask_Table hint_masks,PS_Mask_Table counter_masks,FT_Memory memory)171 psh_hint_table_init( PSH_Hint_Table table, 172 PS_Hint_Table hints, 173 PS_Mask_Table hint_masks, 174 PS_Mask_Table counter_masks, 175 FT_Memory memory ) 176 { 177 FT_UInt count; 178 FT_Error error; 179 180 FT_UNUSED( counter_masks ); 181 182 183 count = hints->num_hints; 184 185 /* allocate our tables */ 186 if ( FT_NEW_ARRAY( table->sort, 2 * count ) || 187 FT_NEW_ARRAY( table->hints, count ) || 188 FT_NEW_ARRAY( table->zones, 2 * count + 1 ) ) 189 goto Exit; 190 191 table->max_hints = count; 192 table->sort_global = table->sort + count; 193 table->num_hints = 0; 194 table->num_zones = 0; 195 table->zone = NULL; 196 197 /* initialize the `table->hints' array */ 198 { 199 PSH_Hint write = table->hints; 200 PS_Hint read = hints->hints; 201 202 203 for ( ; count > 0; count--, write++, read++ ) 204 { 205 write->org_pos = read->pos; 206 write->org_len = read->len; 207 write->flags = read->flags; 208 } 209 } 210 211 /* we now need to determine the initial `parent' stems; first */ 212 /* activate the hints that are given by the initial hint masks */ 213 if ( hint_masks ) 214 { 215 PS_Mask mask = hint_masks->masks; 216 217 218 count = hint_masks->num_masks; 219 table->hint_masks = hint_masks; 220 221 for ( ; count > 0; count--, mask++ ) 222 psh_hint_table_record_mask( table, mask ); 223 } 224 225 /* finally, do a linear parse in case some hints were left alone */ 226 if ( table->num_hints != table->max_hints ) 227 { 228 FT_UInt idx; 229 230 231 FT_TRACE0(( "psh_hint_table_init: missing/incorrect hint masks\n" )); 232 233 count = table->max_hints; 234 for ( idx = 0; idx < count; idx++ ) 235 psh_hint_table_record( table, idx ); 236 } 237 238 Exit: 239 return error; 240 } 241 242 243 static void psh_hint_table_activate_mask(PSH_Hint_Table table,PS_Mask hint_mask)244 psh_hint_table_activate_mask( PSH_Hint_Table table, 245 PS_Mask hint_mask ) 246 { 247 FT_Int mask = 0, val = 0; 248 FT_Byte* cursor = hint_mask->bytes; 249 FT_UInt idx, limit, count; 250 251 252 limit = hint_mask->num_bits; 253 count = 0; 254 255 psh_hint_table_deactivate( table ); 256 257 for ( idx = 0; idx < limit; idx++ ) 258 { 259 if ( mask == 0 ) 260 { 261 val = *cursor++; 262 mask = 0x80; 263 } 264 265 if ( val & mask ) 266 { 267 PSH_Hint hint = &table->hints[idx]; 268 269 270 if ( !psh_hint_is_active( hint ) ) 271 { 272 FT_UInt count2; 273 274 #if 0 275 PSH_Hint* sort = table->sort; 276 PSH_Hint hint2; 277 278 279 for ( count2 = count; count2 > 0; count2--, sort++ ) 280 { 281 hint2 = sort[0]; 282 if ( psh_hint_overlap( hint, hint2 ) ) 283 FT_TRACE0(( "psh_hint_table_activate_mask:" 284 " found overlapping hints\n" )) 285 } 286 #else 287 count2 = 0; 288 #endif 289 290 if ( count2 == 0 ) 291 { 292 psh_hint_activate( hint ); 293 if ( count < table->max_hints ) 294 table->sort[count++] = hint; 295 else 296 FT_TRACE0(( "psh_hint_tableactivate_mask:" 297 " too many active hints\n" )); 298 } 299 } 300 } 301 302 mask >>= 1; 303 } 304 table->num_hints = count; 305 306 /* now, sort the hints; they are guaranteed to not overlap */ 307 /* so we can compare their "org_pos" field directly */ 308 { 309 FT_Int i1, i2; 310 PSH_Hint hint1, hint2; 311 PSH_Hint* sort = table->sort; 312 313 314 /* a simple bubble sort will do, since in 99% of cases, the hints */ 315 /* will be already sorted -- and the sort will be linear */ 316 for ( i1 = 1; i1 < (FT_Int)count; i1++ ) 317 { 318 hint1 = sort[i1]; 319 for ( i2 = i1 - 1; i2 >= 0; 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 psh_dimension_quantize_len(PSH_Dimension dim,FT_Pos len,FT_Bool do_snapping)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 ps_simple_scale(PSH_Hint_Table table,FT_Fixed scale,FT_Fixed delta,FT_Int dimension)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 psh_hint_snap_stem_side_delta(FT_Fixed pos,FT_Fixed len)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 psh_hint_align(PSH_Hint hint,PSH_Globals globals,FT_Int dimension,PSH_Glyph glyph)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 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, this 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 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 psh_hint_table_align_hints(PSH_Hint_Table table,PSH_Globals globals,FT_Int dimension,PSH_Glyph glyph)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 psh_print_zone(PSH_Zone zone)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 psh_glyph_compute_inflections(PSH_Glyph glyph)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 psh_glyph_done(PSH_Glyph glyph)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 int psh_compute_dir(FT_Pos dx,FT_Pos dy)1054 psh_compute_dir( FT_Pos dx, 1055 FT_Pos dy ) 1056 { 1057 FT_Pos ax, ay; 1058 int 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 psh_glyph_load_points(PSH_Glyph glyph,FT_Int dimension)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 psh_glyph_save_points(PSH_Glyph glyph,FT_Int dimension)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 char* 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 psh_glyph_init(PSH_Glyph glyph,FT_Outline * outline,PS_Hints ps_hints,PSH_Globals globals)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_NEW_ARRAY( glyph->points, outline->n_points ) || 1171 FT_NEW_ARRAY( glyph->contours, outline->n_contours ) ) 1172 goto Exit; 1173 1174 glyph->num_points = (FT_UInt)outline->n_points; 1175 glyph->num_contours = (FT_UInt)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 = (FT_UInt)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 if ( !( outline->tags[n] & FT_CURVE_TAG_ON ) ) 1232 point->flags = PSH_POINT_OFF; 1233 1234 dxi = vec[n].x - vec[n_prev].x; 1235 dyi = vec[n].y - vec[n_prev].y; 1236 1237 point->dir_in = (FT_Char)psh_compute_dir( dxi, dyi ); 1238 1239 dxo = vec[n_next].x - vec[n].x; 1240 dyo = vec[n_next].y - vec[n].y; 1241 1242 point->dir_out = (FT_Char)psh_compute_dir( dxo, dyo ); 1243 1244 /* detect smooth points */ 1245 if ( point->flags & PSH_POINT_OFF ) 1246 point->flags |= PSH_POINT_SMOOTH; 1247 1248 else if ( point->dir_in == point->dir_out ) 1249 { 1250 if ( point->dir_out != PSH_DIR_NONE || 1251 psh_corner_is_flat( dxi, dyi, dxo, dyo ) ) 1252 point->flags |= PSH_POINT_SMOOTH; 1253 } 1254 } 1255 } 1256 1257 glyph->outline = outline; 1258 glyph->globals = globals; 1259 1260 #ifdef COMPUTE_INFLEXS 1261 psh_glyph_load_points( glyph, 0 ); 1262 psh_glyph_compute_inflections( glyph ); 1263 #endif /* COMPUTE_INFLEXS */ 1264 1265 /* now deal with hints tables */ 1266 error = psh_hint_table_init( &glyph->hint_tables [0], 1267 &ps_hints->dimension[0].hints, 1268 &ps_hints->dimension[0].masks, 1269 &ps_hints->dimension[0].counters, 1270 memory ); 1271 if ( error ) 1272 goto Exit; 1273 1274 error = psh_hint_table_init( &glyph->hint_tables [1], 1275 &ps_hints->dimension[1].hints, 1276 &ps_hints->dimension[1].masks, 1277 &ps_hints->dimension[1].counters, 1278 memory ); 1279 if ( error ) 1280 goto Exit; 1281 1282 Exit: 1283 return error; 1284 } 1285 1286 1287 /* compute all extrema in a glyph for a given dimension */ 1288 static void psh_glyph_compute_extrema(PSH_Glyph glyph)1289 psh_glyph_compute_extrema( PSH_Glyph glyph ) 1290 { 1291 FT_UInt n; 1292 1293 1294 /* first of all, compute all local extrema */ 1295 for ( n = 0; n < glyph->num_contours; n++ ) 1296 { 1297 PSH_Point first = glyph->contours[n].start; 1298 PSH_Point point, before, after; 1299 1300 1301 if ( glyph->contours[n].count == 0 ) 1302 continue; 1303 1304 point = first; 1305 before = point; 1306 1307 do 1308 { 1309 before = before->prev; 1310 if ( before == first ) 1311 goto Skip; 1312 1313 } while ( before->org_u == point->org_u ); 1314 1315 first = point = before->next; 1316 1317 for (;;) 1318 { 1319 after = point; 1320 do 1321 { 1322 after = after->next; 1323 if ( after == first ) 1324 goto Next; 1325 1326 } while ( after->org_u == point->org_u ); 1327 1328 if ( before->org_u < point->org_u ) 1329 { 1330 if ( after->org_u < point->org_u ) 1331 { 1332 /* local maximum */ 1333 goto Extremum; 1334 } 1335 } 1336 else /* before->org_u > point->org_u */ 1337 { 1338 if ( after->org_u > point->org_u ) 1339 { 1340 /* local minimum */ 1341 Extremum: 1342 do 1343 { 1344 psh_point_set_extremum( point ); 1345 point = point->next; 1346 1347 } while ( point != after ); 1348 } 1349 } 1350 1351 before = after->prev; 1352 point = after; 1353 1354 } /* for */ 1355 1356 Next: 1357 ; 1358 } 1359 1360 /* for each extremum, determine its direction along the */ 1361 /* orthogonal axis */ 1362 for ( n = 0; n < glyph->num_points; n++ ) 1363 { 1364 PSH_Point point, before, after; 1365 1366 1367 point = &glyph->points[n]; 1368 before = point; 1369 after = point; 1370 1371 if ( psh_point_is_extremum( point ) ) 1372 { 1373 do 1374 { 1375 before = before->prev; 1376 if ( before == point ) 1377 goto Skip; 1378 1379 } while ( before->org_v == point->org_v ); 1380 1381 do 1382 { 1383 after = after->next; 1384 if ( after == point ) 1385 goto Skip; 1386 1387 } while ( after->org_v == point->org_v ); 1388 } 1389 1390 if ( before->org_v < point->org_v && 1391 after->org_v > point->org_v ) 1392 { 1393 psh_point_set_positive( point ); 1394 } 1395 else if ( before->org_v > point->org_v && 1396 after->org_v < point->org_v ) 1397 { 1398 psh_point_set_negative( point ); 1399 } 1400 1401 Skip: 1402 ; 1403 } 1404 } 1405 1406 1407 /* major_dir is the direction for points on the bottom/left of the stem; */ 1408 /* Points on the top/right of the stem will have a direction of */ 1409 /* -major_dir. */ 1410 1411 static void psh_hint_table_find_strong_points(PSH_Hint_Table table,PSH_Point point,FT_UInt count,FT_Int threshold,FT_Int major_dir)1412 psh_hint_table_find_strong_points( PSH_Hint_Table table, 1413 PSH_Point point, 1414 FT_UInt count, 1415 FT_Int threshold, 1416 FT_Int major_dir ) 1417 { 1418 PSH_Hint* sort = table->sort; 1419 FT_UInt num_hints = table->num_hints; 1420 1421 1422 for ( ; count > 0; count--, point++ ) 1423 { 1424 FT_Int point_dir = 0; 1425 FT_Pos org_u = point->org_u; 1426 1427 1428 if ( psh_point_is_strong( point ) ) 1429 continue; 1430 1431 if ( PSH_DIR_COMPARE( point->dir_in, major_dir ) ) 1432 point_dir = point->dir_in; 1433 1434 else if ( PSH_DIR_COMPARE( point->dir_out, major_dir ) ) 1435 point_dir = point->dir_out; 1436 1437 if ( point_dir ) 1438 { 1439 if ( point_dir == major_dir ) 1440 { 1441 FT_UInt nn; 1442 1443 1444 for ( nn = 0; nn < num_hints; nn++ ) 1445 { 1446 PSH_Hint hint = sort[nn]; 1447 FT_Pos d = org_u - hint->org_pos; 1448 1449 1450 if ( d < threshold && -d < threshold ) 1451 { 1452 psh_point_set_strong( point ); 1453 point->flags2 |= PSH_POINT_EDGE_MIN; 1454 point->hint = hint; 1455 break; 1456 } 1457 } 1458 } 1459 else if ( point_dir == -major_dir ) 1460 { 1461 FT_UInt nn; 1462 1463 1464 for ( nn = 0; nn < num_hints; nn++ ) 1465 { 1466 PSH_Hint hint = sort[nn]; 1467 FT_Pos d = org_u - hint->org_pos - hint->org_len; 1468 1469 1470 if ( d < threshold && -d < threshold ) 1471 { 1472 psh_point_set_strong( point ); 1473 point->flags2 |= PSH_POINT_EDGE_MAX; 1474 point->hint = hint; 1475 break; 1476 } 1477 } 1478 } 1479 } 1480 1481 #if 1 1482 else if ( psh_point_is_extremum( point ) ) 1483 { 1484 /* treat extrema as special cases for stem edge alignment */ 1485 FT_UInt nn, min_flag, max_flag; 1486 1487 1488 if ( major_dir == PSH_DIR_HORIZONTAL ) 1489 { 1490 min_flag = PSH_POINT_POSITIVE; 1491 max_flag = PSH_POINT_NEGATIVE; 1492 } 1493 else 1494 { 1495 min_flag = PSH_POINT_NEGATIVE; 1496 max_flag = PSH_POINT_POSITIVE; 1497 } 1498 1499 if ( point->flags2 & min_flag ) 1500 { 1501 for ( nn = 0; nn < num_hints; nn++ ) 1502 { 1503 PSH_Hint hint = sort[nn]; 1504 FT_Pos d = org_u - hint->org_pos; 1505 1506 1507 if ( d < threshold && -d < threshold ) 1508 { 1509 point->flags2 |= PSH_POINT_EDGE_MIN; 1510 point->hint = hint; 1511 psh_point_set_strong( point ); 1512 break; 1513 } 1514 } 1515 } 1516 else if ( point->flags2 & max_flag ) 1517 { 1518 for ( nn = 0; nn < num_hints; nn++ ) 1519 { 1520 PSH_Hint hint = sort[nn]; 1521 FT_Pos d = org_u - hint->org_pos - hint->org_len; 1522 1523 1524 if ( d < threshold && -d < threshold ) 1525 { 1526 point->flags2 |= PSH_POINT_EDGE_MAX; 1527 point->hint = hint; 1528 psh_point_set_strong( point ); 1529 break; 1530 } 1531 } 1532 } 1533 1534 if ( !point->hint ) 1535 { 1536 for ( nn = 0; nn < num_hints; nn++ ) 1537 { 1538 PSH_Hint hint = sort[nn]; 1539 1540 1541 if ( org_u >= hint->org_pos && 1542 org_u <= hint->org_pos + hint->org_len ) 1543 { 1544 point->hint = hint; 1545 break; 1546 } 1547 } 1548 } 1549 } 1550 1551 #endif /* 1 */ 1552 } 1553 } 1554 1555 1556 /* the accepted shift for strong points in fractional pixels */ 1557 #define PSH_STRONG_THRESHOLD 32 1558 1559 /* the maximum shift value in font units */ 1560 #define PSH_STRONG_THRESHOLD_MAXIMUM 30 1561 1562 1563 /* find strong points in a glyph */ 1564 static void psh_glyph_find_strong_points(PSH_Glyph glyph,FT_Int dimension)1565 psh_glyph_find_strong_points( PSH_Glyph glyph, 1566 FT_Int dimension ) 1567 { 1568 /* a point is `strong' if it is located on a stem edge and */ 1569 /* has an `in' or `out' tangent parallel to the hint's direction */ 1570 1571 PSH_Hint_Table table = &glyph->hint_tables[dimension]; 1572 PS_Mask mask = table->hint_masks->masks; 1573 FT_UInt num_masks = table->hint_masks->num_masks; 1574 FT_UInt first = 0; 1575 FT_Int major_dir = ( dimension == 0 ) ? PSH_DIR_VERTICAL 1576 : PSH_DIR_HORIZONTAL; 1577 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1578 FT_Fixed scale = dim->scale_mult; 1579 FT_Int threshold; 1580 1581 1582 threshold = (FT_Int)FT_DivFix( PSH_STRONG_THRESHOLD, scale ); 1583 if ( threshold > PSH_STRONG_THRESHOLD_MAXIMUM ) 1584 threshold = PSH_STRONG_THRESHOLD_MAXIMUM; 1585 1586 /* process secondary hints to `selected' points */ 1587 if ( num_masks > 1 && glyph->num_points > 0 ) 1588 { 1589 /* the `endchar' op can reduce the number of points */ 1590 first = mask->end_point > glyph->num_points 1591 ? glyph->num_points 1592 : mask->end_point; 1593 mask++; 1594 for ( ; num_masks > 1; num_masks--, mask++ ) 1595 { 1596 FT_UInt next = FT_MIN( mask->end_point, glyph->num_points ); 1597 1598 1599 if ( next > first ) 1600 { 1601 FT_UInt count = next - first; 1602 PSH_Point point = glyph->points + first; 1603 1604 1605 psh_hint_table_activate_mask( table, mask ); 1606 1607 psh_hint_table_find_strong_points( table, point, count, 1608 threshold, major_dir ); 1609 } 1610 first = next; 1611 } 1612 } 1613 1614 /* process primary hints for all points */ 1615 if ( num_masks == 1 ) 1616 { 1617 FT_UInt count = glyph->num_points; 1618 PSH_Point point = glyph->points; 1619 1620 1621 psh_hint_table_activate_mask( table, table->hint_masks->masks ); 1622 1623 psh_hint_table_find_strong_points( table, point, count, 1624 threshold, major_dir ); 1625 } 1626 1627 /* now, certain points may have been attached to a hint and */ 1628 /* not marked as strong; update their flags then */ 1629 { 1630 FT_UInt count = glyph->num_points; 1631 PSH_Point point = glyph->points; 1632 1633 1634 for ( ; count > 0; count--, point++ ) 1635 if ( point->hint && !psh_point_is_strong( point ) ) 1636 psh_point_set_strong( point ); 1637 } 1638 } 1639 1640 1641 /* find points in a glyph which are in a blue zone and have `in' or */ 1642 /* `out' tangents parallel to the horizontal axis */ 1643 static void psh_glyph_find_blue_points(PSH_Blues blues,PSH_Glyph glyph)1644 psh_glyph_find_blue_points( PSH_Blues blues, 1645 PSH_Glyph glyph ) 1646 { 1647 PSH_Blue_Table table; 1648 PSH_Blue_Zone zone; 1649 FT_UInt glyph_count = glyph->num_points; 1650 FT_UInt blue_count; 1651 PSH_Point point = glyph->points; 1652 1653 1654 for ( ; glyph_count > 0; glyph_count--, point++ ) 1655 { 1656 FT_Pos y; 1657 1658 1659 /* check tangents */ 1660 if ( !PSH_DIR_COMPARE( point->dir_in, PSH_DIR_HORIZONTAL ) && 1661 !PSH_DIR_COMPARE( point->dir_out, PSH_DIR_HORIZONTAL ) ) 1662 continue; 1663 1664 /* skip strong points */ 1665 if ( psh_point_is_strong( point ) ) 1666 continue; 1667 1668 y = point->org_u; 1669 1670 /* look up top zones */ 1671 table = &blues->normal_top; 1672 blue_count = table->count; 1673 zone = table->zones; 1674 1675 for ( ; blue_count > 0; blue_count--, zone++ ) 1676 { 1677 FT_Pos delta = y - zone->org_bottom; 1678 1679 1680 if ( delta < -blues->blue_fuzz ) 1681 break; 1682 1683 if ( y <= zone->org_top + blues->blue_fuzz ) 1684 if ( blues->no_overshoots || delta <= blues->blue_threshold ) 1685 { 1686 point->cur_u = zone->cur_bottom; 1687 psh_point_set_strong( point ); 1688 psh_point_set_fitted( point ); 1689 } 1690 } 1691 1692 /* look up bottom zones */ 1693 table = &blues->normal_bottom; 1694 blue_count = table->count; 1695 zone = table->zones + blue_count - 1; 1696 1697 for ( ; blue_count > 0; blue_count--, zone-- ) 1698 { 1699 FT_Pos delta = zone->org_top - y; 1700 1701 1702 if ( delta < -blues->blue_fuzz ) 1703 break; 1704 1705 if ( y >= zone->org_bottom - blues->blue_fuzz ) 1706 if ( blues->no_overshoots || delta < blues->blue_threshold ) 1707 { 1708 point->cur_u = zone->cur_top; 1709 psh_point_set_strong( point ); 1710 psh_point_set_fitted( point ); 1711 } 1712 } 1713 } 1714 } 1715 1716 1717 /* interpolate strong points with the help of hinted coordinates */ 1718 static void psh_glyph_interpolate_strong_points(PSH_Glyph glyph,FT_Int dimension)1719 psh_glyph_interpolate_strong_points( PSH_Glyph glyph, 1720 FT_Int dimension ) 1721 { 1722 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1723 FT_Fixed scale = dim->scale_mult; 1724 1725 FT_UInt count = glyph->num_points; 1726 PSH_Point point = glyph->points; 1727 1728 1729 for ( ; count > 0; count--, point++ ) 1730 { 1731 PSH_Hint hint = point->hint; 1732 1733 1734 if ( hint ) 1735 { 1736 FT_Pos delta; 1737 1738 1739 if ( psh_point_is_edge_min( point ) ) 1740 point->cur_u = hint->cur_pos; 1741 1742 else if ( psh_point_is_edge_max( point ) ) 1743 point->cur_u = hint->cur_pos + hint->cur_len; 1744 1745 else 1746 { 1747 delta = point->org_u - hint->org_pos; 1748 1749 if ( delta <= 0 ) 1750 point->cur_u = hint->cur_pos + FT_MulFix( delta, scale ); 1751 1752 else if ( delta >= hint->org_len ) 1753 point->cur_u = hint->cur_pos + hint->cur_len + 1754 FT_MulFix( delta - hint->org_len, scale ); 1755 1756 else /* hint->org_len > 0 */ 1757 point->cur_u = hint->cur_pos + 1758 FT_MulDiv( delta, hint->cur_len, 1759 hint->org_len ); 1760 } 1761 psh_point_set_fitted( point ); 1762 } 1763 } 1764 } 1765 1766 1767 #define PSH_MAX_STRONG_INTERNAL 16 1768 1769 static void psh_glyph_interpolate_normal_points(PSH_Glyph glyph,FT_Int dimension)1770 psh_glyph_interpolate_normal_points( PSH_Glyph glyph, 1771 FT_Int dimension ) 1772 { 1773 1774 #if 1 1775 /* first technique: a point is strong if it is a local extremum */ 1776 1777 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1778 FT_Fixed scale = dim->scale_mult; 1779 FT_Memory memory = glyph->memory; 1780 1781 PSH_Point* strongs = NULL; 1782 PSH_Point strongs_0[PSH_MAX_STRONG_INTERNAL]; 1783 FT_UInt num_strongs = 0; 1784 1785 PSH_Point points = glyph->points; 1786 PSH_Point points_end = points + glyph->num_points; 1787 PSH_Point point; 1788 1789 1790 /* first count the number of strong points */ 1791 for ( point = points; point < points_end; point++ ) 1792 { 1793 if ( psh_point_is_strong( point ) ) 1794 num_strongs++; 1795 } 1796 1797 if ( num_strongs == 0 ) /* nothing to do here */ 1798 return; 1799 1800 /* allocate an array to store a list of points, */ 1801 /* stored in increasing org_u order */ 1802 if ( num_strongs <= PSH_MAX_STRONG_INTERNAL ) 1803 strongs = strongs_0; 1804 else 1805 { 1806 FT_Error error; 1807 1808 1809 if ( FT_NEW_ARRAY( strongs, num_strongs ) ) 1810 return; 1811 } 1812 1813 num_strongs = 0; 1814 for ( point = points; point < points_end; point++ ) 1815 { 1816 PSH_Point* insert; 1817 1818 1819 if ( !psh_point_is_strong( point ) ) 1820 continue; 1821 1822 for ( insert = strongs + num_strongs; insert > strongs; insert-- ) 1823 { 1824 if ( insert[-1]->org_u <= point->org_u ) 1825 break; 1826 1827 insert[0] = insert[-1]; 1828 } 1829 insert[0] = point; 1830 num_strongs++; 1831 } 1832 1833 /* now try to interpolate all normal points */ 1834 for ( point = points; point < points_end; point++ ) 1835 { 1836 if ( psh_point_is_strong( point ) ) 1837 continue; 1838 1839 /* sometimes, some local extrema are smooth points */ 1840 if ( psh_point_is_smooth( point ) ) 1841 { 1842 if ( point->dir_in == PSH_DIR_NONE || 1843 point->dir_in != point->dir_out ) 1844 continue; 1845 1846 if ( !psh_point_is_extremum( point ) && 1847 !psh_point_is_inflex( point ) ) 1848 continue; 1849 1850 point->flags &= ~PSH_POINT_SMOOTH; 1851 } 1852 1853 /* find best enclosing point coordinates then interpolate */ 1854 { 1855 PSH_Point before, after; 1856 FT_UInt nn; 1857 1858 1859 for ( nn = 0; nn < num_strongs; nn++ ) 1860 if ( strongs[nn]->org_u > point->org_u ) 1861 break; 1862 1863 if ( nn == 0 ) /* point before the first strong point */ 1864 { 1865 after = strongs[0]; 1866 1867 point->cur_u = after->cur_u + 1868 FT_MulFix( point->org_u - after->org_u, 1869 scale ); 1870 } 1871 else 1872 { 1873 before = strongs[nn - 1]; 1874 1875 for ( nn = num_strongs; nn > 0; nn-- ) 1876 if ( strongs[nn - 1]->org_u < point->org_u ) 1877 break; 1878 1879 if ( nn == num_strongs ) /* point is after last strong point */ 1880 { 1881 before = strongs[nn - 1]; 1882 1883 point->cur_u = before->cur_u + 1884 FT_MulFix( point->org_u - before->org_u, 1885 scale ); 1886 } 1887 else 1888 { 1889 FT_Pos u; 1890 1891 1892 after = strongs[nn]; 1893 1894 /* now interpolate point between before and after */ 1895 u = point->org_u; 1896 1897 if ( u == before->org_u ) 1898 point->cur_u = before->cur_u; 1899 1900 else if ( u == after->org_u ) 1901 point->cur_u = after->cur_u; 1902 1903 else 1904 point->cur_u = before->cur_u + 1905 FT_MulDiv( u - before->org_u, 1906 after->cur_u - before->cur_u, 1907 after->org_u - before->org_u ); 1908 } 1909 } 1910 psh_point_set_fitted( point ); 1911 } 1912 } 1913 1914 if ( strongs != strongs_0 ) 1915 FT_FREE( strongs ); 1916 1917 #endif /* 1 */ 1918 1919 } 1920 1921 1922 /* interpolate other points */ 1923 static void psh_glyph_interpolate_other_points(PSH_Glyph glyph,FT_Int dimension)1924 psh_glyph_interpolate_other_points( PSH_Glyph glyph, 1925 FT_Int dimension ) 1926 { 1927 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1928 FT_Fixed scale = dim->scale_mult; 1929 FT_Fixed delta = dim->scale_delta; 1930 PSH_Contour contour = glyph->contours; 1931 FT_UInt num_contours = glyph->num_contours; 1932 1933 1934 for ( ; num_contours > 0; num_contours--, contour++ ) 1935 { 1936 PSH_Point start = contour->start; 1937 PSH_Point first, next, point; 1938 FT_UInt fit_count; 1939 1940 1941 /* count the number of strong points in this contour */ 1942 next = start + contour->count; 1943 fit_count = 0; 1944 first = NULL; 1945 1946 for ( point = start; point < next; point++ ) 1947 if ( psh_point_is_fitted( point ) ) 1948 { 1949 if ( !first ) 1950 first = point; 1951 1952 fit_count++; 1953 } 1954 1955 /* if there are less than 2 fitted points in the contour, we */ 1956 /* simply scale and eventually translate the contour points */ 1957 if ( fit_count < 2 ) 1958 { 1959 if ( fit_count == 1 ) 1960 delta = first->cur_u - FT_MulFix( first->org_u, scale ); 1961 1962 for ( point = start; point < next; point++ ) 1963 if ( point != first ) 1964 point->cur_u = FT_MulFix( point->org_u, scale ) + delta; 1965 1966 goto Next_Contour; 1967 } 1968 1969 /* there are more than 2 strong points in this contour; we */ 1970 /* need to interpolate weak points between them */ 1971 start = first; 1972 do 1973 { 1974 /* skip consecutive fitted points */ 1975 for (;;) 1976 { 1977 next = first->next; 1978 if ( next == start ) 1979 goto Next_Contour; 1980 1981 if ( !psh_point_is_fitted( next ) ) 1982 break; 1983 1984 first = next; 1985 } 1986 1987 /* find next fitted point after unfitted one */ 1988 for (;;) 1989 { 1990 next = next->next; 1991 if ( psh_point_is_fitted( next ) ) 1992 break; 1993 } 1994 1995 /* now interpolate between them */ 1996 { 1997 FT_Pos org_a, org_ab, cur_a, cur_ab; 1998 FT_Pos org_c, org_ac, cur_c; 1999 FT_Fixed scale_ab; 2000 2001 2002 if ( first->org_u <= next->org_u ) 2003 { 2004 org_a = first->org_u; 2005 cur_a = first->cur_u; 2006 org_ab = next->org_u - org_a; 2007 cur_ab = next->cur_u - cur_a; 2008 } 2009 else 2010 { 2011 org_a = next->org_u; 2012 cur_a = next->cur_u; 2013 org_ab = first->org_u - org_a; 2014 cur_ab = first->cur_u - cur_a; 2015 } 2016 2017 scale_ab = 0x10000L; 2018 if ( org_ab > 0 ) 2019 scale_ab = FT_DivFix( cur_ab, org_ab ); 2020 2021 point = first->next; 2022 do 2023 { 2024 org_c = point->org_u; 2025 org_ac = org_c - org_a; 2026 2027 if ( org_ac <= 0 ) 2028 { 2029 /* on the left of the interpolation zone */ 2030 cur_c = cur_a + FT_MulFix( org_ac, scale ); 2031 } 2032 else if ( org_ac >= org_ab ) 2033 { 2034 /* on the right on the interpolation zone */ 2035 cur_c = cur_a + cur_ab + FT_MulFix( org_ac - org_ab, scale ); 2036 } 2037 else 2038 { 2039 /* within the interpolation zone */ 2040 cur_c = cur_a + FT_MulFix( org_ac, scale_ab ); 2041 } 2042 2043 point->cur_u = cur_c; 2044 2045 point = point->next; 2046 2047 } while ( point != next ); 2048 } 2049 2050 /* keep going until all points in the contours have been processed */ 2051 first = next; 2052 2053 } while ( first != start ); 2054 2055 Next_Contour: 2056 ; 2057 } 2058 } 2059 2060 2061 /*************************************************************************/ 2062 /*************************************************************************/ 2063 /***** *****/ 2064 /***** HIGH-LEVEL INTERFACE *****/ 2065 /***** *****/ 2066 /*************************************************************************/ 2067 /*************************************************************************/ 2068 2069 FT_Error ps_hints_apply(PS_Hints ps_hints,FT_Outline * outline,PSH_Globals globals,FT_Render_Mode hint_mode)2070 ps_hints_apply( PS_Hints ps_hints, 2071 FT_Outline* outline, 2072 PSH_Globals globals, 2073 FT_Render_Mode hint_mode ) 2074 { 2075 PSH_GlyphRec glyphrec; 2076 PSH_Glyph glyph = &glyphrec; 2077 FT_Error error; 2078 #ifdef DEBUG_HINTER 2079 FT_Memory memory; 2080 #endif 2081 FT_Int dimension; 2082 2083 2084 /* something to do? */ 2085 if ( outline->n_points == 0 || outline->n_contours == 0 ) 2086 return FT_Err_Ok; 2087 2088 #ifdef DEBUG_HINTER 2089 2090 memory = globals->memory; 2091 2092 if ( ps_debug_glyph ) 2093 { 2094 psh_glyph_done( ps_debug_glyph ); 2095 FT_FREE( ps_debug_glyph ); 2096 } 2097 2098 if ( FT_NEW( glyph ) ) 2099 return error; 2100 2101 ps_debug_glyph = glyph; 2102 2103 #endif /* DEBUG_HINTER */ 2104 2105 error = psh_glyph_init( glyph, outline, ps_hints, globals ); 2106 if ( error ) 2107 goto Exit; 2108 2109 /* try to optimize the y_scale so that the top of non-capital letters 2110 * is aligned on a pixel boundary whenever possible 2111 */ 2112 { 2113 PSH_Dimension dim_x = &glyph->globals->dimension[0]; 2114 PSH_Dimension dim_y = &glyph->globals->dimension[1]; 2115 2116 FT_Fixed x_scale = dim_x->scale_mult; 2117 FT_Fixed y_scale = dim_y->scale_mult; 2118 2119 FT_Fixed old_x_scale = x_scale; 2120 FT_Fixed old_y_scale = y_scale; 2121 2122 FT_Fixed scaled; 2123 FT_Fixed fitted; 2124 2125 FT_Bool rescale = FALSE; 2126 2127 2128 scaled = FT_MulFix( globals->blues.normal_top.zones->org_ref, y_scale ); 2129 fitted = FT_PIX_ROUND( scaled ); 2130 2131 if ( fitted != 0 && scaled != fitted ) 2132 { 2133 rescale = TRUE; 2134 2135 y_scale = FT_MulDiv( y_scale, fitted, scaled ); 2136 2137 if ( fitted < scaled ) 2138 x_scale -= x_scale / 50; 2139 2140 psh_globals_set_scale( glyph->globals, x_scale, y_scale, 0, 0 ); 2141 } 2142 2143 glyph->do_horz_hints = 1; 2144 glyph->do_vert_hints = 1; 2145 2146 glyph->do_horz_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO || 2147 hint_mode == FT_RENDER_MODE_LCD ); 2148 2149 glyph->do_vert_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO || 2150 hint_mode == FT_RENDER_MODE_LCD_V ); 2151 2152 glyph->do_stem_adjust = FT_BOOL( hint_mode != FT_RENDER_MODE_LIGHT ); 2153 2154 for ( dimension = 0; dimension < 2; dimension++ ) 2155 { 2156 /* load outline coordinates into glyph */ 2157 psh_glyph_load_points( glyph, dimension ); 2158 2159 /* compute local extrema */ 2160 psh_glyph_compute_extrema( glyph ); 2161 2162 /* compute aligned stem/hints positions */ 2163 psh_hint_table_align_hints( &glyph->hint_tables[dimension], 2164 glyph->globals, 2165 dimension, 2166 glyph ); 2167 2168 /* find strong points, align them, then interpolate others */ 2169 psh_glyph_find_strong_points( glyph, dimension ); 2170 if ( dimension == 1 ) 2171 psh_glyph_find_blue_points( &globals->blues, glyph ); 2172 psh_glyph_interpolate_strong_points( glyph, dimension ); 2173 psh_glyph_interpolate_normal_points( glyph, dimension ); 2174 psh_glyph_interpolate_other_points( glyph, dimension ); 2175 2176 /* save hinted coordinates back to outline */ 2177 psh_glyph_save_points( glyph, dimension ); 2178 2179 if ( rescale ) 2180 psh_globals_set_scale( glyph->globals, 2181 old_x_scale, old_y_scale, 0, 0 ); 2182 } 2183 } 2184 2185 Exit: 2186 2187 #ifndef DEBUG_HINTER 2188 psh_glyph_done( glyph ); 2189 #endif 2190 2191 return error; 2192 } 2193 2194 2195 /* END */ 2196