minilzo.c

lzo-1.08-src.zip 高效的压缩解压代码

	k += __lzo_align_gap(&x[k],n);
	p0 = (lzo_bytep) &x[k];
#if defined(PTR_LINEAR)
	r &= __lzo_assert((PTR_LINEAR(p0) & (n-1)) == 0);
#else
	r &= __lzo_assert(n == 4);
	r &= __lzo_assert(PTR_ALIGNED_4(p0));
#endif

	r &= __lzo_assert(k >= 1);
	p1 = (lzo_bytep) &x[1];
	r &= __lzo_assert(PTR_GE(p0,p1));

	r &= __lzo_assert(k < 1+n);
	p1 = (lzo_bytep) &x[1+n];
	r &= __lzo_assert(PTR_LT(p0,p1));

	if (r == 1)
	{
	    lzo_uint32 v0, v1;
#if 0
	    v0 = * (lzo_uint32 *) &x[k];
	    v1 = * (lzo_uint32 *) &x[k+n];
#else

	    u.a_uchar_p = &x[k];
	    v0 = *u.a_lzo_uint32_p;
	    u.a_uchar_p = &x[k+n];
	    v1 = *u.a_lzo_uint32_p;
#endif
	    r &= __lzo_assert(v0 > 0);
	    r &= __lzo_assert(v1 > 0);
	}
    }

    return r;
}

LZO_PUBLIC(int)
_lzo_config_check(void)
{
    lzo_bool r = 1;
    int i;
    union {
	lzo_uint32 a;
	unsigned short b;
	lzo_uint32 aa[4];
	unsigned char x[4*sizeof(lzo_full_align_t)];
    } u;

    COMPILE_TIME_ASSERT( (int) ((unsigned char) ((signed char) -1)) == 255);
    COMPILE_TIME_ASSERT( (((unsigned char)128) << (int)(8*sizeof(int)-8)) < 0);

#if 0
    r &= __lzo_assert((const void *)&u == (const void *)&u.a);
    r &= __lzo_assert((const void *)&u == (const void *)&u.b);
    r &= __lzo_assert((const void *)&u == (const void *)&u.x[0]);
    r &= __lzo_assert((const void *)&u == (const void *)&u.aa[0]);
#endif

    r &= basic_integral_check();
    r &= basic_ptr_check();
    if (r != 1)
	return LZO_E_ERROR;

    u.a = 0; u.b = 0;
    for (i = 0; i < (int) sizeof(u.x); i++)
	u.x[i] = LZO_BYTE(i);

#if defined(LZO_BYTE_ORDER)
    if (r == 1)
    {
#  if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
	lzo_uint32 a = (lzo_uint32) (u.a & LZO_0xffffffffL);
	unsigned short b = (unsigned short) (u.b & 0xffff);
	r &= __lzo_assert(a == 0x03020100L);
	r &= __lzo_assert(b == 0x0100);
#  elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
	lzo_uint32 a = u.a >> (8 * sizeof(u.a) - 32);
	unsigned short b = u.b >> (8 * sizeof(u.b) - 16);
	r &= __lzo_assert(a == 0x00010203L);
	r &= __lzo_assert(b == 0x0001);
#  else
#    error "invalid LZO_BYTE_ORDER"
#  endif
    }
#endif

#if defined(LZO_UNALIGNED_OK_2)
    COMPILE_TIME_ASSERT(sizeof(short) == 2);
    if (r == 1)
    {
	unsigned short b[4];

	for (i = 0; i < 4; i++)
	    b[i] = * (const unsigned short *) &u.x[i];

#  if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
	r &= __lzo_assert(b[0] == 0x0100);
	r &= __lzo_assert(b[1] == 0x0201);
	r &= __lzo_assert(b[2] == 0x0302);
	r &= __lzo_assert(b[3] == 0x0403);
#  elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
	r &= __lzo_assert(b[0] == 0x0001);
	r &= __lzo_assert(b[1] == 0x0102);
	r &= __lzo_assert(b[2] == 0x0203);
	r &= __lzo_assert(b[3] == 0x0304);
#  endif
    }
#endif

#if defined(LZO_UNALIGNED_OK_4)
    COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == 4);
    if (r == 1)
    {
	lzo_uint32 a[4];

	for (i = 0; i < 4; i++)
	    a[i] = * (const lzo_uint32 *) &u.x[i];

#  if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
	r &= __lzo_assert(a[0] == 0x03020100L);
	r &= __lzo_assert(a[1] == 0x04030201L);
	r &= __lzo_assert(a[2] == 0x05040302L);
	r &= __lzo_assert(a[3] == 0x06050403L);
#  elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
	r &= __lzo_assert(a[0] == 0x00010203L);
	r &= __lzo_assert(a[1] == 0x01020304L);
	r &= __lzo_assert(a[2] == 0x02030405L);
	r &= __lzo_assert(a[3] == 0x03040506L);
#  endif
    }
