From 052ad9a56883a56742cec1afc6c1c8dfff222495 Mon Sep 17 00:00:00 2001 From: Denis Vlasenko Date: Wed, 29 Apr 2009 12:01:51 +0000 Subject: lzop: new applet. Busyboxed by Alain Knaff. +7700 bytes. --- archival/Config.in | 15 + archival/Kbuild | 2 + archival/liblzo.h | 93 ++++ archival/liblzo_interface.h | 71 +++ archival/lzo1x_1.c | 35 ++ archival/lzo1x_1o.c | 35 ++ archival/lzo1x_9x.c | 920 ++++++++++++++++++++++++++++++++++++ archival/lzo1x_c.c | 296 ++++++++++++ archival/lzo1x_d.c | 420 +++++++++++++++++ archival/lzop.c | 1075 +++++++++++++++++++++++++++++++++++++++++++ include/applets.h | 3 + include/usage.h | 25 + 12 files changed, 2990 insertions(+) create mode 100644 archival/liblzo.h create mode 100644 archival/liblzo_interface.h create mode 100644 archival/lzo1x_1.c create mode 100644 archival/lzo1x_1o.c create mode 100644 archival/lzo1x_9x.c create mode 100644 archival/lzo1x_c.c create mode 100644 archival/lzo1x_d.c create mode 100644 archival/lzop.c diff --git a/archival/Config.in b/archival/Config.in index e0d43c0ee..a983e4433 100644 --- a/archival/Config.in +++ b/archival/Config.in @@ -165,6 +165,21 @@ config GZIP gzip is used to compress files. It's probably the most widely used UNIX compression program. +config LZOP + bool "lzop" + default n + help + Lzop compression/decompresion. + +config LZOP_COMPR_HIGH + bool "lzop complession levels 7,8,9 (not very useful)" + default n + depends on LZOP + help + High levels (7,8,9) of lzop compression. These levels + are actually slower than gzip at equivalent compression ratios + and take up 3.2K of code. + config RPM2CPIO bool "rpm2cpio" default n diff --git a/archival/Kbuild b/archival/Kbuild index 72dbdda0e..de0ca4315 100644 --- a/archival/Kbuild +++ b/archival/Kbuild @@ -16,6 +16,8 @@ lib-$(CONFIG_DPKG) += dpkg.o lib-$(CONFIG_DPKG_DEB) += dpkg_deb.o lib-$(CONFIG_GUNZIP) += bbunzip.o lib-$(CONFIG_GZIP) += gzip.o bbunzip.o +lib-$(CONFIG_LZOP) += lzop.o lzo1x_1.o lzo1x_1o.o lzo1x_d.o +lib-$(CONFIG_LZOP_COMPR_HIGH) += lzo1x_9x.o lib-$(CONFIG_RPM2CPIO) += rpm2cpio.o lib-$(CONFIG_RPM) += rpm.o lib-$(CONFIG_TAR) += tar.o diff --git a/archival/liblzo.h b/archival/liblzo.h new file mode 100644 index 000000000..843997cb9 --- /dev/null +++ b/archival/liblzo.h @@ -0,0 +1,93 @@ +/* + This file is part of the LZO real-time data compression library. + + Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + Markus F.X.J. Oberhumer + http://www.oberhumer.com/opensource/lzo/ + + The LZO library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The LZO library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the LZO library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include "liblzo_interface.h" + +/* lzo-2.03/src/config1x.h */ +#define M2_MIN_LEN 3 +#define M2_MAX_LEN 8 +#define M3_MAX_LEN 33 +#define M4_MAX_LEN 9 +#define M1_MAX_OFFSET 0x0400 +#define M2_MAX_OFFSET 0x0800 +#define M3_MAX_OFFSET 0x4000 +#define M4_MAX_OFFSET 0xbfff +#define M1_MARKER 0 +#define M3_MARKER 32 +#define M4_MARKER 16 + +#define MX_MAX_OFFSET (M1_MAX_OFFSET + M2_MAX_OFFSET) +#define MIN_LOOKAHEAD (M2_MAX_LEN + 1) + +#define LZO_EOF_CODE + +/* lzo-2.03/src/lzo_dict.h */ +#define GINDEX(m_pos,m_off,dict,dindex,in) m_pos = dict[dindex] +#define DX2(p,s1,s2) \ + (((((unsigned)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0]) +//#define DA3(p,s1,s2,s3) ((DA2((p)+1,s2,s3) << (s1)) + (p)[0]) +//#define DS3(p,s1,s2,s3) ((DS2((p)+1,s2,s3) << (s1)) - (p)[0]) +#define DX3(p,s1,s2,s3) ((DX2((p)+1,s2,s3) << (s1)) ^ (p)[0]) + +#define D_SIZE (1U << D_BITS) +#define D_MASK ((1U << D_BITS) - 1) +#define D_HIGH ((D_MASK >> 1) + 1) + +#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \ + ( \ + m_pos = ip - (unsigned)(ip - m_pos), \ + ((uintptr_t)m_pos < (uintptr_t)in \ + || (m_off = (unsigned)(ip - m_pos)) <= 0 \ + || m_off > max_offset) \ + ) + +#define DENTRY(p,in) (p) +#define UPDATE_I(dict,drun,index,p,in) dict[index] = DENTRY(p,in) + +#define DMS(v,s) ((unsigned) (((v) & (D_MASK >> (s))) << (s))) +#define DM(v) ((unsigned) ((v) & D_MASK)) +#define DMUL(a,b) ((unsigned) ((a) * (b))) + +/* lzo-2.03/src/lzo_ptr.h */ +#define pd(a,b) ((unsigned)((a)-(b))) + +# define TEST_IP (ip < ip_end) +# define NEED_IP(x) \ + if ((unsigned)(ip_end - ip) < (unsigned)(x)) goto input_overrun + +# undef TEST_OP /* don't need both of the tests here */ +# define TEST_OP 1 +# define NEED_OP(x) \ + if ((unsigned)(op_end - op) < (unsigned)(x)) goto output_overrun + +#define HAVE_ANY_OP 1 + +//#if defined(LZO_TEST_OVERRUN_LOOKBEHIND) +# define TEST_LB(m_pos) if (m_pos < out || m_pos >= op) goto lookbehind_overrun +//# define TEST_LBO(m_pos,o) if (m_pos < out || m_pos >= op - (o)) goto lookbehind_overrun +//#else +//# define TEST_LB(m_pos) ((void) 0) +//# define TEST_LBO(m_pos,o) ((void) 0) +//#endif diff --git a/archival/liblzo_interface.h b/archival/liblzo_interface.h new file mode 100644 index 000000000..9a84c0b6b --- /dev/null +++ b/archival/liblzo_interface.h @@ -0,0 +1,71 @@ +/* + This file is part of the LZO real-time data compression library. + + Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + Markus F.X.J. Oberhumer + http://www.oberhumer.com/opensource/lzo/ + + The LZO library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The LZO library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the LZO library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#define LZO1X +#undef LZO1Y + +#undef assert +/* +static void die_at(int line) +{ + bb_error_msg_and_die("internal error at %d", line); +} +#define assert(v) if (!(v)) die_at(__LINE__) +*/ +#define assert(v) ((void)0) + +int lzo1x_1_compress(const uint8_t* src, unsigned src_len, + uint8_t* dst, unsigned* dst_len, + void* wrkmem); +int lzo1x_1_15_compress(const uint8_t* src, unsigned src_len, + uint8_t* dst, unsigned* dst_len, + void* wrkmem); +int lzo1x_999_compress_level(const uint8_t* in, unsigned in_len, + uint8_t* out, unsigned* out_len, + void* wrkmem, + int compression_level); + +/* decompression */ +//int lzo1x_decompress(const uint8_t* src, unsigned src_len, +// uint8_t* dst, unsigned* dst_len, +// void* wrkmem /* NOT USED */); +/* safe decompression with overrun testing */ +int lzo1x_decompress_safe(const uint8_t* src, unsigned src_len, + uint8_t* dst, unsigned* dst_len, + void* wrkmem /* NOT USED */); + +#define LZO_E_OK 0 +#define LZO_E_ERROR (-1) +#define LZO_E_OUT_OF_MEMORY (-2) /* [not used right now] */ +#define LZO_E_NOT_COMPRESSIBLE (-3) /* [not used right now] */ +#define LZO_E_INPUT_OVERRUN (-4) +#define LZO_E_OUTPUT_OVERRUN (-5) +#define LZO_E_LOOKBEHIND_OVERRUN (-6) +#define LZO_E_EOF_NOT_FOUND (-7) +#define LZO_E_INPUT_NOT_CONSUMED (-8) +#define LZO_E_NOT_YET_IMPLEMENTED (-9) /* [not used right now] */ + +/* lzo-2.03/include/lzo/lzoconf.h */ +#define LZO_VERSION 0x2030 diff --git a/archival/lzo1x_1.c b/archival/lzo1x_1.c new file mode 100644 index 000000000..a88839846 --- /dev/null +++ b/archival/lzo1x_1.c @@ -0,0 +1,35 @@ +/* LZO1X-1 compression + + This file is part of the LZO real-time data compression library. + + Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + Markus F.X.J. Oberhumer + http://www.oberhumer.com/opensource/lzo/ + + The LZO library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The LZO library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the LZO library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +#include "libbb.h" +#include "liblzo.h" + +#define D_BITS 14 +#define D_INDEX1(d,p) d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5) +#define D_INDEX2(d,p) d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f) + +#define DO_COMPRESS lzo1x_1_compress + +#include "lzo1x_c.c" diff --git a/archival/lzo1x_1o.c b/archival/lzo1x_1o.c new file mode 100644 index 000000000..3c61253e0 --- /dev/null +++ b/archival/lzo1x_1o.c @@ -0,0 +1,35 @@ +/* LZO1X-1(15) compression + + This file is part of the LZO real-time data compression library. + + Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + Markus F.X.J. Oberhumer + http://www.oberhumer.com/opensource/lzo/ + + The LZO library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The LZO library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the LZO library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +#include "libbb.h" +#include "liblzo.h" + +#define D_BITS 15 +#define D_INDEX1(d,p) d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5) +#define D_INDEX2(d,p) d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f) + +#define DO_COMPRESS lzo1x_1_15_compress + +#include "lzo1x_c.c" diff --git a/archival/lzo1x_9x.c b/archival/lzo1x_9x.c new file mode 100644 index 000000000..d30e2e7d1 --- /dev/null +++ b/archival/lzo1x_9x.c @@ -0,0 +1,920 @@ +/* lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm + + This file is part of the LZO real-time data compression library. + + Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer + Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + The LZO library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The LZO library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the LZO library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + + Markus F.X.J. Oberhumer + + http://www.oberhumer.com/opensource/lzo/ +*/ +#include "libbb.h" + +/* The following is probably only safe on Intel-compatible processors ... */ +#define LZO_UNALIGNED_OK_2 +#define LZO_UNALIGNED_OK_4 + +#include "liblzo.h" + +#define LZO_MAX(a,b) ((a) >= (b) ? (a) : (b)) +#define LZO_MIN(a,b) ((a) <= (b) ? (a) : (b)) +#define LZO_MAX3(a,b,c) ((a) >= (b) ? LZO_MAX(a,c) : LZO_MAX(b,c)) + +/*********************************************************************** +// +************************************************************************/ +#define SWD_N M4_MAX_OFFSET /* size of ring buffer */ +#define SWD_F 2048 /* upper limit for match length */ + +#define SWD_BEST_OFF (LZO_MAX3(M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN) + 1) + +typedef struct { + int init; + + unsigned look; /* bytes in lookahead buffer */ + + unsigned m_len; + unsigned m_off; + + const uint8_t *bp; + const uint8_t *ip; + const uint8_t *in; + const uint8_t *in_end; + uint8_t *out; + + unsigned r1_lit; + +} lzo1x_999_t; + +#define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1)) + +/* lzo_swd.c -- sliding window dictionary */ + +/*********************************************************************** +// +************************************************************************/ +#define SWD_UINT_MAX USHRT_MAX + +#ifndef SWD_HSIZE +# define SWD_HSIZE 16384 +#endif +#ifndef SWD_MAX_CHAIN +# define SWD_MAX_CHAIN 2048 +#endif + +#define HEAD3(b, p) \ + ( ((0x9f5f * ((((b[p]<<5)^b[p+1])<<5) ^ b[p+2])) >> 5) & (SWD_HSIZE-1) ) + +#if defined(LZO_UNALIGNED_OK_2) +# define HEAD2(b,p) (* (uint16_t *) &(b[p])) +#else +# define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8)) +#endif +#define NIL2 SWD_UINT_MAX + +typedef struct lzo_swd { + /* public - "built-in" */ + + /* public - configuration */ + unsigned max_chain; + int use_best_off; + + /* public - output */ + unsigned m_len; + unsigned m_off; + unsigned look; + int b_char; +#if defined(SWD_BEST_OFF) + unsigned best_off[SWD_BEST_OFF]; +#endif + + /* semi public */ + lzo1x_999_t *c; + unsigned m_pos; +#if defined(SWD_BEST_OFF) + unsigned best_pos[SWD_BEST_OFF]; +#endif + + /* private */ + unsigned ip; /* input pointer (lookahead) */ + unsigned bp; /* buffer pointer */ + unsigned rp; /* remove pointer */ + + unsigned node_count; + unsigned first_rp; + + uint8_t b[SWD_N + SWD_F]; + uint8_t b_wrap[SWD_F]; /* must follow b */ + uint16_t head3[SWD_HSIZE]; + uint16_t succ3[SWD_N + SWD_F]; + uint16_t best3[SWD_N + SWD_F]; + uint16_t llen3[SWD_HSIZE]; +#ifdef HEAD2 + uint16_t head2[65536L]; +#endif +} lzo_swd_t, *lzo_swd_p; + +#define SIZEOF_LZO_SWD_T (sizeof(lzo_swd_t)) + + +/* Access macro for head3. + * head3[key] may be uninitialized, but then its value will never be used. + */ +#define s_get_head3(s,key) s->head3[key] + + +/*********************************************************************** +// +************************************************************************/ +#define B_SIZE (SWD_N + SWD_F) + +static int swd_init(lzo_swd_p s) +{ + /* defaults */ + s->node_count = SWD_N; + + memset(s->llen3, 0, sizeof(s->llen3[0]) * (unsigned)SWD_HSIZE); +#ifdef HEAD2 + memset(s->head2, 0xff, sizeof(s->head2[0]) * 65536L); + assert(s->head2[0] == NIL2); +#endif + + s->ip = 0; + s->bp = s->ip; + s->first_rp = s->ip; + + assert(s->ip + SWD_F <= B_SIZE); + s->look = (unsigned) (s->c->in_end - s->c->ip); + if (s->look > 0) { + if (s->look > SWD_F) + s->look = SWD_F; + memcpy(&s->b[s->ip],s->c->ip,s->look); + s->c->ip += s->look; + s->ip += s->look; + } + if (s->ip == B_SIZE) + s->ip = 0; + + s->rp = s->first_rp; + if (s->rp >= s->node_count) + s->rp -= s->node_count; + else + s->rp += B_SIZE - s->node_count; + + return LZO_E_OK; +} + +#define swd_pos2off(s,pos) \ + (s->bp > (pos) ? s->bp - (pos) : B_SIZE - ((pos) - s->bp)) + + +/*********************************************************************** +// +************************************************************************/ +static void swd_getbyte(lzo_swd_p s) +{ + int c; + + if ((c = getbyte(*(s->c))) < 0) { + if (s->look > 0) + --s->look; + } else { + s->b[s->ip] = c; + if (s->ip < SWD_F) + s->b_wrap[s->ip] = c; + } + if (++s->ip == B_SIZE) + s->ip = 0; + if (++s->bp == B_SIZE) + s->bp = 0; + if (++s->rp == B_SIZE) + s->rp = 0; +} + + +/*********************************************************************** +// remove node from lists +************************************************************************/ +static void swd_remove_node(lzo_swd_p s, unsigned node) +{ + if (s->node_count == 0) { + unsigned key; + + key = HEAD3(s->b,node); + assert(s->llen3[key] > 0); + --s->llen3[key]; + +#ifdef HEAD2 + key = HEAD2(s->b,node); + assert(s->head2[key] != NIL2); + if ((unsigned) s->head2[key] == node) + s->head2[key] = NIL2; +#endif + } else + --s->node_count; +} + + +/*********************************************************************** +// +************************************************************************/ +static void swd_accept(lzo_swd_p s, unsigned n) +{ + assert(n <= s->look); + + while (n--) { + unsigned key; + + swd_remove_node(s,s->rp); + + /* add bp into HEAD3 */ + key = HEAD3(s->b,s->bp); + s->succ3[s->bp] = s_get_head3(s,key); + s->head3[key] = s->bp; + s->best3[s->bp] = SWD_F + 1; + s->llen3[key]++; + assert(s->llen3[key] <= SWD_N); + +#ifdef HEAD2 + /* add bp into HEAD2 */ + key = HEAD2(s->b,s->bp); + s->head2[key] = s->bp; +#endif + + swd_getbyte(s); + } +} + + +/*********************************************************************** +// +************************************************************************/ +static void swd_search(lzo_swd_p s, unsigned node, unsigned cnt) +{ + const uint8_t *p1; + const uint8_t *p2; + const uint8_t *px; + unsigned m_len = s->m_len; + const uint8_t *b = s->b; + const uint8_t *bp = s->b + s->bp; + const uint8_t *bx = s->b + s->bp + s->look; + unsigned char scan_end1; + + assert(s->m_len > 0); + + scan_end1 = bp[m_len - 1]; + for ( ; cnt-- > 0; node = s->succ3[node]) { + p1 = bp; + p2 = b + node; + px = bx; + + assert(m_len < s->look); + + if (p2[m_len - 1] == scan_end1 && + p2[m_len] == p1[m_len] && + p2[0] == p1[0] && + p2[1] == p1[1]) { + unsigned i; + assert(lzo_memcmp(bp,&b[node],3) == 0); + + p1 += 2; p2 += 2; + do {} while (++p1 < px && *p1 == *++p2); + i = p1-bp; + + assert(lzo_memcmp(bp,&b[node],i) == 0); + +#if defined(SWD_BEST_OFF) + if (i < SWD_BEST_OFF) { + if (s->best_pos[i] == 0) + s->best_pos[i] = node + 1; + } +#endif + if (i > m_len) { + s->m_len = m_len = i; + s->m_pos = node; + if (m_len == s->look) + return; + if (m_len >= SWD_F) + return; + if (m_len > (unsigned) s->best3[node]) + return; + scan_end1 = bp[m_len - 1]; + } + } + } +} + + +/*********************************************************************** +// +************************************************************************/ +#ifdef HEAD2 + +static int swd_search2(lzo_swd_p s) +{ + unsigned key; + + assert(s->look >= 2); + assert(s->m_len > 0); + + key = s->head2[ HEAD2(s->b,s->bp) ]; + if (key == NIL2) + return 0; + assert(lzo_memcmp(&s->b[s->bp],&s->b[key],2) == 0); +#if defined(SWD_BEST_OFF) + if (s->best_pos[2] == 0) + s->best_pos[2] = key + 1; +#endif + + if (s->m_len < 2) { + s->m_len = 2; + s->m_pos = key; + } + return 1; +} + +#endif + + +/*********************************************************************** +// +************************************************************************/ +static void swd_findbest(lzo_swd_p s) +{ + unsigned key; + unsigned cnt, node; + unsigned len; + + assert(s->m_len > 0); + + /* get current head, add bp into HEAD3 */ + key = HEAD3(s->b,s->bp); + node = s->succ3[s->bp] = s_get_head3(s,key); + cnt = s->llen3[key]++; + assert(s->llen3[key] <= SWD_N + SWD_F); + if (cnt > s->max_chain) + cnt = s->max_chain; + s->head3[key] = s->bp; + + s->b_char = s->b[s->bp]; + len = s->m_len; + if (s->m_len >= s->look) { + if (s->look == 0) + s->b_char = -1; + s->m_off = 0; + s->best3[s->bp] = SWD_F + 1; + } else { +#ifdef HEAD2 + if (swd_search2(s)) +#endif + if (s->look >= 3) + swd_search(s,node,cnt); + if (s->m_len > len) + s->m_off = swd_pos2off(s,s->m_pos); + s->best3[s->bp] = s->m_len; + +#if defined(SWD_BEST_OFF) + if (s->use_best_off) { + int i; + for (i = 2; i < SWD_BEST_OFF; i++) + if (s->best_pos[i] > 0) + s->best_off[i] = swd_pos2off(s,s->best_pos[i]-1); + else + s->best_off[i] = 0; + } +#endif + } + + swd_remove_node(s,s->rp); + +#ifdef HEAD2 + /* add bp into HEAD2 */ + key = HEAD2(s->b,s->bp); + s->head2[key] = s->bp; +#endif +} + +#undef HEAD3 +#undef HEAD2 +#undef s_get_head3 + + +/*********************************************************************** +// +************************************************************************/ +static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off) +{ + int r; + + assert(!c->init); + c->init = 1; + + s->c = c; + + r = swd_init(s); + if (r != 0) + return r; + + s->use_best_off = use_best_off; + return r; +} + + +/*********************************************************************** +// +************************************************************************/ +static int find_match(lzo1x_999_t *c, lzo_swd_p s, + unsigned this_len, unsigned skip) +{ + assert(c->init); + + if (skip > 0) { + assert(this_len >= skip); + swd_accept(s, this_len - skip); + } else { + assert(this_len <= 1); + } + + s->m_len = 1; + s->m_len = 1; +#ifdef SWD_BEST_OFF + if (s->use_best_off) + memset(s->best_pos,0,sizeof(s->best_pos)); +#endif + swd_findbest(s); + c->m_len = s->m_len; + c->m_off = s->m_off; + + swd_getbyte(s); + + if (s->b_char < 0) { + c->look = 0; + c->m_len = 0; + } else { + c->look = s->look + 1; + } + c->bp = c->ip - c->look; + + return LZO_E_OK; +} + +/* this is a public functions, but there is no prototype in a header file */ +static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len, + uint8_t *out, unsigned *out_len, + void *wrkmem, + unsigned good_length, + unsigned max_lazy, + unsigned max_chain, + uint32_t use_best_off); + + +/*********************************************************************** +// +************************************************************************/ +static uint8_t *code_match(lzo1x_999_t *c, + uint8_t *op, unsigned m_len, unsigned m_off) +{ + assert(op > c->out); + if (m_len == 2) { + assert(m_off <= M1_MAX_OFFSET); + assert(c->r1_lit > 0); assert(c->r1_lit < 4); + m_off -= 1; + *op++ = M1_MARKER | ((m_off & 3) << 2); + *op++ = m_off >> 2; + } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) { + assert(m_len >= 3); + m_off -= 1; + *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2); + *op++ = m_off >> 3; + assert(op[-2] >= M2_MARKER); + } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) { + assert(m_len == 3); + assert(m_off > M2_MAX_OFFSET); + m_off -= 1 + M2_MAX_OFFSET; + *op++ = M1_MARKER | ((m_off & 3) << 2); + *op++ = m_off >> 2; + } else if (m_off <= M3_MAX_OFFSET) { + assert(m_len >= 3); + m_off -= 1; + if (m_len <= M3_MAX_LEN) + *op++ = M3_MARKER | (m_len - 2); + else { + m_len -= M3_MAX_LEN; + *op++ = M3_MARKER | 0; + while (m_len > 255) + { + m_len -= 255; + *op++ = 0; + } + assert(m_len > 0); + *op++ = m_len; + } + *op++ = m_off << 2; + *op++ = m_off >> 6; + } else { + unsigned k; + + assert(m_len >= 3); + assert(m_off > 0x4000); assert(m_off <= 0xbfff); + m_off -= 0x4000; + k = (m_off & 0x4000) >> 11; + if (m_len <= M4_MAX_LEN) + *op++ = M4_MARKER | k | (m_len - 2); + else { + m_len -= M4_MAX_LEN; + *op++ = M4_MARKER | k | 0; + while (m_len > 255) + { + m_len -= 255; + *op++ = 0; + } + assert(m_len > 0); + *op++ = m_len; + } + *op++ = m_off << 2; + *op++ = m_off >> 6; + } + + return op; +} + + +static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op, + const uint8_t *ii, unsigned t) +{ + if (op == c->out && t <= 238) { + *op++ = 17 + t; + } else if (t <= 3) { + op[-2] |= t; + } else if (t <= 18) { + *op++ = t - 3; + } else { + unsigned tt = t - 18; + + *op++ = 0; + while (tt > 255) { + tt -= 255; + *op++ = 0; + } + assert(tt > 0); + *op++ = tt; + } + do *op++ = *ii++; while (--t > 0); + + return op; +} + + +static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii, + unsigned lit) +{ + if (lit > 0) { + assert(m_len >= 2); + op = STORE_RUN(c,op,ii,lit); + } else { + assert(m_len >= 3); + } + c->r1_lit = lit; + + return op; +} + + +/*********************************************************************** +// +************************************************************************/ +static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit) +{ + int n = 4; + + if (m_len < 2) + return -1; + if (m_len == 2) + return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1; + if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) + return 2; + if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4) + return 2; + if (m_off <= M3_MAX_OFFSET) { + if (m_len <= M3_MAX_LEN) + return 3; + m_len -= M3_MAX_LEN; + } else if (m_off <= M4_MAX_OFFSET) { + if (m_len <= M4_MAX_LEN) + return 3; + m_len -= M4_MAX_LEN; + } else + return -1; + while (m_len > 255) { + m_len -= 255; + n++; + } + return n; +} + + +static int min_gain(unsigned ahead, unsigned lit1, + unsigned lit2, int l1, int l2, int l3) +{ + int lazy_match_min_gain = 0; + + assert (ahead >= 1); + lazy_match_min_gain += ahead; + + if (lit1 <= 3) + lazy_match_min_gain += (lit2 <= 3) ? 0 : 2; + else if (lit1 <= 18) + lazy_match_min_gain += (lit2 <= 18) ? 0 : 1; + + lazy_match_min_gain += (l2 - l1) * 2; + if (l3 > 0) + lazy_match_min_gain -= (ahead - l3) * 2; + + if (lazy_match_min_gain < 0) + lazy_match_min_gain = 0; + + return lazy_match_min_gain; +} + + +/*********************************************************************** +// +************************************************************************/ +#if defined(SWD_BEST_OFF) + +static void better_match(const lzo_swd_p swd, + unsigned *m_len, unsigned *m_off) +{ + + if (*m_len <= M2_MIN_LEN) + return; + + if (*m_off <= M2_MAX_OFFSET) + return; + + /* M3/M4 -> M2 */ + if (*m_off > M2_MAX_OFFSET && + *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1 && + swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET) + { + *m_len = *m_len - 1; + *m_off = swd->best_off[*m_len]; + return; + } + + /* M4 -> M2 */ + if (*m_off > M3_MAX_OFFSET && + *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2 && + swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET) + { + *m_len = *m_len - 2; + *m_off = swd->best_off[*m_len]; + return; + } + /* M4 -> M3 */ + if (*m_off > M3_MAX_OFFSET && + *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1 && + swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET) + { + *m_len = *m_len - 1; + *m_off = swd->best_off[*m_len]; + } +} + +#endif + + +/*********************************************************************** +// +************************************************************************/ +static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len, + uint8_t *out, unsigned *out_len, + void *wrkmem, + unsigned good_length, + unsigned max_lazy, + unsigned max_chain, + uint32_t use_best_off) +{ + uint8_t *op; + const uint8_t *ii; + unsigned lit; + unsigned m_len, m_off; + lzo1x_999_t cc; + lzo1x_999_t * const c = &cc; + lzo_swd_p const swd = (lzo_swd_p) wrkmem; + int r; + + c->init = 0; + c->ip = c->in = in; + c->in_end = in + in_len; + c->out = out; + + op = out; + ii = c->ip; /* point to start of literal run */ + lit = 0; + c->r1_lit = 0; + + r = init_match(c, swd, use_best_off); + if (r != 0) + return r; + swd->max_chain = max_chain; + + r = find_match(c, swd, 0, 0); + if (r != 0) + return r; + + while (c->look > 0) { + unsigned ahead; + unsigned max_ahead; + int l1, l2, l3; + + m_len = c->m_len; + m_off = c->m_off; + + assert(c->bp == c->ip - c->look); + assert(c->bp >= in); + if (lit == 0) + ii = c->bp; + assert(ii + lit == c->bp); + assert(swd->b_char == *(c->bp)); + + if ( m_len < 2 || + (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4)) || + /* Do not accept this match for compressed-data compatibility + * with LZO v1.01 and before + * [ might be a problem for decompress() and optimize() ] + */ + (m_len == 2 && op == out) || + (op == out && lit == 0)) + { + /* a literal */ + m_len = 0; + } + else if (m_len == M2_MIN_LEN) { + /* compression ratio improves if we code a literal in some cases */ + if (m_off > MX_MAX_OFFSET && lit >= 4) + m_len = 0; + } + + if (m_len == 0) { + /* a literal */ + lit++; + swd->max_chain = max_chain; + r = find_match(c,swd,1,0); + assert(r == 0); + continue; + } + + /* a match */ +#if defined(SWD_BEST_OFF) + if (swd->use_best_off) + better_match(swd,&m_len,&m_off); +#endif + + /* shall we try a lazy match ? */ + ahead = 0; + if (m_len >= max_lazy) { + /* no */ + l1 = 0; + max_ahead = 0; + } else { + /* yes, try a lazy match */ + l1 = len_of_coded_match(m_len,m_off,lit); + assert(l1 > 0); + max_ahead = LZO_MIN(2, (unsigned)l1 - 1); + } + + + while (ahead < max_ahead && c->look > m_len) { + int lazy_match_min_gain; + + if (m_len >= good_length) + swd->max_chain = max_chain >> 2; + else + swd->max_chain = max_chain; + r = find_match(c,swd,1,0); + ahead++; + + assert(r == 0); + assert(c->look > 0); + assert(ii + lit + ahead == c->bp); + + if (c->m_len < m_len) + continue; + if (c->m_len == m_len && c->m_off >= m_off) + continue; +#if defined(SWD_BEST_OFF) + if (swd->use_best_off) + better_match(swd,&c->m_len,&c->m_off); +#endif + l2 = len_of_coded_match(c->m_len,c->m_off,lit+ahead); + if (l2 < 0) + continue; + + /* compressed-data compatibility [see above] */ + l3 = (op == out) ? -1 : len_of_coded_match(ahead,m_off,lit); + + lazy_match_min_gain = min_gain(ahead,lit,lit+ahead,l1,l2,l3); + if (c->m_len >= m_len + lazy_match_min_gain) { + if (l3 > 0) { + /* code previous run */ + op = code_run(c,op,ii,lit); + lit = 0; + /* code shortened match */ + op = code_match(c,op,ahead,m_off); + } else { + lit += ahead; + assert(ii + lit == c->bp); + } + goto lazy_match_done; + } + } + + assert(ii + lit + ahead == c->bp); + + /* 1 - code run */ + op = code_run(c,op,ii,lit); + lit = 0; + + /* 2 - code match */ + op = code_match(c,op,m_len,m_off); + swd->max_chain = max_chain; + r = find_match(c,swd,m_len,1+ahead); + assert(r == 0); + + lazy_match_done: ; + } + + /* store final run */ + if (lit > 0) + op = STORE_RUN(c,op,ii,lit); + +#if defined(LZO_EOF_CODE) + *op++ = M4_MARKER | 1; + *op++ = 0; + *op++ = 0; +#endif + + *out_len = op - out; + + return LZO_E_OK; +} + + +/*********************************************************************** +// +************************************************************************/ +int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len, + uint8_t *out, unsigned *out_len, + void *wrkmem, + int compression_level) +{ + static const struct { + uint16_t good_length; + uint16_t max_lazy; + uint16_t max_chain; + uint16_t use_best_off; + } c[3] = { + { 8, 32, 256, 0 }, + { 32, 128, 2048, 1 }, + { SWD_F, SWD_F, 4096, 1 } /* max. compression */ + }; + + if (compression_level < 7 || compression_level > 9) + return LZO_E_ERROR; + + compression_level -= 7; + return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem, + c[compression_level].good_length, + c[compression_level].max_lazy, + c[compression_level].max_chain, + c[compression_level].use_best_off); +} diff --git a/archival/lzo1x_c.c b/archival/lzo1x_c.c new file mode 100644 index 000000000..cc86f74b1 --- /dev/null +++ b/archival/lzo1x_c.c @@ -0,0 +1,296 @@ +/* implementation of the LZO1[XY]-1 compression algorithm + + This file is part of the LZO real-time data compression library. + + Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + Markus F.X.J. Oberhumer + http://www.oberhumer.com/opensource/lzo/ + + The LZO library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The LZO library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the LZO library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/*********************************************************************** +// compress a block of data. +************************************************************************/ +static NOINLINE unsigned +do_compress(const uint8_t* in, unsigned in_len, + uint8_t* out, unsigned* out_len, + void* wrkmem) +{ + register const uint8_t* ip; + uint8_t* op; + const uint8_t* const in_end = in + in_len; + const uint8_t* const ip_end = in + in_len - M2_MAX_LEN - 5; + const uint8_t* ii; + const void* *const dict = (const void**) wrkmem; + + op = out; + ip = in; + ii = ip; + + ip += 4; + for (;;) { + register const uint8_t* m_pos; + unsigned m_off; + unsigned m_len; + unsigned dindex; + + D_INDEX1(dindex,ip); + GINDEX(m_pos,m_off,dict,dindex,in); + if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) + goto literal; +#if 1 + if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) + goto try_match; + D_INDEX2(dindex,ip); +#endif + GINDEX(m_pos,m_off,dict,dindex,in); + if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) + goto literal; + if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) + goto try_match; + goto literal; + + try_match: +#if 1 && defined(LZO_UNALIGNED_OK_2) + if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip) +#else + if (m_pos[0] != ip[0] || m_pos[1] != ip[1]) +#endif + { + } else { + if (m_pos[2] == ip[2]) { +#if 0 + if (m_off <= M2_MAX_OFFSET) + goto match; + if (lit <= 3) + goto match; + if (lit == 3) { /* better compression, but slower */ + assert(op - 2 > out); op[-2] |= (uint8_t)(3); + *op++ = *ii++; *op++ = *ii++; *op++ = *ii++; + goto code_match; + } + if (m_pos[3] == ip[3]) +#endif + goto match; + } + else { + /* still need a better way for finding M1 matches */ +#if 0 + /* a M1 match */ +#if 0 + if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3) +#else + if (m_off <= M1_MAX_OFFSET && lit == 3) +#endif + { + register unsigned t; + + t = lit; + assert(op - 2 > out); op[-2] |= (uint8_t)(t); + do *op++ = *ii++; while (--t > 0); + assert(ii == ip); + m_off -= 1; + *op++ = (uint8_t)(M1_MARKER | ((m_off & 3) << 2)); + *op++ = (uint8_t)(m_off >> 2); + ip += 2; + goto match_done; + } +#endif + } + } + + /* a literal */ + literal: + UPDATE_I(dict, 0, dindex, ip, in); + ++ip; + if (ip >= ip_end) + break; + continue; + + /* a match */ +match: + UPDATE_I(dict, 0, dindex, ip, in); + /* store current literal run */ + if (pd(ip, ii) > 0) { + register unsigned t = pd(ip, ii); + + if (t <= 3) { + assert(op - 2 > out); + op[-2] |= (uint8_t)(t); + } + else if (t <= 18) + *op++ = (uint8_t)(t - 3); + else { + register unsigned tt = t - 18; + + *op++ = 0; + while (tt > 255) { + tt -= 255; + *op++ = 0; + } + assert(tt > 0); + *op++ = (uint8_t)(tt); + } + do *op++ = *ii++; while (--t > 0); + } + + /* code the match */ + assert(ii == ip); + ip += 3; + if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ + || m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++ +#ifdef LZO1Y + || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++ + || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++ +#endif + ) { + --ip; + m_len = pd(ip, ii); + assert(m_len >= 3); + assert(m_len <= M2_MAX_LEN); + + if (m_off <= M2_MAX_OFFSET) { + m_off -= 1; +#if defined(LZO1X) + *op++ = (uint8_t)(((m_len - 1) << 5) | ((m_off & 7) << 2)); + *op++ = (uint8_t)(m_off >> 3); +#elif defined(LZO1Y) + *op++ = (uint8_t)(((m_len + 1) << 4) | ((m_off & 3) << 2)); + *op++ = (uint8_t)(m_off >> 2); +#endif + } + else if (m_off <= M3_MAX_OFFSET) { + m_off -= 1; + *op++ = (uint8_t)(M3_MARKER | (m_len - 2)); + goto m3_m4_offset; + } else { +#if defined(LZO1X) + m_off -= 0x4000; + assert(m_off > 0); + assert(m_off <= 0x7fff); + *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2)); + goto m3_m4_offset; +#elif defined(LZO1Y) + goto m4_match; +#endif + } + } + else { + { + const uint8_t* end = in_end; + const uint8_t* m = m_pos + M2_MAX_LEN + 1; + while (ip < end && *m == *ip) + m++, ip++; + m_len = pd(ip, ii); + } + assert(m_len > M2_MAX_LEN); + + if (m_off <= M3_MAX_OFFSET) { + m_off -= 1; + if (m_len <= 33) + *op++ = (uint8_t)(M3_MARKER | (m_len - 2)); + else { + m_len -= 33; + *op++ = M3_MARKER | 0; + goto m3_m4_len; + } + } else { +#if defined(LZO1Y) + m4_match: +#endif + m_off -= 0x4000; + assert(m_off > 0); + assert(m_off <= 0x7fff); + if (m_len <= M4_MAX_LEN) + *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11) | (m_len - 2)); + else { + m_len -= M4_MAX_LEN; + *op++ = (uint8_t)(M4_MARKER | ((m_off & 0x4000) >> 11)); + m3_m4_len: + while (m_len > 255) { + m_len -= 255; + *op++ = 0; + } + assert(m_len > 0); + *op++ = (uint8_t)(m_len); + } + } + m3_m4_offset: + *op++ = (uint8_t)((m_off & 63) << 2); + *op++ = (uint8_t)(m_off >> 6); + } +#if 0 + match_done: +#endif + ii = ip; + if (ip >= ip_end) + break; + } + + *out_len = pd(op, out); + return pd(in_end, ii); +} + +/*********************************************************************** +// public entry point +************************************************************************/ +int DO_COMPRESS(const uint8_t* in, unsigned in_len, + uint8_t* out, unsigned* out_len, + void* wrkmem) +{ + uint8_t* op = out; + unsigned t; + + if (in_len <= M2_MAX_LEN + 5) + t = in_len; + else { + t = do_compress(in,in_len,op,out_len,wrkmem); + op += *out_len; + } + + if (t > 0) { + const uint8_t* ii = in + in_len - t; + + if (op == out && t <= 238) + *op++ = (uint8_t)(17 + t); + else if (t <= 3) + op[-2] |= (uint8_t)(t); + else if (t <= 18) + *op++ = (uint8_t)(t - 3); + else { + unsigned tt = t - 18; + + *op++ = 0; + while (tt > 255) { + tt -= 255; + *op++ = 0; + } + assert(tt > 0); + *op++ = (uint8_t)(tt); + } + do *op++ = *ii++; while (--t > 0); + } + + *op++ = M4_MARKER | 1; + *op++ = 0; + *op++ = 0; + + *out_len = pd(op, out); + return 0; /*LZO_E_OK*/ +} diff --git a/archival/lzo1x_d.c b/archival/lzo1x_d.c new file mode 100644 index 000000000..348a85510 --- /dev/null +++ b/archival/lzo1x_d.c @@ -0,0 +1,420 @@ +/* implementation of the LZO1X decompression algorithm + + This file is part of the LZO real-time data compression library. + + Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + Markus F.X.J. Oberhumer + http://www.oberhumer.com/opensource/lzo/ + + The LZO library is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + The LZO library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with the LZO library; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ +#include "libbb.h" +#include "liblzo.h" + +/*********************************************************************** +// decompress a block of data. +************************************************************************/ +/* safe decompression with overrun testing */ +int lzo1x_decompress_safe(const uint8_t* in, unsigned in_len, + uint8_t* out, unsigned* out_len, + void* wrkmem UNUSED_PARAM) +{ + register uint8_t* op; + register const uint8_t* ip; + register unsigned t; +#if defined(COPY_DICT) + unsigned m_off; + const uint8_t* dict_end; +#else + register const uint8_t* m_pos = NULL; /* possibly not needed */ +#endif + const uint8_t* const ip_end = in + in_len; +#if defined(HAVE_ANY_OP) + uint8_t* const op_end = out + *out_len; +#endif +#if defined(LZO1Z) + unsigned last_m_off = 0; +#endif + +// LZO_UNUSED(wrkmem); + +#if defined(COPY_DICT) + if (dict) { + if (dict_len > M4_MAX_OFFSET) { + dict += dict_len - M4_MAX_OFFSET; + dict_len = M4_MAX_OFFSET; + } + dict_end = dict + dict_len; + } else { + dict_len = 0; + dict_end = NULL; + } +#endif /* COPY_DICT */ + + *out_len = 0; + + op = out; + ip = in; + + if (*ip > 17) { + t = *ip++ - 17; + if (t < 4) + goto match_next; + assert(t > 0); NEED_OP(t); NEED_IP(t+1); + do *op++ = *ip++; while (--t > 0); + goto first_literal_run; + } + + while (TEST_IP && TEST_OP) { + t = *ip++; + if (t >= 16) + goto match; + /* a literal run */ + if (t == 0) { + NEED_IP(1); + while (*ip == 0) { + t += 255; + ip++; + NEED_IP(1); + } + t += 15 + *ip++; + } + /* copy literals */ + assert(t > 0); + NEED_OP(t+3); + NEED_IP(t+4); +#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4) +# if !defined(LZO_UNALIGNED_OK_4) + if (PTR_ALIGNED2_4(op, ip)) +# endif + { + COPY4(op, ip); + op += 4; + ip += 4; + if (--t > 0) { + if (t >= 4) { + do { + COPY4(op, ip); + op += 4; + ip += 4; + t -= 4; + } while (t >= 4); + if (t > 0) + do *op++ = *ip++; while (--t > 0); + } else { + do *op++ = *ip++; while (--t > 0); + } + } + } +# if !defined(LZO_UNALIGNED_OK_4) + else +# endif +#endif +#if !defined(LZO_UNALIGNED_OK_4) + { + *op++ = *ip++; + *op++ = *ip++; + *op++ = *ip++; + do *op++ = *ip++; while (--t > 0); + } +#endif + + first_literal_run: + t = *ip++; + if (t >= 16) + goto match; +#if defined(COPY_DICT) +#if defined(LZO1Z) + m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2); + last_m_off = m_off; +#else + m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2); +#endif + NEED_OP(3); + t = 3; COPY_DICT(t,m_off) +#else /* !COPY_DICT */ +#if defined(LZO1Z) + t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2); + m_pos = op - t; + last_m_off = t; +#else + m_pos = op - (1 + M2_MAX_OFFSET); + m_pos -= t >> 2; + m_pos -= *ip++ << 2; +#endif + TEST_LB(m_pos); NEED_OP(3); + *op++ = *m_pos++; + *op++ = *m_pos++; + *op++ = *m_pos; +#endif /* COPY_DICT */ + goto match_done; + + /* handle matches */ + do { + match: + if (t >= 64) { /* a M2 match */ +#if defined(COPY_DICT) +#if defined(LZO1X) + m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3); + t = (t >> 5) - 1; +#elif defined(LZO1Y) + m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2); + t = (t >> 4) - 3; +#elif defined(LZO1Z) + m_off = t & 0x1f; + if (m_off >= 0x1c) + m_off = last_m_off; + else { + m_off = 1 + (m_off << 6) + (*ip++ >> 2); + last_m_off = m_off; + } + t = (t >> 5) - 1; +#endif +#else /* !COPY_DICT */ +#if defined(LZO1X) + m_pos = op - 1; + m_pos -= (t >> 2) & 7; + m_pos -= *ip++ << 3; + t = (t >> 5) - 1; +#elif defined(LZO1Y) + m_pos = op - 1; + m_pos -= (t >> 2) & 3; + m_pos -= *ip++ << 2; + t = (t >> 4) - 3; +#elif defined(LZO1Z) + { + unsigned off = t & 0x1f; + m_pos = op; + if (off >= 0x1c) { + assert(last_m_off > 0); + m_pos -= last_m_off; + } else { + off = 1 + (off << 6) + (*ip++ >> 2); + m_pos -= off; + last_m_off = off; + } + } + t = (t >> 5) - 1; +#endif + TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1); + goto copy_match; +#endif /* COPY_DICT */ + } + else if (t >= 32) { /* a M3 match */ + t &= 31; + if (t == 0) { + NEED_IP(1); + while (*ip == 0) { + t += 255; + ip++; + NEED_IP(1); + } + t += 31 + *ip++; + } +#if defined(COPY_DICT) +#if defined(LZO1Z) + m_off = 1 + (ip[0] << 6) + (ip[1] >> 2); + last_m_off = m_off; +#else + m_off = 1 + (ip[0] >> 2) + (ip[1] << 6); +#endif +#else /* !COPY_DICT */ +#if defined(LZO1Z) + { + unsigned off = 1 + (ip[0] << 6) + (ip[1] >> 2); + m_pos = op - off; + last_m_off = off; + } +#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN) + m_pos = op - 1; + m_pos -= (* (const lzo_ushortp) ip) >> 2; +#else + m_pos = op - 1; + m_pos -= (ip[0] >> 2) + (ip[1] << 6); +#endif +#endif /* COPY_DICT */ + ip += 2; + } + else if (t >= 16) { /* a M4 match */ +#if defined(COPY_DICT) + m_off = (t & 8) << 11; +#else /* !COPY_DICT */ + m_pos = op; + m_pos -= (t & 8) << 11; +#endif /* COPY_DICT */ + t &= 7; + if (t == 0) { + NEED_IP(1); + while (*ip == 0) { + t += 255; + ip++; + NEED_IP(1); + } + t += 7 + *ip++; + } +#if defined(COPY_DICT) +#if defined(LZO1Z) + m_off += (ip[0] << 6) + (ip[1] >> 2); +#else + m_off += (ip[0] >> 2) + (ip[1] << 6); +#endif + ip += 2; + if (m_off == 0) + goto eof_found; + m_off += 0x4000; +#if defined(LZO1Z) + last_m_off = m_off; +#endif +#else /* !COPY_DICT */ +#if defined(LZO1Z) + m_pos -= (ip[0] << 6) + (ip[1] >> 2); +#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN) + m_pos -= (* (const lzo_ushortp) ip) >> 2; +#else + m_pos -= (ip[0] >> 2) + (ip[1] << 6); +#endif + ip += 2; + if (m_pos == op) + goto eof_found; + m_pos -= 0x4000; +#if defined(LZO1Z) + last_m_off = pd((const uint8_t*)op, m_pos); +#endif +#endif /* COPY_DICT */ + } + else { /* a M1 match */ +#if defined(COPY_DICT) +#if defined(LZO1Z) + m_off = 1 + (t << 6) + (*ip++ >> 2); + last_m_off = m_off; +#else + m_off = 1 + (t >> 2) + (*ip++ << 2); +#endif + NEED_OP(2); + t = 2; COPY_DICT(t,m_off) +#else /* !COPY_DICT */ +#if defined(LZO1Z) + t = 1 + (t << 6) + (*ip++ >> 2); + m_pos = op - t; + last_m_off = t; +#else + m_pos = op - 1; + m_pos -= t >> 2; + m_pos -= *ip++ << 2; +#endif + TEST_LB(m_pos); NEED_OP(2); + *op++ = *m_pos++; + *op++ = *m_pos; +#endif /* COPY_DICT */ + goto match_done; + } + + /* copy match */ +#if defined(COPY_DICT) + + NEED_OP(t+3-1); + t += 3-1; COPY_DICT(t,m_off) + +#else /* !COPY_DICT */ + + TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1); +#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4) +# if !defined(LZO_UNALIGNED_OK_4) + if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) { + assert((op - m_pos) >= 4); /* both pointers are aligned */ +# else + if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) { +# endif + COPY4(op,m_pos); + op += 4; m_pos += 4; t -= 4 - (3 - 1); + do { + COPY4(op,m_pos); + op += 4; m_pos += 4; t -= 4; + } while (t >= 4); + if (t > 0) + do *op++ = *m_pos++; while (--t > 0); + } + else +#endif + { + copy_match: + *op++ = *m_pos++; *op++ = *m_pos++; + do *op++ = *m_pos++; while (--t > 0); + } + +#endif /* COPY_DICT */ + + match_done: +#if defined(LZO1Z) + t = ip[-1] & 3; +#else + t = ip[-2] & 3; +#endif + if (t == 0) + break; + + /* copy literals */ + match_next: + assert(t > 0); + assert(t < 4); + NEED_OP(t); + NEED_IP(t+1); +#if 0 + do *op++ = *ip++; while (--t > 0); +#else + *op++ = *ip++; + if (t > 1) { + *op++ = *ip++; + if (t > 2) + *op++ = *ip++; + } +#endif + t = *ip++; + } while (TEST_IP && TEST_OP); + } + +//#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP) + /* no EOF code was found */ + *out_len = pd(op, out); + return LZO_E_EOF_NOT_FOUND; +//#endif + + eof_found: + assert(t == 1); + *out_len = pd(op, out); + return (ip == ip_end ? LZO_E_OK : + (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); + +//#if defined(HAVE_NEED_IP) + input_overrun: + *out_len = pd(op, out); + return LZO_E_INPUT_OVERRUN; +//#endif + +//#if defined(HAVE_NEED_OP) + output_overrun: + *out_len = pd(op, out); + return LZO_E_OUTPUT_OVERRUN; +//#endif + +//#if defined(LZO_TEST_OVERRUN_LOOKBEHIND) + lookbehind_overrun: + *out_len = pd(op, out); + return LZO_E_LOOKBEHIND_OVERRUN; +//#endif +} diff --git a/archival/lzop.c b/archival/lzop.c new file mode 100644 index 000000000..a30d5e78b --- /dev/null +++ b/archival/lzop.c @@ -0,0 +1,1075 @@ +/* + This file is part of the lzop file compressor. + + Copyright (C) 1996..2003 Markus Franz Xaver Johannes Oberhumer + All Rights Reserved. + + Markus F.X.J. Oberhumer + http://www.oberhumer.com/opensource/lzop/ + + lzop and the LZO library are free software; you can redistribute them + and/or modify them under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of + the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; see the file COPYING. + If not, write to the Free Software Foundation, Inc., + 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + + "Minimalized" for busybox by Alain Knaff +*/ + +#include "libbb.h" +#include "unarchive.h" +#include "liblzo_interface.h" + +/* lzo-2.03/src/lzo_ptr.h */ +#define pd(a,b) ((unsigned)((a)-(b))) + +#define lzo_version() LZO_VERSION +#define lzo_sizeof_dict_t (sizeof(uint8_t*)) + +/* lzo-2.03/include/lzo/lzo1x.h */ +#define LZO1X_1_MEM_COMPRESS (16384 * lzo_sizeof_dict_t) +#define LZO1X_1_15_MEM_COMPRESS (32768 * lzo_sizeof_dict_t) +#define LZO1X_999_MEM_COMPRESS (14 * 16384 * sizeof(short)) + +/* lzo-2.03/src/lzo1x_oo.c */ +#define NO_LIT UINT_MAX + +/**********************************************************************/ +static void copy2(uint8_t* ip, const uint8_t* m_pos, unsigned off) +{ + ip[0] = m_pos[0]; + if (off == 1) + ip[1] = m_pos[0]; + else + ip[1] = m_pos[1]; +} + +static void copy3(uint8_t* ip, const uint8_t* m_pos, unsigned off) +{ + ip[0] = m_pos[0]; + if (off == 1) { + ip[2] = ip[1] = m_pos[0]; + } + else if (off == 2) { + ip[1] = m_pos[1]; + ip[2] = m_pos[0]; + } + else { + ip[1] = m_pos[1]; + ip[2] = m_pos[2]; + } +} + +/**********************************************************************/ +// optimize a block of data. +/**********************************************************************/ +#define TEST_IP (ip < ip_end) +#define TEST_OP (op <= op_end) + +static int lzo1x_optimize(uint8_t *in, unsigned in_len, + uint8_t *out, unsigned *out_len, + void* wrkmem UNUSED_PARAM) +{ + uint8_t* op; + uint8_t* ip; + unsigned t; + uint8_t* m_pos; + uint8_t* const ip_end = in + in_len; + uint8_t* const op_end = out + *out_len; + uint8_t* litp = NULL; + unsigned lit = 0; + unsigned next_lit = NO_LIT; + unsigned nl; + unsigned long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0; + +// LZO_UNUSED(wrkmem); + + *out_len = 0; + + op = out; + ip = in; + + if (*ip > 17) { + t = *ip++ - 17; + if (t < 4) + goto match_next; + goto first_literal_run; + } + + while (TEST_IP && TEST_OP) { + t = *ip++; + if (t >= 16) + goto match; + /* a literal run */ + litp = ip - 1; + if (t == 0) { + t = 15; + while (*ip == 0) + t += 255, ip++; + t += *ip++; + } + lit = t + 3; + /* copy literals */ + copy_literal_run: + *op++ = *ip++; + *op++ = *ip++; + *op++ = *ip++; + first_literal_run: + do *op++ = *ip++; while (--t > 0); + + t = *ip++; + + if (t >= 16) + goto match; +#if defined(LZO1X) + m_pos = op - 1 - 0x800; +#elif defined(LZO1Y) + m_pos = op - 1 - 0x400; +#endif + m_pos -= t >> 2; + m_pos -= *ip++ << 2; + *op++ = *m_pos++; + *op++ = *m_pos++; + *op++ = *m_pos++; + lit = 0; + goto match_done; + + + /* handle matches */ + do { + if (t < 16) { /* a M1 match */ + m_pos = op - 1; + m_pos -= t >> 2; + m_pos -= *ip++ << 2; + + if (litp == NULL) + goto copy_m1; + + nl = ip[-2] & 3; + /* test if a match follows */ + if (nl == 0 && lit == 1 && ip[0] >= 16) { + next_lit = nl; + /* adjust length of previous short run */ + lit += 2; + *litp = (unsigned char)((*litp & ~3) | lit); + /* copy over the 2 literals that replace the match */ + copy2(ip-2, m_pos, pd(op, m_pos)); + o_m1_a++; + } + /* test if a literal run follows */ + else if (nl == 0 && ip[0] < 16 && ip[0] != 0 && + (lit + 2 + ip[0] < 16)) + { + t = *ip++; + /* remove short run */ + *litp &= ~3; + /* copy over the 2 literals that replace the match */ + copy2(ip-3+1,m_pos,pd(op,m_pos)); + /* move literals 1 byte ahead */ + litp += 2; + if (lit > 0) + memmove(litp+1, litp, lit); + /* insert new length of long literal run */ + lit += 2 + t + 3; + *litp = (unsigned char)(lit - 3); + + o_m1_b++; + *op++ = *m_pos++; *op++ = *m_pos++; + goto copy_literal_run; + } + copy_m1: + *op++ = *m_pos++; + *op++ = *m_pos++; + } else { + match: + if (t >= 64) { /* a M2 match */ + m_pos = op - 1; +#if defined(LZO1X) + m_pos -= (t >> 2) & 7; + m_pos -= *ip++ << 3; + t = (t >> 5) - 1; +#elif defined(LZO1Y) + m_pos -= (t >> 2) & 3; + m_pos -= *ip++ << 2; + t = (t >> 4) - 3; +#endif + if (litp == NULL) + goto copy_m; + + nl = ip[-2] & 3; + /* test if in beetween two long literal runs */ + if (t == 1 && lit > 3 && nl == 0 + && ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16) + ) { + t = *ip++; + /* copy over the 3 literals that replace the match */ + copy3(ip-1-2,m_pos,pd(op,m_pos)); + /* set new length of previous literal run */ + lit += 3 + t + 3; + *litp = (unsigned char)(lit - 3); + o_m2++; + *op++ = *m_pos++; + *op++ = *m_pos++; + *op++ = *m_pos++; + goto copy_literal_run; + } + } else { + if (t >= 32) { /* a M3 match */ + t &= 31; + if (t == 0) { + t = 31; + while (*ip == 0) + t += 255, ip++; + t += *ip++; + } + m_pos = op - 1; + m_pos -= *ip++ >> 2; + m_pos -= *ip++ << 6; + } else { /* a M4 match */ + m_pos = op; + m_pos -= (t & 8) << 11; + t &= 7; + if (t == 0) { + t = 7; + while (*ip == 0) + t += 255, ip++; + t += *ip++; + } + m_pos -= *ip++ >> 2; + m_pos -= *ip++ << 6; + if (m_pos == op) + goto eof_found; + m_pos -= 0x4000; + } + if (litp == NULL) + goto copy_m; + + nl = ip[-2] & 3; + /* test if in beetween two matches */ + if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16) { + next_lit = nl; + /* make a previous short run */ + lit += 3; + *litp = (unsigned char)((*litp & ~3) | lit); + /* copy over the 3 literals that replace the match */ + copy3(ip-3,m_pos,pd(op,m_pos)); + o_m3_a++; + } + /* test if a literal run follows */ + else if (t == 1 && lit <= 3 && nl == 0 + && ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16) + ) { + t = *ip++; + /* remove short run */ + *litp &= ~3; + /* copy over the 3 literals that replace the match */ + copy3(ip-4+1,m_pos,pd(op,m_pos)); + /* move literals 1 byte ahead */ + litp += 2; + if (lit > 0) + memmove(litp+1,litp,lit); + /* insert new length of long literal run */ + lit += 3 + t + 3; + *litp = (unsigned char)(lit - 3); + + o_m3_b++; + *op++ = *m_pos++; + *op++ = *m_pos++; + *op++ = *m_pos++; + goto copy_literal_run; + } + } + copy_m: + *op++ = *m_pos++; + *op++ = *m_pos++; + do *op++ = *m_pos++; while (--t > 0); + } + + match_done: + if (next_lit == NO_LIT) { + t = ip[-2] & 3; + lit = t; + litp = ip - 2; + } + else + t = next_lit; + next_lit = NO_LIT; + if (t == 0) + break; + /* copy literals */ + match_next: + do *op++ = *ip++; while (--t > 0); + t = *ip++; + } while (TEST_IP && TEST_OP); + } + + /* no EOF code was found */ + *out_len = pd(op, out); + return LZO_E_EOF_NOT_FOUND; + + eof_found: +// LZO_UNUSED(o_m1_a); LZO_UNUSED(o_m1_b); LZO_UNUSED(o_m2); +// LZO_UNUSED(o_m3_a); LZO_UNUSED(o_m3_b); + *out_len = pd(op, out); + return (ip == ip_end ? LZO_E_OK : + (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); +} + +/**********************************************************************/ +#define F_OS F_OS_UNIX +#define F_CS F_CS_NATIVE + +/**********************************************************************/ +#define ADLER32_INIT_VALUE 1 +#define CRC32_INIT_VALUE 0 + +/**********************************************************************/ +enum { + M_LZO1X_1 = 1, + M_LZO1X_1_15 = 2, + M_LZO1X_999 = 3, +}; + +/**********************************************************************/ +/* header flags */ +#define F_ADLER32_D 0x00000001L +#define F_ADLER32_C 0x00000002L +#define F_H_EXTRA_FIELD 0x00000040L +#define F_H_GMTDIFF 0x00000080L +#define F_CRC32_D 0x00000100L +#define F_CRC32_C 0x00000200L +#define F_H_FILTER 0x00000800L +#define F_H_CRC32 0x00001000L +#define F_MASK 0x00003FFFL + +/* operating system & file system that created the file [mostly unused] */ +#define F_OS_UNIX 0x03000000L +#define F_OS_SHIFT 24 +#define F_OS_MASK 0xff000000L + +/* character set for file name encoding [mostly unused] */ +#define F_CS_NATIVE 0x00000000L +#define F_CS_SHIFT 20 +#define F_CS_MASK 0x00f00000L + +/* these bits must be zero */ +#define F_RESERVED ((F_MASK | F_OS_MASK | F_CS_MASK) ^ 0xffffffffL) + +typedef struct chksum_t { + uint32_t f_adler32; + uint32_t f_crc32; +} chksum_t; + +typedef struct header_t { + unsigned version; + unsigned lib_version; + unsigned version_needed_to_extract; + uint32_t flags; + uint32_t mode; + uint32_t mtime; + uint32_t gmtdiff; + uint32_t header_checksum; + + uint32_t extra_field_len; + uint32_t extra_field_checksum; + + unsigned char method; + unsigned char level; + + /* info */ + char name[255+1]; +} header_t; + +struct globals { + const uint32_t *lzo_crc32_table; + chksum_t chksum_in; + chksum_t chksum_out; +}; +#define G (*(struct globals*)&bb_common_bufsiz1) +#define INIT_G() do { } while (0) +//#define G (*ptr_to_globals) +//#define INIT_G() do { +// SET_PTR_TO_GLOBALS(xzalloc(sizeof(G))); +//} while (0) + + +/**********************************************************************/ +#define LZOP_VERSION 0x1010 +//#define LZOP_VERSION_STRING "1.01" +//#define LZOP_VERSION_DATE "Apr 27th 2003" + +#define OPTION_STRING "cfvdt123456789CF" + +enum { + OPT_STDOUT = (1 << 0), + OPT_FORCE = (1 << 1), + OPT_VERBOSE = (1 << 2), + OPT_DECOMPRESS = (1 << 3), + OPT_TEST = (1 << 4), + OPT_1 = (1 << 5), + OPT_2 = (1 << 6), + OPT_3 = (1 << 7), + OPT_4 = (1 << 8), + OPT_5 = (1 << 9), + OPT_6 = (1 << 10), + OPT_789 = (7 << 11), + OPT_7 = (1 << 11), + OPT_8 = (1 << 12), + OPT_C = (1 << 14), + OPT_F = (1 << 15), +}; + +/**********************************************************************/ +// adler32 checksum +// adapted from free code by Mark Adler +// see http://www.zlib.org/ +/**********************************************************************/ +static FAST_FUNC uint32_t +lzo_adler32(uint32_t adler, const uint8_t* buf, unsigned len) +{ + enum { + LZO_BASE = 65521, /* largest prime smaller than 65536 */ + /* NMAX is the largest n such that + * 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ + LZO_NMAX = 5552, + }; + uint32_t s1 = adler & 0xffff; + uint32_t s2 = (adler >> 16) & 0xffff; + unsigned k; + + if (buf == NULL) + return 1; + + while (len > 0) { + k = len < LZO_NMAX ? (unsigned) len : LZO_NMAX; + len -= k; + if (k != 0) do { + s1 += *buf++; + s2 += s1; + } while (--k > 0); + s1 %= LZO_BASE; + s2 %= LZO_BASE; + } + return (s2 << 16) | s1; +} + +static FAST_FUNC uint32_t +lzo_crc32(uint32_t c, const uint8_t* buf, unsigned len) +{ + uint32_t crc; + + if (buf == NULL) + return 0; + + crc = ~c; + if (len != 0) do { + crc = G.lzo_crc32_table[((int)crc ^ *buf) & 0xff] ^ (crc >> 8); + buf += 1; + len -= 1; + } while (len > 0); + + return ~crc; +} + +/**********************************************************************/ +static void init_chksum(chksum_t *ct) +{ + ct->f_adler32 = ADLER32_INIT_VALUE; + ct->f_crc32 = CRC32_INIT_VALUE; +} + +static void add_bytes_to_chksum(chksum_t *ct, const void* buf, int cnt) +{ + /* We need to handle the two checksums at once, because at the + * beginning of the header, we don't know yet which one we'll + * eventually need */ + ct->f_adler32 = lzo_adler32(ct->f_adler32, (const uint8_t*)buf, cnt); + ct->f_crc32 = lzo_crc32(ct->f_crc32, (const uint8_t*)buf, cnt); +} + +static uint32_t chksum_getresult(chksum_t *ct, const header_t *h) +{ + return (h->flags & F_H_CRC32) ? ct->f_crc32 : ct->f_adler32; +} + +/**********************************************************************/ +static uint32_t read32(void) +{ + uint32_t v; + xread(0, &v, 4); + return ntohl(v); +} + +static void write32(uint32_t v) +{ + v = htonl(v); + xwrite(1, &v, 4); +} + +static void f_write(const void* buf, int cnt) +{ + xwrite(1, buf, cnt); + add_bytes_to_chksum(&G.chksum_out, buf, cnt); +} + +static void f_read(void* buf, int cnt) +{ + xread(0, buf, cnt); + add_bytes_to_chksum(&G.chksum_in, buf, cnt); +} + +static int f_read8(void) +{ + uint8_t v; + f_read(&v, 1); + return v; +} + +static void f_write8(uint8_t v) +{ + f_write(&v, 1); +} + +static unsigned f_read16(void) +{ + uint16_t v; + f_read(&v, 2); + return ntohs(v); +} + +static void f_write16(uint16_t v) +{ + v = htons(v); + f_write(&v, 2); +} + +static uint32_t f_read32(void) +{ + uint32_t v; + f_read(&v, 4); + return ntohl(v); +} + +static void f_write32(uint32_t v) +{ + v = htonl(v); + f_write(&v, 4); +} + +/**********************************************************************/ +static int lzo_get_method(header_t *h) +{ + /* check method */ + if (h->method == M_LZO1X_1) { + if (h->level == 0) + h->level = 3; + } else if (h->method == M_LZO1X_1_15) { + if (h->level == 0) + h->level = 1; + } else if (h->method == M_LZO1X_999) { + if (h->level == 0) + h->level = 9; + } else + return -1; /* not a LZO method */ + + /* check compression level */ + if (h->level < 1 || h->level > 9) + return 15; + + return 0; +} + +/**********************************************************************/ +#define LZO_BLOCK_SIZE (256 * 1024l) +#define MAX_BLOCK_SIZE (64 * 1024l * 1024l) /* DO NOT CHANGE */ + +/* LZO may expand uncompressible data by a small amount */ +#define MAX_COMPRESSED_SIZE(x) ((x) + (x) / 16 + 64 + 3) + +/**********************************************************************/ +// compress a file +/**********************************************************************/ +static smallint lzo_compress(const header_t *h) +{ + unsigned block_size = LZO_BLOCK_SIZE; + int r = 0; /* LZO_E_OK */ + uint8_t *const b1 = xzalloc(block_size); + uint8_t *const b2 = xzalloc(MAX_COMPRESSED_SIZE(block_size)); + unsigned src_len = 0, dst_len = 0; + uint32_t d_adler32 = ADLER32_INIT_VALUE; + uint32_t d_crc32 = CRC32_INIT_VALUE; + int l; + smallint ok = 1; + uint8_t *wrk_mem = NULL; + + if (h->method == M_LZO1X_1) + wrk_mem = xzalloc(LZO1X_1_MEM_COMPRESS); + else if (h->method == M_LZO1X_1_15) + wrk_mem = xzalloc(LZO1X_1_15_MEM_COMPRESS); + else if (h->method == M_LZO1X_999) + wrk_mem = xzalloc(LZO1X_999_MEM_COMPRESS); + + for (;;) { + /* read a block */ + l = full_read(0, b1, block_size); + src_len = (l > 0 ? l : 0); + + /* write uncompressed block size */ + write32(src_len); + + /* exit if last block */ + if (src_len == 0) + break; + + /* compute checksum of uncompressed block */ + if (h->flags & F_ADLER32_D) + d_adler32 = lzo_adler32(ADLER32_INIT_VALUE, b1, src_len); + if (h->flags & F_CRC32_D) + d_crc32 = lzo_crc32(CRC32_INIT_VALUE, b1, src_len); + + /* compress */ + if (h->method == M_LZO1X_1) + r = lzo1x_1_compress(b1, src_len, b2, &dst_len, wrk_mem); + else if (h->method == M_LZO1X_1_15) + r = lzo1x_1_15_compress(b1, src_len, b2, &dst_len, wrk_mem); +#if ENABLE_LZOP_COMPR_HIGH + else if (h->method == M_LZO1X_999) + r = lzo1x_999_compress_level(b1, src_len, b2, &dst_len, + wrk_mem, h->level); +#endif + else + bb_error_msg_and_die("internal error"); + + if (r != 0) /* not LZO_E_OK */ + bb_error_msg_and_die("internal error - compression failed"); + + /* write compressed block size */ + if (dst_len < src_len) { + /* optimize */ + if (h->method == M_LZO1X_999) { + unsigned new_len = src_len; + r = lzo1x_optimize(b2, dst_len, b1, &new_len, NULL); + if (r != 0 /*LZO_E_OK*/ || new_len != src_len) + bb_error_msg_and_die("internal error - optimization failed"); + } + write32(dst_len); + } else { + /* data actually expanded => store data uncompressed */ + write32(src_len); + } + + /* write checksum of uncompressed block */ + if (h->flags & F_ADLER32_D) + write32(d_adler32); + if (h->flags & F_CRC32_D) + write32(d_crc32); + + if (dst_len < src_len) { + /* write checksum of compressed block */ + if (h->flags & F_ADLER32_C) + write32(lzo_adler32(ADLER32_INIT_VALUE, b2, + dst_len)); + if (h->flags & F_CRC32_C) + write32(lzo_crc32(CRC32_INIT_VALUE, b2, dst_len)); + /* write compressed block data */ + xwrite(1, b2, dst_len); + } else { + /* write uncompressed block data */ + xwrite(1, b1, src_len); + } + } + + free(wrk_mem); + free(b1); + free(b2); + return ok; +} + +static void lzo_check(uint32_t FAST_FUNC (*fn)(uint32_t, const uint8_t*, unsigned), + uint32_t ref, uint32_t init, + uint8_t* buf, unsigned len) +{ + uint32_t c = fn(init, buf, len); + if (c != ref) + bb_error_msg_and_die("checksum error"); +} + +/**********************************************************************/ +// decompress a file +/**********************************************************************/ +static smallint lzo_decompress(const header_t *h) +{ + unsigned block_size = LZO_BLOCK_SIZE; + int r; + uint32_t src_len, dst_len; + uint32_t c_adler32 = ADLER32_INIT_VALUE; + uint32_t d_adler32 = ADLER32_INIT_VALUE; + uint32_t c_crc32 = CRC32_INIT_VALUE, d_crc32 = CRC32_INIT_VALUE; + smallint ok = 1; + uint8_t *b1; + uint32_t mcs_block_size = MAX_COMPRESSED_SIZE(block_size); + uint8_t *b2 = NULL; + + for (;;) { + uint8_t *dst; + + /* read uncompressed block size */ + dst_len = read32(); + + /* exit if last block */ + if (dst_len == 0) + break; + + /* error if split file */ + if (dst_len == 0xffffffffL) + /* should not happen - not yet implemented */ + bb_error_msg_and_die("this file is a split lzop file"); + + if (dst_len > MAX_BLOCK_SIZE) + bb_error_msg_and_die("lzop file corrupted"); + + /* read compressed block size */ + src_len = read32(); + if (src_len <= 0 || src_len > dst_len) + bb_error_msg_and_die("lzop file corrupted"); + + if (dst_len > block_size) { + if (b2) { +//FIXME! + b2 = NULL; + free(b2); + } + block_size = dst_len; + mcs_block_size = MAX_COMPRESSED_SIZE(block_size); + } + + /* read checksum of uncompressed block */ + if (h->flags & F_ADLER32_D) + d_adler32 = read32(); + if (h->flags & F_CRC32_D) + d_crc32 = read32(); + + /* read checksum of compressed block */ + if (src_len < dst_len) { + if (h->flags & F_ADLER32_C) + c_adler32 = read32(); + if (h->flags & F_CRC32_C) + c_crc32 = read32(); + } + + if (b2 == NULL) + b2 = xzalloc(mcs_block_size); + /* read the block into the end of our buffer */ + b1 = b2 + mcs_block_size - src_len; + xread(0, b1, src_len); + + if (src_len < dst_len) { + unsigned d = dst_len; + + if (!(option_mask32 & OPT_F)) { + /* verify checksum of compressed block */ + if (h->flags & F_ADLER32_C) + lzo_check(lzo_adler32, c_adler32, + ADLER32_INIT_VALUE, + b1, src_len); + if (h->flags & F_CRC32_C) + lzo_check(lzo_crc32, c_crc32, + CRC32_INIT_VALUE, + b1, src_len); + } + + /* decompress */ +// if (option_mask32 & OPT_F) +// r = lzo1x_decompress(b1, src_len, b2, &d, NULL); +// else + r = lzo1x_decompress_safe(b1, src_len, b2, &d, NULL); + + if (r != 0 /*LZO_E_OK*/ || dst_len != d) { + bb_error_msg_and_die("corrupted compressed data"); + } + dst = b2; + } else { + /* "stored" block => no decompression */ + dst = b1; + } + + if (!(option_mask32 & OPT_F)) { + /* verify checksum of uncompressed block */ + if (h->flags & F_ADLER32_D) + lzo_check(lzo_adler32, d_adler32, ADLER32_INIT_VALUE, + dst, dst_len); + if (h->flags & F_CRC32_D) + lzo_check(lzo_crc32, d_crc32, CRC32_INIT_VALUE, + dst, dst_len); + } + + /* write uncompressed block data */ + xwrite(1, dst, dst_len); + } + + free(b2); + return ok; +} + +/**********************************************************************/ +// lzop file signature (shamelessly borrowed from PNG) +/**********************************************************************/ +/* + * The first nine bytes of a lzop file always contain the following values: + * + * 0 1 2 3 4 5 6 7 8 + * --- --- --- --- --- --- --- --- --- + * (hex) 89 4c 5a 4f 00 0d 0a 1a 0a + * (decimal) 137 76 90 79 0 13 10 26 10 + * (C notation - ASCII) \211 L Z O \0 \r \n \032 \n + */ + +/* (vda) comparison with lzop v1.02rc1 ("lzop -1 version); + f_write16(h->lib_version); + f_write16(h->version_needed_to_extract); + f_write8(h->method); + f_write8(h->level); + f_write32(h->flags); + f_write32(h->mode); + f_write32(h->mtime); + f_write32(h->gmtdiff); + + l = (int) strlen(h->name); + f_write8(l); + if (l) + f_write(h->name, l); + + f_write32(chksum_getresult(&G.chksum_out, h)); +} + +static int read_header(header_t *h) +{ + int r; + int l; + uint32_t checksum; + + memset(h, 0, sizeof(*h)); + h->version_needed_to_extract = 0x0900; /* first lzop version */ + h->level = 0; + + init_chksum(&G.chksum_in); + + h->version = f_read16(); + if (h->version < 0x0900) + return 3; + h->lib_version = f_read16(); + if (h->version >= 0x0940) { + h->version_needed_to_extract = f_read16(); + if (h->version_needed_to_extract > LZOP_VERSION) + return 16; + if (h->version_needed_to_extract < 0x0900) + return 3; + } + h->method = f_read8(); + if (h->version >= 0x0940) + h->level = f_read8(); + h->flags = f_read32(); + if (h->flags & F_H_FILTER) + return 16; /* filter not supported */ + h->mode = f_read32(); + h->mtime = f_read32(); + if (h->version >= 0x0940) + h->gmtdiff = f_read32(); + + l = f_read8(); + if (l > 0) + f_read(h->name, l); + h->name[l] = 0; + + checksum = chksum_getresult(&G.chksum_in, h); + h->header_checksum = f_read32(); + if (h->header_checksum != checksum) + return 2; + + if (h->method <= 0) + return 14; + r = lzo_get_method(h); + if (r != 0) + return r; + + /* check reserved flags */ + if (h->flags & F_RESERVED) + return -13; + + /* skip extra field [not used yet] */ + if (h->flags & F_H_EXTRA_FIELD) { + uint32_t k; + + /* note: the checksum also covers the length */ + init_chksum(&G.chksum_in); + h->extra_field_len = f_read32(); + for (k = 0; k < h->extra_field_len; k++) + f_read8(); + checksum = chksum_getresult(&G.chksum_in, h); + h->extra_field_checksum = f_read32(); + if (h->extra_field_checksum != checksum) + return 3; + } + + return 0; +} + +static void p_header(header_t *h) +{ + int r; + + r = read_header(h); + if (r == 0) + return; + bb_error_msg_and_die("header_error %d", r); +} + +/**********************************************************************/ +// compress +/**********************************************************************/ +static void lzo_set_method(header_t *h) +{ + int level = 1; + + if (option_mask32 & OPT_1) { + h->method = M_LZO1X_1_15; + } else if (option_mask32 & OPT_789) { +#if ENABLE_LZOP_COMPR_HIGH + h->method = M_LZO1X_999; + if (option_mask32 & OPT_7) + level = 7; + else if (option_mask32 & OPT_8) + level = 8; + else + level = 9; +#else + bb_error_msg_and_die("high compression not compiled in"); +#endif + } else { /* levels 2..6 or none (defaults to level 3) */ + h->method = M_LZO1X_1; + level = 5; /* levels 2-6 are actually the same */ + } + + h->level = level; +} + +static smallint do_lzo_compress(void) +{ + header_t header; + +#define h (&header) + memset(h, 0, sizeof(*h)); + + lzo_set_method(h); + + h->version = (LZOP_VERSION & 0xffff); + h->version_needed_to_extract = 0x0940; + h->lib_version = lzo_version() & 0xffff; + + h->flags = (F_OS & F_OS_MASK) | (F_CS & F_CS_MASK); + + if (!(option_mask32 & OPT_F) || h->method == M_LZO1X_999) { + h->flags |= F_ADLER32_D; + if (option_mask32 & OPT_C) + h->flags |= F_ADLER32_C; + } + write_header(h); + return lzo_compress(h); +#undef h +} + +/**********************************************************************/ +// decompress +/**********************************************************************/ +static smallint do_lzo_decompress(void) +{ + header_t header; + + check_magic(); + p_header(&header); + return lzo_decompress(&header); +} + +static char* make_new_name_lzop(char *filename) +{ + if (option_mask32 & OPT_DECOMPRESS) { + char *extension = strrchr(filename, '.'); + if (!extension || strcmp(extension + 1, "lzo") != 0) + return xasprintf("%s.out", filename); + *extension = '\0'; + return filename; + } + return xasprintf("%s.lzo", filename); +} + +static IF_DESKTOP(long long) int pack_lzop(unpack_info_t *info UNUSED_PARAM) +{ + if (option_mask32 & OPT_DECOMPRESS) + return do_lzo_decompress(); + return do_lzo_compress(); +} + +int lzop_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE; +int lzop_main(int argc UNUSED_PARAM, char **argv) +{ + getopt32(argv, OPTION_STRING); + argv += optind; + /* lzopcat? */ + if (applet_name[4] == 'c') + option_mask32 |= (OPT_STDOUT | OPT_DECOMPRESS); + /* unlzop? */ + if (applet_name[0] == 'u') + option_mask32 |= OPT_DECOMPRESS; + + G.lzo_crc32_table = crc32_filltable(NULL, 0); + return bbunpack(argv, make_new_name_lzop, pack_lzop); +} diff --git a/include/applets.h b/include/applets.h index a41f75e31..359440def 100644 --- a/include/applets.h +++ b/include/applets.h @@ -242,6 +242,8 @@ IF_LSATTR(APPLET(lsattr, _BB_DIR_BIN, _BB_SUID_NEVER)) IF_LSMOD(APPLET(lsmod, _BB_DIR_SBIN, _BB_SUID_NEVER)) IF_MODPROBE_SMALL(APPLET_ODDNAME(lsmod, modprobe, _BB_DIR_SBIN, _BB_SUID_NEVER, modprobe)) IF_UNLZMA(APPLET_ODDNAME(lzmacat, unlzma, _BB_DIR_USR_BIN, _BB_SUID_NEVER, lzmacat)) +IF_LZOP(APPLET(lzop, _BB_DIR_BIN, _BB_SUID_NEVER)) +IF_LZOP(APPLET_ODDNAME(lzopcat, lzop, _BB_DIR_USR_BIN, _BB_SUID_NEVER, lzopcat)) IF_MAKEDEVS(APPLET(makedevs, _BB_DIR_SBIN, _BB_SUID_NEVER)) IF_MAKEMIME(APPLET(makemime, _BB_DIR_BIN, _BB_SUID_NEVER)) IF_MAN(APPLET(man, _BB_DIR_SBIN, _BB_SUID_NEVER)) @@ -401,6 +403,7 @@ IF_UNEXPAND(APPLET_ODDNAME(unexpand, expand, _BB_DIR_USR_BIN, _BB_SUID_NEVER, un IF_UNIQ(APPLET(uniq, _BB_DIR_USR_BIN, _BB_SUID_NEVER)) IF_UNIX2DOS(APPLET_ODDNAME(unix2dos, dos2unix, _BB_DIR_USR_BIN, _BB_SUID_NEVER, unix2dos)) IF_UNLZMA(APPLET(unlzma, _BB_DIR_USR_BIN, _BB_SUID_NEVER)) +IF_LZOP(APPLET_ODDNAME(unlzop, lzop, _BB_DIR_USR_BIN, _BB_SUID_NEVER, unlzop)) IF_UNZIP(APPLET(unzip, _BB_DIR_USR_BIN, _BB_SUID_NEVER)) IF_UPTIME(APPLET(uptime, _BB_DIR_USR_BIN, _BB_SUID_NEVER)) IF_USLEEP(APPLET_NOFORK(usleep, usleep, _BB_DIR_BIN, _BB_SUID_NEVER, usleep)) diff --git a/include/usage.h b/include/usage.h index 3fb996126..123462a02 100644 --- a/include/usage.h +++ b/include/usage.h @@ -202,6 +202,31 @@ #define busybox_notes_usage \ "Hello world!\n" +#define lzop_trivial_usage \ + "[-cfvd123456789CF] [file..]" +#define lzop_full_usage "\n\n" \ + " -c Write to standard output" \ + "\n -f Force" \ + "\n -v Verbose" \ + "\n -d Decompress" \ + "\n -F Don't store or verify checksum" \ + "\n -C Also write checksum of compressed block" \ + "\n -1..9 Compression level" \ + +#define lzopcat_trivial_usage \ + "[-vCF] [file..]" +#define lzopcat_full_usage "\n\n" \ + " -v Verbose" \ + "\n -F Don't store or verify checksum" \ + +#define unlzop_trivial_usage \ + "[-cfvCF] [file..]" +#define unlzop_full_usage "\n\n" \ + " -c Write to standard output" \ + "\n -f Force" \ + "\n -v Verbose" \ + "\n -F Don't store or verify checksum" \ + #define bzcat_trivial_usage \ "FILE" #define bzcat_full_usage "\n\n" \ -- cgit v1.2.3