Add support for decoding base64.

[clayborg]

Summary

An upcoming patch to LLDB will require the ability to decode base64. This patch adds support for decoding base64 and adds tests.

[clayborg]

Removed an extra string that was added to Base64Test::Base64 during testing.

[alexander-shaposhnikov]

llvm/include/llvm/Support/Base64.h

58

https://godbolt.org/z/1rqe19MPM vs https://godbolt.org/z/sa1z6M8xf (although this for GCC)
-1 -> char - i guess this might trigger -Wnarrowing

[clayborg]

llvm/include/llvm/Support/Base64.h

58

Is there a suffix I need to add to the "-1"?

[clayborg]

Don't use -1 as the invalid table value, use 64 to avoid triggering narrowing conversion errors.

[alexander-shaposhnikov]

llvm/include/llvm/Support/Base64.h

58

unfortunately i don't know off the top of my head

[serge-sans-paille]

llvm/include/llvm/Support/Base64.h

58

if declared static, this will go in RO data and lead to more efficient code, see https://godbolt.org/z/z4zsqKqEn

66

Shouldn't DecodeTable be part of the capture list?

77

nit: multiple

85

I wonder if the code would be simpler to read if the handling of the trailing '=' would be in a separate loop, that way we would have a first loop that does the fast and straight-forward processing of the stream, then a slightly more complex code to handle the trailing bytes?

100

this if could be nested in above else

[serge-sans-paille]

llvm/include/llvm/Support/Base64.h

68

I think declaring constexpr char Invalid = 64 in the function prologue and then using it everywhere would also helps readability ;-)

[clayborg]

Address feedback:

• Handle any bad '=' characters separately before the main loop.
• Remember how many bytes to strip after decoding all bytes.
• Use "Inv" constexpr instead of the magic 64 number to make things more readable
• Update tests for changes

[clayborg]

llvm/include/llvm/Support/Base64.h

85

Actually this would be a good idea to verify that the string ends with at most two '=' characters, and this would help to detect '=' characters in the middle of the string which would be a different error.

[serge-sans-paille]

llvm/include/llvm/Support/Base64.h

69

Would that make sens to set '=' as Inv here? That would prevent you from the initial find

[clayborg]

llvm/include/llvm/Support/Base64.h

69

We can't, we need it to decode to zero so we can always decode 3 bytes worth of output. We then drop any extra zero bytes based on "NumBytesToStrip" at the end. It also keeps the logic much cleaner in the main decode loop since we don't have to check.

[serge-sans-paille]

llvm/include/llvm/Support/Base64.h

69

I understand your point. Doing two pass over the sequence just for the sake of error checking bothers me a bit, I'd rather have a different handler for the tail. Do you have any idea of the length of a typical sequence?

[clayborg]

Updated the code to not pass over the input twice. We now check for invalid '=' characters in the decoding loop. Also changed how we strip extra bytes from the end of the decoded input by looking at the back of the Input string since we already detect invalid '=' characters in the main string and would have returned an error already.

[serge-sans-paille]

Sorry for the back and forth: I find the logic difficult to follow. What would you think of something along these lines (untested) https://godbolt.org/z/vh356fhaP

[aprantl]

llvm/include/llvm/Support/Base64.h

56

Why the template? Would something like SmallVectorImpl<uint8_t> work here?

57

I think an ErrorOr<OutputBytes> or Optional<OutputBytes> would be more idiomatic here?

[clayborg]

In D126254#3549946, @serge-sans-paille wrote:

Sorry for the back and forth: I find the logic difficult to follow. What would you think of something along these lines (untested) https://godbolt.org/z/vh356fhaP

I found that makes the code a bit harder to read and there is a few dups of the "Invalid Base64 character" error producing code sites.

llvm/include/llvm/Support/Base64.h

56

Then any collection class can be used, including SmallVectorImpl<uint8_t>.

57

I can see if that would work. I couldn't remember if you can specialized on return value...

69

I fixed the loop to check for equals in the main loop and got rid of the two loops through the input string.

[clayborg]

ping

[aprantl]

llvm/include/llvm/Support/Base64.h

61

Could we rename this to Base64DecodeTable? It sits in the top-level llvm namespace after all.

[clayborg]

llvm/include/llvm/Support/Base64.h

61

this is a static inside of the decodeBase64 function, so it isn't in the top level llvm namespace.

[dyung]

Your change is failing to build on the PS4 Windows bot, can you take a look and revert if it takes time to fix?

https://lab.llvm.org/buildbot/#/builders/216/builds/6340

