From 5e9934028aa030312a1a2e2e32d5ceade8672beb Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Wed, 3 Nov 2010 02:27:49 +0100 Subject: *: move lzo compressor code to archival/libunarchive/. No code changes Signed-off-by: Denys Vlasenko --- archival/Kbuild.src | 3 +- archival/liblzo.h | 93 ---- archival/liblzo_interface.h | 71 --- archival/libunarchive/Kbuild.src | 2 + archival/libunarchive/liblzo.h | 93 ++++ archival/libunarchive/lzo1x_1.c | 35 ++ archival/libunarchive/lzo1x_1o.c | 35 ++ archival/libunarchive/lzo1x_9x.c | 921 +++++++++++++++++++++++++++++++++++++++ archival/libunarchive/lzo1x_c.c | 296 +++++++++++++ archival/libunarchive/lzo1x_d.c | 420 ++++++++++++++++++ archival/lzo1x_1.c | 35 -- archival/lzo1x_1o.c | 35 -- archival/lzo1x_9x.c | 921 --------------------------------------- archival/lzo1x_c.c | 296 ------------- archival/lzo1x_d.c | 420 ------------------ 15 files changed, 1803 insertions(+), 1873 deletions(-) delete mode 100644 archival/liblzo.h delete mode 100644 archival/liblzo_interface.h create mode 100644 archival/libunarchive/liblzo.h create mode 100644 archival/libunarchive/lzo1x_1.c create mode 100644 archival/libunarchive/lzo1x_1o.c create mode 100644 archival/libunarchive/lzo1x_9x.c create mode 100644 archival/libunarchive/lzo1x_c.c create mode 100644 archival/libunarchive/lzo1x_d.c delete mode 100644 archival/lzo1x_1.c delete mode 100644 archival/lzo1x_1o.c delete mode 100644 archival/lzo1x_9x.c delete mode 100644 archival/lzo1x_c.c delete mode 100644 archival/lzo1x_d.c (limited to 'archival') diff --git a/archival/Kbuild.src b/archival/Kbuild.src index a0edb123d..e49d38538 100644 --- a/archival/Kbuild.src +++ b/archival/Kbuild.src @@ -19,8 +19,7 @@ lib-$(CONFIG_RPM) += rpm.o lib-$(CONFIG_TAR) += tar.o lib-$(CONFIG_UNZIP) += unzip.o -lib-$(CONFIG_LZOP) += lzop.o lzo1x_1.o lzo1x_1o.o lzo1x_d.o bbunzip.o -lib-$(CONFIG_LZOP_COMPR_HIGH) += lzo1x_9x.o +lib-$(CONFIG_LZOP) += lzop.o bbunzip.o lib-$(CONFIG_GZIP) += gzip.o bbunzip.o lib-$(CONFIG_BZIP2) += bzip2.o bbunzip.o diff --git a/archival/liblzo.h b/archival/liblzo.h deleted file mode 100644 index 843997cb9..000000000 --- a/archival/liblzo.h +++ /dev/null @@ -1,93 +0,0 @@ -/* - 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 deleted file mode 100644 index 9a84c0b6b..000000000 --- a/archival/liblzo_interface.h +++ /dev/null @@ -1,71 +0,0 @@ -/* - 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/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 lib-$(CONFIG_TAR) += get_header_tar.o lib-$(CONFIG_UNCOMPRESS) += decompress_uncompress.o lib-$(CONFIG_UNZIP) += decompress_unzip.o +lib-$(CONFIG_LZOP) += lzo1x_1.o lzo1x_1o.o lzo1x_d.o +lib-$(CONFIG_LZOP_COMPR_HIGH) += lzo1x_9x.o lib-$(CONFIG_FEATURE_SEAMLESS_Z) += open_transformer.o decompress_uncompress.o lib-$(CONFIG_FEATURE_SEAMLESS_GZ) += open_transformer.o decompress_unzip.o get_header_tar_gz.o lib-$(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 @@ +/* + 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/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 @@ +/* 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/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 @@ +/* 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/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 @@ +/* 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; + const lzo_swd_p 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/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 @@ +/* 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/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 @@ +/* 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/lzo1x_1.c b/archival/lzo1x_1.c deleted file mode 100644 index a88839846..000000000 --- a/archival/lzo1x_1.c +++ /dev/null @@ -1,35 +0,0 @@ -/* 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 deleted file mode 100644 index 3c61253e0..000000000 --- a/archival/lzo1x_1o.c +++ /dev/null @@ -1,35 +0,0 @@ -/* 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 deleted file mode 100644 index 483205155..000000000 --- a/archival/lzo1x_9x.c +++ /dev/null @@ -1,921 +0,0 @@ -/* 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; - const lzo_swd_p 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 deleted file mode 100644 index cc86f74b1..000000000 --- a/archival/lzo1x_c.c +++ /dev/null @@ -1,296 +0,0 @@ -/* 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 deleted file mode 100644 index 348a85510..000000000 --- a/archival/lzo1x_d.c +++ /dev/null @@ -1,420 +0,0 @@ -/* 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 -} -- cgit v1.2.3