fork download 
  1. #include <algorithm>
  2. #include <array>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <memory>
  6. #include <string>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. class BitInputStream;
  12. class StringBitInputStream;
  13.  
  14. extern shared_ptr<array<unsigned long, 5> > computeHashBySHA1(const shared_ptr<BitInputStream>& msg);
  15.  
  16. class BitInputStream {
  17. public:
  18.     virtual bool getBit() = 0;
  19. 	virtual bool isEOF() = 0;
  20. };
  21.  
  22. class StringBitInputStream : public BitInputStream {
  23. public:
  24. 	StringBitInputStream(const string& str);
  25. 	virtual bool getBit();
  26. 	virtual bool isEOF();
  27. protected:
  28. 	string str;
  29. 	size_t str_pos;
  30. 	unsigned int ch_pos;
  31. };
  32.  
  33. #define ASSERT(pred) assert(#pred, pred);
  34.  
  35. extern void assert(const char* pred_str, const bool& pred);
  36.  
  37. typedef unsigned long (*FUNCTION_IN_SHA1)(const unsigned long& x, const unsigned long& y, const unsigned long& z);
  38.  
  39. static unsigned long rotateLeft(const unsigned long& x, const unsigned int& n);
  40. static unsigned long chInSHA1(const unsigned long& x, const unsigned long& y, const unsigned long& z);
  41. static unsigned long parityInSHA1(const unsigned long& x, const unsigned long& y, const unsigned long& z);
  42. static unsigned long majInSHA1(const unsigned long& x, const unsigned long& y, const unsigned long& z);
  43.  
  44. static const FUNCTION_IN_SHA1 FUNCTIONS_IN_SHA1[] = {
  45. 	chInSHA1, 
  46. 	parityInSHA1, 
  47. 	majInSHA1, 
  48. 	parityInSHA1, 
  49. };
  50.  
  51. static const unsigned long K_IN_SHA1[] = {
  52. 	0x5a827999, 
  53. 	0x6ed9eba1, 
  54. 	0x8f1bbcdc, 
  55. 	0xca62c1d6, 
  56. };
  57.  
  58. static const unsigned long INITIAL_HASH_VALUES_IN_SHA1[] = {
  59. 	0x67452301, 
  60. 	0xefcdab89, 
  61. 	0x98badcfe, 
  62. 	0x10325476, 
  63. 	0xc3d2e1f0, 
  64. };
  65.  
  66. shared_ptr<array<unsigned long, 5> > computeHashBySHA1(const shared_ptr<BitInputStream>& msg) {
  67. 	shared_ptr<array<unsigned long, 5> > hash(new array<unsigned long, 5>);
  68. 	copy(INITIAL_HASH_VALUES_IN_SHA1, INITIAL_HASH_VALUES_IN_SHA1 + 5, &hash->front());
  69. 	shared_ptr<array<unsigned long, 16> > block(new array<unsigned long, 16>);
  70. 	shared_ptr<array<unsigned long, 80> > sche(new array<unsigned long, 80>);
  71. 	unsigned long long len = 0;
  72. 	bool put_end = false;
  73. 	bool put_len = false;
  74. 	while (!put_len) {
  75. 		block->fill(0);
  76. 		unsigned int block_pos = 0;
  77. 		for (; block_pos < 512 && !msg->isEOF(); block_pos++) {
  78. 			block->at(block_pos >> 5) |= (msg->getBit() == true ? 1 : 0) << (31 - (block_pos & 0x1F));
  79. 			len++;
  80. 		}
  81. 		if (block_pos < 512) {
  82. 			if (!put_end) {
  83. 				block->at(block_pos >> 5) |= 1 << (31 - (block_pos & 0x1F));
  84. 				block_pos++;
  85. 				put_end = true;
  86. 			}
  87. 			if (block_pos + 64 <= 512) {
  88. 				*(unsigned long long*)&block->at(14) = len;
  89. 				block->at(14) = len >> 32;
  90. 				block->at(15) = len & 0xFFFFFFFF;
  91. 				put_len = true;
  92. 			}
  93. 		}
  94. 		for (unsigned int i = 0; i < 80; i++) {
  95. 			if (i < 16) sche->at(i) = block->at(i);
  96. 			else sche->at(i) = rotateLeft(sche->at(i - 3) ^ sche->at(i - 8) ^ sche->at(i - 14) ^ sche->at(i - 16), 1);
  97. 		}
  98. 		unsigned long a = hash->at(0);
  99. 		unsigned long b = hash->at(1);
  100. 		unsigned long c = hash->at(2);
  101. 		unsigned long d = hash->at(3);
  102. 		unsigned long e = hash->at(4);
  103. 		for (unsigned int i = 0; i < 80; i++) {
  104. 			unsigned long t = 0;
  105. 			t += rotateLeft(a, 5);
  106. 			t += FUNCTIONS_IN_SHA1[i / 20](b, c, d);
  107. 			t += e;
  108. 			t += K_IN_SHA1[i / 20];
  109. 			t += sche->at(i);
  110. 			e = d;
  111. 			d = c;
  112. 			c = rotateLeft(b, 30);
  113. 			b = a;
  114. 			a = t;
  115. 		}
  116. 		hash->at(0) += a;
  117. 		hash->at(1) += b;
  118. 		hash->at(2) += c;
  119. 		hash->at(3) += d;
  120. 		hash->at(4) += e;
  121. 	}
  122. 	return hash;
  123. }
  124.  
  125. unsigned long rotateLeft(const unsigned long& x, const unsigned int& n) {
  126. 	return (x << n) | (x >> (32 - n));
  127. }
  128.  
  129. unsigned long chInSHA1(const unsigned long& x, const unsigned long& y, const unsigned long& z) {
  130. 	return (x & y) ^ (~x & z);
  131. }
  132.  
  133. unsigned long parityInSHA1(const unsigned long& x, const unsigned long& y, const unsigned long& z) {
  134. 	return x ^ y ^ z;
  135. }
  136.  
  137. unsigned long majInSHA1(const unsigned long& x, const unsigned long& y, const unsigned long& z) {
  138. 	return (x & y) ^ (x & z) ^ (y & z);
  139. }
  140.  
  141. StringBitInputStream::StringBitInputStream(const string& str) : str(str), str_pos(0), ch_pos(7) {}
  142.  
  143. bool StringBitInputStream::getBit() {
  144. 	bool res = ((this->str.at(this->str_pos) >> this->ch_pos) & 1) == 1;
  145. 	if (this->ch_pos == 0) {
  146. 		this->str_pos++;
  147. 		this->ch_pos = 7;
  148. 	}
  149. 	else this->ch_pos--;
  150. 	return res;
  151. }
  152.  
  153. bool StringBitInputStream::isEOF() {
  154. 	return this->str_pos >= this->str.length();
  155. }
  156.  
  157. void assert(const char* pred_str, const bool& pred) {
  158. 	if (pred) {
  159. 		cout << "アサート成功: " << pred_str << endl;
  160. 	}
  161. 	else {
  162. 		cerr << "アサート失敗: " << pred_str << endl;
  163. 		exit(1);
  164. 	}
  165. }
  166.  
  167. int main() {
  168. 	{
  169. 		shared_ptr<array<unsigned long, 5> > hash = computeHashBySHA1(shared_ptr<BitInputStream>(new StringBitInputStream(
  170. 			"abc")));
  171. 		ASSERT(hash->at(0) == 0xa9993e36)
  172. 		ASSERT(hash->at(1) == 0x4706816a)
  173. 		ASSERT(hash->at(2) == 0xba3e2571)
  174. 		ASSERT(hash->at(3) == 0x7850c26c)
  175. 		ASSERT(hash->at(4) == 0x9cd0d89d)
  176. 	}
  177. 	{
  178. 		shared_ptr<array<unsigned long, 5> > hash = computeHashBySHA1(shared_ptr<BitInputStream>(new StringBitInputStream(
  179. 			"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq")));
  180. 		ASSERT(hash->at(0) == 0x84983e44)
  181. 		ASSERT(hash->at(1) == 0x1c3bd26e)
  182. 		ASSERT(hash->at(2) == 0xbaae4aa1)
  183. 		ASSERT(hash->at(3) == 0xf95129e5)
  184. 		ASSERT(hash->at(4) == 0xe54670f1)
  185. 	}
  186. 	return 0;
  187. }
  188.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin 
Standard input is empty
stdout 
アサート成功: hash->at(0) == 0xa9993e36
アサート成功: hash->at(1) == 0x4706816a
アサート成功: hash->at(2) == 0xba3e2571
アサート成功: hash->at(3) == 0x7850c26c
アサート成功: hash->at(4) == 0x9cd0d89d
アサート成功: hash->at(0) == 0x84983e44
アサート成功: hash->at(1) == 0x1c3bd26e
アサート成功: hash->at(2) == 0xbaae4aa1
アサート成功: hash->at(3) == 0xf95129e5
アサート成功: hash->at(4) == 0xe54670f1
https://ideone.com/vEyiW7
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!