ROM compression software

[lynchaj]

Hi,

I have an idea/question for the RomWBW community. Recently I was scrolling through a RomWBW ROM image on my EPROM programmer software. I noticed what seems to be large swathes of repeating data values like $00 and $E5. I estimated that roughly 25%-33% of the ROM capacity was either empty space or easily compressible data.

What is your opinion of implementing a ROM compression software to act as a CBIOS software shim between the BDOS and the actual ROM to implement a virtual memory drive. I think the interface would work much like the current CBIOS track/sector routines but intercept those calls and convert them to/from a compressed ROM image. I am thinking lightweight compression algorithms like Run-Length-Encoding, Huffman encoding, or Limpel-Ziv-77

Is this practical and/or feasible? I am sure its possible because I think Linux currently has similar compressed ROM file systems. Also I recall third party MS-DOS software which allow for compressed disk file systems. Many retrobrew computers are roughly equivalent with respect to processor and memory capability/capacity to early IBM PCs. If this software worked it could potentially realize dramatically increased ROM drive capacity without changing hardware.

https://winworldpc.com/product/stacker/40#

Thanks, Andrew Lynch

[wwarthen]

This is an interesting idea, but may be more complicated to achieve than is obvious.

RomWBW constructs the ROM disk images when building RomWBW using cpmtools. So, in addition to the Z80 code to decompress sectors, there would need to be a way to do the compression when creating the ROM images.

Also, keep in mind that (thanks to Phil), FLASH chips can now act as regular writable disk drives. So, implementing this would ideally mean handling writing as well as reading.

I am really not familiar with the techniques used to implement compressed storage, so perhaps there is a straightforward way to do all this. It seems complicated to use variable length blobs for fixed length sectors. I wonder if anyone has any source code references for something like this.

-Wayne

[lynchaj]

