gists/thps1/thps1.c

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef uint8_t u8;
typedef int32_t s32;
typedef uint32_t u32;
typedef int64_t s64;
typedef uint64_t u64;

static u64 prng_state = 1;
static u32 prng() {
    prng_state = 3935559000370003845 * prng_state + 1;
    return prng_state ^ (prng_state >> 32);
}

typedef struct {
    u8 name[13];
    u8 payload[11];
    u32 residual;
} code_t;

void translate(u8 *name) {
    // in-place translation of ascii to alphabetical indices.
    // the input argument must be able to hold at least 13 characters.
    // the resulting translation is no longer null-terminated (if the input even was).

    int i;
    for (i = 0; i < 13; i++) {
        u8 c = name[i];
        if (c == '\0') break;
        if (c >= 'a' && c <= 'z') {
            name[i] = c - 'a';
        } else if (c >= 'A' && c <= 'Z') {
            name[i] = c - 'A';
        } else {
            name[i] = 26;
        }
    }

    // remaining space gets filled with a null-like character:
    for (; i < 13; i++) {
        name[i] = 26;
    }
}

u32 multu_hi(u32 a, u32 b) {
    // returns the upper 32-bits of a * b (unsigned).
    return (u32)(((u64)a * (u64)b) >> 32);
}

s32 mult_lo(s32 a, s32 b) {
    // returns the lower 32-bits of a * b (signed).
    return (s32)(((s64)a * (s64)b) & 0xFFFFFFFF);
}

void decode(code_t *code) {
    u32 r = 0;
    u32 a3 = 0x98534637;

    for (int i = 0; i < 11; i++) {
        u32 a1 = code->name[i];
        u32 temp = 0x10000 - (a3 & 0xFFFF);
        u32 a0 = a1 + 20 + temp;
        u32 v1 = a0 % 27;
        code->payload[i] = v1;
        r += a1 + mult_lo(r, 0x75344393) + 0x92438937;
        a3 = mult_lo(a3 + v1, 0x34985343) + 0x64358931;
    }

    code->residual = r;
}

int validate(const code_t *code) {
    u32 r = code->residual;
    if (code->name[11] != r % 27) return 0;
    r /= 27;
    if (code->name[12] != r % 27) return 0;
    return 1;
}

void print_code(const code_t *code) {
    for (int i = 0; i < 13; i++) {
        char c = code->name[i];
        c = c == 26 ? ' ' : c + 'A';
        printf("%c", c);
    }

    printf(" -> ");

    for (int i = 0; i < 11; i++) {
        char c = code->payload[i];
        c = c == 26 ? ' ' : c + 'A';
        printf("%c", c);
    }

    printf("\n");
    fflush(stdout);
}

int validate_entry(const char *entry) {
    code_t code = {0};
    for (int i = 0; i < 13; i++) {
        code.name[i] = entry[i];
        if (entry[i] == '\0') break;
    }

    translate(code.name);
    decode(&code);
    int result = validate(&code);
    if (result) print_code(&code);

    // DEBUG:
    //if (result) printf("%s\n", entry);
    //for (i = 0; i < 13; i++) printf(" %02X", code.name[i]); printf("\n");
    //for (i = 0; i < 11; i++) printf(" %02X", code.payload[i]); printf("\n");

    return result;
}

int bruteforce(int count) {
    /*  with a fixed seed, this is useful for testing.
        the first 10 results should be:
AQPIEOJSFIMJE
JHVBASITTCRQR
RXCUCODXHPAIS
GEXEPVFQBBWZN
EZRTHUSHOWHYG
LBSXAAOTMSUXV
WCDKPNSEWDKAF
NJVIYIYNRWZJQ
RVGLKPYDWYCIA
CEIQQHURYAJAV
    */

    int found = 0;
    code_t code = {0};
    while (found < count) {
        for (int j = 0; j < 13; j++) code.name[j] = prng() % 27;
        //for (int j = 3; j < 13; j++) code.name[j] = 26;
        decode(&code);
        if (validate(&code)) {
            found++;
            print_code(&code);
        }
    }
    return 1;
}

int main(int argc, char **argv) {
    if (argc == 1) {
        // self-test. only one code was known prior, so...
        if (!validate_entry("TYR")) return 1;
        return 0;
    }

    int invalid_count = 0;
    for (int i = 1; i < argc; i++) {
        const char *arg = argv[i];
        if (!strcmp(arg, "bruteforce")) {
            invalid_count += !bruteforce(10);
        } else {
            invalid_count += !validate_entry(arg);
        }
    }
    return !!invalid_count;
}