LZMS: more bit decoding/encoding optimizations

diff --git a/include/wimlib/lzms_common.h b/include/wimlib/lzms_common.h
index 69b6e67b4dbbeebd76463be5a39e4322a838ca53..093e50d2d0de1c073b926cf0a0001c6588088c50 100644 (file)
--- a/include/wimlib/lzms_common.h
+++ b/include/wimlib/lzms_common.h
@@ -76,11 +76,34 @@ lzms_update_probability_entry(struct lzms_probability_entry *entry, int bit)
 {
        BUILD_BUG_ON(LZMS_PROBABILITY_DENOMINATOR != sizeof(entry->recent_bits) * 8);
 
 {
        BUILD_BUG_ON(LZMS_PROBABILITY_DENOMINATOR != sizeof(entry->recent_bits) * 8);
 

-       s32 delta_zero_bits = (s32)(entry->recent_bits >>
-                                   (LZMS_PROBABILITY_DENOMINATOR - 1)) - bit;
-
-       entry->num_recent_zero_bits += delta_zero_bits;
-       entry->recent_bits = (entry->recent_bits << 1) | bit;
+#ifdef __x86_64__
+       if (__builtin_constant_p(bit)) {
+               /* Optimized implementation for x86_64 using carry flag  */
+               if (bit) {
+                      __asm__("shlq %[recent_bits]                          \n"
+                              "adcl $0xffffffff, %[num_recent_zero_bits]    \n"
+                              "orq $0x1, %[recent_bits]                     \n"
+                              : [recent_bits] "+r" (entry->recent_bits),
+                                [num_recent_zero_bits] "+mr" (entry->num_recent_zero_bits)
+                              :
+                              : "cc");
+               } else {
+                      __asm__("shlq %[recent_bits]                          \n"
+                              "adcl $0x0, %[num_recent_zero_bits]           \n"
+                              : [recent_bits] "+m" (entry->recent_bits),
+                                [num_recent_zero_bits] "+mr" (entry->num_recent_zero_bits)
+                              :
+                              : "cc");
+               }
+       } else
+#endif
+       {
+               s32 delta_zero_bits = (s32)(entry->recent_bits >>
+                                           (LZMS_PROBABILITY_DENOMINATOR - 1)) - bit;
+
+               entry->num_recent_zero_bits += delta_zero_bits;
+               entry->recent_bits = (entry->recent_bits << 1) | bit;
+       }

 }
 
 /* Given a probability entry, return the chance out of
 }
 
 /* Given a probability entry, return the chance out of


@@ -91,10 +114,19 @@ lzms_get_probability(const struct lzms_probability_entry *prob_entry)
        u32 prob = prob_entry->num_recent_zero_bits;
 
        /* 0% and 100% probabilities aren't allowed.  */
        u32 prob = prob_entry->num_recent_zero_bits;
 
        /* 0% and 100% probabilities aren't allowed.  */

-       if (prob == 0)
-               prob++;
-       else if (prob == LZMS_PROBABILITY_DENOMINATOR)
-               prob--;
+
+       /*
+        *      if (prob == 0)
+        *              prob++;
+        */
+       prob += (prob - 1) >> 31;
+
+       /*
+        *      if (prob == LZMS_PROBABILITY_DENOMINATOR)
+        *              prob--;
+        */
+       prob -= (prob >> LZMS_PROBABILITY_BITS);
+

        return prob;
 }
 
        return prob;
 }
 

diff --git a/src/lzms_decompress.c b/src/lzms_decompress.c
index d5d51417352b2ff5b81a8da2fdaaa27ca6e886ed..5093a3d32ed2e21322b1eba0f172eec0a8163659 100644 (file)
--- a/src/lzms_decompress.c
+++ b/src/lzms_decompress.c
@@ -463,18 +463,22 @@ lzms_decode_bit(struct lzms_range_decoder *rd, u32 *state_p, u32 num_states,
        /* Load the probability entry corresponding to the current state.  */
        prob_entry = &probs[*state_p];
 
        /* Load the probability entry corresponding to the current state.  */
        prob_entry = &probs[*state_p];
 

+       /* Update the state early.  We'll still need to OR the state with 1
+        * later if the decoded bit is a 1.  */
+       *state_p = (*state_p << 1) & (num_states - 1);
+
+       /* Get the probability (out of LZMS_PROBABILITY_DENOMINATOR) that the
+        * next bit is 0.  */
+       prob = lzms_get_probability(prob_entry);
+

        /* Normalize if needed.  */
        /* Normalize if needed.  */

-       if (rd->range <= 0xffff) {
+       if (!(rd->range & 0xFFFF0000)) {

                rd->range <<= 16;
                rd->code <<= 16;
                if (likely(rd->next != rd->end))
                        rd->code |= le16_to_cpu(*rd->next++);
        }
 
                rd->range <<= 16;
                rd->code <<= 16;
                if (likely(rd->next != rd->end))
                        rd->code |= le16_to_cpu(*rd->next++);
        }
 

-       /* Get the probability (out of LZMS_PROBABILITY_DENOMINATOR) that the
-        * next bit is 0.  */
-       prob = lzms_get_probability(prob_entry);
-

        /* Based on the probability, calculate the bound between the 0-bit
         * region and the 1-bit region of the range.  */
        bound = (rd->range >> LZMS_PROBABILITY_BITS) * prob;
        /* Based on the probability, calculate the bound between the 0-bit
         * region and the 1-bit region of the range.  */
        bound = (rd->range >> LZMS_PROBABILITY_BITS) * prob;


@@ -484,7 +488,6 @@ lzms_decode_bit(struct lzms_range_decoder *rd, u32 *state_p, u32 num_states,
                rd->range = bound;
 
                /* Update the state and probability entry based on the decoded bit.  */
                rd->range = bound;
 
                /* Update the state and probability entry based on the decoded bit.  */

-               *state_p = ((*state_p << 1) | 0) & (num_states - 1);

                lzms_update_probability_entry(prob_entry, 0);
                return 0;
        } else {
                lzms_update_probability_entry(prob_entry, 0);
                return 0;
        } else {


@@ -493,8 +496,8 @@ lzms_decode_bit(struct lzms_range_decoder *rd, u32 *state_p, u32 num_states,
                rd->code -= bound;
 
                /* Update the state and probability entry based on the decoded bit.  */
                rd->code -= bound;
 
                /* Update the state and probability entry based on the decoded bit.  */

-               *state_p = ((*state_p << 1) | 1) & (num_states - 1);

                lzms_update_probability_entry(prob_entry, 1);
                lzms_update_probability_entry(prob_entry, 1);

+               *state_p |= 1;

                return 1;
        }
 }
                return 1;
        }
 }