| /******************************************************************************* |
| * 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; |
| } |
| } |
| } |
