Strip parity bits in C from 8 bits of data followed by 1 parity bit

Question

I have a buffer of bits with 8 bits of data followed by 1 parity bit. This pattern repeats itself. The buffer is currently stored as an array of octets.

Example (p are parity bits):

0001 0001 p000 0100 0p00 0001 00p01 1100 ...

should become

0001 0001 0000 1000 0000 0100 0111 00 ...

Basically, I need to strip of every ninth bit to just obtain the data bits. How can I achieve this?

This is related to another question asked here sometime back.

This is on a 32 bit machine so the solution to the related question may not be applicable. The maximum possible number of bits is 45 i.e. 5 data octets

This is what I have tried so far. I have created a "boolean" array and added the bits into the array based on the the bitset of the octet. I then look at every ninth index of the array and through it away. Then move the remaining array down one index. Then I've got only the data bits left. I was thinking there may be better ways of doing this.

Answer 1

Your idea of having an array of bits is good. Just implement the array of bits by a 32-bit number (buffer).

To remove a bit from the middle of the buffer:

void remove_bit(uint32_t* buffer, int* occupancy, int pos)
{
    assert(*occupancy > 0);
    uint32_t high_half = *buffer >> pos >> 1;
    uint32_t low_half = *buffer << (32 - pos) >> (32 - pos);
    *buffer = high_half | low_half;
    --*occupancy;
}

To add a byte to the buffer:

void add_byte(uint32_t* buffer, int* occupancy, uint8_t byte)
{
    assert(*occupancy <= 24);
    *buffer = (*buffer << 8) | byte;
    *occupancy += 8;
}

To remove a byte from the buffer:

uint8_t remove_byte(uint32_t* buffer, int* occupancy)
{
    uint8_t result = *buffer >> (*occupancy - 8);
    assert(*occupancy >= 8);
    *occupancy -= 8;
    return result;
}

You will have to arrange the calls so that the buffer never overflows. For example:

buffer = 0;
occupancy = 0;
add_byte(buffer, occupancy, *input++);
add_byte(buffer, occupancy, *input++);
remove_bit(buffer, occupancy, 7);
*output++ = remove_byte(buffer, occupancy);
add_byte(buffer, occupancy, *input++);
remove_bit(buffer, occupancy, 6);
*output++ = remove_byte(buffer, occupancy);
... (there are only 6 input bytes, so this should be easy)

Answer 2

In pseudo-code (since you're not providing any proof you've tried something), I would probably do it like this, for simplicity:

• View the data (with parity bits included) as a stream of bits
• While there are bits left to read:
  • Read the next 8 bits
  • Write to the output
  • Read one more bit, and discard it

This "lifts you up" from worrying about reading bytes, which no longer is a useful operation since your bytes are interleaved with bits you want to discard.

Answer 3

I have written helper functions to read unaligned bit buffers (this was for AVC streams, see original source here). The code itself is GPL, I'm pasting interesting (modified) bits here.

typedef struct bit_buffer_ {
  uint8_t * start;
  size_t size;
  uint8_t * current;
  uint8_t read_bits;
} bit_buffer;

/* reads one bit and returns its value as a 8-bit integer */
uint8_t get_bit(bit_buffer * bb) {
  uint8_t ret;
  ret = (*(bb->current) >> (7 - bb->read_bits)) & 0x1;
  if (bb->read_bits == 7) {
      bb->read_bits = 0;
      bb->current++;
  }
  else {
      bb->read_bits++;
  }
  return ret;
}

/* reads up to 32 bits and returns the value as a 32-bit integer */
uint32_t get_bits(bit_buffer * bb, size_t nbits) {
  uint32_t i, ret;
  ret = 0;
  for (i = 0; i < nbits; i++) {
    ret = (ret << 1) + get_bit(bb);
  }
  return ret;
}

You can use the structure like this:

uint_8 * buffer;
size_t buffer_size;
/* assumes buffer points to your data */

bit_buffer bb;
bb.start = buffer;
bb.size = buffer_size;
bb.current = buffer;
bb.read_bits = 0;

uint32_t value = get_bits(&bb, 8);
uint8_t parity = get_bit(&bb);

uint32_t value2 = get_bits(&bb, 8);
uint8_t parity2 = get_bit(&bb);

/* etc */

I must stress that this code is quite perfectible, proper bound checking must be implemented, but it works fine in my use-case.

I leave it as an exercise to you to implement a proper bit buffer reader using this for inspiration.

Answer 4

This also works

void RemoveParity(unsigned char buffer[], int size)
{
    int offset = 0;
    int j = 0;

    for(int i = 1; i + j < size; i++)
    {
        if (offset == 0)
        {
            printf("%u\n", buffer[i + j - 1]);
        }
        else
        {
            unsigned char left = buffer[i + j - 1] << offset;
            unsigned char right = buffer[i + j] >> (8 - offset);
            printf("%u\n", (unsigned char)(left | right));
        }
        offset++;
        if (offset == 8)
        {
            offset = 0;
            j++; // advance buffer (8 parity bit consumed)
        }
    }
}