Module:Hash

Documentation for this module may be created at Module:Hash/doc

-- Imports

local luts = mw.loadData('Dev:Hash/LUTs')

-- Utils: bit manipulation

local function u32_add(a, b)
    return (a + b) % 0x100000000
end

local function u32_and(a, b)
    local xx, z = 1, 0
    while (a > 0) and (b > 0) do
        if ((a % 2) + (b % 2)) == 2 then z = z + xx end
        a, b, xx = math.floor(a / 2), math.floor(b / 2), xx * 2
    end
    return z
end

local function u32_not(a)
    return 0xffffffff - a
end

local function u32_or(a, b)
    local xx, z = 1, 0
    while (a > 0) or (b > 0) do
        if ((a % 2) + (b % 2)) > 0 then z = z + xx end
        a, b, xx = math.floor(a / 2), math.floor(b / 2), xx * 2
    end
    return z
end

local function u32_rotl(a, x)
    -- We could do a `x = x % 32` or `assert(x % 32 == 0)`, but nah...
    local xx = math.floor(2 ^ (32 - x))
    return math.floor(a / xx) + ((a % xx) * math.floor(2 ^ x))
end

local function u32_xor(a, b)
    local xx, z = 1, 0
    while (a ~= b) do
        if (a % 2) ~= (b % 2) then z = z + xx end
        a, b, xx = math.floor(a / 2), math.floor(b / 2), xx * 2
    end
    return z
end

-- Utils: structs

local function pack_le_u32(u32)
    local b0 = u32 % 0x100; u32 = math.floor(u32 / 0x100)
    local b1 = u32 % 0x100; u32 = math.floor(u32 / 0x100)
    local b2 = u32 % 0x100; u32 = math.floor(u32 / 0x100)
    local b3 = u32 % 0x100
    return string.char(b0, b1, b2, b3)
end

local function pack_le_u64(u64)
    local b0 = u64 % 0x100; u64 = math.floor(u64 / 0x100)
    local b1 = u64 % 0x100; u64 = math.floor(u64 / 0x100)
    local b2 = u64 % 0x100; u64 = math.floor(u64 / 0x100)
    local b3 = u64 % 0x100; u64 = math.floor(u64 / 0x100)
    local b4 = u64 % 0x100; u64 = math.floor(u64 / 0x100)
    local b5 = u64 % 0x100; u64 = math.floor(u64 / 0x100)
    local b6 = u64 % 0x100; u64 = math.floor(u64 / 0x100)
    local b7 = u64 % 0x100
    return string.char(b0, b1, b2, b3, b4, b5, b6, b7)
end

local function unpack_le_u32(bytes, offset)
    return (string.byte(bytes, offset    )            ) +
           (string.byte(bytes, offset + 1) *     0x100) +
           (string.byte(bytes, offset + 2) *   0x10000) +
           (string.byte(bytes, offset + 3) * 0x1000000)
end

-- Utils: representation

local function bytes_to_hex(bytes)
    local repr = ''
    for i = 1, #bytes do
        repr = repr .. string.format('%02x', string.byte(bytes, i))
    end
    return repr
end

-- Utils: MW helpers

local function make_message(frame)
    local i, message = 0, ''
    for k, v in ipairs(frame.args) do
        if i > 0 then message = message .. '\0' end
        i = i + 1
        message = message .. v
    end
    -- Per Scribunto docs, we can't count the number of anonymous/numbered params with `#frame.args`
    assert(i > 0, 'Function must be invoked with at least one anonymous or numbered parameter')
    return message
end

-- Utils: hash functions

local function md5_f(x, y, z)
    return u32_or(u32_and(x, y), u32_and(u32_not(x), z))
end

local function md5_g(x, y, z)
    return u32_or(u32_and(x, z), u32_and(y, u32_not(z)))
end

local function md5_h(x, y, z)
    return u32_xor(u32_xor(x, y), z)
end

local function md5_i(x, y, z)
    return u32_xor(y, u32_or(x, u32_not(z)))
end

local function md5_op(a, b, c, d, aux, x_k, s, t_i)
    return u32_add(b, u32_rotl(u32_add(u32_add(a, aux(b, c, d)), u32_add(x_k, t_i)), s))
end

local function md5_init()
    return {
        is_finalized = false,
        buffer = '',
        message_length = 0,
        -- Initialize MD buffer (per section 3.3 of RFC 1321)
        a = 0x67452301,
        b = 0xefcdab89,
        c = 0x98badcfe,
        d = 0x10325476
    }
end

