mca: MacroCell Archiver

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
blah
Posts: 313
Joined: April 9th, 2016, 7:22 pm

mca: MacroCell Archiver

Post by blah » December 12th, 2023, 7:32 am

I was working on a large (secret) project, and wanted to save a bunch of intermediary versions, kind of like a source code version control system. The way I did this was simply to copy the entire file every time. That means if you make a 1-cell change to a large pattern, and save it, that 1-cell change will consume a similarly large space on disk. General-purpose text difference compression, like they use for source code, won't help you; that 1 cell change may create a new hash-node in the middle of the file, which kicks up the index of every node after it, resulting in an arbitrarily large amount of lines that have changed.

The nature of a canonicalised quadtree, as used by HashLife and the .mc format itself, makes it trivial to encode the difference efficiently. So I created a program that takes multiple .mc files and puts them all into a single hash-table data structure, each associated with its own root node and comment metadata. Here's a demonstration, compressing some files for my project:

Code: Select all

$ ls -sh *.mc
272K w-0000-2023-07-22.mc  340K w-0007-2023-08-19.mc  444K w-000E-2023-09-24.mc
276K w-0001-2023-07-24.mc  356K w-0008-2023-08-22.mc  464K w-000F-2023-10-02.mc
280K w-0002-2023-07-26.mc  360K w-0009-2023-08-24.mc  468K w-0010-2023-10-13.mc
300K w-0003-2023-08-03.mc  364K w-000A-2023-08-28.mc  468K w-0011-2023-10-29.mc
312K w-0004-2023-08-07.mc  404K w-000B-2023-09-03.mc  464K w-0012-2023-10-30.mc
316K w-0005-2023-08-10.mc  416K w-000C-2023-09-15.mc  468K w-0013-2023-11-22.mc
336K w-0006-2023-08-18.mc  428K w-000D-2023-09-18.mc
$ mca *.mc archive.mca
$ ls -sh archive.mca 
616K archive.mca
$ cat *.mc >naive
$ ls -sh naive 
7.4M naive
$ gzip naive
$ gzip archive.mca 
$ ls -sh archive.mca.gz 
184K archive.mca.gz
$ ls -sh naive.gz 
2.3M naive.gz
The files can be extracted with the command "mca archive.mca". It doesn't work very well for compressing unrelated pattern files, though.

The program source is attached. Compile mca.c (which is written in C89). There's no install script; just move it to $PATH yourself. There are also 2 man pages provided; one for the program, and one for the format, in case you want to implement/modify it.

(And before anyone brings it up: Yes, I know about Golly's "timeline" feature. It can't be run from shell scripts, as far as I'm aware, it's limited in scope, and it isn't documented seemingly at all.)
Attachments
mca.tar.gz
Source code, along with test program.
(12.24 KiB) Downloaded 59 times
succ

Post Reply