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
#define SC_BITS      4
Matthias Braun's avatar
Matthias Braun committed
25
#define SC_MASK      ((sc_word)0xF)
26
27
28
#define SC_RESULT(x) ((x) & ((1U << SC_BITS) - 1U))
#define SC_CARRY(x)  ((unsigned)(x) >> SC_BITS)

29
#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

37
static const sc_word shrs_table[16][4][2] = {
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
	{ { 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} }
};
55

Michael Beck's avatar
Michael Beck committed
56
/** converting a digit to a binary string */
57
static char const *const binary_table[] = {
58
59
	"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111",
	"1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"
60
61
};

62
63
64
65
66
void sc_zero(sc_word *buffer)
{
	memset(buffer, 0, sizeof(buffer[0]) * calc_buffer_size);
}

Matthias Braun's avatar
Matthias Braun committed
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
static sc_word zex_digit(unsigned x)
{
	return (1u << (x+1)) - 1;
}

static sc_word sex_digit(unsigned x)
{
	return (SC_MASK << (x+1)) & SC_MASK;
}

static sc_word max_digit(unsigned x)
{
	return (1u << x) - 1;
}

static sc_word min_digit(unsigned x)
{
	return SC_MASK - max_digit(x);
}

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

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

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

Michael Beck's avatar
Michael Beck committed
114
115
116
/**
 * implements the bitwise AND operation
 */
117
static void do_bitand(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] & val2[counter];
121
122
}

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

Michael Beck's avatar
Michael Beck committed
133
/**
Michael Beck's avatar
Michael Beck committed
134
135
 * returns non-zero if bit at position pos is set
 */
136
static int do_bit(const sc_word *val, int pos)
137
{
138
139
	int bit    = pos % SC_BITS;
	int nibble = pos / SC_BITS;
Michael Beck's avatar
Michael Beck committed
140

141
	return _bitisset(val[nibble], bit);
Michael Beck's avatar
Michael Beck committed
142
143
}

Michael Beck's avatar
Michael Beck committed
144
145
146
/**
 * Implements a fast ADD + 1
 */
147
static void do_inc(const sc_word *val, sc_word *buffer)
148
{
149
150
151
	int counter = 0;

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

Michael Beck's avatar
Michael Beck committed
165
166
167
/**
 * Implements a unary MINUS
 */
168
static void do_negate(const sc_word *val, sc_word *buffer)
169
{
170
171
	do_bitnot(val, buffer);
	do_inc(buffer, buffer);
172
173
}

Michael Beck's avatar
Michael Beck committed
174
175
176
/**
 * Implements a binary ADD
 */
177
static void do_add(const sc_word *val1, const sc_word *val2, sc_word *buffer)
178
{
179
	unsigned carry = 0;
180
181
182
183
	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);
184
	}
185
186
}

Michael Beck's avatar
Michael Beck committed
187
188
189
/**
 * Implements a binary SUB
 */
190
static void do_sub(const sc_word *val1, const sc_word *val2, sc_word *buffer)
191
{
192
	/* intermediate buffer to hold -val2 */
193
	sc_word *temp_buffer = ALLOCAN(sc_word, calc_buffer_size);
Michael Beck's avatar
Michael Beck committed
194

195
196
	do_negate(val2, temp_buffer);
	do_add(val1, temp_buffer, buffer);
Michael Beck's avatar
Michael Beck committed
197
198
199
200
201
}

/**
 * Implements a binary MUL
 */
202
static void do_mul(const sc_word *val1, const sc_word *val2, sc_word *buffer)
203
{
204
205
206
	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);
207

208
	/* init result buffer to zeros */
209
	memset(temp_buffer, 0, calc_buffer_size);
210
211
212

	/* the multiplication works only for positive values, for negative values *
	 * it is necessary to negate them and adjust the result accordingly       */
213
	bool sign = false;
214
	if (sc_is_negative(val1)) {
215
		do_negate(val1, neg_val1);
216
		val1 = neg_val1;
217
		sign = !sign;
218
	}
219
	if (sc_is_negative(val2)) {
220
		do_negate(val2, neg_val2);
221
		val2 = neg_val2;
222
		sign = !sign;
223
224
	}

Matthias Braun's avatar
Matthias Braun committed
225
	for (int c_outer = 0; c_outer < max_value_size; c_outer++) {
Matthias Braun's avatar
Matthias Braun committed
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
		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);
256
		}
Matthias Braun's avatar
Matthias Braun committed
257
258
259
260

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

	if (sign)
264
		do_negate(temp_buffer, buffer);
265
266
	else
		memcpy(buffer, temp_buffer, calc_buffer_size);
267
268
}

Michael Beck's avatar
Michael Beck committed
269
/**
270
 * Shift the buffer to left and add an sc digit
Michael Beck's avatar
Michael Beck committed
271
 */
272
static void do_push(sc_word digit, sc_word *buffer)
273
{
Matthias Braun's avatar
Matthias Braun committed
274
	for (int counter = calc_buffer_size - 2; counter >= 0; counter--) {
275
276
277
		buffer[counter+1] = buffer[counter];
	}
	buffer[0] = digit;
278
279
}

Michael Beck's avatar
Michael Beck committed
280
281
282
283
284
/**
 * Implements truncating integer division and remainder.
 *
 * Note: This is MOST slow
 */
285
static bool do_divmod(const sc_word *dividend, const sc_word *divisor,
286
                      sc_word *quot, sc_word *rem)
287
{
288
289
	assert(quot != dividend && quot != divisor);
	assert(rem != dividend && rem != divisor);
290
	/* clear result buffer */
291
292
	memset(quot, 0, calc_buffer_size);
	memset(rem, 0, calc_buffer_size);
293

294
295
	/* division by zero is not allowed */
	assert(!sc_is_zero(divisor, calc_buffer_size*SC_BITS));
296
297

	/* if the dividend is zero result is zero (quot is zero) */
298
	if (sc_is_zero(dividend, calc_buffer_size*SC_BITS))
299
		return false;
300

301
302
	bool     div_sign = false;
	bool     rem_sign = false;
303
	sc_word *neg_val1 = ALLOCAN(sc_word, calc_buffer_size);
304
	if (sc_is_negative(dividend)) {
305
		do_negate(dividend, neg_val1);
306
307
		div_sign = !div_sign;
		rem_sign = !rem_sign;
308
309
310
		dividend = neg_val1;
	}

311
	sc_word *neg_val2 = ALLOCAN(sc_word, calc_buffer_size);
312
	do_negate(divisor, neg_val2);
313
	const sc_word *minus_divisor;
314
	if (sc_is_negative(divisor)) {
315
		div_sign = !div_sign;
316
317
		minus_divisor = divisor;
		divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
318
	} else {
319
		minus_divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
320
	}
321
322
323
324

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

329
	case ir_relation_less: /* dividend < divisor */
330
		memcpy(rem, dividend, calc_buffer_size);
331
332
333
334
335
336
		goto end;

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

Matthias Braun's avatar
Matthias Braun committed
337
	for (int c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) {
338
		do_push(dividend[c_dividend], rem);
339
		do_push(0, quot);
340

Matthias Braun's avatar
Matthias Braun committed
341
342
		if (sc_comp(rem, divisor) != ir_relation_less) {
			/* remainder >= divisor */
343
344
			/* subtract until the remainder becomes negative, this should
			 * be faster than comparing remainder with divisor  */
345
			do_add(rem, minus_divisor, rem);
346

347
			while (!sc_is_negative(rem)) {
348
				/* TODO can this generate carry or is masking redundant? */
349
				quot[0] = SC_RESULT(quot[0] + 1);
350
				do_add(rem, minus_divisor, rem);
351
352
353
			}

			/* subtracted one too much */
354
			do_add(rem, divisor, rem);
355
356
357
358
		}
	}
end:
	if (div_sign)
359
		do_negate(quot, quot);
360
361

	if (rem_sign)
362
		do_negate(rem, rem);
363
364
365
366

	/* sets carry if remainder is non-zero ??? */
	bool carry_flag = !sc_is_zero(rem, calc_buffer_size*SC_BITS);
	return carry_flag;
367
368
}

Michael Beck's avatar
Michael Beck committed
369
370
371
372
/**
 * Implements a Shift Left, which can either preserve the sign bit
 * or not.
 */
373
374
static void do_shl(const sc_word *val1, sc_word *buffer, long shift_cnt,
                   int bitsize, bool is_signed)
375
{
376
	assert(buffer != val1);
377
	assert(shift_cnt >= 0);
378
	assert(!sc_is_negative(val1) || is_signed);
379
380

	/* if shifting far enough the result is zero */
381
	if (shift_cnt >= bitsize) {
382
		memset(buffer, 0, calc_buffer_size);
383
384
385
		return;
	}

386
	unsigned const shift = shift_cnt % SC_BITS;
387
	shift_cnt = shift_cnt / SC_BITS;
388
389
390

	/* shift the single digits some bytes (offset) and some bits (table)
	 * to the left */
391
	unsigned carry = 0;
392
	for (int counter = 0; counter < bitsize/SC_BITS - shift_cnt; counter++) {
393
394
395
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
		carry = SC_CARRY(shl);
396
	}
397
	int counter   = bitsize/SC_BITS - shift_cnt;
Matthias Braun's avatar
Matthias Braun committed
398
	int bitoffset = 0;
399
	if (bitsize%SC_BITS > 0) {
400
401
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
402
403
404
405
406
407
		bitoffset = counter;
	} else {
		bitoffset = counter - 1;
	}

	/* fill with zeroes */
Matthias Braun's avatar
Matthias Braun committed
408
	for (int counter = 0; counter < shift_cnt; counter++)
409
		buffer[counter] = 0;
410
411

	/* if the mode was signed, change sign when the mode's msb is now 1 */
412
	shift_cnt = bitoffset + shift_cnt;
413
	bitoffset = (bitsize-1) % SC_BITS;
414
	if (is_signed && _bitisset(buffer[shift_cnt], bitoffset)) {
415
		/* this sets the upper bits of the leftmost digit */
Matthias Braun's avatar
Matthias Braun committed
416
		buffer[shift_cnt] |= min_digit(bitoffset);
Matthias Braun's avatar
Matthias Braun committed
417
		for (int counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
Matthias Braun's avatar
Matthias Braun committed
418
			buffer[counter] = SC_MASK;
419
		}
420
	} else if (is_signed && !_bitisset(buffer[shift_cnt], bitoffset)) {
421
		/* this clears the upper bits of the leftmost digit */
Matthias Braun's avatar
Matthias Braun committed
422
		buffer[shift_cnt] &= max_digit(bitoffset);
Matthias Braun's avatar
Matthias Braun committed
423
		for (int counter = shift_cnt+1; counter < calc_buffer_size; counter++) {
424
			buffer[counter] = 0;
425
426
		}
	}
427
428
}

Michael Beck's avatar
Michael Beck committed
429
430
431
432
/**
 * Implements a Shift Right, which can either preserve the sign bit
 * or not.
 *
433
 * @param bitsize   bitsize of the value to be shifted
Michael Beck's avatar
Michael Beck committed
434
 */
435
static bool do_shr(const sc_word *val1, sc_word *buffer, long shift_cnt,
436
                   int bitsize, bool is_signed, bool signed_shift)
