Results 1 to 10 of 10

Thread: LZ77 with 12 bit hash table: what I do wrong?

Threaded View

Previous Post Previous Post   Next Post Next Post
  1. #1
    Member lz77's Avatar
    Join Date
    Jan 2016
    Location
    Russia
    Posts
    49
    Thanks
    15
    Thanked 11 Times in 7 Posts

    Question LZ77 with 12 bit hash table: what I do wrong?

    Here's an algorithm for LZ77 compression. function LZ4_compress_generic in lz4.c uses such algorithm:
    U32 calcHash(U32 s) { return s*2654435761U >> 20; }

    function compress(char* source, char* dest, int source_size)
    { Fill in hash_table[4096] with 0xFFFFFFFF;

    anchor=source;
    // Main loop
    while (rest of source_size > 3)
    { hash=calcHash(U32 *source);
    if (hash_table[hash] == 0xFFFFFFFF) || (source-hash_table(hash) > 65535) || (U32 *source != U32 *hash_table[hash])
    { hash_table[hash]=source++;
    continue;
    }
    match_num=4;
    Calculating additional number of matched bytes both from left and right of source:
    match_num=number of total matched bytes
    Coding llllmmmm oooooooo oooooooo [l]...[l] [literals] [m]...[m]:
    number_of_literals=source-anchor;
    match_num;
    offset=source-hash_table[hash];

    hash_table[hash]=source;
    source+=match_num;
    anchor=source;
    hash_table[calcHash(U32 *(source-2)]=source-2;
    }

    last_literals:
    ...
    }


    lz4 on level=1 shows compression ratio of enwik8 ~ 53%. But if I run my code similar to the above algorithm, it shows ratio = 56.9%.
    My code shows ratio ~ 53% if size of hash_table = 32768 cells. What I do wrong?

    Thanks for your patience.
    Last edited by lz77; 31st July 2017 at 14:43.

Similar Threads

  1. Fast CRC table construction and rolling CRC hash calculation
    By Bulat Ziganshin in forum Data Compression
    Replies: 10
    Last Post: 27th May 2018, 04:32
  2. 32 bit or 64 bit Windows usage case
    By necros in forum The Off-Topic Lounge
    Replies: 10
    Last Post: 18th August 2016, 09:57
  3. Perfect Hash Function to Hash Strings
    By joey in forum Data Compression
    Replies: 18
    Last Post: 22nd March 2016, 11:59
  4. Filling a large Zobrist hash table
    By Earl Colby Pottinger in forum Data Compression
    Replies: 5
    Last Post: 11th October 2013, 14:05
  5. Compression benchmarking: 64 bit images and 24 bit codecs
    By m^2 in forum The Off-Topic Lounge
    Replies: 6
    Last Post: 30th November 2011, 17:01

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •