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