GT1 compression

Using, learning, programming and modding the Gigatron and anything related.
Forum rules
Be nice. No drama.
Post Reply
lb3361
Posts: 367
Joined: 17 Feb 2021, 23:07

GT1 compression

Post by lb3361 »

One of Marcel's comments in the ROM code suggests to look into pucrunch or eximozer for ways to compress GT1 files and fit more in the ROM. As a reference point, simply using gzip on at67's repository of GT1 files https://forum.gigatron.io/viewtopic.php ... pbox#p3958 reduces the code size by about a factor two. However decoding gzipped files on the Gigatron is challenging because the gzip bitstream must be processed one bit at a time (something the Gigatron does not do very well) and because there is no way around using a fair amount of memory to store the Huffman tables that are provided at the beginning of the gzipped data. Memory is the most fundamental problem here. There is simply no area of memory that can safely be used for this purpose with all GT1 files. Therefore one would need each compressed file to specify which pieces of memory are safe for this use, etc. Otherwise there is very little memory available to the SYS_Exec system call: sysArgs[0-7], sysFn, vAC, and that's about it. All this made GT1 compression look very challenging.

I learned a couple weeks ago that it is possible to achieve decent compression without using a bitstream. Yann Collet's LZ4 algorithm is byte based https://github.com/lz4/lz4, and Charles Bloom's LZNIB algorithm uses 4 bits nibbles http://cbloomrants.blogspot.com/2019/01 ... rithm.html.

The LZ4 compression essentially alternates literal runs, that is sequence of uncompressed bytes, and match runs that copy data located at a specific offset from the current address. Interestingly, LZ4 achieves decent results by encoding these offsets with two bytes, which are enough to access any point of the Gigatron address space. In fact we can make this scheme Gigatron-friendly by making sure that runs do not cross page boundaries, and by encoding the match offsets using separate page offsets and byte offsets without dealing with carries. One also need codes to change the current address between GT1 segments. I tried implementing this and obtained encouraging results.

Then I remembered that LZNIB also uses direct matches that do not code an offset but reuse the offset of the last match. Although Charles Bloom made clear that properly using direct matches requires a much more complicated search at compression time, this search gets easier when matches cannot cross page boundaries because we can process each page separately. After a little bit of experimentation, I restricted the page offsets to the 0-127 range and used the 128-255 range to represent short offsets with single byte instead of two.

See https://github.com/lb3361/gigatron-rom/ ... Utils/gt1z for a complete encoder and decoder in C++ (see function "decompress()" for a good idea of how this works.) The compression performance of this scheme is substantially better than LZ4 and on average performs between GZIP -2 and GZIP -3. In the following table, "Apps" refers to all GT1 files in the "Apps" subdirectory of the DEV7ROM, 'Dropbox" refers to at67's GT1 repository, and "Images" is a collection of images encoded as GT1 files. The 'gt1.gz' column uses GZIP -3, the 'gt1.lz4' column uses LZ4 -9. Clearly, compression works much better on the graphics heavy applications found in Dropbox than the more code oriented ones found in Apps.

Code: Select all

+------------------------------------------+----------+----------+----------+----------+
| filename                                 |     size |   gt1.gz |  gt1.lz4 |     gt1z |
+------------------------------------------+----------+----------+----------+----------+
| Apps                                     |   165001 |   -29.3% |   -17.5% |   -26.2% |
| Dropbox                                  |  1240815 |   -56.1% |   -47.7% |   -55.7% |
| Images                                   |   121362 |   -68.0% |   -57.0% |   -62.2% |
+------------------------------------------+----------+----------+----------+----------+
| TOTAL                                    |  1527178 |   -54.1% |   -45.2% |   -53.1% |
+------------------------------------------+----------+----------+----------+----------+
Note that all GT1Z files start with 0x00 0xff which is an unlikely start for a GT1 files. The fun part was to write a version of SYS_Exec that transparently loads either a regular GT1 files or a compressed GT1Z files. I implemented that in DEV7ROM using the FSM approach with a substantially more refined way to create FSM microcode https://forum.gigatron.io/viewtopic.php ... =FSM#p3714. I was then able to reintroduce Pictures (about 11k, uncompressed), and add Frogstroll (about 9k, compressed to 1.6K) and the Shuttle image (19k, compressed to 2.2K). The next step is to properly compressed the pictures in Pictures :-)
gt1z-rom.png
gt1z-rom.png (89.45 KiB) Viewed 738 times
.

I am willing to port this to the official DEVROM is there is demand. Note that this requires two important changes, increasing MaxTicks to 15, and using the FSM approach despite its slightly controversial "bge([fsmState])" instruction.

For the curious, the sys_Exec code is at https://github.com/lb3361/gigatron-rom/ ... m.py#L7072 and https://github.com/lb3361/gigatron-rom/ ... .py#L10475.
Last edited by lb3361 on 13 Jan 2024, 23:37, edited 2 times in total.
petersieg
Posts: 109
Joined: 28 Jun 2023, 09:06

Re: GT1 compression

Post by petersieg »

That looks interesting and promising!
I think, it would be good to have more apps in the rom and the ability to transparently load (un)compressed gt1 programs.

Thx, Peter
lb3361
Posts: 367
Joined: 17 Feb 2021, 23:07

Re: GT1 compression

Post by lb3361 »

