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