Multiple-Precision Arithmetic Library
Overview
The simulated architecture often uses word sizes and the set of arithmetic operations different from those supplied by the simulator host. The mulitple-precision arithmetic library implements type-safe albitriary-precision integer and floating-point types.
The library defines two public headers: <sulima/int> for integer arithmetic and <sulima/fp> for floating-point arithmetic.
NOTE: <sulima/fp> and arithmetic on types wider than the largest fundamental integer type are currently unimplemented. On 32 bit platforms, 64 bit integers can be obtained by compiling with the -DUSE_LONG_LONG option and a compiler that implements the long long type (ie. GCC or TenDRA.)
The library uses a namespace LIA to hide names internal to the library. It also reserves any uppercase identifiers with the LIA_ prefix for use as macros. The acronym ``LIA'' refers to the ISO/IEC 10967 standard for language-independant arithmetic which the library attempts to conform to.
Integer types
On parametised integer types is provided by the library:
SIGNED
UNSIGNED
typeid Int<n>
typeid Int<n,s>
which represent integers modulo 2n (n is any positive integer.) The parameter s is of type IntKind, an enumeration type that defines the SIGNED and UNSIGNED constants. If ommited, it has the default value of SIGNED.
The two types Int<n,SIGNED> and Int<n,UNSIGNED> are identical (and can be converted implicitely to each other), except that operators that do not compute a result modulo 2n, such as / and %, interpret Int<n,SIGNED> values as integers in the range [-2n-1, 2n-1), and Int<n,UNSIGNED> values as integer in the range [0, 2n).
Int<n> objects can be default-initialized to 0, constructed uninitialised from the Uninitialised object from <sulima/base>, constructed from another Int<n,s> object, or constructed from a sign-extended fundamental int type. The final constructor, and all other functions accepting int arguments, are supplied to allow easy introduction of C++ literals (eg. saying x + 5) and therefore are implemented with an assumption that the int argument is a compile-time constant.
I intentionally omit implicit conversion between integer types of different width. Mixed-kind arithmetic (ie. supplying a signed and an unsigned value to a binary operator) are supported on most operators. The exceptions are the / and % operators, for which the result of a mixed-kind operation is not well-defined.
Integer traits
typename IntTraits<T>::Int
typename IntTraits<T>::Nat
bool IntTraits<T>::is_integer
bool IntTraits<T>::is_signed
int IntTraits<T>::width
The IntTraits template provides easy access to some integer properties. In particular, it exposes the signed and unsigned variety of a type (the Int and Nat type names), its sign properties (is_signed) and width in bits (width). The is_integer trait indicates whether the type is an integer type or not. The other members are meaningful only if is_integer is true.
IntTraits has been implemented (specialized) for all standard C++ integer types as well as Int<n,s> fixed-width type.
Member operators
The following usual operators are implemented on Int<n,s>:
Int<n,s> Int<n,s>::operator++ (int)
Int<n,s> Int<n,s>::operator-- (int)
Int<n,s>& Int<n,s>::operator++ ()
Nat<n,s>& Nat<n,s>::operator++ ()
Int<n,s>& Int<n,s>::operator-- ()
Nat<n,s>& Nat<n,s>::operator-- ()
Int<n,s>& Int<n,s>::operator= (Int<n,t> x)
Int<n,s>& Int<n,s>::operator= (int x)
Int<n,s>& Int<n,s>::operator*= (Int<n,t> x)
Int<n,s>& Int<n,s>::operator*= (int x)
Int<n,s>& Int<n,s>::operator/= (Int<n,s> x)
Int<n,s>& Int<n,s>::operator/= (int x)
Int<n,s>& Int<n,s>::operator%= (Int<n,s> x)
Int<n,s>& Int<n,s>::operator%= (int x)
Int<n,s>& Int<n,s>::operator+= (Int<n,t> x)
Int<n,s>& Int<n,s>::operator+= (int x)
Int<n,s>& Int<n,s>::operator-= (Int<n,t> x)
Int<n,s>& Int<n,s>::operator-= (int x)
Int<n,s>& Int<n,s>::operator<<= (int x)
Int<n,s>& Int<n,s>::operator>>= (int x)
Int<n,s>& Int<n,s>::operator&= (Int<n,t> x)
Int<n,s>& Int<n,s>::operator&= (int x)
Int<n,s>& Int<n,s>::operator^= (Int<n,t> x)
Int<n,s>& Int<n,s>::operator^= (int x)
Int<n,s>& Int<n,s>::operator|= (Int<n,t> x)
Int<n,s>& Int<n,s>::operator|= (int x)
These operators have the usual C++ semantics implemented in terms of other operators described below.
Arithmetic identity operator
Int<n,s> operator+ (Int<n,s> x)
The arithmetic identity operator; always returns x. This does not serve any useful purpose, and is provided only for completeness.
Two's complement operator
Int<n,s> operator- (Int<n,s> x)
Return two's complement (arithmetic negation modulo 2n) of x.
One's complement operator
Int<n,s> operator~ (Int<n,s> x)
Return one complement (bitwise negation) of x.
Multiplication operator
Int<n,u> operator* (Int<n,s> x, Int<n,t> y)
Int<n,s> operator* (Int<n,s> x, int y)
Int<n,s> operator* (int x, Int<n,s> y)
where:
u = (s == SIGNED and t == SIGNED) ? SIGNED : UNSIGNED
Return the product of x and y modulo 2n. Because we assume two's complement notation, both the signed and unsigned versions are the same.
Division operator
Int<n,s> operator/ (Int<n,s> x, Int<n,s> y)
Int<n,s> operator/ (Int<n,s> x, int y)
Int<n,s> operator/ (int x, Int<n,s> y)
Preconditions:
y != 0
Return the quotient of the division of x by y. The first three functions treat the operands as signed two's-complement numbers, and return a signed result. The remaining functions treat the operand as unsigned numbers and return unsigned result.
It is always the case that, if q = x / y and r = x % y then q * y + r == x. However, these functions round negative results in the same way as the native / operator (ie. either truncate towards 0 or round towards negative infinity.) If this is not what you want, use divide instead.
Remainder operator
Int<n,s> operator% (Int<n,s> x, Int<n,s> y)
Int<n,s> operator% (Int<n,s> x, int y)
Int<n,s> operator% (int x, Int<n,s> y)
Preconditions:
y != 0
Return the remainder of the division of x by y. The first three functions treat the operands as signed two's-complement numbers. The remaining functions treat the operand as unsigned numbers and return unsigned result.
It is always the case that, if q = x / y and r = x % y then q * y + r == x. However, these functions round quotient in the same way as the native % operator (ie. either truncate towards 0 or round towards negative infinity.) If this is not what you want, use divide instead.
Addition operator
Int<n,u> operator+ (Int<n,s> x, Int<n,t> y)
Int<n,s> operator+ (Int<n,s> x, int y)
Int<n,s> operator+ (int x, Int<n,s> y)
where:
u = (s == SIGNED and t == SIGNED) ? SIGNED : UNSIGNED
Return the sum of x and y modulo 2n.
Subtraction operator
Int<n,u> operator- (Int<n,s> x, Int<n,t> y)
Int<n,s> operator- (Int<n,s> x, int y)
Int<n,s> operator- (int x, Int<n,s> y)
where:
u = (s == SIGNED and t == SIGNED) ? SIGNED : UNSIGNED
Return the different of x and y modulo 2n.
Shift left operator
Int<n,s> operator<< (Int<n,s> x, int p)
Preconditions:
0 <= p < width(x)
Return x bit-shifted left by p bits. The p least-significant bits of the result are cleared.
Shift right operator
Int<n,s> operator>> (Int<n,s> x, int p)
Preconditions:
0 <= p < width(x)
Return x bit-shifted right by p bits. If x is an Int<n> or x >= 0, the p most-significant bits of the result are cleared. Otherwise, >> behaves like the host >> operator, ie. it will either clear the p most-significant bits or set them all to 1. If you need deterministic result, use shift_right or shift_right_arithmetic instead.
Relational operator
bool operator< (Int<n,s> x, Int<n,t> y)
bool operator< (Int<n,s> x, int y)
bool operator< (int x, Int<n,s> y)
Compare x and y. The remaining three relational operators are implemented as a generic template in <sulima/base>.
Note that comparison of mixed types is implemented correctly at the expense of additional runtime checks.
Equivalence operator
bool operator== (Int<n,s> x, Int<n,t> y)
bool operator== (Int<n,s> x, int y)
bool operator== (int x, Int<n,s> y)
Compare x and y for equality modulo 2n. The != operator is implemented as a generic template in <sulima/base>.
Bitwise AND operator
Int<n,u> operator& (Int<n,s> x, Int<n,t> y)
Int<n,s> operator& (Int<n,s> x, int y)
Int<n,s> operator& (int x, Int<n,s> y)
where:
u = (s == SIGNED and t == SIGNED) ? SIGNED : UNSIGNED
Return the logical product of x and y.
Bitwise exclusive OR operator
Int<n,u> operator^ (Int<n,s> x, Int<n,t> y)
Int<n,s> operator^ (Int<n,s> x, int y)
Int<n,s> operator^ (int x, Int<n,s> y)
where:
u = (s == SIGNED and t == SIGNED) ? SIGNED : UNSIGNED
Return the logical difference of x and y.
Bitwise inclusive OR operator
Int<n,u> operator| (Int<n,s> x, Int<n,t> y)
Int<n,s> operator| (Int<n,s> x, int y)
Int<n,s> operator| (int x, Int<n,s> y)
where:
u = (s == SIGNED and t == SIGNED) ? SIGNED : UNSIGNED
Return the logical sum of x and y.
Bit concatenation operator
Int<n+m,u> operator|| (Int<n,s> x, Int<m,t> y)
where:
u = (s == SIGNED and t == SIGNED) ? SIGNED : UNSIGNED
This final operator concatenates two integers into a single integer, using the notation borrowed from the MIPS technical reference manuals. This is made possible as the library forbids implicit conversion of integers to booleans.
The most-significant n bits of the result are taken from x. The least-significant m bits of the result are taken from y.
Integer width
int width(Int<n,s> x)
int width(int x)
Return the width of the integer in bits.
Power of two
bool is_power_of_two(int x)
bool is_power_of_two(Int<n,s> x)
Check if x is a positive power of two.
Shift left
Int<n,s> shift_left(Int<n,s> x, int p)
int shift_left(int x, int p)
Preconditions:
0 <= p < width(x)
Return x bit-shifted left by p bits. The p least-significant bits of the result are cleared.
Shift right logical
Int<n,s> shift_right(Int<n,s> x, int p)
int shift_right(int x, int p)
Preconditions:
0 <= p < width(x)
Return x bit-shifted right by p bits. The p most-significant bits of the result are cleared.
Shift right arithmetic
Int<n,s> shift_right_arithmetic(Int<n,s> x, int p)
int shift_right_arithmetic(int x, int p)
Preconditions:
0 <= p < width(x)
Return x bit-shifted right by p bits. The p most-significant bits of the result are filled with the sign bit of x.
Single bit mask
Int<n,s> bit_mask< Int<n,s> >(int p)
int bit_mask<int>(p)
Int<n,SIGNED> bit_mask<n>(int p)
Preconditions:
0 <= p < width(result)
Return an integer with bit p set to 1 and all other bits set to 0. The type of the result must be specified explicitely, either as a type or an integer width.
General bit mask
Int<n,s> bit_mask< Int<n,s> >(int p, int q)
int bit_mask<int>(p, int q)
Int<n,SIGNED> bit_mask<n>(int p, int q)
Preconditions:
0 <= p < q <= width(result)
Return an integer with all bits in the range [p, q) set to 1 and all other bits set to 0. The type of the result must be specified explicitely, either as a type or an integer width.
Sign mask
int sign_mask(int x)
Int<n,s> sign_mask(Int<n,s> x)
If x is negative, return -1. Otherwise, return 0.
Extract a bit
Int<n,s> bit(Int<n,s> x, int p)
int bit(int x, int p)
Preconditions:
0 <= p < width(x)
Return a value of bit p of x, where bit 0 represents the least-significant bit.
Clear a bit
Int<n,s> clear_bit(Int<n,s> x, int p)
int clear_bit(int x, int p)
Preconditions:
0 <= p < width(x)
Return a copy of x with bit p set to 0.
Set a bit
Int<n,s> set_bit(Int<n,s> x, int p)
int set_bit(int x, int p)
Preconditions:
0 <= p < width(x)
Return a copy of x with bit p set to 1.
Set a bit to a value
Int<n,s> set_bit(Int<n,s> x, int p, Int<m,t> y)
Int<n,s> set_bit(Int<n,s> x, int p, int y)
int set_bit(int x, int p, int y)
Preconditions:
0 <= p < width(x)
Return a copy of x with bit p set to bit(y, 0).
Extract bits
Int<n,s> bits(Int<n,s> x, p, q)
int bits(int x, p, q)
Preconditions:
0 <= p < q <= width(x)
Return the bits of x in the range [m,n). Bit p of x is returned in the least significant bit of the result.
Clear bits
Int<n,s> clear_bits(Int<n,s> x, p, q)
int clear_bits(int x, p, q)
Preconditions:
0 <= p < q <= width(x)
Return a copy of x with all bits in the range [p, q) cleared.
Set bits
Int<n,s> set_bits(Int<n,s> x, p, q)
int set_bits(int x, p, q)
Preconditions:
0 <= p < q <= width(x)
Return a copy of x with all bits in the range [p, q) set to 1.
Set bits to a value
Int<n,s> set_bits(Int<n> x, p, q, Int<m,t> y)
Int<n,s> set_bits(Int<n> x, p, q, int y)
int set_bits(int x, p, q, int y)
Preconditions:
0 <= p < q <= width(x)
q - p <= m
Return a copy of x with all bits in the range [p, q) set to sign_extend<q-p>(y, q-p).
Rotate left
Int<n.s> rotate_left(Int<n,s> x, int p)
int rotate_left(int x, int p)
Preconditions:
0 <= p < width(x)
Return x bit-shifted left by p bits. The p least-significant bits of the result are filled with the p most-significant bits of x.
Rotate right
Int<n,s> rotate_right(Int<n,s> x, int p)
int rotate_right(int x, int p)
Preconditions:
0 <= p < width(x)
Return x bit-shifted right by p bits. The p most-significant bits of the result are filled with the p least-significant bits of x.
Swap bytes
Int<n,s> swap_bytes(Int<n,s> x)
int swap_bytes(int x)
Return a copy of x with the order of octets reversed.
Absolute value
Int<n,s> abs(Int<n,s> x)
int abs(int x)
Return the absolute value of an integer.
Maximum
Int<n,s> max(Int<n,s> x, Int<n,s> y)
int max(int x, int y)
Return the larger of two integers.
Minimum
Int<n,s> min(Int<n,s> x, Int<n,s> y)
int min(int x, int y)
Return the smaller of two integers.
Population count
int population_count(Int<n,s> x)
int population_count(int x)
Return the number of bits set in x.
Leading zeroes
int leading_zeroes(Int<n,s> x)
int leading_zeroes(int x)
Return the number of cleared leading bits in x. The first leading bit is the most significant bit of x.
Trailing zeroes
int trailing_zeroes(Int<n,s> x)
int trailing_zeroes(int x)
Return the number of cleared trailing bits in x. The first trailing bit is the least significant bit of x.
Zero-extend an integer
Int<n,s> zero_extend< Int<n,s> >(Int<m,t> x, int p)
Int<n,s> zero_extend< Int<n,s> >(Int<m,t> x, int p)
Int<n,s> zero_extend< Int<n,s> >(int x, int p)
Int<n,s> zero_extend< Int<n,s> >(Int<m,t> x)
Int<n,s> zero_extend< Int<n,s> >(Int<m,t> x)
Int<n,s> zero_extend< Int<n,s> >(int x)
int zero_extend<int>(Int<n> x, int p)
int zero_extend<int>(Int<n> x, int p)
int zero_extend<int>(int x, int p)
Int<n> zero_extend<n>(int x, int p)
Int<n> zero_extend<n>(Int<m,s> x, int p)
Int<n> zero_extend<n>(Int<m,s> x, int p)
Int<n> zero_extend<n>(int x)
Int<n> zero_extend<n>(Int<m,s> x)
Int<n> zero_extend<n>(Int<m,s> x)
Preconditions:
0 <= p <= width(x)
truncate is identical to zero_extend: if sizeof(T) < sizeof(U), ``truncate'' is a more appropriate description than ``extend''.
Sign-extend an integer
Int<n,s> sign_extend< Int<n,s> >(Int<m,t> x, int p)
Int<n,s> sign_extend< Int<n,s> >(Int<m,t> x, int p)
Int<n,s> sign_extend< Int<n,s> >(int x, int p)
Int<n,s> sign_extend< Int<n,s> >(Int<m,t> x)
Int<n,s> sign_extend< Int<n,s> >(Int<m,t> x)
Int<n,s> sign_extend< Int<n,s> >(int x)
int sign_extend<int>(Int<n> x, int p)
int sign_extend<int>(Int<n> x, int p)
int sign_extend<int>(int x, int p)
Int<n> sign_extend<n>(int x, int p)
Int<n> sign_extend<n>(Int<m,s> x, int p)
Int<n> sign_extend<n>(Int<m,s> x, int p)
Int<n> sign_extend<n>(int x)
Int<n> sign_extend<n>(Int<m,s> x)
Int<n> sign_extend<n>(Int<m,s> x)
Preconditions:
0 <= p <= width(x)
Convert x to the returned type, which must be specified explicitely, either as a type or an integer width. The least-significant min(p, width(result)) bits of the result are taken from x. The remaining bits (if any) of the result are filled with bit(x, p-1).
p has a default value. When ommited, all width(x) bits of x are used in the result.
Explicit conversions
char make_char(Int<n,s> x)
char make_char(int x)
int make_int(Int<n,s> x)
int make_int(int x)
long make_long(Int<n,s> x)
long make_long(int x)
Preconditions:
-(2width(result)-1) <= x < 2width(result)-1
This group of functions performs explicit conversion between different integer types, sign-extending signed x and zero-extending unsigned x.
These functions never discards data: if necessary, the argument must be truncated using zero_extend before converting.