Avalanche Matrix Builder

'Avalanche Matrix Builder (c)2021, @_sorceress
'---------------------------------------------

'Plots output bits of the hash horizontally (Hi->Lo), and input bits of the key vertically (First->Last)
'The matrix shows the amount of bit flips in each output bit, when each input bit is flipped
'This is averaged over a large number of input keys. It may be impractical to try all input keys.

'red    = always/never flipped (bad)
'orange = flipped <1/3 or >2/3 of the time (not good, but acceptable for a few bits)
'green  = flipped between 1/3 and 2/3 of the time (good)

KeyBytes = 3 'size of keys, in bytes. 1->4
KeySamples = 50000 'number of random keys to analyse

'choose your hash function at the bottom on this listing



SCREEN _NEWIMAGE(640, 480, 256)

DIM Pow(31) AS _UNSIGNED LONG
Pow(0) = 1: FOR i = 1 TO 31: Pow(i) = Pow(i - 1) * 2: NEXT
DIM h AS _UNSIGNED LONG, h0 AS _UNSIGNED LONG
DIM F(31, 31) AS LONG

'build the avalanche matrix
KeyBits = KeyBytes * 8: L = Pow(KeyBits)
RANDOMIZE TIMER
FOR i = 0 TO KeySamples
  LOCATE 1, 1: PRINT INT(100 * i / KeySamples); "%"
  Key0 = INT(RND * L) 'random key
  sKey = Key0: GOSUB Hash: h0 = h 'hash the key to compare against
  FOR b0 = 0 TO KeyBits - 1 'consider bitflips
    sKey = Key0 XOR Pow(b0): GOSUB Hash
    FOR b1 = 0 TO 31
      IF (h AND Pow(b1)) <> (h0 AND Pow(b1)) THEN F(b1, b0) = F(b1, b0) + 1
      'bit b1 was flipped in the output, when bit b0 was flipped in the input. count this flip.
    NEXT
  NEXT
NEXT

'now display the avalanche matrix
d = KeySamples / 2 ' ideally the bits get flipped half of the time, so d is the number of flips corresponding to that ideal.
FOR b0 = 0 TO KeyBits - 1
  FOR b1 = 0 TO 31
    excess = ABS(F(31 - b1, b0) - d) 'How many more/less flips than d did we get?
    IF excess = d THEN COLOR 4 'red
    IF excess < d THEN COLOR 43 'orange
    IF excess < d / 3 THEN COLOR 2 'green
    LOCATE b0 + 1, b1 * 2 + 1 + b1 \ 8: PRINT "[]"
  NEXT
NEXT

END

'==========================================================
Hash:
GOSUB jenkins
RETURN

fnv1a: 'FNV1-a. A general purpose hash with good collision behaviour, but not great avalanching.
h = 2166136261
FOR j = 1 TO KeyBytes
  ch = sKey AND 255
  h = (h XOR ch) * 16777619
  sKey = sKey \ 256
NEXT
RETURN

djb2a: 'Bernstein's hash. Excellent collision behaviour for short alphanumeric keys, but terrible avalanching.
h = 5381
FOR j = 1 TO KeyBytes
  ch = sKey AND 255
  h = (h * 33) XOR ch
  sKey = sKey \ 256
NEXT
RETURN

jenkins: 'Jenkins one at a time. A bit slower with more overhead, but excellent avalanching.
h = 0
FOR j = 1 TO KeyBytes
  ch = sKey AND 255
  h = h + ch
  h = h * 1025
  h = h XOR (h \ 64)
  sKey = sKey \ 256
NEXT
h = h * 9
h = h XOR (h / 2048)
h = h * 32769
RETURN