Reading from a simple bitstream in 68000

[DanScott]

So if I have for example A0 pointing to a bitstream, what would be a good method of reading (for example) an arbitrary number or bits from the stream.

I am guessing that you would maybe preload a data register from the address, and then read bits from the data register... but then you will have to reload the data register at some point.

I am trying to get my head around how this could be implemented so that it runs quickly, and not too convoluted code.

Anyone have any experience in this ?

[hooverphonique]

For instance mpeg audio stream decoders make heavy use of this sort of thing, but they are most often written in C I think.

I would say an implementation would depend a lot on, where you want the bits to go (into a register?) and whether you need to read more than 32 bits at a time or not.

[DanScott]

Probably will be usually reading 1 or 4 bits at a time (for an animation compression technique I've devised)

I just can't think of an easy way to re-load the data. What I really want is a simple quick routine that I can inline with a macro (rather than have the overhead of a call to a subroutine).

I guess if i know my current bit position, and I read 4 bits, if the next read position goes over 8. to subtract 8 off the bit position, rotate the data by 8, and then pop a new byte on the end

maybe 16 would be better.. could write a new low word, then "swap" the upper and lower.

[DanScott]

I need to think deeper about this

[PeterK]

In my zlib inflate code I use something like this:

               moveq   #n,D1          ; n bits wanted
               cmp.l   D1,D2          ; bits in buffer ?
               BCC.S   .enoughbits
.readnextbyte
               MOVEQ   #0,D0
               move.b  (Ax)+,D0       ; byte from bitstream
               lsl.l   D2,D0
               or.l    D0,D3          ; the bit buffer
               addq.l  #8,D2
               cmp.l   D1,D2          ; only required for n > 8
               BCS.S   .readnextbyte  ; ditto
.enoughbits
               move.l  D3,D0          ; use your n bits
               ....
               sub.l   D1,D2
               lsr.l   D1,D3

[DanScott]

That looks a great start for me thanks

And if I am only reading no more that 8 bits, I can remove the 2 lines that handle moving more data in

[meynaf]

Beware : inflate is little endian. Perhaps not what you wanted. In addition, in the above code, returned data isn't masked out.

Here's my version.
The following reads D5 bits from (A0)+ into D1.L, max 8 bits.
Initialised with D4=0 (D3 does not need init).

 cmp.b d5,d4
 bcc.s .re
; subq.l #1,d0		; if you want to detect out-of-bounds reading
; bcs horror            ; (needs D0=available data in bytes)
 lsl.l #8,d3
 move.b (a0)+,d3
 addq.b #8,d4
.re
 moveq #0,d1
 bset d4,d1
 subq.l #1,d1
 sub.b d5,d4
 and.l d3,d1
 lsr.l d4,d1            ; also sets Z for single bit

[ross]

Originally Posted by meynaf

Beware : inflate is little endian. Perhaps not what you wanted. In addition, in the above code, returned data isn't masked out.

Here's my version.
The following reads D5 bits from (A0)+ into D1.L, max 8 bits.
Initialised with D4=0 (D3 does not need init).

 cmp.b d5,d4
 bcc.s .re
; subq.l #1,d0		; if you want to detect out-of-bounds reading
; bcs horror            ; (needs D0=available data in bytes)
 lsl.l #8,d3
 move.b (a0)+,d3
 addq.b #8,d4
.re
 moveq #0,d1
 bset d4,d1
 subq.l #1,d1
 sub.b d5,d4
 and.l d3,d1
 lsr.l d4,d1            ; also sets Z for single bit

Interesting this "deferred replenish" for the encoder

[ross]

Originally Posted by DanScott

Probably will be usually reading 1 or 4 bits at a time (for an animation compression technique I've devised)

Can you have two separate bitstream?

Single bit extracted with add dx,dx ->X from the 1st stream.
Nibble from a dx masked and successive lsr #4 with a counter for successive filling from the 2nd.

[phx]

Originally Posted by meynaf

The following reads D5 bits from (A0)+ into D1.L, max 8 bits.
Initialised with D4=0 (D3 does not need init).

 cmp.b d5,d4
 bcc.s .re
; subq.l #1,d0        ; if you want to detect out-of-bounds reading
; bcs horror            ; (needs D0=available data in bytes)
 lsl.l #8,d3
 move.b (a0)+,d3
 addq.b #8,d4
.re
 moveq #0,d1
 bset d4,d1
 subq.l #1,d1
 sub.b d5,d4
 and.l d3,d1
 lsr.l d4,d1            ; also sets Z for single bit

When you read 8 bits at most, wouldn't it be faster to change all longword operations into word-operations? You don't have to waste those extra cycles on an 68000, do you?

BTW, reading from a bitstream is a common operation in most decompression routines. For example the infamous Bytekiller decruncher looks like this:

getbits:
; d4 = bits to get - 1
; -> d2 = result, extended to 16 bits

        clr.w   d2
.1:     lsr.l   #1,d0
        bne     .2
        bsr     nextword
.2:     roxl.l  #1,d2
        dbf     d4,.1
        rts

It reads bit by bit in a loop, which is certainly not optimal. But it uses an intelligent way to detect when a 32-bit register becomes empty, by setting a guard-bit, when reading the next longword:

nextword:
        ...
.1:     move.l  -(a0),d0
        eor.l   d0,d7
        move.w  #$10,ccr
        roxr.l  #1,d0
        rts

[ross]

Originally Posted by phx

..the infamous Bytekiller decruncher looks like this:

infamous is the right word
Not optimized at all.

But it uses an intelligent way to detect when a 32-bit register becomes empty, by setting a guard-bit, when reading the next longword:

nextword:
        ...
.1:     move.l  -(a0),d0
        eor.l   d0,d7
        move.w  #$10,ccr
        roxr.l  #1,d0
        rts

Very bad implementation...

Bit guard need to added and be part of the extracted data.
A tips: when you need to refill if you use full 33 bit ALU?
(32data bit + X as guard)

[DanScott]

Originally Posted by ross

Can you have two separate bitstream?

Single bit extracted with add dx,dx ->X from the 1st stream.
Nibble from a dx masked and successive lsr #4 with a counter for successive filling from the 2nd.

This was something i did consider 1st, as it would be such a simpler solution, however there would be a higher register overhead (should still be possible though), and I would not so easily be able to read (for example) 5 bits or 6 bits if I suddenly found the need to change the layout of my stream.

This is all for something over the next few weeks (have to get Revision out the way first)

[meynaf]

Originally Posted by phx

When you read 8 bits at most, wouldn't it be faster to change all longword operations into word-operations? You don't have to waste those extra cycles on an 68000, do you?

Yeah, sorry, too much 020+ coding, lost 68000 habits long ago.

[ross]

Originally Posted by DanScott

This was something i did consider 1st, as it would be such a simpler solution

Simpler and faster

..and I would not so easily be able to read (for example) 5 bits or 6 bits if I suddenly found the need to change the layout of my stream.

If you are sure that 4 is the minimum bits required you can spread the remaining bit(s) on the 1st stream (unfortunately, there are no submultiples better than 4 in the 32bit and you would be forced to perform variable shift and mask operations).
So:
add dx,dx (from 1st)
addx read(nibble(2nd))

Good Revision!

[ross]

[OT]
@meynaf: I finally got where your image and title came from after Loom's thread

Yes, I know it's serious that I didn't know

[PeterK]

Originally Posted by meynaf

Beware : inflate is little endian. Perhaps not what you wanted. In addition, in the above code, returned data isn't masked out.

Yes, my example is for little endian. The bitstream grows from LSB to MSB. In meynaf's code it's just the opposite. The masking in my code is hidden in the "....", since I don't know what the bits are used for.

[Kalms]

Sometimes it helps to split the code into two phases: first bitstream decoding, into byte- or Word-streams, and then a second phase which reads those byte-or-Word-streams and does the actual graphical work.

It is often easier to decode streams of fixed nr of bits than streams with variable nrs of bits. For >1bit formats you have three main choices for decoding, either shifts and masks, or jump tables, or lookup tables. I'd look at shifts and masks first, followed by lookup tables, followed by jump tables.

[DanScott]

Originally Posted by Kalms

Sometimes it helps to split the code into two phases: first bitstream decoding, into byte- or Word-streams, and then a second phase which reads those byte-or-Word-streams and does the actual graphical work.

It is often easier to decode streams of fixed nr of bits than streams with variable nrs of bits. For >1bit formats you have three main choices for decoding, either shifts and masks, or jump tables, or lookup tables. I'd look at shifts and masks first, followed by lookup tables, followed by jump tables.

Thanks that's some good info there too. Got me thinking heavily about my implementation now. There will a lot of blitter action going on too, so could possibly:

1) Create a blitter queue to be processed on blitter interrupts, while the CPU is decoding the stream and building the next frames worth of data.

2) Just start regular blits, and start decoding the next set of data from the stream while the blitter is working.


I am aiming at 25fps playback, so I should have plenty of time to do all the drawing and decoding for each frame.

[ross]

[OT, another]
@Dan, The Fall is a real beauty, so inspiring and aesthetic.
Reminded me of Lunatico, which is a great compliment

An immortal piece of code for our "little box of tricks".

Alice: "Per quanto tempo è per sempre?"
Bianconiglio: "A volte, solo un secondo.”

ENG:
Alice: “How long is forever?"
White Rabbit: "Sometimes, just one second.”




one last word because I am still stunned
what make the difference?: love and details
this production is full of it

[DanScott]

Originally Posted by ross

[OT, another]
@Dan, The Fall is a real beauty, so inspiring and aesthetic.
Reminded me of Lunatico, which is a great compliment

An immortal piece of code for our "little box of tricks".

Alice: "Per quanto tempo è per sempre?"
Bianconiglio: "A volte, solo un secondo.”

ENG:
Alice: “How long is forever?"
White Rabbit: "Sometimes, just one second.”




one last word because I am still stunned
what make the difference?: love and details
this production is full of it

I honestly had no idea how well The Fall would be received. Just last week, when looking at the parts individually, it seemed maybe it could be just a little too simple.. but when everything was put together, and synched with the music, it just worked. Hearing the crowd reaction during the compo at several places was enough to fill us all with pride