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

Michael Beck's avatar
Michael Beck committed
6
7
/**
 * @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
32
33
34
35
static sc_word *calc_buffer = NULL; /**< buffer holding all results */
static char *output_buffer = NULL;  /**< buffer for output */
static unsigned bit_pattern_size;   /**< maximum number of bits */
static unsigned calc_buffer_size;   /**< size of internally stored values */
static unsigned 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);
}

87
void sc_not(const sc_word *val, sc_word *buffer)
88
{
89
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
Matthias Braun's avatar
Matthias Braun committed
90
		buffer[counter] = val[counter] ^ SC_MASK;
91
92
}

93
void sc_or(const sc_word *val1, const sc_word *val2, sc_word *buffer)
94
{
95
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
96
		buffer[counter] = val1[counter] | val2[counter];
97
98
}

99
void sc_xor(const sc_word *val1, const sc_word *val2, sc_word *buffer)
100
{
101
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
102
		buffer[counter] = val1[counter] ^ val2[counter];
103
104
}

105
void sc_and(const sc_word *val1, const sc_word *val2, sc_word *buffer)
106
{
107
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
108
		buffer[counter] = val1[counter] & val2[counter];
109
110
}

111
void sc_andnot(const sc_word *val1, const sc_word *val2, sc_word *buffer)
112
{
113
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter)
Matthias Braun's avatar
Matthias Braun committed
114
		buffer[counter] = val1[counter] & (SC_MASK ^ val2[counter]);
115
116
}

Michael Beck's avatar
Michael Beck committed
117
118
119
/**
 * Implements a fast ADD + 1
 */
120
static void sc_inc(const sc_word *val, sc_word *buffer)
121
{
122
	unsigned counter = 0;
123
	while (counter++ < calc_buffer_size) {
124
125
		if (*val == 15) {
			*buffer++ = 0;
126
127
			val++;
		} else {
128
129
			/* No carry here, *val != 15 */
			*buffer = *val + 1;
130
131
132
133
134
			return;
		}
	}
	/* here a carry could be lost, this is intended because this should
	 * happen only when a value changes sign. */
135
136
}

137
void sc_neg(const sc_word *val, sc_word *buffer)
138
{
139
140
	sc_not(val, buffer);
	sc_inc(buffer, buffer);
141
142
}

143
void sc_add(const sc_word *val1, const sc_word *val2, sc_word *buffer)
144
{
145
146
	sc_word carry = 0;
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter) {
147
148
149
		unsigned const sum = val1[counter] + val2[counter] + carry;
		buffer[counter] = SC_RESULT(sum);
		carry           = SC_CARRY(sum);
150
	}
151
152
}

153
void sc_sub(const sc_word *val1, const sc_word *val2, sc_word *buffer)
154
{
155
	/* intermediate buffer to hold -val2 */
156
	sc_word *temp_buffer = ALLOCAN(sc_word, calc_buffer_size);
Michael Beck's avatar
Michael Beck committed
157

158
159
	sc_neg(val2, temp_buffer);
	sc_add(val1, temp_buffer, buffer);
Michael Beck's avatar
Michael Beck committed
160
161
}

162
void sc_mul(const sc_word *val1, const sc_word *val2, sc_word *buffer)
163
{
164
165
166
	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);
167

168
	/* init result buffer to zeros */
169
	memset(temp_buffer, 0, calc_buffer_size);
170
171
172

	/* the multiplication works only for positive values, for negative values *
	 * it is necessary to negate them and adjust the result accordingly       */
173
	bool sign = false;
174
	if (sc_is_negative(val1)) {
175
		sc_neg(val1, neg_val1);
176
		val1 = neg_val1;
177
		sign = !sign;
178
	}
179
	if (sc_is_negative(val2)) {
180
		sc_neg(val2, neg_val2);
181
		val2 = neg_val2;
182
		sign = !sign;
183
184
	}

