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