# SHA1 produces a 160 bit digest (or 20 byte hex digest) of any binary
# input message with bit length at most 2^64-1.

# Usage:
#   >>> import sha1
#   >>> data = sha1.str2bin("All your base are belong to us!")
#   >>> sha1.digest(data)
#   '1110101011101101100000101101000101010000110001110110110010000011
#    1101011101110100101001110011011101001110011110001100111000000111
#    11010001110010001100100010100110'
#   >>> sha1.hex_digest(data)
#   'eaed82d150c76c83d774a7374e78ce07d1c8c8a6'

# Copyright (c) 2009, Morten Kristensen (msk@nullpointer.dk)
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
#     * Redistributions of source code must retain the above copyright
#       notice, this list of conditions and the following disclaimer.
#     * Redistributions in binary form must reproduce the above
#       copyright notice, this list of conditions and the following
#       disclaimer in the documentation and/or other materials
#       provided with the distribution.
#     * Neither the name of the Nullpointer.dk nor the names of its
#       contributors may be used to endorse or promote products
#       derived from this software without specific prior written
#       permission.
# 
# THIS SOFTWARE IS PROVIDED BY Morten Kristensen (msk@nullpointer.dk)
# ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Morten
# Kristensen (msk@nullpointer.dk) BE LIABLE FOR ANY DIRECT, INDIRECT,
# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
# CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.

import math

def binrep(num, block=8):
    binrep = bin(num)[2:]        
    rlen = len(binrep)
    pad = 0        
    while (rlen + pad) % block > 0:
        pad += 1
    return "0"*pad + binrep

def str2bin(data):
    binarr = bytearray(data.encode("utf-8"))
    res = ""
    for b in binarr:
        res += binrep(b)
    return res

def pad(binary):
    bits = len(binary)
    if bits > 2**64-1:
        raise ValueError("max 2^64-1 bit input!")
    d = (447 - bits) % 512
    l = binrep(bits, 64)
    return binary + "1" + "0"*d  + l

def AND(A, B, block=32):
    res = ""
    for i in range(block):
        if A[i] == "1" and B[i] == "1":
            res += "1"
        else:
            res += "0"
    return res

def OR(A, B, block=32):
    res = ""
    for i in range(block):
        if A[i] == "1" or B[i] == "1":
            res += "1"
        else:
            res += "0"
    return res

def XOR(A, B, block=32):
    res = ""
    for i in range(block):
        if A[i] == B[i]:
            res += "0"
        else:
            res += "1"
    return res

def NOT(A):
    res = ""
    for i in range(len(A)):
        if A[i] == "0":
            res += "1"
        else:
            res += "0"
    return res

def reverse(string):
    res = ""
    for c in string:
        res = c + res
    return res

def bin2dec(string, base=2):
    string = reverse(string)
    res = 0
    pos = 0
    for elm in string:
        res += int(elm)*(base**pos)
        pos += 1
    return res

def ADD(A, B, block=32):
    a = bin2dec(A)
    b = bin2dec(B)
    return binrep((a + b) % 2**block, block)
        
def logic_f(B, C, D, t):
    if t >= 0 and t <= 19:
        return OR(AND(B, C),
                  AND(NOT(B), D))
    elif (t >= 20 and t <= 39) or (t >= 60 and t <= 79):
        return XOR(XOR(B, C), D)
    elif t >= 40 and t <= 59:
        return OR(OR(AND(B, C),
                     AND(B, D)),
                  AND(C, D))

def k(t):
    if t >= 0 and t <= 19:
        return "01011010100000100111100110011001"
    elif t >= 20 and t <= 39:
        return "01101110110110011110101110100001"
    elif t >= 40 and t <= 59:
        return "10001111000110111011110011011100"
    elif t >= 60 and t <= 79:
        return "11001010011000101100000111010110"

# Circular left shift
def ROTL(shift, binary):
    for i in range(shift):
        binary = binary[1:] + binary[0]
    return binary

def word(i, binary, block=32):
    return binary[(i*block):(i*block)+block]

def digest(binary):
    binary = pad(binary)
    h0 = "01100111010001010010001100000001"
    h1 = "11101111110011011010101110001001"
    h2 = "10011000101110101101110011111110"
    h3 = "00010000001100100101010001110110"
    h4 = "11000011110100101110000111110000"

    n = math.ceil(len(binary)/512)    
    for i in range(n):
        block = word(i, binary, 512)
        words = {k:word(k, block) for k in range(16)}
        for t in range(16, 80):
            words[t] = ROTL(1, XOR(XOR(XOR(words[t-3], words[t-8]),
                                       words[t-14]),
                                   words[t-16]))

        A = h0
        B = h1
        C = h2
        D = h3
        E = h4
        for t in range(80):
            tmp = ADD(ADD(ADD(ADD(ROTL(5, A),
                                  logic_f(B, C, D, t)),
                              E),
                          words[t]),
                      k(t))
            E = D
            D = C
            C = ROTL(30, B)
            B = A
            A = tmp
            
        h0 = ADD(h0, A)
        h1 = ADD(h1, B)
        h2 = ADD(h2, C)
        h3 = ADD(h3, D)
        h4 = ADD(h4, E)
            
    return h0 + h1 + h2 + h3 + h4

def bin2hex(data, block=40):
    res = ""    
    for i in range(block):
        res += hex(bin2dec(word(i, data, 4)))[2:]
    return res

def hex2bin(data):
    res = ""
    for c in data:
        if c == "a":
            n = 10
        elif c == "b":
            n = 11
        elif c == "c":
            n = 12
        elif c == "d":
            n = 13 
        elif c == "e":
            n = 14
        elif c == "f":
            n = 15
        else:
            n = int(c)
        res += binrep(n, 4)
    return res

def hex_digest(binary):
    return bin2hex(digest(binary))