git.infodrom.org Git - infodrom/dtaus/blob - bigint.c

   1 /*
   2     bigint.c - Manage big positive integer numbers
   3     Copyright (c) 1996,2001,5  Martin Schulze <joey@infodrom.org>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with this program; if not, write to the Free Software
  17     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18
  19     $Id$
  20  */
  21
  22 #include "bigint.h"
  23 #include <stdio.h>
  24 #include <string.h>
  25 #include <malloc.h>
  26
  27 bigint bigint_add(bigint a, bigint b)
  28 {
  29   int i;
  30   unsigned long int tmp;
  31   bigint c;
  32
  33   for (i=0; i<BIGINT_LEN; i++) {
  34     tmp = a.val[i] + b.val[i];
  35     if (tmp >= BIGINT_MAX) {
  36       c.val[i] = tmp - BIGINT_MAX;
  37       if (i<BIGINT_LEN-1)
  38         a.val[i+1]++;
  39       else
  40         fprintf(stderr, "Overflow in bigint addition.\n");
  41     } else
  42       c.val[i] = tmp;
  43   }
  44   return c;
  45 }
  46
  47 bigint bigint_sub(bigint a, bigint b)
  48 {
  49   unsigned long int tmp;
  50   int t;
  51   int i;
  52   int cmp = bigint_cmp(a,b);
  53   bigint rem = bigint_int(0);;
  54
  55   if (cmp == -1) {
  56     fprintf(stderr, "Error in bigint_sub: result is negative.\n");
  57     return bigint_int(0);
  58   }
  59   if (cmp == 0)
  60     return bigint_int(0);
  61
  62   for (i=0;i<BIGINT_LEN;i++) {
  63     if (a.val[i] >= b.val[i]) {
  64       a.val[i] = a.val[i] - b.val[i];
  65       continue;
  66     }
  67     tmp = b.val[i];
  68     tmp = tmp - a.val[i];
  69     a.val[i] = 0;
  70     t = i;
  71     while (1) {
  72       if (t+1 >= BIGINT_LEN) {
  73         fprintf(stderr, "Error in bigint_sub.\n");
  74         return bigint_int(0);
  75       }
  76       if ( a.val[t+1] == 0 ) {
  77         t++;
  78         continue;
  79       }
  80       a.val[t+1] = a.val[t+1] - 1;
  81       while(t >= 0) {
  82         rem = bigint_add(rem, bigint_int(a.val[t]));
  83         a.val[t] = BIGINT_MAX - 1;
  84         t--;
  85       }
  86       a.val[i] = a.val[i] - tmp;
  87       a = bigint_add(a, bigint_int(1));
  88       a = bigint_add(a, rem);
  89       break;
  90     }
  91   }
  92
  93   return a;
  94 }
  95
  96 bigint bigint_int(int num)
  97 {
  98   bigint x;
  99   int i;
 100
 101   if (num < 0) {
 102     fprintf(stderr, "Trying to assign negative value to bigint.\n");
 103     num = 0;
 104   }
 105
 106   for (i=0; i<BIGINT_LEN; i++) x.val[i] = 0L;
 107   if (num < BIGINT_MAX)
 108     x.val[0] = num;
 109   else {
 110     x.val[0] = num-BIGINT_MAX;
 111     x.val[1] = num/BIGINT_MAX;
 112   }
 113
 114   return x;
 115 }
 116
 117 bigint bigint_string(char *s)
 118 {
 119   char tmp[BIGINT_PREC+1];
 120   bigint a;
 121   int i;
 122   char *cp, *x;
 123
 124   for (i=0; i<BIGINT_LEN; i++) a.val[i] = 0L;
 125   if ((x = (char *)malloc(strlen(s)+1))) {
 126     strcpy(x, s);
 127     for (i=0; i<BIGINT_LEN; i++) {
 128       if (strlen(x)) {
 129         cp = x;
 130         if (strlen(x) > BIGINT_PREC)
 131           cp += (strlen(x) - BIGINT_PREC);
 132         strcpy(tmp, cp);
 133         *cp = '\0';
 134         sscanf(tmp, "%lu", &a.val[i]);
 135       }
 136     }
 137     free (x);
 138   }
 139
 140   return a;
 141 }
 142
 143 void bigint_sprintf (char *res, char *format, bigint a)
 144 {
 145   char s[(BIGINT_PREC*BIGINT_LEN)+1];
 146   char tmp[BIGINT_PREC+1];
 147   char form[6];
 148   int i, max;
 149
 150   memset (s, 0, sizeof(s));
 151   sprintf(form, "%%0%dlu", BIGINT_PREC);
 152   max = BIGINT_LEN;
 153   for (;max>0 && !a.val[max-1];max--);
 154   if (max == 0) s[0] = '0';
 155   for (i=0; i<max; i++) {
 156     if (i<max-1)
 157       sprintf(tmp, form, a.val[i]);
 158     else
 159       sprintf(tmp, "%lu", a.val[i]);
 160     sprintf (res, "%s%s", tmp, s);
 161     sprintf (s, "%s", res);
 162   }
 163   sprintf (res, format, s);
 164 }
 165
 166 int bigint_cmp(bigint a, bigint b)
 167 {
 168   int i;
 169
 170   for (i=BIGINT_LEN-1; i>=0; i--) {
 171     if (a.val[i] > b.val[i])
 172       return 1;
 173     if (a.val[i] < b.val[i])
 174       return -1;
 175     if (a.val[i] == b.val[i])
 176       continue;
 177   }
 178
 179   return 0;
 180 }