FAILED: unittests/Support/CMakeFiles/SupportTests.dir/Base64Test.cpp.obj 
C:\PROGRA~2\MICROS~1\2019\BUILDT~1\VC\Tools\MSVC\1429~1.301\bin\Hostx64\x64\cl.exe  /nologo /TP -DGTEST_HAS_RTTI=0 -DUNICODE -D_CRT_NONSTDC_NO_DEPRECATE -D_CRT_NONSTDC_NO_WARNINGS -D_CRT_SECURE_NO_DEPRECATE -D_CRT_SECURE_NO_WARNINGS -D_HAS_EXCEPTIONS=0 -D_SCL_SECURE_NO_DEPRECATE -D_SCL_SECURE_NO_WARNINGS -D_UNICODE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -Iunittests\Support -IC:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\unittests\Support -Iinclude -IC:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\include -IC:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\utils\unittest\googletest\include -IC:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\utils\unittest\googlemock\include /DWIN32 /D_WINDOWS   /Zc:inline /Zc:__cplusplus /Oi /bigobj /permissive- /W4 -wd4141 -wd4146 -wd4244 -wd4267 -wd4291 -wd4351 -wd4456 -wd4457 -wd4458 -wd4459 -wd4503 -wd4624 -wd4722 -wd4100 -wd4127 -wd4512 -wd4505 -wd4610 -wd4510 -wd4702 -wd4245 -wd4706 -wd4310 -wd4701 -wd4703 -wd4389 -wd4611 -wd4805 -wd4204 -wd4577 -wd4091 -wd4592 -wd4319 -wd4709 -wd4324 -w14062 -we4238 /Gw /MD /O2 /Ob2  /EHs-c- /GR- -UNDEBUG -std:c++14 /showIncludes /Founittests\Support\CMakeFiles\SupportTests.dir\Base64Test.cpp.obj /Fdunittests\Support\CMakeFiles\SupportTests.dir\ /FS -c C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\unittests\Support\Base64Test.cpp
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\include\llvm/Support/Base64.h(81): error C3493: 'Inv' cannot be implicitly captured because no default capture mode has been specified
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\unittests\Support\Base64Test.cpp(32): note: see reference to function template instantiation 'llvm::Error llvm::decodeBase64<std::vector<char,std::allocator<char>>>(llvm::StringRef,OutputBytes &)' being compiled
        with
        [
            OutputBytes=std::vector<char,std::allocator<char>>
        ]
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\include\llvm/Support/Base64.h(100): error C2064: term does not evaluate to a function taking 1 arguments
C:\buildbot-root\llvm-clang-x86_64-sie-win\llvm-project\llvm\include\llvm/Support/Base64.h(100): error C2737: 'DecodedByte': const object must be initialized

llvm/include/llvm/Support/Base64.h

 //===--- Base64.h - Base64 Encoder/Decoder ----------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file provides generic base64 encoder/decoder.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_BASE64_H
 #define LLVM_SUPPORT_BASE64_H
 
