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

Michael Beck's avatar
Michael Beck committed
19
#include "strcalc.h"
Michael Beck's avatar
Michael Beck committed
20
#include "xmalloc.h"
21
#include "error.h"
Matthias Braun's avatar
Matthias Braun committed
22
#include "bitfiddle.h"
Michael Beck's avatar
Michael Beck committed
23

24
25
26
27
#define SC_BITS      4
#define SC_RESULT(x) ((x) & ((1U << SC_BITS) - 1U))
#define SC_CARRY(x)  ((unsigned)(x) >> SC_BITS)

28
29
#define CLEAR_BUFFER(b) memset(b, 0, calc_buffer_size)
#define _bitisset(digit, pos) (((digit) & (1 << (pos))) != 0)
30

31
static sc_word *calc_buffer = NULL;    /* buffer holding all results */
Matthias Heil's avatar
Matthias Heil committed
32
static char *output_buffer = NULL;  /* buffer for output */
Michael Beck's avatar
Michael Beck committed
33
34
35
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 */
36

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

43
44
45
46
static const sc_word sex_digit[4] = { 14, 12,  8,  0 };
static const sc_word zex_digit[4] = {  1,  3,  7, 15 };
static const sc_word max_digit[4] = {  0,  1,  3,  7 };
static const sc_word min_digit[4] = { 15, 14, 12,  8 };
47

48
static const sc_word shrs_table[16][4][2] = {
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
	{ { 0, 0}, {0, 0}, {0,  0}, {0,  0} },
	{ { 1, 0}, {0, 8}, {0,  4}, {0,  2} },
	{ { 2, 0}, {1, 0}, {0,  8}, {0,  4} },
	{ { 3, 0}, {1, 8}, {0, 12}, {0,  6} },
	{ { 4, 0}, {2, 0}, {1,  0}, {0,  8} },
	{ { 5, 0}, {2, 8}, {1,  4}, {0, 10} },
	{ { 6, 0}, {3, 0}, {1,  8}, {0, 12} },
	{ { 7, 0}, {3, 8}, {1, 12}, {0, 14} },
	{ { 8, 0}, {4, 0}, {2,  0}, {1,  0} },
	{ { 9, 0}, {4, 8}, {2,  4}, {1,  2} },
	{ {10, 0}, {5, 0}, {2,  8}, {1,  4} },
	{ {11, 0}, {5, 8}, {2, 12}, {1,  6} },
	{ {12, 0}, {6, 0}, {3,  0}, {1,  8} },
	{ {13, 0}, {6, 8}, {3,  4}, {1, 10} },
	{ {14, 0}, {7, 0}, {3,  8}, {1, 12} },
	{ {15, 0}, {7, 8}, {3, 12}, {1, 14} }
};
66

Michael Beck's avatar
Michael Beck committed
67
/** converting a digit to a binary string */
68
static char const *const binary_table[] = {
69
70
	"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
	"1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"
71
72
};

Michael Beck's avatar
Michael Beck committed
73
74
75
/**
 * implements the bitwise NOT operation
 */
76
static void do_bitnot(const sc_word *val, sc_word *buffer)
77
{
Matthias Braun's avatar
Matthias Braun committed
78
	for (int counter = 0; counter<calc_buffer_size; counter++)
79
		buffer[counter] = val[counter] ^ 0xF;
80
81
}

Michael Beck's avatar
Michael Beck committed
82
83
84
/**
 * implements the bitwise OR operation
 */
85
static void do_bitor(const sc_word *val1, const sc_word *val2, sc_word *buffer)
86
{
Matthias Braun's avatar
Matthias Braun committed
87
	for (int counter = 0; counter<calc_buffer_size; counter++)
88
		buffer[counter] = val1[counter] | val2[counter];
89
90
}

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

Michael Beck's avatar
Michael Beck committed
100
101
102
/**
 * implements the bitwise AND operation
 */
103
static void do_bitand(const sc_word *val1, const sc_word *val2, sc_word *buffer)
104
{
Matthias Braun's avatar
Matthias Braun committed
105
	for (int counter = 0; counter<calc_buffer_size; counter++)
106
		buffer[counter] = val1[counter] & val2[counter];
107
108
}

