#include <memory>
#include <cmath>
#include <stdexcept>
#include <time.h>
#include <stdlib.h>

using namespace std;

UINT K(UINT t){
	if ((0 <= t) && (t <= 19))
		return 0x5A827999;
	
	else if ((20 <= t) && (t <= 39))
		return 0x6ED9EBA1;
	
	else if ((40 <= t) && (t <= 59))
		return 0x8F1BBCDC;
	
	else if ((60 <= t) && (t <= 79))
		return 0xCA62C1D6;
	
	else
		return 0;
}

UINT f(UINT t, UINT B, UINT C, UINT D){
	if ((0 <= t) && (t <= 19))
		return (B & C) | (!B & D);
	
	else if ((20 <= t) && (t <= 39))
		return B ^ C ^ D;
	
	else if ((40 <= t) && (t <= 59))
		return (B & C) | (B & D) | (C & D);
	
	else if ((60 <= t) && (t <= 79))
		return B ^ C ^ D;
	
	else
		return 0;
}

string SHA1(string input){
	UINT H0, H1, H2, H3, H4;
	UINT A, B, C, D, E;
	ULONG size = input.size()*8;
	ULONG N = size/512 + (((size%512)>448)?2:1);
	UINT i, t, s, temp;
	UINT MASK = 0x0F;

	struct blocks {
		UINT W[16];	
	} *M;

	M = new blocks[N];

	memset(M,0,N*sizeof(blocks));
	memcpy(M, input.data(), input.size());
	memcpy(&M[N-1].W[14], &size, sizeof(size));

	H0 = 0x67452301;
	H1 = 0xEFCDAB89;
	H2 = 0x98BADCFE;
	H3 = 0x10325476;
	H4 = 0xC3D2E1F0;

	for(i = 0; i<N; i++) {
		A = H0; B = H1; C = H2; D = H3; E = H4;

		for (t=0; t<80; t++)
		{
			s = t & MASK;
			if (t >= 16)
				M[i].W[s] = _rotl((M[i].W[(s + 13) & MASK] ^ M[i].W[(s + 8) & MASK] ^ M[i].W[(s + 2) & MASK] ^ M[i].W[s]),1);
			
			temp = _rotl(A,5) + f(t, B, C, D) + E + M[i].W[s] + K(t);
			E = D; D = C; C = _rotl(B, 30); B = A; A = temp;
		}

		H0 += A; H1 += B; H2 += C; H3 += D; H4 += E;
	}

	delete[] M;	

	char buf[41]; sprintf(buf, "%0x%0x%0x%0x%0x",H0, H1, H2, H3, H4);

	return string(buf);
}