/* -*- 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 (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;

    }

}

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)) {

      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_calloc (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);

}