DJB2 Hash for applications where high speed hash or checksum values are neede...

DJB2 Hash for applications where high speed hash or checksum values are needed.
BUG=21126
TEST=djb2_unittest.cc has a quick test.  will replace versions in media unittests and media_bench in future.


Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=28532

[fbarchard, 2009-09-09 22:32:40]

any feedback on this?
I'm switching to a new machine and it would be easier to commit before than
after.

[scherkus (not reviewing), 2009-09-09 23:37:00]

mostly nits on the documentation in the header file

a lot of stuff under /base has excellent documentation so there's a higher bar
to meet :)

http://codereview.chromium.org/193028/diff/7003/6004
File base/djb2.cc (right):

http://codereview.chromium.org/193028/diff/7003/6004#newcode11
Line 11: hash = hash * 33 + *s++;
I can't take credit for this, but (hash * 33) can also be written as ((hash <<
5) + hash)

not sure if gcc/msvc would generate any better assembly

http://codereview.chromium.org/193028/diff/7003/6003
File base/djb2.h (right):

http://codereview.chromium.org/193028/diff/7003/6003#newcode9
Line 9: 
namespace base

http://codereview.chromium.org/193028/diff/7003/6003#newcode10
Line 10: // These functions perform DJB2 hash. The simplest call is DJB2Hash to
nit: there's only one function :)

http://codereview.chromium.org/193028/diff/7003/6003#newcode11
Line 11: // generate the DJB2 hash of the given data.
nit: use a colon to introduce a code sample (replace . with :)

http://codereview.chromium.org/193028/diff/7003/6003#newcode15
Line 15: // calls to DJB2Hash:
nit: DJB2Hash -> DJB2Hash()

http://codereview.chromium.org/193028/diff/7003/6003#newcode16
Line 16: //
nit remove this blank line and indent the code sample by two spaces

http://codereview.chromium.org/193028/diff/7003/6003#newcode17
Line 17: // uint32 hash_value = 5381u;  // Seed for DJB2.
if this seed value is essential for DJB2 I would document it as a global
constant

http://codereview.chromium.org/193028/diff/7003/6003#newcode21
Line 21: // }
I would add an extra section describing what djb2 has over the other hashes
available in /base (sha2, md5) and when you would use it

and links to online documentation is also a good thing

http://codereview.chromium.org/193028/diff/7003/6003#newcode25
Line 25: uint32 DJB2Hash(const void* buf, size_t len, uint32 seed);
nit: this function could be const

[fbarchard, 2009-09-10 00:19:19]

fixed up md5 errors

http://codereview.chromium.org/193028/diff/7003/6004
File base/djb2.cc (right):

http://codereview.chromium.org/193028/diff/7003/6004#newcode11
Line 11: hash = hash * 33 + *s++;
Sometimes shift is faster, sometimes slower.  Using * 33 the compiler is usually
smart enough to figure it out, whereas shift is hard to make into a multiply.
If we care about performance, I'll do it in assembly.  I'd need to benchmark it
to see if it would make a noticable difference to regression testing or
something.

http://codereview.chromium.org/193028/diff/7003/6003
File base/djb2.h (right):

http://codereview.chromium.org/193028/diff/7003/6003#newcode9
Line 9: 
MD5 does not.  I thought this should be as similar as possible to MD5?

http://codereview.chromium.org/193028/diff/7003/6003#newcode10
Line 10: // These functions perform DJB2 hash. The simplest call is DJB2Hash to
On 2009/09/09 23:37:00, scherkus wrote:
> nit: there's only one function :)

Ya, I considered doing the full MD5 API, but it would be less efficient, harder
to use, and harder to make assembly later.  But orthogonal.

http://codereview.chromium.org/193028/diff/7003/6003#newcode11
Line 11: // generate the DJB2 hash of the given data.
On 2009/09/09 23:37:00, scherkus wrote:
> nit: use a colon to introduce a code sample (replace . with :)

