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
19static 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
30static 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
40static 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
55bool 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
86unsigned 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
95bool 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
149uint64_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
168uint64_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