MP.CPP (167556B)
1 // 2 // Copyright 2020 Electronic Arts Inc. 3 // 4 // TiberianDawn.DLL and RedAlert.dll and corresponding source code is free 5 // software: you can redistribute it and/or modify it under the terms of 6 // the GNU General Public License as published by the Free Software Foundation, 7 // either version 3 of the License, or (at your option) any later version. 8 9 // TiberianDawn.DLL and RedAlert.dll and corresponding source code is distributed 10 // in the hope that it will be useful, but with permitted additional restrictions 11 // under Section 7 of the GPL. See the GNU General Public License in LICENSE.TXT 12 // distributed with this program. You should have received a copy of the 13 // GNU General Public License along with permitted additional restrictions 14 // with this program. If not, see https://github.com/electronicarts/CnC_Remastered_Collection 15 16 /* $Header: /CounterStrike/MP.CPP 1 3/03/97 10:25a Joe_bostic $ */ 17 /*********************************************************************************************** 18 *** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S *** 19 *********************************************************************************************** 20 * * 21 * Project Name : Command & Conquer * 22 * * 23 * File Name : MP.CPP * 24 * * 25 * Programmer : Joe L. Bostic * 26 * * 27 * Start Date : 04/26/96 * 28 * * 29 * Last Update : July 2, 1996 [JLB] * 30 * * 31 *---------------------------------------------------------------------------------------------* 32 * Functions: * 33 * _Byte_Precision -- Determines the number of bytes significant in long integer. * 34 * memrev -- Reverse the byte order of the buffer specified. * 35 * XMP_Abs -- Perform an absolute value on the specified MP number. * 36 * XMP_Add -- Add two MP numbers with a carry option. * 37 * XMP_Add_Int -- Add an integer to an MP number (with carry). * 38 * XMP_Compare -- Compare one MP number with another. * 39 * XMP_Count_Bits -- Count the total number of bits (precision) in MP number. * 40 * XMP_Count_Bytes -- Counts the number of precision bytes in MP number. * 41 * XMP_Dec -- Decrement the MP number by one. * 42 * XMP_Decode_ASCII -- Convert ASCII into an MP number. * 43 * XMP_DER_Decode -- Decode a DER number into an MP number. * 44 * XMP_DER_Encode -- Encode a number into a buffer using DER. * 45 * XMP_DER_Length_Encode -- Output the length of a DER block. * 46 * XMP_Double_Mul -- Double precision MP multiply. * 47 * XMP_Encode -- Encode MP number into buffer as compactly as possible. * 48 * XMP_Fermat_Test -- Performs Fermat's Little Theorem on an MP number. * 49 * XMP_Hybrid_Mul -- Special hybrid short multiply (with carry). * 50 * XMP_Inc -- Increment an MP number by one. * 51 * XMP_Init -- Initialize an MP number to a starting value. * 52 * XMP_Inverse_A_Mod_B -- Inverts and performs modulus on an MP number. * 53 * XMP_Is_Prime -- Determine if the specified MP number is prime. * 54 * XMP_Is_Small_Prime -- Determine if MP number is a small prime. * 55 * XMP_Mod_Mult -- Perform a multiply - modulus operation. * 56 * XMP_Mod_Mult_Clear -- Remove temporary values from memory. * 57 * XMP_Move -- Assign one MP number to another. * 58 * XMP_Neg -- Negate the specified MP number. * 59 * XMP_Not -- Perform bitwise NOT operation on MP number. * 60 * XMP_Prepare_Modulus -- Prepare globals for modulus operation. * 61 * XMP_Rabin_Miller_Test -- Performs the Rabin Miller test for primality. * 62 * XMP_Randomize -- Generate a random MP number between the boundaries specified. * 63 * XMP_Randomize -- Generate a random MP number. * 64 * XMP_Reciprocal -- Compute the reciprocal (inverse) of the MP number. * 65 * XMP_Rotate_Left -- Rotate specified MP number leftward. * 66 * XMP_Shift_Left_Bits -- Shifts the MP number left by the specified bit count. * 67 * XMP_Shift_Right_Bits -- Shift the MP number right by specified bit count. * 68 * XMP_Signed_Decode -- Decode a number as if it were signed. * 69 * XMP_Signed_Div -- Signed divide of one MP number into another. * 70 * XMP_Signed_Mult -- A signed multiply between two MP numbers. * 71 * XMP_Signed_Mult_Int -- Multiply an MP number by a signed simple integer. * 72 * XMP_Significance -- Fetch the precision (bytes) of the MP number. * 73 * XMP_Small_Divisors_Test -- Perform the small divisors test on an MP number. * 74 * XMP_Sub -- Subtract one MP number from another (with borrow). * 75 * XMP_Sub_Int -- Subtract an integer from an MP number (with borrow). * 76 * XMP_Unsigned_Decode -- Decode a number as if it were unsigned. * 77 * XMP_Unsigned_Div -- Unsigned divide of one MP number into another. * 78 * XMP_Unsigned_Div_Int -- Perform a short integer divide into an MP number. * 79 * XMP_Unsigned_Mult -- Multiply two unsigned MP numbers together. * 80 * XMP_Unsigned_Mult_Int -- Multiply an MP number by a simple integer. * 81 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ 82 83 84 #include <stdlib.h> 85 #include <string.h> 86 #include <ctype.h> 87 #include <assert.h> 88 #include <limits.h> 89 #include "mp.h" 90 91 92 #ifndef __BORLANDC__ 93 #define min(a, b) (((a) < (b)) ? (a) : (b)) 94 #define _USERENTRY 95 #endif 96 97 98 /*********************************************************************************************** 99 * _Byte_Precision -- Determines the number of bytes significant in long integer. * 100 * * 101 * This utility routine will determine the number of precision bytes exist in the long * 102 * integer specified. There are some optimizations that can occur if the byte precision * 103 * is known. * 104 * * 105 * INPUT: value -- The value of the long integer that the byte precision will be calculated * 106 * for. * 107 * * 108 * OUTPUT: Returns with the number of bytes that the long integer requires (at a minimum) * 109 * to cover the precision of the integer. The minimum value will be 1, the maximum * 110 * will be 4. * 111 * * 112 * WARNINGS: none * 113 * * 114 * HISTORY: * 115 * 07/01/1996 JLB : Created. * 116 *=============================================================================================*/ 117 static int _Byte_Precision(unsigned long value) 118 { 119 int byte_count; 120 for (byte_count = sizeof(value); byte_count; byte_count--) { 121 if (value >> ((byte_count-1)*8)) break; 122 } 123 return(byte_count); 124 } 125 126 127 /*********************************************************************************************** 128 * XMP_DER_Length_Encode -- Output the length of a DER block. * 129 * * 130 * This routine will output the length of the block using Distinguished Encoding Rules. * 131 * The rest of the block must be filled in as appropriate. For data blocks that are less * 132 * than 128 bytes long, the header consists of only one byte. Longer buffers lengths * 133 * can consume up to 5 bytes (depends on magnitude of the length value). * 134 * * 135 * INPUT: length -- The length of the data block to be output. * 136 * * 137 * output -- Pointer to the memory block that will be set up. * 138 * * 139 * OUTPUT: Returns with the number of bytes (header) that was used to store the length * 140 * value. Subsequent data must be placed after the header. * 141 * * 142 * WARNINGS: none * 143 * * 144 * HISTORY: * 145 * 07/01/1996 JLB : Created. * 146 *=============================================================================================*/ 147 int XMP_DER_Length_Encode(unsigned long length, unsigned char * output) 148 { 149 assert(output != NULL); 150 151 int header_length = 0; 152 153 if (length <= SCHAR_MAX) { 154 output[header_length++] = (unsigned char)length; 155 } else { 156 output[header_length++] = (unsigned char)(_Byte_Precision(length) | 0x80); 157 for (int byte_counter = _Byte_Precision(length); byte_counter; --byte_counter) { 158 output[header_length++] = (unsigned char)(length >> ((byte_counter-1)*8)); 159 } 160 } 161 return(header_length); 162 } 163 164 165 /*********************************************************************************************** 166 * XMP_DER_Encode -- Encode a number into a buffer using DER. * 167 * * 168 * This routine is used to encode a number into a buffer using Distinguished Encoding * 169 * Rules. The number of bytes used will be, typically, two bytes more than the number of * 170 * precision bytes in the number. * 171 * * 172 * INPUT: from -- Pointer to the multi-precision number. * 173 * * 174 * output -- Pointer to the buffer that will hold the DER encoded number. * 175 * * 176 * precision-- The precision of the multi-precision number. * 177 * * 178 * OUTPUT: Returns with the number of bytes used in the output buffer. * 179 * * 180 * WARNINGS: Make sure the buffer is big enough to hold the DER encoded number. For safety * 181 * make sure it is precision+6 bytes long. * 182 * * 183 * HISTORY: * 184 * 07/01/1996 JLB : Created. * 185 *=============================================================================================*/ 186 int XMP_DER_Encode(digit const * from, unsigned char * output, int precision) 187 { 188 assert(from != NULL); 189 assert(output != NULL); 190 assert(precision > 0); 191 192 unsigned char buffer[MAX_UNIT_PRECISION*sizeof(digit)+1]; 193 int header_count = 0; 194 195 unsigned number_count = XMP_Encode(buffer, from, precision); 196 197 output[header_count++] = 0x02; 198 header_count += XMP_DER_Length_Encode(number_count, &output[header_count]); 199 memcpy(&output[header_count], buffer, number_count); 200 201 return(header_count+number_count); 202 } 203 204 205 /*********************************************************************************************** 206 * XMP_DER_Decode -- Decode a DER number into an MP number. * 207 * * 208 * Use this routine to decode a Distinguished Encoding Rules number into a multi-precision * 209 * number. This is the counterpart function to the XMP_DER_Encode() function. * 210 * * 211 * INPUT: result -- The buffer the hold the result MP number. * 212 * * 213 * input -- Pointer to the DER encoded number. * 214 * * 215 * precision -- The precision of the MP number. This is the maximum precision the * 216 * DER number can be. * 217 * * 218 * OUTPUT: none * 219 * * 220 * WARNINGS: none * 221 * * 222 * HISTORY: * 223 * 07/01/1996 JLB : Created. * 224 *=============================================================================================*/ 225 void XMP_DER_Decode(digit * result, unsigned char const * input, int precision) 226 { 227 assert(result != NULL); 228 assert(input != NULL); 229 assert(precision > 0); 230 231 if (*input++ == 0x02) { 232 unsigned byte_count; 233 234 if ((*input & 0x80) == 0) { 235 byte_count = *input++; 236 } else { 237 int length = *input++ & 0x7f; 238 if (length > 2) return; 239 byte_count = *input++; 240 if (length > 1) byte_count = (byte_count << 8) | *input++; 241 } 242 if (byte_count <= (precision * sizeof(digit))) { 243 XMP_Signed_Decode(result, input, byte_count, precision); 244 } 245 } 246 } 247 248 249 /*********************************************************************************************** 250 * XMP_Encode -- Encode MP number into buffer. * 251 * * 252 * This routine will encode an multi-precision number into a buffer of specified length. * 253 * The number of stored in "big endian" format with appropriate sign extension. * 254 * * 255 * INPUT: to -- Pointer to the buffer to place the number. * 256 * * 257 * tobytes -- The number of bytes to use in the destination buffer. * 258 * * 259 * from -- Pointer to the MP number to be encoded. * 260 * * 261 * precision-- The precision of the MP number. * 262 * * 263 * OUTPUT: Returns with the number of bytes placed into the destination buffer. * 264 * * 265 * WARNINGS: none * 266 * * 267 * HISTORY: * 268 * 07/01/1996 JLB : Created. * 269 *=============================================================================================*/ 270 unsigned XMP_Encode(unsigned char * to, unsigned tobytes, digit const * from, int precision) 271 { 272 assert(to != NULL); 273 assert(from != NULL); 274 assert(tobytes > 0); 275 assert(precision > 0); 276 277 unsigned frombytes = precision * sizeof(digit); 278 unsigned char filler = (unsigned char)(XMP_Is_Negative(from, precision) ? 0xff : 0); 279 280 int index; 281 for (index = 0; index < (int)(tobytes-frombytes); index++) { 282 *to++ = filler; 283 } 284 285 const unsigned char * fptr = ((const unsigned char *)from) + min(tobytes, frombytes); 286 for (index = 0; index < (int)min(tobytes, frombytes); index++) { 287 *to++ = *--fptr; 288 } 289 290 return(tobytes); 291 } 292 293 294 /*********************************************************************************************** 295 * XMP_Encode -- Encode MP number into buffer as compactly as possible. * 296 * * 297 * This routine will encode the MP number into the specified buffer. The number will be * 298 * encoded using the least number of bytes possible. * 299 * * 300 * INPUT: to -- The buffer to encode the MP number into. * 301 * * 302 * from -- Pointer to the MP number to be encoded. * 303 * * 304 * precision-- The precision of the MP number. * 305 * * 306 * OUTPUT: Returns with the number of bytes used in the destination buffer to hold the * 307 * encoded number. * 308 * * 309 * WARNINGS: Be sure the destination buffer is big enough to hold the encoded MP number. * 310 * A safe size would be the precision plus one. * 311 * * 312 * HISTORY: * 313 * 07/01/1996 JLB : Created. * 314 *=============================================================================================*/ 315 //#pragma warning 364 9 316 unsigned XMP_Encode(unsigned char * to, digit const * from, int precision) 317 { 318 assert(to != NULL); 319 assert(from != NULL); 320 assert(precision > 0); 321 322 bool is_negative = XMP_Is_Negative(from, precision); 323 unsigned char filler = (unsigned char)(is_negative ? 0xff : 0); 324 unsigned char * number_ptr; 325 326 unsigned char * const end = (unsigned char *)from; 327 for (number_ptr = (unsigned char *)end + precision - 1; number_ptr > (unsigned char *)end; number_ptr--) { 328 if (*number_ptr != filler) break; 329 } 330 331 unsigned index = 0; 332 if (((*number_ptr & 0x80) && !is_negative) || (!(*number_ptr & 0x80) && is_negative)) { 333 to[index++] = filler; 334 } 335 336 to[index++] = *number_ptr; 337 338 while (number_ptr != end) { 339 to[index++] = *--number_ptr; 340 } 341 return(index); 342 } 343 344 345 /*********************************************************************************************** 346 * XMP_Signed_Decode -- Decode a number as if it were signed. * 347 * * 348 * Use this routine to convert a coded number back into an MP number. The coded number * 349 * is presumed to be signed. * 350 * * 351 * INPUT: result -- Pointer to the buffer that will hold the decoded MP number. * 352 * * 353 * from -- Pointer to the encoded MP number. * 354 * * 355 * frombytes-- The number of bytes consumed by the encoded MP number. * 356 * * 357 * precision -- The precision of the MP number (maximum) of the result. * 358 * * 359 * OUTPUT: none * 360 * * 361 * WARNINGS: Be sure that the precision is sufficient to hold the decoded MP number. * 362 * Otherwise, the result is undefined. * 363 * * 364 * HISTORY: * 365 * 07/01/1996 JLB : Created. * 366 *=============================================================================================*/ 367 void XMP_Signed_Decode(digit * result, const unsigned char * from, int frombytes, int precision) 368 { 369 assert(result != NULL); 370 assert(from != NULL); 371 assert(frombytes > 0); 372 assert(precision > 0); 373 374 unsigned char filler = (unsigned char)((*from & 0x80) ? 0xff : 0); 375 376 int fillcount = precision * sizeof(digit) - frombytes; 377 unsigned char * dest = (unsigned char *)&result[precision]; 378 379 /* 380 ** Fill in any excess significant bytes. 381 */ 382 int index; 383 for (index = 0; index < fillcount; index++) { 384 *--dest = filler; 385 } 386 387 /* 388 ** Move in the remaining bytes. 389 */ 390 for (index = 0; index < frombytes; index++) { 391 *--dest = *from++; 392 } 393 } 394 395 396 /*********************************************************************************************** 397 * XMP_Unsigned_Decode -- Decode a number as if it were unsigned. * 398 * * 399 * Use this routine to decode a MP number and treat it as if it were unsigned. * 400 * * 401 * INPUT: result -- Pointer to the buffer to hold the result MP number. * 402 * * 403 * from -- Pointer to the encoded MP number. * 404 * * 405 * frombytes-- The number of bytes in the encoded number. * 406 * * 407 * precision-- The precision of the result MP number -- maximum precision. * 408 * * 409 * OUTPUT: none * 410 * * 411 * WARNINGS: Be sure the result MP precision is sufficient to hold the decoded number or * 412 * else the result is undefined. * 413 * * 414 * HISTORY: * 415 * 07/01/1996 JLB : Created. * 416 *=============================================================================================*/ 417 void XMP_Unsigned_Decode(digit * result, const unsigned char * from, int frombytes, int precision) 418 { 419 assert(result != NULL); 420 assert(from != NULL); 421 assert(frombytes > 0); 422 assert(precision > 0); 423 424 int fillcount = precision * sizeof(digit) - frombytes; 425 unsigned char * dest = (unsigned char *)&result[precision]; 426 427 /* 428 ** Fill in any excess significant bytes. 429 */ 430 int index; 431 for (index = 0; index < fillcount; index++) { 432 *--dest = '\0'; 433 } 434 435 /* 436 ** Move in the remaining bytes. 437 */ 438 for (index = 0; index < frombytes; index++) { 439 *--dest = *from++; 440 } 441 } 442 443 444 /*********************************************************************************************** 445 * XMP_Significance -- Fetch the precision (bytes) of the MP number. * 446 * * 447 * This routine will return with the precision of the MP number expressed as bytes. The * 448 * MP number is presumed unsigned. * 449 * * 450 * INPUT: number -- Pointer to the MP number to examine. * 451 * * 452 * precision-- The precision of the MP number to examine. * 453 * * 454 * OUTPUT: Returns with the minimum number of bytes consumed by this MP number. * 455 * * 456 * WARNINGS: Passing a signed MP number to this routine will return an artificially greater * 457 * precision than it really is. * 458 * * 459 * HISTORY: * 460 * 07/01/1996 JLB : Created. * 461 *=============================================================================================*/ 462 int XMP_Significance(const digit * number, int precision) 463 { 464 assert(number != NULL); 465 assert(precision > 0); 466 467 number += precision; 468 do { 469 if (*(--number)) break; 470 } while (--precision); 471 return(precision); 472 } 473 474 475 /*********************************************************************************************** 476 * XMP_Inc -- Increment an MP number by one. * 477 * * 478 * This will increment the MP number by one. * 479 * * 480 * INPUT: number -- Pointer to the MP number to increment. * 481 * * 482 * precision-- The precision of the MP number. * 483 * * 484 * OUTPUT: none * 485 * * 486 * WARNINGS: If the number wraps around the maximum precision, the results are undefined. * 487 * * 488 * HISTORY: * 489 * 07/01/1996 JLB : Created. * 490 *=============================================================================================*/ 491 void XMP_Inc(digit * number, int precision) 492 { 493 assert(number != NULL); 494 assert(precision > 0); 495 496 do { 497 if (++(*number)) break; 498 number++; 499 } while (--precision); 500 } 501 502 503 /*********************************************************************************************** 504 * XMP_Dec -- Decrement the MP number by one. * 505 * * 506 * Use this routine to decrement the specified MP number by one. * 507 * * 508 * INPUT: number -- Pointer to the MP number to decrement. * 509 * * 510 * precision-- The precision of the MP number to decrement. * 511 * * 512 * OUTPUT: none * 513 * * 514 * WARNINGS: If the number wraps below zero, the results are undefined. * 515 * * 516 * HISTORY: * 517 * 07/01/1996 JLB : Created. * 518 *=============================================================================================*/ 519 void XMP_Dec(digit * number, int precision) 520 { 521 assert(number != NULL); 522 assert(precision > 0); 523 524 do { 525 *number -= 1; 526 if ((*number) != ~(digit)0) break; 527 number++; 528 } while (--precision); 529 } 530 531 532 /*********************************************************************************************** 533 * XMP_Neg -- Negate the specified MP number. * 534 * * 535 * This routine will negate (reverse sign) of the specified MP number. * 536 * * 537 * INPUT: number -- Pointer to the MP number to negate. * 538 * * 539 * precision-- The precision of the MP number. * 540 * * 541 * OUTPUT: none * 542 * * 543 * WARNINGS: none * 544 * * 545 * HISTORY: * 546 * 07/01/1996 JLB : Created. * 547 *=============================================================================================*/ 548 void XMP_Neg(digit * number, int precision) 549 { 550 assert(number != NULL); 551 assert(precision > 0); 552 553 XMP_Not(number, precision); 554 XMP_Inc(number, precision); 555 } 556 557 558 /*********************************************************************************************** 559 * XMP_Abs -- Perform an absolute value on the specified MP number. * 560 * * 561 * This will perform the absolute value function on the specified MP number. That is, if * 562 * the MP number is negative, it will be transformed into a positive number. If the number * 563 * is already positive, then it will be left alone. * 564 * * 565 * INPUT: number -- Pointer to the MP number to ABS. * 566 * * 567 * precision-- The precision of the MP number. * 568 * * 569 * OUTPUT: none * 570 * * 571 * WARNINGS: none * 572 * * 573 * HISTORY: * 574 * 07/01/1996 JLB : Created. * 575 *=============================================================================================*/ 576 void XMP_Abs(digit * number, int precision) 577 { 578 assert(number != NULL); 579 assert(precision > 0); 580 581 if (XMP_Is_Negative(number, precision)) { 582 XMP_Neg(number, precision); 583 } 584 } 585 586 587 /*********************************************************************************************** 588 * XMP_Shift_Right_Bits -- Shift the MP number right by specified bit count. * 589 * * 590 * Use this routine to perform a right shift of the MP number by the number of bits * 591 * specified. * 592 * * 593 * INPUT: number -- Pointer to the MP number to perform the shift upon. * 594 * * 595 * bits -- The number of bits to shift. * 596 * * 597 * precision-- The precision of the MP number. * 598 * * 599 * OUTPUT: none * 600 * * 601 * WARNINGS: This is an unsigned shift. * 602 * * 603 * HISTORY: * 604 * 07/01/1996 JLB : Created. * 605 *=============================================================================================*/ 606 void XMP_Shift_Right_Bits(digit * number, int bits, int precision) 607 { 608 assert(number != NULL); 609 assert(bits >= 0); 610 assert(precision > 0); 611 612 if (bits == 0) return; /* shift zero bits is a no-op */ 613 614 /* 615 ** If the shift is by whole bytes, then the shift operation can 616 ** be performed very quickly. 617 */ 618 if (bits == UNITSIZE) { 619 number += precision; 620 digit carry = 0; 621 while (precision--) { 622 number--; 623 digit temp = *number; 624 *number = carry; 625 carry = temp; 626 } 627 return; 628 } 629 630 /* 631 ** If the number of bits to shift is less than one byte, then the 632 ** shift operation is a relatively simple "ripple" effect through 633 ** the MP number buffer. 634 */ 635 if (bits < UNITSIZE) { 636 number += precision; 637 digit carry = 0; 638 digit bitmask = (1L << bits) - 1; 639 int unbits = UNITSIZE - bits; 640 641 while (precision--) { 642 number--; 643 digit temp = *number & bitmask; 644 *number >>= bits; 645 *number |= carry << unbits; 646 carry = temp; 647 } 648 return; 649 } 650 651 /* 652 ** General purpose slow right. 653 */ 654 int digits_to_shift = bits / UNITSIZE; 655 int bits_to_shift = bits % UNITSIZE; 656 657 int index; 658 for (index = digits_to_shift; index < (precision-1); index++) { 659 *number = (*(number + digits_to_shift) >> bits_to_shift) | (*(number + (digits_to_shift + 1)) << (UNITSIZE - bits_to_shift)); 660 number++; 661 } 662 663 if (digits_to_shift < precision) { 664 *number = (*(number + digits_to_shift) >> bits_to_shift); 665 number++; 666 } 667 668 for (index= 0; index < min(digits_to_shift, precision); index++) { 669 *number++ = 0; 670 } 671 } 672 673 674 /*********************************************************************************************** 675 * XMP_Shift_Left_Bits -- Shifts the MP number left by the specified bit count. * 676 * * 677 * Use this routine to perform a left shift of the specified MP number. * 678 * * 679 * INPUT: number -- Pointer to the MP number to perform the shift operation on. * 680 * * 681 * bits -- The number of bits to shift the MP number leftward. * 682 * * 683 * precision-- The precision of the MP number. * 684 * * 685 * OUTPUT: none * 686 * * 687 * WARNINGS: none * 688 * * 689 * HISTORY: * 690 * 07/01/1996 JLB : Created. * 691 *=============================================================================================*/ 692 void XMP_Shift_Left_Bits(digit * number, int bits, int precision) 693 { 694 assert(number != NULL); 695 assert(bits >= 0); 696 assert(precision > 0); 697 698 if (bits == 0) return; /* shift zero bits is a no-op */ 699 700 /* 701 ** If the shift is by whole bytes, then the shift operation can 702 ** be performed very quickly. 703 */ 704 if (bits == UNITSIZE) { 705 digit carry = 0; 706 while (precision--) { 707 digit temp = *number; 708 *number = carry; 709 carry = temp; 710 number++; 711 } 712 return; 713 } 714 715 /* 716 ** If the number of bits to shift is less than one byte, then the 717 ** shift operation is a relatively simple "ripple" effect through 718 ** the MP number buffer. 719 */ 720 if (bits < UNITSIZE) { 721 digit carry = 0; 722 digit bitmask = ~(((digit)-1) >> bits); 723 int unbits = UNITSIZE - bits; /* shift bits must be <= UNITSIZE */ 724 725 while (precision--) { 726 digit temp = *number & bitmask; 727 *number = (*number << bits) | (carry >> unbits); 728 carry = temp; 729 number++; 730 } 731 return; 732 } 733 734 /* 735 ** General purpose slow left; 736 */ 737 int digits_to_shift = bits / UNITSIZE; 738 int bits_to_shift = bits % UNITSIZE; 739 740 int index; 741 number += precision-1; 742 for (index = digits_to_shift; index < (precision-1); index++) { 743 *number = (*(number - digits_to_shift) << bits_to_shift) | (*(number - (digits_to_shift + 1)) >> (UNITSIZE - bits_to_shift)); 744 number--; 745 } 746 747 if (digits_to_shift < precision) { 748 *number = (*(number - digits_to_shift) << bits_to_shift); 749 number--; 750 } 751 752 for (index = 0; index < min(digits_to_shift, precision); index++) { 753 *number-- = 0; 754 } 755 } 756 757 758 /*********************************************************************************************** 759 * XMP_Rotate_Left -- Rotate specified MP number leftward. * 760 * * 761 * This routine will rotate the MP number to the left by one bit. The rotation passes bits * 762 * through a "carry" bit position. The initial value of this "carry" bit is passed to the * 763 * routine and the final value is returned as the result. * 764 * * 765 * INPUT: number -- Pointer to the MP number to perform the left rotate upon. * 766 * * 767 * carry -- The initial value of the "carry" bit. * 768 * * 769 * precision-- The precision of the MP number specified. * 770 * * 771 * OUTPUT: Returns with the final value of the carry bit. This is the the bit value of the * 772 * upper most bit of the MP number prior to the rotate operation. * 773 * * 774 * WARNINGS: none * 775 * * 776 * HISTORY: * 777 * 07/01/1996 JLB : Created. * 778 *=============================================================================================*/ 779 bool XMP_Rotate_Left(digit * number, bool carry, int precision) 780 { 781 assert(number != NULL); 782 assert(precision > 0); 783 784 while (precision--) { 785 bool temp = ((*number & UPPER_MOST_BIT) != 0); 786 *number = (*number << 1); 787 if (carry) *number = *number + 1; 788 carry = temp; 789 number++; 790 } 791 return carry; 792 } 793 794 795 /*********************************************************************************************** 796 * XMP_Not -- Perform bitwise NOT operation on MP number. * 797 * * 798 * Perform a bitwise NOT operation. * 799 * * 800 * INPUT: number -- Pointer to the MP number to operate on. * 801 * * 802 * precision-- The precision of the MP number. * 803 * * 804 * OUTPUT: none * 805 * * 806 * WARNINGS: none * 807 * * 808 * HISTORY: * 809 * 07/01/1996 JLB : Created. * 810 *=============================================================================================*/ 811 void XMP_Not(digit * number, int precision) 812 { 813 assert(number != NULL); 814 assert(precision > 0); 815 816 for (int index = 0; index < precision; index++) { 817 *number = ~(*number); 818 number++; 819 } 820 } 821 822 823 /*********************************************************************************************** 824 * XMP_Init -- Initialize an MP number to a starting value. * 825 * * 826 * This will initialize (assign) a number to an MP number. The initial value is limited * 827 * to the precision allowed by a DIGIT type. * 828 * * 829 * INPUT: number -- Pointer to the MP number to initialize. * 830 * * 831 * value -- Initial integer value to assign to the MP number. * 832 * * 833 * precision-- The precision of the MP number. * 834 * * 835 * OUTPUT: none * 836 * * 837 * WARNINGS: none * 838 * * 839 * HISTORY: * 840 * 07/01/1996 JLB : Created. * 841 *=============================================================================================*/ 842 void XMP_Init(digit * number, digit value, int precision) 843 { 844 assert(number != NULL); 845 assert(precision > 0); 846 847 memset(number, '\0', precision * sizeof(digit)); 848 *number = value; 849 } 850 851 852 /*********************************************************************************************** 853 * XMP_Count_Bits -- Count the total number of bits (precision) in MP number. * 854 * * 855 * This routine will count the maximum number of bits used by this MP number. The result * 856 * could be referred to as the "bit precision" of the MP number. * 857 * * 858 * INPUT: number -- Pointer to the MP number to examine. * 859 * * 860 * precision-- The (digit) precision of the MP number. * 861 * * 862 * OUTPUT: Returns with the number of significant bits in the MP number. * 863 * * 864 * WARNINGS: none * 865 * * 866 * HISTORY: * 867 * 07/01/1996 JLB : Created. * 868 *=============================================================================================*/ 869 unsigned XMP_Count_Bits(const digit * number, int precision) 870 { 871 assert(number != NULL); 872 assert(precision > 0); 873 874 int sub_precision = XMP_Significance(number, precision); 875 if (!sub_precision) return(0); 876 int total_bit_count = XMP_Digits_To_Bits(sub_precision); 877 number += sub_precision-1; 878 digit high_bit_mask = UPPER_MOST_BIT; 879 880 while (!((*number) & high_bit_mask)) { 881 high_bit_mask >>= 1; 882 total_bit_count--; 883 } 884 885 return(total_bit_count); 886 } 887 888 889 /*********************************************************************************************** 890 * XMP_Count_Bytes -- Counts the number of precision bytes in MP number. * 891 * * 892 * This routine will scan the MP number and determine the number of bytes needed to * 893 * represent the MP number. Consider the result the "byte precision" of the number. * 894 * * 895 * INPUT: number -- Pointer to the MP number to examine. * 896 * * 897 * precision-- Precision of the MP number. * 898 * * 899 * OUTPUT: Returns with the number of bytes required to represent the precision of the number.* 900 * * 901 * WARNINGS: none * 902 * * 903 * HISTORY: * 904 * 07/01/1996 JLB : Created. * 905 *=============================================================================================*/ 906 int XMP_Count_Bytes(const digit * number, int precision) 907 { 908 unsigned char * ptr = (unsigned char *)number; 909 int count = 0; 910 for (unsigned index = 0; index < precision*sizeof(digit); index++) { 911 if (!*ptr) break; 912 count++; 913 ptr++; 914 } 915 return(count); 916 } 917 918 919 /*********************************************************************************************** 920 * XMP_Move -- Assign one MP number to another. * 921 * * 922 * This will move one MP number over the top of another. * 923 * * 924 * INPUT: dest -- Destination MP number (will get clobbered). * 925 * * 926 * source -- Source MP number. * 927 * * 928 * precision-- Precision of both MP numbers. * 929 * * 930 * OUTPUT: none * 931 * * 932 * WARNINGS: Both MP numbers must have the same precision. * 933 * * 934 * HISTORY: * 935 * 07/01/1996 JLB : Created. * 936 *=============================================================================================*/ 937 void XMP_Move(digit * dest, digit const * source, int precision) 938 { 939 memcpy(dest, source, precision * sizeof(digit)); 940 } 941 942 943 /*********************************************************************************************** 944 * XMP_Compare -- Compare one MP number with another. * 945 * * 946 * This routine will compare two MP numbers. It will return a value indicating which MP * 947 * number is greater or if they are equal. * 948 * * 949 * INPUT: left_number -- The left hand MP number. * 950 * * 951 * right_number-- The right hand MP number. * 952 * * 953 * precision -- The precision of the MP numbers. * 954 * * 955 * OUTPUT: Returns -1 if the left_number is less than the right_number. * 956 * Returns 1 if the left_number is greater than the right number. * 957 * Returns 0 if both numbers are identical. * 958 * * 959 * WARNINGS: Both numbers must have the same precision. * 960 * * 961 * HISTORY: * 962 * 07/01/1996 JLB : Created. * 963 *=============================================================================================*/ 964 int XMP_Compare(const digit * left_number, const digit * right_number, int precision) 965 { 966 left_number += precision-1; 967 right_number += precision-1; 968 do { 969 if (*left_number < *right_number) return -1; 970 if (*left_number > *right_number) return 1; 971 left_number--; 972 right_number--; 973 } while (--precision); 974 return 0; 975 } 976 977 978 /*********************************************************************************************** 979 * XMP_Add -- Add two MP numbers with a carry option. * 980 * * 981 * Use this routine to add one MP number to another. There is an optional "carry" value * 982 * that (when true) will add an additional 1 to the result. * 983 * * 984 * INPUT: result -- Pointer to the MP buffer that will hold the result. This can be the * 985 * same value as the left_number or right_number pointers. * 986 * * 987 * left_number -- The left hand MP number. * 988 * * 989 * right_number-- The right hand MP number. * 990 * * 991 * carry -- Optional carry flag (typically this will be false). * 992 * * 993 * precision -- The precision of the numbers involved. * 994 * * 995 * OUTPUT: Returns with the carry flag after the addition. If the value is true then an * 996 * overflow occurred. * 997 * * 998 * WARNINGS: none * 999 * * 1000 * HISTORY: * 1001 * 07/01/1996 JLB : Created. * 1002 *=============================================================================================*/ 1003 bool XMP_Add(digit * result, const digit * left_number, const digit * right_number, bool carry, int precision) 1004 { 1005 while (precision--) { 1006 digit term = *left_number + *right_number; 1007 digit final = term + carry; 1008 carry = (term < *left_number || (carry && final == 0)); 1009 1010 right_number++; 1011 left_number++; 1012 *result++ = final; 1013 } 1014 return(carry); 1015 } 1016 1017 1018 /*********************************************************************************************** 1019 * XMP_Add_Int -- Add an integer to an MP number (with carry). * 1020 * * 1021 * This routine will add an integer number to an MP number. There is an optional carry * 1022 * parameter. If the carry flag is true, and additional 1 will be added to the result. * 1023 * This routine is much faster than adding two MP numbers together. * 1024 * * 1025 * INPUT: result -- Pointer to the result MP number. This pointer can be the same as * 1026 * the left_number parameter. * 1027 * * 1028 * left_number -- Pointer to the left hand MP number. * 1029 * * 1030 * right_number-- The integer number to add to the left hand number. * 1031 * * 1032 * carry -- Input carry flag. If this is true, then an additional one will be * 1033 * added to the result. * 1034 * * 1035 * precision -- The precision of the MP numbers. * 1036 * * 1037 * OUTPUT: Returns with the result carry flag. A true value means the addition overflowed. * 1038 * * 1039 * WARNINGS: All MP numbers must share the same precision. Negative numbers are not * 1040 * supported. * 1041 * * 1042 * HISTORY: * 1043 * 07/01/1996 JLB : Created. * 1044 *=============================================================================================*/ 1045 bool XMP_Add_Int(digit * result, const digit * left_number, digit right_number, bool carry, int precision) 1046 { 1047 while (precision--) { 1048 digit term = *left_number + right_number; 1049 digit final = term + carry; 1050 carry = (term < *left_number || (carry && final == 0)); 1051 1052 right_number = 0; 1053 left_number++; 1054 *result++ = final; 1055 } 1056 return(carry); 1057 } 1058 1059 1060 /*********************************************************************************************** 1061 * XMP_Sub -- Subtract one MP number from another (with borrow). * 1062 * * 1063 * This routine will subtract one MP number from another. There is an optional borrow * 1064 * flag that can be specified. * 1065 * * 1066 * INPUT: result -- Pointer to the MP number that will hold the result. This pointer * 1067 * can be the same as the left_number or right_number parameters. * 1068 * * 1069 * left_number -- The left hand number (value will be subtracted from this). * 1070 * * 1071 * right_number-- The right hand number (the value to subtract from the left number) * 1072 * * 1073 * borrow -- The optional borrow flag. If this flag is true, the an extra one * 1074 * will be subtracted from the result. * 1075 * * 1076 * precision -- The precision of the MP numbers involved. * 1077 * * 1078 * OUTPUT: Returns with the borrow result flag. If the value is true, then an underflow * 1079 * occurred during subtraction. * 1080 * * 1081 * WARNINGS: All MP numbers must share the same precision. * 1082 * * 1083 * HISTORY: * 1084 * 07/01/1996 JLB : Created. * 1085 *=============================================================================================*/ 1086 bool XMP_Sub(digit * result, const digit * left_number, const digit * right_number, bool borrow, int precision) 1087 { 1088 const unsigned short * left_number_ptr = (const unsigned short *)left_number; 1089 const unsigned short * right_number_ptr = (const unsigned short *)right_number; 1090 unsigned short * result_ptr = (unsigned short *)result; 1091 1092 precision *= 2; 1093 while (precision--) { 1094 digit x = (digit) *left_number_ptr - (digit) *right_number_ptr - (digit) borrow; 1095 right_number_ptr++; 1096 left_number_ptr++; 1097 *result_ptr++ = (unsigned short)x; 1098 borrow = (((1L << 16) & x) != 0L); 1099 } 1100 return (borrow); 1101 } 1102 1103 1104 /*********************************************************************************************** 1105 * XMP_Sub_Int -- Subtract an integer from an MP number (with borrow). * 1106 * * 1107 * This will subtract an integer from the specified MP number. There is an optional borrow * 1108 * flag available. * 1109 * * 1110 * INPUT: result -- Pointer to the MP buffer that will hold the result. * 1111 * * 1112 * left_number -- Pointer to the MP number that will be subtracted FROM. * 1113 * * 1114 * right_number-- The integer to subtract from the left hand number. * 1115 * * 1116 * borrow -- The optional borrow flag. If this value is true, then an extra one * 1117 * will be subtracted from the result. * 1118 * * 1119 * precision -- The precision of the MP numbers involved. * 1120 * * 1121 * OUTPUT: Returns with the borrow flag of the result. If this value is true, then an * 1122 * underflow occurred during subtraction. * 1123 * * 1124 * WARNINGS: The precision must be identical between the MP numbers involved. * 1125 * * 1126 * HISTORY: * 1127 * 07/01/1996 JLB : Created. * 1128 *=============================================================================================*/ 1129 bool XMP_Sub_Int(digit * result, const digit * left_number, unsigned short right_number, bool borrow, int precision) 1130 { 1131 const unsigned short * left_number_ptr = (const unsigned short *)left_number; 1132 unsigned short * result_ptr = (unsigned short *)result; 1133 1134 precision *= 2; 1135 while (precision--) { 1136 digit x = (digit) *left_number_ptr - right_number - borrow; 1137 left_number_ptr++; 1138 *result_ptr++ = (unsigned short)x; 1139 borrow = (((1L << 16) & x) != 0L); 1140 1141 right_number = 0; 1142 } 1143 return (borrow); 1144 } 1145 1146 1147 /*********************************************************************************************** 1148 * XMP_Unsigned_Mult -- Multiply two unsigned MP numbers together. * 1149 * * 1150 * This routine will multiply two MP numbers together. The result will have the sum of the * 1151 * significance of the two. * 1152 * * 1153 * INPUT: prod -- Pointer to the product MP buffer that will hold the result. * 1154 * * 1155 * multiplicand-- Pointer to the multiplicand MP number. * 1156 * * 1157 * multiplier -- Pointer to the multiplier MP number. * 1158 * * 1159 * precision -- The precision of the MP numbers. * 1160 * * 1161 * OUTPUT: none * 1162 * * 1163 * WARNINGS: Be sure the product will fit within the precision of the result. * 1164 * * 1165 * HISTORY: * 1166 * 07/01/1996 JLB : Created. * 1167 *=============================================================================================*/ 1168 int XMP_Unsigned_Mult(digit * prod, const digit * multiplicand, const digit * multiplier, int precision) 1169 { 1170 XMP_Init(prod, 0, precision); 1171 1172 /* 1173 ** Multiplying by zero is always a zero product. 1174 */ 1175 if (XMP_Test_Eq_Int(multiplicand, 0, precision) || XMP_Test_Eq_Int(multiplier, 0, precision)) { 1176 return 0; 1177 } 1178 1179 int total_bit_count = XMP_Count_Bits(multiplier, precision); 1180 digit high_bit_mask = XMP_Bits_To_Mask(total_bit_count); 1181 int sub_precision = XMP_Bits_To_Digits(total_bit_count); 1182 if (!sub_precision) return(0); 1183 multiplier += sub_precision; 1184 1185 while (total_bit_count--) { 1186 XMP_Shift_Left_Bits(prod, 1, precision); 1187 1188 if ((*(multiplier-1)) & high_bit_mask) { 1189 XMP_Add(prod, prod, multiplicand, 0, precision); 1190 } 1191 1192 high_bit_mask >>= 1; 1193 if (!high_bit_mask) { 1194 high_bit_mask = UPPER_MOST_BIT; 1195 multiplier--; 1196 } 1197 1198 } 1199 return 0; 1200 } 1201 1202 1203 /*********************************************************************************************** 1204 * XMP_Unsigned_Mult_Int -- Multiply an MP number by a simple integer. * 1205 * * 1206 * This is a very fast multiply since the multiplier is just an integer integral. * 1207 * * 1208 * INPUT: prod -- Pointer to the product MP number. * 1209 * * 1210 * multiplicand-- Pointer to the MP number that is the multiplicand. * 1211 * * 1212 * multiplier -- The integral integer that is the multiplier. * 1213 * * 1214 * precision -- The precision of the MP numbers. * 1215 * * 1216 * OUTPUT: none * 1217 * * 1218 * WARNINGS: The multiplier must fit in a signed integer (although it isn't a signed value). * 1219 * * 1220 * HISTORY: * 1221 * 07/02/1996 JLB : Created. * 1222 *=============================================================================================*/ 1223 int XMP_Unsigned_Mult_Int(digit * prod, const digit * multiplicand, short multiplier, int precision) 1224 { 1225 const unsigned short * m2 = (const unsigned short *)multiplicand; 1226 unsigned short * pr = (unsigned short *)prod; 1227 unsigned long carry = 0; 1228 for (int i = 0; i < precision*2; ++i) { 1229 unsigned long p = (((unsigned long)multiplier) * *m2) + carry;; 1230 *pr = (unsigned short) p; 1231 carry = p >> 16; 1232 m2++; 1233 pr++; 1234 } 1235 1236 /* Add carry to the next higher word of product / dividend */ 1237 // *pr += (unsigned short)carry; 1238 return(0); 1239 } 1240 1241 1242 /*********************************************************************************************** 1243 * XMP_Signed_Mult_Int -- Multiply an MP number by a signed simple integer. * 1244 * * 1245 * This will multiply the specified integer with the MP number. It is a much faster * 1246 * multiply than when multiplying two MP numbers. * 1247 * * 1248 * INPUT: prod -- Pointer to the product MP number. * 1249 * * 1250 * multiplicand-- Pointer to the MP number that serves as the multiplicand. * 1251 * * 1252 * multiplier -- The simple integral integer used as the multiplier. * 1253 * * 1254 * precision -- The precision of the MP numbers involved. * 1255 * * 1256 * OUTPUT: none * 1257 * * 1258 * WARNINGS: The multiplier must fist within a signed short integer. * 1259 * * 1260 * HISTORY: * 1261 * 07/02/1996 JLB : Created. * 1262 *=============================================================================================*/ 1263 int XMP_Signed_Mult_Int(digit * prod, const digit * multiplicand, signed short multiplier, int precision) 1264 { 1265 if (XMP_Is_Negative(multiplicand, precision)) { 1266 digit abs_multiplicand[MAX_UNIT_PRECISION]; 1267 XMP_Move(abs_multiplicand, multiplicand, precision); 1268 XMP_Neg(abs_multiplicand, precision); 1269 1270 if (multiplier < 0) { 1271 multiplier = (signed short)-multiplier; 1272 1273 XMP_Unsigned_Mult_Int(prod, abs_multiplicand, multiplier, precision); 1274 } else { 1275 XMP_Unsigned_Mult_Int(prod, abs_multiplicand, multiplier, precision); 1276 XMP_Neg(prod, precision); 1277 } 1278 } else { 1279 if (multiplier < 0) { 1280 multiplier = (signed short)-multiplier; 1281 1282 XMP_Unsigned_Mult_Int(prod, multiplicand, multiplier, precision); 1283 XMP_Neg(prod, precision); 1284 } else { 1285 XMP_Unsigned_Mult_Int(prod, multiplicand, multiplier, precision); 1286 } 1287 } 1288 return(0); 1289 } 1290 1291 1292 /*********************************************************************************************** 1293 * XMP_Signed_Mult -- A signed multiply between two MP numbers. * 1294 * * 1295 * This routine will perform a multiply between two signed MP numbers. * 1296 * * 1297 * INPUT: prod -- Pointer to the product MP number buffer. * 1298 * * 1299 * multiplicand-- Pointer to the multiplicand MP number. * 1300 * * 1301 * multiplier -- Pointer to the multiplier MP number. * 1302 * * 1303 * precision -- The precision of the MP numbers involved. * 1304 * * 1305 * OUTPUT: none * 1306 * * 1307 * WARNINGS: This is not a very fast routine. * 1308 * * 1309 * HISTORY: * 1310 * 07/02/1996 JLB : Created. * 1311 *=============================================================================================*/ 1312 int XMP_Signed_Mult(digit * prod, const digit * multiplicand, const digit * multiplier, int precision) 1313 { 1314 if (XMP_Is_Negative(multiplicand, precision)) { 1315 digit abs_multiplicand[MAX_UNIT_PRECISION]; 1316 XMP_Move(abs_multiplicand, multiplicand, precision); 1317 XMP_Neg(abs_multiplicand, precision); 1318 1319 if (XMP_Is_Negative(multiplier, precision)) { 1320 digit abs_multiplier[MAX_UNIT_PRECISION]; 1321 XMP_Move(abs_multiplier, multiplier, precision); 1322 XMP_Neg(abs_multiplier, precision); 1323 1324 XMP_Unsigned_Mult(prod, abs_multiplicand, abs_multiplier, precision); 1325 } else { 1326 XMP_Unsigned_Mult(prod, abs_multiplicand, multiplier, precision); 1327 XMP_Neg(prod, precision); 1328 } 1329 } else { 1330 if (XMP_Is_Negative(multiplier, precision)) { 1331 digit abs_multiplier[MAX_UNIT_PRECISION]; 1332 XMP_Move(abs_multiplier, multiplier, precision); 1333 XMP_Neg(abs_multiplier, precision); 1334 1335 XMP_Unsigned_Mult(prod, multiplicand, abs_multiplier, precision); 1336 XMP_Neg(prod, precision); 1337 } else { 1338 XMP_Unsigned_Mult(prod, multiplicand, multiplier, precision); 1339 } 1340 } 1341 return(0); 1342 } 1343 1344 1345 /*********************************************************************************************** 1346 * XMP_Unsigned_Div_Int -- Perform a short integer divide into an MP number. * 1347 * * 1348 * This routine performs a fast divide of the specified MP dividend by a simple * 1349 * short integer. The division is an UNSIGNED division however. * 1350 * * 1351 * INPUT: quotient -- Pointer to the MP number buffer where the quotient will go. * 1352 * * 1353 * dividend -- Pointer to the MP number that serves as the dividend. * 1354 * * 1355 * divisor -- The simple signed short integer that serves as the divisor. * 1356 * * 1357 * precision -- The precision that is used by the MP numbers involved. * 1358 * * 1359 * OUTPUT: Returns with the remainder of the division. * 1360 * * 1361 * WARNINGS: This is an UNSIGNED divide even. * 1362 * * 1363 * HISTORY: * 1364 * 07/02/1996 JLB : Created. * 1365 *=============================================================================================*/ 1366 unsigned short XMP_Unsigned_Div_Int(digit * quotient, digit const * dividend, unsigned short divisor, int precision) 1367 { 1368 if (!divisor) return 0; /* zero divisor means divide error */ 1369 1370 unsigned short remainder = 0; 1371 1372 XMP_Init(quotient, 0, precision); 1373 1374 int total_bit_count = XMP_Count_Bits(dividend, precision); 1375 int digit_precision = XMP_Bits_To_Digits(total_bit_count); 1376 digit const * dividend_ptr = dividend + (digit_precision-1); 1377 1378 if (!digit_precision) return(0); 1379 1380 digit high_bit_mask = XMP_Bits_To_Mask(total_bit_count); 1381 digit * quotient_ptr = quotient + (digit_precision-1); 1382 1383 while (total_bit_count--) { 1384 remainder <<= 1; 1385 1386 if ((*dividend_ptr) & high_bit_mask) remainder++; 1387 1388 if (remainder >= divisor) { 1389 remainder -= divisor; 1390 *quotient_ptr |= high_bit_mask; 1391 } 1392 1393 high_bit_mask >>= 1; 1394 if (!high_bit_mask) { 1395 high_bit_mask = UPPER_MOST_BIT; 1396 --dividend_ptr; 1397 --quotient_ptr; 1398 } 1399 } 1400 1401 return(remainder); 1402 } 1403 1404 1405 /*********************************************************************************************** 1406 * XMP_Unsigned_Div -- Unsigned divide of one MP number into another. * 1407 * * 1408 * This will perform the (dog slow) divide of one MP number into another. Because of the * 1409 * slowness of this routine, both the quotient and the remainder are available as a * 1410 * result of the operation. * 1411 * * 1412 * INPUT: remainder -- Pointer to the MP buffer that will hold the remainder of the divide.* 1413 * * 1414 * quotient -- Pointer to the MP buffer that will hold the quotient of the divide. * 1415 * * 1416 * dividend -- The MP dividend (numerator) number. * 1417 * * 1418 * divisor -- The MP divisor (denominator) number. * 1419 * * 1420 * precision -- The precision of the MP numbers involved. * 1421 * * 1422 * OUTPUT: none * 1423 * * 1424 * WARNINGS: This is very slow. * 1425 * * 1426 * HISTORY: * 1427 * 07/02/1996 JLB : Created. * 1428 *=============================================================================================*/ 1429 int XMP_Unsigned_Div(digit * remainder, digit * quotient, digit const * dividend, digit const * divisor, int precision) 1430 { 1431 // check for divide by zero. 1432 if (XMP_Test_Eq_Int(divisor, 0, precision)) return(-1); 1433 1434 XMP_Init(remainder, 0, precision); 1435 XMP_Init(quotient, 0, precision); 1436 1437 int total_bit_count = XMP_Count_Bits(dividend, precision); 1438 int digit_precision = XMP_Bits_To_Digits(total_bit_count); 1439 if (!digit_precision) return(0); 1440 1441 digit const * dividend_ptr = dividend + (digit_precision-1); 1442 digit * quotient_ptr = quotient + (digit_precision-1); 1443 1444 digit high_bit_mask = XMP_Bits_To_Mask(total_bit_count); 1445 while (total_bit_count--) { 1446 XMP_Shift_Left_Bits(remainder, 1, precision); 1447 1448 if (((*dividend_ptr) & high_bit_mask) != 0) { 1449 XMP_Inc(remainder, precision); 1450 } 1451 1452 if (XMP_Compare(remainder, divisor, precision) >= 0) { 1453 XMP_Sub(remainder, remainder, divisor, 0, precision); 1454 *quotient_ptr |= high_bit_mask; 1455 } 1456 1457 high_bit_mask >>= 1; 1458 if (!high_bit_mask) { 1459 high_bit_mask = UPPER_MOST_BIT; 1460 dividend_ptr--; 1461 quotient_ptr--; 1462 } 1463 1464 } 1465 return 0; 1466 } 1467 1468 1469 /*********************************************************************************************** 1470 * XMP_Signed_Div -- Signed divide of one MP number into another. * 1471 * * 1472 * This will perform a signed divide (very very slow) of one MP number into another. * 1473 * Because of the slow nature of this routine, both the quotient and the remainder are * 1474 * available as results. * 1475 * * 1476 * INPUT: remainder -- Pointer to the buffer that will hold the remainder of the divide. * 1477 * * 1478 * quotient -- Pointer to the buffer that will hold the quotient of the divide. * 1479 * * 1480 * dividend -- The dividend (numerator) MP number. * 1481 * * 1482 * divisor -- The divisor (denominator) MP number. * 1483 * * 1484 * precision -- The precision of the MP numbers involved. * 1485 * * 1486 * OUTPUT: none * 1487 * * 1488 * WARNINGS: This is very very slow. * 1489 * * 1490 * HISTORY: * 1491 * 07/02/1996 JLB : Created. * 1492 *=============================================================================================*/ 1493 void XMP_Signed_Div(digit * remainder, digit * quotient, digit const * dividend, digit const * divisor, int precision) 1494 { 1495 bool negative = false; 1496 1497 digit scratch_dividend[MAX_UNIT_PRECISION]; 1498 XMP_Move(scratch_dividend, dividend, precision); 1499 1500 digit scratch_divisor[MAX_UNIT_PRECISION]; 1501 XMP_Move(scratch_divisor, divisor, precision); 1502 1503 if (XMP_Is_Negative(scratch_dividend, precision)) { 1504 XMP_Neg(scratch_dividend, precision); 1505 negative = !negative; 1506 } 1507 1508 if (XMP_Is_Negative(scratch_divisor, precision)) { 1509 XMP_Neg(scratch_divisor, precision); 1510 negative = !negative; 1511 } 1512 1513 XMP_Unsigned_Div(remainder, quotient, scratch_dividend, scratch_divisor, precision); 1514 1515 if (negative) { 1516 XMP_Neg(quotient, precision); 1517 if (!XMP_Test_Eq_Int(remainder, 0, precision)) { 1518 XMP_Dec(quotient, precision); 1519 XMP_Neg(remainder, precision); 1520 XMP_Add(remainder, remainder, scratch_divisor, 0, precision); 1521 } 1522 } 1523 } 1524 1525 1526 /*********************************************************************************************** 1527 * XMP_Inverse_A_Mod_B -- Inverts and performs modulus on an MP number. * 1528 * * 1529 * This is a utility routine that will perform an inverse on the MP number and then * 1530 * perform a modulus of that number by another MP number. There are some algorithms that * 1531 * require this process. * 1532 * * 1533 * INPUT: result -- Pointer to the MP buffer that will hold the result. * 1534 * * 1535 * number -- The MP number that will be inverted then modulo-ized. * 1536 * * 1537 * modulus -- The MP number to modulus the first number by. * 1538 * * 1539 * precision -- The precision of the MP numbers involved. * 1540 * * 1541 * OUTPUT: none * 1542 * * 1543 * WARNINGS: none * 1544 * * 1545 * HISTORY: * 1546 * 07/02/1996 JLB : Created. * 1547 *=============================================================================================*/ 1548 void XMP_Inverse_A_Mod_B(digit * result, digit const * number, digit const * modulus, int precision) 1549 { 1550 digit g[3][MAX_UNIT_PRECISION]; 1551 XMP_Move(g[0], modulus, precision); 1552 XMP_Move(g[1], number, precision); 1553 1554 digit v[3][MAX_UNIT_PRECISION]; 1555 XMP_Init(v[0], 0, precision); 1556 XMP_Init(v[1], 1, precision); 1557 1558 digit y[MAX_UNIT_PRECISION]; 1559 1560 int i; 1561 for (i = 1; !XMP_Test_Eq_Int(g[i%3], 0, precision); i++) { 1562 XMP_Unsigned_Div(g[(i+1)%3], y, g[(i-1)%3], g[i%3], precision); 1563 1564 XMP_Unsigned_Mult(result, v[i%3], y, precision); 1565 XMP_Sub(v[(i+1)%3], v[(i-1)%3], result, 0, precision); 1566 } 1567 1568 if (XMP_Is_Negative(v[(i-1)%3], precision)) { 1569 XMP_Add(v[(i-1)%3], v[(i-1)%3], modulus, 0, precision); 1570 } 1571 1572 XMP_Move(result, v[(i-1)%3], precision); 1573 } 1574 1575 1576 /*********************************************************************************************** 1577 * XMP_Reciprocal -- Compute the reciprocal (inverse) of the MP number. * 1578 * * 1579 * Use this routine to determine the inverse of the specified MP number. The inverse is * 1580 * defined as 1/number. * 1581 * * 1582 * INPUT: result -- Pointer to the result MP number buffer. * 1583 * * 1584 * number -- The number to be inverted. * 1585 * * 1586 * precision-- The precision of the MP number. * 1587 * * 1588 * OUTPUT: none * 1589 * * 1590 * WARNINGS: none * 1591 * * 1592 * HISTORY: * 1593 * 07/02/1996 JLB : Created. * 1594 *=============================================================================================*/ 1595 int XMP_Reciprocal(digit * quotient, const digit * divisor, int precision) 1596 { 1597 digit remainder[MAX_UNIT_PRECISION]; 1598 1599 if (XMP_Test_Eq_Int(divisor, 0, precision)) return -1; /* zero divisor means divide error */ 1600 1601 XMP_Init(remainder, 0, precision); 1602 XMP_Init(quotient, 0, precision); 1603 1604 /* normalize and compute number of bits in quotient first */ 1605 unsigned total_bit_count = XMP_Count_Bits(divisor, precision); 1606 digit high_bit_mask = XMP_Bits_To_Mask(total_bit_count + 1); /* bitmask within a single digit */ 1607 int sub_precision = XMP_Bits_To_Digits(total_bit_count + 1); 1608 1609 XMP_Set_Bit(remainder, total_bit_count - 1); 1610 1611 /* rescale quotient to precision of divisor bits */ 1612 quotient += sub_precision-1; 1613 1614 while (total_bit_count--) { 1615 XMP_Shift_Left_Bits(remainder, 1, precision); 1616 if (XMP_Compare(remainder, divisor, precision) >= 0) { 1617 XMP_Sub(remainder, remainder, divisor, 0, precision); 1618 *quotient |= high_bit_mask; 1619 } 1620 1621 high_bit_mask >>= 1; 1622 if (!high_bit_mask) { 1623 high_bit_mask = UPPER_MOST_BIT; 1624 quotient--; 1625 } 1626 } 1627 1628 XMP_Init(remainder, 0, precision); 1629 return 0; 1630 } 1631 1632 1633 /*********************************************************************************************** 1634 * XMP_Decode_ASCII -- Convert ASCII into an MP number. * 1635 * * 1636 * This routine will convert a supplied ASCII string into an MP number. * 1637 * * 1638 * INPUT: str -- Pointer to the ASCII string that will be converted. * 1639 * * 1640 * mpn -- Pointer to the MP number buffer that will be initialized. * 1641 * * 1642 * precision -- The precision of the MP number. * 1643 * * 1644 * OUTPUT: none * 1645 * * 1646 * WARNINGS: none * 1647 * * 1648 * HISTORY: * 1649 * 07/02/1996 JLB : Created. * 1650 *=============================================================================================*/ 1651 void XMP_Decode_ASCII(char const * str, digit * mpn, int precision) 1652 { 1653 /* 1654 ** Initialize the multiprecision number to zero. From this point 1655 ** onward, this object can be manipulated as a regular number. 1656 ** This is, in fact, what is done as the ascii string is parsed 1657 ** into a working number. 1658 */ 1659 XMP_Init(mpn, 0, precision); 1660 1661 /* 1662 ** No string or zero length is considered '0'. 1663 */ 1664 if (!str) return; 1665 int i = strlen(str); 1666 if (i == 0) return; 1667 1668 unsigned short radix; /* base 2-16 */ 1669 switch (toupper(str[i-1])) { /* classify radix select suffix character */ 1670 case '.': 1671 radix = 10; 1672 break; 1673 1674 case 'H': 1675 radix = 16; 1676 break; 1677 1678 case 'O': 1679 radix = 8; 1680 break; 1681 1682 case 'B': /* caution! 'b' is a hex digit! */ 1683 radix = 2; 1684 break; 1685 1686 default: 1687 radix = 10; 1688 break; 1689 } 1690 1691 bool minus = (*str == '-'); 1692 if (minus) str++; 1693 1694 digit c; 1695 while ((c = (unsigned char)*str++) != 0) { 1696 if (c == ',') continue; /* allow commas in number */ 1697 1698 /* 1699 ** If not a hexadecimal (highest base) digit then it is 1700 ** clearly the end of the processable string. Bail out 1701 ** of the scan loop. 1702 */ 1703 if (!isxdigit((char)c)) break; 1704 1705 /* 1706 ** Convert the character into an integer number 0 through 15. 1707 */ 1708 if (isdigit((char)c)) { 1709 c -= '0'; 1710 } else { 1711 c = (unsigned char)(toupper((char)c) - 'A') + 10; 1712 } 1713 1714 /* 1715 ** If the integer digit is greater than the radix, then we 1716 ** know that further processing should stop. This is the 1717 ** end of the number string. 1718 */ 1719 if (c >= radix) break; /* scan terminated by any non-digit */ 1720 1721 1722 XMP_Unsigned_Mult_Int(mpn, mpn, radix, precision); 1723 XMP_Add_Int(mpn, mpn, c, 0, precision); 1724 } 1725 if (minus) { 1726 XMP_Neg(mpn, precision); 1727 } 1728 } 1729 1730 1731 /*********************************************************************************************** 1732 * XMP_Hybrid_Mul -- Special hybrid short multiply (with carry). * 1733 * * 1734 * Multiply the single-word multiplier times the multiprecision integer * 1735 * in multiplicand, accumulating result in prod. The resulting * 1736 * multiprecision prod will be 1 word longer than the multiplicand. * 1737 * multiplicand is double precision words long. We add into prod, so caller * 1738 * should zero it out first. For best results, this time-critical * 1739 * function should be implemented in assembly. * 1740 * NOTE: Unlike other functions in the multiprecision arithmetic * 1741 * library, both multiplicand and prod are pointing at the LSB, * 1742 * regardless of byte order of the machine. On an 80x86, this makes * 1743 * no difference. But if this assembly function is implemented * 1744 * on a 680x0, it becomes important. * 1745 * * 1746 * Note that this has been modified from the previous version to allow * 1747 * better support for Smith's modmult: * 1748 * The final carry bit is added to the existing product * 1749 * array, rather than simply stored. * 1750 * * 1751 * INPUT: prod -- Pointer to the product MP number buffer. * 1752 * * 1753 * multiplicand -- Pointer to the multiplicand MP number. * 1754 * * 1755 * multiplier -- The short integer used as the multiplier. * 1756 * * 1757 * precision -- The precision of the MP number used. * 1758 * * 1759 * OUTPUT: none * 1760 * * 1761 * WARNINGS: The carry (if any) is added into the integer one beyond the end of the * 1762 * product buffer. * 1763 * * 1764 * HISTORY: * 1765 * 07/02/1996 JLB : Created. * 1766 *=============================================================================================*/ 1767 void XMP_Hybrid_Mul(unsigned short * prod, unsigned short * multiplicand, unsigned short multiplier, int precision) 1768 { 1769 unsigned long carry = 0; 1770 for (int i = 0; i < precision; ++i) { 1771 unsigned long p = (unsigned long)multiplier * *multiplicand++; 1772 p += *prod + carry; 1773 *prod++ = (unsigned short) p; 1774 carry = p >> 16; 1775 } 1776 1777 /* Add carry to the next higher word of product / dividend */ 1778 *prod += (unsigned short) carry; 1779 } 1780 1781 1782 /*********************************************************************************************** 1783 * XMP_Double_Mul -- Double precision MP multiply. * 1784 * * 1785 * This will perform a double precision multiply of MP numbers. This means that the product * 1786 * will be twice the precision of the components. * 1787 * * 1788 * INPUT: prod -- Pointer to the result buffer. This buffer must be able to hold * 1789 * double the precision specified. * 1790 * * 1791 * multiplicand-- Pointer to the multiplicand MP number. * 1792 * * 1793 * multiplier -- Pointer to the multiplier number. * 1794 * * 1795 * precision -- The precision of the two component MP numbers. * 1796 * * 1797 * OUTPUT: none * 1798 * * 1799 * WARNINGS: Be sure the product buffer can hold a double precision number. * 1800 * * 1801 * HISTORY: * 1802 * 07/02/1996 JLB : Created. * 1803 *=============================================================================================*/ 1804 void XMP_Double_Mul(digit * prod, const digit * multiplicand, const digit * multiplier, int precision) 1805 { 1806 /* 1807 ** Clear out the double precision product buffer. 1808 */ 1809 XMP_Init(prod, 0, precision*2); 1810 1811 const unsigned short * multiplier_ptr = (const unsigned short *) multiplier; 1812 unsigned short * product_ptr = (unsigned short *) prod; 1813 1814 // Multiply multiplicand by each word in multiplier, accumulating prod. 1815 for (int i = 0; i < precision*2; ++i) { 1816 XMP_Hybrid_Mul(product_ptr++, (unsigned short *)multiplicand, *multiplier_ptr++, precision*2); 1817 } 1818 } 1819 1820 1821 1822 static int _modulus_shift; // number of bits for recip scaling 1823 static unsigned short _reciprical_high_digit; // MSdigit of scaled recip 1824 static unsigned short _reciprical_low_digit; // LSdigit of scaled recip 1825 1826 static int _modulus_sub_precision; // length of modulus in MULTUNITs 1827 static int _modulus_bit_count; // number of modulus significant bits 1828 static digit _scratch_modulus[MAX_UNIT_PRECISION]; // modulus 1829 1830 // The double precision modulus staging buffer. 1831 static digit _double_staging_number[MAX_UNIT_PRECISION * 2 + 2]; 1832 1833 // most significant digits of modulus. 1834 static digit _mod_quotient[4]; 1835 static digit _mod_divisor[4]; 1836 1837 1838 /*********************************************************************************************** 1839 * XMP_Prepare_Modulus -- Prepare globals for modulus operation. * 1840 * * 1841 * Calculate the reciprocal of modulus with a precision of two MULTUNITs. * 1842 * Assumes that precision has already been adjusted to the * 1843 * size of the modulus, plus SLOP_BITS. * 1844 * * 1845 * Note: This routine was designed to work with large values and * 1846 * doesn't have the necessary testing or handling to work with a * 1847 * modulus having less than three significant digits. For such cases, * 1848 * the separate multiply and modulus routines can be used. * 1849 * * 1850 * INPUT: modulus -- Pointer to the modulus number. * 1851 * * 1852 * precision-- The precision of the modulus number. * 1853 * * 1854 * OUTPUT: none * 1855 * * 1856 * WARNINGS: none * 1857 * * 1858 * HISTORY: * 1859 * 07/02/1996 JLB : Created. * 1860 *=============================================================================================*/ 1861 int XMP_Prepare_Modulus(const digit * n_modulus, int precision) 1862 { 1863 XMP_Move(_scratch_modulus, n_modulus, precision); 1864 1865 _modulus_bit_count = XMP_Count_Bits(_scratch_modulus, precision); 1866 _modulus_sub_precision = (_modulus_bit_count + 16 - 1) / 16; 1867 1868 /* 1869 ** Keep 2*16 bits in _mod_divisor. 1870 ** This will (normally) result in a reciprocal of 2*16+1 bits. 1871 */ 1872 int sub_precision = XMP_Significance(_scratch_modulus, precision); // significant digits in modulus 1873 XMP_Move(_mod_divisor, &_scratch_modulus[sub_precision-2], 2); 1874 _modulus_shift = XMP_Count_Bits(_mod_divisor, 2) - 2 * 16; 1875 XMP_Shift_Right_Bits(_mod_divisor, _modulus_shift, 2); 1876 1877 XMP_Reciprocal(_mod_quotient, _mod_divisor, 2); 1878 XMP_Shift_Right_Bits(_mod_quotient, 1, 2); 1879 1880 /* Reduce to: 0 < _modulus_shift <= 16 */ 1881 _modulus_shift = ((_modulus_shift + (16 - 1)) % 16) + 1; 1882 1883 /* round up */ 1884 XMP_Inc(_mod_quotient, 2); 1885 if (XMP_Count_Bits(_mod_quotient, 2) > 2 * 16) { 1886 XMP_Shift_Right_Bits(_mod_quotient, 1, 2); 1887 _modulus_shift--; /* now 0 <= _modulus_shift <= 16 */ 1888 } 1889 unsigned short * mpm = (unsigned short *) _mod_quotient; 1890 _reciprical_low_digit = *mpm++; 1891 _reciprical_high_digit = *mpm; 1892 1893 return 0; 1894 } 1895 1896 1897 /*********************************************************************************************** 1898 * XMP_Mod_Mult -- Perform a multiply - modulus operation. * 1899 * * 1900 * This routine will combine a multiply and a modulus operation. This takes advantage of * 1901 * a tremendous speed advantage possible if these two processes are combined rather than * 1902 * being performed separately. * 1903 * * 1904 * INPUT: prod -- Pointer to the MP buffer that will hold the result. * 1905 * * 1906 * multiplicand-- The number to multiply. * 1907 * * 1908 * multiplier -- The number to multiply by. * 1909 * * 1910 * precision -- The precision of the MP numbers involved. * 1911 * * 1912 * OUTPUT: none * 1913 * * 1914 * WARNINGS: The modulus must already have been prepared by the routine XMP_Prepare_Modulus. * 1915 * * 1916 * HISTORY: * 1917 * 07/02/1996 JLB : Created. * 1918 *=============================================================================================*/ 1919 int XMP_Mod_Mult(digit * prod, const digit * multiplicand, const digit * multiplier, int precision) 1920 { 1921 XMP_Double_Mul(_double_staging_number, multiplicand, multiplier, precision); 1922 1923 int double_precision = precision * 2 + 1; 1924 1925 _double_staging_number[double_precision - 1] = 0; /* leading 0 digit */ 1926 1927 /* 1928 ** We now start working with MULTUNITs. 1929 ** Determine the most significant MULTUNIT of the product so we don't 1930 ** have to process leading zeros in our divide loop. 1931 */ 1932 int dmi = XMP_Significance(_double_staging_number, double_precision) * 2; // number of significant MULTUNITs in product 1933 1934 if (dmi >= _modulus_sub_precision) { 1935 1936 /* Make dividend negative. This allows the use of mp_single_mul to 1937 ** "subtract" the product of the modulus and the trial divisor 1938 ** by actually adding to a negative dividend. 1939 ** The one's complement of the dividend is used, since it causes 1940 ** a zero value to be represented as all ones. This facilitates 1941 ** testing the result for possible overflow, since a sign bit 1942 ** indicates that no adjustment is necessary, and we should not 1943 ** attempt to adjust if the result of the addition is zero. 1944 */ 1945 XMP_Inc(_double_staging_number, double_precision); 1946 XMP_Neg(_double_staging_number, double_precision); 1947 1948 int nqd = dmi + 1 - _modulus_sub_precision; // number of quotient digits remaining to be generated 1949 1950 /* Set msb, lsb, and normal ptrs of dividend */ 1951 unsigned short * dmph = ((unsigned short *)_double_staging_number) + dmi + 1; // points to one higher than precision would indicate 1952 unsigned short * dmpl = dmph - _modulus_sub_precision; 1953 1954 /* 1955 ** Divide loop. 1956 ** Each iteration computes the next quotient MULTUNIT digit, then 1957 ** multiplies the divisor (modulus) by the quotient digit and adds 1958 ** it to the one's complement of the dividend (equivalent to 1959 ** subtracting). If the product was greater than the remaining dividend, 1960 ** we get a non-negative result, in which case we subtract off the 1961 ** modulus to get the proper negative remainder. 1962 */ 1963 for (; nqd; nqd--) { 1964 --dmph; 1965 --dmpl; 1966 1967 unsigned short q = mp_quo_digit(dmph); // trial quotient digit 1968 if (q > 0) { 1969 XMP_Hybrid_Mul(dmpl, (unsigned short *)_scratch_modulus, q, precision*2); 1970 1971 /* Perform correction if q too large. 1972 ** This rarely occurs. 1973 */ 1974 if (!(*dmph & SEMI_UPPER_MOST_BIT)) { 1975 unsigned short * dmp = dmpl; 1976 if (XMP_Sub((unsigned long *)dmp, (unsigned long *)dmp, _scratch_modulus, false, precision)) { 1977 (*dmph)--; 1978 } 1979 } 1980 } 1981 } 1982 1983 /* d contains the one's complement of the remainder. */ 1984 XMP_Neg(_double_staging_number, precision); 1985 XMP_Dec(_double_staging_number, precision); 1986 } 1987 1988 XMP_Move(prod, _double_staging_number, precision); 1989 return (0); 1990 } 1991 1992 1993 /*********************************************************************************************** 1994 * XMP_Mod_Mult_Clear -- Remove temporary values from memory. * 1995 * * 1996 * Smith's mp_modmult function leaves some internal arrays in memory, * 1997 * so we have to call modmult_burn() at the end of mp_exponent_mod. * 1998 * This is so that no cryptographically sensitive data is left in memory * 1999 * after the program exits. * 2000 * * 2001 * INPUT: precision -- The precision of the numbers involved. * 2002 * * 2003 * OUTPUT: none * 2004 * * 2005 * WARNINGS: none * 2006 * * 2007 * HISTORY: * 2008 * 07/02/1996 JLB : Created. * 2009 *=============================================================================================*/ 2010 void XMP_Mod_Mult_Clear(int precision) 2011 { 2012 XMP_Init(_scratch_modulus, 0, precision); 2013 XMP_Init(_double_staging_number, 0, precision); 2014 XMP_Init(_mod_quotient, 0, ARRAY_SIZE(_mod_quotient)); 2015 XMP_Init(_mod_divisor, 0, ARRAY_SIZE(_mod_divisor)); 2016 _modulus_shift = _modulus_bit_count = 0; 2017 _reciprical_high_digit = _reciprical_low_digit = 0; 2018 _modulus_sub_precision = /*mutemp =*/ 0; 2019 } 2020 2021 2022 /* 2023 ** The function mp_quo_digit is the heart of Smith's modulo reduction, 2024 ** which uses a form of long division. It computes a trial quotient 2025 ** "digit" (MULTUNIT-sized digit) by multiplying the three most 2026 ** significant MULTUNITs of the dividend by the two most significant 2027 ** MULTUNITs of the reciprocal of the modulus. Note that this function 2028 ** requires that 16 * 2 <= sizeof(unsigned long). 2029 ** 2030 ** An important part of this technique is that the quotient never be 2031 ** too small, although it may occasionally be too large. This was 2032 ** done to eliminate the need to check and correct for a remainder 2033 ** exceeding the divisor. It is easier to check for a negative 2034 ** remainder. The following technique rarely needs correction for 2035 ** MULTUNITs of at least 16 bits. 2036 ** 2037 ** The following routine has two implementations: 2038 ** 2039 ** Parameter: dividend - points to the most significant MULTUNIT 2040 ** of the dividend. Note that dividend actually contains the 2041 ** one's complement of the actual dividend value (see comments for 2042 ** XMP_Mod_Mult). 2043 ** 2044 ** Return: the trial quotient digit resulting from dividing the first 2045 ** three MULTUNITs at dividend by the upper two MULTUNITs of the 2046 ** modulus. 2047 */ 2048 unsigned short mp_quo_digit(unsigned short * dividend) 2049 { 2050 unsigned long q, q0, q1, q2; 2051 2052 /* 2053 * Compute the least significant product group. 2054 * The last terms of q1 and q2 perform upward rounding, which is 2055 * needed to guarantee that the result not be too small. 2056 */ 2057 q1 = (dividend[-2] ^ SEMI_MASK) * (unsigned long) _reciprical_high_digit + _reciprical_high_digit; 2058 q2 = (dividend[-1] ^ SEMI_MASK) * (unsigned long) _reciprical_low_digit + (1L << 16); 2059 q0 = (q1 >> 1) + (q2 >> 1) + 1; 2060 2061 /* Compute the middle significant product group. */ 2062 q1 = (dividend[-1] ^ SEMI_MASK) * (unsigned long) _reciprical_high_digit; 2063 q2 = (dividend[0] ^ SEMI_MASK) * (unsigned long) _reciprical_low_digit; 2064 q = (q0 >> 16) + (q1 >> 1) + (q2 >> 1) + 1; 2065 2066 /* Compute the most significant term and add in the others */ 2067 q = (q >> (16 - 2)) + (((dividend[0] ^ SEMI_MASK) * (unsigned long) _reciprical_high_digit) << 1); 2068 q >>= _modulus_shift; 2069 2070 /* Prevent overflow and then wipe out the intermediate results. */ 2071 return (unsigned short) min(q, (unsigned long)(1L << 16) - 1); 2072 } 2073 2074 2075 /* 2076 ** Russian peasant combined exponentiation/modulo algorithm. 2077 ** Calls modmult instead of mult. 2078 ** Computes: expout = (expin**exponent) mod modulus 2079 ** WARNING: All the arguments must be less than the modulus! 2080 */ 2081 int xmp_exponent_mod(digit * expout, const digit * expin, const digit * exponent_ptr, const digit * modulus, int precision) 2082 { 2083 digit product[MAX_UNIT_PRECISION]; 2084 2085 XMP_Init(expout, 1, precision); 2086 if (XMP_Test_Eq_Int(exponent_ptr, 0, precision)) { 2087 if (XMP_Test_Eq_Int(expin, 0, precision)) { 2088 return -1; /* 0 to the 0th power means return error */ 2089 } 2090 return 0; /* otherwise, zero exponent means expout is 1 */ 2091 } 2092 2093 if (XMP_Test_Eq_Int(modulus, 0, precision)) { 2094 return -2; /* zero modulus means error */ 2095 } 2096 2097 if (XMP_Compare(expin, modulus, precision) >= 0) { 2098 return -3; /* if expin >= modulus, return error */ 2099 } 2100 2101 if (XMP_Compare(exponent_ptr, modulus, precision) >= 0) { 2102 return -4; /* if exponent >= modulus, return error */ 2103 } 2104 2105 /* set smallest optimum precision for this modulus */ 2106 int limited_precision = XMP_Significance(modulus, precision); 2107 2108 if (XMP_Prepare_Modulus(modulus, limited_precision)) { 2109 return -5; /* unstageable modulus (STEWART algorithm) */ 2110 } 2111 2112 /* normalize and compute number of bits in exponent first */ 2113 // int exp_precision = XMP_Significance(exponent_ptr, limited_precision); 2114 // if (!exp_precision) return(0); 2115 // int bits = XMP_Digits_To_Bits(exp_precision); 2116 // exponent_ptr += (exp_precision-1); 2117 // digit high_bit_mask = UPPER_MOST_BIT; 2118 // while (! ((*exponent_ptr) & high_bit_mask)) { 2119 // high_bit_mask >>= 1; 2120 // bits--; 2121 // } 2122 2123 int total_bit_count = XMP_Count_Bits(exponent_ptr, limited_precision); 2124 int sub_precision = XMP_Bits_To_Digits(total_bit_count); 2125 if (!sub_precision) return(0); 2126 digit high_bit_mask = XMP_Bits_To_Mask(total_bit_count); 2127 exponent_ptr += (sub_precision-1); 2128 2129 /* We can "optimize out" the first modsquare and modmult: */ 2130 total_bit_count--; /* We know for sure at this point that bits>0 */ 2131 2132 XMP_Move(expout, expin, limited_precision); 2133 2134 high_bit_mask >>= 1; 2135 if (!high_bit_mask) { 2136 high_bit_mask = UPPER_MOST_BIT; 2137 exponent_ptr--; 2138 } 2139 2140 while (total_bit_count--) { 2141 XMP_Mod_Mult(product, expout, expout, limited_precision); 2142 2143 if (((*exponent_ptr) & high_bit_mask)) { 2144 XMP_Mod_Mult(expout, product, expin, limited_precision); 2145 } else { 2146 XMP_Move(expout, product, limited_precision); 2147 } 2148 2149 high_bit_mask >>= 1; 2150 if (!high_bit_mask) { 2151 high_bit_mask = UPPER_MOST_BIT; 2152 exponent_ptr--; 2153 } 2154 2155 } 2156 2157 XMP_Init(product, 0, limited_precision); 2158 XMP_Mod_Mult_Clear(limited_precision); /* ask mp_modmult to also burn its own evidence */ 2159 2160 return 0; 2161 } 2162 2163 2164 /*********************************************************************************************** 2165 * memrev -- Reverse the byte order of the buffer specified. * 2166 * * 2167 * This routine will reverse the byte order in the buffer specified. * 2168 * * 2169 * INPUT: buffer -- Pointer to the buffer that will be reversed. * 2170 * * 2171 * length -- The length of the buffer. * 2172 * * 2173 * OUTPUT: none * 2174 * * 2175 * WARNINGS: none * 2176 * * 2177 * HISTORY: * 2178 * 07/02/1996 JLB : Created. * 2179 *=============================================================================================*/ 2180 void memrev(char * buffer, size_t length) 2181 { 2182 char * r2 = &(buffer[length - 1]); 2183 while (buffer < r2) { 2184 char b = *buffer; 2185 *buffer++ = *r2; 2186 *r2-- = b; 2187 } 2188 } 2189 2190 2191 int _USERENTRY pfunc(const void * pkey, const void * base) 2192 { 2193 if (*(unsigned short *)pkey < *(unsigned short *)base) return(-1); 2194 if (*(unsigned short *)pkey > *(unsigned short *)base) return(1); 2195 return(0); 2196 } 2197 2198 2199 /*********************************************************************************************** 2200 * XMP_Is_Small_Prime -- Determine if MP number is a small prime. * 2201 * * 2202 * This routine will compare the MP number against all known small prime numbers. It will * 2203 * return true if a match was found. * 2204 * * 2205 * INPUT: candidate -- Pointer to MP number that is to be tested. * 2206 * * 2207 * precision -- The precision of the MP number specified. * 2208 * * 2209 * OUTPUT: bool; Was the MP number a member of the small prime community? * 2210 * * 2211 * WARNINGS: none * 2212 * * 2213 * HISTORY: * 2214 * 07/02/1996 JLB : Created. * 2215 *=============================================================================================*/ 2216 bool XMP_Is_Small_Prime(const digit * candidate, int precision) 2217 { 2218 /* 2219 ** If the number is too large for comparison to the known small primes table, then 2220 ** bail immediately. 2221 */ 2222 if (XMP_Significance(candidate, precision) > 1) return(false); 2223 if (*candidate > primeTable[ARRAY_SIZE(primeTable)-1]) return false; 2224 2225 unsigned long * ptr = (unsigned long *)bsearch(&candidate, &primeTable[0], ARRAY_SIZE(primeTable), sizeof(primeTable[0]), pfunc); 2226 return(ptr != NULL); 2227 } 2228 2229 2230 /*********************************************************************************************** 2231 * XMP_Small_Divisors_Test -- Perform the small divisors test on an MP number. * 2232 * * 2233 * This test for primality will divide an MP number by the set of small primes. If any of * 2234 * these numbers divides evenly into the candidate number, then it is known that the * 2235 * candidate is NOT prime. * 2236 * * 2237 * INPUT: candidate -- Pointer to the MP number that is to be tested. * 2238 * * 2239 * precision -- The precision of the MP number/ * 2240 * * 2241 * OUTPUT: bool; Did the MP number pass the small divisors test? * 2242 * * 2243 * WARNINGS: If the MP number passes, it doesn't mean that it is prime, just that is hasn't * 2244 * yet been proven to be not prime. * 2245 * * 2246 * HISTORY: * 2247 * 07/02/1996 JLB : Created. * 2248 *=============================================================================================*/ 2249 bool XMP_Small_Divisors_Test(const digit * candidate, int precision) 2250 { 2251 digit quotient[MAX_UNIT_PRECISION]; 2252 2253 for (unsigned i = 0; i < ARRAY_SIZE(primeTable); i++) { 2254 if (XMP_Unsigned_Div_Int(quotient, candidate, primeTable[i], precision) == 0) return(false); 2255 } 2256 return(true); 2257 } 2258 2259 2260 /*********************************************************************************************** 2261 * XMP_Fermat_Test -- Performs Fermat's Little Theorem on an MP number. * 2262 * * 2263 * This is a more expensive but thorough test for primality. The aggressiveness of this * 2264 * test can be controlled by the number of rounds specified. Four rounds is usually * 2265 * sufficient. * 2266 * * 2267 * INPUT: candidate -- Pointer to the candidate MP number that is to be tested. * 2268 * * 2269 * rounds -- The number of rounds to test the MP number (keep it small). * 2270 * * 2271 * precision -- The precision of the MP number. * 2272 * * 2273 * OUTPUT: bool; Was the number not proven to be not prime. A FALSE means that it is not * 2274 * prime. A TRUE means that it might be prime. * 2275 * * 2276 * WARNINGS: This takes a bit of time. The time it takes is directly controlled by the * 2277 * number of rounds specified. Keep the number of rounds as small as possible. * 2278 * * 2279 * HISTORY: * 2280 * 07/02/1996 JLB : Created. * 2281 *=============================================================================================*/ 2282 bool XMP_Fermat_Test(const digit * candidate_prime, unsigned rounds, int precision) 2283 { 2284 assert(rounds < ARRAY_SIZE(primeTable)); 2285 2286 digit term[MAX_UNIT_PRECISION]; 2287 XMP_Move(term, candidate_prime, precision); 2288 XMP_Dec(term, precision); 2289 2290 for (unsigned i = 0; i < rounds; i++) { 2291 // if ((x**(p-1)) mod p) != 1, then p is not prime 2292 digit result[MAX_UNIT_PRECISION]; 2293 2294 digit small_prime[MAX_UNIT_PRECISION]; 2295 XMP_Init(small_prime, primeTable[i], precision); 2296 2297 xmp_exponent_mod(result, small_prime, term, candidate_prime, precision); 2298 2299 if (!XMP_Test_Eq_Int(result, 1, precision)) return(false); 2300 } 2301 return(true); 2302 } 2303 2304 2305 /*********************************************************************************************** 2306 * XMP_Rabin_Miller_Test -- Performs the Rabin Miller test for primality. * 2307 * * 2308 * This test for primality is even more expensive the Fermat's Little Theorem. It doesn't * 2309 * prove that a number is prime, but it can prove that it is not prime. * 2310 * * 2311 * INPUT: rng -- Reference to to a random number generator. * 2312 * * 2313 * candidate-- Pointer to the candidate MP number that is to be tested. * 2314 * * 2315 * rounds -- The number of test rounds to perform. * 2316 * * 2317 * precision-- The precision of the MP number specified. * 2318 * * 2319 * OUTPUT: bool; Was the number not proven to be not prime? A FALSE means that the number is * 2320 * not prime. A TRUE means that it might be. * 2321 * * 2322 * WARNINGS: This routine takes a long time. Use as few rounds as possible. * 2323 * * 2324 * HISTORY: * 2325 * 07/02/1996 JLB : Created. * 2326 *=============================================================================================*/ 2327 bool XMP_Rabin_Miller_Test(Straw & rng, digit const * w, int rounds, int precision) 2328 { 2329 digit wminus1[MAX_UNIT_PRECISION]; 2330 XMP_Sub_Int(wminus1, w, 1, 0, precision); 2331 2332 unsigned maxbitprecision = precision * sizeof(digit) * 8; 2333 unsigned a; 2334 for (a = 0; a < maxbitprecision; a++) { 2335 if (XMP_Test_Bit(wminus1, a)) { 2336 break; 2337 } 2338 } 2339 2340 digit m[MAX_UNIT_PRECISION]; 2341 XMP_Move(m, wminus1, precision); 2342 XMP_Shift_Right_Bits(wminus1, a, precision); 2343 2344 for (int i = 0; i < rounds; i++) { 2345 digit b[MAX_UNIT_PRECISION]; 2346 digit temp[MAX_UNIT_PRECISION]; 2347 XMP_Init(temp, 2, precision); 2348 XMP_Randomize(b, rng, temp, wminus1, precision); 2349 2350 digit z[MAX_UNIT_PRECISION]; 2351 xmp_exponent_mod(z, b, m, w, precision); 2352 2353 if (XMP_Test_Eq_Int(z, 1, precision) || XMP_Compare(z, wminus1, precision) == 0) { 2354 continue; // passes this round 2355 } 2356 2357 int j; 2358 for (j = 1; j < (int)a; j++) { 2359 digit t2[MAX_UNIT_PRECISION]; 2360 xmp_exponent_mod(t2, z, temp, w, precision); 2361 2362 if (XMP_Compare(t2, wminus1, precision) == 0) { 2363 break; // passed this round 2364 } 2365 if (XMP_Test_Eq_Int(z, 1, precision)) { 2366 return false; 2367 } 2368 } 2369 if (j == a) { 2370 return false; 2371 } 2372 } 2373 return true; 2374 } 2375 2376 2377 /*********************************************************************************************** 2378 * XMP_Randomize -- Generate a random MP number. * 2379 * * 2380 * This routine will generate a random MP number with the number of bits precision * 2381 * specified. This is the starting point for generating large random prime numbers. It is * 2382 * very important that the random number generated is truly random. * 2383 * * 2384 * INPUT: result -- Pointer to the buffer that will hold the MP number. * 2385 * * 2386 * rng -- Reference to a random number generator. * 2387 * * 2388 * total_bits-- The number of bits precision that the MP number must have. * 2389 * * 2390 * precision-- The precision of the MP number to be generated (maximum) * 2391 * * 2392 * OUTPUT: none * 2393 * * 2394 * WARNINGS: none * 2395 * * 2396 * HISTORY: * 2397 * 07/02/1996 JLB : Created. * 2398 *=============================================================================================*/ 2399 void XMP_Randomize(digit * result, Straw & rng, int total_bits, int precision) 2400 { 2401 assert(XMP_Bits_To_Digits(total_bits) <= MAX_UNIT_PRECISION); 2402 2403 total_bits = min(total_bits, precision * 32); 2404 2405 unsigned nbytes = total_bits/8 + 1; 2406 2407 XMP_Init(result, 0, precision); 2408 rng.Get(result, nbytes); 2409 2410 ((unsigned char *)result)[nbytes-1] &= (unsigned char)(~((~0) << (total_bits % 8))); 2411 } 2412 2413 2414 /*********************************************************************************************** 2415 * XMP_Randomize -- Generate a random MP number between the boundaries specified. * 2416 * * 2417 * This routine will generate a random MP number but it will be bounded by the minimum * 2418 * and maximum MP numbers specified. * 2419 * * 2420 * INPUT: result -- Pointer to the MP buffer that will hold the result. * 2421 * * 2422 * rng -- Reference to a random number generator to use. * 2423 * * 2424 * minval -- Minimum value allowed. * 2425 * * 2426 * maxval -- Maximum value allowed. * 2427 * * 2428 * precision -- The precision of the MP numbers involved. * 2429 * * 2430 * OUTPUT: none * 2431 * * 2432 * WARNINGS: none * 2433 * * 2434 * HISTORY: * 2435 * 07/02/1996 JLB : Created. * 2436 *=============================================================================================*/ 2437 void XMP_Randomize(digit * result, Straw & rng, digit const * minval, digit const * maxval, int precision) 2438 { 2439 digit range[MAX_UNIT_PRECISION]; 2440 XMP_Sub(range, maxval, minval, 0, precision); 2441 unsigned int bit_count = XMP_Count_Bits(range, precision); 2442 do { 2443 XMP_Randomize(result, rng, bit_count, precision); 2444 } while (XMP_Compare(result, range, precision) > 0); 2445 2446 XMP_Add(result, result, minval, 0, precision); 2447 } 2448 2449 2450 /*********************************************************************************************** 2451 * XMP_Is_Prime -- Determine if the specified MP number is prime. * 2452 * * 2453 * This routine will perform some checks to try and determine if the specified MP number * 2454 * is a prime number. The result of this test is not 100% conclusive, but it is pretty * 2455 * darn close. * 2456 * * 2457 * INPUT: prime -- Pointer to a candidate number to test for primality. * 2458 * * 2459 * precision-- The precision of the MP number specified. * 2460 * * 2461 * OUTPUT: bool; Was the number not proven to be not prime? If FALSE, then the number is * 2462 * not prime. If TRUE, then it might be. * 2463 * * 2464 * WARNINGS: This can take a very very very very very long time. Especially for the larger * 2465 * numbers. * 2466 * * 2467 * HISTORY: * 2468 * 07/02/1996 JLB : Created. * 2469 *=============================================================================================*/ 2470 bool XMP_Is_Prime(digit const * prime, int precision) 2471 { 2472 /* 2473 ** Even numbers are ALWAYS not prime. 2474 */ 2475 if (!(*prime & 0x01)) return(false); 2476 2477 /* 2478 ** Compare the prime number against the exhaustive list of prime 2479 ** numbers below 14 bits in size. If it finds a match, then 2480 ** the number is a known prime. 2481 */ 2482 if (XMP_Is_Small_Prime(prime, precision)) return(true); 2483 2484 /* 2485 ** Perform the small divisors test. This is not exhaustive, but 2486 ** will weed out a large percentage of non-prime numbers. 2487 */ 2488 if (!XMP_Small_Divisors_Test(prime, precision)) return(false); 2489 2490 /* 2491 ** Perform Fermat's Little Theorum on the candidate prime. Run 2492 ** the theorum for several rounds to ensure a high degree of 2493 ** confidence. 2494 */ 2495 if (!XMP_Fermat_Test(prime, 2, precision)) return(false); 2496 2497 /* 2498 ** If all of the above tests have not confirmed primality nor 2499 ** confirmed non-primality, presume that the number must be prime. 2500 */ 2501 return(true); 2502 } 2503 2504 2505 /* 2506 ** Complete list of all prime numbers that are less than 32719 (inclusive). 2507 */ 2508 unsigned short primeTable[3511] = { 2509 0x0002,0x0003,0x0005,0x0007,0x000B,0x000D,0x0011,0x0013,0x0017,0x001D,0x001F,0x0025,0x0029,0x002B,0x002F,0x0035, 2510 0x003B,0x003D,0x0043,0x0047,0x0049,0x004F,0x0053,0x0059,0x0061,0x0065,0x0067,0x006B,0x006D,0x0071,0x007F,0x0083, 2511 0x0089,0x008B,0x0095,0x0097,0x009D,0x00A3,0x00A7,0x00AD,0x00B3,0x00B5,0x00BF,0x00C1,0x00C5,0x00C7,0x00D3,0x00DF, 2512 0x00E3,0x00E5,0x00E9,0x00EF,0x00F1,0x00FB,0x0101,0x0107,0x010D,0x010F,0x0115,0x0119,0x011B,0x0125,0x0133,0x0137, 2513 0x0139,0x013D,0x014B,0x0151,0x015B,0x015D,0x0161,0x0167,0x016F,0x0175,0x017B,0x017F,0x0185,0x018D,0x0191,0x0199, 2514 0x01A3,0x01A5,0x01AF,0x01B1,0x01B7,0x01BB,0x01C1,0x01C9,0x01CD,0x01CF,0x01D3,0x01DF,0x01E7,0x01EB,0x01F3,0x01F7, 2515 0x01FD,0x0209,0x020B,0x021D,0x0223,0x022D,0x0233,0x0239,0x023B,0x0241,0x024B,0x0251,0x0257,0x0259,0x025F,0x0265, 2516 0x0269,0x026B,0x0277,0x0281,0x0283,0x0287,0x028D,0x0293,0x0295,0x02A1,0x02A5,0x02AB,0x02B3,0x02BD,0x02C5,0x02CF, 2517 0x02D7,0x02DD,0x02E3,0x02E7,0x02EF,0x02F5,0x02F9,0x0301,0x0305,0x0313,0x031D,0x0329,0x032B,0x0335,0x0337,0x033B, 2518 0x033D,0x0347,0x0355,0x0359,0x035B,0x035F,0x036D,0x0371,0x0373,0x0377,0x038B,0x038F,0x0397,0x03A1,0x03A9,0x03AD, 2519 0x03B3,0x03B9,0x03C7,0x03CB,0x03D1,0x03D7,0x03DF,0x03E5,0x03F1,0x03F5,0x03FB,0x03FD,0x0407,0x0409,0x040F,0x0419, 2520 0x041B,0x0425,0x0427,0x042D,0x043F,0x0443,0x0445,0x0449,0x044F,0x0455,0x045D,0x0463,0x0469,0x047F,0x0481,0x048B, 2521 0x0493,0x049D,0x04A3,0x04A9,0x04B1,0x04BD,0x04C1,0x04C7,0x04CD,0x04CF,0x04D5,0x04E1,0x04EB,0x04FD,0x04FF,0x0503, 2522 0x0509,0x050B,0x0511,0x0515,0x0517,0x051B,0x0527,0x0529,0x052F,0x0551,0x0557,0x055D,0x0565,0x0577,0x0581,0x058F, 2523 0x0593,0x0595,0x0599,0x059F,0x05A7,0x05AB,0x05AD,0x05B3,0x05BF,0x05C9,0x05CB,0x05CF,0x05D1,0x05D5,0x05DB,0x05E7, 2524 0x05F3,0x05FB,0x0607,0x060D,0x0611,0x0617,0x061F,0x0623,0x062B,0x062F,0x063D,0x0641,0x0647,0x0649,0x064D,0x0653, 2525 0x0655,0x065B,0x0665,0x0679,0x067F,0x0683,0x0685,0x069D,0x06A1,0x06A3,0x06AD,0x06B9,0x06BB,0x06C5,0x06CD,0x06D3, 2526 0x06D9,0x06DF,0x06F1,0x06F7,0x06FB,0x06FD,0x0709,0x0713,0x071F,0x0727,0x0737,0x0745,0x074B,0x074F,0x0751,0x0755, 2527 0x0757,0x0761,0x076D,0x0773,0x0779,0x078B,0x078D,0x079D,0x079F,0x07B5,0x07BB,0x07C3,0x07C9,0x07CD,0x07CF,0x07D3, 2528 0x07DB,0x07E1,0x07EB,0x07ED,0x07F7,0x0805,0x080F,0x0815,0x0821,0x0823,0x0827,0x0829,0x0833,0x083F,0x0841,0x0851, 2529 0x0853,0x0859,0x085D,0x085F,0x0869,0x0871,0x0883,0x089B,0x089F,0x08A5,0x08AD,0x08BD,0x08BF,0x08C3,0x08CB,0x08DB, 2530 0x08DD,0x08E1,0x08E9,0x08EF,0x08F5,0x08F9,0x0905,0x0907,0x091D,0x0923,0x0925,0x092B,0x092F,0x0935,0x0943,0x0949, 2531 0x094D,0x094F,0x0955,0x0959,0x095F,0x096B,0x0971,0x0977,0x0985,0x0989,0x098F,0x099B,0x09A3,0x09A9,0x09AD,0x09C7, 2532 0x09D9,0x09E3,0x09EB,0x09EF,0x09F5,0x09F7,0x09FD,0x0A13,0x0A1F,0x0A21,0x0A31,0x0A39,0x0A3D,0x0A49,0x0A57,0x0A61, 2533 0x0A63,0x0A67,0x0A6F,0x0A75,0x0A7B,0x0A7F,0x0A81,0x0A85,0x0A8B,0x0A93,0x0A97,0x0A99,0x0A9F,0x0AA9,0x0AAB,0x0AB5, 2534 0x0ABD,0x0AC1,0x0ACF,0x0AD9,0x0AE5,0x0AE7,0x0AED,0x0AF1,0x0AF3,0x0B03,0x0B11,0x0B15,0x0B1B,0x0B23,0x0B29,0x0B2D, 2535 0x0B3F,0x0B47,0x0B51,0x0B57,0x0B5D,0x0B65,0x0B6F,0x0B7B,0x0B89,0x0B8D,0x0B93,0x0B99,0x0B9B,0x0BB7,0x0BB9,0x0BC3, 2536 0x0BCB,0x0BCF,0x0BDD,0x0BE1,0x0BE9,0x0BF5,0x0BFB,0x0C07,0x0C0B,0x0C11,0x0C25,0x0C2F,0x0C31,0x0C41,0x0C5B,0x0C5F, 2537 0x0C61,0x0C6D,0x0C73,0x0C77,0x0C83,0x0C89,0x0C91,0x0C95,0x0C9D,0x0CB3,0x0CB5,0x0CB9,0x0CBB,0x0CC7,0x0CE3,0x0CE5, 2538 0x0CEB,0x0CF1,0x0CF7,0x0CFB,0x0D01,0x0D03,0x0D0F,0x0D13,0x0D1F,0x0D21,0x0D2B,0x0D2D,0x0D3D,0x0D3F,0x0D4F,0x0D55, 2539 0x0D69,0x0D79,0x0D81,0x0D85,0x0D87,0x0D8B,0x0D8D,0x0DA3,0x0DAB,0x0DB7,0x0DBD,0x0DC7,0x0DC9,0x0DCD,0x0DD3,0x0DD5, 2540 0x0DDB,0x0DE5,0x0DE7,0x0DF3,0x0DFD,0x0DFF,0x0E09,0x0E17,0x0E1D,0x0E21,0x0E27,0x0E2F,0x0E35,0x0E3B,0x0E4B,0x0E57, 2541 0x0E59,0x0E5D,0x0E6B,0x0E71,0x0E75,0x0E7D,0x0E87,0x0E8F,0x0E95,0x0E9B,0x0EB1,0x0EB7,0x0EB9,0x0EC3,0x0ED1,0x0ED5, 2542 0x0EDB,0x0EED,0x0EEF,0x0EF9,0x0F07,0x0F0B,0x0F0D,0x0F17,0x0F25,0x0F29,0x0F31,0x0F43,0x0F47,0x0F4D,0x0F4F,0x0F53, 2543 0x0F59,0x0F5B,0x0F67,0x0F6B,0x0F7F,0x0F95,0x0FA1,0x0FA3,0x0FA7,0x0FAD,0x0FB3,0x0FB5,0x0FBB,0x0FD1,0x0FD3,0x0FD9, 2544 0x0FE9,0x0FEF,0x0FFB,0x0FFD,0x1003,0x100F,0x101F,0x1021,0x1025,0x102B,0x1039,0x103D,0x103F,0x1051,0x1069,0x1073, 2545 0x1079,0x107B,0x1085,0x1087,0x1091,0x1093,0x109D,0x10A3,0x10A5,0x10AF,0x10B1,0x10BB,0x10C1,0x10C9,0x10E7,0x10F1, 2546 0x10F3,0x10FD,0x1105,0x110B,0x1115,0x1127,0x112D,0x1139,0x1145,0x1147,0x1159,0x115F,0x1163,0x1169,0x116F,0x1181, 2547 0x1183,0x118D,0x119B,0x11A1,0x11A5,0x11A7,0x11AB,0x11C3,0x11C5,0x11D1,0x11D7,0x11E7,0x11EF,0x11F5,0x11FB,0x120D, 2548 0x121D,0x121F,0x1223,0x1229,0x122B,0x1231,0x1237,0x1241,0x1247,0x1253,0x125F,0x1271,0x1273,0x1279,0x127D,0x128F, 2549 0x1297,0x12AF,0x12B3,0x12B5,0x12B9,0x12BF,0x12C1,0x12CD,0x12D1,0x12DF,0x12FD,0x1307,0x130D,0x1319,0x1327,0x132D, 2550 0x1337,0x1343,0x1345,0x1349,0x134F,0x1357,0x135D,0x1367,0x1369,0x136D,0x137B,0x1381,0x1387,0x138B,0x1391,0x1393, 2551 0x139D,0x139F,0x13AF,0x13BB,0x13C3,0x13D5,0x13D9,0x13DF,0x13EB,0x13ED,0x13F3,0x13F9,0x13FF,0x141B,0x1421,0x142F, 2552 0x1433,0x143B,0x1445,0x144D,0x1459,0x146B,0x146F,0x1471,0x1475,0x148D,0x1499,0x149F,0x14A1,0x14B1,0x14B7,0x14BD, 2553 0x14CB,0x14D5,0x14E3,0x14E7,0x1505,0x150B,0x1511,0x1517,0x151F,0x1525,0x1529,0x152B,0x1537,0x153D,0x1541,0x1543, 2554 0x1549,0x155F,0x1565,0x1567,0x156B,0x157D,0x157F,0x1583,0x158F,0x1591,0x1597,0x159B,0x15B5,0x15BB,0x15C1,0x15C5, 2555 0x15CD,0x15D7,0x15F7,0x1607,0x1609,0x160F,0x1613,0x1615,0x1619,0x161B,0x1625,0x1633,0x1639,0x163D,0x1645,0x164F, 2556 0x1655,0x1669,0x166D,0x166F,0x1675,0x1693,0x1697,0x169F,0x16A9,0x16AF,0x16B5,0x16BD,0x16C3,0x16CF,0x16D3,0x16D9, 2557 0x16DB,0x16E1,0x16E5,0x16EB,0x16ED,0x16F7,0x16F9,0x1709,0x170F,0x1723,0x1727,0x1733,0x1741,0x175D,0x1763,0x1777, 2558 0x177B,0x178D,0x1795,0x179B,0x179F,0x17A5,0x17B3,0x17B9,0x17BF,0x17C9,0x17CB,0x17D5,0x17E1,0x17E9,0x17F3,0x17F5, 2559 0x17FF,0x1807,0x1813,0x181D,0x1835,0x1837,0x183B,0x1843,0x1849,0x184D,0x1855,0x1867,0x1871,0x1877,0x187D,0x187F, 2560 0x1885,0x188F,0x189B,0x189D,0x18A7,0x18AD,0x18B3,0x18B9,0x18C1,0x18C7,0x18D1,0x18D7,0x18D9,0x18DF,0x18E5,0x18EB, 2561 0x18F5,0x18FD,0x1915,0x191B,0x1931,0x1933,0x1945,0x1949,0x1951,0x195B,0x1979,0x1981,0x1993,0x1997,0x1999,0x19A3, 2562 0x19A9,0x19AB,0x19B1,0x19B5,0x19C7,0x19CF,0x19DB,0x19ED,0x19FD,0x1A03,0x1A05,0x1A11,0x1A17,0x1A21,0x1A23,0x1A2D, 2563 0x1A2F,0x1A35,0x1A3F,0x1A4D,0x1A51,0x1A69,0x1A6B,0x1A7B,0x1A7D,0x1A87,0x1A89,0x1A93,0x1AA7,0x1AAB,0x1AAD,0x1AB1, 2564 0x1AB9,0x1AC9,0x1ACF,0x1AD5,0x1AD7,0x1AE3,0x1AF3,0x1AFB,0x1AFF,0x1B05,0x1B23,0x1B25,0x1B2F,0x1B31,0x1B37,0x1B3B, 2565 0x1B41,0x1B47,0x1B4F,0x1B55,0x1B59,0x1B65,0x1B6B,0x1B73,0x1B7F,0x1B83,0x1B91,0x1B9D,0x1BA7,0x1BBF,0x1BC5,0x1BD1, 2566 0x1BD7,0x1BD9,0x1BEF,0x1BF7,0x1C09,0x1C13,0x1C19,0x1C27,0x1C2B,0x1C2D,0x1C33,0x1C3D,0x1C45,0x1C4B,0x1C4F,0x1C55, 2567 0x1C73,0x1C81,0x1C8B,0x1C8D,0x1C99,0x1CA3,0x1CA5,0x1CB5,0x1CB7,0x1CC9,0x1CE1,0x1CF3,0x1CF9,0x1D09,0x1D1B,0x1D21, 2568 0x1D23,0x1D35,0x1D39,0x1D3F,0x1D41,0x1D4B,0x1D53,0x1D5D,0x1D63,0x1D69,0x1D71,0x1D75,0x1D7B,0x1D7D,0x1D87,0x1D89, 2569 0x1D95,0x1D99,0x1D9F,0x1DA5,0x1DA7,0x1DB3,0x1DB7,0x1DC5,0x1DD7,0x1DDB,0x1DE1,0x1DF5,0x1DF9,0x1E01,0x1E07,0x1E0B, 2570 0x1E13,0x1E17,0x1E25,0x1E2B,0x1E2F,0x1E3D,0x1E49,0x1E4D,0x1E4F,0x1E6D,0x1E71,0x1E89,0x1E8F,0x1E95,0x1EA1,0x1EAD, 2571 0x1EBB,0x1EC1,0x1EC5,0x1EC7,0x1ECB,0x1EDD,0x1EE3,0x1EEF,0x1EF7,0x1EFD,0x1F01,0x1F0D,0x1F0F,0x1F1B,0x1F39,0x1F49, 2572 0x1F4B,0x1F51,0x1F67,0x1F75,0x1F7B,0x1F85,0x1F91,0x1F97,0x1F99,0x1F9D,0x1FA5,0x1FAF,0x1FB5,0x1FBB,0x1FD3,0x1FE1, 2573 0x1FE7,0x1FEB,0x1FF3,0x1FFF,0x2011,0x201B,0x201D,0x2027,0x2029,0x202D,0x2033,0x2047,0x204D,0x2051,0x205F,0x2063, 2574 0x2065,0x2069,0x2077,0x207D,0x2089,0x20A1,0x20AB,0x20B1,0x20B9,0x20C3,0x20C5,0x20E3,0x20E7,0x20ED,0x20EF,0x20FB, 2575 0x20FF,0x210D,0x2113,0x2135,0x2141,0x2149,0x214F,0x2159,0x215B,0x215F,0x2173,0x217D,0x2185,0x2195,0x2197,0x21A1, 2576 0x21AF,0x21B3,0x21B5,0x21C1,0x21C7,0x21D7,0x21DD,0x21E5,0x21E9,0x21F1,0x21F5,0x21FB,0x2203,0x2209,0x220F,0x221B, 2577 0x2221,0x2225,0x222B,0x2231,0x2239,0x224B,0x224F,0x2263,0x2267,0x2273,0x2275,0x227F,0x2285,0x2287,0x2291,0x229D, 2578 0x229F,0x22A3,0x22B7,0x22BD,0x22DB,0x22E1,0x22E5,0x22ED,0x22F7,0x2303,0x2309,0x230B,0x2327,0x2329,0x232F,0x2333, 2579 0x2335,0x2345,0x2351,0x2353,0x2359,0x2363,0x236B,0x2383,0x238F,0x2395,0x23A7,0x23AD,0x23B1,0x23BF,0x23C5,0x23C9, 2580 0x23D5,0x23DD,0x23E3,0x23EF,0x23F3,0x23F9,0x2405,0x240B,0x2417,0x2419,0x2429,0x243D,0x2441,0x2443,0x244D,0x245F, 2581 0x2467,0x246B,0x2479,0x247D,0x247F,0x2485,0x249B,0x24A1,0x24AF,0x24B5,0x24BB,0x24C5,0x24CB,0x24CD,0x24D7,0x24D9, 2582 0x24DD,0x24DF,0x24F5,0x24F7,0x24FB,0x2501,0x2507,0x2513,0x2519,0x2527,0x2531,0x253D,0x2543,0x254B,0x254F,0x2573, 2583 0x2581,0x258D,0x2593,0x2597,0x259D,0x259F,0x25AB,0x25B1,0x25BD,0x25CD,0x25CF,0x25D9,0x25E1,0x25F7,0x25F9,0x2605, 2584 0x260B,0x260F,0x2615,0x2627,0x2629,0x2635,0x263B,0x263F,0x264B,0x2653,0x2659,0x2665,0x2669,0x266F,0x267B,0x2681, 2585 0x2683,0x268F,0x269B,0x269F,0x26AD,0x26B3,0x26C3,0x26C9,0x26CB,0x26D5,0x26DD,0x26EF,0x26F5,0x2717,0x2719,0x2735, 2586 0x2737,0x274D,0x2753,0x2755,0x275F,0x276B,0x276D,0x2773,0x2777,0x277F,0x2795,0x279B,0x279D,0x27A7,0x27AF,0x27B3, 2587 0x27B9,0x27C1,0x27C5,0x27D1,0x27E3,0x27EF,0x2803,0x2807,0x280D,0x2813,0x281B,0x281F,0x2821,0x2831,0x283D,0x283F, 2588 0x2849,0x2851,0x285B,0x285D,0x2861,0x2867,0x2875,0x2881,0x2897,0x289F,0x28BB,0x28BD,0x28C1,0x28D5,0x28D9,0x28DB, 2589 0x28DF,0x28ED,0x28F7,0x2903,0x2905,0x2911,0x2921,0x2923,0x293F,0x2947,0x295D,0x2965,0x2969,0x296F,0x2975,0x2983, 2590 0x2987,0x298F,0x299B,0x29A1,0x29A7,0x29AB,0x29BF,0x29C3,0x29D5,0x29D7,0x29E3,0x29E9,0x29ED,0x29F3,0x2A01,0x2A13, 2591 0x2A1D,0x2A25,0x2A2F,0x2A4F,0x2A55,0x2A5F,0x2A65,0x2A6B,0x2A6D,0x2A73,0x2A83,0x2A89,0x2A8B,0x2A97,0x2A9D,0x2AB9, 2592 0x2ABB,0x2AC5,0x2ACD,0x2ADD,0x2AE3,0x2AEB,0x2AF1,0x2AFB,0x2B13,0x2B27,0x2B31,0x2B33,0x2B3D,0x2B3F,0x2B4B,0x2B4F, 2593 0x2B55,0x2B69,0x2B6D,0x2B6F,0x2B7B,0x2B8D,0x2B97,0x2B99,0x2BA3,0x2BA5,0x2BA9,0x2BBD,0x2BCD,0x2BE7,0x2BEB,0x2BF3, 2594 0x2BF9,0x2BFD,0x2C09,0x2C0F,0x2C17,0x2C23,0x2C2F,0x2C35,0x2C39,0x2C41,0x2C57,0x2C59,0x2C69,0x2C77,0x2C81,0x2C87, 2595 0x2C93,0x2C9F,0x2CAD,0x2CB3,0x2CB7,0x2CCB,0x2CCF,0x2CDB,0x2CE1,0x2CE3,0x2CE9,0x2CEF,0x2CFF,0x2D07,0x2D1D,0x2D1F, 2596 0x2D3B,0x2D43,0x2D49,0x2D4D,0x2D61,0x2D65,0x2D71,0x2D89,0x2D9D,0x2DA1,0x2DA9,0x2DB3,0x2DB5,0x2DC5,0x2DC7,0x2DD3, 2597 0x2DDF,0x2E01,0x2E03,0x2E07,0x2E0D,0x2E19,0x2E1F,0x2E25,0x2E2D,0x2E33,0x2E37,0x2E39,0x2E3F,0x2E57,0x2E5B,0x2E6F, 2598 0x2E79,0x2E7F,0x2E85,0x2E93,0x2E97,0x2E9D,0x2EA3,0x2EA5,0x2EB1,0x2EB7,0x2EC1,0x2EC3,0x2ECD,0x2ED3,0x2EE7,0x2EEB, 2599 0x2F05,0x2F09,0x2F0B,0x2F11,0x2F27,0x2F29,0x2F41,0x2F45,0x2F4B,0x2F4D,0x2F51,0x2F57,0x2F6F,0x2F75,0x2F7D,0x2F81, 2600 0x2F83,0x2FA5,0x2FAB,0x2FB3,0x2FC3,0x2FCF,0x2FD1,0x2FDB,0x2FDD,0x2FE7,0x2FED,0x2FF5,0x2FF9,0x3001,0x300D,0x3023, 2601 0x3029,0x3037,0x303B,0x3055,0x3059,0x305B,0x3067,0x3071,0x3079,0x307D,0x3085,0x3091,0x3095,0x30A3,0x30A9,0x30B9, 2602 0x30BF,0x30C7,0x30CB,0x30D1,0x30D7,0x30DF,0x30E5,0x30EF,0x30FB,0x30FD,0x3103,0x3109,0x3119,0x3121,0x3127,0x312D, 2603 0x3139,0x3143,0x3145,0x314B,0x315D,0x3161,0x3167,0x316D,0x3173,0x317F,0x3191,0x3199,0x319F,0x31A9,0x31B1,0x31C3, 2604 0x31C7,0x31D5,0x31DB,0x31ED,0x31F7,0x31FF,0x3209,0x3215,0x3217,0x321D,0x3229,0x3235,0x3259,0x325D,0x3263,0x326B, 2605 0x326F,0x3275,0x3277,0x327B,0x328D,0x3299,0x329F,0x32A7,0x32AD,0x32B3,0x32B7,0x32C9,0x32CB,0x32CF,0x32D1,0x32E9, 2606 0x32ED,0x32F3,0x32F9,0x3307,0x3325,0x332B,0x332F,0x3335,0x3341,0x3347,0x335B,0x335F,0x3367,0x336B,0x3373,0x3379, 2607 0x337F,0x3383,0x33A1,0x33A3,0x33AD,0x33B9,0x33C1,0x33CB,0x33D3,0x33EB,0x33F1,0x33FD,0x3401,0x340F,0x3413,0x3419, 2608 0x341B,0x3437,0x3445,0x3455,0x3457,0x3463,0x3469,0x346D,0x3481,0x348B,0x3491,0x3497,0x349D,0x34A5,0x34AF,0x34BB, 2609 0x34C9,0x34D3,0x34E1,0x34F1,0x34FF,0x3509,0x3517,0x351D,0x352D,0x3533,0x353B,0x3541,0x3551,0x3565,0x356F,0x3571, 2610 0x3577,0x357B,0x357D,0x3581,0x358D,0x358F,0x3599,0x359B,0x35A1,0x35B7,0x35BD,0x35BF,0x35C3,0x35D5,0x35DD,0x35E7, 2611 0x35EF,0x3605,0x3607,0x3611,0x3623,0x3631,0x3635,0x3637,0x363B,0x364D,0x364F,0x3653,0x3659,0x3661,0x366B,0x366D, 2612 0x368B,0x368F,0x36AD,0x36AF,0x36B9,0x36BB,0x36CD,0x36D1,0x36E3,0x36E9,0x36F7,0x3701,0x3703,0x3707,0x371B,0x373F, 2613 0x3745,0x3749,0x374F,0x375D,0x3761,0x3775,0x377F,0x378D,0x37A3,0x37A9,0x37AB,0x37C9,0x37D5,0x37DF,0x37F1,0x37F3, 2614 0x37F7,0x3805,0x380B,0x3821,0x3833,0x3835,0x3841,0x3847,0x384B,0x3853,0x3857,0x385F,0x3865,0x386F,0x3871,0x387D, 2615 0x388F,0x3899,0x38A7,0x38B7,0x38C5,0x38C9,0x38CF,0x38D5,0x38D7,0x38DD,0x38E1,0x38E3,0x38FF,0x3901,0x391D,0x3923, 2616 0x3925,0x3929,0x392F,0x393D,0x3941,0x394D,0x395B,0x396B,0x3979,0x397D,0x3983,0x398B,0x3991,0x3995,0x399B,0x39A1, 2617 0x39A7,0x39AF,0x39B3,0x39BB,0x39BF,0x39CD,0x39DD,0x39E5,0x39EB,0x39EF,0x39FB,0x3A03,0x3A13,0x3A15,0x3A1F,0x3A27, 2618 0x3A2B,0x3A31,0x3A4B,0x3A51,0x3A5B,0x3A63,0x3A67,0x3A6D,0x3A79,0x3A87,0x3AA5,0x3AA9,0x3AB7,0x3ACD,0x3AD5,0x3AE1, 2619 0x3AE5,0x3AEB,0x3AF3,0x3AFD,0x3B03,0x3B11,0x3B1B,0x3B21,0x3B23,0x3B2D,0x3B39,0x3B45,0x3B53,0x3B59,0x3B5F,0x3B71, 2620 0x3B7B,0x3B81,0x3B89,0x3B9B,0x3B9F,0x3BA5,0x3BA7,0x3BAD,0x3BB7,0x3BB9,0x3BC3,0x3BCB,0x3BD1,0x3BD7,0x3BE1,0x3BE3, 2621 0x3BF5,0x3BFF,0x3C01,0x3C0D,0x3C11,0x3C17,0x3C1F,0x3C29,0x3C35,0x3C43,0x3C4F,0x3C53,0x3C5B,0x3C65,0x3C6B,0x3C71, 2622 0x3C85,0x3C89,0x3C97,0x3CA7,0x3CB5,0x3CBF,0x3CC7,0x3CD1,0x3CDD,0x3CDF,0x3CF1,0x3CF7,0x3D03,0x3D0D,0x3D19,0x3D1B, 2623 0x3D1F,0x3D21,0x3D2D,0x3D33,0x3D37,0x3D3F,0x3D43,0x3D6F,0x3D73,0x3D75,0x3D79,0x3D7B,0x3D85,0x3D91,0x3D97,0x3D9D, 2624 0x3DAB,0x3DAF,0x3DB5,0x3DBB,0x3DC1,0x3DC9,0x3DCF,0x3DF3,0x3E05,0x3E09,0x3E0F,0x3E11,0x3E1D,0x3E23,0x3E29,0x3E2F, 2625 0x3E33,0x3E41,0x3E57,0x3E63,0x3E65,0x3E77,0x3E81,0x3E87,0x3EA1,0x3EB9,0x3EBD,0x3EBF,0x3EC3,0x3EC5,0x3EC9,0x3ED7, 2626 0x3EDB,0x3EE1,0x3EE7,0x3EEF,0x3EFF,0x3F0B,0x3F0D,0x3F37,0x3F3B,0x3F3D,0x3F41,0x3F59,0x3F5F,0x3F65,0x3F67,0x3F79, 2627 0x3F7D,0x3F8B,0x3F91,0x3FAD,0x3FBF,0x3FCD,0x3FD3,0x3FDD,0x3FE9,0x3FEB,0x3FF1,0x3FFD,0x401B,0x4021,0x4025,0x402B, 2628 0x4031,0x403F,0x4043,0x4045,0x405D,0x4061,0x4067,0x406D,0x4087,0x4091,0x40A3,0x40A9,0x40B1,0x40B7,0x40BD,0x40DB, 2629 0x40DF,0x40EB,0x40F7,0x40F9,0x4109,0x410B,0x4111,0x4115,0x4121,0x4133,0x4135,0x413B,0x413F,0x4159,0x4165,0x416B, 2630 0x4177,0x417B,0x4193,0x41AB,0x41B7,0x41BD,0x41BF,0x41CB,0x41E7,0x41EF,0x41F3,0x41F9,0x4205,0x4207,0x4219,0x421F, 2631 0x4223,0x4229,0x422F,0x4243,0x4253,0x4255,0x425B,0x4261,0x4273,0x427D,0x4283,0x4285,0x4289,0x4291,0x4297,0x429D, 2632 0x42B5,0x42C5,0x42CB,0x42D3,0x42DD,0x42E3,0x42F1,0x4307,0x430F,0x431F,0x4325,0x4327,0x4333,0x4337,0x4339,0x434F, 2633 0x4357,0x4369,0x438B,0x438D,0x4393,0x43A5,0x43A9,0x43AF,0x43B5,0x43BD,0x43C7,0x43CF,0x43E1,0x43E7,0x43EB,0x43ED, 2634 0x43F1,0x43F9,0x4409,0x440B,0x4417,0x4423,0x4429,0x443B,0x443F,0x4445,0x444B,0x4451,0x4453,0x4459,0x4465,0x446F, 2635 0x4483,0x448F,0x44A1,0x44A5,0x44AB,0x44AD,0x44BD,0x44BF,0x44C9,0x44D7,0x44DB,0x44F9,0x44FB,0x4505,0x4511,0x4513, 2636 0x452B,0x4531,0x4541,0x4549,0x4553,0x4555,0x4561,0x4577,0x457D,0x457F,0x458F,0x45A3,0x45AD,0x45AF,0x45BB,0x45C7, 2637 0x45D9,0x45E3,0x45EF,0x45F5,0x45F7,0x4601,0x4603,0x4609,0x4613,0x4625,0x4627,0x4633,0x4639,0x463D,0x4643,0x4645, 2638 0x465D,0x4679,0x467B,0x467F,0x4681,0x468B,0x468D,0x469D,0x46A9,0x46B1,0x46C7,0x46C9,0x46CF,0x46D3,0x46D5,0x46DF, 2639 0x46E5,0x46F9,0x4705,0x470F,0x4717,0x4723,0x4729,0x472F,0x4735,0x4739,0x474B,0x474D,0x4751,0x475D,0x476F,0x4771, 2640 0x477D,0x4783,0x4787,0x4789,0x4799,0x47A5,0x47B1,0x47BF,0x47C3,0x47CB,0x47DD,0x47E1,0x47ED,0x47FB,0x4801,0x4807, 2641 0x480B,0x4813,0x4819,0x481D,0x4831,0x483D,0x4847,0x4855,0x4859,0x485B,0x486B,0x486D,0x4879,0x4897,0x489B,0x48A1, 2642 0x48B9,0x48CD,0x48E5,0x48EF,0x48F7,0x4903,0x490D,0x4919,0x491F,0x492B,0x4937,0x493D,0x4945,0x4955,0x4963,0x4969, 2643 0x496D,0x4973,0x4997,0x49AB,0x49B5,0x49D3,0x49DF,0x49E1,0x49E5,0x49E7,0x4A03,0x4A0F,0x4A1D,0x4A23,0x4A39,0x4A41, 2644 0x4A45,0x4A57,0x4A5D,0x4A6B,0x4A7D,0x4A81,0x4A87,0x4A89,0x4A8F,0x4AB1,0x4AC3,0x4AC5,0x4AD5,0x4ADB,0x4AED,0x4AEF, 2645 0x4B07,0x4B0B,0x4B0D,0x4B13,0x4B1F,0x4B25,0x4B31,0x4B3B,0x4B43,0x4B49,0x4B59,0x4B65,0x4B6D,0x4B77,0x4B85,0x4BAD, 2646 0x4BB3,0x4BB5,0x4BBB,0x4BBF,0x4BCB,0x4BD9,0x4BDD,0x4BDF,0x4BE3,0x4BE5,0x4BE9,0x4BF1,0x4BF7,0x4C01,0x4C07,0x4C0D, 2647 0x4C0F,0x4C15,0x4C1B,0x4C21,0x4C2D,0x4C33,0x4C4B,0x4C55,0x4C57,0x4C61,0x4C67,0x4C73,0x4C79,0x4C7F,0x4C8D,0x4C93, 2648 0x4C99,0x4CCD,0x4CE1,0x4CE7,0x4CF1,0x4CF3,0x4CFD,0x4D05,0x4D0F,0x4D1B,0x4D27,0x4D29,0x4D2F,0x4D33,0x4D41,0x4D51, 2649 0x4D59,0x4D65,0x4D6B,0x4D81,0x4D83,0x4D8D,0x4D95,0x4D9B,0x4DB1,0x4DB3,0x4DC9,0x4DCF,0x4DD7,0x4DE1,0x4DED,0x4DF9, 2650 0x4DFB,0x4E05,0x4E0B,0x4E17,0x4E19,0x4E1D,0x4E2B,0x4E35,0x4E37,0x4E3D,0x4E4F,0x4E53,0x4E5F,0x4E67,0x4E79,0x4E85, 2651 0x4E8B,0x4E91,0x4E95,0x4E9B,0x4EA1,0x4EAF,0x4EB3,0x4EB5,0x4EC1,0x4ECD,0x4ED1,0x4ED7,0x4EE9,0x4EFB,0x4F07,0x4F09, 2652 0x4F19,0x4F25,0x4F2D,0x4F3F,0x4F49,0x4F63,0x4F67,0x4F6D,0x4F75,0x4F7B,0x4F81,0x4F85,0x4F87,0x4F91,0x4FA5,0x4FA9, 2653 0x4FAF,0x4FB7,0x4FBB,0x4FCF,0x4FD9,0x4FDB,0x4FFD,0x4FFF,0x5003,0x501B,0x501D,0x5029,0x5035,0x503F,0x5045,0x5047, 2654 0x5053,0x5071,0x5077,0x5083,0x5093,0x509F,0x50A1,0x50B7,0x50C9,0x50D5,0x50E3,0x50ED,0x50EF,0x50FB,0x5107,0x510B, 2655 0x510D,0x5111,0x5117,0x5123,0x5125,0x5135,0x5147,0x5149,0x5171,0x5179,0x5189,0x518F,0x5197,0x51A1,0x51A3,0x51A7, 2656 0x51B9,0x51C1,0x51CB,0x51D3,0x51DF,0x51E3,0x51F5,0x51F7,0x5209,0x5213,0x5215,0x5219,0x521B,0x521F,0x5227,0x5243, 2657 0x5245,0x524B,0x5261,0x526D,0x5273,0x5281,0x5293,0x5297,0x529D,0x52A5,0x52AB,0x52B1,0x52BB,0x52C3,0x52C7,0x52C9, 2658 0x52DB,0x52E5,0x52EB,0x52FF,0x5315,0x531D,0x5323,0x5341,0x5345,0x5347,0x534B,0x535D,0x5363,0x5381,0x5383,0x5387, 2659 0x538F,0x5395,0x5399,0x539F,0x53AB,0x53B9,0x53DB,0x53E9,0x53EF,0x53F3,0x53F5,0x53FB,0x53FF,0x540D,0x5411,0x5413, 2660 0x5419,0x5435,0x5437,0x543B,0x5441,0x5449,0x5453,0x5455,0x545F,0x5461,0x546B,0x546D,0x5471,0x548F,0x5491,0x549D, 2661 0x54A9,0x54B3,0x54C5,0x54D1,0x54DF,0x54E9,0x54EB,0x54F7,0x54FD,0x5507,0x550D,0x551B,0x5527,0x552B,0x5539,0x553D, 2662 0x554F,0x5551,0x555B,0x5563,0x5567,0x556F,0x5579,0x5585,0x5597,0x55A9,0x55B1,0x55B7,0x55C9,0x55D9,0x55E7,0x55ED, 2663 0x55F3,0x55FD,0x560B,0x560F,0x5615,0x5617,0x5623,0x562F,0x5633,0x5639,0x563F,0x564B,0x564D,0x565D,0x565F,0x566B, 2664 0x5671,0x5675,0x5683,0x5689,0x568D,0x568F,0x569B,0x56AD,0x56B1,0x56D5,0x56E7,0x56F3,0x56FF,0x5701,0x5705,0x5707, 2665 0x570B,0x5713,0x571F,0x5723,0x5747,0x574D,0x575F,0x5761,0x576D,0x5777,0x577D,0x5789,0x57A1,0x57A9,0x57AF,0x57B5, 2666 0x57C5,0x57D1,0x57D3,0x57E5,0x57EF,0x5803,0x580D,0x580F,0x5815,0x5827,0x582B,0x582D,0x5855,0x585B,0x585D,0x586D, 2667 0x586F,0x5873,0x587B,0x588D,0x5897,0x58A3,0x58A9,0x58AB,0x58B5,0x58BD,0x58C1,0x58C7,0x58D3,0x58D5,0x58DF,0x58F1, 2668 0x58F9,0x58FF,0x5903,0x5917,0x591B,0x5921,0x5945,0x594B,0x594D,0x5957,0x595D,0x5975,0x597B,0x5989,0x5999,0x599F, 2669 0x59B1,0x59B3,0x59BD,0x59D1,0x59DB,0x59E3,0x59E9,0x59ED,0x59F3,0x59F5,0x59FF,0x5A01,0x5A0D,0x5A11,0x5A13,0x5A17, 2670 0x5A1F,0x5A29,0x5A2F,0x5A3B,0x5A4D,0x5A5B,0x5A67,0x5A77,0x5A7F,0x5A85,0x5A95,0x5A9D,0x5AA1,0x5AA3,0x5AA9,0x5ABB, 2671 0x5AD3,0x5AE5,0x5AEF,0x5AFB,0x5AFD,0x5B01,0x5B0F,0x5B19,0x5B1F,0x5B25,0x5B2B,0x5B3D,0x5B49,0x5B4B,0x5B67,0x5B79, 2672 0x5B87,0x5B97,0x5BA3,0x5BB1,0x5BC9,0x5BD5,0x5BEB,0x5BF1,0x5BF3,0x5BFD,0x5C05,0x5C09,0x5C0B,0x5C0F,0x5C1D,0x5C29, 2673 0x5C2F,0x5C33,0x5C39,0x5C47,0x5C4B,0x5C4D,0x5C51,0x5C6F,0x5C75,0x5C77,0x5C7D,0x5C87,0x5C89,0x5CA7,0x5CBD,0x5CBF, 2674 0x5CC3,0x5CC9,0x5CD1,0x5CD7,0x5CDD,0x5CED,0x5CF9,0x5D05,0x5D0B,0x5D13,0x5D17,0x5D19,0x5D31,0x5D3D,0x5D41,0x5D47, 2675 0x5D4F,0x5D55,0x5D5B,0x5D65,0x5D67,0x5D6D,0x5D79,0x5D95,0x5DA3,0x5DA9,0x5DAD,0x5DB9,0x5DC1,0x5DC7,0x5DD3,0x5DD7, 2676 0x5DDD,0x5DEB,0x5DF1,0x5DFD,0x5E07,0x5E0D,0x5E13,0x5E1B,0x5E21,0x5E27,0x5E2B,0x5E2D,0x5E31,0x5E39,0x5E45,0x5E49, 2677 0x5E57,0x5E69,0x5E73,0x5E75,0x5E85,0x5E8B,0x5E9F,0x5EA5,0x5EAF,0x5EB7,0x5EBB,0x5ED9,0x5EFD,0x5F09,0x5F11,0x5F27, 2678 0x5F33,0x5F35,0x5F3B,0x5F47,0x5F57,0x5F5D,0x5F63,0x5F65,0x5F77,0x5F7B,0x5F95,0x5F99,0x5FA1,0x5FB3,0x5FBD,0x5FC5, 2679 0x5FCF,0x5FD5,0x5FE3,0x5FE7,0x5FFB,0x6011,0x6023,0x602F,0x6037,0x6053,0x605F,0x6065,0x606B,0x6073,0x6079,0x6085, 2680 0x609D,0x60AD,0x60BB,0x60BF,0x60CD,0x60D9,0x60DF,0x60E9,0x60F5,0x6109,0x610F,0x6113,0x611B,0x612D,0x6139,0x614B, 2681 0x6155,0x6157,0x615B,0x616F,0x6179,0x6187,0x618B,0x6191,0x6193,0x619D,0x61B5,0x61C7,0x61C9,0x61CD,0x61E1,0x61F1, 2682 0x61FF,0x6209,0x6217,0x621D,0x6221,0x6227,0x623B,0x6241,0x624B,0x6251,0x6253,0x625F,0x6265,0x6283,0x628D,0x6295, 2683 0x629B,0x629F,0x62A5,0x62AD,0x62D5,0x62D7,0x62DB,0x62DD,0x62E9,0x62FB,0x62FF,0x6305,0x630D,0x6317,0x631D,0x632F, 2684 0x6341,0x6343,0x634F,0x635F,0x6367,0x636D,0x6371,0x6377,0x637D,0x637F,0x63B3,0x63C1,0x63C5,0x63D9,0x63E9,0x63EB, 2685 0x63EF,0x63F5,0x6401,0x6403,0x6409,0x6415,0x6421,0x6427,0x642B,0x6439,0x6443,0x6449,0x644F,0x645D,0x6467,0x6475, 2686 0x6485,0x648D,0x6493,0x649F,0x64A3,0x64AB,0x64C1,0x64C7,0x64C9,0x64DB,0x64F1,0x64F7,0x64F9,0x650B,0x6511,0x6521, 2687 0x652F,0x6539,0x653F,0x654B,0x654D,0x6553,0x6557,0x655F,0x6571,0x657D,0x658D,0x658F,0x6593,0x65A1,0x65A5,0x65AD, 2688 0x65B9,0x65C5,0x65E3,0x65F3,0x65FB,0x65FF,0x6601,0x6607,0x661D,0x6629,0x6631,0x663B,0x6641,0x6647,0x664D,0x665B, 2689 0x6661,0x6673,0x667D,0x6689,0x668B,0x6695,0x6697,0x669B,0x66B5,0x66B9,0x66C5,0x66CD,0x66D1,0x66E3,0x66EB,0x66F5, 2690 0x6703,0x6713,0x6719,0x671F,0x6727,0x6731,0x6737,0x673F,0x6745,0x6751,0x675B,0x676F,0x6779,0x6781,0x6785,0x6791, 2691 0x67AB,0x67BD,0x67C1,0x67CD,0x67DF,0x67E5,0x6803,0x6809,0x6811,0x6817,0x682D,0x6839,0x683B,0x683F,0x6845,0x684B, 2692 0x684D,0x6857,0x6859,0x685D,0x6863,0x6869,0x686B,0x6871,0x6887,0x6899,0x689F,0x68B1,0x68BD,0x68C5,0x68D1,0x68D7, 2693 0x68E1,0x68ED,0x68EF,0x68FF,0x6901,0x690B,0x690D,0x6917,0x6929,0x692F,0x6943,0x6947,0x6949,0x694F,0x6965,0x696B, 2694 0x6971,0x6983,0x6989,0x6997,0x69A3,0x69B3,0x69B5,0x69BB,0x69C1,0x69C5,0x69D3,0x69DF,0x69E3,0x69E5,0x69F7,0x6A07, 2695 0x6A2B,0x6A37,0x6A3D,0x6A4B,0x6A67,0x6A69,0x6A75,0x6A7B,0x6A87,0x6A8D,0x6A91,0x6A93,0x6AA3,0x6AC1,0x6AC9,0x6AE1, 2696 0x6AE7,0x6B05,0x6B0F,0x6B11,0x6B23,0x6B27,0x6B2D,0x6B39,0x6B41,0x6B57,0x6B59,0x6B5F,0x6B75,0x6B87,0x6B89,0x6B93, 2697 0x6B95,0x6B9F,0x6BBD,0x6BBF,0x6BDB,0x6BE1,0x6BEF,0x6BFF,0x6C05,0x6C19,0x6C29,0x6C2B,0x6C31,0x6C35,0x6C55,0x6C59, 2698 0x6C5B,0x6C5F,0x6C65,0x6C67,0x6C73,0x6C77,0x6C7D,0x6C83,0x6C8F,0x6C91,0x6C97,0x6C9B,0x6CA1,0x6CA9,0x6CAF,0x6CB3, 2699 0x6CC7,0x6CCB,0x6CEB,0x6CF5,0x6CFD,0x6D0D,0x6D0F,0x6D25,0x6D27,0x6D2B,0x6D31,0x6D39,0x6D3F,0x6D4F,0x6D5D,0x6D61, 2700 0x6D73,0x6D7B,0x6D7F,0x6D93,0x6D99,0x6DA5,0x6DB1,0x6DB7,0x6DC1,0x6DC3,0x6DCD,0x6DCF,0x6DDB,0x6DF7,0x6E03,0x6E15, 2701 0x6E17,0x6E29,0x6E33,0x6E3B,0x6E45,0x6E75,0x6E77,0x6E7B,0x6E81,0x6E89,0x6E93,0x6E95,0x6E9F,0x6EBD,0x6EBF,0x6EE3, 2702 0x6EE9,0x6EF3,0x6EF9,0x6EFB,0x6F0D,0x6F11,0x6F17,0x6F1F,0x6F2F,0x6F3D,0x6F4D,0x6F53,0x6F61,0x6F65,0x6F79,0x6F7D, 2703 0x6F83,0x6F85,0x6F8F,0x6F9B,0x6F9D,0x6FA3,0x6FAF,0x6FB5,0x6FBB,0x6FBF,0x6FCB,0x6FCD,0x6FD3,0x6FD7,0x6FE3,0x6FE9, 2704 0x6FF1,0x6FF5,0x6FF7,0x6FFD,0x700F,0x7019,0x701F,0x7027,0x7033,0x7039,0x704F,0x7051,0x7057,0x7063,0x7075,0x7079, 2705 0x7087,0x708D,0x7091,0x70A5,0x70AB,0x70BB,0x70C3,0x70C7,0x70CF,0x70E5,0x70ED,0x70F9,0x70FF,0x7105,0x7115,0x7121, 2706 0x7133,0x7151,0x7159,0x715D,0x715F,0x7163,0x7169,0x7183,0x7187,0x7195,0x71AD,0x71C3,0x71C9,0x71CB,0x71D1,0x71DB, 2707 0x71E1,0x71EF,0x71F5,0x71FB,0x7207,0x7211,0x7217,0x7219,0x7225,0x722F,0x723B,0x7243,0x7255,0x7267,0x7271,0x7277, 2708 0x727F,0x728F,0x7295,0x729B,0x72A3,0x72B3,0x72C7,0x72CB,0x72CD,0x72D7,0x72D9,0x72E3,0x72EF,0x72F5,0x72FD,0x7303, 2709 0x730D,0x7321,0x732B,0x733D,0x7357,0x735B,0x7361,0x737F,0x7381,0x7385,0x738D,0x7393,0x739F,0x73AB,0x73BD,0x73C1, 2710 0x73C9,0x73DF,0x73E5,0x73E7,0x73F3,0x7415,0x741B,0x742D,0x7439,0x743F,0x7441,0x745D,0x746B,0x747B,0x7489,0x748D, 2711 0x749B,0x74A7,0x74AB,0x74B1,0x74B7,0x74B9,0x74DD,0x74E1,0x74E7,0x74FB,0x7507,0x751F,0x7525,0x753B,0x753D,0x754D, 2712 0x755F,0x756B,0x7577,0x7589,0x758B,0x7591,0x7597,0x759D,0x75A1,0x75A7,0x75B5,0x75B9,0x75BB,0x75D1,0x75D9,0x75E5, 2713 0x75EB,0x75F5,0x75FB,0x7603,0x760F,0x7621,0x762D,0x7633,0x763D,0x763F,0x7655,0x7663,0x7669,0x766F,0x7673,0x7685, 2714 0x768B,0x769F,0x76B5,0x76B7,0x76C3,0x76DB,0x76DF,0x76F1,0x7703,0x7705,0x771B,0x771D,0x7721,0x772D,0x7735,0x7741, 2715 0x774B,0x7759,0x775D,0x775F,0x7771,0x7781,0x77A7,0x77AD,0x77B3,0x77B9,0x77C5,0x77CF,0x77D5,0x77E1,0x77E9,0x77EF, 2716 0x77F3,0x77F9,0x7807,0x7825,0x782B,0x7835,0x783D,0x7853,0x7859,0x7861,0x786D,0x7877,0x7879,0x7883,0x7885,0x788B, 2717 0x7895,0x7897,0x78A1,0x78AD,0x78BF,0x78D3,0x78D9,0x78DD,0x78E5,0x78FB,0x7901,0x7907,0x7925,0x792B,0x7939,0x793F, 2718 0x794B,0x7957,0x795D,0x7967,0x7969,0x7973,0x7991,0x7993,0x79A3,0x79AB,0x79AF,0x79B1,0x79B7,0x79C9,0x79CD,0x79CF, 2719 0x79D5,0x79D9,0x79F3,0x79F7,0x79FF,0x7A05,0x7A0F,0x7A11,0x7A15,0x7A1B,0x7A23,0x7A27,0x7A2D,0x7A4B,0x7A57,0x7A59, 2720 0x7A5F,0x7A65,0x7A69,0x7A7D,0x7A93,0x7A9B,0x7A9F,0x7AA1,0x7AA5,0x7AED,0x7AF5,0x7AF9,0x7B01,0x7B17,0x7B19,0x7B1D, 2721 0x7B2B,0x7B35,0x7B37,0x7B3B,0x7B4F,0x7B55,0x7B5F,0x7B71,0x7B77,0x7B8B,0x7B9B,0x7BA1,0x7BA9,0x7BAF,0x7BB3,0x7BC7, 2722 0x7BD3,0x7BE9,0x7BEB,0x7BEF,0x7BF1,0x7BFD,0x7C07,0x7C19,0x7C1B,0x7C31,0x7C37,0x7C49,0x7C67,0x7C69,0x7C73,0x7C81, 2723 0x7C8B,0x7C93,0x7CA3,0x7CD5,0x7CDB,0x7CE5,0x7CED,0x7CF7,0x7D03,0x7D09,0x7D1B,0x7D1D,0x7D33,0x7D39,0x7D3B,0x7D3F, 2724 0x7D45,0x7D4D,0x7D53,0x7D59,0x7D63,0x7D75,0x7D77,0x7D8D,0x7D8F,0x7D9F,0x7DAD,0x7DB7,0x7DBD,0x7DBF,0x7DCB,0x7DD5, 2725 0x7DE9,0x7DED,0x7DFB,0x7E01,0x7E05,0x7E29,0x7E2B,0x7E2F,0x7E35,0x7E41,0x7E43,0x7E47,0x7E55,0x7E61,0x7E67,0x7E6B, 2726 0x7E71,0x7E73,0x7E79,0x7E7D,0x7E91,0x7E9B,0x7E9D,0x7EA7,0x7EAD,0x7EB9,0x7EBB,0x7ED3,0x7EDF,0x7EEB,0x7EF1,0x7EF7, 2727 0x7EFB,0x7F13,0x7F15,0x7F19,0x7F31,0x7F33,0x7F39,0x7F3D,0x7F43,0x7F4B,0x7F5B,0x7F61,0x7F63,0x7F6D,0x7F79,0x7F87, 2728 0x7F8D,0x7FAF,0x7FB5,0x7FC3,0x7FC9,0x7FCD,0x7FCF 2729 };