+#include "llvm/Support/Error.h"
 #include <cstdint>
 #include <string>
 
 namespace llvm {
 
 template <class InputBytes> std::string encodeBase64(InputBytes const &Bytes) {
   static const char Table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                               "abcdefghijklmnopqrstuvwxyz"
if (i + 1 == Bytes.size()) {
     Buffer[j + 0] = Table[(x >> 18) & 63];
     Buffer[j + 1] = Table[(x >> 12) & 63];
     Buffer[j + 2] = Table[(x >> 6) & 63];
     Buffer[j + 3] = '=';
   }
   return Buffer;
 }
 
+template <class OutputBytes>
+llvm::Error decodeBase64(llvm::StringRef Input, OutputBytes &Output) {
+  // Invalid table value with short name to fit in the table init below. The
+  // invalid value is 64 since valid base64 values are 0 - 63.
+  constexpr char Inv = 64;
+  static char DecodeTable[] = {
+      Inv, Inv, Inv, Inv, Inv, Inv, Inv, Inv, // ........
+      Inv, Inv, Inv, Inv, Inv, Inv, Inv, Inv, // ........
+      Inv, Inv, Inv, Inv, Inv, Inv, Inv, Inv, // ........
+      Inv, Inv, Inv, Inv, Inv, Inv, Inv, Inv, // ........
+      Inv, Inv, Inv, Inv, Inv, Inv, Inv, Inv, // ........
+      Inv, Inv, Inv, 62,  Inv, Inv, Inv, 63,  // ...+.../
+      52,  53,  54,  55,  56,  57,  58,  59,  // 01234567
+      60,  61,  Inv, Inv, Inv, 0,   Inv, Inv, // 89...=..
+      Inv, 0,   1,   2,   3,   4,   5,   6,   // .ABCDEFG
+      7,   8,   9,   10,  11,  12,  13,  14,  // HIJKLMNO
+      15,  16,  17,  18,  19,  20,  21,  22,  // PQRSTUVW
+      23,  24,  25,  Inv, Inv, Inv, Inv, Inv, // XYZ.....
+      Inv, 26,  27,  28,  29,  30,  31,  32,  // .abcdefg
+      33,  34,  35,  36,  37,  38,  39,  40,  // hijklmno
+      41,  42,  43,  44,  45,  46,  47,  48,  // pqrstuvw
+      49,  50,  51                            // xyz.....
+  };
+  auto decodeBase64Byte = [](uint8_t Ch) -> char {
+    if (Ch >= sizeof(DecodeTable))
+      return Inv;
+    return DecodeTable[Ch];
+  };
+  Output.clear();
+  const size_t BytesLength = Input.size();
+  if (BytesLength == 0)
+    return Error::success();
+  // Make sure we have a valid input string length which must be a multiple
+  // of 4.
+  if ((BytesLength % 4) != 0)
+    return createStringError(std::errc::illegal_byte_sequence,
+                             "Base64 encoded strings must be a multiple of 4 "
+                             "bytes in length");
+  // Check for '=' characters in the string. There can be at most two '='
+  // characters at the end of the string and none in the middle.
+  uint32_t NumBytesToStrip = 0;
+  uint64_t EqualPos = Input.find('=');
+  if (EqualPos != StringRef::npos) {
+    NumBytesToStrip = Input.size() - EqualPos;
+    // If we have more than two bytes to strip, then we had an '=' character
+    // in the middle of the string. If we have two bytes to strip, also verify
+    // that the last character is also '='.
+    if (NumBytesToStrip > 2 ||
+        ((NumBytesToStrip == 2) && Input.back() != '=')) {
+      return createStringError(
+          std::errc::illegal_byte_sequence,
+          "Invalid Base64 character %#2.2x at index %" PRIu64, Input[EqualPos],
+          EqualPos);
+    }
+  }
+  char Hex64Bytes[4];
+  for (uint64_t Idx = 0; Idx < BytesLength; Idx += 4) {
+    for (uint64_t ByteIdx = 0; ByteIdx < 4; ++ByteIdx) {
+      const char Byte = Input[Idx + ByteIdx];
+      Hex64Bytes[ByteIdx] = decodeBase64Byte(Byte);
+      if (Hex64Bytes[ByteIdx] == Inv)
+        return createStringError(
+            std::errc::illegal_byte_sequence,
+            "Invalid Base64 character %#2.2x at index %" PRIu64, Byte,
+            Idx + ByteIdx);
+    }
+    // Now we have 6 bits of 3 bytes in value in each of the Hex64Bytes bytes.
+    // Extract the right bytes into the Output buffer.
+    Output.push_back((Hex64Bytes[0] << 2) + ((Hex64Bytes[1] >> 4) & 0x03));
+    Output.push_back((Hex64Bytes[1] << 4) + ((Hex64Bytes[2] >> 2) & 0x0f));
+    Output.push_back((Hex64Bytes[2] << 6) + (Hex64Bytes[3] & 0x3f));
+  }
+  // If we had valid trailing '=' characters strip the right number of bytes
+  // from the end of the output buffer.
+  while (NumBytesToStrip-- > 0)
+    Output.pop_back();
+  return Error::success();
+}
+
 } // end namespace llvm
 
 #endif

llvm/unittests/Support/Base64Test.cpp

 //===- llvm/unittest/Support/Base64Test.cpp - Base64 tests
 //--------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements unit tests for the Base64 functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/Base64.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Testing/Support/Error.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 /// Tests an arbitrary set of bytes passed as \p Input.
 void TestBase64(StringRef Input, StringRef Final) {
   auto Res = encodeBase64(Input);
   EXPECT_EQ(Res, Final);
 }
 