185
	for (unsigned c_outer = 0; c_outer < max_value_size; c_outer++) {
Matthias Braun's avatar
Matthias Braun committed
186
187
188
189
		sc_word outer = val2[c_outer];
		if (outer == 0)
			continue;
		unsigned carry = 0; /* container for carries */
190
		for (unsigned c_inner = 0; c_inner < max_value_size; c_inner++) {
Matthias Braun's avatar
Matthias Braun committed
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
			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);
216
		}
Matthias Braun's avatar
Matthias Braun committed
217
218
219
220

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

	if (sign)
224
		sc_neg(temp_buffer, buffer);
225
226
	else
		memcpy(buffer, temp_buffer, calc_buffer_size);
227
228
}

Michael Beck's avatar
Michael Beck committed
229
/**
230
 * Shift the buffer to left and add an sc digit
Michael Beck's avatar
Michael Beck committed
231
 */
232
static void sc_push(sc_word digit, sc_word *buffer)
233
{
234
	for (unsigned counter = calc_buffer_size - 1; counter-- > 0; ) {
235
236
237
		buffer[counter+1] = buffer[counter];
	}
	buffer[0] = digit;
238
239
}

240
241
bool sc_divmod(const sc_word *dividend, const sc_word *divisor,
               sc_word *quot, sc_word *rem)
