Generic compression on NES - *done*

[tepples]

The old assemblers followed this rule:
1. Labels MUST NOT follow whitespace; they MUST be the first thing on the line. A space, not a colon, denotes a label's end.
2. Anything other than a label MUST have whitespace before it on the line.

For example, .db is an instruction and .db 12,34 at the start of a line thus violates 2.

Newer assemblers use a colon to distinguish a label from an instruction.

[thefox]

The old assemblers followed this rule:
1. Labels MUST NOT follow whitespace; they MUST be the first thing on the line. A space, not a colon, denotes a label's end.
2. Anything other than a label MUST have whitespace before it on the line.

For example, .db is an instruction and .db 12,34 at the start of a line thus violates 2.

Newer assemblers use a colon to distinguish a label from an instruction.

Those are not the problems in this case case, though, the problem is there's no white space after the comma.

[Bregalad]

Thank you very much for the feedback. I am very pleased that this project was useful to someone else !
I shall do the improvements you mention when I get the time to do it. Most of them sound pretty simple.

The reason the .db parser is so picky is because I coded it all by myself and I didn't know too much how to do it so I coded something randomly that worked for typcial cases and didn't bother to stress test it.
I think a comma without a white space should definitely be acceptable, and I don't know why there is an error when you use Foo2. Perhaps "foo" is already defined, and I replace it by it's address before it's followed by a 2 which makes no sense ?

[Bregalad]

OK I've made several of the changes you suggested, and have at least semi-valid reasons not to have changed the others :

- Now all labels are followed by : in outputs files. Which will create weird labels ending with :: if you try to chain algorithm, but at least it will be visible that you chained algorithms that way.
- You can compress using only a single algorithm with the "fix algorithm" -fa option, followed by the number of the algorithm you want to use. I know numbers suck, but I wanted to keep it generic, that way any algorithms can be removed or added in a completely generic way. Calling them by name would have been possible but I'm lazy. In another version pehaps.
- You can force the output to the file you desire with the -o option. It's recommended to use this alongside with -fa, else you'd end up with a single file compressed with the last algorithm, each algorithm overwriting output from the previous one.
- You can change .db into .byte and .dw with .word with the -byte option

Now what way NOT changed :
- .db is still picky about the format. The reason is that if I replaced commas with white spaces, and threat white spaces as separators, then .db 12 34 would have been the same as .db 12, 34 which is a problem. I'd have to put some trought to fix this problem so I can't do it on just a quick fix. For a future version maybe.

- I have no idea what is causing the foo2 bug. I'd have to investigate this and release a fix

- Minmax is still defined as data. The reason for this is that I really do a one to one compression, I compress a List<List<Byte>> into another List<List<Byte>>, both with associated labels. If I had to make the difference between parameters and data, it would not be a one to one compression, and things would not be as generic as they are now (i.e. some coding and decoding algorithm would need more parameters than just a List<List<Byte>> to work, which I did not want to have because they could not expand the same Enoding interface if this were to happen).

The update is temporarly available at Dropbox, and will be released on Romhacking.net very soon.

I hope this will be useful to everyone, and I am looking forward to other feedback in order to improve this tool.

[thefox]

OK I've made several of the changes you suggested, and have at least semi-valid reasons not to have changed the others :

Thanks! The ones that you didn't change weren't a big deal anyways, I can work around them easily.

[thefox]

OK I tried the new version, here are some further suggestions.

- Now all labels are followed by : in outputs files. Which will create weird labels ending with :: if you try to chain algorithm, but at least it will be visible that you chained algorithms that way.

Yes but then the files will be unusable without modification, so I don't think it's a good thing. Also this happens if the input file has labels ending with ":" in them. So I think you should at least strip the ":" from the end of labels read by the mini assembler, or simply (as a quick fix) strip all extra ":" from end of a label when outputting them.

- You can compress using only a single algorithm with the "fix algorithm" -fa option, followed by the number of the algorithm you want to use. I know numbers suck, but I wanted to keep it generic, that way any algorithms can be removed or added in a completely generic way. Calling them by name would have been possible but I'm lazy. In another version pehaps.

