<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>Crypto++: integer.cpp Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.3.7 -->
<div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical List</a> | <a class="qindex" href="annotated.html">Class List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="namespacemembers.html">Namespace Members</a> | <a class="qindex" href="functions.html">Class Members</a> | <a class="qindex" href="globals.html">File Members</a></div>
<h1>integer.cpp</h1><pre class="fragment"><div>00001 <span class="comment">// integer.cpp - written and placed in the public domain by Wei Dai</span>
00002 <span class="comment">// contains public domain code contributed by Alister Lee and Leonard Janke</span>
00003
00004 <span class="preprocessor">#include "pch.h"</span>
00005
00006 <span class="preprocessor">#ifndef CRYPTOPP_IMPORTS</span>
00007 <span class="preprocessor"></span>
00008 <span class="preprocessor">#include "<a class="code" href="integer_8h.html">integer.h</a>"</span>
00009 <span class="preprocessor">#include "modarith.h"</span>
00010 <span class="preprocessor">#include "nbtheory.h"</span>
00011 <span class="preprocessor">#include "asn.h"</span>
00012 <span class="preprocessor">#include "oids.h"</span>
00013 <span class="preprocessor">#include "words.h"</span>
00014 <span class="preprocessor">#include "algparam.h"</span>
00015 <span class="preprocessor">#include "<a class="code" href="pubkey_8h.html">pubkey.h</a>"</span> <span class="comment">// for P1363_KDF2</span>
00016 <span class="preprocessor">#include "sha.h"</span>
00017
00018 <span class="preprocessor">#include <iostream></span>
00019
00020 <span class="preprocessor">#ifdef SSE2_INTRINSICS_AVAILABLE</span>
00021 <span class="preprocessor"></span><span class="preprocessor"> #ifdef __GNUC__</span>
00022 <span class="preprocessor"></span><span class="preprocessor"> #include <xmmintrin.h></span>
00023 <span class="preprocessor"> #include <signal.h></span>
00024 <span class="preprocessor"> #include <setjmp.h></span>
00025 <span class="preprocessor"> #ifdef CRYPTOPP_MEMALIGN_AVAILABLE</span>
00026 <span class="preprocessor"></span><span class="preprocessor"> #include <malloc.h></span>
00027 <span class="preprocessor"> #else</span>
00028 <span class="preprocessor"></span><span class="preprocessor"> #include <stdlib.h></span>
00029 <span class="preprocessor"> #endif</span>
00030 <span class="preprocessor"></span><span class="preprocessor"> #else</span>
00031 <span class="preprocessor"></span><span class="preprocessor"> #include <emmintrin.h></span>
00032 <span class="preprocessor"> #endif</span>
00033 <span class="preprocessor"></span><span class="preprocessor">#elif defined(_MSC_VER) && defined(_M_IX86)</span>
00034 <span class="preprocessor"></span><span class="preprocessor"> #pragma message("You do not seem to have the Visual C++ Processor Pack installed, so use of SSE2 intrinsics will be disabled.")</span>
00035 <span class="preprocessor"></span><span class="preprocessor">#elif defined(__GNUC__) && defined(__i386__)</span>
00036 <span class="preprocessor"></span><span class="preprocessor"> #warning "You do not have GCC 3.3 or later, or did not specify -msse2 compiler option, so use of SSE2 intrinsics will be disabled."</span>
00037 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
00038 <span class="preprocessor"></span>
00039 NAMESPACE_BEGIN(CryptoPP)
00040
00041 bool FunctionAssignIntToInteger(const std::type_info &valueType, <span class="keywordtype">void</span> *pInteger, const <span class="keywordtype">void</span> *pInt)
00042 {
00043 <span class="keywordflow">if</span> (valueType != <span class="keyword">typeid</span>(<a class="code" href="class_integer.html">Integer</a>))
00044 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00045 *reinterpret_cast<Integer *>(pInteger) = *reinterpret_cast<const int *>(pInt);
00046 <span class="keywordflow">return</span> <span class="keyword">true</span>;
00047 }
00048
00049 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">char</span> s_RunAtStartup = (AssignIntToInteger = FunctionAssignIntToInteger, 0);
00050
00051 <span class="preprocessor">#ifdef SSE2_INTRINSICS_AVAILABLE</span>
00052 <span class="preprocessor"></span><span class="keyword">template</span> <<span class="keyword">class</span> T>
00053 CPP_TYPENAME AllocatorBase<T>::pointer AlignedAllocator<T>::allocate(size_type n, <span class="keyword">const</span> <span class="keywordtype">void</span> *)
00054 {
00055 CheckSize(n);
00056 <span class="keywordflow">if</span> (n == 0)
00057 <span class="keywordflow">return</span> NULL;
00058 <span class="keywordflow">if</span> (n >= 4)
00059 {
00060 <span class="keywordtype">void</span> *p;
00061 <span class="preprocessor"> #ifdef CRYPTOPP_MM_MALLOC_AVAILABLE</span>
00062 <span class="preprocessor"></span> <span class="keywordflow">while</span> (!(p = _mm_malloc(<span class="keyword">sizeof</span>(T)*n, 16)))
00063 <span class="preprocessor"> #elif defined(CRYPTOPP_MEMALIGN_AVAILABLE)</span>
00064 <span class="preprocessor"></span> <span class="keywordflow">while</span> (!(p = memalign(16, <span class="keyword">sizeof</span>(T)*n)))
00065 <span class="preprocessor"> #elif defined(CRYPTOPP_MALLOC_ALIGNMENT_IS_16)</span>
00066 <span class="preprocessor"></span> <span class="keywordflow">while</span> (!(p = malloc(<span class="keyword">sizeof</span>(T)*n)))
00067 <span class="preprocessor"> #else</span>
00068 <span class="preprocessor"></span> <span class="keywordflow">while</span> (!(p = (byte *)malloc(<span class="keyword">sizeof</span>(T)*n + 8))) <span class="comment">// assume malloc alignment is at least 8</span>
00069 <span class="preprocessor"> #endif</span>
00070 <span class="preprocessor"></span> CallNewHandler();
00071
00072 <span class="preprocessor"> #ifdef CRYPTOPP_NO_ALIGNED_ALLOC</span>
00073 <span class="preprocessor"></span> assert(m_pBlock == NULL);
00074 m_pBlock = p;
00075 <span class="keywordflow">if</span> (!IsAlignedOn(p, 16))
00076 {
00077 assert(IsAlignedOn(p, 8));
00078 p = (byte *)p + 8;
00079 }
00080 <span class="preprocessor"> #endif</span>
00081 <span class="preprocessor"></span>
00082 assert(IsAlignedOn(p, 16));
00083 <span class="keywordflow">return</span> (T*)p;
00084 }
00085 <span class="keywordflow">return</span> <span class="keyword">new</span> T[n];
00086 }
00087
00088 <span class="keyword">template</span> <<span class="keyword">class</span> T>
00089 <span class="keywordtype">void</span> AlignedAllocator<T>::deallocate(<span class="keywordtype">void</span> *p, size_type n)
00090 {
00091 memset(p, 0, n*<span class="keyword">sizeof</span>(T));
00092 <span class="keywordflow">if</span> (n >= 4)
00093 {
00094 <span class="preprocessor"> #ifdef CRYPTOPP_MM_MALLOC_AVAILABLE</span>
00095 <span class="preprocessor"></span> _mm_free(p);
00096 <span class="preprocessor"> #elif defined(CRYPTOPP_NO_ALIGNED_ALLOC)</span>
00097 <span class="preprocessor"></span> assert(m_pBlock == p || (byte *)m_pBlock+8 == p);
00098 free(m_pBlock);
00099 m_pBlock = NULL;
00100 <span class="preprocessor"> #else</span>
00101 <span class="preprocessor"></span> free(p);
00102 <span class="preprocessor"> #endif</span>
00103 <span class="preprocessor"></span> }
00104 <span class="keywordflow">else</span>
00105 <span class="keyword">delete</span> [] (T *)p;
00106 }
00107 <span class="preprocessor">#endif</span>
00108 <span class="preprocessor"></span>
00109 <span class="keyword">static</span> <span class="keywordtype">int</span> Compare(<span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
00110 {
00111 <span class="keywordflow">while</span> (N--)
00112 <span class="keywordflow">if</span> (A[N] > B[N])
00113 <span class="keywordflow">return</span> 1;
00114 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (A[N] < B[N])
00115 <span class="keywordflow">return</span> -1;
00116
00117 <span class="keywordflow">return</span> 0;
00118 }
00119
00120 <span class="keyword">static</span> word Increment(word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N, word B=1)
00121 {
00122 assert(N);
00123 word t = A[0];
00124 A[0] = t+B;
00125 <span class="keywordflow">if</span> (A[0] >= t)
00126 <span class="keywordflow">return</span> 0;
00127 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=1; i<N; i++)
00128 <span class="keywordflow">if</span> (++A[i])
00129 <span class="keywordflow">return</span> 0;
00130 <span class="keywordflow">return</span> 1;
00131 }
00132
00133 <span class="keyword">static</span> word Decrement(word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N, word B=1)
00134 {
00135 assert(N);
00136 word t = A[0];
00137 A[0] = t-B;
00138 <span class="keywordflow">if</span> (A[0] <= t)
00139 <span class="keywordflow">return</span> 0;
00140 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=1; i<N; i++)
00141 <span class="keywordflow">if</span> (A[i]--)
00142 <span class="keywordflow">return</span> 0;
00143 <span class="keywordflow">return</span> 1;
00144 }
00145
00146 <span class="keyword">static</span> <span class="keywordtype">void</span> TwosComplement(word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
00147 {
00148 Decrement(A, N);
00149 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=0; i<N; i++)
00150 A[i] = ~A[i];
00151 }
00152
00153 <span class="keyword">static</span> word AtomicInverseModPower2(word A)
00154 {
00155 assert(A%2==1);
00156
00157 word R=A%8;
00158
00159 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=3; i<WORD_BITS; i*=2)
00160 R = R*(2-R*A);
00161
00162 assert(R*A==1);
00163 <span class="keywordflow">return</span> R;
00164 }
00165
00166 <span class="comment">// ********************************************************</span>
00167
00168 <span class="keyword">class </span>DWord
00169 {
00170 <span class="keyword">public</span>:
00171 DWord() {}
00172
00173 <span class="preprocessor">#ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00174 <span class="preprocessor"></span> <span class="keyword">explicit</span> DWord(word low)
00175 {
00176 m_whole = low;
00177 }
00178 <span class="preprocessor">#else</span>
00179 <span class="preprocessor"></span> <span class="keyword">explicit</span> DWord(word low)
00180 {
00181 m_halfs.low = low;
00182 m_halfs.high = 0;
00183 }
00184 <span class="preprocessor">#endif</span>
00185 <span class="preprocessor"></span>
00186 DWord(word low, word high)
00187 {
00188 m_halfs.low = low;
00189 m_halfs.high = high;
00190 }
00191
00192 <span class="keyword">static</span> DWord Multiply(word a, word b)
00193 {
00194 DWord r;
00195 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00196 <span class="preprocessor"></span> r.m_whole = (dword)a * b;
00197 <span class="preprocessor"> #elif defined(__alpha__)</span>
00198 <span class="preprocessor"></span> r.m_halfs.low = a*b; __asm__(<span class="stringliteral">"umulh %1,%2,%0"</span> : <span class="stringliteral">"=r"</span> (r.m_halfs.high) : <span class="stringliteral">"r"</span> (a), <span class="stringliteral">"r"</span> (b));
00199 <span class="preprocessor"> #elif defined(__ia64__)</span>
00200 <span class="preprocessor"></span> r.m_halfs.low = a*b; __asm__(<span class="stringliteral">"xmpy.hu %0=%1,%2"</span> : <span class="stringliteral">"=f"</span> (r.m_halfs.high) : <span class="stringliteral">"f"</span> (a), <span class="stringliteral">"f"</span> (b));
00201 <span class="preprocessor"> #elif defined(_ARCH_PPC64)</span>
00202 <span class="preprocessor"></span> r.m_halfs.low = a*b; __asm__(<span class="stringliteral">"mulhdu %0,%1,%2"</span> : <span class="stringliteral">"=r"</span> (r.m_halfs.high) : <span class="stringliteral">"r"</span> (a), <span class="stringliteral">"r"</span> (b) : <span class="stringliteral">"cc"</span>);
00203 <span class="preprocessor"> #elif defined(__x86_64__)</span>
00204 <span class="preprocessor"></span> __asm__(<span class="stringliteral">"mulq %3"</span> : <span class="stringliteral">"=d"</span> (r.m_halfs.high), <span class="stringliteral">"=a"</span> (r.m_halfs.low) : <span class="stringliteral">"a"</span> (a), <span class="stringliteral">"rm"</span> (b) : <span class="stringliteral">"cc"</span>);
00205 <span class="preprocessor"> #elif defined(__mips64)</span>
00206 <span class="preprocessor"></span> __asm__(<span class="stringliteral">"dmultu %2,%3"</span> : <span class="stringliteral">"=h"</span> (r.m_halfs.high), <span class="stringliteral">"=l"</span> (r.m_halfs.low) : <span class="stringliteral">"r"</span> (a), <span class="stringliteral">"r"</span> (b));
00207 <span class="preprocessor"> #elif defined(_M_IX86)</span>
00208 <span class="preprocessor"></span> <span class="comment">// for testing</span>
00209 word64 t = (word64)a * b;
00210 r.m_halfs.high = ((word32 *)(&t))[1];
00211 r.m_halfs.low = (word32)t;
00212 <span class="preprocessor"> #else</span>
00213 <span class="preprocessor"></span><span class="preprocessor"> #error can not implement DWord</span>
00214 <span class="preprocessor"></span><span class="preprocessor"> #endif</span>
00215 <span class="preprocessor"></span> <span class="keywordflow">return</span> r;
00216 }
00217
00218 <span class="keyword">static</span> DWord MultiplyAndAdd(word a, word b, word c)
00219 {
00220 DWord r = Multiply(a, b);
00221 <span class="keywordflow">return</span> r += c;
00222 }
00223
00224 DWord & operator+=(word a)
00225 {
00226 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00227 <span class="preprocessor"></span> m_whole = m_whole + a;
00228 <span class="preprocessor"> #else</span>
00229 <span class="preprocessor"></span> m_halfs.low += a;
00230 m_halfs.high += (m_halfs.low < a);
00231 <span class="preprocessor"> #endif</span>
00232 <span class="preprocessor"></span> <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00233 }
00234
00235 DWord operator+(word a)
00236 {
00237 DWord r;
00238 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00239 <span class="preprocessor"></span> r.m_whole = m_whole + a;
00240 <span class="preprocessor"> #else</span>
00241 <span class="preprocessor"></span> r.m_halfs.low = m_halfs.low + a;
00242 r.m_halfs.high = m_halfs.high + (r.m_halfs.low < a);
00243 <span class="preprocessor"> #endif</span>
00244 <span class="preprocessor"></span> <span class="keywordflow">return</span> r;
00245 }
00246
00247 DWord operator-(DWord a)
00248 {
00249 DWord r;
00250 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00251 <span class="preprocessor"></span> r.m_whole = m_whole - a.m_whole;
00252 <span class="preprocessor"> #else</span>
00253 <span class="preprocessor"></span> r.m_halfs.low = m_halfs.low - a.m_halfs.low;
00254 r.m_halfs.high = m_halfs.high - a.m_halfs.high - (r.m_halfs.low > m_halfs.low);
00255 <span class="preprocessor"> #endif</span>
00256 <span class="preprocessor"></span> <span class="keywordflow">return</span> r;
00257 }
00258
00259 DWord operator-(word a)
00260 {
00261 DWord r;
00262 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00263 <span class="preprocessor"></span> r.m_whole = m_whole - a;
00264 <span class="preprocessor"> #else</span>
00265 <span class="preprocessor"></span> r.m_halfs.low = m_halfs.low - a;
00266 r.m_halfs.high = m_halfs.high - (r.m_halfs.low > m_halfs.low);
00267 <span class="preprocessor"> #endif</span>
00268 <span class="preprocessor"></span> <span class="keywordflow">return</span> r;
00269 }
00270
00271 <span class="comment">// returns quotient, which must fit in a word</span>
00272 word operator/(word divisor);
00273
00274 word operator%(word a);
00275
00276 <span class="keywordtype">bool</span> operator!()<span class="keyword"> const</span>
00277 <span class="keyword"> </span>{
00278 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00279 <span class="preprocessor"></span> <span class="keywordflow">return</span> !m_whole;
00280 <span class="preprocessor"> #else</span>
00281 <span class="preprocessor"></span> <span class="keywordflow">return</span> !m_halfs.high && !m_halfs.low;
00282 <span class="preprocessor"> #endif</span>
00283 <span class="preprocessor"></span> }
00284
00285 word GetLowHalf()<span class="keyword"> const </span>{<span class="keywordflow">return</span> m_halfs.low;}
00286 word GetHighHalf()<span class="keyword"> const </span>{<span class="keywordflow">return</span> m_halfs.high;}
00287 word GetHighHalfAsBorrow()<span class="keyword"> const </span>{<span class="keywordflow">return</span> 0-m_halfs.high;}
00288
00289 <span class="keyword">private</span>:
00290 <span class="keyword">union</span>
00291 <span class="keyword"> </span>{
00292 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00293 <span class="preprocessor"></span> dword m_whole;
00294 <span class="preprocessor"> #endif</span>
00295 <span class="preprocessor"></span> <span class="keyword">struct</span>
00296 <span class="keyword"> </span>{
00297 <span class="preprocessor"> #ifdef IS_LITTLE_ENDIAN</span>
00298 <span class="preprocessor"></span> word low;
00299 word high;
00300 <span class="preprocessor"> #else</span>
00301 <span class="preprocessor"></span> word high;
00302 word low;
00303 <span class="preprocessor"> #endif</span>
00304 <span class="preprocessor"></span> } m_halfs;
00305 };
00306 };
00307
00308 <span class="keyword">class </span>Word
00309 {
00310 <span class="keyword">public</span>:
00311 Word() {}
00312
00313 Word(word value)
00314 {
00315 m_whole = value;
00316 }
00317
00318 Word(hword low, hword high)
00319 {
00320 m_whole = low | (word(high) << (WORD_BITS/2));
00321 }
00322
00323 <span class="keyword">static</span> Word Multiply(hword a, hword b)
00324 {
00325 Word r;
00326 r.m_whole = (word)a * b;
00327 <span class="keywordflow">return</span> r;
00328 }
00329
00330 Word operator-(Word a)
00331 {
00332 Word r;
00333 r.m_whole = m_whole - a.m_whole;
00334 <span class="keywordflow">return</span> r;
00335 }
00336
00337 Word operator-(hword a)
00338 {
00339 Word r;
00340 r.m_whole = m_whole - a;
00341 <span class="keywordflow">return</span> r;
00342 }
00343
00344 <span class="comment">// returns quotient, which must fit in a word</span>
00345 hword operator/(hword divisor)
00346 {
00347 <span class="keywordflow">return</span> hword(m_whole / divisor);
00348 }
00349
00350 <span class="keywordtype">bool</span> operator!()<span class="keyword"> const</span>
00351 <span class="keyword"> </span>{
00352 <span class="keywordflow">return</span> !m_whole;
00353 }
00354
00355 word GetWhole()<span class="keyword"> const </span>{<span class="keywordflow">return</span> m_whole;}
00356 hword GetLowHalf()<span class="keyword"> const </span>{<span class="keywordflow">return</span> hword(m_whole);}
00357 hword GetHighHalf()<span class="keyword"> const </span>{<span class="keywordflow">return</span> hword(m_whole>>(WORD_BITS/2));}
00358 hword GetHighHalfAsBorrow()<span class="keyword"> const </span>{<span class="keywordflow">return</span> 0-hword(m_whole>>(WORD_BITS/2));}
00359
00360 <span class="keyword">private</span>:
00361 word m_whole;
00362 };
00363
00364 <span class="comment">// do a 3 word by 2 word divide, returns quotient and leaves remainder in A</span>
00365 <span class="keyword">template</span> <<span class="keyword">class</span> S, <span class="keyword">class</span> D>
00366 S DivideThreeWordsByTwo(S *A, S B0, S B1, D *dummy=NULL)
00367 {
00368 <span class="comment">// assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a S</span>
00369 assert(A[2] < B1 || (A[2]==B1 && A[1] < B0));
00370
00371 <span class="comment">// estimate the quotient: do a 2 S by 1 S divide</span>
00372 S Q;
00373 <span class="keywordflow">if</span> (S(B1+1) == 0)
00374 Q = A[2];
00375 <span class="keywordflow">else</span>
00376 Q = D(A[1], A[2]) / S(B1+1);
00377
00378 <span class="comment">// now subtract Q*B from A</span>
00379 D p = D::Multiply(B0, Q);
00380 D u = (D) A[0] - p.GetLowHalf();
00381 A[0] = u.GetLowHalf();
00382 u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - D::Multiply(B1, Q);
00383 A[1] = u.GetLowHalf();
00384 A[2] += u.GetHighHalf();
00385
00386 <span class="comment">// Q <= actual quotient, so fix it</span>
00387 <span class="keywordflow">while</span> (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
00388 {
00389 u = (D) A[0] - B0;
00390 A[0] = u.GetLowHalf();
00391 u = (D) A[1] - B1 - u.GetHighHalfAsBorrow();
00392 A[1] = u.GetLowHalf();
00393 A[2] += u.GetHighHalf();
00394 Q++;
00395 assert(Q); <span class="comment">// shouldn't overflow</span>
00396 }
00397
00398 <span class="keywordflow">return</span> Q;
00399 }
00400
00401 <span class="comment">// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1</span>
00402 <span class="keyword">template</span> <<span class="keyword">class</span> S, <span class="keyword">class</span> D>
00403 <span class="keyword">inline</span> D DivideFourWordsByTwo(S *T, <span class="keyword">const</span> D &Al, <span class="keyword">const</span> D &Ah, <span class="keyword">const</span> D &B)
00404 {
00405 <span class="keywordflow">if</span> (!B) <span class="comment">// if divisor is 0, we assume divisor==2**(2*WORD_BITS)</span>
00406 <span class="keywordflow">return</span> D(Ah.GetLowHalf(), Ah.GetHighHalf());
00407 <span class="keywordflow">else</span>
00408 {
00409 S Q[2];
00410 T[0] = Al.GetLowHalf();
00411 T[1] = Al.GetHighHalf();
00412 T[2] = Ah.GetLowHalf();
00413 T[3] = Ah.GetHighHalf();
00414 Q[1] = DivideThreeWordsByTwo<S, D>(T+1, B.GetLowHalf(), B.GetHighHalf());
00415 Q[0] = DivideThreeWordsByTwo<S, D>(T, B.GetLowHalf(), B.GetHighHalf());
00416 <span class="keywordflow">return</span> D(Q[0], Q[1]);
00417 }
00418 }
00419
00420 <span class="comment">// returns quotient, which must fit in a word</span>
00421 <span class="keyword">inline</span> word DWord::operator/(word a)
00422 {
00423 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00424 <span class="preprocessor"></span> <span class="keywordflow">return</span> word(m_whole / a);
00425 <span class="preprocessor"> #else</span>
00426 <span class="preprocessor"></span> hword r[4];
00427 <span class="keywordflow">return</span> DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a).GetWhole();
00428 <span class="preprocessor"> #endif</span>
00429 <span class="preprocessor"></span>}
00430
00431 <span class="keyword">inline</span> word DWord::operator%(word a)
00432 {
00433 <span class="preprocessor"> #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE</span>
00434 <span class="preprocessor"></span> <span class="keywordflow">return</span> word(m_whole % a);
00435 <span class="preprocessor"> #else</span>
00436 <span class="preprocessor"></span> <span class="keywordflow">if</span> (a < (word(1) << (WORD_BITS/2)))
00437 {
00438 hword h = hword(a);
00439 word r = m_halfs.high % h;
00440 r = ((m_halfs.low >> (WORD_BITS/2)) + (r << (WORD_BITS/2))) % h;
00441 <span class="keywordflow">return</span> hword((hword(m_halfs.low) + (r << (WORD_BITS/2))) % h);
00442 }
00443 <span class="keywordflow">else</span>
00444 {
00445 hword r[4];
00446 DivideFourWordsByTwo<hword, Word>(r, m_halfs.low, m_halfs.high, a);
00447 <span class="keywordflow">return</span> Word(r[0], r[1]).GetWhole();
00448 }
00449 <span class="preprocessor"> #endif</span>
00450 <span class="preprocessor"></span>}
00451
00452 <span class="comment">// ********************************************************</span>
00453
00454 <span class="keyword">class </span>Portable
00455 {
00456 <span class="keyword">public</span>:
00457 <span class="keyword">static</span> word Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N);
00458 <span class="keyword">static</span> word Subtract(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N);
00459
00460 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> Multiply2(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00461 <span class="keyword">static</span> <span class="keyword">inline</span> word Multiply2Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00462 <span class="keyword">static</span> <span class="keywordtype">void</span> Multiply4(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00463 <span class="keyword">static</span> <span class="keywordtype">void</span> Multiply8(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00464 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> MultiplyRecursionLimit() {<span class="keywordflow">return</span> 8;}
00465
00466 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> Multiply2Bottom(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00467 <span class="keyword">static</span> <span class="keywordtype">void</span> Multiply4Bottom(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00468 <span class="keyword">static</span> <span class="keywordtype">void</span> Multiply8Bottom(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00469 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> MultiplyBottomRecursionLimit() {<span class="keywordflow">return</span> 8;}
00470
00471 <span class="keyword">static</span> <span class="keywordtype">void</span> Square2(word *R, <span class="keyword">const</span> word *A);
00472 <span class="keyword">static</span> <span class="keywordtype">void</span> Square4(word *R, <span class="keyword">const</span> word *A);
00473 <span class="keyword">static</span> <span class="keywordtype">void</span> Square8(word *R, <span class="keyword">const</span> word *A) {assert(<span class="keyword">false</span>);}
00474 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> SquareRecursionLimit() {<span class="keywordflow">return</span> 4;}
00475 };
00476
00477 word Portable::Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
00478 {
00479 assert (N%2 == 0);
00480
00481 DWord u(0, 0);
00482 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = 0; i < N; i+=2)
00483 {
00484 u = DWord(A[i]) + B[i] + u.GetHighHalf();
00485 C[i] = u.GetLowHalf();
00486 u = DWord(A[i+1]) + B[i+1] + u.GetHighHalf();
00487 C[i+1] = u.GetLowHalf();
00488 }
00489 <span class="keywordflow">return</span> u.GetHighHalf();
00490 }
00491
00492 word Portable::Subtract(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
00493 {
00494 assert (N%2 == 0);
00495
00496 DWord u(0, 0);
00497 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = 0; i < N; i+=2)
00498 {
00499 u = (DWord) A[i] - B[i] - u.GetHighHalfAsBorrow();
00500 C[i] = u.GetLowHalf();
00501 u = (DWord) A[i+1] - B[i+1] - u.GetHighHalfAsBorrow();
00502 C[i+1] = u.GetLowHalf();
00503 }
00504 <span class="keywordflow">return</span> 0-u.GetHighHalf();
00505 }
00506
00507 <span class="keywordtype">void</span> Portable::Multiply2(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
00508 {
00509 <span class="comment">/*</span>
00510 <span class="comment"> word s;</span>
00511 <span class="comment"> dword d;</span>
00512 <span class="comment"></span>
00513 <span class="comment"> if (A1 >= A0)</span>
00514 <span class="comment"> if (B0 >= B1)</span>
00515 <span class="comment"> {</span>
00516 <span class="comment"> s = 0;</span>
00517 <span class="comment"> d = (dword)(A1-A0)*(B0-B1);</span>
00518 <span class="comment"> }</span>
00519 <span class="comment"> else</span>
00520 <span class="comment"> {</span>
00521 <span class="comment"> s = (A1-A0);</span>
00522 <span class="comment"> d = (dword)s*(word)(B0-B1);</span>
00523 <span class="comment"> }</span>
00524 <span class="comment"> else</span>
00525 <span class="comment"> if (B0 > B1)</span>
00526 <span class="comment"> {</span>
00527 <span class="comment"> s = (B0-B1);</span>
00528 <span class="comment"> d = (word)(A1-A0)*(dword)s;</span>
00529 <span class="comment"> }</span>
00530 <span class="comment"> else</span>
00531 <span class="comment"> {</span>
00532 <span class="comment"> s = 0;</span>
00533 <span class="comment"> d = (dword)(A0-A1)*(B1-B0);</span>
00534 <span class="comment"> }</span>
00535 <span class="comment">*/</span>
00536 <span class="comment">// this segment is the branchless equivalent of above</span>
00537 word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};
00538 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ai = A[1] < A[0];
00539 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bi = B[0] < B[1];
00540 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> di = ai & bi;
00541 DWord d = DWord::Multiply(D[di], D[di+2]);
00542 D[1] = D[3] = 0;
00543 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> si = ai + !bi;
00544 word s = D[si];
00545
00546 DWord A0B0 = DWord::Multiply(A[0], B[0]);
00547 C[0] = A0B0.GetLowHalf();
00548
00549 DWord A1B1 = DWord::Multiply(A[1], B[1]);
00550 DWord t = (DWord) A0B0.GetHighHalf() + A0B0.GetLowHalf() + d.GetLowHalf() + A1B1.GetLowHalf();
00551 C[1] = t.GetLowHalf();
00552
00553 t = A1B1 + t.GetHighHalf() + A0B0.GetHighHalf() + d.GetHighHalf() + A1B1.GetHighHalf() - s;
00554 C[2] = t.GetLowHalf();
00555 C[3] = t.GetHighHalf();
00556 }
00557
00558 <span class="keyword">inline</span> <span class="keywordtype">void</span> Portable::Multiply2Bottom(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
00559 {
00560 DWord t = DWord::Multiply(A[0], B[0]);
00561 C[0] = t.GetLowHalf();
00562 C[1] = t.GetHighHalf() + A[0]*B[1] + A[1]*B[0];
00563 }
00564
00565 word Portable::Multiply2Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
00566 {
00567 word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};
00568 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ai = A[1] < A[0];
00569 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bi = B[0] < B[1];
00570 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> di = ai & bi;
00571 DWord d = DWord::Multiply(D[di], D[di+2]);
00572 D[1] = D[3] = 0;
00573 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> si = ai + !bi;
00574 word s = D[si];
00575
00576 DWord A0B0 = DWord::Multiply(A[0], B[0]);
00577 DWord t = A0B0 + C[0];
00578 C[0] = t.GetLowHalf();
00579
00580 DWord A1B1 = DWord::Multiply(A[1], B[1]);
00581 t = (DWord) t.GetHighHalf() + A0B0.GetLowHalf() + d.GetLowHalf() + A1B1.GetLowHalf() + C[1];
00582 C[1] = t.GetLowHalf();
00583
00584 t = (DWord) t.GetHighHalf() + A1B1.GetLowHalf() + A0B0.GetHighHalf() + d.GetHighHalf() + A1B1.GetHighHalf() - s + C[2];
00585 C[2] = t.GetLowHalf();
00586
00587 t = (DWord) t.GetHighHalf() + A1B1.GetHighHalf() + C[3];
00588 C[3] = t.GetLowHalf();
00589 <span class="keywordflow">return</span> t.GetHighHalf();
00590 }
00591
00592 <span class="preprocessor">#define MulAcc(x, y) \</span>
00593 <span class="preprocessor"> p = DWord::MultiplyAndAdd(A[x], B[y], c); \</span>
00594 <span class="preprocessor"> c = p.GetLowHalf(); \</span>
00595 <span class="preprocessor"> p = (DWord) d + p.GetHighHalf(); \</span>
00596 <span class="preprocessor"> d = p.GetLowHalf(); \</span>
00597 <span class="preprocessor"> e += p.GetHighHalf();</span>
00598 <span class="preprocessor"></span>
00599 <span class="preprocessor">#define SaveMulAcc(s, x, y) \</span>
00600 <span class="preprocessor"> R[s] = c; \</span>
00601 <span class="preprocessor"> p = DWord::MultiplyAndAdd(A[x], B[y], d); \</span>
00602 <span class="preprocessor"> c = p.GetLowHalf(); \</span>
00603 <span class="preprocessor"> p = (DWord) e + p.GetHighHalf(); \</span>
00604 <span class="preprocessor"> d = p.GetLowHalf(); \</span>
00605 <span class="preprocessor"> e = p.GetHighHalf();</span>
00606 <span class="preprocessor"></span>
00607 <span class="preprocessor">#define SquAcc(x, y) \</span>
00608 <span class="preprocessor"> q = DWord::Multiply(A[x], A[y]); \</span>
00609 <span class="preprocessor"> p = q + c; \</span>
00610 <span class="preprocessor"> c = p.GetLowHalf(); \</span>
00611 <span class="preprocessor"> p = (DWord) d + p.GetHighHalf(); \</span>
00612 <span class="preprocessor"> d = p.GetLowHalf(); \</span>
00613 <span class="preprocessor"> e += p.GetHighHalf(); \</span>
00614 <span class="preprocessor"> p = q + c; \</span>
00615 <span class="preprocessor"> c = p.GetLowHalf(); \</span>
00616 <span class="preprocessor"> p = (DWord) d + p.GetHighHalf(); \</span>
00617 <span class="preprocessor"> d = p.GetLowHalf(); \</span>
00618 <span class="preprocessor"> e += p.GetHighHalf();</span>
00619 <span class="preprocessor"></span>
00620 <span class="preprocessor">#define SaveSquAcc(s, x, y) \</span>
00621 <span class="preprocessor"> R[s] = c; \</span>
00622 <span class="preprocessor"> q = DWord::Multiply(A[x], A[y]); \</span>
00623 <span class="preprocessor"> p = q + d; \</span>
00624 <span class="preprocessor"> c = p.GetLowHalf(); \</span>
00625 <span class="preprocessor"> p = (DWord) e + p.GetHighHalf(); \</span>
00626 <span class="preprocessor"> d = p.GetLowHalf(); \</span>
00627 <span class="preprocessor"> e = p.GetHighHalf(); \</span>
00628 <span class="preprocessor"> p = q + c; \</span>
00629 <span class="preprocessor"> c = p.GetLowHalf(); \</span>
00630 <span class="preprocessor"> p = (DWord) d + p.GetHighHalf(); \</span>
00631 <span class="preprocessor"> d = p.GetLowHalf(); \</span>
00632 <span class="preprocessor"> e += p.GetHighHalf();</span>
00633 <span class="preprocessor"></span>
00634 <span class="keywordtype">void</span> Portable::Multiply4(word *R, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
00635 {
00636 DWord p;
00637 word c, d, e;
00638
00639 p = DWord::Multiply(A[0], B[0]);
00640 R[0] = p.GetLowHalf();
00641 c = p.GetHighHalf();
00642 d = e = 0;
00643
00644 MulAcc(0, 1);
00645 MulAcc(1, 0);
00646
00647 SaveMulAcc(1, 2, 0);
00648 MulAcc(1, 1);
00649 MulAcc(0, 2);
00650
00651 SaveMulAcc(2, 0, 3);
00652 MulAcc(1, 2);
00653 MulAcc(2, 1);
00654 MulAcc(3, 0);
00655
00656 SaveMulAcc(3, 3, 1);
00657 MulAcc(2, 2);
00658 MulAcc(1, 3);
00659
00660 SaveMulAcc(4, 2, 3);
00661 MulAcc(3, 2);
00662
00663 R[5] = c;
00664 p = DWord::MultiplyAndAdd(A[3], B[3], d);
00665 R[6] = p.GetLowHalf();
00666 R[7] = e + p.GetHighHalf();
00667 }
00668
00669 <span class="keywordtype">void</span> Portable::Square2(word *R, <span class="keyword">const</span> word *A)
00670 {
00671 DWord p, q;
00672 word c, d, e;
00673
00674 p = DWord::Multiply(A[0], A[0]);
00675 R[0] = p.GetLowHalf();
00676 c = p.GetHighHalf();
00677 d = e = 0;
00678
00679 SquAcc(0, 1);
00680
00681 R[1] = c;
00682 p = DWord::MultiplyAndAdd(A[1], A[1], d);
00683 R[2] = p.GetLowHalf();
00684 R[3] = e + p.GetHighHalf();
00685 }
00686
00687 <span class="keywordtype">void</span> Portable::Square4(word *R, <span class="keyword">const</span> word *A)
00688 {
00689 <span class="preprocessor">#ifdef _MSC_VER</span>
00690 <span class="preprocessor"></span> <span class="comment">// VC60 workaround: MSVC 6.0 has an optimization bug that makes</span>
00691 <span class="comment">// (dword)A*B where either A or B has been cast to a dword before</span>
00692 <span class="comment">// very expensive. Revisit this function when this</span>
00693 <span class="comment">// bug is fixed.</span>
00694 Multiply4(R, A, A);
00695 <span class="preprocessor">#else</span>
00696 <span class="preprocessor"></span> <span class="keyword">const</span> word *B = A;
00697 DWord p, q;
00698 word c, d, e;
00699
00700 p = DWord::Multiply(A[0], A[0]);
00701 R[0] = p.GetLowHalf();
00702 c = p.GetHighHalf();
00703 d = e = 0;
00704
00705 SquAcc(0, 1);
00706
00707 SaveSquAcc(1, 2, 0);
00708 MulAcc(1, 1);
00709
00710 SaveSquAcc(2, 0, 3);
00711 SquAcc(1, 2);
00712
00713 SaveSquAcc(3, 3, 1);
00714 MulAcc(2, 2);
00715
00716 SaveSquAcc(4, 2, 3);
00717
00718 R[5] = c;
00719 p = DWord::MultiplyAndAdd(A[3], A[3], d);
00720 R[6] = p.GetLowHalf();
00721 R[7] = e + p.GetHighHalf();
00722 <span class="preprocessor">#endif</span>
00723 <span class="preprocessor"></span>}
00724
00725 <span class="keywordtype">void</span> Portable::Multiply8(word *R, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
00726 {
00727 DWord p;
00728 word c, d, e;
00729
00730 p = DWord::Multiply(A[0], B[0]);
00731 R[0] = p.GetLowHalf();
00732 c = p.GetHighHalf();
00733 d = e = 0;
00734
00735 MulAcc(0, 1);
00736 MulAcc(1, 0);
00737
00738 SaveMulAcc(1, 2, 0);
00739 MulAcc(1, 1);
00740 MulAcc(0, 2);
00741
00742 SaveMulAcc(2, 0, 3);
00743 MulAcc(1, 2);
00744 MulAcc(2, 1);
00745 MulAcc(3, 0);
00746
00747 SaveMulAcc(3, 0, 4);
00748 MulAcc(1, 3);
00749 MulAcc(2, 2);
00750 MulAcc(3, 1);
00751 MulAcc(4, 0);
00752
00753 SaveMulAcc(4, 0, 5);
00754 MulAcc(1, 4);
00755 MulAcc(2, 3);
00756 MulAcc(3, 2);
00757 MulAcc(4, 1);
00758 MulAcc(5, 0);
00759
00760 SaveMulAcc(5, 0, 6);
00761 MulAcc(1, 5);
00762 MulAcc(2, 4);
00763 MulAcc(3, 3);
00764 MulAcc(4, 2);
00765 MulAcc(5, 1);
00766 MulAcc(6, 0);
00767
00768 SaveMulAcc(6, 0, 7);
00769 MulAcc(1, 6);
00770 MulAcc(2, 5);
00771 MulAcc(3, 4);
00772 MulAcc(4, 3);
00773 MulAcc(5, 2);
00774 MulAcc(6, 1);
00775 MulAcc(7, 0);
00776
00777 SaveMulAcc(7, 1, 7);
00778 MulAcc(2, 6);
00779 MulAcc(3, 5);
00780 MulAcc(4, 4);
00781 MulAcc(5, 3);
00782 MulAcc(6, 2);
00783 MulAcc(7, 1);
00784
00785 SaveMulAcc(8, 2, 7);
00786 MulAcc(3, 6);
00787 MulAcc(4, 5);
00788 MulAcc(5, 4);
00789 MulAcc(6, 3);
00790 MulAcc(7, 2);
00791
00792 SaveMulAcc(9, 3, 7);
00793 MulAcc(4, 6);
00794 MulAcc(5, 5);
00795 MulAcc(6, 4);
00796 MulAcc(7, 3);
00797
00798 SaveMulAcc(10, 4, 7);
00799 MulAcc(5, 6);
00800 MulAcc(6, 5);
00801 MulAcc(7, 4);
00802
00803 SaveMulAcc(11, 5, 7);
00804 MulAcc(6, 6);
00805 MulAcc(7, 5);
00806
00807 SaveMulAcc(12, 6, 7);
00808 MulAcc(7, 6);
00809
00810 R[13] = c;
00811 p = DWord::MultiplyAndAdd(A[7], B[7], d);
00812 R[14] = p.GetLowHalf();
00813 R[15] = e + p.GetHighHalf();
00814 }
00815
00816 <span class="keywordtype">void</span> Portable::Multiply4Bottom(word *R, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
00817 {
00818 DWord p;
00819 word c, d, e;
00820
00821 p = DWord::Multiply(A[0], B[0]);
00822 R[0] = p.GetLowHalf();
00823 c = p.GetHighHalf();
00824 d = e = 0;
00825
00826 MulAcc(0, 1);
00827 MulAcc(1, 0);
00828
00829 SaveMulAcc(1, 2, 0);
00830 MulAcc(1, 1);
00831 MulAcc(0, 2);
00832
00833 R[2] = c;
00834 R[3] = d + A[0] * B[3] + A[1] * B[2] + A[2] * B[1] + A[3] * B[0];
00835 }
00836
00837 <span class="keywordtype">void</span> Portable::Multiply8Bottom(word *R, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
00838 {
00839 DWord p;
00840 word c, d, e;
00841
00842 p = DWord::Multiply(A[0], B[0]);
00843 R[0] = p.GetLowHalf();
00844 c = p.GetHighHalf();
00845 d = e = 0;
00846
00847 MulAcc(0, 1);
00848 MulAcc(1, 0);
00849
00850 SaveMulAcc(1, 2, 0);
00851 MulAcc(1, 1);
00852 MulAcc(0, 2);
00853
00854 SaveMulAcc(2, 0, 3);
00855 MulAcc(1, 2);
00856 MulAcc(2, 1);
00857 MulAcc(3, 0);
00858
00859 SaveMulAcc(3, 0, 4);
00860 MulAcc(1, 3);
00861 MulAcc(2, 2);
00862 MulAcc(3, 1);
00863 MulAcc(4, 0);
00864
00865 SaveMulAcc(4, 0, 5);
00866 MulAcc(1, 4);
00867 MulAcc(2, 3);
00868 MulAcc(3, 2);
00869 MulAcc(4, 1);
00870 MulAcc(5, 0);
00871
00872 SaveMulAcc(5, 0, 6);
00873 MulAcc(1, 5);
00874 MulAcc(2, 4);
00875 MulAcc(3, 3);
00876 MulAcc(4, 2);
00877 MulAcc(5, 1);
00878 MulAcc(6, 0);
00879
00880 R[6] = c;
00881 R[7] = d + A[0] * B[7] + A[1] * B[6] + A[2] * B[5] + A[3] * B[4] +
00882 A[4] * B[3] + A[5] * B[2] + A[6] * B[1] + A[7] * B[0];
00883 }
00884
00885 <span class="preprocessor">#undef MulAcc</span>
00886 <span class="preprocessor"></span><span class="preprocessor">#undef SaveMulAcc</span>
00887 <span class="preprocessor"></span><span class="preprocessor">#undef SquAcc</span>
00888 <span class="preprocessor"></span><span class="preprocessor">#undef SaveSquAcc</span>
00889 <span class="preprocessor"></span>
00890 <span class="preprocessor">#ifdef CRYPTOPP_X86ASM_AVAILABLE</span>
00891 <span class="preprocessor"></span>
00892 <span class="comment">// ************** x86 feature detection ***************</span>
00893
00894 <span class="keyword">static</span> <span class="keywordtype">bool</span> s_sse2Enabled = <span class="keyword">true</span>;
00895
00896 <span class="keyword">static</span> <span class="keywordtype">void</span> CpuId(word32 input, word32 *output)
00897 {
00898 <span class="preprocessor">#ifdef __GNUC__</span>
00899 <span class="preprocessor"></span> __asm__
00900 (
00901 <span class="comment">// save ebx in case -fPIC is being used</span>
00902 <span class="stringliteral">"push %%ebx; cpuid; mov %%ebx, %%edi; pop %%ebx"</span>
00903 : <span class="stringliteral">"=a"</span> (output[0]), <span class="stringliteral">"=D"</span> (output[1]), <span class="stringliteral">"=c"</span> (output[2]), <span class="stringliteral">"=d"</span> (output[3])
00904 : <span class="stringliteral">"a"</span> (input)
00905 );
00906 <span class="preprocessor">#else</span>
00907 <span class="preprocessor"></span> __asm
00908 {
00909 mov eax, input
00910 cpuid
00911 mov edi, output
00912 mov [edi], eax
00913 mov [edi+4], ebx
00914 mov [edi+8], ecx
00915 mov [edi+12], edx
00916 }
00917 <span class="preprocessor">#endif</span>
00918 <span class="preprocessor"></span>}
00919
00920 <span class="preprocessor">#ifdef SSE2_INTRINSICS_AVAILABLE</span>
00921 <span class="preprocessor"></span><span class="preprocessor">#ifndef _MSC_VER</span>
00922 <span class="preprocessor"></span><span class="keyword">static</span> jmp_buf s_env;
00923 <span class="keyword">static</span> <span class="keywordtype">void</span> SigIllHandler(<span class="keywordtype">int</span>)
00924 {
00925 longjmp(s_env, 1);
00926 }
00927 <span class="preprocessor">#endif</span>
00928 <span class="preprocessor"></span>
00929 <span class="keyword">static</span> <span class="keywordtype">bool</span> HasSSE2()
00930 {
00931 <span class="keywordflow">if</span> (!s_sse2Enabled)
00932 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00933
00934 word32 cpuid[4];
00935 CpuId(1, cpuid);
00936 <span class="keywordflow">if</span> ((cpuid[3] & (1 << 26)) == 0)
00937 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00938
00939 <span class="preprocessor">#ifdef _MSC_VER</span>
00940 <span class="preprocessor"></span> __try
00941 {
00942 __asm xorpd xmm0, xmm0 <span class="comment">// executing SSE2 instruction</span>
00943 }
00944 __except (1)
00945 {
00946 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00947 }
00948 <span class="keywordflow">return</span> <span class="keyword">true</span>;
00949 <span class="preprocessor">#else</span>
00950 <span class="preprocessor"></span> <span class="keyword">typedef</span> void (*SigHandler)(<span class="keywordtype">int</span>);
00951
00952 SigHandler oldHandler = signal(SIGILL, SigIllHandler);
00953 <span class="keywordflow">if</span> (oldHandler == SIG_ERR)
00954 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00955
00956 <span class="keywordtype">bool</span> result = <span class="keyword">true</span>;
00957 <span class="keywordflow">if</span> (setjmp(s_env))
00958 result = <span class="keyword">false</span>;
00959 <span class="keywordflow">else</span>
00960 __asm __volatile (<span class="stringliteral">"xorps %xmm0, %xmm0"</span>);
00961
00962 signal(SIGILL, oldHandler);
00963 <span class="keywordflow">return</span> result;
00964 <span class="preprocessor">#endif</span>
00965 <span class="preprocessor"></span>}
00966 <span class="preprocessor">#endif</span>
00967 <span class="preprocessor"></span>
00968 <span class="keyword">static</span> <span class="keywordtype">bool</span> IsP4()
00969 {
00970 word32 cpuid[4];
00971
00972 CpuId(0, cpuid);
00973 std::swap(cpuid[2], cpuid[3]);
00974 <span class="keywordflow">if</span> (memcmp(cpuid+1, <span class="stringliteral">"GenuineIntel"</span>, 12) != 0)
00975 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00976
00977 CpuId(1, cpuid);
00978 <span class="keywordflow">return</span> ((cpuid[0] >> 8) & 0xf) == 0xf;
00979 }
00980
00981 <span class="comment">// ************** Pentium/P4 optimizations ***************</span>
00982
00983 <span class="keyword">class </span>PentiumOptimized : <span class="keyword">public</span> Portable
00984 {
00985 <span class="keyword">public</span>:
00986 <span class="keyword">static</span> word CRYPTOPP_CDECL Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N);
00987 <span class="keyword">static</span> word CRYPTOPP_CDECL Subtract(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N);
00988 <span class="keyword">static</span> <span class="keywordtype">void</span> CRYPTOPP_CDECL Multiply4(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00989 <span class="keyword">static</span> <span class="keywordtype">void</span> CRYPTOPP_CDECL Multiply8(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00990 <span class="keyword">static</span> <span class="keywordtype">void</span> CRYPTOPP_CDECL Multiply8Bottom(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
00991 };
00992
00993 <span class="keyword">class </span>P4Optimized
00994 {
00995 <span class="keyword">public</span>:
00996 <span class="keyword">static</span> word CRYPTOPP_CDECL Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N);
00997 <span class="keyword">static</span> word CRYPTOPP_CDECL Subtract(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N);
00998 <span class="preprocessor">#ifdef SSE2_INTRINSICS_AVAILABLE</span>
00999 <span class="preprocessor"></span> <span class="keyword">static</span> <span class="keywordtype">void</span> CRYPTOPP_CDECL Multiply4(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
01000 <span class="keyword">static</span> <span class="keywordtype">void</span> CRYPTOPP_CDECL Multiply8(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
01001 <span class="keyword">static</span> <span class="keywordtype">void</span> CRYPTOPP_CDECL Multiply8Bottom(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
01002 <span class="preprocessor">#endif</span>
01003 <span class="preprocessor"></span>};
01004
01005 <span class="keyword">typedef</span> word (CRYPTOPP_CDECL * PAddSub)(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N);
01006 <span class="keyword">typedef</span> void (CRYPTOPP_CDECL * PMul)(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B);
01007
01008 <span class="keyword">static</span> PAddSub s_pAdd, s_pSub;
01009 <span class="preprocessor">#ifdef SSE2_INTRINSICS_AVAILABLE</span>
01010 <span class="preprocessor"></span><span class="keyword">static</span> PMul s_pMul4, s_pMul8, s_pMul8B;
01011 <span class="preprocessor">#endif</span>
01012 <span class="preprocessor"></span>
01013 <span class="keyword">static</span> <span class="keywordtype">void</span> SetPentiumFunctionPointers()
01014 {
01015 <span class="keywordflow">if</span> (IsP4())
01016 {
01017 s_pAdd = &P4Optimized::Add;
01018 s_pSub = &P4Optimized::Subtract;
01019 }
01020 <span class="keywordflow">else</span>
01021 {
01022 s_pAdd = &PentiumOptimized::Add;
01023 s_pSub = &PentiumOptimized::Subtract;
01024 }
01025
01026 <span class="preprocessor">#ifdef SSE2_INTRINSICS_AVAILABLE</span>
01027 <span class="preprocessor"></span> <span class="keywordflow">if</span> (HasSSE2())
01028 {
01029 s_pMul4 = &P4Optimized::Multiply4;
01030 s_pMul8 = &P4Optimized::Multiply8;
01031 s_pMul8B = &P4Optimized::Multiply8Bottom;
01032 }
01033 <span class="keywordflow">else</span>
01034 {
01035 s_pMul4 = &PentiumOptimized::Multiply4;
01036 s_pMul8 = &PentiumOptimized::Multiply8;
01037 s_pMul8B = &PentiumOptimized::Multiply8Bottom;
01038 }
01039 <span class="preprocessor">#endif</span>
01040 <span class="preprocessor"></span>}
01041
01042 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">char</span> s_RunAtStartupSetPentiumFunctionPointers = (SetPentiumFunctionPointers(), 0);
01043
01044 <span class="keywordtype">void</span> DisableSSE2()
01045 {
01046 s_sse2Enabled = <span class="keyword">false</span>;
01047 SetPentiumFunctionPointers();
01048 }
01049
01050 <span class="keyword">class </span>LowLevel : <span class="keyword">public</span> PentiumOptimized
01051 {
01052 <span class="keyword">public</span>:
01053 <span class="keyword">inline</span> <span class="keyword">static</span> word Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
01054 {<span class="keywordflow">return</span> s_pAdd(C, A, B, N);}
01055 <span class="keyword">inline</span> <span class="keyword">static</span> word Subtract(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
01056 {<span class="keywordflow">return</span> s_pSub(C, A, B, N);}
01057 <span class="keyword">inline</span> <span class="keyword">static</span> <span class="keywordtype">void</span> Square4(word *R, <span class="keyword">const</span> word *A)
01058 {Multiply4(R, A, A);}
01059 <span class="preprocessor">#ifdef SSE2_INTRINSICS_AVAILABLE</span>
01060 <span class="preprocessor"></span> <span class="keyword">inline</span> <span class="keyword">static</span> <span class="keywordtype">void</span> Multiply4(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
01061 {s_pMul4(C, A, B);}
01062 <span class="keyword">inline</span> <span class="keyword">static</span> <span class="keywordtype">void</span> Multiply8(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
01063 {s_pMul8(C, A, B);}
01064 <span class="keyword">inline</span> <span class="keyword">static</span> <span class="keywordtype">void</span> Multiply8Bottom(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
01065 {s_pMul8B(C, A, B);}
01066 <span class="preprocessor">#endif</span>
01067 <span class="preprocessor"></span>};
01068
01069 <span class="comment">// use some tricks to share assembly code between MSVC and GCC</span>
01070 <span class="preprocessor">#ifdef _MSC_VER</span>
01071 <span class="preprocessor"></span><span class="preprocessor"> #define CRYPTOPP_NAKED __declspec(naked)</span>
01072 <span class="preprocessor"></span><span class="preprocessor"> #define AS1(x) __asm x</span>
01073 <span class="preprocessor"></span><span class="preprocessor"> #define AS2(x, y) __asm x, y</span>
01074 <span class="preprocessor"></span><span class="preprocessor"> #define AddPrologue \</span>
01075 <span class="preprocessor"> __asm push ebp \</span>
01076 <span class="preprocessor"> __asm push ebx \</span>
01077 <span class="preprocessor"> __asm push esi \</span>
01078 <span class="preprocessor"> __asm push edi \</span>
01079 <span class="preprocessor"> __asm mov ecx, [esp+20] \</span>
01080 <span class="preprocessor"> __asm mov edx, [esp+24] \</span>
01081 <span class="preprocessor"> __asm mov ebx, [esp+28] \</span>
01082 <span class="preprocessor"> __asm mov esi, [esp+32]</span>
01083 <span class="preprocessor"></span><span class="preprocessor"> #define AddEpilogue \</span>
01084 <span class="preprocessor"> __asm pop edi \</span>
01085 <span class="preprocessor"> __asm pop esi \</span>
01086 <span class="preprocessor"> __asm pop ebx \</span>
01087 <span class="preprocessor"> __asm pop ebp \</span>
01088 <span class="preprocessor"> __asm ret</span>
01089 <span class="preprocessor"></span><span class="preprocessor"> #define MulPrologue \</span>
01090 <span class="preprocessor"> __asm push ebp \</span>
01091 <span class="preprocessor"> __asm push ebx \</span>
01092 <span class="preprocessor"> __asm push esi \</span>
01093 <span class="preprocessor"> __asm push edi \</span>
01094 <span class="preprocessor"> __asm mov ecx, [esp+28] \</span>
01095 <span class="preprocessor"> __asm mov esi, [esp+24] \</span>
01096 <span class="preprocessor"> __asm push [esp+20]</span>
01097 <span class="preprocessor"></span><span class="preprocessor"> #define MulEpilogue \</span>
01098 <span class="preprocessor"> __asm add esp, 4 \</span>
01099 <span class="preprocessor"> __asm pop edi \</span>
01100 <span class="preprocessor"> __asm pop esi \</span>
01101 <span class="preprocessor"> __asm pop ebx \</span>
01102 <span class="preprocessor"> __asm pop ebp \</span>
01103 <span class="preprocessor"> __asm ret</span>
01104 <span class="preprocessor"></span><span class="preprocessor">#else</span>
01105 <span class="preprocessor"></span><span class="preprocessor"> #define CRYPTOPP_NAKED</span>
01106 <span class="preprocessor"></span><span class="preprocessor"> #define AS1(x) #x ";"</span>
01107 <span class="preprocessor"></span><span class="preprocessor"> #define AS2(x, y) #x ", " #y ";"</span>
01108 <span class="preprocessor"></span><span class="preprocessor"> #define AddPrologue \</span>
01109 <span class="preprocessor"> __asm__ __volatile__ \</span>
01110 <span class="preprocessor"> ( \</span>
01111 <span class="preprocessor"> "push %%ebx;" </span><span class="comment">/* save this manually, in case of -fPIC */</span> \
01112 "mov %2, %%ebx;" \
01113 ".intel_syntax noprefix;" \
01114 "push ebp;"
01115 <span class="preprocessor"> #define AddEpilogue \</span>
01116 <span class="preprocessor"> "pop ebp;" \</span>
01117 <span class="preprocessor"> ".att_syntax prefix;" \</span>
01118 <span class="preprocessor"> "pop %%ebx;" \</span>
01119 <span class="preprocessor"> : \</span>
01120 <span class="preprocessor"> : "c" (C), "d" (A), "m" (B), "S" (N) \</span>
01121 <span class="preprocessor"> : "%edi", "memory", "cc" \</span>
01122 <span class="preprocessor"> );</span>
01123 <span class="preprocessor"></span><span class="preprocessor"> #define MulPrologue \</span>
01124 <span class="preprocessor"> __asm__ __volatile__ \</span>
01125 <span class="preprocessor"> ( \</span>
01126 <span class="preprocessor"> "push %%ebx;" </span><span class="comment">/* save this manually, in case of -fPIC */</span> \
01127 "push %%ebp;" \
01128 "push %0;" \
01129 ".intel_syntax noprefix;"
01130 <span class="preprocessor"> #define MulEpilogue \</span>
01131 <span class="preprocessor"> "add esp, 4;" \</span>
01132 <span class="preprocessor"> "pop ebp;" \</span>
01133 <span class="preprocessor"> "pop ebx;" \</span>
01134 <span class="preprocessor"> ".att_syntax prefix;" \</span>
01135 <span class="preprocessor"> : \</span>
01136 <span class="preprocessor"> : "rm" (Z), "S" (X), "c" (Y) \</span>
01137 <span class="preprocessor"> : "%eax", "%edx", "%edi", "memory", "cc" \</span>
01138 <span class="preprocessor"> );</span>
01139 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
01140 <span class="preprocessor"></span>
01141 CRYPTOPP_NAKED word PentiumOptimized::Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
01142 {
01143 AddPrologue
01144
01145 <span class="comment">// now: ebx = B, ecx = C, edx = A, esi = N</span>
01146 AS2( sub ecx, edx) <span class="comment">// hold the distance between C & A so we can add this to A to get C</span>
01147 AS2( xor eax, eax) <span class="comment">// clear eax</span>
01148
01149 AS2( sub eax, esi) <span class="comment">// eax is a negative index from end of B</span>
01150 AS2( lea ebx, [ebx+4*esi]) <span class="comment">// ebx is end of B</span>
01151
01152 AS2( sar eax, 1) <span class="comment">// unit of eax is now dwords; this also clears the carry flag</span>
01153 AS1( jz loopendAdd) <span class="comment">// if no dwords then nothing to do</span>
01154
01155 AS1(loopstartAdd:)
01156 AS2( mov esi,[edx]) <span class="comment">// load lower word of A</span>
01157 AS2( mov ebp,[edx+4]) <span class="comment">// load higher word of A</span>
01158
01159 AS2( mov edi,[ebx+8*eax]) <span class="comment">// load lower word of B</span>
01160 AS2( lea edx,[edx+8]) <span class="comment">// advance A and C</span>
01161
01162 AS2( adc esi,edi) <span class="comment">// add lower words</span>
01163 AS2( mov edi,[ebx+8*eax+4]) <span class="comment">// load higher word of B</span>
01164
01165 AS2( adc ebp,edi) <span class="comment">// add higher words</span>
01166 AS1( inc eax) <span class="comment">// advance B</span>
01167
01168 AS2( mov [edx+ecx-8],esi) <span class="comment">// store lower word result</span>
01169 AS2( mov [edx+ecx-4],ebp) <span class="comment">// store higher word result</span>
01170
01171 AS1( jnz loopstartAdd) <span class="comment">// loop until eax overflows and becomes zero</span>
01172
01173 AS1(loopendAdd:)
01174 AS2( adc eax, 0) <span class="comment">// store carry into eax (return result register)</span>
01175
01176 AddEpilogue
01177 }
01178
01179 CRYPTOPP_NAKED word PentiumOptimized::Subtract(word *C, const word *A, const word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
01180 {
01181 AddPrologue
01182
01183 <span class="comment">// now: ebx = B, ecx = C, edx = A, esi = N</span>
01184 AS2( sub ecx, edx) <span class="comment">// hold the distance between C & A so we can add this to A to get C</span>
01185 AS2( xor eax, eax) <span class="comment">// clear eax</span>
01186
01187 AS2( sub eax, esi) <span class="comment">// eax is a negative index from end of B</span>
01188 AS2( lea ebx, [ebx+4*esi]) <span class="comment">// ebx is end of B</span>
01189
01190 AS2( sar eax, 1) <span class="comment">// unit of eax is now dwords; this also clears the carry flag</span>
01191 AS1( jz loopendSub) <span class="comment">// if no dwords then nothing to do</span>
01192
01193 AS1(loopstartSub:)
01194 AS2( mov esi,[edx]) <span class="comment">// load lower word of A</span>
01195 AS2( mov ebp,[edx+4]) <span class="comment">// load higher word of A</span>
01196
01197 AS2( mov edi,[ebx+8*eax]) <span class="comment">// load lower word of B</span>
01198 AS2( lea edx,[edx+8]) <span class="comment">// advance A and C</span>
01199
01200 AS2( sbb esi,edi) <span class="comment">// subtract lower words</span>
01201 AS2( mov edi,[ebx+8*eax+4]) <span class="comment">// load higher word of B</span>
01202
01203 AS2( sbb ebp,edi) <span class="comment">// subtract higher words</span>
01204 AS1( inc eax) <span class="comment">// advance B</span>
01205
01206 AS2( mov [edx+ecx-8],esi) <span class="comment">// store lower word result</span>
01207 AS2( mov [edx+ecx-4],ebp) <span class="comment">// store higher word result</span>
01208
01209 AS1( jnz loopstartSub) <span class="comment">// loop until eax overflows and becomes zero</span>
01210
01211 AS1(loopendSub:)
01212 AS2( adc eax, 0) <span class="comment">// store carry into eax (return result register)</span>
01213
01214 AddEpilogue
01215 }
01216
01217 <span class="comment">// On Pentium 4, the adc and sbb instructions are very expensive, so avoid them.</span>
01218
01219 CRYPTOPP_NAKED word P4Optimized::Add(word *C, const word *A, const word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
01220 {
01221 AddPrologue
01222
01223 <span class="comment">// now: ebx = B, ecx = C, edx = A, esi = N</span>
01224 AS2( xor eax, eax)
01225 AS1( neg esi)
01226 AS1( jz loopendAddP4) <span class="comment">// if no dwords then nothing to do</span>
01227
01228 AS2( mov edi, [edx])
01229 AS2( mov ebp, [ebx])
01230 AS1( jmp carry1AddP4)
01231
01232 AS1(loopstartAddP4:)
01233 AS2( mov edi, [edx+8])
01234 AS2( add ecx, 8)
01235 AS2( add edx, 8)
01236 AS2( mov ebp, [ebx])
01237 AS2( add edi, eax)
01238 AS1( jc carry1AddP4)
01239 AS2( xor eax, eax)
01240
01241 AS1(carry1AddP4:)
01242 AS2( add edi, ebp)
01243 AS2( mov ebp, 1)
01244 AS2( mov [ecx], edi)
01245 AS2( mov edi, [edx+4])
01246 AS2( cmovc eax, ebp)
01247 AS2( mov ebp, [ebx+4])
01248 AS2( add ebx, 8)
01249 AS2( add edi, eax)
01250 AS1( jc carry2AddP4)
01251 AS2( xor eax, eax)
01252
01253 AS1(carry2AddP4:)
01254 AS2( add edi, ebp)
01255 AS2( mov ebp, 1)
01256 AS2( cmovc eax, ebp)
01257 AS2( mov [ecx+4], edi)
01258 AS2( add esi, 2)
01259 AS1( jnz loopstartAddP4)
01260
01261 AS1(loopendAddP4:)
01262
01263 AddEpilogue
01264 }
01265
01266 CRYPTOPP_NAKED word P4Optimized::Subtract(word *C, const word *A, const word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
01267 {
01268 AddPrologue
01269
01270 <span class="comment">// now: ebx = B, ecx = C, edx = A, esi = N</span>
01271 AS2( xor eax, eax)
01272 AS1( neg esi)
01273 AS1( jz loopendSubP4) <span class="comment">// if no dwords then nothing to do</span>
01274
01275 AS2( mov edi, [edx])
01276 AS2( mov ebp, [ebx])
01277 AS1( jmp carry1SubP4)
01278
01279 AS1(loopstartSubP4:)
01280 AS2( mov edi, [edx+8])
01281 AS2( add edx, 8)
01282 AS2( add ecx, 8)
01283 AS2( mov ebp, [ebx])
01284 AS2( sub edi, eax)
01285 AS1( jc carry1SubP4)
01286 AS2( xor eax, eax)
01287
01288 AS1(carry1SubP4:)
01289 AS2( sub edi, ebp)
01290 AS2( mov ebp, 1)
01291 AS2( mov [ecx], edi)
01292 AS2( mov edi, [edx+4])
01293 AS2( cmovc eax, ebp)
01294 AS2( mov ebp, [ebx+4])
01295 AS2( add ebx, 8)
01296 AS2( sub edi, eax)
01297 AS1( jc carry2SubP4)
01298 AS2( xor eax, eax)
01299
01300 AS1(carry2SubP4:)
01301 AS2( sub edi, ebp)
01302 AS2( mov ebp, 1)
01303 AS2( cmovc eax, ebp)
01304 AS2( mov [ecx+4], edi)
01305 AS2( add esi, 2)
01306 AS1( jnz loopstartSubP4)
01307
01308 AS1(loopendSubP4:)
01309
01310 AddEpilogue
01311 }
01312
01313 <span class="comment">// multiply assembly code originally contributed by Leonard Janke</span>
01314
01315 #define MulStartup \
01316 AS2(xor ebp, ebp) \
01317 AS2(xor edi, edi) \
01318 AS2(xor ebx, ebx)
01319
01320 #define MulShiftCarry \
01321 AS2(mov ebp, edx) \
01322 AS2(mov edi, ebx) \
01323 AS2(xor ebx, ebx)
01324
01325 #define MulAccumulateBottom(i,j) \
01326 AS2(mov eax, [ecx+4*j]) \
01327 AS2(imul eax, dword ptr [esi+4*i]) \
01328 AS2(add ebp, eax)
01329
01330 #define MulAccumulate(i,j) \
01331 AS2(mov eax, [ecx+4*j]) \
01332 AS1(mul dword ptr [esi+4*i]) \
01333 AS2(add ebp, eax) \
01334 AS2(adc edi, edx) \
01335 AS2(adc bl, bh)
01336
01337 #define MulStoreDigit(i) \
01338 AS2(mov edx, edi) \
01339 AS2(mov edi, [esp]) \
01340 AS2(mov [edi+4*i], ebp)
01341
01342 #define MulLastDiagonal(digits) \
01343 AS2(mov eax, [ecx+4*(digits-1)]) \
01344 AS1(mul dword ptr [esi+4*(digits-1)]) \
01345 AS2(add ebp, eax) \
01346 AS2(adc edx, edi) \
01347 AS2(mov edi, [esp]) \
01348 AS2(mov [edi+4*(2*digits-2)], ebp) \
01349 AS2(mov [edi+4*(2*digits-1)], edx)
01350
01351 CRYPTOPP_NAKED <span class="keywordtype">void</span> PentiumOptimized::Multiply4(word* Z, const word* X, const word* Y)
01352 {
01353 MulPrologue
01354 <span class="comment">// now: [esp] = Z, esi = X, ecx = Y</span>
01355 MulStartup
01356 MulAccumulate(0,0)
01357 MulStoreDigit(0)
01358 MulShiftCarry
01359
01360 MulAccumulate(1,0)
01361 MulAccumulate(0,1)
01362 MulStoreDigit(1)
01363 MulShiftCarry
01364
01365 MulAccumulate(2,0)
01366 MulAccumulate(1,1)
01367 MulAccumulate(0,2)
01368 MulStoreDigit(2)
01369 MulShiftCarry
01370
01371 MulAccumulate(3,0)
01372 MulAccumulate(2,1)
01373 MulAccumulate(1,2)
01374 MulAccumulate(0,3)
01375 MulStoreDigit(3)
01376 MulShiftCarry
01377
01378 MulAccumulate(3,1)
01379 MulAccumulate(2,2)
01380 MulAccumulate(1,3)
01381 MulStoreDigit(4)
01382 MulShiftCarry
01383
01384 MulAccumulate(3,2)
01385 MulAccumulate(2,3)
01386 MulStoreDigit(5)
01387 MulShiftCarry
01388
01389 MulLastDiagonal(4)
01390 MulEpilogue
01391 }
01392
01393 CRYPTOPP_NAKED <span class="keywordtype">void</span> PentiumOptimized::Multiply8(word* Z, const word* X, const word* Y)
01394 {
01395 MulPrologue
01396 <span class="comment">// now: [esp] = Z, esi = X, ecx = Y</span>
01397 MulStartup
01398 MulAccumulate(0,0)
01399 MulStoreDigit(0)
01400 MulShiftCarry
01401
01402 MulAccumulate(1,0)
01403 MulAccumulate(0,1)
01404 MulStoreDigit(1)
01405 MulShiftCarry
01406
01407 MulAccumulate(2,0)
01408 MulAccumulate(1,1)
01409 MulAccumulate(0,2)
01410 MulStoreDigit(2)
01411 MulShiftCarry
01412
01413 MulAccumulate(3,0)
01414 MulAccumulate(2,1)
01415 MulAccumulate(1,2)
01416 MulAccumulate(0,3)
01417 MulStoreDigit(3)
01418 MulShiftCarry
01419
01420 MulAccumulate(4,0)
01421 MulAccumulate(3,1)
01422 MulAccumulate(2,2)
01423 MulAccumulate(1,3)
01424 MulAccumulate(0,4)
01425 MulStoreDigit(4)
01426 MulShiftCarry
01427
01428 MulAccumulate(5,0)
01429 MulAccumulate(4,1)
01430 MulAccumulate(3,2)
01431 MulAccumulate(2,3)
01432 MulAccumulate(1,4)
01433 MulAccumulate(0,5)
01434 MulStoreDigit(5)
01435 MulShiftCarry
01436
01437 MulAccumulate(6,0)
01438 MulAccumulate(5,1)
01439 MulAccumulate(4,2)
01440 MulAccumulate(3,3)
01441 MulAccumulate(2,4)
01442 MulAccumulate(1,5)
01443 MulAccumulate(0,6)
01444 MulStoreDigit(6)
01445 MulShiftCarry
01446
01447 MulAccumulate(7,0)
01448 MulAccumulate(6,1)
01449 MulAccumulate(5,2)
01450 MulAccumulate(4,3)
01451 MulAccumulate(3,4)
01452 MulAccumulate(2,5)
01453 MulAccumulate(1,6)
01454 MulAccumulate(0,7)
01455 MulStoreDigit(7)
01456 MulShiftCarry
01457
01458 MulAccumulate(7,1)
01459 MulAccumulate(6,2)
01460 MulAccumulate(5,3)
01461 MulAccumulate(4,4)
01462 MulAccumulate(3,5)
01463 MulAccumulate(2,6)
01464 MulAccumulate(1,7)
01465 MulStoreDigit(8)
01466 MulShiftCarry
01467
01468 MulAccumulate(7,2)
01469 MulAccumulate(6,3)
01470 MulAccumulate(5,4)
01471 MulAccumulate(4,5)
01472 MulAccumulate(3,6)
01473 MulAccumulate(2,7)
01474 MulStoreDigit(9)
01475 MulShiftCarry
01476
01477 MulAccumulate(7,3)
01478 MulAccumulate(6,4)
01479 MulAccumulate(5,5)
01480 MulAccumulate(4,6)
01481 MulAccumulate(3,7)
01482 MulStoreDigit(10)
01483 MulShiftCarry
01484
01485 MulAccumulate(7,4)
01486 MulAccumulate(6,5)
01487 MulAccumulate(5,6)
01488 MulAccumulate(4,7)
01489 MulStoreDigit(11)
01490 MulShiftCarry
01491
01492 MulAccumulate(7,5)
01493 MulAccumulate(6,6)
01494 MulAccumulate(5,7)
01495 MulStoreDigit(12)
01496 MulShiftCarry
01497
01498 MulAccumulate(7,6)
01499 MulAccumulate(6,7)
01500 MulStoreDigit(13)
01501 MulShiftCarry
01502
01503 MulLastDiagonal(8)
01504 MulEpilogue
01505 }
01506
01507 CRYPTOPP_NAKED <span class="keywordtype">void</span> PentiumOptimized::Multiply8Bottom(word* Z, const word* X, const word* Y)
01508 {
01509 MulPrologue
01510 <span class="comment">// now: [esp] = Z, esi = X, ecx = Y</span>
01511 MulStartup
01512 MulAccumulate(0,0)
01513 MulStoreDigit(0)
01514 MulShiftCarry
01515
01516 MulAccumulate(1,0)
01517 MulAccumulate(0,1)
01518 MulStoreDigit(1)
01519 MulShiftCarry
01520
01521 MulAccumulate(2,0)
01522 MulAccumulate(1,1)
01523 MulAccumulate(0,2)
01524 MulStoreDigit(2)
01525 MulShiftCarry
01526
01527 MulAccumulate(3,0)
01528 MulAccumulate(2,1)
01529 MulAccumulate(1,2)
01530 MulAccumulate(0,3)
01531 MulStoreDigit(3)
01532 MulShiftCarry
01533
01534 MulAccumulate(4,0)
01535 MulAccumulate(3,1)
01536 MulAccumulate(2,2)
01537 MulAccumulate(1,3)
01538 MulAccumulate(0,4)
01539 MulStoreDigit(4)
01540 MulShiftCarry
01541
01542 MulAccumulate(5,0)
01543 MulAccumulate(4,1)
01544 MulAccumulate(3,2)
01545 MulAccumulate(2,3)
01546 MulAccumulate(1,4)
01547 MulAccumulate(0,5)
01548 MulStoreDigit(5)
01549 MulShiftCarry
01550
01551 MulAccumulate(6,0)
01552 MulAccumulate(5,1)
01553 MulAccumulate(4,2)
01554 MulAccumulate(3,3)
01555 MulAccumulate(2,4)
01556 MulAccumulate(1,5)
01557 MulAccumulate(0,6)
01558 MulStoreDigit(6)
01559 MulShiftCarry
01560
01561 MulAccumulateBottom(7,0)
01562 MulAccumulateBottom(6,1)
01563 MulAccumulateBottom(5,2)
01564 MulAccumulateBottom(4,3)
01565 MulAccumulateBottom(3,4)
01566 MulAccumulateBottom(2,5)
01567 MulAccumulateBottom(1,6)
01568 MulAccumulateBottom(0,7)
01569 MulStoreDigit(7)
01570 MulEpilogue
01571 }
01572
01573 #undef AS1
01574 #undef AS2
01575
01576 #else <span class="comment">// not x86 - no processor specific code at this layer</span>
01577
01578 typedef Portable LowLevel;
01579
01580 #endif
01581
01582 #ifdef SSE2_INTRINSICS_AVAILABLE
01583
01584 #ifdef __GNUC__
01585 #define CRYPTOPP_FASTCALL
01586 #else
01587 #define CRYPTOPP_FASTCALL __fastcall
01588 #endif
01589
01590 static <span class="keywordtype">void</span> CRYPTOPP_FASTCALL P4_Mul(__m128i *C, const __m128i *A, const __m128i *B)
01591 {
01592 __m128i a3210 = _mm_load_si128(A);
01593 __m128i b3210 = _mm_load_si128(B);
01594
01595 __m128i sum;
01596
01597 __m128i z = _mm_setzero_si128();
01598 __m128i a2b2_a0b0 = _mm_mul_epu32(a3210, b3210);
01599 C[0] = a2b2_a0b0;
01600
01601 __m128i a3120 = _mm_shuffle_epi32(a3210, _MM_SHUFFLE(3, 1, 2, 0));
01602 __m128i b3021 = _mm_shuffle_epi32(b3210, _MM_SHUFFLE(3, 0, 2, 1));
01603 __m128i a1b0_a0b1 = _mm_mul_epu32(a3120, b3021);
01604 __m128i a1b0 = _mm_unpackhi_epi32(a1b0_a0b1, z);
01605 __m128i a0b1 = _mm_unpacklo_epi32(a1b0_a0b1, z);
01606 C[1] = _mm_add_epi64(a1b0, a0b1);
01607
01608 __m128i a31 = _mm_srli_epi64(a3210, 32);
01609 __m128i b31 = _mm_srli_epi64(b3210, 32);
01610 __m128i a3b3_a1b1 = _mm_mul_epu32(a31, b31);
01611 C[6] = a3b3_a1b1;
01612
01613 __m128i a1b1 = _mm_unpacklo_epi32(a3b3_a1b1, z);
01614 __m128i b3012 = _mm_shuffle_epi32(b3210, _MM_SHUFFLE(3, 0, 1, 2));
01615 __m128i a2b0_a0b2 = _mm_mul_epu32(a3210, b3012);
01616 __m128i a0b2 = _mm_unpacklo_epi32(a2b0_a0b2, z);
01617 __m128i a2b0 = _mm_unpackhi_epi32(a2b0_a0b2, z);
01618 sum = _mm_add_epi64(a1b1, a0b2);
01619 C[2] = _mm_add_epi64(sum, a2b0);
01620
01621 __m128i a2301 = _mm_shuffle_epi32(a3210, _MM_SHUFFLE(2, 3, 0, 1));
01622 __m128i b2103 = _mm_shuffle_epi32(b3210, _MM_SHUFFLE(2, 1, 0, 3));
01623 __m128i a3b0_a1b2 = _mm_mul_epu32(a2301, b3012);
01624 __m128i a2b1_a0b3 = _mm_mul_epu32(a3210, b2103);
01625 __m128i a3b0 = _mm_unpackhi_epi32(a3b0_a1b2, z);
01626 __m128i a1b2 = _mm_unpacklo_epi32(a3b0_a1b2, z);
01627 __m128i a2b1 = _mm_unpackhi_epi32(a2b1_a0b3, z);
01628 __m128i a0b3 = _mm_unpacklo_epi32(a2b1_a0b3, z);
01629 __m128i sum1 = _mm_add_epi64(a3b0, a1b2);
01630 sum = _mm_add_epi64(a2b1, a0b3);
01631 C[3] = _mm_add_epi64(sum, sum1);
01632
01633 __m128i a3b1_a1b3 = _mm_mul_epu32(a2301, b2103);
01634 __m128i a2b2 = _mm_unpackhi_epi32(a2b2_a0b0, z);
01635 __m128i a3b1 = _mm_unpackhi_epi32(a3b1_a1b3, z);
01636 __m128i a1b3 = _mm_unpacklo_epi32(a3b1_a1b3, z);
01637 sum = _mm_add_epi64(a2b2, a3b1);
01638 C[4] = _mm_add_epi64(sum, a1b3);
01639
01640 __m128i a1302 = _mm_shuffle_epi32(a3210, _MM_SHUFFLE(1, 3, 0, 2));
01641 __m128i b1203 = _mm_shuffle_epi32(b3210, _MM_SHUFFLE(1, 2, 0, 3));
01642 __m128i a3b2_a2b3 = _mm_mul_epu32(a1302, b1203);
01643 __m128i a3b2 = _mm_unpackhi_epi32(a3b2_a2b3, z);
01644 __m128i a2b3 = _mm_unpacklo_epi32(a3b2_a2b3, z);
01645 C[5] = _mm_add_epi64(a3b2, a2b3);
01646 }
01647
01648 <span class="keywordtype">void</span> P4Optimized::Multiply4(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
01649 {
01650 __m128i temp[7];
01651 <span class="keyword">const</span> word *w = (word *)temp;
01652 <span class="keyword">const</span> __m64 *mw = (__m64 *)w;
01653
01654 P4_Mul(temp, (__m128i *)A, (__m128i *)B);
01655
01656 C[0] = w[0];
01657
01658 __m64 s1, s2;
01659
01660 __m64 w1 = _mm_cvtsi32_si64(w[1]);
01661 __m64 w4 = mw[2];
01662 __m64 w6 = mw[3];
01663 __m64 w8 = mw[4];
01664 __m64 w10 = mw[5];
01665 __m64 w12 = mw[6];
01666 __m64 w14 = mw[7];
01667 __m64 w16 = mw[8];
01668 __m64 w18 = mw[9];
01669 __m64 w20 = mw[10];
01670 __m64 w22 = mw[11];
01671 __m64 w26 = _mm_cvtsi32_si64(w[26]);
01672
01673 s1 = _mm_add_si64(w1, w4);
01674 C[1] = _mm_cvtsi64_si32(s1);
01675 s1 = _mm_srli_si64(s1, 32);
01676
01677 s2 = _mm_add_si64(w6, w8);
01678 s1 = _mm_add_si64(s1, s2);
01679 C[2] = _mm_cvtsi64_si32(s1);
01680 s1 = _mm_srli_si64(s1, 32);
01681
01682 s2 = _mm_add_si64(w10, w12);
01683 s1 = _mm_add_si64(s1, s2);
01684 C[3] = _mm_cvtsi64_si32(s1);
01685 s1 = _mm_srli_si64(s1, 32);
01686
01687 s2 = _mm_add_si64(w14, w16);
01688 s1 = _mm_add_si64(s1, s2);
01689 C[4] = _mm_cvtsi64_si32(s1);
01690 s1 = _mm_srli_si64(s1, 32);
01691
01692 s2 = _mm_add_si64(w18, w20);
01693 s1 = _mm_add_si64(s1, s2);
01694 C[5] = _mm_cvtsi64_si32(s1);
01695 s1 = _mm_srli_si64(s1, 32);
01696
01697 s2 = _mm_add_si64(w22, w26);
01698 s1 = _mm_add_si64(s1, s2);
01699 C[6] = _mm_cvtsi64_si32(s1);
01700 s1 = _mm_srli_si64(s1, 32);
01701
01702 C[7] = _mm_cvtsi64_si32(s1) + w[27];
01703 _mm_empty();
01704 }
01705
01706 <span class="keywordtype">void</span> P4Optimized::Multiply8(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
01707 {
01708 __m128i temp[28];
01709 <span class="keyword">const</span> word *w = (word *)temp;
01710 <span class="keyword">const</span> __m64 *mw = (__m64 *)w;
01711 <span class="keyword">const</span> word *x = (word *)temp+7*4;
01712 <span class="keyword">const</span> __m64 *mx = (__m64 *)x;
01713 <span class="keyword">const</span> word *y = (word *)temp+7*4*2;
01714 <span class="keyword">const</span> __m64 *my = (__m64 *)y;
01715 <span class="keyword">const</span> word *z = (word *)temp+7*4*3;
01716 <span class="keyword">const</span> __m64 *mz = (__m64 *)z;
01717
01718 P4_Mul(temp, (__m128i *)A, (__m128i *)B);
01719
01720 P4_Mul(temp+7, (__m128i *)A+1, (__m128i *)B);
01721
01722 P4_Mul(temp+14, (__m128i *)A, (__m128i *)B+1);
01723
01724 P4_Mul(temp+21, (__m128i *)A+1, (__m128i *)B+1);
01725
01726 C[0] = w[0];
01727
01728 __m64 s1, s2, s3, s4;
01729
01730 __m64 w1 = _mm_cvtsi32_si64(w[1]);
01731 __m64 w4 = mw[2];
01732 __m64 w6 = mw[3];
01733 __m64 w8 = mw[4];
01734 __m64 w10 = mw[5];
01735 __m64 w12 = mw[6];
01736 __m64 w14 = mw[7];
01737 __m64 w16 = mw[8];
01738 __m64 w18 = mw[9];
01739 __m64 w20 = mw[10];
01740 __m64 w22 = mw[11];
01741 __m64 w26 = _mm_cvtsi32_si64(w[26]);
01742 __m64 w27 = _mm_cvtsi32_si64(w[27]);
01743
01744 __m64 x0 = _mm_cvtsi32_si64(x[0]);
01745 __m64 x1 = _mm_cvtsi32_si64(x[1]);
01746 __m64 x4 = mx[2];
01747 __m64 x6 = mx[3];
01748 __m64 x8 = mx[4];
01749 __m64 x10 = mx[5];
01750 __m64 x12 = mx[6];
01751 __m64 x14 = mx[7];
01752 __m64 x16 = mx[8];
01753 __m64 x18 = mx[9];
01754 __m64 x20 = mx[10];
01755 __m64 x22 = mx[11];
01756 __m64 x26 = _mm_cvtsi32_si64(x[26]);
01757 __m64 x27 = _mm_cvtsi32_si64(x[27]);
01758
01759 __m64 y0 = _mm_cvtsi32_si64(y[0]);
01760 __m64 y1 = _mm_cvtsi32_si64(y[1]);
01761 __m64 y4 = my[2];
01762 __m64 y6 = my[3];
01763 __m64 y8 = my[4];
01764 __m64 y10 = my[5];
01765 __m64 y12 = my[6];
01766 __m64 y14 = my[7];
01767 __m64 y16 = my[8];
01768 __m64 y18 = my[9];
01769 __m64 y20 = my[10];
01770 __m64 y22 = my[11];
01771 __m64 y26 = _mm_cvtsi32_si64(y[26]);
01772 __m64 y27 = _mm_cvtsi32_si64(y[27]);
01773
01774 __m64 z0 = _mm_cvtsi32_si64(z[0]);
01775 __m64 z1 = _mm_cvtsi32_si64(z[1]);
01776 __m64 z4 = mz[2];
01777 __m64 z6 = mz[3];
01778 __m64 z8 = mz[4];
01779 __m64 z10 = mz[5];
01780 __m64 z12 = mz[6];
01781 __m64 z14 = mz[7];
01782 __m64 z16 = mz[8];
01783 __m64 z18 = mz[9];
01784 __m64 z20 = mz[10];
01785 __m64 z22 = mz[11];
01786 __m64 z26 = _mm_cvtsi32_si64(z[26]);
01787
01788 s1 = _mm_add_si64(w1, w4);
01789 C[1] = _mm_cvtsi64_si32(s1);
01790 s1 = _mm_srli_si64(s1, 32);
01791
01792 s2 = _mm_add_si64(w6, w8);
01793 s1 = _mm_add_si64(s1, s2);
01794 C[2] = _mm_cvtsi64_si32(s1);
01795 s1 = _mm_srli_si64(s1, 32);
01796
01797 s2 = _mm_add_si64(w10, w12);
01798 s1 = _mm_add_si64(s1, s2);
01799 C[3] = _mm_cvtsi64_si32(s1);
01800 s1 = _mm_srli_si64(s1, 32);
01801
01802 s3 = _mm_add_si64(x0, y0);
01803 s2 = _mm_add_si64(w14, w16);
01804 s1 = _mm_add_si64(s1, s3);
01805 s1 = _mm_add_si64(s1, s2);
01806 C[4] = _mm_cvtsi64_si32(s1);
01807 s1 = _mm_srli_si64(s1, 32);
01808
01809 s3 = _mm_add_si64(x1, y1);
01810 s4 = _mm_add_si64(x4, y4);
01811 s1 = _mm_add_si64(s1, w18);
01812 s3 = _mm_add_si64(s3, s4);
01813 s1 = _mm_add_si64(s1, w20);
01814 s1 = _mm_add_si64(s1, s3);
01815 C[5] = _mm_cvtsi64_si32(s1);
01816 s1 = _mm_srli_si64(s1, 32);
01817
01818 s3 = _mm_add_si64(x6, y6);
01819 s4 = _mm_add_si64(x8, y8);
01820 s1 = _mm_add_si64(s1, w22);
01821 s3 = _mm_add_si64(s3, s4);
01822 s1 = _mm_add_si64(s1, w26);
01823 s1 = _mm_add_si64(s1, s3);
01824 C[6] = _mm_cvtsi64_si32(s1);
01825 s1 = _mm_srli_si64(s1, 32);
01826
01827 s3 = _mm_add_si64(x10, y10);
01828 s4 = _mm_add_si64(x12, y12);
01829 s1 = _mm_add_si64(s1, w27);
01830 s3 = _mm_add_si64(s3, s4);
01831 s1 = _mm_add_si64(s1, s3);
01832 C[7] = _mm_cvtsi64_si32(s1);
01833 s1 = _mm_srli_si64(s1, 32);
01834
01835 s3 = _mm_add_si64(x14, y14);
01836 s4 = _mm_add_si64(x16, y16);
01837 s1 = _mm_add_si64(s1, z0);
01838 s3 = _mm_add_si64(s3, s4);
01839 s1 = _mm_add_si64(s1, s3);
01840 C[8] = _mm_cvtsi64_si32(s1);
01841 s1 = _mm_srli_si64(s1, 32);
01842
01843 s3 = _mm_add_si64(x18, y18);
01844 s4 = _mm_add_si64(x20, y20);
01845 s1 = _mm_add_si64(s1, z1);
01846 s3 = _mm_add_si64(s3, s4);
01847 s1 = _mm_add_si64(s1, z4);
01848 s1 = _mm_add_si64(s1, s3);
01849 C[9] = _mm_cvtsi64_si32(s1);
01850 s1 = _mm_srli_si64(s1, 32);
01851
01852 s3 = _mm_add_si64(x22, y22);
01853 s4 = _mm_add_si64(x26, y26);
01854 s1 = _mm_add_si64(s1, z6);
01855 s3 = _mm_add_si64(s3, s4);
01856 s1 = _mm_add_si64(s1, z8);
01857 s1 = _mm_add_si64(s1, s3);
01858 C[10] = _mm_cvtsi64_si32(s1);
01859 s1 = _mm_srli_si64(s1, 32);
01860
01861 s3 = _mm_add_si64(x27, y27);
01862 s1 = _mm_add_si64(s1, z10);
01863 s1 = _mm_add_si64(s1, z12);
01864 s1 = _mm_add_si64(s1, s3);
01865 C[11] = _mm_cvtsi64_si32(s1);
01866 s1 = _mm_srli_si64(s1, 32);
01867
01868 s3 = _mm_add_si64(z14, z16);
01869 s1 = _mm_add_si64(s1, s3);
01870 C[12] = _mm_cvtsi64_si32(s1);
01871 s1 = _mm_srli_si64(s1, 32);
01872
01873 s3 = _mm_add_si64(z18, z20);
01874 s1 = _mm_add_si64(s1, s3);
01875 C[13] = _mm_cvtsi64_si32(s1);
01876 s1 = _mm_srli_si64(s1, 32);
01877
01878 s3 = _mm_add_si64(z22, z26);
01879 s1 = _mm_add_si64(s1, s3);
01880 C[14] = _mm_cvtsi64_si32(s1);
01881 s1 = _mm_srli_si64(s1, 32);
01882
01883 C[15] = z[27] + _mm_cvtsi64_si32(s1);
01884 _mm_empty();
01885 }
01886
01887 <span class="keywordtype">void</span> P4Optimized::Multiply8Bottom(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
01888 {
01889 __m128i temp[21];
01890 <span class="keyword">const</span> word *w = (word *)temp;
01891 <span class="keyword">const</span> __m64 *mw = (__m64 *)w;
01892 <span class="keyword">const</span> word *x = (word *)temp+7*4;
01893 <span class="keyword">const</span> __m64 *mx = (__m64 *)x;
01894 <span class="keyword">const</span> word *y = (word *)temp+7*4*2;
01895 <span class="keyword">const</span> __m64 *my = (__m64 *)y;
01896
01897 P4_Mul(temp, (__m128i *)A, (__m128i *)B);
01898
01899 P4_Mul(temp+7, (__m128i *)A+1, (__m128i *)B);
01900
01901 P4_Mul(temp+14, (__m128i *)A, (__m128i *)B+1);
01902
01903 C[0] = w[0];
01904
01905 __m64 s1, s2, s3, s4;
01906
01907 __m64 w1 = _mm_cvtsi32_si64(w[1]);
01908 __m64 w4 = mw[2];
01909 __m64 w6 = mw[3];
01910 __m64 w8 = mw[4];
01911 __m64 w10 = mw[5];
01912 __m64 w12 = mw[6];
01913 __m64 w14 = mw[7];
01914 __m64 w16 = mw[8];
01915 __m64 w18 = mw[9];
01916 __m64 w20 = mw[10];
01917 __m64 w22 = mw[11];
01918 __m64 w26 = _mm_cvtsi32_si64(w[26]);
01919
01920 __m64 x0 = _mm_cvtsi32_si64(x[0]);
01921 __m64 x1 = _mm_cvtsi32_si64(x[1]);
01922 __m64 x4 = mx[2];
01923 __m64 x6 = mx[3];
01924 __m64 x8 = mx[4];
01925
01926 __m64 y0 = _mm_cvtsi32_si64(y[0]);
01927 __m64 y1 = _mm_cvtsi32_si64(y[1]);
01928 __m64 y4 = my[2];
01929 __m64 y6 = my[3];
01930 __m64 y8 = my[4];
01931
01932 s1 = _mm_add_si64(w1, w4);
01933 C[1] = _mm_cvtsi64_si32(s1);
01934 s1 = _mm_srli_si64(s1, 32);
01935
01936 s2 = _mm_add_si64(w6, w8);
01937 s1 = _mm_add_si64(s1, s2);
01938 C[2] = _mm_cvtsi64_si32(s1);
01939 s1 = _mm_srli_si64(s1, 32);
01940
01941 s2 = _mm_add_si64(w10, w12);
01942 s1 = _mm_add_si64(s1, s2);
01943 C[3] = _mm_cvtsi64_si32(s1);
01944 s1 = _mm_srli_si64(s1, 32);
01945
01946 s3 = _mm_add_si64(x0, y0);
01947 s2 = _mm_add_si64(w14, w16);
01948 s1 = _mm_add_si64(s1, s3);
01949 s1 = _mm_add_si64(s1, s2);
01950 C[4] = _mm_cvtsi64_si32(s1);
01951 s1 = _mm_srli_si64(s1, 32);
01952
01953 s3 = _mm_add_si64(x1, y1);
01954 s4 = _mm_add_si64(x4, y4);
01955 s1 = _mm_add_si64(s1, w18);
01956 s3 = _mm_add_si64(s3, s4);
01957 s1 = _mm_add_si64(s1, w20);
01958 s1 = _mm_add_si64(s1, s3);
01959 C[5] = _mm_cvtsi64_si32(s1);
01960 s1 = _mm_srli_si64(s1, 32);
01961
01962 s3 = _mm_add_si64(x6, y6);
01963 s4 = _mm_add_si64(x8, y8);
01964 s1 = _mm_add_si64(s1, w22);
01965 s3 = _mm_add_si64(s3, s4);
01966 s1 = _mm_add_si64(s1, w26);
01967 s1 = _mm_add_si64(s1, s3);
01968 C[6] = _mm_cvtsi64_si32(s1);
01969 s1 = _mm_srli_si64(s1, 32);
01970
01971 C[7] = _mm_cvtsi64_si32(s1) + w[27] + x[10] + y[10] + x[12] + y[12];
01972 _mm_empty();
01973 }
01974
01975 <span class="preprocessor">#endif // #ifdef SSE2_INTRINSICS_AVAILABLE</span>
01976 <span class="preprocessor"></span>
01977 <span class="comment">// ********************************************************</span>
01978
01979 <span class="preprocessor">#define A0 A</span>
01980 <span class="preprocessor"></span><span class="preprocessor">#define A1 (A+N2)</span>
01981 <span class="preprocessor"></span><span class="preprocessor">#define B0 B</span>
01982 <span class="preprocessor"></span><span class="preprocessor">#define B1 (B+N2)</span>
01983 <span class="preprocessor"></span>
01984 <span class="preprocessor">#define T0 T</span>
01985 <span class="preprocessor"></span><span class="preprocessor">#define T1 (T+N2)</span>
01986 <span class="preprocessor"></span><span class="preprocessor">#define T2 (T+N)</span>
01987 <span class="preprocessor"></span><span class="preprocessor">#define T3 (T+N+N2)</span>
01988 <span class="preprocessor"></span>
01989 <span class="preprocessor">#define R0 R</span>
01990 <span class="preprocessor"></span><span class="preprocessor">#define R1 (R+N2)</span>
01991 <span class="preprocessor"></span><span class="preprocessor">#define R2 (R+N)</span>
01992 <span class="preprocessor"></span><span class="preprocessor">#define R3 (R+N+N2)</span>
01993 <span class="preprocessor"></span>
01994 <span class="comment">// R[2*N] - result = A*B</span>
01995 <span class="comment">// T[2*N] - temporary work space</span>
01996 <span class="comment">// A[N] --- multiplier</span>
01997 <span class="comment">// B[N] --- multiplicant</span>
01998
01999 <span class="keywordtype">void</span> RecursiveMultiply(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02000 {
02001 assert(N>=2 && N%2==0);
02002
02003 <span class="keywordflow">if</span> (LowLevel::MultiplyRecursionLimit() >= 8 && N==8)
02004 LowLevel::Multiply8(R, A, B);
02005 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (LowLevel::MultiplyRecursionLimit() >= 4 && N==4)
02006 LowLevel::Multiply4(R, A, B);
02007 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (N==2)
02008 LowLevel::Multiply2(R, A, B);
02009 <span class="keywordflow">else</span>
02010 {
02011 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N2 = N/2;
02012 <span class="keywordtype">int</span> carry;
02013
02014 <span class="keywordtype">int</span> aComp = Compare(A0, A1, N2);
02015 <span class="keywordtype">int</span> bComp = Compare(B0, B1, N2);
02016
02017 <span class="keywordflow">switch</span> (2*aComp + aComp + bComp)
02018 {
02019 <span class="keywordflow">case</span> -4:
02020 LowLevel::Subtract(R0, A1, A0, N2);
02021 LowLevel::Subtract(R1, B0, B1, N2);
02022 RecursiveMultiply(T0, T2, R0, R1, N2);
02023 LowLevel::Subtract(T1, T1, R0, N2);
02024 carry = -1;
02025 <span class="keywordflow">break</span>;
02026 <span class="keywordflow">case</span> -2:
02027 LowLevel::Subtract(R0, A1, A0, N2);
02028 LowLevel::Subtract(R1, B0, B1, N2);
02029 RecursiveMultiply(T0, T2, R0, R1, N2);
02030 carry = 0;
02031 <span class="keywordflow">break</span>;
02032 <span class="keywordflow">case</span> 2:
02033 LowLevel::Subtract(R0, A0, A1, N2);
02034 LowLevel::Subtract(R1, B1, B0, N2);
02035 RecursiveMultiply(T0, T2, R0, R1, N2);
02036 carry = 0;
02037 <span class="keywordflow">break</span>;
02038 <span class="keywordflow">case</span> 4:
02039 LowLevel::Subtract(R0, A1, A0, N2);
02040 LowLevel::Subtract(R1, B0, B1, N2);
02041 RecursiveMultiply(T0, T2, R0, R1, N2);
02042 LowLevel::Subtract(T1, T1, R1, N2);
02043 carry = -1;
02044 <span class="keywordflow">break</span>;
02045 <span class="keywordflow">default</span>:
02046 SetWords(T0, 0, N);
02047 carry = 0;
02048 }
02049
02050 RecursiveMultiply(R0, T2, A0, B0, N2);
02051 RecursiveMultiply(R2, T2, A1, B1, N2);
02052
02053 <span class="comment">// now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1</span>
02054
02055 carry += LowLevel::Add(T0, T0, R0, N);
02056 carry += LowLevel::Add(T0, T0, R2, N);
02057 carry += LowLevel::Add(R1, R1, T0, N);
02058
02059 assert (carry >= 0 && carry <= 2);
02060 Increment(R3, N2, carry);
02061 }
02062 }
02063
02064 <span class="comment">// R[2*N] - result = A*A</span>
02065 <span class="comment">// T[2*N] - temporary work space</span>
02066 <span class="comment">// A[N] --- number to be squared</span>
02067
02068 <span class="keywordtype">void</span> RecursiveSquare(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02069 {
02070 assert(N && N%2==0);
02071 <span class="keywordflow">if</span> (LowLevel::SquareRecursionLimit() >= 8 && N==8)
02072 LowLevel::Square8(R, A);
02073 <span class="keywordflow">if</span> (LowLevel::SquareRecursionLimit() >= 4 && N==4)
02074 LowLevel::Square4(R, A);
02075 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (N==2)
02076 LowLevel::Square2(R, A);
02077 <span class="keywordflow">else</span>
02078 {
02079 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N2 = N/2;
02080
02081 RecursiveSquare(R0, T2, A0, N2);
02082 RecursiveSquare(R2, T2, A1, N2);
02083 RecursiveMultiply(T0, T2, A0, A1, N2);
02084
02085 word carry = LowLevel::Add(R1, R1, T0, N);
02086 carry += LowLevel::Add(R1, R1, T0, N);
02087 Increment(R3, N2, carry);
02088 }
02089 }
02090
02091 <span class="comment">// R[N] - bottom half of A*B</span>
02092 <span class="comment">// T[N] - temporary work space</span>
02093 <span class="comment">// A[N] - multiplier</span>
02094 <span class="comment">// B[N] - multiplicant</span>
02095
02096 <span class="keywordtype">void</span> RecursiveMultiplyBottom(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02097 {
02098 assert(N>=2 && N%2==0);
02099 <span class="keywordflow">if</span> (LowLevel::MultiplyBottomRecursionLimit() >= 8 && N==8)
02100 LowLevel::Multiply8Bottom(R, A, B);
02101 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (LowLevel::MultiplyBottomRecursionLimit() >= 4 && N==4)
02102 LowLevel::Multiply4Bottom(R, A, B);
02103 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (N==2)
02104 LowLevel::Multiply2Bottom(R, A, B);
02105 <span class="keywordflow">else</span>
02106 {
02107 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N2 = N/2;
02108
02109 RecursiveMultiply(R, T, A0, B0, N2);
02110 RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
02111 LowLevel::Add(R1, R1, T0, N2);
02112 RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
02113 LowLevel::Add(R1, R1, T0, N2);
02114 }
02115 }
02116
02117 <span class="comment">// R[N] --- upper half of A*B</span>
02118 <span class="comment">// T[2*N] - temporary work space</span>
02119 <span class="comment">// L[N] --- lower half of A*B</span>
02120 <span class="comment">// A[N] --- multiplier</span>
02121 <span class="comment">// B[N] --- multiplicant</span>
02122
02123 <span class="keywordtype">void</span> RecursiveMultiplyTop(word *R, word *T, <span class="keyword">const</span> word *L, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02124 {
02125 assert(N>=2 && N%2==0);
02126
02127 <span class="keywordflow">if</span> (N==4)
02128 {
02129 LowLevel::Multiply4(T, A, B);
02130 memcpy(R, T+4, 4*WORD_SIZE);
02131 }
02132 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (N==2)
02133 {
02134 LowLevel::Multiply2(T, A, B);
02135 memcpy(R, T+2, 2*WORD_SIZE);
02136 }
02137 <span class="keywordflow">else</span>
02138 {
02139 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N2 = N/2;
02140 <span class="keywordtype">int</span> carry;
02141
02142 <span class="keywordtype">int</span> aComp = Compare(A0, A1, N2);
02143 <span class="keywordtype">int</span> bComp = Compare(B0, B1, N2);
02144
02145 <span class="keywordflow">switch</span> (2*aComp + aComp + bComp)
02146 {
02147 <span class="keywordflow">case</span> -4:
02148 LowLevel::Subtract(R0, A1, A0, N2);
02149 LowLevel::Subtract(R1, B0, B1, N2);
02150 RecursiveMultiply(T0, T2, R0, R1, N2);
02151 LowLevel::Subtract(T1, T1, R0, N2);
02152 carry = -1;
02153 <span class="keywordflow">break</span>;
02154 <span class="keywordflow">case</span> -2:
02155 LowLevel::Subtract(R0, A1, A0, N2);
02156 LowLevel::Subtract(R1, B0, B1, N2);
02157 RecursiveMultiply(T0, T2, R0, R1, N2);
02158 carry = 0;
02159 <span class="keywordflow">break</span>;
02160 <span class="keywordflow">case</span> 2:
02161 LowLevel::Subtract(R0, A0, A1, N2);
02162 LowLevel::Subtract(R1, B1, B0, N2);
02163 RecursiveMultiply(T0, T2, R0, R1, N2);
02164 carry = 0;
02165 <span class="keywordflow">break</span>;
02166 <span class="keywordflow">case</span> 4:
02167 LowLevel::Subtract(R0, A1, A0, N2);
02168 LowLevel::Subtract(R1, B0, B1, N2);
02169 RecursiveMultiply(T0, T2, R0, R1, N2);
02170 LowLevel::Subtract(T1, T1, R1, N2);
02171 carry = -1;
02172 <span class="keywordflow">break</span>;
02173 <span class="keywordflow">default</span>:
02174 SetWords(T0, 0, N);
02175 carry = 0;
02176 }
02177
02178 RecursiveMultiply(T2, R0, A1, B1, N2);
02179
02180 <span class="comment">// now T[01] holds (A1-A0)*(B0-B1), T[23] holds A1*B1</span>
02181
02182 word c2 = LowLevel::Subtract(R0, L+N2, L, N2);
02183 c2 += LowLevel::Subtract(R0, R0, T0, N2);
02184 word t = (Compare(R0, T2, N2) == -1);
02185
02186 carry += t;
02187 carry += Increment(R0, N2, c2+t);
02188 carry += LowLevel::Add(R0, R0, T1, N2);
02189 carry += LowLevel::Add(R0, R0, T3, N2);
02190 assert (carry >= 0 && carry <= 2);
02191
02192 CopyWords(R1, T3, N2);
02193 Increment(R1, N2, carry);
02194 }
02195 }
02196
02197 <span class="keyword">inline</span> word Add(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02198 {
02199 <span class="keywordflow">return</span> LowLevel::Add(C, A, B, N);
02200 }
02201
02202 <span class="keyword">inline</span> word Subtract(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02203 {
02204 <span class="keywordflow">return</span> LowLevel::Subtract(C, A, B, N);
02205 }
02206
02207 <span class="keyword">inline</span> <span class="keywordtype">void</span> Multiply(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02208 {
02209 RecursiveMultiply(R, T, A, B, N);
02210 }
02211
02212 <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="class_square.html">Square</a>(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02213 {
02214 RecursiveSquare(R, T, A, N);
02215 }
02216
02217 <span class="keyword">inline</span> <span class="keywordtype">void</span> MultiplyBottom(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02218 {
02219 RecursiveMultiplyBottom(R, T, A, B, N);
02220 }
02221
02222 <span class="keyword">inline</span> <span class="keywordtype">void</span> MultiplyTop(word *R, word *T, <span class="keyword">const</span> word *L, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02223 {
02224 RecursiveMultiplyTop(R, T, L, A, B, N);
02225 }
02226
02227 <span class="keyword">static</span> word LinearMultiply(word *C, <span class="keyword">const</span> word *A, word B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02228 {
02229 word carry=0;
02230 <span class="keywordflow">for</span>(<span class="keywordtype">unsigned</span> i=0; i<N; i++)
02231 {
02232 DWord p = DWord::MultiplyAndAdd(A[i], B, carry);
02233 C[i] = p.GetLowHalf();
02234 carry = p.GetHighHalf();
02235 }
02236 <span class="keywordflow">return</span> carry;
02237 }
02238
02239 <span class="comment">// R[NA+NB] - result = A*B</span>
02240 <span class="comment">// T[NA+NB] - temporary work space</span>
02241 <span class="comment">// A[NA] ---- multiplier</span>
02242 <span class="comment">// B[NB] ---- multiplicant</span>
02243
02244 <span class="keywordtype">void</span> AsymmetricMultiply(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> NA, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> NB)
02245 {
02246 <span class="keywordflow">if</span> (NA == NB)
02247 {
02248 <span class="keywordflow">if</span> (A == B)
02249 Square(R, T, A, NA);
02250 <span class="keywordflow">else</span>
02251 Multiply(R, T, A, B, NA);
02252
02253 <span class="keywordflow">return</span>;
02254 }
02255
02256 <span class="keywordflow">if</span> (NA > NB)
02257 {
02258 std::swap(A, B);
02259 std::swap(NA, NB);
02260 }
02261
02262 assert(NB % NA == 0);
02263 assert((NB/NA)%2 == 0); <span class="comment">// NB is an even multiple of NA</span>
02264
02265 <span class="keywordflow">if</span> (NA==2 && !A[1])
02266 {
02267 <span class="keywordflow">switch</span> (A[0])
02268 {
02269 <span class="keywordflow">case</span> 0:
02270 SetWords(R, 0, NB+2);
02271 <span class="keywordflow">return</span>;
02272 <span class="keywordflow">case</span> 1:
02273 CopyWords(R, B, NB);
02274 R[NB] = R[NB+1] = 0;
02275 <span class="keywordflow">return</span>;
02276 <span class="keywordflow">default</span>:
02277 R[NB] = LinearMultiply(R, B, A[0], NB);
02278 R[NB+1] = 0;
02279 <span class="keywordflow">return</span>;
02280 }
02281 }
02282
02283 Multiply(R, T, A, B, NA);
02284 CopyWords(T+2*NA, R+NA, NA);
02285
02286 <span class="keywordtype">unsigned</span> i;
02287
02288 <span class="keywordflow">for</span> (i=2*NA; i<NB; i+=2*NA)
02289 Multiply(T+NA+i, T, A, B+i, NA);
02290 <span class="keywordflow">for</span> (i=NA; i<NB; i+=2*NA)
02291 Multiply(R+i, T, A, B+i, NA);
02292
02293 <span class="keywordflow">if</span> (Add(R+NA, R+NA, T+2*NA, NB-NA))
02294 Increment(R+NB, NA);
02295 }
02296
02297 <span class="comment">// R[N] ----- result = A inverse mod 2**(WORD_BITS*N)</span>
02298 <span class="comment">// T[3*N/2] - temporary work space</span>
02299 <span class="comment">// A[N] ----- an odd number as input</span>
02300
02301 <span class="keywordtype">void</span> RecursiveInverseModPower2(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02302 {
02303 <span class="keywordflow">if</span> (N==2)
02304 {
02305 T[0] = AtomicInverseModPower2(A[0]);
02306 T[1] = 0;
02307 LowLevel::Multiply2Bottom(T+2, T, A);
02308 TwosComplement(T+2, 2);
02309 Increment(T+2, 2, 2);
02310 LowLevel::Multiply2Bottom(R, T, T+2);
02311 }
02312 <span class="keywordflow">else</span>
02313 {
02314 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N2 = N/2;
02315 RecursiveInverseModPower2(R0, T0, A0, N2);
02316 T0[0] = 1;
02317 SetWords(T0+1, 0, N2-1);
02318 MultiplyTop(R1, T1, T0, R0, A0, N2);
02319 MultiplyBottom(T0, T1, R0, A1, N2);
02320 Add(T0, R1, T0, N2);
02321 TwosComplement(T0, N2);
02322 MultiplyBottom(R1, T1, R0, T0, N2);
02323 }
02324 }
02325
02326 <span class="comment">// R[N] --- result = X/(2**(WORD_BITS*N)) mod M</span>
02327 <span class="comment">// T[3*N] - temporary work space</span>
02328 <span class="comment">// X[2*N] - number to be reduced</span>
02329 <span class="comment">// M[N] --- modulus</span>
02330 <span class="comment">// U[N] --- multiplicative inverse of M mod 2**(WORD_BITS*N)</span>
02331
02332 <span class="keywordtype">void</span> MontgomeryReduce(word *R, word *T, <span class="keyword">const</span> word *X, <span class="keyword">const</span> word *M, <span class="keyword">const</span> word *U, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02333 {
02334 MultiplyBottom(R, T, X, U, N);
02335 MultiplyTop(T, T+N, X, R, M, N);
02336 word borrow = Subtract(T, X+N, T, N);
02337 <span class="comment">// defend against timing attack by doing this Add even when not needed</span>
02338 word carry = Add(T+N, T, M, N);
02339 assert(carry || !borrow);
02340 CopyWords(R, T + (borrow ? N : 0), N);
02341 }
02342
02343 <span class="comment">// R[N] --- result = X/(2**(WORD_BITS*N/2)) mod M</span>
02344 <span class="comment">// T[2*N] - temporary work space</span>
02345 <span class="comment">// X[2*N] - number to be reduced</span>
02346 <span class="comment">// M[N] --- modulus</span>
02347 <span class="comment">// U[N/2] - multiplicative inverse of M mod 2**(WORD_BITS*N/2)</span>
02348 <span class="comment">// V[N] --- 2**(WORD_BITS*3*N/2) mod M</span>
02349
02350 <span class="keywordtype">void</span> HalfMontgomeryReduce(word *R, word *T, <span class="keyword">const</span> word *X, <span class="keyword">const</span> word *M, <span class="keyword">const</span> word *U, <span class="keyword">const</span> word *V, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02351 {
02352 assert(N%2==0 && N>=4);
02353
02354 <span class="preprocessor">#define M0 M</span>
02355 <span class="preprocessor"></span><span class="preprocessor">#define M1 (M+N2)</span>
02356 <span class="preprocessor"></span><span class="preprocessor">#define V0 V</span>
02357 <span class="preprocessor"></span><span class="preprocessor">#define V1 (V+N2)</span>
02358 <span class="preprocessor"></span>
02359 <span class="preprocessor">#define X0 X</span>
02360 <span class="preprocessor"></span><span class="preprocessor">#define X1 (X+N2)</span>
02361 <span class="preprocessor"></span><span class="preprocessor">#define X2 (X+N)</span>
02362 <span class="preprocessor"></span><span class="preprocessor">#define X3 (X+N+N2)</span>
02363 <span class="preprocessor"></span>
02364 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N2 = N/2;
02365 Multiply(T0, T2, V0, X3, N2);
02366 <span class="keywordtype">int</span> c2 = Add(T0, T0, X0, N);
02367 MultiplyBottom(T3, T2, T0, U, N2);
02368 MultiplyTop(T2, R, T0, T3, M0, N2);
02369 c2 -= Subtract(T2, T1, T2, N2);
02370 Multiply(T0, R, T3, M1, N2);
02371 c2 -= Subtract(T0, T2, T0, N2);
02372 <span class="keywordtype">int</span> c3 = -(<span class="keywordtype">int</span>)Subtract(T1, X2, T1, N2);
02373 Multiply(R0, T2, V1, X3, N2);
02374 c3 += Add(R, R, T, N);
02375
02376 <span class="keywordflow">if</span> (c2>0)
02377 c3 += Increment(R1, N2);
02378 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (c2<0)
02379 c3 -= Decrement(R1, N2, -c2);
02380
02381 assert(c3>=-1 && c3<=1);
02382 <span class="keywordflow">if</span> (c3>0)
02383 Subtract(R, R, M, N);
02384 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (c3<0)
02385 Add(R, R, M, N);
02386
02387 <span class="preprocessor">#undef M0</span>
02388 <span class="preprocessor"></span><span class="preprocessor">#undef M1</span>
02389 <span class="preprocessor"></span><span class="preprocessor">#undef V0</span>
02390 <span class="preprocessor"></span><span class="preprocessor">#undef V1</span>
02391 <span class="preprocessor"></span>
02392 <span class="preprocessor">#undef X0</span>
02393 <span class="preprocessor"></span><span class="preprocessor">#undef X1</span>
02394 <span class="preprocessor"></span><span class="preprocessor">#undef X2</span>
02395 <span class="preprocessor"></span><span class="preprocessor">#undef X3</span>
02396 <span class="preprocessor"></span>}
02397
02398 <span class="preprocessor">#undef A0</span>
02399 <span class="preprocessor"></span><span class="preprocessor">#undef A1</span>
02400 <span class="preprocessor"></span><span class="preprocessor">#undef B0</span>
02401 <span class="preprocessor"></span><span class="preprocessor">#undef B1</span>
02402 <span class="preprocessor"></span>
02403 <span class="preprocessor">#undef T0</span>
02404 <span class="preprocessor"></span><span class="preprocessor">#undef T1</span>
02405 <span class="preprocessor"></span><span class="preprocessor">#undef T2</span>
02406 <span class="preprocessor"></span><span class="preprocessor">#undef T3</span>
02407 <span class="preprocessor"></span>
02408 <span class="preprocessor">#undef R0</span>
02409 <span class="preprocessor"></span><span class="preprocessor">#undef R1</span>
02410 <span class="preprocessor"></span><span class="preprocessor">#undef R2</span>
02411 <span class="preprocessor"></span><span class="preprocessor">#undef R3</span>
02412 <span class="preprocessor"></span>
02413 <span class="comment">/*</span>
02414 <span class="comment">// do a 3 word by 2 word divide, returns quotient and leaves remainder in A</span>
02415 <span class="comment">static word SubatomicDivide(word *A, word B0, word B1)</span>
02416 <span class="comment">{</span>
02417 <span class="comment"> // assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a word</span>
02418 <span class="comment"> assert(A[2] < B1 || (A[2]==B1 && A[1] < B0));</span>
02419 <span class="comment"></span>
02420 <span class="comment"> // estimate the quotient: do a 2 word by 1 word divide</span>
02421 <span class="comment"> word Q;</span>
02422 <span class="comment"> if (B1+1 == 0)</span>
02423 <span class="comment"> Q = A[2];</span>
02424 <span class="comment"> else</span>
02425 <span class="comment"> Q = DWord(A[1], A[2]).DividedBy(B1+1);</span>
02426 <span class="comment"></span>
02427 <span class="comment"> // now subtract Q*B from A</span>
02428 <span class="comment"> DWord p = DWord::Multiply(B0, Q);</span>
02429 <span class="comment"> DWord u = (DWord) A[0] - p.GetLowHalf();</span>
02430 <span class="comment"> A[0] = u.GetLowHalf();</span>
02431 <span class="comment"> u = (DWord) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - DWord::Multiply(B1, Q);</span>
02432 <span class="comment"> A[1] = u.GetLowHalf();</span>
02433 <span class="comment"> A[2] += u.GetHighHalf();</span>
02434 <span class="comment"></span>
02435 <span class="comment"> // Q <= actual quotient, so fix it</span>
02436 <span class="comment"> while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))</span>
02437 <span class="comment"> {</span>
02438 <span class="comment"> u = (DWord) A[0] - B0;</span>
02439 <span class="comment"> A[0] = u.GetLowHalf();</span>
02440 <span class="comment"> u = (DWord) A[1] - B1 - u.GetHighHalfAsBorrow();</span>
02441 <span class="comment"> A[1] = u.GetLowHalf();</span>
02442 <span class="comment"> A[2] += u.GetHighHalf();</span>
02443 <span class="comment"> Q++;</span>
02444 <span class="comment"> assert(Q); // shouldn't overflow</span>
02445 <span class="comment"> }</span>
02446 <span class="comment"></span>
02447 <span class="comment"> return Q;</span>
02448 <span class="comment">}</span>
02449 <span class="comment"></span>
02450 <span class="comment">// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1</span>
02451 <span class="comment">static inline void AtomicDivide(word *Q, const word *A, const word *B)</span>
02452 <span class="comment">{</span>
02453 <span class="comment"> if (!B[0] && !B[1]) // if divisor is 0, we assume divisor==2**(2*WORD_BITS)</span>
02454 <span class="comment"> {</span>
02455 <span class="comment"> Q[0] = A[2];</span>
02456 <span class="comment"> Q[1] = A[3];</span>
02457 <span class="comment"> }</span>
02458 <span class="comment"> else</span>
02459 <span class="comment"> {</span>
02460 <span class="comment"> word T[4];</span>
02461 <span class="comment"> T[0] = A[0]; T[1] = A[1]; T[2] = A[2]; T[3] = A[3];</span>
02462 <span class="comment"> Q[1] = SubatomicDivide(T+1, B[0], B[1]);</span>
02463 <span class="comment"> Q[0] = SubatomicDivide(T, B[0], B[1]);</span>
02464 <span class="comment"></span>
02465 <span class="comment">#ifndef NDEBUG</span>
02466 <span class="comment"> // multiply quotient and divisor and add remainder, make sure it equals dividend</span>
02467 <span class="comment"> assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));</span>
02468 <span class="comment"> word P[4];</span>
02469 <span class="comment"> LowLevel::Multiply2(P, Q, B);</span>
02470 <span class="comment"> Add(P, P, T, 4);</span>
02471 <span class="comment"> assert(memcmp(P, A, 4*WORD_SIZE)==0);</span>
02472 <span class="comment">#endif</span>
02473 <span class="comment"> }</span>
02474 <span class="comment">}</span>
02475 <span class="comment">*/</span>
02476
02477 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> AtomicDivide(word *Q, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)
02478 {
02479 word T[4];
02480 DWord q = DivideFourWordsByTwo<word, DWord>(T, DWord(A[0], A[1]), DWord(A[2], A[3]), DWord(B[0], B[1]));
02481 Q[0] = q.GetLowHalf();
02482 Q[1] = q.GetHighHalf();
02483
02484 <span class="preprocessor">#ifndef NDEBUG</span>
02485 <span class="preprocessor"></span> <span class="keywordflow">if</span> (B[0] || B[1])
02486 {
02487 <span class="comment">// multiply quotient and divisor and add remainder, make sure it equals dividend</span>
02488 assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
02489 word P[4];
02490 Portable::Multiply2(P, Q, B);
02491 Add(P, P, T, 4);
02492 assert(memcmp(P, A, 4*WORD_SIZE)==0);
02493 }
02494 <span class="preprocessor">#endif</span>
02495 <span class="preprocessor"></span>}
02496
02497 <span class="comment">// for use by Divide(), corrects the underestimated quotient {Q1,Q0}</span>
02498 <span class="keyword">static</span> <span class="keywordtype">void</span> CorrectQuotientEstimate(word *R, word *T, word *Q, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02499 {
02500 assert(N && N%2==0);
02501
02502 <span class="keywordflow">if</span> (Q[1])
02503 {
02504 T[N] = T[N+1] = 0;
02505 <span class="keywordtype">unsigned</span> i;
02506 <span class="keywordflow">for</span> (i=0; i<N; i+=4)
02507 LowLevel::Multiply2(T+i, Q, B+i);
02508 <span class="keywordflow">for</span> (i=2; i<N; i+=4)
02509 <span class="keywordflow">if</span> (LowLevel::Multiply2Add(T+i, Q, B+i))
02510 T[i+5] += (++T[i+4]==0);
02511 }
02512 <span class="keywordflow">else</span>
02513 {
02514 T[N] = LinearMultiply(T, B, Q[0], N);
02515 T[N+1] = 0;
02516 }
02517
02518 word borrow = Subtract(R, R, T, N+2);
02519 assert(!borrow && !R[N+1]);
02520
02521 <span class="keywordflow">while</span> (R[N] || Compare(R, B, N) >= 0)
02522 {
02523 R[N] -= Subtract(R, R, B, N);
02524 Q[1] += (++Q[0]==0);
02525 assert(Q[0] || Q[1]); <span class="comment">// no overflow</span>
02526 }
02527 }
02528
02529 <span class="comment">// R[NB] -------- remainder = A%B</span>
02530 <span class="comment">// Q[NA-NB+2] --- quotient = A/B</span>
02531 <span class="comment">// T[NA+2*NB+4] - temp work space</span>
02532 <span class="comment">// A[NA] -------- dividend</span>
02533 <span class="comment">// B[NB] -------- divisor</span>
02534
02535 <span class="keywordtype">void</span> Divide(word *R, word *Q, word *T, <span class="keyword">const</span> word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> NA, <span class="keyword">const</span> word *B, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> NB)
02536 {
02537 assert(NA && NB && NA%2==0 && NB%2==0);
02538 assert(B[NB-1] || B[NB-2]);
02539 assert(NB <= NA);
02540
02541 <span class="comment">// set up temporary work space</span>
02542 word *<span class="keyword">const</span> TA=T;
02543 word *<span class="keyword">const</span> TB=T+NA+2;
02544 word *<span class="keyword">const</span> TP=T+NA+2+NB;
02545
02546 <span class="comment">// copy B into TB and normalize it so that TB has highest bit set to 1</span>
02547 <span class="keywordtype">unsigned</span> shiftWords = (B[NB-1]==0);
02548 TB[0] = TB[NB-1] = 0;
02549 CopyWords(TB+shiftWords, B, NB-shiftWords);
02550 <span class="keywordtype">unsigned</span> shiftBits = WORD_BITS - BitPrecision(TB[NB-1]);
02551 assert(shiftBits < WORD_BITS);
02552 ShiftWordsLeftByBits(TB, NB, shiftBits);
02553
02554 <span class="comment">// copy A into TA and normalize it</span>
02555 TA[0] = TA[NA] = TA[NA+1] = 0;
02556 CopyWords(TA+shiftWords, A, NA);
02557 ShiftWordsLeftByBits(TA, NA+2, shiftBits);
02558
02559 <span class="keywordflow">if</span> (TA[NA+1]==0 && TA[NA] <= 1)
02560 {
02561 Q[NA-NB+1] = Q[NA-NB] = 0;
02562 <span class="keywordflow">while</span> (TA[NA] || Compare(TA+NA-NB, TB, NB) >= 0)
02563 {
02564 TA[NA] -= Subtract(TA+NA-NB, TA+NA-NB, TB, NB);
02565 ++Q[NA-NB];
02566 }
02567 }
02568 <span class="keywordflow">else</span>
02569 {
02570 NA+=2;
02571 assert(Compare(TA+NA-NB, TB, NB) < 0);
02572 }
02573
02574 word BT[2];
02575 BT[0] = TB[NB-2] + 1;
02576 BT[1] = TB[NB-1] + (BT[0]==0);
02577
02578 <span class="comment">// start reducing TA mod TB, 2 words at a time</span>
02579 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=NA-2; i>=NB; i-=2)
02580 {
02581 AtomicDivide(Q+i-NB, TA+i-2, BT);
02582 CorrectQuotientEstimate(TA+i-NB, TP, Q+i-NB, TB, NB);
02583 }
02584
02585 <span class="comment">// copy TA into R, and denormalize it</span>
02586 CopyWords(R, TA+shiftWords, NB);
02587 ShiftWordsRightByBits(R, NB, shiftBits);
02588 }
02589
02590 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> EvenWordCount(<span class="keyword">const</span> word *X, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02591 {
02592 <span class="keywordflow">while</span> (N && X[N-2]==0 && X[N-1]==0)
02593 N-=2;
02594 <span class="keywordflow">return</span> N;
02595 }
02596
02597 <span class="comment">// return k</span>
02598 <span class="comment">// R[N] --- result = A^(-1) * 2^k mod M</span>
02599 <span class="comment">// T[4*N] - temporary work space</span>
02600 <span class="comment">// A[NA] -- number to take inverse of</span>
02601 <span class="comment">// M[N] --- modulus</span>
02602
02603 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> AlmostInverse(word *R, word *T, <span class="keyword">const</span> word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> NA, <span class="keyword">const</span> word *M, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02604 {
02605 assert(NA<=N && N && N%2==0);
02606
02607 word *b = T;
02608 word *c = T+N;
02609 word *f = T+2*N;
02610 word *g = T+3*N;
02611 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bcLen=2, fgLen=EvenWordCount(M, N);
02612 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> k=0, s=0;
02613
02614 SetWords(T, 0, 3*N);
02615 b[0]=1;
02616 CopyWords(f, A, NA);
02617 CopyWords(g, M, N);
02618
02619 <span class="keywordflow">while</span> (1)
02620 {
02621 word t=f[0];
02622 <span class="keywordflow">while</span> (!t)
02623 {
02624 <span class="keywordflow">if</span> (EvenWordCount(f, fgLen)==0)
02625 {
02626 SetWords(R, 0, N);
02627 <span class="keywordflow">return</span> 0;
02628 }
02629
02630 ShiftWordsRightByWords(f, fgLen, 1);
02631 <span class="keywordflow">if</span> (c[bcLen-1]) bcLen+=2;
02632 assert(bcLen <= N);
02633 ShiftWordsLeftByWords(c, bcLen, 1);
02634 k+=WORD_BITS;
02635 t=f[0];
02636 }
02637
02638 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0;
02639 <span class="keywordflow">while</span> (t%2 == 0)
02640 {
02641 t>>=1;
02642 i++;
02643 }
02644 k+=i;
02645
02646 <span class="keywordflow">if</span> (t==1 && f[1]==0 && EvenWordCount(f, fgLen)==2)
02647 {
02648 <span class="keywordflow">if</span> (s%2==0)
02649 CopyWords(R, b, N);
02650 <span class="keywordflow">else</span>
02651 Subtract(R, M, b, N);
02652 <span class="keywordflow">return</span> k;
02653 }
02654
02655 ShiftWordsRightByBits(f, fgLen, i);
02656 t=ShiftWordsLeftByBits(c, bcLen, i);
02657 <span class="keywordflow">if</span> (t)
02658 {
02659 c[bcLen] = t;
02660 bcLen+=2;
02661 assert(bcLen <= N);
02662 }
02663
02664 <span class="keywordflow">if</span> (f[fgLen-2]==0 && g[fgLen-2]==0 && f[fgLen-1]==0 && g[fgLen-1]==0)
02665 fgLen-=2;
02666
02667 <span class="keywordflow">if</span> (Compare(f, g, fgLen)==-1)
02668 {
02669 std::swap(f, g);
02670 std::swap(b, c);
02671 s++;
02672 }
02673
02674 Subtract(f, f, g, fgLen);
02675
02676 <span class="keywordflow">if</span> (Add(b, b, c, bcLen))
02677 {
02678 b[bcLen] = 1;
02679 bcLen+=2;
02680 assert(bcLen <= N);
02681 }
02682 }
02683 }
02684
02685 <span class="comment">// R[N] - result = A/(2^k) mod M</span>
02686 <span class="comment">// A[N] - input</span>
02687 <span class="comment">// M[N] - modulus</span>
02688
02689 <span class="keywordtype">void</span> DivideByPower2Mod(word *R, <span class="keyword">const</span> word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> k, <span class="keyword">const</span> word *M, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02690 {
02691 CopyWords(R, A, N);
02692
02693 <span class="keywordflow">while</span> (k--)
02694 {
02695 <span class="keywordflow">if</span> (R[0]%2==0)
02696 ShiftWordsRightByBits(R, N, 1);
02697 <span class="keywordflow">else</span>
02698 {
02699 word carry = Add(R, R, M, N);
02700 ShiftWordsRightByBits(R, N, 1);
02701 R[N-1] += carry<<(WORD_BITS-1);
02702 }
02703 }
02704 }
02705
02706 <span class="comment">// R[N] - result = A*(2^k) mod M</span>
02707 <span class="comment">// A[N] - input</span>
02708 <span class="comment">// M[N] - modulus</span>
02709
02710 <span class="keywordtype">void</span> MultiplyByPower2Mod(word *R, <span class="keyword">const</span> word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> k, <span class="keyword">const</span> word *M, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)
02711 {
02712 CopyWords(R, A, N);
02713
02714 <span class="keywordflow">while</span> (k--)
02715 <span class="keywordflow">if</span> (ShiftWordsLeftByBits(R, N, 1) || Compare(R, M, N)>=0)
02716 Subtract(R, R, M, N);
02717 }
02718
02719 <span class="comment">// ******************************************************************</span>
02720
02721 <span class="keyword">static</span> <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};
02722
02723 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> RoundupSize(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
02724 {
02725 <span class="keywordflow">if</span> (n<=8)
02726 <span class="keywordflow">return</span> RoundupSizeTable[n];
02727 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (n<=16)
02728 <span class="keywordflow">return</span> 16;
02729 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (n<=32)
02730 <span class="keywordflow">return</span> 32;
02731 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (n<=64)
02732 <span class="keywordflow">return</span> 64;
02733 <span class="keywordflow">else</span> <span class="keywordflow">return</span> 1U << BitPrecision(n-1);
02734 }
02735
<a name="l02736"></a><a class="code" href="class_integer.html#_integerz37_0">02736</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>()
02737 : reg(2), sign(POSITIVE)
02738 {
02739 reg[0] = reg[1] = 0;
02740 }
02741
<a name="l02742"></a><a class="code" href="class_integer.html#_integerz37_1">02742</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& t)
02743 : reg(RoundupSize(t.WordCount())), sign(t.sign)
02744 {
02745 CopyWords(reg, t.reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
02746 }
02747
<a name="l02748"></a><a class="code" href="class_integer.html#_integerz37_3">02748</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(Sign s, lword value)
02749 : reg(2), sign(s)
02750 {
02751 reg[0] = word(value);
02752 reg[1] = word(SafeRightShift<WORD_BITS>(value));
02753 }
02754
<a name="l02755"></a><a class="code" href="class_integer.html#_integerz37_2">02755</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<span class="keywordtype">signed</span> <span class="keywordtype">long</span> value)
02756 : reg(2)
02757 {
02758 <span class="keywordflow">if</span> (value >= 0)
02759 sign = POSITIVE;
02760 <span class="keywordflow">else</span>
02761 {
02762 sign = NEGATIVE;
02763 value = -value;
02764 }
02765 reg[0] = word(value);
02766 reg[1] = word(SafeRightShift<WORD_BITS>((<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span>)value));
02767 }
02768
<a name="l02769"></a><a class="code" href="class_integer.html#_integerz37_4">02769</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(Sign s, word high, word low)
02770 : reg(2), sign(s)
02771 {
02772 reg[0] = low;
02773 reg[1] = high;
02774 }
02775
<a name="l02776"></a><a class="code" href="class_integer.html#_integerz41_0">02776</a> <span class="keywordtype">bool</span> <a class="code" href="class_integer.html#_integerz41_0">Integer::IsConvertableToLong</a>()<span class="keyword"> const</span>
02777 <span class="keyword"></span>{
02778 <span class="keywordflow">if</span> (<a class="code" href="class_integer.html#_integerz41_3">ByteCount</a>() > <span class="keyword">sizeof</span>(<span class="keywordtype">long</span>))
02779 <span class="keywordflow">return</span> <span class="keyword">false</span>;
02780
02781 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> value = reg[0];
02782 value += SafeLeftShift<WORD_BITS, unsigned long>(reg[1]);
02783
02784 <span class="keywordflow">if</span> (sign==POSITIVE)
02785 <span class="keywordflow">return</span> (<span class="keywordtype">signed</span> <span class="keywordtype">long</span>)value >= 0;
02786 <span class="keywordflow">else</span>
02787 <span class="keywordflow">return</span> -(<span class="keywordtype">signed</span> <span class="keywordtype">long</span>)value < 0;
02788 }
02789
<a name="l02790"></a><a class="code" href="class_integer.html#_integerz41_1">02790</a> <span class="keywordtype">signed</span> <span class="keywordtype">long</span> <a class="code" href="class_integer.html#_integerz41_1">Integer::ConvertToLong</a>()<span class="keyword"> const</span>
02791 <span class="keyword"></span>{
02792 assert(<a class="code" href="class_integer.html#_integerz41_0">IsConvertableToLong</a>());
02793
02794 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> value = reg[0];
02795 value += SafeLeftShift<WORD_BITS, unsigned long>(reg[1]);
02796 <span class="keywordflow">return</span> sign==POSITIVE ? value : -(<span class="keywordtype">signed</span> <span class="keywordtype">long</span>)value;
02797 }
02798
<a name="l02799"></a><a class="code" href="class_integer.html#_integerz37_8">02799</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &encodedInteger, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> byteCount, Signedness s)
02800 {
02801 Decode(encodedInteger, byteCount, s);
02802 }
02803
<a name="l02804"></a><a class="code" href="class_integer.html#_integerz37_7">02804</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<span class="keyword">const</span> byte *encodedInteger, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> byteCount, Signedness s)
02805 {
02806 Decode(encodedInteger, byteCount, s);
02807 }
02808
<a name="l02809"></a><a class="code" href="class_integer.html#_integerz37_9">02809</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt)
02810 {
02811 BERDecode(bt);
02812 }
02813
<a name="l02814"></a><a class="code" href="class_integer.html#_integerz37_10">02814</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitcount)
02815 {
02816 Randomize(rng, bitcount);
02817 }
02818
<a name="l02819"></a><a class="code" href="class_integer.html#_integerz37_11">02819</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &min, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &max, RandomNumberType rnType, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &equiv, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &mod)
02820 {
02821 <span class="keywordflow">if</span> (!Randomize(rng, min, max, rnType, equiv, mod))
02822 <span class="keywordflow">throw</span> Integer::RandomNumberNotFound();
02823 }
02824
<a name="l02825"></a><a class="code" href="class_integer.html#_integerz37_15">02825</a> <a class="code" href="class_integer.html">Integer</a> <a class="code" href="class_integer.html#_integerz37_15">Integer::Power2</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> e)
02826 {
02827 <a class="code" href="class_integer.html">Integer</a> r((word)0, BitsToWords(e+1));
02828 r.<a class="code" href="class_integer.html#_integerz43_15">SetBit</a>(e);
02829 <span class="keywordflow">return</span> r;
02830 }
02831
02832 <span class="keyword">template</span> <<span class="keywordtype">long</span> i>
02833 <span class="keyword">struct </span>NewInteger
02834 {
02835 <a class="code" href="class_integer.html">Integer</a> * operator()()<span class="keyword"> const</span>
02836 <span class="keyword"> </span>{
02837 <span class="keywordflow">return</span> <span class="keyword">new</span> <a class="code" href="class_integer.html">Integer</a>(i);
02838 }
02839 };
02840
<a name="l02841"></a><a class="code" href="class_integer.html#_integerz37_12">02841</a> <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &<a class="code" href="class_integer.html#_integerz37_12">Integer::Zero</a>()
02842 {
02843 <span class="keywordflow">return</span> <a class="code" href="class_singleton.html">Singleton<Integer></a>().Ref();
02844 }
02845
<a name="l02846"></a><a class="code" href="class_integer.html#_integerz37_13">02846</a> <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &<a class="code" href="class_integer.html#_integerz37_13">Integer::One</a>()
02847 {
02848 <span class="keywordflow">return</span> <a class="code" href="class_singleton.html">Singleton<Integer, NewInteger<1></a> >().Ref();
02849 }
02850
<a name="l02851"></a><a class="code" href="class_integer.html#_integerz37_14">02851</a> <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &<a class="code" href="class_integer.html#_integerz37_14">Integer::Two</a>()
02852 {
02853 <span class="keywordflow">return</span> <a class="code" href="class_singleton.html">Singleton<Integer, NewInteger<2></a> >().Ref();
02854 }
02855
02856 <span class="keywordtype">bool</span> Integer::operator!()<span class="keyword"> const</span>
02857 <span class="keyword"></span>{
02858 <span class="keywordflow">return</span> IsNegative() ? <span class="keyword">false</span> : (reg[0]==0 && <a class="code" href="class_integer.html#_integerz41_4">WordCount</a>()==0);
02859 }
02860
02861 <a class="code" href="class_integer.html">Integer</a>& Integer::operator=(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& t)
02862 {
02863 <span class="keywordflow">if</span> (<span class="keyword">this</span> != &t)
02864 {
02865 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta21">New</a>(RoundupSize(t.WordCount()));
02866 CopyWords(reg, t.reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
02867 sign = t.sign;
02868 }
02869 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
02870 }
02871
<a name="l02872"></a><a class="code" href="class_integer.html#_integerz41_5">02872</a> <span class="keywordtype">bool</span> <a class="code" href="class_integer.html#_integerz41_5">Integer::GetBit</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
02873 <span class="keyword"></span>{
02874 <span class="keywordflow">if</span> (n/WORD_BITS >= reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
02875 <span class="keywordflow">return</span> 0;
02876 <span class="keywordflow">else</span>
02877 <span class="keywordflow">return</span> bool((reg[n/WORD_BITS] >> (n % WORD_BITS)) & 1);
02878 }
02879
<a name="l02880"></a><a class="code" href="class_integer.html#_integerz43_15">02880</a> <span class="keywordtype">void</span> <a class="code" href="class_integer.html#_integerz43_15">Integer::SetBit</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n, <span class="keywordtype">bool</span> value)
02881 {
02882 <span class="keywordflow">if</span> (value)
02883 {
02884 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta24">CleanGrow</a>(RoundupSize(BitsToWords(n+1)));
02885 reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS));
02886 }
02887 <span class="keywordflow">else</span>
02888 {
02889 <span class="keywordflow">if</span> (n/WORD_BITS < reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
02890 reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS));
02891 }
02892 }
02893
<a name="l02894"></a><a class="code" href="class_integer.html#_integerz41_6">02894</a> byte <a class="code" href="class_integer.html#_integerz41_6">Integer::GetByte</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
02895 <span class="keyword"></span>{
02896 <span class="keywordflow">if</span> (n/WORD_SIZE >= reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
02897 <span class="keywordflow">return</span> 0;
02898 <span class="keywordflow">else</span>
02899 <span class="keywordflow">return</span> byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8));
02900 }
02901
<a name="l02902"></a><a class="code" href="class_integer.html#_integerz43_16">02902</a> <span class="keywordtype">void</span> <a class="code" href="class_integer.html#_integerz43_16">Integer::SetByte</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n, byte value)
02903 {
02904 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta24">CleanGrow</a>(RoundupSize(BytesToWords(n+1)));
02905 reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE));
02906 reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE));
02907 }
02908
<a name="l02909"></a><a class="code" href="class_integer.html#_integerz41_7">02909</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <a class="code" href="class_integer.html#_integerz41_7">Integer::GetBits</a>(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)<span class="keyword"> const</span>
02910 <span class="keyword"></span>{
02911 assert(n <= <span class="keyword">sizeof</span>(<span class="keywordtype">unsigned</span> <span class="keywordtype">long</span>)*8);
02912 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> v = 0;
02913 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0; j<n; j++)
02914 v |= <a class="code" href="class_integer.html#_integerz41_5">GetBit</a>(i+j) << j;
02915 <span class="keywordflow">return</span> v;
02916 }
02917
02918 <a class="code" href="class_integer.html">Integer</a> Integer::operator-()<span class="keyword"> const</span>
02919 <span class="keyword"></span>{
02920 <a class="code" href="class_integer.html">Integer</a> result(*<span class="keyword">this</span>);
02921 result.<a class="code" href="class_integer.html#_integerz43_17">Negate</a>();
02922 <span class="keywordflow">return</span> result;
02923 }
02924
02925 <a class="code" href="class_integer.html">Integer</a> Integer::AbsoluteValue()<span class="keyword"> const</span>
02926 <span class="keyword"></span>{
02927 <a class="code" href="class_integer.html">Integer</a> result(*<span class="keyword">this</span>);
02928 result.<a class="code" href="class_integer.html#_integerr1">sign</a> = POSITIVE;
02929 <span class="keywordflow">return</span> result;
02930 }
02931
02932 <span class="keywordtype">void</span> Integer::swap(<a class="code" href="class_integer.html">Integer</a> &a)
02933 {
02934 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta26">swap</a>(a.reg);
02935 std::swap(sign, a.sign);
02936 }
02937
02938 <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(word value, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)
02939 : reg(RoundupSize(length)), sign(POSITIVE)
02940 {
02941 reg[0] = value;
02942 SetWords(reg+1, 0, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()-1);
02943 }
02944
02945 <span class="keyword">template</span> <<span class="keyword">class</span> T>
02946 <span class="keyword">static</span> <a class="code" href="class_integer.html">Integer</a> StringToInteger(<span class="keyword">const</span> T *str)
02947 {
02948 word radix;
02949 <span class="comment">// GCC workaround</span>
02950 <span class="comment">// std::char_traits doesn't exist in GCC 2.x</span>
02951 <span class="comment">// std::char_traits<wchar_t>::length() not defined in GCC 3.2 and STLport 4.5.3</span>
02952 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length;
02953 <span class="keywordflow">for</span> (length = 0; str[length] != 0; length++) {}
02954
02955 <a class="code" href="class_integer.html">Integer</a> v;
02956
02957 <span class="keywordflow">if</span> (length == 0)
02958 <span class="keywordflow">return</span> v;
02959
02960 <span class="keywordflow">switch</span> (str[length-1])
02961 {
02962 <span class="keywordflow">case</span> <span class="charliteral">'h'</span>:
02963 <span class="keywordflow">case</span> <span class="charliteral">'H'</span>:
02964 radix=16;
02965 <span class="keywordflow">break</span>;
02966 <span class="keywordflow">case</span> <span class="charliteral">'o'</span>:
02967 <span class="keywordflow">case</span> <span class="charliteral">'O'</span>:
02968 radix=8;
02969 <span class="keywordflow">break</span>;
02970 <span class="keywordflow">case</span> <span class="charliteral">'b'</span>:
02971 <span class="keywordflow">case</span> <span class="charliteral">'B'</span>:
02972 radix=2;
02973 <span class="keywordflow">break</span>;
02974 <span class="keywordflow">default</span>:
02975 radix=10;
02976 }
02977
02978 <span class="keywordflow">if</span> (length > 2 && str[0] == <span class="charliteral">'0'</span> && str[1] == <span class="charliteral">'x'</span>)
02979 radix = 16;
02980
02981 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=0; i<length; i++)
02982 {
02983 word digit;
02984
02985 <span class="keywordflow">if</span> (str[i] >= <span class="charliteral">'0'</span> && str[i] <= <span class="charliteral">'9'</span>)
02986 digit = str[i] - <span class="charliteral">'0'</span>;
02987 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (str[i] >= <span class="charliteral">'A'</span> && str[i] <= <span class="charliteral">'F'</span>)
02988 digit = str[i] - <span class="charliteral">'A'</span> + 10;
02989 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (str[i] >= <span class="charliteral">'a'</span> && str[i] <= <span class="charliteral">'f'</span>)
02990 digit = str[i] - <span class="charliteral">'a'</span> + 10;
02991 <span class="keywordflow">else</span>
02992 digit = radix;
02993
02994 <span class="keywordflow">if</span> (digit < radix)
02995 {
02996 v *= radix;
02997 v += digit;
02998 }
02999 }
03000
03001 <span class="keywordflow">if</span> (str[0] == <span class="charliteral">'-'</span>)
03002 v.<a class="code" href="class_integer.html#_integerz43_17">Negate</a>();
03003
03004 <span class="keywordflow">return</span> v;
03005 }
03006
<a name="l03007"></a><a class="code" href="class_integer.html#_integerz37_5">03007</a> <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<span class="keyword">const</span> <span class="keywordtype">char</span> *str)
03008 : reg(2), sign(POSITIVE)
03009 {
03010 *<span class="keyword">this</span> = StringToInteger(str);
03011 }
03012
03013 <a class="code" href="class_integer.html#_integerz37_0">Integer::Integer</a>(<span class="keyword">const</span> <span class="keywordtype">wchar_t</span> *str)
03014 : reg(2), sign(POSITIVE)
03015 {
03016 *<span class="keyword">this</span> = StringToInteger(str);
03017 }
03018
<a name="l03019"></a><a class="code" href="class_integer.html#_integerz41_4">03019</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="class_integer.html#_integerz41_4">Integer::WordCount</a>()<span class="keyword"> const</span>
03020 <span class="keyword"></span>{
03021 <span class="keywordflow">return</span> CountWords(reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03022 }
03023
<a name="l03024"></a><a class="code" href="class_integer.html#_integerz41_3">03024</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="class_integer.html#_integerz41_3">Integer::ByteCount</a>()<span class="keyword"> const</span>
03025 <span class="keyword"></span>{
03026 <span class="keywordtype">unsigned</span> wordCount = <a class="code" href="class_integer.html#_integerz41_4">WordCount</a>();
03027 <span class="keywordflow">if</span> (wordCount)
03028 <span class="keywordflow">return</span> (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]);
03029 <span class="keywordflow">else</span>
03030 <span class="keywordflow">return</span> 0;
03031 }
03032
<a name="l03033"></a><a class="code" href="class_integer.html#_integerz41_2">03033</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="class_integer.html#_integerz41_2">Integer::BitCount</a>()<span class="keyword"> const</span>
03034 <span class="keyword"></span>{
03035 <span class="keywordtype">unsigned</span> wordCount = <a class="code" href="class_integer.html#_integerz41_4">WordCount</a>();
03036 <span class="keywordflow">if</span> (wordCount)
03037 <span class="keywordflow">return</span> (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]);
03038 <span class="keywordflow">else</span>
03039 <span class="keywordflow">return</span> 0;
03040 }
03041
03042 <span class="keywordtype">void</span> Integer::Decode(<span class="keyword">const</span> byte *input, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> inputLen, Signedness s)
03043 {
03044 <a class="code" href="class_string_store.html">StringStore</a> store(input, inputLen);
03045 Decode(store, inputLen, s);
03046 }
03047
03048 <span class="keywordtype">void</span> Integer::Decode(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> inputLen, Signedness s)
03049 {
03050 assert(bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_0">MaxRetrievable</a>() >= inputLen);
03051
03052 byte b;
03053 bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_4">Peek</a>(b);
03054 sign = ((s==SIGNED) && (b & 0x80)) ? NEGATIVE : POSITIVE;
03055
03056 <span class="keywordflow">while</span> (inputLen>0 && (sign==POSITIVE ? b==0 : b==0xff))
03057 {
03058 bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_11">Skip</a>(1);
03059 inputLen--;
03060 bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_4">Peek</a>(b);
03061 }
03062
03063 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta22">CleanNew</a>(RoundupSize(BytesToWords(inputLen)));
03064
03065 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=inputLen; i > 0; i--)
03066 {
03067 bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_2">Get</a>(b);
03068 reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8;
03069 }
03070
03071 <span class="keywordflow">if</span> (sign == NEGATIVE)
03072 {
03073 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=inputLen; i<reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()*WORD_SIZE; i++)
03074 reg[i/WORD_SIZE] |= word(0xff) << (i%WORD_SIZE)*8;
03075 TwosComplement(reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03076 }
03077 }
03078
<a name="l03079"></a><a class="code" href="class_integer.html#_integerz39_0">03079</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="class_integer.html#_integerz39_0">Integer::MinEncodedSize</a>(Signedness signedness)<span class="keyword"> const</span>
03080 <span class="keyword"></span>{
03081 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> outputLen = STDMAX(1U, <a class="code" href="class_integer.html#_integerz41_3">ByteCount</a>());
03082 <span class="keywordflow">if</span> (signedness == UNSIGNED)
03083 <span class="keywordflow">return</span> outputLen;
03084 <span class="keywordflow">if</span> (NotNegative() && (<a class="code" href="class_integer.html#_integerz41_6">GetByte</a>(outputLen-1) & 0x80))
03085 outputLen++;
03086 <span class="keywordflow">if</span> (IsNegative() && *<span class="keyword">this</span> < -<a class="code" href="class_integer.html#_integerz37_15">Power2</a>(outputLen*8-1))
03087 outputLen++;
03088 <span class="keywordflow">return</span> outputLen;
03089 }
03090
<a name="l03091"></a><a class="code" href="class_integer.html#_integerz39_1">03091</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="class_integer.html#_integerz39_1">Integer::Encode</a>(byte *output, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> outputLen, Signedness signedness)<span class="keyword"> const</span>
03092 <span class="keyword"></span>{
03093 <a class="code" href="class_array_sink.html">ArraySink</a> sink(output, outputLen);
03094 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz39_1">Encode</a>(sink, outputLen, signedness);
03095 }
03096
03097 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> Integer::Encode(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> outputLen, Signedness signedness)<span class="keyword"> const</span>
03098 <span class="keyword"></span>{
03099 <span class="keywordflow">if</span> (signedness == UNSIGNED || NotNegative())
03100 {
03101 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=outputLen; i > 0; i--)
03102 bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz1_0">Put</a>(GetByte(i-1));
03103 }
03104 <span class="keywordflow">else</span>
03105 {
03106 <span class="comment">// take two's complement of *this</span>
03107 <a class="code" href="class_integer.html">Integer</a> temp = <a class="code" href="class_integer.html#_integerz37_15">Integer::Power2</a>(8*STDMAX(<a class="code" href="class_integer.html#_integerz41_3">ByteCount</a>(), outputLen)) + *<span class="keyword">this</span>;
03108 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=0; i<outputLen; i++)
03109 bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz1_0">Put</a>(temp.<a class="code" href="class_integer.html#_integerz41_6">GetByte</a>(outputLen-i-1));
03110 }
03111 <span class="keywordflow">return</span> outputLen;
03112 }
03113
<a name="l03114"></a><a class="code" href="class_integer.html#_integerz39_3">03114</a> <span class="keywordtype">void</span> <a class="code" href="class_integer.html#_integerz39_3">Integer::DEREncode</a>(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt)<span class="keyword"> const</span>
03115 <span class="keyword"></span>{
03116 <a class="code" href="class_d_e_r_general_encoder.html">DERGeneralEncoder</a> enc(bt, INTEGER);
03117 <a class="code" href="class_integer.html#_integerz39_1">Encode</a>(enc, <a class="code" href="class_integer.html#_integerz39_0">MinEncodedSize</a>(SIGNED), SIGNED);
03118 enc.<a class="code" href="class_d_e_r_general_encoder.html#_d_e_r_set_encodera2">MessageEnd</a>();
03119 }
03120
03121 <span class="keywordtype">void</span> Integer::BERDecode(<span class="keyword">const</span> byte *input, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> len)
03122 {
03123 <a class="code" href="class_string_store.html">StringStore</a> store(input, len);
03124 BERDecode(store);
03125 }
03126
<a name="l03127"></a><a class="code" href="class_integer.html#_integerz39_10">03127</a> <span class="keywordtype">void</span> Integer::BERDecode(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt)
03128 {
03129 <a class="code" href="class_b_e_r_general_decoder.html">BERGeneralDecoder</a> dec(bt, INTEGER);
03130 <span class="keywordflow">if</span> (!dec.<a class="code" href="class_b_e_r_general_decoder.html#_b_e_r_set_decodera2">IsDefiniteLength</a>() || dec.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_0">MaxRetrievable</a>() < dec.<a class="code" href="class_b_e_r_general_decoder.html#_b_e_r_set_decodera3">RemainingLength</a>())
03131 BERDecodeError();
03132 Decode(dec, dec.<a class="code" href="class_b_e_r_general_decoder.html#_b_e_r_set_decodera3">RemainingLength</a>(), SIGNED);
03133 dec.<a class="code" href="class_b_e_r_general_decoder.html#_b_e_r_set_decodera9">MessageEnd</a>();
03134 }
03135
<a name="l03136"></a><a class="code" href="class_integer.html#_integerz39_4">03136</a> <span class="keywordtype">void</span> <a class="code" href="class_integer.html#_integerz39_4">Integer::DEREncodeAsOctetString</a>(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)<span class="keyword"> const</span>
03137 <span class="keyword"></span>{
03138 <a class="code" href="class_d_e_r_general_encoder.html">DERGeneralEncoder</a> enc(bt, OCTET_STRING);
03139 <a class="code" href="class_integer.html#_integerz39_1">Encode</a>(enc, length);
03140 enc.<a class="code" href="class_d_e_r_general_encoder.html#_d_e_r_set_encodera2">MessageEnd</a>();
03141 }
03142
<a name="l03143"></a><a class="code" href="class_integer.html#_integerz39_11">03143</a> <span class="keywordtype">void</span> <a class="code" href="class_integer.html#_integerz39_11">Integer::BERDecodeAsOctetString</a>(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length)
03144 {
03145 <a class="code" href="class_b_e_r_general_decoder.html">BERGeneralDecoder</a> dec(bt, OCTET_STRING);
03146 <span class="keywordflow">if</span> (!dec.<a class="code" href="class_b_e_r_general_decoder.html#_b_e_r_set_decodera2">IsDefiniteLength</a>() || dec.<a class="code" href="class_b_e_r_general_decoder.html#_b_e_r_set_decodera3">RemainingLength</a>() != length)
03147 BERDecodeError();
03148 Decode(dec, length);
03149 dec.<a class="code" href="class_b_e_r_general_decoder.html#_b_e_r_set_decodera9">MessageEnd</a>();
03150 }
03151
<a name="l03152"></a><a class="code" href="class_integer.html#_integerz39_5">03152</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="class_integer.html#_integerz39_5">Integer::OpenPGPEncode</a>(byte *output, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> len)<span class="keyword"> const</span>
03153 <span class="keyword"></span>{
03154 <a class="code" href="class_array_sink.html">ArraySink</a> sink(output, len);
03155 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz39_5">OpenPGPEncode</a>(sink);
03156 }
03157
<a name="l03158"></a><a class="code" href="class_integer.html#_integerz39_6">03158</a> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> <a class="code" href="class_integer.html#_integerz39_5">Integer::OpenPGPEncode</a>(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt)<span class="keyword"> const</span>
03159 <span class="keyword"></span>{
03160 word16 bitCount = <a class="code" href="class_integer.html#_integerz41_2">BitCount</a>();
03161 bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz1_2">PutWord16</a>(bitCount);
03162 <span class="keywordflow">return</span> 2 + <a class="code" href="class_integer.html#_integerz39_1">Encode</a>(bt, BitsToBytes(bitCount));
03163 }
03164
03165 <span class="keywordtype">void</span> Integer::OpenPGPDecode(<span class="keyword">const</span> byte *input, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> len)
03166 {
03167 <a class="code" href="class_string_store.html">StringStore</a> store(input, len);
03168 OpenPGPDecode(store);
03169 }
03170
03171 <span class="keywordtype">void</span> Integer::OpenPGPDecode(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt)
03172 {
03173 word16 bitCount;
03174 <span class="keywordflow">if</span> (bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_6">GetWord16</a>(bitCount) != 2 || bt.<a class="code" href="class_buffered_transformation.html#_zlib_decompressorz7_0">MaxRetrievable</a>() < BitsToBytes(bitCount))
03175 <span class="keywordflow">throw</span> OpenPGPDecodeErr();
03176 Decode(bt, BitsToBytes(bitCount));
03177 }
03178
03179 <span class="keywordtype">void</span> Integer::Randomize(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nbits)
03180 {
03181 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nbytes = nbits/8 + 1;
03182 <a class="code" href="class_sec_block.html">SecByteBlock</a> buf(nbytes);
03183 rng.<a class="code" href="class_random_number_generator.html#_x917_r_n_ga4">GenerateBlock</a>(buf, nbytes);
03184 <span class="keywordflow">if</span> (nbytes)
03185 buf[0] = (byte)Crop(buf[0], nbits % 8);
03186 Decode(buf, nbytes, UNSIGNED);
03187 }
03188
03189 <span class="keywordtype">void</span> Integer::Randomize(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &min, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &max)
03190 {
03191 <span class="keywordflow">if</span> (min > max)
03192 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"Integer: Min must be no greater than Max"</span>);
03193
03194 <a class="code" href="class_integer.html">Integer</a> range = max - min;
03195 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> nbits = range.<a class="code" href="class_integer.html#_integerz41_2">BitCount</a>();
03196
03197 <span class="keywordflow">do</span>
03198 {
03199 Randomize(rng, nbits);
03200 }
03201 <span class="keywordflow">while</span> (*<span class="keyword">this</span> > range);
03202
03203 *<span class="keyword">this</span> += min;
03204 }
03205
<a name="l03206"></a><a class="code" href="class_integer.html#_integerz43_12">03206</a> <span class="keywordtype">bool</span> Integer::Randomize(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &min, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &max, RandomNumberType rnType, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &equiv, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &mod)
03207 {
03208 <span class="keywordflow">return</span> GenerateRandomNoThrow(rng, MakeParameters(<span class="stringliteral">"Min"</span>, min)(<span class="stringliteral">"Max"</span>, max)(<span class="stringliteral">"RandomNumberType"</span>, rnType)(<span class="stringliteral">"EquivalentTo"</span>, equiv)(<span class="stringliteral">"Mod"</span>, mod));
03209 }
03210
03211 <span class="keyword">class </span>KDF2_RNG : <span class="keyword">public</span> <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a>
03212 {
03213 <span class="keyword">public</span>:
03214 KDF2_RNG(<span class="keyword">const</span> byte *seed, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> seedSize)
03215 : m_counter(0), m_counterAndSeed(seedSize + 4)
03216 {
03217 memcpy(m_counterAndSeed + 4, seed, seedSize);
03218 }
03219
03220 byte <a class="code" href="class_random_number_generator.html#_random_number_generatora0">GenerateByte</a>()
03221 {
03222 byte b;
03223 GenerateBlock(&b, 1);
03224 <span class="keywordflow">return</span> b;
03225 }
03226
03227 <span class="keywordtype">void</span> GenerateBlock(byte *output, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> size)
03228 {
03229 UnalignedPutWord(BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter);
03230 ++m_counter;
03231 <a class="code" href="class_p1363___k_d_f2.html">P1363_KDF2<SHA1>::DeriveKey</a>(output, size, m_counterAndSeed, m_counterAndSeed.size(), NULL, 0);
03232 }
03233
03234 <span class="keyword">private</span>:
03235 word32 m_counter;
03236 <a class="code" href="class_sec_block.html">SecByteBlock</a> m_counterAndSeed;
03237 };
03238
03239 <span class="keywordtype">bool</span> Integer::GenerateRandomNoThrow(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &i_rng, <span class="keyword">const</span> <a class="code" href="class_name_value_pairs.html">NameValuePairs</a> &params)
03240 {
03241 <a class="code" href="class_integer.html">Integer</a> min = params.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha40">GetValueWithDefault</a>(<span class="stringliteral">"Min"</span>, Integer::Zero());
03242 <a class="code" href="class_integer.html">Integer</a> max;
03243 <span class="keywordflow">if</span> (!params.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha39">GetValue</a>(<span class="stringliteral">"Max"</span>, max))
03244 {
03245 <span class="keywordtype">int</span> bitLength;
03246 <span class="keywordflow">if</span> (params.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha42">GetIntValue</a>(<span class="stringliteral">"BitLength"</span>, bitLength))
03247 max = <a class="code" href="class_integer.html#_integerz37_15">Integer::Power2</a>(bitLength);
03248 <span class="keywordflow">else</span>
03249 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"Integer: missing Max argument"</span>);
03250 }
03251 <span class="keywordflow">if</span> (min > max)
03252 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"Integer: Min must be no greater than Max"</span>);
03253
03254 <a class="code" href="class_integer.html">Integer</a> equiv = params.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha40">GetValueWithDefault</a>(<span class="stringliteral">"EquivalentTo"</span>, Integer::Zero());
03255 <a class="code" href="class_integer.html">Integer</a> mod = params.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha40">GetValueWithDefault</a>(<span class="stringliteral">"Mod"</span>, Integer::One());
03256
03257 <span class="keywordflow">if</span> (equiv.<a class="code" href="class_integer.html#_integerz41_10">IsNegative</a>() || equiv >= mod)
03258 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"Integer: invalid EquivalentTo and/or Mod argument"</span>);
03259
03260 Integer::RandomNumberType rnType = params.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha40">GetValueWithDefault</a>(<span class="stringliteral">"RandomNumberType"</span>, Integer::ANY);
03261
03262 member_ptr<KDF2_RNG> kdf2Rng;
03263 <a class="code" href="class_const_byte_array_parameter.html">ConstByteArrayParameter</a> seed;
03264 <span class="keywordflow">if</span> (params.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha39">GetValue</a>(<span class="stringliteral">"Seed"</span>, seed))
03265 {
03266 <a class="code" href="class_byte_queue.html">ByteQueue</a> bq;
03267 <a class="code" href="class_d_e_r_sequence_encoder.html">DERSequenceEncoder</a> seq(bq);
03268 min.<a class="code" href="class_integer.html#_integerz39_3">DEREncode</a>(seq);
03269 max.<a class="code" href="class_integer.html#_integerz39_3">DEREncode</a>(seq);
03270 equiv.<a class="code" href="class_integer.html#_integerz39_3">DEREncode</a>(seq);
03271 mod.<a class="code" href="class_integer.html#_integerz39_3">DEREncode</a>(seq);
03272 DEREncodeUnsigned(seq, rnType);
03273 DEREncodeOctetString(seq, seed.<a class="code" href="class_const_byte_array_parameter.html#_const_byte_array_parametera4">begin</a>(), seed.<a class="code" href="class_const_byte_array_parameter.html#_const_byte_array_parametera6">size</a>());
03274 seq.<a class="code" href="class_d_e_r_general_encoder.html#_d_e_r_set_encodera2">MessageEnd</a>();
03275
03276 <a class="code" href="class_sec_block.html">SecByteBlock</a> finalSeed(bq.<a class="code" href="class_byte_queue.html#_d_e_r_set_encodera3">MaxRetrievable</a>());
03277 bq.<a class="code" href="class_byte_queue.html#_d_e_r_set_encodera8">Get</a>(finalSeed, finalSeed.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03278 kdf2Rng.reset(<span class="keyword">new</span> KDF2_RNG(finalSeed.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>(), finalSeed.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()));
03279 }
03280 <a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng = kdf2Rng.get() ? (<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &)*kdf2Rng : i_rng;
03281
03282 <span class="keywordflow">switch</span> (rnType)
03283 {
03284 <span class="keywordflow">case</span> ANY:
03285 <span class="keywordflow">if</span> (mod == <a class="code" href="class_integer.html#_integerz37_13">One</a>())
03286 Randomize(rng, min, max);
03287 <span class="keywordflow">else</span>
03288 {
03289 <a class="code" href="class_integer.html">Integer</a> min1 = min + (equiv-min)%mod;
03290 <span class="keywordflow">if</span> (max < min1)
03291 <span class="keywordflow">return</span> <span class="keyword">false</span>;
03292 Randomize(rng, <a class="code" href="class_integer.html#_integerz37_12">Zero</a>(), (max - min1) / mod);
03293 *<span class="keyword">this</span> *= mod;
03294 *<span class="keyword">this</span> += min1;
03295 }
03296 <span class="keywordflow">return</span> <span class="keyword">true</span>;
03297
03298 <span class="keywordflow">case</span> PRIME:
03299 {
03300 <span class="keyword">const</span> PrimeSelector *pSelector = params.<a class="code" href="class_name_value_pairs.html#_x_t_r___d_ha40">GetValueWithDefault</a>(Name::PointerToPrimeSelector(), (<span class="keyword">const</span> PrimeSelector *)NULL);
03301
03302 <span class="keywordtype">int</span> i;
03303 i = 0;
03304 <span class="keywordflow">while</span> (1)
03305 {
03306 <span class="keywordflow">if</span> (++i==16)
03307 {
03308 <span class="comment">// check if there are any suitable primes in [min, max]</span>
03309 <a class="code" href="class_integer.html">Integer</a> first = min;
03310 <span class="keywordflow">if</span> (FirstPrime(first, max, equiv, mod, pSelector))
03311 {
03312 <span class="comment">// if there is only one suitable prime, we're done</span>
03313 *<span class="keyword">this</span> = first;
03314 <span class="keywordflow">if</span> (!FirstPrime(first, max, equiv, mod, pSelector))
03315 <span class="keywordflow">return</span> <span class="keyword">true</span>;
03316 }
03317 <span class="keywordflow">else</span>
03318 <span class="keywordflow">return</span> <span class="keyword">false</span>;
03319 }
03320
03321 Randomize(rng, min, max);
03322 <span class="keywordflow">if</span> (FirstPrime(*<span class="keyword">this</span>, STDMIN(*<span class="keyword">this</span>+mod*PrimeSearchInterval(max), max), equiv, mod, pSelector))
03323 <span class="keywordflow">return</span> <span class="keyword">true</span>;
03324 }
03325 }
03326
03327 <span class="keywordflow">default</span>:
03328 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"Integer: invalid RandomNumberType argument"</span>);
03329 }
03330 }
03331
03332 std::istream& operator>>(std::istream& in, <a class="code" href="class_integer.html">Integer</a> &a)
03333 {
03334 <span class="keywordtype">char</span> c;
03335 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> length = 0;
03336 <a class="code" href="class_sec_block.html">SecBlock<char></a> str(length + 16);
03337
03338 std::ws(in);
03339
03340 <span class="keywordflow">do</span>
03341 {
03342 in.read(&c, 1);
03343 str[length++] = c;
03344 <span class="keywordflow">if</span> (length >= str.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
03345 str.<a class="code" href="class_sec_block.html#_sec_block_with_hinta23">Grow</a>(length + 16);
03346 }
03347 <span class="keywordflow">while</span> (in && (c==<span class="charliteral">'-'</span> || c==<span class="charliteral">'x'</span> || (c>=<span class="charliteral">'0'</span> && c<='9') || (c>=<span class="charliteral">'a'</span> && c<='f') || (c>=<span class="charliteral">'A'</span> && c<=<span class="charliteral">'F'</span>) || c==<span class="charliteral">'h'</span> || c==<span class="charliteral">'H'</span> || c==<span class="charliteral">'o'</span> || c==<span class="charliteral">'O'</span> || c==<span class="charliteral">','</span> || c==<span class="charliteral">'.'</span>));
03348
03349 <span class="keywordflow">if</span> (in.gcount())
03350 in.putback(c);
03351 str[length-1] = <span class="charliteral">'\0'</span>;
03352 a = <a class="code" href="class_integer.html">Integer</a>(str);
03353
03354 <span class="keywordflow">return</span> in;
03355 }
03356
03357 std::ostream& operator<<(std::ostream& out, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a)
03358 {
03359 <span class="comment">// Get relevant conversion specifications from ostream.</span>
03360 <span class="keywordtype">long</span> f = out.flags() & std::ios::basefield; <span class="comment">// Get base digits.</span>
03361 <span class="keywordtype">int</span> base, block;
03362 <span class="keywordtype">char</span> suffix;
03363 <span class="keywordflow">switch</span>(f)
03364 {
03365 <span class="keywordflow">case</span> std::ios::oct :
03366 base = 8;
03367 block = 8;
03368 suffix = <span class="charliteral">'o'</span>;
03369 <span class="keywordflow">break</span>;
03370 <span class="keywordflow">case</span> std::ios::hex :
03371 base = 16;
03372 block = 4;
03373 suffix = <span class="charliteral">'h'</span>;
03374 <span class="keywordflow">break</span>;
03375 <span class="keywordflow">default</span> :
03376 base = 10;
03377 block = 3;
03378 suffix = <span class="charliteral">'.'</span>;
03379 }
03380
03381 <a class="code" href="class_sec_block.html">SecBlock<char></a> s(a.BitCount() / (BitPrecision(base)-1) + 1);
03382 <a class="code" href="class_integer.html">Integer</a> temp1=a, temp2;
03383 <span class="keywordtype">unsigned</span> i=0;
03384 <span class="keyword">const</span> <span class="keywordtype">char</span> vec[]=<span class="stringliteral">"0123456789ABCDEF"</span>;
03385
03386 <span class="keywordflow">if</span> (a.IsNegative())
03387 {
03388 out << <span class="charliteral">'-'</span>;
03389 temp1.<a class="code" href="class_integer.html#_integerz43_17">Negate</a>();
03390 }
03391
03392 <span class="keywordflow">if</span> (!a)
03393 out << <span class="charliteral">'0'</span>;
03394
03395 <span class="keywordflow">while</span> (!!temp1)
03396 {
03397 word digit;
03398 <a class="code" href="class_integer.html#_integerz49_9">Integer::Divide</a>(digit, temp2, temp1, base);
03399 s[i++]=vec[digit];
03400 temp1=temp2;
03401 }
03402
03403 <span class="keywordflow">while</span> (i--)
03404 {
03405 out << s[i];
03406 <span class="comment">// if (i && !(i%block))</span>
03407 <span class="comment">// out << ",";</span>
03408 }
03409 <span class="keywordflow">return</span> out << suffix;
03410 }
03411
03412 <a class="code" href="class_integer.html">Integer</a>& Integer::operator++()
03413 {
03414 <span class="keywordflow">if</span> (NotNegative())
03415 {
03416 <span class="keywordflow">if</span> (Increment(reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()))
03417 {
03418 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta24">CleanGrow</a>(2*reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03419 reg[reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()/2]=1;
03420 }
03421 }
03422 <span class="keywordflow">else</span>
03423 {
03424 word borrow = Decrement(reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03425 assert(!borrow);
03426 <span class="keywordflow">if</span> (<a class="code" href="class_integer.html#_integerz41_4">WordCount</a>()==0)
03427 *<span class="keyword">this</span> = <a class="code" href="class_integer.html#_integerz37_12">Zero</a>();
03428 }
03429 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
03430 }
03431
03432 <a class="code" href="class_integer.html">Integer</a>& Integer::operator--()
03433 {
03434 <span class="keywordflow">if</span> (IsNegative())
03435 {
03436 <span class="keywordflow">if</span> (Increment(reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()))
03437 {
03438 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta24">CleanGrow</a>(2*reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03439 reg[reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()/2]=1;
03440 }
03441 }
03442 <span class="keywordflow">else</span>
03443 {
03444 <span class="keywordflow">if</span> (Decrement(reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()))
03445 *<span class="keyword">this</span> = -<a class="code" href="class_integer.html#_integerz37_13">One</a>();
03446 }
03447 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
03448 }
03449
03450 <span class="keywordtype">void</span> PositiveAdd(<a class="code" href="class_integer.html">Integer</a> &sum, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& b)
03451 {
03452 word carry;
03453 <span class="keywordflow">if</span> (a.reg.size() == b.reg.size())
03454 carry = Add(sum.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg, b.reg, a.reg.size());
03455 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (a.reg.size() > b.reg.size())
03456 {
03457 carry = Add(sum.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg, b.reg, b.reg.size());
03458 CopyWords(sum.<a class="code" href="class_integer.html#_integerr0">reg</a>+b.reg.size(), a.reg+b.reg.size(), a.reg.size()-b.reg.size());
03459 carry = Increment(sum.<a class="code" href="class_integer.html#_integerr0">reg</a>+b.reg.size(), a.reg.size()-b.reg.size(), carry);
03460 }
03461 <span class="keywordflow">else</span>
03462 {
03463 carry = Add(sum.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg, b.reg, a.reg.size());
03464 CopyWords(sum.<a class="code" href="class_integer.html#_integerr0">reg</a>+a.reg.size(), b.reg+a.reg.size(), b.reg.size()-a.reg.size());
03465 carry = Increment(sum.<a class="code" href="class_integer.html#_integerr0">reg</a>+a.reg.size(), b.reg.size()-a.reg.size(), carry);
03466 }
03467
03468 <span class="keywordflow">if</span> (carry)
03469 {
03470 sum.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta24">CleanGrow</a>(2*sum.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03471 sum.<a class="code" href="class_integer.html#_integerr0">reg</a>[sum.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()/2] = 1;
03472 }
03473 sum.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::POSITIVE;
03474 }
03475
03476 <span class="keywordtype">void</span> PositiveSubtract(<a class="code" href="class_integer.html">Integer</a> &diff, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& b)
03477 {
03478 <span class="keywordtype">unsigned</span> aSize = a.WordCount();
03479 aSize += aSize%2;
03480 <span class="keywordtype">unsigned</span> bSize = b.WordCount();
03481 bSize += bSize%2;
03482
03483 <span class="keywordflow">if</span> (aSize == bSize)
03484 {
03485 <span class="keywordflow">if</span> (Compare(a.reg, b.reg, aSize) >= 0)
03486 {
03487 Subtract(diff.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg, b.reg, aSize);
03488 diff.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::POSITIVE;
03489 }
03490 <span class="keywordflow">else</span>
03491 {
03492 Subtract(diff.<a class="code" href="class_integer.html#_integerr0">reg</a>, b.reg, a.reg, aSize);
03493 diff.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::NEGATIVE;
03494 }
03495 }
03496 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (aSize > bSize)
03497 {
03498 word borrow = Subtract(diff.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg, b.reg, bSize);
03499 CopyWords(diff.<a class="code" href="class_integer.html#_integerr0">reg</a>+bSize, a.reg+bSize, aSize-bSize);
03500 borrow = Decrement(diff.<a class="code" href="class_integer.html#_integerr0">reg</a>+bSize, aSize-bSize, borrow);
03501 assert(!borrow);
03502 diff.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::POSITIVE;
03503 }
03504 <span class="keywordflow">else</span>
03505 {
03506 word borrow = Subtract(diff.<a class="code" href="class_integer.html#_integerr0">reg</a>, b.reg, a.reg, aSize);
03507 CopyWords(diff.<a class="code" href="class_integer.html#_integerr0">reg</a>+aSize, b.reg+aSize, bSize-aSize);
03508 borrow = Decrement(diff.<a class="code" href="class_integer.html#_integerr0">reg</a>+aSize, bSize-aSize, borrow);
03509 assert(!borrow);
03510 diff.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::NEGATIVE;
03511 }
03512 }
03513
03514 <a class="code" href="class_integer.html">Integer</a> Integer::Plus(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& b)<span class="keyword"> const</span>
03515 <span class="keyword"></span>{
03516 <a class="code" href="class_integer.html">Integer</a> sum((word)0, STDMAX(reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>(), b.reg.size()));
03517 <span class="keywordflow">if</span> (NotNegative())
03518 {
03519 <span class="keywordflow">if</span> (b.NotNegative())
03520 PositiveAdd(sum, *<span class="keyword">this</span>, b);
03521 <span class="keywordflow">else</span>
03522 PositiveSubtract(sum, *<span class="keyword">this</span>, b);
03523 }
03524 <span class="keywordflow">else</span>
03525 {
03526 <span class="keywordflow">if</span> (b.NotNegative())
03527 PositiveSubtract(sum, b, *<span class="keyword">this</span>);
03528 <span class="keywordflow">else</span>
03529 {
03530 PositiveAdd(sum, *<span class="keyword">this</span>, b);
03531 sum.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::NEGATIVE;
03532 }
03533 }
03534 <span class="keywordflow">return</span> sum;
03535 }
03536
03537 <a class="code" href="class_integer.html">Integer</a>& Integer::operator+=(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& t)
03538 {
03539 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta24">CleanGrow</a>(t.reg.size());
03540 <span class="keywordflow">if</span> (NotNegative())
03541 {
03542 <span class="keywordflow">if</span> (t.NotNegative())
03543 PositiveAdd(*<span class="keyword">this</span>, *<span class="keyword">this</span>, t);
03544 <span class="keywordflow">else</span>
03545 PositiveSubtract(*<span class="keyword">this</span>, *<span class="keyword">this</span>, t);
03546 }
03547 <span class="keywordflow">else</span>
03548 {
03549 <span class="keywordflow">if</span> (t.NotNegative())
03550 PositiveSubtract(*<span class="keyword">this</span>, t, *<span class="keyword">this</span>);
03551 <span class="keywordflow">else</span>
03552 {
03553 PositiveAdd(*<span class="keyword">this</span>, *<span class="keyword">this</span>, t);
03554 sign = Integer::NEGATIVE;
03555 }
03556 }
03557 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
03558 }
03559
03560 <a class="code" href="class_integer.html">Integer</a> Integer::Minus(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& b)<span class="keyword"> const</span>
03561 <span class="keyword"></span>{
03562 <a class="code" href="class_integer.html">Integer</a> diff((word)0, STDMAX(reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>(), b.reg.size()));
03563 <span class="keywordflow">if</span> (NotNegative())
03564 {
03565 <span class="keywordflow">if</span> (b.NotNegative())
03566 PositiveSubtract(diff, *<span class="keyword">this</span>, b);
03567 <span class="keywordflow">else</span>
03568 PositiveAdd(diff, *<span class="keyword">this</span>, b);
03569 }
03570 <span class="keywordflow">else</span>
03571 {
03572 <span class="keywordflow">if</span> (b.NotNegative())
03573 {
03574 PositiveAdd(diff, *<span class="keyword">this</span>, b);
03575 diff.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::NEGATIVE;
03576 }
03577 <span class="keywordflow">else</span>
03578 PositiveSubtract(diff, b, *<span class="keyword">this</span>);
03579 }
03580 <span class="keywordflow">return</span> diff;
03581 }
03582
03583 <a class="code" href="class_integer.html">Integer</a>& Integer::operator-=(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& t)
03584 {
03585 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta24">CleanGrow</a>(t.reg.size());
03586 <span class="keywordflow">if</span> (NotNegative())
03587 {
03588 <span class="keywordflow">if</span> (t.NotNegative())
03589 PositiveSubtract(*<span class="keyword">this</span>, *<span class="keyword">this</span>, t);
03590 <span class="keywordflow">else</span>
03591 PositiveAdd(*<span class="keyword">this</span>, *<span class="keyword">this</span>, t);
03592 }
03593 <span class="keywordflow">else</span>
03594 {
03595 <span class="keywordflow">if</span> (t.NotNegative())
03596 {
03597 PositiveAdd(*<span class="keyword">this</span>, *<span class="keyword">this</span>, t);
03598 sign = Integer::NEGATIVE;
03599 }
03600 <span class="keywordflow">else</span>
03601 PositiveSubtract(*<span class="keyword">this</span>, t, *<span class="keyword">this</span>);
03602 }
03603 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
03604 }
03605
03606 <a class="code" href="class_integer.html">Integer</a>& Integer::operator<<=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
03607 {
03608 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> wordCount = <a class="code" href="class_integer.html#_integerz41_4">WordCount</a>();
03609 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> shiftWords = n / WORD_BITS;
03610 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> shiftBits = n % WORD_BITS;
03611
03612 reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta24">CleanGrow</a>(RoundupSize(wordCount+BitsToWords(n)));
03613 ShiftWordsLeftByWords(reg, wordCount + shiftWords, shiftWords);
03614 ShiftWordsLeftByBits(reg+shiftWords, wordCount+BitsToWords(shiftBits), shiftBits);
03615 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
03616 }
03617
03618 <a class="code" href="class_integer.html">Integer</a>& Integer::operator>>=(<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
03619 {
03620 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> wordCount = <a class="code" href="class_integer.html#_integerz41_4">WordCount</a>();
03621 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> shiftWords = n / WORD_BITS;
03622 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> shiftBits = n % WORD_BITS;
03623
03624 ShiftWordsRightByWords(reg, wordCount, shiftWords);
03625 <span class="keywordflow">if</span> (wordCount > shiftWords)
03626 ShiftWordsRightByBits(reg, wordCount-shiftWords, shiftBits);
03627 <span class="keywordflow">if</span> (IsNegative() && <a class="code" href="class_integer.html#_integerz41_4">WordCount</a>()==0) <span class="comment">// avoid -0</span>
03628 *<span class="keyword">this</span> = <a class="code" href="class_integer.html#_integerz37_12">Zero</a>();
03629 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
03630 }
03631
03632 <span class="keywordtype">void</span> PositiveMultiply(<a class="code" href="class_integer.html">Integer</a> &product, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)
03633 {
03634 <span class="keywordtype">unsigned</span> aSize = RoundupSize(a.WordCount());
03635 <span class="keywordtype">unsigned</span> bSize = RoundupSize(b.WordCount());
03636
03637 product.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta22">CleanNew</a>(RoundupSize(aSize+bSize));
03638 product.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::POSITIVE;
03639
03640 <a class="code" href="class_sec_block.html">SecAlignedWordBlock</a> workspace(aSize + bSize);
03641 AsymmetricMultiply(product.<a class="code" href="class_integer.html#_integerr0">reg</a>, workspace, a.reg, aSize, b.reg, bSize);
03642 }
03643
03644 <span class="keywordtype">void</span> Multiply(<a class="code" href="class_integer.html">Integer</a> &product, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)
03645 {
03646 PositiveMultiply(product, a, b);
03647
03648 <span class="keywordflow">if</span> (a.NotNegative() != b.NotNegative())
03649 product.<a class="code" href="class_integer.html#_integerz43_17">Negate</a>();
03650 }
03651
03652 <a class="code" href="class_integer.html">Integer</a> Integer::Times(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)<span class="keyword"> const</span>
03653 <span class="keyword"></span>{
03654 <a class="code" href="class_integer.html">Integer</a> product;
03655 Multiply(product, *<span class="keyword">this</span>, b);
03656 <span class="keywordflow">return</span> product;
03657 }
03658
03659 <span class="comment">/*</span>
03660 <span class="comment">void PositiveDivide(Integer &remainder, Integer &quotient,</span>
03661 <span class="comment"> const Integer &dividend, const Integer &divisor)</span>
03662 <span class="comment">{</span>
03663 <span class="comment"> remainder.reg.CleanNew(divisor.reg.size());</span>
03664 <span class="comment"> remainder.sign = Integer::POSITIVE;</span>
03665 <span class="comment"> quotient.reg.New(0);</span>
03666 <span class="comment"> quotient.sign = Integer::POSITIVE;</span>
03667 <span class="comment"> unsigned i=dividend.BitCount();</span>
03668 <span class="comment"> while (i--)</span>
03669 <span class="comment"> {</span>
03670 <span class="comment"> word overflow = ShiftWordsLeftByBits(remainder.reg, remainder.reg.size(), 1);</span>
03671 <span class="comment"> remainder.reg[0] |= dividend[i];</span>
03672 <span class="comment"> if (overflow || remainder >= divisor)</span>
03673 <span class="comment"> {</span>
03674 <span class="comment"> Subtract(remainder.reg, remainder.reg, divisor.reg, remainder.reg.size());</span>
03675 <span class="comment"> quotient.SetBit(i);</span>
03676 <span class="comment"> }</span>
03677 <span class="comment"> }</span>
03678 <span class="comment">}</span>
03679 <span class="comment">*/</span>
03680
03681 <span class="keywordtype">void</span> PositiveDivide(<a class="code" href="class_integer.html">Integer</a> &remainder, <a class="code" href="class_integer.html">Integer</a> &quotient,
03682 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)
03683 {
03684 <span class="keywordtype">unsigned</span> aSize = a.WordCount();
03685 <span class="keywordtype">unsigned</span> bSize = b.WordCount();
03686
03687 <span class="keywordflow">if</span> (!bSize)
03688 <span class="keywordflow">throw</span> <a class="code" href="class_integer_1_1_divide_by_zero.html">Integer::DivideByZero</a>();
03689
03690 <span class="keywordflow">if</span> (a.PositiveCompare(b) == -1)
03691 {
03692 remainder = a;
03693 remainder.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::POSITIVE;
03694 quotient = <a class="code" href="class_integer.html#_integerz37_12">Integer::Zero</a>();
03695 <span class="keywordflow">return</span>;
03696 }
03697
03698 aSize += aSize%2; <span class="comment">// round up to next even number</span>
03699 bSize += bSize%2;
03700
03701 remainder.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta22">CleanNew</a>(RoundupSize(bSize));
03702 remainder.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::POSITIVE;
03703 quotient.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta22">CleanNew</a>(RoundupSize(aSize-bSize+2));
03704 quotient.<a class="code" href="class_integer.html#_integerr1">sign</a> = Integer::POSITIVE;
03705
03706 <a class="code" href="class_sec_block.html">SecAlignedWordBlock</a> T(aSize+2*bSize+4);
03707 Divide(remainder.<a class="code" href="class_integer.html#_integerr0">reg</a>, quotient.<a class="code" href="class_integer.html#_integerr0">reg</a>, T, a.reg, aSize, b.reg, bSize);
03708 }
03709
03710 <span class="keywordtype">void</span> <a class="code" href="class_integer.html#_integerz49_9">Integer::Divide</a>(<a class="code" href="class_integer.html">Integer</a> &remainder, <a class="code" href="class_integer.html">Integer</a> &quotient, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &dividend, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &divisor)
<a name="l03711"></a><a class="code" href="class_integer.html#_integerz49_9">03711</a> {
03712 PositiveDivide(remainder, quotient, dividend, divisor);
03713
03714 <span class="keywordflow">if</span> (dividend.<a class="code" href="class_integer.html#_integerz41_10">IsNegative</a>())
03715 {
03716 quotient.<a class="code" href="class_integer.html#_integerz43_17">Negate</a>();
03717 <span class="keywordflow">if</span> (remainder.<a class="code" href="class_integer.html#_integerz41_9">NotZero</a>())
03718 {
03719 --quotient;
03720 remainder = divisor.<a class="code" href="class_integer.html#_integerz49_0">AbsoluteValue</a>() - remainder;
03721 }
03722 }
03723
03724 <span class="keywordflow">if</span> (divisor.<a class="code" href="class_integer.html#_integerz41_10">IsNegative</a>())
03725 quotient.<a class="code" href="class_integer.html#_integerz43_17">Negate</a>();
03726 }
03727
03728 <span class="keywordtype">void</span> Integer::DivideByPowerOf2(<a class="code" href="class_integer.html">Integer</a> &r, <a class="code" href="class_integer.html">Integer</a> &q, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n)
<a name="l03729"></a><a class="code" href="class_integer.html#_integerz49_11">03729</a> {
03730 q = a;
03731 q >>= n;
03732
03733 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> wordCount = BitsToWords(n);
03734 <span class="keywordflow">if</span> (wordCount <= a.WordCount())
03735 {
03736 r.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta25">resize</a>(RoundupSize(wordCount));
03737 CopyWords(r.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg, wordCount);
03738 SetWords(r.<a class="code" href="class_integer.html#_integerr0">reg</a>+wordCount, 0, r.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()-wordCount);
03739 <span class="keywordflow">if</span> (n % WORD_BITS != 0)
03740 r.<a class="code" href="class_integer.html#_integerr0">reg</a>[wordCount-1] %= (1 << (n % WORD_BITS));
03741 }
03742 <span class="keywordflow">else</span>
03743 {
03744 r.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta25">resize</a>(RoundupSize(a.WordCount()));
03745 CopyWords(r.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg, r.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03746 }
03747 r.<a class="code" href="class_integer.html#_integerr1">sign</a> = POSITIVE;
03748
03749 <span class="keywordflow">if</span> (a.IsNegative() && r.<a class="code" href="class_integer.html#_integerz41_9">NotZero</a>())
03750 {
03751 --q;
03752 r = <a class="code" href="class_integer.html#_integerz37_15">Power2</a>(n) - r;
03753 }
03754 }
03755
03756 <a class="code" href="class_integer.html">Integer</a> Integer::DividedBy(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)<span class="keyword"> const</span>
03757 <span class="keyword"></span>{
03758 <a class="code" href="class_integer.html">Integer</a> remainder, quotient;
03759 Integer::Divide(remainder, quotient, *<span class="keyword">this</span>, b);
03760 <span class="keywordflow">return</span> quotient;
03761 }
03762
03763 <a class="code" href="class_integer.html">Integer</a> Integer::Modulo(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)<span class="keyword"> const</span>
03764 <span class="keyword"></span>{
03765 <a class="code" href="class_integer.html">Integer</a> remainder, quotient;
03766 <a class="code" href="class_integer.html#_integerz49_9">Integer::Divide</a>(remainder, quotient, *<span class="keyword">this</span>, b);
03767 <span class="keywordflow">return</span> remainder;
03768 }
03769
03770 <span class="keywordtype">void</span> <a class="code" href="class_integer.html#_integerz49_9">Integer::Divide</a>(word &remainder, <a class="code" href="class_integer.html">Integer</a> &quotient, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &dividend, word divisor)
<a name="l03771"></a><a class="code" href="class_integer.html#_integerz49_10">03771</a> {
03772 <span class="keywordflow">if</span> (!divisor)
03773 <span class="keywordflow">throw</span> <a class="code" href="class_integer_1_1_divide_by_zero.html">Integer::DivideByZero</a>();
03774
03775 assert(divisor);
03776
03777 <span class="keywordflow">if</span> ((divisor & (divisor-1)) == 0) <span class="comment">// divisor is a power of 2</span>
03778 {
03779 quotient = dividend >> (BitPrecision(divisor)-1);
03780 remainder = dividend.<a class="code" href="class_integer.html#_integerr0">reg</a>[0] & (divisor-1);
03781 <span class="keywordflow">return</span>;
03782 }
03783
03784 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = dividend.<a class="code" href="class_integer.html#_integerz41_4">WordCount</a>();
03785 quotient.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta22">CleanNew</a>(RoundupSize(i));
03786 remainder = 0;
03787 <span class="keywordflow">while</span> (i--)
03788 {
03789 quotient.<a class="code" href="class_integer.html#_integerr0">reg</a>[i] = DWord(dividend.<a class="code" href="class_integer.html#_integerr0">reg</a>[i], remainder) / divisor;
03790 remainder = DWord(dividend.<a class="code" href="class_integer.html#_integerr0">reg</a>[i], remainder) % divisor;
03791 }
03792
03793 <span class="keywordflow">if</span> (dividend.<a class="code" href="class_integer.html#_integerz41_11">NotNegative</a>())
03794 quotient.<a class="code" href="class_integer.html#_integerr1">sign</a> = POSITIVE;
03795 <span class="keywordflow">else</span>
03796 {
03797 quotient.<a class="code" href="class_integer.html#_integerr1">sign</a> = NEGATIVE;
03798 <span class="keywordflow">if</span> (remainder)
03799 {
03800 --quotient;
03801 remainder = divisor - remainder;
03802 }
03803 }
03804 }
03805
03806 <a class="code" href="class_integer.html">Integer</a> Integer::DividedBy(word b)<span class="keyword"> const</span>
03807 <span class="keyword"></span>{
03808 word remainder;
03809 <a class="code" href="class_integer.html">Integer</a> quotient;
03810 Integer::Divide(remainder, quotient, *<span class="keyword">this</span>, b);
03811 <span class="keywordflow">return</span> quotient;
03812 }
03813
03814 word Integer::Modulo(word divisor)<span class="keyword"> const</span>
03815 <span class="keyword"></span>{
03816 <span class="keywordflow">if</span> (!divisor)
03817 <span class="keywordflow">throw</span> <a class="code" href="class_integer_1_1_divide_by_zero.html">Integer::DivideByZero</a>();
03818
03819 assert(divisor);
03820
03821 word remainder;
03822
03823 <span class="keywordflow">if</span> ((divisor & (divisor-1)) == 0) <span class="comment">// divisor is a power of 2</span>
03824 remainder = reg[0] & (divisor-1);
03825 <span class="keywordflow">else</span>
03826 {
03827 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = <a class="code" href="class_integer.html#_integerz41_4">WordCount</a>();
03828
03829 <span class="keywordflow">if</span> (divisor <= 5)
03830 {
03831 DWord sum(0, 0);
03832 <span class="keywordflow">while</span> (i--)
03833 sum += reg[i];
03834 remainder = sum % divisor;
03835 }
03836 <span class="keywordflow">else</span>
03837 {
03838 remainder = 0;
03839 <span class="keywordflow">while</span> (i--)
03840 remainder = DWord(reg[i], remainder) % divisor;
03841 }
03842 }
03843
03844 <span class="keywordflow">if</span> (IsNegative() && remainder)
03845 remainder = divisor - remainder;
03846
03847 <span class="keywordflow">return</span> remainder;
03848 }
03849
03850 <span class="keywordtype">void</span> Integer::Negate()
03851 {
03852 <span class="keywordflow">if</span> (!!(*this)) <span class="comment">// don't flip sign if *this==0</span>
03853 sign = Sign(1-sign);
03854 }
03855
03856 <span class="keywordtype">int</span> Integer::PositiveCompare(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& t)<span class="keyword"> const</span>
03857 <span class="keyword"></span>{
03858 <span class="keywordtype">unsigned</span> size = <a class="code" href="class_integer.html#_integerz41_4">WordCount</a>(), tSize = t.WordCount();
03859
03860 <span class="keywordflow">if</span> (size == tSize)
03861 <span class="keywordflow">return</span> CryptoPP::Compare(reg, t.reg, size);
03862 <span class="keywordflow">else</span>
03863 <span class="keywordflow">return</span> size > tSize ? 1 : -1;
03864 }
03865
03866 <span class="keywordtype">int</span> <a class="code" href="class_integer.html#_integerz47_0">Integer::Compare</a>(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& t)<span class="keyword"> const</span>
<a name="l03867"></a><a class="code" href="class_integer.html#_integerz47_0">03867</a> <span class="keyword"></span>{
03868 <span class="keywordflow">if</span> (NotNegative())
03869 {
03870 <span class="keywordflow">if</span> (t.NotNegative())
03871 <span class="keywordflow">return</span> PositiveCompare(t);
03872 <span class="keywordflow">else</span>
03873 <span class="keywordflow">return</span> 1;
03874 }
03875 <span class="keywordflow">else</span>
03876 {
03877 <span class="keywordflow">if</span> (t.NotNegative())
03878 <span class="keywordflow">return</span> -1;
03879 <span class="keywordflow">else</span>
03880 <span class="keywordflow">return</span> -PositiveCompare(t);
03881 }
03882 }
03883
03884 <a class="code" href="class_integer.html">Integer</a> <a class="code" href="class_integer.html#_integerz49_3">Integer::SquareRoot</a>()<span class="keyword"> const</span>
<a name="l03885"></a><a class="code" href="class_integer.html#_integerz49_3">03885</a> <span class="keyword"></span>{
03886 <span class="keywordflow">if</span> (!IsPositive())
03887 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz37_12">Zero</a>();
03888
03889 <span class="comment">// overestimate square root</span>
03890 <a class="code" href="class_integer.html">Integer</a> x, y = <a class="code" href="class_integer.html#_integerz37_15">Power2</a>((<a class="code" href="class_integer.html#_integerz41_2">BitCount</a>()+1)/2);
03891 assert(y*y >= *<span class="keyword">this</span>);
03892
03893 <span class="keywordflow">do</span>
03894 {
03895 x = y;
03896 y = (x + *<span class="keyword">this</span>/x) >> 1;
03897 } <span class="keywordflow">while</span> (y<x);
03898
03899 <span class="keywordflow">return</span> x;
03900 }
03901
03902 <span class="keywordtype">bool</span> <a class="code" href="class_integer.html#_integerz49_4">Integer::IsSquare</a>()<span class="keyword"> const</span>
<a name="l03903"></a><a class="code" href="class_integer.html#_integerz49_4">03903</a> <span class="keyword"></span>{
03904 <a class="code" href="class_integer.html">Integer</a> r = <a class="code" href="class_integer.html#_integerz49_3">SquareRoot</a>();
03905 <span class="keywordflow">return</span> *<span class="keyword">this</span> == r.<a class="code" href="class_integer.html#_integerz49_2">Squared</a>();
03906 }
03907
03908 <span class="keywordtype">bool</span> <a class="code" href="class_integer.html#_integerz49_5">Integer::IsUnit</a>()<span class="keyword"> const</span>
<a name="l03909"></a><a class="code" href="class_integer.html#_integerz49_5">03909</a> <span class="keyword"></span>{
03910 <span class="keywordflow">return</span> (<a class="code" href="class_integer.html#_integerz41_4">WordCount</a>() == 1) && (reg[0] == 1);
03911 }
03912
03913 <a class="code" href="class_integer.html">Integer</a> <a class="code" href="class_integer.html#_integerz49_6">Integer::MultiplicativeInverse</a>()<span class="keyword"> const</span>
<a name="l03914"></a><a class="code" href="class_integer.html#_integerz49_6">03914</a> <span class="keyword"></span>{
03915 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz49_5">IsUnit</a>() ? *<span class="keyword">this</span> : <a class="code" href="class_integer.html#_integerz37_12">Zero</a>();
03916 }
03917
03918 <a class="code" href="class_integer.html">Integer</a> a_times_b_mod_c(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &x, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& y, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& m)
<a name="l03919"></a><a class="code" href="class_integer.html#_integerz49_13">03919</a> {
03920 <span class="keywordflow">return</span> x*y%m;
03921 }
03922
03923 <a class="code" href="class_integer.html">Integer</a> a_exp_b_mod_c(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &x, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& e, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& m)
<a name="l03924"></a><a class="code" href="class_integer.html#_integerz49_14">03924</a> {
03925 <a class="code" href="class_modular_arithmetic.html">ModularArithmetic</a> mr(m);
03926 <span class="keywordflow">return</span> mr.<a class="code" href="class_abstract_ring.html#_euclidean_domain_ofa19">Exponentiate</a>(x, e);
03927 }
03928
03929 <a class="code" href="class_integer.html">Integer</a> Integer::Gcd(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)
<a name="l03930"></a><a class="code" href="class_integer.html#_integerz49_12">03930</a> {
03931 <span class="keywordflow">return</span> <a class="code" href="class_euclidean_domain_of.html">EuclideanDomainOf<Integer></a>().<a class="code" href="class_integer.html#_integerz49_12">Gcd</a>(a, b);
03932 }
03933
03934 <a class="code" href="class_integer.html">Integer</a> Integer::InverseMod(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &m)<span class="keyword"> const</span>
<a name="l03935"></a><a class="code" href="class_integer.html#_integerz49_7">03935</a> <span class="keyword"></span>{
03936 assert(m.<a class="code" href="class_integer.html#_integerz41_11">NotNegative</a>());
03937
03938 <span class="keywordflow">if</span> (IsNegative() || *<span class="keyword">this</span>>=m)
03939 <span class="keywordflow">return</span> (*<span class="keyword">this</span>%m).<a class="code" href="class_integer.html#_integerz49_7">InverseMod</a>(m);
03940
03941 <span class="keywordflow">if</span> (m.<a class="code" href="class_integer.html#_integerz41_14">IsEven</a>())
03942 {
03943 <span class="keywordflow">if</span> (!m || IsEven())
03944 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz37_12">Zero</a>(); <span class="comment">// no inverse</span>
03945 <span class="keywordflow">if</span> (*<span class="keyword">this</span> == <a class="code" href="class_integer.html#_integerz37_13">One</a>())
03946 <span class="keywordflow">return</span> <a class="code" href="class_integer.html#_integerz37_13">One</a>();
03947
03948 <a class="code" href="class_integer.html">Integer</a> u = m.<a class="code" href="class_integer.html#_integerz49_7">InverseMod</a>(*<span class="keyword">this</span>);
03949 <span class="keywordflow">return</span> !u ? <a class="code" href="class_integer.html#_integerz37_12">Zero</a>() : (m*(*<span class="keyword">this</span>-u)+1)/(*this);
03950 }
03951
03952 <a class="code" href="class_sec_block.html">SecBlock<word></a> T(m.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>() * 4);
03953 <a class="code" href="class_integer.html">Integer</a> r((word)0, m.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03954 <span class="keywordtype">unsigned</span> k = AlmostInverse(r.<a class="code" href="class_integer.html#_integerr0">reg</a>, T, reg, reg.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>(), m.<a class="code" href="class_integer.html#_integerr0">reg</a>, m.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03955 DivideByPower2Mod(r.<a class="code" href="class_integer.html#_integerr0">reg</a>, r.<a class="code" href="class_integer.html#_integerr0">reg</a>, k, m.<a class="code" href="class_integer.html#_integerr0">reg</a>, m.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03956 <span class="keywordflow">return</span> r;
03957 }
03958
03959 word Integer::InverseMod(<span class="keyword">const</span> word mod)<span class="keyword"> const</span>
03960 <span class="keyword"></span>{
03961 word g0 = mod, g1 = *<span class="keyword">this</span> % mod;
03962 word v0 = 0, v1 = 1;
03963 word y;
03964
03965 <span class="keywordflow">while</span> (g1)
03966 {
03967 <span class="keywordflow">if</span> (g1 == 1)
03968 <span class="keywordflow">return</span> v1;
03969 y = g0 / g1;
03970 g0 = g0 % g1;
03971 v0 += y * v1;
03972
03973 <span class="keywordflow">if</span> (!g0)
03974 <span class="keywordflow">break</span>;
03975 <span class="keywordflow">if</span> (g0 == 1)
03976 <span class="keywordflow">return</span> mod-v0;
03977 y = g1 / g0;
03978 g1 = g1 % g0;
03979 v1 += y * v0;
03980 }
03981 <span class="keywordflow">return</span> 0;
03982 }
03983
03984 <span class="comment">// ********************************************************</span>
03985
03986 ModularArithmetic::ModularArithmetic(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt)
03987 {
03988 <a class="code" href="class_b_e_r_sequence_decoder.html">BERSequenceDecoder</a> seq(bt);
03989 <a class="code" href="class_o_i_d.html">OID</a> oid(seq);
03990 <span class="keywordflow">if</span> (oid != ASN1::prime_field())
03991 BERDecodeError();
03992 modulus.<a class="code" href="class_integer.html#_integerz39_9">BERDecode</a>(seq);
03993 seq.<a class="code" href="class_b_e_r_general_decoder.html#_b_e_r_set_decodera9">MessageEnd</a>();
03994 result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta25">resize</a>(modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
03995 }
03996
03997 <span class="keywordtype">void</span> ModularArithmetic::DEREncode(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &bt)<span class="keyword"> const</span>
03998 <span class="keyword"></span>{
03999 <a class="code" href="class_d_e_r_sequence_encoder.html">DERSequenceEncoder</a> seq(bt);
04000 ASN1::prime_field().DEREncode(seq);
04001 modulus.<a class="code" href="class_integer.html#_integerz39_3">DEREncode</a>(seq);
04002 seq.<a class="code" href="class_d_e_r_general_encoder.html#_d_e_r_set_encodera2">MessageEnd</a>();
04003 }
04004
04005 <span class="keywordtype">void</span> ModularArithmetic::DEREncodeElement(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &out, <span class="keyword">const</span> Element &a)<span class="keyword"> const</span>
04006 <span class="keyword"></span>{
04007 a.DEREncodeAsOctetString(out, MaxElementByteLength());
04008 }
04009
04010 <span class="keywordtype">void</span> ModularArithmetic::BERDecodeElement(<a class="code" href="class_buffered_transformation.html">BufferedTransformation</a> &in, Element &a)<span class="keyword"> const</span>
04011 <span class="keyword"></span>{
04012 a.BERDecodeAsOctetString(in, MaxElementByteLength());
04013 }
04014
04015 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& ModularArithmetic::Half(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a)<span class="keyword"> const</span>
04016 <span class="keyword"></span>{
04017 <span class="keywordflow">if</span> (a.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
04018 {
04019 CryptoPP::DivideByPower2Mod(result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>(), a.reg, 1, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg.size());
04020 <span class="keywordflow">return</span> result;
04021 }
04022 <span class="keywordflow">else</span>
04023 <span class="keywordflow">return</span> result1 = (a.IsEven() ? (a >> 1) : ((a+modulus) >> 1));
04024 }
04025
04026 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& ModularArithmetic::Add(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)<span class="keyword"> const</span>
04027 <span class="keyword"></span>{
04028 <span class="keywordflow">if</span> (a.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>() && b.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
04029 {
04030 <span class="keywordflow">if</span> (CryptoPP::Add(result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>(), a.reg, b.reg, a.reg.size())
04031 || Compare(result.<a class="code" href="class_integer.html#_integerr0">reg</a>, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg.size()) >= 0)
04032 {
04033 CryptoPP::Subtract(result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>(), result.<a class="code" href="class_integer.html#_integerr0">reg</a>, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg.size());
04034 }
04035 <span class="keywordflow">return</span> result;
04036 }
04037 <span class="keywordflow">else</span>
04038 {
04039 result1 = a+b;
04040 <span class="keywordflow">if</span> (result1 >= modulus)
04041 result1 -= modulus;
04042 <span class="keywordflow">return</span> result1;
04043 }
04044 }
04045
04046 <a class="code" href="class_integer.html">Integer</a>& ModularArithmetic::Accumulate(<a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)<span class="keyword"> const</span>
04047 <span class="keyword"></span>{
04048 <span class="keywordflow">if</span> (a.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>() && b.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
04049 {
04050 <span class="keywordflow">if</span> (CryptoPP::Add(a.reg, a.reg, b.reg, a.reg.size())
04051 || Compare(a.reg, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg.size()) >= 0)
04052 {
04053 CryptoPP::Subtract(a.reg, a.reg, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg.size());
04054 }
04055 }
04056 <span class="keywordflow">else</span>
04057 {
04058 a+=b;
04059 <span class="keywordflow">if</span> (a>=modulus)
04060 a-=modulus;
04061 }
04062
04063 <span class="keywordflow">return</span> a;
04064 }
04065
04066 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& ModularArithmetic::Subtract(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)<span class="keyword"> const</span>
04067 <span class="keyword"></span>{
04068 <span class="keywordflow">if</span> (a.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>() && b.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
04069 {
04070 <span class="keywordflow">if</span> (CryptoPP::Subtract(result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>(), a.reg, b.reg, a.reg.size()))
04071 CryptoPP::Add(result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>(), result.<a class="code" href="class_integer.html#_integerr0">reg</a>, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg.size());
04072 <span class="keywordflow">return</span> result;
04073 }
04074 <span class="keywordflow">else</span>
04075 {
04076 result1 = a-b;
04077 <span class="keywordflow">if</span> (result1.<a class="code" href="class_integer.html#_integerz41_10">IsNegative</a>())
04078 result1 += modulus;
04079 <span class="keywordflow">return</span> result1;
04080 }
04081 }
04082
04083 <a class="code" href="class_integer.html">Integer</a>& ModularArithmetic::Reduce(<a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)<span class="keyword"> const</span>
04084 <span class="keyword"></span>{
04085 <span class="keywordflow">if</span> (a.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>() && b.reg.size()==modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>())
04086 {
04087 <span class="keywordflow">if</span> (CryptoPP::Subtract(a.reg, a.reg, b.reg, a.reg.size()))
04088 CryptoPP::Add(a.reg, a.reg, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg.size());
04089 }
04090 <span class="keywordflow">else</span>
04091 {
04092 a-=b;
04093 <span class="keywordflow">if</span> (a.IsNegative())
04094 a+=modulus;
04095 }
04096
04097 <span class="keywordflow">return</span> a;
04098 }
04099
04100 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& ModularArithmetic::Inverse(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a)<span class="keyword"> const</span>
04101 <span class="keyword"></span>{
04102 <span class="keywordflow">if</span> (!a)
04103 <span class="keywordflow">return</span> a;
04104
04105 CopyWords(result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>(), modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>());
04106 <span class="keywordflow">if</span> (CryptoPP::Subtract(result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>(), result.<a class="code" href="class_integer.html#_integerr0">reg</a>, a.reg, a.reg.size()))
04107 Decrement(result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>()+a.reg.size(), 1, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>()-a.reg.size());
04108
04109 <span class="keywordflow">return</span> result;
04110 }
04111
04112 <a class="code" href="class_integer.html">Integer</a> ModularArithmetic::CascadeExponentiate(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &x, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &e1, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &y, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &e2)<span class="keyword"> const</span>
04113 <span class="keyword"></span>{
04114 <span class="keywordflow">if</span> (modulus.<a class="code" href="class_integer.html#_integerz41_15">IsOdd</a>())
04115 {
04116 <a class="code" href="class_montgomery_representation.html">MontgomeryRepresentation</a> dr(modulus);
04117 <span class="keywordflow">return</span> dr.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa4">ConvertOut</a>(dr.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa9">CascadeExponentiate</a>(dr.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa3">ConvertIn</a>(x), e1, dr.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa3">ConvertIn</a>(y), e2));
04118 }
04119 <span class="keywordflow">else</span>
04120 <span class="keywordflow">return</span> <a class="code" href="class_abstract_ring.html">AbstractRing<Integer>::CascadeExponentiate</a>(x, e1, y, e2);
04121 }
04122
04123 <span class="keywordtype">void</span> ModularArithmetic::SimultaneousExponentiate(<a class="code" href="class_integer.html">Integer</a> *results, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &base, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> *exponents, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> exponentsCount)<span class="keyword"> const</span>
04124 <span class="keyword"></span>{
04125 <span class="keywordflow">if</span> (modulus.<a class="code" href="class_integer.html#_integerz41_15">IsOdd</a>())
04126 {
04127 <a class="code" href="class_montgomery_representation.html">MontgomeryRepresentation</a> dr(modulus);
04128 dr.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa10">SimultaneousExponentiate</a>(results, dr.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa3">ConvertIn</a>(base), exponents, exponentsCount);
04129 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i<exponentsCount; i++)
04130 results[i] = dr.<a class="code" href="class_montgomery_representation.html#_montgomery_representationa4">ConvertOut</a>(results[i]);
04131 }
04132 <span class="keywordflow">else</span>
04133 <a class="code" href="class_abstract_ring.html">AbstractRing<Integer>::SimultaneousExponentiate</a>(results, base, exponents, exponentsCount);
04134 }
04135
04136 MontgomeryRepresentation::MontgomeryRepresentation(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &m) <span class="comment">// modulus must be odd</span>
04137 : <a class="code" href="class_modular_arithmetic.html">ModularArithmetic</a>(m),
04138 u((word)0, modulus.reg.size()),
04139 workspace(5*modulus.reg.size())
04140 {
04141 <span class="keywordflow">if</span> (!modulus.IsOdd())
04142 <span class="keywordflow">throw</span> <a class="code" href="class_invalid_argument.html">InvalidArgument</a>(<span class="stringliteral">"MontgomeryRepresentation: Montgomery representation requires an odd modulus"</span>);
04143
04144 RecursiveInverseModPower2(u.reg, workspace, modulus.reg, modulus.reg.size());
04145 }
04146
04147 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& MontgomeryRepresentation::Multiply(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &b)<span class="keyword"> const</span>
04148 <span class="keyword"></span>{
04149 word *<span class="keyword">const</span> T = workspace.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>();
04150 word *<span class="keyword">const</span> R = result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>();
04151 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N = modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>();
04152 assert(a.reg.size()<=N && b.reg.size()<=N);
04153
04154 AsymmetricMultiply(T, T+2*N, a.reg, a.reg.size(), b.reg, b.reg.size());
04155 SetWords(T+a.reg.size()+b.reg.size(), 0, 2*N-a.reg.size()-b.reg.size());
04156 MontgomeryReduce(R, T+2*N, T, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, u.<a class="code" href="class_integer.html#_integerr0">reg</a>, N);
04157 <span class="keywordflow">return</span> result;
04158 }
04159
04160 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& MontgomeryRepresentation::Square(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a)<span class="keyword"> const</span>
04161 <span class="keyword"></span>{
04162 word *<span class="keyword">const</span> T = workspace.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>();
04163 word *<span class="keyword">const</span> R = result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>();
04164 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N = modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>();
04165 assert(a.reg.size()<=N);
04166
04167 CryptoPP::Square(T, T+2*N, a.reg, a.reg.size());
04168 SetWords(T+2*a.reg.size(), 0, 2*N-2*a.reg.size());
04169 MontgomeryReduce(R, T+2*N, T, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, u.<a class="code" href="class_integer.html#_integerr0">reg</a>, N);
04170 <span class="keywordflow">return</span> result;
04171 }
04172
04173 <a class="code" href="class_integer.html">Integer</a> MontgomeryRepresentation::ConvertOut(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a)<span class="keyword"> const</span>
04174 <span class="keyword"></span>{
04175 word *<span class="keyword">const</span> T = workspace.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>();
04176 word *<span class="keyword">const</span> R = result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>();
04177 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N = modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>();
04178 assert(a.reg.size()<=N);
04179
04180 CopyWords(T, a.reg, a.reg.size());
04181 SetWords(T+a.reg.size(), 0, 2*N-a.reg.size());
04182 MontgomeryReduce(R, T+2*N, T, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, u.<a class="code" href="class_integer.html#_integerr0">reg</a>, N);
04183 <span class="keywordflow">return</span> result;
04184 }
04185
04186 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a>& MontgomeryRepresentation::MultiplicativeInverse(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &a)<span class="keyword"> const</span>
04187 <span class="keyword"></span>{
04188 <span class="comment">// return (EuclideanMultiplicativeInverse(a, modulus)<<(2*WORD_BITS*modulus.reg.size()))%modulus;</span>
04189 word *<span class="keyword">const</span> T = workspace.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>();
04190 word *<span class="keyword">const</span> R = result.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta9">begin</a>();
04191 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N = modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>.<a class="code" href="class_sec_block.html#_sec_block_with_hinta15">size</a>();
04192 assert(a.reg.size()<=N);
04193
04194 CopyWords(T, a.reg, a.reg.size());
04195 SetWords(T+a.reg.size(), 0, 2*N-a.reg.size());
04196 MontgomeryReduce(R, T+2*N, T, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, u.<a class="code" href="class_integer.html#_integerr0">reg</a>, N);
04197 <span class="keywordtype">unsigned</span> k = AlmostInverse(R, T, R, N, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, N);
04198
04199 <span class="comment">// cout << "k=" << k << " N*32=" << 32*N << endl;</span>
04200
04201 <span class="keywordflow">if</span> (k>N*WORD_BITS)
04202 DivideByPower2Mod(R, R, k-N*WORD_BITS, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, N);
04203 <span class="keywordflow">else</span>
04204 MultiplyByPower2Mod(R, R, N*WORD_BITS-k, modulus.<a class="code" href="class_integer.html#_integerr0">reg</a>, N);
04205
04206 <span class="keywordflow">return</span> result;
04207 }
04208
04209 NAMESPACE_END
04210
04211 <span class="preprocessor">#endif</span>
</div></pre><hr size="1"><address style="align: right;"><small>Generated on Sun Nov 7 08:23:58 2004 for Crypto++ by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0 ></a> 1.3.7 </small></address>
</body>
</html>
distrib
>
Mandriva
>
10.2
>
i586
>
media
>
contrib
>
by-pkgid
>
7457b841ac8136d3a1a9d3d960c5252e
>
files
>
1291
