import struct

_SBOXES = None

def _init_sboxes():
    global _SBOXES
    if _SBOXES is not None:
        return

    _t1 = [
        0x02AAB17CF7E90C5E, 0xAC424B03E243A8EC, 0x72CD5BE30DD5FCD3, 0x6D019B93F6F97F3A,
        0xCD9978FFD21F9193, 0x7573A1C9708029E2, 0xB164326B922A83C3, 0x46883EEE04915870,
        0xEAACE3057103ECE6, 0xC54169B808A3535C, 0x4CE754918DDEC47C, 0x0AA2F4DFDC0DF40C,
        0x10B76F18A74DBEFA, 0xC6CCB6235AD1AB6A, 0x13726121572FE2FF, 0x1A488C6F199D921E,
        0x4BC9F9F4DA0007CA, 0x26F5E6F6E85241C7, 0x859079DBEA5947B6, 0x4F1885C5C99E8C92,
        0xD78E761EA96F864B, 0x8E36428C52B5C17D, 0x69CF6827373063C1, 0xB607C93D9BB4C56E,
        0x7D820E760E76B5EA, 0x645C9CC6F07FDC42, 0xBF38A078243342E0, 0x5F6B343C9D2E7D04,
        0xF2C28AEB600B0EC6, 0x6C0ED85F7254BCAC, 0x71592281A4DB4FE5, 0x1967FA69CE0FED9F,
        0xFD5293F8B96545DB, 0xC879E9D7F2A7600B, 0x860248920193194E, 0xA4F9533B2D9CC0B3,
        0x9053836C15957613, 0xDB6DCF8AFC357BF1, 0x18BEEA7A7A370F57, 0x037117CA50B99066,
        0x6AB30A9774424A35, 0xF4E92F02E325249B, 0x7739DB07061CCAE1, 0xD8F3B49CECA42A05,
        0xBD56BE3F51382F73, 0x45FAED5843B0BB28, 0x1C813D5C11BF1F83, 0x8AF0E4B6D75FA169,
        0x33EE18A487AD9999, 0x3C26E8EAB1C3B092, 0xB510102BC0A822F9, 0x141EEF310CE6123B,
        0xFC65B90059DDB154, 0xE0158640C5E0E607, 0x884E079826C3A3CF, 0x930D0D9523C535FD,
        0x35638D754E9A2B00, 0x4085FCCF40469DD5, 0xC4B17AD28BE23A4C, 0xCAB2F0FC6A3E6A2E,
        0x2860971A6B943FCD, 0x3DDE6EE212E30446, 0x6222F32AE01765AE, 0x5D550BB5478308FE,
        0xA9EFA98DA0EDA22A, 0xC351A71686C40DA7, 0x1105586D9C867C84, 0xDCFFEE85FDA22853,
        0xCCFBD0262C5EEF76, 0xBAF294CB8990D201, 0xE69464F52AFAD975, 0x94B013AFDF133E14,
        0x06A7D1A32823C958, 0x6F95FE5130F61119, 0xD92AB34E462C06C0, 0xED7BDE33887C71D2,
        0x79746D6E6518393E, 0x5BA419385D713329, 0x7C1BA6B948A97564, 0x31987C197BFDAC67,
        0xDE6C23C44B053D02, 0x581C49FED002D64D, 0xDD474D6338261571, 0xAA4546C3E473D062,
        0x928FCE349455F860, 0x48161BBACAAB94D9, 0x63912430770E6F68, 0x6EC8A5E602C6641C,
        0x87282515337DDD2B, 0x2CDA6B42034B701B, 0xB03D37C181CB096D, 0xE108438266C71C6F,
        0x2B3180C7EB51B255, 0xDF92B82F96C08BBC, 0x5C68C8C0A632F3BA, 0x5504CC861C3D0556,
        0xABBFA4E55FB26B8F, 0x41848B0AB3BACEB4, 0xB334A273AA445D32, 0xBCA696F0A85AD881,
        0x24F6EC65B528D56C, 0x0CE1512E90F4524A, 0x4E9DD79D5506D35A, 0x258905FAC6CE9779,
        0x2019295B3E109B33, 0xF8A9478B73A054CC, 0x2924F2F934417EB0, 0x3993357D536D1BC4,
        0x38A81AC21DB6FF8B, 0x47C4FBF17D6016BF, 0x1E0FAADD7667E3F5, 0x7ABCFF62938BEB96,
        0xA78DAD948FC179C9, 0x8F1F98B72911E50D, 0x61E48EAE27121A45, 0x4D62F7AD31859808,
        0xECEBA345EF5CEAEB, 0xF5CEB25EBC9684CE, 0xF633E20CB7F76221, 0xA32CDF06AB8293E4,
        0x985A202CA5EE2CA4, 0xCF0B8447CC8A8FB1, 0x9F765244979859A3, 0xA8D516B1A1240017,
        0x0BD7BA3EBB5DC726, 0xE54BCA55B86ADB39, 0x1D7A3AFD6C478063, 0x519EC608E7669EDD,
        0x0E5715A2D149AA23, 0x177D4571848FF194, 0xEEB55F3241014C22, 0x0F5E5CA13A6BEED4,
        0xAA4B7DC893E509D2, 0xF6D6E4D2237A2B75, 0x8CC5A3D514206B6D, 0xE9E14CD4D3D7C957,
        0x8CE7DFBA41D1C6A0, 0x82C08CA15C2FA0C5, 0xFC28AC282CD29CC9, 0x8F1C16C2440D5C44,
        0x7B0D25BFDD5D25AE, 0xABB6BFAB0E5F91B4, 0xCC2B17A5F9E7C6D7, 0x2E45C62E0E0F8C8E,
        0xE880CBCF41E14C42, 0x3AB95B0DE1CC47D1, 0x51AF1AEBC89A5BA2, 0x1B6E9A26AD6CA5CE,
        0xF7FE08CCE8B4C58C, 0x94F0F85F8E60DE11, 0xCE5BDB5C36CF020B, 0x66F4FC1CCE42E18C,
        0x0F1BBE94BAC7CC0A, 0x9C1F6C5D3C9F45F6, 0x2FDF06CE2E58E8DD, 0x3B2BA50FA5B45BBE,
        0xC68EA9DE7F3B04F6, 0xB7B55AC8F1E49B81, 0x5FB7FF14C0667EB2, 0x02ABB0E3AAED0036,
        0xF04F92F76FD4F4C6, 0x27DAE4EDE5E0D2F7, 0xFCB7A7EC35CF07D2, 0xEB3BC6E6AAC2CA43,
        0x8C3B6E54FB9B0AEC, 0xFAEFF55D11E93C25, 0xFCF2F53C7C6C39D9, 0x3B5D0C97EC30E4E0,
        0x6E87CE1C00CEF0CA, 0xB6D7B4C6ED5EAFCD, 0x1FA2DD8D18D6C474, 0x2F27AAAB50F08D3B,
        0xB43D11C2CBFEA08C, 0x8C3A3038279E8CFE, 0x3A09FB60DEDEACB0, 0x1D5D5EA530DCDE8E,
        0x98E62AC4BAD73AAE, 0xAC7E99F3C92B8D26, 0xC0FC5C71C0CE95D6, 0x2A55D69F104BFECA,
        0x4E96F71F7B91DD0E, 0xE51E5A2A8F3F3BE4, 0x8B79F6A97F07CDD3, 0x1E4C2A3DEC98C5F5,
        0x8A49B51CCF6B80B8, 0x61F14B58B61CFF0D, 0x5EB8FE31C6E9D40F, 0xC8A3F6E18C4F7F53,
        0xFE94AB24AD6C2C07, 0x3F5A6BEA90EC7CC7, 0xB3CC55DA3ED8975D, 0xE3A9EB72EEE8E1FC,
        0x26BBB5AE12E0B562, 0x61F01E3AD00CAF43, 0xB4E35EB51EFBB5FA, 0x62CDCC18E40F6C23,
        0xF92D04D33F56EEB8, 0x5F2A05CCEC5E2E33, 0x9F88E9BC4A15C0BD, 0xC0BC0C75B4BA5E7A,
        0xE19D4EE5F0AAD7FA, 0x7F4ED4F7C0EF8613, 0x2A65FB14CB28B69D, 0xF4F07F079DE8A37B,
        0x2A88EFDE5B7DB971, 0x74B41EEB1B2803BB, 0x5E05E01B9E750F63, 0x28E0703A2EF51B72,
        0xC78BC5D4C0A43BD2, 0x0C96F041484E72C5, 0x4FAC362B5FE59B73, 0x4B0DDAAF99B29D47,
        0xDD3B3E3E8C64DB25, 0x56EE5AE8C4EABC75, 0x20CDE5EB50A73DEE, 0x2D3F068CCFE22DD0,
        0xBC19C0C9A89AE2A1, 0x9AC72A11E791A668, 0x32C7D87A36FC56CC, 0x6F4DECC94ADE64CD,
        0x28F21BE2B90F6E44, 0x91F26ADB3EFE0F30, 0x57E6D1D65C62E0CC, 0x86E3DEF2AD7E63EF,
        0x3E5FA4F4C4ABDA70, 0xB7FC02459A1EA35E, 0x43A53965C5BC4C3E, 0xCCE08E1B70CF2D3B,
        0x4E9EEF06E5B8D3A5, 0xBC85A4E5ACE89A6D, 0x98C1E1B2F96BC4D0, 0x2927F9E3D39A80E5,
        0x7090E57E51810F84, 0xC8A6A6667649C9E1, 0xF03D5B87D0E8B8DE, 0xAFF1BE2B19B82D9E,
        0x67C8B95C11E0A94C, 0x95C87FC2D7DCDBEF, 0x06A3D31AFA50B5B1, 0x45CFE0B94A6E67AC,
        0xA48F2F03E6A3399D, 0xC43ED6D7C6B1D00E, 0xBB2CFBA2A1B94F5A, 0x3DEAAAA5437BAD4C,
        0x4F5A51AF0DB68A4C, 0x2A6F2C1B49C7E2CF, 0x54BB3CD0B4D5D47B, 0x4E3E7E9D0DDF9F62,
        0x4CE5E1EF78F61A33, 0x0E0B68B1AED79FDB, 0x44FA0C6C53E5BB8F, 0x1B12EE1CA88FECC5,
        0x1E05FB65E7A70D6D, 0x50D8C8A67DEB3E32, 0x5CBD6D291F62F21D, 0x6D78F1E56893F01E,
    ]

    _t2 = [v ^ 0xA5A5A5A5A5A5A5A5 for v in _t1]

    _SBOXES = (_t1, _t2,
               [_t1[i] ^ (_t2[i] >> 32 | (_t2[i] & 0xFFFFFFFF) << 32) for i in range(256)],
               [_t2[i] ^ (_t1[i] >> 16 | (_t1[i] & 0xFFFF) << 48) for i in range(256)])


