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   int i = 0;
  81
  82   if (start == NULL) {
  83         start = source->AbsValEnd;
  84         source->AbsValEnd = slice.AbsValEnd;
  85         i = 1;
  86   }     else {
  87         /*start->Previous = slice.AbsValEnd;
  88           slice.AbsValEnd->Next = start;*/
  89         PrependNode(slice.AbsValEnd, start);
  90   }
  91
  92   BigUnsignedInteger* endNode = start;
  93
  94   for (; i <= count && endNode != NULL; i++)
  95         endNode = endNode->Previous;
  96
  97   printf("endNode is null %d\n", endNode == NULL);
  98   if (endNode != NULL) {
  99         /*endNode->Next = slice.AbsValStart;
 100           slice.AbsValStart->Previous = endNode;*/
 101         PrependNode(endNode, slice.AbsValStart);
 102   } else {
 103         source->AbsValStart = slice.AbsValStart;
 104   }
 105
 106   source->Count -= count;
 107   source->Count += slice.Count;
 108
 109   return slice.AbsValEnd->Previous;
 110 }
 111
 112 void Clean(BigInteger* b)
 113 {
 114   BigUnsignedInteger* node = b->AbsValEnd;
 115   if (node->Value != 0)
 116         return;
 117
 118   while (node->Value == 0) {
 119         BigUnsignedInteger* toFree = node;
 120         node = node->Previous;
 121         free(toFree);
 122         b->Count--;
 123   }
 124
 125   // Erase things up
 126   b->AbsValEnd = node;
 127   node->Next = NULL;
 128 }
 129
 130 // base = part1 * 10000^N  + part2
 131 void SplitBigInteger(int N, BigInteger base, BigInteger* part1, BigInteger* part2)
 132 {
 133   // In case N is odd part2 has a 1 more node than part1
 134   int count = (N % 2) == 0 ? N/2 : N/2 + 1;
 135
 136   if (base.Count <= count) {
 137         // Only set part2, part1 == 0
 138         CopyBigInteger(base, part2, NULL, -1);
 139         part2->Sign = Positive;
 140         return;
 141   }
 142
 143   BigUnsignedInteger* node = CopyBigInteger(base, part2, NULL, count);
 144   part2->Sign = Positive;
 145
 146   CopyBigInteger(base, part1, node->Next, -1);
 147   part1->Sign = Positive;
 148
 149 }
 150
 151 void MultiplyByBase(BigInteger* b, int k)
 152 {
 153   int i = 0;
 154   for (; i < k; i++)
 155         PushFrontNode(b, 0);
 156 }
 157
 158 void PrependNode(BigUnsignedInteger* b1, BigUnsignedInteger* b2)
 159 {
 160   b1->Next = b2;
 161   b2->Previous = b1;
 162 }
 163
 164 // Used to push_front a value
 165 void PushFrontNode(BigInteger* bigInt, unsigned int value)
 166 {
 167   BigUnsignedInteger* bigUint = InitBUint(value);
 168
 169   // Do the magic swapping
 170   if (bigInt->AbsValStart != NULL)
 171         PrependNode(bigUint, bigInt->AbsValStart);
 172   // Update BigInt's head field
 173   bigInt->AbsValStart = bigUint;
 174
 175   // If it's the first node added, correctly set bigInt->AbsValEnd
 176   if (bigInt->AbsValEnd == NULL)
 177         bigInt->AbsValEnd = bigUint;
 178
 179   bigInt->Count++;
 180 }
 181
 182 void PushEndNode(BigInteger* bigInt, unsigned int value)
 183 {
 184   BigUnsignedInteger* buint = InitBUint(value);
 185
 186   // Do the magic swapping
 187   if (bigInt->AbsValEnd != NULL)
 188         PrependNode(bigInt->AbsValEnd, buint);
 189   // Update BigInt's head field
 190   bigInt->AbsValEnd = buint;
 191
 192   // If it's the first node added, correctly set bigInt->AbsValStart
 193   if (bigInt->AbsValStart == NULL)
 194         bigInt->AbsValStart = buint;
 195
 196   bigInt->Count++;
 197 }
 198
 199 void PopFrontNode(BigInteger* bigInt)
 200 {
 201   bigInt->Count--;
 202
 203   BigUnsignedInteger* node = bigInt->AbsValStart;
 204   node->Next->Previous = NULL;
 205   bigInt->AbsValStart = node->Next;
 206
 207   free(node);
 208 }
 209
 210 void PopEndNode(BigInteger* bigInt)
 211 {
 212   bigInt->Count--;
 213
 214   BigUnsignedInteger* node = bigInt->AbsValEnd;
 215   node->Previous->Next = NULL;
 216   bigInt->AbsValEnd= node->Previous;
 217
 218   free(node);
 219 }
 220
 221
 222 // Used to insert a node in the *middle* of the BigInt.
 223 // It Do *not* check if we reproduce Push(Front|End)Node behavior
 224 // Use Push(Front|End)Node if you intend to do what these functions are meant for
 225 void InsertNode(BigInteger* bigInt, BigUnsignedInteger* next, unsigned int value)
 226 {
 227   BigUnsignedInteger* buint = InitBUint(value);
 228   BigUnsignedInteger* temp  = next->Previous;
 229
 230   PrependNode(buint, next);
 231   PrependNode(temp, buint);
 232
 233   bigInt->Count++;
 234 }
 235
 236 unsigned int GetValueAtFromEnd(BigInteger b, int index)
 237 {
 238   BigUnsignedInteger* node = b.AbsValEnd;
 239
 240   int i = 0;
 241   for (; i < index; i++) {
 242         if (node == NULL)
 243           return 0;
 244         node = node->Previous;
 245   }
 246   return node->Value;
 247 }
 248
 249 BigInteger mulBigIntByScalar(BigUnsignedInteger* big, unsigned int multiplier)
 250 {
 251   BigInteger temp = CreateZeroBigInt();
 252   unsigned int carry = 0;
 253
 254   // Multiplied bigint supposed to be positive
 255   temp.Sign = multiplier < 0 ? Negative : Positive;
 256
 257   while (big != NULL) {
 258         unsigned int r = big->Value * multiplier + carry;
 259         carry = r / BASE;
 260         PushEndNode(&temp, r % BASE);
 261
 262         big = big->Next;
 263   }
 264   if (carry != 0)
 265         PushEndNode(&temp, carry);
 266
 267   return temp;
 268 }
 269
 270 // Returns b^n
 271 BigInteger powBigInt(BigInteger b, int n)
 272 {
 273   BigInteger result = b;
 274
 275   while ((n & 0x1) == 0) {
 276         result = mulBigInt(result, result);
 277         n /= 2;
 278   }
 279   if (n != 1) {
 280         int i = n;
 281         for (; i >= 1; i--)
 282           result = mulBigInt(result, b);
 283   }
 284
 285   return result;
 286 }
 287
 288
 289 // End Private Function Impl