diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2013-10-02 20:09:36 +0400 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2013-10-02 20:09:36 +0400 |
commit | 1e1cb605b9b58016a618f6e546d5cb0d0dbf8f23 (patch) | |
tree | 1ddcc98f2e802eb6e39406d31bf5f6bf1376f7d1 /core/src/main/java | |
parent | d3a0511269e58cad6c286ec886e3a1632abdf5d1 (diff) |
New class LongArray equivalent to IntArray but using 'long' words.
Diffstat (limited to 'core/src/main/java')
-rw-r--r-- | core/src/main/java/org/bouncycastle/math/ec/LongArray.java | 816 |
1 files changed, 816 insertions, 0 deletions
diff --git a/core/src/main/java/org/bouncycastle/math/ec/LongArray.java b/core/src/main/java/org/bouncycastle/math/ec/LongArray.java new file mode 100644 index 00000000..be1edde2 --- /dev/null +++ b/core/src/main/java/org/bouncycastle/math/ec/LongArray.java @@ -0,0 +1,816 @@ +package org.bouncycastle.math.ec; + +import org.bouncycastle.util.Arrays; + +import java.math.BigInteger; + +class LongArray +{ + /* + * This expands 8 bit indices into 16 bit contents, by inserting 0s between bits. + * In a binary field, this operation is the same as squaring an 8 bit number. + */ + private static final int[] EXPANSION_TABLE = new int[] { 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, + 0x0015, 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, + 0x0111, 0x0114, 0x0115, 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, 0x0400, 0x0401, 0x0404, + 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, 0x0500, + 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, + 0x0555, 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, + 0x1051, 0x1054, 0x1055, 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, 0x1140, 0x1141, 0x1144, + 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, 0x1440, + 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, + 0x1515, 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, + 0x4011, 0x4014, 0x4015, 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, 0x4100, 0x4101, 0x4104, + 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, 0x4400, + 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, + 0x4455, 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, + 0x4551, 0x4554, 0x4555, 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, 0x5040, 0x5041, 0x5044, + 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, 0x5140, + 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, + 0x5415, 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, + 0x5511, 0x5514, 0x5515, 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 }; + + // For toString(); must have length 64 + private static final String ZEROES = "0000000000000000000000000000000000000000000000000000000000000000"; + + private final static byte[] bitLengths = + { + 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, + 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, + 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 + }; + + public static int getWordLength(int bits) + { + return (bits + 63) >>> 6; + } + + // TODO make m fixed for the LongArray, and hence compute T once and for all + + private long[] m_ints; + + public LongArray(int intLen) + { + m_ints = new long[intLen]; + } + + public LongArray(long[] ints) + { + m_ints = ints; + } + + public LongArray(BigInteger bigInt) + { + if (bigInt == null || bigInt.signum() < 0) + { + throw new IllegalArgumentException("invalid F2m field value"); + } + + if (bigInt.equals(ECConstants.ZERO)) + { + m_ints = new long[] { 0L }; + 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 + 7) / 8; + m_ints = new long[intLen]; + + int iarrJ = intLen - 1; + int rem = barrLen % 8 + barrStart; + long temp = 0; + int barrI = barrStart; + if (barrStart < rem) + { + for (; barrI < rem; barrI++) + { + temp <<= 8; + int barrBarrI = barr[barrI] & 0xFF; + temp |= barrBarrI; + } + m_ints[iarrJ--] = temp; + } + + for (; iarrJ >= 0; iarrJ--) + { + temp = 0; + for (int i = 0; i < 8; i++) + { + temp <<= 8; + int barrBarrI = barr[barrI++] & 0xFF; + temp |= barrBarrI; + } + m_ints[iarrJ] = temp; + } + } + + public boolean isZero() + { + return m_ints.length == 0 + || (m_ints[0] == 0L && getUsedLength() == 0); + } + + public int getUsedLength() + { + return getUsedLengthFrom(m_ints.length); + } + + public int getUsedLengthFrom(int from) + { + if (from < 1) + { + return 0; + } + + // Check if first element will act as sentinel + if (m_ints[0] != 0) + { + while (m_ints[--from] == 0) + { + } + return from + 1; + } + + do + { + if (m_ints[--from] != 0) + { + return from + 1; + } + } + while (from > 0); + + return 0; + } + + public int degree() + { + int i = m_ints.length; + long w; + do + { + if (i == 0) + { + return 0; + } + w = m_ints[--i]; + } + while (w == 0); + + int u = (int)(w >>> 32), b; + if (u == 0) + { + u = (int)w; + b = 0; + } + else + { + b = 32; + } + + int t = u >>> 16, k; + if (t == 0) + { + t = u >>> 8; + k = (t == 0) ? bitLengths[u] : 8 + bitLengths[t]; + } + else + { + int v = t >>> 8; + k = (v == 0) ? 16 + bitLengths[t] : 24 + bitLengths[v]; + } + + return (i << 6) + b + k; + } + + private long[] resizedInts(int newLen) + { + long[] newInts = new long[newLen]; + System.arraycopy(m_ints, 0, newInts, 0, Math.min(m_ints.length, newLen)); + return newInts; + } + + public BigInteger toBigInteger() + { + int usedLen = getUsedLength(); + if (usedLen == 0) + { + return ECConstants.ZERO; + } + + long highestInt = m_ints[usedLen - 1]; + byte[] temp = new byte[8]; + int barrI = 0; + boolean trailingZeroBytesDone = false; + for (int j = 7; j >= 0; j--) + { + byte thisByte = (byte)(highestInt >>> (8 * j)); + if (trailingZeroBytesDone || (thisByte != 0)) + { + trailingZeroBytesDone = true; + temp[barrI++] = thisByte; + } + } + + int barrLen = 8 * (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--) + { + long mi = m_ints[iarrJ]; + for (int j = 7; j >= 0; j--) + { + barr[barrI++] = (byte)(mi >>> (8 * j)); + } + } + return new BigInteger(1, barr); + } + + private static long shiftLeftQuick(long[] x) + { + long prev = 0; + for (int i = 0; i < x.length; ++i) + { + long next = x[i]; + x[i] = (next << 1) | prev; + prev = next >>> 63; + } + return prev; + } + + public void addOneShifted(int shift) + { + if (shift >= m_ints.length) + { + m_ints = resizedInts(shift + 1); + } + + m_ints[shift] ^= 1; + } + + public void addShiftedByBits(LongArray other, int bits) + { + int words = bits >>> 6; + int shift = bits & 0x3F; + + if (shift == 0) + { + addShiftedByWords(other, words); + return; + } + + int otherUsedLen = other.getUsedLength(); + if (otherUsedLen == 0) + { + return; + } + + int minLen = otherUsedLen + words + 1; + if (minLen > m_ints.length) + { + m_ints = resizedInts(minLen); + } + + int shiftInv = 64 - shift; + long prev = 0; + for (int i = 0; i < otherUsedLen; ++i) + { + long next = other.m_ints[i]; + m_ints[i + words] ^= (next << shift) | prev; + prev = next >>> shiftInv; + } + m_ints[otherUsedLen + words] ^= prev; + } + + private static long addShiftedByBitsQuick(long[] x, long[] y, int count, int shift) + { + int shiftInv = 64 - shift; + long prev = 0; + for (int i = 0; i < count; ++i) + { + long next = y[i]; + x[i] ^= (next << shift) | prev; + prev = next >>> shiftInv; + } + return prev; + } + + public void addShiftedByWords(LongArray other, int words) + { + int otherUsedLen = other.getUsedLength(); + if (otherUsedLen == 0) + { + return; + } + + int minLen = otherUsedLen + words; + if (minLen > m_ints.length) + { + m_ints = resizedInts(minLen); + } + + for (int i = 0; i < otherUsedLen; i++) + { + m_ints[words + i] ^= other.m_ints[i]; + } + } + + private static void addShiftedByWordsQuick(long[] x, int xOff, long[] y) + { + for (int i = 0; i < y.length; ++i) + { + x[xOff + i] ^= y[i]; + } + } + + private static void addQuick(long[] x, long[] y, int count) + { + for (int i = 0; i < count; ++i) + { + x[i] ^= y[i]; + } + } + + public int getLength() + { + return m_ints.length; + } + + public void flipWord(int bit, long word) + { + int len = m_ints.length; + int n = bit >>> 6; + if (n < len) + { + int shift = bit & 0x3F; + if (shift == 0) + { + m_ints[n] ^= word; + } + else + { + m_ints[n] ^= word << shift; + if (++n < len) + { + m_ints[n] ^= word >>> (64 - shift); + } + } + } + } + + public long getWord(int bit) + { + int len = m_ints.length; + int n = bit >>> 6; + if (n >= len) + { + return 0; + } + int shift = bit & 0x3F; + if (shift == 0) + { + return m_ints[n]; + } + long result = m_ints[n] >>> shift; + if (++n < len) + { + result |= m_ints[n] << (64 - shift); + } + return result; + } + + public boolean testBit(int n) + { + // theInt = n / 64 + int theInt = n >>> 6; + // theBit = n % 64 + int theBit = n & 0x3F; + long tester = 1L << theBit; + return (m_ints[theInt] & tester) != 0; + } + + public void flipBit(int n) + { + // theInt = n / 64 + int theInt = n >>> 6; + // theBit = n % 64 + int theBit = n & 0x3F; + long flipper = 1L << theBit; + m_ints[theInt] ^= flipper; + } + + public void setBit(int n) + { + // theInt = n / 64 + int theInt = n >>> 6; + // theBit = n % 64 + int theBit = n & 0x3F; + long setter = 1L << theBit; + m_ints[theInt] |= setter; + } + + public void clearBit(int n) + { + // theInt = n / 64 + int theInt = n >>> 6; + // theBit = n % 64 + int theBit = n & 0x3F; + long setter = 1L << theBit; + m_ints[theInt] &= ~setter; + } + + public LongArray multiply(LongArray other, int m) + { + int aLen = getUsedLength(); + if (aLen == 0) + { + return new LongArray(1); + } + + int bLen = other.getUsedLength(); + if (bLen == 0) + { + return new LongArray(1); + } + + LongArray A = this, B = other; + if (aLen > bLen) + { + A = other; B = this; + int tmp = aLen; aLen = bLen; bLen = tmp; + } + + if (aLen == 1) + { + long aVal = A.m_ints[0]; + long[] b = B.m_ints; + long[] c = new long[aLen + bLen]; + if ((aVal & 1L) != 0) + { + addQuick(c, b, bLen); + } + int k = 1; + while ((aVal >>>= 1) != 0) + { + if ((aVal & 1L) != 0) + { + addShiftedByBitsQuick(c, b, bLen, k); + } + ++k; + } + return new LongArray(c); + } + + if ((B.m_ints[bLen - 1] >>> 49) != 0L) + { + ++bLen; + } + + int cLen = aLen + bLen; + + long[] a = A.m_ints; + long[] b = B.resizedInts(bLen); + long[] c0 = new long[cLen]; + long[] c1 = new long[cLen]; + long[] c2 = new long[cLen]; + long[] c3 = new long[cLen]; + + long bit1 = 1L << 48; + + for (;;) + { + long bit2 = bit1 >>> 16, bit3 = bit2 >>> 16, bit4 = bit3 >>> 16; + + for (int aPos = 0; aPos < aLen; ++aPos) + { + long aVal = a[aPos]; + if ((aVal & bit1) != 0) + { + addShiftedByWordsQuick(c3, aPos, b); + } + if ((aVal & bit2) != 0) + { + addShiftedByWordsQuick(c2, aPos, b); + } + if ((aVal & bit3) != 0) + { + addShiftedByWordsQuick(c1, aPos, b); + } + if ((aVal & bit4) != 0) + { + addShiftedByWordsQuick(c0, aPos, b); + } + } + + if ((bit1 <<= 1) == 0L) + { + break; + } + + shiftLeftQuick(b); + } + + addShiftedByBitsQuick(c0, c1, cLen, 16); + addShiftedByBitsQuick(c0, c2, cLen, 32); + addShiftedByBitsQuick(c0, c3, cLen, 48); + + return new LongArray(c0); + } + + // 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; + // } + + public void reduce(int m, int[] ks) + { + int len = getUsedLength(); + int mLen = (m + 63) >>> 6; + if (len < mLen) + { + return; + } + + int _2m = m << 1; + int pos = Math.min(_2m - 2, (len << 6) - 1); + + int kMax = ks[ks.length - 1]; + if (kMax < m - 63) + { + reduceWordWise(pos, m, ks); + } + else + { + reduceBitWise(pos, m, ks); + } + + // Instead of flipping the high bits in the loop, explicitly clear any partial word above m bits + int partial = m & 0x3F; + if (partial != 0) + { + m_ints[mLen - 1] &= (1L << partial) - 1; + } + + if (len > mLen) + { + m_ints = resizedInts(mLen); + } + } + + private void reduceBitWise(int from, int m, int[] ks) + { + for (int i = from; i >= m; --i) + { + if (testBit(i)) + { +// clearBit(i); + int bit = i - m; + flipBit(bit); + int j = ks.length; + while (--j >= 0) + { + flipBit(ks[j] + bit); + } + } + } + } + + private void reduceWordWise(int from, int m, int[] ks) + { + int pos = m + ((from - m) & ~0x3F); + for (int i = pos; i >= m; i -= 64) + { + long word = getWord(i); + if (word != 0) + { +// flipWord(i); + int bit = i - m; + flipWord(bit, word); + int j = ks.length; + while (--j >= 0) + { + flipWord(ks[j] + bit, word); + } + } + } + } + + public LongArray square(int m) + { + int len = getUsedLength(), _2len = len << 1; + long[] r = new long[_2len]; + + int pos = 0; + while (pos < _2len) + { + long mi = m_ints[pos >>> 1]; + + { + int mi00 = (int)mi; + int r00 = square16(mi00 & 0xFFFF); + int r32 = square16(mi00 >>> 16); + r[pos++] = (r32 & 0xFFFFFFFFL) << 32 | (r00 & 0xFFFFFFFFL); + } + + { + int mi32 = (int)(mi >>> 32); + int r00 = square16(mi32 & 0xFFFF); + int r32 = square16(mi32 >>> 16); + r[pos++] = (r32 & 0xFFFFFFFFL) << 32 | (r00 & 0xFFFFFFFFL); + } + } + + return new LongArray(r); + } + + private static int square16(int n) + { + return EXPANSION_TABLE[n & 0xFF] | EXPANSION_TABLE[n >>> 8] << 16; + } + + public LongArray modInverse(int m, int[] ks) + { + // Inversion in F2m using the extended Euclidean algorithm + // Input: A nonzero polynomial a(z) of degree at most m-1 + // Output: a(z)^(-1) mod f(z) + + int uzDegree = degree(); + if (uzDegree == 1) + { + return this; + } + + // u(z) := a(z) + LongArray uz = (LongArray)clone(); + + int t = getWordLength(m); + + // v(z) := f(z) + LongArray vz = new LongArray(t); + vz.setBit(m); + vz.setBit(0); + vz.setBit(ks[0]); + if (ks.length > 1) + { + vz.setBit(ks[1]); + vz.setBit(ks[2]); + } + + // g1(z) := 1, g2(z) := 0 + LongArray g1z = new LongArray(t); + g1z.setBit(0); + LongArray g2z = new LongArray(t); + + while (uzDegree != 0) + { + // j := deg(u(z)) - deg(v(z)) + int j = uzDegree - vz.degree(); + + // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j + if (j < 0) + { + final LongArray uzCopy = uz; + uz = vz; + vz = uzCopy; + + final LongArray g1zCopy = g1z; + g1z = g2z; + g2z = g1zCopy; + + j = -j; + } + + // u(z) := u(z) + z^j * v(z) + // Note, that no reduction modulo f(z) is required, because + // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z))) + // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z)) + // = deg(u(z)) + // uz = uz.xor(vz.shiftLeft(j)); + uz.addShiftedByBits(vz, j); + uzDegree = uz.degree(); + + // g1(z) := g1(z) + z^j * g2(z) +// g1z = g1z.xor(g2z.shiftLeft(j)); + if (uzDegree != 0) + { + g1z.addShiftedByBits(g2z, j); + } + } + return g2z; + } + + public boolean equals(Object o) + { + if (!(o instanceof LongArray)) + { + return false; + } + LongArray other = (LongArray) 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++) + { + long mi = m_ints[i]; + hash *= 31; + hash ^= (int)mi; + hash *= 31; + hash ^= (int)(mi >>> 32); + } + return hash; + } + + public Object clone() + { + return new LongArray(Arrays.clone(m_ints)); + } + + public String toString() + { + int i = getUsedLength(); + if (i == 0) + { + return "0"; + } + + StringBuffer sb = new StringBuffer(Long.toBinaryString(m_ints[--i])); + while (--i >= 0) + { + String s = Long.toBinaryString(m_ints[i]); + + // Add leading zeroes, except for highest significant word + int len = s.length(); + if (len < 64) + { + sb.append(ZEROES.substring(len)); + } + + sb.append(s); + } + return sb.toString(); + } +}
\ No newline at end of file |