Shifting arrays of bytes and skipping bits

Question

I'm trying to make a function that would return N number of bits of a given memory chunk, and optionally skipping M bits.

Example:

unsigned char *data = malloc(3);
data[0] = 'A'; data[1] = 'B'; data[2] = 'C';
read(data, 8, 4);

would skip 12 bits and then read 8 bits from the data chunk "ABC".

"Skipping" bits means it would actually bitshift the entire array, carrying bits from the right to the left.

In this example ABC is

01000001 01000010 01000011

and the function would need to return

    0001 0100

This question is a follow up of my previous question

Minimal compilable code

#include <ios>
#include <cmath>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>

using namespace std;

typedef unsigned char byte;
typedef struct bit_data {
    byte *data;
    size_t length;
} bit_data;

/*
   Asume skip_n_bits will be 0 >= skip_n_bits <= 8
*/
bit_data *read(size_t n_bits, size_t skip_n_bits) {
    bit_data *bits = (bit_data *) malloc(sizeof(struct bit_data));

    size_t bytes_to_read = ceil(n_bits / 8.0);
    size_t bytes_to_read_with_skip = ceil(n_bits / 8.0) + ceil(skip_n_bits / 8.0);

    bits->data = (byte *) calloc(1, bytes_to_read);
    bits->length = n_bits;

    /* Hardcoded for the sake of this example*/
    byte *tmp = (byte *) malloc(3);
    tmp[0] = 'A'; tmp[1] = 'B'; tmp[2] = 'C';

    /*not working*/
    if(skip_n_bits > 0){
        unsigned char *tmp2 = (unsigned char *) calloc(1, bytes_to_read_with_skip);
        size_t i;

        for(i = bytes_to_read_with_skip - 1; i > 0; i--) {
            tmp2[i] = tmp[i] << skip_n_bits;
            tmp2[i - 1] = (tmp[i - 1] << skip_n_bits) | (tmp[i] >> (8 - skip_n_bits));
        }

        memcpy(bits->data, tmp2, bytes_to_read);
        free(tmp2);
    }else{
        memcpy(bits->data, tmp, bytes_to_read);
    }
    free(tmp);

    return bits;
}

int main(void) {
    //Reading "ABC"
    //01000001 01000010 01000011
    bit_data *res = read(8, 4);

    cout << bitset<8>(*res->data);
    cout << " -> Should be '00010100'";

    return 0;
}

The current code returns 00000000 instead of 00010100. I feel like the error is something small, but I'm missing it. Where is the problem?

Answer 1

Your code is tagged as C++, and indeed you're already using C++ constructs like bitset, however it's very C-like. The first thing to do I think would be to use more C++.

Turns out bitset is pretty flexible already. My approach would be to create one to store all the bits in our input data, and then grab a subset of that based on the number you wish to skip, and return the subset:

template<size_t N, size_t M, typename T = unsigned char>
std::bitset<N> read(size_t skip_n_bits, const std::array<T, M>& data)
{
    const size_t numBits = sizeof(T) * 8;

    std::bitset<N> toReturn; // initially all zeros

    // if we want to skip all bits, return all zeros
    if (M*numBits <= skip_n_bits)
        return toReturn;

    // create a bitset to store all the bits represented in our data array
    std::bitset<M*numBits> tmp;

    // set bits in tmp based on data
    // convert T into bit representations
    size_t pos = M*numBits-1;
    for (const T& element : data)
    {
        for (size_t i=0; i < numBits; ++i)
        {
            tmp.set(pos-i, (1 << (numBits - i-1)) & element);
        }
        pos -= numBits;
    }

    // grab just the bits we need
    size_t startBit = tmp.size()-skip_n_bits-1;
    for (size_t i = 0; i < N; ++i)
    {
        toReturn[N-i-1] = tmp[startBit];
        tmp <<= 1;
    }

    return toReturn;
}

Full working demo

And now we can call it like so:

// return 8-bit bitset, skip 12 bits
std::array<unsigned char, 3> data{{'A', 'B', 'C'}};
auto&& returned = read<8>(12, data);
std::cout << returned << std::endl;

Prints

00100100

which is precisely our input 01000001 01000010 01000011 skipping the first twelve bits (from the left towards the right), and only grabbing the next 8 available.

I'd argue this is a bit easier to read than what you've got, esp. from a C++ programmer's point of view.