stdlib.bits

Bit-Level Utilities

Generated from v0.60.1. 7 source files, 102 documented symbols.

bitarray.xi

type BitArray

Dynamic array of bits backed by a byte vector. Bit i lives in byte i/8 at bit position 7-(i%8) (MSB-first within each byte), so bit_array_to_bytes yields conventional packed bytes. Out-of-range indices are no-ops / false (never trap). Binary ops yield a result with max(len) bits; missing bits in the shorter operand read as 0.

Field	Type
bits	Vec[UInt8]
len	Int

fn bit_array_new(n: Int) -> BitArray

BitArray of length n (n < 0 is clamped to 0), all bits cleared. Complexity: O(n/8).

fn bit_array_set(ba: &mut BitArray, i: Int)

Sets bit i to 1. Out-of-range indices are ignored. Complexity: O(1).

fn bit_array_clear(ba: &mut BitArray, i: Int)

Clears bit i to 0. Out-of-range indices are ignored. Complexity: O(1).

fn bit_array_test(ba: BitArray, i: Int) -> Bool

True iff bit i is set. Out-of-range indices yield false. Complexity: O(1).

fn bit_array_flip(ba: &mut BitArray, i: Int)

Toggles bit i (0 -> 1, 1 -> 0). Out-of-range indices are ignored. Complexity: O(1).

fn bit_array_count(ba: BitArray) -> Int

Number of set bits. Complexity: O(n).

• Postcondition: result >= 0

fn bit_array_len(ba: BitArray) -> Int

Number of bits. Complexity: O(1).

• Postcondition: result >= 0

fn bit_array_and(a: BitArray, b: BitArray) -> BitArray

Bitwise AND of two bit arrays; the result has max(a.len, b.len) bits and missing bits read as 0. Complexity: O(max/8).

fn bit_array_or(a: BitArray, b: BitArray) -> BitArray

Bitwise OR of two bit arrays; the result has max(a.len, b.len) bits. Complexity: O(max/8).

fn bit_array_xor(a: BitArray, b: BitArray) -> BitArray

Bitwise XOR of two bit arrays; the result has max(a.len, b.len) bits and missing bits read as 0. Complexity: O(max/8).

fn bit_array_not(ba: BitArray) -> BitArray

Bitwise complement over ba.len bits; trailing bits beyond len in the last byte are cleared. Complexity: O(n/8).

fn bit_array_to_bytes(ba: BitArray) -> Vec[UInt8]

Packed byte representation, MSB-first within each byte (bit i of the array is bit 7-(i%8) of byte i/8). Complexity: O(n/8).

---

---

---

bitfield.xi

fn bitfield_get(value: Int, offset: Int, width: Int) -> Int

Extracts width bits at offset as an unsigned, right-justified value. Out-of-range requests are clamped: width <= 0 yields 0; the field is truncated at bit 63. Complexity: O(width).

• Postcondition: result >= 0

fn bitfield_set(value: Int, offset: Int, width: Int, val: Int) -> Int

Inserts val (masked to the field width) into the field at offset, leaving all other bits unchanged. The field is truncated at bit 63. Complexity: O(width).

fn bitfield_clear(value: Int, offset: Int, width: Int) -> Int

Zeros the width bits at offset, leaving all other bits unchanged. Complexity: O(width).

fn bitfield_sign_extend(value: Int, width: Int) -> Int

Sign-extends a width-bit value: bit width-1 is replicated into all higher bit positions. width <= 0 yields 0; width >= 64 returns value unchanged. Complexity: O(width).

fn bitfield_mask(width: Int) -> Int

Mask of width low bits set. width <= 0 yields 0; width >= 64 yields -1 (all 64 bits). Complexity: O(1).

• Postcondition: width >= 1 && width <= 63 => result >= 0

fn bitfield_extract_u(value: Int, offset: Int, width: Int) -> Int

Unsigned field extract, right-justified (alias of bitfield_get). Complexity: O(width).

• Postcondition: result >= 0

fn bitfield_insert(base: Int, value: Int, offset: Int, width: Int) -> Int

Places value into the field of base at offset (alias of bitfield_set with the arguments in insertion order). Complexity: O(width).

---

---

---

bits.xi

fn bit_get(n: Int, pos: Int) -> Int

bit_get -- Returns 1 if the bit at position pos (0 = LSB) is set, 0 otherwise. Position must be in [0, 63] for 64-bit Int.

• Postcondition: result == 0 || result == 1

fn bit_set(n: Int, pos: Int) -> Int

bit_set -- Returns n with the bit at position pos set to 1.

fn bit_clear(n: Int, pos: Int) -> Int

bit_clear -- Returns n with the bit at position pos cleared (set to 0).

