Improving speed of bit copying in a lossless audio encoding algorithm (written in C)

user_15199597 0
Viewed 95

I'm trying to implement a lossless audio codec that will be able to process data coming in at roughly 190 kHz to then be stored to an SD card using SPI DMA. I've found that the algorithm basically works, but has certain bottlenecks that I can't seem to overcome. I was hoping to get some advice on how to best optimize a certain portion of the code that I found to be the "slowest". I'm writing in C on a TI DSP and am using -O3 optimization.

        for (j = packet_to_write.bfp_bits; j>0; j--)
        {
            encoded_data[(filled/16)] |= ((buf_filt[i] >> (j- 1)) & 1) << (filled++ % 16);

        }

In this section of code, I am taking X number of bits from the original data and fitting it into a buffer of encoded data. I've found that the loop is fairly costly and when I am working with a set of data represented by 8+ bits, then this code is too slow for my application. Loop unrolling doesn't really work here since each block of data can be represented by a different number of bits. The "filled" variable represents a bit counter filling up Uint16 indices in the encoded_data buffer.

I'd like some help understanding where bottlenecks may come from in this snippet of code (and hopefully I can take those findings and apply that to other areas of the algo). The authors of the paper that I'm reading (whose algorithm I'm trying to replicate) noted that they used a mixture of C and assembly code, but I'm not sure how assembly would be useful in this case.

Finally, the code itself is functional and I have done some extensive testing on actual audio samples. It's just not fast enough for real-time!

Thanks!

texas-instruments bit-manipulation signal-processing assembly c
1 Answers

You really need to change the representation that you use for the output data. Instead of just a target buffer and the number of bits written, expand this to:

//complete words that have been written
uint16_t *encoded_data;

//number of complete words that have been written
unsigned filled_words;

//bits waiting to be written to encoded_data, LSB first
uint32_t encoded_bits;

//number of bits in encoded_bits
unsinged filled_bits;

This uses a single 32-bit word to buffer bits until we have enough to write out a complete uint16_t. This greatly simplifies the shifting and masking, because you always have at least 16 free bits to write into.

Then you can write out n bits of any source word like this:

void write_bits(uint16_t bits, unsigned n) {
    uint32_t mask = ((uint32_t)0x0FFFF) >> (16-n);
    encoded_bits |= (bits&mask) << filled_bits;
    filled_bits += n;
    if (filled_bits >= 16) {
        encoded_data[filled_words++] = (uint16_t)encoded_bits;
        encoded_bits >>= 16;
        filled_bits -= 16;
    }
}

and instead of your loop, you just write

write_bits(buf_filt[i], packet_to_write.bfp_bits);

No one-bit-at-a-time operations are required.

user_54835260
Related