242
{
243
244
	assert(quot != dividend && quot != divisor);
	assert(rem != dividend && rem != divisor);
245
	/* clear result buffer */
246
247
	memset(quot, 0, calc_buffer_size);
	memset(rem, 0, calc_buffer_size);
248

249
250
	/* division by zero is not allowed */
	assert(!sc_is_zero(divisor, calc_buffer_size*SC_BITS));
251
252

	/* if the dividend is zero result is zero (quot is zero) */
253
	if (sc_is_zero(dividend, calc_buffer_size*SC_BITS))
254
		return false;
255

256
257
	bool     div_sign = false;
	bool     rem_sign = false;
258
	sc_word *neg_val1 = ALLOCAN(sc_word, calc_buffer_size);
259
	if (sc_is_negative(dividend)) {
260
		sc_neg(dividend, neg_val1);
261
262
		div_sign = !div_sign;
		rem_sign = !rem_sign;
263
264
265
		dividend = neg_val1;
	}

266
	sc_word *neg_val2 = ALLOCAN(sc_word, calc_buffer_size);
267
	sc_neg(divisor, neg_val2);
268
	const sc_word *minus_divisor;
269
	if (sc_is_negative(divisor)) {
270
		div_sign = !div_sign;
271
272
		minus_divisor = divisor;
		divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
273
	} else {
274
		minus_divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
275
	}
276
277
278
279

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

284
	case ir_relation_less: /* dividend < divisor */
285
		memcpy(rem, dividend, calc_buffer_size);
286
287
288
289
290
291
		goto end;

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

292
	for (unsigned c_dividend = calc_buffer_size; c_dividend-- > 0; ) {
293
294
		sc_push(dividend[c_dividend], rem);
		sc_push(0, quot);
295

Matthias Braun's avatar
Matthias Braun committed
296
297
		if (sc_comp(rem, divisor) != ir_relation_less) {
			/* remainder >= divisor */
298
299
			/* subtract until the remainder becomes negative, this should
			 * be faster than comparing remainder with divisor  */
300
			sc_add(rem, minus_divisor, rem);
301

302
			while (!sc_is_negative(rem)) {
303
				/* TODO can this generate carry or is masking redundant? */
304
				quot[0] = SC_RESULT(quot[0] + 1);
305
				sc_add(rem, minus_divisor, rem);
306
307
308
			}

			/* subtracted one too much */
309
			sc_add(rem, divisor, rem);
310
311
312
313
		}
	}
end:
	if (div_sign)
314
		sc_neg(quot, quot);
315
316

	if (rem_sign)
317
		sc_neg(rem, rem);
318
319
320
321

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

Michael Beck's avatar
Michael Beck committed
324
325
326
327
/**
 * Implements a Shift Left, which can either preserve the sign bit
 * or not.
 */
328
329
static void do_shl(const sc_word *val1, sc_word *buffer, unsigned shift_cnt,
                   unsigned bitsize, bool is_signed)
330
{
331
	assert(buffer != val1);
332
	assert(!sc_is_negative(val1) || is_signed);
333
334

	/* if shifting far enough the result is zero */
335
	if (shift_cnt >= bitsize) {
336
		memset(buffer, 0, calc_buffer_size);
337
338
339
		return;
	}

340
	unsigned const shift = shift_cnt % SC_BITS;
341
	shift_cnt = shift_cnt / SC_BITS;
342
343
344

	/* shift the single digits some bytes (offset) and some bits (table)
	 * to the left */
345
	unsigned carry = 0;
346
347
	for (unsigned counter = 0; counter < bitsize/SC_BITS - shift_cnt;
	     ++counter) {
348
349
350
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
		carry = SC_CARRY(shl);
351
	}
352
353
	unsigned counter   = bitsize/SC_BITS - shift_cnt;
	unsigned bitoffset = 0;
354
	if (bitsize%SC_BITS > 0) {
355
356
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
357
358
359
360
361
362
		bitoffset = counter;
	} else {
		bitoffset = counter - 1;
	}

	/* fill with zeroes */
363
	for (unsigned counter = 0; counter < shift_cnt; counter++)
364
		buffer[counter] = 0;
365
366

	/* if the mode was signed, change sign when the mode's msb is now 1 */
367
	shift_cnt = bitoffset + shift_cnt;
368
	bitoffset = (bitsize-1) % SC_BITS;
369
	if (is_signed && _bitisset(buffer[shift_cnt], bitoffset)) {
370
		/* this sets the upper bits of the leftmost digit */
Matthias Braun's avatar
Matthias Braun committed
371
		buffer[shift_cnt] |= min_digit(bitoffset);
372
373
		for (unsigned counter = shift_cnt+1; counter < calc_buffer_size;
		     ++counter) {
Matthias Braun's avatar
Matthias Braun committed
374
			buffer[counter] = SC_MASK;
375
		}
376
	} else if (is_signed && !_bitisset(buffer[shift_cnt], bitoffset)) {
377
		/* this clears the upper bits of the leftmost digit */
Matthias Braun's avatar
Matthias Braun committed
378
		buffer[shift_cnt] &= max_digit(bitoffset);
379
380
		for (unsigned counter = shift_cnt+1; counter < calc_buffer_size;
		     ++counter) {
381
			buffer[counter] = 0;
382
383
		}
	}
384
385
}

Michael Beck's avatar
Michael Beck committed
386
387
388
389
/**
 * Implements a Shift Right, which can either preserve the sign bit
 * or not.
 *
390
 * @param bitsize   bitsize of the value to be shifted
Michael Beck's avatar
Michael Beck committed
391
 */
392
393
static bool do_shr(const sc_word *val1, sc_word *buffer, unsigned shift_cnt,
                   unsigned bitsize, bool is_signed, bool signed_shift)
394
{
395
	bool    carry_flag = false;
396
	sc_word sign = signed_shift && sc_get_bit_at(val1, bitsize-1) ? SC_MASK : 0;
397
398

	/* if shifting far enough the result is either 0 or -1 */
399
	if (shift_cnt >= bitsize) {
400
		if (!sc_is_zero(val1, calc_buffer_size*SC_BITS)) {
Matthias Braun's avatar
Matthias Braun committed
401
			carry_flag = true;
402
403
		}
		memset(buffer, sign, calc_buffer_size);
404
		return carry_flag;
405
406
	}

407
408
	unsigned shift_mod = shift_cnt % SC_BITS;
	unsigned shift_nib = shift_cnt / SC_BITS;
409
410

	/* check if any bits are lost, and set carry_flag if so */
411
	for (unsigned counter = 0; counter < shift_nib; ++counter) {
412
		if (val1[counter] != 0) {
Matthias Braun's avatar
Matthias Braun committed
413
			carry_flag = true;
414
415
416
			break;
		}
	}
417
	if ((val1[shift_nib] & ((1<<shift_mod)-1)) != 0)
Matthias Braun's avatar
Matthias Braun committed
418
		carry_flag = true;
419

420
	/* shift digits to the right with offset, carry and all */
421
	buffer[0] = shrs_table[val1[shift_nib]][shift_mod][0];
422
	unsigned counter;
423
424
	for (counter = 1; counter < ((bitsize + 3) / SC_BITS) - shift_nib;
	     ++counter) {
425
		const sc_word *shrs = shrs_table[val1[counter+shift_nib]][shift_mod];
426
427
		buffer[counter]      = shrs[0];
		buffer[counter - 1] |= shrs[1];
428
429
430
	}

	/* the last digit is special in regard of signed/unsigned shift */
431
432
	unsigned bitoffset = bitsize % SC_BITS;
	sc_word  msd       = sign;  /* most significant digit */
433
434
435

	/* 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
436
		msd &= max_digit(bitoffset);
437
438
	}

439
	const sc_word *shrs = shrs_table[msd][shift_mod];
440

441
442
	/* signed shift and signed mode and negative value means all bits to the
	 * left are set */
Matthias Braun's avatar
Matthias Braun committed
443
	if (signed_shift && sign == SC_MASK) {
Matthias Braun's avatar
Matthias Braun committed
444
		buffer[counter] = shrs[0] | min_digit(bitoffset);
445
446
447
448
	} else {
		buffer[counter] = shrs[0];
	}

449
	if (counter > 0)
450
		buffer[counter - 1] |= shrs[1];
451

452
	/* fill with 0xF or 0 depending on sign */
453
454
455
	for (counter++; counter < calc_buffer_size; counter++) {
		buffer[counter] = sign;
	}
456
457

	return carry_flag;
458
459
}

460
const sc_word *sc_get_buffer(void)
461
{
462
	return calc_buffer;
463
464
}

465
unsigned sc_get_buffer_length(void)
466
{
467
	return calc_buffer_size;
468
469
}

470
void sign_extend(sc_word *buffer, unsigned from_bits, bool is_signed)
471
{
472
473
	unsigned bits   = from_bits - 1;
	unsigned nibble = bits / SC_BITS;
474

475
	if (is_signed) {
476
		sc_word max = max_digit(bits % SC_BITS);
477
		if (buffer[nibble] > max) {
478
479
			/* sign bit is set, we need sign expansion */

480
			for (unsigned i = nibble + 1; i < calc_buffer_size; ++i)
Matthias Braun's avatar
Matthias Braun committed
481
				buffer[i] = SC_MASK;
482
			buffer[nibble] |= sex_digit(bits % SC_BITS);
483
484
		} else {
			/* set all bits to zero */
485
			for (unsigned i = nibble + 1; i < calc_buffer_size; ++i)
486
				buffer[i] = 0;
487
			buffer[nibble] &= zex_digit(bits % SC_BITS);
488
489
490
		}
	} else {
		/* do zero extension */
491
		for (unsigned i = nibble + 1; i < calc_buffer_size; ++i)
492
			buffer[i] = 0;
493
		buffer[nibble] &= zex_digit(bits % SC_BITS);
494
	}
495
496
}

497
/** Ensures that our source character set conforms to ASCII for a-f, A-F, 0-9 */
498
static inline void check_ascii(void)
499
{
Matthias Braun's avatar
Matthias Braun committed
500
501
502
503
	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);
504
}
505

