1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
#include <string.h>
// LZW Compressor
struct SYM
{
unsigned char *data;
int size;
int next;
};
struct SYMBOLS
{
SYM syms[512];
int jumptable[256];
int currentsym;
};
static SYMBOLS symbols;
// symbol info
inline int sym_size(int i) { return symbols.syms[i].size; }
inline unsigned char *sym_data(int i) { return symbols.syms[i].data; }
static void sym_index(int sym)
{
int table = symbols.syms[sym].data[0];
symbols.syms[sym].next = symbols.jumptable[table];
symbols.jumptable[table] = sym;
}
static void sym_unindex(int sym)
{
int table = symbols.syms[sym].data[0];
int prev = -1;
int current = symbols.jumptable[table];
while(current != -1)
{
if(current == sym)
{
if(prev != -1)
symbols.syms[prev].next = symbols.syms[current].next;
else
symbols.jumptable[table] = symbols.syms[current].next;
break;
}
prev = current;
current = symbols.syms[current].next;
}
}
static int sym_add(unsigned char *sym, long len)
{
int i = 256+symbols.currentsym;
symbols.syms[i].data = sym;
symbols.syms[i].size = len;
symbols.currentsym = (symbols.currentsym+1)%255;
return i;
}
static int sym_add_and_index(unsigned char *sym, long len)
{
if(symbols.syms[256+symbols.currentsym].size)
sym_unindex(256+symbols.currentsym);
int s = sym_add(sym, len);
sym_index( s);
return s;
}
static void sym_init()
{
static unsigned char table[256];
for(int i = 0; i < 256; i++)
{
table[i] = i;
symbols.syms[i].data = &table[i];
symbols.syms[i].size = 1;
symbols.jumptable[i] = -1;
}
for(int i = 0; i < 512; i++)
symbols.syms[i].next = -1;
/*
// insert some symbols to start with
static unsigned char zeros[8] = {0,0,0,0,0,0,0,0};
//static unsigned char one1[4] = {0,0,0,1};
//static unsigned char one2[4] = {1,0,0,0};
sym_add_and_index(zeros, 2);
sym_add_and_index(zeros, 3);
sym_add_and_index(zeros, 4);
sym_add_and_index(zeros, 5);
sym_add_and_index(zeros, 6);
sym_add_and_index(zeros, 7);
sym_add_and_index(zeros, 8);
//sym_add_and_index(one1, 4);
//sym_add_and_index(one2, 4);*/
symbols.currentsym = 0;
}
static int sym_find(unsigned char *data, int size, int avoid)
{
int best = data[0];
int bestlen = 1;
int current = symbols.jumptable[data[0]];
while(current != -1)
{
if(current != avoid && symbols.syms[current].size <= size && memcmp(data, symbols.syms[current].data, symbols.syms[current].size) == 0)
{
if(bestlen < symbols.syms[current].size)
{
bestlen = symbols.syms[current].size;
best = current;
}
}
current = symbols.syms[current].next;
}
return best;
}
//
// compress
//
long lzw_compress(const void *src_, int size, void *dst_)
{
unsigned char *src = (unsigned char *)src_;
unsigned char *end = (unsigned char *)src_+size;
unsigned char *dst = (unsigned char *)dst_;
long left = (end-src);
int lastsym = -1;
// init symboltable
sym_init();
bool done = false;
while(!done)
{
unsigned char *flagptr = dst;
unsigned char flagbits = 0;
int b = 0;
dst++; // skip a byte where the flags are
for(; b < 8; b++)
{
if(left <= 0) // check for EOF
{
// write EOF symbol
flagbits |= 1<<b;
*dst++ = 255;
done = true;
break;
}
int sym = sym_find(src, left, lastsym);
int symsize = sym_size( sym);
if(sym&0x100)
flagbits |= 1<<b; // add bit that says that its a symbol
*dst++ = sym&0xff; // set symbol
if(left > symsize+1) // create new symbol
lastsym = sym_add_and_index(src, symsize+1);
src += symsize; // advance src
left -= symsize;
}
// write the flags
*flagptr = flagbits;
}
return (long)(dst-(unsigned char*)dst_);
}
//
// decompress
//
long lzw_decompress(const void *src_, void *dst_)
{
unsigned char *src = (unsigned char *)src_;
unsigned char *dst = (unsigned char *)dst_;
unsigned char *prevdst = 0;
int prevsize = -1;
int item;
sym_init();
while(1)
{
unsigned char flagbits = 0;
flagbits = *src++; // read flags
int b = 0;
for(; b < 8; b++)
{
item = *src++;
if(flagbits&(1<<b))
item |= 256;
if(item == 0x1ff) // EOF symbol
return (dst-(unsigned char *)dst_);
if(prevdst) // this one could be removed
sym_add(prevdst, prevsize+1);
memcpy(dst, sym_data(item), sym_size(item));
prevdst = dst;
prevsize = sym_size(item);
dst += sym_size(item);
}
}
return 0;
}
|