diff options
author | polwex <polwex@sortug.com> | 2025-10-05 21:56:51 +0700 |
---|---|---|
committer | polwex <polwex@sortug.com> | 2025-10-05 21:56:51 +0700 |
commit | fcedfddf00b3f994e4f4e40332ac7fc192c63244 (patch) | |
tree | 51d38e62c7bdfcc5f9a5e9435fe820c93cfc9a3d /vere/pkg/ur/serial.c |
claude is gud
Diffstat (limited to 'vere/pkg/ur/serial.c')
-rw-r--r-- | vere/pkg/ur/serial.c | 588 |
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; +} |