minilzo.c

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

	*dest++ = *src++; \
	*dest++ = *src++; \
	*dest++ = *src++; \
	*dest++ = *src++; \
	*dest++ = *src++; \
	*dest++ = *src++; \
    } while (--__l > 0); }

#endif

#define MEMCPY_DS(dest,src,len) \
    do *dest++ = *src++; \
    while (--len > 0)

#define MEMMOVE_DS(dest,src,len) \
    do *dest++ = *src++; \
    while (--len > 0)

#if 0 && defined(LZO_OPTIMIZE_GNUC_i386)

#define BZERO8_PTR(s,l,n) \
__asm__ __volatile__( \
    "movl  %0,%%eax \n"             \
    "movl  %1,%%edi \n"             \
    "movl  %2,%%ecx \n"             \
    "cld \n"                        \
    "rep \n"                        \
    "stosl %%eax,(%%edi) \n"        \
    :               \
    :"g" (0),"g" (s),"g" (n)        \
    :"eax","edi","ecx", "memory", "cc" \
)

#elif (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMSET)

#if 1
#define BZERO8_PTR(s,l,n)   memset((s),0,(lzo_uint)(l)*(n))
#else
#define BZERO8_PTR(s,l,n)   memset((lzo_voidp)(s),0,(lzo_uint)(l)*(n))
#endif

#else

#define BZERO8_PTR(s,l,n) \
    lzo_memset((lzo_voidp)(s),0,(lzo_uint)(l)*(n))

#endif

#if 0
#if defined(__GNUC__) && defined(__i386__)

unsigned char lzo_rotr8(unsigned char value, int shift);
extern __inline__ unsigned char lzo_rotr8(unsigned char value, int shift)
{
    unsigned char result;

    __asm__ __volatile__ ("movb %b1, %b0; rorb %b2, %b0"
			: "=a"(result) : "g"(value), "c"(shift));
    return result;
}

unsigned short lzo_rotr16(unsigned short value, int shift);
extern __inline__ unsigned short lzo_rotr16(unsigned short value, int shift)
{
    unsigned short result;

    __asm__ __volatile__ ("movw %b1, %b0; rorw %b2, %b0"
			: "=a"(result) : "g"(value), "c"(shift));
    return result;
}

#endif
#endif

#ifdef __cplusplus
}
#endif

#endif

LZO_PUBLIC(lzo_bool)
lzo_assert(int expr)
{
    return (expr) ? 1 : 0;
}

/* If you use the LZO library in a product, you *must* keep this
 * copyright string in the executable of your product.
 */

const lzo_byte __lzo_copyright[] =
#if !defined(__LZO_IN_MINLZO)
    LZO_VERSION_STRING;
#else
    "\n\n\n"
    "LZO real-time data compression library.\n"
    "Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002 Markus Franz Xaver Johannes Oberhumer\n"
    "<[e-mail]>\n"
    "http://www.oberhumer.com/opensource/lzo/\n"
    "\n"
    "LZO version: v" LZO_VERSION_STRING ", " LZO_VERSION_DATE "\n"
    "LZO build date: " __DATE__ " " __TIME__ "\n\n"
    "LZO special compilation options:\n"
#ifdef __cplusplus
    " __cplusplus\n"
#endif
#if defined(__PIC__)
    " __PIC__\n"
#elif defined(__pic__)
    " __pic__\n"
#endif
#if (UINT_MAX < LZO_0xffffffffL)
    " 16BIT\n"
#endif
#if defined(__LZO_STRICT_16BIT)
    " __LZO_STRICT_16BIT\n"
#endif
#if (UINT_MAX > LZO_0xffffffffL)
    " UINT_MAX=" _LZO_MEXPAND(UINT_MAX) "\n"
#endif
#if (ULONG_MAX > LZO_0xffffffffL)
    " ULONG_MAX=" _LZO_MEXPAND(ULONG_MAX) "\n"
#endif
#if defined(LZO_BYTE_ORDER)
    " LZO_BYTE_ORDER=" _LZO_MEXPAND(LZO_BYTE_ORDER) "\n"
#endif
#if defined(LZO_UNALIGNED_OK_2)
    " LZO_UNALIGNED_OK_2\n"
#endif
#if defined(LZO_UNALIGNED_OK_4)
    " LZO_UNALIGNED_OK_4\n"
#endif
#if defined(LZO_ALIGNED_OK_4)
    " LZO_ALIGNED_OK_4\n"
#endif
#if defined(LZO_DICT_USE_PTR)
    " LZO_DICT_USE_PTR\n"
#endif
#if defined(__LZO_QUERY_COMPRESS)
    " __LZO_QUERY_COMPRESS\n"
#endif
#if defined(__LZO_QUERY_DECOMPRESS)
    " __LZO_QUERY_DECOMPRESS\n"
#endif
#if defined(__LZO_IN_MINILZO)
    " __LZO_IN_MINILZO\n"
#endif
    "\n\n"
    "$Id: LZO " LZO_VERSION_STRING " built " __DATE__ " " __TIME__
#if defined(__GNUC__) && defined(__VERSION__)
    " by gcc " __VERSION__
#elif defined(__BORLANDC__)
    " by Borland C " _LZO_MEXPAND(__BORLANDC__)
#elif defined(_MSC_VER)
    " by Microsoft C " _LZO_MEXPAND(_MSC_VER)
#elif defined(__PUREC__)
    " by Pure C " _LZO_MEXPAND(__PUREC__)
#elif defined(__SC__)
    " by Symantec C " _LZO_MEXPAND(__SC__)
#elif defined(__TURBOC__)
    " by Turbo C " _LZO_MEXPAND(__TURBOC__)
#elif defined(__WATCOMC__)
    " by Watcom C " _LZO_MEXPAND(__WATCOMC__)
#endif
    " $\n"
    "$Copyright: LZO (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002 Markus Franz Xaver Johannes Oberhumer $\n";
#endif

LZO_PUBLIC(const lzo_byte *)
lzo_copyright(void)
{
    return __lzo_copyright;
}

LZO_PUBLIC(unsigned)
lzo_version(void)
{
    return LZO_VERSION;
}

LZO_PUBLIC(const char *)
lzo_version_string(void)
{
    return LZO_VERSION_STRING;
}

LZO_PUBLIC(const char *)
lzo_version_date(void)
{
    return LZO_VERSION_DATE;
}

LZO_PUBLIC(const lzo_charp)
_lzo_version_string(void)
{
    return LZO_VERSION_STRING;
}

LZO_PUBLIC(const lzo_charp)
_lzo_version_date(void)
{
    return LZO_VERSION_DATE;
}

#define LZO_BASE 65521u
#define LZO_NMAX 5552

#define LZO_DO1(buf,i)  {s1 += buf[i]; s2 += s1;}
#define LZO_DO2(buf,i)  LZO_DO1(buf,i); LZO_DO1(buf,i+1);
#define LZO_DO4(buf,i)  LZO_DO2(buf,i); LZO_DO2(buf,i+2);
#define LZO_DO8(buf,i)  LZO_DO4(buf,i); LZO_DO4(buf,i+4);
#define LZO_DO16(buf,i) LZO_DO8(buf,i); LZO_DO8(buf,i+8);

LZO_PUBLIC(lzo_uint32)
lzo_adler32(lzo_uint32 adler, const lzo_byte *buf, lzo_uint len)
{
    lzo_uint32 s1 = adler & 0xffff;
    lzo_uint32 s2 = (adler >> 16) & 0xffff;
    int k;

    if (buf == NULL)
	return 1;

    while (len > 0)
    {
	k = len < LZO_NMAX ? (int) len : LZO_NMAX;
	len -= k;
	if (k >= 16) do
	{
	    LZO_DO16(buf,0);
	    buf += 16;
	    k -= 16;
	} while (k >= 16);
	if (k != 0) do
	{
	    s1 += *buf++;
	    s2 += s1;
	} while (--k > 0);
	s1 %= LZO_BASE;
	s2 %= LZO_BASE;
    }
    return (s2 << 16) | s1;
}

LZO_PUBLIC(int)
lzo_memcmp(const lzo_voidp s1, const lzo_voidp s2, lzo_uint len)
{
#if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMCMP)
    return memcmp(s1,s2,len);
#else
    const lzo_byte *p1 = (const lzo_byte *) s1;
    const lzo_byte *p2 = (const lzo_byte *) s2;
    int d;

    if (len > 0) do
    {
	d = *p1 - *p2;
	if (d != 0)
	    return d;
	p1++;
	p2++;
    }
    while (--len > 0);
    return 0;
#endif
}

LZO_PUBLIC(lzo_voidp)
lzo_memcpy(lzo_voidp dest, const lzo_voidp src, lzo_uint len)
{
#if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMCPY)
    return memcpy(dest,src,len);
#else
    lzo_byte *p1 = (lzo_byte *) dest;
    const lzo_byte *p2 = (const lzo_byte *) src;

    if (len <= 0 || p1 == p2)
	return dest;
    do
	*p1++ = *p2++;
    while (--len > 0);
    return dest;
#endif
}

LZO_PUBLIC(lzo_voidp)
lzo_memmove(lzo_voidp dest, const lzo_voidp src, lzo_uint len)
{
#if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMMOVE)
    return memmove(dest,src,len);
#else
    lzo_byte *p1 = (lzo_byte *) dest;
    const lzo_byte *p2 = (const lzo_byte *) src;

    if (len <= 0 || p1 == p2)
	return dest;

    if (p1 < p2)
    {
	do
	    *p1++ = *p2++;
	while (--len > 0);
    }
    else
    {
	p1 += len;
	p2 += len;
	do
	    *--p1 = *--p2;
	while (--len > 0);
    }
    return dest;
#endif
}

LZO_PUBLIC(lzo_voidp)
lzo_memset(lzo_voidp s, int c, lzo_uint len)
{
#if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMSET)
    return memset(s,c,len);
#else
    lzo_byte *p = (lzo_byte *) s;

    if (len > 0) do
	*p++ = LZO_BYTE(c);
    while (--len > 0);
    return s;
#endif
}

#if 0
#  define IS_SIGNED(type)       (((type) (1ul << (8 * sizeof(type) - 1))) < 0)
#  define IS_UNSIGNED(type)     (((type) (1ul << (8 * sizeof(type) - 1))) > 0)
#else
#  define IS_SIGNED(type)       (((type) (-1)) < ((type) 0))
#  define IS_UNSIGNED(type)     (((type) (-1)) > ((type) 0))
#endif

#define IS_POWER_OF_2(x)        (((x) & ((x) - 1)) == 0)

static lzo_bool schedule_insns_bug(void);
static lzo_bool strength_reduce_bug(int *);

#if 0 || defined(LZO_DEBUG)
#include <stdio.h>
static lzo_bool __lzo_assert_fail(const char *s, unsigned line)
{
#if defined(__palmos__)
    printf("LZO assertion failed in line %u: '%s'\n",line,s);
#else
    fprintf(stderr,"LZO assertion failed in line %u: '%s'\n",line,s);
#endif
    return 0;
}
#  define __lzo_assert(x)   ((x) ? 1 : __lzo_assert_fail(#x,__LINE__))
#else
#  define __lzo_assert(x)   ((x) ? 1 : 0)
#endif

#undef COMPILE_TIME_ASSERT
#if 0
#  define COMPILE_TIME_ASSERT(expr)     r &= __lzo_assert(expr)
#else
#  define COMPILE_TIME_ASSERT(expr)     LZO_COMPILE_TIME_ASSERT(expr)
#endif

static lzo_bool basic_integral_check(void)
{
    lzo_bool r = 1;

    COMPILE_TIME_ASSERT(CHAR_BIT == 8);
    COMPILE_TIME_ASSERT(sizeof(char) == 1);
    COMPILE_TIME_ASSERT(sizeof(short) >= 2);
    COMPILE_TIME_ASSERT(sizeof(long) >= 4);
    COMPILE_TIME_ASSERT(sizeof(int) >= sizeof(short));
    COMPILE_TIME_ASSERT(sizeof(long) >= sizeof(int));

    COMPILE_TIME_ASSERT(sizeof(lzo_uint) == sizeof(lzo_int));
    COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == sizeof(lzo_int32));

    COMPILE_TIME_ASSERT(sizeof(lzo_uint32) >= 4);
    COMPILE_TIME_ASSERT(sizeof(lzo_uint32) >= sizeof(unsigned));
