1

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

     2

     3

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

     4

     5

   Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer

     6

   Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer

     7

   Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer

     8

   Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer

     9

   Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer

    10

   Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer

    11

   Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer

    12

   All Rights Reserved.

    13

    14

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

    15

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

    16

   published by the Free Software Foundation; either version 2 of

    17

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

    18

    19

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

    20

   but WITHOUT ANY WARRANTY; without even the implied warranty of

    21

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    22

   GNU General Public License for more details.

    23

    24

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

    25

   along with the LZO library; see the file COPYING.

    26

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

    27

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

    28

    29

   Markus F.X.J. Oberhumer

    30

   <markus@oberhumer.com>

    31

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

    32

 */

    33

    34

/*

    35

 * NOTE:

    36

 *   the full LZO package can be found at

    37

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

    38

 */

    39

    40

#define LZO_DISABLE_CHECKS

    41

#define LZO1X

    42

    43

#define __LZO_IN_MINILZO

    44

#define LZO_BUILD

    45

    46

#ifdef MINILZO_HAVE_CONFIG_H

    47

#  include <config.h>

    48

#endif

    49

    50

#undef LZO_HAVE_CONFIG_H

    51

#include "minilzo.h"

    52

    53

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

    54

#  error "version mismatch in miniLZO source files"

    55

#endif

    56

    57

#ifdef MINILZO_HAVE_CONFIG_H

    58

#  define LZO_HAVE_CONFIG_H

    59

#endif

    60

    61

#if !defined(LZO_NO_SYS_TYPES_H)

    62

#  include <sys/types.h>

    63

#endif

    64

#include <stdio.h>

    65

    66

#ifndef __LZO_CONF_H

    67

#define __LZO_CONF_H

    68

    69

#if defined(__BOUNDS_CHECKING_ON)

    70

#  include <unchecked.h>

    71

#else

    72

#  define BOUNDS_CHECKING_OFF_DURING(stmt)	  stmt

    73

#  define BOUNDS_CHECKING_OFF_IN_EXPR(expr)	 (expr)

    74

#endif

    75

    76

#if !defined(LZO_HAVE_CONFIG_H)

    77

#  include <stddef.h>

    78

#  include <string.h>

    79

#  if !defined(NO_STDLIB_H)

    80

#	include <stdlib.h>

    81

#  endif

    82

#  define HAVE_MEMCMP

    83

#  define HAVE_MEMCPY

    84

#  define HAVE_MEMMOVE

    85

#  define HAVE_MEMSET

    86

#else

    87

#  include <sys/types.h>

    88

#  if defined(HAVE_STDDEF_H)

    89

#	include <stddef.h>

    90

#  endif

    91

#  if defined(STDC_HEADERS)

    92

#	include <string.h>

    93

#	include <stdlib.h>

    94

#  endif

    95

#endif

    96

    97

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

    98

#  define HAVE_MALLOC_H

    99

#  define HAVE_HALLOC

   100

#endif

   101

   102

#undef NDEBUG

   103

#if !defined(LZO_DEBUG)

   104

#  define NDEBUG

   105

#endif

   106

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

   107

#  if !defined(NO_STDIO_H)

   108

#	include <stdio.h>

   109

#  endif

   110

#endif

   111

#include <assert.h>

   112

   113

#if !defined(LZO_COMPILE_TIME_ASSERT)

   114

#  define LZO_COMPILE_TIME_ASSERT(expr) \

   115

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

   116

#endif

   117

   118

#if !defined(LZO_UNUSED)

   119

#  if 1

   120

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

   121

#  elif 0

   122

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

   123

#  else

   124

#	define LZO_UNUSED(parm)	(parm = parm)

   125

#  endif

   126

#endif

   127

   128

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

   129

#  if defined(__cplusplus)

   130

#	define __inline__	  inline

   131

#  else

   132

#	define __inline__

   133

#  endif

   134

#endif

   135

   136

#if defined(NO_MEMCMP)

   137

#  undef HAVE_MEMCMP

   138

#endif

   139

   140

#if 0

   141

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

   142

#else

   143

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

   144

#endif

   145

   146

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

   147

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

   148

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

   149

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

   150

   151

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

   152

   153

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

   154

   155

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

   156

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

   157

   158

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

   159

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

   160

   161

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

   162

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

   163

   164

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

   165

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

   166

   167

