/src/skia/third_party/externals/freetype/src/smooth/ftgrays.c
Line | Count | Source (jump to first uncovered line) |
1 | | /**************************************************************************** |
2 | | * |
3 | | * ftgrays.c |
4 | | * |
5 | | * A new `perfect' anti-aliasing renderer (body). |
6 | | * |
7 | | * Copyright (C) 2000-2021 by |
8 | | * David Turner, Robert Wilhelm, and Werner Lemberg. |
9 | | * |
10 | | * This file is part of the FreeType project, and may only be used, |
11 | | * modified, and distributed under the terms of the FreeType project |
12 | | * license, LICENSE.TXT. By continuing to use, modify, or distribute |
13 | | * this file you indicate that you have read the license and |
14 | | * understand and accept it fully. |
15 | | * |
16 | | */ |
17 | | |
18 | | /************************************************************************** |
19 | | * |
20 | | * This file can be compiled without the rest of the FreeType engine, by |
21 | | * defining the STANDALONE_ macro when compiling it. You also need to |
22 | | * put the files `ftgrays.h' and `ftimage.h' into the current |
23 | | * compilation directory. Typically, you could do something like |
24 | | * |
25 | | * - copy `src/smooth/ftgrays.c' (this file) to your current directory |
26 | | * |
27 | | * - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the |
28 | | * same directory |
29 | | * |
30 | | * - compile `ftgrays' with the STANDALONE_ macro defined, as in |
31 | | * |
32 | | * cc -c -DSTANDALONE_ ftgrays.c |
33 | | * |
34 | | * The renderer can be initialized with a call to |
35 | | * `ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated |
36 | | * with a call to `ft_gray_raster.raster_render'. |
37 | | * |
38 | | * See the comments and documentation in the file `ftimage.h' for more |
39 | | * details on how the raster works. |
40 | | * |
41 | | */ |
42 | | |
43 | | /************************************************************************** |
44 | | * |
45 | | * This is a new anti-aliasing scan-converter for FreeType 2. The |
46 | | * algorithm used here is _very_ different from the one in the standard |
47 | | * `ftraster' module. Actually, `ftgrays' computes the _exact_ |
48 | | * coverage of the outline on each pixel cell by straight segments. |
49 | | * |
50 | | * It is based on ideas that I initially found in Raph Levien's |
51 | | * excellent LibArt graphics library (see https://www.levien.com/libart |
52 | | * for more information, though the web pages do not tell anything |
53 | | * about the renderer; you'll have to dive into the source code to |
54 | | * understand how it works). |
55 | | * |
56 | | * Note, however, that this is a _very_ different implementation |
57 | | * compared to Raph's. Coverage information is stored in a very |
58 | | * different way, and I don't use sorted vector paths. Also, it doesn't |
59 | | * use floating point values. |
60 | | * |
61 | | * Bézier segments are flattened by splitting them until their deviation |
62 | | * from straight line becomes much smaller than a pixel. Therefore, the |
63 | | * pixel coverage by a Bézier curve is calculated approximately. To |
64 | | * estimate the deviation, we use the distance from the control point |
65 | | * to the conic chord centre or the cubic chord trisection. These |
66 | | * distances vanish fast after each split. In the conic case, they vanish |
67 | | * predictably and the number of necessary splits can be calculated. |
68 | | * |
69 | | * This renderer has the following advantages: |
70 | | * |
71 | | * - It doesn't need an intermediate bitmap. Instead, one can supply a |
72 | | * callback function that will be called by the renderer to draw gray |
73 | | * spans on any target surface. You can thus do direct composition on |
74 | | * any kind of bitmap, provided that you give the renderer the right |
75 | | * callback. |
76 | | * |
77 | | * - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on |
78 | | * each pixel cell by straight segments. |
79 | | * |
80 | | * - It performs a single pass on the outline (the `standard' FT2 |
81 | | * renderer makes two passes). |
82 | | * |
83 | | * - It can easily be modified to render to _any_ number of gray levels |
84 | | * cheaply. |
85 | | * |
86 | | * - For small (< 80) pixel sizes, it is faster than the standard |
87 | | * renderer. |
88 | | * |
89 | | */ |
90 | | |
91 | | |
92 | | /************************************************************************** |
93 | | * |
94 | | * The macro FT_COMPONENT is used in trace mode. It is an implicit |
95 | | * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log |
96 | | * messages during execution. |
97 | | */ |
98 | | #undef FT_COMPONENT |
99 | | #define FT_COMPONENT smooth |
100 | | |
101 | | |
102 | | #ifdef STANDALONE_ |
103 | | |
104 | | |
105 | | /* The size in bytes of the render pool used by the scan-line converter */ |
106 | | /* to do all of its work. */ |
107 | | #define FT_RENDER_POOL_SIZE 16384L |
108 | | |
109 | | |
110 | | /* Auxiliary macros for token concatenation. */ |
111 | | #define FT_ERR_XCAT( x, y ) x ## y |
112 | | #define FT_ERR_CAT( x, y ) FT_ERR_XCAT( x, y ) |
113 | | |
114 | | #define FT_BEGIN_STMNT do { |
115 | | #define FT_END_STMNT } while ( 0 ) |
116 | | |
117 | | #define FT_MIN( a, b ) ( (a) < (b) ? (a) : (b) ) |
118 | | #define FT_MAX( a, b ) ( (a) > (b) ? (a) : (b) ) |
119 | | #define FT_ABS( a ) ( (a) < 0 ? -(a) : (a) ) |
120 | | |
121 | | |
122 | | /* |
123 | | * Approximate sqrt(x*x+y*y) using the `alpha max plus beta min' |
124 | | * algorithm. We use alpha = 1, beta = 3/8, giving us results with a |
125 | | * largest error less than 7% compared to the exact value. |
126 | | */ |
127 | | #define FT_HYPOT( x, y ) \ |
128 | | ( x = FT_ABS( x ), \ |
129 | | y = FT_ABS( y ), \ |
130 | | x > y ? x + ( 3 * y >> 3 ) \ |
131 | | : y + ( 3 * x >> 3 ) ) |
132 | | |
133 | | |
134 | | /* define this to dump debugging information */ |
135 | | /* #define FT_DEBUG_LEVEL_TRACE */ |
136 | | |
137 | | |
138 | | #ifdef FT_DEBUG_LEVEL_TRACE |
139 | | #include <stdio.h> |
140 | | #include <stdarg.h> |
141 | | #endif |
142 | | |
143 | | #include <stddef.h> |
144 | | #include <string.h> |
145 | | #include <setjmp.h> |
146 | | #include <limits.h> |
147 | | #define FT_CHAR_BIT CHAR_BIT |
148 | | #define FT_UINT_MAX UINT_MAX |
149 | | #define FT_INT_MAX INT_MAX |
150 | | #define FT_ULONG_MAX ULONG_MAX |
151 | | |
152 | | #define ADD_INT( a, b ) \ |
153 | | (int)( (unsigned int)(a) + (unsigned int)(b) ) |
154 | | |
155 | | |
156 | | #define ft_memset memset |
157 | | |
158 | | #define ft_setjmp setjmp |
159 | | #define ft_longjmp longjmp |
160 | | #define ft_jmp_buf jmp_buf |
161 | | |
162 | | typedef ptrdiff_t FT_PtrDist; |
163 | | |
164 | | |
165 | | #define Smooth_Err_Ok 0 |
166 | | #define Smooth_Err_Invalid_Outline -1 |
167 | | #define Smooth_Err_Cannot_Render_Glyph -2 |
168 | | #define Smooth_Err_Invalid_Argument -3 |
169 | | #define Smooth_Err_Raster_Overflow -4 |
170 | | |
171 | | #define FT_BEGIN_HEADER |
172 | | #define FT_END_HEADER |
173 | | |
174 | | #include "ftimage.h" |
175 | | #include "ftgrays.h" |
176 | | |
177 | | |
178 | | /* This macro is used to indicate that a function parameter is unused. */ |
179 | | /* Its purpose is simply to reduce compiler warnings. Note also that */ |
180 | | /* simply defining it as `(void)x' doesn't avoid warnings with certain */ |
181 | | /* ANSI compilers (e.g. LCC). */ |
182 | | #define FT_UNUSED( x ) (x) = (x) |
183 | | |
184 | | |
185 | | /* we only use level 5 & 7 tracing messages; cf. ftdebug.h */ |
186 | | |
187 | | #ifdef FT_DEBUG_LEVEL_TRACE |
188 | | |
189 | | void |
190 | | FT_Message( const char* fmt, |
191 | | ... ) |
192 | | { |
193 | | va_list ap; |
194 | | |
195 | | |
196 | | va_start( ap, fmt ); |
197 | | vfprintf( stderr, fmt, ap ); |
198 | | va_end( ap ); |
199 | | } |
200 | | |
201 | | |
202 | | /* empty function useful for setting a breakpoint to catch errors */ |
203 | | int |
204 | | FT_Throw( int error, |
205 | | int line, |
206 | | const char* file ) |
207 | | { |
208 | | FT_UNUSED( error ); |
209 | | FT_UNUSED( line ); |
210 | | FT_UNUSED( file ); |
211 | | |
212 | | return 0; |
213 | | } |
214 | | |
215 | | |
216 | | /* we don't handle tracing levels in stand-alone mode; */ |
217 | | #ifndef FT_TRACE5 |
218 | | #define FT_TRACE5( varformat ) FT_Message varformat |
219 | | #endif |
220 | | #ifndef FT_TRACE7 |
221 | | #define FT_TRACE7( varformat ) FT_Message varformat |
222 | | #endif |
223 | | #ifndef FT_ERROR |
224 | | #define FT_ERROR( varformat ) FT_Message varformat |
225 | | #endif |
226 | | |
227 | | #define FT_THROW( e ) \ |
228 | | ( FT_Throw( FT_ERR_CAT( Smooth_Err_, e ), \ |
229 | | __LINE__, \ |
230 | | __FILE__ ) | \ |
231 | | FT_ERR_CAT( Smooth_Err_, e ) ) |
232 | | |
233 | | #else /* !FT_DEBUG_LEVEL_TRACE */ |
234 | | |
235 | | #define FT_TRACE5( x ) do { } while ( 0 ) /* nothing */ |
236 | | #define FT_TRACE7( x ) do { } while ( 0 ) /* nothing */ |
237 | | #define FT_ERROR( x ) do { } while ( 0 ) /* nothing */ |
238 | | #define FT_THROW( e ) FT_ERR_CAT( Smooth_Err_, e ) |
239 | | |
240 | | |
241 | | #endif /* !FT_DEBUG_LEVEL_TRACE */ |
242 | | |
243 | | |
244 | | #define FT_DEFINE_OUTLINE_FUNCS( class_, \ |
245 | | move_to_, line_to_, \ |
246 | | conic_to_, cubic_to_, \ |
247 | | shift_, delta_ ) \ |
248 | | static const FT_Outline_Funcs class_ = \ |
249 | | { \ |
250 | | move_to_, \ |
251 | | line_to_, \ |
252 | | conic_to_, \ |
253 | | cubic_to_, \ |
254 | | shift_, \ |
255 | | delta_ \ |
256 | | }; |
257 | | |
258 | | #define FT_DEFINE_RASTER_FUNCS( class_, glyph_format_, \ |
259 | | raster_new_, raster_reset_, \ |
260 | | raster_set_mode_, raster_render_, \ |
261 | | raster_done_ ) \ |
262 | | const FT_Raster_Funcs class_ = \ |
263 | | { \ |
264 | | glyph_format_, \ |
265 | | raster_new_, \ |
266 | | raster_reset_, \ |
267 | | raster_set_mode_, \ |
268 | | raster_render_, \ |
269 | | raster_done_ \ |
270 | | }; |
271 | | |
272 | | |
273 | | #else /* !STANDALONE_ */ |
274 | | |
275 | | |
276 | | #include "ftgrays.h" |
277 | | #include <freetype/internal/ftobjs.h> |
278 | | #include <freetype/internal/ftdebug.h> |
279 | | #include <freetype/internal/ftcalc.h> |
280 | | #include <freetype/ftoutln.h> |
281 | | |
282 | | #include "ftsmerrs.h" |
283 | | |
284 | | |
285 | | #endif /* !STANDALONE_ */ |
286 | | |
287 | | |
288 | | #ifndef FT_MEM_SET |
289 | | #define FT_MEM_SET( d, s, c ) ft_memset( d, s, c ) |
290 | | #endif |
291 | | |
292 | | #ifndef FT_MEM_ZERO |
293 | | #define FT_MEM_ZERO( dest, count ) FT_MEM_SET( dest, 0, count ) |
294 | | #endif |
295 | | |
296 | | #ifndef FT_ZERO |
297 | | #define FT_ZERO( p ) FT_MEM_ZERO( p, sizeof ( *(p) ) ) |
298 | | #endif |
299 | | |
300 | | /* as usual, for the speed hungry :-) */ |
301 | | |
302 | | #undef RAS_ARG |
303 | | #undef RAS_ARG_ |
304 | | #undef RAS_VAR |
305 | | #undef RAS_VAR_ |
306 | | |
307 | | #ifndef FT_STATIC_RASTER |
308 | | |
309 | | #define RAS_ARG gray_PWorker worker |
310 | | #define RAS_ARG_ gray_PWorker worker, |
311 | | |
312 | 0 | #define RAS_VAR worker |
313 | 0 | #define RAS_VAR_ worker, |
314 | | |
315 | | #else /* FT_STATIC_RASTER */ |
316 | | |
317 | | #define RAS_ARG void |
318 | | #define RAS_ARG_ /* empty */ |
319 | | #define RAS_VAR /* empty */ |
320 | | #define RAS_VAR_ /* empty */ |
321 | | |
322 | | #endif /* FT_STATIC_RASTER */ |
323 | | |
324 | | |
325 | | /* must be at least 6 bits! */ |
326 | 0 | #define PIXEL_BITS 8 |
327 | | |
328 | 0 | #define ONE_PIXEL ( 1 << PIXEL_BITS ) |
329 | 0 | #define TRUNC( x ) (TCoord)( (x) >> PIXEL_BITS ) |
330 | 0 | #define FRACT( x ) (TCoord)( (x) & ( ONE_PIXEL - 1 ) ) |
331 | | |
332 | | #if PIXEL_BITS >= 6 |
333 | 0 | #define UPSCALE( x ) ( (x) * ( ONE_PIXEL >> 6 ) ) |
334 | | #define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) ) |
335 | | #else |
336 | | #define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) ) |
337 | | #define DOWNSCALE( x ) ( (x) * ( 64 >> PIXEL_BITS ) ) |
338 | | #endif |
339 | | |
340 | | |
341 | | /* Compute `dividend / divisor' and return both its quotient and */ |
342 | | /* remainder, cast to a specific type. This macro also ensures that */ |
343 | | /* the remainder is always positive. We use the remainder to keep */ |
344 | | /* track of accumulating errors and compensate for them. */ |
345 | | #define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ |
346 | | FT_BEGIN_STMNT \ |
347 | | (quotient) = (type)( (dividend) / (divisor) ); \ |
348 | | (remainder) = (type)( (dividend) % (divisor) ); \ |
349 | | if ( (remainder) < 0 ) \ |
350 | | { \ |
351 | | (quotient)--; \ |
352 | | (remainder) += (type)(divisor); \ |
353 | | } \ |
354 | | FT_END_STMNT |
355 | | |
356 | | #ifdef __arm__ |
357 | | /* Work around a bug specific to GCC which make the compiler fail to */ |
358 | | /* optimize a division and modulo operation on the same parameters */ |
359 | | /* into a single call to `__aeabi_idivmod'. See */ |
360 | | /* */ |
361 | | /* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721 */ |
362 | | #undef FT_DIV_MOD |
363 | | #define FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ |
364 | | FT_BEGIN_STMNT \ |
365 | | (quotient) = (type)( (dividend) / (divisor) ); \ |
366 | | (remainder) = (type)( (dividend) - (quotient) * (divisor) ); \ |
367 | | if ( (remainder) < 0 ) \ |
368 | | { \ |
369 | | (quotient)--; \ |
370 | | (remainder) += (type)(divisor); \ |
371 | | } \ |
372 | | FT_END_STMNT |
373 | | #endif /* __arm__ */ |
374 | | |
375 | | |
376 | | /* These macros speed up repetitive divisions by replacing them */ |
377 | | /* with multiplications and right shifts. */ |
378 | | #define FT_UDIVPREP( c, b ) \ |
379 | 0 | long b ## _r = c ? (long)( FT_ULONG_MAX >> PIXEL_BITS ) / ( b ) \ |
380 | 0 | : 0 |
381 | | #define FT_UDIV( a, b ) \ |
382 | 0 | (TCoord)( ( (unsigned long)( a ) * (unsigned long)( b ## _r ) ) >> \ |
383 | 0 | ( sizeof( long ) * FT_CHAR_BIT - PIXEL_BITS ) ) |
384 | | |
385 | | |
386 | | /* Scale area and apply fill rule to calculate the coverage byte. */ |
387 | | /* The top fill bit is used for the non-zero rule. The eighth */ |
388 | | /* fill bit is used for the even-odd rule. The higher coverage */ |
389 | | /* bytes are either clamped for the non-zero-rule or discarded */ |
390 | | /* later for the even-odd rule. */ |
391 | | #define FT_FILL_RULE( coverage, area, fill ) \ |
392 | 0 | FT_BEGIN_STMNT \ |
393 | 0 | coverage = (int)( area >> ( PIXEL_BITS * 2 + 1 - 8 ) ); \ |
394 | 0 | if ( coverage & fill ) \ |
395 | 0 | coverage = ~coverage; \ |
396 | 0 | if ( coverage > 255 && fill & INT_MIN ) \ |
397 | 0 | coverage = 255; \ |
398 | 0 | FT_END_STMNT |
399 | | |
400 | | |
401 | | /* It is faster to write small spans byte-by-byte than calling */ |
402 | | /* `memset'. This is mainly due to the cost of the function call. */ |
403 | | #define FT_GRAY_SET( d, s, count ) \ |
404 | 0 | FT_BEGIN_STMNT \ |
405 | 0 | unsigned char* q = d; \ |
406 | 0 | switch ( count ) \ |
407 | 0 | { \ |
408 | 0 | case 7: *q++ = (unsigned char)s; /* fall through */ \ |
409 | 0 | case 6: *q++ = (unsigned char)s; /* fall through */ \ |
410 | 0 | case 5: *q++ = (unsigned char)s; /* fall through */ \ |
411 | 0 | case 4: *q++ = (unsigned char)s; /* fall through */ \ |
412 | 0 | case 3: *q++ = (unsigned char)s; /* fall through */ \ |
413 | 0 | case 2: *q++ = (unsigned char)s; /* fall through */ \ |
414 | 0 | case 1: *q = (unsigned char)s; /* fall through */ \ |
415 | 0 | case 0: break; \ |
416 | 0 | default: FT_MEM_SET( d, s, count ); \ |
417 | 0 | } \ |
418 | 0 | FT_END_STMNT |
419 | | |
420 | | |
421 | | /************************************************************************** |
422 | | * |
423 | | * TYPE DEFINITIONS |
424 | | */ |
425 | | |
426 | | /* don't change the following types to FT_Int or FT_Pos, since we might */ |
427 | | /* need to define them to "float" or "double" when experimenting with */ |
428 | | /* new algorithms */ |
429 | | |
430 | | typedef long TPos; /* subpixel coordinate */ |
431 | | typedef int TCoord; /* integer scanline/pixel coordinate */ |
432 | | typedef int TArea; /* cell areas, coordinate products */ |
433 | | |
434 | | |
435 | | typedef struct TCell_* PCell; |
436 | | |
437 | | typedef struct TCell_ |
438 | | { |
439 | | TCoord x; /* same with gray_TWorker.ex */ |
440 | | TCoord cover; /* same with gray_TWorker.cover */ |
441 | | TArea area; |
442 | | PCell next; |
443 | | |
444 | | } TCell; |
445 | | |
446 | | typedef struct TPixmap_ |
447 | | { |
448 | | unsigned char* origin; /* pixmap origin at the bottom-left */ |
449 | | int pitch; /* pitch to go down one row */ |
450 | | |
451 | | } TPixmap; |
452 | | |
453 | | /* maximum number of gray cells in the buffer */ |
454 | | #if FT_RENDER_POOL_SIZE > 2048 |
455 | 0 | #define FT_MAX_GRAY_POOL ( FT_RENDER_POOL_SIZE / sizeof ( TCell ) ) |
456 | | #else |
457 | | #define FT_MAX_GRAY_POOL ( 2048 / sizeof ( TCell ) ) |
458 | | #endif |
459 | | |
460 | | /* FT_Span buffer size for direct rendering only */ |
461 | 0 | #define FT_MAX_GRAY_SPANS 16 |
462 | | |
463 | | |
464 | | #if defined( _MSC_VER ) /* Visual C++ (and Intel C++) */ |
465 | | /* We disable the warning `structure was padded due to */ |
466 | | /* __declspec(align())' in order to compile cleanly with */ |
467 | | /* the maximum level of warnings. */ |
468 | | #pragma warning( push ) |
469 | | #pragma warning( disable : 4324 ) |
470 | | #endif /* _MSC_VER */ |
471 | | |
472 | | typedef struct gray_TWorker_ |
473 | | { |
474 | | ft_jmp_buf jump_buffer; |
475 | | |
476 | | TCoord min_ex, max_ex; /* min and max integer pixel coordinates */ |
477 | | TCoord min_ey, max_ey; |
478 | | TCoord count_ey; /* same as (max_ey - min_ey) */ |
479 | | |
480 | | PCell cell; /* current cell */ |
481 | | PCell cell_free; /* call allocation next free slot */ |
482 | | PCell cell_limit; /* cell allocation limit */ |
483 | | |
484 | | PCell* ycells; /* array of cell linked-lists; one per */ |
485 | | /* vertical coordinate in the current band */ |
486 | | |
487 | | PCell cells; /* cell storage area */ |
488 | | FT_PtrDist max_cells; /* cell storage capacity */ |
489 | | |
490 | | TPos x, y; /* last point position */ |
491 | | |
492 | | FT_Outline outline; /* input outline */ |
493 | | TPixmap target; /* target pixmap */ |
494 | | |
495 | | FT_Raster_Span_Func render_span; |
496 | | void* render_span_data; |
497 | | |
498 | | } gray_TWorker, *gray_PWorker; |
499 | | |
500 | | #if defined( _MSC_VER ) |
501 | | #pragma warning( pop ) |
502 | | #endif |
503 | | |
504 | | #ifndef FT_STATIC_RASTER |
505 | 0 | #define ras (*worker) |
506 | | #else |
507 | | static gray_TWorker ras; |
508 | | #endif |
509 | | |
510 | | /* |
511 | | * Return a pointer to the 'null cell', used as a sentinel at the end of |
512 | | * all `ycells` linked lists. Its x coordinate should be maximal to |
513 | | * ensure no NULL checks are necessary when looking for an insertion point |
514 | | * in `gray_set_cell`. Other loops should check the cell pointer with |
515 | | * CELL_IS_NULL() to detect the end of the list. |
516 | | */ |
517 | 0 | #define NULL_CELL_PTR( ras ) (ras).cells |
518 | | |
519 | | /* The |x| value of the null cell. Must be the largest possible */ |
520 | | /* integer value stored in a `TCell.x` field. */ |
521 | 0 | #define CELL_MAX_X_VALUE INT_MAX |
522 | | |
523 | | /* Return true iff |cell| points to the null cell. */ |
524 | 0 | #define CELL_IS_NULL( cell ) ( (cell)->x == CELL_MAX_X_VALUE ) |
525 | | |
526 | | |
527 | | #define FT_INTEGRATE( ras, a, b ) \ |
528 | 0 | ras.cell->cover = ADD_INT( ras.cell->cover, a ), \ |
529 | 0 | ras.cell->area = ADD_INT( ras.cell->area, (a) * (TArea)(b) ) |
530 | | |
531 | | |
532 | | typedef struct gray_TRaster_ |
533 | | { |
534 | | void* memory; |
535 | | |
536 | | } gray_TRaster, *gray_PRaster; |
537 | | |
538 | | |
539 | | #ifdef FT_DEBUG_LEVEL_TRACE |
540 | | |
541 | | /* to be called while in the debugger -- */ |
542 | | /* this function causes a compiler warning since it is unused otherwise */ |
543 | | static void |
544 | | gray_dump_cells( RAS_ARG ) |
545 | | { |
546 | | int y; |
547 | | |
548 | | |
549 | | for ( y = ras.min_ey; y < ras.max_ey; y++ ) |
550 | | { |
551 | | PCell cell = ras.ycells[y - ras.min_ey]; |
552 | | |
553 | | |
554 | | printf( "%3d:", y ); |
555 | | |
556 | | for ( ; !CELL_IS_NULL( cell ); cell = cell->next ) |
557 | | printf( " (%3d, c:%4d, a:%6d)", |
558 | | cell->x, cell->cover, cell->area ); |
559 | | printf( "\n" ); |
560 | | } |
561 | | } |
562 | | |
563 | | #endif /* FT_DEBUG_LEVEL_TRACE */ |
564 | | |
565 | | |
566 | | /************************************************************************** |
567 | | * |
568 | | * Set the current cell to a new position. |
569 | | */ |
570 | | static void |
571 | | gray_set_cell( RAS_ARG_ TCoord ex, |
572 | | TCoord ey ) |
573 | 0 | { |
574 | | /* Move the cell pointer to a new position in the linked list. We use */ |
575 | | /* NULL to indicate that the cell is outside of the clipping region */ |
576 | | /* during the render phase. This means that: */ |
577 | | /* */ |
578 | | /* . the new vertical position must be within min_ey..max_ey-1. */ |
579 | | /* . the new horizontal position must be strictly less than max_ex */ |
580 | | /* */ |
581 | | /* Note that if a cell is to the left of the clipping region, it is */ |
582 | | /* actually set to the (min_ex-1) horizontal position. */ |
583 | |
|
584 | 0 | TCoord ey_index = ey - ras.min_ey; |
585 | | |
586 | |
|
587 | 0 | if ( ey_index < 0 || ey_index >= ras.count_ey || ex >= ras.max_ex ) |
588 | 0 | ras.cell = NULL_CELL_PTR( ras ); |
589 | 0 | else |
590 | 0 | { |
591 | 0 | PCell* pcell = ras.ycells + ey_index; |
592 | 0 | PCell cell; |
593 | | |
594 | |
|
595 | 0 | ex = FT_MAX( ex, ras.min_ex - 1 ); |
596 | |
|
597 | 0 | while ( 1 ) |
598 | 0 | { |
599 | 0 | cell = *pcell; |
600 | |
|
601 | 0 | if ( cell->x > ex ) |
602 | 0 | break; |
603 | | |
604 | 0 | if ( cell->x == ex ) |
605 | 0 | goto Found; |
606 | | |
607 | 0 | pcell = &cell->next; |
608 | 0 | } |
609 | | |
610 | | /* insert new cell */ |
611 | 0 | cell = ras.cell_free++; |
612 | 0 | if ( cell >= ras.cell_limit ) |
613 | 0 | ft_longjmp( ras.jump_buffer, 1 ); |
614 | | |
615 | 0 | cell->x = ex; |
616 | 0 | cell->area = 0; |
617 | 0 | cell->cover = 0; |
618 | |
|
619 | 0 | cell->next = *pcell; |
620 | 0 | *pcell = cell; |
621 | |
|
622 | 0 | Found: |
623 | 0 | ras.cell = cell; |
624 | 0 | } |
625 | 0 | } |
626 | | |
627 | | |
628 | | #ifndef FT_LONG64 |
629 | | |
630 | | /************************************************************************** |
631 | | * |
632 | | * Render a scanline as one or more cells. |
633 | | */ |
634 | | static void |
635 | | gray_render_scanline( RAS_ARG_ TCoord ey, |
636 | | TPos x1, |
637 | | TCoord y1, |
638 | | TPos x2, |
639 | | TCoord y2 ) |
640 | | { |
641 | | TCoord ex1, ex2, fx1, fx2, first, dy, delta, mod; |
642 | | TPos p, dx; |
643 | | int incr; |
644 | | |
645 | | |
646 | | ex1 = TRUNC( x1 ); |
647 | | ex2 = TRUNC( x2 ); |
648 | | |
649 | | /* trivial case. Happens often */ |
650 | | if ( y1 == y2 ) |
651 | | { |
652 | | gray_set_cell( RAS_VAR_ ex2, ey ); |
653 | | return; |
654 | | } |
655 | | |
656 | | fx1 = FRACT( x1 ); |
657 | | fx2 = FRACT( x2 ); |
658 | | |
659 | | /* everything is located in a single cell. That is easy! */ |
660 | | /* */ |
661 | | if ( ex1 == ex2 ) |
662 | | goto End; |
663 | | |
664 | | /* ok, we'll have to render a run of adjacent cells on the same */ |
665 | | /* scanline... */ |
666 | | /* */ |
667 | | dx = x2 - x1; |
668 | | dy = y2 - y1; |
669 | | |
670 | | if ( dx > 0 ) |
671 | | { |
672 | | p = ( ONE_PIXEL - fx1 ) * dy; |
673 | | first = ONE_PIXEL; |
674 | | incr = 1; |
675 | | } |
676 | | else |
677 | | { |
678 | | p = fx1 * dy; |
679 | | first = 0; |
680 | | incr = -1; |
681 | | dx = -dx; |
682 | | } |
683 | | |
684 | | /* the fractional part of y-delta is mod/dx. It is essential to */ |
685 | | /* keep track of its accumulation for accurate rendering. */ |
686 | | /* XXX: y-delta and x-delta below should be related. */ |
687 | | FT_DIV_MOD( TCoord, p, dx, delta, mod ); |
688 | | |
689 | | FT_INTEGRATE( ras, delta, fx1 + first ); |
690 | | y1 += delta; |
691 | | ex1 += incr; |
692 | | gray_set_cell( RAS_VAR_ ex1, ey ); |
693 | | |
694 | | if ( ex1 != ex2 ) |
695 | | { |
696 | | TCoord lift, rem; |
697 | | |
698 | | |
699 | | p = ONE_PIXEL * dy; |
700 | | FT_DIV_MOD( TCoord, p, dx, lift, rem ); |
701 | | |
702 | | do |
703 | | { |
704 | | delta = lift; |
705 | | mod += rem; |
706 | | if ( mod >= (TCoord)dx ) |
707 | | { |
708 | | mod -= (TCoord)dx; |
709 | | delta++; |
710 | | } |
711 | | |
712 | | FT_INTEGRATE( ras, delta, ONE_PIXEL ); |
713 | | y1 += delta; |
714 | | ex1 += incr; |
715 | | gray_set_cell( RAS_VAR_ ex1, ey ); |
716 | | } while ( ex1 != ex2 ); |
717 | | } |
718 | | |
719 | | fx1 = ONE_PIXEL - first; |
720 | | |
721 | | End: |
722 | | FT_INTEGRATE( ras, y2 - y1, fx1 + fx2 ); |
723 | | } |
724 | | |
725 | | |
726 | | /************************************************************************** |
727 | | * |
728 | | * Render a given line as a series of scanlines. |
729 | | */ |
730 | | static void |
731 | | gray_render_line( RAS_ARG_ TPos to_x, |
732 | | TPos to_y ) |
733 | | { |
734 | | TCoord ey1, ey2, fy1, fy2, first, delta, mod; |
735 | | TPos p, dx, dy, x, x2; |
736 | | int incr; |
737 | | |
738 | | |
739 | | ey1 = TRUNC( ras.y ); |
740 | | ey2 = TRUNC( to_y ); /* if (ey2 >= ras.max_ey) ey2 = ras.max_ey-1; */ |
741 | | |
742 | | /* perform vertical clipping */ |
743 | | if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) || |
744 | | ( ey1 < ras.min_ey && ey2 < ras.min_ey ) ) |
745 | | goto End; |
746 | | |
747 | | fy1 = FRACT( ras.y ); |
748 | | fy2 = FRACT( to_y ); |
749 | | |
750 | | /* everything is on a single scanline */ |
751 | | if ( ey1 == ey2 ) |
752 | | { |
753 | | gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, to_x, fy2 ); |
754 | | goto End; |
755 | | } |
756 | | |
757 | | dx = to_x - ras.x; |
758 | | dy = to_y - ras.y; |
759 | | |
760 | | /* vertical line - avoid calling gray_render_scanline */ |
761 | | if ( dx == 0 ) |
762 | | { |
763 | | TCoord ex = TRUNC( ras.x ); |
764 | | TCoord two_fx = FRACT( ras.x ) << 1; |
765 | | |
766 | | |
767 | | if ( dy > 0) |
768 | | { |
769 | | first = ONE_PIXEL; |
770 | | incr = 1; |
771 | | } |
772 | | else |
773 | | { |
774 | | first = 0; |
775 | | incr = -1; |
776 | | } |
777 | | |
778 | | delta = first - fy1; |
779 | | FT_INTEGRATE( ras, delta, two_fx); |
780 | | ey1 += incr; |
781 | | |
782 | | gray_set_cell( RAS_VAR_ ex, ey1 ); |
783 | | |
784 | | delta = first + first - ONE_PIXEL; |
785 | | while ( ey1 != ey2 ) |
786 | | { |
787 | | FT_INTEGRATE( ras, delta, two_fx); |
788 | | ey1 += incr; |
789 | | |
790 | | gray_set_cell( RAS_VAR_ ex, ey1 ); |
791 | | } |
792 | | |
793 | | delta = fy2 - ONE_PIXEL + first; |
794 | | FT_INTEGRATE( ras, delta, two_fx); |
795 | | |
796 | | goto End; |
797 | | } |
798 | | |
799 | | /* ok, we have to render several scanlines */ |
800 | | if ( dy > 0) |
801 | | { |
802 | | p = ( ONE_PIXEL - fy1 ) * dx; |
803 | | first = ONE_PIXEL; |
804 | | incr = 1; |
805 | | } |
806 | | else |
807 | | { |
808 | | p = fy1 * dx; |
809 | | first = 0; |
810 | | incr = -1; |
811 | | dy = -dy; |
812 | | } |
813 | | |
814 | | /* the fractional part of x-delta is mod/dy. It is essential to */ |
815 | | /* keep track of its accumulation for accurate rendering. */ |
816 | | FT_DIV_MOD( TCoord, p, dy, delta, mod ); |
817 | | |
818 | | x = ras.x + delta; |
819 | | gray_render_scanline( RAS_VAR_ ey1, ras.x, fy1, x, first ); |
820 | | |
821 | | ey1 += incr; |
822 | | gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 ); |
823 | | |
824 | | if ( ey1 != ey2 ) |
825 | | { |
826 | | TCoord lift, rem; |
827 | | |
828 | | |
829 | | p = ONE_PIXEL * dx; |
830 | | FT_DIV_MOD( TCoord, p, dy, lift, rem ); |
831 | | |
832 | | do |
833 | | { |
834 | | delta = lift; |
835 | | mod += rem; |
836 | | if ( mod >= (TCoord)dy ) |
837 | | { |
838 | | mod -= (TCoord)dy; |
839 | | delta++; |
840 | | } |
841 | | |
842 | | x2 = x + delta; |
843 | | gray_render_scanline( RAS_VAR_ ey1, |
844 | | x, ONE_PIXEL - first, |
845 | | x2, first ); |
846 | | x = x2; |
847 | | |
848 | | ey1 += incr; |
849 | | gray_set_cell( RAS_VAR_ TRUNC( x ), ey1 ); |
850 | | } while ( ey1 != ey2 ); |
851 | | } |
852 | | |
853 | | gray_render_scanline( RAS_VAR_ ey1, |
854 | | x, ONE_PIXEL - first, |
855 | | to_x, fy2 ); |
856 | | |
857 | | End: |
858 | | ras.x = to_x; |
859 | | ras.y = to_y; |
860 | | } |
861 | | |
862 | | #else |
863 | | |
864 | | /************************************************************************** |
865 | | * |
866 | | * Render a straight line across multiple cells in any direction. |
867 | | */ |
868 | | static void |
869 | | gray_render_line( RAS_ARG_ TPos to_x, |
870 | | TPos to_y ) |
871 | 0 | { |
872 | 0 | TPos dx, dy; |
873 | 0 | TCoord fx1, fy1, fx2, fy2; |
874 | 0 | TCoord ex1, ey1, ex2, ey2; |
875 | | |
876 | |
|
877 | 0 | ey1 = TRUNC( ras.y ); |
878 | 0 | ey2 = TRUNC( to_y ); |
879 | | |
880 | | /* perform vertical clipping */ |
881 | 0 | if ( ( ey1 >= ras.max_ey && ey2 >= ras.max_ey ) || |
882 | 0 | ( ey1 < ras.min_ey && ey2 < ras.min_ey ) ) |
883 | 0 | goto End; |
884 | | |
885 | 0 | ex1 = TRUNC( ras.x ); |
886 | 0 | ex2 = TRUNC( to_x ); |
887 | |
|
888 | 0 | fx1 = FRACT( ras.x ); |
889 | 0 | fy1 = FRACT( ras.y ); |
890 | |
|
891 | 0 | dx = to_x - ras.x; |
892 | 0 | dy = to_y - ras.y; |
893 | |
|
894 | 0 | if ( ex1 == ex2 && ey1 == ey2 ) /* inside one cell */ |
895 | 0 | ; |
896 | 0 | else if ( dy == 0 ) /* ex1 != ex2 */ /* any horizontal line */ |
897 | 0 | { |
898 | 0 | gray_set_cell( RAS_VAR_ ex2, ey2 ); |
899 | 0 | goto End; |
900 | 0 | } |
901 | 0 | else if ( dx == 0 ) |
902 | 0 | { |
903 | 0 | if ( dy > 0 ) /* vertical line up */ |
904 | 0 | do |
905 | 0 | { |
906 | 0 | fy2 = ONE_PIXEL; |
907 | 0 | FT_INTEGRATE( ras, fy2 - fy1, fx1 * 2 ); |
908 | 0 | fy1 = 0; |
909 | 0 | ey1++; |
910 | 0 | gray_set_cell( RAS_VAR_ ex1, ey1 ); |
911 | 0 | } while ( ey1 != ey2 ); |
912 | 0 | else /* vertical line down */ |
913 | 0 | do |
914 | 0 | { |
915 | 0 | fy2 = 0; |
916 | 0 | FT_INTEGRATE( ras, fy2 - fy1, fx1 * 2 ); |
917 | 0 | fy1 = ONE_PIXEL; |
918 | 0 | ey1--; |
919 | 0 | gray_set_cell( RAS_VAR_ ex1, ey1 ); |
920 | 0 | } while ( ey1 != ey2 ); |
921 | 0 | } |
922 | 0 | else /* any other line */ |
923 | 0 | { |
924 | 0 | TPos prod = dx * (TPos)fy1 - dy * (TPos)fx1; |
925 | 0 | FT_UDIVPREP( ex1 != ex2, dx ); |
926 | 0 | FT_UDIVPREP( ey1 != ey2, dy ); |
927 | | |
928 | | |
929 | | /* The fundamental value `prod' determines which side and the */ |
930 | | /* exact coordinate where the line exits current cell. It is */ |
931 | | /* also easily updated when moving from one cell to the next. */ |
932 | 0 | do |
933 | 0 | { |
934 | 0 | if ( prod - dx * ONE_PIXEL > 0 && |
935 | 0 | prod <= 0 ) /* left */ |
936 | 0 | { |
937 | 0 | fx2 = 0; |
938 | 0 | fy2 = FT_UDIV( -prod, -dx ); |
939 | 0 | prod -= dy * ONE_PIXEL; |
940 | 0 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
941 | 0 | fx1 = ONE_PIXEL; |
942 | 0 | fy1 = fy2; |
943 | 0 | ex1--; |
944 | 0 | } |
945 | 0 | else if ( prod - dx * ONE_PIXEL + dy * ONE_PIXEL > 0 && |
946 | 0 | prod - dx * ONE_PIXEL <= 0 ) /* up */ |
947 | 0 | { |
948 | 0 | prod -= dx * ONE_PIXEL; |
949 | 0 | fx2 = FT_UDIV( -prod, dy ); |
950 | 0 | fy2 = ONE_PIXEL; |
951 | 0 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
952 | 0 | fx1 = fx2; |
953 | 0 | fy1 = 0; |
954 | 0 | ey1++; |
955 | 0 | } |
956 | 0 | else if ( prod + dy * ONE_PIXEL >= 0 && |
957 | 0 | prod - dx * ONE_PIXEL + dy * ONE_PIXEL <= 0 ) /* right */ |
958 | 0 | { |
959 | 0 | prod += dy * ONE_PIXEL; |
960 | 0 | fx2 = ONE_PIXEL; |
961 | 0 | fy2 = FT_UDIV( prod, dx ); |
962 | 0 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
963 | 0 | fx1 = 0; |
964 | 0 | fy1 = fy2; |
965 | 0 | ex1++; |
966 | 0 | } |
967 | 0 | else /* ( prod > 0 && |
968 | | prod + dy * ONE_PIXEL < 0 ) down */ |
969 | 0 | { |
970 | 0 | fx2 = FT_UDIV( prod, -dy ); |
971 | 0 | fy2 = 0; |
972 | 0 | prod += dx * ONE_PIXEL; |
973 | 0 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
974 | 0 | fx1 = fx2; |
975 | 0 | fy1 = ONE_PIXEL; |
976 | 0 | ey1--; |
977 | 0 | } |
978 | |
|
979 | 0 | gray_set_cell( RAS_VAR_ ex1, ey1 ); |
980 | |
|
981 | 0 | } while ( ex1 != ex2 || ey1 != ey2 ); |
982 | 0 | } |
983 | |
|
984 | 0 | fx2 = FRACT( to_x ); |
985 | 0 | fy2 = FRACT( to_y ); |
986 | |
|
987 | 0 | FT_INTEGRATE( ras, fy2 - fy1, fx1 + fx2 ); |
988 | |
|
989 | 0 | End: |
990 | 0 | ras.x = to_x; |
991 | 0 | ras.y = to_y; |
992 | 0 | } |
993 | | |
994 | | #endif |
995 | | |
996 | | /* |
997 | | * Benchmarking shows that using DDA to flatten the quadratic Bézier arcs |
998 | | * is slightly faster in the following cases: |
999 | | * |
1000 | | * - When the host CPU is 64-bit. |
1001 | | * - When SSE2 SIMD registers and instructions are available (even on |
1002 | | * x86). |
1003 | | * |
1004 | | * For other cases, using binary splits is actually slightly faster. |
1005 | | */ |
1006 | | #if defined( __SSE2__ ) || \ |
1007 | | defined( __x86_64__ ) || \ |
1008 | | defined( __aarch64__ ) || \ |
1009 | | defined( _M_AMD64 ) || \ |
1010 | | defined( _M_ARM64 ) |
1011 | | # define BEZIER_USE_DDA 1 |
1012 | | #else |
1013 | | # define BEZIER_USE_DDA 0 |
1014 | | #endif |
1015 | | |
1016 | | /* |
1017 | | * For now, the code that depends on `BEZIER_USE_DDA` requires `FT_Int64` |
1018 | | * to be defined. If `FT_LONG64` is not defined, meaning there is no |
1019 | | * 64-bit type available, disable it to avoid compilation errors. See for |
1020 | | * example https://gitlab.freedesktop.org/freetype/freetype/-/issues/1071. |
1021 | | */ |
1022 | | #if !defined( FT_LONG64 ) |
1023 | | # undef BEZIER_USE_DDA |
1024 | | # define BEZIER_USE_DDA 0 |
1025 | | #endif |
1026 | | |
1027 | | #if BEZIER_USE_DDA |
1028 | | |
1029 | | #ifdef __SSE2__ |
1030 | | # include <emmintrin.h> |
1031 | | #endif |
1032 | | |
1033 | 0 | #define LEFT_SHIFT( a, b ) (FT_Int64)( (FT_UInt64)(a) << (b) ) |
1034 | | |
1035 | | |
1036 | | static void |
1037 | | gray_render_conic( RAS_ARG_ const FT_Vector* control, |
1038 | | const FT_Vector* to ) |
1039 | 0 | { |
1040 | 0 | FT_Vector p0, p1, p2; |
1041 | 0 | TPos dx, dy; |
1042 | 0 | int shift; |
1043 | |
|
1044 | 0 | FT_Int64 ax, ay, bx, by; |
1045 | 0 | FT_Int64 rx, ry; |
1046 | 0 | FT_Int64 qx, qy; |
1047 | 0 | FT_Int64 px, py; |
1048 | |
|
1049 | 0 | FT_UInt count; |
1050 | | |
1051 | |
|
1052 | 0 | p0.x = ras.x; |
1053 | 0 | p0.y = ras.y; |
1054 | 0 | p1.x = UPSCALE( control->x ); |
1055 | 0 | p1.y = UPSCALE( control->y ); |
1056 | 0 | p2.x = UPSCALE( to->x ); |
1057 | 0 | p2.y = UPSCALE( to->y ); |
1058 | | |
1059 | | /* short-cut the arc that crosses the current band */ |
1060 | 0 | if ( ( TRUNC( p0.y ) >= ras.max_ey && |
1061 | 0 | TRUNC( p1.y ) >= ras.max_ey && |
1062 | 0 | TRUNC( p2.y ) >= ras.max_ey ) || |
1063 | 0 | ( TRUNC( p0.y ) < ras.min_ey && |
1064 | 0 | TRUNC( p1.y ) < ras.min_ey && |
1065 | 0 | TRUNC( p2.y ) < ras.min_ey ) ) |
1066 | 0 | { |
1067 | 0 | ras.x = p2.x; |
1068 | 0 | ras.y = p2.y; |
1069 | 0 | return; |
1070 | 0 | } |
1071 | | |
1072 | 0 | dx = FT_ABS( p0.x + p2.x - 2 * p1.x ); |
1073 | 0 | dy = FT_ABS( p0.y + p2.y - 2 * p1.y ); |
1074 | 0 | if ( dx < dy ) |
1075 | 0 | dx = dy; |
1076 | |
|
1077 | 0 | if ( dx <= ONE_PIXEL / 4 ) |
1078 | 0 | { |
1079 | 0 | gray_render_line( RAS_VAR_ p2.x, p2.y ); |
1080 | 0 | return; |
1081 | 0 | } |
1082 | | |
1083 | | /* We can calculate the number of necessary bisections because */ |
1084 | | /* each bisection predictably reduces deviation exactly 4-fold. */ |
1085 | | /* Even 32-bit deviation would vanish after 16 bisections. */ |
1086 | 0 | shift = 0; |
1087 | 0 | do |
1088 | 0 | { |
1089 | 0 | dx >>= 2; |
1090 | 0 | shift += 1; |
1091 | |
|
1092 | 0 | } while ( dx > ONE_PIXEL / 4 ); |
1093 | | |
1094 | | /* |
1095 | | * The (P0,P1,P2) arc equation, for t in [0,1] range: |
1096 | | * |
1097 | | * P(t) = P0*(1-t)^2 + P1*2*t*(1-t) + P2*t^2 |
1098 | | * |
1099 | | * P(t) = P0 + 2*(P1-P0)*t + (P0+P2-2*P1)*t^2 |
1100 | | * = P0 + 2*B*t + A*t^2 |
1101 | | * |
1102 | | * for A = P0 + P2 - 2*P1 |
1103 | | * and B = P1 - P0 |
1104 | | * |
1105 | | * Let's consider the difference when advancing by a small |
1106 | | * parameter h: |
1107 | | * |
1108 | | * Q(h,t) = P(t+h) - P(t) = 2*B*h + A*h^2 + 2*A*h*t |
1109 | | * |
1110 | | * And then its own difference: |
1111 | | * |
1112 | | * R(h,t) = Q(h,t+h) - Q(h,t) = 2*A*h*h = R (constant) |
1113 | | * |
1114 | | * Since R is always a constant, it is possible to compute |
1115 | | * successive positions with: |
1116 | | * |
1117 | | * P = P0 |
1118 | | * Q = Q(h,0) = 2*B*h + A*h*h |
1119 | | * R = 2*A*h*h |
1120 | | * |
1121 | | * loop: |
1122 | | * P += Q |
1123 | | * Q += R |
1124 | | * EMIT(P) |
1125 | | * |
1126 | | * To ensure accurate results, perform computations on 64-bit |
1127 | | * values, after scaling them by 2^32. |
1128 | | * |
1129 | | * h = 1 / 2^N |
1130 | | * |
1131 | | * R << 32 = 2 * A << (32 - N - N) |
1132 | | * = A << (33 - 2*N) |
1133 | | * |
1134 | | * Q << 32 = (2 * B << (32 - N)) + (A << (32 - N - N)) |
1135 | | * = (B << (33 - N)) + (A << (32 - 2*N)) |
1136 | | */ |
1137 | |
|
1138 | 0 | #ifdef __SSE2__ |
1139 | | /* Experience shows that for small shift values, */ |
1140 | | /* SSE2 is actually slower. */ |
1141 | 0 | if ( shift > 2 ) |
1142 | 0 | { |
1143 | 0 | union |
1144 | 0 | { |
1145 | 0 | struct { FT_Int64 ax, ay, bx, by; } i; |
1146 | 0 | struct { __m128i a, b; } vec; |
1147 | |
|
1148 | 0 | } u; |
1149 | |
|
1150 | 0 | union |
1151 | 0 | { |
1152 | 0 | struct { FT_Int32 px_lo, px_hi, py_lo, py_hi; } i; |
1153 | 0 | __m128i vec; |
1154 | |
|
1155 | 0 | } v; |
1156 | |
|
1157 | 0 | __m128i a, b; |
1158 | 0 | __m128i r, q, q2; |
1159 | 0 | __m128i p; |
1160 | | |
1161 | |
|
1162 | 0 | u.i.ax = p0.x + p2.x - 2 * p1.x; |
1163 | 0 | u.i.ay = p0.y + p2.y - 2 * p1.y; |
1164 | 0 | u.i.bx = p1.x - p0.x; |
1165 | 0 | u.i.by = p1.y - p0.y; |
1166 | |
|
1167 | 0 | a = _mm_load_si128( &u.vec.a ); |
1168 | 0 | b = _mm_load_si128( &u.vec.b ); |
1169 | |
|
1170 | 0 | r = _mm_slli_epi64( a, 33 - 2 * shift ); |
1171 | 0 | q = _mm_slli_epi64( b, 33 - shift ); |
1172 | 0 | q2 = _mm_slli_epi64( a, 32 - 2 * shift ); |
1173 | |
|
1174 | 0 | q = _mm_add_epi64( q2, q ); |
1175 | |
|
1176 | 0 | v.i.px_lo = 0; |
1177 | 0 | v.i.px_hi = p0.x; |
1178 | 0 | v.i.py_lo = 0; |
1179 | 0 | v.i.py_hi = p0.y; |
1180 | |
|
1181 | 0 | p = _mm_load_si128( &v.vec ); |
1182 | |
|
1183 | 0 | for ( count = ( 1U << shift ); count > 0; count-- ) |
1184 | 0 | { |
1185 | 0 | p = _mm_add_epi64( p, q ); |
1186 | 0 | q = _mm_add_epi64( q, r ); |
1187 | |
|
1188 | 0 | _mm_store_si128( &v.vec, p ); |
1189 | |
|
1190 | 0 | gray_render_line( RAS_VAR_ v.i.px_hi, v.i.py_hi ); |
1191 | 0 | } |
1192 | |
|
1193 | 0 | return; |
1194 | 0 | } |
1195 | 0 | #endif /* __SSE2__ */ |
1196 | | |
1197 | 0 | ax = p0.x + p2.x - 2 * p1.x; |
1198 | 0 | ay = p0.y + p2.y - 2 * p1.y; |
1199 | 0 | bx = p1.x - p0.x; |
1200 | 0 | by = p1.y - p0.y; |
1201 | |
|
1202 | 0 | rx = LEFT_SHIFT( ax, 33 - 2 * shift ); |
1203 | 0 | ry = LEFT_SHIFT( ay, 33 - 2 * shift ); |
1204 | |
|
1205 | 0 | qx = LEFT_SHIFT( bx, 33 - shift ) + LEFT_SHIFT( ax, 32 - 2 * shift ); |
1206 | 0 | qy = LEFT_SHIFT( by, 33 - shift ) + LEFT_SHIFT( ay, 32 - 2 * shift ); |
1207 | |
|
1208 | 0 | px = LEFT_SHIFT( p0.x, 32 ); |
1209 | 0 | py = LEFT_SHIFT( p0.y, 32 ); |
1210 | |
|
1211 | 0 | for ( count = 1U << shift; count > 0; count-- ) |
1212 | 0 | { |
1213 | 0 | px += qx; |
1214 | 0 | py += qy; |
1215 | 0 | qx += rx; |
1216 | 0 | qy += ry; |
1217 | |
|
1218 | 0 | gray_render_line( RAS_VAR_ (FT_Pos)( px >> 32 ), |
1219 | 0 | (FT_Pos)( py >> 32 ) ); |
1220 | 0 | } |
1221 | 0 | } |
1222 | | |
1223 | | #else /* !BEZIER_USE_DDA */ |
1224 | | |
1225 | | /* |
1226 | | * Note that multiple attempts to speed up the function below |
1227 | | * with SSE2 intrinsics, using various data layouts, have turned |
1228 | | * out to be slower than the non-SIMD code below. |
1229 | | */ |
1230 | | static void |
1231 | | gray_split_conic( FT_Vector* base ) |
1232 | | { |
1233 | | TPos a, b; |
1234 | | |
1235 | | |
1236 | | base[4].x = base[2].x; |
1237 | | a = base[0].x + base[1].x; |
1238 | | b = base[1].x + base[2].x; |
1239 | | base[3].x = b >> 1; |
1240 | | base[2].x = ( a + b ) >> 2; |
1241 | | base[1].x = a >> 1; |
1242 | | |
1243 | | base[4].y = base[2].y; |
1244 | | a = base[0].y + base[1].y; |
1245 | | b = base[1].y + base[2].y; |
1246 | | base[3].y = b >> 1; |
1247 | | base[2].y = ( a + b ) >> 2; |
1248 | | base[1].y = a >> 1; |
1249 | | } |
1250 | | |
1251 | | |
1252 | | static void |
1253 | | gray_render_conic( RAS_ARG_ const FT_Vector* control, |
1254 | | const FT_Vector* to ) |
1255 | | { |
1256 | | FT_Vector bez_stack[16 * 2 + 1]; /* enough to accommodate bisections */ |
1257 | | FT_Vector* arc = bez_stack; |
1258 | | TPos dx, dy; |
1259 | | int draw; |
1260 | | |
1261 | | |
1262 | | arc[0].x = UPSCALE( to->x ); |
1263 | | arc[0].y = UPSCALE( to->y ); |
1264 | | arc[1].x = UPSCALE( control->x ); |
1265 | | arc[1].y = UPSCALE( control->y ); |
1266 | | arc[2].x = ras.x; |
1267 | | arc[2].y = ras.y; |
1268 | | |
1269 | | /* short-cut the arc that crosses the current band */ |
1270 | | if ( ( TRUNC( arc[0].y ) >= ras.max_ey && |
1271 | | TRUNC( arc[1].y ) >= ras.max_ey && |
1272 | | TRUNC( arc[2].y ) >= ras.max_ey ) || |
1273 | | ( TRUNC( arc[0].y ) < ras.min_ey && |
1274 | | TRUNC( arc[1].y ) < ras.min_ey && |
1275 | | TRUNC( arc[2].y ) < ras.min_ey ) ) |
1276 | | { |
1277 | | ras.x = arc[0].x; |
1278 | | ras.y = arc[0].y; |
1279 | | return; |
1280 | | } |
1281 | | |
1282 | | dx = FT_ABS( arc[2].x + arc[0].x - 2 * arc[1].x ); |
1283 | | dy = FT_ABS( arc[2].y + arc[0].y - 2 * arc[1].y ); |
1284 | | if ( dx < dy ) |
1285 | | dx = dy; |
1286 | | |
1287 | | /* We can calculate the number of necessary bisections because */ |
1288 | | /* each bisection predictably reduces deviation exactly 4-fold. */ |
1289 | | /* Even 32-bit deviation would vanish after 16 bisections. */ |
1290 | | draw = 1; |
1291 | | while ( dx > ONE_PIXEL / 4 ) |
1292 | | { |
1293 | | dx >>= 2; |
1294 | | draw <<= 1; |
1295 | | } |
1296 | | |
1297 | | /* We use decrement counter to count the total number of segments */ |
1298 | | /* to draw starting from 2^level. Before each draw we split as */ |
1299 | | /* many times as there are trailing zeros in the counter. */ |
1300 | | do |
1301 | | { |
1302 | | int split = draw & ( -draw ); /* isolate the rightmost 1-bit */ |
1303 | | |
1304 | | |
1305 | | while ( ( split >>= 1 ) ) |
1306 | | { |
1307 | | gray_split_conic( arc ); |
1308 | | arc += 2; |
1309 | | } |
1310 | | |
1311 | | gray_render_line( RAS_VAR_ arc[0].x, arc[0].y ); |
1312 | | arc -= 2; |
1313 | | |
1314 | | } while ( --draw ); |
1315 | | } |
1316 | | |
1317 | | #endif /* !BEZIER_USE_DDA */ |
1318 | | |
1319 | | |
1320 | | /* |
1321 | | * For cubic Bézier, binary splits are still faster than DDA |
1322 | | * because the splits are adaptive to how quickly each sub-arc |
1323 | | * approaches their chord trisection points. |
1324 | | * |
1325 | | * It might be useful to experiment with SSE2 to speed up |
1326 | | * `gray_split_cubic`, though. |
1327 | | */ |
1328 | | static void |
1329 | | gray_split_cubic( FT_Vector* base ) |
1330 | 0 | { |
1331 | 0 | TPos a, b, c; |
1332 | | |
1333 | |
|
1334 | 0 | base[6].x = base[3].x; |
1335 | 0 | a = base[0].x + base[1].x; |
1336 | 0 | b = base[1].x + base[2].x; |
1337 | 0 | c = base[2].x + base[3].x; |
1338 | 0 | base[5].x = c >> 1; |
1339 | 0 | c += b; |
1340 | 0 | base[4].x = c >> 2; |
1341 | 0 | base[1].x = a >> 1; |
1342 | 0 | a += b; |
1343 | 0 | base[2].x = a >> 2; |
1344 | 0 | base[3].x = ( a + c ) >> 3; |
1345 | |
|
1346 | 0 | base[6].y = base[3].y; |
1347 | 0 | a = base[0].y + base[1].y; |
1348 | 0 | b = base[1].y + base[2].y; |
1349 | 0 | c = base[2].y + base[3].y; |
1350 | 0 | base[5].y = c >> 1; |
1351 | 0 | c += b; |
1352 | 0 | base[4].y = c >> 2; |
1353 | 0 | base[1].y = a >> 1; |
1354 | 0 | a += b; |
1355 | 0 | base[2].y = a >> 2; |
1356 | 0 | base[3].y = ( a + c ) >> 3; |
1357 | 0 | } |
1358 | | |
1359 | | |
1360 | | static void |
1361 | | gray_render_cubic( RAS_ARG_ const FT_Vector* control1, |
1362 | | const FT_Vector* control2, |
1363 | | const FT_Vector* to ) |
1364 | 0 | { |
1365 | 0 | FT_Vector bez_stack[16 * 3 + 1]; /* enough to accommodate bisections */ |
1366 | 0 | FT_Vector* arc = bez_stack; |
1367 | | |
1368 | |
|
1369 | 0 | arc[0].x = UPSCALE( to->x ); |
1370 | 0 | arc[0].y = UPSCALE( to->y ); |
1371 | 0 | arc[1].x = UPSCALE( control2->x ); |
1372 | 0 | arc[1].y = UPSCALE( control2->y ); |
1373 | 0 | arc[2].x = UPSCALE( control1->x ); |
1374 | 0 | arc[2].y = UPSCALE( control1->y ); |
1375 | 0 | arc[3].x = ras.x; |
1376 | 0 | arc[3].y = ras.y; |
1377 | | |
1378 | | /* short-cut the arc that crosses the current band */ |
1379 | 0 | if ( ( TRUNC( arc[0].y ) >= ras.max_ey && |
1380 | 0 | TRUNC( arc[1].y ) >= ras.max_ey && |
1381 | 0 | TRUNC( arc[2].y ) >= ras.max_ey && |
1382 | 0 | TRUNC( arc[3].y ) >= ras.max_ey ) || |
1383 | 0 | ( TRUNC( arc[0].y ) < ras.min_ey && |
1384 | 0 | TRUNC( arc[1].y ) < ras.min_ey && |
1385 | 0 | TRUNC( arc[2].y ) < ras.min_ey && |
1386 | 0 | TRUNC( arc[3].y ) < ras.min_ey ) ) |
1387 | 0 | { |
1388 | 0 | ras.x = arc[0].x; |
1389 | 0 | ras.y = arc[0].y; |
1390 | 0 | return; |
1391 | 0 | } |
1392 | | |
1393 | 0 | for (;;) |
1394 | 0 | { |
1395 | | /* with each split, control points quickly converge towards */ |
1396 | | /* chord trisection points and the vanishing distances below */ |
1397 | | /* indicate when the segment is flat enough to draw */ |
1398 | 0 | if ( FT_ABS( 2 * arc[0].x - 3 * arc[1].x + arc[3].x ) > ONE_PIXEL / 2 || |
1399 | 0 | FT_ABS( 2 * arc[0].y - 3 * arc[1].y + arc[3].y ) > ONE_PIXEL / 2 || |
1400 | 0 | FT_ABS( arc[0].x - 3 * arc[2].x + 2 * arc[3].x ) > ONE_PIXEL / 2 || |
1401 | 0 | FT_ABS( arc[0].y - 3 * arc[2].y + 2 * arc[3].y ) > ONE_PIXEL / 2 ) |
1402 | 0 | goto Split; |
1403 | | |
1404 | 0 | gray_render_line( RAS_VAR_ arc[0].x, arc[0].y ); |
1405 | |
|
1406 | 0 | if ( arc == bez_stack ) |
1407 | 0 | return; |
1408 | | |
1409 | 0 | arc -= 3; |
1410 | 0 | continue; |
1411 | |
|
1412 | 0 | Split: |
1413 | 0 | gray_split_cubic( arc ); |
1414 | 0 | arc += 3; |
1415 | 0 | } |
1416 | 0 | } |
1417 | | |
1418 | | |
1419 | | static int |
1420 | | gray_move_to( const FT_Vector* to, |
1421 | | gray_PWorker worker ) |
1422 | 0 | { |
1423 | 0 | TPos x, y; |
1424 | | |
1425 | | |
1426 | | /* start to a new position */ |
1427 | 0 | x = UPSCALE( to->x ); |
1428 | 0 | y = UPSCALE( to->y ); |
1429 | |
|
1430 | 0 | gray_set_cell( RAS_VAR_ TRUNC( x ), TRUNC( y ) ); |
1431 | |
|
1432 | 0 | ras.x = x; |
1433 | 0 | ras.y = y; |
1434 | 0 | return 0; |
1435 | 0 | } |
1436 | | |
1437 | | |
1438 | | static int |
1439 | | gray_line_to( const FT_Vector* to, |
1440 | | gray_PWorker worker ) |
1441 | 0 | { |
1442 | 0 | gray_render_line( RAS_VAR_ UPSCALE( to->x ), UPSCALE( to->y ) ); |
1443 | 0 | return 0; |
1444 | 0 | } |
1445 | | |
1446 | | |
1447 | | static int |
1448 | | gray_conic_to( const FT_Vector* control, |
1449 | | const FT_Vector* to, |
1450 | | gray_PWorker worker ) |
1451 | 0 | { |
1452 | 0 | gray_render_conic( RAS_VAR_ control, to ); |
1453 | 0 | return 0; |
1454 | 0 | } |
1455 | | |
1456 | | |
1457 | | static int |
1458 | | gray_cubic_to( const FT_Vector* control1, |
1459 | | const FT_Vector* control2, |
1460 | | const FT_Vector* to, |
1461 | | gray_PWorker worker ) |
1462 | 0 | { |
1463 | 0 | gray_render_cubic( RAS_VAR_ control1, control2, to ); |
1464 | 0 | return 0; |
1465 | 0 | } |
1466 | | |
1467 | | |
1468 | | static void |
1469 | | gray_sweep( RAS_ARG ) |
1470 | 0 | { |
1471 | 0 | int fill = ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL ) ? 0x100 |
1472 | 0 | : INT_MIN; |
1473 | 0 | int coverage; |
1474 | 0 | int y; |
1475 | | |
1476 | |
|
1477 | 0 | for ( y = ras.min_ey; y < ras.max_ey; y++ ) |
1478 | 0 | { |
1479 | 0 | PCell cell = ras.ycells[y - ras.min_ey]; |
1480 | 0 | TCoord x = ras.min_ex; |
1481 | 0 | TArea cover = 0; |
1482 | |
|
1483 | 0 | unsigned char* line = ras.target.origin - ras.target.pitch * y; |
1484 | | |
1485 | |
|
1486 | 0 | for ( ; !CELL_IS_NULL( cell ); cell = cell->next ) |
1487 | 0 | { |
1488 | 0 | TArea area; |
1489 | | |
1490 | |
|
1491 | 0 | if ( cover != 0 && cell->x > x ) |
1492 | 0 | { |
1493 | 0 | FT_FILL_RULE( coverage, cover, fill ); |
1494 | 0 | FT_GRAY_SET( line + x, coverage, cell->x - x ); |
1495 | 0 | } |
1496 | |
|
1497 | 0 | cover += (TArea)cell->cover * ( ONE_PIXEL * 2 ); |
1498 | 0 | area = cover - cell->area; |
1499 | |
|
1500 | 0 | if ( area != 0 && cell->x >= ras.min_ex ) |
1501 | 0 | { |
1502 | 0 | FT_FILL_RULE( coverage, area, fill ); |
1503 | 0 | line[cell->x] = (unsigned char)coverage; |
1504 | 0 | } |
1505 | |
|
1506 | 0 | x = cell->x + 1; |
1507 | 0 | } |
1508 | |
|
1509 | 0 | if ( cover != 0 ) /* only if cropped */ |
1510 | 0 | { |
1511 | 0 | FT_FILL_RULE( coverage, cover, fill ); |
1512 | 0 | FT_GRAY_SET( line + x, coverage, ras.max_ex - x ); |
1513 | 0 | } |
1514 | 0 | } |
1515 | 0 | } |
1516 | | |
1517 | | |
1518 | | static void |
1519 | | gray_sweep_direct( RAS_ARG ) |
1520 | 0 | { |
1521 | 0 | int fill = ( ras.outline.flags & FT_OUTLINE_EVEN_ODD_FILL ) ? 0x100 |
1522 | 0 | : INT_MIN; |
1523 | 0 | int coverage; |
1524 | 0 | int y; |
1525 | |
|
1526 | 0 | FT_Span span[FT_MAX_GRAY_SPANS]; |
1527 | 0 | int n = 0; |
1528 | | |
1529 | |
|
1530 | 0 | for ( y = ras.min_ey; y < ras.max_ey; y++ ) |
1531 | 0 | { |
1532 | 0 | PCell cell = ras.ycells[y - ras.min_ey]; |
1533 | 0 | TCoord x = ras.min_ex; |
1534 | 0 | TArea cover = 0; |
1535 | | |
1536 | |
|
1537 | 0 | for ( ; !CELL_IS_NULL( cell ); cell = cell->next ) |
1538 | 0 | { |
1539 | 0 | TArea area; |
1540 | | |
1541 | |
|
1542 | 0 | if ( cover != 0 && cell->x > x ) |
1543 | 0 | { |
1544 | 0 | FT_FILL_RULE( coverage, cover, fill ); |
1545 | |
|
1546 | 0 | span[n].coverage = (unsigned char)coverage; |
1547 | 0 | span[n].x = (short)x; |
1548 | 0 | span[n].len = (unsigned short)( cell->x - x ); |
1549 | |
|
1550 | 0 | if ( ++n == FT_MAX_GRAY_SPANS ) |
1551 | 0 | { |
1552 | | /* flush the span buffer and reset the count */ |
1553 | 0 | ras.render_span( y, n, span, ras.render_span_data ); |
1554 | 0 | n = 0; |
1555 | 0 | } |
1556 | 0 | } |
1557 | |
|
1558 | 0 | cover += (TArea)cell->cover * ( ONE_PIXEL * 2 ); |
1559 | 0 | area = cover - cell->area; |
1560 | |
|
1561 | 0 | if ( area != 0 && cell->x >= ras.min_ex ) |
1562 | 0 | { |
1563 | 0 | FT_FILL_RULE( coverage, area, fill ); |
1564 | |
|
1565 | 0 | span[n].coverage = (unsigned char)coverage; |
1566 | 0 | span[n].x = (short)cell->x; |
1567 | 0 | span[n].len = 1; |
1568 | |
|
1569 | 0 | if ( ++n == FT_MAX_GRAY_SPANS ) |
1570 | 0 | { |
1571 | | /* flush the span buffer and reset the count */ |
1572 | 0 | ras.render_span( y, n, span, ras.render_span_data ); |
1573 | 0 | n = 0; |
1574 | 0 | } |
1575 | 0 | } |
1576 | |
|
1577 | 0 | x = cell->x + 1; |
1578 | 0 | } |
1579 | |
|
1580 | 0 | if ( cover != 0 ) /* only if cropped */ |
1581 | 0 | { |
1582 | 0 | FT_FILL_RULE( coverage, cover, fill ); |
1583 | |
|
1584 | 0 | span[n].coverage = (unsigned char)coverage; |
1585 | 0 | span[n].x = (short)x; |
1586 | 0 | span[n].len = (unsigned short)( ras.max_ex - x ); |
1587 | |
|
1588 | 0 | ++n; |
1589 | 0 | } |
1590 | |
|
1591 | 0 | if ( n ) |
1592 | 0 | { |
1593 | | /* flush the span buffer and reset the count */ |
1594 | 0 | ras.render_span( y, n, span, ras.render_span_data ); |
1595 | 0 | n = 0; |
1596 | 0 | } |
1597 | 0 | } |
1598 | 0 | } |
1599 | | |
1600 | | |
1601 | | #ifdef STANDALONE_ |
1602 | | |
1603 | | /************************************************************************** |
1604 | | * |
1605 | | * The following functions should only compile in stand-alone mode, |
1606 | | * i.e., when building this component without the rest of FreeType. |
1607 | | * |
1608 | | */ |
1609 | | |
1610 | | /************************************************************************** |
1611 | | * |
1612 | | * @Function: |
1613 | | * FT_Outline_Decompose |
1614 | | * |
1615 | | * @Description: |
1616 | | * Walk over an outline's structure to decompose it into individual |
1617 | | * segments and Bézier arcs. This function is also able to emit |
1618 | | * `move to' and `close to' operations to indicate the start and end |
1619 | | * of new contours in the outline. |
1620 | | * |
1621 | | * @Input: |
1622 | | * outline :: |
1623 | | * A pointer to the source target. |
1624 | | * |
1625 | | * func_interface :: |
1626 | | * A table of `emitters', i.e., function pointers |
1627 | | * called during decomposition to indicate path |
1628 | | * operations. |
1629 | | * |
1630 | | * @InOut: |
1631 | | * user :: |
1632 | | * A typeless pointer which is passed to each |
1633 | | * emitter during the decomposition. It can be |
1634 | | * used to store the state during the |
1635 | | * decomposition. |
1636 | | * |
1637 | | * @Return: |
1638 | | * Error code. 0 means success. |
1639 | | */ |
1640 | | static int |
1641 | | FT_Outline_Decompose( const FT_Outline* outline, |
1642 | | const FT_Outline_Funcs* func_interface, |
1643 | | void* user ) |
1644 | | { |
1645 | | #undef SCALED |
1646 | | #define SCALED( x ) ( (x) * ( 1L << shift ) - delta ) |
1647 | | |
1648 | | FT_Vector v_last; |
1649 | | FT_Vector v_control; |
1650 | | FT_Vector v_start; |
1651 | | |
1652 | | FT_Vector* point; |
1653 | | FT_Vector* limit; |
1654 | | char* tags; |
1655 | | |
1656 | | int error; |
1657 | | |
1658 | | int n; /* index of contour in outline */ |
1659 | | int first; /* index of first point in contour */ |
1660 | | char tag; /* current point's state */ |
1661 | | |
1662 | | int shift; |
1663 | | TPos delta; |
1664 | | |
1665 | | |
1666 | | if ( !outline ) |
1667 | | return FT_THROW( Invalid_Outline ); |
1668 | | |
1669 | | if ( !func_interface ) |
1670 | | return FT_THROW( Invalid_Argument ); |
1671 | | |
1672 | | shift = func_interface->shift; |
1673 | | delta = func_interface->delta; |
1674 | | first = 0; |
1675 | | |
1676 | | for ( n = 0; n < outline->n_contours; n++ ) |
1677 | | { |
1678 | | int last; /* index of last point in contour */ |
1679 | | |
1680 | | |
1681 | | FT_TRACE5(( "FT_Outline_Decompose: Outline %d\n", n )); |
1682 | | |
1683 | | last = outline->contours[n]; |
1684 | | if ( last < 0 ) |
1685 | | goto Invalid_Outline; |
1686 | | limit = outline->points + last; |
1687 | | |
1688 | | v_start = outline->points[first]; |
1689 | | v_start.x = SCALED( v_start.x ); |
1690 | | v_start.y = SCALED( v_start.y ); |
1691 | | |
1692 | | v_last = outline->points[last]; |
1693 | | v_last.x = SCALED( v_last.x ); |
1694 | | v_last.y = SCALED( v_last.y ); |
1695 | | |
1696 | | v_control = v_start; |
1697 | | |
1698 | | point = outline->points + first; |
1699 | | tags = outline->tags + first; |
1700 | | tag = FT_CURVE_TAG( tags[0] ); |
1701 | | |
1702 | | /* A contour cannot start with a cubic control point! */ |
1703 | | if ( tag == FT_CURVE_TAG_CUBIC ) |
1704 | | goto Invalid_Outline; |
1705 | | |
1706 | | /* check first point to determine origin */ |
1707 | | if ( tag == FT_CURVE_TAG_CONIC ) |
1708 | | { |
1709 | | /* first point is conic control. Yes, this happens. */ |
1710 | | if ( FT_CURVE_TAG( outline->tags[last] ) == FT_CURVE_TAG_ON ) |
1711 | | { |
1712 | | /* start at last point if it is on the curve */ |
1713 | | v_start = v_last; |
1714 | | limit--; |
1715 | | } |
1716 | | else |
1717 | | { |
1718 | | /* if both first and last points are conic, */ |
1719 | | /* start at their middle and record its position */ |
1720 | | /* for closure */ |
1721 | | v_start.x = ( v_start.x + v_last.x ) / 2; |
1722 | | v_start.y = ( v_start.y + v_last.y ) / 2; |
1723 | | |
1724 | | v_last = v_start; |
1725 | | } |
1726 | | point--; |
1727 | | tags--; |
1728 | | } |
1729 | | |
1730 | | FT_TRACE5(( " move to (%.2f, %.2f)\n", |
1731 | | v_start.x / 64.0, v_start.y / 64.0 )); |
1732 | | error = func_interface->move_to( &v_start, user ); |
1733 | | if ( error ) |
1734 | | goto Exit; |
1735 | | |
1736 | | while ( point < limit ) |
1737 | | { |
1738 | | point++; |
1739 | | tags++; |
1740 | | |
1741 | | tag = FT_CURVE_TAG( tags[0] ); |
1742 | | switch ( tag ) |
1743 | | { |
1744 | | case FT_CURVE_TAG_ON: /* emit a single line_to */ |
1745 | | { |
1746 | | FT_Vector vec; |
1747 | | |
1748 | | |
1749 | | vec.x = SCALED( point->x ); |
1750 | | vec.y = SCALED( point->y ); |
1751 | | |
1752 | | FT_TRACE5(( " line to (%.2f, %.2f)\n", |
1753 | | vec.x / 64.0, vec.y / 64.0 )); |
1754 | | error = func_interface->line_to( &vec, user ); |
1755 | | if ( error ) |
1756 | | goto Exit; |
1757 | | continue; |
1758 | | } |
1759 | | |
1760 | | case FT_CURVE_TAG_CONIC: /* consume conic arcs */ |
1761 | | v_control.x = SCALED( point->x ); |
1762 | | v_control.y = SCALED( point->y ); |
1763 | | |
1764 | | Do_Conic: |
1765 | | if ( point < limit ) |
1766 | | { |
1767 | | FT_Vector vec; |
1768 | | FT_Vector v_middle; |
1769 | | |
1770 | | |
1771 | | point++; |
1772 | | tags++; |
1773 | | tag = FT_CURVE_TAG( tags[0] ); |
1774 | | |
1775 | | vec.x = SCALED( point->x ); |
1776 | | vec.y = SCALED( point->y ); |
1777 | | |
1778 | | if ( tag == FT_CURVE_TAG_ON ) |
1779 | | { |
1780 | | FT_TRACE5(( " conic to (%.2f, %.2f)" |
1781 | | " with control (%.2f, %.2f)\n", |
1782 | | vec.x / 64.0, vec.y / 64.0, |
1783 | | v_control.x / 64.0, v_control.y / 64.0 )); |
1784 | | error = func_interface->conic_to( &v_control, &vec, user ); |
1785 | | if ( error ) |
1786 | | goto Exit; |
1787 | | continue; |
1788 | | } |
1789 | | |
1790 | | if ( tag != FT_CURVE_TAG_CONIC ) |
1791 | | goto Invalid_Outline; |
1792 | | |
1793 | | v_middle.x = ( v_control.x + vec.x ) / 2; |
1794 | | v_middle.y = ( v_control.y + vec.y ) / 2; |
1795 | | |
1796 | | FT_TRACE5(( " conic to (%.2f, %.2f)" |
1797 | | " with control (%.2f, %.2f)\n", |
1798 | | v_middle.x / 64.0, v_middle.y / 64.0, |
1799 | | v_control.x / 64.0, v_control.y / 64.0 )); |
1800 | | error = func_interface->conic_to( &v_control, &v_middle, user ); |
1801 | | if ( error ) |
1802 | | goto Exit; |
1803 | | |
1804 | | v_control = vec; |
1805 | | goto Do_Conic; |
1806 | | } |
1807 | | |
1808 | | FT_TRACE5(( " conic to (%.2f, %.2f)" |
1809 | | " with control (%.2f, %.2f)\n", |
1810 | | v_start.x / 64.0, v_start.y / 64.0, |
1811 | | v_control.x / 64.0, v_control.y / 64.0 )); |
1812 | | error = func_interface->conic_to( &v_control, &v_start, user ); |
1813 | | goto Close; |
1814 | | |
1815 | | default: /* FT_CURVE_TAG_CUBIC */ |
1816 | | { |
1817 | | FT_Vector vec1, vec2; |
1818 | | |
1819 | | |
1820 | | if ( point + 1 > limit || |
1821 | | FT_CURVE_TAG( tags[1] ) != FT_CURVE_TAG_CUBIC ) |
1822 | | goto Invalid_Outline; |
1823 | | |
1824 | | point += 2; |
1825 | | tags += 2; |
1826 | | |
1827 | | vec1.x = SCALED( point[-2].x ); |
1828 | | vec1.y = SCALED( point[-2].y ); |
1829 | | |
1830 | | vec2.x = SCALED( point[-1].x ); |
1831 | | vec2.y = SCALED( point[-1].y ); |
1832 | | |
1833 | | if ( point <= limit ) |
1834 | | { |
1835 | | FT_Vector vec; |
1836 | | |
1837 | | |
1838 | | vec.x = SCALED( point->x ); |
1839 | | vec.y = SCALED( point->y ); |
1840 | | |
1841 | | FT_TRACE5(( " cubic to (%.2f, %.2f)" |
1842 | | " with controls (%.2f, %.2f) and (%.2f, %.2f)\n", |
1843 | | vec.x / 64.0, vec.y / 64.0, |
1844 | | vec1.x / 64.0, vec1.y / 64.0, |
1845 | | vec2.x / 64.0, vec2.y / 64.0 )); |
1846 | | error = func_interface->cubic_to( &vec1, &vec2, &vec, user ); |
1847 | | if ( error ) |
1848 | | goto Exit; |
1849 | | continue; |
1850 | | } |
1851 | | |
1852 | | FT_TRACE5(( " cubic to (%.2f, %.2f)" |
1853 | | " with controls (%.2f, %.2f) and (%.2f, %.2f)\n", |
1854 | | v_start.x / 64.0, v_start.y / 64.0, |
1855 | | vec1.x / 64.0, vec1.y / 64.0, |
1856 | | vec2.x / 64.0, vec2.y / 64.0 )); |
1857 | | error = func_interface->cubic_to( &vec1, &vec2, &v_start, user ); |
1858 | | goto Close; |
1859 | | } |
1860 | | } |
1861 | | } |
1862 | | |
1863 | | /* close the contour with a line segment */ |
1864 | | FT_TRACE5(( " line to (%.2f, %.2f)\n", |
1865 | | v_start.x / 64.0, v_start.y / 64.0 )); |
1866 | | error = func_interface->line_to( &v_start, user ); |
1867 | | |
1868 | | Close: |
1869 | | if ( error ) |
1870 | | goto Exit; |
1871 | | |
1872 | | first = last + 1; |
1873 | | } |
1874 | | |
1875 | | FT_TRACE5(( "FT_Outline_Decompose: Done\n", n )); |
1876 | | return Smooth_Err_Ok; |
1877 | | |
1878 | | Exit: |
1879 | | FT_TRACE5(( "FT_Outline_Decompose: Error 0x%x\n", error )); |
1880 | | return error; |
1881 | | |
1882 | | Invalid_Outline: |
1883 | | return FT_THROW( Invalid_Outline ); |
1884 | | } |
1885 | | |
1886 | | #endif /* STANDALONE_ */ |
1887 | | |
1888 | | |
1889 | | FT_DEFINE_OUTLINE_FUNCS( |
1890 | | func_interface, |
1891 | | |
1892 | | (FT_Outline_MoveTo_Func) gray_move_to, /* move_to */ |
1893 | | (FT_Outline_LineTo_Func) gray_line_to, /* line_to */ |
1894 | | (FT_Outline_ConicTo_Func)gray_conic_to, /* conic_to */ |
1895 | | (FT_Outline_CubicTo_Func)gray_cubic_to, /* cubic_to */ |
1896 | | |
1897 | | 0, /* shift */ |
1898 | | 0 /* delta */ |
1899 | | ) |
1900 | | |
1901 | | |
1902 | | static int |
1903 | | gray_convert_glyph_inner( RAS_ARG, |
1904 | | int continued ) |
1905 | 0 | { |
1906 | 0 | int error; |
1907 | | |
1908 | |
|
1909 | 0 | if ( ft_setjmp( ras.jump_buffer ) == 0 ) |
1910 | 0 | { |
1911 | 0 | if ( continued ) |
1912 | 0 | FT_Trace_Disable(); |
1913 | 0 | error = FT_Outline_Decompose( &ras.outline, &func_interface, &ras ); |
1914 | 0 | if ( continued ) |
1915 | 0 | FT_Trace_Enable(); |
1916 | |
|
1917 | 0 | FT_TRACE7(( "band [%d..%d]: %ld cell%s\n", |
1918 | 0 | ras.min_ey, |
1919 | 0 | ras.max_ey, |
1920 | 0 | ras.cell_free - ras.cells, |
1921 | 0 | ras.cell_free - ras.cells == 1 ? "" : "s" )); |
1922 | 0 | } |
1923 | 0 | else |
1924 | 0 | { |
1925 | 0 | error = FT_THROW( Raster_Overflow ); |
1926 | |
|
1927 | 0 | FT_TRACE7(( "band [%d..%d]: to be bisected\n", |
1928 | 0 | ras.min_ey, ras.max_ey )); |
1929 | 0 | } |
1930 | |
|
1931 | 0 | return error; |
1932 | 0 | } |
1933 | | |
1934 | | |
1935 | | static int |
1936 | | gray_convert_glyph( RAS_ARG ) |
1937 | 0 | { |
1938 | 0 | const TCoord yMin = ras.min_ey; |
1939 | 0 | const TCoord yMax = ras.max_ey; |
1940 | |
|
1941 | 0 | TCell buffer[FT_MAX_GRAY_POOL]; |
1942 | 0 | size_t height = (size_t)( yMax - yMin ); |
1943 | 0 | size_t n = FT_MAX_GRAY_POOL / 8; |
1944 | 0 | TCoord y; |
1945 | 0 | TCoord bands[32]; /* enough to accommodate bisections */ |
1946 | 0 | TCoord* band; |
1947 | |
|
1948 | 0 | int continued = 0; |
1949 | | |
1950 | | |
1951 | | /* set up vertical bands */ |
1952 | 0 | if ( height > n ) |
1953 | 0 | { |
1954 | | /* two divisions rounded up */ |
1955 | 0 | n = ( height + n - 1 ) / n; |
1956 | 0 | height = ( height + n - 1 ) / n; |
1957 | 0 | } |
1958 | | |
1959 | | /* memory management */ |
1960 | 0 | n = ( height * sizeof ( PCell ) + sizeof ( TCell ) - 1 ) / sizeof ( TCell ); |
1961 | |
|
1962 | 0 | ras.cells = buffer + n; |
1963 | 0 | ras.max_cells = (FT_PtrDist)( FT_MAX_GRAY_POOL - n ); |
1964 | 0 | ras.cell_limit = ras.cells + ras.max_cells; |
1965 | 0 | ras.ycells = (PCell*)buffer; |
1966 | | |
1967 | | /* Initialize the null cell at the start of the `cells` array. */ |
1968 | | /* Note that this requires `ras.cell_free` initialization to skip */ |
1969 | | /* over the first entry in the array. */ |
1970 | 0 | PCell null_cell = NULL_CELL_PTR( ras ); |
1971 | 0 | null_cell->x = CELL_MAX_X_VALUE; |
1972 | 0 | null_cell->area = 0; |
1973 | 0 | null_cell->cover = 0; |
1974 | 0 | null_cell->next = NULL;; |
1975 | |
|
1976 | 0 | for ( y = yMin; y < yMax; ) |
1977 | 0 | { |
1978 | 0 | ras.min_ey = y; |
1979 | 0 | y += height; |
1980 | 0 | ras.max_ey = FT_MIN( y, yMax ); |
1981 | |
|
1982 | 0 | band = bands; |
1983 | 0 | band[1] = ras.min_ey; |
1984 | 0 | band[0] = ras.max_ey; |
1985 | |
|
1986 | 0 | do |
1987 | 0 | { |
1988 | 0 | TCoord width = band[0] - band[1]; |
1989 | 0 | TCoord w; |
1990 | 0 | int error; |
1991 | | |
1992 | |
|
1993 | 0 | for ( w = 0; w < width; ++w ) |
1994 | 0 | ras.ycells[w] = null_cell; |
1995 | |
|
1996 | 0 | ras.cell_free = ras.cells + 1; /* NOTE: Skip over the null cell. */ |
1997 | 0 | ras.cell = null_cell; |
1998 | 0 | ras.min_ey = band[1]; |
1999 | 0 | ras.max_ey = band[0]; |
2000 | 0 | ras.count_ey = width; |
2001 | |
|
2002 | 0 | error = gray_convert_glyph_inner( RAS_VAR, continued ); |
2003 | 0 | continued = 1; |
2004 | |
|
2005 | 0 | if ( !error ) |
2006 | 0 | { |
2007 | 0 | if ( ras.render_span ) /* for FT_RASTER_FLAG_DIRECT only */ |
2008 | 0 | gray_sweep_direct( RAS_VAR ); |
2009 | 0 | else |
2010 | 0 | gray_sweep( RAS_VAR ); |
2011 | 0 | band--; |
2012 | 0 | continue; |
2013 | 0 | } |
2014 | 0 | else if ( error != Smooth_Err_Raster_Overflow ) |
2015 | 0 | return error; |
2016 | | |
2017 | | /* render pool overflow; we will reduce the render band by half */ |
2018 | 0 | width >>= 1; |
2019 | | |
2020 | | /* this should never happen even with tiny rendering pool */ |
2021 | 0 | if ( width == 0 ) |
2022 | 0 | { |
2023 | 0 | FT_TRACE7(( "gray_convert_glyph: rotten glyph\n" )); |
2024 | 0 | return FT_THROW( Raster_Overflow ); |
2025 | 0 | } |
2026 | | |
2027 | 0 | band++; |
2028 | 0 | band[1] = band[0]; |
2029 | 0 | band[0] += width; |
2030 | 0 | } while ( band >= bands ); |
2031 | 0 | } |
2032 | |
|
2033 | 0 | return Smooth_Err_Ok; |
2034 | 0 | } |
2035 | | |
2036 | | |
2037 | | static int |
2038 | | gray_raster_render( FT_Raster raster, |
2039 | | const FT_Raster_Params* params ) |
2040 | 0 | { |
2041 | 0 | const FT_Outline* outline = (const FT_Outline*)params->source; |
2042 | 0 | const FT_Bitmap* target_map = params->target; |
2043 | |
|
2044 | 0 | #ifndef FT_STATIC_RASTER |
2045 | 0 | gray_TWorker worker[1]; |
2046 | 0 | #endif |
2047 | | |
2048 | |
|
2049 | 0 | if ( !raster ) |
2050 | 0 | return FT_THROW( Invalid_Argument ); |
2051 | | |
2052 | | /* this version does not support monochrome rendering */ |
2053 | 0 | if ( !( params->flags & FT_RASTER_FLAG_AA ) ) |
2054 | 0 | return FT_THROW( Cannot_Render_Glyph ); |
2055 | | |
2056 | 0 | if ( !outline ) |
2057 | 0 | return FT_THROW( Invalid_Outline ); |
2058 | | |
2059 | | /* return immediately if the outline is empty */ |
2060 | 0 | if ( outline->n_points == 0 || outline->n_contours <= 0 ) |
2061 | 0 | return Smooth_Err_Ok; |
2062 | | |
2063 | 0 | if ( !outline->contours || !outline->points ) |
2064 | 0 | return FT_THROW( Invalid_Outline ); |
2065 | | |
2066 | 0 | if ( outline->n_points != |
2067 | 0 | outline->contours[outline->n_contours - 1] + 1 ) |
2068 | 0 | return FT_THROW( Invalid_Outline ); |
2069 | | |
2070 | 0 | ras.outline = *outline; |
2071 | |
|
2072 | 0 | if ( params->flags & FT_RASTER_FLAG_DIRECT ) |
2073 | 0 | { |
2074 | 0 | if ( !params->gray_spans ) |
2075 | 0 | return Smooth_Err_Ok; |
2076 | | |
2077 | 0 | ras.render_span = (FT_Raster_Span_Func)params->gray_spans; |
2078 | 0 | ras.render_span_data = params->user; |
2079 | |
|
2080 | 0 | ras.min_ex = params->clip_box.xMin; |
2081 | 0 | ras.min_ey = params->clip_box.yMin; |
2082 | 0 | ras.max_ex = params->clip_box.xMax; |
2083 | 0 | ras.max_ey = params->clip_box.yMax; |
2084 | 0 | } |
2085 | 0 | else |
2086 | 0 | { |
2087 | | /* if direct mode is not set, we must have a target bitmap */ |
2088 | 0 | if ( !target_map ) |
2089 | 0 | return FT_THROW( Invalid_Argument ); |
2090 | | |
2091 | | /* nothing to do */ |
2092 | 0 | if ( !target_map->width || !target_map->rows ) |
2093 | 0 | return Smooth_Err_Ok; |
2094 | | |
2095 | 0 | if ( !target_map->buffer ) |
2096 | 0 | return FT_THROW( Invalid_Argument ); |
2097 | | |
2098 | 0 | if ( target_map->pitch < 0 ) |
2099 | 0 | ras.target.origin = target_map->buffer; |
2100 | 0 | else |
2101 | 0 | ras.target.origin = target_map->buffer |
2102 | 0 | + ( target_map->rows - 1 ) * (unsigned int)target_map->pitch; |
2103 | |
|
2104 | 0 | ras.target.pitch = target_map->pitch; |
2105 | |
|
2106 | 0 | ras.render_span = (FT_Raster_Span_Func)NULL; |
2107 | 0 | ras.render_span_data = NULL; |
2108 | |
|
2109 | 0 | ras.min_ex = 0; |
2110 | 0 | ras.min_ey = 0; |
2111 | 0 | ras.max_ex = (FT_Pos)target_map->width; |
2112 | 0 | ras.max_ey = (FT_Pos)target_map->rows; |
2113 | 0 | } |
2114 | | |
2115 | | /* exit if nothing to do */ |
2116 | 0 | if ( ras.max_ex <= ras.min_ex || ras.max_ey <= ras.min_ey ) |
2117 | 0 | return Smooth_Err_Ok; |
2118 | | |
2119 | 0 | return gray_convert_glyph( RAS_VAR ); |
2120 | 0 | } |
2121 | | |
2122 | | |
2123 | | /**** RASTER OBJECT CREATION: In stand-alone mode, we simply use *****/ |
2124 | | /**** a static object. *****/ |
2125 | | |
2126 | | #ifdef STANDALONE_ |
2127 | | |
2128 | | static int |
2129 | | gray_raster_new( void* memory, |
2130 | | FT_Raster* araster ) |
2131 | | { |
2132 | | static gray_TRaster the_raster; |
2133 | | |
2134 | | FT_UNUSED( memory ); |
2135 | | |
2136 | | |
2137 | | *araster = (FT_Raster)&the_raster; |
2138 | | FT_ZERO( &the_raster ); |
2139 | | |
2140 | | return 0; |
2141 | | } |
2142 | | |
2143 | | |
2144 | | static void |
2145 | | gray_raster_done( FT_Raster raster ) |
2146 | | { |
2147 | | /* nothing */ |
2148 | | FT_UNUSED( raster ); |
2149 | | } |
2150 | | |
2151 | | #else /* !STANDALONE_ */ |
2152 | | |
2153 | | static int |
2154 | | gray_raster_new( FT_Memory memory, |
2155 | | FT_Raster* araster ) |
2156 | 5 | { |
2157 | 5 | FT_Error error; |
2158 | 5 | gray_PRaster raster = NULL; |
2159 | | |
2160 | | |
2161 | 5 | *araster = 0; |
2162 | 5 | if ( !FT_ALLOC( raster, sizeof ( gray_TRaster ) ) ) |
2163 | 5 | { |
2164 | 5 | raster->memory = memory; |
2165 | 5 | *araster = (FT_Raster)raster; |
2166 | 5 | } |
2167 | | |
2168 | 5 | return error; |
2169 | 5 | } |
2170 | | |
2171 | | |
2172 | | static void |
2173 | | gray_raster_done( FT_Raster raster ) |
2174 | 5 | { |
2175 | 5 | FT_Memory memory = (FT_Memory)((gray_PRaster)raster)->memory; |
2176 | | |
2177 | | |
2178 | 5 | FT_FREE( raster ); |
2179 | 5 | } |
2180 | | |
2181 | | #endif /* !STANDALONE_ */ |
2182 | | |
2183 | | |
2184 | | static void |
2185 | | gray_raster_reset( FT_Raster raster, |
2186 | | unsigned char* pool_base, |
2187 | | unsigned long pool_size ) |
2188 | 5 | { |
2189 | 5 | FT_UNUSED( raster ); |
2190 | 5 | FT_UNUSED( pool_base ); |
2191 | 5 | FT_UNUSED( pool_size ); |
2192 | 5 | } |
2193 | | |
2194 | | |
2195 | | static int |
2196 | | gray_raster_set_mode( FT_Raster raster, |
2197 | | unsigned long mode, |
2198 | | void* args ) |
2199 | 0 | { |
2200 | 0 | FT_UNUSED( raster ); |
2201 | 0 | FT_UNUSED( mode ); |
2202 | 0 | FT_UNUSED( args ); |
2203 | | |
2204 | |
|
2205 | 0 | return 0; /* nothing to do */ |
2206 | 0 | } |
2207 | | |
2208 | | |
2209 | | FT_DEFINE_RASTER_FUNCS( |
2210 | | ft_grays_raster, |
2211 | | |
2212 | | FT_GLYPH_FORMAT_OUTLINE, |
2213 | | |
2214 | | (FT_Raster_New_Func) gray_raster_new, /* raster_new */ |
2215 | | (FT_Raster_Reset_Func) gray_raster_reset, /* raster_reset */ |
2216 | | (FT_Raster_Set_Mode_Func)gray_raster_set_mode, /* raster_set_mode */ |
2217 | | (FT_Raster_Render_Func) gray_raster_render, /* raster_render */ |
2218 | | (FT_Raster_Done_Func) gray_raster_done /* raster_done */ |
2219 | | ) |
2220 | | |
2221 | | |
2222 | | /* END */ |
2223 | | |
2224 | | |
2225 | | /* Local Variables: */ |
2226 | | /* coding: utf-8 */ |
2227 | | /* End: */ |