def _tiger_round(a, b, c, x, mul):
    _init_sboxes()
    t1, t2, t3, t4 = _SBOXES
    c ^= x
    c &= 0xFFFFFFFFFFFFFFFF
    a -= t1[c & 0xFF] ^ t2[(c >> 16) & 0xFF] ^ t3[(c >> 32) & 0xFF] ^ t4[(c >> 48) & 0xFF]
    a &= 0xFFFFFFFFFFFFFFFF
    b += t4[(c >> 8) & 0xFF] ^ t3[(c >> 24) & 0xFF] ^ t2[(c >> 40) & 0xFF] ^ t1[(c >> 56) & 0xFF]
    b &= 0xFFFFFFFFFFFFFFFF
    b = (b * mul) & 0xFFFFFFFFFFFFFFFF
    return a, b, c


def _tiger_pass(a, b, c, x, mul):
    a, b, c = _tiger_round(a, b, c, x[0], mul)
    b, c, a = _tiger_round(b, c, a, x[1], mul)
    c, a, b = _tiger_round(c, a, b, x[2], mul)
    a, b, c = _tiger_round(a, b, c, x[3], mul)
    b, c, a = _tiger_round(b, c, a, x[4], mul)
    c, a, b = _tiger_round(c, a, b, x[5], mul)
    a, b, c = _tiger_round(a, b, c, x[6], mul)
    b, c, a = _tiger_round(b, c, a, x[7], mul)
    return a, b, c


