1 #pragma once
2 // bitblock.hpp : bitblock class
3 //
4 // Copyright (C) 2017-2021 Stillwater Supercomputing, Inc.
5 //
6 // This file is part of the universal numbers project, which is released under an MIT Open Source license.
7 #include <sstream>
8 #include <iostream>
9 #include <iomanip>
10 // this should be removed when we have made the transition away from std::bitset to sw::unum::bitblock
11 #include <cassert>
12 #include <bitset>
13 #include <universal/native/boolean_logic_operators.hpp>
14 #include <universal/internal/bitblock/exceptions.hpp>
15
16 namespace sw::universal::internal {
17
18 // bitblock is a template class implementing efficient multi-precision binary arithmetic and logic
19 template<size_t nbits>
20 class bitblock : public std::bitset<nbits> {
21 using base= std::bitset<nbits>;
22 public:
bitblock()23 constexpr bitblock() : base(0ull) {}
24
25 constexpr bitblock(const bitblock&) = default;
26 constexpr bitblock(bitblock&&) = default;
27
28 constexpr bitblock& operator=(const bitblock&) = default;
29 constexpr bitblock& operator=(bitblock&&) = default;
30
operator =(unsigned long long rhs)31 constexpr bitblock& operator=(unsigned long long rhs) {
32 return *this = (bitblock&)base::operator=(rhs);
33 }
34
reset()35 constexpr base& reset() { *this= bitblock{}; return *this; }
36 using base::reset; // make unary reset visible
37
setToZero()38 void setToZero() { std::bitset<nbits>::reset(); }
load_bits(const std::string & string_of_bits)39 bool load_bits(const std::string& string_of_bits) {
40 if (string_of_bits.length() != nbits) return false;
41 setToZero();
42 int msb = nbits - 1;
43 for (std::string::const_iterator it = string_of_bits.begin(); it != string_of_bits.end(); ++it) {
44 if (*it == '0') {
45 this->reset(msb--);
46 }
47 else if (*it == '1') {
48 this->set(msb--);
49 }
50 else {
51 return false;
52 }
53 }
54 return true;
55 }
56 };
57
58 // logic operators
59
60 // this comparison is for a two's complement number only
61 template<size_t nbits>
twosComplementLessThan(const bitblock<nbits> & lhs,const bitblock<nbits> & rhs)62 bool twosComplementLessThan(const bitblock<nbits>& lhs, const bitblock<nbits>& rhs) {
63 // comparison of the sign bit
64 if (lhs[nbits - 1] == 0 && rhs[nbits - 1] == 1) return false;
65 if (lhs[nbits - 1] == 1 && rhs[nbits - 1] == 0) return true;
66 // sign is equal, compare the remaining bits
67 if (nbits > 1) {
68 for (int i = static_cast<int>(nbits) - 2; i >= 0; --i) {
69 if (lhs[size_t(i)] == 0 && rhs[size_t(i)] == 1) return true;
70 if (lhs[size_t(i)] == 1 && rhs[size_t(i)] == 0) return false;
71 }
72 }
73 // numbers are equal
74 return false;
75 }
76
77 // this comparison works for any number
78 template<size_t nbits>
operator ==(const bitblock<nbits> & lhs,const bitblock<nbits> & rhs)79 bool operator==(const bitblock<nbits>& lhs, const bitblock<nbits>& rhs) {
80 // compare remaining bits
81 if constexpr (nbits > 0) {
82 for (size_t i = 0; i < nbits; ++i) if (lhs[i] != rhs[i]) return false;
83 }
84 // numbers are equal
85 return true;
86 }
87
88 // this comparison is for unsigned numbers only
89 template<size_t nbits>
operator <(const bitblock<nbits> & lhs,const bitblock<nbits> & rhs)90 bool operator< (const bitblock<nbits>& lhs, const bitblock<nbits>& rhs) {
91 // compare remaining bits
92 for (int i = static_cast<int>(nbits) - 1; i >= 0; --i) {
93 if (lhs[size_t(i)] == 0 && rhs[size_t(i)] == 1) return true;
94 if (lhs[size_t(i)] == 1 && rhs[size_t(i)] == 0) return false;
95 }
96 // numbers are equal
97 return false;
98 }
99
100 // test less than or equal for unsigned numbers only
101 template<size_t nbits>
operator <=(const bitblock<nbits> & lhs,const bitblock<nbits> & rhs)102 bool operator<= (const bitblock<nbits>& lhs, const bitblock<nbits>& rhs) {
103 // compare remaining bits
104 for (int i = static_cast<int>(nbits) - 1; i >= 0; --i) {
105 if (lhs[size_t(i)] == 0 && rhs[size_t(i)] == 1) return true;
106 if (lhs[size_t(i)] == 1 && rhs[size_t(i)] == 0) return false;
107 }
108 // numbers are equal
109 return true;
110 }
111
112 // test greater than for unsigned numbers only
113 template<size_t nbits>
operator >(const bitblock<nbits> & lhs,const bitblock<nbits> & rhs)114 bool operator> (const bitblock<nbits>& lhs, const bitblock<nbits>& rhs) {
115 // compare remaining bits
116 if constexpr (nbits > 0) {
117 for (int i = static_cast<int>(nbits) - 1; i >= 0; --i) {
118 if (lhs[size_t(i)] == 0 && rhs[size_t(i)] == 1) return false;
119 if (lhs[size_t(i)] == 1 && rhs[size_t(i)] == 0) return true;
120 }
121 }
122 // numbers are equal
123 return false;
124 }
125
126 // this comparison is for unsigned numbers only
127 template<size_t nbits>
operator >=(const bitblock<nbits> & lhs,const bitblock<nbits> & rhs)128 bool operator>= (const bitblock<nbits>& lhs, const bitblock<nbits>& rhs) {
129 // compare remaining bits
130 for (int i = static_cast<int>(nbits) - 1; i >= 0; --i) {
131 if (lhs[size_t(i)] == 0 && rhs[size_t(i)] == 1) return false;
132 if (lhs[size_t(i)] == 1 && rhs[size_t(i)] == 0) return true;
133 }
134 // numbers are equal
135 return true;
136 }
137
138 ////////////////////////////// ARITHMETIC functions
139
140
141 //////////////////////////////////////////////////////////////////////////////////////
142 // increment and decrement
143
144 // increment the input bitset in place, and return true if there is a carry generated.
145 template<size_t nbits>
increment_bitset(bitblock<nbits> & number)146 bool increment_bitset(bitblock<nbits>& number) {
147 bool carry = true; // ripple carry
148 for (size_t i = 0; i < nbits; i++) {
149 bool _a = number[i];
150 number[i] = bxor(_a, carry);
151 carry = carry && bxor(_a, false);
152 }
153 return carry;
154 }
155
156 // increment the input bitset in place, and return true if there is a carry generated.
157 // The input number is assumed to be right adjusted starting at nbits-nrBits
158 // [1 0 0 0] nrBits = 0 is a noop as there is no word to increment
159 // [1 0 0 0] nrBits = 1 is the word [1]
160 // [1 0 0 0] nrBits = 2 is the word [1 0]
161 // [1 1 0 0] nrBits = 3 is the word [1 1 0], etc.
162 template<size_t nbits>
increment_unsigned(bitblock<nbits> & number,size_t nrBits=nbits-1)163 bool increment_unsigned(bitblock<nbits>& number, size_t nrBits = nbits - 1) {
164 if (nrBits > nbits - 1) nrBits = nbits - 1; // check/fix argument
165 bool carry = 1; // ripple carry
166 size_t lsb = nbits - nrBits;
167 for (size_t i = lsb; i < nbits; i++) {
168 bool _a = number[i];
169 number[i] = bxor(_a, carry);
170 carry = (_a && false) || (carry && bxor(_a, false));
171 }
172 return carry;
173 }
174
175 // decrement the input bitset in place, and return true if there is a borrow generated.
176 template<size_t nbits>
decrement_bitset(bitblock<nbits> & number)177 bool decrement_bitset(bitblock<nbits>& number) {
178 bool borrow = true;
179 for (size_t i = 0; i < nbits; i++) {
180 bool _a = number[i];
181 number[i] = bxor(_a, borrow);
182 borrow = (!bxor(!_a, true) && borrow);
183 }
184 return borrow;
185 }
186
187 //////////////////////////////////////////////////////////////////////////////////////
188 // add and subtract
189
190 // add bitsets a and b and return result in bitset sum. Return true if there is a carry generated.
191 template<size_t nbits>
add_unsigned(bitblock<nbits> a,bitblock<nbits> b,bitblock<nbits+1> & sum)192 bool add_unsigned(bitblock<nbits> a, bitblock<nbits> b, bitblock<nbits + 1>& sum) {
193 bool carry = false; // ripple carry
194 for (size_t i = 0; i < nbits; i++) {
195 bool _a = a[i];
196 bool _b = b[i];
197 sum[i] = bxor(_a, bxor(_b, carry));
198 carry = (_a && _b) || (carry && bxor(_a, _b));
199 }
200 sum.set(nbits, carry);
201 return carry;
202 }
203
204 // subtract bitsets a and b and return result in bitset dif. Return true if there is a borrow generated.
205 template<size_t nbits>
subtract_unsigned(bitblock<nbits> a,bitblock<nbits> b,bitblock<nbits+1> & dif)206 bool subtract_unsigned(bitblock<nbits> a, bitblock<nbits> b, bitblock<nbits + 1>& dif) {
207 bool borrow = false; // ripple borrow
208 for (size_t i = 0; i < nbits; i++) {
209 bool _a = a[i];
210 bool _b = b[i];
211 dif[i] = bxor(bxor(_a, _b), borrow);
212 borrow = (!_a && _b) || (!bxor(!_a, !_b) && borrow);
213 }
214 dif.set(nbits, borrow);
215 return borrow;
216 }
217
218 template<size_t nbits>
add_signed_magnitude(bitblock<nbits> a,bitblock<nbits> b,bitblock<nbits> & sum)219 bool add_signed_magnitude(bitblock<nbits> a, bitblock<nbits> b, bitblock<nbits>& sum) {
220 uint8_t carry = 0;
221 if (nbits > 1) { // need at least 1 bit of magnitude to add
222 bool sign_a = a.test(nbits - 1);
223 if (sign_a) {
224 a = a.flip();
225 carry += 1;
226 }
227 bool sign_b = b.test(nbits - 1);
228 if (sign_b) {
229 b = b.flip();
230 carry += 1;
231 }
232
233 for (size_t i = 0; i < nbits - 2; i++) {
234 bool _a = a[i];
235 bool _b = b[i];
236 sum[i] = bxor(bxor(_a, _b), carry);
237 carry = (_a && _b) || (carry && bxor(_a, _b));
238 }
239 }
240 return carry;
241 }
242
243 template<size_t nbits>
subtract_signed_magnitude(bitblock<nbits> a,bitblock<nbits> b,bitblock<nbits> & diff)244 bool subtract_signed_magnitude(bitblock<nbits> a, bitblock<nbits> b, bitblock<nbits>& diff) {
245 //bool sign_a = a.test(nbits - 1);
246 //bool sign_b = b.test(nbits - 1);
247 std::cerr << "subtract_signed_magnitude not implemented yet" << std::endl;
248 return false;
249 }
250
251 // integral type to bitblock transformations
252
253 // we are using a full nbits sized bitset even though nbits-3 is the maximum fraction
254 // a posit would contain. However, we need an extra bit after the cut-off to make the
255 // round up/down decision. The <nbits-something> size created a lot of sw complexity
256 // that isn't worth the trouble, so we are simplifying and simply manage a full nbits
257 // of fraction bits.
258
259 template<size_t nbits>
extract_23b_fraction(uint32_t _23b_fraction_without_hidden_bit)260 bitblock<nbits> extract_23b_fraction(uint32_t _23b_fraction_without_hidden_bit) {
261 bitblock<nbits> _fraction;
262 uint32_t mask = uint32_t(0x00400000ul);
263 unsigned int ub = (nbits < 23 ? nbits : 23);
264 for (unsigned int i = 0; i < ub; i++) {
265 _fraction[nbits - 1 - i] = _23b_fraction_without_hidden_bit & mask;
266 mask >>= 1;
267 }
268 return _fraction;
269 }
270
271 template<size_t nbits>
extract_52b_fraction(uint64_t _52b_fraction_without_hidden_bit)272 bitblock<nbits> extract_52b_fraction(uint64_t _52b_fraction_without_hidden_bit) {
273 bitblock<nbits> _fraction;
274 uint64_t mask = uint64_t(0x0008000000000000ull);
275 unsigned int ub = (nbits < 52 ? nbits : 52);
276 for (unsigned int i = 0; i < ub; i++) {
277 _fraction[nbits - 1 - i] = _52b_fraction_without_hidden_bit & mask;
278 mask >>= 1;
279 }
280 return _fraction;
281 }
282
283 template<size_t nbits>
extract_63b_fraction(uint64_t _63b_fraction_without_hidden_bit)284 bitblock<nbits> extract_63b_fraction(uint64_t _63b_fraction_without_hidden_bit) {
285 bitblock<nbits> _fraction;
286 uint64_t mask = uint64_t(0x4000000000000000ull);
287 unsigned int ub = (nbits < 63 ? nbits : 63);
288 for (unsigned int i = 0; i < ub; i++) {
289 _fraction[nbits - 1 - i] = _63b_fraction_without_hidden_bit & mask;
290 mask >>= 1;
291 }
292 return _fraction;
293 }
294
295 // 128 bit unsigned int mapped to two uint64_t elements
296 typedef struct __uint128 {
297 uint64_t lower;
298 uint64_t upper;
299 } uint128;
300
301 // take in a long double mapped to two uint64_t elements
302 template<size_t nbits>
extract_long_double_fraction(uint128 * _112b_fraction_without_hidden_bit)303 bitblock<nbits> extract_long_double_fraction(uint128* _112b_fraction_without_hidden_bit) {
304 bitblock<nbits> _fraction;
305 int msb = nbits - 1;
306 uint64_t mask = uint64_t(0x0000800000000000ull);
307 unsigned int ub = (nbits < 48 ? nbits : 48); // 48 bits in the upper half
308 for (unsigned int i = 0; i < ub; i++) {
309 _fraction[msb--] = _112b_fraction_without_hidden_bit->upper & mask;
310 mask >>= 1;
311 }
312 mask = uint64_t(0x8000000000000000ull);
313 ub = (nbits < 112 - 48 ? nbits : 112 - 48); // max 64 bits in the lower half
314 for (unsigned int i = 0; i < ub; i++) {
315 _fraction[msb--] = _112b_fraction_without_hidden_bit->lower & mask;
316 mask >>= 1;
317 }
318 return _fraction;
319 }
320
321 template<size_t nbits>
copy_integer_fraction(unsigned long long _fraction_without_hidden_bit)322 bitblock<nbits> copy_integer_fraction(unsigned long long _fraction_without_hidden_bit) {
323 bitblock<nbits> _fraction;
324 uint64_t mask = uint64_t(0x8000000000000000ull);
325 unsigned int ub = (nbits < 64 ? nbits : 64);
326 for (unsigned int i = 0; i < ub; i++) {
327 _fraction[nbits - 1 - i] = _fraction_without_hidden_bit & mask;
328 mask >>= 1;
329 }
330 return _fraction;
331 }
332
333 ////////////////////////////////////////////////////////////////////////////////////////
334 // bitset copy and slice operators
335
336 // copy a bitset into a bigger bitset starting at position indicated by the shift value
337 template<size_t src_size, size_t tgt_size>
copy_into(const bitblock<src_size> & src,size_t shift,bitblock<tgt_size> & tgt)338 void copy_into(const bitblock<src_size>& src, size_t shift, bitblock<tgt_size>& tgt) {
339 tgt.reset();
340 for (size_t i = 0; i < src_size; i++)
341 tgt.set(i + shift, src[i]);
342 }
343
344 // TODO: is this guard named correctly?
345 #if BITBLOCK_THROW_ARITHMETIC_EXCEPTION
346 // copy a slice of a bitset into a bigger bitset starting at position indicated by the shift value
347 template<size_t src_size, size_t tgt_size>
copy_slice_into(bitblock<src_size> & src,bitblock<tgt_size> & tgt,size_t begin=0,size_t end=src_size,size_t shift=0)348 void copy_slice_into(bitblock<src_size>& src, bitblock<tgt_size>& tgt, size_t begin = 0, size_t end = src_size, size_t shift = 0) {
349 // do NOT reset the target!!!
350 if (end <= src_size) throw iteration_bound_too_large{};
351 if (end + shift < tgt_size) throw iteration_bound_too_large{};
352 for (size_t i = begin; i < end; i++)
353 tgt.set(i + shift, src[i]);
354 }
355 #else // !BITBLOCK_THROW_ARITHMETIC_EXCEPTION
356 // copy a slice of a bitset into a bigger bitset starting at position indicated by the shift value
357 template<size_t src_size, size_t tgt_size>
copy_slice_into(bitblock<src_size> & src,bitblock<tgt_size> & tgt,size_t begin=0,size_t end=src_size,size_t shift=0)358 void copy_slice_into(bitblock<src_size>& src, bitblock<tgt_size>& tgt, size_t begin = 0, size_t end = src_size, size_t shift = 0) {
359 // do NOT reset the target!!!
360 if (end <= src_size) return;
361 if (end + shift < tgt_size) return;
362 for (size_t i = begin; i < end; i++)
363 tgt.set(i + shift, src[i]);
364 }
365 #endif // !BITBLOCK_THROW_ARITHMETIC_EXCEPTION
366
367 template<size_t from, size_t to, size_t src_size>
fixed_subset(const bitblock<src_size> & src)368 bitblock<to - from> fixed_subset(const bitblock<src_size>& src) {
369 static_assert(from <= to, "from cannot be larger than to");
370 static_assert(to <= src_size, "to is larger than src_size");
371
372 bitblock<to - from> result;
373 for (size_t i = 0, end = to - from; i < end; ++i)
374 result[i] = src[i + from];
375 return result;
376 }
377
378 //////////////////////////////////////////////////////////////////////////////////////
379 // multiply and divide
380
381 // accumulate the addend to a running accumulator
382 template<size_t src_size, size_t tgt_size>
accumulate(const bitblock<src_size> & addend,bitblock<tgt_size> & accumulator)383 bool accumulate(const bitblock<src_size>& addend, bitblock<tgt_size>& accumulator) {
384 bool carry = 0; // ripple carry
385 for (size_t i = 0; i < src_size; i++) {
386 bool _a = addend[i];
387 bool _b = accumulator[i];
388 accumulator[i] = bxor(bxor(_a, _b), carry);
389 carry = (_a && _b) || (carry && bxor(_a, _b));
390 }
391 return carry;
392 }
393
394 // multiply bitsets a and b and return result in bitset result.
395 template<size_t operand_size>
multiply_unsigned(const bitblock<operand_size> & a,const bitblock<operand_size> & b,bitblock<2* operand_size> & result)396 void multiply_unsigned(const bitblock<operand_size>& a, const bitblock<operand_size>& b, bitblock<2 * operand_size>& result) {
397 constexpr size_t result_size = 2 * operand_size;
398 bitblock<result_size> addend;
399 result.reset();
400 if (a.test(0)) {
401 copy_into<operand_size, result_size>(b, 0, result);
402 }
403 for (size_t i = 1; i < operand_size; i++) {
404 if (a.test(i)) {
405 copy_into<operand_size, result_size>(b, i, addend);
406 #ifdef DEBUG
407 bool carry = accumulate(addend, result); // we should never have a carry
408 assert(carry == false);
409 #else
410 accumulate(addend, result); // we should never have a carry
411 #endif
412 }
413 }
414 }
415
416 // subtract a subtractand from a running accumulator
417 template<size_t src_size, size_t tgt_size>
subtract(bitblock<tgt_size> & accumulator,const bitblock<src_size> & subtractand)418 bool subtract(bitblock<tgt_size>& accumulator, const bitblock<src_size>& subtractand) {
419 bool borrow = 0; // ripple borrow
420 for (size_t i = 0; i < src_size; i++) {
421 bool _a = accumulator[i];
422 bool _b = subtractand[i];
423 accumulator[i] = bxor(bxor(_a, _b), borrow);
424 borrow = (!_a && _b) || (!bxor(!_a, !_b) && borrow);
425 }
426 return borrow;
427 }
428
429 // divide bitsets a and b and return result in bitset result.
430 template<size_t operand_size>
integer_divide_unsigned(const bitblock<operand_size> & a,const bitblock<operand_size> & b,bitblock<2* operand_size> & result)431 void integer_divide_unsigned(const bitblock<operand_size>& a, const bitblock<operand_size>& b, bitblock<2 * operand_size>& result) {
432 bitblock<operand_size> subtractand, accumulator;
433 result.reset();
434 accumulator = a;
435 int msb = findMostSignificantBit(b);
436 if (msb < 0) {
437 #if BITBLOCK_THROW_ARITHMETIC_EXCEPTION
438 throw bitblock_divide_by_zero{};
439 #else
440 std::cerr << "bitblock_divide_by_zero\n";
441 #endif // BITBLOCK_THROW_ARITHMETIC_EXCEPTION
442 }
443 else {
444 int shift = static_cast<int>(operand_size) - msb - 1;
445 // prepare the subtractand
446 subtractand = b;
447 subtractand <<= static_cast<size_t>(shift);
448 // for (int i = operand_size - msb - 1; i >= 0; --i) {
449 for (int i = shift; i >= 0; --i) {
450
451 if (subtractand <= accumulator) {
452 #ifdef DEBUG
453 bool borrow = subtract(accumulator, subtractand);
454 assert(borrow == true);
455 #else
456 subtract(accumulator, subtractand);
457 #endif
458 result.set(static_cast<size_t>(i));
459 }
460 else {
461 result.reset(static_cast<size_t>(i));
462 }
463 subtractand >>= 1ull;
464 }
465 }
466 }
467
468 // divide bitsets a and b and return result in bitset result.
469 // By providing more bits in the result, the algorithm will fill these with fraction bits if available.
470 // Radix point must be maintained by calling function.
471 template<size_t operand_size, size_t result_size>
divide_with_fraction(const bitblock<operand_size> & a,const bitblock<operand_size> & b,bitblock<result_size> & result)472 void divide_with_fraction(const bitblock<operand_size>& a, const bitblock<operand_size>& b, bitblock<result_size>& result) {
473 bitblock<result_size> subtractand, accumulator;
474 result.reset();
475 copy_into<operand_size, result_size>(a, result_size - operand_size, accumulator);
476 int msb = findMostSignificantBit(b);
477 if (msb < 0) {
478 #if BITBLOCK_THROW_ARITHMETIC_EXCEPTION
479 throw bitblock_divide_by_zero{};
480 #else
481 std::cerr << "bitblock_divide_by_zero\n";
482 #endif // BITBLOCK_THROW_ARITHMETIC_EXCEPTION
483 }
484 else {
485 int shift = static_cast<int>(operand_size) - msb - 1;
486 // prepare the subtractand
487 copy_into<operand_size, result_size>(b, result_size - operand_size, subtractand);
488 subtractand <<= static_cast<size_t>(shift);
489 for (int i = static_cast<int>(result_size) - msb - 1; i >= 0; --i) {
490 //std::cout << "accumulator " << accumulator << std::endl;
491 //std::cout << "subtractand " << subtractand << std::endl;
492 if (subtractand <= accumulator) {
493 #ifdef DEBUG
494 bool borrow = subtract(accumulator, subtractand);
495 assert(borrow == false);
496 #else
497 subtract(accumulator, subtractand);
498 #endif
499 result.set(static_cast<size_t>(i));
500 }
501 else {
502 result.reset(static_cast<size_t>(i));
503 }
504 //std::cout << "result " << result << std::endl;
505 subtractand >>= 1u;
506 }
507 }
508 }
509
510 //////////////////////////////////////////////////////////////////////////////////////
511 // truncating and rounding
512
513 // truncate right-side
514 template<size_t src_size, size_t tgt_size>
truncate(bitblock<src_size> & src,bitblock<tgt_size> & tgt)515 void truncate(bitblock<src_size>& src, bitblock<tgt_size>& tgt) {
516 tgt.reset();
517 for (size_t i = 0; i < tgt_size; i++)
518 tgt.set(tgt_size - 1 - i, src[src_size - 1 - i]);
519 }
520
521 // round
522 template<size_t tgt_size, size_t src_size>
523 struct round_t
524 {
evalsw::universal::internal::round_t525 static bitblock<tgt_size> eval(const bitblock<src_size>& src, size_t n)
526 {
527 static_assert(src_size > 0 && tgt_size > 0, "We don't bother with empty sets.");
528 #if BITBLOCK_THROW_ARITHMETIC_EXCEPTION
529 if (n >= src_size)
530 throw round_off_all{};
531 // look for cut-off leading bits
532 for (size_t leading = tgt_size + n; leading < src_size; ++leading)
533 if (src[leading])
534 throw cut_off_leading_bit{};
535 #else
536 if (n >= src_size) {
537 bitblock<tgt_size> result;
538 result.reset();
539 return result;
540 }
541 for (size_t leading = tgt_size + n; leading < src_size; ++leading) {
542 if (src[leading]) {
543 std::cerr << "cut_off_leading_bit\n";
544 bitblock<tgt_size> result;
545 result.reset();
546 return result;
547 }
548 }
549 #endif // BITBLOCK_THROW_ARITHMETIC_EXCEPTION
550
551 bitblock<tgt_size> result((src >> n).to_ullong()); // convert to size_t to deal with different sizes
552
553 if (n > 0 && src[n - 1]) { // round up potentially if first cut-off bit is true
554 #ifdef BITBLOCK_ROUND_TIES_AWAY_FROM_ZERO // TODO: Evil hack to be consistent with assign_fraction, for testing only
555 result = result.to_ullong() + 1;
556 #else
557
558 bool more_bits = false;
559 for (long i = 0; i + 1 < n && !more_bits; ++i)
560 more_bits |= src[i];
561 if (more_bits) {
562 result = result.to_ullong() + 1; // increment_unsigned is ambiguous
563 }
564 else { // tie: round up odd number
565 #ifndef BITBLOCK_ROUND_TIES_TO_ZERO // TODO: evil hack to be removed later
566 if (result[0])
567 result = result.to_ullong() + 1;
568 #endif
569 }
570 #endif
571 }
572 return result;
573 }
574 };
575
576 template<size_t src_size>
577 struct round_t<0, src_size>
578 {
evalsw::universal::internal::round_t579 static bitblock<0> eval(const bitblock<src_size>&, size_t)
580 {
581 return {};
582 }
583 };
584
585
586
587 /** Round off \p n last bits of bitset \p src. Round to nearest resulting in potentially smaller bitset.
588 * Doesn't return carry bit in case of overflow while rounding up! TODO: Check whether we need carry or we require an extra bit for this case.
589 */
590 template<size_t tgt_size, size_t src_size>
round(const bitblock<src_size> & src,size_t n)591 bitblock<tgt_size> round(const bitblock<src_size>& src, size_t n)
592 {
593 return round_t<tgt_size, src_size>::eval(src, n);
594 }
595
596
597 ////////////////////////////// HELPER functions
598
599 // find the MSB, return position if found, return -1 if no bits are set
600 template<size_t nbits>
findMostSignificantBit(const bitblock<nbits> & bits)601 int findMostSignificantBit(const bitblock<nbits>& bits) {
602 int msb = -1; // indicative of no bits set
603 for (int i = nbits - 1; i >= 0; i--) {
604 if (bits.test(static_cast<size_t>(i))) {
605 msb = i;
606 break;
607 }
608 }
609 return msb;
610 }
611
612 // calculate the 1's complement of a sign-magnitude encoded number
613 template<size_t nbits>
ones_complement(bitblock<nbits> number)614 bitblock<nbits> ones_complement(bitblock<nbits> number) {
615 bitblock<nbits> complement;
616 for (size_t i = 0; i < nbits; i++) {
617 complement.set(i, !number[i]);
618 }
619 return complement;
620 }
621
622 // calculate the 2's complement of a 2's complement encoded number
623 template<size_t nbits>
twos_complement(bitblock<nbits> number)624 bitblock<nbits> twos_complement(bitblock<nbits> number) {
625 bitblock<nbits> complement;
626 uint8_t _slice = 0;
627 uint8_t carry = 1;
628 for (size_t i = 0; i < nbits; i++) {
629 uint8_t not_bit_at_i = number[i] ? uint8_t(0) : uint8_t(1);
630 _slice = uint8_t(not_bit_at_i + carry);
631 // _slice = uint8_t(!number[i]) + carry;
632 carry = uint8_t(_slice >> 1);
633 complement[i] = (0x1 & _slice);
634 }
635 return complement;
636 }
637
638 // DANGER: this depends on the implicit type conversion of number to a uint64_t to sign extent a 2's complement number system
639 // if nbits > 64 then this code breaks.
640 template<size_t nbits, class Type>
convert_to_bitblock(Type number)641 bitblock<nbits> convert_to_bitblock(Type number) {
642 bitblock<nbits> _Bits;
643 uint64_t mask = 1ull;
644 for (size_t i = 0; i < nbits; i++) {
645 _Bits[i] = mask & number;
646 mask <<= 1;
647 }
648 return _Bits;
649 }
650
651 template<size_t nbits>
to_bit_string(bitblock<nbits> bits,bool separator=true)652 std::string to_bit_string(bitblock<nbits> bits, bool separator = true) {
653 std::stringstream ss;
654 int msb = nbits; // compilation warning work-around for nbits = 0
655 for (int i = msb - 1; i >= 0; --i) {
656 ss << (bits[std::size_t(i)] ? "1" : "0");
657 if (separator && i % 4 == 0 && i != 0) ss << "'";
658 }
659 return ss.str();
660 }
661
662 template<size_t nbits>
to_hex(bitblock<nbits> bits)663 std::string to_hex(bitblock<nbits> bits) {
664 char str[(nbits >> 2) + 2]; // plenty of room
665 for (size_t i = 0; i < (nbits >> 2) + 2; ++i) str[i] = 0;
666 //const char* hexits = "0123456789ABCDEF";
667 const char* hexits = "0123456789abcdef";
668 unsigned int maxHexDigits = (nbits >> 2) + ((nbits % 4) ? 1 : 0);
669 for (unsigned int i = 0; i < maxHexDigits; i++) {
670 unsigned int hexit;
671 switch (nbits) {
672 case 1:
673 hexit = bits[0];
674 break;
675 case 2:
676 hexit = static_cast<unsigned int>((bits[1] << 1u) + bits[0]);
677 break;
678 case 3:
679 hexit = static_cast<unsigned int>((bits[2] << 2u) + (bits[1] << 1u) + bits[0]);
680 break;
681 default:
682 hexit = static_cast<unsigned int>((bits[3] << 3u) + (bits[2] << 2u) + (bits[1] << 1u) + bits[0]);
683 break;
684 }
685 str[maxHexDigits - 1 - i] = hexits[hexit];
686 bits >>= 4;
687 }
688 str[maxHexDigits] = 0; // null terminated string
689 return std::string(str);
690 }
691
692 // convert a sign/magnitude number to a string
693 template<size_t nbits>
sign_magnitude_to_string(bitblock<nbits> bits)694 std::string sign_magnitude_to_string(bitblock<nbits> bits) {
695 std::stringstream ss;
696 ss << (bits[nbits - 1] ? "n-" : "p-");
697 if (nbits < 2) return ss.str();
698 for (int i = nbits - 2; i >= 0; --i) {
699 ss << (bits[i] ? "1" : "0");
700 }
701 return ss.str();
702 }
703
704 // return a new bitset with the sign flipped as compared to the input bitset
705 template<size_t nbits>
flip_sign_bit(bitblock<nbits> number)706 bitblock<nbits> flip_sign_bit(bitblock<nbits> number) {
707 number.flip(nbits - 1);
708 return number;
709 }
710
711 // sticky bit representation of all the bits from [msb, lsb], that is, msb is included
712 template<size_t nbits>
anyAfter(const bitblock<nbits> & bits,int msb)713 bool anyAfter(const bitblock<nbits>& bits, int msb) {
714 if (msb < 0) return false; // bad input
715 bool running = false;
716 for (int i = msb; i >= 0; i--) {
717 running |= bits.test(size_t(i));
718 }
719 return running;
720 }
721
722 } // namespace sw::universal::internal
723