From 2682bc5d1d864341aaeb42a449db73c3ecd16d70 Mon Sep 17 00:00:00 2001 From: "Juan J. Martinez" Date: Wed, 30 Dec 2020 19:07:31 +0000 Subject: Initial import --- tools/rasm/zx7.h | 293 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 293 insertions(+) create mode 100644 tools/rasm/zx7.h (limited to 'tools/rasm/zx7.h') diff --git a/tools/rasm/zx7.h b/tools/rasm/zx7.h new file mode 100644 index 0000000..f03659d --- /dev/null +++ b/tools/rasm/zx7.h @@ -0,0 +1,293 @@ +/* + +Warning! This is a modified version of original sources! + +To sum up: +- all include files and C sources were merged in a single file +- existing logs were removed (except error logs) +- main were removed and wrapper added + + + * (c) Copyright 2012 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 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 ZX7_MAX_OFFSET 2176 /* range 1..2176 */ +#define ZX7_MAX_LEN 65536 /* range 2..65536 */ + +typedef struct match_t { + size_t index; + struct match_t *next; +} Match; + +typedef struct optimal_t { + size_t bits; + int offset; + int len; +} Optimal; + +Optimal *optimize(unsigned char *input_data, size_t input_size); + +unsigned char *ZX7_compress(Optimal *optimal, unsigned char *input_data, size_t input_size, size_t *output_size); + +/* + * (c) Copyright 2012 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 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. + */ + +int elias_gamma_bits(int value) { + int bits; + + bits = 1; + while (value > 1) { + bits += 2; + value >>= 1; + } + return bits; +} + +int count_bits(int offset, int len) { + return 1 + (offset > 128 ? 12 : 8) + elias_gamma_bits(len-1); +} + +Optimal* optimize(unsigned char *input_data, size_t input_size) { + size_t *min; + size_t *max; + Match *matches; + Match *match_slots; + Optimal *optimal; + Match *match; + int match_index; + int offset; + size_t len; + size_t best_len; + size_t bits; + size_t i; + + /* allocate all data structures at once */ + min = (size_t *)calloc(ZX7_MAX_OFFSET+1, sizeof(size_t)); + max = (size_t *)calloc(ZX7_MAX_OFFSET+1, sizeof(size_t)); + matches = (Match *)calloc(256*256, sizeof(Match)); + match_slots = (Match *)calloc(input_size, sizeof(Match)); + optimal = (Optimal *)calloc(input_size, sizeof(Optimal)); + + if (!min || !max || !matches || !match_slots || !optimal) { + fprintf(stderr, "Error: Insufficient memory\n"); + exit(1); + } + + /* first byte is always literal */ + optimal[0].bits = 8; + + /* process remaining bytes */ + for (i = 1; i < input_size; i++) { + + optimal[i].bits = optimal[i-1].bits + 9; + match_index = input_data[i-1] << 8 | input_data[i]; + best_len = 1; + for (match = &matches[match_index]; match->next != NULL && best_len < ZX7_MAX_LEN; match = match->next) { + offset = i - match->next->index; + if (offset > ZX7_MAX_OFFSET) { + match->next = NULL; + break; + } + + for (len = 2; len <= ZX7_MAX_LEN; len++) { + if (len > best_len) { + best_len = len; + bits = optimal[i-len].bits + count_bits(offset, len); + if (optimal[i].bits > bits) { + optimal[i].bits = bits; + optimal[i].offset = offset; + optimal[i].len = len; + } + } else if (i+1 == max[offset]+len && max[offset] != 0) { + len = i-min[offset]; + if (len > best_len) { + len = best_len; + } + } + if (i < offset+len || input_data[i-len] != input_data[i-len-offset]) { + break; + } + } + min[offset] = i+1-len; + max[offset] = i; + } + match_slots[i].index = i; + match_slots[i].next = matches[match_index].next; + matches[match_index].next = &match_slots[i]; + } + + /* save time by releasing the largest block only, the O.S. will clean everything else later */ + free(match_slots); + + return optimal; +} + +/* + * (c) Copyright 2012 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 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. + */ + +unsigned char* output_data; +size_t output_index; +size_t bit_index; +int bit_mask; + +void write_byte(int value) { + output_data[output_index++] = value; +} + +void write_bit(int value) { + if (bit_mask == 0) { + bit_mask = 128; + bit_index = output_index; + write_byte(0); + } + if (value > 0) { + output_data[bit_index] |= bit_mask; + } + bit_mask >>= 1; +} + +void write_elias_gamma(int value) { + int i; + + for (i = 2; i <= value; i <<= 1) { + write_bit(0); + } + while ((i >>= 1) > 0) { + write_bit(value & i); + } +} + +unsigned char *ZX7_compress(Optimal *optimal, unsigned char *input_data, size_t input_size, size_t *output_size) { + size_t input_index; + size_t input_prev; + int offset1; + int mask; + int i; + + /* calculate and allocate output buffer */ + input_index = input_size-1; + *output_size = (optimal[input_index].bits+18+7)/8; + output_data = (unsigned char *)MemMalloc(*output_size); + + /* un-reverse optimal sequence */ + optimal[input_index].bits = 0; + while (input_index > 0) { + input_prev = input_index - (optimal[input_index].len > 0 ? optimal[input_index].len : 1); + optimal[input_prev].bits = input_index; + input_index = input_prev; + } + + output_index = 0; + bit_mask = 0; + + /* first byte is always literal */ + write_byte(input_data[0]); + + /* process remaining bytes */ + while ((input_index = optimal[input_index].bits) > 0) { + if (optimal[input_index].len == 0) { + + /* literal indicator */ + write_bit(0); + + /* literal value */ + write_byte(input_data[input_index]); + + } else { + + /* sequence indicator */ + write_bit(1); + + /* sequence length */ + write_elias_gamma(optimal[input_index].len-1); + + /* sequence offset */ + offset1 = optimal[input_index].offset-1; + if (offset1 < 128) { + write_byte(offset1); + } else { + offset1 -= 128; + write_byte((offset1 & 127) | 128); + for (mask = 1024; mask > 127; mask >>= 1) { + write_bit(offset1 & mask); + } + } + } + } + + /* sequence indicator */ + write_bit(1); + + /* end marker > MAX_LEN */ + for (i = 0; i < 16; i++) { + write_bit(0); + } + write_bit(1); + + return output_data; +} -- cgit v1.2.3