#if defined(__LZO_STRICT_16BIT)
    COMPILE_TIME_ASSERT(sizeof(lzo_uint) == 2);
#else
    COMPILE_TIME_ASSERT(sizeof(lzo_uint) >= 4);
    COMPILE_TIME_ASSERT(sizeof(lzo_uint) >= sizeof(unsigned));
#endif

#if (USHRT_MAX == 65535u)
    COMPILE_TIME_ASSERT(sizeof(short) == 2);
#elif (USHRT_MAX == LZO_0xffffffffL)
    COMPILE_TIME_ASSERT(sizeof(short) == 4);
#elif (USHRT_MAX >= LZO_0xffffffffL)
    COMPILE_TIME_ASSERT(sizeof(short) > 4);
#endif
#if (UINT_MAX == 65535u)
    COMPILE_TIME_ASSERT(sizeof(int) == 2);
#elif (UINT_MAX == LZO_0xffffffffL)
    COMPILE_TIME_ASSERT(sizeof(int) == 4);
#elif (UINT_MAX >= LZO_0xffffffffL)
    COMPILE_TIME_ASSERT(sizeof(int) > 4);
#endif
#if (ULONG_MAX == 65535ul)
    COMPILE_TIME_ASSERT(sizeof(long) == 2);
#elif (ULONG_MAX == LZO_0xffffffffL)
    COMPILE_TIME_ASSERT(sizeof(long) == 4);
#elif (ULONG_MAX >= LZO_0xffffffffL)
    COMPILE_TIME_ASSERT(sizeof(long) > 4);
#endif

#if defined(SIZEOF_UNSIGNED)
    COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED == sizeof(unsigned));
#endif
#if defined(SIZEOF_UNSIGNED_LONG)
    COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED_LONG == sizeof(unsigned long));
#endif
#if defined(SIZEOF_UNSIGNED_SHORT)
    COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED_SHORT == sizeof(unsigned short));
#endif
#if !defined(__LZO_IN_MINILZO)
#if defined(SIZEOF_SIZE_T)
    COMPILE_TIME_ASSERT(SIZEOF_SIZE_T == sizeof(size_t));
#endif
#endif

    COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned char));
    COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned short));
    COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned));
    COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned long));
    COMPILE_TIME_ASSERT(IS_SIGNED(short));
    COMPILE_TIME_ASSERT(IS_SIGNED(int));
    COMPILE_TIME_ASSERT(IS_SIGNED(long));

    COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_uint32));
    COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_uint));
    COMPILE_TIME_ASSERT(IS_SIGNED(lzo_int32));
    COMPILE_TIME_ASSERT(IS_SIGNED(lzo_int));

    COMPILE_TIME_ASSERT(INT_MAX    == LZO_STYPE_MAX(sizeof(int)));
    COMPILE_TIME_ASSERT(UINT_MAX   == LZO_UTYPE_MAX(sizeof(unsigned)));
    COMPILE_TIME_ASSERT(LONG_MAX   == LZO_STYPE_MAX(sizeof(long)));
    COMPILE_TIME_ASSERT(ULONG_MAX  == LZO_UTYPE_MAX(sizeof(unsigned long)));
    COMPILE_TIME_ASSERT(SHRT_MAX   == LZO_STYPE_MAX(sizeof(short)));
    COMPILE_TIME_ASSERT(USHRT_MAX  == LZO_UTYPE_MAX(sizeof(unsigned short)));
    COMPILE_TIME_ASSERT(LZO_UINT32_MAX == LZO_UTYPE_MAX(sizeof(lzo_uint32)));
    COMPILE_TIME_ASSERT(LZO_UINT_MAX   == LZO_UTYPE_MAX(sizeof(lzo_uint)));
#if !defined(__LZO_IN_MINILZO)
    COMPILE_TIME_ASSERT(SIZE_T_MAX     == LZO_UTYPE_MAX(sizeof(size_t)));
#endif

    r &= __lzo_assert(LZO_BYTE(257) == 1);

    return r;
}

