strcalc.c 27.5 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
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);
}

82
void sc_not(const sc_word *val, sc_word *buffer)
83
{
84
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
Matthias Braun's avatar
Matthias Braun committed
85
		buffer[counter] = val[counter] ^ SC_MASK;
86
87
}

88
void sc_or(const sc_word *val1, const sc_word *val2, sc_word *buffer)
89
{
90
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
91
		buffer[counter] = val1[counter] | val2[counter];
92
93
}

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

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

106
void sc_andnot(const sc_word *val1, const sc_word *val2, sc_word *buffer)
107
{
108
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter)
Matthias Braun's avatar
Matthias Braun committed
109
		buffer[counter] = val1[counter] & (SC_MASK ^ val2[counter]);
110
111
}

Matthias Braun's avatar
Matthias Braun committed
112
void sc_inc(const sc_word *val, sc_word *buffer)
113
{
114
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter) {
115
116
117
118
119
120
121
122
		sc_word v = val[counter];
		if (v < SC_MASK) {
			buffer[counter] = v+1;
			/* copy the rest of the buffer if necessary */
			if (buffer != val)
				memcpy(&buffer[counter+1], &val[counter+1],
				       calc_buffer_size-(counter+1));
			break;
123
		}
124
		buffer[counter] = 0;
125
	}
126
127
}

128
void sc_neg(const sc_word *val, sc_word *buffer)
129
{
130
131
	sc_not(val, buffer);
	sc_inc(buffer, buffer);
132
133
}

134
void sc_add(const sc_word *val1, const sc_word *val2, sc_word *buffer)
135
{
136
137
	sc_word carry = 0;
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter) {
138
139
140
		unsigned const sum = val1[counter] + val2[counter] + carry;
		buffer[counter] = SC_RESULT(sum);
		carry           = SC_CARRY(sum);
141
	}
142
143
}

144
void sc_sub(const sc_word *val1, const sc_word *val2, sc_word *buffer)
145
{
146
	/* intermediate buffer to hold -val2 */
147
	sc_word *temp_buffer = ALLOCAN(sc_word, calc_buffer_size);
Michael Beck's avatar
Michael Beck committed
148

149
150
	sc_neg(val2, temp_buffer);
	sc_add(val1, temp_buffer, buffer);
Michael Beck's avatar
Michael Beck committed
151
152
}

153
void sc_mul(const sc_word *val1, const sc_word *val2, sc_word *buffer)
154
{
155
	sc_word *temp_buffer = ALLOCANZ(sc_word, calc_buffer_size);
156
157
	sc_word *neg_val1    = ALLOCAN(sc_word, calc_buffer_size);
	sc_word *neg_val2    = ALLOCAN(sc_word, calc_buffer_size);
158
159
160

	/* the multiplication works only for positive values, for negative values *
	 * it is necessary to negate them and adjust the result accordingly       */
161
	bool sign = false;
162
	if (sc_is_negative(val1)) {
163
		sc_neg(val1, neg_val1);
164
		val1 = neg_val1;
165
		sign = !sign;
166
	}
167
	if (sc_is_negative(val2)) {
168
		sc_neg(val2, neg_val2);
169
		val2 = neg_val2;
170
		sign = !sign;
171
172
	}

173
	for (unsigned c_outer = 0; c_outer < max_value_size; c_outer++) {
Matthias Braun's avatar
Matthias Braun committed
174
175
176
177
		sc_word outer = val2[c_outer];
		if (outer == 0)
			continue;
		unsigned carry = 0; /* container for carries */
178
		for (unsigned c_inner = 0; c_inner < max_value_size; c_inner++) {
Matthias Braun's avatar
Matthias Braun committed
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
			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);
204
		}
Matthias Braun's avatar
Matthias Braun committed
205
206
207
208

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

	if (sign)
212
		sc_neg(temp_buffer, buffer);
213
214
	else
		memcpy(buffer, temp_buffer, calc_buffer_size);
215
216
}

Michael Beck's avatar
Michael Beck committed
217
/**
218
 * Shift the buffer to left and add an sc digit
Michael Beck's avatar
Michael Beck committed
219
 */
