dlib C++ Library - hash.cpp

// Copyright (C) 2011 Davis E. King (davis@dlib.net)
// License: Boost Software License See LICENSE.txt for the full license.
#include <sstream>
#include <string>
#include <cstdlib>
#include <ctime>
#include <dlib/hash.h>
#include <dlib/rand.h>
#include <dlib/matrix.h>
#include <dlib/byte_orderer.h>
#include "tester.h"
namespace 
{
 using namespace test;
 using namespace dlib;
 using namespace std;
 logger dlog("test.hash");
 template <typename T>
 void to_little (
 std::vector<T>& item
 )
 {
 byte_orderer bo;
 for (unsigned long i = 0; i < item.size(); ++i)
 bo.host_to_little(item[i]);
 }
 template <typename T>
 void to_little (
 matrix<T>& item
 )
 {
 byte_orderer bo;
 for (long r = 0; r < item.nr(); ++r)
 {
 for (long c = 0; c < item.nc(); ++c)
 {
 bo.host_to_little(item(r,c));
 }
 }
 }
 // Run the official test for MurmurHash3
 void murmur_hash_test()
 {
 uint8 key[256];
 uint32 hashes[256];
 uint32 final = 0;
 memset(key,0,sizeof(key));
 memset(hashes,0,sizeof(hashes));
 // 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)i;
 hashes[i] = murmur_hash3(key,i,256-i);
 }
 byte_orderer bo;
 bo.host_to_little(hashes);
 final = murmur_hash3(hashes,sizeof(hashes),0);
 // using ostringstream to avoid compiler error in visual studio 2005
 ostringstream sout;
 sout << hex << final;
 dlog << LINFO << "final: "<< sout.str();
 DLIB_TEST(final == 0xB0F57EE3);
 }
 void murmur_hash_128_test()
 {
 uint8 key[256];
 uint64 hashes[256*2];
 uint32 final = 0;
 memset(key,0,sizeof(key));
 memset(hashes,0,sizeof(hashes));
 // 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)i;
 const std::pair<uint64,uint64> temp = murmur_hash3_128bit(key,i,256-i);
 hashes[2*i] = temp.first;
 hashes[2*i+1] = temp.second;
 }
 byte_orderer bo;
 bo.host_to_little(hashes);
 final = static_cast<uint32>(murmur_hash3_128bit(hashes,sizeof(hashes),0).first);
 // using ostringstream to avoid compiler error in visual studio 2005
 ostringstream sout;
 sout << hex << final;
 dlog << LINFO << "final 64: "<< sout.str();
 DLIB_TEST(final == 0x6384BA69);
 }
 void test_murmur_hash_128_4()
 {
 byte_orderer bo;
 dlib::rand rnd;
 for (int i = 0; i < 100; ++i)
 {
 uint32 buf[4] = { rnd.get_random_32bit_number(), 
 rnd.get_random_32bit_number(),
 rnd.get_random_32bit_number(),
 rnd.get_random_32bit_number()
 };
 bo.host_to_little(buf);
 std::pair<uint64,uint64> temp1, temp2;
 // Make sure the 4 integer version of murmur hash does the same thing 
 // as the memory block version.
 temp1 = murmur_hash3_128bit(buf, sizeof(buf), 0);
 temp2 = murmur_hash3_128bit(buf[0], buf[1], buf[2], buf[3]);
 DLIB_TEST( temp1.first == temp2.first);
 DLIB_TEST( temp1.second == temp2.second);
 }
 }
 void test_murmur_hash_128_3()
 {
 byte_orderer bo;
 dlib::rand rnd;
 for (int i = 0; i < 100; ++i)
 {
 uint64 buf[2] = { rnd.get_random_64bit_number(), 
 rnd.get_random_64bit_number(),
 };
 const uint32 seed = rnd.get_random_32bit_number();
 bo.host_to_little(buf);
 std::pair<uint64,uint64> temp1, temp2;
 // Make sure the 3 integer version of murmur hash does the same thing 
 // as the memory block version.
 temp1 = murmur_hash3_128bit(buf, sizeof(buf), seed);
 temp2 = murmur_hash3_128bit_3(buf[0], buf[1], seed);
 DLIB_TEST( temp1.first == temp2.first);
 DLIB_TEST( temp1.second == temp2.second);
 }
 }
 void test_murmur_hash_64_2()
 {
 byte_orderer bo;
 dlib::rand rnd;
 for (int i = 0; i < 100; ++i)
 {
 uint32 val = rnd.get_random_32bit_number();
 const uint32 seed = rnd.get_random_32bit_number();
 bo.host_to_little(val);
 uint32 temp1, temp2;
 // Make sure the 2 integer version of murmur hash does the same thing 
 // as the memory block version.
 temp1 = murmur_hash3(&val, sizeof(val), seed);
 temp2 = murmur_hash3_2(val, seed);
 DLIB_TEST(temp1 == temp2);
 }
 }
 void test_murmur_hash_64_3()
 {
 byte_orderer bo;
 dlib::rand rnd;
 for (int i = 0; i < 100; ++i)
 {
 uint32 buf[2] = {rnd.get_random_32bit_number(), 
 rnd.get_random_32bit_number()};
 const uint32 seed = rnd.get_random_32bit_number();
 bo.host_to_little(buf);
 uint32 temp1, temp2;
 // Make sure the 2 integer version of murmur hash does the same thing 
 // as the memory block version.
 temp1 = murmur_hash3(&buf, sizeof(buf), seed);
 temp2 = murmur_hash3_3(buf[0], buf[1], seed);
 DLIB_TEST(temp1 == temp2);
 }
 }
