Skip to content

Free games for graphing calculators: NumWorks, TI-Nspire CX, Casio fx-CG50 and soon TI-84 Plus CE. Balatro, Celeste, Hollow Knight, Minecraft and more.

14.0 KB
Raw Blame
/* The pictures (tools/codec.py, as Five Nights at Freddy's 4's): 16 x 16 squares coded as JPEG codes them.
 *
 * A square: four 8 x 8 blocks of Y, one of Cb and one of Cr (at half resolution), each a Huffman-coded
 * list of quantized cosine coefficients. The inverse transform is libjpeg's "ifast" one (the AAN algorithm,
 * its scales folded into the quantization tables by tools/pack.py), with a shortcut for blocks of one flat
 * colour. Colours are dithered on the way to 16 bits.
 *
 * Screens are decoded as the bands are drawn (pic_draw). A battlefield's terrain is decoded once, when the
 * level starts, into a byte a pixel: its own 256 colours (BGPAL), each pixel the nearest of them (bg_load). */
#include "gfx.h"
#include "res.h"

typedef struct {
  const uint16_t *lut;     /* 9 bits ahead: length << 8 | symbol, 0 when the code is longer */
  const int32_t *maxcode;  /* JPEG's, by length (1 to 17) */
  const int32_t *valoff;
  const uint8_t *vals;
} Huff;

static const uint8_t zigzag[64 + 16] = {
  0, 1, 8, 16, 9, 2, 3, 10, 17, 24, 32, 25, 18, 11, 4, 5, 12, 19, 26, 33, 40, 48, 41, 34, 27, 20, 13, 6, 7,
  14, 21, 28, 35, 42, 49, 56, 57, 50, 43, 36, 29, 22, 15, 23, 30, 37, 44, 51, 58, 59, 52, 45, 38, 31, 39, 46,
  53, 60, 61, 54, 47, 55, 62, 63,
  63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63   /* (a corrupt run lands here) */
};

static Huff huff_tab(int k) {
  const uint8_t *p = section(SEC_HUFF) + 1424 * k;
  return (Huff){(const uint16_t *)(const void *)p, (const int32_t *)(const void *)(p + 1024),
                (const int32_t *)(const void *)(p + 1096), p + 1168};
}

/* ------------------------------------------------------------------ bits */
typedef struct {
  const uint8_t *p;
  uint32_t buf;   /* the next bits, from the top */
  int n;
} Bits;

static inline void fill(Bits *b) {
  while (b->n <= 24) {
    b->buf |= (uint32_t)*b->p++ << (24 - b->n);
    b->n += 8;
  }
}
static inline uint32_t take(Bits *b, int k) {
  uint32_t v = b->buf >> (32 - k);
  b->buf <<= k;
  b->n -= k;
  return v;
}
static inline int decode(Bits *b, const Huff *h) {
  fill(b);
  uint32_t e = h->lut[b->buf >> 23];
  if (e) {
    b->buf <<= e >> 8;
    b->n -= (int)(e >> 8);
    return (int)(e & 0xFF);
  }
  for (int l = 10; l <= 16; l++) {
    int32_t code = (int32_t)(b->buf >> (32 - l));
    if (code <= h->maxcode[l]) {
      b->buf <<= l;
      b->n -= l;
      return h->vals[(code + h->valoff[l]) & 0xFF];
    }
  }
  b->buf <<= 16;   /* (corrupt: give up on this block) */
  b->n -= 16;
  return 0;
}
/* JPEG's extension of s bits to a signed value */
static inline int value(Bits *b, int s) {
  if (!s) return 0;
  fill(b);
  int v = (int)take(b, s);
  return v < 1 << (s - 1) ? v - (1 << s) + 1 : v;
}

/* ------------------------------------------------------------------ one block */
#define CONST_BITS 8
#define MUL(v, c) (((v) * (c)) >> CONST_BITS)
#define FIX_1_082392200 277
#define FIX_1_414213562 362
#define FIX_1_847759065 473
#define FIX_2_613125930 669