local function md5_update(context, message)
    assert(not context.is_finalized, 'MD5 context has already been finalized')

    local buffer = context.buffer .. message
    local partial_block_length = #buffer % 64
    context.buffer = (partial_block_length > 0) and string.sub(buffer, -partial_block_length) or ''
    context.message_length = context.message_length + #message

    -- Process each block (per section 3.4 of RFC 1321)
    for i = 0, math.floor(#buffer / 64) - 1 do
        local x = {}; for j = 0, 15 do x[j + 1] = unpack_le_u32(buffer, (i * 64) + (j * 4) + 1) end

        local a, b, c, d = context.a, context.b, context.c, context.d

        -- Round one
        a = md5_op(a, b, c, d, md5_f, x[ 1],  7, luts.md5_t[ 1])
        d = md5_op(d, a, b, c, md5_f, x[ 2], 12, luts.md5_t[ 2])
        c = md5_op(c, d, a, b, md5_f, x[ 3], 17, luts.md5_t[ 3])
        b = md5_op(b, c, d, a, md5_f, x[ 4], 22, luts.md5_t[ 4])
        a = md5_op(a, b, c, d, md5_f, x[ 5],  7, luts.md5_t[ 5])
        d = md5_op(d, a, b, c, md5_f, x[ 6], 12, luts.md5_t[ 6])
        c = md5_op(c, d, a, b, md5_f, x[ 7], 17, luts.md5_t[ 7])
        b = md5_op(b, c, d, a, md5_f, x[ 8], 22, luts.md5_t[ 8])
        a = md5_op(a, b, c, d, md5_f, x[ 9],  7, luts.md5_t[ 9])
        d = md5_op(d, a, b, c, md5_f, x[10], 12, luts.md5_t[10])
        c = md5_op(c, d, a, b, md5_f, x[11], 17, luts.md5_t[11])
        b = md5_op(b, c, d, a, md5_f, x[12], 22, luts.md5_t[12])
        a = md5_op(a, b, c, d, md5_f, x[13],  7, luts.md5_t[13])
        d = md5_op(d, a, b, c, md5_f, x[14], 12, luts.md5_t[14])
        c = md5_op(c, d, a, b, md5_f, x[15], 17, luts.md5_t[15])
        b = md5_op(b, c, d, a, md5_f, x[16], 22, luts.md5_t[16])

        -- Round two
        a = md5_op(a, b, c, d, md5_g, x[ 2],  5, luts.md5_t[17])
        d = md5_op(d, a, b, c, md5_g, x[ 7],  9, luts.md5_t[18])
        c = md5_op(c, d, a, b, md5_g, x[12], 14, luts.md5_t[19])
        b = md5_op(b, c, d, a, md5_g, x[ 1], 20, luts.md5_t[20])
        a = md5_op(a, b, c, d, md5_g, x[ 6],  5, luts.md5_t[21])
        d = md5_op(d, a, b, c, md5_g, x[11],  9, luts.md5_t[22])
        c = md5_op(c, d, a, b, md5_g, x[16], 14, luts.md5_t[23])
        b = md5_op(b, c, d, a, md5_g, x[ 5], 20, luts.md5_t[24])
        a = md5_op(a, b, c, d, md5_g, x[10],  5, luts.md5_t[25])
        d = md5_op(d, a, b, c, md5_g, x[15],  9, luts.md5_t[26])
        c = md5_op(c, d, a, b, md5_g, x[ 4], 14, luts.md5_t[27])
        b = md5_op(b, c, d, a, md5_g, x[ 9], 20, luts.md5_t[28])
        a = md5_op(a, b, c, d, md5_g, x[14],  5, luts.md5_t[29])
        d = md5_op(d, a, b, c, md5_g, x[ 3],  9, luts.md5_t[30])
        c = md5_op(c, d, a, b, md5_g, x[ 8], 14, luts.md5_t[31])
        b = md5_op(b, c, d, a, md5_g, x[13], 20, luts.md5_t[32])

        -- Round three
        a = md5_op(a, b, c, d, md5_h, x[ 6],  4, luts.md5_t[33])
        d = md5_op(d, a, b, c, md5_h, x[ 9], 11, luts.md5_t[34])
        c = md5_op(c, d, a, b, md5_h, x[12], 16, luts.md5_t[35])
        b = md5_op(b, c, d, a, md5_h, x[15], 23, luts.md5_t[36])
        a = md5_op(a, b, c, d, md5_h, x[ 2],  4, luts.md5_t[37])
        d = md5_op(d, a, b, c, md5_h, x[ 5], 11, luts.md5_t[38])
        c = md5_op(c, d, a, b, md5_h, x[ 8], 16, luts.md5_t[39])
        b = md5_op(b, c, d, a, md5_h, x[11], 23, luts.md5_t[40])
        a = md5_op(a, b, c, d, md5_h, x[14],  4, luts.md5_t[41])
        d = md5_op(d, a, b, c, md5_h, x[ 1], 11, luts.md5_t[42])
        c = md5_op(c, d, a, b, md5_h, x[ 4], 16, luts.md5_t[43])
        b = md5_op(b, c, d, a, md5_h, x[ 7], 23, luts.md5_t[44])
        a = md5_op(a, b, c, d, md5_h, x[10],  4, luts.md5_t[45])
        d = md5_op(d, a, b, c, md5_h, x[13], 11, luts.md5_t[46])
        c = md5_op(c, d, a, b, md5_h, x[16], 16, luts.md5_t[47])
        b = md5_op(b, c, d, a, md5_h, x[ 3], 23, luts.md5_t[48])

        -- Round four
        a = md5_op(a, b, c, d, md5_i, x[ 1],  6, luts.md5_t[49])
        d = md5_op(d, a, b, c, md5_i, x[ 8], 10, luts.md5_t[50])
        c = md5_op(c, d, a, b, md5_i, x[15], 15, luts.md5_t[51])
        b = md5_op(b, c, d, a, md5_i, x[ 6], 21, luts.md5_t[52])
        a = md5_op(a, b, c, d, md5_i, x[13],  6, luts.md5_t[53])
        d = md5_op(d, a, b, c, md5_i, x[ 4], 10, luts.md5_t[54])
        c = md5_op(c, d, a, b, md5_i, x[11], 15, luts.md5_t[55])
        b = md5_op(b, c, d, a, md5_i, x[ 2], 21, luts.md5_t[56])
        a = md5_op(a, b, c, d, md5_i, x[ 9],  6, luts.md5_t[57])
        d = md5_op(d, a, b, c, md5_i, x[16], 10, luts.md5_t[58])
        c = md5_op(c, d, a, b, md5_i, x[ 7], 15, luts.md5_t[59])
        b = md5_op(b, c, d, a, md5_i, x[14], 21, luts.md5_t[60])
        a = md5_op(a, b, c, d, md5_i, x[ 5],  6, luts.md5_t[61])
        d = md5_op(d, a, b, c, md5_i, x[12], 10, luts.md5_t[62])
        c = md5_op(c, d, a, b, md5_i, x[ 3], 15, luts.md5_t[63])
        b = md5_op(b, c, d, a, md5_i, x[10], 21, luts.md5_t[64])

        context.a = u32_add(context.a, a)
        context.b = u32_add(context.b, b)
        context.c = u32_add(context.c, c)
        context.d = u32_add(context.d, d)
    end
end

local function md5_finalize(context)
    assert(not context.is_finalized, 'MD5 context has already been finalized')

    -- Pad (per sections 3.1 and 3.2 of RFC 1321)
    local padding = '\128' .. string.rep('\0', ((56 - ((context.message_length + 1) % 64)) + 64) % 64) .. pack_le_u64(context.message_length * 8)
    assert(#context.buffer + #padding == ((#context.buffer < 56) and 64 or 128))

    md5_update(context, padding)

    -- Concatenate (per section 3.5 of RFC 1321)
    local digest = pack_le_u32(context.a) .. pack_le_u32(context.b) .. pack_le_u32(context.c) .. pack_le_u32(context.d)

    -- Clean up
    context.is_finalized = true
    context.buffer = nil

    return digest
end

local function MD5(message)
    local context = md5_init()
    if message then md5_update(context, message) end

    local iface, memoized_digest, memoized_hexdigest = {}, nil, nil

    function iface.update(message)
        assert(memoized_digest == nil, 'MD5 context has already been finalized')
        md5_update(context, message)
        return iface  -- Facilitate fluent interface
    end

    function iface.digest()
        if memoized_digest == nil then memoized_digest = md5_finalize(context); context = nil end
        return memoized_digest
    end

    function iface.hexdigest()
        if memoized_hexdigest == nil then memoized_hexdigest = bytes_to_hex(iface.digest()) end
        return memoized_hexdigest
    end

    return iface
end

-- Exports

local p = {}

-- Exports: for use in other libraries

p.MD5 = MD5

-- Exports: invocables

function p.md5_hexdigest(frame)
    local message = make_message(frame)
    return mw.hash and mw.hash.hashValue('md5', message) or MD5(message).hexdigest()
end

return p