Jump to content
  • Advertisement
Sign in to follow this  
oliii

bitstreams and bit packing fun

This topic is 4827 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

Hello peeps, I'm attempting to implement a bit streaming structure, for a bitpacking utility for delta-compressed networked communications. I'll start off with appending a bitstream to another bit stream, like so
//--------------------------------------------------------------------------------
// WriteBitStream
//--------------------------------------------------------------------------------
// Append an input bit stream (In, inptr) into 
// an output bit stream (Out, outptr) 
//--------------------------------------------------------------------------------
// with 'numbits' number of bits.
// u_int* Out     : output bit stream data
// u_int  outptr  : start bit position of the output stream data
// u_int* In      : input bit stream data
// u_int  inptr   : start bit position of the input stream data
// u_int  numbits : number of bits to be copied. 
//--------------------------------------------------------------------------------
void WriteBitStream(u_int* Out, u_int outptr, u_int* In, u_int inptr, u_int numbits);


Right, so seems easy... But it's a real mind bender. I was wondering if something like has already been implemented, because I can't get my head around it, or not with difficulty, and I haven't found a good clean and fast algo for it.

Share this post


Link to post
Share on other sites
Advertisement
This is the kind of thing that's actually easier to write in asm, where you can make assumptions (byte order, unaligned accesses) and use special instructions (rotation, shld).
Maybe you could write a generic version and an optimized x86 version?

I'll give it a shot though.

Share this post


Link to post
Share on other sites
Why not just write a class that has some functions to append a bit to the current stream.


Class MyBitStream_C
{
public:
unsigned char BitStream[1000]; //Should make this dynamic/growable
unsigned long BitCount; //Number of bits in stream
private:
unsigned long CurrentByte, CurrentBit;

public:
MyBitStream_C(void)
{
CurrentByte=0;
CurrentBit=0;
++BitCount;
}

void AddBit(char Value) //Append a 1/0
{
if (CurrentBit==8)
{
CurrentBit=0;
CurrentByte++;
BitStream[CurrentByte]=0; //Set it to zero each time.
}
BitStream[CurrentByte] |= (Value<<CurrentBit);
}

char ReadBit(unsigned long BitLocation)
{
if (BitLocation>=BitCount)
return -1;
unsigned long ByteLoc = BitLocation/8;
BitLocation&=7;
return (BitStream[ByteLoc]>>BitLocation)&1; //Check to see if bit is set...
}
};



Now to append, you would simply ReadBits on one stream, and Addbits to the other. Of course you could optimize this a lot, but hey :).


--- Edit ---
Put /source in wrong spot :P

Share this post


Link to post
Share on other sites
One last thing, if you need more functions, like insert bit at a specific location or anything, just let me know, they are easy enough to write (for me at least, i've done a good amount of work with bit's).

Share this post


Link to post
Share on other sites
Quote:
Original post by Ready4Dis
Why not just write a class that has some functions to append a bit to the current stream.

*** Source Snippet Removed ***

Now to append, you would simply ReadBits on one stream, and Addbits to the other. Of course you could optimize this a lot, but hey :).


--- Edit ---
Put /source in wrong spot :P


I dont' reall want to write it bit by bits. Rather, I'd like to paste chunks of bits from one word to another. Even better would be to do 64 bit manipulations. THis thing's gotta be fast.

Also, I don't really need access to single bits and random access. It's for data compression and decompression. So what goes in goes out the same way, no need to shuffle bits.

as a starter, I came up with this, *but* I need to test it.


void WriteBitStream(u_int* Out, u_int outptr, u_int* In, u_int inptr, u_int numbits)
{
while (numbits)
{
u_int outoffset = outptr & 31; // word offset to append data to
u_int inoffset = inptr & 31; // word offset to append data from
u_int outsize = 32 - outoffset; // max size of output that can overwritten
u_int insize = min(32 - inoffset, numbits); // max size of input that can be copied
u_int size = min(insize, outsize); // size of data chunk that can be pasted froom one word to another
u_int data; // chunk of data to append

data = (In[(inptr >> 32)] >> inoffset); // extract data from end of input buffer
data &= (0xFFFFFFFF >> (32 - size)); // crop top bits to the max size

Out[(outptr >> 32)] &= (0xFFFFFFFF >> outsize); // clear high bits of output
Out[(outptr >> 32)] |= (uData << uOutOffset); // append data to end of output

// increment pointers
// We have copied 'size' bits.
outptr += size;
inptr += size;
numbits -= size;
}
}


Share this post


Link to post
Share on other sites
You can easily get the inner loop down to a few basic instructions:
union {
struct {
u32 lo, hi; // assume little-endian
};
u64 full;
} acc;

acc.lo = *In++;
acc.hi = *In++;
acc.full <<= steps;
*Out++ = acc.lo;
Which hopefully translates to something like this:
mov eax,[esi]
shld eax,[esi+4],cl
mov [edi],eax
The edge cases are the real problem however and the amount of logic required to handle them may not be worth it if you're only writing a few words per call.

It may help a little if we're allowed to temporarily overwrite the first and last few bits of the destination buffer while working. Additionally it would be good to know whether the word after the last in the input buffer is readable.

Share this post


Link to post
Share on other sites
Thanks for the replies and ideas.

I think I cracked it, as well as my head.


void PrintStream(u_int* stream, u_int ptr, u_int size)
{
printf("[%d]", size);

for(u_int i = ptr; i < ptr + size; i ++)
{
u_int uData = stream[i >> 5];
u_int bit = i & 31;

if(uData & (1 << bit))
{
printf("1");
}
else
{
printf("0");
}
}
printf("\n");
}
inline u_int GETHIGH(u_int word, u_int offset)
{
return (word >> offset);
}

