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