1 /* lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm
3 This file is part of the LZO real-time data compression library.
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
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.
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.
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.
35 Markus F.X.J. Oberhumer
36 <markus@oberhumer.com>
37 http://www.oberhumer.com/opensource/lzo/
41 /* The following is probably only safe on Intel-compatible processors ... */
42 #define LZO_UNALIGNED_OK_2
43 #define LZO_UNALIGNED_OK_4
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))
51 /***********************************************************************
53 ************************************************************************/
54 #define SWD_N M4_MAX_OFFSET /* size of ring buffer */
55 #define SWD_F 2048 /* upper limit for match length */
57 #define SWD_BEST_OFF (LZO_MAX3(M2_MAX_LEN, M3_MAX_LEN, M4_MAX_LEN) + 1)
62 unsigned look; /* bytes in lookahead buffer */
70 const uint8_t *in_end;
77 #define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
79 /* lzo_swd.c -- sliding window dictionary */
81 /***********************************************************************
83 ************************************************************************/
84 #define SWD_UINT_MAX USHRT_MAX
87 # define SWD_HSIZE 16384
90 # define SWD_MAX_CHAIN 2048
94 ( ((0x9f5f * ((((b[p]<<5)^b[p+1])<<5) ^ b[p+2])) >> 5) & (SWD_HSIZE-1) )
96 #if defined(LZO_UNALIGNED_OK_2)
97 # define HEAD2(b,p) (* (uint16_t *) &(b[p]))
99 # define HEAD2(b,p) (b[p] ^ ((unsigned)b[p+1]<<8))
101 #define NIL2 SWD_UINT_MAX
103 typedef struct lzo_swd {
104 /* public - "built-in" */
106 /* public - configuration */
110 /* public - output */
115 #if defined(SWD_BEST_OFF)
116 unsigned best_off[SWD_BEST_OFF];
122 #if defined(SWD_BEST_OFF)
123 unsigned best_pos[SWD_BEST_OFF];
127 unsigned ip; /* input pointer (lookahead) */
128 unsigned bp; /* buffer pointer */
129 unsigned rp; /* remove pointer */
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];
141 uint16_t head2[65536L];
143 } lzo_swd_t, *lzo_swd_p;
145 #define SIZEOF_LZO_SWD_T (sizeof(lzo_swd_t))
148 /* Access macro for head3.
149 * head3[key] may be uninitialized, but then its value will never be used.
151 #define s_get_head3(s,key) s->head3[key]
154 /***********************************************************************
156 ************************************************************************/
157 #define B_SIZE (SWD_N + SWD_F)
159 static int swd_init(lzo_swd_p s)
162 s->node_count = SWD_N;
164 memset(s->llen3, 0, sizeof(s->llen3[0]) * (unsigned)SWD_HSIZE);
166 memset(s->head2, 0xff, sizeof(s->head2[0]) * 65536L);
167 assert(s->head2[0] == NIL2);
174 assert(s->ip + SWD_F <= B_SIZE);
175 s->look = (unsigned) (s->c->in_end - s->c->ip);
179 memcpy(&s->b[s->ip], s->c->ip, s->look);
187 if (s->rp >= s->node_count)
188 s->rp -= s->node_count;
190 s->rp += B_SIZE - s->node_count;
195 #define swd_pos2off(s,pos) \
196 (s->bp > (pos) ? s->bp - (pos) : B_SIZE - ((pos) - s->bp))
199 /***********************************************************************
201 ************************************************************************/
202 static void swd_getbyte(lzo_swd_p s)
206 if ((c = getbyte(*(s->c))) < 0) {
212 s->b_wrap[s->ip] = c;
214 if (++s->ip == B_SIZE)
216 if (++s->bp == B_SIZE)
218 if (++s->rp == B_SIZE)
223 /***********************************************************************
224 // remove node from lists
225 ************************************************************************/
226 static void swd_remove_node(lzo_swd_p s, unsigned node)
228 if (s->node_count == 0) {
231 key = HEAD3(s->b,node);
232 assert(s->llen3[key] > 0);
236 key = HEAD2(s->b,node);
237 assert(s->head2[key] != NIL2);
238 if ((unsigned) s->head2[key] == node)
239 s->head2[key] = NIL2;
246 /***********************************************************************
248 ************************************************************************/
249 static void swd_accept(lzo_swd_p s, unsigned n)
251 assert(n <= s->look);
256 swd_remove_node(s,s->rp);
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;
264 assert(s->llen3[key] <= SWD_N);
267 /* add bp into HEAD2 */
268 key = HEAD2(s->b, s->bp);
269 s->head2[key] = s->bp;
277 /***********************************************************************
279 ************************************************************************/
280 static void swd_search(lzo_swd_p s, unsigned node, unsigned cnt)
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;
291 assert(s->m_len > 0);
293 scan_end1 = bp[m_len - 1];
294 for ( ; cnt-- > 0; node = s->succ3[node]) {
299 assert(m_len < s->look);
301 if (p2[m_len - 1] == scan_end1
302 && p2[m_len] == p1[m_len]
307 assert(lzo_memcmp(bp, &b[node], 3) == 0);
310 do {} while (++p1 < px && *p1 == *++p2);
313 assert(lzo_memcmp(bp, &b[node], i) == 0);
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;
322 s->m_len = m_len = i;
324 if (m_len == s->look)
328 if (m_len > (unsigned) s->best3[node])
330 scan_end1 = bp[m_len - 1];
337 /***********************************************************************
339 ************************************************************************/
342 static int swd_search2(lzo_swd_p s)
346 assert(s->look >= 2);
347 assert(s->m_len > 0);
349 key = s->head2[HEAD2(s->b, s->bp)];
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;
368 /***********************************************************************
370 ************************************************************************/
371 static void swd_findbest(lzo_swd_p s)
377 assert(s->m_len > 0);
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)
386 s->head3[key] = s->bp;
388 s->b_char = s->b[s->bp];
390 if (s->m_len >= s->look) {
394 s->best3[s->bp] = SWD_F + 1;
400 swd_search(s, node, cnt);
402 s->m_off = swd_pos2off(s,s->m_pos);
403 s->best3[s->bp] = s->m_len;
405 #if defined(SWD_BEST_OFF)
406 if (s->use_best_off) {
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);
418 swd_remove_node(s,s->rp);
421 /* add bp into HEAD2 */
422 key = HEAD2(s->b, s->bp);
423 s->head2[key] = s->bp;
432 /***********************************************************************
434 ************************************************************************/
435 static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
448 s->use_best_off = use_best_off;
453 /***********************************************************************
455 ************************************************************************/
456 static int find_match(lzo1x_999_t *c, lzo_swd_p s,
457 unsigned this_len, unsigned skip)
462 assert(this_len >= skip);
463 swd_accept(s, this_len - skip);
465 assert(this_len <= 1);
472 memset(s->best_pos, 0, sizeof(s->best_pos));
484 c->look = s->look + 1;
486 c->bp = c->ip - c->look;
491 /* this is a public functions, but there is no prototype in a header file */
492 static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
493 uint8_t *out, unsigned *out_len,
495 unsigned good_length,
498 uint32_t use_best_off);
501 /***********************************************************************
503 ************************************************************************/
504 static uint8_t *code_match(lzo1x_999_t *c,
505 uint8_t *op, unsigned m_len, unsigned m_off)
509 assert(m_off <= M1_MAX_OFFSET);
510 assert(c->r1_lit > 0);
511 assert(c->r1_lit < 4);
513 *op++ = M1_MARKER | ((m_off & 3) << 2);
515 } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
518 *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
520 assert(op[-2] >= M2_MARKER);
521 } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
523 assert(m_off > M2_MAX_OFFSET);
524 m_off -= 1 + M2_MAX_OFFSET;
525 *op++ = M1_MARKER | ((m_off & 3) << 2);
527 } else if (m_off <= M3_MAX_OFFSET) {
530 if (m_len <= M3_MAX_LEN)
531 *op++ = M3_MARKER | (m_len - 2);
534 *op++ = M3_MARKER | 0;
535 while (m_len > 255) {
548 assert(m_off > 0x4000);
549 assert(m_off <= 0xbfff);
551 k = (m_off & 0x4000) >> 11;
552 if (m_len <= M4_MAX_LEN)
553 *op++ = M4_MARKER | k | (m_len - 2);
556 *op++ = M4_MARKER | k | 0;
557 while (m_len > 255) {
572 static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
573 const uint8_t *ii, unsigned t)
575 if (op == c->out && t <= 238) {
579 } else if (t <= 18) {
582 unsigned tt = t - 18;
592 do *op++ = *ii++; while (--t > 0);
598 static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
603 op = STORE_RUN(c, op, ii, lit);
613 /***********************************************************************
615 ************************************************************************/
616 static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
623 return (m_off <= M1_MAX_OFFSET && lit > 0 && lit < 4) ? 2 : -1;
624 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
626 if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
628 if (m_off <= M3_MAX_OFFSET) {
629 if (m_len <= M3_MAX_LEN)
632 } else if (m_off <= M4_MAX_OFFSET) {
633 if (m_len <= M4_MAX_LEN)
638 while (m_len > 255) {
646 static int min_gain(unsigned ahead, unsigned lit1,
647 unsigned lit2, int l1, int l2, int l3)
649 int lazy_match_min_gain = 0;
652 lazy_match_min_gain += ahead;
655 lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
657 lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
659 lazy_match_min_gain += (l2 - l1) * 2;
661 lazy_match_min_gain -= (ahead - l3) * 2;
663 if (lazy_match_min_gain < 0)
664 lazy_match_min_gain = 0;
666 return lazy_match_min_gain;
670 /***********************************************************************
672 ************************************************************************/
673 #if defined(SWD_BEST_OFF)
675 static void better_match(const lzo_swd_p swd,
676 unsigned *m_len, unsigned *m_off)
679 if (*m_len <= M2_MIN_LEN)
682 if (*m_off <= M2_MAX_OFFSET)
686 if (*m_off > M2_MAX_OFFSET
687 && *m_len >= M2_MIN_LEN + 1 && *m_len <= M2_MAX_LEN + 1
688 && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M2_MAX_OFFSET
691 *m_off = swd->best_off[*m_len];
696 if (*m_off > M3_MAX_OFFSET
697 && *m_len >= M4_MAX_LEN + 1 && *m_len <= M2_MAX_LEN + 2
698 && swd->best_off[*m_len-2] && swd->best_off[*m_len-2] <= M2_MAX_OFFSET
701 *m_off = swd->best_off[*m_len];
705 if (*m_off > M3_MAX_OFFSET
706 && *m_len >= M4_MAX_LEN + 1 && *m_len <= M3_MAX_LEN + 1
707 && swd->best_off[*m_len-1] && swd->best_off[*m_len-1] <= M3_MAX_OFFSET
710 *m_off = swd->best_off[*m_len];
717 /***********************************************************************
719 ************************************************************************/
720 static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
721 uint8_t *out, unsigned *out_len,
723 unsigned good_length,
726 uint32_t use_best_off)
731 unsigned m_len, m_off;
733 lzo1x_999_t *const c = &cc;
734 const lzo_swd_p swd = (lzo_swd_p) wrkmem;
739 c->in_end = in + in_len;
743 ii = c->ip; /* point to start of literal run */
747 r = init_match(c, swd, use_best_off);
750 swd->max_chain = max_chain;
752 r = find_match(c, swd, 0, 0);
756 while (c->look > 0) {
764 assert(c->bp == c->ip - c->look);
768 assert(ii + lit == c->bp);
769 assert(swd->b_char == *(c->bp));
772 || (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4))
773 /* Do not accept this match for compressed-data compatibility
774 * with LZO v1.01 and before
775 * [ might be a problem for decompress() and optimize() ]
777 || (m_len == 2 && op == out)
778 || (op == out && lit == 0)
783 else if (m_len == M2_MIN_LEN) {
784 /* compression ratio improves if we code a literal in some cases */
785 if (m_off > MX_MAX_OFFSET && lit >= 4)
792 swd->max_chain = max_chain;
793 r = find_match(c, swd, 1, 0);
799 #if defined(SWD_BEST_OFF)
800 if (swd->use_best_off)
801 better_match(swd, &m_len, &m_off);
804 /* shall we try a lazy match ? */
806 if (m_len >= max_lazy) {
811 /* yes, try a lazy match */
812 l1 = len_of_coded_match(m_len, m_off, lit);
814 max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
818 while (ahead < max_ahead && c->look > m_len) {
819 int lazy_match_min_gain;
821 if (m_len >= good_length)
822 swd->max_chain = max_chain >> 2;
824 swd->max_chain = max_chain;
825 r = find_match(c, swd, 1, 0);
830 assert(ii + lit + ahead == c->bp);
832 if (c->m_len < m_len)
834 if (c->m_len == m_len && c->m_off >= m_off)
836 #if defined(SWD_BEST_OFF)
837 if (swd->use_best_off)
838 better_match(swd, &c->m_len, &c->m_off);
840 l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
844 /* compressed-data compatibility [see above] */
845 l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
847 lazy_match_min_gain = min_gain(ahead, lit, lit+ahead, l1, l2, l3);
848 if (c->m_len >= m_len + lazy_match_min_gain) {
850 /* code previous run */
851 op = code_run(c, op, ii, lit);
853 /* code shortened match */
854 op = code_match(c, op, ahead, m_off);
857 assert(ii + lit == c->bp);
859 goto lazy_match_done;
863 assert(ii + lit + ahead == c->bp);
866 op = code_run(c, op, ii, lit);
870 op = code_match(c, op, m_len, m_off);
871 swd->max_chain = max_chain;
872 r = find_match(c, swd, m_len, 1+ahead);
878 /* store final run */
880 op = STORE_RUN(c, op, ii, lit);
882 #if defined(LZO_EOF_CODE)
883 *op++ = M4_MARKER | 1;
894 /***********************************************************************
896 ************************************************************************/
897 int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
898 uint8_t *out, unsigned *out_len,
900 int compression_level)
902 static const struct {
903 uint16_t good_length;
906 uint16_t use_best_off;
909 { 32, 128, 2048, 1 },
910 { SWD_F, SWD_F, 4096, 1 } /* max. compression */
913 if (compression_level < 7 || compression_level > 9)
916 compression_level -= 7;
917 return lzo1x_999_compress_internal(in, in_len, out, out_len, wrkmem,
918 c[compression_level].good_length,
919 c[compression_level].max_lazy,
920 c[compression_level].max_chain,
921 c[compression_level].use_best_off);