/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
//package MPC.Test;

import java.util.Random;

/**
 *
 * @author tordr@stud.ntnu.no
 *///ZpValue is an element in a field. 
//Assuming field size is a positive value between 0 and 2^31-1
//bit 0 is the Least Significant Bit
class ZpValue {

    private static java.util.Random mRandom = new Random();
    private int mValue;
    private int mField;

    public ZpValue(int value, int field) {
        //Works for negative also (value % field) can return negative values
        mValue = ((value % field) + field) % field;
        mField = field;
    }

    public int getValue() {
        return mValue;
    }

    public int getField() {
        return mField;
    }

    public static int getFieldLengthInBits(int fieldSize) {
        int temp = fieldSize;
        for (int i = 0; i < 31; i++) {
            if (temp == 0) {
                return i;
            } else {
                temp = temp / 2;
            }
        }
        return 31;
    }

    @Override
    public String toString() {
        return Integer.toString(mValue);
    }

    public static String print(ZpValue[] bits) {
        String temp = "";
        for (int i = bits.length - 1; i >= 0; i--) {
            temp = temp.concat(bits[i].toString());
        }
        return temp;
    }

    public ZpValue add(ZpValue a) {
        if (this.mField != a.mField) {
            return null;
        } else {
            return new ZpValue(mValue + a.mValue, mField);
        }
    }

    public ZpShare add(ZpShare a) {
        return new ZpShare(add((ZpValue) a));
    }

    public ZpValue sub(ZpValue a) {
        if (this.mField != a.mField) {
            return null;
        } else {
            return new ZpValue(mValue - a.mValue, mField);
        }
    }

    public ZpShare sub(ZpShare a) {
        return new ZpShare(sub((ZpValue) a));
    }

    public ZpValue mult(ZpValue b) {
        if (this.mField != b.mField) {
            return null;
        } else {
            long temp = mValue * b.mValue;
            return new ZpValue((int) (temp % mField), mField);
        }
    }

    public ZpShare mult(ZpShare a) {
        return new ZpShare(mult((ZpValue) a));
    }

    // Returns x^{-1}
    public ZpValue invert() {
        int exp = mValue;
        int temp = 1;
        int tempF = mField - 2;
        for (int i = 0; i < 31; i++) {
            if (1 == tempF % 2) {
                temp = (int) ((long) temp * (long) exp) % mField;
            }
            tempF = tempF / 2;
            exp = (int) (((long) exp * (long) exp) % mField);
        }
        return new ZpValue(temp, mField);
    }

    public static ZpValue randomValue(int fieldSize) {
        return new ZpValue(mRandom.nextInt(fieldSize), fieldSize);
    }

    public static ZpValue nonZeroRandomValue(int fieldSize) {
        return new ZpValue(mRandom.nextInt(fieldSize - 1) + 1, fieldSize);
    }

    public static ZpValue randomBit(int fieldSize) {
        return new ZpValue(mRandom.nextInt(2), fieldSize);
    }

    public ZpValue[] splitInt(int value) {
        //Splits value into bits
        int BitLength = ZpValue.getFieldLengthInBits(mField);
        ZpValue[] ZpArray = new ZpValue[BitLength];
        int temp = value;
        for (int i = 0; i < BitLength; i++) {
            ZpArray[i] = new ZpValue(temp % 2, mField);
            temp = temp / 2;
        }
        return ZpArray;
    }

    public ZpValue xor(ZpValue a) {
        ZpValue temp = this.add(a);
        if (temp.getValue() == 2) {
            temp = new ZpValue(0, temp.getField());
        }
        return temp;
    }

    public ZpValue[] split() {
        return splitInt(mValue);
    }

    public ZpValue[] splitField() {
        return splitInt(mField);
    }

    public static ZpValue join(ZpValue[] array) {
        //Combines 31 bits (or less) into a value
        if (array.length > 31) {
            return null;
        }
        int temp = 0;
        for (int i = array.length - 1; i >= 0; i--) {
            temp = temp * 2 + array[i].mValue;
        }
        return new ZpValue(temp, array[0].mField);
    }

    public static boolean topBitsAre10(int fieldSize) {
        //If Most Significant Bits are 1 and 0 then it return true
        //Otherwise if the Most Significant Bits are 1 and 1 it returns false
        ZpValue temp = new ZpValue(0, fieldSize);
        ZpValue[] vector = temp.splitField();
        assert (vector[vector.length - 1].mValue == 1);
        return (vector[vector.length - 2].mValue == 0);
    }
}

//Share is a dummy class, but shares will be used as if they are unknown values.

//Some functions are not public because they return ZpShare or ZpValue
//The same functions are also not private, so they can be used by other classes
class ZpShare extends ZpValue {

    public ZpShare(int value, int field) {
        super(value, field);
    }

    public ZpShare(ZpValue a) {
        super(a.getValue(), a.getField());
    }

    public static ZpShare share(ZpValue a) {
        return new ZpShare(a);
    }

    public ZpValue reveal() {
        return new ZpValue(this.getValue(), this.getField());
    }

    @Override
    public ZpShare add(ZpShare a) {
        return new ZpShare(super.add(a));
    }

    @Override
    public ZpShare add(ZpValue a) {
        return new ZpShare(super.add(a));
    }

    @Override
    public ZpShare sub(ZpShare a) {
        return new ZpShare(super.sub(a));
    }

    @Override
    public ZpShare sub(ZpValue a) {
        return new ZpShare(super.sub(a));
    }

    @Override
    public ZpShare mult(ZpShare a) {
        return new ZpShare(super.mult(a));
    }

    @Override
    public ZpShare mult(ZpValue a) {
        return new ZpShare(super.mult(a));
    }

    public ZpShare xor(ZpValue a) {
        ZpShare temp = this.add(a);
        if (temp.getValue() == 2) {
            temp = new ZpShare(0, temp.getField());
        }
        return temp;
    }

    public ZpShare xor(ZpShare a) {
        return this.xor((ZpValue) a);
    }

    public static ZpShare randomValue(int fieldSize) {
        return new ZpShare(ZpValue.randomValue(fieldSize));
    }

    public static ZpShare nonZeroRandomValue(int fieldSize) {
        return new ZpShare(ZpValue.nonZeroRandomValue(fieldSize));
    }

    public static ZpShare randomBit(int fieldSize) {
        return new ZpShare(ZpValue.randomBit(fieldSize));
    }

    public static ZpShare join(ZpShare[] array) {
        return new ZpShare(ZpValue.join(array));
    }

    //Tested
    public static ZpShare xor2Bit(ZpShare r_iH, ZpShare r_iL, ZpValue c_iH, ZpValue c_iL) {
        //Returns 0 if both r_iH=c_iH and r_iL=c_iL otherwise return 1.
        //r_iH, c_iH are the highest order bits
        int value = c_iH.getValue() * 2 + c_iL.getValue();
        ZpShare r_iHL = r_iH.mult(r_iL);
        switch (value) {
            case 0: //c_iH = c_iL = 0
                return r_iH.add(r_iL).sub(r_iHL);
            case 1: //c_iL = 1
                return c_iL.sub(r_iL).add(r_iHL);
            case 2: //c_iH = 1
                return c_iH.sub(r_iH).add(r_iHL);
            case 3: //c_iH = c_iL = 1
                return c_iH.sub(r_iHL);
            default:
                return null;
        }
    }

    //Tested
    public static ZpShare r_rc2Bit(ZpShare r_iH, ZpShare r_iL, ZpValue c_iH, ZpValue c_iL) {
        //returns 1 iff r>c otherwise returns 0
        //r_iH, c_iH are the highest order bits
        int value = c_iH.getValue() * 2 + c_iL.getValue();
        ZpShare r_iHL = r_iH.mult(r_iL);
        switch (value) {
            case 0: //c_iH = c_iL = 0
                return r_iH.add(r_iL).sub(r_iHL);
            case 1: //c_iL = 1
                return r_iH;
            case 2: //c_iH = 1
                return r_iHL;
            case 3: //c_iH = c_iL = 1
                return new ZpShare(0, r_iH.getField());
            default:
                return null;
        }
    }

    //The following should not be used in ZpShare
    @Deprecated
    public ZpValue[] splitInt(int value) {
        return null;
    }

    @Deprecated
    public ZpValue[] split() {
        return null;
    }

    @Deprecated
    public ZpValue[] splitField() {
        return null;
    }

    @Deprecated
    public ZpValue invert() {
        return null;
    }
}

public class TestComparisonStandAlone {

    public TestComparisonStandAlone() {
    }

    //Tested
    static ZpShare[] generateRandomBitwiseSharedValue(int fieldSize) {
        int fieldSizeInBits = ZpValue.getFieldLengthInBits(fieldSize);
        ZpShare[] Rand;
        do {
            Rand = new ZpShare[fieldSizeInBits];
            for (int i = 0; i < Rand.length; i++) {
                Rand[i] = ZpShare.randomBit(fieldSize);
            }
            if (ZpValue.topBitsAre10(fieldSize)) {
                Rand = doOptimizationForTopBits(Rand);
            }
            Rand = testRandomBitwiseSharedValue(Rand);
        } while (Rand == null);
        return Rand;
    }

