High-order Boolean to arithmetic conversion

// This program is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License version 2 as published
// by the Free Software Foundation.

//#define DEBUG

#include <stdint.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>

static uint32_t x=123456789, y=362436069, z=521288629;

uint32_t xorshf96(void) {
  uint32_t t;

  x ^= x << 16;
  x ^= x >> 5;
  x ^= x << 1;

  t = x;
  x = y;
  y = z;
  z = t ^ x ^ y;
  return z;
}

void share(uint32_t x,uint32_t a[],int n)
{
  int i;
  a[0]=x;
  for(i=1;i<n;i++)
    a[i]=0;
}

void refresh(uint32_t a[],int n)
{
  int i;
  for(i=0;i<n-1;i++)
  {
    uint32_t tmp=xorshf96(); //rand();
    a[n-1]=a[n-1] ^ tmp;
    a[i]=a[i] ^ tmp;
  }
}

uint32_t xorop(uint32_t a[],int n)
{
  int i;
  uint32_t r=0;
  for(i=0;i<n;i++)
    r^=a[i];
  return r;
}

uint32_t addop(uint32_t a[],int n)
{
  int i;
  uint32_t r=0;
  for(i=0;i<n;i++)
    r+=a[i];
  return r;
}

uint32_t Psi(uint32_t x,uint32_t y)
{
  return (x ^ y)-y;
}

uint32_t Psi0(uint32_t x,uint32_t y,int n)
{
  return Psi(x,y) ^ ((~n & 1) * x);
}

void copy(uint32_t *x,uint32_t *y,int n)
{
  for(int i=0;i<n;i++) x[i]=y[i];
}

void convBA(uint32_t *D,uint32_t *x,int n)
{
  if (n==2)
  {
    uint32_t s=xorshf96();
    uint32_t a1=x[0] ^ s;
    uint32_t a2=x[1] ^ s;

    uint32_t r=xorshf96();

    D[0]=(a1 ^ Psi(a1,r ^ a2)) ^ Psi(a1,r);
    D[1]=a2;

    #ifdef DEBUG
      assert((x[0] ^ x[1])==(D[0] + D[1]));
    #endif

    return;
  }

  uint32_t a[n+1];
  copy(a,x,n);
  a[n]=0;

  refresh(a,n+1);

  uint32_t b[n];

  b[0]=Psi0(a[0],a[1],n);
  for(int i=1;i<n;i++)
    b[i]=Psi(a[0],a[i+1]);

  #ifdef DEBUG
    assert(xorop(x,n)==(xorop(a+1,n)+xorop(b,n)));
  #endif

  uint32_t c[n];
  copy(c,a+1,n);
  refresh(c,n);

  uint32_t d[n];
  copy(d,b,n);
  refresh(d,n);

  #ifdef DEBUG
    assert(xorop(x,n)==(xorop(c,n)+xorop(d,n)));
  #endif

  c[n-2]^=c[n-1];
  d[n-2]^=d[n-1];

  #ifdef DEBUG
    assert(xorop(x,n)==(xorop(c,n-1)+xorop(d,n-1)));
  #endif

  uint32_t A[n-1],B[n-1];
  convBA(A,c,n-1);
  convBA(B,d,n-1);

  for(int i=0;i<n-2;i++)
    D[i]=A[i]+B[i];

  D[n-2]=A[n-2];
  D[n-1]=B[n-2];

  #ifdef DEBUG
  assert(xorop(x,n)==addop(D,n));
  #endif
}

void timings()
{
  int nt=1000;
  int n;

  for(int t=2;t<13;t++)
  {
    if ((t==7) || (t==9) || (t==11)) continue;
    n=t+1;
    uint32_t xin=242;
    uint32_t x[n+1];
    share(xin,x,n);
    refresh(x,n);

    uint32_t D[n];

    clock_t start=clock();
    for(int i=0;i<nt;i++)
      convBA(D,x,n);
    clock_t end=clock();
    float dt=((float) (end-start))/CLOCKS_PER_SEC;

    printf(" $%d$ &",(int) (dt*1000000));

    // printf("order=%d t=%f\n",t,dt);
  }
  printf("\n");
}


int main()
{
  timings();
  return 0;
  int n=5;
  int nt=1000;

  uint32_t xin=242;

  uint32_t x[n+1];

  share(xin,x,n);
  refresh(x,n);

  printf("Input shares: ");
  for(int i=0;i<n;i++)
    printf("%u ",x[i]);
  printf("\n");

  clock_t start=clock();

  uint32_t D[n];

  for(int i=0;i<nt;i++)
    convBA(D,x,n);

  clock_t end=clock();
  float dt=((float) (end-start))/CLOCKS_PER_SEC;


  printf("Ouput shares: ");
  for(int i=0;i<n;i++)
    printf("%u ",D[i]);
  printf("\n");

  printf("check: %u %u\n",xorop(x,n),addop(D,n));
  printf("running time: %f\n",dt);
}