repository·master·Indexed 21 days ago
https://github.com/ilanschnell/bitarrayA C-implemented Python library providing an efficient representation of boolean arrays. It supports high-performance bitwise operations, slicing, the Python buffer protocol for memory sharing, and canonical Huffman coding. The library includes support for both big-endian and little-endian representations and is compatible with free-threaded CPython 3.14+.
When using serialize(), the first byte of the resulting bytes object is a header byte used to reconstruct the bitarray.
x[0] % 16: The number of pad bits (0..7) within the last byte.x[0] // 16: The bit-endianness (0 for little-endian, 1 for big-endian).Valid header values are in the ranges 0 .. 7 or 16 .. 23. For an empty bitarray, the only valid header values are 0 or 16.
While bitarray is memory-safe during concurrent mutation, the results may be non-deterministic.
IndexError or ValueError (e.g., if an index or mask becomes invalid mid-operation).encode(), decode(), or decodetree(), the code dictionaries and their bitarray values are not snapshotted atomically. If you mutate the code dictionary concurrently, the operation may observe a mixture of states or raise an exception. Do not mutate code dictionaries while they are being used for encoding/decoding.The variable-length format is similar to LEB128 and is optimized for memory efficiency, especially for small bitarrays.
Encoding Structure:
1 indicates that more bytes follow, and 0 indicates the last byte of the sequence.Example Encoding Process for bitarray('01010110111001110'):
0101, 0110111, 001110).001110 becomes 0011100).1) is added to the front of the first group (e.g., 001 + 0101 = 0010101).1 for all bytes except the final one.0x95 0xb7 0x1c.from bitarray import bitarray
from bitarray.util import vl_encode
# Encoding a specific bitarray results in a self-terminating byte stream
encoded = vl_encode(bitarray('01010110111001110'))
# Output: b'\x95\xb7\x1c'The repository provides two distinct approaches for implementing sparse bitarrays, which are efficient when the bitarray contains mostly zeros or mostly ones.
flips.py): Represents the bitarray using a list of positions where a bit flips (changes from 0 to 1 or 1 to 0).ones.py): Represents the bitarray using a sorted list of the positions of all '1' bits, along with the total length of the array.Both implementations share common functionality defined in common.py.
Bit-endianness determines how bits within a byte are mapped to indices in a bitarray.
a[0] is the lowest address and the most significant bit.a[0] is the lowest address and the least significant bit.When to care about endianness:
|, ^, &=, |=, ^=, ~), bitarrays must have the same endianness..tobytes(), .frombytes(), .tofile(), .fromfile(), or memoryview().int2ba or ba2int.If you are only performing logical computations on indices, endianness is transparent and has no effect on the results.
from bitarray import bitarray
# Default is big-endian
a = bitarray(b'A')
print(a.endian) # 'big'
print(a) # bitarray('01000001')
# Explicit little-endian
b = bitarray(b'A', endian='little')
print(b.endian) # 'little'
print(b) # bitarray('10000010')To decode a bitarray into symbols, you can use a prefix code (a dictionary mapping symbols to bitarrays) or a decodetree object.
.decode().decodetree: For better performance, convert the dictionary into a decodetree object first using decodetree(code) and pass that to .decode()..decode() returns a decodeiterator which yields the decoded symbols.
import bitarray
# Define a prefix code
code = {
'A': bitarray.bitarray('0'),
'B': bitarray.bitarray('10'),
'C': bitarray.bitarray('11')
}
a = bitarray.bitarray('01011')
# Decode using the dictionary
for symbol in a.decode(code):
print(symbol)
# Optimized decoding with decodetree
tree = bitarray.decodetree(code)
for symbol in a.decode(tree):
print(symbol)The sparse compression algorithm divides the bitarray into blocks and chooses a block type based on the local population of 1 bits. This allows the algorithm to handle large bitarrays that contain both dense and sparse regions efficiently.
The encoded blob consists of:
| Type | Head Byte | Count | Bytes per Index | Encoded Block Size | Decoded Block Size |
|---|---|---|---|---|---|
| 0 | 0x00..0x9f | 0..4096 | N/A (raw) | 1..4097 | 0..4096 |
| 1 | 0xa0..0xbf | 0..31 | 1 | 1..32 | 32 |
| 2 | 0xc2 | 0..255 | 2 | 2..512 | 8,192 |
| 3 | 0xc3 | 0..255 | 3 | 2..767 | 2,097,152 |
| 4 | 0xc4 | 0..255 | 4 | 2..1022 | 536,870,912 |
Note: The head byte 0x00 (Type 0 with 0 raw bytes) acts as the stop byte for the decoder.
Bitarray uses Python critical sections to ensure memory safety and operation-level consistency.
a.setall(0)) are atomic in terms of the result; a concurrent reader will see either the old state or the new state, never a partially completed state.count_and()) protect access to both buffers.if a: followed by a.pop() is a race condition because another thread could modify a between the two calls.searchiterator) between threads is not recommended. next() calls from multiple threads do not guarantee exact-once delivery.bitarray and a bytearray) share the same underlying memory, they use different locks. Concurrent modification through different objects sharing a buffer is not guaranteed to be coherent.Use threading.Lock when you need to perform a transaction involving multiple operations or when you need to ensure a specific sequence of events remains uninterrupted.
import threading
lock = threading.Lock()
a = bitarray(10)
# Use a lock to make a sequence of operations atomic
with lock:
if a:
a.pop()A bitarray behaves similarly to a Python list but is optimized for booleans (8 bits per byte). You can initialize them from strings (whitespace is ignored), iterables, or a specified length.
Key behaviors:
bitarray.append(), extend(), and remove() are available for modification.count(value) returns the number of occurrences of a bit.from bitarray import bitarray
a = bitarray() # create empty bitarray
a.append(1)
a.extend([1, 0])
x = bitarray(2 ** 20) # bitarray of length 1048576 (initialized to 0)
b = bitarray('1001 011') # initialize from string (whitespace is ignored)
lst = [1, 0, False, True, True]
c = bitarray(lst) # initialize from iterable
print(a[2]) # returns 0 (integer)
print(a[2:4]) # returns bitarray('01')
print(a.count(1)) # returns count of 1sTo run the tests for the sparse bitarray implementations, use the provided Makefile.
make test$ make testBitarray (v3.10.0+) supports free-threaded CPython 3.14 and later. You can check if your Python interpreter was built with free-threading support using sysconfig.get_config_var("Py_GIL_DISABLED").
On Python 3.14+, you can also check the current runtime state of the GIL using sys._is_gil_enabled(). Note that a free-threaded build can still be run with the GIL enabled, so these two checks serve different purposes.
import sysconfig
# Check if the build supports free-threading
print(sysconfig.get_config_var("Py_GIL_DISABLED"))
import sys
# Check if the GIL is currently enabled in the runtime
print(sys._is_gil_enabled())Once you have a canonical Huffman dictionary, you can use the standard bitarray.encode() and bitarray.decode() methods to process messages. To decode without the full dictionary, you can use the canonical_decode() utility with the count and symbol lists generated during the creation process.
from bitarray import bitarray
from bitarray.util import canonical_huffman, canonical_decode
# 1. Setup: Create the code
cnt = {'a': 5, 'b': 3, 'c': 1, 'd': 1, 'r': 2}
codedict, count, symbol = canonical_huffman(cnt)
# 2. Encoding
msg = "abracadabra"
a = bitarray()
a.encode(codedict, msg)
# a is now bitarray('01011001110011110101100')
# 3. Decoding using the full dictionary
assert ''.join(a.decode(codedict)) == msg
# 4. Decoding using only count and symbol (more memory efficient)
assert ''.join(canonical_decode(a, count, symbol)) == msg