// Author:  cirakg & claude ai
// Summary: SHA-512 in pure Monkey C (FIPS 180-4), because Connect IQ has no native SHA-512.
//
// Only SHA-512 OTP entries use this (most services use SHA-1). It works on
// 64-bit Long values: Monkey C Longs wrap around on overflow like unsigned
// arithmetic modulo 2^64, but `>>` copies the sign bit, so every right shift
// masks off the copied bits (see the Mn constants).
//
// Verified against the FIPS 180-4 example messages and 15 seeded messages
// around the 128-byte padding boundary (test/crypto/HashTest.mc).
//
// Performance note: one 128-byte block is roughly ten thousand VM operations,
// and an OTP code needs four blocks (HMAC). The cost is measured in M2's
// benchmark tests; long inputs must be split into steps by the caller so the
// watchdog never trips.

import Toybox.Lang;

module Sha512 {

    // Round constants: the first 64 bits of the fractional parts of the cube
    // roots of the first 80 primes (FIPS 180-4 section 4.2.3).
    const K = [
        0x428a2f98d728ae22l, 0x7137449123ef65cdl, 0xb5c0fbcfec4d3b2fl,
        0xe9b5dba58189dbbcl, 0x3956c25bf348b538l, 0x59f111f1b605d019l,
        0x923f82a4af194f9bl, 0xab1c5ed5da6d8118l, 0xd807aa98a3030242l,
        0x12835b0145706fbel, 0x243185be4ee4b28cl, 0x550c7dc3d5ffb4e2l,
        0x72be5d74f27b896fl, 0x80deb1fe3b1696b1l, 0x9bdc06a725c71235l,
        0xc19bf174cf692694l, 0xe49b69c19ef14ad2l, 0xefbe4786384f25e3l,
        0x0fc19dc68b8cd5b5l, 0x240ca1cc77ac9c65l, 0x2de92c6f592b0275l,
        0x4a7484aa6ea6e483l, 0x5cb0a9dcbd41fbd4l, 0x76f988da831153b5l,
        0x983e5152ee66dfabl, 0xa831c66d2db43210l, 0xb00327c898fb213fl,
        0xbf597fc7beef0ee4l, 0xc6e00bf33da88fc2l, 0xd5a79147930aa725l,
        0x06ca6351e003826fl, 0x142929670a0e6e70l, 0x27b70a8546d22ffcl,
        0x2e1b21385c26c926l, 0x4d2c6dfc5ac42aedl, 0x53380d139d95b3dfl,
        0x650a73548baf63del, 0x766a0abb3c77b2a8l, 0x81c2c92e47edaee6l,
        0x92722c851482353bl, 0xa2bfe8a14cf10364l, 0xa81a664bbc423001l,
        0xc24b8b70d0f89791l, 0xc76c51a30654be30l, 0xd192e819d6ef5218l,
        0xd69906245565a910l, 0xf40e35855771202al, 0x106aa07032bbd1b8l,
        0x19a4c116b8d2d0c8l, 0x1e376c085141ab53l, 0x2748774cdf8eeb99l,
        0x34b0bcb5e19b48a8l, 0x391c0cb3c5c95a63l, 0x4ed8aa4ae3418acbl,
        0x5b9cca4f7763e373l, 0x682e6ff3d6b2b8a3l, 0x748f82ee5defb2fcl,
        0x78a5636f43172f60l, 0x84c87814a1f0ab72l, 0x8cc702081a6439ecl,
        0x90befffa23631e28l, 0xa4506cebde82bde9l, 0xbef9a3f7b2c67915l,
        0xc67178f2e372532bl, 0xca273eceea26619cl, 0xd186b8c721c0c207l,
        0xeada7dd6cde0eb1el, 0xf57d4f7fee6ed178l, 0x06f067aa72176fbal,
        0x0a637dc5a2c898a6l, 0x113f9804bef90dael, 0x1b710b35131c471bl,
        0x28db77f523047d84l, 0x32caab7b40c72493l, 0x3c9ebe0a15c9bebcl,
        0x431d67c49c100d4cl, 0x4cc5d4becb3e42b6l, 0x597f299cfc657e2al,
        0x5fcb6fab3ad6faecl, 0x6c44198c4a475817l
    ];

    // Initial hash value: the first 64 bits of the fractional parts of the
    // square roots of the first 8 primes (FIPS 180-4 section 5.3.5).
    const IV = [
        0x6a09e667f3bcc908l, 0xbb67ae8584caa73bl, 0x3c6ef372fe94f82bl,
        0xa54ff53a5f1d36f1l, 0x510e527fade682d1l, 0x9b05688c2b3e6c1fl,
        0x1f83d9abfb41bd6bl, 0x5be0cd19137e2179l
    ];

    const BLOCK_BYTES = 128;
    const LENGTH_FIELD_BYTES = 16;

