strcalc.c 47.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
23
24
25
/**
 * @file
 * @brief    Provides basic mathematical operations on values represented as strings.
 * @date     2003
 * @author   Mathias Heil
 * @version  $Id$
26
 */
Matthias Braun's avatar
Matthias Braun committed
27
#include "config.h"
Boris Boesler's avatar
Boris Boesler committed
28

29
#include <stdlib.h>
30
31
32
33
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <limits.h>
34

Michael Beck's avatar
Michael Beck committed
35
#include "strcalc.h"
Michael Beck's avatar
Michael Beck committed
36
#include "xmalloc.h"
37
#include "error.h"
Michael Beck's avatar
Michael Beck committed
38

39
/*
40
 * local definitions and macros
41
 */
Michael Beck's avatar
Michael Beck committed
42
#define CLEAR_BUFFER(b) assert(b); memset(b, SC_0, calc_buffer_size)
43
#define SHIFT(count) (SC_1 << (count))
44
45
#define _val(a) ((a)-SC_0)
#define _digit(a) ((a)+SC_0)
46
#define _bitisset(digit, pos) (((digit) & SHIFT(pos)) != SC_0)
47

48
/* shortcut output for debugging */
49
50
51
52
#  define sc_print_hex(a) sc_print((a), 0, SC_HEX, 0)
#  define sc_print_dec(a) sc_print((a), 0, SC_DEC, 1)
#  define sc_print_oct(a) sc_print((a), 0, SC_OCT, 0)
#  define sc_print_bin(a) sc_print((a), 0, SC_BIN, 0)
53
54

#ifdef STRCALC_DEBUG_PRINTCOMP
55
56
57
58
#  define DEBUGPRINTF_COMPUTATION(x) printf x
#else
#  define DEBUGPRINTF_COMPUTATION(x) ((void)0)
#endif
Matthias Heil's avatar
Matthias Heil committed
59
#ifdef STRCALC_DEBUG
60
#  define DEBUGPRINTF(x) printf x
61
#else
62
#  define DEBUGPRINTF(x) ((void)0)
63
64
#endif

65

66
/*
67
 * private variables
68
 */
Matthias Heil's avatar
Matthias Heil committed
69
70
static char *calc_buffer = NULL;    /* buffer holding all results */
static char *output_buffer = NULL;  /* buffer for output */
Michael Beck's avatar
Michael Beck committed
71
72
73
static int bit_pattern_size;        /* maximum number of bits */
static int calc_buffer_size;        /* size of internally stored values */
static int max_value_size;          /* maximum size of values */
74

Michael Beck's avatar
Michael Beck committed
75
static int carry_flag;              /**< some computation set the carry_flag:
Michael Beck's avatar
Michael Beck committed
76
                                         - right shift if bits were lost due to shifting
Michael Beck's avatar
Michael Beck committed
77
                                         - division if there was a remainder
Michael Beck's avatar
Michael Beck committed
78
79
                                         However, the meaning of carry is machine dependent
                                         and often defined in other ways! */
80

81
static const char sex_digit[4] = { SC_E, SC_C, SC_8, SC_0 };
82
static const char zex_digit[4] = { SC_1, SC_3, SC_7, SC_F };
83
84
static const char max_digit[4] = { SC_0, SC_1, SC_3, SC_7 };
static const char min_digit[4] = { SC_F, SC_E, SC_C, SC_8 };
85

86
static char const add_table[16][16][2] = {
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
                       { {SC_0, SC_0}, {SC_1, SC_0}, {SC_2, SC_0}, {SC_3, SC_0},
                         {SC_4, SC_0}, {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0},
                         {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0},
                         {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0} },

                       { {SC_1, SC_0}, {SC_2, SC_0}, {SC_3, SC_0}, {SC_4, SC_0},
                         {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0}, {SC_8, SC_0},
                         {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0},
                         {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1} },

                       { {SC_2, SC_0}, {SC_3, SC_0}, {SC_4, SC_0}, {SC_5, SC_0},
                         {SC_6, SC_0}, {SC_7, SC_0}, {SC_8, SC_0}, {SC_9, SC_0},
                         {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0},
                         {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1} },

                       { {SC_3, SC_0}, {SC_4, SC_0}, {SC_5, SC_0}, {SC_6, SC_0},
                         {SC_7, SC_0}, {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0},
                         {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0},
                         {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1} },

                       { {SC_4, SC_0}, {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0},
                         {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0},
                         {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0},
                         {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1} },

                       { {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0}, {SC_8, SC_0},
                         {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0},
                         {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1},
                         {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1} },

                       { {SC_6, SC_0}, {SC_7, SC_0}, {SC_8, SC_0}, {SC_9, SC_0},
                         {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0},
                         {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1},
                         {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1} },

                       { {SC_7, SC_0}, {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0},
                         {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0},
                         {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1},
                         {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1} },

                       { {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0},
                         {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0},
                         {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1},
                         {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1}, {SC_7, SC_1} },

                       { {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0},
                         {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1},
                         {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1},
                         {SC_5, SC_1}, {SC_6, SC_1}, {SC_7, SC_1}, {SC_8, SC_1} },

                       { {SC_A, SC_0}, {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0},
                         {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1},
                         {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1},
                         {SC_6, SC_1}, {SC_7, SC_1}, {SC_8, SC_1}, {SC_9, SC_1} },

                       { {SC_B, SC_0}, {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0},
                         {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1},
                         {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1},
                         {SC_7, SC_1}, {SC_8, SC_1}, {SC_9, SC_1}, {SC_A, SC_1} },

                       { {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0},
                         {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1},
                         {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1}, {SC_7, SC_1},
                         {SC_8, SC_1}, {SC_9, SC_1}, {SC_A, SC_1}, {SC_B, SC_1} },

                       { {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1},
                         {SC_1, SC_1}, {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1},
                         {SC_5, SC_1}, {SC_6, SC_1}, {SC_7, SC_1}, {SC_8, SC_1},
                         {SC_9, SC_1}, {SC_A, SC_1}, {SC_B, SC_1}, {SC_C, SC_1} },

                       { {SC_E, SC_0}, {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1},
                         {SC_2, SC_1}, {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1},
                         {SC_6, SC_1}, {SC_7, SC_1}, {SC_8, SC_1}, {SC_9, SC_1},
                         {SC_A, SC_1}, {SC_B, SC_1}, {SC_C, SC_1}, {SC_D, SC_1} },

                       { {SC_F, SC_0}, {SC_0, SC_1}, {SC_1, SC_1}, {SC_2, SC_1},
                         {SC_3, SC_1}, {SC_4, SC_1}, {SC_5, SC_1}, {SC_6, SC_1},
                         {SC_7, SC_1}, {SC_8, SC_1}, {SC_9, SC_1}, {SC_A, SC_1},
                         {SC_B, SC_1}, {SC_C, SC_1}, {SC_D, SC_1}, {SC_E, SC_1} }
                             };

168
static char const mul_table[16][16][2] = {
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
                       { {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0},
                         {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0},
                         {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0},
                         {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0} },

                       { {SC_0, SC_0}, {SC_1, SC_0}, {SC_2, SC_0}, {SC_3, SC_0},
                         {SC_4, SC_0}, {SC_5, SC_0}, {SC_6, SC_0}, {SC_7, SC_0},
                         {SC_8, SC_0}, {SC_9, SC_0}, {SC_A, SC_0}, {SC_B, SC_0},
                         {SC_C, SC_0}, {SC_D, SC_0}, {SC_E, SC_0}, {SC_F, SC_0} },

                       { {SC_0, SC_0}, {SC_2, SC_0}, {SC_4, SC_0}, {SC_6, SC_0},
                         {SC_8, SC_0}, {SC_A, SC_0}, {SC_C, SC_0}, {SC_E, SC_0},
                         {SC_0, SC_1}, {SC_2, SC_1}, {SC_4, SC_1}, {SC_6, SC_1},
                         {SC_8, SC_1}, {SC_A, SC_1}, {SC_C, SC_1}, {SC_E, SC_1} },

                       { {SC_0, SC_0}, {SC_3, SC_0}, {SC_6, SC_0}, {SC_9, SC_0},
                         {SC_C, SC_0}, {SC_F, SC_0}, {SC_2, SC_1}, {SC_5, SC_1},
                         {SC_8, SC_1}, {SC_B, SC_1}, {SC_E, SC_1}, {SC_1, SC_2},
                         {SC_4, SC_2}, {SC_7, SC_2}, {SC_A, SC_2}, {SC_D, SC_2} },

                       { {SC_0, SC_0}, {SC_4, SC_0}, {SC_8, SC_0}, {SC_C, SC_0},
                         {SC_0, SC_1}, {SC_4, SC_1}, {SC_8, SC_1}, {SC_C, SC_1},
                         {SC_0, SC_2}, {SC_4, SC_2}, {SC_8, SC_2}, {SC_C, SC_2},
                         {SC_0, SC_3}, {SC_4, SC_3}, {SC_8, SC_3}, {SC_C, SC_3} },

                       { {SC_0, SC_0}, {SC_5, SC_0}, {SC_A, SC_0}, {SC_F, SC_0},
                         {SC_4, SC_1}, {SC_9, SC_1}, {SC_E, SC_1}, {SC_3, SC_2},
                         {SC_8, SC_2}, {SC_D, SC_2}, {SC_2, SC_3}, {SC_7, SC_3},
                         {SC_C, SC_3}, {SC_1, SC_4}, {SC_6, SC_4}, {SC_B, SC_4} },

                       { {SC_0, SC_0}, {SC_6, SC_0}, {SC_C, SC_0}, {SC_2, SC_1},
                         {SC_8, SC_1}, {SC_E, SC_1}, {SC_4, SC_2}, {SC_A, SC_2},
                         {SC_0, SC_3}, {SC_6, SC_3}, {SC_C, SC_3}, {SC_2, SC_4},
                         {SC_8, SC_4}, {SC_E, SC_4}, {SC_4, SC_5}, {SC_A, SC_5} },

                       { {SC_0, SC_0}, {SC_7, SC_0}, {SC_E, SC_0}, {SC_5, SC_1},
                         {SC_C, SC_1}, {SC_3, SC_2}, {SC_A, SC_2}, {SC_1, SC_3},
                         {SC_8, SC_3}, {SC_F, SC_3}, {SC_6, SC_4}, {SC_D, SC_4},
                         {SC_4, SC_5}, {SC_B, SC_5}, {SC_2, SC_6}, {SC_9, SC_6} },

                       { {SC_0, SC_0}, {SC_8, SC_0}, {SC_0, SC_1}, {SC_8, SC_1},
                         {SC_0, SC_2}, {SC_8, SC_2}, {SC_0, SC_3}, {SC_8, SC_3},
                         {SC_0, SC_4}, {SC_8, SC_4}, {SC_0, SC_5}, {SC_8, SC_5},
                         {SC_0, SC_6}, {SC_8, SC_6}, {SC_0, SC_7}, {SC_8, SC_7} },

                       { {SC_0, SC_0}, {SC_9, SC_0}, {SC_2, SC_1}, {SC_B, SC_1},
                         {SC_4, SC_2}, {SC_D, SC_2}, {SC_6, SC_3}, {SC_F, SC_3},
                         {SC_8, SC_4}, {SC_1, SC_5}, {SC_A, SC_5}, {SC_3, SC_6},
                         {SC_C, SC_6}, {SC_5, SC_7}, {SC_E, SC_7}, {SC_7, SC_8} },

                       { {SC_0, SC_0}, {SC_A, SC_0}, {SC_4, SC_1}, {SC_E, SC_1},
                         {SC_8, SC_2}, {SC_2, SC_3}, {SC_C, SC_3}, {SC_6, SC_4},
                         {SC_0, SC_5}, {SC_A, SC_5}, {SC_4, SC_6}, {SC_E, SC_6},
                         {SC_8, SC_7}, {SC_2, SC_8}, {SC_C, SC_8}, {SC_6, SC_9} },

                       { {SC_0, SC_0}, {SC_B, SC_0}, {SC_6, SC_1}, {SC_1, SC_2},
                         {SC_C, SC_2}, {SC_7, SC_3}, {SC_2, SC_4}, {SC_D, SC_4},
                         {SC_8, SC_5}, {SC_3, SC_6}, {SC_E, SC_6}, {SC_9, SC_7},
                         {SC_4, SC_8}, {SC_F, SC_8}, {SC_A, SC_9}, {SC_5, SC_A} },

                       { {SC_0, SC_0}, {SC_C, SC_0}, {SC_8, SC_1}, {SC_4, SC_2},
                         {SC_0, SC_3}, {SC_C, SC_3}, {SC_8, SC_4}, {SC_4, SC_5},
                         {SC_0, SC_6}, {SC_C, SC_6}, {SC_8, SC_7}, {SC_4, SC_8},
                         {SC_0, SC_9}, {SC_C, SC_9}, {SC_8, SC_A}, {SC_4, SC_B} },

                       { {SC_0, SC_0}, {SC_D, SC_0}, {SC_A, SC_1}, {SC_7, SC_2},
                         {SC_4, SC_3}, {SC_1, SC_4}, {SC_E, SC_4}, {SC_B, SC_5},
                         {SC_8, SC_6}, {SC_5, SC_7}, {SC_2, SC_8}, {SC_F, SC_8},
                         {SC_C, SC_9}, {SC_9, SC_A}, {SC_6, SC_B}, {SC_3, SC_C} },

                       { {SC_0, SC_0}, {SC_E, SC_0}, {SC_C, SC_1}, {SC_A, SC_2},
                         {SC_8, SC_3}, {SC_6, SC_4}, {SC_4, SC_5}, {SC_2, SC_6},
                         {SC_0, SC_7}, {SC_E, SC_7}, {SC_C, SC_8}, {SC_A, SC_9},
                         {SC_8, SC_A}, {SC_6, SC_B}, {SC_4, SC_C}, {SC_2, SC_D} },

                       { {SC_0, SC_0}, {SC_F, SC_0}, {SC_E, SC_1}, {SC_D, SC_2},
                         {SC_C, SC_3}, {SC_B, SC_4}, {SC_A, SC_5}, {SC_9, SC_6},
                         {SC_8, SC_7}, {SC_7, SC_8}, {SC_6, SC_9}, {SC_5, SC_A},
                         {SC_4, SC_B}, {SC_3, SC_C}, {SC_2, SC_D}, {SC_1, SC_E} }
                             };

