biginteger_utils.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 // Private Function Impl
  32
  33 BigInteger CreateZeroBigInt()
  34 {
  35   BigInteger temp;
  36   temp.Sign = Undefined;
  37   temp.AbsValStart = NULL;
  38   temp.AbsValEnd = NULL;
  39   temp.Count = 0;
  40
  41   return temp;
  42 }
  43
  44 BigUnsignedInteger* InitBUint(unsigned int value)
  45 {
  46   BigUnsignedInteger* bigUint = malloc(sizeof(BigUnsignedInteger));
  47   bigUint->Value = value;
  48
  49   return bigUint;
  50 }
  51
  52 BigUnsignedInteger* CopyBigInteger(BigInteger source, BigInteger* dest, BigUnsignedInteger* start, int count)
  53 {
  54   BigUnsignedInteger* node = (start == NULL) ? source.AbsValStart : start;
  55
  56   do {
  57         PushEndNode(dest, node->Value);
  58         if (--count == 0)
  59           break;
  60   } while ((node = node->Next) != NULL);
  61
  62   return node;
  63 }
  64
  65 BigUnsignedInteger* CopyBigIntegerFromEnd(BigInteger source, BigInteger* dest, BigUnsignedInteger* start, int count)
  66 {
  67   BigUnsignedInteger* node = (start == NULL) ? source.AbsValEnd : start;
  68
  69   do {
  70         PushFrontNode(dest, node->Value);
  71         if (--count == 0)
  72           break;
  73   } while ((node = node->Previous) != NULL);
  74
  75   return node;
  76 }
  77
  78 BigUnsignedInteger* ReplaceFromEnd(BigInteger* source, BigInteger slice, BigUnsignedInteger* start, int count)
  79 {
  80   if (start == NULL) {
  81         source->AbsValEnd = slice.AbsValEnd;
  82         start = source->AbsValEnd;
  83   }     else {
  84         start->Previous = slice.AbsValEnd;
  85   }
  86
  87   BigUnsignedInteger* endNode = start;
  88   int i;
  89   for (i = 0; i < count; i++)
  90         endNode = endNode->Previous;
  91
  92   if (endNode != NULL) {
  93         endNode->Next = slice.AbsValStart;
  94   } else {
  95         source->AbsValStart = slice.AbsValStart;
  96   }
  97
  98   source->Count -= count;
  99   source->Count += slice.Count;
 100
 101   return slice.AbsValEnd->Previous;
 102 }
 103
 104 void Clean(BigInteger* b)
 105 {
 106   BigUnsignedInteger* node = b->AbsValEnd;
 107   if (node->Value != 0)
 108         return;
 109
 110   while (node->Value == 0) {
 111         BigUnsignedInteger* toFree = node;
 112         node = node->Previous;
 113         free(toFree);
 114   }
 115
 116   // Erase things up
 117   b->AbsValEnd = node;
 118   node->Next = NULL;
 119 }
 120
 121 // base = part1 * 10000^N  + part2
 122 void SplitBigInteger(int N, BigInteger base, BigInteger* part1, BigInteger* part2)
 123 {
 124   // In case N is odd part2 has a 1 more node than part1
 125   int count = (N % 2) == 0 ? N/2 : N/2 + 1;
 126
 127   if (base.Count <= count) {
 128         // Only set part2, part1 == 0
 129         CopyBigInteger(base, part2, NULL, -1);
 130         part2->Sign = Positive;
 131         return;
 132   }
 133
 134   BigUnsignedInteger* node = CopyBigInteger(base, part2, NULL, count);
 135   part2->Sign = Positive;
 136
 137   CopyBigInteger(base, part1, node->Next, -1);
 138   part1->Sign = Positive;
 139
 140 }
 141
 142 void MultiplyByBase(BigInteger* b, int k)
 143 {
 144   int i = 0;
 145   for (; i < k; i++)
 146         PushFrontNode(b, 0);
 147 }
 148
 149 void PrependNode(BigUnsignedInteger* b1, BigUnsignedInteger* b2)
 150 {
 151   b1->Next = b2;
 152   b2->Previous = b1;
 153 }
 154
 155 // Used to push_front a value
 156 void PushFrontNode(BigInteger* bigInt, unsigned int value)
 157 {
 158   BigUnsignedInteger* bigUint = InitBUint(value);
 159
 160   // Do the magic swapping
 161   if (bigInt->AbsValStart != NULL)
 162         PrependNode(bigUint, bigInt->AbsValStart);
 163   // Update BigInt's head field
 164   bigInt->AbsValStart = bigUint;
 165
 166   // If it's the first node added, correctly set bigInt->AbsValEnd
 167   if (bigInt->AbsValEnd == NULL)
 168         bigInt->AbsValEnd = bigUint;
 169
 170   bigInt->Count++;
 171 }
 172
 173 void PushEndNode(BigInteger* bigInt, unsigned int value)
 174 {
 175   BigUnsignedInteger* buint = InitBUint(value);
 176
 177   // Do the magic swapping
 178   if (bigInt->AbsValEnd != NULL)
 179         PrependNode(bigInt->AbsValEnd, buint);
 180   // Update BigInt's head field
 181   bigInt->AbsValEnd = buint;
 182
 183   // If it's the first node added, correctly set bigInt->AbsValStart
 184   if (bigInt->AbsValStart == NULL)
 185         bigInt->AbsValStart = buint;
 186
 187   bigInt->Count++;
 188 }
 189
 190 // Used to insert a node in the *middle* of the BigInt.
 191 // It Do *not* check if we reproduce Push(Front|End)Node behavior
 192 // Use Push(Front|End)Node if you intend to do what these functions are meant for
 193 void InsertNode(BigInteger* bigInt, BigUnsignedInteger* next, unsigned int value)
 194 {
 195   BigUnsignedInteger* buint = InitBUint(value);
 196   BigUnsignedInteger* temp  = next->Previous;
 197
 198   PrependNode(buint, next);
 199   PrependNode(temp, buint);
 200
 201   bigInt->Count++;
 202 }
 203
 204 unsigned int GetValueAtFromEnd(BigInteger b, int index)
 205 {
 206   BigUnsignedInteger* node = b.AbsValEnd;
 207
 208   int i = 0;
 209   for (; i < index; i++) {
 210         if (node == NULL)
 211           return 0;
 212         node = node->Previous;
 213   }
 214   return node->Value;
 215 }
 216
 217 BigInteger mulBigIntByScalar(BigUnsignedInteger* big, unsigned int multiplier)
 218 {
 219   BigInteger temp = CreateZeroBigInt();
 220   unsigned int carry = 0;
 221
 222   while (big != NULL) {
 223         unsigned int r = big->Value * multiplier + carry;
 224         carry = r / BASE;
 225         PushEndNode(&temp, r % BASE);
 226
 227         big = big->Next;
 228   }
 229   if (carry != 0)
 230         PushEndNode(&temp, carry);
 231
 232   return temp;
 233 }
 234
 235 // Returns b^n
 236 BigInteger powBigInt(BigInteger b, int n)
 237 {
 238   BigInteger result = b;
 239
 240   while ((n & 0x1) == 0) {
 241         result = mulBigInt(result, result);
 242         n /= 2;
 243   }
 244   if (n != 1) {
 245         int i = n;
 246         for (; i >= 1; i--)
 247           result = mulBigInt(result, b);
 248   }
 249
 250   return result;
 251 }
 252
 253
 254 // End Private Function Impl