smhasher/DifferentialTest.h

//-----------------------------------------------------------------------------
// Differential collision & distribution tests - generate a bunch of random keys,
// see what happens to the hash value when we flip a few bits of the key.

#pragma once

#include "Types.h"
#include "Stats.h"      // for chooseUpToK
#include "KeysetTest.h" // for SparseKeygenRecurse
#include "Random.h"

#include <vector>
#include <algorithm>
#include <stdio.h>

//-----------------------------------------------------------------------------
// Sort through the differentials, ignoring collisions that only occured once 
// (these could be false positives). If we find collisions of 3 or more, the
// differential test fails.

template < class keytype >
bool ProcessDifferentials ( std::vector<keytype> & diffs, int reps, bool dumpCollisions )
{
  std::sort(diffs.begin(), diffs.end());

  int count = 1;
  int ignore = 0;

  bool result = true;

  if(diffs.size())
  {
    keytype kp = diffs[0];

    for(int i = 1; i < (int)diffs.size(); i++)
    {
      if(diffs[i] == kp)
      {
        count++;
        continue;
      }
      else
      {
        if(count > 1)
        {
          result = false;

          double pct = 100 * (double(count) / double(reps));

          if(dumpCollisions)
          {
            printbits((unsigned char*)&kp,sizeof(kp));
            printf(" - %4.2f%%\n", pct );
          }
        }
        else 
        {
          ignore++;
        }

        kp = diffs[i];
        count = 1;
      }
    }

    if(count > 1)
    {
      double pct = 100 * (double(count) / double(reps));

      if(dumpCollisions)
      {
        printbits((unsigned char*)&kp,sizeof(kp));
        printf(" - %4.2f%%\n", pct );
      }
    }
    else 
    {
      ignore++;
    }
  }

  printf("%d total collisions, of which %d single collisions were ignored",(int)diffs.size(),ignore);

  if(result == false)
  {
    printf(" !!!!! ");
  }

  printf("\n");
  printf("\n");

  return result;
}

//-----------------------------------------------------------------------------
// Check all possible keybits-choose-N differentials for collisions, report
// ones that occur significantly more often than expected.

// Random collisions can happen with probability 1 in 2^32 - if we do more than
// 2^32 tests, we'll probably see some spurious random collisions, so don't report
// them.

template < typename keytype, typename hashtype >
void DiffTestRecurse ( pfHash hash, keytype & k1, keytype & k2, hashtype & h1, hashtype & h2, int start, int bitsleft, std::vector<keytype> & diffs )
{
  const int bits = sizeof(keytype)*8;

  for(int i = start; i < bits; i++)
  {
    flipbit(&k2,sizeof(k2),i);
    bitsleft--;

    hash(&k2,sizeof(k2),0,&h2);

    if(h1 == h2)
    {
      diffs.push_back(k1 ^ k2);
    }

    if(bitsleft)
    {
      DiffTestRecurse(hash,k1,k2,h1,h2,i+1,bitsleft,diffs);
    }

    flipbit(&k2,sizeof(k2),i);
    bitsleft++;
  }
}

//----------

template < typename keytype, typename hashtype >
bool DiffTest ( pfHash hash, int diffbits, int reps, bool dumpCollisions )
{
  const int keybits = sizeof(keytype) * 8;
  const int hashbits = sizeof(hashtype) * 8;

  double diffcount = chooseUpToK(keybits,diffbits);
  double testcount = (diffcount * double(reps));
  double expected  = testcount / pow(2.0,double(hashbits));

  Rand r(100);

  std::vector<keytype> diffs;

  keytype k1,k2;
  hashtype h1,h2;

  printf("Testing %0.f up-to-%d-bit differentials in %d-bit keys -> %d bit hashes.\n",diffcount,diffbits,keybits,hashbits);
  printf("%d reps, %0.f total tests, expecting %2.2f random collisions",reps,testcount,expected);

  for(int i = 0; i < reps; i++)
  {
    if(i % (reps/10) == 0) printf(".");

    r.rand_p(&k1,sizeof(keytype));
    k2 = k1;

    hash(&k1,sizeof(k1),0,(uint32_t*)&h1);

    DiffTestRecurse<keytype,hashtype>(hash,k1,k2,h1,h2,0,diffbits,diffs);
  }
  printf("\n");

  bool result = true;

  result &= ProcessDifferentials(diffs,reps,dumpCollisions);

  return result;
}

//-----------------------------------------------------------------------------
// Differential distribution test - for each N-bit input differential, generate
// a large set of differential key pairs, hash them, and test the output 
// differentials using our distribution test code.

// This is a very hard test to pass - even if the hash values are well-distributed,
// the differences between hash values may not be. It's also not entirely relevant
// for testing hash functions, but it's still interesting.

// This test is a _lot_ of work, as it's essentially a full keyset test for
// each of a potentially huge number of input differentials. To speed things
// along, we do only a few distribution tests per keyset instead of the full
// grid.

// #TODO - put diagram drawing back on

template < typename keytype, typename hashtype >
void DiffDistTest ( pfHash hash, const int diffbits, int trials, double & worst, double & avg )
{
  std::vector<keytype>  keys(trials);
  std::vector<hashtype> A(trials),B(trials);

  for(int i = 0; i < trials; i++)
  {
    rand_p(&keys[i],sizeof(keytype));

    hash(&keys[i],sizeof(keytype),0,(uint32_t*)&A[i]);
  }

  //----------

  std::vector<keytype> diffs;

  keytype temp(0);

  SparseKeygenRecurse<keytype>(0,diffbits,true,temp,diffs);

  //----------

  worst = 0;
  avg = 0;

  hashtype h2;

  for(size_t j = 0; j < diffs.size(); j++)
  {
    keytype & d = diffs[j];

    for(int i = 0; i < trials; i++)
    {
      keytype k2 = keys[i] ^ d;

      hash(&k2,sizeof(k2),0,&h2);

      B[i] = A[i] ^ h2;
    }

    double dworst,davg;

    TestDistributionFast(B,dworst,davg);

    avg += davg;
    worst = (dworst > worst) ? dworst : worst;
  }

  avg /= double(diffs.size());
}

//-----------------------------------------------------------------------------
// Simpler differential-distribution test - for all 1-bit differentials,
// generate random key pairs and run full distribution/collision tests on the
// hash differentials

template < typename keytype, typename hashtype >
bool DiffDistTest2 ( pfHash hash  )
{
  Rand r(857374);

  int keybits = sizeof(keytype) * 8;
  const int keycount = 256*256*32;
  keytype k;
  
  std::vector<hashtype> hashes(keycount);
  hashtype h1,h2;

  bool result = true;

  for(int keybit = 0; keybit < keybits; keybit++)
  {
    printf("Testing bit %d\n",keybit);

    for(int i = 0; i < keycount; i++)
    {
      r.rand_p(&k,sizeof(keytype));
      
      hash(&k,sizeof(keytype),0,&h1);
      flipbit(&k,sizeof(keytype),keybit);
      hash(&k,sizeof(keytype),0,&h2);

      hashes[i] = h1 ^ h2;
    }

    result &= TestHashList<hashtype>(hashes,true,true,true);
    printf("\n");
  }

  return result;
}

//----------------------------------------------------------------------------