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(_WIN64)

   333

		typedef unsigned __int64 lzo_ptr_t;

   334

		typedef signed __int64   lzo_sptr_r;

   335

#		define __LZO_HAVE_PTR_T

   336

#	endif

   337

#endif

   338

#if !defined(__LZO_HAVE_PTR_T)

   339

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

   340

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_LONG)

   341

	   typedef unsigned long	lzo_ptr_t;

   342

	   typedef long			 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)

   349

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED)

   350

	   typedef unsigned int	 lzo_ptr_t;

   351

	   typedef int			  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(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED_SHORT)

   358

#	if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_SHORT)

   359

	   typedef unsigned short   lzo_ptr_t;

   360

	   typedef short			lzo_sptr_t;

   361

#	  define __LZO_HAVE_PTR_T

   362

#	endif

   363

#  endif

   364

#endif

   365

#if !defined(__LZO_HAVE_PTR_T)

   366

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

   367

#	error "no suitable type for lzo_ptr_t"

   368

#  else

   369

	 typedef unsigned long	  lzo_ptr_t;

   370

	 typedef long			   lzo_sptr_t;

   371

#	define __LZO_HAVE_PTR_T

   372

#  endif

   373

#endif

   374

   375

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

   376

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

   377

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

   378

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

   379

#else

   380

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

   381

#define PTR_LINEAR(a)	   PTR(a)

   382

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

   383

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

   384

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

   385

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

   386

#endif

   387

   388

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

   389

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

   390

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

   391

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

   392

   393

LZO_EXTERN(lzo_ptr_t)

   394

__lzo_ptr_linear(const lzo_voidp ptr);

   395

   396

typedef union

   397

{

   398

	char			a_char;

   399

	unsigned char   a_uchar;

   400

	short		   a_short;

   401

	unsigned short  a_ushort;

   402

	int			 a_int;

   403

	unsigned int	a_uint;

   404

	long			a_long;

   405

	unsigned long   a_ulong;

   406

	lzo_int		 a_lzo_int;

   407

	lzo_uint		a_lzo_uint;

   408

	lzo_int32	   a_lzo_int32;

   409

	lzo_uint32	  a_lzo_uint32;

   410

	ptrdiff_t	   a_ptrdiff_t;

   411

	lzo_ptrdiff_t   a_lzo_ptrdiff_t;

   412

	lzo_ptr_t	   a_lzo_ptr_t;

   413

	lzo_voidp	   a_lzo_voidp;

   414

	void *		  a_void_p;

   415

	lzo_bytep	   a_lzo_bytep;

   416

	lzo_bytepp	  a_lzo_bytepp;

   417

	lzo_uintp	   a_lzo_uintp;

   418

	lzo_uint *	  a_lzo_uint_p;

   419

	lzo_uint32p	 a_lzo_uint32p;

   420

	lzo_uint32 *	a_lzo_uint32_p;

   421

	unsigned char * a_uchar_p;

   422

	char *		  a_char_p;

   423

}

   424

lzo_full_align_t;

   425

   426

#ifdef __cplusplus

   427

}

   428

#endif

   429

   430

#endif

   431

   432

#define LZO_DETERMINISTIC

   433

   434

#define LZO_DICT_USE_PTR

   435

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

   436

#  undef LZO_DICT_USE_PTR

   437

#endif

   438

   439

#if defined(LZO_DICT_USE_PTR)

   440

#  define lzo_dict_t	const lzo_bytep

   441

#  define lzo_dict_p	lzo_dict_t __LZO_MMODEL *

   442

#else

   443

#  define lzo_dict_t	lzo_uint

   444

#  define lzo_dict_p	lzo_dict_t __LZO_MMODEL *

   445

#endif

   446

   447

#if !defined(lzo_moff_t)

   448

#define lzo_moff_t	  lzo_uint

   449

#endif

   450

   451

#endif

   452

   453

   454

#ifndef __LZO_UTIL_H

   455

#define __LZO_UTIL_H

   456

   457

#ifndef __LZO_CONF_H

   458

#endif

   459

   460

#ifdef __cplusplus

   461

extern "C" {

   462

#endif

   463

   464

#if 1 && defined(HAVE_MEMCPY)

   465

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

   466

   467

#define MEMCPY8_DS(dest,src,len) \

   468

	memcpy(dest,src,len); \

   469

	dest += len; \

   470

	src += len

   471

   472

#endif

   473

#endif

   474

   475

#if 0 && !defined(MEMCPY8_DS)

   476

   477

#define MEMCPY8_DS(dest,src,len) \

   478

	{ do { \

   479

		*dest++ = *src++; \

   480

		*dest++ = *src++; \

   481

		*dest++ = *src++; \

   482

		*dest++ = *src++; \

   483

		*dest++ = *src++; \

   484

		*dest++ = *src++; \

   485

		*dest++ = *src++; \

   486

		*dest++ = *src++; \

   487

		len -= 8; \

   488

	} while (len > 0); }

   489

   490

#endif

   491

   492

#if !defined(MEMCPY8_DS)

   493

   494

#define MEMCPY8_DS(dest,src,len) \

   495

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

   496

	do { \

   497

		*dest++ = *src++; \

   498

		*dest++ = *src++; \

   499

		*dest++ = *src++; \

   500

		*dest++ = *src++; \

   501

		*dest++ = *src++; \

   502

		*dest++ = *src++; \

   503

		*dest++ = *src++; \

   504

		*dest++ = *src++; \

   505

	} while (--__l > 0); }

   506

   507

#endif

   508

   509

#define MEMCPY_DS(dest,src,len) \

   510

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

   511

	while (--len > 0)

   512

   513

#define MEMMOVE_DS(dest,src,len) \

   514

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

   515

	while (--len > 0)

   516

   517

#if 0 && defined(LZO_OPTIMIZE_GNUC_i386)

   518

   519

#define BZERO8_PTR(s,l,n) \

   520

__asm__ __volatile__( \

   521

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

   522

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

   523

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

   524

	"cld \n"						\

   525

	"rep \n"						\

   526

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

   527

	:			   \

   528

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

   529

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