+#include "wimlib/lzms.h"
+#include "wimlib/unaligned.h"
+#include "wimlib/util.h"
+
+#include <pthread.h>
+
+/***************************************************************
+ * Constant tables initialized by lzms_compute_slots(): *
+ ***************************************************************/
+
+/* Table: offset slot => offset slot base value */
+u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1];
+
+/* Table: offset slot => number of extra offset bits */
+u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS];
+
+/* Table: length slot => length slot base value */
+u32 lzms_length_slot_base[LZMS_NUM_LEN_SYMS + 1];
+
+/* Table: length slot => number of extra length bits */
+u8 lzms_extra_length_bits[LZMS_NUM_LEN_SYMS];
+
+unsigned
+lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots)
+{
+ unsigned l = 0;
+ unsigned r = num_slots - 1;
+ for (;;) {
+ LZMS_ASSERT(r >= l);
+ unsigned slot = (l + r) / 2;
+ if (value >= slot_base_tab[slot]) {
+ if (value < slot_base_tab[slot + 1])
+ return slot;
+ else
+ l = slot + 1;
+ } else {
+ r = slot - 1;
+ }
+ }
+}
+
+static void
+lzms_decode_delta_rle_slot_bases(u32 slot_bases[],
+ u8 extra_bits[],
+ const u8 delta_run_lens[],
+ unsigned num_run_lens,
+ u32 final,
+ unsigned expected_num_slots)
+{
+ unsigned order = 0;
+ u32 delta = 1;
+ u32 base = 0;
+ unsigned slot = 0;
+ for (unsigned i = 0; i < num_run_lens; i++) {
+ unsigned run_len = delta_run_lens[i];
+ while (run_len--) {
+ base += delta;
+ if (slot > 0)
+ extra_bits[slot - 1] = order;
+ slot_bases[slot] = base;
+ slot++;
+ }
+ delta <<= 1;
+ order++;
+ }
+ LZMS_ASSERT(slot == expected_num_slots);
+
+ slot_bases[slot] = final;
+ extra_bits[slot - 1] = bsr32(slot_bases[slot] - slot_bases[slot - 1]);
+}
+
+/* Initialize the global offset and length slot tables. */
+static void
+lzms_compute_slots(void)
+{
+ /* If an explicit formula that maps LZMS offset and length slots to slot
+ * bases exists, then it could be used here. But until one is found,
+ * the following code fills in the slots using the observation that the
+ * increase from one slot base to the next is an increasing power of 2.
+ * Therefore, run-length encoding of the delta of adjacent entries can
+ * be used. */
+ static const u8 offset_slot_delta_run_lens[] = {
+ 9, 0, 9, 7, 10, 15, 15, 20,
+ 20, 30, 33, 40, 42, 45, 60, 73,
+ 80, 85, 95, 105, 6,
+ };
+
+ static const u8 length_slot_delta_run_lens[] = {
+ 27, 4, 6, 4, 5, 2, 1, 1,
+ 1, 1, 1, 0, 0, 0, 0, 0,
+ 1,
+ };
+
+ /* Offset slots */
+ lzms_decode_delta_rle_slot_bases(lzms_offset_slot_base,
+ lzms_extra_offset_bits,
+ offset_slot_delta_run_lens,
+ ARRAY_LEN(offset_slot_delta_run_lens),
+ 0x7fffffff,
+ LZMS_MAX_NUM_OFFSET_SYMS);
+
+ /* Length slots */
+ lzms_decode_delta_rle_slot_bases(lzms_length_slot_base,
+ lzms_extra_length_bits,
+ length_slot_delta_run_lens,
+ ARRAY_LEN(length_slot_delta_run_lens),
+ 0x400108ab,
+ LZMS_NUM_LEN_SYMS);
+}
+
+/* Initialize the global offset and length slot tables if not already done. */
+void
+lzms_init_slots(void)
+{
+ static pthread_once_t once = PTHREAD_ONCE_INIT;
+
+ pthread_once(&once, lzms_compute_slots);
+}