/******************************************************************************* * Copyright 2002-2018 Intel Corporation * All Rights Reserved. * * If this software was obtained under the Intel Simplified Software License, * the following terms apply: * * The source code, information and material ("Material") contained herein is * owned by Intel Corporation or its suppliers or licensors, and title to such * Material remains with Intel Corporation or its suppliers or licensors. The * Material contains proprietary information of Intel or its suppliers and * licensors. The Material is protected by worldwide copyright laws and treaty * provisions. No part of the Material may be used, copied, reproduced, * modified, published, uploaded, posted, transmitted, distributed or disclosed * in any way without Intel's prior express written permission. No license under * any patent, copyright or other intellectual property rights in the Material * is granted to or conferred upon you, either expressly, by implication, * inducement, estoppel or otherwise. Any license under such intellectual * property rights must be express and approved by Intel in writing. * * Unless otherwise agreed by Intel in writing, you may not remove or alter this * notice or any other notice embedded in Materials by Intel or Intel's * suppliers or licensors in any way. * * * If this software was obtained under the Apache License, Version 2.0 (the * "License"), the following terms apply: * * You may not use this file except in compliance with the License. You may * obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 * * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * * See the License for the specific language governing permissions and * limitations under the License. *******************************************************************************/ /* // Intel(R) Integrated Performance Primitives // Cryptographic Primitives (ippcp) // // Contents: // ippsGcd_BN() // */ #include "owndefs.h" #include "owncp.h" #include "pcpbn.h" #include "pcptool.h" /*F* // Name: ippsGcd_BN // // Purpose: compute GCD value. // // Returns: Reason: // ippStsNullPtrErr pA == NULL // pB == NULL // pGCD == NULL // ippStsContextMatchErr !BN_VALID_ID(pA) // !BN_VALID_ID(pB) // !BN_VALID_ID(pGCD) // ippStsBadArgErr A==B==0 // ippStsOutOfRangeErr pGCD can not hold result // ippStsNoErr no errors // // Parameters: // pA source BigNum // pB source BigNum // pGCD GCD value // *F*/ IPPFUN(IppStatus, ippsGcd_BN, (IppsBigNumState* pA, IppsBigNumState* pB, IppsBigNumState* pGCD)) { IPP_BAD_PTR3_RET(pA, pB, pGCD); pA = (IppsBigNumState*)(IPP_ALIGNED_PTR(pA, BN_ALIGNMENT)); pB = (IppsBigNumState*)(IPP_ALIGNED_PTR(pB, BN_ALIGNMENT)); pGCD = (IppsBigNumState*)(IPP_ALIGNED_PTR(pGCD, BN_ALIGNMENT)); IPP_BADARG_RET(!BN_VALID_ID(pA), ippStsContextMatchErr); IPP_BADARG_RET(!BN_VALID_ID(pB), ippStsContextMatchErr); IPP_BADARG_RET(!BN_VALID_ID(pGCD), ippStsContextMatchErr); IPP_BADARG_RET(BN_ROOM(pGCD) < IPP_MIN(BN_SIZE(pA), BN_SIZE(pB)), ippStsOutOfRangeErr); { IppsBigNumState* x = pA; IppsBigNumState* y = pB; IppsBigNumState* g = pGCD; int aIsZero = BN_SIZE(pA)==1 && BN_NUMBER(pA)[0]==0; int bIsZero = BN_SIZE(pB)==1 && BN_NUMBER(pB)[0]==0; if(aIsZero && bIsZero) return ippStsBadArgErr; if(aIsZero && !bIsZero) { COPY_BNU(BN_NUMBER(g), BN_NUMBER(pB), BN_SIZE(pB)); BN_SIZE(g) = BN_SIZE(pB); BN_SIGN(g) = ippBigNumPOS; return ippStsNoErr; } if(bIsZero && !aIsZero) { COPY_BNU(BN_NUMBER(g), BN_NUMBER(pA), BN_SIZE(pA)); BN_SIZE(g) = BN_SIZE(pA); BN_SIGN(g) = ippBigNumPOS; return ippStsNoErr; } /* // Lehmer's algorithm requres that first number must be greater than second // x is the first, y is the second */ { int cmpRes = cpCmp_BNU(BN_NUMBER(x), BN_SIZE(x), BN_NUMBER(y), BN_SIZE(y)); if(0>cmpRes) SWAP_PTR(IppsBigNumState, x, y); if(0==cmpRes) { COPY_BNU(BN_NUMBER(g), BN_NUMBER(x), BN_SIZE(x)); BN_SIGN(g) = ippBigNumPOS; BN_SIZE(g) = BN_SIZE(x); return ippStsNoErr; } if(BN_SIZE(x)==1) { BNU_CHUNK_T gcd = cpGcd_BNU(BN_NUMBER(x)[0], BN_NUMBER(y)[0]); BN_NUMBER(g)[0] = gcd; BN_SIZE(g) = 1; return ippStsNoErr; } } { Ipp32u* xBuffer = (Ipp32u*)BN_BUFFER(x); Ipp32u* yBuffer = (Ipp32u*)BN_BUFFER(y); Ipp32u* gBuffer = (Ipp32u*)BN_BUFFER(g); Ipp32u* xData = (Ipp32u*)BN_NUMBER(x); Ipp32u* yData = (Ipp32u*)BN_NUMBER(y); Ipp32u* gData = (Ipp32u*)BN_NUMBER(g); cpSize nsXmax = BN_ROOM(x)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); cpSize nsYmax = BN_ROOM(y)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); cpSize nsGmax = BN_ROOM(g)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); cpSize nsX = BN_SIZE(x)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); cpSize nsY = BN_SIZE(y)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); Ipp32u* T; Ipp32u* u; FIX_BNU(xData, nsX); FIX_BNU(yData, nsY); /* init buffers */ ZEXPAND_COPY_BNU(xBuffer, nsXmax, xData, nsX); ZEXPAND_COPY_BNU(yBuffer, nsYmax, yData, nsY); T = gBuffer; u = gData; ZEXPAND_BNU(T, 0, nsGmax); ZEXPAND_BNU(u, 0, nsGmax); while(nsX > (cpSize)(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u))) { /* xx and yy is the high-order digits of x and y (yy could be 0) */ Ipp64u xx = (Ipp64u)(xBuffer[nsX-1]); Ipp64u yy = (nsY < nsX)? 0 : (Ipp64u)(yBuffer[nsY-1]); Ipp64s AA = 1; Ipp64s BB = 0; Ipp64s CC = 0; Ipp64s DD = 1; Ipp64s t; while((yy+CC)!=0 && (yy+DD)!=0) { Ipp64u q = ( xx + AA ) / ( yy + CC ); Ipp64u q1 = ( xx + BB ) / ( yy + DD ); if(q!=q1) break; t = AA - q*CC; AA = CC; CC = t; t = BB - q*DD; BB = DD; DD = t; t = xx - q*yy; xx = yy; yy = t; } if(BB == 0) { /* T = x mod y */ cpSize nsT = cpMod_BNU32(xBuffer, nsX, yBuffer, nsY); ZEXPAND_BNU(T, 0, nsGmax); COPY_BNU(T, xBuffer, nsT); /* a = b; b = T; */ ZEXPAND_BNU(xBuffer, 0, nsXmax); COPY_BNU(xBuffer, yBuffer, nsY); ZEXPAND_BNU(yBuffer, 0, nsYmax); COPY_BNU(yBuffer, T, nsY); } else { Ipp32u carry; /* // T = AA*x + BB*y; // u = CC*x + DD*y; // b = u; a = T; */ if((AA <= 0)&&(BB>=0)) { Ipp32u a1 = (Ipp32u)(-AA); carry = cpMulDgt_BNU32(T, yBuffer, nsY, (Ipp32u)BB); carry = cpMulDgt_BNU32(u, xBuffer, nsY, a1); /* T = BB*y - AA*x; */ carry = cpSub_BNU32(T, T, u, nsY); } else { if((AA >= 0)&&(BB<=0)) { Ipp32u b1 = (Ipp32u)(-BB); carry = cpMulDgt_BNU32(T, xBuffer, nsY, (Ipp32u)AA); carry = cpMulDgt_BNU32(u, yBuffer, nsY, b1); /* T = AA*x - BB*y; */ carry = cpSub_BNU32(T, T, u, nsY); } else { /*AA*BB>=0 */ carry = cpMulDgt_BNU32(T, xBuffer, nsY, (Ipp32u)AA); carry = cpMulDgt_BNU32(u, yBuffer, nsY, (Ipp32u)BB); /* T = AA*x + BB*y; */ carry = cpAdd_BNU32(T, T, u, nsY); } } /* Now T is reserved. We use only u for intermediate results. */ if((CC <= 0)&&(DD>=0)){ Ipp32u c1 = (Ipp32u)(-CC); /* u = x*CC; x = u; */ carry = cpMulDgt_BNU32(u, xBuffer, nsY, c1); COPY_BNU(xBuffer, u, nsY); /* u = y*DD; */ carry = cpMulDgt_BNU32(u, yBuffer, nsY, (Ipp32u)DD); /* u = DD*y - CC*x; */ carry = cpSub_BNU32(u, u, xBuffer, nsY); } else { if((CC >= 0)&&(DD<=0)){ Ipp32u d1 = (Ipp32u)(-DD); /* u = y*DD; y = u */ carry = cpMulDgt_BNU32(u, yBuffer, nsY, d1); COPY_BNU(yBuffer, u, nsY); /* u = CC*x; */ carry = cpMulDgt_BNU32(u, xBuffer, nsY, (Ipp32u)CC); /* u = CC*x - DD*y; */ carry = cpSub_BNU32(u, u, yBuffer, nsY); } else { /*CC*DD>=0 */ /* y = y*DD */ carry = cpMulDgt_BNU32(u, yBuffer, nsY, (Ipp32u)DD); COPY_BNU(yBuffer, u, nsY); /* u = x*CC */ carry = cpMulDgt_BNU32(u, xBuffer, nsY, (Ipp32u)CC); /* u = x*CC + y*DD */ carry = cpAdd_BNU32(u, u, yBuffer, nsY); } } /* y = u; x = T; */ COPY_BNU(yBuffer, u, nsY); COPY_BNU(xBuffer, T, nsY); } FIX_BNU(xBuffer, nsX); FIX_BNU(yBuffer, nsY); if (nsY > nsX) { SWAP_PTR(IppsBigNumState, x, y); SWAP(nsX, nsY); } if (nsY==1 && yBuffer[nsY-1]==0) { /* End evaluation */ ZEXPAND_BNU(gData, 0, nsGmax); COPY_BNU(gData, xBuffer, nsX); BN_SIZE(g) = INTERNAL_BNU_LENGTH(nsX); BN_SIGN(g) = ippBigNumPOS; return ippStsNoErr; } } BN_NUMBER(g)[0] = cpGcd_BNU(((BNU_CHUNK_T*)xBuffer)[0], ((BNU_CHUNK_T*)yBuffer)[0]); BN_SIZE(g) = 1; BN_SIGN(g) = ippBigNumPOS; return ippStsNoErr; } } }