📄 integer_8cpp-source.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 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.2 --><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">Compound 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">Compound Members</a> | <a class="qindex" href="globals.html">File Members</a></div><h1>integer.cpp</h1><div class="fragment"><pre>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">#include <emmintrin.h></span>00022 <span class="preprocessor">#endif</span>00023 <span class="preprocessor"></span>00024 NAMESPACE_BEGIN(CryptoPP)00025 00026 #ifdef SSE2_INTRINSICS_AVAILABLE00027 <span class="keyword">template</span> <<span class="keyword">class</span> T>00028 CPP_TYPENAME AllocatorBase<T>::pointer AlignedAllocator<T>::allocate(size_type n, <span class="keyword">const</span> <span class="keywordtype">void</span> *)00029 {00030 <span class="keywordflow">if</span> (n < 4)00031 <span class="keywordflow">return</span> <span class="keyword">new</span> T[n];00032 <span class="keywordflow">else</span>00033 <span class="keywordflow">return</span> (T *)_mm_malloc(<span class="keyword">sizeof</span>(T)*n, 16);00034 00035 }00036 00037 <span class="keyword">template</span> <<span class="keyword">class</span> T>00038 <span class="keywordtype">void</span> AlignedAllocator<T>::deallocate(<span class="keywordtype">void</span> *p, size_type n)00039 {00040 memset(p, 0, n*<span class="keyword">sizeof</span>(T));00041 <span class="keywordflow">if</span> (n < 4)00042 <span class="keyword">delete</span> [] p;00043 <span class="keywordflow">else</span>00044 _mm_free(p);00045 }00046 <span class="preprocessor">#endif</span>00047 <span class="preprocessor"></span>00048 <span class="preprocessor">#define MAKE_DWORD(lowWord, highWord) ((dword(highWord)<<WORD_BITS) | (lowWord))</span>00049 <span class="preprocessor"></span>00050 <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)00051 {00052 <span class="keywordflow">while</span> (N--)00053 <span class="keywordflow">if</span> (A[N] > B[N])00054 <span class="keywordflow">return</span> 1;00055 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (A[N] < B[N])00056 <span class="keywordflow">return</span> -1;00057 00058 <span class="keywordflow">return</span> 0;00059 }00060 00061 <span class="keyword">static</span> word Increment(word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N, word B=1)00062 {00063 assert(N);00064 word t = A[0];00065 A[0] = t+B;00066 <span class="keywordflow">if</span> (A[0] >= t)00067 <span class="keywordflow">return</span> 0;00068 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=1; i<N; i++)00069 <span class="keywordflow">if</span> (++A[i])00070 <span class="keywordflow">return</span> 0;00071 <span class="keywordflow">return</span> 1;00072 }00073 00074 <span class="keyword">static</span> word Decrement(word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N, word B=1)00075 {00076 assert(N);00077 word t = A[0];00078 A[0] = t-B;00079 <span class="keywordflow">if</span> (A[0] <= t)00080 <span class="keywordflow">return</span> 0;00081 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=1; i<N; i++)00082 <span class="keywordflow">if</span> (A[i]--)00083 <span class="keywordflow">return</span> 0;00084 <span class="keywordflow">return</span> 1;00085 }00086 00087 <span class="keyword">static</span> <span class="keywordtype">void</span> TwosComplement(word *A, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> N)00088 {00089 Decrement(A, N);00090 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=0; i<N; i++)00091 A[i] = ~A[i];00092 }00093 00094 <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)00095 {00096 word carry=0;00097 <span class="keywordflow">for</span>(<span class="keywordtype">unsigned</span> i=0; i<N; i++)00098 {00099 dword p = (dword)A[i] * B + carry;00100 C[i] = LOW_WORD(p);00101 carry = HIGH_WORD(p);00102 }00103 <span class="keywordflow">return</span> carry;00104 }00105 00106 <span class="keyword">static</span> <span class="keywordtype">void</span> AtomicInverseModPower2(word *C, word A0, word A1)00107 {00108 assert(A0%2==1);00109 00110 dword A=MAKE_DWORD(A0, A1), R=A0%8;00111 00112 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i=3; i<2*WORD_BITS; i*=2)00113 R = R*(2-R*A);00114 00115 assert(R*A==1);00116 00117 C[0] = LOW_WORD(R);00118 C[1] = HIGH_WORD(R);00119 }00120 00121 <span class="comment">// ********************************************************</span>00122 00123 <span class="keyword">class </span>Portable00124 {00125 <span class="keyword">public</span>:00126 <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);00127 <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);00128 00129 <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);00130 <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);00131 <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);00132 <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);00133 <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;}00134 00135 <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);00136 <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);00137 <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);00138 <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;}00139 00140 <span class="keyword">static</span> <span class="keywordtype">void</span> Square2(word *R, <span class="keyword">const</span> word *A);00141 <span class="keyword">static</span> <span class="keywordtype">void</span> Square4(word *R, <span class="keyword">const</span> word *A);00142 <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>);}00143 <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;}00144 };00145 00146 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)00147 {00148 assert (N%2 == 0);00149 00150 <span class="preprocessor">#ifdef IS_LITTLE_ENDIAN</span>00151 <span class="preprocessor"></span> <span class="keywordflow">if</span> (<span class="keyword">sizeof</span>(dword) == <span class="keyword">sizeof</span>(size_t)) <span class="comment">// dword is only register size</span>00152 {00153 dword carry = 0;00154 N >>= 1;00155 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = 0; i < N; i++)00156 {00157 dword a = ((<span class="keyword">const</span> dword *)A)[i] + carry;00158 dword c = a + ((<span class="keyword">const</span> dword *)B)[i];00159 ((dword *)C)[i] = c;00160 carry = (a < carry) | (c < a);00161 }00162 <span class="keywordflow">return</span> (word)carry;00163 }00164 <span class="keywordflow">else</span>00165 <span class="preprocessor">#endif</span>00166 <span class="preprocessor"></span> {00167 word carry = 0;00168 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = 0; i < N; i+=2)00169 {00170 dword u = (dword) carry + A[i] + B[i];00171 C[i] = LOW_WORD(u);00172 u = (dword) HIGH_WORD(u) + A[i+1] + B[i+1];00173 C[i+1] = LOW_WORD(u);00174 carry = HIGH_WORD(u);00175 }00176 <span class="keywordflow">return</span> carry;00177 }00178 }00179 00180 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)00181 {00182 assert (N%2 == 0);00183 00184 <span class="preprocessor">#ifdef IS_LITTLE_ENDIAN</span>00185 <span class="preprocessor"></span> <span class="keywordflow">if</span> (<span class="keyword">sizeof</span>(dword) == <span class="keyword">sizeof</span>(size_t)) <span class="comment">// dword is only register size</span>00186 {00187 dword borrow = 0;00188 N >>= 1;00189 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i = 0; i < N; i++)00190 {00191 dword a = ((<span class="keyword">const</span> dword *)A)[i];00192 dword b = a - borrow;00193 dword c = b - ((<span class="keyword">const</span> dword *)B)[i];00194 ((dword *)C)[i] = c;00195 borrow = (b > a) | (c > b);00196 }00197 <span class="keywordflow">return</span> (word)borrow;00198 }00199 <span class="keywordflow">else</span>00200 <span class="preprocessor">#endif</span>00201 <span class="preprocessor"></span> {00202 word borrow=0;00203 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i < N; i+=2)00204 {00205 dword u = (dword) A[i] - B[i] - borrow;00206 C[i] = LOW_WORD(u);00207 u = (dword) A[i+1] - B[i+1] - (word)(0-HIGH_WORD(u));00208 C[i+1] = LOW_WORD(u);00209 borrow = 0-HIGH_WORD(u);00210 }00211 <span class="keywordflow">return</span> borrow;00212 }00213 }00214 00215 <span class="keywordtype">void</span> Portable::Multiply2(word *C, <span class="keyword">const</span> word *A, <span class="keyword">const</span> word *B)00216 {00217 <span class="comment">/*</span>00218 <span class="comment"> word s;</span>00219 <span class="comment"> dword d;</span>00220 <span class="comment"></span>00221 <span class="comment"> if (A1 >= A0)</span>00222 <span class="comment"> if (B0 >= B1)</span>00223 <span class="comment"> {</span>00224 <span class="comment"> s = 0;</span>00225 <span class="comment"> d = (dword)(A1-A0)*(B0-B1);</span>00226 <span class="comment"> }</span>00227 <span class="comment"> else</span>00228 <span class="comment"> {</span>00229 <span class="comment"> s = (A1-A0);</span>00230 <span class="comment"> d = (dword)s*(word)(B0-B1);</span>00231 <span class="comment"> }</span>00232 <span class="comment"> else</span>00233 <span class="comment"> if (B0 > B1)</span>00234 <span class="comment"> {</span>00235 <span class="comment"> s = (B0-B1);</span>00236 <span class="comment"> d = (word)(A1-A0)*(dword)s;</span>00237 <span class="comment"> }</span>00238 <span class="comment"> else</span>00239 <span class="comment"> {</span>00240 <span class="comment"> s = 0;</span>00241 <span class="comment"> d = (dword)(A0-A1)*(B1-B0);</span>00242 <span class="comment"> }</span>00243 <span class="comment">*/</span>00244 <span class="comment">// this segment is the branchless equivalent of above</span>00245 word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};00246 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ai = A[1] < A[0];00247 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bi = B[0] < B[1];00248 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> di = ai & bi;00249 dword d = (dword)D[di]*D[di+2];00250 D[1] = D[3] = 0;00251 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> si = ai + !bi;00252 word s = D[si];00253 00254 dword A0B0 = (dword)A[0]*B[0];00255 C[0] = LOW_WORD(A0B0);00256 00257 dword A1B1 = (dword)A[1]*B[1];00258 dword t = (dword) HIGH_WORD(A0B0) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1);00259 C[1] = LOW_WORD(t);00260 00261 t = A1B1 + HIGH_WORD(t) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s;00262 C[2] = LOW_WORD(t);00263 C[3] = HIGH_WORD(t);00264 }⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -