strcalc.c 35.3 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

Michael Beck's avatar
Michael Beck committed
6
7
8
9
10
/**
 * @file
 * @brief    Provides basic mathematical operations on values represented as strings.
 * @date     2003
 * @author   Mathias Heil
11
 */
12
#include <stdlib.h>
13
14
15
16
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <limits.h>
17

Michael Beck's avatar
Michael Beck committed
18
#include "strcalc.h"
Michael Beck's avatar
Michael Beck committed
19
#include "xmalloc.h"
20
#include "error.h"
Michael Beck's avatar
Michael Beck committed
21

22
/*
23
 * local definitions and macros
24
 */
25
26
27
28
#define SC_BITS      4
#define SC_RESULT(x) ((x) & ((1U << SC_BITS) - 1U))
#define SC_CARRY(x)  ((unsigned)(x) >> SC_BITS)

Michael Beck's avatar
Michael Beck committed
29
#define CLEAR_BUFFER(b) assert(b); memset(b, SC_0, calc_buffer_size)
30
#define SHIFT(count) (SC_1 << (count))
31
32
#define _val(a) ((a)-SC_0)
#define _digit(a) ((a)+SC_0)
33
#define _bitisset(digit, pos) (((digit) & SHIFT(pos)) != SC_0)
34

35
/*
36
 * private variables
37
 */
Matthias Heil's avatar
Matthias Heil committed
38
39
static char *calc_buffer = NULL;    /* buffer holding all results */
static char *output_buffer = NULL;  /* buffer for output */
Michael Beck's avatar
Michael Beck committed
40
41
42
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 */
43

Matthias Braun's avatar
Matthias Braun committed
44
static bool carry_flag;             /**< some computation set the carry_flag:
Michael Beck's avatar
Michael Beck committed
45
                                         - right shift if bits were lost due to shifting
Michael Beck's avatar
Michael Beck committed
46
                                         - division if there was a remainder
Michael Beck's avatar
Michael Beck committed
47
48
                                         However, the meaning of carry is machine dependent
                                         and often defined in other ways! */
49

50
static const char sex_digit[4] = { SC_E, SC_C, SC_8, SC_0 };
51
static const char zex_digit[4] = { SC_1, SC_3, SC_7, SC_F };
52
53
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 };
54

55
static char const shrs_table[16][4][2] = {
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
                       { {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} }
                                   };
73

Michael Beck's avatar
Michael Beck committed
74
/** converting a digit to a binary string */
75
static char const *const binary_table[] = {
76
77
	"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
	"1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"
78
79
};

80
81
82
83
/*****************************************************************************
 * private functions
 *****************************************************************************/

Michael Beck's avatar
Michael Beck committed
84
85
86
/**
 * implements the bitwise NOT operation
 */
87
88
static void do_bitnot(const char *val, char *buffer)
{
Matthias Braun's avatar
Matthias Braun committed
89
	for (int counter = 0; counter<calc_buffer_size; counter++)
90
		buffer[counter] = val[counter] ^ SC_F;
91
92
}

Michael Beck's avatar
Michael Beck committed
93
94
95
/**
 * implements the bitwise OR operation
 */
96
97
static void do_bitor(const char *val1, const char *val2, char *buffer)
{
Matthias Braun's avatar
Matthias Braun committed
98
	for (int counter = 0; counter<calc_buffer_size; counter++)
99
		buffer[counter] = val1[counter] | val2[counter];
100
101
}

Michael Beck's avatar
Michael Beck committed
102
103
104
/**
 * implements the bitwise eXclusive OR operation
 */
105
106
static void do_bitxor(const char *val1, const char *val2, char *buffer)
{
Matthias Braun's avatar
Matthias Braun committed
107
	for (int counter = 0; counter<calc_buffer_size; counter++)
108
		buffer[counter] = val1[counter] ^ val2[counter];
109
110
}

Michael Beck's avatar
Michael Beck committed
111
112
113
/**
 * implements the bitwise AND operation
 */
114
115
static void do_bitand(const char *val1, const char *val2, char *buffer)
{
Matthias Braun's avatar
Matthias Braun committed
116
	for (int counter = 0; counter<calc_buffer_size; counter++)
117
		buffer[counter] = val1[counter] & val2[counter];
118
119
}

