OLD | NEW |
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ | 1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
2 /* | 2 /* |
3 * Copyright (c) 2012 Lawrence Livermore National Laboratory | 3 * Copyright (c) 2012 Lawrence Livermore National Laboratory |
4 * | 4 * |
5 * This program is free software; you can redistribute it and/or modify | 5 * This program is free software; you can redistribute it and/or modify |
6 * it under the terms of the GNU General Public License version 2 as | 6 * it under the terms of the GNU General Public License version 2 as |
7 * published by the Free Software Foundation; | 7 * published by the Free Software Foundation; |
8 * | 8 * |
9 * This program is distributed in the hope that it will be useful, | 9 * This program is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
12 * GNU General Public License for more details. | 12 * GNU General Public License for more details. |
13 * | 13 * |
14 * You should have received a copy of the GNU General Public License | 14 * You should have received a copy of the GNU General Public License |
15 * along with this program; if not, write to the Free Software | 15 * along with this program; if not, write to the Free Software |
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | 16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
17 * | 17 * |
18 * Author: Peter D. Barnes, Jr. <pdbarnes@llnl.gov> | 18 * Author: Peter D. Barnes, Jr. <pdbarnes@llnl.gov> |
19 */ | 19 */ |
20 | 20 |
21 #include <iomanip> | 21 #include <iomanip> |
22 #include <string> | 22 #include <string> |
23 | 23 |
24 #include "ns3/test.h" | 24 #include "ns3/test.h" |
25 #include "ns3/hash.h" | 25 #include "ns3/hash.h" |
26 | 26 |
27 namespace ns3 { | 27 namespace ns3 { |
28 | 28 |
| 29 class HashTestCase : public TestCase |
| 30 { |
| 31 public: |
| 32 HashTestCase (const std::string name); |
| 33 virtual ~HashTestCase (); |
| 34 protected: |
| 35 void Check ( const std::string hashName, const uint32_t hash); |
| 36 void Check ( const std::string hashName, const uint64_t hash); |
| 37 std::string key; |
| 38 uint32_t hash32Reference; |
| 39 uint64_t hash64Reference; |
| 40 private: |
| 41 void Check ( const std::string hashName, const int bits, const uint64_t hash); |
| 42 virtual void DoRun (void); |
| 43 }; // class HashTestCase |
| 44 |
| 45 HashTestCase::HashTestCase (const std:: string name) |
| 46 : TestCase (name), |
| 47 key ("The quick brown fox jumped over the lazy dogs.") |
| 48 { |
| 49 } |
| 50 |
| 51 HashTestCase::~HashTestCase () |
| 52 { |
| 53 } |
| 54 |
| 55 void |
| 56 HashTestCase::Check ( const std::string hashName, const uint32_t hash) |
| 57 { |
| 58 Check (hashName, 32, hash); |
| 59 } |
| 60 |
| 61 void |
| 62 HashTestCase::Check ( const std::string hashName, const uint64_t hash) |
| 63 { |
| 64 Check (hashName, 64, hash); |
| 65 } |
| 66 |
| 67 void |
| 68 HashTestCase::Check ( std::string hashName, int bits, uint64_t hash) |
| 69 { |
| 70 int w; |
| 71 std::string type; |
| 72 uint64_t hashRef; |
| 73 |
| 74 if (bits == 32) |
| 75 { |
| 76 w = 8; |
| 77 type = "Hash32"; |
| 78 hashRef = hash32Reference; |
| 79 } |
| 80 else |
| 81 { |
| 82 w = 16; |
| 83 type = "Hash64"; |
| 84 hashRef = hash64Reference; |
| 85 } |
| 86 |
| 87 std::cout << GetName () << "checking " |
| 88 << hashName << " " |
| 89 << bits << "-bit result..."; |
| 90 NS_TEST_EXPECT_MSG_EQ (hash, hashRef, |
| 91 hashName << " " << type |
| 92 << " produced " << std::hex << std::setw (w) << hash |
| 93 << ", expected " << std::hex << std::setw (w) << hashRe
f |
| 94 << std::dec |
| 95 ); |
| 96 std::cout << std::hex << std::setw (w) << hash << ", ok" |
| 97 << std::dec << std::endl; |
| 98 } |
| 99 |
| 100 void |
| 101 HashTestCase::DoRun (void) |
| 102 { |
| 103 } |
| 104 |
29 | 105 |
30 //---------------------------- | 106 //---------------------------- |
31 // | 107 // |
32 // Test default hash on fixed string | 108 // Test default hash on fixed string |
33 | 109 |
34 class HashFoxTestCase : public TestCase | 110 class DefaultHashTestCase : public HashTestCase |
35 { | 111 { |
36 public: | 112 public: |
37 HashFoxTestCase (); | 113 DefaultHashTestCase (); |
38 virtual ~HashFoxTestCase (); | 114 virtual ~DefaultHashTestCase (); |
39 private: | 115 private: |
40 virtual void DoRun (void); | 116 virtual void DoRun (void); |
41 }; | 117 }; |
42 | 118 |
43 HashFoxTestCase::HashFoxTestCase () | 119 DefaultHashTestCase::DefaultHashTestCase () |
44 : TestCase ("Check default Hash on a known string") | 120 : HashTestCase ("DefaultHash: ") |
45 { | 121 { |
46 } | 122 } |
47 | 123 |
48 HashFoxTestCase::~HashFoxTestCase () | 124 DefaultHashTestCase::~DefaultHashTestCase () |
49 { | 125 { |
50 } | 126 } |
51 | 127 |
52 void | 128 void |
53 HashFoxTestCase::DoRun (void) | 129 DefaultHashTestCase::DoRun (void) |
54 { | 130 { |
55 std::string key("The quick brown fox."); | 131 std::cout << GetName () << "checking with key: \"" |
| 132 << key << "\"" << std::endl; |
56 | 133 |
57 uint32_t h32r = 0xd138bc62; // murmur3(key) | 134 hash32Reference = 0x463d70e2; // murmur3(key) |
58 uint32_t h32 = Hash32 (key); | 135 Check ( "default", Hash32 (key)); |
59 NS_TEST_ASSERT_MSG_EQ (h32, h32r, | |
60 "Hash32 produced " << std::hex << std::setw ( 8) << h32 | |
61 << ", expected " << std::hex << std::setw ( 8) << h32
r | |
62 ); | |
63 | 136 |
64 uint64_t h64r = 0xfc30fb5d90d6e3a9; | 137 hash64Reference = 0xa750412079d53e04; |
65 uint64_t h64 = Hash64 (key); | 138 Check ( "default", Hash64 (key)); |
66 NS_TEST_ASSERT_MSG_EQ (h64, h64r, | |
67 "Hash64 produced " << std::hex << std::setw (16) << h64 | |
68 << ", expected " << std::hex << std::setw (16) << h64
r | |
69 ); | |
70 } | 139 } |
71 | 140 |
72 //---------------------------- | 141 //---------------------------- |
73 // | 142 // |
74 // Test FNV hash on fixed string | 143 // Test FNV hash on fixed string |
75 | 144 |
76 class HashFnv1aTestCase : public TestCase | 145 class Fnv1aTestCase : public HashTestCase |
77 { | 146 { |
78 public: | 147 public: |
79 HashFnv1aTestCase (); | 148 Fnv1aTestCase (); |
80 virtual ~HashFnv1aTestCase (); | 149 virtual ~Fnv1aTestCase (); |
81 private: | 150 private: |
82 virtual void DoRun (void); | 151 virtual void DoRun (void); |
83 }; | 152 }; |
84 | 153 |
85 HashFnv1aTestCase::HashFnv1aTestCase () | 154 Fnv1aTestCase::Fnv1aTestCase () |
86 : TestCase ("Check Fnv1a Hash on a known string") | 155 : HashTestCase ("Fnv1a: ") |
87 { | 156 { |
88 } | 157 } |
89 | 158 |
90 HashFnv1aTestCase::~HashFnv1aTestCase () | 159 Fnv1aTestCase::~Fnv1aTestCase () |
91 { | 160 { |
92 } | 161 } |
93 | 162 |
94 void | 163 void |
95 HashFnv1aTestCase::DoRun (void) | 164 Fnv1aTestCase::DoRun (void) |
96 { | 165 { |
97 std::string key("The quick brown fnv1a."); | |
98 Hasher hasher = Hasher ( Create<Hash::Function::Fnv1a> () ); | 166 Hasher hasher = Hasher ( Create<Hash::Function::Fnv1a> () ); |
| 167 hash32Reference = 0xa3fc0d6d; // Fnv1a(key) |
| 168 Check ("FNV1a", hasher.clear ().GetHash32 (key)); |
99 | 169 |
100 uint32_t h32r = 0x5735855b; // Fnv1a(key) | 170 hash64Reference = 0x88f6cdbe0a31098d; |
101 uint32_t h32 = hasher.clear ().GetHash32 (key); | 171 Check ( "FNV1a", hasher.clear ().GetHash64 (key)); |
102 NS_TEST_ASSERT_MSG_EQ (h32, h32r, | |
103 "Hash32 produced " << std::hex << std::setw ( 8) << h32 | |
104 << ", expected " << std::hex << std::setw ( 8) << h32
r | |
105 ); | |
106 | |
107 uint64_t h64r = 0x6fb0aea4ad83c27b; | |
108 uint64_t h64 = hasher.clear ().GetHash64 (key); | |
109 NS_TEST_ASSERT_MSG_EQ (h64, h64r, | |
110 "Hash64 produced " << std::hex << std::setw (16) << h64 | |
111 << ", expected " << std::hex << std::setw (16) << h64
r | |
112 ); | |
113 } | 172 } |
114 | 173 |
115 | 174 |
116 //---------------------------- | 175 //---------------------------- |
117 // | 176 // |
118 // Test Murmur3 hash on fixed string | 177 // Test Murmur3 hash on fixed string |
119 | 178 |
120 class HashMurmur3TestCase : public TestCase | 179 class Murmur3TestCase : public HashTestCase |
121 { | 180 { |
122 public: | 181 public: |
123 HashMurmur3TestCase (); | 182 Murmur3TestCase (); |
124 virtual ~HashMurmur3TestCase (); | 183 virtual ~Murmur3TestCase (); |
125 private: | 184 private: |
126 virtual void DoRun (void); | 185 virtual void DoRun (void); |
127 }; | 186 }; |
128 | 187 |
129 HashMurmur3TestCase::HashMurmur3TestCase () | 188 Murmur3TestCase::Murmur3TestCase () |
130 : TestCase ("Check Murmur3 Hash on a known string") | 189 : HashTestCase ("Murmur3: ") |
131 { | 190 { |
132 } | 191 } |
133 | 192 |
134 HashMurmur3TestCase::~HashMurmur3TestCase () | 193 Murmur3TestCase::~Murmur3TestCase () |
135 { | 194 { |
136 } | 195 } |
137 | 196 |
138 void | 197 void |
139 HashMurmur3TestCase::DoRun (void) | 198 Murmur3TestCase::DoRun (void) |
140 { | 199 { |
141 std::string key("The quick brown murmur3."); | |
142 Hasher hasher = Hasher ( Create<Hash::Function::Murmur3> () ); | 200 Hasher hasher = Hasher ( Create<Hash::Function::Murmur3> () ); |
| 201 hash32Reference = 0x463d70e2; // Murmur3(key) |
| 202 Check ( "murmur3", hasher.clear ().GetHash32 (key)); |
143 | 203 |
144 uint32_t h32r = 0xe8a2d100; // Murmur3(key) | 204 hash64Reference = 0xa750412079d53e04; |
145 uint32_t h32 = hasher.clear ().GetHash32 (key); | 205 Check ( "murmur3", hasher.clear ().GetHash64 (key)); |
146 NS_TEST_ASSERT_MSG_EQ (h32, h32r, | |
147 "Hash32 produced " << std::hex << std::setw ( 8) << h32 | |
148 << ", expected " << std::hex << std::setw ( 8) << h32
r | |
149 ); | |
150 | |
151 uint64_t h64r = 0x95373d091a691071; | |
152 uint64_t h64 = hasher.clear ().GetHash64 (key); | |
153 NS_TEST_ASSERT_MSG_EQ (h64, h64r, | |
154 "Hash64 produced " << std::hex << std::setw (16) << h64 | |
155 << ", expected " << std::hex << std::setw (16) << h64
r | |
156 ); | |
157 } | 206 } |
158 | 207 |
159 | 208 |
160 //---------------------------- | 209 //---------------------------- |
161 // | 210 // |
| 211 // Test Hash32Function_ptr/Hash64Function_ptr |
| 212 // |
| 213 // Simple hash function based on the GNU sum program |
| 214 // 16-bit checksum algorithm. See |
| 215 // http://svnweb.freebsd.org/base/stable/9/usr.bin/cksum/sum1.c?view=markup |
| 216 // |
| 217 uint16_t |
| 218 gnu_sum (const char * buffer, const size_t size) |
| 219 { |
| 220 const char * p = buffer; |
| 221 const char * const pend = p + size; |
| 222 |
| 223 uint16_t checksum = 0; /* The checksum mod 2^16. */ |
| 224 |
| 225 while (p != pend) |
| 226 { |
| 227 checksum = (checksum >> 1) + ((checksum & 1) << 15); // barrel shift |
| 228 checksum += *p++; |
| 229 } |
| 230 return checksum; |
| 231 } |
| 232 |
| 233 // Hash32FunctionPtr |
| 234 uint32_t |
| 235 gnu_sum32 (const char * buffer, const size_t size) |
| 236 { |
| 237 uint32_t h = gnu_sum (buffer, size); |
| 238 return (uint32_t)( (h << 16) + h); |
| 239 } |
| 240 |
| 241 // Hash64FunctionPtr |
| 242 uint64_t |
| 243 gnu_sum64 (const char * buffer, const size_t size) |
| 244 { |
| 245 uint64_t h = gnu_sum32 (buffer, size); |
| 246 return (uint64_t)( (h << 32) + h); |
| 247 } |
| 248 |
| 249 class Hash32FunctionPtrTestCase : public HashTestCase |
| 250 { |
| 251 public: |
| 252 Hash32FunctionPtrTestCase (); |
| 253 virtual ~Hash32FunctionPtrTestCase (); |
| 254 private: |
| 255 virtual void DoRun (void); |
| 256 }; |
| 257 |
| 258 Hash32FunctionPtrTestCase::Hash32FunctionPtrTestCase () |
| 259 : HashTestCase ("Hash32FunctionPtr: ") |
| 260 { |
| 261 } |
| 262 |
| 263 Hash32FunctionPtrTestCase::~Hash32FunctionPtrTestCase () |
| 264 { |
| 265 } |
| 266 |
| 267 void |
| 268 Hash32FunctionPtrTestCase::DoRun (void) |
| 269 { |
| 270 Hasher hasher = Hasher ( Create<Hash::Function::Hash32> (&gnu_sum32) ); |
| 271 hash32Reference = 0x41264126; // Hash32FunctionPtr(key) |
| 272 Check ( "gnu_sum32", hasher.clear ().GetHash32 (key)); |
| 273 } |
| 274 |
| 275 class Hash64FunctionPtrTestCase : public HashTestCase |
| 276 { |
| 277 public: |
| 278 Hash64FunctionPtrTestCase (); |
| 279 virtual ~Hash64FunctionPtrTestCase (); |
| 280 private: |
| 281 virtual void DoRun (void); |
| 282 }; |
| 283 |
| 284 Hash64FunctionPtrTestCase::Hash64FunctionPtrTestCase () |
| 285 : HashTestCase ("Hash64FunctionPtr: ") |
| 286 { |
| 287 } |
| 288 |
| 289 Hash64FunctionPtrTestCase::~Hash64FunctionPtrTestCase () |
| 290 { |
| 291 } |
| 292 |
| 293 void |
| 294 Hash64FunctionPtrTestCase::DoRun (void) |
| 295 { |
| 296 Hasher hasher = Hasher ( Create<Hash::Function::Hash64> (&gnu_sum64) ); |
| 297 hash64Reference = 0x4126412641264126; // Hash64FunctionPtr(key) |
| 298 Check ( "gnu_sum64", hasher.clear ().GetHash64 (key)); |
| 299 } |
| 300 |
| 301 class IncrementalTestCase : public HashTestCase |
| 302 { |
| 303 public: |
| 304 IncrementalTestCase (); |
| 305 virtual ~IncrementalTestCase (); |
| 306 private: |
| 307 virtual void DoRun (void); |
| 308 void DoHash (const std::string name, Hasher hasher); |
| 309 // Test strings |
| 310 std::string key1; |
| 311 std::string key2; |
| 312 std::string key12; |
| 313 }; |
| 314 |
| 315 IncrementalTestCase::IncrementalTestCase () |
| 316 : HashTestCase ("Incremental: ") |
| 317 { |
| 318 } |
| 319 |
| 320 IncrementalTestCase::~IncrementalTestCase () |
| 321 { |
| 322 } |
| 323 |
| 324 void |
| 325 IncrementalTestCase::DoHash (const std::string name, Hasher hasher) |
| 326 { |
| 327 hash32Reference = hasher.clear ().GetHash32 (key12); |
| 328 hasher.clear ().GetHash32 (key1); |
| 329 Check ( name, hasher.GetHash32 (key2)); |
| 330 |
| 331 hash64Reference = hasher.clear ().GetHash64 (key12); |
| 332 hasher.clear ().GetHash64 (key1); |
| 333 Check ( name, hasher.GetHash64 (key2)); |
| 334 } |
| 335 |
| 336 void |
| 337 IncrementalTestCase::DoRun (void) |
| 338 { |
| 339 key1 = "The quick brown "; |
| 340 key2 = "Incremental."; |
| 341 key12 = key1 + key2; |
| 342 |
| 343 std::cout << GetName () << "checking with key: " |
| 344 << "\"" << key1 << "\"[" << key1.size () << "] + " |
| 345 << "\"" << key2 << "\"[" << key2.size () << "]" << std::endl; |
| 346 std::cout << GetName () << "equivalent to: " |
| 347 << "\"" << key12 << "\"[" << key12.size () << "]" << std::endl; |
| 348 |
| 349 DoHash ( "default", Hasher ( ) ); |
| 350 DoHash ( "murmur3", Hasher ( Create<Hash::Function::Murmur3> () ) ); |
| 351 DoHash ( "FNV1a", Hasher ( Create<Hash::Function::Fnv1a> () ) ); |
| 352 } |
| 353 |
| 354 //---------------------------- |
| 355 // |
162 // Hash tester | 356 // Hash tester |
163 | 357 |
164 class HashTestSuite : public TestSuite | 358 class HashTestSuite : public TestSuite |
165 { | 359 { |
166 public: | 360 public: |
167 HashTestSuite (); | 361 HashTestSuite (); |
168 }; | 362 }; |
169 | 363 |
170 HashTestSuite::HashTestSuite () | 364 HashTestSuite::HashTestSuite () |
171 : TestSuite ("hash", UNIT) | 365 : TestSuite ("hash", UNIT) |
172 { | 366 { |
173 AddTestCase (new HashFoxTestCase); | 367 AddTestCase (new DefaultHashTestCase); |
174 AddTestCase (new HashFnv1aTestCase); | 368 AddTestCase (new Murmur3TestCase); |
175 AddTestCase (new HashMurmur3TestCase); | 369 AddTestCase (new Fnv1aTestCase); |
| 370 AddTestCase (new Hash32FunctionPtrTestCase); |
| 371 AddTestCase (new Hash64FunctionPtrTestCase); |
| 372 AddTestCase (new IncrementalTestCase); |
176 } | 373 } |
177 | 374 |
178 static HashTestSuite g_hashTestSuite; | 375 static HashTestSuite g_hashTestSuite; |
179 | 376 |
180 } // namespace ns3 | 377 } // namespace ns3 |
OLD | NEW |