114ef89ad923823e81eb825cbf00ea6615c277f3
[novacoin.git] / src / uint256.h
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2012 The Bitcoin developers
3 // Distributed under the MIT/X11 software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 #ifndef BITCOIN_UINT256_H
6 #define BITCOIN_UINT256_H
7
8 #include <limits>
9 #include <string.h>
10 #include <string>
11 #include <vector>
12 #include <stdint.h>
13
14 using namespace std;
15
16
17 /** Base class without constructors for uint256 and uint160.
18  * This makes the compiler let u use it in a union.
19  */
20 template<unsigned int BITS>
21 class base_uint
22 {
23 protected:
24     enum { WIDTH=BITS/32 };
25     uint32_t pn[WIDTH];
26 public:
27
28     const base_uint max()
29     {
30         base_uint ret;
31         for (int i = 0; i < WIDTH; i++)
32             ret.pn[i] = std::numeric_limits<uint32_t>::max();
33         return ret;
34     }
35
36     bool operator!() const
37     {
38         for (int i = 0; i < WIDTH; i++)
39             if (pn[i] != 0)
40                 return false;
41         return true;
42     }
43
44     const base_uint operator~() const
45     {
46         base_uint ret;
47         for (int i = 0; i < WIDTH; i++)
48             ret.pn[i] = ~pn[i];
49         return ret;
50     }
51
52     const base_uint operator-() const
53     {
54         base_uint ret;
55         for (int i = 0; i < WIDTH; i++)
56             ret.pn[i] = ~pn[i];
57         ret++;
58         return ret;
59     }
60
61     double getdouble() const
62     {
63         double ret = 0.0;
64         double fact = 1.0;
65         for (int i = 0; i < WIDTH; i++) {
66             ret += fact * pn[i];
67             fact *= 4294967296.0;
68         }
69         return ret;
70     }
71
72     base_uint& operator=(uint64_t b)
73     {
74         pn[0] = (uint32_t)b;
75         pn[1] = (uint32_t)(b >> 32);
76         for (int i = 2; i < WIDTH; i++)
77             pn[i] = 0;
78         return *this;
79     }
80
81     base_uint& operator^=(const base_uint& b)
82     {
83         for (int i = 0; i < WIDTH; i++)
84             pn[i] ^= b.pn[i];
85         return *this;
86     }
87
88     base_uint& operator&=(const base_uint& b)
89     {
90         for (int i = 0; i < WIDTH; i++)
91             pn[i] &= b.pn[i];
92         return *this;
93     }
94
95     base_uint& operator|=(const base_uint& b)
96     {
97         for (int i = 0; i < WIDTH; i++)
98             pn[i] |= b.pn[i];
99         return *this;
100     }
101
102     base_uint& operator^=(uint64_t b)
103     {
104         pn[0] ^= (uint32_t)b;
105         pn[1] ^= (uint32_t)(b >> 32);
106         return *this;
107     }
108
109     base_uint& operator|=(uint64_t b)
110     {
111         pn[0] |= (uint32_t)b;
112         pn[1] |= (uint32_t)(b >> 32);
113         return *this;
114     }
115
116     base_uint& operator<<=(unsigned int shift)
117     {
118         base_uint a(*this);
119         for (int i = 0; i < WIDTH; i++)
120             pn[i] = 0;
121         int k = shift / 32;
122         shift = shift % 32;
123         for (int i = 0; i < WIDTH; i++)
124         {
125             if (i+k+1 < WIDTH && shift != 0)
126                 pn[i+k+1] |= (a.pn[i] >> (32-shift));
127             if (i+k < WIDTH)
128                 pn[i+k] |= (a.pn[i] << shift);
129         }
130         return *this;
131     }
132
133     base_uint& operator>>=(unsigned int shift)
134     {
135         base_uint a(*this);
136         for (int i = 0; i < WIDTH; i++)
137             pn[i] = 0;
138         int k = shift / 32;
139         shift = shift % 32;
140         for (int i = 0; i < WIDTH; i++)
141         {
142             if (i-k-1 >= 0 && shift != 0)
143                 pn[i-k-1] |= (a.pn[i] << (32-shift));
144             if (i-k >= 0)
145                 pn[i-k] |= (a.pn[i] >> shift);
146         }
147         return *this;
148     }
149
150     base_uint& operator+=(const base_uint& b)
151     {
152         uint64_t carry = 0;
153         for (int i = 0; i < WIDTH; i++)
154         {
155             uint64_t n = carry + pn[i] + b.pn[i];
156             pn[i] = n & 0xffffffff;
157             carry = n >> 32;
158         }
159         return *this;
160     }
161
162     base_uint& operator-=(const base_uint& b)
163     {
164         *this += -b;
165         return *this;
166     }
167
168     base_uint& operator+=(uint64_t b64)
169     {
170         base_uint b;
171         b = b64;
172         *this += b;
173         return *this;
174     }
175
176     base_uint& operator-=(uint64_t b64)
177     {
178         base_uint b;
179         b = b64;
180         *this += -b;
181         return *this;
182     }
183
184
185     base_uint& operator++()
186     {
187         // prefix operator
188         int i = 0;
189         while (++pn[i] == 0 && i < WIDTH-1)
190             i++;
191         return *this;
192     }
193
194     const base_uint operator++(int)
195     {
196         // postfix operator
197         const base_uint ret = *this;
198         ++(*this);
199         return ret;
200     }
201
202     base_uint& operator--()
203     {
204         // prefix operator
205         int i = 0;
206         while (--pn[i] == -1 && i < WIDTH-1)
207             i++;
208         return *this;
209     }
210
211     const base_uint operator--(int)
212     {
213         // postfix operator
214         const base_uint ret = *this;
215         --(*this);
216         return ret;
217     }
218
219
220     friend inline bool operator<(const base_uint& a, const base_uint& b)
221     {
222         for (int i = base_uint::WIDTH-1; i >= 0; i--)
223         {
224             if (a.pn[i] < b.pn[i])
225                 return true;
226             else if (a.pn[i] > b.pn[i])
227                 return false;
228         }
229         return false;
230     }
231
232     friend inline bool operator<=(const base_uint& a, const base_uint& b)
233     {
234         for (int i = base_uint::WIDTH-1; i >= 0; i--)
235         {
236             if (a.pn[i] < b.pn[i])
237                 return true;
238             else if (a.pn[i] > b.pn[i])
239                 return false;
240         }
241         return true;
242     }
243
244     friend inline bool operator>(const base_uint& a, const base_uint& b)
245     {
246         for (int i = base_uint::WIDTH-1; i >= 0; i--)
247         {
248             if (a.pn[i] > b.pn[i])
249                 return true;
250             else if (a.pn[i] < b.pn[i])
251                 return false;
252         }
253         return false;
254     }
255
256     friend inline bool operator>=(const base_uint& a, const base_uint& b)
257     {
258         for (int i = base_uint::WIDTH-1; i >= 0; i--)
259         {
260             if (a.pn[i] > b.pn[i])
261                 return true;
262             else if (a.pn[i] < b.pn[i])
263                 return false;
264         }
265         return true;
266     }
267
268     friend inline bool operator==(const base_uint& a, const base_uint& b)
269     {
270         for (int i = 0; i < base_uint::WIDTH; i++)
271             if (a.pn[i] != b.pn[i])
272                 return false;
273         return true;
274     }
275
276     friend inline bool operator==(const base_uint& a, uint64_t b)
277     {
278         if (a.pn[0] != (uint32_t)b)
279             return false;
280         if (a.pn[1] != (uint32_t)(b >> 32))
281             return false;
282         for (int i = 2; i < base_uint::WIDTH; i++)
283             if (a.pn[i] != 0)
284                 return false;
285         return true;
286     }
287
288     friend inline bool operator!=(const base_uint& a, const base_uint& b)
289     {
290         return (!(a == b));
291     }
292
293     friend inline bool operator!=(const base_uint& a, uint64_t b)
294     {
295         return (!(a == b));
296     }
297
298     std::string GetHex() const
299     {
300         char psz[sizeof(pn)*2 + 1];
301         for (unsigned int i = 0; i < sizeof(pn); i++)
302             sprintf(psz + i*2, "%02x", ((unsigned char*)pn)[sizeof(pn) - i - 1]);
303         return std::string(psz, psz + sizeof(pn)*2);
304     }
305
306     void SetHex(const char* psz)
307     {
308         for (int i = 0; i < WIDTH; i++)
309             pn[i] = 0;
310
311         // skip leading spaces
312         while (isspace(*psz))
313             psz++;
314
315         // skip 0x
316         if (psz[0] == '0' && tolower(psz[1]) == 'x')
317             psz += 2;
318
319         // hex string to uint
320         static const unsigned char phexdigit[256] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0xa,0xb,0xc,0xd,0xe,0xf,0,0,0,0,0,0,0,0,0 };
321         const char* pbegin = psz;
322         while (phexdigit[(unsigned char)*psz] || *psz == '0')
323             psz++;
324         psz--;
325         unsigned char* p1 = (unsigned char*)pn;
326         unsigned char* pend = p1 + WIDTH * 4;
327         while (psz >= pbegin && p1 < pend)
328         {
329             *p1 = phexdigit[(unsigned char)*psz--];
330             if (psz >= pbegin)
331             {
332                 *p1 |= (phexdigit[(unsigned char)*psz--] << 4);
333                 p1++;
334             }
335         }
336     }
337
338     void SetHex(const std::string& str)
339     {
340         SetHex(str.c_str());
341     }
342
343     std::string ToString() const
344     {
345         return (GetHex());
346     }
347
348     unsigned char* begin() const
349     {
350         return (unsigned char*)&pn[0];
351     }
352
353     unsigned char* end() const
354     {
355         return (unsigned char*)&pn[WIDTH];
356     }
357
358     std::vector<unsigned char> getBytes()
359     {
360         return std::vector<unsigned char>(begin(), end());
361     }
362
363     size_t size() const
364     {
365         return sizeof(pn);
366     }
367
368     uint64_t Get64(int n=0) const
369     {
370         return pn[2*n] | (uint64_t)pn[2*n+1] << 32;
371     }
372
373     uint32_t Get32(int n=0) const
374     {
375         return pn[n];
376     }
377
378     unsigned int GetSerializeSize(int nType, int nVersion) const
379     {
380         return sizeof(pn);
381     }
382
383     unsigned int bits() const
384     {
385         for (int pos = WIDTH - 1; pos >= 0; pos--) {
386             if (pn[pos]) {
387                 for (int bits = 31; bits > 0; bits--) {
388                     if (pn[pos] & 1 << bits)
389                         return 32 * pos + bits + 1;
390                 }
391                 return 32 * pos + 1;
392             }
393         }
394         return 0;
395     }
396
397     template<typename Stream>
398     void Serialize(Stream& s, int nType, int nVersion) const
399     {
400         s.write((char*)pn, sizeof(pn));
401     }
402
403     template<typename Stream>
404     void Unserialize(Stream& s, int nType, int nVersion)
405     {
406         s.read((char*)pn, sizeof(pn));
407     }
408
409     friend class uint160;
410     friend class uint256;
411 };
412
413 typedef base_uint<160> base_uint160;
414 typedef base_uint<256> base_uint256;
415
416 //
417 // uint160 and uint256 could be implemented as templates, but to keep
418 // compile errors and debugging cleaner, they're copy and pasted.
419 //
420
421
422
423 //////////////////////////////////////////////////////////////////////////////
424 //
425 // uint160
426 //
427
428 /** 160-bit unsigned integer */
429 class uint160 : public base_uint160
430 {
431 public:
432     typedef base_uint160 basetype;
433
434     uint160();
435     uint160(const basetype& b);
436     uint160& operator=(const basetype& b);
437     uint160(uint64_t b);
438     uint160& operator=(uint64_t b);
439     explicit uint160(const std::string& str);
440     explicit uint160(const std::vector<unsigned char>& vch);
441 };
442
443 inline bool operator==(const uint160& a, uint64_t b)                           { return (base_uint160)a == b; }
444 inline bool operator!=(const uint160& a, uint64_t b)                           { return (base_uint160)a != b; }
445 inline const uint160 operator<<(const base_uint160& a, unsigned int shift)   { return uint160(a) <<= shift; }
446 inline const uint160 operator>>(const base_uint160& a, unsigned int shift)   { return uint160(a) >>= shift; }
447 inline const uint160 operator<<(const uint160& a, unsigned int shift)        { return uint160(a) <<= shift; }
448 inline const uint160 operator>>(const uint160& a, unsigned int shift)        { return uint160(a) >>= shift; }
449
450 inline const uint160 operator^(const base_uint160& a, const base_uint160& b) { return uint160(a) ^= b; }
451 inline const uint160 operator&(const base_uint160& a, const base_uint160& b) { return uint160(a) &= b; }
452 inline const uint160 operator|(const base_uint160& a, const base_uint160& b) { return uint160(a) |= b; }
453 inline const uint160 operator+(const base_uint160& a, const base_uint160& b) { return uint160(a) += b; }
454 inline const uint160 operator-(const base_uint160& a, const base_uint160& b) { return uint160(a) -= b; }
455
456 inline bool operator<(const base_uint160& a, const uint160& b)          { return (base_uint160)a <  (base_uint160)b; }
457 inline bool operator<=(const base_uint160& a, const uint160& b)         { return (base_uint160)a <= (base_uint160)b; }
458 inline bool operator>(const base_uint160& a, const uint160& b)          { return (base_uint160)a >  (base_uint160)b; }
459 inline bool operator>=(const base_uint160& a, const uint160& b)         { return (base_uint160)a >= (base_uint160)b; }
460 inline bool operator==(const base_uint160& a, const uint160& b)         { return (base_uint160)a == (base_uint160)b; }
461 inline bool operator!=(const base_uint160& a, const uint160& b)         { return (base_uint160)a != (base_uint160)b; }
462 inline const uint160 operator^(const base_uint160& a, const uint160& b) { return (base_uint160)a ^  (base_uint160)b; }
463 inline const uint160 operator&(const base_uint160& a, const uint160& b) { return (base_uint160)a &  (base_uint160)b; }
464 inline const uint160 operator|(const base_uint160& a, const uint160& b) { return (base_uint160)a |  (base_uint160)b; }
465 inline const uint160 operator+(const base_uint160& a, const uint160& b) { return (base_uint160)a +  (base_uint160)b; }
466 inline const uint160 operator-(const base_uint160& a, const uint160& b) { return (base_uint160)a -  (base_uint160)b; }
467
468 inline bool operator<(const uint160& a, const base_uint160& b)          { return (base_uint160)a <  (base_uint160)b; }
469 inline bool operator<=(const uint160& a, const base_uint160& b)         { return (base_uint160)a <= (base_uint160)b; }
470 inline bool operator>(const uint160& a, const base_uint160& b)          { return (base_uint160)a >  (base_uint160)b; }
471 inline bool operator>=(const uint160& a, const base_uint160& b)         { return (base_uint160)a >= (base_uint160)b; }
472 inline bool operator==(const uint160& a, const base_uint160& b)         { return (base_uint160)a == (base_uint160)b; }
473 inline bool operator!=(const uint160& a, const base_uint160& b)         { return (base_uint160)a != (base_uint160)b; }
474 inline const uint160 operator^(const uint160& a, const base_uint160& b) { return (base_uint160)a ^  (base_uint160)b; }
475 inline const uint160 operator&(const uint160& a, const base_uint160& b) { return (base_uint160)a &  (base_uint160)b; }
476 inline const uint160 operator|(const uint160& a, const base_uint160& b) { return (base_uint160)a |  (base_uint160)b; }
477 inline const uint160 operator+(const uint160& a, const base_uint160& b) { return (base_uint160)a +  (base_uint160)b; }
478 inline const uint160 operator-(const uint160& a, const base_uint160& b) { return (base_uint160)a -  (base_uint160)b; }
479
480 inline bool operator<(const uint160& a, const uint160& b)               { return (base_uint160)a <  (base_uint160)b; }
481 inline bool operator<=(const uint160& a, const uint160& b)              { return (base_uint160)a <= (base_uint160)b; }
482 inline bool operator>(const uint160& a, const uint160& b)               { return (base_uint160)a >  (base_uint160)b; }
483 inline bool operator>=(const uint160& a, const uint160& b)              { return (base_uint160)a >= (base_uint160)b; }
484 inline bool operator==(const uint160& a, const uint160& b)              { return (base_uint160)a == (base_uint160)b; }
485 inline bool operator!=(const uint160& a, const uint160& b)              { return (base_uint160)a != (base_uint160)b; }
486 inline const uint160 operator^(const uint160& a, const uint160& b)      { return (base_uint160)a ^  (base_uint160)b; }
487 inline const uint160 operator&(const uint160& a, const uint160& b)      { return (base_uint160)a &  (base_uint160)b; }
488 inline const uint160 operator|(const uint160& a, const uint160& b)      { return (base_uint160)a |  (base_uint160)b; }
489 inline const uint160 operator+(const uint160& a, const uint160& b)      { return (base_uint160)a +  (base_uint160)b; }
490 inline const uint160 operator-(const uint160& a, const uint160& b)      { return (base_uint160)a -  (base_uint160)b; }
491
492
493
494
495
496
497 //////////////////////////////////////////////////////////////////////////////
498 //
499 // uint256
500 //
501
502
503 /** Errors thrown by the uint256 class */
504 class uint256_error : public std::exception
505 {
506 public:
507         explicit uint256_error(const std::string& error_message)  : what_(error_message) {}
508
509         virtual const char* what() const throw () { return what_.c_str(); }
510         virtual ~uint256_error() throw () {}
511 private:
512         std::string what_; 
513 };
514
515 /** 256-bit unsigned integer */
516 class uint256 : public base_uint256
517 {
518 public:
519     typedef base_uint256 basetype;
520
521     uint256();
522     uint256(const basetype& b);
523     uint256& operator=(const basetype& b);
524     uint256(uint64_t b);
525     uint256& operator=(uint64_t b);
526     uint256& SetCompact(uint32_t nCompact, bool *pfNegative = NULL, bool *pfOverflow = NULL);
527     uint32_t GetCompact(bool fNegative = false) const;
528     uint256& operator*=(uint32_t b32);
529     uint256& operator*=(const uint256& b);
530     uint256& operator/=(const uint256& b);
531     explicit uint256(const std::string& str);
532     explicit uint256(const std::vector<unsigned char>& vch);
533 };
534
535 inline bool operator==(const uint256& a, uint64_t b)                           { return (base_uint256)a == b; }
536 inline bool operator!=(const uint256& a, uint64_t b)                           { return (base_uint256)a != b; }
537 inline const uint256 operator<<(const base_uint256& a, unsigned int shift)   { return uint256(a) <<= shift; }
538 inline const uint256 operator>>(const base_uint256& a, unsigned int shift)   { return uint256(a) >>= shift; }
539 inline const uint256 operator<<(const uint256& a, unsigned int shift)        { return uint256(a) <<= shift; }
540 inline const uint256 operator>>(const uint256& a, unsigned int shift)        { return uint256(a) >>= shift; }
541
542 inline const uint256 operator^(const base_uint256& a, const base_uint256& b) { return uint256(a) ^= b; }
543 inline const uint256 operator&(const base_uint256& a, const base_uint256& b) { return uint256(a) &= b; }
544 inline const uint256 operator|(const base_uint256& a, const base_uint256& b) { return uint256(a) |= b; }
545 inline const uint256 operator+(const base_uint256& a, const base_uint256& b) { return uint256(a) += b; }
546 inline const uint256 operator*(const base_uint256& a, const base_uint256& b) { return uint256(a) *= b; }
547 inline const uint256 operator/(const base_uint256& a, const base_uint256& b) { return uint256(a) /= b; }
548 inline const uint256 operator-(const base_uint256& a, const base_uint256& b) { return uint256(a) -= b; }
549
550 inline bool operator<(const base_uint256& a, const uint256& b)          { return (base_uint256)a <  (base_uint256)b; }
551 inline bool operator<=(const base_uint256& a, const uint256& b)         { return (base_uint256)a <= (base_uint256)b; }
552 inline bool operator>(const base_uint256& a, const uint256& b)          { return (base_uint256)a >  (base_uint256)b; }
553 inline bool operator>=(const base_uint256& a, const uint256& b)         { return (base_uint256)a >= (base_uint256)b; }
554 inline bool operator==(const base_uint256& a, const uint256& b)         { return (base_uint256)a == (base_uint256)b; }
555 inline bool operator!=(const base_uint256& a, const uint256& b)         { return (base_uint256)a != (base_uint256)b; }
556 inline const uint256 operator^(const base_uint256& a, const uint256& b) { return (base_uint256)a ^  (base_uint256)b; }
557 inline const uint256 operator&(const base_uint256& a, const uint256& b) { return (base_uint256)a &  (base_uint256)b; }
558 inline const uint256 operator|(const base_uint256& a, const uint256& b) { return (base_uint256)a |  (base_uint256)b; }
559 inline const uint256 operator+(const base_uint256& a, const uint256& b) { return (base_uint256)a +  (base_uint256)b; }
560 inline const uint256 operator*(const base_uint256& a, const uint256& b) { return (base_uint256)a *  (base_uint256)b; }
561 inline const uint256 operator/(const base_uint256& a, const uint256& b) { return (base_uint256)a /  (base_uint256)b; }
562 inline const uint256 operator-(const base_uint256& a, const uint256& b) { return (base_uint256)a -  (base_uint256)b; }
563
564 inline bool operator<(const uint256& a, const base_uint256& b)          { return (base_uint256)a <  (base_uint256)b; }
565 inline bool operator<=(const uint256& a, const base_uint256& b)         { return (base_uint256)a <= (base_uint256)b; }
566 inline bool operator>(const uint256& a, const base_uint256& b)          { return (base_uint256)a >  (base_uint256)b; }
567 inline bool operator>=(const uint256& a, const base_uint256& b)         { return (base_uint256)a >= (base_uint256)b; }
568 inline bool operator==(const uint256& a, const base_uint256& b)         { return (base_uint256)a == (base_uint256)b; }
569 inline bool operator!=(const uint256& a, const base_uint256& b)         { return (base_uint256)a != (base_uint256)b; }
570 inline const uint256 operator^(const uint256& a, const base_uint256& b) { return (base_uint256)a ^  (base_uint256)b; }
571 inline const uint256 operator&(const uint256& a, const base_uint256& b) { return (base_uint256)a &  (base_uint256)b; }
572 inline const uint256 operator|(const uint256& a, const base_uint256& b) { return (base_uint256)a |  (base_uint256)b; }
573 inline const uint256 operator+(const uint256& a, const base_uint256& b) { return (base_uint256)a +  (base_uint256)b; }
574 inline const uint256 operator-(const uint256& a, const base_uint256& b) { return (base_uint256)a -  (base_uint256)b; }
575
576 inline bool operator<(const uint256& a, const uint256& b)               { return (base_uint256)a <  (base_uint256)b; }
577 inline bool operator<=(const uint256& a, const uint256& b)              { return (base_uint256)a <= (base_uint256)b; }
578 inline bool operator>(const uint256& a, const uint256& b)               { return (base_uint256)a >  (base_uint256)b; }
579 inline bool operator>=(const uint256& a, const uint256& b)              { return (base_uint256)a >= (base_uint256)b; }
580 inline bool operator==(const uint256& a, const uint256& b)              { return (base_uint256)a == (base_uint256)b; }
581 inline bool operator!=(const uint256& a, const uint256& b)              { return (base_uint256)a != (base_uint256)b; }
582 inline const uint256 operator^(const uint256& a, const uint256& b)      { return (base_uint256)a ^  (base_uint256)b; }
583 inline const uint256 operator&(const uint256& a, const uint256& b)      { return (base_uint256)a &  (base_uint256)b; }
584 inline const uint256 operator|(const uint256& a, const uint256& b)      { return (base_uint256)a |  (base_uint256)b; }
585 inline const uint256 operator+(const uint256& a, const uint256& b)      { return (base_uint256)a +  (base_uint256)b; }
586 inline const uint256 operator-(const uint256& a, const uint256& b)      { return (base_uint256)a -  (base_uint256)b; }
587
588 #endif