# Bitpacker ?some improvement suggestions?

This topic is 4745 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi I just wrote a little bitpacking class, maybe someone can make use of it The usage conditions are mentioned in the header. Now to my question do you have any suggestions to improve it or some additional features?
/*
* You may use this code for nonprofit projects.
* You have to include this header in any copy of that code.
*
* Copyright @ Eduard Aumüller 2005
* basiror@gmx.de
*/

/*
* bitpack just serves for fast and easy bitpacking
*/
namespace cross
{
//set_mask[n] & value to ensure only proper bit setting
0x00000000,
0x00000001,		0x00000003,		0x00000007,		0x0000000F,
0x0000001F,		0x0000003F,		0x0000007F,		0x000000FF,
0x000001FF,		0x000003FF,		0x000007FF,		0x00000FFF,
0x00001FFF,		0x00003FFF,		0x00007FFF,		0x0000FFFF,
0x0001FFFF,		0x0003FFFF,		0x0007FFFF,		0x000FFFFF,
0x001FFFFF,		0x003FFFFF,		0x007FFFFF,		0x00FFFFFF,
0x01FFFFFF,		0x03FFFFFF,		0x07FFFFFF,		0x0FFFFFFF,
0x1FFFFFFF,		0x3FFFFFFF,		0x7FFFFFFF,		0xFFFFFFFF
};
template<uint32 bits, bool networkbyteorder = false> class bitpack
{
public:
enum bitpack_m
{
MAX_ELEMENT_BITS = (sizeof(uint32)*8),
MAX_ARRAY_ELEMENTS = (((bits-1)/(sizeof(uint32)*8))+1),//bits -1 should solve the case of a additional element
BITPACK_ERROR = 0xFFFFFFFF
};
bitpack()
{
std::fill<uint32*,uint32>(&m_Array[0],&m_Array[MAX_ARRAY_ELEMENTS],0);
};
//maximum bit index
uint32	max_idx()
{
return static_cast<uint32>(bits -1);
};
//set all bits
void	set()
{
};
//set bit at position idx to value
void	set(uint32 idx, BOOL value=TRUE)
{
set(idx,1,static_cast<uint32>(value));
};
//set n bits of value make sure no bit above (n-1)th is set
void	set(uint32 idx,uint32 n, uint32 value)
{
uint32	i = idx / MAX_ELEMENT_BITS;
uint32	mod = idx % MAX_ELEMENT_BITS;
uint32	m = MAX_ELEMENT_BITS - mod;

if(i >= MAX_ARRAY_ELEMENTS)
return;

//only 32 bits available to set
if(n > MAX_ELEMENT_BITS)
return;

//set bits at position idx
m_Array |= value<<mod;

if(networkbyteorder == true)
m_Arrayhtonl = htonl(m_Array);

//uint32 crossing m bits were written
if(m < n && (i+1 < MAX_ARRAY_ELEMENTS))
{
m_Array[i+1] |= value>>m;

if(networkbyteorder == true)
m_Arrayhtonl[i+1] = htonl(m_Array[i+1]);
}
};
{
uint32 i = idx / MAX_ELEMENT_BITS;
uint32 mod = idx% MAX_ELEMENT_BITS;
uint32 m = MAX_ELEMENT_BITS - mod;
uint32 value = 0;

if(i >= MAX_ARRAY_ELEMENTS)
return BITPACK_ERROR;

//we can only read 32 bits at once
if(n > MAX_ELEMENT_BITS)
return BITPACK_ERROR;

value = m_Array>>mod;

//anything left to read? shift left for to save the m bits we already wrote!
if(m < n && (i+1 < MAX_ARRAY_ELEMENTS))
value |= m_Array[i+1]<<m;

return value;

};
//clear all bits
void	clear()
{
std::fill<uint32*,uint32>(&m_Array[0],&m_Array[MAX_ARRAY_ELEMENTS],0);
};
//returns the data array in network byte order optionally
const byte8* data(BOOL bNetByteOrder = FALSE)
{
if(bNetByteOrder == FALSE)
return reinterpret_cast<byte8*>(m_Array);

return reinterpret_cast<byte8*>(m_Arrayhtonl);
}
void print()
{
for(int i=0;i<MAX_ARRAY_ELEMENTS;i++)
{
std::cout<<i<<" "<<m_Array<<std::endl;
}
};
private:
uint32	m_Array[MAX_ARRAY_ELEMENTS];
uint32	m_Arrayhtonl[MAX_ARRAY_ELEMENTS];
};
};

