openMSX
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 "CliComm.hh"
24 #include "EventDistributor.hh"
25 #include "StringOp.hh"
26 #include "endian.hh"
27 #include <cassert>
28 #include <cstdio>
29 #include <cstring>
30 #include <memory.h>
31 
32 using std::string;
33 
34 namespace openmsx {
35 
36 // Rotate x bits to the left
37 inline static uint32_t rol32(uint32_t value, int bits)
38 {
39  return (value << bits) | (value >> (32 - bits));
40 }
41 
42 class WorkspaceBlock {
43 private:
44  uint32_t data[16];
45 
46  uint32_t next0(int i)
47  {
48  data[i] = Endian::readB32(&data[i]);
49  return data[i];
50  }
51  uint32_t next(int i)
52  {
53  return data[i & 15] = rol32(
54  data[(i + 13) & 15] ^ data[(i + 8) & 15] ^
55  data[(i + 2) & 15] ^ data[ i & 15]
56  , 1);
57  }
58 
59 public:
60  explicit WorkspaceBlock(const uint8_t buffer[64]);
61 
62  // SHA-1 rounds
63  void r0(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
64  {
65  z += ((w & (x ^ y)) ^ y) + next0(i) + 0x5A827999 + rol32(v, 5);
66  w = rol32(w, 30);
67  }
68  void r1(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
69  {
70  z += ((w & (x ^ y)) ^ y) + next(i) + 0x5A827999 + rol32(v, 5);
71  w = rol32(w, 30);
72  }
73  void r2(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
74  {
75  z += (w ^ x ^ y) + next(i) + 0x6ED9EBA1 + rol32(v, 5);
76  w = rol32(w, 30);
77  }
78  void r3(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
79  {
80  z += (((w | x) & y) | (w & x)) + next(i) + 0x8F1BBCDC + rol32(v, 5);
81  w = rol32(w, 30);
82  }
83  void r4(uint32_t v, uint32_t& w, uint32_t x, uint32_t y, uint32_t& z, int i)
84  {
85  z += (w ^ x ^ y) + next(i) + 0xCA62C1D6 + rol32(v, 5);
86  w = rol32(w, 30);
87  }
88 };
89 
90 WorkspaceBlock::WorkspaceBlock(const uint8_t buffer[64])
91 {
92  memcpy(data, buffer, sizeof(data));
93 }
94 
95 
96 // class Sha1Sum
97 
98 Sha1Sum::Sha1Sum()
99 {
100  clear();
101 }
102 
103 Sha1Sum::Sha1Sum(string_ref str)
104 {
105  if (str.size() != 40) {
106  throw MSXException("Invalid sha1, should be exactly 40 digits long: " + str);
107  }
108  parse40(str.data());
109 }
110 
111 static inline unsigned hex(char x, const char* str)
112 {
113  if (('0' <= x) && (x <= '9')) return x - '0';
114  if (('a' <= x) && (x <= 'f')) return x - 'a' + 10;
115  if (('A' <= x) && (x <= 'F')) return x - 'A' + 10;
116  throw MSXException("Invalid sha1, digits should be 0-9, a-f: " +
117  string(str, 40));
118 }
119 void Sha1Sum::parse40(const char* str)
120 {
121  const char* p = str;
122  for (int i = 0; i < 5; ++i) {
123  unsigned t = 0;
124  for (int j = 0; j < 8; ++j) {
125  t <<= 4;
126  t |= hex(*p++, str);
127  }
128  a[i] = t;
129  }
130 }
131 
132 static inline char digit(unsigned x)
133 {
134  return (x < 10) ? (x + '0') : (x - 10 + 'a');
135 }
136 std::string Sha1Sum::toString() const
137 {
138  char buf[40];
139  char* p = buf;
140  for (int i = 0; i < 5; ++i) {
141  for (int j = 28; j >= 0; j -= 4) {
142  *p++ = digit((a[i] >> j) & 0xf);
143  }
144  }
145  return string(buf, 40);
146 }
147 
148 bool Sha1Sum::empty() const
149 {
150  for (int i = 0; i < 5; ++i) {
151  if (a[i] != 0) return false;
152  }
153  return true;
154 }
155 void Sha1Sum::clear()
156 {
157  for (int i = 0; i < 5; ++i) {
158  a[i] = 0;
159  }
160 }
161 
162 bool Sha1Sum::operator==(const Sha1Sum& other) const
163 {
164  for (int i = 0; i < 5; ++i) {
165  if (a[i] != other.a[i]) return false;
166  }
167  return true;
168 }
169 bool Sha1Sum::operator!=(const Sha1Sum& other) const
170 {
171  return !(*this == other);
172 }
173 
174 bool Sha1Sum::operator<(const Sha1Sum& other) const
175 {
176  for (int i = 0; i < 5-1; ++i) {
177  if (a[i] != other.a[i]) return a[i] < other.a[i];
178  }
179  return a[5-1] < other.a[5-1];
180 }
181 
182 
183 // class SHA1
184 
185 SHA1::SHA1()
186 {
187  // SHA1 initialization constants
188  m_state.a[0] = 0x67452301;
189  m_state.a[1] = 0xEFCDAB89;
190  m_state.a[2] = 0x98BADCFE;
191  m_state.a[3] = 0x10325476;
192  m_state.a[4] = 0xC3D2E1F0;
193 
194  m_count = 0;
195  m_finalized = false;
196 }
197 
198 void SHA1::transform(const uint8_t buffer[64])
199 {
200  WorkspaceBlock block(buffer);
201 
202  // Copy m_state[] to working vars
203  uint32_t a = m_state.a[0];
204  uint32_t b = m_state.a[1];
205  uint32_t c = m_state.a[2];
206  uint32_t d = m_state.a[3];
207  uint32_t e = m_state.a[4];
208 
209  // 4 rounds of 20 operations each. Loop unrolled
210  block.r0(a,b,c,d,e, 0); block.r0(e,a,b,c,d, 1); block.r0(d,e,a,b,c, 2);
211  block.r0(c,d,e,a,b, 3); block.r0(b,c,d,e,a, 4); block.r0(a,b,c,d,e, 5);
212  block.r0(e,a,b,c,d, 6); block.r0(d,e,a,b,c, 7); block.r0(c,d,e,a,b, 8);
213  block.r0(b,c,d,e,a, 9); block.r0(a,b,c,d,e,10); block.r0(e,a,b,c,d,11);
214  block.r0(d,e,a,b,c,12); block.r0(c,d,e,a,b,13); block.r0(b,c,d,e,a,14);
215  block.r0(a,b,c,d,e,15); block.r1(e,a,b,c,d,16); block.r1(d,e,a,b,c,17);
216  block.r1(c,d,e,a,b,18); block.r1(b,c,d,e,a,19); block.r2(a,b,c,d,e,20);
217  block.r2(e,a,b,c,d,21); block.r2(d,e,a,b,c,22); block.r2(c,d,e,a,b,23);
218  block.r2(b,c,d,e,a,24); block.r2(a,b,c,d,e,25); block.r2(e,a,b,c,d,26);
219  block.r2(d,e,a,b,c,27); block.r2(c,d,e,a,b,28); block.r2(b,c,d,e,a,29);
220  block.r2(a,b,c,d,e,30); block.r2(e,a,b,c,d,31); block.r2(d,e,a,b,c,32);
221  block.r2(c,d,e,a,b,33); block.r2(b,c,d,e,a,34); block.r2(a,b,c,d,e,35);
222  block.r2(e,a,b,c,d,36); block.r2(d,e,a,b,c,37); block.r2(c,d,e,a,b,38);
223  block.r2(b,c,d,e,a,39); block.r3(a,b,c,d,e,40); block.r3(e,a,b,c,d,41);
224  block.r3(d,e,a,b,c,42); block.r3(c,d,e,a,b,43); block.r3(b,c,d,e,a,44);
225  block.r3(a,b,c,d,e,45); block.r3(e,a,b,c,d,46); block.r3(d,e,a,b,c,47);
226  block.r3(c,d,e,a,b,48); block.r3(b,c,d,e,a,49); block.r3(a,b,c,d,e,50);
227  block.r3(e,a,b,c,d,51); block.r3(d,e,a,b,c,52); block.r3(c,d,e,a,b,53);
228  block.r3(b,c,d,e,a,54); block.r3(a,b,c,d,e,55); block.r3(e,a,b,c,d,56);
229  block.r3(d,e,a,b,c,57); block.r3(c,d,e,a,b,58); block.r3(b,c,d,e,a,59);
230  block.r4(a,b,c,d,e,60); block.r4(e,a,b,c,d,61); block.r4(d,e,a,b,c,62);
231  block.r4(c,d,e,a,b,63); block.r4(b,c,d,e,a,64); block.r4(a,b,c,d,e,65);
232  block.r4(e,a,b,c,d,66); block.r4(d,e,a,b,c,67); block.r4(c,d,e,a,b,68);
233  block.r4(b,c,d,e,a,69); block.r4(a,b,c,d,e,70); block.r4(e,a,b,c,d,71);
234  block.r4(d,e,a,b,c,72); block.r4(c,d,e,a,b,73); block.r4(b,c,d,e,a,74);
235  block.r4(a,b,c,d,e,75); block.r4(e,a,b,c,d,76); block.r4(d,e,a,b,c,77);
236  block.r4(c,d,e,a,b,78); block.r4(b,c,d,e,a,79);
237 
238  // Add the working vars back into m_state[]
239  m_state.a[0] += a;
240  m_state.a[1] += b;
241  m_state.a[2] += c;
242  m_state.a[3] += d;
243  m_state.a[4] += e;
244 }
245 
246 // Use this function to hash in binary data and strings
247 void SHA1::update(const uint8_t* data, size_t len)
248 {
249  assert(!m_finalized);
250  uint32_t j = (m_count >> 3) & 63;
251 
252  m_count += uint64_t(len) << 3;
253 
254  uint32_t i;
255  if ((j + len) > 63) {
256  memcpy(&m_buffer[j], data, (i = 64 - j));
257  transform(m_buffer);
258  for (; i + 63 < len; i += 64) {
259  transform(&data[i]);
260  }
261  j = 0;
262  } else {
263  i = 0;
264  }
265  memcpy(&m_buffer[j], &data[i], len - i);
266 }
267 
268 void SHA1::finalize()
269 {
270  assert(!m_finalized);
271  uint8_t finalcount[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
272  for (int i = 0; i < 8; i++) {
273  finalcount[i] = uint8_t(m_count >> ((7 - i) * 8));
274  }
275 
276  update(reinterpret_cast<const uint8_t*>("\200"), 1);
277  while ((m_count & 504) != 448) {
278  update(reinterpret_cast<const uint8_t*>("\0"), 1);
279  }
280  update(finalcount, 8); // cause a transform()
281  m_finalized = true;
282 }
283 
284 Sha1Sum SHA1::digest()
285 {
286  if (!m_finalized) finalize();
287  return m_state;
288 }
289 
290 Sha1Sum SHA1::calc(const uint8_t* data, size_t len)
291 {
292  SHA1 sha1;
293  sha1.update(data, len);
294  return sha1.digest();
295 }
296 
297 static void reportProgress(const string& filename, size_t percentage, CliComm& cliComm, EventDistributor& distributor) {
298  cliComm.printProgress("Calculating SHA1 sum for " + filename + "... " + StringOp::toString(percentage) + "%");
299  distributor.deliverEvents();
300 }
301 
302 Sha1Sum SHA1::calcWithProgress(const uint8_t* data, size_t len, const string& filename, CliComm& cliComm, EventDistributor& distributor)
303 {
304  if (len < 10*1024*1024) { // for small files, don't show progress
305  return calc(data, len);
306  }
307  SHA1 sha1;
308  static const size_t NUMBER_OF_STEPS = 100;
309  // calculate in NUMBER_OF_STEPS steps and report progress every step
310  auto stepSize = len / NUMBER_OF_STEPS;
311  auto remainder = len % NUMBER_OF_STEPS;
312  size_t offset = 0;
313  reportProgress(filename, 0, cliComm, distributor);
314  for (size_t i = 0; i < (NUMBER_OF_STEPS - 1); ++i) {
315  sha1.update(&data[offset], stepSize);
316  offset += stepSize;
317  reportProgress(filename, i + 1, cliComm, distributor);
318  }
319  sha1.update(data + offset, stepSize + remainder);
320  reportProgress(filename, 100, cliComm, distributor);
321  return sha1.digest();
322 }
323 
324 } // namespace openmsx
Generated on Mon May 20 2013 12:17:00 for openMSX by   doxygen 1.8.1.2