Add support for computing SHA1 in LLVM

[mehdi_amini]

Summary

Provide a class to generate a SHA1 from a sequence of bytes, and
a convenience raw_ostream adaptor.
This is not used anywhere yet in LLVM, but I plan to base some
ThinLTO incremental scheme on this.

[filcab]

I have some minor comments.
I think having a patch using this before it lands would be nice. :-)

Thank you for working on this.

include/llvm/Support/SHA1.h

35

I think usually (confirmed in OpenSSL and CommonCrypto) these functions are called Init(), Update(), and Final().
I don't care about the case, but we should probably use the same words (just like MD5.h is doing).

39

We probably want to tell people to not reuse SHA1 objects, and might want to assert in debug mode.
After all, you could end up hashing weird things like the message from the first call to result() + some padding (and not any bytes you added later).

With this, you could even re-use the internal state for the result, but that might not be worth it :-)

lib/Support/SHA1.cpp

30

Nit: What does "override" mean in this context? Maybe "default" or "we assume little endian" or something else?

31

In the compilers we support, do we need to resort to this? I don't know about MSVC, but IIRC, gcc and clang always define {BIG,LITTLE}_ENDIAN, no?

We might not need so many tests.

46

Nit: Why do the round constants get names, but the seeds don't?

121

Nit:

while(len--) //?

144

Why here?

151

Nit: I'd prefer a positive test (ifdef, like the one in line 102)

[mehdi_amini]

Thanks for the review.
I don't mind waiting for the use case to be ready before landing this.

include/llvm/Support/SHA1.h

35

Didn't know, I'll update.

39

You mean there is no interest in supporting this:

TEST(raw_sha1_ostreamTest, Intermediate) {
  llvm::raw_sha1_ostream Sha1Stream;
  Sha1Stream << "Hello";
  auto Hash = toHex(Sha1Stream.sha1());

  ASSERT_EQ("F7FF9E8B7BB2E09B70935A5D785E0CC5D9D0ABF0", Hash);

  Sha1Stream << " World!";
  Hash = toHex(Sha1Stream.sha1());

  ASSERT_EQ("2EF7BDE608CE5404E97D5F042F95F89F1C232871", Hash);
}

right?
Is it because it is potentially allowing misuse?

lib/Support/SHA1.cpp

30

All this file is almost copy pasted (and moved to a LLVM style) : http://llvm.org/docs/doxygen/html/FuzzerSHA1_8cpp_source.html

[• rafael]

We already have md5. Is it not strong enough for what you want?

Cheers,
Rafael

[filcab]

include/llvm/Support/SHA1.h

39

As written we don't support that (you'll addUncounted one bit, and then the padding. Afterwards, adding to the stream won't do what it would need to do). I'd like that to be explicit in the documentation (and I'd like an assert or two to make it trigger in debug mode, if that's attempted).

[mehdi_amini]

include/llvm/Support/SHA1.h

39

I'm not sure what you mean, the InternalState is saved and restored in SHA1::result() so that we can resume as is. (this unittest is passing)

[deadalnix]

If perfs matter, I would do it that way:

https://github.com/bitcoin/bitcoin/blob/master/src/crypto/sha1.cpp

lib/Support/SHA1.cpp

72

I would do 2 loops

[mehdi_amini]

Take comments into account

[mehdi_amini]

Thanks for all the comments, I tried to address them.
As long as we're OK with the API, we'll still be able to improve the implementation later performance-wise if necessary.

include/llvm/Support/SHA1.h

39

support both behavior through different API calls now.

lib/Support/SHA1.cpp

72

not sure what you mean?

[ruiu]

include/llvm/Support/SHA1.h

34

Why don't you pass ArrayRef<uint8_t>?

41–45

It is not clear in this comment whether this function returns a hex string or raw bytes.

[mehdi_amini]

Act on Rui's comments

[mehdi_amini]

Thanks Rui for the comments.

include/llvm/Support/SHA1.h

34

Just mimic the API I was wrapping. That's a good point, updated!

41–45

Updated!

[mehdi_amini]

Anything else to change or can we move on and fix whatever comes up post-commit?
(this is blocking D18213 which is accepted)

[filcab]

No blocks on my side. Thank you.

