25 #include "ns3/core-module.h"
75 bool Add (
const std::string phrase)
93 m_coll.push_back (std::make_pair (h, phrase));
104 m_dict.insert (std::make_pair (h, phrase));
114 std::string name =
m_name;
118 case Bits32: name +=
" (32-bit version)";
break;
119 case Bits64: name +=
" (64-bit version)";
break;
120 default: name +=
" (unknown!?!)";
128 std::cout << std::endl;
130 std::cout <<
GetName () <<
": " <<
m_coll.size () <<
" collisions:"
132 for (collision_t::const_iterator it =
m_coll.begin ();
136 uint64_t h = it->first;
138 std::cout << std::setfill (
'0') << std::hex << std::setw(8) << h
139 << std::dec << std::setfill(
' ') <<
" "
140 << std::setw(20) << std::left
141 <<
m_dict.find (h)->second
183 typedef std::vector < std::pair<uint64_t, std::string> >
collision_t;
214 void Add (
const std::string phrase)
216 if (phrase.size () == 0)
222 for (std::vector <Collider>::iterator it =
m_hashes.begin ();
226 newPhrases += it->Add (phrase);
278 long double k32 = 0xFFFFFFFF;
279 long double k64 = 0xFFFFFFFFFFFFFFFFULL;
282 long double Ec32 = n * (n - 1) / ( 2 * k32) * (1 - (n - 2)/(3 * k32));
283 long double Ec64 = n * (n - 1) / ( 2 * k64) * (1 - (n - 2)/(3 * k64));
286 std::cout <<
"" << std::endl;
287 std::cout <<
"Number of words or phrases: " << n << std::endl;
288 std::cout <<
"Expected number of collisions: (32-bit table) " << Ec32
290 std::cout <<
"Expected number of collisions: (64-bit table) " << Ec64
300 for (std::vector <Collider>::const_iterator it =
m_hashes.begin ();
318 int start = clock ();
319 for (std::vector<std::string>::const_iterator
w =
m_words.begin ();
323 for (uint32_t i = 0; i < reps; ++i)
329 double delta = stop -
start;
330 double per = 1e9 * delta / (
m_nphrases * reps * CLOCKS_PER_SEC);
332 std::cout << std::left
333 << std::setw (32) <<
m_hashes[hindex].GetName ()
336 << std::setw (10) << reps
337 << std::setw (10) << stop - start
338 << std::setw (12) << per
346 std::cout <<
"" << std::endl;
347 std::cout << std::left
348 << std::setw (32) <<
"Hash timing"
350 << std::setw (10) <<
"Phrases"
351 << std::setw (10) <<
"Reps"
352 << std::setw (10) <<
"Ticks"
353 << std::setw (12) <<
"ns/hash"
356 for (
unsigned int i = 0; i <
m_hashes.size (); ++i)
384 bool Add (
const std::string file)
403 Add (
"/usr/share/dict/web2");
406 std::cout <<
"Hashing the dictionar"
407 << (
m_files.size () == 1 ?
"y" :
"ies")
410 for (std::vector <std::string>::const_iterator it =
m_files.begin ();
414 std::string dictFile = *it;
415 std::cout <<
"Dictionary file: " << dictFile << std::endl;
420 std::ifstream dictStream;
421 dictStream.open (dictFile.c_str () );
422 if (! dictStream.is_open () )
424 std::cerr <<
"Failed to open dictionary file."
425 <<
"'" << dictFile <<
"'"
430 while (dictStream.good () )
433 getline (dictStream, phrase);
456 using namespace ns3::Hash::Example;
461 std::cout << std::endl;
462 std::cout <<
"Hasher" << std::endl;
468 cmd.
Usage (
"Find hash collisions in the dictionary.");
469 cmd.
AddValue (
"dict",
"Dictionary file to hash",
472 cmd.
AddValue (
"time",
"Run timing test", timing);
473 cmd.
Parse (argc, argv);
477 Hasher ( Create<Hash::Function::Fnv1a> () ),
480 Hasher ( Create<Hash::Function::Fnv1a> () ),
484 Hasher ( Create<Hash::Function::Murmur3> () ),
487 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
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.
NS_LOG_COMPONENT_DEFINE("Hasher")
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.
int main(int argc, char *argv[])
std::map< uint64_t, std::string > hashdict_t
Hashed dictionary of first instance of each hash.
Generic Hash function interface.
uint64_t GetHash(const std::string phrase)
Get the appropriate hash value.