Hardware friendly data decompression

1. A method, comprising:

receiving encoded data to be decompressed;

obtaining a size “S total ” of a total number of symbols in the encoded data, numbers of occurrences for distinct symbols in the encoded data, and a final state generated during an encoding process as a first state for decoding;

building a decoding table containing the distinct symbols corresponding to L encoding states, wherein L is equal to a sum of the numbers of occurrences for the distinct symbols;

decoding the encoded data using the decoding table including: obtaining a current symbol from the decoding table based on a current state X, dynamically determining a current number of bits to be recovered from the encoded data and a new state X; and

outputting symbols recovered from the encoded data.

2. The method of claim 1 , wherein the L encoding states are a range of L distinct values M to M+L−1 with M being a base value for the range and an integer equal to or larger than zero.

3. The method of claim 2 , wherein L is power of 2 and M is zero, and dynamically determining the current number of bits to be recovered from the encoded data and the new state X comprises:

obtaining a Symbol State Value (SSV) by b s+1 +X−2*b s or l s +X−b s , wherein “*” is a multiplication operator, b s and b s+1 are cumulative occurrences of the current symbol and next symbol in a set of symbols, and b n is set to L;

obtaining the current number of bits to be recovered from the encoded data as nBits=R−floor(Ig(SSV)); and

obtaining the new state X as [(SSV)<<nBits]−L+(nBits of the encoded data), wherein “<<” is a left shift operator.

4. The method of claim 2 , wherein L is not power of 2 and M is zero, and dynamically determining the current number of bits to be recovered from the encoded data and the new state X comprises:

setting an initial value of L s to a Symbol State Value (SSV), wherein the SSV is obtained by b s+1 +X−2*b s or l s +X−b s , in which “*” is a multiplication operator, b s and b s+1 are cumulative occurrences of the current symbol and next symbol in a set of symbols, and b n is set to L;

setting a value R to ceiling(Ig(L));

for an index “j” from 0 to R:

obtaining a temporary L s L s_tmp as (L s <<j)+(2{circumflex over ( )}j−1) until L s_tmp falls into an interval {L, . . . , 2L−1), wherein “<<” is a left shift operator, “{circumflex over ( )}” is an exponentiation operator, and

setting a number n_Bits to “j”;

setting X1 to [(SSV)<< n_Bits]−L+(n_Bits of the encoded data);

setting X2 to [(SSV)<<(n_Bits+1)]−L+[(n_Bits+1) of the encoded data];

determining which of X1 and X2 falls into a range of {0, . . . , L−1};

setting the current number of bits to be recovered from the encoded data as n_Bits and the new state X to X1 if X1 falls into the range of {0, . . . , L−1}; and

setting the current number of bits to be recovered from the encoded data as n_Bits+1 and the new state X to X2 if X2 falls into the range of {0, . . . , L−1}.

5. The method of claim 1 , further comprising obtaining a bit order and a concatenation order from metadata associated with the encoded data, the bit order specifying an order of bits when the encoded data is generated and the concatenation order specifying an order for sets of bits generated from consecutive symbols being concatenated together when the encoded data is generated.

6. The method of claim 1 , further comprising building a cumulative occurrences table for all symbols of a set of symbols based on the numbers of occurrences for the distinct symbols in the encoded data.

7. The method of claim 1 , further comprising, after decoding a last symbol from the encoded data, skipping dynamically determining the current number of bits to be recovered from the encoded data and the new state X.

8. The method of claim 1 , wherein the numbers of occurrences for the distinct symbols are reduced numbers of occurrences instead of actual numbers of occurrences.

9. The method of claim 1 , wherein the decoding table is built by an outer loop to go through all symbols in a set of symbols in the encoded data and an inner loop to go through all number of occurrences for each symbol.

10. The method of claim 9 , wherein the decoding table has a storage space for L entries each of lg(n) bits with n being a number of symbols in the set of symbols and lg( ) being a binary logarithm function.

11. A decompressor, comprising:

