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

   1 /*
   2  * Copyright (C) 1995-2008 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  * @version  $Id$
  26  */
  27 #include "config.h"
  28
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <assert.h>
  32 #include <stdio.h>
  33 #include <limits.h>
  34
  35 #include "strcalc.h"
  36 #include "xmalloc.h"
  37 #include "error.h"
  38
  39 /*
  40  * local definitions and macros
  41  */
  42 #define CLEAR_BUFFER(b) assert(b); memset(b, SC_0, calc_buffer_size)
  43 #define _val(a) ((a)-SC_0)
  44 #define _digit(a) ((a)+SC_0)
  45 #define _bitisset(digit, pos) ((digit & shift_table[pos]) != SC_0)
  46
  47 #define fail_char(a, b, c, d) _fail_char((a), (b), (c), (d), __FILE__,  __LINE__)
  48
  49 /* shortcut output for debugging */
  50 #  define sc_print_hex(a) sc_print((a), 0, SC_HEX, 0)
  51 #  define sc_print_dec(a) sc_print((a), 0, SC_DEC, 1)
  52 #  define sc_print_oct(a) sc_print((a), 0, SC_OCT, 0)
  53 #  define sc_print_bin(a) sc_print((a), 0, SC_BIN, 0)
  54
  55 #ifdef STRCALC_DEBUG_PRINTCOMP
  56 #  define DEBUGPRINTF_COMPUTATION(x) printf x
  57 #else
  58 #  define DEBUGPRINTF_COMPUTATION(x) ((void)0)
  59 #endif
  60 #ifdef STRCALC_DEBUG
  61 #  define DEBUGPRINTF(x) printf x
  62 #else
  63 #  define DEBUGPRINTF(x) ((void)0)
  64 #endif
  65
  66
  67 /*
  68  * private variables
  69  */
  70 static char *calc_buffer = NULL;    /* buffer holding all results */
  71 static char *output_buffer = NULL;  /* buffer for output */
  72 static int bit_pattern_size;        /* maximum number of bits */
  73 static int calc_buffer_size;        /* size of internally stored values */
  74 static int max_value_size;          /* maximum size of values */
  75
  76 static int carry_flag;              /**< some computation set the carry_flag:
  77                                          - right shift if bits were lost due to shifting
  78                                          - division if there was a remainder
  79                                          However, the meaning of carry is machine dependent
  80                                          and often defined in other ways! */
  81
  82 static const char sex_digit[4] = { SC_E, SC_C, SC_8, SC_0 };
  83 static const char zex_digit[4] = { SC_1, SC_3, SC_7, SC_F };
  84 static const char max_digit[4] = { SC_0, SC_1, SC_3, SC_7 };
  85 static const char min_digit[4] = { SC_F, SC_E, SC_C, SC_8 };
  86
  87 static const char shift_table[4] = { SC_1, SC_2, SC_4, SC_8 };
  88
  89 static char const add_table[16][16][2] = {
  90                        { {SC_0, SC_0}, {SC_1, SC_0}, {SC_2, SC_0}, {SC_3, SC_0},
  91                          {SC_4, SC_0}, {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0},
  92                          {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0},
  93                          {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0} },
  94
  95                        { {SC_1, SC_0}, {SC_2, SC_0}, {SC_3, SC_0}, {SC_4, SC_0},
  96                          {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0}, {SC_8, SC_0},
  97                          {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0},
  98                          {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1} },
  99
 100                        { {SC_2, SC_0}, {SC_3, SC_0}, {SC_4, SC_0}, {SC_5, SC_0},
 101                          {SC_6, SC_0}, {SC_7, SC_0}, {SC_8, SC_0}, {SC_9, SC_0},
 102                          {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0},
 103                          {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1} },
 104
 105                        { {SC_3, SC_0}, {SC_4, SC_0}, {SC_5, SC_0}, {SC_6, SC_0},
 106                          {SC_7, SC_0}, {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0},
 107                          {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0},
 108                          {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1} },
 109
 110                        { {SC_4, SC_0}, {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0},
 111                          {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0},
 112                          {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0},
 113                          {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1} },
 114
 115                        { {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0}, {SC_8, SC_0},
 116                          {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0},
 117                          {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1},
 118                          {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1} },
 119
 120                        { {SC_6, SC_0}, {SC_7, SC_0}, {SC_8, SC_0}, {SC_9, SC_0},
 121                          {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0},
 122                          {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1},
 123                          {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1} },
 124
 125                        { {SC_7, SC_0}, {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0},
 126                          {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0},
 127                          {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1},
 128                          {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1} },
 129
 130                        { {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0},
 131                          {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0},
 132                          {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1},
 133                          {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1}, {SC_7, SC_1} },
 134
 135                        { {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0},
 136                          {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1},
 137                          {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1},
 138                          {SC_5, SC_1}, {SC_6, SC_1}, {SC_7, SC_1}, {SC_8, SC_1} },
 139
 140                        { {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0},
 141                          {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1},
 142                          {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1},
 143                          {SC_6, SC_1}, {SC_7, SC_1}, {SC_8, SC_1}, {SC_9, SC_1} },
 144
 145                        { {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0},
 146                          {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1},
 147                          {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1},
 148                          {SC_7, SC_1}, {SC_8, SC_1}, {SC_9, SC_1}, {SC_A, SC_1} },
 149
 150                        { {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0},
 151                          {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1},
 152                          {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1}, {SC_7, SC_1},
 153                          {SC_8, SC_1}, {SC_9, SC_1}, {SC_A, SC_1}, {SC_B, SC_1} },
 154
 155                        { {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1},
 156                          {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1},
 157                          {SC_5, SC_1}, {SC_6, SC_1}, {SC_7, SC_1}, {SC_8, SC_1},
 158                          {SC_9, SC_1}, {SC_A, SC_1}, {SC_B, SC_1}, {SC_C, SC_1} },
 159
 160                        { {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1},
 161                          {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1},
 162                          {SC_6, SC_1}, {SC_7, SC_1}, {SC_8, SC_1}, {SC_9, SC_1},
 163                          {SC_A, SC_1}, {SC_B, SC_1}, {SC_C, SC_1}, {SC_D, SC_1} },
 164
 165                        { {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1},
 166                          {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1},
 167                          {SC_7, SC_1}, {SC_8, SC_1}, {SC_9, SC_1}, {SC_A, SC_1},
 168                          {SC_B, SC_1}, {SC_C, SC_1}, {SC_D, SC_1}, {SC_E, SC_1} }
 169                              };
 170
 171 static char const mul_table[16][16][2] = {
 172                        { {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0},
 173                          {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0},
 174                          {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0},
 175                          {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0} },
 176
 177                        { {SC_0, SC_0}, {SC_1, SC_0}, {SC_2, SC_0}, {SC_3, SC_0},
 178                          {SC_4, SC_0}, {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0},
 179                          {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0},
 180                          {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0} },
 181
 182                        { {SC_0, SC_0}, {SC_2, SC_0}, {SC_4, SC_0}, {SC_6, SC_0},
 183                          {SC_8, SC_0}, {SC_A, SC_0}, {SC_C, SC_0}, {SC_E, SC_0},
 184                          {SC_0, SC_1}, {SC_2, SC_1}, {SC_4, SC_1}, {SC_6, SC_1},
 185                          {SC_8, SC_1}, {SC_A, SC_1}, {SC_C, SC_1}, {SC_E, SC_1} },
 186
 187                        { {SC_0, SC_0}, {SC_3, SC_0}, {SC_6, SC_0}, {SC_9, SC_0},
 188                          {SC_C, SC_0}, {SC_F, SC_0}, {SC_2, SC_1}, {SC_5, SC_1},
 189                          {SC_8, SC_1}, {SC_B, SC_1}, {SC_E, SC_1}, {SC_1, SC_2},
 190                          {SC_4, SC_2}, {SC_7, SC_2}, {SC_A, SC_2}, {SC_D, SC_2} },
 191
 192                        { {SC_0, SC_0}, {SC_4, SC_0}, {SC_8, SC_0}, {SC_C, SC_0},
 193                          {SC_0, SC_1}, {SC_4, SC_1}, {SC_8, SC_1}, {SC_C, SC_1},
 194                          {SC_0, SC_2}, {SC_4, SC_2}, {SC_8, SC_2}, {SC_C, SC_2},
 195                          {SC_0, SC_3}, {SC_4, SC_3}, {SC_8, SC_3}, {SC_C, SC_3} },
 196
 197                        { {SC_0, SC_0}, {SC_5, SC_0}, {SC_A, SC_0}, {SC_F, SC_0},
 198                          {SC_4, SC_1}, {SC_9, SC_1}, {SC_E, SC_1}, {SC_3, SC_2},
 199                          {SC_8, SC_2}, {SC_D, SC_2}, {SC_2, SC_3}, {SC_7, SC_3},
 200                          {SC_C, SC_3}, {SC_1, SC_4}, {SC_6, SC_4}, {SC_B, SC_4} },
 201
 202                        { {SC_0, SC_0}, {SC_6, SC_0}, {SC_C, SC_0}, {SC_2, SC_1},
 203                          {SC_8, SC_1}, {SC_E, SC_1}, {SC_4, SC_2}, {SC_A, SC_2},
 204                          {SC_0, SC_3}, {SC_6, SC_3}, {SC_C, SC_3}, {SC_2, SC_4},
 205                          {SC_8, SC_4}, {SC_E, SC_4}, {SC_4, SC_5}, {SC_A, SC_5} },
 206
 207                        { {SC_0, SC_0}, {SC_7, SC_0}, {SC_E, SC_0}, {SC_5, SC_1},
 208                          {SC_C, SC_1}, {SC_3, SC_2}, {SC_A, SC_2}, {SC_1, SC_3},
 209                          {SC_8, SC_3}, {SC_F, SC_3}, {SC_6, SC_4}, {SC_D, SC_4},
 210                          {SC_4, SC_5}, {SC_B, SC_5}, {SC_2, SC_6}, {SC_9, SC_6} },
 211
 212                        { {SC_0, SC_0}, {SC_8, SC_0}, {SC_0, SC_1}, {SC_8, SC_1},
 213                          {SC_0, SC_2}, {SC_8, SC_2}, {SC_0, SC_3}, {SC_8, SC_3},
 214                          {SC_0, SC_4}, {SC_8, SC_4}, {SC_0, SC_5}, {SC_8, SC_5},
 215                          {SC_0, SC_6}, {SC_8, SC_6}, {SC_0, SC_7}, {SC_8, SC_7} },
 216
 217                        { {SC_0, SC_0}, {SC_9, SC_0}, {SC_2, SC_1}, {SC_B, SC_1},
 218                          {SC_4, SC_2}, {SC_D, SC_2}, {SC_6, SC_3}, {SC_F, SC_3},
 219                          {SC_8, SC_4}, {SC_1, SC_5}, {SC_A, SC_5}, {SC_3, SC_6},
 220                          {SC_C, SC_6}, {SC_5, SC_7}, {SC_E, SC_7}, {SC_7, SC_8} },
 221
 222                        { {SC_0, SC_0}, {SC_A, SC_0}, {SC_4, SC_1}, {SC_E, SC_1},
 223                          {SC_8, SC_2}, {SC_2, SC_3}, {SC_C, SC_3}, {SC_6, SC_4},
 224                          {SC_0, SC_5}, {SC_A, SC_5}, {SC_4, SC_6}, {SC_E, SC_6},
 225                          {SC_8, SC_7}, {SC_2, SC_8}, {SC_C, SC_8}, {SC_6, SC_9} },
 226
 227                        { {SC_0, SC_0}, {SC_B, SC_0}, {SC_6, SC_1}, {SC_1, SC_2},
 228                          {SC_C, SC_2}, {SC_7, SC_3}, {SC_2, SC_4}, {SC_D, SC_4},
 229                          {SC_8, SC_5}, {SC_3, SC_6}, {SC_E, SC_6}, {SC_9, SC_7},
 230                          {SC_4, SC_8}, {SC_F, SC_8}, {SC_A, SC_9}, {SC_5, SC_A} },
 231
 232                        { {SC_0, SC_0}, {SC_C, SC_0}, {SC_8, SC_1}, {SC_4, SC_2},
 233                          {SC_0, SC_3}, {SC_C, SC_3}, {SC_8, SC_4}, {SC_4, SC_5},
 234                          {SC_0, SC_6}, {SC_C, SC_6}, {SC_8, SC_7}, {SC_4, SC_8},
 235                          {SC_0, SC_9}, {SC_C, SC_9}, {SC_8, SC_A}, {SC_4, SC_B} },
 236
 237                        { {SC_0, SC_0}, {SC_D, SC_0}, {SC_A, SC_1}, {SC_7, SC_2},
 238                          {SC_4, SC_3}, {SC_1, SC_4}, {SC_E, SC_4}, {SC_B, SC_5},
 239                          {SC_8, SC_6}, {SC_5, SC_7}, {SC_2, SC_8}, {SC_F, SC_8},
 240                          {SC_C, SC_9}, {SC_9, SC_A}, {SC_6, SC_B}, {SC_3, SC_C} },
 241
 242                        { {SC_0, SC_0}, {SC_E, SC_0}, {SC_C, SC_1}, {SC_A, SC_2},
 243                          {SC_8, SC_3}, {SC_6, SC_4}, {SC_4, SC_5}, {SC_2, SC_6},
 244                          {SC_0, SC_7}, {SC_E, SC_7}, {SC_C, SC_8}, {SC_A, SC_9},
 245                          {SC_8, SC_A}, {SC_6, SC_B}, {SC_4, SC_C}, {SC_2, SC_D} },
 246
 247                        { {SC_0, SC_0}, {SC_F, SC_0}, {SC_E, SC_1}, {SC_D, SC_2},
 248                          {SC_C, SC_3}, {SC_B, SC_4}, {SC_A, SC_5}, {SC_9, SC_6},
 249                          {SC_8, SC_7}, {SC_7, SC_8}, {SC_6, SC_9}, {SC_5, SC_A},
 250                          {SC_4, SC_B}, {SC_3, SC_C}, {SC_2, SC_D}, {SC_1, SC_E} }
 251                              };
 252
 253 static char const shrs_table[16][4][2] = {
 254                        { {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0} },
 255                        { {SC_1, SC_0}, {SC_0, SC_8}, {SC_0, SC_4}, {SC_0, SC_2} },
 256                        { {SC_2, SC_0}, {SC_1, SC_0}, {SC_0, SC_8}, {SC_0, SC_4} },
 257                        { {SC_3, SC_0}, {SC_1, SC_8}, {SC_0, SC_C}, {SC_0, SC_6} },
 258                        { {SC_4, SC_0}, {SC_2, SC_0}, {SC_1, SC_0}, {SC_0, SC_8} },
 259                        { {SC_5, SC_0}, {SC_2, SC_8}, {SC_1, SC_4}, {SC_0, SC_A} },
 260                        { {SC_6, SC_0}, {SC_3, SC_0}, {SC_1, SC_8}, {SC_0, SC_C} },
 261                        { {SC_7, SC_0}, {SC_3, SC_8}, {SC_1, SC_C}, {SC_0, SC_E} },
 262                        { {SC_8, SC_0}, {SC_4, SC_0}, {SC_2, SC_0}, {SC_1, SC_0} },
 263                        { {SC_9, SC_0}, {SC_4, SC_8}, {SC_2, SC_4}, {SC_1, SC_2} },
 264                        { {SC_A, SC_0}, {SC_5, SC_0}, {SC_2, SC_8}, {SC_1, SC_4} },
 265                        { {SC_B, SC_0}, {SC_5, SC_8}, {SC_2, SC_C}, {SC_1, SC_6} },
 266                        { {SC_C, SC_0}, {SC_6, SC_0}, {SC_3, SC_0}, {SC_1, SC_8} },
 267                        { {SC_D, SC_0}, {SC_6, SC_8}, {SC_3, SC_4}, {SC_1, SC_A} },
 268                        { {SC_E, SC_0}, {SC_7, SC_0}, {SC_3, SC_8}, {SC_1, SC_C} },
 269                        { {SC_F, SC_0}, {SC_7, SC_8}, {SC_3, SC_C}, {SC_1, SC_E} }
 270                                    };
 271
 272 /** converting a digit to a binary string */
 273 static const char *binary_table[16] = {
 274         "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
 275         "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"
 276 };
 277
 278 /*****************************************************************************
 279  * private functions
 280  *****************************************************************************/
 281 static void _fail_char(const char *str, size_t len, const char fchar, int pos,
 282                        const char *file, int line) {
 283         printf("ERROR:\n");
 284         printf("Unexpected character '%c' in %s:%d\n", fchar, file, line);
 285         while (len-- && *str) printf("%c", *str++); printf("\n");
 286         while (--pos) printf(" "); printf("^\n");
 287         exit(-1);
 288 }
 289
 290 /**
 291  * implements the bitwise NOT operation
 292  */
 293 static void do_bitnot(const char *val, char *buffer) {
 294         int counter;
 295
 296         for (counter = 0; counter<calc_buffer_size; counter++)
 297                 buffer[counter] = val[counter] ^ SC_F;
 298 }
 299
 300 /**
 301  * implements the bitwise OR operation
 302  */
 303 static void do_bitor(const char *val1, const char *val2, char *buffer) {
 304         int counter;
 305
 306         for (counter = 0; counter<calc_buffer_size; counter++)
 307                 buffer[counter] = val1[counter] | val2[counter];
 308 }
 309
 310 /**
 311  * implements the bitwise eXclusive OR operation
 312  */
 313 static void do_bitxor(const char *val1, const char *val2, char *buffer) {
 314         int counter;
 315
 316         for (counter = 0; counter<calc_buffer_size; counter++)
 317                 buffer[counter] = val1[counter] ^ val2[counter];
 318 }
 319
 320 /**
 321  * implements the bitwise AND operation
 322  */
 323 static void do_bitand(const char *val1, const char *val2, char *buffer) {
 324         int counter;
 325
 326         for (counter = 0; counter<calc_buffer_size; counter++)
 327                 buffer[counter] = val1[counter] & val2[counter];
 328 }
 329
 330 /**
 331  * returns the sign bit.
 332  *
 333  * @todo This implementation is wrong, as it returns the highest bit of the buffer
 334  *       NOT the highest bit depending on the real mode
 335  */
 336 static int do_sign(const char *val) {
 337         return (val[calc_buffer_size-1] <= SC_7) ? (1) : (-1);
 338 }
 339
 340 /**
 341  * returns non-zero if bit at position pos is set
 342  */
 343 static int do_bit(const char *val, int pos) {
 344         int bit    = pos & 3;
 345         int nibble = pos >> 2;
 346
 347         return _bitisset(val[nibble], bit);
 348 }
 349
 350 /**
 351  * Implements a fast ADD + 1
 352  */
 353 static void do_inc(const char *val, char *buffer) {
 354         int counter = 0;
 355
 356         while (counter++ < calc_buffer_size) {
 357                 if (*val == SC_F) {
 358                         *buffer++ = SC_0;
 359                         val++;
 360                 } else {
 361                         /* No carry here, *val != SC_F */
 362                         *buffer = add_table[_val(*val)][SC_1][0];
 363                         return;
 364                 }
 365         }
 366         /* here a carry could be lost, this is intended because this should
 367          * happen only when a value changes sign. */
 368 }
 369
 370 /**
 371  * Implements a unary MINUS
 372  */
 373 static void do_negate(const char *val, char *buffer) {
 374         do_bitnot(val, buffer);
 375         do_inc(buffer, buffer);
 376 }
 377
 378 /**
 379  * Implements a binary ADD
 380  *
 381  * @todo The implementation of carry is wrong, as it is the
 382  *       calc_buffer_size carry, not the mode depending
 383  */
 384 static void do_add(const char *val1, const char *val2, char *buffer) {
 385         int counter;
 386         const char *add1, *add2;
 387         char carry = SC_0;
 388
 389         for (counter = 0; counter < calc_buffer_size; counter++)   {
 390                 add1 = add_table[_val(val1[counter])][_val(val2[counter])];
 391                 add2 = add_table[_val(add1[0])][_val(carry)];
 392                 /* carry might be zero */
 393                 buffer[counter] = add2[0];
 394                 carry = add_table[_val(add1[1])][_val(add2[1])][0];
 395         }
 396         carry_flag = carry != SC_0;
 397 }
 398
 399 /**
 400  * Implements a binary SUB
 401  */
 402 static void do_sub(const char *val1, const char *val2, char *buffer) {
 403         char *temp_buffer = alloca(calc_buffer_size); /* intermediate buffer to hold -val2 */
 404
 405         do_negate(val2, temp_buffer);
 406         do_add(val1, temp_buffer, buffer);
 407 }
 408
 409 /**
 410  * Implements a binary MUL
 411  */
 412 static void do_mul(const char *val1, const char *val2, char *buffer) {
 413         char *temp_buffer; /* result buffer */
 414         char *neg_val1;    /* abs of val1 */
 415         char *neg_val2;    /* abs of val2 */
 416
 417         const char *mul, *add1, *add2;      /* intermediate result containers */
 418         char carry = SC_0;                  /* container for carries */
 419         char sign = 0;                      /* marks result sign */
 420         int c_inner, c_outer;               /* loop counters */
 421
 422         temp_buffer = alloca(calc_buffer_size);
 423         neg_val1 = alloca(calc_buffer_size);
 424         neg_val2 = alloca(calc_buffer_size);
 425
 426         /* init result buffer to zeros */
 427         memset(temp_buffer, SC_0, calc_buffer_size);
 428
 429         /* the multiplication works only for positive values, for negative values *
 430          * it is necessary to negate them and adjust the result accordingly       */
 431         if (do_sign(val1) == -1) {
 432                 do_negate(val1, neg_val1);
 433                 val1 = neg_val1;
 434                 sign ^= 1;
 435         }
 436         if (do_sign(val2) == -1) {
 437                 do_negate(val2, neg_val2);
 438                 val2 = neg_val2;
 439                 sign ^= 1;
 440         }
 441
 442         for (c_outer = 0; c_outer < max_value_size; c_outer++) {
 443                 if (val2[c_outer] != SC_0) {
 444                         for (c_inner = 0; c_inner < max_value_size; c_inner++) {
 445                                 /* do the following calculation:                                    *
 446                                  * Add the current carry, the value at position c_outer+c_inner     *
 447                                  * and the result of the multiplication of val1[c_inner] and        *
 448                                  * val2[c_outer]. This is the usual pen-and-paper multiplication.   */
 449
 450                                 /* multiplicate the two digits */
 451                                 mul = mul_table[_val(val1[c_inner])][_val(val2[c_outer])];
 452                                 /* add old value to result of multiplication */
 453                                 add1 = add_table[_val(temp_buffer[c_inner + c_outer])][_val(mul[0])];
 454                                 /* add carry to the sum */
 455                                 add2 = add_table[_val(add1[0])][_val(carry)];
 456
 457                                 /* all carries together result in new carry. This is always smaller *
 458                                  * than the base b:                                                 *
 459                                  * Both multiplicands, the carry and the value already in the temp  *
 460                                  * buffer are single digits and their value is therefore at most    *
 461                                  * equal to (b-1).                                                  *
 462                                  * This leads to:                                                   *
 463                                  * (b-1)(b-1)+(b-1)+(b-1) = b*b-1                                   *
 464                                  * The tables list all operations rem b, so the carry is at most    *
 465                                  * (b*b-1)rem b = -1rem b = b-1                                     */
 466                                 carry = add_table[_val(mul[1])][_val(add1[1])][0];
 467                                 carry = add_table[_val(carry)][_val(add2[1])][0];
 468
 469                                 temp_buffer[c_inner + c_outer] = add2[0];
 470                         }
 471
 472                         /* A carry may hang over */
 473                         /* c_outer is always smaller than max_value_size! */
 474                         temp_buffer[max_value_size + c_outer] = carry;
 475                         carry = SC_0;
 476                 }
 477         }
 478
 479         if (sign)
 480                 do_negate(temp_buffer, buffer);
 481         else
 482                 memcpy(buffer, temp_buffer, calc_buffer_size);
 483 }
 484
 485 /**
 486  * Shift the buffer to left and add a 4 bit digit
 487  */
 488 static void do_push(const char digit, char *buffer) {
 489         int counter;
 490
 491         for (counter = calc_buffer_size - 2; counter >= 0; counter--) {
 492                 buffer[counter+1] = buffer[counter];
 493         }
 494         buffer[0] = digit;
 495 }
 496
 497 /**
 498  * Implements truncating integer division and remainder.
 499  *
 500  * Note: This is MOST slow
 501  */
 502 static void do_divmod(const char *rDividend, const char *divisor, char *quot, char *rem) {
 503         const char *dividend = rDividend;
 504         const char *minus_divisor;
 505         char *neg_val1;
 506         char *neg_val2;
 507
 508         char div_sign = 0;     /* remember division result sign */
 509         char rem_sign = 0;     /* remember remainder result sign */
 510
 511         int c_dividend;      /* loop counters */
 512
 513         neg_val1 = alloca(calc_buffer_size);
 514         neg_val2 = alloca(calc_buffer_size);
 515
 516         /* clear result buffer */
 517         memset(quot, SC_0, calc_buffer_size);
 518         memset(rem, SC_0, calc_buffer_size);
 519
 520         /* if the divisor is zero this won't work (quot is zero) */
 521         if (sc_comp(divisor, quot) == 0) assert(0 && "division by zero!");
 522
 523         /* if the dividend is zero result is zero (quot is zero) */
 524         if (sc_comp(dividend, quot) == 0)
 525                 return;
 526
 527         if (do_sign(dividend) == -1) {
 528                 do_negate(dividend, neg_val1);
 529                 div_sign ^= 1;
 530                 rem_sign ^= 1;
 531                 dividend = neg_val1;
 532         }
 533
 534         do_negate(divisor, neg_val2);
 535         if (do_sign(divisor) == -1) {
 536                 div_sign ^= 1;
 537                 minus_divisor = divisor;
 538                 divisor = neg_val2;
 539         } else
 540                 minus_divisor = neg_val2;
 541
 542         /* if divisor >= dividend division is easy
 543          * (remember these are absolute values) */
 544         switch (sc_comp(dividend, divisor)) {
 545         case 0: /* dividend == divisor */
 546                 quot[0] = SC_1;
 547                 goto end;
 548
 549         case -1: /* dividend < divisor */
 550                 memcpy(rem, dividend, calc_buffer_size);
 551                 goto end;
 552
 553         default: /* unluckily division is necessary :( */
 554                 break;
 555         }
 556
 557         for (c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) {
 558                 do_push(dividend[c_dividend], rem);
 559                 do_push(SC_0, quot);
 560
 561                 if (sc_comp(rem, divisor) != -1) {  /* remainder >= divisor */
 562                         /* subtract until the remainder becomes negative, this should
 563                          * be faster than comparing remainder with divisor  */
 564                         do_add(rem, minus_divisor, rem);
 565
 566                         while (do_sign(rem) == 1) {
 567                                 quot[0] = add_table[_val(quot[0])][SC_1][0];
 568                                 do_add(rem, minus_divisor, rem);
 569                         }
 570
 571                         /* subtracted one too much */
 572                         do_add(rem, divisor, rem);
 573                 }
 574         }
 575 end:
 576         /* sets carry if remainder is non-zero ??? */
 577         carry_flag = !sc_is_zero(rem);
 578
 579         if (div_sign)
 580                 do_negate(quot, quot);
 581
 582         if (rem_sign)
 583                 do_negate(rem, rem);
 584 }
 585
 586 /**
 587  * Implements a Shift Left, which can either preserve the sign bit
 588  * or not.
 589  *
 590  * @todo Assertions seems to be wrong
 591  */
 592 static void do_shl(const char *val1, char *buffer, long shift_cnt, int bitsize, unsigned is_signed) {
 593         const char *shl;
 594         char shift;
 595         char carry = SC_0;
 596
 597         int counter;
 598         int bitoffset = 0;
 599
 600         assert((shift_cnt >= 0) || (0 && "negative leftshift"));
 601         assert(((do_sign(val1) != -1) || is_signed) || (0 && "unsigned mode and negative value"));
 602         assert(((!_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == -1)) || (0 && "value is positive, should be negative"));
 603         assert(((_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == 1)) || (0 && "value is negative, should be positive"));
 604
 605         /* if shifting far enough the result is zero */
 606         if (shift_cnt >= bitsize) {
 607                 memset(buffer, SC_0, calc_buffer_size);
 608                 return;
 609         }
 610
 611         shift = shift_table[_val(shift_cnt%4)];      /* this is 2 ** (offset % 4) */
 612         shift_cnt = shift_cnt / 4;
 613
 614         /* shift the single digits some bytes (offset) and some bits (table)
 615          * to the left */
 616         for (counter = 0; counter < bitsize/4 - shift_cnt; counter++) {
 617                 shl = mul_table[_val(val1[counter])][_val(shift)];
 618                 buffer[counter + shift_cnt] = shl[0] | carry;
 619                 carry = shl[1];
 620         }
 621         if (bitsize%4 > 0) {
 622                 shl = mul_table[_val(val1[counter])][_val(shift)];
 623                 buffer[counter + shift_cnt] = shl[0] | carry;
 624                 bitoffset = counter;
 625         } else {
 626                 bitoffset = counter - 1;
 627         }
 628
 629         /* fill with zeroes */
 630         for (counter = 0; counter < shift_cnt; counter++)
 631                 buffer[counter] = SC_0;
 632
 633         /* if the mode was signed, change sign when the mode's msb is now 1 */
 634         shift_cnt = bitoffset + shift_cnt;
 635         bitoffset = (bitsize-1) % 4;
 636         if (is_signed && _bitisset(buffer[shift_cnt], bitoffset)) {
 637                 /* this sets the upper bits of the leftmost digit */
 638                 buffer[shift_cnt] |= min_digit[bitoffset];
 639                 for (counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
 640                         buffer[counter] = SC_F;
 641                 }
 642         } else if (is_signed && !_bitisset(buffer[shift_cnt], bitoffset)) {
 643                 /* this clears the upper bits of the leftmost digit */
 644                 buffer[shift_cnt] &= max_digit[bitoffset];
 645                 for (counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
 646                         buffer[counter] = SC_0;
 647                 }
 648         }
 649 }
 650
 651 /**
 652  * Implements a Shift Right, which can either preserve the sign bit
 653  * or not.
 654  *
 655  * @param bitsize   bitsize of the value to be shifted
 656  *
 657  * @todo Assertions seems to be wrong
 658  */
 659 static void do_shr(const char *val1, char *buffer, long shift_cnt, int bitsize, unsigned is_signed, int signed_shift) {
 660         const char *shrs;
 661         char sign;
 662         char msd;
 663
 664         int shift_mod, shift_nib;
 665
 666         int counter;
 667         int bitoffset = 0;
 668
 669         assert((shift_cnt >= 0) || (0 && "negative rightshift"));
 670         assert(((!_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == -1)) || (0 && "value is positive, should be negative"));
 671         assert(((_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == 1)) || (0 && "value is negative, should be positive"));
 672
 673         sign = signed_shift && do_bit(val1, bitsize - 1) ? SC_F : SC_0;
 674
 675         /* if shifting far enough the result is either 0 or -1 */
 676         if (shift_cnt >= bitsize) {
 677                 if (!sc_is_zero(val1)) {
 678                         carry_flag = 1;
 679                 }
 680                 memset(buffer, sign, calc_buffer_size);
 681                 return;
 682         }
 683
 684         shift_mod = shift_cnt &  3;
 685         shift_nib = shift_cnt >> 2;
 686
 687         /* check if any bits are lost, and set carry_flag if so */
 688         for (counter = 0; counter < shift_nib; ++counter) {
 689                 if (val1[counter] != 0) {
 690                         carry_flag = 1;
 691                         break;
 692                 }
 693         }
 694         if ((_val(val1[counter]) & ((1<<shift_mod)-1)) != 0)
 695                 carry_flag = 1;
 696
 697         /* shift digits to the right with offset, carry and all */
 698         buffer[0] = shrs_table[_val(val1[shift_nib])][shift_mod][0];
 699         for (counter = 1; counter < ((bitsize + 3) >> 2) - shift_nib; counter++) {
 700                 shrs = shrs_table[_val(val1[counter + shift_nib])][shift_mod];
 701                 buffer[counter]      = shrs[0];
 702                 buffer[counter - 1] |= shrs[1];
 703         }
 704
 705         /* the last digit is special in regard of signed/unsigned shift */
 706         bitoffset = bitsize & 3;
 707         msd = sign;  /* most significant digit */
 708
 709         /* remove sign bits if mode was signed and this is an unsigned shift */
 710         if (!signed_shift && is_signed) {
 711                 msd &= max_digit[bitoffset];
 712         }
 713
 714         shrs = shrs_table[_val(msd)][shift_mod];
 715
 716         /* signed shift and signed mode and negative value means all bits to the left are set */
 717         if (signed_shift && sign == SC_F) {
 718                 buffer[counter] = shrs[0] | min_digit[bitoffset];
 719         } else {
 720                 buffer[counter] = shrs[0];
 721         }
 722
 723         if (counter > 0)
 724                 buffer[counter - 1] |= shrs[1];
 725
 726         /* fill with SC_F or SC_0 depending on sign */
 727         for (counter++; counter < calc_buffer_size; counter++) {
 728                 buffer[counter] = sign;
 729         }
 730 }
 731
 732 /**
 733  * Implements a Rotate Left.
 734  * positive: low-order -> high order, negative other direction
 735  */
 736 static void do_rotl(const char *val1, char *buffer, long offset, int radius, unsigned is_signed) {
 737         char *temp1, *temp2;
 738         temp1 = alloca(calc_buffer_size);
 739         temp2 = alloca(calc_buffer_size);
 740
 741         offset = offset % radius;
 742
 743         /* rotation by multiples of the type length is identity */
 744         if (offset == 0) {
 745                 memmove(buffer, val1, calc_buffer_size);
 746                 return;
 747         }
 748
 749         do_shl(val1, temp1, offset, radius, is_signed);
 750         do_shr(val1, temp2, radius - offset, radius, is_signed, 0);
 751         do_bitor(temp1, temp2, buffer);
 752         carry_flag = 0; /* set by shr, but due to rot this is false */
 753 }
 754
 755 /*****************************************************************************
 756  * public functions, declared in strcalc.h
 757  *****************************************************************************/
 758 const void *sc_get_buffer(void) {
 759         return (void*)calc_buffer;
 760 }
 761
 762 int sc_get_buffer_length(void) {
 763         return calc_buffer_size;
 764 }
 765
 766 /**
 767  * Do sign extension if the mode is signed, otherwise to zero extension.
 768  */
 769 void sign_extend(void *buffer, ir_mode *mode) {
 770         char *calc_buffer = buffer;
 771         int bits          = get_mode_size_bits(mode) - 1;
 772         int nibble        = bits >> 2;
 773         int max           = max_digit[bits & 3];
 774         int i;
 775
 776         if (mode_is_signed(mode)) {
 777                 if (calc_buffer[nibble] > max) {
 778                         /* sign bit is set, we need sign expansion */
 779
 780                         for (i = nibble + 1; i < calc_buffer_size; ++i)
 781                                 calc_buffer[i] = SC_F;
 782                         calc_buffer[nibble] |= sex_digit[bits & 3];
 783                 } else {
 784                         /* set all bits to zero */
 785                         for (i = nibble + 1; i < calc_buffer_size; ++i)
 786                                 calc_buffer[i] = SC_0;
 787                         calc_buffer[nibble] &= zex_digit[bits & 3];
 788                 }
 789         } else {
 790                 /* do zero extension */
 791                 for (i = nibble + 1; i < calc_buffer_size; ++i)
 792                         calc_buffer[i] = SC_0;
 793                 calc_buffer[nibble] &= zex_digit[bits & 3];
 794         }
 795 }
 796
 797 /* FIXME doesn't check for overflows */
 798 void sc_val_from_str(const char *str, unsigned int len, void *buffer, ir_mode *mode) {
 799         const char *orig_str = str;
 800         unsigned int orig_len = len;
 801
 802         char sign = 0;
 803         char *base, *val;
 804
 805         base = alloca(calc_buffer_size);
 806         val = alloca(calc_buffer_size);
 807
 808         /* verify valid pointers (not null) */
 809         assert(str);
 810         /* a string no characters long is an error */
 811         assert(len);
 812
 813         if (buffer == NULL) buffer = calc_buffer;
 814
 815         CLEAR_BUFFER(buffer);
 816         CLEAR_BUFFER(base);
 817         CLEAR_BUFFER(val);
 818
 819         /* strip leading spaces */
 820         while ((len > 0) && (*str == ' ')) { len--; str++; }
 821
 822         /* if the first two characters are 0x or 0X -> hex
 823          * if the first is a 0 -> oct
 824          * else dec, strip leading -/+ and remember sign
 825          *
 826          * only a + or - sign is no number resulting in an error */
 827         if (len >= 2) {
 828                 switch (str[0]) {
 829                 case '0':
 830                         if (str[1] == 'x' || str[1] == 'X') { /* hex */
 831                                 str += 2;
 832                                 len -= 2;
 833                                 base[1] = SC_1; base[0] = SC_0;
 834                         } else { /* oct */
 835                                 str += 1;
 836                                 len -= 1;
 837                                 base[1] = SC_0; base[0] = SC_8;
 838                         }
 839                         break;
 840
 841                 case '+':
 842                         str += 1;
 843                         len -= 1;
 844                         base[1] = SC_0; base[0] = SC_A;
 845                         break;
 846
 847                 case '-':
 848                         str += 1;
 849                         len -= 1;
 850                         sign = 1;
 851                         base[1] = SC_0; base[0] = SC_A;
 852                         break;
 853
 854                 default: /* dec, else would have begun with 0x or 0 */
 855                         base[1] = SC_0; base[0] = SC_A;
 856                 }
 857         } else { /* dec, else would have begun with 0x or 0 */
 858                 base[1] = SC_0; base[0] = SC_A;
 859         }
 860
 861         /* BEGIN string evaluation, from left to right */
 862         while (len > 0) {
 863                 switch (*str) {
 864                 case 'f':
 865                 case 'e':
 866                 case 'd':
 867                 case 'c':
 868                 case 'b':
 869                 case 'a':
 870                         if (base[0] > SC_A || base[1] > SC_0) { /* (base > 10) */
 871                                 val[0] = _digit((*str)-'a'+10);
 872                         }
 873                         else
 874                                 fail_char(orig_str, orig_len, *str, str-orig_str+1);
 875                         break;
 876
 877                 case 'F':
 878                 case 'E':
 879                 case 'D':
 880                 case 'C':
 881                 case 'B':
 882                 case 'A':
 883                         if (base[0] > SC_A || base[1] > SC_0) { /* (base > 10) */
 884                                 val[0] = _digit((*str)-'A'+10);
 885                         }
 886                         else
 887                                 fail_char(orig_str, orig_len, *str, str-orig_str+1);
 888                         break;
 889
 890                 case '9':
 891                 case '8':
 892                         if (base[0] > SC_8 || base[1] > SC_0) { /* (base > 8) */
 893                                 val[0] = _digit((*str)-'0');
 894                         }
 895                         else
 896                                 fail_char(orig_str, orig_len, *str, str-orig_str+1);
 897                         break;
 898
 899                 case '7':
 900                 case '6':
 901                 case '5':
 902                 case '4':
 903                 case '3':
 904                 case '2':
 905                 case '1':
 906                 case '0':
 907                         val[0] = _digit((*str)-'0');
 908                         break;
 909
 910                 default:
 911                         fail_char(orig_str, orig_len, *str, str-orig_str+1);
 912                 } /* switch(*str) */
 913
 914                 /* Radix conversion from base b to base B:
 915                  *  (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
 916                 do_mul(base, calc_buffer, calc_buffer); /* multiply current value with base */
 917                 do_add(val, calc_buffer, calc_buffer);  /* add next digit to current value  */
 918
 919                 /* get ready for the next letter */
 920                 str++;
 921                 len--;
 922         } /* while (len > 0 ) */
 923
 924         if (sign)
 925                 do_negate(calc_buffer, calc_buffer);
 926
 927         /* beware: even if hex numbers have no sign, we need sign extension here */
 928         sign_extend(calc_buffer, mode);
 929 }
 930
 931 void sc_val_from_long(long value, void *buffer) {
 932         char *pos;
 933         char sign, is_minlong;
 934
 935         if (buffer == NULL) buffer = calc_buffer;
 936         pos = buffer;
 937
 938         sign = (value < 0);
 939         is_minlong = value == LONG_MIN;
 940
 941         /* use absolute value, special treatment of MIN_LONG to avoid overflow */
 942         if (sign) {
 943                 if (is_minlong)
 944                         value = -(value+1);
 945                 else
 946                         value = -value;
 947         }
 948
 949         CLEAR_BUFFER(buffer);
 950
 951         while ((value != 0) && (pos < (char*)buffer + calc_buffer_size)) {
 952                 *pos++ = _digit(value & 0xf);
 953                 value >>= 4;
 954         }
 955
 956         if (sign) {
 957                 if (is_minlong)
 958                         do_inc(buffer, buffer);
 959
 960                 do_negate(buffer, buffer);
 961         }
 962 }
 963
 964 void sc_val_from_ulong(unsigned long value, void *buffer) {
 965         unsigned char *pos;
 966
 967         if (buffer == NULL) buffer = calc_buffer;
 968         pos = buffer;
 969
 970         while (pos < (unsigned char *)buffer + calc_buffer_size) {
 971                 *pos++ = (unsigned char)_digit(value & 0xf);
 972                 value >>= 4;
 973         }
 974 }
 975
 976 long sc_val_to_long(const void *val) {
 977         int i;
 978         long l = 0;
 979
 980         for (i = calc_buffer_size - 1; i >= 0; i--) {
 981                 l = (l << 4) + _val(((char *)val)[i]);
 982         }
 983         return l;
 984 }
 985
 986 void sc_min_from_bits(unsigned int num_bits, unsigned int sign, void *buffer) {
 987         char *pos;
 988         int i, bits;
 989
 990         if (buffer == NULL) buffer = calc_buffer;
 991         CLEAR_BUFFER(buffer);
 992
 993         if (!sign) return;  /* unsigned means minimum is 0(zero) */
 994
 995         pos = buffer;
 996
 997         bits = num_bits - 1;
 998         for (i = 0; i < bits/4; i++)
 999                 *pos++ = SC_0;
1000
1001         *pos++ = min_digit[bits%4];
1002
1003         for (i++; i <= calc_buffer_size - 1; i++)
1004                 *pos++ = SC_F;
1005 }
1006
1007 void sc_max_from_bits(unsigned int num_bits, unsigned int sign, void *buffer) {
1008         char* pos;
1009         int i, bits;
1010
1011         if (buffer == NULL) buffer = calc_buffer;
1012         CLEAR_BUFFER(buffer);
1013         pos = buffer;
1014
1015         bits = num_bits - sign;
1016         for (i = 0; i < bits/4; i++)
1017                 *pos++ = SC_F;
1018
1019         *pos++ = max_digit[bits%4];
1020
1021         for (i++; i <= calc_buffer_size - 1; i++)
1022                 *pos++ = SC_0;
1023 }
1024
1025 void sc_truncate(unsigned int num_bits, void *buffer) {
1026         char *cbuffer = buffer;
1027         char *pos = cbuffer + (num_bits / 4);
1028         char *end = cbuffer + calc_buffer_size;
1029
1030         assert(pos < end);
1031
1032         switch(num_bits % 4) {
1033         case 0: /* nothing to do */ break;
1034         case 1: *pos++ &= SC_1; break;
1035         case 2: *pos++ &= SC_3; break;
1036         case 3: *pos++ &= SC_7; break;
1037         }
1038
1039         for( ; pos < end; ++pos)
1040                 *pos = SC_0;
1041 }
1042
1043 int sc_comp(const void* value1, const void* value2) {
1044         int counter = calc_buffer_size - 1;
1045         const char *val1 = (const char *)value1;
1046         const char *val2 = (const char *)value2;
1047
1048         /* compare signs first:
1049          * the loop below can only compare values of the same sign! */
1050         if (do_sign(val1) != do_sign(val2))
1051                 return (do_sign(val1) == 1)?(1):(-1);
1052
1053         /* loop until two digits differ, the values are equal if there
1054          * are no such two digits */
1055         while (val1[counter] == val2[counter]) {
1056                 counter--;
1057                 if (counter < 0) return 0;
1058         }
1059
1060         /* the leftmost digit is the most significant, so this returns
1061          * the correct result.
1062          * This implies the digit enum is ordered */
1063         return (val1[counter] > val2[counter]) ? (1) : (-1);
1064 }
1065
1066 int sc_get_highest_set_bit(const void *value) {
1067         const char *val = (const char*)value;
1068         int high, counter;
1069
1070         high = calc_buffer_size * 4 - 1;
1071
1072         for (counter = calc_buffer_size-1; counter >= 0; counter--) {
1073                 if (val[counter] == SC_0)
1074                         high -= 4;
1075                 else {
1076                         if (val[counter] > SC_7) return high;
1077                         else if (val[counter] > SC_3) return high - 1;
1078                         else if (val[counter] > SC_1) return high - 2;
1079                         else return high - 3;
1080                 }
1081         }
1082         return high;
1083 }
1084
1085 int sc_get_lowest_set_bit(const void *value) {
1086         const char *val = (const char*)value;
1087         int low, counter;
1088
1089         low = 0;
1090         for (counter = 0; counter < calc_buffer_size; counter++) {
1091                 switch (val[counter]) {
1092                 case SC_1:
1093                 case SC_3:
1094                 case SC_5:
1095                 case SC_7:
1096                 case SC_9:
1097                 case SC_B:
1098                 case SC_D:
1099                 case SC_F:
1100                         return low;
1101                 case SC_2:
1102                 case SC_6:
1103                 case SC_A:
1104                 case SC_E:
1105                         return low + 1;
1106                 case SC_4:
1107                 case SC_C:
1108                         return low + 2;
1109                 case SC_8:
1110                         return low + 3;
1111                 default:
1112                         low += 4;
1113                 }
1114         }
1115         return -1;
1116 }
1117
1118 int sc_get_bit_at(const void *value, unsigned pos) {
1119         const char *val = value;
1120         unsigned nibble = pos >> 2;
1121
1122         return (val[nibble] & shift_table[pos & 3]) != SC_0;
1123 }
1124
1125 void sc_set_bit_at(void *value, unsigned pos)
1126 {
1127         char *val = value;
1128         unsigned nibble = pos >> 2;
1129
1130         val[nibble] |= shift_table[pos & 3];
1131 }
1132
1133 int sc_is_zero(const void *value) {
1134         const char* val = (const char *)value;
1135         int counter;
1136
1137         for (counter = 0; counter < calc_buffer_size; ++counter) {
1138                 if (val[counter] != SC_0)
1139                         return 0;
1140         }
1141         return 1;
1142 }
1143
1144 int sc_is_negative(const void *value) {
1145         return do_sign(value) == -1;
1146 }
1147
1148 int sc_had_carry(void) {
1149         return carry_flag;
1150 }
1151
1152 unsigned char sc_sub_bits(const void *value, int len, unsigned byte_ofs) {
1153         const char *val = (const char *)value;
1154         int nibble_ofs  = 2 * byte_ofs;
1155         unsigned char res;
1156
1157         /* the current scheme uses one byte to store a nibble */
1158         if (4 * nibble_ofs >= len)
1159                 return 0;
1160
1161         res = _val(val[nibble_ofs]);
1162         if (len > 4 * (nibble_ofs + 1))
1163                 res |= _val(val[nibble_ofs + 1]) << 4;
1164
1165         /* kick bits outsize */
1166         if (len - 8 * byte_ofs < 8) {
1167                 res &= (1 << (len - 8 * byte_ofs)) - 1;
1168         }
1169         return res;
1170 }
1171
1172 /*
1173  * convert to a string
1174  * FIXME: Doesn't check buffer bounds
1175  */
1176 const char *sc_print(const void *value, unsigned bits, enum base_t base, int signed_mode) {
1177         static const char big_digits[]   = "0123456789ABCDEF";
1178         static const char small_digits[] = "0123456789abcdef";
1179
1180         char *base_val, *div1_res, *div2_res, *rem_res;
1181         int counter, nibbles, i, sign, mask;
1182         char x;
1183
1184         const char *val = (const char *)value;
1185         const char *p;
1186         char *m, *n, *t;
1187         char *pos;
1188         const char *digits = small_digits;
1189
1190         base_val = alloca(calc_buffer_size);
1191         div1_res = alloca(calc_buffer_size);
1192         div2_res = alloca(calc_buffer_size);
1193         rem_res  = alloca(calc_buffer_size);
1194
1195         pos = output_buffer + bit_pattern_size;
1196         *(--pos) = '\0';
1197
1198         /* special case */
1199         if (bits == 0) {
1200                 bits = bit_pattern_size;
1201 #ifdef STRCALC_DEBUG_FULLPRINT
1202                 bits <<= 1;
1203 #endif
1204         }
1205         nibbles = bits >> 2;
1206         switch (base) {
1207
1208         case SC_HEX:
1209                 digits = big_digits;
1210         case SC_hex:
1211                 for (counter = 0; counter < nibbles; ++counter) {
1212                         *(--pos) = digits[_val(val[counter])];
1213 #ifdef STRCALC_DEBUG_GROUPPRINT
1214                         if ((counter+1)%8 == 0)
1215                                 *(--pos) = ' ';
1216 #endif
1217                 }
1218
1219                 /* last nibble must be masked */
1220                 if (bits & 3) {
1221                         mask = zex_digit[(bits & 3) - 1];
1222                         x    = val[counter++] & mask;
1223                         *(--pos) = digits[_val(x)];
1224                 }
1225
1226                 /* now kill zeros */
1227                 for (; counter > 1; --counter, ++pos) {
1228 #ifdef STRCALC_DEBUG_GROUPPRINT
1229                         if (pos[0] == ' ') ++pos;
1230 #endif
1231                         if (pos[0] != '0')
1232                                 break;
1233                 }
1234                 break;
1235
1236         case SC_BIN:
1237                 for (counter = 0; counter < nibbles; ++counter) {
1238                         pos -= 4;
1239                         p = binary_table[_val(val[counter])];
1240                         pos[0] = p[0];
1241                         pos[1] = p[1];
1242                         pos[2] = p[2];
1243                         pos[3] = p[3];
1244                 }
1245
1246                 /* last nibble must be masked */
1247                 if (bits & 3) {
1248                         mask = zex_digit[(bits & 3) - 1];
1249                         x    = val[counter++] & mask;
1250
1251                         pos -= 4;
1252                         p = binary_table[_val(x)];
1253                         pos[0] = p[0];
1254                         pos[1] = p[1];
1255                         pos[2] = p[2];
1256                         pos[3] = p[3];
1257                 }
1258
1259                 /* now kill zeros */
1260                 for (counter <<= 2; counter > 1; --counter, ++pos)
1261                         if (pos[0] != '0')
1262                                 break;
1263                         break;
1264
1265         case SC_DEC:
1266         case SC_OCT:
1267                 memset(base_val, SC_0, calc_buffer_size);
1268                 base_val[0] = base == SC_DEC ? SC_A : SC_8;
1269
1270                 p    = val;
1271                 sign = 0;
1272                 if (signed_mode && base == SC_DEC) {
1273                         /* check for negative values */
1274                         if (do_bit(val, bits - 1)) {
1275                                 do_negate(val, div2_res);
1276                                 sign = 1;
1277                                 p = div2_res;
1278                         }
1279                 }
1280
1281                 /* transfer data into oscillating buffers */
1282                 memset(div1_res, SC_0, calc_buffer_size);
1283                 for (counter = 0; counter < nibbles; ++counter)
1284                         div1_res[counter] = p[counter];
1285
1286                 /* last nibble must be masked */
1287                 if (bits & 3) {
1288                         mask = zex_digit[(bits & 3) - 1];
1289                         div1_res[counter] = p[counter] & mask;
1290                         ++counter;
1291                 }
1292
1293                 m = div1_res;
1294                 n = div2_res;
1295                 for (;;) {
1296                         do_divmod(m, base_val, n, rem_res);
1297                         t = m;
1298                         m = n;
1299                         n = t;
1300                         *(--pos) = digits[_val(rem_res[0])];
1301
1302                         x = 0;
1303                         for (i = 0; i < calc_buffer_size; ++i)
1304                                 x |= _val(m[i]);
1305
1306                         if (x == 0)
1307                                 break;
1308                 }
1309                 if (sign)
1310                         *(--pos) = '-';
1311                 break;
1312
1313         default:
1314                 panic("Unsupported base %d", base);
1315         }
1316         return pos;
1317 }
1318
1319 void init_strcalc(int precision) {
1320         if (calc_buffer == NULL) {
1321                 if (precision <= 0) precision = SC_DEFAULT_PRECISION;
1322
1323                 /* round up to multiple of 4 */
1324                 precision = (precision + 3) & ~3;
1325
1326                 bit_pattern_size = (precision);
1327                 calc_buffer_size = (precision / 2);
1328                 max_value_size   = (precision / 4);
1329
1330                 calc_buffer   = XMALLOCN(char, calc_buffer_size + 1);
1331                 output_buffer = XMALLOCN(char, bit_pattern_size + 1);
1332
1333                 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));
1334         }
1335 }
1336
1337
1338 void finish_strcalc(void) {
1339         free(calc_buffer);   calc_buffer   = NULL;
1340         free(output_buffer); output_buffer = NULL;
1341 }
1342
1343 int sc_get_precision(void) {
1344         return bit_pattern_size;
1345 }
1346
1347
1348 void sc_add(const void *value1, const void *value2, void *buffer) {
1349         CLEAR_BUFFER(calc_buffer);
1350         carry_flag = 0;
1351
1352         DEBUGPRINTF_COMPUTATION(("%s + ", sc_print_hex(value1)));
1353         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1354
1355         do_add(value1, value2, calc_buffer);
1356
1357         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1358
1359         if ((buffer != NULL) && (buffer != calc_buffer)) {
1360                 memcpy(buffer, calc_buffer, calc_buffer_size);
1361         }
1362 }
1363
1364 void sc_sub(const void *value1, const void *value2, void *buffer) {
1365         CLEAR_BUFFER(calc_buffer);
1366         carry_flag = 0;
1367
1368         DEBUGPRINTF_COMPUTATION(("%s - ", sc_print_hex(value1)));
1369         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1370
1371         do_sub(value1, value2, calc_buffer);
1372
1373         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1374
1375         if ((buffer != NULL) && (buffer != calc_buffer)) {
1376                 memcpy(buffer, calc_buffer, calc_buffer_size);
1377         }
1378 }
1379
1380 void sc_neg(const void *value1, void *buffer) {
1381         carry_flag = 0;
1382
1383         DEBUGPRINTF_COMPUTATION(("- %s ->", sc_print_hex(value1)));
1384
1385         do_negate(value1, calc_buffer);
1386
1387         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1388
1389         if ((buffer != NULL) && (buffer != calc_buffer)) {
1390                 memcpy(buffer, calc_buffer, calc_buffer_size);
1391         }
1392 }
1393
1394 void sc_and(const void *value1, const void *value2, void *buffer) {
1395         CLEAR_BUFFER(calc_buffer);
1396         carry_flag = 0;
1397
1398         DEBUGPRINTF_COMPUTATION(("%s & ", sc_print_hex(value1)));
1399         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1400
1401         do_bitand(value1, value2, calc_buffer);
1402
1403         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1404
1405         if ((buffer != NULL) && (buffer != calc_buffer)) {
1406                 memcpy(buffer, calc_buffer, calc_buffer_size);
1407         }
1408 }
1409
1410 void sc_or(const void *value1, const void *value2, void *buffer) {
1411         CLEAR_BUFFER(calc_buffer);
1412         carry_flag = 0;
1413
1414         DEBUGPRINTF_COMPUTATION(("%s | ", sc_print_hex(value1)));
1415         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1416
1417         do_bitor(value1, value2, calc_buffer);
1418
1419         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1420
1421         if ((buffer != NULL) && (buffer != calc_buffer)) {
1422                 memcpy(buffer, calc_buffer, calc_buffer_size);
1423         }
1424 }
1425
1426 void sc_xor(const void *value1, const void *value2, void *buffer) {
1427         CLEAR_BUFFER(calc_buffer);
1428         carry_flag = 0;
1429
1430         DEBUGPRINTF_COMPUTATION(("%s ^ ", sc_print_hex(value1)));
1431         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1432
1433         do_bitxor(value1, value2, calc_buffer);
1434
1435         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1436
1437         if ((buffer != NULL) && (buffer != calc_buffer)) {
1438                 memcpy(buffer, calc_buffer, calc_buffer_size);
1439         }
1440 }
1441
1442 void sc_not(const void *value1, void *buffer) {
1443         CLEAR_BUFFER(calc_buffer);
1444         carry_flag = 0;
1445
1446         DEBUGPRINTF_COMPUTATION(("~ %s ->", sc_print_hex(value1)));
1447
1448         do_bitnot(value1, calc_buffer);
1449
1450         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1451
1452         if ((buffer != NULL) && (buffer != calc_buffer)) {
1453                 memcpy(buffer, calc_buffer, calc_buffer_size);
1454         }
1455 }
1456
1457 void sc_mul(const void *value1, const void *value2, void *buffer) {
1458         CLEAR_BUFFER(calc_buffer);
1459         carry_flag = 0;
1460
1461         DEBUGPRINTF_COMPUTATION(("%s * ", sc_print_hex(value1)));
1462         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1463
1464         do_mul(value1, value2, calc_buffer);
1465
1466         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1467
1468         if ((buffer != NULL) && (buffer != calc_buffer)) {
1469                 memcpy(buffer, calc_buffer, calc_buffer_size);
1470         }
1471 }
1472
1473 void sc_div(const void *value1, const void *value2, void *buffer) {
1474         /* temp buffer holding unused result of divmod */
1475         char *unused_res = alloca(calc_buffer_size);
1476
1477         CLEAR_BUFFER(calc_buffer);
1478         carry_flag = 0;
1479
1480         DEBUGPRINTF_COMPUTATION(("%s / ", sc_print_hex(value1)));
1481         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1482
1483         do_divmod(value1, value2, calc_buffer, unused_res);
1484
1485         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1486
1487         if ((buffer != NULL) && (buffer != calc_buffer)) {
1488                 memcpy(buffer, calc_buffer, calc_buffer_size);
1489         }
1490 }
1491
1492 void sc_mod(const void *value1, const void *value2, void *buffer) {
1493         /* temp buffer holding unused result of divmod */
1494         char *unused_res = alloca(calc_buffer_size);
1495
1496         CLEAR_BUFFER(calc_buffer);
1497         carry_flag = 0;
1498
1499         DEBUGPRINTF_COMPUTATION(("%s %% ", sc_print_hex(value1)));
1500         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1501
1502         do_divmod(value1, value2, unused_res, calc_buffer);
1503
1504         DEBUGPRINTF_COMPUTATION(("%s\n", sc_print_hex(calc_buffer)));
1505
1506         if ((buffer != NULL) && (buffer != calc_buffer)) {
1507                 memcpy(buffer, calc_buffer, calc_buffer_size);
1508         }
1509 }
1510
1511 void sc_divmod(const void *value1, const void *value2, void *div_buffer, void *mod_buffer) {
1512         CLEAR_BUFFER(calc_buffer);
1513         carry_flag = 0;
1514
1515         DEBUGPRINTF_COMPUTATION(("%s %% ", sc_print_hex(value1)));
1516         DEBUGPRINTF_COMPUTATION(("%s -> ", sc_print_hex(value2)));
1517
1518         do_divmod(value1, value2, div_buffer, mod_buffer);
1519
1520         DEBUGPRINTF_COMPUTATION(("%s:%s\n", sc_print_hex(div_buffer), sc_print_hex(mod_buffer)));
1521 }
1522
1523
1524 void sc_shlI(const void *val1, long shift_cnt, int bitsize, int sign, void *buffer) {
1525         carry_flag = 0;
1526
1527         DEBUGPRINTF_COMPUTATION(("%s << %ld ", sc_print_hex(value1), shift_cnt));
1528         do_shl(val1, calc_buffer, shift_cnt, bitsize, sign);
1529
1530         DEBUGPRINTF_COMPUTATION(("-> %s\n", sc_print_hex(calc_buffer)));
1531
1532         if ((buffer != NULL) && (buffer != calc_buffer)) {
1533                 memmove(buffer, calc_buffer, calc_buffer_size);
1534         }
1535 }
1536
1537 void sc_shl(const void *val1, const void *val2, int bitsize, int sign, void *buffer) {
1538         long offset = sc_val_to_long(val2);
1539
1540         sc_shlI(val1, offset, bitsize, sign, buffer);
1541 }
1542
1543 void sc_shrI(const void *val1, long shift_cnt, int bitsize, int sign, void *buffer) {
1544         carry_flag = 0;
1545
1546         DEBUGPRINTF_COMPUTATION(("%s >>u %ld ", sc_print_hex(value1), shift_cnt));
1547         do_shr(val1, calc_buffer, shift_cnt, bitsize, sign, 0);
1548
1549         DEBUGPRINTF_COMPUTATION(("-> %s\n", sc_print_hex(calc_buffer)));
1550
1551         if ((buffer != NULL) && (buffer != calc_buffer)) {
1552                 memmove(buffer, calc_buffer, calc_buffer_size);
1553         }
1554 }
1555
1556 void sc_shr(const void *val1, const void *val2, int bitsize, int sign, void *buffer) {
1557         long shift_cnt = sc_val_to_long(val2);
1558
1559         sc_shrI(val1, shift_cnt, bitsize, sign, buffer);
1560 }
1561
1562 void sc_shrs(const void *val1, const void *val2, int bitsize, int sign, void *buffer) {
1563         long offset = sc_val_to_long(val2);
1564
1565         carry_flag = 0;
1566
1567         DEBUGPRINTF_COMPUTATION(("%s >>s %ld ", sc_print_hex(value1), offset));
1568         do_shr(val1, calc_buffer, offset, bitsize, sign, 1);
1569
1570         DEBUGPRINTF_COMPUTATION(("-> %s\n", sc_print_hex(calc_buffer)));
1571
1572         if ((buffer != NULL) && (buffer != calc_buffer)) {
1573                 memmove(buffer, calc_buffer, calc_buffer_size);
1574         }
1575 }
1576
1577 void sc_rotl(const void *val1, const void *val2, int bitsize, int sign, void *buffer) {
1578         long offset = sc_val_to_long(val2);
1579
1580         carry_flag = 0;
1581
1582         DEBUGPRINTF_COMPUTATION(("%s <<>> %ld ", sc_print_hex(value1), offset));
1583         do_rotl(val1, calc_buffer, offset, bitsize, sign);
1584
1585         DEBUGPRINTF_COMPUTATION(("-> %s\n", sc_print_hex(calc_buffer)));
1586
1587         if ((buffer != NULL) && (buffer != calc_buffer)) {
1588                 memmove(buffer, calc_buffer, calc_buffer_size);
1589         }
1590 }
1591
1592 void sc_zero(void *buffer) {
1593         if (buffer == NULL)
1594                 buffer = calc_buffer;
1595         CLEAR_BUFFER(buffer);
1596         carry_flag = 0;
1597 }