summaryrefslogtreecommitdiff
path: root/vere/pkg/ur/serial.c
diff options
context:
space:
mode:
Diffstat (limited to 'vere/pkg/ur/serial.c')
-rw-r--r--vere/pkg/ur/serial.c588
1 files changed, 588 insertions, 0 deletions
diff --git a/vere/pkg/ur/serial.c b/vere/pkg/ur/serial.c
new file mode 100644
index 0000000..72fb448
--- /dev/null
+++ b/vere/pkg/ur/serial.c
@@ -0,0 +1,588 @@
+/// @file
+
+#include "serial.h"
+
+#include <assert.h>
+#include <stdlib.h>
+
+static void*
+_oom(const char* cap, void* v)
+{
+ if ( !v ) {
+ fprintf(stderr,
+ "ur: hashcons: %s: allocation failed, out of memory\r\n", cap);
+ abort();
+ }
+
+ return v;
+}
+
+static inline void
+_bsw_atom(ur_root_t *r, ur_nref ref, ur_bsw_t *bsw, uint64_t len)
+{
+ switch ( ur_nref_tag(ref) ) {
+ default: assert(0);
+
+ case ur_direct: return ur_bsw_atom64(bsw, len, ref);
+
+ case ur_iatom: {
+ uint8_t *byt = r->atoms.bytes[ur_nref_idx(ref)];
+ return ur_bsw_atom_bytes(bsw, len, byt);
+ }
+ }
+}
+
+/*
+** define opaque struct ur_jam_s (ie, ur_jam_t)
+*/
+struct ur_jam_s {
+ ur_root_t *r;
+ ur_walk_fore_t *w;
+ ur_dict64_t dict;
+ ur_bsw_t bsw;
+};
+
+static void
+_jam_atom(ur_root_t *r, ur_nref ref, void *ptr)
+{
+ ur_jam_t *j = ptr;
+ ur_dict64_t *dict = &j->dict;
+ ur_bsw_t *bsw = &j->bsw;
+ uint64_t bak, len = ur_met(r, 0, ref);
+
+ if ( !ur_dict64_get(r, dict, ref, &bak) ) {
+ ur_dict64_put(r, dict, ref, bsw->bits);
+
+ _bsw_atom(r, ref, bsw, len);
+ }
+ else {
+ uint64_t len_bak = ur_met0_64(bak);
+
+ if ( len <= len_bak ) {
+ _bsw_atom(r, ref, bsw, len);
+ }
+ else {
+ ur_bsw_back64(bsw, len_bak, bak);
+ }
+ }
+}
+
+static ur_bool_t
+_jam_cell(ur_root_t *r, ur_nref ref, void *ptr)
+{
+ ur_jam_t *j = ptr;
+ ur_dict64_t *dict = &j->dict;
+ ur_bsw_t *bsw = &j->bsw;
+ uint64_t bak;
+
+ if ( !ur_dict64_get(r, dict, ref, &bak) ) {
+ ur_dict64_put(r, dict, ref, bsw->bits);
+
+ ur_bsw_cell(bsw);
+ return 1;
+ }
+ else {
+ ur_bsw_back64(bsw, ur_met0_64(bak), bak);
+ return 0;
+ }
+}
+
+static uint64_t
+_jam(ur_jam_t *j,
+ ur_nref ref,
+ uint64_t *len,
+ uint8_t **byt)
+{
+ ur_bsw_init(&j->bsw, ur_fib11, ur_fib12);
+ ur_walk_fore_with(j->w, ref, j, _jam_atom, _jam_cell);
+ return ur_bsw_done(&j->bsw, len, byt);
+}
+
+ur_jam_t*
+ur_jam_init_with(ur_root_t *r,
+ uint64_t d_prev,
+ uint64_t d_size,
+ uint32_t s_prev,
+ uint32_t s_size)
+{
+ ur_jam_t *j = _oom("jam_init", calloc(sizeof(*j), 1));
+ j->w = ur_walk_fore_init_with(r, s_prev, s_size);
+ j->r = r;
+
+ ur_dict64_grow(r, &j->dict, d_prev, d_size);
+
+ return j;
+}
+
+ur_jam_t*
+ur_jam_init(ur_root_t *r)
+{
+ return ur_jam_init_with(r, ur_fib11, ur_fib12, // dict sizes
+ ur_fib10, ur_fib11); // stack sizes
+}
+
+uint64_t
+ur_jam_with(ur_jam_t *j,
+ ur_nref ref,
+ uint64_t *len,
+ uint8_t **byt)
+{
+ uint64_t bits = _jam(j, ref, len, byt);
+ ur_dict64_wipe(&j->dict);
+ return bits;
+}
+
+void
+ur_jam_done(ur_jam_t *j)
+{
+ ur_dict_free((ur_dict_t*)&j->dict);
+ ur_walk_fore_done(j->w);
+ free(j);
+}
+
+uint64_t
+ur_jam(ur_root_t *r,
+ ur_nref ref,
+ uint64_t *len,
+ uint8_t **byt)
+{
+ ur_jam_t *j = ur_jam_init(r);
+ uint64_t bits = _jam(j, ref, len, byt);
+ ur_jam_done(j);
+ return bits;
+}
+
+/*
+** stack frame for recording head vs tail iteration
+**
+** $? [CUE_HEAD bits=@]
+** [hed=* bits=@]
+*/
+
+#define CUE_HEAD 0xffffffffffffffffULL
+
+typedef struct _cue_frame_s {
+ uint64_t ref;
+ uint64_t bits;
+} _cue_frame_t;
+
+typedef struct _cue_stack_s {
+ uint32_t prev;
+ uint32_t size;
+ uint32_t fill;
+ _cue_frame_t* f;
+} _cue_stack_t;
+
+static inline ur_cue_res_e
+_cue_next(ur_root_t *r,
+ _cue_stack_t *s,
+ ur_bsr_t *bsr,
+ ur_dict64_t *dict,
+ ur_nref *out)
+{
+ while ( 1 ) {
+ uint64_t len, bits = bsr->bits;
+ ur_cue_tag_e tag;
+ ur_cue_res_e res;
+
+ if ( ur_cue_good != (res = ur_bsr_tag(bsr, &tag)) ) {
+ return res;
+ }
+
+ switch ( tag ) {
+ default: assert(0);
+
+ case ur_jam_cell: {
+ // reallocate the stack if full
+ //
+ if ( s->fill == s->size ) {
+ uint32_t next = s->prev + s->size;
+ s->f = _oom("cue_next stack", realloc(s->f, next * sizeof(*s->f)));
+ s->prev = s->size;
+ s->size = next;
+ }
+
+ // save a head-frame and read the head from the stream
+ //
+ {
+ _cue_frame_t* f = &(s->f[s->fill++]);
+ f->ref = CUE_HEAD;
+ f->bits = bits;
+ }
+ continue;
+ }
+
+ case ur_jam_back: {
+ if ( ur_cue_good != (res = ur_bsr_rub_len(bsr, &len)) ) {
+ return res;
+ }
+ else if ( 62 < len ) {
+ return ur_cue_meme;
+ }
+ else {
+ uint64_t val, bak = ur_bsr64_any(bsr, len);
+
+ if ( !ur_dict64_get(r, dict, bak, &val) ) {
+ return ur_cue_back;
+ }
+
+ *out = (ur_nref)val;
+ return ur_cue_good;
+ }
+ }
+
+ case ur_jam_atom: {
+ if ( ur_cue_good != (res = ur_bsr_rub_len(bsr, &len)) ) {
+ return res;
+ }
+ else if ( 62 >= len ) {
+ *out = (ur_nref)ur_bsr64_any(bsr, len);
+ }
+ else {
+ uint64_t len_byt = (len >> 3) + !!ur_mask_3(len);
+ uint8_t *byt = _oom("cue_next bytes", calloc(len_byt, 1));
+
+ ur_bsr_bytes_any(bsr, len, byt);
+
+ // strip trailing zeroes
+ //
+ while ( len_byt && !byt[len_byt - 1] ) {
+ len_byt--;
+ }
+
+ *out = ur_coin_bytes_unsafe(r, len_byt, byt);
+ }
+
+ ur_dict64_put(r, dict, bits, (uint64_t)*out);
+ return ur_cue_good;
+ }
+ }
+ }
+}
+
+/*
+** define opaque struct ur_cue_s (ie, ur_cue_t)
+*/
+struct ur_cue_s {
+ ur_root_t *r;
+ _cue_stack_t s;
+ ur_dict64_t dict;
+};
+
+static ur_cue_res_e
+_cue(ur_cue_t *c,
+ uint64_t len,
+ const uint8_t *byt,
+ ur_nref *out)
+{
+ ur_bsr_t bsr = {0};
+ ur_root_t *r = c->r;
+ _cue_stack_t *s = &c->s;
+ ur_dict64_t *dict = &c->dict;
+ ur_cue_res_e res;
+ ur_nref ref;
+
+ // init bitstream-reader
+ //
+ if ( ur_cue_good != (res = ur_bsr_init(&bsr, len, byt)) ) {
+ return res;
+ }
+ // bit-cursor (and backreferences) must fit in 62-bit direct atoms
+ //
+ else if ( 0x7ffffffffffffffULL < len ) {
+ return ur_cue_meme;
+ }
+
+ // advance into stream
+ //
+ res = _cue_next(r, s, &bsr, dict, &ref);
+
+ // process result
+ //
+ while ( s->fill && (ur_cue_good == res) ) {
+ // peek at the top of the stack
+ //
+ _cue_frame_t *f = &(s->f[s->fill - 1]);
+
+ // f is a head-frame; stash result and read the tail from the stream
+ //
+ if ( CUE_HEAD == f->ref ) {
+ f->ref = ref;
+ res = _cue_next(r, s, &bsr, dict, &ref);
+ }
+ // f is a tail-frame; pop the stack and continue
+ //
+ else {
+ ref = ur_cons(r, f->ref, ref);
+ ur_dict64_put(r, dict, f->bits, (uint64_t)ref);
+ s->fill--;
+ }
+ }
+
+ if ( ur_cue_good == res ) {
+ *out = ref;
+ }
+ return res;
+}
+
+ur_cue_t*
+ur_cue_init_with(ur_root_t *r,
+ uint64_t d_prev,
+ uint64_t d_size,
+ uint32_t s_prev,
+ uint32_t s_size)
+{
+ ur_cue_t* c = _oom("cue_init", calloc(sizeof(*c), 1));
+ c->r = r;
+
+ ur_dict64_grow(r, &c->dict, d_prev, d_size);
+
+ c->s.prev = s_prev;
+ c->s.size = s_size;
+ c->s.f = _oom("cue_test_init", malloc(s_size * sizeof(*c->s.f)));
+
+ return c;
+}
+
+ur_cue_t*
+ur_cue_init(ur_root_t *r)
+{
+ return ur_cue_init_with(r, ur_fib11, ur_fib12, // dict sizes
+ ur_fib10, ur_fib11); // stack sizes
+}
+
+ur_cue_res_e
+ur_cue_with(ur_cue_t *c,
+ uint64_t len,
+ const uint8_t *byt,
+ ur_nref *out)
+{
+ ur_cue_res_e res = _cue(c, len, byt, out);
+
+ // XX check size, shrink if above threshold
+ //
+ ur_dict64_wipe(&c->dict);
+ c->s.fill = 0;
+
+ return res;
+}
+
+void
+ur_cue_done(ur_cue_t *c)
+{
+
+ ur_dict_free((ur_dict_t*)&c->dict);
+ free(c->s.f);
+ free(c);
+}
+
+ur_cue_res_e
+ur_cue(ur_root_t *r,
+ uint64_t len,
+ const uint8_t *byt,
+ ur_nref *out)
+{
+ ur_cue_t *c = ur_cue_init(r);
+ ur_cue_res_e res = _cue(c, len, byt, out);
+
+ ur_cue_done(c);
+ return res;
+}
+
+/*
+** stack frame for recording head vs tail iteration
+**
+** [hed=? bits=@]
+**
+*/
+
+typedef struct _cue_test_frame_s {
+ ur_bool_t tal;
+ uint64_t bits;
+} _cue_test_frame_t;
+
+typedef struct _cue_test_stack_s {
+ uint32_t prev;
+ uint32_t size;
+ uint32_t fill;
+ _cue_test_frame_t* f;
+} _cue_test_stack_t;
+
+static inline ur_cue_res_e
+_cue_test_next(_cue_test_stack_t *s,
+ ur_bsr_t *bsr,
+ ur_dict_t *dict)
+{
+ while ( 1 ) {
+ uint64_t len, bits = bsr->bits;
+ ur_cue_tag_e tag;
+ ur_cue_res_e res;
+
+ if ( ur_cue_good != (res = ur_bsr_tag(bsr, &tag)) ) {
+ return res;
+ }
+
+ switch ( tag ) {
+ default: assert(0);
+
+ case ur_jam_cell: {
+ // reallocate the stack if full
+ //
+ if ( s->fill == s->size ) {
+ uint32_t next = s->prev + s->size;
+ s->f = _oom("cue_test", realloc(s->f, next * sizeof(*s->f)));
+ s->prev = s->size;
+ s->size = next;
+ }
+
+ // save a head-frame and read the head from the stream
+ //
+ {
+ _cue_test_frame_t* f = &(s->f[s->fill++]);
+ f->tal = 0;
+ f->bits = bits;
+ }
+ continue;
+ }
+
+ case ur_jam_back: {
+ if ( ur_cue_good != (res = ur_bsr_rub_len(bsr, &len)) ) {
+ return res;
+ }
+ else if ( 62 < len ) {
+ return ur_cue_meme;
+ }
+ else {
+ uint64_t bak = ur_bsr64_any(bsr, len);
+ return ur_dict_get((ur_root_t*)0, dict, bak)
+ ? ur_cue_good
+ : ur_cue_back;
+ }
+ }
+
+ case ur_jam_atom: {
+ if ( ur_cue_good != (res = ur_bsr_rub_len(bsr, &len)) ) {
+ return res;
+ }
+
+ ur_bsr_skip_any(bsr, len);
+ ur_dict_put((ur_root_t*)0, dict, bits);
+ return ur_cue_good;
+ }
+ }
+ }
+}
+
+/*
+** define opaque struct ur_cue_test_s (ie, ur_cue_test_t)
+*/
+struct ur_cue_test_s {
+ _cue_test_stack_t s;
+ ur_dict_t dict;
+};
+
+static ur_cue_res_e
+_cue_test(ur_cue_test_t *t,
+ uint64_t len,
+ const uint8_t *byt)
+{
+ ur_bsr_t bsr = {0};
+ _cue_test_stack_t *s = &t->s;
+ ur_dict_t *dict = &t->dict;
+ ur_cue_res_e res;
+
+ // init bitstream-reader
+ //
+ if ( ur_cue_good != (res = ur_bsr_init(&bsr, len, byt)) ) {
+ return res;
+ }
+ // bit-cursor (and backreferences) must fit in 62-bit direct atoms
+ //
+ else if ( 0x7ffffffffffffffULL < len ) {
+ return ur_cue_meme;
+ }
+
+ // advance into stream
+ //
+ res = _cue_test_next(s, &bsr, dict);
+
+ // process result
+ //
+ while ( s->fill && (ur_cue_good == res) ) {
+ // peek at the top of the stack
+ //
+ _cue_test_frame_t *f = &(s->f[s->fill - 1]);
+
+ // f is a head-frame; stash result and read the tail from the stream
+ //
+ if ( !f->tal ) {
+ f->tal = 1;
+ res = _cue_test_next(s, &bsr, dict);
+ }
+ // f is a tail-frame; pop the stack and continue
+ //
+ else {
+ ur_dict_put((ur_root_t*)0, dict, f->bits);
+ s->fill--;
+ }
+ }
+
+ return res;
+}
+
+ur_cue_test_t*
+ur_cue_test_init_with(uint64_t d_prev,
+ uint64_t d_size,
+ uint32_t s_prev,
+ uint32_t s_size)
+{
+ ur_cue_test_t* t = _oom("cue_test_init", calloc(sizeof(*t), 1));
+
+ ur_dict_grow((ur_root_t*)0, &t->dict, d_prev, d_size);
+
+ t->s.prev = s_prev;
+ t->s.size = s_size;
+ t->s.f = _oom("cue_test_init", malloc(s_size * sizeof(*t->s.f)));
+
+ return t;
+}
+
+ur_cue_test_t*
+ur_cue_test_init(void)
+{
+ return ur_cue_test_init_with(ur_fib11, ur_fib12, // dict sizes
+ ur_fib10, ur_fib11); // stack sizes
+}
+
+ur_bool_t
+ur_cue_test_with(ur_cue_test_t *t,
+ uint64_t len,
+ const uint8_t *byt)
+{
+ ur_bool_t ret = ur_cue_good == _cue_test(t, len, byt);
+
+ // XX check size, shrink if above threshold
+ //
+ ur_dict_wipe(&t->dict);
+ t->s.fill = 0;
+
+ return ret;
+}
+
+void
+ur_cue_test_done(ur_cue_test_t *t)
+{
+ ur_dict_free(&t->dict);
+ free(t->s.f);
+ free(t);
+}
+
+ur_bool_t
+ur_cue_test(uint64_t len, const uint8_t *byt)
+{
+ ur_cue_test_t *t = ur_cue_test_init();
+ ur_bool_t ret = ur_cue_good == _cue_test(t, len, byt);
+
+ ur_cue_test_done(t);
+ return ret;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-16 08:26:39 +0000