1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
/*
Package base36 provides a reasonably fast implementation of a binary base36 codec.
*/
package base36
// Simplified code based on https://godoc.org/github.com/mr-tron/base58
// which in turn is based on https://github.com/trezor/trezor-crypto/commit/89a7d7797b806fac
import (
"fmt"
)
const UcAlphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
const LcAlphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
const maxDigitOrdinal = 'z'
const maxDigitValueB36 = 35
var revAlphabet [maxDigitOrdinal + 1]byte
func init() {
for i := range revAlphabet {
revAlphabet[i] = maxDigitValueB36 + 1
}
for i, c := range UcAlphabet {
revAlphabet[byte(c)] = byte(i)
if c > '9' {
revAlphabet[byte(c)+32] = byte(i)
}
}
}
// EncodeToStringUc encodes the given byte-buffer as base36 using [0-9A-Z] as
// the digit-alphabet
func EncodeToStringUc(b []byte) string { return encode(b, UcAlphabet) }
// EncodeToStringLc encodes the given byte-buffer as base36 using [0-9a-z] as
// the digit-alphabet
func EncodeToStringLc(b []byte) string { return encode(b, LcAlphabet) }
func encode(inBuf []byte, al string) string {
bufsz := len(inBuf)
zcnt := 0
for zcnt < bufsz && inBuf[zcnt] == 0 {
zcnt++
}
// It is crucial to make this as short as possible, especially for
// the usual case of CIDs.
bufsz = zcnt +
// This is an integer simplification of
// ceil(log(256)/log(36))
(bufsz-zcnt)*277/179 + 1
// Note: pools *DO NOT* help, the overhead of zeroing
// kills any performance gain to be had
out := make([]byte, bufsz)
var idx, stopIdx int
var carry uint32
stopIdx = bufsz - 1
for _, b := range inBuf[zcnt:] {
idx = bufsz - 1
for carry = uint32(b); idx > stopIdx || carry != 0; idx-- {
carry += uint32((out[idx])) * 256
out[idx] = byte(carry % 36)
carry /= 36
}
stopIdx = idx
}
// Determine the additional "zero-gap" in the buffer (aside from zcnt)
for stopIdx = zcnt; stopIdx < bufsz && out[stopIdx] == 0; stopIdx++ {
}
// Now encode the values with actual alphabet in-place
vBuf := out[stopIdx-zcnt:]
bufsz = len(vBuf)
for idx = 0; idx < bufsz; idx++ {
out[idx] = al[vBuf[idx]]
}
return string(out[:bufsz])
}
// DecodeString takes a base36 encoded string and returns a slice of the decoded
// bytes.
func DecodeString(s string) ([]byte, error) {
if len(s) == 0 {
return nil, fmt.Errorf("can not decode zero-length string")
}
zcnt := 0
for zcnt < len(s) && s[zcnt] == '0' {
zcnt++
}
// the 32bit algo stretches the result up to 2 times
binu := make([]byte, 2*(((len(s))*179/277)+1)) // no more than 84 bytes when len(s) <= 64
outi := make([]uint32, (len(s)+3)/4) // no more than 16 bytes when len(s) <= 64
for _, r := range s {
if r > maxDigitOrdinal || revAlphabet[r] > maxDigitValueB36 {
return nil, fmt.Errorf("invalid base36 character (%q)", r)
}
c := uint64(revAlphabet[r])
for j := len(outi) - 1; j >= 0; j-- {
t := uint64(outi[j])*36 + c
c = (t >> 32)
outi[j] = uint32(t & 0xFFFFFFFF)
}
}
mask := (uint(len(s)%4) * 8)
if mask == 0 {
mask = 32
}
mask -= 8
outidx := 0
for j := 0; j < len(outi); j++ {
for mask < 32 { // loop relies on uint overflow
binu[outidx] = byte(outi[j] >> mask)
mask -= 8
outidx++
}
mask = 24
}
// find the most significant byte post-decode, if any
for msb := zcnt; msb < outidx; msb++ {
if binu[msb] > 0 {
return binu[msb-zcnt : outidx : outidx], nil
}
}
// it's all zeroes
return binu[:outidx:outidx], nil
}
|
