strcalc.c 25 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
498
	int high = calc_buffer_size * SC_BITS - 1;
	for (unsigned counter = calc_buffer_size; counter-- > 0; ) {
499
		if (value[counter] == 0)
500
			high -= SC_BITS;
501
		else {
502
503
504
			if (value[counter] > 7) return high;
			else if (value[counter] > 3) return high - 1;
			else if (value[counter] > 1) return high - 2;
505
506
507
508
			else return high - 3;
		}
	}
	return high;
Matthias Heil's avatar
Matthias Heil committed
509
510
}

511
int sc_get_lowest_set_bit(const sc_word *value)
512
{
513
514
	int low = 0;
	for (unsigned counter = 0; counter < calc_buffer_size; ++counter) {
515
		switch (value[counter]) {
516
517
518
519
520
521
522
523
		case 1:
		case 3:
		case 5:
		case 7:
		case 9:
		case 11:
		case 13:
		case 15:
524
			return low;
525
526
527
528
		case 2:
		case 6:
		case 10:
		case 14:
529
			return low + 1;
530
531
		case 4:
		case 12:
532
			return low + 2;
533
		case 8:
534
535
			return low + 3;
		default:
536
			low += SC_BITS;
537
538
539
		}
	}
	return -1;
Matthias Heil's avatar
Matthias Heil committed
540
541
}

542
bool sc_get_bit_at(const sc_word *value, unsigned pos)
543
{
544
545
	unsigned nibble = pos / SC_BITS;
	return value[nibble] & (1 << (pos % SC_BITS));
546
547
}

548
void sc_set_bit_at(sc_word *value, unsigned pos)
549
{
550
551
	unsigned nibble = pos / SC_BITS;
	value[nibble] |= 1 << (pos % SC_BITS);
552
553
}

554
void sc_clear_bit_at(sc_word *value, unsigned pos)
Matthias Braun's avatar
Matthias Braun committed
555
{
556
557
	unsigned nibble = pos / SC_BITS;
	value[nibble] &= ~(1 << (pos % SC_BITS));
Matthias Braun's avatar
Matthias Braun committed
558
559
}

560
bool sc_is_zero(const sc_word *value, unsigned bits)
561
{
Matthias Braun's avatar
Matthias Braun committed
562
563
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
564
		if (value[i] != 0)
565
			return false;
566
	}
Matthias Braun's avatar
Matthias Braun committed
567
	sc_word mask = max_digit(bits%SC_BITS);
568
	return mask == 0 || (value[i] & mask) == 0;
Matthias Braun's avatar
Matthias Braun committed
569
570
}

571
bool sc_is_all_one(const sc_word *value, unsigned bits)
Matthias Braun's avatar
Matthias Braun committed
572
573
574
{
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
Matthias Braun's avatar
Matthias Braun committed
575
		if (value[i] != SC_MASK)
Matthias Braun's avatar
Matthias Braun committed
576
577
			return false;
	}
Matthias Braun's avatar
Matthias Braun committed
578
	sc_word mask = max_digit(bits%SC_BITS);
579
	return mask == 0 || (value[i] & mask) == mask;
580
581
}

582
bool sc_is_negative(const sc_word *value)
583
{
584
	return sc_get_bit_at(value, calc_buffer_size*SC_BITS-1);
585
586
}

587
unsigned char sc_sub_bits(const sc_word *value, unsigned len, unsigned byte_ofs)
588
{
589
	/* the current scheme uses one byte to store a nibble */
590
	unsigned nibble_ofs = 2 * byte_ofs;
591
	if (nibble_ofs * SC_BITS >= len)
592
		return 0;
593

594
	unsigned char res = value[nibble_ofs];
595
596
	if (len > (nibble_ofs + 1) * SC_BITS)
		res |= value[nibble_ofs + 1] << SC_BITS;
597

598
	/* kick bits outsize */
599
600
	if (len - 8 * byte_ofs < 8) {
		res &= (1 << (len - 8 * byte_ofs)) - 1;
601
	}
602
	return res;
603
604
}

605
unsigned sc_popcount(const sc_word *value, unsigned bits)
Matthias Braun's avatar
Matthias Braun committed
606
{
607
	unsigned res = 0;
Matthias Braun's avatar
Matthias Braun committed
608
609
	unsigned i;
	for (i = 0; i < bits/SC_BITS; ++i) {
610
		res += popcount(value[i]);
Matthias Braun's avatar
Matthias Braun committed
611
	}
Matthias Braun's avatar
Matthias Braun committed
612
	sc_word mask = max_digit(bits%SC_BITS);
Matthias Braun's avatar
Matthias Braun committed
613
	if (mask != 0)
614
		res += popcount(value[i] & mask);
Matthias Braun's avatar
Matthias Braun committed
615
616
617
618

	return res;
}

Matthias Braun's avatar
Matthias Braun committed
619
void sc_val_from_bytes(unsigned char const *const bytes, size_t n_bytes,
620
                       bool big_endian, sc_word *buffer)
Matthias Braun's avatar
Matthias Braun committed
621
622
623
{
	assert(n_bytes <= (size_t)calc_buffer_size);

624
	sc_word *p = buffer;
625
	assert(SC_BITS == 4);
Matthias Braun's avatar
Matthias Braun committed
626
	if (big_endian) {
627
		for (unsigned char const *bp = bytes+n_bytes-1; bp >= bytes; --bp) {
Matthias Braun's avatar
Matthias Braun committed
628
			unsigned char v = *bp;
Matthias Braun's avatar
Matthias Braun committed
629
630
			*p++ =  v     & SC_MASK;
			*p++ = (v>>4) & SC_MASK;
Matthias Braun's avatar
Matthias Braun committed
631
632
633
634
635
		}
	} 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
636
637
			*p++ =  v     & SC_MASK;
			*p++ = (v>>4) & SC_MASK;
Matthias Braun's avatar
Matthias Braun committed
638
639
		}
	}
640
	for (sc_word *p_end = buffer+calc_buffer_size; p < p_end; ++p)
Matthias Braun's avatar
Matthias Braun committed
641
642
643
		*p = 0;
}

644
void sc_val_from_bits(unsigned char const *const bytes, unsigned from,
645
                      unsigned to, sc_word *buffer)
646
647
{
	assert(from < to);
648
	assert((to - from) / 8 <= calc_buffer_size);
649
650
	assert(SC_BITS == 4);

651
	sc_word *p = buffer;
652
653
654
655
656
657
658
659

	/* 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) {
660
661
		uint32_t val
			= ((uint32_t)*low << (32-high_bit)) >> (32-high_bit+low_bit);
Matthias Braun's avatar
Matthias Braun committed
662
663
		*p++ = (val >> 0) & SC_MASK;
		*p++ = (val >> 4) & SC_MASK;
664
665
666
667
668
		goto clear_rest;
	}

	/* lowest byte gets applied partially */
	uint32_t val = ((uint32_t)*low) >> low_bit;
Matthias Braun's avatar
Matthias Braun committed
669
670
	*p     = (val >> 0) & SC_MASK;
	*(p+1) = (val >> 4) & SC_MASK;
671
672
673
674
675
676
677
	*(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
678
679
680
		*p++   |= (mval >> 0) & SC_MASK;
		*p++    = (mval >> 4) & SC_MASK;
		*p      = (mval >> 8) & SC_MASK;
681
682
683
	}
	/* 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
684
685
	*p++ |= (hval >> 0) & SC_MASK;
	*p++  = (hval >> 4) & SC_MASK;
686
687

clear_rest:
688
689
	assert(p <= buffer + calc_buffer_size);
	memset(p, 0, calc_buffer_size - (p-buffer));
690
691
}

692
const char *sc_print(const sc_word *value, unsigned bits, enum base_t base,
693
694
695
696
697
698
                     bool is_signed)
{
	return sc_print_buf(output_buffer, bit_pattern_size+1, value, bits,
	                    base, is_signed);
}

699
700
701
702
703
704
705
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';
	}
}

706
char *sc_print_buf(char *buf, size_t buf_len, const sc_word *value,
707
                   unsigned bits, enum base_t base, bool is_signed)
708
{
709
710
711
712
713
	static const char big_digits[]   = "0123456789ABCDEF";
	static const char small_digits[] = "0123456789abcdef";

	const char *digits = small_digits;

714
	char *pos = buf + buf_len;
715
	*(--pos) = '\0';
716
	assert(pos >= buf);
717
718

	/* special case */
719
	if (bits == 0)
720
		bits = bit_pattern_size;
721

722
	unsigned words = bits / SC_BITS;
723
	unsigned counter;
724
725
726
727
	switch (base) {
	case SC_HEX:
		digits = big_digits;
	case SC_hex:
728
		for (counter = 0; counter < words; ++counter) {
729
			*(--pos) = digits[value[counter]];
730
		}
731
		assert(pos >= buf);
732

733
		/* last nibble must be masked */
734
		if (bits % SC_BITS) {
735
			sc_word mask = max_digit(bits % SC_BITS);
736
			sc_word x    = value[counter++] & mask;
737
			*(--pos) = digits[x];
738
			assert(pos >= buf);
739
		}
740

741
742
743
744
745
746
747
748
		/* now kill zeros */
		for (; counter > 1; --counter, ++pos) {
			if (pos[0] != '0')
				break;
		}
		break;

	case SC_BIN:
749
		assert(SC_BITS == 4);
750
		for (counter = 0; counter < words; ++counter) {
751
			pos -= SC_BITS;
752
			write_bits(pos, value[counter]);
753
		}
754
		assert(pos >= buf);
755
756

		/* last nibble must be masked */
757
		if (bits % SC_BITS) {
758
			sc_word mask = max_digit(bits % SC_BITS);
759
			sc_word x    = value[counter++] & mask;
760

761
			pos -= SC_BITS;
762
			write_bits(pos, x);
763
		}
764
		assert(pos >= buf);
765
766
767
768
769
770
771
772

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

	case SC_DEC:
773
	case SC_OCT: {
774
		sc_word *base_val = ALLOCANZ(sc_word, calc_buffer_size);
775
		base_val[0] = base == SC_DEC ? 10 : 8;
776

777
		const sc_word *p        = value;
778
		bool           sign     = false;
779
		sc_word       *div2_res = ALLOCAN(sc_word, calc_buffer_size);
780
		if (is_signed && base == SC_DEC) {
781
			/* check for negative values */
782
			if (sc_get_bit_at(value, bits-1)) {
783
				sc_neg(value, div2_res);
784
				sign = true;
785
786
787
788
789
				p = div2_res;
			}
		}

		/* transfer data into oscillating buffers */
790
		sc_word *div1_res = ALLOCANZ(sc_word, calc_buffer_size);
791
		for (counter = 0; counter < words; ++counter)
792
793
794
			div1_res[counter] = p[counter];

		/* last nibble must be masked *