Reading 12-bit words from 32-bit stream

Question

I have a device (ADC) that stores its samples in a 32-bit buffer and each sample is a 12-bit word :

I needed an algorithm to read those samples to a container (say std::vector<uint16_t>). So I started with the following reasoning (see the picture above):

1. The pattern consists of 3 32b-words
2. Any 12b-word is either entirely contained in one 32b-word or overlaps two conjugate ones. In other words any 12b-word depends only on two 32b-words (hereinafter - the current and next one)

So we have:

W = ((b[i] & m1) >> s1) | ((b[i+1] & m2) << s2)

where

b[i]   - i-th element of 32-bit buffer
m1, m2 - masks for the current and next 32-bit word, respectively
s1, s2 - shifts for the current and next 32-bit word, respectively

Of course, i, m1, s1, m2, s2 depend on the position of a 12b-word in the pattern so we will have 8 sets of them. Once we have those 8 sets the algorithm is straight-forward.

Code

twelveBit.h

//twelveBit.h
#include <array>
#include <vector>
#include <iostream>

struct Cfg
{
    bool overlap;  // Is the 2-nd 32-bit word used
    uint8_t s1;    // Shift in the 1-st 32-bit word
    uint8_t s2;    // Shift in the 2-nd 32-bit word
    uint32_t m1;   // Mask  in the 1-st 32-bit word
    uint32_t m2;   // Mask  in the 2-nd 32-bit word
    size_t n;      // Index of the 1-st 32-bit word *in the pattern* (i.e. 0, 1, or 2)

    constexpr
    Cfg( bool overlap,
         uint8_t s1, uint8_t s2,
         uint32_t m1, uint32_t m2,
         size_t n ) :
        overlap( overlap ),
        s1( s1 ), s2( s2 ),
        m1( m1 ), m2( m2 ),
        n( n )
    {}
};

class Reader
{
    private :
        static const std::array<Cfg, 8> cs;
        std::vector<uint16_t>     readWords;

    public :
        void Read12BitWords( const std::vector<uint32_t>& buffer );
        const std::vector<uint16_t>& GetReadWords() const { return readWords; }
};

twelveBit.cpp

#include "twelveBit.h"

const std::array<Cfg, 8> Reader::cs = { Cfg( false, 0,  0, 0x00000fff, 0x00000000, 0 ),
                                        Cfg( false, 12, 0, 0x00fff000, 0x00000000, 0 ),
                                        Cfg( true,  24, 8, 0xff000000, 0x0000000f, 0 ),
                                        Cfg( false, 4,  0, 0x0000fff0, 0x00000000, 1 ),
                                        Cfg( false, 16, 0, 0x0fff0000, 0x00000000, 1 ),
                                        Cfg( true,  28, 4, 0xf0000000, 0x000000ff, 1 ),
                                        Cfg( false, 8,  0, 0x000fff00, 0x00000000, 2 ),
                                        Cfg( false, 20, 0, 0xfff00000, 0x00000000, 2 ) };

void Reader::Read12BitWords( const std::vector<uint32_t>& buffer )
{
    readWords.clear();
    for( size_t i = 0; (i + 2) < buffer.size(); i += 3 )
    {
        // Read 8 12-bit words starting with the buffer index `i`
        for( size_t j = 0; j < cs.size(); ++j )
        {
            readWords.push_back(
                (                   (buffer[i + cs[j].n]     & cs[j].m1) >> cs[j].s1) |
                (cs[j].overlap ? (  (buffer[i + cs[j].n + 1] & cs[j].m2) << cs[j].s2) : 0)
            );
        }
    }
}

Usage

#include "twelveBit.h"

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <random>

#define RST  "\x1B[0m"
#define YLW  "\x1B[33m"
#define RED  "\x1B[31m"

