em_inflate.c

commit 88b121743264770a0159f514289ef24c61f63c84
parent 4e7e309c3c5254a0143442331078a407820c8e41
Author: Emmanuel Marty <emmanuel@fgl.com>
Date:   Wed, 12 Jun 2019 08:49:16 +0200

Faster codeword reversal. Update README.
Diffstat:
M
README.md
 | 
8
+++++---
M
lib/em_inflate.c
 | 
17
++++++++---------

2 files changed, 13 insertions(+), 12 deletions(-)
diff --git a/README.md b/README.md
@@ -1,10 +1,12 @@
-em_inflate -- Fast, in-memory, single file decompressor for gzip and zlib
-=========================================================================
+em_inflate -- Fast, in-memory, single file decompressor for zlib, deflate and gzip
+==================================================================================
 
-em_inflate is a one-file, single function call, memory-to-memory decompressor for the gzip and zlib bitstream formats:
+em_inflate is a one-file, single function call, memory-to-memory decompressor for the zlib, deflate and gzip bitstream formats:
 
 [RFC 1950: ZLIB specification](https://www.ietf.org/rfc/rfc1950.txt)
 
+[RFC 1951: DEFLATE specification](https://www.ietf.org/rfc/rfc1951.txt)
+
 [RFC 1952: GZIP specification](https://www.ietf.org/rfc/rfc1952.txt)
 
 You just need to add em_inflate.c and em_inflate.h to your project and call em_inflate() to decompress some data.
diff --git a/lib/em_inflate.c b/lib/em_inflate.c
@@ -278,15 +278,14 @@ static int em_lsb_huffman_decoder_finalize_table(em_lsb_huffman_decoder_t *pDeco
 
          /* Write accelerated symbol value + codeword len for the (upside down) top NFASTSYMBOLBITS bits of the codeword, at all bit positions */
          if (nCanonicalLength <= NFASTSYMBOLBITS) {
-            unsigned int nRevWord = 0;
-            int j;
-            int nRevBits = nCanonicalLength;
-
-            /* Get upside down codeword */
-            for (j = 0; j < nRevBits; j++) {
-               if (nCanonicalCodeWord & (1 << (nRevBits - 1 - j)))
-                  nRevWord |= (1 << j);
-            }
+            unsigned int nRevWord;
+
+            /* Get upside down codeword (branchless method by Eric Biggers) */
+            nRevWord = ((nCanonicalCodeWord & 0x5555) << 1) | ((nCanonicalCodeWord & 0xaaaa) >> 1);
+            nRevWord = ((nRevWord & 0x3333) << 2) | ((nRevWord & 0xcccc) >> 2);
+            nRevWord = ((nRevWord & 0x0f0f) << 4) | ((nRevWord & 0xf0f0) >> 4);
+            nRevWord = ((nRevWord & 0x00ff) << 8) | ((nRevWord & 0xff00) >> 8);
+            nRevWord = nRevWord >> (16 - nCanonicalLength);
 
             int nSlots = 1 << (NFASTSYMBOLBITS - nCanonicalLength);
             while (nSlots) {