506
bool sc_val_from_str(bool negative, unsigned base, const char *str, size_t len,
507
                     sc_word *buffer)
508
509
510
511
{
	assert(str != NULL);
	assert(len > 0);
	check_ascii();
512

513
	assert(base > 1 && base <= 16);
514
	sc_word *sc_base = ALLOCAN(sc_word, calc_buffer_size);
515
	sc_val_from_ulong(base, sc_base);
516

517
	sc_word *val = ALLOCAN(sc_word, calc_buffer_size);
518

519
520
	sc_zero(buffer);
	sc_zero(val);
521
522
523

	/* BEGIN string evaluation, from left to right */
	while (len > 0) {
524
525
526
527
		char c = *str;
		unsigned v;
		if (c >= '0' && c <= '9')
			v = c - '0';
528
529
530
531
		else if (c >= 'A' && c <= 'F')
			v = c - 'A' + 10;
		else if (c >= 'a' && c <= 'f')
			v = c - 'a' + 10;
532
		else
533
			return false;
534

535
		if (v >= base)
536
			return false;
537
		val[0] = v;
538
539
540

		/* Radix conversion from base b to base B:
		 *  (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
541
		/* multiply current value with base */
542
		sc_mul(sc_base, buffer, buffer);
543
		/* add next digit to current value  */
544
		sc_add(val, buffer, buffer);
545
546
547
548

		/* get ready for the next letter */
		str++;
		len--;
549
	}
550

551
	if (negative)
552
		sc_neg(buffer, buffer);
553

554
	return true;
555
556
}

