| 1 |
/*************************************************************************** |
| 2 |
* Copyright (C) 2005-2019 by the FIFE team * |
| 3 |
* http://www.fifengine.net * |
| 4 |
* This file is part of FIFE. * |
| 5 |
* * |
| 6 |
* FIFE is free software; you can redistribute it and/or * |
| 7 |
* modify it under the terms of the GNU Lesser General Public * |
| 8 |
* License as published by the Free Software Foundation; either * |
| 9 |
* version 2.1 of the License, or (at your option) any later version. * |
| 10 |
* * |
| 11 |
* This library is distributed in the hope that it will be useful, * |
| 12 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of * |
| 13 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * |
| 14 |
* Lesser General Public License for more details. * |
| 15 |
* * |
| 16 |
* You should have received a copy of the GNU Lesser General Public * |
| 17 |
* License along with this library; if not, write to the * |
| 18 |
* Free Software Foundation, Inc., * |
| 19 |
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * |
| 20 |
***************************************************************************/ |
| 21 |
|
| 22 |
// Standard C++ library includes |
| 23 |
#include <algorithm> |
| 24 |
|
| 25 |
// 3rd party library includes |
| 26 |
|
| 27 |
// FIFE includes |
| 28 |
#include "vfs/raw/rawdata.h" |
| 29 |
#include "util/base/exception.h" |
| 30 |
|
| 31 |
#include "lzssdecoder.h" |
| 32 |
|
| 33 |
// just a quick&dirty wrapper around anchorites implementation - needs to be replaced with our own LZSS implementation |
| 34 |
namespace FIFE { |
| 35 |
|
| 36 |
LZSSDecoder::LZSSDecoder() {} |
| 37 |
LZSSDecoder::~LZSSDecoder() {} |
| 38 |
|
| 39 |
|
| 40 |
void LZSSDecoder::decode(RawData* input, uint8_t* output, const uint32_t outputsize) { |
| 41 |
|
| 42 |
m_outindex = 0; |
| 43 |
m_outlen = outputsize; |
| 44 |
|
| 45 |
while (m_outindex < outputsize) { |
| 46 |
uint16_t blockdesc = input->read16Big(); |
| 47 |
uint16_t bytesToRead = blockdesc & 0x7fff; |
| 48 |
|
| 49 |
if (blockdesc & 0x8000) { // uncompressed |
| 50 |
input->readInto(output + m_outindex, bytesToRead); |
| 51 |
m_outindex += bytesToRead; |
| 52 |
} else { |
| 53 |
// Allocate +2 bytes so that on corrupt data the LZSS |
| 54 |
// decoder won't crash the input buffer. |
| 55 |
std::vector<uint8_t> indata(bytesToRead + 2); |
| 56 |
input->readInto(&indata[0], bytesToRead); |
| 57 |
LZSSDecode(&indata[0], bytesToRead, output); |
| 58 |
// Note outindex is advanced inside LZSSDecode. |
| 59 |
} |
| 60 |
|
| 61 |
} |
| 62 |
} |
| 63 |
|
| 64 |
void LZSSDecoder::LZSSDecode(uint8_t* in , int64_t len, uint8_t* out) { |
| 65 |
const int64_t c_nRingBufferSize = 4096; |
| 66 |
const int64_t c_nMatchLengthUpperLimit = 18; |
| 67 |
const int64_t c_nThreshold = 2; |
| 68 |
|
| 69 |
char buffer[c_nRingBufferSize + c_nMatchLengthUpperLimit - 1]; |
| 70 |
int32_t ibuf = 0; |
| 71 |
int32_t c; |
| 72 |
|
| 73 |
int32_t i; |
| 74 |
int32_t j; |
| 75 |
int32_t k; |
| 76 |
int32_t r; |
| 77 |
|
| 78 |
uint32_t flags; |
| 79 |
|
| 80 |
for (i = 0; i < c_nRingBufferSize - c_nMatchLengthUpperLimit; i++) { |
| 81 |
buffer[i] = ' '; |
| 82 |
} |
| 83 |
|
| 84 |
r = c_nRingBufferSize - c_nMatchLengthUpperLimit; |
| 85 |
flags = 0; |
| 86 |
while ( ibuf < len ) { |
| 87 |
if (((flags >>= 1) & 256) == 0) { |
| 88 |
c = in[ibuf++]; |
| 89 |
flags = c | 0xff00;/* uses higher byte cleverly to count eight */ |
| 90 |
} |
| 91 |
|
| 92 |
if (flags & 1) { |
| 93 |
c = in[ibuf++]; |
| 94 |
out[m_outindex++] = c; |
| 95 |
|
| 96 |
buffer[r++] = c; |
| 97 |
r &= (c_nRingBufferSize - 1); |
| 98 |
} else { |
| 99 |
i = in[ibuf++]; |
| 100 |
j = in[ibuf++]; |
| 101 |
|
| 102 |
i |= ((j & 0xf0) << 4); |
| 103 |
j = (j & 0x0f) + c_nThreshold; |
| 104 |
|
| 105 |
for (k = 0; k <= j; k++) { |
| 106 |
c = buffer[(i + k) & (c_nRingBufferSize - 1)]; |
| 107 |
|
| 108 |
out[m_outindex++] = c; |
| 109 |
|
| 110 |
buffer[r++] = c; |
| 111 |
r &= (c_nRingBufferSize - 1); |
| 112 |
} |
| 113 |
} |
| 114 |
} |
| 115 |
} |
| 116 |
|
| 117 |
|
| 118 |
} |