1
2 //----------------------------------------------------------------------------
3 // XYQ: 2006-01-22 Copied from AGG project.
4 // This file uses only integer data, so it's suitable for all platforms.
5 //----------------------------------------------------------------------------
6 //----------------------------------------------------------------------------
7 // Anti-Grain Geometry - Version 2.3
8 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
9 //
10 // Permission to copy, use, modify, sell and distribute this software
11 // is granted provided this copyright notice appears in all copies.
12 // This software is provided "as is" without express or implied
13 // warranty, and with no claim as to its suitability for any purpose.
14 //
15 //----------------------------------------------------------------------------
16 //
17 // The author gratefully acknowleges the support of David Turner,
18 // Robert Wilhelm, and Werner Lemberg - the authors of the FreeType
19 // libray - in producing this work. See http://www.freetype.org for details.
20 //
21 //----------------------------------------------------------------------------
22 // Contact: mcseem@antigrain.com
23 // mcseemagg@yahoo.com
24 // http://www.antigrain.com
25 //----------------------------------------------------------------------------
26 //
27 // Adaptation for 32-bit screen coordinates has been sponsored by
28 // Liberty Technology Systems, Inc., visit http://lib-sys.com
29 //
30 // Liberty Technology Systems, Inc. is the provider of
31 // PostScript and PDF technology for software developers.
32 //
33 //----------------------------------------------------------------------------
34 //
35 // Class outline_aa - implementation.
36 //
37 // Initially the rendering algorithm was designed by David Turner and the
38 // other authors of the FreeType library - see the above notice. I nearly
39 // created a similar renderer, but still I was far from David's work.
40 // I completely redesigned the original code and adapted it for Anti-Grain
41 // ideas. Two functions - render_line and render_hline are the core of
42 // the algorithm - they calculate the exact coverage of each pixel cell
43 // of the polygon. I left these functions almost as is, because there's
44 // no way to improve the perfection - hats off to David and his group!
45 //
46 // All other code is very different from the original.
47 //
48 //----------------------------------------------------------------------------
49 #include <limits.h>
50 #include "agg_rasterizer_scanline_aa.h"
51 #include "third_party/base/numerics/safe_math.h"
52 namespace pdfium
53 {
54 namespace agg
55 {
set_cover(int c,int a)56 AGG_INLINE void cell_aa::set_cover(int c, int a)
57 {
58 cover = c;
59 area = a;
60 }
add_cover(int c,int a)61 AGG_INLINE void cell_aa::add_cover(int c, int a)
62 {
63 cover += c;
64 area += a;
65 }
set_coord(int cx,int cy)66 AGG_INLINE void cell_aa::set_coord(int cx, int cy)
67 {
68 x = cx;
69 y = cy;
70 }
set(int cx,int cy,int c,int a)71 AGG_INLINE void cell_aa::set(int cx, int cy, int c, int a)
72 {
73 x = cx;
74 y = cy;
75 cover = c;
76 area = a;
77 }
~outline_aa()78 outline_aa::~outline_aa()
79 {
80 if(m_num_blocks) {
81 cell_aa** ptr = m_cells + m_num_blocks - 1;
82 while(m_num_blocks--) {
83 FX_Free(*ptr);
84 ptr--;
85 }
86 FX_Free(m_cells);
87 }
88 }
outline_aa()89 outline_aa::outline_aa() :
90 m_num_blocks(0),
91 m_max_blocks(0),
92 m_cur_block(0),
93 m_num_cells(0),
94 m_cells(0),
95 m_cur_cell_ptr(0),
96 m_cur_x(0),
97 m_cur_y(0),
98 m_min_x(0x7FFFFFFF),
99 m_min_y(0x7FFFFFFF),
100 m_max_x(-0x7FFFFFFF),
101 m_max_y(-0x7FFFFFFF),
102 m_sorted(false)
103 {
104 m_cur_cell.set(0x7FFF, 0x7FFF, 0, 0);
105 }
reset()106 void outline_aa::reset()
107 {
108 m_num_cells = 0;
109 m_cur_block = 0;
110 m_cur_cell.set(0x7FFF, 0x7FFF, 0, 0);
111 m_sorted = false;
112 m_min_x = 0x7FFFFFFF;
113 m_min_y = 0x7FFFFFFF;
114 m_max_x = -0x7FFFFFFF;
115 m_max_y = -0x7FFFFFFF;
116 }
allocate_block()117 void outline_aa::allocate_block()
118 {
119 if(m_cur_block >= m_num_blocks) {
120 if(m_num_blocks >= m_max_blocks) {
121 cell_aa** new_cells = FX_Alloc( cell_aa*, m_max_blocks + cell_block_pool);
122 if(m_cells) {
123 memcpy(new_cells, m_cells, m_max_blocks * sizeof(cell_aa*));
124 FX_Free(m_cells);
125 }
126 m_cells = new_cells;
127 m_max_blocks += cell_block_pool;
128 }
129 m_cells[m_num_blocks++] = FX_AllocUninit(cell_aa, cell_block_size);
130 }
131 m_cur_cell_ptr = m_cells[m_cur_block++];
132 }
add_cur_cell()133 AGG_INLINE void outline_aa::add_cur_cell()
134 {
135 if(m_cur_cell.area | m_cur_cell.cover) {
136 if((m_num_cells & cell_block_mask) == 0) {
137 if(m_num_blocks >= cell_block_limit) {
138 return;
139 }
140 allocate_block();
141 }
142 *m_cur_cell_ptr++ = m_cur_cell;
143 ++m_num_cells;
144 }
145 }
set_cur_cell(int x,int y)146 AGG_INLINE void outline_aa::set_cur_cell(int x, int y)
147 {
148 if(m_cur_cell.x != x || m_cur_cell.y != y) {
149 add_cur_cell();
150 m_cur_cell.set(x, y, 0, 0);
151 if(x < m_min_x) {
152 m_min_x = x;
153 }
154 if(x > m_max_x) {
155 m_max_x = x;
156 }
157 if(y < m_min_y) {
158 m_min_y = y;
159 }
160 if(y > m_max_y) {
161 m_max_y = y;
162 }
163 }
164 }
render_hline(int ey,int x1,int y1,int x2,int y2)165 AGG_INLINE void outline_aa::render_hline(int ey, int x1, int y1, int x2, int y2)
166 {
167 int ex1 = x1 >> poly_base_shift;
168 int ex2 = x2 >> poly_base_shift;
169 int fx1 = x1 & poly_base_mask;
170 int fx2 = x2 & poly_base_mask;
171 int delta, p, first, dx;
172 int incr, lift, mod, rem;
173 if(y1 == y2) {
174 set_cur_cell(ex2, ey);
175 return;
176 }
177 if(ex1 == ex2) {
178 delta = y2 - y1;
179 m_cur_cell.add_cover(delta, (fx1 + fx2) * delta);
180 return;
181 }
182 p = (poly_base_size - fx1) * (y2 - y1);
183 first = poly_base_size;
184 incr = 1;
185 dx = x2 - x1;
186 if(dx < 0) {
187 p = fx1 * (y2 - y1);
188 first = 0;
189 incr = -1;
190 dx = -dx;
191 }
192 delta = p / dx;
193 mod = p % dx;
194 if(mod < 0) {
195 delta--;
196 mod += dx;
197 }
198 m_cur_cell.add_cover(delta, (fx1 + first) * delta);
199 ex1 += incr;
200 set_cur_cell(ex1, ey);
201 y1 += delta;
202 if(ex1 != ex2) {
203 p = poly_base_size * (y2 - y1 + delta);
204 lift = p / dx;
205 rem = p % dx;
206 if (rem < 0) {
207 lift--;
208 rem += dx;
209 }
210 mod -= dx;
211 while (ex1 != ex2) {
212 delta = lift;
213 mod += rem;
214 if(mod >= 0) {
215 mod -= dx;
216 delta++;
217 }
218 m_cur_cell.add_cover(delta, (poly_base_size) * delta);
219 y1 += delta;
220 ex1 += incr;
221 set_cur_cell(ex1, ey);
222 }
223 }
224 delta = y2 - y1;
225 m_cur_cell.add_cover(delta, (fx2 + poly_base_size - first) * delta);
226 }
render_line(int x1,int y1,int x2,int y2)227 void outline_aa::render_line(int x1, int y1, int x2, int y2)
228 {
229 enum dx_limit_e { dx_limit = 16384 << poly_base_shift };
230 pdfium::base::CheckedNumeric<int> safe_dx = x2;
231 safe_dx -= x1;
232 if (!safe_dx.IsValid())
233 return;
234
235 int dx = safe_dx.ValueOrDie();
236 if(dx >= dx_limit || dx <= -dx_limit) {
237 pdfium::base::CheckedNumeric<int> safe_cx = x1;
238 safe_cx += x2;
239 safe_cx /= 2;
240 if (!safe_cx.IsValid())
241 return;
242
243 pdfium::base::CheckedNumeric<int> safe_cy = y1;
244 safe_cy += y2;
245 safe_cy /= 2;
246 if (!safe_cy.IsValid())
247 return;
248
249 int cx = safe_cx.ValueOrDie();
250 int cy = safe_cy.ValueOrDie();
251 render_line(x1, y1, cx, cy);
252 render_line(cx, cy, x2, y2);
253 }
254 int dy = y2 - y1;
255 int ey1 = y1 >> poly_base_shift;
256 int ey2 = y2 >> poly_base_shift;
257 int fy1 = y1 & poly_base_mask;
258 int fy2 = y2 & poly_base_mask;
259 int x_from, x_to;
260 int rem, mod, lift, delta, first, incr;
261 if(ey1 == ey2) {
262 render_hline(ey1, x1, fy1, x2, fy2);
263 return;
264 }
265 incr = 1;
266 if(dx == 0) {
267 int ex = x1 >> poly_base_shift;
268 int two_fx = (x1 - (ex << poly_base_shift)) << 1;
269 int area;
270 first = poly_base_size;
271 if(dy < 0) {
272 first = 0;
273 incr = -1;
274 }
275 x_from = x1;
276 delta = first - fy1;
277 m_cur_cell.add_cover(delta, two_fx * delta);
278 ey1 += incr;
279 set_cur_cell(ex, ey1);
280 delta = first + first - poly_base_size;
281 area = two_fx * delta;
282 while(ey1 != ey2) {
283 m_cur_cell.set_cover(delta, area);
284 ey1 += incr;
285 set_cur_cell(ex, ey1);
286 }
287 delta = fy2 - poly_base_size + first;
288 m_cur_cell.add_cover(delta, two_fx * delta);
289 return;
290 }
291 pdfium::base::CheckedNumeric<int> safeP = poly_base_size - fy1;
292 safeP *= dx;
293 if (!safeP.IsValid())
294 return;
295 first = poly_base_size;
296 if(dy < 0) {
297 safeP = fy1;
298 safeP *= dx;
299 if (!safeP.IsValid())
300 return;
301 first = 0;
302 incr = -1;
303 dy = -dy;
304 }
305 delta = (safeP / dy).ValueOrDie();
306 mod = (safeP % dy).ValueOrDie();
307 if(mod < 0) {
308 delta--;
309 mod += dy;
310 }
311 x_from = x1 + delta;
312 render_hline(ey1, x1, fy1, x_from, first);
313 ey1 += incr;
314 set_cur_cell(x_from >> poly_base_shift, ey1);
315 if(ey1 != ey2) {
316 safeP = static_cast<int>(poly_base_size);
317 safeP *= dx;
318 if (!safeP.IsValid())
319 return;
320 lift = (safeP / dy).ValueOrDie();
321 rem = (safeP % dy).ValueOrDie();
322 if (rem < 0) {
323 lift--;
324 rem += dy;
325 }
326 mod -= dy;
327 while(ey1 != ey2) {
328 delta = lift;
329 mod += rem;
330 if (mod >= 0) {
331 mod -= dy;
332 delta++;
333 }
334 x_to = x_from + delta;
335 render_hline(ey1, x_from, poly_base_size - first, x_to, first);
336 x_from = x_to;
337 ey1 += incr;
338 set_cur_cell(x_from >> poly_base_shift, ey1);
339 }
340 }
341 render_hline(ey1, x_from, poly_base_size - first, x2, fy2);
342 }
move_to(int x,int y)343 void outline_aa::move_to(int x, int y)
344 {
345 if(m_sorted) {
346 reset();
347 }
348 set_cur_cell(x >> poly_base_shift, y >> poly_base_shift);
349 m_cur_x = x;
350 m_cur_y = y;
351 }
line_to(int x,int y)352 void outline_aa::line_to(int x, int y)
353 {
354 render_line(m_cur_x, m_cur_y, x, y);
355 m_cur_x = x;
356 m_cur_y = y;
357 m_sorted = false;
358 }
swap_cells(T * a,T * b)359 template <class T> static AGG_INLINE void swap_cells(T* a, T* b)
360 {
361 T temp = *a;
362 *a = *b;
363 *b = temp;
364 }
365 enum {
366 qsort_threshold = 9
367 };
qsort_cells(cell_aa ** start,unsigned num)368 static void qsort_cells(cell_aa** start, unsigned num)
369 {
370 cell_aa** stack[80];
371 cell_aa*** top;
372 cell_aa** limit;
373 cell_aa** base;
374 limit = start + num;
375 base = start;
376 top = stack;
377 for (;;) {
378 int len = int(limit - base);
379 cell_aa** i;
380 cell_aa** j;
381 cell_aa** pivot;
382 if(len > qsort_threshold) {
383 pivot = base + len / 2;
384 swap_cells(base, pivot);
385 i = base + 1;
386 j = limit - 1;
387 if((*j)->x < (*i)->x) {
388 swap_cells(i, j);
389 }
390 if((*base)->x < (*i)->x) {
391 swap_cells(base, i);
392 }
393 if((*j)->x < (*base)->x) {
394 swap_cells(base, j);
395 }
396 for(;;) {
397 int x = (*base)->x;
398 do {
399 i++;
400 } while( (*i)->x < x );
401 do {
402 j--;
403 } while( x < (*j)->x );
404 if(i > j) {
405 break;
406 }
407 swap_cells(i, j);
408 }
409 swap_cells(base, j);
410 if(j - base > limit - i) {
411 top[0] = base;
412 top[1] = j;
413 base = i;
414 } else {
415 top[0] = i;
416 top[1] = limit;
417 limit = j;
418 }
419 top += 2;
420 } else {
421 j = base;
422 i = j + 1;
423 for(; i < limit; j = i, i++) {
424 for(; j[1]->x < (*j)->x; j--) {
425 swap_cells(j + 1, j);
426 if (j == base) {
427 break;
428 }
429 }
430 }
431 if(top > stack) {
432 top -= 2;
433 base = top[0];
434 limit = top[1];
435 } else {
436 break;
437 }
438 }
439 }
440 }
sort_cells()441 void outline_aa::sort_cells()
442 {
443 if(m_sorted) {
444 return;
445 }
446 add_cur_cell();
447 if(m_num_cells == 0) {
448 return;
449 }
450 m_sorted_cells.allocate(m_num_cells, 16);
451 if (m_max_y > 0 && m_min_y < 0 && -m_min_y > INT_MAX - m_max_y) {
452 return;
453 }
454 unsigned size = m_max_y - m_min_y;
455 if (size + 1 < size) {
456 return;
457 }
458 size++;
459 m_sorted_y.allocate(size, 16);
460 m_sorted_y.zero();
461 cell_aa** block_ptr = m_cells;
462 cell_aa* cell_ptr = NULL;
463 unsigned nb = m_num_cells >> cell_block_shift;
464 unsigned i;
465 while(nb--) {
466 cell_ptr = *block_ptr++;
467 i = cell_block_size;
468 while(i--) {
469 m_sorted_y[cell_ptr->y - m_min_y].start++;
470 ++cell_ptr;
471 }
472 }
473 i = m_num_cells & cell_block_mask;
474 if (i) {
475 cell_ptr = *block_ptr++;
476 }
477 while(i--) {
478 m_sorted_y[cell_ptr->y - m_min_y].start++;
479 ++cell_ptr;
480 }
481 unsigned start = 0;
482 for(i = 0; i < m_sorted_y.size(); i++) {
483 unsigned v = m_sorted_y[i].start;
484 m_sorted_y[i].start = start;
485 start += v;
486 }
487 block_ptr = m_cells;
488 nb = m_num_cells >> cell_block_shift;
489 while(nb--) {
490 cell_ptr = *block_ptr++;
491 i = cell_block_size;
492 while(i--) {
493 sorted_y& cur_y = m_sorted_y[cell_ptr->y - m_min_y];
494 m_sorted_cells[cur_y.start + cur_y.num] = cell_ptr;
495 ++cur_y.num;
496 ++cell_ptr;
497 }
498 }
499 i = m_num_cells & cell_block_mask;
500 if (i) {
501 cell_ptr = *block_ptr++;
502 }
503 while(i--) {
504 sorted_y& cur_y = m_sorted_y[cell_ptr->y - m_min_y];
505 m_sorted_cells[cur_y.start + cur_y.num] = cell_ptr;
506 ++cur_y.num;
507 ++cell_ptr;
508 }
509 for(i = 0; i < m_sorted_y.size(); i++) {
510 const sorted_y& cur_y = m_sorted_y[i];
511 if(cur_y.num) {
512 qsort_cells(m_sorted_cells.data() + cur_y.start, cur_y.num);
513 }
514 }
515 m_sorted = true;
516 }
517 // static
calculate_area(int cover,int shift)518 int rasterizer_scanline_aa::calculate_area(int cover, int shift)
519 {
520 unsigned int result = cover;
521 result <<= shift;
522 return result;
523 }
524 // static
safe_add(int * op1,int op2)525 bool rasterizer_scanline_aa::safe_add(int* op1, int op2)
526 {
527 pdfium::base::CheckedNumeric<int> safeOp1 = *op1;
528 safeOp1 += op2;
529 if(!safeOp1.IsValid()) {
530 return false;
531 }
532
533 *op1 = safeOp1.ValueOrDie();
534 return true;
535 }
536 }
537 } // namespace pdfium
538