5#include "ns3/core-module.h"
142 bool Add(
const std::string phrase)
160 m_coll.emplace_back(h, phrase);
171 m_dict.insert(std::make_pair(h, phrase));
181 std::string name =
m_name;
186 name +=
" (32-bit version)";
189 name +=
" (64-bit version)";
192 name +=
" (unknown!?!)";
200 std::cout << std::endl;
202 std::cout <<
GetName() <<
": " <<
m_coll.size() <<
" collisions:" << std::endl;
203 for (
const auto& collision :
m_coll)
205 uint64_t h = collision.first;
207 std::cout << std::setfill(
'0') << std::hex << std::setw(8) << h << std::dec
208 << std::setfill(
' ') <<
" " << std::setw(20) << std::left
209 <<
m_dict.find(h)->second << collision.second << std::right << std::endl;
246 typedef std::vector<std::pair<uint64_t, std::string>>
collision_t;
281 void Add(
const std::string phrase)
288 bool newPhrases =
false;
291 newPhrases |= collider.Add(phrase);
343 long double k32 = 0xFFFFFFFF;
344 auto k64 =
static_cast<long double>(0xFFFFFFFFFFFFFFFFULL);
347 long double Ec32 = n * (n - 1) / (2 * k32) * (1 - (n - 2) / (3 * k32));
348 long double Ec64 = n * (n - 1) / (2 * k64) * (1 - (n - 2) / (3 * k64));
351 std::cout <<
"" << std::endl;
352 std::cout <<
"Number of words or phrases: " << n << std::endl;
353 std::cout <<
"Expected number of collisions: (32-bit table) " << Ec32 << std::endl;
354 std::cout <<
"Expected number of collisions: (64-bit table) " << Ec64 << std::endl;
362 for (
const auto& collider :
m_hashes)
379 for (
const auto& word :
m_words)
387 double delta = stop - start;
388 double per = 1e9 * delta / (
m_nphrases * reps * CLOCKS_PER_SEC);
390 std::cout << std::left << std::setw(32) << collider.
GetName() << std::right << std::setw(10)
391 <<
m_nphrases << std::setw(10) << reps << std::setw(10) << stop - start
392 << std::setw(12) << per << std::endl;
399 std::cout <<
"" << std::endl;
400 std::cout << std::left << std::setw(32) <<
"Hash timing" << std::right << std::setw(10)
401 <<
"Phrases" << std::setw(10) <<
"Reps" << std::setw(10) <<
"Ticks"
402 << std::setw(12) <<
"ns/hash" << std::endl;
404 for (
const auto& collider :
m_hashes)
429 bool Add(
const std::string& file)
442 return "/usr/share/dict/words";
457 std::cout <<
"Hashing the dictionar" << (
m_files.size() == 1 ?
"y" :
"ies") << std::endl;
459 for (
const auto& dictFile :
m_files)
461 std::cout <<
"Dictionary file: " << dictFile << std::endl;
466 std::ifstream dictStream;
467 dictStream.open(dictFile);
468 if (!dictStream.is_open())
470 std::cerr <<
"Failed to open dictionary file."
471 <<
"'" << dictFile <<
"'" << std::endl;
475 while (dictStream.good())
478 getline(dictStream, phrase);
503main(
int argc,
char* argv[])
505 std::cout << std::endl;
506 std::cout <<
"Hasher" << std::endl;
512 cmd.Usage(
"Find hash collisions in the dictionary.");
514 "Dictionary file to hash",
518 cmd.AddValue(
"time",
"Run timing test", timing);
519 cmd.Parse(argc, argv);
Parse command-line arguments.
Keep track of collisions.
Collider(const std::string name, Hasher hash, const Bits bits)
Constructor.
collision_t m_coll
The list of collisions.
std::map< uint64_t, std::string > hashdict_t
Hashed dictionary of first instance of each hash.
uint64_t GetHash(const std::string phrase)
Get the appropriate hash value.
std::string m_name
Name of this hash.
std::vector< std::pair< uint64_t, std::string > > collision_t
Collision map of subsequent instances.
void Report() const
Print the collisions found.
Bits
The size of hash function being tested.
@ Bits64
Use 64-bit hash function.
@ Bits32
Use 32-bit hash function.
bool Add(const std::string phrase)
Add a string to the Collider.
std::string GetName() const
hashdict_t m_dict
The dictionary map, indexed by hash.
Bits m_bits
Hash function.
std::vector< std::string > m_files
List of word files to use.
bool Add(const std::string &file)
CommandLine callback function to add a file argument to the list.
static std::string GetDefault()
void ReadInto(Dictionary &dict)
Add phrases from the files into the dict.
Word list and hashers to test.
void ReportExpectedCollisions() const
Report the expected number of collisions.
void Add(Collider c)
Add a Collider containing a hash function.
std::vector< std::string > m_words
List of unique words.
std::vector< Collider > m_hashes
List of hash Colliders.
void Report() const
Print the collisions for each Collider.
void TimeOne(const Collider &collider)
Time and report the execution of one hash across the entire Dictionary.
unsigned long m_nphrases
Number of strings hashed.
void Add(const std::string phrase)
Add a string to the dictionary.
void Time()
Report the execution time of each hash across the entire Dictionary.
Generic Hash function interface.
uint32_t GetHash32(const char *buffer, const std::size_t size)
Compute 32-bit hash of a byte buffer.
uint64_t GetHash64(const char *buffer, const std::size_t size)
Compute 64-bit hash of a byte buffer.
Hasher & clear()
Restore initial state.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Ptr< T > Create(Ts &&... args)
Create class instances by constructors with varying numbers of arguments and return them by Ptr.
Namespace for hasher-example.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Callback< R, Args... > MakeCallback(R(T::*memPtr)(Args...), OBJ objPtr)
Build Callbacks for class method members which take varying numbers of arguments and potentially retu...