#if !defined(SIZEOF_UNSIGNED)

   168

#  if (UINT_MAX == 0xffff)

   169

#	define SIZEOF_UNSIGNED		 2

   170

#  elif (UINT_MAX == LZO_0xffffffffL)

   171

#	define SIZEOF_UNSIGNED		 4

   172

#  elif (UINT_MAX >= LZO_0xffffffffL)

   173

#	define SIZEOF_UNSIGNED		 8

   174

#  else

   175

#	error "SIZEOF_UNSIGNED"

   176

#  endif

   177

#endif

   178

   179

#if !defined(SIZEOF_UNSIGNED_LONG)

   180

#  if (ULONG_MAX == LZO_0xffffffffL)

   181

#	define SIZEOF_UNSIGNED_LONG	4

   182

#  elif (ULONG_MAX >= LZO_0xffffffffL)

   183

#	define SIZEOF_UNSIGNED_LONG	8

   184

#  else

   185

#	error "SIZEOF_UNSIGNED_LONG"

   186

#  endif

   187

#endif

   188

   189

#if !defined(SIZEOF_SIZE_T)

   190

#  define SIZEOF_SIZE_T			 SIZEOF_UNSIGNED

   191

#endif

   192

#if !defined(SIZE_T_MAX)

   193

#  define SIZE_T_MAX				LZO_UTYPE_MAX(SIZEOF_SIZE_T)

   194

#endif

   195

   196

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

   197

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

   198

#	define LZO_UNALIGNED_OK_2

   199

#  endif

   200

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

   201

#	define LZO_UNALIGNED_OK_4

   202

#  endif

   203

#endif

   204

   205

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

   206

#  if !defined(LZO_UNALIGNED_OK)

   207

#	define LZO_UNALIGNED_OK

   208

#  endif

   209

#endif

   210

   211

#if defined(__LZO_NO_UNALIGNED)

   212

#  undef LZO_UNALIGNED_OK

   213

#  undef LZO_UNALIGNED_OK_2

   214

#  undef LZO_UNALIGNED_OK_4

   215

#endif

   216

   217

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

   218

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

   219

#endif

   220

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

   221

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

   222

#endif

   223

   224

#if defined(__LZO_NO_ALIGNED)

   225

#  undef LZO_ALIGNED_OK_4

   226

#endif

   227

   228

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

   229

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

   230

#endif

   231

   232

#define LZO_LITTLE_ENDIAN	   1234

   233

#define LZO_BIG_ENDIAN		  4321

   234

#define LZO_PDP_ENDIAN		  3412

   235

   236

#if !defined(LZO_BYTE_ORDER)

   237

#  if defined(MFX_BYTE_ORDER)

   238

#	define LZO_BYTE_ORDER	  MFX_BYTE_ORDER

   239

#  elif defined(__LZO_i386)

   240

#	define LZO_BYTE_ORDER	  LZO_LITTLE_ENDIAN

   241

#  elif defined(BYTE_ORDER)

   242

#	define LZO_BYTE_ORDER	  BYTE_ORDER

   243

#  elif defined(__BYTE_ORDER)

   244

#	define LZO_BYTE_ORDER	  __BYTE_ORDER

   245

#  endif

   246

#endif

   247

   248

#if defined(LZO_BYTE_ORDER)

   249

#  if (LZO_BYTE_ORDER != LZO_LITTLE_ENDIAN) && \

   250

	  (LZO_BYTE_ORDER != LZO_BIG_ENDIAN)

   251

#	error "invalid LZO_BYTE_ORDER"

   252

#  endif

   253

#endif

   254

   255

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

   256

#  error "LZO_BYTE_ORDER is not defined"

   257

#endif

   258

   259

#define LZO_OPTIMIZE_GNUC_i386_IS_BUGGY

   260

   261

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

   262

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

   263

#	if !defined(LZO_OPTIMIZE_GNUC_i386_IS_BUGGY)

   264

#	  define LZO_OPTIMIZE_GNUC_i386

   265

#	endif

   266

#  endif

   267

#endif

   268

   269

__LZO_EXTERN_C int __lzo_init_done;

   270

__LZO_EXTERN_C const lzo_byte __lzo_copyright[];

   271

