huffmandemo.gno
7.27 Kb · 216 lines
1// Package huffmandemo is a small gnoweb demo of the canonical Huffman codec
2// provided by the [p/moul/x/daily/huffman](/p/moul/x/daily/huffman/v0)
3// library: the code table for a worked example, what the packed stream looks
4// like, what the skew is worth, and the two inputs that break a naive
5// implementation.
6//
7// It contains no codec logic of its own. Stateless, so Render is
8// deterministic: every figure below is computed from the fixed strings at the
9// top of this file, never from chain state, which is what lets an example test
10// pin the page.
11package huffmandemo
12
13import (
14 "strconv"
15 "strings"
16
17 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/kit/ui/v0"
18 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/md/v0"
19 "gno.land/p/g1magld5ptgzaktqcexxq0pgq5lmdf0kz6re8hlv/x/daily/huffman/v0"
20)
21
22// worked is the example small enough to check by hand: 11 bytes, 5 symbols,
23// frequencies 5/2/2/1/1.
24const worked = "abracadabra"
25
26// samples show what the skew is worth. The first is flat by construction, the
27// last is almost all one symbol, and the ratio moves the whole way between.
28var samples = []string{
29 "abcdefgh",
30 "the quick brown fox jumps over the lazy dog",
31 "mississippi",
32 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcd",
33}
34
35// Render renders the demo for gnoweb.
36//
37// Render("") / Render("/") -> the worked example, the ratios, the edge cases
38// Render("/<text>") -> encode that text and show its table
39func Render(path string) string {
40 if in := parseArg(path); in != "" {
41 return renderInput(in)
42 }
43
44 var b strings.Builder
45 b.WriteString("# Huffman coding\n\n")
46 b.WriteString("Frequency-based prefix codes, demoing the ")
47 b.WriteString("[`p/moul/x/daily/huffman`](/p/moul/x/daily/huffman/v0) library. ")
48 b.WriteString("Rare symbols get long codes, common ones get short codes, and no ")
49 b.WriteString("code is a prefix of another, so the stream needs no separators.\n\n")
50
51 enc, err := huffman.Encode(worked)
52 if err != nil {
53 return b.String() + "> encoding failed: " + err.Error() + "\n"
54 }
55
56 b.WriteString("## `" + worked + "`\n\n")
57 t := ui.NewTable("symbol", "count", "code", "bits")
58 for _, c := range enc.Codes {
59 t.Row(
60 symbolLabel(c.Symbol),
61 strconv.Itoa(countByte(worked, c.Symbol)),
62 "`"+c.String()+"`",
63 strconv.Itoa(c.Len),
64 )
65 }
66 b.WriteString(t.String() + "\n")
67 b.WriteString("The table is sorted by (length, symbol) and the codes are assigned ")
68 b.WriteString("from the lengths alone. That is what canonical means: the decoder ")
69 b.WriteString("rebuilds every code from one small integer per symbol, and two runs ")
70 b.WriteString("over the same input can never disagree about the table.\n\n")
71
72 b.WriteString("### The stream\n\n")
73 b.WriteString("```\n" + enc.BitString() + "\n```\n\n")
74 b.WriteString(ratioLine(enc) + "\n\n")
75
76 decoded, err := enc.Decode()
77 b.WriteString("`Decode()` returns ")
78 if err == nil && decoded == worked {
79 b.WriteString("`" + decoded + "`, the input it started from. ✅\n\n")
80 } else {
81 b.WriteString("the wrong string. ❌\n\n")
82 }
83
84 b.WriteString("## What the skew is worth\n\n")
85 st := ui.NewTable("input", "symbols", "raw", "coded", "saved")
86 for _, s := range samples {
87 e, err := huffman.Encode(s)
88 if err != nil {
89 continue
90 }
91 st.Row(
92 md.InlineCode(s),
93 strconv.Itoa(len(e.Codes)),
94 strconv.Itoa(e.Size*8)+" bits",
95 strconv.Itoa(e.NBits)+" bits",
96 strconv.Itoa(percent(e))+"%",
97 )
98 }
99 b.WriteString(st.String() + "\n")
100 b.WriteString("The floor is the alphabet, not the algorithm: eight distinct ")
101 b.WriteString("bytes used once each cost three bits apiece, which is what a ")
102 b.WriteString("fixed-width code over eight symbols would have spent anyway. ")
103 b.WriteString("Everything past that floor is bought with skew.\n\n")
104
105 b.WriteString("## The two inputs that break a naive implementation\n\n")
106 b.WriteString("**One distinct symbol.** Its leaf has no sibling, so the tree walk ")
107 b.WriteString("gives it a zero-bit code and the stream comes out empty: ")
108 if e, err := huffman.Encode("aaaaa"); err == nil && len(e.Codes) == 1 {
109 b.WriteString("here `aaaaa` is `" + e.BitString() + "`, five one-bit codes, ")
110 b.WriteString("and it is the only incomplete code the library emits.\n\n")
111 } else {
112 b.WriteString("the library refuses it instead.\n\n")
113 }
114 b.WriteString("**A payload that was edited.** `Decode` rebuilds the canonical ")
115 b.WriteString("table from the lengths it was handed and refuses a payload whose ")
116 b.WriteString("own bits disagree with it, so a stored `Encoded` cannot be bent ")
117 b.WriteString("into decoding as a different string:\n\n")
118 bent := &huffman.Encoded{
119 Codes: append([]huffman.Code(nil), enc.Codes...),
120 Data: append([]byte(nil), enc.Data...),
121 NBits: enc.NBits,
122 Size: enc.Size,
123 }
124 bent.Codes[1].Bits = 7
125 if _, err := bent.Decode(); err != nil {
126 b.WriteString("```\n" + err.Error() + "\n```\n\n")
127 }
128
129 b.WriteString("## Try your own\n\n")
130 b.WriteString("```\n/r/moul/x/daily/huffmandemo/v0:mississippi\n```\n")
131 return b.String()
132}
133
134// renderInput encodes a caller's text. Everything echoed back goes through
135// md.InlineCode or ui.Inline: the string arrives from the URL and is
136// attacker controlled markdown until it is escaped. A hand-built code span
137// would not do, because an escaped backtick still closes the span.
138func renderInput(in string) string {
139 var b strings.Builder
140 b.WriteString("# Huffman coding\n\n")
141 b.WriteString("Input: " + md.InlineCode(in) + "\n\n")
142
143 enc, err := huffman.Encode(in)
144 if err != nil {
145 b.WriteString("> " + ui.Inline(err.Error()) + "\n")
146 return b.String()
147 }
148
149 t := ui.NewTable("symbol", "count", "code", "bits")
150 for _, c := range enc.Codes {
151 t.Row(
152 symbolLabel(c.Symbol),
153 strconv.Itoa(countByte(in, c.Symbol)),
154 "`"+c.String()+"`",
155 strconv.Itoa(c.Len),
156 )
157 }
158 b.WriteString(t.String() + "\n")
159 b.WriteString(ratioLine(enc) + "\n\n")
160 b.WriteString("[back](/r/moul/x/daily/huffmandemo/v0)\n")
161 return b.String()
162}
163
164// ratioLine states the budget in one sentence.
165func ratioLine(e *huffman.Encoded) string {
166 return strconv.Itoa(e.NBits) + " bits against " + strconv.Itoa(e.Size*8) +
167 " raw, " + strconv.Itoa(e.Saved()) + " saved (" + strconv.Itoa(percent(e)) + "%)."
168}
169
170// percent is the saving as a whole number. Integer arithmetic: a Render that
171// prints a float is a Render that prints a different float on another node.
172func percent(e *huffman.Encoded) int {
173 raw := e.Size * 8
174 if raw == 0 {
175 return 0
176 }
177 return e.Saved() * 100 / raw
178}
179
180// symbolLabel renders one byte for a table cell. A symbol is a BYTE, not a
181// rune: converting a byte above 127 with string(b) produces a two-byte UTF-8
182// sequence that is not the byte the code stands for, which would make the
183// count beside it wrong for any non-ASCII input. Anything outside printable
184// ASCII is shown as hex instead.
185func symbolLabel(b byte) string {
186 switch b {
187 case ' ':
188 return "`(space)`"
189 case '`':
190 return "`` ` ``"
191 case '|':
192 return "`(pipe)`"
193 }
194 if b < 0x20 || b > 0x7e {
195 const hex = "0123456789abcdef"
196 return "`0x" + string(hex[b>>4]) + string(hex[b&0x0f]) + "`"
197 }
198 return "`" + string(b) + "`"
199}
200
201// countByte counts one byte in s, for the same reason symbolLabel exists.
202func countByte(s string, b byte) int {
203 n := 0
204 for i := 0; i < len(s); i++ {
205 if s[i] == b {
206 n++
207 }
208 }
209 return n
210}
211
212func parseArg(path string) string {
213 s := strings.TrimSpace(path)
214 s = strings.TrimPrefix(s, "/")
215 return s
216}