Retrieving raw pointer from a bit_aligned image

typedef gil::detail::gray1_image_t image_t;
image_t img;
image_t::view_t v = view( img );
unsigned char* p = reinterpret_cast<unsigned char*>( &gil::at_c<0>( v( 0, 0 ) ));

Building the Boost Libraries

This blog entry mainly is a placeholder for me to quickly get the command lines for building boost on Windows for various configurations. For me, I’m interested in 32bit and 64bit code in debug and release configurations. For release config I define certain precompiler symbols ( _SECURE_SCL=0 and _HAS_ITERATOR_DEBUGGING=0 ) to generate fast c++ code.

Also, I like to build boost as fast as possible by using the “-j4” ( 4 cores ) option of the bjam tool.

Here we go. Since the command lines are a little long and might be cropped depending on your browser.

debug - 32bit
-------------
bjam -j4 --toolset=msvc --without-mpi variant=debug link=static runtime-link=shared define=_CRT_NONSTDC_NO_DEPRECATE define=_CRT_SECURE_NO_DEPRECATE define=_SCL_SECURE_NO_DEPRECATE stage

release - 32bit
---------------
bjam -j4 --toolset=msvc --without-mpi variant=release link=static runtime-link=shared define=_CRT_NONSTDC_NO_DEPRECATE define=_CRT_SECURE_NO_DEPRECATE define=_SCL_SECURE_NO_DEPRECATE define=_SECURE_SCL=0 define=_HAS_ITERATOR_DEBUGGING=0 stage

debug - 64bit
---------------
bjam -j4 --toolset=msvc --without-mpi variant=debug link=static runtime-link=shared address-model=64 define=_CRT_NONSTDC_NO_DEPRECATE define=_CRT_SECURE_NO_DEPRECATE define=_SCL_SECURE_NO_DEPRECATE stage

release - 64bit
----------------
bjam -j4 --toolset=msvc --without-mpi variant=release link=static runtime-link=shared address-model=64 define=_CRT_NONSTDC_NO_DEPRECATE define=_CRT_SECURE_NO_DEPRECATE define=_SCL_SECURE_NO_DEPRECATE define=_SECURE_SCL=0 define=_HAS_ITERATOR_DEBUGGING=0 stage

The libraries generated are static .lib files which work with Visual Studio’s auto-link feature.

Fastest way to read a file!

Ok ok, the subject is a little screamy and not entirely correct but I just came along a nice way to read in data file. Instead of reading the file at runtime why not just format the data and read it in at compile time, using the “#include” preprocessor command? Simple, but I just have never thought of it!

Here is what I mean.

int data[8] = {
#include "./data.txt"
};

When compiling with MSVC10 I have to have the “#include” statement at the beginning of a new line. Not sure if that’s needed for all c or c++ compilers.

Lambda Functions

I have just started using MSVC 10 this week and already toying with lambda functions. Here a very small example:

vector<float> out;
// fill vector 

ofstream out_file( "./result.txt" );
for_each( out.begin(), out.end()
        , [&out_file]( float f ) ->void { out_file << f << " "; });

All up to the third parameter of for_each should be familiar territory. The “[&out_file]” is passing a std::ofstream reference into the lambda function. “(float f)” is the parameter of this function and “->void” is the return type. “->void” can be omitted, I believe. Everything the “{” and “}” should be familiar grounds.

Another way to achieve the same effect is to use the “copy” algorithm with an ostream_iterator. Like this:

vector<float> out;
// fill vector 

ofstream out_file( "./result.txt" );
copy( out.begin(), out.end(), ostream_iterator<float>( out_file, " " ));

Addition: Instead of saying “[&out_file]” one could just say “[&]” which means that all variables passed into the lambda function are passed by reference.

Snapper Chain

Recently, I’m in an interviewing cycle for a new job. For this I find a useful to bang my head out on problems such like the Google Code Jam. The first problem in this year’s practice round is called Snapper Chain.

Before reading further I do suggest you read the problem description first.

It took me a while to come up with the right answer. I actually started to code the algorithm first before realize the real solution. Below you can see my first attempt which might be a correct solution but it has a time complexity of O(K), where K is the number of times snapping the finger. It can go up to 10^8 times. When running the code below with the large problem set it would take forever to finish.

#include <algorithm>
#include <cassert>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

