strcalc.c 24.7 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   Arithmetic operations on arbitrary precision integer numbers.
 * @author  Mathias Heil, Matthias Braun
10
 */
11
#include <stdlib.h>
12
13
14
15
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <limits.h>
16

Michael Beck's avatar
Michael Beck committed
17
#include "strcalc.h"
Michael Beck's avatar
Michael Beck committed
18
#include "xmalloc.h"
19
#include "error.h"
Matthias Braun's avatar
Matthias Braun committed
20
#include "bitfiddle.h"
Michael Beck's avatar
Michael Beck committed
21

22
#define SC_BITS      4
Matthias Braun's avatar
Matthias Braun committed
23
#define SC_MASK      ((sc_word)0xF)
24
25
26
#define SC_RESULT(x) ((x) & ((1U << SC_BITS) - 1U))
#define SC_CARRY(x)  ((unsigned)(x) >> SC_BITS)

27
#define _bitisset(digit, pos) (((digit) & (1 << (pos))) != 0)
28

29
30
31
32
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 */
33

34
35
36
37
38
void sc_zero(sc_word *buffer)
{
	memset(buffer, 0, sizeof(buffer[0]) * calc_buffer_size);
}

Matthias Braun's avatar
Matthias Braun committed
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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);
}

54
void sc_not(const sc_word *val, sc_word *buffer)
55
{
56
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
Matthias Braun's avatar
Matthias Braun committed
57
		buffer[counter] = val[counter] ^ SC_MASK;
58
59
}

60
void sc_or(const sc_word *val1, const sc_word *val2, sc_word *buffer)
61
{
62
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
63
		buffer[counter] = val1[counter] | val2[counter];
64
65
}

66
void sc_xor(const sc_word *val1, const sc_word *val2, sc_word *buffer)
67
{
68
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
69
		buffer[counter] = val1[counter] ^ val2[counter];
70
71
}

72
void sc_and(const sc_word *val1, const sc_word *val2, sc_word *buffer)
73
{
74
	for (unsigned counter = 0; counter<calc_buffer_size; counter++)
75
		buffer[counter] = val1[counter] & val2[counter];
76
77
}

78
void sc_andnot(const sc_word *val1, const sc_word *val2, sc_word *buffer)
79
{
80
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter)
Matthias Braun's avatar
Matthias Braun committed
81
		buffer[counter] = val1[counter] & (SC_MASK ^ val2[counter]);
82
83
}

Matthias Braun's avatar
Matthias Braun committed
84
void sc_inc(const sc_word *val, sc_word *buffer)
85
{
86
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter) {
87
88
89
90
91
92
93
94
		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;
95
		}
96
		buffer[counter] = 0;
97
	}
98
99
}

100
void sc_neg(const sc_word *val, sc_word *buffer)
101
{
102
103
	sc_not(val, buffer);
	sc_inc(buffer, buffer);
104
105
}

106
void sc_add(const sc_word *val1, const sc_word *val2, sc_word *buffer)
107
{
108
109
	sc_word carry = 0;
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter) {
110
111
112
		unsigned const sum = val1[counter] + val2[counter] + carry;
		buffer[counter] = SC_RESULT(sum);
		carry           = SC_CARRY(sum);
113
	}
114
115
}

116
void sc_sub(const sc_word *val1, const sc_word *val2, sc_word *buffer)
117
{
118
	/* intermediate buffer to hold -val2 */
119
	sc_word *temp_buffer = ALLOCAN(sc_word, calc_buffer_size);
Michael Beck's avatar
Michael Beck committed
120

121
122
	sc_neg(val2, temp_buffer);
	sc_add(val1, temp_buffer, buffer);
Michael Beck's avatar
Michael Beck committed
123
124
}

125
void sc_mul(const sc_word *val1, const sc_word *val2, sc_word *buffer)
126
{
127
	sc_word *temp_buffer = ALLOCANZ(sc_word, calc_buffer_size);
128
129
	sc_word *neg_val1    = ALLOCAN(sc_word, calc_buffer_size);
	sc_word *neg_val2    = ALLOCAN(sc_word, calc_buffer_size);
130
131
132

	/* the multiplication works only for positive values, for negative values *
	 * it is necessary to negate them and adjust the result accordingly       */
133
	bool sign = false;
134
	if (sc_is_negative(val1)) {
135
		sc_neg(val1, neg_val1);
136
		val1 = neg_val1;
137
		sign = !sign;
138
	}
139
	if (sc_is_negative(val2)) {
140
		sc_neg(val2, neg_val2);
141
		val2 = neg_val2;
142
		sign = !sign;
143
144
	}

145
	for (unsigned c_outer = 0; c_outer < max_value_size; c_outer++) {
Matthias Braun's avatar
Matthias Braun committed
146
147
148
149
		sc_word outer = val2[c_outer];
		if (outer == 0)
			continue;
		unsigned carry = 0; /* container for carries */
150
		for (unsigned c_inner = 0; c_inner < max_value_size; c_inner++) {
Matthias Braun's avatar
Matthias Braun committed
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
			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);
176
		}
Matthias Braun's avatar
Matthias Braun committed
177
178
179
180

		/* A carry may hang over */
		/* c_outer is always smaller than max_value_size! */
		temp_buffer[max_value_size + c_outer] = carry;
181
182
183
	}

	if (sign)
184
		sc_neg(temp_buffer, buffer);
185
186
	else
		memcpy(buffer, temp_buffer, calc_buffer_size);
187
188
}

Michael Beck's avatar
Michael Beck committed
189
/**
190
 * Shift the buffer to left and add an sc digit
Michael Beck's avatar
Michael Beck committed
191
 */
192
static void sc_push(sc_word digit, sc_word *buffer)
193
{
194
	for (unsigned counter = calc_buffer_size - 1; counter-- > 0; ) {
195
196
197
		buffer[counter+1] = buffer[counter];
	}
	buffer[0] = digit;
198
199
}

200
201
bool sc_divmod(const sc_word *dividend, const sc_word *divisor,
               sc_word *quot, sc_word *rem)
202
{
203
204
	assert(quot != dividend && quot != divisor);
	assert(rem != dividend && rem != divisor);
205
	/* clear result buffer */
206
207
	sc_zero(quot);
	sc_zero(rem);
208

209
210
	/* division by zero is not allowed */
	assert(!sc_is_zero(divisor, calc_buffer_size*SC_BITS));
211
212

	/* if the dividend is zero result is zero (quot is zero) */
213
	if (sc_is_zero(dividend, calc_buffer_size*SC_BITS))
214
		return false;
215

216
217
	bool     div_sign = false;
	bool     rem_sign = false;
218
	sc_word *neg_val1 = ALLOCAN(sc_word, calc_buffer_size);
219
	if (sc_is_negative(dividend)) {
220
		sc_neg(dividend, neg_val1);
221
222
		div_sign = !div_sign;
		rem_sign = !rem_sign;
223
224
225
		dividend = neg_val1;
	}

226
	sc_word *neg_val2 = ALLOCAN(sc_word, calc_buffer_size);
227
	sc_neg(divisor, neg_val2);
228
	const sc_word *minus_divisor;
229
	if (sc_is_negative(divisor)) {
230
		div_sign = !div_sign;
231
232
		minus_divisor = divisor;
		divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
233
	} else {
234
		minus_divisor = neg_val2;
Matthias Braun's avatar
Matthias Braun committed
235
	}
236
237
238
239

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

244
	case ir_relation_less: /* dividend < divisor */
245
		memcpy(rem, dividend, calc_buffer_size);
246
247
248
249
250
251
		goto end;

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

252
	for (unsigned c_dividend = calc_buffer_size; c_dividend-- > 0; ) {
253
254
		sc_push(dividend[c_dividend], rem);
		sc_push(0, quot);
255

Matthias Braun's avatar
Matthias Braun committed
256
257
		if (sc_comp(rem, divisor) != ir_relation_less) {
			/* remainder >= divisor */
258
259
			/* subtract until the remainder becomes negative, this should
			 * be faster than comparing remainder with divisor  */
260
			sc_add(rem, minus_divisor, rem);
261

262
			while (!sc_is_negative(rem)) {
263
				/* TODO can this generate carry or is masking redundant? */
264
				quot[0] = SC_RESULT(quot[0] + 1);
265
				sc_add(rem, minus_divisor, rem);
266
267
268
			}

			/* subtracted one too much */
269
			sc_add(rem, divisor, rem);
270
271
272
273
		}
	}
end:
	if (div_sign)
274
		sc_neg(quot, quot);
275
276

	if (rem_sign)
277
		sc_neg(rem, rem);
278
279
280
281

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

284
unsigned sc_get_value_length(void)
285
{
286
	return calc_buffer_size;
287
288
}

289
void sc_zero_extend(sc_word *buffer, unsigned from_bits)
290
{
291
292
293
294
295
296
297
298
299
300
301
302
	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)
{
Matthias Braun's avatar
Matthias Braun committed
303
	assert(from_bits > 0);
304
305
306
307
308
309
310
311
	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);
312
	} else {
313
		sc_zero_extend(buffer, from_bits);
314
	}
315
316
}

317
/** Ensures that our source character set conforms to ASCII for a-f, A-F, 0-9 */
318
static inline void check_ascii(void)
319
{
Matthias Braun's avatar
Matthias Braun committed
320
321
322
323
	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);
324
}
325

326
bool sc_val_from_str(bool negative, unsigned base, const char *str, size_t len,
327
                     sc_word *buffer)
328
329
330
331
{
	assert(str != NULL);
	assert(len > 0);
	check_ascii();
332

333
	assert(base > 1 && base <= 16);
334
	sc_word *sc_base = ALLOCAN(sc_word, calc_buffer_size);
335
	sc_val_from_ulong(base, sc_base);
336

337
	sc_word *val = ALLOCANZ(sc_word, calc_buffer_size);
338

339
	sc_zero(buffer);
340
341
342

	/* BEGIN string evaluation, from left to right */
	while (len > 0) {
343
344
345
346
		char c = *str;
		unsigned v;
		if (c >= '0' && c <= '9')
			v = c - '0';
347
348
349
350
		else if (c >= 'A' && c <= 'F')
			v = c - 'A' + 10;
		else if (c >= 'a' && c <= 'f')
			v = c - 'a' + 10;
351
		else
352
			return false;
353

354
		if (v >= base)
355
			return false;
356
		val[0] = v;
357
358
359

		/* Radix conversion from base b to base B:
		 *  (UnUn-1...U1U0)b == ((((Un*b + Un-1)*b + ...)*b + U1)*b + U0)B */
360
		/* multiply current value with base */
361
		sc_mul(sc_base, buffer, buffer);
362
		/* add next digit to current value  */
363
		sc_add(val, buffer, buffer);
364
365
366
367

		/* get ready for the next letter */
		str++;
		len--;
368
	}
369

370
	if (negative)
371
		sc_neg(buffer, buffer);
372

373
	return true;
374
375
}

376
void sc_val_from_long(long value, sc_word *buffer)
377
{
378
379
	bool sign       = value < 0;
	bool is_minlong = value == LONG_MIN;
380

381
382
383
384
385
386
387
	/* use absolute value, special treatment of MIN_LONG to avoid overflow */
	if (sign) {
		if (is_minlong)
			value = -(value+1);
		else
			value = -value;
	}
388

389
	sc_zero(buffer);
390

Matthias Braun's avatar
Matthias Braun committed
391
	sc_word *pos = buffer;
392
	while ((value != 0) && (pos < buffer + calc_buffer_size)) {
Matthias Braun's avatar
Matthias Braun committed
393
		*pos++ = value & SC_MASK;
394
		value >>= SC_BITS;
395
	}
396

397
398
	if (sign) {
		if (is_minlong)
399
			sc_inc(buffer, buffer);
400

401
		sc_neg(buffer, buffer);
402
	}
403
404
}

