import struct


def _f(x, y, z):
    return x ^ y ^ z

def _g(x, y, z):
    return (x & y) | (~x & z)

def _h(x, y, z):
    return (x | ~y) ^ z

def _i(x, y, z):
    return (x & z) | (y & ~z)

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

def _add(*args):
    s = 0
    for a in args:
        s = (s + a) & 0xFFFFFFFF
    return s


_KL = [0x00000000, 0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC]
_KR = [0x50A28BE6, 0x5C4DD124, 0x6D703EF3, 0x00000000]

_RL = [
    [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],
    [7,4,13,1,10,6,15,3,12,0,9,5,2,14,11,8],
    [3,10,14,4,9,15,8,1,2,7,0,6,13,11,5,12],
    [1,9,11,10,0,8,12,4,13,3,7,15,14,5,6,2],
]
_RR = [
    [5,14,7,0,9,2,11,4,13,6,15,8,1,10,3,12],
    [6,11,3,7,0,13,5,10,14,15,8,12,4,9,1,2],
    [15,5,1,3,7,14,6,9,11,8,12,2,10,0,4,13],
    [8,6,4,1,3,11,15,0,5,12,2,13,9,7,10,14],
]

_SL = [
    [11,14,15,12,5,8,7,9,11,13,14,15,6,7,9,8],
    [7,6,8,13,11,9,7,15,7,12,15,9,11,7,13,12],
    [11,13,6,7,14,9,13,15,14,8,13,6,5,12,7,5],
    [11,12,14,15,14,15,9,8,9,14,5,6,8,6,5,12],
]
_SR = [
    [8,9,9,11,13,15,15,5,7,7,8,11,14,14,12,6],
    [9,13,15,7,12,8,9,11,7,7,12,7,6,15,13,11],
    [9,7,15,11,8,6,6,14,12,13,5,14,13,13,7,5],
    [15,5,8,11,14,14,6,14,6,9,12,9,12,5,15,8],
]

_FL = [_f, _g, _h, _i]
_FR = [_i, _h, _g, _f]


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

    msg = bytearray(data)
    orig_len = len(msg)
    msg.append(0x80)
    while len(msg) % 64 != 56:
        msg.append(0x00)
    msg += struct.pack("<Q", orig_len * 8)

    h0, h1, h2, h3 = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476

    for offset in range(0, len(msg), 64):
        block = msg[offset:offset + 64]
        X = list(struct.unpack("<16I", block))

        al, bl, cl, dl = h0, h1, h2, h3
        ar, br, cr, dr = h0, h1, h2, h3

        for j in range(4):
            for i in range(16):
                t = _add(al, _FL[j](bl, cl, dl), X[_RL[j][i]], _KL[j])
                t = _rotl(t, _SL[j][i])
                al, bl, cl, dl = dl, t, bl, cl

                t = _add(ar, _FR[j](br, cr, dr), X[_RR[j][i]], _KR[j])
                t = _rotl(t, _SR[j][i])
                ar, br, cr, dr = dr, t, br, cr

        t = _add(h1, cl, dr)
        h1 = _add(h2, dl, ar)
        h2 = _add(h3, al, br)
        h3 = _add(h0, bl, cr)
        h0 = t

    return struct.pack("<4I", h0, h1, h2, h3).hex()