def _key_schedule(x):
    x = list(x)
    x[0] = (x[0] - (x[7] ^ 0xA5A5A5A5A5A5A5A5)) & 0xFFFFFFFFFFFFFFFF
    x[1] ^= x[0]
    x[2] = (x[2] + x[1]) & 0xFFFFFFFFFFFFFFFF
    x[3] = (x[3] - (x[2] ^ ((~x[1] & 0xFFFFFFFFFFFFFFFF) << 19))) & 0xFFFFFFFFFFFFFFFF
    x[4] ^= x[3]
    x[5] = (x[5] + x[4]) & 0xFFFFFFFFFFFFFFFF
    x[6] = (x[6] - (x[5] ^ ((~x[4] & 0xFFFFFFFFFFFFFFFF) >> 23))) & 0xFFFFFFFFFFFFFFFF
    x[7] ^= x[6]
    x[0] = (x[0] + x[7]) & 0xFFFFFFFFFFFFFFFF
    x[1] = (x[1] - (x[0] ^ ((~x[7] & 0xFFFFFFFFFFFFFFFF) << 19))) & 0xFFFFFFFFFFFFFFFF
    x[2] ^= x[1]
    x[3] = (x[3] + x[2]) & 0xFFFFFFFFFFFFFFFF
    x[4] = (x[4] - (x[3] ^ ((~x[2] & 0xFFFFFFFFFFFFFFFF) >> 23))) & 0xFFFFFFFFFFFFFFFF
    x[5] ^= x[4]
    x[6] = (x[6] + x[5]) & 0xFFFFFFFFFFFFFFFF
    x[7] = (x[7] - (x[6] ^ 0x0123456789ABCDEF)) & 0xFFFFFFFFFFFFFFFF
    return x


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

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

    a = 0x0123456789ABCDEF
    b = 0xFEDCBA9876543210
    c = 0xF096A5B4C3B2E187

    _init_sboxes()

    for offset in range(0, len(msg), 64):
        block = msg[offset:offset + 64]
        x = list(struct.unpack("<8Q", block))

        aa, bb, cc = a, b, c
        a, b, c = _tiger_pass(a, b, c, x, 5)
        x = _key_schedule(x)
        c, a, b = _tiger_pass(c, a, b, x, 7)
        x = _key_schedule(x)
        b, c, a = _tiger_pass(b, c, a, x, 9)

        a ^= aa
        b = (b - bb) & 0xFFFFFFFFFFFFFFFF
        c = (c + cc) & 0xFFFFFFFFFFFFFFFF

    result = struct.pack("<QQQ", a, b, c)
    return result.hex()