120
121
122
123
124
/**
 * implements the bitwise AND not operation
 */
static void do_bitandnot(const char *val1, const char *val2, char *buffer)
{
Matthias Braun's avatar
Matthias Braun committed
125
	for (int counter = 0; counter < calc_buffer_size; ++counter)
126
127
128
		buffer[counter] = val1[counter] & (SC_F ^ val2[counter]);
}

Michael Beck's avatar
Michael Beck committed
129
130
131
132
133
134
/**
 * 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
 */
135
136
static int do_sign(const char *val)
{
137
	return (val[calc_buffer_size-1] <= SC_7) ? (1) : (-1);
138
139
}

Michael Beck's avatar
Michael Beck committed
140
/**
Michael Beck's avatar
Michael Beck committed
141
142
 * returns non-zero if bit at position pos is set
 */
143
144
static int do_bit(const char *val, int pos)
{
145
146
	int bit    = pos & 3;
	int nibble = pos >> 2;
Michael Beck's avatar
Michael Beck committed
147

148
	return _bitisset(val[nibble], bit);
Michael Beck's avatar
Michael Beck committed
149
150
}

Michael Beck's avatar
Michael Beck committed
151
152
153
/**
 * Implements a fast ADD + 1
 */
154
155
static void do_inc(const char *val, char *buffer)
{
156
157
158
159
160
161
162
163
	int counter = 0;

	while (counter++ < calc_buffer_size) {
		if (*val == SC_F) {
			*buffer++ = SC_0;
			val++;
		} else {
			/* No carry here, *val != SC_F */
164
			*buffer = *val + SC_1;
165
166
167
168
169
			return;
		}
	}
	/* here a carry could be lost, this is intended because this should
	 * happen only when a value changes sign. */
170
171
}

Michael Beck's avatar
Michael Beck committed
172
173
174
/**
 * Implements a unary MINUS
 */
175
176
static void do_negate(const char *val, char *buffer)
{
177
178
	do_bitnot(val, buffer);
	do_inc(buffer, buffer);
179
180
}

Michael Beck's avatar
Michael Beck committed
181
182
183
184
/**
 * Implements a binary ADD
 *
 * @todo The implementation of carry is wrong, as it is the
Michael Beck's avatar
Michael Beck committed
185
 *       calc_buffer_size carry, not the mode depending
Michael Beck's avatar
Michael Beck committed
186
 */
187
188
static void do_add(const char *val1, const char *val2, char *buffer)
{
189
190
191
192
193
	unsigned carry = SC_0;
	for (int counter = 0; counter < calc_buffer_size; ++counter) {
		unsigned const sum = val1[counter] + val2[counter] + carry;
		buffer[counter] = SC_RESULT(sum);
		carry           = SC_CARRY(sum);
194
195
	}
	carry_flag = carry != SC_0;
196
197
}

Michael Beck's avatar
Michael Beck committed
198
199
200
/**
 * Implements a binary SUB
 */
201
202
static void do_sub(const char *val1, const char *val2, char *buffer)
{
203
	char *temp_buffer = (char*) alloca(calc_buffer_size); /* intermediate buffer to hold -val2 */
Michael Beck's avatar
Michael Beck committed
204

205
206
	do_negate(val2, temp_buffer);
	do_add(val1, temp_buffer, buffer);
Michael Beck's avatar
Michael Beck committed
207
208
209
210
211
}

/**
 * Implements a binary MUL
 */
