llvm/lib/Support/SHA1.cpp

   1 //====- SHA1.cpp - Private copy of the SHA1 implementation ---*- C++ -* ======//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This code is taken from public domain
  10 // (http://oauth.googlecode.com/svn/code/c/liboauth/src/sha1.c and
  11 // http://cvsweb.netbsd.org/bsdweb.cgi/src/common/lib/libc/hash/sha1/sha1.c?rev=1.6)
  12 // and modified by wrapping it in a C++ interface for LLVM,
  13 // and removing unnecessary code.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Support/SHA1.h"
  18 #include "llvm/ADT/ArrayRef.h"
  19 #include "llvm/ADT/StringRef.h"
  20 #include "llvm/Support/Endian.h"
  21 #include "llvm/Support/SwapByteOrder.h"
  22 #include <string.h>
  23
  24 using namespace llvm;
  25
  26 static inline uint32_t rol(uint32_t Number, int Bits) {
  27   return (Number << Bits) | (Number >> (32 - Bits));
  28 }
  29
  30 static inline uint32_t blk0(uint32_t *Buf, int I) { return Buf[I]; }
  31
  32 static inline uint32_t blk(uint32_t *Buf, int I) {
  33   Buf[I & 15] = rol(Buf[(I + 13) & 15] ^ Buf[(I + 8) & 15] ^ Buf[(I + 2) & 15] ^
  34                         Buf[I & 15],
  35                     1);
  36   return Buf[I & 15];
  37 }
  38
  39 static inline void r0(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D,
  40                       uint32_t &E, int I, uint32_t *Buf) {
  41   E += ((B & (C ^ D)) ^ D) + blk0(Buf, I) + 0x5A827999 + rol(A, 5);
  42   B = rol(B, 30);
  43 }
  44
  45 static inline void r1(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D,
  46                       uint32_t &E, int I, uint32_t *Buf) {
  47   E += ((B & (C ^ D)) ^ D) + blk(Buf, I) + 0x5A827999 + rol(A, 5);
  48   B = rol(B, 30);
  49 }
  50
  51 static inline void r2(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D,
  52                       uint32_t &E, int I, uint32_t *Buf) {
  53   E += (B ^ C ^ D) + blk(Buf, I) + 0x6ED9EBA1 + rol(A, 5);
  54   B = rol(B, 30);
  55 }
  56
  57 static inline void r3(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D,
  58                       uint32_t &E, int I, uint32_t *Buf) {
  59   E += (((B | C) & D) | (B & C)) + blk(Buf, I) + 0x8F1BBCDC + rol(A, 5);
  60   B = rol(B, 30);
  61 }
  62
  63 static inline void r4(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D,
  64                       uint32_t &E, int I, uint32_t *Buf) {
  65   E += (B ^ C ^ D) + blk(Buf, I) + 0xCA62C1D6 + rol(A, 5);
  66   B = rol(B, 30);
  67 }
  68
  69 /* code */
  70 #define SHA1_K0 0x5a827999
  71 #define SHA1_K20 0x6ed9eba1
  72 #define SHA1_K40 0x8f1bbcdc
  73 #define SHA1_K60 0xca62c1d6
  74
  75 #define SEED_0 0x67452301
  76 #define SEED_1 0xefcdab89
  77 #define SEED_2 0x98badcfe
  78 #define SEED_3 0x10325476
  79 #define SEED_4 0xc3d2e1f0
  80
  81 void SHA1::init() {
  82   InternalState.State[0] = SEED_0;
  83   InternalState.State[1] = SEED_1;
  84   InternalState.State[2] = SEED_2;
  85   InternalState.State[3] = SEED_3;
  86   InternalState.State[4] = SEED_4;
  87   InternalState.ByteCount = 0;
  88   InternalState.BufferOffset = 0;
  89 }
  90
  91 void SHA1::hashBlock() {
  92   uint32_t A = InternalState.State[0];
  93   uint32_t B = InternalState.State[1];
  94   uint32_t C = InternalState.State[2];
  95   uint32_t D = InternalState.State[3];
  96   uint32_t E = InternalState.State[4];
  97
  98   // 4 rounds of 20 operations each. Loop unrolled.
  99   r0(A, B, C, D, E, 0, InternalState.Buffer.L);
 100   r0(E, A, B, C, D, 1, InternalState.Buffer.L);
 101   r0(D, E, A, B, C, 2, InternalState.Buffer.L);
 102   r0(C, D, E, A, B, 3, InternalState.Buffer.L);
 103   r0(B, C, D, E, A, 4, InternalState.Buffer.L);
 104   r0(A, B, C, D, E, 5, InternalState.Buffer.L);
 105   r0(E, A, B, C, D, 6, InternalState.Buffer.L);
 106   r0(D, E, A, B, C, 7, InternalState.Buffer.L);
 107   r0(C, D, E, A, B, 8, InternalState.Buffer.L);
 108   r0(B, C, D, E, A, 9, InternalState.Buffer.L);
 109   r0(A, B, C, D, E, 10, InternalState.Buffer.L);
 110   r0(E, A, B, C, D, 11, InternalState.Buffer.L);
 111   r0(D, E, A, B, C, 12, InternalState.Buffer.L);
 112   r0(C, D, E, A, B, 13, InternalState.Buffer.L);
 113   r0(B, C, D, E, A, 14, InternalState.Buffer.L);
 114   r0(A, B, C, D, E, 15, InternalState.Buffer.L);
 115   r1(E, A, B, C, D, 16, InternalState.Buffer.L);
 116   r1(D, E, A, B, C, 17, InternalState.Buffer.L);
 117   r1(C, D, E, A, B, 18, InternalState.Buffer.L);
 118   r1(B, C, D, E, A, 19, InternalState.Buffer.L);
 119
 120   r2(A, B, C, D, E, 20, InternalState.Buffer.L);
 121   r2(E, A, B, C, D, 21, InternalState.Buffer.L);
 122   r2(D, E, A, B, C, 22, InternalState.Buffer.L);
 123   r2(C, D, E, A, B, 23, InternalState.Buffer.L);
 124   r2(B, C, D, E, A, 24, InternalState.Buffer.L);
 125   r2(A, B, C, D, E, 25, InternalState.Buffer.L);
 126   r2(E, A, B, C, D, 26, InternalState.Buffer.L);
 127   r2(D, E, A, B, C, 27, InternalState.Buffer.L);
 128   r2(C, D, E, A, B, 28, InternalState.Buffer.L);
 129   r2(B, C, D, E, A, 29, InternalState.Buffer.L);
 130   r2(A, B, C, D, E, 30, InternalState.Buffer.L);
 131   r2(E, A, B, C, D, 31, InternalState.Buffer.L);
 132   r2(D, E, A, B, C, 32, InternalState.Buffer.L);
 133   r2(C, D, E, A, B, 33, InternalState.Buffer.L);
 134   r2(B, C, D, E, A, 34, InternalState.Buffer.L);
 135   r2(A, B, C, D, E, 35, InternalState.Buffer.L);
 136   r2(E, A, B, C, D, 36, InternalState.Buffer.L);
 137   r2(D, E, A, B, C, 37, InternalState.Buffer.L);
 138   r2(C, D, E, A, B, 38, InternalState.Buffer.L);
 139   r2(B, C, D, E, A, 39, InternalState.Buffer.L);
 140
 141   r3(A, B, C, D, E, 40, InternalState.Buffer.L);
 142   r3(E, A, B, C, D, 41, InternalState.Buffer.L);
 143   r3(D, E, A, B, C, 42, InternalState.Buffer.L);
 144   r3(C, D, E, A, B, 43, InternalState.Buffer.L);
 145   r3(B, C, D, E, A, 44, InternalState.Buffer.L);
 146   r3(A, B, C, D, E, 45, InternalState.Buffer.L);
 147   r3(E, A, B, C, D, 46, InternalState.Buffer.L);
 148   r3(D, E, A, B, C, 47, InternalState.Buffer.L);
 149   r3(C, D, E, A, B, 48, InternalState.Buffer.L);
 150   r3(B, C, D, E, A, 49, InternalState.Buffer.L);
 151   r3(A, B, C, D, E, 50, InternalState.Buffer.L);
 152   r3(E, A, B, C, D, 51, InternalState.Buffer.L);
 153   r3(D, E, A, B, C, 52, InternalState.Buffer.L);
 154   r3(C, D, E, A, B, 53, InternalState.Buffer.L);
 155   r3(B, C, D, E, A, 54, InternalState.Buffer.L);
 156   r3(A, B, C, D, E, 55, InternalState.Buffer.L);
 157   r3(E, A, B, C, D, 56, InternalState.Buffer.L);
 158   r3(D, E, A, B, C, 57, InternalState.Buffer.L);
 159   r3(C, D, E, A, B, 58, InternalState.Buffer.L);
 160   r3(B, C, D, E, A, 59, InternalState.Buffer.L);
 161
 162   r4(A, B, C, D, E, 60, InternalState.Buffer.L);
 163   r4(E, A, B, C, D, 61, InternalState.Buffer.L);
 164   r4(D, E, A, B, C, 62, InternalState.Buffer.L);
 165   r4(C, D, E, A, B, 63, InternalState.Buffer.L);
 166   r4(B, C, D, E, A, 64, InternalState.Buffer.L);
 167   r4(A, B, C, D, E, 65, InternalState.Buffer.L);
 168   r4(E, A, B, C, D, 66, InternalState.Buffer.L);
 169   r4(D, E, A, B, C, 67, InternalState.Buffer.L);
 170   r4(C, D, E, A, B, 68, InternalState.Buffer.L);
 171   r4(B, C, D, E, A, 69, InternalState.Buffer.L);
 172   r4(A, B, C, D, E, 70, InternalState.Buffer.L);
 173   r4(E, A, B, C, D, 71, InternalState.Buffer.L);
 174   r4(D, E, A, B, C, 72, InternalState.Buffer.L);
 175   r4(C, D, E, A, B, 73, InternalState.Buffer.L);
 176   r4(B, C, D, E, A, 74, InternalState.Buffer.L);
 177   r4(A, B, C, D, E, 75, InternalState.Buffer.L);
 178   r4(E, A, B, C, D, 76, InternalState.Buffer.L);
 179   r4(D, E, A, B, C, 77, InternalState.Buffer.L);
 180   r4(C, D, E, A, B, 78, InternalState.Buffer.L);
 181   r4(B, C, D, E, A, 79, InternalState.Buffer.L);
 182
 183   InternalState.State[0] += A;
 184   InternalState.State[1] += B;
 185   InternalState.State[2] += C;
 186   InternalState.State[3] += D;
 187   InternalState.State[4] += E;
 188 }
 189
 190 void SHA1::addUncounted(uint8_t Data) {
 191   if constexpr (sys::IsBigEndianHost)
 192     InternalState.Buffer.C[InternalState.BufferOffset] = Data;
 193   else
 194     InternalState.Buffer.C[InternalState.BufferOffset ^ 3] = Data;
 195
 196   InternalState.BufferOffset++;
 197   if (InternalState.BufferOffset == BLOCK_LENGTH) {
 198     hashBlock();
 199     InternalState.BufferOffset = 0;
 200   }
 201 }
 202
 203 void SHA1::writebyte(uint8_t Data) {
 204   ++InternalState.ByteCount;
 205   addUncounted(Data);
 206 }
 207
 208 void SHA1::update(ArrayRef<uint8_t> Data) {
 209   InternalState.ByteCount += Data.size();
 210
 211   // Finish the current block.
 212   if (InternalState.BufferOffset > 0) {
 213     const size_t Remainder = std::min<size_t>(
 214         Data.size(), BLOCK_LENGTH - InternalState.BufferOffset);
 215     for (size_t I = 0; I < Remainder; ++I)
 216       addUncounted(Data[I]);
 217     Data = Data.drop_front(Remainder);
 218   }
 219
 220   // Fast buffer filling for large inputs.
 221   while (Data.size() >= BLOCK_LENGTH) {
 222     assert(InternalState.BufferOffset == 0);
 223     static_assert(BLOCK_LENGTH % 4 == 0);
 224     constexpr size_t BLOCK_LENGTH_32 = BLOCK_LENGTH / 4;
 225     for (size_t I = 0; I < BLOCK_LENGTH_32; ++I)
 226       InternalState.Buffer.L[I] = support::endian::read32be(&Data[I * 4]);
 227     hashBlock();
 228     Data = Data.drop_front(BLOCK_LENGTH);
 229   }
 230
 231   // Finish the remainder.
 232   for (uint8_t C : Data)
 233     addUncounted(C);
 234 }
 235
 236 void SHA1::update(StringRef Str) {
 237   update(
 238       ArrayRef<uint8_t>((uint8_t *)const_cast<char *>(Str.data()), Str.size()));
 239 }
 240
 241 void SHA1::pad() {
 242   // Implement SHA-1 padding (fips180-2 5.1.1)
 243
 244   // Pad with 0x80 followed by 0x00 until the end of the block
 245   addUncounted(0x80);
 246   while (InternalState.BufferOffset != 56)
 247     addUncounted(0x00);
 248
 249   // Append length in the last 8 bytes
 250   addUncounted(0); // We're only using 32 bit lengths
 251   addUncounted(0); // But SHA-1 supports 64 bit lengths
 252   addUncounted(0); // So zero pad the top bits
 253   addUncounted(InternalState.ByteCount >> 29); // Shifting to multiply by 8
 254   addUncounted(InternalState.ByteCount >>
 255                21); // as SHA-1 supports bitstreams as well as
 256   addUncounted(InternalState.ByteCount >> 13); // byte.
 257   addUncounted(InternalState.ByteCount >> 5);
 258   addUncounted(InternalState.ByteCount << 3);
 259 }
 260
 261 void SHA1::final(std::array<uint32_t, HASH_LENGTH / 4> &HashResult) {
 262   // Pad to complete the last block
 263   pad();
 264
 265   if constexpr (sys::IsBigEndianHost) {
 266     // Just copy the current state
 267     for (int i = 0; i < 5; i++) {
 268       HashResult[i] = InternalState.State[i];
 269     }
 270   } else {
 271     // Swap byte order back
 272     for (int i = 0; i < 5; i++) {
 273       HashResult[i] = llvm::byteswap(InternalState.State[i]);
 274     }
 275   }
 276 }
 277
 278 std::array<uint8_t, 20> SHA1::final() {
 279   union {
 280     std::array<uint32_t, HASH_LENGTH / 4> HashResult;
 281     std::array<uint8_t, HASH_LENGTH> ReturnResult;
 282   };
 283   static_assert(sizeof(HashResult) == sizeof(ReturnResult));
 284   final(HashResult);
 285   return ReturnResult;
 286 }
 287
 288 std::array<uint8_t, 20> SHA1::result() {
 289   auto StateToRestore = InternalState;
 290
 291   auto Hash = final();
 292
 293   // Restore the state
 294   InternalState = StateToRestore;
 295
 296   // Return pointer to hash (20 characters)
 297   return Hash;
 298 }
 299
 300 std::array<uint8_t, 20> SHA1::hash(ArrayRef<uint8_t> Data) {
 301   SHA1 Hash;
 302   Hash.update(Data);
 303   return Hash.final();
 304 }