inline u_int GETLOW(u_int word, u_int offset)
{
// brrrr
if(offset == 0)
{
return 0;
}

int shift = (32 - offset);
return (word << shift) >> shift;
}

inline u_int GETMID(u_int word, u_int offset, u_int size)
{
return GETLOW(GETHIGH(word, offset), size);
}

//--------------------------------------------------------------------------------
// WriteBitStream
//--------------------------------------------------------------------------------
// Append an input bit stream (In, inptr) into
// an output bit stream (Out, outptr)
//--------------------------------------------------------------------------------
// with 'numbits' number of bits.
// u_int* Out : output bit stream data
// u_int outptr : start bit position of the output stream data
// u_int* In : input bit stream data
// u_int inptr : start bit position of the input stream data
// u_int numbits : number of bits to be copied.
//--------------------------------------------------------------------------------
void WriteBitStream(u_int* Out, u_int outptr, u_int* In, u_int inptr, u_int numbits)
{
printf("input ");
PrintStream(In, 0, inptr + numbits);

printf(" writing ");
PrintStream(In, inptr, numbits);

while (numbits)
{
u_int outoffset = (outptr & 31); // word offset to append data to
u_int inoffset = (inptr & 31); // word offset to append data from
u_int outsize = 32 - outoffset; // max size of output that can overwritten
u_int insize = min(32 - inoffset, numbits); // max size of input that can be copied
u_int size = min(insize, outsize); // size of data chunk that can be pasted froom one word to another

// get input data chunk
u_int indata = GETMID(In[(inptr >> 5)], inoffset, size);
u_int& outdata = Out[(outptr >> 5)];

// append to end of output stream
outdata = GETLOW(outdata, outoffset);
outdata |= (indata << outoffset);

printf(" chunk ");
PrintStream(&indata, 0, size);

// increment pointers
// We have copied 'size' bits.
outptr += size;
inptr += size;
numbits -= size;
}

printf("output");
PrintStream(Out, 0, outptr);
printf("\n\n");

}
u_int ConvertStringToBitStream(u_int* stream, u_int inptr, char* str)
{
u_int size = 0;

while (*str)
{
if(*str != '1' && *str != '0')
{
str++;
continue;
}

u_int i = inptr + size;
u_int word = (i >> 5);
u_int bit = (i & 31);
stream[word] = GETLOW(stream[word], bit);

if(*str == '1')
{
stream[word] |= (1 << bit);
}

str++;
size++;
}
return size;
}


void main()
{
u_int inputstream[2048];
u_int ouptputstream[2048];
u_int size = 0;
u_int outptr = 0;
u_int inptr = 0;

while (1)
{
char str[64];
_cgets(str);
size = ConvertStringToBitStream(inputstream, inptr, str);

if(size == 0)
break;

WriteBitStream(ouptputstream, outptr, inputstream, inptr, size);
outptr += size;
inptr += size;
}
}





GETLOW() really is for clearing the high bits of a word.

ok... it seems to behave. So it basically happens a stream of bits at the end of another stream of bits, with arbitrary offsets.

Thanks. I'll still take a look at those articles, I'm just a noob in that whole networking malarkey.

Now, endianess... super.

[Edited by - oliii on August 25, 2005 7:40:46 PM]

Share this post


Link to post
Share on other sites
This is the best I've been able to come up with so far:
void write_bit_stream(const u32 *src, unsigned src_bit, u32 *dst, unsigned dst_bit, unsigned nbits)
{
signed steps;

struct {
u32 *ptr, mask, org;
} head, tail;

// let the bit offsets cross word boundaries
src += src_bit >> 5, src_bit &= 31;
dst += dst_bit >> 5, dst_bit &= 31;

// calculate the number of steps used to shift the source data into the destination buffer
if(steps = dst_bit - src_bit, steps > 0) {
--src;
}

nbits += dst_bit;

// cache the destination buffer's first and last word
head.ptr = dst;
tail.ptr = &dst[(nbits - 1) >> 5];
head.mask = ~(0xffffffff >> dst_bit);
tail.mask = 0xffffffff >> (nbits & 31);
head.org = *head.ptr & head.mask;
tail.org = *tail.ptr & tail.mask;

// the main loop
if(steps &= 31, steps) {
do {
// load the next two consecutive words
u32 acc_hi = *src++;
u32 acc_lo = *src;

// emulate a double shift
acc_lo >>= steps;
acc_hi <<= 32 - steps;

// output the result's lower half
*dst++ = acc_lo | acc_hi;
} while(dst <= tail.ptr);
// a special case is necessary since a 32 step shift wraps around to zero on some platforms
} else {
do {
*dst++ = *src++;
} while(dst <= tail.ptr);
}

// restore the unused parts of the destination buffer
*head.ptr &= ~head.mask;
*tail.ptr &= ~tail.mask;
*head.ptr |= head.org;
*tail.ptr |= tail.org;
}

I'm too tired to debug it properly right now though, and the code generated by MSVC6 could've been better. Additionally the unused parts of the destination buffer may be temporarily overwritten and the words right before the source buffer's start and end must be readable (not raise a segfault).
It's a big-endian shift by the way, but that could easily be changed.

edit: Tweaked a few things and fixed a bug or two..

[Edited by - doynax on August 26, 2005 1:17:51 PM]

Share this post


Link to post
Share on other sites
I'm wondering why don't you want to use byte-aligned structures, can be done with #pragma pack(...).

i.e.

#pragma pack(1)
typedef struct {
int ...
uint ...
uchar ...
} t_somestruct;
#prama pack(your preferred alignment)


Later, structures can be used from classes that utilize command pattern general techniques.


Edition:
oh, sorry, you're talking about bit streams... so

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.

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!