lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On 10/13/2010 10:34 AM, David Manura wrote:
[snip snip snip]
Another area of difficulty involves a function that reverses the order
of bits [5].  There is not an easy way to optimize the pure Lua form
with existing native bitwise operations:

   local function msb(bits, nbits)
     local res = 0
     for i=1,nbits do
       local b = bits % 2
       bits = (bits - b) / 2
       res = res * 2 + b
     return res

LuaBitOp does implement a function "bswap" that reverses the order of
bytes, but that only would help partly (e.g. swap bytes with bswap and
then swap bits in each byte via an 8-bit lookup table).

Okay, one more niggling item...

Do you have timing data on the relative cost of building the Huffman trees? Should check it before deciding on whether to optimize this. It is called up to only ~300 times for both tables and this is done once per block of max 64KB of data. In any case, this one is restricted to the lengths of the Huffman code, 1-15 bits, as stated in the source code.

For example, in compressing a 111,261 byte text file (Calgary corpus, bib), on a version of LZF I get 19,443 LZ matches and 11,501 bytes of literals. This compares to 2 blocks of <=64KB in gzip, or maybe ~650 calls of bi_reverse() in gzip. So it is important to check how long the Huffman trees are taking to build, or relative workloads of each portion of gzip.

Kein-Hong Man (esq.)
Kuala Lumpur, Malaysia