LZO1X_C.CPP (8308B)
1 // 2 // Copyright 2020 Electronic Arts Inc. 3 // 4 // TiberianDawn.DLL and RedAlert.dll and corresponding source code is free 5 // software: you can redistribute it and/or modify it under the terms of 6 // the GNU General Public License as published by the Free Software Foundation, 7 // either version 3 of the License, or (at your option) any later version. 8 9 // TiberianDawn.DLL and RedAlert.dll and corresponding source code is distributed 10 // in the hope that it will be useful, but with permitted additional restrictions 11 // under Section 7 of the GPL. See the GNU General Public License in LICENSE.TXT 12 // distributed with this program. You should have received a copy of the 13 // GNU General Public License along with permitted additional restrictions 14 // with this program. If not, see https://github.com/electronicarts/CnC_Remastered_Collection 15 16 /* lzo1x_c.c -- standalone LZO1X-1 compressor 17 18 This file is part of the LZO real-time data compression library. 19 20 Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer 21 22 The LZO library is free software; you can redistribute it and/or 23 modify it under the terms of the GNU Library General Public 24 License as published by the Free Software Foundation; either 25 version 2 of the License, or (at your option) any later version. 26 27 The LZO library is distributed in the hope that it will be useful, 28 but WITHOUT ANY WARRANTY; without even the implied warranty of 29 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 30 Library General Public License for more details. 31 32 You should have received a copy of the GNU Library General Public 33 License along with the LZO library; see the file COPYING.LIB. 34 If not, write to the Free Software Foundation, Inc., 35 675 Mass Ave, Cambridge, MA 02139, USA. 36 37 Markus F.X.J. Oberhumer 38 markus.oberhumer@jk.uni-linz.ac.at 39 */ 40 41 42 #include "lzo1x.h" 43 #ifndef NDEBUG 44 #define NDEBUG 45 #endif 46 #include <assert.h> 47 #include "lzo_conf.h" 48 49 #if !defined(LZO1X) && !defined(LZO1Y) 50 # define LZO1X 51 #endif 52 53 54 /*********************************************************************** 55 // 56 ************************************************************************/ 57 58 #define M1_MAX_OFFSET 0x0400 59 #if defined(LZO1X) 60 #define M2_MAX_OFFSET 0x0800 61 #elif defined(LZO1Y) 62 #define M2_MAX_OFFSET 0x0400 63 #endif 64 #define M3_MAX_OFFSET 0x4000 65 #define M4_MAX_OFFSET 0xbfff 66 67 #define MX_MAX_OFFSET (M1_MAX_OFFSET + M2_MAX_OFFSET) 68 69 #define M1_MARKER 0 70 #define M2_MARKER 64 71 #define M3_MARKER 32 72 #define M4_MARKER 16 73 74 75 #define _DV2(p,shift1,shift2) \ 76 (((( (lzo_uint)(p[2]) << shift1) ^ p[1]) << shift2) ^ p[0]) 77 #define DVAL_NEXT(dv,p) \ 78 dv ^= p[-1]; dv = (((dv) >> 5) ^ ((lzo_uint)(p[2]) << (2*5))) 79 #define _DV(p,shift) _DV2(p,shift,shift) 80 #define DVAL_FIRST(dv,p) dv = _DV((p),5) 81 #define _DINDEX(dv,p) ((40799u * (dv)) >> 5) 82 #define DINDEX(dv,p) (((_DINDEX(dv,p)) & 0x3fff) << 0) 83 #define UPDATE_D(dict,cycle,dv,p) dict[ DINDEX(dv,p) ] = (p) 84 #define UPDATE_I(dict,cycle,index,p) dict[index] = (p) 85 86 87 /*********************************************************************** 88 // compress a block of data. 89 ************************************************************************/ 90 91 static int do_compress(const lzo_byte *in , lzo_uint in_len, 92 lzo_byte *out, lzo_uint *out_len, 93 lzo_voidp wrkmem ) 94 { 95 register const lzo_byte *ip; 96 lzo_uint dv; 97 lzo_byte *op; 98 const lzo_byte * const in_end = in + in_len; 99 const lzo_byte * const ip_end = in + in_len - 9 - 4; 100 const lzo_byte *ii; 101 const lzo_bytepp const dict = (const lzo_bytepp) wrkmem; 102 103 op = out; 104 ip = in; 105 ii = ip; 106 107 DVAL_FIRST(dv,ip); UPDATE_D(dict,cycle,dv,ip); ip++; 108 DVAL_NEXT(dv,ip); UPDATE_D(dict,cycle,dv,ip); ip++; 109 DVAL_NEXT(dv,ip); UPDATE_D(dict,cycle,dv,ip); ip++; 110 DVAL_NEXT(dv,ip); UPDATE_D(dict,cycle,dv,ip); ip++; 111 112 while (1) { 113 register const lzo_byte *m_pos; 114 lzo_uint m_len; 115 lzo_ptrdiff_t m_off; 116 lzo_uint lit; 117 118 lzo_uint dindex = DINDEX(dv,ip); 119 m_pos = dict[dindex]; 120 UPDATE_I(dict,cycle,dindex,ip); 121 122 123 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) { 124 } 125 #if defined(LZO_UNALIGNED_OK_2) 126 else 127 if (* (unsigned short *) m_pos != * (unsigned short *) ip) 128 #else 129 else 130 if (m_pos[0] != ip[0] || m_pos[1] != ip[1]) 131 #endif 132 { 133 } else { 134 if (m_pos[2] == ip[2]) { 135 lit = ip - ii; 136 m_pos += 3; 137 if (m_off <= M2_MAX_OFFSET) 138 goto match; 139 140 /* better compression, but slower */ 141 if (lit == 3) { 142 assert(op - 2 > out); op[-2] |= LZO_BYTE(3); 143 *op++ = *ii++; *op++ = *ii++; *op++ = *ii++; 144 goto code_match; 145 } 146 147 if (*m_pos == ip[3]) { 148 goto match; 149 } 150 } else { 151 /* still need a better way for finding M1 matches */ 152 } 153 } 154 155 156 /* a literal */ 157 ++ip; 158 if (ip >= ip_end) { 159 break; 160 } 161 DVAL_NEXT(dv,ip); 162 continue; 163 164 165 /* a match */ 166 167 match: 168 169 /* store current literal run */ 170 if (lit > 0) { 171 register lzo_uint t = lit; 172 173 if (t <= 3) { 174 assert(op - 2 > out); 175 op[-2] |= LZO_BYTE(t); 176 } else { 177 if (t <= 18) { 178 *op++ = LZO_BYTE(t - 3); 179 } else { 180 register lzo_uint tt = t - 18; 181 182 *op++ = 0; 183 while (tt > 255) { 184 tt -= 255; 185 *op++ = 0; 186 } 187 assert(tt > 0); 188 *op++ = LZO_BYTE(tt); 189 } 190 } 191 192 do { 193 *op++ = *ii++; 194 } while (--t > 0); 195 } 196 197 198 /* code the match */ 199 code_match: 200 assert(ii == ip); 201 ip += 3; 202 if (*m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++ || 203 *m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++) 204 { 205 --ip; 206 m_len = ip - ii; 207 assert(m_len >= 3); assert(m_len <= 8); 208 209 if (m_off <= M2_MAX_OFFSET) { 210 m_off -= 1; 211 *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2)); 212 *op++ = LZO_BYTE(m_off >> 3); 213 } else { 214 if (m_off <= M3_MAX_OFFSET) { 215 m_off -= 1; 216 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2)); 217 goto m3_m4_offset; 218 } else { 219 m_off -= 0x4000; 220 assert(m_off > 0); assert(m_off <= 0x7fff); 221 *op++ = LZO_BYTE(M4_MARKER | 222 ((m_off & 0x4000) >> 11) | (m_len - 2)); 223 goto m3_m4_offset; 224 } 225 } 226 } else { 227 const lzo_byte *end; 228 end = in_end; 229 while (ip < end && *m_pos == *ip) { 230 m_pos++; 231 ip++; 232 } 233 m_len = (ip - ii); 234 assert(m_len >= 3); 235 236 if (m_off <= M3_MAX_OFFSET) { 237 m_off -= 1; 238 if (m_len <= 33) { 239 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2)); 240 } else { 241 m_len -= 33; 242 *op++ = M3_MARKER | 0; 243 goto m3_m4_len; 244 } 245 } else { 246 m_off -= 0x4000; 247 assert(m_off > 0); assert(m_off <= 0x7fff); 248 if (m_len <= 9) { 249 *op++ = LZO_BYTE(M4_MARKER | 250 ((m_off & 0x4000) >> 11) | (m_len - 2)); 251 } else { 252 m_len -= 9; 253 *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11)); 254 m3_m4_len: 255 while (m_len > 255) { 256 m_len -= 255; 257 *op++ = 0; 258 } 259 assert(m_len > 0); 260 *op++ = LZO_BYTE(m_len); 261 } 262 } 263 264 m3_m4_offset: 265 *op++ = LZO_BYTE((m_off & 63) << 2); 266 *op++ = LZO_BYTE(m_off >> 6); 267 } 268 269 ii = ip; 270 if (ip >= ip_end) { 271 break; 272 } 273 DVAL_FIRST(dv,ip); 274 } 275 276 /* store final literal run */ 277 if (in_end - ii > 0) { 278 register lzo_uint t = in_end - ii; 279 280 if (op == out && t <= 238) { 281 *op++ = LZO_BYTE(17 + t); 282 } else { 283 if (t <= 3) { 284 op[-2] |= LZO_BYTE(t); 285 } else { 286 if (t <= 18) { 287 *op++ = LZO_BYTE(t - 3); 288 } else { 289 register lzo_uint tt = t - 18; 290 291 *op++ = 0; 292 while (tt > 255) { 293 tt -= 255; 294 *op++ = 0; 295 } 296 assert(tt > 0); 297 *op++ = LZO_BYTE(tt); 298 } 299 } 300 } 301 do { 302 *op++ = *ii++; 303 } while (--t > 0); 304 } 305 306 *out_len = op - out; 307 return LZO_E_OK; 308 } 309 310 311 /*********************************************************************** 312 // public entry point 313 ************************************************************************/ 314 315 int lzo1x_1_compress ( const lzo_byte *in , lzo_uint in_len, 316 lzo_byte *out, lzo_uint *out_len, 317 lzo_voidp wrkmem ) 318 { 319 lzo_byte *op = out; 320 int r = LZO_E_OK; 321 322 if (in_len <= 0) 323 *out_len = 0; 324 else if (in_len <= 9 + 4) 325 { 326 *op++ = LZO_BYTE(17 + in_len); 327 do *op++ = *in++; while (--in_len > 0); 328 *out_len = op - out; 329 } 330 else 331 r = do_compress(in,in_len,out,out_len,wrkmem); 332 333 if (r == LZO_E_OK) 334 { 335 op = out + *out_len; 336 *op++ = M4_MARKER | 1; 337 *op++ = 0; 338 *op++ = 0; 339 *out_len += 3; 340 } 341 342 return r; 343 } 344 345 346 /* 347 vi:ts=4 348 */