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