compressor.cpp
1 // Copyright (c) 2009-2010 Satoshi Nakamoto 2 // Copyright (c) 2009-2021 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 <pubkey.h> 9 #include <script/script.h> 10 11 /* 12 * These check for scripts for which a special case with a shorter encoding is defined. 13 * They are implemented separately from the CScript test, as these test for exact byte 14 * sequence correspondences, and are more strict. For example, IsToPubKey also verifies 15 * whether the public key is valid (as invalid ones cannot be represented in compressed 16 * form). 17 */ 18 19 static bool IsToKeyID(const CScript& script, CKeyID &hash) 20 { 21 if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160 22 && script[2] == 20 && script[23] == OP_EQUALVERIFY 23 && script[24] == OP_CHECKSIG) { 24 memcpy(&hash, &script[3], 20); 25 return true; 26 } 27 return false; 28 } 29 30 static bool IsToScriptID(const CScript& script, CScriptID &hash) 31 { 32 if (script.size() == 23 && script[0] == OP_HASH160 && script[1] == 20 33 && script[22] == OP_EQUAL) { 34 memcpy(&hash, &script[2], 20); 35 return true; 36 } 37 return false; 38 } 39 40 static bool IsToPubKey(const CScript& script, CPubKey &pubkey) 41 { 42 if (script.size() == 35 && script[0] == 33 && script[34] == OP_CHECKSIG 43 && (script[1] == 0x02 || script[1] == 0x03)) { 44 pubkey.Set(&script[1], &script[34]); 45 return true; 46 } 47 if (script.size() == 67 && script[0] == 65 && script[66] == OP_CHECKSIG 48 && script[1] == 0x04) { 49 pubkey.Set(&script[1], &script[66]); 50 return pubkey.IsFullyValid(); // if not fully valid, a case that would not be compressible 51 } 52 return false; 53 } 54 55 bool CompressScript(const CScript& script, CompressedScript& out) 56 { 57 CKeyID keyID; 58 if (IsToKeyID(script, keyID)) { 59 out.resize(21); 60 out[0] = 0x00; 61 memcpy(&out[1], &keyID, 20); 62 return true; 63 } 64 CScriptID scriptID; 65 if (IsToScriptID(script, scriptID)) { 66 out.resize(21); 67 out[0] = 0x01; 68 memcpy(&out[1], &scriptID, 20); 69 return true; 70 } 71 CPubKey pubkey; 72 if (IsToPubKey(script, pubkey)) { 73 out.resize(33); 74 memcpy(&out[1], &pubkey[1], 32); 75 if (pubkey[0] == 0x02 || pubkey[0] == 0x03) { 76 out[0] = pubkey[0]; 77 return true; 78 } else if (pubkey[0] == 0x04) { 79 out[0] = 0x04 | (pubkey[64] & 0x01); 80 return true; 81 } 82 } 83 return false; 84 } 85 86 unsigned int GetSpecialScriptSize(unsigned int nSize) 87 { 88 if (nSize == 0 || nSize == 1) 89 return 20; 90 if (nSize == 2 || nSize == 3 || nSize == 4 || nSize == 5) 91 return 32; 92 return 0; 93 } 94 95 bool DecompressScript(CScript& script, unsigned int nSize, const CompressedScript& in) 96 { 97 switch(nSize) { 98 case 0x00: 99 script.resize(25); 100 script[0] = OP_DUP; 101 script[1] = OP_HASH160; 102 script[2] = 20; 103 memcpy(&script[3], in.data(), 20); 104 script[23] = OP_EQUALVERIFY; 105 script[24] = OP_CHECKSIG; 106 return true; 107 case 0x01: 108 script.resize(23); 109 script[0] = OP_HASH160; 110 script[1] = 20; 111 memcpy(&script[2], in.data(), 20); 112 script[22] = OP_EQUAL; 113 return true; 114 case 0x02: 115 case 0x03: 116 script.resize(35); 117 script[0] = 33; 118 script[1] = nSize; 119 memcpy(&script[2], in.data(), 32); 120 script[34] = OP_CHECKSIG; 121 return true; 122 case 0x04: 123 case 0x05: 124 unsigned char vch[33] = {}; 125 vch[0] = nSize - 2; 126 memcpy(&vch[1], in.data(), 32); 127 CPubKey pubkey{vch}; 128 if (!pubkey.Decompress()) 129 return false; 130 assert(pubkey.size() == 65); 131 script.resize(67); 132 script[0] = 65; 133 memcpy(&script[1], pubkey.begin(), 65); 134 script[66] = OP_CHECKSIG; 135 return true; 136 } 137 return false; 138 } 139 140 // Amount compression: 141 // * If the amount is 0, output 0 142 // * first, divide the amount (in base units) by the largest power of 10 possible; call the exponent e (e is max 9) 143 // * if e<9, the last digit of the resulting number cannot be 0; store it as d, and drop it (divide by 10) 144 // * call the result n 145 // * output 1 + 10*(9*n + d - 1) + e 146 // * if e==9, we only know the resulting number is not zero, so output 1 + 10*(n - 1) + 9 147 // (this is decodable, as d is in [1-9] and e is in [0-9]) 148 149 uint64_t CompressAmount(uint64_t n) 150 { 151 if (n == 0) 152 return 0; 153 int e = 0; 154 while (((n % 10) == 0) && e < 9) { 155 n /= 10; 156 e++; 157 } 158 if (e < 9) { 159 int d = (n % 10); 160 assert(d >= 1 && d <= 9); 161 n /= 10; 162 return 1 + (n*9 + d - 1)*10 + e; 163 } else { 164 return 1 + (n - 1)*10 + 9; 165 } 166 } 167 168 uint64_t DecompressAmount(uint64_t x) 169 { 170 // x = 0 OR x = 1+10*(9*n + d - 1) + e OR x = 1+10*(n - 1) + 9 171 if (x == 0) 172 return 0; 173 x--; 174 // x = 10*(9*n + d - 1) + e 175 int e = x % 10; 176 x /= 10; 177 uint64_t n = 0; 178 if (e < 9) { 179 // x = 9*n + d - 1 180 int d = (x % 9) + 1; 181 x /= 9; 182 // x = n 183 n = x*10 + d; 184 } else { 185 n = x+1; 186 } 187 while (e) { 188 n *= 10; 189 e--; 190 } 191 return n; 192 }