Compact serialization for amounts

Special serializer/deserializer for amount values. It is optimized for
values which have few non-zero digits in decimal representation. Most
amounts currently in the txout set take only 1 or 2 bytes to
represent.

3 files changed, 130 insertions, 3 deletions

diff --git a/src/main.cpp b/src/main.cpp
index 43bb4b1793..ed677f31c8 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -4058,3 +4058,57 @@ void GenerateBitcoins(bool fGenerate, CWallet* pwallet)
         }
     }
 }
+
+// Amount compression:
+// * If the amount is 0, output 0
+// * first, divide the amount (in base units) by the largest power of 10 possible; call the exponent e (e is max 9)
+// * if e<9, the last digit of the resulting number cannot be 0; store it as d, and drop it (divide by 10)
+//   * call the result n
+//   * output 1 + 10*(9*n + d - 1) + e
+// * if e==9, we only know the resulting number is not zero, so output 1 + 10*(n - 1) + 9
+// (this is decodable, as d is in [1-9] and e is in [0-9])
+
+uint64 CTxOutCompressor::CompressAmount(uint64 n)
+{
+    if (n == 0)
+        return 0;
+    int e = 0;
+    while (((n % 10) == 0) && e < 9) {
+        n /= 10;
+        e++;
+    }
+    if (e < 9) {
+        int d = (n % 10);
+        assert(d >= 1 && d <= 9);
+        n /= 10;
+        return 1 + (n*9 + d - 1)*10 + e;
+    } else {
+        return 1 + (n - 1)*10 + 9;
+    }
+}
+
+uint64 CTxOutCompressor::DecompressAmount(uint64 x)
+{
+    // x = 0  OR  x = 1+10*(9*n + d - 1) + e  OR  x = 1+10*(n - 1) + 9
+    if (x == 0)
+        return 0;
+    x--;
+    // x = 10*(9*n + d - 1) + e
+    int e = x % 10;
+    x /= 10;
+    uint64 n = 0;
+    if (e < 9) {
+        // x = 9*n + d - 1
+        int d = (x % 9) + 1;
+        x /= 9;
+        // x = n
+        n = x*10 + d;
+    } else {
+        n = x+1;
+    }
+    while (e) {
+        n *= 10;
+        e--;
+    }
+    return n;
+}
diff --git a/src/main.h b/src/main.h
index 1af781f45c..4286880c9f 100644
--- a/src/main.h
+++ b/src/main.h
@@ -652,14 +652,25 @@ class CTxOutCompressor
 {
 private:
     CTxOut &txout;
+
 public:
+    static uint64 CompressAmount(uint64 nAmount);
+    static uint64 DecompressAmount(uint64 nAmount);
+
     CTxOutCompressor(CTxOut &txoutIn) : txout(txoutIn) { }
 
-    IMPLEMENT_SERIALIZE(
-        READWRITE(VARINT(txout.nValue));
+    IMPLEMENT_SERIALIZE(({
+        if (!fRead) {
+            uint64 nVal = CompressAmount(txout.nValue);
+            READWRITE(VARINT(nVal));
+        } else {
+            uint64 nVal = 0;
+            READWRITE(VARINT(nVal));
+            txout.nValue = DecompressAmount(nVal);
+        }
         CScriptCompressor cscript(REF(txout.scriptPubKey));
         READWRITE(cscript);
-    )
+    });)
 };
 
 
diff --git a/src/test/compress_tests.cpp b/src/test/compress_tests.cpp
new file mode 100644
index 0000000000..71b86bcb41
--- /dev/null
+++ b/src/test/compress_tests.cpp
@@ -0,0 +1,62 @@
+#include <boost/test/unit_test.hpp>
+
+#include <string>
+#include <vector>
+
+#include "main.h"
+
+// amounts 0.00000001 .. 0.00100000
+#define NUM_MULTIPLES_UNIT 100000
+
+// amounts 0.01 .. 100.00
+#define NUM_MULTIPLES_CENT 10000
+
+// amounts 1 .. 10000
+#define NUM_MULTIPLES_1BTC 10000
+
+// amounts 50 .. 21000000
+#define NUM_MULTIPLES_50BTC 420000
+
+using namespace std;
+
+BOOST_AUTO_TEST_SUITE(compress_tests)
+
+bool static TestEncode(uint64 in) {
+    return in == CTxOutCompressor::DecompressAmount(CTxOutCompressor::CompressAmount(in));
+}
+
+bool static TestDecode(uint64 in) {
+    return in == CTxOutCompressor::CompressAmount(CTxOutCompressor::DecompressAmount(in));
+}
+
+bool static TestPair(uint64 dec, uint64 enc) {
+    return CTxOutCompressor::CompressAmount(dec) == enc &&
+           CTxOutCompressor::DecompressAmount(enc) == dec;
+}
+
+BOOST_AUTO_TEST_CASE(compress_amounts)
+{
+    BOOST_CHECK(TestPair(            0,       0x0));
+    BOOST_CHECK(TestPair(            1,       0x1));
+    BOOST_CHECK(TestPair(         CENT,       0x7));
+    BOOST_CHECK(TestPair(         COIN,       0x9));
+    BOOST_CHECK(TestPair(      50*COIN,      0x32));
+    BOOST_CHECK(TestPair(21000000*COIN, 0x1406f40));
+
+    for (uint64 i = 1; i <= NUM_MULTIPLES_UNIT; i++)
+        BOOST_CHECK(TestEncode(i));
+
+    for (uint64 i = 1; i <= NUM_MULTIPLES_CENT; i++)
+        BOOST_CHECK(TestEncode(i * CENT));
+
+    for (uint64 i = 1; i <= NUM_MULTIPLES_1BTC; i++)
+        BOOST_CHECK(TestEncode(i * COIN));
+
+    for (uint64 i = 1; i <= NUM_MULTIPLES_50BTC; i++)
+        BOOST_CHECK(TestEncode(i * 50 * COIN));
+
+    for (uint64 i = 0; i < 100000; i++)
+        BOOST_CHECK(TestDecode(i));
+}
+
+BOOST_AUTO_TEST_SUITE_END()