summaryrefslogtreecommitdiff
path: root/archival/libarchive/lzo1x_9x.c (plain)
blob: 2b490ae83e5840035a46a7429ec3a45e9f33f8f1
1/* lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
2
3 This file is part of the LZO real-time data compression library.
4
5 Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
6 Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
7 Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
8 Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
9 Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
10 Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
11 Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
12 Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
13 Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
14 Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
15 Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
16 Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
17 Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
18 All Rights Reserved.
19
20 The LZO library is free software; you can redistribute it and/or
21 modify it under the terms of the GNU General Public License as
22 published by the Free Software Foundation; either version 2 of
23 the License, or (at your option) any later version.
24
25 The LZO library is distributed in the hope that it will be useful,
26 but WITHOUT ANY WARRANTY; without even the implied warranty of
27 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 GNU General Public License for more details.
29
30 You should have received a copy of the GNU General Public License
31 along with the LZO library; see the file COPYING.
32 If not, write to the Free Software Foundation, Inc.,
33 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
34
35 Markus F.X.J. Oberhumer
36 <markus@oberhumer.com>
37 http://www.oberhumer.com/opensource/lzo/
38*/
39#include "libbb.h"
40
41/* The following is probably only safe on Intel-compatible processors ... */
42#define LZO_UNALIGNED_OK_2
43#define LZO_UNALIGNED_OK_4
44
45#include "liblzo.h"
46
47#define LZO_MAX(a,b) ((a) >= (b) ? (a) : (b))
48#define LZO_MIN(a,b) ((a) <= (b) ? (a) : (b))
49#define LZO_MAX3(a,b,c) ((a) >= (b) ? LZO_MAX(a,c) : LZO_MAX(b,c))
50
51/***********************************************************************
52//
53************************************************************************/
54#define SWD_N M4_MAX_OFFSET /* size of ring buffer */
55#define SWD_F 2048 /* upper limit for match length */
56
57#define SWD_BEST_OFF (LZO_MAX3(M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN) + 1)
58
59typedef struct {
60 int init;
61
62 unsigned look; /* bytes in lookahead buffer */
63
64 unsigned m_len;
65 unsigned m_off;
66
67 const uint8_t *bp;
68 const uint8_t *ip;
69 const uint8_t *in;
70 const uint8_t *in_end;
71 uint8_t *out;
72
73 unsigned r1_lit;
74
75} lzo1x_999_t;
76
77#define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
78
79/* lzo_swd.c -- sliding window dictionary */
80
81/***********************************************************************
82//
83************************************************************************/
84#define SWD_UINT_MAX USHRT_MAX
85
86#ifndef SWD_HSIZE
87# define SWD_HSIZE 16384
88#endif
89#ifndef SWD_MAX_CHAIN
90# define SWD_MAX_CHAIN 2048
91#endif
92
93#define HEAD3(b, p) \
94 ( ((0x9f5f * ((((b[p]<<5)^b[p+1])<<5) ^ b[p+2])) >> 5) & (SWD_HSIZE-1) )
95
96#if defined(LZO_UNALIGNED_OK_2)
97# define HEAD2(b,p) (* (bb__aliased_uint16_t *) &(b[p]))
98#else
99# define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8))
100#endif
101#define NIL2 SWD_UINT_MAX
102
103typedef struct lzo_swd {
104 /* public - "built-in" */
105
106 /* public - configuration */
107 unsigned max_chain;
108 int use_best_off;
109
110 /* public - output */
111 unsigned m_len;
112 unsigned m_off;
113 unsigned look;
114 int b_char;
115#if defined(SWD_BEST_OFF)
116 unsigned best_off[SWD_BEST_OFF];
117#endif
118
119 /* semi public */
120 lzo1x_999_t *c;
121 unsigned m_pos;
122#if defined(SWD_BEST_OFF)
123 unsigned best_pos[SWD_BEST_OFF];
124#endif
125
126 /* private */
127 unsigned ip; /* input pointer (lookahead) */
128 unsigned bp; /* buffer pointer */
129 unsigned rp; /* remove pointer */
130
131 unsigned node_count;
132 unsigned first_rp;
133
134 uint8_t b[SWD_N + SWD_F];
135 uint8_t b_wrap[SWD_F]; /* must follow b */
136 uint16_t head3[SWD_HSIZE];
137 uint16_t succ3[SWD_N + SWD_F];
138 uint16_t best3[SWD_N + SWD_F];
139 uint16_t llen3[SWD_HSIZE];
140#ifdef HEAD2
141 uint16_t head2[65536L];
142#endif
143} lzo_swd_t, *lzo_swd_p;
144
145#define SIZEOF_LZO_SWD_T (sizeof(lzo_swd_t))
146
147
148/* Access macro for head3.
149 * head3[key] may be uninitialized, but then its value will never be used.
150 */
151#define s_get_head3(s,key) s->head3[key]
152
153
154/***********************************************************************
155//
156************************************************************************/
157#define B_SIZE (SWD_N + SWD_F)
158
159static int swd_init(lzo_swd_p s)
160{
161 /* defaults */
162 s->node_count = SWD_N;
163
164 memset(s->llen3, 0, sizeof(s->llen3[0]) * (unsigned)SWD_HSIZE);
165#ifdef HEAD2
166 memset(s->head2, 0xff, sizeof(s->head2[0]) * 65536L);
167 assert(s->head2[0] == NIL2);
168#endif
169
170 s->ip = 0;
171 s->bp = s->ip;
172 s->first_rp = s->ip;
173
174 assert(s->ip + SWD_F <= B_SIZE);
175 s->look = (unsigned) (s->c->in_end - s->c->ip);
176 if (s->look > 0) {
177 if (s->look > SWD_F)
178 s->look = SWD_F;
179 memcpy(&s->b[s->ip], s->c->ip, s->look);
180 s->c->ip += s->look;
181 s->ip += s->look;
182 }
183 if (s->ip == B_SIZE)
184 s->ip = 0;
185
186 s->rp = s->first_rp;
187 if (s->rp >= s->node_count)
188 s->rp -= s->node_count;
189 else
190 s->rp += B_SIZE - s->node_count;
191
192 return LZO_E_OK;
193}
194
195#define swd_pos2off(s,pos) \
196 (s->bp > (pos) ? s->bp - (pos) : B_SIZE - ((pos) - s->bp))
197
198
199/***********************************************************************
200//
201************************************************************************/
202static void swd_getbyte(lzo_swd_p s)
203{
204 int c;
205
206 if ((c = getbyte(*(s->c))) < 0) {
207 if (s->look > 0)
208 --s->look;
209 } else {
210 s->b[s->ip] = c;
211 if (s->ip < SWD_F)
212 s->b_wrap[s->ip] = c;
213 }
214 if (++s->ip == B_SIZE)
215 s->ip = 0;
216 if (++s->bp == B_SIZE)
217 s->bp = 0;
218 if (++s->rp == B_SIZE)
219 s->rp = 0;
220}
221
222
223/***********************************************************************
224// remove node from lists
225************************************************************************/
226static void swd_remove_node(lzo_swd_p s, unsigned node)
227{
228 if (s->node_count == 0) {
229 unsigned key;
230
231 key = HEAD3(s->b,node);
232 assert(s->llen3[key] > 0);
233 --s->llen3[key];
234
235#ifdef HEAD2
236 key = HEAD2(s->b,node);
237 assert(s->head2[key] != NIL2);
238 if ((unsigned) s->head2[key] == node)
239 s->head2[key] = NIL2;
240#endif
241 } else
242 --s->node_count;
243}
244
245
246/***********************************************************************
247//
248************************************************************************/
249static void swd_accept(lzo_swd_p s, unsigned n)
250{
251 assert(n <= s->look);
252
253 while (n--) {
254 unsigned key;
255
256 swd_remove_node(s,s->rp);
257
258 /* add bp into HEAD3 */
259 key = HEAD3(s->b, s->bp);
260 s->succ3[s->bp] = s_get_head3(s, key);
261 s->head3[key] = s->bp;
262 s->best3[s->bp] = SWD_F + 1;
263 s->llen3[key]++;
264 assert(s->llen3[key] <= SWD_N);
265
266#ifdef HEAD2
267 /* add bp into HEAD2 */
268 key = HEAD2(s->b, s->bp);
269 s->head2[key] = s->bp;
270#endif
271
272 swd_getbyte(s);
273 }
274}
275
276
277/***********************************************************************
278//
279************************************************************************/
280static void swd_search(lzo_swd_p s, unsigned node, unsigned cnt)
281{
282 const uint8_t *p1;
283 const uint8_t *p2;
284 const uint8_t *px;
285 unsigned m_len = s->m_len;
286 const uint8_t *b = s->b;
287 const uint8_t *bp = s->b + s->bp;
288 const uint8_t *bx = s->b + s->bp + s->look;
289 unsigned char scan_end1;
290
291 assert(s->m_len > 0);
292
293 scan_end1 = bp[m_len - 1];
294 for ( ; cnt-- > 0; node = s->succ3[node]) {
295 p1 = bp;
296 p2 = b + node;
297 px = bx;
298
299 assert(m_len < s->look);
300
301 if (p2[m_len - 1] == scan_end1
302 && p2[m_len] == p1[m_len]
303 && p2[0] == p1[0]
304 && p2[1] == p1[1]
305 ) {
306 unsigned i;
307 assert(lzo_memcmp(bp, &b[node], 3) == 0);
308
309 p1 += 2; p2 += 2;
310 do {} while (++p1 < px && *p1 == *++p2);
311 i = p1-bp;
312
313 assert(lzo_memcmp(bp, &b[node], i) == 0);
314
315#if defined(SWD_BEST_OFF)
316 if (i < SWD_BEST_OFF) {
317 if (s->best_pos[i] == 0)
318 s->best_pos[i] = node + 1;
319 }
320#endif
321 if (i > m_len) {
322 s->m_len = m_len = i;
323 s->m_pos = node;
324 if (m_len == s->look)
325 return;
326 if (m_len >= SWD_F)
327 return;
328 if (m_len > (unsigned) s->best3[node])
329 return;
330 scan_end1 = bp[m_len - 1];
331 }
332 }
333 }
334}
335
336
337/***********************************************************************
338//
339************************************************************************/
340#ifdef HEAD2
341
342static int swd_search2(lzo_swd_p s)
343{
344 unsigned key;
345
346 assert(s->look >= 2);
347 assert(s->m_len > 0);
348
349 key = s->head2[HEAD2(s->b, s->bp)];
350 if (key == NIL2)
351 return 0;
352 assert(lzo_memcmp(&s->b[s->bp], &s->b[key], 2) == 0);
353#if defined(SWD_BEST_OFF)
354 if (s->best_pos[2] == 0)
355 s->best_pos[2] = key + 1;
356#endif
357
358 if (s->m_len < 2) {
359 s->m_len = 2;
360 s->m_pos = key;
361 }
362 return 1;
363}
364
365#endif
366
367
368/***********************************************************************
369//
370************************************************************************/
371static void swd_findbest(lzo_swd_p s)
372{
373 unsigned key;
374 unsigned cnt, node;
375 unsigned len;
376
377 assert(s->m_len > 0);
378
379 /* get current head, add bp into HEAD3 */
380 key = HEAD3(s->b,s->bp);
381 node = s->succ3[s->bp] = s_get_head3(s, key);
382 cnt = s->llen3[key]++;
383 assert(s->llen3[key] <= SWD_N + SWD_F);
384 if (cnt > s->max_chain)
385 cnt = s->max_chain;
386 s->head3[key] = s->bp;
387
388 s->b_char = s->b[s->bp];
389 len = s->m_len;
390 if (s->m_len >= s->look) {
391 if (s->look == 0)
392 s->b_char = -1;
393 s->m_off = 0;
394 s->best3[s->bp] = SWD_F + 1;
395 } else {
396#ifdef HEAD2
397 if (swd_search2(s))
398#endif
399 if (s->look >= 3)
400 swd_search(s, node, cnt);
401 if (s->m_len > len)
402 s->m_off = swd_pos2off(s,s->m_pos);
403 s->best3[s->bp] = s->m_len;
404
405#if defined(SWD_BEST_OFF)
406 if (s->use_best_off) {
407 int i;
408 for (i = 2; i < SWD_BEST_OFF; i++) {
409 if (s->best_pos[i] > 0)
410 s->best_off[i] = swd_pos2off(s, s->best_pos[i]-1);
411 else
412 s->best_off[i] = 0;
413 }
414 }
415#endif
416 }
417
418 swd_remove_node(s,s->rp);
419
420#ifdef HEAD2
421 /* add bp into HEAD2 */
422 key = HEAD2(s->b, s->bp);
423 s->head2[key] = s->bp;
424#endif
425}
426
427#undef HEAD3
428#undef HEAD2
429#undef s_get_head3
430
431
432/***********************************************************************
433//
434************************************************************************/
435static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
436{
437 int r;
438
439 assert(!c->init);
440 c->init = 1;
441
442 s->c = c;
443
444 r = swd_init(s);
445 if (r != 0)
446 return r;
447
448 s->use_best_off = use_best_off;
449 return r;
450}
451
452
453/***********************************************************************
454//
455************************************************************************/
456static int find_match(lzo1x_999_t *c, lzo_swd_p s,
457 unsigned this_len, unsigned skip)
458{
459 assert(c->init);
460
461 if (skip > 0) {
462 assert(this_len >= skip);
463 swd_accept(s, this_len - skip);
464 } else {
465 assert(this_len <= 1);
466 }
467
468 s->m_len = 1;
469#ifdef SWD_BEST_OFF
470 if (s->use_best_off)
471 memset(s->best_pos, 0, sizeof(s->best_pos));
472#endif
473 swd_findbest(s);
474 c->m_len = s->m_len;
475 c->m_off = s->m_off;
476
477 swd_getbyte(s);
478
479 if (s->b_char < 0) {
480 c->look = 0;
481 c->m_len = 0;
482 } else {
483 c->look = s->look + 1;
484 }
485 c->bp = c->ip - c->look;
486
487 return LZO_E_OK;
488}
489
490/* this is a public functions, but there is no prototype in a header file */
491static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
492 uint8_t *out, unsigned *out_len,
493 void *wrkmem,
494 unsigned good_length,
495 unsigned max_lazy,
496 unsigned max_chain,
497 uint32_t use_best_off);
498
499
500/***********************************************************************
501//
502************************************************************************/
503static uint8_t *code_match(lzo1x_999_t *c,
504 uint8_t *op, unsigned m_len, unsigned m_off)
505{
506 assert(op > c->out);
507 if (m_len == 2) {
508 assert(m_off <= M1_MAX_OFFSET);
509 assert(c->r1_lit > 0);
510 assert(c->r1_lit < 4);
511 m_off -= 1;
512 *op++ = M1_MARKER | ((m_off & 3) << 2);
513 *op++ = m_off >> 2;
514 } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
515 assert(m_len >= 3);
516 m_off -= 1;
517 *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
518 *op++ = m_off >> 3;
519 assert(op[-2] >= M2_MARKER);
520 } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
521 assert(m_len == 3);
522 assert(m_off > M2_MAX_OFFSET);
523 m_off -= 1 + M2_MAX_OFFSET;
524 *op++ = M1_MARKER | ((m_off & 3) << 2);
525 *op++ = m_off >> 2;
526 } else if (m_off <= M3_MAX_OFFSET) {
527 assert(m_len >= 3);
528 m_off -= 1;
529 if (m_len <= M3_MAX_LEN)
530 *op++ = M3_MARKER | (m_len - 2);
531 else {
532 m_len -= M3_MAX_LEN;
533 *op++ = M3_MARKER | 0;
534 while (m_len > 255) {
535 m_len -= 255;
536 *op++ = 0;
537 }
538 assert(m_len > 0);
539 *op++ = m_len;
540 }
541 *op++ = m_off << 2;
542 *op++ = m_off >> 6;
543 } else {
544 unsigned k;
545
546 assert(m_len >= 3);
547 assert(m_off > 0x4000);
548 assert(m_off <= 0xbfff);
549 m_off -= 0x4000;
550 k = (m_off & 0x4000) >> 11;
551 if (m_len <= M4_MAX_LEN)
552 *op++ = M4_MARKER | k | (m_len - 2);
553 else {
554 m_len -= M4_MAX_LEN;
555 *op++ = M4_MARKER | k | 0;
556 while (m_len > 255) {
557 m_len -= 255;
558 *op++ = 0;
559 }
560 assert(m_len > 0);
561 *op++ = m_len;
562 }
563 *op++ = m_off << 2;
564 *op++ = m_off >> 6;
565 }
566
567 return op;
568}
569
570
571static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
572 const uint8_t *ii, unsigned t)
573{
574 if (op == c->out && t <= 238) {
575 *op++ = 17 + t;
576 } else if (t <= 3) {
577 op[-2] |= t;
578 } else if (t <= 18) {
579 *op++ = t - 3;
580 } else {
581 unsigned tt = t - 18;
582
583 *op++ = 0;
584 while (tt > 255) {
585 tt -= 255;
586 *op++ = 0;
587 }
588 assert(tt > 0);
589 *op++ = tt;
590 }
591 do *op++ = *ii++; while (--t > 0);
592
593 return op;
594}
595
596
597static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
598 unsigned lit)
599{
600 if (lit > 0) {
601 assert(m_len >= 2);
602 op = STORE_RUN(c, op, ii, lit);
603 } else {
604 assert(m_len >= 3);
605 }
606 c->r1_lit = lit;
607
608 return op;
609}
610
611
612/***********************************************************************
613//
614************************************************************************/
615static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
616{
617 int n = 4;
618
619 if (m_len < 2)
620 return -1;
621 if (m_len == 2)
622 return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
623 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
624 return 2;
625 if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
626 return 2;
627 if (m_off <= M3_MAX_OFFSET) {
628 if (m_len <= M3_MAX_LEN)
629 return 3;
630 m_len -= M3_MAX_LEN;
631 } else if (m_off <= M4_MAX_OFFSET) {
632 if (m_len <= M4_MAX_LEN)
633 return 3;
634 m_len -= M4_MAX_LEN;
635 } else
636 return -1;
637 while (m_len > 255) {
638 m_len -= 255;
639 n++;
640 }
641 return n;
642}
643
644
645static int min_gain(unsigned ahead, unsigned lit1,
646 unsigned lit2, int l1, int l2, int l3)
647{
648 int lazy_match_min_gain = 0;
649
650 assert (ahead >= 1);
651 lazy_match_min_gain += ahead;
652
653 if (lit1 <= 3)
654 lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
655 else if (lit1 <= 18)
656 lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
657
658 lazy_match_min_gain += (l2 - l1) * 2;
659 if (l3 > 0)
660 lazy_match_min_gain -= (ahead - l3) * 2;
661
662 if (lazy_match_min_gain < 0)
663 lazy_match_min_gain = 0;
664
665 return lazy_match_min_gain;
666}
667
668
669/***********************************************************************
670//
671************************************************************************/
672#if defined(SWD_BEST_OFF)
673
674static void better_match(const lzo_swd_p swd,
675 unsigned *m_len, unsigned *m_off)
676{
677 if (*m_len <= M2_MIN_LEN)
678 return;
679
680 if (*m_off <= M2_MAX_OFFSET)
681 return;
682
683 /* M3/M4 -> M2 */
684 if (*m_off > M2_MAX_OFFSET
685 && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
686 && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
687 ) {
688 *m_len = *m_len - 1;
689 *m_off = swd->best_off[*m_len];
690 return;
691 }
692
693 /* M4 -> M2 */
694 if (*m_off > M3_MAX_OFFSET
695 && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
696 && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
697 ) {
698 *m_len = *m_len - 2;
699 *m_off = swd->best_off[*m_len];
700 return;
701 }
702 /* M4 -> M3 */
703 if (*m_off > M3_MAX_OFFSET
704 && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
705 && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
706 ) {
707 *m_len = *m_len - 1;
708 *m_off = swd->best_off[*m_len];
709 }
710}
711
712#endif
713
714
715/***********************************************************************
716//
717************************************************************************/
718static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
719 uint8_t *out, unsigned *out_len,
720 void *wrkmem,
721 unsigned good_length,
722 unsigned max_lazy,
723 unsigned max_chain,
724 uint32_t use_best_off)
725{
726 uint8_t *op;
727 const uint8_t *ii;
728 unsigned lit;
729 unsigned m_len, m_off;
730 lzo1x_999_t cc;
731 lzo1x_999_t *const c = &cc;
732 const lzo_swd_p swd = (lzo_swd_p) wrkmem;
733 int r;
734
735 c->init = 0;
736 c->ip = c->in = in;
737 c->in_end = in + in_len;
738 c->out = out;
739
740 op = out;
741 ii = c->ip; /* point to start of literal run */
742 lit = 0;
743 c->r1_lit = 0;
744
745 r = init_match(c, swd, use_best_off);
746 if (r != 0)
747 return r;
748 swd->max_chain = max_chain;
749
750 r = find_match(c, swd, 0, 0);
751 if (r != 0)
752 return r;
753
754 while (c->look > 0) {
755 unsigned ahead;
756 unsigned max_ahead;
757 int l1, l2, l3;
758
759 m_len = c->m_len;
760 m_off = c->m_off;
761
762 assert(c->bp == c->ip - c->look);
763 assert(c->bp >= in);
764 if (lit == 0)
765 ii = c->bp;
766 assert(ii + lit == c->bp);
767 assert(swd->b_char == *(c->bp));
768
769 if (m_len < 2
770 || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
771 /* Do not accept this match for compressed-data compatibility
772 * with LZO v1.01 and before
773 * [ might be a problem for decompress() and optimize() ]
774 */
775 || (m_len == 2 && op == out)
776 || (op == out && lit == 0)
777 ) {
778 /* a literal */
779 m_len = 0;
780 }
781 else if (m_len == M2_MIN_LEN) {
782 /* compression ratio improves if we code a literal in some cases */
783 if (m_off > MX_MAX_OFFSET && lit >= 4)
784 m_len = 0;
785 }
786
787 if (m_len == 0) {
788 /* a literal */
789 lit++;
790 swd->max_chain = max_chain;
791 r = find_match(c, swd, 1, 0);
792 assert(r == 0);
793 continue;
794 }
795
796 /* a match */
797#if defined(SWD_BEST_OFF)
798 if (swd->use_best_off)
799 better_match(swd, &m_len, &m_off);
800#endif
801
802 /* shall we try a lazy match ? */
803 ahead = 0;
804 if (m_len >= max_lazy) {
805 /* no */
806 l1 = 0;
807 max_ahead = 0;
808 } else {
809 /* yes, try a lazy match */
810 l1 = len_of_coded_match(m_len, m_off, lit);
811 assert(l1 > 0);
812 max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
813 }
814
815
816 while (ahead < max_ahead && c->look > m_len) {
817 int lazy_match_min_gain;
818
819 if (m_len >= good_length)
820 swd->max_chain = max_chain >> 2;
821 else
822 swd->max_chain = max_chain;
823 r = find_match(c, swd, 1, 0);
824 ahead++;
825
826 assert(r == 0);
827 assert(c->look > 0);
828 assert(ii + lit + ahead == c->bp);
829
830 if (c->m_len < m_len)
831 continue;
832 if (c->m_len == m_len && c->m_off >= m_off)
833 continue;
834#if defined(SWD_BEST_OFF)
835 if (swd->use_best_off)
836 better_match(swd, &c->m_len, &c->m_off);
837#endif
838 l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
839 if (l2 < 0)
840 continue;
841
842 /* compressed-data compatibility [see above] */
843 l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
844
845 lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
846 if (c->m_len >= m_len + lazy_match_min_gain) {
847 if (l3 > 0) {
848 /* code previous run */
849 op = code_run(c, op, ii, lit);
850 lit = 0;
851 /* code shortened match */
852 op = code_match(c, op, ahead, m_off);
853 } else {
854 lit += ahead;
855 assert(ii + lit == c->bp);
856 }
857 goto lazy_match_done;
858 }
859 }
860
861 assert(ii + lit + ahead == c->bp);
862
863 /* 1 - code run */
864 op = code_run(c, op, ii, lit);
865 lit = 0;
866
867 /* 2 - code match */
868 op = code_match(c, op, m_len, m_off);
869 swd->max_chain = max_chain;
870 r = find_match(c, swd, m_len, 1+ahead);
871 assert(r == 0);
872
873 lazy_match_done: ;
874 }
875
876 /* store final run */
877 if (lit > 0)
878 op = STORE_RUN(c, op, ii, lit);
879
880#if defined(LZO_EOF_CODE)
881 *op++ = M4_MARKER | 1;
882 *op++ = 0;
883 *op++ = 0;
884#endif
885
886 *out_len = op - out;
887
888 return LZO_E_OK;
889}
890
891
892/***********************************************************************
893//
894************************************************************************/
895int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
896 uint8_t *out, unsigned *out_len,
897 void *wrkmem,
898 int compression_level)
899{
900 static const struct {
901 uint16_t good_length;
902 uint16_t max_lazy;
903 uint16_t max_chain;
904 uint16_t use_best_off;
905 } c[3] = {
906 { 8, 32, 256, 0 },
907 { 32, 128, 2048, 1 },
908 { SWD_F, SWD_F, 4096, 1 } /* max. compression */
909 };
910
911 if (compression_level < 7 || compression_level > 9)
912 return LZO_E_ERROR;
913
914 compression_level -= 7;
915 return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
916 c[compression_level].good_length,
917 c[compression_level].max_lazy,
918 c[compression_level].max_chain,
919 c[compression_level].use_best_off);
920}
921
generated by cgit at 2024-05-15 09:08:59 (GMT)