LZO_EXTERN(const lzo_byte *) lzo_copyright(void);

   272

__LZO_EXTERN_C const lzo_uint32 _lzo_crc32_table[256];

   273

   274

#define _LZO_STRINGIZE(x)		   #x

   275

#define _LZO_MEXPAND(x)			 _LZO_STRINGIZE(x)

   276

   277

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

   278

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

   279

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

   280

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

   281

   282

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

   283

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

   284

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

   285

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

   286

   287

#ifndef __LZO_PTR_H

   288

#define __LZO_PTR_H

   289

   290

#ifdef __cplusplus

   291

extern "C" {

   292

#endif

   293

   294

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

   295

#  include <dos.h>

   296

#  if 1 && defined(__WATCOMC__)

   297

#	include <i86.h>

   298

	 __LZO_EXTERN_C unsigned char _HShift;

   299

#	define __LZO_HShift	_HShift

   300

#  elif 1 && defined(_MSC_VER)

   301

	 __LZO_EXTERN_C unsigned short __near _AHSHIFT;

   302

#	define __LZO_HShift	((unsigned) &_AHSHIFT)

   303

#  elif defined(__LZO_WIN16)

   304

#	define __LZO_HShift	3

   305

#  else

   306

#	define __LZO_HShift	12

   307

#  endif

   308

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

   309

#	define _FP_SEG		 FP_SEG

   310

#  endif

   311

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

   312

#	define _FP_OFF		 FP_OFF

   313

#  endif

   314

#endif

   315

   316

#if !defined(lzo_ptrdiff_t)

   317

#  if (UINT_MAX >= LZO_0xffffffffL)

   318

	 typedef ptrdiff_t		  lzo_ptrdiff_t;

   319

#  else

   320

	 typedef long			   lzo_ptrdiff_t;

   321

#  endif

   322

#endif

   323

   324

#if !defined(__LZO_HAVE_PTR_T)

   325

#  if defined(lzo_ptr_t)

   326

#	define __LZO_HAVE_PTR_T

   327

#  endif

   328

#endif

   329

#if !defined(__LZO_HAVE_PTR_T)

   330

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

   331

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_LONG)

   332

	   typedef unsigned long	lzo_ptr_t;

   333

	   typedef long			 lzo_sptr_t;

   334

#	  define __LZO_HAVE_PTR_T

   335

#	endif

   336

#  endif

   337

#endif

   338

#if !defined(__LZO_HAVE_PTR_T)

   339

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

   340

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED)

   341

	   typedef unsigned int	 lzo_ptr_t;

   342

	   typedef int			  lzo_sptr_t;

   343

#	  define __LZO_HAVE_PTR_T

   344

#	endif

   345

#  endif

   346

#endif

   347

#if !defined(__LZO_HAVE_PTR_T)

   348

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

   349

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_SHORT)

   350

	   typedef unsigned short   lzo_ptr_t;

   351

	   typedef short			lzo_sptr_t;

   352

#	  define __LZO_HAVE_PTR_T

   353

#	endif

   354

#  endif

   355

#endif

   356

#if !defined(__LZO_HAVE_PTR_T)

   357

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

   358

#	error "no suitable type for lzo_ptr_t"

   359

#  else

   360

	 typedef unsigned long	  lzo_ptr_t;

   361

	 typedef long			   lzo_sptr_t;

   362

#	define __LZO_HAVE_PTR_T

   363

#  endif

   364

#endif

   365

   366

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

   367

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

   368

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

   369

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

   370

#else

   371

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

   372

#define PTR_LINEAR(a)	   PTR(a)

   373

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

   374

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

   375

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

   376

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

   377

#endif

   378

   379

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

   380

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

   381

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

   382

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

   383

   384

LZO_EXTERN(lzo_ptr_t)

   385

__lzo_ptr_linear(const lzo_voidp ptr);

   386

   387

typedef union

   388

{

   389

	char			a_char;

   390

	unsigned char   a_uchar;

   391

	short		   a_short;

   392

	unsigned short  a_ushort;

   393

	int			 a_int;

   394

	unsigned int	a_uint;

   395

	long			a_long;

   396

	unsigned long   a_ulong;

   397

	lzo_int		 a_lzo_int;

   398

	lzo_uint		a_lzo_uint;

   399

	lzo_int32	   a_lzo_int32;

   400

	lzo_uint32	  a_lzo_uint32;

   401

	ptrdiff_t	   a_ptrdiff_t;

   402

	lzo_ptrdiff_t   a_lzo_ptrdiff_t;

   403

	lzo_ptr_t	   a_lzo_ptr_t;

   404

	lzo_voidp	   a_lzo_voidp;

   405

	void *		  a_void_p;

   406

	lzo_bytep	   a_lzo_bytep;

   407

	lzo_bytepp	  a_lzo_bytepp;

   408

	lzo_uintp	   a_lzo_uintp;

   409

	lzo_uint *	  a_lzo_uint_p;

   410

	lzo_uint32p	 a_lzo_uint32p;

   411

	lzo_uint32 *	a_lzo_uint32_p;

   412

	unsigned char * a_uchar_p;

   413

	char *		  a_char_p;

   414

}

   415

lzo_full_align_t;

   416

   417

#ifdef __cplusplus

   418

}

   419

#endif

   420

   421

#endif

   422

   423

#define LZO_DETERMINISTIC

   424

   425

#define LZO_DICT_USE_PTR

   426

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

   427

#  undef LZO_DICT_USE_PTR

   428

#endif

   429

   430

#if defined(LZO_DICT_USE_PTR)

   431

#  define lzo_dict_t	const lzo_bytep

   432

#  define lzo_dict_p	lzo_dict_t __LZO_MMODEL *

   433

#else

   434

#  define lzo_dict_t	lzo_uint

   435

#  define lzo_dict_p	lzo_dict_t __LZO_MMODEL *

   436

#endif

   437

   438

#if !defined(lzo_moff_t)

   439

#define lzo_moff_t	  lzo_uint

   440

#endif

   441

   442

#endif

   443

   444

   445

#ifndef __LZO_UTIL_H

   446

#define __LZO_UTIL_H

   447

   448

#ifndef __LZO_CONF_H

   449

#endif

   450

   451

#ifdef __cplusplus

   452

extern "C" {

   453

#endif

   454

   455

#if 1 && defined(HAVE_MEMCPY)

   456

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

   457

   458

#define MEMCPY8_DS(dest,src,len) \

   459

	memcpy(dest,src,len); \

   460

	dest += len; \

   461

	src += len

   462

   463

#endif

   464

#endif

   465

   466

#if 0 && !defined(MEMCPY8_DS)

   467

   468

#define MEMCPY8_DS(dest,src,len) \

   469

	{ do { \

   470

		*dest++ = *src++; \

   471

		*dest++ = *src++; \

   472

		*dest++ = *src++; \

   473

		*dest++ = *src++; \

   474

		*dest++ = *src++; \

   475

		*dest++ = *src++; \

   476

		*dest++ = *src++; \

   477

		*dest++ = *src++; \

   478

		len -= 8; \

   479

	} while (len > 0); }

   480

   481

#endif

   482

   483

#if !defined(MEMCPY8_DS)

   484

   485

#define MEMCPY8_DS(dest,src,len) \

   486

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

   487

	do { \

   488

		*dest++ = *src++; \

   489

		*dest++ = *src++; \

   490

		*dest++ = *src++; \

   491

		*dest++ = *src++; \

   492

		*dest++ = *src++; \

   493

		*dest++ = *src++; \

   494

		*dest++ = *src++; \

   495

		*dest++ = *src++; \

   496

	} while (--__l > 0); }

   497

   498

#endif

   499

   500

#define MEMCPY_DS(dest,src,len) \

   501

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

   502

	while (--len > 0)

   503

   504

#define MEMMOVE_DS(dest,src,len) \

   505

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

   506

	while (--len > 0)

   507

   508

#if 0 && defined(LZO_OPTIMIZE_GNUC_i386)

   509

   510

#define BZERO8_PTR(s,l,n) \

   511

__asm__ __volatile__( \

   512

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

   513

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

   514

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

   515

	"cld \n"						\

   516

	"rep \n"						\

   517

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

   518

	:			   \

   519

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

   520

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

   521

)

   522

   523

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

   524

   525

#if 1

   526

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

   527

#else

   528

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

   529

#endif

   530