#endif

#if defined(LZO_ALIGNED_OK_4)
    COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == 4);
#endif

    COMPILE_TIME_ASSERT(lzo_sizeof_dict_t == sizeof(lzo_dict_t));

#if defined(__LZO_IN_MINLZO)
    if (r == 1)
    {
	lzo_uint32 adler;
	adler = lzo_adler32(0, NULL, 0);
	adler = lzo_adler32(adler, lzo_copyright(), 200);
	r &= __lzo_assert(adler == 0xc76f1751L);
    }
#endif

    if (r == 1)
    {
	r &= __lzo_assert(!schedule_insns_bug());
    }

    if (r == 1)
    {
	static int x[3];
	static unsigned xn = 3;
	register unsigned j;

	for (j = 0; j < xn; j++)
	    x[j] = (int)j - 3;
	r &= __lzo_assert(!strength_reduce_bug(x));
    }

    if (r == 1)
    {
	r &= ptr_check();
    }

    return r == 1 ? LZO_E_OK : LZO_E_ERROR;
}

static lzo_bool schedule_insns_bug(void)
{
#if defined(__LZO_CHECKER)
    return 0;
#else
    const int clone[] = {1, 2, 0};
    const int *q;
    q = clone;
    return (*q) ? 0 : 1;
#endif
}

static lzo_bool strength_reduce_bug(int *x)
{
    return x[0] != -3 || x[1] != -2 || x[2] != -1;
}

#undef COMPILE_TIME_ASSERT

int __lzo_init_done = 0;

LZO_PUBLIC(int)
__lzo_init2(unsigned v, int s1, int s2, int s3, int s4, int s5,
			int s6, int s7, int s8, int s9)
{
    int r;

    __lzo_init_done = 1;

    if (v == 0)
	return LZO_E_ERROR;

    r = (s1 == -1 || s1 == (int) sizeof(short)) &&
	(s2 == -1 || s2 == (int) sizeof(int)) &&
	(s3 == -1 || s3 == (int) sizeof(long)) &&
	(s4 == -1 || s4 == (int) sizeof(lzo_uint32)) &&
	(s5 == -1 || s5 == (int) sizeof(lzo_uint)) &&
	(s6 == -1 || s6 == (int) lzo_sizeof_dict_t) &&
	(s7 == -1 || s7 == (int) sizeof(char *)) &&
	(s8 == -1 || s8 == (int) sizeof(lzo_voidp)) &&
	(s9 == -1 || s9 == (int) sizeof(lzo_compress_t));
    if (!r)
	return LZO_E_ERROR;

    r = _lzo_config_check();
    if (r != LZO_E_OK)
	return r;

    return r;
}

#if !defined(__LZO_IN_MINILZO)

LZO_EXTERN(int)
__lzo_init(unsigned v,int s1,int s2,int s3,int s4,int s5,int s6,int s7);

LZO_PUBLIC(int)
__lzo_init(unsigned v,int s1,int s2,int s3,int s4,int s5,int s6,int s7)
{
    if (v == 0 || v > 0x1010)
	return LZO_E_ERROR;
    return __lzo_init2(v,s1,s2,s3,s4,s5,-1,-1,s6,s7);
}

#endif

