1e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li/* 2e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * Copyright (c) 2000-2010 Marc Alexander Lehmann <schmorp@schmorp.de> 3e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 4e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * Redistribution and use in source and binary forms, with or without modifica- 5e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * tion, are permitted provided that the following conditions are met: 6e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 7e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 1. Redistributions of source code must retain the above copyright notice, 8e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * this list of conditions and the following disclaimer. 9e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 10e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 2. Redistributions in binary form must reproduce the above copyright 11e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * notice, this list of conditions and the following disclaimer in the 12e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * documentation and/or other materials provided with the distribution. 13e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 14e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED 15e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER- 16e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO 17e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE- 18e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 20e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 21e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH- 22e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 23e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * OF THE POSSIBILITY OF SUCH DAMAGE. 24e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 25e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * Alternatively, the contents of this file may be used under the terms of 26e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * the GNU General Public License ("GPL") version 2 or any later version, 27e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * in which case the provisions of the GPL are applicable instead of 28e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * the above. If you wish to allow the use of your version of this file 29e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * only under the terms of the GPL and not to allow others to use your 30e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * version of this file under the BSD license, indicate your decision 31e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * by deleting the provisions above and replace them with the notice 32e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * and other provisions required by the GPL. If you do not delete the 33e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * provisions above, a recipient may use your version of this file under 34e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * either the BSD or the GPL. 35e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li */ 36e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 37e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#include "lzfP.h" 38e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 39e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#define HSIZE (1 << (HLOG)) 40e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 41e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li/* 42e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * don't play with this unless you benchmark! 43e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * the data format is not dependent on the hash function. 44e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * the hash function might seem strange, just believe me, 45e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * it works ;) 46e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li */ 47e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#ifndef FRST 48e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define FRST(p) (((p[0]) << 8) | p[1]) 49e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define NEXT(v,p) (((v) << 8) | p[2]) 50e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# if ULTRA_FAST 51e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define IDX(h) ((( h >> (3*8 - HLOG)) - h ) & (HSIZE - 1)) 52e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# elif VERY_FAST 53e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define IDX(h) ((( h >> (3*8 - HLOG)) - h*5) & (HSIZE - 1)) 54e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# else 55e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define IDX(h) ((((h ^ (h << 5)) >> (3*8 - HLOG)) - h*5) & (HSIZE - 1)) 56e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# endif 57e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 58e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li/* 59e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * IDX works because it is very similar to a multiplicative hash, e.g. 60e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * ((h * 57321 >> (3*8 - HLOG)) & (HSIZE - 1)) 61e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * the latter is also quite fast on newer CPUs, and compresses similarly. 62e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 63e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * the next one is also quite good, albeit slow ;) 64e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * (int)(cos(h & 0xffffff) * 1e6) 65e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li */ 66e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 67e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if 0 68e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li/* original lzv-like hash function, much worse and thus slower */ 69e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define FRST(p) (p[0] << 5) ^ p[1] 70e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define NEXT(v,p) ((v) << 5) ^ p[2] 71e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define IDX(h) ((h) & (HSIZE - 1)) 72e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 73e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 74e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#define MAX_LIT (1 << 5) 75e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#define MAX_OFF (1 << 13) 76e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#define MAX_REF ((1 << 8) + (1 << 3)) 77e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 78e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if __GNUC__ >= 3 79e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define expect(expr,value) __builtin_expect ((expr),(value)) 80e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define inline inline 81e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#else 82e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define expect(expr,value) (expr) 83e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# define inline static 84e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 85e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 86e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#define expect_false(expr) expect ((expr) != 0, 0) 87e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#define expect_true(expr) expect ((expr) != 0, 1) 88e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 89e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li/* 90e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * compressed format 91e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 92e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 000LLLLL <L+1> ; literal, L+1=1..33 octets 93e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * LLLooooo oooooooo ; backref L+1=1..7 octets, o+1=1..4096 offset 94e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 111ooooo LLLLLLLL oooooooo ; backref L+8 octets, o+1=1..4096 offset 95e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * 96e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li */ 97e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 98e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Liunsigned int 99e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Lilzf_compress (const void *const in_data, unsigned int in_len, 100e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li void *out_data, unsigned int out_len 101e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if LZF_STATE_ARG 102e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li , LZF_STATE htab 103e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 104e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ) 105e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li{ 106e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if !LZF_STATE_ARG 107e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li LZF_STATE htab; 108e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 109e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li const u8 *ip = (const u8 *)in_data; 110e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li u8 *op = (u8 *)out_data; 111e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li const u8 *in_end = ip + in_len; 112e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li u8 *out_end = op + out_len; 113e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li const u8 *ref; 114e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 115e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li /* off requires a type wide enough to hold a general pointer difference. 116e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * ISO C doesn't have that (size_t might not be enough and ptrdiff_t only 117e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * works for differences within a single object). We also assume that no 118e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * no bit pattern traps. Since the only platform that is both non-POSIX 119e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * and fails to support both assumptions is windows 64 bit, we make a 120e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li * special workaround for it. 121e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li */ 122e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if defined (WIN32) && defined (_M_X64) 123e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li unsigned _int64 off; /* workaround for missing POSIX compliance */ 124e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#else 125e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li unsigned long off; 126e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 127e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li unsigned int hval; 128e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li int lit; 129e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 130e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (!in_len || !out_len) 131e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li return 0; 132e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 133e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if INIT_HTAB 134e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li memset (htab, 0, sizeof (htab)); 135e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 136e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 137e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li lit = 0; op++; /* start run */ 138e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 139e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li hval = FRST (ip); 140e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li while (ip < in_end - 2) 141e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 142e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li LZF_HSLOT *hslot; 143e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 144e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li hval = NEXT (hval, ip); 145e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li hslot = htab + IDX (hval); 146e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ref = *hslot + LZF_HSLOT_BIAS; *hslot = ip - LZF_HSLOT_BIAS; 147e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 148e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (1 149e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if INIT_HTAB 150e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li && ref < ip /* the next test will actually take care of this, but this is faster */ 151e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 152e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li && (off = ip - ref - 1) < MAX_OFF 153e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li && ref > (u8 *)in_data 154e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li && ref[2] == ip[2] 155e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if STRICT_ALIGN 156e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li && ((ref[1] << 8) | ref[0]) == ((ip[1] << 8) | ip[0]) 157e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#else 158e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li && *(u16 *)ref == *(u16 *)ip 159e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 160e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ) 161e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 162e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li /* match found at *ref++ */ 163e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li unsigned int len = 2; 164e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li unsigned int maxlen = in_end - ip - len; 165e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li maxlen = maxlen > MAX_REF ? MAX_REF : maxlen; 166e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 167e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (expect_false (op + 3 + 1 >= out_end)) /* first a faster conservative test */ 168e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (op - !lit + 3 + 1 >= out_end) /* second the exact but rare test */ 169e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li return 0; 170e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 171e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li op [- lit - 1] = lit - 1; /* stop run */ 172e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li op -= !lit; /* undo run if length is zero */ 173e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 174e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li for (;;) 175e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 176e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (expect_true (maxlen > 16)) 177e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 178e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 179e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 180e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 181e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 182e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 183e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 184e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 185e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 186e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 187e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 188e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 189e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 190e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 191e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 192e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 193e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 194e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 195e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 196e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; if (ref [len] != ip [len]) break; 197e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 198e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 199e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li do 200e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len++; 201e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li while (len < maxlen && ref[len] == ip[len]); 202e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 203e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li break; 204e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 205e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 206e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li len -= 2; /* len is now #octets - 1 */ 207e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ip++; 208e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 209e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (len < 7) 210e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 211e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li *op++ = (off >> 8) + (len << 5); 212e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 213e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li else 214e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 215e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li *op++ = (off >> 8) + ( 7 << 5); 216e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li *op++ = len - 7; 217e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 218e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 219e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li *op++ = off; 220e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 221e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li lit = 0; op++; /* start run */ 222e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 223e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ip += len + 1; 224e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 225e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (expect_false (ip >= in_end - 2)) 226e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li break; 227e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 228e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#if ULTRA_FAST || VERY_FAST 229e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li --ip; 230e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# if VERY_FAST && !ULTRA_FAST 231e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li --ip; 232e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# endif 233e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li hval = FRST (ip); 234e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 235e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li hval = NEXT (hval, ip); 236e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li htab[IDX (hval)] = ip - LZF_HSLOT_BIAS; 237e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ip++; 238e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 239e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# if VERY_FAST && !ULTRA_FAST 240e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li hval = NEXT (hval, ip); 241e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li htab[IDX (hval)] = ip - LZF_HSLOT_BIAS; 242e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ip++; 243e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li# endif 244e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#else 245e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ip -= len + 1; 246e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 247e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li do 248e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 249e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li hval = NEXT (hval, ip); 250e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li htab[IDX (hval)] = ip - LZF_HSLOT_BIAS; 251e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li ip++; 252e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 253e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li while (len--); 254e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li#endif 255e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 256e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li else 257e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 258e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li /* one more literal byte we must copy */ 259e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (expect_false (op >= out_end)) 260e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li return 0; 261e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 262e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li lit++; *op++ = *ip++; 263e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 264e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (expect_false (lit == MAX_LIT)) 265e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 266e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li op [- lit - 1] = lit - 1; /* stop run */ 267e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li lit = 0; op++; /* start run */ 268e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 269e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 270e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 271e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 272e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (op + 3 > out_end) /* at most 3 bytes can be missing here */ 273e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li return 0; 274e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 275e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li while (ip < in_end) 276e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 277e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li lit++; *op++ = *ip++; 278e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 279e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li if (expect_false (lit == MAX_LIT)) 280e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li { 281e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li op [- lit - 1] = lit - 1; /* stop run */ 282e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li lit = 0; op++; /* start run */ 283e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 284e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li } 285e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 286e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li op [- lit - 1] = lit - 1; /* end run */ 287e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li op -= !lit; /* undo run if length is zero */ 288e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 289e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li return op - (u8 *)out_data; 290e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li} 291e54acca48ba1ab84ac7c693de45ed31ac3f311c2David Li 292