220
static void sc_push(sc_word digit, sc_word *buffer)
221
{
222
	for (unsigned counter = calc_buffer_size - 1; counter-- > 0; ) {
223
224
225
		buffer[counter+1] = buffer[counter];
	}
	buffer[0] = digit;
226
227
}

228
229
bool sc_divmod(const sc_word *dividend, const sc_word *divisor,
               sc_word *quot, sc_word *rem)
230
{
231
232
	assert(quot != dividend && quot != divisor);
	assert(rem != dividend && rem != divisor);
233
	/* clear result buffer */
234
235
	sc_zero(quot);
	sc_zero(rem);
236

237
238
	/* division by zero is not allowed */
	assert(!sc_is_zero(divisor, calc_buffer_size*SC_BITS));
239
240

	/* if the dividend is zero result is zero (quot is zero) */
241
	if (sc_is_zero(dividend, calc_buffer_size*SC_BITS))
242
		return false;
243

244
245
	bool     div_sign = false;
	bool     rem_sign = false;
246
	sc_word *neg_val1 = ALLOCAN(sc_word, calc_buffer_size);
247
	if (sc_is_negative(dividend)) {
248
		sc_neg(dividend, neg_val1);
249
250
		div_sign = !div_sign;
		rem_sign = !rem_sign;
251
252
253
		dividend = neg_val1;
	}

254
	sc_word *neg_val2 = ALLOCAN(sc_word, calc_buffer_size);
255
	sc_neg(divisor, neg_val2);
256
	const sc_word *minus_divisor;
257
	if (sc_is_negative(divisor)) {
258
		div_sign = !div_sign;
259
260
		minus_divisor = divisor;
		divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
261
	} else {
262
		minus_divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
263
	}
264
265
266
267

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

272
	case ir_relation_less: /* dividend < divisor */
273
		memcpy(rem, dividend, calc_buffer_size);
274
275
276
277
278
279
		goto end;

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

280
	for (unsigned c_dividend = calc_buffer_size; c_dividend-- > 0; ) {
281
282
		sc_push(dividend[c_dividend], rem);
		sc_push(0, quot);
283

Matthias Braun's avatar
Matthias Braun committed
284
285
		if (sc_comp(rem, divisor) != ir_relation_less) {
			/* remainder >= divisor */
286
287
			/* subtract until the remainder becomes negative, this should
			 * be faster than comparing remainder with divisor  */
288
			sc_add(rem, minus_divisor, rem);
289

290
			while (!sc_is_negative(rem)) {
291
				/* TODO can this generate carry or is masking redundant? */
292
				quot[0] = SC_RESULT(quot[0] + 1);
293
				sc_add(rem, minus_divisor, rem);
294
295
296
			}

			/* subtracted one too much */
297
			sc_add(rem, divisor, rem);
298
299
300
301
		}
	}
end:
	if (div_sign)
302
		sc_neg(quot, quot);
303
304

	if (rem_sign)
305
		sc_neg(rem, rem);
306
307
308
309

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

Michael Beck's avatar
Michael Beck committed
312
313
314
315
/**
 * Implements a Shift Left, which can either preserve the sign bit
 * or not.
 */
316
317
static void do_shl(const sc_word *val1, sc_word *buffer, unsigned shift_cnt,
                   unsigned bitsize, bool is_signed)
318
{
319
	assert(buffer != val1);
320
321

	/* if shifting far enough the result is zero */
322
	if (shift_cnt >= bitsize) {
323
		sc_zero(buffer);
324
325
326
		return;
	}

327
	unsigned const shift = shift_cnt % SC_BITS;
328
	shift_cnt = shift_cnt / SC_BITS;
329
330
331

	/* shift the single digits some bytes (offset) and some bits (table)
	 * to the left */
332
	unsigned carry = 0;
333
334
	for (unsigned counter = 0; counter < bitsize/SC_BITS - shift_cnt;
	     ++counter) {
335
336
337
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
		carry = SC_CARRY(shl);
338
	}
339
340
	unsigned counter   = bitsize/SC_BITS - shift_cnt;
	unsigned bitoffset = 0;
341
	if (bitsize%SC_BITS > 0) {
342
343
		unsigned const shl = val1[counter] << shift | carry;
		buffer[counter + shift_cnt] = SC_RESULT(shl);
344
345
346
347
348
349
		bitoffset = counter;
	} else {
		bitoffset = counter - 1;
	}

	/* fill with zeroes */
350
	for (unsigned counter = 0; counter < shift_cnt; counter++)
351
		buffer[counter] = 0;
352
353

	/* if the mode was signed, change sign when the mode's msb is now 1 */
354
	shift_cnt = bitoffset + shift_cnt;
355
	bitoffset = (bitsize-1) % SC_BITS;
356
	if (is_signed && _bitisset(buffer[shift_cnt], bitoffset)) {
357
		/* this sets the upper bits of the leftmost digit */
Matthias Braun's avatar
Matthias Braun committed
358
		buffer[shift_cnt] |= min_digit(bitoffset);
359
360
		for (unsigned counter = shift_cnt+1; counter < calc_buffer_size;
		     ++counter) {
Matthias Braun's avatar
Matthias Braun committed
361
			buffer[counter] = SC_MASK;
362
		}
363
	} else if (is_signed && !_bitisset(buffer[shift_cnt], bitoffset)) {
364
		/* this clears the upper bits of the leftmost digit */
Matthias Braun's avatar
Matthias Braun committed
365
		buffer[shift_cnt] &= max_digit(bitoffset);
366
367
		for (unsigned counter = shift_cnt+1; counter < calc_buffer_size;
		     ++counter) {
368
			buffer[counter] = 0;
369
370
		}
	}
371
372
}

Michael Beck's avatar
Michael Beck committed
373
374
375
376
/**
 * Implements a Shift Right, which can either preserve the sign bit
 * or not.
 *
377
 * @param bitsize   bitsize of the value to be shifted
Michael Beck's avatar
Michael Beck committed
378
 */
379
380
static bool do_shr(const sc_word *val1, sc_word *buffer, unsigned shift_cnt,
                   unsigned bitsize, bool is_signed, bool signed_shift)
381
{
382
	bool    carry_flag = false;
383
	sc_word sign = signed_shift && sc_get_bit_at(val1, bitsize-1) ? SC_MASK : 0;
384
385

	/* if shifting far enough the result is either 0 or -1 */
386
	if (shift_cnt >= bitsize) {
387
		if (!sc_is_zero(val1, calc_buffer_size*SC_BITS)) {
Matthias Braun's avatar
Matthias Braun committed
388
			carry_flag = true;
389
390
		}
		memset(buffer, sign, calc_buffer_size);
391
		return carry_flag;
392
393
	}

394
395
	unsigned shift_mod = shift_cnt % SC_BITS;
	unsigned shift_nib = shift_cnt / SC_BITS;
396
397

	/* check if any bits are lost, and set carry_flag if so */
398
	for (unsigned counter = 0; counter < shift_nib; ++counter) {
399
		if (val1[counter] != 0) {
Matthias Braun's avatar
Matthias Braun committed
400
			carry_flag = true;
401
402
403
			break;
		}
	}
404
	if ((val1[shift_nib] & ((1<<shift_mod)-1)) != 0)
Matthias Braun's avatar
Matthias Braun committed
405
		carry_flag = true;
406

407
	/* shift digits to the right with offset, carry and all */
408
	buffer[0] = shrs_table[val1[shift_nib]][shift_mod][0];
409
	unsigned counter;
410
411
	for (counter = 1; counter < ((bitsize + 3) / SC_BITS) - shift_nib;
	     ++counter) {
412
		const sc_word *shrs = shrs_table[val1[counter+shift_nib]][shift_mod];
413
414
		buffer[counter]      = shrs[0];
		buffer[counter - 1] |= shrs[1];
415
416
417
	}

	/* the last digit is special in regard of signed/unsigned shift */
418
419
	unsigned bitoffset = bitsize % SC_BITS;
	sc_word  msd       = sign;  /* most significant digit */
420
421
422

	/* 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
423
		msd &= max_digit(bitoffset);
424
425
	}

426
	const sc_word *shrs = shrs_table[msd][shift_mod];
427

428
429
	/* signed shift and signed mode and negative value means all bits to the
	 * left are set */
Matthias Braun's avatar
Matthias Braun committed
430
	if (signed_shift && sign == SC_MASK) {
Matthias Braun's avatar
Matthias Braun committed
431
		buffer[counter] = shrs[0] | min_digit(bitoffset);
432
433
434
435
	} else {
		buffer[counter] = shrs[0];
	}

436
	if (counter > 0)
437
		buffer[counter - 1] |= shrs[1];
438

439
	/* fill with 0xF or 0 depending on sign */
440
441
442
	for (counter++; counter < calc_buffer_size; counter++) {
		buffer[counter] = sign;
	}
443
444

	return carry_flag;
445
446
}

447
const sc_word *sc_get_buffer(void)
448
{
449
	return calc_buffer;
450
451
}

452
unsigned sc_get_buffer_length(void)
453
{
454
	return calc_buffer_size;
455
456
}

457
void sc_zero_extend(sc_word *buffer, unsigned from_bits)
458
{
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
	unsigned bit  = from_bits % SC_BITS;
	unsigned word = from_bits / SC_BITS;
	if (bit > 0) {
		memset(&buffer[word+1], 0, calc_buffer_size-(word+1));
		buffer[word] &= max_digit(bit);
	} else {
		memset(&buffer[word], 0, calc_buffer_size-word);
	}
}

void sc_sign_extend(sc_word *buffer, unsigned from_bits)
{
	unsigned bits     = from_bits - 1;
	bool     sign_bit = sc_get_bit_at(buffer, bits);
	if (sign_bit) {
		/* sign bit is set, we need sign extension */
		unsigned word = bits / SC_BITS;
		for (unsigned i = word + 1; i < calc_buffer_size; ++i)
			buffer[i] = SC_MASK;
		buffer[word] |= sex_digit(bits % SC_BITS);
479
	} else {
480
		sc_zero_extend(buffer, from_bits);
481
	}
482
483
}

484
/** Ensures that our source character set conforms to ASCII for a-f, A-F, 0-9 */
485
static inline void check_ascii(void)
486
{
Matthias Braun's avatar
Matthias Braun committed
487
488
489
490
	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);
491
}
492

