2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Provides basic mathematical operations on values represented as strings.
24 * @author Mathias Heil
39 * local definitions and macros
42 #define SC_RESULT(x) ((x) & ((1U << SC_BITS) - 1U))
43 #define SC_CARRY(x) ((unsigned)(x) >> SC_BITS)
45 #define CLEAR_BUFFER(b) assert(b); memset(b, SC_0, calc_buffer_size)
46 #define SHIFT(count) (SC_1 << (count))
47 #define _val(a) ((a)-SC_0)
48 #define _digit(a) ((a)+SC_0)
49 #define _bitisset(digit, pos) (((digit) & SHIFT(pos)) != SC_0)
54 static char *calc_buffer = NULL; /* buffer holding all results */
55 static char *output_buffer = NULL; /* buffer for output */
56 static int bit_pattern_size; /* maximum number of bits */
57 static int calc_buffer_size; /* size of internally stored values */
58 static int max_value_size; /* maximum size of values */
60 static int carry_flag; /**< some computation set the carry_flag:
61 - right shift if bits were lost due to shifting
62 - division if there was a remainder
63 However, the meaning of carry is machine dependent
64 and often defined in other ways! */
66 static const char sex_digit[4] = { SC_E, SC_C, SC_8, SC_0 };
67 static const char zex_digit[4] = { SC_1, SC_3, SC_7, SC_F };
68 static const char max_digit[4] = { SC_0, SC_1, SC_3, SC_7 };
69 static const char min_digit[4] = { SC_F, SC_E, SC_C, SC_8 };
71 static char const shrs_table[16][4][2] = {
72 { {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0} },
73 { {SC_1, SC_0}, {SC_0, SC_8}, {SC_0, SC_4}, {SC_0, SC_2} },
74 { {SC_2, SC_0}, {SC_1, SC_0}, {SC_0, SC_8}, {SC_0, SC_4} },
75 { {SC_3, SC_0}, {SC_1, SC_8}, {SC_0, SC_C}, {SC_0, SC_6} },
76 { {SC_4, SC_0}, {SC_2, SC_0}, {SC_1, SC_0}, {SC_0, SC_8} },
77 { {SC_5, SC_0}, {SC_2, SC_8}, {SC_1, SC_4}, {SC_0, SC_A} },
78 { {SC_6, SC_0}, {SC_3, SC_0}, {SC_1, SC_8}, {SC_0, SC_C} },
79 { {SC_7, SC_0}, {SC_3, SC_8}, {SC_1, SC_C}, {SC_0, SC_E} },
80 { {SC_8, SC_0}, {SC_4, SC_0}, {SC_2, SC_0}, {SC_1, SC_0} },
81 { {SC_9, SC_0}, {SC_4, SC_8}, {SC_2, SC_4}, {SC_1, SC_2} },
82 { {SC_A, SC_0}, {SC_5, SC_0}, {SC_2, SC_8}, {SC_1, SC_4} },
83 { {SC_B, SC_0}, {SC_5, SC_8}, {SC_2, SC_C}, {SC_1, SC_6} },
84 { {SC_C, SC_0}, {SC_6, SC_0}, {SC_3, SC_0}, {SC_1, SC_8} },
85 { {SC_D, SC_0}, {SC_6, SC_8}, {SC_3, SC_4}, {SC_1, SC_A} },
86 { {SC_E, SC_0}, {SC_7, SC_0}, {SC_3, SC_8}, {SC_1, SC_C} },
87 { {SC_F, SC_0}, {SC_7, SC_8}, {SC_3, SC_C}, {SC_1, SC_E} }
90 /** converting a digit to a binary string */
91 static char const *const binary_table[] = {
92 "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
93 "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"
96 /*****************************************************************************
98 *****************************************************************************/
101 * implements the bitwise NOT operation
103 static void do_bitnot(const char *val, char *buffer)
107 for (counter = 0; counter<calc_buffer_size; counter++)
108 buffer[counter] = val[counter] ^ SC_F;
112 * implements the bitwise OR operation
114 static void do_bitor(const char *val1, const char *val2, char *buffer)
118 for (counter = 0; counter<calc_buffer_size; counter++)
119 buffer[counter] = val1[counter] | val2[counter];
123 * implements the bitwise eXclusive OR operation
125 static void do_bitxor(const char *val1, const char *val2, char *buffer)
129 for (counter = 0; counter<calc_buffer_size; counter++)
130 buffer[counter] = val1[counter] ^ val2[counter];
134 * implements the bitwise AND operation
136 static void do_bitand(const char *val1, const char *val2, char *buffer)
140 for (counter = 0; counter<calc_buffer_size; counter++)
141 buffer[counter] = val1[counter] & val2[counter];
145 * implements the bitwise AND not operation
147 static void do_bitandnot(const char *val1, const char *val2, char *buffer)
151 for (counter = 0; counter < calc_buffer_size; ++counter)
152 buffer[counter] = val1[counter] & (SC_F ^ val2[counter]);
156 * returns the sign bit.
158 * @todo This implementation is wrong, as it returns the highest bit of the buffer
159 * NOT the highest bit depending on the real mode
161 static int do_sign(const char *val)
163 return (val[calc_buffer_size-1] <= SC_7) ? (1) : (-1);
167 * returns non-zero if bit at position pos is set
169 static int do_bit(const char *val, int pos)
172 int nibble = pos >> 2;
174 return _bitisset(val[nibble], bit);
178 * Implements a fast ADD + 1
180 static void do_inc(const char *val, char *buffer)
184 while (counter++ < calc_buffer_size) {
189 /* No carry here, *val != SC_F */
190 *buffer = *val + SC_1;
194 /* here a carry could be lost, this is intended because this should
195 * happen only when a value changes sign. */
199 * Implements a unary MINUS
201 static void do_negate(const char *val, char *buffer)
203 do_bitnot(val, buffer);
204 do_inc(buffer, buffer);
208 * Implements a binary ADD
210 * @todo The implementation of carry is wrong, as it is the
211 * calc_buffer_size carry, not the mode depending
213 static void do_add(const char *val1, const char *val2, char *buffer)
215 unsigned carry = SC_0;
216 for (int counter = 0; counter < calc_buffer_size; ++counter) {
217 unsigned const sum = val1[counter] + val2[counter] + carry;
218 buffer[counter] = SC_RESULT(sum);
219 carry = SC_CARRY(sum);
221 carry_flag = carry != SC_0;
225 * Implements a binary SUB
227 static void do_sub(const char *val1, const char *val2, char *buffer)
229 char *temp_buffer = (char*) alloca(calc_buffer_size); /* intermediate buffer to hold -val2 */
231 do_negate(val2, temp_buffer);
232 do_add(val1, temp_buffer, buffer);
236 * Implements a binary MUL
238 static void do_mul(const char *val1, const char *val2, char *buffer)
240 char *temp_buffer; /* result buffer */
241 char *neg_val1; /* abs of val1 */
242 char *neg_val2; /* abs of val2 */
244 char sign = 0; /* marks result sign */
245 int c_inner, c_outer; /* loop counters */
247 temp_buffer = (char*) alloca(calc_buffer_size);
248 neg_val1 = (char*) alloca(calc_buffer_size);
249 neg_val2 = (char*) alloca(calc_buffer_size);
251 /* init result buffer to zeros */
252 memset(temp_buffer, SC_0, calc_buffer_size);
254 /* the multiplication works only for positive values, for negative values *
255 * it is necessary to negate them and adjust the result accordingly */
256 if (do_sign(val1) == -1) {
257 do_negate(val1, neg_val1);
261 if (do_sign(val2) == -1) {
262 do_negate(val2, neg_val2);
267 for (c_outer = 0; c_outer < max_value_size; c_outer++) {
268 if (val2[c_outer] != SC_0) {
269 unsigned carry = SC_0; /* container for carries */
270 for (c_inner = 0; c_inner < max_value_size; c_inner++) {
271 /* do the following calculation: *
272 * Add the current carry, the value at position c_outer+c_inner *
273 * and the result of the multiplication of val1[c_inner] and *
274 * val2[c_outer]. This is the usual pen-and-paper multiplication. */
276 /* multiplicate the two digits */
277 unsigned const mul = val1[c_inner] * val2[c_outer];
278 /* add old value to result of multiplication and the carry */
279 unsigned const sum = temp_buffer[c_inner + c_outer] + mul + carry;
281 /* all carries together result in new carry. This is always smaller *
283 * Both multiplicands, the carry and the value already in the temp *
284 * buffer are single digits and their value is therefore at most *
287 * (b-1)(b-1)+(b-1)+(b-1) = b*b-1 *
288 * The tables list all operations rem b, so the carry is at most *
289 * (b*b-1)rem b = -1rem b = b-1 */
290 temp_buffer[c_inner + c_outer] = SC_RESULT(sum);
291 carry = SC_CARRY(sum);
294 /* A carry may hang over */
295 /* c_outer is always smaller than max_value_size! */
296 temp_buffer[max_value_size + c_outer] = carry;
301 do_negate(temp_buffer, buffer);
303 memcpy(buffer, temp_buffer, calc_buffer_size);
307 * Shift the buffer to left and add a 4 bit digit
309 static void do_push(const char digit, char *buffer)
313 for (counter = calc_buffer_size - 2; counter >= 0; counter--) {
314 buffer[counter+1] = buffer[counter];
320 * Implements truncating integer division and remainder.
322 * Note: This is MOST slow
324 static void do_divmod(const char *rDividend, const char *divisor, char *quot, char *rem)
326 const char *dividend = rDividend;
327 const char *minus_divisor;
331 char div_sign = 0; /* remember division result sign */
332 char rem_sign = 0; /* remember remainder result sign */
334 int c_dividend; /* loop counters */
336 neg_val1 = (char*) alloca(calc_buffer_size);
337 neg_val2 = (char*) alloca(calc_buffer_size);
339 /* clear result buffer */
340 memset(quot, SC_0, calc_buffer_size);
341 memset(rem, SC_0, calc_buffer_size);
343 /* if the divisor is zero this won't work (quot is zero) */
344 if (sc_comp(divisor, quot) == 0) assert(0 && "division by zero!");
346 /* if the dividend is zero result is zero (quot is zero) */
347 if (sc_comp(dividend, quot) == 0)
350 if (do_sign(dividend) == -1) {
351 do_negate(dividend, neg_val1);
357 do_negate(divisor, neg_val2);
358 if (do_sign(divisor) == -1) {
360 minus_divisor = divisor;
363 minus_divisor = neg_val2;
365 /* if divisor >= dividend division is easy
366 * (remember these are absolute values) */
367 switch (sc_comp(dividend, divisor)) {
368 case 0: /* dividend == divisor */
372 case -1: /* dividend < divisor */
373 memcpy(rem, dividend, calc_buffer_size);
376 default: /* unluckily division is necessary :( */
380 for (c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) {
381 do_push(dividend[c_dividend], rem);
384 if (sc_comp(rem, divisor) != -1) { /* remainder >= divisor */
385 /* subtract until the remainder becomes negative, this should
386 * be faster than comparing remainder with divisor */
387 do_add(rem, minus_divisor, rem);
389 while (do_sign(rem) == 1) {
390 quot[0] = SC_RESULT(quot[0] + SC_1); /* TODO can this generate carry or is masking redundant? */
391 do_add(rem, minus_divisor, rem);
394 /* subtracted one too much */
395 do_add(rem, divisor, rem);
399 /* sets carry if remainder is non-zero ??? */
400 carry_flag = !sc_is_zero(rem);
403 do_negate(quot, quot);
410 * Implements a Shift Left, which can either preserve the sign bit
413 * @todo Assertions seems to be wrong
415 static void do_shl(const char *val1, char *buffer, long shift_cnt, int bitsize, unsigned is_signed)
420 assert((shift_cnt >= 0) || (0 && "negative leftshift"));
421 assert(((do_sign(val1) != -1) || is_signed) || (0 && "unsigned mode and negative value"));
422 assert(((!_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == -1)) || (0 && "value is positive, should be negative"));
423 assert(((_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == 1)) || (0 && "value is negative, should be positive"));
425 /* if shifting far enough the result is zero */
426 if (shift_cnt >= bitsize) {
427 memset(buffer, SC_0, calc_buffer_size);
431 unsigned const shift = shift_cnt % SC_BITS;
432 shift_cnt = shift_cnt / 4;
434 /* shift the single digits some bytes (offset) and some bits (table)
436 unsigned carry = SC_0;
437 for (counter = 0; counter < bitsize/4 - shift_cnt; counter++) {
438 unsigned const shl = val1[counter] << shift | carry;
439 buffer[counter + shift_cnt] = SC_RESULT(shl);
440 carry = SC_CARRY(shl);
443 unsigned const shl = val1[counter] << shift | carry;
444 buffer[counter + shift_cnt] = SC_RESULT(shl);
447 bitoffset = counter - 1;
450 /* fill with zeroes */
451 for (counter = 0; counter < shift_cnt; counter++)
452 buffer[counter] = SC_0;
454 /* if the mode was signed, change sign when the mode's msb is now 1 */
455 shift_cnt = bitoffset + shift_cnt;
456 bitoffset = (bitsize-1) % 4;
457 if (is_signed && _bitisset(buffer[shift_cnt], bitoffset)) {
458 /* this sets the upper bits of the leftmost digit */
459 buffer[shift_cnt] |= min_digit[bitoffset];
460 for (counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
461 buffer[counter] = SC_F;
463 } else if (is_signed && !_bitisset(buffer[shift_cnt], bitoffset)) {
464 /* this clears the upper bits of the leftmost digit */
465 buffer[shift_cnt] &= max_digit[bitoffset];
466 for (counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
467 buffer[counter] = SC_0;
473 * Implements a Shift Right, which can either preserve the sign bit
476 * @param bitsize bitsize of the value to be shifted
478 * @todo Assertions seems to be wrong
480 static void do_shr(const char *val1, char *buffer, long shift_cnt, int bitsize, unsigned is_signed, int signed_shift)
486 int shift_mod, shift_nib;
491 assert((shift_cnt >= 0) || (0 && "negative rightshift"));
492 assert(((!_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == -1)) || (0 && "value is positive, should be negative"));
493 assert(((_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == 1)) || (0 && "value is negative, should be positive"));
495 sign = signed_shift && do_bit(val1, bitsize - 1) ? SC_F : SC_0;
497 /* if shifting far enough the result is either 0 or -1 */
498 if (shift_cnt >= bitsize) {
499 if (!sc_is_zero(val1)) {
502 memset(buffer, sign, calc_buffer_size);
506 shift_mod = shift_cnt & 3;
507 shift_nib = shift_cnt >> 2;
509 /* check if any bits are lost, and set carry_flag if so */
510 for (counter = 0; counter < shift_nib; ++counter) {
511 if (val1[counter] != 0) {
516 if ((_val(val1[counter]) & ((1<<shift_mod)-1)) != 0)
519 /* shift digits to the right with offset, carry and all */
520 buffer[0] = shrs_table[_val(val1[shift_nib])][shift_mod][0];
521 for (counter = 1; counter < ((bitsize + 3) >> 2) - shift_nib; counter++) {
522 shrs = shrs_table[_val(val1[counter + shift_nib])][shift_mod];
523 buffer[counter] = shrs[0];
524 buffer[counter - 1] |= shrs[1];
527 /* the last digit is special in regard of signed/unsigned shift */
528 bitoffset = bitsize & 3;
529 msd = sign; /* most significant digit */
531 /* remove sign bits if mode was signed and this is an unsigned shift */
532 if (!signed_shift && is_signed) {
533 msd &= max_digit[bitoffset];
536 shrs = shrs_table[_val(msd)][shift_mod];
538 /* signed shift and signed mode and negative value means all bits to the left are set */
539 if (signed_shift && sign == SC_F) {
540 buffer[counter] = shrs[0] | min_digit[bitoffset];
542 buffer[counter] = shrs[0];
546 buffer[counter - 1] |= shrs[1];
548 /* fill with SC_F or SC_0 depending on sign */
549 for (counter++; counter < calc_buffer_size; counter++) {
550 buffer[counter] = sign;
555 * Implements a Rotate Left.
556 * positive: low-order -> high order, negative other direction
558 static void do_rotl(const char *val1, char *buffer, long offset, int radius, unsigned is_signed)
561 temp1 = (char*) alloca(calc_buffer_size);
562 temp2 = (char*) alloca(calc_buffer_size);
564 offset = offset % radius;
566 /* rotation by multiples of the type length is identity */
568 memmove(buffer, val1, calc_buffer_size);
572 do_shl(val1, temp1, offset, radius, is_signed);
573 do_shr(val1, temp2, radius - offset, radius, is_signed, 0);
574 do_bitor(temp1, temp2, buffer);
575 carry_flag = 0; /* set by shr, but due to rot this is false */
578 /*****************************************************************************
579 * public functions, declared in strcalc.h
580 *****************************************************************************/
581 const void *sc_get_buffer(void)
583 return (void*)calc_buffer;
586 int sc_get_buffer_length(void)
588 return calc_buffer_size;
592 * Do sign extension if the mode is signed, otherwise to zero extension.
594 void sign_extend(void *buffer, ir_mode *mode)
596 char *calc_buffer = (char*) buffer;
597 int bits = get_mode_size_bits(mode) - 1;
598 int nibble = bits >> 2;
599 int max = max_digit[bits & 3];
602 if (mode_is_signed(mode)) {
603 if (calc_buffer[nibble] > max) {
604 /* sign bit is set, we need sign expansion */
606 for (i = nibble + 1; i < calc_buffer_size; ++i)
607 calc_buffer[i] = SC_F;
608 calc_buffer[nibble] |= sex_digit[bits & 3];
610 /* set all bits to zero */
611 for (i = nibble + 1; i < calc_buffer_size; ++i)
612 calc_buffer[i] = SC_0;
613 calc_buffer[nibble] &= zex_digit[bits & 3];
616 /* do zero extension */
617 for (i = nibble + 1; i < calc_buffer_size; ++i)
618 calc_buffer[i] = SC_0;
619 calc_buffer[nibble] &= zex_digit[bits & 3];
623 /* we assume that '0'-'9', 'a'-'z' and 'A'-'Z' are a range.
624 * The C-standard does theoretically allow otherwise. */
625 static inline void check_ascii(void)
627 /* C standard guarantees that '0'-'9' is a range */
640 int sc_val_from_str(char sign, unsigned base, const char *str,
641 size_t len, void *buffer)
645 assert(sign == -1 || sign == 1);
650 assert(base > 1 && base <= 16);
651 sc_base = (char*) alloca(calc_buffer_size);
652 sc_val_from_ulong(base, sc_base);
654 val = (char*) alloca(calc_buffer_size);
656 buffer = calc_buffer;
658 CLEAR_BUFFER(buffer);
661 /* BEGIN string evaluation, from left to right */
665 if (c >= '0' && c <= '9')
667 else if (c >= 'A' && c <= 'F')
669 else if (c >= 'a' && c <= 'f')
678 /* Radix conversion from base b to base B:
679 * (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
680 /* multiply current value with base */
681 do_mul(sc_base, (const char*) buffer, (char*) buffer);
682 /* add next digit to current value */
683 do_add(val, (const char*) buffer, (char*) buffer);
685 /* get ready for the next letter */
691 do_negate((const char*) buffer, (char*) buffer);
696 void sc_val_from_long(long value, void *buffer)
699 char sign, is_minlong;
701 if (buffer == NULL) buffer = calc_buffer;
702 pos = (char*) buffer;
705 is_minlong = value == LONG_MIN;
707 /* use absolute value, special treatment of MIN_LONG to avoid overflow */
715 CLEAR_BUFFER(buffer);
717 while ((value != 0) && (pos < (char*)buffer + calc_buffer_size)) {
718 *pos++ = _digit(value & 0xf);
724 do_inc((const char*) buffer, (char*) buffer);
726 do_negate((const char*) buffer, (char*) buffer);
730 void sc_val_from_ulong(unsigned long value, void *buffer)
734 if (buffer == NULL) buffer = calc_buffer;
735 pos = (unsigned char*) buffer;
737 while (pos < (unsigned char *)buffer + calc_buffer_size) {
738 *pos++ = (unsigned char)_digit(value & 0xf);
743 long sc_val_to_long(const void *val)
748 for (i = calc_buffer_size - 1; i >= 0; i--) {
749 l = (l << 4) + _val(((char *)val)[i]);
754 void sc_min_from_bits(unsigned int num_bits, unsigned int sign, void *buffer)
759 if (buffer == NULL) buffer = calc_buffer;
760 CLEAR_BUFFER(buffer);
762 if (!sign) return; /* unsigned means minimum is 0(zero) */
764 pos = (char*) buffer;
767 for (i = 0; i < bits/4; i++)
770 *pos++ = min_digit[bits%4];
772 for (i++; i <= calc_buffer_size - 1; i++)
776 void sc_max_from_bits(unsigned int num_bits, unsigned int sign, void *buffer)
781 if (buffer == NULL) buffer = calc_buffer;
782 CLEAR_BUFFER(buffer);
783 pos = (char*) buffer;
785 bits = num_bits - sign;
786 for (i = 0; i < bits/4; i++)
789 *pos++ = max_digit[bits%4];
791 for (i++; i <= calc_buffer_size - 1; i++)
795 void sc_truncate(unsigned int num_bits, void *buffer)
797 char *cbuffer = (char*) buffer;
798 char *pos = cbuffer + (num_bits / 4);
799 char *end = cbuffer + calc_buffer_size;
803 switch (num_bits % 4) {
804 case 0: /* nothing to do */ break;
805 case 1: *pos++ &= SC_1; break;
806 case 2: *pos++ &= SC_3; break;
807 case 3: *pos++ &= SC_7; break;
810 for ( ; pos < end; ++pos)
814 int sc_comp(const void* value1, const void* value2)
816 int counter = calc_buffer_size - 1;
817 const char *val1 = (const char *)value1;
818 const char *val2 = (const char *)value2;
820 /* compare signs first:
821 * the loop below can only compare values of the same sign! */
822 if (do_sign(val1) != do_sign(val2))
823 return (do_sign(val1) == 1)?(1):(-1);
825 /* loop until two digits differ, the values are equal if there
826 * are no such two digits */
827 while (val1[counter] == val2[counter]) {
829 if (counter < 0) return 0;
832 /* the leftmost digit is the most significant, so this returns
833 * the correct result.
834 * This implies the digit enum is ordered */
835 return (val1[counter] > val2[counter]) ? (1) : (-1);
838 int sc_get_highest_set_bit(const void *value)
840 const char *val = (const char*)value;
843 high = calc_buffer_size * 4 - 1;
845 for (counter = calc_buffer_size-1; counter >= 0; counter--) {
846 if (val[counter] == SC_0)
849 if (val[counter] > SC_7) return high;
850 else if (val[counter] > SC_3) return high - 1;
851 else if (val[counter] > SC_1) return high - 2;
852 else return high - 3;
858 int sc_get_lowest_set_bit(const void *value)
860 const char *val = (const char*)value;
864 for (counter = 0; counter < calc_buffer_size; counter++) {
865 switch (val[counter]) {
892 int sc_get_bit_at(const void *value, unsigned pos)
894 const char *val = (const char*) value;
895 unsigned nibble = pos >> 2;
897 return (val[nibble] & SHIFT(pos & 3)) != SC_0;
900 void sc_set_bit_at(void *value, unsigned pos)
902 char *val = (char*) value;
903 unsigned nibble = pos >> 2;
905 val[nibble] |= SHIFT(pos & 3);
908 int sc_is_zero(const void *value)
910 const char* val = (const char *)value;
913 for (counter = 0; counter < calc_buffer_size; ++counter) {
914 if (val[counter] != SC_0)
920 int sc_is_negative(const void *value)
922 return do_sign((const char*) value) == -1;
925 int sc_had_carry(void)
930 unsigned char sc_sub_bits(const void *value, int len, unsigned byte_ofs)
932 const char *val = (const char *)value;
933 int nibble_ofs = 2 * byte_ofs;
936 /* the current scheme uses one byte to store a nibble */
937 if (4 * nibble_ofs >= len)
940 res = _val(val[nibble_ofs]);
941 if (len > 4 * (nibble_ofs + 1))
942 res |= _val(val[nibble_ofs + 1]) << 4;
944 /* kick bits outsize */
945 if (len - 8 * byte_ofs < 8) {
946 res &= (1 << (len - 8 * byte_ofs)) - 1;
952 * convert to a string
953 * FIXME: Doesn't check buffer bounds
955 const char *sc_print(const void *value, unsigned bits, enum base_t base, int signed_mode)
957 static const char big_digits[] = "0123456789ABCDEF";
958 static const char small_digits[] = "0123456789abcdef";
960 char *base_val, *div1_res, *div2_res, *rem_res;
961 int counter, nibbles, i, sign, mask;
964 const char *val = (const char *)value;
968 const char *digits = small_digits;
970 base_val = (char*) alloca(calc_buffer_size);
971 div1_res = (char*) alloca(calc_buffer_size);
972 div2_res = (char*) alloca(calc_buffer_size);
973 rem_res = (char*) alloca(calc_buffer_size);
975 pos = output_buffer + bit_pattern_size;
980 bits = bit_pattern_size;
988 for (counter = 0; counter < nibbles; ++counter) {
989 *(--pos) = digits[_val(val[counter])];
992 /* last nibble must be masked */
994 mask = zex_digit[(bits & 3) - 1];
995 x = val[counter++] & mask;
996 *(--pos) = digits[_val(x)];
1000 for (; counter > 1; --counter, ++pos) {
1007 for (counter = 0; counter < nibbles; ++counter) {
1009 p = binary_table[_val(val[counter])];
1016 /* last nibble must be masked */
1018 mask = zex_digit[(bits & 3) - 1];
1019 x = val[counter++] & mask;
1022 p = binary_table[_val(x)];
1029 /* now kill zeros */
1030 for (counter <<= 2; counter > 1; --counter, ++pos)
1037 memset(base_val, SC_0, calc_buffer_size);
1038 base_val[0] = base == SC_DEC ? SC_A : SC_8;
1042 if (signed_mode && base == SC_DEC) {
1043 /* check for negative values */
1044 if (do_bit(val, bits - 1)) {
1045 do_negate(val, div2_res);
1051 /* transfer data into oscillating buffers */
1052 memset(div1_res, SC_0, calc_buffer_size);
1053 for (counter = 0; counter < nibbles; ++counter)
1054 div1_res[counter] = p[counter];
1056 /* last nibble must be masked */
1058 mask = zex_digit[(bits & 3) - 1];
1059 div1_res[counter] = p[counter] & mask;
1066 do_divmod(m, base_val, n, rem_res);
1070 *(--pos) = digits[_val(rem_res[0])];
1073 for (i = 0; i < calc_buffer_size; ++i)
1084 panic("Unsupported base %d", base);
1089 void init_strcalc(int precision)
1091 if (calc_buffer == NULL) {
1092 if (precision <= 0) precision = SC_DEFAULT_PRECISION;
1094 /* round up to multiple of 4 */
1095 precision = (precision + 3) & ~3;
1097 bit_pattern_size = (precision);
1098 calc_buffer_size = (precision / 2);
1099 max_value_size = (precision / 4);
1101 calc_buffer = XMALLOCN(char, calc_buffer_size + 1);
1102 output_buffer = XMALLOCN(char, bit_pattern_size + 1);
1107 void finish_strcalc(void)
1109 free(calc_buffer); calc_buffer = NULL;
1110 free(output_buffer); output_buffer = NULL;
1113 int sc_get_precision(void)
1115 return bit_pattern_size;
1119 void sc_add(const void *value1, const void *value2, void *buffer)
1121 CLEAR_BUFFER(calc_buffer);
1124 do_add((const char*) value1, (const char*) value2, (char*) calc_buffer);
1126 if ((buffer != NULL) && (buffer != calc_buffer)) {
1127 memcpy(buffer, calc_buffer, calc_buffer_size);
1131 void sc_sub(const void *value1, const void *value2, void *buffer)
1133 CLEAR_BUFFER(calc_buffer);
1136 do_sub((const char*) value1, (const char*) value2, calc_buffer);
1138 if ((buffer != NULL) && (buffer != calc_buffer)) {
1139 memcpy(buffer, calc_buffer, calc_buffer_size);
1143 void sc_neg(const void *value1, void *buffer)
1147 do_negate((const char*) value1, calc_buffer);
1149 if ((buffer != NULL) && (buffer != calc_buffer)) {
1150 memcpy(buffer, calc_buffer, calc_buffer_size);
1154 void sc_and(const void *value1, const void *value2, void *buffer)
1156 CLEAR_BUFFER(calc_buffer);
1159 do_bitand((const char*) value1, (const char*) value2, calc_buffer);
1161 if ((buffer != NULL) && (buffer != calc_buffer)) {
1162 memcpy(buffer, calc_buffer, calc_buffer_size);
1166 void sc_andnot(const void *value1, const void *value2, void *buffer)
1168 CLEAR_BUFFER(calc_buffer);
1171 do_bitandnot((const char*) value1, (const char*) value2, calc_buffer);
1173 if (buffer != NULL && buffer != calc_buffer) {
1174 memcpy(buffer, calc_buffer, calc_buffer_size);
1178 void sc_or(const void *value1, const void *value2, void *buffer)
1180 CLEAR_BUFFER(calc_buffer);
1183 do_bitor((const char*) value1, (const char*) value2, calc_buffer);
1185 if ((buffer != NULL) && (buffer != calc_buffer)) {
1186 memcpy(buffer, calc_buffer, calc_buffer_size);
1190 void sc_xor(const void *value1, const void *value2, void *buffer)
1192 CLEAR_BUFFER(calc_buffer);
1195 do_bitxor((const char*) value1, (const char*) value2, calc_buffer);
1197 if ((buffer != NULL) && (buffer != calc_buffer)) {
1198 memcpy(buffer, calc_buffer, calc_buffer_size);
1202 void sc_not(const void *value1, void *buffer)
1204 CLEAR_BUFFER(calc_buffer);
1207 do_bitnot((const char*) value1, calc_buffer);
1209 if ((buffer != NULL) && (buffer != calc_buffer)) {
1210 memcpy(buffer, calc_buffer, calc_buffer_size);
1214 void sc_mul(const void *value1, const void *value2, void *buffer)
1216 CLEAR_BUFFER(calc_buffer);
1219 do_mul((const char*) value1, (const char*) value2, calc_buffer);
1221 if ((buffer != NULL) && (buffer != calc_buffer)) {
1222 memcpy(buffer, calc_buffer, calc_buffer_size);
1226 void sc_div(const void *value1, const void *value2, void *buffer)
1228 /* temp buffer holding unused result of divmod */
1229 char *unused_res = (char*) alloca(calc_buffer_size);
1231 CLEAR_BUFFER(calc_buffer);
1234 do_divmod((const char*) value1, (const char*) value2, calc_buffer, unused_res);
1236 if ((buffer != NULL) && (buffer != calc_buffer)) {
1237 memcpy(buffer, calc_buffer, calc_buffer_size);
1241 void sc_mod(const void *value1, const void *value2, void *buffer)
1243 /* temp buffer holding unused result of divmod */
1244 char *unused_res = (char*) alloca(calc_buffer_size);
1246 CLEAR_BUFFER(calc_buffer);
1249 do_divmod((const char*) value1, (const char*) value2, unused_res, calc_buffer);
1251 if ((buffer != NULL) && (buffer != calc_buffer)) {
1252 memcpy(buffer, calc_buffer, calc_buffer_size);
1256 void sc_divmod(const void *value1, const void *value2, void *div_buffer, void *mod_buffer)
1258 CLEAR_BUFFER(calc_buffer);
1261 do_divmod((const char*) value1, (const char*) value2, (char*) div_buffer, (char*) mod_buffer);
1265 void sc_shlI(const void *val1, long shift_cnt, int bitsize, int sign, void *buffer)
1269 do_shl((const char*) val1, calc_buffer, shift_cnt, bitsize, sign);
1271 if ((buffer != NULL) && (buffer != calc_buffer)) {
1272 memmove(buffer, calc_buffer, calc_buffer_size);
1276 void sc_shl(const void *val1, const void *val2, int bitsize, int sign, void *buffer)
1278 long offset = sc_val_to_long(val2);
1280 sc_shlI(val1, offset, bitsize, sign, buffer);
1283 void sc_shrI(const void *val1, long shift_cnt, int bitsize, int sign, void *buffer)
1287 do_shr((const char*) val1, calc_buffer, shift_cnt, bitsize, sign, 0);
1289 if ((buffer != NULL) && (buffer != calc_buffer)) {
1290 memmove(buffer, calc_buffer, calc_buffer_size);
1294 void sc_shr(const void *val1, const void *val2, int bitsize, int sign, void *buffer)
1296 long shift_cnt = sc_val_to_long(val2);
1298 sc_shrI(val1, shift_cnt, bitsize, sign, buffer);
1301 void sc_shrsI(const void *val1, long shift_cnt, int bitsize, int sign, void *buffer)
1305 do_shr((const char*) val1, calc_buffer, shift_cnt, bitsize, sign, 1);
1307 if ((buffer != NULL) && (buffer != calc_buffer)) {
1308 memmove(buffer, calc_buffer, calc_buffer_size);
1312 void sc_shrs(const void *val1, const void *val2, int bitsize, int sign, void *buffer)
1314 long offset = sc_val_to_long(val2);
1318 do_shr((const char*) val1, calc_buffer, offset, bitsize, sign, 1);
1320 if ((buffer != NULL) && (buffer != calc_buffer)) {
1321 memmove(buffer, calc_buffer, calc_buffer_size);
1325 void sc_rotl(const void *val1, const void *val2, int bitsize, int sign, void *buffer)
1327 long offset = sc_val_to_long(val2);
1331 do_rotl((const char*) val1, calc_buffer, offset, bitsize, sign);
1333 if ((buffer != NULL) && (buffer != calc_buffer)) {
1334 memmove(buffer, calc_buffer, calc_buffer_size);
1338 void sc_zero(void *buffer)
1341 buffer = calc_buffer;
1342 CLEAR_BUFFER(buffer);