static inline uint8_t clamp8(int v) { return (uint8_t)(v < 0 ? 0 : v > 255 ? 255 : v); }

/* decodes a block into out (8 x 8 bytes, stride 8); *pred: the DC before it */
static void block(Bits *b, const Huff *dc, const Huff *ac, int *pred, const uint16_t *q, uint8_t *out) {
  int32_t c[64];
  uint64_t cols = 0;   /* which coefficients are not 0, a bit each */
  int s = decode(b, dc);
  *pred += value(b, s);
  int dcv = *pred * q[0];
  for (int k = 1; k < 64;) {
    int rs = decode(b, ac), r = rs >> 4;
    s = rs & 15;
    if (!s) {
      if (r != 15) break;
      k += 16;
      continue;
    }
    k += r;
    if (k > 63) break;
    int z = zigzag[k++];
    cols |= (uint64_t)1 << z;
    c[z] = value(b, s) * q[z];
  }
  if (!cols) {   /* one colour */
    uint8_t v = clamp8(((dcv + 16) >> 5) + 128);
    uint32_t w = v * 0x01010101u;
    for (int i = 0; i < 16; i++) ((uint32_t *)(void *)out)[i] = w;
    return;
  }
  c[0] = dcv;
  int32_t ws[64];
  for (int x = 0; x < 8; x++) {   /* columns */
    int32_t *in = c + x, *o = ws + x;
#define IN(k) ((cols >> (x + 8 * (k)) & 1) ? in[8 * (k)] : 0)
    if (!(cols >> 8 & (0x01010101010101ull << x))) {
      int32_t d = x ? IN(0) : dcv;
      for (int k = 0; k < 8; k++) o[8 * k] = d;
      continue;
    }
    int32_t t0 = x ? IN(0) : dcv, t1 = IN(2), t2 = IN(4), t3 = IN(6);
    int32_t t10 = t0 + t2, t11 = t0 - t2, t13 = t1 + t3, t12 = MUL(t1 - t3, FIX_1_414213562) - t13;
    t0 = t10 + t13, t3 = t10 - t13, t1 = t11 + t12, t2 = t11 - t12;
    int32_t t4 = IN(1), t5 = IN(3), t6 = IN(5), t7 = IN(7);
#undef IN
    int32_t z13 = t6 + t5, z10 = t6 - t5, z11 = t4 + t7, z12 = t4 - t7;
    t7 = z11 + z13;
    t11 = MUL(z11 - z13, FIX_1_414213562);
    int32_t z5 = MUL(z10 + z12, FIX_1_847759065);
    t10 = MUL(z12, FIX_1_082392200) - z5;
    t12 = MUL(z10, -FIX_2_613125930) + z5;
    t6 = t12 - t7, t5 = t11 - t6, t4 = t10 + t5;
    o[0] = t0 + t7, o[56] = t0 - t7, o[8] = t1 + t6, o[48] = t1 - t6;
    o[16] = t2 + t5, o[40] = t2 - t5, o[32] = t3 + t4, o[24] = t3 - t4;
  }
  for (int y = 0; y < 8; y++) {   /* rows: +128 and rounding folded into the first */
    int32_t *w = ws + 8 * y;
    uint8_t *o = out + 8 * y;
    int32_t w0 = w[0] + (128 << 5) + 16;
    int32_t t10 = w0 + w[4], t11 = w0 - w[4], t13 = w[2] + w[6], t12 = MUL(w[2] - w[6], FIX_1_414213562) - t13;
    int32_t t0 = t10 + t13, t3 = t10 - t13, t1 = t11 + t12, t2 = t11 - t12;
    int32_t z13 = w[5] + w[3], z10 = w[5] - w[3], z11 = w[1] + w[7], z12 = w[1] - w[7];
    int32_t t7 = z11 + z13, t11b = MUL(z11 - z13, FIX_1_414213562), z5 = MUL(z10 + z12, FIX_1_847759065);
    int32_t t10b = MUL(z12, FIX_1_082392200) - z5, t12b = MUL(z10, -FIX_2_613125930) + z5;
    int32_t t6 = t12b - t7, t5 = t11b - t6, t4 = t10b + t5;
    o[0] = clamp8((t0 + t7) >> 5), o[7] = clamp8((t0 - t7) >> 5);
    o[1] = clamp8((t1 + t6) >> 5), o[6] = clamp8((t1 - t6) >> 5);
    o[2] = clamp8((t2 + t5) >> 5), o[5] = clamp8((t2 - t5) >> 5);
    o[4] = clamp8((t3 + t4) >> 5), o[3] = clamp8((t3 - t4) >> 5);
  }
}