405
void sc_val_from_ulong(unsigned long value, sc_word *buffer)
406
{
407
	sc_word *pos = buffer;
408

409
	while (pos < buffer + calc_buffer_size) {
Matthias Braun's avatar
Matthias Braun committed
410
		*pos++ = value & SC_MASK;
411
		value >>= SC_BITS;
412
	}
413
414
}

415
long sc_val_to_long(const sc_word *val)
416
{
Andreas Zwinkau's avatar
Andreas Zwinkau committed
417
	unsigned long l = 0;
418
419
	unsigned max_buffer_index = (sizeof(long)*8)/SC_BITS;
	for (unsigned i = max_buffer_index; i-- > 0; ) {
420
421
		assert(l <= (ULONG_MAX>>SC_BITS) && "signed shift overflow");
		l = (l << SC_BITS) + val[i];
422
423
	}
	return l;
424
425
}

426
uint64_t sc_val_to_uint64(const sc_word *val)
427
428
{
	uint64_t res = 0;
429
	for (unsigned i = calc_buffer_size; i-- > 0; ) {
430
		res = (res << SC_BITS) + val[i];
431
	}
Manuel Mohr's avatar
Manuel Mohr committed
432
	return res;
433
434
}

435
void sc_min_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
436
{
437
	if (!sign) {
438
		sc_zero(buffer);
439
440
441
		return;
	} else {
		sc_word *pos = buffer;
442

443
444
		unsigned bits = num_bits - 1;
		unsigned i    = 0;
445
		for ( ; i < bits/SC_BITS; i++)
446
			*pos++ = 0;
447

448
		*pos++ = min_digit(bits%SC_BITS);
449

Matthias Braun's avatar
Matthias Braun committed
450
		for (i++; i < calc_buffer_size; i++)
Matthias Braun's avatar
Matthias Braun committed
451
			*pos++ = SC_MASK;
452
	}
453
454
}

455
void sc_max_from_bits(unsigned num_bits, bool sign, sc_word *buffer)
456
{
457
	sc_word *pos = buffer;
458

459
460
	unsigned bits = num_bits - sign;
	unsigned i    = 0;
461
	for ( ; i < bits/SC_BITS; i++)
Matthias Braun's avatar
Matthias Braun committed
462
		*pos++ = SC_MASK;
463

464
	*pos++ = max_digit(bits%SC_BITS);
465

Matthias Braun's avatar
Matthias Braun committed
466
	for (i++; i < calc_buffer_size; i++)
467
		*pos++ = 0;
468
469
}

