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] &&
306 assert(lzo_memcmp(bp,&b[node],3) == 0);
309 do {} while (++p1 < px && *p1 == *++p2);
312 assert(lzo_memcmp(bp,&b[node],i) == 0);
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;
321 s->m_len = m_len = i;
323 if (m_len == s->look)
327 if (m_len > (unsigned) s->best3[node])
329 scan_end1 = bp[m_len - 1];
336 /***********************************************************************
338 ************************************************************************/
341 static int swd_search2(lzo_swd_p s)
345 assert(s->look >= 2);
346 assert(s->m_len > 0);
348 key = s->head2[ HEAD2(s->b,s->bp) ];
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;
367 /***********************************************************************
369 ************************************************************************/
370 static void swd_findbest(lzo_swd_p s)
376 assert(s->m_len > 0);
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)
385 s->head3[key] = s->bp;
387 s->b_char = s->b[s->bp];
389 if (s->m_len >= s->look) {
393 s->best3[s->bp] = SWD_F + 1;
399 swd_search(s,node,cnt);
401 s->m_off = swd_pos2off(s,s->m_pos);
402 s->best3[s->bp] = s->m_len;
404 #if defined(SWD_BEST_OFF)
405 if (s->use_best_off) {
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);
416 swd_remove_node(s,s->rp);
419 /* add bp into HEAD2 */
420 key = HEAD2(s->b,s->bp);
421 s->head2[key] = s->bp;
430 /***********************************************************************
432 ************************************************************************/
433 static int init_match(lzo1x_999_t *c, lzo_swd_p s, uint32_t use_best_off)
446 s->use_best_off = use_best_off;
451 /***********************************************************************
453 ************************************************************************/
454 static int find_match(lzo1x_999_t *c, lzo_swd_p s,
455 unsigned this_len, unsigned skip)
460 assert(this_len >= skip);
461 swd_accept(s, this_len - skip);
463 assert(this_len <= 1);
470 memset(s->best_pos,0,sizeof(s->best_pos));
482 c->look = s->look + 1;
484 c->bp = c->ip - c->look;
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,
493 unsigned good_length,
496 uint32_t use_best_off);
499 /***********************************************************************
501 ************************************************************************/
502 static uint8_t *code_match(lzo1x_999_t *c,
503 uint8_t *op, unsigned m_len, unsigned m_off)
507 assert(m_off <= M1_MAX_OFFSET);
508 assert(c->r1_lit > 0); assert(c->r1_lit < 4);
510 *op++ = M1_MARKER | ((m_off & 3) << 2);
512 } else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) {
515 *op++ = ((m_len - 1) << 5) | ((m_off & 7) << 2);
517 assert(op[-2] >= M2_MARKER);
518 } else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4) {
520 assert(m_off > M2_MAX_OFFSET);
521 m_off -= 1 + M2_MAX_OFFSET;
522 *op++ = M1_MARKER | ((m_off & 3) << 2);
524 } else if (m_off <= M3_MAX_OFFSET) {
527 if (m_len <= M3_MAX_LEN)
528 *op++ = M3_MARKER | (m_len - 2);
531 *op++ = M3_MARKER | 0;
546 assert(m_off > 0x4000); assert(m_off <= 0xbfff);
548 k = (m_off & 0x4000) >> 11;
549 if (m_len <= M4_MAX_LEN)
550 *op++ = M4_MARKER | k | (m_len - 2);
553 *op++ = M4_MARKER | k | 0;
570 static uint8_t *STORE_RUN(lzo1x_999_t *c, uint8_t *op,
571 const uint8_t *ii, unsigned t)
573 if (op == c->out && t <= 238) {
577 } else if (t <= 18) {
580 unsigned tt = t - 18;
590 do *op++ = *ii++; while (--t > 0);
596 static uint8_t *code_run(lzo1x_999_t *c, uint8_t *op, const uint8_t *ii,
601 op = STORE_RUN(c,op,ii,lit);
611 /***********************************************************************
613 ************************************************************************/
614 static int len_of_coded_match(unsigned m_len, unsigned m_off, unsigned lit)
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)
624 if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && lit >= 4)
626 if (m_off <= M3_MAX_OFFSET) {
627 if (m_len <= M3_MAX_LEN)
630 } else if (m_off <= M4_MAX_OFFSET) {
631 if (m_len <= M4_MAX_LEN)
636 while (m_len > 255) {
644 static int min_gain(unsigned ahead, unsigned lit1,
645 unsigned lit2, int l1, int l2, int l3)
647 int lazy_match_min_gain = 0;
650 lazy_match_min_gain += ahead;
653 lazy_match_min_gain += (lit2 <= 3) ? 0 : 2;
655 lazy_match_min_gain += (lit2 <= 18) ? 0 : 1;
657 lazy_match_min_gain += (l2 - l1) * 2;
659 lazy_match_min_gain -= (ahead - l3) * 2;
661 if (lazy_match_min_gain < 0)
662 lazy_match_min_gain = 0;
664 return lazy_match_min_gain;
668 /***********************************************************************
670 ************************************************************************/
671 #if defined(SWD_BEST_OFF)
673 static void better_match(const lzo_swd_p swd,
674 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 lzo_swd_p const 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);