109
110
111
/**
 * implements the bitwise AND not operation
 */
112
113
static void do_bitandnot(const sc_word *val1, const sc_word *val2,
                         sc_word *buffer)
114
{
Matthias Braun's avatar
Matthias Braun committed
115
	for (int counter = 0; counter < calc_buffer_size; ++counter)
116
		buffer[counter] = val1[counter] & (0xF ^ val2[counter]);
117
118
}

Michael Beck's avatar
Michael Beck committed
119
120
121
/**
 * returns the sign bit.
 */
122
static int do_sign(const sc_word *val)
123
{
124
	return (val[calc_buffer_size-1] <= 7) ? (1) : (-1);
125
126
}

Michael Beck's avatar
Michael Beck committed
127
/**
Michael Beck's avatar
Michael Beck committed
128
129
 * returns non-zero if bit at position pos is set
 */
130
static int do_bit(const sc_word *val, int pos)
131
{
132
133
	int bit    = pos & 3;
	int nibble = pos >> 2;
Michael Beck's avatar
Michael Beck committed
134

135
	return _bitisset(val[nibble], bit);
Michael Beck's avatar
Michael Beck committed
136
137
}

Michael Beck's avatar
Michael Beck committed
138
139
140
/**
 * Implements a fast ADD + 1
 */
141
static void do_inc(const sc_word *val, sc_word *buffer)
142
{
143
144
145
	int counter = 0;

	while (counter++ < calc_buffer_size) {
146
147
		if (*val == 15) {
			*buffer++ = 0;
148
149
			val++;
		} else {
150
151
			/* No carry here, *val != 15 */
			*buffer = *val + 1;
152
153
154
155
156
			return;
		}
	}
	/* here a carry could be lost, this is intended because this should
	 * happen only when a value changes sign. */
157
158
}

Michael Beck's avatar
Michael Beck committed
159
160
161
/**
 * Implements a unary MINUS
 */
162
static void do_negate(const sc_word *val, sc_word *buffer)
163
{
164
165
	do_bitnot(val, buffer);
	do_inc(buffer, buffer);
166
167
}

Michael Beck's avatar
Michael Beck committed
168
169
170
/**
 * Implements a binary ADD
 */
171
static void do_add(const sc_word *val1, const sc_word *val2, sc_word *buffer)
172
{
173
	unsigned carry = 0;
174
175
176
177
	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);
178
	}
179
	carry_flag = carry != 0;
180
181
}

Michael Beck's avatar
Michael Beck committed
182
183
184
/**
 * Implements a binary SUB
 */
185
static void do_sub(const sc_word *val1, const sc_word *val2, sc_word *buffer)
186
{
187
	/* intermediate buffer to hold -val2 */
188
	sc_word *temp_buffer = ALLOCAN(sc_word, calc_buffer_size);
Michael Beck's avatar
Michael Beck committed
189

190
191
	do_negate(val2, temp_buffer);
	do_add(val1, temp_buffer, buffer);
Michael Beck's avatar
Michael Beck committed
192
193
194
195
196
}

/**
 * Implements a binary MUL
 */
197
static void do_mul(const sc_word *val1, const sc_word *val2, sc_word *buffer)
198
{
199
200
201
	sc_word *temp_buffer = ALLOCAN(sc_word, calc_buffer_size);
	sc_word *neg_val1    = ALLOCAN(sc_word, calc_buffer_size);
	sc_word *neg_val2    = ALLOCAN(sc_word, calc_buffer_size);
202

203
	/* init result buffer to zeros */
204
	memset(temp_buffer, 0, calc_buffer_size);
205
206
207

	/* 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
208
	char sign = 0;
209
210
	if (do_sign(val1) == -1) {
		do_negate(val1, neg_val1);
211
212
213
		val1 = neg_val1;
		sign ^= 1;
	}
214
215
	if (do_sign(val2) == -1) {
		do_negate(val2, neg_val2);
216
217
218
219
		val2 = neg_val2;
		sign ^= 1;
	}

Matthias Braun's avatar
Matthias Braun committed
220
	for (int c_outer = 0; c_outer < max_value_size; c_outer++) {
221
222
		if (val2[c_outer] != 0) {
			unsigned carry = 0; /* container for carries */
Matthias Braun's avatar
Matthias Braun committed
223
224
225
226
227
228
			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
				 */
229
230

				/* multiplicate the two digits */
231
				unsigned const mul = val1[c_inner] * val2[c_outer];
232
				/* add old value to result of multiplication and the carry */
Matthias Braun's avatar
Matthias Braun committed
233
234
235
236
237
238
239
240
241
242
243
244
245
				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
				 */
246
247
				temp_buffer[c_inner + c_outer] = SC_RESULT(sum);
				carry                          = SC_CARRY(sum);
248
249
250
251
252
253
254
255
256
			}

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

	if (sign)
257
		do_negate(temp_buffer, buffer);
258
259
	else
		memcpy(buffer, temp_buffer, calc_buffer_size);
260
261
}

Michael Beck's avatar
Michael Beck committed
262
263
264
/**
 * Shift the buffer to left and add a 4 bit digit
 */
265
static void do_push(sc_word digit, sc_word *buffer)
266
{
Matthias Braun's avatar
Matthias Braun committed
267
	for (int counter = calc_buffer_size - 2; counter >= 0; counter--) {
268
269
270
		buffer[counter+1] = buffer[counter];
	}
	buffer[0] = digit;
271
272
}

Michael Beck's avatar
Michael Beck committed
273
274
275
276
277
/**
 * Implements truncating integer division and remainder.
 *
 * Note: This is MOST slow
 */
278
279
static void do_divmod(const sc_word *rDividend, const sc_word *divisor,
                      sc_word *quot, sc_word *rem)
280
{
281
	/* clear result buffer */
282
283
	memset(quot, 0, calc_buffer_size);
	memset(rem, 0, calc_buffer_size);
284
285

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

	/* if the dividend is zero result is zero (quot is zero) */
289
	const sc_word *dividend = rDividend;
290
	if (sc_comp(dividend, quot) == ir_relation_equal)
291
292
		return;

293
294
295
	char     div_sign = 0;
	char     rem_sign = 0;
	sc_word *neg_val1 = ALLOCAN(sc_word, calc_buffer_size);
296
297
	if (do_sign(dividend) == -1) {
		do_negate(dividend, neg_val1);
298
299
300
301
302
		div_sign ^= 1;
		rem_sign ^= 1;
		dividend = neg_val1;
	}

303
	sc_word *neg_val2 = ALLOCAN(sc_word, calc_buffer_size);
304
	do_negate(divisor, neg_val2);
305
	const sc_word *minus_divisor;
306
	if (do_sign(divisor) == -1) {
307
308
309
		div_sign ^= 1;
		minus_divisor = divisor;
		divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
310
	} else {
311
		minus_divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
312
	}
313
314
315
316

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

321
	case ir_relation_less: /* dividend < divisor */
322
		memcpy(rem, dividend, calc_buffer_size);
323
324
325
326
327
328
		goto end;

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

Matthias Braun's avatar
Matthias Braun committed
329
	for (int c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) {
330
		do_push(dividend[c_dividend], rem);
331
		do_push(0, quot);
332

Matthias Braun's avatar
Matthias Braun committed
333
334
		if (sc_comp(rem, divisor) != ir_relation_less) {
			/* remainder >= divisor */
335
336
			/* subtract until the remainder becomes negative, this should
			 * be faster than comparing remainder with divisor  */
337
			do_add(rem, minus_divisor, rem);
338

339
			while (do_sign(rem) == 1) {
340
				/* TODO can this generate carry or is masking redundant? */
341
				quot[0] = SC_RESULT(quot[0] + 1);
342
				do_add(rem, minus_divisor, rem);
343
344
345
			}

			/* subtracted one too much */
346
			do_add(rem, divisor, rem);
347
348
349
350
		}
	}
end:
	/* sets carry if remainder is non-zero ??? */
Matthias Braun's avatar
Matthias Braun committed
351
	carry_flag = !sc_is_zero(rem, calc_buffer_size);
352
353

	if (div_sign)
354
		do_negate(quot, quot);
355
356

	if (rem_sign)
357
		do_negate(rem, rem);
358
359
}

Michael Beck's avatar
Michael Beck committed
360
361
362
363
/**
 * Implements a Shift Left, which can either preserve the sign bit
 * or not.
 */
364
365
static void do_shl(const sc_word *val1, sc_word *buffer, long shift_cnt,
                   int bitsize, bool is_signed)
366
{
367
368
	assert(shift_cnt >= 0);
	assert((do_sign(val1) != -1) || is_signed);
369
370

	/* if shifting far enough the result is zero */
371
	if (shift_cnt >= bitsize) {
372
		memset(buffer, 0, calc_buffer_size);
373
374
375
		return;
	}

376
	unsigned const shift = shift_cnt % SC_BITS;
377
	shift_cnt = shift_cnt / 4;
378
379
380

	/* shift the single digits some bytes (offset) and some bits (table)
	 * to the left */
381
	unsigned carry = 0;
Matthias Braun's avatar
Matthias Braun committed
382
	for (int counter = 0; counter < bitsize/4 - shift_cnt; counter++) {
383
384
385
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
		carry = SC_CARRY(shl);
386
	}
Matthias Braun's avatar
Matthias Braun committed
387
388
	int counter   = bitsize/4 - shift_cnt;
	int bitoffset = 0;
389
	if (bitsize%4 > 0) {
390
391
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
392
393
394
395
396
397
		bitoffset = counter;
	} else {
		bitoffset = counter - 1;
	}

	/* fill with zeroes */
Matthias Braun's avatar
Matthias Braun committed
398
	for (int counter = 0; counter < shift_cnt; counter++)
399
		buffer[counter] = 0;
400
401

	/* if the mode was signed, change sign when the mode's msb is now 1 */
402
403
404
	shift_cnt = bitoffset + shift_cnt;
	bitoffset = (bitsize-1) % 4;
	if (is_signed && _bitisset(buffer[shift_cnt], bitoffset)) {
405
		/* this sets the upper bits of the leftmost digit */
406
		buffer[shift_cnt] |= min_digit[bitoffset];
Matthias Braun's avatar
Matthias Braun committed
407
		for (int counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
408
			buffer[counter] = 0xF;
409
		}
410
	} else if (is_signed && !_bitisset(buffer[shift_cnt], bitoffset)) {
411
		/* this clears the upper bits of the leftmost digit */
412
		buffer[shift_cnt] &= max_digit[bitoffset];
Matthias Braun's avatar
Matthias Braun committed
413
		for (int counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
414
			buffer[counter] = 0;
415
416
		}
	}
417
418
}

Michael Beck's avatar
Michael Beck committed
419
420
421
422
/**
 * Implements a Shift Right, which can either preserve the sign bit
 * or not.
 *
423
 * @param bitsize   bitsize of the value to be shifted
Michael Beck's avatar
Michael Beck committed
424
 */
425
426
static void do_shr(const sc_word *val1, sc_word *buffer, long shift_cnt,
                   int bitsize, bool is_signed, int signed_shift)
