#include <stdio.h>
/* A fillpoly in C - for fun
 * Sed - start : Tue Sep  7 23:31:26 MET DST 1999
 * Wed Sep  8 00:30:42 MET DST 1999 : all done, except the low stuff in
 * fill_left and fill_right and the dealing with colors in fill_lines
 * Wed Sep  8 00:58:03 MET DST 1999 : all cases dealed in fill_left except
 * the 12 harder (where x1!x2 and y1!=y2, which makes 4 combinations, each
 * of them giving 3 subcase (dx>dy or dx=dy or dx<dy)). Well, let's go to
 * bed. Tomorrow, will have to write my dea's report (continue it). In
 * exactly 7 days and some hours, I'll be over with this shit. Cool.
 * But no holidays, because the next day, go to see for army shit, and
 * I have a job now too, shit of the shits !
 * Fri Sep 10 00:23:53 MET DST 1999 - let's continue
 * Fri Sep 10 01:37:00 MET DST 1999 - fill_left done, now let's debug it !
 * Fri Sep 10 02:10:54 MET DST 1999 - ok, it work fine. No bug ! (except an <
 * instead of a <= in the caller of fill_left and a bug with my rotation
 * which turned the poly in the indirect way.
 * Something cool would be to have float instead of int for coords of a point
 * and do some subpixel. And I have to make fill_right too. And the colors !
 * (i did not test that)
 * Fri Sep 17 10:57:52 MET DST 1999 - Ok, let's subpixel it all.
 * Holidays are cool, nope ? Yeah, they are !
 * Sun Sep 19 00:59:26 MET DST 1999 : subpixel seems to work.
 * I'm not sure of it at all, strange behavior with one example,
 * but better with another even if strangeness still in there.
 * I am almost sure something's wrong with floor, so I gonna try
 * to put it all in 16:16 math fixed point.
 */
#include <assert.h>
#include <math.h>

#include "device.h"
#include "poly.h"

#define abs(x) ((x)>0 ? (x) : (-(x)))

static int miny, maxy;

/* returns a*b/c in int 16:16 */
static inline int muldiv(int a, int b, int c)
{
#ifdef PC_ARCHI
  register int r;
  __asm__ volatile ("imul %2  \n"
		    "idiv %3  \n"
		    : "=a" (r)
		    : "a" (a), "b" (b), "c" (c)
		    : "eax", "ebx", "ecx", "edx"
		    );
  return r;
#else
  double r, aa=a, bb=b, cc=c;
  r=aa*bb/cc;
  return r;
#endif
}

/*******************************************************
 *                    fill_left                        *
 *******************************************************/