If -fa is used, it would be nice if it also didn't output "no_coding.asm" file.

- You can force the output to the file you desire with the -o option. It's recommended to use this alongside with -fa, else you'd end up with a single file compressed with the last algorithm, each algorithm overwriting output from the previous one.

I'd prefer if it was possible to set the extension of the file on the command line (e.g. "-o foo.s") instead of it always appending ".asm" at the end of the filename.

[Bisqwit]

Here are some test results profiling Bregalad's CompressionTools for actual data in my Simon's Quest Retranslation.

The methods listed in the bottom of this table are from CompressionTools version 1.1. The others are the compressors I wrote in the specified Retranslation versions.

Code: Select all

FILE#:          0       1       2       3       4       5       6       7       9       10      11      13      14      15              16
FILE:           blank   title   ending  passwd  passwd2 menu    crPalFI crNtaFI crNtaEN srPalFI srNtaFI srNtaEN mapPAL  mapNTA  TOTAL:  +VRAM
--------------- --------------------------------------------    ----------------------- ----------------------- --------------  ------
Uncompressed:   2048    2048    1024    2048    1024    1016    32      1024    1024    32      2048    2048    32      2048    17496   74752
--------------- --------------------------------------------    ----------------------- ----------------------- --------------  ------
RLE:            32      802     531     1524    705     545     33      635     644     32      920     919     33      1266    8621    57280
BitpackRLE:     16      -       -       -       -       -       32      -       -       27      -       -       32      -       -       -
EscapeRLE:      24      803     547     1530    709     549     32      640     649     32      922     921     32      1266    8656    -
BytePair:       1026    -       685     1275    662     632     23      681     690     31      1247    1247    31      1585    -       -
RecBytePair:    22      -       469     865     386     344     21      464     484     31      682     682     31      1294    -       -
TinyHuff:       520     949     610     1409    536     567     23      621     630     27      1155    1155    29      1476    9707    -
TinyHuffFixed:  514     985     612     1449    575     577     18      682     691     24      1293    1292    26      1486    10224   -
Huffman:        -       1070    799     1450    717     734     67      721     731     53      1185    1184    56      1686    -       -
ROM_LZ77:       128     772     690     1148    542     619     32      648     669     34      1040    1036    34      923     8315    63620
ROM_7bit_LZ77   68      -       -       -       -       -       28      -       -       32      -       -       32      -       -       -
RAM_LZ77:       34      554     557     728     410     395     26      555     572     34      704     703     34      808     6114    54844
StaticDic:      145     -       524     943     500     428     24      550     565     32      799     799     32      1191    -       -
--------------- --------------------------------------------    ----------------------- ----------------------- --------------  ------
Tokumaru:       147     823     569     1663    757     559*    -       686     702     -       113     1129    -       1385    -       44472*
pucrunch**:     301     710     676     779     605     555     314     689     710     325     787     786     325     951     8513**  -
appack.exe:     31      469     435     533     343     295     43      435     460     55      519     518     54      718     4908    35196
--------------- --------------------------------------------    ----------------------- ----------------------- --------------  ------
1.3.8:          33      679     467     1487    613     484     34      616     625     33      880     879     34      525     7389    57341
2.3.1:          45      377     467     1168    532     311     21      616     625     33      870     869     34      525     6493    57312
--------------- --------------------------------------------    ----------------------- ----------------------- --------------  ------
Deflate:        16      435     418     468     324     259     20      384     397     32      492     491     703     435     4523    35054
--------------- --------------------------------------------    ----------------------- ----------------------- --------------  ------

