Moved SuperFastHash function from base/hash.cc to base/third_party.

Moved SuperFastHash function from base/hash.cc to base/third_party.

This code was written by Paul Hsieh under a 3-clause BSD license. It
belongs in third_party.

I did not move the existing implementation, but re-downloaded the code
from upstream:
http://www.azillionmonkeys.com/qed/hash.html
This version is formatted differently and is written in plain C, but it
is identical to the version that was previously in hash.cc.

Added LICENSE and README.chromium files, as well as adding license text
to the top of superfasthash.cc, as required by checklicenses.py.

BUG=347393
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=254437

[Matt Giuca, 2014-02-27 02:56:08]

+open-source-third-party-reviews: Please review for compliance. Note that it
passes checklicenses.py, which identifies the license as "BSD (3 clause)".

+security@chromium.org: Potential security concerns:
- Buffer overrun: Indexing logic is somewhat complicated, but I can't see any
possibility of buffer overrun here.
- Hash collisions: This hash should not be used for cryptographic purposes.

Note: This CL will only be committed after
https://codereview.chromium.org/182593002, which adds comprehensive unit tests
for this function (to ensure that nothing has broken during the move).

https://codereview.chromium.org/181643004/diff/20001/base/third_party/superfa...
File base/third_party/superfasthash/OWNERS (right):

https://codereview.chromium.org/181643004/diff/20001/base/third_party/superfa...
base/third_party/superfasthash/OWNERS:2: rvargas@chromium.org
Ricardo, are you okay with being an owner on this third_party module?

[Matt Giuca, 2014-02-27 03:14:09]

https://codereview.chromium.org/181643004/diff/20001/base/hash.cc
File base/hash.cc (right):

https://codereview.chromium.org/181643004/diff/20001/base/hash.cc#newcode10
base/hash.cc:10: return ::SuperFastHash(data, len);
Note: This added indirection may introduce a slight performance regression,
since we now need to call across to another function in a different module (I
looked at the assembly code on Linux; it compiles to an extra jump).

This is probably nothing to worry about, but if we are extremely worried about
performance here, we could directly export the SuperFastHash function from
superfasthash.c (which would require modifying the third_party code to import
base/base_export.h -- it's messier so I'm not in favour of it unless absolutely
necessary).

[rvargas (doing something else), 2014-02-27 04:11:20]

LGTM. Thanks for doing this.

https://codereview.chromium.org/181643004/diff/20001/base/hash.h
File base/hash.h (right):

https://codereview.chromium.org/181643004/diff/20001/base/hash.h#newcode13
base/hash.h:13: #ifdef __cplusplus
Do we need this?

https://codereview.chromium.org/181643004/diff/20001/base/third_party/superfa...
File base/third_party/superfasthash/OWNERS (right):

https://codereview.chromium.org/181643004/diff/20001/base/third_party/superfa...
base/third_party/superfasthash/OWNERS:2: rvargas@chromium.org
On 2014/02/27 02:56:09, Matt Giuca wrote:
> Ricardo, are you okay with being an owner on this third_party module?

Of course.

[Matt Giuca, 2014-02-27 04:24:09]

https://codereview.chromium.org/181643004/diff/20001/base/hash.h
File base/hash.h (right):

https://codereview.chromium.org/181643004/diff/20001/base/hash.h#newcode13
base/hash.h:13: #ifdef __cplusplus
On 2014/02/27 04:11:20, rvargas wrote:
> Do we need this?

Assuming you mean #ifdef __cplusplus as opposed to extern "C" as a whole. You're
right, I should assume C++ in a C++ source file!

