encode.c

Go to the documentation of this file.

 
#include "ccsds124.h"
 
int ccsds124_count_encode(bitbuffer_t *output, uint32_t A) {
    int result = CCSDS124_ERROR_INVALID_ARG;
 
    static const uint8_t count_values[34] = {
        0U, 0U,                                             /* 0: unused, 1: '0' */
        0xC0U, 0xC1U, 0xC2U, 0xC3U, 0xC4U, 0xC5U, 0xC6U, 0xC7U,  /* 2-9 */
        0xC8U, 0xC9U, 0xCAU, 0xCBU, 0xCCU, 0xCDU, 0xCEU, 0xCFU,  /* 10-17 */
        0xD0U, 0xD1U, 0xD2U, 0xD3U, 0xD4U, 0xD5U, 0xD6U, 0xD7U,  /* 18-25 */
        0xD8U, 0xD9U, 0xDAU, 0xDBU, 0xDCU, 0xDDU, 0xDEU, 0xDFU   /* 26-33 */
    };
    static const uint8_t count_bits[34] = {
        0U, 1U,                                     /* 0: unused, 1: 1 bit */
        8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,              /* 2-9: 8 bits each */
        8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,              /* 10-17 */
        8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U,              /* 18-25 */
        8U, 8U, 8U, 8U, 8U, 8U, 8U, 8U               /* 26-33 */
    };
 
    if (output != NULL) {
        if ((A == 0U) || (A > 65535U)) {
            /* Invalid range - result already set to INVALID_ARG */
        } else if (A == 1U) {
            /* Case 1: A = 1 → '0' (single bit, no lookup overhead) */
            result = bitbuffer_append_bit(output, 0);
        } else if (A <= 33U) {
            /* Fast path: use pre-computed lookup table for A=2-33 */
            result = bitbuffer_append_value(output,
                                            (uint32_t)count_values[A],
                                            (size_t)count_bits[A]);
        } else {
            /* Case 3: A ≥ 34 → '111' ∥ BIT_E(A-2)
             * Uses bit-by-bit approach for MISRA-C:2012 compliance. */
 
            /* Append '111' prefix MSB-first: 1, 1, 1 */
            result = bitbuffer_append_bit(output, 1);
            if (result == CCSDS124_OK) {
                result = bitbuffer_append_bit(output, 1);
            }
            if (result == CCSDS124_OK) {
                result = bitbuffer_append_bit(output, 1);
            }
 
            if (result == CCSDS124_OK) {
                /* Calculate E = 2⌊log₂(A-2)+1⌋ - 6
                 * floor(log2(value)) = highest set bit = 31 - clz(value) */
                uint32_t value = A - 2U;
                int highest_bit = 31 - __builtin_clz(value);
                int E = (2 * (highest_bit + 1)) - 6;
 
                /* Append BIT_E(A-2) MSB-first - E bits from bit E-1 down to bit 0 */
                for (int i = E - 1; (i >= 0) && (result == CCSDS124_OK); i--) {
                    uint32_t shifted = value >> (uint32_t)i;
                    uint32_t masked = shifted & 1U;
                    int bit = (int)masked;
                    result = bitbuffer_append_bit(output, bit);
                }
            }
        }
    }
 
    return result;
}
 
 
int ccsds124_rle_encode(bitbuffer_t *output, const bitvector_t *input) {
    int result = CCSDS124_ERROR_INVALID_ARG;
 
    if ((output != NULL) && (input != NULL)) {
        /* DeBruijn lookup table for fast LSB finding (matches reference implementation) */
        static const uint32_t debruijn_lookup[32] = {
            1U, 2U, 29U, 3U, 30U, 15U, 25U, 4U, 31U, 23U, 21U, 16U,
            26U, 18U, 5U, 9U, 32U, 28U, 14U, 24U, 22U, 20U, 17U, 8U,
            27U, 13U, 19U, 7U, 12U, 6U, 11U, 10U
        };
 
        result = CCSDS124_OK;
 
        /* Start from the end of the vector */
        int old_bit_position = (int)input->length;
 
        /* Process words in reverse order (from high to low) */
        for (int word = (int)input->num_words - 1; (word >= 0) && (result == CCSDS124_OK); word--) {
            uint32_t word_data = input->data[word];
 
            /* Process all set bits in this word */
            while ((word_data != 0U) && (result == CCSDS124_OK)) {
                /* Isolate the LSB: x = change & -change */
                uint32_t lsb = word_data & (uint32_t)(-(int32_t)word_data);
 
                /* Find LSB position using DeBruijn sequence */
                uint32_t debruijn_index = (lsb * 0x077CB531U) >> 27U;
                int bit_position_in_word = (int)debruijn_lookup[debruijn_index];
 
                /* Count from the other side (reference line 754) */
                bit_position_in_word = 32 - bit_position_in_word;
 
                /* Calculate global bit position (reference line 756) */
                int new_bit_position = (word * 32) + bit_position_in_word;
 
                /* Calculate delta (number of zeros + 1) */
                int delta = old_bit_position - new_bit_position;
 
                /* Encode the count */
                result = ccsds124_count_encode(output, (uint32_t)delta);
 
                /* Update old position for next iteration */
                old_bit_position = new_bit_position;
 
                /* Clear the processed bit */
                word_data ^= lsb;
            }
        }
 
        /* Append terminator '10' MSB-first (bits: 1, 0) */
        if (result == CCSDS124_OK) {
            result = bitbuffer_append_bit(output, 1);
        }
        if (result == CCSDS124_OK) {
            result = bitbuffer_append_bit(output, 0);
        }
    }
 
    return result;
}
 
 
int ccsds124_bit_extract(bitbuffer_t *output, const bitvector_t *data, const bitvector_t *mask) {
    int result = CCSDS124_ERROR_INVALID_ARG;
 
    if ((output != NULL) && (data != NULL) && (mask != NULL)) {
        if (data->length != mask->length) {
            /* Length mismatch - result already set to INVALID_ARG */
        } else {
            /* DeBruijn lookup for fast LSB finding (same as RLE) */
            static const uint32_t debruijn_lookup[32] = {
                1U, 2U, 29U, 3U, 30U, 15U, 25U, 4U, 31U, 23U, 21U, 16U,
                26U, 18U, 5U, 9U, 32U, 28U, 14U, 24U, 22U, 20U, 17U, 8U,
                27U, 13U, 19U, 7U, 12U, 6U, 11U, 10U
            };
 
            result = CCSDS124_OK;
 
            /* Process words in REVERSE order (high to low) like RLE.
             * This gives bits from highest position to lowest, which is
             * the correct output order for BE (no reversal needed). */
            for (int word = (int)mask->num_words - 1; (word >= 0) && (result == CCSDS124_OK); word--) {
                uint32_t mask_word = mask->data[word];
                uint32_t data_word = data->data[word];
 
                while ((mask_word != 0U) && (result == CCSDS124_OK)) {
                    /* Isolate LSB */
                    uint32_t lsb = mask_word & (uint32_t)(-(int32_t)mask_word);
 
                    /* Find LSB position using DeBruijn */
                    uint32_t debruijn_index = (lsb * 0x077CB531U) >> 27U;
                    int bit_pos_in_word = 32 - (int)debruijn_lookup[debruijn_index];
 
                    /* Check if this bit is within the valid length */
                    int global_pos = (word * 32) + bit_pos_in_word;
                    if ((size_t)global_pos < data->length) {
                        /* Extract and output data bit directly */
                        int bit = 0;
                        if ((data_word & lsb) != 0U) {
                            bit = 1;
                        }
                        result = bitbuffer_append_bit(output, bit);
                    }
 
                    /* Clear processed bit */
                    mask_word ^= lsb;
                }
            }
        }
    }
 
    return result;
}
 
 
int ccsds124_bit_extract_forward(bitbuffer_t *output, const bitvector_t *data, const bitvector_t *mask) {
    int result = CCSDS124_ERROR_INVALID_ARG;
 
    if ((output != NULL) && (data != NULL) && (mask != NULL)) {
        if (data->length != mask->length) {
            /* Length mismatch - result already set to INVALID_ARG */
        } else {
            result = CCSDS124_OK;
 
            /* Process words in FORWARD order (low to high).
             * Within each word, find MSBs first using clz to get
             * bits from lowest position to highest. */
            for (size_t word = 0U; (word < mask->num_words) && (result == CCSDS124_OK); word++) {
                uint32_t mask_word = mask->data[word];
                uint32_t data_word = data->data[word];
 
                while ((mask_word != 0U) && (result == CCSDS124_OK)) {
                    /* Find MSB position using count leading zeros */
                    int clz = __builtin_clz(mask_word);
                    int bit_pos_in_word = clz;  /* Physical position from left */
 
                    /* MSB-first: physical position 0 = bit index 0 */
                    size_t global_pos = (word * 32U) + (size_t)bit_pos_in_word;
 
                    if (global_pos < data->length) {
                        /* Extract data bit at this position */
                        uint32_t bit_mask = 1U << (31U - (uint32_t)clz);
                        int bit = 0;
                        if ((data_word & bit_mask) != 0U) {
                            bit = 1;
                        }
                        result = bitbuffer_append_bit(output, bit);
                    }
 
                    /* Clear the MSB we just processed */
                    mask_word &= ~(1U << (31U - (uint32_t)clz));
                }
            }
        }
    }
 
    return result;
}