biginteger.c

   1 /* Copyright (c) 2008 Jérémie Laval, Marine Jourdain
   2
   3  * Permission is hereby granted, free of charge, to any person obtaining a copy
   4  * of this software and associated documentation files (the "Software"), to deal
   5  * in the Software without restriction, including without limitation the rights
   6  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7  * copies of the Software, and to permit persons to whom the Software is
   8  * furnished to do so, subject to the following conditions:
   9
  10  * The above copyright notice and this permission notice shall be included in
  11  * all copies or substantial portions of the Software.
  12
  13  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  19  * THE SOFTWARE.
  20  *
  21  */
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <math.h>
  26 #include <string.h>
  27
  28 #include "biginteger.h"
  29
  30 // Private Function Impl
  31
  32 #define ATOUI(str) ((unsigned int)strtoul(buffer, NULL, 10))
  33
  34 BigInteger CreateZeroBigInt()
  35 {
  36   BigInteger temp;
  37   temp.Sign = Undefined;
  38   temp.AbsValStart = NULL;
  39   temp.AbsValEnd = NULL;
  40   temp.Count = 0;
  41
  42   return temp;
  43 }
  44
  45 BigUnsignedInteger* InitBUint(unsigned int value)
  46 {
  47   BigUnsignedInteger* bigUint = malloc(sizeof(BigUnsignedInteger));
  48   bigUint->Value = value;
  49
  50   return bigUint;
  51 }
  52
  53 void PrependNode(BigUnsignedInteger* b1, BigUnsignedInteger* b2)
  54 {
  55   b1->Next = b2;
  56   b2->Previous = b1;
  57 }
  58
  59 // Used to push_front a value
  60 void PushFrontNode(BigInteger* bigInt, unsigned int value)
  61 {
  62   BigUnsignedInteger* bigUint = InitBUint(value);
  63
  64   // Do the magic swapping
  65   if (bigInt->AbsValStart != NULL)
  66         PrependNode(bigUint, bigInt->AbsValStart);
  67   // Update BigInt's head field
  68   bigInt->AbsValStart = bigUint;
  69
  70   // If it's the first node added, correctly set bigInt->AbsValEnd
  71   if (bigInt->AbsValEnd == NULL)
  72         bigInt->AbsValEnd = bigUint;
  73
  74   bigInt->Count++;
  75 }
  76
  77 //Used to push_end a value
  78 void PushEndNode(BigInteger* bigInt, unsigned int value)
  79 {
  80   BigUnsignedInteger* buint = InitBUint(value);
  81
  82   // Do the magic swapping
  83   if (bigInt->AbsValEnd != NULL)
  84         PrependNode(bigInt->AbsValEnd, buint);
  85   // Update BigInt's tail field
  86   bigInt->AbsValEnd = buint;
  87
  88   // If it's the first node added, correctly set bigInt->AbsValStart
  89   if (bigInt->AbsValStart == NULL)
  90         bigInt->AbsValStart = buint;
  91
  92   bigInt->Count++;
  93 }
  94
  95 // Used to insert a node in the *middle* of the BigInt.
  96 // It Do *not* check if we reproduce Push(Front|End)Node behavior
  97 // Use Push(Front|End)Node if you intend to do what these functions are meant for
  98 void InsertNode(BigInteger* bigInt, BigUnsignedInteger* next, unsigned int value)
  99 {
 100   BigUnsignedInteger* buint = InitBUint(value);
 101   BigUnsignedInteger* temp  = next->Previous;
 102
 103   PrependNode(buint, next);
 104   PrependNode(temp, buint);
 105
 106   bigInt->Count++;
 107
 108 }
 109
 110 // End Private Function Impl
 111
 112
 113
 114 // Public Function Impl
 115
 116 BigInteger newBigInteger(char* desc)
 117 {
 118   BigInteger   newbigint=CreateZeroBigInt();
 119   //iterative variable
 120   int          i;
 121   //array of character where is stored a part of the total list of character
 122   char         temp[5];
 123   //temporary variable where is stored the integer incoming from the transformation 'character to interger'
 124   unsigned int tempint;
 125
 126   //loop to build the double linked list until we reach the last group of 4 characters
 127   for(i = strlen(desc)-5; i >= 0; i = i - 4) {
 128           strncpy(temp, desc + i,4);
 129           temp[5] = '\0';
 130           tempint = atoi(temp);
 131           PushEndNode(&newbigint,tempint);
 132   }
 133
 134   //test if the number of digit of the number is divisible by 4. if it's not the case, it completes with the rest
 135   if (i < 0) {
 136           strncpy(temp, desc, i + 4);
 137           temp[i+5] = '\0';
 138           tempint = atoi(temp);
 139           PushEndNode(&newbigint, tempint);
 140   }
 141
 142   return newbigint;
 143 }
 144
 145 void printBigInteger(BigInteger bint)
 146 {
 147
 148 }
 149
 150 Boolean isNull(BigInteger bint)
 151 {
 152   return false;
 153 }
 154
 155 int signBigInt(BigInteger bint)
 156 {
 157   return -1;
 158 }
 159
 160 Boolean equalsBigInt(BigInteger b1, BigInteger b2)
 161 {
 162   return false;
 163 }
 164
 165 int compareBigInt(BigInteger b1, BigInteger b2)
 166 {
 167
 168 }
 169
 170 BigInteger sumBigInt(BigInteger b1, BigInteger b2)
 171 {
 172   //test if b2 is negative
 173   if(b1.Sign==Positive && b2.Sign==Negative){
 174     b2.Sign=Positive;
 175     return diffBigInt(b1,b2);
 176   }else{
 177     //test if b1 is negative
 178     if(b1.Sign==Negative && b2.Sign==Positive){
 179       b1.Sign=Positive;
 180       return diffBigInt(b2,b1);
 181     }
 182   }
 183   //variable which will be the result of the sum
 184   BigInteger Sum = CreateZeroBigInt();
 185   //temporary pointer  over b1
 186   BigUnsignedInteger* p1 = b1.AbsValStart;
 187   //temporary pointer over b2
 188   BigUnsignedInteger* p2 = b2.AbsValStart;
 189   //test if the two BigInteger are null
 190
 191   if (b1.Sign == Undefined && b2.Sign == Undefined){
 192     return Sum;
 193   }else{
 194     //test if one of the 2 BigInt is null
 195     if (b1.Sign == Undefined && b2.Sign != Undefined)
 196       Sum = b2;
 197     else if (b2.Sign == Undefined && b1.Sign != Undefined)
 198         Sum = b1;
 199
 200   }
 201
 202   //test if the 2 BigInt are both positive or both negative
 203   int carry=0;
 204   //do the addition until we reach the last node of one of the two numbers, or both
 205   while(p1 != NULL || p2 != NULL){
 206     unsigned int s=(p1==NULL ? 0 : p1->Value) + (p2==NULL ? 0 : p2->Value) + carry;
 207     PushEndNode(&Sum, s%10000);
 208     //compute the carry
 209     if(s >= 10000)
 210       //if the sum exceed 10000
 211       carry=1;
 212     else
 213       carry=0;
 214
 215     if (p1 == NULL) {//test if p2 is longer than p1
 216       p2=p2->Next;
 217     }else if (p2==NULL) { //test if p1 is longer than p2
 218       p1=p1->Next;
 219     }
 220   }
 221   if(carry==1){
 222     PushEndNode(&Sum,1);
 223   }
 224   //if the two numbers are both negative
 225   if(b1.Sign == Negative && b2.Sign == Negative)
 226       Sum.Sign=Negative;
 227
 228   return Sum;
 229 }
 230
 231 BigInteger diffBigInt(BigInteger b1, BigInteger b2)
 232 {
 233
 234
 235
 236
 237   return CreateZeroBigInt();
 238 }
 239
 240 // End Public Function Impl