/*

 * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.

 * Copyright © 2004 Keith Packard

 *

 * Permission to use, copy, modify, distribute, and sell this software and its

 * documentation for any purpose is hereby granted without fee, provided that

 * the above copyright notice appear in all copies and that both that

 * copyright notice and this permission notice appear in supporting

 * documentation, and that the name of Keith Packard not be used in

 * advertising or publicity pertaining to distribution of the software without

 * specific, written prior permission.  Keith Packard makes no

 * representations about the suitability of this software for any purpose.  It

 * is provided "as is" without express or implied warranty.

 *

 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,

 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO

 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR

 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,

 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER

 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR

 * PERFORMANCE OF THIS SOFTWARE.

 */

#ifdef HAVE_CONFIG_H

#include <pixman-config.h>

#endif

#include <stdio.h>

#include <stdlib.h>

#include "pixman-private.h"

/*

 * Compute the smallest value greater than or equal to y which is on a

 * grid row.

 */

PIXMAN_EXPORT pixman_fixed_t

pixman_sample_ceil_y (pixman_fixed_t y, int n)

{

    pixman_fixed_t f = pixman_fixed_frac (y);

    pixman_fixed_t i = pixman_fixed_floor (y);

    f = DIV (f - Y_FRAC_FIRST (n) + (STEP_Y_SMALL (n) - pixman_fixed_e), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +

  Y_FRAC_FIRST (n);

    if (f > Y_FRAC_LAST (n))

    {

  if (pixman_fixed_to_int (i) == 0x7fff)

  {

      f = 0xffff; /* saturate */

  }

  else

  {

      f = Y_FRAC_FIRST (n);

      i += pixman_fixed_1;

  }

    }

    return (i | f);

}

/*

 * Compute the largest value strictly less than y which is on a

 * grid row.

 */

PIXMAN_EXPORT pixman_fixed_t

pixman_sample_floor_y (pixman_fixed_t y,

                       int            n)

{

    pixman_fixed_t f = pixman_fixed_frac (y);

    pixman_fixed_t i = pixman_fixed_floor (y);

    f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +

  Y_FRAC_FIRST (n);

    if (f < Y_FRAC_FIRST (n))

    {

  if (pixman_fixed_to_int (i) == 0xffff8000)

  {

      f = 0; /* saturate */

  }

  else

  {

      f = Y_FRAC_LAST (n);

      i -= pixman_fixed_1;

  }

    }

    return (i | f);

}

/*

 * Step an edge by any amount (including negative values)

 */

PIXMAN_EXPORT void

pixman_edge_step (pixman_edge_t *e,

                  int            n)

{

    pixman_fixed_48_16_t ne;

    e->x += n * e->stepx;

    ne = e->e + n * (pixman_fixed_48_16_t) e->dx;

    if (n >= 0)

    {

  if (ne > 0)

  {

      int nx = (ne + e->dy - 1) / e->dy;

      e->e = ne - nx * (pixman_fixed_48_16_t) e->dy;

      e->x += nx * e->signdx;

  }

    }

    else

    {

  if (ne <= -e->dy)

  {

      int nx = (-ne) / e->dy;

      e->e = ne + nx * (pixman_fixed_48_16_t) e->dy;

      e->x -= nx * e->signdx;

  }

    }

}

/*

 * A private routine to initialize the multi-step

 * elements of an edge structure

 */

static void

_pixman_edge_multi_init (pixman_edge_t * e,

                         int             n,

                         pixman_fixed_t *stepx_p,

                         pixman_fixed_t *dx_p)

{

    pixman_fixed_t stepx;

    pixman_fixed_48_16_t ne;

    ne = n * (pixman_fixed_48_16_t) e->dx;

    stepx = n * e->stepx;

    if (ne > 0)

    {

  int nx = ne / e->dy;

  ne -= nx * (pixman_fixed_48_16_t)e->dy;

  stepx += nx * e->signdx;

    }

    *dx_p = ne;

    *stepx_p = stepx;

}

/*

 * Initialize one edge structure given the line endpoints and a

 * starting y value

 */

PIXMAN_EXPORT void

pixman_edge_init (pixman_edge_t *e,

                  int            n,

                  pixman_fixed_t y_start,

                  pixman_fixed_t x_top,

                  pixman_fixed_t y_top,

                  pixman_fixed_t x_bot,

                  pixman_fixed_t y_bot)

{

    pixman_fixed_t dx, dy;

    e->x = x_top;

    e->e = 0;

    dx = x_bot - x_top;

    dy = y_bot - y_top;

    e->dy = dy;

    e->dx = 0;

    if (dy)

    {

  if (dx >= 0)

  {

      e->signdx = 1;

      e->stepx = dx / dy;

      e->dx = dx % dy;

      e->e = -dy;

  }

  else

  {

      e->signdx = -1;

      e->stepx = -(-dx / dy);

      e->dx = -dx % dy;

      e->e = 0;

  }

  _pixman_edge_multi_init (e, STEP_Y_SMALL (n),

         &e->stepx_small, &e->dx_small);

  _pixman_edge_multi_init (e, STEP_Y_BIG (n),

         &e->stepx_big, &e->dx_big);

    }

    pixman_edge_step (e, y_start - y_top);

}

/*

 * Initialize one edge structure given a line, starting y value

 * and a pixel offset for the line

 */

PIXMAN_EXPORT void

pixman_line_fixed_edge_init (pixman_edge_t *            e,

                             int                        n,

                             pixman_fixed_t             y,

                             const pixman_line_fixed_t *line,

                             int                        x_off,

                             int                        y_off)

{

    pixman_fixed_t x_off_fixed = pixman_int_to_fixed (x_off);

    pixman_fixed_t y_off_fixed = pixman_int_to_fixed (y_off);

    const pixman_point_fixed_t *top, *bot;

    if (line->p1.y <= line->p2.y)

    {

  top = &line->p1;

  bot = &line->p2;

    }

    else

    {

  top = &line->p2;

  bot = &line->p1;

    }

    pixman_edge_init (e, n, y,

                      top->x + x_off_fixed,

                      top->y + y_off_fixed,

                      bot->x + x_off_fixed,

                      bot->y + y_off_fixed);

}

PIXMAN_EXPORT void

pixman_add_traps (pixman_image_t *     image,

                  int16_t              x_off,

                  int16_t              y_off,

                  int                  ntrap,

                  const pixman_trap_t *traps)

{

    int bpp;

    int height;

    pixman_fixed_t x_off_fixed;

    pixman_fixed_t y_off_fixed;

    pixman_edge_t l, r;

    pixman_fixed_t t, b;

    _pixman_image_validate (image);

    height = image->bits.height;

    bpp = PIXMAN_FORMAT_BPP (image->bits.format);

    x_off_fixed = pixman_int_to_fixed (x_off);

    y_off_fixed = pixman_int_to_fixed (y_off);

    while (ntrap--)

    {

  t = traps->top.y + y_off_fixed;

  if (t < 0)

      t = 0;

  t = pixman_sample_ceil_y (t, bpp);

  b = traps->bot.y + y_off_fixed;

  if (pixman_fixed_to_int (b) >= height)

      b = pixman_int_to_fixed (height) - 1;

  b = pixman_sample_floor_y (b, bpp);

  if (b >= t)

  {

      /* initialize edge walkers */

      pixman_edge_init (&l, bpp, t,

                        traps->top.l + x_off_fixed,

                        traps->top.y + y_off_fixed,

                        traps->bot.l + x_off_fixed,

                        traps->bot.y + y_off_fixed);

      pixman_edge_init (&r, bpp, t,

                        traps->top.r + x_off_fixed,

                        traps->top.y + y_off_fixed,

                        traps->bot.r + x_off_fixed,

                        traps->bot.y + y_off_fixed);

      pixman_rasterize_edges (image, &l, &r, t, b);

  }

  traps++;

    }

}

#if 0

static void

dump_image (pixman_image_t *image,

            const char *    title)

{

    int i, j;

    if (!image->type == BITS)

  printf ("%s is not a regular image\n", title);

    if (!image->bits.format == PIXMAN_a8)

  printf ("%s is not an alpha mask\n", title);

    printf ("\n\n\n%s: \n", title);

    for (i = 0; i < image->bits.height; ++i)

    {

  uint8_t *line =

      (uint8_t *)&(image->bits.bits[i * image->bits.rowstride]);

  for (j = 0; j < image->bits.width; ++j)

      printf ("%c", line[j] ? '#' : ' ');

  printf ("\n");

    }

}

#endif

PIXMAN_EXPORT void

pixman_add_trapezoids (pixman_image_t *          image,

                       int16_t                   x_off,

                       int                       y_off,

                       int                       ntraps,

                       const pixman_trapezoid_t *traps)

{

    int i;

#if 0

    dump_image (image, "before");

#endif

    for (i = 0; i < ntraps; ++i)

    {

  const pixman_trapezoid_t *trap = &(traps[i]);

  if (!pixman_trapezoid_valid (trap))

      continue;

  pixman_rasterize_trapezoid (image, trap, x_off, y_off);

    }

#if 0

    dump_image (image, "after");

#endif

}

PIXMAN_EXPORT void

pixman_rasterize_trapezoid (pixman_image_t *          image,

                            const pixman_trapezoid_t *trap,

                            int                       x_off,

                            int                       y_off)

{

    int bpp;

    int height;

    pixman_fixed_t y_off_fixed;

    pixman_edge_t l, r;

    pixman_fixed_t t, b;

    return_if_fail (image->type == BITS);

    _pixman_image_validate (image);

    if (!pixman_trapezoid_valid (trap))

  return;

    height = image->bits.height;

    bpp = PIXMAN_FORMAT_BPP (image->bits.format);

    y_off_fixed = pixman_int_to_fixed (y_off);

    t = trap->top + y_off_fixed;

    if (t < 0)

  t = 0;

    t = pixman_sample_ceil_y (t, bpp);

    b = trap->bottom + y_off_fixed;

    if (pixman_fixed_to_int (b) >= height)

  b = pixman_int_to_fixed (height) - 1;

    b = pixman_sample_floor_y (b, bpp);

    if (b >= t)

    {

  /* initialize edge walkers */

  pixman_line_fixed_edge_init (&l, bpp, t, &trap->left, x_off, y_off);

  pixman_line_fixed_edge_init (&r, bpp, t, &trap->right, x_off, y_off);

  pixman_rasterize_edges (image, &l, &r, t, b);

    }

}

static const pixman_bool_t zero_src_has_no_effect[PIXMAN_N_OPERATORS] =

{

    FALSE,  /* Clear    0     0    */

    FALSE,  /* Src      1     0    */

    TRUE, /* Dst      0     1    */

    TRUE, /* Over     1     1-Aa */

    TRUE, /* OverReverse    1-Ab      1    */

    FALSE,  /* In     Ab      0    */

    FALSE,  /* InReverse    0     Aa   */

    FALSE,  /* Out      1-Ab      0    */

    TRUE, /* OutReverse   0     1-Aa */

    TRUE, /* Atop     Ab      1-Aa */

    FALSE,  /* AtopReverse    1-Ab      Aa   */

    TRUE, /* Xor      1-Ab      1-Aa */

    TRUE, /* Add      1     1    */

};

static pixman_bool_t

get_trap_extents (pixman_op_t op, pixman_image_t *dest,

      const pixman_trapezoid_t *traps, int n_traps,

      pixman_box32_t *box)

{

    int i;

    /* When the operator is such that a zero source has an

     * effect on the underlying image, we have to

     * composite across the entire destination

     */

    if (!zero_src_has_no_effect [op])

    {

  box->x1 = 0;

  box->y1 = 0;

  box->x2 = dest->bits.width;

  box->y2 = dest->bits.height;

  return TRUE;

    }

    box->x1 = INT32_MAX;

    box->y1 = INT32_MAX;

    box->x2 = INT32_MIN;

    box->y2 = INT32_MIN;

    for (i = 0; i < n_traps; ++i)

    {

  const pixman_trapezoid_t *trap = &(traps[i]);

  int y1, y2;

  if (!pixman_trapezoid_valid (trap))

      continue;

  y1 = pixman_fixed_to_int (trap->top);

  if (y1 < box->y1)

      box->y1 = y1;

  y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom));

  if (y2 > box->y2)

      box->y2 = y2;

#define EXTEND_MIN(x)             \

  if (pixman_fixed_to_int ((x)) < box->x1)     \

      box->x1 = pixman_fixed_to_int ((x));

#define EXTEND_MAX(x)             \

  if (pixman_fixed_to_int (pixman_fixed_ceil ((x))) > box->x2) \

      box->x2 = pixman_fixed_to_int (pixman_fixed_ceil ((x)));

#define EXTEND(x)             \

  EXTEND_MIN(x);              \

  EXTEND_MAX(x);

  EXTEND(trap->left.p1.x);

  EXTEND(trap->left.p2.x);

  EXTEND(trap->right.p1.x);

  EXTEND(trap->right.p2.x);

    }

    if (box->x1 >= box->x2 || box->y1 >= box->y2)

  return FALSE;

    return TRUE;

}

