1 /***************************************************************************/ 2 /* */ 3 /* pshalgo.c */ 4 /* */ 5 /* PostScript hinting algorithm (body). */ 6 /* */ 7 /* Copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 psh_hint_overlap(PSH_Hint hint1,PSH_Hint hint2)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 psh_hint_table_done(PSH_Hint_Table table,FT_Memory memory)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 psh_hint_table_deactivate(PSH_Hint_Table table)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 psh_hint_table_record(PSH_Hint_Table table,FT_UInt idx)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_ERROR(( "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_ERROR(( "psh_hint_table_record: too many sorted hints! BUG!\n" )); 141 } 142 143 144 static void psh_hint_table_record_mask(PSH_Hint_Table table,PS_Mask hint_mask)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 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)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_ERROR(( "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 psh_hint_table_activate_mask(PSH_Hint_Table table,PS_Mask hint_mask)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_ERROR(( "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_ERROR(( "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 psh_dimension_quantize_len(PSH_Dimension dim,FT_Pos len,FT_Bool do_snapping)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 ps_simple_scale(PSH_Hint_Table table,FT_Fixed scale,FT_Fixed delta,FT_Int dimension)399 ps_simple_scale( PSH_Hint_Table table, 400 FT_Fixed scale, 401 FT_Fixed delta, 402 FT_Int dimension ) 403 { 404 PSH_Hint hint; 405 FT_UInt count; 406 407 408 for ( count = 0; count < table->max_hints; count++ ) 409 { 410 hint = table->hints + count; 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 psh_hint_snap_stem_side_delta(FT_Fixed pos,FT_Fixed len)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 psh_hint_align(PSH_Hint hint,PSH_Globals globals,FT_Int dimension,PSH_Glyph glyph)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 minimal 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 psh_hint_table_align_hints(PSH_Hint_Table table,PSH_Globals globals,FT_Int dimension,PSH_Glyph glyph)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 psh_print_zone(PSH_Zone zone)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 ) psh_corner_is_flat(FT_Pos x_in,FT_Pos y_in,FT_Pos x_out,FT_Pos y_out)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 psh_corner_orientation(FT_Pos in_x,FT_Pos in_y,FT_Pos out_x,FT_Pos out_y)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 psh_glyph_compute_inflections(PSH_Glyph glyph)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 psh_glyph_done(PSH_Glyph glyph)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 psh_compute_dir(FT_Pos dx,FT_Pos dy)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 = ( dx >= 0 ) ? dx : -dx; 1165 ay = ( dy >= 0 ) ? dy : -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 psh_glyph_load_points(PSH_Glyph glyph,FT_Int dimension)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 psh_glyph_save_points(PSH_Glyph glyph,FT_Int dimension)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 psh_glyph_init(PSH_Glyph glyph,FT_Outline * outline,PS_Hints ps_hints,PSH_Globals globals)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 psh_glyph_compute_extrema(PSH_Glyph glyph)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 psh_hint_table_find_strong_points(PSH_Hint_Table table,PSH_Point point,FT_UInt count,FT_Int threshold,FT_Int major_dir)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 psh_glyph_find_strong_points(PSH_Glyph glyph,FT_Int dimension)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 first = mask->end_point; 1694 mask++; 1695 for ( ; num_masks > 1; num_masks--, mask++ ) 1696 { 1697 FT_UInt next; 1698 FT_Int count; 1699 1700 1701 next = mask->end_point; 1702 count = next - first; 1703 if ( count > 0 ) 1704 { 1705 PSH_Point point = glyph->points + first; 1706 1707 1708 psh_hint_table_activate_mask( table, mask ); 1709 1710 psh_hint_table_find_strong_points( table, point, count, 1711 threshold, major_dir ); 1712 } 1713 first = next; 1714 } 1715 } 1716 1717 /* process primary hints for all points */ 1718 if ( num_masks == 1 ) 1719 { 1720 FT_UInt count = glyph->num_points; 1721 PSH_Point point = glyph->points; 1722 1723 1724 psh_hint_table_activate_mask( table, table->hint_masks->masks ); 1725 1726 psh_hint_table_find_strong_points( table, point, count, 1727 threshold, major_dir ); 1728 } 1729 1730 /* now, certain points may have been attached to a hint and */ 1731 /* not marked as strong; update their flags then */ 1732 { 1733 FT_UInt count = glyph->num_points; 1734 PSH_Point point = glyph->points; 1735 1736 1737 for ( ; count > 0; count--, point++ ) 1738 if ( point->hint && !psh_point_is_strong( point ) ) 1739 psh_point_set_strong( point ); 1740 } 1741 } 1742 1743 1744 /* find points in a glyph which are in a blue zone and have `in' or */ 1745 /* `out' tangents parallel to the horizontal axis */ 1746 static void psh_glyph_find_blue_points(PSH_Blues blues,PSH_Glyph glyph)1747 psh_glyph_find_blue_points( PSH_Blues blues, 1748 PSH_Glyph glyph ) 1749 { 1750 PSH_Blue_Table table; 1751 PSH_Blue_Zone zone; 1752 FT_UInt glyph_count = glyph->num_points; 1753 FT_UInt blue_count; 1754 PSH_Point point = glyph->points; 1755 1756 1757 for ( ; glyph_count > 0; glyph_count--, point++ ) 1758 { 1759 FT_Pos y; 1760 1761 1762 /* check tangents */ 1763 if ( !PSH_DIR_COMPARE( point->dir_in, PSH_DIR_HORIZONTAL ) && 1764 !PSH_DIR_COMPARE( point->dir_out, PSH_DIR_HORIZONTAL ) ) 1765 continue; 1766 1767 /* skip strong points */ 1768 if ( psh_point_is_strong( point ) ) 1769 continue; 1770 1771 y = point->org_u; 1772 1773 /* look up top zones */ 1774 table = &blues->normal_top; 1775 blue_count = table->count; 1776 zone = table->zones; 1777 1778 for ( ; blue_count > 0; blue_count--, zone++ ) 1779 { 1780 FT_Pos delta = y - zone->org_bottom; 1781 1782 1783 if ( delta < -blues->blue_fuzz ) 1784 break; 1785 1786 if ( y <= zone->org_top + blues->blue_fuzz ) 1787 if ( blues->no_overshoots || delta <= blues->blue_threshold ) 1788 { 1789 point->cur_u = zone->cur_bottom; 1790 psh_point_set_strong( point ); 1791 psh_point_set_fitted( point ); 1792 } 1793 } 1794 1795 /* look up bottom zones */ 1796 table = &blues->normal_bottom; 1797 blue_count = table->count; 1798 zone = table->zones + blue_count - 1; 1799 1800 for ( ; blue_count > 0; blue_count--, zone-- ) 1801 { 1802 FT_Pos delta = zone->org_top - y; 1803 1804 1805 if ( delta < -blues->blue_fuzz ) 1806 break; 1807 1808 if ( y >= zone->org_bottom - blues->blue_fuzz ) 1809 if ( blues->no_overshoots || delta < blues->blue_threshold ) 1810 { 1811 point->cur_u = zone->cur_top; 1812 psh_point_set_strong( point ); 1813 psh_point_set_fitted( point ); 1814 } 1815 } 1816 } 1817 } 1818 1819 1820 /* interpolate strong points with the help of hinted coordinates */ 1821 static void psh_glyph_interpolate_strong_points(PSH_Glyph glyph,FT_Int dimension)1822 psh_glyph_interpolate_strong_points( PSH_Glyph glyph, 1823 FT_Int dimension ) 1824 { 1825 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1826 FT_Fixed scale = dim->scale_mult; 1827 1828 FT_UInt count = glyph->num_points; 1829 PSH_Point point = glyph->points; 1830 1831 1832 for ( ; count > 0; count--, point++ ) 1833 { 1834 PSH_Hint hint = point->hint; 1835 1836 1837 if ( hint ) 1838 { 1839 FT_Pos delta; 1840 1841 1842 if ( psh_point_is_edge_min( point ) ) 1843 point->cur_u = hint->cur_pos; 1844 1845 else if ( psh_point_is_edge_max( point ) ) 1846 point->cur_u = hint->cur_pos + hint->cur_len; 1847 1848 else 1849 { 1850 delta = point->org_u - hint->org_pos; 1851 1852 if ( delta <= 0 ) 1853 point->cur_u = hint->cur_pos + FT_MulFix( delta, scale ); 1854 1855 else if ( delta >= hint->org_len ) 1856 point->cur_u = hint->cur_pos + hint->cur_len + 1857 FT_MulFix( delta - hint->org_len, scale ); 1858 1859 else if ( hint->org_len > 0 ) 1860 point->cur_u = hint->cur_pos + 1861 FT_MulDiv( delta, hint->cur_len, 1862 hint->org_len ); 1863 else 1864 point->cur_u = hint->cur_pos; 1865 } 1866 psh_point_set_fitted( point ); 1867 } 1868 } 1869 } 1870 1871 1872 #define PSH_MAX_STRONG_INTERNAL 16 1873 1874 static void psh_glyph_interpolate_normal_points(PSH_Glyph glyph,FT_Int dimension)1875 psh_glyph_interpolate_normal_points( PSH_Glyph glyph, 1876 FT_Int dimension ) 1877 { 1878 1879 #if 1 1880 /* first technique: a point is strong if it is a local extremum */ 1881 1882 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1883 FT_Fixed scale = dim->scale_mult; 1884 FT_Memory memory = glyph->memory; 1885 1886 PSH_Point* strongs = NULL; 1887 PSH_Point strongs_0[PSH_MAX_STRONG_INTERNAL]; 1888 FT_UInt num_strongs = 0; 1889 1890 PSH_Point points = glyph->points; 1891 PSH_Point points_end = points + glyph->num_points; 1892 PSH_Point point; 1893 1894 1895 /* first count the number of strong points */ 1896 for ( point = points; point < points_end; point++ ) 1897 { 1898 if ( psh_point_is_strong( point ) ) 1899 num_strongs++; 1900 } 1901 1902 if ( num_strongs == 0 ) /* nothing to do here */ 1903 return; 1904 1905 /* allocate an array to store a list of points, */ 1906 /* stored in increasing org_u order */ 1907 if ( num_strongs <= PSH_MAX_STRONG_INTERNAL ) 1908 strongs = strongs_0; 1909 else 1910 { 1911 FT_Error error; 1912 1913 1914 if ( FT_NEW_ARRAY( strongs, num_strongs ) ) 1915 return; 1916 } 1917 1918 num_strongs = 0; 1919 for ( point = points; point < points_end; point++ ) 1920 { 1921 PSH_Point* insert; 1922 1923 1924 if ( !psh_point_is_strong( point ) ) 1925 continue; 1926 1927 for ( insert = strongs + num_strongs; insert > strongs; insert-- ) 1928 { 1929 if ( insert[-1]->org_u <= point->org_u ) 1930 break; 1931 1932 insert[0] = insert[-1]; 1933 } 1934 insert[0] = point; 1935 num_strongs++; 1936 } 1937 1938 /* now try to interpolate all normal points */ 1939 for ( point = points; point < points_end; point++ ) 1940 { 1941 if ( psh_point_is_strong( point ) ) 1942 continue; 1943 1944 /* sometimes, some local extrema are smooth points */ 1945 if ( psh_point_is_smooth( point ) ) 1946 { 1947 if ( point->dir_in == PSH_DIR_NONE || 1948 point->dir_in != point->dir_out ) 1949 continue; 1950 1951 if ( !psh_point_is_extremum( point ) && 1952 !psh_point_is_inflex( point ) ) 1953 continue; 1954 1955 point->flags &= ~PSH_POINT_SMOOTH; 1956 } 1957 1958 /* find best enclosing point coordinates then interpolate */ 1959 { 1960 PSH_Point before, after; 1961 FT_UInt nn; 1962 1963 1964 for ( nn = 0; nn < num_strongs; nn++ ) 1965 if ( strongs[nn]->org_u > point->org_u ) 1966 break; 1967 1968 if ( nn == 0 ) /* point before the first strong point */ 1969 { 1970 after = strongs[0]; 1971 1972 point->cur_u = after->cur_u + 1973 FT_MulFix( point->org_u - after->org_u, 1974 scale ); 1975 } 1976 else 1977 { 1978 before = strongs[nn - 1]; 1979 1980 for ( nn = num_strongs; nn > 0; nn-- ) 1981 if ( strongs[nn - 1]->org_u < point->org_u ) 1982 break; 1983 1984 if ( nn == num_strongs ) /* point is after last strong point */ 1985 { 1986 before = strongs[nn - 1]; 1987 1988 point->cur_u = before->cur_u + 1989 FT_MulFix( point->org_u - before->org_u, 1990 scale ); 1991 } 1992 else 1993 { 1994 FT_Pos u; 1995 1996 1997 after = strongs[nn]; 1998 1999 /* now interpolate point between before and after */ 2000 u = point->org_u; 2001 2002 if ( u == before->org_u ) 2003 point->cur_u = before->cur_u; 2004 2005 else if ( u == after->org_u ) 2006 point->cur_u = after->cur_u; 2007 2008 else 2009 point->cur_u = before->cur_u + 2010 FT_MulDiv( u - before->org_u, 2011 after->cur_u - before->cur_u, 2012 after->org_u - before->org_u ); 2013 } 2014 } 2015 psh_point_set_fitted( point ); 2016 } 2017 } 2018 2019 if ( strongs != strongs_0 ) 2020 FT_FREE( strongs ); 2021 2022 #endif /* 1 */ 2023 2024 } 2025 2026 2027 /* interpolate other points */ 2028 static void psh_glyph_interpolate_other_points(PSH_Glyph glyph,FT_Int dimension)2029 psh_glyph_interpolate_other_points( PSH_Glyph glyph, 2030 FT_Int dimension ) 2031 { 2032 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 2033 FT_Fixed scale = dim->scale_mult; 2034 FT_Fixed delta = dim->scale_delta; 2035 PSH_Contour contour = glyph->contours; 2036 FT_UInt num_contours = glyph->num_contours; 2037 2038 2039 for ( ; num_contours > 0; num_contours--, contour++ ) 2040 { 2041 PSH_Point start = contour->start; 2042 PSH_Point first, next, point; 2043 FT_UInt fit_count; 2044 2045 2046 /* count the number of strong points in this contour */ 2047 next = start + contour->count; 2048 fit_count = 0; 2049 first = 0; 2050 2051 for ( point = start; point < next; point++ ) 2052 if ( psh_point_is_fitted( point ) ) 2053 { 2054 if ( !first ) 2055 first = point; 2056 2057 fit_count++; 2058 } 2059 2060 /* if there are less than 2 fitted points in the contour, we */ 2061 /* simply scale and eventually translate the contour points */ 2062 if ( fit_count < 2 ) 2063 { 2064 if ( fit_count == 1 ) 2065 delta = first->cur_u - FT_MulFix( first->org_u, scale ); 2066 2067 for ( point = start; point < next; point++ ) 2068 if ( point != first ) 2069 point->cur_u = FT_MulFix( point->org_u, scale ) + delta; 2070 2071 goto Next_Contour; 2072 } 2073 2074 /* there are more than 2 strong points in this contour; we */ 2075 /* need to interpolate weak points between them */ 2076 start = first; 2077 do 2078 { 2079 point = first; 2080 2081 /* skip consecutive fitted points */ 2082 for (;;) 2083 { 2084 next = first->next; 2085 if ( next == start ) 2086 goto Next_Contour; 2087 2088 if ( !psh_point_is_fitted( next ) ) 2089 break; 2090 2091 first = next; 2092 } 2093 2094 /* find next fitted point after unfitted one */ 2095 for (;;) 2096 { 2097 next = next->next; 2098 if ( psh_point_is_fitted( next ) ) 2099 break; 2100 } 2101 2102 /* now interpolate between them */ 2103 { 2104 FT_Pos org_a, org_ab, cur_a, cur_ab; 2105 FT_Pos org_c, org_ac, cur_c; 2106 FT_Fixed scale_ab; 2107 2108 2109 if ( first->org_u <= next->org_u ) 2110 { 2111 org_a = first->org_u; 2112 cur_a = first->cur_u; 2113 org_ab = next->org_u - org_a; 2114 cur_ab = next->cur_u - cur_a; 2115 } 2116 else 2117 { 2118 org_a = next->org_u; 2119 cur_a = next->cur_u; 2120 org_ab = first->org_u - org_a; 2121 cur_ab = first->cur_u - cur_a; 2122 } 2123 2124 scale_ab = 0x10000L; 2125 if ( org_ab > 0 ) 2126 scale_ab = FT_DivFix( cur_ab, org_ab ); 2127 2128 point = first->next; 2129 do 2130 { 2131 org_c = point->org_u; 2132 org_ac = org_c - org_a; 2133 2134 if ( org_ac <= 0 ) 2135 { 2136 /* on the left of the interpolation zone */ 2137 cur_c = cur_a + FT_MulFix( org_ac, scale ); 2138 } 2139 else if ( org_ac >= org_ab ) 2140 { 2141 /* on the right on the interpolation zone */ 2142 cur_c = cur_a + cur_ab + FT_MulFix( org_ac - org_ab, scale ); 2143 } 2144 else 2145 { 2146 /* within the interpolation zone */ 2147 cur_c = cur_a + FT_MulFix( org_ac, scale_ab ); 2148 } 2149 2150 point->cur_u = cur_c; 2151 2152 point = point->next; 2153 2154 } while ( point != next ); 2155 } 2156 2157 /* keep going until all points in the contours have been processed */ 2158 first = next; 2159 2160 } while ( first != start ); 2161 2162 Next_Contour: 2163 ; 2164 } 2165 } 2166 2167 2168 /*************************************************************************/ 2169 /*************************************************************************/ 2170 /***** *****/ 2171 /***** HIGH-LEVEL INTERFACE *****/ 2172 /***** *****/ 2173 /*************************************************************************/ 2174 /*************************************************************************/ 2175 2176 FT_Error ps_hints_apply(PS_Hints ps_hints,FT_Outline * outline,PSH_Globals globals,FT_Render_Mode hint_mode)2177 ps_hints_apply( PS_Hints ps_hints, 2178 FT_Outline* outline, 2179 PSH_Globals globals, 2180 FT_Render_Mode hint_mode ) 2181 { 2182 PSH_GlyphRec glyphrec; 2183 PSH_Glyph glyph = &glyphrec; 2184 FT_Error error; 2185 #ifdef DEBUG_HINTER 2186 FT_Memory memory; 2187 #endif 2188 FT_Int dimension; 2189 2190 2191 /* something to do? */ 2192 if ( outline->n_points == 0 || outline->n_contours == 0 ) 2193 return PSH_Err_Ok; 2194 2195 #ifdef DEBUG_HINTER 2196 2197 memory = globals->memory; 2198 2199 if ( ps_debug_glyph ) 2200 { 2201 psh_glyph_done( ps_debug_glyph ); 2202 FT_FREE( ps_debug_glyph ); 2203 } 2204 2205 if ( FT_NEW( glyph ) ) 2206 return error; 2207 2208 ps_debug_glyph = glyph; 2209 2210 #endif /* DEBUG_HINTER */ 2211 2212 error = psh_glyph_init( glyph, outline, ps_hints, globals ); 2213 if ( error ) 2214 goto Exit; 2215 2216 /* try to optimize the y_scale so that the top of non-capital letters 2217 * is aligned on a pixel boundary whenever possible 2218 */ 2219 { 2220 PSH_Dimension dim_x = &glyph->globals->dimension[0]; 2221 PSH_Dimension dim_y = &glyph->globals->dimension[1]; 2222 2223 FT_Fixed x_scale = dim_x->scale_mult; 2224 FT_Fixed y_scale = dim_y->scale_mult; 2225 2226 FT_Fixed old_x_scale = x_scale; 2227 FT_Fixed old_y_scale = y_scale; 2228 2229 FT_Fixed scaled; 2230 FT_Fixed fitted; 2231 2232 FT_Bool rescale = FALSE; 2233 2234 2235 scaled = FT_MulFix( globals->blues.normal_top.zones->org_ref, y_scale ); 2236 fitted = FT_PIX_ROUND( scaled ); 2237 2238 if ( fitted != 0 && scaled != fitted ) 2239 { 2240 rescale = TRUE; 2241 2242 y_scale = FT_MulDiv( y_scale, fitted, scaled ); 2243 2244 if ( fitted < scaled ) 2245 x_scale -= x_scale / 50; 2246 2247 psh_globals_set_scale( glyph->globals, x_scale, y_scale, 0, 0 ); 2248 } 2249 2250 glyph->do_horz_hints = 1; 2251 glyph->do_vert_hints = 1; 2252 2253 glyph->do_horz_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO || 2254 hint_mode == FT_RENDER_MODE_LCD ); 2255 2256 glyph->do_vert_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO || 2257 hint_mode == FT_RENDER_MODE_LCD_V ); 2258 2259 glyph->do_stem_adjust = FT_BOOL( hint_mode != FT_RENDER_MODE_LIGHT ); 2260 2261 for ( dimension = 0; dimension < 2; dimension++ ) 2262 { 2263 /* load outline coordinates into glyph */ 2264 psh_glyph_load_points( glyph, dimension ); 2265 2266 /* compute local extrema */ 2267 psh_glyph_compute_extrema( glyph ); 2268 2269 /* compute aligned stem/hints positions */ 2270 psh_hint_table_align_hints( &glyph->hint_tables[dimension], 2271 glyph->globals, 2272 dimension, 2273 glyph ); 2274 2275 /* find strong points, align them, then interpolate others */ 2276 psh_glyph_find_strong_points( glyph, dimension ); 2277 if ( dimension == 1 ) 2278 psh_glyph_find_blue_points( &globals->blues, glyph ); 2279 psh_glyph_interpolate_strong_points( glyph, dimension ); 2280 psh_glyph_interpolate_normal_points( glyph, dimension ); 2281 psh_glyph_interpolate_other_points( glyph, dimension ); 2282 2283 /* save hinted coordinates back to outline */ 2284 psh_glyph_save_points( glyph, dimension ); 2285 2286 if ( rescale ) 2287 psh_globals_set_scale( glyph->globals, 2288 old_x_scale, old_y_scale, 0, 0 ); 2289 } 2290 } 2291 2292 Exit: 2293 2294 #ifndef DEBUG_HINTER 2295 psh_glyph_done( glyph ); 2296 #endif 2297 2298 return error; 2299 } 2300 2301 2302 /* END */ 2303