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