Unsigned Integers
Last updated
Last updated
Unsigned integers are very much like , except that they have fixed bit widths.
You can think of an unsigned integer of bit width w like an array of w Booleans. We can use these bits to represent numbers ranging from 0 to 2^w.
An unsigned integer of bit width w would have type UInt w. This w is a .
To annotate type-level natural numbers with literals in your code, you'll need to enable the extension like this at the top of your file:
This section describes ways to construct unsigned integers.
Note that the bits are arranged in little-endian fashion, meaning that the least significant bit has index 0.
Unsigned integers are constructed with the following constructor under the hood:
Another way of acquiring an unsigned integer is from inputs:
A numeric literal represents the application of the function fromInteger to the appropriate value of type Integer.
The toField statement converts an unsigned integer to a Field.
Bits outside the width of the underlying field will be discarded. For example, If the width of the underlying field is w, the the resulting value of the Field with be the value of the unsigned integer modulo 2^w.
Example usage:
The fromField statement converts a Field to an unsigned integer. The value of the first argument needs to the same as the width of the resulting unsigned integer. Bits outside the width of the unsigned integer will be discarded.
Example usage:
The fromBools statement converts a list of Boolean values to a unsigned integer, ordered from the least significant bit to the most significant bit.
When the length of the list is less than the width of the unsigned integer, the remaining bits are filled with false. When the length of the list is greater than the width of the unsigned integer, the extra bits are discarded.
Example usage:
Example usage: 3 + 4
Example usage: 3 - 4
Example usage: 3 * 4
This function takes two UInt w and produces a slightly longer UInt (w + 1) that comes with the carry bit resulted from the addition.
Example usage:
This is the most general form of addition, allowing you to sum a batch of unsigned integers and decide how many carry bits you want to preserve or discard. The result will be zero-extended if it is longer than expected, and truncated if it is shorter than actually produced.
Example usage:
This function takes two UInt w operands and produces a UInt (w * 2) of double length, preserving all carry bits from the multiplication.
Example usage:
Like addV, this is the most general form of multplication, allowing you to multiply two unsigned integers and decide how many carry bits you want to preserve or discard. The result will be zero-extended if it is longer than expected, and truncated if it is shorter than actually produced.
Example usage:
Carry-less multiplication (also known as XOR multiplication) is similar to schoolbook long multiplication except that all carry numbers are discarded along the way.
This operator allows us to simulate multiplication of binary fields on prime fields. It's useful for implementing cryptographic primitives like the AES cipher.
Example usage: 3 .*. 4
divU x y takes two unsigned integers, with x as the dividend and y as the divisor, and returns the quotient of x and y.
Example usage: 3 `divU` 4
modU x y takes two unsigned integers, with x as the dividend and y as the divisor, and returns the modulo of x and y.
Example usage: 3 `modU` 4
performDivMod x y takes two unsigned integers, with x as the dividend and y as the divisor, and returns a pair of unsigned integers, with the first one being the quotient and the second being the remainder.
Instead of computing the quotient and remainder from the dividend and divisor, we can actually treat any of them as either input or output because division with remainder is more of a relation than a computation in Keelung.
For instance, we can both enforce the dividend to be an even number and obtain the quotient at the same time, as shown below:
Here are the carry-less counterparts of performDivMod and assertCLDivMod:
This operator computes the modular multiplicative inverse of a UInt with regard to some prime constant Integer.
Example usage: modInv 123 2833
Example usage: x .&. 3
Example usage: 42 .|. x
Example usage: y .^. x
Example usage: complement x
rotate x i Rotates the bits of an unsigned integer x to the left by i bits is i is positive, or to the right by -i bits otherwise. During the rotation, the bit value at index n will be shifted to index n + i mod w, where w is the bit width of the unsigned integer.
These three functions are synonyms of each other. They behave like rotate, except that the vacated bits on the right are filled with zeroes (false).
These functions work like left shift, but in the opposite direction.
Bit test is a function that allows you to inspect the bit values in an unsigned integer.
Bits are packed in little-endian order, with the least significant bit having the smallest index and the most significant bit having the largest index.
If the index specified is larger than the bit width w of an unsigned integer or is smaller than zero, the index will be "wrapped" by performing a modulo operation. This allows you to access bits outside the normal range of indices and can be useful in certain situations.
setBit takes an unsigned integer UInt w and returns a new UInt w with the bit at the specified index set to the provided Boolean value.
If the index specified in the setBit function is out of range, it will wrap around to a valid index by taking the remainder of the index divided by the bit width w.
slice takes an unsigned integer UInt w, along with a range, and returns a slice UInt v of that integer. The range is inclusive at the start and exclusive at the end. For instance, if x :: UInt 8, then slice x (2, 4) would return a UInt 2 representing the 3rd and 4th bits of x.
The type of the resulting integer has to be declared explicitly. Here's an example program:
Runtime exceptions are thrown under the following conditions:
The starting index is negative.
The ending index is less than the starting index.
The ending index exceeds the width of the UInt.
The expected width (as specified in the type) does not match the actual width derived from the range.
The join function concatenates two unsigned integers, UInt u and UInt v, producing a new unsigned integer UInt (u + v). This function effectively combines the bit representations of the two input unsigned integers into a single unsigned integer whose width is the sum of the widths of the two inputs.
For example:
Example usage: 3 `eq` 4 or eq 1 2.
neq is implemented as such under the hood:
This series of predicates allows you to make comparisons between two unsigned integers and determine which one is larger or smaller.
For example, we can define a function that takes an unsigned integer as public input and see if it's greater than 42:
Unsigned integers implement the typeclass, making it possible to construct an instance using literals.
@32 in the above example is a on inputUInt, which has type:
See .
Since UInt w is an instance of , all methods of Num works on unsigned integers.
Note that because performDivMod is a , it can only be executed in the Comp context , as shown in the example below:
Returns when two unsigned integers are the same:
Returns when two Booleans are the same:
Rather than computing the result of the comparison, we can also turn it into an assertion by passing the result to the statement. Assertions are typically less costly than computations in terms of the number of constraints generated.