compressor.cpp raw
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-present 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 }
193