/usr/include/x86_64-linux-gnu/qcc/BigNum.h is in liballjoyn-common-dev-1509 15.09a-5.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 | #ifndef _BIGNUM_H
#define _BIGNUM_H
/**
* @file
*
* This file implements an arbitrary precision (big number) arithmetic class.
*/
/******************************************************************************
* Copyright AllSeen Alliance. All rights reserved.
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
******************************************************************************/
#include <qcc/platform.h>
#include <qcc/String.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#define BENCHMARKING
namespace qcc {
// This class implements arbitrary precision arithmetic.
class BigNum {
public:
// Default constructor - initializes the BigNum to zero
BigNum() : digits((uint32_t*) &zero_digit), length(1), neg(false), storage(NULL) { }
// Constructor that initializes a BigNum from a small integer value.
BigNum(uint32_t v);
// Copy constructor
BigNum(const BigNum& other);
// Assignment operator
BigNum& operator=(const BigNum& other);
// The constant value zero
static const BigNum zero;
// Generate a crypographically random number.
//
// @param len The length of the number in bytes.
void gen_rand(size_t len);
// Set value from a hexadecimal string
//@returns false if number was not a hex string
bool set_hex(const qcc::String& number);
// Set a (positive) value from a byte array in big-endian order.
// Use the negation operator to make the number negative.
//
// @param data The data to set
// @param len The length of the data
void set_bytes(const uint8_t* data, size_t len);
// Set value from a decimal string
//@returns false if number was not a decimal string
bool set_dec(const qcc::String& number);
// Render the value as a hexadecimal string
qcc::String get_hex(bool toLower = false) const;
// Render the value as bytes in big-endian order. The value is optionally zero padded (most
// significant bits) if the BigNum value is smaller than the length of buffer.
//
// @param data The buffer to receive the data.
// @param len The length of the buffer
// @param pad If true leading zeroes are added to fill the buffer.
//
// @return The number of bytes gotten.
size_t get_bytes(uint8_t* buffer, size_t len, bool pad = false) const;
// Addition operation
BigNum operator+(const BigNum& n) const;
// Monadic addition
BigNum& operator+=(const BigNum& n);
// Add an integer to an BigNum returning a new BigNum
BigNum operator+(uint32_t i) const;
// Monadic addtion of an integer to an BigNum
BigNum& operator+=(uint32_t i);
// Subtraction operation
BigNum operator-(const BigNum& n) const;
// Monadic subtraction
BigNum& operator-=(const BigNum& n);
// Subtract an integer from an BigNum
BigNum operator-(uint32_t i) const;
// Mondadic subtraction of an integer from an BigNum
BigNum& operator-=(uint32_t i);
// Negation
BigNum operator-() const;
// Absolute value
BigNum abs() const { return neg ? -(*this) : (*this); }
// Multiplication operation
BigNum operator*(const BigNum& n) const;
// Multiplication by an integer
BigNum operator*(uint32_t i) const;
// Division operation
//
// @param n The divisor
//
// @return The quotient after dividing this BigNum by the BigNum n.
BigNum operator/(const BigNum& n) const;
// Division by an integer
//
// @param i The divisor
//
// @return The quotient after dividing this BigNum by i.
//
BigNum operator/(uint32_t i) const;
// Modulus operation
//
// Reduce a bignum modulo the specified value. That is the remainder after dividing by m.
//
// @parm m The modulus.
//
// @return The remainder after division by the modulus
BigNum operator%(const BigNum& m) const;
// Exponentiation
//
// Raises a bignum to the specified power.
//
// @parm e The exponent (power) to raise the number to
//
// @return The new BigNum
BigNum exp(const BigNum& e) const;
// Less-than operator
bool operator<(const BigNum& n) const { return compare(*this, n) < 0; }
// Greater-than operator
bool operator>(const BigNum& n) const { return compare(*this, n) > 0; }
// Less-than-or-equal operator
bool operator<=(const BigNum& n) const { return compare(*this, n) <= 0; }
// Greater-than-or-equal operator
bool operator>=(const BigNum& n) const { return compare(*this, n) >= 0; }
// Equals operator
bool operator==(const BigNum& n) const { return compare(*this, n) == 0; }
// Not-equals operator
bool operator!=(const BigNum& n) const { return compare(*this, n) != 0; }
// Right-shift operator
//
// @param shift The number of bits for the shift
//
BigNum operator>>(uint32_t shift) const;
// In-place right-shift operator
//
// @param shift The number of bits for the shift
//
// @return Reference to this BigNum shifted right as specified
BigNum& operator>>=(uint32_t shift);
// Left-shift operator
//
// @param shift The number of bits for the shift
//
BigNum operator<<(uint32_t shift) const;
// In-place left-shift operator
//
// @param shift The number of bits for the shift
//
// @return Reference to this BigNum shifted left as specified
BigNum& operator<<=(uint32_t shift);
// Test if value is even
bool is_even() const { return !(digits[0] & 1); }
// Test if value is odd
bool is_odd() const { return (digits[0] & 1); }
// Modular exponentiation
//
// @param e The exponent
// @param mod The modulus
BigNum mod_exp(const BigNum& e, const BigNum& mod) const;
// Returns the bit length of this BigNum
size_t bit_len() const;
// Returns the byte (octet) length of this BigNum
size_t byte_len() const { return (7 + bit_len()) / 8; }
// Test if a specific bit is set.
bool test_bit(size_t index) const {
size_t d = index >> 5;
return (d < length) && (digits[d] & (1 << (index & 0x1F)));
}
// Destructor
~BigNum();
private:
// Montgomery multiplication
// @param r Returns the Montgomery product
// @param n The multiplicand
// @param m The modulus
// @param rho The inverse modulus
BigNum& monty_mul(BigNum& r, const BigNum& n, const BigNum& m, uint32_t rho) const;
// Mongtomery modular exponentiation
BigNum monty_mod_exp(const BigNum& n, const BigNum& mod) const;
// Count the trailing zeroes
uint32_t num_trailing_zeroes() const;
// Private constructor that allocates but doesn't initialize storage
BigNum(size_t len, bool neg);
// Makes a copy of an BigNum optionally adding extra (zero'd) space
BigNum clone(size_t extra = 0) const;
// Extend length zero padding most significant digits
BigNum& zero_ext(size_t size);
// reset an BigNum allocating storage if required
BigNum& reset(size_t len, bool neg = false, bool clear = true);
// compare two BigNums. Returns -1, 0, or 1
static int AJ_CALL compare(const BigNum& a, const BigNum& b);
// Remove leading zeroes
static BigNum& AJ_CALL strip_lz(BigNum& n) {
while (n.msdigit() == 0) {
if (n.length == 1) {
n.neg = false;
break;
} else {
--n.length;
}
}
return n;
}
// Right shift
static BigNum& AJ_CALL right_shift(BigNum& result, const BigNum& n, uint32_t shift);
// Multiplication by an integer putting result into an existing BigNum
static BigNum& AJ_CALL mul(BigNum& result, const BigNum& a, uint32_t b, bool neg);
// Multiplication putting result into an existing BigNum
static BigNum& AJ_CALL mul(BigNum& result, const BigNum& a, const BigNum& b);
// Division with remainder
BigNum div(const BigNum& y, BigNum& rem) const;
// Returns reference to the most significant digit
uint32_t& msdigit() const { return digits[length - 1]; }
// Check if value has unsuppressed leading zeroes
bool haslz() const { return length > 1 && digits[length - 1] == 0; }
// Convenience function for temporary values that don't own storage
BigNum& Set(uint32_t* newDigits, size_t digitsLength, bool negative = false) {
this->digits = newDigits;
this->length = digitsLength;
this->neg = negative;
this->storage = NULL;
return *this;
}
// Inplace subtraction for use with temporary values only
BigNum& sub(const BigNum& n, size_t shift = 0);
// Pointer to the digits array
uint32_t* digits;
// Length of the digits array
size_t length;
// True if the value is negative
bool neg;
// Opaque type for storage
class Storage;
// Pointer to storage
Storage* storage;
// Shared zero value
static uint32_t zero_digit;
};
}
#endif
|