Looking for a more efficient bitfield decode algorithm

Question

I have a Visual Studio 2008 C++ application where I receive a bit map (not an image). Each bit that is flipped corresponds to a position on a decode map.

typedef unsigned char BYTE;
const unsigned int COL_COUNT = 8;
const unsigned int ROW_COUNT = 4;

static char g_decode_map[ ROW_COUNT ][ COL_COUNT ] = 
{
    { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h' },
    { 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p' },
    { 'q', 'r', 's', 't', 'u', 'v', 'w', 'x' },
    { 'y', 'z', ',', '.', ' ', ':', '-', '+' }
};

// current implementation
void Decode( const BYTE bitmap[ ROW_COUNT ], 
             const char decode_map[ ROW_COUNT ][ COL_COUNT ], 
             char decoded[ ROW_COUNT * COL_COUNT ] )
{
    int found = 0;
    for( int i = 0; i < ROW_COUNT; ++i )
    {
        for( int j = 0; j < COL_COUNT; ++j )
        {
            if( std::bitset< COL_COUNT >( bitmap[ i ] ).test( j ) )
            {
                decoded[ found++ ] = g_decode_map[ i ][ COL_COUNT - j - 1 ];
            }
        }
    }
}

int main( int argc, char* argv[] )
{
    BYTE bitmap[ ROW_COUNT ] = { 0x01, 0x80, 0x00, 0x00 };
    // expected output { 'h', 'i' } or { 'i', 'h' } order is unimportant

    char decoded[ ROW_COUNT * COL_COUNT + 1 ] = { };
    Decode( bitmap, g_decode_map, decoded );
    printf( "Decoded: %s\r\n", decoded );
    return 0;
}

My current decode implementation works fine, but it strikes me that there may be a more efficient way of doing this. Can anybody suggest a more performant algorithm?

score 1 · Accepted Answer · answered Apr 29 '12 at 05:33

It would be faster to test whether or not each bit is set with bitwise operations as opposed to creating a bitset for each bit that is tested. Try something like this:

for( int i = 0; i < ROW_COUNT; ++i ) {
    for( int j = 0; j < COL_COUNT; ++j ) {
        if(bitmap[i] & (1 << j)) {
            ...

1 << j produces a mask that only has the bit you are wanting to test set. Bitwise anding the mask with your bitmap byte returns true only if that bit is set in bitmap[i]. The result of this conditional should be equivalent to the result of your conditional, and it should be a lot faster.

score 1 · Answer 2 · edited May 23 '17 at 12:21

You're doing 64 conditional checks. 32 in the for loops, and 32 inside the for loop. If you cannot get rid of the 32 inside the for loop, the best you can do is loop unrolling to reduce the number of conditional statements being executed by the forloops. With the row and column length being defined as constants. You can unroll the loops and hardcode some of the numbers for the indices. Instead of having the inner for loop, you could write 8 if statements like below.

This leave the question, what if someone changes the constant values? Then the code breaks. That is correct. If you need it to be robust enough to withstand that, you can use compile time recursion to unroll the loops(links below). Also, anyone who looks at your code will cower in fear and think you're a god. :P Also, Jason's solution would speed things up a bit too.

if( std::bitset< COL_COUNT >( bitmap[ i ] ).test( 0 ) )  
if( std::bitset< COL_COUNT >( bitmap[ i ] ).test( 1 ) )  
if( std::bitset< COL_COUNT >( bitmap[ i ] ).test( 2 ) )  
if( std::bitset< COL_COUNT >( bitmap[ i ] ).test( 3 ) )  
...
if( std::bitset< COL_COUNT >( bitmap[ i ] ).test( 7 ) )

Compile Time Loops(Answer #1)
Template Meta Programming

COL_COUNT probably can't change (8 bits to a byte). But ROW_COUNT can change at compile time. — PaulH, Apr 29 '12 at 17:02
If you were to try doing a compile time loop, you'll have to use an array of bytes and pass it to the function by reference — JustinDanielson, Apr 29 '12 at 19:16

score 0 · Answer 3 · answered Apr 29 '12 at 08:01

This is how to do it fast, assuming COL_COUNT == 8 (to do it really fast, use the in-line assembler):

for( int i = 0; i < ROW_COUNT; ++i )
    {
        unsigned char next_byte = bitmap[i] ;
        for( int j = 0; j < COL_COUNT; ++j )
        {
            if (next_byte & 0x80)
            {
                decoded[ found++ ] = g_decode_map[ i ][ j ];
            }
            next_byte <<= 1 ;
        }
    }

I have coded it to reproduce the behaviour of your program -- but are you sure you have it right? I would expect you to increment found every time, not just when a 1-bit is found.

Yes, I only want to populate the decode with the values from the decode array that have their bits turned on. — PaulH, Apr 29 '12 at 17:00

Looking for a more efficient bitfield decode algorithm

3 Answers3