Line data Source code
1 : /**
2 : * @file bitvector.c
3 : * @brief Fixed-length bit vector implementation using 32-bit words.
4 : *
5 : * @cond INTERNAL
6 : * ============================================================================
7 : * _____ ____
8 : * |_ _|_ _ _ __ __ _ __ _ _ __ __ _ / ___| _ __ __ _ ___ ___
9 : * | |/ _` | '_ \ / _` |/ _` | '__/ _` | \___ \| '_ \ / _` |/ __/ _ \
10 : * | | (_| | | | | (_| | (_| | | | (_| | ___) | |_) | (_| | (_| __/
11 : * |_|\__,_|_| |_|\__,_|\__, |_| \__,_| |____/| .__/ \__,_|\___\___|
12 : * |___/ |_|
13 : * ============================================================================
14 : * @endcond
15 : *
16 : * This module provides fixed-length bit vector operations optimized for
17 : * CCSDS 124.0-B-1 compression. Uses 32-bit words with big-endian byte packing to
18 : * match ESA/ESOC reference implementation.
19 : *
20 : * @par Bit Numbering Convention (CCSDS 124.0-B-1 Section 1.6.1)
21 : * - Bit 0 = LSB (Least Significant Bit)
22 : * - Bit N-1 = MSB (Most Significant Bit, transmitted first)
23 : *
24 : * @par Word Packing (Big-Endian)
25 : * Within each 32-bit word:
26 : * - Word[i] = (Byte[4i] << 24) | (Byte[4i+1] << 16) | (Byte[4i+2] << 8) | Byte[4i+3]
27 : * - Bit 0 = LSB of word, Bit 31 = MSB of word
28 : *
29 : * @authors Georges Labrèche <georges@tanagraspace.com> — https://georges.fyi
30 : * @authors Claude Code (Anthropic) <noreply@anthropic.com>
31 : *
32 : * @see https://ccsds.org/Pubs/124x0b1.pdf CCSDS 124.0-B-1 Standard
33 : */
34 :
35 : #include "ccsds124.h"
36 : #include <string.h>
37 :
38 : /**
39 : * @name Initialization Functions
40 : * @{
41 : */
42 :
43 :
44 1132223 : int bitvector_init(bitvector_t *bv, size_t num_bits) {
45 : int result = CCSDS124_ERROR_INVALID_ARG;
46 :
47 1132223 : if (bv != NULL) {
48 1132223 : if ((num_bits > 0U) && (num_bits <= (size_t)CCSDS124_MAX_PACKET_LENGTH)) {
49 1132221 : bv->length = num_bits;
50 : /* Calculate number of 32-bit words needed */
51 1132221 : size_t num_bytes = (num_bits + 7U) / 8U;
52 1132221 : bv->num_words = (num_bytes + 3U) / 4U; /* Ceiling division */
53 :
54 : /* Zero all words */
55 1132221 : (void)memset(bv->data, 0, bv->num_words * sizeof(uint32_t));
56 :
57 : result = CCSDS124_OK;
58 : }
59 : }
60 :
61 1132223 : return result;
62 : }
63 :
64 :
65 403353 : void bitvector_zero(bitvector_t *bv) {
66 403353 : if (bv != NULL) {
67 403353 : (void)memset(bv->data, 0, bv->num_words * sizeof(uint32_t));
68 : }
69 403353 : }
70 :
71 :
72 1706589 : void bitvector_copy(bitvector_t *dest, const bitvector_t *src) {
73 1706589 : if ((dest != NULL) && (src != NULL)) {
74 1706589 : dest->length = src->length;
75 1706589 : dest->num_words = src->num_words;
76 1706589 : (void)memcpy(dest->data, src->data, src->num_words * sizeof(uint32_t));
77 : }
78 1706589 : }
79 :
80 : /** @} */ /* End of Initialization Functions */
81 :
82 : /* Note: bitvector_get_bit and bitvector_set_bit are now static inline in ccsds124.h */
83 :
84 : /**
85 : * @name Bitwise Operations
86 : *
87 : * Implements bitwise operations as defined in CCSDS 124.0-B-1 Section 1.6.1.
88 : * All operations work word-by-word for efficiency.
89 : * @{
90 : */
91 :
92 :
93 561752 : void bitvector_xor(bitvector_t *result, const bitvector_t *a, const bitvector_t *b) {
94 561752 : if ((result != NULL) && (a != NULL) && (b != NULL)) {
95 561752 : size_t num_words = a->num_words;
96 561752 : if (b->num_words < num_words) {
97 : num_words = b->num_words;
98 : }
99 :
100 11785683 : for (size_t i = 0U; i < num_words; i++) {
101 11223931 : result->data[i] = a->data[i] ^ b->data[i];
102 : }
103 :
104 561752 : result->length = a->length;
105 561752 : result->num_words = a->num_words;
106 : }
107 561752 : }
108 :
109 :
110 382205 : void bitvector_or(bitvector_t *result, const bitvector_t *a, const bitvector_t *b) {
111 382205 : if ((result != NULL) && (a != NULL) && (b != NULL)) {
112 382205 : size_t num_words = a->num_words;
113 382205 : if (b->num_words < num_words) {
114 : num_words = b->num_words;
115 : }
116 :
117 7778598 : for (size_t i = 0U; i < num_words; i++) {
118 7396393 : result->data[i] = a->data[i] | b->data[i];
119 : }
120 :
121 382205 : result->length = a->length;
122 382205 : result->num_words = a->num_words;
123 : }
124 382205 : }
125 :
126 :
127 2 : void bitvector_and(bitvector_t *result, const bitvector_t *a, const bitvector_t *b) {
128 2 : if ((result != NULL) && (a != NULL) && (b != NULL)) {
129 2 : size_t num_words = a->num_words;
130 2 : if (b->num_words < num_words) {
131 : num_words = b->num_words;
132 : }
133 :
134 4 : for (size_t i = 0U; i < num_words; i++) {
135 2 : result->data[i] = a->data[i] & b->data[i];
136 : }
137 :
138 2 : result->length = a->length;
139 2 : result->num_words = a->num_words;
140 : }
141 2 : }
142 :
143 :
144 24234 : void bitvector_not(bitvector_t *result, const bitvector_t *a) {
145 24234 : if ((result != NULL) && (a != NULL)) {
146 581376 : for (size_t i = 0U; i < a->num_words; i++) {
147 557142 : result->data[i] = ~a->data[i];
148 : }
149 :
150 : /* Mask off unused bits in last word with big-endian packing */
151 24234 : if (a->num_words > 0U) {
152 24234 : size_t num_bytes = (a->length + 7U) / 8U;
153 24234 : size_t bytes_in_last_word = ((num_bytes - 1U) % 4U) + 1U;
154 24234 : size_t bits_in_last_byte = a->length - ((num_bytes - 1U) * 8U);
155 :
156 : /* Create mask for valid bits in big-endian word */
157 : uint32_t mask = 0U;
158 72706 : for (size_t byte = 0U; byte < bytes_in_last_word; byte++) {
159 : uint8_t byte_mask;
160 48472 : if (byte == (bytes_in_last_word - 1U)) {
161 : /* MSB-aligned: valid bits are at the top of the byte */
162 24234 : byte_mask = (uint8_t)(0xFFU << (8U - bits_in_last_byte));
163 : } else {
164 : byte_mask = 0xFFU;
165 : }
166 48472 : uint32_t shift_amt = (3U - (uint32_t)byte) * 8U;
167 48472 : mask |= ((uint32_t)byte_mask) << shift_amt;
168 : }
169 24234 : result->data[a->num_words - 1U] &= mask;
170 : }
171 :
172 24234 : result->length = a->length;
173 24234 : result->num_words = a->num_words;
174 : }
175 24234 : }
176 :
177 :
178 5006 : void bitvector_left_shift(bitvector_t *result, const bitvector_t *a) {
179 5006 : if ((result != NULL) && (a != NULL)) {
180 5006 : result->length = a->length;
181 5006 : result->num_words = a->num_words;
182 :
183 : /* MSB-first with big-endian word packing:
184 : * Left shift means shift towards MSB (bit 0).
185 : * In big-endian packing, MSB is at high bits of first word.
186 : * Word-level: shift each word left by 1, carry high bit from next word. */
187 5006 : if (a->num_words > 0U) {
188 : /* Process words from first (MSB) to last (LSB) */
189 78797 : for (size_t i = 0U; i < (a->num_words - 1U); i++) {
190 : /* Shift current word left by 1, bring in MSB from next word */
191 73791 : result->data[i] = (a->data[i] << 1U) | (a->data[i + 1U] >> 31U);
192 : }
193 : /* Last word: shift left, LSB becomes 0 */
194 5006 : result->data[a->num_words - 1U] = a->data[a->num_words - 1U] << 1U;
195 : }
196 : }
197 5006 : }
198 :
199 :
200 2 : void bitvector_reverse(bitvector_t *result, const bitvector_t *a) {
201 2 : if ((result != NULL) && (a != NULL)) {
202 2 : bitvector_zero(result);
203 2 : result->length = a->length;
204 2 : result->num_words = a->num_words;
205 :
206 : /* Reverse bit order */
207 26 : for (size_t i = 0U; i < a->length; i++) {
208 : int bit = bitvector_get_bit(a, i);
209 24 : bitvector_set_bit(result, (a->length - 1U) - i, bit);
210 : }
211 : }
212 2 : }
213 :
214 : /** @} */ /* End of Bitwise Operations */
215 :
216 : /**
217 : * @name Utility Functions
218 : * @{
219 : */
220 :
221 :
222 1411388 : size_t bitvector_hamming_weight(const bitvector_t *bv) {
223 : size_t count = 0U;
224 :
225 1411388 : if (bv != NULL) {
226 : /* Count '1' bits in each word using popcount intrinsic */
227 25800833 : for (size_t i = 0U; i < bv->num_words; i++) {
228 24389445 : count += (size_t)__builtin_popcount(bv->data[i]);
229 : }
230 :
231 : /* Adjust for any extra bits in last word */
232 1411388 : size_t num_bytes = (bv->length + 7U) / 8U;
233 1411388 : size_t extra_bits = (num_bytes * 8U) - bv->length;
234 1411388 : if ((extra_bits > 0U) && (bv->num_words > 0U)) {
235 : /* Count bits in the unused portion of the last word and subtract */
236 2 : uint32_t last_word = bv->data[bv->num_words - 1U];
237 2 : uint32_t mask = ((1U << (uint32_t)extra_bits) - 1U); /* Mask for the unused LSBs */
238 2 : uint32_t extra_word = last_word & mask;
239 2 : count -= (size_t)__builtin_popcount(extra_word);
240 : }
241 : }
242 :
243 1411388 : return count;
244 : }
245 :
246 :
247 5096 : int bitvector_equals(const bitvector_t *a, const bitvector_t *b) {
248 : int result = 0;
249 :
250 5096 : if ((a != NULL) && (b != NULL)) {
251 5096 : if (a->length == b->length) {
252 5096 : if (memcmp(a->data, b->data, a->num_words * sizeof(uint32_t)) == 0) {
253 : result = 1;
254 : }
255 : }
256 : }
257 :
258 5096 : return result;
259 : }
260 :
261 : /** @} */ /* End of Utility Functions */
262 :
263 : /**
264 : * @name Byte Conversion Functions
265 : * @{
266 : */
267 :
268 :
269 189197 : int bitvector_from_bytes(bitvector_t *bv, const uint8_t *data, size_t num_bytes) {
270 : int result = CCSDS124_ERROR_INVALID_ARG;
271 :
272 189197 : if ((bv != NULL) && (data != NULL)) {
273 189197 : size_t expected_bytes = (bv->length + 7U) / 8U;
274 189197 : if (num_bytes > expected_bytes) {
275 : result = CCSDS124_ERROR_OVERFLOW;
276 : } else {
277 : /* Zero the array first */
278 189196 : (void)memset(bv->data, 0, bv->num_words * sizeof(uint32_t));
279 :
280 : /* Pack bytes into 32-bit words (big-endian) */
281 : int j = 4; /* Counter for bytes within word (4, 3, 2, 1) */
282 : uint32_t bytes_to_int = 0U;
283 : size_t current_word = 0U;
284 :
285 14981730 : for (size_t current_byte = 0U; current_byte < num_bytes; current_byte++) {
286 14792534 : j--;
287 14792534 : bytes_to_int |= ((uint32_t)data[current_byte]) << ((unsigned)j * 8U);
288 :
289 14792534 : if (j == 0) {
290 : /* Word complete - store it */
291 3617116 : bv->data[current_word] = bytes_to_int;
292 3617116 : current_word++;
293 : bytes_to_int = 0U;
294 : j = 4;
295 : }
296 : }
297 :
298 : /* Handle incomplete final word */
299 189196 : if (j < 4) {
300 162061 : bv->data[current_word] = bytes_to_int;
301 : }
302 :
303 : result = CCSDS124_OK;
304 : }
305 : }
306 :
307 189197 : return result;
308 : }
309 :
310 :
311 189393 : int bitvector_to_bytes(const bitvector_t *bv, uint8_t *data, size_t num_bytes) {
312 : int result = CCSDS124_ERROR_INVALID_ARG;
313 :
314 189393 : if ((bv != NULL) && (data != NULL)) {
315 189393 : size_t expected_bytes = (bv->length + 7U) / 8U;
316 189393 : if (num_bytes < expected_bytes) {
317 : result = CCSDS124_ERROR_UNDERFLOW;
318 : } else {
319 : /* Extract bytes from 32-bit words (big-endian) */
320 : size_t byte_index = 0U;
321 3969019 : for (size_t word_index = 0U; (word_index < bv->num_words) && (byte_index < num_bytes); word_index++) {
322 3779627 : uint32_t word = bv->data[word_index];
323 :
324 : /* Extract up to 4 bytes from this word */
325 18574075 : for (int j = 3; (j >= 0) && (byte_index < expected_bytes); j--) {
326 14794448 : data[byte_index] = (uint8_t)((word >> ((unsigned)j * 8U)) & 0xFFU);
327 14794448 : byte_index++;
328 : }
329 : }
330 :
331 : result = CCSDS124_OK;
332 : }
333 : }
334 :
335 189393 : return result;
336 : }
337 :
338 : /** @} */ /* End of Byte Conversion Functions */
|
