WebSVN – Kolibri OS – Blame – /contrib/sdk/sources/freetype/src/pshinter/pshalgo.c

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

Subversion Repositories Kolibri OS

(root)/contrib/sdk/sources/freetype/src/pshinter/pshalgo.c – Rev 4349