250
static char const shrs_table[16][4][2] = {
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
                       { {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0}, {SC_0, SC_0} },
                       { {SC_1, SC_0}, {SC_0, SC_8}, {SC_0, SC_4}, {SC_0, SC_2} },
                       { {SC_2, SC_0}, {SC_1, SC_0}, {SC_0, SC_8}, {SC_0, SC_4} },
                       { {SC_3, SC_0}, {SC_1, SC_8}, {SC_0, SC_C}, {SC_0, SC_6} },
                       { {SC_4, SC_0}, {SC_2, SC_0}, {SC_1, SC_0}, {SC_0, SC_8} },
                       { {SC_5, SC_0}, {SC_2, SC_8}, {SC_1, SC_4}, {SC_0, SC_A} },
                       { {SC_6, SC_0}, {SC_3, SC_0}, {SC_1, SC_8}, {SC_0, SC_C} },
                       { {SC_7, SC_0}, {SC_3, SC_8}, {SC_1, SC_C}, {SC_0, SC_E} },
                       { {SC_8, SC_0}, {SC_4, SC_0}, {SC_2, SC_0}, {SC_1, SC_0} },
                       { {SC_9, SC_0}, {SC_4, SC_8}, {SC_2, SC_4}, {SC_1, SC_2} },
                       { {SC_A, SC_0}, {SC_5, SC_0}, {SC_2, SC_8}, {SC_1, SC_4} },
                       { {SC_B, SC_0}, {SC_5, SC_8}, {SC_2, SC_C}, {SC_1, SC_6} },
                       { {SC_C, SC_0}, {SC_6, SC_0}, {SC_3, SC_0}, {SC_1, SC_8} },
                       { {SC_D, SC_0}, {SC_6, SC_8}, {SC_3, SC_4}, {SC_1, SC_A} },
                       { {SC_E, SC_0}, {SC_7, SC_0}, {SC_3, SC_8}, {SC_1, SC_C} },
                       { {SC_F, SC_0}, {SC_7, SC_8}, {SC_3, SC_C}, {SC_1, SC_E} }
                                   };
268

Michael Beck's avatar
Michael Beck committed
269
/** converting a digit to a binary string */
270
static const char *binary_table[16] = {
271
272
	"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
	"1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"
273
274
};

275
276
277
278
/*****************************************************************************
 * private functions
 *****************************************************************************/

Michael Beck's avatar
Michael Beck committed
279
280
281
/**
 * implements the bitwise NOT operation
 */
