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.
C calculatorcalculator-gamescasiochesscrossy-roaddrive-madfx-cg50gamesgeometry-dashgraphing-calculatorndlessnumworksnumworks-appsnumworks-calculatornumworks-gamenumworks-gamestetristi-84-plus-ceti-nspire
/* The player's changes to the world, saved as they happen.
*
* The world is cut in regions of 4 x 4 chunks (64 x 64 columns). Each region
* the player changed has a record in the calculator's storage, read where it
* lies: sorted 32-bit entries, chunk (4 bits), x and z in it (8), y (7), then
* the block (8, the top byte). New changes go to a small journal in RAM, kept
* in the same order; when it fills up (and when the game saves), its entries
* are merged into the records.
*
* NumBlocks.nwa's blocks are 9 bits: one past 255 is kept with its ninth bit in bit 23 of the entry
* (outside every key NumPlay's NumBlocks looks up, which so never sees those blocks), its low byte
* on top; records stay sorted by the 24 bits. If a spot has both kinds of entry (NumPlay's
* NumBlocks changed it after), the other kind wins. Each dimension has its own records: the
* Nether's "nb1rn-3_12.nbe", the End's "nb1re...". */
#include "edits.h"
#include "nb.h"
#pragma GCC optimize("Os") /* (not where the time goes: small) */
typedef struct {
int16_t rx, rz;
uint32_t e; /* the entry, as in the records */
} Journal;
#if NB_DIMS
#define J_MAX 128 /* (NumBlocks.nwa: room for the 9th bits of blocks, nb.h) */
#else
#define J_MAX 256
#endif
static Journal jn[J_MAX];
static int nj;
static char prefix[8] = "nb1";
static bool full; /* a record could not grow: storage is full */
static uint32_t *scratch;
static uint32_t scratch_n;
#if NB_DIMS
static char dim_tag; /* 0 the Overworld, 'n' the Nether, 'e' the End */
void edits_dim(int d) { dim_tag = d == DIM_NETHER ? 'n' : d == DIM_END ? 'e' : 0; }
#define HI (1u << 23)
#endif
void edits_setup(const char *world, uint32_t *buf, uint32_t n) {
int i = 0;
for (; world[i] && i < 7; i++) prefix[i] = world[i];
prefix[i] = 0;
scratch = buf;
scratch_n = n;
}
bool edits_full(void) { return full; }
static inline int floordiv(int a, int d) { return a >= 0 ? a / d : -((-a + d - 1) / d); }
/* "nb1r-3_12.nbe" */
static void region_name(char *out, int rx, int rz) {
char *p = out;
for (const char *s = prefix; *s;) *p++ = *s++;
*p++ = 'r';
#if NB_DIMS
if (dim_tag) *p++ = dim_tag;
#endif
int v[2] = {rx, rz};
for (int k = 0; k < 2; k++) {
if (k) *p++ = '_';
int n = v[k];
if (n < 0) *p++ = '-', n = -n;
char t[8];
int m = 0;
do t[m++] = (char)('0' + n % 10), n /= 10;
while (n);
while (m) *p++ = t[--m];
}
const char *ext = ".nbe";
while (*ext) *p++ = *ext++;
*p = 0;
}
/* a region's record (the last one looked up is remembered until records change) */
static bool cache_ok;
static int cache_rx, cache_rz, cache_n;
static const uint8_t *cache_r;
static const uint8_t *region(int rx, int rz, int *n) {
if (!cache_ok || rx != cache_rx || rz != cache_rz) {
char name[32];
region_name(name, rx, rz);
uint32_t len = 0;
const uint8_t *d = plat_load(name, &len);
cache_r = d;
cache_n = d ? (int)(len / 4) : 0;
cache_rx = rx, cache_rz = rz, cache_ok = true;
}
*n = cache_n;
return cache_r;
}
void edits_clear(void) { nj = 0, full = false, cache_ok = false; }
void edits_forget(void) { cache_ok = false; }
/* records are not aligned in storage: entries are read a byte at a time */
static inline uint32_t rd32(const uint8_t *p) {
uint32_t v;
memcpy(&v, p, 4);
return v;
}
#define R(i) rd32(r + 4 * (i))
/* entries are sorted by their low 24 bits */
#define KEY(e) ((e) & 0xFFFFFF)
static inline uint32_t entry_key(int x, int y, int z) {
int cx = floordiv(x, 16), cz = floordiv(z, 16);
int chunk = (cx & 3) | (cz & 3) << 2;
int xz = (x & 15) | (z & 15) << 4;
return (uint32_t)(chunk << 15 | xz << 7 | (y & 127));
}
static int jcmp(int rx, int rz, uint32_t key, const Journal *j) {
if (rz != j->rz) return rz < j->rz ? -1 : 1;
if (rx != j->rx) return rx < j->rx ? -1 : 1;
uint32_t k = KEY(j->e);
return key < k ? -1 : key > k;
}
static int jlower(int rx, int rz, uint32_t key) {
int lo = 0, hi = nj;
while (lo < hi) {
int m = (lo + hi) / 2;
if (jcmp(rx, rz, key, &jn[m]) > 0) lo = m + 1;
else hi = m;
}
return lo;
}
static int rlower(const uint8_t *r, int n, uint32_t key) {
int lo = 0, hi = n;
while (lo < hi) {
int m = (lo + hi) / 2;
if (KEY(R(m)) < key) lo = m + 1;
else hi = m;
}
return lo;
}
#if NB_DIMS
/* the journal has an entry of key in region (rx, rz), among its entries [i, j) */
static bool journal_has(int rx, int rz, uint32_t key, int i, int j) {
int k = jlower(rx, rz, key);
return k >= i && k < j && jcmp(rx, rz, key, &jn[k]) == 0;
}
#endif
static inline void wr32(uint8_t *p, uint32_t v) { memcpy(p, &v, 4); }
/* the journal's entries go into their regions' records: each record grows in place in storage and the two
* are merged from the end, so a record can be as big as storage lets it be */
bool edits_flush(void) {
bool ok = true;
int i = 0;
while (i < nj) {
int rx = jn[i].rx, rz = jn[i].rz, j = i;
while (j < nj && jn[j].rx == rx && jn[j].rz == rz) j++;
int n;
region(rx, rz, &n);
char name[32];
region_name(name, rx, rz);
cache_ok = false;
int top = n + (j - i);
uint8_t *r = plat_save_grow(name, (uint32_t)top * 4);
if (!r) {
/* no room: these changes stay in the journal */
ok = false;
full = true;
i = j;
continue;
}
int a = n - 1, b = j - 1, o = top;
while (a >= 0 || b >= i) {
if (a >= 0 && (b < i || KEY(R(a)) > KEY(jn[b].e))) {
#if NB_DIMS
if (journal_has(rx, rz, KEY(R(a)) ^ HI, i, j)) {
a--; /* (the journal has its spot, as the other kind) */
continue;
}
#endif
wr32(r + 4 * --o, R(a)), a--; /* (never past what is still to read: o > a) */
} else {
if (a >= 0 && KEY(R(a)) == KEY(jn[b].e)) a--;
wr32(r + 4 * --o, jn[b--].e);
}
}
if (o) memmove(r, r + 4 * o, (size_t)(top - o) * 4);
plat_save_done(name, (uint32_t)(top - o) * 4);
memmove(&jn[i], &jn[j], (size_t)(nj - j) * sizeof jn[0]);
nj -= j - i;
}
return ok;
}
bool edits_put(int x, int y, int z, int b) {
int rx = floordiv(x, 64), rz = floordiv(z, 64);
uint32_t key = entry_key(x, y, z);
#if NB_DIMS
{
/* the spot's entry of the other kind goes: this one replaces it */
int o = jlower(rx, rz, key ^ HI);
if (o < nj && jcmp(rx, rz, key ^ HI, &jn[o]) == 0) {
memmove(&jn[o], &jn[o + 1], (size_t)(nj - o - 1) * sizeof jn[0]);
nj--;
}
key |= (uint32_t)(b >> 8 & 1) << 23;
}
#endif
int i = jlower(rx, rz, key);
if (i < nj && jcmp(rx, rz, key, &jn[i]) == 0) {
jn[i].e = key | (uint32_t)b << 24;
return true;
}
if (nj >= J_MAX) {
edits_flush();
if (nj >= J_MAX) return false;
i = jlower(rx, rz, key);
}
memmove(&jn[i + 1], &jn[i], (size_t)(nj - i) * sizeof jn[0]);
jn[i] = (Journal){(int16_t)rx, (int16_t)rz, key | (uint32_t)b << 24};
nj++;
return true;
}
/* onto a chunk from gen_slab: the record's entries, then the journal's */
void edits_apply(int cx, int cz, int y0, int h, uint8_t *slab) {
int rx = floordiv(cx, 4), rz = floordiv(cz, 4), chunk = (cx & 3) | (cz & 3) << 2;
uint32_t k0 = (uint32_t)chunk << 15, k1 = k0 + (1 << 15);
int n;
const uint8_t *r = region(rx, rz, &n);
for (int i = rlower(r, n, k0); i < n && KEY(R(i)) < k1; i++) {
uint32_t e = R(i);
int y = (int)(e & 127) - y0, xz = (int)(e >> 7) & 255;
if (y >= 0 && y < h) slab[(y * 16 + (xz >> 4)) * 16 + (xz & 15)] = (uint8_t)(e >> 24);
}
for (int i = jlower(rx, rz, k0); i < nj && jn[i].rx == rx && jn[i].rz == rz && KEY(jn[i].e) < k1; i++) {
int y = (int)(jn[i].e & 127) - y0, xz = (int)(jn[i].e >> 7) & 255;
if (y >= 0 && y < h) slab[(y * 16 + (xz >> 4)) * 16 + (xz & 15)] = (uint8_t)(jn[i].e >> 24);
}
}
#if NB_DIMS
/* edits_apply, the ninth bits in hb (a bit a cell of the slab): first the record's entries of each kind
* (the low ones last: they win), then the journal's */
static void apply_range(const uint8_t *r, int n, uint32_t k0, uint32_t k1, int y0, int h, uint8_t *slab, uint8_t *hb,
bool hi) {
for (int i = rlower(r, n, k0); i < n && KEY(R(i)) < k1; i++) {
uint32_t e = R(i);
int y = (int)(e & 127) - y0, xz = (int)(e >> 7) & 255;
if (y < 0 || y >= h) continue;
int c = (y * 16 + (xz >> 4)) * 16 + (xz & 15);
slab[c] = (uint8_t)(e >> 24);
hb[c >> 3] = (uint8_t)((hb[c >> 3] & ~(1 << (c & 7))) | hi << (c & 7));
}
}
void edits_apply9(int cx, int cz, int y0, int h, uint8_t *slab, uint8_t *hb) {
int rx = floordiv(cx, 4), rz = floordiv(cz, 4), chunk = (cx & 3) | (cz & 3) << 2;
uint32_t k0 = (uint32_t)chunk << 15, k1 = k0 + (1 << 15);
int n;
const uint8_t *r = region(rx, rz, &n);
apply_range(r, n, k0 | HI, k1 | HI, y0, h, slab, hb, true);
apply_range(r, n, k0, k1, y0, h, slab, hb, false);
for (int pass = 0; pass < 2; pass++) {
uint32_t a = pass ? k0 | HI : k0, b = pass ? k1 | HI : k1;
for (int i = jlower(rx, rz, a); i < nj && jn[i].rx == rx && jn[i].rz == rz && KEY(jn[i].e) < b; i++) {
int y = (int)(jn[i].e & 127) - y0, xz = (int)(jn[i].e >> 7) & 255;
if (y < 0 || y >= h) continue;
int c = (y * 16 + (xz >> 4)) * 16 + (xz & 15);
slab[c] = (uint8_t)(jn[i].e >> 24);
hb[c >> 3] = (uint8_t)((hb[c >> 3] & ~(1 << (c & 7))) | pass << (c & 7));
}
}
}
#define BLOCK_OF(e) ((int)((e) >> 24) | (int)((e) >> 23 & 1) << 8)
#else
#define BLOCK_OF(e) ((e) >> 24)
#endif
/* the column's sky top (1 + the highest opaque y) with the changes */
int edits_top(int x, int z, int top) {
int rx = floordiv(x, 64), rz = floordiv(z, 64);
uint32_t k0 = entry_key(x, 0, z), k1 = k0 + 128;
int n;
const uint8_t *r = region(rx, rz, &n);
#if NB_DIMS
for (int pass = 0; pass < 2; pass++, k0 |= HI, k1 |= HI) {
#endif
for (int i = rlower(r, n, k0); i < n && KEY(R(i)) < k1; i++) {
uint32_t e = R(i);
if ((blk_flags[BLOCK_OF(e)] & BF_OPAQUE) && (int)(e & 127) + 1 > top) top = (int)(e & 127) + 1;
}
for (int i = jlower(rx, rz, k0); i < nj && jn[i].rx == rx && jn[i].rz == rz && KEY(jn[i].e) < k1; i++)
if ((blk_flags[BLOCK_OF(jn[i].e)] & BF_OPAQUE) && (int)(jn[i].e & 127) + 1 > top) top = (int)(jn[i].e & 127) + 1;
#if NB_DIMS
}
#endif
return top;
}
#if NB_DIMS
/* was the block there changed (else it is as the world was made)? */
bool edits_changed(int x, int y, int z) {
int rx = floordiv(x, 64), rz = floordiv(z, 64), n;
uint32_t key = entry_key(x, y, z);
const uint8_t *r = region(rx, rz, &n);
for (int pass = 0; pass < 2; pass++, key |= HI) {
int i = jlower(rx, rz, key);
if (i < nj && jcmp(rx, rz, key, &jn[i]) == 0) return true;
int k = rlower(r, n, key);
if (k < n && KEY(R(k)) == key) return true;
}
return false;
}
/* Teleporter.placeInExistingPortal: of the blocks b0 and b1 changed within r of (x, z) (portals: only made
* by changes), the nearest to (x, y, z) of those with neither below; false if none. Records only: the
* journal is flushed first */
bool edits_find(int x, int y, int z, int rad, int b0, int b1, int *out) {
int64_t best = -1;
for (int rz = floordiv(z - rad, 64); rz <= floordiv(z + rad, 64); rz++)
for (int rx = floordiv(x - rad, 64); rx <= floordiv(x + rad, 64); rx++) {
int n;
const uint8_t *rec = region(rx, rz, &n);
const uint8_t *r_ = rec;
#define RR(i) rd32(r_ + 4 * (i))
for (int i = n; i-- > 0 && (RR(i) & HI);) {
uint32_t e = RR(i);
int b = BLOCK_OF(e);
if (b != b0 && b != b1) continue;
uint32_t k = KEY(e) & ~HI;
/* (a plain entry of the spot wins over it: NumPlay's NumBlocks changed it since) */
const uint8_t *r = rec;
int j = rlower(r, n, k);
if (j < n && KEY(R(j)) == k) continue;
if ((e & 127) && i > 0 && KEY(RR(i - 1)) == KEY(e) - 1 && (BLOCK_OF(RR(i - 1)) == b0 || BLOCK_OF(RR(i - 1)) == b1))
continue; /* (one below: the lowest of a column counts) */
int chunk = (int)(e >> 15) & 15, xz = (int)(e >> 7) & 255;
int bx = (rx * 4 + (chunk & 3)) * 16 + (xz & 15), bz = (rz * 4 + (chunk >> 2)) * 16 + (xz >> 4), by = (int)(e & 127);
if (bx < x - rad || bx > x + rad || bz < z - rad || bz > z + rad) continue;
int64_t d = (int64_t)(bx - x) * (bx - x) + (int64_t)(by - y) * (by - y) + (int64_t)(bz - z) * (bz - z);
if (best < 0 || d < best) best = d, out[0] = bx, out[1] = by, out[2] = bz;
}
#undef RR
}
return best >= 0;
}
#endif
int edits_count(void) { return nj; }
/* the merge buffer, lent out between merges (n bytes at most) */
void *edits_scratch(uint32_t n) { return n <= scratch_n * 4 ? scratch : NULL; }