1 /***************************************************************************/
5 /* PostScript hinting algorithm 1 (body). */
7 /* Copyright 2001, 2002 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
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. */
16 /***************************************************************************/
20 #include FT_INTERNAL_OBJECTS_H
21 #include FT_INTERNAL_DEBUG_H
25 #define FT_COMPONENT trace_pshalgo1
28 PSH1_Hint_Table ps1_debug_hint_table = 0;
29 PSH1_HintFunc ps1_debug_hint_func = 0;
33 /************************************************************************/
34 /************************************************************************/
36 /***** BASIC HINTS RECORDINGS *****/
38 /************************************************************************/
39 /************************************************************************/
41 /* return true iff two stem hints overlap */
43 psh1_hint_overlap( PSH1_Hint hint1,
46 return ( hint1->org_pos + hint1->org_len >= hint2->org_pos &&
47 hint2->org_pos + hint2->org_len >= hint1->org_pos );
51 /* destroy hints table */
53 psh1_hint_table_done( PSH1_Hint_Table table,
56 FT_FREE( table->zones );
60 FT_FREE( table->sort );
61 FT_FREE( table->hints );
64 table->sort_global = 0;
68 /* deactivate all hints in a table */
70 psh1_hint_table_deactivate( PSH1_Hint_Table table )
72 FT_UInt count = table->max_hints;
73 PSH1_Hint hint = table->hints;
76 for ( ; count > 0; count--, hint++ )
78 psh1_hint_deactivate( hint );
84 /* internal function used to record a new hint */
86 psh1_hint_table_record( PSH1_Hint_Table table,
89 PSH1_Hint hint = table->hints + idx;
92 if ( idx >= table->max_hints )
94 FT_ERROR(( "%s.activate: invalid hint index %d\n", idx ));
98 /* ignore active hints */
99 if ( psh1_hint_is_active( hint ) )
102 psh1_hint_activate( hint );
104 /* now scan the current active hint set in order to determine */
105 /* if we are overlapping with another segment */
107 PSH1_Hint* sorted = table->sort_global;
108 FT_UInt count = table->num_hints;
113 for ( ; count > 0; count--, sorted++ )
117 if ( psh1_hint_overlap( hint, hint2 ) )
119 hint->parent = hint2;
125 if ( table->num_hints < table->max_hints )
126 table->sort_global[table->num_hints++] = hint;
128 FT_ERROR(( "%s.activate: too many sorted hints! BUG!\n",
134 psh1_hint_table_record_mask( PSH1_Hint_Table table,
137 FT_Int mask = 0, val = 0;
138 FT_Byte* cursor = hint_mask->bytes;
142 limit = hint_mask->num_bits;
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 ));
148 for ( idx = 0; idx < limit; idx++ )
157 psh1_hint_table_record( table, idx );
164 /* create hints table */
166 psh1_hint_table_init( PSH1_Hint_Table table,
168 PS_Mask_Table hint_masks,
169 PS_Mask_Table counter_masks,
172 FT_UInt count = hints->num_hints;
175 FT_UNUSED( counter_masks );
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 ) )
184 table->max_hints = count;
185 table->sort_global = table->sort + count;
186 table->num_hints = 0;
187 table->num_zones = 0;
190 /* now, initialize the "hints" array */
192 PSH1_Hint write = table->hints;
193 PS_Hint read = hints->hints;
196 for ( ; count > 0; count--, write++, read++ )
198 write->org_pos = read->pos;
199 write->org_len = read->len;
200 write->flags = read->flags;
204 /* we now need to determine the initial "parent" stems; first */
205 /* activate the hints that are given by the initial hint masks */
208 FT_UInt Count = hint_masks->num_masks;
209 PS_Mask Mask = hint_masks->masks;
212 table->hint_masks = hint_masks;
214 for ( ; Count > 0; Count--, Mask++ )
215 psh1_hint_table_record_mask( table, Mask );
218 /* now, do a linear parse in case some hints were left alone */
219 if ( table->num_hints != table->max_hints )
221 FT_UInt Index, Count;
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 );
236 psh1_hint_table_activate_mask( PSH1_Hint_Table table,
239 FT_Int mask = 0, val = 0;
240 FT_Byte* cursor = hint_mask->bytes;
241 FT_UInt idx, limit, count;
244 limit = hint_mask->num_bits;
247 psh1_hint_table_deactivate( table );
249 for ( idx = 0; idx < limit; idx++ )
259 PSH1_Hint hint = &table->hints[idx];
262 if ( !psh1_hint_is_active( hint ) )
264 PSH1_Hint* sort = table->sort;
269 for ( count2 = count; count2 > 0; count2--, sort++ )
272 if ( psh1_hint_overlap( hint, hint2 ) )
274 FT_ERROR(( "%s.activate_mask: found overlapping hints\n",
282 psh1_hint_activate( hint );
283 if ( count < table->max_hints )
284 table->sort[count++] = hint;
286 FT_ERROR(( "%s.activate_mask: too many active hints\n",
294 table->num_hints = count;
296 /* now, sort the hints; they are guaranteed to not overlap */
297 /* so we can compare their "org_pos" field directly */
300 PSH1_Hint hint1, hint2;
301 PSH1_Hint* sort = table->sort;
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++ )
310 for ( i2 = i1 - 1; i2 >= 0; i2-- )
313 if ( hint2->org_pos < hint1->org_pos )
316 sort[i2 + 1] = hint2;
324 /*************************************************************************/
325 /*************************************************************************/
327 /***** HINTS GRID-FITTING AND OPTIMIZATION *****/
329 /*************************************************************************/
330 /*************************************************************************/
334 ps_simple_scale( PSH1_Hint_Table table,
343 for ( count = 0; count < table->num_hints; count++ )
345 hint = table->sort[count];
346 if ( psh1_hint_is_active( hint ) )
348 hint->cur_pos = FT_MulFix( hint->org_pos, scale ) + delta;
349 hint->cur_len = FT_MulFix( hint->org_len, scale );
351 if ( ps1_debug_hint_func )
352 ps1_debug_hint_func( hint, vertical );
359 FT_LOCAL_DEF( FT_Error )
360 psh1_hint_table_optimize( PSH1_Hint_Table table,
365 PSH_Dimension dim = &globals->dimension[vertical];
366 FT_Fixed scale = dim->scale_mult;
367 FT_Fixed delta = dim->scale_delta;
369 FT_UNUSED( outline );
373 if ( ps_debug_no_vert_hints && vertical )
375 ps_simple_scale( table, scale, delta, vertical );
379 if ( ps_debug_no_horz_hints && !vertical )
381 ps_simple_scale( table, scale, delta, vertical );
386 /* XXXX: for now, we only scale the hints to test all other aspects */
387 /* of the PostScript hinter */
393 for ( count = 0; count < table->num_hints; count++ )
395 hint = table->sort[count];
396 if ( psh1_hint_is_active( hint ) )
399 FT_Pos pos = FT_MulFix( hint->org_pos, scale ) + delta;
400 FT_Pos len = FT_MulFix( hint->org_len, scale );
405 PSH_AlignmentRec align;
408 /* compute fitted width/height */
409 fit_len = psh_dimension_snap_width( dim, hint->org_len );
413 fit_len = ( fit_len + 32 ) & -64;
415 hint->cur_len = fit_len;
417 /* check blue zones for horizontal stems */
418 align.align = PSH_BLUE_ALIGN_NONE;
419 align.align_bot = align.align_top = 0;
422 psh_blues_snap_stem( &globals->blues,
423 hint->org_pos + hint->org_len,
428 switch ( align.align )
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;
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;
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;
447 /* normal processing */
448 if ( ( fit_len / 64 ) & 1 )
450 /* odd number of pixels */
451 fit_center = ( ( pos + ( len >> 1 ) ) & -64 ) + 32;
455 /* even number of pixels */
456 fit_center = ( pos + ( len >> 1 ) + 32 ) & -64;
459 hint->cur_pos = fit_center - ( fit_len >> 1 );
464 hint->cur_pos = ( FT_MulFix( hint->org_pos, scale ) + delta + 32 )
466 hint->cur_len = FT_MulFix( hint->org_len, scale );
471 if ( ps1_debug_hint_func )
472 ps1_debug_hint_func( hint, vertical );
482 /*************************************************************************/
483 /*************************************************************************/
485 /***** POINTS INTERPOLATION ROUTINES *****/
487 /*************************************************************************/
488 /*************************************************************************/
490 #define PSH1_ZONE_MIN -3200000
491 #define PSH1_ZONE_MAX +3200000
493 #define xxDEBUG_ZONES
501 psh1_print_zone( PSH1_Zone zone )
503 printf( "zone [scale,delta,min,max] = [%.3f,%.3f,%d,%d]\n",
504 zone->scale / 65536.0,
511 #define psh1_print_zone( x ) do { } while ( 0 )
514 /* setup interpolation zones once the hints have been grid-fitted */
515 /* by the optimizer */
517 psh1_hint_table_setup_zones( PSH1_Hint_Table table,
523 PSH1_Hint *sort, hint, hint2;
528 /* special case, no hints defined */
529 if ( table->num_hints == 0 )
533 zone->min = PSH1_ZONE_MIN;
534 zone->max = PSH1_ZONE_MAX;
536 table->num_zones = 1;
541 /* the first zone is before the first hint */
542 /* x' = (x-x0)*s + x0' = x*s + ( x0' - x0*s ) */
548 zone->delta = hint->cur_pos - FT_MulFix( hint->org_pos, scale );
549 zone->min = PSH1_ZONE_MIN;
550 zone->max = hint->org_pos;
552 psh1_print_zone( zone );
556 for ( count = table->num_hints; count > 0; count-- )
561 if ( hint->org_len > 0 )
563 /* setup a zone for inner-stem interpolation */
564 /* (x' - x0') = (x - x0)*(x1'-x0')/(x1-x0) */
565 /* x' = x*s2 + x0' - x0*s2 */
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 );
573 psh1_print_zone( zone );
584 /* setup zone for inter-stem interpolation */
585 /* (x'-x1') = (x-x1)*(x2'-x1')/(x2-x1) */
586 /* x' = x*s3 + x1' - x1*s3 */
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 );
596 psh1_print_zone( zone );
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 );
610 psh1_print_zone( zone );
614 table->num_zones = zone - table->zones;
615 table->zone = table->zones;
619 /* tune a single coordinate with the current interpolation zones */
621 psh1_hint_table_tune_coord( PSH1_Hint_Table table,
629 if ( coord < zone->min )
633 if ( zone == table->zones )
638 } while ( coord < zone->min );
641 else if ( coord > zone->max )
645 if ( zone == table->zones + table->num_zones - 1 )
650 } while ( coord > zone->max );
654 return FT_MulFix( coord, zone->scale ) + zone->delta;
658 /* tune a given outline with current interpolation zones. */
659 /* The function only works in a single dimension. */
661 psh1_hint_table_tune_outline( PSH1_Hint_Table table,
667 FT_UInt count, first, last;
668 PS_Mask_Table hint_masks = table->hint_masks;
670 PSH_Dimension dim = &globals->dimension[vertical];
671 FT_Fixed scale = dim->scale_mult;
672 FT_Fixed delta = dim->scale_delta;
675 if ( hint_masks && hint_masks->num_masks > 0 )
678 mask = hint_masks->masks;
679 count = hint_masks->num_masks;
681 for ( ; count > 0; count--, mask++ )
683 last = mask->end_point;
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;
696 vec = outline->points + first;
697 count2 = last - first;
699 for ( ; count2 > 0; count2--, vec++ )
704 px = vertical ? &vec->x : &vec->y;
707 *px = psh1_hint_table_tune_coord( table, (FT_Int)x );
714 else /* no hints in this glyph, simply scale the outline */
719 vec = outline->points;
720 count = outline->n_points;
724 for ( ; count > 0; count--, vec++ )
725 vec->x = FT_MulFix( vec->x, scale ) + delta;
729 for ( ; count > 0; count--, vec++ )
730 vec->y = FT_MulFix( vec->y, scale ) + delta;
736 /*************************************************************************/
737 /*************************************************************************/
739 /***** HIGH-LEVEL INTERFACE *****/
741 /*************************************************************************/
742 /*************************************************************************/
745 ps1_hints_apply( PS_Hints ps_hints,
748 FT_Render_Mode hint_mode )
750 PSH1_Hint_TableRec hints;
755 FT_UNUSED( hint_mode );
757 for ( dimension = 1; dimension >= 0; dimension-- )
759 PS_Dimension dim = &ps_hints->dimension[dimension];
762 /* initialize hints table */
763 FT_MEM_ZERO( &hints, sizeof ( hints ) );
764 error = psh1_hint_table_init( &hints,
772 psh1_hint_table_tune_outline( &hints,
777 psh1_hint_table_done( &hints, ps_hints->memory );