Results 1 to 8 of 8

Thread: Hexadecimal compression

  1. #1
    Member
    Join Date
    Jun 2018
    Location
    Slovakia
    Posts
    148
    Thanks
    41
    Thanked 8 Times in 8 Posts

    Hexadecimal compression

    Here´s hexadecimal compression challenge. It has been generated using online random generator. Challenge is simple - losslessly compress it to the smallest possible size.

    Code:
    1000000 0% hexadecimal data.txt
    CompressMaster
    Attached Files Attached Files

  2. #2
    Member
    Join Date
    Jun 2015
    Location
    Moscow
    Posts
    12
    Thanks
    3
    Thanked 2 Times in 2 Posts
    hex2bin 500000 50% .... it's my first bid, lol

  3. #3
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,362
    Thanks
    212
    Thanked 1,016 Times in 540 Posts
    Yes :)
    I tested it with cdm and paq and it doesn't seem compressible.

    Also, I guess that online service uses some crypto-random...
    I just tried writing such a generator using VS default PRNG,
      char b2h[] = "0123456789ABCDEF"; 
    for( i=0; i<N; i++ ) putc( b2h[rand()%16],g );

    and paq8px compressed it to 136k :)
    Attached Files Attached Files

  4. Thanks:

    xinix (13th June 2019)

  5. #4
    Programmer Bulat Ziganshin's Avatar
    Join Date
    Mar 2007
    Location
    Uzbekistan
    Posts
    4,507
    Thanks
    742
    Thanked 665 Times in 359 Posts
    I just tried writing such a generator using VS default PRNG,

    I can't believe that it's so predictable. What about LCG

    rnd = 29943829*rnd + 1013904223; // https://en.wikipedia.org/wiki/Linear...tial_generator

    and modern ones:

    1. http://xoshiro.di.unimi.it/
    2. http://www.pcg-random.org/

  6. #5
    Programmer schnaader's Avatar
    Join Date
    May 2008
    Location
    Hessen, Germany
    Posts
    564
    Thanks
    215
    Thanked 200 Times in 93 Posts
    “rand() % N“ is known to be bad, see this: https://stackoverflow.com/a/49880109/34065

    Basically, if RAND_MAX % N != 0, you get skewed results.

    Though in this case, it could indeed be the bad random generator, since N==16 should give good results (and the paq8px result points to a bigger skew).
    Last edited by schnaader; 14th June 2019 at 12:45.
    http://schnaader.info
    Damn kids. They're all alike.

  7. #6
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,362
    Thanks
    212
    Thanked 1,016 Times in 540 Posts
    > rnd = 29943829*rnd + 1013904223

    In this case, this has a period of 16 :)
    But with an extra shift, its good:
    unsigned rnd = 1;
    unsigned rng() {
    rnd = 29943829*rnd + 1013904223;
    return rnd>>24;
    }
    Code:
    1,000,000 1.hex
      500,000 1.bin
      500,148 1.7z
      136,563 1.bin.paq8px179fix3
    
    1,000,000 2.hex
      500,000 2.bin
      500,148 2.7z
      500,290 2.bin.paq8px179fix3
    Attached Files Attached Files

  8. #7
    Member
    Join Date
    Dec 2011
    Location
    Cambridge, UK
    Posts
    462
    Thanks
    147
    Thanked 158 Times in 106 Posts
    I recall on one machine if had a loop doing "rand()&1" to get random 0 and 1 bits then they alternated 0, 1, 0, 1, ... haha!

    [Edit: to be fair to the RNG, they sometimes alternated 1, 0, 1, 0 ... ]

    Fortunately MOST machines has long since moved to better random number generators. It's quite shocking if visual studio is still so bad.

  9. #8
    Member
    Join Date
    Aug 2008
    Location
    Planet Earth
    Posts
    788
    Thanks
    64
    Thanked 274 Times in 192 Posts

Similar Threads

  1. Hexadecimal collisions
    By CompressMaster in forum The Off-Topic Lounge
    Replies: 6
    Last Post: 12th June 2019, 18:43

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
  •