fn bit_toggle(n: Int, pos: Int) -> Int

bit_toggle -- Flips the bit at position pos: 0->1, 1->0.

fn bit_count_ones(n: Int) -> Int

bit_count_ones (popcount) -- Counts set bits (1s) in n. Delegates to xiom.num.count_ones for the canonical implementation.

• Postcondition: result >= 0 && result <= 64

fn bit_count_zeros(n: Int) -> Int

bit_count_zeros -- Counts cleared bits (0s) in n.

• Postcondition: result >= 0 && result <= 64

fn popcount(n: Int) -> Int

popcount -- Alias for bit_count_ones. Hamming weight of the value. Delegates to the built-in counting function.

• Postcondition: result >= 0 && result <= 64

fn clz(n: Int) -> Int

clz -- Count Leading Zeros. Returns the number of consecutive zero bits starting from the most significant bit.

• Postcondition: result >= 0 && result <= 64

fn ctz(n: Int) -> Int

ctz -- Count Trailing Zeros. Returns the number of consecutive zero bits starting from the least significant bit.

• Postcondition: result >= 0 && result <= 64

fn rot_left(n: Int, k: Int) -> Int

rot_left -- Circularly shifts bits left by k positions. Bits shifted off the MSB reappear at the LSB. Equivalent to xiom.num.rotate_left.

fn rot_right(n: Int, k: Int) -> Int

rot_right -- Circularly shifts bits right by k positions. Bits shifted off the LSB reappear at the MSB. Equivalent to xiom.num.rotate_right.

fn bit_reverse(n: Int) -> Int

bit_reverse -- Reverses the order of bits in n (mirror). LSB becomes MSB and vice versa.

fn byte_swap16(v: Int) -> Int

byte_swap16 -- Swaps the two bytes of a 16-bit value (stored in lower 16 bits of an Int). Returns the byte-swapped result.

fn byte_swap32(v: Int) -> Int

byte_swap32 -- Swaps all four bytes of a 32-bit value (stored in lower 32 bits of an Int). Returns the byte-swapped result.

fn byte_swap64(v: Int) -> Int

byte_swap64 -- Swaps all eight bytes of a 64-bit value. Returns the fully byte-reversed Int.

fn get_bit_range(n: Int, start: Int, len: Int) -> Int

get_bit_range -- Extracts a contiguous range of bits from n as an unsigned value. start is the LSB position of the range, len is the number of bits. Returns the extracted value right-justified. Example: get_bit_range(0b110101, 0, 3) -> 0b101 (bits 0-2)

fn set_bit_range(n: Int, start: Int, len: Int, value: Int) -> Int

set_bit_range -- Sets a contiguous range of bits in n to the given value. start is the LSB position, len is the bit width. value is right-justified (lower bits only). Returns the modified Int.

fn is_pow2(n: Int) -> Bool

is_pow2 -- Returns true if n > 0 and n is a power of two. Uses the classic bit trick: powers of two have exactly one set bit, so n & (n-1) == 0. NOTE: xiom.num also provides is_power_of_two with identical behavior.

fn low_nibble(n: Int) -> Int

low_nibble -- Extracts the lower 4 bits (nibble) of n. Returns 0-15.

• Postcondition: result >= 0 && result <= 15

fn high_nibble(n: Int) -> Int

high_nibble -- Extracts bits 4-7 (the high nibble of the low byte). Returns 0-15.

• Postcondition: result >= 0 && result <= 15

fn pack_u16_le(low_byte: Int, high_byte: Int) -> Int

pack_u16_le -- Packs two byte values (0-255) into a 16-bit integer in little-endian order: low_byte at bits 0-7, high_byte at bits 8-15.

fn pack_u16_be(high_byte: Int, low_byte: Int) -> Int

pack_u16_be -- Packs two byte values into a 16-bit integer in big-endian order: high_byte at bits 0-7, low_byte at bits 8-15.

fn pack_u32_le(b0: Int, b1: Int, b2: Int, b3: Int) -> Int

pack_u32_le -- Packs four byte values (0-255) into a 32-bit integer in little-endian order: b0 at bits 0-7, b1 at 8-15, b2 at 16-23, b3 at 24-31.

fn pack_u32_be(b0: Int, b1: Int, b2: Int, b3: Int) -> Int

pack_u32_be -- Packs four byte values into a 32-bit integer in big-endian order: b0 at bits 24-31, ... , b3 at bits 0-7.

fn unpack_u16_le(value: Int) -> (Int, Int)

unpack_u16_le -- Unpacks a little-endian 16-bit value into (low_byte, high_byte).

• Postcondition: result._0 >= 0 && result._0 <= 255 && result._1 >= 0 && result._1 <= 255

fn unpack_u16_be(value: Int) -> (Int, Int)

