w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

cairo-mono-scan-converter.c
Go to the documentation of this file.
1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
2 /*
3  * Copyright (c) 2011 Intel Corporation
4  *
5  * Permission is hereby granted, free of charge, to any person
6  * obtaining a copy of this software and associated documentation
7  * files (the "Software"), to deal in the Software without
8  * restriction, including without limitation the rights to use,
9  * copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following
12  * conditions:
13  *
14  * The above copyright notice and this permission notice shall be
15  * included in all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24  * OTHER DEALINGS IN THE SOFTWARE.
25  */
26 #include "cairoint.h"
27 #include "cairo-spans-private.h"
28 #include "cairo-error-private.h"
29 
30 #include <stdlib.h>
31 #include <string.h>
32 #include <limits.h>
33 
34 struct quorem {
35  int32_t quo;
36  int32_t rem;
37 };
38 
39 struct edge {
40  struct edge *next, *prev;
41 
43  int32_t dir;
45 
46  int32_t dy;
47  struct quorem x;
48  struct quorem dxdy;
49 };
50 
51 /* A collection of sorted and vertically clipped edges of the polygon.
52  * Edges are moved from the polygon to an active list while scan
53  * converting. */
54 struct polygon {
55  /* The vertical clip extents. */
56  int32_t ymin, ymax;
57 
58  int num_edges;
59  struct edge *edges;
60 
61  /* Array of edges all starting in the same bucket. An edge is put
62  * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
63  * it is added to the polygon. */
64  struct edge **y_buckets;
65 
66  struct edge *y_buckets_embedded[64];
67  struct edge edges_embedded[32];
68 };
69 
70 struct mono_scan_converter {
71  struct polygon polygon[1];
72 
73  /* Leftmost edge on the current scan line. */
74  struct edge head, tail;
75  int is_vertical;
76 
79  int num_spans;
80 
81  /* Clip box. */
82  int32_t xmin, xmax;
83  int32_t ymin, ymax;
84 };
85 
86 #define I(x) _cairo_fixed_integer_round_down(x)
87 
88 /* Compute the floored division a/b. Assumes / and % perform symmetric
89  * division. */
90 inline static struct quorem
92 {
93  struct quorem qr;
94  qr.quo = a/b;
95  qr.rem = a%b;
96  if ((a^b)<0 && qr.rem) {
97  qr.quo -= 1;
98  qr.rem += b;
99  }
100  return qr;
101 }
102 
103 /* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
104  * division. */
105 static struct quorem
107 {
108  struct quorem qr;
109  long long xa = (long long)x*a;
110  qr.quo = xa/b;
111  qr.rem = xa%b;
112  if ((xa>=0) != (b>=0) && qr.rem) {
113  qr.quo -= 1;
114  qr.rem += b;
115  }
116  return qr;
117 }
118 
119 static cairo_status_t
120 polygon_init (struct polygon *polygon, int ymin, int ymax)
121 {
122  unsigned h = ymax - ymin + 1;
123 
126  polygon->y_buckets = _cairo_malloc_ab (h, sizeof (struct edge *));
127  if (unlikely (NULL == polygon->y_buckets))
129  }
130  memset (polygon->y_buckets, 0, h * sizeof (struct edge *));
131  polygon->y_buckets[h-1] = (void *)-1;
132 
133  polygon->ymin = ymin;
134  polygon->ymax = ymax;
135  return CAIRO_STATUS_SUCCESS;
136 }
137 
138 static void
140 {
143 
145  free (polygon->edges);
146 }
147 
148 static void
150  struct edge *e,
151  int y)
152 {
153  struct edge **ptail = &polygon->y_buckets[y - polygon->ymin];
154  if (*ptail)
155  (*ptail)->prev = e;
156  e->next = *ptail;
157  e->prev = NULL;
158  *ptail = e;
159 }
160 
161 inline static void
163  const cairo_edge_t *edge)
164 {
165  struct edge *e;
166  cairo_fixed_t dx;
168  int y, ytop, ybot;
169  int ymin = polygon->ymin;
170  int ymax = polygon->ymax;
171 
172  y = I(edge->top);
173  ytop = MAX(y, ymin);
174 
175  y = I(edge->bottom);
176  ybot = MIN(y, ymax);
177 
178  if (ybot <= ytop)
179  return;
180 
181  e = polygon->edges + polygon->num_edges++;
182  e->height_left = ybot - ytop;
183  e->dir = edge->dir;
184 
185  dx = edge->line.p2.x - edge->line.p1.x;
186  dy = edge->line.p2.y - edge->line.p1.y;
187 
188  if (dx == 0) {
189  e->vertical = TRUE;
190  e->x.quo = edge->line.p1.x;
191  e->x.rem = 0;
192  e->dxdy.quo = 0;
193  e->dxdy.rem = 0;
194  e->dy = 0;
195  } else {
196  e->vertical = FALSE;
197  e->dxdy = floored_muldivrem (dx, CAIRO_FIXED_ONE, dy);
198  e->dy = dy;
199 
201  dx, dy);
202  e->x.quo += edge->line.p1.x;
203  }
204  e->x.rem -= dy;
205 
207 }
208 
209 static struct edge *
210 merge_sorted_edges (struct edge *head_a, struct edge *head_b)
211 {
212  struct edge *head, **next, *prev;
213  int32_t x;
214 
215  prev = head_a->prev;
216  next = &head;
217  if (head_a->x.quo <= head_b->x.quo) {
218  head = head_a;
219  } else {
220  head = head_b;
221  head_b->prev = prev;
222  goto start_with_b;
223  }
224 
225  do {
226  x = head_b->x.quo;
227  while (head_a != NULL && head_a->x.quo <= x) {
228  prev = head_a;
229  next = &head_a->next;
230  head_a = head_a->next;
231  }
232 
233  head_b->prev = prev;
234  *next = head_b;
235  if (head_a == NULL)
236  return head;
237 
238 start_with_b:
239  x = head_a->x.quo;
240  while (head_b != NULL && head_b->x.quo <= x) {
241  prev = head_b;
242  next = &head_b->next;
243  head_b = head_b->next;
244  }
245 
246  head_a->prev = prev;
247  *next = head_a;
248  if (head_b == NULL)
249  return head;
250  } while (1);
251 }
252 
253 static struct edge *
255  unsigned int level,
256  struct edge **head_out)
257 {
258  struct edge *head_other, *remaining;
259  unsigned int i;
260 
261  head_other = list->next;
262 
263  if (head_other == NULL) {
264  *head_out = list;
265  return NULL;
266  }
267 
268  remaining = head_other->next;
269  if (list->x.quo <= head_other->x.quo) {
270  *head_out = list;
271  head_other->next = NULL;
272  } else {
273  *head_out = head_other;
274  head_other->prev = list->prev;
275  head_other->next = list;
276  list->prev = head_other;
277  list->next = NULL;
278  }
279 
280  for (i = 0; i < level && remaining; i++) {
281  remaining = sort_edges (remaining, i, &head_other);
282  *head_out = merge_sorted_edges (*head_out, head_other);
283  }
284 
285  return remaining;
286 }
287 
288 static struct edge *
289 merge_unsorted_edges (struct edge *head, struct edge *unsorted)
290 {
291  sort_edges (unsorted, UINT_MAX, &unsorted);
292  return merge_sorted_edges (head, unsorted);
293 }
294 
295 inline static void
297 {
298  struct edge *e;
299 
300  for (e = edges; c->is_vertical && e; e = e->next)
301  c->is_vertical = e->vertical;
302 
303  c->head.next = merge_unsorted_edges (c->head.next, edges);
304 }
305 
306 inline static void
307 add_span (struct mono_scan_converter *c, int x1, int x2)
308 {
309  int n;
310 
311  if (x1 < c->xmin)
312  x1 = c->xmin;
313  if (x2 > c->xmax)
314  x2 = c->xmax;
315  if (x2 <= x1)
316  return;
317 
318  n = c->num_spans++;
319  c->spans[n].x = x1;
320  c->spans[n].coverage = 255;
321 
322  n = c->num_spans++;
323  c->spans[n].x = x2;
324  c->spans[n].coverage = 0;
325 }
326 
327 inline static void
328 row (struct mono_scan_converter *c, unsigned int mask)
329 {
330  struct edge *edge = c->head.next;
331  int xstart = INT_MIN, prev_x = INT_MIN;
332  int winding = 0;
333 
334  c->num_spans = 0;
335  while (&c->tail != edge) {
336  struct edge *next = edge->next;
337  int xend = I(edge->x.quo);
338 
339  if (--edge->height_left) {
340  if (!edge->vertical) {
341  edge->x.quo += edge->dxdy.quo;
342  edge->x.rem += edge->dxdy.rem;
343  if (edge->x.rem >= 0) {
344  ++edge->x.quo;
345  edge->x.rem -= edge->dy;
346  }
347  }
348 
349  if (edge->x.quo < prev_x) {
350  struct edge *pos = edge->prev;
351  pos->next = next;
352  next->prev = pos;
353  do {
354  pos = pos->prev;
355  } while (edge->x.quo < pos->x.quo);
356  pos->next->prev = edge;
357  edge->next = pos->next;
358  edge->prev = pos;
359  pos->next = edge;
360  } else
361  prev_x = edge->x.quo;
362  } else {
363  edge->prev->next = next;
364  next->prev = edge->prev;
365  }
366 
367  winding += edge->dir;
368  if ((winding & mask) == 0) {
369  if (I(next->x.quo) > xend + 1) {
370  add_span (c, xstart, xend);
371  xstart = INT_MIN;
372  }
373  } else if (xstart == INT_MIN)
374  xstart = xend;
375 
376  edge = next;
377  }
378 }
379 
380 inline static void dec (struct edge *e, int h)
381 {
382  e->height_left -= h;
383  if (e->height_left == 0) {
384  e->prev->next = e->next;
385  e->next->prev = e->prev;
386  }
387 }
388 
389 static cairo_status_t
391  int xmin, int ymin,
392  int xmax, int ymax)
393 {
395  int max_num_spans;
396 
397  status = polygon_init (c->polygon, ymin, ymax);
398  if (unlikely (status))
399  return status;
400 
401  max_num_spans = xmax - xmin + 1;
402  if (max_num_spans > ARRAY_LENGTH(c->spans_embedded)) {
403  c->spans = _cairo_malloc_ab (max_num_spans,
404  sizeof (cairo_half_open_span_t));
405  if (unlikely (c->spans == NULL)) {
406  polygon_fini (c->polygon);
408  }
409  } else
410  c->spans = c->spans_embedded;
411 
412  c->xmin = xmin;
413  c->xmax = xmax;
414  c->ymin = ymin;
415  c->ymax = ymax;
416 
417  c->head.vertical = 1;
418  c->head.height_left = INT_MAX;
420  c->head.prev = NULL;
421  c->head.next = &c->tail;
422  c->tail.prev = &c->head;
423  c->tail.next = NULL;
425  c->tail.height_left = INT_MAX;
426  c->tail.vertical = 1;
427 
428  c->is_vertical = 1;
429  return CAIRO_STATUS_SUCCESS;
430 }
431 
432 static void
434 {
435  if (self->spans != self->spans_embedded)
436  free (self->spans);
437 
438  polygon_fini(self->polygon);
439 }
440 
441 static cairo_status_t
443  int num_edges)
444 
445 {
446  c->polygon->num_edges = 0;
447  c->polygon->edges = c->polygon->edges_embedded;
448  if (num_edges > ARRAY_LENGTH (c->polygon->edges_embedded)) {
449  c->polygon->edges = _cairo_malloc_ab (num_edges, sizeof (struct edge));
450  if (unlikely (c->polygon->edges == NULL))
452  }
453 
454  return CAIRO_STATUS_SUCCESS;
455 }
456 
457 static void
459  const cairo_edge_t *edge)
460 {
461  polygon_add_edge (c->polygon, edge);
462 }
463 
464 static void
466 {
467  struct edge *edge;
468 
469  for (edge = c->head.next; edge != &c->tail; edge = edge->next) {
470  edge->height_left -= count;
471  if (! edge->height_left) {
472  edge->prev->next = edge->next;
473  edge->next->prev = edge->prev;
474  }
475  }
476 }
477 
478 static cairo_status_t
480  unsigned int winding_mask,
481  cairo_span_renderer_t *renderer)
482 {
483  struct polygon *polygon = c->polygon;
484  int i, j, h = c->ymax - c->ymin;
486 
487  for (i = 0; i < h; i = j) {
488  j = i + 1;
489 
490  if (polygon->y_buckets[i])
492 
493  if (c->is_vertical) {
494  int min_height;
495  struct edge *e;
496 
497  e = c->head.next;
498  min_height = e->height_left;
499  while (e != &c->tail) {
500  if (e->height_left < min_height)
501  min_height = e->height_left;
502  e = e->next;
503  }
504 
505  while (--min_height >= 1 && polygon->y_buckets[j] == NULL)
506  j++;
507  if (j != i + 1)
508  step_edges (c, j - (i + 1));
509  }
510 
511  row (c, winding_mask);
512  if (c->num_spans) {
513  status = renderer->render_rows (renderer, c->ymin+i, j-i,
514  c->spans, c->num_spans);
515  if (unlikely (status))
516  return status;
517  }
518 
519  /* XXX recompute after dropping edges? */
520  if (c->head.next == &c->tail)
521  c->is_vertical = 1;
522  }
523 
524  return CAIRO_STATUS_SUCCESS;
525 }
526 
529 
530  struct mono_scan_converter converter[1];
532 };
533 
535 
536 static void
538 {
540  _mono_scan_converter_fini (self->converter);
541  free(self);
542 }
543 
546  const cairo_polygon_t *polygon)
547 {
550  int i;
551 
552 #if 0
553  FILE *file = fopen ("polygon.txt", "w");
555  fclose (file);
556 #endif
557 
558  status = mono_scan_converter_allocate_edges (self->converter,
559  polygon->num_edges);
560  if (unlikely (status))
561  return status;
562 
563  for (i = 0; i < polygon->num_edges; i++)
564  mono_scan_converter_add_edge (self->converter, &polygon->edges[i]);
565 
566  return CAIRO_STATUS_SUCCESS;
567 }
568 
569 static cairo_status_t
571  cairo_span_renderer_t *renderer)
572 {
574 
575  return mono_scan_converter_render (self->converter,
576  self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
577  renderer);
578 }
579 
582  int ymin,
583  int xmax,
584  int ymax,
586 {
589 
590  self = _cairo_malloc (sizeof(struct _cairo_mono_scan_converter));
591  if (unlikely (self == NULL)) {
593  goto bail_nomem;
594  }
595 
596  self->base.destroy = _cairo_mono_scan_converter_destroy;
597  self->base.generate = _cairo_mono_scan_converter_generate;
598 
599  status = _mono_scan_converter_init (self->converter,
600  xmin, ymin, xmax, ymax);
601  if (unlikely (status))
602  goto bail;
603 
604  self->fill_rule = fill_rule;
605 
606  return &self->base;
607 
608  bail:
609  self->base.destroy(&self->base);
610  bail_nomem:
612 }
int level
Definition: afm2pl.c:1694
#define head
Definition: aptex-macros.h:513
#define count(a)
Definition: aptex-macros.h:781
#define next(a)
Definition: aptex-macros.h:924
void _cairo_debug_print_polygon(FILE *stream, cairo_polygon_t *polygon)
Definition: cairo-debug.c:271
cairo_status_t _cairo_error(cairo_status_t status)
Definition: cairo-error.c:65
static cairo_fixed_t _cairo_fixed_from_int(int i)
#define CAIRO_FIXED_ONE
static int _cairo_fixed_integer_part(cairo_fixed_t f)
#define CAIRO_FIXED_FRAC_MASK
int32_t cairo_fixed_t
#define _cairo_malloc_ab(a, size)
#define _cairo_malloc(size)
cairo_scan_converter_t * _cairo_mono_scan_converter_create(int xmin, int ymin, int xmax, int ymax, cairo_fill_rule_t fill_rule)
cairo_status_t _cairo_mono_scan_converter_add_polygon(void *converter, const cairo_polygon_t *polygon)
cairo_scan_converter_t * _cairo_scan_converter_create_in_error(cairo_status_t error)
Definition: cairo-spans.c:81
enum _cairo_fill_rule cairo_fill_rule_t
@ CAIRO_STATUS_SUCCESS
Definition: cairo.h:315
@ CAIRO_STATUS_NO_MEMORY
Definition: cairo.h:317
enum _cairo_status cairo_status_t
@ CAIRO_FILL_RULE_WINDING
Definition: cairo.h:754
#define ARRAY_LENGTH(__array)
Definition: cairoint.h:137
static void polygon_add_edge(struct polygon *polygon, const cairo_edge_t *edge)
static struct edge * merge_sorted_edges(struct edge *head_a, struct edge *head_b)
static cairo_status_t mono_scan_converter_render(struct mono_scan_converter *c, unsigned int winding_mask, cairo_span_renderer_t *renderer)
static struct quorem floored_muldivrem(int x, int a, int b)
static cairo_status_t _mono_scan_converter_init(struct mono_scan_converter *c, int xmin, int ymin, int xmax, int ymax)
static void add_span(struct mono_scan_converter *c, int x1, int x2)
static struct edge * sort_edges(struct edge *list, unsigned int level, struct edge **head_out)
static void _cairo_mono_scan_converter_destroy(void *converter)
static cairo_status_t polygon_init(struct polygon *polygon, int ymin, int ymax)
#define I(x)
static void active_list_merge_edges(struct mono_scan_converter *c, struct edge *edges)
static cairo_status_t _cairo_mono_scan_converter_generate(void *converter, cairo_span_renderer_t *renderer)
static struct edge * merge_unsorted_edges(struct edge *head, struct edge *unsorted)
static struct quorem floored_divrem(int a, int b)
static void mono_scan_converter_add_edge(struct mono_scan_converter *c, const cairo_edge_t *edge)
static cairo_status_t mono_scan_converter_allocate_edges(struct mono_scan_converter *c, int num_edges)
static void dec(struct edge *e, int h)
static void _mono_scan_converter_fini(struct mono_scan_converter *self)
static void step_edges(struct mono_scan_converter *c, int count)
static void polygon_fini(struct polygon *polygon)
static void _polygon_insert_edge_into_its_y_bucket(struct polygon *polygon, struct edge *e, int y)
static void row(struct mono_scan_converter *c, unsigned int mask)
#define n
Definition: t4ht.c:1290
#define b
Definition: jpegint.h:372
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
#define free(a)
Definition: decNumber.cpp:310
int h
Definition: dviconv.c:9
#define fopen
Definition: xxstdio.h:21
static FIELD_PTR prev
Definition: genind.c:36
#define c(n)
Definition: gpos-common.c:150
#define a(n)
Definition: gpos-common.c:148
#define unlikely(x)
Definition: jbig2arith.cc:116
#define MIN(a, b)
Definition: jpegint.h:269
#define MAX(a, b)
Definition: jpegint.h:267
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
sizeof(AF_ModuleRec)
kerning y
Definition: ttdriver.c:212
signed int int32_t
Definition: stdint.h:77
#define INT_MIN
Definition: c-minmax.h:50
#define INT_MAX
Definition: c-minmax.h:53
#define UINT_MAX
Definition: c-minmax.h:56
#define fclose
Definition: debug.h:100
cell * list
Definition: list_routines.h:30
const int * pos
Definition: combiners.h:905
float x
Definition: cordic.py:15
bstring c int memset(void *s, int c, int length)
#define x1
#define x2
#define status
#define mask(n)
Definition: lbitlib.c:93
ShellFileEnvironment e
Definition: sh6.c:388
struct mono_scan_converter converter[1]
cairo_status_t(* render_rows)(void *abstract_renderer, int y, int height, const cairo_half_open_span_t *coverages, unsigned num_coverages)
struct cell * prev
struct cell * next
struct quorem x
cairo_fixed_t dy
grid_scaled_y_t ytop
cairo_bool_t vertical
grid_scaled_y_t height_left
struct edge * prev
cairo_edge_t edge
struct quorem dxdy
struct edge * next
Definition: filedef.h:30
Definition: ttf.h:354
cairo_half_open_span_t spans_embedded[64]
cairo_half_open_span_t * spans
struct edge ** y_buckets
grid_scaled_y_t ymin
struct edge * edges
grid_scaled_y_t ymax
struct edge * y_buckets_embedded[64]
struct edge edges_embedded[32]
cairo_fixed_t quo
cairo_fixed_t rem
#define FILE
Definition: t1stdio.h:34
int j
Definition: t4ht.c:1589
static double prev_x
Definition: tex4ht.c:1079
return() int(((double) *(font_tbl[cur_fnt].wtbl+(int)(*(font_tbl[cur_fnt].char_wi+(int)(ch - font_tbl[cur_fnt].char_f)% 256)))/(double)(1L<< 20)) *(double) font_tbl[cur_fnt].scale)