← All problems Problem 890
p(n) = number of partitions of n into powers of 2. p(2m) = p(2m+1) = S(m) = [x^m] A(x) where A(x) = prod_{k>=0} (1+x^{2^k})^{k+2}. Carry-DP in base 2 with direct convolution (i128 accumulation). Replaces GMP with manual bignum (base 2^64) for 7^777 computation, and direct O(n^2) convolution for the polynomial multiplication.
View problem on Project Euler
Performance comparison
Metric Our solution Best known
Time complexity O(n^2)O(n * m)Space complexity O(n^2)O(n)Approach Flow solution Dynamic programming or generating function Verdict Unknown
Flow source
# Project Euler 890: Binary Partitions
# p(n) = number of partitions of n into powers of 2.
# p(2m) = p(2m+1) = S(m) = [x^m] A(x) where A(x) = prod_{k>=0} (1+x^{2^k})^{k+2}.
# Carry-DP in base 2 with direct convolution (i128 accumulation).
#
# Replaces GMP with manual bignum (base 2^64) for 7^777 computation,
# and direct O(n^2) convolution for the polynomial multiplication.
extern {
function calloc(n: i64, size: i64) -> ptr<void>
function malloc(n: i64) -> ptr<void>
function free(p: ptr<void>) -> void
}
const MOD: i64 = 1000000007
const BN_LIMBS: i32 = 40
# ---- bignum (base 2^64, little-endian) ----
function bn_zero(a: ptr<u64>, nl: i32) -> void {
for i in 0..nl { a[i] = 0 }
}
function bn_set_val(a: ptr<u64>, v: i64, nl: i32) -> void {
bn_zero(a, nl)
a[0] = v as u64
}
function bn_mul_small(dst: ptr<u64>, a: ptr<u64>, m: i64, nl: i32) -> void {
let mu: u64 = m as u64
let mut carry: u64 = 0
for i in 0..nl {
let prod: i128 = (a[i] as i128) * (mu as i128) + (carry as i128)
dst[i] = prod as u64
carry = (prod >> 64) as u64
}
}
function bn_shr1(dst: ptr<u64>, src: ptr<u64>, nl: i32) -> void {
for i in 0..(nl - 1) {
dst[i] = (src[i] >> 1) | (src[i + 1] << 63)
}
dst[nl - 1] = src[nl - 1] >> 1
}
function bn_bit_len(a: ptr<u64>, nl: i32) -> i32 {
let mut i: i32 = nl - 1
while i >= 0 {
if a[i] != 0 {
let mut bits: i32 = i * 64
let mut v: u64 = a[i]
while v != 0 {
bits = bits + 1
v = v >> 1
}
return bits
}
i = i - 1
}
return 0
}
function bn_get_bit(a: ptr<u64>, k: i32) -> i32 {
let limb: i32 = k / 64
let bit: i32 = k % 64
return ((a[limb] >> bit) & 1) as i32
}
# ---- modular arithmetic ----
function mulmod(a: i64, b: i64, m: i64) -> i64 {
return ((a as i128 * b as i128) % (m as i128)) as i64
}
function mod_pow(base: i64, exp: i64, modv: i64) -> i64 {
if modv == 1 { return 0 }
let mut result: i64 = 1
let mut b: i64 = base % modv
let mut e: i64 = exp
while e > 0 {
if e % 2 == 1 { result = mulmod(result, b, modv) }
b = mulmod(b, b, modv)
e = e / 2
}
return result
}
# ---- factorials ----
let mut fact: ptr<i64> = null
let mut invfact: ptr<i64> = null
function prepare_factorials(nmax: i32) -> void {
fact[0] = 1
for i in 1..(nmax + 1) {
fact[i] = mulmod(fact[i - 1], i as i64, MOD)
}
invfact[nmax] = mod_pow(fact[nmax], MOD - 2, MOD)
let mut i: i32 = nmax
while i >= 1 {
invfact[i - 1] = mulmod(invfact[i], i as i64, MOD)
i = i - 1
}
}
function binom_row(top: i32, row: ptr<i64>) -> void {
for j in 0..(top + 1) {
row[j] = mulmod(fact[top], mulmod(invfact[j], invfact[top - j], MOD), MOD)
}
}
# ---- direct convolution with decimation ----
# Convolve a[0..la-1] and b[0..lb-1], then take indices bit, bit+2, ...
# Results reduced mod MOD.
function convolve_and_decimate(a: ptr<i64>, la: i32, b: ptr<i64>, lb: i32, bit: i32, res: ptr<i64>) -> i32 {
let out_len: i32 = la + lb - 1
let res_len: i32 = (out_len - bit + 1) / 2
for i in 0..res_len {
res[i] = 0
}
for k in 0..out_len {
let mut sum: i128 = 0
let jmin: i32 = if k - lb + 1 > 0 { k - lb + 1 } else { 0 }
let jmax: i32 = if k < la - 1 { k } else { la - 1 }
for j in jmin..(jmax + 1) {
sum = sum + (a[j] as i128) * (b[k - j] as i128)
}
let val: i64 = (sum % (MOD as i128)) as i64
if k >= bit && ((k - bit) % 2) == 0 {
res[(k - bit) / 2] = val
}
}
return res_len
}
function main() -> i32 {
# Compute 7^777 as bignum
let n_val: ptr<u64> = calloc(BN_LIMBS as i64, 8) as ptr<u64>
let tmp_bn: ptr<u64> = calloc(BN_LIMBS as i64, 8) as ptr<u64>
bn_set_val(n_val, 1, BN_LIMBS)
for i in 0..777 {
bn_mul_small(tmp_bn, n_val, 7, BN_LIMBS)
for j in 0..BN_LIMBS { n_val[j] = tmp_bn[j] }
}
# m = n >> 1
let m_val: ptr<u64> = calloc(BN_LIMBS as i64, 8) as ptr<u64>
bn_shr1(m_val, n_val, BN_LIMBS)
let L: i32 = bn_bit_len(m_val, BN_LIMBS)
let max_m: i32 = L + 2
let cap: i32 = L + 10
# Prepare factorials
fact = calloc(2500, 8) as ptr<i64>
invfact = calloc(2500, 8) as ptr<i64>
prepare_factorials(max_m)
# DP arrays
let dp: ptr<i64> = calloc(cap, 8) as ptr<i64>
let new_dp: ptr<i64> = calloc(cap, 8) as ptr<i64>
let row: ptr<i64> = calloc(2500, 8) as ptr<i64>
let mut dp_len: i32 = 1
dp[0] = 1
for k in 0..L {
let bit: i32 = bn_get_bit(m_val, k)
let top: i32 = k + 2
binom_row(top, row)
let new_len: i32 = convolve_and_decimate(dp, dp_len, row, top + 1, bit, new_dp)
for j in 0..new_len { dp[j] = new_dp[j] }
dp_len = new_len
}
let result: i64 = dp[0] % MOD
printf("%lld\n", result)
free(n_val as ptr<void>)
free(tmp_bn as ptr<void>)
free(m_val as ptr<void>)
free(fact as ptr<void>)
free(invfact as ptr<void>)
free(dp as ptr<void>)
free(new_dp as ptr<void>)
free(row as ptr<void>)
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; }
void bn_zero_ptr_u64_i32(uint64_t* a, int32_t nl);
void bn_set_val_ptr_u64_i64_i32(uint64_t* a, int64_t v, int32_t nl);
void bn_mul_small_ptr_u64_ptr_u64_i64_i32(uint64_t* dst, uint64_t* a, int64_t m, int32_t nl);
void bn_shr1_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* src, int32_t nl);
int32_t bn_bit_len_ptr_u64_i32(uint64_t* a, int32_t nl);
int32_t bn_get_bit_ptr_u64_i32(uint64_t* a, int32_t k);
int64_t mulmod_i64_i64_i64(int64_t a, int64_t b, int64_t m);
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t modv);
void prepare_factorials_i32(int32_t nmax);
void binom_row_i32_ptr_i64(int32_t top, int64_t* row);
int32_t convolve_and_decimate_ptr_i64_i32_ptr_i64_i32_i32_ptr_i64(int64_t* a, int32_t la, int64_t* b, int32_t lb, int32_t bit, int64_t* res);
int32_t main(void);
static const int64_t MOD = 1000000007;
static const int32_t BN_LIMBS = 40;
/* Module statics */
static int64_t* fact = NULL;
static int64_t* invfact = NULL;
void bn_zero_ptr_u64_i32(uint64_t* a, int32_t nl) {
int32_t __flow_step_1 = 1;
for (int32_t i = 0; (0 <= nl) ? i < nl : i > nl; i += (0 <= nl) ? 1 : -1) {
a[i] = 0;
}
}
void bn_set_val_ptr_u64_i64_i32(uint64_t* a, int64_t v, int32_t nl) {
bn_zero_ptr_u64_i32(a, nl);
a[0] = ((uint64_t)(v));
}
void bn_mul_small_ptr_u64_ptr_u64_i64_i32(uint64_t* dst, uint64_t* a, int64_t m, int32_t nl) {
uint64_t mu = ((uint64_t)(m));
uint64_t carry = 0;
int32_t __flow_step_2 = 1;
for (int32_t i = 0; (0 <= nl) ? i < nl : i > nl; i += (0 <= nl) ? 1 : -1) {
__int128 prod = ((((__int128)(a[i])) * ((__int128)(mu))) + ((__int128)(carry)));
dst[i] = ((uint64_t)(prod));
carry = ((uint64_t)(FLOW_CHECKED_SHR((prod), (64))));
}
}
void bn_shr1_ptr_u64_ptr_u64_i32(uint64_t* dst, uint64_t* src, int32_t nl) {
int32_t __flow_step_3 = 1;
for (int32_t i = 0; (0 <= (nl - 1)) ? i < (nl - 1) : i > (nl - 1); i += (0 <= (nl - 1)) ? 1 : -1) {
dst[i] = (FLOW_CHECKED_SHR((src[i]), (1)) | FLOW_CHECKED_SHL((src[(i + 1)]), (63)));
}
dst[(nl - 1)] = FLOW_CHECKED_SHR((src[(nl - 1)]), (1));
}
int32_t bn_bit_len_ptr_u64_i32(uint64_t* a, int32_t nl) {
int32_t i = (nl - 1);
while (i >= 0) {
if (a[i] != 0) {
int32_t bits = (i * 64);
uint64_t v = a[i];
while (v != 0) {
bits = (bits + 1);
v = FLOW_CHECKED_SHR((v), (1));
}
return bits;
}
i = (i - 1);
}
return 0;
}
int32_t bn_get_bit_ptr_u64_i32(uint64_t* a, int32_t k) {
int32_t limb = FLOW_CHECKED_DIV((k), (64));
int32_t bit = FLOW_CHECKED_MOD((k), (64));
return ((int32_t)((FLOW_CHECKED_SHR((a[limb]), (bit)) & 1)));
}
int64_t mulmod_i64_i64_i64(int64_t a, int64_t b, int64_t m) {
return ((int64_t)(FLOW_CHECKED_MOD(((((__int128)(a)) * ((__int128)(b)))), (((__int128)(m))))));
}
int64_t mod_pow_i64_i64_i64(int64_t base, int64_t exp, int64_t modv) {
if (modv == 1) {
return 0;
}
int64_t result = 1;
int64_t b = FLOW_CHECKED_MOD((base), (modv));
int64_t e = exp;
while (e > 0) {
if (FLOW_CHECKED_MOD((e), (2)) == 1) {
result = mulmod_i64_i64_i64(result, b, modv);
}
b = mulmod_i64_i64_i64(b, b, modv);
e = FLOW_CHECKED_DIV((e), (2));
}
return result;
}
void prepare_factorials_i32(int32_t nmax) {
fact[0] = 1;
int32_t __flow_step_4 = 1;
for (int32_t i = 1; (1 <= (nmax + 1)) ? i < (nmax + 1) : i > (nmax + 1); i += (1 <= (nmax + 1)) ? 1 : -1) {
fact[i] = mulmod_i64_i64_i64(fact[(i - 1)], ((int64_t)(i)), MOD);
}
invfact[nmax] = mod_pow_i64_i64_i64(fact[nmax], (MOD - 2), MOD);
int32_t i = nmax;
while (i >= 1) {
invfact[(i - 1)] = mulmod_i64_i64_i64(invfact[i], ((int64_t)(i)), MOD);
i = (i - 1);
}
}
void binom_row_i32_ptr_i64(int32_t top, int64_t* row) {
int32_t __flow_step_5 = 1;
for (int32_t j = 0; (0 <= (top + 1)) ? j < (top + 1) : j > (top + 1); j += (0 <= (top + 1)) ? 1 : -1) {
row[j] = mulmod_i64_i64_i64(fact[top], mulmod_i64_i64_i64(invfact[j], invfact[(top - j)], MOD), MOD);
}
}
int32_t convolve_and_decimate_ptr_i64_i32_ptr_i64_i32_i32_ptr_i64(int64_t* a, int32_t la, int64_t* b, int32_t lb, int32_t bit, int64_t* res) {
int32_t out_len = ((la + lb) - 1);
int32_t res_len = FLOW_CHECKED_DIV((((out_len - bit) + 1)), (2));
int32_t __flow_step_6 = 1;
for (int32_t i = 0; (0 <= res_len) ? i < res_len : i > res_len; i += (0 <= res_len) ? 1 : -1) {
res[i] = 0;
}
int32_t __flow_step_7 = 1;
for (int32_t k = 0; (0 <= out_len) ? k < out_len : k > out_len; k += (0 <= out_len) ? 1 : -1) {
__int128 sum = 0;
int32_t jmin = ((((k - lb) + 1) > 0) ? (((k - lb) + 1)) : (0));
int32_t jmax = ((k < (la - 1)) ? (k) : ((la - 1)));
int32_t __flow_step_8 = 1;
for (int32_t j = jmin; (jmin <= (jmax + 1)) ? j < (jmax + 1) : j > (jmax + 1); j += (jmin <= (jmax + 1)) ? 1 : -1) {
sum = (sum + (((__int128)(a[j])) * ((__int128)(b[(k - j)]))));
}
int64_t val = ((int64_t)(FLOW_CHECKED_MOD((sum), (((__int128)(MOD))))));
if ((k >= bit && FLOW_CHECKED_MOD(((k - bit)), (2)) == 0)) {
res[FLOW_CHECKED_DIV(((k - bit)), (2))] = val;
}
}
return res_len;
}
int32_t main(void) {
uint64_t* n_val = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(BN_LIMBS)), 8))));
uint64_t* tmp_bn = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(BN_LIMBS)), 8))));
bn_set_val_ptr_u64_i64_i32(n_val, 1, BN_LIMBS);
int32_t __flow_step_9 = 1;
for (int32_t i = 0; (0 <= 777) ? i < 777 : i > 777; i += (0 <= 777) ? 1 : -1) {
bn_mul_small_ptr_u64_ptr_u64_i64_i32(tmp_bn, n_val, 7, BN_LIMBS);
int32_t __flow_step_10 = 1;
for (int32_t j = 0; (0 <= BN_LIMBS) ? j < BN_LIMBS : j > BN_LIMBS; j += (0 <= BN_LIMBS) ? 1 : -1) {
n_val[j] = tmp_bn[j];
}
}
uint64_t* m_val = (uint64_t*)(((uint64_t*)(calloc(((int64_t)(BN_LIMBS)), 8))));
bn_shr1_ptr_u64_ptr_u64_i32(m_val, n_val, BN_LIMBS);
int32_t L = bn_bit_len_ptr_u64_i32(m_val, BN_LIMBS);
int32_t max_m = (L + 2);
int32_t cap = (L + 10);
fact = ((int64_t*)(calloc(2500, 8)));
invfact = ((int64_t*)(calloc(2500, 8)));
prepare_factorials_i32(max_m);
int64_t* dp = (int64_t*)(((int64_t*)(calloc(cap, 8))));
int64_t* new_dp = (int64_t*)(((int64_t*)(calloc(cap, 8))));
int64_t* row = (int64_t*)(((int64_t*)(calloc(2500, 8))));
int32_t dp_len = 1;
dp[0] = 1;
int32_t __flow_step_11 = 1;
for (int32_t k = 0; (0 <= L) ? k < L : k > L; k += (0 <= L) ? 1 : -1) {
int32_t bit = bn_get_bit_ptr_u64_i32(m_val, k);
int32_t top = (k + 2);
binom_row_i32_ptr_i64(top, row);
int32_t new_len = convolve_and_decimate_ptr_i64_i32_ptr_i64_i32_i32_ptr_i64(dp, dp_len, row, (top + 1), bit, new_dp);
int32_t __flow_step_12 = 1;
for (int32_t j = 0; (0 <= new_len) ? j < new_len : j > new_len; j += (0 <= new_len) ? 1 : -1) {
dp[j] = new_dp[j];
}
dp_len = new_len;
}
int64_t result = FLOW_CHECKED_MOD((dp[0]), (MOD));
printf("%lld\n", result);
free(((void*)(n_val)));
free(((void*)(tmp_bn)));
free(((void*)(m_val)));
free(((void*)(fact)));
free(((void*)(invfact)));
free(((void*)(dp)));
free(((void*)(new_dp)));
free(((void*)(row)));
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 @malloc(i64) -> !llvm.ptr
func.func private @free(!llvm.ptr) -> ()
// Constant: MOD
llvm.mlir.global internal constant @MOD(1000000007 : i64) : i64
// Constant: BN_LIMBS
llvm.mlir.global internal constant @BN_LIMBS(40 : i32) : i32
func.func @bn_zero(%arg0: !llvm.ptr, %arg1: i32) -> () {
%0 = arith.constant 0 : i32
%1 = arith.index_cast %0 : i32 to index
%2 = arith.index_cast %arg1 : i32 to index
%4 = arith.constant 1 : index
%5 = arith.constant -1 : index
%6 = arith.cmpi sle, %1, %2 : index
%3 = arith.select %6, %4, %5 : index
cf.br ^bb0(%1 : index)
^bb0(%7: index):
%8 = arith.cmpi slt, %7, %2 : index
%9 = arith.cmpi sgt, %7, %2 : index
%10 = arith.select %6, %8, %9 : i1
cf.cond_br %10, ^bb1(%7 : index), ^bb2(%7 : index)
^bb1(%11: index):
%12 = arith.constant 0 : i32
%13 = arith.extsi %12 : i32 to i64
%14 = arith.index_cast %11 : index to i64
%15 = llvm.getelementptr %arg0[%14] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %13, %15 : i64, !llvm.ptr
%16 = arith.addi %11, %3 : index
cf.br ^bb0(%16 : index)
^bb2(%17: index):
func.return
}
func.func @bn_set_val(%arg0: !llvm.ptr, %arg1: i64, %arg2: i32) -> () {
func.call @bn_zero(%arg0, %arg2) : (!llvm.ptr, i32) -> ()
%19 = arith.constant 0 : i32
%20 = arith.extsi %19 : i32 to i64
%21 = llvm.getelementptr %arg0[%20] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %arg1, %21 : i64, !llvm.ptr
func.return
}
func.func @bn_mul_small(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i64, %arg3: i32) -> () {
%22 = arith.constant 0 : i32
%23 = arith.extsi %22 : i32 to i64
%24 = llvm.mlir.constant(1 : i64) : i64
%25 = llvm.alloca %24 x i64 : (i64) -> !llvm.ptr
llvm.store %23, %25 : i64, !llvm.ptr
%26 = arith.constant 0 : i32
%27 = arith.index_cast %26 : i32 to index
%28 = arith.index_cast %arg3 : i32 to index
%30 = arith.constant 1 : index
%31 = arith.constant -1 : index
%32 = arith.cmpi sle, %27, %28 : index
%29 = arith.select %32, %30, %31 : index
cf.br ^bb3(%27 : index)
^bb3(%33: index):
%34 = arith.cmpi slt, %33, %28 : index
%35 = arith.cmpi sgt, %33, %28 : index
%36 = arith.select %32, %34, %35 : i1
cf.cond_br %36, ^bb4(%33 : index), ^bb5(%33 : index)
^bb4(%37: index):
%39 = arith.index_cast %37 : index to i64
%40 = llvm.getelementptr %arg1[%39] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%38 = llvm.load %40 : !llvm.ptr -> i64
%41 = arith.extui %38 : i64 to i128
%42 = arith.extui %arg2 : i64 to i128
%44 = arith.trunci %41 : i128 to i64
%45 = arith.trunci %42 : i128 to i64
%43 = arith.muli %44, %45 : i64
%46 = llvm.load %25 : !llvm.ptr -> i64
%47 = arith.extui %46 : i64 to i128
%49 = arith.trunci %47 : i128 to i64
%48 = arith.addi %43, %49 : i64
%50 = arith.extsi %48 : i64 to i128
%51 = arith.trunci %50 : i128 to i64
%52 = arith.index_cast %37 : index to i64
%53 = llvm.getelementptr %arg0[%52] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %51, %53 : i64, !llvm.ptr
%54 = arith.constant 64 : i32
%56 = arith.trunci %50 : i128 to i64
%57 = arith.extsi %54 : i32 to i64
%55 = arith.shrsi %56, %57 : i64
llvm.store %55, %25 : i64, !llvm.ptr
%58 = arith.addi %37, %29 : index
cf.br ^bb3(%58 : index)
^bb5(%59: index):
func.return
}
func.func @bn_shr1(%arg0: !llvm.ptr, %arg1: !llvm.ptr, %arg2: i32) -> () {
%60 = arith.constant 0 : i32
%61 = arith.constant 1 : i32
%62 = arith.subi %arg2, %61 : i32
%63 = arith.index_cast %60 : i32 to index
%64 = arith.index_cast %62 : i32 to index
%66 = arith.constant 1 : index
%67 = arith.constant -1 : index
%68 = arith.cmpi sle, %63, %64 : index
%65 = arith.select %68, %66, %67 : index
cf.br ^bb6(%63 : index)
^bb6(%69: index):
%70 = arith.cmpi slt, %69, %64 : index
%71 = arith.cmpi sgt, %69, %64 : index
%72 = arith.select %68, %70, %71 : i1
cf.cond_br %72, ^bb7(%69 : index), ^bb8(%69 : index)
^bb7(%73: index):
%75 = arith.index_cast %73 : index to i64
%76 = llvm.getelementptr %arg1[%75] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%74 = llvm.load %76 : !llvm.ptr -> i64
%77 = arith.constant 1 : i32
%79 = arith.extsi %77 : i32 to i64
%78 = arith.shrui %74, %79 : i64
%81 = arith.constant 1 : i32
%83 = arith.index_cast %73 : index to i32
%82 = arith.addi %83, %81 : i32
%84 = arith.extsi %82 : i32 to i64
%85 = llvm.getelementptr %arg1[%84] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%80 = llvm.load %85 : !llvm.ptr -> i64
%86 = arith.constant 63 : i32
%88 = arith.extsi %86 : i32 to i64
%87 = arith.shli %80, %88 : i64
%89 = arith.ori %78, %87 : i64
%90 = arith.index_cast %73 : index to i64
%91 = llvm.getelementptr %arg0[%90] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %89, %91 : i64, !llvm.ptr
%92 = arith.addi %73, %65 : index
cf.br ^bb6(%92 : index)
^bb8(%93: index):
%95 = arith.constant 1 : i32
%96 = arith.subi %arg2, %95 : i32
%97 = arith.extsi %96 : i32 to i64
%98 = llvm.getelementptr %arg1[%97] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%94 = llvm.load %98 : !llvm.ptr -> i64
%99 = arith.constant 1 : i32
%101 = arith.extsi %99 : i32 to i64
%100 = arith.shrui %94, %101 : i64
%102 = arith.constant 1 : i32
%103 = arith.subi %arg2, %102 : i32
%104 = arith.extsi %103 : i32 to i64
%105 = llvm.getelementptr %arg0[%104] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %100, %105 : i64, !llvm.ptr
func.return
}
func.func @bn_bit_len(%arg0: !llvm.ptr, %arg1: i32) -> i32 {
%106 = arith.constant 1 : i32
%107 = arith.subi %arg1, %106 : i32
%108 = llvm.mlir.constant(1 : i64) : i64
%109 = llvm.alloca %108 x i32 : (i64) -> !llvm.ptr
llvm.store %107, %109 : i32, !llvm.ptr
cf.br ^bb9
^bb9:
%110 = llvm.load %109 : !llvm.ptr -> i32
%111 = arith.constant 0 : i32
%112 = arith.cmpi sge, %110, %111 : i32
cf.cond_br %112, ^bb10, ^bb11
^bb10:
%114 = llvm.load %109 : !llvm.ptr -> i32
%115 = arith.extsi %114 : i32 to i64
%116 = llvm.getelementptr %arg0[%115] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%113 = llvm.load %116 : !llvm.ptr -> i64
%117 = arith.constant 0 : i32
%119 = arith.extsi %117 : i32 to i64
%118 = arith.cmpi ne, %113, %119 : i64
cf.cond_br %118, ^bb12, ^bb13
^bb12:
%120 = llvm.load %109 : !llvm.ptr -> i32
%121 = arith.constant 64 : i32
%122 = arith.muli %120, %121 : i32
%123 = llvm.mlir.constant(1 : i64) : i64
%124 = llvm.alloca %123 x i32 : (i64) -> !llvm.ptr
llvm.store %122, %124 : i32, !llvm.ptr
%126 = llvm.load %109 : !llvm.ptr -> i32
%127 = arith.extsi %126 : i32 to i64
%128 = llvm.getelementptr %arg0[%127] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%125 = llvm.load %128 : !llvm.ptr -> i64
%129 = llvm.mlir.constant(1 : i64) : i64
%130 = llvm.alloca %129 x i64 : (i64) -> !llvm.ptr
llvm.store %125, %130 : i64, !llvm.ptr
cf.br ^bb15
^bb15:
%131 = llvm.load %130 : !llvm.ptr -> i64
%132 = arith.constant 0 : i32
%134 = arith.extsi %132 : i32 to i64
%133 = arith.cmpi ne, %131, %134 : i64
cf.cond_br %133, ^bb16, ^bb17
^bb16:
%135 = llvm.load %124 : !llvm.ptr -> i32
%136 = arith.constant 1 : i32
%137 = arith.addi %135, %136 : i32
llvm.store %137, %124 : i32, !llvm.ptr
%138 = llvm.load %130 : !llvm.ptr -> i64
%139 = arith.constant 1 : i32
%141 = arith.extsi %139 : i32 to i64
%140 = arith.shrui %138, %141 : i64
llvm.store %140, %130 : i64, !llvm.ptr
cf.br ^bb15
^bb17:
%142 = llvm.load %124 : !llvm.ptr -> i32
func.return %142 : i32
^bb13:
cf.br ^bb14
^bb14:
%143 = llvm.load %109 : !llvm.ptr -> i32
%144 = arith.constant 1 : i32
%145 = arith.subi %143, %144 : i32
llvm.store %145, %109 : i32, !llvm.ptr
cf.br ^bb9
^bb11:
%146 = arith.constant 0 : i32
func.return %146 : i32
}
func.func @bn_get_bit(%arg0: !llvm.ptr, %arg1: i32) -> i32 {
%147 = arith.constant 64 : i32
%148 = arith.divsi %arg1, %147 : i32
%149 = arith.constant 64 : i32
%150 = arith.remsi %arg1, %149 : i32
%152 = arith.extsi %148 : i32 to i64
%153 = llvm.getelementptr %arg0[%152] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%151 = llvm.load %153 : !llvm.ptr -> i64
%155 = arith.extsi %150 : i32 to i64
%154 = arith.shrui %151, %155 : i64
%156 = arith.constant 1 : i32
%158 = arith.extsi %156 : i32 to i64
%157 = arith.andi %154, %158 : i64
%159 = arith.trunci %157 : i64 to i32
func.return %159 : i32
}
func.func @mulmod(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%160 = arith.extsi %arg0 : i64 to i128
%161 = arith.extsi %arg1 : i64 to i128
%163 = arith.trunci %160 : i128 to i64
%164 = arith.trunci %161 : i128 to i64
%162 = arith.muli %163, %164 : i64
%165 = arith.extsi %arg2 : i64 to i128
%167 = arith.trunci %165 : i128 to i64
%166 = arith.remsi %162, %167 : i64
func.return %166 : i64
}
func.func @mod_pow(%arg0: i64, %arg1: i64, %arg2: i64) -> i64 {
%168 = arith.constant 1 : i32
%170 = arith.extsi %168 : i32 to i64
%169 = arith.cmpi eq, %arg2, %170 : i64
cf.cond_br %169, ^bb18, ^bb19
^bb18:
%171 = arith.constant 0 : i32
%172 = arith.extsi %171 : i32 to i64
func.return %172 : i64
^bb19:
cf.br ^bb20
^bb20:
%173 = arith.constant 1 : i32
%174 = arith.extsi %173 : i32 to i64
%175 = llvm.mlir.constant(1 : i64) : i64
%176 = llvm.alloca %175 x i64 : (i64) -> !llvm.ptr
llvm.store %174, %176 : i64, !llvm.ptr
%177 = arith.remsi %arg0, %arg2 : i64
%178 = llvm.mlir.constant(1 : i64) : i64
%179 = llvm.alloca %178 x i64 : (i64) -> !llvm.ptr
llvm.store %177, %179 : i64, !llvm.ptr
%180 = llvm.mlir.constant(1 : i64) : i64
%181 = llvm.alloca %180 x i64 : (i64) -> !llvm.ptr
llvm.store %arg1, %181 : i64, !llvm.ptr
cf.br ^bb21
^bb21:
%182 = llvm.load %181 : !llvm.ptr -> i64
%183 = arith.constant 0 : i32
%185 = arith.extsi %183 : i32 to i64
%184 = arith.cmpi sgt, %182, %185 : i64
cf.cond_br %184, ^bb22, ^bb23
^bb22:
%186 = llvm.load %181 : !llvm.ptr -> i64
%187 = arith.constant 2 : i32
%189 = arith.extsi %187 : i32 to i64
%188 = arith.remsi %186, %189 : i64
%190 = arith.constant 1 : i32
%192 = arith.extsi %190 : i32 to i64
%191 = arith.cmpi eq, %188, %192 : i64
cf.cond_br %191, ^bb24, ^bb25
^bb24:
%194 = llvm.load %176 : !llvm.ptr -> i64
%195 = llvm.load %179 : !llvm.ptr -> i64
%193 = func.call @mulmod(%194, %195, %arg2) : (i64, i64, i64) -> i64
llvm.store %193, %176 : i64, !llvm.ptr
cf.br ^bb26
^bb25:
cf.br ^bb26
^bb26:
%197 = llvm.load %179 : !llvm.ptr -> i64
%198 = llvm.load %179 : !llvm.ptr -> i64
%196 = func.call @mulmod(%197, %198, %arg2) : (i64, i64, i64) -> i64
llvm.store %196, %179 : i64, !llvm.ptr
%199 = llvm.load %181 : !llvm.ptr -> i64
%200 = arith.constant 2 : i32
%202 = arith.extsi %200 : i32 to i64
%201 = arith.divsi %199, %202 : i64
llvm.store %201, %181 : i64, !llvm.ptr
cf.br ^bb21
^bb23:
%203 = llvm.load %176 : !llvm.ptr -> i64
func.return %203 : i64
}
// Module static: fact
llvm.mlir.global internal @fact() {addr_space = 0 : i32} : !llvm.ptr {
%204 = llvm.mlir.zero : !llvm.ptr
llvm.return %204 : !llvm.ptr
}
// Module static: invfact
llvm.mlir.global internal @invfact() {addr_space = 0 : i32} : !llvm.ptr {
%205 = llvm.mlir.zero : !llvm.ptr
llvm.return %205 : !llvm.ptr
}
func.func @prepare_factorials(%arg0: i32) -> () {
%206 = arith.constant 1 : i32
%207 = llvm.mlir.addressof @fact : !llvm.ptr
%208 = llvm.load %207 : !llvm.ptr -> !llvm.ptr
%209 = arith.constant 0 : i32
%210 = arith.extsi %206 : i32 to i64
%211 = arith.extsi %209 : i32 to i64
%212 = llvm.getelementptr %208[%211] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %210, %212 : i64, !llvm.ptr
%213 = arith.constant 1 : i32
%214 = arith.constant 1 : i32
%215 = arith.addi %arg0, %214 : i32
%216 = arith.index_cast %213 : i32 to index
%217 = arith.index_cast %215 : i32 to index
%219 = arith.constant 1 : index
%220 = arith.constant -1 : index
%221 = arith.cmpi sle, %216, %217 : index
%218 = arith.select %221, %219, %220 : index
cf.br ^bb27(%216 : index)
^bb27(%222: index):
%223 = arith.cmpi slt, %222, %217 : index
%224 = arith.cmpi sgt, %222, %217 : index
%225 = arith.select %221, %223, %224 : i1
cf.cond_br %225, ^bb28(%222 : index), ^bb29(%222 : index)
^bb28(%226: index):
%229 = llvm.mlir.addressof @fact : !llvm.ptr
%230 = llvm.load %229 : !llvm.ptr -> !llvm.ptr
%231 = arith.constant 1 : i32
%233 = arith.index_cast %226 : index to i32
%232 = arith.subi %233, %231 : i32
%234 = arith.extsi %232 : i32 to i64
%235 = llvm.getelementptr %230[%234] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%228 = llvm.load %235 : !llvm.ptr -> i64
%236 = arith.index_cast %226 : index to i64
%237 = llvm.mlir.addressof @MOD : !llvm.ptr
%238 = llvm.load %237 : !llvm.ptr -> i64
%227 = func.call @mulmod(%228, %236, %238) : (i64, i64, i64) -> i64
%239 = llvm.mlir.addressof @fact : !llvm.ptr
%240 = llvm.load %239 : !llvm.ptr -> !llvm.ptr
%241 = arith.index_cast %226 : index to i64
%242 = llvm.getelementptr %240[%241] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %227, %242 : i64, !llvm.ptr
%243 = arith.addi %226, %218 : index
cf.br ^bb27(%243 : index)
^bb29(%244: index):
%247 = llvm.mlir.addressof @fact : !llvm.ptr
%248 = llvm.load %247 : !llvm.ptr -> !llvm.ptr
%249 = arith.extsi %arg0 : i32 to i64
%250 = llvm.getelementptr %248[%249] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%246 = llvm.load %250 : !llvm.ptr -> i64
%251 = llvm.mlir.addressof @MOD : !llvm.ptr
%252 = llvm.load %251 : !llvm.ptr -> i64
%253 = arith.constant 2 : i32
%255 = arith.extsi %253 : i32 to i64
%254 = arith.subi %252, %255 : i64
%256 = llvm.mlir.addressof @MOD : !llvm.ptr
%257 = llvm.load %256 : !llvm.ptr -> i64
%245 = func.call @mod_pow(%246, %254, %257) : (i64, i64, i64) -> i64
%258 = llvm.mlir.addressof @invfact : !llvm.ptr
%259 = llvm.load %258 : !llvm.ptr -> !llvm.ptr
%260 = arith.extsi %arg0 : i32 to i64
%261 = llvm.getelementptr %259[%260] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %245, %261 : i64, !llvm.ptr
%262 = llvm.mlir.constant(1 : i64) : i64
%263 = llvm.alloca %262 x i32 : (i64) -> !llvm.ptr
llvm.store %arg0, %263 : i32, !llvm.ptr
cf.br ^bb30
^bb30:
%264 = llvm.load %263 : !llvm.ptr -> i32
%265 = arith.constant 1 : i32
%266 = arith.cmpi sge, %264, %265 : i32
cf.cond_br %266, ^bb31, ^bb32
^bb31:
%269 = llvm.mlir.addressof @invfact : !llvm.ptr
%270 = llvm.load %269 : !llvm.ptr -> !llvm.ptr
%271 = llvm.load %263 : !llvm.ptr -> i32
%272 = arith.extsi %271 : i32 to i64
%273 = llvm.getelementptr %270[%272] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%268 = llvm.load %273 : !llvm.ptr -> i64
%274 = llvm.load %263 : !llvm.ptr -> i32
%275 = arith.extsi %274 : i32 to i64
%276 = llvm.mlir.addressof @MOD : !llvm.ptr
%277 = llvm.load %276 : !llvm.ptr -> i64
%267 = func.call @mulmod(%268, %275, %277) : (i64, i64, i64) -> i64
%278 = llvm.mlir.addressof @invfact : !llvm.ptr
%279 = llvm.load %278 : !llvm.ptr -> !llvm.ptr
%280 = llvm.load %263 : !llvm.ptr -> i32
%281 = arith.constant 1 : i32
%282 = arith.subi %280, %281 : i32
%283 = arith.extsi %282 : i32 to i64
%284 = llvm.getelementptr %279[%283] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %267, %284 : i64, !llvm.ptr
%285 = llvm.load %263 : !llvm.ptr -> i32
%286 = arith.constant 1 : i32
%287 = arith.subi %285, %286 : i32
llvm.store %287, %263 : i32, !llvm.ptr
cf.br ^bb30
^bb32:
func.return
}
func.func @binom_row(%arg0: i32, %arg1: !llvm.ptr) -> () {
%288 = arith.constant 0 : i32
%289 = arith.constant 1 : i32
%290 = arith.addi %arg0, %289 : i32
%291 = arith.index_cast %288 : i32 to index
%292 = arith.index_cast %290 : i32 to index
%294 = arith.constant 1 : index
%295 = arith.constant -1 : index
%296 = arith.cmpi sle, %291, %292 : index
%293 = arith.select %296, %294, %295 : index
cf.br ^bb33(%291 : index)
^bb33(%297: index):
%298 = arith.cmpi slt, %297, %292 : index
%299 = arith.cmpi sgt, %297, %292 : index
%300 = arith.select %296, %298, %299 : i1
cf.cond_br %300, ^bb34(%297 : index), ^bb35(%297 : index)
^bb34(%301: index):
%304 = llvm.mlir.addressof @fact : !llvm.ptr
%305 = llvm.load %304 : !llvm.ptr -> !llvm.ptr
%306 = arith.extsi %arg0 : i32 to i64
%307 = llvm.getelementptr %305[%306] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%303 = llvm.load %307 : !llvm.ptr -> i64
%310 = llvm.mlir.addressof @invfact : !llvm.ptr
%311 = llvm.load %310 : !llvm.ptr -> !llvm.ptr
%312 = arith.index_cast %301 : index to i64
%313 = llvm.getelementptr %311[%312] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%309 = llvm.load %313 : !llvm.ptr -> i64
%315 = llvm.mlir.addressof @invfact : !llvm.ptr
%316 = llvm.load %315 : !llvm.ptr -> !llvm.ptr
%318 = arith.index_cast %301 : index to i32
%317 = arith.subi %arg0, %318 : i32
%319 = arith.extsi %317 : i32 to i64
%320 = llvm.getelementptr %316[%319] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%314 = llvm.load %320 : !llvm.ptr -> i64
%321 = llvm.mlir.addressof @MOD : !llvm.ptr
%322 = llvm.load %321 : !llvm.ptr -> i64
%308 = func.call @mulmod(%309, %314, %322) : (i64, i64, i64) -> i64
%323 = llvm.mlir.addressof @MOD : !llvm.ptr
%324 = llvm.load %323 : !llvm.ptr -> i64
%302 = func.call @mulmod(%303, %308, %324) : (i64, i64, i64) -> i64
%325 = arith.index_cast %301 : index to i64
%326 = llvm.getelementptr %arg1[%325] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %302, %326 : i64, !llvm.ptr
%327 = arith.addi %301, %293 : index
cf.br ^bb33(%327 : index)
^bb35(%328: index):
func.return
}
func.func @convolve_and_decimate(%arg0: !llvm.ptr, %arg1: i32, %arg2: !llvm.ptr, %arg3: i32, %arg4: i32, %arg5: !llvm.ptr) -> i32 {
%329 = arith.addi %arg1, %arg3 : i32
%330 = arith.constant 1 : i32
%331 = arith.subi %329, %330 : i32
%332 = arith.subi %331, %arg4 : i32
%333 = arith.constant 1 : i32
%334 = arith.addi %332, %333 : i32
%335 = arith.constant 2 : i32
%336 = arith.divsi %334, %335 : i32
%337 = arith.constant 0 : i32
%338 = arith.index_cast %337 : i32 to index
%339 = arith.index_cast %336 : i32 to index
%341 = arith.constant 1 : index
%342 = arith.constant -1 : index
%343 = arith.cmpi sle, %338, %339 : index
%340 = arith.select %343, %341, %342 : index
cf.br ^bb36(%338 : index)
^bb36(%344: index):
%345 = arith.cmpi slt, %344, %339 : index
%346 = arith.cmpi sgt, %344, %339 : index
%347 = arith.select %343, %345, %346 : i1
cf.cond_br %347, ^bb37(%344 : index), ^bb38(%344 : index)
^bb37(%348: index):
%349 = arith.constant 0 : i32
%350 = arith.extsi %349 : i32 to i64
%351 = arith.index_cast %348 : index to i64
%352 = llvm.getelementptr %arg5[%351] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %350, %352 : i64, !llvm.ptr
%353 = arith.addi %348, %340 : index
cf.br ^bb36(%353 : index)
^bb38(%354: index):
%355 = arith.constant 0 : i32
%356 = arith.index_cast %355 : i32 to index
%357 = arith.index_cast %331 : i32 to index
%359 = arith.constant 1 : index
%360 = arith.constant -1 : index
%361 = arith.cmpi sle, %356, %357 : index
%358 = arith.select %361, %359, %360 : index
cf.br ^bb39(%356 : index)
^bb39(%362: index):
%363 = arith.cmpi slt, %362, %357 : index
%364 = arith.cmpi sgt, %362, %357 : index
%365 = arith.select %361, %363, %364 : i1
cf.cond_br %365, ^bb40(%362 : index), ^bb41(%362 : index)
^bb40(%366: index):
%367 = arith.constant 0 : i32
%368 = arith.extsi %367 : i32 to i128
%369 = llvm.mlir.constant(1 : i64) : i64
%370 = llvm.alloca %369 x i128 : (i64) -> !llvm.ptr
llvm.store %368, %370 : i128, !llvm.ptr
%372 = arith.index_cast %366 : index to i32
%371 = arith.subi %372, %arg3 : i32
%373 = arith.constant 1 : i32
%374 = arith.addi %371, %373 : i32
%375 = arith.constant 0 : i32
%376 = arith.cmpi sgt, %374, %375 : i32
%377 = scf.if %376 -> (i32) {
%379 = arith.index_cast %366 : index to i32
%378 = arith.subi %379, %arg3 : i32
%380 = arith.constant 1 : i32
%381 = arith.addi %378, %380 : i32
scf.yield %381 : i32
} else {
%382 = arith.constant 0 : i32
scf.yield %382 : i32
}
%383 = arith.constant 1 : i32
%384 = arith.subi %arg1, %383 : i32
%386 = arith.index_cast %366 : index to i32
%385 = arith.cmpi slt, %386, %384 : i32
%387 = scf.if %385 -> (index) {
scf.yield %366 : index
} else {
%388 = arith.constant 1 : i32
%389 = arith.subi %arg1, %388 : i32
scf.yield %389 : i32
}
%390 = arith.index_cast %387 : index to i32
%391 = arith.constant 1 : i32
%392 = arith.addi %390, %391 : i32
%393 = arith.index_cast %377 : i32 to index
%394 = arith.index_cast %392 : i32 to index
%396 = arith.constant 1 : index
%397 = arith.constant -1 : index
%398 = arith.cmpi sle, %393, %394 : index
%395 = arith.select %398, %396, %397 : index
cf.br ^bb42(%393 : index)
^bb42(%399: index):
%400 = arith.cmpi slt, %399, %394 : index
%401 = arith.cmpi sgt, %399, %394 : index
%402 = arith.select %398, %400, %401 : i1
cf.cond_br %402, ^bb43(%399 : index), ^bb44(%399 : index)
^bb43(%403: index):
%404 = llvm.load %370 : !llvm.ptr -> i128
%406 = arith.index_cast %403 : index to i64
%407 = llvm.getelementptr %arg0[%406] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%405 = llvm.load %407 : !llvm.ptr -> i64
%408 = arith.extsi %405 : i64 to i128
%410 = arith.subi %366, %403 : index
%411 = arith.index_cast %410 : index to i64
%412 = llvm.getelementptr %arg2[%411] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%409 = llvm.load %412 : !llvm.ptr -> i64
%413 = arith.extsi %409 : i64 to i128
%415 = arith.trunci %408 : i128 to i64
%416 = arith.trunci %413 : i128 to i64
%414 = arith.muli %415, %416 : i64
%418 = arith.trunci %404 : i128 to i64
%417 = arith.addi %418, %414 : i64
%419 = arith.extsi %417 : i64 to i128
llvm.store %419, %370 : i128, !llvm.ptr
%420 = arith.addi %403, %395 : index
cf.br ^bb42(%420 : index)
^bb44(%421: index):
%422 = llvm.load %370 : !llvm.ptr -> i128
%423 = llvm.mlir.addressof @MOD : !llvm.ptr
%424 = llvm.load %423 : !llvm.ptr -> i64
%425 = arith.extsi %424 : i64 to i128
%427 = arith.trunci %422 : i128 to i64
%428 = arith.trunci %425 : i128 to i64
%426 = arith.remsi %427, %428 : i64
%430 = arith.index_cast %366 : index to i32
%429 = arith.cmpi sge, %430, %arg4 : i32
%431 = scf.if %429 -> (i1) {
%433 = arith.index_cast %366 : index to i32
%432 = arith.subi %433, %arg4 : i32
%434 = arith.constant 2 : i32
%435 = arith.remsi %432, %434 : i32
%436 = arith.constant 0 : i32
%437 = arith.cmpi eq, %435, %436 : i32
scf.yield %437 : i1
} else {
%438 = arith.constant false
scf.yield %438 : i1
}
cf.cond_br %431, ^bb45, ^bb46
^bb45:
%440 = arith.index_cast %366 : index to i32
%439 = arith.subi %440, %arg4 : i32
%441 = arith.constant 2 : i32
%442 = arith.divsi %439, %441 : i32
%443 = arith.extsi %442 : i32 to i64
%444 = llvm.getelementptr %arg5[%443] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %426, %444 : i64, !llvm.ptr
cf.br ^bb47
^bb46:
cf.br ^bb47
^bb47:
%445 = arith.addi %366, %358 : index
cf.br ^bb39(%445 : index)
^bb41(%446: index):
func.return %336 : i32
}
func.func @main() -> i32 {
%448 = llvm.mlir.addressof @BN_LIMBS : !llvm.ptr
%449 = llvm.load %448 : !llvm.ptr -> i32
%450 = arith.extsi %449 : i32 to i64
%451 = arith.constant 8 : i32
%452 = arith.extsi %451 : i32 to i64
%447 = func.call @calloc(%450, %452) : (i64, i64) -> !llvm.ptr
%454 = llvm.mlir.addressof @BN_LIMBS : !llvm.ptr
%455 = llvm.load %454 : !llvm.ptr -> i32
%456 = arith.extsi %455 : i32 to i64
%457 = arith.constant 8 : i32
%458 = arith.extsi %457 : i32 to i64
%453 = func.call @calloc(%456, %458) : (i64, i64) -> !llvm.ptr
%460 = arith.constant 1 : i32
%461 = llvm.mlir.addressof @BN_LIMBS : !llvm.ptr
%462 = llvm.load %461 : !llvm.ptr -> i32
%463 = arith.extsi %460 : i32 to i64
func.call @bn_set_val(%447, %463, %462) : (!llvm.ptr, i64, i32) -> ()
%464 = arith.constant 0 : i32
%465 = arith.constant 777 : i32
%466 = arith.index_cast %464 : i32 to index
%467 = arith.index_cast %465 : i32 to index
%469 = arith.constant 1 : index
%470 = arith.constant -1 : index
%471 = arith.cmpi sle, %466, %467 : index
%468 = arith.select %471, %469, %470 : index
cf.br ^bb48(%466 : index)
^bb48(%472: index):
%473 = arith.cmpi slt, %472, %467 : index
%474 = arith.cmpi sgt, %472, %467 : index
%475 = arith.select %471, %473, %474 : i1
cf.cond_br %475, ^bb49(%472 : index), ^bb50(%472 : index)
^bb49(%476: index):
%478 = arith.constant 7 : i32
%479 = llvm.mlir.addressof @BN_LIMBS : !llvm.ptr
%480 = llvm.load %479 : !llvm.ptr -> i32
%481 = arith.extsi %478 : i32 to i64
func.call @bn_mul_small(%453, %447, %481, %480) : (!llvm.ptr, !llvm.ptr, i64, i32) -> ()
%482 = arith.constant 0 : i32
%483 = llvm.mlir.addressof @BN_LIMBS : !llvm.ptr
%484 = llvm.load %483 : !llvm.ptr -> i32
%485 = arith.index_cast %482 : i32 to index
%486 = arith.index_cast %484 : i32 to index
%488 = arith.constant 1 : index
%489 = arith.constant -1 : index
%490 = arith.cmpi sle, %485, %486 : index
%487 = arith.select %490, %488, %489 : index
cf.br ^bb51(%485 : index)
^bb51(%491: index):
%492 = arith.cmpi slt, %491, %486 : index
%493 = arith.cmpi sgt, %491, %486 : index
%494 = arith.select %490, %492, %493 : i1
cf.cond_br %494, ^bb52(%491 : index), ^bb53(%491 : index)
^bb52(%495: index):
%497 = arith.index_cast %495 : index to i64
%498 = llvm.getelementptr %453[%497] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%496 = llvm.load %498 : !llvm.ptr -> i64
%499 = arith.index_cast %495 : index to i64
%500 = llvm.getelementptr %447[%499] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %496, %500 : i64, !llvm.ptr
%501 = arith.addi %495, %487 : index
cf.br ^bb51(%501 : index)
^bb53(%502: index):
%503 = arith.addi %476, %468 : index
cf.br ^bb48(%503 : index)
^bb50(%504: index):
%506 = llvm.mlir.addressof @BN_LIMBS : !llvm.ptr
%507 = llvm.load %506 : !llvm.ptr -> i32
%508 = arith.extsi %507 : i32 to i64
%509 = arith.constant 8 : i32
%510 = arith.extsi %509 : i32 to i64
%505 = func.call @calloc(%508, %510) : (i64, i64) -> !llvm.ptr
%512 = llvm.mlir.addressof @BN_LIMBS : !llvm.ptr
%513 = llvm.load %512 : !llvm.ptr -> i32
func.call @bn_shr1(%505, %447, %513) : (!llvm.ptr, !llvm.ptr, i32) -> ()
%515 = llvm.mlir.addressof @BN_LIMBS : !llvm.ptr
%516 = llvm.load %515 : !llvm.ptr -> i32
%514 = func.call @bn_bit_len(%505, %516) : (!llvm.ptr, i32) -> i32
%517 = arith.constant 2 : i32
%518 = arith.addi %514, %517 : i32
%519 = arith.constant 10 : i32
%520 = arith.addi %514, %519 : i32
%522 = arith.constant 2500 : i32
%523 = arith.constant 8 : i32
%524 = arith.extsi %522 : i32 to i64
%525 = arith.extsi %523 : i32 to i64
%521 = func.call @calloc(%524, %525) : (i64, i64) -> !llvm.ptr
%526 = llvm.mlir.addressof @fact : !llvm.ptr
llvm.store %521, %526 : !llvm.ptr, !llvm.ptr
%528 = arith.constant 2500 : i32
%529 = arith.constant 8 : i32
%530 = arith.extsi %528 : i32 to i64
%531 = arith.extsi %529 : i32 to i64
%527 = func.call @calloc(%530, %531) : (i64, i64) -> !llvm.ptr
%532 = llvm.mlir.addressof @invfact : !llvm.ptr
llvm.store %527, %532 : !llvm.ptr, !llvm.ptr
func.call @prepare_factorials(%518) : (i32) -> ()
%535 = arith.constant 8 : i32
%536 = arith.extsi %520 : i32 to i64
%537 = arith.extsi %535 : i32 to i64
%534 = func.call @calloc(%536, %537) : (i64, i64) -> !llvm.ptr
%539 = arith.constant 8 : i32
%540 = arith.extsi %520 : i32 to i64
%541 = arith.extsi %539 : i32 to i64
%538 = func.call @calloc(%540, %541) : (i64, i64) -> !llvm.ptr
%543 = arith.constant 2500 : i32
%544 = arith.constant 8 : i32
%545 = arith.extsi %543 : i32 to i64
%546 = arith.extsi %544 : i32 to i64
%542 = func.call @calloc(%545, %546) : (i64, i64) -> !llvm.ptr
%547 = arith.constant 1 : i32
%548 = llvm.mlir.constant(1 : i64) : i64
%549 = llvm.alloca %548 x i32 : (i64) -> !llvm.ptr
llvm.store %547, %549 : i32, !llvm.ptr
%550 = arith.constant 1 : i32
%551 = arith.constant 0 : i32
%552 = arith.extsi %550 : i32 to i64
%553 = arith.extsi %551 : i32 to i64
%554 = llvm.getelementptr %534[%553] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %552, %554 : i64, !llvm.ptr
%555 = arith.constant 0 : i32
%556 = arith.index_cast %555 : i32 to index
%557 = arith.index_cast %514 : i32 to index
%559 = arith.constant 1 : index
%560 = arith.constant -1 : index
%561 = arith.cmpi sle, %556, %557 : index
%558 = arith.select %561, %559, %560 : index
cf.br ^bb54(%556 : index)
^bb54(%562: index):
%563 = arith.cmpi slt, %562, %557 : index
%564 = arith.cmpi sgt, %562, %557 : index
%565 = arith.select %561, %563, %564 : i1
cf.cond_br %565, ^bb55(%562 : index), ^bb56(%562 : index)
^bb55(%566: index):
%568 = arith.index_cast %566 : index to i32
%567 = func.call @bn_get_bit(%505, %568) : (!llvm.ptr, i32) -> i32
%569 = arith.constant 2 : i32
%571 = arith.index_cast %566 : index to i32
%570 = arith.addi %571, %569 : i32
func.call @binom_row(%570, %542) : (i32, !llvm.ptr) -> ()
%574 = llvm.load %549 : !llvm.ptr -> i32
%575 = arith.constant 1 : i32
%576 = arith.addi %570, %575 : i32
%573 = func.call @convolve_and_decimate(%534, %574, %542, %576, %567, %538) : (!llvm.ptr, i32, !llvm.ptr, i32, i32, !llvm.ptr) -> i32
%577 = arith.constant 0 : i32
%578 = arith.index_cast %577 : i32 to index
%579 = arith.index_cast %573 : i32 to index
%581 = arith.constant 1 : index
%582 = arith.constant -1 : index
%583 = arith.cmpi sle, %578, %579 : index
%580 = arith.select %583, %581, %582 : index
cf.br ^bb57(%578 : index)
^bb57(%584: index):
%585 = arith.cmpi slt, %584, %579 : index
%586 = arith.cmpi sgt, %584, %579 : index
%587 = arith.select %583, %585, %586 : i1
cf.cond_br %587, ^bb58(%584 : index), ^bb59(%584 : index)
^bb58(%588: index):
%590 = arith.index_cast %588 : index to i64
%591 = llvm.getelementptr %538[%590] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%589 = llvm.load %591 : !llvm.ptr -> i64
%592 = arith.index_cast %588 : index to i64
%593 = llvm.getelementptr %534[%592] : (!llvm.ptr, i64) -> !llvm.ptr, i64
llvm.store %589, %593 : i64, !llvm.ptr
%594 = arith.addi %588, %580 : index
cf.br ^bb57(%594 : index)
^bb59(%595: index):
llvm.store %573, %549 : i32, !llvm.ptr
%596 = arith.addi %566, %558 : index
cf.br ^bb54(%596 : index)
^bb56(%597: index):
%599 = arith.constant 0 : i32
%600 = arith.extsi %599 : i32 to i64
%601 = llvm.getelementptr %534[%600] : (!llvm.ptr, i64) -> !llvm.ptr, i64
%598 = llvm.load %601 : !llvm.ptr -> i64
%602 = llvm.mlir.addressof @MOD : !llvm.ptr
%603 = llvm.load %602 : !llvm.ptr -> i64
%604 = arith.remsi %598, %603 : i64
%605 = llvm.mlir.addressof @str_0 : !llvm.ptr
%606 = llvm.call @printf(%605, %604) vararg(!llvm.func<i32 (ptr, ...)>) : (!llvm.ptr, i64) -> i32
func.call @free(%447) : (!llvm.ptr) -> ()
func.call @free(%453) : (!llvm.ptr) -> ()
func.call @free(%505) : (!llvm.ptr) -> ()
%611 = llvm.mlir.addressof @fact : !llvm.ptr
%612 = llvm.load %611 : !llvm.ptr -> !llvm.ptr
func.call @free(%612) : (!llvm.ptr) -> ()
%614 = llvm.mlir.addressof @invfact : !llvm.ptr
%615 = llvm.load %614 : !llvm.ptr -> !llvm.ptr
func.call @free(%615) : (!llvm.ptr) -> ()
func.call @free(%534) : (!llvm.ptr) -> ()
func.call @free(%538) : (!llvm.ptr) -> ()
func.call @free(%542) : (!llvm.ptr) -> ()
%619 = arith.constant 0 : i32
func.return %619 : i32
}
}