P.S: It seems I had a comment to be submitted for a few weeks... Sorry for the lag. :-(

include/llvm/Support/SHA1.h

39

Sorry, didn't notice that line before pad() (and the one that restores it).

Thanks!

lib/Support/SHA1.cpp

167

Nit: 20 bytes (not "characters"), since it's just the raw bits.

[mehdi_amini]

Will proceed and address further comment post-commit.

[mehdi_amini]

r265107

[• deece]

Hi folks,

This change breaks on Linux X86 targetting X86, when running check-all or if LLVM_BUILD_TESTS is on:

15:53:55 [ 44%] Building CXX object unittests/Support/CMakeFiles/SupportTests.dir/raw_sha1_ostream_test.cpp.o
15:53:56 [ 44%] Linking CXX executable SupportTests
15:53:56 CMakeFiles/SupportTests.dir/formatted_raw_ostream_test.cpp.o: In function `(anonymous namespace)::formatted_raw_ostreamTest_Test_Tell_Test::TestBody()':
15:53:56 formatted_raw_ostream_test.cpp:(.text._ZN12_GLOBAL__N_140formatted_raw_ostreamTest_Test_Tell_Test8TestBodyEv+0x1ae): undefined reference to `llvm::formatted_raw_ostream::current_pos() const'
15:53:56 collect2: error: ld returned 1 exit status
15:53:56 make[3]: * [unittests/Support/SupportTests] Error 1
15:53:56 make[2]: * [unittests/Support/CMakeFiles/SupportTests.dir/all] Error 2
15:53:56 make[1]: * [CMakeFiles/check-all.dir/rule] Error 2
15:53:56 make: * [check-all] Error 2

[mehdi_amini]

Is there a bot that exhibit this issue?

Otherwise what is your config?

[• deece]

This came from a Jenkins job I'm setting up (I can reproduce it manually on a different machine too).

I've uploaded the full console log and build scripts here:
https://drive.google.com/folderview?id=0B1KcalYwX-jDOFVPSGxSV1JrWHM&usp=sharing

The main entrypoints into the scripts are build-setup.sh and test-setup.sh

[mehdi_amini]

The failure is strange, I suspect DLLVM_LINK_LLVM_DYLIB is playing tricks here...

Also the link failure is in formatted_raw_ostream_test.cpp, which this revision didn't touch. What makes you think this commit is responsible?

[• deece]

Sorry, I was barking up the wrong tree, this commit is unrelated.

include/llvm/Support/SHA1.h

+//==- SHA1.h - SHA1 implementation for LLVM                     --*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This code is taken from public domain
+// (http://oauth.googlecode.com/svn/code/c/liboauth/src/sha1.c)
+// and modified by wrapping it in a C++ interface for LLVM,
+// and removing unnecessary code.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_SHA1_H
+#define LLVM_SUPPORT_SHA1_H
+
+#include "llvm/ADT/StringRef.h"
+
+#include <cstdint>
+
+namespace llvm {
+
+/// A class that wrap the SHA1 algorithm.
+class SHA1 {
+public:
+  SHA1() { init(); }
+
+  /// Reinitialize the internal state
+  void init();
+
+  /// Digest more data.
+  void update(const char *data, size_t len);
+
+  /// Return a reference to the current SHA1 for the digested data since the
+  /// last call to init(). This call will add data to the internal state and as
+  /// such is not suited for getting an intermediate result (see result()).
+  StringRef final();
+
+  /// Return a reference to the current SHA1 for the digested data since the
+  /// last call to init(). This is suitable for getting the SHA1 at any time
+  /// without invalidating the internal state so that more calls can be made
+  /// into update.
+  StringRef result();
+
+private:
+  static constexpr int BLOCK_LENGTH = 64;
+  static constexpr int HASH_LENGTH = 20;
+
+  // Internal State
+  struct {
+    uint32_t Buffer[BLOCK_LENGTH / 4];
+    uint32_t State[HASH_LENGTH / 4];
+    uint32_t ByteCount;
+    uint8_t BufferOffset;
+  } InternalState;
+
+  // Internal copy of the hash, populated and accessed on calls to result()
+  uint32_t HashResult[HASH_LENGTH / 4];
+
+  // Helper
+  void writebyte(uint8_t data);
+  void hashBlock();
+  void addUncounted(uint8_t data);
+  void pad();
+};
+
+} // end llvm namespace
+
+#endif

include/llvm/Support/raw_sha1_ostream.h

+//==- raw_sha1_ostream.h - raw_ostream that compute SHA1        --*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the raw_sha1_ostream class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_RAW_SHA1_OSTREAM_H
+#define LLVM_SUPPORT_RAW_SHA1_OSTREAM_H
+
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/SHA1.h"
+
+namespace llvm {
+
+/// A raw_ostream that hash the content using the sha1 algorithm.
+class raw_sha1_ostream : public raw_ostream {
+  SHA1 State;
+
+  /// See raw_ostream::write_impl.
+  void write_impl(const char *Ptr, size_t Size) override {
+    State.update(Ptr, Size);
+  }
+
+public:
+  /// Return the current SHA1 hash for the content of the stream
+  StringRef sha1() {
+    flush();
+    return State.result();
+  }
+
+  /// Reset the internal state to start over from scratch.
+  void resetHash() { State.init(); }
+
+  uint64_t current_pos() const override { return 0; }
+};
+
+} // end llvm namespace
+
+#endif

lib/Support/CMakeLists.txt

add_llvm_library(LLVMSupport
   MemoryObject.cpp
   MD5.cpp
   Options.cpp
   PluginLoader.cpp
   PrettyStackTrace.cpp
   RandomNumberGenerator.cpp
   Regex.cpp
   ScaledNumber.cpp
+  SHA1.cpp
   SmallPtrSet.cpp
   SmallVector.cpp
   SourceMgr.cpp
   SpecialCaseList.cpp
   Statistic.cpp
   StreamingMemoryObject.cpp
   StringExtras.cpp
   StringMap.cpp

lib/Support/SHA1.cpp

+//======- SHA1.h - Private copy of the SHA1 implementation ---*- C++ -* ======//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This code is taken from public domain
+// (http://oauth.googlecode.com/svn/code/c/liboauth/src/sha1.c)
+// and modified by wrapping it in a C++ interface for LLVM,
+// and removing unnecessary code.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/SHA1.h"
+using namespace llvm;
+
+#include <stdint.h>
+#include <string.h>
+
+#ifdef __BIG_ENDIAN__
+#define SHA_BIG_ENDIAN
+#endif
+
+/* code */
+#define SHA1_K0 0x5a827999
+#define SHA1_K20 0x6ed9eba1
+#define SHA1_K40 0x8f1bbcdc
+#define SHA1_K60 0xca62c1d6
+
+#define SEED_0 0x67452301
+#define SEED_1 0xefcdab89
+#define SEED_2 0x98badcfe
+#define SEED_3 0x10325476
+#define SEED_4 0xc3d2e1f0
+
+void SHA1::init() {
+  InternalState.State[0] = SEED_0;
+  InternalState.State[1] = SEED_1;
+  InternalState.State[2] = SEED_2;
+  InternalState.State[3] = SEED_3;
+  InternalState.State[4] = SEED_4;
+  InternalState.ByteCount = 0;
+  InternalState.BufferOffset = 0;
+}
+
+static uint32_t rol32(uint32_t number, uint8_t bits) {
+  return ((number << bits) | (number >> (32 - bits)));
+}
+
+void SHA1::hashBlock() {
+  uint8_t i;
+  uint32_t a, b, c, d, e, t;
+
+  a = InternalState.State[0];
+  b = InternalState.State[1];
+  c = InternalState.State[2];
+  d = InternalState.State[3];
+  e = InternalState.State[4];
+  for (i = 0; i < 80; i++) {
+    if (i >= 16) {
+      t = InternalState.Buffer[(i + 13) & 15] ^
+          InternalState.Buffer[(i + 8) & 15] ^
+          InternalState.Buffer[(i + 2) & 15] ^ InternalState.Buffer[i & 15];
+      InternalState.Buffer[i & 15] = rol32(t, 1);
+    }
+    if (i < 20) {
+      t = (d ^ (b & (c ^ d))) + SHA1_K0;
+    } else if (i < 40) {
+      t = (b ^ c ^ d) + SHA1_K20;
+    } else if (i < 60) {
+      t = ((b & c) | (d & (b | c))) + SHA1_K40;
+    } else {
+      t = (b ^ c ^ d) + SHA1_K60;
+    }
+    t += rol32(a, 5) + e + InternalState.Buffer[i & 15];
+    e = d;
+    d = c;
+    c = rol32(b, 30);
+    b = a;
+    a = t;
+  }
+  InternalState.State[0] += a;
+  InternalState.State[1] += b;
+  InternalState.State[2] += c;
+  InternalState.State[3] += d;
+  InternalState.State[4] += e;
+}
+
+void SHA1::addUncounted(uint8_t data) {
+  uint8_t *const b = (uint8_t *)InternalState.Buffer;
+#ifdef SHA_BIG_ENDIAN
+  b[InternalState.BufferOffset] = data;
+#else
+  b[InternalState.BufferOffset ^ 3] = data;
+#endif
+  InternalState.BufferOffset++;
+  if (InternalState.BufferOffset == BLOCK_LENGTH) {
+    hashBlock();
+    InternalState.BufferOffset = 0;
+  }
+}
+
+void SHA1::writebyte(uint8_t data) {
+  ++InternalState.ByteCount;
+  addUncounted(data);
+}
+
+void SHA1::update(const char *data, size_t len) {
+  while(len--)
+    writebyte((uint8_t)*data++);
+}
+
+void SHA1::pad() {
+  // Implement SHA-1 padding (fips180-2 §5.1.1)
+
+  // Pad with 0x80 followed by 0x00 until the end of the block
+  addUncounted(0x80);
+  while (InternalState.BufferOffset != 56)
+    addUncounted(0x00);
+
+  // Append length in the last 8 bytes
+  addUncounted(0); // We're only using 32 bit lengths
+  addUncounted(0); // But SHA-1 supports 64 bit lengths
+  addUncounted(0); // So zero pad the top bits
+  addUncounted(InternalState.ByteCount >> 29); // Shifting to multiply by 8
+  addUncounted(InternalState.ByteCount >>
+               21); // as SHA-1 supports bitstreams as well as
+  addUncounted(InternalState.ByteCount >> 13); // byte.
+  addUncounted(InternalState.ByteCount >> 5);
+  addUncounted(InternalState.ByteCount << 3);
+}
+
+
+StringRef SHA1::final() {
+  // Pad to complete the last block
+  pad();
+
+#ifdef SHA_BIG_ENDIAN
+  // Just copy the current state
+  for (int i = 0; i < 5; i++) {
+    HashResult[i] = InternalState.State[i];
+  }
+#else
+  // Swap byte order back
+  for (int i = 0; i < 5; i++) {
+    HashResult[i] = (((InternalState.State[i]) << 24) & 0xff000000) |
+    (((InternalState.State[i]) << 8) & 0x00ff0000) |
+    (((InternalState.State[i]) >> 8) & 0x0000ff00) |
+    (((InternalState.State[i]) >> 24) & 0x000000ff);
+  }
+#endif
+
+  // Return pointer to hash (20 characters)
+  return StringRef((char *)HashResult, HASH_LENGTH);
+}
+
+StringRef SHA1::result() {
+  auto StateToRestore = InternalState;
+
+  auto Hash = final();
+
+  // Restore the state
+  InternalState = StateToRestore;
+
+  // Return pointer to hash (20 characters)
+  return Hash;
+}

unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   TypeNameTest.cpp
   TrailingObjectsTest.cpp
   UnicodeTest.cpp
   YAMLIOTest.cpp
   YAMLParserTest.cpp
   formatted_raw_ostream_test.cpp
   raw_ostream_test.cpp
   raw_pwrite_stream_test.cpp
+  raw_sha1_ostream_test.cpp
   )
 
 # ManagedStatic.cpp uses <pthread>.
 target_link_libraries(SupportTests ${PTHREAD_LIB})

unittests/Support/raw_sha1_ostream_test.cpp

+//===- llvm/unittest/Support/raw_ostream_test.cpp - raw_ostream tests -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/raw_sha1_ostream.h"
+
+#include <string>
+
+using namespace llvm;
+
+static std::string toHex(StringRef Input) {
+  static const char *const LUT = "0123456789ABCDEF";
+  size_t Length = Input.size();
+
+  std::string Output;
+  Output.reserve(2 * Length);
+  for (size_t i = 0; i < Length; ++i) {
+    const unsigned char c = Input[i];
+    Output.push_back(LUT[c >> 4]);
+    Output.push_back(LUT[c & 15]);
+  }
+  return Output;
+}
+
+TEST(raw_sha1_ostreamTest, Basic) {
+  llvm::raw_sha1_ostream Sha1Stream;
+  Sha1Stream << "Hello World!";
+  auto Hash = toHex(Sha1Stream.sha1());
+
+  ASSERT_EQ("2EF7BDE608CE5404E97D5F042F95F89F1C232871", Hash);
+}
+
+// Check that getting the intermediate hash in the middle of the stream does
+// not invalidate the final result.
+TEST(raw_sha1_ostreamTest, Intermediate) {
+  llvm::raw_sha1_ostream Sha1Stream;
+  Sha1Stream << "Hello";
+  auto Hash = toHex(Sha1Stream.sha1());
+
+  ASSERT_EQ("F7FF9E8B7BB2E09B70935A5D785E0CC5D9D0ABF0", Hash);
+  Sha1Stream << " World!";
+  Hash = toHex(Sha1Stream.sha1());
+
+  // Compute the non-split hash separately as a reference.
+  llvm::raw_sha1_ostream NonSplitSha1Stream;
+  NonSplitSha1Stream << "Hello World!";
+  auto NonSplitHash = toHex(NonSplitSha1Stream.sha1());
+
+  ASSERT_EQ(NonSplitHash, Hash);
+}
+
+TEST(raw_sha1_ostreamTest, Reset) {
+  llvm::raw_sha1_ostream Sha1Stream;
+  Sha1Stream << "Hello";
+  auto Hash = toHex(Sha1Stream.sha1());
+
+  ASSERT_EQ("F7FF9E8B7BB2E09B70935A5D785E0CC5D9D0ABF0", Hash);
+
+  Sha1Stream.resetHash();
+  Sha1Stream << " World!";
+  Hash = toHex(Sha1Stream.sha1());
+
+  ASSERT_EQ("7447F2A5A42185C8CF91E632789C431830B59067", Hash);
+}