liblzf/lzf_c_best.c

/*
 * Copyright (c) 2000-2012 Marc Alexander Lehmann <schmorp@schmorp.de>
 *
 * Redistribution and use in source and binary forms, with or without modifica-
 * tion, are permitted provided that the following conditions are met:
 *
 *   1.  Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *
 *   2.  Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
 * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
 * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
 * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Alternatively, the contents of this file may be used under the terms of
 * the GNU General Public License ("GPL") version 2 or any later version,
 * in which case the provisions of the GPL are applicable instead of
 * the above. If you wish to allow the use of your version of this file
 * only under the terms of the GPL and not to allow others to use your
 * version of this file under the BSD license, indicate your decision
 * by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL. If you do not delete the
 * provisions above, a recipient may use your version of this file under
 * either the BSD or the GPL.
 */

#include "lzfP.h"

#define HASH(p) (p[0] << 6) ^ (p[1] << 3) ^ p[2]

#if __GNUC__ >= 3
# define expect(expr,value)         __builtin_expect ((expr),(value))
# define inline                     inline
#else
# define expect(expr,value)         (expr)
# define inline                     static
#endif

#define expect_false(expr) expect ((expr) != 0, 0)
#define expect_true(expr)  expect ((expr) != 0, 1)

/*
 * compressed format
 *
 * 000LLLLL <L+1>    ; literal, L+1=1..33 octets
 * LLLooooo oooooooo ; backref L+1=1..7 octets, o+1=1..4096 offset
 * 111ooooo LLLLLLLL oooooooo ; backref L+8 octets, o+1=1..4096 offset
 *
 */

unsigned int
lzf_compress_best (const void *const in_data, unsigned int in_len,
                   void *out_data, unsigned int out_len
#if LZF_STATE_ARG
              , LZF_STATE_BEST state
#endif
              )
{
  const u8 *ip = (const u8 *)in_data;
        u8 *op = (u8 *)out_data;
  const u8 *in_end  = ip + in_len;
        u8 *out_end = op + out_len;

#if !LZF_STATE_ARG
  LZF_STATE_BEST state;
#endif
#define STATE state[0]

  int lit;

  if (!in_len || !out_len)
    return 0;

  lit = 0; op++; /* start run */

  lit++; *op++ = *ip++;

  while (ip < in_end - 2)
    {
      int best_l = 0;
      const u8 *best_p;
      int e = (in_end - ip < LZF_MAX_REF ? in_end - ip : LZF_MAX_REF) - 1;
      unsigned int res = ((unsigned long)ip) & (LZF_MAX_OFF - 1);
      u16 hash = HASH (ip);
      u16 diff;
      const u8 *b = ip < (u8 *)in_data + LZF_MAX_OFF ? in_data : ip - LZF_MAX_OFF;
      const u8 *p = STATE.first [hash];
      STATE.prev [res] = ip - p; /* update ptr to previous hash match */
      STATE.first [hash] = ip; /* first hash match is here */

      if (p < ip)
        while (p >= b)
          {
            if (p[2] == ip[2]) /* first two bytes almost always match */
              if (p[best_l] == ip[best_l]) /* new match must be longer than the old one to qualify */
                if (p[1] == ip[1] && p[0] == ip[0]) /* just to be sure */
                  {
                    int l = 3;

                    while (p[l] == ip[l] && l < e)
                      ++l;

                    if (l >= best_l)
                      {
                        best_p = p;
                        best_l = l;
                      }
                  }

            diff = STATE.prev [((unsigned long)p) & (LZF_MAX_OFF - 1)];
            p = diff ? p - diff : 0;
          }

      if (best_l)
        {
          int len = best_l;
          int off = ip - best_p - 1;

          if (expect_false (op + 3 + 1 >= out_end)) /* first a faster conservative test */
            if (op - !lit + 3 + 1 >= out_end) /* second the exact but rare test */
              return 0;

          op [- lit - 1] = lit - 1; /* stop run */
          op -= !lit; /* undo run if length is zero */

          len -= 2; /* len is now #octets - 1 */
          ip++;

          if (len < 7)
            {
              *op++ = (off >> 8) + (len << 5);
            }
          else
            {
              *op++ = (off >> 8) + (  7 << 5);
              *op++ = len - 7;
            }

          *op++ = off;

          lit = 0; op++; /* start run */

          ip += len + 1;

          if (expect_false (ip >= in_end - 2))
            break;

          ip -= len + 1;

          //printf (" fill %p for %d\n", ip, len);//D
          do
            {
              u16 hash = HASH (ip);
              res = ((unsigned long)ip) & (LZF_MAX_OFF - 1);

              p = STATE.first [hash];
              STATE.prev [res] = ip - p; /* update ptr to previous hash match */
              STATE.first [hash] = ip; /* first hash match is here */

              ip++;
            }
          while (len--);
        }
      else
        {
          /* one more literal byte we must copy */
          if (expect_false (op >= out_end))
            return 0;

          lit++; *op++ = *ip++;

          if (expect_false (lit == LZF_MAX_LIT))
            {
              op [- lit - 1] = lit - 1; /* stop run */
              lit = 0; op++; /* start run */
            }
        }
    }

  if (op + 3 > out_end) /* at most 3 bytes can be missing here */
    return 0;

  while (ip < in_end)
    {
      lit++; *op++ = *ip++;

      if (expect_false (lit == LZF_MAX_LIT))
        {
          op [- lit - 1] = lit - 1; /* stop run */
          lit = 0; op++; /* start run */
        }
    }

  op [- lit - 1] = lit - 1; /* end run */
  op -= !lit; /* undo run if length is zero */

  return op - (u8 *)out_data;

#undef STATE
}


Revision:	1.5
Committed:	Mon Jun 29 23:34:42 2015 UTC (8 years, 10 months ago) by root
Content type:	text/plain
Branch:	MAIN
Changes since 1.4:	+45 -40 lines
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	/*
2			* Copyright (c) 2000-2012 Marc Alexander Lehmann <schmorp@schmorp.de>
3	root	1.2	*
4	root	1.1	* Redistribution and use in source and binary forms, with or without modifica-
5			* tion, are permitted provided that the following conditions are met:
6	root	1.2	*
7	root	1.1	* 1. Redistributions of source code must retain the above copyright notice,
8			* this list of conditions and the following disclaimer.
9	root	1.2	*
10	root	1.1	* 2. Redistributions in binary form must reproduce the above copyright
11			* notice, this list of conditions and the following disclaimer in the
12			* documentation and/or other materials provided with the distribution.
13	root	1.2	*
14	root	1.1	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
15			* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
16			* CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
17			* EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
18			* CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19			* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
20			* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21			* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
22			* ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
23			* OF THE POSSIBILITY OF SUCH DAMAGE.
24			*
25			* Alternatively, the contents of this file may be used under the terms of
26			* the GNU General Public License ("GPL") version 2 or any later version,
27			* in which case the provisions of the GPL are applicable instead of
28			* the above. If you wish to allow the use of your version of this file
29			* only under the terms of the GPL and not to allow others to use your
30			* version of this file under the BSD license, indicate your decision
31			* by deleting the provisions above and replace them with the notice
32			* and other provisions required by the GPL. If you do not delete the
33			* provisions above, a recipient may use your version of this file under
34			* either the BSD or the GPL.
35			*/
36
37			#include "lzfP.h"
38
39			#define HASH(p) (p[0] << 6) ^ (p[1] << 3) ^ p[2]
40
41			#if __GNUC__ >= 3
42			# define expect(expr,value) __builtin_expect ((expr),(value))
43			# define inline inline
44			#else
45			# define expect(expr,value) (expr)
46			# define inline static
47			#endif
48
49			#define expect_false(expr) expect ((expr) != 0, 0)
50			#define expect_true(expr) expect ((expr) != 0, 1)
51
52			/*
53			* compressed format
54			*
55			* 000LLLLL <L+1> ; literal, L+1=1..33 octets
56			* LLLooooo oooooooo ; backref L+1=1..7 octets, o+1=1..4096 offset
57			* 111ooooo LLLLLLLL oooooooo ; backref L+8 octets, o+1=1..4096 offset
58			*
59			*/
60
61			unsigned int
62			lzf_compress_best (const void *const in_data, unsigned int in_len,
63	root	1.5	void *out_data, unsigned int out_len
64			#if LZF_STATE_ARG
65			, LZF_STATE_BEST state
66			#endif
67			)
68	root	1.1	{
69			const u8 ip = (const u8 )in_data;
70			u8 op = (u8 )out_data;
71			const u8 *in_end = ip + in_len;
72			u8 *out_end = op + out_len;
73
74	root	1.5	#if !LZF_STATE_ARG
75			LZF_STATE_BEST state;
76			#endif
77			#define STATE state[0]
78	root	1.1
79			int lit;
80
81			if (!in_len \|\| !out_len)
82			return 0;
83
84			lit = 0; op++; /* start run */
85
86			lit++; op++ = ip++;
87
88			while (ip < in_end - 2)
89			{
90			int best_l = 0;
91			const u8 *best_p;
92	root	1.5	int e = (in_end - ip < LZF_MAX_REF ? in_end - ip : LZF_MAX_REF) - 1;
93			unsigned int res = ((unsigned long)ip) & (LZF_MAX_OFF - 1);
94	root	1.1	u16 hash = HASH (ip);
95			u16 diff;
96	root	1.5	const u8 b = ip < (u8 )in_data + LZF_MAX_OFF ? in_data : ip - LZF_MAX_OFF;
97			const u8 *p = STATE.first [hash];
98			STATE.prev [res] = ip - p; /* update ptr to previous hash match */
99			STATE.first [hash] = ip; /* first hash match is here */
100	root	1.1
101			if (p < ip)
102	root	1.5	while (p >= b)
103			{
104			if (p[2] == ip[2]) /* first two bytes almost always match */
105			if (p[best_l] == ip[best_l]) /* new match must be longer than the old one to qualify */
106			if (p[1] == ip[1] && p[0] == ip[0]) /* just to be sure */
107			{
108			int l = 3;
109
110			while (p[l] == ip[l] && l < e)
111			++l;
112
113			if (l >= best_l)
114			{
115			best_p = p;
116			best_l = l;
117			}
118			}
119
120			diff = STATE.prev [((unsigned long)p) & (LZF_MAX_OFF - 1)];
121			p = diff ? p - diff : 0;
122			}
123	root	1.1
124			if (best_l)
125			{
126			int len = best_l;
127			int off = ip - best_p - 1;
128
129			if (expect_false (op + 3 + 1 >= out_end)) /* first a faster conservative test */
130			if (op - !lit + 3 + 1 >= out_end) /* second the exact but rare test */
131			return 0;
132
133			op [- lit - 1] = lit - 1; /* stop run */
134			op -= !lit; /* undo run if length is zero */
135
136			len -= 2; /* len is now #octets - 1 */
137			ip++;
138
139			if (len < 7)
140			{
141			*op++ = (off >> 8) + (len << 5);
142			}
143			else
144			{
145			*op++ = (off >> 8) + ( 7 << 5);
146			*op++ = len - 7;
147			}
148
149			*op++ = off;
150
151			lit = 0; op++; /* start run */
152
153			ip += len + 1;
154
155			if (expect_false (ip >= in_end - 2))
156			break;
157
158			ip -= len + 1;
159
160			//printf (" fill %p for %d\n", ip, len);//D
161			do
162			{
163			u16 hash = HASH (ip);
164	root	1.5	res = ((unsigned long)ip) & (LZF_MAX_OFF - 1);
165	root	1.1
166	root	1.5	p = STATE.first [hash];
167			STATE.prev [res] = ip - p; /* update ptr to previous hash match */
168			STATE.first [hash] = ip; /* first hash match is here */
169	root	1.1
170			ip++;
171			}
172			while (len--);
173			}
174			else
175			{
176			/* one more literal byte we must copy */
177			if (expect_false (op >= out_end))
178			return 0;
179
180			lit++; op++ = ip++;
181
182	root	1.5	if (expect_false (lit == LZF_MAX_LIT))
183	root	1.1	{
184			op [- lit - 1] = lit - 1; /* stop run */
185			lit = 0; op++; /* start run */
186			}
187			}
188			}
189
190			if (op + 3 > out_end) /* at most 3 bytes can be missing here */
191			return 0;
192
193			while (ip < in_end)
194			{
195			lit++; op++ = ip++;
196
197	root	1.5	if (expect_false (lit == LZF_MAX_LIT))
198	root	1.1	{
199			op [- lit - 1] = lit - 1; /* stop run */
200			lit = 0; op++; /* start run */
201			}
202			}
203
204			op [- lit - 1] = lit - 1; /* end run */
205			op -= !lit; /* undo run if length is zero */
206
207			return op - (u8 *)out_data;
208	root	1.5
209			#undef STATE
210	root	1.1	}
211
212	root	1.5