1 package org.bouncycastle.math.raw; 2 3 import java.math.BigInteger; 4 5 import org.bouncycastle.util.Pack; 6 7 public abstract class Nat224 8 { 9 private static final long M = 0xFFFFFFFFL; 10 11 public static int add(int[] x, int[] y, int[] z) 12 { 13 long c = 0; 14 c += (x[0] & M) + (y[0] & M); 15 z[0] = (int)c; 16 c >>>= 32; 17 c += (x[1] & M) + (y[1] & M); 18 z[1] = (int)c; 19 c >>>= 32; 20 c += (x[2] & M) + (y[2] & M); 21 z[2] = (int)c; 22 c >>>= 32; 23 c += (x[3] & M) + (y[3] & M); 24 z[3] = (int)c; 25 c >>>= 32; 26 c += (x[4] & M) + (y[4] & M); 27 z[4] = (int)c; 28 c >>>= 32; 29 c += (x[5] & M) + (y[5] & M); 30 z[5] = (int)c; 31 c >>>= 32; 32 c += (x[6] & M) + (y[6] & M); 33 z[6] = (int)c; 34 c >>>= 32; 35 return (int)c; 36 } 37 38 public static int add(int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 39 { 40 long c = 0; 41 c += (x[xOff + 0] & M) + (y[yOff + 0] & M); 42 z[zOff + 0] = (int)c; 43 c >>>= 32; 44 c += (x[xOff + 1] & M) + (y[yOff + 1] & M); 45 z[zOff + 1] = (int)c; 46 c >>>= 32; 47 c += (x[xOff + 2] & M) + (y[yOff + 2] & M); 48 z[zOff + 2] = (int)c; 49 c >>>= 32; 50 c += (x[xOff + 3] & M) + (y[yOff + 3] & M); 51 z[zOff + 3] = (int)c; 52 c >>>= 32; 53 c += (x[xOff + 4] & M) + (y[yOff + 4] & M); 54 z[zOff + 4] = (int)c; 55 c >>>= 32; 56 c += (x[xOff + 5] & M) + (y[yOff + 5] & M); 57 z[zOff + 5] = (int)c; 58 c >>>= 32; 59 c += (x[xOff + 6] & M) + (y[yOff + 6] & M); 60 z[zOff + 6] = (int)c; 61 c >>>= 32; 62 return (int)c; 63 } 64 65 public static int addBothTo(int[] x, int[] y, int[] z) 66 { 67 long c = 0; 68 c += (x[0] & M) + (y[0] & M) + (z[0] & M); 69 z[0] = (int)c; 70 c >>>= 32; 71 c += (x[1] & M) + (y[1] & M) + (z[1] & M); 72 z[1] = (int)c; 73 c >>>= 32; 74 c += (x[2] & M) + (y[2] & M) + (z[2] & M); 75 z[2] = (int)c; 76 c >>>= 32; 77 c += (x[3] & M) + (y[3] & M) + (z[3] & M); 78 z[3] = (int)c; 79 c >>>= 32; 80 c += (x[4] & M) + (y[4] & M) + (z[4] & M); 81 z[4] = (int)c; 82 c >>>= 32; 83 c += (x[5] & M) + (y[5] & M) + (z[5] & M); 84 z[5] = (int)c; 85 c >>>= 32; 86 c += (x[6] & M) + (y[6] & M) + (z[6] & M); 87 z[6] = (int)c; 88 c >>>= 32; 89 return (int)c; 90 } 91 92 public static int addBothTo(int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 93 { 94 long c = 0; 95 c += (x[xOff + 0] & M) + (y[yOff + 0] & M) + (z[zOff + 0] & M); 96 z[zOff + 0] = (int)c; 97 c >>>= 32; 98 c += (x[xOff + 1] & M) + (y[yOff + 1] & M) + (z[zOff + 1] & M); 99 z[zOff + 1] = (int)c; 100 c >>>= 32; 101 c += (x[xOff + 2] & M) + (y[yOff + 2] & M) + (z[zOff + 2] & M); 102 z[zOff + 2] = (int)c; 103 c >>>= 32; 104 c += (x[xOff + 3] & M) + (y[yOff + 3] & M) + (z[zOff + 3] & M); 105 z[zOff + 3] = (int)c; 106 c >>>= 32; 107 c += (x[xOff + 4] & M) + (y[yOff + 4] & M) + (z[zOff + 4] & M); 108 z[zOff + 4] = (int)c; 109 c >>>= 32; 110 c += (x[xOff + 5] & M) + (y[yOff + 5] & M) + (z[zOff + 5] & M); 111 z[zOff + 5] = (int)c; 112 c >>>= 32; 113 c += (x[xOff + 6] & M) + (y[yOff + 6] & M) + (z[zOff + 6] & M); 114 z[zOff + 6] = (int)c; 115 c >>>= 32; 116 return (int)c; 117 } 118 119 public static int addTo(int[] x, int[] z) 120 { 121 long c = 0; 122 c += (x[0] & M) + (z[0] & M); 123 z[0] = (int)c; 124 c >>>= 32; 125 c += (x[1] & M) + (z[1] & M); 126 z[1] = (int)c; 127 c >>>= 32; 128 c += (x[2] & M) + (z[2] & M); 129 z[2] = (int)c; 130 c >>>= 32; 131 c += (x[3] & M) + (z[3] & M); 132 z[3] = (int)c; 133 c >>>= 32; 134 c += (x[4] & M) + (z[4] & M); 135 z[4] = (int)c; 136 c >>>= 32; 137 c += (x[5] & M) + (z[5] & M); 138 z[5] = (int)c; 139 c >>>= 32; 140 c += (x[6] & M) + (z[6] & M); 141 z[6] = (int)c; 142 c >>>= 32; 143 return (int)c; 144 } 145 146 public static int addTo(int[] x, int xOff, int[] z, int zOff, int cIn) 147 { 148 long c = cIn & M; 149 c += (x[xOff + 0] & M) + (z[zOff + 0] & M); 150 z[zOff + 0] = (int)c; 151 c >>>= 32; 152 c += (x[xOff + 1] & M) + (z[zOff + 1] & M); 153 z[zOff + 1] = (int)c; 154 c >>>= 32; 155 c += (x[xOff + 2] & M) + (z[zOff + 2] & M); 156 z[zOff + 2] = (int)c; 157 c >>>= 32; 158 c += (x[xOff + 3] & M) + (z[zOff + 3] & M); 159 z[zOff + 3] = (int)c; 160 c >>>= 32; 161 c += (x[xOff + 4] & M) + (z[zOff + 4] & M); 162 z[zOff + 4] = (int)c; 163 c >>>= 32; 164 c += (x[xOff + 5] & M) + (z[zOff + 5] & M); 165 z[zOff + 5] = (int)c; 166 c >>>= 32; 167 c += (x[xOff + 6] & M) + (z[zOff + 6] & M); 168 z[zOff + 6] = (int)c; 169 c >>>= 32; 170 return (int)c; 171 } 172 173 public static int addToEachOther(int[] u, int uOff, int[] v, int vOff) 174 { 175 long c = 0; 176 c += (u[uOff + 0] & M) + (v[vOff + 0] & M); 177 u[uOff + 0] = (int)c; 178 v[vOff + 0] = (int)c; 179 c >>>= 32; 180 c += (u[uOff + 1] & M) + (v[vOff + 1] & M); 181 u[uOff + 1] = (int)c; 182 v[vOff + 1] = (int)c; 183 c >>>= 32; 184 c += (u[uOff + 2] & M) + (v[vOff + 2] & M); 185 u[uOff + 2] = (int)c; 186 v[vOff + 2] = (int)c; 187 c >>>= 32; 188 c += (u[uOff + 3] & M) + (v[vOff + 3] & M); 189 u[uOff + 3] = (int)c; 190 v[vOff + 3] = (int)c; 191 c >>>= 32; 192 c += (u[uOff + 4] & M) + (v[vOff + 4] & M); 193 u[uOff + 4] = (int)c; 194 v[vOff + 4] = (int)c; 195 c >>>= 32; 196 c += (u[uOff + 5] & M) + (v[vOff + 5] & M); 197 u[uOff + 5] = (int)c; 198 v[vOff + 5] = (int)c; 199 c >>>= 32; 200 c += (u[uOff + 6] & M) + (v[vOff + 6] & M); 201 u[uOff + 6] = (int)c; 202 v[vOff + 6] = (int)c; 203 c >>>= 32; 204 return (int)c; 205 } 206 207 public static void copy(int[] x, int[] z) 208 { 209 z[0] = x[0]; 210 z[1] = x[1]; 211 z[2] = x[2]; 212 z[3] = x[3]; 213 z[4] = x[4]; 214 z[5] = x[5]; 215 z[6] = x[6]; 216 } 217 218 public static int[] create() 219 { 220 return new int[7]; 221 } 222 223 public static int[] createExt() 224 { 225 return new int[14]; 226 } 227 228 public static boolean diff(int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 229 { 230 boolean pos = gte(x, xOff, y, yOff); 231 if (pos) 232 { 233 sub(x, xOff, y, yOff, z, zOff); 234 } 235 else 236 { 237 sub(y, yOff, x, xOff, z, zOff); 238 } 239 return pos; 240 } 241 242 public static boolean eq(int[] x, int[] y) 243 { 244 for (int i = 6; i >= 0; --i) 245 { 246 if (x[i] != y[i]) 247 { 248 return false; 249 } 250 } 251 return true; 252 } 253 254 public static int[] fromBigInteger(BigInteger x) 255 { 256 if (x.signum() < 0 || x.bitLength() > 224) 257 { 258 throw new IllegalArgumentException(); 259 } 260 261 int[] z = create(); 262 int i = 0; 263 while (x.signum() != 0) 264 { 265 z[i++] = x.intValue(); 266 x = x.shiftRight(32); 267 } 268 return z; 269 } 270 271 public static int getBit(int[] x, int bit) 272 { 273 if (bit == 0) 274 { 275 return x[0] & 1; 276 } 277 int w = bit >> 5; 278 if (w < 0 || w >= 7) 279 { 280 return 0; 281 } 282 int b = bit & 31; 283 return (x[w] >>> b) & 1; 284 } 285 286 public static boolean gte(int[] x, int[] y) 287 { 288 for (int i = 6; i >= 0; --i) 289 { 290 int x_i = x[i] ^ Integer.MIN_VALUE; 291 int y_i = y[i] ^ Integer.MIN_VALUE; 292 if (x_i < y_i) 293 return false; 294 if (x_i > y_i) 295 return true; 296 } 297 return true; 298 } 299 300 public static boolean gte(int[] x, int xOff, int[] y, int yOff) 301 { 302 for (int i = 6; i >= 0; --i) 303 { 304 int x_i = x[xOff + i] ^ Integer.MIN_VALUE; 305 int y_i = y[yOff + i] ^ Integer.MIN_VALUE; 306 if (x_i < y_i) 307 return false; 308 if (x_i > y_i) 309 return true; 310 } 311 return true; 312 } 313 314 public static boolean isOne(int[] x) 315 { 316 if (x[0] != 1) 317 { 318 return false; 319 } 320 for (int i = 1; i < 7; ++i) 321 { 322 if (x[i] != 0) 323 { 324 return false; 325 } 326 } 327 return true; 328 } 329 330 public static boolean isZero(int[] x) 331 { 332 for (int i = 0; i < 7; ++i) 333 { 334 if (x[i] != 0) 335 { 336 return false; 337 } 338 } 339 return true; 340 } 341 342 public static void mul(int[] x, int[] y, int[] zz) 343 { 344 long y_0 = y[0] & M; 345 long y_1 = y[1] & M; 346 long y_2 = y[2] & M; 347 long y_3 = y[3] & M; 348 long y_4 = y[4] & M; 349 long y_5 = y[5] & M; 350 long y_6 = y[6] & M; 351 352 { 353 long c = 0, x_0 = x[0] & M; 354 c += x_0 * y_0; 355 zz[0] = (int)c; 356 c >>>= 32; 357 c += x_0 * y_1; 358 zz[1] = (int)c; 359 c >>>= 32; 360 c += x_0 * y_2; 361 zz[2] = (int)c; 362 c >>>= 32; 363 c += x_0 * y_3; 364 zz[3] = (int)c; 365 c >>>= 32; 366 c += x_0 * y_4; 367 zz[4] = (int)c; 368 c >>>= 32; 369 c += x_0 * y_5; 370 zz[5] = (int)c; 371 c >>>= 32; 372 c += x_0 * y_6; 373 zz[6] = (int)c; 374 c >>>= 32; 375 zz[7] = (int)c; 376 } 377 378 for (int i = 1; i < 7; ++i) 379 { 380 long c = 0, x_i = x[i] & M; 381 c += x_i * y_0 + (zz[i + 0] & M); 382 zz[i + 0] = (int)c; 383 c >>>= 32; 384 c += x_i * y_1 + (zz[i + 1] & M); 385 zz[i + 1] = (int)c; 386 c >>>= 32; 387 c += x_i * y_2 + (zz[i + 2] & M); 388 zz[i + 2] = (int)c; 389 c >>>= 32; 390 c += x_i * y_3 + (zz[i + 3] & M); 391 zz[i + 3] = (int)c; 392 c >>>= 32; 393 c += x_i * y_4 + (zz[i + 4] & M); 394 zz[i + 4] = (int)c; 395 c >>>= 32; 396 c += x_i * y_5 + (zz[i + 5] & M); 397 zz[i + 5] = (int)c; 398 c >>>= 32; 399 c += x_i * y_6 + (zz[i + 6] & M); 400 zz[i + 6] = (int)c; 401 c >>>= 32; 402 zz[i + 7] = (int)c; 403 } 404 } 405 406 public static void mul(int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff) 407 { 408 long y_0 = y[yOff + 0] & M; 409 long y_1 = y[yOff + 1] & M; 410 long y_2 = y[yOff + 2] & M; 411 long y_3 = y[yOff + 3] & M; 412 long y_4 = y[yOff + 4] & M; 413 long y_5 = y[yOff + 5] & M; 414 long y_6 = y[yOff + 6] & M; 415 416 { 417 long c = 0, x_0 = x[xOff + 0] & M; 418 c += x_0 * y_0; 419 zz[zzOff + 0] = (int)c; 420 c >>>= 32; 421 c += x_0 * y_1; 422 zz[zzOff + 1] = (int)c; 423 c >>>= 32; 424 c += x_0 * y_2; 425 zz[zzOff + 2] = (int)c; 426 c >>>= 32; 427 c += x_0 * y_3; 428 zz[zzOff + 3] = (int)c; 429 c >>>= 32; 430 c += x_0 * y_4; 431 zz[zzOff + 4] = (int)c; 432 c >>>= 32; 433 c += x_0 * y_5; 434 zz[zzOff + 5] = (int)c; 435 c >>>= 32; 436 c += x_0 * y_6; 437 zz[zzOff + 6] = (int)c; 438 c >>>= 32; 439 zz[zzOff + 7] = (int)c; 440 } 441 442 for (int i = 1; i < 7; ++i) 443 { 444 ++zzOff; 445 long c = 0, x_i = x[xOff + i] & M; 446 c += x_i * y_0 + (zz[zzOff + 0] & M); 447 zz[zzOff + 0] = (int)c; 448 c >>>= 32; 449 c += x_i * y_1 + (zz[zzOff + 1] & M); 450 zz[zzOff + 1] = (int)c; 451 c >>>= 32; 452 c += x_i * y_2 + (zz[zzOff + 2] & M); 453 zz[zzOff + 2] = (int)c; 454 c >>>= 32; 455 c += x_i * y_3 + (zz[zzOff + 3] & M); 456 zz[zzOff + 3] = (int)c; 457 c >>>= 32; 458 c += x_i * y_4 + (zz[zzOff + 4] & M); 459 zz[zzOff + 4] = (int)c; 460 c >>>= 32; 461 c += x_i * y_5 + (zz[zzOff + 5] & M); 462 zz[zzOff + 5] = (int)c; 463 c >>>= 32; 464 c += x_i * y_6 + (zz[zzOff + 6] & M); 465 zz[zzOff + 6] = (int)c; 466 c >>>= 32; 467 zz[zzOff + 7] = (int)c; 468 } 469 } 470 471 public static int mulAddTo(int[] x, int[] y, int[] zz) 472 { 473 long y_0 = y[0] & M; 474 long y_1 = y[1] & M; 475 long y_2 = y[2] & M; 476 long y_3 = y[3] & M; 477 long y_4 = y[4] & M; 478 long y_5 = y[5] & M; 479 long y_6 = y[6] & M; 480 481 long zc = 0; 482 for (int i = 0; i < 7; ++i) 483 { 484 long c = 0, x_i = x[i] & M; 485 c += x_i * y_0 + (zz[i + 0] & M); 486 zz[i + 0] = (int)c; 487 c >>>= 32; 488 c += x_i * y_1 + (zz[i + 1] & M); 489 zz[i + 1] = (int)c; 490 c >>>= 32; 491 c += x_i * y_2 + (zz[i + 2] & M); 492 zz[i + 2] = (int)c; 493 c >>>= 32; 494 c += x_i * y_3 + (zz[i + 3] & M); 495 zz[i + 3] = (int)c; 496 c >>>= 32; 497 c += x_i * y_4 + (zz[i + 4] & M); 498 zz[i + 4] = (int)c; 499 c >>>= 32; 500 c += x_i * y_5 + (zz[i + 5] & M); 501 zz[i + 5] = (int)c; 502 c >>>= 32; 503 c += x_i * y_6 + (zz[i + 6] & M); 504 zz[i + 6] = (int)c; 505 c >>>= 32; 506 c += zc + (zz[i + 7] & M); 507 zz[i + 7] = (int)c; 508 zc = c >>> 32; 509 } 510 return (int)zc; 511 } 512 513 public static int mulAddTo(int[] x, int xOff, int[] y, int yOff, int[] zz, int zzOff) 514 { 515 long y_0 = y[yOff + 0] & M; 516 long y_1 = y[yOff + 1] & M; 517 long y_2 = y[yOff + 2] & M; 518 long y_3 = y[yOff + 3] & M; 519 long y_4 = y[yOff + 4] & M; 520 long y_5 = y[yOff + 5] & M; 521 long y_6 = y[yOff + 6] & M; 522 523 long zc = 0; 524 for (int i = 0; i < 7; ++i) 525 { 526 long c = 0, x_i = x[xOff + i] & M; 527 c += x_i * y_0 + (zz[zzOff + 0] & M); 528 zz[zzOff + 0] = (int)c; 529 c >>>= 32; 530 c += x_i * y_1 + (zz[zzOff + 1] & M); 531 zz[zzOff + 1] = (int)c; 532 c >>>= 32; 533 c += x_i * y_2 + (zz[zzOff + 2] & M); 534 zz[zzOff + 2] = (int)c; 535 c >>>= 32; 536 c += x_i * y_3 + (zz[zzOff + 3] & M); 537 zz[zzOff + 3] = (int)c; 538 c >>>= 32; 539 c += x_i * y_4 + (zz[zzOff + 4] & M); 540 zz[zzOff + 4] = (int)c; 541 c >>>= 32; 542 c += x_i * y_5 + (zz[zzOff + 5] & M); 543 zz[zzOff + 5] = (int)c; 544 c >>>= 32; 545 c += x_i * y_6 + (zz[zzOff + 6] & M); 546 zz[zzOff + 6] = (int)c; 547 c >>>= 32; 548 c += zc + (zz[zzOff + 7] & M); 549 zz[zzOff + 7] = (int)c; 550 zc = c >>> 32; 551 ++zzOff; 552 } 553 return (int)zc; 554 } 555 556 public static long mul33Add(int w, int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 557 { 558 // assert w >>> 31 == 0; 559 560 long c = 0, wVal = w & M; 561 long x0 = x[xOff + 0] & M; 562 c += wVal * x0 + (y[yOff + 0] & M); 563 z[zOff + 0] = (int)c; 564 c >>>= 32; 565 long x1 = x[xOff + 1] & M; 566 c += wVal * x1 + x0 + (y[yOff + 1] & M); 567 z[zOff + 1] = (int)c; 568 c >>>= 32; 569 long x2 = x[xOff + 2] & M; 570 c += wVal * x2 + x1 + (y[yOff + 2] & M); 571 z[zOff + 2] = (int)c; 572 c >>>= 32; 573 long x3 = x[xOff + 3] & M; 574 c += wVal * x3 + x2 + (y[yOff + 3] & M); 575 z[zOff + 3] = (int)c; 576 c >>>= 32; 577 long x4 = x[xOff + 4] & M; 578 c += wVal * x4 + x3 + (y[yOff + 4] & M); 579 z[zOff + 4] = (int)c; 580 c >>>= 32; 581 long x5 = x[xOff + 5] & M; 582 c += wVal * x5 + x4 + (y[yOff + 5] & M); 583 z[zOff + 5] = (int)c; 584 c >>>= 32; 585 long x6 = x[xOff + 6] & M; 586 c += wVal * x6 + x5 + (y[yOff + 6] & M); 587 z[zOff + 6] = (int)c; 588 c >>>= 32; 589 c += x6; 590 return c; 591 } 592 593 public static int mulByWord(int x, int[] z) 594 { 595 long c = 0, xVal = x & M; 596 c += xVal * (z[0] & M); 597 z[0] = (int)c; 598 c >>>= 32; 599 c += xVal * (z[1] & M); 600 z[1] = (int)c; 601 c >>>= 32; 602 c += xVal * (z[2] & M); 603 z[2] = (int)c; 604 c >>>= 32; 605 c += xVal * (z[3] & M); 606 z[3] = (int)c; 607 c >>>= 32; 608 c += xVal * (z[4] & M); 609 z[4] = (int)c; 610 c >>>= 32; 611 c += xVal * (z[5] & M); 612 z[5] = (int)c; 613 c >>>= 32; 614 c += xVal * (z[6] & M); 615 z[6] = (int)c; 616 c >>>= 32; 617 return (int)c; 618 } 619 620 public static int mulByWordAddTo(int x, int[] y, int[] z) 621 { 622 long c = 0, xVal = x & M; 623 c += xVal * (z[0] & M) + (y[0] & M); 624 z[0] = (int)c; 625 c >>>= 32; 626 c += xVal * (z[1] & M) + (y[1] & M); 627 z[1] = (int)c; 628 c >>>= 32; 629 c += xVal * (z[2] & M) + (y[2] & M); 630 z[2] = (int)c; 631 c >>>= 32; 632 c += xVal * (z[3] & M) + (y[3] & M); 633 z[3] = (int)c; 634 c >>>= 32; 635 c += xVal * (z[4] & M) + (y[4] & M); 636 z[4] = (int)c; 637 c >>>= 32; 638 c += xVal * (z[5] & M) + (y[5] & M); 639 z[5] = (int)c; 640 c >>>= 32; 641 c += xVal * (z[6] & M) + (y[6] & M); 642 z[6] = (int)c; 643 c >>>= 32; 644 return (int)c; 645 } 646 647 public static int mulWordAddTo(int x, int[] y, int yOff, int[] z, int zOff) 648 { 649 long c = 0, xVal = x & M; 650 c += xVal * (y[yOff + 0] & M) + (z[zOff + 0] & M); 651 z[zOff + 0] = (int)c; 652 c >>>= 32; 653 c += xVal * (y[yOff + 1] & M) + (z[zOff + 1] & M); 654 z[zOff + 1] = (int)c; 655 c >>>= 32; 656 c += xVal * (y[yOff + 2] & M) + (z[zOff + 2] & M); 657 z[zOff + 2] = (int)c; 658 c >>>= 32; 659 c += xVal * (y[yOff + 3] & M) + (z[zOff + 3] & M); 660 z[zOff + 3] = (int)c; 661 c >>>= 32; 662 c += xVal * (y[yOff + 4] & M) + (z[zOff + 4] & M); 663 z[zOff + 4] = (int)c; 664 c >>>= 32; 665 c += xVal * (y[yOff + 5] & M) + (z[zOff + 5] & M); 666 z[zOff + 5] = (int)c; 667 c >>>= 32; 668 c += xVal * (y[yOff + 6] & M) + (z[zOff + 6] & M); 669 z[zOff + 6] = (int)c; 670 c >>>= 32; 671 return (int)c; 672 } 673 674 public static int mul33DWordAdd(int x, long y, int[] z, int zOff) 675 { 676 // assert x >>> 31 == 0; 677 // assert zOff <= 3; 678 679 long c = 0, xVal = x & M; 680 long y00 = y & M; 681 c += xVal * y00 + (z[zOff + 0] & M); 682 z[zOff + 0] = (int)c; 683 c >>>= 32; 684 long y01 = y >>> 32; 685 c += xVal * y01 + y00 + (z[zOff + 1] & M); 686 z[zOff + 1] = (int)c; 687 c >>>= 32; 688 c += y01 + (z[zOff + 2] & M); 689 z[zOff + 2] = (int)c; 690 c >>>= 32; 691 c += (z[zOff + 3] & M); 692 z[zOff + 3] = (int)c; 693 c >>>= 32; 694 return c == 0 ? 0 : Nat.incAt(7, z, zOff, 4); 695 } 696 697 public static int mul33WordAdd(int x, int y, int[] z, int zOff) 698 { 699 // assert x >>> 31 == 0; 700 // assert zOff <= 4; 701 702 long c = 0, xVal = x & M, yVal = y & M; 703 c += yVal * xVal + (z[zOff + 0] & M); 704 z[zOff + 0] = (int)c; 705 c >>>= 32; 706 c += yVal + (z[zOff + 1] & M); 707 z[zOff + 1] = (int)c; 708 c >>>= 32; 709 c += (z[zOff + 2] & M); 710 z[zOff + 2] = (int)c; 711 c >>>= 32; 712 return c == 0 ? 0 : Nat.incAt(7, z, zOff, 3); 713 } 714 715 public static int mulWordDwordAdd(int x, long y, int[] z, int zOff) 716 { 717 // assert zOff <= 4; 718 long c = 0, xVal = x & M; 719 c += xVal * (y & M) + (z[zOff + 0] & M); 720 z[zOff + 0] = (int)c; 721 c >>>= 32; 722 c += xVal * (y >>> 32) + (z[zOff + 1] & M); 723 z[zOff + 1] = (int)c; 724 c >>>= 32; 725 c += (z[zOff + 2] & M); 726 z[zOff + 2] = (int)c; 727 c >>>= 32; 728 return c == 0 ? 0 : Nat.incAt(7, z, zOff, 3); 729 } 730 731 public static int mulWord(int x, int[] y, int[] z, int zOff) 732 { 733 long c = 0, xVal = x & M; 734 int i = 0; 735 do 736 { 737 c += xVal * (y[i] & M); 738 z[zOff + i] = (int)c; 739 c >>>= 32; 740 } 741 while (++i < 7); 742 return (int)c; 743 } 744 745 public static void square(int[] x, int[] zz) 746 { 747 long x_0 = x[0] & M; 748 long zz_1; 749 750 int c = 0, w; 751 { 752 int i = 6, j = 14; 753 do 754 { 755 long xVal = (x[i--] & M); 756 long p = xVal * xVal; 757 zz[--j] = (c << 31) | (int)(p >>> 33); 758 zz[--j] = (int)(p >>> 1); 759 c = (int)p; 760 } 761 while (i > 0); 762 763 { 764 long p = x_0 * x_0; 765 zz_1 = ((c << 31) & M) | (p >>> 33); 766 zz[0] = (int)p; 767 c = (int)(p >>> 32) & 1; 768 } 769 } 770 771 long x_1 = x[1] & M; 772 long zz_2 = zz[2] & M; 773 774 { 775 zz_1 += x_1 * x_0; 776 w = (int)zz_1; 777 zz[1] = (w << 1) | c; 778 c = w >>> 31; 779 zz_2 += zz_1 >>> 32; 780 } 781 782 long x_2 = x[2] & M; 783 long zz_3 = zz[3] & M; 784 long zz_4 = zz[4] & M; 785 { 786 zz_2 += x_2 * x_0; 787 w = (int)zz_2; 788 zz[2] = (w << 1) | c; 789 c = w >>> 31; 790 zz_3 += (zz_2 >>> 32) + x_2 * x_1; 791 zz_4 += zz_3 >>> 32; 792 zz_3 &= M; 793 } 794 795 long x_3 = x[3] & M; 796 long zz_5 = (zz[5] & M) + (zz_4 >>> 32); zz_4 &= M; 797 long zz_6 = (zz[6] & M) + (zz_5 >>> 32); zz_5 &= M; 798 { 799 zz_3 += x_3 * x_0; 800 w = (int)zz_3; 801 zz[3] = (w << 1) | c; 802 c = w >>> 31; 803 zz_4 += (zz_3 >>> 32) + x_3 * x_1; 804 zz_5 += (zz_4 >>> 32) + x_3 * x_2; 805 zz_4 &= M; 806 zz_6 += zz_5 >>> 32; 807 zz_5 &= M; 808 } 809 810 long x_4 = x[4] & M; 811 long zz_7 = (zz[7] & M) + (zz_6 >>> 32); zz_6 &= M; 812 long zz_8 = (zz[8] & M) + (zz_7 >>> 32); zz_7 &= M; 813 { 814 zz_4 += x_4 * x_0; 815 w = (int)zz_4; 816 zz[4] = (w << 1) | c; 817 c = w >>> 31; 818 zz_5 += (zz_4 >>> 32) + x_4 * x_1; 819 zz_6 += (zz_5 >>> 32) + x_4 * x_2; 820 zz_5 &= M; 821 zz_7 += (zz_6 >>> 32) + x_4 * x_3; 822 zz_6 &= M; 823 zz_8 += zz_7 >>> 32; 824 zz_7 &= M; 825 } 826 827 long x_5 = x[5] & M; 828 long zz_9 = (zz[9] & M) + (zz_8 >>> 32); zz_8 &= M; 829 long zz_10 = (zz[10] & M) + (zz_9 >>> 32); zz_9 &= M; 830 { 831 zz_5 += x_5 * x_0; 832 w = (int)zz_5; 833 zz[5] = (w << 1) | c; 834 c = w >>> 31; 835 zz_6 += (zz_5 >>> 32) + x_5 * x_1; 836 zz_7 += (zz_6 >>> 32) + x_5 * x_2; 837 zz_6 &= M; 838 zz_8 += (zz_7 >>> 32) + x_5 * x_3; 839 zz_7 &= M; 840 zz_9 += (zz_8 >>> 32) + x_5 * x_4; 841 zz_8 &= M; 842 zz_10 += zz_9 >>> 32; 843 zz_9 &= M; 844 } 845 846 long x_6 = x[6] & M; 847 long zz_11 = (zz[11] & M) + (zz_10 >>> 32); zz_10 &= M; 848 long zz_12 = (zz[12] & M) + (zz_11 >>> 32); zz_11 &= M; 849 { 850 zz_6 += x_6 * x_0; 851 w = (int)zz_6; 852 zz[6] = (w << 1) | c; 853 c = w >>> 31; 854 zz_7 += (zz_6 >>> 32) + x_6 * x_1; 855 zz_8 += (zz_7 >>> 32) + x_6 * x_2; 856 zz_9 += (zz_8 >>> 32) + x_6 * x_3; 857 zz_10 += (zz_9 >>> 32) + x_6 * x_4; 858 zz_11 += (zz_10 >>> 32) + x_6 * x_5; 859 zz_12 += zz_11 >>> 32; 860 } 861 862 w = (int)zz_7; 863 zz[7] = (w << 1) | c; 864 c = w >>> 31; 865 w = (int)zz_8; 866 zz[8] = (w << 1) | c; 867 c = w >>> 31; 868 w = (int)zz_9; 869 zz[9] = (w << 1) | c; 870 c = w >>> 31; 871 w = (int)zz_10; 872 zz[10] = (w << 1) | c; 873 c = w >>> 31; 874 w = (int)zz_11; 875 zz[11] = (w << 1) | c; 876 c = w >>> 31; 877 w = (int)zz_12; 878 zz[12] = (w << 1) | c; 879 c = w >>> 31; 880 w = zz[13] + (int)(zz_12 >>> 32); 881 zz[13] = (w << 1) | c; 882 } 883 884 public static void square(int[] x, int xOff, int[] zz, int zzOff) 885 { 886 long x_0 = x[xOff + 0] & M; 887 long zz_1; 888 889 int c = 0, w; 890 { 891 int i = 6, j = 14; 892 do 893 { 894 long xVal = (x[xOff + i--] & M); 895 long p = xVal * xVal; 896 zz[zzOff + --j] = (c << 31) | (int)(p >>> 33); 897 zz[zzOff + --j] = (int)(p >>> 1); 898 c = (int)p; 899 } 900 while (i > 0); 901 902 { 903 long p = x_0 * x_0; 904 zz_1 = ((c << 31) & M) | (p >>> 33); 905 zz[zzOff + 0] = (int)p; 906 c = (int)(p >>> 32) & 1; 907 } 908 } 909 910 long x_1 = x[xOff + 1] & M; 911 long zz_2 = zz[zzOff + 2] & M; 912 913 { 914 zz_1 += x_1 * x_0; 915 w = (int)zz_1; 916 zz[zzOff + 1] = (w << 1) | c; 917 c = w >>> 31; 918 zz_2 += zz_1 >>> 32; 919 } 920 921 long x_2 = x[xOff + 2] & M; 922 long zz_3 = zz[zzOff + 3] & M; 923 long zz_4 = zz[zzOff + 4] & M; 924 { 925 zz_2 += x_2 * x_0; 926 w = (int)zz_2; 927 zz[zzOff + 2] = (w << 1) | c; 928 c = w >>> 31; 929 zz_3 += (zz_2 >>> 32) + x_2 * x_1; 930 zz_4 += zz_3 >>> 32; 931 zz_3 &= M; 932 } 933 934 long x_3 = x[xOff + 3] & M; 935 long zz_5 = (zz[zzOff + 5] & M) + (zz_4 >>> 32); zz_4 &= M; 936 long zz_6 = (zz[zzOff + 6] & M) + (zz_5 >>> 32); zz_5 &= M; 937 { 938 zz_3 += x_3 * x_0; 939 w = (int)zz_3; 940 zz[zzOff + 3] = (w << 1) | c; 941 c = w >>> 31; 942 zz_4 += (zz_3 >>> 32) + x_3 * x_1; 943 zz_5 += (zz_4 >>> 32) + x_3 * x_2; 944 zz_4 &= M; 945 zz_6 += zz_5 >>> 32; 946 zz_5 &= M; 947 } 948 949 long x_4 = x[xOff + 4] & M; 950 long zz_7 = (zz[zzOff + 7] & M) + (zz_6 >>> 32); zz_6 &= M; 951 long zz_8 = (zz[zzOff + 8] & M) + (zz_7 >>> 32); zz_7 &= M; 952 { 953 zz_4 += x_4 * x_0; 954 w = (int)zz_4; 955 zz[zzOff + 4] = (w << 1) | c; 956 c = w >>> 31; 957 zz_5 += (zz_4 >>> 32) + x_4 * x_1; 958 zz_6 += (zz_5 >>> 32) + x_4 * x_2; 959 zz_5 &= M; 960 zz_7 += (zz_6 >>> 32) + x_4 * x_3; 961 zz_6 &= M; 962 zz_8 += zz_7 >>> 32; 963 zz_7 &= M; 964 } 965 966 long x_5 = x[xOff + 5] & M; 967 long zz_9 = (zz[zzOff + 9] & M) + (zz_8 >>> 32); zz_8 &= M; 968 long zz_10 = (zz[zzOff + 10] & M) + (zz_9 >>> 32); zz_9 &= M; 969 { 970 zz_5 += x_5 * x_0; 971 w = (int)zz_5; 972 zz[zzOff + 5] = (w << 1) | c; 973 c = w >>> 31; 974 zz_6 += (zz_5 >>> 32) + x_5 * x_1; 975 zz_7 += (zz_6 >>> 32) + x_5 * x_2; 976 zz_6 &= M; 977 zz_8 += (zz_7 >>> 32) + x_5 * x_3; 978 zz_7 &= M; 979 zz_9 += (zz_8 >>> 32) + x_5 * x_4; 980 zz_8 &= M; 981 zz_10 += zz_9 >>> 32; 982 zz_9 &= M; 983 } 984 985 long x_6 = x[xOff + 6] & M; 986 long zz_11 = (zz[zzOff + 11] & M) + (zz_10 >>> 32); zz_10 &= M; 987 long zz_12 = (zz[zzOff + 12] & M) + (zz_11 >>> 32); zz_11 &= M; 988 { 989 zz_6 += x_6 * x_0; 990 w = (int)zz_6; 991 zz[zzOff + 6] = (w << 1) | c; 992 c = w >>> 31; 993 zz_7 += (zz_6 >>> 32) + x_6 * x_1; 994 zz_8 += (zz_7 >>> 32) + x_6 * x_2; 995 zz_9 += (zz_8 >>> 32) + x_6 * x_3; 996 zz_10 += (zz_9 >>> 32) + x_6 * x_4; 997 zz_11 += (zz_10 >>> 32) + x_6 * x_5; 998 zz_12 += zz_11 >>> 32; 999 } 1000 1001 w = (int)zz_7; 1002 zz[zzOff + 7] = (w << 1) | c; 1003 c = w >>> 31; 1004 w = (int)zz_8; 1005 zz[zzOff + 8] = (w << 1) | c; 1006 c = w >>> 31; 1007 w = (int)zz_9; 1008 zz[zzOff + 9] = (w << 1) | c; 1009 c = w >>> 31; 1010 w = (int)zz_10; 1011 zz[zzOff + 10] = (w << 1) | c; 1012 c = w >>> 31; 1013 w = (int)zz_11; 1014 zz[zzOff + 11] = (w << 1) | c; 1015 c = w >>> 31; 1016 w = (int)zz_12; 1017 zz[zzOff + 12] = (w << 1) | c; 1018 c = w >>> 31; 1019 w = zz[zzOff + 13] + (int)(zz_12 >>> 32); 1020 zz[zzOff + 13] = (w << 1) | c; 1021 } 1022 1023 public static int sub(int[] x, int[] y, int[] z) 1024 { 1025 long c = 0; 1026 c += (x[0] & M) - (y[0] & M); 1027 z[0] = (int)c; 1028 c >>= 32; 1029 c += (x[1] & M) - (y[1] & M); 1030 z[1] = (int)c; 1031 c >>= 32; 1032 c += (x[2] & M) - (y[2] & M); 1033 z[2] = (int)c; 1034 c >>= 32; 1035 c += (x[3] & M) - (y[3] & M); 1036 z[3] = (int)c; 1037 c >>= 32; 1038 c += (x[4] & M) - (y[4] & M); 1039 z[4] = (int)c; 1040 c >>= 32; 1041 c += (x[5] & M) - (y[5] & M); 1042 z[5] = (int)c; 1043 c >>= 32; 1044 c += (x[6] & M) - (y[6] & M); 1045 z[6] = (int)c; 1046 c >>= 32; 1047 return (int)c; 1048 } 1049 1050 public static int sub(int[] x, int xOff, int[] y, int yOff, int[] z, int zOff) 1051 { 1052 long c = 0; 1053 c += (x[xOff + 0] & M) - (y[yOff + 0] & M); 1054 z[zOff + 0] = (int)c; 1055 c >>= 32; 1056 c += (x[xOff + 1] & M) - (y[yOff + 1] & M); 1057 z[zOff + 1] = (int)c; 1058 c >>= 32; 1059 c += (x[xOff + 2] & M) - (y[yOff + 2] & M); 1060 z[zOff + 2] = (int)c; 1061 c >>= 32; 1062 c += (x[xOff + 3] & M) - (y[yOff + 3] & M); 1063 z[zOff + 3] = (int)c; 1064 c >>= 32; 1065 c += (x[xOff + 4] & M) - (y[yOff + 4] & M); 1066 z[zOff + 4] = (int)c; 1067 c >>= 32; 1068 c += (x[xOff + 5] & M) - (y[yOff + 5] & M); 1069 z[zOff + 5] = (int)c; 1070 c >>= 32; 1071 c += (x[xOff + 6] & M) - (y[yOff + 6] & M); 1072 z[zOff + 6] = (int)c; 1073 c >>= 32; 1074 return (int)c; 1075 } 1076 1077 public static int subBothFrom(int[] x, int[] y, int[] z) 1078 { 1079 long c = 0; 1080 c += (z[0] & M) - (x[0] & M) - (y[0] & M); 1081 z[0] = (int)c; 1082 c >>= 32; 1083 c += (z[1] & M) - (x[1] & M) - (y[1] & M); 1084 z[1] = (int)c; 1085 c >>= 32; 1086 c += (z[2] & M) - (x[2] & M) - (y[2] & M); 1087 z[2] = (int)c; 1088 c >>= 32; 1089 c += (z[3] & M) - (x[3] & M) - (y[3] & M); 1090 z[3] = (int)c; 1091 c >>= 32; 1092 c += (z[4] & M) - (x[4] & M) - (y[4] & M); 1093 z[4] = (int)c; 1094 c >>= 32; 1095 c += (z[5] & M) - (x[5] & M) - (y[5] & M); 1096 z[5] = (int)c; 1097 c >>= 32; 1098 c += (z[6] & M) - (x[6] & M) - (y[6] & M); 1099 z[6] = (int)c; 1100 c >>= 32; 1101 return (int)c; 1102 } 1103 1104 public static int subFrom(int[] x, int[] z) 1105 { 1106 long c = 0; 1107 c += (z[0] & M) - (x[0] & M); 1108 z[0] = (int)c; 1109 c >>= 32; 1110 c += (z[1] & M) - (x[1] & M); 1111 z[1] = (int)c; 1112 c >>= 32; 1113 c += (z[2] & M) - (x[2] & M); 1114 z[2] = (int)c; 1115 c >>= 32; 1116 c += (z[3] & M) - (x[3] & M); 1117 z[3] = (int)c; 1118 c >>= 32; 1119 c += (z[4] & M) - (x[4] & M); 1120 z[4] = (int)c; 1121 c >>= 32; 1122 c += (z[5] & M) - (x[5] & M); 1123 z[5] = (int)c; 1124 c >>= 32; 1125 c += (z[6] & M) - (x[6] & M); 1126 z[6] = (int)c; 1127 c >>= 32; 1128 return (int)c; 1129 } 1130 1131 public static int subFrom(int[] x, int xOff, int[] z, int zOff) 1132 { 1133 long c = 0; 1134 c += (z[zOff + 0] & M) - (x[xOff + 0] & M); 1135 z[zOff + 0] = (int)c; 1136 c >>= 32; 1137 c += (z[zOff + 1] & M) - (x[xOff + 1] & M); 1138 z[zOff + 1] = (int)c; 1139 c >>= 32; 1140 c += (z[zOff + 2] & M) - (x[xOff + 2] & M); 1141 z[zOff + 2] = (int)c; 1142 c >>= 32; 1143 c += (z[zOff + 3] & M) - (x[xOff + 3] & M); 1144 z[zOff + 3] = (int)c; 1145 c >>= 32; 1146 c += (z[zOff + 4] & M) - (x[xOff + 4] & M); 1147 z[zOff + 4] = (int)c; 1148 c >>= 32; 1149 c += (z[zOff + 5] & M) - (x[xOff + 5] & M); 1150 z[zOff + 5] = (int)c; 1151 c >>= 32; 1152 c += (z[zOff + 6] & M) - (x[xOff + 6] & M); 1153 z[zOff + 6] = (int)c; 1154 c >>= 32; 1155 return (int)c; 1156 } 1157 1158 public static BigInteger toBigInteger(int[] x) 1159 { 1160 byte[] bs = new byte[28]; 1161 for (int i = 0; i < 7; ++i) 1162 { 1163 int x_i = x[i]; 1164 if (x_i != 0) 1165 { 1166 Pack.intToBigEndian(x_i, bs, (6 - i) << 2); 1167 } 1168 } 1169 return new BigInteger(1, bs); 1170 } 1171 1172 public static void zero(int[] z) 1173 { 1174 z[0] = 0; 1175 z[1] = 0; 1176 z[2] = 0; 1177 z[3] = 0; 1178 z[4] = 0; 1179 z[5] = 0; 1180 z[6] = 0; 1181 } 1182 } 1183
