aboutsummaryrefslogtreecommitdiff
path: root/tools/rasm/ZX0-main
diff options
context:
space:
mode:
authorJuan J. Martinez <jjm@usebox.net>2022-09-06 07:37:20 +0100
committerJuan J. Martinez <jjm@usebox.net>2022-09-06 07:37:20 +0100
commit30bf0f51335e87812ffeb54e9437f0b6a1514d67 (patch)
tree9c85a2de53b4da69fcfaa84488cc6c12ebd3e5d0 /tools/rasm/ZX0-main
parentd8990284057e6401d0374f439df51879595d804d (diff)
downloadubox-msx-lib-30bf0f51335e87812ffeb54e9437f0b6a1514d67.tar.gz
ubox-msx-lib-30bf0f51335e87812ffeb54e9437f0b6a1514d67.zip
Updated rasm to 1.7
Diffstat (limited to 'tools/rasm/ZX0-main')
-rw-r--r--tools/rasm/ZX0-main/LICENSE29
-rw-r--r--tools/rasm/ZX0-main/README.md369
-rw-r--r--tools/rasm/ZX0-main/src/compress.c164
-rw-r--r--tools/rasm/ZX0-main/src/memory.c75
-rw-r--r--tools/rasm/ZX0-main/src/optimize.c137
-rw-r--r--tools/rasm/ZX0-main/src/zx0.h46
6 files changed, 820 insertions, 0 deletions
diff --git a/tools/rasm/ZX0-main/LICENSE b/tools/rasm/ZX0-main/LICENSE
new file mode 100644
index 0000000..a0b5162
--- /dev/null
+++ b/tools/rasm/ZX0-main/LICENSE
@@ -0,0 +1,29 @@
+BSD 3-Clause License
+
+Copyright (c) 2021, Einar Saukas
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+1. Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+2. Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
+
+3. Neither the name of the copyright holder nor the names of its
+ contributors may be used to endorse or promote products derived from
+ this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/tools/rasm/ZX0-main/README.md b/tools/rasm/ZX0-main/README.md
new file mode 100644
index 0000000..404ac54
--- /dev/null
+++ b/tools/rasm/ZX0-main/README.md
@@ -0,0 +1,369 @@
+# ZX0
+
+**ZX0** is an optimal data compressor for a custom
+[LZ77/LZSS](https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Storer%E2%80%93Szymanski)
+based compression format, that provides a tradeoff between high compression
+ratio, and extremely simple fast decompression. Therefore it's especially
+appropriate for low-end platforms, including 8-bit computers like the ZX
+Spectrum.
+
+
+## Usage
+
+To compress a file, use the command-line compressor as follows:
+
+```
+zx0 Cobra.scr
+```
+
+This will generate a compressed file called "Cobra.scr.zx0".
+
+Afterwards you can choose a decompressor routine in assembly Z80, according to
+your requirements for speed and size:
+
+* "Standard" routine: 69 bytes only
+* "Turbo" routine: 128 bytes, about 20% faster
+* "Mega" routine: 414 bytes, about 25% faster
+
+Finally compile the chosen decompressor routine and load the compressed file
+somewhere in memory. To decompress data, just call the routine specifying the
+source address of compressed data in HL and the target address in DE.
+
+For instance, if you compile the decompressor routine to address 65000, load
+"Cobra.scr.zx0" at address 51200, and you want to decompress it directly to the
+screen, then execute the following code:
+
+```
+ LD HL, 51200 ; source address (put "Cobra.scr.zx0" there)
+ LD DE, 16384 ; target address (screen memory in this case)
+ CALL 65000 ; decompress routine compiled at this address
+```
+
+It's also possible to decompress data into a memory area that partially overlaps
+the compressed data itself (only if you won't need to decompress it again later,
+obviously). In this case, the last address of compressed data must be at least
+"delta" bytes higher than the last address of decompressed data. The exact value
+of "delta" for each case is reported by **ZX0** during compression. See image
+below:
+
+```
+ |------------------| compressed data
+ |---------------------------------| decompressed data
+ start >> <--->
+ delta
+```
+
+For convenience, there's also a command-line decompressor that works as follows:
+
+```
+dzx0 Cobra.scr.zx0
+```
+
+
+## Performance
+
+The **ZX0** optimal compressor algorithm is fairly complex, thus compressing
+typical files can take a few seconds. During development, you can speed up this
+process simply using **ZX0** in "quick" mode. This will produce a non-optimal
+larger compressed file but execute almost instantly:
+
+```
+zx0 -q Cobra.scr
+```
+
+This way, you can repeatedly modify your files, then quickly compress and test
+them. Later, when you finish changing these files, you can compress them again
+without "quick" mode for maximum compression. Notice that using "quick" mode
+will only affect the size of the compressed file, not its format. Therefore
+all decompressor routines will continue to work exactly the same way.
+
+Fortunately all complexity lies on the compression process only. The **ZX0**
+compression format itself is very simple and efficient, providing a high
+compression ratio that can be decompressed quickly and easily. The provided
+**ZX0** decompressor routines in assembly Z80 are small and fast, they only use
+main registers BC, DE, HL, A and optionally alternate register A' (use the
+backwards variant to avoid using A'), consume very little stack space and does
+not require additional decompression buffer.
+
+The provided **ZX0** decompressor in C writes the output file while reading the
+compressed file, without keeping it in memory. Therefore it always use the same
+amount of memory, regardless of file size. Thus even large compressed files can
+be decompressed in very small computers with limited memory, even if it took
+considerable time and memory to compress it originally. It means decompressing
+within asymptotically optimal space and time O(n) only, using storage space O(n)
+for input and output files, and only memory space O(w) for processing.
+
+
+## File Format
+
+The ZX0 compressed format is very simple. There are only 3 kinds of blocks:
+
+* Literal (copy next N bytes from compressed file)
+```
+0 Elias(length) byte[1] byte[2] ... byte[N]
+```
+
+* Copy from last offset (repeat N bytes from last offset)
+```
+0 Elias(length)
+```
+
+* Copy from new offset (repeat N bytes from new offset)
+```
+1 Elias(MSB(offset)) LSB(offset) Elias(length-1)
+```
+
+**ZX0** needs only 1 bit to distinguish between these blocks, because literal
+blocks cannot be consecutive, and reusing last offset can only happen after a
+literal block. The first block is always a literal, so the first bit is omitted.
+
+The offset MSB and all lengths are stored using interlaced
+[Elias Gamma Coding](https://en.wikipedia.org/wiki/Elias_gamma_coding). When
+offset MSB equals 256 it means EOF. The offset LSB is stored using 7 bits
+instead of 8, because it produces better results in most practical cases.
+
+
+## Advanced Features
+
+The **ZX0** compressor contains a few extra "hidden" features, that are slightly
+harder to use properly, and not supported by the **ZX0** decompressor in C. Please
+read carefully these instructions before attempting to use any of them!
+
+
+#### _COMPRESSING BACKWARDS_
+
+When using **ZX0** for "in-place" decompression (decompressing data to overlap the
+same memory area storing the compressed data), you must always leave a small
+margin of "delta" bytes of compressed data at the end. However it won't work to
+decompress some large data that will occupy all the upper memory until the last
+memory address, since there won't be even a couple bytes left at the end.
+
+A possible workaround is to compress and decompress data backwards, starting at
+the last memory address. Therefore you will only need to leave a small margin of
+"delta" bytes of compressed data at the beginning instead. Technically, it will
+require that lowest address of compressed data should be at least "delta" bytes
+lower than lowest address of decompressed data. See image below:
+
+ compressed data |------------------|
+ decompressed data |---------------------------------|
+ <---> << start
+ delta
+
+To compress a file backwards, use the command-line compressor as follows:
+
+```
+zx0 -b Cobra.scr
+```
+
+To decompress it later, you must call one of the supplied "backwards" variants
+of the Assembly decompressor, specifying last source address of compressed data
+in HL and last target address in DE.
+
+For instance, if you compile a "backwards" Assembly decompressor routine to
+address 64000, load backwards compressed file "Cobra.scr.zx0" (with size 2202
+bytes) to address 51200, and want to decompress it directly to the ZX Spectrum
+screen (with 6912 bytes), then execute the following code:
+
+```
+ LD HL, 51200+2202-1 ; source (last address of "Cobra.scr.zx0")
+ LD DE, 16384+6912-1 ; target (last address of screen memory)
+ CALL 64000 ; backwards decompress routine
+```
+
+Notice that compressing backwards may sometimes produce slightly smaller
+compressed files in certain cases, slightly larger compressed files in others.
+Overall it shouldn't make much difference either way.
+
+
+#### _COMPRESSING WITH PREFIX_
+
+The LZ77/LZSS compression is achieved by "abbreviating repetitions", such that
+certain sequences of bytes are replaced with much shorter references to previous
+occurrences of these same sequences. For this reason, it's harder to get very
+good compression ratio on very short files, or in the initial parts of larger
+files, due to lack of choices for previous sequences that could be referenced.
+
+A possible improvement is to compress data while also taking into account what
+else will be already stored in memory during decompression later. Thus the
+compressed data may even contain shorter references to repetitions stored in
+some previous "prefix" memory area, instead of just repetitions within the
+decompressed area itself.
+
+An input file may contain both some prefix data to be referenced only, and the
+actual data to be compressed. An optional parameter can specify how many bytes
+must be skipped before compression. See below:
+
+```
+ compressed data
+ |-------------------|
+ prefix decompressed data
+ |--------------|---------------------------------|
+ start >>
+ <--------------> <--->
+ skip delta
+```
+
+As usual, if you want to decompress data into a memory area that partially
+overlaps the compressed data itself, the last address of compressed data must be
+at least "delta" bytes higher than the last address of decompressed data.
+
+For instance, if you want the first 6144 bytes of a certain file to be skipped
+(not compressed but possibly referenced), then use the command-line compressor
+as follows:
+
+```
+zx0 +6144 Cobra.cbr
+```
+
+In practice, suppose an action game uses a few generic sprites that are common
+for all levels (such as player graphics), and other sprites are specific for
+each level (such as enemies). All generic sprites must stay always accessible at
+a certain memory area, but any level specific data can be only decompressed as
+needed, to the memory area immediately following it. In this case, the generic
+sprites area could be used as prefix when compressing and decompressing each
+level, in an attempt to improve compression. For instance, suppose generic
+graphics are loaded from file "generic.gfx" to address 56000, occupying 2500
+bytes, and level specific graphics will be decompressed immediately afterwards,
+to address 58500. To compress each level using "generic.gfx" as a 2500 bytes
+prefix, use the command-line compressor as follows:
+
+```
+copy /b generic.gfx+level_1.gfx prefixed_level_1.gfx
+zx0 +2500 prefixed_level_1.gfx
+
+copy /b generic.gfx+level_2.gfx prefixed_level_2.gfx
+zx0 +2500 prefixed_level_2.gfx
+
+copy /b generic.gfx+level_3.gfx prefixed_level_3.gfx
+zx0 +2500 prefixed_level_3.gfx
+```
+
+To decompress it later, you simply need to use one of the normal variants of the
+Assembly decompressor, as usual. In this case, if you loaded compressed file
+"prefixed_level_1.gfx.zx0" to address 48000 for instance, decompressing it will
+require the following code:
+
+```
+ LD HL, 48000 ; source address (put "prefixed_level_1.gfx.zx0" there)
+ LD DE, 58500 ; target address (level specific memory area in this case)
+ CALL 65000 ; decompress routine compiled at this address
+```
+
+However decompression will only work properly if exactly the same prefix data is
+present in the memory area immediately preceding the decompression address.
+Therefore you must be extremely careful to ensure the prefix area does not store
+variables, self-modifying code, or anything else that may change prefix content
+between compression and decompression. Also don't forget to recompress your
+files whenever you modify a prefix!
+
+In certain cases, compressing with a prefix may considerably help compression.
+In others, it may not even make any difference. It mostly depends on how much
+similarity exists between data to be compressed and its provided prefix.
+
+
+#### _COMPRESSING BACKWARDS WITH SUFIX_
+
+Both features above can be used together. A file can be compressed backwards,
+with an optional parameter to specify how many bytes should be skipped (not
+compressed but possibly referenced) from the end of the input file instead. See
+below:
+
+```
+ compressed data
+ |-------------------|
+ decompressed data sufix
+ |---------------------------------|--------------|
+ << start
+ <---> <-------------->
+ delta skip
+```
+
+As usual, if you want to decompress data into a memory area that partially
+overlaps the compressed data itself, lowest address of compressed data must be
+at least "delta" bytes lower than lowest address of decompressed data.
+
+For instance, if you want to skip the last 768 bytes of a certain input file and
+compress everything else (possibly referencing this "sufix" of 768 bytes), then
+use the command-line compressor as follows:
+
+```
+zx0 -b +768 Cobra.cbr
+```
+
+In previous example, suppose the action game now stores level-specific sprites
+in the memory area from address 33000 to 33511 (512 bytes), just before generic
+sprites that are stored from address 33512 to 34535 (1024 bytes). In this case,
+these generic sprites could be used as sufix when compressing and decompressing
+level-specific data as needed, in an attempt to improve compression. To compress
+each level using "generic.gfx" as a 1024 bytes sufix, use the command-line
+compressor as follows:
+
+```
+copy /b "level_1.gfx+generic.gfx level_1_sufixed.gfx
+zx0 -b +1024 level_1_sufixed.gfx
+
+copy /b "level_2.gfx+generic.gfx level_2_sufixed.gfx
+zx0 -b +1024 level_2_sufixed.gfx
+
+copy /b "level_3.gfx+generic.gfx level_3_sufixed.gfx
+zx0 -b +1024 level_3_sufixed.gfx
+```
+
+To decompress it later, use the backwards variant of the Assembly decompressor.
+In this case, if you compile a "backwards" decompressor routine to address
+64000, and load compressed file "level_1_sufixed.gfx.zx0" (with 217 bytes) to
+address 39000 for instance, decompressing it will require the following code:
+
+```
+ LD HL, 39000+217-1 ; source (last address of "level_1_sufixed.gfx.zx0")
+ LD DE, 33000+512-1 ; target (last address of level-specific data)
+ CALL 64000 ; backwards decompress routine
+```
+
+Analogously, decompression will only work properly if exactly the same sufix
+data is present in the memory area immediately following the decompression area.
+Therefore you must be extremely careful to ensure the sufix area does not store
+variables, self-modifying code, or anything else that may change sufix content
+between compression and decompression. Also don't forget to recompress your
+files whenever you modify a sufix!
+
+Also if you are using "in-place" decompression, you must leave a small margin of
+"delta" bytes of compressed data just before the decompression area.
+
+
+## License
+
+The **ZX0** data compression format and algorithm was designed and implemented
+by **Einar Saukas**. Special thanks to **introspec/spke** for several
+suggestions and improvements!
+
+The optimal C compressor is available under the "BSD-3" license. In practice,
+this is relevant only if you want to modify its source code and/or incorporate
+the compressor within your own products. Otherwise, if you just execute it to
+compress files, you can simply ignore these conditions.
+
+The decompressors can be used freely within your own programs (either for the
+ZX Spectrum or any other platform), even for commercial releases. The only
+condition is that you must indicate somehow in your documentation that you have
+used **ZX0**.
+
+
+## Links
+
+Projects using **ZX0**:
+
+* [MSXlib](https://github.com/theNestruo/msx-msxlib) - A set of libraries to
+create MSX videogame cartridges, that includes **ZX0** and **ZX7**.
+
+
+Related projects (by the same author):
+
+* [RCS](https://github.com/einar-saukas/RCS) - Use **ZX0** and **RCS** together
+to improve compression of ZX Spectrum screens.
+
+* [ZX1](https://github.com/einar-saukas/ZX1) - A simpler but faster version
+of **ZX0** (**ZX1** sacrifices about 1.5% compression to run about 15% faster).
+
+* [ZX7](https://spectrumcomputing.co.uk/entry/27996/ZX-Spectrum/ZX7) - A widely
+popular predecessor compressor (now superseded by **ZX0**).
+
diff --git a/tools/rasm/ZX0-main/src/compress.c b/tools/rasm/ZX0-main/src/compress.c
new file mode 100644
index 0000000..7feb567
--- /dev/null
+++ b/tools/rasm/ZX0-main/src/compress.c
@@ -0,0 +1,164 @@
+/*
+ * (c) Copyright 2021 by Einar Saukas. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * * The name of its author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "zx0.h"
+
+unsigned char* output_data;
+int output_index;
+int input_index;
+int bit_index;
+int bit_mask;
+int diff;
+int backtrack;
+
+void read_bytes(int n, int *delta) {
+ input_index += n;
+ diff += n;
+ if (*delta < diff)
+ *delta = diff;
+}
+
+void write_byte(int value) {
+ output_data[output_index++] = value;
+ diff--;
+}
+
+void write_bit(int value) {
+ if (backtrack) {
+ if (value)
+ output_data[output_index-1] |= 1;
+ backtrack = FALSE;
+ } else {
+ if (!bit_mask) {
+ bit_mask = 128;
+ bit_index = output_index;
+ write_byte(0);
+ }
+ if (value)
+ output_data[bit_index] |= bit_mask;
+ bit_mask >>= 1;
+ }
+}
+
+void write_interlaced_elias_gamma(int value, int backwards_mode, int invert_mode) {
+ int i;
+
+ for (i = 2; i <= value; i <<= 1)
+ ;
+ i >>= 1;
+ while (i >>= 1) {
+ write_bit(backwards_mode);
+ write_bit(invert_mode ? !(value & i) : (value & i));
+ }
+ write_bit(!backwards_mode);
+}
+
+unsigned char *zx0_compress(BLOCK *optimal, unsigned char *input_data, int input_size, int skip, int backwards_mode, int invert_mode, int *output_size, int *delta) {
+ BLOCK *prev;
+ BLOCK *next;
+ int last_offset = INITIAL_OFFSET;
+ int length;
+ int i;
+
+ /* calculate and allocate output buffer */
+ *output_size = (optimal->bits+25)/8;
+ output_data = (unsigned char *)malloc(*output_size);
+ if (!output_data) {
+ fprintf(stderr, "Error: Insufficient memory\n");
+ exit(1);
+ }
+
+ /* un-reverse optimal sequence */
+ prev = NULL;
+ while (optimal) {
+ next = optimal->chain;
+ optimal->chain = prev;
+ prev = optimal;
+ optimal = next;
+ }
+
+ /* initialize data */
+ diff = *output_size-input_size+skip;
+ *delta = 0;
+ input_index = skip;
+ output_index = 0;
+ bit_mask = 0;
+ backtrack = TRUE;
+
+ /* generate output */
+ for (optimal = prev->chain; optimal; prev=optimal, optimal = optimal->chain) {
+ length = optimal->index-prev->index;
+
+ if (!optimal->offset) {
+ /* copy literals indicator */
+ write_bit(0);
+
+ /* copy literals length */
+ write_interlaced_elias_gamma(length, backwards_mode, FALSE);
+
+ /* copy literals values */
+ for (i = 0; i < length; i++) {
+ write_byte(input_data[input_index]);
+ read_bytes(1, delta);
+ }
+ } else if (optimal->offset == last_offset) {
+ /* copy from last offset indicator */
+ write_bit(0);
+
+ /* copy from last offset length */
+ write_interlaced_elias_gamma(length, backwards_mode, FALSE);
+ read_bytes(length, delta);
+ } else {
+ /* copy from new offset indicator */
+ write_bit(1);
+
+ /* copy from new offset MSB */
+ write_interlaced_elias_gamma((optimal->offset-1)/128+1, backwards_mode, invert_mode);
+
+ /* copy from new offset LSB */
+ if (backwards_mode)
+ write_byte(((optimal->offset-1)%128)<<1);
+ else
+ write_byte((127-(optimal->offset-1)%128)<<1);
+
+ /* copy from new offset length */
+ backtrack = TRUE;
+ write_interlaced_elias_gamma(length-1, backwards_mode, FALSE);
+ read_bytes(length, delta);
+
+ last_offset = optimal->offset;
+ }
+ }
+
+ /* end marker */
+ write_bit(1);
+ write_interlaced_elias_gamma(256, backwards_mode, invert_mode);
+
+ /* done! */
+ return output_data;
+}
diff --git a/tools/rasm/ZX0-main/src/memory.c b/tools/rasm/ZX0-main/src/memory.c
new file mode 100644
index 0000000..be52c3a
--- /dev/null
+++ b/tools/rasm/ZX0-main/src/memory.c
@@ -0,0 +1,75 @@
+/*
+ * (c) Copyright 2021 by Einar Saukas. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * * The name of its author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "zx0.h"
+
+#define QTY_BLOCKS 10000
+
+BLOCK *ghost_root = NULL;
+BLOCK *dead_array = NULL;
+int dead_array_size = 0;
+
+BLOCK *allocate(int bits, int index, int offset, BLOCK *chain) {
+ BLOCK *ptr;
+
+ if (ghost_root) {
+ ptr = ghost_root;
+ ghost_root = ptr->ghost_chain;
+ if (ptr->chain && !--ptr->chain->references) {
+ ptr->chain->ghost_chain = ghost_root;
+ ghost_root = ptr->chain;
+ }
+ } else {
+ if (!dead_array_size) {
+ dead_array = (BLOCK *)malloc(QTY_BLOCKS*sizeof(BLOCK));
+ if (!dead_array) {
+ fprintf(stderr, "Error: Insufficient memory\n");
+ exit(1);
+ }
+ dead_array_size = QTY_BLOCKS;
+ }
+ ptr = &dead_array[--dead_array_size];
+ }
+ ptr->bits = bits;
+ ptr->index = index;
+ ptr->offset = offset;
+ if (chain)
+ chain->references++;
+ ptr->chain = chain;
+ ptr->references = 0;
+ return ptr;
+}
+
+void assign(BLOCK **ptr, BLOCK *chain) {
+ chain->references++;
+ if (*ptr && !--(*ptr)->references) {
+ (*ptr)->ghost_chain = ghost_root;
+ ghost_root = *ptr;
+ }
+ *ptr = chain;
+}
diff --git a/tools/rasm/ZX0-main/src/optimize.c b/tools/rasm/ZX0-main/src/optimize.c
new file mode 100644
index 0000000..263837c
--- /dev/null
+++ b/tools/rasm/ZX0-main/src/optimize.c
@@ -0,0 +1,137 @@
+/*
+ * (c) Copyright 2021 by Einar Saukas. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * * The name of its author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "zx0.h"
+
+#define MAX_SCALE 50
+
+int offset_ceiling(int index, int offset_limit) {
+ return index > offset_limit ? offset_limit : index < INITIAL_OFFSET ? INITIAL_OFFSET : index;
+}
+
+int elias_gamma_bits(int value) {
+ int bits = 1;
+ while (value >>= 1)
+ bits += 2;
+ return bits;
+}
+
+BLOCK* zx0_optimize(unsigned char *input_data, int input_size, int skip, int offset_limit) {
+ BLOCK **last_literal;
+ BLOCK **last_match;
+ BLOCK **optimal;
+ int* match_length;
+ int* best_length;
+ int best_length_size;
+ int bits;
+ int index;
+ int offset;
+ int length;
+ int bits2;
+ int dots = 2;
+ int max_offset = offset_ceiling(input_size-1, offset_limit);
+
+ /* allocate all main data structures at once */
+ last_literal = (BLOCK **)calloc(max_offset+1, sizeof(BLOCK *));
+ last_match = (BLOCK **)calloc(max_offset+1, sizeof(BLOCK *));
+ optimal = (BLOCK **)calloc(input_size, sizeof(BLOCK *));
+ match_length = (int *)calloc(max_offset+1, sizeof(int));
+ best_length = (int *)malloc(input_size*sizeof(int));
+ if (!last_literal || !last_match || !optimal || !match_length || !best_length) {
+ fprintf(stderr, "Error: Insufficient memory\n");
+ exit(1);
+ }
+ best_length[2] = 2;
+
+ /* start with fake block */
+ assign(&last_match[INITIAL_OFFSET], allocate(-1, skip-1, INITIAL_OFFSET, NULL));
+
+ printf("[");
+
+ /* process remaining bytes */
+ for (index = skip; index < input_size; index++) {
+ best_length_size = 2;
+ max_offset = offset_ceiling(index, offset_limit);
+ for (offset = 1; offset <= max_offset; offset++) {
+ if (index != skip && index >= offset && input_data[index] == input_data[index-offset]) {
+ /* copy from last offset */
+ if (last_literal[offset]) {
+ length = index-last_literal[offset]->index;
+ bits = last_literal[offset]->bits + 1 + elias_gamma_bits(length);
+ assign(&last_match[offset], allocate(bits, index, offset, last_literal[offset]));
+ if (!optimal[index] || optimal[index]->bits > bits)
+ assign(&optimal[index], last_match[offset]);
+ }
+ /* copy from new offset */
+ if (++match_length[offset] > 1) {
+ if (best_length_size < match_length[offset]) {
+ bits = optimal[index-best_length[best_length_size]]->bits + elias_gamma_bits(best_length[best_length_size]-1);
+ do {
+ best_length_size++;
+ bits2 = optimal[index-best_length_size]->bits + elias_gamma_bits(best_length_size-1);
+ if (bits2 <= bits) {
+ best_length[best_length_size] = best_length_size;
+ bits = bits2;
+ } else {
+ best_length[best_length_size] = best_length[best_length_size-1];
+ }
+ } while(best_length_size < match_length[offset]);
+ }
+ length = best_length[match_length[offset]];
+ bits = optimal[index-length]->bits + 8 + elias_gamma_bits((offset-1)/128+1) + elias_gamma_bits(length-1);
+ if (!last_match[offset] || last_match[offset]->index != index || last_match[offset]->bits > bits) {
+ assign(&last_match[offset], allocate(bits, index, offset, optimal[index-length]));
+ if (!optimal[index] || optimal[index]->bits > bits)
+ assign(&optimal[index], last_match[offset]);
+ }
+ }
+ } else {
+ /* copy literals */
+ match_length[offset] = 0;
+ if (last_match[offset]) {
+ length = index-last_match[offset]->index;
+ bits = last_match[offset]->bits + 1 + elias_gamma_bits(length) + length*8;
+ assign(&last_literal[offset], allocate(bits, index, 0, last_match[offset]));
+ if (!optimal[index] || optimal[index]->bits > bits)
+ assign(&optimal[index], last_literal[offset]);
+ }
+ }
+ }
+
+ /* indicate progress */
+ if (index*MAX_SCALE/input_size > dots) {
+ printf(".");
+ fflush(stdout);
+ dots++;
+ }
+ }
+
+ printf("]\n");
+
+ return optimal[input_size-1];
+}
diff --git a/tools/rasm/ZX0-main/src/zx0.h b/tools/rasm/ZX0-main/src/zx0.h
new file mode 100644
index 0000000..3b60402
--- /dev/null
+++ b/tools/rasm/ZX0-main/src/zx0.h
@@ -0,0 +1,46 @@
+/*
+ * (c) Copyright 2021 by Einar Saukas. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * * The name of its author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#define INITIAL_OFFSET 1
+
+#define FALSE 0
+#define TRUE 1
+
+typedef struct block_t {
+ struct block_t *chain;
+ struct block_t *ghost_chain;
+ int bits;
+ int index;
+ int offset;
+ int references;
+} BLOCK;
+
+BLOCK *allocate(int bits, int index, int offset, BLOCK *chain);
+
+void assign(BLOCK **ptr, BLOCK *chain);
+
+BLOCK *zx0_optimize(unsigned char *input_data, int input_size, int skip, int offset_limit);
+
+unsigned char *zx0_compress(BLOCK *optimal, unsigned char *input_data, int input_size, int skip, int backwards_mode, int invert_mode, int *output_size, int *delta);