-rw-r--r-- 1245 cryptattacktester-20231020/sorting_cost.cpp raw
#include <cassert>
#include "bit_cost.h"
#include "bit_matrix_cost.h"
#include "ram_cost.h"
#include "sorting_cost.h"
bigint bit_vector_gt_cost(bigint length)
{
if (length <= 0) return 0;
if (length == 1) return 1;
return 5*(length-1);
}
bigint counting(bigint n, bigint b, bigint s)
{
bigint ret = ((n / (bigint(1) << (b+1))) << b);
bigint t0 = n % (bigint(1) << (b+1));
bigint t1 = bigint(1) << b;
if (t0 < t1) ret += t0;
else ret += t1;
if (s == 0) return ret;
else return n-ret;
}
bigint sorting_cost(bigint n,bigint length,bigint auxlength)
{
if (n <= 0) return 0;
bigint result = 0;
bigint t = 0;
for (bigint z = n;z > 0;z >>= 1) ++t;
if (n == bigint(1)<<(t-1)) --t;
for (bigint j = t-1;j >= 0;--j) {
bigint p = bigint(1)<<j;
bigint q = bigint(1)<<(t-1);
bigint r = 0;
bigint d = p;
for (;;) {
bigint tmp = bit_vector_gt_cost(length); // bit_vector_gt(m.at(i), m.at(i+d))
tmp += length*bit_cswap_cost; // bit_vector_cswap(c, m.at(i), m.at(i+d))
tmp += auxlength*bit_cswap_cost;
tmp *= counting(n-d, j, r == 0 ? 0 : 1);
result += tmp;
if (q == p) break;
d = q-p;
q >>= 1;
r = p;
}
}
return result;
}