void fill_left(device *d, point *p1, point *p2)
{
  /* lots of goto for lisibility (if if else if if else else is impossible to debug) */
  register int x1=p1->x*65536., x2=p2->x*65536., y1=p1->y*65536., y2=p2->y*65536., dx, dy;
  register int xcur;
  register int xinc;
  register int i;
  register int y1i=(y1+65535)>>16, y2i=(y2+65535)>>16;

  /* in asm, those two subs are good for us, because we can test if x1<x2 and if y1<y2 at the same time, but it's C */
  dx=x2-x1;
  dy=y2-y1;

  if (dx<0)
    goto x1_sup_x2;
  if (dx)
    goto x1_inf_x2;

  /* here x1==x2 */
  if (dy<-65535)
    goto x1_eq_x2_and_y1_sup_y2;
  if (dy>65535)
    goto x1_eq_x2_and_y1_inf_y2;
  /* here x1==x2 && y1==y2 */
  if (y1i<y2i) {
    the_lines[y1i].x_left=x1;
  } else {
    the_lines[y2i].x_left=x1;
  }
  return;
x1_eq_x2_and_y1_sup_y2:
  for (i=y2i; i<y1i; i++) {
    the_lines[i].x_left=x1;
  }
  return;
x1_eq_x2_and_y1_inf_y2:
  for (i=y1i; i<y2i; i++) {
    the_lines[i].x_left=x1;
  }
  return;

x1_inf_x2:
  if (dy<-65535)
    goto x1_inf_x2_and_y1_sup_y2;
  if (dy>65535)
    goto x1_inf_x2_and_y1_inf_y2;
  /* x1<x2 && y1==y2 */
  if (y1i<y2i) {
    the_lines[y1i].x_left=x1;
  } else {
    the_lines[y2i].x_left=x1;
  }
  return;
x1_inf_x2_and_y1_sup_y2:
  /*
                  (x2, y2)


       (x1, y1)
   */
  if (dx!=dy)
    goto x1_inf_x2_and_y1_sup_y2_dx_sup_dy;
  /* here dx == dy */
  for (i=y2i; i<y1i; i++, x2-=65536) {
    the_lines[i].x_left=x2;
  }
  return;
x1_inf_x2_and_y1_sup_y2_dx_sup_dy:
  /*
                    xxxx
		xxxx
	    xxxx
	xxxx
  */
  xinc=muldiv(dx, 65536, dy);
  xcur=x2+muldiv(xinc, (y2i<<16)-y2, 65536);
  for (i=y2i; i<y1i; i++, xcur+=xinc) {
    the_lines[i].x_left=xcur;
  }
  return;

x1_inf_x2_and_y1_inf_y2:
  /*
      (x1, y1)


                  (x2, y2)
  */
  if (dx!=dy)
    goto x1_inf_x2_and_y1_inf_y2_and_dx_sup_dy;
  /* here dx == dy */
  for (i=y1i; i<y2i; i++, x1+=65536) {
    the_lines[i].x_left=x1;
  }
  return;

x1_inf_x2_and_y1_inf_y2_and_dx_sup_dy:
  /*
        xxxx
	    xxxx
	        xxxx
   */
  xinc=muldiv(dx,65536,dy);
  xcur=x1+muldiv(xinc, ((y1i<<16)-y1), 65536);
  for (i=y1i; i<y2i; i++, xcur+=xinc) {
    the_lines[i].x_left=xcur;
  }
  return;

x1_sup_x2:
  if (dy<-65535)
    goto x1_sup_x2_and_y1_sup_y2;
  if (dy>65535)
    goto x1_sup_x2_and_y1_inf_y2;
  /* x1>x2 && y1==y2 */
  if (y1i<y2i) {
    the_lines[y1i].x_left=x2;
  } else {
    the_lines[y2i].x_left=x2;
  }
  return;
x1_sup_x2_and_y1_sup_y2:
  /*
       (x2, y2)


                 (x1, y1)
   */
  if (dx!=dy)
    goto x1_sup_x2_and_y1_sup_y2_and_dx_sup_dy;
  /* here dx == dy */
  for (i=y2i; i<y1i; i++, x2+=65536) {
    the_lines[i].x_left=x2;
  }
  return;
x1_sup_x2_and_y1_sup_y2_and_dx_sup_dy:
  xinc=muldiv(dx, 65536, dy);
  xcur=x2+muldiv(xinc, (y2i<<16)-y2, 65536);
  for (i=y2i; i<y1i; i++, xcur+=xinc) {
    the_lines[i].x_left=xcur;
  }
  return;

x1_sup_x2_and_y1_inf_y2:
  /*
                 (x1, y1)


      (x2, y2)
   */
  if (dx!=dy)
    goto x1_sup_x2_and_y1_inf_y2_and_dx_sup_dy;
  /* here dx == dy */
  for (i=y1i; i<y2i; i++, x1-=65536) {
    the_lines[i].x_left=x1;
  }
  return;
x1_sup_x2_and_y1_inf_y2_and_dx_sup_dy:
  xinc=muldiv(dx, 65536, dy);
  xcur=x1+muldiv(xinc, (y1i<<16)-y1, 65536);
  for (i=y1i; i<y2i; i++, xcur+=xinc) {
    the_lines[i].x_left=xcur;
  }
  return;
}

/************************************************
 *                 fill_right                   *
 ************************************************/
