25 #include "ns3/core-module.h"
154 bool Add (
const std::string phrase)
172 m_coll.push_back (std::make_pair (h, phrase));
183 m_dict.insert (std::make_pair (h, phrase));
193 std::string name =
m_name;
197 case Bits32: name +=
" (32-bit version)";
break;
198 case Bits64: name +=
" (64-bit version)";
break;
199 default: name +=
" (unknown!?!)";
207 std::cout << std::endl;
209 std::cout <<
GetName () <<
": " <<
m_coll.size () <<
" collisions:"
211 for (collision_t::const_iterator it =
m_coll.begin ();
215 uint64_t h = it->first;
217 std::cout << std::setfill (
'0') << std::hex << std::setw(8) << h
218 << std::dec << std::setfill(
' ') <<
" "
219 << std::setw(20) << std::left
220 <<
m_dict.find (h)->second
262 typedef std::vector < std::pair<uint64_t, std::string> >
collision_t;
297 void Add (
const std::string phrase)
299 if (phrase.size () == 0)
305 for (std::vector <Collider>::iterator it =
m_hashes.begin ();
309 newPhrases += it->Add (phrase);
361 long double k32 = 0xFFFFFFFF;
362 long double k64 = 0xFFFFFFFFFFFFFFFFULL;
365 long double Ec32 = n * (n - 1) / ( 2 * k32) * (1 - (n - 2)/(3 * k32));
366 long double Ec64 = n * (n - 1) / ( 2 * k64) * (1 - (n - 2)/(3 * k64));
369 std::cout <<
"" << std::endl;
370 std::cout <<
"Number of words or phrases: " << n << std::endl;
371 std::cout <<
"Expected number of collisions: (32-bit table) " << Ec32
373 std::cout <<
"Expected number of collisions: (64-bit table) " << Ec64
383 for (std::vector <Collider>::const_iterator it =
m_hashes.begin ();
401 int start = clock ();
402 for (std::vector<std::string>::const_iterator
w =
m_words.begin ();
406 for (uint32_t i = 0; i < reps; ++i)
412 double delta = stop -
start;
413 double per = 1e9 * delta / (
m_nphrases * reps * CLOCKS_PER_SEC);
415 std::cout << std::left
416 << std::setw (32) <<
m_hashes[hindex].GetName ()
419 << std::setw (10) << reps
420 << std::setw (10) << stop - start
421 << std::setw (12) << per
429 std::cout <<
"" << std::endl;
430 std::cout << std::left
431 << std::setw (32) <<
"Hash timing"
433 << std::setw (10) <<
"Phrases"
434 << std::setw (10) <<
"Reps"
435 << std::setw (10) <<
"Ticks"
436 << std::setw (12) <<
"ns/hash"
439 for (
unsigned int i = 0; i <
m_hashes.size (); ++i)
486 Add (
"/usr/share/dict/web2");
489 std::cout <<
"Hashing the dictionar"
490 << (
m_files.size () == 1 ?
"y" :
"ies")
493 for (std::vector <std::string>::const_iterator it =
m_files.begin ();
497 std::string dictFile = *it;
498 std::cout <<
"Dictionary file: " << dictFile << std::endl;
503 std::ifstream dictStream;
504 dictStream.open (dictFile.c_str () );
505 if (! dictStream.is_open () )
507 std::cerr <<
"Failed to open dictionary file."
508 <<
"'" << dictFile <<
"'"
513 while (dictStream.good () )
516 getline (dictStream, phrase);
542 main (
int argc,
char *argv[])
544 std::cout << std::endl;
545 std::cout <<
"Hasher" << std::endl;
551 cmd.
Usage (
"Find hash collisions in the dictionary.");
552 cmd.
AddValue (
"dict",
"Dictionary file to hash",
555 cmd.
AddValue (
"time",
"Run timing test", timing);
556 cmd.
Parse (argc, argv);
560 Hasher ( Create<Hash::Function::Fnv1a> () ),
563 Hasher ( Create<Hash::Function::Fnv1a> () ),
567 Hasher ( Create<Hash::Function::Murmur3> () ),
570 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.
Use 64-bit hash function.
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.
Bits
The size of hash function being tested.
Hasher & clear(void)
Restore initial state.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
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.
Namespace for hasher-example.
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.
uint64_t GetHash(const std::string phrase)
Get the appropriate hash value.