This library provides a way to easily handle arbitrary large integers.
This library provides the following operations :
- addition, substraction, multiplication, division and modulo
- bits operators (AND, OR, XOR, left and right shifts)
- boolean operators
- modular exponentiation (using montgomery algorithm)
- modular inverse
Example
In this example, we use a 1024 bits long RSA key to encrypt and decrypt a message. We first encrypt the value 0x41 (65 in decimal) and then decrypt it. At the end, m should be equal to 0x41. The encryption is fast (0, 4 second) while the decryption is really slow. This code will take between 30 seconds and 2 minutes to execute depending on the compiler and optimization flags.
main.cpp
#include "mbed.h" #include "BigInt.h" #include <stdlib.h> #include <stdio.h> uint8_t modbits[] = { 0xd9, 0x4d, 0x88, 0x9e, 0x88, 0x85, 0x3d, 0xd8, 0x97, 0x69, 0xa1, 0x80, 0x15, 0xa0, 0xa2, 0xe6, 0xbf, 0x82, 0xbf, 0x35, 0x6f, 0xe1, 0x4f, 0x25, 0x1f, 0xb4, 0xf5, 0xe2, 0xdf, 0x0d, 0x9f, 0x9a, 0x94, 0xa6, 0x8a, 0x30, 0xc4, 0x28, 0xb3, 0x9e, 0x33, 0x62, 0xfb, 0x37, 0x79, 0xa4, 0x97, 0xec, 0xea, 0xea, 0x37, 0x10, 0x0f, 0x26, 0x4d, 0x7f, 0xb9, 0xfb, 0x1a, 0x97, 0xfb, 0xf6, 0x21, 0x13, 0x3d, 0xe5, 0x5f, 0xdc, 0xb9, 0xb1, 0xad, 0x0d, 0x7a, 0x31, 0xb3, 0x79, 0x21, 0x6d, 0x79, 0x25, 0x2f, 0x5c, 0x52, 0x7b, 0x9b, 0xc6, 0x3d, 0x83, 0xd4, 0xec, 0xf4, 0xd1, 0xd4, 0x5c, 0xbf, 0x84, 0x3e, 0x84, 0x74, 0xba, 0xbc, 0x65, 0x5e, 0x9b, 0xb6, 0x79, 0x9c, 0xba, 0x77, 0xa4, 0x7e, 0xaf, 0xa8, 0x38, 0x29, 0x64, 0x74, 0xaf, 0xc2, 0x4b, 0xeb, 0x9c, 0x82, 0x5b, 0x73, 0xeb, 0xf5, 0x49 }; uint8_t dbits[] = { 0x04, 0x7b, 0x9c, 0xfd, 0xe8, 0x43, 0x17, 0x6b, 0x88, 0x74, 0x1d, 0x68, 0xcf, 0x09, 0x69, 0x52, 0xe9, 0x50, 0x81, 0x31, 0x51, 0x05, 0x8c, 0xe4, 0x6f, 0x2b, 0x04, 0x87, 0x91, 0xa2, 0x6e, 0x50, 0x7a, 0x10, 0x95, 0x79, 0x3c, 0x12, 0xba, 0xe1, 0xe0, 0x9d, 0x82, 0x21, 0x3a, 0xd9, 0x32, 0x69, 0x28, 0xcf, 0x7c, 0x23, 0x50, 0xac, 0xb1, 0x9c, 0x98, 0xf1, 0x9d, 0x32, 0xd5, 0x77, 0xd6, 0x66, 0xcd, 0x7b, 0xb8, 0xb2, 0xb5, 0xba, 0x62, 0x9d, 0x25, 0xcc, 0xf7, 0x2a, 0x5c, 0xeb, 0x8a, 0x8d, 0xa0, 0x38, 0x90, 0x6c, 0x84, 0xdc, 0xdb, 0x1f, 0xe6, 0x77, 0xdf, 0xfb, 0x2c, 0x02, 0x9f, 0xd8, 0x92, 0x63, 0x18, 0xee, 0xde, 0x1b, 0x58, 0x27, 0x2a, 0xf2, 0x2b, 0xda, 0x5c, 0x52, 0x32, 0xbe, 0x06, 0x68, 0x39, 0x39, 0x8e, 0x42, 0xf5, 0x35, 0x2d, 0xf5, 0x88, 0x48, 0xad, 0xad, 0x11, 0xa1 }; int main() { BigInt e = 65537, mod, d; mod.importData(modbits, sizeof(modbits)); d.importData(dbits, sizeof(dbits)); BigInt c = modPow(0x41,e,mod); c.print(); BigInt m = modPow(c,d,mod); m.print(); printf("done\n"); return 0; }
BigInt.cpp@3:3fa3ceb0c69d, 2013-09-20 (annotated)
- Committer:
- feb11
- Date:
- Fri Sep 20 15:55:19 2013 +0000
- Revision:
- 3:3fa3ceb0c69d
- Parent:
- 2:1001793a090d
- Child:
- 4:773aed3156c5
simplified code
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
feb11 | 0:9d554894785b | 1 | #include "BigInt.h" |
feb11 | 0:9d554894785b | 2 | #include <string.h> |
feb11 | 0:9d554894785b | 3 | #include <stdio.h> |
feb11 | 0:9d554894785b | 4 | #include <stdlib.h> |
feb11 | 0:9d554894785b | 5 | #include <iostream> |
feb11 | 0:9d554894785b | 6 | #include <climits> |
feb11 | 0:9d554894785b | 7 | |
feb11 | 0:9d554894785b | 8 | |
feb11 | 0:9d554894785b | 9 | static uint32_t max(const uint32_t a, const uint32_t b) |
feb11 | 0:9d554894785b | 10 | { |
feb11 | 0:9d554894785b | 11 | return a < b ? b : a; |
feb11 | 0:9d554894785b | 12 | } |
feb11 | 0:9d554894785b | 13 | |
feb11 | 0:9d554894785b | 14 | static uint32_t num(const uint32_t a) |
feb11 | 0:9d554894785b | 15 | { |
feb11 | 0:9d554894785b | 16 | return a/4 + (a%4 ? 1:0); |
feb11 | 0:9d554894785b | 17 | } |
feb11 | 0:9d554894785b | 18 | |
feb11 | 0:9d554894785b | 19 | BigInt::BigInt(): |
feb11 | 0:9d554894785b | 20 | size(0), |
feb11 | 0:9d554894785b | 21 | bits(0) |
feb11 | 0:9d554894785b | 22 | { |
feb11 | 0:9d554894785b | 23 | } |
feb11 | 0:9d554894785b | 24 | |
feb11 | 2:1001793a090d | 25 | BigInt::BigInt(const uint32_t a) |
feb11 | 2:1001793a090d | 26 | { |
feb11 | 2:1001793a090d | 27 | if(a >> 24) |
feb11 | 2:1001793a090d | 28 | size = 4; |
feb11 | 2:1001793a090d | 29 | else if(a >> 16) |
feb11 | 2:1001793a090d | 30 | size = 3; |
feb11 | 2:1001793a090d | 31 | else if(a >> 8) |
feb11 | 2:1001793a090d | 32 | size = 2; |
feb11 | 2:1001793a090d | 33 | else |
feb11 | 2:1001793a090d | 34 | size = 1; |
feb11 | 2:1001793a090d | 35 | bits = new uint32_t[1]; |
feb11 | 2:1001793a090d | 36 | bits[0] = a; |
feb11 | 2:1001793a090d | 37 | } |
feb11 | 2:1001793a090d | 38 | |
feb11 | 0:9d554894785b | 39 | BigInt::BigInt(const BigInt &a): |
feb11 | 0:9d554894785b | 40 | size(a.size) |
feb11 | 0:9d554894785b | 41 | { |
feb11 | 0:9d554894785b | 42 | uint32_t l = num(size); |
feb11 | 0:9d554894785b | 43 | bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 44 | for(int i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 45 | bits[i] = a.bits[i]; |
feb11 | 0:9d554894785b | 46 | } |
feb11 | 0:9d554894785b | 47 | |
feb11 | 0:9d554894785b | 48 | |
feb11 | 0:9d554894785b | 49 | BigInt::~BigInt() |
feb11 | 0:9d554894785b | 50 | { |
feb11 | 0:9d554894785b | 51 | if(bits) |
feb11 | 0:9d554894785b | 52 | delete[] bits; |
feb11 | 0:9d554894785b | 53 | bits = 0; |
feb11 | 0:9d554894785b | 54 | } |
feb11 | 0:9d554894785b | 55 | |
feb11 | 0:9d554894785b | 56 | BigInt& BigInt::operator=(const BigInt& a) |
feb11 | 0:9d554894785b | 57 | { |
feb11 | 0:9d554894785b | 58 | size = a.size; |
feb11 | 0:9d554894785b | 59 | uint32_t l = num(size); |
feb11 | 0:9d554894785b | 60 | if(bits) |
feb11 | 0:9d554894785b | 61 | delete[] bits; |
feb11 | 0:9d554894785b | 62 | bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 63 | for(int i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 64 | bits[i] = a.bits[i]; |
feb11 | 0:9d554894785b | 65 | return *this; |
feb11 | 0:9d554894785b | 66 | } |
feb11 | 0:9d554894785b | 67 | |
feb11 | 0:9d554894785b | 68 | void BigInt::import(uint8_t *data, uint32_t length) |
feb11 | 0:9d554894785b | 69 | { |
feb11 | 0:9d554894785b | 70 | size = length; |
feb11 | 0:9d554894785b | 71 | size_t l = size/4; |
feb11 | 0:9d554894785b | 72 | if(size % 4 != 0) |
feb11 | 0:9d554894785b | 73 | l++; |
feb11 | 0:9d554894785b | 74 | if(bits) |
feb11 | 0:9d554894785b | 75 | delete[] bits; |
feb11 | 0:9d554894785b | 76 | bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 77 | memset(bits, 0, sizeof(uint32_t)*l); |
feb11 | 0:9d554894785b | 78 | for(int i = 0; i < length; ++i) |
feb11 | 0:9d554894785b | 79 | bits[i/4] |= data[i] << ((i%4)*8); |
feb11 | 0:9d554894785b | 80 | } |
feb11 | 0:9d554894785b | 81 | |
feb11 | 0:9d554894785b | 82 | BigInt operator+(const BigInt &a, const BigInt& b) |
feb11 | 0:9d554894785b | 83 | { |
feb11 | 0:9d554894785b | 84 | BigInt result; |
feb11 | 0:9d554894785b | 85 | |
feb11 | 0:9d554894785b | 86 | result.size = a.size > b.size ? a.size : b.size; |
feb11 | 0:9d554894785b | 87 | size_t l = result.size/4; |
feb11 | 0:9d554894785b | 88 | if(result.size % 4 != 0) |
feb11 | 0:9d554894785b | 89 | l++; |
feb11 | 0:9d554894785b | 90 | result.bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 91 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 0:9d554894785b | 92 | uint32_t al = num(a.size); |
feb11 | 0:9d554894785b | 93 | uint32_t bl = num(b.size); |
feb11 | 0:9d554894785b | 94 | uint32_t carry = 0; |
feb11 | 0:9d554894785b | 95 | for(int i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 96 | { |
feb11 | 0:9d554894785b | 97 | uint32_t tmpA = 0, tmpB = 0; |
feb11 | 0:9d554894785b | 98 | if(i < al) |
feb11 | 0:9d554894785b | 99 | tmpA = a.bits[i]; |
feb11 | 0:9d554894785b | 100 | if(i < bl) |
feb11 | 0:9d554894785b | 101 | tmpB = b.bits[i]; |
feb11 | 0:9d554894785b | 102 | result.bits[i] = tmpA + tmpB + carry; |
feb11 | 0:9d554894785b | 103 | carry = result.bits[i] < max(tmpA, tmpB); |
feb11 | 0:9d554894785b | 104 | } |
feb11 | 0:9d554894785b | 105 | if(carry) |
feb11 | 0:9d554894785b | 106 | { |
feb11 | 0:9d554894785b | 107 | result.size++; |
feb11 | 0:9d554894785b | 108 | if(result.size > l*4) |
feb11 | 0:9d554894785b | 109 | { |
feb11 | 0:9d554894785b | 110 | l++; |
feb11 | 0:9d554894785b | 111 | result.bits = (uint32_t*)realloc(result.bits, l * sizeof(uint32_t)); |
feb11 | 0:9d554894785b | 112 | result.bits[l-1] = 0x00000001; |
feb11 | 0:9d554894785b | 113 | } |
feb11 | 0:9d554894785b | 114 | else |
feb11 | 0:9d554894785b | 115 | { |
feb11 | 0:9d554894785b | 116 | result.bits[l-1] += 1 << (8 *((result.size-1)%4)); |
feb11 | 0:9d554894785b | 117 | } |
feb11 | 0:9d554894785b | 118 | } |
feb11 | 0:9d554894785b | 119 | |
feb11 | 0:9d554894785b | 120 | return result; |
feb11 | 0:9d554894785b | 121 | } |
feb11 | 0:9d554894785b | 122 | |
feb11 | 0:9d554894785b | 123 | BigInt& BigInt::operator+=(const BigInt &b) |
feb11 | 0:9d554894785b | 124 | { |
feb11 | 0:9d554894785b | 125 | return (*this = (*this) + b); |
feb11 | 0:9d554894785b | 126 | } |
feb11 | 0:9d554894785b | 127 | |
feb11 | 0:9d554894785b | 128 | BigInt& BigInt::operator++() |
feb11 | 0:9d554894785b | 129 | { |
feb11 | 3:3fa3ceb0c69d | 130 | return (*this += 1); |
feb11 | 0:9d554894785b | 131 | } |
feb11 | 0:9d554894785b | 132 | |
feb11 | 0:9d554894785b | 133 | BigInt BigInt::operator++(int) |
feb11 | 0:9d554894785b | 134 | { |
feb11 | 0:9d554894785b | 135 | BigInt t = *this; |
feb11 | 3:3fa3ceb0c69d | 136 | *this += 1; |
feb11 | 0:9d554894785b | 137 | return t; |
feb11 | 0:9d554894785b | 138 | } |
feb11 | 0:9d554894785b | 139 | |
feb11 | 0:9d554894785b | 140 | // a - b, if b >= a, returns 0 |
feb11 | 0:9d554894785b | 141 | // No negative number allowed |
feb11 | 0:9d554894785b | 142 | BigInt operator-(const BigInt &a, const BigInt& b) |
feb11 | 0:9d554894785b | 143 | { |
feb11 | 0:9d554894785b | 144 | BigInt result; |
feb11 | 0:9d554894785b | 145 | |
feb11 | 0:9d554894785b | 146 | if(b >= a) |
feb11 | 0:9d554894785b | 147 | { |
feb11 | 3:3fa3ceb0c69d | 148 | return result = 0; |
feb11 | 0:9d554894785b | 149 | } |
feb11 | 0:9d554894785b | 150 | else |
feb11 | 0:9d554894785b | 151 | { |
feb11 | 0:9d554894785b | 152 | result.size = a.size; |
feb11 | 0:9d554894785b | 153 | uint32_t l = num(a.size); |
feb11 | 0:9d554894785b | 154 | result.bits = new uint32_t[l]; |
feb11 | 0:9d554894785b | 155 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 0:9d554894785b | 156 | uint32_t bl = num(b.size); |
feb11 | 0:9d554894785b | 157 | uint8_t borrow = 0; |
feb11 | 0:9d554894785b | 158 | for(uint32_t i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 159 | { |
feb11 | 0:9d554894785b | 160 | uint32_t tmpA = a.bits[i], tmpB = 0; |
feb11 | 0:9d554894785b | 161 | if(i < bl) |
feb11 | 0:9d554894785b | 162 | tmpB = b.bits[i]; |
feb11 | 0:9d554894785b | 163 | if(borrow) |
feb11 | 0:9d554894785b | 164 | { |
feb11 | 0:9d554894785b | 165 | if(tmpA == 0) |
feb11 | 0:9d554894785b | 166 | tmpA = ULONG_MAX; |
feb11 | 0:9d554894785b | 167 | else |
feb11 | 0:9d554894785b | 168 | --tmpA; |
feb11 | 0:9d554894785b | 169 | |
feb11 | 0:9d554894785b | 170 | if(tmpA < tmpB) |
feb11 | 0:9d554894785b | 171 | result.bits[i] = tmpA + 1 + (ULONG_MAX - tmpB); |
feb11 | 0:9d554894785b | 172 | else |
feb11 | 0:9d554894785b | 173 | result.bits[i] = tmpA - tmpB; |
feb11 | 0:9d554894785b | 174 | |
feb11 | 0:9d554894785b | 175 | if(a.bits[i] != 0 && tmpA > tmpB) |
feb11 | 0:9d554894785b | 176 | borrow = 0; |
feb11 | 0:9d554894785b | 177 | } |
feb11 | 0:9d554894785b | 178 | else |
feb11 | 0:9d554894785b | 179 | { |
feb11 | 0:9d554894785b | 180 | if(tmpA < tmpB) |
feb11 | 0:9d554894785b | 181 | result.bits[i] = tmpA + 1 + (ULONG_MAX - tmpB); |
feb11 | 0:9d554894785b | 182 | else |
feb11 | 0:9d554894785b | 183 | result.bits[i] = tmpA - tmpB; |
feb11 | 0:9d554894785b | 184 | borrow = tmpA < tmpB; |
feb11 | 0:9d554894785b | 185 | } |
feb11 | 0:9d554894785b | 186 | } |
feb11 | 0:9d554894785b | 187 | |
feb11 | 0:9d554894785b | 188 | // trim result |
feb11 | 0:9d554894785b | 189 | uint8_t *tmp = (uint8_t*)result.bits; |
feb11 | 0:9d554894785b | 190 | uint32_t newSize = result.size; |
feb11 | 0:9d554894785b | 191 | while(tmp[newSize-1] == 0 && newSize > 0) |
feb11 | 0:9d554894785b | 192 | newSize--; |
feb11 | 0:9d554894785b | 193 | result.size = newSize; |
feb11 | 0:9d554894785b | 194 | uint32_t tmpL = num(result.size); |
feb11 | 0:9d554894785b | 195 | if(tmpL < l) |
feb11 | 0:9d554894785b | 196 | result.bits = (uint32_t*)realloc(result.bits, sizeof(uint32_t)*tmpL); |
feb11 | 0:9d554894785b | 197 | |
feb11 | 0:9d554894785b | 198 | return result; |
feb11 | 0:9d554894785b | 199 | } |
feb11 | 0:9d554894785b | 200 | } |
feb11 | 0:9d554894785b | 201 | |
feb11 | 0:9d554894785b | 202 | BigInt& BigInt::operator-=(const BigInt &b) |
feb11 | 0:9d554894785b | 203 | { |
feb11 | 0:9d554894785b | 204 | return (*this = (*this) - b); |
feb11 | 0:9d554894785b | 205 | } |
feb11 | 0:9d554894785b | 206 | |
feb11 | 0:9d554894785b | 207 | BigInt& BigInt::operator--() |
feb11 | 0:9d554894785b | 208 | { |
feb11 | 3:3fa3ceb0c69d | 209 | return (*this -= 1); |
feb11 | 0:9d554894785b | 210 | } |
feb11 | 0:9d554894785b | 211 | |
feb11 | 0:9d554894785b | 212 | BigInt BigInt::operator--(int) |
feb11 | 0:9d554894785b | 213 | { |
feb11 | 0:9d554894785b | 214 | BigInt t = *this; |
feb11 | 3:3fa3ceb0c69d | 215 | *this -= 1; |
feb11 | 0:9d554894785b | 216 | return t; |
feb11 | 0:9d554894785b | 217 | } |
feb11 | 3:3fa3ceb0c69d | 218 | |
feb11 | 1:00f2c40d46ed | 219 | BigInt operator*(const BigInt &a, const BigInt& b) |
feb11 | 1:00f2c40d46ed | 220 | { |
feb11 | 1:00f2c40d46ed | 221 | BigInt result; |
feb11 | 1:00f2c40d46ed | 222 | |
feb11 | 1:00f2c40d46ed | 223 | // if a == 0 or b == 0 then result = 0 |
feb11 | 1:00f2c40d46ed | 224 | if(!a || !b) |
feb11 | 3:3fa3ceb0c69d | 225 | return result = 0; |
feb11 | 1:00f2c40d46ed | 226 | |
feb11 | 1:00f2c40d46ed | 227 | // if a == 1, then result = b |
feb11 | 3:3fa3ceb0c69d | 228 | if(a == 1) |
feb11 | 1:00f2c40d46ed | 229 | return (result = b); |
feb11 | 1:00f2c40d46ed | 230 | |
feb11 | 1:00f2c40d46ed | 231 | // if b == 1, then result = a |
feb11 | 3:3fa3ceb0c69d | 232 | if(b == 1) |
feb11 | 1:00f2c40d46ed | 233 | return (result = a); |
feb11 | 1:00f2c40d46ed | 234 | |
feb11 | 1:00f2c40d46ed | 235 | |
feb11 | 1:00f2c40d46ed | 236 | |
feb11 | 1:00f2c40d46ed | 237 | return result; |
feb11 | 1:00f2c40d46ed | 238 | } |
feb11 | 1:00f2c40d46ed | 239 | |
feb11 | 1:00f2c40d46ed | 240 | BigInt& BigInt::operator*=(const BigInt &b) |
feb11 | 1:00f2c40d46ed | 241 | { |
feb11 | 1:00f2c40d46ed | 242 | return (*this = (*this) * b); |
feb11 | 1:00f2c40d46ed | 243 | } |
feb11 | 1:00f2c40d46ed | 244 | |
feb11 | 1:00f2c40d46ed | 245 | BigInt operator>>(const BigInt &a, const uint32_t m) |
feb11 | 1:00f2c40d46ed | 246 | { |
feb11 | 1:00f2c40d46ed | 247 | BigInt result; |
feb11 | 1:00f2c40d46ed | 248 | if(m == 0) |
feb11 | 1:00f2c40d46ed | 249 | return result = a; |
feb11 | 1:00f2c40d46ed | 250 | if(m/8 >= a.size) |
feb11 | 3:3fa3ceb0c69d | 251 | return result = 0; |
feb11 | 1:00f2c40d46ed | 252 | |
feb11 | 1:00f2c40d46ed | 253 | result.size = a.size - m/8; |
feb11 | 1:00f2c40d46ed | 254 | result.bits = new uint32_t[num(result.size)]; |
feb11 | 1:00f2c40d46ed | 255 | uint8_t s = m%32; |
feb11 | 1:00f2c40d46ed | 256 | for(uint32_t i = 0; i < num(result.size); ++i) |
feb11 | 1:00f2c40d46ed | 257 | { |
feb11 | 1:00f2c40d46ed | 258 | if(m/32+i+1 < num(a.size)) |
feb11 | 1:00f2c40d46ed | 259 | result.bits[i] = (a.bits[m/32+i+1] << (32-s)) | (a.bits[m/32+i] >> s); |
feb11 | 1:00f2c40d46ed | 260 | else |
feb11 | 1:00f2c40d46ed | 261 | result.bits[i] = (a.bits[m/32+i] >> s); |
feb11 | 1:00f2c40d46ed | 262 | } |
feb11 | 1:00f2c40d46ed | 263 | |
feb11 | 1:00f2c40d46ed | 264 | |
feb11 | 1:00f2c40d46ed | 265 | return result; |
feb11 | 1:00f2c40d46ed | 266 | } |
feb11 | 1:00f2c40d46ed | 267 | |
feb11 | 1:00f2c40d46ed | 268 | BigInt& BigInt::operator>>=(const uint32_t m) |
feb11 | 1:00f2c40d46ed | 269 | { |
feb11 | 1:00f2c40d46ed | 270 | return *this = *this >> m; |
feb11 | 1:00f2c40d46ed | 271 | } |
feb11 | 1:00f2c40d46ed | 272 | |
feb11 | 1:00f2c40d46ed | 273 | BigInt operator<<(const BigInt &a, const uint32_t m) |
feb11 | 1:00f2c40d46ed | 274 | { |
feb11 | 1:00f2c40d46ed | 275 | BigInt result; |
feb11 | 1:00f2c40d46ed | 276 | |
feb11 | 1:00f2c40d46ed | 277 | if(m == 0) |
feb11 | 1:00f2c40d46ed | 278 | return result = a; |
feb11 | 1:00f2c40d46ed | 279 | |
feb11 | 1:00f2c40d46ed | 280 | result.size = m/8 + a.size; |
feb11 | 1:00f2c40d46ed | 281 | uint32_t h = a.bits[num(a.size)-1]; |
feb11 | 1:00f2c40d46ed | 282 | if((h << (m%32)) < h) |
feb11 | 1:00f2c40d46ed | 283 | ++result.size; |
feb11 | 1:00f2c40d46ed | 284 | uint32_t l = num(result.size); |
feb11 | 1:00f2c40d46ed | 285 | result.bits = new uint32_t[l]; |
feb11 | 1:00f2c40d46ed | 286 | memset(result.bits, 0, sizeof(uint32_t)*l); |
feb11 | 1:00f2c40d46ed | 287 | uint32_t s = m % 32; |
feb11 | 1:00f2c40d46ed | 288 | for(uint32_t i = 0; i < num(a.size); ++i) |
feb11 | 1:00f2c40d46ed | 289 | { |
feb11 | 1:00f2c40d46ed | 290 | if(i == 0) |
feb11 | 1:00f2c40d46ed | 291 | result.bits[m/32+i] = a.bits[i] << s; |
feb11 | 1:00f2c40d46ed | 292 | else |
feb11 | 1:00f2c40d46ed | 293 | result.bits[m/32+i] = (a.bits[i] << s) | (a.bits[i-1] >> (32-s)); |
feb11 | 1:00f2c40d46ed | 294 | } |
feb11 | 1:00f2c40d46ed | 295 | if(a.bits[num(a.size)-1] << s < a.bits[num(a.size)-1]) |
feb11 | 1:00f2c40d46ed | 296 | result.bits[num(result.size)-1] = a.bits[num(a.size)-1] >> (32-s); |
feb11 | 1:00f2c40d46ed | 297 | |
feb11 | 1:00f2c40d46ed | 298 | |
feb11 | 1:00f2c40d46ed | 299 | return result; |
feb11 | 1:00f2c40d46ed | 300 | } |
feb11 | 1:00f2c40d46ed | 301 | |
feb11 | 1:00f2c40d46ed | 302 | BigInt& BigInt::operator<<=(const uint32_t m) |
feb11 | 1:00f2c40d46ed | 303 | { |
feb11 | 1:00f2c40d46ed | 304 | return (*this = *this << m); |
feb11 | 1:00f2c40d46ed | 305 | } |
feb11 | 0:9d554894785b | 306 | |
feb11 | 0:9d554894785b | 307 | bool operator==(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 308 | { |
feb11 | 0:9d554894785b | 309 | if(a.size != b.size) |
feb11 | 0:9d554894785b | 310 | return false; |
feb11 | 0:9d554894785b | 311 | |
feb11 | 0:9d554894785b | 312 | uint32_t l = num(a.size); |
feb11 | 0:9d554894785b | 313 | for(int i = 0; i < l; ++i) |
feb11 | 0:9d554894785b | 314 | if(a.bits[i] != b.bits[i]) |
feb11 | 0:9d554894785b | 315 | return false; |
feb11 | 0:9d554894785b | 316 | return true; |
feb11 | 0:9d554894785b | 317 | } |
feb11 | 0:9d554894785b | 318 | |
feb11 | 0:9d554894785b | 319 | bool operator!=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 320 | { |
feb11 | 0:9d554894785b | 321 | return ! (a==b); |
feb11 | 0:9d554894785b | 322 | } |
feb11 | 0:9d554894785b | 323 | |
feb11 | 0:9d554894785b | 324 | bool operator<(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 325 | { |
feb11 | 0:9d554894785b | 326 | if(a.size < b.size) |
feb11 | 0:9d554894785b | 327 | return true; |
feb11 | 0:9d554894785b | 328 | if(a.size > b.size) |
feb11 | 0:9d554894785b | 329 | return false; |
feb11 | 0:9d554894785b | 330 | uint32_t l = num(a.size); |
feb11 | 0:9d554894785b | 331 | for(int i = l-1; i >= 0; --i) |
feb11 | 0:9d554894785b | 332 | if(a.bits[i] < b.bits[i]) |
feb11 | 0:9d554894785b | 333 | return true; |
feb11 | 0:9d554894785b | 334 | return false; |
feb11 | 0:9d554894785b | 335 | } |
feb11 | 0:9d554894785b | 336 | |
feb11 | 0:9d554894785b | 337 | bool operator<=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 338 | { |
feb11 | 0:9d554894785b | 339 | return (a < b) || (a == b); |
feb11 | 0:9d554894785b | 340 | } |
feb11 | 0:9d554894785b | 341 | |
feb11 | 0:9d554894785b | 342 | bool operator>(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 343 | { |
feb11 | 0:9d554894785b | 344 | if(a.size > b.size) |
feb11 | 0:9d554894785b | 345 | return true; |
feb11 | 0:9d554894785b | 346 | if(a.size < b.size) |
feb11 | 0:9d554894785b | 347 | return false; |
feb11 | 0:9d554894785b | 348 | uint32_t l = num(a.size); |
feb11 | 0:9d554894785b | 349 | for(int i = l-1; i >= 0; --i) |
feb11 | 0:9d554894785b | 350 | if(a.bits[i] > b.bits[i]) |
feb11 | 0:9d554894785b | 351 | return true; |
feb11 | 0:9d554894785b | 352 | return false; |
feb11 | 0:9d554894785b | 353 | } |
feb11 | 0:9d554894785b | 354 | |
feb11 | 0:9d554894785b | 355 | bool operator>=(const BigInt &a, const BigInt &b) |
feb11 | 0:9d554894785b | 356 | { |
feb11 | 0:9d554894785b | 357 | return (a > b) || (a == b); |
feb11 | 0:9d554894785b | 358 | } |
feb11 | 0:9d554894785b | 359 | |
feb11 | 1:00f2c40d46ed | 360 | bool operator!(const BigInt &a) |
feb11 | 0:9d554894785b | 361 | { |
feb11 | 1:00f2c40d46ed | 362 | if(a.size != 1) |
feb11 | 0:9d554894785b | 363 | return false; |
feb11 | 1:00f2c40d46ed | 364 | return a.bits[0] == 0; |
feb11 | 0:9d554894785b | 365 | } |
feb11 | 0:9d554894785b | 366 | |
feb11 | 0:9d554894785b | 367 | void BigInt::print() |
feb11 | 0:9d554894785b | 368 | { |
feb11 | 0:9d554894785b | 369 | printf("size: %d bytes\n", size); |
feb11 | 0:9d554894785b | 370 | uint32_t n = num(size); |
feb11 | 0:9d554894785b | 371 | for(int i = n-1; i >= 0; --i) |
feb11 | 0:9d554894785b | 372 | { |
feb11 | 1:00f2c40d46ed | 373 | printf("%08x ", bits[i]); |
feb11 | 0:9d554894785b | 374 | } |
feb11 | 0:9d554894785b | 375 | printf("\n"); |
feb11 | 0:9d554894785b | 376 | } |