src/lib/sixel.c

#include "internal.h"
#include "fbuf.h"

#define RGBSIZE 3
#define CENTSIZE (RGBSIZE + 1) // size of a color table entry

// we set P2 based on whether there is any transparency in the sixel. if not,
// use SIXEL_P2_ALLOPAQUE (0), for faster drawing in certain terminals.
typedef enum {
  SIXEL_P2_ALLOPAQUE = 0,
  SIXEL_P2_TRANS = 1,
} sixel_p2_e;

// returns the number of individual sixels necessary to represent the specified
// pixel geometry. these might encompass more pixel rows than |dimy| would
// suggest, up to the next multiple of 6 (i.e. a single row becomes a 6-row
// bitmap; as do two, three, four, five, or six rows). input is scaled geometry.
static inline int
sixelcount(int dimy, int dimx){
  return (dimy + 5) / 6 * dimx;
}

// create an auxiliary vector suitable for a Sixel sprixcell, and zero it out.
// there are two bytes per pixel in the cell: a contiguous set of palette
// indices (yet another reason that we work with 256 colors), and a contiguous
// set of two-value transparencies (these could be folded down to bits from
// bytes, saving 7/8 of the space FIXME).
static inline uint8_t*
sixel_auxiliary_vector(const sprixel* s){
  int pixels = ncplane_pile(s->n)->cellpxy * ncplane_pile(s->n)->cellpxx;
  uint8_t* ret = malloc(sizeof(*ret) * pixels * 2);
  if(ret){
    memset(ret, 0, sizeof(*ret) * pixels);
  }
  return ret;
}

// we keep a color-indexed set of sixels (a single-row column of six pixels,
// encoded as a byte) across the life of the sprixel. This provides a good
// combination of easy-to-edit (for wipes and restores) -- you can index by
// color, and then by position, in O(1) -- and a form which can easily be
// converted to the actual Sixel encoding. wipes and restores come in and edit
// these sixels in O(1), and then at display time we recreate the encoded
// bitmap in one go if necessary. we could just wipe and restore directly using
// the encoded form, but it's a tremendous pain in the ass. this sixelmap will
// be kept in the sprixel. when first encoding, data and table each have an
// entry for every color register; call sixelmap_trim() when done to cut them
// down to the actual number of colors used.
typedef struct sixelmap {
  int colors;
  int sixelcount;
  unsigned char* data;  // |colors| x |sixelcount|-byte arrays
  unsigned char* table; // |colors| x CENTSIZE: components + dtable index
} sixelmap;

// whip up an all-zero sixelmap for the specified pixel geometry and color
// register count. we might not use all the available color registers; call
// sixelmap_trim() to release any unused memory once done encoding.
static sixelmap*
sixelmap_create(int cregs, int dimy, int dimx){
  sixelmap* ret = malloc(sizeof(*ret));
  if(ret){
    ret->sixelcount = sixelcount(dimy, dimx);
    if(ret->sixelcount){
      size_t dsize = sizeof(*ret->data) * cregs * ret->sixelcount;
      ret->data = malloc(dsize);
      if(ret->data){
        size_t tsize = CENTSIZE * cregs;
        ret->table = malloc(tsize);
        if(ret->table){
          memset(ret->table, 0, tsize);
          memset(ret->data, 0, dsize);
          ret->colors = 0;
          return ret;
        }
        free(ret->data);
      }
    }
    free(ret);
  }
  return NULL;
}

// trims s->data down to the number of colors actually used (as opposed to the
// number of color registers available).
static int
sixelmap_trim(sixelmap* s){
  if(s->colors == 0){
    free(s->table);
    s->table = NULL;
    free(s->data);
    s->data = NULL;
    return 0;
  }
  size_t dsize = sizeof(*s->data) * s->colors * s->sixelcount;
  unsigned char* tmp = realloc(s->data, dsize);
  if(tmp == NULL){
    return -1;
  }
  s->data = tmp;
  size_t tsize = CENTSIZE * s->colors;
  if((tmp = realloc(s->table, tsize)) == NULL){
    return -1;
  }
  s->table = tmp;
  return 0;
}

void sixelmap_free(sixelmap *s){
  if(s){
    free(s->table);
    free(s->data);
    free(s);
  }
}

typedef struct cdetails {
  int64_t sums[3];   // sum of components of all matching original colors
  int32_t count;     // count of pixels matching
  char hi[RGBSIZE];  // highest sixelspace components we've seen
  char lo[RGBSIZE];  // lowest sixelspace color we've seen
} cdetails;

// second pass: construct data for extracted colors over the sixels
typedef struct sixeltable {
  sixelmap* map;        // copy of palette indices / transparency bits
  // FIXME keep these internal to palette extraction; finalize there
  cdetails* deets;      // |colorregs| cdetails structures
  int colorregs;
  sixel_p2_e p2;        // set to SIXEL_P2_TRANS if we have transparent pixels
} sixeltable;

// the P2 parameter on a sixel specifies how unspecified pixels are drawn.
// if P2 is 1, unspecified pixels are transparent. otherwise, they're drawn
// as something else. some terminals (e.g. foot) can draw more quickly if
// P2 is 0, so we set that when we have no transparent pixels -- i.e. when
// all TAM entries are 0. P2 is at a fixed location in the sixel header.
// obviously, the sixel must already exist.
static inline void
change_p2(char* sixel, sixel_p2_e value){
  sixel[4] = value + '0';
}

// take (8-bit rgb value & mask) to sixelspace [0..100]
static inline char
ss(unsigned rgb, unsigned char mask){
  return (rgb & mask) * 100 / 255;
}

static inline void
break_sixel_comps(unsigned char comps[static RGBSIZE], uint32_t rgba, unsigned char mask){
  comps[0] = ss(ncpixel_r(rgba), mask);
  comps[1] = ss(ncpixel_g(rgba), mask);
  comps[2] = ss(ncpixel_b(rgba), mask);
//fprintf(stderr, "%u %u %u\n", comps[0], comps[1], comps[2]);
}

static inline int
ctable_to_dtable(const unsigned char* ctable){
  return ctable[3]; // * 256 + ctable[4];
}

static inline void
dtable_to_ctable(int dtable, unsigned char* ctable){
  ctable[3] = dtable;
  /*ctable[3] = dtable / 256;
  ctable[4] = dtable % 256;*/
}

// wipe the color from startx to endx, from starty to endy. returns 1 if any
// pixels were actually wiped.
static inline int
wipe_color(sixelmap* smap, int color, int sband, int eband,
           int startx, int endx, int starty, int endy, int dimx,
           int cellpixy, int cellpixx, uint8_t* auxvec){
  int wiped = 0;
  int didx = ctable_to_dtable(smap->table + color * CENTSIZE);
  // offset into map->data where our color starts
  int coff = smap->sixelcount * didx;
//fprintf(stderr, "didx: %d sixels: %d color: %d B: %d-%d Y: %d-%d X: %d-%d coff: %d\n", didx, smap->sixelcount, color, sband, eband, starty, endy, startx, endx, coff);
  // we're going to repurpose starty as "starting row of this band", so keep it
  // around as originy for auxvecidx computations
  int originy = starty;
  for(int b = sband ; b <= eband && b * 6 <= endy ; ++b){
    const int boff = coff + b * dimx; // offset in data where band starts
    unsigned char mask = 63;
    for(int i = 0 ; i < 6 ; ++i){
      if(b * 6 + i >= starty && b * 6 + i <= endy){
        mask &= ~(1u << i);
      }
//fprintf(stderr, "s/e: %d/%d mask: %02x\n", starty, endy, mask);
    }
    for(int x = startx ; x <= endx ; ++x){
      const int xoff = boff + x;
      assert(xoff < (smap->colors + 1) * smap->sixelcount);
//fprintf(stderr, "band: %d color: %d idx: %d mask: %02x\n", b, color, color * smap->sixelcount + xoff, mask);
//fprintf(stderr, "color: %d idx: %d data: %02x\n", color, color * smap->sixelcount + xoff, smap->data[color * smap->sixelcount + xoff]);
      // this is the auxvec position of the upperleftmost pixel of the sixel
      // there will be up to five more, each cellpxx away, for the five pixels
      // below it. there will be cellpxx - 1 after it, each with their own five.
//fprintf(stderr, "smap->data[%d] = %02x boff: %d x: %d color: %d\n", xoff, smap->data[xoff], boff, x, color);
      for(int i = 0 ; i < 6 && b * 6 + i <= endy ; ++i){
        int auxvecidx = (x - startx) + ((b * 6 + i - originy) * cellpixx);
        unsigned bit = 1u << i;
//fprintf(stderr, "xoff: %d i: %d b: %d endy: %d mask: 0x%02x\n", xoff, i, b, endy, mask);
        if(!(mask & bit) && (smap->data[xoff] & bit)){
//fprintf(stderr, "band %d %d/%d writing %d to auxvec[%d] %p xoff: %d boff: %d\n", b, b * 6 + i, x, color, auxvecidx, auxvec, xoff, boff);
          auxvec[auxvecidx] = color;
          auxvec[cellpixx * cellpixy + auxvecidx] = 0;
        }
      }
      if((smap->data[xoff] & mask) != smap->data[xoff]){
        smap->data[xoff] &= mask;
        wiped = 1;
      }
//fprintf(stderr, "post: %02x\n", smap->data[color * smap->sixelcount + xoff]);
    }
    starty = (starty + 6) / 6 * 6;
  }
  return wiped;
}

// we return -1 because we're not doing a proper wipe -- that's not possible
// using sixel. we just mark it as partially transparent, so that if it's
// redrawn, it's redrawn using P2=1.
int sixel_wipe(sprixel* s, int ycell, int xcell){
//fprintf(stderr, "WIPING %d/%d\n", ycell, xcell);
  uint8_t* auxvec = sixel_auxiliary_vector(s);
  if(auxvec == NULL){
    return -1;
  }
  const int cellpxy = ncplane_pile(s->n)->cellpxy;
  const int cellpxx = ncplane_pile(s->n)->cellpxx;
  memset(auxvec + cellpxx * cellpxy, 0xff, cellpxx * cellpxy);
  sixelmap* smap = s->smap;
  const int startx = xcell * cellpxx;
  const int starty = ycell * cellpxy;
  int endx = ((xcell + 1) * cellpxx) - 1;
  if(endx >= s->pixx){
    endx = s->pixx - 1;
  }
  int endy = ((ycell + 1) * cellpxy) - 1;
  if(endy >= s->pixy){
    endy = s->pixy - 1;
  }
  const int startband = starty / 6;
  const int endband = endy / 6;
//fprintf(stderr, "y/x: %d/%d start: %d/%d end: %d/%d\n", ycell, xcell, starty, startx, endy, endx);
  // walk through each color, and wipe the necessary sixels from each band
  int w = 0;
  for(int c = 0 ; c < smap->colors ; ++c){
    w |= wipe_color(smap, c, startband, endband, startx, endx, starty, endy,
                    s->pixx, cellpxy, cellpxx, auxvec);
  }
  if(w){
    s->wipes_outstanding = true;
  }
  change_p2(s->glyph.buf, SIXEL_P2_TRANS);
  assert(NULL == s->n->tam[s->dimx * ycell + xcell].auxvector);
  s->n->tam[s->dimx * ycell + xcell].auxvector = auxvec;
  // FIXME this invalidation ought not be necessary, since we're simply
  // wiping, and thus a glyph is going to be printed over whatever we've
  // just destroyed. in alacritty, however, this isn't sufficient to knock
  // out a graphic; we need repaint with the transparency.
  // see https://github.com/dankamongmen/notcurses/issues/2142
  int absx, absy;
  ncplane_abs_yx(s->n, &absy, &absx);
  sprixel_invalidate(s, absy, absx);
  return 0;
}

// rebuilds the auxiliary vectors, and scrubs the actual pixels, following
// extraction of the palette. doing so allows the new frame's pixels to
// contribute to the solved palette, even if they were wiped in the previous
// frame. pixels ought thus have been set up in sixel_blit(), despite TAM
// entries in the ANNIHILATED state.
static int
scrub_color_table(sprixel* s){
  if(s->n && s->n->tam){
    // we use the sprixel cell geometry rather than the plane's because this
    // is called during our initial blit, before we've resized the plane.
    for(unsigned y = 0 ; y < s->dimy ; ++y){
      for(unsigned x = 0 ; x < s->dimx ; ++x){
        unsigned txyidx = y * s->dimx + x;
        sprixcell_e state = s->n->tam[txyidx].state;
        if(state == SPRIXCELL_ANNIHILATED || state == SPRIXCELL_ANNIHILATED_TRANS){
//fprintf(stderr, "POSTEXRACT WIPE %d/%d\n", y, x);
          sixel_wipe(s, y, x);
        }
      }
    }
  }
  return 0;
}

// returns the index at which the provided color can be found *in the
// dtable*, possibly inserting it into the ctable. returns -1 if the
// color is not in the table and the table is full.
static int
find_color(sixeltable* stab, unsigned char comps[static RGBSIZE]){
  int i;
  if(stab->map->colors){
    int l, r;
    l = 0;
    r = stab->map->colors - 1;
    do{
      i = l + (r - l) / 2;
//fprintf(stderr, "%02x%02x%02x L %d R %d m %d\n", comps[0], comps[1], comps[2], l, r, i);
      int cmp = memcmp(stab->map->table + i * CENTSIZE, comps, RGBSIZE);
      if(cmp == 0){
        return ctable_to_dtable(stab->map->table + i * CENTSIZE);
      }
      if(cmp < 0){
        l = i + 1;
      }else{ // key is smaller
        r = i - 1;
      }
//fprintf(stderr, "BCMP: %d L %d R %d m: %d\n", cmp, l, r, i);
    }while(l <= r);
    if(r < 0){
      i = 0;
    }else if(l == stab->map->colors){
      i = stab->map->colors;
    }else{
      i = l;
    }
    if(stab->map->colors == stab->colorregs){
      return -1;
    }
    if(i < stab->map->colors){
//fprintf(stderr, "INSERTING COLOR %u %u %u AT %d\n", comps[0], comps[1], comps[2], i);
      memmove(stab->map->table + (i + 1) * CENTSIZE,
              stab->map->table + i * CENTSIZE,
              (stab->map->colors - i) * CENTSIZE);
    }
  }else{
    i = 0;
  }
//fprintf(stderr, "NEW COLOR CONCAT %u %u %u AT %d\n", comps[0], comps[1], comps[2], i);
  memcpy(stab->map->table + i * CENTSIZE, comps, RGBSIZE);
  dtable_to_ctable(stab->map->colors, stab->map->table + i * CENTSIZE);
  ++stab->map->colors;
  return stab->map->colors - 1;
  //return ctable_to_dtable(stab->map->table + i * CENTSIZE);
}

static void
update_deets(uint32_t rgb, cdetails* deets){
  unsigned char comps[RGBSIZE];
  deets->sums[0] += ncpixel_r(rgb);
  deets->sums[1] += ncpixel_g(rgb);
  deets->sums[2] += ncpixel_b(rgb);
  comps[0] = ss(ncpixel_r(rgb), 0xff);
  comps[1] = ss(ncpixel_g(rgb), 0xff);
  comps[2] = ss(ncpixel_b(rgb), 0xff);
  if(deets->count == 0){
    deets->lo[0] = deets->hi[0] = comps[0];
    deets->lo[1] = deets->hi[1] = comps[1];
    deets->lo[2] = deets->hi[2] = comps[2];
  }else{
    if(deets->hi[0] < comps[0]){
      deets->hi[0] = comps[0];
    }else if(deets->lo[0] > comps[0]){
      deets->lo[0] = comps[0];
    }
    if(deets->hi[1] < comps[1]){
      deets->hi[1] = comps[1];
    }else if(deets->lo[1] > comps[1]){
      deets->lo[1] = comps[1];
    }
    if(deets->hi[2] < comps[2]){
      deets->hi[2] = comps[2];
    }else if(deets->lo[2] > comps[2]){
      deets->lo[2] = comps[2];
    }
  }
  ++deets->count;
}

// goes through the needs_refresh matrix, and damages cells needing refreshing.
void sixel_refresh(const ncpile* p, sprixel* s){
  if(s->needs_refresh == NULL){
    return;
  }
  int absy, absx;
  ncplane_abs_yx(s->n, &absy, &absx);
  for(unsigned y = 0 ; y < s->dimy ; ++y){
    const unsigned yy = absy + y;
    for(unsigned x = 0 ; x < s->dimx ; ++x){
      unsigned idx = y * s->dimx + x;
      if(s->needs_refresh[idx]){
        const unsigned xx = absx + x;
        if(xx < p->dimx && yy < p->dimy){
          unsigned ridx = yy * p->dimx + xx;
          struct crender *r = &p->crender[ridx];
          r->s.damaged = 1;
        }
      }
    }
  }
  free(s->needs_refresh);
  s->needs_refresh = NULL;
}

// when we first cross into a new cell, we check its old state, and if it
// was transparent, set the rmatrix low. otherwise, set it high. this should
// only be called for the first pixel in each cell.
static inline void
update_rmatrix(unsigned char* rmatrix, int txyidx, const tament* tam){
  if(rmatrix == NULL){
    return;
  }
  sprixcell_e state = tam[txyidx].state;
  if(state == SPRIXCELL_TRANSPARENT || state > SPRIXCELL_ANNIHILATED){
    rmatrix[txyidx] = 0;
  }else{
    rmatrix[txyidx] = 1;
  }
}

// no mattter the input palette, we can always get a maximum of 64 colors if we
// mask at 0xc0 on each component (this partitions each component into 4 chunks,
// and 4 * 4 * 4 -> 64). so this will never overflow our color register table
// (assumed to have at least 256 registers). at each color, we store a pixel
// count, and a sum of all three channels. in addition, we track whether we've
// seen at least two colors in the chunk.
static inline int
extract_color_table(const uint32_t* data, int linesize, int cols,
                    int leny, int lenx, sixeltable* stab,
                    tament* tam, const blitterargs* bargs){
  const int begx = bargs->begx;
  const int begy = bargs->begy;
  const int cdimy = bargs->u.pixel.cellpxy;
  const int cdimx = bargs->u.pixel.cellpxx;
  unsigned char mask = 0xc0;
  int pos = 0; // pixel position
  unsigned char* rmatrix = bargs->u.pixel.spx->needs_refresh;
  for(int visy = begy ; visy < (begy + leny) ; visy += 6){ // pixel row
    for(int visx = begx ; visx < (begx + lenx) ; visx += 1){ // pixel column
      for(int sy = visy ; sy < (begy + leny) && sy < visy + 6 ; ++sy){ // offset within sprixel
        const uint32_t* rgb = (data + (linesize / 4 * sy) + visx);
        int txyidx = (sy / cdimy) * cols + (visx / cdimx);
        // we can't just check if lastidx != txyidx; that's true for each row
        // of the cell. this will only be true once.
        bool firstpix = (sy % cdimy == 0 && visx % cdimx == 0);
        bool lastrow = visy + 6 >= begy + leny;
        // we do *not* exempt already-wiped pixels from palette creation. once
        // we're done, we'll call sixel_wipe() on these cells. so they remain
        // one of SPRIXCELL_ANNIHILATED or SPRIXCELL_ANNIHILATED_TRANS.
        if(tam[txyidx].state != SPRIXCELL_ANNIHILATED && tam[txyidx].state != SPRIXCELL_ANNIHILATED_TRANS){
          if(rgba_trans_p(*rgb, bargs->transcolor)){
            if(firstpix){
              update_rmatrix(rmatrix, txyidx, tam);
              tam[txyidx].state = SPRIXCELL_TRANSPARENT;
            }else if(tam[txyidx].state == SPRIXCELL_OPAQUE_SIXEL){
              tam[txyidx].state = SPRIXCELL_MIXED_SIXEL;
            }
            stab->p2 = SIXEL_P2_TRANS; // even one forces P2=1
          }else{
            if(firstpix){
              update_rmatrix(rmatrix, txyidx, tam);
              tam[txyidx].state = SPRIXCELL_OPAQUE_SIXEL;
            }else if(tam[txyidx].state == SPRIXCELL_TRANSPARENT){
              tam[txyidx].state = SPRIXCELL_MIXED_SIXEL;
            }
          }
        }else{
//fprintf(stderr, "TRANS SKIP %d %d %d %d (cell: %d %d)\n", visy, visx, sy, txyidx, sy / cdimy, visx / cdimx);
          if(rgba_trans_p(*rgb, bargs->transcolor)){
            if(firstpix){
              update_rmatrix(rmatrix, txyidx, tam);
              tam[txyidx].state = SPRIXCELL_ANNIHILATED_TRANS;
              free(tam[txyidx].auxvector);
              tam[txyidx].auxvector = NULL;
            }
          }else{
            if(firstpix){
              update_rmatrix(rmatrix, txyidx, tam);
              free(tam[txyidx].auxvector);
              tam[txyidx].auxvector = NULL;
            }
            tam[txyidx].state = SPRIXCELL_ANNIHILATED;
          }
          stab->p2 = SIXEL_P2_TRANS; // even one forces P2=1
        }
        if(lastrow){
          bool lastcol = visx + 1 >= begx + lenx;
          if(lastcol){
            // if we're opaque, we needn't clear the old cell with a glyph
            if(tam[txyidx].state == SPRIXCELL_OPAQUE_SIXEL){
              if(rmatrix){
                rmatrix[txyidx] = 0;
              }
            }
          }
        }
        if(rgba_trans_p(*rgb, bargs->transcolor)){
          continue;
        }
        unsigned char comps[RGBSIZE];
        break_sixel_comps(comps, *rgb, mask);
        int c = find_color(stab, comps);
        if(c < 0){
//fprintf(stderr, "FAILED FINDING COLOR AUGH 0x%02x\n", mask);
          return -1;
        }
        stab->map->data[c * stab->map->sixelcount + pos] |= (1u << (sy - visy));
        update_deets(*rgb, &stab->deets[c]);
//fprintf(stderr, "color %d pos %d: 0x%x\n", c, pos, stab->data[c * stab->map->sixelcount + pos]);
//fprintf(stderr, " sums: %u %u %u count: %d r/g/b: %u %u %u\n", stab->deets[c].sums[0], stab->deets[c].sums[1], stab->deets[c].sums[2], stab->deets[c].count, ncpixel_r(*rgb), ncpixel_g(*rgb), ncpixel_b(*rgb));
      }
      ++pos;
    }
  }
  return 0;
}

