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   int i;//iterative variable
 120   char temp[5];//array of character where islu
 121   unsigned int tempint;//temporary variable where is stored the integer incoming from the transformation 'character to interger'
 122
 123   for(i=strlen(desc)-5;i>=0;i=i-4){//loop to build the double linked list until we reach the last group of 4 characters
 124         strncpy(temp,desc + i,4);
 125         temp[5]='\0';
 126         tempint=atoi(temp);
 127         PushEndNode(&newbigint,tempint);
 128   }
 129   if(i<0){//test if the number of digit of the number is divisible by 4. if it's not the case, it completes with the rest
 130         strncpy(temp,desc,i+4);
 131         temp[i+5]='\0';
 132         tempint=atoi(temp);
 133         PushEndNode(&newbigint,tempint);
 134   }
 135   return newbigint;
 136 }
 137
 138 void printBigInteger(BigInteger bint)
 139 {
 140
 141 }
 142
 143 Boolean isNull(BigInteger bint)
 144 {
 145
 146 }
 147
 148 int signBigInt(BigInteger bint)
 149 {
 150
 151 }
 152
 153 Boolean equalsBigInt(BigInteger b1, BigInteger b2)
 154 {
 155
 156 }
 157
 158 int compareBigInt(BigInteger b1, BigInteger b2)
 159 {
 160
 161 }
 162
 163 BigInteger sumBigInt(BigInteger b1, BigInteger b2)
 164 {
 165   BigInterger Sum=CreateZeroBigInt();//variable which will be the result of the sum
 166   BigInteger p1=b1;//temporary pointer  over b1
 167   BigInterger p2=b2;//temporary pointer over b2
 168   int carry=0;//the carry can be equal to 0 or 1
 169   while(p1!=NULL && p2!=NULL){//do the addition until we reach the last node of one of the two numbers, or both
 170     PushFrontNode(&Sum, (p1->value + p2->value + carry)%10000);
 171     if(p1->value + p2->value>=10000)//compute the carry
 172       carry=1;
 173     else
 174       carry=0;
 175   p1=p1->next;
 176   p2=p2->next;
 177   }
 178   if(p1==NULL && p2!=NULL)
 179     PushFrontNode(&Sum,p2->value);
 180   else{
 181     if(p2==NULL && p1!=NULL)
 182       PushFrontNode(&Sum,p1->value);
 183   }
 184 }
 185
 186 BigInteger diffBigInt(BigInteger b1, BigInteger b2)
 187 {
 188
 189 }
 190
 191 // End Public Function Impl