/*
* 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
const int set_masks[33] = {
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()
{
std::fill<uint32*,uint32>(&m_Array[0],&m_Array[MAX_ARRAY_ELEMENTS],set_mask[32]);
};
//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;
value&= set_masks[n];
//set bits at position idx
m_Array &=~ set_masks[n]<<mod;
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] &=~ set_masks[n]>>m;
m_Array[i+1] |= value>>m;
if(networkbyteorder == true)
m_Arrayhtonl[i+1] = htonl(m_Array[i+1]);
}
};
//read n bits
uint32 read(uint32 idx, uint32 n)
{
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;
//now mask all n bits
value&= set_masks[n];
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];
};
};
Bitpacker ?some improvement suggestions?
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?
edit: this is the updated code
[Edited by - Basiror on September 25, 2005 4:11:57 AM]
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.
Quote:Original post by BasirorIt would be nice to have low-level access of some sort to the internal buffer for serialization.
Now to my question do you have any suggestions to improve it
or some additional features?
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.
@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]
@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]
Quote:Original post by BasirorMSVC6, 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..
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?
Quote:Original post by BasirorIt'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.
I also tried the outshift you mentioned it doesn t seem to cause a problem here
maybe your compiler creates a different code?
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.
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement