1 // Copyright 2011 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 // Package base32 implements base32 encoding as specified by RFC 4648.
6 package base32
7 8 import (
9 "io"
10 "slices"
11 "strconv"
12 )
13 14 /*
15 * Encodings
16 */
17 18 // An Encoding is a radix 32 encoding/decoding scheme, defined by a
19 // 32-character alphabet. The most common is the "base32" encoding
20 // introduced for SASL GSSAPI and standardized in RFC 4648.
21 // The alternate "base32hex" encoding is used in DNSSEC.
22 type Encoding struct {
23 encode [32]byte // mapping of symbol index to symbol byte value
24 decodeMap [256]uint8 // mapping of symbol byte value to symbol index
25 padChar rune
26 }
27 28 const (
29 StdPadding rune = '=' // Standard padding character
30 NoPadding rune = -1 // No padding
31 )
32 33 const (
34 decodeMapInitialize = "" +
35 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
36 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
37 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
38 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
39 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
40 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
41 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
42 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
43 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
44 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
45 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
46 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
47 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
48 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
49 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff" +
50 "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
51 invalidIndex = '\xff'
52 )
53 54 // NewEncoding returns a new padded Encoding defined by the given alphabet,
55 // which must be a 32-byte string that contains unique byte values and
56 // does not contain the padding character or CR / LF ('\r', '\n').
57 // The alphabet is treated as a sequence of byte values
58 // without any special treatment for multi-byte UTF-8.
59 // The resulting Encoding uses the default padding character ('='),
60 // which may be changed or disabled via [Encoding.WithPadding].
61 func NewEncoding(encoder []byte) *Encoding {
62 if len(encoder) != 32 {
63 panic("encoding alphabet is not 32-bytes long")
64 }
65 66 e := &Encoding{}
67 e.padChar = StdPadding
68 copy(e.encode[:], encoder)
69 copy(e.decodeMap[:], decodeMapInitialize)
70 71 for i := 0; i < len(encoder); i++ {
72 // Note: While we document that the alphabet cannot contain
73 // the padding character, we do not enforce it since we do not know
74 // if the caller intends to switch the padding from StdPadding later.
75 switch {
76 case encoder[i] == '\n' || encoder[i] == '\r':
77 panic("encoding alphabet contains newline character")
78 case e.decodeMap[encoder[i]] != invalidIndex:
79 panic("encoding alphabet includes duplicate symbols")
80 }
81 e.decodeMap[encoder[i]] = uint8(i)
82 }
83 return e
84 }
85 86 // StdEncoding is the standard base32 encoding, as defined in RFC 4648.
87 var StdEncoding = NewEncoding("ABCDEFGHIJKLMNOPQRSTUVWXYZ234567")
88 89 // HexEncoding is the “Extended Hex Alphabet” defined in RFC 4648.
90 // It is typically used in DNS.
91 var HexEncoding = NewEncoding("0123456789ABCDEFGHIJKLMNOPQRSTUV")
92 93 // WithPadding creates a new encoding identical to enc except
94 // with a specified padding character, or NoPadding to disable padding.
95 // The padding character must not be '\r' or '\n',
96 // must not be contained in the encoding's alphabet,
97 // must not be negative, and must be a rune equal or below '\xff'.
98 // Padding characters above '\x7f' are encoded as their exact byte value
99 // rather than using the UTF-8 representation of the codepoint.
100 func (enc Encoding) WithPadding(padding rune) *Encoding {
101 switch {
102 case padding < NoPadding || padding == '\r' || padding == '\n' || padding > 0xff:
103 panic("invalid padding")
104 case padding != NoPadding && enc.decodeMap[byte(padding)] != invalidIndex:
105 panic("padding contained in alphabet")
106 }
107 enc.padChar = padding
108 return &enc
109 }
110 111 /*
112 * Encoder
113 */
114 115 // Encode encodes src using the encoding enc,
116 // writing [Encoding.EncodedLen](len(src)) bytes to dst.
117 //
118 // The encoding pads the output to a multiple of 8 bytes,
119 // so Encode is not appropriate for use on individual blocks
120 // of a large data stream. Use [NewEncoder] instead.
121 func (enc *Encoding) Encode(dst, src []byte) {
122 if len(src) == 0 {
123 return
124 }
125 // enc is a pointer receiver, so the use of enc.encode within the hot
126 // loop below means a nil check at every operation. Lift that nil check
127 // outside of the loop to speed up the encoder.
128 _ = enc.encode
129 130 di, si := 0, 0
131 n := (len(src) / 5) * 5
132 for si < n {
133 // Combining two 32 bit loads allows the same code to be used
134 // for 32 and 64 bit platforms.
135 hi := uint32(src[si+0])<<24 | uint32(src[si+1])<<16 | uint32(src[si+2])<<8 | uint32(src[si+3])
136 lo := hi<<8 | uint32(src[si+4])
137 138 dst[di+0] = enc.encode[(hi>>27)&0x1F]
139 dst[di+1] = enc.encode[(hi>>22)&0x1F]
140 dst[di+2] = enc.encode[(hi>>17)&0x1F]
141 dst[di+3] = enc.encode[(hi>>12)&0x1F]
142 dst[di+4] = enc.encode[(hi>>7)&0x1F]
143 dst[di+5] = enc.encode[(hi>>2)&0x1F]
144 dst[di+6] = enc.encode[(lo>>5)&0x1F]
145 dst[di+7] = enc.encode[(lo)&0x1F]
146 147 si += 5
148 di += 8
149 }
150 151 // Add the remaining small block
152 remain := len(src) - si
153 if remain == 0 {
154 return
155 }
156 157 // Encode the remaining bytes in reverse order.
158 val := uint32(0)
159 switch remain {
160 case 4:
161 val |= uint32(src[si+3])
162 dst[di+6] = enc.encode[val<<3&0x1F]
163 dst[di+5] = enc.encode[val>>2&0x1F]
164 val |= uint32(src[si+2]) << 8
165 dst[di+4] = enc.encode[val>>7&0x1F]
166 val |= uint32(src[si+1]) << 16
167 dst[di+3] = enc.encode[val>>12&0x1F]
168 dst[di+2] = enc.encode[val>>17&0x1F]
169 val |= uint32(src[si+0]) << 24
170 dst[di+1] = enc.encode[val>>22&0x1F]
171 dst[di+0] = enc.encode[val>>27&0x1F]
172 case 3:
173 val |= uint32(src[si+2]) << 8
174 dst[di+4] = enc.encode[val>>7&0x1F]
175 val |= uint32(src[si+1]) << 16
176 dst[di+3] = enc.encode[val>>12&0x1F]
177 dst[di+2] = enc.encode[val>>17&0x1F]
178 val |= uint32(src[si+0]) << 24
179 dst[di+1] = enc.encode[val>>22&0x1F]
180 dst[di+0] = enc.encode[val>>27&0x1F]
181 case 2:
182 val |= uint32(src[si+1]) << 16
183 dst[di+3] = enc.encode[val>>12&0x1F]
184 dst[di+2] = enc.encode[val>>17&0x1F]
185 val |= uint32(src[si+0]) << 24
186 dst[di+1] = enc.encode[val>>22&0x1F]
187 dst[di+0] = enc.encode[val>>27&0x1F]
188 case 1:
189 val |= uint32(src[si+0]) << 24
190 dst[di+1] = enc.encode[val>>22&0x1F]
191 dst[di+0] = enc.encode[val>>27&0x1F]
192 }
193 194 // Pad the final quantum
195 if enc.padChar != NoPadding {
196 nPad := (remain * 8 / 5) + 1
197 for i := nPad; i < 8; i++ {
198 dst[di+i] = byte(enc.padChar)
199 }
200 }
201 }
202 203 // AppendEncode appends the base32 encoded src to dst
204 // and returns the extended buffer.
205 func (enc *Encoding) AppendEncode(dst, src []byte) []byte {
206 n := enc.EncodedLen(len(src))
207 dst = slices.Grow(dst, n)
208 enc.Encode(dst[len(dst):][:n], src)
209 return dst[:len(dst)+n]
210 }
211 212 // EncodeToString returns the base32 encoding of src.
213 func (enc *Encoding) EncodeToString(src []byte) []byte {
214 buf := []byte{:enc.EncodedLen(len(src))}
215 enc.Encode(buf, src)
216 return []byte(buf)
217 }
218 219 type encoder struct {
220 err error
221 enc *Encoding
222 w io.Writer
223 buf [5]byte // buffered data waiting to be encoded
224 nbuf int // number of bytes in buf
225 out [1024]byte // output buffer
226 }
227 228 func (e *encoder) Write(p []byte) (n int, err error) {
229 if e.err != nil {
230 return 0, e.err
231 }
232 233 // Leading fringe.
234 if e.nbuf > 0 {
235 var i int
236 for i = 0; i < len(p) && e.nbuf < 5; i++ {
237 e.buf[e.nbuf] = p[i]
238 e.nbuf++
239 }
240 n += i
241 p = p[i:]
242 if e.nbuf < 5 {
243 return
244 }
245 e.enc.Encode(e.out[0:], e.buf[0:])
246 if _, e.err = e.w.Write(e.out[0:8]); e.err != nil {
247 return n, e.err
248 }
249 e.nbuf = 0
250 }
251 252 // Large interior chunks.
253 for len(p) >= 5 {
254 nn := len(e.out) / 8 * 5
255 if nn > len(p) {
256 nn = len(p)
257 nn -= nn % 5
258 }
259 e.enc.Encode(e.out[0:], p[0:nn])
260 if _, e.err = e.w.Write(e.out[0 : nn/5*8]); e.err != nil {
261 return n, e.err
262 }
263 n += nn
264 p = p[nn:]
265 }
266 267 // Trailing fringe.
268 copy(e.buf[:], p)
269 e.nbuf = len(p)
270 n += len(p)
271 return
272 }
273 274 // Close flushes any pending output from the encoder.
275 // It is an error to call Write after calling Close.
276 func (e *encoder) Close() error {
277 // If there's anything left in the buffer, flush it out
278 if e.err == nil && e.nbuf > 0 {
279 e.enc.Encode(e.out[0:], e.buf[0:e.nbuf])
280 encodedLen := e.enc.EncodedLen(e.nbuf)
281 e.nbuf = 0
282 _, e.err = e.w.Write(e.out[0:encodedLen])
283 }
284 return e.err
285 }
286 287 // NewEncoder returns a new base32 stream encoder. Data written to
288 // the returned writer will be encoded using enc and then written to w.
289 // Base32 encodings operate in 5-byte blocks; when finished
290 // writing, the caller must Close the returned encoder to flush any
291 // partially written blocks.
292 func NewEncoder(enc *Encoding, w io.Writer) io.WriteCloser {
293 return &encoder{enc: enc, w: w}
294 }
295 296 // EncodedLen returns the length in bytes of the base32 encoding
297 // of an input buffer of length n.
298 func (enc *Encoding) EncodedLen(n int) int {
299 if enc.padChar == NoPadding {
300 return n/5*8 + (n%5*8+4)/5
301 }
302 return (n + 4) / 5 * 8
303 }
304 305 /*
306 * Decoder
307 */
308 309 type CorruptInputError int64
310 311 func (e CorruptInputError) Error() string {
312 return "illegal base32 data at input byte " + strconv.FormatInt(int64(e), 10)
313 }
314 315 // decode is like Decode but returns an additional 'end' value, which
316 // indicates if end-of-message padding was encountered and thus any
317 // additional data is an error. This method assumes that src has been
318 // stripped of all supported whitespace ('\r' and '\n').
319 func (enc *Encoding) decode(dst, src []byte) (n int, end bool, err error) {
320 // Lift the nil check outside of the loop.
321 _ = enc.decodeMap
322 323 dsti := 0
324 olen := len(src)
325 326 for len(src) > 0 && !end {
327 // Decode quantum using the base32 alphabet
328 var dbuf [8]byte
329 dlen := 8
330 331 for j := 0; j < 8; {
332 333 if len(src) == 0 {
334 if enc.padChar != NoPadding {
335 // We have reached the end and are missing padding
336 return n, false, CorruptInputError(olen - len(src) - j)
337 }
338 // We have reached the end and are not expecting any padding
339 dlen, end = j, true
340 break
341 }
342 in := src[0]
343 src = src[1:]
344 if in == byte(enc.padChar) && j >= 2 && len(src) < 8 {
345 // We've reached the end and there's padding
346 if len(src)+j < 8-1 {
347 // not enough padding
348 return n, false, CorruptInputError(olen)
349 }
350 for k := 0; k < 8-1-j; k++ {
351 if len(src) > k && src[k] != byte(enc.padChar) {
352 // incorrect padding
353 return n, false, CorruptInputError(olen - len(src) + k - 1)
354 }
355 }
356 dlen, end = j, true
357 // 7, 5 and 2 are not valid padding lengths, and so 1, 3 and 6 are not
358 // valid dlen values. See RFC 4648 Section 6 "Base 32 Encoding" listing
359 // the five valid padding lengths, and Section 9 "Illustrations and
360 // Examples" for an illustration for how the 1st, 3rd and 6th base32
361 // src bytes do not yield enough information to decode a dst byte.
362 if dlen == 1 || dlen == 3 || dlen == 6 {
363 return n, false, CorruptInputError(olen - len(src) - 1)
364 }
365 break
366 }
367 dbuf[j] = enc.decodeMap[in]
368 if dbuf[j] == 0xFF {
369 return n, false, CorruptInputError(olen - len(src) - 1)
370 }
371 j++
372 }
373 374 // Pack 8x 5-bit source blocks into 5 byte destination
375 // quantum
376 switch dlen {
377 case 8:
378 dst[dsti+4] = dbuf[6]<<5 | dbuf[7]
379 n++
380 dst[dsti+3] = dbuf[4]<<7 | dbuf[5]<<2 | dbuf[6]>>3
381 n++
382 dst[dsti+2] = dbuf[3]<<4 | dbuf[4]>>1
383 n++
384 dst[dsti+1] = dbuf[1]<<6 | dbuf[2]<<1 | dbuf[3]>>4
385 n++
386 dst[dsti+0] = dbuf[0]<<3 | dbuf[1]>>2
387 n++
388 case 7:
389 dst[dsti+3] = dbuf[4]<<7 | dbuf[5]<<2 | dbuf[6]>>3
390 n++
391 dst[dsti+2] = dbuf[3]<<4 | dbuf[4]>>1
392 n++
393 dst[dsti+1] = dbuf[1]<<6 | dbuf[2]<<1 | dbuf[3]>>4
394 n++
395 dst[dsti+0] = dbuf[0]<<3 | dbuf[1]>>2
396 n++
397 case 5:
398 dst[dsti+2] = dbuf[3]<<4 | dbuf[4]>>1
399 n++
400 dst[dsti+1] = dbuf[1]<<6 | dbuf[2]<<1 | dbuf[3]>>4
401 n++
402 dst[dsti+0] = dbuf[0]<<3 | dbuf[1]>>2
403 n++
404 case 4:
405 dst[dsti+1] = dbuf[1]<<6 | dbuf[2]<<1 | dbuf[3]>>4
406 n++
407 dst[dsti+0] = dbuf[0]<<3 | dbuf[1]>>2
408 n++
409 case 2:
410 dst[dsti+0] = dbuf[0]<<3 | dbuf[1]>>2
411 n++
412 }
413 dsti += 5
414 }
415 return n, end, nil
416 }
417 418 // Decode decodes src using the encoding enc. It writes at most
419 // [Encoding.DecodedLen](len(src)) bytes to dst and returns the number of bytes
420 // written. The caller must ensure that dst is large enough to hold all
421 // the decoded data. If src contains invalid base32 data, it will return the
422 // number of bytes successfully written and [CorruptInputError].
423 // Newline characters (\r and \n) are ignored.
424 func (enc *Encoding) Decode(dst, src []byte) (n int, err error) {
425 buf := []byte{:len(src)}
426 l := stripNewlines(buf, src)
427 n, _, err = enc.decode(dst, buf[:l])
428 return
429 }
430 431 // AppendDecode appends the base32 decoded src to dst
432 // and returns the extended buffer.
433 // If the input is malformed, it returns the partially decoded src and an error.
434 // New line characters (\r and \n) are ignored.
435 func (enc *Encoding) AppendDecode(dst, src []byte) ([]byte, error) {
436 // Compute the output size without padding to avoid over allocating.
437 n := len(src)
438 for n > 0 && rune(src[n-1]) == enc.padChar {
439 n--
440 }
441 n = decodedLen(n, NoPadding)
442 443 dst = slices.Grow(dst, n)
444 n, err := enc.Decode(dst[len(dst):][:n], src)
445 return dst[:len(dst)+n], err
446 }
447 448 // DecodeString returns the bytes represented by the base32 string s.
449 // If the input is malformed, it returns the partially decoded data and
450 // [CorruptInputError]. New line characters (\r and \n) are ignored.
451 func (enc *Encoding) DecodeString(s []byte) ([]byte, error) {
452 buf := []byte(s)
453 l := stripNewlines(buf, buf)
454 n, _, err := enc.decode(buf, buf[:l])
455 return buf[:n], err
456 }
457 458 type decoder struct {
459 err error
460 enc *Encoding
461 r io.Reader
462 end bool // saw end of message
463 buf [1024]byte // leftover input
464 nbuf int
465 out []byte // leftover decoded output
466 outbuf [1024 / 8 * 5]byte
467 }
468 469 func readEncodedData(r io.Reader, buf []byte, min int, expectsPadding bool) (n int, err error) {
470 for n < min && err == nil {
471 var nn int
472 nn, err = r.Read(buf[n:])
473 n += nn
474 }
475 // data was read, less than min bytes could be read
476 if n < min && n > 0 && err == io.EOF {
477 err = io.ErrUnexpectedEOF
478 }
479 // no data was read, the buffer already contains some data
480 // when padding is disabled this is not an error, as the message can be of
481 // any length
482 if expectsPadding && min < 8 && n == 0 && err == io.EOF {
483 err = io.ErrUnexpectedEOF
484 }
485 return
486 }
487 488 func (d *decoder) Read(p []byte) (n int, err error) {
489 // Use leftover decoded output from last read.
490 if len(d.out) > 0 {
491 n = copy(p, d.out)
492 d.out = d.out[n:]
493 if len(d.out) == 0 {
494 return n, d.err
495 }
496 return n, nil
497 }
498 499 if d.err != nil {
500 return 0, d.err
501 }
502 503 // Read a chunk.
504 nn := (len(p) + 4) / 5 * 8
505 if nn < 8 {
506 nn = 8
507 }
508 if nn > len(d.buf) {
509 nn = len(d.buf)
510 }
511 512 // Minimum amount of bytes that needs to be read each cycle
513 var min int
514 var expectsPadding bool
515 if d.enc.padChar == NoPadding {
516 min = 1
517 expectsPadding = false
518 } else {
519 min = 8 - d.nbuf
520 expectsPadding = true
521 }
522 523 nn, d.err = readEncodedData(d.r, d.buf[d.nbuf:nn], min, expectsPadding)
524 d.nbuf += nn
525 if d.nbuf < min {
526 return 0, d.err
527 }
528 if nn > 0 && d.end {
529 return 0, CorruptInputError(0)
530 }
531 532 // Decode chunk into p, or d.out and then p if p is too small.
533 var nr int
534 if d.enc.padChar == NoPadding {
535 nr = d.nbuf
536 } else {
537 nr = d.nbuf / 8 * 8
538 }
539 nw := d.enc.DecodedLen(d.nbuf)
540 541 if nw > len(p) {
542 nw, d.end, err = d.enc.decode(d.outbuf[0:], d.buf[0:nr])
543 d.out = d.outbuf[0:nw]
544 n = copy(p, d.out)
545 d.out = d.out[n:]
546 } else {
547 n, d.end, err = d.enc.decode(p, d.buf[0:nr])
548 }
549 d.nbuf -= nr
550 for i := 0; i < d.nbuf; i++ {
551 d.buf[i] = d.buf[i+nr]
552 }
553 554 if err != nil && (d.err == nil || d.err == io.EOF) {
555 d.err = err
556 }
557 558 if len(d.out) > 0 {
559 // We cannot return all the decoded bytes to the caller in this
560 // invocation of Read, so we return a nil error to ensure that Read
561 // will be called again. The error stored in d.err, if any, will be
562 // returned with the last set of decoded bytes.
563 return n, nil
564 }
565 566 return n, d.err
567 }
568 569 type newlineFilteringReader struct {
570 wrapped io.Reader
571 }
572 573 // stripNewlines removes newline characters and returns the number
574 // of non-newline characters copied to dst.
575 func stripNewlines(dst, src []byte) int {
576 offset := 0
577 for _, b := range src {
578 if b == '\r' || b == '\n' {
579 continue
580 }
581 dst[offset] = b
582 offset++
583 }
584 return offset
585 }
586 587 func (r *newlineFilteringReader) Read(p []byte) (int, error) {
588 n, err := r.wrapped.Read(p)
589 for n > 0 {
590 s := p[0:n]
591 offset := stripNewlines(s, s)
592 if err != nil || offset > 0 {
593 return offset, err
594 }
595 // Previous buffer entirely whitespace, read again
596 n, err = r.wrapped.Read(p)
597 }
598 return n, err
599 }
600 601 // NewDecoder constructs a new base32 stream decoder.
602 func NewDecoder(enc *Encoding, r io.Reader) io.Reader {
603 return &decoder{enc: enc, r: &newlineFilteringReader{r}}
604 }
605 606 // DecodedLen returns the maximum length in bytes of the decoded data
607 // corresponding to n bytes of base32-encoded data.
608 func (enc *Encoding) DecodedLen(n int) int {
609 return decodedLen(n, enc.padChar)
610 }
611 612 func decodedLen(n int, padChar rune) int {
613 if padChar == NoPadding {
614 return n/8*5 + n%8*5/8
615 }
616 return n / 8 * 5
617 }
618