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) (* (bb__aliased_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);
471 memset(s->best_pos, 0, sizeof(s->best_pos));
483 c->look = s->look + 1;
485 c->bp = c->ip - c->look;
490 /* this is a public functions, but there is no prototype in a header file */
491 static int lzo1x_999_compress_internal(const uint8_t *in , unsigned in_len,
492 uint8_t *out, unsigned *out_len,
494 unsigned good_length,
497 uint32_t use_best_off);
500 /***********************************************************************
502 ************************************************************************/
503 static uint8_t *code_match(lzo1x_999_t *c,
504 uint8_t *op, unsigned m_len, unsigned m_off)
508 assert(m_off <= M1_MAX_OFFSET);
509 assert(c->r1_lit > 0);
510 assert(c->r1_lit < 4);
512 *op++ = M1_MARKER | ((m_off & 3) << 2);
514 } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
517 *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
519 assert(op[-2] >= M2_MARKER);
520 } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
522 assert(m_off > M2_MAX_OFFSET);
523 m_off -= 1 + M2_MAX_OFFSET;
524 *op++ = M1_MARKER | ((m_off & 3) << 2);
526 } else if (m_off <= M3_MAX_OFFSET) {
529 if (m_len <= M3_MAX_LEN)
530 *op++ = M3_MARKER | (m_len - 2);
533 *op++ = M3_MARKER | 0;
534 while (m_len > 255) {
547 assert(m_off > 0x4000);
548 assert(m_off <= 0xbfff);
550 k = (m_off & 0x4000) >> 11;
551 if (m_len <= M4_MAX_LEN)
552 *op++ = M4_MARKER | k | (m_len - 2);
555 *op++ = M4_MARKER | k | 0;
556 while (m_len > 255) {
571 static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
572 const uint8_t *ii, unsigned t)
574 if (op == c->out && t <= 238) {
578 } else if (t <= 18) {
581 unsigned tt = t - 18;
591 do *op++ = *ii++; while (--t > 0);
597 static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
602 op = STORE_RUN(c, op, ii, lit);
612 /***********************************************************************
614 ************************************************************************/
615 static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
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)
625 if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
627 if (m_off <= M3_MAX_OFFSET) {
628 if (m_len <= M3_MAX_LEN)
631 } else if (m_off <= M4_MAX_OFFSET) {
632 if (m_len <= M4_MAX_LEN)
637 while (m_len > 255) {
645 static int min_gain(unsigned ahead, unsigned lit1,
646 unsigned lit2, int l1, int l2, int l3)
648 int lazy_match_min_gain = 0;
651 lazy_match_min_gain += ahead;
654 lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
656 lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
658 lazy_match_min_gain += (l2 - l1) * 2;
660 lazy_match_min_gain -= (ahead - l3) * 2;
662 if (lazy_match_min_gain < 0)
663 lazy_match_min_gain = 0;
665 return lazy_match_min_gain;
669 /***********************************************************************
671 ************************************************************************/
672 #if defined(SWD_BEST_OFF)
674 static void better_match(const lzo_swd_p swd,
675 unsigned *m_len, unsigned *m_off)
677 if (*m_len <= M2_MIN_LEN)
680 if (*m_off <= M2_MAX_OFFSET)
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
689 *m_off = swd->best_off[*m_len];
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
699 *m_off = swd->best_off[*m_len];
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
708 *m_off = swd->best_off[*m_len];
715 /***********************************************************************
717 ************************************************************************/
718 static int lzo1x_999_compress_internal(const uint8_t *in, unsigned in_len,
719 uint8_t *out, unsigned *out_len,
721 unsigned good_length,
724 uint32_t use_best_off)
729 unsigned m_len, m_off;
731 lzo1x_999_t *const c = &cc;
732 const lzo_swd_p swd = (lzo_swd_p) wrkmem;
737 c->in_end = in + in_len;
741 ii = c->ip; /* point to start of literal run */
745 r = init_match(c, swd, use_best_off);
748 swd->max_chain = max_chain;
750 r = find_match(c, swd, 0, 0);
754 while (c->look > 0) {
762 assert(c->bp == c->ip - c->look);
766 assert(ii + lit == c->bp);
767 assert(swd->b_char == *(c->bp));
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() ]
775 || (m_len == 2 && op == out)
776 || (op == out && lit == 0)
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)
790 swd->max_chain = max_chain;
791 r = find_match(c, swd, 1, 0);
797 #if defined(SWD_BEST_OFF)
798 if (swd->use_best_off)
799 better_match(swd, &m_len, &m_off);
802 /* shall we try a lazy match ? */
804 if (m_len >= max_lazy) {
809 /* yes, try a lazy match */
810 l1 = len_of_coded_match(m_len, m_off, lit);
812 max_ahead = LZO_MIN(2, (unsigned)l1 - 1);
816 while (ahead < max_ahead && c->look > m_len) {
817 int lazy_match_min_gain;
819 if (m_len >= good_length)
820 swd->max_chain = max_chain >> 2;
822 swd->max_chain = max_chain;
823 r = find_match(c, swd, 1, 0);
828 assert(ii + lit + ahead == c->bp);
830 if (c->m_len < m_len)
832 if (c->m_len == m_len && c->m_off >= m_off)
834 #if defined(SWD_BEST_OFF)
835 if (swd->use_best_off)
836 better_match(swd, &c->m_len, &c->m_off);
838 l2 = len_of_coded_match(c->m_len, c->m_off, lit+ahead);
842 /* compressed-data compatibility [see above] */
843 l3 = (op == out) ? -1 : len_of_coded_match(ahead, m_off, lit);
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) {
848 /* code previous run */
849 op = code_run(c, op, ii, lit);
851 /* code shortened match */
852 op = code_match(c, op, ahead, m_off);
855 assert(ii + lit == c->bp);
857 goto lazy_match_done;
861 assert(ii + lit + ahead == c->bp);
864 op = code_run(c, op, ii, lit);
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);
876 /* store final run */
878 op = STORE_RUN(c, op, ii, lit);
880 #if defined(LZO_EOF_CODE)
881 *op++ = M4_MARKER | 1;
892 /***********************************************************************
894 ************************************************************************/
895 int lzo1x_999_compress_level(const uint8_t *in, unsigned in_len,
896 uint8_t *out, unsigned *out_len,
898 int compression_level)
900 static const struct {
901 uint16_t good_length;
904 uint16_t use_best_off;
907 { 32, 128, 2048, 1 },
908 { SWD_F, SWD_F, 4096, 1 } /* max. compression */
911 if (compression_level < 7 || compression_level > 9)
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);