X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Ftv%2Fstrcalc.c;h=9a286b4c2d018f82cd71da1a53bcc9485c2a6fb6;hb=5c37521f4464edd75e85a32e52d5bf5225f8ede5;hp=799c36adf349e4109a7bff60b38aec4015d86d55;hpb=8405e525debcaf841c9d2cef98f1945d3822adb0;p=libfirm diff --git a/ir/tv/strcalc.c b/ir/tv/strcalc.c index 799c36adf..9a286b4c2 100644 --- a/ir/tv/strcalc.c +++ b/ir/tv/strcalc.c @@ -1,44 +1,80 @@ -/****i* strcalc/implementation - * - * AUTHORS - * Matthias Heil - * - * NOTES - ******/ +/* + * Project: libFIRM + * File name: ir/tv/strcalc.c + * Purpose: + * Author: Mathias Heil + * Modified by: + * Created: + * CVS-ID: $Id$ + * Copyright: (c) 2003 Universität Karlsruhe + * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + */ + + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif +#ifdef HAVE_STDLIB_H +# include +#endif +#ifdef HAVE_ALLOCA_H +# include +#endif +#ifdef HAVE_MALLOC_H +# include +#endif +#ifdef HAVE_STRING_H +# include /* memset/memcmp */ +#endif #include /* assertions */ -#include /* memset/memcmp */ +#include /* output for error messages */ +#include /* definition of LONG_MIN, used in sc_get_val_from_long */ #include "strcalc.h" -#include /* output for error messages */ -#include - -/***************************************************************************** +/* * local definitions and macros - *****************************************************************************/ -#define BIT_PATTERN_SIZE (8 * BIGGEST_INTEGER_SIZE_IN_BYTES) -#define CALC_BUFFER_SIZE (4 * BIGGEST_INTEGER_SIZE_IN_BYTES) -#define MAX_VALUE_SIZE (2 * BIGGEST_INTEGER_SIZE_IN_BYTES) - -#define CLEAR_CALC_BUFFER() assert(calc_buffer); memset(calc_buffer, SC_0, CALC_BUFFER_SIZE) + */ +#define CLEAR_BUFFER(b) assert(b); memset(b, SC_0, calc_buffer_size) #define _val(a) ((a)-SC_0) #define _digit(a) ((a)+SC_0) #define _bitisset(digit, pos) (and_table[_val(digit)][_val(shift_table[pos])] != SC_0) #define fail_char(a, b, c, d) _fail_char((a), (b), (c), (d), __FILE__, __LINE__) -#if 0 +/* shortcut output for debugging */ +# define sc_print_hex(a) sc_print((a), 0, SC_HEX) +# define sc_print_dec(a) sc_print((a), 0, SC_DEC) +# define sc_print_oct(a) sc_print((a), 0, SC_OCT) +# define sc_print_bin(a) sc_print((a), 0, SC_BIN) + +#ifdef STRCALC_DEBUG_PRINTCOMP +# define DEBUGPRINTF_COMPUTATION(x) printf x +#else +# define DEBUGPRINTF_COMPUTATION(x) ((void)0) +#endif +#ifdef STRCALC_DEBUG # define DEBUGPRINTF(x) printf x #else # define DEBUGPRINTF(x) ((void)0) #endif -/***************************************************************************** - * private variables - *****************************************************************************/ -static char calc_buffer[CALC_BUFFER_SIZE]; /* buffer holding all results */ +/* + * private variables + */ +static char *calc_buffer = NULL; /* buffer holding all results */ +static char *output_buffer = NULL; /* buffer for output */ +static int bit_pattern_size; /* maximum number of bits */ +static int calc_buffer_size; /* size of internally stored values */ +static int max_value_size; /* maximum size of values */ + +static int carry_flag; /**< some computation set the carry_flag: + - right shift if bits were lost due to shifting + - division if there was a remainder + However, the meaning of carry is machine dependent + and often defined in other ways! */ static const char max_digit[4] = { SC_0, SC_1, SC_3, SC_7 }; static const char min_digit[4] = { SC_F, SC_E, SC_C, SC_8 }; @@ -89,7 +125,7 @@ static const char and_table[16][16] = { SC_8, SC_8, SC_8, SC_8, SC_C, SC_C, SC_C, SC_C }, { SC_0, SC_1, SC_0, SC_1, SC_4, SC_5, SC_4, SC_5, - SC_8, SC_9, SC_8, SC_9, SC_D, SC_E, SC_D, SC_E }, + SC_8, SC_9, SC_8, SC_9, SC_C, SC_D, SC_C, SC_D }, { SC_0, SC_0, SC_2, SC_2, SC_4, SC_4, SC_6, SC_6, SC_8, SC_8, SC_A, SC_A, SC_C, SC_C, SC_E, SC_E }, @@ -378,6 +414,13 @@ static char const shrs_table[16][4][2] = { { {SC_E, SC_0}, {SC_7, SC_0}, {SC_3, SC_8}, {SC_1, SC_C} }, { {SC_F, SC_0}, {SC_7, SC_8}, {SC_3, SC_C}, {SC_1, SC_E} } }; + +/** converting a digit to a binary string */ +static const char *binary_table[16] = { + "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", + "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111" +}; + /***************************************************************************** * private functions *****************************************************************************/ @@ -391,48 +434,80 @@ static void _fail_char(const char *str, size_t len, const char fchar, int pos, exit(-1); } +/** + * implements the bitwise NOT operation + */ static void _bitnot(const char *val, char *buffer) { int counter; - for (counter = 0; counter> 2; + + return _bitisset(val[nibble], bit); +} + +/** + * Implements a fast ADD + 1 + */ +static void _inc(const char *val, char *buffer) { int counter = 0; - while (counter++ < CALC_BUFFER_SIZE) + while (counter++ < calc_buffer_size) { if (*val == SC_F) { @@ -446,23 +521,32 @@ static void _inc(char *val, char *buffer) return; } } - /* here a carry could be lost, this is intended because this will only - * happen when a value changes sign. */ + /* here a carry could be lost, this is intended because this should + * happen only when a value changes sign. */ } +/** + * Implements a unary MINUS + */ static void _negate(const char *val, char *buffer) { _bitnot(val, buffer); _inc(buffer, buffer); } +/** + * Implements a binary ADD + * + * @todo The implementation of carry is wrong, as it is the + * calc_buffer_size carry, not the mode depending + */ static void _add(const char *val1, const char *val2, char *buffer) { int counter; const char *add1, *add2; char carry = SC_0; - for (counter = 0; counter < CALC_BUFFER_SIZE; counter++) + for (counter = 0; counter < calc_buffer_size; counter++) { add1 = add_table[_val(val1[counter])][_val(val2[counter])]; add2 = add_table[_val(add1[0])][_val(carry)]; @@ -470,22 +554,40 @@ static void _add(const char *val1, const char *val2, char *buffer) buffer[counter] = add2[0]; carry = add_table[_val(add1[1])][_val(add2[1])][0]; } - /* loose last carry, which will occur only when changing sign */ + carry_flag = carry != SC_0; } +/** + * Implements a binary SUB + */ +static void _sub(const char *val1, const char *val2, char *buffer) +{ + char *temp_buffer = alloca(calc_buffer_size); /* intermediate buffer to hold -val2 */ + + _negate(val2, temp_buffer); + _add(val1, temp_buffer, buffer); +} + +/** + * Implements a binary MUL + */ static void _mul(const char *val1, const char *val2, char *buffer) { - char temp_buffer[CALC_BUFFER_SIZE]; /* result buffer */ - char neg_val1[CALC_BUFFER_SIZE]; /* abs of val1 */ - char neg_val2[CALC_BUFFER_SIZE]; /* abs of val2 */ + char *temp_buffer; /* result buffer */ + char *neg_val1; /* abs of val1 */ + char *neg_val2; /* abs of val2 */ const char *mul, *add1, *add2; /* intermediate result containers */ char carry = SC_0; /* container for carries */ char sign = 0; /* marks result sign */ int c_inner, c_outer; /* loop counters */ + temp_buffer = alloca(calc_buffer_size); + neg_val1 = alloca(calc_buffer_size); + neg_val2 = alloca(calc_buffer_size); + /* init result buffer to zeroes */ - memset(temp_buffer, SC_0, CALC_BUFFER_SIZE); + memset(temp_buffer, SC_0, calc_buffer_size); /* the multiplication works only for positive values, for negative values * * it is necessary to negate them and adjust the result accordingly */ @@ -500,11 +602,11 @@ static void _mul(const char *val1, const char *val2, char *buffer) sign ^= 1; } - for (c_outer = 0; c_outer < MAX_VALUE_SIZE; c_outer++) + for (c_outer = 0; c_outer < max_value_size; c_outer++) { if (val2[c_outer] != SC_0) { - for (c_inner = 0; c_inner < MAX_VALUE_SIZE; c_inner++) + for (c_inner = 0; c_inner < max_value_size; c_inner++) { /* do the following calculation: * * Add the current carry, the value at position c_outer+c_inner * @@ -534,76 +636,80 @@ static void _mul(const char *val1, const char *val2, char *buffer) } /* A carry may hang over */ - /* c_outer is always smaller than MAX_VALUE_SIZE! */ - temp_buffer[MAX_VALUE_SIZE + c_outer] = carry; + /* c_outer is always smaller than max_value_size! */ + temp_buffer[max_value_size + c_outer] = carry; + carry = SC_0; } } if (sign) _negate(temp_buffer, buffer); else - memcpy(buffer, temp_buffer, CALC_BUFFER_SIZE); -} - -static void _sub(const char *val1, const char *val2, char *buffer) -{ - char temp_buffer[CALC_BUFFER_SIZE]; /* intermediate buffer to hold -val2 */ - - _negate(val2, temp_buffer); - _add(val1, temp_buffer, buffer); + memcpy(buffer, temp_buffer, calc_buffer_size); } +/** + * Shift the buffer to left and add a 4 bit digit + */ static void _push(const char digit, char *buffer) { int counter; - for (counter = CALC_BUFFER_SIZE - 2; counter >= 0; counter--) + for (counter = calc_buffer_size - 2; counter >= 0; counter--) { buffer[counter+1] = buffer[counter]; } buffer[0] = digit; } -/* XXX: This is MOST slow */ -static void _divmod(const char *dividend, const char *divisor, char *quot, char *rem) +/** + * Implements truncating integer division and remainder. + * + * Note: This is MOST slow + */ +static void _divmod(const char *rDividend, const char *divisor, char *quot, char *rem) { + const char *dividend = rDividend; const char *minus_divisor; - char neg_val1[CALC_BUFFER_SIZE]; - char neg_val2[CALC_BUFFER_SIZE]; + char *neg_val1; + char *neg_val2; - char sign = 0; /* remember result sign */ + char div_sign = 0; /* remember division result sign */ + char rem_sign = 0; /* remember remainder esult sign */ int c_dividend; /* loop counters */ + neg_val1 = alloca(calc_buffer_size); + neg_val2 = alloca(calc_buffer_size); + /* clear result buffer */ - memset(quot, SC_0, CALC_BUFFER_SIZE); - memset(rem, SC_0, CALC_BUFFER_SIZE); + memset(quot, SC_0, calc_buffer_size); + memset(rem, SC_0, calc_buffer_size); - /* if the dividend is zero result is zero (quot is zero)*/ - if (sc_comp(dividend, quot) == 0) return; /* if the divisor is zero this won't work (quot is zero) */ - if (sc_comp(divisor, quot) == 0) assert(0 && "quotision by zero!"); + if (sc_comp(divisor, quot) == 0) assert(0 && "division by zero!"); - if (_sign(dividend) == -1) - { + /* if the dividend is zero result is zero (quot is zero)*/ + if (sc_comp(dividend, quot) == 0) + return; + + if (_sign(dividend) == -1) { _negate(dividend, neg_val1); - sign ^= 1; + div_sign ^= 1; + rem_sign ^= 1; dividend = neg_val1; } _negate(divisor, neg_val2); - if (_sign(divisor) == -1) - { - sign ^= 1; + if (_sign(divisor) == -1) { + div_sign ^= 1; minus_divisor = divisor; divisor = neg_val2; } else - { minus_divisor = neg_val2; - } - /* if divisor >= dividend quotision is easy + /* if divisor >= dividend division is easy * (remember these are absolute values) */ switch (sc_comp(dividend, divisor)) { @@ -612,14 +718,14 @@ static void _divmod(const char *dividend, const char *divisor, char *quot, char return; case -1: /* dividend < divisor */ - memcpy(rem, dividend, CALC_BUFFER_SIZE); + memcpy(rem, rDividend, calc_buffer_size); return; - default: /* unluckily quotision is necessary :( */ + default: /* unluckily division is necessary :( */ break; } - for (c_dividend = MAX_VALUE_SIZE - 1; c_dividend >= 0; c_dividend--) + for (c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) { _push(dividend[c_dividend], rem); _push(SC_0, quot); @@ -641,82 +747,96 @@ static void _divmod(const char *dividend, const char *divisor, char *quot, char } } - if (sign) - { + /* sets carry if remainder is non-zero ??? */ + carry_flag = !sc_is_zero(rem); + + if (div_sign) _negate(quot, quot); + + if (rem_sign) _negate(rem, rem); - } } -static void _shl(const char *val1, const char *val2, char *buffer, unsigned radius, unsigned is_signed) +/** + * Implements a Shift Left, which can either preserve the sign bit + * or not. + * + * @todo Assertions seems to be wrong + */ +static void _shl(const char *val1, char *buffer, long offset, int radius, unsigned is_signed) { const char *shl; char shift; char carry = SC_0; int counter; - int offset = 0; int bitoffset = 0; - assert((_sign(val2) != -1) || (0 && "negative leftshift")); + assert((offset >= 0) || (0 && "negative leftshift")); assert(((_sign(val1) != -1) || is_signed) || (0 && "unsigned mode and negative value")); assert(((!_bitisset(val1[(radius-1)/4], (radius-1)%4)) || !is_signed || (_sign(val1) == -1)) || (0 && "value is positive, should be negative")); assert(((_bitisset(val1[(radius-1)/4], (radius-1)%4)) || !is_signed || (_sign(val1) == 1)) || (0 && "value is negative, should be positive")); - /* the whole value must be moved left the number of bytes represented - * by the value in quot, with bytes to the right set to zero */ - /*XXX This might result in trouble */ - for (counter = MAX_VALUE_SIZE - 1; counter >= 0; counter--) - { - offset = (offset << 4) | (_val(val2[counter])); - } - - shift = shift_table[_val(offset%4)]; /* this is 2 ** (val2 % 4) */ - /* if shifting far enough the result is zero */ if (offset >= radius) { - memset(buffer, SC_0, CALC_BUFFER_SIZE); + memset(buffer, SC_0, calc_buffer_size); return; } + + shift = shift_table[_val(offset%4)]; /* this is 2 ** (offset % 4) */ offset = offset / 4; /* shift the single digits some bytes (offset) and some bits (table) * to the left */ - for (counter = 0; counter < CALC_BUFFER_SIZE - offset; counter++) + for (counter = 0; counter < radius/4 - offset; counter++) { shl = mul_table[_val(val1[counter])][_val(shift)]; buffer[counter + offset] = or_table[_val(shl[0])][_val(carry)]; carry = shl[1]; } + if (radius%4 > 0) + { + shl = mul_table[_val(val1[counter])][_val(shift)]; + buffer[counter + offset] = or_table[_val(shl[0])][_val(carry)]; + bitoffset = counter; + } else { + bitoffset = counter - 1; + } /* fill with zeroes */ - for (counter = 0; counter < offset; counter++) buffer[counter] = 0; + for (counter = 0; counter < offset; counter++) buffer[counter] = SC_0; + /* if the mode was signed, change sign when the mode's msb is now 1 */ - offset = (radius - 1) / 4; - bitoffset = (radius - 1) % 4; - if (is_signed && _bitisset(buffer[offset], bitoffset) && (_sign(buffer) == 1)) + offset = bitoffset + offset; + bitoffset = (radius-1) % 4; + if (is_signed && _bitisset(buffer[offset], bitoffset)) { /* this sets the upper bits of the leftmost digit */ buffer[offset] = or_table[_val(buffer[offset])][_val(min_digit[bitoffset])]; - for (counter = offset+1; counter < CALC_BUFFER_SIZE; counter++) + for (counter = offset+1; counter < calc_buffer_size; counter++) { buffer[counter] = SC_F; } } - else if (is_signed && !_bitisset(buffer[offset], bitoffset) && (_sign(buffer) == -1)) + else if (is_signed && !_bitisset(buffer[offset], bitoffset)) { - /* this unsets the upper bits of the leftmost digit */ + /* this clears the upper bits of the leftmost digit */ buffer[offset] = and_table[_val(buffer[offset])][_val(max_digit[bitoffset])]; - /* zero the upper part of the value */ - for (counter = offset+1; counter < CALC_BUFFER_SIZE; counter++) + for (counter = offset+1; counter < calc_buffer_size; counter++) { buffer[counter] = SC_0; } } } -static void _shr(const char *val1, const char *val2, char *buffer, unsigned radius, unsigned is_signed, int signed_shift) +/** + * Implements a Shift Right, which can either preserve the sign bit + * or not. + * + * @todo Assertions seems to be wrong + */ +static void _shr(const char *val1, char *buffer, long offset, int radius, unsigned is_signed, int signed_shift) { const char *shrs; char sign; @@ -725,35 +845,48 @@ static void _shr(const char *val1, const char *val2, char *buffer, unsigned radi int shift; int counter; - int offset = 0; int bitoffset = 0; - assert((_sign(val2) != -1) || (0 && "negative rightshift")); + assert((offset >= 0) || (0 && "negative rightshift")); assert(((_sign(val1) != -1) || is_signed) || (0 && "unsigned mode and negative value")); assert(((!_bitisset(val1[(radius-1)/4], (radius-1)%4)) || !is_signed || (_sign(val1) == -1)) || (0 && "value is positive, should be negative")); assert(((_bitisset(val1[(radius-1)/4], (radius-1)%4)) || !is_signed || (_sign(val1) == 1)) || (0 && "value is negative, should be positive")); - /*XXX get the value of val2, this might result in trouble * - * (but who wants shifts THAT far anyway) */ - for (counter = MAX_VALUE_SIZE - 1; counter >= 0; counter--) - { - offset = (offset << 4) | (_val(val2[counter])); - } - - shift = offset % 4; /* this is val2 % 4 */ - sign = ((signed_shift) && (_sign(val1) == -1))?(SC_F):(SC_0); + /* if shifting far enough the result is either 0 or -1 */ if (offset >= radius) { - memset(buffer, sign, CALC_BUFFER_SIZE); + if (!sc_is_zero(val1)) { + carry_flag = 1; + } + memset(buffer, sign, calc_buffer_size); return; } + + shift = offset % 4; offset = offset / 4; - buffer[0] = shrs_table[_val(val1[offset])][shift][0]; + /* check if any bits are lost, and set carry_flag if so */ + for (counter = 0; counter < offset; counter++) + { + if (val1[counter] != 0) + { + carry_flag = 1; + break; + } + } + if ((_val(val1[counter]) & ((1< 0) { + buffer[counter] = shrs_table[_val(val1[offset])][shift][0]; + counter = 1; + } + for (; counter < radius/4 - offset; counter++) { shrs = shrs_table[_val(val1[counter + offset])][shift]; buffer[counter] = shrs[0]; @@ -761,9 +894,8 @@ static void _shr(const char *val1, const char *val2, char *buffer, unsigned radi } /* the last digit is special in regard of signed/unsigned shift */ - /* counter = radius/4 (after for loop) */ bitoffset = radius%4; - msd = val1[counter]; /* most significant digit */ + msd = (radius/4 0) buffer[counter - 1] = or_table[_val(buffer[counter-1])][_val(shrs[1])]; /* fill with SC_F or SC_0 depending on sign */ - for (counter++; counter < CALC_BUFFER_SIZE; counter++) + for (counter++; counter < calc_buffer_size; counter++) { buffer[counter] = sign; } } -/* positive: low-order -> high order, negative other direction */ -static void _rot(const char *val1, const char *val2, char *buffer, unsigned radius, unsigned is_signed) +/** + * Implements a Rotate Right. + * positive: low-order -> high order, negative other direction + */ +static void _rot(const char *val1, char *buffer, long offset, int radius, unsigned is_signed) { - char temp_buffer[CALC_BUFFER_SIZE]; - - const char *shl; - char carry = SC_0; - - int counter, old_counter; - int shift; - int offset = 0; - int bitoffset; + char *temp1, *temp2; + temp1 = alloca(calc_buffer_size); + temp2 = alloca(calc_buffer_size); - /*XXX get the value of val2, this might result in trouble * - * (but who wants shifts THAT far anyway) */ - for (counter = MAX_VALUE_SIZE - 1; counter >= 0; counter--) - { - offset = (offset << 4) | (_val(val2[counter])); - } - /* rotation by multiples of the typelength is identity */ offset = offset % radius; + + /* rotation by multiples of the type length is identity */ if (offset == 0) { - memmove(buffer, val1, CALC_BUFFER_SIZE); + memmove(buffer, val1, calc_buffer_size); return; } - /* rotation to the right is the same as rotation to the left - * when done by the right amount */ - if (offset < 0) offset = radius + offset; - shift = _val(shift_table[offset % 4]); - offset = offset / 4; - - DEBUGPRINTF(("offset: %d, shift: %d\n", offset, shift)); - for (counter = 0; counter < radius/4 - offset; counter++) - { - shl = mul_table[_val(val1[counter])][_val(shift)]; - temp_buffer[counter + offset] = or_table[_val(shl[0])][_val(carry)]; - carry = shl[1]; - DEBUGPRINTF(("%d(%x): %s\n", counter, shl[0], sc_print_hex(temp_buffer))); - } - old_counter = counter; - for (; counter < radius/4; counter++) - { - shl = mul_table[_val(val1[counter])][_val(shift)]; - temp_buffer[counter - old_counter] = or_table[_val(shl[0])][_val(carry)]; - carry = shl[1]; - DEBUGPRINTF(("%d(%x)> %s\n", counter, shl[0], sc_print_hex(temp_buffer))); - } - temp_buffer[counter - old_counter] = or_table[_val(temp_buffer[counter-old_counter])][_val(carry)]; - - offset = (radius-1)/4; - bitoffset - (radius-1)%4; - /* fill the rest of the buffer depending on msb and mode signedness*/ - if (is_signed && _bitisset(temp_buffer[offset], bitoffset)) - { - - } - else - { - - } - - memcpy(buffer, temp_buffer, CALC_BUFFER_SIZE); + _shl(val1, temp1, offset, radius, is_signed); + _shr(val1, temp2, radius - offset, radius, is_signed, 0); + _bitor(temp1, temp2, buffer); + carry_flag = 0; /* set by shr, but due to rot this is false */ } /***************************************************************************** @@ -860,28 +952,33 @@ const void *sc_get_buffer(void) return (void*)calc_buffer; } -const int sc_get_buffer_length(void) +int sc_get_buffer_length(void) { - return CALC_BUFFER_SIZE; + return calc_buffer_size; } -void sc_val_from_str(const char *str, unsigned int len) +/* FIXME doesn't check for overflows */ +void sc_val_from_str(const char *str, unsigned int len, void *buffer) { const char *orig_str = str; unsigned int orig_len = len; char sign = 0; - char base[CALC_BUFFER_SIZE]; - char val[CALC_BUFFER_SIZE]; + char *base, *val; + + base = alloca(calc_buffer_size); + val = alloca(calc_buffer_size); /* verify valid pointers (not null) */ assert(str); /* a string no characters long is an error */ assert(len); - CLEAR_CALC_BUFFER(); - memset(base, SC_0, CALC_BUFFER_SIZE); - memset(val, SC_0, CALC_BUFFER_SIZE); + if (buffer == NULL) buffer = calc_buffer; + + CLEAR_BUFFER(buffer); + memset(base, SC_0, calc_buffer_size); + memset(val, SC_0, calc_buffer_size); /* strip leading spaces */ while ((len > 0) && (*str == ' ')) { len--; str++; } @@ -935,7 +1032,7 @@ void sc_val_from_str(const char *str, unsigned int len) base[1] = SC_0; base[0] = SC_A; } - /* begin string evaluation, from left to right */ + /* BEGIN string evaluation, from left to right */ while (len > 0) { switch (*str) @@ -1009,26 +1106,54 @@ void sc_val_from_str(const char *str, unsigned int len) } } -void sc_val_from_long(long value) +void sc_val_from_long(long value, void *buffer) { char *pos; - int sign; + char sign, is_minlong; + + if (buffer == NULL) buffer = calc_buffer; + pos = buffer; - pos = calc_buffer; sign = (value < 0); + is_minlong = value == LONG_MIN; - /* FIXME MININT won't work */ - if (sign) value = -value; + /* use absolute value, special treatment of MIN_LONG */ + if (sign) { + if (is_minlong) + value = -(value+1); + else + value = -value; + } - CLEAR_CALC_BUFFER(); + CLEAR_BUFFER(buffer); - while ((value != 0) && (pos < calc_buffer + CALC_BUFFER_SIZE)) + while ((value != 0) && (pos < (char*)buffer + calc_buffer_size)) { - *pos++ = _digit(value % 16); - value /= 16; + *pos++ = _digit(value & 0xf); + value >>= 4; + } + + + if (sign) { + if (is_minlong) + _inc(buffer, buffer); + + _negate(buffer, buffer); } +} - if (sign) _negate(calc_buffer, calc_buffer); +void sc_val_from_ulong(unsigned long value, void *buffer) +{ + unsigned char *pos; + + if (buffer == NULL) buffer = calc_buffer; + pos = buffer; + + while (pos < (unsigned char *)buffer + calc_buffer_size) + { + *pos++ = (unsigned char)_digit(value & 0xf); + value >>= 4; + } } long sc_val_to_long(const void *val) @@ -1036,22 +1161,24 @@ long sc_val_to_long(const void *val) int i; long l = 0; - for (i = CALC_BUFFER_SIZE - 1; i >= 0; i--) + for (i = calc_buffer_size - 1; i >= 0; i--) { l = (l << 4) + _val(((char *)val)[i]); } return l; } -void sc_min_from_bits(unsigned int num_bits, unsigned int sign) +void sc_min_from_bits(unsigned int num_bits, unsigned int sign, void *buffer) { char* pos; int i, bits; - CLEAR_CALC_BUFFER(); + if (buffer == NULL) buffer = calc_buffer; + CLEAR_BUFFER(buffer); + if (!sign) return; /* unsigned means minimum is 0(zero) */ - pos = calc_buffer; + pos = buffer; bits = num_bits - 1; for (i = 0; i < bits/4; i++) @@ -1059,17 +1186,18 @@ void sc_min_from_bits(unsigned int num_bits, unsigned int sign) *pos++ = min_digit[bits%4]; - for (i++; i <= CALC_BUFFER_SIZE - 1; i++) + for (i++; i <= calc_buffer_size - 1; i++) *pos++ = SC_F; } -void sc_max_from_bits(unsigned int num_bits, unsigned int sign) +void sc_max_from_bits(unsigned int num_bits, unsigned int sign, void *buffer) { char* pos; int i, bits; - CLEAR_CALC_BUFFER(); - pos = calc_buffer; + if (buffer == NULL) buffer = calc_buffer; + CLEAR_BUFFER(buffer); + pos = buffer; bits = num_bits - sign; for (i = 0; i < bits/4; i++) @@ -1077,104 +1205,120 @@ void sc_max_from_bits(unsigned int num_bits, unsigned int sign) *pos++ = max_digit[bits%4]; - for (i++; i <= CALC_BUFFER_SIZE - 1; i++) + for (i++; i <= calc_buffer_size - 1; i++) *pos++ = SC_0; } -void sc_calc(const void* value1, const void* value2, unsigned op) +void sc_calc(const void* value1, const void* value2, unsigned op, void *buffer) { - char unused_res[CALC_BUFFER_SIZE]; /* temp buffer holding unused result of divmod */ + char *unused_res; /* temp buffer holding unused result of divmod */ const char *val1 = (const char *)value1; const char *val2 = (const char *)value2; - CLEAR_CALC_BUFFER(); - DEBUGPRINTF(("%s ", sc_print(value1, SC_HEX))); + unused_res = alloca(calc_buffer_size); + + CLEAR_BUFFER(calc_buffer); + carry_flag = 0; + + DEBUGPRINTF_COMPUTATION(("%s ", sc_print_hex(value1))); switch (op) { case SC_NEG: _negate(val1, calc_buffer); - DEBUGPRINTF(("negated: %s\n", sc_print_hex(calc_buffer))); - return; + DEBUGPRINTF_COMPUTATION(("negated: %s\n", sc_print_hex(calc_buffer))); + break; case SC_OR: - DEBUGPRINTF(("| ")); + DEBUGPRINTF_COMPUTATION(("| ")); _bitor(val1, val2, calc_buffer); break; case SC_AND: - DEBUGPRINTF(("& ")); + DEBUGPRINTF_COMPUTATION(("& ")); _bitand(val1, val2, calc_buffer); break; case SC_XOR: - DEBUGPRINTF(("^ ")); + DEBUGPRINTF_COMPUTATION(("^ ")); _bitxor(val1, val2, calc_buffer); break; case SC_NOT: _bitnot(val1, calc_buffer); - DEBUGPRINTF(("bit-negated: %s\n", sc_print_hex(calc_buffer))); - return; + DEBUGPRINTF_COMPUTATION(("bit-negated: %s\n", sc_print_hex(calc_buffer))); + break; case SC_ADD: - DEBUGPRINTF(("+ ")); + DEBUGPRINTF_COMPUTATION(("+ ")); _add(val1, val2, calc_buffer); break; case SC_SUB: - DEBUGPRINTF(("- ")); + DEBUGPRINTF_COMPUTATION(("- ")); _sub(val1, val2, calc_buffer); break; case SC_MUL: - DEBUGPRINTF(("* ")); + DEBUGPRINTF_COMPUTATION(("* ")); _mul(val1, val2, calc_buffer); break; case SC_DIV: - DEBUGPRINTF(("/ ")); + DEBUGPRINTF_COMPUTATION(("/ ")); _divmod(val1, val2, calc_buffer, unused_res); break; case SC_MOD: - DEBUGPRINTF(("%% ")); + DEBUGPRINTF_COMPUTATION(("%% ")); _divmod(val1, val2, unused_res, calc_buffer); break; default: assert(0); } - DEBUGPRINTF(("%s -> ", sc_print_hex(value2))); - DEBUGPRINTF(("%s\n", sc_print_hex(calc_buffer))); + DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2))); + DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer))); + + if ((buffer != NULL) && (buffer != calc_buffer)) + { + memcpy(buffer, calc_buffer, calc_buffer_size); + } } -void sc_bitcalc(const void* value1, const void* value2, unsigned radius, unsigned sign, unsigned op) +void sc_bitcalc(const void* value1, const void* value2, int radius, int sign, unsigned op, void* buffer) { const char *val1 = (const char *)value1; const char *val2 = (const char *)value2; - CLEAR_CALC_BUFFER(); + long offset; - DEBUGPRINTF(("%s ", sc_print_hex(value1))); + carry_flag = 0; + offset = sc_val_to_long(val2); + + DEBUGPRINTF_COMPUTATION(("%s ", sc_print_hex(value1))); switch (op) { case SC_SHL: - DEBUGPRINTF(("<< ")); - _shl(val1, val2, calc_buffer, radius, sign); + DEBUGPRINTF_COMPUTATION(("<< %ld ", offset)); + _shl(val1, calc_buffer, offset, radius, sign); break; case SC_SHR: - DEBUGPRINTF((">> ")); - _shr(val1, val2, calc_buffer, radius, sign, 0); + DEBUGPRINTF_COMPUTATION((">> %ld ", offset)); + _shr(val1, calc_buffer, offset, radius, sign, 0); break; case SC_SHRS: - DEBUGPRINTF((">>> ")); - _shr(val1, val2, calc_buffer, radius, sign, 1); + DEBUGPRINTF_COMPUTATION((">>> %ld ", offset)); + _shr(val1, calc_buffer, offset, radius, sign, 1); break; case SC_ROT: - DEBUGPRINTF(("<<>> ")); - _rot(val1, val2, calc_buffer, radius, sign); + DEBUGPRINTF_COMPUTATION(("<<>> %ld ", offset)); + _rot(val1, calc_buffer, offset, radius, sign); break; default: assert(0); } - DEBUGPRINTF(("%s -> ", sc_print_hex(value2))); - DEBUGPRINTF(("%s\n", sc_print_hex(calc_buffer))); + DEBUGPRINTF_COMPUTATION(("-> %s\n", sc_print_hex(calc_buffer))); + + if ((buffer != NULL) && (buffer != calc_buffer)) + { + memmove(buffer, calc_buffer, calc_buffer_size); + } } int sc_comp(const void* value1, const void* value2) { - int counter = CALC_BUFFER_SIZE - 1; + int counter = calc_buffer_size - 1; const char *val1 = (const char *)value1; const char *val2 = (const char *)value2; @@ -1196,34 +1340,263 @@ int sc_comp(const void* value1, const void* value2) return (val1[counter] > val2[counter]) ? (1) : (-1); } -char *sc_print(const void *value, unsigned base) +int sc_get_highest_set_bit(const void *value) { + const char *val = (const char*)value; + int high, counter; + + high = calc_buffer_size * 4 - 1; + + for (counter = calc_buffer_size-1; counter >= 0; counter--) { + if (val[counter] == SC_0) high -= 4; + else { + if (val[counter] > SC_7) return high; + else if (val[counter] > SC_3) return high - 1; + else if (val[counter] > SC_1) return high - 2; + else return high - 3; + } + } + return high; +} + +int sc_get_lowest_set_bit(const void *value) +{ + const char *val = (const char*)value; + int low, counter; + char sign; + + sign = (_sign(val)==1)?(SC_0):(SC_F); + low = 0; + + for (counter = 0; counter < calc_buffer_size; counter++) { + if (val[counter] == SC_0) low += 4; + else { + if (val[counter] < SC_2) return low; + else if (val[counter] < SC_4) return low + 1; + else if (val[counter] < SC_8) return low + 2; + else return low + 3; + } + } + return -1; +} + +int sc_is_zero(const void *value) +{ + const char* val = (const char *)value; int counter; - const char *val = (char*)value; + for (counter = 0; counter < calc_buffer_size; counter++) { + if (val[counter] != SC_0) return 0; + } + return 1; +} + +int sc_is_negative(const void *value) +{ + return _sign(value) == -1; +} + +int sc_had_carry(void) +{ + return carry_flag; +} + +unsigned char sc_sub_bits(const void *value, int len, unsigned byte_ofs) +{ + const char *val = (const char *)value; + int nibble_ofs = 2 * byte_ofs; + unsigned char res; + + /* the current scheme uses one byte to store a nibble */ + if (nibble_ofs >= len) + return 0; + + res = _val(val[nibble_ofs]); + if (len > nibble_ofs + 1) + res |= _val(val[nibble_ofs + 1]) << 4; + + return res; +} + +/* + * convert to a string + * FIXME: Doesn't check buffer bounds + */ +const char *sc_print(const void *value, unsigned bits, enum base_t base) +{ + static const char big_digits[] = "0123456789ABCDEF"; + static const char small_digits[] = "0123456789abcdef"; + + char *base_val, *div1_res, *div2_res, *rem_res; + int counter, nibbles, i, sign; + char x; + + const char *val = (const char *)value; + const char *p; + char *m, *n, *t; char *pos; - static char *buf = NULL; + const char *digits = small_digits; - if (buf != NULL) free(buf); - buf = malloc(BIT_PATTERN_SIZE); + base_val = alloca(calc_buffer_size); + div1_res = alloca(calc_buffer_size); + div2_res = alloca(calc_buffer_size); + rem_res = alloca(calc_buffer_size); - pos = buf + BIT_PATTERN_SIZE - 1; - *pos = '\0'; + pos = output_buffer + bit_pattern_size; + *(--pos) = '\0'; - switch (base) - { - case SC_HEX: - for (counter = 0; counter < MAX_VALUE_SIZE; counter++) - { - if (val[counter] < SC_A) - *(--pos) = val[counter] + '0'; - else - *(--pos) = val[counter] + 'a' - 10; + /* special case */ + if (bits == 0) { + bits = bit_pattern_size; +#ifdef STRCALC_DEBUG_FULLPRINT + bits <<= 1; +#endif + } + nibbles = bits >> 2; + switch (base) { + + case SC_HEX: + digits = big_digits; + case SC_hex: + for (counter = 0; counter < nibbles; ++counter) { + *(--pos) = digits[_val(val[counter])]; +#ifdef STRCALC_DEBUG_GROUPPRINT + if ((counter+1)%8 == 0) + *(--pos) = ' '; +#endif + } + + /* last nibble must be masked */ + if (bits & 3) { + x = and_table[_val(val[++counter])][bits & 3]; + *(--pos) = digits[_val(x)]; + } + + /* now kill zeros */ + for (; counter > 1; --counter, ++pos) { +#ifdef STRCALC_DEBUG_GROUPPRINT + if (pos[0] == ' ') ++pos; +#endif + if (pos[0] != '0') + break; + } + break; + + case SC_BIN: + for (counter = 0; counter < nibbles; ++counter) { + pos -= 4; + p = binary_table[_val(val[counter])]; + pos[0] = p[0]; + pos[1] = p[1]; + pos[2] = p[2]; + pos[3] = p[3]; + } + + /* last nibble must be masked */ + if (bits & 3) { + x = and_table[_val(val[++counter])][bits & 3]; + + pos -= 4; + p = binary_table[_val(x)]; + pos[0] = p[0]; + pos[1] = p[1]; + pos[2] = p[2]; + pos[3] = p[3]; + } + + /* now kill zeros */ + for (counter <<= 2; counter > 1; --counter, ++pos) + if (pos[0] != '0') + break; + break; + + case SC_DEC: + case SC_OCT: + memset(base_val, SC_0, calc_buffer_size); + base_val[0] = base == SC_DEC ? SC_A : SC_8; + + p = val; + sign = 0; + if (base == SC_DEC) { + /* check for negative values */ + if (_bit(val, bits - 1)) { + _negate(val, div2_res); + sign = 1; + p = div2_res; } - break; + } - default: - assert(0); - } + /* transfer data into oscillating buffers */ + memset(div1_res, SC_0, calc_buffer_size); + for (counter = 0; counter < nibbles; ++counter) + div1_res[counter] = p[counter]; + + /* last nibble must be masked */ + if (bits & 3) { + ++counter; + + div1_res[counter] = and_table[_val(p[counter])][bits & 3]; + } + + m = div1_res; + n = div2_res; + for (;;) { + _divmod(m, base_val, n, rem_res); + t = m; + m = n; + n = t; + *(--pos) = digits[_val(rem_res[0])]; + + x = 0; + for (i = 0; i < sizeof(div1_res); ++i) + x |= _val(m[i]); + + if (x == 0) + break; + } + if (sign) + *(--pos) = '-'; + break; + + default: + printf("%i\n", base); + assert(0); + return NULL; +} return pos; } + +void init_strcalc(int precision) +{ + if (calc_buffer == NULL) { + if (precision <= 0) precision = SC_DEFAULT_PRECISION; + + /* round up to multiple of 4 */ + precision = (precision + 3) & ~3; + + bit_pattern_size = (precision); + calc_buffer_size = (precision / 2); + max_value_size = (precision / 4); + + calc_buffer = malloc(calc_buffer_size+1 * sizeof(char)); + output_buffer = malloc(bit_pattern_size+1 * sizeof(char)); + + if (calc_buffer == NULL || output_buffer == NULL) { + assert(0 && "malloc failed"); + exit(-1); + } + + DEBUGPRINTF(("init strcalc: \n\tPRECISION: %d\n\tCALC_BUFFER_SIZE = %d\n\tMAX_VALUE_SIZE = %d\n\tbuffer pointer: %p\n", precision, calc_buffer_size, max_value_size, calc_buffer)); + } +} + + +void finish_strcalc() { + free(calc_buffer); calc_buffer = NULL; + free(output_buffer); output_buffer = NULL; +} + +int sc_get_precision(void) +{ + return bit_pattern_size; +}