?? integer.cpp
字號:
// integer.cpp - written and placed in the public domain by Wei Dai
#include "pch.h"
#include "integer.h"
#include "modarith.h"
#include "nbtheory.h"
#include "asn.h"
#include "words.h"
#include <iostream>
#include "algebra.cpp"
#include "eprecomp.cpp"
NAMESPACE_BEGIN(CryptoPP)
#define MAKE_DWORD(lowWord, highWord) ((dword(highWord)<<WORD_BITS) | (lowWord))
#if defined(_MSC_VER) && defined(_M_IX86) && (_M_IX86<=500)
// Add() and Subtract() are coded in Pentium assembly for a speed increase
// of about 10-20 percent for a RSA signature
static __declspec(naked) word __fastcall Add(word *C, const word *A, const word *B, unsigned int N)
{
__asm
{
push ebp
push ebx
push esi
push edi
mov esi, [esp+24]
mov ebx, [esp+20]
sub ecx, edx
xor eax, eax
sub eax, esi
lea ebx, [ebx+4*esi]
sar eax, 1 // clears the carry flag
jz loopend
loopstart:
mov esi,[edx]
mov ebp,[edx+4]
mov edi,[ebx+8*eax]
lea edx,[edx+8]
adc esi,edi
mov edi,[ebx+8*eax+4]
adc ebp,edi
inc eax
mov [edx+ecx-8],esi
mov [edx+ecx-4],ebp
jnz loopstart
loopend:
adc eax, 0
pop edi
pop esi
pop ebx
pop ebp
ret 8
}
}
static __declspec(naked) word __fastcall Subtract(word *C, const word *A, const word *B, unsigned int N)
{
__asm
{
push ebp
push ebx
push esi
push edi
mov esi, [esp+24]
mov ebx, [esp+20]
sub ecx, edx
xor eax, eax
sub eax, esi
lea ebx, [ebx+4*esi]
sar eax, 1 // clears the carry flag
jz loopend
loopstart:
mov esi,[edx]
mov ebp,[edx+4]
mov edi,[ebx+8*eax]
lea edx,[edx+8]
sbb esi,edi
mov edi,[ebx+8*eax+4]
sbb ebp,edi
inc eax
mov [edx+ecx-8],esi
mov [edx+ecx-4],ebp
jnz loopstart
loopend:
adc eax, 0
pop edi
pop esi
pop ebx
pop ebp
ret 8
}
}
#else // defined(_MSC_VER) && defined(_M_IX86) && (_M_IX86<=500)
static word Add(word *C, const word *A, const word *B, unsigned int N)
{
assert (N%2 == 0);
word carry=0;
for (unsigned i = 0; i < N; i+=2)
{
dword u = (dword) carry + A[i] + B[i];
C[i] = LOW_WORD(u);
u = (dword) HIGH_WORD(u) + A[i+1] + B[i+1];
C[i+1] = LOW_WORD(u);
carry = HIGH_WORD(u);
}
return carry;
}
static word Subtract(word *C, const word *A, const word *B, unsigned int N)
{
assert (N%2 == 0);
word borrow=0;
for (unsigned i = 0; i < N; i+=2)
{
dword u = (dword) A[i] - B[i] - borrow;
C[i] = LOW_WORD(u);
u = (dword) A[i+1] - B[i+1] - (word)(0-HIGH_WORD(u));
C[i+1] = LOW_WORD(u);
borrow = 0-HIGH_WORD(u);
}
return borrow;
}
#endif // defined(_MSC_VER) && defined(_M_IX86) && (_M_IX86<=500)
static int Compare(const word *A, const word *B, unsigned int N)
{
while (N--)
if (A[N] > B[N])
return 1;
else if (A[N] < B[N])
return -1;
return 0;
}
static word Increment(word *A, unsigned int N, word B=1)
{
assert(N);
word t = A[0];
A[0] = t+B;
if (A[0] >= t)
return 0;
for (unsigned i=1; i<N; i++)
if (++A[i])
return 0;
return 1;
}
static word Decrement(word *A, unsigned int N, word B=1)
{
assert(N);
word t = A[0];
A[0] = t-B;
if (A[0] <= t)
return 0;
for (unsigned i=1; i<N; i++)
if (A[i]--)
return 0;
return 1;
}
static void TwosComplement(word *A, unsigned int N)
{
Decrement(A, N);
for (unsigned i=0; i<N; i++)
A[i] = ~A[i];
}
static word LinearMultiply(word *C, const word *A, word B, unsigned int N)
{
word carry=0;
for(unsigned i=0; i<N; i++)
{
dword p = (dword)A[i] * B + carry;
C[i] = LOW_WORD(p);
carry = HIGH_WORD(p);
}
return carry;
}
static void AtomicMultiply(word *C, word A0, word A1, word B0, word B1)
{
word s;
dword d;
if (A1 >= A0)
if (B0 >= B1)
{
s = 0;
d = (dword)(A1-A0)*(B0-B1);
}
else
{
s = (A1-A0);
d = (dword)s*(word)(B0-B1);
}
else
if (B0 > B1)
{
s = (B0-B1);
d = (word)(A1-A0)*(dword)s;
}
else
{
s = 0;
d = (dword)(A0-A1)*(B1-B0);
}
dword A0B0 = (dword)A0*B0;
C[0] = LOW_WORD(A0B0);
dword A1B1 = (dword)A1*B1;
dword t = (dword) HIGH_WORD(A0B0) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1);
C[1] = LOW_WORD(t);
t = A1B1 + HIGH_WORD(t) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s;
C[2] = LOW_WORD(t);
C[3] = HIGH_WORD(t);
}
static word AtomicMultiplyAdd(word *C, word A0, word A1, word B0, word B1)
{
word s;
dword d;
if (A1 >= A0)
if (B0 >= B1)
{
s = 0;
d = (dword)(A1-A0)*(B0-B1);
}
else
{
s = (A1-A0);
d = (dword)s*(word)(B0-B1);
}
else
if (B0 > B1)
{
s = (B0-B1);
d = (word)(A1-A0)*(dword)s;
}
else
{
s = 0;
d = (dword)(A0-A1)*(B1-B0);
}
dword A0B0 = (dword)A0*B0;
dword t = A0B0 + C[0];
C[0] = LOW_WORD(t);
dword A1B1 = (dword)A1*B1;
t = (dword) HIGH_WORD(t) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1) + C[1];
C[1] = LOW_WORD(t);
t = (dword) HIGH_WORD(t) + LOW_WORD(A1B1) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s + C[2];
C[2] = LOW_WORD(t);
t = (dword) HIGH_WORD(t) + HIGH_WORD(A1B1) + C[3];
C[3] = LOW_WORD(t);
return HIGH_WORD(t);
}
static inline void AtomicSquare(word *C, word A, word B)
{
dword t1 = (dword) A*A;
C[0] = LOW_WORD(t1);
dword t2 = (dword) A*B;
t1 = (dword) HIGH_WORD(t1) + LOW_WORD(t2) + LOW_WORD(t2);
C[1] = LOW_WORD(t1);
t1 = (dword) B*B + HIGH_WORD(t1) + HIGH_WORD(t2) + HIGH_WORD(t2);
C[2] = LOW_WORD(t1);
C[3] = HIGH_WORD(t1);
}
static inline void AtomicMultiplyBottom(word *C, word A0, word A1, word B0, word B1)
{
dword t = (dword)A0*B0;
C[0] = LOW_WORD(t);
C[1] = HIGH_WORD(t) + A0*B1 + A1*B0;
}
static inline void AtomicMultiplyBottomAdd(word *C, word A0, word A1, word B0, word B1)
{
dword t = (dword)A0*B0 + C[0];
C[0] = LOW_WORD(t);
C[1] += HIGH_WORD(t) + A0*B1 + A1*B0;
}
static void CombaMultiply(word *R, const word *A, const word *B)
{
dword p;
word c=0, d=0, e=0;
#define MulAcc(x, y) \
p = (dword)A[x] * B[y] + c; \
c = LOW_WORD(p); \
p = (dword)d + HIGH_WORD(p); \
d = LOW_WORD(p); \
e += HIGH_WORD(p);
#define SaveMulAcc(s, x, y) \
R[s] = c; \
p = (dword)A[x] * B[y] + d; \
c = LOW_WORD(p); \
p = (dword)e + HIGH_WORD(p); \
d = LOW_WORD(p); \
e = HIGH_WORD(p);
p = (dword)A[0] * B[0];
R[0] = LOW_WORD(p);
c = HIGH_WORD(p);
d = e = 0;
MulAcc(0, 1);
MulAcc(1, 0);
SaveMulAcc(1, 2, 0);
MulAcc(1, 1);
MulAcc(0, 2);
SaveMulAcc(2, 0, 3);
MulAcc(1, 2);
MulAcc(2, 1);
MulAcc(3, 0);
SaveMulAcc(3, 3, 1);
MulAcc(2, 2);
MulAcc(1, 3);
SaveMulAcc(4, 2, 3);
MulAcc(3, 2);
R[5] = c;
p = (dword)A[3] * B[3] + d;
R[6] = LOW_WORD(p);
R[7] = e + HIGH_WORD(p);
#undef MulAcc
#undef SaveMulAcc
}
static void AtomicInverseModPower2(word *C, word A0, word A1)
{
assert(A0%2==1);
dword A=MAKE_DWORD(A0, A1), R=A0%8;
for (unsigned i=3; i<2*WORD_BITS; i*=2)
R = R*(2-R*A);
assert(R*A==1);
C[0] = LOW_WORD(R);
C[1] = HIGH_WORD(R);
}
// ********************************************************
#define A0 A
#define A1 (A+N2)
#define B0 B
#define B1 (B+N2)
#define T0 T
#define T1 (T+N2)
#define T2 (T+N)
#define T3 (T+N+N2)
#define R0 R
#define R1 (R+N2)
#define R2 (R+N)
#define R3 (R+N+N2)
// R[2*N] - result = A*B
// T[2*N] - temporary work space
// A[N] --- multiplier
// B[N] --- multiplicant
void RecursiveMultiply(word *R, word *T, const word *A, const word *B, unsigned int N)
{
assert(N>=2 && N%2==0);
if (N==2)
AtomicMultiply(R, A[0], A[1], B[0], B[1]);
else if (N==4)
CombaMultiply(R, A, B);
else
{
const unsigned int N2 = N/2;
int carry;
int aComp = Compare(A0, A1, N2);
int bComp = Compare(B0, B1, N2);
switch (2*aComp + aComp + bComp)
{
case -4:
Subtract(R0, A1, A0, N2);
Subtract(R1, B0, B1, N2);
RecursiveMultiply(T0, T2, R0, R1, N2);
Subtract(T1, T1, R0, N2);
carry = -1;
break;
case -2:
Subtract(R0, A1, A0, N2);
Subtract(R1, B0, B1, N2);
RecursiveMultiply(T0, T2, R0, R1, N2);
carry = 0;
break;
case 2:
Subtract(R0, A0, A1, N2);
Subtract(R1, B1, B0, N2);
RecursiveMultiply(T0, T2, R0, R1, N2);
carry = 0;
break;
case 4:
Subtract(R0, A1, A0, N2);
Subtract(R1, B0, B1, N2);
RecursiveMultiply(T0, T2, R0, R1, N2);
Subtract(T1, T1, R1, N2);
carry = -1;
break;
default:
SetWords(T0, 0, N);
carry = 0;
}
RecursiveMultiply(R0, T2, A0, B0, N2);
RecursiveMultiply(R2, T2, A1, B1, N2);
// now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1
carry += Add(T0, T0, R0, N);
carry += Add(T0, T0, R2, N);
carry += Add(R1, R1, T0, N);
assert (carry >= 0 && carry <= 2);
Increment(R3, N2, carry);
}
}
// R[2*N] - result = A*A
// T[2*N] - temporary work space
// A[N] --- number to be squared
void RecursiveSquare(word *R, word *T, const word *A, unsigned int N)
{
assert(N && N%2==0);
if (N==2)
AtomicSquare(R, A[0], A[1]);
else if (N==4)
{
AtomicSquare(R, A[0], A[1]);
AtomicSquare(R+4, A[2], A[3]);
AtomicMultiply(T, A[0], A[1], A[2], A[3]);
word carry = Add(R+2, R+2, T, 4);
carry += Add(R+2, R+2, T, 4);
Increment(R+6, 2, carry);
}
else
{
const unsigned int N2 = N/2;
RecursiveSquare(R0, T2, A0, N2);
RecursiveSquare(R2, T2, A1, N2);
RecursiveMultiply(T0, T2, A0, A1, N2);
word carry = Add(R1, R1, T0, N);
carry += Add(R1, R1, T0, N);
Increment(R3, N2, carry);
}
}
// R[N] - bottom half of A*B
// T[N] - temporary work space
// A[N] - multiplier
// B[N] - multiplicant
void RecursiveMultiplyBottom(word *R, word *T, const word *A, const word *B, unsigned int N)
{
assert(N>=2 && N%2==0);
if (N==2)
AtomicMultiplyBottom(R, A[0], A[1], B[0], B[1]);
else if (N==4)
{
AtomicMultiply(R, A[0], A[1], B[0], B[1]);
AtomicMultiplyBottomAdd(R+2, A[0], A[1], B[2], B[3]);
AtomicMultiplyBottomAdd(R+2, A[2], A[3], B[0], B[1]);
}
else
{
const unsigned int N2 = N/2;
RecursiveMultiply(R, T, A0, B0, N2);
RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
Add(R1, R1, T0, N2);
RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
Add(R1, R1, T0, N2);
}
}
// R[N] --- upper half of A*B
// T[2*N] - temporary work space
// L[N] --- lower half of A*B
// A[N] --- multiplier
// B[N] --- multiplicant
void RecursiveMultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, unsigned int N)
{
assert(N>=2 && N%2==0);
if (N==2)
{
AtomicMultiply(T, A[0], A[1], B[0], B[1]);
R[0] = T[2];
R[1] = T[3];
}
else
{
const unsigned int N2 = N/2;
int carry;
int aComp = Compare(A0, A1, N2);
int bComp = Compare(B0, B1, N2);
switch (2*aComp + aComp + bComp)
{
case -4:
Subtract(R0, A1, A0, N2);
Subtract(R1, B0, B1, N2);
RecursiveMultiply(T0, T2, R0, R1, N2);
Subtract(T1, T1, R0, N2);
carry = -1;
break;
case -2:
Subtract(R0, A1, A0, N2);
Subtract(R1, B0, B1, N2);
RecursiveMultiply(T0, T2, R0, R1, N2);
carry = 0;
break;
case 2:
Subtract(R0, A0, A1, N2);
Subtract(R1, B1, B0, N2);
RecursiveMultiply(T0, T2, R0, R1, N2);
carry = 0;
break;
case 4:
Subtract(R0, A1, A0, N2);
Subtract(R1, B0, B1, N2);
RecursiveMultiply(T0, T2, R0, R1, N2);
Subtract(T1, T1, R1, N2);
carry = -1;
break;
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -