aboutsummaryrefslogtreecommitdiff
path: root/archival/libunarchive
diff options
context:
space:
mode:
authorDenys Vlasenko <vda.linux@googlemail.com>2010-11-03 02:27:49 +0100
committerDenys Vlasenko <vda.linux@googlemail.com>2010-11-03 02:27:49 +0100
commit5e9934028aa030312a1a2e2e32d5ceade8672beb (patch)
tree52f384d6c8e695fa2be1dbbc0a7e21e85033f3b2 /archival/libunarchive
parentdb5fe62b6d9977304b864f961dae71232091b26c (diff)
downloadbusybox-w32-5e9934028aa030312a1a2e2e32d5ceade8672beb.tar.gz
busybox-w32-5e9934028aa030312a1a2e2e32d5ceade8672beb.tar.bz2
busybox-w32-5e9934028aa030312a1a2e2e32d5ceade8672beb.zip
*: move lzo compressor code to archival/libunarchive/. No code changes
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'archival/libunarchive')
-rw-r--r--archival/libunarchive/Kbuild.src2
-rw-r--r--archival/libunarchive/liblzo.h93
-rw-r--r--archival/libunarchive/lzo1x_1.c35
-rw-r--r--archival/libunarchive/lzo1x_1o.c35
-rw-r--r--archival/libunarchive/lzo1x_9x.c921
-rw-r--r--archival/libunarchive/lzo1x_c.c296
-rw-r--r--archival/libunarchive/lzo1x_d.c420
7 files changed, 1802 insertions, 0 deletions
diff --git a/archival/libunarchive/Kbuild.src b/archival/libunarchive/Kbuild.src
index e92b4aad2..b0bc4e5aa 100644
--- a/archival/libunarchive/Kbuild.src
+++ b/archival/libunarchive/Kbuild.src
@@ -48,6 +48,8 @@ lib-$(CONFIG_RPM) += open_transformer.o decompress_unzip.o
48lib-$(CONFIG_TAR) += get_header_tar.o 48lib-$(CONFIG_TAR) += get_header_tar.o
49lib-$(CONFIG_UNCOMPRESS) += decompress_uncompress.o 49lib-$(CONFIG_UNCOMPRESS) += decompress_uncompress.o
50lib-$(CONFIG_UNZIP) += decompress_unzip.o 50lib-$(CONFIG_UNZIP) += decompress_unzip.o
51lib-$(CONFIG_LZOP) += lzo1x_1.o lzo1x_1o.o lzo1x_d.o
52lib-$(CONFIG_LZOP_COMPR_HIGH) += lzo1x_9x.o
51lib-$(CONFIG_FEATURE_SEAMLESS_Z) += open_transformer.o decompress_uncompress.o 53lib-$(CONFIG_FEATURE_SEAMLESS_Z) += open_transformer.o decompress_uncompress.o
52lib-$(CONFIG_FEATURE_SEAMLESS_GZ) += open_transformer.o decompress_unzip.o get_header_tar_gz.o 54lib-$(CONFIG_FEATURE_SEAMLESS_GZ) += open_transformer.o decompress_unzip.o get_header_tar_gz.o
53lib-$(CONFIG_FEATURE_SEAMLESS_BZ2) += open_transformer.o decompress_bunzip2.o get_header_tar_bz2.o 55lib-$(CONFIG_FEATURE_SEAMLESS_BZ2) += open_transformer.o decompress_bunzip2.o get_header_tar_bz2.o
diff --git a/archival/libunarchive/liblzo.h b/archival/libunarchive/liblzo.h
new file mode 100644
index 000000000..843997cb9
--- /dev/null
+++ b/archival/libunarchive/liblzo.h
@@ -0,0 +1,93 @@
1/*
2 This file is part of the LZO real-time data compression library.
3
4 Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
5 All Rights Reserved.
6
7 Markus F.X.J. Oberhumer <markus@oberhumer.com>
8 http://www.oberhumer.com/opensource/lzo/
9
10 The LZO library is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License as
12 published by the Free Software Foundation; either version 2 of
13 the License, or (at your option) any later version.
14
15 The LZO library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with the LZO library; see the file COPYING.
22 If not, write to the Free Software Foundation, Inc.,
23 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
24 */
25
26#include "liblzo_interface.h"
27
28/* lzo-2.03/src/config1x.h */
29#define M2_MIN_LEN 3
30#define M2_MAX_LEN 8
31#define M3_MAX_LEN 33
32#define M4_MAX_LEN 9
33#define M1_MAX_OFFSET 0x0400
34#define M2_MAX_OFFSET 0x0800
35#define M3_MAX_OFFSET 0x4000
36#define M4_MAX_OFFSET 0xbfff
37#define M1_MARKER 0
38#define M3_MARKER 32
39#define M4_MARKER 16
40
41#define MX_MAX_OFFSET (M1_MAX_OFFSET + M2_MAX_OFFSET)
42#define MIN_LOOKAHEAD (M2_MAX_LEN + 1)
43
44#define LZO_EOF_CODE
45
46/* lzo-2.03/src/lzo_dict.h */
47#define GINDEX(m_pos,m_off,dict,dindex,in) m_pos = dict[dindex]
48#define DX2(p,s1,s2) \
49 (((((unsigned)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0])
50//#define DA3(p,s1,s2,s3) ((DA2((p)+1,s2,s3) << (s1)) + (p)[0])
51//#define DS3(p,s1,s2,s3) ((DS2((p)+1,s2,s3) << (s1)) - (p)[0])
52#define DX3(p,s1,s2,s3) ((DX2((p)+1,s2,s3) << (s1)) ^ (p)[0])
53
54#define D_SIZE (1U << D_BITS)
55#define D_MASK ((1U << D_BITS) - 1)
56#define D_HIGH ((D_MASK >> 1) + 1)
57
58#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
59 ( \
60 m_pos = ip - (unsigned)(ip - m_pos), \
61 ((uintptr_t)m_pos < (uintptr_t)in \
62 || (m_off = (unsigned)(ip - m_pos)) <= 0 \
63 || m_off > max_offset) \
64 )
65
66#define DENTRY(p,in) (p)
67#define UPDATE_I(dict,drun,index,p,in) dict[index] = DENTRY(p,in)
68
69#define DMS(v,s) ((unsigned) (((v) & (D_MASK >> (s))) << (s)))
70#define DM(v) ((unsigned) ((v) & D_MASK))
71#define DMUL(a,b) ((unsigned) ((a) * (b)))
72
73/* lzo-2.03/src/lzo_ptr.h */
74#define pd(a,b) ((unsigned)((a)-(b)))
75
76# define TEST_IP (ip < ip_end)
77# define NEED_IP(x) \
78 if ((unsigned)(ip_end - ip) < (unsigned)(x)) goto input_overrun
79
80# undef TEST_OP /* don't need both of the tests here */
81# define TEST_OP 1
82# define NEED_OP(x) \
83 if ((unsigned)(op_end - op) < (unsigned)(x)) goto output_overrun
84
85#define HAVE_ANY_OP 1
86
87//#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
88# define TEST_LB(m_pos) if (m_pos < out || m_pos >= op) goto lookbehind_overrun
89//# define TEST_LBO(m_pos,o) if (m_pos < out || m_pos >= op - (o)) goto lookbehind_overrun
90//#else
91//# define TEST_LB(m_pos) ((void) 0)
92//# define TEST_LBO(m_pos,o) ((void) 0)
93//#endif
diff --git a/archival/libunarchive/lzo1x_1.c b/archival/libunarchive/lzo1x_1.c
new file mode 100644
index 000000000..a88839846
--- /dev/null
+++ b/archival/libunarchive/lzo1x_1.c
@@ -0,0 +1,35 @@
1/* LZO1X-1 compression
2
3 This file is part of the LZO real-time data compression library.
4
5 Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
6 All Rights Reserved.
7
8 Markus F.X.J. Oberhumer <markus@oberhumer.com>
9 http://www.oberhumer.com/opensource/lzo/
10
11 The LZO library is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License as
13 published by the Free Software Foundation; either version 2 of
14 the License, or (at your option) any later version.
15
16 The LZO library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with the LZO library; see the file COPYING.
23 If not, write to the Free Software Foundation, Inc.,
24 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
25 */
26#include "libbb.h"
27#include "liblzo.h"
28
29#define D_BITS 14
30#define D_INDEX1(d,p) d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5)
31#define D_INDEX2(d,p) d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
32
33#define DO_COMPRESS lzo1x_1_compress
34
35#include "lzo1x_c.c"
diff --git a/archival/libunarchive/lzo1x_1o.c b/archival/libunarchive/lzo1x_1o.c
new file mode 100644
index 000000000..3c61253e0
--- /dev/null
+++ b/archival/libunarchive/lzo1x_1o.c
@@ -0,0 +1,35 @@
1/* LZO1X-1(15) compression
2
3 This file is part of the LZO real-time data compression library.
4
5 Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
6 All Rights Reserved.
7
8 Markus F.X.J. Oberhumer <markus@oberhumer.com>
9 http://www.oberhumer.com/opensource/lzo/
10
11 The LZO library is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License as
13 published by the Free Software Foundation; either version 2 of
14 the License, or (at your option) any later version.
15
16 The LZO library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with the LZO library; see the file COPYING.
23 If not, write to the Free Software Foundation, Inc.,
24 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
25 */
26#include "libbb.h"
27#include "liblzo.h"
28
29#define D_BITS 15
30#define D_INDEX1(d,p) d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5)
31#define D_INDEX2(d,p) d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
32
33#define DO_COMPRESS lzo1x_1_15_compress
34
35#include "lzo1x_c.c"
diff --git a/archival/libunarchive/lzo1x_9x.c b/archival/libunarchive/lzo1x_9x.c
new file mode 100644
index 000000000..483205155
--- /dev/null
+++ b/archival/libunarchive/lzo1x_9x.c
@@ -0,0 +1,921 @@
1/* lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
2
3 This file is part of the LZO real-time data compression library.
4
5 Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
6 Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
7 Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
8 Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
9 Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
10 Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
11 Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
12 Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
13 Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
14 Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
15 Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
16 Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
17 Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
18 All Rights Reserved.
19
20 The LZO library is free software; you can redistribute it and/or
21 modify it under the terms of the GNU General Public License as
22 published by the Free Software Foundation; either version 2 of
23 the License, or (at your option) any later version.
24
25 The LZO library is distributed in the hope that it will be useful,
26 but WITHOUT ANY WARRANTY; without even the implied warranty of
27 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 GNU General Public License for more details.
29
30 You should have received a copy of the GNU General Public License
31 along with the LZO library; see the file COPYING.
32 If not, write to the Free Software Foundation, Inc.,
33 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
34
35 Markus F.X.J. Oberhumer
36 <markus@oberhumer.com>
37 http://www.oberhumer.com/opensource/lzo/
38*/
39#include "libbb.h"
40
41/* The following is probably only safe on Intel-compatible processors ... */
42#define LZO_UNALIGNED_OK_2
43#define LZO_UNALIGNED_OK_4
44
45#include "liblzo.h"
46
47#define LZO_MAX(a,b) ((a) >= (b) ? (a) : (b))
48#define LZO_MIN(a,b) ((a) <= (b) ? (a) : (b))
49#define LZO_MAX3(a,b,c) ((a) >= (b) ? LZO_MAX(a,c) : LZO_MAX(b,c))
50
51/***********************************************************************
52//
53************************************************************************/
54#define SWD_N M4_MAX_OFFSET /* size of ring buffer */
55#define SWD_F 2048 /* upper limit for match length */
56
57#define SWD_BEST_OFF (LZO_MAX3(M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN) + 1)
58
59typedef struct {
60 int init;
61
62 unsigned look; /* bytes in lookahead buffer */
63
64 unsigned m_len;
65 unsigned m_off;
66
67 const uint8_t *bp;
68 const uint8_t *ip;
69 const uint8_t *in;
70 const uint8_t *in_end;
71 uint8_t *out;
72
73 unsigned r1_lit;
74
75} lzo1x_999_t;
76
77#define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
78
79/* lzo_swd.c -- sliding window dictionary */
80
81/***********************************************************************
82//
83************************************************************************/
84#define SWD_UINT_MAX USHRT_MAX
85
86#ifndef SWD_HSIZE
87# define SWD_HSIZE 16384
88#endif
89#ifndef SWD_MAX_CHAIN
90# define SWD_MAX_CHAIN 2048
91#endif
92
93#define HEAD3(b, p) \
94 ( ((0x9f5f * ((((b[p]<<5)^b[p+1])<<5) ^ b[p+2])) >> 5) & (SWD_HSIZE-1) )
95
96#if defined(LZO_UNALIGNED_OK_2)
97# define HEAD2(b,p) (* (uint16_t *) &(b[p]))
98#else
99# define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8))
100#endif
101#define NIL2 SWD_UINT_MAX
102
103typedef struct lzo_swd {
104 /* public - "built-in" */
105
106 /* public - configuration */
107 unsigned max_chain;
108 int use_best_off;
109
110 /* public - output */
111 unsigned m_len;
112 unsigned m_off;
113 unsigned look;
114 int b_char;
115#if defined(SWD_BEST_OFF)
116 unsigned best_off[SWD_BEST_OFF];
117#endif
118
119 /* semi public */
120 lzo1x_999_t *c;
121 unsigned m_pos;
122#if defined(SWD_BEST_OFF)
123 unsigned best_pos[SWD_BEST_OFF];
124#endif
125
126 /* private */
127 unsigned ip; /* input pointer (lookahead) */
128 unsigned bp; /* buffer pointer */
129 unsigned rp; /* remove pointer */
130
131 unsigned node_count;
132 unsigned first_rp;
133
134 uint8_t b[SWD_N + SWD_F];
135 uint8_t b_wrap[SWD_F]; /* must follow b */
136 uint16_t head3[SWD_HSIZE];
137 uint16_t succ3[SWD_N + SWD_F];
138 uint16_t best3[SWD_N + SWD_F];
139 uint16_t llen3[SWD_HSIZE];
140#ifdef HEAD2
141 uint16_t head2[65536L];
142#endif
143} lzo_swd_t, *lzo_swd_p;
144
145#define SIZEOF_LZO_SWD_T (sizeof(lzo_swd_t))
146
147
148/* Access macro for head3.
149 * head3[key] may be uninitialized, but then its value will never be used.
150 */
151#define s_get_head3(s,key) s->head3[key]
152
153
154/***********************************************************************
155//
156************************************************************************/
157#define B_SIZE (SWD_N + SWD_F)
158
159static int swd_init(lzo_swd_p s)
160{
161 /* defaults */
162 s->node_count = SWD_N;
163
164 memset(s->llen3, 0, sizeof(s->llen3[0]) * (unsigned)SWD_HSIZE);
165#ifdef HEAD2
166 memset(s->head2, 0xff, sizeof(s->head2[0]) * 65536L);
167 assert(s->head2[0] == NIL2);
168#endif
169
170 s->ip = 0;
171 s->bp = s->ip;
172 s->first_rp = s->ip;
173
174 assert(s->ip + SWD_F <= B_SIZE);
175 s->look = (unsigned) (s->c->in_end - s->c->ip);
176 if (s->look > 0) {
177 if (s->look > SWD_F)
178 s->look = SWD_F;
179 memcpy(&s->b[s->ip], s->c->ip, s->look);
180 s->c->ip += s->look;
181 s->ip += s->look;
182 }
183 if (s->ip == B_SIZE)
184 s->ip = 0;
185
186 s->rp = s->first_rp;
187 if (s->rp >= s->node_count)
188 s->rp -= s->node_count;
189 else
190 s->rp += B_SIZE - s->node_count;
191
192 return LZO_E_OK;
193}
194
195#define swd_pos2off(s,pos) \
196 (s->bp > (pos) ? s->bp - (pos) : B_SIZE - ((pos) - s->bp))
197
198
199/***********************************************************************
200//
201************************************************************************/
202static void swd_getbyte(lzo_swd_p s)
203{
204 int c;
205
206 if ((c = getbyte(*(s->c))) < 0) {
207 if (s->look > 0)
208 --s->look;
209 } else {
210 s->b[s->ip] = c;
211 if (s->ip < SWD_F)
212 s->b_wrap[s->ip] = c;
213 }
214 if (++s->ip == B_SIZE)
215 s->ip = 0;
216 if (++s->bp == B_SIZE)
217 s->bp = 0;
218 if (++s->rp == B_SIZE)
219 s->rp = 0;
220}
221
222
223/***********************************************************************
224// remove node from lists
225************************************************************************/
226static void swd_remove_node(lzo_swd_p s, unsigned node)
227{
228 if (s->node_count == 0) {
229 unsigned key;
230
231 key = HEAD3(s->b,node);
232 assert(s->llen3[key] > 0);
233 --s->llen3[key];
234
235#ifdef HEAD2
236 key = HEAD2(s->b,node);
237 assert(s->head2[key] != NIL2);
238 if ((unsigned) s->head2[key] == node)
239 s->head2[key] = NIL2;
240#endif
241 } else
242 --s->node_count;
243}
244
245
246/***********************************************************************
247//
248************************************************************************/
249static void swd_accept(lzo_swd_p s, unsigned n)
250{
251 assert(n <= s->look);
252
253 while (n--) {
254 unsigned key;
255
256 swd_remove_node(s,s->rp);
257
258 /* add bp into HEAD3 */
259 key = HEAD3(s->b, s->bp);
260 s->succ3[s->bp] = s_get_head3(s, key);
261 s->head3[key] = s->bp;
262 s->best3[s->bp] = SWD_F + 1;
263 s->llen3[key]++;
264 assert(s->llen3[key] <= SWD_N);
265
266#ifdef HEAD2
267 /* add bp into HEAD2 */
268 key = HEAD2(s->b, s->bp);
269 s->head2[key] = s->bp;
270#endif
271
272 swd_getbyte(s);
273 }
274}
275
276
277/***********************************************************************
278//
279************************************************************************/
280static void swd_search(lzo_swd_p s, unsigned node, unsigned cnt)
281{
282 const uint8_t *p1;
283 const uint8_t *p2;
284 const uint8_t *px;
285 unsigned m_len = s->m_len;
286 const uint8_t *b = s->b;
287 const uint8_t *bp = s->b + s->bp;
288 const uint8_t *bx = s->b + s->bp + s->look;
289 unsigned char scan_end1;
290
291 assert(s->m_len > 0);
292
293 scan_end1 = bp[m_len - 1];
294 for ( ; cnt-- > 0; node = s->succ3[node]) {
295 p1 = bp;
296 p2 = b + node;
297 px = bx;
298
299 assert(m_len < s->look);
300
301 if (p2[m_len - 1] == scan_end1
302 && p2[m_len] == p1[m_len]
303 && p2[0] == p1[0]
304 && p2[1] == p1[1]
305 ) {
306 unsigned i;
307 assert(lzo_memcmp(bp, &b[node], 3) == 0);
308
309 p1 += 2; p2 += 2;
310 do {} while (++p1 < px && *p1 == *++p2);
311 i = p1-bp;
312
313 assert(lzo_memcmp(bp, &b[node], i) == 0);
314
315#if defined(SWD_BEST_OFF)
316 if (i < SWD_BEST_OFF) {
317 if (s->best_pos[i] == 0)
318 s->best_pos[i] = node + 1;
319 }
320#endif
321 if (i > m_len) {
322 s->m_len = m_len = i;
323 s->m_pos = node;
324 if (m_len == s->look)
325 return;
326 if (m_len >= SWD_F)
327 return;
328 if (m_len > (unsigned) s->best3[node])
329 return;
330 scan_end1 = bp[m_len - 1];
331 }
332 }
333 }
334}
335
336
337/***********************************************************************
338//
339************************************************************************/
340#ifdef HEAD2
341
342static int swd_search2(lzo_swd_p s)
343{
344 unsigned key;
345
346 assert(s->look >= 2);
347 assert(s->m_len > 0);
348
349 key = s->head2[HEAD2(s->b, s->bp)];
350 if (key == NIL2)
351 return 0;
352 assert(lzo_memcmp(&s->b[s->bp], &s->b[key], 2) == 0);
353#if defined(SWD_BEST_OFF)
354 if (s->best_pos[2] == 0)
355 s->best_pos[2] = key + 1;
356#endif
357
358 if (s->m_len < 2) {
359 s->m_len = 2;
360 s->m_pos = key;
361 }
362 return 1;
363}
364
365#endif
366
367
368/***********************************************************************
369//
370************************************************************************/
371static void swd_findbest(lzo_swd_p s)
372{
373 unsigned key;
374 unsigned cnt, node;
375 unsigned len;
376
377 assert(s->m_len > 0);
378
379 /* get current head, add bp into HEAD3 */
380 key = HEAD3(s->b,s->bp);
381 node = s->succ3[s->bp] = s_get_head3(s, key);
382 cnt = s->llen3[key]++;
383 assert(s->llen3[key] <= SWD_N + SWD_F);
384 if (cnt > s->max_chain)
385 cnt = s->max_chain;
386 s->head3[key] = s->bp;
387
388 s->b_char = s->b[s->bp];
389 len = s->m_len;
390 if (s->m_len >= s->look) {
391 if (s->look == 0)
392 s->b_char = -1;
393 s->m_off = 0;
394 s->best3[s->bp] = SWD_F + 1;
395 } else {
396#ifdef HEAD2
397 if (swd_search2(s))
398#endif
399 if (s->look >= 3)
400 swd_search(s, node, cnt);
401 if (s->m_len > len)
402 s->m_off = swd_pos2off(s,s->m_pos);
403 s->best3[s->bp] = s->m_len;
404
405#if defined(SWD_BEST_OFF)
406 if (s->use_best_off) {
407 int i;
408 for (i = 2; i < SWD_BEST_OFF; i++) {
409 if (s->best_pos[i] > 0)
410 s->best_off[i] = swd_pos2off(s, s->best_pos[i]-1);
411 else
412 s->best_off[i] = 0;
413 }
414 }
415#endif
416 }
417
418 swd_remove_node(s,s->rp);
419
420#ifdef HEAD2
421 /* add bp into HEAD2 */
422 key = HEAD2(s->b, s->bp);
423 s->head2[key] = s->bp;
424#endif
425}
426
427#undef HEAD3
428#undef HEAD2
429#undef s_get_head3
430
431
432/***********************************************************************
433//
434************************************************************************/
435static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
436{
437 int r;
438
439 assert(!c->init);
440 c->init = 1;
441
442 s->c = c;
443
444 r = swd_init(s);
445 if (r != 0)
446 return r;
447
448 s->use_best_off = use_best_off;
449 return r;
450}
451
452
453/***********************************************************************
454//
455************************************************************************/
456static int find_match(lzo1x_999_t *c, lzo_swd_p s,
457 unsigned this_len, unsigned skip)
458{
459 assert(c->init);
460
461 if (skip > 0) {
462 assert(this_len >= skip);
463 swd_accept(s, this_len - skip);
464 } else {
465 assert(this_len <= 1);
466 }
467
468 s->m_len = 1;
469 s->m_len = 1;
470#ifdef SWD_BEST_OFF
471 if (s->use_best_off)
472 memset(s->best_pos, 0, sizeof(s->best_pos));
473#endif
474 swd_findbest(s);
475 c->m_len = s->m_len;
476 c->m_off = s->m_off;
477
478 swd_getbyte(s);
479
480 if (s->b_char < 0) {
481 c->look = 0;
482 c->m_len = 0;
483 } else {
484 c->look = s->look + 1;
485 }
486 c->bp = c->ip - c->look;
487
488 return LZO_E_OK;
489}
490
491/* this is a public functions, but there is no prototype in a header file */
492static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
493 uint8_t *out, unsigned *out_len,
494 void *wrkmem,
495 unsigned good_length,
496 unsigned max_lazy,
497 unsigned max_chain,
498 uint32_t use_best_off);
499
500
501/***********************************************************************
502//
503************************************************************************/
504static uint8_t *code_match(lzo1x_999_t *c,
505 uint8_t *op, unsigned m_len, unsigned m_off)
506{
507 assert(op > c->out);
508 if (m_len == 2) {
509 assert(m_off <= M1_MAX_OFFSET);
510 assert(c->r1_lit > 0);
511 assert(c->r1_lit < 4);
512 m_off -= 1;
513 *op++ = M1_MARKER | ((m_off & 3) << 2);
514 *op++ = m_off >> 2;
515 } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
516 assert(m_len >= 3);
517 m_off -= 1;
518 *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
519 *op++ = m_off >> 3;
520 assert(op[-2] >= M2_MARKER);
521 } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
522 assert(m_len == 3);
523 assert(m_off > M2_MAX_OFFSET);
524 m_off -= 1 + M2_MAX_OFFSET;
525 *op++ = M1_MARKER | ((m_off & 3) << 2);
526 *op++ = m_off >> 2;
527 } else if (m_off <= M3_MAX_OFFSET) {
528 assert(m_len >= 3);
529 m_off -= 1;
530 if (m_len <= M3_MAX_LEN)
531 *op++ = M3_MARKER | (m_len - 2);
532 else {
533 m_len -= M3_MAX_LEN;
534 *op++ = M3_MARKER | 0;
535 while (m_len > 255) {
536 m_len -= 255;
537 *op++ = 0;
538 }
539 assert(m_len > 0);
540 *op++ = m_len;
541 }
542 *op++ = m_off << 2;
543 *op++ = m_off >> 6;
544 } else {
545 unsigned k;
546
547 assert(m_len >= 3);
548 assert(m_off > 0x4000);
549 assert(m_off <= 0xbfff);
550 m_off -= 0x4000;
551 k = (m_off & 0x4000) >> 11;
552 if (m_len <= M4_MAX_LEN)
553 *op++ = M4_MARKER | k | (m_len - 2);
554 else {
555 m_len -= M4_MAX_LEN;
556 *op++ = M4_MARKER | k | 0;
557 while (m_len > 255) {
558 m_len -= 255;
559 *op++ = 0;
560 }
561 assert(m_len > 0);
562 *op++ = m_len;
563 }
564 *op++ = m_off << 2;
565 *op++ = m_off >> 6;
566 }
567
568 return op;
569}
570
571
572static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
573 const uint8_t *ii, unsigned t)
574{
575 if (op == c->out && t <= 238) {
576 *op++ = 17 + t;
577 } else if (t <= 3) {
578 op[-2] |= t;
579 } else if (t <= 18) {
580 *op++ = t - 3;
581 } else {
582 unsigned tt = t - 18;
583
584 *op++ = 0;
585 while (tt > 255) {
586 tt -= 255;
587 *op++ = 0;
588 }
589 assert(tt > 0);
590 *op++ = tt;
591 }
592 do *op++ = *ii++; while (--t > 0);
593
594 return op;
595}
596
597
598static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
599 unsigned lit)
600{
601 if (lit > 0) {
602 assert(m_len >= 2);
603 op = STORE_RUN(c, op, ii, lit);
604 } else {
605 assert(m_len >= 3);
606 }
607 c->r1_lit = lit;
608
609 return op;
610}
611
612
613/***********************************************************************
614//
615************************************************************************/
616static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
617{
618 int n = 4;
619
620 if (m_len < 2)
621 return -1;
622 if (m_len == 2)
623 return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
624 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
625 return 2;
626 if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
627 return 2;
628 if (m_off <= M3_MAX_OFFSET) {
629 if (m_len <= M3_MAX_LEN)
630 return 3;
631 m_len -= M3_MAX_LEN;
632 } else if (m_off <= M4_MAX_OFFSET) {
633 if (m_len <= M4_MAX_LEN)
634 return 3;
635 m_len -= M4_MAX_LEN;
636 } else
637 return -1;
638 while (m_len > 255) {
639 m_len -= 255;
640 n++;
641 }
642 return n;
643}
644
645
646static int min_gain(unsigned ahead, unsigned lit1,
647 unsigned lit2, int l1, int l2, int l3)
648{
649 int lazy_match_min_gain = 0;
650
651 assert (ahead >= 1);
652 lazy_match_min_gain += ahead;
653
654 if (lit1 <= 3)
655 lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
656 else if (lit1 <= 18)
657 lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
658
659 lazy_match_min_gain += (l2 - l1) * 2;
660 if (l3 > 0)
661 lazy_match_min_gain -= (ahead - l3) * 2;
662
663 if (lazy_match_min_gain < 0)
664 lazy_match_min_gain = 0;
665
666 return lazy_match_min_gain;
667}
668
669
670/***********************************************************************
671//
672************************************************************************/
673#if defined(SWD_BEST_OFF)
674
675static void better_match(const lzo_swd_p swd,
676 unsigned *m_len, unsigned *m_off)
677{
678 if (*m_len <= M2_MIN_LEN)
679 return;
680
681 if (*m_off <= M2_MAX_OFFSET)
682 return;
683
684 /* M3/M4 -> M2 */
685 if (*m_off > M2_MAX_OFFSET
686 && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
687 && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
688 ) {
689 *m_len = *m_len - 1;
690 *m_off = swd->best_off[*m_len];
691 return;
692 }
693
694 /* M4 -> M2 */
695 if (*m_off > M3_MAX_OFFSET
696 && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
697 && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
698 ) {
699 *m_len = *m_len - 2;
700 *m_off = swd->best_off[*m_len];
701 return;
702 }
703 /* M4 -> M3 */
704 if (*m_off > M3_MAX_OFFSET
705 && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
706 && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
707 ) {
708 *m_len = *m_len - 1;
709 *m_off = swd->best_off[*m_len];
710 }
711}
712
713#endif
714
715
716/***********************************************************************
717//
718************************************************************************/
719static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
720 uint8_t *out, unsigned *out_len,
721 void *wrkmem,
722 unsigned good_length,
723 unsigned max_lazy,
724 unsigned max_chain,
725 uint32_t use_best_off)
726{
727 uint8_t *op;
728 const uint8_t *ii;
729 unsigned lit;
730 unsigned m_len, m_off;
731 lzo1x_999_t cc;
732 lzo1x_999_t *const c = &cc;
733 const lzo_swd_p swd = (lzo_swd_p) wrkmem;
734 int r;
735
736 c->init = 0;
737 c->ip = c->in = in;
738 c->in_end = in + in_len;
739 c->out = out;
740
741 op = out;
742 ii = c->ip; /* point to start of literal run */
743 lit = 0;
744 c->r1_lit = 0;
745
746 r = init_match(c, swd, use_best_off);
747 if (r != 0)
748 return r;
749 swd->max_chain = max_chain;
750
751 r = find_match(c, swd, 0, 0);
752 if (r != 0)
753 return r;
754
755 while (c->look > 0) {
756 unsigned ahead;
757 unsigned max_ahead;
758 int l1, l2, l3;
759
760 m_len = c->m_len;
761 m_off = c->m_off;
762
763 assert(c->bp == c->ip - c->look);
764 assert(c->bp >= in);
765 if (lit == 0)
766 ii = c->bp;
767 assert(ii + lit == c->bp);
768 assert(swd->b_char == *(c->bp));
769
770 if (m_len < 2
771 || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
772 /* Do not accept this match for compressed-data compatibility
773 * with LZO v1.01 and before
774 * [ might be a problem for decompress() and optimize() ]
775 */
776 || (m_len == 2 && op == out)
777 || (op == out && lit == 0)
778 ) {
779 /* a literal */
780 m_len = 0;
781 }
782 else if (m_len == M2_MIN_LEN) {
783 /* compression ratio improves if we code a literal in some cases */
784 if (m_off > MX_MAX_OFFSET && lit >= 4)
785 m_len = 0;
786 }
787
788 if (m_len == 0) {
789 /* a literal */
790 lit++;
791 swd->max_chain = max_chain;
792 r = find_match(c, swd, 1, 0);
793 assert(r == 0);
794 continue;
795 }
796
797 /* a match */
798#if defined(SWD_BEST_OFF)
799 if (swd->use_best_off)
800 better_match(swd, &m_len, &m_off);
801#endif
802
803 /* shall we try a lazy match ? */
804 ahead = 0;
805 if (m_len >= max_lazy) {
806 /* no */
807 l1 = 0;
808 max_ahead = 0;
809 } else {
810 /* yes, try a lazy match */
811 l1 = len_of_coded_match(m_len, m_off, lit);
812 assert(l1 > 0);
813 max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
814 }
815
816
817 while (ahead < max_ahead && c->look > m_len) {
818 int lazy_match_min_gain;
819
820 if (m_len >= good_length)
821 swd->max_chain = max_chain >> 2;
822 else
823 swd->max_chain = max_chain;
824 r = find_match(c, swd, 1, 0);
825 ahead++;
826
827 assert(r == 0);
828 assert(c->look > 0);
829 assert(ii + lit + ahead == c->bp);
830
831 if (c->m_len < m_len)
832 continue;
833 if (c->m_len == m_len && c->m_off >= m_off)
834 continue;
835#if defined(SWD_BEST_OFF)
836 if (swd->use_best_off)
837 better_match(swd, &c->m_len, &c->m_off);
838#endif
839 l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
840 if (l2 < 0)
841 continue;
842
843 /* compressed-data compatibility [see above] */
844 l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
845
846 lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
847 if (c->m_len >= m_len + lazy_match_min_gain) {
848 if (l3 > 0) {
849 /* code previous run */
850 op = code_run(c, op, ii, lit);
851 lit = 0;
852 /* code shortened match */
853 op = code_match(c, op, ahead, m_off);
854 } else {
855 lit += ahead;
856 assert(ii + lit == c->bp);
857 }
858 goto lazy_match_done;
859 }
860 }
861
862 assert(ii + lit + ahead == c->bp);
863
864 /* 1 - code run */
865 op = code_run(c, op, ii, lit);
866 lit = 0;
867
868 /* 2 - code match */
869 op = code_match(c, op, m_len, m_off);
870 swd->max_chain = max_chain;
871 r = find_match(c, swd, m_len, 1+ahead);
872 assert(r == 0);
873
874 lazy_match_done: ;
875 }
876
877 /* store final run */
878 if (lit > 0)
879 op = STORE_RUN(c, op, ii, lit);
880
881#if defined(LZO_EOF_CODE)
882 *op++ = M4_MARKER | 1;
883 *op++ = 0;
884 *op++ = 0;
885#endif
886
887 *out_len = op - out;
888
889 return LZO_E_OK;
890}
891
892
893/***********************************************************************
894//
895************************************************************************/
896int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
897 uint8_t *out, unsigned *out_len,
898 void *wrkmem,
899 int compression_level)
900{
901 static const struct {
902 uint16_t good_length;
903 uint16_t max_lazy;
904 uint16_t max_chain;
905 uint16_t use_best_off;
906 } c[3] = {
907 { 8, 32, 256, 0 },
908 { 32, 128, 2048, 1 },
909 { SWD_F, SWD_F, 4096, 1 } /* max. compression */
910 };
911
912 if (compression_level < 7 || compression_level > 9)
913 return LZO_E_ERROR;
914
915 compression_level -= 7;
916 return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
917 c[compression_level].good_length,
918 c[compression_level].max_lazy,
919 c[compression_level].max_chain,
920 c[compression_level].use_best_off);
921}
diff --git a/archival/libunarchive/lzo1x_c.c b/archival/libunarchive/lzo1x_c.c
new file mode 100644
index 000000000..cc86f74b1
--- /dev/null
+++ b/archival/libunarchive/lzo1x_c.c
@@ -0,0 +1,296 @@
1/* implementation of the LZO1[XY]-1 compression algorithm
2
3 This file is part of the LZO real-time data compression library.
4
5 Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
6 All Rights Reserved.
7
8 Markus F.X.J. Oberhumer <markus@oberhumer.com>
9 http://www.oberhumer.com/opensource/lzo/
10
11 The LZO library is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License as
13 published by the Free Software Foundation; either version 2 of
14 the License, or (at your option) any later version.
15
16 The LZO library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with the LZO library; see the file COPYING.
23 If not, write to the Free Software Foundation, Inc.,
24 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
25 */
26
27/***********************************************************************
28// compress a block of data.
29************************************************************************/
30static NOINLINE unsigned
31do_compress(const uint8_t* in, unsigned in_len,
32 uint8_t* out, unsigned* out_len,
33 void* wrkmem)
34{
35 register const uint8_t* ip;
36 uint8_t* op;
37 const uint8_t* const in_end = in + in_len;
38 const uint8_t* const ip_end = in + in_len - M2_MAX_LEN - 5;
39 const uint8_t* ii;
40 const void* *const dict = (const void**) wrkmem;
41
42 op = out;
43 ip = in;
44 ii = ip;
45
46 ip += 4;
47 for (;;) {
48 register const uint8_t* m_pos;
49 unsigned m_off;
50 unsigned m_len;
51 unsigned dindex;
52
53 D_INDEX1(dindex,ip);
54 GINDEX(m_pos,m_off,dict,dindex,in);
55 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
56 goto literal;
57#if 1
58 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
59 goto try_match;
60 D_INDEX2(dindex,ip);
61#endif
62 GINDEX(m_pos,m_off,dict,dindex,in);
63 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
64 goto literal;
65 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
66 goto try_match;
67 goto literal;
68
69 try_match:
70#if 1 && defined(LZO_UNALIGNED_OK_2)
71 if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
72#else
73 if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
74#endif
75 {
76 } else {
77 if (m_pos[2] == ip[2]) {
78#if 0
79 if (m_off <= M2_MAX_OFFSET)
80 goto match;
81 if (lit <= 3)
82 goto match;
83 if (lit == 3) { /* better compression, but slower */
84 assert(op - 2 > out); op[-2] |= (uint8_t)(3);
85 *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
86 goto code_match;
87 }
88 if (m_pos[3] == ip[3])
89#endif
90 goto match;
91 }
92 else {
93 /* still need a better way for finding M1 matches */
94#if 0
95 /* a M1 match */
96#if 0
97 if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3)
98#else
99 if (m_off <= M1_MAX_OFFSET && lit == 3)
100#endif
101 {
102 register unsigned t;
103
104 t = lit;
105 assert(op - 2 > out); op[-2] |= (uint8_t)(t);
106 do *op++ = *ii++; while (--t > 0);
107 assert(ii == ip);
108 m_off -= 1;
109 *op++ = (uint8_t)(M1_MARKER | ((m_off & 3) << 2));
110 *op++ = (uint8_t)(m_off >> 2);
111 ip += 2;
112 goto match_done;
113 }
114#endif
115 }
116 }
117
118 /* a literal */
119 literal:
120 UPDATE_I(dict, 0, dindex, ip, in);
121 ++ip;
122 if (ip >= ip_end)
123 break;
124 continue;
125
126 /* a match */
127match:
128 UPDATE_I(dict, 0, dindex, ip, in);
129 /* store current literal run */
130 if (pd(ip, ii) > 0) {
131 register unsigned t = pd(ip, ii);
132
133 if (t <= 3) {
134 assert(op - 2 > out);
135 op[-2] |= (uint8_t)(t);
136 }
137 else if (t <= 18)
138 *op++ = (uint8_t)(t - 3);
139 else {
140 register unsigned tt = t - 18;
141
142 *op++ = 0;
143 while (tt > 255) {
144 tt -= 255;
145 *op++ = 0;
146 }
147 assert(tt > 0);
148 *op++ = (uint8_t)(tt);
149 }
150 do *op++ = *ii++; while (--t > 0);
151 }
152
153 /* code the match */
154 assert(ii == ip);
155 ip += 3;
156 if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++
157 || m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++
158#ifdef LZO1Y
159 || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++
160 || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++
161#endif
162 ) {
163 --ip;
164 m_len = pd(ip, ii);
165 assert(m_len >= 3);
166 assert(m_len <= M2_MAX_LEN);
167
168 if (m_off <= M2_MAX_OFFSET) {
169 m_off -= 1;
170#if defined(LZO1X)
171 *op++ = (uint8_t)(((m_len - 1) << 5) | ((m_off & 7) << 2));
172 *op++ = (uint8_t)(m_off >> 3);
173#elif defined(LZO1Y)
174 *op++ = (uint8_t)(((m_len + 1) << 4) | ((m_off & 3) << 2));
175 *op++ = (uint8_t)(m_off >> 2);
176#endif
177 }
178 else if (m_off <= M3_MAX_OFFSET) {
179 m_off -= 1;
180 *op++ = (uint8_t)(M3_MARKER | (m_len - 2));
181 goto m3_m4_offset;
182 } else {
183#if defined(LZO1X)
184 m_off -= 0x4000;
185 assert(m_off > 0);
186 assert(m_off <= 0x7fff);
187 *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
188 goto m3_m4_offset;
189#elif defined(LZO1Y)
190 goto m4_match;
191#endif
192 }
193 }
194 else {
195 {
196 const uint8_t* end = in_end;
197 const uint8_t* m = m_pos + M2_MAX_LEN + 1;
198 while (ip < end && *m == *ip)
199 m++, ip++;
200 m_len = pd(ip, ii);
201 }
202 assert(m_len > M2_MAX_LEN);
203
204 if (m_off <= M3_MAX_OFFSET) {
205 m_off -= 1;
206 if (m_len <= 33)
207 *op++ = (uint8_t)(M3_MARKER | (m_len - 2));
208 else {
209 m_len -= 33;
210 *op++ = M3_MARKER | 0;
211 goto m3_m4_len;
212 }
213 } else {
214#if defined(LZO1Y)
215 m4_match:
216#endif
217 m_off -= 0x4000;
218 assert(m_off > 0);
219 assert(m_off <= 0x7fff);
220 if (m_len <= M4_MAX_LEN)
221 *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2));
222 else {
223 m_len -= M4_MAX_LEN;
224 *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11));
225 m3_m4_len:
226 while (m_len > 255) {
227 m_len -= 255;
228 *op++ = 0;
229 }
230 assert(m_len > 0);
231 *op++ = (uint8_t)(m_len);
232 }
233 }
234 m3_m4_offset:
235 *op++ = (uint8_t)((m_off & 63) << 2);
236 *op++ = (uint8_t)(m_off >> 6);
237 }
238#if 0
239 match_done:
240#endif
241 ii = ip;
242 if (ip >= ip_end)
243 break;
244 }
245
246 *out_len = pd(op, out);
247 return pd(in_end, ii);
248}
249
250/***********************************************************************
251// public entry point
252************************************************************************/
253int DO_COMPRESS(const uint8_t* in, unsigned in_len,
254 uint8_t* out, unsigned* out_len,
255 void* wrkmem)
256{
257 uint8_t* op = out;
258 unsigned t;
259
260 if (in_len <= M2_MAX_LEN + 5)
261 t = in_len;
262 else {
263 t = do_compress(in,in_len,op,out_len,wrkmem);
264 op += *out_len;
265 }
266
267 if (t > 0) {
268 const uint8_t* ii = in + in_len - t;
269
270 if (op == out && t <= 238)
271 *op++ = (uint8_t)(17 + t);
272 else if (t <= 3)
273 op[-2] |= (uint8_t)(t);
274 else if (t <= 18)
275 *op++ = (uint8_t)(t - 3);
276 else {
277 unsigned tt = t - 18;
278
279 *op++ = 0;
280 while (tt > 255) {
281 tt -= 255;
282 *op++ = 0;
283 }
284 assert(tt > 0);
285 *op++ = (uint8_t)(tt);
286 }
287 do *op++ = *ii++; while (--t > 0);
288 }
289
290 *op++ = M4_MARKER | 1;
291 *op++ = 0;
292 *op++ = 0;
293
294 *out_len = pd(op, out);
295 return 0; /*LZO_E_OK*/
296}
diff --git a/archival/libunarchive/lzo1x_d.c b/archival/libunarchive/lzo1x_d.c
new file mode 100644
index 000000000..348a85510
--- /dev/null
+++ b/archival/libunarchive/lzo1x_d.c
@@ -0,0 +1,420 @@
1/* implementation of the LZO1X decompression algorithm
2
3 This file is part of the LZO real-time data compression library.
4
5 Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
6 All Rights Reserved.
7
8 Markus F.X.J. Oberhumer <markus@oberhumer.com>
9 http://www.oberhumer.com/opensource/lzo/
10
11 The LZO library is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License as
13 published by the Free Software Foundation; either version 2 of
14 the License, or (at your option) any later version.
15
16 The LZO library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
20
21 You should have received a copy of the GNU General Public License
22 along with the LZO library; see the file COPYING.
23 If not, write to the Free Software Foundation, Inc.,
24 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
25 */
26#include "libbb.h"
27#include "liblzo.h"
28
29/***********************************************************************
30// decompress a block of data.
31************************************************************************/
32/* safe decompression with overrun testing */
33int lzo1x_decompress_safe(const uint8_t* in, unsigned in_len,
34 uint8_t* out, unsigned* out_len,
35 void* wrkmem UNUSED_PARAM)
36{
37 register uint8_t* op;
38 register const uint8_t* ip;
39 register unsigned t;
40#if defined(COPY_DICT)
41 unsigned m_off;
42 const uint8_t* dict_end;
43#else
44 register const uint8_t* m_pos = NULL; /* possibly not needed */
45#endif
46 const uint8_t* const ip_end = in + in_len;
47#if defined(HAVE_ANY_OP)
48 uint8_t* const op_end = out + *out_len;
49#endif
50#if defined(LZO1Z)
51 unsigned last_m_off = 0;
52#endif
53
54// LZO_UNUSED(wrkmem);
55
56#if defined(COPY_DICT)
57 if (dict) {
58 if (dict_len > M4_MAX_OFFSET) {
59 dict += dict_len - M4_MAX_OFFSET;
60 dict_len = M4_MAX_OFFSET;
61 }
62 dict_end = dict + dict_len;
63 } else {
64 dict_len = 0;
65 dict_end = NULL;
66 }
67#endif /* COPY_DICT */
68
69 *out_len = 0;
70
71 op = out;
72 ip = in;
73
74 if (*ip > 17) {
75 t = *ip++ - 17;
76 if (t < 4)
77 goto match_next;
78 assert(t > 0); NEED_OP(t); NEED_IP(t+1);
79 do *op++ = *ip++; while (--t > 0);
80 goto first_literal_run;
81 }
82
83 while (TEST_IP && TEST_OP) {
84 t = *ip++;
85 if (t >= 16)
86 goto match;
87 /* a literal run */
88 if (t == 0) {
89 NEED_IP(1);
90 while (*ip == 0) {
91 t += 255;
92 ip++;
93 NEED_IP(1);
94 }
95 t += 15 + *ip++;
96 }
97 /* copy literals */
98 assert(t > 0);
99 NEED_OP(t+3);
100 NEED_IP(t+4);
101#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
102# if !defined(LZO_UNALIGNED_OK_4)
103 if (PTR_ALIGNED2_4(op, ip))
104# endif
105 {
106 COPY4(op, ip);
107 op += 4;
108 ip += 4;
109 if (--t > 0) {
110 if (t >= 4) {
111 do {
112 COPY4(op, ip);
113 op += 4;
114 ip += 4;
115 t -= 4;
116 } while (t >= 4);
117 if (t > 0)
118 do *op++ = *ip++; while (--t > 0);
119 } else {
120 do *op++ = *ip++; while (--t > 0);
121 }
122 }
123 }
124# if !defined(LZO_UNALIGNED_OK_4)
125 else
126# endif
127#endif
128#if !defined(LZO_UNALIGNED_OK_4)
129 {
130 *op++ = *ip++;
131 *op++ = *ip++;
132 *op++ = *ip++;
133 do *op++ = *ip++; while (--t > 0);
134 }
135#endif
136
137 first_literal_run:
138 t = *ip++;
139 if (t >= 16)
140 goto match;
141#if defined(COPY_DICT)
142#if defined(LZO1Z)
143 m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
144 last_m_off = m_off;
145#else
146 m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
147#endif
148 NEED_OP(3);
149 t = 3; COPY_DICT(t,m_off)
150#else /* !COPY_DICT */
151#if defined(LZO1Z)
152 t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
153 m_pos = op - t;
154 last_m_off = t;
155#else
156 m_pos = op - (1 + M2_MAX_OFFSET);
157 m_pos -= t >> 2;
158 m_pos -= *ip++ << 2;
159#endif
160 TEST_LB(m_pos); NEED_OP(3);
161 *op++ = *m_pos++;
162 *op++ = *m_pos++;
163 *op++ = *m_pos;
164#endif /* COPY_DICT */
165 goto match_done;
166
167 /* handle matches */
168 do {
169 match:
170 if (t >= 64) { /* a M2 match */
171#if defined(COPY_DICT)
172#if defined(LZO1X)
173 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
174 t = (t >> 5) - 1;
175#elif defined(LZO1Y)
176 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
177 t = (t >> 4) - 3;
178#elif defined(LZO1Z)
179 m_off = t & 0x1f;
180 if (m_off >= 0x1c)
181 m_off = last_m_off;
182 else {
183 m_off = 1 + (m_off << 6) + (*ip++ >> 2);
184 last_m_off = m_off;
185 }
186 t = (t >> 5) - 1;
187#endif
188#else /* !COPY_DICT */
189#if defined(LZO1X)
190 m_pos = op - 1;
191 m_pos -= (t >> 2) & 7;
192 m_pos -= *ip++ << 3;
193 t = (t >> 5) - 1;
194#elif defined(LZO1Y)
195 m_pos = op - 1;
196 m_pos -= (t >> 2) & 3;
197 m_pos -= *ip++ << 2;
198 t = (t >> 4) - 3;
199#elif defined(LZO1Z)
200 {
201 unsigned off = t & 0x1f;
202 m_pos = op;
203 if (off >= 0x1c) {
204 assert(last_m_off > 0);
205 m_pos -= last_m_off;
206 } else {
207 off = 1 + (off << 6) + (*ip++ >> 2);
208 m_pos -= off;
209 last_m_off = off;
210 }
211 }
212 t = (t >> 5) - 1;
213#endif
214 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
215 goto copy_match;
216#endif /* COPY_DICT */
217 }
218 else if (t >= 32) { /* a M3 match */
219 t &= 31;
220 if (t == 0) {
221 NEED_IP(1);
222 while (*ip == 0) {
223 t += 255;
224 ip++;
225 NEED_IP(1);
226 }
227 t += 31 + *ip++;
228 }
229#if defined(COPY_DICT)
230#if defined(LZO1Z)
231 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
232 last_m_off = m_off;
233#else
234 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
235#endif
236#else /* !COPY_DICT */
237#if defined(LZO1Z)
238 {
239 unsigned off = 1 + (ip[0] << 6) + (ip[1] >> 2);
240 m_pos = op - off;
241 last_m_off = off;
242 }
243#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
244 m_pos = op - 1;
245 m_pos -= (* (const lzo_ushortp) ip) >> 2;
246#else
247 m_pos = op - 1;
248 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
249#endif
250#endif /* COPY_DICT */
251 ip += 2;
252 }
253 else if (t >= 16) { /* a M4 match */
254#if defined(COPY_DICT)
255 m_off = (t & 8) << 11;
256#else /* !COPY_DICT */
257 m_pos = op;
258 m_pos -= (t & 8) << 11;
259#endif /* COPY_DICT */
260 t &= 7;
261 if (t == 0) {
262 NEED_IP(1);
263 while (*ip == 0) {
264 t += 255;
265 ip++;
266 NEED_IP(1);
267 }
268 t += 7 + *ip++;
269 }
270#if defined(COPY_DICT)
271#if defined(LZO1Z)
272 m_off += (ip[0] << 6) + (ip[1] >> 2);
273#else
274 m_off += (ip[0] >> 2) + (ip[1] << 6);
275#endif
276 ip += 2;
277 if (m_off == 0)
278 goto eof_found;
279 m_off += 0x4000;
280#if defined(LZO1Z)
281 last_m_off = m_off;
282#endif
283#else /* !COPY_DICT */
284#if defined(LZO1Z)
285 m_pos -= (ip[0] << 6) + (ip[1] >> 2);
286#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
287 m_pos -= (* (const lzo_ushortp) ip) >> 2;
288#else
289 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
290#endif
291 ip += 2;
292 if (m_pos == op)
293 goto eof_found;
294 m_pos -= 0x4000;
295#if defined(LZO1Z)
296 last_m_off = pd((const uint8_t*)op, m_pos);
297#endif
298#endif /* COPY_DICT */
299 }
300 else { /* a M1 match */
301#if defined(COPY_DICT)
302#if defined(LZO1Z)
303 m_off = 1 + (t << 6) + (*ip++ >> 2);
304 last_m_off = m_off;
305#else
306 m_off = 1 + (t >> 2) + (*ip++ << 2);
307#endif
308 NEED_OP(2);
309 t = 2; COPY_DICT(t,m_off)
310#else /* !COPY_DICT */
311#if defined(LZO1Z)
312 t = 1 + (t << 6) + (*ip++ >> 2);
313 m_pos = op - t;
314 last_m_off = t;
315#else
316 m_pos = op - 1;
317 m_pos -= t >> 2;
318 m_pos -= *ip++ << 2;
319#endif
320 TEST_LB(m_pos); NEED_OP(2);
321 *op++ = *m_pos++;
322 *op++ = *m_pos;
323#endif /* COPY_DICT */
324 goto match_done;
325 }
326
327 /* copy match */
328#if defined(COPY_DICT)
329
330 NEED_OP(t+3-1);
331 t += 3-1; COPY_DICT(t,m_off)
332
333#else /* !COPY_DICT */
334
335 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
336#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
337# if !defined(LZO_UNALIGNED_OK_4)
338 if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) {
339 assert((op - m_pos) >= 4); /* both pointers are aligned */
340# else
341 if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
342# endif
343 COPY4(op,m_pos);
344 op += 4; m_pos += 4; t -= 4 - (3 - 1);
345 do {
346 COPY4(op,m_pos);
347 op += 4; m_pos += 4; t -= 4;
348 } while (t >= 4);
349 if (t > 0)
350 do *op++ = *m_pos++; while (--t > 0);
351 }
352 else
353#endif
354 {
355 copy_match:
356 *op++ = *m_pos++; *op++ = *m_pos++;
357 do *op++ = *m_pos++; while (--t > 0);
358 }
359
360#endif /* COPY_DICT */
361
362 match_done:
363#if defined(LZO1Z)
364 t = ip[-1] & 3;
365#else
366 t = ip[-2] & 3;
367#endif
368 if (t == 0)
369 break;
370
371 /* copy literals */
372 match_next:
373 assert(t > 0);
374 assert(t < 4);
375 NEED_OP(t);
376 NEED_IP(t+1);
377#if 0
378 do *op++ = *ip++; while (--t > 0);
379#else
380 *op++ = *ip++;
381 if (t > 1) {
382 *op++ = *ip++;
383 if (t > 2)
384 *op++ = *ip++;
385 }
386#endif
387 t = *ip++;
388 } while (TEST_IP && TEST_OP);
389 }
390
391//#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
392 /* no EOF code was found */
393 *out_len = pd(op, out);
394 return LZO_E_EOF_NOT_FOUND;
395//#endif
396
397 eof_found:
398 assert(t == 1);
399 *out_len = pd(op, out);
400 return (ip == ip_end ? LZO_E_OK :
401 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
402
403//#if defined(HAVE_NEED_IP)
404 input_overrun:
405 *out_len = pd(op, out);
406 return LZO_E_INPUT_OVERRUN;
407//#endif
408
409//#if defined(HAVE_NEED_OP)
410 output_overrun:
411 *out_len = pd(op, out);
412 return LZO_E_OUTPUT_OVERRUN;
413//#endif
414
415//#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
416 lookbehind_overrun:
417 *out_len = pd(op, out);
418 return LZO_E_LOOKBEHIND_OVERRUN;
419//#endif
420}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-15 08:32:45 +0000