/* A super minimal software rasterizer.
 *
 * Based on <http://canonical.org/~kragen/sw/dev3/xputimage.c>.
 *
 * Not super smooth (moving the mouse delays screen updates), and
 * needs some cleanup.
 *
 * In one test, I got 2.013 million cycles (kcachegrind’s estimate)
 * for 323 frames, about 6.23 million cycles per frame, about 3.9
 * milliseconds per frame.  Of that time, some is in the prefix-sum
 * calculation; it should be possible to follow Raph’s lead to speed
 * that up quite a bit with SSE.
 *
 * This is already a measurable improvement from an initial version
 * that didn’t use memset().
 *
 * XXX switch to xshmu?
 */

#include <assert.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include <unistd.h>
#include <sys/times.h>
#include <sys/types.h>

#include <X11/Xlib.h>
#include <X11/Xutil.h>

void err(char *fmt, ...);
void idle_update(uint32_t *buf, int width, int height);
void redraw(Display *d, Window w, int screen, XImage *im, int ww, int hh);
void click(uint32_t *buf, int width, int height);
void keypress();

int mouse_x, mouse_y;

int main(int argc, char **argv)
{
  int width = 640, height = 480;
  uint32_t *buf = malloc(width*height*sizeof(*buf));
  if (!buf) {
    err("malloc");
  }

  Display *d = XOpenDisplay(NULL);
  if (!d) {
    err("XOpenDisplay");
  }
  int screen = DefaultScreen(d);
  Window w = XCreateSimpleWindow(d, DefaultRootWindow(d),
                                 0, 0, /* x, y */
                                 width, height,
                                 0, 0, /* borderwidth, border */
                                 WhitePixel(d, screen));

  XSelectInput(d, w, ExposureMask
               | KeyPressMask
               | KeyReleaseMask
               | ButtonPressMask
               | ButtonReleaseMask
               | EnterWindowMask
               | LeaveWindowMask
               | PointerMotionMask
               | StructureNotifyMask);

  XMapWindow(d, w);

  XImage *im = XCreateImage(d,
                            DefaultVisual(d, screen),
                            24,      /* depth */
                            ZPixmap, /* format */
                            0,       /* offset (in X pixels) */
                            (char*)buf, /* data */
                            width,
                            height,
                            32, /* bitmap_pad */
                            0); /* let Xlib calculate bytes_per_line */

  XEvent ev;
  fd_set fds;
  FD_ZERO(&fds);
  int fd = ConnectionNumber(d);
  for (;;) {
    /* Poll for input, run idle_update if none */
    if (!XPending(d)) {
      struct timeval tv = { 0, 16667 };
      FD_SET(fd, &fds);
      select(fd, &fds, NULL, NULL, &tv);
      if (!FD_ISSET(fd, &fds)) {
        idle_update(buf, width, height);
        redraw(d, w, screen, im, width, height);
      }
    }

    if (XPending(d)) {
      XNextEvent(d, &ev);
      if (ev.type == Expose) {
        redraw(d, w, screen, im, width, height);
      } else if (ev.type == KeyPress) {
        keypress();
        break;
      } else if (ev.type == MotionNotify) {
        mouse_x = ev.xmotion.x;
        mouse_y = ev.xmotion.y;
        redraw(d, w, screen, im, width, height);
      } else if (ev.type == ButtonPress) {
        mouse_x = ev.xmotion.x;
        mouse_y = ev.xmotion.y;
        click(buf, width, height);
      }
    }
  }

  XDestroyImage(im);
  XCloseDisplay(d);
  return 0;
}

enum { n_triangles = 256 };
typedef struct { int x[3], y[3], vx[3], vy[3], color; } triangle;
triangle triangles[n_triangles] =
  { { {10, 20, 30}, {40, 50, 60}, {7, 8, 9}, {10, 11, 12}, 0x0102040 } };
int next_triangle = 0;

void draw_triangle(triangle *t, uint32_t *buf, int width, int height);
void update_point(triangle *t, int vertex, int width, int height);

int updates;

void idle_update(uint32_t *buf, int width, int height) {
  memset(buf, 0, width * height * sizeof(buf[0]));

  for (triangle *t = triangles; t != triangles + n_triangles; t++) {
    draw_triangle(t, buf, width, height);
    for (int ii = 0; ii < 3; ii++) {
      update_point(t, ii, width, height);
    }
  }

  /* Compute prefix sums to fill in the polygons. */
  for (int yy = 0; yy < height; yy++) {
    for (int xx = 1; xx < width; xx++) {
      buf[yy*width + xx] += buf[yy*width + xx - 1];
    }
  }

  updates++;
}

