base58.gno

  1// Package base58 ports the core of Bitcoin's Base58 codec (à la mr-tron/base58
  2// and btcutil/base58) to a gno.land realm.
  3//
  4// Base58 is a base conversion from base-256 (raw bytes) to base-58 using an
  5// alphabet that omits the visually ambiguous characters 0 (zero), O (capital
  6// o), I (capital i) and l (lower L). The conversion here is done with pure
  7// byte-slice math — the classic div/mod-by-58 carry loop — so it needs no
  8// math/big. Leading zero bytes map to leading '1' characters and back, exactly
  9// like the reference implementations.
 10package base58
 11
 12import (
 13	"encoding/hex"
 14	"strings"
 15)
 16
 17// Alphabet is the Bitcoin Base58 alphabet.
 18const Alphabet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
 19
 20// Encode converts a byte slice to its Base58 string representation.
 21//
 22// Algorithm: treat the input as a big base-256 integer and repeatedly convert
 23// it into base-58 digits via a carry loop, most-significant digit first. Each
 24// leading zero byte becomes a leading '1'.
 25func Encode(input []byte) string {
 26	// Count leading zero bytes — they encode as '1' and are handled apart.
 27	zeros := 0
 28	for zeros < len(input) && input[zeros] == 0 {
 29		zeros++
 30	}
 31
 32	// Upper bound on the base-58 digit count: log(256)/log(58) ≈ 1.365, so
 33	// 138/100 of the significant byte count (+1) is always enough.
 34	size := (len(input)-zeros)*138/100 + 1
 35	digits := make([]byte, size)
 36
 37	length := 0
 38	for i := zeros; i < len(input); i++ {
 39		carry := int(input[i])
 40		j := 0
 41		// Walk from the least-significant end, folding the new byte in.
 42		for k := size - 1; (carry != 0 || j < length) && k >= 0; k-- {
 43			carry += 256 * int(digits[k])
 44			digits[k] = byte(carry % 58)
 45			carry /= 58
 46			j++
 47		}
 48		length = j
 49	}
 50
 51	// Skip the leading zero digits produced by the over-allocation.
 52	it := size - length
 53
 54	out := make([]byte, 0, zeros+length)
 55	for i := 0; i < zeros; i++ {
 56		out = append(out, '1')
 57	}
 58	for ; it < size; it++ {
 59		out = append(out, Alphabet[digits[it]])
 60	}
 61	return string(out)
 62}
 63
 64// Decode converts a Base58 string back to the original byte slice. It returns
 65// nil if the string contains a character outside the alphabet.
 66//
 67// Algorithm: the mirror of Encode — treat the string as a big base-58 integer
 68// and convert it back to base-256 bytes with a carry loop. Each leading '1'
 69// becomes a leading zero byte.
 70func Decode(s string) []byte {
 71	// Count leading '1's — they decode to zero bytes.
 72	zeros := 0
 73	for zeros < len(s) && s[zeros] == '1' {
 74		zeros++
 75	}
 76
 77	// Upper bound on the byte count: log(58)/log(256) ≈ 0.733.
 78	size := (len(s)-zeros)*733/1000 + 1
 79	bytesBuf := make([]byte, size)
 80
 81	length := 0
 82	for i := zeros; i < len(s); i++ {
 83		carry := strings.IndexByte(Alphabet, s[i])
 84		if carry < 0 {
 85			return nil // character not in the alphabet
 86		}
 87		j := 0
 88		for k := size - 1; (carry != 0 || j < length) && k >= 0; k-- {
 89			carry += 58 * int(bytesBuf[k])
 90			bytesBuf[k] = byte(carry % 256)
 91			carry /= 256
 92			j++
 93		}
 94		length = j
 95	}
 96
 97	it := size - length
 98
 99	out := make([]byte, 0, zeros+length)
100	for i := 0; i < zeros; i++ {
101		out = append(out, 0)
102	}
103	for ; it < size; it++ {
104		out = append(out, bytesBuf[it])
105	}
106	return out
107}
108
109// IsValid reports whether every character of s belongs to the Base58 alphabet.
110func IsValid(s string) bool {
111	for i := 0; i < len(s); i++ {
112		if strings.IndexByte(Alphabet, s[i]) < 0 {
113			return false
114		}
115	}
116	return true
117}
118
119// Render produces the gnoweb Markdown view.
120//
121//   - "/"        → the alphabet + a small gallery of worked examples.
122//   - "/<hex>"   → decode the hex input to bytes, show its Base58, and the
123//     hex-encoded decoded round-trip to prove Encode/Decode are inverse.
124func Render(path string) string {
125	arg := strings.TrimPrefix(path, "/")
126	arg = strings.TrimSpace(arg)
127
128	if arg == "" {
129		return renderHome()
130	}
131	return renderHex(arg)
132}
133
134func renderHome() string {
135	var b strings.Builder
136	b.WriteString("# Base58 (Bitcoin alphabet)\n\n")
137	b.WriteString("Base conversion from raw bytes (base-256) to base-58, using the ")
138	b.WriteString("Bitcoin alphabet — no `0`, `O`, `I`, `l`. Implemented with pure ")
139	b.WriteString("byte-slice math (div/mod-by-58 carry loop), no `math/big`.\n\n")
140
141	b.WriteString("## Alphabet\n\n")
142	b.WriteString("```\n")
143	b.WriteString(Alphabet)
144	b.WriteString("\n```\n\n")
145	b.WriteString("58 characters, index 0…57.\n\n")
146
147	b.WriteString("## Examples\n\n")
148	b.WriteString("| input (utf-8) | hex | Base58 |\n")
149	b.WriteString("|---|---|---|\n")
150	examples := []string{"", "hello world", "gno.land", "Bitcoin"}
151	for _, e := range examples {
152		h := hex.EncodeToString([]byte(e))
153		if h == "" {
154			h = "(empty)"
155		}
156		label := e
157		if label == "" {
158			label = "(empty)"
159		}
160		b.WriteString("| `" + label + "` | `" + h + "` | `" + Encode([]byte(e)) + "` |\n")
161	}
162	b.WriteString("\n")
163
164	b.WriteString("Leading zero bytes → leading `1`s:\n\n")
165	b.WriteString("| bytes | Base58 |\n|---|---|\n")
166	b.WriteString("| `[0x00]` | `" + Encode([]byte{0}) + "` |\n")
167	b.WriteString("| `[0x00 0x00 0x00]` | `" + Encode([]byte{0, 0, 0}) + "` |\n\n")
168
169	b.WriteString("## Try it\n\n")
170	b.WriteString("Append a hex string to the path to encode/round-trip it:\n\n")
171	b.WriteString("- `/68656c6c6f` — the bytes for \"hello\"\n")
172	b.WriteString("- `/00000000` — four zero bytes\n")
173	b.WriteString("- `/deadbeef`\n")
174	return b.String()
175}
176
177func renderHex(arg string) string {
178	var b strings.Builder
179	b.WriteString("# Base58 — round-trip\n\n")
180	b.WriteString("[← alphabet & examples](/r/moul/x/daily/base58/v1)\n\n")
181
182	raw, err := hex.DecodeString(arg)
183	if err != nil {
184		b.WriteString("**Invalid hex input.**\n\n")
185		b.WriteString("`" + arg + "` is not a valid hex string. ")
186		b.WriteString("Provide an even number of hex digits, e.g. `/deadbeef`.\n")
187		return b.String()
188	}
189
190	encoded := Encode(raw)
191	decoded := Decode(encoded)
192	roundTrip := hex.EncodeToString(decoded)
193
194	inHex := arg
195	if inHex == "" {
196		inHex = "(empty)"
197	}
198	outHex := roundTrip
199	if outHex == "" {
200		outHex = "(empty)"
201	}
202	enc := encoded
203	if enc == "" {
204		enc = "(empty)"
205	}
206
207	b.WriteString("| step | value |\n|---|---|\n")
208	b.WriteString("| hex input | `" + inHex + "` |\n")
209	b.WriteString("| bytes | `" + byteList(raw) + "` |\n")
210	b.WriteString("| **Base58** | `" + enc + "` |\n")
211	b.WriteString("| decoded (hex) | `" + outHex + "` |\n\n")
212
213	if roundTrip == arg {
214		b.WriteString("✓ Round-trip matches: `Decode(Encode(x)) == x`.\n")
215	} else {
216		b.WriteString("✗ Round-trip mismatch.\n")
217	}
218	return b.String()
219}
220
221// byteList renders a byte slice as a compact space-separated hex list.
222func byteList(b []byte) string {
223	if len(b) == 0 {
224		return "(none)"
225	}
226	const digits = "0123456789abcdef"
227	out := make([]byte, 0, len(b)*3)
228	for i, c := range b {
229		if i > 0 {
230			out = append(out, ' ')
231		}
232		out = append(out, digits[c>>4], digits[c&0x0f])
233	}
234	return string(out)
235}