/* ------------------------------------------------------------------ one square */
#if defined(__ARM_FEATURE_SAT)
#include <arm_acle.h>
#define SAT8(v) __usat(v, 8)
#else
#define SAT8(v) ((v) < 0 ? 0 : (v) > 255 ? 255 : (v))
#endif
/* a 4 x 4 ordered dither: what is added to red and blue (0 to 7) and green (0 to 3) before they lose bits */
static const uint8_t dither_rb[4][4] = {{0, 4, 1, 5}, {6, 2, 7, 3}, {1, 5, 0, 4}, {7, 3, 6, 2}};
static const uint8_t dither_g[4][4] = {{0, 2, 0, 2}, {3, 1, 3, 1}, {0, 2, 0, 2}, {3, 1, 3, 1}};

/* decodes the square at data into dst (16 x 16, rows stride apart) */
static void square(const uint8_t *data, int qset, uint16_t *dst, int stride) {
  static Huff h[4];
  static const uint8_t *loaded;
  if (loaded != kr_bin) {
    for (int k = 0; k < 4; k++) h[k] = huff_tab(k);
    loaded = kr_bin;
  }
  const uint16_t *qy = (const uint16_t *)(const void *)(section(SEC_QUANT) + 256 * qset), *qc = qy + 64;
  uint8_t y[4][64] __attribute__((aligned(4))), cb[64] __attribute__((aligned(4))), cr[64] __attribute__((aligned(4)));
  Bits b = {data, 0, 0};
  int pred = 0;
  for (int k = 0; k < 4; k++) block(&b, &h[0], &h[1], &pred, qy, y[k]);
  pred = 0;
  block(&b, &h[2], &h[3], &pred, qc, cb);
  pred = 0;
  block(&b, &h[2], &h[3], &pred, qc, cr);
  for (int rp = 0; rp < 8; rp++) {   /* two rows at a time, sharing their colours */
    int dr[8], dg[8], db[8];
    for (int c = 0; c < 8; c++) {
      int u = cb[rp * 8 + c] - 128, v = cr[rp * 8 + c] - 128;
      dr[c] = (91881 * v + 32768) >> 16;
      dg[c] = (-22554 * u - 46802 * v + 32768) >> 16;
      db[c] = (116130 * u + 32768) >> 16;
    }
    for (int r = 2 * rp; r < 2 * rp + 2; r++) {
      const uint8_t *yl = y[(r >> 3) * 2] + (r & 7) * 8, *drb = dither_rb[r & 3], *dgg = dither_g[r & 3];
      uint16_t *o = dst + r * stride;
      for (int c = 0; c < 16; c++) {
        if (c == 8) yl = y[(r >> 3) * 2 + 1] + (r & 7) * 8;
        int l = yl[c & 7], k = c >> 1;
        int R = SAT8(l + dr[k] + drb[c & 3]), G = SAT8(l + dg[k] + dgg[c & 3]), B = SAT8(l + db[k] + drb[(c + 2) & 3]);
        o[c] = (uint16_t)((R & 0xF8) << 8 | (G & 0xFC) << 3 | B >> 3);
      }
    }
  }
}

/* ------------------------------------------------------------------ pictures */
typedef struct {
  int mw, mh, q;
  const uint8_t *table, *base_table;   /* base_table: the picture whose squares it shares, or NULL */
  int count;                           /* its own squares then */
} Info;

static Info info(int id) {
  const uint8_t *p = section(SEC_PICS) + 12 * id, *t = section(SEC_TABLE);
  Info i = {p[0], p[1], p[2], t + rd32(p + 8), NULL, (int)rd16(p + 6)};
  uint32_t base = rd16(p + 4);
  if (base != 0xFFFF) i.base_table = t + rd32(section(SEC_PICS) + 12 * base + 8);
  return i;
}

static uint32_t square_at(const Info *i, int k) {
  if (!i->base_table) return rd24(i->table + 3 * k);
  int lo = 0, hi = i->count - 1;
  while (lo <= hi) {
    int mid = (lo + hi) >> 1, mk = (int)rd16(i->table + 5 * mid);
    if (mk == k) return rd24(i->table + 5 * mid + 2);
    if (mk < k) lo = mid + 1;
    else hi = mid - 1;
  }
  return rd24(i->base_table + 3 * k);
}

#if NP_SOFT_FLOAT
/* (calculators with RAM to spare and a slower CPU: the squares decoded are kept, by their codes' place) */
#include <stdlib.h>
#include <string.h>
typedef struct {
  const uint8_t *data;
  int q;
  uint16_t px[256];
} Kept;
static Kept *kept;
static uint32_t kept_bits;
static bool kept_tried;

static const uint16_t *kept_square(const uint8_t *data, int q) {
  if (!kept_tried) {
    kept_tried = true;
    for (kept_bits = 11; kept_bits >= 6 && !(kept = malloc(sizeof(Kept) << kept_bits)); kept_bits--) {}
    if (kept)
      for (uint32_t i = 0; i < 1u << kept_bits; i++) kept[i].data = NULL;
  }
  if (!kept) return NULL;
  Kept *k = &kept[(uint32_t)(uintptr_t)data * 2654435761u >> (32 - kept_bits)];
  if (k->data != data || k->q != q) {
    square(data, q, k->px, 16);
    k->data = data, k->q = q;
  }
  return k->px;
}

void pic_end(void) {
  free(kept);
  kept = NULL, kept_tried = false;
}
#endif

int pic_w(int id) { return 16 * section(SEC_PICS)[12 * id]; }
int pic_h(int id) { return 16 * section(SEC_PICS)[12 * id + 1]; }

void pic_part(int id, int x, int y, int sx, int sy, int w, int h) {
  Info in = info(id);
  /* clip to the screen, the band and the picture */
  int x0 = x > 0 ? x : 0, x1 = x + w < SCREEN_W ? x + w : SCREEN_W;
  int y0 = y > gfx_y0 ? y : gfx_y0, y1 = y + h < gfx_y0 + BAND_H ? y + h : gfx_y0 + BAND_H;
  if (x0 >= x1 || y0 >= y1) return;
  const uint8_t *bank = section(SEC_BANK);
  uint16_t px[256];
  /* in the picture: rows y0 - y + sy to y1 - y + sy, columns likewise */
  int pr0 = y0 - y + sy, pr1 = y1 - y + sy, pc0 = x0 - x + sx, pc1 = x1 - x + sx;
  for (int my = pr0 >> 4; my <= (pr1 - 1) >> 4 && my < in.mh; my++)
    for (int mx = pc0 >> 4; mx <= (pc1 - 1) >> 4 && mx < in.mw; mx++) {
      const uint8_t *data = bank + square_at(&in, my * in.mw + mx);
      int r0 = my * 16 > pr0 ? my * 16 : pr0, r1 = my * 16 + 16 < pr1 ? my * 16 + 16 : pr1;
      int c0 = mx * 16 > pc0 ? mx * 16 : pc0, c1 = mx * 16 + 16 < pc1 ? mx * 16 + 16 : pc1;
#if NP_SOFT_FLOAT
      const uint16_t *k = kept_square(data, in.q);
      if (k) {
        for (int r = r0; r < r1; r++)
          memcpy(gfx_band + (r - sy + y - gfx_y0) * SCREEN_W + (c0 - sx + x), k + (r - my * 16) * 16 + (c0 - mx * 16),
                 (size_t)(c1 - c0) * 2);
        continue;
      }
#endif
      if (r1 - r0 == 16 && c1 - c0 == 16) {   /* all of it shows: straight into the band */
        square(data, in.q, gfx_band + (r0 - sy + y - gfx_y0) * SCREEN_W + (c0 - sx + x), SCREEN_W);
        continue;
      }
      square(data, in.q, px, 16);
      for (int r = r0; r < r1; r++) {
        uint16_t *d = gfx_band + (r - sy + y - gfx_y0) * SCREEN_W + (c0 - sx + x);
        const uint16_t *s = px + (r - my * 16) * 16 + (c0 - mx * 16);
        for (int c = c0; c < c1; c++) *d++ = *s++;
      }
    }
}