(Also, I just realised it shouldn't be in hash.h, but hash.cc -- whoops.)

[jln (very slow on Chromium), 2014-02-27 04:37:17]

Security review:

This is a surprisingly painful 60 LOC.

I think I'd be fine with leaving third_party/superfasthash as-is, despite its
problems, but let's handle the cast in base/ better!

https://codereview.chromium.org/181643004/diff/20001/base/hash.h
File base/hash.h (right):

https://codereview.chromium.org/181643004/diff/20001/base/hash.h#newcode26
base/hash.h:26: 
Please, make it very clear that none of these should be used a cryptographically
secure hash functions.

https://codereview.chromium.org/181643004/diff/20001/base/hash.h#newcode30
base/hash.h:30: return SuperFastHash(key, static_cast<int>(length));
This cast is implementation defined for values strictly larger than MAX_INT.
In this particular case, it won't lead to memory corruption iff SuperFastHash()
handles negative length with no memory access.

It's not great to have to rely on a dependency in third_party to respect an
implicit contract like this.

Could you please add:

if (length > std::numeric_limits<int>::max()) {
  NOTREACHED();
  return 0;
}

https://codereview.chromium.org/181643004/diff/40001/base/third_party/superfa...
File base/third_party/superfasthash/superfasthash.c (right):

https://codereview.chromium.org/181643004/diff/40001/base/third_party/superfa...
base/third_party/superfasthash/superfasthash.c:47: rem = len & 3;
I know it's not your code, but compilers would optimize this correctly if we
used the more legible:
rem = len % 4;
len /= 4;

https://codereview.chromium.org/181643004/diff/40001/base/third_party/superfa...
base/third_party/superfasthash/superfasthash.c:55: data  += 2*sizeof (uint16_t);
The code is already assuming that this is exactly 4. If chat weren't 8 bits
long, it wouldn't work anyways because of "data + 2" above.

https://codereview.chromium.org/181643004/diff/40001/base/third_party/superfa...
base/third_party/superfasthash/superfasthash.c:63: hash ^= ((signed
char)data[sizeof (uint16_t)]) << 18;
why the cast, it's already signed
Also, same remark with sizeof(uint16_t); this doesn't make the code more
generic, the assumption that it's "2" is already hardwired here.

[Matt Giuca, 2014-02-27 05:25:29]

Hi Julien,

Thanks for a speedy security review!

> This is a surprisingly painful 60 LOC.

I know :(

> I think I'd be fine with leaving third_party/superfasthash as-is, despite
> its problems, but let's handle the cast in base/ better!

I agree with your assessment of third_party/superfasthash (I've been staring at
this code all morning wishing I could refactor this code). But I think
ultimately we should make as few changes as possible to third_party code
(compatibility, security, and legal only). None of the issues you mentioned
address security concerns, they just make the code more readable.

https://codereview.chromium.org/181643004/diff/20001/base/hash.h
File base/hash.h (right):

https://codereview.chromium.org/181643004/diff/20001/base/hash.h#newcode26
base/hash.h:26: 
On 2014/02/27 04:37:17, jln wrote:
> Please, make it very clear that none of these should be used a
cryptographically
> secure hash functions.

Done.

https://codereview.chromium.org/181643004/diff/20001/base/hash.h#newcode30
base/hash.h:30: return SuperFastHash(key, static_cast<int>(length));
On 2014/02/27 04:37:17, jln wrote:
> This cast is implementation defined for values strictly larger than MAX_INT.
> In this particular case, it won't lead to memory corruption iff
SuperFastHash()
> handles negative length with no memory access.
> 
> It's not great to have to rely on a dependency in third_party to respect an
> implicit contract like this.
> 
> Could you please add:
> 
> if (length > std::numeric_limits<int>::max()) {
>   NOTREACHED();
>   return 0;
> }

Done.

(Note that the existing implementation does check len <= 0, so there is no
existing security vulnerability here, but I agree that we should be checking all
the same.)

https://codereview.chromium.org/181643004/diff/40001/base/third_party/superfa...
File base/third_party/superfasthash/superfasthash.c (right):

https://codereview.chromium.org/181643004/diff/40001/base/third_party/superfa...
base/third_party/superfasthash/superfasthash.c:47: rem = len & 3;
I agree, but there is no harm in leaving it as-is (see email).

On a side note: it is frustrating when someone writes ">>= 2" instead of "/= 4"
when it is, by definition in the C/C++ spec, identical. But sadly, the same
cannot be said for % of signed ints versus &, which has different (slower and
less ideal) behaviour for negative numbers.

https://codereview.chromium.org/181643004/diff/40001/base/third_party/superfa...
base/third_party/superfasthash/superfasthash.c:55: data  += 2*sizeof (uint16_t);
Again, I agree, but no harm in leaving.

https://codereview.chromium.org/181643004/diff/40001/base/third_party/superfa...
base/third_party/superfasthash/superfasthash.c:63: hash ^= ((signed
char)data[sizeof (uint16_t)]) << 18;
On 2014/02/27 04:37:17, jln wrote:
> why the cast, it's already signed

The cast is actually necessary because it isn't defined whether char is signed
or unsigned (it's unsigned on ARM, apparently). (The cast was actually
introduced in http://crrev/9375011 and at some point ended up in the upstream
code -- not sure if inspired by Chromium or just by coincidence.)

See http://crbug.com/90659, particularly comment #3, where it was decided to
keep treating the last char as signed, despite the fact that all of the other
chars are treated as unsigned.

> Also, same remark with sizeof(uint16_t); this doesn't make the code more
> generic, the assumption that it's "2" is already hardwired here.

Again, I agree, but no harm in leaving.

https://codereview.chromium.org/181643004/diff/50008/base/hash.h
File base/hash.h (right):

https://codereview.chromium.org/181643004/diff/50008/base/hash.h#newcode34
base/hash.h:34: return Hash(key.data(), key.size());
I fixed the static_cast here too (by calling through the other overload of
Hash).

I've also removed the early-return if key.empty(). It seems redundant (since
SuperFastHash early-exits in this case anyway). More importantly, I think the
logic in SuperFastHash should not be duplicated here (what if we wanted to
change the hash of an empty string -- we'd have to change it in two places).

[jln (very slow on Chromium), 2014-02-27 19:02:13]

lgtm for security

https://chromiumcodereview.appspot.com/181643004/diff/40001/base/third_party/...
File base/third_party/superfasthash/superfasthash.c (right):

https://chromiumcodereview.appspot.com/181643004/diff/40001/base/third_party/...
base/third_party/superfasthash/superfasthash.c:47: rem = len & 3;
On 2014/02/27 05:25:29, Matt Giuca wrote:
> But sadly, the same
> cannot be said for % of signed ints versus &, which has different (slower and
> less ideal) behaviour for negative numbers.

Ahh, good point!

[brettw, 2014-02-27 19:19:26]

base owners lgtm, I didn't check the details.

[Matt Giuca, 2014-02-28 03:45:38]

Note: I have lgtm (via email) from legal.

[Matt Giuca, 2014-02-28 09:54:32]

The CQ bit was checked by mgiuca@chromium.org

[commit-bot: I haz the power, 2014-02-28 09:54:44]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/mgiuca@chromium.org/181643004/50008

[commit-bot: I haz the power, 2014-02-28 10:04:12]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-02-28 10:04:13]

Try jobs failed on following builders: mac_chromium_compile_dbg

[Matt Giuca, 2014-03-02 23:40:32]

It's very strange that this compile error doesn't show itself in the tests (I
re-ran the tests after adding that check, but not chrome itself). Apparently
-Wsign-compare is enabled for chrome, but not tests...

[Matt Giuca, 2014-03-03 00:01:59]

The CQ bit was checked by mgiuca@chromium.org

[commit-bot: I haz the power, 2014-03-03 00:02:13]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/mgiuca@chromium.org/181643004/90001

[commit-bot: I haz the power, 2014-03-03 01:09:23]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-03-03 01:09:24]

