Hexadecimal compression

[CompressMaster]

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

1000000 0% hexadecimal data.txt

CompressMaster

[SpyFX]

hex2bin 500000 50% .... it's my first bid, lol

[Shelwien]

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 :)

[Bulat Ziganshin]

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/

[schnaader]

“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).

[Shelwien]

> 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;

}

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

[JamesB]

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.

[Sportman]

Truly random is difficult:
https://www.yubico.com/support/secur...s/ysa-2019-02/
https://www.yubico.com/replaceorder/