Done.

http://codereview.chromium.org/193028/diff/7003/6003#newcode15
Line 15: // calls to DJB2Hash:
I followed MD5 style.  Including these fixes to md5.h
Done.

http://codereview.chromium.org/193028/diff/7003/6003#newcode16
Line 16: //
fixed in MD5.h as well.

http://codereview.chromium.org/193028/diff/7003/6003#newcode17
Line 17: // uint32 hash_value = 5381u;  // Seed for DJB2.
On 2009/09/09 23:37:00, scherkus wrote:
> if this seed value is essential for DJB2 I would document it as a global
> constant

Done.

http://codereview.chromium.org/193028/diff/7003/6003#newcode21
Line 21: // }
Done.  Also added for MD5

http://codereview.chromium.org/193028/diff/7003/6003#newcode25
Line 25: uint32 DJB2Hash(const void* buf, size_t len, uint32 seed);
On 2009/09/09 23:37:00, scherkus wrote:
> nit: this function could be const

md5 isn't.  Thats more common for class members.

[fbarchard, 2009-09-11 18:06:50]

Here is the code generated for djb2
mov         esi,eax
shl         esi,5
add         esi,eax
movzx       eax,byte ptr [ecx]
add         eax,esi
add         ecx,1
sub         edx,1
jne         00000011

[fbarchard, 2009-09-12 02:41:59]

ping?

The code for djb2 has been used in several unittests and benchmarks.  It would
be nice to move it a central place available to all of chrome

[fbarchard, 2009-09-17 18:11:53]

can I go ahead with the commit?
This code is on my old machine, which will be reformatted for linux asap

[fbarchard, 2009-09-21 22:36:24]

any thoughts on djb2 hash?

[fbarchard, 2009-10-05 21:47:36]

ping

[brettw, 2009-10-05 21:53:30]

Is there a need to put this in base? Can you just put it in the media directory
where you need it?

[scherkus (not reviewing), 2009-10-05 22:00:18]

doh sorry for not reviewing this earlier.. if media/base is the better fit then
so be it

md5 clean up looks good though

[fbarchard, 2009-10-08 18:43:44]

split md5 change into its own CL.
moved into media/base

[brettw, 2009-10-08 22:40:42]

LGTM with one change.

http://codereview.chromium.org/193028/diff/21003/21007
File media/base/djb2.h (right):

http://codereview.chromium.org/193028/diff/21003/21007#newcode5
Line 5: #ifndef BASE_DJB2_H_
Be sure to update these include guards.

http://codereview.chromium.org/193028/diff/21003/21007#newcode21
Line 21: const uint32 kDJB2HashSeed = 5381u;
This will cause errors if this file is included from more than one .cc file,
since there will be dulpicate definitions. You need to declare it extern in the
header and put the value in a .cc.

[awong, 2009-10-08 22:56:53]

http://codereview.chromium.org/193028/diff/21003/21007
File media/base/djb2.h (right):

http://codereview.chromium.org/193028/diff/21003/21007#newcode21
Line 21: const uint32 kDJB2HashSeed = 5381u;
On 2009/10/08 22:40:42, brettw wrote:
> This will cause errors if this file is included from more than one .cc file,
> since there will be dulpicate definitions. You need to declare it extern in
the
> header and put the value in a .cc.

I'm actually pretty certain that in C++, this isn't a problem.  This got
discussed in the webkit-dev list a while back, and global consts end up having
internal linkage (and in this case, it probably just gets constant propagated
away).

Here's the links given on the webkit-dev thread:
http://stackoverflow.com/questions/998425/why-does-const-imply-internal-linka...
http://bytes.com/topic/c/answers/62013-const-has-internal-linkage-c

[fbarchard, 2009-10-08 23:08:14]

originally I had a macro.  andrew suggested const.  I did static const, which
works in c, but he said remove static.
i'll add the static again, which I know limits the scope to each file.