IMPORT: slz: import slz into the tree
SLZ is rarely packaged by distros and there have been complaints about
the CPU and memory usage of ZLIB, leading to some suggestions to better
address the issue by simply integrating SLZ into the tree (just 3 files).
See discussions below:
https://www.mail-archive.com/haproxy@formilux.org/msg38037.html
https://www.mail-archive.com/haproxy@formilux.org/msg40079.html
https://www.mail-archive.com/haproxy@formilux.org/msg40365.html
This patch does just this, after minor adjustments to these files:
- tables.h was renamed to slz-tables.h
- tables.h had the precomputed tables removed since not used here
- slz.c uses includes <import/slz*> instead of "slz*.h"
The slz commit imported here was b06c172 ("slz: avoid a build warning
with -Wimplicit-fallthrough"). No other change was performed either to
SLZ nor to haproxy at this point so that this operation may be replicated
if needed for a future version.
diff --git a/include/import/slz-tables.h b/include/import/slz-tables.h
new file mode 100644
index 0000000..ff6c939
--- /dev/null
+++ b/include/import/slz-tables.h
@@ -0,0 +1,235 @@
+/* Fixed Huffman table as per RFC1951.
+ *
+ * Lit Value Bits Codes
+ * --------- ---- -----
+ * 0 - 143 8 00110000 through 10111111
+ * 144 - 255 9 110010000 through 111111111
+ * 256 - 279 7 0000000 through 0010111
+ * 280 - 287 8 11000000 through 11000111
+ *
+ * The codes are encoded in reverse, the high bit of the code appears encoded
+ * as bit 0. The table is built by mkhuff.sh. The 16 bits are encoded this way :
+ * - bits 0..3 : bits
+ * - bits 4..12 : code
+ */
+static const uint16_t fixed_huff[288] = {
+ 0x00c8, 0x08c8, 0x04c8, 0x0cc8, 0x02c8, 0x0ac8, 0x06c8, 0x0ec8, // 0
+ 0x01c8, 0x09c8, 0x05c8, 0x0dc8, 0x03c8, 0x0bc8, 0x07c8, 0x0fc8, // 8
+ 0x0028, 0x0828, 0x0428, 0x0c28, 0x0228, 0x0a28, 0x0628, 0x0e28, // 16
+ 0x0128, 0x0928, 0x0528, 0x0d28, 0x0328, 0x0b28, 0x0728, 0x0f28, // 24
+ 0x00a8, 0x08a8, 0x04a8, 0x0ca8, 0x02a8, 0x0aa8, 0x06a8, 0x0ea8, // 32
+ 0x01a8, 0x09a8, 0x05a8, 0x0da8, 0x03a8, 0x0ba8, 0x07a8, 0x0fa8, // 40
+ 0x0068, 0x0868, 0x0468, 0x0c68, 0x0268, 0x0a68, 0x0668, 0x0e68, // 48
+ 0x0168, 0x0968, 0x0568, 0x0d68, 0x0368, 0x0b68, 0x0768, 0x0f68, // 56
+ 0x00e8, 0x08e8, 0x04e8, 0x0ce8, 0x02e8, 0x0ae8, 0x06e8, 0x0ee8, // 64
+ 0x01e8, 0x09e8, 0x05e8, 0x0de8, 0x03e8, 0x0be8, 0x07e8, 0x0fe8, // 72
+ 0x0018, 0x0818, 0x0418, 0x0c18, 0x0218, 0x0a18, 0x0618, 0x0e18, // 80
+ 0x0118, 0x0918, 0x0518, 0x0d18, 0x0318, 0x0b18, 0x0718, 0x0f18, // 88
+ 0x0098, 0x0898, 0x0498, 0x0c98, 0x0298, 0x0a98, 0x0698, 0x0e98, // 96
+ 0x0198, 0x0998, 0x0598, 0x0d98, 0x0398, 0x0b98, 0x0798, 0x0f98, // 104
+ 0x0058, 0x0858, 0x0458, 0x0c58, 0x0258, 0x0a58, 0x0658, 0x0e58, // 112
+ 0x0158, 0x0958, 0x0558, 0x0d58, 0x0358, 0x0b58, 0x0758, 0x0f58, // 120
+ 0x00d8, 0x08d8, 0x04d8, 0x0cd8, 0x02d8, 0x0ad8, 0x06d8, 0x0ed8, // 128
+ 0x01d8, 0x09d8, 0x05d8, 0x0dd8, 0x03d8, 0x0bd8, 0x07d8, 0x0fd8, // 136
+ 0x0139, 0x1139, 0x0939, 0x1939, 0x0539, 0x1539, 0x0d39, 0x1d39, // 144
+ 0x0339, 0x1339, 0x0b39, 0x1b39, 0x0739, 0x1739, 0x0f39, 0x1f39, // 152
+ 0x00b9, 0x10b9, 0x08b9, 0x18b9, 0x04b9, 0x14b9, 0x0cb9, 0x1cb9, // 160
+ 0x02b9, 0x12b9, 0x0ab9, 0x1ab9, 0x06b9, 0x16b9, 0x0eb9, 0x1eb9, // 168
+ 0x01b9, 0x11b9, 0x09b9, 0x19b9, 0x05b9, 0x15b9, 0x0db9, 0x1db9, // 176
+ 0x03b9, 0x13b9, 0x0bb9, 0x1bb9, 0x07b9, 0x17b9, 0x0fb9, 0x1fb9, // 184
+ 0x0079, 0x1079, 0x0879, 0x1879, 0x0479, 0x1479, 0x0c79, 0x1c79, // 192
+ 0x0279, 0x1279, 0x0a79, 0x1a79, 0x0679, 0x1679, 0x0e79, 0x1e79, // 200
+ 0x0179, 0x1179, 0x0979, 0x1979, 0x0579, 0x1579, 0x0d79, 0x1d79, // 208
+ 0x0379, 0x1379, 0x0b79, 0x1b79, 0x0779, 0x1779, 0x0f79, 0x1f79, // 216
+ 0x00f9, 0x10f9, 0x08f9, 0x18f9, 0x04f9, 0x14f9, 0x0cf9, 0x1cf9, // 224
+ 0x02f9, 0x12f9, 0x0af9, 0x1af9, 0x06f9, 0x16f9, 0x0ef9, 0x1ef9, // 232
+ 0x01f9, 0x11f9, 0x09f9, 0x19f9, 0x05f9, 0x15f9, 0x0df9, 0x1df9, // 240
+ 0x03f9, 0x13f9, 0x0bf9, 0x1bf9, 0x07f9, 0x17f9, 0x0ff9, 0x1ff9, // 248
+ 0x0007, 0x0407, 0x0207, 0x0607, 0x0107, 0x0507, 0x0307, 0x0707, // 256
+ 0x0087, 0x0487, 0x0287, 0x0687, 0x0187, 0x0587, 0x0387, 0x0787, // 264
+ 0x0047, 0x0447, 0x0247, 0x0647, 0x0147, 0x0547, 0x0347, 0x0747, // 272
+ 0x0038, 0x0838, 0x0438, 0x0c38, 0x0238, 0x0a38, 0x0638, 0x0e38 // 280
+};
+
+/* length from 3 to 258 converted to bit strings for use with fixed huffman
+ * coding. It was built by tools/dump_len.c. The format is the following :
+ * - bits 0..15 = code
+ * - bits 16..19 = #bits
+ */
+static const uint32_t len_fh[259] = {
+ 0x000000, 0x000000, 0x000000, 0x070040, /* 0-3 */
+ 0x070020, 0x070060, 0x070010, 0x070050, /* 4-7 */
+ 0x070030, 0x070070, 0x070008, 0x080048, /* 8-11 */
+ 0x0800c8, 0x080028, 0x0800a8, 0x080068, /* 12-15 */
+ 0x0800e8, 0x080018, 0x080098, 0x090058, /* 16-19 */
+ 0x0900d8, 0x090158, 0x0901d8, 0x090038, /* 20-23 */
+ 0x0900b8, 0x090138, 0x0901b8, 0x090078, /* 24-27 */
+ 0x0900f8, 0x090178, 0x0901f8, 0x090004, /* 28-31 */
+ 0x090084, 0x090104, 0x090184, 0x0a0044, /* 32-35 */
+ 0x0a00c4, 0x0a0144, 0x0a01c4, 0x0a0244, /* 36-39 */
+ 0x0a02c4, 0x0a0344, 0x0a03c4, 0x0a0024, /* 40-43 */
+ 0x0a00a4, 0x0a0124, 0x0a01a4, 0x0a0224, /* 44-47 */
+ 0x0a02a4, 0x0a0324, 0x0a03a4, 0x0a0064, /* 48-51 */
+ 0x0a00e4, 0x0a0164, 0x0a01e4, 0x0a0264, /* 52-55 */
+ 0x0a02e4, 0x0a0364, 0x0a03e4, 0x0a0014, /* 56-59 */
+ 0x0a0094, 0x0a0114, 0x0a0194, 0x0a0214, /* 60-63 */
+ 0x0a0294, 0x0a0314, 0x0a0394, 0x0b0054, /* 64-67 */
+ 0x0b00d4, 0x0b0154, 0x0b01d4, 0x0b0254, /* 68-71 */
+ 0x0b02d4, 0x0b0354, 0x0b03d4, 0x0b0454, /* 72-75 */
+ 0x0b04d4, 0x0b0554, 0x0b05d4, 0x0b0654, /* 76-79 */
+ 0x0b06d4, 0x0b0754, 0x0b07d4, 0x0b0034, /* 80-83 */
+ 0x0b00b4, 0x0b0134, 0x0b01b4, 0x0b0234, /* 84-87 */
+ 0x0b02b4, 0x0b0334, 0x0b03b4, 0x0b0434, /* 88-91 */
+ 0x0b04b4, 0x0b0534, 0x0b05b4, 0x0b0634, /* 92-95 */
+ 0x0b06b4, 0x0b0734, 0x0b07b4, 0x0b0074, /* 96-99 */
+ 0x0b00f4, 0x0b0174, 0x0b01f4, 0x0b0274, /* 100-103 */
+ 0x0b02f4, 0x0b0374, 0x0b03f4, 0x0b0474, /* 104-107 */
+ 0x0b04f4, 0x0b0574, 0x0b05f4, 0x0b0674, /* 108-111 */
+ 0x0b06f4, 0x0b0774, 0x0b07f4, 0x0c0003, /* 112-115 */
+ 0x0c0103, 0x0c0203, 0x0c0303, 0x0c0403, /* 116-119 */
+ 0x0c0503, 0x0c0603, 0x0c0703, 0x0c0803, /* 120-123 */
+ 0x0c0903, 0x0c0a03, 0x0c0b03, 0x0c0c03, /* 124-127 */
+ 0x0c0d03, 0x0c0e03, 0x0c0f03, 0x0d0083, /* 128-131 */
+ 0x0d0183, 0x0d0283, 0x0d0383, 0x0d0483, /* 132-135 */
+ 0x0d0583, 0x0d0683, 0x0d0783, 0x0d0883, /* 136-139 */
+ 0x0d0983, 0x0d0a83, 0x0d0b83, 0x0d0c83, /* 140-143 */
+ 0x0d0d83, 0x0d0e83, 0x0d0f83, 0x0d1083, /* 144-147 */
+ 0x0d1183, 0x0d1283, 0x0d1383, 0x0d1483, /* 148-151 */
+ 0x0d1583, 0x0d1683, 0x0d1783, 0x0d1883, /* 152-155 */
+ 0x0d1983, 0x0d1a83, 0x0d1b83, 0x0d1c83, /* 156-159 */
+ 0x0d1d83, 0x0d1e83, 0x0d1f83, 0x0d0043, /* 160-163 */
+ 0x0d0143, 0x0d0243, 0x0d0343, 0x0d0443, /* 164-167 */
+ 0x0d0543, 0x0d0643, 0x0d0743, 0x0d0843, /* 168-171 */
+ 0x0d0943, 0x0d0a43, 0x0d0b43, 0x0d0c43, /* 172-175 */
+ 0x0d0d43, 0x0d0e43, 0x0d0f43, 0x0d1043, /* 176-179 */
+ 0x0d1143, 0x0d1243, 0x0d1343, 0x0d1443, /* 180-183 */
+ 0x0d1543, 0x0d1643, 0x0d1743, 0x0d1843, /* 184-187 */
+ 0x0d1943, 0x0d1a43, 0x0d1b43, 0x0d1c43, /* 188-191 */
+ 0x0d1d43, 0x0d1e43, 0x0d1f43, 0x0d00c3, /* 192-195 */
+ 0x0d01c3, 0x0d02c3, 0x0d03c3, 0x0d04c3, /* 196-199 */
+ 0x0d05c3, 0x0d06c3, 0x0d07c3, 0x0d08c3, /* 200-203 */
+ 0x0d09c3, 0x0d0ac3, 0x0d0bc3, 0x0d0cc3, /* 204-207 */
+ 0x0d0dc3, 0x0d0ec3, 0x0d0fc3, 0x0d10c3, /* 208-211 */
+ 0x0d11c3, 0x0d12c3, 0x0d13c3, 0x0d14c3, /* 212-215 */
+ 0x0d15c3, 0x0d16c3, 0x0d17c3, 0x0d18c3, /* 216-219 */
+ 0x0d19c3, 0x0d1ac3, 0x0d1bc3, 0x0d1cc3, /* 220-223 */
+ 0x0d1dc3, 0x0d1ec3, 0x0d1fc3, 0x0d0023, /* 224-227 */
+ 0x0d0123, 0x0d0223, 0x0d0323, 0x0d0423, /* 228-231 */
+ 0x0d0523, 0x0d0623, 0x0d0723, 0x0d0823, /* 232-235 */
+ 0x0d0923, 0x0d0a23, 0x0d0b23, 0x0d0c23, /* 236-239 */
+ 0x0d0d23, 0x0d0e23, 0x0d0f23, 0x0d1023, /* 240-243 */
+ 0x0d1123, 0x0d1223, 0x0d1323, 0x0d1423, /* 244-247 */
+ 0x0d1523, 0x0d1623, 0x0d1723, 0x0d1823, /* 248-251 */
+ 0x0d1923, 0x0d1a23, 0x0d1b23, 0x0d1c23, /* 252-255 */
+ 0x0d1d23, 0x0d1e23, 0x0800a3 /* 256-258 */
+};
+
+static uint32_t crc32_fast[4][256];
+static uint32_t fh_dist_table[32768];
+
+/* Make the table for a fast CRC.
+ * Not thread-safe, must be called exactly once.
+ */
+static inline void __slz_make_crc_table(void)
+{
+ uint32_t c;
+ int n, k;
+
+ for (n = 0; n < 256; n++) {
+ c = (uint32_t) n ^ 255;
+ for (k = 0; k < 8; k++) {
+ if (c & 1) {
+ c = 0xedb88320 ^ (c >> 1);
+ } else {
+ c = c >> 1;
+ }
+ }
+ crc32_fast[0][n] = c ^ 0xff000000;
+ }
+
+ /* Note: here we *do not* have to invert the bits corresponding to the
+ * byte position, because [0] already has the 8 highest bits inverted,
+ * and these bits are shifted by 8 at the end of the operation, which
+ * results in having the next 8 bits shifted in turn. That's why we
+ * have the xor in the index used just after a computation.
+ */
+ for (n = 0; n < 256; n++) {
+ crc32_fast[1][n] = 0xff000000 ^ crc32_fast[0][(0xff000000 ^ crc32_fast[0][n] ^ 0xff) & 0xff] ^ (crc32_fast[0][n] >> 8);
+ crc32_fast[2][n] = 0xff000000 ^ crc32_fast[0][(0x00ff0000 ^ crc32_fast[1][n] ^ 0xff) & 0xff] ^ (crc32_fast[1][n] >> 8);
+ crc32_fast[3][n] = 0xff000000 ^ crc32_fast[0][(0x0000ff00 ^ crc32_fast[2][n] ^ 0xff) & 0xff] ^ (crc32_fast[2][n] >> 8);
+ }
+}
+
+/* Returns code for lengths 1 to 32768. The bit size for the next value can be
+ * found this way :
+ *
+ * bits = code >> 1;
+ * if (bits)
+ * bits--;
+ *
+ */
+static inline uint32_t dist_to_code(uint32_t l)
+{
+ uint32_t code;
+
+ code = 0;
+ switch (l) {
+ case 24577 ... 32768: code++; /* fall through */
+ case 16385 ... 24576: code++; /* fall through */
+ case 12289 ... 16384: code++; /* fall through */
+ case 8193 ... 12288: code++; /* fall through */
+ case 6145 ... 8192: code++; /* fall through */
+ case 4097 ... 6144: code++; /* fall through */
+ case 3073 ... 4096: code++; /* fall through */
+ case 2049 ... 3072: code++; /* fall through */
+ case 1537 ... 2048: code++; /* fall through */
+ case 1025 ... 1536: code++; /* fall through */
+ case 769 ... 1024: code++; /* fall through */
+ case 513 ... 768: code++; /* fall through */
+ case 385 ... 512: code++; /* fall through */
+ case 257 ... 384: code++; /* fall through */
+ case 193 ... 256: code++; /* fall through */
+ case 129 ... 192: code++; /* fall through */
+ case 97 ... 128: code++; /* fall through */
+ case 65 ... 96: code++; /* fall through */
+ case 49 ... 64: code++; /* fall through */
+ case 33 ... 48: code++; /* fall through */
+ case 25 ... 32: code++; /* fall through */
+ case 17 ... 24: code++; /* fall through */
+ case 13 ... 16: code++; /* fall through */
+ case 9 ... 12: code++; /* fall through */
+ case 7 ... 8: code++; /* fall through */
+ case 5 ... 6: code++; /* fall through */
+ case 4 : code++; /* fall through */
+ case 3 : code++; /* fall through */
+ case 2 : code++; /* fall through */
+ }
+
+ return code;
+}
+
+/* not thread-safe, must be called exactly once */
+static inline void __slz_prepare_dist_table()
+{
+ uint32_t dist;
+ uint32_t code;
+ uint32_t bits;
+
+ for (dist = 0; dist < sizeof(fh_dist_table) / sizeof(*fh_dist_table); dist++) {
+ code = dist_to_code(dist + 1);
+ bits = code >> 1;
+ if (bits)
+ bits--;
+
+ /* Distance codes are stored on 5 bits reversed. The RFC
+ * doesn't state that they are reversed, but it's the only
+ * way it works.
+ */
+ code = ((code & 0x01) << 4) | ((code & 0x02) << 2) |
+ (code & 0x04) |
+ ((code & 0x08) >> 2) | ((code & 0x10) >> 4);
+
+ code += (dist & ((1 << bits) - 1)) << 5;
+ fh_dist_table[dist] = (code << 5) + bits + 5;
+ }
+}