code review 4257042: hash: new FNV-1a implementation

hash: new FNV-1a implementation

[pascal, 2011-02-26 15:14:11]

Hello golang-dev@googlegroups.com (cc: fnv-mail@asthe.com,
golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[agl1, 2011-02-26 21:40:21]

On Sat, Feb 26, 2011 at 10:14 AM,  <pascal@quies.net> wrote:
> Description:
> hash: new FNV-1a implementation

I wonder if FNV1a is sufficiently useful to be included in the
standard library. Was there something in particular that you needed it
for?


Cheers

AGL

[rsc, 2011-02-26 22:13:05]

I don't know.  If we had any hash functions yet then
it might be out of place but right now there is nothing
in the gap between CRC and cryptographic hashes
like SHA1.  That is, we don't have any hash functions,
in the original sense of the term.  A well written
implementation of a well engineered general purpose
hash function like FNV seems like it would fill that
gap nicely.

Russ

[agl1, 2011-02-28 14:04:09]

LGTM

http://codereview.appspot.com/4257042/diff/2001/src/pkg/hash/fnv/fnv.go
File src/pkg/hash/fnv/fnv.go (right):

http://codereview.appspot.com/4257042/diff/2001/src/pkg/hash/fnv/fnv.go#newcode5
src/pkg/hash/fnv/fnv.go:5: // Fowler-Noll-Vo is a non-cryptographic hash
function
// The fnv package implements FNV-1a, a non-cryptographic hash function created
by Glenn Fowler, Landon Curt Noll, and Phong Vo. See
http://isthe.com/chongo/tech/comp/fnv/.

http://codereview.appspot.com/4257042/diff/2001/src/pkg/hash/fnv/fnv_test.go
File src/pkg/hash/fnv/fnv_test.go (right):

http://codereview.appspot.com/4257042/diff/2001/src/pkg/hash/fnv/fnv_test.go#...
src/pkg/hash/fnv/fnv_test.go:6: 
I understand that you're using double newlines for grouping, but it looks a
little loose here (and also at the beginning of fnv.go).

[rsc, 2011-02-28 15:30:34]

I'd be just as happy without the double newlines.

// Constructs a 32-bit FNV-1a implementation
should be

// New32 returns a new hash.Hash computing the 32-bit FNV-1a hash.

similarly New64.

[pascal, 2011-02-28 21:13:54]

Hello agl1, rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-02-28 21:24:12]

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go
File src/pkg/hash/fnv/fnv_test.go (right):

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#...
src/pkg/hash/fnv/fnv_test.go:16: var golden32 = map[uint32]string{
more typical is

var golden32 = []struct{
    sum uint32
    text uint32
}{
    {0x811c9dc5, ""},
    ...
}

and then 

for tt := range golden32 {
   use tt.sum, tt.range
}

the map is cute but it means you can't depend on
the iteration order.

look at the tests for hash/crc32 for example.

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#...
src/pkg/hash/fnv/fnv_test.go:36: t.Errorf("Integer 0x%x instead of 0x%x for %s",
actual, expected, text)
look at crc32_test.go for error message format too.
easier to give enough details if you speak in Go code.

t.Errorf("hash32(%q) = 0x%x want 0x%x", tt.text, tt.sum, sum)

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#...
src/pkg/hash/fnv/fnv_test.go:39: t.Errorf("Array 0x%x instead of 0x%x for %s",
actual, expected, text)
t.Errorf("hash32(%q) bytes = 0x%x want 0x%x", tt.text, tt.sum, sum)

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#...
src/pkg/hash/fnv/fnv_test.go:72: t.Fatal("Wrong size")
all these prints should have details.

t.Fatalf("h.Size()=%d but len(sum)=%d", h.Size(), len(sum))

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#...
src/pkg/hash/fnv/fnv_test.go:76: t.Fatal("Sum changed on retry")
t.Fatalf("first h.Sum()=%x, second h.Sum()=%x", sum, second)

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#...
src/pkg/hash/fnv/fnv_test.go:82: t.Fatal("Sum changed with reset")
t.Fatalf("h.Sum()=%x, but after Reset h.Sum()=%x", sum, second)

http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.go#...
src/pkg/hash/fnv/fnv_test.go:89: t.Fatal("Sum changed with partitial writes")
t.Fatalf("h.Sum()=%x, but with partial writes, h.Sum()=%x", sum, second)

[pascal, 2011-02-28 22:49:37]

Hi Russ,

Thanks for the feedback. 

Why would the order matter for the golden tests?

More descriptive test assertions are ofcourse always a good thing. However 
doing so in Go is currently quite repetitive. After makeing the changes I'll 
create a separate proposal on golang-dev to standardize this.

Cheers


On Monday 28 February 2011 22:24:12 rsc@golang.org wrote:
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o File src/pkg/hash/fnv/fnv_test.go (right):
> 
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o#newcode16 src/pkg/hash/fnv/fnv_test.go:16: var golden32 =
> map[uint32]string{ more typical is
> 
> var golden32 = []struct{
>      sum uint32
>      text uint32
> }{
>      {0x811c9dc5, ""},
>      ...
> }
> 
> and then
> 
> for tt := range golden32 {
>     use tt.sum, tt.range
> }
> 
> the map is cute but it means you can't depend on
> the iteration order.
> 
> look at the tests for hash/crc32 for example.
> 
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o#newcode36 src/pkg/hash/fnv/fnv_test.go:36: t.Errorf("Integer 0x%x instead
> of 0x%x for %s", actual, expected, text)
> look at crc32_test.go for error message format too.
> easier to give enough details if you speak in Go code.
> 
> t.Errorf("hash32(%q) = 0x%x want 0x%x", tt.text, tt.sum, sum)
> 
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o#newcode39 src/pkg/hash/fnv/fnv_test.go:39: t.Errorf("Array 0x%x instead
> of 0x%x for %s", actual, expected, text)
> t.Errorf("hash32(%q) bytes = 0x%x want 0x%x", tt.text, tt.sum, sum)
> 
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o#newcode72 src/pkg/hash/fnv/fnv_test.go:72: t.Fatal("Wrong size")
> all these prints should have details.
> 
> t.Fatalf("h.Size()=%d but len(sum)=%d", h.Size(), len(sum))
> 
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o#newcode76 src/pkg/hash/fnv/fnv_test.go:76: t.Fatal("Sum changed on
> retry")
> t.Fatalf("first h.Sum()=%x, second h.Sum()=%x", sum, second)
> 
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o#newcode82 src/pkg/hash/fnv/fnv_test.go:82: t.Fatal("Sum changed with
> reset") t.Fatalf("h.Sum()=%x, but after Reset h.Sum()=%x", sum, second)
> 
> http://codereview.appspot.com/4257042/diff/4004/src/pkg/hash/fnv/fnv_test.g
> o#newcode89 src/pkg/hash/fnv/fnv_test.go:89: t.Fatal("Sum changed with
> partitial writes")
> t.Fatalf("h.Sum()=%x, but with partial writes, h.Sum()=%x", sum, second)
> 
> http://codereview.appspot.com/4257042/

[rsc, 2011-03-01 15:19:02]

> Why would the order matter for the golden tests?

It's often useful to have the simple tests before the
more complicated tests.  Also, the map approach
fails as soon as there is more than one argument or
more than one result or more than one test with the
same result.

Russ

[rsc, 2011-03-01 16:41:11]

I looked again at the FNV web page.
There's no indication there that the FNV-1a hash
is meant to supersede the FNV-1 hash.
It's a little confusing for hash/fnv's New32 to
compute the FNV-1a hash.  They're very similar,
of course, but I think it would be better to expose
both.  People who use the package to get the
specific FNV hash (as opposed to using the
package to get some good general purpose hash)
will be surprised that it doesn't give standard FNV1.

New32, New32a, New64, New64a
?

Russ

[pascal, 2011-03-01 19:48:33]

Hi Russ,

It's better to reflect the algorithm in the API indeed. How about fnv1a.New32 
and fnv1a.New64?

 "Some people use FNV-1a instead of FNV-1 because they see slightly better 
dispersion for tiny (<4 octets) chunks of memory. Either FNV-1 or FNV-1a make 
a fine hash"
-- http://isthe.com/chongo/tech/comp/fnv/#FNV-1a

Now we're on the subject of consistency, I found it somewhat odd that 
hash.Hash#Sum() doesn't specify it's endianness. Shall I include a comment 
with this patch?

Cheers,

Pascal


On Tuesday 01 March 2011 17:41:05 Russ Cox wrote:
> I looked again at the FNV web page.
> There's no indication there that the FNV-1a hash
> is meant to supersede the FNV-1 hash.
> It's a little confusing for hash/fnv's New32 to
> compute the FNV-1a hash.  They're very similar,
> of course, but I think it would be better to expose
> both.  People who use the package to get the
> specific FNV hash (as opposed to using the
> package to get some good general purpose hash)
> will be surprised that it doesn't give standard FNV1.
> 
> New32, New32a, New64, New64a
> ?
> 
> Russ

[rsc, 2011-03-01 21:21:54]

> It's better to reflect the algorithm in the API indeed. How about fnv1a.New32
> and fnv1a.New64?

I'd rather not have two distinct packages for algorithms
that differ only in one line.
Let's keep it as fnv and use New32, New32a, New64, New64a.

I'm not sure that the interface definition needs to state
the endian-ness of the check-sum.  I will think about it.

Russ

[pascal, 2011-03-01 22:19:51]

Hello agl1, rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-03-02 18:44:55]

please add FNV-1 (non-a)

http://codereview.appspot.com/4257042/diff/15001/src/pkg/hash/fnv/fnv.go
File src/pkg/hash/fnv/fnv.go (right):

http://codereview.appspot.com/4257042/diff/15001/src/pkg/hash/fnv/fnv.go#newc...
src/pkg/hash/fnv/fnv.go:7: // Noll, and Phong Vo.
move Noll, up to previous line.
just to avoid splitting his name.

http://codereview.appspot.com/4257042/diff/15001/src/pkg/hash/fnv/fnv.go#newc...
src/pkg/hash/fnv/fnv.go:28: // New32 returns a new hash.Hash computing the
32-bit FNV-1a hash.
New32a

[pascal, 2011-03-03 02:50:32]

Hello agl1, rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-03-03 03:21:34]

Please complete a CLA as described at
http://golang.org/doc/contribute.html#copyright

Thanks.
Russ

[rsc, 2011-03-03 16:49:15]

LGTM

Please make the minor comment fix below and I will submit.

http://codereview.appspot.com/4257042/diff/10003/src/pkg/hash/fnv/fnv.go
File src/pkg/hash/fnv/fnv.go (right):

http://codereview.appspot.com/4257042/diff/10003/src/pkg/hash/fnv/fnv.go#newc...
src/pkg/hash/fnv/fnv.go:5: // The fnv package implements FNV-1 and FNV-1a, a
s/ a//

http://codereview.appspot.com/4257042/diff/10003/src/pkg/hash/fnv/fnv.go#newc...
src/pkg/hash/fnv/fnv.go:6: // non-cryptographic hash function created by
s/function/functions/

[pascal, 2011-03-03 23:39:22]

Hello agl1, rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[pascal, 2011-03-04 02:13:31]

Hello agl1, rsc (cc: golang-dev@googlegroups.com),

Please take another look.

[rsc, 2011-03-07 15:25:43]

LGTM

[rsc, 2011-03-07 16:11:25]

*** Submitted as 50bc23b43d82 ***

hash: new FNV-1a implementation

R=agl1, rsc
CC=golang-dev
http://codereview.appspot.com/4257042

Committer: Russ Cox <rsc@golang.org>