#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "bbn.h"
#include "stack.h"
#include "common.h"
#define safe_free(ptr) do { free((ptr));(ptr)=NULL; } while(0)
typedef enum {
SIGN_PLUS,
SIGN_MINUS
} EnumSign;
struct BigBaseNumber {
int base; /* base of number */
EnumSign sign; /* sign of number */
int ilen; /* length of integer part */
int flen; /* length of fraction part */
char *integer; /* integer part */
char *fraction; /* fraction part */
char *iptr; /* no leading zero byte, real pointer to integer */
};
static void* safe_malloc( size_t size, const char *str )
{
void *ptr = NULL;
if ( size > 0 ) {
ptr = malloc( size );
if ( !ptr ) {
fprintf( stderr, "%s: out of memory\n", str );
exit( -1 );
}
memset( ptr, 0, size );
}
return ptr;
}
/* remove leading zero bytes of integer part and trailing zero bytes */
static void BBN_RemoveZeroByte( PBBN pbbn )
{
int n, len;
char *ptr = pbbn->iptr;
/* remove leading zero bytes */
len = pbbn->ilen;
for ( n = 0; n < len-1; n++ ) {
if ( ptr[n] ) {
break;
}
pbbn->ilen--;
pbbn->iptr++;
}
/* remove trailing zero bytes */
len = pbbn->flen;
for ( n = len-1; n >= 0; n-- ) {
if ( pbbn->fraction[n] ) {
break;
}
pbbn->flen--;
}
}
/* caller should promise that str is valid with base */
PBBN BBN_Create( const char *str, int base )
{
char ch;
int n;
const char *ptr;
PBBN pbbn = NULL;
assert( BBN_MIN_BASE <= base && base <= BBN_MAX_BASE );
pbbn = (PBBN)safe_malloc( sizeof(*pbbn), __FUNCTION__ );
pbbn->base = base;
pbbn->sign = SIGN_PLUS;
if ( !str ) return pbbn;
if ( str[0] == '+' || str[0] == '-' ) {
if ( str[0] == '-' ) {
pbbn->sign = SIGN_MINUS;
}
str++;
}
ptr = strchr( str, '.' );
if ( ptr ) { /* number has fraction part */
pbbn->ilen = ptr - str;
ptr++;
pbbn->flen = strlen( ptr );
assert( pbbn->flen > 0 );
pbbn->fraction = (char*)safe_malloc( pbbn->flen, __FUNCTION__ );
for ( n = 0; n < pbbn->flen; n++ ) {
ch = ptr[n];
if ( isdigit(ch) ) {
pbbn->fraction[n] = ch-'0';
} else {
if ( islower(ch) ) {
ch = toupper( ch );
}
pbbn->fraction[n] = ch -'A' + 10;
}
}
} else {
pbbn->ilen = strlen(str);
}
if ( pbbn->ilen == 0 ) return pbbn;
pbbn->integer = (char *)safe_malloc( pbbn->ilen, __FUNCTION__ );
pbbn->iptr = pbbn->integer;
for ( n = 0; n < pbbn->ilen; n++ ) {
ch = str[n];
if ( isdigit(ch) ) {
pbbn->integer[n] = ch - '0';
} else {
if ( islower(ch) ) {
ch = toupper( ch );
}
pbbn->integer[n] = ch - 'A' + 10;
}
}
BBN_RemoveZeroByte( pbbn );
/* maybe user pass "-0.0" to this function, set sign = SIGN_PLUS */
if ( BBN_IsZero( pbbn ) && pbbn->sign == SIGN_MINUS ) {
pbbn->sign = SIGN_PLUS;
}
return pbbn;
}
PBBN BBN_CreateInteger( int value, int base )
{
int positive = (value>=0);
char buf[256]; /* buf can contains any integer for binary */
char *ptr = buf + sizeof(buf) - 2; /* last character is '\0' */
assert( BBN_MIN_BASE <= base && base <= BBN_MAX_BASE );
memset( buf, 0, sizeof(buf) );
if ( value == 0 ) {
*ptr-- = '0';
}
if ( value < 0 ) value *= -1;
while ( value != 0 ) {
char ch = (char)( value % base );
if ( ch < 10 ) {
ch += '0';
} else {
ch += 'A';
}
*ptr-- = ch;
value /= base;
}
if ( positive ) {
ptr++;
} else {
*ptr = '-';
}
return BBN_Create( ptr, base );
}
void BBN_Free( PBBN pbbn )
{
safe_free( pbbn->integer );
safe_free( pbbn->fraction );
safe_free( pbbn );
}
void BBN_Print( const PBBN pbbn )
{
char ch;
int n;
if ( pbbn->sign == SIGN_MINUS ) {
fprintf( stdout, "-" );
}
if ( pbbn->ilen == 0 ) {
fprintf( stdout, "0" );
} else {
for ( n = 0; n < pbbn->ilen; n++ ) {
ch = pbbn->iptr[n];
if ( ch < 10 ) {
ch += '0';
} else {
ch += 'A' - 10;
}
fprintf( stdout, "%c", ch );
}
}
if ( pbbn->flen > 0 ) {
fprintf( stdout, "." );
for ( n = 0; n < pbbn->flen; n++ ) {
ch = pbbn->fraction[n];
if ( ch < 10 ) {
ch += '0';
} else {
ch += 'A' - 10;
}
fprintf( stdout, "%c", ch );
}
}
fprintf( stdout, " %d\n", pbbn->base );
}
static PBBN BBN_AddUnsign( const PBBN pbbn1, const PBBN pbbn2 )
{
int n, n1, n2, len;
char ch, carry;
char *ptr, *ptr1, *ptr2;
PBBN pResult = NULL;
assert( pbbn1 != NULL && pbbn2 != NULL );
assert( pbbn1->base == pbbn2->base );
pResult = BBN_Create( NULL, pbbn1->base );
pResult->ilen = MAX( pbbn1->ilen, pbbn2->ilen ) + 1;
pResult->flen = MAX( pbbn1->flen, pbbn2->flen );
pResult->integer = (char *)safe_malloc( pResult->ilen, __FUNCTION__ );
pResult->iptr = pResult->integer;
if ( pResult->flen > 0 ) {
pResult->fraction = (char *)safe_malloc( pResult->flen, __FUNCTION__ );
}
/* add fraction part */
n1 = pbbn1->flen;
n2 = pbbn2->flen;
len = MIN( n1, n2 );
if ( n1 > n2 ) {
memcpy( pResult->fraction, pbbn1->fraction+n2, n1 - n2 );
} else if ( n1 < n2 ) {
memcpy( pResult->fraction, pbbn2->fraction+n1, n2 - n1 );
}
carry = 0;
for ( n = len-1; n >= 0; n-- ) {
ch = pbbn1->fraction[n] + pbbn2->fraction[n] + carry;
carry = ch / (char)pbbn1->base;
ch = ch % (char)pbbn1->base;
pResult->fraction[n] = ch;
}
/* add integer part */
n1 = pbbn1->ilen;
n2 = pbbn2->ilen;
len = MIN( n1, n2 );
ptr = pResult->iptr + pResult->ilen - 1;
ptr1 = pbbn1->iptr + n1 - 1;
ptr2 = pbbn2->iptr + n2 - 1;
for ( n = 0; n < len; n++ ) {
ch = *ptr1-- + *ptr2-- + carry;
carry = ch / (char)pbbn1->base;
ch = ch % (char)pbbn1->base;
*ptr-- = ch;
}
if ( n1 > n2 ) {
len = n1 - n2;
for ( n = 0; n < len; n++ ) {
ch = carry + *ptr1--;
carry = ch / (char)pbbn1->base;
ch = ch % (char)pbbn1->base;
*ptr-- = ch;
}
} else if ( n1 < n2 ) {
len = n2 - n1;
for ( n = 0; n < len; n++ ) {
ch = carry + *ptr2--;
carry = ch / (char)pbbn1->base;
ch = ch % (char)pbbn1->base;
*ptr-- = ch;
}
}
*ptr = carry;
/* remove leading zero byte and trailing zero byte */
BBN_RemoveZeroByte( pResult );
return pResult;
}
/* assume pbbn1 >= pbbn2 without sign */
static PBBN BBN_SubUnsign( const PBBN pbbn1, const PBBN pbbn2 )
{
int n, n1, n2, len;
char ch, borrow;
char *ptr, *ptr1, *ptr2;
PBBN pResult = NULL;
assert( pbbn1 != NULL && pbbn2 != NULL );
assert( pbbn1->base == pbbn2->base );
assert( BBN_CmpUnsign( pbbn1, pbbn2 ) >= 0 );
pResult = BBN_Create( NULL, pbbn1->base );
pResult->ilen = MAX( pbbn1->ilen, pbbn2->ilen );
pResult->flen = MAX( pbbn1->flen, pbbn2->flen );
pResult->integer = (char *)safe_malloc( pResult->ilen, __FUNCTION__ );
pResult->iptr = pResult->integer;
pResult->fraction = (char *)safe_malloc( pResult->flen, __FUNCTION__ );
/* subtract fraction part */
borrow = 0;
n1 = pbbn1->flen;
n2 = pbbn2->flen;
ptr1 = pbbn1->fraction + n1 - 1;
ptr2 = pbbn2->fraction + n2 - 1;
ptr = pResult->fraction + pResult->flen - 1;
if ( n1 > n2 ) {
len = n1 - n2;
for ( n = 0; n < len; n++ ) {
*ptr-- = *ptr1--;
}
} else if ( n1 < n2 ) {
len = n2 - n1;
for ( n = 0; n < len; n++ ) {
ch = 0 - *ptr2-- - borrow;
if ( ch < 0 ) {
ch += pbbn1->base;
borrow = 1;
} else {
borrow = 0;
}
*ptr-- = ch;
}
}
len = MIN( n1, n2 );
for ( n = 0; n < len; n++ ) {
ch = *ptr1-- - *ptr2-- - borrow;
if ( ch < 0 ) {
ch += pbbn1->base;
borrow = 1;
} else {
borrow = 0;
}
*ptr-- = ch;
}
/* subtract integer part */
n1 = pbbn1->ilen;
n2 = pbbn2->ilen;
assert( n1 >= n2 );
ptr1 = pbbn1->iptr + n1 - 1;
ptr2 = pbbn2->iptr + n2 - 1;
ptr = pResult->iptr + pResult->ilen - 1;
for ( n = 0; n < n2; n++ ) {
ch = *ptr1-- - *ptr2-- - borrow;
if ( ch < 0 ) {
ch += pbbn1->base;
borrow = 1;
} else {
borrow = 0;
}
*ptr-- = ch;
}
len = n1 - n2;
for ( n = 0; n < len; n++ ) {
ch = *ptr1-- - borrow;
if ( ch < 0 ) {
ch += pbbn1->base;
borrow = 1;
} else {
borrow = 0;
}
*ptr-- = ch;
}
if ( borrow == 1 ) {
BBN_Print( pbbn1 );
BBN_Print(
20100351524.tgz （15个子文件） 
add 
stack.h 766B Makefile 270B common.h 379B bin add.case 506B run.sh 275B check.c 4KB run.clean 165B bbn.h 2KB stack.c 2KB bbn.c 19KB README 2KB main.c 1KB test Makefile 259B test.c 5KB check.c 4KB资源评论
jenny_yu10252013-04-08资源很好，作者用心。
