← All problems Problem 803
Pseudorandom Sequence: find the minimum step at which the sequence starting from the "PuzzleOne" seed first produces "LuckyText". Pure Flow port of the native C solver using 48-bit LCG arithmetic.
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 803
# Pseudorandom Sequence: find the minimum step at which the sequence
# starting from the "PuzzleOne" seed first produces "LuckyText".
# Pure Flow port of the native C solver using 48-bit LCG arithmetic.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const A_VAL: i64 = 25214903917
const C_VAL: i64 = 11
const MOD48: i64 = 281474976710656
const MOD24: i64 = 16777216
const MOD18: i64 = 262144
const INV9_MOD13: i32 = 3
const ORDER_EXP: i32 = 46
# Global state for dlog
let mut G_ORDER: i64 = 0
let mut inv_pows: ptr<i64> = null
# Global output for powA_sumY
let mut g_powv: i64 = 0
let mut g_sumv: i64 = 0
function mul48(a: i64, b: i64) -> i64 {
let prod: i128 = (a as i128) * (b as i128)
return (prod % (MOD48 as i128)) as i64
}
function powmod48(base: i64, exp: i64) -> i64 {
let mut result: i64 = 1
let mut b: i64 = base % MOD48
if b < 0 { b = b + MOD48 }
let mut e: i64 = exp
while e > 0 {
if e % 2 == 1 {
result = mul48(result, b)
}
b = mul48(b, b)
e = e / 2
}
return result
}
function invmod48(x0: i64) -> i64 {
let mut x: i64 = x0 % MOD48
if x < 0 { x = x + MOD48 }
let mut inv: i64 = x
let mut i: i32 = 0
while i < 5 {
let t: i64 = mul48(x, inv)
let two_minus: i64 = (MOD48 + 2 - t) % MOD48
inv = mul48(inv, two_minus)
i = i + 1
}
return inv
}
function step48(x: i64) -> i64 {
return (mul48(A_VAL, x) + C_VAL) % MOD48
}
function b_from_a(a: i64) -> i32 {
return ((a >> 16) % 52) as i32
}
function check_prefix(a0: i64, vals: ptr<i32>, L: i32) -> i32 {
let mut a: i64 = a0 % MOD48
if a < 0 { a = a + MOD48 }
let mut i: i32 = 0
while i < L {
if b_from_a(a) != vals[i] { return 0 }
a = step48(a)
i = i + 1
}
return 1
}
function u0_candidates(pattern_vals: ptr<i32>, L: i32, out: ptr<i64>, max_out: i32) -> i32 {
let mut count: i32 = 0
let mut u0: i64 = 0
while u0 < MOD18 {
let mut u: i64 = u0
let mut ok: bool = true
let mut i: i32 = 0
while i < L {
if ((u >> 16) % 4) as i32 != pattern_vals[i] % 4 {
ok = false
break
}
u = (mul48(A_VAL, u) + C_VAL) % MOD18
i = i + 1
}
if ok {
if count < max_out { out[count] = u0 }
count = count + 1
}
u0 = u0 + 1
}
return count
}
function solve_y0(carries24: ptr<i64>, residues13: ptr<i32>, L: i32, out: ptr<i64>, max_out: i32) -> i32 {
if L == 0 { return 0 }
let r0: i32 = residues13[0]
let mut count: i32 = 0
if L == 1 {
let mut y0: i64 = r0 as i64
while y0 < MOD24 {
if count < max_out { out[count] = y0 }
count = count + 1
y0 = y0 + 13
}
return count
}
let r1: i32 = residues13[1]
let a24: i64 = A_VAL % MOD24
if L == 2 {
let y0_init: i64 = r0 as i64
let mut y1: i64 = (mul48(A_VAL, y0_init) + carries24[0]) % MOD24
let delta1: i64 = (13 * a24) % MOD24
let mut y0: i64 = r0 as i64
while y0 < MOD24 {
if y1 % 13 == r1 as i64 {
if count < max_out { out[count] = y0 }
count = count + 1
}
y1 = (y1 + delta1) % MOD24
y0 = y0 + 13
}
return count
}
# L >= 3
let r2: i32 = residues13[2]
let y0_init: i64 = r0 as i64
let mut y1: i64 = (mul48(A_VAL, y0_init) + carries24[0]) % MOD24
let mut y2: i64 = (mul48(A_VAL, y1) + carries24[1]) % MOD24
let delta1: i64 = (13 * a24) % MOD24
let delta2: i64 = mul48(delta1, a24) % MOD24
let mut y0: i64 = r0 as i64
while y0 < MOD24 {
if y1 % 13 == r1 as i64 && y2 % 13 == r2 as i64 {
let mut y: i64 = y2
let mut ok: bool = true
let mut i: i32 = 2
while i < L - 1 {
y = (mul48(A_VAL, y) + carries24[i]) % MOD24
if y % 13 != residues13[i + 1] as i64 {
ok = false
break
}
i = i + 1
}
if ok {
if count < max_out { out[count] = y0 }
count = count + 1
}
}
y1 = (y1 + delta1) % MOD24
y2 = (y2 + delta2) % MOD24
y0 = y0 + 13
}
return count
}
function solve_states(vals: ptr<i32>, L: i32, states_out: ptr<i64>, max_states: i32) -> i32 {
let us: ptr<i64> = calloc(1024, 8)
let n_us: i32 = u0_candidates(vals, L, us, 1024)
let mut n_states: i32 = 0
let u_list: ptr<i64> = calloc(64, 8)
let k_list: ptr<i64> = calloc(64, 8)
let carries24: ptr<i64> = calloc(64, 8)
let t_list: ptr<i32> = calloc(64, 4)
let residues13: ptr<i32> = calloc(64, 4)
let y0s: ptr<i64> = calloc(4096, 8)
let mut ui: i32 = 0
while ui < n_us {
let u0: i64 = us[ui]
let mut u: i64 = u0
let mut i: i32 = 0
while i < L {
u_list[i] = u
let nxt: i64 = A_VAL * u + C_VAL
if i < L - 1 { k_list[i] = nxt >> 18 }
u = nxt % MOD18
i = i + 1
}
let mut w0: i32 = 0
while w0 < 64 {
let mut w: i64 = w0 as i64
let mut i2: i32 = 0
while i2 < L {
t_list[i2] = (((u_list[i2] >> 16) % 4) + w * 4) as i32
if i2 < L - 1 {
carries24[i2] = (k_list[i2] + A_VAL * w) >> 6
w = (A_VAL * w + k_list[i2]) % 64
}
i2 = i2 + 1
}
# Compute residues13
let mut i3: i32 = 0
while i3 < L {
let mut t_mod13: i32 = t_list[i3] % 13
if t_mod13 < 0 { t_mod13 = t_mod13 + 13 }
let mut diff: i32 = (vals[i3] - t_mod13) % 13
if diff < 0 { diff = diff + 13 }
residues13[i3] = (INV9_MOD13 * diff) % 13
i3 = i3 + 1
}
# Solve y0
let n_y0: i32 = solve_y0(carries24, residues13, L, y0s, 4096)
let mut yi: i32 = 0
while yi < n_y0 {
let y0: i64 = y0s[yi]
let x0: i64 = u0 + ((w0 as i64) << 18)
let a0: i64 = x0 + (y0 << 24)
if check_prefix(a0, vals, L) == 1 {
if n_states < max_states { states_out[n_states] = a0 }
n_states = n_states + 1
}
yi = yi + 1
}
w0 = w0 + 1
}
ui = ui + 1
}
free(us)
free(u_list)
free(k_list)
free(carries24)
free(t_list)
free(residues13)
free(y0s)
return n_states
}
function precompute_dlog() -> void {
inv_pows = calloc(ORDER_EXP as i64, 8)
G_ORDER = powmod48(A_VAL, (1 as i64) << (ORDER_EXP - 1))
let mut i: i32 = 0
while i < ORDER_EXP {
let p: i64 = powmod48(A_VAL, (1 as i64) << i)
inv_pows[i] = invmod48(p)
i = i + 1
}
}
function dlog_pow2(h: i64) -> i64 {
let mut x: i64 = 0
let mut cur: i64 = h % MOD48
if cur < 0 { cur = cur + MOD48 }
let mut i: i32 = 0
while i < ORDER_EXP {
let e: i64 = (1 as i64) << (ORDER_EXP - 1 - i)
let t: i64 = powmod48(cur, e)
if t == G_ORDER {
x = x | ((1 as i64) << i)
cur = mul48(cur, inv_pows[i])
}
i = i + 1
}
return x
}
function powA_sumY(n: i64) -> void {
if n == 0 {
g_powv = 1
g_sumv = 0
return
}
let mut powv: i64 = 1
let mut sumv: i64 = 0
let mut top: i32 = 63
while (n >> top) % 2 == 0 {
top = top - 1
}
let mut bit: i32 = top
while bit >= 0 {
let one_plus_powv: i64 = (1 + powv) % MOD48
sumv = mul48(sumv, one_plus_powv)
powv = mul48(powv, powv)
if (n >> bit) % 2 == 1 {
sumv = (sumv + powv) % MOD48
powv = mul48(powv, A_VAL)
}
bit = bit - 1
}
g_powv = powv
g_sumv = sumv
}
function index_of_state(a0_in: i64, target_in: i64) -> i64 {
let a0: i64 = a0_in % MOD48
if a0 < 0 { a0 = a0 + MOD48 }
let target: i64 = target_in % MOD48
if target < 0 { target = target + MOD48 }
if target == a0 { return 0 }
let a1: i64 = step48(a0)
let mut K: i64 = (a1 - a0) % MOD48
if K < 0 { K = K + MOD48 }
let invK: i64 = invmod48(K)
let mut diff: i64 = (target - a0) % MOD48
if diff < 0 { diff = diff + MOD48 }
let y_target: i64 = mul48(diff, invK)
let h: i64 = (mul48(A_VAL - 1, y_target) + 1) % MOD48
let n0: i64 = dlog_pow2(h)
let stepN: i64 = (1 as i64) << ORDER_EXP
let mut t: i32 = 0
while t < 4 {
let n: i64 = n0 + (t as i64) * stepN
powA_sumY(n)
if g_sumv == y_target { return n }
t = t + 1
}
return 0
}
function main() -> i32 {
precompute_dlog()
# "PuzzleOne" -> vals = [41, 20, 25, 25, 11, 4, 40, 13, 4]
let puzzle_vals: ptr<i32> = calloc(64, 4)
puzzle_vals[0] = 41
puzzle_vals[1] = 20
puzzle_vals[2] = 25
puzzle_vals[3] = 25
puzzle_vals[4] = 11
puzzle_vals[5] = 4
puzzle_vals[6] = 40
puzzle_vals[7] = 13
puzzle_vals[8] = 4
let puzzle_states: ptr<i64> = calloc(16, 8)
let n_puzzle: i32 = solve_states(puzzle_vals, 9, puzzle_states, 16)
let seed: i64 = puzzle_states[0]
# "LuckyText" -> vals = [37, 20, 2, 10, 24, 45, 4, 23, 19]
let lucky_vals: ptr<i32> = calloc(64, 4)
lucky_vals[0] = 37
lucky_vals[1] = 20
lucky_vals[2] = 2
lucky_vals[3] = 10
lucky_vals[4] = 24
lucky_vals[5] = 45
lucky_vals[6] = 4
lucky_vals[7] = 23
lucky_vals[8] = 19
let lucky_states: ptr<i64> = calloc(256, 8)
let n_lucky: i32 = solve_states(lucky_vals, 9, lucky_states, 256)
let mut best: i64 = 0
let mut found: bool = false
let mut i: i32 = 0
while i < n_lucky {
let n: i64 = index_of_state(seed, lucky_states[i])
if !found || n < best {
best = n
found = true
}
i = i + 1
}
printf("%lld\n", best)
free(puzzle_vals)
free(puzzle_states)
free(lucky_vals)
free(lucky_states)
free(inv_pows)
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 mul48_i64_i64(int64_t a, int64_t b);
int64_t powmod48_i64_i64(int64_t base, int64_t exp);
int64_t invmod48_i64(int64_t x0);
int64_t step48_i64(int64_t x);
int32_t b_from_a_i64(int64_t a);
int32_t check_prefix_i64_ptr_i32_i32(int64_t a0, int32_t* vals, int32_t L);
int32_t u0_candidates_ptr_i32_i32_ptr_i64_i32(int32_t* pattern_vals, int32_t L, int64_t* out, int32_t max_out);
int32_t solve_y0_ptr_i64_ptr_i32_i32_ptr_i64_i32(int64_t* carries24, int32_t* residues13, int32_t L, int64_t* out, int32_t max_out);
int32_t solve_states_ptr_i32_i32_ptr_i64_i32(int32_t* vals, int32_t L, int64_t* states_out, int32_t max_states);
void precompute_dlog(void);
int64_t dlog_pow2_i64(int64_t h);
void powA_sumY_i64(int64_t n);
int64_t index_of_state_i64_i64(int64_t a0_in, int64_t target_in);
int32_t main(void);
static const int64_t A_VAL = 25214903917;
static const int64_t C_VAL = 11;
static const int64_t MOD48 = 281474976710656;
static const int64_t MOD24 = 16777216;
static const int64_t MOD18 = 262144;
static const int32_t INV9_MOD13 = 3;
static const int32_t ORDER_EXP = 46;
/* Module statics */
static int64_t G_ORDER = 0;
static int64_t* inv_pows = NULL;
static int64_t g_powv = 0;
static int64_t g_sumv = 0;
int64_t mul48_i64_i64(int64_t a, int64_t b) {
__int128 prod = (((__int128)(a)) * ((__int128)(b)));
return ((int64_t)(FLOW_CHECKED_MOD((prod), (((__int128)(MOD48))))));
}
int64_t powmod48_i64_i64(int64_t base, int64_t exp) {
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (MOD48));
if (b < 0) {
b = (b + MOD48);
}
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mul48_i64_i64(result, b);
}
b = mul48_i64_i64(b, b);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
int64_t invmod48_i64(int64_t x0) {
int64_t x = FLOW_CHECKED_MOD((x0), (MOD48));
if (x < 0) {
x = (x + MOD48);
}
int64_t inv = x;
int32_t i = 0;
while (i < 5) {
int64_t t = mul48_i64_i64(x, inv);
int64_t two_minus = FLOW_CHECKED_MOD((((MOD48 + 2) - t)), (MOD48));
inv = mul48_i64_i64(inv, two_minus);
i = (i + 1);
}
return inv;
}
int64_t step48_i64(int64_t x) {
return FLOW_CHECKED_MOD(((mul48_i64_i64(A_VAL, x) + C_VAL)), (MOD48));
}
int32_t b_from_a_i64(int64_t a) {
return ((int32_t)(FLOW_CHECKED_MOD((FLOW_CHECKED_SHR((a), (16))), (52))));
}
int32_t check_prefix_i64_ptr_i32_i32(int64_t a0, int32_t* vals, int32_t L) {
int64_t a = FLOW_CHECKED_MOD((a0), (MOD48));
if (a < 0) {
a = (a + MOD48);
}
int32_t i = 0;
while (i < L) {
if (b_from_a_i64(a) != vals[i]) {
return 0;
}
a = step48_i64(a);
i = (i + 1);
}
return 1;
}
int32_t u0_candidates_ptr_i32_i32_ptr_i64_i32(int32_t* pattern_vals, int32_t L, int64_t* out, int32_t max_out) {
int32_t count = 0;
int64_t u0 = 0;
while (u0 < MOD18) {
int64_t u = u0;
bool ok = 1;
int32_t i = 0;
while (i < L) {
if (((int32_t)(FLOW_CHECKED_MOD((FLOW_CHECKED_SHR((u), (16))), (4)))) != FLOW_CHECKED_MOD((pattern_vals[i]), (4))) {
ok = 0;
break;
}
u = FLOW_CHECKED_MOD(((mul48_i64_i64(A_VAL, u) + C_VAL)), (MOD18));
i = (i + 1);
}
if (ok) {
if (count < max_out) {
out[count] = u0;
}
count = (count + 1);
}
u0 = (u0 + 1);
}
return count;
}
int32_t solve_y0_ptr_i64_ptr_i32_i32_ptr_i64_i32(int64_t* carries24, int32_t* residues13, int32_t L, int64_t* out, int32_t max_out) {
if (L == 0) {
return 0;
}
int32_t r0 = residues13[0];
int32_t count = 0;
if (L == 1) {
int64_t y0 = ((int64_t)(r0));
while (y0 < MOD24) {
if (count < max_out) {
out[count] = y0;
}
count = (count + 1);
y0 = (y0 + 13);
}
return count;
}
int32_t r1 = residues13[1];
int64_t a24 = FLOW_CHECKED_MOD((A_VAL), (MOD24));
if (L == 2) {
int64_t y0_init = ((int64_t)(r0));
int64_t y1 = FLOW_CHECKED_MOD(((mul48_i64_i64(A_VAL, y0_init) + carries24[0])), (MOD24));
int64_t delta1 = FLOW_CHECKED_MOD(((13 * a24)), (MOD24));
int64_t y0 = ((int64_t)(r0));
while (y0 < MOD24) {
if (FLOW_CHECKED_MOD((y1), (13)) == ((int64_t)(r1))) {
if (count < max_out) {
out[count] = y0;
}
count = (count + 1);
}
y1 = FLOW_CHECKED_MOD(((y1 + delta1)), (MOD24));
y0 = (y0 + 13);
}
return count;
}
int32_t r2 = residues13[2];
int64_t y0_init = ((int64_t)(r0));
int64_t y1 = FLOW_CHECKED_MOD(((mul48_i64_i64(A_VAL, y0_init) + carries24[0])), (MOD24));
int64_t y2 = FLOW_CHECKED_MOD(((mul48_i64_i64(A_VAL, y1) + carries24[1])), (MOD24));
int64_t delta1 = FLOW_CHECKED_MOD(((13 * a24)), (MOD24));
int64_t delta2 = FLOW_CHECKED_MOD((mul48_i64_i64(delta1, a24)), (MOD24));
int64_t y0 = ((int64_t)(r0));
while (y0 < MOD24) {
if ((FLOW_CHECKED_MOD((y1), (13)) == ((int64_t)(r1)) && FLOW_CHECKED_MOD((y2), (13)) == ((int64_t)(r2)))) {
int64_t y = y2;
bool ok = 1;
int32_t i = 2;
while (i < (L - 1)) {
y = FLOW_CHECKED_MOD(((mul48_i64_i64(A_VAL, y) + carries24[i])), (MOD24));
if (FLOW_CHECKED_MOD((y), (13)) != ((int64_t)(residues13[(i + 1)]))) {
ok = 0;
break;
}
i = (i + 1);
}
if (ok) {
if (count < max_out) {
out[count] = y0;
}
count = (count + 1);
}
}
y1 = FLOW_CHECKED_MOD(((y1 + delta1)), (MOD24));
y2 = FLOW_CHECKED_MOD(((y2 + delta2)), (MOD24));
y0 = (y0 + 13);
}
return count;
}
int32_t solve_states_ptr_i32_i32_ptr_i64_i32(int32_t* vals, int32_t L, int64_t* states_out, int32_t max_states) {
int64_t* us = (int64_t*)(calloc(1024, 8));
int32_t n_us = u0_candidates_ptr_i32_i32_ptr_i64_i32(vals, L, us, 1024);
int32_t n_states = 0;
int64_t* u_list = (int64_t*)(calloc(64, 8));
int64_t* k_list = (int64_t*)(calloc(64, 8));
int64_t* carries24 = (int64_t*)(calloc(64, 8));
int32_t* t_list = (int32_t*)(calloc(64, 4));
int32_t* residues13 = (int32_t*)(calloc(64, 4));
int64_t* y0s = (int64_t*)(calloc(4096, 8));
int32_t ui = 0;
while (ui < n_us) {
int64_t u0 = us[ui];
int64_t u = u0;
int32_t i = 0;
while (i < L) {
u_list[i] = u;
int64_t nxt = ((A_VAL * u) + C_VAL);
if (i < (L - 1)) {
k_list[i] = FLOW_CHECKED_SHR((nxt), (18));
}
u = FLOW_CHECKED_MOD((nxt), (MOD18));
i = (i + 1);
}
int32_t w0 = 0;
while (w0 < 64) {
int64_t w = ((int64_t)(w0));
int32_t i2 = 0;
while (i2 < L) {
t_list[i2] = ((int32_t)((FLOW_CHECKED_MOD((FLOW_CHECKED_SHR((u_list[i2]), (16))), (4)) + (w * 4))));
if (i2 < (L - 1)) {
carries24[i2] = FLOW_CHECKED_SHR(((k_list[i2] + (A_VAL * w))), (6));
w = FLOW_CHECKED_MOD((((A_VAL * w) + k_list[i2])), (64));
}
i2 = (i2 + 1);
}
int32_t i3 = 0;
while (i3 < L) {
int32_t t_mod13 = FLOW_CHECKED_MOD((t_list[i3]), (13));
if (t_mod13 < 0) {
t_mod13 = (t_mod13 + 13);
}
int32_t diff = FLOW_CHECKED_MOD(((vals[i3] - t_mod13)), (13));
if (diff < 0) {
diff = (diff + 13);
}
residues13[i3] = FLOW_CHECKED_MOD(((INV9_MOD13 * diff)), (13));
i3 = (i3 + 1);
}
int32_t n_y0 = solve_y0_ptr_i64_ptr_i32_i32_ptr_i64_i32(carries24, residues13, L, y0s, 4096);
int32_t yi = 0;
while (yi < n_y0) {
int64_t y0 = y0s[yi];
int64_t x0 = (u0 + FLOW_CHECKED_SHL((((int64_t)(w0))), (18)));
int64_t a0 = (x0 + FLOW_CHECKED_SHL((y0), (24)));
if (check_prefix_i64_ptr_i32_i32(a0, vals, L) == 1) {
if (n_states < max_states) {
states_out[n_states] = a0;
}
n_states = (n_states + 1);
}
yi = (yi + 1);
}
w0 = (w0 + 1);
}
ui = (ui + 1);
}
free(us);
free(u_list);
free(k_list);
free(carries24);
free(t_list);
free(residues13);
free(y0s);
return n_states;
}
void precompute_dlog(void) {
inv_pows = calloc(((int64_t)(ORDER_EXP)), 8);
G_ORDER = powmod48_i64_i64(A_VAL, FLOW_CHECKED_SHL((((int64_t)(1))), ((ORDER_EXP - 1))));
int32_t i = 0;
while (i < ORDER_EXP) {
int64_t p = powmod48_i64_i64(A_VAL, FLOW_CHECKED_SHL((((int64_t)(1))), (i)));
inv_pows[i] = invmod48_i64(p);
i = (i + 1);
}
}
int64_t dlog_pow2_i64(int64_t h) {
int64_t x = 0;
int64_t cur = FLOW_CHECKED_MOD((h), (MOD48));
if (cur < 0) {
cur = (cur + MOD48);
}
int32_t i = 0;
while (i < ORDER_EXP) {
int64_t e = FLOW_CHECKED_SHL((((int64_t)(1))), (((ORDER_EXP - 1) - i)));
int64_t t = powmod48_i64_i64(cur, e);
if (t == G_ORDER) {
x = (x | FLOW_CHECKED_SHL((((int64_t)(1))), (i)));
cur = mul48_i64_i64(cur, inv_pows[i]);
}
i = (i + 1);
}
return x;
}
void powA_sumY_i64(int64_t n) {
if (n == 0) {
g_powv = 1;
g_sumv = 0;
return;
}
int64_t powv = 1;
int64_t sumv = 0;
int32_t top = 63;
while (FLOW_CHECKED_MOD((FLOW_CHECKED_SHR((n), (top))), (2)) == 0) {
top = (top - 1);
}
int32_t bit = top;
while (bit >= 0) {
int64_t one_plus_powv = FLOW_CHECKED_MOD(((1 + powv)), (MOD48));
sumv = mul48_i64_i64(sumv, one_plus_powv);
powv = mul48_i64_i64(powv, powv);
if (FLOW_CHECKED_MOD((FLOW_CHECKED_SHR((n), (bit))), (2)) == 1) {
sumv = FLOW_CHECKED_MOD(((sumv + powv)), (MOD48));
powv = mul48_i64_i64(powv, A_VAL);
}
bit = (bit - 1);
}
g_powv = powv;
g_sumv = sumv;
}
int64_t index_of_state_i64_i64(int64_t a0_in, int64_t target_in) {
int64_t a0 = FLOW_CHECKED_MOD((a0_in), (MOD48));
if (a0 < 0) {
a0 = (a0 + MOD48);
}
int64_t target = FLOW_CHECKED_MOD((target_in), (MOD48));
if (target < 0) {
target = (target + MOD48);
}
if (target == a0) {
return 0;
}
int64_t a1 = step48_i64(a0);
int64_t K = FLOW_CHECKED_MOD(((a1 - a0)), (MOD48));
if (K < 0) {
K = (K + MOD48);
}
int64_t invK = invmod48_i64(K);
int64_t diff = FLOW_CHECKED_MOD(((target - a0)), (MOD48));
if (diff < 0) {
diff = (diff + MOD48);
}
int64_t y_target = mul48_i64_i64(diff, invK);
int64_t h = FLOW_CHECKED_MOD(((mul48_i64_i64((A_VAL - 1), y_target) + 1)), (MOD48));
int64_t n0 = dlog_pow2_i64(h);
int64_t stepN = FLOW_CHECKED_SHL((((int64_t)(1))), (ORDER_EXP));
int32_t t = 0;
while (t < 4) {
int64_t n = (n0 + (((int64_t)(t)) * stepN));
powA_sumY_i64(n);
if (g_sumv == y_target) {
return n;
}
t = (t + 1);
}
return 0;
}
int32_t main(void) {
precompute_dlog();
int32_t* puzzle_vals = (int32_t*)(calloc(64, 4));
puzzle_vals[0] = 41;
puzzle_vals[1] = 20;
puzzle_vals[2] = 25;
puzzle_vals[3] = 25;
puzzle_vals[4] = 11;
puzzle_vals[5] = 4;
puzzle_vals[6] = 40;
puzzle_vals[7] = 13;
puzzle_vals[8] = 4;
int64_t* puzzle_states = (int64_t*)(calloc(16, 8));
int32_t n_puzzle = solve_states_ptr_i32_i32_ptr_i64_i32(puzzle_vals, 9, puzzle_states, 16);
int64_t seed = puzzle_states[0];
int32_t* lucky_vals = (int32_t*)(calloc(64, 4));
lucky_vals[0] = 37;
lucky_vals[1] = 20;
lucky_vals[2] = 2;
lucky_vals[3] = 10;
lucky_vals[4] = 24;
lucky_vals[5] = 45;
lucky_vals[6] = 4;
lucky_vals[7] = 23;
lucky_vals[8] = 19;
int64_t* lucky_states = (int64_t*)(calloc(256, 8));
int32_t n_lucky = solve_states_ptr_i32_i32_ptr_i64_i32(lucky_vals, 9, lucky_states, 256);
int64_t best = 0;
bool found = 0;
int32_t i = 0;
while (i < n_lucky) {
int64_t n = index_of_state_i64_i64(seed, lucky_states[i]);
if (((!(found)) || n < best)) {
best = n;
found = 1;
}
i = (i + 1);
}
printf("%lld\n", best);
free(puzzle_vals);
free(puzzle_states);
free(lucky_vals);
free(lucky_states);
free(inv_pows);
return 0;
}
Generated MLIR
module {
llvm.func @printf(!llvm.ptr, ...) -> i32
llvm.mlir.global internal constant @str_0("%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: A_VAL
llvm.mlir.global internal constant @A_VAL(25214903917 : i64) : i64
// Constant: C_VAL
llvm.mlir.global internal constant @C_VAL(11 : i64) : i64
// Constant: MOD48
llvm.mlir.global internal constant @MOD48(281474976710656 : i64) : i64
// Constant: MOD24
llvm.mlir.global internal constant @MOD24(16777216 : i64) : i64
// Constant: MOD18
llvm.mlir.global internal constant @MOD18(262144 : i64) : i64
// Constant: INV9_MOD13
llvm.mlir.global internal constant @INV9_MOD13(3 : i32) : i32
// Constant: ORDER_EXP
llvm.mlir.global internal constant @ORDER_EXP(46 : i32) : i32
// Module static: G_ORDER
llvm.mlir.global internal @G_ORDER(0 : i64) : i64
// Module static: inv_pows
llvm.mlir.global internal @inv_pows() {addr_space = 0 : i32} : !llvm.ptr {
%0 = llvm.mlir.zero : !llvm.ptr
llvm.return %0 : !llvm.ptr
}
// Module static: g_powv
llvm.mlir.global internal @g_powv(0 : i64) : i64
// Module static: g_sumv
llvm.mlir.global internal @g_sumv(0 : i64) : i64
func.func @mul48(%arg0: i64, %arg1: i64) -> i64 {
%1 = arith.extsi %arg0 : i64 to i128
%2 = arith.extsi %arg1 : i64 to i128
%4 = arith.trunci %1 : i128 to i64
%5 = arith.trunci %2 : i128 to i64
%3 = arith.muli %4, %5 : i64
%6 = arith.extsi %3 : i64 to i128
%7 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%8 = llvm.load %7 : !llvm.ptr -> i64
%9 = arith.extsi %8 : i64 to i128
%11 = arith.trunci %6 : i128 to i64
%12 = arith.trunci %9 : i128 to i64
%10 = arith.remsi %11, %12 : i64
func.return %10 : i64
}
func.func @powmod48(%arg0: i64, %arg1: i64) -> i64 {
%13 = arith.constant 1 : i32
%14 = arith.extsi %13 : i32 to i64
%15 = llvm.mlir.constant(1 : i64) : i64
%16 = llvm.alloca %15 x i64 : (i64) -> !llvm.ptr
llvm.store %14, %16 : i64, !llvm.ptr
%17 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%18 = llvm.load %17 : !llvm.ptr -> i64
%19 = arith.remsi %arg0, %18 : i64
%20 = llvm.mlir.constant(1 : i64) : i64
%21 = llvm.alloca %20 x i64 : (i64) -> !llvm.ptr
llvm.store %19, %21 : i64, !llvm.ptr
%22 = llvm.load %21 : !llvm.ptr -> i64
%23 = arith.constant 0 : i32
%25 = arith.extsi %23 : i32 to i64
%24 = arith.cmpi slt, %22, %25 : i64
cf.cond_br %24, ^bb0, ^bb1
^bb0:
%26 = llvm.load %21 : !llvm.ptr -> i64
%27 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%28 = llvm.load %27 : !llvm.ptr -> i64
%29 = arith.addi %26, %28 : i64
llvm.store %29, %21 : i64, !llvm.ptr
cf.br ^bb2
^bb1:
cf.br ^bb2
^bb2:
%30 = llvm.mlir.constant(1 : i64) : i64
%31 = llvm.alloca %30 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %31 : i64, !llvm.ptr
cf.br ^bb3
^bb3:
%32 = llvm.load %31 : !llvm.ptr -> i64
%33 = arith.constant 0 : i32
%35 = arith.extsi %33 : i32 to i64
%34 = arith.cmpi sgt, %32, %35 : i64
cf.cond_br %34, ^bb4, ^bb5
^bb4:
%36 = llvm.load %31 : !llvm.ptr -> i64
%37 = arith.constant 2 : i32
%39 = arith.extsi %37 : i32 to i64
%38 = arith.remsi %36, %39 : i64
%40 = arith.constant 1 : i32
%42 = arith.extsi %40 : i32 to i64
%41 = arith.cmpi eq, %38, %42 : i64
cf.cond_br %41, ^bb6, ^bb7
^bb6:
%44 = llvm.load %16 : !llvm.ptr -> i64
%45 = llvm.load %21 : !llvm.ptr -> i64
%43 = func.call @mul48(%44, %45) : (i64, i64) -> i64
llvm.store %43, %16 : i64, !llvm.ptr
cf.br ^bb8
^bb7:
cf.br ^bb8
^bb8:
%47 = llvm.load %21 : !llvm.ptr -> i64
%48 = llvm.load %21 : !llvm.ptr -> i64
%46 = func.call @mul48(%47, %48) : (i64, i64) -> i64
llvm.store %46, %21 : i64, !llvm.ptr
%49 = llvm.load %31 : !llvm.ptr -> i64
%50 = arith.constant 2 : i32
%52 = arith.extsi %50 : i32 to i64
%51 = arith.divsi %49, %52 : i64
llvm.store %51, %31 : i64, !llvm.ptr
cf.br ^bb3
^bb5:
%53 = llvm.load %16 : !llvm.ptr -> i64
func.return %53 : i64
}
func.func @invmod48(%arg0: i64) -> i64 {
%54 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%55 = llvm.load %54 : !llvm.ptr -> i64
%56 = arith.remsi %arg0, %55 : i64
%57 = llvm.mlir.constant(1 : i64) : i64
%58 = llvm.alloca %57 x i64 : (i64) -> !llvm.ptr
llvm.store %56, %58 : i64, !llvm.ptr
%59 = llvm.load %58 : !llvm.ptr -> i64
%60 = arith.constant 0 : i32
%62 = arith.extsi %60 : i32 to i64
%61 = arith.cmpi slt, %59, %62 : i64
cf.cond_br %61, ^bb9, ^bb10
^bb9:
%63 = llvm.load %58 : !llvm.ptr -> i64
%64 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%65 = llvm.load %64 : !llvm.ptr -> i64
%66 = arith.addi %63, %65 : i64
llvm.store %66, %58 : i64, !llvm.ptr
cf.br ^bb11
^bb10:
cf.br ^bb11
^bb11:
%67 = llvm.load %58 : !llvm.ptr -> i64
%68 = llvm.mlir.constant(1 : i64) : i64
%69 = llvm.alloca %68 x i64 : (i64) -> !llvm.ptr
llvm.store %67, %69 : i64, !llvm.ptr
%70 = arith.constant 0 : i32
%71 = llvm.mlir.constant(1 : i64) : i64
%72 = llvm.alloca %71 x i32 : (i64) -> !llvm.ptr
llvm.store %70, %72 : i32, !llvm.ptr
cf.br ^bb12
^bb12:
%73 = llvm.load %72 : !llvm.ptr -> i32
%74 = arith.constant 5 : i32
%75 = arith.cmpi slt, %73, %74 : i32
cf.cond_br %75, ^bb13, ^bb14
^bb13:
%77 = llvm.load %58 : !llvm.ptr -> i64
%78 = llvm.load %69 : !llvm.ptr -> i64
%76 = func.call @mul48(%77, %78) : (i64, i64) -> i64
%79 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%80 = llvm.load %79 : !llvm.ptr -> i64
%81 = arith.constant 2 : i32
%83 = arith.extsi %81 : i32 to i64
%82 = arith.addi %80, %83 : i64
%84 = arith.subi %82, %76 : i64
%85 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%86 = llvm.load %85 : !llvm.ptr -> i64
%87 = arith.remsi %84, %86 : i64
%89 = llvm.load %69 : !llvm.ptr -> i64
%88 = func.call @mul48(%89, %87) : (i64, i64) -> i64
llvm.store %88, %69 : i64, !llvm.ptr
%90 = llvm.load %72 : !llvm.ptr -> i32
%91 = arith.constant 1 : i32
%92 = arith.addi %90, %91 : i32
llvm.store %92, %72 : i32, !llvm.ptr
cf.br ^bb12
^bb14:
%93 = llvm.load %69 : !llvm.ptr -> i64
func.return %93 : i64
}
func.func @step48(%arg0: i64) -> i64 {
%95 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%96 = llvm.load %95 : !llvm.ptr -> i64
%94 = func.call @mul48(%96, %arg0) : (i64, i64) -> i64
%97 = llvm.mlir.addressof @C_VAL : !llvm.ptr
%98 = llvm.load %97 : !llvm.ptr -> i64
%99 = arith.addi %94, %98 : i64
%100 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%101 = llvm.load %100 : !llvm.ptr -> i64
%102 = arith.remsi %99, %101 : i64
func.return %102 : i64
}
func.func @b_from_a(%arg0: i64) -> i32 {
%103 = arith.constant 16 : i32
%105 = arith.extsi %103 : i32 to i64
%104 = arith.shrsi %arg0, %105 : i64
%106 = arith.constant 52 : i32
%108 = arith.extsi %106 : i32 to i64
%107 = arith.remsi %104, %108 : i64
%109 = arith.trunci %107 : i64 to i32
func.return %109 : i32
}
func.func @check_prefix(%arg0: i64, %arg1: !llvm.ptr, %arg2: i32) -> i32 {
%110 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%111 = llvm.load %110 : !llvm.ptr -> i64
%112 = arith.remsi %arg0, %111 : i64
%113 = llvm.mlir.constant(1 : i64) : i64
%114 = llvm.alloca %113 x i64 : (i64) -> !llvm.ptr
llvm.store %112, %114 : i64, !llvm.ptr
%115 = llvm.load %114 : !llvm.ptr -> i64
%116 = arith.constant 0 : i32
%118 = arith.extsi %116 : i32 to i64
%117 = arith.cmpi slt, %115, %118 : i64
cf.cond_br %117, ^bb15, ^bb16
^bb15:
%119 = llvm.load %114 : !llvm.ptr -> i64
%120 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%121 = llvm.load %120 : !llvm.ptr -> i64
%122 = arith.addi %119, %121 : i64
llvm.store %122, %114 : i64, !llvm.ptr
cf.br ^bb17
^bb16:
cf.br ^bb17
^bb17:
%123 = arith.constant 0 : i32
%124 = llvm.mlir.constant(1 : i64) : i64
%125 = llvm.alloca %124 x i32 : (i64) -> !llvm.ptr
llvm.store %123, %125 : i32, !llvm.ptr
cf.br ^bb18
^bb18:
%126 = llvm.load %125 : !llvm.ptr -> i32
%127 = arith.cmpi slt, %126, %arg2 : i32
cf.cond_br %127, ^bb19, ^bb20
^bb19:
%129 = llvm.load %114 : !llvm.ptr -> i64
%128 = func.call @b_from_a(%129) : (i64) -> i32
%131 = llvm.load %125 : !llvm.ptr -> i32
%132 = arith.extsi %131 : i32 to i64
%133 = llvm.getelementptr %arg1[%132] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%130 = llvm.load %133 : !llvm.ptr -> i32
%134 = arith.cmpi ne, %128, %130 : i32
cf.cond_br %134, ^bb21, ^bb22
^bb21:
%135 = arith.constant 0 : i32
func.return %135 : i32
^bb22:
cf.br ^bb23
^bb23:
%137 = llvm.load %114 : !llvm.ptr -> i64
%136 = func.call @step48(%137) : (i64) -> i64
llvm.store %136, %114 : i64, !llvm.ptr
%138 = llvm.load %125 : !llvm.ptr -> i32
%139 = arith.constant 1 : i32
%140 = arith.addi %138, %139 : i32
llvm.store %140, %125 : i32, !llvm.ptr
cf.br ^bb18
^bb20:
%141 = arith.constant 1 : i32
func.return %141 : i32
}
func.func @u0_candidates(%arg0: !llvm.ptr, %arg1: i32, %arg2: !llvm.ptr, %arg3: i32) -> i32 {
%142 = arith.constant 0 : i32
%143 = llvm.mlir.constant(1 : i64) : i64
%144 = llvm.alloca %143 x i32 : (i64) -> !llvm.ptr
llvm.store %142, %144 : i32, !llvm.ptr
%145 = arith.constant 0 : i32
%146 = arith.extsi %145 : i32 to i64
%147 = llvm.mlir.constant(1 : i64) : i64
%148 = llvm.alloca %147 x i64 : (i64) -> !llvm.ptr
llvm.store %146, %148 : i64, !llvm.ptr
cf.br ^bb24
^bb24:
%149 = llvm.load %148 : !llvm.ptr -> i64
%150 = llvm.mlir.addressof @MOD18 : !llvm.ptr
%151 = llvm.load %150 : !llvm.ptr -> i64
%152 = arith.cmpi slt, %149, %151 : i64
cf.cond_br %152, ^bb25, ^bb26
^bb25:
%153 = llvm.load %148 : !llvm.ptr -> i64
%154 = llvm.mlir.constant(1 : i64) : i64
%155 = llvm.alloca %154 x i64 : (i64) -> !llvm.ptr
llvm.store %153, %155 : i64, !llvm.ptr
%156 = arith.constant 1 : i1
%157 = llvm.mlir.constant(1 : i64) : i64
%158 = llvm.alloca %157 x i1 : (i64) -> !llvm.ptr
llvm.store %156, %158 : i1, !llvm.ptr
%159 = arith.constant 0 : i32
%160 = llvm.mlir.constant(1 : i64) : i64
%161 = llvm.alloca %160 x i32 : (i64) -> !llvm.ptr
llvm.store %159, %161 : i32, !llvm.ptr
cf.br ^bb27
^bb27:
%162 = llvm.load %161 : !llvm.ptr -> i32
%163 = arith.cmpi slt, %162, %arg1 : i32
cf.cond_br %163, ^bb28, ^bb29
^bb28:
%164 = llvm.load %155 : !llvm.ptr -> i64
%165 = arith.constant 16 : i32
%167 = arith.extsi %165 : i32 to i64
%166 = arith.shrsi %164, %167 : i64
%168 = arith.constant 4 : i32
%170 = arith.extsi %168 : i32 to i64
%169 = arith.remsi %166, %170 : i64
%171 = arith.trunci %169 : i64 to i32
%173 = llvm.load %161 : !llvm.ptr -> i32
%174 = arith.extsi %173 : i32 to i64
%175 = llvm.getelementptr %arg0[%174] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%172 = llvm.load %175 : !llvm.ptr -> i32
%176 = arith.constant 4 : i32
%177 = arith.remsi %172, %176 : i32
%178 = arith.cmpi ne, %171, %177 : i32
cf.cond_br %178, ^bb30, ^bb31
^bb30:
%179 = arith.constant 0 : i1
llvm.store %179, %158 : i1, !llvm.ptr
cf.br ^bb29
^bb31:
cf.br ^bb32
^bb32:
%181 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%182 = llvm.load %181 : !llvm.ptr -> i64
%183 = llvm.load %155 : !llvm.ptr -> i64
%180 = func.call @mul48(%182, %183) : (i64, i64) -> i64
%184 = llvm.mlir.addressof @C_VAL : !llvm.ptr
%185 = llvm.load %184 : !llvm.ptr -> i64
%186 = arith.addi %180, %185 : i64
%187 = llvm.mlir.addressof @MOD18 : !llvm.ptr
%188 = llvm.load %187 : !llvm.ptr -> i64
%189 = arith.remsi %186, %188 : i64
llvm.store %189, %155 : i64, !llvm.ptr
%190 = llvm.load %161 : !llvm.ptr -> i32
%191 = arith.constant 1 : i32
%192 = arith.addi %190, %191 : i32
llvm.store %192, %161 : i32, !llvm.ptr
cf.br ^bb27
^bb29:
%193 = llvm.load %158 : !llvm.ptr -> i1
cf.cond_br %193, ^bb33, ^bb34
^bb33:
%194 = llvm.load %144 : !llvm.ptr -> i32
%195 = arith.cmpi slt, %194, %arg3 : i32
cf.cond_br %195, ^bb36, ^bb37
^bb36:
%196 = llvm.load %148 : !llvm.ptr -> i64
%197 = llvm.load %144 : !llvm.ptr -> i32
%198 = arith.extsi %197 : i32 to i64
%199 = llvm.getelementptr %arg2[%198] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %196, %199 : i64, !llvm.ptr
cf.br ^bb38
^bb37:
cf.br ^bb38
^bb38:
%200 = llvm.load %144 : !llvm.ptr -> i32
%201 = arith.constant 1 : i32
%202 = arith.addi %200, %201 : i32
llvm.store %202, %144 : i32, !llvm.ptr
cf.br ^bb35
^bb34:
cf.br ^bb35
^bb35:
%203 = llvm.load %148 : !llvm.ptr -> i64
%204 = arith.constant 1 : i32
%206 = arith.extsi %204 : i32 to i64
%205 = arith.addi %203, %206 : i64
llvm.store %205, %148 : i64, !llvm.ptr
cf.br ^bb24
^bb26:
%207 = llvm.load %144 : !llvm.ptr -> i32
func.return %207 : i32
}
func.func @solve_y0(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32, %arg3: !llvm.ptr, %arg4: i32) -> i32 {
%208 = arith.constant 0 : i32
%209 = arith.cmpi eq, %arg2, %208 : i32
cf.cond_br %209, ^bb39, ^bb40
^bb39:
%210 = arith.constant 0 : i32
func.return %210 : i32
^bb40:
cf.br ^bb41
^bb41:
%212 = arith.constant 0 : i32
%213 = arith.extsi %212 : i32 to i64
%214 = llvm.getelementptr %arg1[%213] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%211 = llvm.load %214 : !llvm.ptr -> i32
%215 = arith.constant 0 : i32
%216 = llvm.mlir.constant(1 : i64) : i64
%217 = llvm.alloca %216 x i32 : (i64) -> !llvm.ptr
llvm.store %215, %217 : i32, !llvm.ptr
%218 = arith.constant 1 : i32
%219 = arith.cmpi eq, %arg2, %218 : i32
cf.cond_br %219, ^bb42, ^bb43
^bb42:
%220 = arith.extsi %211 : i32 to i64
%221 = llvm.mlir.constant(1 : i64) : i64
%222 = llvm.alloca %221 x i64 : (i64) -> !llvm.ptr
llvm.store %220, %222 : i64, !llvm.ptr
cf.br ^bb45
^bb45:
%223 = llvm.load %222 : !llvm.ptr -> i64
%224 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%225 = llvm.load %224 : !llvm.ptr -> i64
%226 = arith.cmpi slt, %223, %225 : i64
cf.cond_br %226, ^bb46, ^bb47
^bb46:
%227 = llvm.load %217 : !llvm.ptr -> i32
%228 = arith.cmpi slt, %227, %arg4 : i32
cf.cond_br %228, ^bb48, ^bb49
^bb48:
%229 = llvm.load %222 : !llvm.ptr -> i64
%230 = llvm.load %217 : !llvm.ptr -> i32
%231 = arith.extsi %230 : i32 to i64
%232 = llvm.getelementptr %arg3[%231] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %229, %232 : i64, !llvm.ptr
cf.br ^bb50
^bb49:
cf.br ^bb50
^bb50:
%233 = llvm.load %217 : !llvm.ptr -> i32
%234 = arith.constant 1 : i32
%235 = arith.addi %233, %234 : i32
llvm.store %235, %217 : i32, !llvm.ptr
%236 = llvm.load %222 : !llvm.ptr -> i64
%237 = arith.constant 13 : i32
%239 = arith.extsi %237 : i32 to i64
%238 = arith.addi %236, %239 : i64
llvm.store %238, %222 : i64, !llvm.ptr
cf.br ^bb45
^bb47:
%240 = llvm.load %217 : !llvm.ptr -> i32
func.return %240 : i32
^bb43:
cf.br ^bb44
^bb44:
%242 = arith.constant 1 : i32
%243 = arith.extsi %242 : i32 to i64
%244 = llvm.getelementptr %arg1[%243] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%241 = llvm.load %244 : !llvm.ptr -> i32
%245 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%246 = llvm.load %245 : !llvm.ptr -> i64
%247 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%248 = llvm.load %247 : !llvm.ptr -> i64
%249 = arith.remsi %246, %248 : i64
%250 = arith.constant 2 : i32
%251 = arith.cmpi eq, %arg2, %250 : i32
cf.cond_br %251, ^bb51, ^bb52
^bb51:
%252 = arith.extsi %211 : i32 to i64
%254 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%255 = llvm.load %254 : !llvm.ptr -> i64
%253 = func.call @mul48(%255, %252) : (i64, i64) -> i64
%257 = arith.constant 0 : i32
%258 = arith.extsi %257 : i32 to i64
%259 = llvm.getelementptr %arg0[%258] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%256 = llvm.load %259 : !llvm.ptr -> i64
%260 = arith.addi %253, %256 : i64
%261 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%262 = llvm.load %261 : !llvm.ptr -> i64
%263 = arith.remsi %260, %262 : i64
%264 = llvm.mlir.constant(1 : i64) : i64
%265 = llvm.alloca %264 x i64 : (i64) -> !llvm.ptr
llvm.store %263, %265 : i64, !llvm.ptr
%266 = arith.constant 13 : i32
%268 = arith.extsi %266 : i32 to i64
%267 = arith.muli %268, %249 : i64
%269 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%270 = llvm.load %269 : !llvm.ptr -> i64
%271 = arith.remsi %267, %270 : i64
%272 = arith.extsi %211 : i32 to i64
%273 = llvm.mlir.constant(1 : i64) : i64
%274 = llvm.alloca %273 x i64 : (i64) -> !llvm.ptr
llvm.store %272, %274 : i64, !llvm.ptr
cf.br ^bb54
^bb54:
%275 = llvm.load %274 : !llvm.ptr -> i64
%276 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%277 = llvm.load %276 : !llvm.ptr -> i64
%278 = arith.cmpi slt, %275, %277 : i64
cf.cond_br %278, ^bb55, ^bb56
^bb55:
%279 = llvm.load %265 : !llvm.ptr -> i64
%280 = arith.constant 13 : i32
%282 = arith.extsi %280 : i32 to i64
%281 = arith.remsi %279, %282 : i64
%283 = arith.extsi %241 : i32 to i64
%284 = arith.cmpi eq, %281, %283 : i64
cf.cond_br %284, ^bb57, ^bb58
^bb57:
%285 = llvm.load %217 : !llvm.ptr -> i32
%286 = arith.cmpi slt, %285, %arg4 : i32
cf.cond_br %286, ^bb60, ^bb61
^bb60:
%287 = llvm.load %274 : !llvm.ptr -> i64
%288 = llvm.load %217 : !llvm.ptr -> i32
%289 = arith.extsi %288 : i32 to i64
%290 = llvm.getelementptr %arg3[%289] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %287, %290 : i64, !llvm.ptr
cf.br ^bb62
^bb61:
cf.br ^bb62
^bb62:
%291 = llvm.load %217 : !llvm.ptr -> i32
%292 = arith.constant 1 : i32
%293 = arith.addi %291, %292 : i32
llvm.store %293, %217 : i32, !llvm.ptr
cf.br ^bb59
^bb58:
cf.br ^bb59
^bb59:
%294 = llvm.load %265 : !llvm.ptr -> i64
%295 = arith.addi %294, %271 : i64
%296 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%297 = llvm.load %296 : !llvm.ptr -> i64
%298 = arith.remsi %295, %297 : i64
llvm.store %298, %265 : i64, !llvm.ptr
%299 = llvm.load %274 : !llvm.ptr -> i64
%300 = arith.constant 13 : i32
%302 = arith.extsi %300 : i32 to i64
%301 = arith.addi %299, %302 : i64
llvm.store %301, %274 : i64, !llvm.ptr
cf.br ^bb54
^bb56:
%303 = llvm.load %217 : !llvm.ptr -> i32
func.return %303 : i32
^bb52:
cf.br ^bb53
^bb53:
%305 = arith.constant 2 : i32
%306 = arith.extsi %305 : i32 to i64
%307 = llvm.getelementptr %arg1[%306] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%304 = llvm.load %307 : !llvm.ptr -> i32
%308 = arith.extsi %211 : i32 to i64
%310 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%311 = llvm.load %310 : !llvm.ptr -> i64
%309 = func.call @mul48(%311, %308) : (i64, i64) -> i64
%313 = arith.constant 0 : i32
%314 = arith.extsi %313 : i32 to i64
%315 = llvm.getelementptr %arg0[%314] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%312 = llvm.load %315 : !llvm.ptr -> i64
%316 = arith.addi %309, %312 : i64
%317 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%318 = llvm.load %317 : !llvm.ptr -> i64
%319 = arith.remsi %316, %318 : i64
%320 = llvm.mlir.constant(1 : i64) : i64
%321 = llvm.alloca %320 x i64 : (i64) -> !llvm.ptr
llvm.store %319, %321 : i64, !llvm.ptr
%323 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> i64
%325 = llvm.load %321 : !llvm.ptr -> i64
%322 = func.call @mul48(%324, %325) : (i64, i64) -> i64
%327 = arith.constant 1 : i32
%328 = arith.extsi %327 : i32 to i64
%329 = llvm.getelementptr %arg0[%328] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%326 = llvm.load %329 : !llvm.ptr -> i64
%330 = arith.addi %322, %326 : i64
%331 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%332 = llvm.load %331 : !llvm.ptr -> i64
%333 = arith.remsi %330, %332 : i64
%334 = llvm.mlir.constant(1 : i64) : i64
%335 = llvm.alloca %334 x i64 : (i64) -> !llvm.ptr
llvm.store %333, %335 : i64, !llvm.ptr
%336 = arith.constant 13 : i32
%338 = arith.extsi %336 : i32 to i64
%337 = arith.muli %338, %249 : i64
%339 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%340 = llvm.load %339 : !llvm.ptr -> i64
%341 = arith.remsi %337, %340 : i64
%342 = func.call @mul48(%341, %249) : (i64, i64) -> i64
%343 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%344 = llvm.load %343 : !llvm.ptr -> i64
%345 = arith.remsi %342, %344 : i64
%346 = arith.extsi %211 : i32 to i64
%347 = llvm.mlir.constant(1 : i64) : i64
%348 = llvm.alloca %347 x i64 : (i64) -> !llvm.ptr
llvm.store %346, %348 : i64, !llvm.ptr
cf.br ^bb63
^bb63:
%349 = llvm.load %348 : !llvm.ptr -> i64
%350 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%351 = llvm.load %350 : !llvm.ptr -> i64
%352 = arith.cmpi slt, %349, %351 : i64
cf.cond_br %352, ^bb64, ^bb65
^bb64:
%353 = llvm.load %321 : !llvm.ptr -> i64
%354 = arith.constant 13 : i32
%356 = arith.extsi %354 : i32 to i64
%355 = arith.remsi %353, %356 : i64
%357 = arith.extsi %241 : i32 to i64
%358 = arith.cmpi eq, %355, %357 : i64
%359 = scf.if %358 -> (i1) {
%360 = llvm.load %335 : !llvm.ptr -> i64
%361 = arith.constant 13 : i32
%363 = arith.extsi %361 : i32 to i64
%362 = arith.remsi %360, %363 : i64
%364 = arith.extsi %304 : i32 to i64
%365 = arith.cmpi eq, %362, %364 : i64
scf.yield %365 : i1
} else {
%366 = arith.constant false
scf.yield %366 : i1
}
cf.cond_br %359, ^bb66, ^bb67
^bb66:
%367 = llvm.load %335 : !llvm.ptr -> i64
%368 = llvm.mlir.constant(1 : i64) : i64
%369 = llvm.alloca %368 x i64 : (i64) -> !llvm.ptr
llvm.store %367, %369 : i64, !llvm.ptr
%370 = arith.constant 1 : i1
%371 = llvm.mlir.constant(1 : i64) : i64
%372 = llvm.alloca %371 x i1 : (i64) -> !llvm.ptr
llvm.store %370, %372 : i1, !llvm.ptr
%373 = arith.constant 2 : i32
%374 = llvm.mlir.constant(1 : i64) : i64
%375 = llvm.alloca %374 x i32 : (i64) -> !llvm.ptr
llvm.store %373, %375 : i32, !llvm.ptr
cf.br ^bb69
^bb69:
%376 = llvm.load %375 : !llvm.ptr -> i32
%377 = arith.constant 1 : i32
%378 = arith.subi %arg2, %377 : i32
%379 = arith.cmpi slt, %376, %378 : i32
cf.cond_br %379, ^bb70, ^bb71
^bb70:
%381 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%382 = llvm.load %381 : !llvm.ptr -> i64
%383 = llvm.load %369 : !llvm.ptr -> i64
%380 = func.call @mul48(%382, %383) : (i64, i64) -> i64
%385 = llvm.load %375 : !llvm.ptr -> i32
%386 = arith.extsi %385 : i32 to i64
%387 = llvm.getelementptr %arg0[%386] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%384 = llvm.load %387 : !llvm.ptr -> i64
%388 = arith.addi %380, %384 : i64
%389 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%390 = llvm.load %389 : !llvm.ptr -> i64
%391 = arith.remsi %388, %390 : i64
llvm.store %391, %369 : i64, !llvm.ptr
%392 = llvm.load %369 : !llvm.ptr -> i64
%393 = arith.constant 13 : i32
%395 = arith.extsi %393 : i32 to i64
%394 = arith.remsi %392, %395 : i64
%397 = llvm.load %375 : !llvm.ptr -> i32
%398 = arith.constant 1 : i32
%399 = arith.addi %397, %398 : i32
%400 = arith.extsi %399 : i32 to i64
%401 = llvm.getelementptr %arg1[%400] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%396 = llvm.load %401 : !llvm.ptr -> i32
%402 = arith.extsi %396 : i32 to i64
%403 = arith.cmpi ne, %394, %402 : i64
cf.cond_br %403, ^bb72, ^bb73
^bb72:
%404 = arith.constant 0 : i1
llvm.store %404, %372 : i1, !llvm.ptr
cf.br ^bb71
^bb73:
cf.br ^bb74
^bb74:
%405 = llvm.load %375 : !llvm.ptr -> i32
%406 = arith.constant 1 : i32
%407 = arith.addi %405, %406 : i32
llvm.store %407, %375 : i32, !llvm.ptr
cf.br ^bb69
^bb71:
%408 = llvm.load %372 : !llvm.ptr -> i1
cf.cond_br %408, ^bb75, ^bb76
^bb75:
%409 = llvm.load %217 : !llvm.ptr -> i32
%410 = arith.cmpi slt, %409, %arg4 : i32
cf.cond_br %410, ^bb78, ^bb79
^bb78:
%411 = llvm.load %348 : !llvm.ptr -> i64
%412 = llvm.load %217 : !llvm.ptr -> i32
%413 = arith.extsi %412 : i32 to i64
%414 = llvm.getelementptr %arg3[%413] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %411, %414 : i64, !llvm.ptr
cf.br ^bb80
^bb79:
cf.br ^bb80
^bb80:
%415 = llvm.load %217 : !llvm.ptr -> i32
%416 = arith.constant 1 : i32
%417 = arith.addi %415, %416 : i32
llvm.store %417, %217 : i32, !llvm.ptr
cf.br ^bb77
^bb76:
cf.br ^bb77
^bb77:
cf.br ^bb68
^bb67:
cf.br ^bb68
^bb68:
%418 = llvm.load %321 : !llvm.ptr -> i64
%419 = arith.addi %418, %341 : i64
%420 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%421 = llvm.load %420 : !llvm.ptr -> i64
%422 = arith.remsi %419, %421 : i64
llvm.store %422, %321 : i64, !llvm.ptr
%423 = llvm.load %335 : !llvm.ptr -> i64
%424 = arith.addi %423, %345 : i64
%425 = llvm.mlir.addressof @MOD24 : !llvm.ptr
%426 = llvm.load %425 : !llvm.ptr -> i64
%427 = arith.remsi %424, %426 : i64
llvm.store %427, %335 : i64, !llvm.ptr
%428 = llvm.load %348 : !llvm.ptr -> i64
%429 = arith.constant 13 : i32
%431 = arith.extsi %429 : i32 to i64
%430 = arith.addi %428, %431 : i64
llvm.store %430, %348 : i64, !llvm.ptr
cf.br ^bb63
^bb65:
%432 = llvm.load %217 : !llvm.ptr -> i32
func.return %432 : i32
}
func.func @solve_states(%arg0: !llvm.ptr, %arg1: i32, %arg2: !llvm.ptr, %arg3: i32) -> i32 {
%434 = arith.constant 1024 : i32
%435 = arith.constant 8 : i32
%436 = arith.extsi %434 : i32 to i64
%437 = arith.extsi %435 : i32 to i64
%433 = func.call @calloc(%436, %437) : (i64, i64) -> !llvm.ptr
%439 = arith.constant 1024 : i32
%438 = func.call @u0_candidates(%arg0, %arg1, %433, %439) : (!llvm.ptr, i32, !llvm.ptr, i32) -> i32
%440 = arith.constant 0 : i32
%441 = llvm.mlir.constant(1 : i64) : i64
%442 = llvm.alloca %441 x i32 : (i64) -> !llvm.ptr
llvm.store %440, %442 : i32, !llvm.ptr
%444 = arith.constant 64 : i32
%445 = arith.constant 8 : i32
%446 = arith.extsi %444 : i32 to i64
%447 = arith.extsi %445 : i32 to i64
%443 = func.call @calloc(%446, %447) : (i64, i64) -> !llvm.ptr
%449 = arith.constant 64 : i32
%450 = arith.constant 8 : i32
%451 = arith.extsi %449 : i32 to i64
%452 = arith.extsi %450 : i32 to i64
%448 = func.call @calloc(%451, %452) : (i64, i64) -> !llvm.ptr
%454 = arith.constant 64 : i32
%455 = arith.constant 8 : i32
%456 = arith.extsi %454 : i32 to i64
%457 = arith.extsi %455 : i32 to i64
%453 = func.call @calloc(%456, %457) : (i64, i64) -> !llvm.ptr
%459 = arith.constant 64 : i32
%460 = arith.constant 4 : i32
%461 = arith.extsi %459 : i32 to i64
%462 = arith.extsi %460 : i32 to i64
%458 = func.call @calloc(%461, %462) : (i64, i64) -> !llvm.ptr
%464 = arith.constant 64 : i32
%465 = arith.constant 4 : i32
%466 = arith.extsi %464 : i32 to i64
%467 = arith.extsi %465 : i32 to i64
%463 = func.call @calloc(%466, %467) : (i64, i64) -> !llvm.ptr
%469 = arith.constant 4096 : i32
%470 = arith.constant 8 : i32
%471 = arith.extsi %469 : i32 to i64
%472 = arith.extsi %470 : i32 to i64
%468 = func.call @calloc(%471, %472) : (i64, i64) -> !llvm.ptr
%473 = arith.constant 0 : i32
%474 = llvm.mlir.constant(1 : i64) : i64
%475 = llvm.alloca %474 x i32 : (i64) -> !llvm.ptr
llvm.store %473, %475 : i32, !llvm.ptr
cf.br ^bb81
^bb81:
%476 = llvm.load %475 : !llvm.ptr -> i32
%477 = arith.cmpi slt, %476, %438 : i32
cf.cond_br %477, ^bb82, ^bb83
^bb82:
%479 = llvm.load %475 : !llvm.ptr -> i32
%480 = arith.extsi %479 : i32 to i64
%481 = llvm.getelementptr %433[%480] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%478 = llvm.load %481 : !llvm.ptr -> i64
%482 = llvm.mlir.constant(1 : i64) : i64
%483 = llvm.alloca %482 x i64 : (i64) -> !llvm.ptr
llvm.store %478, %483 : i64, !llvm.ptr
%484 = arith.constant 0 : i32
%485 = llvm.mlir.constant(1 : i64) : i64
%486 = llvm.alloca %485 x i32 : (i64) -> !llvm.ptr
llvm.store %484, %486 : i32, !llvm.ptr
cf.br ^bb84
^bb84:
%487 = llvm.load %486 : !llvm.ptr -> i32
%488 = arith.cmpi slt, %487, %arg1 : i32
cf.cond_br %488, ^bb85, ^bb86
^bb85:
%489 = llvm.load %483 : !llvm.ptr -> i64
%490 = llvm.load %486 : !llvm.ptr -> i32
%491 = arith.extsi %490 : i32 to i64
%492 = llvm.getelementptr %443[%491] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %489, %492 : i64, !llvm.ptr
%493 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%494 = llvm.load %493 : !llvm.ptr -> i64
%495 = llvm.load %483 : !llvm.ptr -> i64
%496 = arith.muli %494, %495 : i64
%497 = llvm.mlir.addressof @C_VAL : !llvm.ptr
%498 = llvm.load %497 : !llvm.ptr -> i64
%499 = arith.addi %496, %498 : i64
%500 = llvm.load %486 : !llvm.ptr -> i32
%501 = arith.constant 1 : i32
%502 = arith.subi %arg1, %501 : i32
%503 = arith.cmpi slt, %500, %502 : i32
cf.cond_br %503, ^bb87, ^bb88
^bb87:
%504 = arith.constant 18 : i32
%506 = arith.extsi %504 : i32 to i64
%505 = arith.shrsi %499, %506 : i64
%507 = llvm.load %486 : !llvm.ptr -> i32
%508 = arith.extsi %507 : i32 to i64
%509 = llvm.getelementptr %448[%508] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %505, %509 : i64, !llvm.ptr
cf.br ^bb89
^bb88:
cf.br ^bb89
^bb89:
%510 = llvm.mlir.addressof @MOD18 : !llvm.ptr
%511 = llvm.load %510 : !llvm.ptr -> i64
%512 = arith.remsi %499, %511 : i64
llvm.store %512, %483 : i64, !llvm.ptr
%513 = llvm.load %486 : !llvm.ptr -> i32
%514 = arith.constant 1 : i32
%515 = arith.addi %513, %514 : i32
llvm.store %515, %486 : i32, !llvm.ptr
cf.br ^bb84
^bb86:
%516 = arith.constant 0 : i32
%517 = llvm.mlir.constant(1 : i64) : i64
%518 = llvm.alloca %517 x i32 : (i64) -> !llvm.ptr
llvm.store %516, %518 : i32, !llvm.ptr
cf.br ^bb90
^bb90:
%519 = llvm.load %518 : !llvm.ptr -> i32
%520 = arith.constant 64 : i32
%521 = arith.cmpi slt, %519, %520 : i32
cf.cond_br %521, ^bb91, ^bb92
^bb91:
%522 = llvm.load %518 : !llvm.ptr -> i32
%523 = arith.extsi %522 : i32 to i64
%524 = llvm.mlir.constant(1 : i64) : i64
%525 = llvm.alloca %524 x i64 : (i64) -> !llvm.ptr
llvm.store %523, %525 : i64, !llvm.ptr
%526 = arith.constant 0 : i32
%527 = llvm.mlir.constant(1 : i64) : i64
%528 = llvm.alloca %527 x i32 : (i64) -> !llvm.ptr
llvm.store %526, %528 : i32, !llvm.ptr
cf.br ^bb93
^bb93:
%529 = llvm.load %528 : !llvm.ptr -> i32
%530 = arith.cmpi slt, %529, %arg1 : i32
cf.cond_br %530, ^bb94, ^bb95
^bb94:
%532 = llvm.load %528 : !llvm.ptr -> i32
%533 = arith.extsi %532 : i32 to i64
%534 = llvm.getelementptr %443[%533] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%531 = llvm.load %534 : !llvm.ptr -> i64
%535 = arith.constant 16 : i32
%537 = arith.extsi %535 : i32 to i64
%536 = arith.shrsi %531, %537 : i64
%538 = arith.constant 4 : i32
%540 = arith.extsi %538 : i32 to i64
%539 = arith.remsi %536, %540 : i64
%541 = llvm.load %525 : !llvm.ptr -> i64
%542 = arith.constant 4 : i32
%544 = arith.extsi %542 : i32 to i64
%543 = arith.muli %541, %544 : i64
%545 = arith.addi %539, %543 : i64
%546 = arith.trunci %545 : i64 to i32
%547 = llvm.load %528 : !llvm.ptr -> i32
%548 = arith.extsi %547 : i32 to i64
%549 = llvm.getelementptr %458[%548] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %546, %549 : i32, !llvm.ptr
%550 = llvm.load %528 : !llvm.ptr -> i32
%551 = arith.constant 1 : i32
%552 = arith.subi %arg1, %551 : i32
%553 = arith.cmpi slt, %550, %552 : i32
cf.cond_br %553, ^bb96, ^bb97
^bb96:
%555 = llvm.load %528 : !llvm.ptr -> i32
%556 = arith.extsi %555 : i32 to i64
%557 = llvm.getelementptr %448[%556] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%554 = llvm.load %557 : !llvm.ptr -> i64
%558 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%559 = llvm.load %558 : !llvm.ptr -> i64
%560 = llvm.load %525 : !llvm.ptr -> i64
%561 = arith.muli %559, %560 : i64
%562 = arith.addi %554, %561 : i64
%563 = arith.constant 6 : i32
%565 = arith.extsi %563 : i32 to i64
%564 = arith.shrsi %562, %565 : i64
%566 = llvm.load %528 : !llvm.ptr -> i32
%567 = arith.extsi %566 : i32 to i64
%568 = llvm.getelementptr %453[%567] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %564, %568 : i64, !llvm.ptr
%569 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%570 = llvm.load %569 : !llvm.ptr -> i64
%571 = llvm.load %525 : !llvm.ptr -> i64
%572 = arith.muli %570, %571 : i64
%574 = llvm.load %528 : !llvm.ptr -> i32
%575 = arith.extsi %574 : i32 to i64
%576 = llvm.getelementptr %448[%575] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%573 = llvm.load %576 : !llvm.ptr -> i64
%577 = arith.addi %572, %573 : i64
%578 = arith.constant 64 : i32
%580 = arith.extsi %578 : i32 to i64
%579 = arith.remsi %577, %580 : i64
llvm.store %579, %525 : i64, !llvm.ptr
cf.br ^bb98
^bb97:
cf.br ^bb98
^bb98:
%581 = llvm.load %528 : !llvm.ptr -> i32
%582 = arith.constant 1 : i32
%583 = arith.addi %581, %582 : i32
llvm.store %583, %528 : i32, !llvm.ptr
cf.br ^bb93
^bb95:
%584 = arith.constant 0 : i32
%585 = llvm.mlir.constant(1 : i64) : i64
%586 = llvm.alloca %585 x i32 : (i64) -> !llvm.ptr
llvm.store %584, %586 : i32, !llvm.ptr
cf.br ^bb99
^bb99:
%587 = llvm.load %586 : !llvm.ptr -> i32
%588 = arith.cmpi slt, %587, %arg1 : i32
cf.cond_br %588, ^bb100, ^bb101
^bb100:
%590 = llvm.load %586 : !llvm.ptr -> i32
%591 = arith.extsi %590 : i32 to i64
%592 = llvm.getelementptr %458[%591] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%589 = llvm.load %592 : !llvm.ptr -> i32
%593 = arith.constant 13 : i32
%594 = arith.remsi %589, %593 : i32
%595 = llvm.mlir.constant(1 : i64) : i64
%596 = llvm.alloca %595 x i32 : (i64) -> !llvm.ptr
llvm.store %594, %596 : i32, !llvm.ptr
%597 = llvm.load %596 : !llvm.ptr -> i32
%598 = arith.constant 0 : i32
%599 = arith.cmpi slt, %597, %598 : i32
cf.cond_br %599, ^bb102, ^bb103
^bb102:
%600 = llvm.load %596 : !llvm.ptr -> i32
%601 = arith.constant 13 : i32
%602 = arith.addi %600, %601 : i32
llvm.store %602, %596 : i32, !llvm.ptr
cf.br ^bb104
^bb103:
cf.br ^bb104
^bb104:
%604 = llvm.load %586 : !llvm.ptr -> i32
%605 = arith.extsi %604 : i32 to i64
%606 = llvm.getelementptr %arg0[%605] : (!llvm.ptr, i64) -> !llvm.ptr, i32
%603 = llvm.load %606 : !llvm.ptr -> i32
%607 = llvm.load %596 : !llvm.ptr -> i32
%608 = arith.subi %603, %607 : i32
%609 = arith.constant 13 : i32
%610 = arith.remsi %608, %609 : i32
%611 = llvm.mlir.constant(1 : i64) : i64
%612 = llvm.alloca %611 x i32 : (i64) -> !llvm.ptr
llvm.store %610, %612 : i32, !llvm.ptr
%613 = llvm.load %612 : !llvm.ptr -> i32
%614 = arith.constant 0 : i32
%615 = arith.cmpi slt, %613, %614 : i32
cf.cond_br %615, ^bb105, ^bb106
^bb105:
%616 = llvm.load %612 : !llvm.ptr -> i32
%617 = arith.constant 13 : i32
%618 = arith.addi %616, %617 : i32
llvm.store %618, %612 : i32, !llvm.ptr
cf.br ^bb107
^bb106:
cf.br ^bb107
^bb107:
%619 = llvm.mlir.addressof @INV9_MOD13 : !llvm.ptr
%620 = llvm.load %619 : !llvm.ptr -> i32
%621 = llvm.load %612 : !llvm.ptr -> i32
%622 = arith.muli %620, %621 : i32
%623 = arith.constant 13 : i32
%624 = arith.remsi %622, %623 : i32
%625 = llvm.load %586 : !llvm.ptr -> i32
%626 = arith.extsi %625 : i32 to i64
%627 = llvm.getelementptr %463[%626] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %624, %627 : i32, !llvm.ptr
%628 = llvm.load %586 : !llvm.ptr -> i32
%629 = arith.constant 1 : i32
%630 = arith.addi %628, %629 : i32
llvm.store %630, %586 : i32, !llvm.ptr
cf.br ^bb99
^bb101:
%632 = arith.constant 4096 : i32
%631 = func.call @solve_y0(%453, %463, %arg1, %468, %632) : (!llvm.ptr, !llvm.ptr, i32, !llvm.ptr, i32) -> i32
%633 = arith.constant 0 : i32
%634 = llvm.mlir.constant(1 : i64) : i64
%635 = llvm.alloca %634 x i32 : (i64) -> !llvm.ptr
llvm.store %633, %635 : i32, !llvm.ptr
cf.br ^bb108
^bb108:
%636 = llvm.load %635 : !llvm.ptr -> i32
%637 = arith.cmpi slt, %636, %631 : i32
cf.cond_br %637, ^bb109, ^bb110
^bb109:
%639 = llvm.load %635 : !llvm.ptr -> i32
%640 = arith.extsi %639 : i32 to i64
%641 = llvm.getelementptr %468[%640] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%638 = llvm.load %641 : !llvm.ptr -> i64
%642 = llvm.load %518 : !llvm.ptr -> i32
%643 = arith.extsi %642 : i32 to i64
%644 = arith.constant 18 : i32
%646 = arith.extsi %644 : i32 to i64
%645 = arith.shli %643, %646 : i64
%647 = arith.addi %478, %645 : i64
%648 = arith.constant 24 : i32
%650 = arith.extsi %648 : i32 to i64
%649 = arith.shli %638, %650 : i64
%651 = arith.addi %647, %649 : i64
%652 = func.call @check_prefix(%651, %arg0, %arg1) : (i64, !llvm.ptr, i32) -> i32
%653 = arith.constant 1 : i32
%654 = arith.cmpi eq, %652, %653 : i32
cf.cond_br %654, ^bb111, ^bb112
^bb111:
%655 = llvm.load %442 : !llvm.ptr -> i32
%656 = arith.cmpi slt, %655, %arg3 : i32
cf.cond_br %656, ^bb114, ^bb115
^bb114:
%657 = llvm.load %442 : !llvm.ptr -> i32
%658 = arith.extsi %657 : i32 to i64
%659 = llvm.getelementptr %arg2[%658] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %651, %659 : i64, !llvm.ptr
cf.br ^bb116
^bb115:
cf.br ^bb116
^bb116:
%660 = llvm.load %442 : !llvm.ptr -> i32
%661 = arith.constant 1 : i32
%662 = arith.addi %660, %661 : i32
llvm.store %662, %442 : i32, !llvm.ptr
cf.br ^bb113
^bb112:
cf.br ^bb113
^bb113:
%663 = llvm.load %635 : !llvm.ptr -> i32
%664 = arith.constant 1 : i32
%665 = arith.addi %663, %664 : i32
llvm.store %665, %635 : i32, !llvm.ptr
cf.br ^bb108
^bb110:
%666 = llvm.load %518 : !llvm.ptr -> i32
%667 = arith.constant 1 : i32
%668 = arith.addi %666, %667 : i32
llvm.store %668, %518 : i32, !llvm.ptr
cf.br ^bb90
^bb92:
%669 = llvm.load %475 : !llvm.ptr -> i32
%670 = arith.constant 1 : i32
%671 = arith.addi %669, %670 : i32
llvm.store %671, %475 : i32, !llvm.ptr
cf.br ^bb81
^bb83:
func.call @free(%433) : (!llvm.ptr) -> ()
func.call @free(%443) : (!llvm.ptr) -> ()
func.call @free(%448) : (!llvm.ptr) -> ()
func.call @free(%453) : (!llvm.ptr) -> ()
func.call @free(%458) : (!llvm.ptr) -> ()
func.call @free(%463) : (!llvm.ptr) -> ()
func.call @free(%468) : (!llvm.ptr) -> ()
%679 = llvm.load %442 : !llvm.ptr -> i32
func.return %679 : i32
}
func.func @precompute_dlog() -> () {
%681 = llvm.mlir.addressof @ORDER_EXP : !llvm.ptr
%682 = llvm.load %681 : !llvm.ptr -> i32
%683 = arith.extsi %682 : i32 to i64
%684 = arith.constant 8 : i32
%685 = arith.extsi %684 : i32 to i64
%680 = func.call @calloc(%683, %685) : (i64, i64) -> !llvm.ptr
%686 = llvm.mlir.addressof @inv_pows : !llvm.ptr
llvm.store %680, %686 : !llvm.ptr, !llvm.ptr
%688 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%689 = llvm.load %688 : !llvm.ptr -> i64
%690 = arith.constant 1 : i32
%691 = arith.extsi %690 : i32 to i64
%692 = llvm.mlir.addressof @ORDER_EXP : !llvm.ptr
%693 = llvm.load %692 : !llvm.ptr -> i32
%694 = arith.constant 1 : i32
%695 = arith.subi %693, %694 : i32
%697 = arith.extsi %695 : i32 to i64
%696 = arith.shli %691, %697 : i64
%687 = func.call @powmod48(%689, %696) : (i64, i64) -> i64
%698 = llvm.mlir.addressof @G_ORDER : !llvm.ptr
llvm.store %687, %698 : i64, !llvm.ptr
%699 = arith.constant 0 : i32
%700 = llvm.mlir.constant(1 : i64) : i64
%701 = llvm.alloca %700 x i32 : (i64) -> !llvm.ptr
llvm.store %699, %701 : i32, !llvm.ptr
cf.br ^bb117
^bb117:
%702 = llvm.load %701 : !llvm.ptr -> i32
%703 = llvm.mlir.addressof @ORDER_EXP : !llvm.ptr
%704 = llvm.load %703 : !llvm.ptr -> i32
%705 = arith.cmpi slt, %702, %704 : i32
cf.cond_br %705, ^bb118, ^bb119
^bb118:
%707 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%708 = llvm.load %707 : !llvm.ptr -> i64
%709 = arith.constant 1 : i32
%710 = arith.extsi %709 : i32 to i64
%711 = llvm.load %701 : !llvm.ptr -> i32
%713 = arith.extsi %711 : i32 to i64
%712 = arith.shli %710, %713 : i64
%706 = func.call @powmod48(%708, %712) : (i64, i64) -> i64
%714 = func.call @invmod48(%706) : (i64) -> i64
%715 = llvm.mlir.addressof @inv_pows : !llvm.ptr
%716 = llvm.load %715 : !llvm.ptr -> !llvm.ptr
%717 = llvm.load %701 : !llvm.ptr -> i32
%718 = arith.extsi %717 : i32 to i64
%719 = llvm.getelementptr %716[%718] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %714, %719 : i64, !llvm.ptr
%720 = llvm.load %701 : !llvm.ptr -> i32
%721 = arith.constant 1 : i32
%722 = arith.addi %720, %721 : i32
llvm.store %722, %701 : i32, !llvm.ptr
cf.br ^bb117
^bb119:
func.return
}
func.func @dlog_pow2(%arg0: i64) -> i64 {
%723 = arith.constant 0 : i32
%724 = arith.extsi %723 : i32 to i64
%725 = llvm.mlir.constant(1 : i64) : i64
%726 = llvm.alloca %725 x i64 : (i64) -> !llvm.ptr
llvm.store %724, %726 : i64, !llvm.ptr
%727 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%728 = llvm.load %727 : !llvm.ptr -> i64
%729 = arith.remsi %arg0, %728 : i64
%730 = llvm.mlir.constant(1 : i64) : i64
%731 = llvm.alloca %730 x i64 : (i64) -> !llvm.ptr
llvm.store %729, %731 : i64, !llvm.ptr
%732 = llvm.load %731 : !llvm.ptr -> i64
%733 = arith.constant 0 : i32
%735 = arith.extsi %733 : i32 to i64
%734 = arith.cmpi slt, %732, %735 : i64
cf.cond_br %734, ^bb120, ^bb121
^bb120:
%736 = llvm.load %731 : !llvm.ptr -> i64
%737 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%738 = llvm.load %737 : !llvm.ptr -> i64
%739 = arith.addi %736, %738 : i64
llvm.store %739, %731 : i64, !llvm.ptr
cf.br ^bb122
^bb121:
cf.br ^bb122
^bb122:
%740 = arith.constant 0 : i32
%741 = llvm.mlir.constant(1 : i64) : i64
%742 = llvm.alloca %741 x i32 : (i64) -> !llvm.ptr
llvm.store %740, %742 : i32, !llvm.ptr
cf.br ^bb123
^bb123:
%743 = llvm.load %742 : !llvm.ptr -> i32
%744 = llvm.mlir.addressof @ORDER_EXP : !llvm.ptr
%745 = llvm.load %744 : !llvm.ptr -> i32
%746 = arith.cmpi slt, %743, %745 : i32
cf.cond_br %746, ^bb124, ^bb125
^bb124:
%747 = arith.constant 1 : i32
%748 = arith.extsi %747 : i32 to i64
%749 = llvm.mlir.addressof @ORDER_EXP : !llvm.ptr
%750 = llvm.load %749 : !llvm.ptr -> i32
%751 = arith.constant 1 : i32
%752 = arith.subi %750, %751 : i32
%753 = llvm.load %742 : !llvm.ptr -> i32
%754 = arith.subi %752, %753 : i32
%756 = arith.extsi %754 : i32 to i64
%755 = arith.shli %748, %756 : i64
%758 = llvm.load %731 : !llvm.ptr -> i64
%757 = func.call @powmod48(%758, %755) : (i64, i64) -> i64
%759 = llvm.mlir.addressof @G_ORDER : !llvm.ptr
%760 = llvm.load %759 : !llvm.ptr -> i64
%761 = arith.cmpi eq, %757, %760 : i64
cf.cond_br %761, ^bb126, ^bb127
^bb126:
%762 = llvm.load %726 : !llvm.ptr -> i64
%763 = arith.constant 1 : i32
%764 = arith.extsi %763 : i32 to i64
%765 = llvm.load %742 : !llvm.ptr -> i32
%767 = arith.extsi %765 : i32 to i64
%766 = arith.shli %764, %767 : i64
%768 = arith.ori %762, %766 : i64
llvm.store %768, %726 : i64, !llvm.ptr
%770 = llvm.load %731 : !llvm.ptr -> i64
%772 = llvm.mlir.addressof @inv_pows : !llvm.ptr
%773 = llvm.load %772 : !llvm.ptr -> !llvm.ptr
%774 = llvm.load %742 : !llvm.ptr -> i32
%775 = arith.extsi %774 : i32 to i64
%776 = llvm.getelementptr %773[%775] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%771 = llvm.load %776 : !llvm.ptr -> i64
%769 = func.call @mul48(%770, %771) : (i64, i64) -> i64
llvm.store %769, %731 : i64, !llvm.ptr
cf.br ^bb128
^bb127:
cf.br ^bb128
^bb128:
%777 = llvm.load %742 : !llvm.ptr -> i32
%778 = arith.constant 1 : i32
%779 = arith.addi %777, %778 : i32
llvm.store %779, %742 : i32, !llvm.ptr
cf.br ^bb123
^bb125:
%780 = llvm.load %726 : !llvm.ptr -> i64
func.return %780 : i64
}
func.func @powA_sumY(%arg0: i64) -> () {
%781 = arith.constant 0 : i32
%783 = arith.extsi %781 : i32 to i64
%782 = arith.cmpi eq, %arg0, %783 : i64
cf.cond_br %782, ^bb129, ^bb130
^bb129:
%784 = arith.constant 1 : i32
%785 = arith.extsi %784 : i32 to i64
%786 = llvm.mlir.addressof @g_powv : !llvm.ptr
llvm.store %785, %786 : i64, !llvm.ptr
%787 = arith.constant 0 : i32
%788 = arith.extsi %787 : i32 to i64
%789 = llvm.mlir.addressof @g_sumv : !llvm.ptr
llvm.store %788, %789 : i64, !llvm.ptr
func.return
^bb130:
cf.br ^bb131
^bb131:
%790 = arith.constant 1 : i32
%791 = arith.extsi %790 : i32 to i64
%792 = llvm.mlir.constant(1 : i64) : i64
%793 = llvm.alloca %792 x i64 : (i64) -> !llvm.ptr
llvm.store %791, %793 : i64, !llvm.ptr
%794 = arith.constant 0 : i32
%795 = arith.extsi %794 : i32 to i64
%796 = llvm.mlir.constant(1 : i64) : i64
%797 = llvm.alloca %796 x i64 : (i64) -> !llvm.ptr
llvm.store %795, %797 : i64, !llvm.ptr
%798 = arith.constant 63 : i32
%799 = llvm.mlir.constant(1 : i64) : i64
%800 = llvm.alloca %799 x i32 : (i64) -> !llvm.ptr
llvm.store %798, %800 : i32, !llvm.ptr
cf.br ^bb132
^bb132:
%801 = llvm.load %800 : !llvm.ptr -> i32
%803 = arith.extsi %801 : i32 to i64
%802 = arith.shrsi %arg0, %803 : i64
%804 = arith.constant 2 : i32
%806 = arith.extsi %804 : i32 to i64
%805 = arith.remsi %802, %806 : i64
%807 = arith.constant 0 : i32
%809 = arith.extsi %807 : i32 to i64
%808 = arith.cmpi eq, %805, %809 : i64
cf.cond_br %808, ^bb133, ^bb134
^bb133:
%810 = llvm.load %800 : !llvm.ptr -> i32
%811 = arith.constant 1 : i32
%812 = arith.subi %810, %811 : i32
llvm.store %812, %800 : i32, !llvm.ptr
cf.br ^bb132
^bb134:
%813 = llvm.load %800 : !llvm.ptr -> i32
%814 = llvm.mlir.constant(1 : i64) : i64
%815 = llvm.alloca %814 x i32 : (i64) -> !llvm.ptr
llvm.store %813, %815 : i32, !llvm.ptr
cf.br ^bb135
^bb135:
%816 = llvm.load %815 : !llvm.ptr -> i32
%817 = arith.constant 0 : i32
%818 = arith.cmpi sge, %816, %817 : i32
cf.cond_br %818, ^bb136, ^bb137
^bb136:
%819 = arith.constant 1 : i32
%820 = llvm.load %793 : !llvm.ptr -> i64
%822 = arith.extsi %819 : i32 to i64
%821 = arith.addi %822, %820 : i64
%823 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%824 = llvm.load %823 : !llvm.ptr -> i64
%825 = arith.remsi %821, %824 : i64
%827 = llvm.load %797 : !llvm.ptr -> i64
%826 = func.call @mul48(%827, %825) : (i64, i64) -> i64
llvm.store %826, %797 : i64, !llvm.ptr
%829 = llvm.load %793 : !llvm.ptr -> i64
%830 = llvm.load %793 : !llvm.ptr -> i64
%828 = func.call @mul48(%829, %830) : (i64, i64) -> i64
llvm.store %828, %793 : i64, !llvm.ptr
%831 = llvm.load %815 : !llvm.ptr -> i32
%833 = arith.extsi %831 : i32 to i64
%832 = arith.shrsi %arg0, %833 : i64
%834 = arith.constant 2 : i32
%836 = arith.extsi %834 : i32 to i64
%835 = arith.remsi %832, %836 : i64
%837 = arith.constant 1 : i32
%839 = arith.extsi %837 : i32 to i64
%838 = arith.cmpi eq, %835, %839 : i64
cf.cond_br %838, ^bb138, ^bb139
^bb138:
%840 = llvm.load %797 : !llvm.ptr -> i64
%841 = llvm.load %793 : !llvm.ptr -> i64
%842 = arith.addi %840, %841 : i64
%843 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%844 = llvm.load %843 : !llvm.ptr -> i64
%845 = arith.remsi %842, %844 : i64
llvm.store %845, %797 : i64, !llvm.ptr
%847 = llvm.load %793 : !llvm.ptr -> i64
%848 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%849 = llvm.load %848 : !llvm.ptr -> i64
%846 = func.call @mul48(%847, %849) : (i64, i64) -> i64
llvm.store %846, %793 : i64, !llvm.ptr
cf.br ^bb140
^bb139:
cf.br ^bb140
^bb140:
%850 = llvm.load %815 : !llvm.ptr -> i32
%851 = arith.constant 1 : i32
%852 = arith.subi %850, %851 : i32
llvm.store %852, %815 : i32, !llvm.ptr
cf.br ^bb135
^bb137:
%853 = llvm.load %793 : !llvm.ptr -> i64
%854 = llvm.mlir.addressof @g_powv : !llvm.ptr
llvm.store %853, %854 : i64, !llvm.ptr
%855 = llvm.load %797 : !llvm.ptr -> i64
%856 = llvm.mlir.addressof @g_sumv : !llvm.ptr
llvm.store %855, %856 : i64, !llvm.ptr
func.return
}
func.func @index_of_state(%arg0: i64, %arg1: i64) -> i64 {
%857 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%858 = llvm.load %857 : !llvm.ptr -> i64
%859 = arith.remsi %arg0, %858 : i64
%860 = arith.constant 0 : i32
%862 = arith.extsi %860 : i32 to i64
%861 = arith.cmpi slt, %859, %862 : i64
%863 = scf.if %861 -> (i64) {
%864 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%865 = llvm.load %864 : !llvm.ptr -> i64
%866 = arith.addi %859, %865 : i64
scf.yield %866 : i64
} else {
scf.yield %859 : i64
}
%867 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%868 = llvm.load %867 : !llvm.ptr -> i64
%869 = arith.remsi %arg1, %868 : i64
%870 = arith.constant 0 : i32
%872 = arith.extsi %870 : i32 to i64
%871 = arith.cmpi slt, %869, %872 : i64
%873 = scf.if %871 -> (i64) {
%874 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%875 = llvm.load %874 : !llvm.ptr -> i64
%876 = arith.addi %869, %875 : i64
scf.yield %876 : i64
} else {
scf.yield %869 : i64
}
%877 = arith.cmpi eq, %873, %863 : i64
cf.cond_br %877, ^bb141, ^bb142
^bb141:
%878 = arith.constant 0 : i32
%879 = arith.extsi %878 : i32 to i64
func.return %879 : i64
^bb142:
cf.br ^bb143
^bb143:
%880 = func.call @step48(%863) : (i64) -> i64
%881 = arith.subi %880, %863 : i64
%882 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%883 = llvm.load %882 : !llvm.ptr -> i64
%884 = arith.remsi %881, %883 : i64
%885 = llvm.mlir.constant(1 : i64) : i64
%886 = llvm.alloca %885 x i64 : (i64) -> !llvm.ptr
llvm.store %884, %886 : i64, !llvm.ptr
%887 = llvm.load %886 : !llvm.ptr -> i64
%888 = arith.constant 0 : i32
%890 = arith.extsi %888 : i32 to i64
%889 = arith.cmpi slt, %887, %890 : i64
cf.cond_br %889, ^bb144, ^bb145
^bb144:
%891 = llvm.load %886 : !llvm.ptr -> i64
%892 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%893 = llvm.load %892 : !llvm.ptr -> i64
%894 = arith.addi %891, %893 : i64
llvm.store %894, %886 : i64, !llvm.ptr
cf.br ^bb146
^bb145:
cf.br ^bb146
^bb146:
%896 = llvm.load %886 : !llvm.ptr -> i64
%895 = func.call @invmod48(%896) : (i64) -> i64
%897 = arith.subi %873, %863 : i64
%898 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%899 = llvm.load %898 : !llvm.ptr -> i64
%900 = arith.remsi %897, %899 : i64
%901 = llvm.mlir.constant(1 : i64) : i64
%902 = llvm.alloca %901 x i64 : (i64) -> !llvm.ptr
llvm.store %900, %902 : i64, !llvm.ptr
%903 = llvm.load %902 : !llvm.ptr -> i64
%904 = arith.constant 0 : i32
%906 = arith.extsi %904 : i32 to i64
%905 = arith.cmpi slt, %903, %906 : i64
cf.cond_br %905, ^bb147, ^bb148
^bb147:
%907 = llvm.load %902 : !llvm.ptr -> i64
%908 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%909 = llvm.load %908 : !llvm.ptr -> i64
%910 = arith.addi %907, %909 : i64
llvm.store %910, %902 : i64, !llvm.ptr
cf.br ^bb149
^bb148:
cf.br ^bb149
^bb149:
%912 = llvm.load %902 : !llvm.ptr -> i64
%911 = func.call @mul48(%912, %895) : (i64, i64) -> i64
%914 = llvm.mlir.addressof @A_VAL : !llvm.ptr
%915 = llvm.load %914 : !llvm.ptr -> i64
%916 = arith.constant 1 : i32
%918 = arith.extsi %916 : i32 to i64
%917 = arith.subi %915, %918 : i64
%913 = func.call @mul48(%917, %911) : (i64, i64) -> i64
%919 = arith.constant 1 : i32
%921 = arith.extsi %919 : i32 to i64
%920 = arith.addi %913, %921 : i64
%922 = llvm.mlir.addressof @MOD48 : !llvm.ptr
%923 = llvm.load %922 : !llvm.ptr -> i64
%924 = arith.remsi %920, %923 : i64
%925 = func.call @dlog_pow2(%924) : (i64) -> i64
%926 = arith.constant 1 : i32
%927 = arith.extsi %926 : i32 to i64
%928 = llvm.mlir.addressof @ORDER_EXP : !llvm.ptr
%929 = llvm.load %928 : !llvm.ptr -> i32
%931 = arith.extsi %929 : i32 to i64
%930 = arith.shli %927, %931 : i64
%932 = arith.constant 0 : i32
%933 = llvm.mlir.constant(1 : i64) : i64
%934 = llvm.alloca %933 x i32 : (i64) -> !llvm.ptr
llvm.store %932, %934 : i32, !llvm.ptr
cf.br ^bb150
^bb150:
%935 = llvm.load %934 : !llvm.ptr -> i32
%936 = arith.constant 4 : i32
%937 = arith.cmpi slt, %935, %936 : i32
cf.cond_br %937, ^bb151, ^bb152
^bb151:
%938 = llvm.load %934 : !llvm.ptr -> i32
%939 = arith.extsi %938 : i32 to i64
%940 = arith.muli %939, %930 : i64
%941 = arith.addi %925, %940 : i64
func.call @powA_sumY(%941) : (i64) -> ()
%943 = llvm.mlir.addressof @g_sumv : !llvm.ptr
%944 = llvm.load %943 : !llvm.ptr -> i64
%945 = arith.cmpi eq, %944, %911 : i64
cf.cond_br %945, ^bb153, ^bb154
^bb153:
func.return %941 : i64
^bb154:
cf.br ^bb155
^bb155:
%946 = llvm.load %934 : !llvm.ptr -> i32
%947 = arith.constant 1 : i32
%948 = arith.addi %946, %947 : i32
llvm.store %948, %934 : i32, !llvm.ptr
cf.br ^bb150
^bb152:
%949 = arith.constant 0 : i32
%950 = arith.extsi %949 : i32 to i64
func.return %950 : i64
}
func.func @main() -> i32 {
func.call @precompute_dlog() : () -> ()
%953 = arith.constant 64 : i32
%954 = arith.constant 4 : i32
%955 = arith.extsi %953 : i32 to i64
%956 = arith.extsi %954 : i32 to i64
%952 = func.call @calloc(%955, %956) : (i64, i64) -> !llvm.ptr
%957 = arith.constant 41 : i32
%958 = arith.constant 0 : i32
%959 = arith.extsi %958 : i32 to i64
%960 = llvm.getelementptr %952[%959] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %957, %960 : i32, !llvm.ptr
%961 = arith.constant 20 : i32
%962 = arith.constant 1 : i32
%963 = arith.extsi %962 : i32 to i64
%964 = llvm.getelementptr %952[%963] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %961, %964 : i32, !llvm.ptr
%965 = arith.constant 25 : i32
%966 = arith.constant 2 : i32
%967 = arith.extsi %966 : i32 to i64
%968 = llvm.getelementptr %952[%967] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %965, %968 : i32, !llvm.ptr
%969 = arith.constant 25 : i32
%970 = arith.constant 3 : i32
%971 = arith.extsi %970 : i32 to i64
%972 = llvm.getelementptr %952[%971] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %969, %972 : i32, !llvm.ptr
%973 = arith.constant 11 : i32
%974 = arith.constant 4 : i32
%975 = arith.extsi %974 : i32 to i64
%976 = llvm.getelementptr %952[%975] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %973, %976 : i32, !llvm.ptr
%977 = arith.constant 4 : i32
%978 = arith.constant 5 : i32
%979 = arith.extsi %978 : i32 to i64
%980 = llvm.getelementptr %952[%979] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %977, %980 : i32, !llvm.ptr
%981 = arith.constant 40 : i32
%982 = arith.constant 6 : i32
%983 = arith.extsi %982 : i32 to i64
%984 = llvm.getelementptr %952[%983] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %981, %984 : i32, !llvm.ptr
%985 = arith.constant 13 : i32
%986 = arith.constant 7 : i32
%987 = arith.extsi %986 : i32 to i64
%988 = llvm.getelementptr %952[%987] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %985, %988 : i32, !llvm.ptr
%989 = arith.constant 4 : i32
%990 = arith.constant 8 : i32
%991 = arith.extsi %990 : i32 to i64
%992 = llvm.getelementptr %952[%991] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %989, %992 : i32, !llvm.ptr
%994 = arith.constant 16 : i32
%995 = arith.constant 8 : i32
%996 = arith.extsi %994 : i32 to i64
%997 = arith.extsi %995 : i32 to i64
%993 = func.call @calloc(%996, %997) : (i64, i64) -> !llvm.ptr
%999 = arith.constant 9 : i32
%1000 = arith.constant 16 : i32
%998 = func.call @solve_states(%952, %999, %993, %1000) : (!llvm.ptr, i32, !llvm.ptr, i32) -> i32
%1002 = arith.constant 0 : i32
%1003 = arith.extsi %1002 : i32 to i64
%1004 = llvm.getelementptr %993[%1003] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1001 = llvm.load %1004 : !llvm.ptr -> i64
%1006 = arith.constant 64 : i32
%1007 = arith.constant 4 : i32
%1008 = arith.extsi %1006 : i32 to i64
%1009 = arith.extsi %1007 : i32 to i64
%1005 = func.call @calloc(%1008, %1009) : (i64, i64) -> !llvm.ptr
%1010 = arith.constant 37 : i32
%1011 = arith.constant 0 : i32
%1012 = arith.extsi %1011 : i32 to i64
%1013 = llvm.getelementptr %1005[%1012] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1010, %1013 : i32, !llvm.ptr
%1014 = arith.constant 20 : i32
%1015 = arith.constant 1 : i32
%1016 = arith.extsi %1015 : i32 to i64
%1017 = llvm.getelementptr %1005[%1016] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1014, %1017 : i32, !llvm.ptr
%1018 = arith.constant 2 : i32
%1019 = arith.constant 2 : i32
%1020 = arith.extsi %1019 : i32 to i64
%1021 = llvm.getelementptr %1005[%1020] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1018, %1021 : i32, !llvm.ptr
%1022 = arith.constant 10 : i32
%1023 = arith.constant 3 : i32
%1024 = arith.extsi %1023 : i32 to i64
%1025 = llvm.getelementptr %1005[%1024] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1022, %1025 : i32, !llvm.ptr
%1026 = arith.constant 24 : i32
%1027 = arith.constant 4 : i32
%1028 = arith.extsi %1027 : i32 to i64
%1029 = llvm.getelementptr %1005[%1028] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1026, %1029 : i32, !llvm.ptr
%1030 = arith.constant 45 : i32
%1031 = arith.constant 5 : i32
%1032 = arith.extsi %1031 : i32 to i64
%1033 = llvm.getelementptr %1005[%1032] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1030, %1033 : i32, !llvm.ptr
%1034 = arith.constant 4 : i32
%1035 = arith.constant 6 : i32
%1036 = arith.extsi %1035 : i32 to i64
%1037 = llvm.getelementptr %1005[%1036] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1034, %1037 : i32, !llvm.ptr
%1038 = arith.constant 23 : i32
%1039 = arith.constant 7 : i32
%1040 = arith.extsi %1039 : i32 to i64
%1041 = llvm.getelementptr %1005[%1040] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1038, %1041 : i32, !llvm.ptr
%1042 = arith.constant 19 : i32
%1043 = arith.constant 8 : i32
%1044 = arith.extsi %1043 : i32 to i64
%1045 = llvm.getelementptr %1005[%1044] : (!llvm.ptr, i64) -> !llvm.ptr, i32
llvm.store %1042, %1045 : i32, !llvm.ptr
%1047 = arith.constant 256 : i32
%1048 = arith.constant 8 : i32
%1049 = arith.extsi %1047 : i32 to i64
%1050 = arith.extsi %1048 : i32 to i64
%1046 = func.call @calloc(%1049, %1050) : (i64, i64) -> !llvm.ptr
%1052 = arith.constant 9 : i32
%1053 = arith.constant 256 : i32
%1051 = func.call @solve_states(%1005, %1052, %1046, %1053) : (!llvm.ptr, i32, !llvm.ptr, i32) -> i32
%1054 = arith.constant 0 : i32
%1055 = arith.extsi %1054 : i32 to i64
%1056 = llvm.mlir.constant(1 : i64) : i64
%1057 = llvm.alloca %1056 x i64 : (i64) -> !llvm.ptr
llvm.store %1055, %1057 : i64, !llvm.ptr
%1058 = arith.constant 0 : i1
%1059 = llvm.mlir.constant(1 : i64) : i64
%1060 = llvm.alloca %1059 x i1 : (i64) -> !llvm.ptr
llvm.store %1058, %1060 : i1, !llvm.ptr
%1061 = arith.constant 0 : i32
%1062 = llvm.mlir.constant(1 : i64) : i64
%1063 = llvm.alloca %1062 x i32 : (i64) -> !llvm.ptr
llvm.store %1061, %1063 : i32, !llvm.ptr
cf.br ^bb156
^bb156:
%1064 = llvm.load %1063 : !llvm.ptr -> i32
%1065 = arith.cmpi slt, %1064, %1051 : i32
cf.cond_br %1065, ^bb157, ^bb158
^bb157:
%1068 = llvm.load %1063 : !llvm.ptr -> i32
%1069 = arith.extsi %1068 : i32 to i64
%1070 = llvm.getelementptr %1046[%1069] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%1067 = llvm.load %1070 : !llvm.ptr -> i64
%1066 = func.call @index_of_state(%1001, %1067) : (i64, i64) -> i64
%1071 = llvm.load %1060 : !llvm.ptr -> i1
%1073 = arith.constant 1 : i1
%1072 = arith.xori %1071, %1073 : i1
%1075 = scf.if %1072 -> (i1) {
%1076 = arith.constant true
scf.yield %1076 : i1
} else {
%1077 = llvm.load %1057 : !llvm.ptr -> i64
%1078 = arith.cmpi slt, %1066, %1077 : i64
scf.yield %1078 : i1
}
cf.cond_br %1075, ^bb159, ^bb160
^bb159:
llvm.store %1066, %1057 : i64, !llvm.ptr
%1079 = arith.constant 1 : i1
llvm.store %1079, %1060 : i1, !llvm.ptr
cf.br ^bb161
^bb160:
cf.br ^bb161
^bb161:
%1080 = llvm.load %1063 : !llvm.ptr -> i32
%1081 = arith.constant 1 : i32
%1082 = arith.addi %1080, %1081 : i32
llvm.store %1082, %1063 : i32, !llvm.ptr
cf.br ^bb156
^bb158:
%1083 = llvm.mlir.addressof @str_0 : !llvm.ptr
%1084 = llvm.load %1057 : !llvm.ptr -> i64
%1085 = llvm.call @printf(%1083, %1084) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%952) : (!llvm.ptr) -> ()
func.call @free(%993) : (!llvm.ptr) -> ()
func.call @free(%1005) : (!llvm.ptr) -> ()
func.call @free(%1046) : (!llvm.ptr) -> ()
%1091 = llvm.mlir.addressof @inv_pows : !llvm.ptr
%1092 = llvm.load %1091 : !llvm.ptr -> !llvm.ptr
func.call @free(%1092) : (!llvm.ptr) -> ()
%1093 = arith.constant 0 : i32
func.return %1093 : i32
}
}