1

/* $Id$ */

     2

     3

/* minilzo.c -- mini subset of the LZO real-time data compression library

     4

     5

   This file is part of the LZO real-time data compression library.

     6

     7

   Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer

     8

   Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer

     9

   Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer

    10

   Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer

    11

   Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer

    12

   Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer

    13

   Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer

    14

   All Rights Reserved.

    15

    16

   The LZO library is free software; you can redistribute it and/or

    17

   modify it under the terms of the GNU General Public License as

    18

   published by the Free Software Foundation; either version 2 of

    19

   the License, or (at your option) any later version.

    20

    21

   The LZO library is distributed in the hope that it will be useful,

    22

   but WITHOUT ANY WARRANTY; without even the implied warranty of

    23

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    24

   GNU General Public License for more details.

    25

    26

   You should have received a copy of the GNU General Public License

    27

   along with the LZO library; see the file COPYING.

    28

   If not, write to the Free Software Foundation, Inc.,

    29

   59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

    30

    31

   Markus F.X.J. Oberhumer

    32

   <markus@oberhumer.com>

    33

   http://www.oberhumer.com/opensource/lzo/

    34

 */

    35

    36

/*

    37

 * NOTE:

    38

 *   the full LZO package can be found at

    39

 *   http://www.oberhumer.com/opensource/lzo/

    40

 */

    41

    42

#define LZO_DISABLE_CHECKS

    43

#define LZO1X

    44

    45

#define __LZO_IN_MINILZO

    46

#define LZO_BUILD

    47

    48

#ifdef MINILZO_HAVE_CONFIG_H

    49

#  include <config.h>

    50

#endif

    51

    52

#undef LZO_HAVE_CONFIG_H

    53

#include "minilzo.h"

    54

    55

#if !defined(MINILZO_VERSION) || (MINILZO_VERSION != 0x1080)

    56

#  error "version mismatch in miniLZO source files"

    57

#endif

    58

    59

#ifdef MINILZO_HAVE_CONFIG_H

    60

#  define LZO_HAVE_CONFIG_H

    61

#endif

    62

    63

#if !defined(LZO_NO_SYS_TYPES_H)

    64

#  include <sys/types.h>

    65

#endif

    66

#include <stdio.h>

    67

    68

#ifndef __LZO_CONF_H

    69

#define __LZO_CONF_H

    70

    71

#if defined(__BOUNDS_CHECKING_ON)

    72

#  include <unchecked.h>

    73

#else

    74

#  define BOUNDS_CHECKING_OFF_DURING(stmt)	  stmt

    75

#  define BOUNDS_CHECKING_OFF_IN_EXPR(expr)	 (expr)

    76

#endif

    77

    78

#if !defined(LZO_HAVE_CONFIG_H)

    79

#  include <stddef.h>

    80

#  include <string.h>

    81

#  if !defined(NO_STDLIB_H)

    82

#	include <stdlib.h>

    83

#  endif

    84

#  define HAVE_MEMCMP

    85

#  define HAVE_MEMCPY

    86

#  define HAVE_MEMMOVE

    87

#  define HAVE_MEMSET

    88

#else

    89

#  include <sys/types.h>

    90

#  if defined(HAVE_STDDEF_H)

    91

#	include <stddef.h>

    92

#  endif

    93

#  if defined(STDC_HEADERS)

    94

#	include <string.h>

    95

#	include <stdlib.h>

    96

#  endif

    97

#endif

    98

    99

#if defined(__LZO_DOS16) || defined(__LZO_WIN16)

   100

#  define HAVE_MALLOC_H

   101

#  define HAVE_HALLOC

   102

#endif

   103

   104

#undef NDEBUG

   105

#if !defined(LZO_DEBUG)

   106

#  define NDEBUG

   107

#endif

   108

#if defined(LZO_DEBUG) || !defined(NDEBUG)

   109

#  if !defined(NO_STDIO_H)

   110

#	include <stdio.h>

   111

#  endif

   112

#endif

   113

#include <assert.h>

   114

   115

#if !defined(LZO_COMPILE_TIME_ASSERT)

   116

#  define LZO_COMPILE_TIME_ASSERT(expr) \

   117

		{ typedef int __lzo_compile_time_assert_fail[1 - 2 * !(expr)]; }

   118

#endif

   119

   120

#if !defined(LZO_UNUSED)

   121

#  if 1

   122

#	define LZO_UNUSED(var)	 ((void)&var)

   123

#  elif 0

   124

#	define LZO_UNUSED(var)	 { typedef int __lzo_unused[sizeof(var) ? 2 : 1]; }

   125

#  else

   126

#	define LZO_UNUSED(parm)	(parm = parm)

   127

#  endif

   128

#endif

   129

   130

#if !defined(__inline__) && !defined(__GNUC__)

   131

#  if defined(__cplusplus)

   132

#	define __inline__	  inline

   133

#  else

   134

#	define __inline__

   135

#  endif

   136

#endif

   137

   138

#if defined(NO_MEMCMP)

   139

#  undef HAVE_MEMCMP

   140

#endif

   141

   142

#if 0

   143

#  define LZO_BYTE(x)	   ((unsigned char) (x))

   144

#else

   145

#  define LZO_BYTE(x)	   ((unsigned char) ((x) & 0xff))

   146

#endif

   147

   148

#define LZO_MAX(a,b)		((a) >= (b) ? (a) : (b))

   149

#define LZO_MIN(a,b)		((a) <= (b) ? (a) : (b))

   150

#define LZO_MAX3(a,b,c)	 ((a) >= (b) ? LZO_MAX(a,c) : LZO_MAX(b,c))

   151

#define LZO_MIN3(a,b,c)	 ((a) <= (b) ? LZO_MIN(a,c) : LZO_MIN(b,c))

   152

   153

#define lzo_sizeof(type)	((lzo_uint) (sizeof(type)))

   154

   155

#define LZO_HIGH(array)	 ((lzo_uint) (sizeof(array)/sizeof(*(array))))

   156

   157

#define LZO_SIZE(bits)	  (1u << (bits))

   158

#define LZO_MASK(bits)	  (LZO_SIZE(bits) - 1)

   159

   160

#define LZO_LSIZE(bits)	 (1ul << (bits))

   161

#define LZO_LMASK(bits)	 (LZO_LSIZE(bits) - 1)

   162

   163

#define LZO_USIZE(bits)	 ((lzo_uint) 1 << (bits))

   164

#define LZO_UMASK(bits)	 (LZO_USIZE(bits) - 1)

   165

   166

#define LZO_STYPE_MAX(b)	(((1l  << (8*(b)-2)) - 1l)  + (1l  << (8*(b)-2)))

   167

#define LZO_UTYPE_MAX(b)	(((1ul << (8*(b)-1)) - 1ul) + (1ul << (8*(b)-1)))

   168

   169

#if !defined(SIZEOF_UNSIGNED)

   170

#  if (UINT_MAX == 0xffff)

   171

#	define SIZEOF_UNSIGNED		 2

   172

#  elif (UINT_MAX == LZO_0xffffffffL)

   173

#	define SIZEOF_UNSIGNED		 4

   174

#  elif (UINT_MAX >= LZO_0xffffffffL)

   175

#	define SIZEOF_UNSIGNED		 8

   176

#  else

   177

#	error "SIZEOF_UNSIGNED"

   178

#  endif

   179

#endif

   180

   181

#if !defined(SIZEOF_UNSIGNED_LONG)

   182

#  if (ULONG_MAX == LZO_0xffffffffL)

   183

#	define SIZEOF_UNSIGNED_LONG	4

   184

#  elif (ULONG_MAX >= LZO_0xffffffffL)

   185

#	define SIZEOF_UNSIGNED_LONG	8

   186

#  else

   187

#	error "SIZEOF_UNSIGNED_LONG"

   188

#  endif

   189

#endif

   190

   191

#if !defined(SIZEOF_SIZE_T)

   192

#  define SIZEOF_SIZE_T			 SIZEOF_UNSIGNED

   193

#endif

   194

#if !defined(SIZE_T_MAX)

   195

#  define SIZE_T_MAX				LZO_UTYPE_MAX(SIZEOF_SIZE_T)

   196

#endif

   197

   198

#if 1 && defined(__LZO_i386) && (UINT_MAX == LZO_0xffffffffL)

   199

#  if !defined(LZO_UNALIGNED_OK_2) && (USHRT_MAX == 0xffff)

   200

#	define LZO_UNALIGNED_OK_2

   201

#  endif

   202

#  if !defined(LZO_UNALIGNED_OK_4) && (LZO_UINT32_MAX == LZO_0xffffffffL)

   203

#	define LZO_UNALIGNED_OK_4

   204

#  endif

   205

#endif

   206

   207

#if defined(LZO_UNALIGNED_OK_2) || defined(LZO_UNALIGNED_OK_4)

   208

#  if !defined(LZO_UNALIGNED_OK)

   209

#	define LZO_UNALIGNED_OK

   210

#  endif

   211

#endif

   212

   213

#if defined(__LZO_NO_UNALIGNED)

   214

#  undef LZO_UNALIGNED_OK

   215

#  undef LZO_UNALIGNED_OK_2

   216

#  undef LZO_UNALIGNED_OK_4

   217

#endif

   218

   219

#if defined(LZO_UNALIGNED_OK_2) && (USHRT_MAX != 0xffff)

   220

#  error "LZO_UNALIGNED_OK_2 must not be defined on this system"

   221

#endif

   222

#if defined(LZO_UNALIGNED_OK_4) && (LZO_UINT32_MAX != LZO_0xffffffffL)

   223

#  error "LZO_UNALIGNED_OK_4 must not be defined on this system"

   224

#endif

   225

   226

#if defined(__LZO_NO_ALIGNED)

   227

#  undef LZO_ALIGNED_OK_4

   228

#endif

   229

   230

#if defined(LZO_ALIGNED_OK_4) && (LZO_UINT32_MAX != LZO_0xffffffffL)

   231

#  error "LZO_ALIGNED_OK_4 must not be defined on this system"

   232

#endif

   233

   234

#define LZO_LITTLE_ENDIAN	   1234

   235

#define LZO_BIG_ENDIAN		  4321

   236

#define LZO_PDP_ENDIAN		  3412

   237

   238

#if !defined(LZO_BYTE_ORDER)

   239

#  if defined(MFX_BYTE_ORDER)

   240

#	define LZO_BYTE_ORDER	  MFX_BYTE_ORDER

   241

#  elif defined(__LZO_i386)

   242

#	define LZO_BYTE_ORDER	  LZO_LITTLE_ENDIAN

   243

#  elif defined(BYTE_ORDER)

   244

#	define LZO_BYTE_ORDER	  BYTE_ORDER

   245

#  elif defined(__BYTE_ORDER)

   246

#	define LZO_BYTE_ORDER	  __BYTE_ORDER

   247

#  endif

   248

#endif

   249

   250

#if defined(LZO_BYTE_ORDER)

   251

#  if (LZO_BYTE_ORDER != LZO_LITTLE_ENDIAN) && \

   252

	  (LZO_BYTE_ORDER != LZO_BIG_ENDIAN)

   253

#	error "invalid LZO_BYTE_ORDER"

   254

#  endif

   255

#endif

   256

   257

#if defined(LZO_UNALIGNED_OK) && !defined(LZO_BYTE_ORDER)

   258

#  error "LZO_BYTE_ORDER is not defined"

   259

#endif

   260

   261

#define LZO_OPTIMIZE_GNUC_i386_IS_BUGGY

   262

   263

#if defined(NDEBUG) && !defined(LZO_DEBUG) && !defined(__LZO_CHECKER)

   264

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

   265

#	if !defined(LZO_OPTIMIZE_GNUC_i386_IS_BUGGY)

   266

#	  define LZO_OPTIMIZE_GNUC_i386

   267

#	endif

   268

#  endif

   269

#endif

   270

   271

__LZO_EXTERN_C int __lzo_init_done;

   272

__LZO_EXTERN_C const lzo_byte __lzo_copyright[];

   273

LZO_EXTERN(const lzo_byte *) lzo_copyright(void);

   274

__LZO_EXTERN_C const lzo_uint32 _lzo_crc32_table[256];

   275

   276

#define _LZO_STRINGIZE(x)		   #x

   277

#define _LZO_MEXPAND(x)			 _LZO_STRINGIZE(x)

   278

   279

#define _LZO_CONCAT2(a,b)		   a ## b

   280

#define _LZO_CONCAT3(a,b,c)		 a ## b ## c

   281

#define _LZO_CONCAT4(a,b,c,d)	   a ## b ## c ## d

   282

#define _LZO_CONCAT5(a,b,c,d,e)	 a ## b ## c ## d ## e

   283

   284

#define _LZO_ECONCAT2(a,b)		  _LZO_CONCAT2(a,b)

   285

#define _LZO_ECONCAT3(a,b,c)		_LZO_CONCAT3(a,b,c)

   286

#define _LZO_ECONCAT4(a,b,c,d)	  _LZO_CONCAT4(a,b,c,d)

   287

#define _LZO_ECONCAT5(a,b,c,d,e)	_LZO_CONCAT5(a,b,c,d,e)

   288

   289

#ifndef __LZO_PTR_H

   290

#define __LZO_PTR_H

   291

   292

#ifdef __cplusplus

   293

extern "C" {

   294

#endif

   295

   296

#if defined(__LZO_DOS16) || defined(__LZO_WIN16)

   297

#  include <dos.h>

   298

#  if 1 && defined(__WATCOMC__)

   299

#	include <i86.h>

   300

	 __LZO_EXTERN_C unsigned char _HShift;

   301

#	define __LZO_HShift	_HShift

   302

#  elif 1 && defined(_MSC_VER)

   303

	 __LZO_EXTERN_C unsigned short __near _AHSHIFT;

   304

#	define __LZO_HShift	((unsigned) &_AHSHIFT)

   305

#  elif defined(__LZO_WIN16)

   306

#	define __LZO_HShift	3

   307

#  else

   308

#	define __LZO_HShift	12

   309

#  endif

   310

#  if !defined(_FP_SEG) && defined(FP_SEG)

   311

#	define _FP_SEG		 FP_SEG

   312

#  endif

   313

#  if !defined(_FP_OFF) && defined(FP_OFF)

   314

#	define _FP_OFF		 FP_OFF

   315

#  endif

   316

#endif

   317

   318

#if !defined(lzo_ptrdiff_t)

   319

#  if (UINT_MAX >= LZO_0xffffffffL)

   320

	 typedef ptrdiff_t		  lzo_ptrdiff_t;

   321

#  else

   322

	 typedef long			   lzo_ptrdiff_t;

   323

#  endif

   324

#endif

   325

   326

#if !defined(__LZO_HAVE_PTR_T)

   327

#  if defined(lzo_ptr_t)

   328

#	define __LZO_HAVE_PTR_T

   329

#  endif

   330

#endif

   331

#if !defined(__LZO_HAVE_PTR_T)

   332

#  if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED_LONG)

   333

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_LONG)

   334

	   typedef unsigned long	lzo_ptr_t;

   335

	   typedef long			 lzo_sptr_t;

   336

#	  define __LZO_HAVE_PTR_T

   337

#	endif

   338

#  endif

   339

#endif

   340

#if !defined(__LZO_HAVE_PTR_T)

   341

