Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Lonewolf10]

Hi,

Over the last 2 and a half months I have been working on a ping (.png) decoder in AMOS. It works for files saved by MS Paint (from Windows XP) and Personal Paint (1996 version). I haven't tested it with Adam7 (interlaced) images yet and I have only implemented decoding of a handful of chunks, aswell as filters 0 and 1 (none and reverse sub). (I need images that use filters 2,3 & 4 before I know that code is good)

At present I find all the codes and reorder them from shortest to longest, then start scanning all codes of the same length of the code I'm trying to match. Whilst this is quicker than scanning through all the codes each time, it still takes an hour(!) to fully decode a 320x200 image (IDAT chunk size ~9000 bytes) on a 68K based (emulated) Amiga.

I was wondering if there is a quicker way to match the code found to the huffman codes?


I plan to port the code from AMOS to 68K assembler and then use it in a game I'm making. If I can use .png files instead or .raw (or .iff) files then I can get approximately x3 more graphics into the game. More, if I use the same technique to compress (deflate) the sound and level data files too!
Of course, I can only do that if the decompress (inflate) time is reasonable. (Some of that can be disquised by intro screens and pre-level screens)

Any help would be much appreciated.

[bruceuncle]

Ah.  Similar to the problem I've got with storing results from the AMOS XRef app.  Each time I come across a Variable, Proc, Label or Function token, I need to:

• Scan the existing results for a match to the name.
• Insert a record for it if it doesn't exist.
• Insert a line number and type ("definition" or "usage") record for it.

Then, after the source scan is completed, output them in sorted order.

The 'linear' scans on the name records would give me the same problem you're getting - lengthy run times.

One solution is to use a Binary Tree structure to store the records in sorted order.  They're very quick to search but have one big drawback.  If the tree gets too 'unbalanced', the search time approaches that of a 'linear' scan.  Worst case scenario is when the records are already in sorted order before they're inserted into the tree.  The scan is then 'linear'.

A 'well-balanced' Binary Tree only has a maximum search time equal to its 'depth'.  Which is not much gain for small collections of data but makes an enormous difference for large collections.  For example: 1,000,000 records can be searched with a maximum of just 20 comparisons per search.

Putting it back-to-front:

2 ^ maximum_search_depth = number_of_records

There are ways to produce self-balancing Binary Trees when the records are inserted, but coding one is complex.  I've shelved it for the time being to get stuck into the bug-fixing and docs projects.

I've attached a zip of some of the more useful stuff I downloaded when I was researching it.  They will also explain some of the terminology I used above.

[SamuraiCrow]

All of the implementations of LibPNG in C use ZLib to do their decoding grunt work.  There is a shared library implementation here.  You'll have to translate the FD file into LibCall commands or figure out the FD-to-extension converter but as an added bonus, when running on PPC accelerated Amigas it will unpack faster still.

[Lonewolf10]

Thanks for the help guys