ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/liblzf/lzf_c_best.c
Revision: 1.6
Committed: Sun Oct 11 22:26:07 2015 UTC (8 years, 9 months ago) by root
Content type: text/plain
Branch: MAIN
CVS Tags: HEAD
Changes since 1.5: +2 -0 lines
Log Message:
*** empty log message ***

File Contents

# Content
1 /*
2 * Copyright (c) 2000-2012 Marc Alexander Lehmann <schmorp@schmorp.de>
3 *
4 * Redistribution and use in source and binary forms, with or without modifica-
5 * tion, are permitted provided that the following conditions are met:
6 *
7 * 1. Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 *
10 * 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 *
14 * 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 void *out_data, unsigned int out_len
64 #if LZF_STATE_ARG
65 , LZF_STATE_BEST state
66 #endif
67 )
68 {
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 #if !LZF_STATE_ARG
75 LZF_STATE_BEST state;
76 #endif
77 #define STATE state[0]
78
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 &state; /* avoid undefined behaviour by forcing non-register class, 6.3.2.1p2 */
89
90 while (ip < in_end - 2)
91 {
92 int best_l = 0;
93 const u8 *best_p;
94 int e = (in_end - ip < LZF_MAX_REF ? in_end - ip : LZF_MAX_REF) - 1;
95 unsigned int res = ((unsigned long)ip) & (LZF_MAX_OFF - 1);
96 u16 hash = HASH (ip);
97 u16 diff;
98 const u8 *b = ip < (u8 *)in_data + LZF_MAX_OFF ? in_data : ip - LZF_MAX_OFF;
99 const u8 *p = STATE.first [hash];
100 STATE.prev [res] = ip - p; /* update ptr to previous hash match */
101 STATE.first [hash] = ip; /* first hash match is here */
102
103 if (p < ip)
104 while (p >= b)
105 {
106 if (p[2] == ip[2]) /* first two bytes almost always match */
107 if (p[best_l] == ip[best_l]) /* new match must be longer than the old one to qualify */
108 if (p[1] == ip[1] && p[0] == ip[0]) /* just to be sure */
109 {
110 int l = 3;
111
112 while (p[l] == ip[l] && l < e)
113 ++l;
114
115 if (l >= best_l)
116 {
117 best_p = p;
118 best_l = l;
119 }
120 }
121
122 diff = STATE.prev [((unsigned long)p) & (LZF_MAX_OFF - 1)];
123 p = diff ? p - diff : 0;
124 }
125
126 if (best_l)
127 {
128 int len = best_l;
129 int off = ip - best_p - 1;
130
131 if (expect_false (op + 3 + 1 >= out_end)) /* first a faster conservative test */
132 if (op - !lit + 3 + 1 >= out_end) /* second the exact but rare test */
133 return 0;
134
135 op [- lit - 1] = lit - 1; /* stop run */
136 op -= !lit; /* undo run if length is zero */
137
138 len -= 2; /* len is now #octets - 1 */
139 ip++;
140
141 if (len < 7)
142 {
143 *op++ = (off >> 8) + (len << 5);
144 }
145 else
146 {
147 *op++ = (off >> 8) + ( 7 << 5);
148 *op++ = len - 7;
149 }
150
151 *op++ = off;
152
153 lit = 0; op++; /* start run */
154
155 ip += len + 1;
156
157 if (expect_false (ip >= in_end - 2))
158 break;
159
160 ip -= len + 1;
161
162 //printf (" fill %p for %d\n", ip, len);//D
163 do
164 {
165 u16 hash = HASH (ip);
166 res = ((unsigned long)ip) & (LZF_MAX_OFF - 1);
167
168 p = STATE.first [hash];
169 STATE.prev [res] = ip - p; /* update ptr to previous hash match */
170 STATE.first [hash] = ip; /* first hash match is here */
171
172 ip++;
173 }
174 while (len--);
175 }
176 else
177 {
178 /* one more literal byte we must copy */
179 if (expect_false (op >= out_end))
180 return 0;
181
182 lit++; *op++ = *ip++;
183
184 if (expect_false (lit == LZF_MAX_LIT))
185 {
186 op [- lit - 1] = lit - 1; /* stop run */
187 lit = 0; op++; /* start run */
188 }
189 }
190 }
191
192 if (op + 3 > out_end) /* at most 3 bytes can be missing here */
193 return 0;
194
195 while (ip < in_end)
196 {
197 lit++; *op++ = *ip++;
198
199 if (expect_false (lit == LZF_MAX_LIT))
200 {
201 op [- lit - 1] = lit - 1; /* stop run */
202 lit = 0; op++; /* start run */
203 }
204 }
205
206 op [- lit - 1] = lit - 1; /* end run */
207 op -= !lit; /* undo run if length is zero */
208
209 return op - (u8 *)out_data;
210
211 #undef STATE
212 }
213
214