Download docs/research/HUFFMAN_UPDATES.md from nmarshall/urt-rs: direct link, hf CLI and curl.
- Browser
- Download file 6.99 kB
-
https://huggingface.co/nmarshall/urt-rs/resolve/main/docs/research/HUFFMAN_UPDATES.md
- Command line
-
hf download hf://nmarshall/urt-rs/docs/research/HUFFMAN_UPDATES.md
-
curl -L -o HUFFMAN_UPDATES.md https://huggingface.co/nmarshall/urt-rs/resolve/main/docs/research/HUFFMAN_UPDATES.md
Bounded adaptive Huffman insertion and increment
Reproduce with python3 scripts/analyze_huffman_updates.py; validate with python3 scripts/test_huffman_updates.py. huffman-updates.json retains two hash-verified graphs per Linux ELF64 engine: Huff_addRef and increment. Initial object bytes are supplied from the source/disassembly-matched initialization report, whose full report hash is recorded.
These compositions evaluate native instructions over virtual objects. The increment PUSH is changed to NOP and evaluation stops before POP/RET; recursive CALLs are stopped and their bodies evaluated explicitly, restoring every caller register while retaining child memory effects. No original process, native callee, memset, or actual full seed-training execution occurs. Validity checks apply only to the sampled finite trees and sequences; they do not prove ABI, all adaptive paths, original-runtime or platform conformance.
UPDATE-001 — Low-byte dispatch and NYT insertion (RE-357)
Huff_addRef first zero-extends the input's low byte, selecting lookup object +32 +8*byte. An existing entry forwards that node into increment without prior memory writes. Twelve paired isolated probes cover input words 0/1/255/256/257/0xffffffff with explicitly supplied existing entries. The supplied targets use the initial NYT address solely to characterize dispatch; these aliases are not legal symbol/tree fixtures. Unlike the previously observed signed index in Huff_offsetTransmit, addRef locally normalizes its input to a byte. Valid callers still require audit.
For a new byte, the object node count increases by two. A leaf uses the old count's slot and an internal node the following slot, with addresses object +0x830 +56*index. The leaf's symbol is the normalized byte; the internal symbol is 257. Both start at weight one. The old NYT becomes the internal node's left child and the new symbol its right child. The internal node replaces NYT at its former parent or becomes root, and parent/list/lookup pointers are repaired. The subsequent increment request starts at the new internal node's parent; when the first symbol creates a root, that request receives null.
The first insertion into the supplied empty object yields node count three: NYT at index zero with weight zero; byte leaf at index one with weight one; root internal at index two with weight one. NYT and leaf share the root as parent, and the two positive-weight nodes share a leader cell. Every new byte creates exactly one additional leaf/internal pair in sampled sequences. Visiting all 256 byte symbols once yields 513 reachable nodes, with lookup entries for every byte and NYT 256.
UPDATE-002 — Repeated symbols and recursive weights (RE-358)
Twenty-two paired sequence compositions cover empty input, first bytes 0/255, sixteen repeats of zero, alternating 0/1, ascending/reversed eight-byte orders, two sixteen-byte cycles, repeated boundary-byte mixtures and the complete ascending byte alphabet. Updates retain complete prefix states for sequences of length at most 24; longer sequences retain final states and all dispatch/trace summaries.
Existing leaves are reused. increment updates weight and may reorder tree/list nodes before recursively updating parents; the caller's post-recursion adjustments also execute in these compositions. Independent Counter oracles verify every leaf weight equals its occurrence count. A separate tree traversal verifies root weight equals sequence length, every internal weight equals its two child weights, child/parent pointers agree, the graph is acyclic and every allocated node is reachable. NYT stays at index zero with weight zero.
Null increment retains all supplied memory. Recursive compositions reach depth eight in the full byte-alphabet fixture. This is bounded recursion through current mutated parent links, not a substitute for proving every tie/swap case or ABI register preservation. Trace summaries describe synthetic compositions; no native CALL executes implicitly. Exact trained codewords require the real 1,053,340-repetition seed sequence and all relevant tie behavior.
UPDATE-003 — Rank links, block leaders and pointer-cell reuse (RE-359)
The sampled node fields are left +0, right +8, parent +16, next +24, previous +32, leader-cell pointer +40, weight +48 and symbol +52. Node layout is 56 bytes. The rank list begins at the object's +16 pointer, which retains NYT as its start. Object +24 remains zero in these first-object compositions; the asymmetric second-object initialization was not composed here.
Independent list traversal verifies every node appears exactly once, next/previous links agree and weights are nondecreasing. Positive-weight nodes of one weight share one cell, and each cell points to the last node of that weight in rank order. NYT has no leader cell. These observed invariants provide an independent check of the native swap/head-maintenance paths exercised by the sequence corpus, not exhaustive coverage of arbitrary malformed or tied trees.
Pointer cells allocate at object +0xb030 +8*index, using the counter at +4. The free-cell chain begins at object +0x828 and stores its next link in the freed cell itself. The native routines reuse those cells when creating new weight blocks. Tests partition every allocated cell into exactly one live leader cell or free-chain member, with no duplicate/cyclic free entries in the sampled states. The full alphabet requires only fifteen allocated cells for 513 nodes; thus cells are shared/reused rather than allocated per node. Exact capacity bounds and overflow/error behavior remain open.
The object-wide outside canaries are preserved for all sequences. This does not prove arbitrary writes remain inside pool capacity or validate aliased/corrupted objects.
Validation and next work
Eight independent tests verify node allocation/lookup/Counter counts, complete tree reachability/parent/subtree weights, rank ordering/reverse links, leader cells, live/free pool partition and reuse, dispatch/low-byte aliases, null/recursive stopped-call behavior and paired results. A fresh isolated root increment additionally verifies its weight change and call-free evaluated trace. No evaluator extension was needed.
RE-360: audit individual tree/list swaps and parent/leader tie gates with branch-complete fixtures, second-object initialization/update equivalence, malformed/aliased/capacity/wrap states and legal callers; reconstruct actual initialized codebooks efficiently using the exact seed schedule with native-equivalence checks; compose message encoders/decoders and real packets and validate original-runtime/all-platform contracts.
Codebook follow-up: differential recoding and modeled training checks both object halves and exports provisional seed-trained codewords (RE-361–363). Actual full native training/runtime/platform/packet validation remains open.