#define do_compress         _lzo1x_1_do_compress

#define LZO_NEED_DICT_H
#define D_BITS          14
#define D_INDEX1(d,p)       d = DM((0x21*DX3(p,5,5,6)) >> 5)
#define D_INDEX2(d,p)       d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)

#ifndef __LZO_CONFIG1X_H
#define __LZO_CONFIG1X_H

#if !defined(LZO1X) && !defined(LZO1Y) && !defined(LZO1Z)
#  define LZO1X
#endif

#if !defined(__LZO_IN_MINILZO)
#include <lzo1x.h>
#endif

#define LZO_EOF_CODE
#undef LZO_DETERMINISTIC

#define M1_MAX_OFFSET   0x0400
#ifndef M2_MAX_OFFSET
#define M2_MAX_OFFSET   0x0800
#endif
#define M3_MAX_OFFSET   0x4000
#define M4_MAX_OFFSET   0xbfff

#define MX_MAX_OFFSET   (M1_MAX_OFFSET + M2_MAX_OFFSET)

#define M1_MIN_LEN      2
#define M1_MAX_LEN      2
#define M2_MIN_LEN      3
#ifndef M2_MAX_LEN
#define M2_MAX_LEN      8
#endif
#define M3_MIN_LEN      3
#define M3_MAX_LEN      33
#define M4_MIN_LEN      3
#define M4_MAX_LEN      9

#define M1_MARKER       0
#define M2_MARKER       64
#define M3_MARKER       32
#define M4_MARKER       16

#ifndef MIN_LOOKAHEAD
#define MIN_LOOKAHEAD       (M2_MAX_LEN + 1)
#endif

#if defined(LZO_NEED_DICT_H)

#ifndef LZO_HASH
#define LZO_HASH            LZO_HASH_LZO_INCREMENTAL_B
#endif
#define DL_MIN_LEN          M2_MIN_LEN

#ifndef __LZO_DICT_H
#define __LZO_DICT_H

