Coverage for ccsds124/bitvector.py: 100%
135 statements
« prev ^ index » next coverage.py v7.14.3, created at 2026-06-29 15:01 +0000
1"""
2Fixed-length bit vector implementation using 32-bit words.
4This module provides fixed-length bit vector operations optimized for
5CCSDS 124.0-B-1 compression. Uses 32-bit words with big-endian byte packing to
6match ESA/ESOC reference implementation.
8Bit Numbering Convention (CCSDS 124.0-B-1 Section 1.6.1):
9- Bit 0 = MSB (Most Significant Bit, transmitted first)
10- Bit N-1 = LSB (Least Significant Bit)
12MicroPython compatible - no typing module imports.
13"""
16class BitVector:
17 """Fixed-length bit vector using 32-bit word storage."""
19 def __init__(self, num_bits: int) -> None:
20 """
21 Initialize a bit vector with specified length.
23 Args:
24 num_bits: Number of bits (must be > 0)
26 Raises:
27 ValueError: If num_bits <= 0
28 """
29 if num_bits <= 0:
30 raise ValueError("num_bits must be positive")
32 self.length = num_bits
33 # Calculate number of 32-bit words needed
34 num_bytes = (num_bits + 7) // 8
35 self.num_words = (num_bytes + 3) // 4
37 # Initialize all words to zero
38 self._data = [0] * self.num_words
40 def zero(self) -> None:
41 """Set all bits to zero."""
42 for i in range(self.num_words):
43 self._data[i] = 0
45 def copy(self) -> "BitVector":
46 """
47 Create a copy of this bit vector.
49 Returns:
50 New BitVector with same contents
51 """
52 result = BitVector(self.length)
53 for i in range(self.num_words):
54 result._data[i] = self._data[i]
55 return result
57 def copy_from(self, other: "BitVector") -> None:
58 """
59 Copy contents from another bit vector into this one.
61 Args:
62 other: Source bit vector to copy from
63 """
64 num_words = min(self.num_words, other.num_words)
65 for i in range(num_words):
66 self._data[i] = other._data[i]
68 def get_bit(self, pos: int) -> int:
69 """
70 Get bit value at position.
72 Args:
73 pos: Bit position (0 = MSB, length-1 = LSB)
75 Returns:
76 Bit value (0 or 1)
78 Raises:
79 IndexError: If pos is out of range
80 """
81 if pos < 0 or pos >= self.length:
82 raise IndexError(f"Bit position {pos} out of range [0, {self.length})")
84 # Calculate byte and bit within byte
85 byte_index = pos // 8
86 bit_in_byte = pos % 8
88 # Calculate word index and byte position within word
89 word_index = byte_index // 4
90 byte_in_word = byte_index % 4
92 # Big-endian: byte 0 is at bits 24-31, byte 1 at 16-23, etc.
93 # MSB-first indexing: bit 0 is the MSB (leftmost) within each byte
94 bit_in_word = ((3 - byte_in_word) * 8) + (7 - bit_in_byte)
96 return (self._data[word_index] >> bit_in_word) & 1
98 def set_bit(self, pos: int, value: int) -> None:
99 """
100 Set bit value at position.
102 Args:
103 pos: Bit position (0 = MSB, length-1 = LSB)
104 value: Bit value (0 or non-zero for 1)
106 Raises:
107 IndexError: If pos is out of range
108 """
109 if pos < 0 or pos >= self.length:
110 raise IndexError(f"Bit position {pos} out of range [0, {self.length})")
112 # Calculate byte and bit within byte
113 byte_index = pos // 8
114 bit_in_byte = pos % 8
116 # Calculate word index and byte position within word
117 word_index = byte_index // 4
118 byte_in_word = byte_index % 4
120 # Big-endian: byte 0 is at bits 24-31, byte 1 at 16-23, etc.
121 # MSB-first indexing: bit 0 is the MSB (leftmost) within each byte
122 bit_in_word = ((3 - byte_in_word) * 8) + (7 - bit_in_byte)
124 if value:
125 # Set bit to 1
126 self._data[word_index] |= 1 << bit_in_word
127 else:
128 # Clear bit to 0
129 self._data[word_index] &= ~(1 << bit_in_word)
131 def from_bytes(self, data: bytes) -> None:
132 """
133 Load bit vector from bytes.
135 Args:
136 data: Bytes to load (big-endian)
137 """
138 # Zero the array first
139 self.zero()
141 # Pack bytes into 32-bit words (big-endian)
142 j = 4 # Counter for bytes within word (4, 3, 2, 1)
143 bytes_to_int = 0
144 current_word = 0
146 for byte in data:
147 j -= 1
148 bytes_to_int |= byte << (j * 8)
150 if j == 0:
151 # Word complete - store it
152 self._data[current_word] = bytes_to_int
153 current_word += 1
154 bytes_to_int = 0
155 j = 4
157 # Handle incomplete final word
158 if j < 4:
159 self._data[current_word] = bytes_to_int
161 def to_bytes(self) -> bytes:
162 """
163 Convert bit vector to bytes.
165 Returns:
166 Bytes representation (big-endian)
167 """
168 expected_bytes = (self.length + 7) // 8
169 result = bytearray(expected_bytes)
171 byte_index = 0
172 for word_index in range(self.num_words):
173 word = self._data[word_index]
175 # Extract up to 4 bytes from this word
176 for j in range(3, -1, -1):
177 if byte_index >= expected_bytes:
178 break
179 result[byte_index] = (word >> (j * 8)) & 0xFF
180 byte_index += 1
182 return bytes(result)
184 def xor(self, a: "BitVector", b: "BitVector | None" = None) -> "BitVector":
185 """
186 Compute XOR of bit vectors.
188 Two calling conventions:
189 - result = v.xor(other) - returns new vector with v XOR other
190 - v.xor(a, b) - stores a XOR b into v (in-place)
192 Args:
193 a: First operand (or only operand if b is None)
194 b: Second operand (optional)
196 Returns:
197 New BitVector if b is None, else self
198 """
199 if b is None:
200 # Old API: return self XOR a
201 result = BitVector(self.length)
202 num_words = min(self.num_words, a.num_words)
203 for i in range(num_words):
204 result._data[i] = self._data[i] ^ a._data[i]
205 return result
206 else:
207 # New API: self = a XOR b
208 num_words = min(self.num_words, a.num_words, b.num_words)
209 for i in range(num_words):
210 self._data[i] = a._data[i] ^ b._data[i]
211 return self
213 def or_(self, a: "BitVector", b: "BitVector | None" = None) -> "BitVector":
214 """
215 Compute OR of bit vectors.
217 Two calling conventions:
218 - result = v.or_(other) - returns new vector with v OR other
219 - v.or_(a, b) - stores a OR b into v (in-place)
221 Args:
222 a: First operand (or only operand if b is None)
223 b: Second operand (optional)
225 Returns:
226 New BitVector if b is None, else self
227 """
228 if b is None:
229 # Old API: return self OR a
230 result = BitVector(self.length)
231 num_words = min(self.num_words, a.num_words)
232 for i in range(num_words):
233 result._data[i] = self._data[i] | a._data[i]
234 return result
235 else:
236 # New API: self = a OR b
237 num_words = min(self.num_words, a.num_words, b.num_words)
238 for i in range(num_words):
239 self._data[i] = a._data[i] | b._data[i]
240 return self
242 def and_(self, other: "BitVector") -> "BitVector":
243 """
244 Compute AND with another bit vector.
246 Args:
247 other: Other bit vector
249 Returns:
250 New BitVector with result
251 """
252 result = BitVector(self.length)
253 num_words = min(self.num_words, other.num_words)
255 for i in range(num_words):
256 result._data[i] = self._data[i] & other._data[i]
258 return result
260 def not_(self) -> "BitVector":
261 """
262 Compute NOT (bitwise inversion).
264 Returns:
265 New BitVector with inverted bits
266 """
267 result = BitVector(self.length)
269 for i in range(self.num_words):
270 result._data[i] = ~self._data[i] & 0xFFFFFFFF
272 # Mask off unused bits in last word
273 if self.num_words > 0:
274 num_bytes = (self.length + 7) // 8
275 bytes_in_last_word = ((num_bytes - 1) % 4) + 1
276 bits_in_last_byte = self.length - ((num_bytes - 1) * 8)
278 # Create mask for valid bits in big-endian word.
279 # MSB-first: valid bits in a partial last byte are at the HIGH
280 # end of the byte, so mask 0xFF << (8 - bits) (GOTCHAS #19).
281 mask = 0
282 for byte in range(bytes_in_last_word):
283 if byte == bytes_in_last_word - 1:
284 byte_mask = (0xFF << (8 - bits_in_last_byte)) & 0xFF
285 else:
286 byte_mask = 0xFF
287 shift_amt = (3 - byte) * 8
288 mask |= byte_mask << shift_amt
290 result._data[self.num_words - 1] &= mask
292 return result
294 def left_shift(self) -> "BitVector":
295 """
296 Compute left shift by 1 position.
298 Left shift moves bits toward MSB (lower indices).
299 MSB is lost, LSB becomes 0.
301 Returns:
302 New BitVector with shifted bits
303 """
304 result = BitVector(self.length)
306 # Word-level left shift (big-endian: MSB in high bits of first word)
307 # Shift each word left by 1, carry MSB from next word
308 carry = 0
309 for i in range(self.num_words - 1, -1, -1):
310 word = self._data[i]
311 result._data[i] = ((word << 1) | carry) & 0xFFFFFFFF
312 carry = (word >> 31) & 1
314 return result
316 def hamming_weight(self) -> int:
317 """
318 Count number of 1 bits.
320 Returns:
321 Number of bits set to 1
322 """
323 count = 0
324 for word in self._data:
325 # Fast popcount using bit manipulation
326 n = word
327 while n:
328 count += n & 1
329 n >>= 1
330 return count
332 def equals(self, other: "BitVector") -> bool:
333 """
334 Check equality with another bit vector.
336 Args:
337 other: Other bit vector
339 Returns:
340 True if equal, False otherwise
341 """
342 if self.length != other.length:
343 return False
345 for i in range(self.num_words):
346 if self._data[i] != other._data[i]:
347 return False
349 return True