X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Ftv%2Fstrcalc.c;h=6e45a26b4bbdc13f03242d6ae9b30995f1a2bfb3;hb=4ca2b9085b12d5dac2d975a830f7e74148e67e78;hp=fa054f66df69d2d13ea8034d03761d23e774851d;hpb=54ce4eb3599f32b1dfffeaf0dd071f1907d2b898;p=libfirm diff --git a/ir/tv/strcalc.c b/ir/tv/strcalc.c index fa054f66d..6e45a26b4 100644 --- a/ir/tv/strcalc.c +++ b/ir/tv/strcalc.c @@ -1,52 +1,84 @@ -/****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. + */ -#include /* assertions */ -#include /* memset/memcmp */ -#include "strcalc.h" +#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 /* output for error messages */ -#include +#include /* definition of LONG_MIN, used in sc_get_val_from_long */ + +#include "strcalc.h" +#include "xmalloc.h" /* * 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__) -/* shortcut output for debugging only, gices always full precisition */ -#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) +/* shortcut output for debugging */ +# define sc_print_hex(a) sc_print((a), 0, SC_HEX, 0) +# define sc_print_dec(a) sc_print((a), 0, SC_DEC, 1) +# define sc_print_oct(a) sc_print((a), 0, SC_OCT, 0) +# define sc_print_bin(a) sc_print((a), 0, SC_BIN, 0) - -#if 0 +#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 */ - +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 sex_digit[4] = { SC_E, SC_C, SC_8, SC_0 }; +static const char zex_digit[4] = { SC_1, SC_3, SC_7, SC_F }; 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 }; @@ -96,7 +128,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 }, @@ -386,7 +418,7 @@ static char const shrs_table[16][4][2] = { { {SC_F, SC_0}, {SC_7, SC_8}, {SC_3, SC_C}, {SC_1, SC_E} } }; -/* for converting to binary string */ +/** 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" @@ -405,48 +437,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) { @@ -460,23 +524,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)]; @@ -484,22 +557,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 */ @@ -514,11 +605,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 * @@ -548,77 +639,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 divisor is zero this won't work (quot is zero) */ + if (sc_comp(divisor, quot) == 0) assert(0 && "division by zero!"); /* 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 (_sign(dividend) == -1) - { + 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)) { @@ -627,14 +721,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); @@ -656,82 +750,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; @@ -740,35 +848,47 @@ 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(((_sign(val1) != -1) || is_signed) || (0 && "unsigned mode and negative value")); + assert((offset >= 0) || (0 && "negative rightshift")); 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]; @@ -776,9 +896,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 */ } /***************************************************************************** @@ -875,28 +954,63 @@ 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; +} + +/** + * Do sign extension if the mode is signed, otherwise to zero extension. + */ +void sign_extend(char *calc_buffer, ir_mode *mode) { + int bits = get_mode_size_bits(mode) - 1; + int nibble = bits >> 2; + int max = max_digit[bits & 3]; + int i; + + if (mode_is_signed(mode)) { + if (calc_buffer[nibble] > max) { + /* sign bit is set, we need sign expansion */ + + for (i = nibble + 1; i < calc_buffer_size; ++i) + calc_buffer[i] = SC_F; + calc_buffer[nibble] = or_table[(int)calc_buffer[nibble]][(int)sex_digit[bits & 3]]; + } else { + /* set all bits to zero */ + for (i = nibble + 1; i < calc_buffer_size; ++i) + calc_buffer[i] = SC_0; + calc_buffer[nibble] = and_table[(int)calc_buffer[nibble]][(int)zex_digit[bits & 3]]; + } + } else { + /* do zero extension */ + for (i = nibble + 1; i < calc_buffer_size; ++i) + calc_buffer[i] = SC_0; + calc_buffer[nibble] = and_table[(int)calc_buffer[nibble]][(int)zex_digit[bits & 3]]; + } } -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, ir_mode *mode) { 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); + CLEAR_BUFFER(base); + CLEAR_BUFFER(val); /* strip leading spaces */ while ((len > 0) && (*str == ' ')) { len--; str++; } @@ -950,7 +1064,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) @@ -1019,31 +1133,59 @@ void sc_val_from_str(const char *str, unsigned int len) } /* while (len > 0 ) */ if (sign) - { _negate(calc_buffer, calc_buffer); - } + + /* beware: even if hex numbers have no sign, we need sign extension here */ + sign_extend(calc_buffer, mode); } -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 to avoid overflow */ + 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) @@ -1051,22 +1193,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++) @@ -1074,17 +1218,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++) @@ -1092,104 +1237,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; @@ -1211,10 +1372,71 @@ int sc_comp(const void* value1, const void* value2) return (val1[counter] > val2[counter]) ? (1) : (-1); } +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; + + 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; - unsigned nibble_ofs = 2 * 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 */ @@ -1230,53 +1452,66 @@ unsigned char sc_sub_bits(const void *value, int len, unsigned byte_ofs) /* * convert to a string + * FIXME: Doesn't check buffer bounds */ -const char *sc_print(const void *value, unsigned bits, enum base_t base) +const char *sc_print(const void *value, unsigned bits, enum base_t base, int signed_mode) { - char base_val[CALC_BUFFER_SIZE]; - char div1_res[CALC_BUFFER_SIZE]; - char div2_res[CALC_BUFFER_SIZE]; - char rem_res[CALC_BUFFER_SIZE]; - int counter, nibbles, i; + 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) { - /* TODO: this buffer could be allocated in the initialising phase too */ - buf = malloc(BIT_PATTERN_SIZE + 1); - if (! buf) - return NULL; - } + 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; - *pos = '\0'; + pos = output_buffer + bit_pattern_size; + *(--pos) = '\0'; /* special case */ - if (bits == 0) - bits = BIT_PATTERN_SIZE; - + if (bits == 0) { + bits = bit_pattern_size; +#ifdef STRCALC_DEBUG_FULLPRINT + bits <<= 1; +#endif + } nibbles = bits >> 2; switch (base) { case SC_HEX: - for (counter = 0; counter < nibbles; ++counter) - *(--pos) = "0123456789abcdef"[_val(val[counter])]; + 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) = "0123456789abcdef"[_val(x)]; + *(--pos) = digits[_val(x)]; } /* now kill zeros */ - for (; counter > 1; --counter, ++pos) + for (; counter > 1; --counter, ++pos) { +#ifdef STRCALC_DEBUG_GROUPPRINT + if (pos[0] == ' ') ++pos; +#endif if (pos[0] != '0') break; + } break; case SC_BIN: @@ -1309,19 +1544,30 @@ const char *sc_print(const void *value, unsigned bits, enum base_t base) case SC_DEC: case SC_OCT: - memset(base_val, SC_0, CALC_BUFFER_SIZE); + memset(base_val, SC_0, calc_buffer_size); base_val[0] = base == SC_DEC ? SC_A : SC_8; - /* transfer data into oscilating buffers */ - memset(div1_res, SC_0, CALC_BUFFER_SIZE); + p = val; + sign = 0; + if (signed_mode && base == SC_DEC) { + /* check for negative values */ + if (_bit(val, bits - 1)) { + _negate(val, div2_res); + sign = 1; + p = div2_res; + } + } + + /* transfer data into oscillating buffers */ + memset(div1_res, SC_0, calc_buffer_size); for (counter = 0; counter < nibbles; ++counter) - div1_res[counter] = val[counter]; + div1_res[counter] = p[counter]; - /* last nibble must be masked */ + /* last nibble must be masked */ if (bits & 3) { ++counter; - div1_res[counter] = and_table[_val(val[counter])][bits & 3]; + div1_res[counter] = and_table[_val(p[counter])][bits & 3]; } m = div1_res; @@ -1331,20 +1577,53 @@ const char *sc_print(const void *value, unsigned bits, enum base_t base) t = m; m = n; n = t; - *(--pos) = "0123456789abcdef"[_val(rem_res[0])]; + *(--pos) = digits[_val(rem_res[0])]; x = 0; - for (i = 0; i < sizeof(div1_res); ++i) + for (i = 0; i < calc_buffer_size; ++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 = xmalloc(calc_buffer_size+1 * sizeof(char)); + output_buffer = xmalloc(bit_pattern_size+1 * sizeof(char)); + + 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; +}