282
283
static void do_bitnot(const char *val, char *buffer)
{
284
	int counter;
285

286
	for (counter = 0; counter<calc_buffer_size; counter++)
287
		buffer[counter] = val[counter] ^ SC_F;
288
289
}

Michael Beck's avatar
Michael Beck committed
290
291
292
/**
 * implements the bitwise OR operation
 */
293
294
static void do_bitor(const char *val1, const char *val2, char *buffer)
{
295
	int counter;
296

297
	for (counter = 0; counter<calc_buffer_size; counter++)
298
		buffer[counter] = val1[counter] | val2[counter];
299
300
}

Michael Beck's avatar
Michael Beck committed
301
302
303
/**
 * implements the bitwise eXclusive OR operation
 */
304
305
static void do_bitxor(const char *val1, const char *val2, char *buffer)
{
306
	int counter;
307

308
	for (counter = 0; counter<calc_buffer_size; counter++)
309
		buffer[counter] = val1[counter] ^ val2[counter];
310
311
}

Michael Beck's avatar
Michael Beck committed
312
313
314
/**
 * implements the bitwise AND operation
 */
315
316
static void do_bitand(const char *val1, const char *val2, char *buffer)
{
317
	int counter;
318

319
	for (counter = 0; counter<calc_buffer_size; counter++)
320
		buffer[counter] = val1[counter] & val2[counter];
321
322
}

323
324
325
326
327
328
329
330
331
332
333
/**
 * implements the bitwise AND not operation
 */
static void do_bitandnot(const char *val1, const char *val2, char *buffer)
{
	int counter;

	for (counter = 0; counter < calc_buffer_size; ++counter)
		buffer[counter] = val1[counter] & (SC_F ^ val2[counter]);
}

Michael Beck's avatar
Michael Beck committed
334
335
336
337
338
339
/**
 * returns the sign bit.
 *
 * @todo This implementation is wrong, as it returns the highest bit of the buffer
 *       NOT the highest bit depending on the real mode
 */
340
341
static int do_sign(const char *val)
{
342
	return (val[calc_buffer_size-1] <= SC_7) ? (1) : (-1);
343
344
}

Michael Beck's avatar
Michael Beck committed
345
/**
Michael Beck's avatar
Michael Beck committed
346
347
 * returns non-zero if bit at position pos is set
 */
348
349
static int do_bit(const char *val, int pos)
{
350
351
	int bit    = pos & 3;
	int nibble = pos >> 2;
Michael Beck's avatar
Michael Beck committed
352

353
	return _bitisset(val[nibble], bit);
Michael Beck's avatar
Michael Beck committed
354
355
}

Michael Beck's avatar
Michael Beck committed
356
357
358
/**
 * Implements a fast ADD + 1
 */
359
360
static void do_inc(const char *val, char *buffer)
{
361
362
363
364
365
366
367
368
369
370
371
372
373
374
	int counter = 0;

	while (counter++ < calc_buffer_size) {
		if (*val == SC_F) {
			*buffer++ = SC_0;
			val++;
		} else {
			/* No carry here, *val != SC_F */
			*buffer = add_table[_val(*val)][SC_1][0];
			return;
		}
	}
	/* here a carry could be lost, this is intended because this should
	 * happen only when a value changes sign. */
375
376
}

Michael Beck's avatar
Michael Beck committed
377
378
379
/**
 * Implements a unary MINUS
 */
380
381
static void do_negate(const char *val, char *buffer)
{
382
383
	do_bitnot(val, buffer);
	do_inc(buffer, buffer);
384
385
}

Michael Beck's avatar
Michael Beck committed
386
387
388
389
/**
 * Implements a binary ADD
 *
 * @todo The implementation of carry is wrong, as it is the
Michael Beck's avatar
Michael Beck committed
390
 *       calc_buffer_size carry, not the mode depending
Michael Beck's avatar
Michael Beck committed
391
 */
392
393
static void do_add(const char *val1, const char *val2, char *buffer)
{
394
395
396
397
398
399
400
401
402
403
404
405
	int counter;
	const char *add1, *add2;
	char carry = SC_0;

	for (counter = 0; counter < calc_buffer_size; counter++)   {
		add1 = add_table[_val(val1[counter])][_val(val2[counter])];
		add2 = add_table[_val(add1[0])][_val(carry)];
		/* carry might be zero */
		buffer[counter] = add2[0];
		carry = add_table[_val(add1[1])][_val(add2[1])][0];
	}
	carry_flag = carry != SC_0;
406
407
}

Michael Beck's avatar
Michael Beck committed
408
409
410
/**
 * Implements a binary SUB
 */
411
412
static void do_sub(const char *val1, const char *val2, char *buffer)
{
413
	char *temp_buffer = (char*) alloca(calc_buffer_size); /* intermediate buffer to hold -val2 */
Michael Beck's avatar
Michael Beck committed
414

415
416
	do_negate(val2, temp_buffer);
	do_add(val1, temp_buffer, buffer);
Michael Beck's avatar
Michael Beck committed
417
418
419
420
421
}

/**
 * Implements a binary MUL
 */
422
423
static void do_mul(const char *val1, const char *val2, char *buffer)
{
424
425
426
427
428
429
430
431
432
	char *temp_buffer; /* result buffer */
	char *neg_val1;    /* abs of val1 */
	char *neg_val2;    /* abs of val2 */

	const char *mul, *add1, *add2;      /* intermediate result containers */
	char carry = SC_0;                  /* container for carries */
	char sign = 0;                      /* marks result sign */
	int c_inner, c_outer;               /* loop counters */

433
434
435
	temp_buffer = (char*) alloca(calc_buffer_size);
	neg_val1 = (char*) alloca(calc_buffer_size);
	neg_val2 = (char*) alloca(calc_buffer_size);
436

437
	/* init result buffer to zeros */
438
439
440
441
	memset(temp_buffer, SC_0, calc_buffer_size);

	/* the multiplication works only for positive values, for negative values *
	 * it is necessary to negate them and adjust the result accordingly       */
442
443
	if (do_sign(val1) == -1) {
		do_negate(val1, neg_val1);
444
445
446
		val1 = neg_val1;
		sign ^= 1;
	}
447
448
	if (do_sign(val2) == -1) {
		do_negate(val2, neg_val2);
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
		val2 = neg_val2;
		sign ^= 1;
	}

	for (c_outer = 0; c_outer < max_value_size; c_outer++) {
		if (val2[c_outer] != SC_0) {
			for (c_inner = 0; c_inner < max_value_size; c_inner++) {
				/* do the following calculation:                                    *
				 * Add the current carry, the value at position c_outer+c_inner     *
				 * and the result of the multiplication of val1[c_inner] and        *
				 * val2[c_outer]. This is the usual pen-and-paper multiplication.   */

				/* multiplicate the two digits */
				mul = mul_table[_val(val1[c_inner])][_val(val2[c_outer])];
				/* add old value to result of multiplication */
				add1 = add_table[_val(temp_buffer[c_inner + c_outer])][_val(mul[0])];
				/* add carry to the sum */
				add2 = add_table[_val(add1[0])][_val(carry)];

				/* all carries together result in new carry. This is always smaller *
				 * than the base b:                                                 *
				 * Both multiplicands, the carry and the value already in the temp  *
				 * buffer are single digits and their value is therefore at most    *
				 * equal to (b-1).                                                  *
				 * This leads to:                                                   *
				 * (b-1)(b-1)+(b-1)+(b-1) = b*b-1                                   *
				 * The tables list all operations rem b, so the carry is at most    *
				 * (b*b-1)rem b = -1rem b = b-1                                     */
				carry = add_table[_val(mul[1])][_val(add1[1])][0];
				carry = add_table[_val(carry)][_val(add2[1])][0];

				temp_buffer[c_inner + c_outer] = add2[0];
			}

			/* A carry may hang over */
			/* c_outer is always smaller than max_value_size! */
			temp_buffer[max_value_size + c_outer] = carry;
			carry = SC_0;
		}
	}

	if (sign)
491
		do_negate(temp_buffer, buffer);
492
493
	else
		memcpy(buffer, temp_buffer, calc_buffer_size);
494
495
}

Michael Beck's avatar
Michael Beck committed
496
497
498
/**
 * Shift the buffer to left and add a 4 bit digit
 */
499
500
static void do_push(const char digit, char *buffer)
{
501
502
503
504
505
506
	int counter;

	for (counter = calc_buffer_size - 2; counter >= 0; counter--) {
		buffer[counter+1] = buffer[counter];
	}
	buffer[0] = digit;
507
508
}

Michael Beck's avatar
Michael Beck committed
509
510
511
512
513
/**
 * Implements truncating integer division and remainder.
 *
 * Note: This is MOST slow
 */
514
515
static void do_divmod(const char *rDividend, const char *divisor, char *quot, char *rem)
{
516
517
518
519
520
521
	const char *dividend = rDividend;
	const char *minus_divisor;
	char *neg_val1;
	char *neg_val2;

	char div_sign = 0;     /* remember division result sign */
Michael Beck's avatar
Michael Beck committed
522
	char rem_sign = 0;     /* remember remainder result sign */
523
524
525

	int c_dividend;      /* loop counters */

526
527
	neg_val1 = (char*) alloca(calc_buffer_size);
	neg_val2 = (char*) alloca(calc_buffer_size);
528
529
530
531
532
533
534
535
536
537
538
539

	/* clear result buffer */
	memset(quot, SC_0, calc_buffer_size);
	memset(rem, SC_0, calc_buffer_size);

	/* if the divisor is zero this won't work (quot is zero) */
	if (sc_comp(divisor, quot) == 0) assert(0 && "division by zero!");

	/* if the dividend is zero result is zero (quot is zero) */
	if (sc_comp(dividend, quot) == 0)
		return;

540
541
	if (do_sign(dividend) == -1) {
		do_negate(dividend, neg_val1);
542
543
544
545
546
		div_sign ^= 1;
		rem_sign ^= 1;
		dividend = neg_val1;
	}

547
548
	do_negate(divisor, neg_val2);
	if (do_sign(divisor) == -1) {
549
550
551
552
553
554
555
556
557
558
559
560
561
562
		div_sign ^= 1;
		minus_divisor = divisor;
		divisor = neg_val2;
	} else
		minus_divisor = neg_val2;

	/* if divisor >= dividend division is easy
	 * (remember these are absolute values) */
	switch (sc_comp(dividend, divisor)) {
	case 0: /* dividend == divisor */
		quot[0] = SC_1;
		goto end;

	case -1: /* dividend < divisor */
563
		memcpy(rem, dividend, calc_buffer_size);
564
565
566
567
568
569
570
		goto end;

	default: /* unluckily division is necessary :( */
		break;
	}

	for (c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) {
571
572
		do_push(dividend[c_dividend], rem);
		do_push(SC_0, quot);
573
574
575
576

		if (sc_comp(rem, divisor) != -1) {  /* remainder >= divisor */
			/* subtract until the remainder becomes negative, this should
			 * be faster than comparing remainder with divisor  */
577
			do_add(rem, minus_divisor, rem);
578

579
			while (do_sign(rem) == 1) {
580
				quot[0] = add_table[_val(quot[0])][SC_1][0];
581
				do_add(rem, minus_divisor, rem);
582
583
584
			}

			/* subtracted one too much */
585
			do_add(rem, divisor, rem);
586
587
588
589
590
591
592
		}
	}
end:
	/* sets carry if remainder is non-zero ??? */
	carry_flag = !sc_is_zero(rem);

	if (div_sign)
593
		do_negate(quot, quot);
594
595

	if (rem_sign)
596
		do_negate(rem, rem);
597
598
}

Michael Beck's avatar
Michael Beck committed
599
600
601
602
603
604
/**
 * Implements a Shift Left, which can either preserve the sign bit
 * or not.
 *
 * @todo Assertions seems to be wrong
 */
605
606
static void do_shl(const char *val1, char *buffer, long shift_cnt, int bitsize, unsigned is_signed)
{
607
608
609
610
611
612
613
	const char *shl;
	char shift;
	char carry = SC_0;

	int counter;
	int bitoffset = 0;

614
	assert((shift_cnt >= 0) || (0 && "negative leftshift"));
615
616
617
	assert(((do_sign(val1) != -1) || is_signed) || (0 && "unsigned mode and negative value"));
	assert(((!_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == -1)) || (0 && "value is positive, should be negative"));
	assert(((_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == 1)) || (0 && "value is negative, should be positive"));
618
619

	/* if shifting far enough the result is zero */
620
	if (shift_cnt >= bitsize) {
621
622
623
624
		memset(buffer, SC_0, calc_buffer_size);
		return;
	}

625
	shift     = SHIFT(shift_cnt % 4); /* this is 2 ** (offset % 4) */
626
	shift_cnt = shift_cnt / 4;
627
628
629

	/* shift the single digits some bytes (offset) and some bits (table)
	 * to the left */
630
	for (counter = 0; counter < bitsize/4 - shift_cnt; counter++) {
631
		shl = mul_table[_val(val1[counter])][_val(shift)];
632
		buffer[counter + shift_cnt] = shl[0] | carry;
633
634
		carry = shl[1];
	}
635
	if (bitsize%4 > 0) {
636
		shl = mul_table[_val(val1[counter])][_val(shift)];
637
		buffer[counter + shift_cnt] = shl[0] | carry;
638
639
640
641
642
643
		bitoffset = counter;
	} else {
		bitoffset = counter - 1;
	}

	/* fill with zeroes */
644
	for (counter = 0; counter < shift_cnt; counter++)
645
646
647
		buffer[counter] = SC_0;

	/* if the mode was signed, change sign when the mode's msb is now 1 */
648
649
650
	shift_cnt = bitoffset + shift_cnt;
	bitoffset = (bitsize-1) % 4;
	if (is_signed && _bitisset(buffer[shift_cnt], bitoffset)) {
651
		/* this sets the upper bits of the leftmost digit */
652
		buffer[shift_cnt] |= min_digit[bitoffset];
653
		for (counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
654
655
			buffer[counter] = SC_F;
		}
656
	} else if (is_signed && !_bitisset(buffer[shift_cnt], bitoffset)) {
657
		/* this clears the upper bits of the leftmost digit */
658
		buffer[shift_cnt] &= max_digit[bitoffset];
659
		for (counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
660
661
662
			buffer[counter] = SC_0;
		}
	}
663
664
}

Michael Beck's avatar
Michael Beck committed
665
666
667
668
/**
 * Implements a Shift Right, which can either preserve the sign bit
 * or not.
 *
669
670
 * @param bitsize   bitsize of the value to be shifted
 *
Michael Beck's avatar
Michael Beck committed
671
672
 * @todo Assertions seems to be wrong
 */
673
674
static void do_shr(const char *val1, char *buffer, long shift_cnt, int bitsize, unsigned is_signed, int signed_shift)
{
675
676
677
678
	const char *shrs;
	char sign;
	char msd;

679
	int shift_mod, shift_nib;
680
681
682
683

	int counter;
	int bitoffset = 0;

684
	assert((shift_cnt >= 0) || (0 && "negative rightshift"));
685
686
	assert(((!_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == -1)) || (0 && "value is positive, should be negative"));
	assert(((_bitisset(val1[(bitsize-1)/4], (bitsize-1)%4)) || !is_signed || (do_sign(val1) == 1)) || (0 && "value is negative, should be positive"));
687

688
	sign = signed_shift && do_bit(val1, bitsize - 1) ? SC_F : SC_0;
689
690

	/* if shifting far enough the result is either 0 or -1 */
691
	if (shift_cnt >= bitsize) {
692
693
694
695
696
697
698
		if (!sc_is_zero(val1)) {
			carry_flag = 1;
		}
		memset(buffer, sign, calc_buffer_size);
		return;
	}

699
700
	shift_mod = shift_cnt &  3;
	shift_nib = shift_cnt >> 2;
701
702

	/* check if any bits are lost, and set carry_flag if so */
703
	for (counter = 0; counter < shift_nib; ++counter) {
704
705
706
707
708
		if (val1[counter] != 0) {
			carry_flag = 1;
			break;
		}
	}
709
	if ((_val(val1[counter]) & ((1<<shift_mod)-1)) != 0)
710
		carry_flag = 1;
711

712
	/* shift digits to the right with offset, carry and all */
713
	buffer[0] = shrs_table[_val(val1[shift_nib])][shift_mod][0];
714
	for (counter = 1; counter < ((bitsize + 3) >> 2) - shift_nib; counter++) {
715
		shrs = shrs_table[_val(val1[counter + shift_nib])][shift_mod];
716
717
		buffer[counter]      = shrs[0];
		buffer[counter - 1] |= shrs[1];
718
719
720
	}

	/* the last digit is special in regard of signed/unsigned shift */
721
722
	bitoffset = bitsize & 3;
	msd = sign;  /* most significant digit */
723
724
725

	/* remove sign bits if mode was signed and this is an unsigned shift */
	if (!signed_shift && is_signed) {
726
		msd &= max_digit[bitoffset];
727
728
	}

729
	shrs = shrs_table[_val(msd)][shift_mod];
730
731

	/* signed shift and signed mode and negative value means all bits to the left are set */
732
	if (signed_shift && sign == SC_F) {
733
		buffer[counter] = shrs[0] | min_digit[bitoffset];
734
735
736
737
	} else {
		buffer[counter] = shrs[0];
	}

738
	if (counter > 0)
739
		buffer[counter - 1] |= shrs[1];
740
741
742
743
744

	/* fill with SC_F or SC_0 depending on sign */
	for (counter++; counter < calc_buffer_size; counter++) {
		buffer[counter] = sign;
	}
745
746
}