493
bool sc_val_from_str(bool negative, unsigned base, const char *str, size_t len,
494
                     sc_word *buffer)
495
496
497
498
{
	assert(str != NULL);
	assert(len > 0);
	check_ascii();
499

500
	assert(base > 1 && base <= 16);
501
	sc_word *sc_base = ALLOCAN(sc_word, calc_buffer_size);
502
	sc_val_from_ulong(base, sc_base);
503

504
	sc_word *val = ALLOCANZ(sc_word, calc_buffer_size);
505

506
	sc_zero(buffer);
507
508
509

	/* BEGIN string evaluation, from left to right */
	while (len > 0) {
510
511
512
513
		char c = *str;
		unsigned v;
		if (c >= '0' && c <= '9')
			v = c - '0';
514
515
516
517
		else if (c >= 'A' && c <= 'F')
			v = c - 'A' + 10;
		else if (c >= 'a' && c <= 'f')
			v = c - 'a' + 10;
518
		else
519
			return false;
520

521
		if (v >= base)
522
			return false;
523
		val[0] = v;
524
525
526

		/* Radix conversion from base b to base B:
		 *  (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
527
		/* multiply current value with base */
528
		sc_mul(sc_base, buffer, buffer);
529
		/* add next digit to current value  */
530
		sc_add(val, buffer, buffer);
531
532
533
534

		/* get ready for the next letter */
		str++;
		len--;
535
	}
536

537
	if (negative)
538
		sc_neg(buffer, buffer);
539

540
	return true;
541
542
}

