1 // Copyright 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "components/base32/base32.h"
6
7 #include <stddef.h>
8
9 #include <limits>
10
11 #include "base/check_op.h"
12 #include "base/numerics/safe_math.h"
13
14 namespace base32 {
15
16 namespace {
17
18 // Returns a 5 bit number between [0,31] matching the provided base 32 encoded
19 // character. Returns 0xff on error.
ReverseMapping(char input_char)20 uint8_t ReverseMapping(char input_char) {
21 if (input_char >= 'A' && input_char <= 'Z')
22 return input_char - 'A';
23 if (input_char >= '2' && input_char <= '7')
24 return input_char - '2' + 26;
25 return 0xff;
26 }
27
28 } // namespace
29
Base32Encode(base::StringPiece input,Base32EncodePolicy policy)30 std::string Base32Encode(base::StringPiece input, Base32EncodePolicy policy) {
31 if (input.empty())
32 return std::string();
33
34 // Per RFC4648, the output is formed of 8 characters per 40 bits of input and
35 // another 8 characters for the last group of [1,39] bits in the input.
36 // That is: ceil(input.size() * 8.0 / 40.0) * 8 ==
37 // ceil(input.size() / 5.0) * 8 ==
38 // ((input.size() + 4) / 5) * 8.
39 const size_t padded_length = ((input.size() + 4) / 5) * 8;
40
41 // When no padding is used, the output is exactly 1 character per 5 bits of
42 // input and one more for the last [1,4] bits.
43 // That is: ceil(input.size() * 8.0 / 5.0) ==
44 // (input.size() * 8 + 4) / 5.
45 const size_t unpadded_length =
46 ((base::MakeCheckedNum(input.size()) * 8 + 4) / 5).ValueOrDie();
47
48 std::string output;
49 const size_t encoded_length = policy == Base32EncodePolicy::INCLUDE_PADDING
50 ? padded_length
51 : unpadded_length;
52 output.reserve(encoded_length);
53
54 // A bit stream which will be read from the left and appended to from the
55 // right as it's emptied.
56 uint16_t bit_stream = (static_cast<uint8_t>(input[0]) << 8);
57 size_t next_byte_index = 1;
58 int free_bits = 8;
59 while (free_bits < 16) {
60 // Extract the 5 leftmost bits in the stream
61 output.push_back(kEncoding[bit_stream >> 11]);
62 bit_stream <<= 5;
63 free_bits += 5;
64
65 // If there is enough room in the bit stream, inject another byte (if there
66 // are any left...).
67 if (free_bits >= 8 && next_byte_index < input.size()) {
68 free_bits -= 8;
69 bit_stream += static_cast<uint8_t>(input[next_byte_index++]) << free_bits;
70 }
71 }
72
73 if (policy == Base32EncodePolicy::INCLUDE_PADDING) {
74 output.append(padded_length - unpadded_length, kPaddingChar);
75 }
76
77 DCHECK_EQ(encoded_length, output.size());
78 return output;
79 }
80
Base32Decode(base::StringPiece input)81 std::string Base32Decode(base::StringPiece input) {
82 // Remove padding, if any
83 const size_t padding_index = input.find(kPaddingChar);
84 if (padding_index != base::StringPiece::npos)
85 input.remove_suffix(input.size() - padding_index);
86
87 if (input.empty())
88 return std::string();
89
90 const size_t decoded_length =
91 (base::MakeCheckedNum(input.size()) * 5 / 8).ValueOrDie();
92
93 std::string output;
94 output.reserve(decoded_length);
95
96 // A bit stream which will be read from the left and appended to from the
97 // right as it's emptied.
98 uint16_t bit_stream = 0;
99 size_t free_bits = 16;
100 for (char input_char : input) {
101 const uint8_t decoded_5bits = ReverseMapping(input_char);
102 // If an invalid character is read from the input, then stop decoding.
103 if (decoded_5bits >= 32)
104 return std::string();
105
106 // Place the next decoded 5-bits in the stream.
107 bit_stream |= decoded_5bits << (free_bits - 5);
108 free_bits -= 5;
109
110 // If the stream is filled with a byte, flush the stream of that byte and
111 // append it to the output.
112 if (free_bits <= 8) {
113 output.push_back(static_cast<char>(bit_stream >> 8));
114 bit_stream <<= 8;
115 free_bits += 8;
116 }
117 }
118
119 DCHECK_EQ(decoded_length, output.size());
120 return output;
121 }
122
123 } // namespace base32
124