212
213
static void do_mul(const char *val1, const char *val2, char *buffer)
{
Matthias Braun's avatar
Matthias Braun committed
214
215
216
	char *temp_buffer = (char*) alloca(calc_buffer_size);
	char *neg_val1    = (char*) alloca(calc_buffer_size);
	char *neg_val2    = (char*) alloca(calc_buffer_size);
217

218
	/* init result buffer to zeros */
219
220
221
222
	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       */
Matthias Braun's avatar
Matthias Braun committed
223
	char sign = 0;
224
225
	if (do_sign(val1) == -1) {
		do_negate(val1, neg_val1);
226
227
228
		val1 = neg_val1;
		sign ^= 1;
	}
229
230
	if (do_sign(val2) == -1) {
		do_negate(val2, neg_val2);
231
232
233
234
		val2 = neg_val2;
		sign ^= 1;
	}

Matthias Braun's avatar
Matthias Braun committed
235
	for (int c_outer = 0; c_outer < max_value_size; c_outer++) {
236
		if (val2[c_outer] != SC_0) {
237
			unsigned carry = SC_0; /* container for carries */
Matthias Braun's avatar
Matthias Braun committed
238
239
240
241
242
243
			for (int 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
				 */
244
245

				/* multiplicate the two digits */
246
				unsigned const mul = val1[c_inner] * val2[c_outer];
247
				/* add old value to result of multiplication and the carry */
Matthias Braun's avatar
Matthias Braun committed
248
249
250
251
252
253
254
255
256
257
258
259
260
				unsigned const sum = temp_buffer[c_inner+c_outer] + mul + 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
				 */
261
262
				temp_buffer[c_inner + c_outer] = SC_RESULT(sum);
				carry                          = SC_CARRY(sum);
263
264
265
266
267
268
269
270
271
			}

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

	if (sign)
272
		do_negate(temp_buffer, buffer);
273
274
	else
		memcpy(buffer, temp_buffer, calc_buffer_size);
275
276
}

Michael Beck's avatar
Michael Beck committed
277
278
279
/**
 * Shift the buffer to left and add a 4 bit digit
 */
280
281
static void do_push(const char digit, char *buffer)
{
Matthias Braun's avatar
Matthias Braun committed
282
	for (int counter = calc_buffer_size - 2; counter >= 0; counter--) {
283
284
285
		buffer[counter+1] = buffer[counter];
	}
	buffer[0] = digit;
286
287
}

Michael Beck's avatar
Michael Beck committed
288
289
290
291
292
/**
 * Implements truncating integer division and remainder.
 *
 * Note: This is MOST slow
 */
Matthias Braun's avatar
Matthias Braun committed
293
294
static void do_divmod(const char *rDividend, const char *divisor, char *quot,
                      char *rem)
295
{
296
297
298
299
300
	/* 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) */
301
	assert(sc_comp(divisor, quot) != ir_relation_equal && "division by zero!");
302
303

	/* if the dividend is zero result is zero (quot is zero) */
Matthias Braun's avatar
Matthias Braun committed
304
	const char *dividend = rDividend;
305
	if (sc_comp(dividend, quot) == ir_relation_equal)
306
307
		return;

Matthias Braun's avatar
Matthias Braun committed
308
309
310
	char  div_sign = 0;
	char  rem_sign = 0;
	char *neg_val1 = (char*) alloca(calc_buffer_size);
311
312
	if (do_sign(dividend) == -1) {
		do_negate(dividend, neg_val1);
313
314
315
316
317
		div_sign ^= 1;
		rem_sign ^= 1;
		dividend = neg_val1;
	}

Matthias Braun's avatar
Matthias Braun committed
318
	char *neg_val2 = (char*) alloca(calc_buffer_size);
319
	do_negate(divisor, neg_val2);
Matthias Braun's avatar
Matthias Braun committed
320
	const char *minus_divisor;
321
	if (do_sign(divisor) == -1) {
322
323
324
		div_sign ^= 1;
		minus_divisor = divisor;
		divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
325
	} else {
326
		minus_divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
327
	}
328
329
330
331

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

336
	case ir_relation_less: /* dividend < divisor */
337
		memcpy(rem, dividend, calc_buffer_size);
338
339
340
341
342
343
		goto end;

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

Matthias Braun's avatar
Matthias Braun committed
344
	for (int c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) {
345
346
		do_push(dividend[c_dividend], rem);
		do_push(SC_0, quot);
347

Matthias Braun's avatar
Matthias Braun committed
348
349
		if (sc_comp(rem, divisor) != ir_relation_less) {
			/* remainder >= divisor */
350
351
			/* subtract until the remainder becomes negative, this should
			 * be faster than comparing remainder with divisor  */
352
			do_add(rem, minus_divisor, rem);
353

354
			while (do_sign(rem) == 1) {
355
				quot[0] = SC_RESULT(quot[0] + SC_1); /* TODO can this generate carry or is masking redundant? */
356
				do_add(rem, minus_divisor, rem);
357
358
359
			}

			/* subtracted one too much */
360
			do_add(rem, divisor, rem);
361
362
363
364
		}
	}
end:
	/* sets carry if remainder is non-zero ??? */
Matthias Braun's avatar
Matthias Braun committed
365
	carry_flag = !sc_is_zero(rem, calc_buffer_size);
366
367

	if (div_sign)
368
		do_negate(quot, quot);
369
370

	if (rem_sign)
371
		do_negate(rem, rem);
372
373
}

Michael Beck's avatar
Michael Beck committed
374
375
376
377
378
379
/**
 * Implements a Shift Left, which can either preserve the sign bit
 * or not.
 *
 * @todo Assertions seems to be wrong
 */
Matthias Braun's avatar
Matthias Braun committed
380
static void do_shl(const char *val1, char *buffer, long shift_cnt, int bitsize,
381
                   bool is_signed)
382
{
383
	assert((shift_cnt >= 0) || (0 && "negative leftshift"));
384
385
386
	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"));
387
388

	/* if shifting far enough the result is zero */
389
	if (shift_cnt >= bitsize) {
390
391
392
393
		memset(buffer, SC_0, calc_buffer_size);
		return;
	}

394
	unsigned const shift = shift_cnt % SC_BITS;
395
	shift_cnt = shift_cnt / 4;
396
397
398

	/* shift the single digits some bytes (offset) and some bits (table)
	 * to the left */
399
	unsigned carry = SC_0;
Matthias Braun's avatar
Matthias Braun committed
400
	for (int counter = 0; counter < bitsize/4 - shift_cnt; counter++) {
401
402
403
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
		carry = SC_CARRY(shl);
404
	}
Matthias Braun's avatar
Matthias Braun committed
405
406
	int counter   = bitsize/4 - shift_cnt;
	int bitoffset = 0;
407
	if (bitsize%4 > 0) {
408
409
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
410
411
412
413
414
415
		bitoffset = counter;
	} else {
		bitoffset = counter - 1;
	}

	/* fill with zeroes */
Matthias Braun's avatar
Matthias Braun committed
416
	for (int counter = 0; counter < shift_cnt; counter++)
417
418
419
		buffer[counter] = SC_0;

	/* if the mode was signed, change sign when the mode's msb is now 1 */
420
421
422
	shift_cnt = bitoffset + shift_cnt;
	bitoffset = (bitsize-1) % 4;
	if (is_signed && _bitisset(buffer[shift_cnt], bitoffset)) {
423
		/* this sets the upper bits of the leftmost digit */
424
		buffer[shift_cnt] |= min_digit[bitoffset];
Matthias Braun's avatar
Matthias Braun committed
425
		for (int counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
426
427
			buffer[counter] = SC_F;
		}
428
	} else if (is_signed && !_bitisset(buffer[shift_cnt], bitoffset)) {
429
		/* this clears the upper bits of the leftmost digit */
430
		buffer[shift_cnt] &= max_digit[bitoffset];
Matthias Braun's avatar
Matthias Braun committed
431
		for (int counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
432
433
434
			buffer[counter] = SC_0;
		}
	}
435
436
}

Michael Beck's avatar
Michael Beck committed
437
438
439
440
/**
 * Implements a Shift Right, which can either preserve the sign bit
 * or not.
 *
441
442
 * @param bitsize   bitsize of the value to be shifted
 *
Michael Beck's avatar
Michael Beck committed
443
444
 * @todo Assertions seems to be wrong
 */
Matthias Braun's avatar
Matthias Braun committed
445
static void do_shr(const char *val1, char *buffer, long shift_cnt, int bitsize,
446
                   bool is_signed, int signed_shift)
447
{
448
	assert((shift_cnt >= 0) || (0 && "negative rightshift"));
449
450
	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"));
451

Matthias Braun's avatar
Matthias Braun committed
452
	char sign = signed_shift && do_bit(val1, bitsize - 1) ? SC_F : SC_0;
453
454

	/* if shifting far enough the result is either 0 or -1 */
455
	if (shift_cnt >= bitsize) {
Matthias Braun's avatar
Matthias Braun committed
456
		if (!sc_is_zero(val1, calc_buffer_size)) {
Matthias Braun's avatar
Matthias Braun committed
457
			carry_flag = true;
458
459
460
461
462
		}
		memset(buffer, sign, calc_buffer_size);
		return;
	}

Matthias Braun's avatar
Matthias Braun committed
463
464
	int shift_mod = shift_cnt &  3;
	int shift_nib = shift_cnt >> 2;
465
466

	/* check if any bits are lost, and set carry_flag if so */
Matthias Braun's avatar
Matthias Braun committed
467
	for (int counter = 0; counter < shift_nib; ++counter) {
468
		if (val1[counter] != 0) {
Matthias Braun's avatar
Matthias Braun committed
469
			carry_flag = true;
470
471
472
			break;
		}
	}
Matthias Braun's avatar
Matthias Braun committed
473
	if ((_val(val1[shift_nib]) & ((1<<shift_mod)-1)) != 0)
Matthias Braun's avatar
Matthias Braun committed
474
		carry_flag = true;
475

476
	/* shift digits to the right with offset, carry and all */
477
	buffer[0] = shrs_table[_val(val1[shift_nib])][shift_mod][0];
Matthias Braun's avatar
Matthias Braun committed
478
	int counter;
479
	for (counter = 1; counter < ((bitsize + 3) >> 2) - shift_nib; counter++) {
Matthias Braun's avatar
Matthias Braun committed
480
		const char *shrs = shrs_table[_val(val1[counter + shift_nib])][shift_mod];
481
482
		buffer[counter]      = shrs[0];
		buffer[counter - 1] |= shrs[1];
483
484
485
	}

	/* the last digit is special in regard of signed/unsigned shift */
Matthias Braun's avatar
Matthias Braun committed
486
487
	int bitoffset = bitsize & 3;
	char msd = sign;  /* most significant digit */
488
489
490

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

Matthias Braun's avatar
Matthias Braun committed
494
	const char *shrs = shrs_table[_val(msd)][shift_mod];
495
496

	/* signed shift and signed mode and negative value means all bits to the left are set */
497
	if (signed_shift && sign == SC_F) {
498
		buffer[counter] = shrs[0] | min_digit[bitoffset];
499
500
501
502
	} else {
		buffer[counter] = shrs[0];
	}

503
	if (counter > 0)
504
		buffer[counter - 1] |= shrs[1];
505
506
507
508
509

	/* fill with SC_F or SC_0 depending on sign */
	for (counter++; counter < calc_buffer_size; counter++) {
		buffer[counter] = sign;
	}
510
511
512
513
514
}

/*****************************************************************************
 * public functions, declared in strcalc.h
 *****************************************************************************/
515
516
const void *sc_get_buffer(void)
{
517
	return (void*)calc_buffer;
518
519
}

520
521
int sc_get_buffer_length(void)
{
522
	return calc_buffer_size;
523
524
}

525
void sign_extend(void *buffer, unsigned from_bits, bool is_signed)
526
{
Matthias Braun's avatar
Matthias Braun committed
527
	char *calc_buffer = (char*)buffer;
528
	int bits          = from_bits - 1;
529
	int nibble        = bits >> 2;
530

531
	if (is_signed) {
Matthias Braun's avatar
Matthias Braun committed
532
		int max = max_digit[bits & 3];
533
534
535
		if (calc_buffer[nibble] > max) {
			/* sign bit is set, we need sign expansion */

Matthias Braun's avatar
Matthias Braun committed
536
			for (int i = nibble + 1; i < calc_buffer_size; ++i)
537
				calc_buffer[i] = SC_F;
538
			calc_buffer[nibble] |= sex_digit[bits & 3];
539
540
		} else {
			/* set all bits to zero */
Matthias Braun's avatar
Matthias Braun committed
541
			for (int i = nibble + 1; i < calc_buffer_size; ++i)
542
				calc_buffer[i] = SC_0;
543
			calc_buffer[nibble] &= zex_digit[bits & 3];
544
545
546
		}
	} else {
		/* do zero extension */
Matthias Braun's avatar
Matthias Braun committed
547
		for (int i = nibble + 1; i < calc_buffer_size; ++i)
548
			calc_buffer[i] = SC_0;
549
		calc_buffer[nibble] &= zex_digit[bits & 3];
550
	}
551
552
}

Matthias Braun's avatar
Matthias Braun committed
553
/* ensure that our source character set conforms to ASCII for a-f, A-F, 0-9 */
554
static inline void check_ascii(void)
555
{
Matthias Braun's avatar
Matthias Braun committed
556
557
558
559
	assert((('a'-97) | ('b'-98) | ('c'-99) | ('d'-100) | ('e'-101) | ('f'-102)
	       |('A'-65) | ('B'-66) | ('C'-67) | ('D'- 68) | ('E'- 69) | ('F'- 70)
	       |('0'-48) | ('1'-49) | ('2'-50) | ('3'- 51) | ('4'- 52)
	       |('5'-53) | ('6'-54) | ('7'-55) | ('8'- 56) | ('9'- 57)) == 0);
560
}
561

562
563
bool sc_val_from_str(char sign, unsigned base, const char *str, size_t len,
                     void *buffer)
564
565
566
567
568
{
	assert(sign == -1 || sign == 1);
	assert(str != NULL);
	assert(len > 0);
	check_ascii();
569

570
	assert(base > 1 && base <= 16);
Matthias Braun's avatar
Matthias Braun committed
571
	char *sc_base = (char*) alloca(calc_buffer_size);
572
	sc_val_from_ulong(base, sc_base);
573

Matthias Braun's avatar
Matthias Braun committed
574
	char *val = (char*) alloca(calc_buffer_size);
575
576
	if (buffer == NULL)
		buffer = calc_buffer;
577
578
579
580
581
582

	CLEAR_BUFFER(buffer);
	CLEAR_BUFFER(val);

	/* BEGIN string evaluation, from left to right */
	while (len > 0) {
583
584
585
586
		char c = *str;
		unsigned v;
		if (c >= '0' && c <= '9')
			v = c - '0';
587
588
589
590
		else if (c >= 'A' && c <= 'F')
			v = c - 'A' + 10;
		else if (c >= 'a' && c <= 'f')
			v = c - 'a' + 10;
591
		else
592
			return false;
593

594
		if (v >= base)
595
			return false;
596
		val[0] = v;
597
598
599

		/* Radix conversion from base b to base B:
		 *  (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
600
		/* multiply current value with base */
601
		do_mul(sc_base, (const char*) buffer, (char*) buffer);
602
		/* add next digit to current value  */
603
		do_add(val, (const char*) buffer, (char*) buffer);
604
605
606
607

		/* get ready for the next letter */
		str++;
		len--;
608
	}
609

610
	if (sign < 0)
611
		do_negate((const char*) buffer, (char*) buffer);
612

613
	return true;
614
615
}

616
617
void sc_val_from_long(long value, void *buffer)
{
618
	if (buffer == NULL) buffer = calc_buffer;
Matthias Braun's avatar
Matthias Braun committed
619
	char *pos = (char*) buffer;
620

Matthias Braun's avatar
Matthias Braun committed
621
622
	char sign       = (value < 0);
	char is_minlong = value == LONG_MIN;
623

624
625
626
627
628
629
630
	/* use absolute value, special treatment of MIN_LONG to avoid overflow */
	if (sign) {
		if (is_minlong)
			value = -(value+1);
		else
			value = -value;
	}
631

632
	CLEAR_BUFFER(buffer);
633

634
635
636
637
	while ((value != 0) && (pos < (char*)buffer + calc_buffer_size)) {
		*pos++ = _digit(value & 0xf);
		value >>= 4;
	}
638

639
640
	if (sign) {
		if (is_minlong)
641
			do_inc((const char*) buffer, (char*) buffer);
642

643
		do_negate((const char*) buffer, (char*) buffer);
644
	}
645
646
}

647
648
void sc_val_from_ulong(unsigned long value, void *buffer)
{
649
	if (buffer == NULL) buffer = calc_buffer;
Matthias Braun's avatar
Matthias Braun committed
650
	unsigned char *pos = (unsigned char*) buffer;
651

652
653
654
655
	while (pos < (unsigned char *)buffer + calc_buffer_size) {
		*pos++ = (unsigned char)_digit(value & 0xf);
		value >>= 4;
	}
656
657
}

658
659
long sc_val_to_long(const void *val)
{
Andreas Zwinkau's avatar
Andreas Zwinkau committed
660
661
662
663
	unsigned long l = 0;
	int max_buffer_index = sizeof(long)*8/SC_BITS;
	for (size_t i = max_buffer_index; i-- > 0;) {
		assert(l <= (ULONG_MAX>>4) && "signed shift overflow");
664
665
666
		l = (l << 4) + _val(((char *)val)[i]);
	}
	return l;
667
668
}

669
670
671
672
673
674
uint64_t sc_val_to_uint64(const void *val)
{
	uint64_t res = 0;
	for (int i = calc_buffer_size - 1; i >= 0; i--) {
		res = (res << 4) + _val(((char*)val)[i]);
	}
Manuel Mohr's avatar
Manuel Mohr committed
675
	return res;
676
677
}

678
void sc_min_from_bits(unsigned int num_bits, bool sign, void *buffer)
679
{
680
681
	if (buffer == NULL) buffer = calc_buffer;
	CLEAR_BUFFER(buffer);
682

683
	if (!sign) return;  /* unsigned means minimum is 0(zero) */
684

Matthias Braun's avatar
Matthias Braun committed
685
	char *pos = (char*) buffer;
686

Matthias Braun's avatar
Matthias Braun committed
687
688
	int bits = num_bits - 1;
	int i;
689
690
	for (i = 0; i < bits/4; i++)
		*pos++ = SC_0;
691

692
	*pos++ = min_digit[bits%4];
693

694
695
	for (i++; i <= calc_buffer_size - 1; i++)
		*pos++ = SC_F;
696
697
}

698
void sc_max_from_bits(unsigned int num_bits, bool sign, void *buffer)
699
{
700
701
	if (buffer == NULL) buffer = calc_buffer;
	CLEAR_BUFFER(buffer);
Matthias Braun's avatar
Matthias Braun committed
702
	char *pos = (char*) buffer;
703

Matthias Braun's avatar
Matthias Braun committed
704
705
706
	int bits = num_bits - sign;
	int i    = 0;
	for ( ; i < bits/4; i++)
707
		*pos++ = SC_F;
708

709
	*pos++ = max_digit[bits%4];
710

711
712
	for (i++; i <= calc_buffer_size - 1; i++)
		*pos++ = SC_0;
713
714
}

715
716
void sc_truncate(unsigned int num_bits, void *buffer)
{
717
	char *cbuffer = (char*) buffer;
718
719
	char *pos = cbuffer + (num_bits / 4);
	char *end = cbuffer + calc_buffer_size;
720
721
722

	assert(pos < end);

723
	switch (num_bits % 4) {
724
	case 0: /* nothing to do */ break;
725
726
727
	case 1: *pos++ &= SC_1; break;
	case 2: *pos++ &= SC_3; break;
	case 3: *pos++ &= SC_7; break;
728
729
	}

730
	for ( ; pos < end; ++pos)
731
732
733
		*pos = SC_0;
}

734
ir_relation sc_comp(void const* const value1, void const* const value2)
735
{
736
737
738
739
740
741
	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! */
742
	if (do_sign(val1) != do_sign(val2))
743
		return do_sign(val1) == 1 ? ir_relation_greater : ir_relation_less;
744
745
746
747
748

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

	/* the leftmost digit is the most significant, so this returns
	 * the correct result.
	 * This implies the digit enum is ordered */
755
	return val1[counter] > val2[counter] ? ir_relation_greater : ir_relation_less;
756
757
}

758
759
int sc_get_highest_set_bit(const void *value)
{
Matthias Braun's avatar
Matthias Braun committed
760
761
762
	const char *val  = (const char*)value;
	int         high = calc_buffer_size * 4 - 1;
	for (int counter = calc_buffer_size-1; counter >= 0; counter--) {
763
764
765
766
767
768
769
770
771
772
		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
773
774
}

775
776
int sc_get_lowest_set_bit(const void *value)
{
777
	const char *val = (const char*)value;
Matthias Braun's avatar
Matthias Braun committed
778
779
	int         low = 0;
	for (int counter = 0; counter < calc_buffer_size; counter++) {
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
		switch (val[counter]) {
		case SC_1:
		case SC_3:
		case SC_5:
		case SC_7:
		case SC_9:
		case SC_B:
		case SC_D:
		case SC_F:
			return low;
		case SC_2:
		case SC_6:
		case SC_A:
		case SC_E:
			return low + 1;
		case SC_4:
		case SC_C:
			return low + 2;
		case SC_8:
			return low + 3;
		default:
801
802
803
804
			low += 4;
		}
	}
	return -1;
Matthias Heil's avatar
Matthias Heil committed
805
806
}

807
808
int sc_get_bit_at(const void *value, unsigned pos)
{
Matthias Braun's avatar
Matthias Braun committed
809
810
	const char *val    = (const char*) value;
	unsigned    nibble = pos >> 2;
811

812
	return (val[nibble] & SHIFT(pos & 3)) != SC_0;
813
814
}

815
816
void sc_set_bit_at(void *value, unsigned pos)
{
Matthias Braun's avatar
Matthias Braun committed
817
	char    *val    = (char*) value;
818
819
	unsigned nibble = pos >> 2;

820
	val[nibble] |= SHIFT(pos & 3);
821
822
}

Matthias Braun's avatar
Matthias Braun committed
823
824
825
826
827
828
829
830
831
void sc_clear_bit_at(void *value, unsigned pos)
{
	char    *val    = (char*) value;
	unsigned nibble = pos >> 2;

	val[nibble] &= ~SHIFT(pos & 3);
}

bool sc_is_zero(const void *value, unsigned bits)
832
{
833
	const char* val = (const char *)value;
Matthias Braun's avatar
Matthias Braun committed
834
835
836
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
		if (val[i] != SC_0)
837
			return false;
838
	}
Matthias Braun's avatar
Matthias Braun committed
839
840
841
842
843
844
845
846
847
848
849
850
851
852
	char mask = max_digit[bits%SC_BITS];
	return mask == 0 || (val[i] & mask) == SC_0;
}

bool sc_is_all_one(const void *value, unsigned bits)
{
	const char* val = (const char*)value;
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
		if (val[i] != SC_F)
			return false;
	}
	char mask = max_digit[bits%SC_BITS];
	return mask == 0 || (val[i] & mask) == mask;
853
854
}

855
bool sc_is_negative(const void *value)
856
{
857
	return do_sign((const char*) value) == -1;
858
859
}

860
861
unsigned char sc_sub_bits(const void *value, int len, unsigned byte_ofs)
{
862
	/* the current scheme uses one byte to store a nibble */
Matthias Braun's avatar
Matthias Braun committed
863
	int nibble_ofs = 2 * byte_ofs;
864
	if (4 * nibble_ofs >= len)
865
		return 0;
866

Matthias Braun's avatar
Matthias Braun committed
867
868
	const char   *val = (const char *)value;
	unsigned char res = _val(val[nibble_ofs]);
869
	if (len > 4 * (nibble_ofs + 1))
870
		res |= _val(val[nibble_ofs + 1]) << 4;
871

872
	/* kick bits outsize */
873
874
	if (len - 8 * byte_ofs < 8) {
		res &= (1 << (len - 8 * byte_ofs)) - 1;
875
	}
876
	return res;
877
878
}

Matthias Braun's avatar
Matthias Braun committed
879
880
881
882
883
884
885
886
void sc_val_from_bytes(unsigned char const *const bytes, size_t n_bytes,
                       bool big_endian, void *buffer)
{
	assert(n_bytes <= (size_t)calc_buffer_size);

	if (buffer == NULL)
		buffer = calc_buffer;
	char *p = (char*)buffer;
887
	assert(SC_BITS == 4);
Matthias Braun's avatar
Matthias Braun committed
888
	if (big_endian) {
889
		for (unsigned char const *bp = bytes+n_bytes-1; bp >= bytes; --bp) {