diff options
author | Juan J. Martinez <jjm@usebox.net> | 2022-09-06 07:37:20 +0100 |
---|---|---|
committer | Juan J. Martinez <jjm@usebox.net> | 2022-09-06 07:37:20 +0100 |
commit | 30bf0f51335e87812ffeb54e9437f0b6a1514d67 (patch) | |
tree | 9c85a2de53b4da69fcfaa84488cc6c12ebd3e5d0 /tools/rasm/ZX0-main | |
parent | d8990284057e6401d0374f439df51879595d804d (diff) | |
download | ubox-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/LICENSE | 29 | ||||
-rw-r--r-- | tools/rasm/ZX0-main/README.md | 369 | ||||
-rw-r--r-- | tools/rasm/ZX0-main/src/compress.c | 164 | ||||
-rw-r--r-- | tools/rasm/ZX0-main/src/memory.c | 75 | ||||
-rw-r--r-- | tools/rasm/ZX0-main/src/optimize.c | 137 | ||||
-rw-r--r-- | tools/rasm/ZX0-main/src/zx0.h | 46 |
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); |