Proposed digest hashes.

Proposed digest hashes.

[bungeman, 2013-01-08 20:10:29]

So these may not be the fastest possible implementations of MD5 and SHA1, but
they do support incremental hashing. Not sure we need or want both, but it turns
out that SHA1 can be optimized to be a bit faster that MD5, especially on x64.

[epoger, 2013-01-11 18:36:32]

Thanks for adding these, Ben!

For now, I have just reviewed the header files and unit tests... I'll examine
the cpp files in a few minutes.

Generally, I like the interfaces...

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h
File src/utils/SkMD5.h (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode14
src/utils/SkMD5.h:14: //#define SK_MD5_CLEAR_DATA
What are these here for?  Are they dials for tweaking performance later on?

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode15
src/utils/SkMD5.h:15: //#define SK_CPU_LENDIAN
Is there some reason we would set this explicitly, rather than using its
automatic setting determined at compile time?

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode26
src/utils/SkMD5.h:26: void finish(uint8_t digest[16]);
Better to define a kDigestSize constant that the caller can use to allocate
their buffer.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.h
File src/utils/SkSHA1.h (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.h#newcode14
src/utils/SkSHA1.h:14: //#define SK_SHA1_CLEAR_DATA
same questions as in SkMD5.h

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.h#newcode18
src/utils/SkSHA1.h:18: class SkSHA1 {
Should we consider making both SkMD5 and SkSHA1 extend an abstract class, given
that their interfaces are so similar?  It would be nice to be able to swap out
hash implementations...

You could add size_t getDigestLength() so that the caller would know how big of
a buffer to pass finish()...

https://codereview.appspot.com/7071055/diff/1/tests/MD5Test.cpp
File tests/MD5Test.cpp (right):

https://codereview.appspot.com/7071055/diff/1/tests/MD5Test.cpp#newcode10
tests/MD5Test.cpp:10: static bool digests_equal(const uint8_t
expectedDigest[16], const uint8_t computedDigest[16]) {
I think it would be better to use a kDigestLength constant instead of "16"
everywhere.

https://codereview.appspot.com/7071055/diff/1/tests/MD5Test.cpp#newcode24
tests/MD5Test.cpp:24: context.update((const uint8_t*)string, len);
This does not test the incremental behavior... it would be nice to know that we
got the same digest, no matter how we fed the bytes in...

1. all at once
2. 1 byte at a time
3. first N bytes, then the rest of the bytes, for N=1...8

https://codereview.appspot.com/7071055/diff/1/tests/MD5Test.cpp#newcode34
tests/MD5Test.cpp:34: { "", { 0xd4, 0x1d, 0x8c, 0xd9, 0x8f, 0x00, 0xb2, 0x04,
0xe9, 0x80, 0x09, 0x98, 0xec, 0xf8, 0x42, 0x7e } },
Do these test cases validate that our implementation yields the same results as
some reference implementation?

If so, please add a link to the reference results.

If not, please look for some to compare against.

https://codereview.appspot.com/7071055/diff/1/tests/SHA1Test.cpp
File tests/SHA1Test.cpp (right):

https://codereview.appspot.com/7071055/diff/1/tests/SHA1Test.cpp#newcode1
tests/SHA1Test.cpp:1: /*
Same comments as in MD5Test.cpp.

(And if SkMD5 and SkSHA1 shared a base class, the tests could be combined,
except for the digest values!)

[epoger, 2013-01-11 18:46:48]

Implementations look good to me!

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.cpp
File src/utils/SkMD5.cpp (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.cpp#newcode2
src/utils/SkMD5.cpp:2: * Copyright 2012 Google Inc.
2013

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.cpp#newcode7
src/utils/SkMD5.cpp:7: * The following code is based on the description in RFC
1321.
link please

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h
File src/utils/SkMD5.h (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode22
src/utils/SkMD5.h:22: /** Processes input, adding it to the digest. */
Just out of curiosity... what happens if you call update() again after finish()?

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.cpp
File src/utils/SkSHA1.cpp (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.cpp#newcode7
src/utils/SkSHA1.cpp:7: * The following code is based on the description in RFC
3174.
link please

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.cpp#newcode82
src/utils/SkSHA1.cpp:82: #if defined(SK_SHA1_CLEAR_DATA)
Maybe make this a parameter of the constructor, rather than a compile-time
switch?

[epoger, 2013-01-15 15:02:11]

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h
File src/utils/SkMD5.h (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode26
src/utils/SkMD5.h:26: void finish(uint8_t digest[16]);
On 2013/01/11 18:36:32, epoger wrote:
> Better to define a kDigestSize constant that the caller can use to allocate
> their buffer.

P.S. Just thought of this: how about providing an alternative finish() that
would return the digest as an SkString, or some other object that holds the
digest data?  That would be the easiest for callers, especially if you create a
single abstract interface class that could return digests of different lengths
(depending on hash implementation)

[bungeman, 2013-01-30 22:03:52]

I'm not really for putting a string version of the digest on this directly, as
turning a bunch of bytes into a hex string seems more general / not specific to
digests, especially since SkString::appendHex(uint32_t) exists.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.cpp
File src/utils/SkMD5.cpp (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.cpp#newcode2
src/utils/SkMD5.cpp:2: * Copyright 2012 Google Inc.
On 2013/01/11 18:46:48, epoger wrote:
> 2013

Well, I wrote this one in 2012. The ones I wrote in 2013 have 2013 on them.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.cpp#newcode7
src/utils/SkMD5.cpp:7: * The following code is based on the description in RFC
1321.
On 2013/01/11 18:46:48, epoger wrote:
> link please

Done.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h
File src/utils/SkMD5.h (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode14
src/utils/SkMD5.h:14: //#define SK_MD5_CLEAR_DATA
On 2013/01/11 18:36:32, epoger wrote:
> What are these here for?  Are they dials for tweaking performance later on?

Done.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode15
src/utils/SkMD5.h:15: //#define SK_CPU_LENDIAN
On 2013/01/11 18:36:32, epoger wrote:
> Is there some reason we would set this explicitly, rather than using its
> automatic setting determined at compile time?

Done.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode22
src/utils/SkMD5.h:22: /** Processes input, adding it to the digest. */
On 2013/01/11 18:46:48, epoger wrote:
> Just out of curiosity... what happens if you call update() again after
finish()?

Done.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode26
src/utils/SkMD5.h:26: void finish(uint8_t digest[16]);
On 2013/01/15 15:02:11, epoger wrote:
> On 2013/01/11 18:36:32, epoger wrote:
> > Better to define a kDigestSize constant that the caller can use to allocate
> > their buffer.
> 
> P.S. Just thought of this: how about providing an alternative finish() that
> would return the digest as an SkString, or some other object that holds the
> digest data?  That would be the easiest for callers, especially if you create
a
> single abstract interface class that could return digests of different lengths
> (depending on hash implementation)

Formatting the digest output is not something the MD5 implementation itself
should ever do. Having a dynamic digest length to accommodate potentially
different implementations (like Java does) means that it is not possible to keep
the digest on the stack (and the fact that this currently doesn't require heap
anywhere is rather nice). For both of these issues would be better handled by a
wrapper.

In order to handle the more common case that the top level driver knows which
driver to use (it has to create it) but wants to be able to pass it down without
stating what kind it is, this MD5 and SHA1 should implement SkWStream.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkMD5.h#newcode26
src/utils/SkMD5.h:26: void finish(uint8_t digest[16]);
On 2013/01/11 18:36:32, epoger wrote:
> Better to define a kDigestSize constant that the caller can use to allocate
> their buffer.

The issue with a 'length' is that we also want to specify uint8_t. Instead
created a Digest type. Then the length can be had from
SK_ARRAY_COUNT(SkMD5::Digest.data) and the person creating one doesn't need to
know.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.cpp
File src/utils/SkSHA1.cpp (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.cpp#newcode7
src/utils/SkSHA1.cpp:7: * The following code is based on the description in RFC
3174.
On 2013/01/11 18:46:48, epoger wrote:
> link please

Done.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.cpp#newcode82
src/utils/SkSHA1.cpp:82: #if defined(SK_SHA1_CLEAR_DATA)
On 2013/01/11 18:46:48, epoger wrote:
> Maybe make this a parameter of the constructor, rather than a compile-time
> switch?

I just put it here because if you're using this to hash 'secrets' then you
really should be clearing state. However, Skia doesn't really do 'secrets' so
it's faster to just not have the code. In other words, Skia doesn't want this
bit of code, and would never pass true for this proposed parameter to the
constructor, and the resulting field would just be wasted space. However, I
wanted to make it very obvious that we *aren't* clearing state because who knows
who might copy-paste this implementation into some other project.

tl;dr: we want a digest and don't care about 'security'

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.h
File src/utils/SkSHA1.h (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.h#newcode14
src/utils/SkSHA1.h:14: //#define SK_SHA1_CLEAR_DATA
On 2013/01/11 18:36:32, epoger wrote:
> same questions as in SkMD5.h

Done.

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.h#newcode18
src/utils/SkSHA1.h:18: class SkSHA1 {
On 2013/01/11 18:36:32, epoger wrote:
> Should we consider making both SkMD5 and SkSHA1 extend an abstract class,
given
> that their interfaces are so similar?  It would be nice to be able to swap out
> hash implementations...
> 
> You could add size_t getDigestLength() so that the caller would know how big
of
> a buffer to pass finish()...

The interfaces to the digest parts are similar on accident mostly. However, they
are similar in that they take a stream of input, so made these implement
SkWStream.

https://codereview.appspot.com/7071055/diff/1/tests/MD5Test.cpp
File tests/MD5Test.cpp (right):

https://codereview.appspot.com/7071055/diff/1/tests/MD5Test.cpp#newcode10
tests/MD5Test.cpp:10: static bool digests_equal(const uint8_t
expectedDigest[16], const uint8_t computedDigest[16]) {
On 2013/01/11 18:36:32, epoger wrote:
> I think it would be better to use a kDigestLength constant instead of "16"
> everywhere.

Done, though with 'Digest' type.

https://codereview.appspot.com/7071055/diff/1/tests/MD5Test.cpp#newcode24
tests/MD5Test.cpp:24: context.update((const uint8_t*)string, len);
On 2013/01/11 18:36:32, epoger wrote:
> This does not test the incremental behavior... it would be nice to know that
we
> got the same digest, no matter how we fed the bytes in...
> 
> 1. all at once
> 2. 1 byte at a time
> 3. first N bytes, then the rest of the bytes, for N=1...8

Got 1 and 2, but 3 seems a bit strange? The finish(Digest&) method must always
add bits to the end, so this is fairly well tested already.

https://codereview.appspot.com/7071055/diff/1/tests/MD5Test.cpp#newcode34
tests/MD5Test.cpp:34: { "", { 0xd4, 0x1d, 0x8c, 0xd9, 0x8f, 0x00, 0xb2, 0x04,
0xe9, 0x80, 0x09, 0x98, 0xec, 0xf8, 0x42, 0x7e } },
On 2013/01/11 18:36:32, epoger wrote:
> Do these test cases validate that our implementation yields the same results
as
> some reference implementation?
> 
> If so, please add a link to the reference results.
> 
> If not, please look for some to compare against.

Yes, these are the reference values from the specification. Added comment with
link.

[epoger, 2013-01-31 17:16:20]

LGTM

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.cpp
File src/utils/SkSHA1.cpp (right):

https://codereview.appspot.com/7071055/diff/1/src/utils/SkSHA1.cpp#newcode82
src/utils/SkSHA1.cpp:82: #if defined(SK_SHA1_CLEAR_DATA)
On 2013/01/30 22:03:52, bungeman wrote:
> On 2013/01/11 18:46:48, epoger wrote:
> > Maybe make this a parameter of the constructor, rather than a compile-time
> > switch?
> 
> I just put it here because if you're using this to hash 'secrets' then you
> really should be clearing state. However, Skia doesn't really do 'secrets' so
> it's faster to just not have the code. In other words, Skia doesn't want this
> bit of code, and would never pass true for this proposed parameter to the
> constructor, and the resulting field would just be wasted space. However, I
> wanted to make it very obvious that we *aren't* clearing state because who
knows
> who might copy-paste this implementation into some other project.
> 
> tl;dr: we want a digest and don't care about 'security'

Thanks for the explanation.  Seems reasonable.

[bungeman, 2013-01-31 21:50:23]

Committed revision 7496.

Warnings about newlines and unused variables fixed with revision 7500.