edit: this is the updated code [Edited by - Basiror on September 25, 2005 4:11:57 AM]

##### Share on other sites
Your formula for MAX_ARRAY_ELEMENTS is incorrect; it allocates an extra element for any number of bits which is a multiple of MAX_ELEMENT_BITS.

##### Share on other sites
Quote:
 Original post by BasirorNow to my question do you have any suggestions to improve itor some additional features?
It would be nice to have low-level access of some sort to the internal buffer for serialization.
Also how about templating the unit type? With that you'd get a proper byte-order handling simply by changing it to a byte.

Be careful with shifting constants larger than the size of the integer (the m variable in set and read if the bit index is an even multiple of 32). On newer x86 chips (386+ actually) such shifts get their high bits ignored and thus (in this case) preserve the original value instead of shifting it out completely.

Have you studied the generated assembly code? For some reason MSVC6 failed to optimize power-of-two modulo into bitwise ANDs for me when using enum for constants.

Overall it looks like a very useful little class.

##### Share on other sites
@Sneftel: yes right I will correct this one
@doynax: I have compiled it and the ASM part of the modulo is and $32,.... on my machine did you use MSVC++6.0 or the VC2003 toolkit? I also tried the outshift you mentioned it doesn t seem to cause a problem here maybe your compiler creates a different code? I wrote this class with uint32 in mind for my engine but since the structure of the code is the same for any type I should be a problem to template unit type I ll post the updated code tomorrow I am just to tired right now thx for the suggestions [soure lang="cpp"] ?set@?$bitpack@$0DI@@cross@@QAEXIII@Z PROC NEAR ; cross::bitpack<56>::set, COMDAT ; _this$ = ecx

; 60 : {

00000 53 push ebx
00001 8b d9 mov ebx, ecx

; 61 : uint32 i = idx / MAX_ELEMENT_BITS;

00003 8b 4c 24 08 mov ecx, DWORD PTR _idx$[esp] 00007 56 push esi 00008 8b d1 mov edx, ecx ; 62 : uint32 mod = idx % MAX_ELEMENT_BITS; 0000a 83 e1 1f and ecx, 31 ; 0000001fH ; 63 : uint32 m = MAX_ELEMENT_BITS - mod; 0000d be 20 00 00 00 mov esi, 32 ; 00000020H 00012 c1 ea 05 shr edx, 5 00015 2b f1 sub esi, ecx [/source] #### Share this post ##### Link to post ##### Share on other sites Quote:  Original post by BasirorI have compiled it and the ASM part of the modulo is and$32,.... on my machine did you use MSVC++6.0 or the VC2003 toolkit?
MSVC6, and your code seems to compile just fine with it for me too. I'm quite certain that I managed to get it to happen (with maximum optimizations on and all), I just can't figure out the precise circumstances..
Quote:
 Original post by BasirorI also tried the outshift you mentioned it doesn t seem to cause a problem heremaybe your compiler creates a different code?
It's a hardware 'bug', not a software one. The generated assembly code from your post can let m (esi) reach 32 which would wrap around to zero and result in no shift at all.

edit: Wait a second, that's not a problem at all, the if(m < n) cases filters them out. Sorry for implying that your code was buggy but I've run into this issue a few times myself when trying to remove special cases from bit stream handling.

##### Share on other sites
in fact the case m = 32 will never appear, because this means you just write to a higher index idx+1 and m=32 can never be the result of x%32

ok thanks for the feedback ill post the corrected code in a few mins

edit: I just thought about the templated type, alternatively I could provide a method that returns a pointer to network byte ordered data and updates it when ever you set some bits

edit2: I added a data member function that returns normal data or host byte ordered, the htonl calls are optimized away if you create the bitpack instance with networkbyteorder=false, ill keep this code up to date when I do further additions later on

[Edited by - Basiror on September 25, 2005 4:27:58 AM]

1. 1
2. 2
Rutin
21
3. 3
4. 4
frob
14
5. 5

• 12
• 9
• 17
• 19
• 9
• ### Forum Statistics

• Total Topics
632598
• Total Posts
3007334

×

## Important Information

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!