… | |
… | |
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 | |
65 | unsigned int |
61 | unsigned int |
66 | lzf_compress_best (const void *const in_data, unsigned int in_len, |
62 | lzf_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 | |