🔒 Locked

boolean compression (c++)

Started by Yohomyth Jan 24, 2004 at 8:34 PM 10 replies 1.1k views

Original Post

Jan 24, 2004 at 8:34 PM

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

billybob

Jan 24, 2004 at 8:39 PM

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.

Yohomyth

Author

Yohomyth

Jan 24, 2004 at 11:45 PM

"use flags/bitfields instead"

how do you use those?

"Solutions are not the answer." - Richard Nixon

sadwanmage

Jan 25, 2004 at 4:41 AM

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

intrest86

Jan 25, 2004 at 5:01 AM

Doesn''t the STL Vector class do this for you when you template it for bools? At least my MSVC documentation claims that booleans are a special case Vector.

Nice Coder

101

Nice Coder

Jan 25, 2004 at 5:48 AM

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

oliii

271

oliii

Jan 25, 2004 at 7:21 AM

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

oliii

271

oliii

Jan 25, 2004 at 7:24 AM

btw, bitfields always pad the remaining unused bits.

a38750

Jan 25, 2004 at 7:55 AM

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]

TerranFury

Jan 25, 2004 at 8:36 AM

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.

Topic Locked

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