// ----------------------------------------------------------------------------------------
 uint64 slow_count_bits ( uint64 v)
 {
 uint64 count = 0;
 for (int i = 0; i < 64; ++i)
 {
 if (v&1)
 ++count;
 v >>= 1;
 }
 return count;
 }
 uint32 slow_count_bits ( uint32 v)
 {
 uint32 count = 0;
 for (int i = 0; i < 32; ++i)
 {
 if (v&1)
 ++count;
 v >>= 1;
 }
 return count;
 }
// ----------------------------------------------------------------------------------------
 void test_hamming_stuff()
 {
 dlib::rand rnd;
 for (int i = 0; i < 10000; ++i)
 {
 uint32 v = rnd.get_random_32bit_number();
 uint64 v2 = rnd.get_random_64bit_number();
 DLIB_TEST(slow_count_bits(v) == count_bits(v));
 DLIB_TEST(slow_count_bits(v2) == count_bits(v2));
 }
 DLIB_TEST(hamming_distance((uint32)0x1F, (uint32)0x0F) == 1);
 DLIB_TEST(hamming_distance((uint32)0x1F, (uint32)0x1F) == 0);
 DLIB_TEST(hamming_distance((uint32)0x1F, (uint32)0x19) == 2);
 DLIB_TEST(hamming_distance((uint32)0x2F, (uint32)0x19) == 4);
 }
