openMSX
utils/sha1.cc
Go to the documentation of this file.
1 /*
2 Based on:
3 100% free public domain implementation of the SHA-1 algorithm
4 by Dominik Reichl <Dominik.Reichl@tiscali.de>
5 
6 Refactored in C++ style as part of openMSX
7 by Maarten ter Huurne and Wouter Vermaelen.
8 
9 === Test Vectors (from FIPS PUB 180-1) ===
10 
11 "abc"
12 A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D
13 
14 "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
15 84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
16 
17 A million repetitions of "a"
18 34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F
19 */
20 
21 #include "sha1.hh"
22 #include "MSXException.hh"
23 #include "endian.hh"
24 #include "enumerate.hh"
25 #include "likely.hh"
26 #include "ranges.hh"
27 #include "xrange.hh"
28 #include <cassert>
29 #include <cstring>
30 #ifdef __SSE2__
31 #include <emmintrin.h> // SSE2
32 #endif
33 
34 using std::string;
35 
36 namespace openmsx {
37 
38 // Rotate x bits to the left
39 [[nodiscard]] static constexpr uint32_t rol32(uint32_t value, int bits)
40 {
41  return (value << bits) | (value >> (32 - bits));
42 }
43 
45 private:
46  uint32_t data[16];
47 
48  [[nodiscard]] uint32_t next0(int i)
49  {
50  data[i] = Endian::readB32(&data[i]);
51  return data[i];
52  }
53  [[nodiscard]] uint32_t next(int i)
54  {
55  return data[i & 15] = rol32(
56  data[(i + 13) & 15] ^ data[(i + 8) & 15] ^
57  data[(i + 2) & 15] ^ data[ i & 15]
58  , 1);
59  }
60 
61 public:
62  explicit WorkspaceBlock(const uint8_t buffer[64]);
63 
64  // SHA-1 rounds
65  void r0(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
66  {
67  z += ((w & (x ^ y)) ^ y) + next0(i) + 0x5A827999 + rol32(v, 5);
68  w = rol32(w, 30);
69  }
70  void r1(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
71  {
72  z += ((w & (x ^ y)) ^ y) + next(i) + 0x5A827999 + rol32(v, 5);
73  w = rol32(w, 30);
74  }
75  void r2(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
76  {
77  z += (w ^ x ^ y) + next(i) + 0x6ED9EBA1 + rol32(v, 5);
78  w = rol32(w, 30);
79  }
80  void r3(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
81  {
82  z += (((w | x) & y) | (w & x)) + next(i) + 0x8F1BBCDC + rol32(v, 5);
83  w = rol32(w, 30);
84  }
85  void r4(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
86  {
87  z += (w ^ x ^ y) + next(i) + 0xCA62C1D6 + rol32(v, 5);
88  w = rol32(w, 30);
89  }
90 };
91 
92 WorkspaceBlock::WorkspaceBlock(const uint8_t buffer[64])
93 {
94  memcpy(data, buffer, sizeof(data));
95 }
96 
97 
98 // class Sha1Sum
99 
101 {
102  clear();
103 }
104 
105 Sha1Sum::Sha1Sum(std::string_view hex)
106 {
107  if (hex.size() != 40) {
108  throw MSXException("Invalid sha1, should be exactly 40 digits long: ", hex);
109  }
110  parse40(hex.data());
111 }
112 
113 #ifdef __SSE2__
114 // emulate some missing unsigned-8-bit comparison functions
115 [[nodiscard]] static inline __m128i _mm_cmpge_epu8(__m128i a, __m128i b)
116 {
117  return _mm_cmpeq_epi8(_mm_max_epu8(a, b), a);
118 }
119 
120 [[nodiscard]] static inline __m128i _mm_cmple_epu8(__m128i a, __m128i b)
121 {
122  return _mm_cmpge_epu8(b, a);
123 }
124 
125 // load 64-bit (possibly unaligned) and swap bytes
126 [[nodiscard]] static inline uint64_t loadSwap64(const char* s)
127 {
128  return Endian::read_UA_B64(s);
129 }
130 
131 #else
132 
133 [[nodiscard]] static /*constexpr*/ unsigned hex(char x, const char* str)
134 {
135  if (('0' <= x) && (x <= '9')) return x - '0';
136  if (('a' <= x) && (x <= 'f')) return x - 'a' + 10;
137  if (('A' <= x) && (x <= 'F')) return x - 'A' + 10;
138  throw MSXException("Invalid sha1, digits should be 0-9, a-f: ",
139  std::string_view(str, 40));
140 }
141 #endif
142 
143 void Sha1Sum::parse40(const char* str)
144 {
145 #ifdef __SSE2__
146  // SSE2 version
147 
148  // load characters
149  __m128i s0 = _mm_set_epi64x(loadSwap64(str + 8), loadSwap64(str + 0));
150  __m128i s1 = _mm_set_epi64x(loadSwap64(str + 24), loadSwap64(str + 16));
151  __m128i s2 = _mm_set_epi64x('0' * 0x0101010101010101, loadSwap64(str + 32));
152 
153  // chars - '0'
154  __m128i cc0 = _mm_set1_epi8(char(-'0'));
155  __m128i s0_0 = _mm_add_epi8(s0, cc0);
156  __m128i s1_0 = _mm_add_epi8(s1, cc0);
157  __m128i s2_0 = _mm_add_epi8(s2, cc0);
158 
159  // (chars | 32) - 'a' (convert uppercase 'A'-'F' into lower case)
160  __m128i c32 = _mm_set1_epi8(32);
161  __m128i cca = _mm_set1_epi8(char(-'a'));
162  __m128i s0_a = _mm_add_epi8(_mm_or_si128(s0, c32), cca);
163  __m128i s1_a = _mm_add_epi8(_mm_or_si128(s1, c32), cca);
164  __m128i s2_a = _mm_add_epi8(_mm_or_si128(s2, c32), cca);
165 
166  // was in range '0'-'9'?
167  __m128i c9 = _mm_set1_epi8(9);
168  __m128i c0_0 = _mm_cmple_epu8(s0_0, c9);
169  __m128i c1_0 = _mm_cmple_epu8(s1_0, c9);
170  __m128i c2_0 = _mm_cmple_epu8(s2_0, c9);
171 
172  // was in range 'a'-'f'?
173  __m128i c5 = _mm_set1_epi8(5);
174  __m128i c0_a = _mm_cmple_epu8(s0_a, c5);
175  __m128i c1_a = _mm_cmple_epu8(s1_a, c5);
176  __m128i c2_a = _mm_cmple_epu8(s2_a, c5);
177 
178  // either '0'-'9' or 'a'-f' must be in range for all chars
179  __m128i ok0 = _mm_or_si128(c0_0, c0_a);
180  __m128i ok1 = _mm_or_si128(c1_0, c1_a);
181  __m128i ok2 = _mm_or_si128(c2_0, c2_a);
182  __m128i ok = _mm_and_si128(_mm_and_si128(ok0, ok1), ok2);
183  if (unlikely(_mm_movemask_epi8(ok) != 0xffff)) {
184  throw MSXException("Invalid sha1, digits should be 0-9, a-f: ",
185  std::string_view(str, 40));
186  }
187 
188  // '0'-'9' to numeric value (or zero)
189  __m128i d0_0 = _mm_and_si128(s0_0, c0_0);
190  __m128i d1_0 = _mm_and_si128(s1_0, c1_0);
191  __m128i d2_0 = _mm_and_si128(s2_0, c2_0);
192 
193  // 'a'-'f' to numeric value (or zero)
194  __m128i c10 = _mm_set1_epi8(10);
195  __m128i d0_a = _mm_and_si128(_mm_add_epi8(s0_a, c10), c0_a);
196  __m128i d1_a = _mm_and_si128(_mm_add_epi8(s1_a, c10), c1_a);
197  __m128i d2_a = _mm_and_si128(_mm_add_epi8(s2_a, c10), c2_a);
198 
199  // combine 0-9 / 10-15 into 0-15
200  __m128i d0 = _mm_or_si128(d0_0, d0_a);
201  __m128i d1 = _mm_or_si128(d1_0, d1_a);
202  __m128i d2 = _mm_or_si128(d2_0, d2_a);
203 
204  // compact bytes to nibbles
205  __m128i c00ff = _mm_set1_epi16(0x00ff);
206  __m128i e0 = _mm_and_si128(_mm_or_si128(d0, _mm_srli_epi16(d0, 4)), c00ff);
207  __m128i e1 = _mm_and_si128(_mm_or_si128(d1, _mm_srli_epi16(d1, 4)), c00ff);
208  __m128i e2 = _mm_and_si128(_mm_or_si128(d2, _mm_srli_epi16(d2, 4)), c00ff);
209  __m128i f0 = _mm_packus_epi16(e0, e0);
210  __m128i f1 = _mm_packus_epi16(e1, e1);
211  __m128i f2 = _mm_packus_epi16(e2, e2);
212 
213  // store result
214  _mm_storeu_si128(reinterpret_cast<__m128i*>(a), _mm_unpacklo_epi64(f0, f1));
215  a[4] = _mm_cvtsi128_si32(f2);
216 #else
217  // equivalent c++ version
218  const char* p = str;
219  for (auto& ai : a) {
220  unsigned t = 0;
221  repeat(8, [&] {
222  t <<= 4;
223  t |= hex(*p++, str);
224  });
225  ai = t;
226  }
227 #endif
228 }
229 
230 [[nodiscard]] static constexpr char digit(unsigned x)
231 {
232  return (x < 10) ? (x + '0') : (x - 10 + 'a');
233 }
234 std::string Sha1Sum::toString() const
235 {
236  char buf[40];
237  char* p = buf;
238  for (const auto& ai : a) {
239  for (int j = 28; j >= 0; j -= 4) {
240  *p++ = digit((ai >> j) & 0xf);
241  }
242  }
243  return string(buf, 40);
244 }
245 
246 bool Sha1Sum::empty() const
247 {
248  return ranges::all_of(a, [](auto& e) { return e == 0; });
249 }
251 {
252  ranges::fill(a, 0);
253 }
254 
255 
256 // class SHA1
257 
259 {
260  // SHA1 initialization constants
261  m_state.a[0] = 0x67452301;
262  m_state.a[1] = 0xEFCDAB89;
263  m_state.a[2] = 0x98BADCFE;
264  m_state.a[3] = 0x10325476;
265  m_state.a[4] = 0xC3D2E1F0;
266 
267  m_count = 0;
268  m_finalized = false;
269 }
270 
271 void SHA1::transform(const uint8_t buffer[64])
272 {
273  WorkspaceBlock block(buffer);
274 
275  // Copy m_state[] to working vars
276  uint32_t a = m_state.a[0];
277  uint32_t b = m_state.a[1];
278  uint32_t c = m_state.a[2];
279  uint32_t d = m_state.a[3];
280  uint32_t e = m_state.a[4];
281 
282  // 4 rounds of 20 operations each. Loop unrolled
283  block.r0(a,b,c,d,e, 0); block.r0(e,a,b,c,d, 1); block.r0(d,e,a,b,c, 2);
284  block.r0(c,d,e,a,b, 3); block.r0(b,c,d,e,a, 4); block.r0(a,b,c,d,e, 5);
285  block.r0(e,a,b,c,d, 6); block.r0(d,e,a,b,c, 7); block.r0(c,d,e,a,b, 8);
286  block.r0(b,c,d,e,a, 9); block.r0(a,b,c,d,e,10); block.r0(e,a,b,c,d,11);
287  block.r0(d,e,a,b,c,12); block.r0(c,d,e,a,b,13); block.r0(b,c,d,e,a,14);
288  block.r0(a,b,c,d,e,15); block.r1(e,a,b,c,d,16); block.r1(d,e,a,b,c,17);
289  block.r1(c,d,e,a,b,18); block.r1(b,c,d,e,a,19); block.r2(a,b,c,d,e,20);
290  block.r2(e,a,b,c,d,21); block.r2(d,e,a,b,c,22); block.r2(c,d,e,a,b,23);
291  block.r2(b,c,d,e,a,24); block.r2(a,b,c,d,e,25); block.r2(e,a,b,c,d,26);
292  block.r2(d,e,a,b,c,27); block.r2(c,d,e,a,b,28); block.r2(b,c,d,e,a,29);
293  block.r2(a,b,c,d,e,30); block.r2(e,a,b,c,d,31); block.r2(d,e,a,b,c,32);
294  block.r2(c,d,e,a,b,33); block.r2(b,c,d,e,a,34); block.r2(a,b,c,d,e,35);
295  block.r2(e,a,b,c,d,36); block.r2(d,e,a,b,c,37); block.r2(c,d,e,a,b,38);
296  block.r2(b,c,d,e,a,39); block.r3(a,b,c,d,e,40); block.r3(e,a,b,c,d,41);
297  block.r3(d,e,a,b,c,42); block.r3(c,d,e,a,b,43); block.r3(b,c,d,e,a,44);
298  block.r3(a,b,c,d,e,45); block.r3(e,a,b,c,d,46); block.r3(d,e,a,b,c,47);
299  block.r3(c,d,e,a,b,48); block.r3(b,c,d,e,a,49); block.r3(a,b,c,d,e,50);
300  block.r3(e,a,b,c,d,51); block.r3(d,e,a,b,c,52); block.r3(c,d,e,a,b,53);
301  block.r3(b,c,d,e,a,54); block.r3(a,b,c,d,e,55); block.r3(e,a,b,c,d,56);
302  block.r3(d,e,a,b,c,57); block.r3(c,d,e,a,b,58); block.r3(b,c,d,e,a,59);
303  block.r4(a,b,c,d,e,60); block.r4(e,a,b,c,d,61); block.r4(d,e,a,b,c,62);
304  block.r4(c,d,e,a,b,63); block.r4(b,c,d,e,a,64); block.r4(a,b,c,d,e,65);
305  block.r4(e,a,b,c,d,66); block.r4(d,e,a,b,c,67); block.r4(c,d,e,a,b,68);
306  block.r4(b,c,d,e,a,69); block.r4(a,b,c,d,e,70); block.r4(e,a,b,c,d,71);
307  block.r4(d,e,a,b,c,72); block.r4(c,d,e,a,b,73); block.r4(b,c,d,e,a,74);
308  block.r4(a,b,c,d,e,75); block.r4(e,a,b,c,d,76); block.r4(d,e,a,b,c,77);
309  block.r4(c,d,e,a,b,78); block.r4(b,c,d,e,a,79);
310 
311  // Add the working vars back into m_state[]
312  m_state.a[0] += a;
313  m_state.a[1] += b;
314  m_state.a[2] += c;
315  m_state.a[3] += d;
316  m_state.a[4] += e;
317 }
318 
319 // Use this function to hash in binary data and strings
321 {
322  const uint8_t* data = data_.data();
323  size_t len = data_.size();
324 
325  assert(!m_finalized);
326  uint32_t j = m_count & 63;
327 
328  m_count += len;
329 
330  size_t i;
331  if ((j + len) > 63) {
332  memcpy(&m_buffer[j], data, (i = 64 - j));
333  transform(m_buffer);
334  for (; i + 63 < len; i += 64) {
335  transform(&data[i]);
336  }
337  j = 0;
338  } else {
339  i = 0;
340  }
341  memcpy(&m_buffer[j], &data[i], len - i);
342 }
343 
344 void SHA1::finalize()
345 {
346  assert(!m_finalized);
347 
348  uint32_t j = m_count & 63;
349  m_buffer[j++] = 0x80;
350  if (j > 56) {
351  memset(&m_buffer[j], 0, 64 - j);
352  transform(m_buffer);
353  j = 0;
354  }
355  memset(&m_buffer[j], 0, 56 - j);
356  Endian::B64 finalCount = 8 * m_count; // convert number of bytes to bits
357  memcpy(&m_buffer[56], &finalCount, 8);
358  transform(m_buffer);
359 
360  m_finalized = true;
361 }
362 
364 {
365  if (!m_finalized) finalize();
366  return m_state;
367 }
368 
370 {
371  SHA1 sha1;
372  sha1.update(data);
373  return sha1.digest();
374 }
375 
376 } // namespace openmsx
TclObject t
Helper class to perform a sha1 calculation.
Definition: sha1.hh:81
Sha1Sum digest()
Get the final hash.
Definition: utils/sha1.cc:363
void update(span< const uint8_t > data)
Incrementally calculate the hash value.
Definition: utils/sha1.cc:320
static Sha1Sum calc(span< const uint8_t > data)
Easier to use interface, if you can pass all data in one go.
Definition: utils/sha1.cc:369
This class represents the result of a sha1 calculation (a 160-bit value).
Definition: sha1.hh:22
bool empty() const
Definition: utils/sha1.cc:246
void parse40(const char *str)
Parse from a 40-character long buffer.
Definition: utils/sha1.cc:143
std::string toString() const
Definition: utils/sha1.cc:234
void r1(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:70
void r2(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:75
WorkspaceBlock(const uint8_t buffer[64])
Definition: utils/sha1.cc:92
void r4(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:85
void r0(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:65
void r3(uint32_t v, uint32_t &w, uint32_t x, uint32_t y, uint32_t &z, int i)
Definition: utils/sha1.cc:80
constexpr pointer data() const noexcept
Definition: span.hh:323
constexpr index_type size() const noexcept
Definition: span.hh:296
#define unlikely(x)
Definition: likely.hh:15
ALWAYS_INLINE uint64_t read_UA_B64(const void *p)
Definition: endian.hh:225
uint32_t readB32(const void *p)
Definition: endian.hh:156
This file implemented 3 utility functions:
Definition: Autofire.cc:9
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:124
void fill(ForwardRange &&range, const T &value)
Definition: ranges.hh:197
bool all_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:119
constexpr void repeat(T n, Op op)
Repeat the given operation 'op' 'n' times.
Definition: xrange.hh:170