437
{
438
	assert(shift_cnt >= 0);
439

440
	bool    carry_flag = false;
Matthias Braun's avatar
Matthias Braun committed
441
	sc_word sign = signed_shift && do_bit(val1, bitsize - 1) ? SC_MASK : 0;
442
443

	/* if shifting far enough the result is either 0 or -1 */
444
	if (shift_cnt >= bitsize) {
445
		if (!sc_is_zero(val1, calc_buffer_size*SC_BITS)) {
Matthias Braun's avatar
Matthias Braun committed
446
			carry_flag = true;
447
448
		}
		memset(buffer, sign, calc_buffer_size);
449
		return carry_flag;
450
451
	}

452
453
	int shift_mod = shift_cnt % SC_BITS;
	int shift_nib = shift_cnt / SC_BITS;
454
455

	/* check if any bits are lost, and set carry_flag if so */
Matthias Braun's avatar
Matthias Braun committed
456
	for (int counter = 0; counter < shift_nib; ++counter) {
457
		if (val1[counter] != 0) {
Matthias Braun's avatar
Matthias Braun committed
458
			carry_flag = true;
459
460
461
			break;
		}
	}
462
	if ((val1[shift_nib] & ((1<<shift_mod)-1)) != 0)
Matthias Braun's avatar
Matthias Braun committed
463
		carry_flag = true;
464

465
	/* shift digits to the right with offset, carry and all */
466
	buffer[0] = shrs_table[val1[shift_nib]][shift_mod][0];
Matthias Braun's avatar
Matthias Braun committed
467
	int counter;
468
469
	for (counter = 1; counter < ((bitsize + 3) / SC_BITS) - shift_nib;
	     ++counter) {
470
		const sc_word *shrs = shrs_table[val1[counter+shift_nib]][shift_mod];
471
472
		buffer[counter]      = shrs[0];
		buffer[counter - 1] |= shrs[1];
473
474
475
	}

	/* the last digit is special in regard of signed/unsigned shift */
476
	int     bitoffset = bitsize % SC_BITS;
477
	sc_word msd       = sign;  /* most significant digit */
478
479
480

	/* remove sign bits if mode was signed and this is an unsigned shift */
	if (!signed_shift && is_signed) {
Matthias Braun's avatar
Matthias Braun committed
481
		msd &= max_digit(bitoffset);
482
483
	}

484
	const sc_word *shrs = shrs_table[msd][shift_mod];
485

486
487
	/* signed shift and signed mode and negative value means all bits to the
	 * left are set */
Matthias Braun's avatar
Matthias Braun committed
488
	if (signed_shift && sign == SC_MASK) {
Matthias Braun's avatar
Matthias Braun committed
489
		buffer[counter] = shrs[0] | min_digit(bitoffset);
490
491
492
493
	} else {
		buffer[counter] = shrs[0];
	}

494
	if (counter > 0)
495
		buffer[counter - 1] |= shrs[1];
496

497
	/* fill with 0xF or 0 depending on sign */
498
499
500
	for (counter++; counter < calc_buffer_size; counter++) {
		buffer[counter] = sign;
	}
501
502

	return carry_flag;
503
504
}

505

506
const sc_word *sc_get_buffer(void)
507
{
508
	return calc_buffer;
509
510
}

511
512
int sc_get_buffer_length(void)
{
513
	return calc_buffer_size;
514
515
}

516
void sign_extend(sc_word *buffer, unsigned from_bits, bool is_signed)
517
{
518
	int bits   = from_bits - 1;
519
	int nibble = bits / SC_BITS;
520

521
	if (is_signed) {
522
		sc_word max = max_digit(bits % SC_BITS);
523
		if (buffer[nibble] > max) {
524
525
			/* sign bit is set, we need sign expansion */

Matthias Braun's avatar
Matthias Braun committed
526
			for (int i = nibble + 1; i < calc_buffer_size; ++i)
Matthias Braun's avatar
Matthias Braun committed
527
				buffer[i] = SC_MASK;
528
			buffer[nibble] |= sex_digit(bits % SC_BITS);
529
530
		} else {
			/* set all bits to zero */
Matthias Braun's avatar
Matthias Braun committed
531
			for (int i = nibble + 1; i < calc_buffer_size; ++i)
532
				buffer[i] = 0;
533
			buffer[nibble] &= zex_digit(bits % SC_BITS);
534
535
536
		}
	} else {
		/* do zero extension */
Matthias Braun's avatar
Matthias Braun committed
537
		for (int i = nibble + 1; i < calc_buffer_size; ++i)
538
			buffer[i] = 0;
539
		buffer[nibble] &= zex_digit(bits % SC_BITS);
540
	}
541
542
}

Matthias Braun's avatar
Matthias Braun committed
543
/* ensure that our source character set conforms to ASCII for a-f, A-F, 0-9 */
544
static inline void check_ascii(void)
545
{
Matthias Braun's avatar
Matthias Braun committed
546
547
548
549
	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);
550
}
551

552
bool sc_val_from_str(bool negative, unsigned base, const char *str, size_t len,
553
                     sc_word *buffer)
554
555
556
557
{
	assert(str != NULL);
	assert(len > 0);
	check_ascii();
558

559
	assert(base > 1 && base <= 16);
560
	sc_word *sc_base = ALLOCAN(sc_word, calc_buffer_size);
561
	sc_val_from_ulong(base, sc_base);
562

563
	sc_word *val = ALLOCAN(sc_word, calc_buffer_size);
564

565
566
	sc_zero(buffer);
	sc_zero(val);
567
568
569

	/* BEGIN string evaluation, from left to right */
	while (len > 0) {
570
571
572
573
		char c = *str;
		unsigned v;
		if (c >= '0' && c <= '9')
			v = c - '0';
574
575
576
577
		else if (c >= 'A' && c <= 'F')
			v = c - 'A' + 10;
		else if (c >= 'a' && c <= 'f')
			v = c - 'a' + 10;
578
		else
579
			return false;
580

581
		if (v >= base)
582
			return false;
583
		val[0] = v;
584
585
586

		/* Radix conversion from base b to base B:
		 *  (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
587
		/* multiply current value with base */
588
		do_mul(sc_base, buffer, buffer);
589
		/* add next digit to current value  */
590
		do_add(val, buffer, buffer);
591
592
593
594

		/* get ready for the next letter */
		str++;
		len--;
595
	}
596

597
	if (negative)
598
		do_negate(buffer, buffer);
599

600
	return true;
601
602
}

603
void sc_val_from_long(long value, sc_word *buffer)
604
{
605
	sc_word *pos = buffer;
606

607
608
	bool sign       = value < 0;
	bool is_minlong = value == LONG_MIN;
609

610
611
612
613
614
615
616
	/* use absolute value, special treatment of MIN_LONG to avoid overflow */
	if (sign) {
		if (is_minlong)
			value = -(value+1);
		else
			value = -value;
	}
617

618
	sc_zero(buffer);
619

620
	while ((value != 0) && (pos < buffer + calc_buffer_size)) {
Matthias Braun's avatar
Matthias Braun committed
621
		*pos++ = value & SC_MASK;
622
		value >>= SC_BITS;
623
	}
624

625
626
	if (sign) {
		if (is_minlong)
627
			do_inc(buffer, buffer);
628

629
		do_negate(buffer, buffer);
630
	}
631
632
}

633
void sc_val_from_ulong(unsigned long value, sc_word *buffer)
634
{
635
	sc_word *pos = buffer;
636

637
	while (pos < buffer + calc_buffer_size) {
Matthias Braun's avatar
Matthias Braun committed
638
		*pos++ = value & SC_MASK;
639
		value >>= SC_BITS;
640
	}
641
642
}

643
long sc_val_to_long(const sc_word *val)
644
{
Andreas Zwinkau's avatar
Andreas Zwinkau committed
645
646
647
	unsigned long l = 0;
	int max_buffer_index = sizeof(long)*8/SC_BITS;
	for (size_t i = max_buffer_index; i-- > 0;) {
648
649
		assert(l <= (ULONG_MAX>>SC_BITS) && "signed shift overflow");
		l = (l << SC_BITS) + val[i];
650
651
	}
	return l;
652
653
}

654
uint64_t sc_val_to_uint64(const sc_word *val)
655
656
657
{
	uint64_t res = 0;
	for (int i = calc_buffer_size - 1; i >= 0; i--) {
658
		res = (res << SC_BITS) + val[i];
659
	}
Manuel Mohr's avatar
Manuel Mohr committed
660
	return res;
661
662
}