557
void sc_val_from_long(long value, sc_word *buffer)
558
{
559
	sc_word *pos = buffer;
560

561
562
	bool sign       = value < 0;
	bool is_minlong = value == LONG_MIN;
563

564
565
566
567
568
569
570
	/* use absolute value, special treatment of MIN_LONG to avoid overflow */
	if (sign) {
		if (is_minlong)
			value = -(value+1);
		else
			value = -value;
	}
571

572
	sc_zero(buffer);
573

574
	while ((value != 0) && (pos < buffer + calc_buffer_size)) {
Matthias Braun's avatar
Matthias Braun committed
575
		*pos++ = value & SC_MASK;
576
		value >>= SC_BITS;
577
	}
578

579
580
	if (sign) {
		if (is_minlong)
581
			sc_inc(buffer, buffer);
582

583
		sc_neg(buffer, buffer);
584
	}
585
586
}

587
void sc_val_from_ulong(unsigned long value, sc_word *buffer)
588
{
589
	sc_word *pos = buffer;
590

591
	while (pos < buffer + calc_buffer_size) {
Matthias Braun's avatar
Matthias Braun committed
592
		*pos++ = value & SC_MASK;
593
		value >>= SC_BITS;
594
	}
595
596
}

597
long sc_val_to_long(const sc_word *val)
598
{
Andreas Zwinkau's avatar
Andreas Zwinkau committed
599
	unsigned long l = 0;
600
601
	unsigned max_buffer_index = (sizeof(long)*8)/SC_BITS;
	for (unsigned i = max_buffer_index; i-- > 0; ) {
602
603
		assert(l <= (ULONG_MAX>>SC_BITS) && "signed shift overflow");
		l = (l << SC_BITS) + val[i];
604
605
	}
	return l;
606
607
}

608
uint64_t sc_val_to_uint64(const sc_word *val)
609
610
{
	uint64_t res = 0;
611
	for (unsigned i = calc_buffer_size; i-- > 0; ) {
612
		res = (res << SC_BITS) + val[i];
613
	}
Manuel Mohr's avatar
Manuel Mohr committed
614
	return res;
615
616
}

617
void sc_min_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
618
{
619
	if (!sign) {
620
		sc_zero(buffer);
621
622
623
		return;
	} else {
		sc_word *pos = buffer;
624

625
626
		unsigned bits = num_bits - 1;
		unsigned i    = 0;
627
		for ( ; i < bits/SC_BITS; i++)
628
			*pos++ = 0;
629

630
		*pos++ = min_digit(bits%SC_BITS);
631

632
		for (i++; i <= calc_buffer_size - 1; i++)
Matthias Braun's avatar
Matthias Braun committed
633
			*pos++ = SC_MASK;
634
	}
635
636
}

637
void sc_max_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
638
{
639
	sc_word *pos = buffer;
640

641
642
	unsigned bits = num_bits - sign;
	unsigned i    = 0;
643
	for ( ; i < bits/SC_BITS; i++)
Matthias Braun's avatar
Matthias Braun committed
644
		*pos++ = SC_MASK;
645

646
	*pos++ = max_digit(bits%SC_BITS);
647

648
	for (i++; i <= calc_buffer_size - 1; i++)
649
		*pos++ = 0;
650
651
}

