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