[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