static void fill_right(device *d, point *p1, point *p2)
{
  /* lots of goto for lisibility (if if else if if else else is impossible to debug) */
  register int x1=p1->x*65536., x2=p2->x*65536., y1=p1->y*65536., y2=p2->y*65536., dx, dy;
  register int xcur;
  register int xinc;
  register int i;
  register int y1i=(y1+65535)>>16, y2i=(y2+65535)>>16;

  /* in asm, those two subs are good for us, because we can test if x1<x2 and if y1<y2 at the same time, but it's C */
  dx=x2-x1;
  dy=y2-y1;

  if (dx<0)
    goto x1_sup_x2;
  if (dx)
    goto x1_inf_x2;

  /* here x1==x2 */
  if (dy<-65535)
    goto x1_eq_x2_and_y1_sup_y2;
  if (dy>65535)
    goto x1_eq_x2_and_y1_inf_y2;
  /* here x1==x2 && y1==y2 */
  if (y1i<y2i) {
    the_lines[y1i].x_right=x1;
  } else {
    the_lines[y2i].x_right=x1;
  }
  return;
x1_eq_x2_and_y1_sup_y2:
  for (i=y2i; i<y1i; i++) {
    the_lines[i].x_right=x1;
  }
  return;
x1_eq_x2_and_y1_inf_y2:
  for (i=y1i; i<y2i; i++) {
    the_lines[i].x_right=x1;
  }
  return;

x1_inf_x2:
  if (dy<-65535)
    goto x1_inf_x2_and_y1_sup_y2;
  if (dy>65535)
    goto x1_inf_x2_and_y1_inf_y2;
  /* x1<x2 && y1==y2 */
  if (y1i<y2i) {
    the_lines[y1i].x_right=x2;
  } else {
    the_lines[y2i].x_right=x2;
  }
  return;
x1_inf_x2_and_y1_sup_y2:
  /*
                  (x2, y2)


       (x1, y1)
   */
  if (dx!=dy)
    goto x1_inf_x2_and_y1_sup_y2_dx_sup_dy;
  /* here dx == dy */
  for (i=y2i; i<y1i; i++, x2-=65536) {
    the_lines[i].x_right=x2;
  }
  return;
x1_inf_x2_and_y1_sup_y2_dx_sup_dy:
  /*
                    xxxx
		xxxx
	    xxxx
	xxxx
  */
  xinc=muldiv(dx, 65536, dy);
  xcur=x2+muldiv(xinc, (y2i<<16)-y2, 65536);
  for (i=y2i; i<y1i; i++, xcur+=xinc) {
    the_lines[i].x_right=xcur;
  }
  return;

x1_inf_x2_and_y1_inf_y2:
  /*
      (x1, y1)


                  (x2, y2)
  */
  if (dx!=dy)
    goto x1_inf_x2_and_y1_inf_y2_and_dx_sup_dy;
  /* here dx == dy */
  for (i=y1i; i<y2i; i++, x1+=65536) {
    the_lines[i].x_right=x1;
  }
  return;

x1_inf_x2_and_y1_inf_y2_and_dx_sup_dy:
  /*
        xxxx
	    xxxx
	        xxxx
   */
  xinc=muldiv(dx,65536,dy);
  xcur=x1+muldiv(xinc, ((y1i<<16)-y1), 65536);
  for (i=y1i; i<y2i; i++, xcur+=xinc) {
    the_lines[i].x_right=xcur;
  }
  return;

x1_sup_x2:
  if (dy<-65535)
    goto x1_sup_x2_and_y1_sup_y2;
  if (dy>65535)
    goto x1_sup_x2_and_y1_inf_y2;
  /* x1>x2 && y1==y2 */
  if (y2i<y1i) {
    the_lines[y2i].x_right=x1;
  } else {
    the_lines[y1i].x_right=x1;
  }
  return;
x1_sup_x2_and_y1_sup_y2:
  /*
       (x2, y2)


                 (x1, y1)
   */
  if (dx!=dy)
    goto x1_sup_x2_and_y1_sup_y2_and_dx_sup_dy;
  /* here dx == dy */
  for (i=y2i; i<y1i; i++, x2+=65536) {
    the_lines[i].x_right=x2;
  }
  return;
x1_sup_x2_and_y1_sup_y2_and_dx_sup_dy:
  xinc=muldiv(dx, 65536, dy);
  xcur=x2+muldiv(xinc, (y2i<<16)-y2, 65536);
  for (i=y2i; i<y1i; i++, xcur+=xinc) {
    the_lines[i].x_right=xcur;
  }
  return;

x1_sup_x2_and_y1_inf_y2:
  /*
                 (x1, y1)


      (x2, y2)
   */
  if (dx!=dy)
    goto x1_sup_x2_and_y1_inf_y2_and_dx_sup_dy;
  /* here dx == dy */
  for (i=y1i; i<y2i; i++, x1-=65536) {
    the_lines[i].x_right=x1;
  }
  return;
x1_sup_x2_and_y1_inf_y2_and_dx_sup_dy:
  xinc=muldiv(dx, 65536, dy);
  xcur=x1+muldiv(xinc, (y1i<<16)-y1, 65536);
  for (i=y1i; i<y2i; i++, xcur+=xinc) {
    the_lines[i].x_right=xcur;
  }
  return;
}

