-rw-r--r-- 1245 cryptattacktester-20230614/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;
}