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