    //Tested
    static ZpShare[] testRandomBitwiseSharedValue(ZpShare[] Rand) {
        // Testing if Rand > P. Test only for p_i (ZpSplit[i]) = 0.
        // There is a separate test for the last bit.
        // Testing if (1-r_i+p_i) + \sum (r_j xor p_j)
        // For last bit testing (p_0-r_0) + \sum (r_j xor p_j)
        // Note (1+p_i) and (p_0) are both 1.
        ZpValue tempV = new ZpValue(0, Rand[0].getField());
        ZpValue[] ZpSplit = tempV.splitField();
        ZpShare[] raXorSp = new ZpShare[ZpSplit.length];
        if (ZpSplit.length != Rand.length) {
            return null;
        }

        for (int j = 0; j < ZpSplit.length; j++) {
            raXorSp[j] = Rand[j].xor(ZpSplit[j]);
        }

        for (int i = ZpSplit.length - 1; i >= 0; i--) {
            if ((0 == ZpSplit[i].getValue()) || (0 == i)) {
                ZpShare tempS = new ZpShare(1, Rand[0].getField());
                tempS = tempS.sub(Rand[i]);
                for (int j = ZpSplit.length - 1; j > i; j--) {
                    tempS = tempS.add(raXorSp[j]);
                }
                //tempS = tempS.mult(ZpShare.randomValue(mFieldSize));
                ZpValue temp = tempS.reveal();
                if (0 == temp.getValue()) {
                    return null;
                }
            }
        }
        return Rand;
    }

    //Tested
    static ZpShare[] doOptimizationForTopBits(ZpShare[] Rand) {
        //The two top bits op Zp are 1 and 0, so the two top bits
        //of ShArray have to be 0 when multipled together
        //This optimisation makes the function 75% likely to succeed
        int fieldSize = Rand[0].getField();
        int topBit = Rand.length - 1;
        ZpShare temp = Rand[topBit].mult(Rand[topBit - 1]);
        ZpValue rev = temp.reveal();
        while (1 == rev.getValue()) {
            Rand[topBit] = ZpShare.randomBit(fieldSize);
            Rand[topBit - 1] = ZpShare.randomBit(fieldSize);
            temp = Rand[topBit].mult(Rand[topBit - 1]);
            rev = temp.reveal();
        }
        return Rand;
    }

    //Tested
    static ZpShare CompareUnrestricted(ZpShare a, ZpShare b) {
        //Compares a > b for all values of a and b
        //Calls CompareRestricted 3 times
        //tests w=a<p/2, x=b<p/2, y=(a-b)modp<p/2
        ZpShare zero = new ZpShare(0, a.getField());
        ZpValue one = new ZpValue(1, a.getField());
        ZpShare w = CompareRestricted(zero, a); //a>p/2
        ZpShare x = CompareRestricted(zero, b); //b>p/2
        ZpShare y = CompareRestricted(a, b); //a>b
        //System.out.println("w,x,y " +w+" "+x+" "+y);
        ZpShare wXorX = w.xor(x);
        ZpShare invWXorX = one.sub(wXorX);
        // If w xor x = 0 then use y, otherwise return w
        ZpShare z = ( invWXorX.mult(y) ).add( wXorX.mult(w) );
        return z;
    }

    //Tested
    static ZpShare CompareRestricted(ZpShare a, ZpShare b) {
        //Compares a > b, where a,b < p/2
        //Calls CreateShareX and GetLSBofX
        // sh_0 is the least significant bit of sh
        // (a > b) = (2(b-a))_0 = c_0 xor r_0 xor (r > c)
        // Where c = 2(b-a)+r, r is a bitwise shared random value
        // c is revealed without loss of security

        ZpShare[] r_ar = generateRandomBitwiseSharedValue(a.getField());
        ZpShare r = ZpShare.join(r_ar);
        ZpShare cSh = b.add(b).sub(a).sub(a).add(r);
        ZpValue c = cSh.reveal();
        //System.out.println("a, b, r c " + a + " " + b + " " + r + " " + c);
        ZpValue[] c_ar = c.split();
        ZpShare x = CreateShareX(r_ar, c_ar);
        ZpShare x0 = GetLSBofX(x);
        //System.out.println("r[0] c[0] x0 " + r_ar[0]+" "+c_ar[0]+" "+x0);
        return r_ar[0].xor(c_ar[0]).xor(x0);
    }

    //Tested
    static ZpShare CreateShareX(ZpShare[] rand, ZpValue[] c_ar) {
        //Transforms comparison of rand > c_ar into a value x.
        //LSB of x is the same as the comparison (rand > c_ar)
        //x < 2sqrt(p). No restrictions on rand and c_ar
        // x = \sum r_i(1-c_i) 2^\sum (r_j xor c_j) on two bits at a time
        if (rand.length != c_ar.length) {
            return null;
        }
        if (rand.length % 2 == 1) {
            ZpShare[] tempShare = new ZpShare[rand.length + 1];
            ZpValue[] tempValue = new ZpValue[rand.length + 1];
            tempShare[0] = new ZpShare(0, rand[0].getField());
            tempValue[0] = new ZpValue(0, rand[0].getField());
            for (int i = 0; i < rand.length; i++) {
                tempShare[i + 1] = rand[i];
                tempValue[i + 1] = c_ar[i];
            }
            rand = tempShare; //New arrays of even length
            c_ar = tempValue; //Added 0 element to LSB of both arrays
        }
        //System.out.println("r c x " + ZpValue.print(rand) + " " + ZpValue.print(c_ar));
        int halfLen = rand.length / 2;
        ZpShare[] xor2Bit = new ZpShare[halfLen]; //Two and two bit r_j xor c_j
        ZpShare[] r_rc2Bit = new ZpShare[halfLen]; //Two and two bit r_i(1-c_i)
        ZpShare one = new ZpShare(1, rand[0].getField());
        for (int i = 0; i < halfLen; i++) {
            xor2Bit[i] = ZpShare.xor2Bit(rand[2 * i + 1], rand[2 * i],
                    c_ar[2 * i + 1], c_ar[2 * i]);
            xor2Bit[i] = xor2Bit[i].add(one); //Either 1 or 2
            r_rc2Bit[i] = ZpShare.r_rc2Bit(rand[2 * i + 1], rand[2 * i],
                    c_ar[2 * i + 1], c_ar[2 * i]);
        }
        ZpShare[] pow = fan_inFromTop(xor2Bit);
        //System.out.println("xor r_rc pow " + ZpValue.print(xor2Bit) + " " + ZpValue.print(r_rc2Bit) + " " + ZpValue.print(pow));
        ZpShare x = r_rc2Bit[halfLen-1];
        //System.out.println("x r_rc2Bit " + x + " " + r_rc2Bit[halfLen-1]);
        for (int i = halfLen-2; i >= 0; i--) {
            x = x.add((r_rc2Bit[i]).mult(pow[i+1]));
            //System.out.println("x r_rc2Bit pow " + x + " " + r_rc2Bit[i] + " " + pow[i+1]);
        }
        return x;
    }

    //Tested
    static ZpShare GetLSBofX(ZpShare x) {
        //Garantied to return the least significant bit (LSB) of x,
        //only when x<p/4 or x+r_low<p, where r_low has the 2 MSB set to 0.

        ZpShare[] r_ar = generateRandomBitwiseSharedValue(x.getField());
        int bitLen = r_ar.length;
        ZpShare r = ZpShare.join(r_ar);
        ZpShare cSh = x.add(r);
        ZpValue c = cSh.reveal();
        ZpValue[] c_split = c.split();
//        System.out.println("x+r=c:" + x + "+" + r + "=" + c);
        //If the most significant bits (MSB) of r are 0 and 0 then there is
        //no chance of overflow in c=x+r because x<p/4, r<p/4
        //There are 4 possible values for the 2 MSB of r, so this can be
        //checked with a binary circut.

        //topXX is 1 only if the top bits are XX
        ZpShare top11 = r_ar[bitLen - 1].mult(r_ar[bitLen - 2]);
        ZpShare one = new ZpShare(1, c.getField());
        ZpShare zero = new ZpShare(0, c.getField());
        ZpShare top00 = one.sub(r_ar[bitLen - 1]).sub(r_ar[bitLen - 2]).add(top11);

        //Switch statement based upon the MSB of c
        int topC = c_split[bitLen - 1].getValue() * 2 + c_split[bitLen - 2].getValue();
        ZpShare useC0 = null;
        ZpShare useInvC0 = null;
        ZpValue c0 = c_split[0];
//        System.out.println("top " + r_ar[bitLen - 1] + " " +
//                r_ar[bitLen - 2] + " " + topC + " " + c0);
        switch (topC) {
            // Use c0 if top00 else use 1-c0
            case 0:
                useC0 = top00;
                useInvC0 = one.sub(top00);
                break;
            case 1:
                useC0 = one.sub(r_ar[bitLen - 1]);
                useInvC0 = r_ar[bitLen - 1];
                break;
            case 2:
                useC0 = one.sub(top11);
                useInvC0 = top11;
                break;
            case 3:
                useC0 = one;
                useInvC0 = zero;
                break;
            default:
                return null;
        }
//        System.out.println("Use c0 " + useC0 + " " + useInvC0);
        ZpShare ans = (useC0.mult(c0)).add(useInvC0.mult(one.sub(c0)));
        ans = ans.xor(r_ar[0]);
        return ans;
    }

