1 /******************************************************************************* 2 * Copyright 2002-2018 Intel Corporation 3 * All Rights Reserved. 4 * 5 * If this software was obtained under the Intel Simplified Software License, 6 * the following terms apply: 7 * 8 * The source code, information and material ("Material") contained herein is 9 * owned by Intel Corporation or its suppliers or licensors, and title to such 10 * Material remains with Intel Corporation or its suppliers or licensors. The 11 * Material contains proprietary information of Intel or its suppliers and 12 * licensors. The Material is protected by worldwide copyright laws and treaty 13 * provisions. No part of the Material may be used, copied, reproduced, 14 * modified, published, uploaded, posted, transmitted, distributed or disclosed 15 * in any way without Intel's prior express written permission. No license under 16 * any patent, copyright or other intellectual property rights in the Material 17 * is granted to or conferred upon you, either expressly, by implication, 18 * inducement, estoppel or otherwise. Any license under such intellectual 19 * property rights must be express and approved by Intel in writing. 20 * 21 * Unless otherwise agreed by Intel in writing, you may not remove or alter this 22 * notice or any other notice embedded in Materials by Intel or Intel's 23 * suppliers or licensors in any way. 24 * 25 * 26 * If this software was obtained under the Apache License, Version 2.0 (the 27 * "License"), the following terms apply: 28 * 29 * You may not use this file except in compliance with the License. You may 30 * obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 31 * 32 * 33 * Unless required by applicable law or agreed to in writing, software 34 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 35 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 36 * 37 * See the License for the specific language governing permissions and 38 * limitations under the License. 39 *******************************************************************************/ 40 41 /* 42 // Intel(R) Integrated Performance Primitives 43 // Cryptographic Primitives (ippcp) 44 // 45 // Contents: 46 // ippsGcd_BN() 47 // 48 */ 49 50 #include "owndefs.h" 51 #include "owncp.h" 52 #include "pcpbn.h" 53 #include "pcptool.h" 54 55 56 /*F* 57 // Name: ippsGcd_BN 58 // 59 // Purpose: compute GCD value. 60 // 61 // Returns: Reason: 62 // ippStsNullPtrErr pA == NULL 63 // pB == NULL 64 // pGCD == NULL 65 // ippStsContextMatchErr !BN_VALID_ID(pA) 66 // !BN_VALID_ID(pB) 67 // !BN_VALID_ID(pGCD) 68 // ippStsBadArgErr A==B==0 69 // ippStsOutOfRangeErr pGCD can not hold result 70 // ippStsNoErr no errors 71 // 72 // Parameters: 73 // pA source BigNum 74 // pB source BigNum 75 // pGCD GCD value 76 // 77 *F*/ 78 IPPFUN(IppStatus, ippsGcd_BN, (IppsBigNumState* pA, IppsBigNumState* pB, IppsBigNumState* pGCD)) 79 { 80 IPP_BAD_PTR3_RET(pA, pB, pGCD); 81 82 pA = (IppsBigNumState*)(IPP_ALIGNED_PTR(pA, BN_ALIGNMENT)); 83 pB = (IppsBigNumState*)(IPP_ALIGNED_PTR(pB, BN_ALIGNMENT)); 84 pGCD = (IppsBigNumState*)(IPP_ALIGNED_PTR(pGCD, BN_ALIGNMENT)); 85 IPP_BADARG_RET(!BN_VALID_ID(pA), ippStsContextMatchErr); 86 IPP_BADARG_RET(!BN_VALID_ID(pB), ippStsContextMatchErr); 87 IPP_BADARG_RET(!BN_VALID_ID(pGCD), ippStsContextMatchErr); 88 89 IPP_BADARG_RET(BN_ROOM(pGCD) < IPP_MIN(BN_SIZE(pA), BN_SIZE(pB)), ippStsOutOfRangeErr); 90 91 { 92 IppsBigNumState* x = pA; 93 IppsBigNumState* y = pB; 94 IppsBigNumState* g = pGCD; 95 96 int aIsZero = BN_SIZE(pA)==1 && BN_NUMBER(pA)[0]==0; 97 int bIsZero = BN_SIZE(pB)==1 && BN_NUMBER(pB)[0]==0; 98 99 if(aIsZero && bIsZero) 100 return ippStsBadArgErr; 101 if(aIsZero && !bIsZero) { 102 COPY_BNU(BN_NUMBER(g), BN_NUMBER(pB), BN_SIZE(pB)); 103 BN_SIZE(g) = BN_SIZE(pB); 104 BN_SIGN(g) = ippBigNumPOS; 105 return ippStsNoErr; 106 } 107 if(bIsZero && !aIsZero) { 108 COPY_BNU(BN_NUMBER(g), BN_NUMBER(pA), BN_SIZE(pA)); 109 BN_SIZE(g) = BN_SIZE(pA); 110 BN_SIGN(g) = ippBigNumPOS; 111 return ippStsNoErr; 112 } 113 114 /* 115 // Lehmer's algorithm requres that first number must be greater than second 116 // x is the first, y is the second 117 */ 118 { 119 int cmpRes = cpCmp_BNU(BN_NUMBER(x), BN_SIZE(x), BN_NUMBER(y), BN_SIZE(y)); 120 if(0>cmpRes) 121 SWAP_PTR(IppsBigNumState, x, y); 122 if(0==cmpRes) { 123 COPY_BNU(BN_NUMBER(g), BN_NUMBER(x), BN_SIZE(x)); 124 BN_SIGN(g) = ippBigNumPOS; 125 BN_SIZE(g) = BN_SIZE(x); 126 return ippStsNoErr; 127 } 128 if(BN_SIZE(x)==1) { 129 BNU_CHUNK_T gcd = cpGcd_BNU(BN_NUMBER(x)[0], BN_NUMBER(y)[0]); 130 BN_NUMBER(g)[0] = gcd; 131 BN_SIZE(g) = 1; 132 return ippStsNoErr; 133 } 134 } 135 136 { 137 Ipp32u* xBuffer = (Ipp32u*)BN_BUFFER(x); 138 Ipp32u* yBuffer = (Ipp32u*)BN_BUFFER(y); 139 Ipp32u* gBuffer = (Ipp32u*)BN_BUFFER(g); 140 Ipp32u* xData = (Ipp32u*)BN_NUMBER(x); 141 Ipp32u* yData = (Ipp32u*)BN_NUMBER(y); 142 Ipp32u* gData = (Ipp32u*)BN_NUMBER(g); 143 cpSize nsXmax = BN_ROOM(x)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); 144 cpSize nsYmax = BN_ROOM(y)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); 145 cpSize nsGmax = BN_ROOM(g)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); 146 cpSize nsX = BN_SIZE(x)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); 147 cpSize nsY = BN_SIZE(y)*(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u)); 148 149 Ipp32u* T; 150 Ipp32u* u; 151 152 FIX_BNU(xData, nsX); 153 FIX_BNU(yData, nsY); 154 155 /* init buffers */ 156 ZEXPAND_COPY_BNU(xBuffer, nsXmax, xData, nsX); 157 ZEXPAND_COPY_BNU(yBuffer, nsYmax, yData, nsY); 158 159 T = gBuffer; 160 u = gData; 161 ZEXPAND_BNU(T, 0, nsGmax); 162 ZEXPAND_BNU(u, 0, nsGmax); 163 164 while(nsX > (cpSize)(sizeof(BNU_CHUNK_T)/sizeof(Ipp32u))) { 165 /* xx and yy is the high-order digits of x and y (yy could be 0) */ 166 167 Ipp64u xx = (Ipp64u)(xBuffer[nsX-1]); 168 Ipp64u yy = (nsY < nsX)? 0 : (Ipp64u)(yBuffer[nsY-1]); 169 170 Ipp64s AA = 1; 171 Ipp64s BB = 0; 172 Ipp64s CC = 0; 173 Ipp64s DD = 1; 174 Ipp64s t; 175 176 while((yy+CC)!=0 && (yy+DD)!=0) { 177 Ipp64u q = ( xx + AA ) / ( yy + CC ); 178 Ipp64u q1 = ( xx + BB ) / ( yy + DD ); 179 if(q!=q1) 180 break; 181 t = AA - q*CC; 182 AA = CC; 183 CC = t; 184 t = BB - q*DD; 185 BB = DD; 186 DD = t; 187 t = xx - q*yy; 188 xx = yy; 189 yy = t; 190 } 191 192 if(BB == 0) { 193 /* T = x mod y */ 194 cpSize nsT = cpMod_BNU32(xBuffer, nsX, yBuffer, nsY); 195 ZEXPAND_BNU(T, 0, nsGmax); 196 COPY_BNU(T, xBuffer, nsT); 197 /* a = b; b = T; */ 198 ZEXPAND_BNU(xBuffer, 0, nsXmax); 199 COPY_BNU(xBuffer, yBuffer, nsY); 200 ZEXPAND_BNU(yBuffer, 0, nsYmax); 201 COPY_BNU(yBuffer, T, nsY); 202 } 203 204 else { 205 Ipp32u carry; 206 /* 207 // T = AA*x + BB*y; 208 // u = CC*x + DD*y; 209 // b = u; a = T; 210 */ 211 if((AA <= 0)&&(BB>=0)) { 212 Ipp32u a1 = (Ipp32u)(-AA); 213 carry = cpMulDgt_BNU32(T, yBuffer, nsY, (Ipp32u)BB); 214 carry = cpMulDgt_BNU32(u, xBuffer, nsY, a1); 215 /* T = BB*y - AA*x; */ 216 carry = cpSub_BNU32(T, T, u, nsY); 217 } 218 else { 219 if((AA >= 0)&&(BB<=0)) { 220 Ipp32u b1 = (Ipp32u)(-BB); 221 carry = cpMulDgt_BNU32(T, xBuffer, nsY, (Ipp32u)AA); 222 carry = cpMulDgt_BNU32(u, yBuffer, nsY, b1); 223 /* T = AA*x - BB*y; */ 224 carry = cpSub_BNU32(T, T, u, nsY); 225 } 226 else { 227 /*AA*BB>=0 */ 228 carry = cpMulDgt_BNU32(T, xBuffer, nsY, (Ipp32u)AA); 229 carry = cpMulDgt_BNU32(u, yBuffer, nsY, (Ipp32u)BB); 230 /* T = AA*x + BB*y; */ 231 carry = cpAdd_BNU32(T, T, u, nsY); 232 } 233 } 234 235 /* Now T is reserved. We use only u for intermediate results. */ 236 if((CC <= 0)&&(DD>=0)){ 237 Ipp32u c1 = (Ipp32u)(-CC); 238 /* u = x*CC; x = u; */ 239 carry = cpMulDgt_BNU32(u, xBuffer, nsY, c1); 240 COPY_BNU(xBuffer, u, nsY); 241 /* u = y*DD; */ 242 carry = cpMulDgt_BNU32(u, yBuffer, nsY, (Ipp32u)DD); 243 /* u = DD*y - CC*x; */ 244 carry = cpSub_BNU32(u, u, xBuffer, nsY); 245 } 246 else { 247 if((CC >= 0)&&(DD<=0)){ 248 Ipp32u d1 = (Ipp32u)(-DD); 249 /* u = y*DD; y = u */ 250 carry = cpMulDgt_BNU32(u, yBuffer, nsY, d1); 251 COPY_BNU(yBuffer, u, nsY); 252 /* u = CC*x; */ 253 carry = cpMulDgt_BNU32(u, xBuffer, nsY, (Ipp32u)CC); 254 /* u = CC*x - DD*y; */ 255 carry = cpSub_BNU32(u, u, yBuffer, nsY); 256 } 257 else { 258 /*CC*DD>=0 */ 259 /* y = y*DD */ 260 carry = cpMulDgt_BNU32(u, yBuffer, nsY, (Ipp32u)DD); 261 COPY_BNU(yBuffer, u, nsY); 262 /* u = x*CC */ 263 carry = cpMulDgt_BNU32(u, xBuffer, nsY, (Ipp32u)CC); 264 /* u = x*CC + y*DD */ 265 carry = cpAdd_BNU32(u, u, yBuffer, nsY); 266 } 267 } 268 269 /* y = u; x = T; */ 270 COPY_BNU(yBuffer, u, nsY); 271 COPY_BNU(xBuffer, T, nsY); 272 } 273 274 FIX_BNU(xBuffer, nsX); 275 FIX_BNU(yBuffer, nsY); 276 277 if (nsY > nsX) { 278 SWAP_PTR(IppsBigNumState, x, y); 279 SWAP(nsX, nsY); 280 } 281 282 if (nsY==1 && yBuffer[nsY-1]==0) { 283 /* End evaluation */ 284 ZEXPAND_BNU(gData, 0, nsGmax); 285 COPY_BNU(gData, xBuffer, nsX); 286 BN_SIZE(g) = INTERNAL_BNU_LENGTH(nsX); 287 BN_SIGN(g) = ippBigNumPOS; 288 return ippStsNoErr; 289 } 290 } 291 292 BN_NUMBER(g)[0] = cpGcd_BNU(((BNU_CHUNK_T*)xBuffer)[0], ((BNU_CHUNK_T*)yBuffer)[0]); 293 BN_SIZE(g) = 1; 294 BN_SIGN(g) = ippBigNumPOS; 295 return ippStsNoErr; 296 } 297 } 298 } 299