# # # Nim's Runtime Library # (c) Copyright 2017 Nim Authors # (c) Copyright 2019 Status Research # # See the file "copying.txt", included in this # distribution, for details about the copyright. # ## This module implements a series of low level methods for bit manipulation. ## By default, this module use compiler intrinsics to improve performance ## on supported compilers: ``GCC``, ``LLVM_GCC``, ``CLANG``, ``VCC``, ``ICC``. ## ## The module will fallback to pure nim procs incase the backend is not supported. ## You can also use the flag `noIntrinsicsBitOpts` to disable compiler intrinsics. ## ## This module is also compatible with other backends: ``Javascript``, ``Nimscript`` ## as well as the ``compiletime VM``. {.push raises: [].} import endians2 const useBuiltins = not defined(noIntrinsicsBitOpts) template bitsof*(T: typedesc[SomeInteger]): int = 8 * sizeof(T) template bitsof*(x: SomeInteger): int = 8 * sizeof(x) type BitIndexable = SomeUnsignedInt # #### Pure Nim version #### func nextPow2Nim(x: SomeUnsignedInt): SomeUnsignedInt = var v = x - 1 # round down, make sure all bits are 1 below the threshold, then add 1 v = v or v shr 1 v = v or v shr 2 v = v or v shr 4 when bitsof(x) > 8: v = v or v shr 8 when bitsof(x) > 16: v = v or v shr 16 when bitsof(x) > 32: v = v or v shr 32 v + 1 func firstOneNim(x: uint32): int = ## Returns the 1-based index of the least significant set bit of x, or if x is zero, returns zero. # https://graphics.stanford.edu/%7Eseander/bithacks.html#ZerosOnRightMultLookup const lookup = [0'u8, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9] if x == 0: 0 else: let k = not x + 1 # get two's complement cast[int](1 + lookup[((x and k) * 0x077CB531'u32) shr 27]) func firstOneNim(x: uint8|uint16): int = firstOneNim(x.uint32) func firstOneNim(x: uint64): int = ## Returns the 1-based index of the least significant set bit of x, or if x is zero, returns zero. # https://graphics.stanford.edu/%7Eseander/bithacks.html#ZerosOnRightMultLookup if (x and uint32.high) == 0: cast[int](32 + uint(firstOneNim(uint32(x shr 32'u32)))) else: firstOneNim(uint32(x)) func log2truncNim(x: uint8|uint16|uint32): int = ## Quickly find the log base 2 of a 32-bit or less integer. # https://graphics.stanford.edu/%7Eseander/bithacks.html#IntegerLogDeBruijn # https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers const lookup: array[32, uint8] = [0'u8, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31] var v = x.uint32 v = v or v shr 1 # first round down to one less than a power of 2 v = v or v shr 2 v = v or v shr 4 v = v or v shr 8 v = v or v shr 16 cast[int](lookup[uint32(v * 0x07C4ACDD'u32) shr 27]) func log2truncNim(x: uint64): int = ## Quickly find the log base 2 of a 64-bit integer. # https://graphics.stanford.edu/%7Eseander/bithacks.html#IntegerLogDeBruijn # https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers const lookup: array[64, uint8] = [0'u8, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56, 45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63] var v = x v = v or v shr 1 # first round down to one less than a power of 2 v = v or v shr 2 v = v or v shr 4 v = v or v shr 8 v = v or v shr 16 v = v or v shr 32 cast[int](lookup[(v * 0x03F6EAF2CD271461'u64) shr 58]) func countOnesNim(x: uint8|uint16|uint32): int = ## Counts the set bits in integer. (also called Hamming weight.) # generic formula is from: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel var v = x.uint32 v = v - ((v shr 1) and 0x55555555) v = (v and 0x33333333) + ((v shr 2) and 0x33333333) cast[int](((v + (v shr 4) and 0xF0F0F0F) * 0x1010101) shr 24) func countOnesNim(x: uint64): int = ## Counts the set bits in integer. (also called Hamming weight.) # generic formula is from: https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel var v = x v = v - ((v shr 1'u64) and 0x5555555555555555'u64) v = (v and 0x3333333333333333'u64) + ((v shr 2'u64) and 0x3333333333333333'u64) v = (v + (v shr 4'u64) and 0x0F0F0F0F0F0F0F0F'u64) cast[int]((v * 0x0101010101010101'u64) shr 56'u64) func parityNim(x: SomeUnsignedInt): int = # formula id from: https://graphics.stanford.edu/%7Eseander/bithacks.html#ParityParallel var v = x when sizeof(v) == 8: v = v xor (v shr 32) when sizeof(v) >= 4: v = v xor (v shr 16) when sizeof(v) >= 2: v = v xor (v shr 8) v = v xor (v shr 4) v = v and 0xf cast[int]((0x6996'u shr v) and 1) when (defined(gcc) or defined(llvm_gcc) or defined(clang)) and useBuiltins: # Returns the number of set 1-bits in value. func builtin_popcount(x: cuint): cint {.importc: "__builtin_popcount", nodecl.} func builtin_popcountll(x: culonglong): cint {.importc: "__builtin_popcountll", nodecl.} # Returns the bit parity in value func builtin_parity(x: cuint): cint {.importc: "__builtin_parity", nodecl.} func builtin_parityll(x: culonglong): cint {.importc: "__builtin_parityll", nodecl.} # Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero. func builtin_ffs(x: cint): cint {.importc: "__builtin_ffs", nodecl.} func builtin_ffsll(x: clonglong): cint {.importc: "__builtin_ffsll", nodecl.} # Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. func builtin_clz(x: cuint): cint {.importc: "__builtin_clz", nodecl.} func builtin_clzll(x: culonglong): cint {.importc: "__builtin_clzll", nodecl.} func countOnesBuiltin(x: SomeUnsignedInt): int = when bitsof(x) == bitsof(culonglong): cast[int](builtin_popcountll(x.culonglong)) else: cast[int](builtin_popcount(x.cuint)) func parityBuiltin(x: SomeUnsignedInt): int = when bitsof(x) == bitsof(culonglong): cast[int](builtin_parityll(x.culonglong)) else: cast[int](builtin_parity(x.cuint)) func firstOneBuiltin(x: SomeUnsignedInt): int = when bitsof(x) == bitsof(clonglong): cast[int](builtin_ffsll(cast[clonglong](x))) else: cast[int](builtin_ffs(cast[cint](x.cuint))) func log2truncBuiltin(v: uint8|uint16|uint32): int = cast[int](31 - cast[cuint](builtin_clz(v.uint32))) func log2truncBuiltin(v: uint64): int = cast[int](63 - cast[cuint](builtin_clzll(v))) elif defined(vcc) and useBuiltins: const arch64 = sizeof(int) == 8 # Counts the number of one bits (population count) in a 16-, 32-, or 64-byte unsigned integer. func builtin_popcnt16(a2: uint16): uint16 {.importc: "__popcnt16" header: "".} func builtin_popcnt32(a2: uint32): uint32 {.importc: "__popcnt" header: "".} # Search the mask data from most significant bit (MSB) to least significant bit (LSB) for a set bit (1). func bitScanReverse(index: ptr culong, mask: culong): cuchar {.importc: "_BitScanReverse", header: "".} # Search the mask data from least significant bit (LSB) to the most significant bit (MSB) for a set bit (1). func bitScanForward(index: ptr culong, mask: culong): cuchar {.importc: "_BitScanForward", header: "".} when arch64: func builtin_popcnt64(a2: uint64): uint64 {.importc: "__popcnt64" header: "".} func bitScanReverse64(index: ptr culong, mask: uint64): cuchar {.importc: "_BitScanReverse64", header: "".} func bitScanForward64(index: ptr culong, mask: uint64): cuchar {.importc: "_BitScanForward64", header: "".} func countOnesBuiltin(v: uint8|uint16): int = cast[int](builtin_popcnt16(v.uint16)) func countOnesBuiltin(v: uint32): int = cast[int](builtin_popcnt32(v)) func countOnesBuiltin(v: uint64): int = when arch64: cast[int](builtin_popcnt64(v)) else: cast[int]( builtin_popcnt32((v and uint32.high).uint32) + builtin_popcnt32((v shr 32'u64).uint32)) template checkedScan(fnc: untyped, x: typed, def: typed): int = var index{.noinit.}: culong if fnc(index.addr, v) == cuchar(0): def else: cast[int](index) func firstOneBuiltin(v: uint8|uint16|uint32): int = 1 + checkedScan(bitScanForward, v.culong, -1) func firstOneBuiltin(v: uint64): int = when arch64: 1 + checkedScan(bitScanForward64, v.culonglong, -1) else: firstOneNim(v) template bitScan(fnc: untyped, x: typed): int = var index{.noinit.}: culong if fnc(index.addr, v) == cuchar(0): 0 else: cast[int](index) func log2truncBuiltin(v: uint8|uint16|uint32): int = bitScan(bitScanReverse, v.culong) func log2truncBuiltin(v: uint64): int = when arch64: bitScan(bitScanReverse64, v.culong) else: log2truncNim(v) elif defined(icc) and useBuiltins: const arch64 = sizeof(int) == 8 # Intel compiler intrinsics: http://fulla.fnal.gov/intel/compiler_c/main_cls/intref_cls/common/intref_allia_misc.htm # see also: https://software.intel.com/en-us/node/523362 # Count the number of bits set to 1 in an integer a, and return that count in dst. func builtin_popcnt32(x: cint): cint {.importc: "_popcnt32" header: "".} # Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. func bitScanForward(p: ptr uint32, b: uint32): cuchar {.importc: "_BitScanForward", header: "".} # Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. func bitScanReverse(p: ptr uint32, b: uint32): cuchar {.importc: "_BitScanReverse", header: "".} when arch64: func builtin_popcnt64(x: uint64): cint {.importc: "_popcnt64" header: "".} func bitScanForward64(p: ptr uint32, b: uint64): cuchar {.importc: "_BitScanForward64", header: "".} func bitScanReverse64(p: ptr uint32, b: uint64): cuchar {.importc: "_BitScanReverse64", header: "".} template checkedScan(fnc: untyped, x: typed, def: typed): int = var index{.noinit.}: culong if fnc(index.addr, v) == cuchar(0): def else: cast[int](index) template bitScan(fnc: untyped, x: typed): int = var index{.noinit.}: culong if fnc(index.addr, v) == cuchar(0): 0 else: cast[int](index) func countOnesBuiltin(v: uint8|uint16|uint32): int = cast[int](builtin_popcnt32(cast[cint](v))) func countOnesBuiltin(v: uint64): int = when arch64: cast[int](builtin_popcnt64(v)) else: cast[int]( builtin_popcnt32(cast[cint](v and 0xFFFFFFFF'u64)) + builtin_popcnt32(cast[cint](v shr 32'u64))) func firstOneBuiltin(v: uint8|uint16|uint32): int = 1 + checkedScan(bitScanForward, v.culong, -1) func firstOneBuiltin(v: uint64): int = when arch64: 1 + checkedScan(bitScanForward64, v.culong, -1) else: firstOneNim(v) func log2truncBuiltin(v: uint8|uint16|uint32): int = bitScan(bitScanReverse, v.culong) func log2truncBuiltin(v: uint64): int = when arch64: bitScan(bitScanReverse64, v.culong) else: log2truncNim(v) func countOnes*(x: SomeUnsignedInt): int {.inline.} = ## Counts the set bits in integer. (also called `Hamming weight`:idx:.) ## ## Example: ## doAssert countOnes(0b01000100'u8) == 2 when nimvm: countOnesNim(x) else: when declared(countOnesBuiltin): countOnesBuiltin(x) else: countOnesNim(x) func countZeros*(x: SomeUnsignedInt): int {.inline.} = bitsof(x) - countOnes(x) func parity*(x: SomeUnsignedInt): int {.inline.} = ## Calculate the bit parity in integer. If number of 1-bit ## is odd parity is 1, otherwise 0. ## ## Example: ## doAssert parity(0b00000001'u8) == 1 # Can be used a base if creating ASM version. # https://stackoverflow.com/questions/21617970/how-to-check-if-value-has-even-parity-of-bits-or-odd when nimvm: parityNim(x) else: when declared(parityBuiltin): parityBuiltin(x) else: parityNim(x) func firstOne*(x: SomeUnsignedInt): int {.inline.} = ## Returns the 1-based index of the least significant set bit of x. ## If `x` is zero result is 0 ## ## firstOne(x) == trailingZeros(x) + 1 ## ## Example: ## doAssert firstOneBit(0b00000010'u8) == 2 ## when nimvm: firstOneNim(x) else: when declared(firstOneBuiltin): firstOneBuiltin(x) else: firstOneNim(x) func log2trunc*(x: SomeUnsignedInt): int {.inline.} = ## Return the truncated base 2 logarithm of `x` - this is the zero-based ## index of the last set bit. ## ## If `x` is zero result is -1 ## ## log2trunc(x) == bitsof(x) - leadingZeros(x) - 1. ## ## Example: ## doAssert log2trunc(0b01001000'u8) == 6 if x == 0: -1 else: when nimvm: log2truncNim(x) else: when declared(log2truncBuiltin): log2truncBuiltin(x) else: log2truncNim(x) template bitWidth*(x: SomeUnsignedInt): int = ## Returns the number of bits needed to write down the ## number `x` in binary. If `x` is zero, the result is 0. log2trunc(x) + 1 func leadingZeros*(x: SomeInteger): int {.inline.} = ## Returns the number of leading zero bits in integer. ## If `x` is zero, result is bitsof(x) ## ## Example: ## doAssert leadingZeros(0b00000000'u8) == 8 ## doAssert leadingZeros(0b00100000'u8) == 2 ## # Performance note: # On recent x86_64 cpu's, this translates to the LZCNT instruction bitsof(x) - 1 - log2trunc(x) func trailingZeros*(x: SomeUnsignedInt): int {.inline.} = ## Returns the number of trailing zeros in integer. ## If `x` is zero, result is sizeof(x) * 8 ## ## Example: ## doAssert trailingZeros(0b00000010'u8) == 1 ## # Performance note: # On recent x86_64 cpu's, this translates to the TZCNT instruction if x == 0: bitsof(x) else: firstOne(x) - 1 func nextPow2*(x: SomeUnsignedInt): SomeUnsignedInt {.inline.} = ## Calculate the next power-of-2 of x - wraps to 0 ## ## Examples: ## doAssert nextPow2(3) == 4 ## doAssert nextPow2(4) == 4 nextPow2Nim(x) func rotateLeft*(v: SomeUnsignedInt, amount: SomeInteger): SomeUnsignedInt {.inline.} = ## Left-rotate bits in an unsigned value # using this form instead of the one below should handle any value # out of range as well as negative values. # taken from: https://en.wikipedia.org/wiki/Circular_shift#Implementing_circular_shifts const mask = 8 * sizeof(v) - 1 let amount = int(amount and mask) (v shl amount) or (v shr ( (-amount) and mask)) func rotateRight*(v: SomeUnsignedInt, amount: SomeInteger): SomeUnsignedInt {.inline.} = ## Right-rotate bits in an unsigned value. const mask = bitsof(v) - 1 let amount = int(amount and mask) (v shr amount) or (v shl ( (-amount) and mask)) template mostSignificantBit(T: type): auto = const res = 1 shl (sizeof(T) * 8 - 1) T(res) template getBit*(x: BitIndexable, bit: Natural): bool = ## reads a bit from `x`, assuming 0 to be the position of the ## least significant bit type T = type(x) ((x shr bit) and T(1)) != 0 template getBitLE*(x: BitIndexable, bit: Natural): bool = getBit(x, bit) template getBitBE*(x: BitIndexable, bit: Natural): bool = ## Reads a bit from `x`, assuming 0 to be the position of ## the most significant bit. ## ## This indexing may be natural when you are considering the ## string representation of a bit field. For example, 72 can ## be written in binary as 0b01001000. The first bit here is ## zero, while the second bit is one. ## ## Since the string representation will depend on the size of ## the operand, using `getBitBE` with the same numeric value ## and a bit position may produce different results depending ## on the machine type used to store the value. For this reason, ## this indexing scheme is considered more error-prone and ## `getBitLE` is considering the default indexing scheme. (x and mostSignificantBit(x.type) shr bit) != 0 func changeBit*(x: var BitIndexable, bit: Natural, val: bool) {.inline.} = ## changes a bit in `x` to val, assuming 0 to be the position of the ## least significant bit type T = type(x) x = (x and not (T(1) shl bit)) or (T(val) shl bit) template changeBitLE*(x: var BitIndexable, bit: Natural, val: bool) = setBit(x, bit, val) func changeBitBE*(x: var BitIndexable, bit: Natural, val: bool) {.inline.} = ## changes a bit in `x` to val, assuming 0 to be the position of the ## most significant bit changeBit(x, bitsof(x) - 1 - bit, val) func setBit*(x: var BitIndexable, bit: Natural) {.inline.} = ## sets bit in `x`, assuming 0 to be the position of the ## least significant bit type T = type(x) let mask = T(1) shl bit x = x or mask template setBitLE*(x: var BitIndexable, bit: Natural) = setBit(x, bit) func setBitBE*(x: var BitIndexable, bit: Natural) {.inline.} = ## sets a bit in `x`, assuming 0 to be the position of the ## most significant bit let mask = mostSignificantBit(x.type) shr bit x = x or mask func clearBit*(x: var BitIndexable, bit: Natural) {.inline.} = ## clears bit in a byte, assuming 0 to be the position of the ## least significant bit type T = type(x) let mask = T(1) shl bit x = x and not mask template clearBitLE*(x: var BitIndexable, bit: Natural) = clearBit(x, bit) func clearBitBE*(x: var BitIndexable, bit: Natural) {.inline.} = ## clears a bit in `x`, assuming 0 to be the position of the ## most significant bit let mask = mostSignificantBit(x.type) shr bit x = x and not mask func toggleBit*(x: var BitIndexable, bit: Natural) {.inline.} = ## toggles (inverts) bit in `x`, assuming 0 to be the position of the ## least significant bit type T = type(x) let mask = T(1) shl bit x = x xor mask template toggleBitLE*(x: var BitIndexable, bit: Natural) = toggleBit(x, bit) func toggleBitBE*(x: var BitIndexable, bit: Natural) {.inline.} = ## toggles (inverts) a bit in `x`, assuming 0 to be the position of the ## most significant bit let mask = mostSignificantBit(x.type) shr bit x = x xor mask template byteIndex(pos: Natural): int = pos shr 3 # same as pos div 8 template bitIndex(pos: Natural): int = pos and 0b111 # same as pos mod 8 func getBit*(bytes: openarray[byte], pos: Natural): bool {.inline.} = getBit(bytes[byteIndex pos], bitIndex pos) template getBitLE*(bytes: openarray[byte], pos: Natural): bool = getBit(bytes, pos) func getBitBE*(bytes: openarray[byte], pos: Natural): bool {.inline.} = getBitBE(bytes[byteIndex pos], bitIndex pos) func changeBit*(bytes: var openarray[byte], pos: Natural, value: bool) {.inline.} = changeBit(bytes[byteIndex pos], bitIndex pos, value) template changeBitLE*(bytes: var openarray[byte], pos: Natural, value: bool) = changeBit(bytes, pos, value) func changeBitBE*(bytes: var openarray[byte], pos: Natural, value: bool) {.inline.} = changeBitBE(bytes[byteIndex pos], bitIndex pos, value) func setBit*(bytes: var openarray[byte], pos: Natural) {.inline.} = setBit(bytes[byteIndex pos], bitIndex pos) template setBitLE*(bytes: var openarray[byte], pos: Natural) = setBit(bytes, pos) func setBitBE*(bytes: var openarray[byte], pos: Natural) {.inline.} = setBitBE(bytes[byteIndex pos], bitIndex pos) func clearBit*(bytes: var openarray[byte], pos: Natural) {.inline.} = clearBit(bytes[byteIndex pos], bitIndex pos) template clearBitLE*(bytes: var openarray[byte], pos: Natural) = clearBit(bytes, pos) func clearBitBE*(bytes: var openarray[byte], pos: Natural) {.inline.} = clearBitBE(bytes[byteIndex pos], bitIndex pos) func toggleBit*(bytes: var openarray[byte], pos: Natural) {.inline.} = toggleBit(bytes[byteIndex pos], bitIndex pos) template toggleBitLE*(bytes: var openarray[byte], pos: Natural) = toggleBit(bytes, pos) func toggleBitBE*(bytes: var openarray[byte], pos: Natural) {.inline.} = toggleBitBE(bytes[byteIndex pos], bitIndex pos) template setBit*(x: var BitIndexable, bit: Natural, val: bool) {.deprecated: "changeBit".} = changeBit(x, bit, val) template setBitLE*(x: var BitIndexable, bit: Natural, val: bool) {.deprecated: "changeBitLE".} = changeBitLE(x, bit, val) template setBitBE*(x: var BitIndexable, bit: Natural, val: bool) {.deprecated: "changeBitBE".} = changeBitBE(x, bit, val) template raiseBit*(x: var BitIndexable, bit: Natural) {.deprecated: "setBit".} = setBit(x, bit) template raiseBitLE*(x: var BitIndexable, bit: Natural) {.deprecated: "setBitLE".} = setBitLE(x, bit) template raiseBitBE*(x: var BitIndexable, bit: Natural) {.deprecated: "setBitBE".} = setBitBE(x, bit) func lowerBit*(x: var BitIndexable, bit: Natural) {.inline, deprecated: "clearBit".} = clearBit(x, bit) template lowerBitLE*(x: var BitIndexable, bit: Natural) {.deprecated: "clearBitLE".} = clearBit(x, bit) template lowerBitBE*(x: var BitIndexable, bit: Natural) {.deprecated: "clearBitBE".} = clearBitBE(x, bit) template setBit*(bytes: var openarray[byte], pos: Natural, val: bool) {.deprecated: "changeBit".} = changeBit(bytes, pos, val) template setBitLE*(bytes: var openarray[byte], pos: Natural, val: bool) {.deprecated: "changeBitLE".} = changeBitLE(bytes, pos, val) template setBitBE*(bytes: var openarray[byte], pos: Natural, val: bool) {.deprecated: "changeBitBE".} = changeBitBE(bytes, pos, val) template raiseBit*(bytes: var openarray[byte], pos: Natural) {.deprecated: "setBit".} = setBit(bytes, pos) template raiseBitLE*(bytes: var openarray[byte], pos: Natural) {.deprecated: "setBitLE".} = setBitLE(bytes, pos) template raiseBitBE*(bytes: var openarray[byte], pos: Natural) {.deprecated: "setBitBE".} = setBitBE(bytes, pos) template lowerBit*(bytes: var openarray[byte], pos: Natural) {.deprecated: "clearBit".} = clearBit(bytes, pos) template lowerBitLE*(bytes: var openarray[byte], pos: Natural) {.deprecated: "clearBitLE".} = clearBitLE(bytes, pos) template lowerBitBE*(bytes: var openarray[byte], pos: Natural) {.deprecated: "clearBitBE".} = clearBitBE(bytes, pos) func getBitsBE*(data: openarray[byte], slice: HSlice, T: type[SomeUnsignedInt]): T = ## Treats `data` as an unsigned big endian integer and returns a slice of bits ## extracted from it, assuming 0 to be the possition of the most significant bit. let totalBits = data.len * 8 template normalizeIdx(idx): int = when idx is BackwardsIndex: totalBits - int(idx) else: int(idx) let a = normalizeIdx(slice.a) b = normalizeIdx(slice.b) + 1 sliceLen = b - a const resultBits = sizeof(result) * 8 doAssert a < b and sliceLen <= resultBits and b <= totalBits let limbs = cast[ptr UncheckedArray[T]](unsafeAddr data[0]) template readLimb(idx: int): auto = when cpuEndian == bigEndian or sizeof(result) == 1: limbs[][idx] else: swapBytes(limbs[][idx]) let firstLimbIdx = a div resultBits firstLimbUnusedBits = (a mod resultBits) firstLimbUsedBits = resultBits - firstLimbUnusedBits firstLimb = readLimb firstLimbIdx if sliceLen > firstLimbUsedBits: let bitsFromSecondLimb = sliceLen - firstLimbUsedBits secondLimb = readLimb(firstLimbIdx + 1) ((firstLimb shl firstLimbUnusedBits) shr (firstLimbUnusedBits - bitsFromSecondLimb)) or (secondLimb shr (resultBits - bitsFromSecondLimb)) else: (firstLimb shl firstLimbUnusedBits) shr (resultBits - sliceLen) template getBitsBE*(data: openarray[byte], slice: HSlice): BiggestUInt = getBitsBE(data, slice, BiggestUInt)