Make SkSHA1 and SkM5 use common SkDigestHash result type

Make SkSHA1 and SkM5 use common SkDigestHash result type

[epoger, 2013-04-15 18:21:38]

https://codereview.chromium.org/14265010/diff/1/bench/ChecksumBench.cpp
File bench/ChecksumBench.cpp (right):

https://codereview.chromium.org/14265010/diff/1/bench/ChecksumBench.cpp#newcode1
bench/ChecksumBench.cpp:1: /*
Toplevel comment: the reason for this change is: a stepping-stone for (possibly)
changing the hash algorithm used for GM image checksums, as mentioned in
https://goto.google.com/ChecksumRemainingSteps

https://codereview.chromium.org/14265010/diff/1/src/utils/SkMD5.cpp
File src/utils/SkMD5.cpp (right):

https://codereview.chromium.org/14265010/diff/1/src/utils/SkMD5.cpp#newcode83
src/utils/SkMD5.cpp:83: // TODO(epoger): eliminate the extra 16-byte copy, by
writing directly into digest.data???
Any thoughts on this?  I intend to get to work on this while awaiting review of
the rest of this change...

[epoger, 2013-04-15 19:17:03]

https://codereview.chromium.org/14265010/diff/10001/src/utils/SkHashDigest.h
File src/utils/SkHashDigest.h (right):

https://codereview.chromium.org/14265010/diff/10001/src/utils/SkHashDigest.h#...
src/utils/SkHashDigest.h:34: void copyFrom(void *data, size_t length) {
patchset 2: renamed SkHashDigest::set() to SkHashDigest::copyFrom(), to make it
clear that the SkHashDigest creates its own copy of the source bytearray.

[bungeman-skia, 2013-04-15 19:19:55]

https://codereview.chromium.org/14265010/diff/1/src/utils/SkMD5.h
File src/utils/SkMD5.h (right):

https://codereview.chromium.org/14265010/diff/1/src/utils/SkMD5.h#newcode37
src/utils/SkMD5.h:37: void finish(SkHashDigest& digest);
I see no reason for this change, and I would prefer not to burden the
implementation with a malloc and extra complexity in the case where the size is
already known. The actual content of this change shows no use case in which this
change is actually useful.

SkMD5 and SkSHA1 already implement SkWStream so there is already a common
interface for writing to the hashes (and even better no one knows they are
hashes). At creation of a hash, you have to know which one you're going to
create, so you can reserve the memory (and know the size) at that time. Then
just pass the pointer to that memory to finish and create the
SkData/SkHashDigest around that. This also alleviates the 'extra copy' issue. In
fact I see no reason at the moment to have the extra SkHashDigest type; it seems
it's possible to just use SkData directly?

[epoger, 2013-04-15 19:32:41]

https://codereview.chromium.org/14265010/diff/1/src/utils/SkMD5.h
File src/utils/SkMD5.h (right):

https://codereview.chromium.org/14265010/diff/1/src/utils/SkMD5.h#newcode37
src/utils/SkMD5.h:37: void finish(SkHashDigest& digest);
On 2013/04/15 19:19:56, bungeman1 wrote:
> I see no reason for this change, and I would prefer not to burden the
> implementation with a malloc and extra complexity in the case where the size
is
> already known. The actual content of this change shows no use case in which
this
> change is actually useful.
> 
> SkMD5 and SkSHA1 already implement SkWStream so there is already a common
> interface for writing to the hashes (and even better no one knows they are
> hashes). At creation of a hash, you have to know which one you're going to
> create, so you can reserve the memory (and know the size) at that time. Then
> just pass the pointer to that memory to finish and create the
> SkData/SkHashDigest around that. This also alleviates the 'extra copy' issue.
In
> fact I see no reason at the moment to have the extra SkHashDigest type; it
seems
> it's possible to just use SkData directly?

I meant this change as a stepping-stone to making SkBitmapHasher's API
completely unaware of which hash implementation is used by the implementation. 
Thus, callers to SkBitmapHasher could receive the benefits of new hash
implementations without changing any of their code.

I will go ahead and complete that work within this same CL, and send it back for
further review... then perhaps you can help me figure out if there is a
similarly clean way of doing it without a common SkHashDigest class.  Will you
be in the office on Wednesday?  If so, maybe we can "hash" it out in person...

[bungeman-skia, 2013-04-15 19:56:38]

On 2013/04/15 19:32:41, epoger wrote:
> https://codereview.chromium.org/14265010/diff/1/src/utils/SkMD5.h
> File src/utils/SkMD5.h (right):
> 
> https://codereview.chromium.org/14265010/diff/1/src/utils/SkMD5.h#newcode37
> src/utils/SkMD5.h:37: void finish(SkHashDigest& digest);
> On 2013/04/15 19:19:56, bungeman1 wrote:
> > I see no reason for this change, and I would prefer not to burden the
> > implementation with a malloc and extra complexity in the case where the size
> is
> > already known. The actual content of this change shows no use case in which
> this
> > change is actually useful.
> > 
> > SkMD5 and SkSHA1 already implement SkWStream so there is already a common
> > interface for writing to the hashes (and even better no one knows they are
> > hashes). At creation of a hash, you have to know which one you're going to
> > create, so you can reserve the memory (and know the size) at that time. Then
> > just pass the pointer to that memory to finish and create the
> > SkData/SkHashDigest around that. This also alleviates the 'extra copy'
issue.
> In
> > fact I see no reason at the moment to have the extra SkHashDigest type; it
> seems
> > it's possible to just use SkData directly?
> 
> I meant this change as a stepping-stone to making SkBitmapHasher's API
> completely unaware of which hash implementation is used by the implementation.

> Thus, callers to SkBitmapHasher could receive the benefits of new hash
> implementations without changing any of their code.
> 
> I will go ahead and complete that work within this same CL, and send it back
for
> further review... then perhaps you can help me figure out if there is a
> similarly clean way of doing it without a common SkHashDigest class.  Will you
> be in the office on Wednesday?  If so, maybe we can "hash" it out in person...

I'm just suggesting that the interface be something more like

static SkData* ComputeDigest(const SkBitmap& bitmap);

and that the implementation be something like 

SkData* ComputeDigest(const SkBitmap& bitmap) {
    SkImageEncoder* encoder = SkImageEncoder::Create(kRAW_Type);
    SkSHA1 context;
    encoder.encode(context, bitmap, 0);
    SkSHA1::Digest* data = (SkSHA1::Digest*)sk_malloc(sizeof(SkSHA1::Digest));
    context.finish(*digest);
    return SkData::NewFromMalloc(data, sizeof(SkSHA1::Digest));
}

where kRAW_Type is a new encode which replaces SkBitmapTransformer, which can
then be removed. No one outside ComputeDigest need know what was used to create
the hash.

[epoger, 2013-04-15 19:59:39]

On 2013/04/15 19:56:38, bungeman1 wrote:
> I'm just suggesting that the interface be something more like
> 
> static SkData* ComputeDigest(const SkBitmap& bitmap);
> 
> and that the implementation be something like 
> [...]

Thanks for the concrete suggestion!  That may well work.  Let me get the rest of
this code written, and then I'll see if I can go in that direction.

[epoger, 2013-04-18 16:39:34]

https://codereview.chromium.org/14265010/diff/14001/gm/gm_expectations.h
File gm/gm_expectations.h (right):

https://codereview.chromium.org/14265010/diff/14001/gm/gm_expectations.h#newc...
gm/gm_expectations.h:15: #include "SkHashDigest.h"
Patchset 3 is just a checkpoint... it's not time for re-review yet.

https://codereview.chromium.org/14265010/diff/14001/src/utils/SkBitmapHasher.h
File src/utils/SkBitmapHasher.h (right):

https://codereview.chromium.org/14265010/diff/14001/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.h:20: //#define BITMAP_HASH_TYPE_SkHashDigest
Patchset 3 adds code (turned off by default by preprocessor directives) to pass
around the cityhash-generated bitmap hash as an SkHashDigest instead of as a
uint64_t.

If we switch to MD5 or SHA1 instead of cityhash, we'll need to use something
bigger than a uint64_t (e.g. an SkHashDigest or SkData object) to pass the
digest around.  So, using that larger object for cityhash also will make it
easier to switch later.

https://codereview.chromium.org/14265010/diff/14001/tests/BitmapHasherTest.cpp
File tests/BitmapHasherTest.cpp (right):

https://codereview.chromium.org/14265010/diff/14001/tests/BitmapHasherTest.cp...
tests/BitmapHasherTest.cpp:48: REPORTER_ASSERT(fReporter,
actualDigest.toHexString().equals("382fb0b168dff918"));
SkHashDigest.toHexString() displays the bytes in little-endian order (bytes are
listed in the reverse order from the compiler's representation of a uint64_t, as
seen below)

[epoger, 2013-04-18 17:02:49]

https://codereview.chromium.org/14265010/diff/17002/gm/gm_expectations.h
File gm/gm_expectations.h (right):

https://codereview.chromium.org/14265010/diff/17002/gm/gm_expectations.h#newc...
gm/gm_expectations.h:16: #include "SkImageDecoder.h"
Patchset 4 and 5 are the same thing (I got an error when uploading patchset 4,
so I reran the upload as patchset 5)

Still just a checkpoint, not ready for review.

https://codereview.chromium.org/14265010/diff/17002/gm/gm_expectations.h#newc...
gm/gm_expectations.h:161: #ifdef BITMAP_HASH_TYPE_SkHashDigest
Oops, turns out that I needed this one code change when turning on
BITMAP_HASH_TYPE_SkHashDigest .

https://codereview.chromium.org/14265010/diff/17002/gm/tests/outputs/compared...
File
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt
(right):

https://codereview.chromium.org/14265010/diff/17002/gm/tests/outputs/compared...
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt:5:
"checksum" : "aad886e262610384"
Note that checksums are now recorded in little-endian hex form.

9512553915271796906 base 10
= 0x84036162E286D8AA base 16
= "aad886e262610384" when you reverse the bytes.

https://codereview.chromium.org/14265010/diff/17002/src/utils/SkBitmapHasher.h
File src/utils/SkBitmapHasher.h (right):

https://codereview.chromium.org/14265010/diff/17002/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.h:20: #define BITMAP_HASH_TYPE_SkHashDigest
flipping the switch!

[epoger, 2013-04-18 17:45:48]

OK, Ben, time for us to re-engage on this... please take a look, and ping me
sometime to arrange live discussion.

https://codereview.chromium.org/14265010/diff/36002/gm/tests/outputs/compared...
File
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt
(right):

https://codereview.chromium.org/14265010/diff/36002/gm/tests/outputs/compared...
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt:2:
"actual-results" : {
Ready for renewed discussion at patchset 8.

(Patchsets 6/7/8 are all the same--"gcl upload" failed on patchsets 6 and 7, so
I just kept retrying until it worked)

https://codereview.chromium.org/14265010/diff/36002/gm/tests/outputs/compared...
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt:5:
"checksum" : "320b5a7f0e7b69b35780e41f1b3f1937"
updated gm self-test results with MD5 digests instead of CityHash

https://codereview.chromium.org/14265010/diff/36002/src/utils/SkBitmapHasher.cpp
File src/utils/SkBitmapHasher.cpp (right):

https://codereview.chromium.org/14265010/diff/36002/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.cpp:48: SkMD5 hasher;
Here's what I like so much about the SkHashDigest wrapper: it makes it so easy
to swap out hash implementations!

The fact that the digest has a different length than it did for CityHash is
hidden away within the wrapper.  Conversions to/from hex string are handled
exactly as before.  The callers don't have to change at all...

https://codereview.chromium.org/14265010/diff/36002/tests/BitmapHasherTest.cpp
File tests/BitmapHasherTest.cpp (right):

https://codereview.chromium.org/14265010/diff/36002/tests/BitmapHasherTest.cp...
tests/BitmapHasherTest.cpp:46: REPORTER_ASSERT(fReporter,
expectedDigest.copyFromHexString("87ef6627560329fb8a2439ee7023e027"));
replacing expected hash digest values in the unit tests... but note that no code
changes are needed to deal with the change in digest size.

[epoger, 2013-04-18 18:07:13]

https://codereview.chromium.org/14265010/diff/36002/gm/gm_expectations.h
File gm/gm_expectations.h (right):

https://codereview.chromium.org/14265010/diff/36002/gm/gm_expectations.h#newc...
gm/gm_expectations.h:58: return Json::Value(checksum.toHexString().c_str());
If this code got the hash digest back as an SkData instead of as an
SkHashDigest, it would need its own code to convert between hex string and the
raw data.  I think it's handy that SkHashDigest provides that...

https://codereview.chromium.org/14265010/diff/36002/gm/gmmain.cpp
File gm/gmmain.cpp (right):

https://codereview.chromium.org/14265010/diff/36002/gm/gmmain.cpp#newcode718
gm/gmmain.cpp:718: if (!SkBitmapHasher::ComputeDigest(actualBitmap,
&actualBitmapHash)) {
Unlike SkData objects, SkHashDigest objects are mutable.  That allows
ComputeDigest() to "fill in" the result in the &actualBitmapHash parameter, and
return the "success" boolean separately.

If ComputeDigest() returned its results as an SkData object, I guess it would
return that SkData object instead of a bool... but then, how would it signal
errors?  Maybe by returning an empty SkData object?  Or returning SkData *
instead of SkData, and NULL in case of an error?

I guess those approaches would work... any thoughts on what might be preferable?

https://codereview.chromium.org/14265010/diff/36002/gm/tests/outputs/compared...
File
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt
(right):

https://codereview.chromium.org/14265010/diff/36002/gm/tests/outputs/compared...
gm/tests/outputs/compared-against-different-pixels-images/output-expected/json-summary.txt:2:
"actual-results" : {
On 2013/04/18 17:45:48, epoger wrote:
> Ready for renewed discussion at patchset 8.

I should have made this clearer: please see the diffs between patchset 5 and
patchset 8.  That set of changes just switched the hashing algorithm used "under
the covers" in SkBitmapHasher.cpp.

It it my view that the simplicity of switching algorithms justifies the
existence of the SkHashDigest class, or perhaps some different wrapper around
the hash results.  If so, we can then examine the totality of this CL and look
for cleanups...

[epoger, 2013-04-19 17:20:53]

https://codereview.chromium.org/14265010/diff/53019/src/utils/SkBitmapHasher.cpp
File src/utils/SkBitmapHasher.cpp (right):

https://codereview.chromium.org/14265010/diff/53019/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.cpp:3: * Copyright 2012 Google Inc.
Patchsets 9, 10, and 11 are all identical... "gcl upload" failed the first two
times.  Again.

https://codereview.chromium.org/14265010/diff/53019/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.cpp:50: SkMD5::Digest digest;
In patchset 11, I have reverted all changes to SkMD5 and SkSHA1 code.

Instead, similar to Ben's suggestion in
https://codereview.chromium.org/14265010/#msg5 , I leave the SkMD5 interface
as-is and now SkBitmapHasher.cpp wraps its result in an SkHashDigest object.

For now, there is still an extra copy of the hash digest created on the stack
here in SkBitmapHasher::ComputeDigestInternal(); I'll see if I can eliminate
that with a malloc here.  But for now, I wanted to make as simple a change as
possible that would revert the changes to SkMD5 and SkSHA1.

Ben... do you think I'm on the right track here?

[bungeman-skia, 2013-04-19 20:18:02]

> Ben... do you think I'm on the right track here?

This is looking better, see https://codereview.chromium.org/14267031/ for what I
had in mind.

[epoger, 2013-04-21 10:54:57]

https://codereview.chromium.org/14265010/diff/12005/src/utils/SkBitmapHasher.cpp
File src/utils/SkBitmapHasher.cpp (right):

https://codereview.chromium.org/14265010/diff/12005/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.cpp:38: // Add all the pixel data, one transformed row
at a time.
Patchset 12: when generating an MD5 digest, call hasher.update() with one row of
pixels at a time.


Basically, instead of:

buffer = malloc(entire_bitmap_size)
transformer.copyBitmapToPixelBuffer(buffer)
hasher.update(buffer)

This now does:

buffer = malloc(one_row)
for (each row) {
  transformer.copyRowToPixelBuffer(buffer)
  hasher.update(buffer)
}


It still copies/transforms all pixels of the bitmap (which we have to do in
order to rearrange bits within the pixel representation), but at least now it
doesn't have to malloc a giant buffer (which I would think could be more of a
strain on constrained platforms).

https://codereview.chromium.org/14265010/diff/12005/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.cpp:43: if (!transformer.copyRowToPixelBuffer(row,
buffer, rowBufferSize)) {
Ah, now I better see the value of Ben's 
https://codereview.chromium.org/14267031/ ('ARGB image encoder for checksums.') 
That would make this part of the code cleaner.

[epoger, 2013-04-22 01:22:28]

There is a good chance that I won't be committing this change at all, because
the performance seems significantly worse with MD5 than with CityHash.  I've
captured some performance numbers here:
https://code.google.com/p/skia/issues/detail?id=1257 ('deciding between
CityHash, MD5, and SHA1 for image hash algorithm')

Ben, please take a look at that bug, and let me know what you think.

[bungeman-skia, 2013-04-22 05:14:02]

Back of the envelope... 2000 tests, 4MB (1000*1000*4) for each is ~10GB of
output. MD5 normally goes at 100-400MB/s so somewhere on the rough order of
25-100 seconds. Seeing that 2000MB/s is (I think) about the best that cityhash
can get, it should already be using on the order of 5-15s given our timings. As
a result, the slowdown you're seeing seems a bit high, though perhaps not
incredibly outlandish. However, there are some differences in the code paths...

https://codereview.chromium.org/14265010/diff/12005/src/utils/SkBitmapHasher.cpp
File src/utils/SkBitmapHasher.cpp (right):

https://codereview.chromium.org/14265010/diff/12005/src/utils/SkBitmapHasher....
src/utils/SkBitmapHasher.cpp:43: if (!transformer.copyRowToPixelBuffer(row,
buffer, rowBufferSize)) {
On 2013/04/21 10:54:57, epoger wrote:
> Ah, now I better see the value of Ben's 
> https://codereview.chromium.org/14267031/ ('ARGB image encoder for
checksums.') 
> That would make this part of the code cleaner.

More importantly (I think), it pulls the bitmap lock/unlock cleanly out of this
loop.

https://codereview.chromium.org/14265010/diff/12005/src/utils/SkBitmapTransfo...
File src/utils/SkBitmapTransformer.cpp (right):

https://codereview.chromium.org/14265010/diff/12005/src/utils/SkBitmapTransfo...
src/utils/SkBitmapTransformer.cpp:105: fBitmap.lockPixels();
This isn't cheap as it involves taking a mutex, as does the unlock. This is also
taken care of with the ARGB encoder as it just does the one lock/unlock. If you
take this lock/unlock out of here and push it up to just one lock/unlock in the
hasher, what does that do?

[epoger, 2013-04-23 15:07:36]

Once Ben commits https://codereview.chromium.org/14267031/ ('ARGB image encoder
for checksums.'), and we've confirmed that it does not significantly degrade
performance, I will refresh this CL to include that change, and make the
following other changes:

1. make sure that I'm calling the MD5 and Cityhash encoders as efficiently as
possible
2. disable GM's writePath option, so that the GenerateGMs step doesn't write out
actual image files (which will be more in line with the eventual operation in
checksum-land)

and then try MD5 and Cityhash again on the NexusS trybot.

[epoger, 2013-04-24 18:25:09]

Closing in favor of newer https://codereview.chromium.org/14054012/ ('Assess
performance impact of using 64-bit-truncated MD5 instead of 64-bit CityHash')