Retried try job too often on win_rel for step(s) app_list_unittests,
ash_unittests, aura_unittests, cacheinvalidation_unittests, cc_unittests,
check_deps, check_deps2git, chrome_elf_unittests, chromedriver_unittests,
components_unittests, compositor_unittests, content_browsertests,
content_unittests, crypto_unittests, events_unittests, gfx_unittests,
google_apis_unittests, gpu_unittests, installer_util_unittests, ipc_tests,
jingle_unittests, media_unittests, mini_installer_test, nacl_integration,
ppapi_unittests, printing_unittests, remoting_unittests, sql_unittests,
sync_integration_tests, sync_unit_tests, telemetry_perf_unittests,
telemetry_unittests, views_unittests
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=win_rel&nu...

[Matt Giuca, 2014-03-03 01:42:23]

The CQ bit was checked by mgiuca@chromium.org

[commit-bot: I haz the power, 2014-03-03 01:42:32]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/mgiuca@chromium.org/181643004/90001

[commit-bot: I haz the power, 2014-03-03 07:59:30]

Change committed as 254437

[Noel Gordon, 2014-03-04 08:39:52]

https://codereview.chromium.org/181643004/diff/90001/base/hash.h
File base/hash.h (left):

https://codereview.chromium.org/181643004/diff/90001/base/hash.h#oldcode16
base/hash.h:16: // This is the hash used on WebCore/platform/stringhash
Late to this party, but why did the reference to the Blink (nee WebCore) gets
nixed here?