652
void sc_truncate(unsigned num_bits, sc_word *buffer)
653
{
654
	sc_word *cbuffer = buffer;
655
	sc_word *pos     = cbuffer + (num_bits / SC_BITS);
656
	sc_word *end     = cbuffer + calc_buffer_size;
657
658
659

	assert(pos < end);

660
	switch (num_bits % SC_BITS) {
661
	case 0: /* nothing to do */ break;
662
663
664
	case 1: *pos++ &= 1; break;
	case 2: *pos++ &= 3; break;
	case 3: *pos++ &= 7; break;
665
666
	}

667
	for ( ; pos < end; ++pos)
668
		*pos = 0;
669
670
}

671
ir_relation sc_comp(const sc_word* const val1, const sc_word* const val2)
672
{
673
674
	/* compare signs first:
	 * the loop below can only compare values of the same sign! */
675
676
677
678
	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;
679
680
681

	/* loop until two digits differ, the values are equal if there
	 * are no such two digits */
682
	unsigned counter = calc_buffer_size - 1;
683
	while (val1[counter] == val2[counter]) {
684
685
		if (counter == 0)
			return ir_relation_equal;
686
687
688
689
690
691
		counter--;
	}

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

696
int sc_get_highest_set_bit(const sc_word *value)
697
{
698
699
	int high = calc_buffer_size * SC_BITS - 1;
	for (unsigned counter = calc_buffer_size; counter-- > 0; ) {
700
		if (value[counter] == 0)
701
			high -= SC_BITS;
702
		else {
703
704
705
			if (value[counter] > 7) return high;
			else if (value[counter] > 3) return high - 1;
			else if (value[counter] > 1) return high - 2;
706
707
708
709
			else return high - 3;
		}
	}
	return high;
Matthias Heil's avatar
Matthias Heil committed
710
711
}

712
int sc_get_lowest_set_bit(const sc_word *value)
713
{
714
715
	int low = 0;
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter) {
716
		switch (value[counter]) {
717
718
719
720
721
722
723
724
		case 1:
		case 3:
		case 5:
		case 7:
		case 9:
		case 11:
		case 13:
		case 15:
725
			return low;
726
727
728
729
		case 2:
		case 6:
		case 10:
		case 14:
730
			return low + 1;
731
732
		case 4:
		case 12:
733
			return low + 2;
734
		case 8:
735
736
			return low + 3;
		default:
737
			low += SC_BITS;
738
739
740
		}
	}
	return -1;
Matthias Heil's avatar
Matthias Heil committed
741
742
}

743
bool sc_get_bit_at(const sc_word *value, unsigned pos)
744
{
745
746
	unsigned nibble = pos / SC_BITS;
	return value[nibble] & (1 << (pos % SC_BITS));
747
748
}

749
void sc_set_bit_at(sc_word *value, unsigned pos)
750
{
751
752
	unsigned nibble = pos / SC_BITS;
	value[nibble] |= 1 << (pos % SC_BITS);
753
754
}

755
void sc_clear_bit_at(sc_word *value, unsigned pos)
Matthias Braun's avatar
Matthias Braun committed
756
{
757
758
	unsigned nibble = pos / SC_BITS;
	value[nibble] &= ~(1 << (pos % SC_BITS));
Matthias Braun's avatar
Matthias Braun committed
759
760
}

761
bool sc_is_zero(const sc_word *value, unsigned bits)
762
{
Matthias Braun's avatar
Matthias Braun committed
763
764
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
765
		if (value[i] != 0)
766
			return false;
767
	}
Matthias Braun's avatar
Matthias Braun committed
768
	sc_word mask = max_digit(bits%SC_BITS);
769
	return mask == 0 || (value[i] & mask) == 0;
Matthias Braun's avatar
Matthias Braun committed
770
771
}

772
bool sc_is_all_one(const sc_word *value, unsigned bits)
Matthias Braun's avatar
Matthias Braun committed
773
774
775
{
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
Matthias Braun's avatar
Matthias Braun committed
776
		if (value[i] != SC_MASK)
Matthias Braun's avatar
Matthias Braun committed
777
778
			return false;
	}
Matthias Braun's avatar
Matthias Braun committed
779
	sc_word mask = max_digit(bits%SC_BITS);
780
	return mask == 0 || (value[i] & mask) == mask;
781