1 /**************************************************************************** 2 ** 3 ** Copyright (C) 2016 The Qt Company Ltd. 4 ** Contact: https://www.qt.io/licensing/ 5 ** 6 ** This file is part of the QtGui module of the Qt Toolkit. 7 ** 8 ** $QT_BEGIN_LICENSE:LGPL$ 9 ** Commercial License Usage 10 ** Licensees holding valid commercial Qt licenses may use this file in 11 ** accordance with the commercial license agreement provided with the 12 ** Software or, alternatively, in accordance with the terms contained in 13 ** a written agreement between you and The Qt Company. For licensing terms 14 ** and conditions see https://www.qt.io/terms-conditions. For further 15 ** information use the contact form at https://www.qt.io/contact-us. 16 ** 17 ** GNU Lesser General Public License Usage 18 ** Alternatively, this file may be used under the terms of the GNU Lesser 19 ** General Public License version 3 as published by the Free Software 20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the 21 ** packaging of this file. Please review the following information to 22 ** ensure the GNU Lesser General Public License version 3 requirements 23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. 24 ** 25 ** GNU General Public License Usage 26 ** Alternatively, this file may be used under the terms of the GNU 27 ** General Public License version 2.0 or (at your option) the GNU General 28 ** Public license version 3 or any later version approved by the KDE Free 29 ** Qt Foundation. The licenses are as published by the Free Software 30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 31 ** included in the packaging of this file. Please review the following 32 ** information to ensure the GNU General Public License requirements will 33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and 34 ** https://www.gnu.org/licenses/gpl-3.0.html. 35 ** 36 ** $QT_END_LICENSE$ 37 ** 38 ****************************************************************************/ 39 40 /***************************************************************************/ 41 /* */ 42 /* qgrayraster.c, derived from ftgrays.c */ 43 /* */ 44 /* A new `perfect' anti-aliasing renderer (body). */ 45 /* */ 46 /* Copyright 2000-2016 by */ 47 /* David Turner, Robert Wilhelm, and Werner Lemberg. */ 48 /* */ 49 /* This file is part of the FreeType project, and may only be used, */ 50 /* modified, and distributed under the terms of the FreeType project */ 51 /* license, ../../3rdparty/freetype/docs/FTL.TXT. By continuing to use, */ 52 /* modify, or distribute this file you indicate that you have read */ 53 /* the license and understand and accept it fully. */ 54 /* */ 55 /***************************************************************************/ 56 57 /*************************************************************************/ 58 /* */ 59 /* This file can be compiled without the rest of the FreeType engine, by */ 60 /* defining the _STANDALONE_ macro when compiling it. You also need to */ 61 /* put the files `ftgrays.h' and `ftimage.h' into the current */ 62 /* compilation directory. Typically, you could do something like */ 63 /* */ 64 /* - copy `src/smooth/ftgrays.c' (this file) to your current directory */ 65 /* */ 66 /* - copy `include/freetype/ftimage.h' and `src/smooth/ftgrays.h' to the */ 67 /* same directory */ 68 /* */ 69 /* - compile `ftgrays' with the _STANDALONE_ macro defined, as in */ 70 /* */ 71 /* cc -c -D_STANDALONE_ ftgrays.c */ 72 /* */ 73 /* The renderer can be initialized with a call to */ 74 /* `qt_ft_gray_raster.raster_new'; an anti-aliased bitmap can be generated */ 75 /* with a call to `qt_ft_gray_raster.raster_render'. */ 76 /* */ 77 /* See the comments and documentation in the file `ftimage.h' for more */ 78 /* details on how the raster works. */ 79 /* */ 80 /*************************************************************************/ 81 82 /*************************************************************************/ 83 /* */ 84 /* This is a new anti-aliasing scan-converter for FreeType 2. The */ 85 /* algorithm used here is _very_ different from the one in the standard */ 86 /* `ftraster' module. Actually, `ftgrays' computes the _exact_ */ 87 /* coverage of the outline on each pixel cell. */ 88 /* */ 89 /* It is based on ideas that I initially found in Raph Levien's */ 90 /* excellent LibArt graphics library (see http://www.levien.com/libart */ 91 /* for more information, though the web pages do not tell anything */ 92 /* about the renderer; you'll have to dive into the source code to */ 93 /* understand how it works). */ 94 /* */ 95 /* Note, however, that this is a _very_ different implementation */ 96 /* compared to Raph's. Coverage information is stored in a very */ 97 /* different way, and I don't use sorted vector paths. Also, it doesn't */ 98 /* use floating point values. */ 99 /* */ 100 /* This renderer has the following advantages: */ 101 /* */ 102 /* - It doesn't need an intermediate bitmap. Instead, one can supply a */ 103 /* callback function that will be called by the renderer to draw gray */ 104 /* spans on any target surface. You can thus do direct composition on */ 105 /* any kind of bitmap, provided that you give the renderer the right */ 106 /* callback. */ 107 /* */ 108 /* - A perfect anti-aliaser, i.e., it computes the _exact_ coverage on */ 109 /* each pixel cell. */ 110 /* */ 111 /* - It performs a single pass on the outline (the `standard' FT2 */ 112 /* renderer makes two passes). */ 113 /* */ 114 /* - It can easily be modified to render to _any_ number of gray levels */ 115 /* cheaply. */ 116 /* */ 117 /* - For small (< 20) pixel sizes, it is faster than the standard */ 118 /* renderer. */ 119 /* */ 120 /*************************************************************************/ 121 122 /*************************************************************************/ 123 /* */ 124 /* The macro QT_FT_COMPONENT is used in trace mode. It is an implicit */ 125 /* parameter of the QT_FT_TRACE() and QT_FT_ERROR() macros, used to print/log */ 126 /* messages during execution. */ 127 /* */ 128 #undef QT_FT_COMPONENT 129 #define QT_FT_COMPONENT trace_smooth 130 131 132 /* Auxiliary macros for token concatenation. */ 133 #define QT_FT_ERR_XCAT( x, y ) x ## y 134 #define QT_FT_ERR_CAT( x, y ) QT_FT_ERR_XCAT( x, y ) 135 136 #define QT_FT_BEGIN_STMNT do { 137 #define QT_FT_END_STMNT } while ( 0 ) 138 139 #define QT_FT_MAX( a, b ) ( (a) > (b) ? (a) : (b) ) 140 #define QT_FT_ABS( a ) ( (a) < 0 ? -(a) : (a) ) 141 142 143 /* 144 * Approximate sqrt(x*x+y*y) using the `alpha max plus beta min' 145 * algorithm. We use alpha = 1, beta = 3/8, giving us results with a 146 * largest error less than 7% compared to the exact value. 147 */ 148 #define QT_FT_HYPOT( x, y ) \ 149 ( x = QT_FT_ABS( x ), \ 150 y = QT_FT_ABS( y ), \ 151 x > y ? x + ( 3 * y >> 3 ) \ 152 : y + ( 3 * x >> 3 ) ) 153 154 #define ErrRaster_MemoryOverflow -4 155 156 #if defined(VXWORKS) 157 # include <vxWorksCommon.h> /* needed for setjmp.h */ 158 #endif 159 #include <string.h> /* for qt_ft_memcpy() */ 160 #include <setjmp.h> 161 #include <limits.h> 162 163 #define QT_FT_UINT_MAX UINT_MAX 164 165 #define qt_ft_memset memset 166 167 #define qt_ft_setjmp setjmp 168 #define qt_ft_longjmp longjmp 169 #define qt_ft_jmp_buf jmp_buf 170 171 #include <stddef.h> 172 typedef ptrdiff_t QT_FT_PtrDist; 173 174 #define ErrRaster_Invalid_Mode -2 175 #define ErrRaster_Invalid_Outline -1 176 #define ErrRaster_Invalid_Argument -3 177 #define ErrRaster_Memory_Overflow -4 178 #define ErrRaster_OutOfMemory -6 179 180 #define QT_FT_BEGIN_HEADER 181 #define QT_FT_END_HEADER 182 183 #include <private/qrasterdefs_p.h> 184 #include <private/qgrayraster_p.h> 185 186 #include <qcompilerdetection.h> 187 188 #include <stdlib.h> 189 #include <stdio.h> 190 191 #define QT_FT_UNUSED( x ) (void) x 192 193 #define QT_FT_TRACE5( x ) do { } while ( 0 ) /* nothing */ 194 #define QT_FT_TRACE7( x ) do { } while ( 0 ) /* nothing */ 195 #define QT_FT_ERROR( x ) do { } while ( 0 ) /* nothing */ 196 #define QT_FT_THROW( e ) QT_FT_ERR_CAT( ErrRaster_, e ) 197 198 #ifndef QT_FT_MEM_SET 199 #define QT_FT_MEM_SET( d, s, c ) qt_ft_memset( d, s, c ) 200 #endif 201 202 #ifndef QT_FT_MEM_ZERO 203 #define QT_FT_MEM_ZERO( dest, count ) QT_FT_MEM_SET( dest, 0, count ) 204 #endif 205 206 207 #define RAS_ARG PWorker worker 208 #define RAS_ARG_ PWorker worker, 209 210 #define RAS_VAR worker 211 #define RAS_VAR_ worker, 212 213 #define ras (*worker) 214 215 /* must be at least 6 bits! */ 216 #define PIXEL_BITS 8 217 218 #define ONE_PIXEL ( 1L << PIXEL_BITS ) 219 #define TRUNC( x ) ( (TCoord)( (x) >> PIXEL_BITS ) ) 220 #define SUBPIXELS( x ) ( (TPos)(x) * ONE_PIXEL ) 221 #define FLOOR( x ) ( (x) & -ONE_PIXEL ) 222 #define CEILING( x ) ( ( (x) + ONE_PIXEL - 1 ) & -ONE_PIXEL ) 223 #define ROUND( x ) ( ( (x) + ONE_PIXEL / 2 ) & -ONE_PIXEL ) 224 225 #if PIXEL_BITS >= 6 226 #define UPSCALE( x ) ( (x) * ( ONE_PIXEL >> 6 ) ) 227 #define DOWNSCALE( x ) ( (x) >> ( PIXEL_BITS - 6 ) ) 228 #else 229 #define UPSCALE( x ) ( (x) >> ( 6 - PIXEL_BITS ) ) 230 #define DOWNSCALE( x ) ( (x) * ( 64 >> PIXEL_BITS ) ) 231 #endif 232 233 /* Compute `dividend / divisor' and return both its quotient and */ 234 /* remainder, cast to a specific type. This macro also ensures that */ 235 /* the remainder is always positive. */ 236 #define QT_FT_DIV_MOD( type, dividend, divisor, quotient, remainder ) \ 237 QT_FT_BEGIN_STMNT \ 238 (quotient) = (type)( (dividend) / (divisor) ); \ 239 (remainder) = (type)( (dividend) % (divisor) ); \ 240 if ( (remainder) < 0 ) \ 241 { \ 242 (quotient)--; \ 243 (remainder) += (type)(divisor); \ 244 } \ 245 QT_FT_END_STMNT 246 247 /* These macros speed up repetitive divisions by replacing them */ 248 /* with multiplications and right shifts. */ 249 #define QT_FT_UDIVPREP( b ) \ 250 long b ## _r = (long)( ULONG_MAX >> PIXEL_BITS ) / ( b ) 251 #define QT_FT_UDIV( a, b ) \ 252 ( ( (unsigned long)( a ) * (unsigned long)( b ## _r ) ) >> \ 253 ( sizeof( long ) * CHAR_BIT - PIXEL_BITS ) ) 254 255 256 /*************************************************************************/ 257 /* */ 258 /* TYPE DEFINITIONS */ 259 /* */ 260 261 /* don't change the following types to QT_FT_Int or QT_FT_Pos, since we might */ 262 /* need to define them to "float" or "double" when experimenting with */ 263 /* new algorithms */ 264 265 typedef long TCoord; /* integer scanline/pixel coordinate */ 266 typedef long TPos; /* sub-pixel coordinate */ 267 typedef long TArea ; /* cell areas, coordinate products */ 268 269 /* maximal number of gray spans in a call to the span callback */ 270 #define QT_FT_MAX_GRAY_SPANS 256 271 272 273 typedef struct TCell_* PCell; 274 275 typedef struct TCell_ 276 { 277 int x; 278 int cover; 279 TArea area; 280 PCell next; 281 282 } TCell; 283 284 285 typedef struct TWorker_ 286 { 287 TCoord ex, ey; 288 TPos min_ex, max_ex; 289 TPos min_ey, max_ey; 290 TPos count_ex, count_ey; 291 292 TArea area; 293 int cover; 294 int invalid; 295 296 PCell cells; 297 QT_FT_PtrDist max_cells; 298 QT_FT_PtrDist num_cells; 299 300 TPos x, y; 301 302 QT_FT_Outline outline; 303 QT_FT_Bitmap target; 304 QT_FT_BBox clip_box; 305 306 QT_FT_Span gray_spans[QT_FT_MAX_GRAY_SPANS]; 307 int num_gray_spans; 308 309 QT_FT_Raster_Span_Func render_span; 310 void* render_span_data; 311 312 int band_size; 313 int band_shoot; 314 315 qt_ft_jmp_buf jump_buffer; 316 317 void* buffer; 318 long buffer_size; 319 320 PCell* ycells; 321 TPos ycount; 322 323 int skip_spans; 324 } TWorker, *PWorker; 325 326 327 typedef struct TRaster_ 328 { 329 void* buffer; 330 long buffer_size; 331 long buffer_allocated_size; 332 int band_size; 333 void* memory; 334 PWorker worker; 335 336 } TRaster, *PRaster; 337 q_gray_rendered_spans(TRaster * raster)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 gray_init_cells(RAS_ARG_ void * buffer,long byte_size)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 gray_compute_cbox(RAS_ARG)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 gray_find_cell(RAS_ARG)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 gray_record_cell(RAS_ARG)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 gray_set_cell(RAS_ARG_ TCoord ex,TCoord ey)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 gray_start_cell(RAS_ARG_ TCoord ex,TCoord ey)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 gray_render_scanline(RAS_ARG_ TCoord ey,TPos x1,TCoord y1,TPos x2,TCoord y2)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 gray_render_line(RAS_ARG_ TPos to_x,TPos to_y)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 gray_render_line(RAS_ARG_ TPos to_x,TPos to_y)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 gray_split_conic(QT_FT_Vector * base)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 gray_render_conic(RAS_ARG_ const QT_FT_Vector * control,const QT_FT_Vector * to)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 gray_split_cubic(QT_FT_Vector * base)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 gray_render_cubic(RAS_ARG_ const QT_FT_Vector * control1,const QT_FT_Vector * control2,const QT_FT_Vector * to)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 gray_move_to(const QT_FT_Vector * to,PWorker worker)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 gray_render_span(int count,const QT_FT_Span * spans,PWorker worker)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 gray_hline(RAS_ARG_ TCoord x,TCoord y,TPos area,int acount)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 */ gray_dump_cells(RAS_ARG)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 gray_sweep(RAS_ARG_ const QT_FT_Bitmap * target)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 QT_FT_Outline_Decompose(const QT_FT_Outline * outline,void * user)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 gray_convert_glyph_inner(RAS_ARG)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 gray_convert_glyph(RAS_ARG)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 gray_raster_render(QT_FT_Raster raster,const QT_FT_Raster_Params * params)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 gray_raster_new(QT_FT_Raster * araster)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 gray_raster_done(QT_FT_Raster raster)1947 gray_raster_done( QT_FT_Raster raster ) 1948 { 1949 free(raster); 1950 } 1951 1952 1953 static void gray_raster_reset(QT_FT_Raster raster,char * pool_base,long pool_size)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