monotone

monotone Mtn Source Tree

Root/cryptopp/integer.h

1#ifndef CRYPTOPP_INTEGER_H
2#define CRYPTOPP_INTEGER_H
3
4/** \file */
5
6#include "cryptlib.h"
7#include "secblock.h"
8
9#include <iosfwd>
10#include <algorithm>
11
12#ifdef _M_IX86
13#if (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 500)) || (defined(__ICL) && (__ICL >= 500))
14#define SSE2_INTRINSICS_AVAILABLE
15#elif defined(_MSC_VER)
16// _mm_free seems to be the only way to tell if the Processor Pack is installed or not
17#include <malloc.h>
18#if defined(_mm_free)
19#define SSE2_INTRINSICS_AVAILABLE
20#endif
21#endif
22#endif
23
24NAMESPACE_BEGIN(CryptoPP)
25
26#ifdef SSE2_INTRINSICS_AVAILABLE
27template <class T>
28class AlignedAllocator : public AllocatorBase<T>
29{
30public:
31CRYPTOPP_INHERIT_ALLOCATOR_TYPES
32
33pointer allocate(size_type n, const void *);
34void deallocate(void *p, size_type n);
35pointer reallocate(T *p, size_type oldSize, size_type newSize, bool preserve)
36{
37return StandardReallocate(*this, p, oldSize, newSize, preserve);
38}
39};
40typedef SecBlock<word, AlignedAllocator<word> > SecAlignedWordBlock;
41#else
42typedef SecWordBlock SecAlignedWordBlock;
43#endif
44
45//! multiple precision integer and basic arithmetics
46/*! This class can represent positive and negative integers
47with absolute value less than (256**sizeof(word)) ** (256**sizeof(int)).
48\nosubgrouping
49*/
50class Integer : public ASN1Object
51{
52public:
53//! \name ENUMS, EXCEPTIONS, and TYPEDEFS
54//@{
55//! division by zero exception
56class DivideByZero : public Exception
57{
58public:
59DivideByZero() : Exception(OTHER_ERROR, "Integer: division by zero") {}
60};
61
62//!
63class RandomNumberNotFound : public Exception
64{
65public:
66RandomNumberNotFound() : Exception(OTHER_ERROR, "Integer: no integer satisfies the given parameters") {}
67};
68
69//!
70enum Sign {POSITIVE=0, NEGATIVE=1};
71
72//!
73enum Signedness {
74//!
75UNSIGNED,
76//!
77SIGNED};
78
79//!
80enum RandomNumberType {
81//!
82ANY,
83//!
84PRIME};
85//@}
86
87//! \name CREATORS
88//@{
89//! creates the zero integer
90Integer();
91
92//! copy constructor
93Integer(const Integer& t);
94
95//! convert from signed long
96Integer(signed long value);
97
98//! convert from two words
99Integer(Sign s, word highWord, word lowWord);
100
101//! convert from string
102/*! str can be in base 2, 8, 10, or 16. Base is determined by a
103case insensitive suffix of 'h', 'o', or 'b'. No suffix means base 10.
104*/
105explicit Integer(const char *str);
106explicit Integer(const wchar_t *str);
107
108//! convert from big-endian byte array
109Integer(const byte *encodedInteger, unsigned int byteCount, Signedness s=UNSIGNED);
110
111//! convert from big-endian form stored in a BufferedTransformation
112Integer(BufferedTransformation &bt, unsigned int byteCount, Signedness s=UNSIGNED);
113
114//! convert from BER encoded byte array stored in a BufferedTransformation object
115explicit Integer(BufferedTransformation &bt);
116
117//! create a random integer
118/*! The random integer created is uniformly distributed over [0, 2**bitcount). */
119Integer(RandomNumberGenerator &rng, unsigned int bitcount);
120
121//! avoid calling constructors for these frequently used integers
122static const Integer &Zero();
123//! avoid calling constructors for these frequently used integers
124static const Integer &One();
125//! avoid calling constructors for these frequently used integers
126static const Integer &Two();
127
128//! create a random integer of special type
129/*! Ideally, the random integer created should be uniformly distributed
130over {x | min <= x <= max and x is of rnType and x % mod == equiv}.
131However the actual distribution may not be uniform because sequential
132search is used to find an appropriate number from a random starting
133point.
134May return (with very small probability) a pseudoprime when a prime
135is requested and max > lastSmallPrime*lastSmallPrime (lastSmallPrime
136is declared in nbtheory.h).
137\throw RandomNumberNotFound if the set is empty.
138*/
139Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType=ANY, const Integer &equiv=Zero(), const Integer &mod=One());
140
141//! return the integer 2**e
142static Integer Power2(unsigned int e);
143//@}
144
145//! \name ENCODE/DECODE
146//@{
147//! minimum number of bytes to encode this integer
148/*! MinEncodedSize of 0 is 1 */
149unsigned int MinEncodedSize(Signedness=UNSIGNED) const;
150//! encode in big-endian format
151/*! unsigned means encode absolute value, signed means encode two's complement if negative.
152if outputLen < MinEncodedSize, the most significant bytes will be dropped
153if outputLen > MinEncodedSize, the most significant bytes will be padded
154*/
155unsigned int Encode(byte *output, unsigned int outputLen, Signedness=UNSIGNED) const;
156//!
157unsigned int Encode(BufferedTransformation &bt, unsigned int outputLen, Signedness=UNSIGNED) const;
158
159//! encode using Distinguished Encoding Rules, put result into a BufferedTransformation object
160void DEREncode(BufferedTransformation &bt) const;
161
162//! encode absolute value as big-endian octet string
163void DEREncodeAsOctetString(BufferedTransformation &bt, unsigned int length) const;
164
165//! encode absolute value in OpenPGP format, return length of output
166unsigned int OpenPGPEncode(byte *output, unsigned int bufferSize) const;
167//! encode absolute value in OpenPGP format, put result into a BufferedTransformation object
168unsigned int OpenPGPEncode(BufferedTransformation &bt) const;
169
170//!
171void Decode(const byte *input, unsigned int inputLen, Signedness=UNSIGNED);
172//!
173//* Precondition: bt.MaxRetrievable() >= inputLen
174void Decode(BufferedTransformation &bt, unsigned int inputLen, Signedness=UNSIGNED);
175
176//!
177void BERDecode(const byte *input, unsigned int inputLen);
178//!
179void BERDecode(BufferedTransformation &bt);
180
181//! decode nonnegative value as big-endian octet string
182void BERDecodeAsOctetString(BufferedTransformation &bt, unsigned int length);
183
184class OpenPGPDecodeErr : public Exception
185{
186public:
187OpenPGPDecodeErr() : Exception(INVALID_DATA_FORMAT, "OpenPGP decode error") {}
188};
189
190//!
191void OpenPGPDecode(const byte *input, unsigned int inputLen);
192//!
193void OpenPGPDecode(BufferedTransformation &bt);
194//@}
195
196//! \name ACCESSORS
197//@{
198//! return true if *this can be represented as a signed long
199bool IsConvertableToLong() const;
200//! return equivalent signed long if possible, otherwise undefined
201signed long ConvertToLong() const;
202
203//! number of significant bits = floor(log2(abs(*this))) + 1
204unsigned int BitCount() const;
205//! number of significant bytes = ceiling(BitCount()/8)
206unsigned int ByteCount() const;
207//! number of significant words = ceiling(ByteCount()/sizeof(word))
208unsigned int WordCount() const;
209
210//! return the i-th bit, i=0 being the least significant bit
211bool GetBit(unsigned int i) const;
212//! return the i-th byte
213byte GetByte(unsigned int i) const;
214//! return n lowest bits of *this >> i
215unsigned long GetBits(unsigned int i, unsigned int n) const;
216
217//!
218bool IsZero() const {return !*this;}
219//!
220bool NotZero() const {return !IsZero();}
221//!
222bool IsNegative() const {return sign == NEGATIVE;}
223//!
224bool NotNegative() const {return !IsNegative();}
225//!
226bool IsPositive() const {return NotNegative() && NotZero();}
227//!
228bool NotPositive() const {return !IsPositive();}
229//!
230bool IsEven() const {return GetBit(0) == 0;}
231//!
232bool IsOdd() const{return GetBit(0) == 1;}
233//@}
234
235//! \name MANIPULATORS
236//@{
237//!
238Integer& operator=(const Integer& t);
239
240//!
241Integer& operator+=(const Integer& t);
242//!
243Integer& operator-=(const Integer& t);
244//!
245Integer& operator*=(const Integer& t){return *this = Times(t);}
246//!
247Integer& operator/=(const Integer& t){return *this = DividedBy(t);}
248//!
249Integer& operator%=(const Integer& t){return *this = Modulo(t);}
250//!
251Integer& operator/=(word t) {return *this = DividedBy(t);}
252//!
253Integer& operator%=(word t) {return *this = Modulo(t);}
254
255//!
256Integer& operator<<=(unsigned int);
257//!
258Integer& operator>>=(unsigned int);
259
260//!
261void Randomize(RandomNumberGenerator &rng, unsigned int bitcount);
262//!
263void Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max);
264//! set this Integer to a random element of {x | min <= x <= max and x is of rnType and x % mod == equiv}
265/*! returns false if the set is empty */
266bool Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv=Zero(), const Integer &mod=One());
267
268bool GenerateRandomNoThrow(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs);
269void GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &params = g_nullNameValuePairs)
270{
271if (!GenerateRandomNoThrow(rng, params))
272throw RandomNumberNotFound();
273}
274
275//! set the n-th bit to value
276void SetBit(unsigned int n, bool value=1);
277//! set the n-th byte to value
278void SetByte(unsigned int n, byte value);
279
280//!
281void Negate();
282//!
283void SetPositive() {sign = POSITIVE;}
284//!
285void SetNegative() {if (!!(*this)) sign = NEGATIVE;}
286
287//!
288void swap(Integer &a);
289//@}
290
291//! \name UNARY OPERATORS
292//@{
293//!
294booloperator!() const;
295//!
296Integer operator+() const {return *this;}
297//!
298Integer operator-() const;
299//!
300Integer&operator++();
301//!
302Integer&operator--();
303//!
304Integer operator++(int) {Integer temp = *this; ++*this; return temp;}
305//!
306Integer operator--(int) {Integer temp = *this; --*this; return temp;}
307//@}
308
309//! \name BINARY OPERATORS
310//@{
311//! signed comparison
312/*! \retval -1 if *this < a
313\retval 0 if *this = a
314\retval 1 if *this > a
315*/
316int Compare(const Integer& a) const;
317
318//!
319Integer Plus(const Integer &b) const;
320//!
321Integer Minus(const Integer &b) const;
322//!
323Integer Times(const Integer &b) const;
324//!
325Integer DividedBy(const Integer &b) const;
326//!
327Integer Modulo(const Integer &b) const;
328//!
329Integer DividedBy(word b) const;
330//!
331word Modulo(word b) const;
332
333//!
334Integer operator>>(unsigned int n) const{return Integer(*this)>>=n;}
335//!
336Integer operator<<(unsigned int n) const{return Integer(*this)<<=n;}
337//@}
338
339//! \name OTHER ARITHMETIC FUNCTIONS
340//@{
341//!
342Integer AbsoluteValue() const;
343//!
344Integer Doubled() const {return Plus(*this);}
345//!
346Integer Squared() const {return Times(*this);}
347//! extract square root, if negative return 0, else return floor of square root
348Integer SquareRoot() const;
349//! return whether this integer is a perfect square
350bool IsSquare() const;
351
352//! is 1 or -1
353bool IsUnit() const;
354//! return inverse if 1 or -1, otherwise return 0
355Integer MultiplicativeInverse() const;
356
357//! modular multiplication
358friend Integer a_times_b_mod_c(const Integer &x, const Integer& y, const Integer& m);
359//! modular exponentiation
360friend Integer a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
361
362//! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
363static void Divide(Integer &r, Integer &q, const Integer &a, const Integer &d);
364//! use a faster division algorithm when divisor is short
365static void Divide(word &r, Integer &q, const Integer &a, word d);
366
367//! returns same result as Divide(r, q, a, Power2(n)), but faster
368static void DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n);
369
370//! greatest common divisor
371static Integer Gcd(const Integer &a, const Integer &n);
372//! calculate multiplicative inverse of *this mod n
373Integer InverseMod(const Integer &n) const;
374//!
375word InverseMod(word n) const;
376//@}
377
378//! \name INPUT/OUTPUT
379//@{
380//!
381friend std::istream& operator>>(std::istream& in, Integer &a);
382//!
383friend std::ostream& operator<<(std::ostream& out, const Integer &a);
384//@}
385
386private:
387friend class ModularArithmetic;
388friend class MontgomeryRepresentation;
389friend class HalfMontgomeryRepresentation;
390
391Integer(word value, unsigned int length);
392
393int PositiveCompare(const Integer &t) const;
394friend void PositiveAdd(Integer &sum, const Integer &a, const Integer &b);
395friend void PositiveSubtract(Integer &diff, const Integer &a, const Integer &b);
396friend void PositiveMultiply(Integer &product, const Integer &a, const Integer &b);
397friend void PositiveDivide(Integer &remainder, Integer &quotient, const Integer &dividend, const Integer &divisor);
398
399SecAlignedWordBlock reg;
400Sign sign;
401};
402
403//!
404inline bool operator==(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)==0;}
405//!
406inline bool operator!=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)!=0;}
407//!
408inline bool operator> (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)> 0;}
409//!
410inline bool operator>=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)>=0;}
411//!
412inline bool operator< (const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)< 0;}
413//!
414inline bool operator<=(const CryptoPP::Integer& a, const CryptoPP::Integer& b) {return a.Compare(b)<=0;}
415//!
416inline CryptoPP::Integer operator+(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Plus(b);}
417//!
418inline CryptoPP::Integer operator-(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Minus(b);}
419//!
420inline CryptoPP::Integer operator*(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Times(b);}
421//!
422inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.DividedBy(b);}
423//!
424inline CryptoPP::Integer operator%(const CryptoPP::Integer &a, const CryptoPP::Integer &b) {return a.Modulo(b);}
425//!
426inline CryptoPP::Integer operator/(const CryptoPP::Integer &a, CryptoPP::word b) {return a.DividedBy(b);}
427//!
428inline CryptoPP::word operator%(const CryptoPP::Integer &a, CryptoPP::word b) {return a.Modulo(b);}
429
430NAMESPACE_END
431
432NAMESPACE_BEGIN(std)
433template<> inline void swap(CryptoPP::Integer &a, CryptoPP::Integer &b)
434{
435a.swap(b);
436}
437NAMESPACE_END
438
439#endif

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status