nsz Git - libfirm/blob - ir/tv/strcalc.c

   1 /*
   2  * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Provides basic mathematical operations on values represented as strings.
  23  * @date     2003
  24  * @author   Mathias Heil
  25  */
  26 #include "config.h"
  27
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <assert.h>
  31 #include <stdio.h>
  32 #include <limits.h>
  33
  34 #include "strcalc.h"
  35 #include "xmalloc.h"
  36 #include "error.h"
  37
  38 /*
  39  * local definitions and macros
  40  */
  41 #define SC_BITS      4
  42 #define SC_RESULT(x) ((x) & ((1U << SC_BITS) - 1U))
  43 #define SC_CARRY(x)  ((unsigned)(x) >> SC_BITS)
  44
  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)
  50
  51 /*
  52  * private variables
  53  */
  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 */
  59
  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! */
  65
  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 };
  70
  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} }
  88                                    };
  89
  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"
  94 };
  95
  96 /*****************************************************************************
  97  * private functions
  98  *****************************************************************************/
  99
 100 /**
 101  * implements the bitwise NOT operation
 102  */
 103 static void do_bitnot(const char *val, char *buffer)
 104 {
 105         int counter;
 106
 107         for (counter = 0; counter<calc_buffer_size; counter++)
 108                 buffer[counter] = val[counter] ^ SC_F;
 109 }
 110
 111 /**
 112  * implements the bitwise OR operation
 113  */
 114 static void do_bitor(const char *val1, const char *val2, char *buffer)
 115 {
 116         int counter;
 117
 118         for (counter = 0; counter<calc_buffer_size; counter++)
 119                 buffer[counter] = val1[counter] | val2[counter];
 120 }
 121
 122 /**
 123  * implements the bitwise eXclusive OR operation
 124  */
 125 static void do_bitxor(const char *val1, const char *val2, char *buffer)
 126 {
 127         int counter;
 128
 129         for (counter = 0; counter<calc_buffer_size; counter++)
 130                 buffer[counter] = val1[counter] ^ val2[counter];
 131 }
 132
 133 /**
 134  * implements the bitwise AND operation
 135  */
 136 static void do_bitand(const char *val1, const char *val2, char *buffer)
 137 {
 138         int counter;
 139
 140         for (counter = 0; counter<calc_buffer_size; counter++)
 141                 buffer[counter] = val1[counter] & val2[counter];
 142 }
 143
 144 /**
 145  * implements the bitwise AND not operation
 146  */
 147 static void do_bitandnot(const char *val1, const char *val2, char *buffer)
 148 {
 149         int counter;
 150
 151         for (counter = 0; counter < calc_buffer_size; ++counter)
 152                 buffer[counter] = val1[counter] & (SC_F ^ val2[counter]);
 153 }
 154
 155 /**
 156  * returns the sign bit.
 157  *
 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
 160  */
 161 static int do_sign(const char *val)
 162 {
 163         return (val[calc_buffer_size-1] <= SC_7) ? (1) : (-1);
 164 }
 165
 166 /**
 167  * returns non-zero if bit at position pos is set
 168  */
 169 static int do_bit(const char *val, int pos)
 170 {
 171         int bit    = pos & 3;
 172         int nibble = pos >> 2;
 173
 174         return _bitisset(val[nibble], bit);
 175 }
 176
 177 /**
 178  * Implements a fast ADD + 1
 179  */
 180 static void do_inc(const char *val, char *buffer)
 181 {
 182         int counter = 0;
 183
 184         while (counter++ < calc_buffer_size) {
 185                 if (*val == SC_F) {
 186                         *buffer++ = SC_0;
 187                         val++;
 188                 } else {
 189                         /* No carry here, *val != SC_F */
 190                         *buffer = *val + SC_1;
 191                         return;
 192                 }
 193         }
 194         /* here a carry could be lost, this is intended because this should
 195          * happen only when a value changes sign. */
 196 }
 197
 198 /**
 199  * Implements a unary MINUS
 200  */
 201 static void do_negate(const char *val, char *buffer)
 202 {
 203         do_bitnot(val, buffer);
 204         do_inc(buffer, buffer);
 205 }
 206
 207 /**
 208  * Implements a binary ADD
 209  *
 210  * @todo The implementation of carry is wrong, as it is the
 211  *       calc_buffer_size carry, not the mode depending
 212  */
 213 static void do_add(const char *val1, const char *val2, char *buffer)
 214 {
 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);
 220         }
 221         carry_flag = carry != SC_0;
 222 }
 223
 224 /**
 225  * Implements a binary SUB
 226  */
 227 static void do_sub(const char *val1, const char *val2, char *buffer)
 228 {
 229         char *temp_buffer = (char*) alloca(calc_buffer_size); /* intermediate buffer to hold -val2 */
 230
 231         do_negate(val2, temp_buffer);
 232         do_add(val1, temp_buffer, buffer);
 233 }
 234
 235 /**
 236  * Implements a binary MUL
 237  */
 238 static void do_mul(const char *val1, const char *val2, char *buffer)
 239 {
 240         char *temp_buffer; /* result buffer */
 241         char *neg_val1;    /* abs of val1 */
 242         char *neg_val2;    /* abs of val2 */
 243
 244         char sign = 0;                      /* marks result sign */
 245         int c_inner, c_outer;               /* loop counters */
 246
 247         temp_buffer = (char*) alloca(calc_buffer_size);
 248         neg_val1 = (char*) alloca(calc_buffer_size);
 249         neg_val2 = (char*) alloca(calc_buffer_size);
 250
 251         /* init result buffer to zeros */
 252         memset(temp_buffer, SC_0, calc_buffer_size);
 253
 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);
 258                 val1 = neg_val1;
 259                 sign ^= 1;
 260         }
 261         if (do_sign(val2) == -1) {
 262                 do_negate(val2, neg_val2);
 263                 val2 = neg_val2;
 264                 sign ^= 1;
 265         }
 266
 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.   */
 275
 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;
 280
 281                                 /* all carries together result in new carry. This is always smaller *
 282                                  * than the base b:                                                 *
 283                                  * Both multiplicands, the carry and the value already in the temp  *
 284                                  * buffer are single digits and their value is therefore at most    *
 285                                  * equal to (b-1).                                                  *
 286                                  * This leads to:                                                   *
 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);
 292                         }
 293
 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;
 297                 }
 298         }
 299
 300         if (sign)
 301                 do_negate(temp_buffer, buffer);
 302         else
 303                 memcpy(buffer, temp_buffer, calc_buffer_size);
 304 }
 305
 306 /**
 307  * Shift the buffer to left and add a 4 bit digit
 308  */
 309 static void do_push(const char digit, char *buffer)
 310 {
 311         int counter;
 312
 313         for (counter = calc_buffer_size - 2; counter >= 0; counter--) {
 314                 buffer[counter+1] = buffer[counter];
 315         }
 316         buffer[0] = digit;
 317 }
 318
 319 /**
 320  * Implements truncating integer division and remainder.
 321  *
 322  * Note: This is MOST slow
 323  */
 324 static void do_divmod(const char *rDividend, const char *divisor, char *quot, char *rem)
 325 {
 326         const char *dividend = rDividend;
 327         const char *minus_divisor;
 328         char *neg_val1;
 329         char *neg_val2;
 330
 331         char div_sign = 0;     /* remember division result sign */
 332         char rem_sign = 0;     /* remember remainder result sign */
 333
 334         int c_dividend;      /* loop counters */
 335
 336         neg_val1 = (char*) alloca(calc_buffer_size);
 337         neg_val2 = (char*) alloca(calc_buffer_size);
 338
 339         /* clear result buffer */
 340         memset(quot, SC_0, calc_buffer_size);
 341         memset(rem, SC_0, calc_buffer_size);
 342
 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!");
 345
 346         /* if the dividend is zero result is zero (quot is zero) */
 347         if (sc_comp(dividend, quot) == 0)
 348                 return;
 349
 350         if (do_sign(dividend) == -1) {
 351                 do_negate(dividend, neg_val1);
 352                 div_sign ^= 1;
 353                 rem_sign ^= 1;
 354                 dividend = neg_val1;
 355         }
 356
 357         do_negate(divisor, neg_val2);
 358         if (do_sign(divisor) == -1) {
 359                 div_sign ^= 1;
 360                 minus_divisor = divisor;
 361                 divisor = neg_val2;
 362         } else
 363                 minus_divisor = neg_val2;
 364
 365         /* if divisor >= dividend division is easy
 366          * (remember these are absolute values) */
 367         switch (sc_comp(dividend, divisor)) {
 368         case 0: /* dividend == divisor */
 369                 quot[0] = SC_1;
 370                 goto end;
 371
 372         case -1: /* dividend < divisor */
 373                 memcpy(rem, dividend, calc_buffer_size);
 374                 goto end;
 375
 376         default: /* unluckily division is necessary :( */
 377                 break;
 378         }
 379
 380         for (c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) {
 381                 do_push(dividend[c_dividend], rem);
 382                 do_push(SC_0, quot);
 383
 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);
 388
 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);
 392                         }
 393
 394                         /* subtracted one too much */
 395                         do_add(rem, divisor, rem);
 396                 }
 397         }
 398 end:
 399         /* sets carry if remainder is non-zero ??? */
 400         carry_flag = !sc_is_zero(rem);
 401
 402         if (div_sign)
 403                 do_negate(quot, quot);
 404
 405         if (rem_sign)
 406                 do_negate(rem, rem);
 407 }
 408
 409 /**
 410  * Implements a Shift Left, which can either preserve the sign bit
 411  * or not.
 412  *
 413  * @todo Assertions seems to be wrong
 414  */
 415 static void do_shl(const char *val1, char *buffer, long shift_cnt, int bitsize, unsigned is_signed)
 416 {
 417         int counter;
 418         int bitoffset = 0;
 419
 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"));
 424
 425         /* if shifting far enough the result is zero */
 426         if (shift_cnt >= bitsize) {
 427                 memset(buffer, SC_0, calc_buffer_size);
 428                 return;
 429         }
 430
 431         unsigned const shift = shift_cnt % SC_BITS;
 432         shift_cnt = shift_cnt / 4;
 433
 434         /* shift the single digits some bytes (offset) and some bits (table)
 435          * to the left */
 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);
 441         }
 442         if (bitsize%4 > 0) {
 443                 unsigned const shl = val1[counter] << shift | carry;
 444                 buffer[counter + shift_cnt] = SC_RESULT(shl);
 445                 bitoffset = counter;
 446         } else {
 447                 bitoffset = counter - 1;
 448         }
 449
 450         /* fill with zeroes */
 451         for (counter = 0; counter < shift_cnt; counter++)
 452                 buffer[counter] = SC_0;
 453
 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;
 462                 }
 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;
 468                 }
 469         }
 470 }
 471
 472 /**
 473  * Implements a Shift Right, which can either preserve the sign bit
 474  * or not.
 475  *
 476  * @param bitsize   bitsize of the value to be shifted
 477  *
 478  * @todo Assertions seems to be wrong
 479  */
 480 static void do_shr(const char *val1, char *buffer, long shift_cnt, int bitsize, unsigned is_signed, int signed_shift)
 481 {
 482         const char *shrs;
 483         char sign;
 484         char msd;
 485
 486         int shift_mod, shift_nib;
 487
 488         int counter;
 489         int bitoffset = 0;
 490
 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"));
 494
 495         sign = signed_shift && do_bit(val1, bitsize - 1) ? SC_F : SC_0;
 496
 497         /* if shifting far enough the result is either 0 or -1 */
 498         if (shift_cnt >= bitsize) {
 499                 if (!sc_is_zero(val1)) {
 500                         carry_flag = 1;
 501                 }
 502                 memset(buffer, sign, calc_buffer_size);
 503                 return;
 504         }
 505
 506         shift_mod = shift_cnt &  3;
 507         shift_nib = shift_cnt >> 2;
 508
 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) {
 512                         carry_flag = 1;
 513                         break;
 514                 }
 515         }
 516         if ((_val(val1[counter]) & ((1<<shift_mod)-1)) != 0)
 517                 carry_flag = 1;
 518
 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];
 525         }
 526
 527         /* the last digit is special in regard of signed/unsigned shift */
 528         bitoffset = bitsize & 3;
 529         msd = sign;  /* most significant digit */
 530
 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];
 534         }
 535
 536         shrs = shrs_table[_val(msd)][shift_mod];
 537
 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];
 541         } else {
 542                 buffer[counter] = shrs[0];
 543         }
 544
 545         if (counter > 0)
 546                 buffer[counter - 1] |= shrs[1];
 547
 548         /* fill with SC_F or SC_0 depending on sign */
 549         for (counter++; counter < calc_buffer_size; counter++) {
 550                 buffer[counter] = sign;
 551         }
 552 }
 553
 554 /**
 555  * Implements a Rotate Left.
 556  * positive: low-order -> high order, negative other direction
 557  */
 558 static void do_rotl(const char *val1, char *buffer, long offset, int radius, unsigned is_signed)
 559 {
 560         char *temp1, *temp2;
 561         temp1 = (char*) alloca(calc_buffer_size);
 562         temp2 = (char*) alloca(calc_buffer_size);
 563
 564         offset = offset % radius;
 565
 566         /* rotation by multiples of the type length is identity */
 567         if (offset == 0) {
 568                 memmove(buffer, val1, calc_buffer_size);
 569                 return;
 570         }
 571
 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 */
 576 }
 577
 578 /*****************************************************************************
 579  * public functions, declared in strcalc.h
 580  *****************************************************************************/
 581 const void *sc_get_buffer(void)
 582 {
 583         return (void*)calc_buffer;
 584 }
 585
 586 int sc_get_buffer_length(void)
 587 {
 588         return calc_buffer_size;
 589 }
 590
 591 /**
 592  * Do sign extension if the mode is signed, otherwise to zero extension.
 593  */
 594 void sign_extend(void *buffer, ir_mode *mode)
 595 {
 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];
 600         int i;
 601
 602         if (mode_is_signed(mode)) {
 603                 if (calc_buffer[nibble] > max) {
 604                         /* sign bit is set, we need sign expansion */
 605
 606                         for (i = nibble + 1; i < calc_buffer_size; ++i)
 607                                 calc_buffer[i] = SC_F;
 608                         calc_buffer[nibble] |= sex_digit[bits & 3];
 609                 } else {
 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];
 614                 }
 615         } else {
 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];
 620         }
 621 }
 622
 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)
 626 {
 627         /* C standard guarantees that '0'-'9' is a range */
 628         assert('b'-'a' == 1
 629                 && 'c'-'a' == 2
 630                 && 'd'-'a' == 3
 631                 && 'e'-'a' == 4
 632                 && 'f'-'a' == 5);
 633         assert('B'-'A' == 1
 634                 && 'C'-'A' == 2
 635                 && 'D'-'A' == 3
 636                 && 'E'-'A' == 4
 637                 && 'F'-'A' == 5);
 638 }
 639
 640 int sc_val_from_str(char sign, unsigned base, const char *str,
 641                     size_t len, void *buffer)
 642 {
 643         char *sc_base, *val;
 644
 645         assert(sign == -1 || sign == 1);
 646         assert(str != NULL);
 647         assert(len > 0);
 648         check_ascii();
 649
 650         assert(base > 1 && base <= 16);
 651         sc_base = (char*) alloca(calc_buffer_size);
 652         sc_val_from_ulong(base, sc_base);
 653
 654         val = (char*) alloca(calc_buffer_size);
 655         if (buffer == NULL)
 656                 buffer = calc_buffer;
 657
 658         CLEAR_BUFFER(buffer);
 659         CLEAR_BUFFER(val);
 660
 661         /* BEGIN string evaluation, from left to right */
 662         while (len > 0) {
 663                 char c = *str;
 664                 unsigned v;
 665                 if (c >= '0' && c <= '9')
 666                         v = c - '0';
 667                 else if (c >= 'A' && c <= 'F')
 668                         v = c - 'A' + 10;
 669                 else if (c >= 'a' && c <= 'f')
 670                         v = c - 'a' + 10;
 671                 else
 672                         return 0;
 673
 674                 if (v >= base)
 675                         return 0;
 676                 val[0] = v;
 677
 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);
 684
 685                 /* get ready for the next letter */
 686                 str++;
 687                 len--;
 688         }
 689
 690         if (sign < 0)
 691                 do_negate((const char*) buffer, (char*) buffer);
 692
 693         return 1;
 694 }
 695
 696 void sc_val_from_long(long value, void *buffer)
 697 {
 698         char *pos;
 699         char sign, is_minlong;
 700
 701         if (buffer == NULL) buffer = calc_buffer;
 702         pos = (char*) buffer;
 703
 704         sign = (value < 0);
 705         is_minlong = value == LONG_MIN;
 706
 707         /* use absolute value, special treatment of MIN_LONG to avoid overflow */
 708         if (sign) {
 709                 if (is_minlong)
 710                         value = -(value+1);
 711                 else
 712                         value = -value;
 713         }
 714
 715         CLEAR_BUFFER(buffer);
 716
 717         while ((value != 0) && (pos < (char*)buffer + calc_buffer_size)) {
 718                 *pos++ = _digit(value & 0xf);
 719                 value >>= 4;
 720         }
 721
 722         if (sign) {
 723                 if (is_minlong)
 724                         do_inc((const char*) buffer, (char*) buffer);
 725
 726                 do_negate((const char*) buffer, (char*) buffer);
 727         }
 728 }
 729
 730 void sc_val_from_ulong(unsigned long value, void *buffer)
 731 {
 732         unsigned char *pos;
 733
 734         if (buffer == NULL) buffer = calc_buffer;
 735         pos = (unsigned char*) buffer;
 736
 737         while (pos < (unsigned char *)buffer + calc_buffer_size) {
 738                 *pos++ = (unsigned char)_digit(value & 0xf);
 739                 value >>= 4;
 740         }
 741 }
 742
 743 long sc_val_to_long(const void *val)
 744 {
 745         int i;
 746         long l = 0;
 747
 748         for (i = calc_buffer_size - 1; i >= 0; i--) {
 749                 l = (l << 4) + _val(((char *)val)[i]);
 750         }
 751         return l;
 752 }
 753
 754 void sc_min_from_bits(unsigned int num_bits, unsigned int sign, void *buffer)
 755 {
 756         char *pos;
 757         int i, bits;
 758
 759         if (buffer == NULL) buffer = calc_buffer;
 760         CLEAR_BUFFER(buffer);
 761
 762         if (!sign) return;  /* unsigned means minimum is 0(zero) */
 763
 764         pos = (char*) buffer;
 765
 766         bits = num_bits - 1;
 767         for (i = 0; i < bits/4; i++)
 768                 *pos++ = SC_0;
 769
 770         *pos++ = min_digit[bits%4];
 771
 772         for (i++; i <= calc_buffer_size - 1; i++)
 773                 *pos++ = SC_F;
 774 }
 775
 776 void sc_max_from_bits(unsigned int num_bits, unsigned int sign, void *buffer)
 777 {
 778         char* pos;
 779         int i, bits;
 780
 781         if (buffer == NULL) buffer = calc_buffer;
 782         CLEAR_BUFFER(buffer);
 783         pos = (char*) buffer;
 784
 785         bits = num_bits - sign;
 786         for (i = 0; i < bits/4; i++)
 787                 *pos++ = SC_F;
 788
 789         *pos++ = max_digit[bits%4];
 790
 791         for (i++; i <= calc_buffer_size - 1; i++)
 792                 *pos++ = SC_0;
 793 }
 794
 795 void sc_truncate(unsigned int num_bits, void *buffer)
 796 {
 797         char *cbuffer = (char*) buffer;
 798         char *pos = cbuffer + (num_bits / 4);
 799         char *end = cbuffer + calc_buffer_size;
 800
 801         assert(pos < end);
 802
 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;
 808         }
 809
 810         for ( ; pos < end; ++pos)
 811                 *pos = SC_0;
 812 }
 813
 814 int sc_comp(const void* value1, const void* value2)
 815 {
 816         int counter = calc_buffer_size - 1;
 817         const char *val1 = (const char *)value1;
 818         const char *val2 = (const char *)value2;
 819
 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);
 824
 825         /* loop until two digits differ, the values are equal if there
 826          * are no such two digits */
 827         while (val1[counter] == val2[counter]) {
 828                 counter--;
 829                 if (counter < 0) return 0;
 830         }
 831
 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);
 836 }
 837
 838 int sc_get_highest_set_bit(const void *value)
 839 {
 840         const char *val = (const char*)value;
 841         int high, counter;
 842
 843         high = calc_buffer_size * 4 - 1;
 844
 845         for (counter = calc_buffer_size-1; counter >= 0; counter--) {
 846                 if (val[counter] == SC_0)
 847                         high -= 4;
 848                 else {
 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;
 853                 }
 854         }
 855         return high;
 856 }
 857
 858 int sc_get_lowest_set_bit(const void *value)
 859 {
 860         const char *val = (const char*)value;
 861         int low, counter;
 862
 863         low = 0;
 864         for (counter = 0; counter < calc_buffer_size; counter++) {
 865                 switch (val[counter]) {
 866                 case SC_1:
 867                 case SC_3:
 868                 case SC_5:
 869                 case SC_7:
 870                 case SC_9:
 871                 case SC_B:
 872                 case SC_D:
 873                 case SC_F:
 874                         return low;
 875                 case SC_2:
 876                 case SC_6:
 877                 case SC_A:
 878                 case SC_E:
 879                         return low + 1;
 880                 case SC_4:
 881                 case SC_C:
 882                         return low + 2;
 883                 case SC_8:
 884                         return low + 3;
 885                 default:
 886                         low += 4;
 887                 }
 888         }
 889         return -1;
 890 }
 891
 892 int sc_get_bit_at(const void *value, unsigned pos)
 893 {
 894         const char *val = (const char*) value;
 895         unsigned nibble = pos >> 2;
 896
 897         return (val[nibble] & SHIFT(pos & 3)) != SC_0;
 898 }
 899
 900 void sc_set_bit_at(void *value, unsigned pos)
 901 {
 902         char *val = (char*) value;
 903         unsigned nibble = pos >> 2;
 904
 905         val[nibble] |= SHIFT(pos & 3);
 906 }
 907
 908 int sc_is_zero(const void *value)
 909 {
 910         const char* val = (const char *)value;
 911         int counter;
 912
 913         for (counter = 0; counter < calc_buffer_size; ++counter) {
 914                 if (val[counter] != SC_0)
 915                         return 0;
 916         }
 917         return 1;
 918 }
 919
 920 int sc_is_negative(const void *value)
 921 {
 922         return do_sign((const char*) value) == -1;
 923 }
 924
 925 int sc_had_carry(void)
 926 {
 927         return carry_flag;
 928 }
 929
 930 unsigned char sc_sub_bits(const void *value, int len, unsigned byte_ofs)
 931 {
 932         const char *val = (const char *)value;
 933         int nibble_ofs  = 2 * byte_ofs;
 934         unsigned char res;
 935
 936         /* the current scheme uses one byte to store a nibble */
 937         if (4 * nibble_ofs >= len)
 938                 return 0;
 939
 940         res = _val(val[nibble_ofs]);
 941         if (len > 4 * (nibble_ofs + 1))
 942                 res |= _val(val[nibble_ofs + 1]) << 4;
 943
 944         /* kick bits outsize */
 945         if (len - 8 * byte_ofs < 8) {
 946                 res &= (1 << (len - 8 * byte_ofs)) - 1;
 947         }
 948         return res;
 949 }
 950
 951 /*
 952  * convert to a string
 953  * FIXME: Doesn't check buffer bounds
 954  */
 955 const char *sc_print(const void *value, unsigned bits, enum base_t base, int signed_mode)
 956 {
 957         static const char big_digits[]   = "0123456789ABCDEF";
 958         static const char small_digits[] = "0123456789abcdef";
 959
 960         char *base_val, *div1_res, *div2_res, *rem_res;
 961         int counter, nibbles, i, sign, mask;
 962         char x;
 963
 964         const char *val = (const char *)value;
 965         const char *p;
 966         char *m, *n, *t;
 967         char *pos;
 968         const char *digits = small_digits;
 969
 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);
 974
 975         pos = output_buffer + bit_pattern_size;
 976         *(--pos) = '\0';
 977
 978         /* special case */
 979         if (bits == 0) {
 980                 bits = bit_pattern_size;
 981         }
 982         nibbles = bits >> 2;
 983         switch (base) {
 984
 985         case SC_HEX:
 986                 digits = big_digits;
 987         case SC_hex:
 988                 for (counter = 0; counter < nibbles; ++counter) {
 989                         *(--pos) = digits[_val(val[counter])];
 990                 }
 991
 992                 /* last nibble must be masked */
 993                 if (bits & 3) {
 994                         mask = zex_digit[(bits & 3) - 1];
 995                         x    = val[counter++] & mask;
 996                         *(--pos) = digits[_val(x)];
 997                 }
 998
 999                 /* now kill zeros */
1000                 for (; counter > 1; --counter, ++pos) {
1001                         if (pos[0] != '0')
1002                                 break;
1003                 }
1004                 break;
1005
1006         case SC_BIN:
1007                 for (counter = 0; counter < nibbles; ++counter) {
1008                         pos -= 4;
1009                         p = binary_table[_val(val[counter])];
1010                         pos[0] = p[0];
1011                         pos[1] = p[1];
1012                         pos[2] = p[2];
1013                         pos[3] = p[3];
1014                 }
1015
1016                 /* last nibble must be masked */
1017                 if (bits & 3) {
1018                         mask = zex_digit[(bits & 3) - 1];
1019                         x    = val[counter++] & mask;
1020
1021                         pos -= 4;
1022                         p = binary_table[_val(x)];
1023                         pos[0] = p[0];
1024                         pos[1] = p[1];
1025                         pos[2] = p[2];
1026                         pos[3] = p[3];
1027                 }
1028
1029                 /* now kill zeros */
1030                 for (counter <<= 2; counter > 1; --counter, ++pos)
1031                         if (pos[0] != '0')
1032                                 break;
1033                         break;
1034
1035         case SC_DEC:
1036         case SC_OCT:
1037                 memset(base_val, SC_0, calc_buffer_size);
1038                 base_val[0] = base == SC_DEC ? SC_A : SC_8;
1039
1040                 p    = val;
1041                 sign = 0;
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);
1046                                 sign = 1;
1047                                 p = div2_res;
1048                         }
1049                 }
1050
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];
1055
1056                 /* last nibble must be masked */
1057                 if (bits & 3) {
1058                         mask = zex_digit[(bits & 3) - 1];
1059                         div1_res[counter] = p[counter] & mask;
1060                         ++counter;
1061                 }
1062
1063                 m = div1_res;
1064                 n = div2_res;
1065                 for (;;) {
1066                         do_divmod(m, base_val, n, rem_res);
1067                         t = m;
1068                         m = n;
1069                         n = t;
1070                         *(--pos) = digits[_val(rem_res[0])];
1071
1072                         x = 0;
1073                         for (i = 0; i < calc_buffer_size; ++i)
1074                                 x |= _val(m[i]);
1075
1076                         if (x == 0)
1077                                 break;
1078                 }
1079                 if (sign)
1080                         *(--pos) = '-';
1081                 break;
1082
1083         default:
1084                 panic("Unsupported base %d", base);
1085         }
1086         return pos;
1087 }
1088
1089 void init_strcalc(int precision)
1090 {
1091         if (calc_buffer == NULL) {
1092                 if (precision <= 0) precision = SC_DEFAULT_PRECISION;
1093
1094                 /* round up to multiple of 4 */
1095                 precision = (precision + 3) & ~3;
1096
1097                 bit_pattern_size = (precision);
1098                 calc_buffer_size = (precision / 2);
1099                 max_value_size   = (precision / 4);
1100
1101                 calc_buffer   = XMALLOCN(char, calc_buffer_size + 1);
1102                 output_buffer = XMALLOCN(char, bit_pattern_size + 1);
1103         }
1104 }
1105
1106
1107 void finish_strcalc(void)
1108 {
1109         free(calc_buffer);   calc_buffer   = NULL;
1110         free(output_buffer); output_buffer = NULL;
1111 }
1112
1113 int sc_get_precision(void)
1114 {
1115         return bit_pattern_size;
1116 }
1117
1118
1119 void sc_add(const void *value1, const void *value2, void *buffer)
1120 {
1121         CLEAR_BUFFER(calc_buffer);
1122         carry_flag = 0;
1123
1124         do_add((const char*) value1, (const char*) value2, (char*) calc_buffer);
1125
1126         if ((buffer != NULL) && (buffer != calc_buffer)) {
1127                 memcpy(buffer, calc_buffer, calc_buffer_size);
1128         }
1129 }
1130
1131 void sc_sub(const void *value1, const void *value2, void *buffer)
1132 {
1133         CLEAR_BUFFER(calc_buffer);
1134         carry_flag = 0;
1135
1136         do_sub((const char*) value1, (const char*) value2, calc_buffer);
1137
1138         if ((buffer != NULL) && (buffer != calc_buffer)) {
1139                 memcpy(buffer, calc_buffer, calc_buffer_size);
1140         }
1141 }
1142
1143 void sc_neg(const void *value1, void *buffer)
1144 {
1145         carry_flag = 0;
1146
1147         do_negate((const char*) value1, calc_buffer);
1148
1149         if ((buffer != NULL) && (buffer != calc_buffer)) {
1150                 memcpy(buffer, calc_buffer, calc_buffer_size);
1151         }
1152 }
1153
1154 void sc_and(const void *value1, const void *value2, void *buffer)
1155 {
1156         CLEAR_BUFFER(calc_buffer);
1157         carry_flag = 0;
1158
1159         do_bitand((const char*) value1, (const char*) value2, calc_buffer);
1160
1161         if ((buffer != NULL) && (buffer != calc_buffer)) {
1162                 memcpy(buffer, calc_buffer, calc_buffer_size);
1163         }
1164 }
1165
1166 void sc_andnot(const void *value1, const void *value2, void *buffer)
1167 {
1168         CLEAR_BUFFER(calc_buffer);
1169         carry_flag = 0;
1170
1171         do_bitandnot((const char*) value1, (const char*) value2, calc_buffer);
1172
1173         if (buffer != NULL && buffer != calc_buffer) {
1174                 memcpy(buffer, calc_buffer, calc_buffer_size);
1175         }
1176 }
1177
1178 void sc_or(const void *value1, const void *value2, void *buffer)
1179 {
1180         CLEAR_BUFFER(calc_buffer);
1181         carry_flag = 0;
1182
1183         do_bitor((const char*) value1, (const char*) value2, calc_buffer);
1184
1185         if ((buffer != NULL) && (buffer != calc_buffer)) {
1186                 memcpy(buffer, calc_buffer, calc_buffer_size);
1187         }
1188 }
1189
1190 void sc_xor(const void *value1, const void *value2, void *buffer)
1191 {
1192         CLEAR_BUFFER(calc_buffer);
1193         carry_flag = 0;
1194
1195         do_bitxor((const char*) value1, (const char*) value2, calc_buffer);
1196
1197         if ((buffer != NULL) && (buffer != calc_buffer)) {
1198                 memcpy(buffer, calc_buffer, calc_buffer_size);
1199         }
1200 }
1201
1202 void sc_not(const void *value1, void *buffer)
1203 {
1204         CLEAR_BUFFER(calc_buffer);
1205         carry_flag = 0;
1206
1207         do_bitnot((const char*) value1, calc_buffer);
1208
1209         if ((buffer != NULL) && (buffer != calc_buffer)) {
1210                 memcpy(buffer, calc_buffer, calc_buffer_size);
1211         }
1212 }
1213
1214 void sc_mul(const void *value1, const void *value2, void *buffer)
1215 {
1216         CLEAR_BUFFER(calc_buffer);
1217         carry_flag = 0;
1218
1219         do_mul((const char*) value1, (const char*) value2, calc_buffer);
1220
1221         if ((buffer != NULL) && (buffer != calc_buffer)) {
1222                 memcpy(buffer, calc_buffer, calc_buffer_size);
1223         }
1224 }
1225
1226 void sc_div(const void *value1, const void *value2, void *buffer)
1227 {
1228         /* temp buffer holding unused result of divmod */
1229         char *unused_res = (char*) alloca(calc_buffer_size);
1230
1231         CLEAR_BUFFER(calc_buffer);
1232         carry_flag = 0;
1233
1234         do_divmod((const char*) value1, (const char*) value2, calc_buffer, unused_res);
1235
1236         if ((buffer != NULL) && (buffer != calc_buffer)) {
1237                 memcpy(buffer, calc_buffer, calc_buffer_size);
1238         }
1239 }
1240
1241 void sc_mod(const void *value1, const void *value2, void *buffer)
1242 {
1243         /* temp buffer holding unused result of divmod */
1244         char *unused_res = (char*) alloca(calc_buffer_size);
1245
1246         CLEAR_BUFFER(calc_buffer);
1247         carry_flag = 0;
1248
1249         do_divmod((const char*) value1, (const char*) value2, unused_res, calc_buffer);
1250
1251         if ((buffer != NULL) && (buffer != calc_buffer)) {
1252                 memcpy(buffer, calc_buffer, calc_buffer_size);
1253         }
1254 }
1255
1256 void sc_divmod(const void *value1, const void *value2, void *div_buffer, void *mod_buffer)
1257 {
1258         CLEAR_BUFFER(calc_buffer);
1259         carry_flag = 0;
1260
1261         do_divmod((const char*) value1, (const char*) value2, (char*) div_buffer, (char*) mod_buffer);
1262 }
1263
1264
1265 void sc_shlI(const void *val1, long shift_cnt, int bitsize, int sign, void *buffer)
1266 {
1267         carry_flag = 0;
1268
1269         do_shl((const char*) val1, calc_buffer, shift_cnt, bitsize, sign);
1270
1271         if ((buffer != NULL) && (buffer != calc_buffer)) {
1272                 memmove(buffer, calc_buffer, calc_buffer_size);
1273         }
1274 }
1275
1276 void sc_shl(const void *val1, const void *val2, int bitsize, int sign, void *buffer)
1277 {
1278         long offset = sc_val_to_long(val2);
1279
1280         sc_shlI(val1, offset, bitsize, sign, buffer);
1281 }
1282
1283 void sc_shrI(const void *val1, long shift_cnt, int bitsize, int sign, void *buffer)
1284 {
1285         carry_flag = 0;
1286
1287         do_shr((const char*) val1, calc_buffer, shift_cnt, bitsize, sign, 0);
1288
1289         if ((buffer != NULL) && (buffer != calc_buffer)) {
1290                 memmove(buffer, calc_buffer, calc_buffer_size);
1291         }
1292 }
1293
1294 void sc_shr(const void *val1, const void *val2, int bitsize, int sign, void *buffer)
1295 {
1296         long shift_cnt = sc_val_to_long(val2);
1297
1298         sc_shrI(val1, shift_cnt, bitsize, sign, buffer);
1299 }
1300
1301 void sc_shrsI(const void *val1, long shift_cnt, int bitsize, int sign, void *buffer)
1302 {
1303         carry_flag = 0;
1304
1305         do_shr((const char*) val1, calc_buffer, shift_cnt, bitsize, sign, 1);
1306
1307         if ((buffer != NULL) && (buffer != calc_buffer)) {
1308                 memmove(buffer, calc_buffer, calc_buffer_size);
1309         }
1310 }
1311
1312 void sc_shrs(const void *val1, const void *val2, int bitsize, int sign, void *buffer)
1313 {
1314         long offset = sc_val_to_long(val2);
1315
1316         carry_flag = 0;
1317
1318         do_shr((const char*) val1, calc_buffer, offset, bitsize, sign, 1);
1319
1320         if ((buffer != NULL) && (buffer != calc_buffer)) {
1321                 memmove(buffer, calc_buffer, calc_buffer_size);
1322         }
1323 }
1324
1325 void sc_rotl(const void *val1, const void *val2, int bitsize, int sign, void *buffer)
1326 {
1327         long offset = sc_val_to_long(val2);
1328
1329         carry_flag = 0;
1330
1331         do_rotl((const char*) val1, calc_buffer, offset, bitsize, sign);
1332
1333         if ((buffer != NULL) && (buffer != calc_buffer)) {
1334                 memmove(buffer, calc_buffer, calc_buffer_size);
1335         }
1336 }
1337
1338 void sc_zero(void *buffer)
1339 {
1340         if (buffer == NULL)
1341                 buffer = calc_buffer;
1342         CLEAR_BUFFER(buffer);
1343         carry_flag = 0;
1344 }