It implements HC4 matchfinder for now with some minor optimization. Signed-off-by: Gao Xiang <[email protected]> --- lzma/mf.c | 311 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ lzma/mf.h | 73 +++++++++++++ 2 files changed, 384 insertions(+) create mode 100644 lzma/mf.c create mode 100644 lzma/mf.h
diff --git a/lzma/mf.c b/lzma/mf.c new file mode 100644 index 0000000..e7bcc40 --- /dev/null +++ b/lzma/mf.c @@ -0,0 +1,311 @@ +// SPDX-License-Identifier: Apache-2.0 +/* + * ez/lzma/mf.c - LZMA matchfinder + * + * Copyright (C) 2019-2020 Gao Xiang <[email protected]> + */ +#include <stdlib.h> +#include <ez/unaligned.h> +#include <ez/bitops.h> +#include "mf.h" +#include "bytehash.h" + +#define LZMA_HASH_2_SZ (1U << 10) +#define LZMA_HASH_3_SZ (1U << 16) + +#define LZMA_HASH_3_BASE (LZMA_HASH_2_SZ) +#define LZMA_HASH_4_BASE (LZMA_HASH_2_SZ + LZMA_HASH_3_SZ) + +static inline uint32_t mt_calc_dualhash(const uint8_t cur[2]) +{ + return crc32_byte_hashtable[cur[0]] ^ cur[1]; +} + +static inline uint32_t mt_calc_hash_3(const uint8_t cur[3], + const uint32_t dualhash) +{ + return (dualhash ^ (cur[2] << 8)) & (LZMA_HASH_3_SZ - 1); +} + +static inline uint32_t mt_calc_hash_4(const uint8_t cur[4], unsigned int nbits) +{ + const uint32_t golden_ratio_32 = 0x61C88647; + + return (get_unaligned_le32(cur) * golden_ratio_32) >> (32 - nbits); +} + +/* Mark the current byte as processed from point of view of the match finder. */ +static void mf_move(struct lzma_mf *mf) +{ + if (mf->chaincur + 1 > mf->max_distance) + mf->chaincur = 0; + else + ++mf->chaincur; + + ++mf->cur; + DBG_BUGON(mf->buffer + mf->cur > mf->iend); +} + +static unsigned int lzma_mf_do_hc4_find(struct lzma_mf *mf, + struct lzma_match *matches) +{ + const uint32_t cur = mf->cur; + const uint8_t *ip = mf->buffer + cur; + const uint32_t pos = cur + mf->offset; + const uint32_t nice_len = mf->nice_len; + const uint8_t *ilimit = + ip + nice_len < mf->iend ? ip + nice_len : mf->iend; + + const uint32_t dualhash = mt_calc_dualhash(ip); + const uint32_t hash_2 = dualhash & (LZMA_HASH_2_SZ - 1); + const uint32_t delta2 = pos - mf->hash[hash_2]; + const uint32_t hash_3 = mt_calc_hash_3(ip, dualhash); + const uint32_t delta3 = pos - mf->hash[LZMA_HASH_3_BASE + hash_3]; + const uint32_t hash_value = mt_calc_hash_4(ip, mf->hashbits); + uint32_t cur_match = mf->hash[LZMA_HASH_4_BASE + hash_value]; + unsigned int bestlen, depth; + const uint8_t *matchend; + struct lzma_match *mp; + + mf->hash[hash_2] = pos; + mf->hash[LZMA_HASH_3_BASE + hash_3] = pos; + mf->hash[LZMA_HASH_4_BASE + hash_value] = pos; + mf->chain[mf->chaincur] = cur_match; + + mp = matches; + bestlen = 0; + + /* check the 2-byte match */ + if (delta2 <= mf->max_distance && *(ip - delta2) == *ip) { + matchend = ez_memcmp(ip + 2, ip - delta2 + 2, ilimit); + + bestlen = matchend - ip; + *(mp++) = (struct lzma_match) { .len = bestlen, + .dist = delta2 }; + + if (matchend >= ilimit) + goto out; + } + + /* check the 3-byte match */ + if (delta2 != delta3 && delta3 <= mf->max_distance && + *(ip - delta3) == *ip) { + matchend = ez_memcmp(ip + 3, ip - delta3 + 3, ilimit); + + if (matchend - ip > bestlen) { + bestlen = matchend - ip; + *(mp++) = (struct lzma_match) { .len = bestlen, + .dist = delta3 }; + + if (matchend >= ilimit) + goto out; + } + } + + /* check 4 or more byte matches, traversal the whole hash chain */ + for (depth = mf->depth; depth; --depth) { + const uint32_t delta = pos - cur_match; + const uint8_t *match = ip - delta; + uint32_t nextcur; + + if (delta > mf->max_distance) + break; + + nextcur = (mf->chaincur >= delta ? mf->chaincur - delta : + mf->max_distance + 1 + mf->chaincur - delta); + cur_match = mf->chain[nextcur]; + + if (get_unaligned32(match) == get_unaligned32(ip) && + match[bestlen] == ip[bestlen]) { + matchend = ez_memcmp(ip + 4, match + 4, ilimit); + + if (matchend - ip <= bestlen) + continue; + + bestlen = matchend - ip; + *(mp++) = (struct lzma_match) { .len = bestlen, + .dist = delta }; + + if (matchend >= ilimit) + break; + } + } + +out: + return mp - matches; +} + +/* aka. lzma_mf_hc4_skip */ +void lzma_mf_skip(struct lzma_mf *mf, unsigned int bytetotal) +{ + const unsigned int hashbits = mf->hashbits; + unsigned int unhashedskip = mf->unhashedskip; + unsigned int bytecount = 0; + + if (unhashedskip) { + bytetotal += unhashedskip; + mf->cur -= unhashedskip; + mf->lookahead -= unhashedskip; + mf->unhashedskip = 0; + } + + if (unlikely(!bytetotal)) + return; + + do { + const uint8_t *ip = mf->buffer + mf->cur; + uint32_t pos, dualhash, hash_2, hash_3, hash_value; + + if (mf->iend - ip < 4) { + unhashedskip = bytetotal - bytecount; + + mf->unhashedskip = unhashedskip; + mf->cur += unhashedskip; + break; + } + + pos = mf->cur + mf->offset; + + dualhash = mt_calc_dualhash(ip); + hash_2 = dualhash & (LZMA_HASH_2_SZ - 1); + mf->hash[hash_2] = pos; + + hash_3 = mt_calc_hash_3(ip, dualhash); + mf->hash[LZMA_HASH_3_BASE + hash_3] = pos; + + hash_value = mt_calc_hash_4(ip, hashbits); + + mf->chain[mf->chaincur] = + mf->hash[LZMA_HASH_4_BASE + hash_value]; + mf->hash[LZMA_HASH_4_BASE + hash_value] = pos; + + mf_move(mf); + } while (++bytecount < bytetotal); + + mf->lookahead += bytetotal; +} + +static int lzma_mf_hc4_find(struct lzma_mf *mf, + struct lzma_match *matches, bool finish) +{ + int ret; + + if (mf->iend - &mf->buffer[mf->cur] < 4) { + if (!finish) + return -ERANGE; + + mf->eod = true; + if (mf->buffer + mf->cur == mf->iend) + return -ERANGE; + } + + if (!mf->eod) { + ret = lzma_mf_do_hc4_find(mf, matches); + } else { + ret = 0; + /* ++mf->unhashedskip; */ + mf->unhashedskip = 0; /* bypass all lzma_mf_skip(mf, 0); */ + } + mf_move(mf); + ++mf->lookahead; + return ret; +} + +int lzma_mf_find(struct lzma_mf *mf, struct lzma_match *matches, bool finish) +{ + const uint8_t *ip = mf->buffer + mf->cur; + const uint8_t *iend = max((const uint8_t *)mf->iend, + ip + kMatchMaxLen); + unsigned int i; + int ret; + + /* if (mf->unhashedskip && !mf->eod) */ + if (mf->unhashedskip) + lzma_mf_skip(mf, 0); + + ret = lzma_mf_hc4_find(mf, matches, finish); + if (ret <= 0) + return ret; + + i = ret; + do { + const uint8_t *cur = ip + matches[--i].len; + + if (matches[i].len < mf->nice_len || cur >= iend) + break; + + /* extend the candicated match as far as it can */ + matches[i].len = ez_memcmp(cur, cur - matches[i].dist, + iend) - ip; + } while (i); + return ret; +} + +void lzma_mf_fill(struct lzma_mf *mf, const uint8_t *in, unsigned int size) +{ + DBG_BUGON(mf->buffer + mf->cur > mf->iend); + + /* move the sliding window in advance if needed */ + //if (mf->cur >= mf->size - mf->keep_size_after) + // move_window(mf); + + memcpy(mf->iend, in, size); + mf->iend += size; +} + +int lzma_mf_reset(struct lzma_mf *mf, const struct lzma_mf_properties *p) +{ + const uint32_t dictsize = p->dictsize; + unsigned int new_hashbits; + + if (!dictsize) + return -EINVAL; + + if (dictsize < UINT16_MAX) { + new_hashbits = 16; + /* most significant set bit + 1 of distsize to derive hashbits */ + } else { + const unsigned int hs = fls(dictsize); + + new_hashbits = hs - (1 << (hs - 1) == dictsize); + if (new_hashbits > 31) + new_hashbits = 31; + } + + if (new_hashbits != mf->hashbits || + mf->max_distance != dictsize - 1) { + if (mf->hash) + free(mf->hash); + if (mf->chain) + free(mf->chain); + + mf->hashbits = 0; + mf->hash = calloc(LZMA_HASH_4_BASE + (1 << new_hashbits), + sizeof(mf->hash[0])); + if (!mf->hash) + return -ENOMEM; + + mf->chain = malloc(sizeof(mf->chain[0]) * (dictsize - 1)); + if (!mf->chain) { + free(mf->hash); + return -ENOMEM; + } + mf->hashbits = new_hashbits; + } + + mf->max_distance = dictsize - 1; + /* + * Set the initial value as mf->max_distance + 1. + * This would avoid hash zero initialization. + */ + mf->offset = mf->max_distance + 1; + + mf->nice_len = p->nice_len; + mf->depth = p->depth; + + mf->cur = 0; + mf->lookahead = 0; + mf->chaincur = 0; + return 0; +} + diff --git a/lzma/mf.h b/lzma/mf.h new file mode 100644 index 0000000..3df5043 --- /dev/null +++ b/lzma/mf.h @@ -0,0 +1,73 @@ +/* SPDX-License-Identifier: Apache-2.0 */ +/* + * ez/lzma/mf.h - header file for LZMA matchfinder + * + * Copyright (C) 2019-2020 Gao Xiang <[email protected]> + */ +#ifndef __LZMA_MF_H +#define __LZMA_MF_H + +#include <ez/util.h> +#include "lzma_common.h" + +struct lzma_mf_properties { + uint32_t dictsize; + + uint32_t nice_len, depth; +}; + +/* + * an array used used by the LZ-based encoder to hold + * the length-distance pairs found by LZMA matchfinder. + */ +struct lzma_match { + unsigned int len; + unsigned int dist; +}; + +struct lzma_mf { + /* pointer to buffer with data to be compressed */ + uint8_t *buffer; + + /* size of the whole LZMA matchbuffer */ + uint32_t size; + + uint32_t offset; + + /* indicate the next byte to run through the match finder */ + uint32_t cur; + + /* maximum length of a match that the matchfinder will try to find. */ + uint32_t nice_len; + + /* indicate the first byte that doesn't contain valid input data */ + uint8_t *iend; + + /* indicate the number of bytes still not encoded */ + uint32_t lookahead; + + /* LZ matchfinder hash chain representation */ + uint32_t *hash, *chain; + + /* indicate the next byte in chain (0 ~ max_distance) */ + uint32_t chaincur; + uint8_t hashbits; + + /* maximum number of loops in the match finder */ + uint8_t depth; + + uint32_t max_distance; + + /* the number of bytes unhashed, and wait to roll back later */ + uint32_t unhashedskip; + + bool eod; +}; + +int lzma_mf_find(struct lzma_mf *mf, struct lzma_match *matches, bool finish); +void lzma_mf_skip(struct lzma_mf *mf, unsigned int n); +void lzma_mf_fill(struct lzma_mf *mf, const uint8_t *in, unsigned int size); +int lzma_mf_reset(struct lzma_mf *mf, const struct lzma_mf_properties *p); + +#endif + -- 2.20.1
