Generate passcodes for Medal of Honor: Rising Sun (PlayStation 2, GameCube, Xbox)

medal_of_honor_rising_sun.py

import string
import itertools
from collections import defaultdict

KNOWN_CODES = """\
Cichlid
ALBINO
Loach
LELEUPI
GOURAMI
BENGAL
ZEBRA
Tetra
Botia
MOOR
Pleco
Discus
CARDINAL
BOXFISH
WRASSE
BANNER
PARROT
DOTTYBACK
BETTA
BATFISH
JAWFISH
TUSKFISH
MANDARIN
PUFFER
TANG
TRIGGER
HOGFISH
DAMSEL
GARIBALDI
SPINEFOOT
SEAHORSE
TILEFISH
GOBY
BUTTERFLY"""


TARGETS = {
    # PlayStation 2
    0x50D56DF8: {"system": "PS2", "code": None},
    0x810249C0: {"system": "PS2", "code": None},
    0xBB2534B0: {"system": "PS2", "code": None},
    0x00162F50: {"system": "PS2", "code": None},
    0x9E6F213E: {"system": "PS2", "code": None},
    0xBAC90A77: {"system": "PS2", "code": None},
    0x001D1629: {"system": "PS2", "code": None},
    0x56686A35: {"system": "PS2", "code": None},
    0x8130E2D9: {"system": "PS2", "code": None},
    0x73CC2DE7: {"system": "PS2", "code": None},
    0xE1BFF229: {"system": "PS2", "code": None},
    0x1A7240F3: {"system": "PS2", "code": None},
    0x77933AE7: {"system": "PS2", "code": None},
    0x54949B01: {"system": "PS2", "code": None},
    0x02DC149B: {"system": "PS2", "code": None},
    0x02DC149C: {"system": "PS2", "code": None},
    0x02DC149D: {"system": "PS2", "code": None},
    0x02DC149E: {"system": "PS2", "code": None},
    0x02DC149F: {"system": "PS2", "code": None},
    0x02DC14A0: {"system": "PS2", "code": None},
    0x02DC14A1: {"system": "PS2", "code": None},
    0x02DC14A2: {"system": "PS2", "code": None},
    0x02DC14A3: {"system": "PS2", "code": None},
    0x5E5EA82B: {"system": "PS2", "code": None},
    0x5E5EA82C: {"system": "PS2", "code": None},
    0x5E5EA82D: {"system": "PS2", "code": None},
    0x5E5EA82E: {"system": "PS2", "code": None},
    0x5E5EA82F: {"system": "PS2", "code": None},
    0x5E5EA830: {"system": "PS2", "code": None},
    0x5E5EA831: {"system": "PS2", "code": None},
    0x5E5EA832: {"system": "PS2", "code": None},
    0x5E5EA833: {"system": "PS2", "code": None},
    0x4336A476: {"system": "PS2", "code": None},
    0x5E5EA84C: {"system": "PS2", "code": None},
    # GameCube
    0xCBD17F55: {"system": "GC", "code": None},
    0x5029CC54: {"system": "GC", "code": None},
    0x896B7366: {"system": "GC", "code": None},
    0x56FC368A: {"system": "GC", "code": None},
    0x03368D06: {"system": "GC", "code": None},
    0x037D5AF2: {"system": "GC", "code": None},
    0x2B9CC6F3: {"system": "GC", "code": None},
    0x00197B3C: {"system": "GC", "code": None},
    0x03C227FF: {"system": "GC", "code": None},
    0x9482B86F: {"system": "GC", "code": None},
    0xE869D98F: {"system": "GC", "code": None},
    0x042E6E73: {"system": "GC", "code": None},
    0x0281E98E: {"system": "GC", "code": None},
    0x5206D3C8: {"system": "GC", "code": None},
    0x027A32C7: {"system": "GC", "code": None},
    0x027A32C8: {"system": "GC", "code": None},
    0x027A32C9: {"system": "GC", "code": None},
    0x027A32CA: {"system": "GC", "code": None},
    0x027A32CB: {"system": "GC", "code": None},
    0x027A32CC: {"system": "GC", "code": None},
    0x027A32CD: {"system": "GC", "code": None},
    0x027A32CE: {"system": "GC", "code": None},
    0x027A32CF: {"system": "GC", "code": None},
    0x51C08BD7: {"system": "GC", "code": None},
    0x51C08BD8: {"system": "GC", "code": None},
    0x51C08BD9: {"system": "GC", "code": None},
    0x51C08BDA: {"system": "GC", "code": None},
    0x51C08BDB: {"system": "GC", "code": None},
    0x51C08BDC: {"system": "GC", "code": None},
    0x51C08BDD: {"system": "GC", "code": None},
    0x51C08BDE: {"system": "GC", "code": None},
    0x51C08BDF: {"system": "GC", "code": None},
    0x02DF9E54: {"system": "GC", "code": None},
    0x51C08BF8: {"system": "GC", "code": None},
    # Xbox
    0x674492F0: {"system": "XB", "code": None},
    0xF8568D52: {"system": "XB", "code": None},
    0x94BEB546: {"system": "XB", "code": None},
    0xF20103AB: {"system": "XB", "code": None},
    0xAAE96EF2: {"system": "XB", "code": None},
    0x89F8D420: {"system": "XB", "code": None},
    0x83E77BF4: {"system": "XB", "code": None},
    0x027C6F2F: {"system": "XB", "code": None},
    0xE1D13C04: {"system": "XB", "code": None},
    0x798B0828: {"system": "XB", "code": None},
    0xB08694DD: {"system": "XB", "code": None},
    0x72690CB7: {"system": "XB", "code": None},
    0xAAEBD01E: {"system": "XB", "code": None},
    0x51BE9015: {"system": "XB", "code": None},
    0x54DB79F3: {"system": "XB", "code": None},
    0x54DB79F4: {"system": "XB", "code": None},
    0x54DB79F5: {"system": "XB", "code": None},
    0x54DB79F6: {"system": "XB", "code": None},
    0x54DB79F7: {"system": "XB", "code": None},
    0x54DB79F8: {"system": "XB", "code": None},
    0x54DB79F9: {"system": "XB", "code": None},
    0x54DB79FA: {"system": "XB", "code": None},
    0x54DB79FB: {"system": "XB", "code": None},
    0xF04AB883: {"system": "XB", "code": None},
    0xF04AB884: {"system": "XB", "code": None},
    0xF04AB885: {"system": "XB", "code": None},
    0xF04AB886: {"system": "XB", "code": None},
    0xF04AB887: {"system": "XB", "code": None},
    0xF04AB888: {"system": "XB", "code": None},
    0xF04AB889: {"system": "XB", "code": None},
    0xF04AB88A: {"system": "XB", "code": None},
    0xF04AB88B: {"system": "XB", "code": None},
    0x4DA3FB89: {"system": "XB", "code": None},
    0xF04AB8A4: {"system": "XB", "code": None},
}


def get_hash(data):
    val = 0xFFFFFFFF
    for d in data:
        val = ((val * 0x21) + d) & 0xFFFFFFFF
    return val


def meet_in_the_middle(total_len):
    prefix_len = total_len // 2
    suffix_len = total_len - prefix_len
    charset = string.ascii_uppercase
    char_codes = [ord(c) for c in charset]

    forward_map = defaultdict(list)

    # Forward hash
    for prod in itertools.product(char_codes, repeat=prefix_len):
        h = 0xFFFFFFFF
        for c in prod:
            h = ((h * 0x21) + c) & 0xFFFFFFFF
        forward_map[h].append("".join(chr(c) for c in prod))

    # Reverse hash
    for prod in itertools.product(char_codes, repeat=suffix_len):
        for target, info in TARGETS.items():
            if info["code"]:
                continue

            h = target
            for c in reversed(prod):
                h = ((h - c) * 0x3E0F83E1) & 0xFFFFFFFF

            # Match the reversed hash to forward hashes
            if h in forward_map:
                suffix = "".join(chr(c) for c in prod)
                for prefix in forward_map[h]:
                    full_s = prefix + suffix
                    info["code"] = full_s
                    info["status"] = "new"
                    if all(info["code"] for info in TARGETS.values()):
                        return


if __name__ == "__main__":
    for line in KNOWN_CODES.splitlines():
        line = line.strip().upper()
        h = get_hash(line.encode())
        if h in TARGETS:
            TARGETS[h]["code"] = line
            TARGETS[h]["status"] = "old"

    for n in itertools.count(4):
        meet_in_the_middle(n)
        if all(info["code"] for info in TARGETS.values()):
            break

    for target, info in TARGETS.items():
        print(
            info["system"],
            format(target, "08x"),
            info["code"],
            info["status"],
            sep=",",
        )

See Rings of Saturn for details.

Output:

