ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/liblzf/lzf_c_best.c
(Generate patch)

Comparing liblzf/lzf_c_best.c (file contents):
Revision 1.4 by root, Sat Jun 27 19:50:25 2015 UTC vs.
Revision 1.5 by root, Mon Jun 29 23:34:42 2015 UTC

… …
36 36
37#include "lzfP.h" 37#include "lzfP.h"
38 38
39#define HASH(p) (p[0] << 6) ^ (p[1] << 3) ^ p[2] 39#define HASH(p) (p[0] << 6) ^ (p[1] << 3) ^ p[2]
40 40
41#define MAX_LIT (1 << 5)
42#define MAX_OFF (1 << 13)
43#define MAX_REF ((1 << 8) + (1 << 3))
44
45#if __GNUC__ >= 3 41#if __GNUC__ >= 3
46# define expect(expr,value) __builtin_expect ((expr),(value)) 42# define expect(expr,value) __builtin_expect ((expr),(value))
47# define inline inline 43# define inline inline
48#else 44#else
49# define expect(expr,value) (expr) 45# define expect(expr,value) (expr)
… …
62 * 58 *
63 */ 59 */
64 60
65unsigned int 61unsigned int
66lzf_compress_best (const void *const in_data, unsigned int in_len, 62lzf_compress_best (const void *const in_data, unsigned int in_len,
67 void *out_data, unsigned int out_len) 63 void *out_data, unsigned int out_len
64#if LZF_STATE_ARG
65 , LZF_STATE_BEST state
66#endif
67 )
68{ 68{
69 const u8 *ip = (const u8 *)in_data; 69 const u8 *ip = (const u8 *)in_data;
70 u8 *op = (u8 *)out_data; 70 u8 *op = (u8 *)out_data;
71 const u8 *in_end = ip + in_len; 71 const u8 *in_end = ip + in_len;
72 u8 *out_end = op + out_len; 72 u8 *out_end = op + out_len;
73 73
74 const u8 *first [1 << (6+8)]; /* most recent occurance of a match */ 74#if !LZF_STATE_ARG
75 u16 prev [MAX_OFF]; /* how many bytes to go backwards for the next match */ 75 LZF_STATE_BEST state;
76#endif
77#define STATE state[0]
76 78
77 int lit; 79 int lit;
78 80
79 if (!in_len || !out_len) 81 if (!in_len || !out_len)
80 return 0; 82 return 0;
… …
85 87
86 while (ip < in_end - 2) 88 while (ip < in_end - 2)
87 { 89 {
88 int best_l = 0; 90 int best_l = 0;
89 const u8 *best_p; 91 const u8 *best_p;
90 int e = (in_end - ip < MAX_REF ? in_end - ip : MAX_REF) - 1; 92 int e = (in_end - ip < LZF_MAX_REF ? in_end - ip : LZF_MAX_REF) - 1;
91 unsigned int res = ((unsigned long)ip) & (MAX_OFF - 1); 93 unsigned int res = ((unsigned long)ip) & (LZF_MAX_OFF - 1);
92 u16 hash = HASH (ip); 94 u16 hash = HASH (ip);
93 u16 diff; 95 u16 diff;
94 const u8 *b = ip < (u8 *)in_data + MAX_OFF ? in_data : ip - MAX_OFF; 96 const u8 *b = ip < (u8 *)in_data + LZF_MAX_OFF ? in_data : ip - LZF_MAX_OFF;
95 const u8 *p = first [hash]; 97 const u8 *p = STATE.first [hash];
96 prev [res] = ip - p; /* update ptr to previous hash match */ 98 STATE.prev [res] = ip - p; /* update ptr to previous hash match */
97 first [hash] = ip; /* first hash match is here */ 99 STATE.first [hash] = ip; /* first hash match is here */
98 100
99 if (p < ip) 101 if (p < ip)
100 while (p >= b) 102 while (p >= b)
101 { 103 {
102 if (p[2] == ip[2]) /* first two bytes almost always match */ 104 if (p[2] == ip[2]) /* first two bytes almost always match */
103 if (p[best_l] == ip[best_l]) /* new match must be longer than the old one to qualify */ 105 if (p[best_l] == ip[best_l]) /* new match must be longer than the old one to qualify */
104 if (p[1] == ip[1] && p[0] == ip[0]) /* just to be sure */ 106 if (p[1] == ip[1] && p[0] == ip[0]) /* just to be sure */
105 { 107 {
106 int l = 3; 108 int l = 3;
107 109
108 while (p[l] == ip[l] && l < e) 110 while (p[l] == ip[l] && l < e)
109 ++l; 111 ++l;
110 112
111 if (l >= best_l) 113 if (l >= best_l)
112 { 114 {
113 best_p = p; 115 best_p = p;
114 best_l = l; 116 best_l = l;
115 } 117 }
116 } 118 }
117 119
118 diff = prev [((unsigned long)p) & (MAX_OFF - 1)]; 120 diff = STATE.prev [((unsigned long)p) & (LZF_MAX_OFF - 1)];
119 p = diff ? p - diff : 0; 121 p = diff ? p - diff : 0;
120 } 122 }
121 123
122 if (best_l) 124 if (best_l)
123 { 125 {
124 int len = best_l; 126 int len = best_l;
125 int off = ip - best_p - 1; 127 int off = ip - best_p - 1;
… …
157 159
158 //printf (" fill %p for %d\n", ip, len);//D 160 //printf (" fill %p for %d\n", ip, len);//D
159 do 161 do
160 { 162 {
161 u16 hash = HASH (ip); 163 u16 hash = HASH (ip);
162 res = ((unsigned long)ip) & (MAX_OFF - 1); 164 res = ((unsigned long)ip) & (LZF_MAX_OFF - 1);
163 165
164 p = first [hash]; 166 p = STATE.first [hash];
165 prev [res] = ip - p; /* update ptr to previous hash match */ 167 STATE.prev [res] = ip - p; /* update ptr to previous hash match */
166 first [hash] = ip; /* first hash match is here */ 168 STATE.first [hash] = ip; /* first hash match is here */
167 169
168 ip++; 170 ip++;
169 } 171 }
170 while (len--); 172 while (len--);
171 } 173 }
… …
175 if (expect_false (op >= out_end)) 177 if (expect_false (op >= out_end))
176 return 0; 178 return 0;
177 179
178 lit++; *op++ = *ip++; 180 lit++; *op++ = *ip++;
179 181
180 if (expect_false (lit == MAX_LIT)) 182 if (expect_false (lit == LZF_MAX_LIT))
181 { 183 {
182 op [- lit - 1] = lit - 1; /* stop run */ 184 op [- lit - 1] = lit - 1; /* stop run */
183 lit = 0; op++; /* start run */ 185 lit = 0; op++; /* start run */
184 } 186 }
185 } 187 }
… …
190 192
191 while (ip < in_end) 193 while (ip < in_end)
192 { 194 {
193 lit++; *op++ = *ip++; 195 lit++; *op++ = *ip++;
194 196
195 if (expect_false (lit == MAX_LIT)) 197 if (expect_false (lit == LZF_MAX_LIT))
196 { 198 {
197 op [- lit - 1] = lit - 1; /* stop run */ 199 op [- lit - 1] = lit - 1; /* stop run */
198 lit = 0; op++; /* start run */ 200 lit = 0; op++; /* start run */
199 } 201 }
200 } 202 }
201 203
202 op [- lit - 1] = lit - 1; /* end run */ 204 op [- lit - 1] = lit - 1; /* end run */
203 op -= !lit; /* undo run if length is zero */ 205 op -= !lit; /* undo run if length is zero */
204 206
205 return op - (u8 *)out_data; 207 return op - (u8 *)out_data;
208
209#undef STATE
206} 210}
207 211
212

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines