src/compressor.cpp

   1 // Copyright (c) 2009-2010 Satoshi Nakamoto
   2 // Copyright (c) 2009-2014 The Bitcoin Core developers
   3 // Distributed under the MIT software license, see the accompanying
   4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   5
   6 #include "compressor.h"
   7
   8 #include "hash.h"
   9 #include "pubkey.h"
  10 #include "script/standard.h"
  11
  12 bool CScriptCompressor::IsToKeyID(CKeyID &hash) const
  13 {
  14     if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160
  15                             && script[2] == 20 && script[23] == OP_EQUALVERIFY
  16                             && script[24] == OP_CHECKSIG) {
  17         memcpy(&hash, &script[3], 20);
  18         return true;
  19     }
  20     return false;
  21 }
  22
  23 bool CScriptCompressor::IsToScriptID(CScriptID &hash) const
  24 {
  25     if (script.size() == 23 && script[0] == OP_HASH160 && script[1] == 20
  26                             && script[22] == OP_EQUAL) {
  27         memcpy(&hash, &script[2], 20);
  28         return true;
  29     }
  30     return false;
  31 }
  32
  33 bool CScriptCompressor::IsToPubKey(CPubKey &pubkey) const
  34 {
  35     if (script.size() == 35 && script[0] == 33 && script[34] == OP_CHECKSIG
  36                             && (script[1] == 0x02 || script[1] == 0x03)) {
  37         pubkey.Set(&script[1], &script[34]);
  38         return true;
  39     }
  40     if (script.size() == 67 && script[0] == 65 && script[66] == OP_CHECKSIG
  41                             && script[1] == 0x04) {
  42         pubkey.Set(&script[1], &script[66]);
  43         return pubkey.IsFullyValid(); // if not fully valid, a case that would not be compressible
  44     }
  45     return false;
  46 }
  47
  48 bool CScriptCompressor::Compress(std::vector<unsigned char> &out) const
  49 {
  50     CKeyID keyID;
  51     if (IsToKeyID(keyID)) {
  52         out.resize(21);
  53         out[0] = 0x00;
  54         memcpy(&out[1], &keyID, 20);
  55         return true;
  56     }
  57     CScriptID scriptID;
  58     if (IsToScriptID(scriptID)) {
  59         out.resize(21);
  60         out[0] = 0x01;
  61         memcpy(&out[1], &scriptID, 20);
  62         return true;
  63     }
  64     CPubKey pubkey;
  65     if (IsToPubKey(pubkey)) {
  66         out.resize(33);
  67         memcpy(&out[1], &pubkey[1], 32);
  68         if (pubkey[0] == 0x02 || pubkey[0] == 0x03) {
  69             out[0] = pubkey[0];
  70             return true;
  71         } else if (pubkey[0] == 0x04) {
  72             out[0] = 0x04 | (pubkey[64] & 0x01);
  73             return true;
  74         }
  75     }
  76     return false;
  77 }
  78
  79 unsigned int CScriptCompressor::GetSpecialSize(unsigned int nSize) const
  80 {
  81     if (nSize == 0 || nSize == 1)
  82         return 20;
  83     if (nSize == 2 || nSize == 3 || nSize == 4 || nSize == 5)
  84         return 32;
  85     return 0;
  86 }
  87
  88 bool CScriptCompressor::Decompress(unsigned int nSize, const std::vector<unsigned char> &in)
  89 {
  90     switch(nSize) {
  91     case 0x00:
  92         script.resize(25);
  93         script[0] = OP_DUP;
  94         script[1] = OP_HASH160;
  95         script[2] = 20;
  96         memcpy(&script[3], &in[0], 20);
  97         script[23] = OP_EQUALVERIFY;
  98         script[24] = OP_CHECKSIG;
  99         return true;
 100     case 0x01:
 101         script.resize(23);
 102         script[0] = OP_HASH160;
 103         script[1] = 20;
 104         memcpy(&script[2], &in[0], 20);
 105         script[22] = OP_EQUAL;
 106         return true;
 107     case 0x02:
 108     case 0x03:
 109         script.resize(35);
 110         script[0] = 33;
 111         script[1] = nSize;
 112         memcpy(&script[2], &in[0], 32);
 113         script[34] = OP_CHECKSIG;
 114         return true;
 115     case 0x04:
 116     case 0x05:
 117         unsigned char vch[33] = {};
 118         vch[0] = nSize - 2;
 119         memcpy(&vch[1], &in[0], 32);
 120         CPubKey pubkey(&vch[0], &vch[33]);
 121         if (!pubkey.Decompress())
 122             return false;
 123         assert(pubkey.size() == 65);
 124         script.resize(67);
 125         script[0] = 65;
 126         memcpy(&script[1], pubkey.begin(), 65);
 127         script[66] = OP_CHECKSIG;
 128         return true;
 129     }
 130     return false;
 131 }
 132
 133 // Amount compression:
 134 // * If the amount is 0, output 0
 135 // * first, divide the amount (in base units) by the largest power of 10 possible; call the exponent e (e is max 9)
 136 // * if e<9, the last digit of the resulting number cannot be 0; store it as d, and drop it (divide by 10)
 137 //   * call the result n
 138 //   * output 1 + 10*(9*n + d - 1) + e
 139 // * if e==9, we only know the resulting number is not zero, so output 1 + 10*(n - 1) + 9
 140 // (this is decodable, as d is in [1-9] and e is in [0-9])
 141
 142 uint64_t CTxOutCompressor::CompressAmount(uint64_t n)
 143 {
 144     if (n == 0)
 145         return 0;
 146     int e = 0;
 147     while (((n % 10) == 0) && e < 9) {
 148         n /= 10;
 149         e++;
 150     }
 151     if (e < 9) {
 152         int d = (n % 10);
 153         assert(d >= 1 && d <= 9);
 154         n /= 10;
 155         return 1 + (n*9 + d - 1)*10 + e;
 156     } else {
 157         return 1 + (n - 1)*10 + 9;
 158     }
 159 }
 160
 161 uint64_t CTxOutCompressor::DecompressAmount(uint64_t x)
 162 {
 163     // x = 0  OR  x = 1+10*(9*n + d - 1) + e  OR  x = 1+10*(n - 1) + 9
 164     if (x == 0)
 165         return 0;
 166     x--;
 167     // x = 10*(9*n + d - 1) + e
 168     int e = x % 10;
 169     x /= 10;
 170     uint64_t n = 0;
 171     if (e < 9) {
 172         // x = 9*n + d - 1
 173         int d = (x % 9) + 1;
 174         x /= 9;
 175         // x = n
 176         n = x*10 + d;
 177     } else {
 178         n = x+1;
 179     }
 180     while (e) {
 181         n *= 10;
 182         e--;
 183     }
 184     return n;
 185 }