Adds a base32 component.

components/base32/base32.cc

Index: components/base32/base32.cc
diff --git a/components/base32/base32.cc b/components/base32/base32.cc
new file mode 100644
index 0000000000000000000000000000000000000000..dd33521c1c7248414ab08ae7f30a072addec7ef8
--- /dev/null
+++ b/components/base32/base32.cc
@@ -0,0 +1,58 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/base32/base32.h"
+
+#include <stddef.h>
+#include <algorithm>
+
+namespace base32 {
+
+namespace {
+const char kEncoding[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";

[gab, 2016/06/03 18:46:11]

constexpr

[Rob Percival, 2016/06/04 06:20:25]

Done.

+}  // namespace
+
+std::string Base32Encode(base::StringPiece input, Base32EncodePolicy policy) {
+  std::string output;

[gab, 2016/06/03 18:46:11]

if (input.size() > std::numeric_limits<size_t>::max() / 8) {
  NOTREACHED() << "Input is too large and would overflow size computation
below.";
  return std::string();
}

// Per RFC4648, the output is formed of 8 characters per 40 bits of input and
// another 8 characters for the last group of [1,39] bits in the input.
// That is: ceil(input.size() * 8.0 / 40.0) * 8 ==
//          ceil(input.size() / 5.0) * 8 ==
//          ((input.size() + 4) / 5) * 8.
const size_t padded_length = ((input.size() + 4) / 5) * 8;

// When no padding is used, the output is exactly 1 character per 5 bits of
// input and one more for the last [1,4] bits.
// That is: ceil(input.size() * 8.0 / 5.0) ==
//          (input.size() * 8 + 4) / 5.
const size_t unpadded_length = (input.size() * 8 + 4) / 5;


std::string output;
output.reserve(encoded_length);

[Rob Percival, 2016/06/04 06:20:25]

Done. An alternative would be letting the caller reserve capacity in the output
string instead (and make it an out parameter, rather than a return value). I
only suggest this because the two prospective users of this component both only
encode fixed-length input (MD5 hashes and SHA256 hashes, respectively), so this
code adds unnecessary complexity. I'm happy with either.

+
+  // Transform 5 input bytes into 8 output bytes at a time.

[gab, 2016/06/03 18:46:11]

s/output bytes/characters/ (or "encoded characters")

[Rob Percival, 2016/06/04 06:20:25]

Acknowledged.

+  // Based on the encoding process described in RFC4648, section 6.
+  for (size_t input_offset = 0; input_offset < input.size();

[gab, 2016/06/03 18:46:11]

0U

[Rob Percival, 2016/06/04 06:20:25]

What effect does this have?

[gab, 2016/06/07 01:24:10]

Explicitly declares this constant as unsigned. I guess it's not required because
there is an implicit conversion at compile-time otherwise anyways, just a habit
of mine to be explicit about types.

+       input_offset += 5) {

[gab, 2016/06/03 18:46:11]

5U

[Rob Percival, 2016/06/04 06:20:25]

What effect does this have?

+    // Bits of input left to encode.

[gab, 2016/06/03 18:46:11]

// Bits of input left to encode in the current 40 bits (or less if at end)
block.

[Rob Percival, 2016/06/04 06:20:25]

Acknowledged.

+    size_t bits_remaining =
+        std::min(size_t(5), input.size() - input_offset) * 8;

[gab, 2016/06/03 18:46:11]

s/size_t(5)/5U/

[Rob Percival, 2016/06/04 06:20:25]

Is this semantically better or just shorter?

[gab, 2016/06/07 01:24:10]

It's more readable IMO because it's clearly a constant whereas size_t(5) is
constructor syntax. I assume you only do size_t(5) to avoid the signed/unsigned
warnings , 5U does just that.

+    // A buffer for up to 40 bits of input that is consumed 5 bits at a time.
+    // 40 bits is used because it is the lowest common multiple of 5 and 8.

[gab, 2016/06/03 18:46:11]

I'd remove the second sentence, no need to justify, that's the spec anyways. So
perhaps:

// A buffer for up to 40 bits of input that is consumed 5 bits at a time per
RFC4648.

[Rob Percival, 2016/06/04 06:20:25]

Acknowledged.

+    uint64_t input_group = 0;
+
+    // Load 8 bits at a time into the buffer.

[gab, 2016/06/03 18:46:11]

s/Load 8 bits at a time./Fill the buffer, 8 bits at a time./ ? (the current
comment somehow made me think you would only load 8 bits in this pass of the
loop)

[Rob Percival, 2016/06/04 06:20:25]

Acknowledged.

+    // Can't simply memcpy because of endianness.
+    for (size_t i = 0; i < bits_remaining / 8; ++i) {

[gab, 2016/06/03 18:46:11]

If |bits_remaining == 39| then 39 / 8 is 4 and you will only fill 32 bits in the
input_group.

(Need more tests to cover that use case?)

This algorithm appears more complex then the one that was in ShellUtil, I think
we can re-use that one with a slight tweak to handle padding. i.e. (plus tweak
to avoid special casing single byte inputs -- still need to return early on
empty inputs but that's okay):

// A bit stream which will be read from the left and appended to from the 
// right as it's emptied. 
uint16_t bit_stream = (static_cast<uint8_t>(input[0]) << 8); 
size_t next_byte_index = 1; 
int free_bits = 8;
while (free_bits < 16) {  
  // Extract the 5 leftmost bits in the stream  
  output.push_back(kEncoding[(bit_stream & 0xf800) >> 11]);  
  bit_stream <<= 5; 
  free_bits += 5; 

  // If there is enough room in the bit stream, inject another byte (if there 
  // are any left...).  
  if (free_bits >= 8 && next_byte_index < size) { 
    free_bits -= 8; 
    bit_stream += static_cast<uint8_t>(input[next_byte_index++]) << free_bits;  
  } 
}

if (policy == Base32EncodePolicy::INCLUDE_PADDING) {
  output.append(padded_length - unpadded_length,'=');
}

[Rob Percival, 2016/06/04 06:20:24]

|bits_remaining| is always a multiple of 8 at this point, so truncation is not
possible.
I suppose it is a bit more complicated. It's closer to how the RFC describes
doing it (in groups of 40 bits), but simplicity trumps that I think. I'll swap
in this algorithm.

+      input_group <<= 8;
+      input_group |= static_cast<uint8_t>(input[input_offset + i]);
+    }
+    // Shift the bits we've set to start at the MSB, for ease of access.
+    input_group <<= (64 - bits_remaining);
+
+    // Output the |input_group| as up to 8 bytes in base32.
+    // If we run out of bits, padding will make up the remaining bytes
+    // (unless |policy| dictates otherwise).
+    for (size_t output_count = 0; output_count < 8; ++output_count) {
+      if (bits_remaining == 0) {
+        if (policy == Base32EncodePolicy::INCLUDE_PADDING)
+          output.append(8 - output_count, '=');
+        break;
+      }
+      // Encode the first 5 bits, then shift them out of the buffer.
+      output.push_back(kEncoding[input_group >> 59]);
+      input_group <<= 5;
+      bits_remaining -= std::min(size_t(5), bits_remaining);
+    }
+  }
+

[gab, 2016/06/03 18:46:11]

#include "base/logging.h"

DCHECK_EQ(encoded_length, output.size()); 

[Rob Percival, 2016/06/04 06:20:25]

Done.

+  return output;
+}
+
+}  // namespace base32