#include "KeysetTest.h"

#include "Platform.h"
#include "Random.h"

#include <map>
#include <set>

//-----------------------------------------------------------------------------
// This should hopefully be a thorough and uambiguous test of whether a hash
// is correctly implemented on a given platform

bool VerificationTest ( pfHash hash, const int hashbits, uint32_t expected, bool verbose )
{
  const int hashbytes = hashbits / 8;

  uint8_t * key    = new uint8_t[256];
  uint8_t * hashes = new uint8_t[hashbytes * 256];
  uint8_t * final  = new uint8_t[hashbytes];

  memset(key,0,256);
  memset(hashes,0,hashbytes*256);
  memset(final,0,hashbytes);

  // Hash keys of the form {0}, {0,1}, {0,1,2}... up to N=255,using 256-N as
  // the seed

  for(int i = 0; i < 256; i++)
  {
    key[i] = (uint8_t)i;

    hash(key,i,256-i,&hashes[i*hashbytes]);
  }

  // Then hash the result array

  hash(hashes,hashbytes*256,0,final);

  // The first four bytes of that hash, interpreted as a little-endian integer, is our
  // verification value

  uint32_t verification = (final[0] << 0) | (final[1] << 8) | (final[2] << 16) | (final[3] << 24);

  delete [] key;
  delete [] hashes;
  delete [] final;

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

  if(expected != verification)
  {
    if(verbose) fprintf(stderr,"Verification value 0x%08X : Failed! (Expected 0x%08x)\n",verification,expected);
    return false;
  }
  else
  {
    if(verbose) fprintf(stderr,"Verification value 0x%08X : Passed!\n",verification);
    return true;
  }
}

//----------------------------------------------------------------------------
// Basic sanity checks -

// A hash function should not be reading outside the bounds of the key.

// Flipping a bit of a key should, with overwhelmingly high probability,
// result in a different hash.

// Hashing the same key twice should always produce the same result.

// The memory alignment of the key should not affect the hash result.

bool SanityTest ( pfHash hash, const int hashbits )
{
	
	// return true;
	
	fprintf(stderr,"Running sanity check 1");

  Rand r(883741);

  bool result = true;
  bool diff = true;
  bool same = true;

  const int hashbytes = hashbits/8;
//  const int reps = 10;
  const int reps = 1;
  const int keymax = 256;
  const int pad = 16;
  const int buflen = keymax + pad*3;
  
  uint8_t * buffer1 = new uint8_t[buflen];
  uint8_t * buffer2 = new uint8_t[buflen];

  uint8_t * hash1 = new uint8_t[hashbytes];
  uint8_t * hash2 = new uint8_t[hashbytes];

  //----------
  
  for(int irep = 0; irep < reps; irep++)
  {
 //   if(irep % (reps/10) == 0) fprintf(stderr,".");

    for(int len = 4; len <= keymax; len++)
    {
      for(int offset = pad; offset < pad*2; offset++)
      {
        uint8_t * key1 = &buffer1[pad];
        uint8_t * key2 = &buffer2[pad+offset];
        // uint8_t * key2 = &buffer2[pad]; // no offset

        r.rand_p(buffer1,buflen);
        r.rand_p(buffer2,buflen);

				memcpy(key2,key1,len);				
				
				hash(key1,len,0,hash1);
								
        for(int bit = 0; bit < (len * 8); bit++)
        {
          // Flip a bit, hash the key -> we should get a different result.
          flipbit(key2,len,bit);
          hash(key2,len,0,hash2);


        	if(memcmp(hash1,hash2,hashbytes) == 0)
          {
						fprintf(stderr,"\nkey1 = "); for (int m=0; m<len; m++) fprintf(stderr,"%02X", key1[m]);
						fprintf(stderr,"\nkey2 = "); for (int m=0; m<len; m++) fprintf(stderr,"%02X", key2[m]);
						fprintf(stderr,"\n");

						fprintf(stderr,"\ndiff => hash1 = "); for (int m=0; m<hashbytes; m++) fprintf(stderr,"%02X", hash1[m]);
						fprintf(stderr,"\ndiff => hash2 = "); for (int m=0; m<hashbytes; m++) fprintf(stderr,"%02X", hash2[m]);
						fprintf(stderr,"\n");
						
            result = false;
						diff = false;
						
						fprintf(stderr,"\nbit, len, offset = %d, %d, %d\n", bit, len, offset);

						// break
						offset = pad*2;
						len = keymax;
						bit = (len * 8);
          }

          // Flip it back, hash again -> we should get the original result.
          // flipbit(key2,len,bit);
					// hash(key2,len,0,hash2);
					
					// somethings wrong with back flipping so use key1 instead
          hash(key1,len,0,hash2);


          if (memcmp(hash1,hash2,hashbytes) != 0)
          {
						fprintf(stderr,"\nkey1 = "); for (int m=0; m<len; m++) fprintf(stderr,"%02X", key1[m]);
						fprintf(stderr,"\nkey2 = "); for (int m=0; m<len; m++) fprintf(stderr,"%02X", key2[m]);
						fprintf(stderr,"\n");
						
						fprintf(stderr,"\nsame <= hash1 = "); for (int m=0; m<hashbytes; m++) fprintf(stderr,"%02X", hash1[m]);
						fprintf(stderr,"\nsame <= hash2 = "); for (int m=0; m<hashbytes; m++) fprintf(stderr,"%02X", hash2[m]);
						fprintf(stderr,"\n");
						
            result = false;
						same = false;

						
						fprintf(stderr,"\nbit, len, offset = %d, %d, %d\n", bit, len, offset);
						
						// break
						offset = pad*2;
						len = keymax;
						bit = (len * 8);
          }
        }
      }
    }
  }

  if(result == false)
  {
    fprintf(stderr," *********FAIL 1*********\n");

		if (diff == false) fprintf(stderr," *********DIFF*********\n");
		if (same == false) fprintf(stderr," *********SAME*********\n");
		
		fprintf(stderr,"\nsame <= hash1 = "); for (int m=0; m<hashbytes; m++) fprintf(stderr,"%02X", hash1[m]);
		fprintf(stderr,"\nsame <= hash2 = "); for (int m=0; m<hashbytes; m++) fprintf(stderr,"%02X", hash2[m]);
		fprintf(stderr,"\n");
	}
  else
  {
    fprintf(stderr," PASS\n");
  }
	
  delete [] buffer1;
  delete [] buffer2;

  delete [] hash1;
  delete [] hash2;

  return result;
}

//----------------------------------------------------------------------------
// Appending zero bytes to a key should always cause it to produce a different
// hash value

void AppendedZeroesTest ( pfHash hash, const int hashbits )
{
  fprintf(stderr,"Running sanity check 2");
  
  Rand r(173994);

  const int hashbytes = hashbits/8;

//	fprintf(stderr,"hashbytes = %d\n", hashbytes);

  for(int rep = 0; rep < 1; rep++)
//  for(int rep = 0; rep < 100; rep++)
  {
//    if(rep % 10 == 0) fprintf(stderr,".");

    // unsigned char key[256];
    unsigned char key[256 + 32]; // really lengthen the key
    memset(key,0,sizeof(key));

    r.rand_p(key,32);

    uint32_t h1[16];
    uint32_t h2[16];
	
//    memset(h1,0,hashbytes); // does NOT empty the array !!!!
//    memset(h2,0,hashbytes);
		
		for (int m=0; m<hashbytes; m++) h1[m] = 0;
		for (int m=0; m<hashbytes; m++) h2[m] = 0;
		
    for(int i = 0; i < 32; i+=4)
    {
			//			hash(key,32+i,0,h1);
			// really lengthen the key
			key[32+i] = 0x00;
			hash(key,32+i,0,h1);

      if(memcmp(h1,h2,hashbytes) == 0)
      {
        fprintf(stderr," *********FAIL 2*********\n");

				// Always print key as Big Int
				fprintf(stderr,"\nkey = "); for (int m=0; m<(32+i); m++) {
				fprintf(stderr,"%02X ", key[m]);
				}
				fprintf(stderr,"\n");
	
				fprintf(stderr,"\nhash1 (FAIL) = "); for (int m=0; m<hashbytes; m++) fprintf(stderr,"%08X ", h1[m]);
				fprintf(stderr,"\nhash2 (FAIL) = "); for (int m=0; m<hashbytes; m++) fprintf(stderr,"%08X ", h2[m]);
				
				// return;
      }

			/*
			fprintf(stderr,"\nh1 = "); for (int m=0; m<hashbytes; m++) {
			 		fprintf(stderr,"%02X ", h1[m]);
			 	}
			fprintf(stderr,"\nh1 = "); for (int m=0; m<hashbytes; m++) {
				fprintf(stderr,"%02X ", h2[m]);
			}
			fprintf(stderr, "\n");
			sleep(2);
			*/
			
      memcpy(h2,h1,hashbytes);
    }
  }

  fprintf(stderr," PASS\n");
}

