Playground
gnomod.toml
module = "gno.land/r/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/huffmandemo/v0" gno = "0.9" private = true [addpkg] creator = "g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv" height = 914308 max_deposit = "6000000ugnot"
huffmandemo.gno
// Package huffmandemo is a small gnoweb demo of the canonical Huffman codec
// provided by the [p/moul/x/daily/huffman](/p/moul/x/daily/huffman/v0)
// library: the code table for a worked example, what the packed stream looks
// like, what the skew is worth, and the two inputs that break a naive
// implementation.
//
// It contains no codec logic of its own. Stateless, so Render is
// deterministic: every figure below is computed from the fixed strings at the
// top of this file, never from chain state, which is what lets an example test
// pin the page.
package huffmandemo
import (
"strconv"
"strings"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
"gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/huffman/v0"
)
// worked is the example small enough to check by hand: 11 bytes, 5 symbols,
// frequencies 5/2/2/1/1.
const worked = "abracadabra"
// samples show what the skew is worth. The first is flat by construction, the
// last is almost all one symbol, and the ratio moves the whole way between.
var samples = []string{
"abcdefgh",
"the quick brown fox jumps over the lazy dog",
"mississippi",
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcd",
}
// Render renders the demo for gnoweb.
//
// Render("") / Render("/") -> the worked example, the ratios, the edge cases
// Render("/<text>") -> encode that text and show its table
func Render(path string) string {
if in := parseArg(path); in != "" {
return renderInput(in)
}
var b strings.Builder
b.WriteString("# Huffman coding\n\n")
b.WriteString("Frequency-based prefix codes, demoing the ")
b.WriteString("[`p/moul/x/daily/huffman`](/p/moul/x/daily/huffman/v0) library. ")
b.WriteString("Rare symbols get long codes, common ones get short codes, and no ")
b.WriteString("code is a prefix of another, so the stream needs no separators.\n\n")
enc, err := huffman.Encode(worked)
if err != nil {
return b.String() + "> encoding failed: " + err.Error() + "\n"
}
b.WriteString("## `" + worked + "`\n\n")
t := ui.NewTable("symbol", "count", "code", "bits")
for _, c := range enc.Codes {
t.Row(
symbolLabel(c.Symbol),
strconv.Itoa(countByte(worked, c.Symbol)),
"`"+c.String()+"`",
strconv.Itoa(c.Len),
)
}
b.WriteString(t.String() + "\n")
b.WriteString("The table is sorted by (length, symbol) and the codes are assigned ")
b.WriteString("from the lengths alone. That is what canonical means: the decoder ")
b.WriteString("rebuilds every code from one small integer per symbol, and two runs ")
b.WriteString("over the same input can never disagree about the table.\n\n")
b.WriteString("### The stream\n\n")
b.WriteString("```\n" + enc.BitString() + "\n```\n\n")
b.WriteString(ratioLine(enc) + "\n\n")
decoded, err := enc.Decode()
b.WriteString("`Decode()` returns ")
if err == nil && decoded == worked {
b.WriteString("`" + decoded + "`, the input it started from. ✅\n\n")
} else {
b.WriteString("the wrong string. ❌\n\n")
}
b.WriteString("## What the skew is worth\n\n")
st := ui.NewTable("input", "symbols", "raw", "coded", "saved")
for _, s := range samples {
e, err := huffman.Encode(s)
if err != nil {
continue
}
st.Row(
md.InlineCode(s),
strconv.Itoa(len(e.Codes)),
strconv.Itoa(e.Size*8)+" bits",
strconv.Itoa(e.NBits)+" bits",
strconv.Itoa(percent(e))+"%",
)
}
b.WriteString(st.String() + "\n")
b.WriteString("The floor is the alphabet, not the algorithm: eight distinct ")
b.WriteString("bytes used once each cost three bits apiece, which is what a ")
b.WriteString("fixed-width code over eight symbols would have spent anyway. ")
b.WriteString("Everything past that floor is bought with skew.\n\n")
b.WriteString("## The two inputs that break a naive implementation\n\n")
b.WriteString("**One distinct symbol.** Its leaf has no sibling, so the tree walk ")
b.WriteString("gives it a zero-bit code and the stream comes out empty: ")
if e, err := huffman.Encode("aaaaa"); err == nil && len(e.Codes) == 1 {
b.WriteString("here `aaaaa` is `" + e.BitString() + "`, five one-bit codes, ")
b.WriteString("and it is the only incomplete code the library emits.\n\n")
} else {
b.WriteString("the library refuses it instead.\n\n")
}
b.WriteString("**A payload that was edited.** `Decode` rebuilds the canonical ")
b.WriteString("table from the lengths it was handed and refuses a payload whose ")
b.WriteString("own bits disagree with it, so a stored `Encoded` cannot be bent ")
b.WriteString("into decoding as a different string:\n\n")
bent := &huffman.Encoded{
Codes: append([]huffman.Code(nil), enc.Codes...),
Data: append([]byte(nil), enc.Data...),
NBits: enc.NBits,
Size: enc.Size,
}
bent.Codes[1].Bits = 7
if _, err := bent.Decode(); err != nil {
b.WriteString("```\n" + err.Error() + "\n```\n\n")
}
b.WriteString("## Try your own\n\n")
b.WriteString("```\n/r/moul/x/daily/huffmandemo/v0:mississippi\n```\n")
return b.String()
}
// renderInput encodes a caller's text. Everything echoed back goes through
// md.InlineCode or ui.Inline: the string arrives from the URL and is
// attacker controlled markdown until it is escaped. A hand-built code span
// would not do, because an escaped backtick still closes the span.
func renderInput(in string) string {
var b strings.Builder
b.WriteString("# Huffman coding\n\n")
b.WriteString("Input: " + md.InlineCode(in) + "\n\n")
enc, err := huffman.Encode(in)
if err != nil {
b.WriteString("> " + ui.Inline(err.Error()) + "\n")
return b.String()
}
t := ui.NewTable("symbol", "count", "code", "bits")
for _, c := range enc.Codes {
t.Row(
symbolLabel(c.Symbol),
strconv.Itoa(countByte(in, c.Symbol)),
"`"+c.String()+"`",
strconv.Itoa(c.Len),
)
}
b.WriteString(t.String() + "\n")
b.WriteString(ratioLine(enc) + "\n\n")
b.WriteString("[back](/r/moul/x/daily/huffmandemo/v0)\n")
return b.String()
}
// ratioLine states the budget in one sentence.
func ratioLine(e *huffman.Encoded) string {
return strconv.Itoa(e.NBits) + " bits against " + strconv.Itoa(e.Size*8) +
" raw, " + strconv.Itoa(e.Saved()) + " saved (" + strconv.Itoa(percent(e)) + "%)."
}
// percent is the saving as a whole number. Integer arithmetic: a Render that
// prints a float is a Render that prints a different float on another node.
func percent(e *huffman.Encoded) int {
raw := e.Size * 8
if raw == 0 {
return 0
}
return e.Saved() * 100 / raw
}
// symbolLabel renders one byte for a table cell. A symbol is a BYTE, not a
// rune: converting a byte above 127 with string(b) produces a two-byte UTF-8
// sequence that is not the byte the code stands for, which would make the
// count beside it wrong for any non-ASCII input. Anything outside printable
// ASCII is shown as hex instead.
func symbolLabel(b byte) string {
switch b {
case ' ':
return "`(space)`"
case '`':
return "`` ` ``"
case '|':
return "`(pipe)`"
}
if b < 0x20 || b > 0x7e {
const hex = "0123456789abcdef"
return "`0x" + string(hex[b>>4]) + string(hex[b&0x0f]) + "`"
}
return "`" + string(b) + "`"
}
// countByte counts one byte in s, for the same reason symbolLabel exists.
func countByte(s string, b byte) int {
n := 0
for i := 0; i < len(s); i++ {
if s[i] == b {
n++
}
}
return n
}
func parseArg(path string) string {
s := strings.TrimSpace(path)
s = strings.TrimPrefix(s, "/")
return s
}
render_example_test.gno
package huffmandemo
// ExampleRender pins the realm's Render output as a testable example. Every
// figure in it is derived from the fixed strings in huffmandemo.gno, so a
// change in the library's table or bit count fails here.
func ExampleRender() {
print(Render(""))
// Output:
// # Huffman coding
//
// Frequency-based prefix codes, demoing the [`p/moul/x/daily/huffman`](/p/moul/x/daily/huffman/v0) library. Rare symbols get long codes, common ones get short codes, and no code is a prefix of another, so the stream needs no separators.
//
// ## `abracadabra`
//
// | symbol | count | code | bits |
// | --- | --- | --- | --- |
// | `a` | 5 | `0` | 1 |
// | `b` | 2 | `100` | 3 |
// | `c` | 1 | `101` | 3 |
// | `d` | 1 | `110` | 3 |
// | `r` | 2 | `111` | 3 |
//
// The table is sorted by (length, symbol) and the codes are assigned from the lengths alone. That is what canonical means: the decoder rebuilds every code from one small integer per symbol, and two runs over the same input can never disagree about the table.
//
// ### The stream
//
// ```
// 01001110101011001001110
// ```
//
// 23 bits against 88 raw, 65 saved (73%).
//
// `Decode()` returns `abracadabra`, the input it started from. ✅
//
// ## What the skew is worth
//
// | input | symbols | raw | coded | saved |
// | --- | --- | --- | --- | --- |
// | `abcdefgh` | 8 | 64 bits | 24 bits | 62% |
// | `the quick brown fox jumps over the lazy dog` | 27 | 344 bits | 192 bits | 44% |
// | `mississippi` | 4 | 88 bits | 21 bits | 76% |
// | `aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcd` | 4 | 264 bits | 38 bits | 85% |
//
// The floor is the alphabet, not the algorithm: eight distinct bytes used once each cost three bits apiece, which is what a fixed-width code over eight symbols would have spent anyway. Everything past that floor is bought with skew.
//
// ## The two inputs that break a naive implementation
//
// **One distinct symbol.** Its leaf has no sibling, so the tree walk gives it a zero-bit code and the stream comes out empty: here `aaaaa` is `00000`, five one-bit codes, and it is the only incomplete code the library emits.
//
// **A payload that was edited.** `Decode` rebuilds the canonical table from the lengths it was handed and refuses a payload whose own bits disagree with it, so a stored `Encoded` cannot be bent into decoding as a different string:
//
// ```
// huffman: corrupt payload
// ```
//
// ## Try your own
//
// ```
// /r/moul/x/daily/huffmandemo/v0:mississippi
// ```
}
// ExampleRender_input pins the caller-supplied path, which is the only part of
// the page that is not fixed.
func ExampleRender_input() {
print(Render("/hello"))
// Output:
// # Huffman coding
//
// Input: `hello`
//
// | symbol | count | code | bits |
// | --- | --- | --- | --- |
// | `e` | 1 | `00` | 2 |
// | `h` | 1 | `01` | 2 |
// | `l` | 2 | `10` | 2 |
// | `o` | 1 | `11` | 2 |
//
// 10 bits against 40 raw, 30 saved (75%).
//
// [back](/r/moul/x/daily/huffmandemo/v0)
}