Michael Beck's avatar
Michael Beck committed
747
/**
748
 * Implements a Rotate Left.
Michael Beck's avatar
Michael Beck committed
749
750
 * positive: low-order -> high order, negative other direction
 */
751
752
static void do_rotl(const char *val1, char *buffer, long offset, int radius, unsigned is_signed)
{
753
	char *temp1, *temp2;
754
755
	temp1 = (char*) alloca(calc_buffer_size);
	temp2 = (char*) alloca(calc_buffer_size);
756
757
758
759
760
761
762
763
764

	offset = offset % radius;

	/* rotation by multiples of the type length is identity */
	if (offset == 0) {
		memmove(buffer, val1, calc_buffer_size);
		return;
	}

765
766
767
	do_shl(val1, temp1, offset, radius, is_signed);
	do_shr(val1, temp2, radius - offset, radius, is_signed, 0);
	do_bitor(temp1, temp2, buffer);
768
	carry_flag = 0; /* set by shr, but due to rot this is false */
769
770
771
772
773
}

/*****************************************************************************
 * public functions, declared in strcalc.h
 *****************************************************************************/
774
775
const void *sc_get_buffer(void)
{
776
	return (void*)calc_buffer;
777
778
}

779
780
int sc_get_buffer_length(void)
{
781
	return calc_buffer_size;
782
783
}

784
/**
785
 * Do sign extension if the mode is signed, otherwise to zero extension.
786
 */
787
788
void sign_extend(void *buffer, ir_mode *mode)
{
789
	char *calc_buffer = (char*) buffer;
790
791
792
	int bits          = get_mode_size_bits(mode) - 1;
	int nibble        = bits >> 2;
	int max           = max_digit[bits & 3];
793
794
795
796
797
798
799
800
	int i;

	if (mode_is_signed(mode)) {
		if (calc_buffer[nibble] > max) {
			/* sign bit is set, we need sign expansion */

			for (i = nibble + 1; i < calc_buffer_size; ++i)
				calc_buffer[i] = SC_F;
801
			calc_buffer[nibble] |= sex_digit[bits & 3];
802
803
804
805
		} else {
			/* set all bits to zero */
			for (i = nibble + 1; i < calc_buffer_size; ++i)
				calc_buffer[i] = SC_0;
806
			calc_buffer[nibble] &= zex_digit[bits & 3];
807
808
809
810
811
		}
	} else {
		/* do zero extension */
		for (i = nibble + 1; i < calc_buffer_size; ++i)
			calc_buffer[i] = SC_0;
812
		calc_buffer[nibble] &= zex_digit[bits & 3];
813
	}
814
815
}

816
817
818
/* we assume that '0'-'9', 'a'-'z' and 'A'-'Z' are a range.
 * The C-standard does theoretically allow otherwise. */
static inline void check_ascii(void)
819
{
820
	/* C standard guarantees that '0'-'9' is a range */
821
822
823
824
825
826
827
828
829
830
831
	assert('b'-'a' == 1
		&& 'c'-'a' == 2
		&& 'd'-'a' == 3
		&& 'e'-'a' == 4
		&& 'f'-'a' == 5);
	assert('B'-'A' == 1
		&& 'C'-'A' == 2
		&& 'D'-'A' == 3
		&& 'E'-'A' == 4
		&& 'F'-'A' == 5);
}
832

833
int sc_val_from_str(char sign, unsigned base, const char *str,
834
                    size_t len, void *buffer)
835
836
{
	char *sc_base, *val;
837

838
839
840
841
	assert(sign == -1 || sign == 1);
	assert(str != NULL);
	assert(len > 0);
	check_ascii();
842

843
	assert(base > 1 && base <= 16);
844
	sc_base = (char*) alloca(calc_buffer_size);
845
	sc_val_from_ulong(base, sc_base);
846

847
	val = (char*) alloca(calc_buffer_size);
848
849
	if (buffer == NULL)
		buffer = calc_buffer;
850
851
852
853
854
855

	CLEAR_BUFFER(buffer);
	CLEAR_BUFFER(val);

	/* BEGIN string evaluation, from left to right */
	while (len > 0) {
856
857
858
859
		char c = *str;
		unsigned v;
		if (c >= '0' && c <= '9')
			v = c - '0';
860
861
862
863
		else if (c >= 'A' && c <= 'F')
			v = c - 'A' + 10;
		else if (c >= 'a' && c <= 'f')
			v = c - 'a' + 10;
864
865
		else
			return 0;
866

867
868
869
		if (v >= base)
			return 0;
		val[0] = v;
870
871
872

		/* Radix conversion from base b to base B:
		 *  (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
873
		/* multiply current value with base */
874
		do_mul(sc_base, (const char*) buffer, (char*) buffer);
875
		/* add next digit to current value  */
876
		do_add(val, (const char*) buffer, (char*) buffer);
877
878
879
880
881
882

		/* get ready for the next letter */
		str++;
		len--;
	} /* while (len > 0 ) */

883
	if (sign < 0)
884
		do_negate((const char*) buffer, (char*) buffer);
885

886
	return 1;
887
888
}

889
890
void sc_val_from_long(long value, void *buffer)
{
891
892
	char *pos;
	char sign, is_minlong;
893

894
	if (buffer == NULL) buffer = calc_buffer;
895
	pos = (char*) buffer;
896

897
898
	sign = (value < 0);
	is_minlong = value == LONG_MIN;
899

900
901
902
903
904
905
906
	/* use absolute value, special treatment of MIN_LONG to avoid overflow */
	if (sign) {
		if (is_minlong)
			value = -(value+1);
		else
			value = -value;
	}
907

908
	CLEAR_BUFFER(buffer);
909

910
911
912
913
	while ((value != 0) && (pos < (char*)buffer + calc_buffer_size)) {
		*pos++ = _digit(value & 0xf);
		value >>= 4;
	}
914

915
916
	if (sign) {
		if (is_minlong)
917
			do_inc((const char*) buffer, (char*) buffer);
918

919
		do_negate((const char*) buffer, (char*) buffer);
920
	}
921
922
}

923
924
void sc_val_from_ulong(unsigned long value, void *buffer)
{
925
	unsigned char *pos;
926

927
	if (buffer == NULL) buffer = calc_buffer;
928
	pos = (unsigned char*) buffer;
929

930
931
932
933
	while (pos < (unsigned char *)buffer + calc_buffer_size) {
		*pos++ = (unsigned char)_digit(value & 0xf);
		value >>= 4;
	}
934
935
}

936
937
long sc_val_to_long(const void *val)
{
938
939
	int i;
	long l = 0;
940

941
942
943
944
	for (i = calc_buffer_size - 1; i >= 0; i--) {
		l = (l << 4) + _val(((char *)val)[i]);
	}
	return l;
945
946
}

947
948
void sc_min_from_bits(unsigned int num_bits, unsigned int sign, void *buffer)
{
949
950
	char *pos;
	int i, bits;
951

952
953
	if (buffer == NULL) buffer = calc_buffer;
	CLEAR_BUFFER(buffer);
954

955
	if (!sign) return;  /* unsigned means minimum is 0(zero) */
956

957
	pos = (char*) buffer;
958

959
960
961
	bits = num_bits - 1;
	for (i = 0; i < bits/4; i++)
		*pos++ = SC_0;
962

963
	*pos++ = min_digit[bits%4];
964

965
966
	for (i++; i <= calc_buffer_size - 1; i++)
		*pos++ = SC_F;
967
968
}

969
970
void sc_max_from_bits(unsigned int num_bits, unsigned int sign, void *buffer)
{
Michael Beck's avatar
Michael Beck committed
971
	char* pos;
972
	int i, bits;
973

974
975
	if (buffer == NULL) buffer = calc_buffer;
	CLEAR_BUFFER(buffer);
976
	pos = (char*) buffer;
977

978
979
980
	bits = num_bits - sign;
	for (i = 0; i < bits/4; i++)
		*pos++ = SC_F;
981

982
	*pos++ = max_digit[bits%4];
983

984
985
	for (i++; i <= calc_buffer_size - 1; i++)
		*pos++ = SC_0;
986
987
}

988
989
void sc_truncate(unsigned int num_bits, void *buffer)
{
990
	char *cbuffer = (char*) buffer;
991
992
	char *pos = cbuffer + (num_bits / 4);
	char *end = cbuffer + calc_buffer_size;
993
994
995

	assert(pos < end);

996
	switch (num_bits % 4) {
997
	case 0: /* nothing to do */ break;
998
999
1000
	case 1: *pos++ &= SC_1; break;
	case 2: *pos++ &= SC_3; break;
	case 3: *pos++ &= SC_7; break;
1001
1002
	}

1003
	for ( ; pos < end; ++pos)
1004
1005
1006
		*pos = SC_0;
}

1007
1008
int sc_comp(const void* value1, const void* value2)
{
1009
1010
1011
1012
1013
1014
	int counter = calc_buffer_size - 1;
	const char *val1 = (const char *)value1;
	const char *val2 = (const char *)value2;

	/* compare signs first:
	 * the loop below can only compare values of the same sign! */
1015
1016
	if (do_sign(val1) != do_sign(val2))
		return (do_sign(val1) == 1)?(1):(-1);
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028

	/* loop until two digits differ, the values are equal if there
	 * are no such two digits */
	while (val1[counter] == val2[counter]) {
		counter--;
		if (counter < 0) return 0;
	}

	/* the leftmost digit is the most significant, so this returns
	 * the correct result.
	 * This implies the digit enum is ordered */
	return (val1[counter] > val2[counter]) ? (1) : (-1);
1029
1030
}

1031
1032
int sc_get_highest_set_bit(const void *value)
{
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
	const char *val = (const char*)value;
	int high, counter;

	high = calc_buffer_size * 4 - 1;

	for (counter = calc_buffer_size-1; counter >= 0; counter--) {
		if (val[counter] == SC_0)
			high -= 4;
		else {
			if (val[counter] > SC_7) return high;
			else if (val[counter] > SC_3) return high - 1;
			else if (val[counter] > SC_1) return high - 2;
			else return high - 3;
		}
	}
	return high;
Matthias Heil's avatar
Matthias Heil committed
1049
1050
}

1051
1052
int sc_get_lowest_set_bit(const void *value)
{
1053
1054
1055
1056
1057
	const char *val = (const char*)value;
	int low, counter;

	low = 0;
	for (counter = 0; counter