CnC_Remastered_Collection

Command and Conquer: Red Alert
Log | Files | Refs | README | LICENSE

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 */