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