unpack_u16_be -- Unpacks a big-endian 16-bit value into (high_byte, low_byte).

• Postcondition: result._0 >= 0 && result._0 <= 255 && result._1 >= 0 && result._1 <= 255

fn unpack_u32_le(value: Int) -> (Int, Int, Int, Int)

unpack_u32_le -- Unpacks a little-endian 32-bit value into a 4-tuple of bytes (b0=LSB .. b3=MSB).

• Postcondition: result._0 >= 0 && result._0 <= 255 && result._1 >= 0 && result._1 <= 255 && result._2 >= 0 && result._2 <= 255 && result._3 >= 0 && result._3 <= 255

fn unpack_u32_be(value: Int) -> (Int, Int, Int, Int)

unpack_u32_be -- Unpacks a big-endian 32-bit value into a 4-tuple of bytes (b0=MSB .. b3=LSB).

• Postcondition: result._0 >= 0 && result._0 <= 255 && result._1 >= 0 && result._1 <= 255 && result._2 >= 0 && result._2 <= 255 && result._3 >= 0 && result._3 <= 255

---

---

bitwise.xi

fn popcnt(n: Int) -> Int

Population count: number of set bits in n. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn clz(n: Int) -> Int

Count of consecutive zero bits starting from the most significant bit; 64 for zero. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn ctz(n: Int) -> Int

Count of consecutive zero bits starting from the least significant bit; 64 for zero. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn bit_reverse(n: Int) -> Int

Reverses the bit order of n (bit 0 <-> bit 63). Complexity: O(64).

fn bit_reverse_byte(b_in: Int) -> Int

Reverses the bit order of a single byte (low 8 bits of the input). Complexity: O(8).

fn byte_swap(v: Int) -> Int

Reverses the byte order of v (byte 0 <-> byte 7). Complexity: O(8).

fn rotate_left(n: Int, k: Int) -> Int

Circular left shift by k bits (the shift amount is reduced mod 64). Complexity: O(1).

fn rotate_right(n: Int, k: Int) -> Int

Circular right shift by k bits (the shift amount is reduced mod 64). Complexity: O(1).

fn bit_width(n: Int) -> Int

Number of bits needed to represent n: 0 for zero, 64 for negative values (the sign bit is counted), otherwise floor(log2 n) + 1. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn bit_length(n: Int) -> Int

Alias of bit_width. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn leading_ones(n: Int) -> Int

Count of consecutive 1 bits starting from the most significant bit. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn trailing_ones(n: Int) -> Int

Count of consecutive 1 bits starting from the least significant bit. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn bit_parity(n: Int) -> Int

1 if the population count is odd, else 0. Complexity: O(64).

• Postcondition: result == 0 || result == 1

fn bit_scan_forward(n: Int) -> Int

Index of the lowest set bit; -1 when n == 0. Complexity: O(64).

• Postcondition: result >= -1 && result <= 63

fn bit_scan_reverse(n: Int) -> Int

Index of the highest set bit; -1 when n == 0. Complexity: O(64).

• Postcondition: result >= -1 && result <= 63

fn is_power_of_two_bit(n: Int) -> Bool

True iff n > 0 and n is a power of two (exactly one set bit). Complexity: O(64).

---

---

---

endianness.xi

fn is_big_endian() -> Bool

True if the host stores integers big-endian. The supported targets are little-endian, so this returns false. Complexity: O(1).

fn is_little_endian() -> Bool

True if the host stores integers little-endian. The supported targets are little-endian, so this returns true. Complexity: O(1).

fn to_be(v: Int, size: Int) -> Int

Converts v to big-endian byte order for a size-byte value (the low size bytes are reversed; higher bytes are cleared). Complexity: O(size).

fn to_le(v: Int, size: Int) -> Int

Converts v to little-endian byte order for a size-byte value. On the little-endian host this is the identity. Complexity: O(1).

fn from_be(v: Int, size: Int) -> Int

Decodes a size-byte big-endian value held in v into host order (the low size bytes are reversed). Complexity: O(size).

fn from_le(v: Int, size: Int) -> Int

Decodes a size-byte little-endian value held in v into host order (the identity on the little-endian host). Complexity: O(1).

fn native_to_be(v: Int) -> Int

Converts a native value to big-endian order (all 8 bytes reversed). Complexity: O(8).

fn native_to_le(v: Int) -> Int

Converts a native value to little-endian order (the identity on this host). Complexity: O(1).

fn be_to_native(v: Int) -> Int

Converts a big-endian value to native order (all 8 bytes reversed). Complexity: O(8).

fn le_to_native(v: Int) -> Int

Converts a little-endian value to native order (the identity on this host). Complexity: O(1).

