1/* lzo1f_1.c -- implementation of the LZO1F-1 compression algorithm 2 3 This file is part of the LZO real-time data compression library. 4 5 Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer 6 Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer 7 Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer 8 Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer 9 Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer 10 Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer 11 Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer 12 Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer 13 Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer 14 Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer 15 Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer 16 Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer 17 Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer 18 All Rights Reserved. 19 20 The LZO library is free software; you can redistribute it and/or 21 modify it under the terms of the GNU General Public License as 22 published by the Free Software Foundation; either version 2 of 23 the License, or (at your option) any later version. 24 25 The LZO library is distributed in the hope that it will be useful, 26 but WITHOUT ANY WARRANTY; without even the implied warranty of 27 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 28 GNU General Public License for more details. 29 30 You should have received a copy of the GNU General Public License 31 along with the LZO library; see the file COPYING. 32 If not, write to the Free Software Foundation, Inc., 33 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 34 35 Markus F.X.J. Oberhumer 36 <markus@oberhumer.com> 37 http://www.oberhumer.com/opensource/lzo/ 38 */ 39 40 41#include "lzo_conf.h" 42#include "lzo/lzo1f.h" 43 44 45/*********************************************************************** 46// 47************************************************************************/ 48 49#define M2_MAX_OFFSET 0x0800 50#define M3_MAX_OFFSET 0x3fff 51#define M3_MARKER 224 52 53 54#ifndef LZO_HASH 55#define LZO_HASH LZO_HASH_LZO_INCREMENTAL_A 56#endif 57#define D_BITS 14 58#define D_INDEX1(d,p) d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5) 59#define D_INDEX2(d,p) d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f) 60#include "lzo_dict.h" 61 62 63/*********************************************************************** 64// compress a block of data. 65************************************************************************/ 66 67static __lzo_noinline 68int do_compress ( const lzo_bytep in , lzo_uint in_len, 69 lzo_bytep out, lzo_uintp out_len, 70 lzo_voidp wrkmem ) 71{ 72 register const lzo_bytep ip; 73 lzo_bytep op; 74 const lzo_bytep const in_end = in + in_len; 75 const lzo_bytep const ip_end = in + in_len - 9; 76 const lzo_bytep ii; 77 lzo_dict_p const dict = (lzo_dict_p) wrkmem; 78 79 op = out; 80 ip = in; 81 ii = ip; 82 83 ip++; 84 for (;;) 85 { 86 register const lzo_bytep m_pos; 87 lzo_uint m_off; 88 lzo_uint m_len; 89 lzo_uint dindex; 90 lzo_uint lit; 91 92 DINDEX1(dindex,ip); 93 GINDEX(m_pos,m_off,dict,dindex,in); 94 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET)) 95 goto literal; 96#if 1 97 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) 98 goto try_match; 99 DINDEX2(dindex,ip); 100#endif 101 GINDEX(m_pos,m_off,dict,dindex,in); 102 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET)) 103 goto literal; 104 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) 105 goto try_match; 106 goto literal; 107 108 109try_match: 110#if 0 && defined(LZO_UNALIGNED_OK_2) 111 if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip) 112#else 113 if (m_pos[0] != ip[0] || m_pos[1] != ip[1]) 114#endif 115 { 116 } 117 else 118 { 119 if (m_pos[2] == ip[2]) 120 { 121 m_pos += 3; 122#if 0 123 if (m_off <= M2_MAX_OFFSET) 124 goto match; 125 if (lit <= 3) 126 goto match; 127 if (lit == 3) /* better compression, but slower */ 128 { 129 assert(op - 2 > out); op[-2] |= LZO_BYTE(3); 130 *op++ = *ii++; *op++ = *ii++; *op++ = *ii++; 131 goto code_match; 132 } 133 if (*m_pos == ip[3]) 134#endif 135 goto match; 136 } 137 } 138 139 140 /* a literal */ 141literal: 142 UPDATE_I(dict,0,dindex,ip,in); 143 if (++ip >= ip_end) 144 break; 145 continue; 146 147 148 /* a match */ 149match: 150 UPDATE_I(dict,0,dindex,ip,in); 151 /* store current literal run */ 152 lit = pd(ip,ii); 153 if (lit > 0) 154 { 155 register lzo_uint t = lit; 156 157 if (t < 4 && op > out) 158 op[-2] |= LZO_BYTE(t); 159 else if (t <= 31) 160 *op++ = LZO_BYTE(t); 161 else 162 { 163 register lzo_uint tt = t - 31; 164 165 *op++ = 0; 166 while (tt > 255) 167 { 168 tt -= 255; 169 *op++ = 0; 170 } 171 assert(tt > 0); 172 *op++ = LZO_BYTE(tt); 173 } 174 do *op++ = *ii++; while (--t > 0); 175 } 176 assert(ii == ip); 177 178 179 /* code the match */ 180 ip += 3; 181 if (*m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++ || 182 *m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++) 183 { 184 --ip; 185 m_len = pd(ip, ii); 186 assert(m_len >= 3); assert(m_len <= 8); 187 188 if (m_off <= M2_MAX_OFFSET) 189 { 190 m_off -= 1; 191 *op++ = LZO_BYTE(((m_len - 2) << 5) | ((m_off & 7) << 2)); 192 *op++ = LZO_BYTE(m_off >> 3); 193 } 194 else if (m_len == 3 && m_off <= 2*M2_MAX_OFFSET && lit > 0) 195 { 196 m_off -= 1; 197 /* m_off -= M2_MAX_OFFSET; */ 198 *op++ = LZO_BYTE(((m_off & 7) << 2)); 199 *op++ = LZO_BYTE(m_off >> 3); 200 } 201 else 202 { 203 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2)); 204 *op++ = LZO_BYTE((m_off & 63) << 2); 205 *op++ = LZO_BYTE(m_off >> 6); 206 } 207 } 208 else 209 { 210 { 211 const lzo_bytep end; 212 end = in_end; 213 while (ip < end && *m_pos == *ip) 214 m_pos++, ip++; 215 m_len = pd(ip, ii); 216 } 217 assert(m_len >= 3); 218 219 if (m_len <= 33) 220 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2)); 221 else 222 { 223 m_len -= 33; 224 *op++ = M3_MARKER | 0; 225 while (m_len > 255) 226 { 227 m_len -= 255; 228 *op++ = 0; 229 } 230 assert(m_len > 0); 231 *op++ = LZO_BYTE(m_len); 232 } 233 *op++ = LZO_BYTE((m_off & 63) << 2); 234 *op++ = LZO_BYTE(m_off >> 6); 235 } 236 237 ii = ip; 238 if (ip >= ip_end) 239 break; 240 } 241 242 243 /* store final literal run */ 244 if (pd(in_end,ii) > 0) 245 { 246 register lzo_uint t = pd(in_end,ii); 247 248 if (t < 4 && op > out) 249 op[-2] |= LZO_BYTE(t); 250 else if (t <= 31) 251 *op++ = LZO_BYTE(t); 252 else 253 { 254 register lzo_uint tt = t - 31; 255 256 *op++ = 0; 257 while (tt > 255) 258 { 259 tt -= 255; 260 *op++ = 0; 261 } 262 assert(tt > 0); 263 *op++ = LZO_BYTE(tt); 264 } 265 do *op++ = *ii++; while (--t > 0); 266 } 267 268 *out_len = pd(op, out); 269 return LZO_E_OK; 270} 271 272 273/*********************************************************************** 274// public entry point 275************************************************************************/ 276 277LZO_PUBLIC(int) 278lzo1f_1_compress ( const lzo_bytep in , lzo_uint in_len, 279 lzo_bytep out, lzo_uintp out_len, 280 lzo_voidp wrkmem ) 281{ 282 lzo_bytep op = out; 283 int r = LZO_E_OK; 284 285 if (in_len <= 0) 286 *out_len = 0; 287 else if (in_len <= 10) 288 { 289 *op++ = LZO_BYTE(in_len); 290 do *op++ = *in++; while (--in_len > 0); 291 *out_len = pd(op, out); 292 } 293 else 294 r = do_compress(in,in_len,out,out_len,wrkmem); 295 296 if (r == LZO_E_OK) 297 { 298 op = out + *out_len; 299 *op++ = M3_MARKER | 1; 300 *op++ = 0; 301 *op++ = 0; 302 *out_len += 3; 303 } 304 305 return r; 306} 307 308 309/* 310vi:ts=4:et 311*/ 312 313