Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

source: branches/samhain-2_2-branch/src/minilzo.c@ 87

Last change on this file since 87 was 1, checked in by katerina, 19 years ago
Initial import
File size: 63.9 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: