#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* Target output size in bytes, not counting the final newline. */
#define SIZE 9999

static char points[] =
{
   15,70,
   11,72, 10,79, 16,84,
   20,87, 30,85, 29,79,
   28,74, 19,68, 15,70,
   0,

   59,65,
   59,68, 60,74, 65,76,
   70,78, 75,71, 71,65,
   68,61, 59,61, 59,65,
   0,

   37,8,
   46,8,  45,2,  58,4,
   71,6,  74,16, 76,31,
   77,38, 84,39, 77,47,
   64,58, 20,38, 17,26,
   14,14, 25,8,  37,8,
   0,

   29,38,
   23,33, 19,26, 24,23,
   29,20, 37,28, 43,35,
   48,41, 48,46, 57,49,
   57,50, 57,52, 56,54,
   65,57, 59,67, 55,70,
   44,78, 31,77, 23,67,
   12,51, 29,41, 29,38,
   0,

   19,75,
   20,76, 21,77, 23,77,
   24,74, 25,72, 30,72,
   31,71, 30,69, 29,68,
   23,68, 21,71, 19,75,
   0,

   59,70,
   61,70, 62,69, 63,68,
   64,68, 66,70, 66,71,
   65,73, 61,75, 59,75,
   58,74, 58,71, 59,70,
   0,

   59,70,
   60,71, 60,74, 59,75,
   54,75, 52,72, 50,69,
   51,67, 52,66, 54,66,
   55,68, 56,70, 59,70,
   0,

   0
}, *p = points, *image, *w;
static int width, height = 6,
           *range,
           x, y, t;
static double ft, scale;

/* Interpolate between two points. */
static double Interpolate(double a, double b)
{
   return a + (b - a) * ft;
}

/* Interpolate a single component
   https://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm */
static int InterpolateComponent()
{
   return (int)Interpolate(
                  Interpolate(
                     Interpolate(scale * *p,   scale * p[2]),
                     Interpolate(scale * p[2], scale * p[4])),
                  Interpolate(
                     Interpolate(scale * p[2], scale * p[4]),
                     Interpolate(scale * p[4], scale * p[6])));
}

int main(int argc, char **argv)
{
   /* Set width so that (width*height/6 + height) is roughly equal to target
      size, but not exceeding target size.

      Also try to maintain square canvas.                                    */
   for(; (width = (SIZE - 33 - height) * 6 / height) > height; height += 6) {}

   image = w = calloc(width * height, 1);
   range = malloc(height * 2 * sizeof(int));
   if( image == NULL || range == NULL )
      return printf("Out of memory\n");
   scale = width / 90.0;

   while( *p != 0 )
   {
      /* Collect horizontal ranges for each scanline.

         This allows us to draw filled shapes one scanline at a time,
         and the shapes can be both convex and concave as long as each
         scanline is continuous.  We can enforce the continuous requirement
         by tweaking our shapes, saving us the complexity of having to
         write a more featureful rasterizer.                                */
      memset(range, 0, height * 2 * sizeof(int));
      for(; p[2] != 0; p += 6)
      {
         for(t = 0; t < height * 4; t++)
         {
            ft = (double)t / (height * 4.0);

            x = InterpolateComponent();
            p++;
            y = InterpolateComponent();
            p--;

            if( x > 0 && x < width && y >= 0 && y < height )
            {
               if( range[y * 2] == 0 )
               {
                  range[y * 2] = range[y * 2 + 1] = x;
               }
               else
               {
                  range[y * 2] = range[y * 2] < x ? range[y * 2] : x;
                  range[y * 2 + 1] = range[y * 2 + 1] > x ? range[y * 2 + 1] : x;
               }
            }
         }
      }

      /* Draw scanlines. */
      for(y = 0; y < height; y++)
      {
         if( range[y * 2] != 0 )
         {
            for(x = range[y * 2]; x <= range[y * 2 + 1]; x++)
               image[y * width + x] = p < points + 73 ? (x + y) & 1 : 1;
         }
      }

      /* p[0],p[1] is the last pair of coordinates.  p[2] is a trailing zero.
         Thus, to get to the start of the next shape, we need to skip 3.     */
      p += 3;
   }

   /* Convert to Sixel.  Each set of 6 rows costs width+1 bytes. */
   for(y = 0; y < height; y += 6)
   {
      for(x = 0; x < width; x++)
      {
         *w++ = 0x3f +
                image[y * width + x] +
                (image[(y + 1) * width + x] << 1) +
                (image[(y + 2) * width + x] << 2) +
                (image[(y + 3) * width + x] << 3) +
                (image[(y + 4) * width + x] << 4) +
                (image[(y + 5) * width + x] << 5);
      }
      *w++ = '-';
   }

   /* Output image. */
   printf("\x1bPq#0;2;0;0;0#1;2;100;100;100#1");  /* Header = 31 bytes. */

   /* Pad output. */
   while( w - image < SIZE - 33 )
      *w++ = '$';

   fwrite(image, w - image, 1, stdout);
   puts("\x1b\\");  /* Footer = 2 bytes plus newline. */
   return 0;
}