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