Problem 244
Sliding block puzzle: sum of checksums of shortest paths.
View problem on Project Euler
Performance comparison
| Metric | Our solution | Best known |
|---|
| Time complexity | O(n^2) | O(n!) |
|---|
| Space complexity | O(n^2) | O(n!) |
|---|
| Approach | Flow solution | BFS or A* search |
|---|
| Verdict | Optimal |
|---|
Flow source
# Project Euler 244
# Sliding block puzzle: sum of checksums of shortest paths.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 100000007
const CAP: i64 = 262144
function encode(cells: ptr<i32>) -> i64 {
let mut v: i64 = 0
let mut i: i32 = 0
while i < 16 {
v = v | ((cells[i] as i64) << (2 * i))
i = i + 1
}
return v
}
function decode(state: i64, cells: ptr<i32>) -> void {
let mut i: i32 = 0
while i < 16 {
cells[i] = ((state >> (2 * i)) & 3) as i32
i = i + 1
}
}
function main() -> i32 {
let KEYS: ptr<i64> = calloc(CAP, 8)
let SEEN: ptr<i8> = calloc(CAP, 1)
let Q: ptr<i64> = calloc(CAP, 8)
let QC: ptr<i64> = calloc(CAP, 8)
let cells: ptr<i32> = calloc(16, 4)
let ncells: ptr<i32> = calloc(16, 4)
if KEYS == null || Q == null { return 1 }
let start_s: ptr<i8> = ".rbbrrbbrrbbrrbb"
let goal_s: ptr<i8> = ".brbbrbrrbrbbrbr"
let mut i: i32 = 0
while i < 16 {
let c: i32 = start_s[i] as i32
match c {
46 => { cells[i] = 0 }
114 => { cells[i] = 1 }
_ => { cells[i] = 2 }
}
i = i + 1
}
let start: i64 = encode(cells)
i = 0
while i < 16 {
let c: i32 = goal_s[i] as i32
match c {
46 => { cells[i] = 0 }
114 => { cells[i] = 1 }
_ => { cells[i] = 2 }
}
i = i + 1
}
let goal: i64 = encode(cells)
# hash insert start
let mut h: i64 = start % CAP
if h < 0 { h = 0 - h }
SEEN[h] = 1
KEYS[h] = start
Q[0] = start
QC[0] = 0
let mut qh: i64 = 0
let mut qt: i64 = 1
let mut result: i64 = 0
let mut last_iter: bool = false
while !last_iter {
let layer_end: i64 = qt
let mut next_start: i64 = qt
while qh < layer_end {
let state: i64 = Q[qh]
let checksum: i64 = QC[qh]
qh = qh + 1
if state == goal {
last_iter = true
result = (result + checksum) % MOD
}
decode(state, cells)
let mut emp: i32 = 0
while emp < 16 {
if cells[emp] == 0 { break }
emp = emp + 1
}
let ex: i32 = emp % 4
let ey: i32 = emp / 4
let mut mi: i32 = 0
while mi < 4 {
let mut move: i32 = 0
let mut tx: i32 = ex
let mut ty: i32 = ey
let mut ok: bool = true
match mi {
0 => { move = 76; if ex == 3 { ok = false } else { tx = ex + 1 } }
1 => { move = 82; if ex == 0 { ok = false } else { tx = ex - 1 } }
2 => { move = 85; if ey == 3 { ok = false } else { ty = ey + 1 } }
_ => { move = 68; if ey == 0 { ok = false } else { ty = ey - 1 } }
}
if ok {
let ti: i32 = ty * 4 + tx
let mut j: i32 = 0
while j < 16 {
ncells[j] = cells[j]
j = j + 1
}
ncells[emp] = cells[ti]
ncells[ti] = 0
let ns: i64 = encode(ncells)
let ncs: i64 = (checksum * 243 + (move as i64)) % MOD
h = ns % CAP
if h < 0 { h = 0 - h }
let mut inserted: bool = false
while true {
if SEEN[h] == 0 {
SEEN[h] = 1
KEYS[h] = ns
inserted = true
break
}
if KEYS[h] == ns { break }
h = h + 1
if h >= CAP { h = 0 }
}
if inserted {
Q[qt] = ns
QC[qt] = ncs
qt = qt + 1
}
}
mi = mi + 1
}
}
if last_iter { break }
if qh >= qt { break }
}
printf("%lld\n", result)
free(KEYS); free(SEEN); free(Q); free(QC); free(cells); free(ncells)
return 0
}
Generated C
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Flow runtime helpers */
typedef struct flow_temp_node { struct flow_temp_node* next; } flow_temp_node;
static flow_temp_node* flow_temp_head = NULL;
static int flow_temp_atexit_set = 0;
__attribute__((unused)) static void flow_temp_free_all(void) {
while (flow_temp_head) {
flow_temp_node* n = flow_temp_head;
flow_temp_head = n->next;
free(n);
}
}
__attribute__((unused)) static void* flow_temp_alloc(size_t nbytes) {
flow_temp_node* node = (flow_temp_node*)malloc(sizeof(flow_temp_node) + nbytes);
if (!node) return NULL;
node->next = flow_temp_head;
flow_temp_head = node;
if (!flow_temp_atexit_set) {
flow_temp_atexit_set = 1;
atexit(flow_temp_free_all);
}
return (void*)(node + 1);
}
#ifndef FLOW_DIAG
#define FLOW_DIAG(msg) fprintf(stderr, "%s", (msg))
#endif
#ifndef FLOW_LOG
#define FLOW_LOG(fmt, ...) printf(fmt, __VA_ARGS__)
#endif
#ifndef FLOW_LOG_EMPTY
#define FLOW_LOG_EMPTY(fmt) printf(fmt)
#endif
static char* flow_strcat(const char* a, const char* b) {
size_t la = strlen(a ? a : ""), lb = strlen(b ? b : "");
char* r = (char*)flow_temp_alloc(la + lb + 1);
if (!r) return NULL;
if (la) memcpy(r, a, la);
if (lb) memcpy(r + la, b, lb);
r[la + lb] = '\0';
return r;
}
#define __flow_in_arr(arr, val) __extension__ ({ \
int _found = 0; \
size_t _n = sizeof(arr)/sizeof((arr)[0]); \
for (size_t _i = 0; _i < _n; _i++) { \
if ((arr)[_i] == (val)) { _found = 1; break; } \
} _found; })
/* Unified fault handler (MISRA #279) — override with -DFLOW_FAULT_HANDLER=fn */
#ifndef FLOW_FAULT_HANDLER
__attribute__((unused)) static inline void flow_fault_handler(const char* msg) {
fprintf(stderr, "flow: %s\n", msg ? msg : "fault");
abort();
#if defined(__GNUC__) || defined(__clang__)
__builtin_unreachable();
#endif
}
#else
#define flow_fault_handler FLOW_FAULT_HANDLER
#endif
#define flow_div_by_zero_handler() flow_fault_handler("division by zero")
#define flow_shift_ub_handler() flow_fault_handler("invalid shift (amount out of range or left-shift of negative)")
#ifndef FLOW_CHECKED_DIV
#define FLOW_CHECKED_DIV(L, R) (((R) != 0) ? ((L) / (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_MOD
#define FLOW_CHECKED_MOD(L, R) (((R) != 0) ? ((L) % (R)) : (flow_div_by_zero_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHL
#define FLOW_CHECKED_SHL(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull)) && ((L) >= 0)) ? ((L) << (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#ifndef FLOW_CHECKED_SHR
#define FLOW_CHECKED_SHR(L, R) ((((R) >= 0) && ((unsigned long long)(R) < (sizeof(L) * 8ull))) ? ((L) >> (R)) : (flow_shift_ub_handler(), (L) * 0))
#endif
#include <math.h>
void* _ui_state = NULL;
static inline float i32_to_f32(int32_t v) { return (float)v; }
/* Host stub for @gpu kernels (device codegen replaces this). */
static inline int32_t gpu_thread_id(void) { return 0; }
int64_t encode_ptr_i32(int32_t* cells);
void decode_i64_ptr_i32(int64_t state, int32_t* cells);
int32_t main(void);
static const int64_t MOD = 100000007;
static const int64_t CAP = 262144;
int64_t encode_ptr_i32(int32_t* cells) {
int64_t v = 0;
int32_t i = 0;
while (i < 16) {
v = (v | FLOW_CHECKED_SHL((((int64_t)(cells[i]))), ((2 * i))));
i = (i + 1);
}
return v;
}
void decode_i64_ptr_i32(int64_t state, int32_t* cells) {
int32_t i = 0;
while (i < 16) {
cells[i] = ((int32_t)((FLOW_CHECKED_SHR((state), ((2 * i))) & 3)));
i = (i + 1);
}
}
int32_t main(void) {
int64_t* KEYS = (int64_t*)(calloc(CAP, 8));
int8_t* SEEN = (int8_t*)(calloc(CAP, 1));
int64_t* Q = (int64_t*)(calloc(CAP, 8));
int64_t* QC = (int64_t*)(calloc(CAP, 8));
int32_t* cells = (int32_t*)(calloc(16, 4));
int32_t* ncells = (int32_t*)(calloc(16, 4));
if ((KEYS == NULL || Q == NULL)) {
return 1;
}
int8_t* start_s = (int8_t*)(".rbbrrbbrrbbrrbb");
int8_t* goal_s = (int8_t*)(".brbbrbrrbrbbrbr");
int32_t i = 0;
while (i < 16) {
int32_t c = ((int32_t)(start_s[i]));
{ // match block
if ((c) == 46) {
cells[i] = 0;
} else if ((c) == 114) {
cells[i] = 1;
} else { // exhaustive
cells[i] = 2;
}
} // end match
i = (i + 1);
}
int64_t start = encode_ptr_i32(cells);
i = 0;
while (i < 16) {
int32_t c = ((int32_t)(goal_s[i]));
{ // match block
if ((c) == 46) {
cells[i] = 0;
} else if ((c) == 114) {
cells[i] = 1;
} else { // exhaustive
cells[i] = 2;
}
} // end match
i = (i + 1);
}
int64_t goal = encode_ptr_i32(cells);
int64_t h = FLOW_CHECKED_MOD((start), (CAP));
if (h < 0) {
h = (0 - h);
}
SEEN[h] = 1;
KEYS[h] = start;
Q[0] = start;
QC[0] = 0;
int64_t qh = 0;
int64_t qt = 1;
int64_t result = 0;
bool last_iter = 0;
while ((!(last_iter))) {
int64_t layer_end = qt;
int64_t next_start = qt;
while (qh < layer_end) {
int64_t state = Q[qh];
int64_t checksum = QC[qh];
qh = (qh + 1);
if (state == goal) {
last_iter = 1;
result = FLOW_CHECKED_MOD(((result + checksum)), (MOD));
}
decode_i64_ptr_i32(state, cells);
int32_t emp = 0;
while (emp < 16) {
if (cells[emp] == 0) {
break;
}
emp = (emp + 1);
}
int32_t ex = FLOW_CHECKED_MOD((emp), (4));
int32_t ey = FLOW_CHECKED_DIV((emp), (4));
int32_t mi = 0;
while (mi < 4) {
int32_t move = 0;
int32_t tx = ex;
int32_t ty = ey;
bool ok = 1;
{ // match block
if ((mi) == 0) {
move = 76;
if (ex == 3) {
ok = 0;
} else {
tx = (ex + 1);
}
} else if ((mi) == 1) {
move = 82;
if (ex == 0) {
ok = 0;
} else {
tx = (ex - 1);
}
} else if ((mi) == 2) {
move = 85;
if (ey == 3) {
ok = 0;
} else {
ty = (ey + 1);
}
} else { // exhaustive
move = 68;
if (ey == 0) {
ok = 0;
} else {
ty = (ey - 1);
}
}
} // end match
if (ok) {
int32_t ti = ((ty * 4) + tx);
int32_t j = 0;
while (j < 16) {
ncells[j] = cells[j];
j = (j + 1);
}
ncells[emp] = cells[ti];
ncells[ti] = 0;
int64_t ns = encode_ptr_i32(ncells);
int64_t ncs = FLOW_CHECKED_MOD((((checksum * 243) + ((int64_t)(move)))), (MOD));
h = FLOW_CHECKED_MOD((ns), (CAP));
if (h < 0) {
h = (0 - h);
}
bool inserted = 0;
while (1) {
if (SEEN[h] == 0) {
SEEN[h] = 1;
KEYS[h] = ns;
inserted = 1;
break;
}
if (KEYS[h] == ns) {
break;
}
h = (h + 1);
if (h >= CAP) {
h = 0;
}
}
if (inserted) {
Q[qt] = ns;
QC[qt] = ncs;
qt = (qt + 1);
}
}
mi = (mi + 1);
}
}
if (last_iter) {
break;
}
if (qh >= qt) {
break;
}
}
printf("%lld\n", result);
free(KEYS);
free(SEEN);
free(Q);
free(QC);
free(cells);
free(ncells);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0(".rbbrrbbrrbbrrbb\00") {addr_space = 0 : i32} : !llvm.array<17 x i8>
llvm.mlir.global internal constant @str_1(".brbbrbrrbrbbrbr\00") {addr_space = 0 : i32} : !llvm.array<17 x i8>
llvm.mlir.global internal constant @str_2("%lld\n\00") {addr_space = 0 : i32} : !llvm.array<6 x i8>
func.func private @calloc(i64, i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(100000007 : i64) : i64
// Constant: CAP
llvm.mlir.global internal constant @CAP(262144 : i64) : i64
func.func @encode(%arg0: !llvm.ptr) -> i64 {
%0 = arith.constant 0 : i32
%1 = arith.extsi %0 : i32 to i64
%2 = llvm.mlir.constant(1 : i64) : i64
%3 = llvm.alloca %2 x i64 : (i64) -> !llvm.ptr
llvm.store %1, %3 : i64, !llvm.ptr
%4 = arith.constant 0 : i32
%5 = llvm.mlir.constant(1 : i64) : i64
%6 = llvm.alloca %5 x i32 : (i64) -> !llvm.ptr
llvm.store %4, %6 : i32, !llvm.ptr
cf.br ^bb0
^bb0:
%7 = llvm.load %6 : !llvm.ptr -> i32
%8 = arith.constant 16 : i32
%9 = arith.cmpi slt, %7, %8 : i32
cf.cond_br %9, ^bb1, ^bb2
^bb1:
%10 = llvm.load %3 : !llvm.ptr -> i64
%12 = llvm.load %6 : !llvm.ptr -> i32
%13 = arith.extsi %12 : i32 to i64
%14 = llvm.getelementptr %arg0[%13] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%11 = llvm.load %14 : !llvm.ptr -> i32
%15 = arith.extsi %11 : i32 to i64
%16 = arith.constant 2 : i32
%17 = llvm.load %6 : !llvm.ptr -> i32
%18 = arith.muli %16, %17 : i32
%20 = arith.extsi %18 : i32 to i64
%19 = arith.shli %15, %20 : i64
%21 = arith.ori %10, %19 : i64
llvm.store %21, %3 : i64, !llvm.ptr
%22 = llvm.load %6 : !llvm.ptr -> i32
%23 = arith.constant 1 : i32
%24 = arith.addi %22, %23 : i32
llvm.store %24, %6 : i32, !llvm.ptr
cf.br ^bb0
^bb2:
%25 = llvm.load %3 : !llvm.ptr -> i64
func.return %25 : i64
}
func.func @decode(%arg0: i64, %arg1: !llvm.ptr) -> () {
%26 = arith.constant 0 : i32
%27 = llvm.mlir.constant(1 : i64) : i64
%28 = llvm.alloca %27 x i32 : (i64) -> !llvm.ptr
llvm.store %26, %28 : i32, !llvm.ptr
cf.br ^bb3
^bb3:
%29 = llvm.load %28 : !llvm.ptr -> i32
%30 = arith.constant 16 : i32
%31 = arith.cmpi slt, %29, %30 : i32
cf.cond_br %31, ^bb4, ^bb5
^bb4:
%32 = arith.constant 2 : i32
%33 = llvm.load %28 : !llvm.ptr -> i32
%34 = arith.muli %32, %33 : i32
%36 = arith.extsi %34 : i32 to i64
%35 = arith.shrsi %arg0, %36 : i64
%37 = arith.constant 3 : i32
%39 = arith.extsi %37 : i32 to i64
%38 = arith.andi %35, %39 : i64
%40 = arith.trunci %38 : i64 to i32
%41 = llvm.load %28 : !llvm.ptr -> i32
%42 = arith.extsi %41 : i32 to i64
%43 = llvm.getelementptr %arg1[%42] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %40, %43 : i32, !llvm.ptr
%44 = llvm.load %28 : !llvm.ptr -> i32
%45 = arith.constant 1 : i32
%46 = arith.addi %44, %45 : i32
llvm.store %46, %28 : i32, !llvm.ptr
cf.br ^bb3
^bb5:
func.return
}
func.func @main() -> i32 {
%48 = llvm.mlir.addressof @CAP : !llvm.ptr
%49 = llvm.load %48 : !llvm.ptr -> i64
%50 = arith.constant 8 : i32
%51 = arith.extsi %50 : i32 to i64
%47 = func.call @calloc(%49, %51) : (i64, i64) -> !llvm.ptr
%53 = llvm.mlir.addressof @CAP : !llvm.ptr
%54 = llvm.load %53 : !llvm.ptr -> i64
%55 = arith.constant 1 : i32
%56 = arith.extsi %55 : i32 to i64
%52 = func.call @calloc(%54, %56) : (i64, i64) -> !llvm.ptr
%58 = llvm.mlir.addressof @CAP : !llvm.ptr
%59 = llvm.load %58 : !llvm.ptr -> i64
%60 = arith.constant 8 : i32
%61 = arith.extsi %60 : i32 to i64
%57 = func.call @calloc(%59, %61) : (i64, i64) -> !llvm.ptr
%63 = llvm.mlir.addressof @CAP : !llvm.ptr
%64 = llvm.load %63 : !llvm.ptr -> i64
%65 = arith.constant 8 : i32
%66 = arith.extsi %65 : i32 to i64
%62 = func.call @calloc(%64, %66) : (i64, i64) -> !llvm.ptr
%68 = arith.constant 16 : i32
%69 = arith.constant 4 : i32
%70 = arith.extsi %68 : i32 to i64
%71 = arith.extsi %69 : i32 to i64
%67 = func.call @calloc(%70, %71) : (i64, i64) -> !llvm.ptr
%73 = arith.constant 16 : i32
%74 = arith.constant 4 : i32
%75 = arith.extsi %73 : i32 to i64
%76 = arith.extsi %74 : i32 to i64
%72 = func.call @calloc(%75, %76) : (i64, i64) -> !llvm.ptr
%77 = llvm.mlir.zero : !llvm.ptr
%78 = llvm.icmp "eq" %47, %77 : !llvm.ptr
%79 = scf.if %78 -> (i1) {
%80 = arith.constant true
scf.yield %80 : i1
} else {
%81 = llvm.mlir.zero : !llvm.ptr
%82 = llvm.icmp "eq" %57, %81 : !llvm.ptr
scf.yield %82 : i1
}
cf.cond_br %79, ^bb6, ^bb7
^bb6:
%83 = arith.constant 1 : i32
func.return %83 : i32
^bb7:
cf.br ^bb8
^bb8:
%84 = llvm.mlir.addressof @str_0 : !llvm.ptr
%85 = llvm.mlir.addressof @str_1 : !llvm.ptr
%86 = arith.constant 0 : i32
%87 = llvm.mlir.constant(1 : i64) : i64
%88 = llvm.alloca %87 x i32 : (i64) -> !llvm.ptr
llvm.store %86, %88 : i32, !llvm.ptr
cf.br ^bb9
^bb9:
%89 = llvm.load %88 : !llvm.ptr -> i32
%90 = arith.constant 16 : i32
%91 = arith.cmpi slt, %89, %90 : i32
cf.cond_br %91, ^bb10, ^bb11
^bb10:
%93 = llvm.load %88 : !llvm.ptr -> i32
%94 = arith.extsi %93 : i32 to i64
%95 = llvm.getelementptr %84[%94] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%92 = llvm.load %95 : !llvm.ptr -> i8
%96 = arith.extsi %92 : i8 to i32
%97 = arith.constant 46 : i32
%98 = arith.cmpi eq, %96, %97 : i32
cf.cond_br %98, ^bb12, ^bb13
^bb12:
%99 = arith.constant 0 : i32
%100 = llvm.load %88 : !llvm.ptr -> i32
%101 = arith.extsi %100 : i32 to i64
%102 = llvm.getelementptr %67[%101] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %99, %102 : i32, !llvm.ptr
cf.br ^bb18
^bb13:
%103 = arith.constant 114 : i32
%104 = arith.cmpi eq, %96, %103 : i32
cf.cond_br %104, ^bb14, ^bb15
^bb14:
%105 = arith.constant 1 : i32
%106 = llvm.load %88 : !llvm.ptr -> i32
%107 = arith.extsi %106 : i32 to i64
%108 = llvm.getelementptr %67[%107] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %105, %108 : i32, !llvm.ptr
cf.br ^bb18
^bb15:
%109 = arith.constant 1 : i1
cf.cond_br %109, ^bb16, ^bb17
^bb16:
%110 = arith.constant 2 : i32
%111 = llvm.load %88 : !llvm.ptr -> i32
%112 = arith.extsi %111 : i32 to i64
%113 = llvm.getelementptr %67[%112] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %110, %113 : i32, !llvm.ptr
cf.br ^bb18
^bb17:
cf.br ^bb18
^bb18:
%114 = llvm.load %88 : !llvm.ptr -> i32
%115 = arith.constant 1 : i32
%116 = arith.addi %114, %115 : i32
llvm.store %116, %88 : i32, !llvm.ptr
cf.br ^bb9
^bb11:
%117 = func.call @encode(%67) : (!llvm.ptr) -> i64
%118 = arith.constant 0 : i32
llvm.store %118, %88 : i32, !llvm.ptr
cf.br ^bb19
^bb19:
%119 = llvm.load %88 : !llvm.ptr -> i32
%120 = arith.constant 16 : i32
%121 = arith.cmpi slt, %119, %120 : i32
cf.cond_br %121, ^bb20, ^bb21
^bb20:
%123 = llvm.load %88 : !llvm.ptr -> i32
%124 = arith.extsi %123 : i32 to i64
%125 = llvm.getelementptr %85[%124] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%122 = llvm.load %125 : !llvm.ptr -> i8
%126 = arith.extsi %122 : i8 to i32
%127 = arith.constant 46 : i32
%128 = arith.cmpi eq, %126, %127 : i32
cf.cond_br %128, ^bb22, ^bb23
^bb22:
%129 = arith.constant 0 : i32
%130 = llvm.load %88 : !llvm.ptr -> i32
%131 = arith.extsi %130 : i32 to i64
%132 = llvm.getelementptr %67[%131] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %129, %132 : i32, !llvm.ptr
cf.br ^bb28
^bb23:
%133 = arith.constant 114 : i32
%134 = arith.cmpi eq, %126, %133 : i32
cf.cond_br %134, ^bb24, ^bb25
^bb24:
%135 = arith.constant 1 : i32
%136 = llvm.load %88 : !llvm.ptr -> i32
%137 = arith.extsi %136 : i32 to i64
%138 = llvm.getelementptr %67[%137] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %135, %138 : i32, !llvm.ptr
cf.br ^bb28
^bb25:
%139 = arith.constant 1 : i1
cf.cond_br %139, ^bb26, ^bb27
^bb26:
%140 = arith.constant 2 : i32
%141 = llvm.load %88 : !llvm.ptr -> i32
%142 = arith.extsi %141 : i32 to i64
%143 = llvm.getelementptr %67[%142] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %140, %143 : i32, !llvm.ptr
cf.br ^bb28
^bb27:
cf.br ^bb28
^bb28:
%144 = llvm.load %88 : !llvm.ptr -> i32
%145 = arith.constant 1 : i32
%146 = arith.addi %144, %145 : i32
llvm.store %146, %88 : i32, !llvm.ptr
cf.br ^bb19
^bb21:
%147 = func.call @encode(%67) : (!llvm.ptr) -> i64
%148 = llvm.mlir.addressof @CAP : !llvm.ptr
%149 = llvm.load %148 : !llvm.ptr -> i64
%150 = arith.remsi %117, %149 : i64
%151 = llvm.mlir.constant(1 : i64) : i64
%152 = llvm.alloca %151 x i64 : (i64) -> !llvm.ptr
llvm.store %150, %152 : i64, !llvm.ptr
%153 = llvm.load %152 : !llvm.ptr -> i64
%154 = arith.constant 0 : i32
%156 = arith.extsi %154 : i32 to i64
%155 = arith.cmpi slt, %153, %156 : i64
cf.cond_br %155, ^bb29, ^bb30
^bb29:
%157 = arith.constant 0 : i32
%158 = llvm.load %152 : !llvm.ptr -> i64
%160 = arith.extsi %157 : i32 to i64
%159 = arith.subi %160, %158 : i64
llvm.store %159, %152 : i64, !llvm.ptr
cf.br ^bb31
^bb30:
cf.br ^bb31
^bb31:
%161 = arith.constant 1 : i32
%162 = llvm.load %152 : !llvm.ptr -> i64
%163 = arith.trunci %161 : i32 to i8
%164 = llvm.getelementptr %52[%162] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %163, %164 : i8, !llvm.ptr
%165 = llvm.load %152 : !llvm.ptr -> i64
%166 = llvm.getelementptr %47[%165] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %117, %166 : i64, !llvm.ptr
%167 = arith.constant 0 : i32
%168 = arith.extsi %167 : i32 to i64
%169 = llvm.getelementptr %57[%168] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %117, %169 : i64, !llvm.ptr
%170 = arith.constant 0 : i32
%171 = arith.constant 0 : i32
%172 = arith.extsi %170 : i32 to i64
%173 = arith.extsi %171 : i32 to i64
%174 = llvm.getelementptr %62[%173] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %172, %174 : i64, !llvm.ptr
%175 = arith.constant 0 : i32
%176 = arith.extsi %175 : i32 to i64
%177 = llvm.mlir.constant(1 : i64) : i64
%178 = llvm.alloca %177 x i64 : (i64) -> !llvm.ptr
llvm.store %176, %178 : i64, !llvm.ptr
%179 = arith.constant 1 : i32
%180 = arith.extsi %179 : i32 to i64
%181 = llvm.mlir.constant(1 : i64) : i64
%182 = llvm.alloca %181 x i64 : (i64) -> !llvm.ptr
llvm.store %180, %182 : i64, !llvm.ptr
%183 = arith.constant 0 : i32
%184 = arith.extsi %183 : i32 to i64
%185 = llvm.mlir.constant(1 : i64) : i64
%186 = llvm.alloca %185 x i64 : (i64) -> !llvm.ptr
llvm.store %184, %186 : i64, !llvm.ptr
%187 = arith.constant 0 : i1
%188 = llvm.mlir.constant(1 : i64) : i64
%189 = llvm.alloca %188 x i1 : (i64) -> !llvm.ptr
llvm.store %187, %189 : i1, !llvm.ptr
cf.br ^bb32
^bb32:
%190 = llvm.load %189 : !llvm.ptr -> i1
%192 = arith.constant 1 : i1
%191 = arith.xori %190, %192 : i1
cf.cond_br %191, ^bb33, ^bb34
^bb33:
%194 = llvm.load %182 : !llvm.ptr -> i64
%195 = llvm.load %182 : !llvm.ptr -> i64
%196 = llvm.mlir.constant(1 : i64) : i64
%197 = llvm.alloca %196 x i64 : (i64) -> !llvm.ptr
llvm.store %195, %197 : i64, !llvm.ptr
cf.br ^bb35
^bb35:
%198 = llvm.load %178 : !llvm.ptr -> i64
%199 = arith.cmpi slt, %198, %194 : i64
cf.cond_br %199, ^bb36, ^bb37
^bb36:
%201 = llvm.load %178 : !llvm.ptr -> i64
%202 = llvm.getelementptr %57[%201] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%200 = llvm.load %202 : !llvm.ptr -> i64
%204 = llvm.load %178 : !llvm.ptr -> i64
%205 = llvm.getelementptr %62[%204] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%203 = llvm.load %205 : !llvm.ptr -> i64
%206 = llvm.load %178 : !llvm.ptr -> i64
%207 = arith.constant 1 : i32
%209 = arith.extsi %207 : i32 to i64
%208 = arith.addi %206, %209 : i64
llvm.store %208, %178 : i64, !llvm.ptr
%210 = arith.cmpi eq, %200, %147 : i64
cf.cond_br %210, ^bb38, ^bb39
^bb38:
%211 = arith.constant 1 : i1
llvm.store %211, %189 : i1, !llvm.ptr
%212 = llvm.load %186 : !llvm.ptr -> i64
%213 = arith.addi %212, %203 : i64
%214 = llvm.mlir.addressof @MOD : !llvm.ptr
%215 = llvm.load %214 : !llvm.ptr -> i64
%216 = arith.remsi %213, %215 : i64
llvm.store %216, %186 : i64, !llvm.ptr
cf.br ^bb40
^bb39:
cf.br ^bb40
^bb40:
func.call @decode(%200, %67) : (i64, !llvm.ptr) -> ()
%218 = arith.constant 0 : i32
%219 = llvm.mlir.constant(1 : i64) : i64
%220 = llvm.alloca %219 x i32 : (i64) -> !llvm.ptr
llvm.store %218, %220 : i32, !llvm.ptr
cf.br ^bb41
^bb41:
%221 = llvm.load %220 : !llvm.ptr -> i32
%222 = arith.constant 16 : i32
%223 = arith.cmpi slt, %221, %222 : i32
cf.cond_br %223, ^bb42, ^bb43
^bb42:
%225 = llvm.load %220 : !llvm.ptr -> i32
%226 = arith.extsi %225 : i32 to i64
%227 = llvm.getelementptr %67[%226] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%224 = llvm.load %227 : !llvm.ptr -> i32
%228 = arith.constant 0 : i32
%229 = arith.cmpi eq, %224, %228 : i32
cf.cond_br %229, ^bb44, ^bb45
^bb44:
cf.br ^bb43
^bb45:
cf.br ^bb46
^bb46:
%230 = llvm.load %220 : !llvm.ptr -> i32
%231 = arith.constant 1 : i32
%232 = arith.addi %230, %231 : i32
llvm.store %232, %220 : i32, !llvm.ptr
cf.br ^bb41
^bb43:
%233 = llvm.load %220 : !llvm.ptr -> i32
%234 = arith.constant 4 : i32
%235 = arith.remsi %233, %234 : i32
%236 = llvm.load %220 : !llvm.ptr -> i32
%237 = arith.constant 4 : i32
%238 = arith.divsi %236, %237 : i32
%239 = arith.constant 0 : i32
%240 = llvm.mlir.constant(1 : i64) : i64
%241 = llvm.alloca %240 x i32 : (i64) -> !llvm.ptr
llvm.store %239, %241 : i32, !llvm.ptr
cf.br ^bb47
^bb47:
%242 = llvm.load %241 : !llvm.ptr -> i32
%243 = arith.constant 4 : i32
%244 = arith.cmpi slt, %242, %243 : i32
cf.cond_br %244, ^bb48, ^bb49
^bb48:
%245 = arith.constant 0 : i32
%246 = llvm.mlir.constant(1 : i64) : i64
%247 = llvm.alloca %246 x i32 : (i64) -> !llvm.ptr
llvm.store %245, %247 : i32, !llvm.ptr
%248 = llvm.mlir.constant(1 : i64) : i64
%249 = llvm.alloca %248 x i32 : (i64) -> !llvm.ptr
llvm.store %235, %249 : i32, !llvm.ptr
%250 = llvm.mlir.constant(1 : i64) : i64
%251 = llvm.alloca %250 x i32 : (i64) -> !llvm.ptr
llvm.store %238, %251 : i32, !llvm.ptr
%252 = arith.constant 1 : i1
%253 = llvm.mlir.constant(1 : i64) : i64
%254 = llvm.alloca %253 x i1 : (i64) -> !llvm.ptr
llvm.store %252, %254 : i1, !llvm.ptr
%255 = llvm.load %241 : !llvm.ptr -> i32
%256 = arith.constant 0 : i32
%257 = arith.cmpi eq, %255, %256 : i32
cf.cond_br %257, ^bb50, ^bb51
^bb50:
%258 = arith.constant 76 : i32
llvm.store %258, %247 : i32, !llvm.ptr
%259 = arith.constant 3 : i32
%260 = arith.cmpi eq, %235, %259 : i32
cf.cond_br %260, ^bb59, ^bb60
^bb59:
%261 = arith.constant 0 : i1
llvm.store %261, %254 : i1, !llvm.ptr
cf.br ^bb61
^bb60:
%262 = arith.constant 1 : i32
%263 = arith.addi %235, %262 : i32
llvm.store %263, %249 : i32, !llvm.ptr
cf.br ^bb61
^bb61:
cf.br ^bb58
^bb51:
%264 = arith.constant 1 : i32
%265 = arith.cmpi eq, %255, %264 : i32
cf.cond_br %265, ^bb52, ^bb53
^bb52:
%266 = arith.constant 82 : i32
llvm.store %266, %247 : i32, !llvm.ptr
%267 = arith.constant 0 : i32
%268 = arith.cmpi eq, %235, %267 : i32
cf.cond_br %268, ^bb62, ^bb63
^bb62:
%269 = arith.constant 0 : i1
llvm.store %269, %254 : i1, !llvm.ptr
cf.br ^bb64
^bb63:
%270 = arith.constant 1 : i32
%271 = arith.subi %235, %270 : i32
llvm.store %271, %249 : i32, !llvm.ptr
cf.br ^bb64
^bb64:
cf.br ^bb58
^bb53:
%272 = arith.constant 2 : i32
%273 = arith.cmpi eq, %255, %272 : i32
cf.cond_br %273, ^bb54, ^bb55
^bb54:
%274 = arith.constant 85 : i32
llvm.store %274, %247 : i32, !llvm.ptr
%275 = arith.constant 3 : i32
%276 = arith.cmpi eq, %238, %275 : i32
cf.cond_br %276, ^bb65, ^bb66
^bb65:
%277 = arith.constant 0 : i1
llvm.store %277, %254 : i1, !llvm.ptr
cf.br ^bb67
^bb66:
%278 = arith.constant 1 : i32
%279 = arith.addi %238, %278 : i32
llvm.store %279, %251 : i32, !llvm.ptr
cf.br ^bb67
^bb67:
cf.br ^bb58
^bb55:
%280 = arith.constant 1 : i1
cf.cond_br %280, ^bb56, ^bb57
^bb56:
%281 = arith.constant 68 : i32
llvm.store %281, %247 : i32, !llvm.ptr
%282 = arith.constant 0 : i32
%283 = arith.cmpi eq, %238, %282 : i32
cf.cond_br %283, ^bb68, ^bb69
^bb68:
%284 = arith.constant 0 : i1
llvm.store %284, %254 : i1, !llvm.ptr
cf.br ^bb70
^bb69:
%285 = arith.constant 1 : i32
%286 = arith.subi %238, %285 : i32
llvm.store %286, %251 : i32, !llvm.ptr
cf.br ^bb70
^bb70:
cf.br ^bb58
^bb57:
cf.br ^bb58
^bb58:
%287 = llvm.load %254 : !llvm.ptr -> i1
cf.cond_br %287, ^bb71, ^bb72
^bb71:
%288 = llvm.load %251 : !llvm.ptr -> i32
%289 = arith.constant 4 : i32
%290 = arith.muli %288, %289 : i32
%291 = llvm.load %249 : !llvm.ptr -> i32
%292 = arith.addi %290, %291 : i32
%293 = arith.constant 0 : i32
%294 = llvm.mlir.constant(1 : i64) : i64
%295 = llvm.alloca %294 x i32 : (i64) -> !llvm.ptr
llvm.store %293, %295 : i32, !llvm.ptr
cf.br ^bb74
^bb74:
%296 = llvm.load %295 : !llvm.ptr -> i32
%297 = arith.constant 16 : i32
%298 = arith.cmpi slt, %296, %297 : i32
cf.cond_br %298, ^bb75, ^bb76
^bb75:
%300 = llvm.load %295 : !llvm.ptr -> i32
%301 = arith.extsi %300 : i32 to i64
%302 = llvm.getelementptr %67[%301] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%299 = llvm.load %302 : !llvm.ptr -> i32
%303 = llvm.load %295 : !llvm.ptr -> i32
%304 = arith.extsi %303 : i32 to i64
%305 = llvm.getelementptr %72[%304] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %299, %305 : i32, !llvm.ptr
%306 = llvm.load %295 : !llvm.ptr -> i32
%307 = arith.constant 1 : i32
%308 = arith.addi %306, %307 : i32
llvm.store %308, %295 : i32, !llvm.ptr
cf.br ^bb74
^bb76:
%310 = arith.extsi %292 : i32 to i64
%311 = llvm.getelementptr %67[%310] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%309 = llvm.load %311 : !llvm.ptr -> i32
%312 = llvm.load %220 : !llvm.ptr -> i32
%313 = arith.extsi %312 : i32 to i64
%314 = llvm.getelementptr %72[%313] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %309, %314 : i32, !llvm.ptr
%315 = arith.constant 0 : i32
%316 = arith.extsi %292 : i32 to i64
%317 = llvm.getelementptr %72[%316] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %315, %317 : i32, !llvm.ptr
%318 = func.call @encode(%72) : (!llvm.ptr) -> i64
%319 = arith.constant 243 : i32
%321 = arith.extsi %319 : i32 to i64
%320 = arith.muli %203, %321 : i64
%322 = llvm.load %247 : !llvm.ptr -> i32
%323 = arith.extsi %322 : i32 to i64
%324 = arith.addi %320, %323 : i64
%325 = llvm.mlir.addressof @MOD : !llvm.ptr
%326 = llvm.load %325 : !llvm.ptr -> i64
%327 = arith.remsi %324, %326 : i64
%328 = llvm.mlir.addressof @CAP : !llvm.ptr
%329 = llvm.load %328 : !llvm.ptr -> i64
%330 = arith.remsi %318, %329 : i64
llvm.store %330, %152 : i64, !llvm.ptr
%331 = llvm.load %152 : !llvm.ptr -> i64
%332 = arith.constant 0 : i32
%334 = arith.extsi %332 : i32 to i64
%333 = arith.cmpi slt, %331, %334 : i64
cf.cond_br %333, ^bb77, ^bb78
^bb77:
%335 = arith.constant 0 : i32
%336 = llvm.load %152 : !llvm.ptr -> i64
%338 = arith.extsi %335 : i32 to i64
%337 = arith.subi %338, %336 : i64
llvm.store %337, %152 : i64, !llvm.ptr
cf.br ^bb79
^bb78:
cf.br ^bb79
^bb79:
%339 = arith.constant 0 : i1
%340 = llvm.mlir.constant(1 : i64) : i64
%341 = llvm.alloca %340 x i1 : (i64) -> !llvm.ptr
llvm.store %339, %341 : i1, !llvm.ptr
cf.br ^bb80
^bb80:
%342 = arith.constant 1 : i1
cf.cond_br %342, ^bb81, ^bb82
^bb81:
%344 = llvm.load %152 : !llvm.ptr -> i64
%345 = llvm.getelementptr %52[%344] : (!llvm.ptr, i64) -> !llvm.ptr, i8
%343 = llvm.load %345 : !llvm.ptr -> i8
%346 = arith.constant 0 : i32
%348 = arith.extsi %343 : i8 to i32
%347 = arith.cmpi eq, %348, %346 : i32
cf.cond_br %347, ^bb83, ^bb84
^bb83:
%349 = arith.constant 1 : i32
%350 = llvm.load %152 : !llvm.ptr -> i64
%351 = arith.trunci %349 : i32 to i8
%352 = llvm.getelementptr %52[%350] : (!llvm.ptr, i64) -> !llvm.ptr, i8
llvm.store %351, %352 : i8, !llvm.ptr
%353 = llvm.load %152 : !llvm.ptr -> i64
%354 = llvm.getelementptr %47[%353] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %318, %354 : i64, !llvm.ptr
%355 = arith.constant 1 : i1
llvm.store %355, %341 : i1, !llvm.ptr
cf.br ^bb82
^bb84:
cf.br ^bb85
^bb85:
%357 = llvm.load %152 : !llvm.ptr -> i64
%358 = llvm.getelementptr %47[%357] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%356 = llvm.load %358 : !llvm.ptr -> i64
%359 = arith.cmpi eq, %356, %318 : i64
cf.cond_br %359, ^bb86, ^bb87
^bb86:
cf.br ^bb82
^bb87:
cf.br ^bb88
^bb88:
%360 = llvm.load %152 : !llvm.ptr -> i64
%361 = arith.constant 1 : i32
%363 = arith.extsi %361 : i32 to i64
%362 = arith.addi %360, %363 : i64
llvm.store %362, %152 : i64, !llvm.ptr
%364 = llvm.load %152 : !llvm.ptr -> i64
%365 = llvm.mlir.addressof @CAP : !llvm.ptr
%366 = llvm.load %365 : !llvm.ptr -> i64
%367 = arith.cmpi sge, %364, %366 : i64
cf.cond_br %367, ^bb89, ^bb90
^bb89:
%368 = arith.constant 0 : i32
%369 = arith.extsi %368 : i32 to i64
llvm.store %369, %152 : i64, !llvm.ptr
cf.br ^bb91
^bb90:
cf.br ^bb91
^bb91:
cf.br ^bb80
^bb82:
%370 = llvm.load %341 : !llvm.ptr -> i1
cf.cond_br %370, ^bb92, ^bb93
^bb92:
%371 = llvm.load %182 : !llvm.ptr -> i64
%372 = llvm.getelementptr %57[%371] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %318, %372 : i64, !llvm.ptr
%373 = llvm.load %182 : !llvm.ptr -> i64
%374 = llvm.getelementptr %62[%373] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %327, %374 : i64, !llvm.ptr
%375 = llvm.load %182 : !llvm.ptr -> i64
%376 = arith.constant 1 : i32
%378 = arith.extsi %376 : i32 to i64
%377 = arith.addi %375, %378 : i64
llvm.store %377, %182 : i64, !llvm.ptr
cf.br ^bb94
^bb93:
cf.br ^bb94
^bb94:
cf.br ^bb73
^bb72:
cf.br ^bb73
^bb73:
%379 = llvm.load %241 : !llvm.ptr -> i32
%380 = arith.constant 1 : i32
%381 = arith.addi %379, %380 : i32
llvm.store %381, %241 : i32, !llvm.ptr
cf.br ^bb47
^bb49:
cf.br ^bb35
^bb37:
%382 = llvm.load %189 : !llvm.ptr -> i1
cf.cond_br %382, ^bb95, ^bb96
^bb95:
cf.br ^bb34
^bb96:
cf.br ^bb97
^bb97:
%383 = llvm.load %178 : !llvm.ptr -> i64
%384 = llvm.load %182 : !llvm.ptr -> i64
%385 = arith.cmpi sge, %383, %384 : i64
cf.cond_br %385, ^bb98, ^bb99
^bb98:
cf.br ^bb34
^bb99:
cf.br ^bb100
^bb100:
cf.br ^bb32
^bb34:
%386 = llvm.mlir.addressof @str_2 : !llvm.ptr
%387 = llvm.load %186 : !llvm.ptr -> i64
%388 = llvm.call @printf(%386, %387) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%47) : (!llvm.ptr) -> ()
func.call @free(%52) : (!llvm.ptr) -> ()
func.call @free(%57) : (!llvm.ptr) -> ()
func.call @free(%62) : (!llvm.ptr) -> ()
func.call @free(%67) : (!llvm.ptr) -> ()
func.call @free(%72) : (!llvm.ptr) -> ()
%395 = arith.constant 0 : i32
func.return %395 : i32
}
}