543
void sc_val_from_long(long value, sc_word *buffer)
544
{
545
	sc_word *pos = buffer;
546

547
548
	bool sign       = value < 0;
	bool is_minlong = value == LONG_MIN;
549

550
551
552
553
554
555
556
	/* use absolute value, special treatment of MIN_LONG to avoid overflow */
	if (sign) {
		if (is_minlong)
			value = -(value+1);
		else
			value = -value;
	}
557

558
	sc_zero(buffer);
559

560
	while ((value != 0) && (pos < buffer + calc_buffer_size)) {
Matthias Braun's avatar
Matthias Braun committed
561
		*pos++ = value & SC_MASK;
562
		value >>= SC_BITS;
563
	}
564

565
566
	if (sign) {
		if (is_minlong)
567
			sc_inc(buffer, buffer);
568

569
		sc_neg(buffer, buffer);
570
	}
571
572
}

573
void sc_val_from_ulong(unsigned long value, sc_word *buffer)
574
{
575
	sc_word *pos = buffer;
576

577
	while (pos < buffer + calc_buffer_size) {
Matthias Braun's avatar
Matthias Braun committed
578
		*pos++ = value & SC_MASK;
579
		value >>= SC_BITS;
580
	}
581
582
}

583
long sc_val_to_long(const sc_word *val)
584
{
Andreas Zwinkau's avatar
Andreas Zwinkau committed
585
	unsigned long l = 0;
586
587
	unsigned max_buffer_index = (sizeof(long)*8)/SC_BITS;
	for (unsigned i = max_buffer_index; i-- > 0; ) {
588
589
		assert(l <= (ULONG_MAX>>SC_BITS) && "signed shift overflow");
		l = (l << SC_BITS) + val[i];
590
591
	}
	return l;
592
593
}

