1package org.bouncycastle.math.ec; 2 3import org.bouncycastle.util.Arrays; 4 5import java.math.BigInteger; 6 7class IntArray 8{ 9// private static int DEINTERLEAVE_MASK = 0x55555555; 10 11 /* 12 * This expands 8 bit indices into 16 bit contents, by inserting 0s between bits. 13 * In a binary field, this operation is the same as squaring an 8 bit number. 14 */ 15 private static final int[] INTERLEAVE_TABLE = new int[] { 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 16 0x0015, 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 17 0x0111, 0x0114, 0x0115, 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, 0x0400, 0x0401, 0x0404, 18 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, 0x0500, 19 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 20 0x0555, 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 21 0x1051, 0x1054, 0x1055, 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, 0x1140, 0x1141, 0x1144, 22 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, 0x1440, 23 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 24 0x1515, 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 25 0x4011, 0x4014, 0x4015, 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, 0x4100, 0x4101, 0x4104, 26 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, 0x4400, 27 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 28 0x4455, 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 29 0x4551, 0x4554, 0x4555, 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, 0x5040, 0x5041, 0x5044, 30 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, 0x5140, 31 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 32 0x5415, 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 33 0x5511, 0x5514, 0x5515, 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 }; 34 35 // For toString(); must have length 32 36 private static final String ZEROES = "00000000000000000000000000000000"; 37 38 private final static byte[] bitLengths = 39 { 40 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 41 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 42 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 43 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 44 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 45 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 46 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 47 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 48 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 49 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 50 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 51 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 52 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 53 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 54 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 55 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 56 }; 57 58 public static int getWordLength(int bits) 59 { 60 return (bits + 31) >>> 5; 61 } 62 63 // TODO make m fixed for the IntArray, and hence compute T once and for all 64 65 private int[] m_ints; 66 67 public IntArray(int intLen) 68 { 69 m_ints = new int[intLen]; 70 } 71 72 public IntArray(int[] ints) 73 { 74 m_ints = ints; 75 } 76 77 public IntArray(BigInteger bigInt) 78 { 79 if (bigInt == null || bigInt.signum() < 0) 80 { 81 throw new IllegalArgumentException("invalid F2m field value"); 82 } 83 84 if (bigInt.signum() == 0) 85 { 86 m_ints = new int[] { 0 }; 87 return; 88 } 89 90 byte[] barr = bigInt.toByteArray(); 91 int barrLen = barr.length; 92 int barrStart = 0; 93 if (barr[0] == 0) 94 { 95 // First byte is 0 to enforce highest (=sign) bit is zero. 96 // In this case ignore barr[0]. 97 barrLen--; 98 barrStart = 1; 99 } 100 int intLen = (barrLen + 3) / 4; 101 m_ints = new int[intLen]; 102 103 int iarrJ = intLen - 1; 104 int rem = barrLen % 4 + barrStart; 105 int temp = 0; 106 int barrI = barrStart; 107 if (barrStart < rem) 108 { 109 for (; barrI < rem; barrI++) 110 { 111 temp <<= 8; 112 int barrBarrI = barr[barrI] & 0xFF; 113 temp |= barrBarrI; 114 } 115 m_ints[iarrJ--] = temp; 116 } 117 118 for (; iarrJ >= 0; iarrJ--) 119 { 120 temp = 0; 121 for (int i = 0; i < 4; i++) 122 { 123 temp <<= 8; 124 int barrBarrI = barr[barrI++] & 0xFF; 125 temp |= barrBarrI; 126 } 127 m_ints[iarrJ] = temp; 128 } 129 } 130 131 public boolean isZero() 132 { 133 int[] a = m_ints; 134 for (int i = 0; i < a.length; ++i) 135 { 136 if (a[i] != 0) 137 { 138 return false; 139 } 140 } 141 return true; 142 } 143 144 public int getUsedLength() 145 { 146 return getUsedLengthFrom(m_ints.length); 147 } 148 149 public int getUsedLengthFrom(int from) 150 { 151 int[] a = m_ints; 152 from = Math.min(from, a.length); 153 154 if (from < 1) 155 { 156 return 0; 157 } 158 159 // Check if first element will act as sentinel 160 if (a[0] != 0) 161 { 162 while (a[--from] == 0) 163 { 164 } 165 return from + 1; 166 } 167 168 do 169 { 170 if (a[--from] != 0) 171 { 172 return from + 1; 173 } 174 } 175 while (from > 0); 176 177 return 0; 178 } 179 180 public int degree() 181 { 182 int i = m_ints.length, w; 183 do 184 { 185 if (i == 0) 186 { 187 return 0; 188 } 189 w = m_ints[--i]; 190 } 191 while (w == 0); 192 193 return (i << 5) + bitLength(w); 194 } 195 196 private static int bitLength(int w) 197 { 198 int t = w >>> 16; 199 if (t == 0) 200 { 201 t = w >>> 8; 202 return (t == 0) ? bitLengths[w] : 8 + bitLengths[t]; 203 } 204 205 int u = t >>> 8; 206 return (u == 0) ? 16 + bitLengths[t] : 24 + bitLengths[u]; 207 } 208 209 private int[] resizedInts(int newLen) 210 { 211 int[] newInts = new int[newLen]; 212 System.arraycopy(m_ints, 0, newInts, 0, Math.min(m_ints.length, newLen)); 213 return newInts; 214 } 215 216 public BigInteger toBigInteger() 217 { 218 int usedLen = getUsedLength(); 219 if (usedLen == 0) 220 { 221 return ECConstants.ZERO; 222 } 223 224 int highestInt = m_ints[usedLen - 1]; 225 byte[] temp = new byte[4]; 226 int barrI = 0; 227 boolean trailingZeroBytesDone = false; 228 for (int j = 3; j >= 0; j--) 229 { 230 byte thisByte = (byte) (highestInt >>> (8 * j)); 231 if (trailingZeroBytesDone || (thisByte != 0)) 232 { 233 trailingZeroBytesDone = true; 234 temp[barrI++] = thisByte; 235 } 236 } 237 238 int barrLen = 4 * (usedLen - 1) + barrI; 239 byte[] barr = new byte[barrLen]; 240 for (int j = 0; j < barrI; j++) 241 { 242 barr[j] = temp[j]; 243 } 244 // Highest value int is done now 245 246 for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) 247 { 248 for (int j = 3; j >= 0; j--) 249 { 250 barr[barrI++] = (byte) (m_ints[iarrJ] >>> (8 * j)); 251 } 252 } 253 return new BigInteger(1, barr); 254 } 255 256 private static int shiftLeft(int[] x, int count) 257 { 258 int prev = 0; 259 for (int i = 0; i < count; ++i) 260 { 261 int next = x[i]; 262 x[i] = (next << 1) | prev; 263 prev = next >>> 31; 264 } 265 return prev; 266 } 267 268 public void addOneShifted(int shift) 269 { 270 if (shift >= m_ints.length) 271 { 272 m_ints = resizedInts(shift + 1); 273 } 274 275 m_ints[shift] ^= 1; 276 } 277 278 private void addShiftedByBits(IntArray other, int bits) 279 { 280 int words = bits >>> 5; 281 int shift = bits & 0x1F; 282 283 if (shift == 0) 284 { 285 addShiftedByWords(other, words); 286 return; 287 } 288 289 int otherUsedLen = other.getUsedLength(); 290 if (otherUsedLen == 0) 291 { 292 return; 293 } 294 295 int minLen = otherUsedLen + words + 1; 296 if (minLen > m_ints.length) 297 { 298 m_ints = resizedInts(minLen); 299 } 300 301 int shiftInv = 32 - shift, prev = 0; 302 for (int i = 0; i < otherUsedLen; ++i) 303 { 304 int next = other.m_ints[i]; 305 m_ints[i + words] ^= (next << shift) | prev; 306 prev = next >>> shiftInv; 307 } 308 m_ints[otherUsedLen + words] ^= prev; 309 } 310 311 private static int addShiftedByBits(int[] x, int[] y, int count, int shift) 312 { 313 int shiftInv = 32 - shift, prev = 0; 314 for (int i = 0; i < count; ++i) 315 { 316 int next = y[i]; 317 x[i] ^= (next << shift) | prev; 318 prev = next >>> shiftInv; 319 } 320 return prev; 321 } 322 323 private static int addShiftedByBits(int[] x, int xOff, int[] y, int yOff, int count, int shift) 324 { 325 int shiftInv = 32 - shift, prev = 0; 326 for (int i = 0; i < count; ++i) 327 { 328 int next = y[yOff + i]; 329 x[xOff + i] ^= (next << shift) | prev; 330 prev = next >>> shiftInv; 331 } 332 return prev; 333 } 334 335 public void addShiftedByWords(IntArray other, int words) 336 { 337 int otherUsedLen = other.getUsedLength(); 338 if (otherUsedLen == 0) 339 { 340 return; 341 } 342 343 int minLen = otherUsedLen + words; 344 if (minLen > m_ints.length) 345 { 346 m_ints = resizedInts(minLen); 347 } 348 349 for (int i = 0; i < otherUsedLen; i++) 350 { 351 m_ints[words + i] ^= other.m_ints[i]; 352 } 353 } 354 355 private static void addShiftedByWords(int[] x, int xOff, int[] y, int count) 356 { 357 for (int i = 0; i < count; ++i) 358 { 359 x[xOff + i] ^= y[i]; 360 } 361 } 362 363 private static void add(int[] x, int[] y, int count) 364 { 365 for (int i = 0; i < count; ++i) 366 { 367 x[i] ^= y[i]; 368 } 369 } 370 371 private static void distribute(int[] x, int dst1, int dst2, int src, int count) 372 { 373 for (int i = 0; i < count; ++i) 374 { 375 int v = x[src + i]; 376 x[dst1 + i] ^= v; 377 x[dst2 + i] ^= v; 378 } 379 } 380 381 public int getLength() 382 { 383 return m_ints.length; 384 } 385 386 public void flipWord(int bit, int word) 387 { 388 int len = m_ints.length; 389 int n = bit >>> 5; 390 if (n < len) 391 { 392 int shift = bit & 0x1F; 393 if (shift == 0) 394 { 395 m_ints[n] ^= word; 396 } 397 else 398 { 399 m_ints[n] ^= word << shift; 400 if (++n < len) 401 { 402 m_ints[n] ^= word >>> (32 - shift); 403 } 404 } 405 } 406 } 407 408 public int getWord(int bit) 409 { 410 int len = m_ints.length; 411 int n = bit >>> 5; 412 if (n >= len) 413 { 414 return 0; 415 } 416 int shift = bit & 0x1F; 417 if (shift == 0) 418 { 419 return m_ints[n]; 420 } 421 int result = m_ints[n] >>> shift; 422 if (++n < len) 423 { 424 result |= m_ints[n] << (32 - shift); 425 } 426 return result; 427 } 428 429 public boolean testBitZero() 430 { 431 return m_ints.length > 0 && (m_ints[0] & 1) != 0; 432 } 433 434 public boolean testBit(int n) 435 { 436 // theInt = n / 32 437 int theInt = n >>> 5; 438 // theBit = n % 32 439 int theBit = n & 0x1F; 440 int tester = 1 << theBit; 441 return ((m_ints[theInt] & tester) != 0); 442 } 443 444 public void flipBit(int n) 445 { 446 // theInt = n / 32 447 int theInt = n >>> 5; 448 // theBit = n % 32 449 int theBit = n & 0x1F; 450 int flipper = 1 << theBit; 451 m_ints[theInt] ^= flipper; 452 } 453 454 public void setBit(int n) 455 { 456 // theInt = n / 32 457 int theInt = n >>> 5; 458 // theBit = n % 32 459 int theBit = n & 0x1F; 460 int setter = 1 << theBit; 461 m_ints[theInt] |= setter; 462 } 463 464 public void clearBit(int n) 465 { 466 // theInt = n / 32 467 int theInt = n >>> 5; 468 // theBit = n % 32 469 int theBit = n & 0x1F; 470 int setter = 1 << theBit; 471 m_ints[theInt] &= ~setter; 472 } 473 474 public IntArray multiply(IntArray other, int m) 475 { 476 int aLen = getUsedLength(); 477 if (aLen == 0) 478 { 479 return new IntArray(1); 480 } 481 482 int bLen = other.getUsedLength(); 483 if (bLen == 0) 484 { 485 return new IntArray(1); 486 } 487 488 IntArray A = this, B = other; 489 if (aLen > bLen) 490 { 491 A = other; B = this; 492 int tmp = aLen; aLen = bLen; bLen = tmp; 493 } 494 495 if (aLen == 1) 496 { 497 int a = A.m_ints[0]; 498 int[] b = B.m_ints; 499 int[] c = new int[aLen + bLen]; 500 if ((a & 1) != 0) 501 { 502 add(c, b, bLen); 503 } 504 int k = 1; 505 while ((a >>>= 1) != 0) 506 { 507 if ((a & 1) != 0) 508 { 509 addShiftedByBits(c, b, bLen, k); 510 } 511 ++k; 512 } 513 return new IntArray(c); 514 } 515 516 // TODO It'd be better to be able to tune the width directly (need support for interleaving arbitrary widths) 517 int complexity = aLen <= 8 ? 1 : 2; 518 519 int width = 1 << complexity; 520 int shifts = (32 >>> complexity); 521 522 int bExt = bLen; 523 if ((B.m_ints[bLen - 1] >>> (33 - shifts)) != 0) 524 { 525 ++bExt; 526 } 527 528 int cLen = bExt + aLen; 529 530 int[] c = new int[cLen << width]; 531 System.arraycopy(B.m_ints, 0, c, 0, bLen); 532 interleave(A.m_ints, 0, c, bExt, aLen, complexity); 533 534 int[] ci = new int[1 << width]; 535 for (int i = 1; i < ci.length; ++i) 536 { 537 ci[i] = ci[i - 1] + cLen; 538 } 539 540 int MASK = (1 << width) - 1; 541 542 int k = 0; 543 for (;;) 544 { 545 for (int aPos = 0; aPos < aLen; ++aPos) 546 { 547 int index = (c[bExt + aPos] >>> k) & MASK; 548 if (index != 0) 549 { 550 addShiftedByWords(c, aPos + ci[index], c, bExt); 551 } 552 } 553 554 if ((k += width) >= 32) 555 { 556 break; 557 } 558 559 shiftLeft(c, bExt); 560 } 561 562 int ciPos = ci.length, pow2 = ciPos >>> 1, offset = 32; 563 while (--ciPos > 1) 564 { 565 if (ciPos == pow2) 566 { 567 offset -= shifts; 568 addShiftedByBits(c, ci[1], c, ci[pow2], cLen, offset); 569 pow2 >>>= 1; 570 } 571 else 572 { 573 distribute(c, ci[pow2], ci[ciPos - pow2], ci[ciPos], cLen); 574 } 575 } 576 577 // TODO reduce in place to avoid extra copying 578 IntArray p = new IntArray(cLen); 579 System.arraycopy(c, ci[1], p.m_ints, 0, cLen); 580 return p; 581 } 582 583// private static void deInterleave(int[] x, int xOff, int[] z, int zOff, int count, int rounds) 584// { 585// for (int i = 0; i < count; ++i) 586// { 587// z[zOff + i] = deInterleave(x[zOff + i], rounds); 588// } 589// } 590// 591// private static int deInterleave(int x, int rounds) 592// { 593// while (--rounds >= 0) 594// { 595// x = deInterleave16(x & DEINTERLEAVE_MASK) | (deInterleave16((x >>> 1) & DEINTERLEAVE_MASK) << 16); 596// } 597// return x; 598// } 599// 600// private static int deInterleave16(int x) 601// { 602// x = (x | (x >>> 1)) & 0x33333333; 603// x = (x | (x >>> 2)) & 0x0F0F0F0F; 604// x = (x | (x >>> 4)) & 0x00FF00FF; 605// x = (x | (x >>> 8)) & 0x0000FFFF; 606// return x; 607// } 608 609 public void reduce(int m, int[] ks) 610 { 611 int len = getUsedLength(); 612 int mLen = (m + 31) >>> 5; 613 if (len < mLen) 614 { 615 return; 616 } 617 618 int _2m = m << 1; 619 int pos = Math.min(_2m - 2, (len << 5) - 1); 620 621 int kMax = ks[ks.length - 1]; 622 if (kMax < m - 31) 623 { 624 reduceWordWise(pos, m, ks); 625 } 626 else 627 { 628 reduceBitWise(pos, m, ks); 629 } 630 631 // Instead of flipping the high bits in the loop, explicitly clear any partial word above m bits 632 int partial = m & 0x1F; 633 if (partial != 0) 634 { 635 m_ints[mLen - 1] &= (1 << partial) - 1; 636 } 637 638 if (len > mLen) 639 { 640 m_ints = resizedInts(mLen); 641 } 642 } 643 644 private void reduceBitWise(int from, int m, int[] ks) 645 { 646 for (int i = from; i >= m; --i) 647 { 648 if (testBit(i)) 649 { 650// clearBit(i); 651 int bit = i - m; 652 flipBit(bit); 653 int j = ks.length; 654 while (--j >= 0) 655 { 656 flipBit(ks[j] + bit); 657 } 658 } 659 } 660 } 661 662 private void reduceWordWise(int from, int m, int[] ks) 663 { 664 int pos = m + ((from - m) & ~0x1F); 665 for (int i = pos; i >= m; i -= 32) 666 { 667 int word = getWord(i); 668 if (word != 0) 669 { 670// flipWord(i); 671 int bit = i - m; 672 flipWord(bit, word); 673 int j = ks.length; 674 while (--j >= 0) 675 { 676 flipWord(ks[j] + bit, word); 677 } 678 } 679 } 680 } 681 682 public IntArray square(int m) 683 { 684 int len = getUsedLength(); 685 if (len == 0) 686 { 687 return this; 688 } 689 690 int _2len = len << 1; 691 int[] r = new int[_2len]; 692 693 int pos = 0; 694 while (pos < _2len) 695 { 696 int mi = m_ints[pos >>> 1]; 697 r[pos++] = interleave16(mi & 0xFFFF); 698 r[pos++] = interleave16(mi >>> 16); 699 } 700 701 return new IntArray(r); 702 } 703 704 private static void interleave(int[] x, int xOff, int[] z, int zOff, int count, int rounds) 705 { 706 for (int i = 0; i < count; ++i) 707 { 708 z[zOff + i] = interleave(x[xOff + i], rounds); 709 } 710 } 711 712 private static int interleave(int x, int rounds) 713 { 714 while (--rounds >= 0) 715 { 716 x = interleave16(x & 0xFFFF) | (interleave16(x >>> 16) << 1); 717 } 718 return x; 719 } 720 721 private static int interleave16(int n) 722 { 723 return INTERLEAVE_TABLE[n & 0xFF] | INTERLEAVE_TABLE[n >>> 8] << 16; 724 } 725 726 public IntArray modInverse(int m, int[] ks) 727 { 728 // Inversion in F2m using the extended Euclidean algorithm 729 // Input: A nonzero polynomial a(z) of degree at most m-1 730 // Output: a(z)^(-1) mod f(z) 731 732 int uzDegree = degree(); 733 if (uzDegree == 1) 734 { 735 return this; 736 } 737 738 // u(z) := a(z) 739 IntArray uz = (IntArray)clone(); 740 741 int t = getWordLength(m); 742 743 // v(z) := f(z) 744 IntArray vz = new IntArray(t); 745 vz.setBit(m); 746 vz.setBit(0); 747 vz.setBit(ks[0]); 748 if (ks.length > 1) 749 { 750 vz.setBit(ks[1]); 751 vz.setBit(ks[2]); 752 } 753 754 // g1(z) := 1, g2(z) := 0 755 IntArray g1z = new IntArray(t); 756 g1z.setBit(0); 757 IntArray g2z = new IntArray(t); 758 759 while (uzDegree != 0) 760 { 761 // j := deg(u(z)) - deg(v(z)) 762 int j = uzDegree - vz.degree(); 763 764 // If j < 0 then: u(z) <-> v(z), g1(z) <-> g2(z), j := -j 765 if (j < 0) 766 { 767 final IntArray uzCopy = uz; 768 uz = vz; 769 vz = uzCopy; 770 771 final IntArray g1zCopy = g1z; 772 g1z = g2z; 773 g2z = g1zCopy; 774 775 j = -j; 776 } 777 778 // u(z) := u(z) + z^j * v(z) 779 // Note, that no reduction modulo f(z) is required, because 780 // deg(u(z) + z^j * v(z)) <= max(deg(u(z)), j + deg(v(z))) 781 // = max(deg(u(z)), deg(u(z)) - deg(v(z)) + deg(v(z)) 782 // = deg(u(z)) 783 // uz = uz.xor(vz.shiftLeft(j)); 784 uz.addShiftedByBits(vz, j); 785 uzDegree = uz.degree(); 786 787 // g1(z) := g1(z) + z^j * g2(z) 788// g1z = g1z.xor(g2z.shiftLeft(j)); 789 if (uzDegree != 0) 790 { 791 g1z.addShiftedByBits(g2z, j); 792 } 793 } 794 return g2z; 795 } 796 797 public boolean equals(Object o) 798 { 799 if (!(o instanceof IntArray)) 800 { 801 return false; 802 } 803 IntArray other = (IntArray) o; 804 int usedLen = getUsedLength(); 805 if (other.getUsedLength() != usedLen) 806 { 807 return false; 808 } 809 for (int i = 0; i < usedLen; i++) 810 { 811 if (m_ints[i] != other.m_ints[i]) 812 { 813 return false; 814 } 815 } 816 return true; 817 } 818 819 public int hashCode() 820 { 821 int usedLen = getUsedLength(); 822 int hash = 1; 823 for (int i = 0; i < usedLen; i++) 824 { 825 hash *= 31; 826 hash ^= m_ints[i]; 827 } 828 return hash; 829 } 830 831 public Object clone() 832 { 833 return new IntArray(Arrays.clone(m_ints)); 834 } 835 836 public String toString() 837 { 838 int i = getUsedLength(); 839 if (i == 0) 840 { 841 return "0"; 842 } 843 844 StringBuffer sb = new StringBuffer(Integer.toBinaryString(m_ints[--i])); 845 while (--i >= 0) 846 { 847 String s = Integer.toBinaryString(m_ints[i]); 848 849 // Add leading zeroes, except for highest significant word 850 int len = s.length(); 851 if (len < 32) 852 { 853 sb.append(ZEROES.substring(len)); 854 } 855 856 sb.append(s); 857 } 858 return sb.toString(); 859 } 860}