import struct


def _rotl32(x, n):
    return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF


def _f1(x6, x5, x4, x3, x2, x1, x0):
    return ((x1) & ((x0) ^ (x4))) ^ ((x2) & (x5)) ^ ((x3) & (x6)) ^ (x0)

def _f2(x6, x5, x4, x3, x2, x1, x0):
    return ((x2) & (((x1) & ~(x3)) ^ ((x4) & (x5)) ^ (x6) ^ (x0))) ^ ((x4) & ((x1) ^ (x5))) ^ ((x3 & x5) ^ x0)

def _f3(x6, x5, x4, x3, x2, x1, x0):
    return ((x3) & (((x1) & (x2)) ^ (x6) ^ (x0))) ^ ((x1) & (x4)) ^ ((x2) & (x5)) ^ (x0)


_ORDER_1 = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31]
_ORDER_2 = [5,14,26,18,11,28,7,16,0,23,20,22,1,10,4,8,30,3,21,9,17,24,29,6,19,12,15,13,2,25,31,27]
_ORDER_3 = [19,9,4,20,28,17,8,22,29,14,25,12,24,30,16,26,31,15,7,3,1,0,18,27,13,6,21,10,23,11,5,2]

_K2 = [
    0x452821E6, 0x38D01377, 0xBE5466CF, 0x34E90C6C,
    0xC0AC29B7, 0xC97C50DD, 0x3F84D5B5, 0xB5470917,
    0x9216D5D9, 0x8979FB1B, 0xD1310BA6, 0x98DFB5AC,
    0x2FFD72DB, 0xD01ADFB7, 0xB8E1AFED, 0x6A267E96,
    0xBA7C9045, 0xF12C7F99, 0x24A19947, 0xB3916CF7,
    0x0801F2E2, 0x858EFC16, 0x636920D8, 0x71574E69,
    0xA458FEA3, 0xF4933D7E, 0x0D95748F, 0x728EB658,
    0x718BCD58, 0x82154AEE, 0x7B54A41D, 0xC25A59B5,
]

_K3 = [
    0x9C30D539, 0x2AF26013, 0xC5D1B023, 0x286085F0,
    0xCA417918, 0xB8DB38EF, 0x8E79DCB0, 0x603A180E,
    0x6C9E0E8B, 0xB01E8A3E, 0xD71577C1, 0xBD314B27,
    0x78AF2FDA, 0x55605C60, 0xE65525F3, 0xAA55AB94,
    0x57489862, 0x63E81440, 0x55CA396A, 0x2AAB10B6,
    0xB4CC5C34, 0x1141E8CE, 0xA15486AF, 0x7C72E993,
    0xB3EE1411, 0x636FBC2A, 0x2BA9C55D, 0x741831F6,
    0xCE5C3E16, 0x9B87931E, 0xAFD6BA33, 0x6C24CF5C,
]


def haval128(data):
    if isinstance(data, str):
        data = data.encode("utf-8")

    msg = bytearray(data)
    orig_len_bits = len(data) * 8
    msg.append(0x01)
    while len(msg) % 128 != 118:
        msg.append(0x00)

    version_info = (3 & 0x07) | ((128 & 0xFF) << 3) | ((3 & 0x03) << 11)
    msg += struct.pack("<H", version_info)
    msg += struct.pack("<Q", orig_len_bits)

    h = [
        0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344,
        0xA4093822, 0x299F31D0, 0x082EFA98, 0xEC4E6C89,
    ]

    for offset in range(0, len(msg), 128):
        block = msg[offset:offset + 128]
        w = list(struct.unpack("<32I", block))

        t = list(h)

        for i in range(32):
            idx = _ORDER_1[i]
            temp = _f1(t[6], t[5], t[4], t[3], t[2], t[1], t[0])
            temp = _rotl32(temp, 25)
            temp = (temp + t[7] + w[idx]) & 0xFFFFFFFF
            for j in range(7, 0, -1):
                t[j] = t[j - 1]
            t[0] = temp

        for i in range(32):
            idx = _ORDER_2[i]
            temp = _f2(t[6], t[5], t[4], t[3], t[2], t[1], t[0])
            temp = _rotl32(temp, 25)
            temp = (temp + t[7] + w[idx] + _K2[i]) & 0xFFFFFFFF
            for j in range(7, 0, -1):
                t[j] = t[j - 1]
            t[0] = temp

        for i in range(32):
            idx = _ORDER_3[i]
            temp = _f3(t[6], t[5], t[4], t[3], t[2], t[1], t[0])
            temp = _rotl32(temp, 25)
            temp = (temp + t[7] + w[idx] + _K3[i]) & 0xFFFFFFFF
            for j in range(7, 0, -1):
                t[j] = t[j - 1]
            t[0] = temp

        for i in range(8):
            h[i] = (h[i] + t[i]) & 0xFFFFFFFF

    x0, x1, x2, x3, x4, x5, x6, x7 = h
    x0 = (x0 + ((x7 >> 24) & 0xF)) & 0xFFFFFFFF
    x1 = (x1 + ((x7 >> 16) & 0xF)) & 0xFFFFFFFF
    x2 = (x2 + ((x7 >> 8) & 0xF)) & 0xFFFFFFFF
    x3 = (x3 + ((x7) & 0xF)) & 0xFFFFFFFF

    return struct.pack("<4I", x0, x1, x2, x3).hex()