25 #include "ns3/core-module.h"
152 bool Add (
const std::string phrase)
170 m_coll.push_back (std::make_pair (h, phrase));
181 m_dict.insert (std::make_pair (h, phrase));
191 std::string name =
m_name;
195 case Bits32: name +=
" (32-bit version)";
break;
196 case Bits64: name +=
" (64-bit version)";
break;
197 default: name +=
" (unknown!?!)";
205 std::cout << std::endl;
207 std::cout <<
GetName () <<
": " <<
m_coll.size () <<
" collisions:"
209 for (collision_t::const_iterator it =
m_coll.begin ();
213 uint64_t h = it->first;
215 std::cout << std::setfill (
'0') << std::hex << std::setw(8) << h
216 << std::dec << std::setfill(
' ') <<
" "
217 << std::setw(20) << std::left
218 <<
m_dict.find (h)->second
260 typedef std::vector < std::pair<uint64_t, std::string> >
collision_t;
295 void Add (
const std::string phrase)
297 if (phrase.size () == 0)
303 for (std::vector <Collider>::iterator it =
m_hashes.begin ();
307 newPhrases += it->Add (phrase);
359 long double k32 = 0xFFFFFFFF;
360 long double k64 = 0xFFFFFFFFFFFFFFFFULL;
363 long double Ec32 = n * (n - 1) / ( 2 * k32) * (1 - (n - 2)/(3 * k32));
364 long double Ec64 = n * (n - 1) / ( 2 * k64) * (1 - (n - 2)/(3 * k64));
367 std::cout <<
"" << std::endl;
368 std::cout <<
"Number of words or phrases: " << n << std::endl;
369 std::cout <<
"Expected number of collisions: (32-bit table) " << Ec32
371 std::cout <<
"Expected number of collisions: (64-bit table) " << Ec64
381 for (std::vector <Collider>::const_iterator it =
m_hashes.begin ();
399 int start = clock ();
400 for (std::vector<std::string>::const_iterator
w =
m_words.begin ();
404 for (uint32_t i = 0; i < reps; ++i)
410 double delta = stop -
start;
411 double per = 1e9 * delta / (
m_nphrases * reps * CLOCKS_PER_SEC);
413 std::cout << std::left
414 << std::setw (32) <<
m_hashes[hindex].GetName ()
417 << std::setw (10) << reps
418 << std::setw (10) << stop - start
419 << std::setw (12) << per
427 std::cout <<
"" << std::endl;
428 std::cout << std::left
429 << std::setw (32) <<
"Hash timing"
431 << std::setw (10) <<
"Phrases"
432 << std::setw (10) <<
"Reps"
433 << std::setw (10) <<
"Ticks"
434 << std::setw (12) <<
"ns/hash"
437 for (
unsigned int i = 0; i <
m_hashes.size (); ++i)
465 bool Add (
const std::string file)
484 Add (
"/usr/share/dict/web2");
487 std::cout <<
"Hashing the dictionar"
488 << (
m_files.size () == 1 ?
"y" :
"ies")
491 for (std::vector <std::string>::const_iterator it =
m_files.begin ();
495 std::string dictFile = *it;
496 std::cout <<
"Dictionary file: " << dictFile << std::endl;
501 std::ifstream dictStream;
502 dictStream.open (dictFile.c_str () );
503 if (! dictStream.is_open () )
505 std::cerr <<
"Failed to open dictionary file."
506 <<
"'" << dictFile <<
"'"
511 while (dictStream.good () )
514 getline (dictStream, phrase);
537 using namespace ns3::Hash::Example;
540 main (
int argc,
char *argv[])
542 std::cout << std::endl;
543 std::cout <<
"Hasher" << std::endl;
549 cmd.
Usage (
"Find hash collisions in the dictionary.");
550 cmd.
AddValue (
"dict",
"Dictionary file to hash",
553 cmd.
AddValue (
"time",
"Run timing test", timing);
554 cmd.
Parse (argc, argv);
558 Hasher ( Create<Hash::Function::Fnv1a> () ),
561 Hasher ( Create<Hash::Function::Fnv1a> () ),
565 Hasher ( Create<Hash::Function::Murmur3> () ),
568 Hasher ( Create<Hash::Function::Murmur3> () ),
Use 32-bit hash function.
std::vector< std::pair< uint64_t, std::string > > collision_t
Collision map of subsequent instances.
void Add(const std::string phrase)
Add a string to the dictionary.
void TimeOne(const int hindex)
Time and report the execution of one hash across the entire Dictionary.
std::string GetName() const
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
void Report() const
Print the collisions found.
void Time()
Report the execution time of each hash across the entire Dictionary.
void ReportExpectedCollisions() const
Report the expected number of collisions.
bool Add(const std::string file)
CommandLine callback function to add a file argument to the list.
bool Add(const std::string phrase)
Add a string to the Collider.
unsigned long m_nphrases
Number of strings hashed.
void Usage(const std::string usage)
Supply the program usage and documentation.
Word list and hashers to test.
Collider(const std::string name, Hasher hash, const enum Bits bits)
Constructor.
uint32_t GetHash32(const char *buffer, const size_t size)
Compute 32-bit hash of a byte buffer.
Callback< R > MakeCallback(R(T::*memPtr)(void), OBJ objPtr)
std::vector< std::string > m_words
List of unique words.
Parse command-line arguments.
void ReadInto(Dictionary &dict)
Add phrases from the files into the dict.
Keep track of collisions.
std::string m_name
Name of this hash.
Hasher & clear(void)
Restore initial state.
Use 64-bit hash function.
std::vector< std::string > m_files
List of word files to use.
void Report() const
Print the collisions for each Collider.
enum Bits m_bits
Hash function.
std::vector< Collider > m_hashes
List of hash Colliders.
void Add(Collider c)
Add a Collider containing a hash function.
void AddValue(const std::string &name, const std::string &help, T &value)
Add a program argument, assigning to POD.
collision_t m_coll
The list of collisions.
void Parse(int argc, char *argv[])
Parse the program arguments.
hashdict_t m_dict
The dictionary map, indexed by hash.
uint64_t GetHash64(const char *buffer, const size_t size)
Compute 64-bit hash of a byte buffer.
std::map< uint64_t, std::string > hashdict_t
Hashed dictionary of first instance of each hash.
Generic Hash function interface.
Bits
The size of hash function being tested.
uint64_t GetHash(const std::string phrase)
Get the appropriate hash value.