math/ec/IntArray.java

package org.bouncycastle.math.ec;

import org.bouncycastle.util.Arrays;

import java.math.BigInteger;

class IntArray
{
    // TODO make m fixed for the IntArray, and hence compute T once and for all

    private int[] m_ints;

    public IntArray(int intLen)
    {
        m_ints = new int[intLen];
    }

    public IntArray(int[] ints)
    {
        m_ints = ints;
    }

    public IntArray(BigInteger bigInt)
    {
        this(bigInt, 0);
    }

    public IntArray(BigInteger bigInt, int minIntLen)
    {
        if (bigInt.signum() == -1)
        {
            throw new IllegalArgumentException("Only positive Integers allowed");
        }
        if (bigInt.equals(ECConstants.ZERO))
        {
            m_ints = new int[] { 0 };
            return;
        }

        byte[] barr = bigInt.toByteArray();
        int barrLen = barr.length;
        int barrStart = 0;
        if (barr[0] == 0)
        {
            // First byte is 0 to enforce highest (=sign) bit is zero.
            // In this case ignore barr[0].
            barrLen--;
            barrStart = 1;
        }
        int intLen = (barrLen + 3) / 4;
        if (intLen < minIntLen)
        {
            m_ints = new int[minIntLen];
        }
        else
        {
            m_ints = new int[intLen];
        }

        int iarrJ = intLen - 1;
        int rem = barrLen % 4 + barrStart;
        int temp = 0;
        int barrI = barrStart;
        if (barrStart < rem)
        {
            for (; barrI < rem; barrI++)
            {
                temp <<= 8;
                int barrBarrI = barr[barrI];
                if (barrBarrI < 0)
                {
                    barrBarrI += 256;
                }
                temp |= barrBarrI;
            }
            m_ints[iarrJ--] = temp;
        }

        for (; iarrJ >= 0; iarrJ--)
        {
            temp = 0;
            for (int i = 0; i < 4; i++)
            {
                temp <<= 8;
                int barrBarrI = barr[barrI++];
                if (barrBarrI < 0)
                {
                    barrBarrI += 256;
                }
                temp |= barrBarrI;
            }
            m_ints[iarrJ] = temp;
        }
    }

    public boolean isZero()
    {
        return m_ints.length == 0
            || (m_ints[0] == 0 && getUsedLength() == 0);
    }

    public int getUsedLength()
    {
        int highestIntPos = m_ints.length;

        if (highestIntPos < 1)
        {
            return 0;
        }

        // Check if first element will act as sentinel
        if (m_ints[0] != 0)
        {
            while (m_ints[--highestIntPos] == 0)
            {
            }
            return highestIntPos + 1;
        }

        do
        {
            if (m_ints[--highestIntPos] != 0)
            {
                return highestIntPos + 1;
            }
        }
        while (highestIntPos > 0);

        return 0;
    }

    public int bitLength()
    {
        // JDK 1.5: see Integer.numberOfLeadingZeros()
        int intLen = getUsedLength();
        if (intLen == 0)
        {
            return 0;
        }

        int last = intLen - 1;
        int highest = m_ints[last];
        int bits = (last << 5) + 1;

        // A couple of binary search steps
        if ((highest & 0xffff0000) != 0)
        {
            if ((highest & 0xff000000) != 0)
            {
                bits += 24;
                highest >>>= 24;
            }
            else
            {
                bits += 16;
                highest >>>= 16;
            }
        }
        else if (highest > 0x000000ff)
        {
            bits += 8;
            highest >>>= 8;
        }

        while (highest != 1)
        {
            ++bits;
            highest >>>= 1;
        }

        return bits;
    }

    private int[] resizedInts(int newLen)
    {
        int[] newInts = new int[newLen];
        int oldLen = m_ints.length;
        int copyLen = oldLen < newLen ? oldLen : newLen;
        System.arraycopy(m_ints, 0, newInts, 0, copyLen);
        return newInts;
    }

