#include "registers.h"
#include "bits/stdc++.h"
using namespace std;
// used for storing 1's at the end of input, to not have 0's that kill min
const int REM_FLAG = 99;
const int EVEN_FLAG = 98;
const int ODD_FLAG = 97;
const int EVEN_OVERFLOW_FLAG = 96;
const int ODD_OVERFLOW_FLAG = 95;
const int INPUT = 0;
const int OFFSET_INPUT = 5;
const int OFFSET_INPUT_UP = 6;
const int A = 1;
const int B = 2;
const int ADD_RES = 3;
const int ADD_RES_1 = 4;
void initialize(int n, int k, int s)
{
vector<bool> rem_flag(2000);
vector<bool> even_flag(2000);
vector<bool> overflow_flag(2000);
for (int i = 0; i < 2000; i++)
{
rem_flag[i] = i >= n * k;
even_flag[i] = (i / k) % 2 == 0;
overflow_flag[i] = i % (k * 2) == k;
}
append_store(EVEN_FLAG, even_flag);
append_store(EVEN_OVERFLOW_FLAG, overflow_flag);
append_store(REM_FLAG, rem_flag);
if (s == 1)
{
append_left(ODD_OVERFLOW_FLAG, EVEN_OVERFLOW_FLAG, k);
append_not(ODD_FLAG, EVEN_FLAG);
}
append_or(INPUT, INPUT, REM_FLAG);
}
void do_min(int k, int align)
{
// overview:
// Do a + !b
// Overflow bit indicates larger num
// Extrapolate(?) overflow to bitmask
// Do (a & mask) | (b & !mask)
// align numbers
append_right(B, INPUT, align);
append_and(B, B, EVEN_FLAG);
append_and(INPUT, INPUT, EVEN_FLAG);
// do a + !b
append_not(ADD_RES, B);
append_add(ADD_RES, ADD_RES, INPUT);
// isolate overflow bit
append_and(ADD_RES, ADD_RES, EVEN_OVERFLOW_FLAG);
int mx = k + 1;
int cur = 1;
while (cur < mx)
{
int neww = min(cur * 2, mx);
int diff = neww - cur;
cur = neww;
append_right(ADD_RES_1, ADD_RES, diff);
append_or(ADD_RES, ADD_RES, ADD_RES_1);
}
// Do (a & mask) | (b & !mask)
append_and(INPUT, INPUT, ADD_RES);
append_not(ADD_RES, ADD_RES);
append_and(B, B, ADD_RES);
append_or(INPUT, INPUT, B);
}
void do_swap(int k, bool invert)
{
// overview:
// Do a + !b
// Overflow bit indicates larger num
// Extrapolate(?) overflow to bitmask
// Swap
// align numbers
int flag = invert ? ODD_FLAG : EVEN_FLAG;
int other_flag = invert ? EVEN_FLAG : ODD_FLAG;
int overflow = invert ? ODD_OVERFLOW_FLAG : EVEN_OVERFLOW_FLAG;
append_right(OFFSET_INPUT, INPUT, k);
append_left(OFFSET_INPUT_UP, INPUT, k);
append_and(A, INPUT, flag);
append_not(ADD_RES, OFFSET_INPUT);
append_and(ADD_RES, ADD_RES, flag);
// do a + !b
append_add(ADD_RES, ADD_RES, A);
// isolate overflow bit
append_and(ADD_RES, ADD_RES, overflow);
append_left(ADD_RES, ADD_RES, k - 1);
int mx = k * 2;
int cur = 1;
while (cur < mx)
{
int neww = min(cur * 2, mx);
int diff = neww - cur;
cur = neww;
append_right(ADD_RES_1, ADD_RES, diff);
append_or(ADD_RES, ADD_RES, ADD_RES_1);
}
// find up and down to keep
append_and(OFFSET_INPUT_UP, OFFSET_INPUT_UP, other_flag);
append_and(OFFSET_INPUT_UP, OFFSET_INPUT_UP, ADD_RES);
append_and(OFFSET_INPUT, OFFSET_INPUT, flag);
append_and(OFFSET_INPUT, OFFSET_INPUT, ADD_RES);
// keep relavent input
append_not(ADD_RES, ADD_RES);
append_and(INPUT, INPUT, ADD_RES);
// union
append_or(INPUT, INPUT, OFFSET_INPUT_UP);
append_or(INPUT, INPUT, OFFSET_INPUT);
}
void solve_s0(int n, int k)
{
int sk = 1;
int lk = 1;
while (sk < n)
{
sk *= 2;
++lk;
}
int align = k;
for (int i = 0; i < lk - 1; i++)
{
do_min(k, align);
align *= 2;
}
}
void solve_s1(int n, int k)
{
for (int i = 0; i < n / 2 + 25; i++)
{
do_swap(k, false);
do_swap(k, true);
}
}
void construct_instructions(int s, int n, int k, int q)
{
initialize(n, k, s);
if (s == 0)
solve_s0(n, k);
else
solve_s1(n, k);
}
