b58.gno

  1// Package b58 ports the core of Bitcoin's Base58 codec (à la mr-tron/base58 and
  2// btcutil/base58) to gno — as a reusable pure package.
  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 is done with pure byte-slice
  7// math — the classic div/mod-by-58 carry loop — so it needs no math/big. Leading
  8// zero bytes map to leading '1' characters and back, exactly like the reference
  9// implementations.
 10//
 11// A live demo of this package (an interactive encoder / round-tripper) is at
 12// [r/moul/x/daily/b58demo](/r/moul/x/daily/b58demo/v0).
 13package b58
 14
 15import "strings"
 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}