Skip to content

Commit

Permalink
Use a single buffer for encoding
Browse files Browse the repository at this point in the history
Also with this in place switching to uint32 is worth it
ribasushi committed May 23, 2020
1 parent a282224 commit 986b8a8
Showing 1 changed file with 31 additions and 36 deletions.
67 changes: 31 additions & 36 deletions base36.go
Original file line number Diff line number Diff line change
@@ -41,58 +41,53 @@ func EncodeToStringLc(b []byte) string { return encode(b, LcAlphabet) }

func encode(inBuf []byte, al string) string {

// As a polar opposite to the base58 implementation, using a uint32 here is
// significantly slower
var carry uint64

var encIdx, valIdx, zcnt, high int

inSize := len(inBuf)
for zcnt < inSize && inBuf[zcnt] == 0 {
bufsz := len(inBuf)
zcnt := 0
for zcnt < bufsz && inBuf[zcnt] == 0 {
zcnt++
}

// Really this is log(256)/log(36) or 1.55, but integer math is easier
// Use 2 as a constant and just overallocate
encSize := (inSize - zcnt) * 2
// 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

// Allocate one big buffer up front
// Note: pools *DO NOT* help, the overhead of zeroing the val-half (see below)
// Note: pools *DO NOT* help, the overhead of zeroing
// kills any performance gain to be had
outBuf := make([]byte, (zcnt + encSize*2))
out := make([]byte, bufsz)

// use the second half for the temporary numeric buffer
val := outBuf[encSize+zcnt:]
var idx, stopIdx int
var carry uint32

high = encSize - 1
stopIdx = bufsz - 1
for _, b := range inBuf[zcnt:] {
valIdx = encSize - 1
for carry = uint64(b); valIdx > high || carry != 0; valIdx-- {
carry += uint64((val[valIdx])) * 256
val[valIdx] = byte(carry % 36)
idx = bufsz - 1
for carry = uint32(b); idx > stopIdx || carry != 0; idx-- {
carry += uint32((out[idx])) * 256
out[idx] = byte(carry % 36)
carry /= 36
}
high = valIdx
stopIdx = idx
}

// Reset the value index to the first significant value position
for valIdx = 0; valIdx < encSize && val[valIdx] == 0; valIdx++ {
// Determine the additional "zero-gap" in the buffer (aside from zcnt)
for stopIdx = zcnt; stopIdx < bufsz && out[stopIdx] == 0; stopIdx++ {
}

// Now write the known-length result to first half of buffer
encSize += zcnt - valIdx

for encIdx = 0; encIdx < zcnt; encIdx++ {
outBuf[encIdx] = '0'
}

for encIdx < encSize {
outBuf[encIdx] = al[val[valIdx]]
encIdx++
valIdx++
// Now encode the values with actual alphabet in-place
vBuf := out[stopIdx-zcnt:]
bufsz = len(vBuf)
for idx = 0; idx < bufsz; idx++ {
if idx < zcnt {
out[idx] = '0'
} else {
out[idx] = al[vBuf[idx]]
}
}

return string(outBuf[:encSize])
return string(out[:bufsz])
}

// DecodeString takes a base36 encoded string and returns a slice of the decoded

0 comments on commit 986b8a8

Please sign in to comment.