/*

 * pixman_composite_trapezoids()

 *

 * All the trapezoids are conceptually rendered to an infinitely big image.

 * The (0, 0) coordinates of this image are then aligned with the (x, y)

 * coordinates of the source image, and then both images are aligned with

 * the (x, y) coordinates of the destination. Then these three images are

 * composited across the entire destination.

 */

PIXMAN_EXPORT void

pixman_composite_trapezoids (pixman_op_t    op,

           pixman_image_t *   src,

           pixman_image_t *   dst,

           pixman_format_code_t mask_format,

           int      x_src,

           int      y_src,

           int      x_dst,

           int      y_dst,

           int      n_traps,

           const pixman_trapezoid_t * traps)

{

    int i;

    return_if_fail (PIXMAN_FORMAT_TYPE (mask_format) == PIXMAN_TYPE_A);

    if (n_traps <= 0)

  return;

    _pixman_image_validate (src);

    _pixman_image_validate (dst);

    if (op == PIXMAN_OP_ADD &&

  (src->common.flags & FAST_PATH_IS_OPAQUE)   &&

  (mask_format == dst->common.extended_format_code)  &&

  !(dst->common.have_clip_region))

    {

  for (i = 0; i < n_traps; ++i)

  {

      const pixman_trapezoid_t *trap = &(traps[i]);

      if (!pixman_trapezoid_valid (trap))

    continue;

      pixman_rasterize_trapezoid (dst, trap, x_dst, y_dst);

  }

    }

    else

    {

  pixman_image_t *tmp;

  pixman_box32_t box;

  int i;

  if (!get_trap_extents (op, dst, traps, n_traps, &box))

      return;

  if (!(tmp = pixman_image_create_bits (

      mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1)))

      return;

  for (i = 0; i < n_traps; ++i)

  {

      const pixman_trapezoid_t *trap = &(traps[i]);

      if (!pixman_trapezoid_valid (trap))

    continue;

      pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1);

  }

  pixman_image_composite (op, src, tmp, dst,

        x_src + box.x1, y_src + box.y1,

        0, 0,

        x_dst + box.x1, y_dst + box.y1,

        box.x2 - box.x1, box.y2 - box.y1);

  pixman_image_unref (tmp);

    }

}

