git.maemo.org Git - presencevnc/blob - libvnc/libvncclient/minilzo.c

   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_IN_MINILZO
  41 #define LZO_BUILD
  42
  43 #ifdef MINILZO_HAVE_CONFIG_H
  44 #  include <config.h>
  45 #endif
  46
  47 #undef LZO_HAVE_CONFIG_H
  48 #include "minilzo.h"
  49
  50 #if !defined(MINILZO_VERSION) || (MINILZO_VERSION != 0x1080)
  51 #  error "version mismatch in miniLZO source files"
  52 #endif
  53
  54 #ifdef MINILZO_HAVE_CONFIG_H
  55 #  define LZO_HAVE_CONFIG_H
  56 #endif
  57
  58 #if !defined(LZO_NO_SYS_TYPES_H)
  59 #  include <sys/types.h>
  60 #endif
  61 #include <stdio.h>
  62
  63 #ifndef __LZO_CONF_H
  64 #define __LZO_CONF_H
  65
  66 #if !defined(__LZO_IN_MINILZO)
  67 #  ifndef __LZOCONF_H
  68 #    include <lzoconf.h>
  69 #  endif
  70 #endif
  71
  72 #if defined(__BOUNDS_CHECKING_ON)
  73 #  include <unchecked.h>
  74 #else
  75 #  define BOUNDS_CHECKING_OFF_DURING(stmt)      stmt
  76 #  define BOUNDS_CHECKING_OFF_IN_EXPR(expr)     (expr)
  77 #endif
  78
  79 #if !defined(LZO_HAVE_CONFIG_H)
  80 #  include <stddef.h>
  81 #  include <string.h>
  82 #  if !defined(NO_STDLIB_H)
  83 #    include <stdlib.h>
  84 #  endif
  85 #  define HAVE_MEMCMP
  86 #  define HAVE_MEMCPY
  87 #  define HAVE_MEMMOVE
  88 #  define HAVE_MEMSET
  89 #else
  90 #  include <sys/types.h>
  91 #  if defined(HAVE_STDDEF_H)
  92 #    include <stddef.h>
  93 #  endif
  94 #  if defined(STDC_HEADERS)
  95 #    include <string.h>
  96 #    include <stdlib.h>
  97 #  endif
  98 #endif
  99
 100 #if defined(__LZO_DOS16) || defined(__LZO_WIN16)
 101 #  define HAVE_MALLOC_H
 102 #  define HAVE_HALLOC
 103 #endif
 104
 105 #undef NDEBUG
 106 #if !defined(LZO_DEBUG)
 107 #  define NDEBUG
 108 #endif
 109 #if defined(LZO_DEBUG) || !defined(NDEBUG)
 110 #  if !defined(NO_STDIO_H)
 111 #    include <stdio.h>
 112 #  endif
 113 #endif
 114 #include <assert.h>
 115
 116 #if !defined(LZO_COMPILE_TIME_ASSERT)
 117 #  define LZO_COMPILE_TIME_ASSERT(expr) \
 118         { typedef int __lzo_compile_time_assert_fail[1 - 2 * !(expr)]; }
 119 #endif
 120
 121 #if !defined(LZO_UNUSED)
 122 #  if 1
 123 #    define LZO_UNUSED(var)     ((void)&var)
 124 #  elif 0
 125 #    define LZO_UNUSED(var)     { typedef int __lzo_unused[sizeof(var) ? 2 : 1]; }
 126 #  else
 127 #    define LZO_UNUSED(parm)    (parm = parm)
 128 #  endif
 129 #endif
 130
 131 #if !defined(__inline__) && !defined(__GNUC__)
 132 #  if defined(__cplusplus)
 133 #    define __inline__      inline
 134 #  else
 135 #    define __inline__
 136 #  endif
 137 #endif
 138
 139 #if defined(NO_MEMCMP)
 140 #  undef HAVE_MEMCMP
 141 #endif
 142
 143 #if !defined(HAVE_MEMCMP)
 144 #  undef memcmp
 145 #  define memcmp    lzo_memcmp
 146 #endif
 147 #if !defined(HAVE_MEMCPY)
 148 #  undef memcpy
 149 #  define memcpy    lzo_memcpy
 150 #endif
 151 #if !defined(HAVE_MEMMOVE)
 152 #  undef memmove
 153 #  define memmove   lzo_memmove
 154 #endif
 155 #if !defined(HAVE_MEMSET)
 156 #  undef memset
 157 #  define memset    lzo_memset
 158 #endif
 159
 160 #if 0
 161 #  define LZO_BYTE(x)       ((unsigned char) (x))
 162 #else
 163 #  define LZO_BYTE(x)       ((unsigned char) ((x) & 0xff))
 164 #endif
 165
 166 #define LZO_MAX(a,b)        ((a) >= (b) ? (a) : (b))
 167 #define LZO_MIN(a,b)        ((a) <= (b) ? (a) : (b))
 168 #define LZO_MAX3(a,b,c)     ((a) >= (b) ? LZO_MAX(a,c) : LZO_MAX(b,c))
 169 #define LZO_MIN3(a,b,c)     ((a) <= (b) ? LZO_MIN(a,c) : LZO_MIN(b,c))
 170
 171 #define lzo_sizeof(type)    ((lzo_uint) (sizeof(type)))
 172
 173 #define LZO_HIGH(array)     ((lzo_uint) (sizeof(array)/sizeof(*(array))))
 174
 175 #define LZO_SIZE(bits)      (1u << (bits))
 176 #define LZO_MASK(bits)      (LZO_SIZE(bits) - 1)
 177
 178 #define LZO_LSIZE(bits)     (1ul << (bits))
 179 #define LZO_LMASK(bits)     (LZO_LSIZE(bits) - 1)
 180
 181 #define LZO_USIZE(bits)     ((lzo_uint) 1 << (bits))
 182 #define LZO_UMASK(bits)     (LZO_USIZE(bits) - 1)
 183
 184 #define LZO_STYPE_MAX(b)    (((1l  << (8*(b)-2)) - 1l)  + (1l  << (8*(b)-2)))
 185 #define LZO_UTYPE_MAX(b)    (((1ul << (8*(b)-1)) - 1ul) + (1ul << (8*(b)-1)))
 186
 187 #if !defined(SIZEOF_UNSIGNED)
 188 #  if (UINT_MAX == 0xffff)
 189 #    define SIZEOF_UNSIGNED         2
 190 #  elif (UINT_MAX == LZO_0xffffffffL)
 191 #    define SIZEOF_UNSIGNED         4
 192 #  elif (UINT_MAX >= LZO_0xffffffffL)
 193 #    define SIZEOF_UNSIGNED         8
 194 #  else
 195 #    error "SIZEOF_UNSIGNED"
 196 #  endif
 197 #endif
 198
 199 #if !defined(SIZEOF_UNSIGNED_LONG)
 200 #  if (ULONG_MAX == LZO_0xffffffffL)
 201 #    define SIZEOF_UNSIGNED_LONG    4
 202 #  elif (ULONG_MAX >= LZO_0xffffffffL)
 203 #    define SIZEOF_UNSIGNED_LONG    8
 204 #  else
 205 #    error "SIZEOF_UNSIGNED_LONG"
 206 #  endif
 207 #endif
 208
 209 #if !defined(SIZEOF_SIZE_T)
 210 #  define SIZEOF_SIZE_T             SIZEOF_UNSIGNED
 211 #endif
 212 #if !defined(SIZE_T_MAX)
 213 #  define SIZE_T_MAX                LZO_UTYPE_MAX(SIZEOF_SIZE_T)
 214 #endif
 215
 216 #if 1 && defined(__LZO_i386) && (UINT_MAX == LZO_0xffffffffL)
 217 #  if !defined(LZO_UNALIGNED_OK_2) && (USHRT_MAX == 0xffff)
 218 #    define LZO_UNALIGNED_OK_2
 219 #  endif
 220 #  if !defined(LZO_UNALIGNED_OK_4) && (LZO_UINT32_MAX == LZO_0xffffffffL)
 221 #    define LZO_UNALIGNED_OK_4
 222 #  endif
 223 #endif
 224
 225 #if defined(LZO_UNALIGNED_OK_2) || defined(LZO_UNALIGNED_OK_4)
 226 #  if !defined(LZO_UNALIGNED_OK)
 227 #    define LZO_UNALIGNED_OK
 228 #  endif
 229 #endif
 230
 231 #if defined(__LZO_NO_UNALIGNED)
 232 #  undef LZO_UNALIGNED_OK
 233 #  undef LZO_UNALIGNED_OK_2
 234 #  undef LZO_UNALIGNED_OK_4
 235 #endif
 236
 237 #if defined(LZO_UNALIGNED_OK_2) && (USHRT_MAX != 0xffff)
 238 #  error "LZO_UNALIGNED_OK_2 must not be defined on this system"
 239 #endif
 240 #if defined(LZO_UNALIGNED_OK_4) && (LZO_UINT32_MAX != LZO_0xffffffffL)
 241 #  error "LZO_UNALIGNED_OK_4 must not be defined on this system"
 242 #endif
 243
 244 #if defined(__LZO_NO_ALIGNED)
 245 #  undef LZO_ALIGNED_OK_4
 246 #endif
 247
 248 #if defined(LZO_ALIGNED_OK_4) && (LZO_UINT32_MAX != LZO_0xffffffffL)
 249 #  error "LZO_ALIGNED_OK_4 must not be defined on this system"
 250 #endif
 251
 252 #define LZO_LITTLE_ENDIAN       1234
 253 #define LZO_BIG_ENDIAN          4321
 254 #define LZO_PDP_ENDIAN          3412
 255
 256 #if !defined(LZO_BYTE_ORDER)
 257 #  if defined(MFX_BYTE_ORDER)
 258 #    define LZO_BYTE_ORDER      MFX_BYTE_ORDER
 259 #  elif defined(__LZO_i386)
 260 #    define LZO_BYTE_ORDER      LZO_LITTLE_ENDIAN
 261 #  elif defined(BYTE_ORDER)
 262 #    define LZO_BYTE_ORDER      BYTE_ORDER
 263 #  elif defined(__BYTE_ORDER)
 264 #    define LZO_BYTE_ORDER      __BYTE_ORDER
 265 #  endif
 266 #endif
 267
 268 #if defined(LZO_BYTE_ORDER)
 269 #  if (LZO_BYTE_ORDER != LZO_LITTLE_ENDIAN) && \
 270       (LZO_BYTE_ORDER != LZO_BIG_ENDIAN)
 271 #    error "invalid LZO_BYTE_ORDER"
 272 #  endif
 273 #endif
 274
 275 #if defined(LZO_UNALIGNED_OK) && !defined(LZO_BYTE_ORDER)
 276 #  error "LZO_BYTE_ORDER is not defined"
 277 #endif
 278
 279 #define LZO_OPTIMIZE_GNUC_i386_IS_BUGGY
 280
 281 #if defined(NDEBUG) && !defined(LZO_DEBUG) && !defined(__LZO_CHECKER)
 282 #  if defined(__GNUC__) && defined(__i386__)
 283 #    if !defined(LZO_OPTIMIZE_GNUC_i386_IS_BUGGY)
 284 #      define LZO_OPTIMIZE_GNUC_i386
 285 #    endif
 286 #  endif
 287 #endif
 288
 289 __LZO_EXTERN_C int __lzo_init_done;
 290 __LZO_EXTERN_C const lzo_byte __lzo_copyright[];
 291 LZO_EXTERN(const lzo_byte *) lzo_copyright(void);
 292 __LZO_EXTERN_C const lzo_uint32 _lzo_crc32_table[256];
 293
 294 #define _LZO_STRINGIZE(x)           #x
 295 #define _LZO_MEXPAND(x)             _LZO_STRINGIZE(x)
 296
 297 #define _LZO_CONCAT2(a,b)           a ## b
 298 #define _LZO_CONCAT3(a,b,c)         a ## b ## c
 299 #define _LZO_CONCAT4(a,b,c,d)       a ## b ## c ## d
 300 #define _LZO_CONCAT5(a,b,c,d,e)     a ## b ## c ## d ## e
 301
 302 #define _LZO_ECONCAT2(a,b)          _LZO_CONCAT2(a,b)
 303 #define _LZO_ECONCAT3(a,b,c)        _LZO_CONCAT3(a,b,c)
 304 #define _LZO_ECONCAT4(a,b,c,d)      _LZO_CONCAT4(a,b,c,d)
 305 #define _LZO_ECONCAT5(a,b,c,d,e)    _LZO_CONCAT5(a,b,c,d,e)
 306
 307 #if 0
 308
 309 #define __LZO_IS_COMPRESS_QUERY(i,il,o,ol,w)    ((lzo_voidp)(o) == (w))
 310 #define __LZO_QUERY_COMPRESS(i,il,o,ol,w,n,s) \
 311                 (*ol = (n)*(s), LZO_E_OK)
 312
 313 #define __LZO_IS_DECOMPRESS_QUERY(i,il,o,ol,w)  ((lzo_voidp)(o) == (w))
 314 #define __LZO_QUERY_DECOMPRESS(i,il,o,ol,w,n,s) \
 315                 (*ol = (n)*(s), LZO_E_OK)
 316
 317 #define __LZO_IS_OPTIMIZE_QUERY(i,il,o,ol,w)    ((lzo_voidp)(o) == (w))
 318 #define __LZO_QUERY_OPTIMIZE(i,il,o,ol,w,n,s) \
 319                 (*ol = (n)*(s), LZO_E_OK)
 320
 321 #endif
 322
 323 #ifndef __LZO_PTR_H
 324 #define __LZO_PTR_H
 325
 326 #ifdef __cplusplus
 327 extern "C" {
 328 #endif
 329
 330 #if defined(__LZO_DOS16) || defined(__LZO_WIN16)
 331 #  include <dos.h>
 332 #  if 1 && defined(__WATCOMC__)
 333 #    include <i86.h>
 334      __LZO_EXTERN_C unsigned char _HShift;
 335 #    define __LZO_HShift    _HShift
 336 #  elif 1 && defined(_MSC_VER)
 337      __LZO_EXTERN_C unsigned short __near _AHSHIFT;
 338 #    define __LZO_HShift    ((unsigned) &_AHSHIFT)
 339 #  elif defined(__LZO_WIN16)
 340 #    define __LZO_HShift    3
 341 #  else
 342 #    define __LZO_HShift    12
 343 #  endif
 344 #  if !defined(_FP_SEG) && defined(FP_SEG)
 345 #    define _FP_SEG         FP_SEG
 346 #  endif
 347 #  if !defined(_FP_OFF) && defined(FP_OFF)
 348 #    define _FP_OFF         FP_OFF
 349 #  endif
 350 #endif
 351
 352 #if !defined(lzo_ptrdiff_t)
 353 #  if (UINT_MAX >= LZO_0xffffffffL)
 354      typedef ptrdiff_t          lzo_ptrdiff_t;
 355 #  else
 356      typedef long               lzo_ptrdiff_t;
 357 #  endif
 358 #endif
 359
 360 #if !defined(__LZO_HAVE_PTR_T)
 361 #  if defined(lzo_ptr_t)
 362 #    define __LZO_HAVE_PTR_T
 363 #  endif
 364 #endif
 365 #if !defined(__LZO_HAVE_PTR_T)
 366 #  if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED_LONG)
 367 #    if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_LONG)
 368        typedef unsigned long    lzo_ptr_t;
 369        typedef long             lzo_sptr_t;
 370 #      define __LZO_HAVE_PTR_T
 371 #    endif
 372 #  endif
 373 #endif
 374 #if !defined(__LZO_HAVE_PTR_T)
 375 #  if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED)
 376 #    if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED)
 377        typedef unsigned int     lzo_ptr_t;
 378        typedef int              lzo_sptr_t;
 379 #      define __LZO_HAVE_PTR_T
 380 #    endif
 381 #  endif
 382 #endif
 383 #if !defined(__LZO_HAVE_PTR_T)
 384 #  if defined(SIZEOF_CHAR_P) && defined(SIZEOF_UNSIGNED_SHORT)
 385 #    if (SIZEOF_CHAR_P == SIZEOF_UNSIGNED_SHORT)
 386        typedef unsigned short   lzo_ptr_t;
 387        typedef short            lzo_sptr_t;
 388 #      define __LZO_HAVE_PTR_T
 389 #    endif
 390 #  endif
 391 #endif
 392 #if !defined(__LZO_HAVE_PTR_T)
 393 #  if defined(LZO_HAVE_CONFIG_H) || defined(SIZEOF_CHAR_P)
 394 #    error "no suitable type for lzo_ptr_t"
 395 #  else
 396      typedef unsigned long      lzo_ptr_t;
 397      typedef long               lzo_sptr_t;
 398 #    define __LZO_HAVE_PTR_T
 399 #  endif
 400 #endif
 401
 402 #if defined(__LZO_DOS16) || defined(__LZO_WIN16)
 403 #define PTR(a)              ((lzo_bytep) (a))
 404 #define PTR_ALIGNED_4(a)    ((_FP_OFF(a) & 3) == 0)
 405 #define PTR_ALIGNED2_4(a,b) (((_FP_OFF(a) | _FP_OFF(b)) & 3) == 0)
 406 #else
 407 #define PTR(a)              ((lzo_ptr_t) (a))
 408 #define PTR_LINEAR(a)       PTR(a)
 409 #define PTR_ALIGNED_4(a)    ((PTR_LINEAR(a) & 3) == 0)
 410 #define PTR_ALIGNED_8(a)    ((PTR_LINEAR(a) & 7) == 0)
 411 #define PTR_ALIGNED2_4(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0)
 412 #define PTR_ALIGNED2_8(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0)
 413 #endif
 414
 415 #define PTR_LT(a,b)         (PTR(a) < PTR(b))
 416 #define PTR_GE(a,b)         (PTR(a) >= PTR(b))
 417 #define PTR_DIFF(a,b)       ((lzo_ptrdiff_t) (PTR(a) - PTR(b)))
 418 #define pd(a,b)             ((lzo_uint) ((a)-(b)))
 419
 420 LZO_EXTERN(lzo_ptr_t)
 421 __lzo_ptr_linear(const lzo_voidp ptr);
 422
 423 typedef union
 424 {
 425     char            a_char;
 426     unsigned char   a_uchar;
 427     short           a_short;
 428     unsigned short  a_ushort;
 429     int             a_int;
 430     unsigned int    a_uint;
 431     long            a_long;
 432     unsigned long   a_ulong;
 433     lzo_int         a_lzo_int;
 434     lzo_uint        a_lzo_uint;
 435     lzo_int32       a_lzo_int32;
 436     lzo_uint32      a_lzo_uint32;
 437     ptrdiff_t       a_ptrdiff_t;
 438     lzo_ptrdiff_t   a_lzo_ptrdiff_t;
 439     lzo_ptr_t       a_lzo_ptr_t;
 440     lzo_voidp       a_lzo_voidp;
 441     void *          a_void_p;
 442     lzo_bytep       a_lzo_bytep;
 443     lzo_bytepp      a_lzo_bytepp;
 444     lzo_uintp       a_lzo_uintp;
 445     lzo_uint *      a_lzo_uint_p;
 446     lzo_uint32p     a_lzo_uint32p;
 447     lzo_uint32 *    a_lzo_uint32_p;
 448     unsigned char * a_uchar_p;
 449     char *          a_char_p;
 450 }
 451 lzo_full_align_t;
 452
 453 #ifdef __cplusplus
 454 }
 455 #endif
 456
 457 #endif
 458
 459 #define LZO_DETERMINISTIC
 460
 461 #define LZO_DICT_USE_PTR
 462 #if defined(__LZO_DOS16) || defined(__LZO_WIN16) || defined(__LZO_STRICT_16BIT)
 463 #  undef LZO_DICT_USE_PTR
 464 #endif
 465
 466 #if defined(LZO_DICT_USE_PTR)
 467 #  define lzo_dict_t    const lzo_bytep
 468 #  define lzo_dict_p    lzo_dict_t __LZO_MMODEL *
 469 #else
 470 #  define lzo_dict_t    lzo_uint
 471 #  define lzo_dict_p    lzo_dict_t __LZO_MMODEL *
 472 #endif
 473
 474 #if !defined(lzo_moff_t)
 475 #define lzo_moff_t      lzo_uint
 476 #endif
 477
 478 #endif
 479
 480 LZO_PUBLIC(lzo_ptr_t)
 481 __lzo_ptr_linear(const lzo_voidp ptr)
 482 {
 483     lzo_ptr_t p;
 484
 485 #if defined(__LZO_DOS16) || defined(__LZO_WIN16)
 486     p = (((lzo_ptr_t)(_FP_SEG(ptr))) << (16 - __LZO_HShift)) + (_FP_OFF(ptr));
 487 #else
 488     p = PTR_LINEAR(ptr);
 489 #endif
 490
 491     return p;
 492 }
 493
 494 LZO_PUBLIC(unsigned)
 495 __lzo_align_gap(const lzo_voidp ptr, lzo_uint size)
 496 {
 497     lzo_ptr_t p, s, n;
 498
 499     assert(size > 0);
 500
 501     p = __lzo_ptr_linear(ptr);
 502     s = (lzo_ptr_t) (size - 1);
 503 #if 0
 504     assert((size & (size - 1)) == 0);
 505     n = ((p + s) & ~s) - p;
 506 #else
 507     n = (((p + s) / size) * size) - p;
 508 #endif
 509
 510     assert((long)n >= 0);
 511     assert(n <= s);
 512
 513     return (unsigned)n;
 514 }
 515
 516 #ifndef __LZO_UTIL_H
 517 #define __LZO_UTIL_H
 518
 519 #ifndef __LZO_CONF_H
 520 #endif
 521
 522 #ifdef __cplusplus
 523 extern "C" {
 524 #endif
 525
 526 #if 1 && defined(HAVE_MEMCPY)
 527 #if !defined(__LZO_DOS16) && !defined(__LZO_WIN16)
 528
 529 #define MEMCPY8_DS(dest,src,len) \
 530     memcpy(dest,src,len); \
 531     dest += len; \
 532     src += len
 533
 534 #endif
 535 #endif
 536
 537 #if 0 && !defined(MEMCPY8_DS)
 538
 539 #define MEMCPY8_DS(dest,src,len) \
 540     { do { \
 541         *dest++ = *src++; \
 542         *dest++ = *src++; \
 543         *dest++ = *src++; \
 544         *dest++ = *src++; \
 545         *dest++ = *src++; \
 546         *dest++ = *src++; \
 547         *dest++ = *src++; \
 548         *dest++ = *src++; \
 549         len -= 8; \
 550     } while (len > 0); }
 551
 552 #endif
 553
 554 #if !defined(MEMCPY8_DS)
 555
 556 #define MEMCPY8_DS(dest,src,len) \
 557     { register lzo_uint __l = (len) / 8; \
 558     do { \
 559         *dest++ = *src++; \
 560         *dest++ = *src++; \
 561         *dest++ = *src++; \
 562         *dest++ = *src++; \
 563         *dest++ = *src++; \
 564         *dest++ = *src++; \
 565         *dest++ = *src++; \
 566         *dest++ = *src++; \
 567     } while (--__l > 0); }
 568
 569 #endif
 570
 571 #define MEMCPY_DS(dest,src,len) \
 572     do *dest++ = *src++; \
 573     while (--len > 0)
 574
 575 #define MEMMOVE_DS(dest,src,len) \
 576     do *dest++ = *src++; \
 577     while (--len > 0)
 578
 579 #if 0 && defined(LZO_OPTIMIZE_GNUC_i386)
 580
 581 #define BZERO8_PTR(s,l,n) \
 582 __asm__ __volatile__( \
 583     "movl  %0,%%eax \n"             \
 584     "movl  %1,%%edi \n"             \
 585     "movl  %2,%%ecx \n"             \
 586     "cld \n"                        \
 587     "rep \n"                        \
 588     "stosl %%eax,(%%edi) \n"        \
 589     :               \
 590     :"g" (0),"g" (s),"g" (n)        \
 591     :"eax","edi","ecx", "memory", "cc" \
 592 )
 593
 594 #elif (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMSET)
 595
 596 #if 1
 597 #define BZERO8_PTR(s,l,n)   memset((s),0,(lzo_uint)(l)*(n))
 598 #else
 599 #define BZERO8_PTR(s,l,n)   memset((lzo_voidp)(s),0,(lzo_uint)(l)*(n))
 600 #endif
 601
 602 #else
 603
 604 #define BZERO8_PTR(s,l,n) \
 605     lzo_memset((lzo_voidp)(s),0,(lzo_uint)(l)*(n))
 606
 607 #endif
 608
 609 #if 0
 610 #if defined(__GNUC__) && defined(__i386__)
 611
 612 unsigned char lzo_rotr8(unsigned char value, int shift);
 613 extern __inline__ unsigned char lzo_rotr8(unsigned char value, int shift)
 614 {
 615     unsigned char result;
 616
 617     __asm__ __volatile__ ("movb %b1, %b0; rorb %b2, %b0"
 618                         : "=a"(result) : "g"(value), "c"(shift));
 619     return result;
 620 }
 621
 622 unsigned short lzo_rotr16(unsigned short value, int shift);
 623 extern __inline__ unsigned short lzo_rotr16(unsigned short value, int shift)
 624 {
 625     unsigned short result;
 626
 627     __asm__ __volatile__ ("movw %b1, %b0; rorw %b2, %b0"
 628                         : "=a"(result) : "g"(value), "c"(shift));
 629     return result;
 630 }
 631
 632 #endif
 633 #endif
 634
 635 #ifdef __cplusplus
 636 }
 637 #endif
 638
 639 #endif
 640
 641 LZO_PUBLIC(lzo_bool)
 642 lzo_assert(int expr)
 643 {
 644     return (expr) ? 1 : 0;
 645 }
 646
 647 /* If you use the LZO library in a product, you *must* keep this
 648  * copyright string in the executable of your product.
 649  */
 650
 651 const lzo_byte __lzo_copyright[] =
 652 #if !defined(__LZO_IN_MINLZO)
 653     LZO_VERSION_STRING;
 654 #else
 655     "\n\n\n"
 656     "LZO real-time data compression library.\n"
 657     "Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002 Markus Franz Xaver Johannes Oberhumer\n"
 658     "<markus.oberhumer@jk.uni-linz.ac.at>\n"
 659     "http://www.oberhumer.com/opensource/lzo/\n"
 660     "\n"
 661     "LZO version: v" LZO_VERSION_STRING ", " LZO_VERSION_DATE "\n"
 662     "LZO build date: " __DATE__ " " __TIME__ "\n\n"
 663     "LZO special compilation options:\n"
 664 #ifdef __cplusplus
 665     " __cplusplus\n"
 666 #endif
 667 #if defined(__PIC__)
 668     " __PIC__\n"
 669 #elif defined(__pic__)
 670     " __pic__\n"
 671 #endif
 672 #if (UINT_MAX < LZO_0xffffffffL)
 673     " 16BIT\n"
 674 #endif
 675 #if defined(__LZO_STRICT_16BIT)
 676     " __LZO_STRICT_16BIT\n"
 677 #endif
 678 #if (UINT_MAX > LZO_0xffffffffL)
 679     " UINT_MAX=" _LZO_MEXPAND(UINT_MAX) "\n"
 680 #endif
 681 #if (ULONG_MAX > LZO_0xffffffffL)
 682     " ULONG_MAX=" _LZO_MEXPAND(ULONG_MAX) "\n"
 683 #endif
 684 #if defined(LZO_BYTE_ORDER)
 685     " LZO_BYTE_ORDER=" _LZO_MEXPAND(LZO_BYTE_ORDER) "\n"
 686 #endif
 687 #if defined(LZO_UNALIGNED_OK_2)
 688     " LZO_UNALIGNED_OK_2\n"
 689 #endif
 690 #if defined(LZO_UNALIGNED_OK_4)
 691     " LZO_UNALIGNED_OK_4\n"
 692 #endif
 693 #if defined(LZO_ALIGNED_OK_4)
 694     " LZO_ALIGNED_OK_4\n"
 695 #endif
 696 #if defined(LZO_DICT_USE_PTR)
 697     " LZO_DICT_USE_PTR\n"
 698 #endif
 699 #if defined(__LZO_QUERY_COMPRESS)
 700     " __LZO_QUERY_COMPRESS\n"
 701 #endif
 702 #if defined(__LZO_QUERY_DECOMPRESS)
 703     " __LZO_QUERY_DECOMPRESS\n"
 704 #endif
 705 #if defined(__LZO_IN_MINILZO)
 706     " __LZO_IN_MINILZO\n"
 707 #endif
 708     "\n\n"
 709     "$Id: LZO " LZO_VERSION_STRING " built " __DATE__ " " __TIME__
 710 #if defined(__GNUC__) && defined(__VERSION__)
 711     " by gcc " __VERSION__
 712 #elif defined(__BORLANDC__)
 713     " by Borland C " _LZO_MEXPAND(__BORLANDC__)
 714 #elif defined(_MSC_VER)
 715     " by Microsoft C " _LZO_MEXPAND(_MSC_VER)
 716 #elif defined(__PUREC__)
 717     " by Pure C " _LZO_MEXPAND(__PUREC__)
 718 #elif defined(__SC__)
 719     " by Symantec C " _LZO_MEXPAND(__SC__)
 720 #elif defined(__TURBOC__)
 721     " by Turbo C " _LZO_MEXPAND(__TURBOC__)
 722 #elif defined(__WATCOMC__)
 723     " by Watcom C " _LZO_MEXPAND(__WATCOMC__)
 724 #endif
 725     " $\n"
 726     "$Copyright: LZO (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002 Markus Franz Xaver Johannes Oberhumer $\n";
 727 #endif
 728
 729 LZO_PUBLIC(const lzo_byte *)
 730 lzo_copyright(void)
 731 {
 732     return __lzo_copyright;
 733 }
 734
 735 LZO_PUBLIC(unsigned)
 736 lzo_version(void)
 737 {
 738     return LZO_VERSION;
 739 }
 740
 741 LZO_PUBLIC(const char *)
 742 lzo_version_string(void)
 743 {
 744     return LZO_VERSION_STRING;
 745 }
 746
 747 LZO_PUBLIC(const char *)
 748 lzo_version_date(void)
 749 {
 750     return LZO_VERSION_DATE;
 751 }
 752
 753 LZO_PUBLIC(const lzo_charp)
 754 _lzo_version_string(void)
 755 {
 756     return LZO_VERSION_STRING;
 757 }
 758
 759 LZO_PUBLIC(const lzo_charp)
 760 _lzo_version_date(void)
 761 {
 762     return LZO_VERSION_DATE;
 763 }
 764
 765 #define LZO_BASE 65521u
 766 #define LZO_NMAX 5552
 767
 768 #define LZO_DO1(buf,i)  {s1 += buf[i]; s2 += s1;}
 769 #define LZO_DO2(buf,i)  LZO_DO1(buf,i); LZO_DO1(buf,i+1);
 770 #define LZO_DO4(buf,i)  LZO_DO2(buf,i); LZO_DO2(buf,i+2);
 771 #define LZO_DO8(buf,i)  LZO_DO4(buf,i); LZO_DO4(buf,i+4);
 772 #define LZO_DO16(buf,i) LZO_DO8(buf,i); LZO_DO8(buf,i+8);
 773
 774 LZO_PUBLIC(lzo_uint32)
 775 lzo_adler32(lzo_uint32 adler, const lzo_byte *buf, lzo_uint len)
 776 {
 777     lzo_uint32 s1 = adler & 0xffff;
 778     lzo_uint32 s2 = (adler >> 16) & 0xffff;
 779     int k;
 780
 781     if (buf == NULL)
 782         return 1;
 783
 784     while (len > 0)
 785     {
 786         k = len < LZO_NMAX ? (int) len : LZO_NMAX;
 787         len -= k;
 788         if (k >= 16) do
 789         {
 790             LZO_DO16(buf,0);
 791             buf += 16;
 792             k -= 16;
 793         } while (k >= 16);
 794         if (k != 0) do
 795         {
 796             s1 += *buf++;
 797             s2 += s1;
 798         } while (--k > 0);
 799         s1 %= LZO_BASE;
 800         s2 %= LZO_BASE;
 801     }
 802     return (s2 << 16) | s1;
 803 }
 804
 805 LZO_PUBLIC(int)
 806 lzo_memcmp(const lzo_voidp s1, const lzo_voidp s2, lzo_uint len)
 807 {
 808 #if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMCMP)
 809     return memcmp(s1,s2,len);
 810 #else
 811     const lzo_byte *p1 = (const lzo_byte *) s1;
 812     const lzo_byte *p2 = (const lzo_byte *) s2;
 813     int d;
 814
 815     if (len > 0) do
 816     {
 817         d = *p1 - *p2;
 818         if (d != 0)
 819             return d;
 820         p1++;
 821         p2++;
 822     }
 823     while (--len > 0);
 824     return 0;
 825 #endif
 826 }
 827
 828 LZO_PUBLIC(lzo_voidp)
 829 lzo_memcpy(lzo_voidp dest, const lzo_voidp src, lzo_uint len)
 830 {
 831 #if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMCPY)
 832     return memcpy(dest,src,len);
 833 #else
 834     lzo_byte *p1 = (lzo_byte *) dest;
 835     const lzo_byte *p2 = (const lzo_byte *) src;
 836
 837     if (len <= 0 || p1 == p2)
 838         return dest;
 839     do
 840         *p1++ = *p2++;
 841     while (--len > 0);
 842     return dest;
 843 #endif
 844 }
 845
 846 LZO_PUBLIC(lzo_voidp)
 847 lzo_memmove(lzo_voidp dest, const lzo_voidp src, lzo_uint len)
 848 {
 849 #if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMMOVE)
 850     return memmove(dest,src,len);
 851 #else
 852     lzo_byte *p1 = (lzo_byte *) dest;
 853     const lzo_byte *p2 = (const lzo_byte *) src;
 854
 855     if (len <= 0 || p1 == p2)
 856         return dest;
 857
 858     if (p1 < p2)
 859     {
 860         do
 861             *p1++ = *p2++;
 862         while (--len > 0);
 863     }
 864     else
 865     {
 866         p1 += len;
 867         p2 += len;
 868         do
 869             *--p1 = *--p2;
 870         while (--len > 0);
 871     }
 872     return dest;
 873 #endif
 874 }
 875
 876 LZO_PUBLIC(lzo_voidp)
 877 lzo_memset(lzo_voidp s, int c, lzo_uint len)
 878 {
 879 #if (LZO_UINT_MAX <= SIZE_T_MAX) && defined(HAVE_MEMSET)
 880     return memset(s,c,len);
 881 #else
 882     lzo_byte *p = (lzo_byte *) s;
 883
 884     if (len > 0) do
 885         *p++ = LZO_BYTE(c);
 886     while (--len > 0);
 887     return s;
 888 #endif
 889 }
 890
 891 #if 0
 892 #  define IS_SIGNED(type)       (((type) (1ul << (8 * sizeof(type) - 1))) < 0)
 893 #  define IS_UNSIGNED(type)     (((type) (1ul << (8 * sizeof(type) - 1))) > 0)
 894 #else
 895 #  define IS_SIGNED(type)       (((type) (-1)) < ((type) 0))
 896 #  define IS_UNSIGNED(type)     (((type) (-1)) > ((type) 0))
 897 #endif
 898
 899 #define IS_POWER_OF_2(x)        (((x) & ((x) - 1)) == 0)
 900
 901 static lzo_bool schedule_insns_bug(void);
 902 static lzo_bool strength_reduce_bug(int *);
 903
 904 #if 0 || defined(LZO_DEBUG)
 905 #include <stdio.h>
 906 static lzo_bool __lzo_assert_fail(const char *s, unsigned line)
 907 {
 908 #if defined(__palmos__)
 909     printf("LZO assertion failed in line %u: '%s'\n",line,s);
 910 #else
 911     fprintf(stderr,"LZO assertion failed in line %u: '%s'\n",line,s);
 912 #endif
 913     return 0;
 914 }
 915 #  define __lzo_assert(x)   ((x) ? 1 : __lzo_assert_fail(#x,__LINE__))
 916 #else
 917 #  define __lzo_assert(x)   ((x) ? 1 : 0)
 918 #endif
 919
 920 #undef COMPILE_TIME_ASSERT
 921 #if 0
 922 #  define COMPILE_TIME_ASSERT(expr)     r &= __lzo_assert(expr)
 923 #else
 924 #  define COMPILE_TIME_ASSERT(expr)     LZO_COMPILE_TIME_ASSERT(expr)
 925 #endif
 926
 927 static lzo_bool basic_integral_check(void)
 928 {
 929     lzo_bool r = 1;
 930
 931     COMPILE_TIME_ASSERT(CHAR_BIT == 8);
 932     COMPILE_TIME_ASSERT(sizeof(char) == 1);
 933     COMPILE_TIME_ASSERT(sizeof(short) >= 2);
 934     COMPILE_TIME_ASSERT(sizeof(long) >= 4);
 935     COMPILE_TIME_ASSERT(sizeof(int) >= sizeof(short));
 936     COMPILE_TIME_ASSERT(sizeof(long) >= sizeof(int));
 937
 938     COMPILE_TIME_ASSERT(sizeof(lzo_uint) == sizeof(lzo_int));
 939     COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == sizeof(lzo_int32));
 940
 941     COMPILE_TIME_ASSERT(sizeof(lzo_uint32) >= 4);
 942     COMPILE_TIME_ASSERT(sizeof(lzo_uint32) >= sizeof(unsigned));
 943 #if defined(__LZO_STRICT_16BIT)
 944     COMPILE_TIME_ASSERT(sizeof(lzo_uint) == 2);
 945 #else
 946     COMPILE_TIME_ASSERT(sizeof(lzo_uint) >= 4);
 947     COMPILE_TIME_ASSERT(sizeof(lzo_uint) >= sizeof(unsigned));
 948 #endif
 949
 950 #if (USHRT_MAX == 65535u)
 951     COMPILE_TIME_ASSERT(sizeof(short) == 2);
 952 #elif (USHRT_MAX == LZO_0xffffffffL)
 953     COMPILE_TIME_ASSERT(sizeof(short) == 4);
 954 #elif (USHRT_MAX >= LZO_0xffffffffL)
 955     COMPILE_TIME_ASSERT(sizeof(short) > 4);
 956 #endif
 957 #if (UINT_MAX == 65535u)
 958     COMPILE_TIME_ASSERT(sizeof(int) == 2);
 959 #elif (UINT_MAX == LZO_0xffffffffL)
 960     COMPILE_TIME_ASSERT(sizeof(int) == 4);
 961 #elif (UINT_MAX >= LZO_0xffffffffL)
 962     COMPILE_TIME_ASSERT(sizeof(int) > 4);
 963 #endif
 964 #if (ULONG_MAX == 65535ul)
 965     COMPILE_TIME_ASSERT(sizeof(long) == 2);
 966 #elif (ULONG_MAX == LZO_0xffffffffL)
 967     COMPILE_TIME_ASSERT(sizeof(long) == 4);
 968 #elif (ULONG_MAX >= LZO_0xffffffffL)
 969     COMPILE_TIME_ASSERT(sizeof(long) > 4);
 970 #endif
 971
 972 #if defined(SIZEOF_UNSIGNED)
 973     COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED == sizeof(unsigned));
 974 #endif
 975 #if defined(SIZEOF_UNSIGNED_LONG)
 976     COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED_LONG == sizeof(unsigned long));
 977 #endif
 978 #if defined(SIZEOF_UNSIGNED_SHORT)
 979     COMPILE_TIME_ASSERT(SIZEOF_UNSIGNED_SHORT == sizeof(unsigned short));
 980 #endif
 981 #if !defined(__LZO_IN_MINILZO)
 982 #if defined(SIZEOF_SIZE_T)
 983     COMPILE_TIME_ASSERT(SIZEOF_SIZE_T == sizeof(size_t));
 984 #endif
 985 #endif
 986
 987     COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned char));
 988     COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned short));
 989     COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned));
 990     COMPILE_TIME_ASSERT(IS_UNSIGNED(unsigned long));
 991     COMPILE_TIME_ASSERT(IS_SIGNED(short));
 992     COMPILE_TIME_ASSERT(IS_SIGNED(int));
 993     COMPILE_TIME_ASSERT(IS_SIGNED(long));
 994
 995     COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_uint32));
 996     COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_uint));
 997     COMPILE_TIME_ASSERT(IS_SIGNED(lzo_int32));
 998     COMPILE_TIME_ASSERT(IS_SIGNED(lzo_int));
 999
