1 /***************************************************************************/ 2 /* */ 3 /* pshalgo1.c */ 4 /* */ 5 /* PostScript hinting algorithm 1 (body). */ 6 /* */ 7 /* Copyright 2001, 2002 by */ 8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */ 9 /* */ 10 /* This file is part of the FreeType project, and may only be used */ 11 /* modified and distributed under the terms of the FreeType project */ 12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ 13 /* this file you indicate that you have read the license and */ 14 /* understand and accept it fully. */ 15 /* */ 16 /***************************************************************************/ 17 18 19 #include <ft2build.h> 20 #include FT_INTERNAL_OBJECTS_H 21 #include FT_INTERNAL_DEBUG_H 22 #include "pshalgo1.h" 23 24 #undef FT_COMPONENT 25 #define FT_COMPONENT trace_pshalgo1 26 27 #ifdef DEBUG_HINTER 28 PSH1_Hint_Table ps1_debug_hint_table = 0; 29 PSH1_HintFunc ps1_debug_hint_func = 0; 30 #endif 31 32 33 /************************************************************************/ 34 /************************************************************************/ 35 /***** *****/ 36 /***** BASIC HINTS RECORDINGS *****/ 37 /***** *****/ 38 /************************************************************************/ 39 /************************************************************************/ 40 41 /* return true iff two stem hints overlap */ 42 static FT_Int psh1_hint_overlap(PSH1_Hint hint1,PSH1_Hint hint2)43 psh1_hint_overlap( PSH1_Hint hint1, 44 PSH1_Hint hint2 ) 45 { 46 return ( hint1->org_pos + hint1->org_len >= hint2->org_pos && 47 hint2->org_pos + hint2->org_len >= hint1->org_pos ); 48 } 49 50 51 /* destroy hints table */ 52 static void psh1_hint_table_done(PSH1_Hint_Table table,FT_Memory memory)53 psh1_hint_table_done( PSH1_Hint_Table table, 54 FT_Memory memory ) 55 { 56 FT_FREE( table->zones ); 57 table->num_zones = 0; 58 table->zone = 0; 59 60 FT_FREE( table->sort ); 61 FT_FREE( table->hints ); 62 table->num_hints = 0; 63 table->max_hints = 0; 64 table->sort_global = 0; 65 } 66 67 68 /* deactivate all hints in a table */ 69 static void psh1_hint_table_deactivate(PSH1_Hint_Table table)70 psh1_hint_table_deactivate( PSH1_Hint_Table table ) 71 { 72 FT_UInt count = table->max_hints; 73 PSH1_Hint hint = table->hints; 74 75 76 for ( ; count > 0; count--, hint++ ) 77 { 78 psh1_hint_deactivate( hint ); 79 hint->order = -1; 80 } 81 } 82 83 84 /* internal function used to record a new hint */ 85 static void psh1_hint_table_record(PSH1_Hint_Table table,FT_UInt idx)86 psh1_hint_table_record( PSH1_Hint_Table table, 87 FT_UInt idx ) 88 { 89 PSH1_Hint hint = table->hints + idx; 90 91 92 if ( idx >= table->max_hints ) 93 { 94 FT_ERROR(( "%s.activate: invalid hint index %d\n", idx )); 95 return; 96 } 97 98 /* ignore active hints */ 99 if ( psh1_hint_is_active( hint ) ) 100 return; 101 102 psh1_hint_activate( hint ); 103 104 /* now scan the current active hint set in order to determine */ 105 /* if we are overlapping with another segment */ 106 { 107 PSH1_Hint* sorted = table->sort_global; 108 FT_UInt count = table->num_hints; 109 PSH1_Hint hint2; 110 111 112 hint->parent = 0; 113 for ( ; count > 0; count--, sorted++ ) 114 { 115 hint2 = sorted[0]; 116 117 if ( psh1_hint_overlap( hint, hint2 ) ) 118 { 119 hint->parent = hint2; 120 break; 121 } 122 } 123 } 124 125 if ( table->num_hints < table->max_hints ) 126 table->sort_global[table->num_hints++] = hint; 127 else 128 FT_ERROR(( "%s.activate: too many sorted hints! BUG!\n", 129 "ps.fitter" )); 130 } 131 132 133 static void psh1_hint_table_record_mask(PSH1_Hint_Table table,PS_Mask hint_mask)134 psh1_hint_table_record_mask( PSH1_Hint_Table table, 135 PS_Mask hint_mask ) 136 { 137 FT_Int mask = 0, val = 0; 138 FT_Byte* cursor = hint_mask->bytes; 139 FT_UInt idx, limit; 140 141 142 limit = hint_mask->num_bits; 143 144 if ( limit != table->max_hints ) 145 FT_ERROR(( "%s.activate_mask: invalid bit count (%d instead of %d)\n", 146 "ps.fitter", hint_mask->num_bits, table->max_hints )); 147 148 for ( idx = 0; idx < limit; idx++ ) 149 { 150 if ( mask == 0 ) 151 { 152 val = *cursor++; 153 mask = 0x80; 154 } 155 156 if ( val & mask ) 157 psh1_hint_table_record( table, idx ); 158 159 mask >>= 1; 160 } 161 } 162 163 164 /* create hints table */ 165 static FT_Error psh1_hint_table_init(PSH1_Hint_Table table,PS_Hint_Table hints,PS_Mask_Table hint_masks,PS_Mask_Table counter_masks,FT_Memory memory)166 psh1_hint_table_init( PSH1_Hint_Table table, 167 PS_Hint_Table hints, 168 PS_Mask_Table hint_masks, 169 PS_Mask_Table counter_masks, 170 FT_Memory memory ) 171 { 172 FT_UInt count = hints->num_hints; 173 FT_Error error; 174 175 FT_UNUSED( counter_masks ); 176 177 178 /* allocate our tables */ 179 if ( FT_NEW_ARRAY( table->sort, 2 * count ) || 180 FT_NEW_ARRAY( table->hints, count ) || 181 FT_NEW_ARRAY( table->zones, 2 * count + 1 ) ) 182 goto Exit; 183 184 table->max_hints = count; 185 table->sort_global = table->sort + count; 186 table->num_hints = 0; 187 table->num_zones = 0; 188 table->zone = 0; 189 190 /* now, initialize the "hints" array */ 191 { 192 PSH1_Hint write = table->hints; 193 PS_Hint read = hints->hints; 194 195 196 for ( ; count > 0; count--, write++, read++ ) 197 { 198 write->org_pos = read->pos; 199 write->org_len = read->len; 200 write->flags = read->flags; 201 } 202 } 203 204 /* we now need to determine the initial "parent" stems; first */ 205 /* activate the hints that are given by the initial hint masks */ 206 if ( hint_masks ) 207 { 208 FT_UInt Count = hint_masks->num_masks; 209 PS_Mask Mask = hint_masks->masks; 210 211 212 table->hint_masks = hint_masks; 213 214 for ( ; Count > 0; Count--, Mask++ ) 215 psh1_hint_table_record_mask( table, Mask ); 216 } 217 218 /* now, do a linear parse in case some hints were left alone */ 219 if ( table->num_hints != table->max_hints ) 220 { 221 FT_UInt Index, Count; 222 223 224 FT_ERROR(( "%s.init: missing/incorrect hint masks!\n" )); 225 Count = table->max_hints; 226 for ( Index = 0; Index < Count; Index++ ) 227 psh1_hint_table_record( table, Index ); 228 } 229 230 Exit: 231 return error; 232 } 233 234 235 static void psh1_hint_table_activate_mask(PSH1_Hint_Table table,PS_Mask hint_mask)236 psh1_hint_table_activate_mask( PSH1_Hint_Table table, 237 PS_Mask hint_mask ) 238 { 239 FT_Int mask = 0, val = 0; 240 FT_Byte* cursor = hint_mask->bytes; 241 FT_UInt idx, limit, count; 242 243 244 limit = hint_mask->num_bits; 245 count = 0; 246 247 psh1_hint_table_deactivate( table ); 248 249 for ( idx = 0; idx < limit; idx++ ) 250 { 251 if ( mask == 0 ) 252 { 253 val = *cursor++; 254 mask = 0x80; 255 } 256 257 if ( val & mask ) 258 { 259 PSH1_Hint hint = &table->hints[idx]; 260 261 262 if ( !psh1_hint_is_active( hint ) ) 263 { 264 PSH1_Hint* sort = table->sort; 265 FT_UInt count2; 266 PSH1_Hint hint2; 267 268 269 for ( count2 = count; count2 > 0; count2--, sort++ ) 270 { 271 hint2 = sort[0]; 272 if ( psh1_hint_overlap( hint, hint2 ) ) 273 { 274 FT_ERROR(( "%s.activate_mask: found overlapping hints\n", 275 "psf.hint" )); 276 break; 277 } 278 } 279 280 if ( count2 == 0 ) 281 { 282 psh1_hint_activate( hint ); 283 if ( count < table->max_hints ) 284 table->sort[count++] = hint; 285 else 286 FT_ERROR(( "%s.activate_mask: too many active hints\n", 287 "psf.hint" )); 288 } 289 } 290 } 291 292 mask >>= 1; 293 } 294 table->num_hints = count; 295 296 /* now, sort the hints; they are guaranteed to not overlap */ 297 /* so we can compare their "org_pos" field directly */ 298 { 299 FT_Int i1, i2; 300 PSH1_Hint hint1, hint2; 301 PSH1_Hint* sort = table->sort; 302 303 304 /* a simple bubble sort will do, since in 99% of cases, the hints */ 305 /* will be already sorted; and the sort will be linear */ 306 for ( i1 = 1; i1 < (FT_Int)count; i1++ ) 307 { 308 hint1 = sort[i1]; 309 310 for ( i2 = i1 - 1; i2 >= 0; i2-- ) 311 { 312 hint2 = sort[i2]; 313 if ( hint2->org_pos < hint1->org_pos ) 314 break; 315 316 sort[i2 + 1] = hint2; 317 sort[i2] = hint1; 318 } 319 } 320 } 321 } 322 323 324 /*************************************************************************/ 325 /*************************************************************************/ 326 /***** *****/ 327 /***** HINTS GRID-FITTING AND OPTIMIZATION *****/ 328 /***** *****/ 329 /*************************************************************************/ 330 /*************************************************************************/ 331 332 #ifdef DEBUG_HINTER 333 void ps_simple_scale(PSH1_Hint_Table table,FT_Fixed scale,FT_Fixed delta,FT_Int vertical)334 ps_simple_scale( PSH1_Hint_Table table, 335 FT_Fixed scale, 336 FT_Fixed delta, 337 FT_Int vertical ) 338 { 339 PSH1_Hint hint; 340 FT_UInt count; 341 342 343 for ( count = 0; count < table->num_hints; count++ ) 344 { 345 hint = table->sort[count]; 346 if ( psh1_hint_is_active( hint ) ) 347 { 348 hint->cur_pos = FT_MulFix( hint->org_pos, scale ) + delta; 349 hint->cur_len = FT_MulFix( hint->org_len, scale ); 350 351 if ( ps1_debug_hint_func ) 352 ps1_debug_hint_func( hint, vertical ); 353 } 354 } 355 } 356 #endif 357 358 359 FT_LOCAL_DEF( FT_Error ) psh1_hint_table_optimize(PSH1_Hint_Table table,PSH_Globals globals,FT_Outline * outline,FT_Int vertical)360 psh1_hint_table_optimize( PSH1_Hint_Table table, 361 PSH_Globals globals, 362 FT_Outline* outline, 363 FT_Int vertical ) 364 { 365 PSH_Dimension dim = &globals->dimension[vertical]; 366 FT_Fixed scale = dim->scale_mult; 367 FT_Fixed delta = dim->scale_delta; 368 369 FT_UNUSED( outline ); 370 371 372 #ifdef DEBUG_HINTER 373 if ( ps_debug_no_vert_hints && vertical ) 374 { 375 ps_simple_scale( table, scale, delta, vertical ); 376 return 0; 377 } 378 379 if ( ps_debug_no_horz_hints && !vertical ) 380 { 381 ps_simple_scale( table, scale, delta, vertical ); 382 return 0; 383 } 384 #endif 385 386 /* XXXX: for now, we only scale the hints to test all other aspects */ 387 /* of the PostScript hinter */ 388 { 389 PSH1_Hint hint; 390 FT_UInt count; 391 392 393 for ( count = 0; count < table->num_hints; count++ ) 394 { 395 hint = table->sort[count]; 396 if ( psh1_hint_is_active( hint ) ) 397 { 398 #if 1 399 FT_Pos pos = FT_MulFix( hint->org_pos, scale ) + delta; 400 FT_Pos len = FT_MulFix( hint->org_len, scale ); 401 402 FT_Pos fit_center; 403 FT_Pos fit_len; 404 405 PSH_AlignmentRec align; 406 407 408 /* compute fitted width/height */ 409 fit_len = psh_dimension_snap_width( dim, hint->org_len ); 410 if ( fit_len < 64 ) 411 fit_len = 64; 412 else 413 fit_len = ( fit_len + 32 ) & -64; 414 415 hint->cur_len = fit_len; 416 417 /* check blue zones for horizontal stems */ 418 align.align = PSH_BLUE_ALIGN_NONE; 419 align.align_bot = align.align_top = 0; 420 if ( !vertical ) 421 { 422 psh_blues_snap_stem( &globals->blues, 423 hint->org_pos + hint->org_len, 424 hint->org_pos, 425 &align ); 426 } 427 428 switch ( align.align ) 429 { 430 case PSH_BLUE_ALIGN_TOP: 431 /* the top of the stem is aligned against a blue zone */ 432 hint->cur_pos = align.align_top - fit_len; 433 break; 434 435 case PSH_BLUE_ALIGN_BOT: 436 /* the bottom of the stem is aligned against a blue zone */ 437 hint->cur_pos = align.align_bot; 438 break; 439 440 case PSH_BLUE_ALIGN_TOP | PSH_BLUE_ALIGN_BOT: 441 /* both edges of the stem are aligned against blue zones */ 442 hint->cur_pos = align.align_bot; 443 hint->cur_len = align.align_top - align.align_bot; 444 break; 445 446 default: 447 /* normal processing */ 448 if ( ( fit_len / 64 ) & 1 ) 449 { 450 /* odd number of pixels */ 451 fit_center = ( ( pos + ( len >> 1 ) ) & -64 ) + 32; 452 } 453 else 454 { 455 /* even number of pixels */ 456 fit_center = ( pos + ( len >> 1 ) + 32 ) & -64; 457 } 458 459 hint->cur_pos = fit_center - ( fit_len >> 1 ); 460 } 461 462 # else 463 464 hint->cur_pos = ( FT_MulFix( hint->org_pos, scale ) + delta + 32 ) 465 & -64; 466 hint->cur_len = FT_MulFix( hint->org_len, scale ); 467 468 # endif 469 470 #ifdef DEBUG_HINTER 471 if ( ps1_debug_hint_func ) 472 ps1_debug_hint_func( hint, vertical ); 473 #endif 474 } 475 } 476 } 477 478 return 0; 479 } 480 481 482 /*************************************************************************/ 483 /*************************************************************************/ 484 /***** *****/ 485 /***** POINTS INTERPOLATION ROUTINES *****/ 486 /***** *****/ 487 /*************************************************************************/ 488 /*************************************************************************/ 489 490 #define PSH1_ZONE_MIN -3200000 491 #define PSH1_ZONE_MAX +3200000 492 493 #define xxDEBUG_ZONES 494 495 496 #ifdef DEBUG_ZONES 497 498 #include <stdio.h> 499 500 static void psh1_print_zone(PSH1_Zone zone)501 psh1_print_zone( PSH1_Zone zone ) 502 { 503 printf( "zone [scale,delta,min,max] = [%.3f,%.3f,%d,%d]\n", 504 zone->scale / 65536.0, 505 zone->delta / 64.0, 506 zone->min, 507 zone->max ); 508 } 509 510 #else 511 #define psh1_print_zone( x ) do { } while ( 0 ) 512 #endif 513 514 /* setup interpolation zones once the hints have been grid-fitted */ 515 /* by the optimizer */ 516 static void psh1_hint_table_setup_zones(PSH1_Hint_Table table,FT_Fixed scale,FT_Fixed delta)517 psh1_hint_table_setup_zones( PSH1_Hint_Table table, 518 FT_Fixed scale, 519 FT_Fixed delta ) 520 { 521 FT_UInt count; 522 PSH1_Zone zone; 523 PSH1_Hint *sort, hint, hint2; 524 525 526 zone = table->zones; 527 528 /* special case, no hints defined */ 529 if ( table->num_hints == 0 ) 530 { 531 zone->scale = scale; 532 zone->delta = delta; 533 zone->min = PSH1_ZONE_MIN; 534 zone->max = PSH1_ZONE_MAX; 535 536 table->num_zones = 1; 537 table->zone = zone; 538 return; 539 } 540 541 /* the first zone is before the first hint */ 542 /* x' = (x-x0)*s + x0' = x*s + ( x0' - x0*s ) */ 543 544 sort = table->sort; 545 hint = sort[0]; 546 547 zone->scale = scale; 548 zone->delta = hint->cur_pos - FT_MulFix( hint->org_pos, scale ); 549 zone->min = PSH1_ZONE_MIN; 550 zone->max = hint->org_pos; 551 552 psh1_print_zone( zone ); 553 554 zone++; 555 556 for ( count = table->num_hints; count > 0; count-- ) 557 { 558 FT_Fixed scale2; 559 560 561 if ( hint->org_len > 0 ) 562 { 563 /* setup a zone for inner-stem interpolation */ 564 /* (x' - x0') = (x - x0)*(x1'-x0')/(x1-x0) */ 565 /* x' = x*s2 + x0' - x0*s2 */ 566 567 scale2 = FT_DivFix( hint->cur_len, hint->org_len ); 568 zone->scale = scale2; 569 zone->min = hint->org_pos; 570 zone->max = hint->org_pos + hint->org_len; 571 zone->delta = hint->cur_pos - FT_MulFix( zone->min, scale2 ); 572 573 psh1_print_zone( zone ); 574 575 zone++; 576 } 577 578 if ( count == 1 ) 579 break; 580 581 sort++; 582 hint2 = sort[0]; 583 584 /* setup zone for inter-stem interpolation */ 585 /* (x'-x1') = (x-x1)*(x2'-x1')/(x2-x1) */ 586 /* x' = x*s3 + x1' - x1*s3 */ 587 588 scale2 = FT_DivFix( hint2->cur_pos - (hint->cur_pos + hint->cur_len), 589 hint2->org_pos - (hint->org_pos + hint->org_len) ); 590 zone->scale = scale2; 591 zone->min = hint->org_pos + hint->org_len; 592 zone->max = hint2->org_pos; 593 zone->delta = hint->cur_pos + hint->cur_len - 594 FT_MulFix( zone->min, scale2 ); 595 596 psh1_print_zone( zone ); 597 598 zone++; 599 600 hint = hint2; 601 } 602 603 /* the last zone */ 604 zone->scale = scale; 605 zone->min = hint->org_pos + hint->org_len; 606 zone->max = PSH1_ZONE_MAX; 607 zone->delta = hint->cur_pos + hint->cur_len - 608 FT_MulFix( zone->min, scale ); 609 610 psh1_print_zone( zone ); 611 612 zone++; 613 614 table->num_zones = zone - table->zones; 615 table->zone = table->zones; 616 } 617 618 619 /* tune a single coordinate with the current interpolation zones */ 620 static FT_Pos psh1_hint_table_tune_coord(PSH1_Hint_Table table,FT_Int coord)621 psh1_hint_table_tune_coord( PSH1_Hint_Table table, 622 FT_Int coord ) 623 { 624 PSH1_Zone zone; 625 626 627 zone = table->zone; 628 629 if ( coord < zone->min ) 630 { 631 do 632 { 633 if ( zone == table->zones ) 634 break; 635 636 zone--; 637 638 } while ( coord < zone->min ); 639 table->zone = zone; 640 } 641 else if ( coord > zone->max ) 642 { 643 do 644 { 645 if ( zone == table->zones + table->num_zones - 1 ) 646 break; 647 648 zone++; 649 650 } while ( coord > zone->max ); 651 table->zone = zone; 652 } 653 654 return FT_MulFix( coord, zone->scale ) + zone->delta; 655 } 656 657 658 /* tune a given outline with current interpolation zones. */ 659 /* The function only works in a single dimension. */ 660 static void psh1_hint_table_tune_outline(PSH1_Hint_Table table,FT_Outline * outline,PSH_Globals globals,FT_Int vertical)661 psh1_hint_table_tune_outline( PSH1_Hint_Table table, 662 FT_Outline* outline, 663 PSH_Globals globals, 664 FT_Int vertical ) 665 666 { 667 FT_UInt count, first, last; 668 PS_Mask_Table hint_masks = table->hint_masks; 669 PS_Mask mask; 670 PSH_Dimension dim = &globals->dimension[vertical]; 671 FT_Fixed scale = dim->scale_mult; 672 FT_Fixed delta = dim->scale_delta; 673 674 675 if ( hint_masks && hint_masks->num_masks > 0 ) 676 { 677 first = 0; 678 mask = hint_masks->masks; 679 count = hint_masks->num_masks; 680 681 for ( ; count > 0; count--, mask++ ) 682 { 683 last = mask->end_point; 684 685 if ( last > first ) 686 { 687 FT_Vector* vec; 688 FT_Int count2; 689 690 691 psh1_hint_table_activate_mask( table, mask ); 692 psh1_hint_table_optimize( table, globals, outline, vertical ); 693 psh1_hint_table_setup_zones( table, scale, delta ); 694 last = mask->end_point; 695 696 vec = outline->points + first; 697 count2 = last - first; 698 699 for ( ; count2 > 0; count2--, vec++ ) 700 { 701 FT_Pos x, *px; 702 703 704 px = vertical ? &vec->x : &vec->y; 705 x = *px; 706 707 *px = psh1_hint_table_tune_coord( table, (FT_Int)x ); 708 } 709 } 710 711 first = last; 712 } 713 } 714 else /* no hints in this glyph, simply scale the outline */ 715 { 716 FT_Vector* vec; 717 718 719 vec = outline->points; 720 count = outline->n_points; 721 722 if ( vertical ) 723 { 724 for ( ; count > 0; count--, vec++ ) 725 vec->x = FT_MulFix( vec->x, scale ) + delta; 726 } 727 else 728 { 729 for ( ; count > 0; count--, vec++ ) 730 vec->y = FT_MulFix( vec->y, scale ) + delta; 731 } 732 } 733 } 734 735 736 /*************************************************************************/ 737 /*************************************************************************/ 738 /***** *****/ 739 /***** HIGH-LEVEL INTERFACE *****/ 740 /***** *****/ 741 /*************************************************************************/ 742 /*************************************************************************/ 743 744 FT_Error ps1_hints_apply(PS_Hints ps_hints,FT_Outline * outline,PSH_Globals globals,FT_Render_Mode hint_mode)745 ps1_hints_apply( PS_Hints ps_hints, 746 FT_Outline* outline, 747 PSH_Globals globals, 748 FT_Render_Mode hint_mode ) 749 { 750 PSH1_Hint_TableRec hints; 751 FT_Error error = 0; 752 FT_Int dimension; 753 754 755 FT_UNUSED( hint_mode ); 756 757 for ( dimension = 1; dimension >= 0; dimension-- ) 758 { 759 PS_Dimension dim = &ps_hints->dimension[dimension]; 760 761 762 /* initialize hints table */ 763 FT_MEM_ZERO( &hints, sizeof ( hints ) ); 764 error = psh1_hint_table_init( &hints, 765 &dim->hints, 766 &dim->masks, 767 &dim->counters, 768 ps_hints->memory ); 769 if ( error ) 770 goto Exit; 771 772 psh1_hint_table_tune_outline( &hints, 773 outline, 774 globals, 775 dimension ); 776 777 psh1_hint_table_done( &hints, ps_hints->memory ); 778 } 779 780 Exit: 781 return error; 782 } 783 784 785 /* END */ 786