Jump to content
  • Advertisement
Sign in to follow this  
Basiror

Bitpacker ?some improvement suggestions?

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

If you intended to correct an error in the post then please contact us.

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
	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];
	};
};

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

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
Quote:
Original post by Basiror
Now to my question do you have any suggestions to improve it
or 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 this post


Link to post
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 Basiror
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?
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 Basiror
I also tried the outshift you mentioned it doesn t seem to cause a problem here
maybe 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 this post


Link to post
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]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!