// run through the sixels matching color |src|, going to color |stab->colors|,
// keeping those under |r||g||b|, and putting those above it into the new
// color. rebuilds both sixel groups and color details.
static void
unzip_color(const uint32_t* data, int linesize, int begy, int begx,
            int leny, int lenx, sixeltable* stab, int src,
            unsigned char rgb[static 3]){
  unsigned char* tcrec = stab->map->table + CENTSIZE * stab->map->colors;
  dtable_to_ctable(stab->map->colors, tcrec);
  cdetails* targdeets = stab->deets + stab->map->colors;
  unsigned char* crec = stab->map->table + CENTSIZE * src;
  int didx = ctable_to_dtable(crec);
  cdetails* deets = stab->deets + didx;
  unsigned char* srcsixels = stab->map->data + stab->map->sixelcount * didx;
  unsigned char* dstsixels = stab->map->data + stab->map->sixelcount * stab->map->colors;
//fprintf(stderr, "counts: src: %d dst: %d src: %p dst: %p\n", deets->count, targdeets->count, srcsixels, dstsixels);
  int sixel = 0;
  memset(deets, 0, sizeof(*deets));
  for(int visy = begy ; visy < (begy + leny) ; visy += 6){
    for(int visx = begx ; visx < (begx + lenx) ; visx += 1, ++sixel){
      if(srcsixels[sixel]){
        for(int sy = visy ; sy < (begy + leny) && sy < visy + 6 ; ++sy){
          if(srcsixels[sixel] & (1u << (sy - visy))){
            const uint32_t* pixel = (const uint32_t*)(data + (linesize / 4 * sy) + visx);
            unsigned char comps[RGBSIZE];
            break_sixel_comps(comps, *pixel, 0xff);
            if(comps[0] > rgb[0] || comps[1] > rgb[1] || comps[2] > rgb[2]){
              dstsixels[sixel] |= (1u << (sy - visy));
              srcsixels[sixel] &= ~(1u << (sy - visy));
              update_deets(*pixel, targdeets);
//fprintf(stderr, "%u/%u/%u comps: [%u/%u/%u]\n", r, g, b, comps[0], comps[1], comps[2]);
//fprintf(stderr, "match sixel %d %u %u\n", sixel, srcsixels[sixel], 1u << (sy - visy));
            }else{
              update_deets(*pixel, deets);
            }
          }
        }
      }
    }
  }
}

// relax segment |coloridx|. we must have room for a new color. we find the
// biggest component gap, and split our color entry in half there. we know
// the elements can't go into any preexisting color entry, so the only
// choices are staying where they are, or going to the new one. "unzip" the
// sixels from the data table by looking back to the sources and classifying
// them in one or the other centry. rebuild our sums, sixels, hi/lo, and
// counts as we do so. anaphase, baybee! target always gets the upper range.
// returns 1 if we did a refinement, 0 otherwise.
static int
refine_color(const uint32_t* data, int linesize, int begy, int begx,
             int leny, int lenx, sixeltable* stab, int color){
  unsigned char* crec = stab->map->table + CENTSIZE * color;
  int didx = ctable_to_dtable(crec);
  cdetails* deets = stab->deets + didx;
  int rdelt = deets->hi[0] - deets->lo[0];
  int gdelt = deets->hi[1] - deets->lo[1];
  int bdelt = deets->hi[2] - deets->lo[2];
  unsigned char rgbmax[3] = { deets->hi[0], deets->hi[1], deets->hi[2] };
  if(gdelt >= rdelt && gdelt >= bdelt){ // split on green
    if(gdelt < 3){
      return 0;
    }
//fprintf(stderr, "[%d->%d] SPLIT ON GREEN %d %d (pop: %d)\n", color, stab->map->colors, deets->hi[1], deets->lo[1], deets->count);
    rgbmax[1] = deets->lo[1] + (deets->hi[1] - deets->lo[1]) / 2;
  }else if(rdelt >= gdelt && rdelt >= bdelt){ // split on red
    if(rdelt < 3){
      return 0;
    }
//fprintf(stderr, "[%d->%d] SPLIT ON RED %d %d (pop: %d)\n", color, stab->map->colors, deets->hi[0], deets->lo[0], deets->count);
    rgbmax[0] = deets->lo[0] + (deets->hi[0] - deets->lo[0]) / 2;
  }else{ // split on blue
    if(bdelt < 3){
      return 0;
    }
//fprintf(stderr, "[%d->%d] SPLIT ON BLUE %d %d (pop: %d)\n", color, stab->map->colors, deets->hi[2], deets->lo[2], deets->count);
    rgbmax[2] = deets->lo[2] + (deets->hi[2] - deets->lo[2]) / 2;
  }
  unzip_color(data, linesize, begy, begx, leny, lenx, stab, color, rgbmax);
  ++stab->map->colors;
  return 1;
}

// relax the details down into free color registers
static void
refine_color_table(const uint32_t* data, int linesize, int begy, int begx,
                   int leny, int lenx, sixeltable* stab){
  while(stab->map->colors < stab->colorregs){
    bool refined = false;
    int tmpcolors = stab->map->colors; // force us to come back through
    for(int i = 0 ; i < tmpcolors ; ++i){
      unsigned char* crec = stab->map->table + CENTSIZE * i;
      int didx = ctable_to_dtable(crec);
      cdetails* deets = stab->deets + didx;
//fprintf(stderr, "[%d->%d] hi: %d %d %d lo: %d %d %d\n", i, didx, deets->hi[0], deets->hi[1], deets->hi[2], deets->lo[0], deets->lo[1], deets->lo[2]);
      if(deets->count > leny * lenx / stab->colorregs){
        if(refine_color(data, linesize, begy, begx, leny, lenx, stab, i)){
          if(stab->map->colors == stab->colorregs){
  //fprintf(stderr, "filled table!\n");
            break;
          }
          refined = true;
        }
      }
    }
    if(!refined){ // no more possible work
      break;
    }
  }
  // we're full!
}

// Emit some number of equivalent, subsequent sixels, using sixel RLE. We've
// seen the sixel |crle| for |seenrle| columns in a row. |seenrle| must > 0.
static int
write_rle(int* printed, int color, fbuf* f, int seenrle, unsigned char crle,
          int* needclosure){
  if(!*printed){
    if(*needclosure){
      if(fbuf_putc(f, '$') != 1){
        return -1;
      }
    }
    if(fbuf_putc(f, '#') != 1){
      return -1;
    }
    if(fbuf_putint(f, color) < 0){
      return -1;
    }
    *printed = 1;
    *needclosure = 0;
  }
  crle += 63;
  if(seenrle == 2){
    if(fbuf_putc(f, crle) != 1){
      return -1;
    }
  }else if(seenrle != 1){
    if(fbuf_putc(f, '!') != 1){
      return -1;
    }
    if(fbuf_putint(f, seenrle) < 0){
      return -1;
    }
  }
  if(fbuf_putc(f, crle) != 1){
    return -1;
  }
  return 0;
}

static inline int
write_sixel_intro(fbuf* f, sixel_p2_e p2, int leny, int lenx){
  int r = fbuf_puts(f, "\x1bP0;");
  if(r < 0){
    return -1;
  }
  int rr = fbuf_putint(f, p2);
  if(rr < 0){
    return -1;
  }
  r += rr;
  rr = fbuf_puts(f, ";0q\"1;1;");
  if(rr < 0){
    return -1;
  }
  r += rr;
  rr = fbuf_putint(f, lenx);
  if(rr < 0){
    return -1;
  }
  r += rr;
  if(fbuf_putc(f, ';') != 1){
    return -1;
  }
  ++r;
  rr = fbuf_putint(f, leny);
  if(rr < 0){
    return -1;
  }
  r += rr;
  return r;
}

// write a single color register. rc/gc/bc are on [0..100].
static inline int
write_sixel_creg(fbuf* f, int idx, int rc, int gc, int bc){
  int r = 0;
  if(fbuf_putc(f, '#') != 1){
    return -1;
  }
  ++r;
  int rr = fbuf_putint(f, idx);
  if(rr < 0){
    return -1;
  }
  r += rr;
  rr = fbuf_puts(f, ";2;");
  if(rr < 0){
    return -1;
  }
  r += rr;
  rr = fbuf_putint(f, rc);
  if(rr < 0){
    return -1;
  }
  r += rr;
  if(fbuf_putc(f, ';') != 1){
    return -1;
  }
  ++r;
  rr = fbuf_putint(f, gc);
  if(rr < 0){
    return -1;
  }
  r += rr;
  if(fbuf_putc(f, ';') != 1){
    return -1;
  }
  ++r;
  rr = fbuf_putint(f, bc);
  if(rr < 0){
    return -1;
  }
  r += rr;
  return r;
}

// write the escape which opens a Sixel, plus the palette table. returns the
// number of bytes written, so that this header can be directly copied in
// future reencodings. |leny| and |lenx| are output pixel geometry.
// returns the number of bytes written, so it can be stored at *parse_start.
static int
write_sixel_header(fbuf* f, int leny, int lenx, const sixeltable* stab, sixel_p2_e p2){
  if(leny % 6){
    return -1;
  }
  // Set Raster Attributes - pan/pad=1 (pixel aspect ratio), Ph=lenx, Pv=leny
  int r = write_sixel_intro(f, p2, leny, lenx);
  if(r < 0){
    return -1;
  }
  for(int i = 0 ; i < stab->map->colors ; ++i){
    const unsigned char* rgb = stab->map->table + i * CENTSIZE;
    int idx = ctable_to_dtable(rgb);
    int count = stab->deets[idx].count;
//fprintf(stderr, "RGB: %3u(%d) %3u(%d) %3u(%d) DT: %d SUMS: %3ld %3ld %3ld COUNT: %d\n", rgb[0], ss(rgb[0], 0xff), rgb[1], ss(rgb[1], 0xff), rgb[2], ss(rgb[2], 0xff), idx, stab->deets[idx].sums[0] / count * 100 / 255, stab->deets[idx].sums[1] / count * 100 / 255, stab->deets[idx].sums[2] / count * 100 / 255, count);
    //fprintf(fp, "#%d;2;%u;%u;%u", i, rgb[0], rgb[1], rgb[2]);
    // we emit the average of the actual sums rather than the RGB clustering
    // point, as it can be (and usually is) much more accurate.
    int rr = write_sixel_creg(f, i, (stab->deets[idx].sums[0] * 100 / count / 255),
                              (stab->deets[idx].sums[1] * 100 / count / 255),
                              (stab->deets[idx].sums[2] * 100 / count / 255));
    if(rr < 0){
      return -1;
    }
    r += rr;
  }
  return r;
}

static int
write_sixel_payload(fbuf* f, int lenx, const sixelmap* map){
  int p = 0;
  while(p < map->sixelcount){
    int needclosure = 0;
    for(int i = 0 ; i < map->colors ; ++i){
      int seenrle = 0; // number of repetitions
      unsigned char crle = 0; // character being repeated
      int idx = ctable_to_dtable(map->table + i * CENTSIZE);
      int printed = 0;
      for(int m = p ; m < map->sixelcount && m < p + lenx ; ++m){
//fprintf(stderr, "%d ", idx * map->sixelcount + m);
//fputc(map->data[idx * map->sixelcount + m] + 63, stderr);
        if(seenrle){
          if(map->data[idx * map->sixelcount + m] == crle){
            ++seenrle;
          }else{
            if(write_rle(&printed, i, f, seenrle, crle, &needclosure)){
              return -1;
            }
            seenrle = 1;
            crle = map->data[idx * map->sixelcount + m];
          }
        }else{
          seenrle = 1;
          crle = map->data[idx * map->sixelcount + m];
        }
      }
      if(crle){
        if(write_rle(&printed, i, f, seenrle, crle, &needclosure)){
          return -1;
        }
      }
      needclosure = needclosure | printed;
    }
    if(p + lenx < map->sixelcount){
      if(fbuf_putc(f, '-') != 1){
        return -1;
      }
    }
    p += lenx;
  }
  if(fbuf_puts(f, "\e\\") < 0){
    return -1;
  }
  return 0;
}

// emit the sixel in its entirety, plus escapes to start and end pixel mode.
// only called the first time we encode; after that, the palette remains
// constant, and is simply copied. fclose()s |fp| on success. |outx| and |outy|
// are output geometry.
static int
write_sixel(fbuf* f, int outy, int outx, const sixeltable* stab,
            int* parse_start, sixel_p2_e p2){
  *parse_start = write_sixel_header(f, outy, outx, stab, p2);
  if(*parse_start < 0){
    return -1;
  }
  if(write_sixel_payload(f, outx, stab->map) < 0){
    return -1;
  }
  return 0;
}

// once per render cycle (if needed), make the actual payload match the TAM. we
// don't do these one at a time due to the complex (expensive) process involved
// in regenerating a sixel (we can't easily do it in-place). anything newly
// ANNIHILATED (state is ANNIHILATED, but no auxvec present) is dropped from
// the payload, and an auxvec is generated. anything newly restored (state is
// OPAQUE_SIXEL or MIXED_SIXEL, but an auxvec is present) is restored to the
// payload, and the auxvec is freed. none of this takes effect until the sixel
// is redrawn, and annihilated sprixcells still require a glyph to be emitted.
static inline int
sixel_reblit(sprixel* s){
  fbuf f;
  if(fbuf_init(&f)){
    return -1;
  }
  if(fbuf_putn(&f, s->glyph.buf, s->parse_start) != s->parse_start){
    fbuf_free(&f);
    return -1;
  }
  if(write_sixel_payload(&f, s->pixx, s->smap) < 0){
    fbuf_free(&f);
    return -1;
  }
  fbuf_free(&s->glyph);
  // FIXME update P2 if necessary
  memcpy(&s->glyph, &f, sizeof(f));
  return 0;
}

// Sixel blitter. Sixels are stacks 6 pixels high, and 1 pixel wide. RGB colors
// are programmed as a set of registers, which are then referenced by the
// stacks. There is also a RLE component, handled in rasterization.
// A pixel block is indicated by setting cell_pixels_p(). |leny| and |lenx| are
// scaled geometry in pixels. We calculate output geometry herein, and supply
// transparent filler input for any missing rows.
static inline int
sixel_blit_inner(int leny, int lenx, sixeltable* stab, const blitterargs* bargs, tament* tam){
  fbuf f;
  if(fbuf_init(&f)){
    return -1;
  }
  sprixel* s = bargs->u.pixel.spx;
  const int cellpxy = bargs->u.pixel.cellpxy;
  const int cellpxx = bargs->u.pixel.cellpxx;
  int parse_start = 0;
  int outy = leny;
  if(leny % 6){
    outy += 6 - (leny % 6);
    stab->p2 = SIXEL_P2_TRANS;
  }
  // calls fclose() on success
  if(write_sixel(&f, outy, lenx, stab, &parse_start, stab->p2)){
    fbuf_free(&f);
    return -1;
  }
  scrub_tam_boundaries(tam, outy, lenx, cellpxy, cellpxx);
  // take ownership of buf on success
  if(plane_blit_sixel(s, &f, outy, lenx, parse_start, tam, SPRIXEL_INVALIDATED) < 0){
    fbuf_free(&f);
    return -1;
  }
  // we're keeping the buf remnants
  sixelmap_trim(stab->map);
  s->smap = stab->map;
  return 1;
}

// |leny| and |lenx| are the scaled output geometry. we take |leny| up to the
// nearest multiple of six greater than or equal to |leny|.
int sixel_blit(ncplane* n, int linesize, const void* data, int leny, int lenx,
               const blitterargs* bargs){
  int colorregs = bargs->u.pixel.colorregs;
  if(colorregs > 256){
    colorregs = 256;
  }
  assert(colorregs >= 64);
  sixeltable stable = {
    .map = sixelmap_create(colorregs, leny - bargs->begy, lenx - bargs->begx),
    .deets = malloc(colorregs * sizeof(cdetails)),
    .colorregs = colorregs,
    .p2 = SIXEL_P2_ALLOPAQUE,
  };
  if(stable.deets == NULL || stable.map == NULL){
    sixelmap_free(stable.map);
    free(stable.deets);
    return -1;
  }
  // stable.table doesn't need initializing; we start from the bottom
  memset(stable.deets, 0, sizeof(*stable.deets) * colorregs);
  int cols = bargs->u.pixel.spx->dimx;
  int rows = bargs->u.pixel.spx->dimy;
  typeof(bargs->u.pixel.spx->needs_refresh) rmatrix;
  rmatrix = malloc(sizeof(*rmatrix) * rows * cols);
  if(rmatrix == NULL){
    sixelmap_free(stable.map);
    free(stable.deets);
    return -1;
  }
  bargs->u.pixel.spx->needs_refresh = rmatrix;
  assert(n->tam);
  if(extract_color_table(data, linesize, cols, leny, lenx, &stable, n->tam, bargs)){
    free(bargs->u.pixel.spx->needs_refresh);
    sixelmap_free(stable.map);
    free(stable.deets);
    return -1;
  }
  refine_color_table(data, linesize, bargs->begy, bargs->begx, leny, lenx, &stable);
  // takes ownership of sixelmap on success
  int r = sixel_blit_inner(leny, lenx, &stable, bargs, n->tam);
  if(r < 0){
    sixelmap_free(stable.map);
  }
  free(stable.deets);
  scrub_color_table(bargs->u.pixel.spx);
  return r;
}

// to destroy a sixel, we damage all cells underneath it. we might not have
// to, though, if we've got a new sixel ready to go where the old sixel was
// (though we'll still need to if the new sprixcell not opaque, and the
// old and new sprixcell are different in any transparent pixel).
int sixel_scrub(const ncpile* p, sprixel* s){
  loginfo("%d state %d at %d/%d (%d/%d)\n", s->id, s->invalidated, s->movedfromy, s->movedfromx, s->dimy, s->dimx);
  int starty = s->movedfromy;
  int startx = s->movedfromx;
  for(int yy = starty ; yy < starty + (int)s->dimy && yy < (int)p->dimy ; ++yy){
    for(int xx = startx ; xx < startx + (int)s->dimx && xx < (int)p->dimx ; ++xx){
      int ridx = yy * p->dimx + xx;
      struct crender *r = &p->crender[ridx];
      if(!s->n){
        // need this to damage cells underneath a sprixel we're removing
        r->s.damaged = 1;
        continue;
      }
      sprixel* trues = r->sprixel ? r->sprixel : s;
      if(yy >= (int)trues->n->leny || yy - trues->n->absy < 0){
        r->s.damaged = 1;
        continue;
      }
      if(xx >= (int)trues->n->lenx || xx - trues->n->absx < 0){
        r->s.damaged = 1;
        continue;
      }
      sprixcell_e state = sprixel_state(trues, yy, xx);
//fprintf(stderr, "CHECKING %d/%d state: %d %d/%d\n", yy - s->movedfromy - s->n->absy, xx - s->movedfromx - s->n->absx, state, yy, xx);
      if(state == SPRIXCELL_TRANSPARENT || state == SPRIXCELL_MIXED_SIXEL){
        r->s.damaged = 1;
      }else if(s->invalidated == SPRIXEL_MOVED){
        // ideally, we wouldn't damage our annihilated sprixcells, but if
        // we're being annihilated only during this cycle, we need to go
        // ahead and damage it.
        r->s.damaged = 1;
      }
    }
  }
  return 1;
}

// returns the number of bytes written
int sixel_draw(const tinfo* ti, const ncpile* p, sprixel* s, fbuf* f,
               int yoff, int xoff){
  (void)ti;
  // if we've wiped or rebuilt any cells, effect those changes now, or else
  // we'll get flicker when we move to the new location.
  if(s->wipes_outstanding){
    if(sixel_reblit(s)){
      return -1;
    }
    s->wipes_outstanding = false;
  }
  if(p){
    const int targy = s->n->absy + yoff;
    const int targx = s->n->absx + xoff;
    if(goto_location(p->nc, f, targy, targx, NULL)){
      return -1;
    }
    if(s->invalidated == SPRIXEL_MOVED){
      for(int yy = s->movedfromy ; yy < s->movedfromy + (int)s->dimy && yy < (int)p->dimy ; ++yy){
        if(yy < 0){
          continue;
        }
        for(int xx = s->movedfromx ; xx < s->movedfromx + (int)s->dimx && xx < (int)p->dimx ; ++xx){
          if(xx < 0){
            continue;
          }
          struct crender *r = &p->crender[yy * p->dimx + xx];
          if(!r->sprixel || sprixel_state(r->sprixel, yy, xx) != SPRIXCELL_OPAQUE_SIXEL){
            r->s.damaged = 1;
          }
        }
      }
    }
  }
  if(fbuf_putn(f, s->glyph.buf, s->glyph.used) < 0){
    return -1;
  }
  s->invalidated = SPRIXEL_QUIESCENT;
  return s->glyph.used;
}

// private mode 80 (DECSDM) manages "Sixel Scrolling Mode" vs "Sixel Display
// Mode". when 80 is enabled (i.e. DECSDM mode), images are displayed at the
// upper left, and clipped to the window. we don't want either of those things
// to happen, so we explicitly disable DECSDM.
// private mode 8452 places the cursor at the end of a sixel when it's
//  emitted. we don't need this for rendered mode, but we do want it for
//  direct mode. it causes us no problems, so always set it.
int sixel_init(int fd){
  return tty_emit("\e[?80l\e[?8452h", fd);
}

int sixel_init_inverted(int fd){
  // some terminals, at some versions, invert the sense of DECSDM. for those,
  // we must use 80h rather than the correct 80l. this grows out of a
  // misunderstanding in XTerm through patchlevel 368, which was widely
  // copied into other terminals.
  return tty_emit("\e[?80h\e[?8452h", fd);
}

// only called for cells in SPRIXCELL_ANNIHILATED[_TRANS]. just post to
// wipes_outstanding, so the Sixel gets regenerated the next render cycle,
// just like wiping. this is necessary due to the complex nature of
// modifying a Sixel -- we want to do them all in one batch.
int sixel_rebuild(sprixel* s, int ycell, int xcell, uint8_t* auxvec){
  s->wipes_outstanding = true;
  sixelmap* smap = s->smap;
  const int cellpxx = ncplane_pile(s->n)->cellpxx;
  const int cellpxy = ncplane_pile(s->n)->cellpxy;
  const int startx = xcell * cellpxx;
  const int starty = ycell * cellpxy;
  int endx = ((xcell + 1) * cellpxx) - 1;
  if(endx > s->pixx){
    endx = s->pixx;
  }
  int endy = ((ycell + 1) * cellpxy) - 1;
  if(endy > s->pixy){
    endy = s->pixy;
  }
  int transparent = 0;
//fprintf(stderr, "%d/%d start: %d/%d end: %d/%d bands: %d-%d\n", ycell, xcell, starty, startx, endy, endx, starty / 6, endy / 6);
  for(int x = startx ; x <= endx ; ++x){
    for(int y = starty ; y <= endy ; ++y){
      int auxvecidx = (y - starty) * cellpxx + (x - startx);
      int trans = auxvec[cellpxx * cellpxy + auxvecidx];
      if(!trans){
        int color = auxvec[auxvecidx];
        int didx = ctable_to_dtable(smap->table + color * CENTSIZE);
        int coff = smap->sixelcount * didx;
        int band = y / 6;
        int boff = coff + band * s->pixx;
        int xoff = boff + x;
//fprintf(stderr, "DIDX: %d %d/%d band: %d coff: %d boff: %d rebuild %d/%d with color %d from %d %p xoff: %d\n", didx, ycell, xcell, band, coff, boff, y, x, color, auxvecidx, auxvec, xoff);
        s->smap->data[xoff] |= (1u << (y % 6));
      }else{
        ++transparent;
      }
    }
  }
  sprixcell_e newstate;
  if(transparent == cellpxx * cellpxy){
    newstate = SPRIXCELL_TRANSPARENT;
  }else if(transparent){
    newstate = SPRIXCELL_MIXED_SIXEL;
  }else{
    newstate = SPRIXCELL_OPAQUE_SIXEL;
  }
  s->n->tam[s->dimx * ycell + xcell].state = newstate;
  return 1;
}

int sixel_shutdown(fbuf* f){
  (void)f;
  // no way to know what the state was before; we ought use XTSAVE/XTRESTORE
  return 0;
}

uint8_t* sixel_trans_auxvec(const ncpile* p){
  const size_t slen = 2 * p->cellpxy * p->cellpxx;
  uint8_t* a = malloc(slen);
  if(a){
    memset(a, 0, slen);
  }
  return a;
}