/* device dependant stuff (the only one function in there) (depends of x and y res of device,
 * of depth too) (we suppose 320x200x256, 256 grey levels)
 */
void fill_lines(device *d, int thecol)
{
  if (d->depth==8) {
    register int i;
#ifndef PC_ARCHI
    register int j;
    register unsigned char *q;
#endif
    register unsigned char *p=d->buffer;
    device_line *cur_line=&the_lines[(int)miny];
    register int col=thecol;

    p+=miny*SCREEN_X;
    for (i=miny; i<maxy; i++, p+=SCREEN_X, cur_line++) {
#ifndef PC_ARCHI
      register const int xleft=(cur_line->x_left/65536)+1;
      register const int xright=cur_line->x_right/65536;
      q=p;
      q+=xleft;
      for (j=xleft; j<=xright /*cur_line->x_right*/; j++, q++)
	*q=col;
#else
      __asm__ volatile ("movl	%0, %%ebx	\n"
			"movl	%1, %%ecx	\n"
			"shrl	$16, %%ebx	\n"
			"shrl	$16, %%ecx	\n"
			"incl	%%ebx		\n"
			"addl	%%ebx, %%edi	\n"
			"inc	%%ecx		\n"
			"subl	%%ebx, %%ecx	\n"
			"jbe	1f		\n"
			"2: rep; stosb		\n"
			"1:			\n"
			:
			: "g" (cur_line->x_left), "g" (cur_line->x_right), "a" (col), "D" (p)
			: "ebx", "ecx", "eax", "edi"
			);
#endif
    }
  } else if (d->depth==16) { /* here 16bpp */
    register int i;
#ifndef PC_ARCHI
    register int j;
    register unsigned short *q;
#endif
    register unsigned short *p=(unsigned short *)d->buffer;
    device_line *cur_line=&the_lines[(int)miny];
    register int col=thecol;

    p+=miny*SCREEN_X;
    for (i=miny; i<maxy; i++, p+=SCREEN_X, cur_line++) {
#ifndef PC_ARCHI
      register const int xleft=(cur_line->x_left/65536)+1;
      register const int xright=cur_line->x_right/65536;
      q=p;
      q+=xleft;
      for (j=xleft; j<=xright /*cur_line->x_right*/; j++, q++)
	*q=col;
#else
      __asm__ volatile ("movl	%0, %%ebx	\n"
			"movl	%1, %%ecx	\n"
			"shrl	$16, %%ebx	\n"
			"shrl	$16, %%ecx	\n"
			"incl	%%ebx		\n"
			"addl	%%ebx, %%edi	\n"
			"addl	%%ebx, %%edi	\n"
			"inc	%%ecx		\n"
			"subl	%%ebx, %%ecx	\n"
			"jbe	1f		\n"
			"2: rep; stosw		\n"
			"1:			\n"
			:
			: "g" (cur_line->x_left), "g" (cur_line->x_right), "a" (col), "D" (p)
			: "ebx", "ecx", "eax", "edi"
			);
#endif
    }
  } else if (d->depth==24) {
    register int i;
    register int j;
    register unsigned char *q;
    register unsigned char *p=(unsigned char *)d->buffer;
    device_line *cur_line=&the_lines[(int)miny];
    register int col1=thecol&255;
    register int col2=(thecol>>8)&255;
    register int col3=thecol>>16;

    p+=miny*SCREEN_X*3;
    for (i=miny; i<maxy; i++, p+=SCREEN_X*3, cur_line++) {
      register const int xleft=(cur_line->x_left/65536)+1;
      register const int xright=cur_line->x_right/65536;
      q=p;
      q+=xleft*3;
      for (j=xleft; j<=xright /*cur_line->x_right*/; j++, q++) {
	*q++=col1;
	*q++=col2;
	*q=col3;
      }
    }
  } else { /* here 32bpp */
    register int i;
#ifndef PC_ARCHI
    register int j;
    register unsigned int *q;
#endif
    register unsigned int *p=(unsigned int *)d->buffer;
    device_line *cur_line=&the_lines[(int)miny];
    register int col=thecol;

    p+=miny*SCREEN_X;
    for (i=miny; i<maxy; i++, p+=SCREEN_X, cur_line++) {
#ifndef PC_ARCHI
      register const int xleft=(cur_line->x_left/65536)+1;
      register const int xright=cur_line->x_right/65536;
      q=p;
      q+=xleft;
      for (j=xleft; j<=xright /*cur_line->x_right*/; j++, q++)
	*q=col;
#else
      __asm__ volatile ("movl	%0, %%ebx	\n"
			"movl	%1, %%ecx	\n"
			"shrl	$16, %%ebx	\n"
			"shrl	$16, %%ecx	\n"
			"incl	%%ebx		\n"
			"addl	%%ebx, %%edi	\n"
			"addl	%%ebx, %%edi	\n"
			"addl	%%ebx, %%edi	\n"
			"addl	%%ebx, %%edi	\n"
			"incl	%%ecx	\n"
			"subl	%%ebx, %%ecx	\n"
			"jbe	1f		\n"
			"2: rep; stosl		\n"
			"1:			\n"
			:
			: "g" (cur_line->x_left), "g" (cur_line->x_right), "a" (col), "D" (p)
			: "ebx", "ecx", "eax", "edi"
			);
#endif
    }
  }
}