enum snapper { no_power_off = 0
             , no_power_on  // = 1
             , power_off    // = 2
             , power_on     // = 3
             };

bool is_powered( snapper s ) { return ( s > no_power_on ); }
bool is_on( snapper s ) { return ( s == no_power_on || s == power_on ); }

bool all_on( const vector< snapper >& chain )
{
    for( size_t i = 0; i < chain.size(); ++i )
    {
        if( is_on( chain[i] ) == false || is_powered( chain[i] ) == false )
            return false;
    }

    return true;
}

void snap( vector< snapper >& chain )
{
    // loop through all devices and toggle their state if they are powered
    for( size_t i = 0 ; i < chain.size(); ++i )
    {
        if( is_powered( chain[i] ))
        {
            chain[i] = ( is_on( chain[i] )) ? power_off : power_on;
        }
    }

    // power of all snappers
    for( size_t i = 0 ; i < chain.size(); ++i )
    {
        chain[i] = ( is_on( chain[i] )) ? no_power_on : no_power_off;
    }

    // first snapper is always powered
    chain[0] = ( is_on( chain[0] )) ? power_on : power_off;

    // loop through all snappers and turn on when possible
    // start with second snapper
    for( size_t i = 1 ; i < chain.size(); ++i )
    {
        snapper& cur = chain[i];
        snapper prev = chain[i-1];

        if( is_powered( prev ) && is_on( prev ) )
        {
            cur = ( is_on( cur )) ? power_on : power_off;
        }
        else
        {
            // no other snapper can be powered
            break;
        }
    }
}

bool run( int n, int k )
{
    vector< snapper > chain( n );
    fill( chain.begin(), chain.end(), no_power_off );

    chain[0] = power_off;

    for( int i = 0; i < k; ++i )
    {
        snap( chain );
    }

    return all_on( chain );
}

int main(int argc, char* argv[])
{
    FILE* in;
    in = fopen( "../A-large-practice.in", "r" );

    ofstream out( "../large_results.txt" );

    if( in == NULL ) exit( 1 );

    int tasks = 0, n = 0, k = 0;
    fscanf( in, "%d", &tasks );

    for( int i = 1; i <= tasks; ++i )
    {
        fscanf( in, "%d %d", &n, &k );

        if( k == 0 )
        {
            out << "Case #" << i << ": " << "OFF" << endl;
        }
        else
        {
            bool t  = run( n, k );

            out << "Case #" << i << ": " << ( ( t == true ) ? "ON" : "OFF" ) << endl;
        }
    }

    fclose( in );

	return 0;
}

Clearly there must be a better solution hopefully with O(n) time complexity, where n is the number of snappers. N is bound to be 30 or less.

While reading the problem description over and over again I noticed the last sample, n=4 and k=47. Apparently, the light is on for this case. Converting the number 47 into binary code make it “0010 1111”. Mhmm, n=4 and there are four ones in the first half byte. Could it be when the number first bits set to 1 equals the number of snapper that the light is on? Good thing I had the my code above to “prove” my theory. Indeed, I was right and my next solution only depended on the number of snappers.

The upper half byte ( “0010” ) here refers to the number the light goes on. The first time it goes on is when snapping 15 times (k=15). The next times are when snapping 31 and 47 times, respectively.

n=4
k=15 – 0000 1111
k=31 – 0001 1111
k=47 – 0010 1111
k=63 – 0011 1111
etc…

bool run( int n, int k )
{
    int binary_N = 1;

    for( int i = 0; i < n - 1 ; ++i )
    {
        binary_N = binary_N << 1;
        binary_N = binary_N + 1;
    }

    if(( k & binary_N ) == binary_N )
    {
        return true;
    }

    return false;
}

int main(int argc, char* argv[])
{
    FILE* in;
    in = fopen( "../A-large-practice.in", "r" );

    ofstream out( "../large_results.txt" );

    if( in == NULL ) exit( 1 );

    int tasks = 0, n = 0, k = 0;
    fscanf( in, "%d", &tasks );

    for( int i = 1; i <= tasks; ++i )
    {
        fscanf( in, "%d %d", &n, &k );

        if( k == 0 )
        {
            out << "Case #" << i << ": " << "OFF" << endl;
        }
        else
        {
            bool t  = run( n, k );

            out << "Case #" << i << ": " << ( ( t == true ) ? "ON" : "OFF" ) << endl;
        }
    }

    fclose( in );

	return 0;
}

I have summited to my results to google and they are correct. Nice…

Until now I have not cheated nor taken a look at the provided analysis. Let’s see what the immortals came up with…

OK OK, after having read google’s analysis it’s more clear now why my solution is the right one. I’m not sure I get it completely but hopefully writing about will help me understanding.

With my own words the correct way of thinking here goes like this:

Take two binary numbers, p and q. p represents the on/off state of all snappers, whereas q represents the powered/unpowered state. Each number has as many bits as there are snappers. For now we assume it’s N=4.

The initial states are p = 0000 and q=0001. The first snapper ( read right to left ) is always powered. Now, two operations need to be accomplished for each snap.

1. Calculate the on/off situation for all snapper according to the last state. p_i = p_i-1 XOR q_i-1

2. After 1, update the powered/unpowered situation. q_i = foo( p_i ). The algorithm foo is going from right to left and determines if snapper at position i is powered based on the state of i-1. If snapper i-1 is ON and POWERED snapper i is powered as well.

Here a short run for n=4 and k=5

0: p0=0000 q0=0001
1: p1=0001 q1=0011 – the rightmost bit is both 1 for p_1 and q_0 meaning that the second snapper is powered.
2: p2=0010 q2=0001 – don’t forget to start with the rightmost bit and then make your way left
3: p3=0011 q3=0111
4: p4=0100 q4=0001

When p3 = 0011 the result for q3 is this: The snapper is always on.

q3 = 1

According to p3 the state of the first snapper is on. Now we know the second snapper is powered.

q3 = 11

Again, the second snapper is ON, too. See p3. above. Meaning the third snapper is powered.

q3 = 111

The third snapper is not in on state meaning we have determined q3 – 0111.

It’s easy to see that every p is p_i-1 + 1. p2 = p1 + 1.

The next step in understanding the solution is to realize that we can take a p and determine q from it’s bit pattern. For instance, take the the bit pattern p_i=10101111 then q_i must be q=00011111 since p_i+1 = p_i XOR q_i. p_i+1 MUST be p_i+1.

    10101111
XOR 00011111
    10110000

Here we can see the 5 rightmost bits in q are powered. Meaning if we only have 4 snappers they are all powered and though the light is.

Though, when N rightmost bits of K are 1 the light is ON.

Thanks for reading.

Retrieving a pointer to any_image buffer

Here a basic example:

int main(int argc, char *argv[])
{
    typedef boost::mpl::vector< gray8_image_t
                              , rgb8_image_t
                              >::type my_img_types;

    any_image< my_img_types > runtime_image;
    rgb8_image_t& img = runtime_image._dynamic_cast< rgb8_image_t >();

    unsigned char* data = interleaved_view_get_raw_data( view( img ) );
}

The variant class which any_image is derived from contains a _dynamic_cast member. This member can be used to retrieve the image type to then subsequently have access to the buffer using interleaved_view_get_raw_data.

Bit-Aligned Images

// Defining bit aligned images

// 1-bit black/white image
typedef bit_aligned_image1_type< 1, gray_layout_t >::type gray1_image_t;

// 4-bit gray image
typedef bit_aligned_image1_type< 4, gray_layout_t >::type gray4_image_t;

// 2-bits per channel rgb image
typedef bit_aligned_image3_type< 2, 2, 2, rgb_layout_t >::type rgb2_image_t;

// rgb332 image
typedef bit_aligned_image3_type< 3, 3, 2, rgb_layout_t >::type rgb332_image_t;


// Useful metafunctions

// Please note, for bit_aligned images we use view_t::reference type and 
// not view_t::value_type ( pixel_t ).

typedef gray1_image_t::view_t::reference  gray1_ref_t;
typedef gray4_image_t::view_t::reference  gray4_ref_t;
typedef rgb2_image_t::view_t::reference   rgb2_ref_t;
typedef rgb332_image_t::view_t::reference rgb332_ref_t;


// num_channels< Reference >
BOOST_STATIC_ASSERT( num_channels< gray1_ref_t  >::value == 1 );
BOOST_STATIC_ASSERT( num_channels< gray4_ref_t  >::value == 1 );
BOOST_STATIC_ASSERT( num_channels< rgb2_ref_t   >::value == 3 );
BOOST_STATIC_ASSERT( num_channels< rgb332_ref_t >::value == 3 );