1 /* 2 * Copyright (c) 2000-2008 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 #if defined(_KERNEL) || defined (_STANDALONE) 38 #include <lib/libkern/libkern.h> 39 #include "lzfP.h" 40 #else 41 #include "lzf.h" 42 #endif 43 44 #define HSIZE (1 << (LZF_HLOG)) 45 46 /* 47 * don't play with this unless you benchmark! 48 * decompression is not dependent on the hash function 49 * the hashing function might seem strange, just believe me 50 * it works ;) 51 */ 52 #ifndef FRST 53 # define FRST(p) (((p[0]) << 8) | p[1]) 54 # define NEXT(v,p) (((v) << 8) | p[2]) 55 # if ULTRA_FAST 56 # define IDX(h) ((( h >> (3*8 - LZF_HLOG)) - h ) & (HSIZE - 1)) 57 # elif VERY_FAST 58 # define IDX(h) ((( h >> (3*8 - LZF_HLOG)) - h*5) & (HSIZE - 1)) 59 # else 60 # define IDX(h) ((((h ^ (h << 5)) >> (3*8 - LZF_HLOG)) - h*5) & (HSIZE - 1)) 61 # endif 62 #endif 63 /* 64 * IDX works because it is very similar to a multiplicative hash, e.g. 65 * ((h * 57321 >> (3*8 - LZF_HLOG)) & (HSIZE - 1)) 66 * the latter is also quite fast on newer CPUs, and compresses similarly. 67 * 68 * the next one is also quite good, albeit slow ;) 69 * (int)(cos(h & 0xffffff) * 1e6) 70 */ 71 72 #if 0 73 /* original lzv-like hash function, much worse and thus slower */ 74 # define FRST(p) (p[0] << 5) ^ p[1] 75 # define NEXT(v,p) ((v) << 5) ^ p[2] 76 # define IDX(h) ((h) & (HSIZE - 1)) 77 #endif 78 79 #define MAX_LIT (1 << 5) 80 #define MAX_OFF (1 << 13) 81 #define MAX_REF ((1 << 8) + (1 << 3)) 82 83 #if __GNUC__ >= 3 84 # define expect(expr,value) __builtin_expect ((expr),(value)) 85 # define inline inline 86 #else 87 # define expect(expr,value) (expr) 88 # define inline static 89 #endif 90 91 #define expect_false(expr) expect ((expr) != 0, 0) 92 #define expect_true(expr) expect ((expr) != 0, 1) 93 94 /* 95 * compressed format 96 * 97 * 000LLLLL <L+1> ; literal 98 * LLLooooo oooooooo ; backref L 99 * 111ooooo LLLLLLLL oooooooo ; backref L+7 100 * 101 */ 102 103 unsigned int 104 lzf_compress_r (const void *const in_data, unsigned int in_len, 105 void *out_data, unsigned int out_len, LZF_STATE htab) 106 { 107 const u8 **hslot; 108 const u8 *ip = (const u8 *)in_data; 109 u8 *op = (u8 *)out_data; 110 const u8 *in_end = ip + in_len; 111 u8 *out_end = op + out_len; 112 const u8 *ref; 113 114 /* off requires a type wide enough to hold a general pointer difference. 115 * ISO C doesn't have that (size_t might not be enough and ptrdiff_t only 116 * works for differences within a single object). We also assume that no 117 * no bit pattern traps. Since the only platform that is both non-POSIX 118 * and fails to support both assumptions is windows 64 bit, we make a 119 * special workaround for it. 120 */ 121 #if defined (WIN32) && defined (_M_X64) 122 unsigned _int64 off; /* workaround for missing POSIX compliance */ 123 #else 124 unsigned long off; 125 #endif 126 unsigned int hval; 127 int lit; 128 129 if (!in_len || !out_len) 130 return 0; 131 132 #if INIT_HTAB 133 memset (htab, 0, sizeof (htab)); 134 # if 0 135 for (hslot = htab; hslot < htab + HSIZE; hslot++) 136 *hslot++ = ip; 137 # endif 138 #endif 139 140 lit = 0; op++; /* start run */ 141 142 hval = FRST (ip); 143 while (ip < in_end - 2) 144 { 145 hval = NEXT (hval, ip); 146 hslot = htab + IDX (hval); 147 ref = *hslot; *hslot = ip; 148 149 if (/*CONSTCOND*/1 150 #if INIT_HTAB 151 && ref < ip /* the next test will actually take care of this, but this is faster */ 152 #endif 153 && (off = ip - ref - 1) < MAX_OFF 154 && ip + 4 < in_end 155 && ref > (const u8 *)in_data 156 #if STRICT_ALIGN 157 && ref[0] == ip[0] 158 && ref[1] == ip[1] 159 && ref[2] == ip[2] 160 #else 161 && *(const u16 *)(const void *)ref == *(const u16 *)(const void *)ip 162 && ref[2] == ip[2] 163 #endif 164 ) 165 { 166 /* match found at *ref++ */ 167 unsigned int len = 2; 168 unsigned int maxlen = (unsigned)(in_end - ip) - len; 169 maxlen = maxlen > MAX_REF ? MAX_REF : maxlen; 170 171 if (expect_false (op + 3 + 1 >= out_end)) /* first a faster conservative test */ 172 if (op - !lit + 3 + 1 >= out_end) /* second the exact but rare test */ 173 return 0; 174 175 op [- lit - 1] = lit - 1; /* stop run */ 176 op -= !lit; /* undo run if length is zero */ 177 178 for (;;) 179 { 180 if (expect_true (maxlen > 16)) 181 { 182 len++; if (ref [len] != ip [len]) break; 183 len++; if (ref [len] != ip [len]) break; 184 len++; if (ref [len] != ip [len]) break; 185 len++; if (ref [len] != ip [len]) break; 186 187 len++; if (ref [len] != ip [len]) break; 188 len++; if (ref [len] != ip [len]) break; 189 len++; if (ref [len] != ip [len]) break; 190 len++; if (ref [len] != ip [len]) break; 191 192 len++; if (ref [len] != ip [len]) break; 193 len++; if (ref [len] != ip [len]) break; 194 len++; if (ref [len] != ip [len]) break; 195 len++; if (ref [len] != ip [len]) break; 196 197 len++; if (ref [len] != ip [len]) break; 198 len++; if (ref [len] != ip [len]) break; 199 len++; if (ref [len] != ip [len]) break; 200 len++; if (ref [len] != ip [len]) break; 201 } 202 203 do 204 len++; 205 while (len < maxlen && ref[len] == ip[len]); 206 207 break; 208 } 209 210 len -= 2; /* len is now #octets - 1 */ 211 ip++; 212 213 if (len < 7) 214 { 215 *op++ = (unsigned char)((off >> 8) + (len << 5)); 216 } 217 else 218 { 219 *op++ = (unsigned char)((off >> 8) + ( 7 << 5)); 220 *op++ = len - 7; 221 } 222 223 *op++ = (unsigned char)off; 224 lit = 0; op++; /* start run */ 225 226 ip += len + 1; 227 228 if (expect_false (ip >= in_end - 2)) 229 break; 230 231 #if ULTRA_FAST || VERY_FAST 232 --ip; 233 # if VERY_FAST && !ULTRA_FAST 234 --ip; 235 # endif 236 hval = FRST (ip); 237 238 hval = NEXT (hval, ip); 239 htab[IDX (hval)] = ip; 240 ip++; 241 242 # if VERY_FAST && !ULTRA_FAST 243 hval = NEXT (hval, ip); 244 htab[IDX (hval)] = ip; 245 ip++; 246 # endif 247 #else 248 ip -= len + 1; 249 250 do 251 { 252 hval = NEXT (hval, ip); 253 htab[IDX (hval)] = ip; 254 ip++; 255 } 256 while (len--); 257 #endif 258 } 259 else 260 { 261 /* one more literal byte we must copy */ 262 if (expect_false (op >= out_end)) 263 return 0; 264 265 lit++; *op++ = *ip++; 266 267 /*LINTED*/ 268 if (expect_false (lit == MAX_LIT)) 269 { 270 op [- lit - 1] = lit - 1; /* stop run */ 271 lit = 0; op++; /* start run */ 272 } 273 } 274 } 275 276 if (op + 3 > out_end) /* at most 3 bytes can be missing here */ 277 return 0; 278 279 while (ip < in_end) 280 { 281 lit++; *op++ = *ip++; 282 283 /*LINTED*/ 284 if (expect_false (lit == MAX_LIT)) 285 { 286 op [- lit - 1] = lit - 1; /* stop run */ 287 lit = 0; op++; /* start run */ 288 } 289 } 290 291 op [- lit - 1] = lit - 1; /* end run */ 292 op -= !lit; /* undo run if length is zero */ 293 294 return (unsigned)(op - (u8 *)out_data); 295 } 296