an un-packer configured to receive encoded data to be decompressed and obtain a size “S total ” of a total number of symbols in the encoded data, numbers of occurrences for distinct symbols in the encoded data, and a final state generated during an encoding process as a first state for decoding;

a decoding table constructor configured to build a decoding table containing the distinct symbols corresponding to L encoding states, wherein L is equal to a sum of the numbers of occurrences for the distinct symbols;

a decoding table storage to store the decoding table; and

a decoding engine configured to decode the encoded data using the decoding table including: obtain a current symbol from the decoding table based on a current state X, dynamically determine a current number of bits to be recovered from the encoded data and a new state X, and output symbols recovered from the encoded data.

12. The decompressor of claim 11 , wherein the L encoding states are a range of L distinct values M to M+L−1 with M being a base value for the range and an integer equal to or larger than zero.

13. The decompressor of claim 12 , wherein L is power of 2 and M is zero, and to dynamically determine the current number of bits to be recovered from the encoded data and the new state X, the decoding engine is further configured to:

obtain a Symbol State Value (SSV) by b s+1 +X−2*b s or l s +X−b s , wherein “*” is a multiplication operator, b s and b s+1 are cumulative occurrences of the current symbol and next symbol in a set of symbols, and b n is set to L;

obtain the current number of bits to be recovered from the encoded data as nBits=R−floor(Ig(SSV)); and

obtain the new state X as [(SSV)<<nBits]−L+(nBits of the encoded data), wherein “<<” is a left shift operator.

14. The decompressor of claim 12 , wherein L is not power of 2 and M is zero, and to dynamically determine the current number of bits to be recovered from the encoded data and the new state X, the decoding engine is further configured to:

set an initial value of L s to a Symbol State Value (SSV), wherein the SSV is obtained by b s+1 +X−2*b s or l s +X−b s , in which “*” is a multiplication operator, b s and b s+1 are cumulative occurrences of the current symbol and next symbol in a set of symbols, and b n is set to L;

set a value R to ceiling(Ig(L));

for an index “j” from 0 to R:

obtain a temporary L s L s_tmp as (L s <<j)+(2{circumflex over ( )}j−1) until L s_tmp falls into an interval {L, . . . , 2L−1), wherein “<<” is a left shift operator, “A” is an exponentiation operator, and set a number n_Bits to “j”;

set X1 to [(SSV)<<n_Bits]−L+(n_Bits of the encoded data);

set X2 to [(SSV)<<(n_Bits+1)]−L+[(n_Bits+1) of the encoded data];

determine which of X1 and X2 falls into a range of {0, . . . , L−1};

set the current number of bits to be recovered from the encoded data as n_Bits and the new state X to X1 if X1 falls into the range of {0, . . . , L−1}; and

set the current number of bits to be recovered from the encoded data as nBits+1 and the new state X to X2 if X2 falls into the range of {0, . . . , L−1}.

15. The decompressor of claim 11 , wherein the un-packer is further configured to obtain a bit order and a concatenation order from metadata associated with the encoded data, the bit order specifying an order of bits when the encoded data is generated and the concatenation order specifying an order for sets of bits generated from consecutive symbols being concatenated together when the encoded data is generated.

16. The decompressor of claim 11 , wherein the decoding table constructor is further configured to obtain a cumulative occurrences table for all symbols of a set of symbols based on the numbers of occurrences for the distinct symbols.

17. The decompressor of claim 11 , wherein the decoding engine is further configured to, after decode a last symbol from the encoded data, skip dynamically determining the current number of bits to be recovered from the encoded data and the new state X.

18. The decompressor of claim 11 , wherein the numbers of occurrences for the distinct symbols are reduced numbers of occurrences instead of actual numbers of occurrences.

19. The decompressor of claim 11 , wherein the decoding table is built by an outer loop to go through all symbols in a set of symbols in the encoded data and an inner loop to go through all number of occurrences for each symbol.

20. The decompressor of claim 19 , wherein the decoding table has a storage space for L entries each of lg(n) bits with n being a number of symbols in the set of symbols and lg( ) being a binary logarithm function.