+/* Returns the LZX position slot that corresponds to a given formatted offset.
+ *
+ * Logically, this returns the smallest i such that
+ * formatted_offset >= lzx_position_base[i].
+ *
+ * The actual implementation below takes advantage of the regularity of the
+ * numbers in the lzx_position_base array to calculate the slot directly from
+ * the formatted offset without actually looking at the array.
+ */
+static inline unsigned
+lzx_get_position_slot_raw(unsigned formatted_offset)
+{
+ if (formatted_offset >= 196608) {
+ return (formatted_offset >> 17) + 34;
+ } else {
+ LZX_ASSERT(2 <= formatted_offset && formatted_offset < 655360);
+ unsigned mssb_idx = bsr32(formatted_offset);
+ return (mssb_idx << 1) |
+ ((formatted_offset >> (mssb_idx - 1)) & 1);
+ }
+}
+
+extern bool lzx_window_size_valid(size_t window_size);
+extern unsigned lzx_get_num_main_syms(u32 window_size);
+
+#define LZX_NUM_RECENT_OFFSETS 3
+
+/* Least-recently used queue for match offsets. */
+struct lzx_lru_queue {
+ u32 R[LZX_NUM_RECENT_OFFSETS];