594
uint64_t sc_val_to_uint64(const sc_word *val)
595
596
{
	uint64_t res = 0;
597
	for (unsigned i = calc_buffer_size; i-- > 0; ) {
598
		res = (res << SC_BITS) + val[i];
599
	}
Manuel Mohr's avatar
Manuel Mohr committed
600
	return res;
601
602
}

603
void sc_min_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
604
{
605
	if (!sign) {
606
		sc_zero(buffer);
607
608
609
		return;
	} else {
		sc_word *pos = buffer;
610

611
612
		unsigned bits = num_bits - 1;
		unsigned i    = 0;
613
		for ( ; i < bits/SC_BITS; i++)
614
			*pos++ = 0;
615

616
		*pos++ = min_digit(bits%SC_BITS);
617

618
		for (i++; i <= calc_buffer_size - 1; i++)
Matthias Braun's avatar
Matthias Braun committed
619
			*pos++ = SC_MASK;
620
	}
621
622
}

623
void sc_max_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
624
{
625
	sc_word *pos = buffer;
626

627
628
	unsigned bits = num_bits - sign;
	unsigned i    = 0;
629
	for ( ; i < bits/SC_BITS; i++)
Matthias Braun's avatar
Matthias Braun committed
630
		*pos++ = SC_MASK;
631

632
	*pos++ = max_digit(bits%SC_BITS);
633

634
	for (i++; i <= calc_buffer_size - 1; i++)
635
		*pos++ = 0;
636
637
}

638
ir_relation sc_comp(const sc_word* const val1, const sc_word* const val2)
639
{
640
641
	/* compare signs first:
	 * the loop below can only compare values of the same sign! */
642
643
644
645
	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;
646
647
648

	/* loop until two digits differ, the values are equal if there
	 * are no such two digits */
649
	unsigned counter = calc_buffer_size - 1;
650
	while (val1[counter] == val2[counter]) {
651
652
		if (counter == 0)
			return ir_relation_equal;
653
654
655
656
657
658
		counter--;
	}

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

663
int sc_get_highest_set_bit(const sc_word *value)
664
{
665
666
	int high = calc_buffer_size * SC_BITS - 1;
	for (unsigned counter = calc_buffer_size; counter-- > 0; ) {
667
		if (value[counter] == 0)
668
			high -= SC_BITS;
669
		else {
670
671
672
			if (value[counter] > 7) return high;
			else if (value[counter] > 3) return high - 1;
			else if (value[counter] > 1) return high - 2;
673
674
675
676
			else return high - 3;
		}
	}
	return high;
Matthias Heil's avatar
Matthias Heil committed
677
678
}

679
int sc_get_lowest_set_bit(const sc_word *value)
680
{
681
682
	int low = 0;
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter) {
683
		switch (value[counter]) {
684
685
686
687
688
689
690
691
		case 1:
		case 3:
		case 5:
		case 7:
		case 9:
		case 11:
		case 13:
		case 15:
692
			return low;
693
694
695
696
		case 2:
		case 6:
		case 10:
		case 14:
697
			return low + 1;
698
699
		case 4:
		case 12:
700
			return low + 2;
701
		case 8:
702
703
			return low + 3;
		default:
704
			low += SC_BITS;
705
706
707
		}
	}
	return -1;
Matthias Heil's avatar
Matthias Heil committed
708
709
}