1000     COMPILE_TIME_ASSERT(INT_MAX    == LZO_STYPE_MAX(sizeof(int)));
1001     COMPILE_TIME_ASSERT(UINT_MAX   == LZO_UTYPE_MAX(sizeof(unsigned)));
1002     COMPILE_TIME_ASSERT(LONG_MAX   == LZO_STYPE_MAX(sizeof(long)));
1003     COMPILE_TIME_ASSERT(ULONG_MAX  == LZO_UTYPE_MAX(sizeof(unsigned long)));
1004     COMPILE_TIME_ASSERT(SHRT_MAX   == LZO_STYPE_MAX(sizeof(short)));
1005     COMPILE_TIME_ASSERT(USHRT_MAX  == LZO_UTYPE_MAX(sizeof(unsigned short)));
1006     COMPILE_TIME_ASSERT(LZO_UINT32_MAX == LZO_UTYPE_MAX(sizeof(lzo_uint32)));
1007     COMPILE_TIME_ASSERT(LZO_UINT_MAX   == LZO_UTYPE_MAX(sizeof(lzo_uint)));
1008 #if !defined(__LZO_IN_MINILZO)
1009     COMPILE_TIME_ASSERT(SIZE_T_MAX     == LZO_UTYPE_MAX(sizeof(size_t)));
1010 #endif
1011
1012     r &= __lzo_assert(LZO_BYTE(257) == 1);
1013
1014     return r;
1015 }
1016
1017 static lzo_bool basic_ptr_check(void)
1018 {
1019     lzo_bool r = 1;
1020
1021     COMPILE_TIME_ASSERT(sizeof(char *) >= sizeof(int));
1022     COMPILE_TIME_ASSERT(sizeof(lzo_byte *) >= sizeof(char *));
1023
1024     COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_byte *));
1025     COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_voidpp));
1026     COMPILE_TIME_ASSERT(sizeof(lzo_voidp) == sizeof(lzo_bytepp));
1027     COMPILE_TIME_ASSERT(sizeof(lzo_voidp) >= sizeof(lzo_uint));
1028
1029     COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) == sizeof(lzo_voidp));
1030     COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) == sizeof(lzo_sptr_t));
1031     COMPILE_TIME_ASSERT(sizeof(lzo_ptr_t) >= sizeof(lzo_uint));
1032
1033     COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= 4);
1034     COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= sizeof(ptrdiff_t));
1035
1036     COMPILE_TIME_ASSERT(sizeof(ptrdiff_t) >= sizeof(size_t));
1037     COMPILE_TIME_ASSERT(sizeof(lzo_ptrdiff_t) >= sizeof(lzo_uint));
1038
1039 #if defined(SIZEOF_CHAR_P)
1040     COMPILE_TIME_ASSERT(SIZEOF_CHAR_P == sizeof(char *));
1041 #endif
1042 #if defined(SIZEOF_PTRDIFF_T)
1043     COMPILE_TIME_ASSERT(SIZEOF_PTRDIFF_T == sizeof(ptrdiff_t));
1044 #endif
1045
1046     COMPILE_TIME_ASSERT(IS_SIGNED(ptrdiff_t));
1047     COMPILE_TIME_ASSERT(IS_UNSIGNED(size_t));
1048     COMPILE_TIME_ASSERT(IS_SIGNED(lzo_ptrdiff_t));
1049     COMPILE_TIME_ASSERT(IS_SIGNED(lzo_sptr_t));
1050     COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_ptr_t));
1051     COMPILE_TIME_ASSERT(IS_UNSIGNED(lzo_moff_t));
1052
1053     return r;
1054 }
1055
1056 static lzo_bool ptr_check(void)
1057 {
1058     lzo_bool r = 1;
1059     int i;
1060     char _wrkmem[10 * sizeof(lzo_byte *) + sizeof(lzo_full_align_t)];
1061     lzo_bytep wrkmem;
1062     lzo_bytepp dict;
1063     unsigned char x[4 * sizeof(lzo_full_align_t)];
1064     long d;
1065     lzo_full_align_t a;
1066     lzo_full_align_t u;
1067
1068     for (i = 0; i < (int) sizeof(x); i++)
1069         x[i] = LZO_BYTE(i);
1070
1071     wrkmem = LZO_PTR_ALIGN_UP((lzo_byte *)_wrkmem,sizeof(lzo_full_align_t));
1072
1073 #if 0
1074     dict = (lzo_bytepp) wrkmem;
1075 #else
1076
1077     u.a_lzo_bytep = wrkmem; dict = u.a_lzo_bytepp;
1078 #endif
1079
1080     d = (long) ((const lzo_bytep) dict - (const lzo_bytep) _wrkmem);
1081     r &= __lzo_assert(d >= 0);
1082     r &= __lzo_assert(d < (long) sizeof(lzo_full_align_t));
1083
1084     memset(&a,0,sizeof(a));
1085     r &= __lzo_assert(a.a_lzo_voidp == NULL);
1086
1087     memset(&a,0xff,sizeof(a));
1088     r &= __lzo_assert(a.a_ushort == USHRT_MAX);
1089     r &= __lzo_assert(a.a_uint == UINT_MAX);
1090     r &= __lzo_assert(a.a_ulong == ULONG_MAX);
1091     r &= __lzo_assert(a.a_lzo_uint == LZO_UINT_MAX);
1092     r &= __lzo_assert(a.a_lzo_uint32 == LZO_UINT32_MAX);
1093
1094     if (r == 1)
1095     {
1096         for (i = 0; i < 8; i++)
1097             r &= __lzo_assert((const lzo_voidp) (&dict[i]) == (const lzo_voidp) (&wrkmem[i * sizeof(lzo_byte *)]));
1098     }
1099
1100     memset(&a,0,sizeof(a));
1101     r &= __lzo_assert(a.a_char_p == NULL);
1102     r &= __lzo_assert(a.a_lzo_bytep == NULL);
1103     r &= __lzo_assert(NULL == (void *)0);
1104     if (r == 1)
1105     {
1106         for (i = 0; i < 10; i++)
1107             dict[i] = wrkmem;
1108         BZERO8_PTR(dict+1,sizeof(dict[0]),8);
1109         r &= __lzo_assert(dict[0] == wrkmem);
1110         for (i = 1; i < 9; i++)
1111             r &= __lzo_assert(dict[i] == NULL);
1112         r &= __lzo_assert(dict[9] == wrkmem);
1113     }
1114
1115     if (r == 1)
1116     {
1117         unsigned k = 1;
1118         const unsigned n = (unsigned) sizeof(lzo_uint32);
1119         lzo_byte *p0;
1120         lzo_byte *p1;
1121
1122         k += __lzo_align_gap(&x[k],n);
1123         p0 = (lzo_bytep) &x[k];
1124 #if defined(PTR_LINEAR)
1125         r &= __lzo_assert((PTR_LINEAR(p0) & (n-1)) == 0);
1126 #else
1127         r &= __lzo_assert(n == 4);
1128         r &= __lzo_assert(PTR_ALIGNED_4(p0));
1129 #endif
1130
1131         r &= __lzo_assert(k >= 1);
1132         p1 = (lzo_bytep) &x[1];
1133         r &= __lzo_assert(PTR_GE(p0,p1));
1134
1135         r &= __lzo_assert(k < 1+n);
1136         p1 = (lzo_bytep) &x[1+n];
1137         r &= __lzo_assert(PTR_LT(p0,p1));
1138
1139         if (r == 1)
1140         {
1141             lzo_uint32 v0, v1;
1142 #if 0
1143             v0 = * (lzo_uint32 *) &x[k];
1144             v1 = * (lzo_uint32 *) &x[k+n];
1145 #else
1146
1147             u.a_uchar_p = &x[k];
1148             v0 = *u.a_lzo_uint32_p;
1149             u.a_uchar_p = &x[k+n];
1150             v1 = *u.a_lzo_uint32_p;
1151 #endif
1152             r &= __lzo_assert(v0 > 0);
1153             r &= __lzo_assert(v1 > 0);
1154         }
1155     }
1156
1157     return r;
1158 }
1159
1160 LZO_PUBLIC(int)
1161 _lzo_config_check(void)
1162 {
1163     lzo_bool r = 1;
1164     int i;
1165     union {
1166         lzo_uint32 a;
1167         unsigned short b;
1168         lzo_uint32 aa[4];
1169         unsigned char x[4*sizeof(lzo_full_align_t)];
1170     } u;
1171
1172     COMPILE_TIME_ASSERT( (int) ((unsigned char) ((signed char) -1)) == 255);
1173     COMPILE_TIME_ASSERT( (((unsigned char)128) << (int)(8*sizeof(int)-8)) < 0);
1174
1175 #if 0
1176     r &= __lzo_assert((const void *)&u == (const void *)&u.a);
1177     r &= __lzo_assert((const void *)&u == (const void *)&u.b);
1178     r &= __lzo_assert((const void *)&u == (const void *)&u.x[0]);
1179     r &= __lzo_assert((const void *)&u == (const void *)&u.aa[0]);
1180 #endif
1181
1182     r &= basic_integral_check();
1183     r &= basic_ptr_check();
1184     if (r != 1)
1185         return LZO_E_ERROR;
1186
1187     u.a = 0; u.b = 0;
1188     for (i = 0; i < (int) sizeof(u.x); i++)
1189         u.x[i] = LZO_BYTE(i);
1190
1191 #if defined(LZO_BYTE_ORDER)
1192     if (r == 1)
1193     {
1194 #  if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
1195         lzo_uint32 a = (lzo_uint32) (u.a & LZO_0xffffffffL);
1196         unsigned short b = (unsigned short) (u.b & 0xffff);
1197         r &= __lzo_assert(a == 0x03020100L);
1198         r &= __lzo_assert(b == 0x0100);
1199 #  elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
1200         lzo_uint32 a = u.a >> (8 * sizeof(u.a) - 32);
1201         unsigned short b = u.b >> (8 * sizeof(u.b) - 16);
1202         r &= __lzo_assert(a == 0x00010203L);
1203         r &= __lzo_assert(b == 0x0001);
1204 #  else
1205 #    error "invalid LZO_BYTE_ORDER"
1206 #  endif
1207     }
1208 #endif
1209
1210 #if defined(LZO_UNALIGNED_OK_2)
1211     COMPILE_TIME_ASSERT(sizeof(short) == 2);
1212     if (r == 1)
1213     {
1214         unsigned short b[4];
1215
1216         for (i = 0; i < 4; i++)
1217             b[i] = * (const unsigned short *) &u.x[i];
1218
1219 #  if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
1220         r &= __lzo_assert(b[0] == 0x0100);
1221         r &= __lzo_assert(b[1] == 0x0201);
1222         r &= __lzo_assert(b[2] == 0x0302);
1223         r &= __lzo_assert(b[3] == 0x0403);
1224 #  elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
1225         r &= __lzo_assert(b[0] == 0x0001);
1226         r &= __lzo_assert(b[1] == 0x0102);
1227         r &= __lzo_assert(b[2] == 0x0203);
1228         r &= __lzo_assert(b[3] == 0x0304);
1229 #  endif
1230     }
1231 #endif
1232
1233 #if defined(LZO_UNALIGNED_OK_4)
1234     COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == 4);
1235     if (r == 1)
1236     {
1237         lzo_uint32 a[4];
1238
1239         for (i = 0; i < 4; i++)
1240             a[i] = * (const lzo_uint32 *) &u.x[i];
1241
1242 #  if (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
1243         r &= __lzo_assert(a[0] == 0x03020100L);
1244         r &= __lzo_assert(a[1] == 0x04030201L);
1245         r &= __lzo_assert(a[2] == 0x05040302L);
1246         r &= __lzo_assert(a[3] == 0x06050403L);
1247 #  elif (LZO_BYTE_ORDER == LZO_BIG_ENDIAN)
1248         r &= __lzo_assert(a[0] == 0x00010203L);
1249         r &= __lzo_assert(a[1] == 0x01020304L);
1250         r &= __lzo_assert(a[2] == 0x02030405L);
1251         r &= __lzo_assert(a[3] == 0x03040506L);
1252 #  endif
1253     }
1254 #endif
1255
1256 #if defined(LZO_ALIGNED_OK_4)
1257     COMPILE_TIME_ASSERT(sizeof(lzo_uint32) == 4);
1258 #endif
1259
1260     COMPILE_TIME_ASSERT(lzo_sizeof_dict_t == sizeof(lzo_dict_t));
1261
1262 #if defined(__LZO_IN_MINLZO)
1263     if (r == 1)
1264     {
1265         lzo_uint32 adler;
1266         adler = lzo_adler32(0, NULL, 0);
1267         adler = lzo_adler32(adler, lzo_copyright(), 200);
1268         r &= __lzo_assert(adler == 0xc76f1751L);
1269     }
1270 #endif
1271
1272     if (r == 1)
1273     {
1274         r &= __lzo_assert(!schedule_insns_bug());
1275     }
1276
1277     if (r == 1)
1278     {
1279         static int x[3];
1280         static unsigned xn = 3;
1281         register unsigned j;
1282
1283         for (j = 0; j < xn; j++)
1284             x[j] = (int)j - 3;
1285         r &= __lzo_assert(!strength_reduce_bug(x));
1286     }
1287
1288     if (r == 1)
1289     {
1290         r &= ptr_check();
1291     }
1292
1293     return r == 1 ? LZO_E_OK : LZO_E_ERROR;
1294 }
1295
1296 static lzo_bool schedule_insns_bug(void)
1297 {
1298 #if defined(__LZO_CHECKER)
1299     return 0;
1300 #else
1301     const int clone[] = {1, 2, 0};
1302     const int *q;
1303     q = clone;
1304     return (*q) ? 0 : 1;
1305 #endif
1306 }
1307
1308 static lzo_bool strength_reduce_bug(int *x)
1309 {
1310     return x[0] != -3 || x[1] != -2 || x[2] != -1;
1311 }
1312
1313 #undef COMPILE_TIME_ASSERT
1314
1315 int __lzo_init_done = 0;
1316
1317 LZO_PUBLIC(int)
1318 __lzo_init2(unsigned v, int s1, int s2, int s3, int s4, int s5,
1319                         int s6, int s7, int s8, int s9)
1320 {
1321     int r;
1322
1323     __lzo_init_done = 1;
1324
1325     if (v == 0)
1326         return LZO_E_ERROR;
1327
1328     r = (s1 == -1 || s1 == (int) sizeof(short)) &&
1329         (s2 == -1 || s2 == (int) sizeof(int)) &&
1330         (s3 == -1 || s3 == (int) sizeof(long)) &&
1331         (s4 == -1 || s4 == (int) sizeof(lzo_uint32)) &&
1332         (s5 == -1 || s5 == (int) sizeof(lzo_uint)) &&
1333         (s6 == -1 || s6 == (int) lzo_sizeof_dict_t) &&
1334         (s7 == -1 || s7 == (int) sizeof(char *)) &&
1335         (s8 == -1 || s8 == (int) sizeof(lzo_voidp)) &&
1336         (s9 == -1 || s9 == (int) sizeof(lzo_compress_t));
1337     if (!r)
1338         return LZO_E_ERROR;
1339
1340     r = _lzo_config_check();
1341     if (r != LZO_E_OK)
1342         return r;
1343
1344     return r;
1345 }
1346
1347 #if !defined(__LZO_IN_MINILZO)
1348
1349 LZO_EXTERN(int)
1350 __lzo_init(unsigned v,int s1,int s2,int s3,int s4,int s5,int s6,int s7);
1351
1352 LZO_PUBLIC(int)
1353 __lzo_init(unsigned v,int s1,int s2,int s3,int s4,int s5,int s6,int s7)
1354 {
1355     if (v == 0 || v > 0x1010)
1356         return LZO_E_ERROR;
1357     return __lzo_init2(v,s1,s2,s3,s4,s5,-1,-1,s6,s7);
1358 }
1359
1360 #endif
1361
1362 #define do_compress         _lzo1x_1_do_compress
1363
1364 #define LZO_NEED_DICT_H
1365 #define D_BITS          14
1366 #define D_INDEX1(d,p)       d = DM((0x21*DX3(p,5,5,6)) >> 5)
1367 #define D_INDEX2(d,p)       d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
1368
1369 #ifndef __LZO_CONFIG1X_H
1370 #define __LZO_CONFIG1X_H
1371
1372 #if !defined(LZO1X) && !defined(LZO1Y) && !defined(LZO1Z)
1373 #  define LZO1X
1374 #endif
1375
1376 #if !defined(__LZO_IN_MINILZO)
1377 #include <lzo1x.h>
1378 #endif
1379
1380 #define LZO_EOF_CODE
1381 #undef LZO_DETERMINISTIC
1382
1383 #define M1_MAX_OFFSET   0x0400
1384 #ifndef M2_MAX_OFFSET
1385 #define M2_MAX_OFFSET   0x0800
1386 #endif
1387 #define M3_MAX_OFFSET   0x4000
1388 #define M4_MAX_OFFSET   0xbfff
1389
1390 #define MX_MAX_OFFSET   (M1_MAX_OFFSET + M2_MAX_OFFSET)
1391
1392 #define M1_MIN_LEN      2
1393 #define M1_MAX_LEN      2
1394 #define M2_MIN_LEN      3
1395 #ifndef M2_MAX_LEN
1396 #define M2_MAX_LEN      8
1397 #endif
1398 #define M3_MIN_LEN      3
1399 #define M3_MAX_LEN      33
1400 #define M4_MIN_LEN      3
1401 #define M4_MAX_LEN      9
1402
1403 #define M1_MARKER       0
1404 #define M2_MARKER       64
1405 #define M3_MARKER       32
1406 #define M4_MARKER       16
1407
1408 #ifndef MIN_LOOKAHEAD
1409 #define MIN_LOOKAHEAD       (M2_MAX_LEN + 1)
1410 #endif
1411
1412 #if defined(LZO_NEED_DICT_H)
1413
1414 #ifndef LZO_HASH
1415 #define LZO_HASH            LZO_HASH_LZO_INCREMENTAL_B
1416 #endif
1417 #define DL_MIN_LEN          M2_MIN_LEN
1418
1419 #ifndef __LZO_DICT_H
1420 #define __LZO_DICT_H
1421
1422 #ifdef __cplusplus
1423 extern "C" {
1424 #endif
1425
1426 #if !defined(D_BITS) && defined(DBITS)
1427 #  define D_BITS        DBITS
1428 #endif
1429 #if !defined(D_BITS)
1430 #  error "D_BITS is not defined"
1431 #endif
1432 #if (D_BITS < 16)
1433 #  define D_SIZE        LZO_SIZE(D_BITS)
1434 #  define D_MASK        LZO_MASK(D_BITS)
1435 #else
1436 #  define D_SIZE        LZO_USIZE(D_BITS)
1437 #  define D_MASK        LZO_UMASK(D_BITS)
1438 #endif
1439 #define D_HIGH          ((D_MASK >> 1) + 1)
1440
1441 #if !defined(DD_BITS)
1442 #  define DD_BITS       0
1443 #endif
1444 #define DD_SIZE         LZO_SIZE(DD_BITS)
1445 #define DD_MASK         LZO_MASK(DD_BITS)
1446
1447 #if !defined(DL_BITS)
1448 #  define DL_BITS       (D_BITS - DD_BITS)
1449 #endif
1450 #if (DL_BITS < 16)
1451 #  define DL_SIZE       LZO_SIZE(DL_BITS)
1452 #  define DL_MASK       LZO_MASK(DL_BITS)
1453 #else
1454 #  define DL_SIZE       LZO_USIZE(DL_BITS)
1455 #  define DL_MASK       LZO_UMASK(DL_BITS)
1456 #endif
1457
1458 #if (D_BITS != DL_BITS + DD_BITS)
1459 #  error "D_BITS does not match"
1460 #endif
1461 #if (D_BITS < 8 || D_BITS > 18)
1462 #  error "invalid D_BITS"
1463 #endif
1464 #if (DL_BITS < 8 || DL_BITS > 20)
1465 #  error "invalid DL_BITS"
1466 #endif
1467 #if (DD_BITS < 0 || DD_BITS > 6)
1468 #  error "invalid DD_BITS"
1469 #endif
1470
1471 #if !defined(DL_MIN_LEN)
1472 #  define DL_MIN_LEN    3
1473 #endif
1474 #if !defined(DL_SHIFT)
1475 #  define DL_SHIFT      ((DL_BITS + (DL_MIN_LEN - 1)) / DL_MIN_LEN)
1476 #endif
1477
1478 #define LZO_HASH_GZIP                   1
1479 #define LZO_HASH_GZIP_INCREMENTAL       2
1480 #define LZO_HASH_LZO_INCREMENTAL_A      3
1481 #define LZO_HASH_LZO_INCREMENTAL_B      4
1482
1483 #if !defined(LZO_HASH)
1484 #  error "choose a hashing strategy"
1485 #endif
1486
1487 #if (DL_MIN_LEN == 3)
1488 #  define _DV2_A(p,shift1,shift2) \
1489         (((( (lzo_uint32)((p)[0]) << shift1) ^ (p)[1]) << shift2) ^ (p)[2])
1490 #  define _DV2_B(p,shift1,shift2) \
1491         (((( (lzo_uint32)((p)[2]) << shift1) ^ (p)[1]) << shift2) ^ (p)[0])
1492 #  define _DV3_B(p,shift1,shift2,shift3) \
1493         ((_DV2_B((p)+1,shift1,shift2) << (shift3)) ^ (p)[0])
1494 #elif (DL_MIN_LEN == 2)
1495 #  define _DV2_A(p,shift1,shift2) \
1496         (( (lzo_uint32)(p[0]) << shift1) ^ p[1])
1497 #  define _DV2_B(p,shift1,shift2) \
1498         (( (lzo_uint32)(p[1]) << shift1) ^ p[2])
1499 #else
1500 #  error "invalid DL_MIN_LEN"
1501 #endif
1502 #define _DV_A(p,shift)      _DV2_A(p,shift,shift)
1503 #define _DV_B(p,shift)      _DV2_B(p,shift,shift)
1504 #define DA2(p,s1,s2) \
1505         (((((lzo_uint32)((p)[2]) << (s2)) + (p)[1]) << (s1)) + (p)[0])
1506 #define DS2(p,s1,s2) \
1507         (((((lzo_uint32)((p)[2]) << (s2)) - (p)[1]) << (s1)) - (p)[0])
1508 #define DX2(p,s1,s2) \
1509         (((((lzo_uint32)((p)[2]) << (s2)) ^ (p)[1]) << (s1)) ^ (p)[0])
1510 #define DA3(p,s1,s2,s3) ((DA2((p)+1,s2,s3) << (s1)) + (p)[0])
1511 #define DS3(p,s1,s2,s3) ((DS2((p)+1,s2,s3) << (s1)) - (p)[0])
1512 #define DX3(p,s1,s2,s3) ((DX2((p)+1,s2,s3) << (s1)) ^ (p)[0])
1513 #define DMS(v,s)        ((lzo_uint) (((v) & (D_MASK >> (s))) << (s)))
1514 #define DM(v)           DMS(v,0)
1515
1516 #if (LZO_HASH == LZO_HASH_GZIP)
1517 #  define _DINDEX(dv,p)     (_DV_A((p),DL_SHIFT))
1518
1519 #elif (LZO_HASH == LZO_HASH_GZIP_INCREMENTAL)
1520 #  define __LZO_HASH_INCREMENTAL
1521 #  define DVAL_FIRST(dv,p)  dv = _DV_A((p),DL_SHIFT)
1522 #  define DVAL_NEXT(dv,p)   dv = (((dv) << DL_SHIFT) ^ p[2])
1523 #  define _DINDEX(dv,p)     (dv)
1524 #  define DVAL_LOOKAHEAD    DL_MIN_LEN
1525
1526 #elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_A)
1527 #  define __LZO_HASH_INCREMENTAL
1528 #  define DVAL_FIRST(dv,p)  dv = _DV_A((p),5)
1529 #  define DVAL_NEXT(dv,p) \
1530                 dv ^= (lzo_uint32)(p[-1]) << (2*5); dv = (((dv) << 5) ^ p[2])
1531 #  define _DINDEX(dv,p)     ((0x9f5f * (dv)) >> 5)
1532 #  define DVAL_LOOKAHEAD    DL_MIN_LEN
1533
1534 #elif (LZO_HASH == LZO_HASH_LZO_INCREMENTAL_B)
1535 #  define __LZO_HASH_INCREMENTAL
1536 #  define DVAL_FIRST(dv,p)  dv = _DV_B((p),5)
1537 #  define DVAL_NEXT(dv,p) \
1538                 dv ^= p[-1]; dv = (((dv) >> 5) ^ ((lzo_uint32)(p[2]) << (2*5)))
1539 #  define _DINDEX(dv,p)     ((0x9f5f * (dv)) >> 5)
1540 #  define DVAL_LOOKAHEAD    DL_MIN_LEN
1541
1542 #else
1543 #  error "choose a hashing strategy"
1544 #endif
1545
1546 #ifndef DINDEX
1547 #define DINDEX(dv,p)        ((lzo_uint)((_DINDEX(dv,p)) & DL_MASK) << DD_BITS)
1548 #endif
1549 #if !defined(DINDEX1) && defined(D_INDEX1)
1550 #define DINDEX1             D_INDEX1
1551 #endif
1552 #if !defined(DINDEX2) && defined(D_INDEX2)
1553 #define DINDEX2             D_INDEX2
1554 #endif
1555
1556 #if !defined(__LZO_HASH_INCREMENTAL)
1557 #  define DVAL_FIRST(dv,p)  ((void) 0)
1558 #  define DVAL_NEXT(dv,p)   ((void) 0)
1559 #  define DVAL_LOOKAHEAD    0
1560 #endif
1561
1562 #if !defined(DVAL_ASSERT)
1563 #if defined(__LZO_HASH_INCREMENTAL) && !defined(NDEBUG)
1564 static void DVAL_ASSERT(lzo_uint32 dv, const lzo_byte *p)
1565 {
1566     lzo_uint32 df;
1567     DVAL_FIRST(df,(p));
1568     assert(DINDEX(dv,p) == DINDEX(df,p));
1569 }
1570 #else
1571 #  define DVAL_ASSERT(dv,p) ((void) 0)
1572 #endif
1573 #endif
1574
1575 #if defined(LZO_DICT_USE_PTR)
1576 #  define DENTRY(p,in)                          (p)
1577 #  define GINDEX(m_pos,m_off,dict,dindex,in)    m_pos = dict[dindex]
1578 #else
1579 #  define DENTRY(p,in)                          ((lzo_uint) ((p)-(in)))
1580 #  define GINDEX(m_pos,m_off,dict,dindex,in)    m_off = dict[dindex]
1581 #endif
1582
1583 #if (DD_BITS == 0)
1584
1585 #  define UPDATE_D(dict,drun,dv,p,in)       dict[ DINDEX(dv,p) ] = DENTRY(p,in)
1586 #  define UPDATE_I(dict,drun,index,p,in)    dict[index] = DENTRY(p,in)
1587 #  define UPDATE_P(ptr,drun,p,in)           (ptr)[0] = DENTRY(p,in)
1588
1589 #else
1590
1591 #  define UPDATE_D(dict,drun,dv,p,in)   \
1592         dict[ DINDEX(dv,p) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
1593 #  define UPDATE_I(dict,drun,index,p,in)    \
1594         dict[ (index) + drun++ ] = DENTRY(p,in); drun &= DD_MASK
1595 #  define UPDATE_P(ptr,drun,p,in)   \
1596         (ptr) [ drun++ ] = DENTRY(p,in); drun &= DD_MASK
1597
1598 #endif
1599
1600 #if defined(LZO_DICT_USE_PTR)
1601
1602 #define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
1603         (m_pos == NULL || (m_off = (lzo_moff_t) (ip - m_pos)) > max_offset)
1604
1605 #define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
1606     (BOUNDS_CHECKING_OFF_IN_EXPR( \
1607         (PTR_LT(m_pos,in) || \
1608          (m_off = (lzo_moff_t) PTR_DIFF(ip,m_pos)) <= 0 || \
1609           m_off > max_offset) ))
1610
1611 #else
1612
1613 #define LZO_CHECK_MPOS_DET(m_pos,m_off,in,ip,max_offset) \
1614         (m_off == 0 || \
1615          ((m_off = (lzo_moff_t) ((ip)-(in)) - m_off) > max_offset) || \
1616          (m_pos = (ip) - (m_off), 0) )
1617
1618 #define LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,max_offset) \
1619         ((lzo_moff_t) ((ip)-(in)) <= m_off || \
1620          ((m_off = (lzo_moff_t) ((ip)-(in)) - m_off) > max_offset) || \
1621          (m_pos = (ip) - (m_off), 0) )
1622
1623 #endif
1624
1625 #if defined(LZO_DETERMINISTIC)
1626 #  define LZO_CHECK_MPOS    LZO_CHECK_MPOS_DET
1627 #else
1628 #  define LZO_CHECK_MPOS    LZO_CHECK_MPOS_NON_DET
1629 #endif
1630
1631 #ifdef __cplusplus
1632 }
1633 #endif
1634
1635 #endif
1636
1637 #endif
1638
1639 #endif
1640
1641 #define DO_COMPRESS     lzo1x_1_compress
1642
1643 static
1644 lzo_uint do_compress     ( const lzo_byte *in , lzo_uint  in_len,
1645                                  lzo_byte *out, lzo_uintp out_len,
1646                                  lzo_voidp wrkmem )
1647 {
1648 #if 0 && defined(__GNUC__) && defined(__i386__)
1649     register const lzo_byte *ip __asm__("%esi");
1650 #else
1651     register const lzo_byte *ip;
1652 #endif
1653     lzo_byte *op;
1654     const lzo_byte * const in_end = in + in_len;
1655     const lzo_byte * const ip_end = in + in_len - M2_MAX_LEN - 5;
1656     const lzo_byte *ii;
1657     lzo_dict_p const dict = (lzo_dict_p) wrkmem;
1658
1659     op = out;
1660     ip = in;
1661     ii = ip;
1662
1663     ip += 4;
1664     for (;;)
1665     {
1666 #if 0 && defined(__GNUC__) && defined(__i386__)
1667         register const lzo_byte *m_pos __asm__("%edi");
1668 #else
1669         register const lzo_byte *m_pos;
1670 #endif
1671         lzo_moff_t m_off;
1672         lzo_uint m_len;
1673         lzo_uint dindex;
1674
1675         DINDEX1(dindex,ip);
1676         GINDEX(m_pos,m_off,dict,dindex,in);
1677         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
1678             goto literal;
1679 #if 1
1680         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
1681             goto try_match;
1682         DINDEX2(dindex,ip);
1683 #endif
1684         GINDEX(m_pos,m_off,dict,dindex,in);
1685         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
1686             goto literal;
1687         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
1688             goto try_match;
1689         goto literal;
1690
1691 try_match:
1692 #if 1 && defined(LZO_UNALIGNED_OK_2)
1693         if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
1694 #else
1695         if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
1696 #endif
1697         {
1698         }
1699         else
1700         {
1701             if (m_pos[2] == ip[2])
1702             {
1703 #if 0
1704                 if (m_off <= M2_MAX_OFFSET)
1705                     goto match;
1706                 if (lit <= 3)
1707                     goto match;
1708                 if (lit == 3)
1709                 {
1710                     assert(op - 2 > out); op[-2] |= LZO_BYTE(3);
1711                     *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
1712                     goto code_match;
1713                 }
1714                 if (m_pos[3] == ip[3])
1715 #endif
1716                     goto match;
1717             }
1718             else
1719             {
1720 #if 0
1721 #if 0
1722                 if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3)
1723 #else
1724                 if (m_off <= M1_MAX_OFFSET && lit == 3)
1725 #endif
1726                 {
1727                     register lzo_uint t;
1728
1729                     t = lit;
1730                     assert(op - 2 > out); op[-2] |= LZO_BYTE(t);
1731                     do *op++ = *ii++; while (--t > 0);
1732                     assert(ii == ip);
1733                     m_off -= 1;
1734                     *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
1735                     *op++ = LZO_BYTE(m_off >> 2);
1736                     ip += 2;
1737                     goto match_done;
1738                 }
1739 #endif
1740             }
1741         }
1742
1743 literal:
1744         UPDATE_I(dict,0,dindex,ip,in);
1745         ++ip;
1746         if (ip >= ip_end)
1747             break;
1748         continue;
1749
1750 match:
1751         UPDATE_I(dict,0,dindex,ip,in);
1752         if (pd(ip,ii) > 0)
1753         {
1754             register lzo_uint t = pd(ip,ii);
1755
1756             if (t <= 3)
1757             {
1758                 assert(op - 2 > out);
1759                 op[-2] |= LZO_BYTE(t);
1760             }
1761             else if (t <= 18)
1762                 *op++ = LZO_BYTE(t - 3);
1763             else
1764             {
1765                 register lzo_uint tt = t - 18;
1766
1767                 *op++ = 0;
1768                 while (tt > 255)
1769                 {
1770                     tt -= 255;
1771                     *op++ = 0;
1772                 }
1773                 assert(tt > 0);
1774                 *op++ = LZO_BYTE(tt);
1775             }
1776             do *op++ = *ii++; while (--t > 0);
1777         }
1778
1779         assert(ii == ip);
1780         ip += 3;
1781         if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ ||
1782             m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++
1783 #ifdef LZO1Y
1784             || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++
1785             || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++
1786 #endif
1787            )
1788         {
1789             --ip;
1790             m_len = ip - ii;
1791             assert(m_len >= 3); assert(m_len <= M2_MAX_LEN);
1792
1793             if (m_off <= M2_MAX_OFFSET)
1794             {
1795                 m_off -= 1;
1796 #if defined(LZO1X)
1797                 *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
1798                 *op++ = LZO_BYTE(m_off >> 3);
1799 #elif defined(LZO1Y)
1800                 *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
1801                 *op++ = LZO_BYTE(m_off >> 2);
1802 #endif
1803             }
1804             else if (m_off <= M3_MAX_OFFSET)
1805             {
1806                 m_off -= 1;
1807                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
1808                 goto m3_m4_offset;
1809             }
1810             else
1811 #if defined(LZO1X)
1812             {
1813                 m_off -= 0x4000;
1814                 assert(m_off > 0); assert(m_off <= 0x7fff);
1815                 *op++ = LZO_BYTE(M4_MARKER |
1816                                  ((m_off & 0x4000) >> 11) | (m_len - 2));
1817                 goto m3_m4_offset;
1818             }
1819 #elif defined(LZO1Y)
1820                 goto m4_match;
1821 #endif
1822         }
1823         else
1824         {
1825             {
1826                 const lzo_byte *end = in_end;
1827                 const lzo_byte *m = m_pos + M2_MAX_LEN + 1;
1828                 while (ip < end && *m == *ip)
1829                     m++, ip++;
1830                 m_len = (ip - ii);
1831             }
1832             assert(m_len > M2_MAX_LEN);
1833
1834             if (m_off <= M3_MAX_OFFSET)
1835             {
1836                 m_off -= 1;
1837                 if (m_len <= 33)
1838                     *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
1839                 else
1840                 {
1841                     m_len -= 33;
1842                     *op++ = M3_MARKER | 0;
1843                     goto m3_m4_len;
1844                 }
1845             }
1846             else
1847             {
1848 #if defined(LZO1Y)
1849 m4_match:
1850 #endif
1851                 m_off -= 0x4000;
1852                 assert(m_off > 0); assert(m_off <= 0x7fff);
1853                 if (m_len <= M4_MAX_LEN)
1854                     *op++ = LZO_BYTE(M4_MARKER |
1855                                      ((m_off & 0x4000) >> 11) | (m_len - 2));
1856                 else
1857                 {
1858                     m_len -= M4_MAX_LEN;
1859                     *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11));
1860 m3_m4_len:
1861                     while (m_len > 255)
1862                     {
1863                         m_len -= 255;
1864                         *op++ = 0;
1865                     }
1866                     assert(m_len > 0);
1867                     *op++ = LZO_BYTE(m_len);
1868                 }
1869             }
1870
1871 m3_m4_offset:
1872             *op++ = LZO_BYTE((m_off & 63) << 2);
1873             *op++ = LZO_BYTE(m_off >> 6);
1874         }
1875
1876 #if 0
1877 match_done:
1878 #endif
1879         ii = ip;
1880         if (ip >= ip_end)
1881             break;
1882     }
1883
1884     *out_len = op - out;
1885     return pd(in_end,ii);
1886 }
1887
1888 LZO_PUBLIC(int)
1889 DO_COMPRESS      ( const lzo_byte *in , lzo_uint  in_len,
1890                          lzo_byte *out, lzo_uintp out_len,
1891                          lzo_voidp wrkmem )
1892 {
1893     lzo_byte *op = out;
1894     lzo_uint t;
1895
1896 #if defined(__LZO_QUERY_COMPRESS)
1897     if (__LZO_IS_COMPRESS_QUERY(in,in_len,out,out_len,wrkmem))
1898         return __LZO_QUERY_COMPRESS(in,in_len,out,out_len,wrkmem,D_SIZE,lzo_sizeof(lzo_dict_t));
1899 #endif
1900
1901     if (in_len <= M2_MAX_LEN + 5)
1902         t = in_len;
1903     else
1904     {
1905         t = do_compress(in,in_len,op,out_len,wrkmem);
1906         op += *out_len;
1907     }
1908
1909     if (t > 0)
1910     {
1911         const lzo_byte *ii = in + in_len - t;
1912
1913         if (op == out && t <= 238)
1914             *op++ = LZO_BYTE(17 + t);
1915         else if (t <= 3)
1916             op[-2] |= LZO_BYTE(t);
1917         else if (t <= 18)
1918             *op++ = LZO_BYTE(t - 3);
1919         else
1920         {
1921             lzo_uint tt = t - 18;
1922
1923             *op++ = 0;
1924             while (tt > 255)
1925             {
1926                 tt -= 255;
1927                 *op++ = 0;
1928             }
1929             assert(tt > 0);
1930             *op++ = LZO_BYTE(tt);
1931         }
1932         do *op++ = *ii++; while (--t > 0);
1933     }
1934
1935     *op++ = M4_MARKER | 1;
1936     *op++ = 0;
1937     *op++ = 0;
1938
1939     *out_len = op - out;
1940     return LZO_E_OK;
1941 }
1942
1943 #undef do_compress
1944 #undef DO_COMPRESS
1945 #undef LZO_HASH
1946
1947 #undef LZO_TEST_DECOMPRESS_OVERRUN
1948 #undef LZO_TEST_DECOMPRESS_OVERRUN_INPUT
1949 #undef LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT
1950 #undef LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND
1951 #undef DO_DECOMPRESS
1952 #define DO_DECOMPRESS       lzo1x_decompress
1953
1954 #if defined(LZO_TEST_DECOMPRESS_OVERRUN)
1955 #  if !defined(LZO_TEST_DECOMPRESS_OVERRUN_INPUT)
1956 #    define LZO_TEST_DECOMPRESS_OVERRUN_INPUT       2
1957 #  endif
1958 #  if !defined(LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT)
1959 #    define LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT      2
1960 #  endif
1961 #  if !defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
1962 #    define LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND
1963 #  endif
1964 #endif
1965
1966 #undef TEST_IP
1967 #undef TEST_OP
1968 #undef TEST_LOOKBEHIND
1969 #undef NEED_IP
1970 #undef NEED_OP
1971 #undef HAVE_TEST_IP
1972 #undef HAVE_TEST_OP
1973 #undef HAVE_NEED_IP
1974 #undef HAVE_NEED_OP
1975 #undef HAVE_ANY_IP
1976 #undef HAVE_ANY_OP
1977
1978 #if defined(LZO_TEST_DECOMPRESS_OVERRUN_INPUT)
1979 #  if (LZO_TEST_DECOMPRESS_OVERRUN_INPUT >= 1)
1980 #    define TEST_IP             (ip < ip_end)
1981 #  endif
1982 #  if (LZO_TEST_DECOMPRESS_OVERRUN_INPUT >= 2)
1983 #    define NEED_IP(x) \
1984             if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x))  goto input_overrun
1985 #  endif
1986 #endif
1987
1988 #if defined(LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT)
1989 #  if (LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT >= 1)
1990 #    define TEST_OP             (op <= op_end)
1991 #  endif
1992 #  if (LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT >= 2)
1993 #    undef TEST_OP
1994 #    define NEED_OP(x) \
1995             if ((lzo_uint)(op_end - op) < (lzo_uint)(x))  goto output_overrun
1996 #  endif
1997 #endif
1998
1999 #if defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
2000 #  define TEST_LOOKBEHIND(m_pos,out)    if (m_pos < out) goto lookbehind_overrun
2001 #else
2002 #  define TEST_LOOKBEHIND(m_pos,op)     ((void) 0)
2003 #endif
2004
2005 #if !defined(LZO_EOF_CODE) && !defined(TEST_IP)
2006 #  define TEST_IP               (ip < ip_end)
2007 #endif
2008
2009 #if defined(TEST_IP)
2010 #  define HAVE_TEST_IP
2011 #else
2012 #  define TEST_IP               1
2013 #endif
2014 #if defined(TEST_OP)
2015 #  define HAVE_TEST_OP
2016 #else
2017 #  define TEST_OP               1
2018 #endif
2019
2020 #if defined(NEED_IP)
2021 #  define HAVE_NEED_IP
2022 #else
2023 #  define NEED_IP(x)            ((void) 0)
2024 #endif
2025 #if defined(NEED_OP)
2026 #  define HAVE_NEED_OP
2027 #else
2028 #  define NEED_OP(x)            ((void) 0)
2029 #endif
2030
2031 #if defined(HAVE_TEST_IP) || defined(HAVE_NEED_IP)
2032 #  define HAVE_ANY_IP
2033 #endif
2034 #if defined(HAVE_TEST_OP) || defined(HAVE_NEED_OP)
2035 #  define HAVE_ANY_OP
2036 #endif
2037
2038 #undef __COPY4
2039 #define __COPY4(dst,src)    * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
2040
2041 #undef COPY4
2042 #if defined(LZO_UNALIGNED_OK_4)
2043 #  define COPY4(dst,src)    __COPY4(dst,src)
2044 #elif defined(LZO_ALIGNED_OK_4)
2045 #  define COPY4(dst,src)    __COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src))
2046 #endif
2047
2048 #if defined(DO_DECOMPRESS)
2049 LZO_PUBLIC(int)
2050 DO_DECOMPRESS  ( const lzo_byte *in , lzo_uint  in_len,
2051                        lzo_byte *out, lzo_uintp out_len,
2052                        lzo_voidp wrkmem )
2053 #endif
2054 {
2055     register lzo_byte *op;
2056     register const lzo_byte *ip;
2057     register lzo_uint t;
2058 #if defined(COPY_DICT)
2059     lzo_uint m_off;
2060     const lzo_byte *dict_end;
2061 #else
2062     register const lzo_byte *m_pos;
2063 #endif
2064
2065     const lzo_byte * const ip_end = in + in_len;
2066 #if defined(HAVE_ANY_OP)
2067     lzo_byte * const op_end = out + *out_len;
2068 #endif
2069 #if defined(LZO1Z)
2070     lzo_uint last_m_off = 0;
2071 #endif
2072
2073     LZO_UNUSED(wrkmem);
2074
2075 #if defined(__LZO_QUERY_DECOMPRESS)
2076     if (__LZO_IS_DECOMPRESS_QUERY(in,in_len,out,out_len,wrkmem))
2077         return __LZO_QUERY_DECOMPRESS(in,in_len,out,out_len,wrkmem,0,0);
2078 #endif
2079
2080 #if defined(COPY_DICT)
2081     if (dict)
2082     {
2083         if (dict_len > M4_MAX_OFFSET)
2084         {
2085             dict += dict_len - M4_MAX_OFFSET;
2086             dict_len = M4_MAX_OFFSET;
2087         }
2088         dict_end = dict + dict_len;
2089     }
2090     else
2091     {
2092         dict_len = 0;
2093         dict_end = NULL;
2094     }
2095 #endif
2096
2097     *out_len = 0;
2098
2099     op = out;
2100     ip = in;
2101
2102     if (*ip > 17)
2103     {
2104         t = *ip++ - 17;
2105         if (t < 4)
2106             goto match_next;
2107         assert(t > 0); NEED_OP(t); NEED_IP(t+1);
2108         do *op++ = *ip++; while (--t > 0);
2109         goto first_literal_run;
2110     }
2111
2112     while (TEST_IP && TEST_OP)
2113     {
2114         t = *ip++;
2115         if (t >= 16)
2116             goto match;
2117         if (t == 0)
2118         {
2119             NEED_IP(1);
2120             while (*ip == 0)
2121             {
2122                 t += 255;
2123                 ip++;
2124                 NEED_IP(1);
2125             }
2126             t += 15 + *ip++;
2127         }
2128         assert(t > 0); NEED_OP(t+3); NEED_IP(t+4);
2129 #if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
2130 #if !defined(LZO_UNALIGNED_OK_4)
2131         if (PTR_ALIGNED2_4(op,ip))
2132         {
2133 #endif
2134         COPY4(op,ip);
2135         op += 4; ip += 4;
2136         if (--t > 0)
2137         {
2138             if (t >= 4)
2139             {
2140                 do {
2141                     COPY4(op,ip);
2142                     op += 4; ip += 4; t -= 4;
2143                 } while (t >= 4);
2144                 if (t > 0) do *op++ = *ip++; while (--t > 0);
2145             }
2146             else
2147                 do *op++ = *ip++; while (--t > 0);
2148         }
2149 #if !defined(LZO_UNALIGNED_OK_4)
2150         }
2151         else
2152 #endif
2153 #endif
2154 #if !defined(LZO_UNALIGNED_OK_4)
2155         {
2156             *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
2157             do *op++ = *ip++; while (--t > 0);
2158         }
2159 #endif
2160
2161 first_literal_run:
2162
2163         t = *ip++;
2164         if (t >= 16)
2165             goto match;
2166 #if defined(COPY_DICT)
2167 #if defined(LZO1Z)
2168         m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
2169         last_m_off = m_off;
2170 #else
2171         m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
2172 #endif
2173         NEED_OP(3);
2174         t = 3; COPY_DICT(t,m_off)
2175 #else
2176 #if defined(LZO1Z)
2177         t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
2178         m_pos = op - t;
2179         last_m_off = t;
2180 #else
2181         m_pos = op - (1 + M2_MAX_OFFSET);
2182         m_pos -= t >> 2;
2183         m_pos -= *ip++ << 2;
2184 #endif
2185         TEST_LOOKBEHIND(m_pos,out); NEED_OP(3);
2186         *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
2187 #endif
2188         goto match_done;
2189
2190         while (TEST_IP && TEST_OP)
2191         {
2192 match:
2193             if (t >= 64)
2194             {
2195 #if defined(COPY_DICT)
2196 #if defined(LZO1X)
2197                 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
2198                 t = (t >> 5) - 1;
2199 #elif defined(LZO1Y)
2200                 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
2201                 t = (t >> 4) - 3;
2202 #elif defined(LZO1Z)
2203                 m_off = t & 0x1f;
2204                 if (m_off >= 0x1c)
2205                     m_off = last_m_off;
2206                 else
2207                 {
2208                     m_off = 1 + (m_off << 6) + (*ip++ >> 2);
2209                     last_m_off = m_off;
2210                 }
2211                 t = (t >> 5) - 1;
2212 #endif
2213 #else
2214 #if defined(LZO1X)
2215                 m_pos = op - 1;
2216                 m_pos -= (t >> 2) & 7;
2217                 m_pos -= *ip++ << 3;
2218                 t = (t >> 5) - 1;
2219 #elif defined(LZO1Y)
2220                 m_pos = op - 1;
2221                 m_pos -= (t >> 2) & 3;
2222                 m_pos -= *ip++ << 2;
2223                 t = (t >> 4) - 3;
2224 #elif defined(LZO1Z)
2225                 {
2226                     lzo_uint off = t & 0x1f;
2227                     m_pos = op;
2228                     if (off >= 0x1c)
2229                     {
2230                         assert(last_m_off > 0);
2231                         m_pos -= last_m_off;
2232                     }
2233                     else
2234                     {
2235                         off = 1 + (off << 6) + (*ip++ >> 2);
2236                         m_pos -= off;
2237                         last_m_off = off;
2238                     }
2239                 }
2240                 t = (t >> 5) - 1;
2241 #endif
2242                 TEST_LOOKBEHIND(m_pos,out); assert(t > 0); NEED_OP(t+3-1);
2243                 goto copy_match;
2244 #endif
2245             }
2246             else if (t >= 32)
2247             {
2248                 t &= 31;
2249                 if (t == 0)
2250                 {
2251                     NEED_IP(1);
2252                     while (*ip == 0)
2253                     {
2254                         t += 255;
2255                         ip++;
2256                         NEED_IP(1);
2257                     }
2258                     t += 31 + *ip++;
2259                 }
2260 #if defined(COPY_DICT)
2261 #if defined(LZO1Z)
2262                 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
2263                 last_m_off = m_off;
2264 #else
2265                 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
2266 #endif
2267 #else
2268 #if defined(LZO1Z)
2269                 {
2270                     lzo_uint off = 1 + (ip[0] << 6) + (ip[1] >> 2);
2271                     m_pos = op - off;
2272                     last_m_off = off;
2273                 }
2274 #elif defined(LZO_UNALIGNED_OK_2) && (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
2275                 m_pos = op - 1;
2276                 m_pos -= (* (const lzo_ushortp) ip) >> 2;
2277 #else
2278                 m_pos = op - 1;
2279                 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
2280 #endif
2281 #endif
2282                 ip += 2;
2283             }
2284             else if (t >= 16)
2285             {
2286 #if defined(COPY_DICT)
2287                 m_off = (t & 8) << 11;
2288 #else
2289                 m_pos = op;
2290                 m_pos -= (t & 8) << 11;
2291 #endif
2292                 t &= 7;
2293                 if (t == 0)
2294                 {
2295                     NEED_IP(1);
2296                     while (*ip == 0)
2297                     {
2298                         t += 255;
2299                         ip++;
2300                         NEED_IP(1);
2301                     }
2302                     t += 7 + *ip++;
2303                 }
2304 #if defined(COPY_DICT)
2305 #if defined(LZO1Z)
2306                 m_off += (ip[0] << 6) + (ip[1] >> 2);
2307 #else
2308                 m_off += (ip[0] >> 2) + (ip[1] << 6);
2309 #endif
2310                 ip += 2;
2311                 if (m_off == 0)
2312                     goto eof_found;
2313                 m_off += 0x4000;
2314 #if defined(LZO1Z)
2315                 last_m_off = m_off;
2316 #endif
2317 #else
2318 #if defined(LZO1Z)
2319                 m_pos -= (ip[0] << 6) + (ip[1] >> 2);
2320 #elif defined(LZO_UNALIGNED_OK_2) && (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
2321                 m_pos -= (* (const lzo_ushortp) ip) >> 2;
2322 #else
2323                 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
2324 #endif
2325                 ip += 2;
2326                 if (m_pos == op)
2327                     goto eof_found;
2328                 m_pos -= 0x4000;
2329 #if defined(LZO1Z)
2330                 last_m_off = op - m_pos;
2331 #endif
2332 #endif
2333             }
2334             else
2335             {
2336 #if defined(COPY_DICT)
2337 #if defined(LZO1Z)
2338                 m_off = 1 + (t << 6) + (*ip++ >> 2);
2339                 last_m_off = m_off;
2340 #else
2341                 m_off = 1 + (t >> 2) + (*ip++ << 2);
2342 #endif
2343                 NEED_OP(2);
2344                 t = 2; COPY_DICT(t,m_off)
2345 #else
2346 #if defined(LZO1Z)
2347                 t = 1 + (t << 6) + (*ip++ >> 2);
2348                 m_pos = op - t;
2349                 last_m_off = t;
2350 #else
2351                 m_pos = op - 1;
2352                 m_pos -= t >> 2;
2353                 m_pos -= *ip++ << 2;
2354 #endif
2355                 TEST_LOOKBEHIND(m_pos,out); NEED_OP(2);
2356                 *op++ = *m_pos++; *op++ = *m_pos;
2357 #endif
2358                 goto match_done;
2359             }
2360
2361 #if defined(COPY_DICT)
2362
2363             NEED_OP(t+3-1);
2364             t += 3-1; COPY_DICT(t,m_off)
2365
2366 #else
2367
2368             TEST_LOOKBEHIND(m_pos,out); assert(t > 0); NEED_OP(t+3-1);
2369 #if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
2370 #if !defined(LZO_UNALIGNED_OK_4)
2371             if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos))
2372             {
2373                 assert((op - m_pos) >= 4);
2374 #else
2375             if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
2376             {
2377 #endif
2378                 COPY4(op,m_pos);
2379                 op += 4; m_pos += 4; t -= 4 - (3 - 1);
2380                 do {
2381                     COPY4(op,m_pos);
2382                     op += 4; m_pos += 4; t -= 4;
2383                 } while (t >= 4);
2384                 if (t > 0) do *op++ = *m_pos++; while (--t > 0);
2385             }
2386             else
2387 #endif
2388             {
2389 copy_match:
2390                 *op++ = *m_pos++; *op++ = *m_pos++;
2391                 do *op++ = *m_pos++; while (--t > 0);
2392             }
2393
2394 #endif
2395
2396 match_done:
2397 #if defined(LZO1Z)
2398             t = ip[-1] & 3;
2399 #else
2400             t = ip[-2] & 3;
2401 #endif
2402             if (t == 0)
2403                 break;
2404
2405 match_next:
2406             assert(t > 0); NEED_OP(t); NEED_IP(t+1);
2407             do *op++ = *ip++; while (--t > 0);
2408             t = *ip++;
2409         }
2410     }
2411
2412 #if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
2413     *out_len = op - out;
2414     return LZO_E_EOF_NOT_FOUND;
2415 #endif
2416
2417 eof_found:
2418     assert(t == 1);
2419     *out_len = op - out;
2420     return (ip == ip_end ? LZO_E_OK :
2421            (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
2422
2423 #if defined(HAVE_NEED_IP)
2424 input_overrun:
2425     *out_len = op - out;
2426     return LZO_E_INPUT_OVERRUN;
2427 #endif
2428
2429 #if defined(HAVE_NEED_OP)
2430 output_overrun:
2431     *out_len = op - out;
2432     return LZO_E_OUTPUT_OVERRUN;
2433 #endif
2434
2435 #if defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
2436 lookbehind_overrun:
2437     *out_len = op - out;
2438     return LZO_E_LOOKBEHIND_OVERRUN;
2439 #endif
2440 }
2441
2442 #define LZO_TEST_DECOMPRESS_OVERRUN
2443 #undef DO_DECOMPRESS
2444 #define DO_DECOMPRESS       lzo1x_decompress_safe
2445
2446 #if defined(LZO_TEST_DECOMPRESS_OVERRUN)
2447 #  if !defined(LZO_TEST_DECOMPRESS_OVERRUN_INPUT)
2448 #    define LZO_TEST_DECOMPRESS_OVERRUN_INPUT       2
2449 #  endif
2450 #  if !defined(LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT)
2451 #    define LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT      2
2452 #  endif
2453 #  if !defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
2454 #    define LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND
2455 #  endif
2456 #endif
2457
2458 #undef TEST_IP
2459 #undef TEST_OP
2460 #undef TEST_LOOKBEHIND
2461 #undef NEED_IP
2462 #undef NEED_OP
2463 #undef HAVE_TEST_IP
2464 #undef HAVE_TEST_OP
2465 #undef HAVE_NEED_IP
2466 #undef HAVE_NEED_OP
2467 #undef HAVE_ANY_IP
2468 #undef HAVE_ANY_OP
2469
2470 #if defined(LZO_TEST_DECOMPRESS_OVERRUN_INPUT)
2471 #  if (LZO_TEST_DECOMPRESS_OVERRUN_INPUT >= 1)
2472 #    define TEST_IP             (ip < ip_end)
2473 #  endif
2474 #  if (LZO_TEST_DECOMPRESS_OVERRUN_INPUT >= 2)
2475 #    define NEED_IP(x) \
2476             if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x))  goto input_overrun
2477 #  endif
2478 #endif
2479
2480 #if defined(LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT)
2481 #  if (LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT >= 1)
2482 #    define TEST_OP             (op <= op_end)
2483 #  endif
2484 #  if (LZO_TEST_DECOMPRESS_OVERRUN_OUTPUT >= 2)
2485 #    undef TEST_OP
2486 #    define NEED_OP(x) \
2487             if ((lzo_uint)(op_end - op) < (lzo_uint)(x))  goto output_overrun
2488 #  endif
2489 #endif
2490
2491 #if defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
2492 #  define TEST_LOOKBEHIND(m_pos,out)    if (m_pos < out) goto lookbehind_overrun
2493 #else
2494 #  define TEST_LOOKBEHIND(m_pos,op)     ((void) 0)
2495 #endif
2496
2497 #if !defined(LZO_EOF_CODE) && !defined(TEST_IP)
2498 #  define TEST_IP               (ip < ip_end)
2499 #endif
2500
2501 #if defined(TEST_IP)
2502 #  define HAVE_TEST_IP
2503 #else
2504 #  define TEST_IP               1
2505 #endif
2506 #if defined(TEST_OP)
2507 #  define HAVE_TEST_OP
2508 #else
2509 #  define TEST_OP               1
2510 #endif
2511
2512 #if defined(NEED_IP)
2513 #  define HAVE_NEED_IP
2514 #else
2515 #  define NEED_IP(x)            ((void) 0)
2516 #endif
2517 #if defined(NEED_OP)
2518 #  define HAVE_NEED_OP
2519 #else
2520 #  define NEED_OP(x)            ((void) 0)
2521 #endif
2522
2523 #if defined(HAVE_TEST_IP) || defined(HAVE_NEED_IP)
2524 #  define HAVE_ANY_IP
2525 #endif
2526 #if defined(HAVE_TEST_OP) || defined(HAVE_NEED_OP)
2527 #  define HAVE_ANY_OP
2528 #endif
2529
2530 #undef __COPY4
2531 #define __COPY4(dst,src)    * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src)
2532
2533 #undef COPY4
2534 #if defined(LZO_UNALIGNED_OK_4)
2535 #  define COPY4(dst,src)    __COPY4(dst,src)
2536 #elif defined(LZO_ALIGNED_OK_4)
2537 #  define COPY4(dst,src)    __COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src))
2538 #endif
2539
2540 #if defined(DO_DECOMPRESS)
2541 LZO_PUBLIC(int)
2542 DO_DECOMPRESS  ( const lzo_byte *in , lzo_uint  in_len,
2543                        lzo_byte *out, lzo_uintp out_len,
2544                        lzo_voidp wrkmem )
2545 #endif
2546 {
2547     register lzo_byte *op;
2548     register const lzo_byte *ip;
2549     register lzo_uint t;
2550 #if defined(COPY_DICT)
2551     lzo_uint m_off;
2552     const lzo_byte *dict_end;
2553 #else
2554     register const lzo_byte *m_pos;
2555 #endif
2556
2557     const lzo_byte * const ip_end = in + in_len;
2558 #if defined(HAVE_ANY_OP)
2559     lzo_byte * const op_end = out + *out_len;
2560 #endif
2561 #if defined(LZO1Z)
2562     lzo_uint last_m_off = 0;
2563 #endif
2564
2565     LZO_UNUSED(wrkmem);
2566
2567 #if defined(__LZO_QUERY_DECOMPRESS)
2568     if (__LZO_IS_DECOMPRESS_QUERY(in,in_len,out,out_len,wrkmem))
2569         return __LZO_QUERY_DECOMPRESS(in,in_len,out,out_len,wrkmem,0,0);
2570 #endif
2571
2572 #if defined(COPY_DICT)
2573     if (dict)
2574     {
2575         if (dict_len > M4_MAX_OFFSET)
2576         {
2577             dict += dict_len - M4_MAX_OFFSET;
2578             dict_len = M4_MAX_OFFSET;
2579         }
2580         dict_end = dict + dict_len;
2581     }
2582     else
2583     {
2584         dict_len = 0;
2585         dict_end = NULL;
2586     }
2587 #endif
2588
2589     *out_len = 0;
2590
2591     op = out;
2592     ip = in;
2593
2594     if (*ip > 17)
2595     {
2596         t = *ip++ - 17;
2597         if (t < 4)
2598             goto match_next;
2599         assert(t > 0); NEED_OP(t); NEED_IP(t+1);
2600         do *op++ = *ip++; while (--t > 0);
2601         goto first_literal_run;
2602     }
2603
2604     while (TEST_IP && TEST_OP)
2605     {
2606         t = *ip++;
2607         if (t >= 16)
2608             goto match;
2609         if (t == 0)
2610         {
2611             NEED_IP(1);
2612             while (*ip == 0)
2613             {
2614                 t += 255;
2615                 ip++;
2616                 NEED_IP(1);
2617             }
2618             t += 15 + *ip++;
2619         }
2620         assert(t > 0); NEED_OP(t+3); NEED_IP(t+4);
2621 #if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
2622 #if !defined(LZO_UNALIGNED_OK_4)
2623         if (PTR_ALIGNED2_4(op,ip))
2624         {
2625 #endif
2626         COPY4(op,ip);
2627         op += 4; ip += 4;
2628         if (--t > 0)
2629         {
2630             if (t >= 4)
2631             {
2632                 do {
2633                     COPY4(op,ip);
2634                     op += 4; ip += 4; t -= 4;
2635                 } while (t >= 4);
2636                 if (t > 0) do *op++ = *ip++; while (--t > 0);
2637             }
2638             else
2639                 do *op++ = *ip++; while (--t > 0);
2640         }
2641 #if !defined(LZO_UNALIGNED_OK_4)
2642         }
2643         else
2644 #endif
2645 #endif
2646 #if !defined(LZO_UNALIGNED_OK_4)
2647         {
2648             *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
2649             do *op++ = *ip++; while (--t > 0);
2650         }
2651 #endif
2652
2653 first_literal_run:
2654
2655         t = *ip++;
2656         if (t >= 16)
2657             goto match;
2658 #if defined(COPY_DICT)
2659 #if defined(LZO1Z)
2660         m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
2661         last_m_off = m_off;
2662 #else
2663         m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
2664 #endif
2665         NEED_OP(3);
2666         t = 3; COPY_DICT(t,m_off)
2667 #else
2668 #if defined(LZO1Z)
2669         t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
2670         m_pos = op - t;
2671         last_m_off = t;
2672 #else
2673         m_pos = op - (1 + M2_MAX_OFFSET);
2674         m_pos -= t >> 2;
2675         m_pos -= *ip++ << 2;
2676 #endif
2677         TEST_LOOKBEHIND(m_pos,out); NEED_OP(3);
2678         *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos;
2679 #endif
2680         goto match_done;
2681
2682         while (TEST_IP && TEST_OP)
2683         {
2684 match:
2685             if (t >= 64)
2686             {
2687 #if defined(COPY_DICT)
2688 #if defined(LZO1X)
2689                 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
2690                 t = (t >> 5) - 1;
2691 #elif defined(LZO1Y)
2692                 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
2693                 t = (t >> 4) - 3;
2694 #elif defined(LZO1Z)
2695                 m_off = t & 0x1f;
2696                 if (m_off >= 0x1c)
2697                     m_off = last_m_off;
2698                 else
2699                 {
2700                     m_off = 1 + (m_off << 6) + (*ip++ >> 2);
2701                     last_m_off = m_off;
2702                 }
2703                 t = (t >> 5) - 1;
2704 #endif
2705 #else
2706 #if defined(LZO1X)
2707                 m_pos = op - 1;
2708                 m_pos -= (t >> 2) & 7;
2709                 m_pos -= *ip++ << 3;
2710                 t = (t >> 5) - 1;
2711 #elif defined(LZO1Y)
2712                 m_pos = op - 1;
2713                 m_pos -= (t >> 2) & 3;
2714                 m_pos -= *ip++ << 2;
2715                 t = (t >> 4) - 3;
2716 #elif defined(LZO1Z)
2717                 {
2718                     lzo_uint off = t & 0x1f;
2719                     m_pos = op;
2720                     if (off >= 0x1c)
2721                     {
2722                         assert(last_m_off > 0);
2723                         m_pos -= last_m_off;
2724                     }
2725                     else
2726                     {
2727                         off = 1 + (off << 6) + (*ip++ >> 2);
2728                         m_pos -= off;
2729                         last_m_off = off;
2730                     }
2731                 }
2732                 t = (t >> 5) - 1;
2733 #endif
2734                 TEST_LOOKBEHIND(m_pos,out); assert(t > 0); NEED_OP(t+3-1);
2735                 goto copy_match;
2736 #endif
2737             }
2738             else if (t >= 32)
2739             {
2740                 t &= 31;
2741                 if (t == 0)
2742                 {
2743                     NEED_IP(1);
2744                     while (*ip == 0)
2745                     {
2746                         t += 255;
2747                         ip++;
2748                         NEED_IP(1);
2749                     }
2750                     t += 31 + *ip++;
2751                 }
2752 #if defined(COPY_DICT)
2753 #if defined(LZO1Z)
2754                 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
2755                 last_m_off = m_off;
2756 #else
2757                 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
2758 #endif
2759 #else
2760 #if defined(LZO1Z)
2761                 {
2762                     lzo_uint off = 1 + (ip[0] << 6) + (ip[1] >> 2);
2763                     m_pos = op - off;
2764                     last_m_off = off;
2765                 }
2766 #elif defined(LZO_UNALIGNED_OK_2) && (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
2767                 m_pos = op - 1;
2768                 m_pos -= (* (const lzo_ushortp) ip) >> 2;
2769 #else
2770                 m_pos = op - 1;
2771                 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
2772 #endif
2773 #endif
2774                 ip += 2;
2775             }
2776             else if (t >= 16)
2777             {
2778 #if defined(COPY_DICT)
2779                 m_off = (t & 8) << 11;
2780 #else
2781                 m_pos = op;
2782                 m_pos -= (t & 8) << 11;
2783 #endif
2784                 t &= 7;
2785                 if (t == 0)
2786                 {
2787                     NEED_IP(1);
2788                     while (*ip == 0)
2789                     {
2790                         t += 255;
2791                         ip++;
2792                         NEED_IP(1);
2793                     }
2794                     t += 7 + *ip++;
2795                 }
2796 #if defined(COPY_DICT)
2797 #if defined(LZO1Z)
2798                 m_off += (ip[0] << 6) + (ip[1] >> 2);
2799 #else
2800                 m_off += (ip[0] >> 2) + (ip[1] << 6);
2801 #endif
2802                 ip += 2;
2803                 if (m_off == 0)
2804                     goto eof_found;
2805                 m_off += 0x4000;
2806 #if defined(LZO1Z)
2807                 last_m_off = m_off;
2808 #endif
2809 #else
2810 #if defined(LZO1Z)
2811                 m_pos -= (ip[0] << 6) + (ip[1] >> 2);
2812 #elif defined(LZO_UNALIGNED_OK_2) && (LZO_BYTE_ORDER == LZO_LITTLE_ENDIAN)
2813                 m_pos -= (* (const lzo_ushortp) ip) >> 2;
2814 #else
2815                 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
2816 #endif
2817                 ip += 2;
2818                 if (m_pos == op)
2819                     goto eof_found;
2820                 m_pos -= 0x4000;
2821 #if defined(LZO1Z)
2822                 last_m_off = op - m_pos;
2823 #endif
2824 #endif
2825             }
2826             else
2827             {
2828 #if defined(COPY_DICT)
2829 #if defined(LZO1Z)
2830                 m_off = 1 + (t << 6) + (*ip++ >> 2);
2831                 last_m_off = m_off;
2832 #else
2833                 m_off = 1 + (t >> 2) + (*ip++ << 2);
2834 #endif
2835                 NEED_OP(2);
2836                 t = 2; COPY_DICT(t,m_off)
2837 #else
2838 #if defined(LZO1Z)
2839                 t = 1 + (t << 6) + (*ip++ >> 2);
2840                 m_pos = op - t;
2841                 last_m_off = t;
2842 #else
2843                 m_pos = op - 1;
2844                 m_pos -= t >> 2;
2845                 m_pos -= *ip++ << 2;
2846 #endif
2847                 TEST_LOOKBEHIND(m_pos,out); NEED_OP(2);
2848                 *op++ = *m_pos++; *op++ = *m_pos;
2849 #endif
2850                 goto match_done;
2851             }
2852
2853 #if defined(COPY_DICT)
2854
2855             NEED_OP(t+3-1);
2856             t += 3-1; COPY_DICT(t,m_off)
2857
2858 #else
2859
2860             TEST_LOOKBEHIND(m_pos,out); assert(t > 0); NEED_OP(t+3-1);
2861 #if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
2862 #if !defined(LZO_UNALIGNED_OK_4)
2863             if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos))
2864             {
2865                 assert((op - m_pos) >= 4);
2866 #else
2867             if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4)
2868             {
2869 #endif
2870                 COPY4(op,m_pos);
2871                 op += 4; m_pos += 4; t -= 4 - (3 - 1);
2872                 do {
2873                     COPY4(op,m_pos);
2874                     op += 4; m_pos += 4; t -= 4;
2875                 } while (t >= 4);
2876                 if (t > 0) do *op++ = *m_pos++; while (--t > 0);
2877             }
2878             else
2879 #endif
2880             {
2881 copy_match:
2882                 *op++ = *m_pos++; *op++ = *m_pos++;
2883                 do *op++ = *m_pos++; while (--t > 0);
2884             }
2885
2886 #endif
2887
2888 match_done:
2889 #if defined(LZO1Z)
2890             t = ip[-1] & 3;
2891 #else
2892             t = ip[-2] & 3;
2893 #endif
2894             if (t == 0)
2895                 break;
2896
2897 match_next:
2898             assert(t > 0); NEED_OP(t); NEED_IP(t+1);
2899             do *op++ = *ip++; while (--t > 0);
2900             t = *ip++;
2901         }
2902     }
2903
2904 #if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
2905     *out_len = op - out;
2906     return LZO_E_EOF_NOT_FOUND;
2907 #endif
2908
2909 eof_found:
2910     assert(t == 1);
2911     *out_len = op - out;
2912     return (ip == ip_end ? LZO_E_OK :
2913            (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
2914
2915 #if defined(HAVE_NEED_IP)
2916 input_overrun:
2917     *out_len = op - out;
2918     return LZO_E_INPUT_OVERRUN;
2919 #endif
2920
2921 #if defined(HAVE_NEED_OP)
2922 output_overrun:
2923     *out_len = op - out;
2924     return LZO_E_OUTPUT_OVERRUN;
2925 #endif
2926
2927 #if defined(LZO_TEST_DECOMPRESS_OVERRUN_LOOKBEHIND)
2928 lookbehind_overrun:
2929     *out_len = op - out;
2930     return LZO_E_LOOKBEHIND_OVERRUN;
2931 #endif
2932 }
2933
2934 /***** End of minilzo.c *****/
2935