int main()
{
    std::random_device rd;
    std::default_random_engine re( rd() );
    std::uniform_int_distribution<uint32_t> uniform( 0, 0xffffffff );

    constexpr size_t N = 5;
    std::vector<uint32_t> stream( N );
    std::generate( stream.begin(), stream.end(), [&](){ return uniform( re ); } );

    Reader r;                   //
    r.Read12BitWords( stream ); // <-- ACTUAL USAGE !!!
    auto rw = r.GetReadWords(); //
    auto rwc = rw;

    std::reverse( stream.begin(), stream.end() );
    for( auto v : stream )
    {
        std::cout << std::setfill('0') << std::setw(8) << std::hex << v;
    }
    std::cout << "\n";

    int color = 0;
    std::reverse( rwc.begin(), rwc.end() );
    for( auto it = rwc.cbegin(); it != rwc.cend(); ++it )
    {
        if( color++ % 2 ) { std::cout << YLW << std::setfill('0') << std::setw(3) << std::hex << *it << RST; }
        else              { std::cout << RED << std::setfill('0') << std::setw(3) << std::hex << *it << RST; }
    }
    std::cout << "\n";

    return 0;
}

P.S.

In my case, the size of the buffer is always a multiplier of 3, otherwise it is a sign that an error has occurred.

Answer 1

Overview:

I can't see anything wrong with this code on a read through it (I did not compile it).