Deflate is provided for curiosity only. Like RAM_LZ77, it is way too complex to be implemented on NES.
Tokumaru crashed for 32-byte files, and failed to work for the 1016-byte file. Increasing the size to 1024 produced the result of 559 bytes. It also complained that the 74 kilobyte VRAM file contained too many tiles, but hacking the source code increasing the limit from 512 tiles to 10000 tiles produced a successful compression (don't know if it is decompressable).
pucrunch includes a decompressor in each data, and thus has a large starting cost.

From the CompressTools selection, there were quite a few codecs that failed to apply to one or more files, and as such they cannot be said to be general-purpose. And EscapeRLE got a "verify error" for files 0 and 1 (harmless, as the data was valid).

The compression methods marked with a mere version number (1.3.8 and 2.3.1) stand for the compression method I wrote myself for Simon's Quest. Turns out it is not too bad a general-purpose compressor, though it is mostly oriented for compression of nametables. I also profiled it for the game's VROM data (with duplicate tiles removed), and it achieved a performance somewhere between ROM_LZ77 and RAM_LZ77.

The compression format, basically RLE with tweaks, is documented below:

Code: Select all

        ; LIT: Input byte c = 0..3F:
        ;        Put next (c+0x01) bytes verbatim, except BACKWARDS
        ; END: Input byte c = 40:
        ;        End stream
        ; SEQ: Input byte c = 41..7F:
        ;        Read byte b
        ;        Put b, (c-0x3F) times; add 1 to b after each iteration
        ; DBL: Input byte c = 80..9F:
        ;        Read byte b1
        ;        Read byte b2
        ;        Put b1, (c-0x7D) times; swap b2 and b1 after each iteration
        ; RUN: Input byte c = A0..FF:
        ;        Read byte b
        ;        Put b, (0x101-c) times

The earlier version was almost the same, except RUN was 80..FF and DBL did not exist.
You can find the source code to the decompressor for the 1.3.8 version here. It assembles into 92 bytes, and uses 4 bytes from zeropage for parameters. It decompresses directly into PPU's $2007 port.
The 2.3.1 version can be found here. It assembles into 123 bytes.
You can find an example compressor here: http://bisqwit.iki.fi/src/nes-ppu_rlein ... ss.php.txt

If you wish to perform independent tests, you can download the files I used for testing here.

[Dwedit]

I'd say test out APLIB, pucrunch, and LZMA (same compression as 7-zip) as well. APLIB is fast for decompressing, since it uses a nice trick where 8-bit values are always byte aligned. Obviously not as fast as RLE, but still good.

APLIB is one of the best I've seen that has very low system requirements to decompress.

Also test out "tokumaru_tile_compression" for graphics.

[Bisqwit]

LZMA actually produced just 10 bytes smaller total than Deflate when I tested, for this data.
I should test APLIB, or rather my reimplementation thereof. I'm not sure how efficient it would be to rewrite it for 6502 though. The decompressor is neat and nice in 8086 assembler, but...
And I'll see about Tokumaru's project, as well. Thanks for the suggestion.

EDIT: Added Tokumaru.
APLIB's algorithm (which is LZ-based by the way) is a bit of trouble due to its thousands of options, and the fact that the choice of those options very much determines how large the decompressor will be. My COM file packer tests those options in conjuction with the decompressor size and chooses the smallest combination. Oh, and LZ-based are trouble for 6502 in general.
(Disclaimer: My knowledge of APLIB comes almost entirely through reverse engineering the executable compressor of aPACK.)

[Dwedit]

If pucrunch was displaying "standalone decompressor required", then it wasn't including any decompression code.

[thefox]

APLIB's algorithm (which is LZ-based by the way) is a bit of trouble due to its thousands of options, and the fact that the choice of those options very much determines how large the decompressor will be. My COM file packer tests those options in conjuction with the decompressor size and chooses the smallest combination. Oh, and LZ-based are trouble for 6502 in general.
(Disclaimer: My knowledge of APLIB comes almost entirely through reverse engineering the executable compressor of aPACK.)

There's a 6502 decompressor for apLib at http://jiggawatt.org/badc0de/decrunch/a ... h_6502.asm, it works well enough (I used it in STREEMERZ). I'm not sure what compression options you're talking about, appack.exe I've been using (from apLib's "examples" directory) didn't give me any.

[Bisqwit]

If pucrunch was displaying "standalone decompressor required", then it wasn't including any decompression code.

It never did, unless I missed it.

There's a 6502 decompressor for apLib at http://jiggawatt.org/badc0de/decrunch/a ... h_6502.asm, it works well enough (I used it in STREEMERZ). I'm not sure what compression options you're talking about, appack.exe I've been using (from apLib's "examples" directory) didn't give me any.

Interesting.
The compression options may have been of my adding, then. It has been years.

You can find my reimplementation of aPack, suitable for small .com files, here: http://bisqwit.iki.fi/src/apacker-com.cc
To compile it, you need a C++ compiler and a libc implementation that supports positional arguments syntax for printf (e.g. %$4d). At runtime, it requires nasm.

Some tests here, using my apacker reimplementation, aPACK v1.00, and appack.exe from aPLib v1.01, for a few DOS programs I've written in the last few years. All results include the decompressor code.

Code: Select all

|| What    || Original || apacker-com || aPACK || appack
| synhili  | 3961      | 2610         | 2638    | 2759*
| jainput  | 9679      | 5384         | 5826    | 5915*
| inputter | 1620      | 1396         | 1403    | 1313*

Links: synhili, jainput, inputter
(Note: appack results do NOT include a decompressor. A decompressor weighs about 80-100 bytes.)

The options include, if I read my code correctly:
- Whether a byte that is just the previous byte plus an increments of +1, -1, or +2, is encoded efficiently as a gamma
- Whether x86 near jumps (JMP NEAR) are translated into absolute format or not
- Whether x86 near calls (CALL NEAR) are translated into absolute format or not
- Whether type-2 codepairs (appends) are supported or not
- 0, 1 or 2 special efficiently encoded choosable constant bytes (aplib has always one, which is a zerobyte). Removing the one extends the range of the special short-offset copy by one byte.
- Whether all literals are stored in a separate table, and literals in actual data are encoded as gamma offsets to that table.

[Bregalad]

I just want to say I released version 1.2, which will be available on Romhacking.net in a day or so.

I implemented why thefox suggested (I am really sorry to have taken more than 2 months to do this, especially considering it took me about 1 hour to do it but you know December-January-February is usually one of those super busy periods of the year), and I fixed a bug bisqwit had found.

I want to thank you both for having helped to improve CompressTools.

Also,

Like RAM_LZ77, it is way too complex to be implemented on NES.

RAM_LZ77 is not too complex for the NES, it can just use a lot of RAM, which would probably end up needing external SRAM.
If the source code is modified to force 8-bit references to the sliding window, then the coded could eat only 256 bytes of RAM, which is acceptable even without external SRAM. However :
1) the codec is likely to work very poorly with only 8-bit references
2) In order to decode block N you have to decode blocks 0, 1, .... upto N, so if N is large it can be very time consuming. It is currently the only algorithm in CompressTools that can't allow random access to individual blocks when decoding

The compression methods marked with a mere version number (1.3.8 and 2.3.1) stand for the compression method I wrote myself for Simon's Quest. Turns out it is not too bad a general-purpose compressor, though it is mostly oriented for compression of nametables. I also profiled it for the game's VROM data (with duplicate tiles removed), and it achieved a performance somewhere between ROM_LZ77 and RAM_LZ77.

This sounds interesting. It sounds like this works very well with nametables, as it can also encode alternate patterns like ABABAB very efficiently.
I think daisy chaining any RLE variant over a BytePair encoding will give a very similar result.

I am worried about the verify error you get with Escape RLE.
This means that the data was encoded, then decoded again, and that the result was different from the original data. At least my algorithms does this, instead of only encoding, like some compressors does ^^

EDIT : Also, please not that now, to force an algorithm, you have to use names, not numbers (which makes more sense). For example what was -fa 0 in version 1.1 should be -fa RLE in version 1.2

[Bisqwit]

I am worried about the verify error you get with Escape RLE.
This means that the data was encoded, then decoded again, and that the result was different from the original data. At least my algorithms does this, instead of only encoding, like some compressors does ^^

The problem with EscapeRLE appears to be with runs that are >= 129 bytes long (i.e. they encode as $80..$FF). Your decoder reads them wrong.
A minimal test case that invokes this error is a file that contains 129 bytes of NUL.

[Bregalad]

Yeah, good old "bug" of java forcing bytes to signed.
I'll fix this right away, thank you very much.