SHA1.sol

pragma solidity ^0.4.0;

//Version is tested and working

//Go to https://gist.github.com/D-Nice/8de76f76dd60a29952264ab3898b9eb7 for WIP optimized version

contract SHA1 {

    uint8[4] shift = [3, 8, 14, 16];
    uint constant leftAlign = 16**56;
    uint constant prep = 16**55; //allow extra bits as requested in spec
    uint constant h0 = 1732584193 * prep; //0x67452301
    uint constant h1 = 4023233417 * prep; //0xEFCDAB89
    uint constant h2 = 2562383102 * prep; //0x98BADCFE
    uint constant h3 = 271733878 * prep; //0x10325476
    uint constant h4 = 3285377520 * prep; //0xC3D2E1F0

    event LOG(string indexed input, bytes digest);
    event LOGVars(uint[2] A, uint[2] B, uint[2] C, uint[2] D, uint[2] E);
    //event DEBUGWrds(uint[80]);
    //event DEBUG(string, uint);

    uint[4] K = [1518500249 * prep, 1859775393 * prep, 2400959708 * prep, 3395469782 * prep];
                //0x5A827999        //0x6ED9EBA1       //8F1BBCDC         //CA62C1D6
    function run(string _m) returns (bytes h) {
        //string memory _m = "A Test for 64 bytes message working";
        bytes memory raw = bytes(_m);

        //PREPARE PRE-PROCESSING
        uint reusedPos = raw.length + 32; //reusing due to stack depth limit
        //uint extraBitShift = (16**(62));

        //BEGIN 1-BIT APPEND AT LAST CHAR
        assembly {
            let extraBitShift := mload(0x40)
            extraBitShift := exp(16, 62)
            mstore(add(raw, reusedPos), mul(0x80, extraBitShift))
        }
        uint[2] memory A;
        A[0] = h0;
        uint[2] memory B;
        B[0] = h1;
        uint[2] memory C;
        C[0] = h2;
        uint[2] memory D;
        D[0] = h3;
        uint[2] memory E;
        E[0] = h4;

        uint rawMsgLen;

        //256byte bug was because chunk was set to a var here (sets to uint8...)
        for(uint chunk = 0; chunk <= (raw.length - (raw.length / 64) * 8) / 56; chunk++) {
            bytes memory tmp = new bytes(64); //this was causing words not to be masked properly
            // divide by 56 'should' be right, tested working with up to 128 bytes, but will have to see with larger
            // it isnt right, fix it
            if(chunk == (raw.length - (raw.length / 64) * 8) / 56)
                rawMsgLen = raw.length * 8;

            reusedPos = 32 + (64 * chunk); //didnt know 
            //BEGIN CHAR LENGTH APPEND AT ENDING OF LAST 64-BITS
            //CHUNK MESSAGE TO 512-BITS
            assembly {
                let endBits := mload(0x40)
                endBits := mload(add(raw, add(reusedPos, 32)))
                //endBits := and(endBits, 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000)
                //no need for above
                endBits := or(endBits, rawMsgLen)

                mstore(add(tmp, 0), 0x20) //mem offset
                mstore(add(tmp, 64), mload(add(raw, reusedPos))) //the bytes themselves :)
                mstore(add(tmp, 96), endBits)
                mstore(add(tmp, 32), 64) //turn into 512-bit/64-byte chunk here (will need to take care of 448 mod 512 in future)

            } //5k total gas cost up to here

            //BREAK 512-BIT CHUNK INTO SIXTEEN 32-BIT WORDS
            uint[80] memory t; //uint easiest(probably most efficient) to work with for bitwise ops
            reusedPos = 64;

            uint tmpW;
            //~ 15k gas cost used up to here
            for(var i = 0; i < 16; i++) {
                assembly {
                    tmpW := mload(add(tmp, reusedPos))
                    tmpW := and(tmpW, 0xFFFFFFFF00000000000000000000000000000000000000000000000000000000)
                }   //mask to 32-bit word
                t[i] = tmpW;
                reusedPos += 4;
            }
            //DEBUGWrds(t);
            t = expandWords(t);
            //DEBUGWrds(t);
            (A[1], B[1], C[1], D[1], E[1]) = (hashLoop(t, A[0], B[0], C[0], D[0], E[0]));

            A[0] = ((A[0] + A[1]) * 16) / 16; //add then truncate
            B[0] = ((B[0] + B[1]) * 16) / 16;
            C[0] = ((C[0] + C[1]) * 16) / 16;
            D[0] = ((D[0] + D[1]) * 16) / 16;
            E[0] = ((E[0] + E[1]) * 16) / 16;

            LOGVars(A,B,C,D,E);

        }
        A[0] *= 16;
        B[0] /= 16 ** 7; //masking with and would be better
        C[0] /= 16 ** 15;
        D[0] /= 16 ** 23;
        E[0] /= 16 ** 31;

        h = toBytes20ish(A[0] + B[0] + C[0] + D[0] + E[0]);
        LOG(_m, h);
    }

    function expandWords(uint[80] t) private returns (uint[80]) {
        for(var i = 16; i < t.length; i++) {//~1800 gas per round
            uint tRes;
            uint tNext;

            // ROTL1(((i-3 XOR i-8) XOR i-14) XOR i-16)
            for (var x = 1; x < 4; x++) {
                if (x == 1)
                    tRes = t[i-shift[0]];
                tNext = t[i-shift[x]];
                tRes = tRes ^ tNext;
            }
            t[i] = (ROTL(tRes, 1)/ leftAlign) * leftAlign; //rotate left 1, truncate

        }
        return t;
    }

    function hashLoop(uint[80] t, uint a, uint b, uint c, uint d, uint e)
    private returns (uint A, uint B, uint C, uint D, uint E) {
        A = a;
        B = b;
        C = c;
        D = d;
        E = e;
        uint f;
        uint m;
        for (var i = 0; i < t.length; i++) { //~1200 gas cost per round
            if (i <= 19)
                f = f_1(t[i], B, C, D);
            else if (i <= 39 || i >= 60)
                f = f_2(t[i], B, C, D);
            else if (i <= 59)
                f = f_3(t[i], B, C, D);
            m = ROTL(A, 5) + f + E + K[i/20] + t[i]/16;
            m = m * 16; //truncate result
            E = D;
            D = C;
            C = ((ROTL(B, 30) * 16) / leftAlign) * prep;//(ROTL(B*16, 30) / leftAlign) * prep;
            B = A;
            A = (m / leftAlign) * prep;
        }

    }

    function f_1(uint t, uint B, uint C, uint D)
    private
    returns (uint f) {
        f = B & C;
        f = f | ~B & D;
    }

    function f_2(uint t, uint B, uint C, uint D)
    private
    returns (uint f) {
        f = B ^ C;
        f = f ^ D;
    }

    function f_3(uint t, uint B, uint C, uint D)
    private
    returns (uint f) {
        f = ((B & C) | (B & D)) | C & D;

    }

    function toBytes20ish(uint256 x) internal constant returns (bytes b) {
        b = new bytes(20);
        assembly { mstore(add(b, 32), x) }
    }

    //Thanks to Axic
    function shl(uint x, uint y) internal returns (uint) {
        return x * (2 ** y);
    }

    function shr(uint x, uint y) internal returns (uint) {
        return x / (2 ** y);
    }

    function ROTL(uint x, uint y) internal returns (uint) {
        return shr(x, 32 - y) | shl(x, y);// leftAlign) * leftAlign; //could possibly use assembly here to mask to save on costs (about 25k it seems)
    }
}