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