fn swap_endian(v: Int) -> Int

Unconditionally reverses the byte order of v (all 8 bytes). Complexity: O(8).

fn bswap_16(v: Int) -> Int

Byte-swaps a 16-bit value stored in the low 16 bits of v. Complexity: O(2).

fn bswap_32(v: Int) -> Int

Byte-swaps a 32-bit value stored in the low 32 bits of v. Complexity: O(4).

fn bswap_64(v: Int) -> Int

Byte-swaps a 64-bit value. Complexity: O(8).

fn bswap_128(v: Int) -> Int

Byte-swaps a 128-bit value. FALLBACK (platform Int is 64-bit): identical to bswap_64. Complexity: O(8).

fn bswap_256(v: Int) -> Int

Byte-swaps a 256-bit value. FALLBACK (platform Int is 64-bit): identical to bswap_64. Complexity: O(8).

---

---

---

popcount.xi

fn popcount(n: Int) -> Int

Number of set bits in n. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn popcount64(n: UInt64) -> Int

Number of set bits in a UInt64 value. The low bit of an arithmetic shift is identical to a logical shift, so (n >> i) & 1 is exact. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn count_leading_zeros(n: Int) -> Int

Consecutive zero bits from the most significant bit; 64 for zero. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn count_trailing_zeros(n: Int) -> Int

Consecutive zero bits from the least significant bit; 64 for zero. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn count_ones(n: Int) -> Int

Number of set bits (alias of popcount). Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn count_zeros(n: Int) -> Int

Number of cleared bits (64 - popcount). Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn parity(n: Int) -> Int

1 if the population count is odd, else 0. Complexity: O(64).

• Postcondition: result == 0 || result == 1

fn bit_length(n: Int) -> Int

Number of bits needed to represent n: 0 for zero, 64 for negative values, otherwise floor(log2 n) + 1. Complexity: O(64).

• Postcondition: result >= 0 && result <= 64

fn next_pow2(n: Int) -> Int

Smallest power of two >= n. n <= 0 yields 1; values above 2^62 yield 0 (the next power of two would not fit an Int). Complexity: O(63).

fn prev_pow2(n: Int) -> Int

Largest power of two <= n. n <= 0 yields 0. Complexity: O(64).

fn rotate_left(n: Int, k: Int) -> Int

Circular left shift by k bits (the shift amount is reduced mod 64). Complexity: O(1).

fn rotate_right(n: Int, k: Int) -> Int

Circular right shift by k bits (the shift amount is reduced mod 64). Complexity: O(1).

---

---

---

rotation.xi

fn rotate_left(n: Int, k: Int) -> Int

Circular left rotation by k bits (the shift amount is reduced mod 64). Complexity: O(1).

fn rotate_right(n: Int, k: Int) -> Int

Circular right rotation by k bits (the shift amount is reduced mod 64). Complexity: O(1).

fn rotate_left_carry(n: Int, k: Int, carry_in: Int) -> (Int, Int)

Rotate-left-with-carry: performs k rotate-through-carry steps (each step moves bit 63 into the carry and shifts the carry into bit 0). Returns (rotated_value, new_carry). The shift amount is reduced mod 64. Complexity: O(k).

• Postcondition: result._1 == 0 || result._1 == 1

fn rotate_right_carry(n: Int, k: Int, carry_in: Int) -> (Int, Int)

Rotate-right-with-carry: performs k rotate-through-carry steps (each step moves bit 0 into the carry and shifts the carry into bit 63). Returns (rotated_value, new_carry). The shift amount is reduced mod 64. Complexity: O(k).

• Postcondition: result._1 == 0 || result._1 == 1

fn rol_imm(n: Int, k: Int) -> Int

Rotate left by a "compile-time constant" k (equivalent to rotate_left; the language has no distinct immediate form). Complexity: O(1).

fn ror_imm(n: Int, k: Int) -> Int

Rotate right by a "compile-time constant" k (equivalent to rotate_right). Complexity: O(1).

fn bit_rotate_left(n: Int, k: Int) -> Int

Alias of rotate_left. Complexity: O(1).

fn bit_rotate_right(n: Int, k: Int) -> Int

Alias of rotate_right. Complexity: O(1).

fn masked_rotate_left(n: Int, k: Int, mask: Int) -> Int

Rotates left only the bits selected by mask; the rotation happens within the span of the selected bit positions and unselected bits are unchanged. The shift amount is reduced mod (number of selected bits). Complexity: O(64 + popcount(mask)).

fn masked_rotate_right(n: Int, k: Int, mask: Int) -> Int

Rotates right only the bits selected by mask (inverse of masked_rotate_left). The shift amount is reduced mod (number of selected bits). Complexity: O(64 + popcount(mask)).

---

---

---