-rw-r--r-- 1853 cryptattacktester-20230614/index_cost.cpp raw
#include <cassert>
#include "sorting_cost.h"
#include "bit_vector_cost.h"
#include "index_cost.h"

bigint bit_vector_add_cost(bigint xbits,bigint ybits)
{
  if (ybits > xbits)
    return bit_vector_add_cost(ybits,xbits);
  bigint result = 0;
  result += ybits*5; // full adder
  result += (xbits-ybits)*2; // half adder
  return result;
}

bigint bit_vector_hamming_weight_cost(bigint n)
{
  if (n <= 1) return 0;
  bigint x = 1;
  x <<= nbits(n)-1;
  x -= 1;
  bigint y = n-x-1;

  bigint result = 0;
  result += bit_vector_hamming_weight_cost(x); // bit_vector_hamming_weight(bit_vector_extract(v, 0, x));
  result += bit_vector_hamming_weight_cost(y); // bit_vector_hamming_weight(bit_vector_extract(v, x, x + y));
  result += bit_vector_add_cost(x ? nbits(x) : bigint(0),y ? nbits(y) : bigint(0));
  return result;
}

bigint bit_vector_hamming_weight_isnot_cost(bigint bits,bigint target)
{
  bigint wbits = nbits(bits);
  bigint targetbits = nbits(target);
  assert(targetbits <= wbits);
  return bit_vector_hamming_weight_cost(bits)+wbits;
}

bigint set_size_cost(bigint indices,bigint idx_bits)
{
  if (indices <= 0) return 0;
  bigint result = 0;
  result += sorting_cost(indices,idx_bits);
  result += indices-1; // v.at(i+0) & v.at(i+1);
  result += (indices-1)*bit_vector_compare_cost(idx_bits); // bit_vector_compare(set.at(i+0), set.at(i+1))
  result += indices-1; // b.andn
  result += 2*(indices-1); // v.at(i+0) ^= b; v.at(i+1) ^= b;
  result += bit_vector_hamming_weight_cost(indices); // bit_vector_hamming_weight(v);
  return result;
}

bigint set_size_check_cost(bigint indices,bigint idx_bits,bigint target)
{
  bigint result = set_size_cost(indices,idx_bits);
  result += 1+bit_vector_integer_compare_cost(nbits(indices),nbits(target)); // ~bit_vector_integer_compare(w_set, w_vec); // XXX: can speed up circuit
  return result;
}