strcalc.c 30 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
#define _bitisset(digit, pos) (((digit) & (1 << (pos))) != 0)
29

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

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

42
43
44
45
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 };
46

47
static const sc_word shrs_table[16][4][2] = {
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
	{ { 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} }
};
65

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

72
73
74
75
76
void sc_zero(sc_word *buffer)
{
	memset(buffer, 0, sizeof(buffer[0]) * calc_buffer_size);
}

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

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

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

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

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

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

131
	return _bitisset(val[nibble], bit);
Michael Beck's avatar
Michael Beck committed
132
133
}

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

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

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

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

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

186
187
	do_negate(val2, temp_buffer);
	do_add(val1, temp_buffer, buffer);
Michael Beck's avatar
Michael Beck committed
188
189
190
191
192
}

/**
 * Implements a binary MUL
 */
193
static void do_mul(const sc_word *val1, const sc_word *val2, sc_word *buffer)
194
{
195
196
197
	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);
198

199
	/* init result buffer to zeros */
200
	memset(temp_buffer, 0, calc_buffer_size);
201
202
203

	/* 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
204
	char sign = 0;
205
	if (sc_is_negative(val1)) {
206
		do_negate(val1, neg_val1);
207
208
209
		val1 = neg_val1;
		sign ^= 1;
	}
210
	if (sc_is_negative(val2)) {
211
		do_negate(val2, neg_val2);
212
213
214
215
		val2 = neg_val2;
		sign ^= 1;
	}

Matthias Braun's avatar
Matthias Braun committed
216
	for (int c_outer = 0; c_outer < max_value_size; c_outer++) {
Matthias Braun's avatar
Matthias Braun committed
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
		sc_word outer = val2[c_outer];
		if (outer == 0)
			continue;
		unsigned carry = 0; /* container for carries */
		for (int c_inner = 0; c_inner < max_value_size; c_inner++) {
			sc_word inner = val1[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 */
			unsigned const mul = inner*outer;
			/* add old value to result of multiplication and the carry */
			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
			 */
			temp_buffer[c_inner + c_outer] = SC_RESULT(sum);
			carry                          = SC_CARRY(sum);
247
		}
Matthias Braun's avatar
Matthias Braun committed
248
249
250
251

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

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

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

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

285
286
	/* division by zero is not allowed */
	assert(!sc_is_zero(divisor, calc_buffer_size*SC_BITS));
287
288

	/* if the dividend is zero result is zero (quot is zero) */
289
	if (sc_is_zero(dividend, calc_buffer_size*SC_BITS))
290
291
		return;

292
293
	bool     div_sign = false;
	bool     rem_sign = false;
294
	sc_word *neg_val1 = ALLOCAN(sc_word, calc_buffer_size);
295
	if (sc_is_negative(dividend)) {
296
		do_negate(dividend, neg_val1);
297
298
		div_sign ^= true;
		rem_sign ^= true;
299
300
301
		dividend = neg_val1;
	}

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

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

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

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

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

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

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

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

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

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

Michael Beck's avatar
Michael Beck committed
359
360
361
362
/**
 * Implements a Shift Left, which can either preserve the sign bit
 * or not.
 */
363
364
static void do_shl(const sc_word *val1, sc_word *buffer, long shift_cnt,
                   int bitsize, bool is_signed)
365
{
366
	assert(buffer != val1);
367
	assert(shift_cnt >= 0);
368
	assert(!sc_is_negative(val1) || 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) {
434
		if (!sc_is_zero(val1, calc_buffer_size*SC_BITS)) {
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
553
	sc_zero(buffer);
	sc_zero(val);
554
555
556

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

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

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

		/* get ready for the next letter */
		str++;
		len--;
582
	}
583

584
	if (sign < 0)
585
		do_negate(buffer, buffer);
586

587
	return true;
588
589
}

590
void sc_val_from_long(long value, sc_word *buffer)
591
{
592
	sc_word *pos = buffer;
593

Matthias Braun's avatar
Matthias Braun committed
594
595
	char sign       = (value < 0);
	char is_minlong = value == LONG_MIN;
596

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

605
	sc_zero(buffer);
606

607
	while ((value != 0) && (pos < buffer + calc_buffer_size)) {
608
		*pos++ = value & 0xF;
609
610
		value >>= 4;
	}
611

612
613
	if (sign) {
		if (is_minlong)
614
			do_inc(buffer, buffer);
615

616
		do_negate(buffer, buffer);
617
	}
618
619
}

620
void sc_val_from_ulong(unsigned long value, sc_word *buffer)
621
{
622
	sc_word *pos = buffer;
623

624
625
	while (pos < buffer + calc_buffer_size) {
		*pos++ = value & 0xF;
626
627
		value >>= 4;
	}
628
629
}

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

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

650
void sc_min_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
651
{
652
	if (!sign) {
653
		sc_zero(buffer);
654
655
656
		return;
	} else {
		sc_word *pos = buffer;
657

658
659
660
661
		unsigned bits = num_bits - 1;
		unsigned i    = 0;
		for ( ; i < bits/4; i++)
			*pos++ = 0;
662

663
		*pos++ = min_digit[bits%4];
664

665
666
667
		for (i++; (int)i <= calc_buffer_size - 1; i++)
			*pos++ = 0xF;
	}
668
669
}

670
void sc_max_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
671
{
672
	sc_word *pos = buffer;
673

674
675
	unsigned bits = num_bits - sign;
	unsigned i    = 0;
Matthias Braun's avatar
Matthias Braun committed
676
	for ( ; i < bits/4; i++)
677
		*pos++ = 0xF;
678

679
	*pos++ = max_digit[bits%4];
680

681
	for (i++; (int)i <= calc_buffer_size - 1; i++)
682
		*pos++ = 0;
683
684
}

685
void sc_truncate(unsigned int num_bits, sc_word *buffer)
686
{
687
688
689
	sc_word *cbuffer = buffer;
	sc_word *pos     = cbuffer + (num_bits / 4);
	sc_word *end     = cbuffer + calc_buffer_size;
690
691
692

	assert(pos < end);

693
	switch (num_bits % 4) {
694
	case 0: /* nothing to do */ break;
695
696
697
	case 1: *pos++ &= 1; break;
	case 2: *pos++ &= 3; break;
	case 3: *pos++ &= 7; break;
698
699
	}

700
	for ( ; pos < end; ++pos)
701
		*pos = 0;
702
703
}

704
ir_relation sc_comp(const sc_word* const val1, const sc_word* const val2)
705
{
706
707
	/* compare signs first:
	 * the loop below can only compare values of the same sign! */
708
709
710
711
	bool val1_negative = sc_is_negative(val1);
	bool val2_negative = sc_is_negative(val2);
	if (val1_negative != val2_negative)
		return val1_negative ? ir_relation_less : ir_relation_greater;
712
713
714

	/* loop until two digits differ, the values are equal if there
	 * are no such two digits */
715
	int counter = calc_buffer_size - 1;
716
717
	while (val1[counter] == val2[counter]) {
		counter--;
718
		if (counter < 0) return ir_relation_equal;
719
720
721
722
723
	}

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

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

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

775
int sc_get_bit_at(const sc_word *value, unsigned pos)
776
{
777
778
	unsigned nibble = pos >> 2;
	return (value[nibble] & (1 << (pos & 3))) != 0;
779
780
}

781
void sc_set_bit_at(sc_word *value, unsigned pos)
782
783
{
	unsigned nibble = pos >> 2;
784
	value[nibble] |= 1 << (pos & 3);
785
786
}

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

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

804
bool sc_is_all_one(const sc_word *value, unsigned bits)
Matthias Braun's avatar
Matthias Braun committed
805
806
807
{
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
808
		if (value[i] != 0xF)
Matthias Braun's avatar
Matthias Braun committed
809
810
			return false;
	}
811
812
	sc_word mask = max_digit[bits%SC_BITS];
	return mask == 0 || (value[i] & mask) == mask;