summaryrefslogtreecommitdiff
path: root/Build/source/libs/cairo/cairo-src/src/cairo-mono-scan-converter.c
diff options
context:
space:
mode:
authorDenis Bitouzé <dbitouze@wanadoo.fr>2021-02-25 18:23:07 +0000
committerDenis Bitouzé <dbitouze@wanadoo.fr>2021-02-25 18:23:07 +0000
commitc6101f91d071883b48b1b4b51e5eba0f36d9a78d (patch)
tree1bf7f5a881d7a4f5c5bf59d0b2821943dd822372 /Build/source/libs/cairo/cairo-src/src/cairo-mono-scan-converter.c
parent07ee7222e389b0777456b427a55c22d0e6ffd267 (diff)
French translation for tlmgr updated
git-svn-id: svn://tug.org/texlive/trunk@57912 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Build/source/libs/cairo/cairo-src/src/cairo-mono-scan-converter.c')
-rw-r--r--Build/source/libs/cairo/cairo-src/src/cairo-mono-scan-converter.c612
1 files changed, 0 insertions, 612 deletions
diff --git a/Build/source/libs/cairo/cairo-src/src/cairo-mono-scan-converter.c b/Build/source/libs/cairo/cairo-src/src/cairo-mono-scan-converter.c
deleted file mode 100644
index 891f435c9eb..00000000000
--- a/Build/source/libs/cairo/cairo-src/src/cairo-mono-scan-converter.c
+++ /dev/null
@@ -1,612 +0,0 @@
-/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
-/*
- * Copyright (c) 2011 Intel Corporation
- *
- * Permission is hereby granted, free of charge, to any person
- * obtaining a copy of this software and associated documentation
- * files (the "Software"), to deal in the Software without
- * restriction, including without limitation the rights to use,
- * copy, modify, merge, publish, distribute, sublicense, and/or sell
- * copies of the Software, and to permit persons to whom the
- * Software is furnished to do so, subject to the following
- * conditions:
- *
- * The above copyright notice and this permission notice shall be
- * included in all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
- * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
- * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
- * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
- * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
- * OTHER DEALINGS IN THE SOFTWARE.
- */
-#include "cairoint.h"
-#include "cairo-spans-private.h"
-#include "cairo-error-private.h"
-
-#include <stdlib.h>
-#include <string.h>
-#include <limits.h>
-
-struct quorem {
- int32_t quo;
- int32_t rem;
-};
-
-struct edge {
- struct edge *next, *prev;
-
- int32_t height_left;
- int32_t dir;
- int32_t vertical;
-
- int32_t dy;
- struct quorem x;
- struct quorem dxdy;
-};
-
-/* A collection of sorted and vertically clipped edges of the polygon.
- * Edges are moved from the polygon to an active list while scan
- * converting. */
-struct polygon {
- /* The vertical clip extents. */
- int32_t ymin, ymax;
-
- int num_edges;
- struct edge *edges;
-
- /* Array of edges all starting in the same bucket. An edge is put
- * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
- * it is added to the polygon. */
- struct edge **y_buckets;
-
- struct edge *y_buckets_embedded[64];
- struct edge edges_embedded[32];
-};
-
-struct mono_scan_converter {
- struct polygon polygon[1];
-
- /* Leftmost edge on the current scan line. */
- struct edge head, tail;
- int is_vertical;
-
- cairo_half_open_span_t *spans;
- cairo_half_open_span_t spans_embedded[64];
- int num_spans;
-
- /* Clip box. */
- int32_t xmin, xmax;
- int32_t ymin, ymax;
-};
-
-#define I(x) _cairo_fixed_integer_round_down(x)
-
-/* Compute the floored division a/b. Assumes / and % perform symmetric
- * division. */
-inline static struct quorem
-floored_divrem(int a, int b)
-{
- struct quorem qr;
- qr.quo = a/b;
- qr.rem = a%b;
- if ((a^b)<0 && qr.rem) {
- qr.quo -= 1;
- qr.rem += b;
- }
- return qr;
-}
-
-/* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
- * division. */
-static struct quorem
-floored_muldivrem(int x, int a, int b)
-{
- struct quorem qr;
- long long xa = (long long)x*a;
- qr.quo = xa/b;
- qr.rem = xa%b;
- if ((xa>=0) != (b>=0) && qr.rem) {
- qr.quo -= 1;
- qr.rem += b;
- }
- return qr;
-}
-
-static cairo_status_t
-polygon_init (struct polygon *polygon, int ymin, int ymax)
-{
- unsigned h = ymax - ymin + 1;
-
- polygon->y_buckets = polygon->y_buckets_embedded;
- if (h > ARRAY_LENGTH (polygon->y_buckets_embedded)) {
- polygon->y_buckets = _cairo_malloc_ab (h, sizeof (struct edge *));
- if (unlikely (NULL == polygon->y_buckets))
- return _cairo_error (CAIRO_STATUS_NO_MEMORY);
- }
- memset (polygon->y_buckets, 0, h * sizeof (struct edge *));
- polygon->y_buckets[h-1] = (void *)-1;
-
- polygon->ymin = ymin;
- polygon->ymax = ymax;
- return CAIRO_STATUS_SUCCESS;
-}
-
-static void
-polygon_fini (struct polygon *polygon)
-{
- if (polygon->y_buckets != polygon->y_buckets_embedded)
- free (polygon->y_buckets);
-
- if (polygon->edges != polygon->edges_embedded)
- free (polygon->edges);
-}
-
-static void
-_polygon_insert_edge_into_its_y_bucket(struct polygon *polygon,
- struct edge *e,
- int y)
-{
- struct edge **ptail = &polygon->y_buckets[y - polygon->ymin];
- if (*ptail)
- (*ptail)->prev = e;
- e->next = *ptail;
- e->prev = NULL;
- *ptail = e;
-}
-
-inline static void
-polygon_add_edge (struct polygon *polygon,
- const cairo_edge_t *edge)
-{
- struct edge *e;
- cairo_fixed_t dx;
- cairo_fixed_t dy;
- int y, ytop, ybot;
- int ymin = polygon->ymin;
- int ymax = polygon->ymax;
-
- y = I(edge->top);
- ytop = MAX(y, ymin);
-
- y = I(edge->bottom);
- ybot = MIN(y, ymax);
-
- if (ybot <= ytop)
- return;
-
- e = polygon->edges + polygon->num_edges++;
- e->height_left = ybot - ytop;
- e->dir = edge->dir;
-
- dx = edge->line.p2.x - edge->line.p1.x;
- dy = edge->line.p2.y - edge->line.p1.y;
-
- if (dx == 0) {
- e->vertical = TRUE;
- e->x.quo = edge->line.p1.x;
- e->x.rem = 0;
- e->dxdy.quo = 0;
- e->dxdy.rem = 0;
- e->dy = 0;
- } else {
- e->vertical = FALSE;
- e->dxdy = floored_muldivrem (dx, CAIRO_FIXED_ONE, dy);
- e->dy = dy;
-
- e->x = floored_muldivrem (ytop * CAIRO_FIXED_ONE + CAIRO_FIXED_FRAC_MASK/2 - edge->line.p1.y,
- dx, dy);
- e->x.quo += edge->line.p1.x;
- }
- e->x.rem -= dy;
-
- _polygon_insert_edge_into_its_y_bucket (polygon, e, ytop);
-}
-
-static struct edge *
-merge_sorted_edges (struct edge *head_a, struct edge *head_b)
-{
- struct edge *head, **next, *prev;
- int32_t x;
-
- prev = head_a->prev;
- next = &head;
- if (head_a->x.quo <= head_b->x.quo) {
- head = head_a;
- } else {
- head = head_b;
- head_b->prev = prev;
- goto start_with_b;
- }
-
- do {
- x = head_b->x.quo;
- while (head_a != NULL && head_a->x.quo <= x) {
- prev = head_a;
- next = &head_a->next;
- head_a = head_a->next;
- }
-
- head_b->prev = prev;
- *next = head_b;
- if (head_a == NULL)
- return head;
-
-start_with_b:
- x = head_a->x.quo;
- while (head_b != NULL && head_b->x.quo <= x) {
- prev = head_b;
- next = &head_b->next;
- head_b = head_b->next;
- }
-
- head_a->prev = prev;
- *next = head_a;
- if (head_b == NULL)
- return head;
- } while (1);
-}
-
-static struct edge *
-sort_edges (struct edge *list,
- unsigned int level,
- struct edge **head_out)
-{
- struct edge *head_other, *remaining;
- unsigned int i;
-
- head_other = list->next;
-
- if (head_other == NULL) {
- *head_out = list;
- return NULL;
- }
-
- remaining = head_other->next;
- if (list->x.quo <= head_other->x.quo) {
- *head_out = list;
- head_other->next = NULL;
- } else {
- *head_out = head_other;
- head_other->prev = list->prev;
- head_other->next = list;
- list->prev = head_other;
- list->next = NULL;
- }
-
- for (i = 0; i < level && remaining; i++) {
- remaining = sort_edges (remaining, i, &head_other);
- *head_out = merge_sorted_edges (*head_out, head_other);
- }
-
- return remaining;
-}
-
-static struct edge *
-merge_unsorted_edges (struct edge *head, struct edge *unsorted)
-{
- sort_edges (unsorted, UINT_MAX, &unsorted);
- return merge_sorted_edges (head, unsorted);
-}
-
-inline static void
-active_list_merge_edges (struct mono_scan_converter *c, struct edge *edges)
-{
- struct edge *e;
-
- for (e = edges; c->is_vertical && e; e = e->next)
- c->is_vertical = e->vertical;
-
- c->head.next = merge_unsorted_edges (c->head.next, edges);
-}
-
-inline static void
-add_span (struct mono_scan_converter *c, int x1, int x2)
-{
- int n;
-
- if (x1 < c->xmin)
- x1 = c->xmin;
- if (x2 > c->xmax)
- x2 = c->xmax;
- if (x2 <= x1)
- return;
-
- n = c->num_spans++;
- c->spans[n].x = x1;
- c->spans[n].coverage = 255;
-
- n = c->num_spans++;
- c->spans[n].x = x2;
- c->spans[n].coverage = 0;
-}
-
-inline static void
-row (struct mono_scan_converter *c, unsigned int mask)
-{
- struct edge *edge = c->head.next;
- int xstart = INT_MIN, prev_x = INT_MIN;
- int winding = 0;
-
- c->num_spans = 0;
- while (&c->tail != edge) {
- struct edge *next = edge->next;
- int xend = I(edge->x.quo);
-
- if (--edge->height_left) {
- if (!edge->vertical) {
- edge->x.quo += edge->dxdy.quo;
- edge->x.rem += edge->dxdy.rem;
- if (edge->x.rem >= 0) {
- ++edge->x.quo;
- edge->x.rem -= edge->dy;
- }
- }
-
- if (edge->x.quo < prev_x) {
- struct edge *pos = edge->prev;
- pos->next = next;
- next->prev = pos;
- do {
- pos = pos->prev;
- } while (edge->x.quo < pos->x.quo);
- pos->next->prev = edge;
- edge->next = pos->next;
- edge->prev = pos;
- pos->next = edge;
- } else
- prev_x = edge->x.quo;
- } else {
- edge->prev->next = next;
- next->prev = edge->prev;
- }
-
- winding += edge->dir;
- if ((winding & mask) == 0) {
- if (I(next->x.quo) > xend + 1) {
- add_span (c, xstart, xend);
- xstart = INT_MIN;
- }
- } else if (xstart == INT_MIN)
- xstart = xend;
-
- edge = next;
- }
-}
-
-inline static void dec (struct edge *e, int h)
-{
- e->height_left -= h;
- if (e->height_left == 0) {
- e->prev->next = e->next;
- e->next->prev = e->prev;
- }
-}
-
-static cairo_status_t
-_mono_scan_converter_init(struct mono_scan_converter *c,
- int xmin, int ymin,
- int xmax, int ymax)
-{
- cairo_status_t status;
- int max_num_spans;
-
- status = polygon_init (c->polygon, ymin, ymax);
- if (unlikely (status))
- return status;
-
- max_num_spans = xmax - xmin + 1;
- if (max_num_spans > ARRAY_LENGTH(c->spans_embedded)) {
- c->spans = _cairo_malloc_ab (max_num_spans,
- sizeof (cairo_half_open_span_t));
- if (unlikely (c->spans == NULL)) {
- polygon_fini (c->polygon);
- return _cairo_error (CAIRO_STATUS_NO_MEMORY);
- }
- } else
- c->spans = c->spans_embedded;
-
- c->xmin = xmin;
- c->xmax = xmax;
- c->ymin = ymin;
- c->ymax = ymax;
-
- c->head.vertical = 1;
- c->head.height_left = INT_MAX;
- c->head.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MIN));
- c->head.prev = NULL;
- c->head.next = &c->tail;
- c->tail.prev = &c->head;
- c->tail.next = NULL;
- c->tail.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MAX));
- c->tail.height_left = INT_MAX;
- c->tail.vertical = 1;
-
- c->is_vertical = 1;
- return CAIRO_STATUS_SUCCESS;
-}
-
-static void
-_mono_scan_converter_fini(struct mono_scan_converter *self)
-{
- if (self->spans != self->spans_embedded)
- free (self->spans);
-
- polygon_fini(self->polygon);
-}
-
-static cairo_status_t
-mono_scan_converter_allocate_edges(struct mono_scan_converter *c,
- int num_edges)
-
-{
- c->polygon->num_edges = 0;
- c->polygon->edges = c->polygon->edges_embedded;
- if (num_edges > ARRAY_LENGTH (c->polygon->edges_embedded)) {
- c->polygon->edges = _cairo_malloc_ab (num_edges, sizeof (struct edge));
- if (unlikely (c->polygon->edges == NULL))
- return _cairo_error (CAIRO_STATUS_NO_MEMORY);
- }
-
- return CAIRO_STATUS_SUCCESS;
-}
-
-static void
-mono_scan_converter_add_edge (struct mono_scan_converter *c,
- const cairo_edge_t *edge)
-{
- polygon_add_edge (c->polygon, edge);
-}
-
-static void
-step_edges (struct mono_scan_converter *c, int count)
-{
- struct edge *edge;
-
- for (edge = c->head.next; edge != &c->tail; edge = edge->next) {
- edge->height_left -= count;
- if (! edge->height_left) {
- edge->prev->next = edge->next;
- edge->next->prev = edge->prev;
- }
- }
-}
-
-static cairo_status_t
-mono_scan_converter_render(struct mono_scan_converter *c,
- unsigned int winding_mask,
- cairo_span_renderer_t *renderer)
-{
- struct polygon *polygon = c->polygon;
- int i, j, h = c->ymax - c->ymin;
- cairo_status_t status;
-
- for (i = 0; i < h; i = j) {
- j = i + 1;
-
- if (polygon->y_buckets[i])
- active_list_merge_edges (c, polygon->y_buckets[i]);
-
- if (c->is_vertical) {
- int min_height;
- struct edge *e;
-
- e = c->head.next;
- min_height = e->height_left;
- while (e != &c->tail) {
- if (e->height_left < min_height)
- min_height = e->height_left;
- e = e->next;
- }
-
- while (--min_height >= 1 && polygon->y_buckets[j] == NULL)
- j++;
- if (j != i + 1)
- step_edges (c, j - (i + 1));
- }
-
- row (c, winding_mask);
- if (c->num_spans) {
- status = renderer->render_rows (renderer, c->ymin+i, j-i,
- c->spans, c->num_spans);
- if (unlikely (status))
- return status;
- }
-
- /* XXX recompute after dropping edges? */
- if (c->head.next == &c->tail)
- c->is_vertical = 1;
- }
-
- return CAIRO_STATUS_SUCCESS;
-}
-
-struct _cairo_mono_scan_converter {
- cairo_scan_converter_t base;
-
- struct mono_scan_converter converter[1];
- cairo_fill_rule_t fill_rule;
-};
-
-typedef struct _cairo_mono_scan_converter cairo_mono_scan_converter_t;
-
-static void
-_cairo_mono_scan_converter_destroy (void *converter)
-{
- cairo_mono_scan_converter_t *self = converter;
- _mono_scan_converter_fini (self->converter);
- free(self);
-}
-
-cairo_status_t
-_cairo_mono_scan_converter_add_polygon (void *converter,
- const cairo_polygon_t *polygon)
-{
- cairo_mono_scan_converter_t *self = converter;
- cairo_status_t status;
- int i;
-
-#if 0
- FILE *file = fopen ("polygon.txt", "w");
- _cairo_debug_print_polygon (file, polygon);
- fclose (file);
-#endif
-
- status = mono_scan_converter_allocate_edges (self->converter,
- polygon->num_edges);
- if (unlikely (status))
- return status;
-
- for (i = 0; i < polygon->num_edges; i++)
- mono_scan_converter_add_edge (self->converter, &polygon->edges[i]);
-
- return CAIRO_STATUS_SUCCESS;
-}
-
-static cairo_status_t
-_cairo_mono_scan_converter_generate (void *converter,
- cairo_span_renderer_t *renderer)
-{
- cairo_mono_scan_converter_t *self = converter;
-
- return mono_scan_converter_render (self->converter,
- self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
- renderer);
-}
-
-cairo_scan_converter_t *
-_cairo_mono_scan_converter_create (int xmin,
- int ymin,
- int xmax,
- int ymax,
- cairo_fill_rule_t fill_rule)
-{
- cairo_mono_scan_converter_t *self;
- cairo_status_t status;
-
- self = _cairo_malloc (sizeof(struct _cairo_mono_scan_converter));
- if (unlikely (self == NULL)) {
- status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
- goto bail_nomem;
- }
-
- self->base.destroy = _cairo_mono_scan_converter_destroy;
- self->base.generate = _cairo_mono_scan_converter_generate;
-
- status = _mono_scan_converter_init (self->converter,
- xmin, ymin, xmax, ymax);
- if (unlikely (status))
- goto bail;
-
- self->fill_rule = fill_rule;
-
- return &self->base;
-
- bail:
- self->base.destroy(&self->base);
- bail_nomem:
- return _cairo_scan_converter_create_in_error (status);
-}