#  if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED)

   342

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED)

   343

	   typedef unsigned int	 lzo_ptr_t;

   344

	   typedef int			  lzo_sptr_t;

   345

#	  define __LZO_HAVE_PTR_T

   346

#	endif

   347

#  endif

   348

#endif

   349

#if !defined(__LZO_HAVE_PTR_T)

   350

#  if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED_SHORT)

   351

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_SHORT)

   352

	   typedef unsigned short   lzo_ptr_t;

   353

	   typedef short			lzo_sptr_t;

   354

#	  define __LZO_HAVE_PTR_T

   355

#	endif

   356

#  endif

   357

#endif

   358

#if !defined(__LZO_HAVE_PTR_T)

   359

#  if defined(LZO_HAVE_CONFIG_H) || defined(SIZEOF_CHAR_P)

   360

#	error "no suitable type for lzo_ptr_t"

   361

#  else

   362

	 typedef unsigned long	  lzo_ptr_t;

   363

	 typedef long			   lzo_sptr_t;

   364

#	define __LZO_HAVE_PTR_T

   365

#  endif

   366

#endif

   367

   368

#if defined(__LZO_DOS16) || defined(__LZO_WIN16)

   369

#define PTR(a)			  ((lzo_bytep) (a))

   370

#define PTR_ALIGNED_4(a)	((_FP_OFF(a) & 3) == 0)

   371

#define PTR_ALIGNED2_4(a,b) (((_FP_OFF(a) | _FP_OFF(b)) & 3) == 0)

   372

#else

   373

#define PTR(a)			  ((lzo_ptr_t) (a))

   374

#define PTR_LINEAR(a)	   PTR(a)

   375

#define PTR_ALIGNED_4(a)	((PTR_LINEAR(a) & 3) == 0)

   376

#define PTR_ALIGNED_8(a)	((PTR_LINEAR(a) & 7) == 0)

   377

#define PTR_ALIGNED2_4(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0)

   378

#define PTR_ALIGNED2_8(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0)

   379

#endif

   380

   381

#define PTR_LT(a,b)		 (PTR(a) < PTR(b))

   382

#define PTR_GE(a,b)		 (PTR(a) >= PTR(b))

   383

#define PTR_DIFF(a,b)	   ((lzo_ptrdiff_t) (PTR(a) - PTR(b)))

   384

#define pd(a,b)			 ((lzo_uint) ((a)-(b)))

   385

   386

LZO_EXTERN(lzo_ptr_t)

   387

__lzo_ptr_linear(const lzo_voidp ptr);

   388

   389

typedef union

   390

{

   391

	char			a_char;

   392

	unsigned char   a_uchar;

   393

	short		   a_short;

   394

	unsigned short  a_ushort;

   395

	int			 a_int;

   396

	unsigned int	a_uint;

   397

	long			a_long;

   398

	unsigned long   a_ulong;

   399

	lzo_int		 a_lzo_int;

   400

	lzo_uint		a_lzo_uint;

   401

	lzo_int32	   a_lzo_int32;

   402

	lzo_uint32	  a_lzo_uint32;

   403

	ptrdiff_t	   a_ptrdiff_t;

   404

	lzo_ptrdiff_t   a_lzo_ptrdiff_t;

   405

	lzo_ptr_t	   a_lzo_ptr_t;

   406

	lzo_voidp	   a_lzo_voidp;

   407

	void *		  a_void_p;

   408

	lzo_bytep	   a_lzo_bytep;

   409

	lzo_bytepp	  a_lzo_bytepp;

   410

	lzo_uintp	   a_lzo_uintp;

   411

	lzo_uint *	  a_lzo_uint_p;

   412

	lzo_uint32p	 a_lzo_uint32p;

   413

	lzo_uint32 *	a_lzo_uint32_p;

   414

	unsigned char * a_uchar_p;

   415

	char *		  a_char_p;

   416

}

   417

