From 518fe2aab7b96dc9cd259049dec80be509860a43 Mon Sep 17 00:00:00 2001 From: chriseth Date: Tue, 15 Nov 2016 14:55:19 +0100 Subject: Correct implementation of swarm hash. --- libdevcore/SwarmHash.cpp | 38 ++++++++++++++++---------------------- test/libdevcore/SwarmHash.cpp | 15 ++++++++------- 2 files changed, 24 insertions(+), 29 deletions(-) diff --git a/libdevcore/SwarmHash.cpp b/libdevcore/SwarmHash.cpp index 583d84b1..e7b844eb 100644 --- a/libdevcore/SwarmHash.cpp +++ b/libdevcore/SwarmHash.cpp @@ -38,32 +38,26 @@ h256 swarmHashSimple(bytesConstRef _data, size_t _size) return keccak256(toLittleEndian(_size) + _data.toBytes()); } -h256 dev::swarmHash(bytes const& _input) +h256 swarmHashIntermediate(bytes const& _input, size_t _offset, size_t _length) { - bytes data = _input; - size_t lastChunkSize = 0; - size_t level = 0; - do + if (_length <= 0x1000) + return swarmHashSimple(bytesConstRef(_input.data() + _offset, _length), _length); + else { bytes innerNodes; - size_t i = 0; - do + size_t maxRepresentedSize = 0x1000; + while (maxRepresentedSize * (0x1000 / 32) < _length) + maxRepresentedSize *= (0x1000 / 32); + for (size_t i = 0; i < _length; i += maxRepresentedSize) { - size_t bytes = std::min(0x1000, data.size() - i); - size_t size = bytes << (7 * level); - if (i + 0x1000 >= data.size()) - { - // last node - size = level == 0 ? bytes : ((bytes - 32) << (7 * level)) + lastChunkSize; - lastChunkSize = size; - } - innerNodes += swarmHashSimple(bytesConstRef(_input.data() + i, bytes), size).asBytes(); - i += 0x1000; + size_t size = std::min(maxRepresentedSize, _length - i); + innerNodes += swarmHashIntermediate(_input, _offset + i, size).asBytes(); } - while (i < data.size()); - data = std::move(innerNodes); - level++; + return swarmHashSimple(bytesConstRef(&innerNodes), _length); } - while (data.size() > 32); - return h256(data); +} + +h256 dev::swarmHash(bytes const& _input) +{ + return swarmHashIntermediate(_input, 0, _input.size()); } diff --git a/test/libdevcore/SwarmHash.cpp b/test/libdevcore/SwarmHash.cpp index 1f0c2ea5..a23c36fd 100644 --- a/test/libdevcore/SwarmHash.cpp +++ b/test/libdevcore/SwarmHash.cpp @@ -41,13 +41,14 @@ BOOST_AUTO_TEST_CASE(test_zeros) BOOST_CHECK_EQUAL(swarmHashHex(bytes()), string("011b4d03dd8c01f1049143cf9c4c817e4b167f1d1b83e5c6f0f10d89ba1e7bce")); BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x1000 - 1, 0)), string("32f0faabc4265ac238cd945087133ce3d7e9bb2e536053a812b5373c54043adb")); BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x1000, 0)), string("411dd45de7246e94589ff5888362c41e85bd3e582a92d0fda8f0e90b76439bec")); - BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x1000 + 1, 0)), string("970b0b1fe0bf90549af9aba54e8ce18884cce97d63069efe92f73fd50037c3e2")); - BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x2000 - 1, 0)), string("1e7bd4d46836b63a2e7c313b68d24ad6be56ed6c8b30634005fd213bb580b0b4")); - BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x2000, 0)), string("ab184c15eee316dd54e8887614a535f589478e99b922a1ede30ec418344c8324")); - BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x2000 + 1, 0)), string("c8915d9244ad5d7428a41b207e083de6eafffac629b45ad462062ea8dc5ac4a3")); - BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x80000, 0)), string("d0bf003bbc34a68f608f8bc88b497c19ce4ad61f38436ee3120b33db9cc9a116")); - BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x80020, 0)), string("d001908f9942ad56d5343574e33bd74b30092115b1c29a67c20869a9ddbbedc3")); - BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x800020, 0)), string("cdeedeccfe3eaa1c4095713af579b9c2b151d2b3f45ce6652ba2f5cd537a60ba")); + BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x1000 + 1, 0)), string("69754a0098432bbc2e84fe1205276870748a61a065ab6ef44d6a2e7b13ce044d")); + BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x2000 - 1, 0)), string("69ad3c581043404f775ffa8d6f1b25ad4a9ee812971190e90209c0966116a321")); + BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x2000, 0)), string("f00222373ff82d0a178dc6271c78953e9c88f74130a52d401f5ec51475f63c43")); + BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x2000 + 1, 0)), string("86d6773e79e02fd8145ee1aedba89ace0c15f2566db1249654000039a9a134bf")); + BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x80000, 0)), string("cc0854fe2c6b98e920d5c14b1a88e6d4223e55b8f78883f60939aa2485e361bf")); + BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x80020, 0)), string("ee9ffca246e70d3704740ba4df450fa6988d14a1c2439c7e734c7a77a4eb6fd3")); + BOOST_CHECK_EQUAL(swarmHashHex(bytes(0x800020, 0)), string("78b90b20c90559fb904535181a7c28929ea2f30a2329dbc25232de579709f12f")); + BOOST_CHECK_EQUAL(swarmHashHex(bytes(2095104, 0)), string("a9958184589fc11b4027a4c233e777ebe2e99c66f96b74aef2a0638a94dd5439")); } BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3