I just finished writing an adder for a bigint struct I made. It seems as if it works. The thing is is that I have ended up with about 80 lines of code just to add 2 numbers together. I'm guessing that there may be an easier way to do this, as this is pretty much just something I invented off the top of my head. If anyone has any suggestions on how to make it simpler/faster/better, or can spot a bug in it let us know.
Cheers.
Bignum.c:
Code:
#include "bignum.h"
bigint make_int(Uint8 size)
{
bigint new_int;
new_int.byte = (Uint8*)calloc(size, 1);
new_int.size = size;
return new_int;
}
void reset_int(bigint i)
{
memset(i.byte, 0, i.size);
}
void set_int(bigint num, Uint32 set_to)
{
int i;
Uint8 *byte = num.byte;
for(i=0; i<4; i++, byte++)
{
*byte = set_to & 255;
set_to >>= 8;
}
}
bigint resize_bigint(bigint old, Uint8 size)
{
bigint result = make_int(size);
Uint8 *src = old.byte;
Uint8 *dst = result.byte;
Uint8 i;
for(i=0; i<old.size; i++, src++, dst++)
*dst = *src;
free(old.byte);
return result;
}
//******************** ADDER ********************************//
bigint add_bigint(bigint a, bigint b)
{
Uint8 big = MAX(a.size, b.size);
Uint8 sml = MIN(a.size, b.size);
bigint result = make_int(big);
Uint8 *a_ptr = (a.size > b.size)? a.byte: b.byte;
Uint8 *b_ptr = (a.size > b.size)? b.byte: a.byte;
Uint8 *r_ptr = result.byte;
Uint8 carry=0;
Uint8 count=0;
// Add bytes up until the smallest bignum's size
for(; count<sml; count++)
{
carry = add_byte(a_ptr, b_ptr, r_ptr, carry);
a_ptr++; b_ptr++; r_ptr++;
}
// If one number was bigger continue adding carry, or copying bytes
for(; count<big; count++)
{
if(carry)
carry = add_carry(a_ptr, r_ptr);
else
*r_ptr = *a_ptr;
r_ptr++; a_ptr++;
}
// If there was a carry on the last byte, then resize result and add carry
if(carry)
{
result = resize_bigint(result, big+1);
r_ptr = result.byte + big;
*r_ptr = 1;
}
return result;
}
Uint8 add_byte(Uint8 *a, Uint8 *b, Uint8 *r, Uint8 carry)
{
Uint8 i, num = 0;
Uint8 bit = 1;
for(i=0; i<CHAR_BIT; i++)
{
num = 0;
if(*a & bit) num++;
if(*b & bit) num++;
if( carry ) num++;
if(num & 1) *r |= bit;
carry = (num & 2);
bit <<= 1;
}
return carry; //returns 2 NOT 1!
}
Uint8 add_carry(Uint8 *a, Uint8 *r)
{
Uint8 carry = 1;
Uint8 bit = 1,i;
for(i=0; i<CHAR_BIT; i++)
{
if(carry)
if(*a & bit)
*r &= ~bit;
else
{
*r |= bit;
carry = 0;
}
else
if(*a & bit)
*r |= bit;
}
return carry;
}
//************************************************************//
void print_int_bin(bigint num)
{
int x, y, bit;
Uint8 *byte = num.byte+(num.size-1);
for(y=0; y<num.size; y++)
{
bit = 128;
for(x=0; x<CHAR_BIT; x++, bit>>=1)
putchar((*byte & bit)?'1':'0');
putchar(' ');
byte--;
}
}
Bignum.h:
Code:
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#ifndef Uint8
#define Uint8 unsigned char
#endif
#ifndef Uint16
#define Uint16 unsigned short
#endif
#ifndef Uint32
#define Uint32 unsigned long
#endif
#define MIN(x,y) ((x<y) ? (x) : (y))
#define MAX(x,y) ((x>y) ? (x) : (y))
typedef struct
{
Uint8*byte;
Uint8 size;
}bigint;
bigint make_int(Uint8 size);
void reset_int(bigint i);
void set_int(bigint num, Uint32 set_to);
bigint resize_bigint(bigint old);
bigint add_bigint(bigint a, bigint b);
Uint8 add_byte(Uint8 *a, Uint8 *b, Uint8 *r, Uint8 carry);
Uint8 add_carry(Uint8 *a, Uint8 *r);
void print_int_bin(bigint num);
Test Prog:
Code:
#include <stdio.h>
#include "bignum.h"
int main(int argc, char *argv[])
{
bigint a = make_int(2);
set_int(a, 10);
print_int_bin(a);
putchar('\n');
bigint b = make_int(4);
set_int(b, 0xFFFFFFFF);
print_int_bin(b);
putchar('\n');
bigint c = add_bigint(a, b);
print_int_bin(c);
putchar('\n');
getchar();
return 0;
}