FreeCalypso > hg > freecalypso-reveng

annotate fluid-mnf/lzdecode.c @ 320:20feaf83c661

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
frbl/reconst/convert.c: better match to original object still not perfect though
author Mychaela Falconia <falcon@freecalypso.org>
date Thu, 05 Mar 2020 05:01:14 +0000
parents 9cecc930d78f
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
311
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
1 /*******************************************************************************
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
2 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
3 * Simple LZ77 compressor (c) Texas Instruments, Jesper Pedersem TI-DK
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
4 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
5 * File format:
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
6 * ---------------------------------------------------
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
7 * | Tag | Data | Tag | Data | Tag | Data etc...
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
8 * ---------------------------------------------------
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
9 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
10 * Where TAG is 1 bit indicating how to interpret the following data
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
11 * (0 = uncompressed, 1 = compressed)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
12 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
13 * Depending on TAG the Data is:
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
14 * 0 : One uncompressed char of raw data
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
15 * 1 : A length of and a pointer to a match in the previous data
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
16 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
17 * ----------------------------------------
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
18 * Length + pointer = | Length (3 bits) | Position (12 bits) |
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
19 * ----------------------------------------
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
20 * MSB LSB MSB LSB
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
21 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
22 * Compression threshold is 1 i.e. add 1 to Length to get the actual Length.
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
23 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
24 * It has been found that 5+14 bits is the most optimum for our kind of
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
25 * data, but we use only 3+12 bits for improoved speed. Compression is
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
26 * almost as good because we can set the threshold at 1 instead of 2 (2 char
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
27 * matches can be compressed to 12+3 bits)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
28 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
29 * With a 12 bit position we can use 4K for the sliding window. Position
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
30 * indicates where the match exists as an absolute address into the
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
31 * window. This way we have a very simple "pseudo sliding window" which
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
32 * automatically enables RLE (Run Length Encoding).
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
33 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
34 * The code performs a "lazy" string search i.e. a match will be dropped if
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
35 * it prevents an even greater match for the very next string. This yeild
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
36 * slightly better compression (approx. 1%) at minor cost of compression
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
37 * speed - decompression time is the same! A second order lazy match could
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
38 * be implemented, but it gives an insignificant improovement of about 0.1%
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
39 * when compressing executeables
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
40 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
41 ******************************************************************************/
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
42
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
43 #if (TARGET == 0)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
44 #include "fluid.h"
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
45 #include <stdlib.h>
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
46 #endif
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
47
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
48 #include "lz.h"
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
49
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
50
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
51 /******************************************************************************
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
52 * Globals
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
53 ******************************************************************************/
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
54
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
55
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
56 /******************************************************************************
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
57 * getchar/putchar
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
58 ******************************************************************************/
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
59
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
60 #define EOF -1
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
61
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
62 #define LZ_PUTCHAR(data) \
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
63 *plz->buffer_out++ = data; \
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
64 plz->buffer_out_size++;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
65
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
66
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
67
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
68 /******************************************************************************
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
69 * Code
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
70 ******************************************************************************/
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
71 uint8 get_byte(struct lz_s *plz)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
72 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
73 plz->buffer_in_size--;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
74 return(*plz->buffer_in++);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
75 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
76
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
77 uint16 get_word(struct lz_s *plz)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
78 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
79 uint16 tmp;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
80
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
81 tmp = (*plz->buffer_in++) << 8;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
82 tmp |= (*plz->buffer_in++);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
83 plz->buffer_in_size -= 2;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
84 return(tmp);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
85 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
86
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
87
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
88 void decompress_init(struct lz_s *plz)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
89 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
90 plz->window_pos = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
91 plz->bitbuf = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
92 plz->bitbuf_size = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
93 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
94
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
95 int decompress(struct lz_s *plz,
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
96 unsigned char *outbuf, unsigned char *inbuf, int size)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
97 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
98 int16 match_pos;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
99 int16 match_len, i;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
100 int8 ch;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
101 uint8 tag_byte;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
102 uint8 tag_pos;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
103 uint16 tmp;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
104
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
105
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
106 plz->buffer_out = outbuf;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
107 plz->buffer_out_size = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
108 plz->buffer_in = inbuf;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
109 plz->buffer_in_size = size;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
110
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
111 while(plz->buffer_in_size > 0)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
112 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
113 tag_byte = get_byte(plz);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
114
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
115 for(tag_pos = 0x80; (plz->buffer_in_size > 0) && (tag_pos > 0x00); tag_pos >>= 0x01)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
116 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
117 if(tag_byte & tag_pos) // Compressed?
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
118 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
119 tmp = get_word(plz);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
120 match_len = (tmp >> POS_BITS) + THRESHOLD + 1;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
121 match_pos = (tmp & POS_MASK);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
122 for (i = 0; i < match_len; i++)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
123 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
124 plz->window[plz->window_pos] = plz->window[WINDOW_MASK & (match_pos + i)];
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
125 LZ_PUTCHAR(plz->window[plz->window_pos]);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
126 plz->window_pos++;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
127 plz->window_pos &= WINDOW_MASK;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
128 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
129 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
130 else
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
131 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
132 ch = get_byte(plz);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
133 plz->window[plz->window_pos] = ch;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
134 LZ_PUTCHAR(ch);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
135 plz->window_pos++;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
136 plz->window_pos &= WINDOW_MASK;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
137 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
138 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
139 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
140 return plz->buffer_out_size;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
141 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
142