lzo_full_align_t;

   418

   419

#ifdef __cplusplus

   420

}

   421

#endif

   422

   423

#endif

   424

   425

#define LZO_DETERMINISTIC

   426

   427

#define LZO_DICT_USE_PTR

   428

#if defined(__LZO_DOS16) || defined(__LZO_WIN16) || defined(__LZO_STRICT_16BIT)

   429

#  undef LZO_DICT_USE_PTR

   430

#endif

   431

   432

#if defined(LZO_DICT_USE_PTR)

   433

#  define lzo_dict_t	const lzo_bytep

   434

#  define lzo_dict_p	lzo_dict_t __LZO_MMODEL *

   435

#else

   436

#  define lzo_dict_t	lzo_uint

   437

#  define lzo_dict_p	lzo_dict_t __LZO_MMODEL *

   438

#endif

   439

   440

#if !defined(lzo_moff_t)

   441

#define lzo_moff_t	  lzo_uint

   442

#endif

   443

   444

#endif

   445

   446

   447

#ifndef __LZO_UTIL_H

   448

#define __LZO_UTIL_H

   449

   450

#ifndef __LZO_CONF_H

   451

#endif

   452

   453

#ifdef __cplusplus

   454

extern "C" {

   455

#endif

   456

   457

#if 1 && defined(HAVE_MEMCPY)

   458

#if !defined(__LZO_DOS16) && !defined(__LZO_WIN16)

   459

   460

#define MEMCPY8_DS(dest,src,len) \

   461

	memcpy(dest,src,len); \

   462

	dest += len; \

   463

	src += len

   464

   465

#endif

   466

#endif

   467

   468

#if 0 && !defined(MEMCPY8_DS)

   469

   470

#define MEMCPY8_DS(dest,src,len) \

   471

	{ do { \

   472

		*dest++ = *src++; \

   473

		*dest++ = *src++; \

   474

		*dest++ = *src++; \

   475

		*dest++ = *src++; \

   476

		*dest++ = *src++; \

   477

		*dest++ = *src++; \

   478

		*dest++ = *src++; \

   479

		*dest++ = *src++; \

   480

		len -= 8; \

   481

	} while (len > 0); }

   482

   483

#endif

   484

   485

#if !defined(MEMCPY8_DS)

   486

   487

#define MEMCPY8_DS(dest,src,len) \

   488

	{ register lzo_uint __l = (len) / 8; \

   489

	do { \

   490

		*dest++ = *src++; \

   491

		*dest++ = *src++; \

   492

		*dest++ = *src++; \

   493

		*dest++ = *src++; \

   494

		*dest++ = *src++; \

   495

		*dest++ = *src++; \

   496

		*dest++ = *src++; \

   497

		*dest++ = *src++; \

   498

	} while (--__l > 0); }

   499

   500

#endif

   501

   502

#define MEMCPY_DS(dest,src,len) \

   503

	do *dest++ = *src++; \

   504

	while (--len > 0)

   505

   506

#define MEMMOVE_DS(dest,src,len) \

   507

	do *dest++ = *src++; \

   508

	while (--len > 0)

   509

   510

#if 0 && defined(LZO_OPTIMIZE_GNUC_i386)

   511

   512

#define BZERO8_PTR(s,l,n) \

   513

__asm__ __volatile__( \

   514

	"movl  %0,%%eax \n"			 \

   515

	"movl  %1,%%edi \n"			 \

   516

	"movl  %2,%%ecx \n"			 \

   517

	"cld \n"						\

   518

	"rep \n"						\

   519

	"stosl %%eax,(%%edi) \n"		\

   520

	:			   \

   521

	:"g" (0),"g" (s),"g" (n)		\

   522

	:"eax","edi","ecx", "memory", "cc" \

   523

)

   524

   525

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

   526

   527

#if 1

   528

#define BZERO8_PTR(s,l,n)   memset((s),0,(lzo_uint)(l)*(n))

   529

#else