1 /**************************************************************************** 2 * 3 * pshalgo.c 4 * 5 * PostScript hinting algorithm (body). 6 * 7 * Copyright (C) 2001-2021 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_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, this is, use the */ 520 /* scaled distance between the centers of the hints to */ 521 /* compute the new position */ 522 par_org_center = parent->org_pos + ( parent->org_len >> 1 ); 523 par_cur_center = parent->cur_pos + ( parent->cur_len >> 1 ); 524 cur_org_center = hint->org_pos + ( hint->org_len >> 1 ); 525 526 cur_delta = FT_MulFix( cur_org_center - par_org_center, scale ); 527 pos = par_cur_center + cur_delta - ( len >> 1 ); 528 } 529 530 hint->cur_pos = pos; 531 hint->cur_len = fit_len; 532 533 /* Stem adjustment tries to snap stem widths to standard 534 * ones. This is important to prevent unpleasant rounding 535 * artefacts. 536 */ 537 if ( glyph->do_stem_adjust ) 538 { 539 if ( len <= 64 ) 540 { 541 /* the stem is less than one pixel; we will center it 542 * around the nearest pixel center 543 */ 544 if ( len >= 32 ) 545 { 546 /* This is a special case where we also widen the stem 547 * and align it to the pixel grid. 548 * 549 * stem_center = pos + (len/2) 550 * nearest_pixel_center = FT_ROUND(stem_center-32)+32 551 * new_pos = nearest_pixel_center-32 552 * = FT_ROUND(stem_center-32) 553 * = FT_FLOOR(stem_center-32+32) 554 * = FT_FLOOR(stem_center) 555 * new_len = 64 556 */ 557 pos = FT_PIX_FLOOR( pos + ( len >> 1 ) ); 558 len = 64; 559 } 560 else if ( len > 0 ) 561 { 562 /* This is a very small stem; we simply align it to the 563 * pixel grid, trying to find the minimum displacement. 564 * 565 * left = pos 566 * right = pos + len 567 * left_nearest_edge = ROUND(pos) 568 * right_nearest_edge = ROUND(right) 569 * 570 * if ( ABS(left_nearest_edge - left) <= 571 * ABS(right_nearest_edge - right) ) 572 * new_pos = left 573 * else 574 * new_pos = right 575 */ 576 FT_Pos left_nearest = FT_PIX_ROUND( pos ); 577 FT_Pos right_nearest = FT_PIX_ROUND( pos + len ); 578 FT_Pos left_disp = left_nearest - pos; 579 FT_Pos right_disp = right_nearest - ( pos + len ); 580 581 582 if ( left_disp < 0 ) 583 left_disp = -left_disp; 584 if ( right_disp < 0 ) 585 right_disp = -right_disp; 586 if ( left_disp <= right_disp ) 587 pos = left_nearest; 588 else 589 pos = right_nearest; 590 } 591 else 592 { 593 /* this is a ghost stem; we simply round it */ 594 pos = FT_PIX_ROUND( pos ); 595 } 596 } 597 else 598 { 599 len = psh_dimension_quantize_len( dim, len, 0 ); 600 } 601 } 602 603 /* now that we have a good hinted stem width, try to position */ 604 /* the stem along a pixel grid integer coordinate */ 605 hint->cur_pos = pos + psh_hint_snap_stem_side_delta( pos, len ); 606 hint->cur_len = len; 607 } 608 } 609 610 if ( do_snapping ) 611 { 612 pos = hint->cur_pos; 613 len = hint->cur_len; 614 615 if ( len < 64 ) 616 len = 64; 617 else 618 len = FT_PIX_ROUND( len ); 619 620 switch ( align.align ) 621 { 622 case PSH_BLUE_ALIGN_TOP: 623 hint->cur_pos = align.align_top - len; 624 hint->cur_len = len; 625 break; 626 627 case PSH_BLUE_ALIGN_BOT: 628 hint->cur_len = len; 629 break; 630 631 case PSH_BLUE_ALIGN_BOT | PSH_BLUE_ALIGN_TOP: 632 /* don't touch */ 633 break; 634 635 636 default: 637 hint->cur_len = len; 638 if ( len & 64 ) 639 pos = FT_PIX_FLOOR( pos + ( len >> 1 ) ) + 32; 640 else 641 pos = FT_PIX_ROUND( pos + ( len >> 1 ) ); 642 643 hint->cur_pos = pos - ( len >> 1 ); 644 hint->cur_len = len; 645 } 646 } 647 648 psh_hint_set_fitted( hint ); 649 650 #ifdef DEBUG_HINTER 651 if ( ps_debug_hint_func ) 652 ps_debug_hint_func( hint, dimension ); 653 #endif 654 } 655 } 656 657 658 #if 0 /* not used for now, experimental */ 659 660 /* 661 * A variant to perform "light" hinting (i.e. FT_RENDER_MODE_LIGHT) 662 * of stems 663 */ 664 static void 665 psh_hint_align_light( PSH_Hint hint, 666 PSH_Globals globals, 667 FT_Int dimension, 668 PSH_Glyph glyph ) 669 { 670 PSH_Dimension dim = &globals->dimension[dimension]; 671 FT_Fixed scale = dim->scale_mult; 672 FT_Fixed delta = dim->scale_delta; 673 674 675 if ( !psh_hint_is_fitted( hint ) ) 676 { 677 FT_Pos pos = FT_MulFix( hint->org_pos, scale ) + delta; 678 FT_Pos len = FT_MulFix( hint->org_len, scale ); 679 680 FT_Pos fit_len; 681 682 PSH_AlignmentRec align; 683 684 685 /* ignore stem alignments when requested through the hint flags */ 686 if ( ( dimension == 0 && !glyph->do_horz_hints ) || 687 ( dimension == 1 && !glyph->do_vert_hints ) ) 688 { 689 hint->cur_pos = pos; 690 hint->cur_len = len; 691 692 psh_hint_set_fitted( hint ); 693 return; 694 } 695 696 fit_len = len; 697 698 hint->cur_len = fit_len; 699 700 /* check blue zones for horizontal stems */ 701 align.align = PSH_BLUE_ALIGN_NONE; 702 align.align_bot = align.align_top = 0; 703 704 if ( dimension == 1 ) 705 psh_blues_snap_stem( &globals->blues, 706 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_NEW_ARRAY( glyph->points, outline->n_points ) || 1171 FT_NEW_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 if ( !( outline->tags[n] & FT_CURVE_TAG_ON ) ) 1232 point->flags = PSH_POINT_OFF; 1233 1234 dxi = vec[n].x - vec[n_prev].x; 1235 dyi = vec[n].y - vec[n_prev].y; 1236 1237 point->dir_in = psh_compute_dir( dxi, dyi ); 1238 1239 dxo = vec[n_next].x - vec[n].x; 1240 dyo = vec[n_next].y - vec[n].y; 1241 1242 point->dir_out = psh_compute_dir( dxo, dyo ); 1243 1244 /* detect smooth points */ 1245 if ( point->flags & PSH_POINT_OFF ) 1246 point->flags |= PSH_POINT_SMOOTH; 1247 1248 else if ( point->dir_in == point->dir_out ) 1249 { 1250 if ( point->dir_out != PSH_DIR_NONE || 1251 psh_corner_is_flat( dxi, dyi, dxo, dyo ) ) 1252 point->flags |= PSH_POINT_SMOOTH; 1253 } 1254 } 1255 } 1256 1257 glyph->outline = outline; 1258 glyph->globals = globals; 1259 1260 #ifdef COMPUTE_INFLEXS 1261 psh_glyph_load_points( glyph, 0 ); 1262 psh_glyph_compute_inflections( glyph ); 1263 #endif /* COMPUTE_INFLEXS */ 1264 1265 /* now deal with hints tables */ 1266 error = psh_hint_table_init( &glyph->hint_tables [0], 1267 &ps_hints->dimension[0].hints, 1268 &ps_hints->dimension[0].masks, 1269 &ps_hints->dimension[0].counters, 1270 memory ); 1271 if ( error ) 1272 goto Exit; 1273 1274 error = psh_hint_table_init( &glyph->hint_tables [1], 1275 &ps_hints->dimension[1].hints, 1276 &ps_hints->dimension[1].masks, 1277 &ps_hints->dimension[1].counters, 1278 memory ); 1279 if ( error ) 1280 goto Exit; 1281 1282 Exit: 1283 return error; 1284 } 1285 1286 1287 /* compute all extrema in a glyph for a given dimension */ 1288 static void psh_glyph_compute_extrema(PSH_Glyph glyph)1289 psh_glyph_compute_extrema( PSH_Glyph glyph ) 1290 { 1291 FT_UInt n; 1292 1293 1294 /* first of all, compute all local extrema */ 1295 for ( n = 0; n < glyph->num_contours; n++ ) 1296 { 1297 PSH_Point first = glyph->contours[n].start; 1298 PSH_Point point, before, after; 1299 1300 1301 if ( glyph->contours[n].count == 0 ) 1302 continue; 1303 1304 point = first; 1305 before = point; 1306 1307 do 1308 { 1309 before = before->prev; 1310 if ( before == first ) 1311 goto Skip; 1312 1313 } while ( before->org_u == point->org_u ); 1314 1315 first = point = before->next; 1316 1317 for (;;) 1318 { 1319 after = point; 1320 do 1321 { 1322 after = after->next; 1323 if ( after == first ) 1324 goto Next; 1325 1326 } while ( after->org_u == point->org_u ); 1327 1328 if ( before->org_u < point->org_u ) 1329 { 1330 if ( after->org_u < point->org_u ) 1331 { 1332 /* local maximum */ 1333 goto Extremum; 1334 } 1335 } 1336 else /* before->org_u > point->org_u */ 1337 { 1338 if ( after->org_u > point->org_u ) 1339 { 1340 /* local minimum */ 1341 Extremum: 1342 do 1343 { 1344 psh_point_set_extremum( point ); 1345 point = point->next; 1346 1347 } while ( point != after ); 1348 } 1349 } 1350 1351 before = after->prev; 1352 point = after; 1353 1354 } /* for */ 1355 1356 Next: 1357 ; 1358 } 1359 1360 /* for each extremum, determine its direction along the */ 1361 /* orthogonal axis */ 1362 for ( n = 0; n < glyph->num_points; n++ ) 1363 { 1364 PSH_Point point, before, after; 1365 1366 1367 point = &glyph->points[n]; 1368 before = point; 1369 after = point; 1370 1371 if ( psh_point_is_extremum( point ) ) 1372 { 1373 do 1374 { 1375 before = before->prev; 1376 if ( before == point ) 1377 goto Skip; 1378 1379 } while ( before->org_v == point->org_v ); 1380 1381 do 1382 { 1383 after = after->next; 1384 if ( after == point ) 1385 goto Skip; 1386 1387 } while ( after->org_v == point->org_v ); 1388 } 1389 1390 if ( before->org_v < point->org_v && 1391 after->org_v > point->org_v ) 1392 { 1393 psh_point_set_positive( point ); 1394 } 1395 else if ( before->org_v > point->org_v && 1396 after->org_v < point->org_v ) 1397 { 1398 psh_point_set_negative( point ); 1399 } 1400 1401 Skip: 1402 ; 1403 } 1404 } 1405 1406 1407 /* the min and max are based on contour orientation and fill rule */ 1408 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)1409 psh_hint_table_find_strong_points( PSH_Hint_Table table, 1410 PSH_Point point, 1411 FT_UInt count, 1412 FT_Int threshold, 1413 PSH_Dir major_dir ) 1414 { 1415 PSH_Hint* sort = table->sort; 1416 FT_UInt num_hints = table->num_hints; 1417 1418 1419 for ( ; count > 0; count--, point++ ) 1420 { 1421 PSH_Dir point_dir; 1422 FT_Pos org_u = point->org_u; 1423 1424 1425 if ( psh_point_is_strong( point ) ) 1426 continue; 1427 1428 point_dir = 1429 (PSH_Dir)( ( point->dir_in | point->dir_out ) & major_dir ); 1430 1431 if ( point_dir & ( PSH_DIR_DOWN | PSH_DIR_RIGHT ) ) 1432 { 1433 FT_UInt nn; 1434 1435 1436 for ( nn = 0; nn < num_hints; nn++ ) 1437 { 1438 PSH_Hint hint = sort[nn]; 1439 FT_Pos d = org_u - hint->org_pos; 1440 1441 1442 if ( d < threshold && -d < threshold ) 1443 { 1444 psh_point_set_strong( point ); 1445 point->flags2 |= PSH_POINT_EDGE_MIN; 1446 point->hint = hint; 1447 break; 1448 } 1449 } 1450 } 1451 else if ( point_dir & ( PSH_DIR_UP | PSH_DIR_LEFT ) ) 1452 { 1453 FT_UInt nn; 1454 1455 1456 for ( nn = 0; nn < num_hints; nn++ ) 1457 { 1458 PSH_Hint hint = sort[nn]; 1459 FT_Pos d = org_u - hint->org_pos - hint->org_len; 1460 1461 1462 if ( d < threshold && -d < threshold ) 1463 { 1464 psh_point_set_strong( point ); 1465 point->flags2 |= PSH_POINT_EDGE_MAX; 1466 point->hint = hint; 1467 break; 1468 } 1469 } 1470 } 1471 1472 #if 1 1473 else if ( psh_point_is_extremum( point ) ) 1474 { 1475 /* treat extrema as special cases for stem edge alignment */ 1476 FT_UInt nn, min_flag, max_flag; 1477 1478 1479 if ( major_dir == PSH_DIR_HORIZONTAL ) 1480 { 1481 min_flag = PSH_POINT_POSITIVE; 1482 max_flag = PSH_POINT_NEGATIVE; 1483 } 1484 else 1485 { 1486 min_flag = PSH_POINT_NEGATIVE; 1487 max_flag = PSH_POINT_POSITIVE; 1488 } 1489 1490 if ( point->flags2 & min_flag ) 1491 { 1492 for ( nn = 0; nn < num_hints; nn++ ) 1493 { 1494 PSH_Hint hint = sort[nn]; 1495 FT_Pos d = org_u - hint->org_pos; 1496 1497 1498 if ( d < threshold && -d < threshold ) 1499 { 1500 point->flags2 |= PSH_POINT_EDGE_MIN; 1501 point->hint = hint; 1502 psh_point_set_strong( point ); 1503 break; 1504 } 1505 } 1506 } 1507 else if ( point->flags2 & max_flag ) 1508 { 1509 for ( nn = 0; nn < num_hints; nn++ ) 1510 { 1511 PSH_Hint hint = sort[nn]; 1512 FT_Pos d = org_u - hint->org_pos - hint->org_len; 1513 1514 1515 if ( d < threshold && -d < threshold ) 1516 { 1517 point->flags2 |= PSH_POINT_EDGE_MAX; 1518 point->hint = hint; 1519 psh_point_set_strong( point ); 1520 break; 1521 } 1522 } 1523 } 1524 1525 if ( !point->hint ) 1526 { 1527 for ( nn = 0; nn < num_hints; nn++ ) 1528 { 1529 PSH_Hint hint = sort[nn]; 1530 1531 1532 if ( org_u >= hint->org_pos && 1533 org_u <= ADD_INT( hint->org_pos, hint->org_len ) ) 1534 { 1535 point->hint = hint; 1536 break; 1537 } 1538 } 1539 } 1540 } 1541 1542 #endif /* 1 */ 1543 } 1544 } 1545 1546 1547 /* the accepted shift for strong points in fractional pixels */ 1548 #define PSH_STRONG_THRESHOLD 32 1549 1550 /* the maximum shift value in font units */ 1551 #define PSH_STRONG_THRESHOLD_MAXIMUM 30 1552 1553 1554 /* find strong points in a glyph */ 1555 static void psh_glyph_find_strong_points(PSH_Glyph glyph,FT_Int dimension)1556 psh_glyph_find_strong_points( PSH_Glyph glyph, 1557 FT_Int dimension ) 1558 { 1559 /* a point is `strong' if it is located on a stem edge and */ 1560 /* has an `in' or `out' tangent parallel to the hint's direction */ 1561 1562 PSH_Hint_Table table = &glyph->hint_tables[dimension]; 1563 PS_Mask mask = table->hint_masks->masks; 1564 FT_UInt num_masks = table->hint_masks->num_masks; 1565 FT_UInt first = 0; 1566 PSH_Dir major_dir = ( dimension == 0 ) ? PSH_DIR_VERTICAL 1567 : PSH_DIR_HORIZONTAL; 1568 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1569 FT_Fixed scale = dim->scale_mult; 1570 FT_Int threshold; 1571 1572 1573 threshold = (FT_Int)FT_DivFix( PSH_STRONG_THRESHOLD, scale ); 1574 if ( threshold > PSH_STRONG_THRESHOLD_MAXIMUM ) 1575 threshold = PSH_STRONG_THRESHOLD_MAXIMUM; 1576 1577 /* process secondary hints to `selected' points */ 1578 if ( num_masks > 1 && glyph->num_points > 0 ) 1579 { 1580 /* the `endchar' op can reduce the number of points */ 1581 first = mask->end_point > glyph->num_points 1582 ? glyph->num_points 1583 : mask->end_point; 1584 mask++; 1585 for ( ; num_masks > 1; num_masks--, mask++ ) 1586 { 1587 FT_UInt next = FT_MIN( mask->end_point, glyph->num_points ); 1588 1589 1590 if ( next > first ) 1591 { 1592 FT_UInt count = next - first; 1593 PSH_Point point = glyph->points + first; 1594 1595 1596 psh_hint_table_activate_mask( table, mask ); 1597 1598 psh_hint_table_find_strong_points( table, point, count, 1599 threshold, major_dir ); 1600 } 1601 first = next; 1602 } 1603 } 1604 1605 /* process primary hints for all points */ 1606 if ( num_masks == 1 ) 1607 { 1608 FT_UInt count = glyph->num_points; 1609 PSH_Point point = glyph->points; 1610 1611 1612 psh_hint_table_activate_mask( table, table->hint_masks->masks ); 1613 1614 psh_hint_table_find_strong_points( table, point, count, 1615 threshold, major_dir ); 1616 } 1617 1618 /* now, certain points may have been attached to a hint and */ 1619 /* not marked as strong; update their flags then */ 1620 { 1621 FT_UInt count = glyph->num_points; 1622 PSH_Point point = glyph->points; 1623 1624 1625 for ( ; count > 0; count--, point++ ) 1626 if ( point->hint && !psh_point_is_strong( point ) ) 1627 psh_point_set_strong( point ); 1628 } 1629 } 1630 1631 1632 /* find points in a glyph which are in a blue zone and have `in' or */ 1633 /* `out' tangents parallel to the horizontal axis */ 1634 static void psh_glyph_find_blue_points(PSH_Blues blues,PSH_Glyph glyph)1635 psh_glyph_find_blue_points( PSH_Blues blues, 1636 PSH_Glyph glyph ) 1637 { 1638 PSH_Blue_Table table; 1639 PSH_Blue_Zone zone; 1640 FT_UInt glyph_count = glyph->num_points; 1641 FT_UInt blue_count; 1642 PSH_Point point = glyph->points; 1643 1644 1645 for ( ; glyph_count > 0; glyph_count--, point++ ) 1646 { 1647 FT_Pos y; 1648 1649 1650 /* check tangents */ 1651 if ( !( point->dir_in & PSH_DIR_HORIZONTAL ) && 1652 !( point->dir_out & PSH_DIR_HORIZONTAL ) ) 1653 continue; 1654 1655 /* skip strong points */ 1656 if ( psh_point_is_strong( point ) ) 1657 continue; 1658 1659 y = point->org_u; 1660 1661 /* look up top zones */ 1662 table = &blues->normal_top; 1663 blue_count = table->count; 1664 zone = table->zones; 1665 1666 for ( ; blue_count > 0; blue_count--, zone++ ) 1667 { 1668 FT_Pos delta = y - zone->org_bottom; 1669 1670 1671 if ( delta < -blues->blue_fuzz ) 1672 break; 1673 1674 if ( y <= zone->org_top + blues->blue_fuzz ) 1675 if ( blues->no_overshoots || delta <= blues->blue_threshold ) 1676 { 1677 point->cur_u = zone->cur_bottom; 1678 psh_point_set_strong( point ); 1679 psh_point_set_fitted( point ); 1680 } 1681 } 1682 1683 /* look up bottom zones */ 1684 table = &blues->normal_bottom; 1685 blue_count = table->count; 1686 zone = table->zones + blue_count - 1; 1687 1688 for ( ; blue_count > 0; blue_count--, zone-- ) 1689 { 1690 FT_Pos delta = zone->org_top - y; 1691 1692 1693 if ( delta < -blues->blue_fuzz ) 1694 break; 1695 1696 if ( y >= zone->org_bottom - blues->blue_fuzz ) 1697 if ( blues->no_overshoots || delta < blues->blue_threshold ) 1698 { 1699 point->cur_u = zone->cur_top; 1700 psh_point_set_strong( point ); 1701 psh_point_set_fitted( point ); 1702 } 1703 } 1704 } 1705 } 1706 1707 1708 /* interpolate strong points with the help of hinted coordinates */ 1709 static void psh_glyph_interpolate_strong_points(PSH_Glyph glyph,FT_Int dimension)1710 psh_glyph_interpolate_strong_points( PSH_Glyph glyph, 1711 FT_Int dimension ) 1712 { 1713 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1714 FT_Fixed scale = dim->scale_mult; 1715 1716 FT_UInt count = glyph->num_points; 1717 PSH_Point point = glyph->points; 1718 1719 1720 for ( ; count > 0; count--, point++ ) 1721 { 1722 PSH_Hint hint = point->hint; 1723 1724 1725 if ( hint ) 1726 { 1727 FT_Pos delta; 1728 1729 1730 if ( psh_point_is_edge_min( point ) ) 1731 point->cur_u = hint->cur_pos; 1732 1733 else if ( psh_point_is_edge_max( point ) ) 1734 point->cur_u = hint->cur_pos + hint->cur_len; 1735 1736 else 1737 { 1738 delta = point->org_u - hint->org_pos; 1739 1740 if ( delta <= 0 ) 1741 point->cur_u = hint->cur_pos + FT_MulFix( delta, scale ); 1742 1743 else if ( delta >= hint->org_len ) 1744 point->cur_u = hint->cur_pos + hint->cur_len + 1745 FT_MulFix( delta - hint->org_len, scale ); 1746 1747 else /* hint->org_len > 0 */ 1748 point->cur_u = hint->cur_pos + 1749 FT_MulDiv( delta, hint->cur_len, 1750 hint->org_len ); 1751 } 1752 psh_point_set_fitted( point ); 1753 } 1754 } 1755 } 1756 1757 1758 #define PSH_MAX_STRONG_INTERNAL 16 1759 1760 static void psh_glyph_interpolate_normal_points(PSH_Glyph glyph,FT_Int dimension)1761 psh_glyph_interpolate_normal_points( PSH_Glyph glyph, 1762 FT_Int dimension ) 1763 { 1764 1765 #if 1 1766 /* first technique: a point is strong if it is a local extremum */ 1767 1768 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1769 FT_Fixed scale = dim->scale_mult; 1770 FT_Memory memory = glyph->memory; 1771 1772 PSH_Point* strongs = NULL; 1773 PSH_Point strongs_0[PSH_MAX_STRONG_INTERNAL]; 1774 FT_UInt num_strongs = 0; 1775 1776 PSH_Point points = glyph->points; 1777 PSH_Point points_end = points + glyph->num_points; 1778 PSH_Point point; 1779 1780 1781 /* first count the number of strong points */ 1782 for ( point = points; point < points_end; point++ ) 1783 { 1784 if ( psh_point_is_strong( point ) ) 1785 num_strongs++; 1786 } 1787 1788 if ( num_strongs == 0 ) /* nothing to do here */ 1789 return; 1790 1791 /* allocate an array to store a list of points, */ 1792 /* stored in increasing org_u order */ 1793 if ( num_strongs <= PSH_MAX_STRONG_INTERNAL ) 1794 strongs = strongs_0; 1795 else 1796 { 1797 FT_Error error; 1798 1799 1800 if ( FT_NEW_ARRAY( strongs, num_strongs ) ) 1801 return; 1802 } 1803 1804 num_strongs = 0; 1805 for ( point = points; point < points_end; point++ ) 1806 { 1807 PSH_Point* insert; 1808 1809 1810 if ( !psh_point_is_strong( point ) ) 1811 continue; 1812 1813 for ( insert = strongs + num_strongs; insert > strongs; insert-- ) 1814 { 1815 if ( insert[-1]->org_u <= point->org_u ) 1816 break; 1817 1818 insert[0] = insert[-1]; 1819 } 1820 insert[0] = point; 1821 num_strongs++; 1822 } 1823 1824 /* now try to interpolate all normal points */ 1825 for ( point = points; point < points_end; point++ ) 1826 { 1827 if ( psh_point_is_strong( point ) ) 1828 continue; 1829 1830 /* sometimes, some local extrema are smooth points */ 1831 if ( psh_point_is_smooth( point ) ) 1832 { 1833 if ( point->dir_in == PSH_DIR_NONE || 1834 point->dir_in != point->dir_out ) 1835 continue; 1836 1837 if ( !psh_point_is_extremum( point ) && 1838 !psh_point_is_inflex( point ) ) 1839 continue; 1840 1841 point->flags &= ~PSH_POINT_SMOOTH; 1842 } 1843 1844 /* find best enclosing point coordinates then interpolate */ 1845 { 1846 PSH_Point before, after; 1847 FT_UInt nn; 1848 1849 1850 for ( nn = 0; nn < num_strongs; nn++ ) 1851 if ( strongs[nn]->org_u > point->org_u ) 1852 break; 1853 1854 if ( nn == 0 ) /* point before the first strong point */ 1855 { 1856 after = strongs[0]; 1857 1858 point->cur_u = after->cur_u + 1859 FT_MulFix( point->org_u - after->org_u, 1860 scale ); 1861 } 1862 else 1863 { 1864 before = strongs[nn - 1]; 1865 1866 for ( nn = num_strongs; nn > 0; nn-- ) 1867 if ( strongs[nn - 1]->org_u < point->org_u ) 1868 break; 1869 1870 if ( nn == num_strongs ) /* point is after last strong point */ 1871 { 1872 before = strongs[nn - 1]; 1873 1874 point->cur_u = before->cur_u + 1875 FT_MulFix( point->org_u - before->org_u, 1876 scale ); 1877 } 1878 else 1879 { 1880 FT_Pos u; 1881 1882 1883 after = strongs[nn]; 1884 1885 /* now interpolate point between before and after */ 1886 u = point->org_u; 1887 1888 if ( u == before->org_u ) 1889 point->cur_u = before->cur_u; 1890 1891 else if ( u == after->org_u ) 1892 point->cur_u = after->cur_u; 1893 1894 else 1895 point->cur_u = before->cur_u + 1896 FT_MulDiv( u - before->org_u, 1897 after->cur_u - before->cur_u, 1898 after->org_u - before->org_u ); 1899 } 1900 } 1901 psh_point_set_fitted( point ); 1902 } 1903 } 1904 1905 if ( strongs != strongs_0 ) 1906 FT_FREE( strongs ); 1907 1908 #endif /* 1 */ 1909 1910 } 1911 1912 1913 /* interpolate other points */ 1914 static void psh_glyph_interpolate_other_points(PSH_Glyph glyph,FT_Int dimension)1915 psh_glyph_interpolate_other_points( PSH_Glyph glyph, 1916 FT_Int dimension ) 1917 { 1918 PSH_Dimension dim = &glyph->globals->dimension[dimension]; 1919 FT_Fixed scale = dim->scale_mult; 1920 FT_Fixed delta = dim->scale_delta; 1921 PSH_Contour contour = glyph->contours; 1922 FT_UInt num_contours = glyph->num_contours; 1923 1924 1925 for ( ; num_contours > 0; num_contours--, contour++ ) 1926 { 1927 PSH_Point start = contour->start; 1928 PSH_Point first, next, point; 1929 FT_UInt fit_count; 1930 1931 1932 /* count the number of strong points in this contour */ 1933 next = start + contour->count; 1934 fit_count = 0; 1935 first = NULL; 1936 1937 for ( point = start; point < next; point++ ) 1938 if ( psh_point_is_fitted( point ) ) 1939 { 1940 if ( !first ) 1941 first = point; 1942 1943 fit_count++; 1944 } 1945 1946 /* if there are less than 2 fitted points in the contour, we */ 1947 /* simply scale and eventually translate the contour points */ 1948 if ( fit_count < 2 ) 1949 { 1950 if ( fit_count == 1 ) 1951 delta = first->cur_u - FT_MulFix( first->org_u, scale ); 1952 1953 for ( point = start; point < next; point++ ) 1954 if ( point != first ) 1955 point->cur_u = FT_MulFix( point->org_u, scale ) + delta; 1956 1957 goto Next_Contour; 1958 } 1959 1960 /* there are more than 2 strong points in this contour; we */ 1961 /* need to interpolate weak points between them */ 1962 start = first; 1963 do 1964 { 1965 /* skip consecutive fitted points */ 1966 for (;;) 1967 { 1968 next = first->next; 1969 if ( next == start ) 1970 goto Next_Contour; 1971 1972 if ( !psh_point_is_fitted( next ) ) 1973 break; 1974 1975 first = next; 1976 } 1977 1978 /* find next fitted point after unfitted one */ 1979 for (;;) 1980 { 1981 next = next->next; 1982 if ( psh_point_is_fitted( next ) ) 1983 break; 1984 } 1985 1986 /* now interpolate between them */ 1987 { 1988 FT_Pos org_a, org_ab, cur_a, cur_ab; 1989 FT_Pos org_c, org_ac, cur_c; 1990 FT_Fixed scale_ab; 1991 1992 1993 if ( first->org_u <= next->org_u ) 1994 { 1995 org_a = first->org_u; 1996 cur_a = first->cur_u; 1997 org_ab = next->org_u - org_a; 1998 cur_ab = next->cur_u - cur_a; 1999 } 2000 else 2001 { 2002 org_a = next->org_u; 2003 cur_a = next->cur_u; 2004 org_ab = first->org_u - org_a; 2005 cur_ab = first->cur_u - cur_a; 2006 } 2007 2008 scale_ab = 0x10000L; 2009 if ( org_ab > 0 ) 2010 scale_ab = FT_DivFix( cur_ab, org_ab ); 2011 2012 point = first->next; 2013 do 2014 { 2015 org_c = point->org_u; 2016 org_ac = org_c - org_a; 2017 2018 if ( org_ac <= 0 ) 2019 { 2020 /* on the left of the interpolation zone */ 2021 cur_c = cur_a + FT_MulFix( org_ac, scale ); 2022 } 2023 else if ( org_ac >= org_ab ) 2024 { 2025 /* on the right on the interpolation zone */ 2026 cur_c = cur_a + cur_ab + FT_MulFix( org_ac - org_ab, scale ); 2027 } 2028 else 2029 { 2030 /* within the interpolation zone */ 2031 cur_c = cur_a + FT_MulFix( org_ac, scale_ab ); 2032 } 2033 2034 point->cur_u = cur_c; 2035 2036 point = point->next; 2037 2038 } while ( point != next ); 2039 } 2040 2041 /* keep going until all points in the contours have been processed */ 2042 first = next; 2043 2044 } while ( first != start ); 2045 2046 Next_Contour: 2047 ; 2048 } 2049 } 2050 2051 2052 /*************************************************************************/ 2053 /*************************************************************************/ 2054 /***** *****/ 2055 /***** HIGH-LEVEL INTERFACE *****/ 2056 /***** *****/ 2057 /*************************************************************************/ 2058 /*************************************************************************/ 2059 2060 FT_Error ps_hints_apply(PS_Hints ps_hints,FT_Outline * outline,PSH_Globals globals,FT_Render_Mode hint_mode)2061 ps_hints_apply( PS_Hints ps_hints, 2062 FT_Outline* outline, 2063 PSH_Globals globals, 2064 FT_Render_Mode hint_mode ) 2065 { 2066 PSH_GlyphRec glyphrec; 2067 PSH_Glyph glyph = &glyphrec; 2068 FT_Error error; 2069 #ifdef DEBUG_HINTER 2070 FT_Memory memory; 2071 #endif 2072 FT_Int dimension; 2073 2074 2075 /* something to do? */ 2076 if ( outline->n_points == 0 || outline->n_contours == 0 ) 2077 return FT_Err_Ok; 2078 2079 #ifdef DEBUG_HINTER 2080 2081 memory = globals->memory; 2082 2083 if ( ps_debug_glyph ) 2084 { 2085 psh_glyph_done( ps_debug_glyph ); 2086 FT_FREE( ps_debug_glyph ); 2087 } 2088 2089 if ( FT_NEW( glyph ) ) 2090 return error; 2091 2092 ps_debug_glyph = glyph; 2093 2094 #endif /* DEBUG_HINTER */ 2095 2096 error = psh_glyph_init( glyph, outline, ps_hints, globals ); 2097 if ( error ) 2098 goto Exit; 2099 2100 /* try to optimize the y_scale so that the top of non-capital letters 2101 * is aligned on a pixel boundary whenever possible 2102 */ 2103 { 2104 PSH_Dimension dim_x = &glyph->globals->dimension[0]; 2105 PSH_Dimension dim_y = &glyph->globals->dimension[1]; 2106 2107 FT_Fixed x_scale = dim_x->scale_mult; 2108 FT_Fixed y_scale = dim_y->scale_mult; 2109 2110 FT_Fixed old_x_scale = x_scale; 2111 FT_Fixed old_y_scale = y_scale; 2112 2113 FT_Fixed scaled; 2114 FT_Fixed fitted; 2115 2116 FT_Bool rescale = FALSE; 2117 2118 2119 scaled = FT_MulFix( globals->blues.normal_top.zones->org_ref, y_scale ); 2120 fitted = FT_PIX_ROUND( scaled ); 2121 2122 if ( fitted != 0 && scaled != fitted ) 2123 { 2124 rescale = TRUE; 2125 2126 y_scale = FT_MulDiv( y_scale, fitted, scaled ); 2127 2128 if ( fitted < scaled ) 2129 x_scale -= x_scale / 50; 2130 2131 psh_globals_set_scale( glyph->globals, x_scale, y_scale, 0, 0 ); 2132 } 2133 2134 glyph->do_horz_hints = 1; 2135 glyph->do_vert_hints = 1; 2136 2137 glyph->do_horz_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO || 2138 hint_mode == FT_RENDER_MODE_LCD ); 2139 2140 glyph->do_vert_snapping = FT_BOOL( hint_mode == FT_RENDER_MODE_MONO || 2141 hint_mode == FT_RENDER_MODE_LCD_V ); 2142 2143 glyph->do_stem_adjust = FT_BOOL( hint_mode != FT_RENDER_MODE_LIGHT ); 2144 2145 for ( dimension = 0; dimension < 2; dimension++ ) 2146 { 2147 /* load outline coordinates into glyph */ 2148 psh_glyph_load_points( glyph, dimension ); 2149 2150 /* compute local extrema */ 2151 psh_glyph_compute_extrema( glyph ); 2152 2153 /* compute aligned stem/hints positions */ 2154 psh_hint_table_align_hints( &glyph->hint_tables[dimension], 2155 glyph->globals, 2156 dimension, 2157 glyph ); 2158 2159 /* find strong points, align them, then interpolate others */ 2160 psh_glyph_find_strong_points( glyph, dimension ); 2161 if ( dimension == 1 ) 2162 psh_glyph_find_blue_points( &globals->blues, glyph ); 2163 psh_glyph_interpolate_strong_points( glyph, dimension ); 2164 psh_glyph_interpolate_normal_points( glyph, dimension ); 2165 psh_glyph_interpolate_other_points( glyph, dimension ); 2166 2167 /* save hinted coordinates back to outline */ 2168 psh_glyph_save_points( glyph, dimension ); 2169 2170 if ( rescale ) 2171 psh_globals_set_scale( glyph->globals, 2172 old_x_scale, old_y_scale, 0, 0 ); 2173 } 2174 } 2175 2176 Exit: 2177 2178 #ifndef DEBUG_HINTER 2179 psh_glyph_done( glyph ); 2180 #endif 2181 2182 return error; 2183 } 2184 2185 2186 /* END */ 2187