1	// Copyright (C) 2016 The Qt Company Ltd.
2	// Copyright (C) 2000-2016 by David Turner, Robert Wilhelm, and Werner Lemberg.
3	// SPDX-License-Identifier: FTL OR GPL-2.0-only
4
5	/***************************************************************************/
6	/* */
7	/* qgrayraster.c, derived from ftgrays.c */
8	/* */
9	/* A new `perfect' anti-aliasing renderer (body). */
10	/* */
11	/* Copyright 2000-2016 by */
12	/* David Turner, Robert Wilhelm, and Werner Lemberg. */
13	/* */
14	/* This file is part of the FreeType project, and may only be used, */
15	/* modified, and distributed under the terms of the FreeType project */
16	/* license, ../../3rdparty/freetype/docs/FTL.TXT. By continuing to use, */
17	/* modify, or distribute this file you indicate that you have read */
18	/* the license and understand and accept it fully. */
19	/* */
20	/***************************************************************************/
21
22	/*************************************************************************/
23	/* */
24	/* This file can be compiled without the rest of the FreeType engine, by */
25	/* defining the _STANDALONE_ macro when compiling it. You also need to */
26	/* put the files `ftgrays.h' and `ftimage.h' into the current */
27	/* compilation directory. Typically, you could do something like */
28	/* */
29	/* - copy `src/smooth/ftgrays.c' (this file) to your current directory */
30	/* */
31	/* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */
32	/* same directory */
33	/* */
34	/* - compile `ftgrays' with the _STANDALONE_ macro defined, as in */
35	/* */
36	/* cc -c -D_STANDALONE_ ftgrays.c */
37	/* */
38	/* The renderer can be initialized with a call to */
39	/* `qt_ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated */
40	/* with a call to `qt_ft_gray_raster.raster_render'. */
41	/* */
42	/* See the comments and documentation in the file `ftimage.h' for more */
43	/* details on how the raster works. */
44	/* */
45	/*************************************************************************/
46
47	/*************************************************************************/
48	/* */
49	/* This is a new anti-aliasing scan-converter for FreeType 2. The */
50	/* algorithm used here is _very_ different from the one in the standard */
51	/* `ftraster' module. Actually, `ftgrays' computes the _exact_ */
52	/* coverage of the outline on each pixel cell. */
53	/* */
54	/* It is based on ideas that I initially found in Raph Levien's */
55	/* excellent LibArt graphics library (see http://www.levien.com/libart */
56	/* for more information, though the web pages do not tell anything */
57	/* about the renderer; you'll have to dive into the source code to */
58	/* understand how it works). */
59	/* */
60	/* Note, however, that this is a _very_ different implementation */
61	/* compared to Raph's. Coverage information is stored in a very */
62	/* different way, and I don't use sorted vector paths. Also, it doesn't */
63	/* use floating point values. */
64	/* */
65	/* This renderer has the following advantages: */
66	/* */
67	/* - It doesn't need an intermediate bitmap. Instead, one can supply a */
68	/* callback function that will be called by the renderer to draw gray */
69	/* spans on any target surface. You can thus do direct composition on */
70	/* any kind of bitmap, provided that you give the renderer the right */
71	/* callback. */
72	/* */
73	/* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on */
74	/* each pixel cell. */
75	/* */
76	/* - It performs a single pass on the outline (the `standard' FT2 */
77	/* renderer makes two passes). */
78	/* */
79	/* - It can easily be modified to render to _any_ number of gray levels */
80	/* cheaply. */
81	/* */
82	/* - For small (< 20) pixel sizes, it is faster than the standard */
83	/* renderer. */
84	/* */
85	/*************************************************************************/
86
87	/*************************************************************************/
88	/* */
89	/* The macro QT_FT_COMPONENT is used in trace mode. It is an implicit */
90	/* parameter of the QT_FT_TRACE() and QT_FT_ERROR() macros, used to print/log */
91	/* messages during execution. */
92	/* */
93	#undef QT_FT_COMPONENT
94	#define QT_FT_COMPONENT trace_smooth
95
96
97	/* Auxiliary macros for token concatenation. */
98	#define QT_FT_ERR_XCAT( x, y ) x ## y
99	#define QT_FT_ERR_CAT( x, y ) QT_FT_ERR_XCAT( x, y )
100
101	#define QT_FT_BEGIN_STMNT do {
102	#define QT_FT_END_STMNT } while ( 0 )
103
104	#define QT_FT_MAX( a, b ) ( (a) > (b) ? (a) : (b) )
105	#define QT_FT_ABS( a ) ( (a) < 0 ? -(a) : (a) )
106
107
108	/*
109	* Approximate sqrt(x*x+y*y) using the `alpha max plus beta min'
110	* algorithm. We use alpha = 1, beta = 3/8, giving us results with a
111	* largest error less than 7% compared to the exact value.
112	*/
113	#define QT_FT_HYPOT( x, y ) \
114	( x = QT_FT_ABS( x ), \
115	y = QT_FT_ABS( y ), \
116	x > y ? x + ( 3 * y >> 3 ) \
117	: y + ( 3 * x >> 3 ) )
118
119	#define ErrRaster_MemoryOverflow -4
120
121	#if defined(VXWORKS)
122	# include <vxWorksCommon.h> /* needed for setjmp.h */
123	#endif
124	#include <string.h> /* for qt_ft_memcpy() */
125	#include <setjmp.h>
126	#include <limits.h>
127
128	#define QT_FT_UINT_MAX UINT_MAX
129
130	#define qt_ft_memset memset
131
132	#define qt_ft_setjmp setjmp
133	#define qt_ft_longjmp longjmp
134	#define qt_ft_jmp_buf jmp_buf
135
136	#include <stddef.h>
137	typedef ptrdiff_t QT_FT_PtrDist;
138
139	#define ErrRaster_Invalid_Mode -2
140	#define ErrRaster_Invalid_Outline -1
141	#define ErrRaster_Invalid_Argument -3
142	#define ErrRaster_Memory_Overflow -4
143	#define ErrRaster_OutOfMemory -6
144
145	#define QT_FT_BEGIN_HEADER
146	#define QT_FT_END_HEADER
147
148	#include <private/qrasterdefs_p.h>
149	#include <private/qgrayraster_p.h>
150
151	#include <qcompilerdetection.h>
152
153	#include <stdlib.h>
154	#include <stdio.h>
155	#include <assert.h>
156
157	#define QT_FT_UNUSED( x ) (void) x
158
159	#define QT_FT_TRACE5( x ) do { } while ( 0 ) /* nothing */
160	#define QT_FT_TRACE7( x ) do { } while ( 0 ) /* nothing */
161	#define QT_FT_ERROR( x ) do { } while ( 0 ) /* nothing */
162	#define QT_FT_THROW( e ) QT_FT_ERR_CAT( ErrRaster_, e )
163
164	#ifndef QT_FT_MEM_SET
165	#define QT_FT_MEM_SET( d, s, c ) qt_ft_memset( d, s, c )
166	#endif
167
168	#ifndef QT_FT_MEM_ZERO
169	#define QT_FT_MEM_ZERO( dest, count ) QT_FT_MEM_SET( dest, 0, count )
170	#endif
171
172
173	#define RAS_ARG PWorker worker
174	#define RAS_ARG_ PWorker worker,
175
176	#define RAS_VAR worker
177	#define RAS_VAR_ worker,
178
179	#define ras (*worker)
180
181	/* must be at least 6 bits! */
182	#define PIXEL_BITS 8
183
184	#define ONE_PIXEL ( 1L << PIXEL_BITS )
185	#define TRUNC( x ) (TCoord)( (x) >> PIXEL_BITS )
186	#define FRACT( x ) (TCoord)( (x) & ( ONE_PIXEL - 1 ) )
187
188	#if PIXEL_BITS >= 6
189	#define UPSCALE( x ) ( (x) * ( ONE_PIXEL >> 6 ) )
190	#define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) )
191	#else
192	#define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) )
193	#define DOWNSCALE( x ) ( (x) * ( 64 >> PIXEL_BITS ) )
194	#endif
195
196	/* Compute `dividend / divisor' and return both its quotient and */
197	/* remainder, cast to a specific type. This macro also ensures that */
198	/* the remainder is always positive. */
199	#define QT_FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \
200	QT_FT_BEGIN_STMNT \
201	(quotient) = (type)( (dividend) / (divisor) ); \
202	(remainder) = (type)( (dividend) % (divisor) ); \
203	if ( (remainder) < 0 ) \
204	{ \
205	(quotient)--; \
206	(remainder) += (type)(divisor); \
207	} \
208	QT_FT_END_STMNT
209
210	/* These macros speed up repetitive divisions by replacing them */
211	/* with multiplications and right shifts. */
212	#define QT_FT_UDIVPREP( b ) \
213	long b ## _r = (long)( ULONG_MAX >> PIXEL_BITS ) / ( b )
214	#define QT_FT_UDIV( a, b ) \
215	( ( (unsigned long)( a ) * (unsigned long)( b ## _r ) ) >> \
216	( sizeof( long ) * CHAR_BIT - PIXEL_BITS ) )
217
218
219	/*************************************************************************/
220	/* */
221	/* TYPE DEFINITIONS */
222	/* */
223
224	/* don't change the following types to QT_FT_Int or QT_FT_Pos, since we might */
225	/* need to define them to "float" or "double" when experimenting with */
226	/* new algorithms */
227
228	typedef long TCoord; /* integer scanline/pixel coordinate */
229	typedef long TPos; /* sub-pixel coordinate */
230	typedef long TArea ; /* cell areas, coordinate products */
231
232	/* maximal number of gray spans in a call to the span callback */
233	#define QT_FT_MAX_GRAY_SPANS 256
234
235
236	typedef struct TCell_* PCell;
237
238	typedef struct TCell_
239	{
240	int x;
241	int cover;
242	TArea area;
243	PCell next;
244
245	} TCell;
246
247
248	typedef struct TWorker_
249	{
250	TCoord ex, ey;
251	TPos min_ex, max_ex;
252	TPos min_ey, max_ey;
253	TPos count_ex, count_ey;
254
255	TArea area;
256	int cover;
257	int invalid;
258
259	PCell cells;
260	QT_FT_PtrDist max_cells;
261	QT_FT_PtrDist num_cells;
262
263	TPos x, y;
264
265	QT_FT_Outline outline;
266	QT_FT_Bitmap target;
267	QT_FT_BBox clip_box;
268
269	QT_FT_Span gray_spans[QT_FT_MAX_GRAY_SPANS];
270	int num_gray_spans;
271
272	QT_FT_Raster_Span_Func render_span;
273	void* render_span_data;
274
275	int band_size;
276	int band_shoot;
277
278	qt_ft_jmp_buf jump_buffer;
279
280	void* buffer;
281	long buffer_size;
282
283	PCell* ycells;
284	TPos ycount;
285
286	int skip_spans;
287	} TWorker, *PWorker;
288
289
290	typedef struct TRaster_
291	{
292	void* buffer;
293	long buffer_size;
294	long buffer_allocated_size;
295	int band_size;
296	void* memory;
297	PWorker worker;
298
299	} TRaster, *PRaster;
300
301	int q_gray_rendered_spans(TRaster *raster)
302	{
303	if ( raster && raster->worker )
304	return raster->worker->skip_spans > 0 ? 0 : -raster->worker->skip_spans;
305	return 0;
306	}
307
308	/*************************************************************************/
309	/* */
310	/* Initialize the cells table. */
311	/* */
312	static void
313	gray_init_cells( RAS_ARG_ void* buffer,
314	long byte_size )
315	{
316	ras.buffer = buffer;
317	ras.buffer_size = byte_size;
318
319	ras.ycells = (PCell*) buffer;
320	ras.cells = NULL;
321	ras.max_cells = 0;
322	ras.num_cells = 0;
323	ras.area = 0;
324	ras.cover = 0;
325	ras.invalid = 1;
326	}
327
328
329	/*************************************************************************/
330	/* */
331	/* Compute the outline bounding box. */
332	/* */
333	static void
334	gray_compute_cbox( RAS_ARG )
335	{
336	QT_FT_Outline* outline = &ras.outline;
337	QT_FT_Vector* vec = outline->points;
338	QT_FT_Vector* limit = vec + outline->n_points;
339
340
341	if ( outline->n_points <= 0 )
342	{
343	ras.min_ex = ras.max_ex = 0;
344	ras.min_ey = ras.max_ey = 0;
345	return;
346	}
347
348	ras.min_ex = ras.max_ex = vec->x;
349	ras.min_ey = ras.max_ey = vec->y;
350
351	vec++;
352
353	for ( ; vec < limit; vec++ )
354	{
355	TPos x = vec->x;
356	TPos y = vec->y;
357
358
359	if ( x < ras.min_ex ) ras.min_ex = x;
360	if ( x > ras.max_ex ) ras.max_ex = x;
361	if ( y < ras.min_ey ) ras.min_ey = y;
362	if ( y > ras.max_ey ) ras.max_ey = y;
363	}
364
365	/* truncate the bounding box to integer pixels */
366	ras.min_ex = ras.min_ex >> 6;
367	ras.min_ey = ras.min_ey >> 6;
368	ras.max_ex = ( ras.max_ex + 63 ) >> 6;
369	ras.max_ey = ( ras.max_ey + 63 ) >> 6;
370	}
371
372
373	/*************************************************************************/
374	/* */
375	/* Record the current cell in the table. */
376	/* */
377	static PCell
378	gray_find_cell( RAS_ARG )
379	{
380	PCell *pcell, cell;
381	TPos x = ras.ex;
382
383
384	if ( x > ras.count_ex )
385	x = ras.count_ex;
386
387	pcell = &ras.ycells[ras.ey];
388	for (;;)
389	{
390	cell = *pcell;
391	if ( cell == NULL || cell->x > x )
392	break;
393
394	if ( cell->x == x )
395	goto Exit;
396
397	pcell = &cell->next;
398	}
399
400	if ( ras.num_cells >= ras.max_cells )
401	qt_ft_longjmp( ras.jump_buffer, val: 1 );
402
403	cell = ras.cells + ras.num_cells++;
404	cell->x = x;
405	cell->area = 0;
406	cell->cover = 0;
407
408	cell->next = *pcell;
409	*pcell = cell;
410
411	Exit:
412	return cell;
413	}
414
415
416	static void
417	gray_record_cell( RAS_ARG )
418	{
419	if ( ras.area | ras.cover )
420	{
421	PCell cell = gray_find_cell( RAS_VAR );
422
423
424	cell->area += ras.area;
425	cell->cover += ras.cover;
426	}
427	}
428
429
430	/*************************************************************************/
431	/* */
432	/* Set the current cell to a new position. */
433	/* */
434	static void
435	gray_set_cell( RAS_ARG_ TCoord ex,
436	TCoord ey )
437	{
438	/* Move the cell pointer to a new position. We set the `invalid' */
439	/* flag to indicate that the cell isn't part of those we're interested */
440	/* in during the render phase. This means that: */
441	/* */
442	/* . the new vertical position must be within min_ey..max_ey-1. */
443	/* . the new horizontal position must be strictly less than max_ex */
444	/* */
445	/* Note that if a cell is to the left of the clipping region, it is */
446	/* actually set to the (min_ex-1) horizontal position. */
447
448	/* All cells that are on the left of the clipping region go to the */
449	/* min_ex - 1 horizontal position. */
450	ey -= ras.min_ey;
451
452	if ( ex > ras.max_ex )
453	ex = ras.max_ex;
454
455	ex -= ras.min_ex;
456	if ( ex < 0 )
457	ex = -1;
458
459	/* are we moving to a different cell ? */
460	if ( ex != ras.ex || ey != ras.ey )
461	{
462	/* record the current one if it is valid */
463	if ( !ras.invalid )
464	gray_record_cell( RAS_VAR );
465
466	ras.area = 0;
467	ras.cover = 0;
468	ras.ex = ex;
469	ras.ey = ey;
470	}
471
472	ras.invalid = ( (unsigned int)ey >= (unsigned int)ras.count_ey ||
473	ex >= ras.count_ex );
474	}
475
476
477	/*************************************************************************/
478	/* */
479	/* Start a new contour at a given cell. */
480	/* */
481	static void
482	gray_start_cell( RAS_ARG_ TCoord ex,
483	TCoord ey )
484	{
485	if ( ex > ras.max_ex )
486	ex = (TCoord)( ras.max_ex );
487
488	if ( ex < ras.min_ex )
489	ex = (TCoord)( ras.min_ex - 1 );
490
491	ras.area = 0;
492	ras.cover = 0;
493	ras.ex = ex - ras.min_ex;
494	ras.ey = ey - ras.min_ey;
495	ras.invalid = 0;
496
497	gray_set_cell( RAS_VAR_ ex, ey );
498	}
499
500	// The new render-line implementation is not yet used
501	#if 1
502
503	/*************************************************************************/
504	/* */
505	/* Render a scanline as one or more cells. */
506	/* */
507	static void
508	gray_render_scanline( RAS_ARG_ TCoord ey,
509	TPos x1,
510	TCoord y1,
511	TPos x2,
512	TCoord y2 )
513	{
514	TCoord ex1, ex2, fx1, fx2, first, dy, delta, mod;
515	TPos p, dx;
516	int incr;
517
518
519	ex1 = TRUNC( x1 );
520	ex2 = TRUNC( x2 );
521
522	/* trivial case. Happens often */
523	if ( y1 == y2 )
524	{
525	gray_set_cell( RAS_VAR_ ex: ex2, ey );
526	return;
527	}
528
529	fx1 = FRACT( x1 );
530	fx2 = FRACT( x2 );
531
532	/* everything is located in a single cell. That is easy! */
533	/* */
534	if ( ex1 == ex2 )
535	goto End;
536
537	/* ok, we'll have to render a run of adjacent cells on the same */
538	/* scanline... */
539	/* */
540	dx = x2 - x1;
541	dy = y2 - y1;
542
543	if ( dx > 0 )
544	{
545	p = ( ONE_PIXEL - fx1 ) * dy;
546	first = ONE_PIXEL;
547	incr = 1;
548	} else {
549	p = fx1 * dy;
550	first = 0;
551	incr = -1;
552	dx = -dx;
553	}
554
555	QT_FT_DIV_MOD( TCoord, p, dx, delta, mod );
556
557	ras.area += (TArea)( fx1 + first ) * delta;
558	ras.cover += delta;
559	y1 += delta;
560	ex1 += incr;
561	gray_set_cell( RAS_VAR_ ex: ex1, ey );
562
563	if ( ex1 != ex2 )
564	{
565	TCoord lift, rem;
566
567
568	p = ONE_PIXEL * dy;
569	QT_FT_DIV_MOD( TCoord, p, dx, lift, rem );
570
571	do
572	{
573	delta = lift;
574	mod += rem;
575	if ( mod >= (TCoord)dx )
576	{
577	mod -= (TCoord)dx;
578	delta++;
579	}
580
581	ras.area += (TArea)( ONE_PIXEL * delta );
582	ras.cover += delta;
583	y1 += delta;
584	ex1 += incr;
585	gray_set_cell( RAS_VAR_ ex: ex1, ey );
586	} while ( ex1 != ex2 );
587	}
588	fx1 = ONE_PIXEL - first;
589
590	End:
591	dy = y2 - y1;
592
593	ras.area += (TArea)( ( fx1 + fx2 ) * dy );
594	ras.cover += dy;
595	}
596
597
598	/*************************************************************************/
599	/* */
600	/* Render a given line as a series of scanlines. */
601	/* */
602	static void
603	gray_render_line( RAS_ARG_ TPos to_x,
604	TPos to_y )
605	{
606	TCoord ey1, ey2, fy1, fy2, first, delta, mod;
607	TPos p, dx, dy, x, x2;
608	int incr;
609
610	ey1 = TRUNC( ras.y );
611	ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */
612
613	/* perform vertical clipping */
614	if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) ||
615	( ey1 < ras.min_ey && ey2 < ras.min_ey ) )
616	goto End;
617
618	fy1 = FRACT( ras.y );
619	fy2 = FRACT( to_y );
620
621	/* everything is on a single scanline */
622	if ( ey1 == ey2 )
623	{
624	gray_render_scanline( RAS_VAR_ ey: ey1, ras.x, y1: fy1, x2: to_x, y2: fy2 );
625	goto End;
626	}
627
628	dx = to_x - ras.x;
629	dy = to_y - ras.y;
630
631	/* vertical line - avoid calling gray_render_scanline */
632	if ( dx == 0 )
633	{
634	TCoord ex = TRUNC( ras.x );
635	TCoord two_fx = FRACT( ras.x ) << 1;
636	TPos area, max_ey1;
637
638
639	if ( dy > 0)
640	{
641	first = ONE_PIXEL;
642	}
643	else
644	{
645	first = 0;
646	}
647
648	delta = first - fy1;
649	ras.area += (TArea)two_fx * delta;
650	ras.cover += delta;
651
652	delta = first + first - ONE_PIXEL;
653	area = (TArea)two_fx * delta;
654	max_ey1 = ras.count_ey + ras.min_ey;
655	if (dy < 0) {
656	if (ey1 > max_ey1) {
657	ey1 = (max_ey1 > ey2) ? max_ey1 : ey2;
658	gray_set_cell( worker: &ras, ex, ey: ey1 );
659	} else {
660	ey1--;
661	gray_set_cell( worker: &ras, ex, ey: ey1 );
662	}
663	while ( ey1 > ey2 && ey1 >= ras.min_ey)
664	{
665	ras.area += area;
666	ras.cover += delta;
667	ey1--;
668
669	gray_set_cell( worker: &ras, ex, ey: ey1 );
670	}
671	if (ey1 != ey2) {
672	ey1 = ey2;
673	gray_set_cell( worker: &ras, ex, ey: ey1 );
674	}
675	} else {
676	if (ey1 < ras.min_ey) {
677	ey1 = (ras.min_ey < ey2) ? ras.min_ey : ey2;
678	gray_set_cell( worker: &ras, ex, ey: ey1 );
679	} else {
680	ey1++;
681	gray_set_cell( worker: &ras, ex, ey: ey1 );
682	}
683	while ( ey1 < ey2 && ey1 < max_ey1)
684	{
685	ras.area += area;
686	ras.cover += delta;
687	ey1++;
688
689	gray_set_cell( worker: &ras, ex, ey: ey1 );
690	}
691	if (ey1 != ey2) {
692	ey1 = ey2;
693	gray_set_cell( worker: &ras, ex, ey: ey1 );
694	}
695	}
696
697	delta = (int)( fy2 - ONE_PIXEL + first );
698	ras.area += (TArea)two_fx * delta;
699	ras.cover += delta;
700
701	goto End;
702	}
703
704	/* ok, we have to render several scanlines */
705	if ( dy > 0)
706	{
707	p = ( ONE_PIXEL - fy1 ) * dx;
708	first = ONE_PIXEL;
709	incr = 1;
710	}
711	else
712	{
713	p = fy1 * dx;
714	first = 0;
715	incr = -1;
716	dy = -dy;
717	}
718
719	/* the fractional part of x-delta is mod/dy. It is essential to */
720	/* keep track of its accumulation for accurate rendering. */
721	QT_FT_DIV_MOD( TCoord, p, dy, delta, mod );
722
723	x = ras.x + delta;
724	gray_render_scanline( RAS_VAR_ ey: ey1, ras.x, y1: fy1, x2: x, y2: (TCoord)first );
725
726	ey1 += incr;
727	gray_set_cell( RAS_VAR_ TRUNC( x ), ey: ey1 );
728
729	if ( ey1 != ey2 )
730	{
731	TCoord lift, rem;
732
733
734	p = ONE_PIXEL * dx;
735	QT_FT_DIV_MOD( TCoord, p, dy, lift, rem );
736
737	do
738	{
739	delta = lift;
740	mod += rem;
741	if ( mod >= (TCoord)dy )
742	{
743	mod -= (TCoord)dy;
744	delta++;
745	}
746
747	x2 = x + delta;
748	gray_render_scanline( RAS_VAR_ ey: ey1,
749	x1: x, ONE_PIXEL - first,
750	x2, y2: first );
751	x = x2;
752
753	ey1 += incr;
754	gray_set_cell( RAS_VAR_ TRUNC( x ), ey: ey1 );
755	} while ( ey1 != ey2 );
756	}
757
758	gray_render_scanline( RAS_VAR_ ey: ey1,
759	x1: x, ONE_PIXEL - first,
760	x2: to_x, y2: fy2 );
761
762	End:
763	ras.x = to_x;
764	ras.y = to_y;
765	}
766
767
768	#else
769
770	/*************************************************************************/
771	/* */
772	/* Render a straight line across multiple cells in any direction. */
773	/* */
774	static void
775	gray_render_line( RAS_ARG_ TPos to_x,
776	TPos to_y )
777	{
778	TPos dx, dy, fx1, fy1, fx2, fy2;
779	TCoord ex1, ex2, ey1, ey2;
780
781
782	ex1 = TRUNC( ras.x );
783	ex2 = TRUNC( to_x );
784	ey1 = TRUNC( ras.y );
785	ey2 = TRUNC( to_y );
786
787	/* perform vertical clipping */
788	if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) ||
789	( ey1 < ras.min_ey && ey2 < ras.min_ey ) )
790	goto End;
791
792	dx = to_x - ras.x;
793	dy = to_y - ras.y;
794
795	fx1 = FRACT( ras.x );
796	fy1 = FRACT( ras.y );
797
798	if ( ex1 == ex2 && ey1 == ey2 ) /* inside one cell */
799	;
800	else if ( dy == 0 ) /* ex1 != ex2 */ /* any horizontal line */
801	{
802	ex1 = ex2;
803	gray_set_cell( RAS_VAR_ ex1, ey1 );
804	}
805	else if ( dx == 0 )
806	{
807	if ( dy > 0 ) /* vertical line up */
808	do
809	{
810	fy2 = ONE_PIXEL;
811	ras.cover += ( fy2 - fy1 );
812	ras.area += ( fy2 - fy1 ) * fx1 * 2;
813	fy1 = 0;
814	ey1++;
815	gray_set_cell( RAS_VAR_ ex1, ey1 );
816	} while ( ey1 != ey2 );
817	else /* vertical line down */
818	do
819	{
820	fy2 = 0;
821	ras.cover += ( fy2 - fy1 );
822	ras.area += ( fy2 - fy1 ) * fx1 * 2;
823	fy1 = ONE_PIXEL;
824	ey1--;
825	gray_set_cell( RAS_VAR_ ex1, ey1 );
826	} while ( ey1 != ey2 );
827	}
828	else /* any other line */
829	{
830	TArea prod = dx * fy1 - dy * fx1;
831	QT_FT_UDIVPREP( dx );
832	QT_FT_UDIVPREP( dy );
833
834
835	/* The fundamental value `prod' determines which side and the */
836	/* exact coordinate where the line exits current cell. It is */
837	/* also easily updated when moving from one cell to the next. */
838	do
839	{
840	if ( prod <= 0 &&
841	prod - dx * ONE_PIXEL > 0 ) /* left */
842	{
843	fx2 = 0;
844	fy2 = (TPos)QT_FT_UDIV( -prod, -dx );
845	prod -= dy * ONE_PIXEL;
846	ras.cover += ( fy2 - fy1 );
847	ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
848	fx1 = ONE_PIXEL;
849	fy1 = fy2;
850	ex1--;
851	}
852	else if ( prod - dx * ONE_PIXEL <= 0 &&
853	prod - dx * ONE_PIXEL + dy * ONE_PIXEL > 0 ) /* up */
854	{
855	prod -= dx * ONE_PIXEL;
856	fx2 = (TPos)QT_FT_UDIV( -prod, dy );
857	fy2 = ONE_PIXEL;
858	ras.cover += ( fy2 - fy1 );
859	ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
860	fx1 = fx2;
861	fy1 = 0;
862	ey1++;
863	}
864	else if ( prod - dx * ONE_PIXEL + dy * ONE_PIXEL <= 0 &&
865	prod + dy * ONE_PIXEL >= 0 ) /* right */
866	{
867	prod += dy * ONE_PIXEL;
868	fx2 = ONE_PIXEL;
869	fy2 = (TPos)QT_FT_UDIV( prod, dx );
870	ras.cover += ( fy2 - fy1 );
871	ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
872	fx1 = 0;
873	fy1 = fy2;
874	ex1++;
875	}
876	else /* ( prod + dy * ONE_PIXEL < 0 &&
877	prod > 0 ) down */
878	{
879	fx2 = (TPos)QT_FT_UDIV( prod, -dy );
880	fy2 = 0;
881	prod += dx * ONE_PIXEL;
882	ras.cover += ( fy2 - fy1 );
883	ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
884	fx1 = fx2;
885	fy1 = ONE_PIXEL;
886	ey1--;
887	}
888
889	gray_set_cell( RAS_VAR_ ex1, ey1 );
890	} while ( ex1 != ex2 || ey1 != ey2 );
891	}
892
893	fx2 = FRACT( to_x );
894	fy2 = FRACT( to_y );
895
896	ras.cover += ( fy2 - fy1 );
897	ras.area += ( fy2 - fy1 ) * ( fx1 + fx2 );
898
899	End:
900	ras.x = to_x;
901	ras.y = to_y;
902	}
903
904	#endif
905
906	static void
907	gray_split_conic( QT_FT_Vector* base )
908	{
909	TPos a, b;
910
911
912	base[4].x = base[2].x;
913	b = base[1].x;
914	a = base[3].x = ( base[2].x + b ) / 2;
915	b = base[1].x = ( base[0].x + b ) / 2;
916	base[2].x = ( a + b ) / 2;
917
918	base[4].y = base[2].y;
919	b = base[1].y;
920	a = base[3].y = ( base[2].y + b ) / 2;
921	b = base[1].y = ( base[0].y + b ) / 2;
922	base[2].y = ( a + b ) / 2;
923	}
924
925
926	static void
927	gray_render_conic( RAS_ARG_ const QT_FT_Vector* control,
928	const QT_FT_Vector* to )
929	{
930	QT_FT_Vector bez_stack[16 * 2 + 1]; /* enough to accommodate bisections */
931	QT_FT_Vector* arc = bez_stack;
932	TPos dx, dy;
933	int draw, split;
934
935
936	arc[0].x = UPSCALE( to->x );
937	arc[0].y = UPSCALE( to->y );
938	arc[1].x = UPSCALE( control->x );
939	arc[1].y = UPSCALE( control->y );
940	arc[2].x = ras.x;
941	arc[2].y = ras.y;
942
943	/* short-cut the arc that crosses the current band */
944	if ( ( TRUNC( arc[0].y ) >= ras.max_ey &&
945	TRUNC( arc[1].y ) >= ras.max_ey &&
946	TRUNC( arc[2].y ) >= ras.max_ey ) ||
947	( TRUNC( arc[0].y ) < ras.min_ey &&
948	TRUNC( arc[1].y ) < ras.min_ey &&
949	TRUNC( arc[2].y ) < ras.min_ey ) )
950	{
951	ras.x = arc[0].x;
952	ras.y = arc[0].y;
953	return;
954	}
955
956	dx = QT_FT_ABS( arc[2].x + arc[0].x - 2 * arc[1].x );
957	dy = QT_FT_ABS( arc[2].y + arc[0].y - 2 * arc[1].y );
958	if ( dx < dy )
959	dx = dy;
960
961	/* We can calculate the number of necessary bisections because */
962	/* each bisection predictably reduces deviation exactly 4-fold. */
963	/* Even 32-bit deviation would vanish after 16 bisections. */
964	draw = 1;
965	while ( dx > ONE_PIXEL / 4 )
966	{
967	dx >>= 2;
968	draw <<= 1;
969	}
970
971	/* We use decrement counter to count the total number of segments */
972	/* to draw starting from 2^level. Before each draw we split as */
973	/* many times as there are trailing zeros in the counter. */
974	do
975	{
976	split = 1;
977	while ( ( draw & split ) == 0 )
978	{
979	gray_split_conic( base: arc );
980	arc += 2;
981	split <<= 1;
982	}
983
984	gray_render_line( RAS_VAR_ to_x: arc[0].x, to_y: arc[0].y );
985	arc -= 2;
986
987	} while ( --draw );
988	}
989
990
991	static void
992	gray_split_cubic( QT_FT_Vector* base )
993	{
994	TPos a, b, c, d;
995
996
997	base[6].x = base[3].x;
998	c = base[1].x;
999	d = base[2].x;
1000	base[1].x = a = ( base[0].x + c ) / 2;
1001	base[5].x = b = ( base[3].x + d ) / 2;
1002	c = ( c + d ) / 2;
1003	base[2].x = a = ( a + c ) / 2;
1004	base[4].x = b = ( b + c ) / 2;
1005	base[3].x = ( a + b ) / 2;
1006
1007	base[6].y = base[3].y;
1008	c = base[1].y;
1009	d = base[2].y;
1010	base[1].y = a = ( base[0].y + c ) / 2;
1011	base[5].y = b = ( base[3].y + d ) / 2;
1012	c = ( c + d ) / 2;
1013	base[2].y = a = ( a + c ) / 2;
1014	base[4].y = b = ( b + c ) / 2;
1015	base[3].y = ( a + b ) / 2;
1016	}
1017
1018
1019	static void
1020	gray_render_cubic( RAS_ARG_ const QT_FT_Vector* control1,
1021	const QT_FT_Vector* control2,
1022	const QT_FT_Vector* to )
1023	{
1024	QT_FT_Vector bez_stack[16 * 3 + 1]; /* enough to accommodate bisections */
1025	QT_FT_Vector* arc = bez_stack;
1026	TPos dx, dy, dx_, dy_;
1027	TPos dx1, dy1, dx2, dy2;
1028	TPos L, s, s_limit;
1029
1030
1031	arc[0].x = UPSCALE( to->x );
1032	arc[0].y = UPSCALE( to->y );
1033	arc[1].x = UPSCALE( control2->x );
1034	arc[1].y = UPSCALE( control2->y );
1035	arc[2].x = UPSCALE( control1->x );
1036	arc[2].y = UPSCALE( control1->y );
1037	arc[3].x = ras.x;
1038	arc[3].y = ras.y;
1039
1040	/* short-cut the arc that crosses the current band */
1041	if ( ( TRUNC( arc[0].y ) >= ras.max_ey &&
1042	TRUNC( arc[1].y ) >= ras.max_ey &&
1043	TRUNC( arc[2].y ) >= ras.max_ey &&
1044	TRUNC( arc[3].y ) >= ras.max_ey ) ||
1045	( TRUNC( arc[0].y ) < ras.min_ey &&
1046	TRUNC( arc[1].y ) < ras.min_ey &&
1047	TRUNC( arc[2].y ) < ras.min_ey &&
1048	TRUNC( arc[3].y ) < ras.min_ey ) )
1049	{
1050	ras.x = arc[0].x;
1051	ras.y = arc[0].y;
1052	return;
1053	}
1054
1055	for (;;)
1056	{
1057	/* Decide whether to split or draw. See `Rapid Termination */
1058	/* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */
1059	/* F. Hain, at */
1060	/* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */
1061
1062
1063	/* dx and dy are x and y components of the P0-P3 chord vector. */
1064	dx = dx_ = arc[3].x - arc[0].x;
1065	dy = dy_ = arc[3].y - arc[0].y;
1066
1067	L = QT_FT_HYPOT( dx_, dy_ );
1068
1069	/* Avoid possible arithmetic overflow below by splitting. */
1070	if ( L >= (1 << 23) )
1071	goto Split;
1072
1073	/* Max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1). */
1074	s_limit = L * (TPos)( ONE_PIXEL / 6 );
1075
1076	/* s is L * the perpendicular distance from P1 to the line P0-P3. */
1077	dx1 = arc[1].x - arc[0].x;
1078	dy1 = arc[1].y - arc[0].y;
1079	s = QT_FT_ABS( dy * dx1 - dx * dy1 );
1080
1081	if ( s > s_limit )
1082	goto Split;
1083
1084	/* s is L * the perpendicular distance from P2 to the line P0-P3. */
1085	dx2 = arc[2].x - arc[0].x;
1086	dy2 = arc[2].y - arc[0].y;
1087	s = QT_FT_ABS( dy * dx2 - dx * dy2 );
1088
1089	if ( s > s_limit )
1090	goto Split;
1091
1092	/* Split super curvy segments where the off points are so far
1093	from the chord that the angles P0-P1-P3 or P0-P2-P3 become
1094	acute as detected by appropriate dot products. */
1095	if ( dx1 * ( dx1 - dx ) + dy1 * ( dy1 - dy ) > 0 ||
1096	dx2 * ( dx2 - dx ) + dy2 * ( dy2 - dy ) > 0 )
1097	goto Split;
1098
1099	gray_render_line( RAS_VAR_ to_x: arc[0].x, to_y: arc[0].y );
1100
1101	if ( arc == bez_stack )
1102	return;
1103
1104	arc -= 3;
1105	continue;
1106
1107	Split:
1108	gray_split_cubic( base: arc );
1109	arc += 3;
1110	}
1111	}
1112
1113
1114
1115	static int
1116	gray_move_to( const QT_FT_Vector* to,
1117	PWorker worker )
1118	{
1119	TPos x, y;
1120
1121
1122	/* record current cell, if any */
1123	if ( !ras.invalid )
1124	gray_record_cell( worker );
1125
1126	/* start to a new position */
1127	x = UPSCALE( to->x );
1128	y = UPSCALE( to->y );
1129
1130	gray_start_cell( worker, TRUNC( x ), TRUNC( y ) );
1131
1132	ras.x = x;
1133	ras.y = y;
1134	return 0;
1135	}
1136
1137	static void
1138	gray_render_span( int count,
1139	const QT_FT_Span* spans,
1140	PWorker worker )
1141	{
1142	unsigned char* p;
1143	QT_FT_Bitmap* map = &worker->target;
1144
1145	for ( ; count > 0; count--, spans++ )
1146	{
1147	unsigned char coverage = spans->coverage;
1148
1149	/* first of all, compute the scanline offset */
1150	p = (unsigned char*)map->buffer - spans->y * map->pitch;
1151	if ( map->pitch >= 0 )
1152	p += ( map->rows - 1 ) * (unsigned int)map->pitch;
1153
1154
1155	if ( coverage )
1156	{
1157	unsigned char* q = p + spans->x;
1158
1159
1160	/* For small-spans it is faster to do it by ourselves than
1161	* calling `memset'. This is mainly due to the cost of the
1162	* function call.
1163	*/
1164	switch ( spans->len )
1165	{
1166	case 7: *q++ = coverage; Q_FALLTHROUGH();
1167	case 6: *q++ = coverage; Q_FALLTHROUGH();
1168	case 5: *q++ = coverage; Q_FALLTHROUGH();
1169	case 4: *q++ = coverage; Q_FALLTHROUGH();
1170	case 3: *q++ = coverage; Q_FALLTHROUGH();
1171	case 2: *q++ = coverage; Q_FALLTHROUGH();
1172	case 1: *q = coverage; Q_FALLTHROUGH();
1173	case 0: break;
1174	default:
1175	QT_FT_MEM_SET( q, coverage, spans->len );
1176	}
1177	}
1178	}
1179	}
1180
1181
1182	static void
1183	gray_hline( RAS_ARG_ TCoord x,
1184	TCoord y,
1185	TPos area,
1186	int acount )
1187	{
1188	int coverage;
1189
1190
1191	/* compute the coverage line's coverage, depending on the */
1192	/* outline fill rule */
1193	/* */
1194	/* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
1195	/* */
1196	coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) );
1197	/* use range 0..256 */
1198	if ( coverage < 0 )
1199	coverage = -coverage;
1200
1201	if ( ras.outline.flags & QT_FT_OUTLINE_EVEN_ODD_FILL )
1202	{
1203	coverage &= 511;
1204
1205	if ( coverage > 256 )
1206	coverage = 512 - coverage;
1207	else if ( coverage == 256 )
1208	coverage = 255;
1209	}
1210	else
1211	{
1212	/* normal non-zero winding rule */
1213	if ( coverage >= 256 )
1214	coverage = 255;
1215	}
1216
1217	y += (TCoord)ras.min_ey;
1218	x += (TCoord)ras.min_ex;
1219
1220	/* QT_FT_Span.x is an int, so limit our coordinates appropriately */
1221	if ( x >= (1 << 23) )
1222	x = (1 << 23) - 1;
1223
1224	/* QT_FT_Span.y is an int, so limit our coordinates appropriately */
1225	if ( y >= (1 << 23) )
1226	y = (1 << 23) - 1;
1227
1228	if ( coverage )
1229	{
1230	QT_FT_Span* span;
1231	int count;
1232	int skip;
1233
1234
1235	/* see whether we can add this span to the current list */
1236	count = ras.num_gray_spans;
1237	span = ras.gray_spans + count - 1;
1238	if ( count > 0 &&
1239	span->y == y &&
1240	span->x + span->len == x &&
1241	span->coverage == coverage )
1242	{
1243	span->len = span->len + acount;
1244	return;
1245	}
1246
1247	if ( count >= QT_FT_MAX_GRAY_SPANS )
1248	{
1249	if ( ras.render_span && count > ras.skip_spans )
1250	{
1251	skip = ras.skip_spans > 0 ? ras.skip_spans : 0;
1252	ras.render_span( ras.num_gray_spans - skip,
1253	ras.gray_spans + skip,
1254	ras.render_span_data );
1255	}
1256
1257	ras.skip_spans -= ras.num_gray_spans;
1258
1259	/* ras.render_span( span->y, ras.gray_spans, count ); */
1260
1261	#ifdef DEBUG_GRAYS
1262
1263	if ( 1 )
1264	{
1265	int n;
1266
1267
1268	fprintf( stderr, "y=%3d ", y );
1269	span = ras.gray_spans;
1270	for ( n = 0; n < count; n++, span++ )
1271	fprintf( stderr, "[%d..%d]:%02x ",
1272	span->x, span->x + span->len - 1, span->coverage );
1273	fprintf( stderr, "\n" );
1274	}
1275
1276	#endif /* DEBUG_GRAYS */
1277
1278	ras.num_gray_spans = 0;
1279
1280	span = ras.gray_spans;
1281	}
1282	else
1283	span++;
1284
1285	/* add a gray span to the current list */
1286	span->x = x;
1287	span->len = acount;
1288	span->y = y;
1289	span->coverage = (unsigned char)coverage;
1290
1291	ras.num_gray_spans++;
1292	}
1293	}
1294
1295
1296	#ifdef DEBUG_GRAYS
1297
1298	/* to be called while in the debugger */
1299	gray_dump_cells( RAS_ARG )
1300	{
1301	int yindex;
1302
1303
1304	for ( yindex = 0; yindex < ras.ycount; yindex++ )
1305	{
1306	PCell cell;
1307
1308
1309	printf( "%3d:", yindex );
1310
1311	for ( cell = ras.ycells[yindex]; cell != NULL; cell = cell->next )
1312	printf( " (%3d, c:%4d, a:%6d)", cell->x, cell->cover, cell->area );
1313	printf( "\n" );
1314	}
1315	}
1316
1317	#endif /* DEBUG_GRAYS */
1318
1319
1320	static void
1321	gray_sweep( RAS_ARG_ const QT_FT_Bitmap* target )
1322	{
1323	int yindex;
1324
1325	QT_FT_UNUSED( target );
1326
1327
1328	if ( ras.num_cells == 0 )
1329	return;
1330
1331	QT_FT_TRACE7(( "gray_sweep: start\n" ));
1332
1333	for ( yindex = 0; yindex < ras.ycount; yindex++ )
1334	{
1335	PCell cell = ras.ycells[yindex];
1336	TCoord cover = 0;
1337	TCoord x = 0;
1338
1339
1340	for ( ; cell != NULL; cell = cell->next )
1341	{
1342	TArea area;
1343
1344
1345	if ( cell->x > x && cover != 0 )
1346	gray_hline( RAS_VAR_ x, y: yindex, area: cover * ( ONE_PIXEL * 2 ),
1347	acount: cell->x - x );
1348
1349	cover += cell->cover;
1350	area = cover * ( ONE_PIXEL * 2 ) - cell->area;
1351
1352	if ( area != 0 && cell->x >= 0 )
1353	gray_hline( RAS_VAR_ x: cell->x, y: yindex, area, acount: 1 );
1354
1355	x = cell->x + 1;
1356	}
1357
1358	if ( ras.count_ex > x && cover != 0 )
1359	gray_hline( RAS_VAR_ x, y: yindex, area: cover * ( ONE_PIXEL * 2 ),
1360	ras.count_ex - x );
1361	}
1362
1363	QT_FT_TRACE7(( "gray_sweep: end\n" ));
1364	}
1365
1366	/*************************************************************************/
1367	/* */
1368	/* The following function should only compile in stand_alone mode, */
1369	/* i.e., when building this component without the rest of FreeType. */
1370	/* */
1371	/*************************************************************************/
1372
1373	/*************************************************************************/
1374	/* */
1375	/* <Function> */
1376	/* QT_FT_Outline_Decompose */
1377	/* */
1378	/* <Description> */
1379	/* Walks over an outline's structure to decompose it into individual */
1380	/* segments and Bezier arcs. This function is also able to emit */
1381	/* `move to' and `close to' operations to indicate the start and end */
1382	/* of new contours in the outline. */
1383	/* */
1384	/* <Input> */
1385	/* outline :: A pointer to the source target. */
1386	/* */
1387	/* user :: A typeless pointer which is passed to each */
1388	/* emitter during the decomposition. It can be */
1389	/* used to store the state during the */
1390	/* decomposition. */
1391	/* */
1392	/* <Return> */
1393	/* Error code. 0 means success. */
1394	/* */
1395	static
1396	int QT_FT_Outline_Decompose( const QT_FT_Outline* outline,
1397	void* user )
1398	{
1399	#undef SCALED
1400	#define SCALED( x ) (x)
1401
1402	QT_FT_Vector v_last;
1403	QT_FT_Vector v_control;
1404	QT_FT_Vector v_start;
1405
1406	QT_FT_Vector* point;
1407	QT_FT_Vector* limit;
1408	char* tags;
1409
1410	int n; /* index of contour in outline */
1411	int first; /* index of first point in contour */
1412	int error;
1413	char tag; /* current point's state */
1414
1415	if ( !outline )
1416	return ErrRaster_Invalid_Outline;
1417
1418	first = 0;
1419
1420	for ( n = 0; n < outline->n_contours; n++ )
1421	{
1422	int last; /* index of last point in contour */
1423
1424
1425	last = outline->contours[n];
1426	if ( last < 0 )
1427	goto Invalid_Outline;
1428	limit = outline->points + last;
1429
1430	v_start = outline->points[first];
1431	v_start.x = SCALED( v_start.x );
1432	v_start.y = SCALED( v_start.y );
1433
1434	v_last = outline->points[last];
1435	v_last.x = SCALED( v_last.x );
1436	v_last.y = SCALED( v_last.y );
1437
1438	v_control = v_start;
1439
1440	point = outline->points + first;
1441	tags = outline->tags + first;
1442	tag = QT_FT_CURVE_TAG( tags[0] );
1443
1444	/* A contour cannot start with a cubic control point! */
1445	if ( tag == QT_FT_CURVE_TAG_CUBIC )
1446	goto Invalid_Outline;
1447
1448	/* check first point to determine origin */
1449	if ( tag == QT_FT_CURVE_TAG_CONIC )
1450	{
1451	/* first point is conic control. Yes, this happens. */
1452	if ( QT_FT_CURVE_TAG( outline->tags[last] ) == QT_FT_CURVE_TAG_ON )
1453	{
1454	/* start at last point if it is on the curve */
1455	v_start = v_last;
1456	limit--;
1457	}
1458	else
1459	{
1460	/* if both first and last points are conic, */
1461	/* start at their middle and record its position */
1462	/* for closure */
1463	v_start.x = ( v_start.x + v_last.x ) / 2;
1464	v_start.y = ( v_start.y + v_last.y ) / 2;
1465
1466	v_last = v_start;
1467	}
1468	point--;
1469	tags--;
1470	}
1471
1472	QT_FT_TRACE5(( " move to (%.2f, %.2f)\n",
1473	v_start.x / 64.0, v_start.y / 64.0 ));
1474	error = gray_move_to( to: &v_start, worker: user );
1475	if ( error )
1476	goto Exit;
1477
1478	while ( point < limit )
1479	{
1480	point++;
1481	tags++;
1482
1483	tag = QT_FT_CURVE_TAG( tags[0] );
1484	switch ( tag )
1485	{
1486	case QT_FT_CURVE_TAG_ON: /* emit a single line_to */
1487	{
1488	QT_FT_Vector vec;
1489
1490
1491	vec.x = SCALED( point->x );
1492	vec.y = SCALED( point->y );
1493
1494	QT_FT_TRACE5(( " line to (%.2f, %.2f)\n",
1495	vec.x / 64.0, vec.y / 64.0 ));
1496	gray_render_line(worker: user, UPSCALE(vec.x), UPSCALE(vec.y));
1497	continue;
1498	}
1499
1500	case QT_FT_CURVE_TAG_CONIC: /* consume conic arcs */
1501	{
1502	v_control.x = SCALED( point->x );
1503	v_control.y = SCALED( point->y );
1504
1505	Do_Conic:
1506	if ( point < limit )
1507	{
1508	QT_FT_Vector vec;
1509	QT_FT_Vector v_middle;
1510
1511
1512	point++;
1513	tags++;
1514	tag = QT_FT_CURVE_TAG( tags[0] );
1515
1516	vec.x = SCALED( point->x );
1517	vec.y = SCALED( point->y );
1518
1519	if ( tag == QT_FT_CURVE_TAG_ON )
1520	{
1521	QT_FT_TRACE5(( " conic to (%.2f, %.2f)"
1522	" with control (%.2f, %.2f)\n",
1523	vec.x / 64.0, vec.y / 64.0,
1524	v_control.x / 64.0, v_control.y / 64.0 ));
1525	gray_render_conic(worker: user, control: &v_control, to: &vec);
1526	continue;
1527	}
1528
1529	if ( tag != QT_FT_CURVE_TAG_CONIC )
1530	goto Invalid_Outline;
1531
1532	v_middle.x = ( v_control.x + vec.x ) / 2;
1533	v_middle.y = ( v_control.y + vec.y ) / 2;
1534
1535	QT_FT_TRACE5(( " conic to (%.2f, %.2f)"
1536	" with control (%.2f, %.2f)\n",
1537	v_middle.x / 64.0, v_middle.y / 64.0,
1538	v_control.x / 64.0, v_control.y / 64.0 ));
1539	gray_render_conic(worker: user, control: &v_control, to: &v_middle);
1540
1541	v_control = vec;
1542	goto Do_Conic;
1543	}
1544
1545	QT_FT_TRACE5(( " conic to (%.2f, %.2f)"
1546	" with control (%.2f, %.2f)\n",
1547	v_start.x / 64.0, v_start.y / 64.0,
1548	v_control.x / 64.0, v_control.y / 64.0 ));
1549	gray_render_conic(worker: user, control: &v_control, to: &v_start);
1550	goto Close;
1551	}
1552
1553	default: /* QT_FT_CURVE_TAG_CUBIC */
1554	{
1555	QT_FT_Vector vec1, vec2;
1556
1557
1558	if ( point + 1 > limit ||
1559	QT_FT_CURVE_TAG( tags[1] ) != QT_FT_CURVE_TAG_CUBIC )
1560	goto Invalid_Outline;
1561
1562	point += 2;
1563	tags += 2;
1564
1565	vec1.x = SCALED( point[-2].x );
1566	vec1.y = SCALED( point[-2].y );
1567
1568	vec2.x = SCALED( point[-1].x );
1569	vec2.y = SCALED( point[-1].y );
1570
1571	if ( point <= limit )
1572	{
1573	QT_FT_Vector vec;
1574
1575
1576	vec.x = SCALED( point->x );
1577	vec.y = SCALED( point->y );
1578
1579	QT_FT_TRACE5(( " cubic to (%.2f, %.2f)"
1580	" with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
1581	vec.x / 64.0, vec.y / 64.0,
1582	vec1.x / 64.0, vec1.y / 64.0,
1583	vec2.x / 64.0, vec2.y / 64.0 ));
1584	gray_render_cubic(worker: user, control1: &vec1, control2: &vec2, to: &vec);
1585	continue;
1586	}
1587
1588	QT_FT_TRACE5(( " cubic to (%.2f, %.2f)"
1589	" with controls (%.2f, %.2f) and (%.2f, %.2f)\n",
1590	v_start.x / 64.0, v_start.y / 64.0,
1591	vec1.x / 64.0, vec1.y / 64.0,
1592	vec2.x / 64.0, vec2.y / 64.0 ));
1593	gray_render_cubic(worker: user, control1: &vec1, control2: &vec2, to: &v_start);
1594	goto Close;
1595	}
1596	}
1597	}
1598
1599	/* close the contour with a line segment */
1600	QT_FT_TRACE5(( " line to (%.2f, %.2f)\n",
1601	v_start.x / 64.0, v_start.y / 64.0 ));
1602	gray_render_line(worker: user, UPSCALE(v_start.x), UPSCALE(v_start.y));
1603
1604	Close:
1605	first = last + 1;
1606	}
1607
1608	QT_FT_TRACE5(( "FT_Outline_Decompose: Done\n", n ));
1609	return 0;
1610
1611	Exit:
1612	QT_FT_TRACE5(( "FT_Outline_Decompose: Error %d\n", error ));
1613	return error;
1614
1615	Invalid_Outline:
1616	return ErrRaster_Invalid_Outline;
1617	}
1618
1619	typedef struct TBand_
1620	{
1621	TPos min, max;
1622
1623	} TBand;
1624
1625	static int
1626	gray_convert_glyph_inner( RAS_ARG )
1627	{
1628	volatile int error = 0;
1629
1630	if ( qt_ft_setjmp( ras.jump_buffer ) == 0 )
1631	{
1632	error = QT_FT_Outline_Decompose( outline: &ras.outline, user: &ras );
1633	if ( !ras.invalid )
1634	gray_record_cell( RAS_VAR );
1635	}
1636	else
1637	{
1638	error = ErrRaster_Memory_Overflow;
1639	}
1640
1641	return error;
1642	}
1643
1644
1645	static int
1646	gray_convert_glyph( RAS_ARG )
1647	{
1648	TBand bands[40];
1649	TBand* volatile band;
1650	int volatile n, num_bands;
1651	TPos volatile min, max, max_y;
1652	QT_FT_BBox* clip;
1653	int skip;
1654
1655	ras.num_gray_spans = 0;
1656
1657	/* Set up state in the raster object */
1658	gray_compute_cbox( RAS_VAR );
1659
1660	/* clip to target bitmap, exit if nothing to do */
1661	clip = &ras.clip_box;
1662
1663	if ( ras.max_ex <= clip->xMin || ras.min_ex >= clip->xMax ||
1664	ras.max_ey <= clip->yMin || ras.min_ey >= clip->yMax )
1665	return 0;
1666
1667	if ( ras.min_ex < clip->xMin ) ras.min_ex = clip->xMin;
1668	if ( ras.min_ey < clip->yMin ) ras.min_ey = clip->yMin;
1669
1670	if ( ras.max_ex > clip->xMax ) ras.max_ex = clip->xMax;
1671	if ( ras.max_ey > clip->yMax ) ras.max_ey = clip->yMax;
1672
1673	ras.count_ex = ras.max_ex - ras.min_ex;
1674	ras.count_ey = ras.max_ey - ras.min_ey;
1675
1676	/* set up vertical bands */
1677	num_bands = (int)( ( ras.max_ey - ras.min_ey ) / ras.band_size );
1678	if ( num_bands == 0 )
1679	num_bands = 1;
1680	if ( num_bands >= 39 )
1681	num_bands = 39;
1682
1683	ras.band_shoot = 0;
1684
1685	min = ras.min_ey;
1686	max_y = ras.max_ey;
1687
1688	for ( n = 0; n < num_bands; n++, min = max )
1689	{
1690	max = min + ras.band_size;
1691	if ( n == num_bands - 1 || max > max_y )
1692	max = max_y;
1693
1694	bands[0].min = min;
1695	bands[0].max = max;
1696	band = bands;
1697
1698	while ( band >= bands )
1699	{
1700	TPos bottom, top, middle;
1701	int error;
1702
1703	{
1704	PCell cells_max;
1705	int yindex;
1706	int cell_start, cell_end, cell_mod;
1707
1708
1709	ras.ycells = (PCell*)ras.buffer;
1710	ras.ycount = band->max - band->min;
1711
1712	cell_start = sizeof ( PCell ) * ras.ycount;
1713	cell_mod = cell_start % sizeof ( TCell );
1714	if ( cell_mod > 0 )
1715	cell_start += sizeof ( TCell ) - cell_mod;
1716
1717	cell_end = ras.buffer_size;
1718	cell_end -= cell_end % sizeof( TCell );
1719
1720	cells_max = (PCell)( (char*)ras.buffer + cell_end );
1721	ras.cells = (PCell)( (char*)ras.buffer + cell_start );
1722	if ( ras.cells >= cells_max )
1723	goto ReduceBands;
1724
1725	ras.max_cells = (int)(cells_max - ras.cells);
1726	if ( ras.max_cells < 2 )
1727	goto ReduceBands;
1728
1729	for ( yindex = 0; yindex < ras.ycount; yindex++ )
1730	ras.ycells[yindex] = NULL;
1731	}
1732
1733	ras.num_cells = 0;
1734	ras.invalid = 1;
1735	ras.min_ey = band->min;
1736	ras.max_ey = band->max;
1737	ras.count_ey = band->max - band->min;
1738
1739	error = gray_convert_glyph_inner( RAS_VAR );
1740
1741	if ( !error )
1742	{
1743	gray_sweep( RAS_VAR_ target: &ras.target );
1744	band--;
1745	continue;
1746	}
1747	else if ( error != ErrRaster_Memory_Overflow )
1748	return 1;
1749
1750	ReduceBands:
1751	/* render pool overflow; we will reduce the render band by half */
1752	bottom = band->min;
1753	top = band->max;
1754	middle = bottom + ( ( top - bottom ) >> 1 );
1755
1756	/* This is too complex for a single scanline; there must */
1757	/* be some problems. */
1758	if ( middle == bottom )
1759	{
1760	#ifdef DEBUG_GRAYS
1761	fprintf( stderr, "Rotten glyph!\n" );
1762	#endif
1763	return ErrRaster_OutOfMemory;
1764	}
1765
1766	if ( bottom-top >= ras.band_size )
1767	ras.band_shoot++;
1768
1769	band[1].min = bottom;
1770	band[1].max = middle;
1771	band[0].min = middle;
1772	band[0].max = top;
1773	band++;
1774	}
1775	}
1776
1777	if ( ras.render_span && ras.num_gray_spans > ras.skip_spans )
1778	{
1779	skip = ras.skip_spans > 0 ? ras.skip_spans : 0;
1780	ras.render_span( ras.num_gray_spans - skip,
1781	ras.gray_spans + skip,
1782	ras.render_span_data );
1783	}
1784
1785	ras.skip_spans -= ras.num_gray_spans;
1786
1787	if ( ras.band_shoot > 8 && ras.band_size > 16 )
1788	ras.band_size = ras.band_size / 2;
1789
1790	return 0;
1791	}
1792
1793
1794	static int
1795	gray_raster_render( QT_FT_Raster raster,
1796	const QT_FT_Raster_Params* params )
1797	{
1798	const QT_FT_Outline* outline = (const QT_FT_Outline*)params->source;
1799	const QT_FT_Bitmap* target_map = params->target;
1800	PWorker worker;
1801
1802
1803	if ( !raster || !raster->buffer || !raster->buffer_size )
1804	return ErrRaster_Invalid_Argument;
1805
1806	/* Should always be non-null, it is set by raster_reset() which is always */
1807	/* called with a non-null pool, and a pool_size >= MINIMUM_POOL_SIZE. */
1808	assert(raster->worker);
1809
1810	raster->worker->skip_spans = params->skip_spans;
1811
1812	/* If raster object and raster buffer are allocated, but */
1813	/* raster size isn't of the minimum size, indicate out of */
1814	/* memory. */
1815	if (raster->buffer_allocated_size < MINIMUM_POOL_SIZE )
1816	return ErrRaster_OutOfMemory;
1817
1818	if ( !outline )
1819	return ErrRaster_Invalid_Outline;
1820
1821	/* return immediately if the outline is empty */
1822	if ( outline->n_points == 0 || outline->n_contours <= 0 )
1823	return 0;
1824
1825	if ( !outline->contours || !outline->points )
1826	return ErrRaster_Invalid_Outline;
1827
1828	if ( outline->n_points !=
1829	outline->contours[outline->n_contours - 1] + 1 )
1830	return ErrRaster_Invalid_Outline;
1831
1832	worker = raster->worker;
1833
1834	/* if direct mode is not set, we must have a target bitmap */
1835	if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 )
1836	{
1837	if ( !target_map )
1838	return ErrRaster_Invalid_Argument;
1839
1840	/* nothing to do */
1841	if ( !target_map->width || !target_map->rows )
1842	return 0;
1843
1844	if ( !target_map->buffer )
1845	return ErrRaster_Invalid_Argument;
1846	}
1847
1848	/* this version does not support monochrome rendering */
1849	if ( !( params->flags & QT_FT_RASTER_FLAG_AA ) )
1850	return ErrRaster_Invalid_Mode;
1851
1852	/* compute clipping box */
1853	if ( ( params->flags & QT_FT_RASTER_FLAG_DIRECT ) == 0 )
1854	{
1855	/* compute clip box from target pixmap */
1856	ras.clip_box.xMin = 0;
1857	ras.clip_box.yMin = 0;
1858	ras.clip_box.xMax = target_map->width;
1859	ras.clip_box.yMax = target_map->rows;
1860	}
1861	else if ( params->flags & QT_FT_RASTER_FLAG_CLIP )
1862	{
1863	ras.clip_box = params->clip_box;
1864	}
1865	else
1866	{
1867	ras.clip_box.xMin = -(1 << 23);
1868	ras.clip_box.yMin = -(1 << 23);
1869	ras.clip_box.xMax = (1 << 23) - 1;
1870	ras.clip_box.yMax = (1 << 23) - 1;
1871	}
1872
1873	gray_init_cells( worker, buffer: raster->buffer, byte_size: raster->buffer_size );
1874
1875	ras.outline = *outline;
1876	ras.num_cells = 0;
1877	ras.invalid = 1;
1878	ras.band_size = raster->band_size;
1879
1880	if ( target_map )
1881	ras.target = *target_map;
1882
1883	ras.render_span = (QT_FT_Raster_Span_Func)gray_render_span;
1884	ras.render_span_data = &ras;
1885
1886	if ( params->flags & QT_FT_RASTER_FLAG_DIRECT )
1887	{
1888	ras.render_span = (QT_FT_Raster_Span_Func)params->gray_spans;
1889	ras.render_span_data = params->user;
1890	}
1891
1892	return gray_convert_glyph( worker );
1893	}
1894
1895
1896	/**** RASTER OBJECT CREATION: In standalone mode, we simply use *****/
1897	/**** a static object. *****/
1898
1899	static int
1900	gray_raster_new( QT_FT_Raster* araster )
1901	{
1902	*araster = malloc(size: sizeof(TRaster));
1903	if (!*araster) {
1904	*araster = 0;
1905	return ErrRaster_Memory_Overflow;
1906	}
1907	QT_FT_MEM_ZERO(*araster, sizeof(TRaster));
1908
1909	return 0;
1910	}
1911
1912
1913	static void
1914	gray_raster_done( QT_FT_Raster raster )
1915	{
1916	free(ptr: raster);
1917	}
1918
1919
1920	static void
1921	gray_raster_reset( QT_FT_Raster raster,
1922	char* pool_base,
1923	long pool_size )
1924	{
1925	PRaster rast = (PRaster)raster;
1926
1927	if ( raster )
1928	{
1929	if ( pool_base && ( pool_size >= MINIMUM_POOL_SIZE ) )
1930	{
1931	PWorker worker = (PWorker)pool_base;
1932
1933
1934	rast->worker = worker;
1935	rast->buffer = pool_base +
1936	( ( sizeof ( TWorker ) + sizeof ( TCell ) - 1 ) &
1937	~( sizeof ( TCell ) - 1 ) );
1938	rast->buffer_size = (long)( ( pool_base + pool_size ) -
1939	(char*)rast->buffer ) &
1940	~( sizeof ( TCell ) - 1 );
1941	rast->band_size = (int)( rast->buffer_size /
1942	( sizeof ( TCell ) * 8 ) );
1943	}
1944	else if ( pool_base)
1945	{ /* Case when there is a raster pool allocated, but it */
1946	/* doesn't have the minimum size (and so memory will be reallocated) */
1947	rast->buffer = pool_base;
1948	rast->worker = NULL;
1949	rast->buffer_size = pool_size;
1950	}
1951	else
1952	{
1953	rast->buffer = NULL;
1954	rast->buffer_size = 0;
1955	rast->worker = NULL;
1956	}
1957	rast->buffer_allocated_size = pool_size;
1958	}
1959	}
1960
1961	const QT_FT_Raster_Funcs qt_ft_grays_raster =
1962	{
1963	QT_FT_GLYPH_FORMAT_OUTLINE,
1964
1965	(QT_FT_Raster_New_Func) gray_raster_new,
1966	(QT_FT_Raster_Reset_Func) gray_raster_reset,
1967	(QT_FT_Raster_Set_Mode_Func)0,
1968	(QT_FT_Raster_Render_Func) gray_raster_render,
1969	(QT_FT_Raster_Done_Func) gray_raster_done
1970	};
1971
1972	/* END */
1973