/*
* This program demonstrates a method of performing basic arithmetic
* operations (+ - * / %) on arbitrarily long unsigned BINARY numbers.
*
* The arithmetic is performed using only SHIFT, ADD and SUBTRACT
* operations. These algorithms are ideally suitable for fast long
* math functions written in assembler. They operate quite slowly
* when written in 'C', due to the considerable overhead involved
* in simulating the "Carry bit", which is used used to propogate
* the multi-byte add, subtract and shifts.
*
* The numbers are stored and manipulated in memory based "registers".
* These registers are accessed a byte at a time, and are stored in
* "little endian" format (least significant byte occuring first in
* memory). This is done for two reasons:
* 1 - It makes it easier for most of the functions to manupulate
* the register.
* 2 - It makes it easy to define small constants in 'C', due to
* the automatic zero filling on the right.
* eg: unsigned char BIG_ONE[BIG_WIDTH] = { 1 };
*
* Copyright 1993-1995 Dave Dunfield
* All rights reserved.
*
* Compile command: cc bignum -fop
*/
#include <stdio.h>
/*
* To work with larger/smaller numbers, change this constant
*/
#define BIG_WIDTH 8 /* 8 bytes (64 bits) */
/*
* This temporary register will contain the REMAINDER after a division,
* and also a second copy of the product after a multiplication.
*/
unsigned char big_temp[BIG_WIDTH];
/*
* Add two BIG values: n1 += n2
* Returns carry out of big addition.
*/
unsigned big_add(unsigned char *n1, unsigned char *n2)
{
unsigned i, t;
i = BIG_WIDTH;
t = 0;
do {
t = (unsigned)*n1 + (unsigned)*n2++ + t;
*n1++ = t;
t = t >> 8; }
while(--i);
return t;
}
/*
* Subtract two BIG values: n1 -= n2
* Returns borrow out of big subtraction.
*/
unsigned big_sub(unsigned char *n1, unsigned char *n2)
{
unsigned i, t;
i = BIG_WIDTH;
t = 0;
do {
t = (unsigned)*n1 - (unsigned)*n2++ - t;
*n1++ = t;
t = (t >> 8) ? 1 : 0; }
while(--i);
return t;
}
/*
* Shift a BIG value right: n1 >>= 1
* 'c' is the carry in (1/0 shifted in on left)
* Returns carry out of big shift.
*/
unsigned char big_shift_right(unsigned char *n1, unsigned char c)
{
unsigned i;
unsigned char c1;
i = BIG_WIDTH;
do {
c1 = n1[--i];
n1[i] = (c1 >> 1) | (c ? 0x80 : 0);
c = c1 & 0x01; }
while(i);
return c;
}
/*
* Shift a BIG value left: n1 <<= 1
* 'c' is the carry in (1/0 shifted in on right)
* Returns carry out of big shift.
*/
unsigned char big_shift_left(unsigned char *n1, unsigned char c)
{
unsigned i;
unsigned char c1;
i = 0;
do {
c1 = n1[i];
n1[i] = (c1 << 1) | (c ? 0x01 : 0);
c = c1 & 0x80; }
while(++i < BIG_WIDTH);
return c;
}
/*
* Test a BIG value for ZERO
*/
int big_test(unsigned char *n1)
{
unsigned i;
i = BIG_WIDTH;
do {
if(*n1++)
return 1; }
while(--i);
return 0;
}
/*
* Compare two BIG values. Return 1 if n1 < n2
*/
int big_compare(unsigned char *n1, unsigned char *n2)
{
unsigned i;
n1 += (i = BIG_WIDTH);
n2 += BIG_WIDTH;
do {
if(*--n1 != *--n2)
return *n1 < *n2; }
while(--i);
return 0;
}
/*
* Multiply two BIG values: n1 *= n2
* Product is also stored in big_temp
*/
big_mul(unsigned char *n1, unsigned char *n2)
{
unsigned char n3[BIG_WIDTH];
/* Use a local copy of 'n2' to avoid destroying the original */
memset(big_temp, 0, sizeof(big_temp));
memcpy(n3, n2, sizeof(n3));
do {
if(big_shift_right(n1, 0))
big_add(big_temp, n3);
if(!big_test(n1))
break;
big_shift_left(n3, 0); }
while(big_test(n3));
memcpy(n1, big_temp, sizeof(big_temp));
}
/*
* Perform a BIG divide: n1 /= n2
* Remainder is stored in big_temp
*/
big_div(unsigned char *n1, unsigned char *n2)
{
unsigned t, cy;
memset(big_temp, 0, sizeof(big_temp));
t = (BIG_WIDTH*8) + 1;
carry_zero:
cy = 0;
for(;;) {
cy = big_shift_left(n1, cy);
if(!--t)
return;
big_shift_left(big_temp, cy);
if(big_compare(big_temp, n2))
goto carry_zero;
big_sub(big_temp, n2);
cy = 1; }
}
/*
* Convert BIG number to an ASCII string
*/
big_to_string(unsigned char *string, unsigned char *n1, unsigned char base)
{
unsigned sp;
unsigned char n2[BIG_WIDTH], btemp[BIG_WIDTH], c, stack[(BIG_WIDTH*25)/10+1];
/* Use a local copy of 'n1' to avoid destroying original */
memcpy(n2, n1, sizeof(n2));
memset(btemp, sp = 0, sizeof(btemp));
*btemp = base;
/* Stack up digits in reverse order */
do {
big_div(n2, btemp);
if((c = *big_temp + '0') > '9')
c += 7;
stack[sp++] = c; }
while(big_test(n2));
/* Unstack digits into output buffer */
do
*string++ = stack[--sp];
while(sp);
*string = 0;
}
/*
* Parse a string into a BIG number
* Returns character terminating conversion (0 = end of string)
*/
char string_to_big(unsigned char *string, unsigned char *n1, unsigned char base)
{
unsigned char btemp[BIG_WIDTH], c;
memset(btemp, 0, sizeof(btemp));
memset(n1, 0, BIG_WIDTH);
while(c = *string++) {
if(isdigit(c)) /* Decimal digit */
c -= '0';
else if(c >= 'a') /* Lower-case alphabetic */
c -= ('a' - 10);
else if(c >= 'A') /* Upper-case alphabetic */
c -= ('A' - 10);
else /* Error - Invalid digit */
break;
if(c >= base) /* Error - out of range */
break;
*btemp = base;
big_mul(n1, btemp); /* Make room */
*btemp = c;
big_add(n1, btemp); } /* Add new digit */
return c;
}
/*
* Demo program... A simple BIG number command line calculator
*/
main(int argc, char *argv[])
{
int i;
char output[(BIG_WIDTH*25)/10+1];
unsigned char buffer1[BIG_WIDTH], buffer2[BIG_WIDTH];
if(argc < 2) {
fputs("\nUse: bignum <num> [+-*/% <num> ...]\n", stderr);
exit(-1); }
/* Obtain first value from command line */
string_to_big(argv[1], buffer1, 10);
/* For each operator/number, get value & perform operation */
for(i=2; i < argc; i += 2) {
string_to_big(argv[i+1], buffer2, 10);
switch(*argv[i]) {
case '+' : big_add(buffer1, buffer2); break;
case '-' : big_sub(buffer1, buffer2); break;
case '*' : big_mul(buffer1, buffer2); break;
case '/' : big_div(buffer1, buffer2); break;
case '%' :
big_div(buffer1, buffer2);
memcpy(buffer1, big_temp, sizeof(buffer1));
break;
default:
fputs("\nInvalid operator. Use: + - * / %\n", stderr);
exit(-1); } }
/* Display final result */
big_to_string(output, buffer1, 10);
printf("%s\n", output);
}