#ifdef __cplusplus
extern "C" {
#endif

#if !defined(D_BITS) && defined(DBITS)
#  define D_BITS        DBITS
#endif
#if !defined(D_BITS)
#  error "D_BITS is not defined"
#endif
#if (D_BITS < 16)
#  define D_SIZE        LZO_SIZE(D_BITS)
#  define D_MASK        LZO_MASK(D_BITS)
#else
#  define D_SIZE        LZO_USIZE(D_BITS)
#  define D_MASK        LZO_UMASK(D_BITS)
#endif
#define D_HIGH          ((D_MASK >> 1) + 1)

#if !defined(DD_BITS)
#  define DD_BITS       0
#endif
#define DD_SIZE         LZO_SIZE(DD_BITS)
#define DD_MASK         LZO_MASK(DD_BITS)

#if !defined(DL_BITS)
#  define DL_BITS       (D_BITS - DD_BITS)
#endif
#if (DL_BITS < 16)
#  define DL_SIZE       LZO_SIZE(DL_BITS)
#  define DL_MASK       LZO_MASK(DL_BITS)
#else
#  define DL_SIZE       LZO_USIZE(DL_BITS)
#  define DL_MASK       LZO_UMASK(DL_BITS)
#endif

#if (D_BITS != DL_BITS + DD_BITS)
#  error "D_BITS does not match"
#endif
#if (D_BITS < 8 || D_BITS > 18)
#  error "invalid D_BITS"
#endif
#if (DL_BITS < 8 || DL_BITS > 20)
#  error "invalid DL_BITS"
#endif
#if (DD_BITS < 0 || DD_BITS > 6)
#  error "invalid DD_BITS"
#endif

#if !defined(DL_MIN_LEN)
#  define DL_MIN_LEN    3
#endif
#if !defined(DL_SHIFT)
#  define DL_SHIFT      ((DL_BITS + (DL_MIN_LEN - 1)) / DL_MIN_LEN)
#endif

#define LZO_HASH_GZIP                   1
#define LZO_HASH_GZIP_INCREMENTAL       2
#define LZO_HASH_LZO_INCREMENTAL_A      3
#define LZO_HASH_LZO_INCREMENTAL_B      4

#if !defined(LZO_HASH)
#  error "choose a hashing strategy"
#endif

#if (DL_MIN_LEN == 3)
#  define _DV2_A(p,shift1,shift2) \
	(((( (lzo_uint32)((p)[0]) << shift1) ^ (p)[1]) << shift2) ^ (p)[2])
#  define _DV2_B(p,shift1,shift2) \
	(((( (lzo_uint32)((p)[2]) << shift1) ^ (p)[1]) << shift2) ^ (p)[0])
#  define _DV3_B(p,shift1,shift2,shift3) \
	((_DV2_B((p)+1,shift1,shift2) << (shift3)) ^ (p)[0])
#elif (DL_MIN_LEN == 2)
#  define _DV2_A(p,shift1,shift2) \
	(( (lzo_uint32)(p[0]) << shift1) ^ p[1])
#  define _DV2_B(p,shift1,shift2) \
	(( (lzo_uint32)(p[1]) << shift1) ^ p[2])
#else
#  error "invalid DL_MIN_LEN"
#endif
#define _DV_A(p,shift)      _DV2_A(p,shift,shift)
#define _DV_B(p,shift)      _DV2_B(p,shift,shift)
#define DA2(p,s1,s2) \
	(((((lzo_uint32)((p)[2]) << (s2)) + (p)[1]) << (s1)) + (p)[0])
#define DS2(p,s1,s2) \
	(((((lzo_uint32)((p)[2]) << (s2)) - (p)[1]) << (s1)) - (p)[0])
#define DX2(p,s1,s2) \
	(((((lzo_uint32)((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 DMS(v,s)        ((lzo_uint) (((v) & (D_MASK >> (s))) << (s)))
#define DM(v)           DMS(v,0)

#if (LZO_HASH == LZO_HASH_GZIP)
#  define _DINDEX(dv,p)     (_DV_A((p),DL_SHIFT))

#elif (LZO_HASH == LZO_HASH_GZIP_INCREMENTAL)
#  define __LZO_HASH_INCREMENTAL
#  define DVAL_FIRST(dv,p)  dv = _DV_A((p),DL_SHIFT)
#  define DVAL_NEXT(dv,p)   dv = (((dv) << DL_SHIFT) ^ p[2])
#  define _DINDEX(dv,p)     (dv)
#  define DVAL_LOOKAHEAD    DL_MIN_LEN

#elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_A)
#  define __LZO_HASH_INCREMENTAL
#  define DVAL_FIRST(dv,p)  dv = _DV_A((p),5)
#  define DVAL_NEXT(dv,p) \
		dv ^= (lzo_uint32)(p[-1]) << (2*5); dv = (((dv) << 5) ^ p[2])
#  define _DINDEX(dv,p)     ((0x9f5f * (dv)) >> 5)
#  define DVAL_LOOKAHEAD    DL_MIN_LEN

#elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_B)
#  define __LZO_HASH_INCREMENTAL
#  define DVAL_FIRST(dv,p)  dv = _DV_B((p),5)
#  define DVAL_NEXT(dv,p) \
		dv ^= p[-1]; dv = (((dv) >> 5) ^ ((lzo_uint32)(p[2]) << (2*5)))
#  define _DINDEX(dv,p)     ((0x9f5f * (dv)) >> 5)
#  define DVAL_LOOKAHEAD    DL_MIN_LEN

#else
#  error "choose a hashing strategy"
#endif

#ifndef DINDEX
#define DINDEX(dv,p)        ((lzo_uint)((_DINDEX(dv,p)) & DL_MASK) << DD_BITS)
#endif
#if !defined(DINDEX1) && defined(D_INDEX1)
#define DINDEX1             D_INDEX1
#endif
#if !defined(DINDEX2) && defined(D_INDEX2)
#define DINDEX2             D_INDEX2
#endif

#if !defined(__LZO_HASH_INCREMENTAL)
#  define DVAL_FIRST(dv,p)  ((void) 0)
#  define DVAL_NEXT(dv,p)   ((void) 0)
#  define DVAL_LOOKAHEAD    0
#endif

#if !defined(DVAL_ASSERT)
#if defined(__LZO_HASH_INCREMENTAL) && !defined(NDEBUG)
static void DVAL_ASSERT(lzo_uint32 dv, const lzo_byte *p)
{
    lzo_uint32 df;
    DVAL_FIRST(df,(p));
    assert(DINDEX(dv,p) == DINDEX(df,p));
}
#else
#  define DVAL_ASSERT(dv,p) ((void) 0)
#endif
#endif

#if defined(LZO_DICT_USE_PTR)
#  define DENTRY(p,in)                          (p)
#  define GINDEX(m_pos,m_off,dict,dindex,in)    m_pos = dict[dindex]
#else
#  define DENTRY(p,in)                          ((lzo_uint) ((p)-(in)))
#  define GINDEX(m_pos,m_off,dict,dindex,in)    m_off = dict[dindex]
#endif

#if (DD_BITS == 0)

#  define UPDATE_D(dict,drun,dv,p,in)       dict[ DINDEX(dv,p) ] = DENTRY(p,in)
#  define UPDATE_I(dict,drun,index,p,in)    dict[index] = DENTRY(p,in)
#  define UPDATE_P(ptr,drun,p,in)           (ptr)[0] = DENTRY(p,in)

#else

#  define UPDATE_D(dict,drun,dv,p,in)   \
	dict[ DINDEX(dv,p) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
#  define UPDATE_I(dict,drun,index,p,in)    \
	dict[ (index) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
#  define UPDATE_P(ptr,drun,p,in)   \
	(ptr) [ drun++ ] = DENTRY(p,in); drun &= DD_MASK

#endif

#if defined(LZO_DICT_USE_PTR)

#define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
	(m_pos == NULL || (m_off = (lzo_moff_t) (ip - m_pos)) > max_offset)

#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
    (BOUNDS_CHECKING_OFF_IN_EXPR( \
	(PTR_LT(m_pos,in) || \
	 (m_off = (lzo_moff_t) PTR_DIFF(ip,m_pos)) <= 0 || \
	  m_off > max_offset) ))

#else

#define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
	(m_off == 0 || \
	 ((m_off = (lzo_moff_t) ((ip)-(in)) - m_off) > max_offset) || \
	 (m_pos = (ip) - (m_off), 0) )

#define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
	((lzo_moff_t) ((ip)-(in)) <= m_off || \
	 ((m_off = (lzo_moff_t) ((ip)-(in)) - m_off) > max_offset) || \
	 (m_pos = (ip) - (m_off), 0) )

#endif

#if defined(LZO_DETERMINISTIC)
#  define LZO_CHECK_MPOS    LZO_CHECK_MPOS_DET
#else
#  define LZO_CHECK_MPOS    LZO_CHECK_MPOS_NON_DET
#endif

#ifdef __cplusplus
}
#endif

#endif

#endif

#endif

#define DO_COMPRESS     lzo1x_1_compress

static
lzo_uint do_compress     ( const lzo_byte *in , lzo_uint  in_len,
				 lzo_byte *out, lzo_uintp out_len,
				 lzo_voidp wrkmem )
{
#if 0 && defined(__GNUC__) && defined(__i386__)
    register const lzo_byte *ip __asm__("%esi");
#else
    register const lzo_byte *ip;
#endif
    lzo_byte *op;
    const lzo_byte * const in_end = in + in_len;
    const lzo_byte * const ip_end = in + in_len - M2_MAX_LEN - 5;
    const lzo_byte *ii;
    lzo_dict_p const dict = (lzo_dict_p) wrkmem;

    op = out;
    ip = in;
    ii = ip;

    ip += 4;
    for (;;)
    {
#if 0 && defined(__GNUC__) && defined(__i386__)
	register const lzo_byte *m_pos __asm__("%edi");
#else
	register const lzo_byte *m_pos;
#endif
	lzo_moff_t m_off;
	lzo_uint m_len;
	lzo_uint dindex;

	DINDEX1(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])