Jens Rohler: prevent negative numbers
[infodrom/dtaus] / 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 }