Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Bitstream decoding
2015-07-20 09:34
lft

Registered: Jul 2007
Posts: 369
Bitstream decoding

I wrote a little article about fast bitstream decoding over at codebase. Enjoy!
2015-07-20 10:31
Oswald

Registered: Apr 2002
Posts: 5094
just rushed trough it, but found some nifty nice routine at the end, and a well written article, well done :)
2015-07-20 11:01
Mr. SID

Registered: Jan 2003
Posts: 424
Nice and elegant. Very good read!
2015-07-20 11:30
tlr

Registered: Sep 2003
Posts: 1790
Some very nice tricks in there. Thanks for sharing!
2015-07-20 12:57
TNT
Account closed

Registered: Oct 2004
Posts: 189
One more trick mentioned here: you get free OR operation by loading A with a value with multible bits set :)
2015-07-20 13:00
Flavioweb

Registered: Nov 2011
Posts: 463
Nice! Thanks a lot!
2015-07-20 18:01
Bitbreaker

Registered: Oct 2002
Posts: 508
The routine is nice, but gets unhandy when the number of bits to be fetched is determinded while fetching, consider for e.g. the elias gamma encoding as being used to encode the lengtths in doynax/byteboozer?
One would need to shift in from the right side ones for building up a counter and then shift them out again to the left when fetching the bits to be fetched for a number. So one would need at least the ability to change the direction of the shifter.
I counted some cycles and it is just as fast as a jsr to get_byte in case, but of course it reduces code. But there's overhead after each fetch with the table lookup. Also when using x as lowbyte and index, things can be made faster:

ldy buffer,x
inx
bne no_new_page

Of course x then can't be used anywhere else.
2015-07-20 18:56
lft

Registered: Jul 2007
Posts: 369
Quoting Bitbreaker
consider for e.g. the elias gamma encoding as being used to encode the lengtths in doynax/byteboozer?


Yes, for some applications, there is no need for generic decision trees. Then it might be faster to use other methods. My approach can in principle be used to encode Elias Gamma or Huffman (with 128 symbols, I think), because both of these can be regarded as decision trees. But certainly, for the Elias Gamma case, it should be faster to use right-shifting instead of having a table entry for each shift position. And for Huffman, there is no need to support fields wider than one bit, so that can probably also be optimised.

Quote:
Also when using x as lowbyte and index, things can be made faster:

ldy buffer,x
inx
bne no_new_page

Of course x then can't be used anywhere else.


This is an excellent improvement. Why didn't I think of that? =)
2015-07-20 21:54
lft

Registered: Jul 2007
Posts: 369
Quoting lft
This is an excellent improvement. Why didn't I think of that? =)


Oh, now I remember. I did think of it. In the final decoder, both A and Y need to be preserved. Therefore, if we use indexed addressing to save four cycles, we must also save and restore one of those registers, at a cost of six cycles.
2015-07-21 18:09
Frantic

Registered: Mar 2003
Posts: 1648
Dear Sir lft,

Thank you for your most excellent addition to the codebase.

My very best wishes,
Frantic
2015-07-22 19:13
Glasnost
Account closed

Registered: Aug 2011
Posts: 26
Nice article :)

Another good example of code optimisation.

replace the ..
clc
jmp decodeloop

with
clc
bcc decodeloop

and save a byte.
2015-07-22 20:40
Peiselulli

Registered: Oct 2006
Posts: 81
... and add a cycle if a page is crossed ;-(
2015-07-23 04:31
Mr. SID

Registered: Jan 2003
Posts: 424
Don't cross the pages!
2015-07-23 07:30
Oswald

Registered: Apr 2002
Posts: 5094
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
csabanw
JackAsser/Booze Design
Twoflower/ΤRIΛD
Jangler/Artline Desi..
Chrx/Design/Chaos
Guests online: 115
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 Edge of Disgrace  (9.6)
6 What Is The Matrix 2  (9.6)
7 The Demo Coder  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 No Listen  (9.6)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 Dawnfall V1.1  (9.5)
7 Rainbow Connection  (9.5)
8 Onscreen 5k  (9.5)
9 Morph  (9.5)
10 Libertongo  (9.5)
Top Groups
1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Triad  (9.3)
5 Censor Design  (9.3)
Top Logo Graphicians
1 t0m3000  (10)
2 Sander  (9.8)
3 Mermaid  (9.5)
4 Facet  (9.4)
5 Shine  (9.4)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.042 sec.