static lzo_bool basic_ptr_check(void)
{
    lzo_bool r = 1;

    COMPILE_TIME_ASSERT(sizeof(char *) >= sizeof(int));
    COMPILE_TIME_ASSERT(sizeof(lzo_byte *) >= sizeof(char *));

    COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_byte *));
    COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_voidpp));
    COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_bytepp));
    COMPILE_TIME_ASSERT(sizeof(lzo_voidp) >= sizeof(lzo_uint));

    COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) == sizeof(lzo_voidp));
    COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) == sizeof(lzo_sptr_t));
    COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) >= sizeof(lzo_uint));

    COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= 4);
    COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= sizeof(ptrdiff_t));

    COMPILE_TIME_ASSERT(sizeof(ptrdiff_t) >= sizeof(size_t));
    COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= sizeof(lzo_uint));

#if defined(SIZEOF_CHAR_P)
    COMPILE_TIME_ASSERT(SIZEOF_CHAR_P == sizeof(char *));
#endif
#if defined(SIZEOF_PTRDIFF_T)
    COMPILE_TIME_ASSERT(SIZEOF_PTRDIFF_T == sizeof(ptrdiff_t));
#endif

    COMPILE_TIME_ASSERT(IS_SIGNED(ptrdiff_t));
    COMPILE_TIME_ASSERT(IS_UNSIGNED(size_t));
    COMPILE_TIME_ASSERT(IS_SIGNED(lzo_ptrdiff_t));
    COMPILE_TIME_ASSERT(IS_SIGNED(lzo_sptr_t));
    COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_ptr_t));
    COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_moff_t));

    return r;
}

static lzo_bool ptr_check(void)
{
    lzo_bool r = 1;
    int i;
    char _wrkmem[10 * sizeof(lzo_byte *) + sizeof(lzo_full_align_t)];
    lzo_bytep wrkmem;
    lzo_bytepp dict;
    unsigned char x[4 * sizeof(lzo_full_align_t)];
    long d;
    lzo_full_align_t a;
    lzo_full_align_t u;

    for (i = 0; i < (int) sizeof(x); i++)
	x[i] = LZO_BYTE(i);

    wrkmem = LZO_PTR_ALIGN_UP((lzo_byte *)_wrkmem,sizeof(lzo_full_align_t));

#if 0
    dict = (lzo_bytepp) wrkmem;
#else

    u.a_lzo_bytep = wrkmem; dict = u.a_lzo_bytepp;
#endif

    d = (long) ((const lzo_bytep) dict - (const lzo_bytep) _wrkmem);
    r &= __lzo_assert(d >= 0);
    r &= __lzo_assert(d < (long) sizeof(lzo_full_align_t));

    memset(&a,0,sizeof(a));
    r &= __lzo_assert(a.a_lzo_voidp == NULL);

    memset(&a,0xff,sizeof(a));
    r &= __lzo_assert(a.a_ushort == USHRT_MAX);
    r &= __lzo_assert(a.a_uint == UINT_MAX);
    r &= __lzo_assert(a.a_ulong == ULONG_MAX);
    r &= __lzo_assert(a.a_lzo_uint == LZO_UINT_MAX);
    r &= __lzo_assert(a.a_lzo_uint32 == LZO_UINT32_MAX);

    if (r == 1)
    {
	for (i = 0; i < 8; i++)
	    r &= __lzo_assert((const lzo_voidp) (&dict[i]) == (const lzo_voidp) (&wrkmem[i * sizeof(lzo_byte *)]));
    }

    memset(&a,0,sizeof(a));
    r &= __lzo_assert(a.a_char_p == NULL);
    r &= __lzo_assert(a.a_lzo_bytep == NULL);
    r &= __lzo_assert(NULL == (void *)0);
    if (r == 1)
    {
	for (i = 0; i < 10; i++)
	    dict[i] = wrkmem;
	BZERO8_PTR(dict+1,sizeof(dict[0]),8);
	r &= __lzo_assert(dict[0] == wrkmem);
	for (i = 1; i < 9; i++)
	    r &= __lzo_assert(dict[i] == NULL);
	r &= __lzo_assert(dict[9] == wrkmem);
    }

    if (r == 1)
    {
	unsigned k = 1;
	const unsigned n = (unsigned) sizeof(lzo_uint32);
	lzo_byte *p0;
	lzo_byte *p1;