//--------------------------------------------------------------------------------
// 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);
bitstreams and bit packing fun
Author
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
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.
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.
Maybe you could write a generic version and an optimized x86 version?
I'll give it a shot though.
Why not just write a class that has some functions to append a bit to the current stream.
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
Class MyBitStream_C{public:unsigned char BitStream[1000]; //Should make this dynamic/growableunsigned long BitCount; //Number of bits in streamprivate: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
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).
Packing Integers (you can get better compression when the range is limited and known: sub-bit precision packing)
The Inner Product (see Networking)
See Game Programming Gems IV: Bit Packing: A Network Compression Technique
Bitpacker article
The Inner Product (see Networking)
See Game Programming Gems IV: Bit Packing: A Network Compression Technique
Bitpacker article
Author
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; }}
You can easily get the inner loop down to a few basic instructions:
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.
union { struct { u32 lo, hi; // assume little-endian }; u64 full;} acc;acc.lo = *In++;acc.hi = *In++;acc.full <<= steps;*Out++ = acc.lo;mov eax,[esi]shld eax,[esi+4],clmov [edi],eaxIt 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.
Author
Thanks for the replies and ideas.
I think I cracked it, as well as my head.
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;<br> u_int bit = i & <span class="cpp-number">31</span>;<br> <br> <span class="cpp-keyword">if</span>(uData & (<span class="cpp-number">1</span> << bit))<br> {<br> printf(<span class="cpp-literal">"1"</span>);<br> }<br> <span class="cpp-keyword">else</span><br> {<br> printf(<span class="cpp-literal">"0"</span>);<br> }<br> }<br> printf(<span class="cpp-literal">"\n"</span>);<br>}<br><span class="cpp-keyword">inline</span> u_int GETHIGH(u_int word, u_int offset)<br>{<br> <span class="cpp-keyword">return</span> (word >> offset);<br>}<br><br><span class="cpp-keyword">inline</span> u_int GETLOW(u_int word, u_int offset)<br>{<br> <span class="cpp-comment">// brrrr</span><br> <span class="cpp-keyword">if</span>(offset == <span class="cpp-number">0</span>)<br> {<br> <span class="cpp-keyword">return</span> <span class="cpp-number">0</span>;<br> }<br><br> <span class="cpp-keyword">int</span> shift = (<span class="cpp-number">32</span> - offset);<br> <span class="cpp-keyword">return</span> (word << shift) >> shift;<br>}<br><br><span class="cpp-keyword">inline</span> u_int GETMID(u_int word, u_int offset, u_int size) <br>{<br> <span class="cpp-keyword">return</span> GETLOW(GETHIGH(word, offset), size);<br>}<br><br><span class="cpp-comment">//——————————————————————————–</span><br><span class="cpp-comment">// WriteBitStream</span><br><span class="cpp-comment">//——————————————————————————–</span><br><span class="cpp-comment">// Append an input bit stream (In, inptr) into </span><br><span class="cpp-comment">// an output bit stream (Out, outptr) </span><br><span class="cpp-comment">//——————————————————————————–</span><br><span class="cpp-comment">// with 'numbits' number of bits.</span><br><span class="cpp-comment">// u_int* Out : output bit stream data</span><br><span class="cpp-comment">// u_int outptr : start bit position of the output stream data</span><br><span class="cpp-comment">// u_int* In : input bit stream data</span><br><span class="cpp-comment">// u_int inptr : start bit position of the input stream data</span><br><span class="cpp-comment">// u_int numbits : number of bits to be copied. </span><br><span class="cpp-comment">//——————————————————————————–</span><br><span class="cpp-keyword">void</span> WriteBitStream(u_int* Out, u_int outptr, u_int* In, u_int inptr, u_int numbits)<br>{<br> printf(<span class="cpp-literal">"input "</span>);<br> PrintStream(In, <span class="cpp-number">0</span>, inptr + numbits);<br> <br> printf(<span class="cpp-literal">" writing "</span>);<br> PrintStream(In, inptr, numbits);<br> <br> <span class="cpp-keyword">while</span> (numbits)<br> {<br> u_int outoffset = (outptr & <span class="cpp-number">31</span>); <span class="cpp-comment">// word offset to append data to</span><br> u_int inoffset = (inptr & <span class="cpp-number">31</span>); <span class="cpp-comment">// word offset to append data from</span><br> u_int outsize = <span class="cpp-number">32</span> - outoffset; <span class="cpp-comment">// max size of output that can overwritten</span><br> u_int insize = min(<span class="cpp-number">32</span> - inoffset, numbits); <span class="cpp-comment">// max size of input that can be copied</span><br> u_int size = min(insize, outsize); <span class="cpp-comment">// size of data chunk that can be pasted froom one word to another</span><br> <br> <span class="cpp-comment">// get input data chunk</span><br> u_int indata = GETMID(In[(inptr >> <span class="cpp-number">5</span>)], inoffset, size);<br> u_int& outdata = Out[(outptr >> <span class="cpp-number">5</span>)];<br><br> <span class="cpp-comment">// append to end of output stream</span><br> outdata = GETLOW(outdata, outoffset);<br> outdata |= (indata << outoffset);<br><br> printf(<span class="cpp-literal">" chunk "</span>);<br> PrintStream(&indata, <span class="cpp-number">0</span>, size);<br><br> <span class="cpp-comment">// increment pointers</span><br> <span class="cpp-comment">// We have copied 'size' bits.</span><br> outptr += size;<br> inptr += size;<br> numbits -= size;<br> }<br><br> printf(<span class="cpp-literal">"output"</span>);<br> PrintStream(Out, <span class="cpp-number">0</span>, outptr);<br> printf(<span class="cpp-literal">"\n\n"</span>);<br><br>}<br>u_int ConvertStringToBitStream(u_int* stream, u_int inptr, <span class="cpp-keyword">char</span>* str)<br>{<br> u_int size = <span class="cpp-number">0</span>;<br><br> <span class="cpp-keyword">while</span> (*str)<br> {<br> <span class="cpp-keyword">if</span>(*str != '<span class="cpp-number">1</span>' && *str != '<span class="cpp-number">0</span>')<br> {<br> str++;<br> <span class="cpp-keyword">continue</span>;<br> }<br><br> u_int i = inptr + size;<br> u_int word = (i >> <span class="cpp-number">5</span>);<br> u_int bit = (i & <span class="cpp-number">31</span>);<br> stream[word] = GETLOW(stream[word], bit);<br> <br> <span class="cpp-keyword">if</span>(*str == '<span class="cpp-number">1</span>')<br> {<br> stream[word] |= (<span class="cpp-number">1</span> << bit);<br> }<br><br> str++;<br> size++;<br> }<br> <span class="cpp-keyword">return</span> size;<br>}<br><br><br><span class="cpp-keyword">void</span> main()<br>{<br> u_int inputstream[<span class="cpp-number">2048</span>];<br> u_int ouptputstream[<span class="cpp-number">2048</span>];<br> u_int size = <span class="cpp-number">0</span>;<br> u_int outptr = <span class="cpp-number">0</span>;<br> u_int inptr = <span class="cpp-number">0</span>;<br><br> <span class="cpp-keyword">while</span> (<span class="cpp-number">1</span>)<br> {<br> <span class="cpp-keyword">char</span> str[<span class="cpp-number">64</span>];<br> _cgets(str);<br> size = ConvertStringToBitStream(inputstream, inptr, str);<br><br> <span class="cpp-keyword">if</span>(size == <span class="cpp-number">0</span>)<br> <span class="cpp-keyword">break</span>;<br><br> WriteBitStream(ouptputstream, outptr, inputstream, inptr, size);<br> outptr += size;<br> inptr += size;<br> }<br>}<br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>GETLOW() really is for clearing the high bits of a word. <br><br>ok… it seems to behave. So it basically happens a stream of bits at the end of another stream of bits, with arbitrary offsets.<br><br>Thanks. I'll still take a look at those articles, I'm just a noob in that whole networking malarkey.<br><br>Now, endianess… super.<br><br><!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - oliii on August 25, 2005 7:40:46 PM]<!–EDIT–></span><!–/EDIT–>
This is the best I've been able to come up with so far:
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]
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]
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
