search

skeeto / hash-prospector

Automated integer hash function discovery
The Unlicense
672 stars 27 forks source link

OP-REQ: byte shuffle for 64bit or 32bit operation #7

Open gzm55 opened 3 years ago

gzm55 commented 3 years ago

Bytes shuffling is another reversible operation and the effects should between mul and xorshift.

Logan007 commented 3 years ago

If SSSE3 can be assumed to be present (#include <immintrin.h>, #ifdef __SSSE3__), that would be the PSHUFB instruction or _mm_shuffle_epi8() intrinsic along with 128-bit XMM register store and read back (MOVD / MOVQ).

Tiny challenge here: The randomized parameter to PSHUFB itself needs to be a permutation of 0x00 ... 0x03 / 0x07. This could be solved by starting off from 0x00 ... 0x07 and randomly exchanging the values pairwise, e.g. four n x (n-1) times length = 32 times required (this is still somewhat flaky with a view to equi-distributed permutations).

gzm55 commented 3 years ago

Since the op is run as jit x86 codes, it could be always assumed as true to get SSSE3 instructions, otherwise this op can be force disabled.

The shuffle algorithm could help to generate the parameter.