tjwebb / fnv-plus

Javascript FNV-1a Hash Algorithm (up to 1024 bit) implementation. Based on:
http://tools.ietf.org/html/draft-eastlake-fnv-06
85 stars 13 forks source link

Interoperability with other implementations of FNV-1a #2

Closed mjradwin closed 10 years ago

mjradwin commented 10 years ago

How would you propose using your fnvplus.seed() API to support using the standard offset_basis values as described in draft-eastlake-fnv-06.txt?

We would like to be able to initialize fnvplus so it is compatible with Appendix C: A Few Test Vectors :

var fnv = require('fnv-plus'),
    assert = require('assert');

assert.equal(fnv.hash('',       64).hex(), 'cbf29ce484222325');
assert.equal(fnv.hash('a',      64).hex(), 'af63dc4c8601ec8c');
assert.equal(fnv.hash('foobar', 64).hex(), '85944171f73967e8');

In our Java application, we generate unique IDs using 64-bit FNV-1a. For the same given string we would like to be able to generate the identical hash values in JavaScript using fnv-plus. The fnvplus.seed() implementation does allow the caller to specify a seed value, but that value is transformed (through hashing) so it can't be used as an offset_basis.

tjwebb commented 10 years ago

So, there are two issues at hand here:

  1. The offset_basis is actually a hash; the default seed is actually an FNV-0 hash of the string chongo <Landon Curt Noll> /\../\. So I can make my API clearer to this effect: that the input into seed() will be hashed using FNV-0. If it were not, some other strategy e.g. modulus would need to be used to ensure that the seed is within the keyspace of the target hash function.
  2. It is the case that I do not test fidelity to the reference implementation in this manner, which may result in seeing output that doesn't seem to line up with your existing hashes. I will take a closer look at this and give you an update on my findings.
tjwebb commented 10 years ago

I hadn't noticed this before, but it makes sense now: the reference offset_basis values are actually computed using FNV-1, and not FNV-1a, and so my offsets will not match the reference offsets. IMO this is basically historical error, but I should nevertheless conform to the extant literature. I will correct this in v1.2.7.

tjwebb commented 10 years ago

@mjradwin I think I've resolved your issue. See: https://github.com/tjwebb/fnv-plus/blob/master/spec/fnv-plus.js#L110-L127

mjradwin commented 10 years ago

Awesome, thanks! I will pull the latest and confirm your fix.

tjwebb commented 10 years ago

Great, let me know.

mjradwin commented 10 years ago

Pulled 1.2.7 from npm and everything's working great!

tjwebb commented 10 years ago

Excellent. Thanks for your feedback