strcalc.c 32.1 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
124
125
/**
 * returns the sign bit.
 */
126
static int do_sign(const sc_word *val)
127
{
128
	return (val[calc_buffer_size-1] <= 7) ? (1) : (-1);
129
130
}

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

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

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

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

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

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

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

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

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

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

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

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

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

	if (sign)
261
		do_negate(temp_buffer, buffer);
262
263
	else
		memcpy(buffer, temp_buffer, calc_buffer_size);
264
265
}

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

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

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

	/* if the dividend is zero result is zero (quot is zero) */
293
	const sc_word *dividend = rDividend;
294
	if (sc_comp(dividend, quot) == ir_relation_equal)
295
296
		return;

297
298
299
	char     div_sign = 0;
	char     rem_sign = 0;
	sc_word *neg_val1 = ALLOCAN(sc_word, calc_buffer_size);
300
301
	if (do_sign(dividend) == -1) {
		do_negate(dividend, neg_val1);
302
303
304
305
306
		div_sign ^= 1;
		rem_sign ^= 1;
		dividend = neg_val1;
	}

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

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

325
	case ir_relation_less: /* dividend < divisor */
326
		memcpy(rem, dividend, calc_buffer_size);
327
328
329
330
331
332
		goto end;

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

Matthias Braun's avatar
Matthias Braun committed
333
	for (int c_dividend = calc_buffer_size - 1; c_dividend >= 0; c_dividend--) {
334
		do_push(dividend[c_dividend], rem);
335
		do_push(0, quot);
336

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

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

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

	if (div_sign)
358
		do_negate(quot, quot);
359
360

	if (rem_sign)
361
		do_negate(rem, rem);
362
363
}

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

	/* if shifting far enough the result is zero */
375
	if (shift_cnt >= bitsize) {
376
		memset(buffer, 0, calc_buffer_size);
377
378
379
		return;
	}

380
	unsigned const shift = shift_cnt % SC_BITS;
381
	shift_cnt = shift_cnt / 4;
382
383
384

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

	/* fill with zeroes */
Matthias Braun's avatar
Matthias Braun committed
402
	for (int counter = 0; counter < shift_cnt; counter++)
403
		buffer[counter] = 0;
404
405

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

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

434
	sc_word sign = signed_shift && do_bit(val1, bitsize - 1) ? 0xF : 0;
435
436

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

Matthias Braun's avatar
Matthias Braun committed
445
446
	int shift_mod = shift_cnt &  3;
	int shift_nib = shift_cnt >> 2;
447
448

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

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

	/* the last digit is special in regard of signed/unsigned shift */
468
469
	int     bitoffset = bitsize & 3;
	sc_word msd       = sign;  /* most significant digit */
470
471
472

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

476
	const sc_word *shrs = shrs_table[msd][shift_mod];
477

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

486
	if (counter > 0)
487
		buffer[counter - 1] |= shrs[1];
488

489
	/* fill with 0xF or 0 depending on sign */
490
491
492
	for (counter++; counter < calc_buffer_size; counter++) {
		buffer[counter] = sign;
	}
493
494
}

495

496
const sc_word *sc_get_buffer(void)
497
{
498
	return calc_buffer;
499
500
}

501
502
int sc_get_buffer_length(void)
{
503
	return calc_buffer_size;
504
505
}