    // Masks that clear the bits `>>` copies from the sign: Mn keeps the low
    // 64 - n bits, so ((x >> n) & Mn) is a logical shift and
    // (((x >> n) & Mn) | (x << (64 - n))) a right rotation by n. The rotations
    // are written out inline in compress(), because function calls are
    // expensive in the Monkey C VM and compress() is the hot loop.
    const M1 = 0x7fffffffffffffffl;
    const M6 = 0x03ffffffffffffffl;
    const M7 = 0x01ffffffffffffffl;
    const M8 = 0x00ffffffffffffffl;
    const M14 = 0x0003ffffffffffffl;
    const M18 = 0x00003fffffffffffl;
    const M19 = 0x00001fffffffffffl;
    const M28 = 0x0000000fffffffffl;
    const M34 = 0x000000003fffffffl;
    const M39 = 0x0000000001ffffffl;
    const M41 = 0x00000000007fffffl;
    const M61 = 0x0000000000000007l;

    // Read 8 bytes at offset as a big-endian 64-bit value (two native 32-bit reads).
    function read64(data as ByteArray, offset as Number) as Long {
        var hi = data.decodeNumber(Lang.NUMBER_FORMAT_UINT32, {:offset => offset, :endianness => Lang.ENDIAN_BIG}) as Number or Long;
        var lo = data.decodeNumber(Lang.NUMBER_FORMAT_UINT32, {:offset => offset + 4, :endianness => Lang.ENDIAN_BIG}) as Number or Long;
        return (hi.toLong() << 32) | (lo.toLong() & 0xFFFFFFFFl);
    }

    // The message followed by FIPS 180-4 padding: a 1 bit, zeros, and the
    // message length in bits as a 128-bit big-endian number.
    function pad(data as ByteArray) as ByteArray {
        var length = data.size();
        var total = ((length + 1 + LENGTH_FIELD_BYTES + BLOCK_BYTES - 1) / BLOCK_BYTES) * BLOCK_BYTES;
        var msg = new [total]b;
        for (var i = 0; i < length; i++) {
            msg[i] = data[i];
        }
        msg[length] = 0x80;
        // Monkey C ByteArrays are limited far below 2^61 bytes, so the upper 64
        // bits of the length field are always zero.
        var bits = length.toLong() * 8l;
        for (var i = 0; i < 8; i++) {
            msg[total - 1 - i] = ((bits >> (8 * i)) & 0xFFl).toNumber();
        }
        return msg;
    }

    // Process one 128-byte block at offset into the hash state h.
    function compress(h as Array<Long>, msg as ByteArray, offset as Number, w as Array<Long>) as Void {
        for (var t = 0; t < 16; t++) {
            w[t] = read64(msg, offset + 8 * t);
        }
        for (var t = 16; t < 80; t++) {
            var x = w[t - 15];
            var y = w[t - 2];
            var s0 = (((x >> 1) & M1) | (x << 63)) ^ (((x >> 8) & M8) | (x << 56)) ^ ((x >> 7) & M7);
            var s1 = (((y >> 19) & M19) | (y << 45)) ^ (((y >> 61) & M61) | (y << 3)) ^ ((y >> 6) & M6);
            w[t] = w[t - 16] + s0 + w[t - 7] + s1;
        }
        var a = h[0];
        var b = h[1];
        var c = h[2];
        var d = h[3];
        var e = h[4];
        var f = h[5];
        var g = h[6];
        var hh = h[7];
        for (var t = 0; t < 80; t++) {
            var bigS1 = (((e >> 14) & M14) | (e << 50)) ^ (((e >> 18) & M18) | (e << 46)) ^ (((e >> 41) & M41) | (e << 23));
            var choose = (e & f) ^ (~e & g);
            var temp1 = hh + bigS1 + choose + (K[t] as Long) + w[t];
            var bigS0 = (((a >> 28) & M28) | (a << 36)) ^ (((a >> 34) & M34) | (a << 30)) ^ (((a >> 39) & M39) | (a << 25));
            var majority = (a & b) ^ (a & c) ^ (b & c);
            hh = g;
            g = f;
            f = e;
            e = d + temp1;
            d = c;
            c = b;
            b = a;
            a = temp1 + bigS0 + majority;
        }
        h[0] = h[0] + a;
        h[1] = h[1] + b;
        h[2] = h[2] + c;
        h[3] = h[3] + d;
        h[4] = h[4] + e;
        h[5] = h[5] + f;
        h[6] = h[6] + g;
        h[7] = h[7] + hh;
    }

    // The 64-byte SHA-512 digest of data. The padded copy of the message is
    // wiped before returning, because HMAC feeds keys through here.
    function digest(data as ByteArray) as ByteArray {
        var msg = pad(data);
        var h = [] as Array<Long>;
        for (var i = 0; i < 8; i++) {
            h.add(IV[i] as Long);
        }
        var w = [] as Array<Long>;
        for (var i = 0; i < 80; i++) {
            w.add(0l);
        }
        for (var offset = 0; offset < msg.size(); offset += BLOCK_BYTES) {
            compress(h, msg, offset, w);
        }
        Bytes.wipe(msg);
        for (var i = 0; i < 80; i++) {
            w[i] = 0l;
        }
        var out = new [64]b;
        for (var i = 0; i < 8; i++) {
            var word = h[i];
            for (var j = 7; j >= 0; j--) {
                out[8 * i + j] = (word & 0xFFl).toNumber();
                word = word >> 8;
            }
        }
        return out;
    }
}