470
ir_relation sc_comp(const sc_word* const val1, const sc_word* const val2)
471
{
472
473
	/* compare signs first:
	 * the loop below can only compare values of the same sign! */
474
475
476
477
	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;
478
479
480

	/* loop until two digits differ, the values are equal if there
	 * are no such two digits */
481
	unsigned counter = calc_buffer_size - 1;
482
	while (val1[counter] == val2[counter]) {
483
484
		if (counter == 0)
			return ir_relation_equal;
485
486
487
488
489
490
		counter--;
	}

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

495
int sc_get_highest_set_bit(const sc_word *value)
496
{
497
	for (unsigned counter = calc_buffer_size; counter-- > 0; ) {
498
499
500
		sc_word word = value[counter];
		if (word != 0)
			return counter*SC_BITS + (31 - nlz(word));
501
	}
502
	return -1;
Matthias Heil's avatar
Matthias Heil committed
503
504
}

505
int sc_get_lowest_set_bit(const sc_word *value)
506
{
507
508
509
510
511
	for (unsigned counter = 0; counter < calc_buffer_size;
	     ++counter) {
		sc_word word = value[counter];
		if (word != 0)
			return (counter * SC_BITS) + ntz(word);
512
513
	}
	return -1;
Matthias Heil's avatar
Matthias Heil committed
514
515
}

516
bool sc_get_bit_at(const sc_word *value, unsigned pos)
517
{
518
519
	unsigned nibble = pos / SC_BITS;
	return value[nibble] & (1 << (pos % SC_BITS));
520
521
}

522
void sc_set_bit_at(sc_word *value, unsigned pos)
523
{
524
525
	unsigned nibble = pos / SC_BITS;
	value[nibble] |= 1 << (pos % SC_BITS);
526
527
}

528
void sc_clear_bit_at(sc_word *value, unsigned pos)
Matthias Braun's avatar
Matthias Braun committed
529
{
530
531
	unsigned nibble = pos / SC_BITS;
	value[nibble] &= ~(1 << (pos % SC_BITS));
Matthias Braun's avatar
Matthias Braun committed
532
533
}

534
bool sc_is_zero(const sc_word *value, unsigned bits)
535
{
Matthias Braun's avatar
Matthias Braun committed
536
537
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
538
		if (value[i] != 0)
539
			return false;
540
	}
Matthias Braun's avatar
Matthias Braun committed
541
	sc_word mask = max_digit(bits%SC_BITS);
542
	return mask == 0 || (value[i] & mask) == 0;
Matthias Braun's avatar
Matthias Braun committed
543
544
}

545
bool sc_is_all_one(const sc_word *value, unsigned bits)
Matthias Braun's avatar
Matthias Braun committed
546
547
548
{
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
Matthias Braun's avatar
Matthias Braun committed
549
		if (value[i] != SC_MASK)
Matthias Braun's avatar
Matthias Braun committed
550
551
			return false;
	}
Matthias Braun's avatar
Matthias Braun committed
552
	sc_word mask = max_digit(bits%SC_BITS);
553
	return mask == 0 || (value[i] & mask) == mask;
554
555
}

556
bool sc_is_negative(const sc_word *value)
557
{
558
	return sc_get_bit_at(value, calc_buffer_size*SC_BITS-1);
559
560
}

561
unsigned char sc_sub_bits(const sc_word *value, unsigned len, unsigned byte_ofs)
562
{
563
	/* the current scheme uses one byte to store a nibble */
564
	unsigned nibble_ofs = 2 * byte_ofs;
565
	if (nibble_ofs * SC_BITS >= len)
566
		return 0;
567

568
	unsigned char res = value[nibble_ofs];
569
570
	if (len > (nibble_ofs + 1) * SC_BITS)
		res |= value[nibble_ofs + 1] << SC_BITS;
571

572
	/* kick bits outside */
573
574
	if (len - 8 * byte_ofs < 8) {
		res &= (1 << (len - 8 * byte_ofs)) - 1;
575
	}
576
	return res;
577
578
}

579
unsigned sc_popcount(const sc_word *value, unsigned bits)
Matthias Braun's avatar
Matthias Braun committed
580
{
581
	unsigned res = 0;
Matthias Braun's avatar
Matthias Braun committed
582
583
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
584
		res += popcount(value[i]);
Matthias Braun's avatar
Matthias Braun committed
585
	}
Matthias Braun's avatar
Matthias Braun committed
586
	sc_word mask = max_digit(bits%SC_BITS);
Matthias Braun's avatar
Matthias Braun committed
587
	if (mask != 0)
588
		res += popcount(value[i] & mask);
Matthias Braun's avatar
Matthias Braun committed
589
590
591
592

	return res;
}

Matthias Braun's avatar
Matthias Braun committed
593
void sc_val_from_bytes(unsigned char const *const bytes, size_t n_bytes,
594
                       bool big_endian, sc_word *buffer)
Matthias Braun's avatar
Matthias Braun committed
595
{
596
	assert(n_bytes*8 <= (size_t)calc_buffer_size*SC_BITS);
Matthias Braun's avatar
Matthias Braun committed
597

598
	sc_word *p = buffer;
599
	assert(SC_BITS == 4);
Matthias Braun's avatar
Matthias Braun committed
600
	if (big_endian) {
601
		for (unsigned char const *bp = bytes+n_bytes-1; bp >= bytes; --bp) {
Matthias Braun's avatar
Matthias Braun committed
602
			unsigned char v = *bp;
Matthias Braun's avatar
Matthias Braun committed
603
604
			*p++ =  v     & SC_MASK;
			*p++ = (v>>4) & SC_MASK;
Matthias Braun's avatar
Matthias Braun committed
605
606
607
608
609
		}
	} else {
		for (unsigned char const *bp = bytes, *bp_end = bytes + n_bytes;
		     bp < bp_end; ++bp) {
			unsigned char v = *bp;
Matthias Braun's avatar
Matthias Braun committed
610
611
			*p++ =  v     & SC_MASK;
			*p++ = (v>>4) & SC_MASK;
Matthias Braun's avatar
Matthias Braun committed
612
613
		}
	}
614
	for (sc_word *p_end = buffer+calc_buffer_size; p < p_end; ++p)
Matthias Braun's avatar
Matthias Braun committed
615
616
617
		*p = 0;
}

618
void sc_val_from_bits(unsigned char const *const bytes, unsigned from,
619
                      unsigned to, sc_word *buffer)
620
621
{
	assert(from < to);
622
	assert((to - from) / 8 <= calc_buffer_size);
623
624
	assert(SC_BITS == 4);

625
	sc_word *p = buffer;
626
627
628
629
630
631
632
633

	/* see which is the lowest and highest byte, special case if they are
	 * the same. */
	const unsigned char *const low      = &bytes[from/8];
	const unsigned char *const high     = &bytes[(to-1)/8];
	const uint8_t              low_bit  = from%8;
	const uint8_t              high_bit = (to-1)%8 + 1;
	if (low == high) {
634
635
		uint32_t val
			= ((uint32_t)*low << (32-high_bit)) >> (32-high_bit+low_bit);
Matthias Braun's avatar
Matthias Braun committed
636
637
		*p++ = (val >> 0) & SC_MASK;
		*p++ = (val >> 4) & SC_MASK;
638
639
640
641
642
		goto clear_rest;
	}

	/* lowest byte gets applied partially */
	uint32_t val = ((uint32_t)*low) >> low_bit;
Matthias Braun's avatar
Matthias Braun committed
643
644
	*p     = (val >> 0) & SC_MASK;
	*(p+1) = (val >> 4) & SC_MASK;
645
646
647
648
649
650
651
	*(p+2) = 0;
	unsigned bit = (8-low_bit)%4;
	p += (8-low_bit)/4;
	/* fully apply bytes in the middle (but note that they may affect up to 3
	 * units of the destination number) */
	for (const unsigned char *mid = low+1; mid < high; ++mid) {
		uint32_t mval = ((uint32_t)*mid) << bit;
Matthias Braun's avatar
Matthias Braun committed
652
653
654
		*p++   |= (mval >> 0) & SC_MASK;
		*p++    = (mval >> 4) & SC_MASK;
		*p      = (mval >> 8) & SC_MASK;
655
656
657
	}
	/* partially apply the highest byte */
	uint32_t hval = ((uint32_t)(*high) << (32-high_bit)) >> (32-high_bit-bit);
Matthias Braun's avatar
Matthias Braun committed
658
659
	*p++ |= (hval >> 0) & SC_MASK;
	*p++  = (hval >> 4) & SC_MASK;
660
661

clear_rest:
662
663
	assert(p <= buffer + calc_buffer_size);
	memset(p, 0, calc_buffer_size - (p-buffer));
664
665
}

666
const char *sc_print(const sc_word *value, unsigned bits, enum base_t base,
667
668
669
670
671
672
                     bool is_signed)
{
	return sc_print_buf(output_buffer, bit_pattern_size+1, value, bits,
	                    base, is_signed);
}