Seems it's in wtf/StringHasher.g these days :
https://chromium.googlesource.com/chromium/blink/+/master/Source/wtf/StringHa...

https://codereview.chromium.org/181643004/diff/90001/base/hash.h
File base/hash.h (right):

https://codereview.chromium.org/181643004/diff/90001/base/hash.h#newcode20
base/hash.h:20: // Computes the hash of a string |key| of a given |length|.
|key| does not need
"hash of a string"?  |key| does not appear to be a string - it seems to be just
a pointer to memory.  What am I missing?

Also, the hash is computed over |length| memory bytes.  I would be an astonished
API user if null bytes caused the hash computation to exit
early.

[Matt Giuca, 2014-03-04 23:47:31]

https://codereview.chromium.org/181643004/diff/90001/base/hash.h
File base/hash.h (left):

https://codereview.chromium.org/181643004/diff/90001/base/hash.h#oldcode16
base/hash.h:16: // This is the hash used on WebCore/platform/stringhash
On 2014/03/04 08:39:52, Noel Gordon (Google) wrote:
> Late to this party, but why did the reference to the Blink (nee WebCore) gets
> nixed here?
> 
> Seems it's in wtf/StringHasher.g these days :
>
https://chromium.googlesource.com/chromium/blink/+/master/Source/wtf/StringHa...
> 

Ah, is that where it is. I did a brief search for it and didn't find it, so I
deleted this comment.

But even having found it, I don't see the point of a comment that says "this is
the hash used elsewhere".

1. It doesn't seem relevant; it's a totally separate implementation of the same
algorithm and changing one will not affect the other (so why add a "dependency"
-- if it moves again, this comment will get out of date again).

2. It's dangerous to say "it's the same as X" because they seem to have drifted
apart so far that they are now slightly different algorithms. In particular, the
upstream version used in Chromium has a special bug^H^H^Hcase where it treats
the last byte as signed rather than unsigned. (It was discussed in 2011 and
decided to keep this bug for backwards compatibility.) Whereas the Blink version
appears to have fixed this bug.

https://codereview.chromium.org/181643004/diff/90001/base/hash.h
File base/hash.h (right):

https://codereview.chromium.org/181643004/diff/90001/base/hash.h#newcode20
base/hash.h:20: // Computes the hash of a string |key| of a given |length|.
|key| does not need
On 2014/03/04 08:39:52, Noel Gordon (Google) wrote:
> "hash of a string"?  |key| does not appear to be a string - it seems to be
just
> a pointer to memory.  What am I missing?
> 
> Also, the hash is computed over |length| memory bytes.  I would be an
astonished
> API user if null bytes caused the hash computation to exit
> early.

Yeah, all correct. I was just trying to be quite clear about the behaviour but
in hindsight, maybe it would have been easier to say "hash of a block of
memory". Do you think it's worth updating this comment?

[Noel Gordon, 2014-03-05 02:05:14]

On 2014/03/04 23:47:31, Matt Giuca wrote:
 
> But even having found it, I don't see the point of a comment that says "this
is
> the hash used elsewhere".

Imagine there was a security issue with this code.  Would it be helpful to known
that some derivative of the code was used in wtf?

[Noel Gordon, 2014-03-05 02:21:17]

On 2014/03/04 23:47:31, Matt Giuca wrote:

> Yeah, all correct. I was just trying to be quite clear about the behaviour but
> in hindsight, maybe it would have been easier to say "hash of a block of
> memory". Do you think it's worth updating this comment?

Ideally, comments should be accurate/useful if we add them.  It's hard to
write good comments, in general.  I think it's worth fixing.  I'd maybe
add a unit test to show that internal null's don't matter

 "null\0 containing\0 test \0 string\0"

Anyho, thanks for doing this work.