void update_point(triangle *t, int v, int w, int h) {
  t->x[v] += t->vx[v];
  if (t->x[v] < 0) {            /* bounce left */
    t->x[v] = 0;
    t->vx[v] = -t->vx[v];
  }
  if (t->x[v] >= w) {           /* bounce right */
    t->x[v] = w-1;
    t->vx[v] = -t->vx[v];
  }

  t->y[v] += t->vy[v];
  if (t->y[v] < 0) {            /* bounce top */
    t->y[v] = 0;
    t->vy[v] = -t->vy[v];
  }
  if (t->y[v] >= h) {           /* bounce bottom */
    t->y[v] = h-1;
    t->vy[v] = -t->vy[v];
  }
}


void draw_trap(int y0, int x0a, int x0b,
               int y1, int x1a, int x1b,
               uint32_t *buf, int width, int height, int color);

void draw_triangle(triangle *t, uint32_t *buf, int width, int height) {
  int i_top, i_mid, i_bot;
  /* Sort the three indices by y. */
  if (t->y[0] < t->y[1]) {
    i_top = 0;
    i_mid = 1;
  } else {
    i_top = 1;
    i_mid = 0;
  }
  if (t->y[i_mid] > t->y[2]) {
    i_bot = i_mid;
    i_mid = 2;
  } else {
    i_bot = 2;
  }
  if (t->y[i_mid] < t->y[i_top]) {
    int tmp = i_mid;
    i_mid = i_top;
    i_top = tmp;
  }
  assert(t->y[i_top] <= t->y[i_mid]);
  assert(t->y[i_mid] <= t->y[i_bot]);

  /* Now we have two (possibly empty) triangles joined at a horizontal
     line at t->y[i_mid].

     First, though, we have to figure out where to cut the other side
     of the triangle on its way down there.

     XXX I should probably not be rounding xmid to integer pixels.
  */
  int dy = t->y[i_bot] - t->y[i_top];
  if (!dy) return;
  int dx = t->x[i_bot] - t->x[i_top],
      dy_short = t->y[i_mid] - t->y[i_top],
      xmid = t->x[i_top] + dx * dy_short / dy;
  draw_trap(t->y[i_top], t->x[i_top], t->x[i_top],
            t->y[i_mid], t->x[i_mid], xmid,
            buf, width, height, t->color);
  draw_trap(t->y[i_mid], t->x[i_mid], xmid,
            t->y[i_bot], t->x[i_bot], t->x[i_bot],
            buf, width, height, t->color);
}

/* Horizontal-trapezoid filling routine: fills a trapezoid from (x0a,
   y0) - (x0b, y0) - (x1b, y1) - (x0b, y1) back to start.  The top and
   bottom sides must be horizontal but can be trivial.  The left and
   right sides cannot cross.

   I’m going to do the math in fixed-point, for old time’s sake, with
   a 11-bit fractional part.

   You could argue that this isn’t really a *filling* routine because
   it relies on the later prefix-sum step to do the actual filling; it
   just marks the deltas.
*/
void draw_trap(int y0, int x0a, int x0b,
               int y1, int x1a, int x1b,
               uint32_t *buf, int width, int height,
               int color) {
  assert(y1 >= y0);
  int dy = y1 - y0;
  if (!dy) return;

  /* ensure the trapezoid sides don’t cross */
  if (x0a < x0b) assert(x1a <= x1b);
  if (x1a < x1b) assert(x0a <= x0b);

  /* ensure the as are to the left of the bs */
  if (x0a > x0b || x1a > x1b) {
    int tmp = x0b;
    x0b = x0a;
    x0a = tmp;
    tmp = x1b;
    x1b = x1a;
    x1a = tmp;
  }

  int xa = x0a << 11,
    xb = x0b << 11,
    dxa = ((x1a - x0a) << 11) / dy,
    dxb = ((x1b - x0b) << 11) / dy;

  for (int y = y0; y != y1; y++) {
    /* this still fails sometimes: assert(xa <= xb); */
    buf[width * y + (xa >> 11)] += color;
    buf[width * y + (xb >> 11)] -= color;
    xa += dxa;
    xb += dxb;
  }
}

void redraw(Display *d, Window w, int screen, XImage *im, int ww, int hh) {
      XPutImage(d, w, DefaultGC(d, screen), im,
                0, 0,           /* src_x, src_y */
                0, 0,           /* dest_x, dest_y */
                ww, hh);
}

void click(uint32_t *buf, int width, int height) {
  next_triangle = (next_triangle + 1) % n_triangles;
  triangle *t = &triangles[next_triangle];

  for (int ii = 0; ii != 3; ii++) {
    t->x[ii] = mouse_x;
    t->y[ii] = mouse_y;
    t->vx[ii] = (random() & 15) - 8;
    t->vy[ii] = (random() & 15) - 8;
  }
  t->color = random() & 0x3f3f3f;
}

void keypress()
{
  printf("%d updates\n", updates);
}

void err(char *fmt, ...)
{
  va_list args;
  va_start(args, fmt);
  perror(fmt);
  vfprintf(stderr, fmt, args);
  exit(-1);
  va_end(args);
}