/* the poly is direct and clipped and convex */
#include <stdio.h>
void fillpoly(device *d, poly *p)
{
  register int i;
  register point *q=&p->points[0], *r=&p->points[0];
  register int nb=p->nb_points;
  register int tl=0, br=0;

  assert(p);
  assert(d);
  assert(p->nb_points>2);
  /* get top left and bottom right points */
  miny=((int)(r[0].y*65536.)+65535)>>16;
  maxy=((int)(r[0].y*65536.)+32767)>>16;
  
  for (i=0; i<nb; i++, q++) {
    /* fprintf(stderr, "p[%d]=(%d, %d)\n", i, q->x, q->y); */
    if ((q->y < r[tl].y) || (q->y==r[tl].y && q->x < r[tl].x)) {
      tl=i;
      miny=((int)(r[i].y*65536.)+65535)>>16;
    }
    if ((q->y > r[br].y) || (q->y==r[br].y && q->x > r[br].x)) {
      br=i;
      maxy=((int)(r[i].y*65536.)+32767)>>16;
    }
  }
  /* fprintf(stderr, "top-left=%d bottom-right=%d\nminy=%d maxy=%d\n", tl, br, miny, maxy); */
  /* draw left stuff */
  if (br==tl)
    return;
  assert(br!=tl);
  if (br<tl) {
    for (i=tl; i<nb-1; i++)
      fill_left(d, &r[i], &r[i+1]);
    fill_left(d, &r[nb-1], &r[0]);
    for (i=0; i<=br-1; i++)
      fill_left(d, &r[i], &r[i+1]);
  } else { /* br > tl */
    for (i=tl; i<=br-1; i++) {
      /* fprintf(stderr, "line p[%d] -> p[%d]\n", i, i+1); */
      fill_left(d, &r[i], &r[i+1]);
    }
  }
  /* getchar(); */
  /* draw right stuff */
  if (br>tl) {
    for (i=br; i<nb-1; i++)
      fill_right(d, &r[i], &r[i+1]);
    fill_right(d, &r[nb-1], &r[0]);
    for (i=0; i<=tl-1; i++)
      fill_right(d, &r[i], &r[i+1]);
  } else { /* br < tl */
    for (i=br; i<=tl-1; i++)
      fill_right(d, &r[i], &r[i+1]);
  }

  /* fill the lines */
  fill_lines(d, p->color);
}