//-----------------------------------------------------------------------------
// Generate all keys of up to N bytes containing two non-zero bytes

void TwoBytesKeygen ( int maxlen, KeyCallback & c )
{
  //----------
  // Compute # of keys

  int keycount = 0;

  for(int i = 2; i <= maxlen; i++) keycount += (int)chooseK(i,2);

  keycount *= 255*255;

  for(int i = 2; i <= maxlen; i++) keycount += i*255;

  fprintf(stderr,"Keyset 'TwoBytes' - up-to-%d-byte keys, %d total keys\n",maxlen, keycount);

  c.reserve(keycount);

  //----------
  // Add all keys with one non-zero byte

  uint8_t key[256];

  memset(key,0,256);

  for(int keylen = 2; keylen <= maxlen; keylen++)
  for(int byteA = 0; byteA < keylen; byteA++)
  {
    for(int valA = 1; valA <= 255; valA++)
    {
      key[byteA] = (uint8_t)valA;

      c(key,keylen);
    }

    key[byteA] = 0;
  }

  //----------
  // Add all keys with two non-zero bytes

  for(int keylen = 2; keylen <= maxlen; keylen++)
  for(int byteA = 0; byteA < keylen-1; byteA++)
  for(int byteB = byteA+1; byteB < keylen; byteB++)
  {
    for(int valA = 1; valA <= 255; valA++)
    {
      key[byteA] = (uint8_t)valA;

      for(int valB = 1; valB <= 255; valB++)
      {
        key[byteB] = (uint8_t)valB;
        c(key,keylen);
      }

      key[byteB] = 0;
    }

    key[byteA] = 0;
  }
}

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

template< typename hashtype >
void DumpCollisionMap ( CollisionMap<hashtype,ByteVec> & cmap )
{
  typedef CollisionMap<hashtype,ByteVec> cmap_t;

  for(typename cmap_t::iterator it = cmap.begin(); it != cmap.end(); ++it)
  {
    const hashtype & hash = (*it).first;

    fprintf(stderr,"Hash - ");
    printbytes(&hash,sizeof(hashtype));
    fprintf(stderr,"\n");

    std::vector<ByteVec> & keys = (*it).second;

    for(int i = 0; i < (int)keys.size(); i++)
    {
      ByteVec & key = keys[i];

      fprintf(stderr,"Key  - ");
      printbytes(&key[0],(int)key.size());
      fprintf(stderr,"\n");
    }
    fprintf(stderr,"\n");
  }

}

// test code

void ReportCollisions ( pfHash hash )
{
  fprintf(stderr,"Hashing keyset\n");

  std::vector<uint128_t> hashes;

  HashCallback<uint128_t> c(hash,hashes);

  TwoBytesKeygen(20,c);

  fprintf(stderr,"%d hashes\n",(int)hashes.size());

  fprintf(stderr,"Finding collisions\n");

  HashSet<uint128_t> collisions;

  FindCollisions(hashes,collisions,1000);

  fprintf(stderr,"%d collisions\n",(int)collisions.size());

  fprintf(stderr,"Mapping collisions\n");

  CollisionMap<uint128_t,ByteVec> cmap;

  CollisionCallback<uint128_t> c2(hash,collisions,cmap);

  TwoBytesKeygen(20,c2);

  fprintf(stderr,"Dumping collisions\n");

  DumpCollisionMap(cmap);
}