15db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootpackage org.bouncycastle.math.ec; 25db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 35db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootimport org.bouncycastle.util.Arrays; 45db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 55db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootimport java.math.BigInteger; 65db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 75db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootclass LongArray 85db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root{ 95db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static long DEINTERLEAVE_MASK = 0x5555555555555555L; 105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * This expands 8 bit indices into 16 bit contents (high bit 14), by inserting 0s between bits. 135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * In a binary field, this operation is the same as squaring an 8 bit number. 145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static final int[] INTERLEAVE2_TABLE = new int[] 165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, 185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, 205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, 215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, 225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, 235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, 245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, 255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, 265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, 275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, 285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, 295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, 305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, 315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, 325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, 335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, 345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, 355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, 365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, 375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, 385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, 395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, 405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, 415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, 425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, 435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, 445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, 455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, 465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, 475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, 485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root }; 505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * This expands 7 bit indices into 21 bit contents (high bit 18), by inserting 0s between bits. 535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static final int[] INTERLEAVE3_TABLE = new int[] 555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00000, 0x00001, 0x00008, 0x00009, 0x00040, 0x00041, 0x00048, 0x00049, 575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00200, 0x00201, 0x00208, 0x00209, 0x00240, 0x00241, 0x00248, 0x00249, 585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01000, 0x01001, 0x01008, 0x01009, 0x01040, 0x01041, 0x01048, 0x01049, 595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01200, 0x01201, 0x01208, 0x01209, 0x01240, 0x01241, 0x01248, 0x01249, 605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x08000, 0x08001, 0x08008, 0x08009, 0x08040, 0x08041, 0x08048, 0x08049, 615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x08200, 0x08201, 0x08208, 0x08209, 0x08240, 0x08241, 0x08248, 0x08249, 625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x09000, 0x09001, 0x09008, 0x09009, 0x09040, 0x09041, 0x09048, 0x09049, 635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x09200, 0x09201, 0x09208, 0x09209, 0x09240, 0x09241, 0x09248, 0x09249, 645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x40000, 0x40001, 0x40008, 0x40009, 0x40040, 0x40041, 0x40048, 0x40049, 655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x40200, 0x40201, 0x40208, 0x40209, 0x40240, 0x40241, 0x40248, 0x40249, 665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x41000, 0x41001, 0x41008, 0x41009, 0x41040, 0x41041, 0x41048, 0x41049, 675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x41200, 0x41201, 0x41208, 0x41209, 0x41240, 0x41241, 0x41248, 0x41249, 685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x48000, 0x48001, 0x48008, 0x48009, 0x48040, 0x48041, 0x48048, 0x48049, 695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x48200, 0x48201, 0x48208, 0x48209, 0x48240, 0x48241, 0x48248, 0x48249, 705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x49000, 0x49001, 0x49008, 0x49009, 0x49040, 0x49041, 0x49048, 0x49049, 715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x49200, 0x49201, 0x49208, 0x49209, 0x49240, 0x49241, 0x49248, 0x49249 725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root }; 735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * This expands 8 bit indices into 32 bit contents (high bit 28), by inserting 0s between bits. 765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static final int[] INTERLEAVE4_TABLE = new int[] 785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00000000, 0x00000001, 0x00000010, 0x00000011, 0x00000100, 0x00000101, 0x00000110, 0x00000111, 805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00001000, 0x00001001, 0x00001010, 0x00001011, 0x00001100, 0x00001101, 0x00001110, 0x00001111, 815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00010000, 0x00010001, 0x00010010, 0x00010011, 0x00010100, 0x00010101, 0x00010110, 0x00010111, 825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00011000, 0x00011001, 0x00011010, 0x00011011, 0x00011100, 0x00011101, 0x00011110, 0x00011111, 835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00100000, 0x00100001, 0x00100010, 0x00100011, 0x00100100, 0x00100101, 0x00100110, 0x00100111, 845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00101000, 0x00101001, 0x00101010, 0x00101011, 0x00101100, 0x00101101, 0x00101110, 0x00101111, 855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00110000, 0x00110001, 0x00110010, 0x00110011, 0x00110100, 0x00110101, 0x00110110, 0x00110111, 865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00111000, 0x00111001, 0x00111010, 0x00111011, 0x00111100, 0x00111101, 0x00111110, 0x00111111, 875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01000000, 0x01000001, 0x01000010, 0x01000011, 0x01000100, 0x01000101, 0x01000110, 0x01000111, 885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01001000, 0x01001001, 0x01001010, 0x01001011, 0x01001100, 0x01001101, 0x01001110, 0x01001111, 895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01010000, 0x01010001, 0x01010010, 0x01010011, 0x01010100, 0x01010101, 0x01010110, 0x01010111, 905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01011000, 0x01011001, 0x01011010, 0x01011011, 0x01011100, 0x01011101, 0x01011110, 0x01011111, 915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01100000, 0x01100001, 0x01100010, 0x01100011, 0x01100100, 0x01100101, 0x01100110, 0x01100111, 925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01101000, 0x01101001, 0x01101010, 0x01101011, 0x01101100, 0x01101101, 0x01101110, 0x01101111, 935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01110000, 0x01110001, 0x01110010, 0x01110011, 0x01110100, 0x01110101, 0x01110110, 0x01110111, 945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x01111000, 0x01111001, 0x01111010, 0x01111011, 0x01111100, 0x01111101, 0x01111110, 0x01111111, 955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x10000000, 0x10000001, 0x10000010, 0x10000011, 0x10000100, 0x10000101, 0x10000110, 0x10000111, 965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x10001000, 0x10001001, 0x10001010, 0x10001011, 0x10001100, 0x10001101, 0x10001110, 0x10001111, 975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x10010000, 0x10010001, 0x10010010, 0x10010011, 0x10010100, 0x10010101, 0x10010110, 0x10010111, 985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x10011000, 0x10011001, 0x10011010, 0x10011011, 0x10011100, 0x10011101, 0x10011110, 0x10011111, 995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x10100000, 0x10100001, 0x10100010, 0x10100011, 0x10100100, 0x10100101, 0x10100110, 0x10100111, 1005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x10101000, 0x10101001, 0x10101010, 0x10101011, 0x10101100, 0x10101101, 0x10101110, 0x10101111, 1015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x10110000, 0x10110001, 0x10110010, 0x10110011, 0x10110100, 0x10110101, 0x10110110, 0x10110111, 1025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x10111000, 0x10111001, 0x10111010, 0x10111011, 0x10111100, 0x10111101, 0x10111110, 0x10111111, 1035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x11000000, 0x11000001, 0x11000010, 0x11000011, 0x11000100, 0x11000101, 0x11000110, 0x11000111, 1045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x11001000, 0x11001001, 0x11001010, 0x11001011, 0x11001100, 0x11001101, 0x11001110, 0x11001111, 1055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x11010000, 0x11010001, 0x11010010, 0x11010011, 0x11010100, 0x11010101, 0x11010110, 0x11010111, 1065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x11011000, 0x11011001, 0x11011010, 0x11011011, 0x11011100, 0x11011101, 0x11011110, 0x11011111, 1075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x11100000, 0x11100001, 0x11100010, 0x11100011, 0x11100100, 0x11100101, 0x11100110, 0x11100111, 1085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x11101000, 0x11101001, 0x11101010, 0x11101011, 0x11101100, 0x11101101, 0x11101110, 0x11101111, 1095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x11110000, 0x11110001, 0x11110010, 0x11110011, 0x11110100, 0x11110101, 0x11110110, 0x11110111, 1105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x11111000, 0x11111001, 0x11111010, 0x11111011, 0x11111100, 0x11111101, 0x11111110, 0x11111111 1115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root }; 1125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 1145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * This expands 7 bit indices into 35 bit contents (high bit 30), by inserting 0s between bits. 1155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 1165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static final int[] INTERLEAVE5_TABLE = new int[] { 1175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00000000, 0x00000001, 0x00000020, 0x00000021, 0x00000400, 0x00000401, 0x00000420, 0x00000421, 1185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00008000, 0x00008001, 0x00008020, 0x00008021, 0x00008400, 0x00008401, 0x00008420, 0x00008421, 1195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00100000, 0x00100001, 0x00100020, 0x00100021, 0x00100400, 0x00100401, 0x00100420, 0x00100421, 1205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x00108000, 0x00108001, 0x00108020, 0x00108021, 0x00108400, 0x00108401, 0x00108420, 0x00108421, 1215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x02000000, 0x02000001, 0x02000020, 0x02000021, 0x02000400, 0x02000401, 0x02000420, 0x02000421, 1225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x02008000, 0x02008001, 0x02008020, 0x02008021, 0x02008400, 0x02008401, 0x02008420, 0x02008421, 1235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x02100000, 0x02100001, 0x02100020, 0x02100021, 0x02100400, 0x02100401, 0x02100420, 0x02100421, 1245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x02108000, 0x02108001, 0x02108020, 0x02108021, 0x02108400, 0x02108401, 0x02108420, 0x02108421, 1255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x40000000, 0x40000001, 0x40000020, 0x40000021, 0x40000400, 0x40000401, 0x40000420, 0x40000421, 1265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x40008000, 0x40008001, 0x40008020, 0x40008021, 0x40008400, 0x40008401, 0x40008420, 0x40008421, 1275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x40100000, 0x40100001, 0x40100020, 0x40100021, 0x40100400, 0x40100401, 0x40100420, 0x40100421, 1285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x40108000, 0x40108001, 0x40108020, 0x40108021, 0x40108400, 0x40108401, 0x40108420, 0x40108421, 1295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x42000000, 0x42000001, 0x42000020, 0x42000021, 0x42000400, 0x42000401, 0x42000420, 0x42000421, 1305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x42008000, 0x42008001, 0x42008020, 0x42008021, 0x42008400, 0x42008401, 0x42008420, 0x42008421, 1315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x42100000, 0x42100001, 0x42100020, 0x42100021, 0x42100400, 0x42100401, 0x42100420, 0x42100421, 1325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x42108000, 0x42108001, 0x42108020, 0x42108021, 0x42108400, 0x42108401, 0x42108420, 0x42108421 1335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root }; 1345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 1355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 1365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * This expands 9 bit indices into 63 bit (long) contents (high bit 56), by inserting 0s between bits. 1375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 1385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static final long[] INTERLEAVE7_TABLE = new long[] 1395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 1405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000000000000L, 0x0000000000000001L, 0x0000000000000080L, 0x0000000000000081L, 1415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000000004000L, 0x0000000000004001L, 0x0000000000004080L, 0x0000000000004081L, 1425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000000200000L, 0x0000000000200001L, 0x0000000000200080L, 0x0000000000200081L, 1435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000000204000L, 0x0000000000204001L, 0x0000000000204080L, 0x0000000000204081L, 1445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000010000000L, 0x0000000010000001L, 0x0000000010000080L, 0x0000000010000081L, 1455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000010004000L, 0x0000000010004001L, 0x0000000010004080L, 0x0000000010004081L, 1465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000010200000L, 0x0000000010200001L, 0x0000000010200080L, 0x0000000010200081L, 1475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000010204000L, 0x0000000010204001L, 0x0000000010204080L, 0x0000000010204081L, 1485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000800000000L, 0x0000000800000001L, 0x0000000800000080L, 0x0000000800000081L, 1495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000800004000L, 0x0000000800004001L, 0x0000000800004080L, 0x0000000800004081L, 1505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000800200000L, 0x0000000800200001L, 0x0000000800200080L, 0x0000000800200081L, 1515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000800204000L, 0x0000000800204001L, 0x0000000800204080L, 0x0000000800204081L, 1525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000810000000L, 0x0000000810000001L, 0x0000000810000080L, 0x0000000810000081L, 1535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000810004000L, 0x0000000810004001L, 0x0000000810004080L, 0x0000000810004081L, 1545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000810200000L, 0x0000000810200001L, 0x0000000810200080L, 0x0000000810200081L, 1555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000000810204000L, 0x0000000810204001L, 0x0000000810204080L, 0x0000000810204081L, 1565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040000000000L, 0x0000040000000001L, 0x0000040000000080L, 0x0000040000000081L, 1575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040000004000L, 0x0000040000004001L, 0x0000040000004080L, 0x0000040000004081L, 1585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040000200000L, 0x0000040000200001L, 0x0000040000200080L, 0x0000040000200081L, 1595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040000204000L, 0x0000040000204001L, 0x0000040000204080L, 0x0000040000204081L, 1605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040010000000L, 0x0000040010000001L, 0x0000040010000080L, 0x0000040010000081L, 1615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040010004000L, 0x0000040010004001L, 0x0000040010004080L, 0x0000040010004081L, 1625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040010200000L, 0x0000040010200001L, 0x0000040010200080L, 0x0000040010200081L, 1635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040010204000L, 0x0000040010204001L, 0x0000040010204080L, 0x0000040010204081L, 1645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040800000000L, 0x0000040800000001L, 0x0000040800000080L, 0x0000040800000081L, 1655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040800004000L, 0x0000040800004001L, 0x0000040800004080L, 0x0000040800004081L, 1665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040800200000L, 0x0000040800200001L, 0x0000040800200080L, 0x0000040800200081L, 1675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040800204000L, 0x0000040800204001L, 0x0000040800204080L, 0x0000040800204081L, 1685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040810000000L, 0x0000040810000001L, 0x0000040810000080L, 0x0000040810000081L, 1695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040810004000L, 0x0000040810004001L, 0x0000040810004080L, 0x0000040810004081L, 1705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040810200000L, 0x0000040810200001L, 0x0000040810200080L, 0x0000040810200081L, 1715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0000040810204000L, 0x0000040810204001L, 0x0000040810204080L, 0x0000040810204081L, 1725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000000000000L, 0x0002000000000001L, 0x0002000000000080L, 0x0002000000000081L, 1735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000000004000L, 0x0002000000004001L, 0x0002000000004080L, 0x0002000000004081L, 1745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000000200000L, 0x0002000000200001L, 0x0002000000200080L, 0x0002000000200081L, 1755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000000204000L, 0x0002000000204001L, 0x0002000000204080L, 0x0002000000204081L, 1765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000010000000L, 0x0002000010000001L, 0x0002000010000080L, 0x0002000010000081L, 1775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000010004000L, 0x0002000010004001L, 0x0002000010004080L, 0x0002000010004081L, 1785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000010200000L, 0x0002000010200001L, 0x0002000010200080L, 0x0002000010200081L, 1795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000010204000L, 0x0002000010204001L, 0x0002000010204080L, 0x0002000010204081L, 1805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000800000000L, 0x0002000800000001L, 0x0002000800000080L, 0x0002000800000081L, 1815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000800004000L, 0x0002000800004001L, 0x0002000800004080L, 0x0002000800004081L, 1825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000800200000L, 0x0002000800200001L, 0x0002000800200080L, 0x0002000800200081L, 1835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000800204000L, 0x0002000800204001L, 0x0002000800204080L, 0x0002000800204081L, 1845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000810000000L, 0x0002000810000001L, 0x0002000810000080L, 0x0002000810000081L, 1855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000810004000L, 0x0002000810004001L, 0x0002000810004080L, 0x0002000810004081L, 1865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000810200000L, 0x0002000810200001L, 0x0002000810200080L, 0x0002000810200081L, 1875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002000810204000L, 0x0002000810204001L, 0x0002000810204080L, 0x0002000810204081L, 1885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040000000000L, 0x0002040000000001L, 0x0002040000000080L, 0x0002040000000081L, 1895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040000004000L, 0x0002040000004001L, 0x0002040000004080L, 0x0002040000004081L, 1905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040000200000L, 0x0002040000200001L, 0x0002040000200080L, 0x0002040000200081L, 1915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040000204000L, 0x0002040000204001L, 0x0002040000204080L, 0x0002040000204081L, 1925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040010000000L, 0x0002040010000001L, 0x0002040010000080L, 0x0002040010000081L, 1935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040010004000L, 0x0002040010004001L, 0x0002040010004080L, 0x0002040010004081L, 1945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040010200000L, 0x0002040010200001L, 0x0002040010200080L, 0x0002040010200081L, 1955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040010204000L, 0x0002040010204001L, 0x0002040010204080L, 0x0002040010204081L, 1965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040800000000L, 0x0002040800000001L, 0x0002040800000080L, 0x0002040800000081L, 1975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040800004000L, 0x0002040800004001L, 0x0002040800004080L, 0x0002040800004081L, 1985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040800200000L, 0x0002040800200001L, 0x0002040800200080L, 0x0002040800200081L, 1995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040800204000L, 0x0002040800204001L, 0x0002040800204080L, 0x0002040800204081L, 2005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040810000000L, 0x0002040810000001L, 0x0002040810000080L, 0x0002040810000081L, 2015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040810004000L, 0x0002040810004001L, 0x0002040810004080L, 0x0002040810004081L, 2025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040810200000L, 0x0002040810200001L, 0x0002040810200080L, 0x0002040810200081L, 2035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0002040810204000L, 0x0002040810204001L, 0x0002040810204080L, 0x0002040810204081L, 2045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000000000000L, 0x0100000000000001L, 0x0100000000000080L, 0x0100000000000081L, 2055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000000004000L, 0x0100000000004001L, 0x0100000000004080L, 0x0100000000004081L, 2065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000000200000L, 0x0100000000200001L, 0x0100000000200080L, 0x0100000000200081L, 2075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000000204000L, 0x0100000000204001L, 0x0100000000204080L, 0x0100000000204081L, 2085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000010000000L, 0x0100000010000001L, 0x0100000010000080L, 0x0100000010000081L, 2095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000010004000L, 0x0100000010004001L, 0x0100000010004080L, 0x0100000010004081L, 2105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000010200000L, 0x0100000010200001L, 0x0100000010200080L, 0x0100000010200081L, 2115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000010204000L, 0x0100000010204001L, 0x0100000010204080L, 0x0100000010204081L, 2125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000800000000L, 0x0100000800000001L, 0x0100000800000080L, 0x0100000800000081L, 2135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000800004000L, 0x0100000800004001L, 0x0100000800004080L, 0x0100000800004081L, 2145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000800200000L, 0x0100000800200001L, 0x0100000800200080L, 0x0100000800200081L, 2155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000800204000L, 0x0100000800204001L, 0x0100000800204080L, 0x0100000800204081L, 2165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000810000000L, 0x0100000810000001L, 0x0100000810000080L, 0x0100000810000081L, 2175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000810004000L, 0x0100000810004001L, 0x0100000810004080L, 0x0100000810004081L, 2185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000810200000L, 0x0100000810200001L, 0x0100000810200080L, 0x0100000810200081L, 2195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100000810204000L, 0x0100000810204001L, 0x0100000810204080L, 0x0100000810204081L, 2205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040000000000L, 0x0100040000000001L, 0x0100040000000080L, 0x0100040000000081L, 2215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040000004000L, 0x0100040000004001L, 0x0100040000004080L, 0x0100040000004081L, 2225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040000200000L, 0x0100040000200001L, 0x0100040000200080L, 0x0100040000200081L, 2235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040000204000L, 0x0100040000204001L, 0x0100040000204080L, 0x0100040000204081L, 2245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040010000000L, 0x0100040010000001L, 0x0100040010000080L, 0x0100040010000081L, 2255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040010004000L, 0x0100040010004001L, 0x0100040010004080L, 0x0100040010004081L, 2265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040010200000L, 0x0100040010200001L, 0x0100040010200080L, 0x0100040010200081L, 2275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040010204000L, 0x0100040010204001L, 0x0100040010204080L, 0x0100040010204081L, 2285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040800000000L, 0x0100040800000001L, 0x0100040800000080L, 0x0100040800000081L, 2295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040800004000L, 0x0100040800004001L, 0x0100040800004080L, 0x0100040800004081L, 2305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040800200000L, 0x0100040800200001L, 0x0100040800200080L, 0x0100040800200081L, 2315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040800204000L, 0x0100040800204001L, 0x0100040800204080L, 0x0100040800204081L, 2325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040810000000L, 0x0100040810000001L, 0x0100040810000080L, 0x0100040810000081L, 2335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040810004000L, 0x0100040810004001L, 0x0100040810004080L, 0x0100040810004081L, 2345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040810200000L, 0x0100040810200001L, 0x0100040810200080L, 0x0100040810200081L, 2355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0100040810204000L, 0x0100040810204001L, 0x0100040810204080L, 0x0100040810204081L, 2365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000000000000L, 0x0102000000000001L, 0x0102000000000080L, 0x0102000000000081L, 2375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000000004000L, 0x0102000000004001L, 0x0102000000004080L, 0x0102000000004081L, 2385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000000200000L, 0x0102000000200001L, 0x0102000000200080L, 0x0102000000200081L, 2395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000000204000L, 0x0102000000204001L, 0x0102000000204080L, 0x0102000000204081L, 2405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000010000000L, 0x0102000010000001L, 0x0102000010000080L, 0x0102000010000081L, 2415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000010004000L, 0x0102000010004001L, 0x0102000010004080L, 0x0102000010004081L, 2425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000010200000L, 0x0102000010200001L, 0x0102000010200080L, 0x0102000010200081L, 2435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000010204000L, 0x0102000010204001L, 0x0102000010204080L, 0x0102000010204081L, 2445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000800000000L, 0x0102000800000001L, 0x0102000800000080L, 0x0102000800000081L, 2455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000800004000L, 0x0102000800004001L, 0x0102000800004080L, 0x0102000800004081L, 2465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000800200000L, 0x0102000800200001L, 0x0102000800200080L, 0x0102000800200081L, 2475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000800204000L, 0x0102000800204001L, 0x0102000800204080L, 0x0102000800204081L, 2485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000810000000L, 0x0102000810000001L, 0x0102000810000080L, 0x0102000810000081L, 2495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000810004000L, 0x0102000810004001L, 0x0102000810004080L, 0x0102000810004081L, 2505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000810200000L, 0x0102000810200001L, 0x0102000810200080L, 0x0102000810200081L, 2515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102000810204000L, 0x0102000810204001L, 0x0102000810204080L, 0x0102000810204081L, 2525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040000000000L, 0x0102040000000001L, 0x0102040000000080L, 0x0102040000000081L, 2535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040000004000L, 0x0102040000004001L, 0x0102040000004080L, 0x0102040000004081L, 2545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040000200000L, 0x0102040000200001L, 0x0102040000200080L, 0x0102040000200081L, 2555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040000204000L, 0x0102040000204001L, 0x0102040000204080L, 0x0102040000204081L, 2565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040010000000L, 0x0102040010000001L, 0x0102040010000080L, 0x0102040010000081L, 2575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040010004000L, 0x0102040010004001L, 0x0102040010004080L, 0x0102040010004081L, 2585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040010200000L, 0x0102040010200001L, 0x0102040010200080L, 0x0102040010200081L, 2595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040010204000L, 0x0102040010204001L, 0x0102040010204080L, 0x0102040010204081L, 2605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040800000000L, 0x0102040800000001L, 0x0102040800000080L, 0x0102040800000081L, 2615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040800004000L, 0x0102040800004001L, 0x0102040800004080L, 0x0102040800004081L, 2625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040800200000L, 0x0102040800200001L, 0x0102040800200080L, 0x0102040800200081L, 2635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040800204000L, 0x0102040800204001L, 0x0102040800204080L, 0x0102040800204081L, 2645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040810000000L, 0x0102040810000001L, 0x0102040810000080L, 0x0102040810000081L, 2655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040810004000L, 0x0102040810004001L, 0x0102040810004080L, 0x0102040810004081L, 2665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040810200000L, 0x0102040810200001L, 0x0102040810200080L, 0x0102040810200081L, 2675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0x0102040810204000L, 0x0102040810204001L, 0x0102040810204080L, 0x0102040810204081L 2685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root }; 2695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // For toString(); must have length 64 2715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static final String ZEROES = "0000000000000000000000000000000000000000000000000000000000000000"; 2725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root final static byte[] bitLengths = 2745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 2755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 2765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 2775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 2805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 2815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 2825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 2835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 2845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 2855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 2865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 2875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 2885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 2895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 2905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 2915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root }; 2925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // TODO make m fixed for the LongArray, and hence compute T once and for all 2945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private long[] m_ints; 2965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 2975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray(int intLen) 2985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 2995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints = new long[intLen]; 3005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray(long[] ints) 3035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints = ints; 3055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray(long[] ints, int off, int len) 3085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (off == 0 && len == ints.length) 3105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints = ints; 3125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 3145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints = new long[len]; 3165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root System.arraycopy(ints, off, m_ints, 0, len); 3175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray(BigInteger bigInt) 3215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (bigInt == null || bigInt.signum() < 0) 3235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root throw new IllegalArgumentException("invalid F2m field value"); 3255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (bigInt.signum() == 0) 3285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints = new long[] { 0L }; 3305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return; 3315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root byte[] barr = bigInt.toByteArray(); 3345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int barrLen = barr.length; 3355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int barrStart = 0; 3365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (barr[0] == 0) 3375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // First byte is 0 to enforce highest (=sign) bit is zero. 3395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // In this case ignore barr[0]. 3405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root barrLen--; 3415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root barrStart = 1; 3425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int intLen = (barrLen + 7) / 8; 3445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints = new long[intLen]; 3455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int iarrJ = intLen - 1; 3475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int rem = barrLen % 8 + barrStart; 3485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long temp = 0; 3495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int barrI = barrStart; 3505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (barrStart < rem) 3515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (; barrI < rem; barrI++) 3535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root temp <<= 8; 3555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int barrBarrI = barr[barrI] & 0xFF; 3565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root temp |= barrBarrI; 3575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints[iarrJ--] = temp; 3595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (; iarrJ >= 0; iarrJ--) 3625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root temp = 0; 3645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < 8; i++) 3655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root temp <<= 8; 3675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int barrBarrI = barr[barrI++] & 0xFF; 3685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root temp |= barrBarrI; 3695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints[iarrJ] = temp; 3715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public boolean isZero() 3755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] a = m_ints; 3775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < a.length; ++i) 3785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (a[i] != 0L) 3805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return false; 3825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return true; 3855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public int getUsedLength() 3885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return getUsedLengthFrom(m_ints.length); 3905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 3915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public int getUsedLengthFrom(int from) 3935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] a = m_ints; 3955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root from = Math.min(from, a.length); 3965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 3975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (from < 1) 3985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 3995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return 0; 4005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // Check if first element will act as sentinel 4035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (a[0] != 0) 4045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (a[--from] == 0) 4065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return from + 1; 4095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root do 4125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (a[--from] != 0) 4145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return from + 1; 4165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (from > 0); 4195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return 0; 4215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public int degree() 4245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i = m_ints.length; 4265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long w; 4275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root do 4285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (i == 0) 4305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return 0; 4325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root w = m_ints[--i]; 4345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (w == 0); 4365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return (i << 6) + bitLength(w); 4385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private int degreeFrom(int limit) 4415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i = (limit + 62) >>> 6; 4435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long w; 4445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root do 4455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (i == 0) 4475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return 0; 4495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root w = m_ints[--i]; 4515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (w == 0); 4535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return (i << 6) + bitLength(w); 4555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private int lowestCoefficient() 4585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (int i = 0; i < m_ints.length; ++i) 4605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long mi = m_ints[i]; 4625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (mi != 0) 4635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int j = 0; 4655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while ((mi & 0xFFL) == 0) 4665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// j += 8; 4685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// mi >>>= 8; 4695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while ((mi & 1L) == 0) 4715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 4725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// ++j; 4735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// mi >>>= 1; 4745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return (i << 6) + j; 4765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return -1; 4795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 4805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static int bitLength(long w) 4825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int u = (int)(w >>> 32), b; 4845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (u == 0) 4855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root u = (int)w; 4875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root b = 0; 4885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 4905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root b = 32; 4925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 4935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 4945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int t = u >>> 16, k; 4955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (t == 0) 4965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 4975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root t = u >>> 8; 4985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root k = (t == 0) ? bitLengths[u] : 8 + bitLengths[t]; 4995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 5015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int v = t >>> 8; 5035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root k = (v == 0) ? 16 + bitLengths[t] : 24 + bitLengths[v]; 5045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return b + k; 5075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private long[] resizedInts(int newLen) 5105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] newInts = new long[newLen]; 5125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root System.arraycopy(m_ints, 0, newInts, 0, Math.min(m_ints.length, newLen)); 5135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return newInts; 5145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public BigInteger toBigInteger() 5175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int usedLen = getUsedLength(); 5195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (usedLen == 0) 5205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return ECConstants.ZERO; 5225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long highestInt = m_ints[usedLen - 1]; 5255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root byte[] temp = new byte[8]; 5265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int barrI = 0; 5275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root boolean trailingZeroBytesDone = false; 5285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int j = 7; j >= 0; j--) 5295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root byte thisByte = (byte)(highestInt >>> (8 * j)); 5315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (trailingZeroBytesDone || (thisByte != 0)) 5325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root trailingZeroBytesDone = true; 5345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root temp[barrI++] = thisByte; 5355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int barrLen = 8 * (usedLen - 1) + barrI; 5395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root byte[] barr = new byte[barrLen]; 5405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int j = 0; j < barrI; j++) 5415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root barr[j] = temp[j]; 5435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // Highest value int is done now 5455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) 5475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long mi = m_ints[iarrJ]; 5495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int j = 7; j >= 0; j--) 5505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root barr[barrI++] = (byte)(mi >>> (8 * j)); 5525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new BigInteger(1, barr); 5555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static long shiftUp(long[] x, int xOff, int count) 5585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 5595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long prev = 0; 5605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (int i = 0; i < count; ++i) 5615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 5625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long next = x[xOff + i]; 5635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x[xOff + i] = (next << 1) | prev; 5645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// prev = next >>> 63; 5655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 5665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return prev; 5675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 5685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long shiftUp(long[] x, int xOff, int count, int shift) 5705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int shiftInv = 64 - shift; 5725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long prev = 0; 5735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 5745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long next = x[xOff + i]; 5765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x[xOff + i] = (next << shift) | prev; 5775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root prev = next >>> shiftInv; 5785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return prev; 5805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long shiftUp(long[] x, int xOff, long[] z, int zOff, int count, int shift) 5835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int shiftInv = 64 - shift; 5855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long prev = 0; 5865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 5875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long next = x[xOff + i]; 5895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root z[zOff + i] = (next << shift) | prev; 5905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root prev = next >>> shiftInv; 5915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return prev; 5935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 5945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 5955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray addOne() 5965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (m_ints.length == 0) 5985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 5995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new LongArray(new long[]{ 1L }); 6005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int resultLen = Math.max(1, getUsedLength()); 6035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] ints = resizedInts(resultLen); 6045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ints[0] ^= 1L; 6055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new LongArray(ints); 6065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private void addShiftedByBits(LongArray other, int bits) 6095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 6105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int words = bits >>> 6; 6115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int shift = bits & 0x3F; 6125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 6135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (shift == 0) 6145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 6155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// addShiftedByWords(other, words); 6165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return; 6175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 6185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 6195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int otherUsedLen = other.getUsedLength(); 6205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (otherUsedLen == 0) 6215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 6225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return; 6235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 6245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 6255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int minLen = otherUsedLen + words + 1; 6265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (minLen > m_ints.length) 6275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 6285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// m_ints = resizedInts(minLen); 6295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 6305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 6315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long carry = addShiftedByBits(m_ints, words, other.m_ints, 0, otherUsedLen, shift); 6325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// m_ints[otherUsedLen + words] ^= carry; 6335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 6345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private void addShiftedByBitsSafe(LongArray other, int otherDegree, int bits) 6365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int otherLen = (otherDegree + 63) >>> 6; 6385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int words = bits >>> 6; 6405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int shift = bits & 0x3F; 6415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (shift == 0) 6435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root add(m_ints, words, other.m_ints, 0, otherLen); 6455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return; 6465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long carry = addShiftedUp(m_ints, words, other.m_ints, 0, otherLen, shift); 6495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (carry != 0L) 6505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints[otherLen + words] ^= carry; 6525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long addShiftedUp(long[] x, int xOff, long[] y, int yOff, int count, int shift) 6565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int shiftInv = 64 - shift; 6585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long prev = 0; 6595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 6605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long next = y[yOff + i]; 6625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x[xOff + i] ^= (next << shift) | prev; 6635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root prev = next >>> shiftInv; 6645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return prev; 6665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long addShiftedDown(long[] x, int xOff, long[] y, int yOff, int count, int shift) 6695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int shiftInv = 64 - shift; 6715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long prev = 0; 6725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i = count; 6735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--i >= 0) 6745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long next = y[yOff + i]; 6765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x[xOff + i] ^= (next >>> shift) | prev; 6775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root prev = next << shiftInv; 6785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return prev; 6805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public void addShiftedByWords(LongArray other, int words) 6835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int otherUsedLen = other.getUsedLength(); 6855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (otherUsedLen == 0) 6865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return; 6885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int minLen = otherUsedLen + words; 6915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (minLen > m_ints.length) 6925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 6935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root m_ints = resizedInts(minLen); 6945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root add(m_ints, words, other.m_ints, 0, otherUsedLen); 6975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 6985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 6995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void add(long[] x, int xOff, long[] y, int yOff, int count) 7005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 7025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x[xOff + i] ^= y[yOff + i]; 7045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void add(long[] x, int xOff, long[] y, int yOff, long[] z, int zOff, int count) 7085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 7105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root z[zOff + i] = x[xOff + i] ^ y[yOff + i]; 7125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void addBoth(long[] x, int xOff, long[] y1, int y1Off, long[] y2, int y2Off, int count) 7165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 7185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x[xOff + i] ^= y1[y1Off + i] ^ y2[y2Off + i]; 7205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void distribute(long[] x, int src, int dst1, int dst2, int count) 7245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 7265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long v = x[src + i]; 7285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x[dst1 + i] ^= v; 7295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x[dst2 + i] ^= v; 7305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public int getLength() 7345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return m_ints.length; 7365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void flipWord(long[] buf, int off, int bit, long word) 7395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int n = off + (bit >>> 6); 7415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int shift = bit & 0x3F; 7425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (shift == 0) 7435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root buf[n] ^= word; 7455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 7475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root buf[n] ^= word << shift; 7495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root word >>>= (64 - shift); 7505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (word != 0) 7515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root buf[++n] ^= word; 7535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static long getWord(long[] buf, int off, int len, int bit) 7585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 7595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int n = off + (bit >>> 6); 7605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int shift = bit & 0x3F; 7615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (shift == 0) 7625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 7635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return buf[n]; 7645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 7655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long result = buf[n] >>> shift; 7665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (++n < len) 7675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 7685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// result |= buf[n] << (64 - shift); 7695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 7705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return result; 7715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 7725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public boolean testBitZero() 7745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return m_ints.length > 0 && (m_ints[0] & 1L) != 0; 7765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static boolean testBit(long[] buf, int off, int n) 7795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // theInt = n / 64 7815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int theInt = n >>> 6; 7825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // theBit = n % 64 7835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int theBit = n & 0x3F; 7845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long tester = 1L << theBit; 7855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return (buf[off + theInt] & tester) != 0; 7865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void flipBit(long[] buf, int off, int n) 7895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 7905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // theInt = n / 64 7915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int theInt = n >>> 6; 7925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // theBit = n % 64 7935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int theBit = n & 0x3F; 7945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long flipper = 1L << theBit; 7955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root buf[off + theInt] ^= flipper; 7965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 7975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 7985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static void setBit(long[] buf, int off, int n) 7995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 8005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// // theInt = n / 64 8015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int theInt = n >>> 6; 8025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// // theBit = n % 64 8035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int theBit = n & 0x3F; 8045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long setter = 1L << theBit; 8055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// buf[off + theInt] |= setter; 8065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 8075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 8085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static void clearBit(long[] buf, int off, int n) 8095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 8105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// // theInt = n / 64 8115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int theInt = n >>> 6; 8125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// // theBit = n % 64 8135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int theBit = n & 0x3F; 8145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long setter = 1L << theBit; 8155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// buf[off + theInt] &= ~setter; 8165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 8175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void multiplyWord(long a, long[] b, int bLen, long[] c, int cOff) 8195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if ((a & 1L) != 0L) 8215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root add(c, cOff, b, 0, bLen); 8235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int k = 1; 8255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while ((a >>>= 1) != 0) 8265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if ((a & 1L) != 0L) 8285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long carry = addShiftedUp(c, cOff, b, 0, bLen, k); 8305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (carry != 0) 8315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root c[cOff + bLen] ^= carry; 8335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ++k; 8365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray modMultiplyLD(LongArray other, int m, int[] ks) 8405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 8425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Find out the degree of each argument and handle the zero cases 8435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 8445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aDeg = degree(); 8455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aDeg == 0) 8465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this; 8485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bDeg = other.degree(); 8505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (bDeg == 0) 8515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return other; 8535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 8565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Swap if necessary so that A is the smaller argument 8575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 8585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray A = this, B = other; 8595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aDeg > bDeg) 8605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root A = other; B = this; 8625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int tmp = aDeg; aDeg = bDeg; bDeg = tmp; 8635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 8665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Establish the word lengths of the arguments and result 8675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 8685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aLen = (aDeg + 63) >>> 6; 8695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bLen = (bDeg + 63) >>> 6; 8705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int cLen = (aDeg + bDeg + 62) >>> 6; 8715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aLen == 1) 8735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long a = A.m_ints[0]; 8755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (a == 1L) 8765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 8775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return B; 8785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 8815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Fast path for small A, with performance dependent only on the number of set bits 8825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 8835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] c = new long[cLen]; 8845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root multiplyWord(a, B.m_ints, bLen, c, 0); 8855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 8875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Reduce the raw answer against the reduction coefficients 8885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 8895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return reduceResult(c, 0, cLen, m, ks); 8905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 8915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 8935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Determine if B will get bigger during shifting 8945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 8955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bMax = (bDeg + 7 + 63) >>> 6; 8965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 8975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 8985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Lookup table for the offset of each B in the tables 8995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 9005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int[] ti = new int[16]; 9015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 9035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Precompute table of all 4-bit products of B 9045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 9055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] T0 = new long[bMax << 4]; 9065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int tOff = bMax; 9075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ti[1] = tOff; 9085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root System.arraycopy(B.m_ints, 0, T0, tOff, bLen); 9095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 2; i < 16; ++i) 9105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ti[i] = (tOff += bMax); 9125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if ((i & 1) == 0) 9135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root shiftUp(T0, tOff >>> 1, T0, tOff, bMax, 1); 9155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 9175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root add(T0, bMax, T0, tOff - bMax, T0, tOff, bMax); 9195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 9235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Second table with all 4-bit products of B shifted 4 bits 9245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 9255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] T1 = new long[T0.length]; 9265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root shiftUp(T0, 0, T1, 0, T0.length, 4); 9275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// shiftUp(T0, bMax, T1, bMax, tOff, 4); 9285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] a = A.m_ints; 9305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] c = new long[cLen]; 9315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int MASK = 0xF; 9335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 9355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Lopez-Dahab algorithm 9365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 9375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int k = 56; k >= 0; k -= 8) 9395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int j = 1; j < aLen; j += 2) 9415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aVal = (int)(a[j] >>> k); 9435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int u = aVal & MASK; 9445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int v = (aVal >>> 4) & MASK; 9455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root addBoth(c, j - 1, T0, ti[u], T1, ti[v], bMax); 9465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root shiftUp(c, 0, cLen, 8); 9485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int k = 56; k >= 0; k -= 8) 9515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int j = 0; j < aLen; j += 2) 9535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aVal = (int)(a[j] >>> k); 9555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int u = aVal & MASK; 9565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int v = (aVal >>> 4) & MASK; 9575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root addBoth(c, j, T0, ti[u], T1, ti[v], bMax); 9585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (k > 0) 9605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root shiftUp(c, 0, cLen, 8); 9625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 9665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Finally the raw answer is collected, reduce it against the reduction coefficients 9675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 9685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return reduceResult(c, 0, cLen, m, ks); 9695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray modMultiply(LongArray other, int m, int[] ks) 9725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 9745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Find out the degree of each argument and handle the zero cases 9755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 9765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aDeg = degree(); 9775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aDeg == 0) 9785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this; 9805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bDeg = other.degree(); 9825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (bDeg == 0) 9835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return other; 9855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 9885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Swap if necessary so that A is the smaller argument 9895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 9905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray A = this, B = other; 9915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aDeg > bDeg) 9925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 9935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root A = other; B = this; 9945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int tmp = aDeg; aDeg = bDeg; bDeg = tmp; 9955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 9965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 9975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 9985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Establish the word lengths of the arguments and result 9995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aLen = (aDeg + 63) >>> 6; 10015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bLen = (bDeg + 63) >>> 6; 10025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int cLen = (aDeg + bDeg + 62) >>> 6; 10035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aLen == 1) 10055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long a = A.m_ints[0]; 10075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (a == 1L) 10085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return B; 10105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 10135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Fast path for small A, with performance dependent only on the number of set bits 10145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] c = new long[cLen]; 10165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root multiplyWord(a, B.m_ints, bLen, c, 0); 10175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 10195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Reduce the raw answer against the reduction coefficients 10205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return reduceResult(c, 0, cLen, m, ks); 10225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 10255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Determine if B will get bigger during shifting 10265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bMax = (bDeg + 7 + 63) >>> 6; 10285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 10305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Lookup table for the offset of each B in the tables 10315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int[] ti = new int[16]; 10335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 10355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Precompute table of all 4-bit products of B 10365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] T0 = new long[bMax << 4]; 10385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int tOff = bMax; 10395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ti[1] = tOff; 10405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root System.arraycopy(B.m_ints, 0, T0, tOff, bLen); 10415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 2; i < 16; ++i) 10425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ti[i] = (tOff += bMax); 10445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if ((i & 1) == 0) 10455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root shiftUp(T0, tOff >>> 1, T0, tOff, bMax, 1); 10475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 10495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root add(T0, bMax, T0, tOff - bMax, T0, tOff, bMax); 10515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 10555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Second table with all 4-bit products of B shifted 4 bits 10565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] T1 = new long[T0.length]; 10585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root shiftUp(T0, 0, T1, 0, T0.length, 4); 10595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// shiftUp(T0, bMax, T1, bMax, tOff, 4); 10605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] a = A.m_ints; 10625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] c = new long[cLen << 3]; 10635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int MASK = 0xF; 10655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 10675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Lopez-Dahab (Modified) algorithm 10685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int aPos = 0; aPos < aLen; ++aPos) 10715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long aVal = a[aPos]; 10735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int cOff = aPos; 10745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (;;) 10755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int u = (int)aVal & MASK; 10775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root aVal >>>= 4; 10785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int v = (int)aVal & MASK; 10795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root addBoth(c, cOff, T0, ti[u], T1, ti[v], bMax); 10805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if ((aVal >>>= 4) == 0L) 10815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root break; 10835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root cOff += cLen; 10855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int cOff = c.length; 10895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while ((cOff -= cLen) != 0) 10905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 10915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root addShiftedUp(c, cOff - cLen, c, cOff, cLen, 8); 10925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 10945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 10955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Finally the raw answer is collected, reduce it against the reduction coefficients 10965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 10975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return reduceResult(c, 0, cLen, m, ks); 10985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 10995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray modMultiplyAlt(LongArray other, int m, int[] ks) 11015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 11035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Find out the degree of each argument and handle the zero cases 11045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 11055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aDeg = degree(); 11065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aDeg == 0) 11075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this; 11095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 11105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bDeg = other.degree(); 11115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (bDeg == 0) 11125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return other; 11145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 11155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 11175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Swap if necessary so that A is the smaller argument 11185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 11195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray A = this, B = other; 11205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aDeg > bDeg) 11215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root A = other; B = this; 11235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int tmp = aDeg; aDeg = bDeg; bDeg = tmp; 11245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 11255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 11275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Establish the word lengths of the arguments and result 11285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 11295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aLen = (aDeg + 63) >>> 6; 11305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bLen = (bDeg + 63) >>> 6; 11315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int cLen = (aDeg + bDeg + 62) >>> 6; 11325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (aLen == 1) 11345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long a = A.m_ints[0]; 11365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (a == 1L) 11375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 11385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return B; 11395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 11405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 11425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Fast path for small A, with performance dependent only on the number of set bits 11435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 11445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] c = new long[cLen]; 11455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root multiplyWord(a, B.m_ints, bLen, c, 0); 11465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 11485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Reduce the raw answer against the reduction coefficients 11495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 11505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return reduceResult(c, 0, cLen, m, ks); 11515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 11525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // NOTE: This works, but is slower than width 4 processing 11545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (aLen == 2) 11555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 11565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// /* 11575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * Use common-multiplicand optimization to save ~1/4 of the adds 11585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// */ 11595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long a1 = A.m_ints[0], a2 = A.m_ints[1]; 11605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long aa = a1 & a2; a1 ^= aa; a2 ^= aa; 11615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 11625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long[] b = B.m_ints; 11635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long[] c = new long[cLen]; 11645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// multiplyWord(aa, b, bLen, c, 1); 11655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// add(c, 0, c, 1, cLen - 1); 11665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// multiplyWord(a1, b, bLen, c, 0); 11675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// multiplyWord(a2, b, bLen, c, 1); 11685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 11695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// /* 11705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// * Reduce the raw answer against the reduction coefficients 11715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// */ 11725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return reduceResult(c, 0, cLen, m, ks); 11735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 11745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 11765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Determine the parameters of the interleaved window algorithm: the 'width' in bits to 11775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * process together, the number of evaluation 'positions' implied by that width, and the 11785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * 'top' position at which the regular window algorithm stops. 11795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 11805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int width, positions, top, banks; 11815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // NOTE: width 4 is the fastest over the entire range of sizes used in current crypto 11835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// width = 1; positions = 64; top = 64; banks = 4; 11845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// width = 2; positions = 32; top = 64; banks = 4; 11855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// width = 3; positions = 21; top = 63; banks = 3; 11865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root width = 4; positions = 16; top = 64; banks = 8; 11875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// width = 5; positions = 13; top = 65; banks = 7; 11885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// width = 7; positions = 9; top = 63; banks = 9; 11895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// width = 8; positions = 8; top = 64; banks = 8; 11905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 11925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Determine if B will get bigger during shifting 11935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 11945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int shifts = top < 64 ? positions : positions - 1; 11955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bMax = (bDeg + shifts + 63) >>> 6; 11965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bTotal = bMax * banks, stride = width * banks; 11985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 11995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 12005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Create a single temporary buffer, with an offset table to find the positions of things in it 12015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 12025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int[] ci = new int[1 << width]; 12035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int cTotal = aLen; 12045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ci[0] = cTotal; 12065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root cTotal += bTotal; 12075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ci[1] = cTotal; 12085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 2; i < ci.length; ++i) 12095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root cTotal += cLen; 12115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ci[i] = cTotal; 12125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root cTotal += cLen; 12145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // NOTE: Provide a safe dump for "high zeroes" since we are adding 'bMax' and not 'bLen' 12165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ++cTotal; 12175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] c = new long[cTotal]; 12195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // Prepare A in interleaved form, according to the chosen width 12215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root interleave(A.m_ints, 0, c, 0, aLen, width); 12225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // Make a working copy of B, since we will be shifting it 12245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bOff = aLen; 12265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root System.arraycopy(B.m_ints, 0, c, bOff, bLen); 12275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int bank = 1; bank < banks; ++bank) 12285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root shiftUp(c, aLen, c, bOff += bMax, bMax, bank); 12305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 12345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * The main loop analyzes the interleaved windows in A, and for each non-zero window 12355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * a single word-array XOR is performed to a carefully selected slice of 'c'. The loop is 12365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * breadth-first, checking the lowest window in each word, then looping again for the 12375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * next higher window position. 12385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 12395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int MASK = (1 << width) - 1; 12405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int k = 0; 12425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (;;) 12435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int aPos = 0; 12455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root do 12465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long aVal = c[aPos] >>> k; 12485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int bank = 0, bOff = aLen; 12495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (;;) 12505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int index = (int)(aVal) & MASK; 12525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (index != 0) 12535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 12555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Add to a 'c' buffer based on the bit-pattern of 'index'. Since A is in 12565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * interleaved form, the bits represent the current B shifted by 0, 'positions', 12575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * 'positions' * 2, ..., 'positions' * ('width' - 1) 12585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 12595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root add(c, aPos + ci[index], c, bOff, bMax); 12605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (++bank == banks) 12625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root break; 12645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root bOff += bMax; 12665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root aVal >>>= width; 12675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (++aPos < aLen); 12705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if ((k += stride) >= top) 12725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (k >= 64) 12745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root break; 12765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 12795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Adjustment for window setups with top == 63, the final bit (if any) is processed 12805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * as the top-bit of a window 12815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 12825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root k = 64 - width; 12835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root MASK &= MASK << (top - k); 12845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 12875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * After each position has been checked for all words of A, B is shifted up 1 place 12885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 12895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root shiftUp(c, aLen, bTotal, banks); 12905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 12915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 12925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int ciPos = ci.length; 12935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--ciPos > 1) 12945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if ((ciPos & 1L) == 0L) 12965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 12975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 12985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * For even numbers, shift contents and add to the half-position 12995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 13005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root addShiftedUp(c, ci[ciPos >>> 1], c, ci[ciPos], cLen, positions); 13015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 13035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 13055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * For odd numbers, 'distribute' contents to the result and the next-lowest position 13065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 13075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root distribute(c, ci[ciPos], ci[ciPos - 1], ci[1], cLen); 13085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 13125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Finally the raw answer is collected, reduce it against the reduction coefficients 13135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 13145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return reduceResult(c, ci[1], cLen, m, ks); 13155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static LongArray reduceResult(long[] buf, int off, int len, int m, int[] ks) 13185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int rLen = reduceInPlace(buf, off, len, m, ks); 13205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new LongArray(buf, off, rLen); 13215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static void deInterleave(long[] x, int xOff, long[] z, int zOff, int count, int rounds) 13245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 13255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (int i = 0; i < count; ++i) 13265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 13275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// z[zOff + i] = deInterleave(x[zOff + i], rounds); 13285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 13295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 13305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 13315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static long deInterleave(long x, int rounds) 13325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 13335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while (--rounds >= 0) 13345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 13355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = deInterleave32(x & DEINTERLEAVE_MASK) | (deInterleave32((x >>> 1) & DEINTERLEAVE_MASK) << 32); 13365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 13375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return x; 13385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 13395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 13405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static long deInterleave32(long x) 13415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 13425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = (x | (x >>> 1)) & 0x3333333333333333L; 13435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = (x | (x >>> 2)) & 0x0F0F0F0F0F0F0F0FL; 13445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = (x | (x >>> 4)) & 0x00FF00FF00FF00FFL; 13455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = (x | (x >>> 8)) & 0x0000FFFF0000FFFFL; 13465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x = (x | (x >>> 16)) & 0x00000000FFFFFFFFL; 13475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return x; 13485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 13495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static int reduceInPlace(long[] buf, int off, int len, int m, int[] ks) 13515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int mLen = (m + 63) >>> 6; 13535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (len < mLen) 13545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return len; 13565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int numBits = Math.min(len << 6, (m << 1) - 1); // TODO use actual degree? 13595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int excessBits = (len << 6) - numBits; 13605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (excessBits >= 64) 13615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root --len; 13635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root excessBits -= 64; 13645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int kLen = ks.length, kMax = ks[kLen - 1], kNext = kLen > 1 ? ks[kLen - 2] : 0; 13675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int wordWiseLimit = Math.max(m, kMax + 64); 13685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int vectorableWords = (excessBits + Math.min(numBits - wordWiseLimit, m - kNext)) >> 6; 13695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (vectorableWords > 1) 13705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int vectorWiseWords = len - vectorableWords; 13725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root reduceVectorWise(buf, off, len, vectorWiseWords, m, ks); 13735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (len > vectorWiseWords) 13745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root buf[off + --len] = 0L; 13765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root numBits = vectorWiseWords << 6; 13785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (numBits > wordWiseLimit) 13815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root reduceWordWise(buf, off, len, wordWiseLimit, m, ks); 13835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root numBits = wordWiseLimit; 13845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (numBits > m) 13875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root reduceBitWise(buf, off, numBits, m, ks); 13895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return mLen; 13925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 13935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 13945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void reduceBitWise(long[] buf, int off, int bitlength, int m, int[] ks) 13955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--bitlength >= m) 13975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 13985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (testBit(buf, off, bitlength)) 13995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root reduceBit(buf, off, bitlength, m, ks); 14015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void reduceBit(long[] buf, int off, int bit, int m, int[] ks) 14065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root flipBit(buf, off, bit); 14085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int base = bit - m; 14095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int j = ks.length; 14105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--j >= 0) 14115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root flipBit(buf, off, ks[j] + base); 14135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root flipBit(buf, off, base); 14155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void reduceWordWise(long[] buf, int off, int len, int toBit, int m, int[] ks) 14185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int toPos = toBit >>> 6; 14205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--len > toPos) 14225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long word = buf[off + len]; 14245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (word != 0) 14255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root buf[off + len] = 0; 14275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root reduceWord(buf, off, (len << 6), word, m, ks); 14285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int partial = toBit & 0x3F; 14325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long word = buf[off + toPos] >>> partial; 14335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (word != 0) 14345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root buf[off + toPos] ^= word << partial; 14365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root reduceWord(buf, off, toBit, word, m, ks); 14375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void reduceWord(long[] buf, int off, int bit, long word, int m, int[] ks) 14415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int offset = bit - m; 14435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int j = ks.length; 14445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--j >= 0) 14455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root flipWord(buf, off, offset + ks[j], word); 14475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root flipWord(buf, off, offset, word); 14495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void reduceVectorWise(long[] buf, int off, int len, int words, int m, int[] ks) 14525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 14545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * NOTE: It's important we go from highest coefficient to lowest, because for the highest 14555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * one (only) we allow the ranges to partially overlap, and therefore any changes must take 14565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * effect for the subsequent lower coefficients. 14575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 14585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int baseBit = (words << 6) - m; 14595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int j = ks.length; 14605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--j >= 0) 14615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root flipVector(buf, off, buf, off + words, len - words, baseBit + ks[j]); 14635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root flipVector(buf, off, buf, off + words, len - words, baseBit); 14655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void flipVector(long[] x, int xOff, long[] y, int yOff, int yLen, int bits) 14685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root xOff += bits >>> 6; 14705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root bits &= 0x3F; 14715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (bits == 0) 14735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root add(x, xOff, y, yOff, yLen); 14755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 14775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long carry = addShiftedDown(x, xOff + 1, y, yOff, yLen, 64 - bits); 14795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x[xOff] ^= carry; 14805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray modSquare(int m, int[] ks) 14845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int len = getUsedLength(); 14865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (len == 0) 14875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this; 14895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 14905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int _2len = len << 1; 14925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long[] r = new long[_2len]; 14935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 14945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int pos = 0; 14955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (pos < _2len) 14965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 14975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long mi = m_ints[pos >>> 1]; 14985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root r[pos++] = interleave2_32to64((int)mi); 14995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root r[pos++] = interleave2_32to64((int)(mi >>> 32)); 15005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 15015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 15025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new LongArray(r, 0, reduceInPlace(r, 0, r.length, m, ks)); 15035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 15045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 15055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private LongArray modSquareN(int n, int m, int[] ks) 15065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 15075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int len = getUsedLength(); 15085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (len == 0) 15095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 15105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return this; 15115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 15125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 15135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int mLen = (m + 63) >>> 6; 15145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long[] r = new long[mLen << 1]; 15155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// System.arraycopy(m_ints, 0, r, 0, len); 15165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 15175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while (--n >= 0) 15185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 15195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// squareInPlace(r, len, m, ks); 15205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// len = reduceInPlace(r, 0, r.length, m, ks); 15215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 15225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 15235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return new LongArray(r, 0, len); 15245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 15255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 15265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static void squareInPlace(long[] x, int xLen, int m, int[] ks) 15275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 15285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int pos = xLen << 1; 15295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while (--xLen >= 0) 15305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 15315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long xVal = x[xLen]; 15325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x[--pos] = interleave2_32to64((int)(xVal >>> 32)); 15335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// x[--pos] = interleave2_32to64((int)xVal); 15345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 15355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 15365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 15375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void interleave(long[] x, int xOff, long[] z, int zOff, int count, int width) 15385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 15395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root switch (width) 15405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 15415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root case 3: 15425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root interleave3(x, xOff, z, zOff, count); 15435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root break; 15445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root case 5: 15455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root interleave5(x, xOff, z, zOff, count); 15465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root break; 15475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root case 7: 15485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root interleave7(x, xOff, z, zOff, count); 15495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root break; 15505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root default: 15515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root interleave2_n(x, xOff, z, zOff, count, bitLengths[width] - 1); 15525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root break; 15535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 15545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 15555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 15565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void interleave3(long[] x, int xOff, long[] z, int zOff, int count) 15575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 15585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 15595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 15605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root z[zOff + i] = interleave3(x[xOff + i]); 15615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 15625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 15635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 15645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long interleave3(long x) 15655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 15665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long z = x & (1L << 63); 15675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return z 15685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave3_21to63((int)x & 0x1FFFFF) 15695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave3_21to63((int)(x >>> 21) & 0x1FFFFF) << 1 15705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave3_21to63((int)(x >>> 42) & 0x1FFFFF) << 2; 15715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 15725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int zPos = 0, wPos = 0, xPos = 0; 15735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (;;) 15745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 15755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// z |= ((x >>> xPos) & 1L) << zPos; 15765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (++zPos == 63) 15775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 15785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// String sz2 = Long.toBinaryString(z); 15795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return z; 15805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 15815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if ((xPos += 21) >= 63) 15825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 15835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// xPos = ++wPos; 15845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 15855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 15865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 15875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 15885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long interleave3_21to63(int x) 15895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 15905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r00 = INTERLEAVE3_TABLE[x & 0x7F]; 15915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r21 = INTERLEAVE3_TABLE[(x >>> 7) & 0x7F]; 15925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r42 = INTERLEAVE3_TABLE[x >>> 14]; 15935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return (r42 & 0xFFFFFFFFL) << 42 | (r21 & 0xFFFFFFFFL) << 21 | (r00 & 0xFFFFFFFFL); 15945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 15955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 15965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void interleave5(long[] x, int xOff, long[] z, int zOff, int count) 15975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 15985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 15995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root z[zOff + i] = interleave5(x[xOff + i]); 16015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long interleave5(long x) 16055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return interleave3_13to65((int)x & 0x1FFF) 16075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave3_13to65((int)(x >>> 13) & 0x1FFF) << 1 16085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave3_13to65((int)(x >>> 26) & 0x1FFF) << 2 16095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave3_13to65((int)(x >>> 39) & 0x1FFF) << 3 16105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave3_13to65((int)(x >>> 52) & 0x1FFF) << 4; 16115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// long z = 0; 16135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int zPos = 0, wPos = 0, xPos = 0; 16145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (;;) 16155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 16165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// z |= ((x >>> xPos) & 1L) << zPos; 16175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (++zPos == 64) 16185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 16195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return z; 16205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 16215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if ((xPos += 13) >= 64) 16225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 16235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// xPos = ++wPos; 16245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 16255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 16265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long interleave3_13to65(int x) 16295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r00 = INTERLEAVE5_TABLE[x & 0x7F]; 16315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r35 = INTERLEAVE5_TABLE[x >>> 7]; 16325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return (r35 & 0xFFFFFFFFL) << 35 | (r00 & 0xFFFFFFFFL); 16335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void interleave7(long[] x, int xOff, long[] z, int zOff, int count) 16365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 16385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root z[zOff + i] = interleave7(x[xOff + i]); 16405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long interleave7(long x) 16445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long z = x & (1L << 63); 16465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return z 16475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | INTERLEAVE7_TABLE[(int)x & 0x1FF] 16485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | INTERLEAVE7_TABLE[(int)(x >>> 9) & 0x1FF] << 1 16495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | INTERLEAVE7_TABLE[(int)(x >>> 18) & 0x1FF] << 2 16505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | INTERLEAVE7_TABLE[(int)(x >>> 27) & 0x1FF] << 3 16515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | INTERLEAVE7_TABLE[(int)(x >>> 36) & 0x1FF] << 4 16525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | INTERLEAVE7_TABLE[(int)(x >>> 45) & 0x1FF] << 5 16535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | INTERLEAVE7_TABLE[(int)(x >>> 54) & 0x1FF] << 6; 16545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int zPos = 0, wPos = 0, xPos = 0; 16565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (;;) 16575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 16585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// z |= ((x >>> xPos) & 1L) << zPos; 16595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (++zPos == 63) 16605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 16615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return z; 16625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 16635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if ((xPos += 9) >= 63) 16645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 16655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// xPos = ++wPos; 16665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 16675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 16685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static void interleave2_n(long[] x, int xOff, long[] z, int zOff, int count, int rounds) 16715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < count; ++i) 16735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root z[zOff + i] = interleave2_n(x[xOff + i], rounds); 16755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long interleave2_n(long x, int rounds) 16795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (rounds > 1) 16815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root rounds -= 2; 16835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x = interleave4_16to64((int)x & 0xFFFF) 16845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave4_16to64((int)(x >>> 16) & 0xFFFF) << 1 16855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave4_16to64((int)(x >>> 32) & 0xFFFF) << 2 16865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root | interleave4_16to64((int)(x >>> 48) & 0xFFFF) << 3; 16875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (rounds > 0) 16895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root x = interleave2_32to64((int)x) | interleave2_32to64((int)(x >>> 32)) << 1; 16915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return x; 16935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 16945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 16955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long interleave4_16to64(int x) 16965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 16975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r00 = INTERLEAVE4_TABLE[x & 0xFF]; 16985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r32 = INTERLEAVE4_TABLE[x >>> 8]; 16995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return (r32 & 0xFFFFFFFFL) << 32 | (r00 & 0xFFFFFFFFL); 17005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 17015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 17025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root private static long interleave2_32to64(int x) 17035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 17045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r00 = INTERLEAVE2_TABLE[x & 0xFF] | INTERLEAVE2_TABLE[(x >>> 8) & 0xFF] << 16; 17055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int r32 = INTERLEAVE2_TABLE[(x >>> 16) & 0xFF] | INTERLEAVE2_TABLE[x >>> 24] << 16; 17065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return (r32 & 0xFFFFFFFFL) << 32 | (r00 & 0xFFFFFFFFL); 17075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 17085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 17095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static LongArray expItohTsujii2(LongArray B, int n, int m, int[] ks) 17105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray t1 = B, t3 = new LongArray(new long[]{ 1L }); 17125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int scale = 1; 17135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int numTerms = n; 17155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while (numTerms > 1) 17165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if ((numTerms & 1) != 0) 17185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t3 = t3.modMultiply(t1, m, ks); 17205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modSquareN(scale, m, ks); 17215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray t2 = t1.modSquareN(scale, m, ks); 17245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modMultiply(t2, m, ks); 17255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// numTerms >>>= 1; scale <<= 1; 17265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return t3.modMultiply(t1, m, ks); 17295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static LongArray expItohTsujii23(LongArray B, int n, int m, int[] ks) 17325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray t1 = B, t3 = new LongArray(new long[]{ 1L }); 17345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int scale = 1; 17355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int numTerms = n; 17375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while (numTerms > 1) 17385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// boolean m03 = numTerms % 3 == 0; 17405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// boolean m14 = !m03 && (numTerms & 1) != 0; 17415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (m14) 17435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t3 = t3.modMultiply(t1, m, ks); 17455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modSquareN(scale, m, ks); 17465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray t2 = t1.modSquareN(scale, m, ks); 17495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modMultiply(t2, m, ks); 17505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (m03) 17525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t2 = t2.modSquareN(scale, m, ks); 17545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modMultiply(t2, m, ks); 17555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// numTerms /= 3; scale *= 3; 17565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// else 17585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// numTerms >>>= 1; scale <<= 1; 17605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return t3.modMultiply(t1, m, ks); 17645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// private static LongArray expItohTsujii235(LongArray B, int n, int m, int[] ks) 17675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray t1 = B, t4 = new LongArray(new long[]{ 1L }); 17695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int scale = 1; 17705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// int numTerms = n; 17725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// while (numTerms > 1) 17735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (numTerms % 5 == 0) 17755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root//// t1 = expItohTsujii23(t1, 5, m, ks); 17775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray t3 = t1; 17795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modSquareN(scale, m, ks); 17805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray t2 = t1.modSquareN(scale, m, ks); 17825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modMultiply(t2, m, ks); 17835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t2 = t1.modSquareN(scale << 1, m, ks); 17845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modMultiply(t2, m, ks); 17855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modMultiply(t3, m, ks); 17875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// numTerms /= 5; scale *= 5; 17895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// continue; 17905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 17915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// boolean m03 = numTerms % 3 == 0; 17935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// boolean m14 = !m03 && (numTerms & 1) != 0; 17945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 17955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (m14) 17965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 17975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t4 = t4.modMultiply(t1, m, ks); 17985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modSquareN(scale, m, ks); 17995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 18005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 18015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray t2 = t1.modSquareN(scale, m, ks); 18025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modMultiply(t2, m, ks); 18035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 18045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// if (m03) 18055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 18065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t2 = t2.modSquareN(scale, m, ks); 18075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// t1 = t1.modMultiply(t2, m, ks); 18085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// numTerms /= 3; scale *= 3; 18095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 18105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// else 18115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 18125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// numTerms >>>= 1; scale <<= 1; 18135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 18145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 18155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 18165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return t4.modMultiply(t1, m, ks); 18175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 18185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public LongArray modInverse(int m, int[] ks) 18205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 18215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 18225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Fermat's Little Theorem 18235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 18245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray A = this; 18255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray B = A.modSquare(m, ks); 18265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray R0 = B, R1 = B; 18275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// for (int i = 2; i < m; ++i) 18285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 18295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// R1 = R1.modSquare(m, ks); 18305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// R0 = R0.modMultiply(R1, m, ks); 18315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 18325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// 18335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return R0; 18345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 18365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Itoh-Tsujii 18375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 18385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// LongArray B = modSquare(m, ks); 18395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// switch (m) 18405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// { 18415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// case 409: 18425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return expItohTsujii23(B, m - 1, m, ks); 18435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// case 571: 18445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return expItohTsujii235(B, m - 1, m, ks); 18455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// case 163: 18465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// case 233: 18475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// case 283: 18485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// default: 18495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// return expItohTsujii2(B, m - 1, m, ks); 18505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// } 18515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 18535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Inversion in F2m using the extended Euclidean algorithm 18545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * 18555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Input: A nonzero polynomial a(z) of degree at most m-1 18565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Output: a(z)^(-1) mod f(z) 18575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 18585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int uzDegree = degree(); 18595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (uzDegree == 1) 18605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 18615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return this; 18625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 18635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // u(z) := a(z) 18655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray uz = (LongArray)clone(); 18665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int t = (m + 63) >>> 6; 18685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // v(z) := f(z) 18705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray vz = new LongArray(t); 18715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root reduceBit(vz.m_ints, 0, m, m, ks); 18725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // g1(z) := 1, g2(z) := 0 18745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray g1z = new LongArray(t); 18755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root g1z.m_ints[0] = 1L; 18765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray g2z = new LongArray(t); 18775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int[] uvDeg = new int[]{ uzDegree, m + 1 }; 18795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray[] uv = new LongArray[]{ uz, vz }; 18805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int[] ggDeg = new int[]{ 1, 0 }; 18825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray[] gg = new LongArray[]{ g1z, g2z }; 18835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int b = 1; 18855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int duv1 = uvDeg[b]; 18865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int dgg1 = ggDeg[b]; 18875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int j = duv1 - uvDeg[1 - b]; 18885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 18895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (;;) 18905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 18915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (j < 0) 18925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 18935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root j = -j; 18945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root uvDeg[b] = duv1; 18955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ggDeg[b] = dgg1; 18965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root b = 1 - b; 18975db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root duv1 = uvDeg[b]; 18985db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root dgg1 = ggDeg[b]; 18995db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19005db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19015db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root uv[b].addShiftedByBitsSafe(uv[1 - b], uvDeg[1 - b], j); 19025db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19035db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int duv2 = uv[b].degreeFrom(duv1); 19045db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (duv2 == 0) 19055db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19065db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return gg[1 - b]; 19075db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19085db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19095db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int dgg2 = ggDeg[1 - b]; 19115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root gg[b].addShiftedByBitsSafe(gg[1 - b], dgg2, j); 19125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root dgg2 += j; 19135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (dgg2 > dgg1) 19155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root dgg1 = dgg2; 19175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else if (dgg2 == dgg1) 19195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root dgg1 = gg[b].degreeFrom(dgg1); 19215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root j += (duv2 - duv1); 19255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root duv1 = duv2; 19265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public boolean equals(Object o) 19305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (!(o instanceof LongArray)) 19325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return false; 19345db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root LongArray other = (LongArray) o; 19365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int usedLen = getUsedLength(); 19375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (other.getUsedLength() != usedLen) 19385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return false; 19405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < usedLen; i++) 19425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (m_ints[i] != other.m_ints[i]) 19445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19455db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return false; 19465db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return true; 19495db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19505db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public int hashCode() 19525db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int usedLen = getUsedLength(); 19545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int hash = 1; 19555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root for (int i = 0; i < usedLen; i++) 19565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root long mi = m_ints[i]; 19585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root hash *= 31; 19595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root hash ^= (int)mi; 19605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root hash *= 31; 19615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root hash ^= (int)(mi >>> 32); 19625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return hash; 19645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public Object clone() 19675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return new LongArray(Arrays.clone(m_ints)); 19695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root public String toString() 19725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i = getUsedLength(); 19745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (i == 0) 19755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return "0"; 19775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root StringBuffer sb = new StringBuffer(Long.toBinaryString(m_ints[--i])); 19805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (--i >= 0) 19815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root String s = Long.toBinaryString(m_ints[i]); 19835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // Add leading zeroes, except for highest significant word 19855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int len = s.length(); 19865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (len < 64) 19875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 19885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root sb.append(ZEROES.substring(len)); 19895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 19915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root sb.append(s); 19925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return sb.toString(); 19945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 19955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root}