710
bool sc_get_bit_at(const sc_word *value, unsigned pos)
711
{
712
713
	unsigned nibble = pos / SC_BITS;
	return value[nibble] & (1 << (pos % SC_BITS));
714
715
}

716
void sc_set_bit_at(sc_word *value, unsigned pos)
717
{
718
719
	unsigned nibble = pos / SC_BITS;
	value[nibble] |= 1 << (pos % SC_BITS);
720
721
}

722
void sc_clear_bit_at(sc_word *value, unsigned pos)
Matthias Braun's avatar
Matthias Braun committed
723
{
724
725
	unsigned nibble = pos / SC_BITS;
	value[nibble] &= ~(1 << (pos % SC_BITS));
Matthias Braun's avatar
Matthias Braun committed
726
727
}

728
bool sc_is_zero(const sc_word *value, unsigned bits)
729
{
Matthias Braun's avatar
Matthias Braun committed
730
731
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
732
		if (value[i] != 0)
733
			return false;
734
	}
Matthias Braun's avatar
Matthias Braun committed
735
	sc_word mask = max_digit(bits%SC_BITS);
736
	return mask == 0 || (value[i] & mask) == 0;
Matthias Braun's avatar
Matthias Braun committed
737
738
}

739
bool sc_is_all_one(const sc_word *value, unsigned bits)
Matthias Braun's avatar
Matthias Braun committed
740
741
742
{
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
Matthias Braun's avatar
Matthias Braun committed
743
		if (value[i] != SC_MASK)
Matthias Braun's avatar
Matthias Braun committed
744
745
			return false;
	}
Matthias Braun's avatar
Matthias Braun committed
746
	sc_word mask = max_digit(bits%SC_BITS);
747
	return mask == 0 || (value[i] & mask) == mask;
748
749
}

750
bool sc_is_negative(const sc_word *value)
751
{
752
	return sc_get_bit_at(value, calc_buffer_size*SC_BITS-1);
753
754
}

755
unsigned char sc_sub_bits(const sc_word *value, unsigned len, unsigned byte_ofs)
756
{
757
	/* the current scheme uses one byte to store a nibble */
758
	unsigned nibble_ofs = 2 * byte_ofs;
759
	if (nibble_ofs * SC_BITS >= len)
760
		return 0;
761

762
	unsigned char res = value[nibble_ofs];
763
764
	if (len > (nibble_ofs + 1) * SC_BITS)
		res |= value[nibble_ofs + 1] << SC_BITS;
765

766
	/* kick bits outsize */
767
768
	if (len - 8 * byte_ofs < 8) {
		res &= (1 << (len - 8 * byte_ofs)) - 1;
769
	}
770
	return res;
771
772
}

773
unsigned sc_popcount(const sc_word *value, unsigned bits)
Matthias Braun's avatar
Matthias Braun committed
774
{
775
	unsigned res = 0;
Matthias Braun's avatar
Matthias Braun committed
776
777
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
778
		res += popcount(value[i]);
Matthias Braun's avatar
Matthias Braun committed
779
	}
Matthias Braun's avatar
Matthias Braun committed
780
	sc_word mask = max_digit(bits%SC_BITS);
Matthias Braun's avatar
Matthias Braun committed
781
	if (mask != 0)
782
		res += popcount(value[i] & mask);
Matthias Braun's avatar
Matthias Braun committed
783
784
785
786

	return res;
}

Matthias Braun's avatar
Matthias Braun committed