427
{
428
	assert(shift_cnt >= 0);
429

430
	sc_word sign = signed_shift && do_bit(val1, bitsize - 1) ? 0xF : 0;
431
432

	/* if shifting far enough the result is either 0 or -1 */
433
	if (shift_cnt >= bitsize) {
Matthias Braun's avatar
Matthias Braun committed
434
		if (!sc_is_zero(val1, calc_buffer_size)) {
Matthias Braun's avatar
Matthias Braun committed
435
			carry_flag = true;
436
437
438
439
440
		}
		memset(buffer, sign, calc_buffer_size);
		return;
	}

Matthias Braun's avatar
Matthias Braun committed
441
442
	int shift_mod = shift_cnt &  3;
	int shift_nib = shift_cnt >> 2;
443
444

	/* check if any bits are lost, and set carry_flag if so */
Matthias Braun's avatar
Matthias Braun committed
445
	for (int counter = 0; counter < shift_nib; ++counter) {
446
		if (val1[counter] != 0) {
Matthias Braun's avatar
Matthias Braun committed
447
			carry_flag = true;
448
449
450
			break;
		}
	}
451
	if ((val1[shift_nib] & ((1<<shift_mod)-1)) != 0)
Matthias Braun's avatar
Matthias Braun committed
452
		carry_flag = true;
453

454
	/* shift digits to the right with offset, carry and all */
455
	buffer[0] = shrs_table[val1[shift_nib]][shift_mod][0];
Matthias Braun's avatar
Matthias Braun committed
456
	int counter;
457
	for (counter = 1; counter < ((bitsize + 3) >> 2) - shift_nib; counter++) {
458
		const sc_word *shrs = shrs_table[val1[counter+shift_nib]][shift_mod];
459
460
		buffer[counter]      = shrs[0];
		buffer[counter - 1] |= shrs[1];
461
462
463
	}

	/* the last digit is special in regard of signed/unsigned shift */
464
465
	int     bitoffset = bitsize & 3;
	sc_word msd       = sign;  /* most significant digit */
466
467
468

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

472
	const sc_word *shrs = shrs_table[msd][shift_mod];
473

474
475
	/* signed shift and signed mode and negative value means all bits to the
	 * left are set */
476
	if (signed_shift && sign == 0xF) {
477
		buffer[counter] = shrs[0] | min_digit[bitoffset];
478
479
480
481
	} else {
		buffer[counter] = shrs[0];
	}

482
	if (counter > 0)
483
		buffer[counter - 1] |= shrs[1];
484

485
	/* fill with 0xF or 0 depending on sign */
486
487
488
	for (counter++; counter < calc_buffer_size; counter++) {
		buffer[counter] = sign;
	}
489
490
}

491

492
const sc_word *sc_get_buffer(void)
493
{
494
	return calc_buffer;
495
496
}

497
498
int sc_get_buffer_length(void)
{
499
	return calc_buffer_size;
500
501
}

502
void sign_extend(sc_word *buffer, unsigned from_bits, bool is_signed)
503
{
504
505
	int bits   = from_bits - 1;
	int nibble = bits >> 2;
506

507
	if (is_signed) {
508
509
		sc_word max = max_digit[bits & 3];
		if (buffer[nibble] > max) {
510
511
			/* sign bit is set, we need sign expansion */

Matthias Braun's avatar
Matthias Braun committed
512
			for (int i = nibble + 1; i < calc_buffer_size; ++i)
513
514
				buffer[i] = 0xF;
			buffer[nibble] |= sex_digit[bits & 3];
515
516
		} else {
			/* set all bits to zero */
Matthias Braun's avatar
Matthias Braun committed
517
			for (int i = nibble + 1; i < calc_buffer_size; ++i)
518
519
				buffer[i] = 0;
			buffer[nibble] &= zex_digit[bits & 3];
520
521
522
		}
	} else {
		/* do zero extension */
Matthias Braun's avatar
Matthias Braun committed
523
		for (int i = nibble + 1; i < calc_buffer_size; ++i)
524
525
			buffer[i] = 0;
		buffer[nibble] &= zex_digit[bits & 3];
526
	}
527
528
}

Matthias Braun's avatar
Matthias Braun committed
529
/* ensure that our source character set conforms to ASCII for a-f, A-F, 0-9 */
530
static inline void check_ascii(void)
531
{
Matthias Braun's avatar
Matthias Braun committed
532
533
534
535
	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);
536
}
537

538
bool sc_val_from_str(char sign, unsigned base, const char *str, size_t len,
539
                     sc_word *buffer)
540
541
542
543
544
{
	assert(sign == -1 || sign == 1);
	assert(str != NULL);
	assert(len > 0);
	check_ascii();
545

546
	assert(base > 1 && base <= 16);
547
	sc_word *sc_base = ALLOCAN(sc_word, calc_buffer_size);
548
	sc_val_from_ulong(base, sc_base);
549

550
	sc_word *val = ALLOCAN(sc_word, calc_buffer_size);
551
552
	if (buffer == NULL)
		buffer = calc_buffer;
553
554
555
556
557
558

	CLEAR_BUFFER(buffer);
	CLEAR_BUFFER(val);

	/* BEGIN string evaluation, from left to right */
	while (len > 0) {
559
560
561
562
		char c = *str;
		unsigned v;
		if (c >= '0' && c <= '9')
			v = c - '0';
563
564
565
566
		else if (c >= 'A' && c <= 'F')
			v = c - 'A' + 10;
		else if (c >= 'a' && c <= 'f')
			v = c - 'a' + 10;
567
		else
568
			return false;
569

570
		if (v >= base)
571
			return false;
572
		val[0] = v;
573
574
575

		/* Radix conversion from base b to base B:
		 *  (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
576
		/* multiply current value with base */
577
		do_mul(sc_base, buffer, buffer);
578
		/* add next digit to current value  */
579
		do_add(val, buffer, buffer);
580
581
582
583

		/* get ready for the next letter */
		str++;
		len--;
584
	}
585

586
	if (sign < 0)
587
		do_negate(buffer, buffer);
588

589
	return true;
590
591
}

592
void sc_val_from_long(long value, sc_word *buffer)
593
{
594
	if (buffer == NULL) buffer = calc_buffer;
595
	sc_word *pos = buffer;
596

Matthias Braun's avatar
Matthias Braun committed
597
598
	char sign       = (value < 0);
	char is_minlong = value == LONG_MIN;
599

600
601
602
603
604
605
606
	/* use absolute value, special treatment of MIN_LONG to avoid overflow */
	if (sign) {
		if (is_minlong)
			value = -(value+1);
		else
			value = -value;
	}
607

608
	CLEAR_BUFFER(buffer);
609

610
	while ((value != 0) && (pos < buffer + calc_buffer_size)) {
611
		*pos++ = value & 0xF;
612
613
		value >>= 4;
	}
614

615
616
	if (sign) {
		if (is_minlong)
617
			do_inc(buffer, buffer);
618

619
		do_negate(buffer, buffer);
620
	}
621
622
}

623
void sc_val_from_ulong(unsigned long value, sc_word *buffer)
624
{
625
	if (buffer == NULL) buffer = calc_buffer;
626
	sc_word *pos = buffer;
627

628
629
	while (pos < buffer + calc_buffer_size) {
		*pos++ = value & 0xF;
630
631
		value >>= 4;
	}
632
633
}

634
long sc_val_to_long(const sc_word *val)
635
{
Andreas Zwinkau's avatar
Andreas Zwinkau committed
636
637
638
639
	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");
640
		l = (l << 4) + val[i];
641
642
	}
	return l;
643
644
}

645
uint64_t sc_val_to_uint64(const sc_word *val)
646
647
648
{
	uint64_t res = 0;
	for (int i = calc_buffer_size - 1; i >= 0; i--) {
649
		res = (res << 4) + val[i];
650
	}
Manuel Mohr's avatar
Manuel Mohr committed
651
	return res;
652
653
}

654
void sc_min_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
655
{
656
657
	if (buffer == NULL) buffer = calc_buffer;
	CLEAR_BUFFER(buffer);
658

659
	if (!sign) return;  /* unsigned means minimum is 0(zero) */
660

661
	sc_word *pos = buffer;
662

663
664
665
	unsigned bits = num_bits - 1;
	unsigned i    = 0;
	for ( ; i < bits/4; i++)
666
		*pos++ = 0;
667

668
	*pos++ = min_digit[bits%4];
669

670
	for (i++; (int)i <= calc_buffer_size - 1; i++)
671
		*pos++ = 0xF;
672
673
}

