FreeCalypso > hg > freecalypso-reveng

annotate fluid-mnf/lzencode.c @ 356:00060bb8b240

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fluid-mnf/misc.c: fixed stopwatch functions for Unix
author Mychaela Falconia <falcon@freecalypso.org>
date Fri, 13 Mar 2020 20:47:37 +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 * Searching in the window is done with help from an index and we maintain
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
42 * the window as a single linked list to further speed up the compression.
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
43 *
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
44 ******************************************************************************/
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
45
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
46 #include "fluid.h"
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
47 #include "lz.h"
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
48
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
49 #include <stdlib.h>
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
50 #include <stdio.h>
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
51 #include <string.h>
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
52 #include <ctype.h>
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 ******************************************************************************/
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 #define NIL -1 // Used for indexing purposes
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
60
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
61 // When we find a match put it into a struct like this.
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
62 typedef struct {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
63 int16 pos;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
64 int8 len;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
65 } match_def_t;
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 * Globals
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
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
72 static uint8 window[WINDOW_SIZE]; // Our sliding window buffer
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
73 static int16 window_pos; // And the current position in it
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
74 static uint8 lookahead; // number of bytes in the lookahead area
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 // Global input/output buffer pointers
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
77 static uint8 *buffer_out;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
78 static uint8 *buffer_in;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
79 static uint32 buffer_out_size;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
80 static uint32 buffer_in_size;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
81
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
82 static uint32 total_in_size = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
83 static uint32 total_out_size = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
84
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
85 static uint8 *p_tag_byte = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
86 static uint8 tag_pos = 0;
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 static int16 lookup[256]; // Table for looking up a link to any given character
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
89 static int16 lookup_end[256]; // The last link in the window.
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
90 static int16 next[WINDOW_SIZE]; // Contain links to next similar chars
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
91
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
92
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 * getchar/putchar
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
96 ******************************************************************************/
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 static int lze_getchar(void)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
99 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
100 total_in_size++;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
101
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
102 if (buffer_in_size-- > 0)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
103 return *buffer_in++;
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 buffer_in_size++;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
106
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
107 return EOF;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
108 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
109
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
110 static int lze_putchar(unsigned char data)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
111 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
112 total_out_size++;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
113
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
114 *buffer_out++ = data;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
115 buffer_out_size++;
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 return 0;
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
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
120 static int lze_putword(uint16 data)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
121 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
122 total_out_size += 2;
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 *buffer_out++ = (uint8)((data >> 8) & 0x00FF);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
125 *buffer_out++ = (uint8)(data & 0x00FF);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
126 buffer_out_size += 2;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
127
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
128 return 0;
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
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 * Code
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
133 ******************************************************************************/
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
134
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
135
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
136 // Searches for the best possible match to the string at 'source_pos' within
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
137 // the window. Lazy searches is made faster by specifying a match to beat
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
138 // 'match_len' so we don't vaste time by testing too small matches. Will
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
139 // stop at any match 'max_len' in size.
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
140 match_def_t find_best_match(int16 source_pos, int16 match_len, int16 max_len)
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 match_def_t current, best;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
143 int16 start_pos;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
144
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
145 best.len = match_len;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
146
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
147 if ((start_pos = lookup[window[source_pos]]) != NIL) // Get the first entry
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
148 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
149 current.pos = start_pos;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
150 do
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
151 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
152 if (window[WINDOW_MASK & (current.pos + best.len)] ==
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
153 window[WINDOW_MASK & (source_pos + best.len)]) // Possible match?
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
154 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
155 current.len = 1;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
156
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
157 while((window[WINDOW_MASK & (current.pos + current.len)] ==
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
158 window[WINDOW_MASK & (source_pos + current.len)]) &&
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
159 current.len < max_len)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
160 current.len++;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
161 if (current.len > best.len)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
162 best = current;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
163 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
164 if (best.len >= max_len)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
165 break; // no need to search for better matches when we have the best
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
166
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
167 current.pos = next[current.pos]; // jump to next matching char
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
168 } while(current.pos != NIL); // All. possibilities tested?
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
169 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
170 if (best.len <= match_len)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
171 best.len = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
172 return best;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
173 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
174
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
175 // Will remove 'count' links from 'begin' to make room for new data. Will be
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
176 // called when we need to overwrite some of the window by new lookahead
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
177 // chars.
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
178 void clear_index_positions(uint16 begin, uint16 count)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
179 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
180 uint16 i, pos;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
181
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
182 for (i = 0; i < count; i++)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
183 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
184 pos = WINDOW_MASK & (begin +i );
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
185
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
186 if (lookup[window[pos]] == pos) {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
187 if (lookup_end[window[pos]] == pos)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
188 lookup[window[pos]] = lookup_end[window[pos]] = NIL;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
189 else
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
190 lookup[window[pos]] = next[pos];
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
191 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
192 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
193 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
194
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
195
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
196 // Generate indexes for a string, so the match routines can find the
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
197 // characters in it very fast! We need to clean up obsolete indexes after
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
198 // this routine has been called
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
199 void index_string(int16 source_pos, int16 source_len)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
200 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
201 int16 i, j;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
202 uint8 c;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
203
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
204 for (i=0; i<source_len; i++)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
205 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
206 j = WINDOW_MASK & (source_pos + i);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
207 c = window[j];
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
208
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
209 next[j] = NIL;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
210 if (lookup[c] == NIL) // first time we encounter this char?
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
211 lookup[c] = j; // generate index for this new char
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
212 else
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
213 next[lookup_end[c]] = j;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
214 lookup_end[c] = j;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
215 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
216 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
217
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
218
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
219 void update_tag_byte(uint8 compressed)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
220 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
221 if(tag_pos == 0x00)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
222 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
223 p_tag_byte = buffer_out++; // Grap a byte in the output stream
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
224 buffer_out_size++;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
225
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
226 compressed ? (*p_tag_byte = 0x80) : (*p_tag_byte = 0x00);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
227 tag_pos = 0x40;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
228 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
229 else
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
230 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
231 if(compressed)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
232 *p_tag_byte |= tag_pos;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
233
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
234 tag_pos >>= 0x01;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
235 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
236 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
237
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
238
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
239
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
240 // Puts an uncompressed char into the file and update the window
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
241 // position. We cannot just putc(data) because the offset might be any
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
242 // number of bits off.
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
243 void save_raw(uint8 data)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
244 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
245 update_tag_byte(0);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
246 lze_putchar(data);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
247
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
248 index_string(window_pos, 1);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
249 window_pos = WINDOW_MASK & (window_pos + 1);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
250 lookahead--;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
251 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
252
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
253 // Puts a compressed match (length and position) into the file and update
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
254 // the window position.
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
255 void save_compressed(uint8 len, uint16 pos)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
256 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
257 uint16 tmp = 0x0000;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
258
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
259 update_tag_byte(1);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
260
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
261 tmp = ((uint8)(len - (THRESHOLD + 1))) << POS_BITS;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
262 tmp |= ((uint16)(pos & POS_MASK));
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
263
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
264 lze_putword(tmp);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
265
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
266 index_string(window_pos, len);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
267 window_pos = WINDOW_MASK & (window_pos + len);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
268 lookahead -= len;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
269 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
270
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
271 void compress_init(void)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
272 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
273 int i;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
274
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
275 // Initialize - whole window is unindexed at beginning
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
276 for (i = 0; i < 256; i++)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
277 lookup[i] = lookup_end[i] = NIL;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
278 for (i = 0; i < WINDOW_SIZE; i++)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
279 next[i] = window[i] = NIL;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
280
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
281 buffer_out_size = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
282 window_pos = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
283 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
284
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
285 int compress(char *outbuf, char *inbuf, int size)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
286 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
287 int ch, eof;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
288 match_def_t match, lazy_match;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
289
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
290 buffer_out = outbuf;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
291 buffer_out_size = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
292 buffer_in = inbuf;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
293 buffer_in_size = size;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
294 if (size <= 0)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
295 return 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
296
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
297 p_tag_byte = NULL;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
298 tag_pos = 0x00;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
299
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
300 do
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
301 {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
302 clear_index_positions(WINDOW_MASK & (window_pos + lookahead), MAX_MATCH);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
303
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
304 // (re-)fill the lookahead buffer from the bit-stream
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
305 while (lookahead < MAX_MATCH) {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
306 eof = ((ch = lze_getchar()) == EOF);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
307 window[WINDOW_MASK & (window_pos + lookahead++)] = (uint8) ch;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
308 if (eof) {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
309 window[WINDOW_MASK & (window_pos + --lookahead)] = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
310 break;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
311 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
312 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
313 // End of compression?
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
314 if (lookahead == 0)
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
315 break;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
316
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
317 // Search for a match so we can compress the data
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
318 match = find_best_match(window_pos, THRESHOLD, lookahead);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
319
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
320 if (match.len > THRESHOLD) {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
321
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
322 lazy_match.len = 0;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
323
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
324 // check if the lazy match is better
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
325 if (match.len < lookahead - 1) {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
326 lazy_match = find_best_match(WINDOW_MASK & (window_pos + 1),
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
327 match.len, lookahead-1);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
328 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
329 if (lazy_match.len > match.len) {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
330 // skip the current and use the lazy
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
331 save_raw(window[window_pos]);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
332 save_compressed(lazy_match.len, lazy_match.pos);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
333 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
334 else {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
335 save_compressed(match.len, match.pos);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
336 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
337 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
338 else {
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
339 // Compression failed - just stuff the raw data
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
340 save_raw(window[window_pos]);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
341 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
342
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
343 } while (!eof || lookahead > 0);
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
344
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
345 // put_bits(-1, 0); // No more data, so flush the buffer and exit
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
346
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
347 return buffer_out_size;
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
348 }
9cecc930d78f fluid-mnf: original source from TI,
Mychaela Falconia <falcon@freecalypso.org>
parents:
diff changeset
349