    public BigInteger toBigInteger()
    {
        int usedLen = getUsedLength();
        if (usedLen == 0)
        {
            return ECConstants.ZERO;
        }

        int highestInt = m_ints[usedLen - 1];
        byte[] temp = new byte[4];
        int barrI = 0;
        boolean trailingZeroBytesDone = false;
        for (int j = 3; j >= 0; j--)
        {
            byte thisByte = (byte) (highestInt >>> (8 * j));
            if (trailingZeroBytesDone || (thisByte != 0))
            {
                trailingZeroBytesDone = true;
                temp[barrI++] = thisByte;
            }
        }

        int barrLen = 4 * (usedLen - 1) + barrI;
        byte[] barr = new byte[barrLen];
        for (int j = 0; j < barrI; j++)
        {
            barr[j] = temp[j];
        }
        // Highest value int is done now

        for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--)
        {
            for (int j = 3; j >= 0; j--)
            {
                barr[barrI++] = (byte) (m_ints[iarrJ] >>> (8 * j));
            }
        }
        return new BigInteger(1, barr);
    }

    public void shiftLeft()
    {
        int usedLen = getUsedLength();
        if (usedLen == 0)
        {
            return;
        }
        if (m_ints[usedLen - 1] < 0)
        {
            // highest bit of highest used byte is set, so shifting left will
            // make the IntArray one byte longer
            usedLen++;
            if (usedLen > m_ints.length)
            {
                // make the m_ints one byte longer, because we need one more
                // byte which is not available in m_ints
                m_ints = resizedInts(m_ints.length + 1);
            }
        }

        boolean carry = false;
        for (int i = 0; i < usedLen; i++)
        {
            // nextCarry is true if highest bit is set
            boolean nextCarry = m_ints[i] < 0;
            m_ints[i] <<= 1;
            if (carry)
            {
                // set lowest bit
                m_ints[i] |= 1;
            }
            carry = nextCarry;
        }
    }

    public IntArray shiftLeft(int n)
    {
        int usedLen = getUsedLength();
        if (usedLen == 0)
        {
            return this;
        }

        if (n == 0)
        {
            return this;
        }

        if (n > 31)
        {
            throw new IllegalArgumentException("shiftLeft() for max 31 bits "
                + ", " + n + "bit shift is not possible");
        }

        int[] newInts = new int[usedLen + 1];

        int nm32 = 32 - n;
        newInts[0] = m_ints[0] << n;
        for (int i = 1; i < usedLen; i++)
        {
            newInts[i] = (m_ints[i] << n) | (m_ints[i - 1] >>> nm32);
        }
        newInts[usedLen] = m_ints[usedLen - 1] >>> nm32;

        return new IntArray(newInts);
    }

    public void addShifted(IntArray other, int shift)
    {
        int usedLenOther = other.getUsedLength();
        int newMinUsedLen = usedLenOther + shift;
        if (newMinUsedLen > m_ints.length)
        {
            m_ints = resizedInts(newMinUsedLen);
            //System.out.println("Resize required");
        }

        for (int i = 0; i < usedLenOther; i++)
        {
            m_ints[i + shift] ^= other.m_ints[i];
        }
    }

    public int getLength()
    {
        return m_ints.length;
    }

    public boolean testBit(int n)
    {
        // theInt = n / 32
        int theInt = n >> 5;
        // theBit = n % 32
        int theBit = n & 0x1F;
        int tester = 1 << theBit;
        return ((m_ints[theInt] & tester) != 0);
    }

    public void flipBit(int n)
    {
        // theInt = n / 32
        int theInt = n >> 5;
        // theBit = n % 32
        int theBit = n & 0x1F;
        int flipper = 1 << theBit;
        m_ints[theInt] ^= flipper;
    }

    public void setBit(int n)
    {
        // theInt = n / 32
        int theInt = n >> 5;
        // theBit = n % 32
        int theBit = n & 0x1F;
        int setter = 1 << theBit;
        m_ints[theInt] |= setter;
    }

    public IntArray multiply(IntArray other, int m)
    {
        // Lenght of c is 2m bits rounded up to the next int (32 bit)
        int t = (m + 31) >> 5;
        if (m_ints.length < t)
        {
            m_ints = resizedInts(t);
        }

        IntArray b = new IntArray(other.resizedInts(other.getLength() + 1));
        IntArray c = new IntArray((m + m + 31) >> 5);
        // IntArray c = new IntArray(t + t);
        int testBit = 1;
        for (int k = 0; k < 32; k++)
        {
            for (int j = 0; j < t; j++)
            {
                if ((m_ints[j] & testBit) != 0)
                {
                    // The kth bit of m_ints[j] is set
                    c.addShifted(b, j);
                }
            }
            testBit <<= 1;
            b.shiftLeft();
        }
        return c;
    }

    // public IntArray multiplyLeftToRight(IntArray other, int m) {
    // // Lenght of c is 2m bits rounded up to the next int (32 bit)
    // int t = (m + 31) / 32;
    // if (m_ints.length < t) {
    // m_ints = resizedInts(t);
    // }
    //
    // IntArray b = new IntArray(other.resizedInts(other.getLength() + 1));
    // IntArray c = new IntArray((m + m + 31) / 32);
    // // IntArray c = new IntArray(t + t);
    // int testBit = 1 << 31;
    // for (int k = 31; k >= 0; k--) {
    // for (int j = 0; j < t; j++) {
    // if ((m_ints[j] & testBit) != 0) {
    // // The kth bit of m_ints[j] is set
    // c.addShifted(b, j);
    // }
    // }
    // testBit >>>= 1;
    // if (k > 0) {
    // c.shiftLeft();
    // }
    // }
    // return c;
    // }

    // TODO note, redPol.length must be 3 for TPB and 5 for PPB
    public void reduce(int m, int[] redPol)
    {
        for (int i = m + m - 2; i >= m; i--)
        {
            if (testBit(i))
            {
                int bit = i - m;
                flipBit(bit);
                flipBit(i);
                int l = redPol.length;
                while (--l >= 0)
                {
                    flipBit(redPol[l] + bit);
                }
            }
        }
        m_ints = resizedInts((m + 31) >> 5);
    }

    public IntArray square(int m)
    {
        // TODO make the table static final
        final int[] table = { 0x0, 0x1, 0x4, 0x5, 0x10, 0x11, 0x14, 0x15, 0x40,
            0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55 };

        int t = (m + 31) >> 5;
        if (m_ints.length < t)
        {
            m_ints = resizedInts(t);
        }

        IntArray c = new IntArray(t + t);

        // TODO twice the same code, put in separate private method
        for (int i = 0; i < t; i++)
        {
            int v0 = 0;
            for (int j = 0; j < 4; j++)
            {
                v0 = v0 >>> 8;
                int u = (m_ints[i] >>> (j * 4)) & 0xF;
                int w = table[u] << 24;
                v0 |= w;
            }
            c.m_ints[i + i] = v0;

            v0 = 0;
            int upper = m_ints[i] >>> 16;
            for (int j = 0; j < 4; j++)
            {
                v0 = v0 >>> 8;
                int u = (upper >>> (j * 4)) & 0xF;
                int w = table[u] << 24;
                v0 |= w;
            }
            c.m_ints[i + i + 1] = v0;
        }
        return c;
    }

    public boolean equals(Object o)
    {
        if (!(o instanceof IntArray))
        {
            return false;
        }
        IntArray other = (IntArray) o;
        int usedLen = getUsedLength();
        if (other.getUsedLength() != usedLen)
        {
            return false;
        }
        for (int i = 0; i < usedLen; i++)
        {
            if (m_ints[i] != other.m_ints[i])
            {
                return false;
            }
        }
        return true;
    }

    public int hashCode()
    {
        int usedLen = getUsedLength();
        int hash = 1;
        for (int i = 0; i < usedLen; i++)
        {
            hash = hash * 31 + m_ints[i];
        }
        return hash;
    }

    public Object clone()
    {
        return new IntArray(Arrays.clone(m_ints));
    }

    public String toString()
    {
        int usedLen = getUsedLength();
        if (usedLen == 0)
        {
            return "0";
        }

        StringBuffer sb = new StringBuffer(Integer
            .toBinaryString(m_ints[usedLen - 1]));
        for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--)
        {
            String hexString = Integer.toBinaryString(m_ints[iarrJ]);

            // Add leading zeroes, except for highest significant int
            for (int i = hexString.length(); i < 8; i++)
            {
                hexString = "0" + hexString;
            }
            sb.append(hexString);
        }
        return sb.toString();
    }
}