Back to General and Gameplay Programming

required bit count at compile time

General and Gameplay Programming Programming

Started by zfvesoljc February 28, 2012 03:05 PM

9 comments, last by Ectara 12 years, 1 month ago

zfvesoljc

605

Author

February 28, 2012 03:05 PM

I'm saving enum values to bit stream, and I would like to use only such number of bits as really required.



enum EMessage {

	mOne = 0,

	mTwo,

	mThree,

	...

	mTen,

	//

	mLast,	 // value 10

};

In the above example, the last entry has value of 10, meaning I need at least 4 bits to write it (assuming only positive values). I can calculate this value in runtime via a function, but it would a bit nicer to have this value at compile time so I could do this:



enum EMessage {

	mOne = 0,

	mTwo,

	mThree,

	...

	mTen,

	//

	mLast,	 // value 10

	cbcMessage = Func( mLast ),

};

where cbcMessage would be "constant" bit count value (in this case 4).

Any ideas?

Telastyn

3,778

February 28, 2012 03:26 PM

I'm saving enum values to bit stream, and I would like to use only such number of bits as really required.

Any ideas?

Quit wasting your time on the triviality and work on making more/better code. Realistically you're likely to add more enum values over time; leave room for them.

-- Tangent Developer Journal - Delegates - Part 2

zfvesoljc

605

Author

February 28, 2012 04:21 PM

Quit wasting your time on the triviality and work on making more/better code. Realistically you're likely to add more enum values over time; leave room for them.

I asked a specific question, trivial or not. And I can waste my time any way I want.

vNeeki

194

February 28, 2012 04:23 PM

HDD/RAM space is not a problem these days but you could use one bit flag to tell whether to read a full byte or 4bits.

zfvesoljc

605

Author

February 28, 2012 04:52 PM

HDD/RAM space is not a problem these days

Who said anything about storage? Believe it or not, there are still some parts of the world where network bandwidth is not abundant.

but you could use one bit flag to tell whether to read a full byte or 4bits

I'm not sure how this would help me. I want to save minimum number of bits required. It could be 2, 4, 7 or even 23. I just wanted to know, if anybody had a quick idea how to get number of minimum bits required based on some max value (at compile time).

Telastyn

3,778

February 28, 2012 05:32 PM

Set a constant with the correct number. There is (to my knowledge) no great way to do that programmatically. There is likely template black magic, but I don't know of any offhand. You can parse out the file and do code generation, but that sucks.

-- Tangent Developer Journal - Delegates - Part 2

Brother Bob

10,350

February 28, 2012 05:55 PM

A very trivial way to get the number of necessary bits to store a value at compile time:
[source]
template<unsigned int N> struct number_of_bits
{
static const unsigned int value = 1 + number_of_bits<(N >> 1)>::value;
};

template<> struct number_of_bits<0>
{
static const unsigned int value = 0;
};
[/source]
Use:
[source]
int bits = number_of_bits<42>::value;
[/source]
It's not very generic or error-safe, but it works under normal circumstances at least. Add whatever error-checking you feel is necessary, or modify to suite you needs.

vNeeki

194

February 28, 2012 06:08 PM

[quote name='vNeeki' timestamp='1330446235' post='4917415']
HDD/RAM space is not a problem these days

Who said anything about storage? Believe it or not, there are still some parts of the world where network bandwidth is not abundant.

but you could use one bit flag to tell whether to read a full byte or 4bits



struct Value

{

	int val;

	int bits;

};



static const Values[16] =

{

	{0,1},

	{1,1},

	{2,2},

	{3,2},

	{4,3},

	{5,3},

	{6,3},

	{7,3},

	{8,4},

	{9,4},

	{10,4},

	{11,4},

	{12,4},

	{13,4},

	{14,4},

	{15,4},

};



void MyWriter::WriteByte(unsigned char Byte)

{

	if(Byte < 16)  

	{

		WriteBit(1);

		WriteBits(Values[Byte].value,Values[Byte].bits);

	}

	else

	{

		WriteBit(0);

		WriteBits(Byte,8);

	}

}



void MyWriter::WriteWord(unsigned short Word)

{

	WriteByte(Word >> 8);

	WriteByte(Word & 0xFF);

}

Antheus

2,410

February 28, 2012 07:04 PM

I just wanted to know, if anybody had a quick idea how to get number of minimum bits required based on some max value (at compile time).[/quote]

Number of bits required to represent n unique values is definition of entropy, which is log2(n). Template solution above should do the trick.

Above result will be rounded to an integer, but for compression one can achieve fractional number of bits.

It may be more efficient to simply write bytes and them compress them with Huffman or arithmetic coding.

zfvesoljc

605

Author

February 29, 2012 10:50 AM

A very trivial way to get the number of necessary bits to store a value at compile time:
[source]
template<unsigned int N> struct number_of_bits
{
static const unsigned int value = 1 + number_of_bits<(N >> 1)>::value;
};

template<> struct number_of_bits<0>
{
static const unsigned int value = 0;
};
[/source]
Use:
[source]
int bits = number_of_bits<42>::value;
[/source]
It's not very generic or error-safe, but it works under normal circumstances at least. Add whatever error-checking you feel is necessary, or modify to suite you needs.

Thank you!

required bit count at compile time

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

required bit count at compile time

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines