Generic hash function interface, with two implementations.

This is the first of three of patches to address Bug 582,
"Tags are not serialized and deserialized from Packet::Serialize and Packet::Deserialize" 
https://www.nsnam.org/bugzilla/show_bug.cgi?id=582

One issue is to serialize the *type* of the derived Tag, when the Packet only has a PacketTagList to work from.  This serialization has to produce a consistent result on every compute node in a parallel cluster, even one with heterogeneous nodes. This can be particularly tricky if the different instances of ns3 don't create TypeId's in the same order, which results in a single type (by name) being represented by different TypeId values (integers) on different nodes.

One approach, partially implemented by Jeffrey Young at Georgia Tech, is to serialize the TypeId name (a string).  This seems unattractive because it takes time and space, typically much more space than the tag data itself (which is limited to 20 bytes).

The alternative approach proposed here is to add a consistent 32-bit hash to the TypeId, then pass that to identify the tag type.

To simplify review, I've split this into three patches:

1.  Add class Hash:  generic hash function interface, with two implementations (this review).

2.  Add hashes to TypeId.

3.  Use TypeId hash to serialize Tags.

This review covers the Hash class and implementation.  The class itself provides a simple API for callers to hash objects.  It wraps multiple underlying hash function implementations.  This patch includes the venerable FNV1a, and murmur3.  

It is straightforward to add new implementations.   If your hash function has the right signature, it can be as simple as:

    Hash (Ptr<HashImplementation> (Hash32Implementation<&hashf>))

[Jeff Y, 2012-07-23 14:19:42]

Peter,

  This looks good to me at least in terms of the coding style, and the comments
look detailed and reasonable.

  I had one question that maybe someone else on the NS-3 dev team can help
answer. I realize the use of different namespaces is added for scoping and
clarity, but I'm wondering if there are any restrictions on how many levels of
nested namespaces can be used. Most code currently in the core directory just
uses the ns3 namespace, but you have several files that have the nested
<Hash::Function::*Implementation>. It's quite likely it's not a big deal, but
this is the only thing I would check on.

--Jeff

http://codereview.appspot.com/6357056/diff/1/doc/manual/source/hash-functions...
File doc/manual/source/hash-functions.rst (right):

http://codereview.appspot.com/6357056/diff/1/doc/manual/source/hash-functions...
doc/manual/source/hash-functions.rst:71: * SMHasher:
Assuming that you want to point to http://code.google.com/p/smhasher/

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-fnv.cc
File src/core/model/hash-fnv.cc (right):

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-fnv.cc#newco...
src/core/model/hash-fnv.cc:40: 
Does NS-3 specify a specific depth for nested namespaces? I'm not sure if
Function and *Implementation namespaces would make use more confusing or
conflict with existing NS-3 layout.

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-fnv.h
File src/core/model/hash-fnv.h (right):

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-fnv.h#newcode59
src/core/model/hash-fnv.h:59: */
Might be useful to indicate here that Fnv1a doesn't have an "initial state", so
nothing is returned for this hash implementation.

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-murmur3.h
File src/core/model/hash-murmur3.h (right):

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-murmur3.h#ne...
src/core/model/hash-murmur3.h:67: * Restore initial state
Might be useful to indicate here that Murmur doesn't have an "initial state", so
nothing is returned.

[Peter Barnes, 2012-07-23 18:45:29]

http://codereview.appspot.com/6357056/diff/1/doc/manual/source/hash-functions...
File doc/manual/source/hash-functions.rst (right):

http://codereview.appspot.com/6357056/diff/1/doc/manual/source/hash-functions...
doc/manual/source/hash-functions.rst:71: * SMHasher:
On 2012/07/23 14:19:42, Jeff Y wrote:
> Assuming that you want to point to http://code.google.com/p/smhasher/

Will be fixed in next patch.

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-fnv.cc
File src/core/model/hash-fnv.cc (right):

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-fnv.cc#newco...
src/core/model/hash-fnv.cc:40: 
On 2012/07/23 14:19:42, Jeff Y wrote:
> Does NS-3 specify a specific depth for nested namespaces? I'm not sure if
> Function and *Implementation namespaces would make use more confusing or
> conflict with existing NS-3 layout.

Interesting Q in general.  

The motivation here is to keep separate the global names of each implementation.
 It's easy to imagine several hash implementations with functions named "hash,"
say.  If they all get dumped into the same namespace, addition of the second
implementation will break the compile, possibly in the original implementation
file, which would be very hard to diagnose.

We can argue whether I need the Function namespace.

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-fnv.h
File src/core/model/hash-fnv.h (right):

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-fnv.h#newcode59
src/core/model/hash-fnv.h:59: */
On 2012/07/23 14:19:42, Jeff Y wrote:
> Might be useful to indicate here that Fnv1a doesn't have an "initial state",
so
> nothing is returned for this hash implementation.

All hash functions have an initial state.  What's missing from this wrapper (my
Hasher class on down) is the capability for incremental hashing:  start in the
initial state, hash this chunk (buffer), now continue hashing with the next
chunk, ... finally give me the accumulated hash.

I haven't implemented this yet, because no one needs it at the moment.  I should
just go ahead and implement, then the clear() functions won't seem so useless.

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-murmur3.h
File src/core/model/hash-murmur3.h (right):

http://codereview.appspot.com/6357056/diff/1/src/core/model/hash-murmur3.h#ne...
src/core/model/hash-murmur3.h:67: * Restore initial state
On 2012/07/23 14:19:42, Jeff Y wrote:
> Might be useful to indicate here that Murmur doesn't have an "initial state",
so
> nothing is returned.

Will implement incremental hashing interface.

[Peter Barnes, 2012-07-25 23:48:31]

On 2012/07/25 23:40:32, Peter Barnes wrote:
Looks like a few ns-3-dev changes snuck in to src/core/wscript in this second
patch.

[Jeff Y, 2012-07-26 14:50:13]

Patch Set 2 looks good. Thanks for going ahead and adding support and test cases
for incremental hash. I was going to suggest marking it as TBD, but your
implementation looks good.

As for the namespaces, I'm not too picky on how this is implemented. I can't
think of a rule that would preclude this usage (especially since it helps
delineate different hash functions), so it was more of a question about NS-3
style than anything else.

[Mathieu Lacage, 2012-07-28 07:43:11]

one minor comment. nothing holding commit. Great code !

http://codereview.appspot.com/6357056/diff/7001/src/core/model/hash-function.h
File src/core/model/hash-function.h (right):

http://codereview.appspot.com/6357056/diff/7001/src/core/model/hash-function....
src/core/model/hash-function.h:33: typedef uint32_t Hash32_t;
In general, I have tried to avoid such typedefs in ns-3 and just expose the
underlying type. I can live with that but I believe that it is better to expose
the integer and clearly convey to the user the fact that the type has clear and
unambiguous value semantics. 

In typical torvalds style:
http://lkml.indiana.edu/hypermail/linux/kernel/0206.1/0402.html

I know that many others disagree with that specific use of typedef (to hide
integer types) and I am not going to block that patch for that but I wanted to
point out how the existing codebase handles this issue.

[Mathieu Lacage, 2012-07-28 08:01:39]

ack

[Peter Barnes, 2012-08-20 19:40:17]

On 2012/07/28 07:43:11, Mathieu Lacage wrote:
>
http://codereview.appspot.com/6357056/diff/7001/src/core/model/hash-function....
> src/core/model/hash-function.h:33: typedef uint32_t Hash32_t;
> it is better to expose the integer and clearly convey to the user the fact
that 
> the type has clear and unambiguous value semantics. 
> 
> In typical torvalds style:
> http://lkml.indiana.edu/hypermail/linux/kernel/0206.1/0402.html

We can argue about the advantages in C++ vs. the disadvantages in C, but that's
best done over beer ;)

Removed in next version.

[Peter Barnes, 2012-08-20 23:32:58]

http://codereview.appspot.com/6357056/diff/7001/src/core/wscript
File src/core/wscript (right):

http://codereview.appspot.com/6357056/diff/7001/src/core/wscript#newcode127
src/core/wscript:127: 'model/random-variable-stream.cc',
Not sure how these edits got in here; not part of hash

http://codereview.appspot.com/6357056/diff/20001/src/core/model/hash.h
File src/core/model/hash.h (right):

http://codereview.appspot.com/6357056/diff/20001/src/core/model/hash.h#newcode29
src/core/model/hash.h:29: #include "hash-function.h"  // typedef ns3::uint32_t,
ns3::uint64_t
Oops

[Tom Henderson, 2013-07-25 04:31:46]

On 2013/07/24 21:13:30, Peter Barnes wrote:

Peter, can you refresh us on the status of this and the associated bug.?