[WIP] [PATCH v0.0-20200229 04/11] ez: lzma: add range encoder
Gao Xiang
hsiangkao at aol.com
Sat Feb 29 15:50:10 AEDT 2020
The implementation is greatly inspired by XZ Utils,
which is created by Lasse Collin <lasse.collin at tukaani.org>.
Signed-off-by: Gao Xiang <hsiangkao at aol.com>
---
lzma/rc_common.h | 48 ++++++++++
lzma/rc_encoder.h | 221 ++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 269 insertions(+)
create mode 100644 lzma/rc_common.h
create mode 100644 lzma/rc_encoder.h
diff --git a/lzma/rc_common.h b/lzma/rc_common.h
new file mode 100644
index 0000000..b424fa1
--- /dev/null
+++ b/lzma/rc_common.h
@@ -0,0 +1,48 @@
+/* SPDX-License-Identifier: Unlicense */
+/*
+ * ez/lzma/rc_common.h - common definitions for range coder
+ *
+ * Copyright (C) 2019-2020 Gao Xiang <hsiangkao at aol.com>
+ *
+ * Authors: Igor Pavlov <http://7-zip.org/>
+ * Lasse Collin <lasse.collin at tukaani.org>
+ * Gao Xiang <hsiangkao at aol.com>
+ */
+#ifndef __EZ_LZMA_RC_COMMON_H
+#define __EZ_LZMA_RC_COMMON_H
+
+#include <ez/defs.h>
+
+/* Constants */
+#define RC_SHIFT_BITS 8
+#define RC_TOP_BITS 24
+#define RC_TOP_VALUE (1U << RC_TOP_BITS)
+#define RC_BIT_MODEL_TOTAL_BITS 11
+#define RC_BIT_MODEL_TOTAL (1U << RC_BIT_MODEL_TOTAL_BITS)
+#define RC_MOVE_BITS 5
+
+/* Type definitions */
+
+/*
+ * Type of probabilities used with range coder
+ *
+ * This needs to be at least 12-bit, so uint16_t is a logical choice. However,
+ * on some architecture and compiler combinations, a bigger type may give
+ * better speed since the probability variables are accessed a lot.
+ * On the other hand, bigger probability type increases cache footprint,
+ * since there are 2 to 14 thousand probability variables in LZMA (assuming
+ * the limit of lc + lp <= 4; with lc + lp <= 12 there would be about 1.5
+ * million variables).
+ *
+ * I will stick unless some specific architectures are *much* faster (20-50%)
+ * with uint32_t than uint16_t.
+ */
+typedef uint16_t probability;
+
+static inline uint32_t rc_bound(uint32_t range, probability prob)
+{
+ return (range >> RC_BIT_MODEL_TOTAL_BITS) * prob;
+}
+
+#endif
+
diff --git a/lzma/rc_encoder.h b/lzma/rc_encoder.h
new file mode 100644
index 0000000..98bf34d
--- /dev/null
+++ b/lzma/rc_encoder.h
@@ -0,0 +1,221 @@
+/* SPDX-License-Identifier: Unlicense */
+/*
+ * ez/lzma/rc_encoder.h - range code encoder
+ *
+ * Copyright (C) 2019-2020 Gao Xiang <hsiangkao at aol.com>
+ *
+ * Authors: Igor Pavlov <http://7-zip.org/>
+ * Lasse Collin <lasse.collin at tukaani.org>
+ * Gao Xiang <hsiangkao at aol.com>
+ */
+#ifndef __EZ_LZMA_RC_ENCODER_H
+#define __EZ_LZMA_RC_ENCODER_H
+
+#include "rc_common.h"
+
+/*
+ * Maximum number of symbols that can be put pending into lzma_range_encoder
+ * structure between calls to lzma_rc_encode(). For LZMA, 52+5 is enough
+ * (match with big distance and length followed by range encoder flush).
+ */
+#define RC_SYMBOLS_MAX 58
+
+#define RC_BIT_0 0
+#define RC_BIT_1 1
+#define RC_DIRECT_0 2
+#define RC_DIRECT_1 3
+#define RC_FLUSH 4
+
+struct lzma_rc_encoder {
+ uint64_t low;
+ uint64_t extended_bytes;
+ uint32_t range;
+ uint8_t firstbyte;
+
+ /* Number of symbols in the tables */
+ uint8_t count;
+
+ /* rc_encode()'s position in the tables */
+ uint8_t pos;
+
+ /* Symbols to encode (use uint8_t so can be in a single cacheline.) */
+ uint8_t symbols[RC_SYMBOLS_MAX];
+
+ /* Probabilities associated with RC_BIT_0 or RC_BIT_1 */
+ probability *probs[RC_SYMBOLS_MAX];
+};
+
+static inline void rc_reset(struct lzma_rc_encoder *rc)
+{
+ *rc = (struct lzma_rc_encoder) {
+ .range = UINT32_MAX,
+ /* .firstbyte = 0, */
+ };
+}
+
+static inline void rc_bit(struct lzma_rc_encoder *rc,
+ probability *prob, uint32_t bit)
+{
+ rc->symbols[rc->count] = bit;
+ rc->probs[rc->count] = prob;
+ ++rc->count;
+}
+
+static inline void rc_bittree(struct lzma_rc_encoder *rc,
+ probability *probs, uint32_t nbits,
+ uint32_t symbol)
+{
+ uint32_t model_index = 1;
+
+ do {
+ const uint32_t bit = (symbol >> --nbits) & 1;
+
+ rc_bit(rc, &probs[model_index], bit);
+ model_index = (model_index << 1) + bit;
+ } while (nbits);
+}
+
+static inline void rc_bittree_reverse(struct lzma_rc_encoder *rc,
+ probability *probs,
+ uint32_t nbits, uint32_t symbol)
+{
+ uint32_t model_index = 1;
+
+ do {
+ const uint32_t bit = symbol & 1;
+
+ symbol >>= 1;
+ rc_bit(rc, &probs[model_index], bit);
+ model_index = (model_index << 1) + bit;
+ } while (--nbits);
+}
+
+static inline void rc_direct(struct lzma_rc_encoder *rc,
+ uint32_t val, uint32_t nbits)
+{
+ do {
+ rc->symbols[rc->count] = RC_DIRECT_0 + ((val >> --nbits) & 1);
+ ++rc->count;
+ } while (nbits);
+}
+
+
+static inline void rc_flush(struct lzma_rc_encoder *rc)
+{
+ unsigned int i;
+
+ for (i = 0; i < 5; ++i)
+ rc->symbols[rc->count++] = RC_FLUSH;
+}
+
+static inline bool rc_shift_low(struct lzma_rc_encoder *rc,
+ uint8_t **ppos, uint8_t *oend)
+{
+ if (rc->low >> 24 != UINT8_MAX) {
+ const uint32_t carrybit = rc->low >> 32;
+
+ DBG_BUGON(carrybit > 1);
+
+ /* first or interrupted byte */
+ if (unlikely(*ppos >= oend))
+ return true;
+ *(*ppos)++ = rc->firstbyte + carrybit;
+
+ while (rc->extended_bytes) {
+ --rc->extended_bytes;
+ if (unlikely(*ppos >= oend)) {
+ rc->firstbyte = UINT8_MAX;
+ return true;
+ }
+ *(*ppos)++ = carrybit - 1;
+ }
+ rc->firstbyte = rc->low >> 24;
+ } else {
+ ++rc->extended_bytes;
+ }
+ rc->low = (rc->low & 0x00FFFFFF) << RC_SHIFT_BITS;
+ return false;
+}
+
+static inline bool rc_encode(struct lzma_rc_encoder *rc,
+ uint8_t **ppos, uint8_t *oend)
+{
+ DBG_BUGON(rc->count > RC_SYMBOLS_MAX);
+
+ while (rc->pos < rc->count) {
+ /* Normalize */
+ if (rc->range < RC_TOP_VALUE) {
+ if (rc_shift_low(rc, ppos, oend))
+ return true;
+
+ rc->range <<= RC_SHIFT_BITS;
+ }
+
+ /* Encode a bit */
+ switch (rc->symbols[rc->pos]) {
+ case RC_BIT_0: {
+ probability prob = *rc->probs[rc->pos];
+
+ rc->range = rc_bound(rc->range, prob);
+ prob += (RC_BIT_MODEL_TOTAL - prob) >> RC_MOVE_BITS;
+ *rc->probs[rc->pos] = prob;
+ break;
+ }
+
+ case RC_BIT_1: {
+ probability prob = *rc->probs[rc->pos];
+ const uint32_t bound = rc_bound(rc->range, prob);
+
+ rc->low += bound;
+ rc->range -= bound;
+ prob -= prob >> RC_MOVE_BITS;
+ *rc->probs[rc->pos] = prob;
+ break;
+ }
+
+ case RC_DIRECT_0:
+ rc->range >>= 1;
+ break;
+
+ case RC_DIRECT_1:
+ rc->range >>= 1;
+ rc->low += rc->range;
+ break;
+
+ case RC_FLUSH:
+ /* Prevent further normalizations */
+ rc->range = UINT32_MAX;
+
+ /* Flush the last five bytes (see rc_flush()) */
+ do {
+ if (rc_shift_low(rc, ppos, oend))
+ return true;
+ } while (++rc->pos < rc->count);
+
+ /*
+ * Reset the range encoder so we are ready to continue
+ * encoding if we weren't finishing the stream.
+ */
+ rc_reset(rc);
+ return false;
+
+ default:
+ DBG_BUGON(1);
+ break;
+ }
+ ++rc->pos;
+ }
+
+ rc->count = 0;
+ rc->pos = 0;
+ return false;
+}
+
+
+static inline uint64_t rc_pending(const struct lzma_rc_encoder *rc)
+{
+ return rc->extended_bytes + 5;
+}
+
+#endif
+
--
2.20.1
More information about the Linux-erofs
mailing list