Line data Source code
1 : /**
2 : * @file encode.c
3 : * @brief CCSDS 124.0-B-1 encoding functions (COUNT, RLE, BE).
4 : *
5 : * @cond INTERNAL
6 : * ============================================================================
7 : * _____ ____
8 : * |_ _|_ _ _ __ __ _ __ _ _ __ __ _ / ___| _ __ __ _ ___ ___
9 : * | |/ _` | '_ \ / _` |/ _` | '__/ _` | \___ \| '_ \ / _` |/ __/ _ \
10 : * | | (_| | | | | (_| | (_| | | | (_| | ___) | |_) | (_| | (_| __/
11 : * |_|\__,_|_| |_|\__,_|\__, |_| \__,_| |____/| .__/ \__,_|\___\___|
12 : * |___/ |_|
13 : * ============================================================================
14 : * @endcond
15 : *
16 : * Implements CCSDS 124.0-B-1 Section 5.2 encoding schemes:
17 : * - Counter Encoding (COUNT) - Section 5.2.2, Table 5-1, Equation 9
18 : * - Run-Length Encoding (RLE) - Section 5.2.3, Equation 10
19 : * - Bit Extraction (BE) - Section 5.2.4, Equation 11
20 : *
21 : * @authors Georges Labrèche <georges@tanagraspace.com> — https://georges.fyi
22 : * @authors Claude Code (Anthropic) <noreply@anthropic.com>
23 : *
24 : * @see https://ccsds.org/Pubs/124x0b1.pdf CCSDS 124.0-B-1 Standard
25 : */
26 :
27 : #include "ccsds124.h"
28 :
29 : /**
30 : * @name Counter Encoding (COUNT)
31 : *
32 : * CCSDS Section 5.2.2, Table 5-1, Equation 9.
33 : * Encodes positive integers 1 ≤ A ≤ 2^16 - 1:
34 : * - A = 1 → '0'
35 : * - 2 ≤ A ≤ 33 → '110' ∥ BIT₅(A-2)
36 : * - A ≥ 34 → '111' ∥ BIT_E(A-2) where E = 2⌊log₂(A-2)+1⌋ - 6
37 : * @{
38 : */
39 :
40 862718 : int ccsds124_count_encode(bitbuffer_t *output, uint32_t A) {
41 : int result = CCSDS124_ERROR_INVALID_ARG;
42 :
43 : /**
44 : * Pre-computed COUNT encodings for values 1-33.
45 : *
46 : * Eliminates per-value bit-by-bit encoding for the most common COUNT values
47 : * by using bitbuffer_append_value() with pre-computed patterns.
48 : *
49 : * Performance: ~2% compression speedup from this optimization. Combined with
50 : * DeBruijn bit extraction and word-level operations, achieves 14-16% faster
51 : * compression and 13-39% faster decompression on real-world datasets.
52 : *
53 : * - A=1: '0' (1 bit) → handled separately (single append_bit is faster)
54 : * - A=2-33: '110' ∥ BIT₅(A-2) (8 bits) → count_values[A]=0xC0|(A-2)
55 : *
56 : * Values 1-33 cover the fast path; larger values (A≥34) use bit-by-bit
57 : * encoding for MISRA-C:2012 compliance (shift bounds verification).
58 : */
59 : static const uint8_t count_values[34] = {
60 : 0U, 0U, /* 0: unused, 1: '0' */
61 : 0xC0U, 0xC1U, 0xC2U, 0xC3U, 0xC4U, 0xC5U, 0xC6U, 0xC7U, /* 2-9 */
62 : 0xC8U, 0xC9U, 0xCAU, 0xCBU, 0xCCU, 0xCDU, 0xCEU, 0xCFU, /* 10-17 */
63 : 0xD0U, 0xD1U, 0xD2U, 0xD3U, 0xD4U, 0xD5U, 0xD6U, 0xD7U, /* 18-25 */
64 : 0xD8U, 0xD9U, 0xDAU, 0xDBU, 0xDCU, 0xDDU, 0xDEU, 0xDFU /* 26-33 */
65 : };
66 : static const uint8_t count_bits[34] = {
67 : 0U, 1U, /* 0: unused, 1: 1 bit */
68 : 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, /* 2-9: 8 bits each */
69 : 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, /* 10-17 */
70 : 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U, /* 18-25 */
71 : 8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U /* 26-33 */
72 : };
73 :
74 862718 : if (output != NULL) {
75 862718 : if ((A == 0U) || (A > 65535U)) {
76 : /* Invalid range - result already set to INVALID_ARG */
77 862718 : } else if (A == 1U) {
78 : /* Case 1: A = 1 → '0' (single bit, no lookup overhead) */
79 366491 : result = bitbuffer_append_bit(output, 0);
80 496227 : } else if (A <= 33U) {
81 : /* Fast path: use pre-computed lookup table for A=2-33 */
82 250920 : result = bitbuffer_append_value(output,
83 250920 : (uint32_t)count_values[A],
84 250920 : (size_t)count_bits[A]);
85 : } else {
86 : /* Case 3: A ≥ 34 → '111' ∥ BIT_E(A-2)
87 : * Uses bit-by-bit approach for MISRA-C:2012 compliance. */
88 :
89 : /* Append '111' prefix MSB-first: 1, 1, 1 */
90 245307 : result = bitbuffer_append_bit(output, 1);
91 245307 : if (result == CCSDS124_OK) {
92 245307 : result = bitbuffer_append_bit(output, 1);
93 : }
94 245307 : if (result == CCSDS124_OK) {
95 245307 : result = bitbuffer_append_bit(output, 1);
96 : }
97 :
98 245307 : if (result == CCSDS124_OK) {
99 : /* Calculate E = 2⌊log₂(A-2)+1⌋ - 6
100 : * floor(log2(value)) = highest set bit = 31 - clz(value) */
101 245307 : uint32_t value = A - 2U;
102 245307 : int highest_bit = 31 - __builtin_clz(value);
103 245307 : int E = (2 * (highest_bit + 1)) - 6;
104 :
105 : /* Append BIT_E(A-2) MSB-first - E bits from bit E-1 down to bit 0 */
106 2595501 : for (int i = E - 1; (i >= 0) && (result == CCSDS124_OK); i--) {
107 2350194 : uint32_t shifted = value >> (uint32_t)i;
108 2350194 : uint32_t masked = shifted & 1U;
109 2350194 : int bit = (int)masked;
110 2350194 : result = bitbuffer_append_bit(output, bit);
111 : }
112 : }
113 : }
114 : }
115 :
116 862718 : return result;
117 : }
118 :
119 : /** @} */ /* End of Counter Encoding */
120 :
121 : /**
122 : * @name Run-Length Encoding (RLE)
123 : *
124 : * CCSDS Section 5.2.3, Equation 10.
125 : * RLE(a) = COUNT(C₀) ∥ COUNT(C₁) ∥ ... ∥ COUNT(C_{H(a)-1}) ∥ '10'
126 : *
127 : * where Cᵢ = 1 + (count of consecutive '0' bits before i-th '1' bit)
128 : * and H(a) = Hamming weight (number of '1' bits in a)
129 : *
130 : * @note Trailing zeros are not encoded (deducible from vector length)
131 : * @{
132 : */
133 :
134 :
135 194256 : int ccsds124_rle_encode(bitbuffer_t *output, const bitvector_t *input) {
136 : int result = CCSDS124_ERROR_INVALID_ARG;
137 :
138 194256 : if ((output != NULL) && (input != NULL)) {
139 : /* DeBruijn lookup table for fast LSB finding (matches reference implementation) */
140 : static const uint32_t debruijn_lookup[32] = {
141 : 1U, 2U, 29U, 3U, 30U, 15U, 25U, 4U, 31U, 23U, 21U, 16U,
142 : 26U, 18U, 5U, 9U, 32U, 28U, 14U, 24U, 22U, 20U, 17U, 8U,
143 : 27U, 13U, 19U, 7U, 12U, 6U, 11U, 10U
144 : };
145 :
146 : result = CCSDS124_OK;
147 :
148 : /* Start from the end of the vector */
149 194256 : int old_bit_position = (int)input->length;
150 :
151 : /* Process words in reverse order (from high to low) */
152 4052555 : for (int word = (int)input->num_words - 1; (word >= 0) && (result == CCSDS124_OK); word--) {
153 3858299 : uint32_t word_data = input->data[word];
154 :
155 : /* Process all set bits in this word */
156 4718414 : while ((word_data != 0U) && (result == CCSDS124_OK)) {
157 : /* Isolate the LSB: x = change & -change */
158 860115 : uint32_t lsb = word_data & (uint32_t)(-(int32_t)word_data);
159 :
160 : /* Find LSB position using DeBruijn sequence */
161 860115 : uint32_t debruijn_index = (lsb * 0x077CB531U) >> 27U;
162 860115 : int bit_position_in_word = (int)debruijn_lookup[debruijn_index];
163 :
164 : /* Count from the other side (reference line 754) */
165 860115 : bit_position_in_word = 32 - bit_position_in_word;
166 :
167 : /* Calculate global bit position (reference line 756) */
168 860115 : int new_bit_position = (word * 32) + bit_position_in_word;
169 :
170 : /* Calculate delta (number of zeros + 1) */
171 860115 : int delta = old_bit_position - new_bit_position;
172 :
173 : /* Encode the count */
174 860115 : result = ccsds124_count_encode(output, (uint32_t)delta);
175 :
176 : /* Update old position for next iteration */
177 : old_bit_position = new_bit_position;
178 :
179 : /* Clear the processed bit */
180 860115 : word_data ^= lsb;
181 : }
182 : }
183 :
184 : /* Append terminator '10' MSB-first (bits: 1, 0) */
185 194256 : if (result == CCSDS124_OK) {
186 194256 : result = bitbuffer_append_bit(output, 1);
187 : }
188 194256 : if (result == CCSDS124_OK) {
189 194256 : result = bitbuffer_append_bit(output, 0);
190 : }
191 : }
192 :
193 194256 : return result;
194 : }
195 :
196 : /** @} */ /* End of Run-Length Encoding */
197 :
198 : /**
199 : * @name Bit Extraction (BE)
200 : *
201 : * CCSDS Section 5.2.4, Equation 11.
202 : * BE(a, b) = a_{g_{H(b)-1}} ∥ ... ∥ a_{g₁} ∥ a_{g₀}
203 : *
204 : * where gᵢ is the position of the i-th '1' bit in b (MSB to LSB order)
205 : *
206 : * Extracts bits from 'a' at positions where 'b' has '1' bits.
207 : * Output order: MSB to LSB (reverse order of finding '1' bits)
208 : *
209 : * @par Example
210 : * @code
211 : * BE('10110011', '01001010') = '001'
212 : * Positions with '1' in mask: 1, 3, 6
213 : * Extract from data: bit[1]=1, bit[3]=0, bit[6]=0
214 : * Output (MSB→LSB): 0, 0, 1
215 : * @endcode
216 : * @{
217 : */
218 :
219 :
220 186657 : int ccsds124_bit_extract(bitbuffer_t *output, const bitvector_t *data, const bitvector_t *mask) {
221 : int result = CCSDS124_ERROR_INVALID_ARG;
222 :
223 186657 : if ((output != NULL) && (data != NULL) && (mask != NULL)) {
224 186657 : if (data->length != mask->length) {
225 : /* Length mismatch - result already set to INVALID_ARG */
226 : } else {
227 : /* DeBruijn lookup for fast LSB finding (same as RLE) */
228 : static const uint32_t debruijn_lookup[32] = {
229 : 1U, 2U, 29U, 3U, 30U, 15U, 25U, 4U, 31U, 23U, 21U, 16U,
230 : 26U, 18U, 5U, 9U, 32U, 28U, 14U, 24U, 22U, 20U, 17U, 8U,
231 : 27U, 13U, 19U, 7U, 12U, 6U, 11U, 10U
232 : };
233 :
234 : result = CCSDS124_OK;
235 :
236 : /* Process words in REVERSE order (high to low) like RLE.
237 : * This gives bits from highest position to lowest, which is
238 : * the correct output order for BE (no reversal needed). */
239 3926531 : for (int word = (int)mask->num_words - 1; (word >= 0) && (result == CCSDS124_OK); word--) {
240 3739875 : uint32_t mask_word = mask->data[word];
241 3739875 : uint32_t data_word = data->data[word];
242 :
243 44534085 : while ((mask_word != 0U) && (result == CCSDS124_OK)) {
244 : /* Isolate LSB */
245 40794210 : uint32_t lsb = mask_word & (uint32_t)(-(int32_t)mask_word);
246 :
247 : /* Find LSB position using DeBruijn */
248 40794210 : uint32_t debruijn_index = (lsb * 0x077CB531U) >> 27U;
249 40794210 : int bit_pos_in_word = 32 - (int)debruijn_lookup[debruijn_index];
250 :
251 : /* Check if this bit is within the valid length */
252 40794210 : int global_pos = (word * 32) + bit_pos_in_word;
253 40794210 : if ((size_t)global_pos < data->length) {
254 : /* Extract and output data bit directly */
255 : int bit = 0;
256 40794210 : if ((data_word & lsb) != 0U) {
257 : bit = 1;
258 : }
259 40794210 : result = bitbuffer_append_bit(output, bit);
260 : }
261 :
262 : /* Clear processed bit */
263 40794210 : mask_word ^= lsb;
264 : }
265 : }
266 : }
267 : }
268 :
269 186657 : return result;
270 : }
271 :
272 :
273 24233 : int ccsds124_bit_extract_forward(bitbuffer_t *output, const bitvector_t *data, const bitvector_t *mask) {
274 : int result = CCSDS124_ERROR_INVALID_ARG;
275 :
276 24233 : if ((output != NULL) && (data != NULL) && (mask != NULL)) {
277 24233 : if (data->length != mask->length) {
278 : /* Length mismatch - result already set to INVALID_ARG */
279 : } else {
280 : result = CCSDS124_OK;
281 :
282 : /* Process words in FORWARD order (low to high).
283 : * Within each word, find MSBs first using clz to get
284 : * bits from lowest position to highest. */
285 581372 : for (size_t word = 0U; (word < mask->num_words) && (result == CCSDS124_OK); word++) {
286 557140 : uint32_t mask_word = mask->data[word];
287 557140 : uint32_t data_word = data->data[word];
288 :
289 974195 : while ((mask_word != 0U) && (result == CCSDS124_OK)) {
290 : /* Find MSB position using count leading zeros */
291 417055 : int clz = __builtin_clz(mask_word);
292 : int bit_pos_in_word = clz; /* Physical position from left */
293 :
294 : /* MSB-first: physical position 0 = bit index 0 */
295 417055 : size_t global_pos = (word * 32U) + (size_t)bit_pos_in_word;
296 :
297 417055 : if (global_pos < data->length) {
298 : /* Extract data bit at this position */
299 417055 : uint32_t bit_mask = 1U << (31U - (uint32_t)clz);
300 : int bit = 0;
301 417055 : if ((data_word & bit_mask) != 0U) {
302 : bit = 1;
303 : }
304 417055 : result = bitbuffer_append_bit(output, bit);
305 : }
306 :
307 : /* Clear the MSB we just processed */
308 417055 : mask_word &= ~(1U << (31U - (uint32_t)clz));
309 : }
310 : }
311 : }
312 : }
313 :
314 24233 : return result;
315 : }
316 :
317 : /** @} */ /* End of Bit Extraction */
|
