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 #include "biginteger_utils.h"
  30
  31 // Public Function Impl
  32
  33 BigInteger newBigInteger(char* desc)
  34 {
  35   BigInteger   newbigint=CreateZeroBigInt();
  36   //iterative variable
  37   int          i;
  38   //array of character where is stored a part of the total list of character
  39   char         temp[5];
  40   //temporary variable where is stored the integer incoming from the transformation 'character to interger'
  41   unsigned int tempint;
  42
  43   //loop to build the double linked list until we reach the last group of 4 characters
  44   for(i = strlen(desc)-5; i >= 0; i = i - 4) {
  45           strncpy(temp, desc + i,4);
  46           temp[5] = '\0';
  47           tempint = atoi(temp);
  48           PushEndNode(&newbigint,tempint);
  49   }
  50
  51   //test if the number of digit of the number is divisible by 4. if it's not the case, it completes with the rest
  52   if (i < 0) {
  53           strncpy(temp, desc, i + 4);
  54           temp[i+5] = '\0';
  55           tempint = atoi(temp);
  56           PushEndNode(&newbigint, tempint);
  57   }
  58
  59   return newbigint;
  60 }
  61
  62 void printBigInteger(BigInteger bint)
  63 {
  64   if (bint.Sign == Negative)
  65         printf("%c", '-');
  66
  67   BigUnsignedInteger* node = bint.AbsValEnd;
  68
  69   do {
  70         if (node != bint.AbsValEnd)
  71           printf("%04u", node->Value);
  72         else
  73           printf("%u", node->Value);
  74   } while((node = node->Previous) != NULL);
  75
  76   printf("\n");
  77 }
  78
  79 Boolean isNull(BigInteger bint)
  80 {
  81   return false;
  82 }
  83
  84 int signBigInt(BigInteger bint)
  85 {
  86   return -1;
  87 }
  88
  89 Boolean equalsBigInt(BigInteger b1, BigInteger b2)
  90 {
  91   return false;
  92 }
  93
  94 /* b1 > b2 => 1
  95  * b1 < b2 => -1
  96  * b1 == b2 => 0
  97  */
  98 int compareBigInt(BigInteger b1, BigInteger b2)
  99 {
 100   //trivial cases
 101   //test if only one of the two big integer is negative
 102   if (b1.Sign == Positive && b2.Sign == Negative)
 103     return 1;
 104   else if (b1.Sign == Negative && b2.Sign == Positive)
 105     return -1;
 106   //test if one of the two big int is shorter than the other
 107   if (b1.Count != b2.Count)
 108     return b1.Count > b2.Count ? 1 : -1;
 109   //if the two big int are null
 110   if(b1.Sign==Undefined && b2.Sign==Undefined)
 111     return 0;
 112   //temporary pointers to go through b1 and b2
 113   BigUnsignedInteger* end1=b1.AbsValEnd;
 114   BigUnsignedInteger* end2=b2.AbsValEnd;
 115
 116   //general case
 117   //look for the first group of 4 digits which is different according the 2 bigint
 118   while(end1->Value == end2->Value && end1!=NULL){
 119     end1 = end1->Previous;
 120     end2 = end2->Previous;
 121   }
 122
 123   //test if the 2 bigint are equals (we reach a step where all the nodes before are equals)
 124   if(end1 == NULL)
 125     return 0;
 126
 127   return end1->Value > end2->Value ? 1 : -1;
 128 }
 129
 130 // End Public Function Impl