Archived

This topic is now archived and is closed to further replies.

Yohomyth

boolean compression (c++)

Recommended Posts

Something i noticed on my copy of visual c++ is that booleans take up a whole byte of memory (they should only be 1 bit). And enumerators always seemed to take up 4 bytes (?????). I have thought of a solution. Here is a piece of code you can use to minimize memory used by true/false variables (sorry, i''m doin this from memory so i maght make a mistake). //just to let you know: //i put p_ before parameter id //and t_ before temporary id #include <stdlib.h> //not sure which header #include <math.h> #define BYTE unsigned __int8 bool SetBit(BYTE *p_target, int p_byte, bool p_value) { //disassemble the byte bool t_bits[8]; for(int r = 0; r < 8; r++) if(*p_target >= pow(2,8-r)) { t_bits[r] = true; *p_target -= pow(2,8-r); } //set the value t_bits[p_byte] = p_value; //assemble the byte for(int r = 0; r < 8; r++) if(t_bits[r]) *p_target += pow(2,8-r); //return if necessary return p_value; } bool GetBit(BYTE *p_source, int p_byte) { //disassemble the byte bool t_bits[8]; BYTE t_source = *p_source; for(int r = 0; r < 8; r++) if(t_source >= pow(2,8-r)) { t_bits[r] = true; t_source -= pow(2,8-r); } //return the value return t_bits[p_byte]; } bool ToggleBit(BYTE *p_target, int p_byte) { //find out the origonal value... bool t_bit = GetBit(p_target,p_byte); //...toggle it... if(t_bit) SetBit(p_target,p_byte,false); else SetBit(p_target,p_byte,true); //...and return if necessary return (!t_bit); } I hope this is of use. I might have made some mistakes though. And i''m building a site for some misc. c++ code with [tested] stuff like this. When i''m finished it will be http://cppcode.yohomyth.com . "Solutions are not the answer." - Richard Nixon

Share this post


Link to post
Share on other sites
this is not worth the trouble, saving 7 bits isn''t worth the extra processing to do this. if you really want it, use flags/bitfields instead. if you insist, ffs at least use bit shifting, not pow.

Share this post


Link to post
Share on other sites
I thought if you put bools in a structure there was a keyword (packed? dunno it in C++) that removed all the padding (i.e. a struct with 3 bools would be 3 bits long). And there was another that bunched them together, but still aligned on byte boundaries. Surely that would be quicker than the flags method. (though flags still have merit in that you can test multiple bools at once, etc).

Share this post


Link to post
Share on other sites
I found a little VB function which read-wrote bits using boolean logic and a byte array (in vb6)
Private BitField() As Byte

Private Function GetBool(N As Long) As Boolean
If (BitField(N \ 8) And 2 ^ (N - ((N \ 8) * 8))) = 2 ^ (N - ((N \ 8) * 8)) Then GetBool = True
End Function

Private Sub SetBool(N As Long, Val As Boolean)
If Val = True Then
BitField(N \ 8) = BitField(N \ 8) Or 2 ^ (N - ((N \ 8) * 8))
Else
BitField(N \ 8) = BitField(N \ 8) Xor 2 ^ (N - ((N \ 8) * 8))
End If
End Sub
Public Sub resizebytes(nnum As Long)
ReDim Preserve BitField(nnum)
End Sub
Public Function sizeofbytes()
sizeofbytes = UBound(BitField)
End Function
Public Sub wipebytes()
ReDim BitField(0)
BitField(0) = 0
End Sub

Share this post


Link to post
Share on other sites
quote:
Original post by sadwanmage
I thought if you put bools in a structure there was a keyword (packed? dunno it in C++) that removed all the padding (i.e. a struct with 3 bools would be 3 bits long). And there was another that bunched them together, but still aligned on byte boundaries. Surely that would be quicker than the flags method. (though flags still have merit in that you can test multiple bools at once, etc).


you''re talking about bitfields? something like

bool IsEnabled :1;
bool IsVisible :1;
bool IsDead :1;
bool IsInvisible :1;
bool IsUndestructible:1;
bool IsDamaged :1;
bool HasWeapon :1;
bool FiredWeapon :1;

bitfields are quite useful, you can do stuff like


short IsDead :1;
short IsVisible :1;
short Health :8;
short Transparency:4;



and you can also bind them to a single variable, to be able to pass the ''structure'' to functions and the like


class CPlayer
{
union
{
short m_Flags;

struct
{
short m_IsDead :1;
short m_IsVisible :1;
short m_Health :8;
short m_Transparency:4;
};
};

public:
void SetFlags(short Flags)
{
m_Flags = Flags;
}

bool IsDead () const { return (bool) m_IsDead; }
bool IsVisible () const { return (bool) m_IsDead; }
int GetHealth () const { return (int) m_Health; }
int GetTransparency() const { return (int) m_Transparency; }

};



they are a bit OTT on most cases, except when you need to reduce the space to a minimum (networking would be an obvious candidate).

Share this post


Link to post
Share on other sites
Your functions become much simpler if you use bitwise operators:

BYTE data;

//SetBit true

data |= (1<<bit);
//SetBit false

data &= ~(1<<bit);

//GetBit

(bool)(data&(1<<bit))




[edited by - frankd on January 25, 2004 8:57:24 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
by doing this, you''re essentially trading speed for space... and well, unless you have ALOT of booleans, it''s not going to be worth it.

the reasons booleans are ''1 byte'' is because that''s the smallest amount of space you can address on your target platform.

btw, nearly everyone knows about this ''space optimization'', and have implemented it much less naively (no offense).

a common idiom of this ''optimization'' in C++ is simply ..

char const FLAG_1 = 0x01;
char const FLAG_2 = 0x02;
char const FLAG_3 = 0x04;

char flags = 0;

flags |= FLAG_3; //set flag_3.
flags |= FLAG_1; //set flag_1

if(flags & FLAG_3) do_something(); //if flag_3 is set




Share this post


Link to post
Share on other sites
This really doesn''t cost very much at all; it''s just a few bitwise operations, so it''s really fast (if done w/o function calls, etc). It''s usually not really necessary, but it really doesn''t hurt much.

There ARE some places where it actually makesd a lot of sense: Large voxel datasets representing solid objects, for example.

This trick will also make copying a given set of data 8x faster.

Share this post


Link to post
Share on other sites