AxioDL
/
lzokay
mirror of https://github.com/AxioDL/lzokay.git
2
0
Fork 0
Code Issues Packages Projects Releases Wiki Activity
lzokay/lzokay.cpp

647 lines
20 KiB
C++
Raw Permalink Blame History

#include "lzokay.hpp"
#include <cstring>
#include <algorithm>
#include <iterator>
/*
* Based on documentation from the Linux sources: Documentation/lzo.txt
* https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/Documentation/lzo.txt
*/
namespace lzokay {
#if _WIN32
#define HOST_BIG_ENDIAN 0
#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
#define HOST_BIG_ENDIAN 1
#else
#define HOST_BIG_ENDIAN 0
#endif
#if HOST_BIG_ENDIAN
static uint16_t get_le16(const uint8_t* p) {
uint16_t val = *reinterpret_cast<const uint16_t*>(p);
#if __GNUC__
return __builtin_bswap16(val);
#elif _WIN32
return _byteswap_ushort(val);
#else
return (val = (val << 8) | ((val >> 8) & 0xFF));
#endif
}
#else
static uint16_t get_le16(const uint8_t* p) {
return *reinterpret_cast<const uint16_t*>(p);
}
#endif
constexpr std::size_t Max255Count = std::size_t(~0) / 255 - 2;
#define NEEDS_IN(count) \
if (inp + (count) > inp_end) { \
dst_size = outp - dst; \
return EResult::InputOverrun; \
}
#define NEEDS_OUT(count) \
if (outp + (count) > outp_end) { \
dst_size = outp - dst; \
return EResult::OutputOverrun; \
}
#define CONSUME_ZERO_BYTE_LENGTH \
std::size_t offset; \
{ \
const uint8_t *old_inp = inp; \
while (*inp == 0) ++inp; \
offset = inp - old_inp; \
if (offset > Max255Count) { \
dst_size = outp - dst; \
return EResult::Error; \
} \
}
#define WRITE_ZERO_BYTE_LENGTH(length) \
{ \
std::size_t l; \
for (l = length; l > 255; l -= 255) { *outp++ = 0; } \
*outp++ = l; \
}
constexpr uint32_t M1MaxOffset = 0x0400;
constexpr uint32_t M2MaxOffset = 0x0800;
constexpr uint32_t M3MaxOffset = 0x4000;
constexpr uint32_t M4MaxOffset = 0xbfff;
constexpr uint32_t M1MinLen = 2;
constexpr uint32_t M1MaxLen = 2;
constexpr uint32_t M2MinLen = 3;
constexpr uint32_t M2MaxLen = 8;
constexpr uint32_t M3MinLen = 3;
constexpr uint32_t M3MaxLen = 33;
constexpr uint32_t M4MinLen = 3;
constexpr uint32_t M4MaxLen = 9;
constexpr uint32_t M1Marker = 0x0;
constexpr uint32_t M2Marker = 0x40;
constexpr uint32_t M3Marker = 0x20;
constexpr uint32_t M4Marker = 0x10;
constexpr uint32_t MaxMatchByLengthLen = 34; /* Max M3 len + 1 */
EResult decompress(const uint8_t* src, std::size_t src_size,
uint8_t* dst, std::size_t init_dst_size,
std::size_t& dst_size) {
dst_size = init_dst_size;
if (src_size < 3) {
dst_size = 0;
return EResult::InputOverrun;
}
const uint8_t* inp = src;
const uint8_t* inp_end = src + src_size;
uint8_t* outp = dst;
uint8_t* outp_end = dst + dst_size;
uint8_t* lbcur;
std::size_t lblen;
std::size_t state = 0;
std::size_t nstate = 0;
/* First byte encoding */
if (*inp >= 22) {
/* 22..255 : copy literal string
* length = (byte - 17) = 4..238
* state = 4 [ don't copy extra literals ]
* skip byte
*/
std::size_t len = *inp++ - uint8_t(17);
NEEDS_IN(len)
NEEDS_OUT(len)
for (std::size_t i = 0; i < len; ++i)
*outp++ = *inp++;
state = 4;
} else if (*inp >= 18) {
/* 18..21 : copy 0..3 literals
* state = (byte - 17) = 0..3 [ copy <state> literals ]
* skip byte
*/
nstate = *inp++ - uint8_t(17);
state = nstate;
NEEDS_IN(nstate)
NEEDS_OUT(nstate)
for (std::size_t i = 0; i < nstate; ++i)
*outp++ = *inp++;
}
/* 0..17 : follow regular instruction encoding, see below. It is worth
* noting that codes 16 and 17 will represent a block copy from
* the dictionary which is empty, and that they will always be
* invalid at this place.
*/
while (true) {
NEEDS_IN(1)
uint8_t inst = *inp++;
if (inst & 0xC0) {
/* [M2]
* 1 L L D D D S S (128..255)
* Copy 5-8 bytes from block within 2kB distance
* state = S (copy S literals after this block)
* length = 5 + L
* Always followed by exactly one byte : H H H H H H H H
* distance = (H << 3) + D + 1
*
* 0 1 L D D D S S (64..127)
* Copy 3-4 bytes from block within 2kB distance
* state = S (copy S literals after this block)
* length = 3 + L
* Always followed by exactly one byte : H H H H H H H H
* distance = (H << 3) + D + 1
*/
NEEDS_IN(1)
lbcur = outp - ((*inp++ << 3) + ((inst >> 2) & 0x7) + 1);
lblen = std::size_t(inst >> 5) + 1;
nstate = inst & uint8_t(0x3);
} else if (inst & M3Marker) {
/* [M3]
* 0 0 1 L L L L L (32..63)
* Copy of small block within 16kB distance (preferably less than 34B)
* length = 2 + (L ?: 31 + (zero_bytes * 255) + non_zero_byte)
* Always followed by exactly one LE16 : D D D D D D D D : D D D D D D S S
* distance = D + 1
* state = S (copy S literals after this block)
*/
lblen = std::size_t(inst & uint8_t(0x1f)) + 2;
if (lblen == 2) {
CONSUME_ZERO_BYTE_LENGTH
NEEDS_IN(1)
lblen += offset * 255 + 31 + *inp++;
}
NEEDS_IN(2)
nstate = get_le16(inp);
inp += 2;
lbcur = outp - ((nstate >> 2) + 1);
nstate &= 0x3;
} else if (inst & M4Marker) {
/* [M4]
* 0 0 0 1 H L L L (16..31)
* Copy of a block within 16..48kB distance (preferably less than 10B)
* length = 2 + (L ?: 7 + (zero_bytes * 255) + non_zero_byte)
* Always followed by exactly one LE16 : D D D D D D D D : D D D D D D S S
* distance = 16384 + (H << 14) + D
* state = S (copy S literals after this block)
* End of stream is reached if distance == 16384
*/
lblen = std::size_t(inst & uint8_t(0x7)) + 2;
if (lblen == 2) {
CONSUME_ZERO_BYTE_LENGTH
NEEDS_IN(1)
lblen += offset * 255 + 7 + *inp++;
}
NEEDS_IN(2)
nstate = get_le16(inp);
inp += 2;
lbcur = outp - (((inst & 0x8) << 11) + (nstate >> 2));
nstate &= 0x3;
if (lbcur == outp)
break; /* Stream finished */
lbcur -= 16384;
} else {
/* [M1] Depends on the number of literals copied by the last instruction. */
if (state == 0) {
/* If last instruction did not copy any literal (state == 0), this
* encoding will be a copy of 4 or more literal, and must be interpreted
* like this :
*
* 0 0 0 0 L L L L (0..15) : copy long literal string
* length = 3 + (L ?: 15 + (zero_bytes * 255) + non_zero_byte)
* state = 4 (no extra literals are copied)
*/
std::size_t len = inst + 3;
if (len == 3) {
CONSUME_ZERO_BYTE_LENGTH
NEEDS_IN(1)
len += offset * 255 + 15 + *inp++;
}
/* copy_literal_run */
NEEDS_IN(len)
NEEDS_OUT(len)
for (std::size_t i = 0; i < len; ++i)
*outp++ = *inp++;
state = 4;
continue;
} else if (state != 4) {
/* If last instruction used to copy between 1 to 3 literals (encoded in
* the instruction's opcode or distance), the instruction is a copy of a
* 2-byte block from the dictionary within a 1kB distance. It is worth
* noting that this instruction provides little savings since it uses 2
* bytes to encode a copy of 2 other bytes but it encodes the number of
* following literals for free. It must be interpreted like this :
*
* 0 0 0 0 D D S S (0..15) : copy 2 bytes from <= 1kB distance
* length = 2
* state = S (copy S literals after this block)
* Always followed by exactly one byte : H H H H H H H H
* distance = (H << 2) + D + 1
*/
NEEDS_IN(1)
nstate = inst & uint8_t(0x3);
lbcur = outp - ((inst >> 2) + (*inp++ << 2) + 1);
lblen = 2;
} else {
/* If last instruction used to copy 4 or more literals (as detected by
* state == 4), the instruction becomes a copy of a 3-byte block from the
* dictionary from a 2..3kB distance, and must be interpreted like this :
*
* 0 0 0 0 D D S S (0..15) : copy 3 bytes from 2..3 kB distance
* length = 3
* state = S (copy S literals after this block)
* Always followed by exactly one byte : H H H H H H H H
* distance = (H << 2) + D + 2049
*/
NEEDS_IN(1)
nstate = inst & uint8_t(0x3);
lbcur = outp - ((inst >> 2) + (*inp++ << 2) + 2049);
lblen = 3;
}
}
if (lbcur < dst) {
dst_size = outp - dst;
return EResult::LookbehindOverrun;
}
NEEDS_IN(nstate)
NEEDS_OUT(lblen + nstate)
/* Copy lookbehind */
for (std::size_t i = 0; i < lblen; ++i)
*outp++ = *lbcur++;
state = nstate;
/* Copy literal */
for (std::size_t i = 0; i < nstate; ++i)
*outp++ = *inp++;
}
dst_size = outp - dst;
if (lblen != 3) /* Ensure terminating M4 was encountered */
return EResult::Error;
if (inp == inp_end)
return EResult::Success;
else if (inp < inp_end)
return EResult::InputNotConsumed;
else
return EResult::InputOverrun;
}
struct State {
const uint8_t* src;
const uint8_t* src_end;
const uint8_t* inp;
uint32_t wind_sz;
uint32_t wind_b;
uint32_t wind_e;
uint32_t cycle1_countdown;
const uint8_t* bufp;
uint32_t buf_sz;
/* Access next input byte and advance both ends of circular buffer */
void get_byte(uint8_t* buf) {
if (inp >= src_end) {
if (wind_sz > 0)
--wind_sz;
buf[wind_e] = 0;
if (wind_e < DictBase::MaxMatchLen)
buf[DictBase::BufSize + wind_e] = 0;
} else {
buf[wind_e] = *inp;
if (wind_e < DictBase::MaxMatchLen)
buf[DictBase::BufSize + wind_e] = *inp;
++inp;
}
if (++wind_e == DictBase::BufSize)
wind_e = 0;
if (++wind_b == DictBase::BufSize)
wind_b = 0;
}
uint32_t pos2off(uint32_t pos) const {
return wind_b > pos ? wind_b - pos : DictBase::BufSize - (pos - wind_b);
}
};
class DictImpl : public DictBase {
public:
struct Match3Impl : DictBase::Match3 {
static uint32_t make_key(const uint8_t* data) {
return ((0x9f5f * (((uint32_t(data[0]) << 5 ^ uint32_t(data[1])) << 5) ^ data[2])) >> 5) & 0x3fff;
}
uint16_t get_head(uint32_t key) const {
return (chain_sz[key] == 0) ? uint16_t(UINT16_MAX) : head[key];
}
void init() {
std::fill(std::begin(chain_sz), std::end(chain_sz), 0);
}
void remove(uint32_t pos, const uint8_t* b) {
--chain_sz[make_key(b + pos)];
}
void advance(State& s, uint32_t& match_pos, uint32_t& match_count, const uint8_t* b) {
uint32_t key = make_key(b + s.wind_b);
match_pos = chain[s.wind_b] = get_head(key);
match_count = chain_sz[key]++;
if (match_count > DictBase::MaxMatchLen)
match_count = DictBase::MaxMatchLen;
head[key] = uint16_t(s.wind_b);
}
void skip_advance(State& s, const uint8_t* b) {
uint32_t key = make_key(b + s.wind_b);
chain[s.wind_b] = get_head(key);
head[key] = uint16_t(s.wind_b);
best_len[s.wind_b] = uint16_t(DictBase::MaxMatchLen + 1);
chain_sz[key]++;
}
};
struct Match2Impl : DictBase::Match2 {
static uint32_t make_key(const uint8_t* data) {
return uint32_t(data[0]) ^ (uint32_t(data[1]) << 8);
}
void init() {
std::fill(std::begin(head), std::end(head), UINT16_MAX);
}
void add(uint16_t pos, const uint8_t* b) {
head[make_key(b + pos)] = pos;
}
void remove(uint32_t pos, const uint8_t* b) {
uint16_t& p = head[make_key(b + pos)];
if (p == pos)
p = UINT16_MAX;
}
bool search(State& s, uint32_t& lb_pos, uint32_t& lb_len,
uint32_t best_pos[MaxMatchByLengthLen], const uint8_t* b) const {
uint16_t pos = head[make_key(b + s.wind_b)];
if (pos == UINT16_MAX)
return false;
if (best_pos[2] == 0)
best_pos[2] = pos + 1;
if (lb_len < 2) {
lb_len = 2;
lb_pos = pos;
}
return true;
}
};
void init(State& s, const uint8_t* src, std::size_t src_size) {
auto& match3 = static_cast<Match3Impl&>(_storage->match3);
auto& match2 = static_cast<Match2Impl&>(_storage->match2);
s.cycle1_countdown = DictBase::MaxDist;
match3.init();
match2.init();
s.src = src;
s.src_end = src + src_size;
s.inp = src;
s.wind_sz = uint32_t(std::min(src_size, std::size_t(MaxMatchLen)));
s.wind_b = 0;
s.wind_e = s.wind_sz;
std::copy_n(s.inp, s.wind_sz, _storage->buffer);
s.inp += s.wind_sz;
if (s.wind_e == DictBase::BufSize)
s.wind_e = 0;
if (s.wind_sz < 3)
std::fill_n(_storage->buffer + s.wind_b + s.wind_sz, 3, 0);
}
void reset_next_input_entry(State& s, Match3Impl& match3, Match2Impl& match2) {
/* Remove match from about-to-be-clobbered buffer entry */
if (s.cycle1_countdown == 0) {
match3.remove(s.wind_e, _storage->buffer);
match2.remove(s.wind_e, _storage->buffer);
} else {
--s.cycle1_countdown;
}
}
void advance(State& s, uint32_t& lb_off, uint32_t& lb_len,
uint32_t best_off[MaxMatchByLengthLen], bool skip) {
auto& match3 = static_cast<Match3Impl&>(_storage->match3);
auto& match2 = static_cast<Match2Impl&>(_storage->match2);
if (skip) {
for (uint32_t i = 0; i < lb_len - 1; ++i) {
reset_next_input_entry(s, match3, match2);
match3.skip_advance(s, _storage->buffer);
match2.add(uint16_t(s.wind_b), _storage->buffer);
s.get_byte(_storage->buffer);
}
}
lb_len = 1;
lb_off = 0;
uint32_t lb_pos;
uint32_t best_pos[MaxMatchByLengthLen] = {};
uint32_t match_pos, match_count;
match3.advance(s, match_pos, match_count, _storage->buffer);
int best_char = _storage->buffer[s.wind_b];
uint32_t best_len = lb_len;
if (lb_len >= s.wind_sz) {
if (s.wind_sz == 0)
best_char = -1;
lb_off = 0;
match3.best_len[s.wind_b] = DictBase::MaxMatchLen + 1;
} else {
if (match2.search(s, lb_pos, lb_len, best_pos, _storage->buffer) && s.wind_sz >= 3) {
for (uint32_t i = 0; i < match_count; ++i, match_pos = match3.chain[match_pos]) {
auto ref_ptr = _storage->buffer + s.wind_b;
auto match_ptr = _storage->buffer + match_pos;
auto mismatch = std::mismatch(ref_ptr, ref_ptr + s.wind_sz, match_ptr);
auto match_len = uint32_t(mismatch.first - ref_ptr);
if (match_len < 2)
continue;
if (match_len < MaxMatchByLengthLen && best_pos[match_len] == 0)
best_pos[match_len] = match_pos + 1;
if (match_len > lb_len) {
lb_len = match_len;
lb_pos = match_pos;
if (match_len == s.wind_sz || match_len > match3.best_len[match_pos])
break;
}
}
}
if (lb_len > best_len)
lb_off = s.pos2off(lb_pos);
match3.best_len[s.wind_b] = uint16_t(lb_len);
for (auto posit = std::begin(best_pos) + 2, offit = best_off + 2;
posit != std::end(best_pos); ++posit, ++offit) {
*offit = (*posit > 0) ? s.pos2off(*posit - 1) : 0;
}
}
reset_next_input_entry(s, match3, match2);
match2.add(uint16_t(s.wind_b), _storage->buffer);
s.get_byte(_storage->buffer);
if (best_char < 0) {
s.buf_sz = 0;
lb_len = 0;
/* Signal exit */
} else {
s.buf_sz = s.wind_sz + 1;
}
s.bufp = s.inp - s.buf_sz;
}
};
static void find_better_match(const uint32_t best_off[MaxMatchByLengthLen], uint32_t& lb_len, uint32_t& lb_off) {
if (lb_len <= M2MinLen || lb_off <= M2MaxOffset)
return;
if (lb_off > M2MaxOffset && lb_len >= M2MinLen + 1 && lb_len <= M2MaxLen + 1 &&
best_off[lb_len - 1] != 0 && best_off[lb_len - 1] <= M2MaxOffset) {
lb_len -= 1;
lb_off = best_off[lb_len];
} else if (lb_off > M3MaxOffset && lb_len >= M4MaxLen + 1 && lb_len <= M2MaxLen + 2 &&
best_off[lb_len - 2] && best_off[lb_len] <= M2MaxOffset) {
lb_len -= 2;
lb_off = best_off[lb_len];
} else if (lb_off > M3MaxOffset && lb_len >= M4MaxLen + 1 && lb_len <= M3MaxLen + 1 &&
best_off[lb_len - 1] != 0 && best_off[lb_len - 2] <= M3MaxOffset) {
lb_len -= 1;
lb_off = best_off[lb_len];
}
}
static EResult encode_literal_run(uint8_t*& outp, const uint8_t* outp_end, const uint8_t* dst, std::size_t& dst_size,
const uint8_t* lit_ptr, uint32_t lit_len) {
if (outp == dst && lit_len <= 238) {
NEEDS_OUT(1);
*outp++ = uint8_t(17 + lit_len);
} else if (lit_len <= 3) {
outp[-2] = uint8_t(outp[-2] | lit_len);
} else if (lit_len <= 18) {
NEEDS_OUT(1);
*outp++ = uint8_t(lit_len - 3);
} else {
NEEDS_OUT((lit_len - 18) / 255 + 2);
*outp++ = 0;
WRITE_ZERO_BYTE_LENGTH(lit_len - 18);
}
NEEDS_OUT(lit_len);
outp = std::copy_n(lit_ptr, lit_len, outp);
return EResult::Success;
}
static EResult encode_lookback_match(uint8_t*& outp, const uint8_t* outp_end, const uint8_t* dst, std::size_t& dst_size,
uint32_t lb_len, uint32_t lb_off, uint32_t last_lit_len) {
if (lb_len == 2) {
lb_off -= 1;
NEEDS_OUT(2);
*outp++ = uint8_t(M1Marker | ((lb_off & 0x3) << 2));
*outp++ = uint8_t(lb_off >> 2);
} else if (lb_len <= M2MaxLen && lb_off <= M2MaxOffset) {
lb_off -= 1;
NEEDS_OUT(2);
*outp++ = uint8_t((lb_len - 1) << 5 | ((lb_off & 0x7) << 2));
*outp++ = uint8_t(lb_off >> 3);
} else if (lb_len == M2MinLen && lb_off <= M1MaxOffset + M2MaxOffset && last_lit_len >= 4) {
lb_off -= 1 + M2MaxOffset;
NEEDS_OUT(2);
*outp++ = uint8_t(M1Marker | ((lb_off & 0x3) << 2));
*outp++ = uint8_t(lb_off >> 2);
} else if (lb_off <= M3MaxOffset) {
lb_off -= 1;
if (lb_len <= M3MaxLen) {
NEEDS_OUT(1);
*outp++ = uint8_t(M3Marker | (lb_len - 2));
} else {
lb_len -= M3MaxLen;
NEEDS_OUT(lb_len / 255 + 2);
*outp++ = uint8_t(M3Marker);
WRITE_ZERO_BYTE_LENGTH(lb_len);
}
NEEDS_OUT(2);
*outp++ = uint8_t(lb_off << 2);
*outp++ = uint8_t(lb_off >> 6);
} else {
lb_off -= 0x4000;
if (lb_len <= M4MaxLen) {
NEEDS_OUT(1);
*outp++ = uint8_t(M4Marker | ((lb_off & 0x4000) >> 11) | (lb_len - 2));
} else {
lb_len -= M4MaxLen;
NEEDS_OUT(lb_len / 255 + 2);
*outp++ = uint8_t(M4Marker | ((lb_off & 0x4000) >> 11));
WRITE_ZERO_BYTE_LENGTH(lb_len);
}
NEEDS_OUT(2);
*outp++ = uint8_t(lb_off << 2);
*outp++ = uint8_t(lb_off >> 6);
}
return EResult::Success;
}
EResult compress(const uint8_t* src, std::size_t src_size,
uint8_t* dst, std::size_t init_dst_size,
std::size_t& dst_size, DictBase& dict) {
EResult err;
State s;
auto& d = static_cast<DictImpl&>(dict);
dst_size = init_dst_size;
uint8_t* outp = dst;
uint8_t* outp_end = dst + dst_size;
uint32_t lit_len = 0;
uint32_t lb_off, lb_len;
uint32_t best_off[MaxMatchByLengthLen];
d.init(s, src, src_size);
const uint8_t* lit_ptr = s.inp;
d.advance(s, lb_off, lb_len, best_off, false);
while (s.buf_sz > 0) {
if (lit_len == 0)
lit_ptr = s.bufp;
if (lb_len < 2 || (lb_len == 2 && (lb_off > M1MaxOffset || lit_len == 0 || lit_len >= 4)) ||
(lb_len == 2 && outp == dst) || (outp == dst && lit_len == 0)) {
lb_len = 0;
} else if (lb_len == M2MinLen && lb_off > M1MaxOffset + M2MaxOffset && lit_len >= 4) {
lb_len = 0;
}
if (lb_len == 0) {
++lit_len;
d.advance(s, lb_off, lb_len, best_off, false);
continue;
}
find_better_match(best_off, lb_len, lb_off);
if ((err = encode_literal_run(outp, outp_end, dst, dst_size, lit_ptr, lit_len)) < EResult::Success)
return err;
if ((err = encode_lookback_match(outp, outp_end, dst, dst_size, lb_len, lb_off, lit_len)) < EResult::Success)
return err;
lit_len = 0;
d.advance(s, lb_off, lb_len, best_off, true);
}
if ((err = encode_literal_run(outp, outp_end, dst, dst_size, lit_ptr, lit_len)) < EResult::Success)
return err;
/* Terminating M4 */
NEEDS_OUT(3);
*outp++ = M4Marker | 1;
*outp++ = 0;
*outp++ = 0;
dst_size = outp - dst;
return EResult::Success;
}
}
Reference in New Issue View Git Blame Copy Permalink