uspace/app/sbi/src/bigint.c

   1 /*
   2  * Copyright (c) 2010 Jiri Svoboda
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @file Big integers.
  30  *
  31  * Sysel type @c int should accomodate large numbers. This implementation
  32  * is limited by the available memory and range of the @c size_t type used
  33  * to index digits.
  34  */
  35
  36 #include <assert.h>
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39 #include "debug.h"
  40 #include "mytypes.h"
  41
  42 #include "bigint.h"
  43
  44 static void bigint_sign_comb(bool_t srf_a, bigint_t *a, bool_t srf_b,
  45     bigint_t *b, bigint_t *dest);
  46 static void bigint_add_abs(bigint_t *a, bigint_t *b, bigint_t *dest);
  47 static void bigint_sub_abs(bigint_t *a, bigint_t *b, bigint_t *dest);
  48 static void bigint_shift_mul_dig(bigint_t *a, bigint_word_t b, size_t shift,
  49     bigint_t *dest);
  50
  51 static void bigint_alloc(bigint_t *bigint, size_t length);
  52 static void bigint_refine_len(bigint_t *bigint);
  53
  54 /** Initialize bigint with value from small integer.
  55  *
  56  * Initializes a bigint structure with the provided small value.
  57  *
  58  * @param value         Initial value (small int).
  59  */
  60 void bigint_init(bigint_t *bigint, int value)
  61 {
  62         size_t length;
  63         size_t idx;
  64         int t;
  65
  66 #ifdef DEBUG_BIGINT_TRACE
  67         printf("Initialize bigint with int value %d.\n", value);
  68 #endif
  69
  70         if (value < 0) {
  71                 bigint->negative = b_true;
  72                 value = -value;
  73         } else {
  74                 bigint->negative = b_false;
  75         }
  76
  77         /* Determine length. */
  78         length = 0;
  79         t = value;
  80         while (t > 0) {
  81                 length += 1;
  82                 t = t / BIGINT_BASE;
  83         }
  84
  85         /* Allocate digit array. */
  86         bigint_alloc(bigint, length);
  87
  88         /* Compute digits. */
  89         t = value;
  90         for (idx = 0; idx < length; ++idx) {
  91                 bigint->digit[idx] = t % BIGINT_BASE;
  92                 t = t / BIGINT_BASE;
  93         }
  94 }
  95
  96 /** Shallow copy of integer.
  97  *
  98  * @param src           Source.
  99  * @param dest          Destination.
 100  */
 101 void bigint_shallow_copy(bigint_t *src, bigint_t *dest)
 102 {
 103 #ifdef DEBUG_BIGINT_TRACE
 104         printf("Shallow copy of bigint.\n");
 105 #endif
 106         dest->negative = src->negative;
 107         dest->digit = src->digit;
 108         dest->length = src->length;
 109 }
 110 /** Clone big integer.
 111  *
 112  * @param src           Source.
 113  * @param dest          Destination.
 114  */
 115 void bigint_clone(bigint_t *src, bigint_t *dest)
 116 {
 117         size_t idx;
 118
 119 #ifdef DEBUG_BIGINT_TRACE
 120         printf("Clone bigint.\n");
 121 #endif
 122         /* Copy sign. */
 123         dest->negative = src->negative;
 124
 125         /* Allocate dest digit array. */
 126         bigint_alloc(dest, src->length);
 127
 128         /* Copy digits. */
 129         for (idx = 0; idx < dest->length; ++idx)
 130                 dest->digit[idx] = src->digit[idx];
 131 }
 132
 133 /** Compute big integer with reversed sign.
 134  *
 135  * @param src           Source.
 136  * @param dest          Destination.
 137  */
 138 void bigint_reverse_sign(bigint_t *src, bigint_t *dest)
 139 {
 140         size_t idx;
 141
 142 #ifdef DEBUG_BIGINT_TRACE
 143         printf("Reverse-sign copy of bigint.\n");
 144 #endif
 145         /* Copy reversed sign. */
 146         dest->negative = !src->negative;
 147
 148         /* Allocate dest digit array. */
 149         bigint_alloc(dest, src->length);
 150
 151         /* Copy digits. */
 152         for (idx = 0; idx < dest->length; ++idx)
 153                 dest->digit[idx] = src->digit[idx];
 154 }
 155
 156 /** Destroy big integer.
 157  *
 158  * Any bigint that is initialized via bigint_init() or any other bigint
 159  * function that constructs a new bigint value should be destroyed with
 160  * this function to free memory associated with the bigint. It should
 161  * also be used to destroy a bigint before it is reused.
 162  *
 163  * @param bigint        The bigint to destroy.
 164  */
 165 void bigint_destroy(bigint_t *bigint)
 166 {
 167 #ifdef DEBUG_BIGINT_TRACE
 168         printf("Destroy bigint.\n");
 169 #endif
 170         bigint->negative = b_false;
 171
 172         bigint->length = 0;
 173
 174         free(bigint->digit);
 175         bigint->digit = NULL;
 176 }
 177
 178 /** Get value of big integer.
 179  *
 180  * Allows to obtain the value of big integer, provided that it fits
 181  * into a small integer.
 182  *
 183  * @param bigint        Bigint to obtain value from.
 184  * @param dval          Place to store value.
 185  * @return              EOK on success, ELIMIT if bigint is too big to fit
 186  *                      to @a dval.
 187  */
 188 errno_t bigint_get_value_int(bigint_t *bigint, int *dval)
 189 {
 190         bigint_t vval, diff;
 191         size_t idx;
 192         int val;
 193         bool_t zf;
 194
 195 #ifdef DEBUG_BIGINT_TRACE
 196         printf("Get int value of bigint.\n");
 197 #endif
 198         val = 0;
 199         for (idx = 0; idx < bigint->length; ++idx) {
 200                 val = val * BIGINT_BASE + bigint->digit[idx];
 201         }
 202
 203         if (bigint->negative)
 204                 val = -val;
 205
 206         /* If the value did not fit @c val now contains garbage. Verify. */
 207         bigint_init(&vval, val);
 208
 209         bigint_sub(bigint, &vval, &diff);
 210         zf = bigint_is_zero(&diff);
 211
 212         bigint_destroy(&vval);
 213         bigint_destroy(&diff);
 214
 215         /* If the difference is not zero, the verification failed. */
 216         if (zf != b_true)
 217                 return EINVAL;
 218
 219         *dval = val;
 220         return EOK;
 221 }
 222
 223 /** Determine if bigint is zero.
 224  *
 225  * @param bigint        Big integer.
 226  * @return              b_true if @a bigint is zero, b_false otherwise.
 227  */
 228 bool_t bigint_is_zero(bigint_t *bigint)
 229 {
 230 #ifdef DEBUG_BIGINT_TRACE
 231         printf("Determine if bigint is zero.\n");
 232 #endif
 233         return (bigint->length == 0);
 234 }
 235
 236 /** Determine if bigint is negative.
 237  *
 238  * @param bigint        Big integer.
 239  * @return              b_true if @a bigint is negative, b_false otherwise.
 240  */
 241 bool_t bigint_is_negative(bigint_t *bigint)
 242 {
 243 #ifdef DEBUG_BIGINT_TRACE
 244         printf("Determine if bigint is negative\n");
 245 #endif
 246         /* Verify that we did not accidentaly introduce a negative zero. */
 247         assert(bigint->negative == b_false || bigint->length > 0);
 248
 249         return bigint->negative;
 250 }
 251
 252 /** Divide bigint by (unsigned) digit.
 253  *
 254  * @param a             Bigint dividend.
 255  * @param b             Divisor digit.
 256  * @param quot          Output bigint quotient.
 257  * @param rem           Output remainder digit.
 258  */
 259 void bigint_div_digit(bigint_t *a, bigint_word_t b, bigint_t *quot,
 260     bigint_word_t *rem)
 261 {
 262         size_t lbound;
 263         size_t idx;
 264         bigint_dword_t da, db;
 265         bigint_dword_t q, r;
 266
 267 #ifdef DEBUG_BIGINT_TRACE
 268         printf("Divide bigint by digit.\n");
 269 #endif
 270         lbound = a->length;
 271         bigint_alloc(quot, lbound);
 272
 273         quot->negative = a->negative;
 274
 275         r = 0;
 276         idx = lbound;
 277         while (idx > 0) {
 278                 --idx;
 279
 280                 da = a->digit[idx] + r * BIGINT_BASE;
 281                 db = b;
 282
 283                 q = da / db;
 284                 r = da % db;
 285
 286                 quot->digit[idx] = q;
 287         }
 288
 289         bigint_refine_len(quot);
 290         *rem = r;
 291 }
 292
 293 /** Add two big integers.
 294  *
 295  * The big integers @a a and @a b are added and the result is stored in
 296  * @a dest.
 297  *
 298  * @param a             First addend.
 299  * @param b             Second addend.
 300  * @param dest          Destination bigint.
 301  */
 302 void bigint_add(bigint_t *a, bigint_t *b, bigint_t *dest)
 303 {
 304 #ifdef DEBUG_BIGINT_TRACE
 305         printf("Add bigints.\n");
 306 #endif
 307         bigint_sign_comb(b_false, a, b_false, b, dest);
 308 }
 309
 310 /** Subtract two big integers.
 311  *
 312  * The big integers @a a and @a b are subtracted and the result is stored in
 313  * @a dest.
 314  *
 315  * @param a             Minuend.
 316  * @param b             Subtrahend.
 317  * @param dest          Destination bigint.
 318  */
 319 void bigint_sub(bigint_t *a, bigint_t *b, bigint_t *dest)
 320 {
 321 #ifdef DEBUG_BIGINT_TRACE
 322         printf("Subtract bigints.\n");
 323 #endif
 324         bigint_sign_comb(b_false, a, b_true, b, dest);
 325 }
 326
 327 /** Multiply two big integers.
 328  *
 329  * The big integers @a a and @a b are multiplied and the result is stored in
 330  * @a dest.
 331  *
 332  * @param a             First factor.
 333  * @param b             Second factor.
 334  * @param dest          Destination bigint.
 335  */
 336 void bigint_mul(bigint_t *a, bigint_t *b, bigint_t *dest)
 337 {
 338         size_t idx;
 339         bigint_t dprod;
 340         bigint_t sum;
 341         bigint_t tmp;
 342
 343 #ifdef DEBUG_BIGINT_TRACE
 344         printf("Multiply bigints.\n");
 345 #endif
 346         bigint_init(&sum, 0);
 347         for (idx = 0; idx < b->length; ++idx) {
 348                 bigint_shift_mul_dig(a, b->digit[idx], idx, &dprod);
 349                 bigint_add(&dprod, &sum, &tmp);
 350                 bigint_destroy(&dprod);
 351
 352                 bigint_destroy(&sum);
 353                 bigint_shallow_copy(&tmp, &sum);
 354         }
 355
 356         if (b->negative)
 357                 sum.negative = !sum.negative;
 358
 359         bigint_shallow_copy(&sum, dest);
 360 }
 361
 362 /** Convert bigint to string.
 363  *
 364  * @param bigint        Bigint to convert.
 365  * @param dptr          Place to store pointer to new string.
 366  */
 367 void bigint_get_as_string(bigint_t *bigint, char **dptr)
 368 {
 369         static const char digits[] = { '0', '1', '2', '3', '4', '5', '6',
 370                 '7', '8', '9' };
 371
 372         bigint_t val, tmp;
 373         bigint_word_t rem;
 374         size_t nchars;
 375         char *str;
 376         size_t idx;
 377
 378 #ifdef DEBUG_BIGINT_TRACE
 379         printf("Convert bigint to string.\n");
 380 #endif
 381         static_assert(BIGINT_BASE >= 10, "");
 382
 383         /* Compute number of characters. */
 384         nchars = 0;
 385
 386         if (bigint_is_zero(bigint) || bigint->negative)
 387                 nchars += 1; /* '0' or '-' */
 388
 389         bigint_clone(bigint, &val);
 390         while (bigint_is_zero(&val) != b_true) {
 391                 bigint_div_digit(&val, 10, &tmp, &rem);
 392                 bigint_destroy(&val);
 393                 bigint_shallow_copy(&tmp, &val);
 394
 395                 nchars += 1;
 396         }
 397         bigint_destroy(&val);
 398
 399         /* Store characters to array. */
 400
 401         str = malloc(nchars * sizeof(char) + 1);
 402         if (str == NULL) {
 403                 printf("Memory allocation failed.\n");
 404                 exit(1);
 405         }
 406
 407         if (bigint_is_zero(bigint)) {
 408                 str[0] = '0';
 409         } else if (bigint->negative) {
 410                 str[0] = '-';
 411         }
 412
 413         idx = 1;
 414         bigint_clone(bigint, &val);
 415         while (bigint_is_zero(&val) != b_true) {
 416                 bigint_div_digit(&val, 10, &tmp, &rem);
 417                 bigint_destroy(&val);
 418                 bigint_shallow_copy(&tmp, &val);
 419
 420                 str[nchars - idx] = digits[(int) rem];
 421                 ++idx;
 422         }
 423
 424         bigint_destroy(&val);
 425         str[nchars] = '\0';
 426         *dptr = str;
 427 }
 428
 429 /** Print bigint to standard output.
 430  *
 431  * @param bigint        Bigint to print.
 432  */
 433 void bigint_print(bigint_t *bigint)
 434 {
 435         char *str;
 436
 437 #ifdef DEBUG_BIGINT_TRACE
 438         printf("Print bigint.\n");
 439 #endif
 440         bigint_get_as_string(bigint, &str);
 441         printf("%s", str);
 442         free(str);
 443 }
 444
 445 /** Compute sign combination of two big integers.
 446  *
 447  * Of the big integers @a a and @a b each is optionally sign-reversed and then
 448  * they are added and the result is stored in @a dest.
 449  *
 450  * @param srf_a         First sign reversal flag.
 451  * @param a             First bigint.
 452  * @param srf_b         Second sign reversal flag.
 453  * @param b             Second bigint.
 454  * @param dest          Destination bigint.
 455  */
 456 static void bigint_sign_comb(bool_t srf_a, bigint_t *a, bool_t srf_b,
 457     bigint_t *b, bigint_t *dest)
 458 {
 459         bool_t neg_a, neg_b;
 460
 461 #ifdef DEBUG_BIGINT_TRACE
 462         printf("Signed combination of two bigints.\n");
 463 #endif
 464         /* Compute resulting signs of combination elements. */
 465         neg_a = (srf_a != a->negative);
 466         neg_b = (srf_b != b->negative);
 467
 468         if (neg_a == neg_b) {
 469                 bigint_add_abs(a, b, dest);
 470                 dest->negative = neg_a;
 471         } else {
 472                 bigint_sub_abs(a, b, dest);
 473                 dest->negative = (neg_a != dest->negative);
 474         }
 475 }
 476
 477 /** Add absolute values of two big integers.
 478  *
 479  * The absolute values of big integers @a a and @a b are added and the result
 480  * is stored in @a dest.
 481  *
 482  * @param a             First addend.
 483  * @param b             Second addend.
 484  * @param dest          Destination bigint.
 485  */
 486 static void bigint_add_abs(bigint_t *a, bigint_t *b, bigint_t *dest)
 487 {
 488         size_t lbound;
 489         size_t idx;
 490         bigint_dword_t da, db;
 491         bigint_dword_t tmp;
 492         bigint_word_t res, carry;
 493
 494 #ifdef DEBUG_BIGINT_TRACE
 495         printf("Add absolute values of bigints.\n");
 496 #endif
 497         /* max(a->length, b->length) + 1 */
 498         lbound = (a->length > b->length ? a->length : b->length) + 1;
 499         dest->negative = b_false;
 500
 501         bigint_alloc(dest, lbound);
 502         carry = 0;
 503
 504         for (idx = 0; idx < lbound; ++idx) {
 505                 da = idx < a->length ? a->digit[idx] : 0;
 506                 db = idx < b->length ? b->digit[idx] : 0;
 507
 508                 tmp = da + db + (bigint_word_t) carry;
 509
 510                 carry = (bigint_word_t) (tmp / BIGINT_BASE);
 511                 res = (bigint_word_t) (tmp % BIGINT_BASE);
 512
 513                 dest->digit[idx] = res;
 514         }
 515
 516         /* If our lbound is correct, carry must be zero. */
 517         assert(carry == 0);
 518
 519         bigint_refine_len(dest);
 520 }
 521
 522 /** Subtract absolute values of two big integers.
 523  *
 524  * The absolute values of big integers @a a and @a b are subtracted and the
 525  * result is stored in @a dest.
 526  *
 527  * @param a             Minuend.
 528  * @param b             Subtrahend.
 529  * @param dest          Destination bigint.
 530  */
 531 static void bigint_sub_abs(bigint_t *a, bigint_t *b, bigint_t *dest)
 532 {
 533         size_t lbound;
 534         size_t idx;
 535         bigint_dword_t da, db;
 536         bigint_dword_t tmp;
 537         bigint_word_t res, borrow;
 538
 539 #ifdef DEBUG_BIGINT_TRACE
 540         printf("Subtract absolute values of bigints.\n");
 541 #endif
 542         /* max(a->length, b->length) */
 543         lbound = a->length > b->length ? a->length : b->length;
 544
 545         bigint_alloc(dest, lbound);
 546         borrow = 0;
 547
 548         for (idx = 0; idx < lbound; ++idx) {
 549                 da = idx < a->length ? a->digit[idx] : 0;
 550                 db = idx < b->length ? b->digit[idx] : 0;
 551
 552                 if (da > db + borrow) {
 553                         tmp = da - db - borrow;
 554                         borrow = 0;
 555                 } else {
 556                         tmp = da + BIGINT_BASE - db - borrow;
 557                         borrow = 1;
 558                 }
 559
 560                 res = (bigint_word_t) tmp;
 561                 dest->digit[idx] = res;
 562         }
 563
 564         if (borrow != 0) {
 565                 /* We subtracted the greater number from the smaller. */
 566                 dest->negative = b_true;
 567
 568                 /*
 569                  * Now we must complement the number to get the correct
 570                  * absolute value. We do this by subtracting from 10..0
 571                  * (0 repeated lbound-times).
 572                  */
 573                 borrow = 0;
 574
 575                 for (idx = 0; idx < lbound; ++idx) {
 576                         da = 0;
 577                         db = dest->digit[idx];
 578
 579                         if (da > db + borrow) {
 580                                 tmp = da - db - borrow;
 581                                 borrow = 0;
 582                         } else {
 583                                 tmp = da + BIGINT_BASE - db - borrow;
 584                                 borrow = 1;
 585                         }
 586
 587                         res = (bigint_word_t) tmp;
 588                         dest->digit[idx] = res;
 589                 }
 590
 591                 /* The last step is the '1'. */
 592                 assert(borrow == 1);
 593         } else {
 594                 dest->negative = b_false;
 595         }
 596
 597         bigint_refine_len(dest);
 598 }
 599
 600 /** Multiply big integer by digit.
 601  *
 602  * @param a             Bigint factor.
 603  * @param b             Digit factor.
 604  * @param dest          Destination bigint.
 605  */
 606 static void bigint_shift_mul_dig(bigint_t *a, bigint_word_t b, size_t shift,
 607     bigint_t *dest)
 608 {
 609         size_t lbound;
 610         size_t idx;
 611
 612         bigint_dword_t da, db;
 613         bigint_dword_t tmp;
 614         bigint_word_t res, carry;
 615
 616 #ifdef DEBUG_BIGINT_TRACE
 617         printf("Multiply bigint by digit.\n");
 618 #endif
 619         /* Compute length bound and allocate. */
 620         lbound = a->length + shift + 1;
 621         bigint_alloc(dest, lbound);
 622
 623         /* Copy sign. */
 624         dest->negative = a->negative;
 625
 626         for (idx = 0; idx < shift; ++idx)
 627                 dest->digit[idx] = 0;
 628
 629         carry = 0;
 630         for (idx = 0; idx < lbound - shift; ++idx) {
 631                 da = idx < a->length ? a->digit[idx] : 0;
 632                 db = b;
 633
 634                 tmp = da * db + (bigint_word_t) carry;
 635
 636                 carry = (bigint_word_t) (tmp / BIGINT_BASE);
 637                 res = (bigint_word_t) (tmp % BIGINT_BASE);
 638
 639                 dest->digit[shift + idx] = res;
 640         }
 641
 642         /* If our lbound is correct, carry must be zero. */
 643         assert(carry == 0);
 644
 645         bigint_refine_len(dest);
 646 }
 647
 648 /** Allocate bigint of the given length.
 649  *
 650  * @param bigint        Bigint whose digit array should be allocated.
 651  * @param length        Length of array (also set as bigint length).
 652  */
 653 static void bigint_alloc(bigint_t *bigint, size_t length)
 654 {
 655         size_t a_length;
 656
 657 #ifdef DEBUG_BIGINT_TRACE
 658         printf("Allocate bigint digit array.\n");
 659 #endif
 660         /* malloc() sometimes cannot allocate blocks of zero size. */
 661         if (length == 0)
 662                 a_length = 1;
 663         else
 664                 a_length = length;
 665
 666         bigint->digit = malloc(a_length * sizeof(bigint_word_t));
 667         if (bigint->digit == NULL) {
 668                 printf("Memory allocation failed.\n");
 669                 exit(1);
 670         }
 671
 672         bigint->length = length;
 673 }
 674
 675 /** Adjust length field of bigint to be exact.
 676  *
 677  * When bigint is allocated with bigint_alloc() its length can be
 678  * imprecise (higher than actually number of non-zero digits).
 679  * Then this function is used to lower @c length to the exact value.
 680  */
 681 static void bigint_refine_len(bigint_t *bigint)
 682 {
 683 #ifdef DEBUG_BIGINT_TRACE
 684         printf("Refine bigint length.\n");
 685 #endif
 686         while (bigint->length > 0 && bigint->digit[bigint->length - 1] == 0)
 687                 bigint->length -= 1;
 688
 689         if (bigint->length == 0)
 690                 bigint->negative = b_false;
 691 }