506
void sign_extend(sc_word *buffer, unsigned from_bits, bool is_signed)
507
{
508
509
	int bits   = from_bits - 1;
	int nibble = bits >> 2;
510

511
	if (is_signed) {
512
513
		sc_word max = max_digit[bits & 3];
		if (buffer[nibble] > max) {
514
515
			/* sign bit is set, we need sign expansion */

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

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

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

550
	assert(base > 1 && base <= 16);
551
	sc_word *sc_base = ALLOCAN(sc_word, calc_buffer_size);
552
	sc_val_from_ulong(base, sc_base);
553

554
	sc_word *val = ALLOCAN(sc_word, calc_buffer_size);
555
556
	if (buffer == NULL)
		buffer = calc_buffer;
557

558
559
	sc_zero(buffer);
	sc_zero(val);
560
561
562

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

574
		if (v >= base)
575
			return false;
576
		val[0] = v;
577
578
579

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

		/* get ready for the next letter */
		str++;
		len--;
588
	}
589

590
	if (sign < 0)
591
		do_negate(buffer, buffer);
592

593
	return true;
594
595
}

596
void sc_val_from_long(long value, sc_word *buffer)
597
{
598
	if (buffer == NULL) buffer = calc_buffer;
599
	sc_word *pos = buffer;
600

Matthias Braun's avatar
Matthias Braun committed
601
602
	char sign       = (value < 0);
	char is_minlong = value == LONG_MIN;
603

604
605
606
607
608
609
610
	/* use absolute value, special treatment of MIN_LONG to avoid overflow */
	if (sign) {
		if (is_minlong)
			value = -(value+1);
		else
			value = -value;
	}
611

612
	sc_zero(buffer);
613

614
	while ((value != 0) && (pos < buffer + calc_buffer_size)) {
615
		*pos++ = value & 0xF;
616
617
		value >>= 4;
	}
618

619
620
	if (sign) {
		if (is_minlong)
621
			do_inc(buffer, buffer);
622

623
		do_negate(buffer, buffer);
624
	}
625
626
}

627
void sc_val_from_ulong(unsigned long value, sc_word *buffer)
628
{
629
	if (buffer == NULL) buffer = calc_buffer;
630
	sc_word *pos = buffer;
631

632
633
	while (pos < buffer + calc_buffer_size) {
		*pos++ = value & 0xF;
634
635
		value >>= 4;
	}
636
637
}

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

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

658
void sc_min_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
659
{
660
	if (buffer == NULL) buffer = calc_buffer;
661
	if (!sign) {
662
		sc_zero(buffer);
663
664
665
		return;
	} else {
		sc_word *pos = buffer;
666

667
668
669
670
		unsigned bits = num_bits - 1;
		unsigned i    = 0;
		for ( ; i < bits/4; i++)
			*pos++ = 0;
671

672
		*pos++ = min_digit[bits%4];
673

674
675
676
		for (i++; (int)i <= calc_buffer_size - 1; i++)
			*pos++ = 0xF;
	}
677
678
}

679
void sc_max_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
680
{
681
	if (buffer == NULL) buffer = calc_buffer;
682
	sc_word *pos = buffer;
683

684
685
	unsigned bits = num_bits - sign;
	unsigned i    = 0;
Matthias Braun's avatar
Matthias Braun committed
686
	for ( ; i < bits/4; i++)
687
		*pos++ = 0xF;
688

689
	*pos++ = max_digit[bits%4];
690

691
	for (i++; (int)i <= calc_buffer_size - 1; i++)
692
		*pos++ = 0;
693
694
}

695
void sc_truncate(unsigned int num_bits, sc_word *buffer)
696
{
697
698
699
	sc_word *cbuffer = buffer;
	sc_word *pos     = cbuffer + (num_bits / 4);
	sc_word *end     = cbuffer + calc_buffer_size;
700
701
702

	assert(pos < end);

703
	switch (num_bits % 4) {
704
	case 0: /* nothing to do */ break;
705
706
707
	case 1: *pos++ &= 1; break;
	case 2: *pos++ &= 3; break;
	case 3: *pos++ &= 7; break;
708
709
	}

710
	for ( ; pos < end; ++pos)
711
		*pos = 0;
712
713
}

714
ir_relation sc_comp(const sc_word* const val1, const sc_word* const val2)
715
{
716
717
718
719
	int counter = calc_buffer_size - 1;

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

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

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

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

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

783
int sc_get_bit_at(const sc_word *value, unsigned pos)
784
{
785
786
	unsigned nibble = pos >> 2;
	return (value[nibble] & (1 << (pos & 3))) != 0;
787
788
}

789
void sc_set_bit_at(sc_word *value, unsigned pos)
790
791
{
	unsigned nibble = pos >> 2;
792
	value[nibble] |= 1 << (pos & 3);
793
794
}

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

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