18212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrompackage org.bouncycastle.math.ec; 28212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 38212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromimport org.bouncycastle.util.Arrays; 48212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 58212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromimport java.math.BigInteger; 68212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 78212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstromclass IntArray 88212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom{ 98212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // TODO make m fixed for the IntArray, and hence compute T once and for all 108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int[] m_ints; 128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public IntArray(int intLen) 148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = new int[intLen]; 168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public IntArray(int[] ints) 198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = ints; 218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public IntArray(BigInteger bigInt) 248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom this(bigInt, 0); 268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public IntArray(BigInteger bigInt, int minIntLen) 298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (bigInt.signum() == -1) 318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("Only positive Integers allowed"); 338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (bigInt.equals(ECConstants.ZERO)) 358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = new int[] { 0 }; 378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return; 388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte[] barr = bigInt.toByteArray(); 418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int barrLen = barr.length; 428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int barrStart = 0; 438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (barr[0] == 0) 448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // First byte is 0 to enforce highest (=sign) bit is zero. 468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // In this case ignore barr[0]. 478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom barrLen--; 488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom barrStart = 1; 498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int intLen = (barrLen + 3) / 4; 518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (intLen < minIntLen) 528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = new int[minIntLen]; 548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = new int[intLen]; 588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int iarrJ = intLen - 1; 618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int rem = barrLen % 4 + barrStart; 628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int temp = 0; 638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int barrI = barrStart; 648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (barrStart < rem) 658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (; barrI < rem; barrI++) 678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom temp <<= 8; 698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int barrBarrI = barr[barrI]; 708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (barrBarrI < 0) 718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom barrBarrI += 256; 738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom temp |= barrBarrI; 758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints[iarrJ--] = temp; 778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (; iarrJ >= 0; iarrJ--) 808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom temp = 0; 828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 0; i < 4; i++) 838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom temp <<= 8; 858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int barrBarrI = barr[barrI++]; 868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (barrBarrI < 0) 878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom barrBarrI += 256; 898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom temp |= barrBarrI; 918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints[iarrJ] = temp; 938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public boolean isZero() 978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return m_ints.length == 0 998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom || (m_ints[0] == 0 && getUsedLength() == 0); 1008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getUsedLength() 1038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int highestIntPos = m_ints.length; 1058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (highestIntPos < 1) 1078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return 0; 1098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Check if first element will act as sentinel 1128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (m_ints[0] != 0) 1138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (m_ints[--highestIntPos] == 0) 1158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return highestIntPos + 1; 1188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom do 1218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (m_ints[--highestIntPos] != 0) 1238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return highestIntPos + 1; 1258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (highestIntPos > 0); 1288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return 0; 1308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int bitLength() 1338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // JDK 1.5: see Integer.numberOfLeadingZeros() 1358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int intLen = getUsedLength(); 1368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (intLen == 0) 1378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return 0; 1398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int last = intLen - 1; 1428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int highest = m_ints[last]; 1438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int bits = (last << 5) + 1; 1448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // A couple of binary search steps 1468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((highest & 0xffff0000) != 0) 1478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((highest & 0xff000000) != 0) 1498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom bits += 24; 1518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom highest >>>= 24; 1528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else 1548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom bits += 16; 1568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom highest >>>= 16; 1578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom else if (highest > 0x000000ff) 1608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom bits += 8; 1628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom highest >>>= 8; 1638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (highest != 1) 1668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom ++bits; 1688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom highest >>>= 1; 1698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return bits; 1728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom private int[] resizedInts(int newLen) 1758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int[] newInts = new int[newLen]; 1778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int oldLen = m_ints.length; 1788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int copyLen = oldLen < newLen ? oldLen : newLen; 1798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom System.arraycopy(m_ints, 0, newInts, 0, copyLen); 1808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return newInts; 1818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public BigInteger toBigInteger() 1848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int usedLen = getUsedLength(); 1868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (usedLen == 0) 1878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return ECConstants.ZERO; 1898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 1908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 1918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int highestInt = m_ints[usedLen - 1]; 1928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte[] temp = new byte[4]; 1938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int barrI = 0; 1948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom boolean trailingZeroBytesDone = false; 1958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = 3; j >= 0; j--) 1968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 1978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte thisByte = (byte) (highestInt >>> (8 * j)); 1988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (trailingZeroBytesDone || (thisByte != 0)) 1998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom trailingZeroBytesDone = true; 2018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom temp[barrI++] = thisByte; 2028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int barrLen = 4 * (usedLen - 1) + barrI; 2068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom byte[] barr = new byte[barrLen]; 2078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = 0; j < barrI; j++) 2088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom barr[j] = temp[j]; 2108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Highest value int is done now 2128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) 2148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = 3; j >= 0; j--) 2168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom barr[barrI++] = (byte) (m_ints[iarrJ] >>> (8 * j)); 2188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new BigInteger(1, barr); 2218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public void shiftLeft() 2248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int usedLen = getUsedLength(); 2268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (usedLen == 0) 2278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return; 2298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (m_ints[usedLen - 1] < 0) 2318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // highest bit of highest used byte is set, so shifting left will 2338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // make the IntArray one byte longer 2348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom usedLen++; 2358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (usedLen > m_ints.length) 2368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // make the m_ints one byte longer, because we need one more 2388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // byte which is not available in m_ints 2398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = resizedInts(m_ints.length + 1); 2408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom boolean carry = false; 2448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 0; i < usedLen; i++) 2458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // nextCarry is true if highest bit is set 2478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom boolean nextCarry = m_ints[i] < 0; 2488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints[i] <<= 1; 2498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (carry) 2508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // set lowest bit 2528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints[i] |= 1; 2538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom carry = nextCarry; 2558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public IntArray shiftLeft(int n) 2598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int usedLen = getUsedLength(); 2618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (usedLen == 0) 2628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this; 2648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (n == 0) 2678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return this; 2698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (n > 31) 2728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom throw new IllegalArgumentException("shiftLeft() for max 31 bits " 2748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom + ", " + n + "bit shift is not possible"); 2758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int[] newInts = new int[usedLen + 1]; 2788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int nm32 = 32 - n; 2808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom newInts[0] = m_ints[0] << n; 2818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 1; i < usedLen; i++) 2828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom newInts[i] = (m_ints[i] << n) | (m_ints[i - 1] >>> nm32); 2848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom newInts[usedLen] = m_ints[usedLen - 1] >>> nm32; 2868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new IntArray(newInts); 2888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 2908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public void addShifted(IntArray other, int shift) 2918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int usedLenOther = other.getUsedLength(); 2938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int newMinUsedLen = usedLenOther + shift; 2948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (newMinUsedLen > m_ints.length) 2958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 2968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = resizedInts(newMinUsedLen); 2978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom //System.out.println("Resize required"); 2988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 2998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 0; i < usedLenOther; i++) 3018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints[i + shift] ^= other.m_ints[i]; 3038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int getLength() 3078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return m_ints.length; 3098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public boolean testBit(int n) 3128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // theInt = n / 32 3148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int theInt = n >> 5; 3158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // theBit = n % 32 3168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int theBit = n & 0x1F; 3178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int tester = 1 << theBit; 3188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return ((m_ints[theInt] & tester) != 0); 3198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public void flipBit(int n) 3228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // theInt = n / 32 3248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int theInt = n >> 5; 3258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // theBit = n % 32 3268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int theBit = n & 0x1F; 3278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int flipper = 1 << theBit; 3288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints[theInt] ^= flipper; 3298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public void setBit(int n) 3328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // theInt = n / 32 3348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int theInt = n >> 5; 3358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // theBit = n % 32 3368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int theBit = n & 0x1F; 3378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int setter = 1 << theBit; 3388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints[theInt] |= setter; 3398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public IntArray multiply(IntArray other, int m) 3428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Lenght of c is 2m bits rounded up to the next int (32 bit) 3448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int t = (m + 31) >> 5; 3458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (m_ints.length < t) 3468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = resizedInts(t); 3488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray b = new IntArray(other.resizedInts(other.getLength() + 1)); 3518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray c = new IntArray((m + m + 31) >> 5); 3528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // IntArray c = new IntArray(t + t); 3538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int testBit = 1; 3548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int k = 0; k < 32; k++) 3558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = 0; j < t; j++) 3578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if ((m_ints[j] & testBit) != 0) 3598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // The kth bit of m_ints[j] is set 3618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom c.addShifted(b, j); 3628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom testBit <<= 1; 3658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom b.shiftLeft(); 3668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return c; 3688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 3698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // public IntArray multiplyLeftToRight(IntArray other, int m) { 3718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // // Lenght of c is 2m bits rounded up to the next int (32 bit) 3728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // int t = (m + 31) / 32; 3738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // if (m_ints.length < t) { 3748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // m_ints = resizedInts(t); 3758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // } 3768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // 3778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // IntArray b = new IntArray(other.resizedInts(other.getLength() + 1)); 3788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // IntArray c = new IntArray((m + m + 31) / 32); 3798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // // IntArray c = new IntArray(t + t); 3808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // int testBit = 1 << 31; 3818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // for (int k = 31; k >= 0; k--) { 3828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // for (int j = 0; j < t; j++) { 3838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // if ((m_ints[j] & testBit) != 0) { 3848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // // The kth bit of m_ints[j] is set 3858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // c.addShifted(b, j); 3868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // } 3878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // } 3888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // testBit >>>= 1; 3898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // if (k > 0) { 3908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // c.shiftLeft(); 3918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // } 3928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // } 3938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // return c; 3948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // } 3958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 3968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // TODO note, redPol.length must be 3 for TPB and 5 for PPB 3978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public void reduce(int m, int[] redPol) 3988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 3998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = m + m - 2; i >= m; i--) 4008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (testBit(i)) 4028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int bit = i - m; 4048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom flipBit(bit); 4058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom flipBit(i); 4068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int l = redPol.length; 4078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom while (--l >= 0) 4088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom flipBit(redPol[l] + bit); 4108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = resizedInts((m + 31) >> 5); 4148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public IntArray square(int m) 4178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // TODO make the table static final 4198212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom final int[] table = { 0x0, 0x1, 0x4, 0x5, 0x10, 0x11, 0x14, 0x15, 0x40, 4208212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55 }; 4218212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4228212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int t = (m + 31) >> 5; 4238212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (m_ints.length < t) 4248212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4258212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom m_ints = resizedInts(t); 4268212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4278212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4288212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray c = new IntArray(t + t); 4298212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4308212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // TODO twice the same code, put in separate private method 4318212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 0; i < t; i++) 4328212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4338212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int v0 = 0; 4348212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = 0; j < 4; j++) 4358212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4368212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom v0 = v0 >>> 8; 4378212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int u = (m_ints[i] >>> (j * 4)) & 0xF; 4388212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int w = table[u] << 24; 4398212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom v0 |= w; 4408212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4418212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom c.m_ints[i + i] = v0; 4428212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4438212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom v0 = 0; 4448212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int upper = m_ints[i] >>> 16; 4458212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int j = 0; j < 4; j++) 4468212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4478212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom v0 = v0 >>> 8; 4488212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int u = (upper >>> (j * 4)) & 0xF; 4498212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int w = table[u] << 24; 4508212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom v0 |= w; 4518212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4528212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom c.m_ints[i + i + 1] = v0; 4538212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4548212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return c; 4558212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4568212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4578212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public boolean equals(Object o) 4588212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4598212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (!(o instanceof IntArray)) 4608212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4618212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return false; 4628212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4638212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom IntArray other = (IntArray) o; 4648212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int usedLen = getUsedLength(); 4658212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (other.getUsedLength() != usedLen) 4668212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4678212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return false; 4688212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4698212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 0; i < usedLen; i++) 4708212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4718212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (m_ints[i] != other.m_ints[i]) 4728212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4738212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return false; 4748212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4758212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4768212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return true; 4778212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4788212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4798212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public int hashCode() 4808212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4818212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int usedLen = getUsedLength(); 4828212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int hash = 1; 4838212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = 0; i < usedLen; i++) 4848212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4858212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom hash = hash * 31 + m_ints[i]; 4868212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4878212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return hash; 4888212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4898212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4908212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public Object clone() 4918212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4928212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return new IntArray(Arrays.clone(m_ints)); 4938212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 4948212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 4958212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom public String toString() 4968212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 4978212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom int usedLen = getUsedLength(); 4988212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom if (usedLen == 0) 4998212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5008212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return "0"; 5018212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5028212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5038212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom StringBuffer sb = new StringBuffer(Integer 5048212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom .toBinaryString(m_ints[usedLen - 1])); 5058212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) 5068212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5078212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom String hexString = Integer.toBinaryString(m_ints[iarrJ]); 5088212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom 5098212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom // Add leading zeroes, except for highest significant int 5108212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom for (int i = hexString.length(); i < 8; i++) 5118212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom { 5128212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom hexString = "0" + hexString; 5138212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5148212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom sb.append(hexString); 5158212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5168212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom return sb.toString(); 5178212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom } 5188212855a312dc8ebe081a3e08b1d2d8f8757af02Brian Carlstrom} 519