Skip to content Search Apps Documentation Source Content File Folder Download Copy Actions State String Boolean Number Struct Map Slice Pointer Function Closure Reference Nil Package Type Interface Unknown

Community realm. Read the code first. Community realm, deployed by its author. Read the code before you interact or send coins.

v0 source pure

Package huffman compresses a string with canonical Huffman codes: the classic frequency-based prefix code, in the one...

Readme View source

gno.land/p/moul/x/daily/huffman/v0

Canonical Huffman codes, with a decoder that validates: Table, Encode, Encoded.Decode, Encoded.BitString, Encoded.Saved.

1import "gno.land/p/moul/x/daily/huffman/v0"
2
3codes, _ := huffman.Table("abracadabra")  // a=0, b=100, c=101, d=110, r=111
4enc, _ := huffman.Encode("abracadabra")   // 23 bits against 88 raw
5enc.BitString()                           // "01001110101011001001110"
6enc.Decode()                              // "abracadabra", or ErrCorrupt

A Huffman tree is not unique. Two equally optimal trees give the same total bit count and different codes, and which one you get depends on how ties are broken while merging, which means a naive implementation can hand two callers different tables for the same input. Canonical coding throws the tree away and keeps only the code lengths, then re-derives the bits by sorting on (length, symbol). That is what makes the output deterministic enough for a Render and small enough to store: the header a decoder needs is one integer per symbol, not a tree.

The decoder validates, deliberately. Encoded is a plain struct with exported fields, so a caller can build one by hand or read one back out of storage, and a decoder that trusts what it is handed returns a string nobody ever encoded. Decode rebuilds the canonical table from the lengths it was given and refuses a payload whose own Bits disagree, checks the Kraft equality so the code set is a complete prefix code, requires Data to be exactly the bytes NBits needs with zero padding in the last one, refuses a zero-bit or zero-size payload because Encode never produces one, refuses a stream that ends mid-code, and refuses a result whose length is not Size. Spare bytes and dirty padding are not cosmetic: both are a way to carry a second payload that decodes to the same string.

Three behaviours worth knowing before you use it:

  • A one-symbol alphabet gets a one-bit code. Its leaf has no sibling, so the tree walk would give it a zero-bit code and "aaaaa" would encode to an empty stream that decodes to nothing. It is the only incomplete code this package emits (Kraft sum 1/2), and Decode allows exactly that one case.
  • Symbols are bytes, not runes. The alphabet is 0 to 255 and a multi-byte UTF-8 character is several symbols. Round-tripping is byte-exact either way; only a per-symbol display has to care.
  • Ties prefer the leaf queue. The merge uses the two-queue variant, leaves pre-sorted by (frequency, symbol) and merged nodes appended in creation order, so no priority queue, no map iteration and nothing that could reorder between two runs.

MaxLen is 4096 bytes. That bound is also what keeps a code under 18 bits: the worst case for Huffman is a Fibonacci frequency distribution, where reaching a 32-bit code needs megabytes of input. ErrTooDeep exists for the overflow anyway, returned rather than panicked, because a realm's Render can never be fixed once its path is published.

Live demo: r/moul/x/daily/huffmandemo.

Built for gno 0.9.

Part of moul/gno-contracts — moul's versioned gno.land contracts. See the repository for the full catalog, build/test tooling, and usage.

🧪 Highly experimental — potentially vibe-coded. Not audited; may break, change, or be removed at any time. Do not use with anything of value. Full disclaimer: DISCLAIMER.

Overview

Package huffman compresses a string with canonical Huffman codes: the classic frequency-based prefix code, in the one form that is safe to put on a chain.

Two properties matter here and neither is about compression.

The codes are CANONICAL. A plain Huffman tree is not unique: two equally optimal trees give the same total bit count and different codes, and which one you get depends on how ties are broken while merging. Canonical codes throw the tree away and keep only the code LENGTHS, then re-derive the bits by sorting on (length, symbol). The same input therefore always produces the same table, which is what a deterministic Render and a reproducible payload both need, and the table a decoder has to carry shrinks to one length per symbol.

Decoding VALIDATES. Encoded is a plain struct with exported fields, so a caller can build one by hand or read one out of storage, and a decoder that trusts what it is handed will happily return a string nobody ever encoded. Encoded.Decode rebuilds the canonical table from the lengths it was given, refuses a payload whose own Bits disagree with it, and checks the Kraft equality, the bit budget and the decoded size before returning.

A live demo of this package is at r/moul/x/daily/huffmandemo(/r/moul/x/daily/huffmandemo/v0).

Constants 1

const MaxLen 

1const MaxLen = 4096
source

MaxLen bounds input so gas stays predictable.

Variables 1

var ErrEmpty, ErrTooLong, ErrTooDeep, ErrCorrupt 

 1var (
 2	// ErrEmpty is returned for an input with no bytes in it: there is no such
 3	// thing as a code for an empty alphabet.
 4	ErrEmpty = errors.New("huffman: empty input")
 5	// ErrTooLong is returned when input exceeds MaxLen.
 6	ErrTooLong = errors.New("huffman: input too long")
 7	// ErrTooDeep is returned when the optimal code would be longer than 32
 8	// bits. Unreachable at MaxLen, and returned rather than panicked because a
 9	// realm's Render can never be fixed once the path is published.
10	ErrTooDeep = errors.New("huffman: code longer than 32 bits")
11	// ErrCorrupt is returned by Decode when the payload is not one this
12	// package could have produced.
13	ErrCorrupt = errors.New("huffman: corrupt payload")
14)
source

Functions 2

func Table 

1func Table(s string) ([]Code, error)
source

Table returns the canonical code table for s, sorted by (Len, Symbol), without encoding anything.

func Encode 

1func Encode(s string) (*Encoded, error)
source

Encode builds the canonical table for s and packs s with it.

Types 2

type Code

struct 
1type Code struct {
2	Symbol byte
3	Len    int    // length in bits, 1 to 32
4	Bits   uint32 // the code, right aligned, most significant bit first
5}
source

Code is one symbol's canonical prefix code.

Methods on Code

func String

method on Code 
1func (c Code) String() string
source

String renders the code as its bit pattern, "110" and not "6".

type Encoded

struct 
1type Encoded struct {
2	Codes []Code // sorted by (Len, Symbol)
3	Data  []byte // the bit stream, most significant bit of each byte first
4	NBits int    // significant bits in Data; the rest of the last byte is padding
5	Size  int    // length of the original input, in bytes
6}
source

Encoded is a compressed payload: the canonical table, which is the whole header a decoder needs, and the packed bit stream.

Methods on Encoded

func BitString

method on Encoded 
1func (e *Encoded) BitString() string
source

BitString renders the stream as '0' and '1', padding excluded. It is meant for demos and error messages: the result is NBits characters long.

func Decode

method on Encoded 
1func (e *Encoded) Decode() (string, error)
source

Decode validates the payload and returns the original string.

Everything it checks is something a hand-built or storage-read Encoded can get wrong: an empty or over-long table, a zero length, a table out of canonical order, a repeated symbol, Bits that disagree with the lengths, a code set that is not a complete prefix code, a zero-bit or zero-size payload, a Data slice that is not exactly the bytes NBits needs, nonzero padding in the last byte, a stream ending mid-code, and a decoded length that is not Size.

func Saved

method on Encoded 
1func (e *Encoded) Saved() int
source

Saved reports how many bits the encoding removed, which is negative when the alphabet is flat enough that the codes cost more than the bytes did.

Dependencies

Imports 2

/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/huffman/v0

Imported by indexer

Find the packages that import it

Source Files 4