All my comments are minor and just nit picky.
So the below is just a few things I would do differently (but I don't think your way is wrong).

Things I did not like in general are:

Way too much extra white space everywhere (this is the opposite of most people, where I complain about too little white space).

• After Open brace
• Before Close brace
• Before : (in private/public)

---

I believe that types like uint16_t are optionally in the global namespace (I could be wrong on that) when included via the C++ headers. So you should prefix them with std like this: std::uint16_t. But even if I was wrong about the optional bit, they are in the standard namespace and I would always be specific and include the prefix.

---

Naming conventions.

Most (and this is not universal) standards. Have user defined types begin with an initial capital letter like your Reader. But all functions and objects names begin with a lower case letter. This is invaluable in helping you identify the difference between a function call and creating an object, as the syntax is so similar.

   Cfg(1, 2, "etc")          // Is this an object or a function call
                             // Initial capital letter (so object).


   Read12BitWords("Stuff")   // I though that was an object maybe
                             // but actually a method call.
                             // PS. I know I cheated here as this is
                             // not the way you call it here, but in
                             // a larger piece of code a method call
                             // will not always need the object

Code Review

Do you really need <iostream> here?

//twelveBit.h
#include <iostream>

---

You don't need a constructor here. I forget the name of what it is called. But simply use the {<list of values>} and the compiler will build it.

struct Cfg
{
   // I would drop this:
     constexpr
    Cfg( bool overlap,
         uint8_t s1, uint8_t s2,
         uint32_t m1, uint32_t m2,
         size_t n ) :
        overlap( overlap ),
        s1( s1 ), s2( s2 ),
        m1( m1 ), m2( m2 ),
        n( n )
    {}
};

Code then looks simpler:

struct CfgV2
{
    bool overlap;  // Is the 2-nd 32-bit word used
    uint8_t s1;    // Shift in the 1-st 32-bit word
    uint8_t s2;    // Shift in the 2-nd 32-bit word
    uint32_t m1;   // Mask  in the 1-st 32-bit word
    uint32_t m2;   // Mask  in the 2-nd 32-bit word
    size_t n;      // Index of the 1-st 32-bit word *in the pattern* (i.e. 0, 1, or 2)
};

const std::array<CfgV2, 8> Reader::cs = { {false, 0,  0, 0x00000fff, 0x00000000, 0},
                                          {false, 12, 0, 0x00fff000, 0x00000000, 0},
                                          {true,  24, 8, 0xff000000, 0x0000000f, 0},
                                          {false, 4,  0, 0x0000fff0, 0x00000000, 1},
                                          {false, 16, 0, 0x0fff0000, 0x00000000, 1},
                                          {true,  28, 4, 0xf0000000, 0x000000ff, 1},
                                          {false, 8,  0, 0x000fff00, 0x00000000, 2},
                                          {false, 20, 0, 0xfff00000, 0x00000000, 2} };

---

The reader is the class I would redesign (not much). The reader should read but it does not need to store the vector. I would pass a reference to the destination vector as part of the constructor.

class Reader
{
    private :
        static const std::array<Cfg, 8> cs;
        std::vector<uint16_t>     readWords;

    public :
        void Read12BitWords( const std::vector<uint32_t>& buffer );
        const std::vector<uint16_t>& GetReadWords() const { return readWords; }
};

This is how I would design it:

class Reader
{
    private:
        static const std::array<Cfg, 8> cs;

        std::vector<uint16_t>&     data;

    public:
        Reader(std::vector<uint16_t>& data)
            : data(data)
        {}

        template<typename I>
        void read12BitWords(I begin, I end);
};

---

This is actually very clever. I like it.

// I would not pass a vector as input.
// I would pass in two iterators.
// That way the input can be a vector/list or even a stream
void Reader::Read12BitWords( const std::vector<uint32_t>& buffer )
{
    // Not sure if I would clear the buffer.
    // As mentioned above, I would pass the vector in as a parameter
    // to the constructor. So the vector does not belong to the reader
    // class but belongs to a higher level construct. It is the owner
    // of the vector that decides if it needs clearing or not the reader
    // would simply append data.
    readWords.clear();

    // Sure this is a good check.
    // But what happens if your input is not an exact multiple of 3?
    // In this case you are going to throw away either 1 or 2 32 bit
    // bytes and generate no error.
    for( size_t i = 0; (i + 2) < buffer.size(); i += 3 )
    {

        // I would change this to a range based for:
        //    for (auto const& cfg: cs)
        // This also slightly simplifies your push as no indexing
        for( size_t j = 0; j < cs.size(); ++j )
        {
            readWords.push_back(
                (                   (buffer[i + cs[j].n]     & cs[j].m1) >> cs[j].s1) |
                (cs[j].overlap ? (  (buffer[i + cs[j].n + 1] & cs[j].m2) << cs[j].s2) : 0)
            );
        }
    }
}

---

This is very terminal specific.
May work for you but not guaranteed. You should have a look at a package called ncurses (and that was 20 years ago there may be better now).

#define RST  "\x1B[0m"
#define YLW  "\x1B[33m"
#define RED  "\x1B[31m"

---

    // Note: Here you are making a copy of the vector.
    //       That may now be what you want when the vector is large.
    auto rw = r.GetReadWords();

    // Another copy.
    auto rwc = rw;

---

Prefer to use std::begin(stream) and std::end(stream)

    std::reverse( stream.begin(), stream.end() );

This allows you to change the type of stream and not worry to much about the actual type (you can change it to an array and it would still work).

---

    // You have used range based for in the previous loop
    // why go back to the old version of the for loop?    
    for( auto it = rwc.cbegin(); it != rwc.cend(); ++it )

---

main() is special. You don't need a return value.

    return 0;

Actually having a return value indicates there is a failure state that could happen and I should look through the rest of main to find the return that indicates an error.

Use return 0 to indicate there is no error only if there is a posibility that there is an error state being returned in another part of main. Don't return anything to indicate that your code never returns an error state.

Difference on usage:

This is your usage:

Reader r;                   //
r.Read12BitWords( stream ); // <-- ACTUAL USAGE !!!
auto rw = r.GetReadWords(); //
auto rwc = rw;

My usage would have looked like this:

std::vector<std::uint16_t>  data;
Reader                      reader(data);

reader.read12BitWords(std::begin(stream), std::end(stream));

Answer 2

It took me a while to figure out what is really going on here, because the explanation is either incomplete, incorrect, or both.

In fact, the 12-bit values are not being read in the order shown, are they? From what I can suss, the order is actually like this:

┌───────┬───────────┬───────────┐
│   3   │     2     │     1     │
├───┬───┴───────┬───┴───────┬───┤
│ 6 │     5     │     4     │ 3 │
├───┴───────┬───┴───────┬───┴───┤
│     8     │     7     │   6   │
└───────────┴───────────┴───────┘

Given that, I’d say your transform algorithm is wildly over-complicated. It actually looks like quite a simple transform:

1. Take the low 12 bits.
2. Shift right by 12 bits.
3. If there less than 12 bits left:
   1. Take as many bits as are left.
   2. Read the next 32 bits.
   3. Take as many bits needed from the low bits of that to get your 12 bits.
   4. Shift right by as many bits as you took.
4. If there is more data, go to 1.

And in code:

auto f(std::vector<std::uint32_t> const& data)
{
    constexpr auto bits_to_read  = 32;
    constexpr auto bits_to_write = 12;

    auto output = std::vector<std::uint16_t>{};

    auto next = data.begin();
    auto const end = data.end();

    auto input_word = std::uint32_t{};
    auto bits_left = 0;

    while (next != end and bits_left != 0)
    {
        // Case 1: No more bits left, so read the next input word.
        if (bits_left == 0)
        {
            input_word = *next++;
            bits_left = bits_to_read;
        }

        // Case 2: Enough bits left for a 12-bit read.
        if (bits_left >= bits_to_write)
        {
            output.push_back(std::uint16_t(0xFFFu & input_word));
            input_word >>= bits_to_write;
            bits_left -= bits_to_write;
        }
        // Case 3: Not enough bits left for a 12-bit read.
        else
        {
            if (next == end)
                throw std::runtime_error{"not enough input words"};

            // Helper function to compute masks:
            auto const mask_for_bits = [](auto bits)
            {
                switch (bits)
                {
                case 4:
                    return 0xFu; // rude!
                case 8:
                    return 0xFFu;
                // Don't need any more cases, though should add a default
                // just to be safe.
                default:
                    assert(not "should never get here");
                }

                // Or you could generalize:
                //      auto mask = 0;
                //      while (bits--)
                //          mask = (mask << 1) | 1;
                //      return mask;
                // Or do both.
            };

            // Write what we have so far.
            output.push_back(std::uint16_t(mask_for_bits(bits_left) & input_word));

            // Get the next 32-bit input word.
            input_word = *next++;

            // Get the bits needed from the input word, shift them to the
            // right place, and OR them with what we have so far.
            auto const bits_needed = bits_to_write - bits_left;
            output.back() |= (input_word & mask_for_bits(bits_needed)) << bits_left;

            // Shift the input word to remove the bits we just used, and
            // update the count of bits left.
            input_word >>= bits_needed;
            bits_left = bits_to_write - bits_needed;
        }
    }

    return output;
}

Obviously not tested or anything.

Note that the function above is almost perfectly generalized. If you read in a different amount of bits than 32 in each input chunk, or if you want to output something other than 12 bit chunks, you can change those constants. And the guts of the function is based on iterators, which means it could work with anything, not just vectors.

That brings me to main point of my review, which is that it makes no sense for this to be a class. This is clearly a job for a function.

When I look at the usage:

    Reader r;                   //
    r.Read12BitWords( stream ); // <-- ACTUAL USAGE !!!
    auto rw = r.GetReadWords(); //

That’s just appalling. Three lines to do a simple transform?

(I’m not thrilled with @Martin York’s improvement either:

std::vector<std::uint16_t>  data;
Reader                      reader(data);

reader.read12BitWords(std::begin(stream), std::end(stream));

Much better, but still far from good.)

Here’s what I’d like to see:

transform_32bit_words_to_12bit_words(data, output);

where output is whatever you want to put the output into. Want it in a vector? Then:

auto rw = std::vector<std::uint16_t>{};
transform_32bit_words_to_12bit_words(data, std::back_inserter{rw});

// Or, to avoid repeated allocations:
auto rw = std::vector<std::uint16_t>((data.size() / 3 ) * 4);
transform_32bit_words_to_12bit_words(data, rw.begin());

The name transform_32bit_words_to_12bit_words is open for bike-shedding. The point is that when designing an interface for whatever it is you’re trying to do, you should make it as ergonomic as possible.

Here’s an example of the interface I might make for this function:

template <typename I, typename O>
struct transform_32bit_words_to_12bit_words_result
{
    [[no_unique_address]] I in;
    [[no_unique_address]] O out;
    [[no_unique_address]] std::size_t bits_remaining;

    constexpr auto complete() const noexcept { return bits_remaining == 0; }
};

template <std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O>
    requires unsigned_integer_with_minimum_bit_size<std::ranges::iter_value_t<I>, 32>
constexpr auto transform_32bit_words_to_12bit_words(I first, S last, O out) -> transform_32bit_words_to_12bit_words_result<I, O>;

template <std::ranges::input_range R, std::weakly_incrementable O>
    requires unsigned_integer_with_minimum_bit_size<std::ranges::range_value_t<R>, 32>
constexpr auto transform_32bit_words_to_12bit_words(R&& range, O out) -> transform_32bit_words_to_12bit_words_result<std::ranges::borrowed_iterator_t<R>, O>;

bits_remaining != 0 would indicate a partial read. So, you could do:

if (transform_32bit_words_to_12bit_words(data, out).complete())
    // a perfect read
else
    // report a partial read error

The unsigned_integer_with_minimum_bit_size<T, N> concept should be self-explanatory. You should probably also constrain the output iterator, but that’s too much to think about for now.

Hell, I might even go the whole hog and make it all completely generic:

template <typename I, typename O>
struct transform_words_result
{
    [[no_unique_address]] I in;
    [[no_unique_address]] O out;
    [[no_unique_address]] std::size_t bits_remaining;

    constexpr auto complete() const noexcept { return bits_remaining == 0; }
};

template <
    std::size_t InputWordSize,
    std::size_t OutputWordSize,
    std::input_iterator I,
    std::sentinel_for<I> S,
    std::weakly_incrementable O
>
    requires valid_word_size<InputWordSize>
        and valid_word_size<OutputWordSize>
        and unsigned_integer_with_minimum_bit_size<std::ranges::iter_value_t<I>, InputWordSize>
constexpr auto transform_words(I first, S last, O out) -> transform_words_result<I, O>
{

    using output_type = /* you'll need something to figure this out */;

    auto const mask_for_bits = [](auto bits)
    {
        auto mask = std::ranges::iter_value_t<I>(0);
        while (bits--)
            mask = (mask << 1) | 1;
        return mask;
    };

    auto input_word = std::ranges::iter_value_t<I>{};
    auto bits_left = std::size_t(0);

    while (first != end and bits_left != 0)
    {
        // Case 1: No more bits left, so read the next input word.
        if (bits_left == 0)
        {
            input_word = *first++;
            bits_left = InputWordSize;
        }

        // Case 2: Enough bits left for a read.
        if (bits_left >= OutputWordSize)
        {
            *out++ = output_type(mask_for_bits(OutputWordSize) & input_word);
            input_word >>= OutputWordSize;
            bits_left -= OutputWordSize;
        }
        // Case 3: Not enough bits left for a read.
        else
        {
            if (first == end)
                break;

            // Write what we have so far.
            auto current = output_type(mask_for_bits(bits_left) & input_word);

            // Get the next input word.
            input_word = *first++;

            // Get the bits needed from the input word, shift them to the
            // right place, and OR them with what we have so far.
            auto const bits_needed = OutputWordSize - bits_left;
            current |= (input_word & mask_for_bits(bits_needed)) << bits_left;

            // Shift the input word to remove the bits we just used, and
            // update the count of bits left.
            input_word >>= bits_needed;
            bits_left = OutputWordSize - bits_needed;

            // Write the value.
            *out++ = current;
        }
    }

    return { first, out, bits_left };
}

template <
    std::size_t InputWordSize,
    std::size_t OutputWordSize,
    std::ranges::input_range R,
    std::weakly_incrementable O
>
    requires valid_word_size<InputWordSize>
        and valid_word_size<OutputWordSize>
        and unsigned_integer_with_minimum_bit_size<std::ranges::range_value_t<R>, 32>
constexpr auto transform_words(R&& range, O out) -> transform_words_result<std::ranges::borrowed_iterator_t<R>, O>
{
    return transform_words<InputWordSize, OutputWordSize>(std::ranges::begin(range), std::ranges::end(range), out);
}

Usage:

transform_words<32, 16>(data, output);

I might also add a second function, maybe called transform_words_size that doesn’t actually do the transform, but rather just computes how many words will be read/written. That will allow you to pre-allocate, or at least know how many outputs will happen. But that’s a bit dodgy, because if you’re not careful, a clumsy user might try to use the size function and then the actual transform function on an input range… which won’t work (you only get a single pass over an input range).

Another, interesting interface option is: instead of an algorithm, make a custom view. Unfortunately, it isn’t possible yet to make custom views (we’ll need C++23 for that, or you can use ranges-v3), but to give a taste of how that might look:

for (auto&& value : data | transform_words_view<32, 16>)
    std::cout << value;

Or with a more complex example:

// Clip the transformed data, and invert it:
using namespace std::ranges::views;

auto const clip = [](auto v) { return std::min(v, 100); }
auto const invert = [](auto v) { return 0xFFFu - v; }

for (auto&& value : data | transform_words_view<32, 16> | views::filter(clip) | views::transform(invert))
    std::cout << value;

Yet another option is a coroutine generator. You could technically implement that today… but I’d wait until we get a pre-made generator interface in the standard library.

Any of these options are both easier to use, and more flexible than a class that requires two member function calls and an external vector. And most will probably be substantially more efficient even in the same usage scenario (that is, reading from a vector<uint32_t>, writing to a vector<uint16_t>).