Thread: Bits and bytes- Please help.

Originally Posted by quzah

The ordering didn't confuse me, the OP saying they wanted "first" when really they wanted "last" confused me.

Me too, but based on the examples it became obvious what the OP actually meant.

Originally Posted by laserlight

Me too, but based on the examples it became obvious what the OP actually meant.

Obvious if you haven't just woken up, sure.


Quzah.

Originally Posted by slingerland3g

but there was mention that the rest of the bits or bytes were to be summed up and added to the result, though not clear on what that was to achieve.

Are you referring to the explanations of how to use a smaller lookup table?

Originally Posted by quzah

Obvious if you haven't just woken up, sure.

Heh. I am going to sleep now.

Well, after running a few tests, it appears that the lookup table method is probably the fastest route (roughly 10 times faster than the bit-by-bit and ceil/log2 (I'm not sure if this could be optimized for integers, though) approaches).

Code:

int initialize_table( unsigned char table[ 256 ] )
{
    table[ 0 ] = 0;
    int
        min = 1;
    for( int i = min; i < 9; i++ )
    {
        int 
            max = 1 << i;
        for( int j = min; j < max; j++ )
        {
            table[ j ] = 9 - i;
        }
        min = max;
    }
}

/*
    Returns on interval [0 (error), 32 (LSB)]   
*/

int get_first_available_channel( unsigned channels )
{
    static unsigned char 
        table[ 256 ];
    static int 
        unused = initialize_table( table );
    int 
        index = table[ channels >> 24 ];
    if( index )
        return index;
    index = table[ ( channels >> 16 ) & 0xff ];
    if( index )
        return index + 8;
    index = table[ ( channels >> 8 ) & 0xff ];
    if( index )
        return index + 16;
    index = table[ channels & 0xff ];
    if( index )
        return index + 24;
    return 0;    
}

For the sake of simplicity I assumed 32 bit integers...

Originally Posted by slingerland3g

Lol, this discussion took all kinds of turns. The OP needed to know the first MSB set to decide on the lowest numbered channel available. I believe I am clear now, but there was mention that the rest of the bits or bytes were to be summed up and added to the result, though not clear on what that was to achieve.

That computing trailing zeros howto was real interesting.

What I meant was if suppose four bytes has the value say x'00558844'. So I will take the first byte(from the left), x'00'. Since it is zero I will add 8 to the result and now go with second byte x'55'. Use the lookup table suggested by LaserLight and add to the result. That would be the final.

There would be an exception.If all the bytes are 0, then no channel free.

This is why I thought to be the fastest, when compared to binary log.

Code:

int binlog(unsigned int n) {
  int res = 0;
  if (n >= 1<<16) { n >>= 16; res += 16; }
  if (n >= 1<< 8) { n >>=  8; res +=  8; }
  if (n >= 1<< 4) { n >>=  4; res +=  4; }
  if (n >= 1<< 2) { n >>=  2; res +=  2; }
  if (n >= 1<< 1) { res +=  1; }
  return  ((n == 0) ? (-1) : res);

subtract from 32 if the result is not -1

Code:

int log( unsigned int n )
{
    return n == 0   ?                         -1 :
        n     < 257 ?      LUT[  n      & 0xFF ] :
        n>>8  < 257 ?  8 + LUT[ (n>> 8) & 0xFF ] :
        n>>16 < 257 ? 16 + LUT[ (n>>16) & 0xFF ] :
                      24 + LUT[ (n>>24) & 0xFF ] ;
}

You'll always have a zero check. Beyond that:

Zero check.
Less than check.
Shift, less than.
Shift, less than.
Shift, add, AND, LUT.

Ten..damn I keep forgetting something...maximum operations? Should end up a few shorter than your last post.


Quzah.

>> IBTD

How so?

>> Ten..damn I keep forgetting something...maximum operations? Should end up a few shorter than your last post.

You could optimize out the two comparison shifts by replacing them with straight compares (ie: 0x10000 and 0x100000).

No optimizations, but after cleaning the code up somewhat the bit-by-bit approach was twice as fast as before, but still much slower than the lookup table. Here's a crude test program that should be easy to compile:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define array_size( array ) ( sizeof( array ) / sizeof( array[ 0 ] ) )

int initialize_table( unsigned char table[ 256 ] )
{
	table[ 0 ] = 0;
	int
		min = 1;
	for( int index = min; index < 9; index++ )
	{
		int 
			max = 1 << index;
		for( int j = min; j < max; j++ )
		{
			table[ j ] = 9 - index;
		}
		min = max;
	}
}

int get_first_available_channel_table_lookup( unsigned channels )
{
	static unsigned char 
		table[ 256 ];
	static int 
		unused = initialize_table( table );
	return 
		channels == 0 ? 0 
		: channels < 0x100 ? table[ channels & 0xff ] + 24
		: channels < 0x10000 ? table[ ( channels >> 8 ) & 0xff ] + 16
		: channels < 0x1000000 ? table[ ( channels >> 16 ) & 0xff ] + 8
		: table[ ( channels >> 24 ) & 0xff ];
}

int get_first_available_channel_ceil_log( unsigned channels )
{
	int
		index = ( int )ceil( log2( channels + 1 ) );
	return index ? 33 - index : 0;	
}

int get_first_available_channel_bit_by_bit( unsigned channels )
{   
	for( unsigned index = 1, mask = 0x80000000; mask; mask >>= 1, index++ )
	{
		if( channels & mask )
			return index;
	}		
	return 0;
}

typedef int ( * get_first_available_channel_function )( unsigned );

void test( unsigned* values, size_t length, const char* name, get_first_available_channel_function function, size_t repetitions )
{
	size_t
		iterations = repetitions * length;	
	unsigned
		* v, 
		* e = values + length;
	clock_t
		elapsed,
		stop,
		start = clock( );
	while( repetitions-- )
	{	
		v = values;
		while( v != e )
		{
			function( *v++ );
		}
	}	
	stop = clock( );
	elapsed = ( clock_t )( ( ( double ) ( stop - start ) / ( double )CLK_TCK ) * 1000 );
	printf( "%s : %d iterations performed in %d milliseconds\n", name, iterations, ( size_t )elapsed );
} 

int main( void ) 
{ 
	srand( time( 0 ) );
	unsigned
		data[ 256 ];
	size_t
		repetitions = 30000, 
		tests = 10;
	struct
	{
		char* 
			name;
		get_first_available_channel_function 
			function;
	}
		functions[ ] = 
	{
		{ "ceil_log", get_first_available_channel_ceil_log }, 
		{ "table_lookup", get_first_available_channel_table_lookup }, 
		{ "bit_by_bit", get_first_available_channel_bit_by_bit }		
	};
	while( tests-- )
	{	
		for( int index = 0; index < array_size( data ); ++index )
		{
			data[ index ] = rand( );
		}	
		for( int index = 0; index < array_size( functions ); ++index )
		{
			test( data, array_size( data ), functions[ index ].name, functions[ index ].function, repetitions );
		}
	}	
	return 0;
}

Originally Posted by Sebastiani

No optimizations, but after cleaning the code up somewhat the bit-by-bit approach was twice as fast as before, but still much slower than the lookup table.

Optimisations make sense when doing such a comparison, methinks. I think initialize_table() should return void, and you should change this in get_first_available_channel_table_lookup()'s implementation:

Code:

static int
    unused = initialize_table( table );

to:

Code:

static int
    unused = 1;
if( unused )
{
    initialize_table( table );
    unused = 0;
}

>> Optimisations make sense when doing such a comparison, methinks.

True, but since some compilers fare worse than others in optimizations I was just treating the comparison as "computational complexity" to address the general performance traits of the algorithms. But yes, optimizations could well change the numbers quite a bit (but I'm guessing they wouldn't "turn the tables" on the results, anyway).

>> I think initialize_table() should return void, and you should change this in get_first_available_channel_table_lookup()'s implementation:

It's just a kludge to deal with the fact that the language has no facilities for calling a function "statically". Maybe instead of returning an int it could return a dummy object (ie: 'class unused'), but other than that, I really don't see what's wrong with that method. On the other hand, the test-and-set approach is much less appealing, as it unnecessarily performs the test every invocation, and besides that just clutters the function. But I guess it's just a matter of taste.

Originally Posted by Sebastiani

It's just a kludge to deal with the fact that the language has no facilities for calling a function "statically". Maybe instead of returning an int it could return a dummy object (ie: 'class unused'), but other than that, I really don't see what's wrong with that method. On the other hand, the test-and-set approach is much less appealing, as it unnecessarily performs the test every invocation, and besides that just clutters the function. But I guess it's just a matter of taste.

The MinGW port of gcc 3.4.5 refused to compile your original code, reporting that the initialiser of the static variable was not constant.