summaryrefslogtreecommitdiff
path: root/tools/rasm/zx7.h
diff options
context:
space:
mode:
authorJuan J. Martinez <jjm@usebox.net>2020-12-30 19:07:31 +0000
committerJuan J. Martinez <jjm@usebox.net>2020-12-30 19:23:41 +0000
commit2682bc5d1d864341aaeb42a449db73c3ecd16d70 (patch)
tree9116764364b4ee0ce7f6037305077807b57776de /tools/rasm/zx7.h
downloadubox-msx-lib-2682bc5d1d864341aaeb42a449db73c3ecd16d70.tar.gz
ubox-msx-lib-2682bc5d1d864341aaeb42a449db73c3ecd16d70.zip
Initial import1.0
Diffstat (limited to 'tools/rasm/zx7.h')
-rw-r--r--tools/rasm/zx7.h293
1 files changed, 293 insertions, 0 deletions
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 <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 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 <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.
+ */
+
+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 <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.
+ */
+
+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;
+}