static int

greater_y (const pixman_point_fixed_t *a, const pixman_point_fixed_t *b)

{

    if (a->y == b->y)

  return a->x > b->x;

    return a->y > b->y;

}

/*

 * Note that the definition of this function is a bit odd because

 * of the X coordinate space (y increasing downwards).

 */

static int

clockwise (const pixman_point_fixed_t *ref,

     const pixman_point_fixed_t *a,

     const pixman_point_fixed_t *b)

{

    pixman_point_fixed_t  ad, bd;

    ad.x = a->x - ref->x;

    ad.y = a->y - ref->y;

    bd.x = b->x - ref->x;

    bd.y = b->y - ref->y;

    return ((pixman_fixed_32_32_t) bd.y * ad.x -

      (pixman_fixed_32_32_t) ad.y * bd.x) < 0;

}

static void

triangle_to_trapezoids (const pixman_triangle_t *tri, pixman_trapezoid_t *traps)

{

    const pixman_point_fixed_t *top, *left, *right, *tmp;

    top = &tri->p1;

    left = &tri->p2;

    right = &tri->p3;

    if (greater_y (top, left))

    {

  tmp = left;

  left = top;

  top = tmp;

    }

    if (greater_y (top, right))

    {

  tmp = right;

  right = top;

  top = tmp;

    }

    if (clockwise (top, right, left))

    {

  tmp = right;

  right = left;

  left = tmp;

    }

    /*

     * Two cases:

     *

     *    +   +

     *         / \             / \

     *        /   \           /   \

     *       /     +         +     \

     *      /    --           --    \

     *     /   --               --   \

     *    / ---                   --- \

     *   +--                         --+

     */

    traps->top = top->y;

    traps->left.p1 = *top;

    traps->left.p2 = *left;

    traps->right.p1 = *top;

    traps->right.p2 = *right;

    if (right->y < left->y)

  traps->bottom = right->y;

    else

  traps->bottom = left->y;

    traps++;

    *traps = *(traps - 1);

    if (right->y < left->y)

    {

  traps->top = right->y;

  traps->bottom = left->y;

  traps->right.p1 = *right;

  traps->right.p2 = *left;

    }

    else

    {

  traps->top = left->y;

  traps->bottom = right->y;

  traps->left.p1 = *left;

  traps->left.p2 = *right;

    }

}

static pixman_trapezoid_t *

convert_triangles (int n_tris, const pixman_triangle_t *tris)

{

    pixman_trapezoid_t *traps;

    int i;

    if (n_tris <= 0)

  return NULL;

    traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t));

    if (!traps)

  return NULL;

    for (i = 0; i < n_tris; ++i)

  triangle_to_trapezoids (&(tris[i]), traps + 2 * i);

    return traps;

}

PIXMAN_EXPORT void

pixman_composite_triangles (pixman_op_t     op,

          pixman_image_t *    src,

          pixman_image_t *    dst,

          pixman_format_code_t  mask_format,

          int       x_src,

          int       y_src,

          int       x_dst,

          int       y_dst,

          int       n_tris,

          const pixman_triangle_t * tris)

{

    pixman_trapezoid_t *traps;

    if ((traps = convert_triangles (n_tris, tris)))

    {

  pixman_composite_trapezoids (op, src, dst, mask_format,

             x_src, y_src, x_dst, y_dst,

             n_tris * 2, traps);

  free (traps);

    }

}

PIXMAN_EXPORT void

pixman_add_triangles (pixman_image_t          *image,

          int32_t                x_off,

          int32_t                y_off,

          int                n_tris,

          const pixman_triangle_t *tris)

{

    pixman_trapezoid_t *traps;

    if ((traps = convert_triangles (n_tris, tris)))

    {

  pixman_add_trapezoids (image, x_off, y_off,

             n_tris * 2, traps);

  free (traps);

    }

}