+/*
+ * The DECODE_TABLE_ENOUGH() macro evaluates to the maximum number of decode
+ * table entries, including all subtable entries, that may be required for
+ * decoding a given Huffman code. This depends on three parameters:
+ *
+ * num_syms: the maximum number of symbols in the code
+ * table_bits: the number of bits with which the root table will be indexed
+ * max_codeword_len: the maximum allowed codeword length in the code
+ *
+ * Given these parameters, the utility program 'enough' from zlib, when passed
+ * the three arguments 'num_syms', 'table_bits', and 'max_codeword_len', will
+ * compute the maximum number of entries required. This has already been done
+ * for the combinations we need and incorporated into the macro below so that
+ * the mapping can be done at compilation time. If an unknown combination is
+ * used, then a compilation error will result. To fix this, use 'enough' to
+ * find the missing value and add it below. If that still doesn't fix the
+ * compilation error, then most likely a constraint would be violated by the
+ * requested parameters, so they cannot be used, at least without other changes
+ * to the decode table --- see DECODE_TABLE_SIZE().
+ */
+#define DECODE_TABLE_ENOUGH(num_syms, table_bits, max_codeword_len) ( \
+ ((num_syms) == 8 && (table_bits) == 7 && (max_codeword_len) == 15) ? 128 : \
+ ((num_syms) == 8 && (table_bits) == 5 && (max_codeword_len) == 7) ? 36 : \
+ ((num_syms) == 8 && (table_bits) == 6 && (max_codeword_len) == 7) ? 66 : \
+ ((num_syms) == 8 && (table_bits) == 7 && (max_codeword_len) == 7) ? 128 : \
+ ((num_syms) == 20 && (table_bits) == 5 && (max_codeword_len) == 15) ? 1062 : \
+ ((num_syms) == 20 && (table_bits) == 6 && (max_codeword_len) == 15) ? 582 : \
+ ((num_syms) == 20 && (table_bits) == 7 && (max_codeword_len) == 15) ? 390 : \
+ ((num_syms) == 54 && (table_bits) == 9 && (max_codeword_len) == 15) ? 618 : \
+ ((num_syms) == 54 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1098 : \
+ ((num_syms) == 249 && (table_bits) == 9 && (max_codeword_len) == 16) ? 878 : \
+ ((num_syms) == 249 && (table_bits) == 10 && (max_codeword_len) == 16) ? 1326 : \
+ ((num_syms) == 249 && (table_bits) == 11 && (max_codeword_len) == 16) ? 2318 : \
+ ((num_syms) == 256 && (table_bits) == 9 && (max_codeword_len) == 15) ? 822 : \
+ ((num_syms) == 256 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1302 : \
+ ((num_syms) == 256 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2310 : \
+ ((num_syms) == 512 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1558 : \
+ ((num_syms) == 512 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2566 : \
+ ((num_syms) == 512 && (table_bits) == 12 && (max_codeword_len) == 15) ? 4606 : \
+ ((num_syms) == 656 && (table_bits) == 10 && (max_codeword_len) == 16) ? 1734 : \
+ ((num_syms) == 656 && (table_bits) == 11 && (max_codeword_len) == 16) ? 2726 : \
+ ((num_syms) == 656 && (table_bits) == 12 && (max_codeword_len) == 16) ? 4758 : \
+ ((num_syms) == 799 && (table_bits) == 9 && (max_codeword_len) == 15) ? 1366 : \
+ ((num_syms) == 799 && (table_bits) == 10 && (max_codeword_len) == 15) ? 1846 : \
+ ((num_syms) == 799 && (table_bits) == 11 && (max_codeword_len) == 15) ? 2854 : \
+ -1)
+
+/* Wrapper around DECODE_TABLE_ENOUGH() that does additional compile-time
+ * validation. */
+#define DECODE_TABLE_SIZE(num_syms, table_bits, max_codeword_len) ( \
+ \
+ /* All values must be positive. */ \
+ STATIC_ASSERT_ZERO((num_syms) > 0) + \
+ STATIC_ASSERT_ZERO((table_bits) > 0) + \
+ STATIC_ASSERT_ZERO((max_codeword_len) > 0) + \
+ \
+ /* There cannot be more symbols than possible codewords. */ \
+ STATIC_ASSERT_ZERO((num_syms) <= 1U << (max_codeword_len)) + \
+ \
+ /* There is no reason for the root table to be indexed with
+ * more bits than the maximum codeword length. */ \
+ STATIC_ASSERT_ZERO((table_bits) <= (max_codeword_len)) + \
+ \
+ /* The maximum symbol value must fit in the 'symbol' field. */ \
+ STATIC_ASSERT_ZERO((num_syms) - 1 <= DECODE_TABLE_MAX_SYMBOL) + \
+ \
+ /* The maximum codeword length in the root table must fit in
+ * the 'length' field. */ \
+ STATIC_ASSERT_ZERO((table_bits) <= DECODE_TABLE_MAX_LENGTH) + \
+ \
+ /* The maximum codeword length in a subtable must fit in the
+ * 'length' field. */ \
+ STATIC_ASSERT_ZERO((max_codeword_len) - (table_bits) <= \
+ DECODE_TABLE_MAX_LENGTH) + \
+ \
+ /* The minimum subtable index must be greater than the maximum
+ * symbol value. If this were not the case, then there would
+ * be no way to tell whether a given root table entry is a
+ * "subtable pointer" or not. (An alternate solution would be
+ * to reserve a flag bit specifically for this purpose.) */ \
+ STATIC_ASSERT_ZERO((1U << table_bits) > (num_syms) - 1) + \
+ \
+ /* The needed 'enough' value must have been defined. */ \
+ STATIC_ASSERT_ZERO(DECODE_TABLE_ENOUGH( \
+ (num_syms), (table_bits), \
+ (max_codeword_len)) > 0) + \
+ \
+ /* The maximum subtable index must fit in the 'symbol' field. */\
+ STATIC_ASSERT_ZERO(DECODE_TABLE_ENOUGH( \
+ (num_syms), (table_bits), \
+ (max_codeword_len)) - 1 <= \
+ DECODE_TABLE_MAX_SYMBOL) + \
+ \
+ /* Finally, make the macro evaluate to the needed maximum
+ * number of decode table entries. */ \
+ DECODE_TABLE_ENOUGH((num_syms), (table_bits), \
+ (max_codeword_len)) \
+)
+
+/*
+ * Declare the decode table for a Huffman code, given several compile-time
+ * constants that describe the code. See DECODE_TABLE_ENOUGH() for details.
+ *
+ * Decode tables must be aligned to a DECODE_TABLE_ALIGNMENT-byte boundary.
+ * This implies that if a decode table is nested inside a dynamically allocated
+ * structure, then the outer structure must be allocated on a
+ * DECODE_TABLE_ALIGNMENT-byte aligned boundary as well.
+ */
+#define DECODE_TABLE(name, num_syms, table_bits, max_codeword_len) \
+ u16 name[DECODE_TABLE_SIZE((num_syms), (table_bits), \
+ (max_codeword_len))] \
+ _aligned_attribute(DECODE_TABLE_ALIGNMENT)
+
+/*
+ * Declare the temporary "working_space" array needed for building the decode
+ * table for a Huffman code.
+ */
+#define DECODE_TABLE_WORKING_SPACE(name, num_syms, max_codeword_len) \
+ u16 name[2 * ((max_codeword_len) + 1) + (num_syms)];
+