ftraster.c source code [Godot/thirdparty/freetype/src/raster/ftraster.c]

1	/****************************************************************************
2	*
3	* ftraster.c
4	*
5	* The FreeType glyph rasterizer (body).
6	*
7	* Copyright (C) 1996-2023 by
8	* David Turner, Robert Wilhelm, and Werner Lemberg.
9	*
10	* This file is part of the FreeType project, and may only be used,
11	* modified, and distributed under the terms of the FreeType project
12	* license, LICENSE.TXT. By continuing to use, modify, or distribute
13	* this file you indicate that you have read the license and
14	* understand and accept it fully.
15	*
16	*/
17
18	/**************************************************************************
19	*
20	* This file can be compiled without the rest of the FreeType engine, by
21	* defining the STANDALONE_ macro when compiling it. You also need to
22	* put the files `ftimage.h' and `ftmisc.h' into the $(incdir)
23	* directory. Typically, you should do something like
24	*
25	* - copy `src/raster/ftraster.c' (this file) to your current directory
26	*
27	* - copy `include/freetype/ftimage.h' and `src/raster/ftmisc.h' to your
28	* current directory
29	*
30	* - compile `ftraster' with the STANDALONE_ macro defined, as in
31	*
32	* cc -c -DSTANDALONE_ ftraster.c
33	*
34	* The renderer can be initialized with a call to
35	* `ft_standard_raster.raster_new'; a bitmap can be generated
36	* with a call to `ft_standard_raster.raster_render'.
37	*
38	* See the comments and documentation in the file `ftimage.h' for more
39	* details on how the raster works.
40	*
41	*/
42
43
44	/**************************************************************************
45	*
46	* This is a rewrite of the FreeType 1.x scan-line converter
47	*
48	*/
49
50	#ifdef STANDALONE_
51
52	/ The size in bytes of the render pool used by the scan-line converter /
53	/ to do all of its work. /
54	#define FT_RENDER_POOL_SIZE 16384L
55
56	#define FT_CONFIG_STANDARD_LIBRARY_H <stdlib.h>
57
58	#include <string.h> /* for memset */
59
60	#include "ftmisc.h"
61	#include "ftimage.h"
62
63	#else /* !STANDALONE_ */
64
65	#include "ftraster.h"
66	#include <freetype/internal/ftcalc.h> /* for FT_MulDiv and FT_MulDiv_No_Round */
67	#include <freetype/ftoutln.h> /* for FT_Outline_Get_CBox */
68
69	#endif /* !STANDALONE_ */
70
71
72	/**************************************************************************
73	*
74	* A simple technical note on how the raster works
75	* -----------------------------------------------
76	*
77	* Converting an outline into a bitmap is achieved in several steps:
78	*
79	* 1 - Decomposing the outline into successive `profiles'. Each
80	* profile is simply an array of scanline intersections on a given
81	* dimension. A profile's main attributes are
82	*
83	* o its scanline position boundaries, i.e. `Ymin' and `Ymax'
84	*
85	* o an array of intersection coordinates for each scanline
86	* between `Ymin' and `Ymax'
87	*
88	* o a direction, indicating whether it was built going `up' or
89	* `down', as this is very important for filling rules
90	*
91	* o its drop-out mode
92	*
93	* 2 - Sweeping the target map's scanlines in order to compute segment
94	* `spans' which are then filled. Additionally, this pass
95	* performs drop-out control.
96	*
97	* The outline data is parsed during step 1 only. The profiles are
98	* built from the bottom of the render pool, used as a stack. The
99	* following graphics shows the profile list under construction:
100	*
101	* __________________________________________________________ _ _
102	* \| \| \| \| \|
103	* \| profile \| coordinates for \| profile \| coordinates for \|-->
104	* \| 1 \| profile 1 \| 2 \| profile 2 \|-->
105	* \|_________\|_________________\|_________\|_________________\|__ _ _
106	*
107	* ^ ^
108	* \| \|
109	* start of render pool top
110	*
111	* The top of the profile stack is kept in the `top' variable.
112	*
113	* As you can see, a profile record is pushed on top of the render
114	* pool, which is then followed by its coordinates/intersections. If
115	* a change of direction is detected in the outline, a new profile is
116	* generated until the end of the outline.
117	*
118	* Note that when all profiles have been generated, the function
119	* Finalize_Profile_Table() is used to record, for each profile, its
120	* bottom-most scanline as well as the scanline above its upmost
121	* boundary. These positions are called `y-turns' because they (sort
122	* of) correspond to local extrema. They are stored in a sorted list
123	* built from the top of the render pool as a downwards stack:
124	*
125	* _ _ _______________________________________
126	* \| \|
127	* <--\| sorted list of \|
128	* <--\| extrema scanlines \|
129	* _ _ __________________\|____________________\|
130	*
131	* ^ ^
132	* \| \|
133	* maxBuff sizeBuff = end of pool
134	*
135	* This list is later used during the sweep phase in order to
136	* optimize performance (see technical note on the sweep below).
137	*
138	* Of course, the raster detects whether the two stacks collide and
139	* handles the situation properly.
140	*
141	*/
142
143
144	/***********************************************************************/
145	/***********************************************************************/
146	/* */
147	/* CONFIGURATION MACROS */
148	/* */
149	/***********************************************************************/
150	/***********************************************************************/
151
152
153	/***********************************************************************/
154	/***********************************************************************/
155	/* */
156	/* OTHER MACROS (do not change) */
157	/* */
158	/***********************************************************************/
159	/***********************************************************************/
160
161	/**************************************************************************
162	*
163	* The macro FT_COMPONENT is used in trace mode. It is an implicit
164	* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log
165	* messages during execution.
166	*/
167	#undef FT_COMPONENT
168	#define FT_COMPONENT raster
169
170
171	#ifdef STANDALONE_
172
173	/ Auxiliary macros for token concatenation. /
174	#define FT_ERR_XCAT( x, y ) x ## y
175	#define FT_ERR_CAT( x, y ) FT_ERR_XCAT( x, y )
176
177	/ This macro is used to indicate that a function parameter is unused. /
178	/ Its purpose is simply to reduce compiler warnings. Note also that /
179	/ simply defining it as `(void)x' doesn't avoid warnings with certain /
180	/ ANSI compilers (e.g. LCC). /
181	#define FT_UNUSED( x ) (x) = (x)
182
183	/ Disable the tracing mechanism for simplicity -- developers can /
184	/ activate it easily by redefining these macros. /
185	#ifndef FT_ERROR
186	#define FT_ERROR( x ) do { } while ( 0 ) /* nothing */
187	#endif
188
189	#ifndef FT_TRACE
190	#define FT_TRACE( x ) do { } while ( 0 ) /* nothing */
191	#define FT_TRACE1( x ) do { } while ( 0 ) /* nothing */
192	#define FT_TRACE6( x ) do { } while ( 0 ) /* nothing */
193	#define FT_TRACE7( x ) do { } while ( 0 ) /* nothing */
194	#endif
195
196	#ifndef FT_THROW
197	#define FT_THROW( e ) FT_ERR_CAT( Raster_Err_, e )
198	#endif
199
200	#define Raster_Err_Ok 0
201	#define Raster_Err_Invalid_Outline -1
202	#define Raster_Err_Cannot_Render_Glyph -2
203	#define Raster_Err_Invalid_Argument -3
204	#define Raster_Err_Raster_Overflow -4
205	#define Raster_Err_Raster_Uninitialized -5
206	#define Raster_Err_Raster_Negative_Height -6
207
208	#define ft_memset memset
209
210	#define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_, raster_new_, \
211	raster_reset_, raster_set_mode_, \
212	raster_render_, raster_done_ ) \
213	const FT_Raster_Funcs class_ = \
214	{ \
215	glyph_format_, \
216	raster_new_, \
217	raster_reset_, \
218	raster_set_mode_, \
219	raster_render_, \
220	raster_done_ \
221	};
222
223	#else /* !STANDALONE_ */
224
225
226	#include <freetype/internal/ftobjs.h>
227	#include <freetype/internal/ftdebug.h> /* for FT_TRACE, FT_ERROR, and FT_THROW */
228
229	#include "rasterrs.h"
230
231
232	#endif /* !STANDALONE_ */
233
234
235	#ifndef FT_MEM_SET
236	#define FT_MEM_SET( d, s, c ) ft_memset( d, s, c )
237	#endif
238
239	#ifndef FT_MEM_ZERO
240	#define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count )
241	#endif
242
243	#ifndef FT_ZERO
244	#define FT_ZERO( p ) FT_MEM_ZERO( p, sizeof ( *(p) ) )
245	#endif
246
247	/ FMulDiv means `Fast MulDiv'; it is used in case where `b' is /
248	/ typically a small value and the result of ab is known to fit into /*
249	/ 32 bits. /
250	#define FMulDiv( a, b, c ) ( (a) * (b) / (c) )
251
252	/ On the other hand, SMulDiv means `Slow MulDiv', and is used typically /
253	/ for clipping computations. It simply uses the FT_MulDiv() function /
254	/ defined in `ftcalc.h'. /
255	#define SMulDiv FT_MulDiv
256	#define SMulDiv_No_Round FT_MulDiv_No_Round
257
258	/ The rasterizer is a very general purpose component; please leave /
259	/ the following redefinitions there (you never know your target /
260	/ environment). /
261
262	#ifndef TRUE
263	#define TRUE 1
264	#endif
265
266	#ifndef FALSE
267	#define FALSE 0
268	#endif
269
270	#ifndef NULL
271	#define NULL (void*)0
272	#endif
273
274	#ifndef SUCCESS
275	#define SUCCESS 0
276	#endif
277
278	#ifndef FAILURE
279	#define FAILURE 1
280	#endif
281
282
283	#define MaxBezier 32 /* The maximum number of stacked Bezier curves. */
284	/ Setting this constant to more than 32 is a /
285	/ pure waste of space. /
286
287	#define Pixel_Bits 6 /* fractional bits of input coordinates */
288
289
290	/***********************************************************************/
291	/***********************************************************************/
292	/* */
293	/* SIMPLE TYPE DECLARATIONS */
294	/* */
295	/***********************************************************************/
296	/***********************************************************************/
297
298	typedef int Int;
299	typedef unsigned int UInt;
300	typedef short Short;
301	typedef unsigned short UShort, *PUShort;
302	typedef long Long, *PLong;
303	typedef unsigned long ULong;
304
305	typedef unsigned char Byte, *PByte;
306	typedef char Bool;
307
308
309	typedef union Alignment_
310	{
311	Long l;
312	void* p;
313	void (f)(void*);
314
315	} Alignment, *PAlignment;
316
317
318	typedef struct TPoint_
319	{
320	Long x;
321	Long y;
322
323	} TPoint;
324
325
326	/ values for the `flags' bit field /
327	#define Flow_Up 0x08U
328	#define Overshoot_Top 0x10U
329	#define Overshoot_Bottom 0x20U
330
331
332	/ States of each line, arc, and profile /
333	typedef enum TStates_
334	{
335	Unknown_State,
336	Ascending_State,
337	Descending_State,
338	Flat_State
339
340	} TStates;
341
342
343	typedef struct TProfile_ TProfile;
344	typedef TProfile* PProfile;
345
346	struct TProfile_
347	{
348	FT_F26Dot6 X; / current coordinate during sweep /
349	PProfile link; / link to next profile (various purposes) /
350	PLong offset; / start of profile's data in render pool /
351	UShort flags; / Bit 0-2: drop-out mode /
352	/ Bit 3: profile orientation (up/down) /
353	/ Bit 4: is top profile? /
354	/ Bit 5: is bottom profile? /
355	Long height; / profile's height in scanlines /
356	Long start; / profile's starting scanline /
357
358	Int countL; / number of lines to step before this /
359	/ profile becomes drawable /
360
361	PProfile next; / next profile in same contour, used /
362	/ during drop-out control /
363	};
364
365	typedef PProfile TProfileList;
366	typedef PProfile* PProfileList;
367
368
369	#define AlignProfileSize \
370	( ( sizeof ( TProfile ) + sizeof ( Alignment ) - 1 ) / sizeof ( Long ) )
371
372
373	#undef RAS_ARG
374	#undef RAS_ARGS
375	#undef RAS_VAR
376	#undef RAS_VARS
377
378	#ifdef FT_STATIC_RASTER
379
380
381	#define RAS_ARGS /* void */
382	#define RAS_ARG void
383
384	#define RAS_VARS /* void */
385	#define RAS_VAR /* void */
386
387	#define FT_UNUSED_RASTER do { } while ( 0 )
388
389
390	#else /* !FT_STATIC_RASTER */
391
392
393	#define RAS_ARGS black_PWorker worker,
394	#define RAS_ARG black_PWorker worker
395
396	#define RAS_VARS worker,
397	#define RAS_VAR worker
398
399	#define FT_UNUSED_RASTER FT_UNUSED( worker )
400
401
402	#endif /* !FT_STATIC_RASTER */
403
404
405	typedef struct black_TWorker_ black_TWorker, *black_PWorker;
406
407
408	/ prototypes used for sweep function dispatch /
409	typedef void
410	Function_Sweep_Init( RAS_ARGS Short min,
411	Short max );
412
413	typedef void
414	Function_Sweep_Span( RAS_ARGS Short y,
415	FT_F26Dot6 x1,
416	FT_F26Dot6 x2,
417	PProfile left,
418	PProfile right );
419
420	typedef void
421	Function_Sweep_Step( RAS_ARG );
422
423
424	/ NOTE: These operations are only valid on 2's complement processors /
425	#undef FLOOR
426	#undef CEILING
427	#undef TRUNC
428	#undef SCALED
429
430	#define FLOOR( x ) ( (x) & -ras.precision )
431	#define CEILING( x ) ( ( (x) + ras.precision - 1 ) & -ras.precision )
432	#define TRUNC( x ) ( (Long)(x) >> ras.precision_bits )
433	#define FRAC( x ) ( (x) & ( ras.precision - 1 ) )
434
435	/ scale and shift grid to pixel centers /
436	#define SCALED( x ) ( (x) * ras.precision_scale - ras.precision_half )
437
438	#define IS_BOTTOM_OVERSHOOT( x ) \
439	(Bool)( CEILING( x ) - x >= ras.precision_half )
440	#define IS_TOP_OVERSHOOT( x ) \
441	(Bool)( x - FLOOR( x ) >= ras.precision_half )
442
443	/ Smart dropout rounding to find which pixel is closer to span ends. /
444	/ To mimick Windows, symmetric cases break down indepenently of the /
445	/ precision. /
446	#define SMART( p, q ) FLOOR( ( (p) + (q) + ras.precision * 63 / 64 ) >> 1 )
447
448	#if FT_RENDER_POOL_SIZE > 2048
449	#define FT_MAX_BLACK_POOL ( FT_RENDER_POOL_SIZE / sizeof ( Long ) )
450	#else
451	#define FT_MAX_BLACK_POOL ( 2048 / sizeof ( Long ) )
452	#endif
453
454	/ The most used variables are positioned at the top of the structure. /
455	/ Thus, their offset can be coded with less opcodes, resulting in a /
456	/ smaller executable. /
457
458	struct black_TWorker_
459	{
460	Int precision_bits; / precision related variables /
461	Int precision;
462	Int precision_half;
463	Int precision_scale;
464	Int precision_step;
465	Int precision_jitter;
466
467	PLong buff; / The profiles buffer /
468	PLong sizeBuff; / Render pool size /
469	PLong maxBuff; / Profiles buffer size /
470	PLong top; / Current cursor in buffer /
471
472	FT_Error error;
473
474	Int numTurns; / number of Y-turns in outline /
475
476	Byte dropOutControl; / current drop_out control method /
477
478	UShort bWidth; / target bitmap width /
479	PByte bOrigin; / target bitmap bottom-left origin /
480	PByte bLine; / target bitmap current line /
481
482	Long lastX, lastY;
483	Long minY, maxY;
484
485	UShort num_Profs; / current number of profiles /
486
487	Bool fresh; / signals a fresh new profile which /
488	/ `start' field must be completed /
489	Bool joint; / signals that the last arc ended /
490	/ exactly on a scanline. Allows /
491	/ removal of doublets /
492	PProfile cProfile; / current profile /
493	PProfile fProfile; / head of linked list of profiles /
494	PProfile gProfile; / contour's first profile in case /
495	/ of impact /
496
497	TStates state; / rendering state /
498
499	FT_Bitmap target; / description of target bit/pixmap /
500	FT_Outline outline;
501
502	/ dispatch variables /
503
504	Function_Sweep_Init* Proc_Sweep_Init;
505	Function_Sweep_Span* Proc_Sweep_Span;
506	Function_Sweep_Span* Proc_Sweep_Drop;
507	Function_Sweep_Step* Proc_Sweep_Step;
508
509	};
510
511
512	typedef struct black_TRaster_
513	{
514	void* memory;
515
516	} black_TRaster, *black_PRaster;
517
518	#ifdef FT_STATIC_RASTER
519
520	static black_TWorker ras;
521
522	#else /* !FT_STATIC_RASTER */
523
524	#define ras (*worker)
525
526	#endif /* !FT_STATIC_RASTER */
527
528
529	/***********************************************************************/
530	/***********************************************************************/
531	/* */
532	/* PROFILES COMPUTATION */
533	/* */
534	/***********************************************************************/
535	/***********************************************************************/
536
537
538	/**************************************************************************
539	*
540	* @Function:
541	* Set_High_Precision
542	*
543	* @Description:
544	* Set precision variables according to param flag.
545	*
546	* @Input:
547	* High ::
548	* Set to True for high precision (typically for ppem < 24),
549	* false otherwise.
550	*/
551	static void
552	Set_High_Precision( RAS_ARGS Int High )
553	{
554	/*
555	* `precision_step' is used in `Bezier_Up' to decide when to split a
556	* given y-monotonous Bezier arc that crosses a scanline before
557	* approximating it as a straight segment. The default value of 32 (for
558	* low accuracy) corresponds to
559	*
560	* 32 / 64 == 0.5 pixels,
561	*
562	* while for the high accuracy case we have
563	*
564	* 256 / (1 << 12) = 0.0625 pixels.
565	*
566	* `precision_jitter' is an epsilon threshold used in
567	* `Vertical_Sweep_Span' to deal with small imperfections in the Bezier
568	* decomposition (after all, we are working with approximations only);
569	* it avoids switching on additional pixels which would cause artifacts
570	* otherwise.
571	*
572	* The value of `precision_jitter' has been determined heuristically.
573	*
574	*/
575
576	if ( High )
577	{
578	ras.precision_bits = `12`;
579	ras.precision_step = `256`;
580	ras.precision_jitter = `30`;
581	}
582	else
583	{
584	ras.precision_bits = `6`;
585	ras.precision_step = `32`;
586	ras.precision_jitter = `2`;
587	}
588
589	FT_TRACE6(( "Set_High_Precision(%s)\n", High ? "true" : "false" ));
590
591	ras.precision = `1` << ras.precision_bits;
592	ras.precision_half = ras.precision >> `1`;
593	ras.precision_scale = ras.precision >> Pixel_Bits;
594	}
595
596
597	/**************************************************************************
598	*
599	* @Function:
600	* New_Profile
601	*
602	* @Description:
603	* Create a new profile in the render pool.
604	*
605	* @Input:
606	* aState ::
607	* The state/orientation of the new profile.
608	*
609	* overshoot ::
610	* Whether the profile's unrounded start position
611	* differs by at least a half pixel.
612	*
613	* @Return:
614	* SUCCESS on success. FAILURE in case of overflow or of incoherent
615	* profile.
616	*/
617	static Bool
618	New_Profile( RAS_ARGS TStates aState,
619	Bool overshoot )
620	{
621	if ( !ras.fProfile )
622	{
623	ras.cProfile = (PProfile)ras.top;
624	ras.fProfile = ras.cProfile;
625	ras.top += AlignProfileSize;
626	}
627
628	if ( ras.top >= ras.maxBuff )
629	{
630	ras.error = FT_THROW( Raster_Overflow );
631	return FAILURE;
632	}
633
634	ras.cProfile->start = `0`;
635	ras.cProfile->height = `0`;
636	ras.cProfile->offset = ras.top;
637	ras.cProfile->link = (PProfile)`0`;
638	ras.cProfile->next = (PProfile)`0`;
639	ras.cProfile->flags = ras.dropOutControl;
640
641	switch ( aState )
642	{
643	case Ascending_State:
644	ras.cProfile->flags \|= Flow_Up;
645	if ( overshoot )
646	ras.cProfile->flags \|= Overshoot_Bottom;
647
648	FT_TRACE6(( " new ascending profile = %p\n", (void *)ras.cProfile ));
649	break;
650
651	case Descending_State:
652	if ( overshoot )
653	ras.cProfile->flags \|= Overshoot_Top;
654	FT_TRACE6(( " new descending profile = %p\n", (void *)ras.cProfile ));
655	break;
656
657	default:
658	FT_ERROR(( "New_Profile: invalid profile direction\n" ));
659	ras.error = FT_THROW( Invalid_Outline );
660	return FAILURE;
661	}
662
663	if ( !ras.gProfile )
664	ras.gProfile = ras.cProfile;
665
666	ras.state = aState;
667	ras.fresh = TRUE;
668	ras.joint = FALSE;
669
670	return SUCCESS;
671	}
672
673
674	/**************************************************************************
675	*
676	* @Function:
677	* End_Profile
678	*
679	* @Description:
680	* Finalize the current profile.
681	*
682	* @Input:
683	* overshoot ::
684	* Whether the profile's unrounded end position differs
685	* by at least a half pixel.
686	*
687	* @Return:
688	* SUCCESS on success. FAILURE in case of overflow or incoherency.
689	*/
690	static Bool
691	End_Profile( RAS_ARGS Bool overshoot )
692	{
693	Long h;
694
695
696	h = (Long)( ras.top - ras.cProfile->offset );
697
698	if ( h < `0` )
699	{
700	FT_ERROR(( "End_Profile: negative height encountered\n" ));
701	ras.error = FT_THROW( Raster_Negative_Height );
702	return FAILURE;
703	}
704
705	if ( h > `0` )
706	{
707	PProfile oldProfile;
708
709
710	FT_TRACE6(( " ending profile %p, start = %ld, height = %ld\n",
711	(void *)ras.cProfile, ras.cProfile->start, h ));
712
713	ras.cProfile->height = h;
714	if ( overshoot )
715	{
716	if ( ras.cProfile->flags & Flow_Up )
717	ras.cProfile->flags \|= Overshoot_Top;
718	else
719	ras.cProfile->flags \|= Overshoot_Bottom;
720	}
721
722	oldProfile = ras.cProfile;
723	ras.cProfile = (PProfile)ras.top;
724
725	ras.top += AlignProfileSize;
726
727	ras.cProfile->height = `0`;
728	ras.cProfile->offset = ras.top;
729
730	oldProfile->next = ras.cProfile;
731	ras.num_Profs++;
732	}
733
734	if ( ras.top >= ras.maxBuff )
735	{
736	FT_TRACE1(( "overflow in End_Profile\n" ));
737	ras.error = FT_THROW( Raster_Overflow );
738	return FAILURE;
739	}
740
741	ras.joint = FALSE;
742
743	return SUCCESS;
744	}
745
746
747	/**************************************************************************
748	*
749	* @Function:
750	* Insert_Y_Turn
751	*
752	* @Description:
753	* Insert a salient into the sorted list placed on top of the render
754	* pool.
755	*
756	* @Input:
757	* New y scanline position.
758	*
759	* @Return:
760	* SUCCESS on success. FAILURE in case of overflow.
761	*/
762	static Bool
763	Insert_Y_Turn( RAS_ARGS Int y )
764	{
765	PLong y_turns;
766	Int n;
767
768
769	n = ras.numTurns - `1`;
770	y_turns = ras.sizeBuff - ras.numTurns;
771
772	/ look for first y value that is <= /
773	while ( n >= `0` && y < y_turns[n] )
774	n--;
775
776	/ if it is <, simply insert it, ignore if == /
777	if ( n >= `0` && y > y_turns[n] )
778	do
779	{
780	Int y2 = (Int)y_turns[n];
781
782
783	y_turns[n] = y;
784	y = y2;
785	} while ( --n >= `0` );
786
787	if ( n < `0` )
788	{
789	ras.maxBuff--;
790	if ( ras.maxBuff <= ras.top )
791	{
792	ras.error = FT_THROW( Raster_Overflow );
793	return FAILURE;
794	}
795	ras.numTurns++;
796	ras.sizeBuff[-ras.numTurns] = y;
797	}
798
799	return SUCCESS;
800	}
801
802
803	/**************************************************************************
804	*
805	* @Function:
806	* Finalize_Profile_Table
807	*
808	* @Description:
809	* Adjust all links in the profiles list.
810	*
811	* @Return:
812	* SUCCESS on success. FAILURE in case of overflow.
813	*/
814	static Bool
815	Finalize_Profile_Table( RAS_ARG )
816	{
817	UShort n;
818	PProfile p;
819
820
821	n = ras.num_Profs;
822	p = ras.fProfile;
823
824	if ( n > `1` && p )
825	{
826	do
827	{
828	Int bottom, top;
829
830
831	if ( n > `1` )
832	p->link = (PProfile)( p->offset + p->height );
833	else
834	p->link = NULL;
835
836	if ( p->flags & Flow_Up )
837	{
838	bottom = (Int)p->start;
839	top = (Int)( p->start + p->height - `1` );
840	}
841	else
842	{
843	bottom = (Int)( p->start - p->height + `1` );
844	top = (Int)p->start;
845	p->start = bottom;
846	p->offset += p->height - `1`;
847	}
848
849	if ( Insert_Y_Turn( RAS_VARS bottom ) \|\|
850	Insert_Y_Turn( RAS_VARS top + `1` ) )
851	return FAILURE;
852
853	p = p->link;
854	} while ( --n );
855	}
856	else
857	ras.fProfile = NULL;
858
859	return SUCCESS;
860	}
861
862
863	/**************************************************************************
864	*
865	* @Function:
866	* Split_Conic
867	*
868	* @Description:
869	* Subdivide one conic Bezier into two joint sub-arcs in the Bezier
870	* stack.
871	*
872	* @Input:
873	* None (subdivided Bezier is taken from the top of the stack).
874	*
875	* @Note:
876	* This routine is the `beef' of this component. It is _the_ inner
877	* loop that should be optimized to hell to get the best performance.
878	*/
879	static void
880	Split_Conic( TPoint* base )
881	{
882	Long a, b;
883
884
885	base[`4`].x = base[`2`].x;
886	a = base[`0`].x + base[`1`].x;
887	b = base[`1`].x + base[`2`].x;
888	base[`3`].x = b >> `1`;
889	base[`2`].x = ( a + b ) >> `2`;
890	base[`1`].x = a >> `1`;
891
892	base[`4`].y = base[`2`].y;
893	a = base[`0`].y + base[`1`].y;
894	b = base[`1`].y + base[`2`].y;
895	base[`3`].y = b >> `1`;
896	base[`2`].y = ( a + b ) >> `2`;
897	base[`1`].y = a >> `1`;
898
899	/ hand optimized. gcc doesn't seem to be too good at common /
900	/ expression substitution and instruction scheduling ;-) /
901	}
902
903
904	/**************************************************************************
905	*
906	* @Function:
907	* Split_Cubic
908	*
909	* @Description:
910	* Subdivide a third-order Bezier arc into two joint sub-arcs in the
911	* Bezier stack.
912	*
913	* @Note:
914	* This routine is the `beef' of the component. It is one of _the_
915	* inner loops that should be optimized like hell to get the best
916	* performance.
917	*/
918	static void
919	Split_Cubic( TPoint* base )
920	{
921	Long a, b, c;
922
923
924	base[`6`].x = base[`3`].x;
925	a = base[`0`].x + base[`1`].x;
926	b = base[`1`].x + base[`2`].x;
927	c = base[`2`].x + base[`3`].x;
928	base[`5`].x = c >> `1`;
929	c += b;
930	base[`4`].x = c >> `2`;
931	base[`1`].x = a >> `1`;
932	a += b;
933	base[`2`].x = a >> `2`;
934	base[`3`].x = ( a + c ) >> `3`;
935
936	base[`6`].y = base[`3`].y;
937	a = base[`0`].y + base[`1`].y;
938	b = base[`1`].y + base[`2`].y;
939	c = base[`2`].y + base[`3`].y;
940	base[`5`].y = c >> `1`;
941	c += b;
942	base[`4`].y = c >> `2`;
943	base[`1`].y = a >> `1`;
944	a += b;
945	base[`2`].y = a >> `2`;
946	base[`3`].y = ( a + c ) >> `3`;
947	}
948
949
950	/**************************************************************************
951	*
952	* @Function:
953	* Line_Up
954	*
955	* @Description:
956	* Compute the x-coordinates of an ascending line segment and store
957	* them in the render pool.
958	*
959	* @Input:
960	* x1 ::
961	* The x-coordinate of the segment's start point.
962	*
963	* y1 ::
964	* The y-coordinate of the segment's start point.
965	*
966	* x2 ::
967	* The x-coordinate of the segment's end point.
968	*
969	* y2 ::
970	* The y-coordinate of the segment's end point.
971	*
972	* miny ::
973	* A lower vertical clipping bound value.
974	*
975	* maxy ::
976	* An upper vertical clipping bound value.
977	*
978	* @Return:
979	* SUCCESS on success, FAILURE on render pool overflow.
980	*/
981	static Bool
982	Line_Up( RAS_ARGS Long x1,
983	Long y1,
984	Long x2,
985	Long y2,
986	Long miny,
987	Long maxy )
988	{
989	Long Dx, Dy;
990	Int e1, e2, f1, f2, size; / XXX: is `Short' sufficient? /
991	Long Ix, Rx, Ax;
992
993	PLong top;
994
995
996	Dx = x2 - x1;
997	Dy = y2 - y1;
998
999	if ( Dy <= `0` \|\| y2 < miny \|\| y1 > maxy )
1000	return SUCCESS;
1001
1002	if ( y1 < miny )
1003	{
1004	/ Take care: miny-y1 can be a very large value; we use /
1005	/ a slow MulDiv function to avoid clipping bugs /
1006	x1 += SMulDiv( Dx, miny - y1, Dy );
1007	e1 = (Int)TRUNC( miny );
1008	f1 = `0`;
1009	}
1010	else
1011	{
1012	e1 = (Int)TRUNC( y1 );
1013	f1 = (Int)FRAC( y1 );
1014	}
1015
1016	if ( y2 > maxy )
1017	{
1018	/ x2 += FMulDiv( Dx, maxy - y2, Dy ); UNNECESSARY /
1019	e2 = (Int)TRUNC( maxy );
1020	f2 = `0`;
1021	}
1022	else
1023	{
1024	e2 = (Int)TRUNC( y2 );
1025	f2 = (Int)FRAC( y2 );
1026	}
1027
1028	if ( f1 > `0` )
1029	{
1030	if ( e1 == e2 )
1031	return SUCCESS;
1032	else
1033	{
1034	x1 += SMulDiv( Dx, ras.precision - f1, Dy );
1035	e1 += `1`;
1036	}
1037	}
1038	else
1039	if ( ras.joint )
1040	{
1041	ras.top--;
1042	ras.joint = FALSE;
1043	}
1044
1045	ras.joint = (char)( f2 == `0` );
1046
1047	if ( ras.fresh )
1048	{
1049	ras.cProfile->start = e1;
1050	ras.fresh = FALSE;
1051	}
1052
1053	size = e2 - e1 + `1`;
1054	if ( ras.top + size >= ras.maxBuff )
1055	{
1056	ras.error = FT_THROW( Raster_Overflow );
1057	return FAILURE;
1058	}
1059
1060	if ( Dx > `0` )
1061	{
1062	Ix = SMulDiv_No_Round( ras.precision, Dx, Dy );
1063	Rx = ( ras.precision * Dx ) % Dy;
1064	Dx = `1`;
1065	}
1066	else
1067	{
1068	Ix = -SMulDiv_No_Round( ras.precision, -Dx, Dy );
1069	Rx = ( ras.precision * -Dx ) % Dy;
1070	Dx = -`1`;
1071	}
1072
1073	Ax = -Dy;
1074	top = ras.top;
1075
1076	while ( size > `0` )
1077	{
1078	*top++ = x1;
1079
1080	x1 += Ix;
1081	Ax += Rx;
1082	if ( Ax >= `0` )
1083	{
1084	Ax -= Dy;
1085	x1 += Dx;
1086	}
1087	size--;
1088	}
1089
1090	ras.top = top;
1091	return SUCCESS;
1092	}
1093
1094
1095	/**************************************************************************
1096	*
1097	* @Function:
1098	* Line_Down
1099	*
1100	* @Description:
1101	* Compute the x-coordinates of an descending line segment and store
1102	* them in the render pool.
1103	*
1104	* @Input:
1105	* x1 ::
1106	* The x-coordinate of the segment's start point.
1107	*
1108	* y1 ::
1109	* The y-coordinate of the segment's start point.
1110	*
1111	* x2 ::
1112	* The x-coordinate of the segment's end point.
1113	*
1114	* y2 ::
1115	* The y-coordinate of the segment's end point.
1116	*
1117	* miny ::
1118	* A lower vertical clipping bound value.
1119	*
1120	* maxy ::
1121	* An upper vertical clipping bound value.
1122	*
1123	* @Return:
1124	* SUCCESS on success, FAILURE on render pool overflow.
1125	*/
1126	static Bool
1127	Line_Down( RAS_ARGS Long x1,
1128	Long y1,
1129	Long x2,
1130	Long y2,
1131	Long miny,
1132	Long maxy )
1133	{
1134	Bool result, fresh;
1135
1136
1137	fresh = ras.fresh;
1138
1139	result = Line_Up( RAS_VARS x1, -y1, x2, -y2, -maxy, -miny );
1140
1141	if ( fresh && !ras.fresh )
1142	ras.cProfile->start = -ras.cProfile->start;
1143
1144	return result;
1145	}
1146
1147
1148	/ A function type describing the functions used to split Bezier arcs /
1149	typedef void (TSplitter)( TPoint base );
1150
1151
1152	/**************************************************************************
1153	*
1154	* @Function:
1155	* Bezier_Up
1156	*
1157	* @Description:
1158	* Compute the x-coordinates of an ascending Bezier arc and store
1159	* them in the render pool.
1160	*
1161	* @Input:
1162	* degree ::
1163	* The degree of the Bezier arc (either 2 or 3).
1164	*
1165	* splitter ::
1166	* The function to split Bezier arcs.
1167	*
1168	* miny ::
1169	* A lower vertical clipping bound value.
1170	*
1171	* maxy ::
1172	* An upper vertical clipping bound value.
1173	*
1174	* @Return:
1175	* SUCCESS on success, FAILURE on render pool overflow.
1176	*/
1177	static Bool
1178	Bezier_Up( RAS_ARGS Int degree,
1179	TPoint* arc,
1180	TSplitter splitter,
1181	Long miny,
1182	Long maxy )
1183	{
1184	Long y1, y2, e, e2, e0;
1185	Short f1;
1186
1187	TPoint* start_arc;
1188
1189	PLong top;
1190
1191
1192	y1 = arc[degree].y;
1193	y2 = arc[`0`].y;
1194	top = ras.top;
1195
1196	if ( y2 < miny \|\| y1 > maxy )
1197	goto Fin;
1198
1199	e2 = FLOOR( y2 );
1200
1201	if ( e2 > maxy )
1202	e2 = maxy;
1203
1204	e0 = miny;
1205
1206	if ( y1 < miny )
1207	e = miny;
1208	else
1209	{
1210	e = CEILING( y1 );
1211	f1 = (Short)( FRAC( y1 ) );
1212	e0 = e;
1213
1214	if ( f1 == `0` )
1215	{
1216	if ( ras.joint )
1217	{
1218	top--;
1219	ras.joint = FALSE;
1220	}
1221
1222	*top++ = arc[degree].x;
1223
1224	e += ras.precision;
1225	}
1226	}
1227
1228	if ( ras.fresh )
1229	{
1230	ras.cProfile->start = TRUNC( e0 );
1231	ras.fresh = FALSE;
1232	}
1233
1234	if ( e2 < e )
1235	goto Fin;
1236
1237	if ( ( top + TRUNC( e2 - e ) + `1` ) >= ras.maxBuff )
1238	{
1239	ras.top = top;
1240	ras.error = FT_THROW( Raster_Overflow );
1241	return FAILURE;
1242	}
1243
1244	start_arc = arc;
1245
1246	do
1247	{
1248	ras.joint = FALSE;
1249
1250	y2 = arc[`0`].y;
1251
1252	if ( y2 > e )
1253	{
1254	y1 = arc[degree].y;
1255	if ( y2 - y1 >= ras.precision_step )
1256	{
1257	splitter( arc );
1258	arc += degree;
1259	}
1260	else
1261	{
1262	*top++ = arc[degree].x + FMulDiv( arc[`0`].x - arc[degree].x,
1263	e - y1, y2 - y1 );
1264	arc -= degree;
1265	e += ras.precision;
1266	}
1267	}
1268	else
1269	{
1270	if ( y2 == e )
1271	{
1272	ras.joint = TRUE;
1273	*top++ = arc[`0`].x;
1274
1275	e += ras.precision;
1276	}
1277	arc -= degree;
1278	}
1279	} while ( arc >= start_arc && e <= e2 );
1280
1281	Fin:
1282	ras.top = top;
1283	return SUCCESS;
1284	}
1285
1286
1287	/**************************************************************************
1288	*
1289	* @Function:
1290	* Bezier_Down
1291	*
1292	* @Description:
1293	* Compute the x-coordinates of an descending Bezier arc and store
1294	* them in the render pool.
1295	*
1296	* @Input:
1297	* degree ::
1298	* The degree of the Bezier arc (either 2 or 3).
1299	*
1300	* splitter ::
1301	* The function to split Bezier arcs.
1302	*
1303	* miny ::
1304	* A lower vertical clipping bound value.
1305	*
1306	* maxy ::
1307	* An upper vertical clipping bound value.
1308	*
1309	* @Return:
1310	* SUCCESS on success, FAILURE on render pool overflow.
1311	*/
1312	static Bool
1313	Bezier_Down( RAS_ARGS Int degree,
1314	TPoint* arc,
1315	TSplitter splitter,
1316	Long miny,
1317	Long maxy )
1318	{
1319	Bool result, fresh;
1320
1321
1322	arc[`0`].y = -arc[`0`].y;
1323	arc[`1`].y = -arc[`1`].y;
1324	arc[`2`].y = -arc[`2`].y;
1325	if ( degree > `2` )
1326	arc[`3`].y = -arc[`3`].y;
1327
1328	fresh = ras.fresh;
1329
1330	result = Bezier_Up( RAS_VARS degree, arc, splitter, -maxy, -miny );
1331
1332	if ( fresh && !ras.fresh )
1333	ras.cProfile->start = -ras.cProfile->start;
1334
1335	arc[`0`].y = -arc[`0`].y;
1336	return result;
1337	}
1338
1339
1340	/**************************************************************************
1341	*
1342	* @Function:
1343	* Line_To
1344	*
1345	* @Description:
1346	* Inject a new line segment and adjust the Profiles list.
1347	*
1348	* @Input:
1349	* x ::
1350	* The x-coordinate of the segment's end point (its start point
1351	* is stored in `lastX').
1352	*
1353	* y ::
1354	* The y-coordinate of the segment's end point (its start point
1355	* is stored in `lastY').
1356	*
1357	* @Return:
1358	* SUCCESS on success, FAILURE on render pool overflow or incorrect
1359	* profile.
1360	*/
1361	static Bool
1362	Line_To( RAS_ARGS Long x,
1363	Long y )
1364	{
1365	/ First, detect a change of direction /
1366
1367	switch ( ras.state )
1368	{
1369	case Unknown_State:
1370	if ( y > ras.lastY )
1371	{
1372	if ( New_Profile( RAS_VARS Ascending_State,
1373	IS_BOTTOM_OVERSHOOT( ras.lastY ) ) )
1374	return FAILURE;
1375	}
1376	else
1377	{
1378	if ( y < ras.lastY )
1379	if ( New_Profile( RAS_VARS Descending_State,
1380	IS_TOP_OVERSHOOT( ras.lastY ) ) )
1381	return FAILURE;
1382	}
1383	break;
1384
1385	case Ascending_State:
1386	if ( y < ras.lastY )
1387	{
1388	if ( End_Profile( RAS_VARS IS_TOP_OVERSHOOT( ras.lastY ) ) \|\|
1389	New_Profile( RAS_VARS Descending_State,
1390	IS_TOP_OVERSHOOT( ras.lastY ) ) )
1391	return FAILURE;
1392	}
1393	break;
1394
1395	case Descending_State:
1396	if ( y > ras.lastY )
1397	{
1398	if ( End_Profile( RAS_VARS IS_BOTTOM_OVERSHOOT( ras.lastY ) ) \|\|
1399	New_Profile( RAS_VARS Ascending_State,
1400	IS_BOTTOM_OVERSHOOT( ras.lastY ) ) )
1401	return FAILURE;
1402	}
1403	break;
1404
1405	default:
1406	;
1407	}
1408
1409	/ Then compute the lines /
1410
1411	switch ( ras.state )
1412	{
1413	case Ascending_State:
1414	if ( Line_Up( RAS_VARS ras.lastX, ras.lastY,
1415	x, y, ras.minY, ras.maxY ) )
1416	return FAILURE;
1417	break;
1418
1419	case Descending_State:
1420	if ( Line_Down( RAS_VARS ras.lastX, ras.lastY,
1421	x, y, ras.minY, ras.maxY ) )
1422	return FAILURE;
1423	break;
1424
1425	default:
1426	;
1427	}
1428
1429	ras.lastX = x;
1430	ras.lastY = y;
1431
1432	return SUCCESS;
1433	}
1434
1435
1436	/**************************************************************************
1437	*
1438	* @Function:
1439	* Conic_To
1440	*
1441	* @Description:
1442	* Inject a new conic arc and adjust the profile list.
1443	*
1444	* @Input:
1445	* cx ::
1446	* The x-coordinate of the arc's new control point.
1447	*
1448	* cy ::
1449	* The y-coordinate of the arc's new control point.
1450	*
1451	* x ::
1452	* The x-coordinate of the arc's end point (its start point is
1453	* stored in `lastX').
1454	*
1455	* y ::
1456	* The y-coordinate of the arc's end point (its start point is
1457	* stored in `lastY').
1458	*
1459	* @Return:
1460	* SUCCESS on success, FAILURE on render pool overflow or incorrect
1461	* profile.
1462	*/
1463	static Bool
1464	Conic_To( RAS_ARGS Long cx,
1465	Long cy,
1466	Long x,
1467	Long y )
1468	{
1469	Long y1, y2, y3, x3, ymin, ymax;
1470	TStates state_bez;
1471	TPoint arcs[`2` * MaxBezier + `1`]; / The Bezier stack /
1472	TPoint* arc; / current Bezier arc pointer /
1473
1474
1475	arc = arcs;
1476	arc[`2`].x = ras.lastX;
1477	arc[`2`].y = ras.lastY;
1478	arc[`1`].x = cx;
1479	arc[`1`].y = cy;
1480	arc[`0`].x = x;
1481	arc[`0`].y = y;
1482
1483	do
1484	{
1485	y1 = arc[`2`].y;
1486	y2 = arc[`1`].y;
1487	y3 = arc[`0`].y;
1488	x3 = arc[`0`].x;
1489
1490	/ first, categorize the Bezier arc /
1491
1492	if ( y1 <= y3 )
1493	{
1494	ymin = y1;
1495	ymax = y3;
1496	}
1497	else
1498	{
1499	ymin = y3;
1500	ymax = y1;
1501	}
1502
1503	if ( y2 < ymin \|\| y2 > ymax )
1504	{
1505	/ this arc has no given direction, split it! /
1506	Split_Conic( arc );
1507	arc += `2`;
1508	}
1509	else if ( y1 == y3 )
1510	{
1511	/ this arc is flat, ignore it and pop it from the Bezier stack /
1512	arc -= `2`;
1513	}
1514	else
1515	{
1516	/ the arc is y-monotonous, either ascending or descending /
1517	/ detect a change of direction /
1518	state_bez = y1 < y3 ? Ascending_State : Descending_State;
1519	if ( ras.state != state_bez )
1520	{
1521	Bool o = ( state_bez == Ascending_State )
1522	? IS_BOTTOM_OVERSHOOT( y1 )
1523	: IS_TOP_OVERSHOOT( y1 );
1524
1525
1526	/ finalize current profile if any /
1527	if ( ras.state != Unknown_State &&
1528	End_Profile( RAS_VARS o ) )
1529	goto Fail;
1530
1531	/ create a new profile /
1532	if ( New_Profile( RAS_VARS state_bez, o ) )
1533	goto Fail;
1534	}
1535
1536	/ now call the appropriate routine /
1537	if ( state_bez == Ascending_State )
1538	{
1539	if ( Bezier_Up( RAS_VARS `2`, arc, Split_Conic,
1540	ras.minY, ras.maxY ) )
1541	goto Fail;
1542	}
1543	else
1544	if ( Bezier_Down( RAS_VARS `2`, arc, Split_Conic,
1545	ras.minY, ras.maxY ) )
1546	goto Fail;
1547	arc -= `2`;
1548	}
1549
1550	} while ( arc >= arcs );
1551
1552	ras.lastX = x3;
1553	ras.lastY = y3;
1554
1555	return SUCCESS;
1556
1557	Fail:
1558	return FAILURE;
1559	}
1560
1561
1562	/**************************************************************************
1563	*
1564	* @Function:
1565	* Cubic_To
1566	*
1567	* @Description:
1568	* Inject a new cubic arc and adjust the profile list.
1569	*
1570	* @Input:
1571	* cx1 ::
1572	* The x-coordinate of the arc's first new control point.
1573	*
1574	* cy1 ::
1575	* The y-coordinate of the arc's first new control point.
1576	*
1577	* cx2 ::
1578	* The x-coordinate of the arc's second new control point.
1579	*
1580	* cy2 ::
1581	* The y-coordinate of the arc's second new control point.
1582	*
1583	* x ::
1584	* The x-coordinate of the arc's end point (its start point is
1585	* stored in `lastX').
1586	*
1587	* y ::
1588	* The y-coordinate of the arc's end point (its start point is
1589	* stored in `lastY').
1590	*
1591	* @Return:
1592	* SUCCESS on success, FAILURE on render pool overflow or incorrect
1593	* profile.
1594	*/
1595	static Bool
1596	Cubic_To( RAS_ARGS Long cx1,
1597	Long cy1,
1598	Long cx2,
1599	Long cy2,
1600	Long x,
1601	Long y )
1602	{
1603	Long y1, y2, y3, y4, x4, ymin1, ymax1, ymin2, ymax2;
1604	TStates state_bez;
1605	TPoint arcs[`3` * MaxBezier + `1`]; / The Bezier stack /
1606	TPoint* arc; / current Bezier arc pointer /
1607
1608
1609	arc = arcs;
1610	arc[`3`].x = ras.lastX;
1611	arc[`3`].y = ras.lastY;
1612	arc[`2`].x = cx1;
1613	arc[`2`].y = cy1;
1614	arc[`1`].x = cx2;
1615	arc[`1`].y = cy2;
1616	arc[`0`].x = x;
1617	arc[`0`].y = y;
1618
1619	do
1620	{
1621	y1 = arc[`3`].y;
1622	y2 = arc[`2`].y;
1623	y3 = arc[`1`].y;
1624	y4 = arc[`0`].y;
1625	x4 = arc[`0`].x;
1626
1627	/ first, categorize the Bezier arc /
1628
1629	if ( y1 <= y4 )
1630	{
1631	ymin1 = y1;
1632	ymax1 = y4;
1633	}
1634	else
1635	{
1636	ymin1 = y4;
1637	ymax1 = y1;
1638	}
1639
1640	if ( y2 <= y3 )
1641	{
1642	ymin2 = y2;
1643	ymax2 = y3;
1644	}
1645	else
1646	{
1647	ymin2 = y3;
1648	ymax2 = y2;
1649	}
1650
1651	if ( ymin2 < ymin1 \|\| ymax2 > ymax1 )
1652	{
1653	/ this arc has no given direction, split it! /
1654	Split_Cubic( arc );
1655	arc += `3`;
1656	}
1657	else if ( y1 == y4 )
1658	{
1659	/ this arc is flat, ignore it and pop it from the Bezier stack /
1660	arc -= `3`;
1661	}
1662	else
1663	{
1664	state_bez = ( y1 <= y4 ) ? Ascending_State : Descending_State;
1665
1666	/ detect a change of direction /
1667	if ( ras.state != state_bez )
1668	{
1669	Bool o = ( state_bez == Ascending_State )
1670	? IS_BOTTOM_OVERSHOOT( y1 )
1671	: IS_TOP_OVERSHOOT( y1 );
1672
1673
1674	/ finalize current profile if any /
1675	if ( ras.state != Unknown_State &&
1676	End_Profile( RAS_VARS o ) )
1677	goto Fail;
1678
1679	if ( New_Profile( RAS_VARS state_bez, o ) )
1680	goto Fail;
1681	}
1682
1683	/ compute intersections /
1684	if ( state_bez == Ascending_State )
1685	{
1686	if ( Bezier_Up( RAS_VARS `3`, arc, Split_Cubic,
1687	ras.minY, ras.maxY ) )
1688	goto Fail;
1689	}
1690	else
1691	if ( Bezier_Down( RAS_VARS `3`, arc, Split_Cubic,
1692	ras.minY, ras.maxY ) )
1693	goto Fail;
1694	arc -= `3`;
1695	}
1696
1697	} while ( arc >= arcs );
1698
1699	ras.lastX = x4;
1700	ras.lastY = y4;
1701
1702	return SUCCESS;
1703
1704	Fail:
1705	return FAILURE;
1706	}
1707
1708
1709	#undef SWAP_
1710	#define SWAP_( x, y ) do \
1711	{ \
1712	Long swap = x; \
1713	\
1714	\
1715	x = y; \
1716	y = swap; \
1717	} while ( 0 )
1718
1719
1720	/**************************************************************************
1721	*
1722	* @Function:
1723	* Decompose_Curve
1724	*
1725	* @Description:
1726	* Scan the outline arrays in order to emit individual segments and
1727	* Beziers by calling Line_To() and Bezier_To(). It handles all
1728	* weird cases, like when the first point is off the curve, or when
1729	* there are simply no `on' points in the contour!
1730	*
1731	* @Input:
1732	* first ::
1733	* The index of the first point in the contour.
1734	*
1735	* last ::
1736	* The index of the last point in the contour.
1737	*
1738	* flipped ::
1739	* If set, flip the direction of the curve.
1740	*
1741	* @Return:
1742	* SUCCESS on success, FAILURE on error.
1743	*/
1744	static Bool
1745	Decompose_Curve( RAS_ARGS Int first,
1746	Int last,
1747	Int flipped )
1748	{
1749	FT_Vector v_last;
1750	FT_Vector v_control;
1751	FT_Vector v_start;
1752
1753	FT_Vector* points;
1754	FT_Vector* point;
1755	FT_Vector* limit;
1756	char* tags;
1757
1758	UInt tag; / current point's state /
1759
1760
1761	points = ras.outline.points;
1762	limit = points + last;
1763
1764	v_start.x = SCALED( points[first].x );
1765	v_start.y = SCALED( points[first].y );
1766	v_last.x = SCALED( points[last].x );
1767	v_last.y = SCALED( points[last].y );
1768
1769	if ( flipped )
1770	{
1771	SWAP_( v_start.x, v_start.y );
1772	SWAP_( v_last.x, v_last.y );
1773	}
1774
1775	v_control = v_start;
1776
1777	point = points + first;
1778	tags = ras.outline.tags + first;
1779
1780	/ set scan mode if necessary /
1781	if ( tags[`0`] & FT_CURVE_TAG_HAS_SCANMODE )
1782	ras.dropOutControl = (Byte)tags[`0`] >> `5`;
1783
1784	tag = FT_CURVE_TAG( tags[`0`] );
1785
1786	/ A contour cannot start with a cubic control point! /
1787	if ( tag == FT_CURVE_TAG_CUBIC )
1788	goto Invalid_Outline;
1789
1790	/ check first point to determine origin /
1791	if ( tag == FT_CURVE_TAG_CONIC )
1792	{
1793	/ first point is conic control. Yes, this happens. /
1794	if ( FT_CURVE_TAG( ras.outline.tags[last] ) == FT_CURVE_TAG_ON )
1795	{
1796	/ start at last point if it is on the curve /
1797	v_start = v_last;
1798	limit--;
1799	}
1800	else
1801	{
1802	/ if both first and last points are conic, /
1803	/ start at their middle and record its position /
1804	/ for closure /
1805	v_start.x = ( v_start.x + v_last.x ) / `2`;
1806	v_start.y = ( v_start.y + v_last.y ) / `2`;
1807
1808	/ v_last = v_start; /
1809	}
1810	point--;
1811	tags--;
1812	}
1813
1814	ras.lastX = v_start.x;
1815	ras.lastY = v_start.y;
1816
1817	while ( point < limit )
1818	{
1819	point++;
1820	tags++;
1821
1822	tag = FT_CURVE_TAG( tags[`0`] );
1823
1824	switch ( tag )
1825	{
1826	case FT_CURVE_TAG_ON: / emit a single line_to /
1827	{
1828	Long x, y;
1829
1830
1831	x = SCALED( point->x );
1832	y = SCALED( point->y );
1833	if ( flipped )
1834	SWAP_( x, y );
1835
1836	if ( Line_To( RAS_VARS x, y ) )
1837	goto Fail;
1838	continue;
1839	}
1840
1841	case FT_CURVE_TAG_CONIC: / consume conic arcs /
1842	v_control.x = SCALED( point[`0`].x );
1843	v_control.y = SCALED( point[`0`].y );
1844
1845	if ( flipped )
1846	SWAP_( v_control.x, v_control.y );
1847
1848	Do_Conic:
1849	if ( point < limit )
1850	{
1851	FT_Vector v_middle;
1852	Long x, y;
1853
1854
1855	point++;
1856	tags++;
1857	tag = FT_CURVE_TAG( tags[`0`] );
1858
1859	x = SCALED( point[`0`].x );
1860	y = SCALED( point[`0`].y );
1861
1862	if ( flipped )
1863	SWAP_( x, y );
1864
1865	if ( tag == FT_CURVE_TAG_ON )
1866	{
1867	if ( Conic_To( RAS_VARS v_control.x, v_control.y, x, y ) )
1868	goto Fail;
1869	continue;
1870	}
1871
1872	if ( tag != FT_CURVE_TAG_CONIC )
1873	goto Invalid_Outline;
1874
1875	v_middle.x = ( v_control.x + x ) / `2`;
1876	v_middle.y = ( v_control.y + y ) / `2`;
1877
1878	if ( Conic_To( RAS_VARS v_control.x, v_control.y,
1879	v_middle.x, v_middle.y ) )
1880	goto Fail;
1881
1882	v_control.x = x;
1883	v_control.y = y;
1884
1885	goto Do_Conic;
1886	}
1887
1888	if ( Conic_To( RAS_VARS v_control.x, v_control.y,
1889	v_start.x, v_start.y ) )
1890	goto Fail;
1891
1892	goto Close;
1893
1894	default: / FT_CURVE_TAG_CUBIC /
1895	{
1896	Long x1, y1, x2, y2, x3, y3;
1897
1898
1899	if ( point + `1` > limit \|\|
1900	FT_CURVE_TAG( tags[`1`] ) != FT_CURVE_TAG_CUBIC )
1901	goto Invalid_Outline;
1902
1903	point += `2`;
1904	tags += `2`;
1905
1906	x1 = SCALED( point[-`2`].x );
1907	y1 = SCALED( point[-`2`].y );
1908	x2 = SCALED( point[-`1`].x );
1909	y2 = SCALED( point[-`1`].y );
1910
1911	if ( flipped )
1912	{
1913	SWAP_( x1, y1 );
1914	SWAP_( x2, y2 );
1915	}
1916
1917	if ( point <= limit )
1918	{
1919	x3 = SCALED( point[`0`].x );
1920	y3 = SCALED( point[`0`].y );
1921
1922	if ( flipped )
1923	SWAP_( x3, y3 );
1924
1925	if ( Cubic_To( RAS_VARS x1, y1, x2, y2, x3, y3 ) )
1926	goto Fail;
1927	continue;
1928	}
1929
1930	if ( Cubic_To( RAS_VARS x1, y1, x2, y2, v_start.x, v_start.y ) )
1931	goto Fail;
1932	goto Close;
1933	}
1934	}
1935	}
1936
1937	/ close the contour with a line segment /
1938	if ( Line_To( RAS_VARS v_start.x, v_start.y ) )
1939	goto Fail;
1940
1941	Close:
1942	return SUCCESS;
1943
1944	Invalid_Outline:
1945	ras.error = FT_THROW( Invalid_Outline );
1946
1947	Fail:
1948	return FAILURE;
1949	}
1950
1951
1952	/**************************************************************************
1953	*
1954	* @Function:
1955	* Convert_Glyph
1956	*
1957	* @Description:
1958	* Convert a glyph into a series of segments and arcs and make a
1959	* profiles list with them.
1960	*
1961	* @Input:
1962	* flipped ::
1963	* If set, flip the direction of curve.
1964	*
1965	* @Return:
1966	* SUCCESS on success, FAILURE if any error was encountered during
1967	* rendering.
1968	*/
1969	static Bool
1970	Convert_Glyph( RAS_ARGS Int flipped )
1971	{
1972	Int i;
1973	Int first, last;
1974
1975
1976	ras.fProfile = NULL;
1977	ras.joint = FALSE;
1978	ras.fresh = FALSE;
1979
1980	ras.maxBuff = ras.sizeBuff - AlignProfileSize;
1981
1982	ras.numTurns = `0`;
1983
1984	ras.cProfile = (PProfile)ras.top;
1985	ras.cProfile->offset = ras.top;
1986	ras.num_Profs = `0`;
1987
1988	last = -`1`;
1989	for ( i = `0`; i < ras.outline.n_contours; i++ )
1990	{
1991	PProfile lastProfile;
1992	Bool o;
1993
1994
1995	ras.state = Unknown_State;
1996	ras.gProfile = NULL;
1997
1998	first = last + `1`;
1999	last = ras.outline.contours[i];
2000
2001	if ( Decompose_Curve( RAS_VARS first, last, flipped ) )
2002	return FAILURE;
2003
2004	/ we must now check whether the extreme arcs join or not /
2005	if ( FRAC( ras.lastY ) == `0` &&
2006	ras.lastY >= ras.minY &&
2007	ras.lastY <= ras.maxY )
2008	if ( ras.gProfile &&
2009	( ras.gProfile->flags & Flow_Up ) ==
2010	( ras.cProfile->flags & Flow_Up ) )
2011	ras.top--;
2012	/ Note that ras.gProfile can be nil if the contour was too small /
2013	/ to be drawn. /
2014
2015	lastProfile = ras.cProfile;
2016	if ( ras.top != ras.cProfile->offset &&
2017	( ras.cProfile->flags & Flow_Up ) )
2018	o = IS_TOP_OVERSHOOT( ras.lastY );
2019	else
2020	o = IS_BOTTOM_OVERSHOOT( ras.lastY );
2021	if ( End_Profile( RAS_VARS o ) )
2022	return FAILURE;
2023
2024	/ close the `next profile in contour' linked list /
2025	if ( ras.gProfile )
2026	lastProfile->next = ras.gProfile;
2027	}
2028
2029	if ( Finalize_Profile_Table( RAS_VAR ) )
2030	return FAILURE;
2031
2032	return (Bool)( ras.top < ras.maxBuff ? SUCCESS : FAILURE );
2033	}
2034
2035
2036	/***********************************************************************/
2037	/***********************************************************************/
2038	/* */
2039	/* SCAN-LINE SWEEPS AND DRAWING */
2040	/* */
2041	/***********************************************************************/
2042	/***********************************************************************/
2043
2044
2045	/**************************************************************************
2046	*
2047	* Init_Linked
2048	*
2049	* Initializes an empty linked list.
2050	*/
2051	static void
2052	Init_Linked( TProfileList* l )
2053	{
2054	*l = NULL;
2055	}
2056
2057
2058	/**************************************************************************
2059	*
2060	* InsNew
2061	*
2062	* Inserts a new profile in a linked list.
2063	*/
2064	static void
2065	InsNew( PProfileList list,
2066	PProfile profile )
2067	{
2068	PProfile *old, current;
2069	Long x;
2070
2071
2072	old = list;
2073	current = *old;
2074	x = profile->X;
2075
2076	while ( current )
2077	{
2078	if ( x < current->X )
2079	break;
2080	old = &current->link;
2081	current = *old;
2082	}
2083
2084	profile->link = current;
2085	*old = profile;
2086	}
2087
2088
2089	/**************************************************************************
2090	*
2091	* DelOld
2092	*
2093	* Removes an old profile from a linked list.
2094	*/
2095	static void
2096	DelOld( PProfileList list,
2097	const PProfile profile )
2098	{
2099	PProfile *old, current;
2100
2101
2102	old = list;
2103	current = *old;
2104
2105	while ( current )
2106	{
2107	if ( current == profile )
2108	{
2109	*old = current->link;
2110	return;
2111	}
2112
2113	old = &current->link;
2114	current = *old;
2115	}
2116
2117	/ we should never get there, unless the profile was not part of /
2118	/ the list. /
2119	}
2120
2121
2122	/**************************************************************************
2123	*
2124	* Sort
2125	*
2126	* Sorts a trace list. In 95%, the list is already sorted. We need
2127	* an algorithm which is fast in this case. Bubble sort is enough
2128	* and simple.
2129	*/
2130	static void
2131	Sort( PProfileList list )
2132	{
2133	PProfile *old, current, next;
2134
2135
2136	/ First, set the new X coordinate of each profile /
2137	current = *list;
2138	while ( current )
2139	{
2140	current->X = *current->offset;
2141	current->offset += ( current->flags & Flow_Up ) ? `1` : -`1`;
2142	current->height--;
2143	current = current->link;
2144	}
2145
2146	/ Then sort them /
2147	old = list;
2148	current = *old;
2149
2150	if ( !current )
2151	return;
2152
2153	next = current->link;
2154
2155	while ( next )
2156	{
2157	if ( current->X <= next->X )
2158	{
2159	old = &current->link;
2160	current = *old;
2161
2162	if ( !current )
2163	return;
2164	}
2165	else
2166	{
2167	*old = next;
2168	current->link = next->link;
2169	next->link = current;
2170
2171	old = list;
2172	current = *old;
2173	}
2174
2175	next = current->link;
2176	}
2177	}
2178
2179
2180	/**************************************************************************
2181	*
2182	* Vertical Sweep Procedure Set
2183	*
2184	* These four routines are used during the vertical black/white sweep
2185	* phase by the generic Draw_Sweep() function.
2186	*
2187	*/
2188
2189	static void
2190	Vertical_Sweep_Init( RAS_ARGS Short min,
2191	Short max )
2192	{
2193	FT_UNUSED( max );
2194
2195
2196	ras.bLine = ras.bOrigin - min * ras.target.pitch;
2197	}
2198
2199
2200	static void
2201	Vertical_Sweep_Span( RAS_ARGS Short y,
2202	FT_F26Dot6 x1,
2203	FT_F26Dot6 x2,
2204	PProfile left,
2205	PProfile right )
2206	{
2207	Long e1, e2;
2208
2209	Int dropOutControl = left->flags & `7`;
2210
2211	FT_UNUSED( y );
2212	FT_UNUSED( left );
2213	FT_UNUSED( right );
2214
2215
2216	/ in high-precision mode, we need 12 digits after the comma to /
2217	/ represent multiples of 1/(1<<12) = 1/4096 /
2218	FT_TRACE7(( " y=%d x=[% .12f;% .12f]",
2219	y,
2220	(double)x1 / (double)ras.precision,
2221	(double)x2 / (double)ras.precision ));
2222
2223	/ Drop-out control /
2224
2225	e1 = CEILING( x1 );
2226	e2 = FLOOR( x2 );
2227
2228	/ take care of the special case where both the left /
2229	/ and right contour lie exactly on pixel centers /
2230	if ( dropOutControl != `2` &&
2231	x2 - x1 - ras.precision <= ras.precision_jitter &&
2232	e1 != x1 && e2 != x2 )
2233	e2 = e1;
2234
2235	e1 = TRUNC( e1 );
2236	e2 = TRUNC( e2 );
2237
2238	if ( e2 >= `0` && e1 < ras.bWidth )
2239	{
2240	Byte* target;
2241
2242	Int c1, c2;
2243	Byte f1, f2;
2244
2245
2246	if ( e1 < `0` )
2247	e1 = `0`;
2248	if ( e2 >= ras.bWidth )
2249	e2 = ras.bWidth - `1`;
2250
2251	FT_TRACE7(( " -> x=[%ld;%ld]", e1, e2 ));
2252
2253	c1 = (Short)( e1 >> `3` );
2254	c2 = (Short)( e2 >> `3` );
2255
2256	f1 = (Byte) ( `0xFF` >> ( e1 & `7` ) );
2257	f2 = (Byte) ~( `0x7F` >> ( e2 & `7` ) );
2258
2259	target = ras.bLine + c1;
2260	c2 -= c1;
2261
2262	if ( c2 > `0` )
2263	{
2264	target[`0`] \|= f1;
2265
2266	/ memset() is slower than the following code on many platforms. /
2267	/ This is due to the fact that, in the vast majority of cases, /
2268	/ the span length in bytes is relatively small. /
2269	while ( --c2 > `0` )
2270	*( ++target ) = `0xFF`;
2271
2272	target[`1`] \|= f2;
2273	}
2274	else
2275	*target \|= ( f1 & f2 );
2276	}
2277
2278	FT_TRACE7(( "\n" ));
2279	}
2280
2281
2282	static void
2283	Vertical_Sweep_Drop( RAS_ARGS Short y,
2284	FT_F26Dot6 x1,
2285	FT_F26Dot6 x2,
2286	PProfile left,
2287	PProfile right )
2288	{
2289	Long e1, e2, pxl;
2290	Short c1, f1;
2291
2292
2293	FT_TRACE7(( " y=%d x=[% .12f;% .12f]",
2294	y,
2295	(double)x1 / (double)ras.precision,
2296	(double)x2 / (double)ras.precision ));
2297
2298	/ Drop-out control /
2299
2300	/ e2 x2 x1 e1 /
2301	/ /
2302	/ ^ \| /
2303	/ \| \| /
2304	/ +-------------+---------------------+------------+ /
2305	/ \| \| /
2306	/ \| v /
2307	/ /
2308	/ pixel contour contour pixel /
2309	/ center center /
2310
2311	/ drop-out mode scan conversion rules (as defined in OpenType) /
2312	/ --------------------------------------------------------------- /
2313	/ 0 1, 2, 3 /
2314	/ 1 1, 2, 4 /
2315	/ 2 1, 2 /
2316	/ 3 same as mode 2 /
2317	/ 4 1, 2, 5 /
2318	/ 5 1, 2, 6 /
2319	/ 6, 7 same as mode 2 /
2320
2321	e1 = CEILING( x1 );
2322	e2 = FLOOR ( x2 );
2323	pxl = e1;
2324
2325	if ( e1 > e2 )
2326	{
2327	Int dropOutControl = left->flags & `7`;
2328
2329
2330	if ( e1 == e2 + ras.precision )
2331	{
2332	switch ( dropOutControl )
2333	{
2334	case `0`: / simple drop-outs including stubs /
2335	pxl = e2;
2336	break;
2337
2338	case `4`: / smart drop-outs including stubs /
2339	pxl = SMART( x1, x2 );
2340	break;
2341
2342	case `1`: / simple drop-outs excluding stubs /
2343	case `5`: / smart drop-outs excluding stubs /
2344
2345	/ Drop-out Control Rules #4 and #6 /
2346
2347	/ The specification neither provides an exact definition /
2348	/ of a `stub' nor gives exact rules to exclude them. /
2349	/ /
2350	/ Here the constraints we use to recognize a stub. /
2351	/ /
2352	/ upper stub: /
2353	/ /
2354	/ - P_Left and P_Right are in the same contour /
2355	/ - P_Right is the successor of P_Left in that contour /
2356	/ - y is the top of P_Left and P_Right /
2357	/ /
2358	/ lower stub: /
2359	/ /
2360	/ - P_Left and P_Right are in the same contour /
2361	/ - P_Left is the successor of P_Right in that contour /
2362	/ - y is the bottom of P_Left /
2363	/ /
2364	/ We draw a stub if the following constraints are met. /
2365	/ /
2366	/ - for an upper or lower stub, there is top or bottom /
2367	/ overshoot, respectively /
2368	/ - the covered interval is greater or equal to a half /
2369	/ pixel /
2370
2371	/ upper stub test /
2372	if ( left->next == right &&
2373	left->height <= `0` &&
2374	!( left->flags & Overshoot_Top &&
2375	x2 - x1 >= ras.precision_half ) )
2376	goto Exit;
2377
2378	/ lower stub test /
2379	if ( right->next == left &&
2380	left->start == y &&
2381	!( left->flags & Overshoot_Bottom &&
2382	x2 - x1 >= ras.precision_half ) )
2383	goto Exit;
2384
2385	if ( dropOutControl == `1` )
2386	pxl = e2;
2387	else
2388	pxl = SMART( x1, x2 );
2389	break;
2390
2391	default: / modes 2, 3, 6, 7 /
2392	goto Exit; / no drop-out control /
2393	}
2394
2395	/ undocumented but confirmed: If the drop-out would result in a /
2396	/ pixel outside of the bounding box, use the pixel inside of the /
2397	/ bounding box instead /
2398	if ( pxl < `0` )
2399	pxl = e1;
2400	else if ( TRUNC( pxl ) >= ras.bWidth )
2401	pxl = e2;
2402
2403	/ check that the other pixel isn't set /
2404	e1 = ( pxl == e1 ) ? e2 : e1;
2405
2406	e1 = TRUNC( e1 );
2407
2408	c1 = (Short)( e1 >> `3` );
2409	f1 = (Short)( e1 & `7` );
2410
2411	if ( e1 >= `0` && e1 < ras.bWidth &&
2412	ras.bLine[c1] & ( `0x80` >> f1 ) )
2413	goto Exit;
2414	}
2415	else
2416	goto Exit;
2417	}
2418
2419	e1 = TRUNC( pxl );
2420
2421	if ( e1 >= `0` && e1 < ras.bWidth )
2422	{
2423	FT_TRACE7(( " -> x=%ld", e1 ));
2424
2425	c1 = (Short)( e1 >> `3` );
2426	f1 = (Short)( e1 & `7` );
2427
2428	ras.bLine[c1] \|= (char)( `0x80` >> f1 );
2429	}
2430
2431	Exit:
2432	FT_TRACE7(( " dropout=%d\n", left->flags & `7` ));
2433	}
2434
2435
2436	static void
2437	Vertical_Sweep_Step( RAS_ARG )
2438	{
2439	ras.bLine -= ras.target.pitch;
2440	}
2441
2442
2443	/************************************************************************
2444	*
2445	* Horizontal Sweep Procedure Set
2446	*
2447	* These four routines are used during the horizontal black/white
2448	* sweep phase by the generic Draw_Sweep() function.
2449	*
2450	*/
2451
2452	static void
2453	Horizontal_Sweep_Init( RAS_ARGS Short min,
2454	Short max )
2455	{
2456	/ nothing, really /
2457	FT_UNUSED_RASTER;
2458	FT_UNUSED( min );
2459	FT_UNUSED( max );
2460	}
2461
2462
2463	static void
2464	Horizontal_Sweep_Span( RAS_ARGS Short y,
2465	FT_F26Dot6 x1,
2466	FT_F26Dot6 x2,
2467	PProfile left,
2468	PProfile right )
2469	{
2470	Long e1, e2;
2471
2472	FT_UNUSED( left );
2473	FT_UNUSED( right );
2474
2475
2476	FT_TRACE7(( " x=%d y=[% .12f;% .12f]",
2477	y,
2478	(double)x1 / (double)ras.precision,
2479	(double)x2 / (double)ras.precision ));
2480
2481	/ We should not need this procedure but the vertical sweep /
2482	/ mishandles horizontal lines through pixel centers. So we /
2483	/ have to check perfectly aligned span edges here. /
2484	/ /
2485	/ XXX: Can we handle horizontal lines better and drop this? /
2486
2487	e1 = CEILING( x1 );
2488
2489	if ( x1 == e1 )
2490	{
2491	e1 = TRUNC( e1 );
2492
2493	if ( e1 >= `0` && (ULong)e1 < ras.target.rows )
2494	{
2495	Byte f1;
2496	PByte bits;
2497
2498
2499	bits = ras.bOrigin + ( y >> `3` ) - e1 * ras.target.pitch;
2500	f1 = (Byte)( `0x80` >> ( y & `7` ) );
2501
2502	FT_TRACE7(( bits[`0`] & f1 ? " redundant"
2503	: " -> y=%ld edge", e1 ));
2504
2505	bits[`0`] \|= f1;
2506	}
2507	}
2508
2509	e2 = FLOOR ( x2 );
2510
2511	if ( x2 == e2 )
2512	{
2513	e2 = TRUNC( e2 );
2514
2515	if ( e2 >= `0` && (ULong)e2 < ras.target.rows )
2516	{
2517	Byte f1;
2518	PByte bits;
2519
2520
2521	bits = ras.bOrigin + ( y >> `3` ) - e2 * ras.target.pitch;
2522	f1 = (Byte)( `0x80` >> ( y & `7` ) );
2523
2524	FT_TRACE7(( bits[`0`] & f1 ? " redundant"
2525	: " -> y=%ld edge", e2 ));
2526
2527	bits[`0`] \|= f1;
2528	}
2529	}
2530
2531	FT_TRACE7(( "\n" ));
2532	}
2533
2534
2535	static void
2536	Horizontal_Sweep_Drop( RAS_ARGS Short y,
2537	FT_F26Dot6 x1,
2538	FT_F26Dot6 x2,
2539	PProfile left,
2540	PProfile right )
2541	{
2542	Long e1, e2, pxl;
2543	PByte bits;
2544	Byte f1;
2545
2546
2547	FT_TRACE7(( " x=%d y=[% .12f;% .12f]",
2548	y,
2549	(double)x1 / (double)ras.precision,
2550	(double)x2 / (double)ras.precision ));
2551
2552	/ During the horizontal sweep, we only take care of drop-outs /
2553
2554	/ e1 + <-- pixel center /
2555	/ \| /
2556	/ x1 ---+--> <-- contour /
2557	/ \| /
2558	/ \| /
2559	/ x2 <--+--- <-- contour /
2560	/ \| /
2561	/ \| /
2562	/ e2 + <-- pixel center /
2563
2564	e1 = CEILING( x1 );
2565	e2 = FLOOR ( x2 );
2566	pxl = e1;
2567
2568	if ( e1 > e2 )
2569	{
2570	Int dropOutControl = left->flags & `7`;
2571
2572
2573	if ( e1 == e2 + ras.precision )
2574	{
2575	switch ( dropOutControl )
2576	{
2577	case `0`: / simple drop-outs including stubs /
2578	pxl = e2;
2579	break;
2580
2581	case `4`: / smart drop-outs including stubs /
2582	pxl = SMART( x1, x2 );
2583	break;
2584
2585	case `1`: / simple drop-outs excluding stubs /
2586	case `5`: / smart drop-outs excluding stubs /
2587	/ see Vertical_Sweep_Drop for details /
2588
2589	/ rightmost stub test /
2590	if ( left->next == right &&
2591	left->height <= `0` &&
2592	!( left->flags & Overshoot_Top &&
2593	x2 - x1 >= ras.precision_half ) )
2594	goto Exit;
2595
2596	/ leftmost stub test /
2597	if ( right->next == left &&
2598	left->start == y &&
2599	!( left->flags & Overshoot_Bottom &&
2600	x2 - x1 >= ras.precision_half ) )
2601	goto Exit;
2602
2603	if ( dropOutControl == `1` )
2604	pxl = e2;
2605	else
2606	pxl = SMART( x1, x2 );
2607	break;
2608
2609	default: / modes 2, 3, 6, 7 /
2610	goto Exit; / no drop-out control /
2611	}
2612
2613	/ undocumented but confirmed: If the drop-out would result in a /
2614	/ pixel outside of the bounding box, use the pixel inside of the /
2615	/ bounding box instead /
2616	if ( pxl < `0` )
2617	pxl = e1;
2618	else if ( (ULong)( TRUNC( pxl ) ) >= ras.target.rows )
2619	pxl = e2;
2620
2621	/ check that the other pixel isn't set /
2622	e1 = ( pxl == e1 ) ? e2 : e1;
2623
2624	e1 = TRUNC( e1 );
2625
2626	bits = ras.bOrigin + ( y >> `3` ) - e1 * ras.target.pitch;
2627	f1 = (Byte)( `0x80` >> ( y & `7` ) );
2628
2629	if ( e1 >= `0` &&
2630	(ULong)e1 < ras.target.rows &&
2631	*bits & f1 )
2632	goto Exit;
2633	}
2634	else
2635	goto Exit;
2636	}
2637
2638	e1 = TRUNC( pxl );
2639
2640	if ( e1 >= `0` && (ULong)e1 < ras.target.rows )
2641	{
2642	FT_TRACE7(( " -> y=%ld", e1 ));
2643
2644	bits = ras.bOrigin + ( y >> `3` ) - e1 * ras.target.pitch;
2645	f1 = (Byte)( `0x80` >> ( y & `7` ) );
2646
2647	bits[`0`] \|= f1;
2648	}
2649
2650	Exit:
2651	FT_TRACE7(( " dropout=%d\n", left->flags & `7` ));
2652	}
2653
2654
2655	static void
2656	Horizontal_Sweep_Step( RAS_ARG )
2657	{
2658	/ Nothing, really /
2659	FT_UNUSED_RASTER;
2660	}
2661
2662
2663	/**************************************************************************
2664	*
2665	* Generic Sweep Drawing routine
2666	*
2667	*/
2668
2669	static Bool
2670	Draw_Sweep( RAS_ARG )
2671	{
2672	Short y, y_change, y_height;
2673
2674	PProfile P, Q, P_Left, P_Right;
2675
2676	Short min_Y, max_Y, top, bottom, dropouts;
2677
2678	Long x1, x2, xs, e1, e2;
2679
2680	TProfileList waiting;
2681	TProfileList draw_left, draw_right;
2682
2683
2684	/ initialize empty linked lists /
2685
2686	Init_Linked( &waiting );
2687
2688	Init_Linked( &draw_left );
2689	Init_Linked( &draw_right );
2690
2691	/ first, compute min and max Y /
2692
2693	P = ras.fProfile;
2694	max_Y = (Short)TRUNC( ras.minY );
2695	min_Y = (Short)TRUNC( ras.maxY );
2696
2697	while ( P )
2698	{
2699	Q = P->link;
2700
2701	bottom = (Short)P->start;
2702	top = (Short)( P->start + P->height - `1` );
2703
2704	if ( min_Y > bottom )
2705	min_Y = bottom;
2706	if ( max_Y < top )
2707	max_Y = top;
2708
2709	P->X = `0`;
2710	InsNew( &waiting, P );
2711
2712	P = Q;
2713	}
2714
2715	/ check the Y-turns /
2716	if ( ras.numTurns == `0` )
2717	{
2718	ras.error = FT_THROW( Invalid_Outline );
2719	return FAILURE;
2720	}
2721
2722	/ now initialize the sweep /
2723
2724	ras.Proc_Sweep_Init( RAS_VARS min_Y, max_Y );
2725
2726	/ then compute the distance of each profile from min_Y /
2727
2728	P = waiting;
2729
2730	while ( P )
2731	{
2732	P->countL = P->start - min_Y;
2733	P = P->link;
2734	}
2735
2736	/ let's go /
2737
2738	y = min_Y;
2739	y_height = `0`;
2740
2741	if ( ras.numTurns > `0` &&
2742	ras.sizeBuff[-ras.numTurns] == min_Y )
2743	ras.numTurns--;
2744
2745	while ( ras.numTurns > `0` )
2746	{
2747	/ check waiting list for new activations /
2748
2749	P = waiting;
2750
2751	while ( P )
2752	{
2753	Q = P->link;
2754	P->countL -= y_height;
2755	if ( P->countL == `0` )
2756	{
2757	DelOld( &waiting, P );
2758
2759	if ( P->flags & Flow_Up )
2760	InsNew( &draw_left, P );
2761	else
2762	InsNew( &draw_right, P );
2763	}
2764
2765	P = Q;
2766	}
2767
2768	/ sort the drawing lists /
2769
2770	Sort( &draw_left );
2771	Sort( &draw_right );
2772
2773	y_change = (Short)ras.sizeBuff[-ras.numTurns--];
2774	y_height = (Short)( y_change - y );
2775
2776	while ( y < y_change )
2777	{
2778	/ let's trace /
2779
2780	dropouts = `0`;
2781
2782	P_Left = draw_left;
2783	P_Right = draw_right;
2784
2785	while ( P_Left && P_Right )
2786	{
2787	x1 = P_Left ->X;
2788	x2 = P_Right->X;
2789
2790	if ( x1 > x2 )
2791	{
2792	xs = x1;
2793	x1 = x2;
2794	x2 = xs;
2795	}
2796
2797	e1 = FLOOR( x1 );
2798	e2 = CEILING( x2 );
2799
2800	if ( x2 - x1 <= ras.precision &&
2801	e1 != x1 && e2 != x2 )
2802	{
2803	if ( e1 > e2 \|\| e2 == e1 + ras.precision )
2804	{
2805	Int dropOutControl = P_Left->flags & `7`;
2806
2807
2808	if ( dropOutControl != `2` )
2809	{
2810	/ a drop-out was detected /
2811
2812	P_Left ->X = x1;
2813	P_Right->X = x2;
2814
2815	/ mark profile for drop-out processing /
2816	P_Left->countL = `1`;
2817	dropouts++;
2818	}
2819
2820	goto Skip_To_Next;
2821	}
2822	}
2823
2824	ras.Proc_Sweep_Span( RAS_VARS y, x1, x2, P_Left, P_Right );
2825
2826	Skip_To_Next:
2827
2828	P_Left = P_Left->link;
2829	P_Right = P_Right->link;
2830	}
2831
2832	/ handle drop-outs _after_ the span drawing -- /
2833	/ drop-out processing has been moved out of the loop /
2834	/ for performance tuning /
2835	if ( dropouts > `0` )
2836	goto Scan_DropOuts;
2837
2838	Next_Line:
2839
2840	ras.Proc_Sweep_Step( RAS_VAR );
2841
2842	y++;
2843
2844	if ( y < y_change )
2845	{
2846	Sort( &draw_left );
2847	Sort( &draw_right );
2848	}
2849	}
2850
2851	/ now finalize the profiles that need it /
2852
2853	P = draw_left;
2854	while ( P )
2855	{
2856	Q = P->link;
2857	if ( P->height == `0` )
2858	DelOld( &draw_left, P );
2859	P = Q;
2860	}
2861
2862	P = draw_right;
2863	while ( P )
2864	{
2865	Q = P->link;
2866	if ( P->height == `0` )
2867	DelOld( &draw_right, P );
2868	P = Q;
2869	}
2870	}
2871
2872	/ for gray-scaling, flush the bitmap scanline cache /
2873	while ( y <= max_Y )
2874	{
2875	ras.Proc_Sweep_Step( RAS_VAR );
2876	y++;
2877	}
2878
2879	return SUCCESS;
2880
2881	Scan_DropOuts:
2882
2883	P_Left = draw_left;
2884	P_Right = draw_right;
2885
2886	while ( P_Left && P_Right )
2887	{
2888	if ( P_Left->countL )
2889	{
2890	P_Left->countL = `0`;
2891	#if 0
2892	dropouts--; / -- this is useful when debugging only /
2893	#endif
2894	ras.Proc_Sweep_Drop( RAS_VARS y,
2895	P_Left->X,
2896	P_Right->X,
2897	P_Left,
2898	P_Right );
2899	}
2900
2901	P_Left = P_Left->link;
2902	P_Right = P_Right->link;
2903	}
2904
2905	goto Next_Line;
2906	}
2907
2908
2909	#ifdef STANDALONE_
2910
2911	/**************************************************************************
2912	*
2913	* The following functions should only compile in stand-alone mode,
2914	* i.e., when building this component without the rest of FreeType.
2915	*
2916	*/
2917
2918	/**************************************************************************
2919	*
2920	* @Function:
2921	* FT_Outline_Get_CBox
2922	*
2923	* @Description:
2924	* Return an outline's `control box'. The control box encloses all
2925	* the outline's points, including Bézier control points. Though it
2926	* coincides with the exact bounding box for most glyphs, it can be
2927	* slightly larger in some situations (like when rotating an outline
2928	* that contains Bézier outside arcs).
2929	*
2930	* Computing the control box is very fast, while getting the bounding
2931	* box can take much more time as it needs to walk over all segments
2932	* and arcs in the outline. To get the latter, you can use the
2933	* `ftbbox' component, which is dedicated to this single task.
2934	*
2935	* @Input:
2936	* outline ::
2937	* A pointer to the source outline descriptor.
2938	*
2939	* @Output:
2940	* acbox ::
2941	* The outline's control box.
2942	*
2943	* @Note:
2944	* See @FT_Glyph_Get_CBox for a discussion of tricky fonts.
2945	*/
2946
2947	static void
2948	FT_Outline_Get_CBox( const FT_Outline* outline,
2949	FT_BBox *acbox )
2950	{
2951	if ( outline && acbox )
2952	{
2953	Long xMin, yMin, xMax, yMax;
2954
2955
2956	if ( outline->n_points == `0` )
2957	{
2958	xMin = `0`;
2959	yMin = `0`;
2960	xMax = `0`;
2961	yMax = `0`;
2962	}
2963	else
2964	{
2965	FT_Vector* vec = outline->points;
2966	FT_Vector* limit = vec + outline->n_points;
2967
2968
2969	xMin = xMax = vec->x;
2970	yMin = yMax = vec->y;
2971	vec++;
2972
2973	for ( ; vec < limit; vec++ )
2974	{
2975	Long x, y;
2976
2977
2978	x = vec->x;
2979	if ( x < xMin ) xMin = x;
2980	if ( x > xMax ) xMax = x;
2981
2982	y = vec->y;
2983	if ( y < yMin ) yMin = y;
2984	if ( y > yMax ) yMax = y;
2985	}
2986	}
2987	acbox->xMin = xMin;
2988	acbox->xMax = xMax;
2989	acbox->yMin = yMin;
2990	acbox->yMax = yMax;
2991	}
2992	}
2993
2994	#endif /* STANDALONE_ */
2995
2996
2997	/**************************************************************************
2998	*
2999	* @Function:
3000	* Render_Single_Pass
3001	*
3002	* @Description:
3003	* Perform one sweep with sub-banding.
3004	*
3005	* @Input:
3006	* flipped ::
3007	* If set, flip the direction of the outline.
3008	*
3009	* @Return:
3010	* Renderer error code.
3011	*/
3012	static int
3013	Render_Single_Pass( RAS_ARGS Bool flipped,
3014	Int y_min,
3015	Int y_max )
3016	{
3017	Int y_mid;
3018	Int band_top = `0`;
3019	Int band_stack[`32`]; / enough to bisect 32-bit int bands /
3020
3021
3022	while ( `1` )
3023	{
3024	ras.minY = (Long)y_min * ras.precision;
3025	ras.maxY = (Long)y_max * ras.precision;
3026
3027	ras.top = ras.buff;
3028
3029	ras.error = Raster_Err_Ok;
3030
3031	if ( Convert_Glyph( RAS_VARS flipped ) )
3032	{
3033	if ( ras.error != Raster_Err_Raster_Overflow )
3034	return ras.error;
3035
3036	/ sub-banding /
3037
3038	if ( y_min == y_max )
3039	return ras.error; / still Raster_Overflow /
3040
3041	y_mid = ( y_min + y_max ) >> `1`;
3042
3043	band_stack[band_top++] = y_min;
3044	y_min = y_mid + `1`;
3045	}
3046	else
3047	{
3048	if ( ras.fProfile )
3049	if ( Draw_Sweep( RAS_VAR ) )
3050	return ras.error;
3051
3052	if ( --band_top < `0` )
3053	break;
3054
3055	y_max = y_min - `1`;
3056	y_min = band_stack[band_top];
3057	}
3058	}
3059
3060	return Raster_Err_Ok;
3061	}
3062
3063
3064	/**************************************************************************
3065	*
3066	* @Function:
3067	* Render_Glyph
3068	*
3069	* @Description:
3070	* Render a glyph in a bitmap. Sub-banding if needed.
3071	*
3072	* @Return:
3073	* FreeType error code. 0 means success.
3074	*/
3075	static FT_Error
3076	Render_Glyph( RAS_ARG )
3077	{
3078	FT_Error error;
3079
3080
3081	Set_High_Precision( RAS_VARS ras.outline.flags &
3082	FT_OUTLINE_HIGH_PRECISION );
3083
3084	if ( ras.outline.flags & FT_OUTLINE_IGNORE_DROPOUTS )
3085	ras.dropOutControl = `2`;
3086	else
3087	{
3088	if ( ras.outline.flags & FT_OUTLINE_SMART_DROPOUTS )
3089	ras.dropOutControl = `4`;
3090	else
3091	ras.dropOutControl = `0`;
3092
3093	if ( !( ras.outline.flags & FT_OUTLINE_INCLUDE_STUBS ) )
3094	ras.dropOutControl += `1`;
3095	}
3096
3097	/ Vertical Sweep /
3098	FT_TRACE7(( "Vertical pass (ftraster)\n" ));
3099
3100	ras.Proc_Sweep_Init = Vertical_Sweep_Init;
3101	ras.Proc_Sweep_Span = Vertical_Sweep_Span;
3102	ras.Proc_Sweep_Drop = Vertical_Sweep_Drop;
3103	ras.Proc_Sweep_Step = Vertical_Sweep_Step;
3104
3105	ras.bWidth = (UShort)ras.target.width;
3106	ras.bOrigin = (Byte*)ras.target.buffer;
3107
3108	if ( ras.target.pitch > `0` )
3109	ras.bOrigin += (Long)( ras.target.rows - `1` ) * ras.target.pitch;
3110
3111	error = Render_Single_Pass( RAS_VARS `0`, `0`, (Int)ras.target.rows - `1` );
3112	if ( error )
3113	return error;
3114
3115	/ Horizontal Sweep /
3116	if ( !( ras.outline.flags & FT_OUTLINE_SINGLE_PASS ) )
3117	{
3118	FT_TRACE7(( "Horizontal pass (ftraster)\n" ));
3119
3120	ras.Proc_Sweep_Init = Horizontal_Sweep_Init;
3121	ras.Proc_Sweep_Span = Horizontal_Sweep_Span;
3122	ras.Proc_Sweep_Drop = Horizontal_Sweep_Drop;
3123	ras.Proc_Sweep_Step = Horizontal_Sweep_Step;
3124
3125	error = Render_Single_Pass( RAS_VARS `1`, `0`, (Int)ras.target.width - `1` );
3126	if ( error )
3127	return error;
3128	}
3129
3130	return Raster_Err_Ok;
3131	}
3132
3133
3134	/* RASTER OBJECT CREATION: In standalone mode, we simply use **/
3135	/* a static object. **/
3136
3137
3138	#ifdef STANDALONE_
3139
3140
3141	static int
3142	ft_black_new( void* memory,
3143	FT_Raster *araster )
3144	{
3145	static black_TRaster the_raster;
3146	FT_UNUSED( memory );
3147
3148
3149	*araster = (FT_Raster)&the_raster;
3150	FT_ZERO( &the_raster );
3151
3152	return `0`;
3153	}
3154
3155
3156	static void
3157	ft_black_done( FT_Raster raster )
3158	{
3159	/ nothing /
3160	FT_UNUSED( raster );
3161	}
3162
3163
3164	#else /* !STANDALONE_ */
3165
3166
3167	static int
3168	ft_black_new( void* memory_, / FT_Memory /
3169	FT_Raster araster_ ) /* black_PRaster /
3170	{
3171	FT_Memory memory = (FT_Memory)memory_;
3172	black_PRaster araster = (black_PRaster)araster_;
3173
3174	FT_Error error;
3175	black_PRaster raster = NULL;
3176
3177
3178	if ( !FT_NEW( raster ) )
3179	raster->memory = memory;
3180
3181	*araster = raster;
3182
3183	return error;
3184	}
3185
3186
3187	static void
3188	ft_black_done( FT_Raster raster_ ) / black_PRaster /
3189	{
3190	black_PRaster raster = (black_PRaster)raster_;
3191	FT_Memory memory = (FT_Memory)raster->memory;
3192
3193
3194	FT_FREE( raster );
3195	}
3196
3197
3198	#endif /* !STANDALONE_ */
3199
3200
3201	static void
3202	ft_black_reset( FT_Raster raster,
3203	PByte pool_base,
3204	ULong pool_size )
3205	{
3206	FT_UNUSED( raster );
3207	FT_UNUSED( pool_base );
3208	FT_UNUSED( pool_size );
3209	}
3210
3211
3212	static int
3213	ft_black_set_mode( FT_Raster raster,
3214	ULong mode,
3215	void* args )
3216	{
3217	FT_UNUSED( raster );
3218	FT_UNUSED( mode );
3219	FT_UNUSED( args );
3220
3221	return `0`;
3222	}
3223
3224
3225	static int
3226	ft_black_render( FT_Raster raster,
3227	const FT_Raster_Params* params )
3228	{
3229	const FT_Outline* outline = (const FT_Outline*)params->source;
3230	const FT_Bitmap* target_map = params->target;
3231
3232	#ifndef FT_STATIC_RASTER
3233	black_TWorker worker[`1`];
3234	#endif
3235
3236	Long buffer[FT_MAX_BLACK_POOL];
3237
3238
3239	if ( !raster )
3240	return FT_THROW( Raster_Uninitialized );
3241
3242	if ( !outline )
3243	return FT_THROW( Invalid_Outline );
3244
3245	/ return immediately if the outline is empty /
3246	if ( outline->n_points == `0` \|\| outline->n_contours <= `0` )
3247	return Raster_Err_Ok;
3248
3249	if ( !outline->contours \|\| !outline->points )
3250	return FT_THROW( Invalid_Outline );
3251
3252	if ( outline->n_points !=
3253	outline->contours[outline->n_contours - `1`] + `1` )
3254	return FT_THROW( Invalid_Outline );
3255
3256	/ this version of the raster does not support direct rendering, sorry /
3257	if ( params->flags & FT_RASTER_FLAG_DIRECT \|\|
3258	params->flags & FT_RASTER_FLAG_AA )
3259	return FT_THROW( Cannot_Render_Glyph );
3260
3261	if ( !target_map )
3262	return FT_THROW( Invalid_Argument );
3263
3264	/ nothing to do /
3265	if ( !target_map->width \|\| !target_map->rows )
3266	return Raster_Err_Ok;
3267
3268	if ( !target_map->buffer )
3269	return FT_THROW( Invalid_Argument );
3270
3271	ras.outline = *outline;
3272	ras.target = *target_map;
3273
3274	ras.buff = buffer;
3275	ras.sizeBuff = (&buffer)[`1`]; / Points to right after buffer. /
3276
3277	return Render_Glyph( RAS_VAR );
3278	}
3279
3280
3281	FT_DEFINE_RASTER_FUNCS(
3282	ft_standard_raster,
3283
3284	FT_GLYPH_FORMAT_OUTLINE,
3285
3286	ft_black_new, / FT_Raster_New_Func raster_new /
3287	ft_black_reset, / FT_Raster_Reset_Func raster_reset /
3288	ft_black_set_mode, / FT_Raster_Set_Mode_Func raster_set_mode /
3289	ft_black_render, / FT_Raster_Render_Func raster_render /
3290	ft_black_done / FT_Raster_Done_Func raster_done /
3291	)
3292
3293
3294	/ END /
3295

Browse the source code of Godot/thirdparty/freetype/src/raster/ftraster.c