    static ZpShare[] fan_inFromTop(ZpShare[] Array) {
        ZpShare[] temp = new ZpShare[Array.length];
        ZpShare[] temp2 = new ZpShare[Array.length];
        for(int i=0; i<Array.length; i++) {
            temp[i] = Array[Array.length-1-i];
        }
        temp = fan_in(temp);
        for(int i=0; i<Array.length; i++) {
            temp2[i] = temp[temp.length-1-i];
        }
        return temp2;
    }

    //Tested
    static ZpShare[] fan_in(ZpShare[] Array) {
        int field = Array[0].getField();
        ZpShare[] r = new ZpShare[Array.length]; //random
        ZpShare[] s = new ZpShare[Array.length]; //random
        ZpValue[] r2 = new ZpValue[Array.length]; //temp
        ZpShare[] r3 = new ZpShare[Array.length]; //temp
        ZpValue[] prod = new ZpValue[Array.length]; //temp
        for (int i = 0; i < Array.length; i++) {
            r[i] = ZpShare.nonZeroRandomValue(field);
            s[i] = ZpShare.nonZeroRandomValue(field);
        //System.out.println("Random " + i + ":" + r[i] + " " + s[i]);
        }
        r2[0] = (r[0].mult(s[0])).reveal(); //r2[i] = r[i]*s[i]
        r2[0] = r2[0].invert(); // r2[i] = (r[i]*s[i])^{-1}
        //System.out.println("(rs)^-1 = " + r2[0]);
        r3[0] = s[0]; //r3[0] = r[-1]*s[0] = 1*s[0] 
        r2[0] = (Array[0].mult(r2[0]).mult(r3[0])).reveal();
        //System.out.println("r2[0] = " + r2[0]);
        for (int i = 1; i < Array.length; i++) {
            r2[i] = (r[i].mult(s[i])).reveal(); //r2[i] = r[i]*s[i]
            r2[i] = r2[i].invert(); // r2[i] = (r[i]*s[i])^{-1}
            //System.out.println("(rs)^-1 = " + r2[i]);
            r3[i] = r[i - 1].mult(s[i]); //r3[i] = r[i-1]*s[i]
            //r2[i] = a[i]*r[i-1]*r[i]^{-1}
            r2[i] = (Array[i].mult(r2[i]).mult(r3[i])).reveal();
        //System.out.println("r2[" + i + "] = " + r2[i]);
        }

        //Fan-in from bottom
        prod[0] = r2[0];
        r3[0] = Array[0]; // a[0]*r[-1]*r[0]^{-1}*r[0]=a[0]
        for (int i = 1; i < Array.length; i++) {
            prod[i] = prod[i - 1].mult(r2[i]);
            r3[i] = prod[i].mult(r[i]);
        }
        return r3; //Fan-in
    }

    public static void DoTest(int fieldSize) {
        int sum=0;
        int test=0;
        for (int i = 0; i < fieldSize; i++) {
            System.out.println(i);
            ZpShare a = new ZpShare(i, fieldSize);
            for (int j = 0; j < fieldSize; j++) {
                ZpShare b = new ZpShare(j, fieldSize);
                ZpShare ret = CompareUnrestricted(a,b);
                //ZpShare ret = CompareRestricted(b,a);
                ZpValue xV = ret.reveal();
                if (j<i)
                    test = 1;
                else
                    test = 0;
                //Sum is the sum of the difference between
                //expected result and returned value.
                sum += (test-xV.getValue())*(test-xV.getValue());
            }
        }
        //Sum = 0 means that there are no errors in the program
        System.out.println("Sum  = " + sum);
    }

    public static void main(String[] args) {
        //int fieldSize = 2147483647; //2^31 - 1, prime
        //int fieldSize = 721141;
        int fieldSize = 1009;
        //int fieldSize = 1031;
        //int fieldSize = 31;

        ZpShare a = new ZpShare(5, fieldSize);
        ZpShare b = new ZpShare(3, fieldSize);
        ZpShare ret = CompareUnrestricted(a,b);
        //ZpShare ret = CompareRestricted(b,a);
        ZpValue revealed = ret.reveal();
        System.out.println("Comparing "+a+" > "+b+" gives "+revealed);
        //DoTest(mFieldSize);
    }

}