Following on this work.

The Gigatron ROM does not just contain GT1 files but also images and basic programs using ad-hoc schemes to encode them economically and load them as needed. Instead, we can encode this data as GT1 files, compress them as GT1Z files, and load them using SYS_Exec.

For instance the Racer program depends on a 256x16 cityscape image stored in the ROM. This image is reloaded into the screen whenever the game restarts. In the normal ROM, this image is encoded by packing groups of four pixels into three bytes and using SYS_Unpack_54 to decode this. Instead we can now convert the image into a GT1 file, compress it as a GT1Z file, and read it with SYS_Exec. So I quickly put together two python programs in https://github.com/lb3361/gigatron-rom/ ... ster/Utils:
  • imgtogt1.py reads an image file, scales it to the desired size (default 160x120), quantize the colors to the Gigatron color palette, and produces a GT1 file that loads the image into the screen buffer (default 0x800). In the case of the Racer cityscape, the GT1Z file size is competitive with the original PNG file size (albeit with less colors) and about three times smaller than the usual 4 pixels-in-3-bytes encoding.

    Code: Select all

       1122  Horizon-256x16.png
       4147  Horizon-256x16.gt1
        988  Horizon-256x16.gt1z
      12288  Horizon-256x16.rgb.     (raw image, three bytes per pixel)
       3072  Horizon-256x16.packed34 (gigatron colors, four pixels in three bytes)
    
    Horizon-256x16.png
    Horizon-256x16.png (1.1 KiB) Viewed 678 times
     
    Or course we then need to change Racer.gcl to use SYS_Exec to load the cityscape. But this is in fact easier than the previous code.

     
  • gtbtogt1.py does the same thing for TinyBasic programs. It also adds an executable stub that locates TinyBasic, loads it, and runs the program. This makes it really easy to start TinyBasic program. But it also offers opportunities for GT1Z compression. Alas the first results were a bit disappointing:

    Code: Select all

      3506  TicTac_v1.gtb
      2059  TicTac_v2.gt1
      1647  TicTac_v2.gt1z
       975 TicTac_v2.gtb.gz     (comparison: compressing the GTB with GZIP -3)
      1408 TicTac_v2.gtb.lz4.   (comparison: compressing the GTB with LZ4)
    
    Then I realized that TinyBasic programs are stored as lots of little disconnected segments (one per basic line). In fact neither LZ4 nor GZIP work very well when we compress the GT1 file instead of the Basic text contained in the GTB files:

    Code: Select all

      1462 TicTac_v2.gt1.gz
      1775 TicTac_v2.gt1.lz4
    
    So I added an option to the GT1Z program that fills the space between segments with zeroes, as long as the segments are in the same page. With this option, we get file sizes that are at least competitive with those achieved by LZ4 on the basic text. The GZIP performance seems out of reach because it benefits from the Huffman code ability to leverage the limited character set and encode literal data with less than 8 bits per characters. Neither GT1Z nor LZ4 can do this.

    Code: Select all

      1397  TicTac_v2.gt1z
    
These changes save space in the ROM. But I also like them because they replace a lot of complicated ad-hoc code by a single approach. I installed this new ROM in https://www.gigatron128k.com and was happy to see that everything looks the same even though there is now about 6KB of free space for future purposes.
Last edited by lb3361 on 04 Jan 2024, 17:56, edited 1 time in total.
petersieg
Posts: 109
Joined: 28 Jun 2023, 09:06

Re: GT1 compression

Post by petersieg »

Hi.

That looks very interesting. I like that lean and mean solutions. I also like to have a ROM, that containts more nice little games (Tetronis, Bricks, Snake, ...) and that is able to load uncompressed and compressed gt1 files.
Looking forward to such a new ROM(8) somewhere down the new year ;)

BTW: The link in the last post to the new online emulator is wrong!

Excellent work!
Peter
lb3361
Posts: 367
Joined: 17 Feb 2021, 23:07

Re: GT1 compression

Post by lb3361 »

petersieg wrote: 04 Jan 2024, 15:26 I also like to have a ROM, that containts more nice little games (Tetronis, Bricks, Snake, ...) and that is able to load uncompressed and compressed gt1 files. Looking forward to such a new ROM(8) somewhere down the new year ;)
SYS_Exec in the current dev7 rom already can load either compressed or uncompressed gt1 files. The current selection contains Apple-1 and MSBASIC which do not compress very well. Removing them would make space for three or four substantial games. Changing the selection of programs in a ROM, one must just do two things: (1) change the list of programs in the Makefile (see https://github.com/lb3361/gigatron-rom/ ... r/Makefile, both gt1 and gt1z work), and (2) change the MainMenu (see https://github.com/lb3361/gigatron-rom/ ... inMenu.gcl). Adding rows to the main menu is not as simple as it should...
petersieg wrote: 04 Jan 2024, 15:26 BTW: The link in the last post to the new online emulator is wrong!
Fixed.
petersieg
Posts: 109
Joined: 28 Jun 2023, 09:06

Re: GT1 compression

Post by petersieg »

Can not report this spam post, when I click on !, I get: HTTP 7404 Not, not, not, not, not, not found

Peter
at67
Site Admin
Posts: 647
Joined: 14 May 2018, 08:29

Re: GT1 compression

Post by at67 »

It's been dealt with.
Post Reply