Skip to main content
gamedev.net
🔒 Locked

Bit manipulation

Started by marshdabeachy Dec 14, 2008 at 8:19 PM 3 replies 1.3k views
Original Post
marshdabeachy
marshdabeachy
It's been a few years since I've done direct bit manipulation, so I'm trying to figure out the best way to go about this. I'm implementing a replay feature into a game with a fixed timestep. So I will effectively just be logging inputs, spawning, and the associated frame number, and feed the data back into the engine so it can recreate it. I'm keeping track of the frame number, the operation performed, and the data associated with the operation. Since the game could theoretically last for several hours, I need to compress the record keeping as much as possible, so I'm making ever bit count. With the frame counter, I figured I could fit about five hours into 20 bits (2^20 can hold quite a lot), so I'm sticking with that number. I have a total of 6 possible actions, so that's 3 more bits for the action. Data is associated with the action and thus varies, but it's anywhere from 1 to 15 extra bits. What I want to do is just stack this data end to end, and then break it apart later when I load the replay back up. Effectively, I don't want to waste a single bit. The problem I'm running into is breaking this up over multiple bytes. I've got 20 bytes for the frame number, and then I've got to stuff 3 more bits into that third byte after the 20th bit, and then a varying amount of data packed behind that... and then when the next action is logged, nothing's falling at the beginning of a byte anyway, so it's a big mess. Spreading data across two or more bytes gets complicated, especially when it doesn't start at the beginning of the byte. I'm rather fluent in C++'s bitwise operations but am not sure about the best way to go about getting this to work. Any tips?
KulSeran
KulSeran
Unless the amount of data currently in ram is an issue, you might just consider compressing the data after-the-fact. A good compression program will have an easier time working with your data if you don't play with the bits.

What you want is a bit writer class. For the most part you could just drop bits into a vector and then write that out (or if bool writes as 8bits or the like, you could hand pack each block of bools easier at this stage than sooner)
std::vector<bool> bitVectorfor ( int i = 0; i < 20; ++i ){   bitVector.push_back(frame & (1<<i));}for ( int i = 0; i < 2; ++i ){   bitVector.push_back(command & (1<<i));}for ( int i = 0; i < dataLen; ++i ){   bitVector.push_back(data & (1<<i));}

output bitVector to a file as is.
marshdabeachy
marshdabeachy
That looks like a much cleaner solution than anything I was attempting.

One thing I want to clarify... I tried stuffing 1 million bools into a vector to see what would happen to memory, and it barely made an impact. I take it that the vector specialization of bool only uses 1 bit instead of the normal 8? I'm going to be keeping track of a lot of bits.
Vorpy
Vorpy
vector is a bit weird. The standard actually states that it has to perform the optimization you mentioned, where the elements are individual bits. Since the time the standard was written, the people behind the standards have realized that this causes some problems because it isn't possible to get a reference to an individual bit and so vector fails to work in some places where standard containers are supposed to work. I'm not sure what its current status in the standards is. It's probably safe to use it as long as you don't try anything too fancy.
frob
frob
You should use the bitset class instead.

Although most major vendors support the vector specialization, many minor ones do not (check the documentation). Many provide ways to explicitly disable the specialization.



It is language issue #96. It is the oldest open issue. It was officially submitted as a language defect on 1998-10-07.


The language standard committee has had this on the chopping block for over ten years. It is (almost) ready to be deprecated and then removed from the standard.


There are two proposed classes to replace it: dynamic_bitset and bit_vector. I believe both are already available in the boost libraries.

What happens next depends on the standardization of those classes. It is assumed that before the 0x standard is finished up they will either deprecate the specialization or make the specialization an optional feature.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.