// ----------------------------------------------------------------------------------------
 class test_hash : public tester
 {
 public:
 test_hash (
 ) :
 tester ("test_hash",
 "Runs tests on the hash routines.")
 {}
 void perform_test (
 )
 {
 print_spinner();
 test_hamming_stuff();
 murmur_hash_test();
 murmur_hash_128_test();
 std::string str1 = "some random string";
 matrix<unsigned char> mat(2,2);
 mat = 1,2,3,4;
 matrix<uint64> mat2(2,3);
 mat2 = 1,2,3,4,5,6;
 to_little(mat2);
 std::vector<unsigned char> v(4);
 v[0] = 'c';
 v[1] = 'a';
 v[2] = 't';
 v[3] = '!';
 std::vector<uint16> v2(4);
 v[0] = 'c';
 v[1] = 'a';
 v[2] = 't';
 v[3] = '!';
 to_little(v2);
 std::map<unsigned char, unsigned char> m;
 m['c'] = 'C';
 m['a'] = 'A';
 m['t'] = 'T';
 dlog << LINFO << "hash(str1): "<< dlib::hash(str1);
 dlog << LINFO << "hash(v): "<< dlib::hash(v);
 dlog << LINFO << "hash(v2): "<< dlib::hash(v2);
 dlog << LINFO << "hash(m): "<< dlib::hash(m);
 dlog << LINFO << "hash(mat): "<< dlib::hash(mat);
 dlog << LINFO << "hash(mat2): "<< dlib::hash(mat2);
 uint32 ui1 = 123485393;
 uint64 ui2 = ui1;
 ui2 *= ui2;
 ui2 *= ui2;
 dlog << LINFO << "hash(ui1): "<< dlib::hash(ui1);
 dlog << LINFO << "hash(ui2): "<< dlib::hash(ui2);
 dlog << LINFO << "hash(make_pair(ui2,ui1)): "<< dlib::hash(make_pair(ui2,ui1));
 dlog << LINFO << "hash(make_pair(ui2,ui2)): "<< dlib::hash(make_pair(ui2,ui2));
 dlog << LINFO << "hash(make_pair(ui1,ui1)): "<< dlib::hash(make_pair(ui1,ui1));
 dlog << LINFO << "hash(ui1,3): "<< dlib::hash(ui1,3);
 dlog << LINFO << "hash(ui2,3): "<< dlib::hash(ui2,3);
 dlog << LINFO << "hash(make_pair(ui2,ui1),3): "<< dlib::hash(make_pair(ui2,ui1),3);
 dlog << LINFO << "hash(make_pair(ui2,ui2),3): "<< dlib::hash(make_pair(ui2,ui2),3);
 dlog << LINFO << "hash(make_pair(ui1,ui1),3): "<< dlib::hash(make_pair(ui1,ui1),3);
 DLIB_TEST(dlib::hash(ui1) == 0x63e272e4);
 DLIB_TEST(dlib::hash(ui2) == 0xaf55561a);
 DLIB_TEST(dlib::hash(make_pair(ui2,ui1)) == 0x52685376);
 DLIB_TEST(dlib::hash(make_pair(ui2,ui2)) == 0xd25d6929);
 DLIB_TEST(dlib::hash(make_pair(ui1,ui1)) == 0xeea3b63e);
 DLIB_TEST(dlib::hash(ui1,3) == 0x95d1c4c0);
 DLIB_TEST(dlib::hash(ui2,3) == 0x6ada728d);
 DLIB_TEST(dlib::hash(make_pair(ui2,ui1),3) == 0x2f72a0ff);
 DLIB_TEST(dlib::hash(make_pair(ui2,ui2),3) == 0xac1407f0);
 DLIB_TEST(dlib::hash(make_pair(ui1,ui1),3) == 0x39ad637a);
 DLIB_TEST(dlib::hash(str1) == 0x3ffe6bf6);
 DLIB_TEST(dlib::hash(v) == 0xf1af2ca6);
 DLIB_TEST(dlib::hash(v2) == 0x63852afc);
 DLIB_TEST(dlib::hash(m) == 0xaacc3f6f);
 DLIB_TEST(dlib::hash(mat) == 0x3e349da5);
 DLIB_TEST(dlib::hash(mat2) == 0x3a95dc52);
 DLIB_TEST(murmur_hash3(&str1[0], str1.size(), 0) == 0x3ffe6bf6);
 dlog << LINFO << "hash(str1,1): "<< dlib::hash(str1,1);
 dlog << LINFO << "hash(v,3): "<< dlib::hash(v,3);
 dlog << LINFO << "hash(v2,3): "<< dlib::hash(v2,3);
 dlog << LINFO << "hash(m,4): "<< dlib::hash(m,4);
 dlog << LINFO << "hash(mat,5): "<< dlib::hash(mat,5);
 dlog << LINFO << "hash(mat2,6): "<< dlib::hash(mat2,6);
 DLIB_TEST(dlib::hash(str1,1) == 0xb17cea93);
 DLIB_TEST(dlib::hash(v,3) == 0x7ec9284c);
 DLIB_TEST(dlib::hash(v2,3) == 0xb2ce147f);
 DLIB_TEST(dlib::hash(m,4) == 0xfa5e7ac2);
 DLIB_TEST(dlib::hash(mat,5) == 0x8de27259);
 DLIB_TEST(dlib::hash(mat2,6) == 0xb8aa7714);
 DLIB_TEST(murmur_hash3(&str1[0], str1.size(), 1) == 0xb17cea93);
 test_murmur_hash_128_4();
 test_murmur_hash_128_3();
 test_murmur_hash_64_2();
 test_murmur_hash_64_3();
 }
 } a;
}