Line data Source code
1 : /**
2 : * @file bitbuffer.c
3 : * @brief Variable-length bit buffer for building compressed output.
4 : *
5 : * @cond INTERNAL
6 : * ============================================================================
7 : * _____ ____
8 : * |_ _|_ _ _ __ __ _ __ _ _ __ __ _ / ___| _ __ __ _ ___ ___
9 : * | |/ _` | '_ \ / _` |/ _` | '__/ _` | \___ \| '_ \ / _` |/ __/ _ \
10 : * | | (_| | | | | (_| | (_| | | | (_| | ___) | |_) | (_| | (_| __/
11 : * |_|\__,_|_| |_|\__,_|\__, |_| \__,_| |____/| .__/ \__,_|\___\___|
12 : * |___/ |_|
13 : * ============================================================================
14 : * @endcond
15 : *
16 : * This module provides a dynamically-growing bit buffer for constructing
17 : * compressed output streams. Bits are appended sequentially using MSB-first
18 : * ordering as required by CCSDS 124.0-B-1.
19 : *
20 : * @par Bit Ordering
21 : * Bits are appended MSB-first within each byte:
22 : * - First bit appended goes to bit position 7
23 : * - Second bit goes to position 6, etc.
24 : *
25 : * @authors Georges Labrèche <georges@tanagraspace.com> — https://georges.fyi
26 : * @authors Claude Code (Anthropic) <noreply@anthropic.com>
27 : *
28 : * @see https://ccsds.org/Pubs/124x0b1.pdf CCSDS 124.0-B-1 Standard
29 : */
30 :
31 : #include "ccsds124.h"
32 : #include <string.h>
33 :
34 : /**
35 : * @name Initialization Functions
36 : * @{
37 : */
38 :
39 :
40 378534 : void bitbuffer_init(bitbuffer_t *bb) {
41 378534 : if (bb != NULL) {
42 378534 : bb->num_bits = 0U;
43 378534 : bb->acc = 0U;
44 378534 : bb->acc_len = 0U;
45 378534 : (void)memset(bb->data, 0, CCSDS124_MAX_OUTPUT_BYTES);
46 : }
47 378534 : }
48 :
49 :
50 189280 : void bitbuffer_clear(bitbuffer_t *bb) {
51 189280 : bitbuffer_init(bb);
52 189280 : }
53 :
54 : /** @} */ /* End of Initialization Functions */
55 :
56 : /**
57 : * @name Bit Appending Functions
58 : * @{
59 : */
60 :
61 :
62 : /**
63 : * @brief Flush accumulator to data buffer when it has 8+ bits.
64 : * @param[in,out] bb Bit buffer
65 : */
66 : static void bitbuffer_flush_acc(bitbuffer_t *bb) {
67 12377952 : while (bb->acc_len >= 8U) {
68 : /* Extract top 8 bits */
69 6188976 : bb->acc_len -= 8U;
70 6188976 : size_t byte_index = (bb->num_bits - bb->acc_len - 8U) / 8U;
71 6188976 : bb->data[byte_index] = (uint8_t)(bb->acc >> bb->acc_len);
72 6188976 : bb->acc &= ((1U << bb->acc_len) - 1U); /* Clear extracted bits */
73 : }
74 : }
75 :
76 :
77 48165520 : int bitbuffer_append_bit(bitbuffer_t *bb, int bit) {
78 : int result = CCSDS124_ERROR_INVALID_ARG;
79 :
80 48165520 : if (bb != NULL) {
81 : /* Check for overflow - CCSDS124_MAX_OUTPUT_BYTES * 8 bits */
82 : size_t max_bits = CCSDS124_MAX_OUTPUT_BYTES * 8U;
83 48165520 : if (bb->num_bits >= max_bits) {
84 : result = CCSDS124_ERROR_OVERFLOW;
85 : } else {
86 : /* Accumulate bit in MSB-first order */
87 48165420 : uint32_t bit_val = ((uint32_t)bit) & 1U;
88 48165420 : bb->acc = (bb->acc << 1U) | bit_val;
89 48165420 : bb->acc_len++;
90 48165420 : bb->num_bits++;
91 :
92 : /* Flush when accumulator has 8+ bits */
93 48165420 : if (bb->acc_len >= 8U) {
94 : bitbuffer_flush_acc(bb);
95 : }
96 :
97 : result = CCSDS124_OK;
98 : }
99 : }
100 :
101 48165520 : return result;
102 : }
103 :
104 :
105 3 : int bitbuffer_append_bits(bitbuffer_t *bb, const uint8_t *data, size_t num_bits) {
106 : int result = CCSDS124_ERROR_INVALID_ARG;
107 :
108 3 : if ((bb != NULL) && (data != NULL)) {
109 : /* Check for overflow - CCSDS124_MAX_OUTPUT_BYTES * 8 bits */
110 : size_t max_bits = CCSDS124_MAX_OUTPUT_BYTES * 8U;
111 3 : if ((bb->num_bits + num_bits) > max_bits) {
112 : result = CCSDS124_ERROR_OVERFLOW;
113 : } else {
114 : result = CCSDS124_OK;
115 :
116 : /* Append each bit MSB-first */
117 23 : for (size_t i = 0U; (i < num_bits) && (result == CCSDS124_OK); i++) {
118 21 : size_t byte_index = i / 8U;
119 21 : size_t bit_index = i % 8U;
120 :
121 : /* Extract bits MSB-first (bit 7, 6, 5, ..., 0) */
122 21 : uint32_t shift_amount = 7U - (uint32_t)bit_index;
123 21 : uint32_t shifted = (uint32_t)data[byte_index] >> shift_amount;
124 21 : uint32_t masked = shifted & 1U;
125 21 : int bit = (int)masked;
126 :
127 21 : result = bitbuffer_append_bit(bb, bit);
128 : }
129 : }
130 : }
131 :
132 3 : return result;
133 : }
134 :
135 :
136 : /**
137 : * @brief Append multiple bits from a value in a single operation.
138 : *
139 : * Batches bit operations to reduce function call overhead vs calling
140 : * bitbuffer_append_bit() in a loop. Used by COUNT encoding lookup table.
141 : *
142 : * Performance: ~2% compression speedup from this optimization. Combined with
143 : * DeBruijn bit extraction and word-level operations, achieves 14-16% faster
144 : * compression and 13-39% faster decompression on real-world datasets.
145 : *
146 : * @param[out] bb Bit buffer
147 : * @param[in] value Value containing bits (right-justified)
148 : * @param[in] num_bits Number of bits to append (1-24)
149 : * @return CCSDS124_OK on success, error code otherwise
150 : */
151 250920 : int bitbuffer_append_value(bitbuffer_t *bb, uint32_t value, size_t num_bits) {
152 : int result = CCSDS124_ERROR_INVALID_ARG;
153 :
154 250920 : if ((bb != NULL) && (num_bits > 0U) && (num_bits <= 24U)) {
155 : /* Check for overflow */
156 : size_t max_bits = CCSDS124_MAX_OUTPUT_BYTES * 8U;
157 250920 : if ((bb->num_bits + num_bits) > max_bits) {
158 : result = CCSDS124_ERROR_OVERFLOW;
159 : } else {
160 : /* Add bits directly to accumulator.
161 : * Value is right-justified: the bottom 'num_bits' bits are the data.
162 : * Mask to ensure only the relevant bits are used. */
163 250920 : uint32_t mask = (1U << (uint32_t)num_bits) - 1U;
164 250920 : uint32_t masked_value = value & mask;
165 :
166 250920 : bb->acc = (bb->acc << (uint32_t)num_bits) | masked_value;
167 250920 : bb->acc_len += num_bits;
168 250920 : bb->num_bits += num_bits;
169 :
170 : /* Flush complete bytes */
171 : bitbuffer_flush_acc(bb);
172 :
173 : result = CCSDS124_OK;
174 : }
175 : }
176 :
177 250920 : return result;
178 : }
179 :
180 :
181 2591 : int bitbuffer_append_bitvector(bitbuffer_t *bb, const bitvector_t *bv) {
182 : int result = CCSDS124_ERROR_INVALID_ARG;
183 :
184 2591 : if ((bb != NULL) && (bv != NULL)) {
185 : result = CCSDS124_OK;
186 :
187 : /* Calculate number of bytes from bit length */
188 2591 : size_t num_bytes = (bv->length + 7U) / 8U;
189 :
190 : /* CCSDS MSB-first: bytes in order, but bits within each byte from MSB to LSB */
191 157674 : for (size_t byte_idx = 0U; (byte_idx < num_bytes) && (result == CCSDS124_OK); byte_idx++) {
192 : size_t bits_in_this_byte = 8U;
193 :
194 : /* Last byte may have fewer than 8 bits */
195 155083 : if (byte_idx == (num_bytes - 1U)) {
196 2591 : size_t remainder = bv->length % 8U;
197 2591 : if (remainder != 0U) {
198 : bits_in_this_byte = remainder;
199 : }
200 : }
201 :
202 : /* With MSB-first bitvector indexing: bit 0 is MSB, bit 7 is LSB
203 : * We want to append bits in order: MSB first, LSB last
204 : * So we iterate through positions 0, 1, 2, ..., bits_in_this_byte-1 */
205 155083 : size_t start_bit = byte_idx * 8U;
206 1395740 : for (size_t bit_offset = 0U; (bit_offset < bits_in_this_byte) && (result == CCSDS124_OK); bit_offset++) {
207 1240657 : size_t pos = start_bit + bit_offset;
208 : int bit = bitvector_get_bit(bv, pos);
209 :
210 1240657 : result = bitbuffer_append_bit(bb, bit);
211 : }
212 : }
213 : }
214 :
215 2591 : return result;
216 : }
217 :
218 : /** @} */ /* End of Bit Appending Functions */
219 :
220 : /**
221 : * @name Query Functions
222 : * @{
223 : */
224 :
225 :
226 54 : size_t bitbuffer_size(const bitbuffer_t *bb) {
227 : size_t size = 0U;
228 :
229 54 : if (bb != NULL) {
230 54 : size = bb->num_bits;
231 : }
232 :
233 54 : return size;
234 : }
235 :
236 : /** @} */ /* End of Query Functions */
237 :
238 : /**
239 : * @name Byte Conversion Functions
240 : * @{
241 : */
242 :
243 :
244 189216 : size_t bitbuffer_to_bytes(const bitbuffer_t *bb, uint8_t *data, size_t max_bytes) {
245 : size_t num_bytes = 0U;
246 :
247 189216 : if ((bb != NULL) && (data != NULL)) {
248 : /* Calculate number of bytes needed (ceiling division) */
249 189216 : num_bytes = (bb->num_bits + 7U) / 8U;
250 :
251 189216 : if (num_bytes > max_bytes) {
252 : num_bytes = max_bytes;
253 : }
254 :
255 : /* Copy flushed bytes from data buffer */
256 189216 : size_t flushed_bytes = (bb->num_bits - bb->acc_len) / 8U;
257 189216 : if (flushed_bytes > num_bytes) {
258 : flushed_bytes = num_bytes;
259 : }
260 189216 : if (flushed_bytes > 0U) {
261 187614 : (void)memcpy(data, bb->data, flushed_bytes);
262 : }
263 :
264 : /* Handle remaining bits in accumulator */
265 189216 : if ((bb->acc_len > 0U) && (flushed_bytes < num_bytes)) {
266 : /* Shift accumulator bits to MSB position */
267 169235 : uint8_t last_byte = (uint8_t)(bb->acc << (8U - bb->acc_len));
268 169235 : data[flushed_bytes] = last_byte;
269 : }
270 : }
271 :
272 189216 : return num_bytes;
273 : }
274 :
275 : /** @} */ /* End of Byte Conversion Functions */
|
