diff options
author | bungeman@google.com <bungeman@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2013-01-31 19:47:48 +0000 |
---|---|---|
committer | bungeman@google.com <bungeman@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2013-01-31 19:47:48 +0000 |
commit | cfcb1bef94a8cfb565d9450b38f57d4f5c83790a (patch) | |
tree | 8b6aeb7ace8795f02d39ba02c39ebd0a21a5c1c5 | |
parent | cb9b4a5ce66abdd8b3fca48769744e63422099f7 (diff) |
Add SHA1 and MD5 to utils.
https://codereview.appspot.com/7071055/
git-svn-id: http://skia.googlecode.com/svn/trunk@7496 2bbb7eff-a529-9590-31e7-b0007b416f81
-rw-r--r-- | bench/ChecksumBench.cpp | 68 | ||||
-rw-r--r-- | gyp/bench.gyp | 1 | ||||
-rw-r--r-- | gyp/tests.gyp | 2 | ||||
-rw-r--r-- | gyp/utils.gyp | 4 | ||||
-rw-r--r-- | src/utils/SkMD5.cpp | 252 | ||||
-rw-r--r-- | src/utils/SkMD5.h | 54 | ||||
-rw-r--r-- | src/utils/SkSHA1.cpp | 268 | ||||
-rw-r--r-- | src/utils/SkSHA1.h | 54 | ||||
-rw-r--r-- | tests/MD5Test.cpp | 68 | ||||
-rw-r--r-- | tests/SHA1Test.cpp | 55 |
10 files changed, 821 insertions, 5 deletions
diff --git a/bench/ChecksumBench.cpp b/bench/ChecksumBench.cpp index 31160c7ad0..2d0b542f7c 100644 --- a/bench/ChecksumBench.cpp +++ b/bench/ChecksumBench.cpp @@ -7,7 +7,18 @@ #include "SkBenchmark.h" #include "SkCanvas.h" #include "SkChecksum.h" +#include "SkCityHash.h" +#include "SkMD5.h" #include "SkRandom.h" +#include "SkSHA1.h" + +enum ChecksumType { + kChecksum_ChecksumType, + kMD5_ChecksumType, + kSHA1_ChecksumType, + kCityHash32, + kCityHash64 +}; class ComputeChecksumBench : public SkBenchmark { enum { @@ -16,9 +27,10 @@ class ComputeChecksumBench : public SkBenchmark { N = SkBENCHLOOP(100000), }; uint32_t fData[U32COUNT]; + ChecksumType fType; public: - ComputeChecksumBench(void* param) : INHERITED(param) { + ComputeChecksumBench(void* param, ChecksumType type) : INHERITED(param), fType(type) { SkRandom rand; for (int i = 0; i < U32COUNT; ++i) { fData[i] = rand.nextU(); @@ -28,13 +40,51 @@ public: protected: virtual const char* onGetName() { - return "compute_checksum"; + switch (fType) { + case kChecksum_ChecksumType: return "compute_checksum"; + case kMD5_ChecksumType: return "compute_md5"; + case kSHA1_ChecksumType: return "compute_sha1"; + case kCityHash32: return "compute_cityhash32"; + case kCityHash64: return "compute_cityhash64"; + default: SK_CRASH(); return ""; + } } virtual void onDraw(SkCanvas* canvas) { - for (int i = 0; i < N; i++) { - (void) SkChecksum::Compute(fData, sizeof(fData)); + switch (fType) { + case kChecksum_ChecksumType: { + for (int i = 0; i < N; i++) { + volatile uint32_t result = SkChecksum::Compute(fData, sizeof(fData)); + } + } break; + case kMD5_ChecksumType: { + for (int i = 0; i < N; i++) { + SkMD5 md5; + md5.update(reinterpret_cast<uint8_t*>(fData), sizeof(fData)); + SkMD5::Digest digest; + md5.finish(digest); + } + } break; + case kSHA1_ChecksumType: { + for (int i = 0; i < N; i++) { + SkSHA1 sha1; + sha1.update(reinterpret_cast<uint8_t*>(fData), sizeof(fData)); + SkSHA1::Digest digest; + sha1.finish(digest); + } + } break; + case kCityHash32: { + for (int i = 0; i < N; i++) { + volatile uint32_t result = SkCityHash::Compute32(reinterpret_cast<char*>(fData), sizeof(fData)); + } + } break; + case kCityHash64: { + for (int i = 0; i < N; i++) { + volatile uint64_t result = SkCityHash::Compute64(reinterpret_cast<char*>(fData), sizeof(fData)); + } + } break; } + } private: @@ -43,6 +93,14 @@ private: /////////////////////////////////////////////////////////////////////////////// -static SkBenchmark* Fact0(void* p) { return new ComputeChecksumBench(p); } +static SkBenchmark* Fact0(void* p) { return new ComputeChecksumBench(p, kChecksum_ChecksumType); } +static SkBenchmark* Fact1(void* p) { return new ComputeChecksumBench(p, kMD5_ChecksumType); } +static SkBenchmark* Fact2(void* p) { return new ComputeChecksumBench(p, kSHA1_ChecksumType); } +static SkBenchmark* Fact3(void* p) { return new ComputeChecksumBench(p, kCityHash32); } +static SkBenchmark* Fact4(void* p) { return new ComputeChecksumBench(p, kCityHash64); } static BenchRegistry gReg0(Fact0); +static BenchRegistry gReg1(Fact1); +static BenchRegistry gReg2(Fact2); +static BenchRegistry gReg3(Fact3); +static BenchRegistry gReg4(Fact4); diff --git a/gyp/bench.gyp b/gyp/bench.gyp index 9690f32aec..be768f04ae 100644 --- a/gyp/bench.gyp +++ b/gyp/bench.gyp @@ -11,6 +11,7 @@ 'include_dirs' : [ '../src/core', '../src/effects', + '../src/utils', ], 'includes': [ 'bench.gypi' diff --git a/gyp/tests.gyp b/gyp/tests.gyp index 066435caf6..10e99d274d 100644 --- a/gyp/tests.gyp +++ b/gyp/tests.gyp @@ -58,6 +58,7 @@ '../tests/HashCacheTest.cpp', '../tests/InfRectTest.cpp', '../tests/LListTest.cpp', + '../tests/MD5Test.cpp', '../tests/MathTest.cpp', '../tests/MatrixTest.cpp', '../tests/Matrix44Test.cpp', @@ -84,6 +85,7 @@ '../tests/RegionTest.cpp', '../tests/RoundRectTest.cpp', '../tests/RTreeTest.cpp', + '../tests/SHA1Test.cpp', '../tests/ScalarTest.cpp', '../tests/ShaderOpacityTest.cpp', '../tests/Sk64Test.cpp', diff --git a/gyp/utils.gyp b/gyp/utils.gyp index b4469ba1de..c62657de7b 100644 --- a/gyp/utils.gyp +++ b/gyp/utils.gyp @@ -74,6 +74,8 @@ '../src/utils/SkInterpolator.cpp', '../src/utils/SkLayer.cpp', '../src/utils/SkMatrix44.cpp', + '../src/utils/SkMD5.cpp', + '../src/utils/SkMD5.h', '../src/utils/SkMeshUtils.cpp', '../src/utils/SkNinePatch.cpp', '../src/utils/SkNWayCanvas.cpp', @@ -84,6 +86,8 @@ '../src/utils/SkParsePath.cpp', '../src/utils/SkPictureUtils.cpp', '../src/utils/SkProxyCanvas.cpp', + '../src/utils/SkSHA1.cpp', + '../src/utils/SkSHA1.h', '../src/utils/SkRTConf.cpp', '../src/utils/SkThreadUtils.h', '../src/utils/SkThreadUtils_pthread.cpp', diff --git a/src/utils/SkMD5.cpp b/src/utils/SkMD5.cpp new file mode 100644 index 0000000000..725ae55f3f --- /dev/null +++ b/src/utils/SkMD5.cpp @@ -0,0 +1,252 @@ +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + * + * The following code is based on the description in RFC 1321. + * http://www.ietf.org/rfc/rfc1321.txt + */ + +#include "SkTypes.h" +#include "SkMD5.h" +#include <string.h> + +/** MD5 basic transformation. Transforms state based on block. */ +static void transform(uint32_t state[4], const uint8_t block[64]); + +/** Encodes input into output (4 little endian 32 bit values). */ +static void encode(uint8_t output[16], const uint32_t input[4]); + +/** Encodes input into output (little endian 64 bit value). */ +static void encode(uint8_t output[8], const uint64_t input); + +/** Decodes input (4 little endian 32 bit values) into storage, if required. */ +static const uint32_t* decode(uint32_t storage[16], const uint8_t input[64]); + +SkMD5::SkMD5() : byteCount(0) { + // These are magic numbers from the specification. + this->state[0] = 0x67452301; + this->state[1] = 0xefcdab89; + this->state[2] = 0x98badcfe; + this->state[3] = 0x10325476; +} + +void SkMD5::update(const uint8_t* input, size_t inputLength) { + unsigned int bufferIndex = (unsigned int)(this->byteCount & 0x3F); + unsigned int bufferAvailable = 64 - bufferIndex; + + unsigned int inputIndex; + if (inputLength >= bufferAvailable) { + if (bufferIndex) { + memcpy(&this->buffer[bufferIndex], input, bufferAvailable); + transform(this->state, this->buffer); + inputIndex = bufferAvailable; + } else { + inputIndex = 0; + } + + for (; inputIndex + 63 < inputLength; inputIndex += 64) { + transform(this->state, &input[inputIndex]); + } + + bufferIndex = 0; + } else { + inputIndex = 0; + } + + memcpy(&this->buffer[bufferIndex], &input[inputIndex], inputLength - inputIndex); + + this->byteCount += inputLength; +} + +void SkMD5::finish(Digest& digest) { + // Get the number of bits before padding. + uint8_t bits[8]; + encode(bits, this->byteCount << 3); + + // Pad out to 56 mod 64. + unsigned int bufferIndex = (unsigned int)(this->byteCount & 0x3F); + unsigned int paddingLength = (bufferIndex < 56) ? (56 - bufferIndex) : (120 - bufferIndex); + static uint8_t PADDING[64] = { + 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + }; + this->update(PADDING, paddingLength); + + // Append length (length before padding, will cause final update). + this->update(bits, 8); + + // Write out digest. + encode(digest.data, this->state); + +#if defined(SK_MD5_CLEAR_DATA) + // Clear state. + memset(this, 0, sizeof(*this)); +#endif +} + +struct F { uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) { + //return (x & y) | ((~x) & z); + return ((y ^ z) & x) ^ z; //equivelent but faster +}}; + +struct G { uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) { + return (x & z) | (y & (~z)); + //return ((x ^ y) & z) ^ y; //equivelent but slower +}}; + +struct H { uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) { + return x ^ y ^ z; +}}; + +struct I { uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) { + return y ^ (x | (~z)); +}}; + +/** Rotates x left n bits. */ +static inline uint32_t rotate_left(uint32_t x, uint8_t n) { + return (x << n) | (x >> (32 - n)); +} + +template <typename T> +static inline void operation(T operation, uint32_t& a, uint32_t b, uint32_t c, uint32_t d, + uint32_t x, uint8_t s, uint32_t t) { + a = b + rotate_left(a + operation(b, c, d) + x + t, s); +} + +static void transform(uint32_t state[4], const uint8_t block[64]) { + uint32_t a = state[0], b = state[1], c = state[2], d = state[3]; + + uint32_t storage[16]; + const uint32_t* X = decode(storage, block); + + // Round 1 + operation(F(), a, b, c, d, X[ 0], 7, 0xd76aa478); // 1 + operation(F(), d, a, b, c, X[ 1], 12, 0xe8c7b756); // 2 + operation(F(), c, d, a, b, X[ 2], 17, 0x242070db); // 3 + operation(F(), b, c, d, a, X[ 3], 22, 0xc1bdceee); // 4 + operation(F(), a, b, c, d, X[ 4], 7, 0xf57c0faf); // 5 + operation(F(), d, a, b, c, X[ 5], 12, 0x4787c62a); // 6 + operation(F(), c, d, a, b, X[ 6], 17, 0xa8304613); // 7 + operation(F(), b, c, d, a, X[ 7], 22, 0xfd469501); // 8 + operation(F(), a, b, c, d, X[ 8], 7, 0x698098d8); // 9 + operation(F(), d, a, b, c, X[ 9], 12, 0x8b44f7af); // 10 + operation(F(), c, d, a, b, X[10], 17, 0xffff5bb1); // 11 + operation(F(), b, c, d, a, X[11], 22, 0x895cd7be); // 12 + operation(F(), a, b, c, d, X[12], 7, 0x6b901122); // 13 + operation(F(), d, a, b, c, X[13], 12, 0xfd987193); // 14 + operation(F(), c, d, a, b, X[14], 17, 0xa679438e); // 15 + operation(F(), b, c, d, a, X[15], 22, 0x49b40821); // 16 + + // Round 2 + operation(G(), a, b, c, d, X[ 1], 5, 0xf61e2562); // 17 + operation(G(), d, a, b, c, X[ 6], 9, 0xc040b340); // 18 + operation(G(), c, d, a, b, X[11], 14, 0x265e5a51); // 19 + operation(G(), b, c, d, a, X[ 0], 20, 0xe9b6c7aa); // 20 + operation(G(), a, b, c, d, X[ 5], 5, 0xd62f105d); // 21 + operation(G(), d, a, b, c, X[10], 9, 0x2441453); // 22 + operation(G(), c, d, a, b, X[15], 14, 0xd8a1e681); // 23 + operation(G(), b, c, d, a, X[ 4], 20, 0xe7d3fbc8); // 24 + operation(G(), a, b, c, d, X[ 9], 5, 0x21e1cde6); // 25 + operation(G(), d, a, b, c, X[14], 9, 0xc33707d6); // 26 + operation(G(), c, d, a, b, X[ 3], 14, 0xf4d50d87); // 27 + operation(G(), b, c, d, a, X[ 8], 20, 0x455a14ed); // 28 + operation(G(), a, b, c, d, X[13], 5, 0xa9e3e905); // 29 + operation(G(), d, a, b, c, X[ 2], 9, 0xfcefa3f8); // 30 + operation(G(), c, d, a, b, X[ 7], 14, 0x676f02d9); // 31 + operation(G(), b, c, d, a, X[12], 20, 0x8d2a4c8a); // 32 + + // Round 3 + operation(H(), a, b, c, d, X[ 5], 4, 0xfffa3942); // 33 + operation(H(), d, a, b, c, X[ 8], 11, 0x8771f681); // 34 + operation(H(), c, d, a, b, X[11], 16, 0x6d9d6122); // 35 + operation(H(), b, c, d, a, X[14], 23, 0xfde5380c); // 36 + operation(H(), a, b, c, d, X[ 1], 4, 0xa4beea44); // 37 + operation(H(), d, a, b, c, X[ 4], 11, 0x4bdecfa9); // 38 + operation(H(), c, d, a, b, X[ 7], 16, 0xf6bb4b60); // 39 + operation(H(), b, c, d, a, X[10], 23, 0xbebfbc70); // 40 + operation(H(), a, b, c, d, X[13], 4, 0x289b7ec6); // 41 + operation(H(), d, a, b, c, X[ 0], 11, 0xeaa127fa); // 42 + operation(H(), c, d, a, b, X[ 3], 16, 0xd4ef3085); // 43 + operation(H(), b, c, d, a, X[ 6], 23, 0x4881d05); // 44 + operation(H(), a, b, c, d, X[ 9], 4, 0xd9d4d039); // 45 + operation(H(), d, a, b, c, X[12], 11, 0xe6db99e5); // 46 + operation(H(), c, d, a, b, X[15], 16, 0x1fa27cf8); // 47 + operation(H(), b, c, d, a, X[ 2], 23, 0xc4ac5665); // 48 + + // Round 4 + operation(I(), a, b, c, d, X[ 0], 6, 0xf4292244); // 49 + operation(I(), d, a, b, c, X[ 7], 10, 0x432aff97); // 50 + operation(I(), c, d, a, b, X[14], 15, 0xab9423a7); // 51 + operation(I(), b, c, d, a, X[ 5], 21, 0xfc93a039); // 52 + operation(I(), a, b, c, d, X[12], 6, 0x655b59c3); // 53 + operation(I(), d, a, b, c, X[ 3], 10, 0x8f0ccc92); // 54 + operation(I(), c, d, a, b, X[10], 15, 0xffeff47d); // 55 + operation(I(), b, c, d, a, X[ 1], 21, 0x85845dd1); // 56 + operation(I(), a, b, c, d, X[ 8], 6, 0x6fa87e4f); // 57 + operation(I(), d, a, b, c, X[15], 10, 0xfe2ce6e0); // 58 + operation(I(), c, d, a, b, X[ 6], 15, 0xa3014314); // 59 + operation(I(), b, c, d, a, X[13], 21, 0x4e0811a1); // 60 + operation(I(), a, b, c, d, X[ 4], 6, 0xf7537e82); // 61 + operation(I(), d, a, b, c, X[11], 10, 0xbd3af235); // 62 + operation(I(), c, d, a, b, X[ 2], 15, 0x2ad7d2bb); // 63 + operation(I(), b, c, d, a, X[ 9], 21, 0xeb86d391); // 64 + + state[0] += a; + state[1] += b; + state[2] += c; + state[3] += d; + +#if defined(SK_MD5_CLEAR_DATA) + // Clear sensitive information. + if (X == &storage) { + memset(storage, 0, sizeof(storage)); + } +#endif +} + +static void encode(uint8_t output[16], const uint32_t input[4]) { + for (size_t i = 0, j = 0; i < 4; i++, j += 4) { + output[j ] = (uint8_t) (input[i] & 0xff); + output[j+1] = (uint8_t)((input[i] >> 8) & 0xff); + output[j+2] = (uint8_t)((input[i] >> 16) & 0xff); + output[j+3] = (uint8_t)((input[i] >> 24) & 0xff); + } +} + +static void encode(uint8_t output[8], const uint64_t input) { + output[0] = (uint8_t) (input & 0xff); + output[1] = (uint8_t)((input >> 8) & 0xff); + output[2] = (uint8_t)((input >> 16) & 0xff); + output[3] = (uint8_t)((input >> 24) & 0xff); + output[4] = (uint8_t)((input >> 32) & 0xff); + output[5] = (uint8_t)((input >> 40) & 0xff); + output[6] = (uint8_t)((input >> 48) & 0xff); + output[7] = (uint8_t)((input >> 56) & 0xff); +} + +static inline bool is_aligned(const void *pointer, size_t byte_count) { + return reinterpret_cast<uintptr_t>(pointer) % byte_count == 0; +} + +static const uint32_t* decode(uint32_t storage[16], const uint8_t input[64]) { +#if defined(SK_CPU_LENDIAN) && defined(SK_CPU_FAST_UNALIGNED_ACCESS) + return reinterpret_cast<const uint32_t*>(input); +#else +#if defined(SK_CPU_LENDIAN) + if (is_aligned(input, 4)) { + return reinterpret_cast<const uint32_t*>(input); + } +#endif + for (size_t i = 0, j = 0; j < 64; i++, j += 4) { + storage[i] = ((uint32_t)input[j ]) | + (((uint32_t)input[j+1]) << 8) | + (((uint32_t)input[j+2]) << 16) | + (((uint32_t)input[j+3]) << 24); + } + return storage; +#endif +} diff --git a/src/utils/SkMD5.h b/src/utils/SkMD5.h new file mode 100644 index 0000000000..23119e897c --- /dev/null +++ b/src/utils/SkMD5.h @@ -0,0 +1,54 @@ +/* + * Copyright 2012 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkMD5_DEFINED +#define SkMD5_DEFINED + +#include "SkTypes.h" +#include "SkEndian.h" +#include "SkStream.h" + +//The following macros can be defined to affect the MD5 code generated. +//SK_MD5_CLEAR_DATA causes all intermediate state to be overwritten with 0's. +//SK_CPU_LENDIAN allows 32 bit <=> 8 bit conversions without copies (if alligned). +//SK_CPU_FAST_UNALIGNED_ACCESS allows 32 bit <=> 8 bit conversions without copies if SK_CPU_LENDIAN. + +class SkMD5 : SkWStream { +public: + SkMD5(); + + /** Processes input, adding it to the digest. + * Note that this treats the buffer as a series of uint8_t values. + */ + virtual bool write(const void* buffer, size_t size) SK_OVERRIDE { + update(reinterpret_cast<const uint8_t*>(buffer), size); + return true; + } + + /** Processes input, adding it to the digest. Calling this after finish is undefined. */ + void update(const uint8_t* input, size_t length); + + struct Digest { + uint8_t data[16]; + }; + + /** Computes and returns the digest. */ + void finish(Digest& digest); + +private: + // number of bytes, modulo 2^64 + uint64_t byteCount; + + // state (ABCD) + uint32_t state[4]; + + // input buffer + uint8_t buffer[64]; +}; + +#endif + diff --git a/src/utils/SkSHA1.cpp b/src/utils/SkSHA1.cpp new file mode 100644 index 0000000000..1abac0640e --- /dev/null +++ b/src/utils/SkSHA1.cpp @@ -0,0 +1,268 @@ +/* + * Copyright 2013 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + * + * The following code is based on the description in RFC 3174. + * http://www.ietf.org/rfc/rfc3174.txt + */ + +#include "SkTypes.h" +#include "SkSHA1.h" +#include <string.h> + +/** SHA1 basic transformation. Transforms state based on block. */ +static void transform(uint32_t state[5], const uint8_t block[64]); + +/** Encodes input into output (5 big endian 32 bit values). */ +static void encode(uint8_t output[20], const uint32_t input[5]); + +/** Encodes input into output (big endian 64 bit value). */ +static void encode(uint8_t output[8], const uint64_t input); + +SkSHA1::SkSHA1() : byteCount(0) { + // These are magic numbers from the specification. The first four are the same as MD5. + this->state[0] = 0x67452301; + this->state[1] = 0xefcdab89; + this->state[2] = 0x98badcfe; + this->state[3] = 0x10325476; + this->state[4] = 0xc3d2e1f0; +} + +void SkSHA1::update(const uint8_t* input, size_t inputLength) { + unsigned int bufferIndex = (unsigned int)(this->byteCount & 0x3F); + unsigned int bufferAvailable = 64 - bufferIndex; + + unsigned int inputIndex; + if (inputLength >= bufferAvailable) { + if (bufferIndex) { + memcpy(&this->buffer[bufferIndex], input, bufferAvailable); + transform(this->state, this->buffer); + inputIndex = bufferAvailable; + } else { + inputIndex = 0; + } + + for (; inputIndex + 63 < inputLength; inputIndex += 64) { + transform(this->state, &input[inputIndex]); + } + + bufferIndex = 0; + } else { + inputIndex = 0; + } + + memcpy(&this->buffer[bufferIndex], &input[inputIndex], inputLength - inputIndex); + + this->byteCount += inputLength; +} + +void SkSHA1::finish(Digest& digest) { + // Get the number of bits before padding. + uint8_t bits[8]; + encode(bits, this->byteCount << 3); + + // Pad out to 56 mod 64. + unsigned int bufferIndex = (unsigned int)(this->byteCount & 0x3F); + unsigned int paddingLength = (bufferIndex < 56) ? (56 - bufferIndex) : (120 - bufferIndex); + static uint8_t PADDING[64] = { + 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + }; + this->update(PADDING, paddingLength); + + // Append length (length before padding, will cause final update). + this->update(bits, 8); + + // Write out digest. + encode(digest.data, this->state); + +#if defined(SK_SHA1_CLEAR_DATA) + // Clear state. + memset(this, 0, sizeof(*this)); +#endif +} + +struct F1 { uint32_t operator()(uint32_t B, uint32_t C, uint32_t D) { + return (B & C) | ((~B) & D); + //return D ^ (B & (C ^ D)); + //return (B & C) ^ ((~B) & D); + //return (B & C) + ((~B) & D); + //return _mm_or_ps(_mm_andnot_ps(B, D), _mm_and_ps(B, C)); //SSE2 + //return vec_sel(D, C, B); //PPC +}}; + +struct F2 { uint32_t operator()(uint32_t B, uint32_t C, uint32_t D) { + return B ^ C ^ D; +}}; + +struct F3 { uint32_t operator()(uint32_t B, uint32_t C, uint32_t D) { + return (B & C) | (B & D) | (C & D); + //return (B & C) | (D & (B | C)); + //return (B & C) | (D & (B ^ C)); + //return (B & C) + (D & (B ^ C)); + //return (B & C) ^ (B & D) ^ (C & D); +}}; + +/** Rotates x left n bits. */ +static inline uint32_t rotate_left(uint32_t x, uint8_t n) { + return (x << n) | (x >> (32 - n)); +} + +template <typename T> +static inline void operation(T operation, + uint32_t A, uint32_t& B, uint32_t C, uint32_t D, uint32_t& E, + uint32_t w, uint32_t k) { + E += rotate_left(A, 5) + operation(B, C, D) + w + k; + B = rotate_left(B, 30); +} + +static void transform(uint32_t state[5], const uint8_t block[64]) { + uint32_t A = state[0], B = state[1], C = state[2], D = state[3], E = state[4]; + + // Round constants defined in SHA-1. + static const uint32_t K[] = { + 0x5A827999, //sqrt(2) * 2^30 + 0x6ED9EBA1, //sqrt(3) * 2^30 + 0x8F1BBCDC, //sqrt(5) * 2^30 + 0xCA62C1D6, //sqrt(10) * 2^30 + }; + + uint32_t W[80]; + + // Initialize the array W. + size_t i = 0; + for (size_t j = 0; i < 16; ++i, j += 4) { + W[i] = (((uint32_t)block[j ]) << 24) | + (((uint32_t)block[j+1]) << 16) | + (((uint32_t)block[j+2]) << 8) | + (((uint32_t)block[j+3]) ); + } + for (; i < 80; ++i) { + W[i] = rotate_left(W[i-3] ^ W[i-8] ^ W[i-14] ^ W[i-16], 1); + //The following is equivelent and speeds up SSE implementations, but slows non-SSE. + //W[i] = rotate_left(W[i-6] ^ W[i-16] ^ W[i-28] ^ W[i-32], 2); + } + + // Round 1 + operation(F1(), A, B, C, D, E, W[ 0], K[0]); + operation(F1(), E, A, B, C, D, W[ 1], K[0]); + operation(F1(), D, E, A, B, C, W[ 2], K[0]); + operation(F1(), C, D, E, A, B, W[ 3], K[0]); + operation(F1(), B, C, D, E, A, W[ 4], K[0]); + operation(F1(), A, B, C, D, E, W[ 5], K[0]); + operation(F1(), E, A, B, C, D, W[ 6], K[0]); + operation(F1(), D, E, A, B, C, W[ 7], K[0]); + operation(F1(), C, D, E, A, B, W[ 8], K[0]); + operation(F1(), B, C, D, E, A, W[ 9], K[0]); + operation(F1(), A, B, C, D, E, W[10], K[0]); + operation(F1(), E, A, B, C, D, W[11], K[0]); + operation(F1(), D, E, A, B, C, W[12], K[0]); + operation(F1(), C, D, E, A, B, W[13], K[0]); + operation(F1(), B, C, D, E, A, W[14], K[0]); + operation(F1(), A, B, C, D, E, W[15], K[0]); + operation(F1(), E, A, B, C, D, W[16], K[0]); + operation(F1(), D, E, A, B, C, W[17], K[0]); + operation(F1(), C, D, E, A, B, W[18], K[0]); + operation(F1(), B, C, D, E, A, W[19], K[0]); + + // Round 2 + operation(F2(), A, B, C, D, E, W[20], K[1]); + operation(F2(), E, A, B, C, D, W[21], K[1]); + operation(F2(), D, E, A, B, C, W[22], K[1]); + operation(F2(), C, D, E, A, B, W[23], K[1]); + operation(F2(), B, C, D, E, A, W[24], K[1]); + operation(F2(), A, B, C, D, E, W[25], K[1]); + operation(F2(), E, A, B, C, D, W[26], K[1]); + operation(F2(), D, E, A, B, C, W[27], K[1]); + operation(F2(), C, D, E, A, B, W[28], K[1]); + operation(F2(), B, C, D, E, A, W[29], K[1]); + operation(F2(), A, B, C, D, E, W[30], K[1]); + operation(F2(), E, A, B, C, D, W[31], K[1]); + operation(F2(), D, E, A, B, C, W[32], K[1]); + operation(F2(), C, D, E, A, B, W[33], K[1]); + operation(F2(), B, C, D, E, A, W[34], K[1]); + operation(F2(), A, B, C, D, E, W[35], K[1]); + operation(F2(), E, A, B, C, D, W[36], K[1]); + operation(F2(), D, E, A, B, C, W[37], K[1]); + operation(F2(), C, D, E, A, B, W[38], K[1]); + operation(F2(), B, C, D, E, A, W[39], K[1]); + + // Round 3 + operation(F3(), A, B, C, D, E, W[40], K[2]); + operation(F3(), E, A, B, C, D, W[41], K[2]); + operation(F3(), D, E, A, B, C, W[42], K[2]); + operation(F3(), C, D, E, A, B, W[43], K[2]); + operation(F3(), B, C, D, E, A, W[44], K[2]); + operation(F3(), A, B, C, D, E, W[45], K[2]); + operation(F3(), E, A, B, C, D, W[46], K[2]); + operation(F3(), D, E, A, B, C, W[47], K[2]); + operation(F3(), C, D, E, A, B, W[48], K[2]); + operation(F3(), B, C, D, E, A, W[49], K[2]); + operation(F3(), A, B, C, D, E, W[50], K[2]); + operation(F3(), E, A, B, C, D, W[51], K[2]); + operation(F3(), D, E, A, B, C, W[52], K[2]); + operation(F3(), C, D, E, A, B, W[53], K[2]); + operation(F3(), B, C, D, E, A, W[54], K[2]); + operation(F3(), A, B, C, D, E, W[55], K[2]); + operation(F3(), E, A, B, C, D, W[56], K[2]); + operation(F3(), D, E, A, B, C, W[57], K[2]); + operation(F3(), C, D, E, A, B, W[58], K[2]); + operation(F3(), B, C, D, E, A, W[59], K[2]); + + // Round 4 + operation(F2(), A, B, C, D, E, W[60], K[3]); + operation(F2(), E, A, B, C, D, W[61], K[3]); + operation(F2(), D, E, A, B, C, W[62], K[3]); + operation(F2(), C, D, E, A, B, W[63], K[3]); + operation(F2(), B, C, D, E, A, W[64], K[3]); + operation(F2(), A, B, C, D, E, W[65], K[3]); + operation(F2(), E, A, B, C, D, W[66], K[3]); + operation(F2(), D, E, A, B, C, W[67], K[3]); + operation(F2(), C, D, E, A, B, W[68], K[3]); + operation(F2(), B, C, D, E, A, W[69], K[3]); + operation(F2(), A, B, C, D, E, W[70], K[3]); + operation(F2(), E, A, B, C, D, W[71], K[3]); + operation(F2(), D, E, A, B, C, W[72], K[3]); + operation(F2(), C, D, E, A, B, W[73], K[3]); + operation(F2(), B, C, D, E, A, W[74], K[3]); + operation(F2(), A, B, C, D, E, W[75], K[3]); + operation(F2(), E, A, B, C, D, W[76], K[3]); + operation(F2(), D, E, A, B, C, W[77], K[3]); + operation(F2(), C, D, E, A, B, W[78], K[3]); + operation(F2(), B, C, D, E, A, W[79], K[3]); + + state[0] += A; + state[1] += B; + state[2] += C; + state[3] += D; + state[4] += E; + +#if defined(SK_SHA1_CLEAR_DATA) + // Clear sensitive information. + memset(W, 0, sizeof(W)); +#endif +} + +static void encode(uint8_t output[20], const uint32_t input[5]) { + for (size_t i = 0, j = 0; i < 5; i++, j += 4) { + output[j ] = (uint8_t)((input[i] >> 24) & 0xff); + output[j+1] = (uint8_t)((input[i] >> 16) & 0xff); + output[j+2] = (uint8_t)((input[i] >> 8) & 0xff); + output[j+3] = (uint8_t)((input[i] ) & 0xff); + } +} + +static void encode(uint8_t output[8], const uint64_t input) { + output[0] = (uint8_t)((input >> 56) & 0xff); + output[1] = (uint8_t)((input >> 48) & 0xff); + output[2] = (uint8_t)((input >> 40) & 0xff); + output[3] = (uint8_t)((input >> 32) & 0xff); + output[4] = (uint8_t)((input >> 24) & 0xff); + output[5] = (uint8_t)((input >> 16) & 0xff); + output[6] = (uint8_t)((input >> 8) & 0xff); + output[7] = (uint8_t)((input ) & 0xff); +} diff --git a/src/utils/SkSHA1.h b/src/utils/SkSHA1.h new file mode 100644 index 0000000000..e0653c62e6 --- /dev/null +++ b/src/utils/SkSHA1.h @@ -0,0 +1,54 @@ +/* + * Copyright 2013 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +#ifndef SkSHA1_DEFINED +#define SkSHA1_DEFINED + +#include "SkTypes.h" +#include "SkEndian.h" +#include "SkStream.h" + +//The following macros can be defined to affect the SHA1 code generated. +//SK_SHA1_CLEAR_DATA causes all intermediate state to be overwritten with 0's. +//SK_CPU_BENDIAN allows 32 bit <=> 8 bit conversions without copies (if alligned). +//SK_CPU_FAST_UNALIGNED_ACCESS allows 32 bit <=> 8 bit conversions without copies if SK_CPU_BENDIAN. + +class SkSHA1 : SkWStream { +public: + SkSHA1(); + + /** Processes input, adding it to the digest. + * Note that this treats the buffer as a series of uint8_t values. + */ + virtual bool write(const void* buffer, size_t size) SK_OVERRIDE { + update(reinterpret_cast<const uint8_t*>(buffer), size); + return true; + } + + /** Processes input, adding it to the digest. Calling this after finish is undefined. */ + void update(const uint8_t* input, size_t length); + + struct Digest { + uint8_t data[20]; + }; + + /** Computes and returns the digest. */ + void finish(Digest& digest); + +private: + // number of bytes, modulo 2^64 + uint64_t byteCount; + + // state (ABCDE) + uint32_t state[5]; + + // input buffer + uint8_t buffer[64]; +}; + +#endif + diff --git a/tests/MD5Test.cpp b/tests/MD5Test.cpp new file mode 100644 index 0000000000..a7b132b272 --- /dev/null +++ b/tests/MD5Test.cpp @@ -0,0 +1,68 @@ +/* + * Copyright 2013 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ +#include "Test.h" +#include "SkMD5.h" + +static bool digests_equal(const SkMD5::Digest& expectedDigest, const SkMD5::Digest& computedDigest) { + for (size_t i = 0; i < SK_ARRAY_COUNT(expectedDigest.data); ++i) { + if (expectedDigest.data[i] != computedDigest.data[i]) { + return false; + } + } + return true; +} + +static void md5_test(const char* string, const SkMD5::Digest& expectedDigest, skiatest::Reporter* reporter) { + size_t len = strlen(string); + + // All at once + { + SkMD5 context; + context.update(reinterpret_cast<const uint8_t*>(string), len); + SkMD5::Digest digest; + context.finish(digest); + + REPORTER_ASSERT(reporter, digests_equal(expectedDigest, digest)); + } + + // One byte at a time. + { + SkMD5 context; + const uint8_t* data = reinterpret_cast<const uint8_t*>(string); + const uint8_t* end = reinterpret_cast<const uint8_t*>(string + len); + for (; data < end; ++data) { + context.update(data, 1); + } + SkMD5::Digest digest; + context.finish(digest); + + REPORTER_ASSERT(reporter, digests_equal(expectedDigest, digest)); + } +} + +static struct MD5Test { + const char* message; + SkMD5::Digest digest; +} md5_tests[] = { + // Reference tests from RFC1321 Section A.5 ( http://www.ietf.org/rfc/rfc1321.txt ) + { "", {{ 0xd4, 0x1d, 0x8c, 0xd9, 0x8f, 0x00, 0xb2, 0x04, 0xe9, 0x80, 0x09, 0x98, 0xec, 0xf8, 0x42, 0x7e }} }, + { "a", {{ 0x0c, 0xc1, 0x75, 0xb9, 0xc0, 0xf1, 0xb6, 0xa8, 0x31, 0xc3, 0x99, 0xe2, 0x69, 0x77, 0x26, 0x61 }} }, + { "abc", {{ 0x90, 0x01, 0x50, 0x98, 0x3c, 0xd2, 0x4f, 0xb0, 0xd6, 0x96, 0x3f, 0x7d, 0x28, 0xe1, 0x7f, 0x72 }} }, + { "message digest", {{ 0xf9, 0x6b, 0x69, 0x7d, 0x7c, 0xb7, 0x93, 0x8d, 0x52, 0x5a, 0x2f, 0x31, 0xaa, 0xf1, 0x61, 0xd0 }} }, + { "abcdefghijklmnopqrstuvwxyz", {{ 0xc3, 0xfc, 0xd3, 0xd7, 0x61, 0x92, 0xe4, 0x00, 0x7d, 0xfb, 0x49, 0x6c, 0xca, 0x67, 0xe1, 0x3b }} }, + { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", {{ 0xd1, 0x74, 0xab, 0x98, 0xd2, 0x77, 0xd9, 0xf5, 0xa5, 0x61, 0x1c, 0x2c, 0x9f, 0x41, 0x9d, 0x9f }} }, + { "12345678901234567890123456789012345678901234567890123456789012345678901234567890", {{ 0x57, 0xed, 0xf4, 0xa2, 0x2b, 0xe3, 0xc9, 0x55, 0xac, 0x49, 0xda, 0x2e, 0x21, 0x07, 0xb6, 0x7a }} }, +}; + +static void TestMD5(skiatest::Reporter* reporter) { + for (size_t i = 0; i < SK_ARRAY_COUNT(md5_tests); ++i) { + md5_test(md5_tests[i].message, md5_tests[i].digest, reporter); + } +} + +#include "TestClassDef.h" +DEFINE_TESTCLASS("MD5", MD5TestClass, TestMD5)
\ No newline at end of file diff --git a/tests/SHA1Test.cpp b/tests/SHA1Test.cpp new file mode 100644 index 0000000000..9f078499bf --- /dev/null +++ b/tests/SHA1Test.cpp @@ -0,0 +1,55 @@ +/* + * Copyright 2013 Google Inc. + * + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ +#include "Test.h" +#include "SkSHA1.h" + +static bool digests_equal(const SkSHA1::Digest& expectedDigest, const SkSHA1::Digest& computedDigest) { + for (size_t i = 0; i < SK_ARRAY_COUNT(expectedDigest.data); ++i) { + if (expectedDigest.data[i] != computedDigest.data[i]) { + return false; + } + } + return true; +} + +static struct SHA1Test { + const char* message; + const unsigned long int repeatCount; + const SkSHA1::Digest digest; +} sha1_tests[] = { + // Reference tests from RFC3174 Section 7.3 ( http://www.ietf.org/rfc/rfc3174.txt ) + { "abc", 1, {{ 0xA9, 0x99, 0x3E, 0x36, 0x47, 0x06, 0x81, 0x6A, 0xBA, 0x3E, 0x25, 0x71, 0x78, 0x50, 0xC2, 0x6C, 0x9C, 0xD0, 0xD8, 0x9D }} }, + { "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq", 1, {{ 0x84, 0x98, 0x3E, 0x44, 0x1C, 0x3B, 0xD2, 0x6E, 0xBA, 0xAE, 0x4A, 0xA1, 0xF9, 0x51, 0x29, 0xE5, 0xE5, 0x46, 0x70, 0xF1 }} }, + { "a", 1000000, {{ 0x34, 0xAA, 0x97, 0x3C, 0xD4, 0xC4, 0xDA, 0xA4, 0xF6, 0x1E, 0xEB, 0x2B, 0xDB, 0xAD, 0x27, 0x31, 0x65, 0x34, 0x01, 0x6F }} }, + { "0123456701234567012345670123456701234567012345670123456701234567", 10, {{ 0xDE, 0xA3, 0x56, 0xA2, 0xCD, 0xDD, 0x90, 0xC7, 0xA7, 0xEC, 0xED, 0xC5, 0xEB, 0xB5, 0x63, 0x93, 0x4F, 0x46, 0x04, 0x52 }} }, + + // Reference tests from running GNU sha1sum on test input + { "The quick brown fox jumps over the lazy dog", 1, {{ 0x2f, 0xd4, 0xe1, 0xc6, 0x7a, 0x2d, 0x28, 0xfc, 0xed, 0x84, 0x9e, 0xe1, 0xbb, 0x76, 0xe7, 0x39, 0x1b, 0x93, 0xeb, 0x12 }} }, + { "", 1, {{ 0xda, 0x39, 0xa3, 0xee, 0x5e, 0x6b, 0x4b, 0x0d, 0x32, 0x55, 0xbf, 0xef, 0x95, 0x60, 0x18, 0x90, 0xaf, 0xd8, 0x07, 0x09 }} }, +}; + +static void sha1_test(const SHA1Test& test, skiatest::Reporter* reporter) { + size_t len = strlen(test.message); + + SkSHA1 context; + for (unsigned long int i = 0; i < test.repeatCount; ++i) { + context.update(reinterpret_cast<const uint8_t*>(test.message), len); + } + SkSHA1::Digest digest; + context.finish(digest); + + REPORTER_ASSERT(reporter, digests_equal(test.digest, digest)); +} + +static void TestSHA1(skiatest::Reporter* reporter) { + for (size_t i = 0; i < SK_ARRAY_COUNT(sha1_tests); ++i) { + sha1_test(sha1_tests[i], reporter); + } +} + +#include "TestClassDef.h" +DEFINE_TESTCLASS("SHA1", SHA1TestClass, TestSHA1)
\ No newline at end of file |