674
void sc_max_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
675
{
676
677
	if (buffer == NULL) buffer = calc_buffer;
	CLEAR_BUFFER(buffer);
678
	sc_word *pos = buffer;
679

680
681
	unsigned bits = num_bits - sign;
	unsigned i    = 0;
Matthias Braun's avatar
Matthias Braun committed
682
	for ( ; i < bits/4; i++)
683
		*pos++ = 0xF;
684

685
	*pos++ = max_digit[bits%4];
686

687
	for (i++; (int)i <= calc_buffer_size - 1; i++)
688
		*pos++ = 0;
689
690
}

691
void sc_truncate(unsigned int num_bits, sc_word *buffer)
692
{
693
694
695
	sc_word *cbuffer = buffer;
	sc_word *pos     = cbuffer + (num_bits / 4);
	sc_word *end     = cbuffer + calc_buffer_size;
696
697
698

	assert(pos < end);

699
	switch (num_bits % 4) {
700
	case 0: /* nothing to do */ break;
701
702
703
	case 1: *pos++ &= 1; break;
	case 2: *pos++ &= 3; break;
	case 3: *pos++ &= 7; break;
704
705
	}

706
	for ( ; pos < end; ++pos)
707
		*pos = 0;
708
709
}

710
ir_relation sc_comp(const sc_word* const val1, const sc_word* const val2)
711
{
712
713
714
715
	int counter = calc_buffer_size - 1;

	/* compare signs first:
	 * the loop below can only compare values of the same sign! */
716
	if (do_sign(val1) != do_sign(val2))
717
		return do_sign(val1) == 1 ? ir_relation_greater : ir_relation_less;
718
719
720
721
722

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

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

732
int sc_get_highest_set_bit(const sc_word *value)
733
{
734
	int            high = calc_buffer_size * 4 - 1;
Matthias Braun's avatar
Matthias Braun committed
735
	for (int counter = calc_buffer_size-1; counter >= 0; counter--) {
736
		if (value[counter] == 0)
737
738
			high -= 4;
		else {
739
740
741
			if (value[counter] > 7) return high;
			else if (value[counter] > 3) return high - 1;
			else if (value[counter] > 1) return high - 2;
742
743
744
745
			else return high - 3;
		}
	}
	return high;
Matthias Heil's avatar
Matthias Heil committed
746
747
}

748
int sc_get_lowest_set_bit(const sc_word *value)
749
{
Matthias Braun's avatar
Matthias Braun committed
750
751
	int         low = 0;
	for (int counter = 0; counter < calc_buffer_size; counter++) {
752
		switch (value[counter]) {
753
754
755
756
757
758
759
760
		case 1:
		case 3:
		case 5:
		case 7:
		case 9:
		case 11:
		case 13:
		case 15:
761
			return low;
762
763
764
765
		case 2:
		case 6:
		case 10:
		case 14:
766
			return low + 1;
767
768
		case 4:
		case 12:
769
			return low + 2;
770
		case 8:
771
772
			return low + 3;
		default:
773
774
775
776
			low += 4;
		}
	}
	return -1;
Matthias Heil's avatar
Matthias Heil committed
777
778
}

779
int sc_get_bit_at(const sc_word *value, unsigned pos)
780
{
781
782
	unsigned nibble = pos >> 2;
	return (value[nibble] & (1 << (pos & 3))) != 0;
783
784
}

785
void sc_set_bit_at(sc_word *value, unsigned pos)
786
787
{
	unsigned nibble = pos >> 2;
788
	value[nibble] |= 1 << (pos & 3);
789
790
}

791
void sc_clear_bit_at(sc_word *value, unsigned pos)
Matthias Braun's avatar
Matthias Braun committed
792
793
{
	unsigned nibble = pos >> 2;
794
	value[nibble] &= ~(1 << (pos & 3));
Matthias Braun's avatar
Matthias Braun committed
795
796
}

797
bool sc_is_zero(const sc_word *value, unsigned bits)
798
{
Matthias Braun's avatar
Matthias Braun committed
799
800
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
801
		if (value[i] != 0)
802
			return false;
803
	}
804
805
	sc_word mask = max_digit[bits%SC_BITS];
	return mask == 0 || (value[i] & mask) == 0;
Matthias Braun's avatar
Matthias Braun committed
806
807
}

808
bool sc_is_all_one(const sc_word *value, unsigned bits)