--- a/src/core/examples/hash-example.cc Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/examples/hash-example.cc Mon Nov 17 15:51:36 2014 -0800
@@ -25,483 +25,18 @@
#include "ns3/core-module.h"
#include "ns3/hash.h"
-namespace ns3
-{
-
-NS_LOG_COMPONENT_DEFINE ("Hasher");
-
-namespace Hash
-{
-
/**
- * \ingroup hash
- * Namespace for hasher-example
-*/
-namespace Example
-{
-
-/**
- * Keep track of collisions
- */
-class Collider {
-
-public:
- std::string m_name; /**< Name of this hash */
- Hasher m_hash; /**< The hash */
-
- enum Bits {
- Bits32, /**< Use 32-bit hash function */
- Bits64 /**< Use 64-bit hash function */
- };
-
- /**
- * Constructor
- *
- * \param [in] name Hash function name
- * \param [in] hash Hash function
- * \param [in] bits Which hash length to use
- */
- Collider (const std::string name, Hasher hash, const enum Bits bits)
- : m_name (name),
- m_hash (hash),
- m_bits (bits)
- { }
-
- /**
- * Add a string to the Collider
- *
- * \param [in] phrase the string to add
- * \return true if this was a new string
- */
- bool Add (const std::string phrase)
- {
- uint64_t h = GetHash (phrase);
-
- // Check for collisions
- if (m_dict.count (h) > 0)
- {
- // we've seen this hash before, why?
- if (phrase == m_dict[h])
- {
- // duplicate phrase
- return false;
- }
-
- // new phrase generating a real collision
- // alphabetize
- if ( m_dict[h] < phrase)
- {
- m_coll.push_back (std::make_pair (h, phrase));
- }
- else
- {
- m_coll.push_back (std::make_pair (h, m_dict[h]));
- m_dict[h] = phrase;
- }
- }
- else
- {
- // Insert new hash
- m_dict.insert (std::make_pair (h, phrase));
- }
- return true;
- } // Add ()
-
- /**
- * \return The hash name, including the length
- */
- std::string GetName () const
- {
- std::string name = m_name;
-
- switch (m_bits)
- {
- case Bits32: name += " (32-bit version)"; break;
- case Bits64: name += " (64-bit version)"; break;
- default: name += " (unknown!?!)";
- }
- return name;
- }
-
- /** Print the collisions found */
- void Report () const
- {
- std::cout << std::endl;
-
- std::cout << GetName () << ": " << m_coll.size () << " collisions:"
- << std::endl;
- for (collision_t::const_iterator it = m_coll.begin ();
- it != m_coll.end ();
- ++it)
- {
- uint64_t h = it->first;
-
- std::cout << std::setfill ('0') << std::hex << std::setw(8) << h
- << std::dec << std::setfill(' ') << " "
- << std::setw(20) << std::left
- << m_dict.find (h)->second
- << it->second
- << std::right
- << std::endl;
- }
- } // Report ()
-
-
-private:
-
- /**
- * Get the appropriate hash value
- *
- * \param [in] phrase the string to hash
- * \return the hash value, using the number of bits set in the constructor
- */
- uint64_t GetHash (const std::string phrase)
- {
- m_hash.clear ();
- uint64_t h = 0;
-
- if (m_bits == Bits32)
- {
- h = m_hash.GetHash32 (phrase);
- }
- else
- {
- h = m_hash.GetHash64 (phrase);
- }
- return h;
- }
-
- /** Hash function */
- enum Bits m_bits;
-
- /** Hashed dictionary of first instance of each hash */
- typedef std::map <uint64_t, std::string> hashdict_t;
-
- /** The dictionary map, indexed by hash */
- hashdict_t m_dict;
-
- /** Collision map of subsequent instances */
- typedef std::vector < std::pair<uint64_t, std::string> > collision_t;
-
- /** The list of collisions */
- collision_t m_coll;
-
-}; // class Collider
-
-
-/**
- * Word list and hashers to test
- */
-class Dictionary {
-public:
- /** Constructor */
- Dictionary ()
- : m_nphrases (0)
- {
- m_words.reserve (320000);
- }
-
- /** Add a Collider containing a hash function */
- void Add (Collider c)
- {
- m_hashes.push_back (c);
- }
-
- /**
- * Add a string to the dictionary
- *
- * \param [in] phrase the string to add
- */
- void Add (const std::string phrase)
- {
- if (phrase.size () == 0)
- {
- return ;
- }
-
- int newPhrases = 0;
- for (std::vector <Collider>::iterator it = m_hashes.begin ();
- it != m_hashes.end ();
- ++it)
- {
- newPhrases += it->Add (phrase);
- }
-
- if (newPhrases)
- {
- ++m_nphrases;
- m_words.push_back (phrase);
- }
- } // Add ()
-
- /**
- * Report the expected number of collisions
- *
- * See, e.g.,
- * http://www.math.dartmouth.edu/archive/m19w03/public_html/Section6-5.pdf
- *
- * \f[
- * E(collisions) = n - k + k (1 - 1/k)^n
- * \f]
- *
- * where <i>n</i> is the number of entries in the table, and
- * <i>k</i> is the number of buckets.
- *
- * This form is numerically unstable for low collision rates.
- * Expanding for large \f$ k \f$ we get
- *
- * \f{eqnarray*}{
- * E(c) &=& \frac{1}{k} {n \choose 2}
- * - \frac{1}{{{k^2}}} {n \choose 3}
- * + \frac{1}{{{k^3}}} {n \choose 4}
- * - \ldots \\
- * &=& \frac{1}{k} {n \choose 2}
- * \left[ {1 - \frac{{n - 2}}{{3k}}
- * + \frac{{\left( {n - 2} \right)
- * \left( {n - 3} \right)}}{{12{k^2}}}
- * - \ldots } \right] \\
- * &=& \frac{1}{k} {n \choose 2}
- * \left\{ {1 - \frac{{n - 2}}{{3k}}
- * \left[ {1 + \frac{{n - 3}}{{4k}}
- * - \ldots }
- * \right]}
- * \right\}
- * \f}
- *
- * For simplicity, we'll use the first two terms
- * of the second form.
- */
- void ReportExpectedCollisions () const
- {
- // Expected number of collisions
- //
- // Number of buckets = k = 2^bits
- long double k32 = 0xFFFFFFFF;
- long double k64 = 0xFFFFFFFFFFFFFFFFULL;
-
- long double n = m_nphrases;
- long double Ec32 = n * (n - 1) / ( 2 * k32) * (1 - (n - 2)/(3 * k32));
- long double Ec64 = n * (n - 1) / ( 2 * k64) * (1 - (n - 2)/(3 * k64));
-
- // Output collisions
- std::cout << "" << std::endl;
- std::cout << "Number of words or phrases: " << n << std::endl;
- std::cout << "Expected number of collisions: (32-bit table) " << Ec32
- << std::endl;
- std::cout << "Expected number of collisions: (64-bit table) " << Ec64
- << std::endl;
- } // ReportExpectedCollisions
-
-
- /** Print the collisions for each Collider */
- void Report () const
- {
- ReportExpectedCollisions ();
-
- for (std::vector <Collider>::const_iterator it = m_hashes.begin ();
- it != m_hashes.end ();
- ++it)
- {
- it->Report ();
- }
- } // Report ()
-
- /**
- * Time and report the execution of one hash across the entire Dictionary
- *
- * \param [in] hindex index of the hash Collider to use
- */
- void TimeOne (const int hindex)
- {
- // Hashing speed
- uint32_t reps = 100;
- Hasher h = m_hashes[hindex].m_hash;
- int start = clock ();
- for (std::vector<std::string>::const_iterator w = m_words.begin ();
- w != m_words.end();
- ++w)
- {
- for (uint32_t i = 0; i < reps; ++i)
- {
- h.clear ().GetHash32 (*w);
- }
- }
- int stop = clock ();
- double delta = stop - start;
- double per = 1e9 * delta / (m_nphrases * reps * CLOCKS_PER_SEC);
-
- std::cout << std::left
- << std::setw (32) << m_hashes[hindex].GetName ()
- << std::right
- << std::setw (10) << m_nphrases
- << std::setw (10) << reps
- << std::setw (10) << stop - start
- << std::setw (12) << per
- << std::endl;
-
- } // TimeOne ()
-
- /** Report the execution time of each hash across the entire Dictionary */
- void Time ()
- {
- std::cout << "" << std::endl;
- std::cout << std::left
- << std::setw (32) << "Hash timing"
- << std::right
- << std::setw (10) << "Phrases"
- << std::setw (10) << "Reps"
- << std::setw (10) << "Ticks"
- << std::setw (12) << "ns/hash"
- << std::endl;
-
- for (unsigned int i = 0; i < m_hashes.size (); ++i)
- {
- TimeOne (i);
- }
- } // Time ()
-
-private:
- unsigned long m_nphrases; /**< Number of strings hashed */
- std::vector <Collider> m_hashes; /**< List of hash Colliders */
- std::vector <std::string> m_words; /**< List of unique words */
-
-}; // class Dictionary
-
-
-/**
- * Source word list files
- */
-class DictFiles
-{
-
-public:
-
- /**
- * CommandLine callback function to add a file argument to the list
- *
- * \param [in] file the word file to add
- * \return true if the file is new to the list
- */
- bool Add (const std::string file)
- {
- if (std::find (m_files.begin (), m_files.end (), file) == m_files.end ())
- {
- m_files.push_back (file);
- }
-
- return true;
- }
-
- /**
- * Add phrases from the files into the dict
- *
- * \param [in,out] dict the Dictionary to add words to
- */
- void ReadInto (Dictionary & dict)
- {
- if (m_files.size () == 0)
- {
- Add ("/usr/share/dict/web2");
- }
-
- std::cout << "Hashing the dictionar"
- << (m_files.size () == 1 ? "y" : "ies")
- << std::endl;
-
- for (std::vector <std::string>::const_iterator it = m_files.begin ();
- it != m_files.end ();
- ++it)
- {
- std::string dictFile = *it;
- std::cout << "Dictionary file: " << dictFile << std::endl;
-
- // Find collisions
-
- // Open the file
- std::ifstream dictStream;
- dictStream.open (dictFile.c_str () );
- if (! dictStream.is_open () )
- {
- std::cerr << "Failed to open dictionary file."
- << "'" << dictFile << "'"
- << std::endl;
- continue;
- }
-
- while (dictStream.good () )
- {
- std::string phrase;
- getline (dictStream, phrase);
- dict.Add (phrase);
- } // while
-
- dictStream.close ();
-
- } // for m_files
-
- } // ReadInto
-
-private:
- std::vector <std::string> m_files; /**< List of word files to use */
-
-}; // class DictFiles
-
-} // namespace Example
-
-} // namespace Hash
-
-} // namespace ns3
-
-
-using namespace ns3;
-using namespace ns3::Hash::Example;
-
-int
-main (int argc, char *argv[])
-{
- std::cout << std::endl;
- std::cout << "Hasher" << std::endl;
-
- bool timing = false;
- DictFiles files;
-
- CommandLine cmd;
- cmd.Usage ("Find hash collisions in the dictionary.");
- cmd.AddValue ("dict", "Dictionary file to hash",
- MakeCallback(&DictFiles::Add,
- &files));
- cmd.AddValue ("time", "Run timing test", timing);
- cmd.Parse (argc, argv);
-
- Dictionary dict;
- dict.Add ( Collider ("FNV1a",
- Hasher ( Create<Hash::Function::Fnv1a> () ),
- Collider::Bits32));
- dict.Add ( Collider ("FNV1a",
- Hasher ( Create<Hash::Function::Fnv1a> () ),
- Collider::Bits64));
-
- dict.Add ( Collider ("Murmur3",
- Hasher ( Create<Hash::Function::Murmur3> () ),
- Collider::Bits32));
- dict.Add ( Collider ("Murmur3",
- Hasher ( Create<Hash::Function::Murmur3> () ),
- Collider::Bits64));
-
- files.ReadInto (dict);
-
- dict.Report ();
-
- if (timing)
- {
- dict.Time ();
- } // if (timing)
-
-
-} // main
-
-
-/* Example Output:
+ * \file
+ * Example usage of ns3::Hash.
+ *
+ * This example reads words from a list of files, creates a dictionary
+ * mapping words to hash values, reports collisions, and measures the
+ * execution time of the hash function implementations.
+ *
+ * See \ref hash
+ *
+ * Example Output:
+ * \verbatim
./waf --run="hasher-example --time \
--dict=/usr/share/dict/web2 \
@@ -562,4 +97,485 @@
Murmur3 (32-bit version) 312094 100 4152139 133.041
Murmur3 (64-bit version) 312094 100 4191464 134.301
+ \endverbatim
+ */
+
+namespace ns3
+{
+
+NS_LOG_COMPONENT_DEFINE ("Hasher");
+
+namespace Hash
+{
+
+/**
+ * \ingroup hash
+ * Namespace for hasher-example.
*/
+namespace Example
+{
+
+/**
+ * Keep track of collisions
+ */
+class Collider {
+
+public:
+ std::string m_name; /**< Name of this hash. */
+ Hasher m_hash; /**< The hash. */
+
+ /** The size of hash function being tested. */
+ enum Bits {
+ Bits32, /**< Use 32-bit hash function. */
+ Bits64 /**< Use 64-bit hash function. */
+ };
+
+ /**
+ * Constructor.
+ *
+ * \param [in] name Hash function name.
+ * \param [in] hash Hash function.
+ * \param [in] bits Which hash length to use.
+ */
+ Collider (const std::string name, Hasher hash, const enum Bits bits)
+ : m_name (name),
+ m_hash (hash),
+ m_bits (bits)
+ { }
+
+ /**
+ * Add a string to the Collider.
+ *
+ * \param [in] phrase The string to add.
+ * \return true If this was a new string.
+ */
+ bool Add (const std::string phrase)
+ {
+ uint64_t h = GetHash (phrase);
+
+ // Check for collisions
+ if (m_dict.count (h) > 0)
+ {
+ // we've seen this hash before, why?
+ if (phrase == m_dict[h])
+ {
+ // duplicate phrase
+ return false;
+ }
+
+ // new phrase generating a real collision
+ // alphabetize
+ if ( m_dict[h] < phrase)
+ {
+ m_coll.push_back (std::make_pair (h, phrase));
+ }
+ else
+ {
+ m_coll.push_back (std::make_pair (h, m_dict[h]));
+ m_dict[h] = phrase;
+ }
+ }
+ else
+ {
+ // Insert new hash
+ m_dict.insert (std::make_pair (h, phrase));
+ }
+ return true;
+ } // Add ()
+
+ /**
+ * \return The hash name, including the length.
+ */
+ std::string GetName () const
+ {
+ std::string name = m_name;
+
+ switch (m_bits)
+ {
+ case Bits32: name += " (32-bit version)"; break;
+ case Bits64: name += " (64-bit version)"; break;
+ default: name += " (unknown!?!)";
+ }
+ return name;
+ }
+
+ /** Print the collisions found. */
+ void Report () const
+ {
+ std::cout << std::endl;
+
+ std::cout << GetName () << ": " << m_coll.size () << " collisions:"
+ << std::endl;
+ for (collision_t::const_iterator it = m_coll.begin ();
+ it != m_coll.end ();
+ ++it)
+ {
+ uint64_t h = it->first;
+
+ std::cout << std::setfill ('0') << std::hex << std::setw(8) << h
+ << std::dec << std::setfill(' ') << " "
+ << std::setw(20) << std::left
+ << m_dict.find (h)->second
+ << it->second
+ << std::right
+ << std::endl;
+ }
+ } // Report ()
+
+
+private:
+
+ /**
+ * Get the appropriate hash value.
+ *
+ * \param [in] phrase The string to hash.
+ * \return The hash value, using the number of bits set in the constructor.
+ */
+ uint64_t GetHash (const std::string phrase)
+ {
+ m_hash.clear ();
+ uint64_t h = 0;
+
+ if (m_bits == Bits32)
+ {
+ h = m_hash.GetHash32 (phrase);
+ }
+ else
+ {
+ h = m_hash.GetHash64 (phrase);
+ }
+ return h;
+ }
+
+ /** Hash function. */
+ enum Bits m_bits;
+
+ /** Hashed dictionary of first instance of each hash. */
+ typedef std::map <uint64_t, std::string> hashdict_t;
+
+ /** The dictionary map, indexed by hash. */
+ hashdict_t m_dict;
+
+ /** Collision map of subsequent instances. */
+ typedef std::vector < std::pair<uint64_t, std::string> > collision_t;
+
+ /** The list of collisions. */
+ collision_t m_coll;
+
+}; // class Collider
+
+
+/**
+ * Word list and hashers to test.
+ */
+class Dictionary {
+public:
+ /** Constructor. */
+ Dictionary ()
+ : m_nphrases (0)
+ {
+ m_words.reserve (320000);
+ }
+
+ /**
+ * Add a Collider containing a hash function.
+ *
+ * \param [in] c The Collider to add.
+ */
+ void Add (Collider c)
+ {
+ m_hashes.push_back (c);
+ }
+
+ /**
+ * Add a string to the dictionary.
+ *
+ * \param [in] phrase The string to add.
+ */
+ void Add (const std::string phrase)
+ {
+ if (phrase.size () == 0)
+ {
+ return ;
+ }
+
+ int newPhrases = 0;
+ for (std::vector <Collider>::iterator it = m_hashes.begin ();
+ it != m_hashes.end ();
+ ++it)
+ {
+ newPhrases += it->Add (phrase);
+ }
+
+ if (newPhrases)
+ {
+ ++m_nphrases;
+ m_words.push_back (phrase);
+ }
+ } // Add ()
+
+ /**
+ * Report the expected number of collisions.
+ *
+ * See, e.g.,
+ * http://www.math.dartmouth.edu/archive/m19w03/public_html/Section6-5.pdf
+ *
+ * \f[
+ * E(collisions) = n - k + k (1 - 1/k)^n
+ * \f]
+ *
+ * where <i>n</i> is the number of entries in the table, and
+ * <i>k</i> is the number of buckets.
+ *
+ * This form is numerically unstable for low collision rates.
+ * Expanding for large \f$ k \f$ we get
+ *
+ * \f{eqnarray*}{
+ * E(c) &=& \frac{1}{k} {n \choose 2}
+ * - \frac{1}{{{k^2}}} {n \choose 3}
+ * + \frac{1}{{{k^3}}} {n \choose 4}
+ * - \ldots \\
+ * &=& \frac{1}{k} {n \choose 2}
+ * \left[ {1 - \frac{{n - 2}}{{3k}}
+ * + \frac{{\left( {n - 2} \right)
+ * \left( {n - 3} \right)}}{{12{k^2}}}
+ * - \ldots } \right] \\
+ * &=& \frac{1}{k} {n \choose 2}
+ * \left\{ {1 - \frac{{n - 2}}{{3k}}
+ * \left[ {1 + \frac{{n - 3}}{{4k}}
+ * - \ldots }
+ * \right]}
+ * \right\}
+ * \f}
+ *
+ * For simplicity, we'll use the first two terms
+ * of the second form.
+ */
+ void ReportExpectedCollisions () const
+ {
+ // Expected number of collisions
+ //
+ // Number of buckets = k = 2^bits
+ long double k32 = 0xFFFFFFFF;
+ long double k64 = 0xFFFFFFFFFFFFFFFFULL;
+
+ long double n = m_nphrases;
+ long double Ec32 = n * (n - 1) / ( 2 * k32) * (1 - (n - 2)/(3 * k32));
+ long double Ec64 = n * (n - 1) / ( 2 * k64) * (1 - (n - 2)/(3 * k64));
+
+ // Output collisions
+ std::cout << "" << std::endl;
+ std::cout << "Number of words or phrases: " << n << std::endl;
+ std::cout << "Expected number of collisions: (32-bit table) " << Ec32
+ << std::endl;
+ std::cout << "Expected number of collisions: (64-bit table) " << Ec64
+ << std::endl;
+ } // ReportExpectedCollisions
+
+
+ /** Print the collisions for each Collider. */
+ void Report () const
+ {
+ ReportExpectedCollisions ();
+
+ for (std::vector <Collider>::const_iterator it = m_hashes.begin ();
+ it != m_hashes.end ();
+ ++it)
+ {
+ it->Report ();
+ }
+ } // Report ()
+
+ /**
+ * Time and report the execution of one hash across the entire Dictionary.
+ *
+ * \param [in] hindex Index of the hash Collider to use.
+ */
+ void TimeOne (const int hindex)
+ {
+ // Hashing speed
+ uint32_t reps = 100;
+ Hasher h = m_hashes[hindex].m_hash;
+ int start = clock ();
+ for (std::vector<std::string>::const_iterator w = m_words.begin ();
+ w != m_words.end();
+ ++w)
+ {
+ for (uint32_t i = 0; i < reps; ++i)
+ {
+ h.clear ().GetHash32 (*w);
+ }
+ }
+ int stop = clock ();
+ double delta = stop - start;
+ double per = 1e9 * delta / (m_nphrases * reps * CLOCKS_PER_SEC);
+
+ std::cout << std::left
+ << std::setw (32) << m_hashes[hindex].GetName ()
+ << std::right
+ << std::setw (10) << m_nphrases
+ << std::setw (10) << reps
+ << std::setw (10) << stop - start
+ << std::setw (12) << per
+ << std::endl;
+
+ } // TimeOne ()
+
+ /** Report the execution time of each hash across the entire Dictionary. */
+ void Time ()
+ {
+ std::cout << "" << std::endl;
+ std::cout << std::left
+ << std::setw (32) << "Hash timing"
+ << std::right
+ << std::setw (10) << "Phrases"
+ << std::setw (10) << "Reps"
+ << std::setw (10) << "Ticks"
+ << std::setw (12) << "ns/hash"
+ << std::endl;
+
+ for (unsigned int i = 0; i < m_hashes.size (); ++i)
+ {
+ TimeOne (i);
+ }
+ } // Time ()
+
+private:
+ unsigned long m_nphrases; /**< Number of strings hashed. */
+ std::vector <Collider> m_hashes; /**< List of hash Colliders. */
+ std::vector <std::string> m_words; /**< List of unique words. */
+
+}; // class Dictionary
+
+
+/**
+ * Source word list files.
+ */
+class DictFiles
+{
+
+public:
+
+ /**
+ * CommandLine callback function to add a file argument to the list.
+ *
+ * \param [in] file The word file to add.
+ * \return true Tf the file is new to the list.
+ */
+ bool Add (const std::string file)
+ {
+ if (std::find (m_files.begin (), m_files.end (), file) == m_files.end ())
+ {
+ m_files.push_back (file);
+ }
+
+ return true;
+ }
+
+ /**
+ * Add phrases from the files into the dict.
+ *
+ * \param [in,out] dict The Dictionary to add words to.
+ */
+ void ReadInto (Dictionary & dict)
+ {
+ if (m_files.size () == 0)
+ {
+ Add ("/usr/share/dict/web2");
+ }
+
+ std::cout << "Hashing the dictionar"
+ << (m_files.size () == 1 ? "y" : "ies")
+ << std::endl;
+
+ for (std::vector <std::string>::const_iterator it = m_files.begin ();
+ it != m_files.end ();
+ ++it)
+ {
+ std::string dictFile = *it;
+ std::cout << "Dictionary file: " << dictFile << std::endl;
+
+ // Find collisions
+
+ // Open the file
+ std::ifstream dictStream;
+ dictStream.open (dictFile.c_str () );
+ if (! dictStream.is_open () )
+ {
+ std::cerr << "Failed to open dictionary file."
+ << "'" << dictFile << "'"
+ << std::endl;
+ continue;
+ }
+
+ while (dictStream.good () )
+ {
+ std::string phrase;
+ getline (dictStream, phrase);
+ dict.Add (phrase);
+ } // while
+
+ dictStream.close ();
+
+ } // for m_files
+
+ } // ReadInto
+
+private:
+ std::vector <std::string> m_files; /**< List of word files to use. */
+
+}; // class DictFiles
+
+} // namespace Example
+
+} // namespace Hash
+
+} // namespace ns3
+
+
+using namespace ns3;
+using namespace ns3::Hash::Example;
+
+int
+main (int argc, char *argv[])
+{
+ std::cout << std::endl;
+ std::cout << "Hasher" << std::endl;
+
+ bool timing = false;
+ DictFiles files;
+
+ CommandLine cmd;
+ cmd.Usage ("Find hash collisions in the dictionary.");
+ cmd.AddValue ("dict", "Dictionary file to hash",
+ MakeCallback(&DictFiles::Add,
+ &files));
+ cmd.AddValue ("time", "Run timing test", timing);
+ cmd.Parse (argc, argv);
+
+ Dictionary dict;
+ dict.Add ( Collider ("FNV1a",
+ Hasher ( Create<Hash::Function::Fnv1a> () ),
+ Collider::Bits32));
+ dict.Add ( Collider ("FNV1a",
+ Hasher ( Create<Hash::Function::Fnv1a> () ),
+ Collider::Bits64));
+
+ dict.Add ( Collider ("Murmur3",
+ Hasher ( Create<Hash::Function::Murmur3> () ),
+ Collider::Bits32));
+ dict.Add ( Collider ("Murmur3",
+ Hasher ( Create<Hash::Function::Murmur3> () ),
+ Collider::Bits64));
+
+ files.ReadInto (dict);
+
+ dict.Report ();
+
+ if (timing)
+ {
+ dict.Time ();
+ } // if (timing)
+
+
+} // main
--- a/src/core/model/hash-function.h Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/model/hash-function.h Mon Nov 17 15:51:36 2014 -0800
@@ -35,7 +35,7 @@
/**
* \ingroup hash
*
- * \brief Hash function implementation base class
+ * \brief Hash function implementation base class.
*/
class Implementation : public SimpleRefCount<Implementation>
{
@@ -43,16 +43,16 @@
/**
* Compute 32-bit hash of a byte buffer
*
- * Call clear () between calls to GetHash32() to reset the
+ * Call clear() between calls to GetHash32() to reset the
* internal state and hash each buffer separately.
*
* If you don't call clear() between calls to GetHash32,
* you can hash successive buffers. The final return value
* will be the cumulative hash across all calls.
*
- * \param [in] buffer pointer to the beginning of the buffer
- * \param [in] size length of the buffer, in bytes
- * \return 32-bit hash of the buffer
+ * \param [in] buffer Pointer to the beginning of the buffer.
+ * \param [in] size Length of the buffer, in bytes.
+ * \return 32-bit hash of the buffer.
*/
virtual uint32_t GetHash32 (const char * buffer, const size_t size) = 0;
/**
@@ -60,28 +60,28 @@
*
* Default implementation returns 32-bit hash, with a warning.
*
- * Call clear () between calls to GetHash64() to reset the
+ * Call clear() between calls to GetHash64() to reset the
* internal state and hash each buffer separately.
*
* If you don't call clear() between calls to GetHash64,
* you can hash successive buffers. The final return value
* will be the cumulative hash across all calls.
*
- * \param [in] buffer pointer to the beginning of the buffer
- * \param [in] size length of the buffer, in bytes
- * \return 64-bit hash of the buffer
+ * \param [in] buffer Pointer to the beginning of the buffer.
+ * \param [in] size Length of the buffer, in bytes.
+ * \return 64-bit hash of the buffer.
*/
virtual uint64_t GetHash64 (const char * buffer, const size_t size);
/**
- * Restore initial state
+ * Restore initial state.
*/
virtual void clear (void) = 0;
/**
- * Constructor
+ * Constructor.
*/
Implementation () { };
/**
- * Destructor
+ * Destructor.
*/
virtual ~Implementation () { };
}; // Hashfunction
@@ -107,18 +107,23 @@
/**
* \ingroup hash
- * Hash functions
+ * Hash functions.
*/
namespace Function {
/**
* \ingroup hash
*
- * \brief Template for Hashfunctions from 32-bit hash functions
+ * \brief Template for Hashfunctions from 32-bit hash functions.
*/
class Hash32 : public Implementation
{
public:
+ /**
+ * Constructor from a 32-bit hash function pointer.
+ *
+ * \param [in] hp Function pointer to a 32-bit hash function.
+ */
Hash32 (Hash32Function_ptr hp) : m_fp (hp) { };
uint32_t GetHash32 (const char * buffer, const size_t size)
{
@@ -126,7 +131,7 @@
}
void clear () { };
private:
- Hash32Function_ptr m_fp;
+ Hash32Function_ptr m_fp; /**< The hash function. */
}; // Hash32
/**
@@ -137,6 +142,11 @@
class Hash64 : public Implementation
{
public:
+ /**
+ * Constructor from a 64-bit hash function pointer.
+ *
+ * \param [in] hp Function pointer to a 64-bit hash function.
+ */
Hash64 (Hash64Function_ptr hp) : m_fp (hp) { };
uint64_t GetHash64 (const char * buffer, const size_t size)
{
@@ -152,7 +162,7 @@
}
void clear () { };
private:
- Hash64Function_ptr m_fp;
+ Hash64Function_ptr m_fp; /**< The hash function. */
}; // Hash64<Hash64Function_ptr>
--- a/src/core/model/hash.h Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/model/hash.h Mon Nov 17 15:51:36 2014 -0800
@@ -36,12 +36,15 @@
* \ingroup core
* \defgroup hash Hash Functions
*
- * \brief Generic Hash function interface
+ * \brief Generic Hash function interface.
+ *
+ * See \ref Hasher for main entry point.
+ * See \ref hash-example.cc for example usage.
*/
/**
* \ingroup hash
*
- * \brief Generic Hash function interface
+ * \brief Generic Hash function interface.
*
* This class provides a generic interface for computing hashes
* of buffers. Various getters return hashes of different lengths.
@@ -59,7 +62,7 @@
* uint32_t hash = Hasher.GetHash32 (data);
* \endcode
*
- * The available implementations are documented in group hash.
+ * The available implementations are documented in \ref hash.
* The default implementation is Murmur3. FNV1a is also available.
*
* In addition to this class interface, global functions are
@@ -79,13 +82,13 @@
{
public:
/**
- * Constructor using the default implementation
+ * Constructor using the default implementation.
*/
Hasher ();
/**
- * Constructor using the supplied implementation
+ * Constructor using the supplied implementation.
*
- * \param [in] hp Ptr<Hash::Implementation> to the desired implementation
+ * \param [in] hp Ptr<Hash::Implementation> to the desired implementation.
*/
Hasher (Ptr<Hash::Implementation> hp);
/**
@@ -98,13 +101,13 @@
* you can hash successive buffers. The final return value
* will be the cumulative hash across all calls.
*
- * \param [in] buffer pointer to the beginning of the buffer
- * \param [in] size length of the buffer, in bytes
- * \return 32-bit hash of the buffer
+ * \param [in] buffer Pointer to the beginning of the buffer.
+ * \param [in] size Length of the buffer, in bytes.
+ * \return 32-bit hash of the buffer..
*/
uint32_t GetHash32 (const char * buffer, const size_t size);
/**
- * Compute 64-bit hash of a byte buffer
+ * Compute 64-bit hash of a byte buffer.
*
* Call clear () between calls to GetHash64() to reset the
* internal state and hash each buffer separately.
@@ -113,14 +116,14 @@
* you can hash successive buffers. The final return value
* will be the cumulative hash across all calls.
*
- * \param [in] buffer pointer to the beginning of the buffer
- * \param [in] size length of the buffer, in bytes
- * \return 64-bit hash of the buffer
+ * \param [in] buffer Pointer to the beginning of the buffer.
+ * \param [in] size Length of the buffer, in bytes.
+ * \return 64-bit hash of the buffer.
*/
uint64_t GetHash64 (const char * buffer, const size_t size);
/**
- * Compute 32-bit hash of a string
+ * Compute 32-bit hash of a string.
*
* Call clear () between calls to GetHash32() to reset the
* internal state and hash each string separately.
@@ -129,12 +132,12 @@
* you can hash successive strings. The final return value
* will be the cumulative hash across all calls.
*
- * \param [in] s string to hash
- * \return 32-bit hash of the string
+ * \param [in] s String to hash.
+ * \return 32-bit hash of the string.
*/
uint32_t GetHash32 (const std::string s);
/**
- * Compute 64-bit hash of a string
+ * Compute 64-bit hash of a string.
*
* Call clear () between calls to GetHash64() to reset the
* internal state and hash each string separately.
@@ -143,19 +146,28 @@
* you can hash successive strings. The final return value
* will be the cumulative hash across all calls.
*
- * \param [in] s string to hash
- * \return 64-bit hash of the string
+ * \param [in] s String to hash.
+ * \return 64-bit hash of the string.
*/
uint64_t GetHash64 (const std::string s);
/**
- * Restore initial state
+ * Restore initial state.
+ *
+ * Returning this Hasher allows code like this:
+ *
+ * \code
+ * Hasher h;
+ * h.GetHash32 (...);
+ * ...
+ * h.clear ().GetHash64 (...);
+ * \endcode
*
* \return this
*/
Hasher & clear (void);
private:
- Ptr<Hash::Implementation> m_impl; /** Hash implementation */
+ Ptr<Hash::Implementation> m_impl; /**< Hash implementation. */
}; // Hasher
@@ -166,40 +178,40 @@
/**
* \ingroup hash
*
- * Compute 32-bit hash of a byte buffer, using the default hash function
+ * Compute 32-bit hash of a byte buffer, using the default hash function.
*
- * \param [in] buffer pointer to the beginning of the buffer
- * \param [in] size length of the buffer, in bytes
- * \return 32-bit hash of the buffer
+ * \param [in] buffer Pointer to the beginning of the buffer.
+ * \param [in] size Length of the buffer, in bytes.
+ * \return 32-bit hash of the buffer.
*/
uint32_t Hash32 (const char * buffer, const size_t size);
/**
* \ingroup hash
*
- * Compute 64-bit hash of a byte buffer, using the default hash function
+ * Compute 64-bit hash of a byte buffer, using the default hash function.
*
- * \param [in] buffer pointer to the beginning of the buffer
- * \param [in] size length of the buffer, in bytes
- * \return 64-bit hash of the buffer
+ * \param [in] buffer Pointer to the beginning of the buffer.
+ * \param [in] size Length of the buffer, in bytes.
+ * \return 64-bit hash of the buffer.
*/
uint64_t Hash64 (const char * buffer, const size_t size);
/**
* \ingroup hash
*
- * Compute 32-bit hash of a string, using the default hash function
+ * Compute 32-bit hash of a string, using the default hash function.
*
- * \param [in] s string to hash
- * \return 32-bit hash of the string
+ * \param [in] s String to hash.
+ * \return 32-bit hash of the string.
*/
uint32_t Hash32 (const std::string s);
/**
* \ingroup hash
*
- * Compute 64-bit hash of a string, using the default hash function
+ * Compute 64-bit hash of a string, using the default hash function.
*
- * \param [in] s string to hash
- * \return 64-bit hash of the string
+ * \param [in] s String to hash.
+ * \return 64-bit hash of the string.
*/
uint64_t Hash64 (const std::string s);
--- a/src/core/model/int64x64-128.cc Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/model/int64x64-128.cc Mon Nov 17 15:51:36 2014 -0800
@@ -29,6 +29,17 @@
// of causing recursions leading to stack overflow
NS_LOG_COMPONENT_DEFINE ("int64x64-128");
+/**
+ * \ingroup highprec
+ * Compute the sign of the result of multiplying or dividing
+ * Q64.64 fixed precision operands.
+ *
+ * \param [in] sa The signed value of the first operand.
+ * \param [in] sb The signed value of the second operand.
+ * \param [out] ua The unsigned magnitude of the first operand.
+ * \param [out] ub The unsigned magnitude of the second operand.
+ * \returns True if the result will be negative.
+ */
static inline
bool
output_sign (const int128_t sa,
--- a/src/core/model/int64x64-128.h Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/model/int64x64-128.h Mon Nov 17 15:51:36 2014 -0800
@@ -38,19 +38,20 @@
*/
class int64x64_t
{
- /// uint128_t high bit (sign bit)
+ /// uint128_t high bit (sign bit).
static const uint128_t HP128_MASK_HI_BIT = (((int128_t)1)<<127);
- /// Mask for fraction part
+ /// Mask for fraction part.
static const uint64_t HP_MASK_LO = 0xffffffffffffffffULL;
- /// Mask for sign + integer part
+ /// Mask for sign + integer part.
static const uint64_t HP_MASK_HI = ~HP_MASK_LO;
/**
- * Floating point value of HP_MASK_LO + 1
+ * Floating point value of HP_MASK_LO + 1.
* We really want:
* \code
* static const long double HP_MAX_64 = std:pow (2.0L, 64);
* \endcode
- * but we can't call functions in const definitions,
+ * but we can't call functions in const definitions.
+ *
* We could make this a static and initialize in int64x64-128.cc or
* int64x64.cc, but this requires handling static initialization order
* when most of the implementation is inline. Instead, we resort to
@@ -67,22 +68,22 @@
* we expose the underlying implementation type here.
*/
enum impl_type {
- int128_impl, //!< Native int128_t implementation.
- cairo_impl, //!< cairo wideint implementation
- ld_impl, //!< long double implementation
+ int128_impl, //!< Native \c int128_t implementation.
+ cairo_impl, //!< Cairo wideint implementation.
+ ld_impl, //!< `long double` implementation.
};
/// Type tag for this implementation.
static const enum impl_type implementation = int128_impl;
- /// Default constructor
+ /// Default constructor.
inline int64x64_t ()
: _v (0) {}
/**@{*/
/**
* Construct from a floating point value.
*
- * \param [in] value floating value to represent
+ * \param [in] value Floating value to represent.
*/
inline int64x64_t (const double value)
{
@@ -123,7 +124,7 @@
/**
* Construct from an integral type.
*
- * \param [in] v integer value to represent
+ * \param [in] v Integer value to represent.
*/
inline int64x64_t (const int v)
: _v (v)
@@ -179,6 +180,7 @@
* Assignment.
*
* \param [in] o Value to assign to this int64x64_t.
+ * \returns This int64x64_t.
*/
inline int64x64_t & operator = (const int64x64_t & o)
{
@@ -229,7 +231,7 @@
*
* \param [in] o The inverse operand.
*
- * \see Invert
+ * \see Invert()
*/
void MulByInvert (const int64x64_t & o);
@@ -249,6 +251,7 @@
static int64x64_t Invert (const uint64_t v);
private:
+
friend bool operator == (const int64x64_t & lhs, const int64x64_t & rhs);
friend bool operator < (const int64x64_t & lhs, const int64x64_t & rhs);
@@ -304,7 +307,7 @@
*
* \param [in] a Numerator.
* \param [in] b Denominator.
- * \return The Q64.64 representation of `a / b`
+ * \return The Q64.64 representation of `a / b`.
*/
static uint128_t Udiv (const uint128_t a, const uint128_t b);
/**
@@ -312,16 +315,16 @@
*
* \param [in] a The numerator, a Q64.64 value.
* \param [in] b The inverse of the denominator, a Q0.128 value
- * \return The product `a * b`, representing the ration `a / b^-1`
+ * \return The product `a * b`, representing the ration `a / b^-1`.
*
- * \see Invert
+ * \see Invert()
*/
static uint128_t UmulByInvert (const uint128_t a, const uint128_t b);
/**
* Construct from an integral type.
*
- * \param [in] v integer value to represent
+ * \param [in] v Integer value to represent.
*/
inline int64x64_t (const int128_t v)
: _v (v) {}
@@ -341,7 +344,7 @@
}
/**
* \ingroup highprec
- * Less than operator
+ * Less than operator.
*/
inline bool operator < (const int64x64_t & lhs, const int64x64_t & rhs)
{
@@ -349,7 +352,7 @@
}
/**
* \ingroup highprec
- * Greater operator
+ * Greater operator.
*/
inline bool operator > (const int64x64_t & lhs, const int64x64_t & rhs)
{
@@ -358,7 +361,7 @@
/**
* \ingroup highprec
- * Compound addition operator
+ * Compound addition operator.
*/
inline int64x64_t & operator += (int64x64_t & lhs, const int64x64_t & rhs)
{
@@ -367,7 +370,7 @@
}
/**
* \ingroup highprec
- * Compound subtraction operator
+ * Compound subtraction operator.
*/
inline int64x64_t & operator -= (int64x64_t & lhs, const int64x64_t & rhs)
{
@@ -376,7 +379,7 @@
}
/**
* \ingroup highprec
- * Compound multiplication operator
+ * Compound multiplication operator.
*/
inline int64x64_t & operator *= (int64x64_t & lhs, const int64x64_t & rhs)
{
@@ -385,7 +388,7 @@
}
/**
* \ingroup highprec
- * Compound division operator
+ * Compound division operator.
*/
inline int64x64_t & operator /= (int64x64_t & lhs, const int64x64_t & rhs)
{
@@ -395,7 +398,7 @@
/**
* \ingroup highprec
- * Unary plus operator
+ * Unary plus operator.
*/
inline int64x64_t operator + (const int64x64_t & lhs)
{
@@ -403,7 +406,7 @@
}
/**
* \ingroup highprec
- * Unary negation operator (change sign operator)
+ * Unary negation operator (change sign operator).
*/
inline int64x64_t operator - (const int64x64_t & lhs)
{
@@ -411,7 +414,7 @@
}
/**
* \ingroup highprec
- * Logical not operator
+ * Logical not operator.
*/
inline int64x64_t operator ! (const int64x64_t & lhs)
{
--- a/src/core/model/int64x64-cairo.cc Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/model/int64x64-cairo.cc Mon Nov 17 15:51:36 2014 -0800
@@ -37,6 +37,17 @@
// of causing recursions leading to stack overflow
NS_LOG_COMPONENT_DEFINE ("int64x64-cairo");
+/**
+ * \ingroup highprec
+ * Compute the sign of the result of multiplying or dividing
+ * Q64.64 fixed precision operands.
+ *
+ * \param [in] sa The signed value of the first operand.
+ * \param [in] sb The signed value of the second operand.
+ * \param [out] ua The unsigned magnitude of the first operand.
+ * \param [out] ub The unsigned magnitude of the second operand.
+ * \returns True if the result will be negative.
+ */
static inline
bool
output_sign (const cairo_int128_t sa,
--- a/src/core/model/int64x64.cc Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/model/int64x64.cc Mon Nov 17 15:51:36 2014 -0800
@@ -154,6 +154,15 @@
return os;
}
+/**
+ * \ingroup highprec
+ * Read the integer portion of a number from a string containing
+ * just the integral digits (no decimal point or fractional part).
+ *
+ * \param [in] str The string representation of the integral part
+ * of a number, with no fractional part or decimal point.
+ * \returns The integer.
+ */
static uint64_t ReadHiDigits (std::string str)
{
const char *buf = str.c_str ();
@@ -167,6 +176,16 @@
return retval;
}
+/**
+ * \ingroup highprec
+ * Read the fractional part of a number from a string containing
+ * just the decimal digits of the fractional part (no integral part
+ * or decimal point).
+ *
+ * \param [in] str The string representation of the fractional part
+ * of a number, without integral part or decimal point.
+ * \returns The decimal portion of the input number.
+ */
static uint64_t ReadLoDigits (std::string str)
{
int64x64_t low;
--- a/src/core/model/int64x64.h Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/model/int64x64.h Mon Nov 17 15:51:36 2014 -0800
@@ -43,13 +43,6 @@
* \defgroup highprec High Precision Q64.64
*
* Functions and class for high precision Q64.64 fixed point arithmetic.
- */
-
-/**
- * \ingroup highprec
- * \class int64x64_t
- *
- * High precision numerical type, implementing Q64.64 fixed precision.
*
* A Q64.64 fixed precision number consists of:
*
@@ -70,39 +63,12 @@
* Comparison | `==`, `!=`, `<`, `<=`, `>`, `>=`
* Unary | `+`, `-`, `!`
*/
-
-
-/**
- * \ingroup core
- * \defgroup highprec High Precision Q64.64
- *
- * Functions and class for high precision Q64.64 fixed point arithmetic.
- */
/**
* \ingroup highprec
* \class int64x64_t
*
* High precision numerical type, implementing Q64.64 fixed precision.
- *
- * A Q64.64 fixed precision number consists of:
- *
- * Bits | Function
- * ---- | --------
- * 1 | Sign bit
- * 63 | Integer portion
- * 64 | Fractional portion
- *
- * The `high` word consists of the sign bit and integer value;
- * the `low` word is the fractional part, unscaled.
- *
- * All standard arithmetic operations are supported:
- *
- * Category | Operators
- * ----------- | ---------
- * Computation | `+`, `+=`, `-`, `-=`, `*`, `*=`, `/`, `/=`
- * Comparison | `==`, `!=`, `<`, `<=`, `>`, `>=`
- * Unary | `+`, `-`, `!`
*/
@@ -160,7 +126,7 @@
}
/**
* \ingroup highprec
- * Less or equal operator
+ * Less or equal operator.
*/
inline bool operator <= (const int64x64_t & lhs, const int64x64_t & rhs)
{
@@ -168,7 +134,7 @@
}
/**
* \ingroup highprec
- * Greater or equal operator
+ * Greater or equal operator.
*/
inline bool operator >= (const int64x64_t & lhs, const int64x64_t & rhs)
{
@@ -176,7 +142,7 @@
}
/**
* \ingroup highprec
- * Output streamer for int64x64_t
+ * Output streamer for int64x64_t.
*
* Values are printed with the following format flags
* (independent of the the stream flags):
@@ -187,17 +153,27 @@
* `precision` decimal places are printed. If `floatfield` is not set,
* all digits of the fractional part are printed, up to the
* representation limit of 20 digits; trailing zeros are omitted.
+ *
+ * \param [in] os The output stream.
+ * \param [in] value The numerical value to print.
+ * \returns The stream.
*/
-std::ostream &operator << (std::ostream &os, const int64x64_t &val);
+std::ostream &operator << (std::ostream &os, const int64x64_t &value);
/**
* \ingroup highprec
- * Input streamer for int64x64_t
+ * Input streamer for int64x64_t.
+ *
+ * \param [in] is The input stream.
+ * \param [out] value The numerical value to set.
+ * \returns The stream.
*/
-std::istream &operator >> (std::istream &is, int64x64_t &val);
+std::istream &operator >> (std::istream &is, int64x64_t &value);
/**
* \ingroup highprec
* Absolute value.
+ * \param value The value to operate on.
+ * \return The absolute value of \p value.
*/
inline int64x64_t Abs (const int64x64_t &value)
{
@@ -208,6 +184,8 @@
* \ingroup highprec
* Minimum.
*
+ * \param [in] a The first value.
+ * \param [in] b The second value.
* \return The smaller of the arguments.
*/
inline int64x64_t Min (const int64x64_t &a, const int64x64_t &b)
@@ -218,6 +196,8 @@
* \ingroup highprec
* Maximum.
*
+ * \param [in] a The first value.
+ * \param [in] b The second value.
* \return The larger of the arguments.
*/
inline int64x64_t Max (const int64x64_t &a, const int64x64_t &b)
--- a/src/core/test/int64x64-test-suite.cc Mon Nov 17 15:49:59 2014 -0800
+++ b/src/core/test/int64x64-test-suite.cc Mon Nov 17 15:51:36 2014 -0800
@@ -54,9 +54,18 @@
*/
+/**
+ * Pretty printer for test cases.
+ */
class Printer
{
public:
+ /**
+ * Construct from high and low words of Q64.64 representation.
+ *
+ * \param [in] high The integer portion.
+ * \param [in] low The fractional portion.
+ */
Printer (const int64_t high, const uint64_t low)
: m_haveInt (false),
m_value (0),
@@ -64,6 +73,11 @@
m_low (low)
{ }
+ /**
+ * Construct from an \c int64x64_t Q64.64 value.
+ *
+ * \param [in] value The value.
+ */
Printer (const int64x64_t value)
: m_haveInt (true),
m_value (value),
@@ -72,12 +86,19 @@
{ }
private:
+ /**
+ * Output streamer, the main reason for this class.
+ *
+ * \param [in] os The stream.
+ * \param [in] p The value to print.
+ * \returns The stream.
+ */
friend std::ostream & operator << (std::ostream & os, const Printer & p);
- bool m_haveInt;
- int64x64_t m_value;
- int64_t m_high;
- uint64_t m_low;
+ bool m_haveInt; /**< Do we have a full int64x64_t value? */
+ int64x64_t m_value; /**< The int64x64_t value. */
+ int64_t m_high; /**< The high (integer) word. */
+ uint64_t m_low; /**< The low (fractional) word. */
};
std::ostream & operator << (std::ostream & os, const Printer & p)
@@ -96,7 +117,7 @@
return os;
}
-
+
class Int64x64HiLoTestCase : public TestCase
{
public: