Syndicate, test and fix base64 implementation

[serge-sans-paille]

Summary

As an answer to https://github.com/llvm/llvm-project/issues/149, and to a comment in the code, syndicate base64 implementation between compiler-rt and clang-tools-extra

[lebedev.ri]

compiler-rt/lib/fuzzer/FuzzerUtil.cpp

14–16

I don't believe we can do this. libfuzzer is acting as a sub-sub-project,
and i strongly believe it wants to shy away from using anything
other than it's own headers and standard c/c++ headers.

[serge-sans-paille]

Restore duplication, fix the bug in two separate locations.

[serge-sans-paille]

Fix typo

[serge-sans-paille]

As a side note, pre-reserving the buffer size gives interesting speedup, see http://quick-bench.com/Lp6OwO2etW1YEmJayVWn3U8JDiY

[serge-sans-paille]

Other copy/paste typo.

[serge-sans-paille]

Up?

[hokein]

thanks for doing this! didn't look into details yet. Could you explain what was the bug in the previous code? since this patch contains some refactoring changes, it is not quite straightforward to spot it.

llvm/unittests/Support/Base64Test.cpp

1

nit: Base64Test.cpp.

30

nit: i would just inline the TestBase64.

[serge-sans-paille]

In D75057#1895550, @hokein wrote:

thanks for doing this! didn't look into details yet. Could you explain what was the bug in the previous code?

Yeah, the code was using + operator instead of | to combine the results, which is a problem when shifting signed values. (0xFF << 16) is implicitly converted to a (signed) int, and thus results in 0xffff0000, which is negative. Combining negative numbers with a + in that context is not what we want to do.

[serge-sans-paille]

Add a test case that exhibits the overflow in previous implementation + minor nits from @hokein

[serge-sans-paille]

llvm/unittests/Support/Base64Test.cpp

30

I wouldn't :-) I find it easier to read like that, if that's okay with you.

[hokein]

In D75057#1896114, @serge-sans-paille wrote:

In D75057#1895550, @hokein wrote:

thanks for doing this! didn't look into details yet. Could you explain what was the bug in the previous code?

Yeah, the code was using + operator instead of | to combine the results, which is a problem when shifting signed values. (0xFF << 16) is implicitly converted to a (signed) int, and thus results in 0xffff0000, which is negative. Combining negative numbers with a + in that context is not what we want to do.

fair enough, thanks for the clarification.

llvm/unittests/Support/Base64Test.cpp

30

personal I don't think it is easier comparing with inline them, EXPECT_EQ(encodeBase64("f"), "abc"); seems clearer to me, up to you.

43

nit: explicit StringRef is not needed.

[hctim]

Looks like this change broke the UBSan build bots:

FAIL: LLVM-Unit :: Support/./SupportTests/Base64Test.Base64 (3484 of 36324)
******************** TEST 'LLVM-Unit :: Support/./SupportTests/Base64Test.Base64' FAILED ********************
Note: Google Test filter = Base64Test.Base64
[==========] Running 1 test from 1 test case.
[----------] Global test environment set-up.
[----------] 1 test from Base64Test
[ RUN      ] Base64Test.Base64
/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/include/llvm/Support/Base64.h:42:28: runtime error: left shift of negative value -1
    #0 0x4993b6 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > llvm::encodeBase64<llvm::StringRef>(llvm::StringRef const&) /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/include/llvm/Support/Base64.h:42:28
    #1 0x498b78 in (anonymous namespace)::TestBase64(llvm::StringRef, llvm::StringRef) /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Support/Base64Test.cpp:23:14
    #2 0x498aeb in Base64Test_Base64_Test::TestBody() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/unittests/Support/Base64Test.cpp:42:3
    #3 0x8d85f9 in testing::Test::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2474:5
    #4 0x8d9581 in testing::TestInfo::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2656:11
    #5 0x8d9f32 in testing::TestCase::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:2774:28
    #6 0x8e1602 in testing::internal::UnitTestImpl::RunAllTests() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:4649:43
    #7 0x8e1085 in testing::UnitTest::Run() /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/src/gtest.cc:4257:10
    #8 0x8d0933 in RUN_ALL_TESTS /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/googletest/include/gtest/gtest.h:2233:46
    #9 0x8d0933 in main /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/utils/unittest/UnitTestMain/TestMain.cpp:50:10
    #10 0x7f806f76e2e0 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x202e0)
    #11 0x445d39 in _start (/b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm_build_ubsan/unittests/Support/SupportTests+0x445d39)

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /b/sanitizer-x86_64-linux-bootstrap-ubsan/build/llvm-project/llvm/include/llvm/Support/Base64.h:42:28 in 

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 