Hi
I had some ideas about implementing ROM compression and went so far as to find some RLE code examples. The compression techniques are well documented since they are so ancient. I think most people with a computer science or computer engineering degree will recognize these techniques. Run-Length-Encoding (not RLL, that's something else entirely) is probably the most lightweight and easiest to implement at least in C. Z80 assembler may be another matter. However the principles are the same.

Yes, this would require at least a couple pieces of software. First would be a stand alone compression utility which takes CP/M files and writes them in compressed ROM format. Second would be a shim code to intercept the BDOS calls to CBIOS (track, sector, etc.) and convert those into pointers into the compressed ROM data store.

For the shim code, my initial implementation idea was to use a linked list of linked lists. The first linked list would be virtual "tracks" and each record would have a pointer to the next record until it reaches the end. In each track record there would be another linked list for the sectors. You would traverse the track link list first, then the sector linked list. When you get to the desired track & sector record you'd find your variable length data blob, pass it to the RLE decoder and out pops the virtual sector (or LBA), pass control back to BDOS and it continues. The danger with RLE is under certain conditions the compressed sector can actually be longer than the uncompressed sector so there would need to be a flag distinguishing a records data blob as either compressed or non-compressed. It's the same approach for LZ-77 or Huffman encoding or whatever compression algorithm is finally chosen. The key is the algorithm has to be lightweight enough to run efficiently on a 4 MHz Z80 so that really limits the choices.

Were the CP/M CBIOS written in C, implementing this would be almost trivial. I am sure there are people on this list who could knock out a working prototype in an evening or two. However being in 8080/Z80 assembler this is a bit more complex. My inspiration for this idea comes from Linux because there are two or three different compressed ROM file systems like ROMFS and CRAMFS. I think there is another one too but I can't remember the name right now. These are somewhat different than what I am proposing because they operate at the file system level where I am suggesting a virtual disk track/sector approach but the concepts are similar.

During the latter days of the IBM PC there were a flurry of compressed disk drivers like Stacker, DoubleSpace, etc. I had at one point a hardware compression coprocessor for a disk compression software and it was the coolest thing back in the day. I forget which one but there were at least a couple on the market. I think they're totally obsolete now though but the idea is still good for small storage spaces like ROMs

https://forum.winworldpc.com/discussion/10401/software-spotlight-drive-compression-tools

I had kind of shelved the idea as impractical to implement because I just am to swamped right now to dedicate the time needed. Also I am not the best coder and I prefer hardware design. Really I don't want to put aside all the other things I am currently working on to do this project instead. Rather then let the idea just disappear into the vapor I thought to post it here in case there is someone out there just waiting for an idea such as this to come along

Thanks for listening. I appreciate the chance to gather my thoughts. I hope this benefits someone eventually.

Andrew Lynch

[wwarthen]

OK, this generally makes sense to me. As you say, the compression algorithms themselves are pretty well known. I am actually less concerned about that than the management of the variable length sector data. The linked list approach would be fine for static ROMs. For writable ROMs, it gets messier to manage the free space as things are updated. Would not really need to support writable ROMs though.

Anyway, a reasonable concept. My to do list has too many higher priority things on it to work on this in the foreseeable future. So, if any adventurous coder wants to pursue this, I would be happy to support the RomWBW integration itself.

-Wayne

[feilipu]

Just to chime in on a potential path forward here.

The current best practice for asymmetrical 8080 / Z80 compression is Einar Saukas ZX0.

A comparison with other compressors (courtesy of introspec/spke) can be seen here.

z88dk now uses ZX0 to compress the data sections for all ROM builds, so there's tested compression and decompression code in the repository that can be used. ZX7 is also available in the repository as the old standard.

So this is not a whole solution for RomWBW, but at least the compression / decompression engines are done.
And the project reduces to how to implement into RomWBW.

Phillip

[wwarthen]

Good info Phillip. I should have mentioned previously that RomWBW does already have an LZSA2 decompression engine embedded thanks to Phil Summers. Font data within RomWBW is compressed when built and then decompressed when loaded to a video card. ZX0 may be superior, but the biggest hurdle is really the code to wrap all of this for a ROM disk.

Thanks,

Wayne

[lynchaj]

Hi
Yes, the difficult part is making the linked list data structure join up to the CBIOS interface. The current CBIOS takes advantage of the regular size of tracks and sectors to find data in the ROM. With compression the data blob size will vary so you need a way to navigate in the data structure using pointers to where the data blobs are stored.

There is a specific name for this data structure (more specific than linked list) but I cannot remember what it is called. It's not a heap or a stack and more than a linked list but whatever it is actually called isn't important.

An additional complicating factor is that the memory where the data structure is stored is not linear so you'd need a special two part pointer; one part (say 6 bits) to tell you which 32KB ROM page to index using the MPCLs and a 15 bit pointer to where the data blob is in the data structure (stored in the 32KB page). A small but important detail. Also boundary conditions for 32KB pages would need consistent rules.

If we had nice linear 32 bit or 64 bit memory this data structure would be trivial because it would be just a basic linked list (track) of linked lists (sectors) with data blobs as one of the record fields. Maybe a couple of other attribute flags (compressed vs non-compressed). Literally a freshman comp sci homework assignment in C or whatever. 8080/Z80 assembler makes it a bit more complicated but the concept is identical.

So that was my idea on how to proceed. Write the prototype in C code assuming linear memory. Then convert the linear memory data structure to the 32KB ROM page format with the two part pointer. Get that working and once completed make it the compression utility to create a compressed ROM image from data files like cpmtools does now. Then re-write the program in Z80 assembler as decompression only for the CBIOS. Probably there are people talented enough to go directly to Z80 assembler but I am not one of them. I like to build things in small increments and iterate. It's just how my brain works.

Thanks, Andrew Lynch

PS, Personally, I don't think it is practical to support read/write on the compressed data structure. I am thinking it would be "write once, read many" where you use the compressed ROM utility to write the data structure one time, burn it in to ROM, and then use the CBIOS to extract virtual sectors as needed. No updating the sectors once in ROM. For simplicity's sake, making the ROM image read/write would be a lot more complicated and require clean/dirty sector tagging and probably a repack utility. Ugh. Save that for the advanced studies...