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