Correct implementation of swarm hash.

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<size_t>(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()