663
void sc_min_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
664
{
665
	if (!sign) {
666
		sc_zero(buffer);
667
668
669
		return;
	} else {
		sc_word *pos = buffer;
670

671
672
		unsigned bits = num_bits - 1;
		unsigned i    = 0;
673
		for ( ; i < bits/SC_BITS; i++)
674
			*pos++ = 0;
675

676
		*pos++ = min_digit(bits%SC_BITS);
677

678
		for (i++; (int)i <= calc_buffer_size - 1; i++)
Matthias Braun's avatar
Matthias Braun committed
679
			*pos++ = SC_MASK;
680
	}
681
682
}

683
void sc_max_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
684
{
685
	sc_word *pos = buffer;
686

687
688
	unsigned bits = num_bits - sign;
	unsigned i    = 0;
689
	for ( ; i < bits/SC_BITS; i++)
Matthias Braun's avatar
Matthias Braun committed
690
		*pos++ = SC_MASK;
691

692
	*pos++ = max_digit(bits%SC_BITS);
693

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

698
void sc_truncate(unsigned int num_bits, sc_word *buffer)
699
{
700
	sc_word *cbuffer = buffer;
701
	sc_word *pos     = cbuffer + (num_bits / SC_BITS);
702
	sc_word *end     = cbuffer + calc_buffer_size;
703
704
705

	assert(pos < end);

706
	switch (num_bits % SC_BITS) {
707
	case 0: /* nothing to do */ break;
708
709
710
	case 1: *pos++ &= 1; break;
	case 2: *pos++ &= 3; break;
	case 3: *pos++ &= 7; break;
711
712
	}

713
	for ( ; pos < end; ++pos)
714
		*pos = 0;
715
716
}

717
ir_relation sc_comp(const sc_word* const val1, const sc_word* const val2)
718
{
719
720
	/* compare signs first:
	 * the loop below can only compare values of the same sign! */
721
722
723
724
	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;
725
726
727

	/* loop until two digits differ, the values are equal if there
	 * are no such two digits */
728
	int counter = calc_buffer_size - 1;
729
730
	while (val1[counter] == val2[counter]) {
		counter--;
731
		if (counter < 0) return ir_relation_equal;
732
733
734
735
736
	}

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

741
int sc_get_highest_set_bit(const sc_word *value)
742
{
743
	int            high = calc_buffer_size * SC_BITS - 1;
Matthias Braun's avatar
Matthias Braun committed
744
	for (int counter = calc_buffer_size-1; counter >= 0; counter--) {
745
		if (value[counter] == 0)
746
			high -= SC_BITS;
747
		else {
748
749
750
			if (value[counter] > 7) return high;
			else if (value[counter] > 3) return high - 1;
			else if (value[counter] > 1) return high - 2;
751
752
753
754
			else return high - 3;
		}
	}
	return high;
Matthias Heil's avatar
Matthias Heil committed
755
756
}

757
int sc_get_lowest_set_bit(const sc_word *value)
758
{
Matthias Braun's avatar
Matthias Braun committed
759
760
	int         low = 0;
	for (int counter = 0; counter < calc_buffer_size; counter++) {
761
		switch (value[counter]) {
762
763
764
765
766
767
768
769
		case 1:
		case 3:
		case 5:
		case 7:
		case 9:
		case 11:
		case 13:
		case 15:
770
			return low;
771
772
773
774
		case 2:
		case 6:
		case 10:
		case 14:
775
			return low + 1;
776
777
		case 4:
		case 12:
778
			return low + 2;
779
		case 8:
780
781
			return low + 3;
		default:
782
			low += SC_BITS;
783
784
785
		}
	}
	return -1;
Matthias Heil's avatar
Matthias Heil committed
786
787
}

788
bool sc_get_bit_at(const sc_word *value, unsigned pos)
789
{
790
791
	unsigned nibble = pos / SC_BITS;
	return value[nibble] & (1 << (pos % SC_BITS));
792
793
}