673
674
675
676
677
678
679
static void write_bits(char *dest, sc_word word)
{
	for (unsigned i = 0; i < SC_BITS; ++i) {
		dest[i] = (word & (1u << (SC_BITS-i-1))) ? '1' : '0';
	}
}

680
char *sc_print_buf(char *buf, size_t buf_len, const sc_word *value,
681
                   unsigned bits, enum base_t base, bool is_signed)
682
{
683
684
685
686
687
	static const char big_digits[]   = "0123456789ABCDEF";
	static const char small_digits[] = "0123456789abcdef";

	const char *digits = small_digits;

688
	char *pos = buf + buf_len;
689
	*(--pos) = '\0';
690
	assert(pos >= buf);
691
692

	/* special case */
693
	if (bits == 0)
694
		bits = bit_pattern_size;
695

696
	unsigned words = bits / SC_BITS;
697
	unsigned counter;
698
699
700
701
	switch (base) {
	case SC_HEX:
		digits = big_digits;
	case SC_hex:
702
		for (counter = 0; counter < words; ++counter) {
703
			*(--pos) = digits[value[counter]];
704
		}
705
		assert(pos >= buf);
706

707
		/* last nibble must be masked */
708
		if (bits % SC_BITS) {
709
			sc_word mask = max_digit(bits % SC_BITS);
710
			sc_word x    = value[counter++] & mask;
711
			*(--pos) = digits[x];
712
			assert(pos >= buf);
713
		}
714

715
716
717
718
719
720
721
722
		/* now kill zeros */
		for (; counter > 1; --counter, ++pos) {
			if (pos[0] != '0')
				break;
		}
		break;

	case SC_BIN:
723
		assert(SC_BITS == 4);
724
		for (counter = 0; counter < words; ++counter) {
725
			pos -= SC_BITS;
726
			write_bits(pos, value[counter]);
727
		}
728
		assert(pos >= buf);
729
730

		/* last nibble must be masked */
731
		if (bits % SC_BITS) {
732
			sc_word mask = max_digit(bits % SC_BITS);
733
			sc_word x    = value[counter++] & mask;
734

735
			pos -= SC_BITS;
736
			write_bits(pos, x);
737
		}
738
		assert(pos >= buf);
739
740
741
742
743
744
745
746

		/* now kill zeros */
		for (counter <<= 2; counter > 1; --counter, ++pos)
			if (pos[0] != '0')
				break;
			break;

	case SC_DEC:
747
	case SC_OCT: {
748
		sc_word *base_val = ALLOCANZ(sc_word, calc_buffer_size);
749
		base_val[0] = base == SC_DEC ? 10 : 8;
750

751
		const sc_word *p        = value;
752
		bool           sign     = false;
753
		sc_word       *div2_res = ALLOCAN(sc_word, calc_buffer_size);
754
		if (is_signed && base == SC_DEC) {
755
			/* check for negative values */
756
			if (sc_get_bit_at(value, bits-1)) {
757
				sc_neg(value, div2_res);
758
				sign = true;
759
760
761
762
763
				p = div2_res;
			}
		}

		/* transfer data into oscillating buffers */
764
		sc_word *div1_res = ALLOCANZ(sc_word, calc_buffer_size);
765
		for (counter = 0; counter < words; ++counter)
766
767
768
			div1_res[counter] = p[counter];

		/* last nibble must be masked */
769
		if (bits % SC_BITS) {
770
			sc_word mask = max_digit(bits % SC_BITS);
771
			div1_res[counter] = p[counter] & mask;
772
773
774
			++counter;
		}

775
776
777
		sc_word *m       = div1_res;
		sc_word *n       = div2_res;
		sc_word *rem_res = ALLOCAN(sc_word, calc_buffer_size);
778
		for (;;) {
779
			sc_divmod(m, base_val, n, rem_res);
780
			sc_word *t = m;
781
782
			m = n;
			n = t;
783
			*(--pos) = digits[rem_res[0]];
784