Skip to content

Instantly share code, notes, and snippets.

@sasdf

sasdf/solve.cpp

Last active November 29, 2021 06:18
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sasdf/78fa4f4c9dc9db93534e4742b1de92e1 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sasdf/78fa4f4c9dc9db93534e4742b1de92e1 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sasdf revised this gist Nov 29, 2021. 2 changed files with 2 additions and 2 deletions.
    2 changes: 1 addition & 1 deletion solve.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,7 @@
    // g++ -O3 solve.cpp -fopenmp && ./a.out
    //
    // Credits:
    // Algorithm: @utaha
    // Algorithm: @utaha1228
    // Optimization: @sasdf

    #include "table.h" // Generated by python3 solve.py
    2 changes: 1 addition & 1 deletion solve.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,7 +1,7 @@
    #!/usr/bin/env python3
    #
    # Credits:
    # Algorithm: @utaha
    # Algorithm: @utaha1228
    # Optimization: @sasdf

    import sys
  2. sasdf revised this gist Nov 29, 2021. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion solve.py
    View file
    Original file line number Diff line number Diff line change
    @@ -105,7 +105,7 @@ def main():
    # delta changes the variable from '0' to '0' ~ '9'
    #
    # ascii bin delta repr using basis below
    # A B A-A`|B-B` C
    # A B A-A0|B-B0 C
    # 0: 0000 0000 0000|0000 0000
    # 1: 0001 0001 0001|0001 0001
    # 2: 0010 0010 0010|0010 0010
  3. sasdf created this gist Nov 29, 2021.
    153 changes: 153 additions & 0 deletions solve.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,153 @@
    // g++ -O3 solve.cpp -fopenmp && ./a.out
    //
    // Credits:
    // Algorithm: @utaha
    // Optimization: @sasdf

    #include "table.h" // Generated by python3 solve.py
    #include <omp.h>
    #include <cstdint>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>


    // defined in table.h
    // #define N 16

    #define SIZE (N * 4)
    #define NTHREADS 10


    class LinearBase {
    public:
    __uint128_t lb[SIZE][2];

    LinearBase() {
    memset(this->lb, 0, sizeof(this->lb));
    };

    void add_base(__uint128_t *x) {
    __uint128_t num = x[0], mask = x[1];
    for (int i=SIZE-1; i>=0; i--) {
    if ((num >> i) & 1) {
    if (this->lb[i][0] == 0 && this->lb[i][1] == 0) {
    this->lb[i][0] = num;
    this->lb[i][1] = mask;
    break;
    } else {
    num ^= this->lb[i][0];
    mask ^= this->lb[i][1];
    }
    }
    }
    }

    __uint128_t get_base_rep(__uint128_t num) {
    __uint128_t mask = 0;
    for (int i=SIZE-1; i>=0; i--) {
    if ((num >> i) & 1) {
    if (this->lb[i][1] == 0) {
    return -1;
    }
    num ^= this->lb[i][0];
    mask ^= this->lb[i][1];
    }
    }
    return mask;
    }
    };

    void print128(__uint128_t x){
    fprintf(stderr, "%016llx %016llx\n", (uint64_t)(x >> 64), (uint64_t)(x));
    }

    int main() {
    LinearBase lbcache[NTHREADS][N+1];
    bool cache_initialized[NTHREADS] = {0};

    uint64_t total = 1ULL << N;
    uint64_t report = total / 10000;
    uint64_t progress = 0;
    uint64_t local_progress[NTHREADS] = {0};

    #pragma omp parallel for num_threads(NTHREADS)
    for (uint64_t M=0; M<total; M++) {
    int tidx = omp_get_thread_num();

    local_progress[tidx] ++;
    if (local_progress[tidx] == report) {
    local_progress[tidx] = 0;
    #pragma omp critical
    {
    progress += report;
    fprintf(stderr, "%.2f\r", (double)progress * 100.0 / (double)total);
    }
    }

    LinearBase LB;
    int ii = 0;

    if (cache_initialized[tidx]) {
    int Mdiff = (M - 1) ^ M;
    for (ii=0; ii<N; ii++) {
    int j = N - 1 - ii;
    if ((Mdiff >> j) & 1) { break; }
    }
    LB = lbcache[tidx][ii];
    } else {
    cache_initialized[tidx] = true;
    }

    for (int i=ii; i<N; i++) {
    int j = N - 1 - i;
    if ((M >> j) & 1) {
    for (int z=0; z<4; z++) {
    LB.add_base(numbers[i][z]);
    }
    } else {
    for (int z=0; z<4; z++) {
    LB.add_base(alphabets[i][z]);
    }
    }
    lbcache[tidx][i+1] = LB;
    }

    __uint128_t orig_diff = diff_bias;
    for (int i=0; i<N; i++) {
    if ((M >> i) & 1) {
    orig_diff ^= diffs[i];
    }
    }

    __uint128_t res = LB.get_base_rep(orig_diff);
    // print128(res);
    if (res == -1) { continue; }

    bool ok = true;
    char buf[33];
    memset(buf, 0, 33);
    for (int i=0; i<N; i++) {
    int j = N - 1 - i;
    int d = (res >> (j * 4)) & 0xf;
    if ((M >> i) & 1) {
    if (d < 10) { buf[i] = '0' + d; }
    else { ok = false; break; }
    } else {
    if (d == 4) { buf[i] = 'a'; }
    else if (d == 2) { buf[i] = 'b'; }
    else if (d == 14) { buf[i] = 'c'; }
    else if (d == 1) { buf[i] = 'd'; }
    else if (d == 5) { buf[i] = 'e'; }
    else if (d == 3) { buf[i] = 'f'; }
    else { ok = false; break; }
    }
    }
    if (ok) {
    fprintf(stderr, "\nanswer = %s\n", buf);
    // print128(res);
    }
    }
    fprintf(stderr, "\n");
    return 0;
    }
    277 changes: 277 additions & 0 deletions solve.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,277 @@
    #!/usr/bin/env python3
    #
    # Credits:
    # Algorithm: @utaha
    # Optimization: @sasdf

    import sys
    from tqdm import tqdm


    N = 16 # 16 for warmup, 32 for hard

    # Search range
    start = 0
    end = 1 << N


    def crc128(buf, crc=0xffffffffffffffffffffffffffffffff):
    for val in buf:
    crc ^= val << 120
    for _ in range(8):
    crc <<= 1
    if crc & 2**128:
    crc ^= 0x14caa61b0d7fe5fa54189d46709eaba2d
    return crc


    def crc64(buf, crc=0xffffffffffffffff):
    for val in buf:
    crc ^= val << 56
    for _ in range(8):
    crc <<= 1
    if crc & 2**64:
    crc ^= 0x1ad93d23594c935a9
    return crc


    def getCrc(crc): # a string contains N hex character
    assert len(crc) == N
    assert all((x in '1234567890abcdef`\0') for x in crc)
    if N == 16:
    inp = f'My crc64 is 0x{crc}! Cool, isn\'t it?'.encode()
    return crc64(inp)
    else:
    inp = f'My crc128 is 0x{crc}! Cool, isn\'t it?'.encode()
    return crc128(inp)


    def getDiff(crc):
    return getCrc(crc) ^ int(crc.replace('`', '9'), 16)


    class LinearBase:
    def __init__(self):
    self.SIZE = N * 4
    self.lb = [(-1, -1)] * self.SIZE # (mat, aug)

    def add_base(self, num, mask):
    # Echelonize
    for i in range(self.SIZE - 1, -1, -1):
    if num & (1 << i):
    if self.lb[i] == (-1, -1):
    self.lb[i] = (num, mask)
    break
    else:
    num ^= self.lb[i][0]
    mask ^= self.lb[i][1]

    def get_base_rep(self, num):
    # Solve matrix
    mask = 0
    for i in range(self.SIZE - 1, -1, -1):
    if num & (1 << i):
    if self.lb[i] == (-1, -1):
    return "RIP"
    num ^= self.lb[i][0]
    mask ^= self.lb[i][1]
    return mask


    def multByX(num):
    num <<= 1
    if N == 16:
    if num & (1 << 64):
    num ^= 0x1ad93d23594c935a9
    else:
    if num & (1 << 128):
    num ^= 0x14caa61b0d7fe5fa54189d46709eaba2d
    return num


    def multByXn(num, n):
    for _ in range(n):
    num = multByX(num)
    return num


    def main():
    # Precompute tables

    # LHS
    numbers = []
    alphabets = []
    for i in range(N):
    # delta changes the variable from '0' to '0' ~ '9'
    #
    # ascii bin delta repr using basis below
    # A B A-A`|B-B` C
    # 0: 0000 0000 0000|0000 0000
    # 1: 0001 0001 0001|0001 0001
    # 2: 0010 0010 0010|0010 0010
    # 3: 0011 0011 0011|0011 0011
    # 4: 0100 0100 0100|0100 0100
    # 5: 0101 0101 0101|0101 0101
    # 6: 0110 0110 0110|0110 0110
    # 7: 0111 0111 0111|0111 0111
    # 8: 1000 1000 1000|1000 1000
    # 9: 1001 1001 1001|1001 1001
    #
    # base0 0001|0001 0001
    # base1 0010|0010 0010
    # base2 0100|0100 0100
    # base3 1000|1000 1000

    A = getCrc('0' * N) ^ getCrc(('1' + '0' * i).rjust(N, '0'))
    B = (1 << (i * 4))
    delta = A ^ B
    tmp = []
    for j in range(4):
    tmp.append([delta, 1 << (i * 4 + j)])
    delta = multByX(delta)
    numbers.append(tmp)

    for i in range(N):
    # delta changes the variable from '`' to 'a' ~ 'f'
    #
    # ascii bin delta repr using basis below
    # A B A-A`|B-B` C
    # `: 000 001 000|000 0000
    # a: 001 010 001|011 0100
    # b: 010 011 010|010 0010
    # c: 011 100 011|101 1110
    # d: 100 101 100|100 0001
    # e: 101 110 101|111 0101
    # f: 110 111 110|110 0011
    #
    # base0 100|100 0001
    # base1 010|010 0010
    # base2 001|011 0100
    # base3 000|100 1000

    A = getCrc('`' * N) ^ getCrc('`' * (N - 1 - i) + 'a' + '`' * i)
    B = (1 << (i * 4))
    tmp = [
    [multByXn(A, 2) ^ multByXn(B, 2), (1 << (i * 4 + 0))],
    [multByXn(A, 1) ^ multByXn(B, 1), (1 << (i * 4 + 1))],
    [A ^ B ^ multByXn(B, 1) , (1 << (i * 4 + 2))],
    [multByXn(B, 2) , (1 << (i * 4 + 3))],
    ]
    alphabets.append(tmp)


    # RHS
    diffs = []
    diff_bias = getDiff('`' * N)
    for i in range(N):
    diffs.append(getDiff(('`' * i + '0').ljust(N, '`')) ^ diff_bias)


    # Dump all tables for C++ impl
    with open('table.h', 'w') as f:
    f.write(f'#define N {N}\n')
    f.write(f'const char* _numbers = (\n')
    for a in numbers:
    for b in a:
    for x in b:
    f.write(' "' + ''.join(f'\\x{d:02x}' for d in x.to_bytes(16, 'little')) + '"\n')
    f.write(');\n')
    f.write(f'__uint128_t (*__numbers)[{N}][4][2] = (__uint128_t(*)[{N}][4][2])_numbers;\n')
    f.write(f'#define numbers (*__numbers)\n')

    f.write(f'const char* _alphabets = (\n')
    for a in alphabets:
    for b in a:
    for x in b:
    f.write(' "' + ''.join(f'\\x{d:02x}' for d in x.to_bytes(16, 'little')) + '"\n')
    f.write(');\n')
    f.write(f'__uint128_t (*__alphabets)[{N}][4][2] = (__uint128_t(*)[{N}][4][2])_alphabets;\n')
    f.write(f'#define alphabets (*__alphabets)\n')

    f.write(f'const char* _diffs = (\n')
    for x in diffs:
    f.write(' "' + ''.join(f'\\x{d:02x}' for d in x.to_bytes(16, 'little')) + '"\n')
    f.write(');\n')
    f.write(f'__uint128_t (*__diffs)[{N}] = (__uint128_t(*)[{N}])_diffs;\n')
    f.write(f'#define diffs (*__diffs)\n')

    f.write(f'const char* _diff_bias = (\n')
    x = diff_bias
    f.write(' "' + ''.join(f'\\x{d:02x}' for d in x.to_bytes(16, 'little')) + '"\n')
    f.write(');\n')
    f.write(f'__uint128_t (*__diff_bias) = (__uint128_t*)_diff_bias;\n')
    f.write(f'#define diff_bias (*__diff_bias)\n')


    # Python impl
    # Solve all possible 2^N basis combinations (i.e. numbers or alphabets)

    lbcache = [] # Echelonize basis cache
    for M in tqdm(range(start, end), desc='Solving'):
    LB = LinearBase()

    if len(lbcache) == 0:
    lbcache, ii = [LB.lb[:]], 0
    else:
    # Find the first changed basis
    Mdiff = (M - 1) ^ M
    for ii in range(N):
    j = N - 1 - ii
    if Mdiff & (1 << j):
    break
    # Reuse previous echelonize basis
    LB.lb = lbcache[ii][:]
    lbcache = lbcache[:ii+1]

    # Add basis and echelonize it
    for i in range(ii, N):
    j = N - 1 - i
    if M & (1 << j):
    for num, mask in numbers[i]:
    LB.add_base(num, mask)
    else:
    for num, mask in alphabets[i]:
    LB.add_base(num, mask)
    lbcache.append(LB.lb[:])

    # Prepare RHS
    rhs = diff_bias
    for i in range(N):
    if M & (1 << i):
    rhs ^= diffs[i]

    # Solve the equations ( res @ LB == rhs )
    res = LB.get_base_rep(rhs)
    if res == 'RIP':
    continue

    # Mapping back to hex
    ans = ''
    for i in range(N):
    j = N - 1 - i
    d = (res >> (j * 4)) & 0xf
    if M & (1 << i):
    if d >= 10:
    break
    else:
    ans += str(d)
    else:
    if d == 4:
    ans += 'a'
    elif d == 2:
    ans += 'b'
    elif d == 14:
    ans += 'c'
    elif d == 1:
    ans += 'd'
    elif d == 5:
    ans += 'e'
    elif d == 3:
    ans += 'f'
    else:
    break
    else:
    print(ans)
    # return

    main()