release/src/router/mysql/extra/yassl/taocrypt/include/integer.hpp

   1 /*
   2    Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; version 2 of the License.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12
  13    You should have received a copy of the GNU General Public License
  14    along with this program; see the file COPYING. If not, write to the
  15    Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
  16    MA  02110-1301  USA.
  17 */
  18
  19 /* based on Wei Dai's integer.h from CryptoPP */
  20
  21
  22 #ifndef TAO_CRYPT_INTEGER_HPP
  23 #define TAO_CRYPT_INTEGER_HPP
  24
  25
  26 #ifdef _MSC_VER
  27     // 4250: dominance
  28     // 4660: explicitly instantiating a class already implicitly instantiated
  29     // 4661: no suitable definition provided for explicit template request
  30     // 4786: identifer was truncated in debug information
  31     // 4355: 'this' : used in base member initializer list
  32 #   pragma warning(disable: 4250 4660 4661 4786 4355)
  33 #endif
  34
  35
  36 #include "misc.hpp"
  37 #include "block.hpp"
  38 #include "random.hpp"
  39 #include "file.hpp"
  40 #include <string.h>
  41 #ifdef USE_SYS_STL
  42     #include <algorithm>
  43 #else
  44     #include "algorithm.hpp"
  45 #endif
  46
  47
  48 #ifdef TAOCRYPT_X86ASM_AVAILABLE
  49
  50 #ifdef _M_IX86
  51     #if (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 500)) || \
  52       (defined(__ICL) && (__ICL >= 500))
  53         #define SSE2_INTRINSICS_AVAILABLE
  54         #define TAOCRYPT_MM_MALLOC_AVAILABLE
  55     #elif defined(_MSC_VER)
  56         // _mm_free seems to be the only way to tell if the Processor Pack is
  57         //installed or not
  58         #include <malloc.h>
  59         #if defined(_mm_free)
  60             #define SSE2_INTRINSICS_AVAILABLE
  61             #define TAOCRYPT_MM_MALLOC_AVAILABLE
  62         #endif
  63     #endif
  64 #endif
  65
  66 // SSE2 intrinsics work in GCC 3.3 or later
  67 #if defined(__SSE2__) && (__GNUC__ == 4 || __GNUC_MAJOR__ > 3 ||  \
  68                           __GNUC_MINOR__ > 2)
  69     #define SSE2_INTRINSICS_AVAILABLE
  70 #endif
  71
  72 #endif  // X86ASM
  73
  74
  75
  76
  77 namespace TaoCrypt {
  78
  79 #if defined(SSE2_INTRINSICS_AVAILABLE)
  80
  81     // Allocator handling proper alignment
  82     template <class T>
  83     class AlignedAllocator : public AllocatorBase<T>
  84     {
  85     public:
  86         typedef typename AllocatorBase<T>::pointer   pointer;
  87         typedef typename AllocatorBase<T>::size_type size_type;
  88
  89         pointer allocate(size_type n, const void* = 0);
  90         void deallocate(void* p, size_type n);
  91         pointer reallocate(T* p, size_type oldSize, size_type newSize,
  92                            bool preserve)
  93         {
  94             return StdReallocate(*this, p, oldSize, newSize, preserve);
  95         }
  96
  97     #if !(defined(TAOCRYPT_MALLOC_ALIGNMENT_IS_16) || \
  98         defined(TAOCRYPT_MEMALIGN_AVAILABLE) || \
  99         defined(TAOCRYPT_MM_MALLOC_AVAILABLE))
 100     #define TAOCRYPT_NO_ALIGNED_ALLOC
 101         AlignedAllocator() : m_pBlock(0) {}
 102     protected:
 103         void *m_pBlock;
 104     #endif
 105     };
 106
 107     typedef Block<word, AlignedAllocator<word> > AlignedWordBlock;
 108 #else
 109     typedef WordBlock AlignedWordBlock;
 110 #endif
 111
 112
 113
 114 // general MAX
 115 template<typename T> inline
 116 const T& max(const T& a, const T& b)
 117 {
 118     return a > b ? a : b;
 119 }
 120
 121
 122 // Large Integer class
 123 class Integer {
 124 public:
 125         enum Sign {POSITIVE = 0, NEGATIVE = 1 };
 126         enum Signedness { UNSIGNED, SIGNED };
 127         enum RandomNumberType { ANY, PRIME };
 128
 129         class DivideByZero {};
 130
 131         Integer();
 132         Integer(const Integer& t);
 133         Integer(signed long value);
 134         Integer(Sign s, word highWord, word lowWord);
 135
 136         // BER Decode Source
 137         explicit Integer(Source&);
 138
 139         Integer(const byte* encodedInteger, unsigned int byteCount,
 140                 Signedness s = UNSIGNED);
 141
 142         ~Integer() {}
 143
 144         static const Integer& Zero();
 145         static const Integer& One();
 146
 147         Integer& Ref() { return *this; }
 148
 149         Integer(RandomNumberGenerator& rng, const Integer& min,
 150                 const Integer& max);
 151
 152         static Integer Power2(unsigned int e);
 153
 154         unsigned int MinEncodedSize(Signedness = UNSIGNED) const;
 155         unsigned int Encode(byte* output, unsigned int outputLen,
 156                             Signedness = UNSIGNED) const;
 157
 158         void Decode(const byte* input, unsigned int inputLen,
 159                     Signedness = UNSIGNED);
 160         void Decode(Source&);
 161
 162         bool  IsConvertableToLong() const;
 163         signed long ConvertToLong() const;
 164
 165         unsigned int BitCount() const;
 166         unsigned int ByteCount() const;
 167         unsigned int WordCount() const;
 168
 169         bool GetBit(unsigned int i) const;
 170         byte GetByte(unsigned int i) const;
 171         unsigned long GetBits(unsigned int i, unsigned int n) const;
 172
 173         bool IsZero()      const { return !*this; }
 174         bool NotZero()     const { return !IsZero(); }
 175         bool IsNegative()  const { return sign_ == NEGATIVE; }
 176         bool NotNegative() const { return !IsNegative(); }
 177         bool IsPositive()  const { return NotNegative() && NotZero(); }
 178         bool NotPositive() const { return !IsPositive(); }
 179         bool IsEven()      const { return GetBit(0) == 0; }
 180         bool IsOdd()       const { return GetBit(0) == 1; }
 181
 182         Integer&  operator=(const Integer& t);
 183         Integer&  operator+=(const Integer& t);
 184         Integer&  operator-=(const Integer& t);
 185         Integer&  operator*=(const Integer& t)  { return *this = Times(t); }
 186         Integer&  operator/=(const Integer& t)
 187                         { return *this = DividedBy(t);}
 188         Integer&  operator%=(const Integer& t)  { return *this = Modulo(t); }
 189         Integer&  operator/=(word t)  { return *this = DividedBy(t); }
 190         Integer&  operator%=(word t)  { return *this = Modulo(t); }
 191         Integer&  operator<<=(unsigned int);
 192         Integer&  operator>>=(unsigned int);
 193
 194
 195         void Randomize(RandomNumberGenerator &rng, unsigned int bitcount);
 196         void Randomize(RandomNumberGenerator &rng, const Integer &min,
 197                        const Integer &max);
 198
 199         void SetBit(unsigned int n, bool value = 1);
 200         void SetByte(unsigned int n, byte value);
 201
 202         void Negate();
 203         void SetPositive() { sign_ = POSITIVE; }
 204         void SetNegative() { if (!!(*this)) sign_ = NEGATIVE; }
 205         void Swap(Integer& a);
 206
 207         bool        operator!() const;
 208         Integer     operator+() const {return *this;}
 209         Integer     operator-() const;
 210         Integer&    operator++();
 211         Integer&    operator--();
 212         Integer     operator++(int)
 213             { Integer temp = *this; ++*this; return temp; }
 214         Integer     operator--(int)
 215             { Integer temp = *this; --*this; return temp; }
 216
 217         int Compare(const Integer& a) const;
 218
 219         Integer Plus(const Integer &b) const;
 220         Integer Minus(const Integer &b) const;
 221         Integer Times(const Integer &b) const;
 222         Integer DividedBy(const Integer &b) const;
 223         Integer Modulo(const Integer &b) const;
 224         Integer DividedBy(word b) const;
 225         word    Modulo(word b) const;
 226
 227         Integer operator>>(unsigned int n) const { return Integer(*this)>>=n; }
 228         Integer operator<<(unsigned int n) const { return Integer(*this)<<=n; }
 229
 230         Integer AbsoluteValue() const;
 231         Integer Doubled() const { return Plus(*this); }
 232         Integer Squared() const { return Times(*this); }
 233         Integer SquareRoot() const;
 234
 235         bool    IsSquare() const;
 236         bool    IsUnit() const;
 237
 238         Integer MultiplicativeInverse() const;
 239
 240         friend Integer a_times_b_mod_c(const Integer& x, const Integer& y,
 241                                        const Integer& m);
 242         friend Integer a_exp_b_mod_c(const Integer& x, const Integer& e,
 243                                      const Integer& m);
 244
 245         static void Divide(Integer& r, Integer& q, const Integer& a,
 246                            const Integer& d);
 247         static void Divide(word& r, Integer& q, const Integer& a, word d);
 248         static void DivideByPowerOf2(Integer& r, Integer& q, const Integer& a,
 249                                      unsigned int n);
 250         static Integer Gcd(const Integer& a, const Integer& n);
 251
 252         Integer InverseMod(const Integer& n) const;
 253         word InverseMod(word n) const;
 254
 255 private:
 256     friend class ModularArithmetic;
 257     friend class MontgomeryRepresentation;
 258
 259     Integer(word value, unsigned int length);
 260     int PositiveCompare(const Integer& t) const;
 261
 262     friend void PositiveAdd(Integer& sum, const Integer& a, const Integer& b);
 263     friend void PositiveSubtract(Integer& diff, const Integer& a,
 264                                  const Integer& b);
 265     friend void PositiveMultiply(Integer& product, const Integer& a,
 266                                  const Integer& b);
 267     friend void PositiveDivide(Integer& remainder, Integer& quotient, const
 268                                Integer& dividend, const Integer& divisor);
 269     AlignedWordBlock reg_;
 270     Sign             sign_;
 271 };
 272
 273 inline bool operator==(const Integer& a, const Integer& b)
 274                         {return a.Compare(b)==0;}
 275 inline bool operator!=(const Integer& a, const Integer& b)
 276                         {return a.Compare(b)!=0;}
 277 inline bool operator> (const Integer& a, const Integer& b)
 278                         {return a.Compare(b)> 0;}
 279 inline bool operator>=(const Integer& a, const Integer& b)
 280                         {return a.Compare(b)>=0;}
 281 inline bool operator< (const Integer& a, const Integer& b)
 282                         {return a.Compare(b)< 0;}
 283 inline bool operator<=(const Integer& a, const Integer& b)
 284                         {return a.Compare(b)<=0;}
 285
 286 inline Integer operator+(const Integer &a, const Integer &b)
 287                         {return a.Plus(b);}
 288 inline Integer operator-(const Integer &a, const Integer &b)
 289                         {return a.Minus(b);}
 290 inline Integer operator*(const Integer &a, const Integer &b)
 291                         {return a.Times(b);}
 292 inline Integer operator/(const Integer &a, const Integer &b)
 293                         {return a.DividedBy(b);}
 294 inline Integer operator%(const Integer &a, const Integer &b)
 295                         {return a.Modulo(b);}
 296 inline Integer operator/(const Integer &a, word b) {return a.DividedBy(b);}
 297 inline word    operator%(const Integer &a, word b) {return a.Modulo(b);}
 298
 299 inline void swap(Integer &a, Integer &b)
 300 {
 301     a.Swap(b);
 302 }
 303
 304
 305 Integer CRT(const Integer& xp, const Integer& p, const Integer& xq,
 306             const Integer& q,  const Integer& u);
 307
 308 inline Integer ModularExponentiation(const Integer& a, const Integer& e,
 309                                      const Integer& m)
 310 {
 311     return a_exp_b_mod_c(a, e, m);
 312 }
 313
 314 Integer ModularRoot(const Integer& a, const Integer& dp, const Integer& dq,
 315                     const Integer& p, const Integer& q,  const Integer& u);
 316
 317
 318
 319 }   // namespace
 320
 321 #endif // TAO_CRYPT_INTEGER_HPP