shotgun/lib/bignum.c

   1 #include <ctype.h>
   2 #include <math.h>
   3
   4 #include "shotgun/lib/shotgun.h"
   5 #include "shotgun/lib/string.h"
   6
   7 #define NMP mp_int *n; OBJECT n_obj; \
   8   NEW_STRUCT(n_obj, n, BASIC_CLASS(bignum), mp_int); \
   9   mp_init(n);
  10 #define MMP mp_int *m; OBJECT m_obj; \
  11   NEW_STRUCT(m_obj, m, BASIC_CLASS(bignum), mp_int); \
  12   mp_init(m);
  13
  14
  15 #define MP(k) DATA_STRUCT(k, mp_int*)
  16 #define BDIGIT_DBL long long
  17 #define DIGIT_RADIX (1L << DIGIT_BIT)
  18
  19 void bignum_cleanup(STATE, OBJECT obj) {
  20   mp_int *n = MP(obj);
  21   mp_clear(n);
  22 }
  23
  24 void bignum_init(STATE) {
  25   state_add_cleanup(state, BASIC_CLASS(bignum), bignum_cleanup);
  26 }
  27
  28 static void twos_complement(mp_int *a)
  29 {
  30   long i = a->used;
  31   BDIGIT_DBL num;
  32
  33   while (i--) {
  34     DIGIT(a,i) = (~DIGIT(a,i)) & (DIGIT_RADIX-1);
  35   }
  36
  37   i = 0; num = 1;
  38   do {
  39     num += DIGIT(a,i);
  40     DIGIT(a,i++) = num & (DIGIT_RADIX-1);
  41     num = num >> DIGIT_BIT;
  42   } while (i < a->used);
  43
  44 }
  45
  46 OBJECT bignum_new(STATE, native_int num) {
  47   mp_int *a;
  48   OBJECT o;
  49   o = object_memory_new_opaque(state, BASIC_CLASS(bignum), sizeof(mp_int));
  50   a = (mp_int*)BYTES_OF(o);
  51
  52   if(num < 0) {
  53     mp_init_set_long(a, (unsigned long)-num);
  54     a->sign = MP_NEG;
  55   } else {
  56     mp_init_set_long(a, (unsigned long)num);
  57   }
  58   return o;
  59 }
  60
  61 OBJECT bignum_new_unsigned(STATE, unsigned int num) {
  62   OBJECT o;
  63   o = object_memory_new_opaque(state, BASIC_CLASS(bignum), sizeof(mp_int));
  64   mp_init_set_int(MP(o), num);
  65   return o;
  66 }
  67
  68 static inline OBJECT bignum_normalize(STATE, OBJECT b) {
  69   mp_clamp(MP(b));
  70
  71   if(mp_count_bits(MP(b)) <= FIXNUM_WIDTH) {
  72     native_int val;
  73     val = (native_int)bignum_to_ll(state, b);
  74     return I2N(val);
  75   }
  76   return b;
  77 }
  78
  79 OBJECT bignum_add(STATE, OBJECT a, OBJECT b) {
  80   NMP;
  81
  82   if(FIXNUM_P(b)) {
  83     if(N2I(b) < 0) {
  84       mp_sub_d(MP(a), -N2I(b), n);
  85     } else {
  86       mp_add_d(MP(a), N2I(b), n);
  87     }
  88   } else {
  89     mp_add(MP(a), MP(b), n);
  90   }
  91
  92   return bignum_normalize(state, n_obj);
  93 }
  94
  95 OBJECT bignum_sub(STATE, OBJECT a, OBJECT b) {
  96   NMP;
  97
  98   if(FIXNUM_P(b)) {
  99     if(N2I(b) < 0) {
 100       mp_add_d(MP(a), -N2I(b), n);
 101     } else {
 102       mp_sub_d(MP(a), N2I(b), n);
 103     }
 104   } else {
 105     mp_sub(MP(a), MP(b), n);
 106   }
 107
 108   return bignum_normalize(state, n_obj);
 109 }
 110
 111 void bignum_debug(STATE, OBJECT n) {
 112   char *stra = XMALLOC(2048);
 113   mp_toradix(MP(n), stra, 10);
 114   printf("n: %s\n", stra);
 115   FREE(stra);
 116   return;
 117 }
 118
 119 OBJECT bignum_mul(STATE, OBJECT a, OBJECT b) {
 120   NMP;
 121
 122   if(FIXNUM_P(b)) {
 123     if(b == I2N(2)) {
 124       mp_mul_2(MP(a), n);
 125       return n_obj;
 126     }
 127     if(N2I(b) < 0) {
 128       /* mp_mul_d only accepts positive integers (unsigned long).
 129        * Therefore we jump through some hoops to negate
 130        * both parts so the final result is the same.
 131        */
 132       mp_neg(MP(a), n);
 133       mp_mul_d(n, -N2I(b), n);
 134     } else {
 135       mp_mul_d(MP(a), N2I(b), n);
 136     }
 137   } else {
 138     mp_mul(MP(a), MP(b), n);
 139   }
 140
 141   return bignum_normalize(state, n_obj);
 142 }
 143
 144 OBJECT bignum_div(STATE, OBJECT a, OBJECT b, mp_int *mod) {
 145   NMP;
 146   mp_int m, x, y, z;
 147
 148   if(FIXNUM_P(b)) {
 149     b = bignum_new(state, N2I(b));
 150   }
 151
 152   mp_init(&m);
 153   mp_init(&x);
 154   mp_init(&y);
 155   mp_init(&z);
 156
 157   if(mp_cmp_d(MP(b), 0) == MP_LT) {
 158     if(mp_cmp_d(MP(a), 0) == MP_LT) {
 159       mp_neg(MP(a), &x);
 160       mp_neg(MP(b), &y);
 161       mp_div(&x, &y, &z, NULL);
 162     } else {
 163       mp_neg(MP(b), &x);
 164       mp_div(MP(a), &x, &y, NULL);
 165       mp_neg(&y, &z);
 166     }
 167   } else {
 168     if (mp_cmp_d(MP(a), 0) == MP_LT) {
 169       mp_neg(MP(a), &x);
 170       mp_div(&x, MP(b), &y, NULL);
 171       mp_neg(&y, &z);
 172     } else {
 173       mp_div(MP(a), MP(b), &z, NULL);
 174     }
 175   }
 176
 177   mp_mul(&z, MP(b), &x);
 178   mp_sub(MP(a), &x, &y);
 179
 180   if((mp_cmp_d(&y, 0) == MP_LT && mp_cmp_d(MP(b), 0) == MP_GT)
 181       || (mp_cmp_d(&y, 0) == MP_GT && mp_cmp_d(MP(b), 0) == MP_LT)) {
 182     mp_add(&y, MP(b), &m);
 183     mp_sub_d(&z, 1, n);
 184   } else {
 185     mp_copy(&z, n);
 186     mp_copy(&y, &m);
 187   }
 188
 189   if(mod) {
 190     mp_copy(&m, mod);
 191   }
 192
 193   mp_clear(&m);
 194   mp_clear(&x);
 195   mp_clear(&y);
 196   mp_clear(&z);
 197
 198   return bignum_normalize(state, n_obj);
 199 }
 200
 201 OBJECT bignum_divmod(STATE, OBJECT a, OBJECT b) {
 202   MMP;
 203   OBJECT div, ary;
 204
 205   div = bignum_div(state, a, b, m);
 206
 207   ary = array_new(state, 2);
 208   array_set(state, ary, 0, div);
 209   array_set(state, ary, 1, bignum_normalize(state, m_obj));
 210   return ary;
 211 }
 212
 213 OBJECT bignum_mod(STATE, OBJECT a, OBJECT b) {
 214   NMP;
 215
 216   if(FIXNUM_P(b)) {
 217     b = bignum_new(state, N2I(b));
 218   }
 219   mp_mod(MP(a), MP(b), n);
 220   return bignum_normalize(state, n_obj);
 221 }
 222
 223 int bignum_is_zero(STATE, OBJECT a) {
 224   return mp_iszero(MP(a)) ? TRUE : FALSE;
 225 }
 226
 227 #define BITWISE_OP_AND 1
 228 #define BITWISE_OP_OR  2
 229 #define BITWISE_OP_XOR 3
 230
 231 void bignum_bitwise_op(int op, mp_int *x, mp_int *y, mp_int *n)
 232 {
 233   mp_int   a,   b;
 234   mp_int *d1, *d2;
 235   int i, sign,  l1,  l2;
 236   mp_init(&a) ; mp_init(&b);
 237
 238   if (y->sign == MP_NEG) {
 239     mp_copy(y, &b);
 240     twos_complement(&b);
 241     y = &b;
 242   }
 243
 244   if (x->sign == MP_NEG) {
 245     mp_copy(x, &a);
 246     twos_complement(&a);
 247     x = &a;
 248   }
 249
 250   if (x->used > y->used) {
 251     l1 = y->used;
 252     l2 = x->used;
 253     d1 = y;
 254     d2 = x;
 255     sign = y->sign;
 256   } else {
 257     l1 = x->used;
 258     l2 = y->used;
 259     d1 = x;
 260     d2 = y;
 261     sign = x->sign;
 262   }
 263
 264   mp_grow(n, l2);
 265   n->used = l2;
 266   n->sign = MP_ZPOS;
 267   switch(op) {
 268     case BITWISE_OP_AND:
 269       if (x->sign == MP_NEG && y->sign == MP_NEG) n->sign = MP_NEG;
 270       for (i=0; i < l1; i++) {
 271         DIGIT(n,i) = DIGIT(d1,i) & DIGIT(d2,i);
 272       }
 273       for (; i < l2; i++) {
 274         DIGIT(n,i) = (sign == MP_ZPOS)?0:DIGIT(d2,i);
 275       }
 276       break;
 277     case BITWISE_OP_OR:
 278       if (x->sign == MP_NEG || y->sign == MP_NEG) n->sign = MP_NEG;
 279       for (i=0; i < l1; i++) {
 280         DIGIT(n,i) = DIGIT(d1,i) | DIGIT(d2,i);
 281       }
 282       for (; i < l2; i++) {
 283         DIGIT(n,i) = (sign == MP_ZPOS)?DIGIT(d2,i):(DIGIT_RADIX-1);
 284       }
 285       break;
 286     case BITWISE_OP_XOR:
 287       if (x->sign != y->sign) n->sign = MP_NEG;
 288       for (i=0; i < l1; i++) {
 289         DIGIT(n,i) = DIGIT(d1,i) ^ DIGIT(d2,i);
 290       }
 291       for (; i < l2; i++) {
 292         DIGIT(n,i) = (sign == MP_ZPOS)?DIGIT(d2,i):~DIGIT(d2,i);
 293       }
 294       break;
 295   }
 296
 297   if (n->sign == MP_NEG) twos_complement(n);
 298
 299   /* free allocated resources for twos complement copies */
 300   mp_clear(&a);
 301   mp_clear(&b);
 302 }
 303
 304 OBJECT bignum_and(STATE, OBJECT a, OBJECT b) {
 305   NMP;
 306
 307   if(FIXNUM_P(b)) {
 308     b = bignum_new(state, N2I(b));
 309   }
 310
 311   /* Perhaps this should use mp_and rather than our own version */
 312   bignum_bitwise_op(BITWISE_OP_AND, MP(a), MP(b), n);
 313   return bignum_normalize(state, n_obj);
 314 }
 315
 316 OBJECT bignum_or(STATE, OBJECT a, OBJECT b) {
 317   NMP;
 318
 319   if(FIXNUM_P(b)) {
 320     b = bignum_new(state, N2I(b));
 321   }
 322   /* Perhaps this should use mp_or rather than our own version */
 323   bignum_bitwise_op(BITWISE_OP_OR, MP(a), MP(b), n);
 324   return bignum_normalize(state, n_obj);
 325 }
 326
 327 OBJECT bignum_xor(STATE, OBJECT a, OBJECT b) {
 328   NMP;
 329
 330   if(FIXNUM_P(b)) {
 331     b = bignum_new(state, N2I(b));
 332   }
 333   /* Perhaps this should use mp_xor rather than our own version */
 334   bignum_bitwise_op(BITWISE_OP_XOR, MP(a), MP(b), n);
 335   return bignum_normalize(state, n_obj);
 336 }
 337
 338 OBJECT bignum_invert(STATE, OBJECT self) {
 339   NMP;
 340
 341   mp_int a; mp_init(&a);
 342   mp_int b; mp_init_set_int(&b, 1);
 343
 344   /* inversion by -(a)-1 */
 345   mp_neg(MP(self), &a);
 346   mp_sub(&a, &b, n);
 347
 348   mp_clear(&a); mp_clear(&b);
 349   return bignum_normalize(state, n_obj);
 350 }
 351
 352 OBJECT bignum_neg(STATE, OBJECT self) {
 353   NMP;
 354
 355   mp_neg(MP(self), n);
 356   return bignum_normalize(state, n_obj);
 357 }
 358
 359 /* These 2 don't use mp_lshd because it shifts by internal digits,
 360    not bits. */
 361
 362 OBJECT bignum_left_shift(STATE, OBJECT self, OBJECT bits) {
 363   NMP;
 364   int shift = N2I(bits);
 365   mp_int *a = MP(self);
 366
 367   mp_mul_2d(a, shift, n);
 368   n->sign = a->sign;
 369   return bignum_normalize(state, n_obj);
 370 }
 371
 372 OBJECT bignum_right_shift(STATE, OBJECT self, OBJECT bits) {
 373   NMP;
 374   int shift = N2I(bits);
 375   mp_int * a = MP(self);
 376
 377   if ((shift / DIGIT_BIT) >= a->used) {
 378     if (a->sign == MP_ZPOS)
 379       return I2N(0);
 380     else
 381       return I2N(-1);
 382   }
 383
 384   if (shift == 0) {
 385     mp_copy(a, n);
 386   } else {
 387     int need_floor = (a->sign == MP_NEG) && (DIGIT(a, 0) & 1);
 388
 389     mp_div_2d(a, shift, n, NULL);
 390     n->sign = a->sign;
 391     if (need_floor) {
 392       /* We sometimes have to simulate the rounding toward negative
 393          infinity that would happen if we were using a twos-complement
 394          representation.  We know we'll never overflow or need to grow,
 395          but we may need to back away from zero.  (libtommath doesn't
 396          seem to have an increment-in-place function.) */
 397       long i = 0;
 398       BDIGIT_DBL num = 1;
 399
 400       if (n->used == 0)
 401           n->used = 1;
 402       while (i < n->used) {
 403         num += DIGIT(n,i);
 404         DIGIT(n,i++) = num & (DIGIT_RADIX-1);
 405         num = num >> DIGIT_BIT;
 406       }
 407     }
 408   }
 409
 410   return bignum_normalize(state, n_obj);
 411 }
 412
 413 OBJECT bignum_equal(STATE, OBJECT a, OBJECT b) {
 414   int r;
 415   if(FIXNUM_P(b)) {
 416     if(N2I(b) < 0) {
 417       mp_int n;
 418       mp_init(&n);
 419       mp_neg(MP(a), &n);
 420       r = mp_cmp_d(&n, -N2I(b));
 421       mp_clear(&n);
 422     } else {
 423       r = mp_cmp_d(MP(a), N2I(b));
 424     }
 425   } else {
 426     r = mp_cmp(MP(a), MP(b));
 427   }
 428
 429   if(r == MP_EQ) {
 430     return Qtrue;
 431   }
 432   return Qfalse;
 433 }
 434
 435 OBJECT bignum_compare(STATE, OBJECT a, OBJECT b) {
 436   int r;
 437   if(FIXNUM_P(b)) {
 438     b = bignum_new(state, N2I(b));
 439   }
 440   r = mp_cmp(MP(a), MP(b));
 441
 442   switch(r) {
 443     case MP_LT:
 444       return I2N(-1);
 445     case MP_GT:
 446       return I2N(1);
 447   }
 448   return I2N(0);
 449 }
 450
 451 OBJECT bignum_gt(STATE, OBJECT a, OBJECT b) {
 452   int r;
 453   if(FIXNUM_P(b)) {
 454     native_int bi;
 455     r = mp_cmp_d(MP(a), (bi = N2I(b)) < 0 ? -bi : bi);
 456   } else {
 457     r = mp_cmp(MP(a), MP(b));
 458   }
 459
 460   if(r == MP_GT) {
 461     return Qtrue;
 462   }
 463   return Qfalse;
 464 }
 465
 466 OBJECT bignum_ge(STATE, OBJECT a, OBJECT b) {
 467   int r;
 468   if(FIXNUM_P(b)) {
 469     if(N2I(b) < 0) {
 470       r = mp_cmp_d(MP(a), -N2I(b));
 471     } else {
 472       r = mp_cmp_d(MP(a), N2I(b));
 473     }
 474   } else {
 475     r = mp_cmp(MP(a), MP(b));
 476   }
 477
 478   if(r == MP_GT || r == MP_EQ) {
 479     return Qtrue;
 480   }
 481   return Qfalse;
 482 }
 483
 484 OBJECT bignum_lt(STATE, OBJECT a, OBJECT b) {
 485   int r;
 486   if(FIXNUM_P(b)) {
 487     native_int bi;
 488     r = mp_cmp_d(MP(a), (bi = N2I(b)) < 0 ? -bi : bi);
 489   } else {
 490     r = mp_cmp(MP(a), MP(b));
 491   }
 492
 493   if(r == MP_LT) {
 494     return Qtrue;
 495   }
 496   return Qfalse;
 497 }
 498
 499 OBJECT bignum_le(STATE, OBJECT a, OBJECT b) {
 500   int r;
 501   if(FIXNUM_P(b)) {
 502     native_int bi;
 503     r = mp_cmp_d(MP(a), (bi = N2I(b)) < 0 ? -bi : bi);
 504   } else {
 505     r = mp_cmp(MP(a), MP(b));
 506   }
 507
 508   if(r == MP_LT || r == MP_EQ) {
 509     return Qtrue;
 510   }
 511   return Qfalse;
 512 }
 513
 514 unsigned long bignum_to_int(STATE, OBJECT self) {
 515   return mp_get_int(MP(self));
 516 }
 517
 518 int bignum_to_i(STATE, OBJECT self) {
 519   mp_int *s = MP(self);
 520
 521   if (s->sign == MP_NEG) return -mp_get_int(s);
 522
 523   return mp_get_int(s);
 524 }
 525
 526 unsigned int bignum_to_ui(STATE, OBJECT self) {
 527   return (unsigned int)mp_get_int(MP(self));
 528 }
 529
 530 unsigned long long bignum_to_ull(STATE, OBJECT self) {
 531   mp_int t;
 532   mp_int *s = MP(self);
 533   unsigned long long out, tmp;
 534
 535   /* mp_get_int() gets only the lower 32 bits, on any platform. */
 536   out = mp_get_int(s);
 537
 538   mp_init(&t);
 539   mp_div_2d(s, 32, &t, NULL);
 540
 541   tmp = mp_get_int(&t);
 542   out |= tmp << 32;
 543
 544   mp_clear(&t);
 545   return out;
 546 }
 547
 548 long long bignum_to_ll(STATE, OBJECT self) {
 549   mp_int *s = MP(self);
 550
 551   if (s->sign == MP_NEG)
 552     return -bignum_to_ull(state, self);
 553   else
 554     return bignum_to_ull(state, self);
 555 }
 556
 557 OBJECT bignum_from_ull(STATE, unsigned long long val) {
 558   OBJECT ret;
 559   mp_int low, high;
 560
 561   mp_init_set_int(&low, val & 0xffffffff);
 562   mp_init_set_int(&high, val >> 32);
 563   mp_mul_2d(&high, 32, &high);
 564
 565   ret = bignum_new_unsigned(state, 0);
 566
 567   mp_or(&low, &high, MP(ret));
 568
 569   mp_clear(&low);
 570   mp_clear(&high);
 571
 572   return ret;
 573 }
 574
 575 OBJECT bignum_from_ll(STATE, long long val) {
 576   OBJECT ret;
 577
 578   if(val < 0) {
 579     ret = bignum_from_ull(state, (unsigned long long)-val);
 580     MP(ret)->sign = MP_NEG;
 581   } else {
 582     ret = bignum_from_ull(state, (unsigned long long)val);
 583   }
 584
 585   return ret;
 586 }
 587
 588 OBJECT bignum_to_s(STATE, OBJECT self, OBJECT radix) {
 589   char *buf;
 590   int sz = 1024;
 591   int k;
 592   OBJECT obj;
 593
 594   for(;;) {
 595     buf = ALLOC_N(char, sz);
 596     mp_toradix_nd(MP(self), buf, N2I(radix), sz, &k);
 597     if(k < sz - 2) {
 598       obj = string_new(state, buf);
 599       FREE(buf);
 600       return obj;
 601     }
 602     FREE(buf);
 603     sz += 1024;
 604   }
 605 }
 606
 607 OBJECT bignum_from_string_detect(STATE, char *str) {
 608   char *s;
 609   int radix;
 610   int sign;
 611   NMP;
 612   s = str;
 613   sign = 1;
 614   while(isspace(*s)) { s++; }
 615   if(*s == '+') {
 616     s++;
 617   } else if(*s == '-') {
 618     sign = 0;
 619     s++;
 620   }
 621   radix = 10;
 622   if(*s == '0') {
 623     switch(s[1]) {
 624       case 'x': case 'X':
 625         radix = 16; s += 2;
 626         break;
 627       case 'b': case 'B':
 628         radix = 2; s += 2;
 629         break;
 630       case 'o': case 'O':
 631         radix = 8; s += 2;
 632         break;
 633       case 'd': case 'D':
 634         radix = 10; s += 2;
 635         break;
 636       default:
 637         radix = 8; s += 1;
 638     }
 639   }
 640   mp_read_radix(n, s, radix);
 641
 642   if(!sign) {
 643     n->sign = MP_NEG;
 644   }
 645
 646   return bignum_normalize(state, n_obj);
 647 }
 648
 649 OBJECT bignum_from_string(STATE, char *str, int radix) {
 650   NMP;
 651   mp_read_radix(n, str, radix);
 652   return bignum_normalize(state, n_obj);
 653 }
 654
 655 void bignum_into_string(STATE, OBJECT self, int radix, char *buf, int sz) {
 656   int k;
 657   mp_toradix_nd(MP(self), buf, radix, sz, &k);
 658 }
 659
 660 double bignum_to_double(STATE, OBJECT self) {
 661   int i;
 662   double res;
 663   double m;
 664   mp_int *a;
 665
 666   a = MP(self);
 667
 668   if (a->used == 0) {
 669      return 0;
 670   }
 671
 672   /* get number of digits of the lsb we have to read */
 673   i = a->used;
 674   m = DIGIT_RADIX;
 675
 676   /* get most significant digit of result */
 677   res = DIGIT(a,i);
 678
 679   while (--i >= 0) {
 680     res = (res * m) + DIGIT(a,i);
 681   }
 682
 683   if(isinf(res)) {
 684     /* Bignum out of range */
 685     res = HUGE_VAL;
 686   }
 687
 688   if(a->sign == MP_NEG) res = -res;
 689
 690   return res;
 691 }
 692
 693 OBJECT bignum_from_double(STATE, double d)
 694 {
 695   NMP;
 696
 697   long i = 0;
 698   BDIGIT_DBL c;
 699   double value;
 700
 701   value = (d < 0) ? -d : d;
 702
 703   /*
 704   if (isinf(d)) {
 705     rb_raise(rb_eFloatDomainError, d < 0 ? "-Infinity" : "Infinity");
 706   }
 707   if (isnan(d)) {
 708     rb_raise(rb_eFloatDomainError, "NaN");
 709   }
 710   */
 711
 712   while (!(value <= (LONG_MAX >> 1)) || 0 != (long)value) {
 713     value = value / (double)(DIGIT_RADIX);
 714     i++;
 715   }
 716
 717   mp_grow(n, i);
 718
 719   while (i--) {
 720     value *= DIGIT_RADIX;
 721     c = (BDIGIT_DBL) value;
 722     value -= c;
 723     DIGIT(n,i) = c;
 724     n->used += 1;
 725   }
 726
 727   if (d < 0) {
 728     mp_neg(n, n);
 729   }
 730
 731   return bignum_normalize(state, n_obj);
 732 }
 733
 734 OBJECT bignum_size(STATE, OBJECT self)
 735 {
 736   int bits = mp_count_bits(MP(self));
 737   int bytes = (bits + 7) / 8;
 738
 739   /* MRI returns this in words, but thats an implementation detail as far
 740      as I'm concerned. */
 741   return I2N(bytes);
 742 }
 743
 744 int bignum_hash_int(OBJECT self)
 745 {
 746   mp_int *a = MP(self);
 747
 748   /* Apparently, a couple bits of each a->dp[n] aren't actually used,
 749      (e.g. when DIGIT_BIT is 60) so this hash is actually including
 750      that unused memory.  This might only be a problem if calculations
 751      are leaving cruft in those unused bits.  However, since Bignums
 752      are immutable, this shouldn't happen to us. */
 753   return string_hash_str((unsigned char *)a->dp, a->used * sizeof(mp_digit));
 754 }
 755
 756 int mp_init_set_long (mp_int * a, unsigned long b)
 757 {
 758   int err;
 759   if ((err = mp_init(a)) != MP_OKAY) {
 760      return err;
 761   }
 762   return mp_set_long(a, b);
 763 }
 764
 765 int mp_set_long (mp_int * a, unsigned long b)
 766 {
 767   int     x, res;
 768   // TODO: Move these two values to bignum.h
 769   size_t  count = sizeof(unsigned long) * 2;
 770   size_t  shift_width = (sizeof(unsigned long) * 8) - 4;
 771
 772   mp_zero (a);
 773
 774   /* set four bits at a time */
 775   for (x = 0; x < count; x++) {
 776     /* shift the number up four bits */
 777     if ((res = mp_mul_2d (a, 4, a)) != MP_OKAY) {
 778       return res;
 779     }
 780
 781     /* OR in the top four bits of the source */
 782     a->dp[0] |= (b >> shift_width) & 15;
 783
 784     /* shift the source up to the next four bits */
 785     b <<= 4;
 786
 787     /* ensure that digits are not clamped off */
 788     a->used += 1;
 789   }
 790   mp_clamp (a);
 791   return MP_OKAY;
 792 }