Testing Time: 68.95s
********************
Failing Tests (1):
    LLVM-Unit :: Support/./SupportTests/Base64Test.Base64

• http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-ubsan/builds/18078/steps/check-llvm%20ubsan/logs/stdio

I'll send out a revert shortly, to reproduce the sanitizer bots you can use the instructions here, or, given that this is UBSan, it should be sufficient to just add -DLLVM_USE_SANITIZER=Undefined and run check-llvm :).

clang-tools-extra/clangd/SemanticHighlighting.cpp

 #include "clang/AST/Type.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/Base64.h"
 #include "llvm/Support/Casting.h"
 #include <algorithm>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 /// Some names are not written in the source code and cannot be highlighted,
bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc Q) {
     }
     return RecursiveASTVisitor::TraverseNestedNameSpecifierLoc(Q);
   }
 
 private:
   HighlightingsBuilder &H;
 };
 
-// Encode binary data into base64.
-// This was copied from compiler-rt/lib/fuzzer/FuzzerUtil.cpp.
-// FIXME: Factor this out into llvm/Support?
-std::string encodeBase64(const llvm::SmallVectorImpl<char> &Bytes) {
-  static const char Table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
-                              "abcdefghijklmnopqrstuvwxyz"
-                              "0123456789+/";
-  std::string Res;
-  size_t I;
-  for (I = 0; I + 2 < Bytes.size(); I += 3) {
-    uint32_t X = (Bytes[I] << 16) + (Bytes[I + 1] << 8) + Bytes[I + 2];
-    Res += Table[(X >> 18) & 63];
-    Res += Table[(X >> 12) & 63];
-    Res += Table[(X >> 6) & 63];
-    Res += Table[X & 63];
-  }
-  if (I + 1 == Bytes.size()) {
-    uint32_t X = (Bytes[I] << 16);
-    Res += Table[(X >> 18) & 63];
-    Res += Table[(X >> 12) & 63];
-    Res += "==";
-  } else if (I + 2 == Bytes.size()) {
-    uint32_t X = (Bytes[I] << 16) + (Bytes[I + 1] << 8);
-    Res += Table[(X >> 18) & 63];
-    Res += Table[(X >> 12) & 63];
-    Res += Table[(X >> 6) & 63];
-    Res += "=";
-  }
-  return Res;
-}
-
 void write32be(uint32_t I, llvm::raw_ostream &OS) {
   std::array<char, 4> Buf;
   llvm::support::endian::write32be(Buf.data(), I);
   OS.write(Buf.data(), Buf.size());
 }
 
 void write16be(uint16_t I, llvm::raw_ostream &OS) {
   std::array<char, 2> Buf;

compiler-rt/lib/fuzzer/FuzzerUtil.cpp

 //===- FuzzerUtil.cpp - Misc utils ----------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 // Misc utils.
 //===----------------------------------------------------------------------===//
 
 #include "FuzzerUtil.h"
 #include "FuzzerIO.h"
 #include "FuzzerInternal.h"
 #include <cassert>
 #include <chrono>
 #include <cstring>
 #include <errno.h>
 #include <mutex>
 #include <signal.h>
 #include <sstream>
 #include <stdio.h>
 #include <sys/types.h>
 #include <thread>
 
if (ParseOneDictionaryEntry(S, &U)) {
       Printf("ParseDictionaryFile: error in line %d\n\t\t%s\n", LineNo,
              S.c_str());
       return false;
     }
   }
   return true;
 }
 
+// Code duplicated (and tested) in llvm/include/llvm/Support/Base64.h
 std::string Base64(const Unit &U) {
   static const char Table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                               "abcdefghijklmnopqrstuvwxyz"
                               "0123456789+/";
-  std::string Res;
-  size_t i;
-  for (i = 0; i + 2 < U.size(); i += 3) {
-    uint32_t x = (U[i] << 16) + (U[i + 1] << 8) + U[i + 2];
-    Res += Table[(x >> 18) & 63];
-    Res += Table[(x >> 12) & 63];
-    Res += Table[(x >> 6) & 63];
-    Res += Table[x & 63];
+  std::string Buffer;
+  Buffer.resize(((U.size() + 2) / 3) * 4);
+
+  size_t i = 0, j = 0;
+  for (size_t n = U.size() / 3 * 3; i < n; i += 3, j += 4) {
+    uint32_t x = (U[i] << 16) | (U[i + 1] << 8) | U[i + 2];
+    Buffer[j + 0] = Table[(x >> 18) & 63];
+    Buffer[j + 1] = Table[(x >> 12) & 63];
+    Buffer[j + 2] = Table[(x >> 6) & 63];
+    Buffer[j + 3] = Table[x & 63];
   }
   if (i + 1 == U.size()) {
     uint32_t x = (U[i] << 16);
-    Res += Table[(x >> 18) & 63];
-    Res += Table[(x >> 12) & 63];
-    Res += "==";
+    Buffer[j + 0] = Table[(x >> 18) & 63];
+    Buffer[j + 1] = Table[(x >> 12) & 63];
+    Buffer[j + 2] = '=';
+    Buffer[j + 3] = '=';
   } else if (i + 2 == U.size()) {
-    uint32_t x = (U[i] << 16) + (U[i + 1] << 8);
-    Res += Table[(x >> 18) & 63];
-    Res += Table[(x >> 12) & 63];
-    Res += Table[(x >> 6) & 63];
-    Res += "=";
+    uint32_t x = (U[i] << 16) | (U[i + 1] << 8);
+    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 Res;
+  return Buffer;
 }
 
 static std::mutex SymbolizeMutex;
 
 std::string DescribePC(const char *SymbolizedFMT, uintptr_t PC) {
   std::unique_lock<std::mutex> l(SymbolizeMutex, std::try_to_lock);
   if (!EF->__sanitizer_symbolize_pc || !l.owns_lock())
     return "<can not symbolize>";

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 <string>
+
+namespace llvm {
+
+template <class InputBytes> std::string encodeBase64(InputBytes const &Bytes) {
+  static const char Table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+                              "abcdefghijklmnopqrstuvwxyz"
+                              "0123456789+/";
+  std::string Buffer;
+  Buffer.resize(((Bytes.size() + 2) / 3) * 4);
+
+  size_t i = 0, j = 0;
+  for (size_t n = Bytes.size() / 3 * 3; i < n; i += 3, j += 4) {
+    uint32_t x = (Bytes[i] << 16) | (Bytes[i + 1] << 8) | Bytes[i + 2];
+    Buffer[j + 0] = Table[(x >> 18) & 63];
+    Buffer[j + 1] = Table[(x >> 12) & 63];
+    Buffer[j + 2] = Table[(x >> 6) & 63];
+    Buffer[j + 3] = Table[x & 63];
+  }
+  if (i + 1 == Bytes.size()) {
+    uint32_t x = (Bytes[i] << 16);
+    Buffer[j + 0] = Table[(x >> 18) & 63];
+    Buffer[j + 1] = Table[(x >> 12) & 63];
+    Buffer[j + 2] = '=';
+    Buffer[j + 3] = '=';
+  } else if (i + 2 == Bytes.size()) {
+    uint32_t x = (Bytes[i] << 16) | (Bytes[i + 1] << 8);
+    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;
+}
+
+} // end namespace llvm
+
+#endif

llvm/unittests/Support/Base64Test.cpp

+//===- llvm/unittest/Support/Base64.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 "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);
+}
+
+} // 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");
+
+  // 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,
+             "VGhlIHF1aWNrIGJyb3duIGZveCBqdW1wcyBvdmVyIDEzIGxhenkgZG9ncy4=");
+}

llvm/unittests/Support/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Support
   )
 
 add_llvm_unittest(SupportTests
   AlignmentTest.cpp
   AlignOfTest.cpp
   AllocatorTest.cpp
   AnnotationsTest.cpp
   ARMAttributeParser.cpp
   ArrayRecyclerTest.cpp
+  Base64Test.cpp
   BinaryStreamTest.cpp
   BlockFrequencyTest.cpp
   BranchProbabilityTest.cpp
   CachePruningTest.cpp
   CrashRecoveryTest.cpp
   Casting.cpp
   CheckedArithmeticTest.cpp
   Chrono.cpp