void pic_draw(int id, int x, int y) { pic_part(id, x, y, 0, 0, pic_w(id), pic_h(id)); }

/* ------------------------------------------------------------------ the terrain, a byte a pixel */
static uint8_t *bg_mem;
static int bg_w, bg_h;
static uint16_t bg_pal[256], bg_pal_dim[256];
static bool bg_dark;

void bg_load(int id, uint8_t *mem) {
  Info in = info(id);
  bg_mem = mem, bg_w = in.mw * 16, bg_h = in.mh * 16;
  const uint8_t *pal = section(SEC_BGPAL) + 512 * id;
  for (int i = 0; i < 256; i++) {
    bg_pal[i] = (uint16_t)rd16(pal + 2 * i);
    bg_pal_dim[i] = gfx_mix(BLACK, bg_pal[i], 14);
  }
  /* the nearest of the 256 colours for each colour of 12 bits */
  static uint8_t near[4096];
  int16_t pr[256], pg[256], pb[256];
  for (int i = 0; i < 256; i++)
    pr[i] = (int16_t)((bg_pal[i] >> 11) * 255 / 31), pg[i] = (int16_t)((bg_pal[i] >> 5 & 63) * 255 / 63),
    pb[i] = (int16_t)((bg_pal[i] & 31) * 255 / 31);
  for (int c = 0; c < 4096; c++) {
    int r = (c >> 8) * 17, g = (c >> 4 & 15) * 17, b = (c & 15) * 17, best = 0, bd = 1 << 30;
    for (int i = 0; i < 256; i++) {
      int d = 2 * (r - pr[i]) * (r - pr[i]) + 4 * (g - pg[i]) * (g - pg[i]) + 3 * (b - pb[i]) * (b - pb[i]);
      if (d < bd) bd = d, best = i;
    }
    near[c] = (uint8_t)best;
  }
  const uint8_t *bank = section(SEC_BANK);
  uint16_t px[256];
  for (int my = 0; my < in.mh; my++)
    for (int mx = 0; mx < in.mw; mx++) {
      square(bank + square_at(&in, my * in.mw + mx), in.q, px, 16);
      for (int r = 0; r < 16; r++) {
        uint8_t *d = mem + (my * 16 + r) * bg_w + mx * 16;
        for (int c = 0; c < 16; c++) {
          uint16_t v = px[r * 16 + c];
          d[c] = near[(v >> 12) << 8 | (v >> 7 & 15) << 4 | (v >> 1 & 15)];
        }
      }
    }
}

void bg_dim(bool dim) { bg_dark = dim; }

void bg_draw(int x, int y) {
  int y0 = gfx_y0 > y ? gfx_y0 : y, y1 = gfx_y0 + BAND_H < y + bg_h ? gfx_y0 + BAND_H : y + bg_h;
  int x0 = x > 0 ? x : 0, x1 = x + bg_w < SCREEN_W ? x + bg_w : SCREEN_W;
  const uint16_t *pal = bg_dark ? bg_pal_dim : bg_pal;
  for (int sy = y0; sy < y1; sy++) {
    const uint8_t *s = bg_mem + (sy - y) * bg_w + (x0 - x);
    uint16_t *d = gfx_band + (sy - gfx_y0) * SCREEN_W + x0;
    for (int k = x1 - x0; k > 0; k--) *d++ = pal[*s++];
  }
}