+void TestBase64Decode(StringRef Input, StringRef Expected,
+                      StringRef ExpectedErrorMessage = {}) {
+  std::vector<char> DecodedBytes;
+  if (ExpectedErrorMessage.empty()) {
+    ASSERT_THAT_ERROR(decodeBase64(Input, DecodedBytes), Succeeded());
+    EXPECT_EQ(llvm::ArrayRef<char>(DecodedBytes),
+              llvm::ArrayRef<char>(Expected.data(), Expected.size()));
+  } else {
+    ASSERT_THAT_ERROR(decodeBase64(Input, DecodedBytes),
+                      FailedWithMessage(ExpectedErrorMessage));
+  }
+}
+
+char NonPrintableVector[] = {0x00, 0x00, 0x00,       0x46,
+                             0x00, 0x08, (char)0xff, (char)0xee};
+
+char LargeVector[] = {0x54, 0x68, 0x65, 0x20, 0x71, 0x75, 0x69, 0x63, 0x6b,
+                      0x20, 0x62, 0x72, 0x6f, 0x77, 0x6e, 0x20, 0x66, 0x6f,
+                      0x78, 0x20, 0x6a, 0x75, 0x6d, 0x70, 0x73, 0x20, 0x6f,
+                      0x76, 0x65, 0x72, 0x20, 0x31, 0x33, 0x20, 0x6c, 0x61,
+                      0x7a, 0x79, 0x20, 0x64, 0x6f, 0x67, 0x73, 0x2e};
+
 } // namespace
 
 TEST(Base64Test, Base64) {
   // from: https://tools.ietf.org/html/rfc4648#section-10
   TestBase64("", "");
   TestBase64("f", "Zg==");
   TestBase64("fo", "Zm8=");
   TestBase64("foo", "Zm9v");
   TestBase64("foob", "Zm9vYg==");
   TestBase64("fooba", "Zm9vYmE=");
   TestBase64("foobar", "Zm9vYmFy");
 
   // With non-printable values.
-  char NonPrintableVector[] = {0x00, 0x00, 0x00,       0x46,
-                               0x00, 0x08, (char)0xff, (char)0xee};
   TestBase64({NonPrintableVector, sizeof(NonPrintableVector)}, "AAAARgAI/+4=");
 
   // Large test case
-  char LargeVector[] = {0x54, 0x68, 0x65, 0x20, 0x71, 0x75, 0x69, 0x63, 0x6b,
-                        0x20, 0x62, 0x72, 0x6f, 0x77, 0x6e, 0x20, 0x66, 0x6f,
-                        0x78, 0x20, 0x6a, 0x75, 0x6d, 0x70, 0x73, 0x20, 0x6f,
-                        0x76, 0x65, 0x72, 0x20, 0x31, 0x33, 0x20, 0x6c, 0x61,
-                        0x7a, 0x79, 0x20, 0x64, 0x6f, 0x67, 0x73, 0x2e};
   TestBase64({LargeVector, sizeof(LargeVector)},
              "VGhlIHF1aWNrIGJyb3duIGZveCBqdW1wcyBvdmVyIDEzIGxhenkgZG9ncy4=");
 }
+
+TEST(Base64Test, DecodeBase64) {
+  std::vector<llvm::StringRef> Outputs = {"",     "f",     "fo",    "foo",
+                                          "foob", "fooba", "foobar"};
+  Outputs.push_back(
+      llvm::StringRef(NonPrintableVector, sizeof(NonPrintableVector)));
+
+  Outputs.push_back(llvm::StringRef(LargeVector, sizeof(LargeVector)));
+  // Make sure we can encode and decode any byte.
+  std::vector<char> AllChars;
+  for (int Ch = INT8_MIN; Ch <= INT8_MAX; ++Ch)
+    AllChars.push_back(Ch);
+  Outputs.push_back(llvm::StringRef(AllChars.data(), AllChars.size()));
+
+  for (const auto &Output : Outputs) {
+    // We trust that encoding is working after running the Base64Test::Base64()
+    // test function above, so we can use it to encode the string and verify we
+    // can decode it correctly.
+    auto Input = encodeBase64(Output);
+    TestBase64Decode(Input, Output);
+  }
+  struct ErrorInfo {
+    llvm::StringRef Input;
+    llvm::StringRef ErrorMessage;
+  };
+  std::vector<ErrorInfo> ErrorInfos = {
+      {"f", "Base64 encoded strings must be a multiple of 4 bytes in length"},
+      {"=abc", "Invalid Base64 character 0x3d at index 0"},
+      {"a=bc", "Invalid Base64 character 0x3d at index 1"},
+      {"ab=c", "Invalid Base64 character 0x3d at index 2"},
+      {"fun!", "Invalid Base64 character 0x21 at index 3"},
+  };
+
+  for (const auto &EI : ErrorInfos)
+    TestBase64Decode(EI.Input, "", EI.ErrorMessage);
+}