required bit count at compile time

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.

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.

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.

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).

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.

A very trivial way to get the number of necessary bits to store a value at compile time:
[source]
template 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.

[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

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).
[/quote]


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);
}


D:

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.

A very trivial way to get the number of necessary bits to store a value at compile time:
[source]
template 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!

While I agree with the above posters, that this is something trivial to be concerned with, and one should write the full message and then compress later, what if he is writing a compression algorithm? Writing the data uncompressed and then using another algorithm would defeat the purpose. I don't usually try to pack every little data field, but I don't know what exactly he is writing. When I store something in memory like an image that is loaded as a placeholder, I write an algorithm that takes the smallest space and decompresses the fastest. Using a high-powered compression type might have too much overhead. Imagery is just about the only time I would pack data, such as pixels, into limited bit counts by hand.

To be relevant to the conversation, I'd wonder how necessary this is. This would have a decent speed hit if this is being used enough to have a significant impact. I'm sure that if you packed everything into minimum bit amounts, then you won't achieve as much compression as a more conventional compression method; and after this microcompression, if you were to compress this and other data together, this compressed data probably wouldn't dictionary well for, say, Huffman compression. Choosing the first idea that comes to mind might be shooting yourself in the foot.

For instance, what data can you avoid sending instead? Left 4 Dead sent the Y coordinates of actors only when it changed; otherwise, it was superfluous, and could be assumed to be the same. Afterwards, it was Huffman compressed, of course. Some data, like normalized math units, can calculate the missing part from the others. Perhaps there is something you could leave out or calculate upon receiving that would make up for the bits wasted? Calculating it would be faster than unpacking all of the data.

And if you absolutely must pack bits, I'd suggest aligning and packing powers of two. It will get really slow and hairy really quickly if you need to take some bits from one byte, and some bits from another, and putting them together, and keeping track of which byte is being read, and its bit offset, and how much to shift to put it together. Squeezing out that last bit or two is most likely by far not worth it. Saving a factor of two, four, or eight is significant; a factor of 4.3 is not worth the effort.