#include <limits.h>
#include <inttypes.h>
#include <errno.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define bitsof(T) (CHAR_BIT * sizeof(T))
int test( int num, char *op, int val );
char *operations[] = {
"==", "!=", ">", ">=", "<", "<=",
"<<", ">>", "|", "&", "^",
"+", "*", "-", "/", NULL, "%",
NULL };
int main() {
int num = 64, val = 2, i;
for ( i = 0; operations[i]; ++i ) {
test( num, operations[i], val );
}
return 0;
}
typedef unsigned long mcc_int_seg_t;
#define BI_SEG_END_BIT (~(ULONG_MAX >> 1))
typedef struct mcc_bit {
mcc_int_seg_t i;
mcc_int_seg_t *seg;
mcc_int_seg_t b;
mcc_int_seg_t bit;
} mcc_bit_t;
mcc_bit_t inc_mcc_bit( mcc_bit_t num ) {
++(num.b);
num.bit <<= 1;
if ( !(num.bit) ) {
num.bit = 1;
++(num.i);
++(num.seg);
}
return num;
}
mcc_bit_t add_mcc_bit( mcc_bit_t num, mcc_int_seg_t bits ) {
mcc_int_seg_t i = 0;
if ( !(num.b) ) goto add_mcc_bit_bytes;
while ( bits && num.b % bitsof(mcc_int_seg_t) ) {
--bits;
num = inc_mcc_bit(num);
}
add_mcc_bit_bytes:
if ( !bits ) return num;
i = bits / bitsof(mcc_int_seg_t);
num.i += i;
num.seg = &(num.seg[i]);
num.bit = 1u << (bits % bitsof(mcc_int_seg_t));
if ( bits > bitsof(mcc_int_seg_t) && num.bit > 1u ) {
++(num.seg); ++(num.i);
}
num.b += bits;
return num;
}
mcc_bit_t dec_mcc_bit( mcc_bit_t num ) {
mcc_bit_t tmp = num;
--(tmp.b);
tmp.bit >>= 1;
if ( !(tmp.bit) ) {
tmp.bit = BI_SEG_END_BIT;
--(tmp.i);
--(tmp.seg);
}
return tmp;
}
mcc_bit_t sub_mcc_bit( mcc_bit_t num, mcc_int_seg_t bits ) {
mcc_int_seg_t i = 0;
if ( !(num.b) ) goto sub_mcc_bit_bytes;
while ( bits && num.b % bitsof(mcc_int_seg_t) ) {
--bits;
num = dec_mcc_bit(num);
}
sub_mcc_bit_bytes:
if ( !bits ) return num;
i = bits / bitsof(mcc_int_seg_t);
if ( bits % bitsof(mcc_int_seg_t) ) ++i;
num.i -= i;
while ( i-- ) --(num.seg);
num.bit = BI_SEG_END_BIT;
num.bit >>= (bits % bitsof(mcc_int_seg_t));
num.b -= bits;
return num;
}
int cmp_mcc_bit( mcc_bit_t num, mcc_bit_t val ) {
if ( num.b > val.b ) return 1;
if ( num.b < val.b ) return -1;
return 0;
}
typedef struct _bi {
size_t size;
mcc_bit_t zero, stop;
} mcc_int_t;
int mcc_int_validate( mcc_int_t const * const num ) {
if ( !num || !(num->zero.seg) || !(num->stop.seg) )
return EADDRNOTAVAIL;
if ( cmp_mcc_bit( num->zero, num->stop ) > 0 ) return ERANGE;
return EXIT_SUCCESS;
}
int mcc_int_validate2( mcc_int_t const * const num, mcc_int_t const * const val ) {
int ret = mcc_int_validate( num );
switch ( ret ) {
case EXIT_SUCCESS: break;
case EADDRNOTAVAIL: return EDESTADDRREQ;
default: return ret;
}
return mcc_int_validate( val );
}
int bitemp( mcc_int_t *dst, mcc_int_seg_t *src, size_t count ) {
if ( !dst ) return EDESTADDRREQ;
if ( !src ) return EADDRNOTAVAIL;
if ( !count ) return ERANGE;
(void)memset( dst, 0, sizeof(mcc_int_t) );
dst->size = count * sizeof(mcc_int_seg_t);
dst->zero.seg = src;
dst->zero.bit = 1;
dst->stop = add_mcc_bit( dst->zero, dst->size * CHAR_BIT );
return EXIT_SUCCESS;
}
int bisize( mcc_int_t *dst, size_t size ) {
mcc_int_seg_t *mem;
size_t nodes;
if ( !size ) {
if ( dst->zero.seg ) free( dst->zero.seg );
memset( dst, 0, sizeof(mcc_int_seg_t) );
return EXIT_SUCCESS;
}
nodes = size / sizeof(mcc_int_seg_t);
if ( size % sizeof(mcc_int_seg_t) ) ++nodes;
++nodes;
size = nodes * sizeof(mcc_int_seg_t);
if ( !(dst->zero.seg) ) mem = malloc( size );
else mem = realloc( dst->zero.seg, size );
if ( !mem ) ENOMEM;
memset( &(dst->zero), 0, sizeof(mcc_bit_t) );
dst->zero.seg = mem;
dst->zero.bit = 1;
size -= sizeof(mcc_int_seg_t);
dst->size = size;
dst->stop = add_mcc_bit( dst->zero, size * CHAR_BIT );
return EXIT_SUCCESS;
}
int bisize_and_fill( mcc_int_t *dst, void const *src, size_t size ) {
int ret = bisize( dst, size );
if ( ret != EXIT_SUCCESS ) return ret;
(void)memset( dst->zero.seg, 0, dst->size );
(void)memcpy( dst->zero.seg, src, size );
return EXIT_SUCCESS;
}
int cmp__mcc_int( mcc_int_t const * const num, mcc_int_t const * const val ) {
mcc_bit_t n, v;
if ( !num || !(num->zero.seg) || !(num->size) ) {
if ( !val ) return 0;
v = val->stop;
while ( v.b ) {
v = dec_mcc_bit(v);
if ( *(v.seg) & v.bit ) return -1;
}
return 0;
}
n = num->stop;
if ( !val || !(val->zero.seg) || !(val->size) ) {
while ( n.b ) {
n = dec_mcc_bit(n);
if ( *(n.seg) & n.bit ) return -1;
}
return 0;
}
v = val->stop;
while ( n.b || v.b ) {
while ( n.b ) {
n = dec_mcc_bit(n);
if ( *(n.seg) & n.bit ) break;
}
while ( v.b ) {
v = dec_mcc_bit(v);
if ( *(v.seg) & v.bit ) break;
}
if ( n.b != v.b ) return ( n.b > v.b ) ? 1 : -1;
}
return 0;
}
#define eql__mcc_int( num, val ) (cmp__mcc_int( num, val ) == 0)
#define neq__mcc_int( num, val ) (cmp__mcc_int( num, val ) != 0)
#define gth__mcc_int( num, val ) (cmp__mcc_int( num, val ) > 0)
#define gte__mcc_int( num, val ) (cmp__mcc_int( num, val ) >= 0)
#define lth__mcc_int( num, val ) (cmp__mcc_int( num, val ) < 0)
#define lte__mcc_int( num, val ) (cmp__mcc_int( num, val ) <= 0)
int biclamp1( mcc_int_t *num ) {
int ret = mcc_int_validate(num);
mcc_bit_t one, pos;
if ( ret != EXIT_SUCCESS ) return ret;
one = dec_mcc_bit(pos = num->stop);
while ( pos.i == one.i ) {
if ( !(*(pos.seg) & pos.bit) )
*(pos.seg) |= pos.bit;
}
return EXIT_SUCCESS;
}
int biclamp0( mcc_int_t *num ) {
int ret = mcc_int_validate(num);
mcc_bit_t one, pos;
if ( ret != EXIT_SUCCESS ) return ret;
one = dec_mcc_bit(pos = num->stop);
while ( pos.i == one.i ) {
if ( *(pos.seg) & pos.bit )
*(pos.seg) ^= pos.bit;
}
return EXIT_SUCCESS;
}
int add__mcc_int( mcc_int_t *num, mcc_int_t const * const val ) {
mcc_bit_t n, v, stop;
_Bool c = 0;
int ret = mcc_int_validate2( num, val );
if ( ret != EXIT_SUCCESS ) return ret;
stop = (cmp_mcc_bit(num->stop,val->stop) < 0) ? num->stop : val->stop;
for ( n = num->zero, v = val->zero; n.b < stop.b && v.b < stop.b;
n = inc_mcc_bit(n), v = inc_mcc_bit(v) ) {
if ( c ) {
*(n.seg) ^= n.bit;
if ( *(n.seg) & n.bit )
c = 0;
}
if ( *(v.seg) & v.bit ) {
*(n.seg) ^= n.bit;
if ( !(*(n.seg) & n.bit) )
c = 1;
}
}
if ( c ) {
for ( ; n.b < stop.b; n = inc_mcc_bit(n) ) {
*(n.seg) ^= n.bit;
if ( *(n.seg) & n.bit ) {
c = 0;
break;
}
}
}
return c ? EOVERFLOW : EXIT_SUCCESS;
}
int add_ubi( mcc_int_t *num, mcc_int_t *val ) {
int ret = add__mcc_int( num, val );
if ( ret == EOVERFLOW ) {
memset( num->zero.seg, -1, num->size );
ret = biclamp0( num );
}
return ret;
}
int add_sbi( mcc_int_t *num, mcc_int_t *val ) {
int ret = mcc_int_validate2(num,val);
mcc_int_t tmp;
if ( ret != EXIT_SUCCESS ) return ret;
tmp = *num;
tmp.stop = dec_mcc_bit(tmp.stop);
ret = add__mcc_int( &tmp, val );
if ( ret == EOVERFLOW ) {
memset( num->zero.seg, -1, num->size );
ret = biclamp0( &tmp );
}
return ret;
}
int shl___mcc_int( mcc_int_t *num, mcc_int_seg_t bits ) {
int ret = mcc_int_validate( num );
mcc_bit_t n, v;
if ( ret != EXIT_SUCCESS ) return ret;
if ( !bits ) return EXIT_SUCCESS;
v = sub_mcc_bit( num->stop, bits - 1 );
n = num->stop;
while ( v.b ) {
n = dec_mcc_bit(n);
v = dec_mcc_bit(v);
if ( *(v.seg) & v.bit )
*(n.seg) |= n.bit;
else if ( *(n.seg) & n.bit )
*(n.seg) ^= n.bit;
}
while ( n.bit >> 1 ) {
n = dec_mcc_bit(n);
if ( *(n.seg) & n.bit )
*(n.seg) ^= n.bit;
}
if ( n.i ) memset( num->zero.seg, 0, n.i * sizeof(mcc_int_seg_t) );
return EXIT_SUCCESS;
}
int shl__mcc_int( mcc_int_t *num, mcc_int_t const * const val ) {
int ret = mcc_int_validate2( num, val );
mcc_int_t tmp = {0};
if ( ret != EXIT_SUCCESS ) return ret;
ret = bitemp( &tmp, &(num->stop.b), 1 );
if ( ret != EXIT_SUCCESS ) return ret;
if ( gte__mcc_int( val, &tmp ) ) {
memset( num->zero.seg, 0, num->size );
return EXIT_SUCCESS;
}
return shl___mcc_int( num, *(val->zero.seg) );
}
int shr___mcc_int( mcc_int_t *num, mcc_int_seg_t bits ) {
int ret = mcc_int_validate( num );
mcc_bit_t n, v;
if ( ret != EXIT_SUCCESS ) return ret;
if ( !bits ) return EXIT_SUCCESS;
v = add_mcc_bit( num->zero, bits );
n = num->zero;
while ( v.b < num->stop.b ) {
if ( *(v.seg) & v.bit )
*(n.seg) |= n.bit;
else if ( *(n.seg) & n.bit )
*(n.seg) ^= n.bit;
n = inc_mcc_bit(n);
v = inc_mcc_bit(v);
}
while ( n.bit > 1u ) {
if ( *(n.seg) & n.bit )
*(n.seg) ^= n.bit;
n = inc_mcc_bit(n);
}
if ( n.i < num->stop.i ) {
n.i = num->stop.i - n.i;
memset( n.seg, 0, n.i * sizeof(mcc_int_seg_t) );
}
return EXIT_SUCCESS;
}
int shr__mcc_int( mcc_int_t *num, mcc_int_t const * const val ) {
int ret = mcc_int_validate2( num, val );
mcc_int_t tmp = {0};
if ( ret != EXIT_SUCCESS ) return ret;
ret = bitemp( &tmp, &(num->stop.b), 1 );
if ( ret != EXIT_SUCCESS ) return ret;
if ( gte__mcc_int( val, &tmp ) ) {
memset( num->zero.seg, 0, num->size );
return EXIT_SUCCESS;
}
return shr___mcc_int(num, *(val->zero.seg) );
}
int aor__mcc_int( mcc_int_t *num, mcc_int_t const * const val ) {
int ret = mcc_int_validate2( num, val );
mcc_bit_t n, v, e;
if ( ret != EXIT_SUCCESS ) return ret;
n = num->zero;
v = val->zero;
e = (cmp_mcc_bit(num->stop, val->stop) < 0) ? num->stop : val->stop;
while ( n.b < e.b && v.b < e.b ) {
if ( *(v.seg) & v.bit )
*(n.seg) |= n.bit;
n = inc_mcc_bit(n);
v = inc_mcc_bit(v);
}
return EXIT_SUCCESS;
}
int xor__mcc_int( mcc_int_t *num, mcc_int_t const * const val ) {
int ret = mcc_int_validate2( num, val );
mcc_bit_t n, v, e;
if ( ret != EXIT_SUCCESS ) return ret;
n = num->zero;
v = val->zero;
e = (cmp_mcc_bit(num->stop, val->stop) < 0) ? num->stop : val->stop;
while ( n.b < e.b && v.b < e.b ) {
if ( *(v.seg) & v.bit )
*(n.seg) ^= n.bit;
n = inc_mcc_bit(n);
v = inc_mcc_bit(v);
}
return EXIT_SUCCESS;
}
int and__mcc_int( mcc_int_t *num, mcc_int_t const * const val ) {
int ret = mcc_int_validate2( num, val );
mcc_bit_t n, v, e;
if ( ret != EXIT_SUCCESS ) return ret;
n = num->zero;
v = val->zero;
e = (cmp_mcc_bit(num->stop, val->stop) < 0) ? num->stop : val->stop;
while ( n.b < e.b && v.b < e.b ) {
if ( !(*(v.seg) & v.bit) && *(n.seg) & n.bit )
*(n.seg) ^= n.bit;
n = inc_mcc_bit(n);
v = inc_mcc_bit(v);
}
while ( n.b < num->stop.b ) {
if ( *(n.seg) & n.bit )
*(n.seg) ^= n.bit;
n = inc_mcc_bit(n);
}
return EXIT_SUCCESS;
}
int mul__mcc_int( mcc_int_t *num, mcc_int_t const * const val ) {
int ret = mcc_int_validate2( num, val );
mcc_int_t tmp = {0};
mcc_bit_t v;
mcc_int_seg_t bits = 0;
if ( ret != EXIT_SUCCESS ) return ret;
ret = bisize_and_fill( &tmp, num->zero.seg, num->size );
if ( ret != EXIT_SUCCESS ) return ret;
for ( v = val->zero; v.b < val->stop.b; v = inc_mcc_bit(v) ) {
if ( *(v.seg) & v.bit ) {
(void)shl___mcc_int( &tmp, bits );
if ( add__mcc_int( num, &tmp ) == EOVERFLOW )
ret = EOVERFLOW;
bits = 0;
}
++bits;
}
(void)bisize( &tmp, 0 );
return ret;
}
int sub__mcc_int( mcc_int_t *num, mcc_int_t const * const val ) {
mcc_bit_t n, v, stop;
_Bool c = 0;
int ret = mcc_int_validate2( num, val );
if ( ret != EXIT_SUCCESS ) return ret;
stop = (cmp_mcc_bit(num->stop,val->stop) < 0) ? num->stop : val->stop;
for ( n = num->zero, v = val->zero; n.b < stop.b && v.b < stop.b;
n = inc_mcc_bit(n), v = inc_mcc_bit(v) ) {
if ( c ) {
*(n.seg) ^= n.bit;
if ( !(*(n.seg) & n.bit) )
c = 0;
}
if ( *(v.seg) & v.bit ) {
*(n.seg) ^= n.bit;
if ( *(n.seg) & n.bit )
c = 1;
}
}
if ( c ) {
for ( ; n.b < stop.b; n = inc_mcc_bit(n) ) {
*(n.seg) ^= n.bit;
if ( !(*(n.seg) & n.bit) ) {
c = 0;
break;
}
}
}
return c ? EOVERFLOW : EXIT_SUCCESS;
}
int div__mcc_int( mcc_int_t *num, mcc_int_t const * const val, mcc_int_t *rem ) {
int ret = mcc_int_validate2( num, val );
mcc_int_t seg = {0};
mcc_int_seg_t bits = 0;
if ( ret != EXIT_SUCCESS ) return ret;
ret = mcc_int_validate(rem);
if ( ret != EXIT_SUCCESS )
return (ret == EADDRNOTAVAIL) ? EDESTADDRREQ : ret;
if ( rem->size != num->size ) return ERANGE;
seg = *rem;
seg.zero = seg.stop;
(void)memcpy( rem->zero.seg, num->zero.seg, num->size );
(void)memset( num->zero.seg, 0, num->size );
if ( eql__mcc_int( val, NULL ) ) return EXIT_SUCCESS;
while ( gte__mcc_int( rem, val ) && seg.zero.b ) {
seg.zero = dec_mcc_bit(seg.zero);
if ( gte__mcc_int( &seg, val ) ) {
shl___mcc_int( num, bits );
sub__mcc_int( &seg, val );
*(num->zero.seg) |= num->zero.bit;
bits = 0;
}
++bits;
}
if ( bits ) shl___mcc_int( num, bits );
return EXIT_SUCCESS;
}
int test( int num, char *op, int val ) {
int ret = EXIT_FAILURE, rem = num;
mcc_int_t _num = {0}, _val = {0}, _rem = {0};
(void)bisize_and_fill( &_num, &num, sizeof(int) );
(void)bisize_and_fill( &_val, &val, sizeof(int) );
(void)bisize_and_fill( &_rem, &num, sizeof(int) );
switch ( *op ) {
case 0: ret = EILSEQ; goto fail;
case '|': num |= val; aor__mcc_int( &_num, &_val ); goto done;
case '^': num ^= val; xor__mcc_int( &_num, &_val ); goto done;
case '&': num &= val; and__mcc_int( &_num, &_val ); goto done;
case '+': num += val; add__mcc_int( &_num, &_val ); goto done;
case '*': num *= val; mul__mcc_int( &_num, &_val ); goto done;
case '-': num -= val; sub__mcc_int( &_num, &_val ); goto done;
case '/':
num -= val; rem %= val;
div__mcc_int( &_num, &_val, &_rem ); goto done;
case '=':
if ( op[1] != '=' ) goto fail;
num = (num == val);
*(_num.zero.seg) = eql__mcc_int( &_num, &_val );
goto done;
case '!':
if ( op[1] != '=' ) goto fail;
num = (num != val);
*(_num.zero.seg) = neq__mcc_int( &_num, &_val );
goto done;
case '>':
if ( op[1] == '>' ) {
num = (num >> val);
shr__mcc_int( &_num, &_val );
}
else if ( op[1] == '=' ) {
num = (num >= val);
*(_num.zero.seg) = gte__mcc_int( &_num, &_val );
}
else {
num = (num > val);
*(_num.zero.seg) = gth__mcc_int( &_num, &_val );
}
goto done;
case '<':
if ( op[1] == '<' ) {
num = (num << val);
shl__mcc_int( &_num, &_val );
}
else if ( op[1] == '=' ) {
num = (num <= val);
*(_num.zero.seg) = lte__mcc_int( &_num, &_val );
}
else {
num = (num < val);
*(_num.zero.seg) = lth__mcc_int( &_num, &_val );
}
goto done;
}
done:
if ( memcmp( _num.zero.seg, &num, sizeof(int) ) )
ret = EXIT_SUCCESS;
printf( "_num = %016lX, num = %016X, "
"_rem = %016lX, rem = %016X op = '%s'\n",
*(_num.zero.seg), num, *(_rem.zero.seg), rem, op );
fail:
bisize( &_num, 0 );
bisize( &_val, 0 );
bisize( &_rem, 0 );
return ret;
}