PS2,50d56df8,AURIGA,new
PS2,810249c0,BUTTERFLY,old
PS2,bb2534b0,IKFCPNV,new
PS2,00162f50,GOBY,old
PS2,9e6f213e,GARIBALDI,old
PS2,bac90a77,TILEFISH,old
PS2,001d1629,TANG,old
PS2,56686a35,DAMSEL,old
PS2,8130e2d9,SEAHORSE,old
PS2,73cc2de7,PUFFER,old
PS2,e1bff229,MANDARIN,old
PS2,1a7240f3,TRIGGER,old
PS2,77933ae7,HOGFISH,old
PS2,54949b01,CHROMI,new
PS2,02dc149b,GOASR,new
PS2,02dc149c,GOASS,new
PS2,02dc149d,GOAST,new
PS2,02dc149e,GOASU,new
PS2,02dc149f,GOASV,new
PS2,02dc14a0,GOASW,new
PS2,02dc14a1,GOASX,new
PS2,02dc14a2,GOASY,new
PS2,02dc14a3,GOASZ,new
PS2,5e5ea82b,GOASQQ,new
PS2,5e5ea82c,GOASQR,new
PS2,5e5ea82d,GOASQS,new
PS2,5e5ea82e,GOASQT,new
PS2,5e5ea82f,GOASQU,new
PS2,5e5ea830,GOASQV,new
PS2,5e5ea831,GOASQW,new
PS2,5e5ea832,GOASQX,new
PS2,5e5ea833,GOASQY,new
PS2,4336a476,SPINEFOOT,old
PS2,5e5ea84c,GOASRQ,new
GC,cbd17f55,ZFBDIQV,new
GC,5029cc54,ALBINO,old
GC,896b7366,BALLOON,new
GC,56fc368a,DISCUS,old
GC,03368d06,LOACH,old
GC,037d5af2,PLECO,old
GC,2b9cc6f3,GOURAMI,old
GC,00197b3c,MOOR,old
GC,03c227ff,TETRA,old
GC,9482b86f,LELEUPI,old
GC,e869d98f,CICHLID,old
GC,042e6e73,ZEBRA,old
GC,0281e98e,BOTIA,old
GC,5206d3c8,BENGAL,old
GC,027a32c7,BARAR,new
GC,027a32c8,BARAS,new
GC,027a32c9,BARAT,new
GC,027a32ca,BARAU,new
GC,027a32cb,BARAV,new
GC,027a32cc,BARAW,new
GC,027a32cd,BARAX,new
GC,027a32ce,BARAY,new
GC,027a32cf,BARAZ,new
GC,51c08bd7,BARAQQ,new
GC,51c08bd8,BARAQR,new
GC,51c08bd9,BARAQS,new
GC,51c08bda,BARAQT,new
GC,51c08bdb,BARAQU,new
GC,51c08bdc,BARAQV,new
GC,51c08bdd,BARAQW,new
GC,51c08bde,BARAQX,new
GC,51c08bdf,BARAQY,new
GC,02df9e54,GUPPY,new
GC,51c08bf8,BARARQ,new
XB,674492f0,TUSKFISH,old
XB,f8568d52,FZVESMX,new
XB,94beb546,VDWLNLP,new
XB,f20103ab,JAWFISH,old
XB,aae96ef2,BOXFISH,old
XB,89f8d420,BATFISH,old
XB,83e77bf4,WRASSE,old
XB,027c6f2f,BETTA,old
XB,e1d13c04,DOTTYBACK,old
XB,798b0828,SCOPAS,new
XB,b08694dd,CARDINAL,old
XB,72690cb7,PARROT,old
XB,aaebd01e,VNGCMNV,new
XB,51be9015,BANNER,old
XB,54db79f3,CLOWMR,new
XB,54db79f4,CLOWMS,new
XB,54db79f5,CLOWMT,new
XB,54db79f6,CLOWMU,new
XB,54db79f7,CLOWMV,new
XB,54db79f8,CLOWMW,new
XB,54db79f9,CLOWMX,new
XB,54db79fa,CLOWMY,new
XB,54db79fb,CLOWMZ,new
XB,f04ab883,FWGKFZU,new
XB,f04ab884,PVOGSUA,new
XB,f04ab885,PVOGSUB,new
XB,f04ab886,PVOGSUC,new
XB,f04ab887,PVOGSUD,new
XB,f04ab888,PVOGSUE,new
XB,f04ab889,PVOGSUF,new
XB,f04ab88a,PVOGSUG,new
XB,f04ab88b,PVOGSUH,new
XB,4da3fb89,NRXFWDQ,new
XB,f04ab8a4,CLOWMRQ,new