LXR linux/drivers/staging/rt3090/common/crypt

   1/*
   2 *************************************************************************
   3 * Ralink Tech Inc.
   4 * 5F., No.36, Taiyuan St., Jhubei City,
   5 * Hsinchu County 302,
   6 * Taiwan, R.O.C.
   7 *
   8 * (c) Copyright 2002-2007, Ralink Technology, Inc.
   9 *
  10 * This program is free software; you can redistribute it and/or modify  *
  11 * it under the terms of the GNU General Public License as published by  *
  12 * the Free Software Foundation; either version 2 of the License, or     *
  13 * (at your option) any later version.                                   *
  14 *                                                                       *
  15 * This program is distributed in the hope that it will be useful,       *
  16 * but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  18 * GNU General Public License for more details.                          *
  19 *                                                                       *
  20 * You should have received a copy of the GNU General Public License     *
  21 * along with this program; if not, write to the                         *
  22 * Free Software Foundation, Inc.,                                       *
  23 * 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
  24 *                                                                       *
  25 *************************************************************************
  26
  27    Module Name:
  28        cmm_profile.c
  29
  30    Abstract:
  31
  32    Revision History:
  33    Who          When          What
  34    ---------    ----------    ----------------------------------------------
  35 */
  36
  37#include "crypt_biginteger.h"
  38
  39#ifdef __KERNEL__
  40#define DEBUGPRINT(fmt, args...) printk(KERN_ERR fmt, ## args)
  41#else
  42#define DEBUGPRINT(fmt, args...) printf(fmt, ## args)
  43#endif /* __KERNEL__ */
  44
  45#define UINT32_HBITS(value)     (((value) >> 0x10) & 0xffff)
  46#define UINT32_LBITS(value)     ((value) & 0xffff)
  47#define UINT32_GETBYTE(value, index)    (((value) >> ((index)*8)) & 0xff)
  48#define UINT64_HBITS(value)     (((value) >> 0x20) & 0xffffffff)
  49#define UINT64_LBITS(value)     ((value) & 0xffffffff)
  50
  51static UINT8 WPS_DH_P_VALUE[192] =
  52{
  53    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  54    0xC9, 0x0F, 0xDA, 0xA2, 0x21, 0x68, 0xC2, 0x34,
  55    0xC4, 0xC6, 0x62, 0x8B, 0x80, 0xDC, 0x1C, 0xD1,
  56    0x29, 0x02, 0x4E, 0x08, 0x8A, 0x67, 0xCC, 0x74,
  57    0x02, 0x0B, 0xBE, 0xA6, 0x3B, 0x13, 0x9B, 0x22,
  58    0x51, 0x4A, 0x08, 0x79, 0x8E, 0x34, 0x04, 0xDD,
  59    0xEF, 0x95, 0x19, 0xB3, 0xCD, 0x3A, 0x43, 0x1B,
  60    0x30, 0x2B, 0x0A, 0x6D, 0xF2, 0x5F, 0x14, 0x37,
  61    0x4F, 0xE1, 0x35, 0x6D, 0x6D, 0x51, 0xC2, 0x45,
  62    0xE4, 0x85, 0xB5, 0x76, 0x62, 0x5E, 0x7E, 0xC6,
  63    0xF4, 0x4C, 0x42, 0xE9, 0xA6, 0x37, 0xED, 0x6B,
  64    0x0B, 0xFF, 0x5C, 0xB6, 0xF4, 0x06, 0xB7, 0xED,
  65    0xEE, 0x38, 0x6B, 0xFB, 0x5A, 0x89, 0x9F, 0xA5,
  66    0xAE, 0x9F, 0x24, 0x11, 0x7C, 0x4B, 0x1F, 0xE6,
  67    0x49, 0x28, 0x66, 0x51, 0xEC, 0xE4, 0x5B, 0x3D,
  68    0xC2, 0x00, 0x7C, 0xB8, 0xA1, 0x63, 0xBF, 0x05,
  69    0x98, 0xDA, 0x48, 0x36, 0x1C, 0x55, 0xD3, 0x9A,
  70    0x69, 0x16, 0x3F, 0xA8, 0xFD, 0x24, 0xCF, 0x5F,
  71    0x83, 0x65, 0x5D, 0x23, 0xDC, 0xA3, 0xAD, 0x96,
  72    0x1C, 0x62, 0xF3, 0x56, 0x20, 0x85, 0x52, 0xBB,
  73    0x9E, 0xD5, 0x29, 0x07, 0x70, 0x96, 0x96, 0x6D,
  74    0x67, 0x0C, 0x35, 0x4E, 0x4A, 0xBC, 0x98, 0x04,
  75    0xF1, 0x74, 0x6C, 0x08, 0xCA, 0x23, 0x73, 0x27,
  76    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
  77};
  78
  79static UINT8 WPS_DH_R_VALUE[193] =
  80{
  81    0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  82    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  83    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  84    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  85    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  86    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  87    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  88    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  89    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  90    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  91    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  92    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  93    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  94    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  95    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  96    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  97    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  98    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  99    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 100    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 101    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 102    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 103    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 104    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 105    0x00,
 106};
 107
 108static UINT8 WPS_DH_X_VALUE[184] =
 109{
 110    0x36, 0xf0, 0x25, 0x5d, 0xde, 0x97, 0x3d, 0xcb,
 111    0x3b, 0x39, 0x9d, 0x74, 0x7f, 0x23, 0xe3, 0x2e,
 112    0xd6, 0xfd, 0xb1, 0xf7, 0x75, 0x98, 0x33, 0x8b,
 113    0xfd, 0xf4, 0x41, 0x59, 0xc4, 0xec, 0x64, 0xdd,
 114    0xae, 0xb5, 0xf7, 0x86, 0x71, 0xcb, 0xfb, 0x22,
 115    0x10, 0x6a, 0xe6, 0x4c, 0x32, 0xc5, 0xbc, 0xe4,
 116    0xcf, 0xd4, 0xf5, 0x92, 0x0d, 0xa0, 0xeb, 0xc8,
 117    0xb0, 0x1e, 0xca, 0x92, 0x92, 0xae, 0x3d, 0xba,
 118    0x1b, 0x7a, 0x4a, 0x89, 0x9d, 0xa1, 0x81, 0x39,
 119    0x0b, 0xb3, 0xbd, 0x16, 0x59, 0xc8, 0x12, 0x94,
 120    0xf4, 0x00, 0xa3, 0x49, 0x0b, 0xf9, 0x48, 0x12,
 121    0x11, 0xc7, 0x94, 0x04, 0xa5, 0x76, 0x60, 0x5a,
 122    0x51, 0x60, 0xdb, 0xee, 0x83, 0xb4, 0xe0, 0x19,
 123    0xb6, 0xd7, 0x99, 0xae, 0x13, 0x1b, 0xa4, 0xc2,
 124    0x3d, 0xff, 0x83, 0x47, 0x5e, 0x9c, 0x40, 0xfa,
 125    0x67, 0x25, 0xb7, 0xc9, 0xe3, 0xaa, 0x2c, 0x65,
 126    0x96, 0xe9, 0xc0, 0x57, 0x02, 0xdb, 0x30, 0xa0,
 127    0x7c, 0x9a, 0xa2, 0xdc, 0x23, 0x5c, 0x52, 0x69,
 128    0xe3, 0x9d, 0x0c, 0xa9, 0xdf, 0x7a, 0xad, 0x44,
 129    0x61, 0x2a, 0xd6, 0xf8, 0x8f, 0x69, 0x69, 0x92,
 130    0x98, 0xf3, 0xca, 0xb1, 0xb5, 0x43, 0x67, 0xfb,
 131    0x0e, 0x8b, 0x93, 0xf7, 0x35, 0xdc, 0x8c, 0xd8,
 132    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
 133};
 134
 135static UINT8 WPS_DH_RRModP_VALUE[192] =
 136{
 137        0xe3, 0xb3, 0x3c, 0x72, 0x59, 0x54, 0x1c, 0x01,
 138        0xee, 0x9c, 0x9a, 0x21, 0x6c, 0xc1, 0xeb, 0xd2,
 139        0xae, 0x59, 0x41, 0x04, 0x79, 0x29, 0xa1, 0xc7,
 140        0xe9, 0xc3, 0xfa, 0x02, 0xcc, 0x24, 0x56, 0xef,
 141        0x10, 0x26, 0x30, 0xfa, 0x9a, 0x36, 0xa5, 0x1f,
 142        0x57, 0xb5, 0x93, 0x48, 0x67, 0x98, 0x44, 0x60,
 143        0x0b, 0xe4, 0x96, 0x47, 0xa8, 0x7c, 0x7b, 0x37,
 144        0xf8, 0x05, 0x65, 0x64, 0x96, 0x9b, 0x7f, 0x02,
 145        0xdc, 0x54, 0x1a, 0x4e, 0xd4, 0x05, 0x3f, 0x54,
 146        0xd6, 0x2a, 0x0e, 0xea, 0xb2, 0x70, 0x52, 0x1b,
 147        0x22, 0xc2, 0x96, 0xe9, 0xd4, 0x6f, 0xec, 0x23,
 148        0x8e, 0x1a, 0xbd, 0x78, 0x02, 0x23, 0xb7, 0x6b,
 149        0xb8, 0xfe, 0x61, 0x21, 0x19, 0x6b, 0x7e, 0x88,
 150        0x1c, 0x72, 0x9c, 0x7e, 0x04, 0xb9, 0xf7, 0x96,
 151        0x07, 0xcd, 0x0a, 0x62, 0x8e, 0x43, 0x41, 0x30,
 152        0x04, 0xa5, 0x41, 0xff, 0x93, 0xae, 0x1c, 0xeb,
 153        0xb0, 0x04, 0xa7, 0x50, 0xdb, 0x10, 0x2d, 0x39,
 154        0xb9, 0x05, 0x2b, 0xb4, 0x7a, 0x58, 0xf1, 0x70,
 155        0x7e, 0x8c, 0xd2, 0xac, 0x98, 0xb5, 0xfb, 0x62,
 156        0x8f, 0x23, 0x31, 0xb1, 0x3b, 0x01, 0xe0, 0x18,
 157        0xf4, 0x66, 0xee, 0x5f, 0xbc, 0xd4, 0x9d, 0x68,
 158        0xd0, 0xab, 0x92, 0xe1, 0x83, 0x97, 0xf2, 0x45,
 159        0x8e, 0x0e, 0x3e, 0x21, 0x67, 0x47, 0x8c, 0x73,
 160        0xf1, 0x15, 0xd2, 0x7d, 0x32, 0xc6, 0x95, 0xe0,
 161};
 162
 163static UINT8 Value_0[1] = {0x00};
 164static UINT8 Value_1[1] = {0x01};
 165static PBIG_INTEGER pBI_U = NULL, pBI_S = NULL, pBI_O = NULL;
 166static UINT Bits_Of_R = 0;
 167
 168
 169VOID BigInteger_Print (
 170    IN PBIG_INTEGER pBI)
 171{
 172    int i = 0, j = 0;
 173
 174    if ((pBI == NULL) || (pBI->pIntegerArray == NULL))
 175        return;
 176
 177    if (strlen(pBI->Name) != 0)
 178        DEBUGPRINT("Name=%s\n", pBI->Name);
 179    DEBUGPRINT("AllocSize=%d, ArrayLength=%d, IntegerLength=%d, Signed=%d\n", pBI->AllocSize, pBI->ArrayLength, pBI->IntegerLength, pBI->Signed);
 180    for (i = (pBI->ArrayLength - 1), j = 0;i >=0;i--,j++) {
 181        DEBUGPRINT("%08x, ", pBI->pIntegerArray[i]);
 182        if ((j%8) == 7)
 183            DEBUGPRINT("\n");
 184    } /* End od for */
 185    DEBUGPRINT("\n\n");
 186} /* End of BigInteger_Print */
 187
 188
 189VOID BigInteger_Init (
 190    INOUT PBIG_INTEGER *pBI)
 191{
 192    if (*pBI != NULL)
 193        BigInteger_Free(pBI);
 194
 195    if ((*pBI = (PBIG_INTEGER) kmalloc(sizeof(BIG_INTEGER), GFP_ATOMIC)) == NULL) {
 196        DEBUGPRINT("BigInteger_Init: allocate %d bytes memory failure.\n", (sizeof(BIG_INTEGER)));
 197        return;
 198    } /* End of if */
 199
 200    NdisZeroMemory(*pBI, sizeof(BIG_INTEGER));
 201    (*pBI)->pIntegerArray = NULL;
 202    (*pBI)->Signed = 1;
 203} /* End of BigInteger_Init */
 204
 205
 206VOID BigInteger_Free_AllocSize (
 207    IN PBIG_INTEGER *pBI)
 208{
 209    if ((*pBI != NULL) && ((*pBI)->pIntegerArray != NULL)) {
 210        kfree((*pBI)->pIntegerArray);
 211        NdisZeroMemory(*pBI, sizeof(BIG_INTEGER));
 212        (*pBI)->pIntegerArray = NULL;
 213        (*pBI)->Signed = 1;
 214    } /* End of if */
 215} /* End of BigInteger_Free_AllocSize */
 216
 217
 218VOID BigInteger_Free (
 219    IN PBIG_INTEGER *pBI)
 220{
 221    if (*pBI != NULL) {
 222        BigInteger_Free_AllocSize(pBI);
 223        kfree(*pBI);
 224    } /* End of if */
 225
 226    *pBI = NULL;
 227} /* End of BigInteger_Free */
 228
 229
 230VOID BigInteger_AllocSize (
 231    IN PBIG_INTEGER *pBI,
 232    IN UINT Length)
 233{
 234    UINT ArrayLength = 0;
 235
 236    if (Length == 0)
 237        return;
 238
 239    if (*pBI == NULL)
 240        BigInteger_Init(pBI);
 241
 242    /* Caculate array size */
 243    ArrayLength = Length >> 0x2;
 244    if ((Length & 0x3) != 0)
 245        ArrayLength++;
 246
 247    if (((*pBI)->pIntegerArray != NULL) && ((*pBI)->AllocSize < (sizeof(UINT32)*ArrayLength)))
 248        BigInteger_Free_AllocSize(pBI);
 249
 250    if ((*pBI)->pIntegerArray == NULL) {
 251        if (((*pBI)->pIntegerArray = (UINT32 *) kmalloc(sizeof(UINT32)*ArrayLength, GFP_ATOMIC)) == NULL) {
 252            DEBUGPRINT("BigInteger_AllocSize: allocate %d bytes memory failure.\n", (sizeof(UINT32)*ArrayLength));
 253            return;
 254        } /* End of if */
 255        (*pBI)->AllocSize = sizeof(UINT32)*ArrayLength;
 256    } /* End of if */
 257
 258    NdisZeroMemory((*pBI)->pIntegerArray, (*pBI)->AllocSize);
 259    (*pBI)->ArrayLength = ArrayLength;
 260    (*pBI)->IntegerLength = Length;
 261} /* End of BigInteger_AllocSize */
 262
 263
 264VOID BigInteger_ClearHighBits (
 265    IN PBIG_INTEGER pBI)
 266{
 267    INT BIArrayIndex, ShiftIndex = 0;
 268    UINT8 value;
 269
 270    if ((pBI == NULL) || (pBI->pIntegerArray == NULL))
 271        return;
 272
 273    BIArrayIndex = pBI->ArrayLength - 1;
 274    while ((BIArrayIndex >= 0) && (pBI->pIntegerArray[BIArrayIndex] == 0))
 275        BIArrayIndex--;
 276
 277    if (BIArrayIndex >= 0) {
 278        value = 0;
 279        ShiftIndex = 4;
 280        while (value == 0) {
 281            ShiftIndex--;
 282            value = UINT32_GETBYTE(pBI->pIntegerArray[BIArrayIndex], ShiftIndex);
 283        } /* End of while */
 284    } /* End of if */
 285
 286    if ((BIArrayIndex == -1) && (ShiftIndex == -1)) {
 287        pBI->IntegerLength = 1;
 288        pBI->ArrayLength = 1;
 289        pBI->Signed = 1;
 290    } else {
 291        pBI->IntegerLength = (BIArrayIndex*4) + ShiftIndex + 1;
 292        pBI->ArrayLength = BIArrayIndex + 1;
 293    } /* End of if */
 294} /* End of BigInteger_ClearHighBits */
 295
 296
 297VOID BigInteger_BI2Bin (
 298    IN PBIG_INTEGER pBI,
 299    OUT UINT8 *pValue,
 300    OUT UINT *Length)
 301{
 302    INT  ValueIndex, BIArrayIndex, ShiftIndex;
 303    UINT32  Number;
 304
 305    if (pBI == NULL) {
 306        DEBUGPRINT("BigInteger_BI2Bin: pBI is NUll\n");
 307        *Length = 0;
 308        return;
 309    } /* End of if */
 310
 311    if (*Length < (sizeof(UINT8) * pBI->IntegerLength)) {
 312        DEBUGPRINT("BigInteger_BI2Bin: length(%d) is not enough.\n", *Length);
 313        *Length = 0;
 314        return;
 315    } /* End of if */
 316
 317    if (pBI->pIntegerArray == NULL) {
 318        *Length = 0;
 319        return;
 320    } /* End of if */
 321
 322    BigInteger_ClearHighBits(pBI);
 323    if ((ShiftIndex = pBI->IntegerLength & 0x3) == 0)
 324       ShiftIndex = 4;
 325    BIArrayIndex = pBI->ArrayLength - 1;
 326    ValueIndex = 0;
 327
 328    Number = pBI->pIntegerArray[BIArrayIndex];
 329    while (ValueIndex < pBI->IntegerLength)
 330    {
 331        pValue[ValueIndex++] = (UINT8) UINT32_GETBYTE(Number, ShiftIndex - 1);
 332        if ((--ShiftIndex) == 0) {
 333            ShiftIndex = 4;
 334            BIArrayIndex--;
 335            Number = pBI->pIntegerArray[BIArrayIndex];
 336        } /* End of if */
 337    } /* End of while */
 338    *Length = pBI->IntegerLength;
 339} /* End of BigInteger_BI2Bin */
 340
 341
 342VOID BigInteger_Bin2BI (
 343    IN UINT8 *pValue,
 344    IN UINT Length,
 345    OUT PBIG_INTEGER *pBI)
 346{
 347    INT  ValueIndex, BIArrayIndex, ShiftIndex;
 348    UINT32  Number;
 349
 350    BigInteger_AllocSize(pBI, Length);
 351
 352    if ((*pBI)->pIntegerArray != NULL) {
 353        Number = 0;
 354        if ((ShiftIndex = Length & 0x3) == 0)
 355            ShiftIndex = 4;
 356        BIArrayIndex = (*pBI)->ArrayLength - 1;
 357        ValueIndex = 0;
 358        while (ValueIndex < Length)
 359        {
 360            Number = (Number << 8) | (UINT8) pValue[ValueIndex++];
 361            if ((--ShiftIndex) == 0) {
 362                (*pBI)->pIntegerArray[BIArrayIndex] = Number;
 363                ShiftIndex = 4;
 364                BIArrayIndex--;
 365                Number = 0;
 366            } /* End of if */
 367        } /* End of while */
 368    } /* End of if */
 369} /* End of BigInteger_Bin2BI */
 370
 371
 372/* Calculate the bits of BigInteger, the highest bit is 1 */
 373VOID BigInteger_BitsOfBI (
 374    IN PBIG_INTEGER pBI,
 375    OUT UINT *Bits_Of_P)
 376{
 377    UINT32 Number, Index;
 378
 379    Number = pBI->pIntegerArray[pBI->ArrayLength - 1];
 380    Index = 0;
 381    while ((!(Number & 0x80000000)) && (Index < 32)) {
 382        Number <<= 1;
 383        Index++;
 384    } /* End of while */
 385    *Bits_Of_P = (pBI->ArrayLength*sizeof(UINT32)) - Index;
 386} /* End of BigInteger_BitsOfBN */
 387
 388
 389INT BigInteger_GetBitValue (
 390    IN PBIG_INTEGER pBI,
 391    IN UINT Index)
 392{
 393    UINT Array = 0;
 394    UINT Shift = 0;
 395
 396    if (Index > 0) {
 397        Array = (Index - 1) >> 0x5;
 398        Shift = (Index - 1) & 0x1F;
 399    }
 400    if (Array > pBI->ArrayLength)
 401        return 0;
 402
 403    return ((pBI->pIntegerArray[Array] >> Shift) & 0x1);
 404} /* End of BigInteger_GetBitValue */
 405
 406
 407UINT8 BigInteger_GetByteValue (
 408    IN PBIG_INTEGER pBI,
 409    IN UINT Index)
 410{
 411    UINT Array = 0;
 412    UINT Shift = 0;
 413
 414    if (Index > 0) {
 415        Array = (Index - 1) >> 0x2;
 416        Shift = (Index - 1) & 0x3;
 417    }
 418    if ((Array > pBI->ArrayLength) || (Index > pBI->IntegerLength))
 419        return 0;
 420
 421
 422    return (UINT8) UINT32_GETBYTE(pBI->pIntegerArray[Array], Shift - 1);
 423} /* End of BigInteger_GetByteValue */
 424
 425
 426VOID BigInteger_Copy (
 427    IN PBIG_INTEGER pBI_Copied,
 428    OUT PBIG_INTEGER *pBI_Result)
 429{
 430    BigInteger_AllocSize(pBI_Result, pBI_Copied->IntegerLength);
 431    NdisCopyMemory((*pBI_Result)->pIntegerArray, pBI_Copied->pIntegerArray, (sizeof(UINT32)*(*pBI_Result)->ArrayLength));
 432    (*pBI_Result)->ArrayLength = pBI_Copied->ArrayLength;
 433    (*pBI_Result)->IntegerLength = pBI_Copied->IntegerLength;
 434    (*pBI_Result)->Signed = pBI_Copied->Signed;
 435} /* End of BigInteger_Copy */
 436
 437
 438INT BigInteger_UnsignedCompare (
 439    IN PBIG_INTEGER pFirstOperand,
 440    IN PBIG_INTEGER pSecondOperand)
 441{
 442    INT BIArrayIndex;
 443
 444    if (pFirstOperand->IntegerLength > pSecondOperand->IntegerLength)
 445        return 1;
 446
 447    if (pFirstOperand->IntegerLength < pSecondOperand->IntegerLength)
 448        return -1;
 449
 450    if (pFirstOperand->IntegerLength == pSecondOperand->IntegerLength) {
 451        for(BIArrayIndex = (pFirstOperand->ArrayLength - 1);BIArrayIndex >= 0 ; BIArrayIndex--)
 452        {
 453            if (pFirstOperand->pIntegerArray[BIArrayIndex] > pSecondOperand->pIntegerArray[BIArrayIndex])
 454                return 1;
 455            else if (pFirstOperand->pIntegerArray[BIArrayIndex] < pSecondOperand->pIntegerArray[BIArrayIndex])
 456                return -1;
 457        } /* End of for */
 458    } /* End of if */
 459
 460    return 0;
 461} /* End of BigInteger_Compare */
 462
 463
 464VOID BigInteger_Add (
 465    IN PBIG_INTEGER pFirstOperand,
 466    IN PBIG_INTEGER pSecondOperand,
 467    OUT PBIG_INTEGER *pBI_Result)
 468{
 469    INT CompareResult;
 470    UINT32 BIArrayIndex;
 471    UINT64 Sum, Carry;
 472    PBIG_INTEGER pTempBI = NULL;
 473
 474    if  ((pFirstOperand == NULL) || (pFirstOperand->pIntegerArray == NULL)
 475      || (pSecondOperand == NULL) || (pSecondOperand->pIntegerArray == NULL)) {
 476        DEBUGPRINT("BigInteger_Add: first or second operand is NULL.\n");
 477        return;
 478    } /* End of if */
 479
 480    if (*pBI_Result == NULL)
 481        BigInteger_Init(pBI_Result);
 482
 483    CompareResult = BigInteger_UnsignedCompare(pFirstOperand, pSecondOperand);
 484    if ((CompareResult == 0) & ((pFirstOperand->Signed * pSecondOperand->Signed) < 0)) {
 485        BigInteger_AllocSize(pBI_Result, 1);
 486        return ;
 487    } /* End of if */
 488
 489    /*
 490     *  Singed table
 491     *  A + B || A > B || A < B
 492     *  ------------------------
 493     *  +   + ||   +   ||   +
 494     *  +   - ||   +   ||   -
 495     *  -   + ||   -   ||   +
 496     *  -   - ||   -   ||   -
 497     */
 498    if ((pFirstOperand->Signed * pSecondOperand->Signed) > 0) {
 499        if (pFirstOperand->IntegerLength > pSecondOperand->IntegerLength) {
 500                BigInteger_AllocSize(pBI_Result, pFirstOperand->IntegerLength + 1);
 501        } else {
 502                BigInteger_AllocSize(pBI_Result, pSecondOperand->IntegerLength + 1);
 503        } /* End of if */
 504
 505        Carry = 0;
 506        for (BIArrayIndex=0; BIArrayIndex < (*pBI_Result)->ArrayLength; BIArrayIndex++)
 507        {
 508
 509            Sum = 0;
 510            if (BIArrayIndex < pFirstOperand->ArrayLength)
 511                Sum += (UINT64) pFirstOperand->pIntegerArray[BIArrayIndex];
 512
 513            if (BIArrayIndex < pSecondOperand->ArrayLength)
 514                Sum += (UINT64) pSecondOperand->pIntegerArray[BIArrayIndex];
 515
 516            Sum += Carry;
 517            Carry = Sum  >> 32;
 518            (*pBI_Result)->pIntegerArray[BIArrayIndex] = (UINT32) (Sum & 0xffffffffUL);
 519        } /* End of for */
 520        (*pBI_Result)->Signed = pFirstOperand->Signed;
 521        BigInteger_ClearHighBits(*pBI_Result);
 522    } else {
 523        if  ((pFirstOperand->Signed == 1) & (pSecondOperand->Signed == -1)) {
 524            BigInteger_Copy(pSecondOperand, &pTempBI);
 525            pTempBI->Signed = 1;
 526            BigInteger_Sub(pFirstOperand, pTempBI, pBI_Result);
 527        } else if ((pFirstOperand->Signed == -1) & (pSecondOperand->Signed == 1)) {
 528            BigInteger_Copy(pFirstOperand, &pTempBI);
 529            pTempBI->Signed = 1;
 530            BigInteger_Sub(pSecondOperand, pTempBI, pBI_Result);
 531        } /* End of if */
 532    } /* End of if */
 533
 534    BigInteger_Free(&pTempBI);
 535} /* End of BigInteger_Add */
 536
 537
 538VOID BigInteger_Sub (
 539    IN PBIG_INTEGER pFirstOperand,
 540    IN PBIG_INTEGER pSecondOperand,
 541    OUT PBIG_INTEGER *pBI_Result)
 542{
 543    INT CompareResult;
 544    UINT32 BIArrayIndex, Carry;
 545    PBIG_INTEGER pTempBI = NULL, pTempBI2 = NULL;
 546
 547    if  ((pFirstOperand == NULL) || (pFirstOperand->pIntegerArray == NULL)
 548      || (pSecondOperand == NULL) || (pSecondOperand->pIntegerArray == NULL)) {
 549        DEBUGPRINT("BigInteger_Sub: first or second operand is NULL.\n");
 550        return;
 551    } /* End of if */
 552
 553    if (*pBI_Result == NULL)
 554        BigInteger_Init(pBI_Result);
 555
 556    CompareResult = BigInteger_UnsignedCompare(pFirstOperand, pSecondOperand);
 557    if ((CompareResult == 0) & ((pFirstOperand->Signed * pSecondOperand->Signed) > 0)) {
 558        BigInteger_AllocSize(pBI_Result, 1);
 559        return ;
 560    } /* End of if */
 561
 562    BigInteger_Init(&pTempBI);
 563    BigInteger_Init(&pTempBI2);
 564
 565    /*
 566     *  Singed table
 567     *  A - B || A > B || A < B
 568     *  ------------------------
 569     *  +   + ||   +   ||   -
 570     *  +   - ||   +   ||   +
 571     *  -   + ||   -   ||   -
 572     *  -   - ||   -   ||   +
 573     */
 574    if ((pFirstOperand->Signed * pSecondOperand->Signed) > 0) {
 575        if (CompareResult == 1) {
 576            BigInteger_Copy(pFirstOperand, &pTempBI);
 577            BigInteger_Copy(pSecondOperand, &pTempBI2);
 578        } else if (CompareResult == -1) {
 579            BigInteger_Copy(pSecondOperand, &pTempBI);
 580            BigInteger_Copy(pFirstOperand, &pTempBI2);
 581        } /* End of if */
 582
 583        BigInteger_Copy(pTempBI, pBI_Result);
 584        Carry = 0;
 585        for (BIArrayIndex=0; BIArrayIndex < (*pBI_Result)->ArrayLength; BIArrayIndex++)
 586        {
 587            if (BIArrayIndex < pTempBI2->ArrayLength) {
 588                if ((*pBI_Result)->pIntegerArray[BIArrayIndex] >= (pTempBI2->pIntegerArray[BIArrayIndex] - Carry)) {
 589                    (*pBI_Result)->pIntegerArray[BIArrayIndex] = (*pBI_Result)->pIntegerArray[BIArrayIndex] - pTempBI2->pIntegerArray[BIArrayIndex] - Carry;
 590                    Carry = 0;
 591                } else {
 592                    (*pBI_Result)->pIntegerArray[BIArrayIndex] = 0xffffffffUL - pTempBI2->pIntegerArray[BIArrayIndex] - Carry + (*pBI_Result)->pIntegerArray[BIArrayIndex] + 1;
 593                    Carry = 1;
 594                } /* End of if */
 595            } else {
 596                if ((*pBI_Result)->pIntegerArray[BIArrayIndex] >= Carry) {
 597                    (*pBI_Result)->pIntegerArray[BIArrayIndex] -= Carry;
 598                    Carry = 0;
 599                } else {
 600                    (*pBI_Result)->pIntegerArray[BIArrayIndex] = 0xffffffffUL - Carry;
 601                    Carry = 1;
 602                } /* End of if */
 603            } /* End of if */
 604        } /* End of for */
 605
 606        if  (((pFirstOperand->Signed == 1) & (pSecondOperand->Signed == 1) & (CompareResult == -1))
 607          || ((pFirstOperand->Signed == -1) & (pSecondOperand->Signed == -1) & (CompareResult == 1)))
 608            (*pBI_Result)->Signed = -1;
 609
 610        BigInteger_ClearHighBits(*pBI_Result);
 611    } else {
 612        if  ((pFirstOperand->Signed == 1) & (pSecondOperand->Signed == -1)) {
 613            BigInteger_Copy(pSecondOperand, &pTempBI);
 614            pTempBI->Signed = 1;
 615            BigInteger_Add(pFirstOperand, pTempBI, pBI_Result);
 616        } else if ((pFirstOperand->Signed == -1) & (pSecondOperand->Signed == 1)) {
 617            BigInteger_Copy(pFirstOperand, &pTempBI);
 618            pTempBI->Signed = 1;
 619            BigInteger_Add(pTempBI, pSecondOperand, pBI_Result);
 620            (*pBI_Result)->Signed = -1;
 621        } /* End of if */
 622    } /* End of if */
 623
 624    BigInteger_Free(&pTempBI);
 625    BigInteger_Free(&pTempBI2);
 626} /* End of BigInteger_Sub */
 627
 628
 629VOID BigInteger_Mul (
 630    IN PBIG_INTEGER pFirstOperand,
 631    IN PBIG_INTEGER pSecondOperand,
 632    OUT PBIG_INTEGER *pBI_Result)
 633{
 634
 635    UINT32 BIFirstIndex, BISecondIndex;
 636    UINT64 FirstValue, SecondValue, Sum, Carry;
 637
 638    if  ((pFirstOperand == NULL) || (pFirstOperand->pIntegerArray == NULL)
 639      || (pSecondOperand == NULL) || (pSecondOperand->pIntegerArray == NULL)) {
 640        DEBUGPRINT("BigInteger_Mul: first or second operand is NULL.\n");
 641        return;
 642    } /* End of if */
 643
 644    /* The first or second operand is zero */
 645    if  (((pFirstOperand->IntegerLength  == 1) && (pFirstOperand->pIntegerArray[0]  == 0))
 646       ||((pSecondOperand->IntegerLength == 1) && (pSecondOperand->pIntegerArray[0] == 0))) {
 647        BigInteger_AllocSize(pBI_Result, 1);
 648        goto output;
 649    } /* End of if */
 650
 651    /* The first or second operand is one */
 652    if  ((pFirstOperand->IntegerLength  == 1) && (pFirstOperand->pIntegerArray[0]  == 1)) {
 653        BigInteger_Copy(pSecondOperand, pBI_Result);
 654        goto output;
 655    } /* End of if */
 656    if  ((pSecondOperand->IntegerLength  == 1) && (pSecondOperand->pIntegerArray[0]  == 1)) {
 657        BigInteger_Copy(pFirstOperand, pBI_Result);
 658        goto output;
 659    } /* End of if */
 660
 661    BigInteger_AllocSize(pBI_Result, pFirstOperand->IntegerLength + pSecondOperand->IntegerLength);
 662
 663    for (BIFirstIndex=0; BIFirstIndex < pFirstOperand->ArrayLength; BIFirstIndex++)
 664    {
 665        Carry = 0;
 666        FirstValue = (UINT64) pFirstOperand->pIntegerArray[BIFirstIndex];
 667        if (FirstValue == 0) {
 668            continue;
 669        } else {
 670            for (BISecondIndex=0; BISecondIndex < pSecondOperand->ArrayLength; BISecondIndex++)
 671            {
 672                SecondValue = ((UINT64) pSecondOperand->pIntegerArray[BISecondIndex])*FirstValue;
 673                Sum = (UINT64) ((*pBI_Result)->pIntegerArray[BIFirstIndex + BISecondIndex] + SecondValue + Carry);
 674                Carry = Sum >> 32;
 675                (*pBI_Result)->pIntegerArray[BIFirstIndex + BISecondIndex] = (UINT32) (Sum & 0xffffffffUL);
 676            } /* End of for */
 677            while (Carry != 0) {
 678                Sum = (UINT64) (*pBI_Result)->pIntegerArray[BIFirstIndex + BISecondIndex];
 679                Sum += Carry;
 680
 681                Carry = Sum >> 32;
 682                (*pBI_Result)->pIntegerArray[BIFirstIndex + BISecondIndex] = (UINT32) (Sum & 0xffffffffUL);
 683                BISecondIndex++;
 684            } /* End of while */
 685        } /* End of if */
 686    } /* End of for */
 687
 688output:
 689    (*pBI_Result)->Signed = pFirstOperand->Signed * pSecondOperand->Signed;
 690    BigInteger_ClearHighBits(*pBI_Result);
 691} /* End of BigInteger_Mul */
 692
 693
 694VOID BigInteger_Square (
 695    IN PBIG_INTEGER pBI,
 696    OUT PBIG_INTEGER *pBI_Result)
 697{
 698    INT BIFirstIndex, BISecondIndex;
 699        UINT32 HBITS_Value, LBITS_Value, Temp1_Value, Temp2_Value, Carry32;
 700        UINT32 *Point_Of_S, *Point_Of_Result, *Point_Of_BI;
 701    UINT64 Result64_1, Result64_2, Carry64, TempValue64;
 702
 703    if ((pBI == NULL) || (pBI->pIntegerArray == NULL)) {
 704        DEBUGPRINT("\tBigInteger_Square: the operand is NULL.\n");
 705        return;
 706    } /* End of if */
 707
 708    /* The operand is zero */
 709    if  ((pBI->IntegerLength  == 1) && (pBI->pIntegerArray[0]  ==  0)) {
 710        BigInteger_AllocSize(pBI_Result, 1);
 711        goto output;
 712    } /* End of if */
 713
 714    BigInteger_AllocSize(pBI_Result, (pBI->IntegerLength*2) + 20);
 715    BigInteger_AllocSize(&pBI_S, (pBI->IntegerLength*2) + 20);
 716    BigInteger_AllocSize(&pBI_O, (pBI->IntegerLength*2) + 20);
 717
 718    /*
 719     * Input: pBI = {a_0, a_1, a_2, a_3, ..., a_n}
 720     * Step1. calculate a_0^2, a_1^2, a_2^2, a_3^2 ... a_n^2
 721     */
 722        Point_Of_S = pBI_S->pIntegerArray;
 723    for (BIFirstIndex=0; BIFirstIndex < pBI->ArrayLength; BIFirstIndex++)
 724    {
 725        HBITS_Value = UINT32_HBITS(pBI->pIntegerArray[BIFirstIndex]);
 726                LBITS_Value = UINT32_LBITS(pBI->pIntegerArray[BIFirstIndex]);
 727                Temp1_Value = HBITS_Value*LBITS_Value;
 728                Temp2_Value = (Temp1_Value & 0x7fff) << 0x11;
 729                Point_Of_S[0] = (LBITS_Value*LBITS_Value) + Temp2_Value;
 730                Point_Of_S[1] = (HBITS_Value*HBITS_Value) + ((Temp1_Value >> 0xf) & 0x1ffff);
 731                if (Point_Of_S[0] < Temp2_Value)
 732                        Point_Of_S[1] += 1;
 733
 734                Point_Of_S += 2;
 735    } /* End of for */
 736
 737    /*
 738     * Step2. calculate a_0*{a_1, a_2, a_3, a_4, ..., a_n}
 739     */
 740    Point_Of_BI = pBI->pIntegerArray;
 741    Point_Of_Result = (*pBI_Result)->pIntegerArray;
 742    Point_Of_Result[0] = 0;
 743    TempValue64 = (UINT64) Point_Of_BI[0];
 744    Point_Of_Result++;
 745    Carry64 = 0;
 746    for (BIFirstIndex=1; BIFirstIndex < pBI->ArrayLength; BIFirstIndex++)
 747    {
 748        Result64_1 =  (UINT64) Point_Of_BI[BIFirstIndex]*TempValue64;
 749        Result64_1 += Carry64;
 750        Carry64 = (Result64_1 >> 32);
 751        Point_Of_Result[0] = (UINT32) (Result64_1 & 0xffffffffUL);
 752        Point_Of_Result++;
 753    } /* End of for */
 754    if (Carry64 > 0)
 755        Point_Of_Result[0] = (UINT32) (Carry64 & 0xffffffffUL);
 756
 757    /*
 758     * Step3. calculate
 759     *           a_1*{a_2, a_3, a_4, ..., a_n}
 760     *           a_2*{a_3, a_4, a_5, ..., a_n}
 761     *           a_3*{a_4, a_5, a_6, ..., a_n}
 762     *           a_4*{a_5, a_6, a_7, ..., a_n}
 763     *           ...
 764     *           a_n-1*{a_n}
 765     */
 766    Point_Of_BI = pBI->pIntegerArray;
 767    for (BIFirstIndex=1; BIFirstIndex < (pBI->ArrayLength - 1); BIFirstIndex++)
 768    {
 769        Point_Of_Result = (*pBI_Result)->pIntegerArray;
 770        Point_Of_Result += (BIFirstIndex*2) + 1;
 771        TempValue64 = (UINT64) Point_Of_BI[BIFirstIndex];
 772        Carry64 = 0;
 773        for (BISecondIndex=(BIFirstIndex + 1); BISecondIndex < pBI->ArrayLength; BISecondIndex++)
 774        {
 775            Result64_1 = ((UINT64) Point_Of_Result[0]) + Carry64;
 776            Result64_2 = (UINT64) Point_Of_BI[BISecondIndex]*TempValue64;
 777            Carry64 = (Result64_1 >> 32);
 778            Result64_1 = (Result64_1 & 0xffffffffUL);
 779            Result64_1 = Result64_1 + Result64_2;
 780            Carry64 += (Result64_1 >> 32);
 781            Point_Of_Result[0] = (UINT32) (Result64_1 & 0xffffffffUL);
 782            Point_Of_Result++;
 783        } /* End of for */
 784        if (Carry64 > 0)
 785            Point_Of_Result[0] += (UINT32) (Carry64 & 0xffffffffUL);
 786    } /* End of for */
 787
 788    BigInteger_ClearHighBits(*pBI_Result);
 789    BigInteger_Copy(*pBI_Result, &pBI_O);
 790
 791    Carry32 = 0;
 792        for (BIFirstIndex=0; BIFirstIndex < pBI_O->ArrayLength; BIFirstIndex++) {
 793        pBI_O->pIntegerArray[BIFirstIndex] = (pBI_O->pIntegerArray[BIFirstIndex] << 1) | Carry32;
 794        if (pBI_O->pIntegerArray[BIFirstIndex] < (*pBI_Result)->pIntegerArray[BIFirstIndex])
 795            Carry32 = 1;
 796        else
 797            Carry32 = 0;
 798    } /* End of for */
 799    pBI_O->pIntegerArray[BIFirstIndex] = Carry32;
 800    pBI_O->IntegerLength++;
 801    pBI_O->ArrayLength++;
 802    BigInteger_ClearHighBits(pBI_O);
 803
 804    BigInteger_Add(pBI_O, pBI_S, pBI_Result);
 805output:
 806    (*pBI_Result)->Signed = 1;
 807    BigInteger_ClearHighBits(*pBI_Result);
 808} /* End of BigInteger_Square */
 809
 810
 811VOID BigInteger_Div (
 812    IN PBIG_INTEGER pFirstOperand,
 813    IN PBIG_INTEGER pSecondOperand,
 814    OUT PBIG_INTEGER *pBI_Result,
 815    OUT PBIG_INTEGER *pBI_Remainder)
 816{
 817    INT CompareResult;
 818    INT Index, MulIndex, ComputeSize;
 819    UINT32 MulStart;
 820    UINT AllocLength, ArrayIndex, ShiftIndex;
 821    PBIG_INTEGER pTempBI = NULL, pTempBI2 = NULL, pMulBI = NULL;
 822    UINT8 SecondHighByte;
 823
 824    if  ((pFirstOperand == NULL) || (pFirstOperand->pIntegerArray == NULL)
 825      || (pSecondOperand == NULL) || (pSecondOperand->pIntegerArray == NULL)) {
 826        DEBUGPRINT("BigInteger_Div: first or second operand is NULL.\n");
 827        return;
 828    } /* End of if */
 829
 830    /* The second operand is zero */
 831    if ((pSecondOperand->IntegerLength == 1) && (pSecondOperand->pIntegerArray[0] == 0)) {
 832        DEBUGPRINT("BigInteger_Div: second operand is zero.\n");
 833        return;
 834    } /* End of if */
 835
 836    if (*pBI_Result == NULL)
 837        BigInteger_Init(pBI_Result);
 838    if (*pBI_Remainder == NULL)
 839        BigInteger_Init(pBI_Remainder);
 840
 841    /* The second operand is one */
 842    if  ((pSecondOperand->IntegerLength  == 1) && (pSecondOperand->pIntegerArray[0]  == 1)) {
 843        BigInteger_Copy(pFirstOperand, pBI_Result);
 844        BigInteger_Bin2BI(Value_0, 1, pBI_Remainder);
 845        goto output;
 846    } /* End of if */
 847
 848    CompareResult = BigInteger_UnsignedCompare(pFirstOperand, pSecondOperand);
 849    if (CompareResult == 0) {
 850        BigInteger_Bin2BI(Value_1, 1, pBI_Result);
 851        BigInteger_Bin2BI(Value_0, 1, pBI_Remainder);
 852        goto output;
 853    } else if (CompareResult == -1) {
 854        BigInteger_Bin2BI(Value_0, 1, pBI_Result);
 855        BigInteger_Copy(pFirstOperand, pBI_Remainder);
 856        goto output;
 857    } /* End of if */
 858    BigInteger_AllocSize(pBI_Result, pFirstOperand->IntegerLength - pSecondOperand->IntegerLength + 1);
 859    BigInteger_AllocSize(pBI_Remainder, pSecondOperand->IntegerLength);
 860
 861    AllocLength = (UINT) (pFirstOperand->IntegerLength << 1);
 862    BigInteger_AllocSize(&pTempBI, AllocLength);
 863    BigInteger_AllocSize(&pTempBI2, AllocLength);
 864    BigInteger_AllocSize(&pMulBI, AllocLength);
 865
 866    BigInteger_Copy(pFirstOperand, pBI_Remainder);
 867    SecondHighByte = BigInteger_GetByteValue(pSecondOperand, pSecondOperand->IntegerLength);
 868    ComputeSize = (INT) pFirstOperand->IntegerLength - pSecondOperand->IntegerLength + 1;
 869    for (Index = (INT) ComputeSize;Index >= 0;Index--) {
 870        if (BigInteger_UnsignedCompare(*pBI_Remainder, pSecondOperand) == -1)
 871            break;
 872
 873        if (((pSecondOperand->IntegerLength + Index) - (*pBI_Remainder)->IntegerLength) <= 1) {
 874            BigInteger_AllocSize(&pMulBI, Index + 1);
 875            ArrayIndex = 0;
 876            if (Index > 0)
 877                ArrayIndex = (UINT) (Index - 1) >> 2 ;
 878            ShiftIndex = (Index & 0x03);
 879            if (ShiftIndex == 0)
 880                ShiftIndex = 4;
 881            ShiftIndex--;
 882            MulStart = 0;
 883            MulStart = (BigInteger_GetByteValue((*pBI_Remainder), pFirstOperand->IntegerLength + Index - ComputeSize + 1) & 0xFF) << 8;
 884            MulStart = MulStart | (BigInteger_GetByteValue((*pBI_Remainder), pFirstOperand->IntegerLength + Index - ComputeSize) & 0xFF);
 885            if (MulStart < (UINT32) SecondHighByte)
 886                continue;
 887
 888            MulStart = MulStart / (UINT32) SecondHighByte;
 889
 890            if (MulStart > 0xFF)
 891                MulStart = 0x100;
 892
 893            for (MulIndex = (INT) MulStart;MulIndex <= 0x101;MulIndex++) { /* 0xFFFF / 0xFF = 0x101 */
 894                if ((MulIndex > 0xFF) && (ShiftIndex == 3))
 895                        pMulBI->pIntegerArray[ArrayIndex + 1] = 0x01;
 896                pMulBI->pIntegerArray[ArrayIndex] = ((UINT) MulIndex << (8*ShiftIndex));
 897                BigInteger_Mul(pSecondOperand, pMulBI , &pTempBI);
 898                CompareResult = BigInteger_UnsignedCompare(*pBI_Remainder, pTempBI);
 899                if (CompareResult < 1) {
 900                    if (MulIndex > 1) {
 901                        if (CompareResult != 0) {
 902                            if ((MulIndex == 0x100) && (ShiftIndex == 3))
 903                                   pMulBI->pIntegerArray[ArrayIndex + 1] = 0;
 904                            pMulBI->pIntegerArray[ArrayIndex] = ((UINT) (MulIndex - 1) << (8*ShiftIndex));
 905                        } /* End of if */
 906
 907                        BigInteger_Mul(pSecondOperand, pMulBI, &pTempBI);
 908                        BigInteger_Sub(*pBI_Remainder, pTempBI, &pTempBI2);
 909                        BigInteger_Copy(pTempBI2, pBI_Remainder);
 910                        BigInteger_Add(*pBI_Result, pMulBI, &pTempBI2);
 911                        BigInteger_Copy(pTempBI2, pBI_Result);
 912                    } /* End of if */
 913                    break;
 914                } /* End of if */
 915
 916                if ((MulIndex >= 0x100) && (ShiftIndex == 3))
 917                   pMulBI->pIntegerArray[ArrayIndex++] = 0;
 918                pMulBI->pIntegerArray[ArrayIndex] = 0;
 919            } /* End of for */
 920        } /* End of if */
 921    } /* End of for */
 922
 923    BigInteger_Free(&pTempBI);
 924    BigInteger_Free(&pTempBI2);
 925    BigInteger_Free(&pMulBI);
 926output:
 927    (*pBI_Result)->Signed = pFirstOperand->Signed * pSecondOperand->Signed;
 928    (*pBI_Remainder)->Signed = pFirstOperand->Signed * pSecondOperand->Signed;
 929    BigInteger_ClearHighBits(*pBI_Result);
 930    BigInteger_ClearHighBits(*pBI_Remainder);
 931} /* End of BigInteger_Div */
 932
 933
 934VOID BigInteger_Montgomery_Reduction (
 935    IN PBIG_INTEGER pBI_A,
 936    IN PBIG_INTEGER pBI_P,
 937     IN PBIG_INTEGER pBI_R,
 938    OUT PBIG_INTEGER *pBI_Result)
 939{
 940    UINT32 *Point_P, *Point_Result;
 941    UINT32 LoopCount;
 942    UINT64 Result64_1, Result64_2, Carry64, TempValue64;
 943    INT FirstLoop, SecondLoop;
 944
 945    BigInteger_AllocSize(pBI_Result, pBI_A->IntegerLength+ pBI_P->IntegerLength + 20);
 946    BigInteger_Copy(pBI_A, pBI_Result);
 947
 948    Point_P = pBI_P->pIntegerArray;
 949    Point_Result = (*pBI_Result)->pIntegerArray;
 950
 951    LoopCount = Bits_Of_R >> 0x5;
 952    for (FirstLoop = 0;FirstLoop < LoopCount;FirstLoop++) {
 953        Carry64 = 0;
 954        TempValue64 = (UINT64) Point_Result[0];
 955        for (SecondLoop = 0;SecondLoop < pBI_P->ArrayLength;SecondLoop++) {
 956            Result64_1 = ((UINT64) Point_Result[SecondLoop]) + Carry64;
 957            Result64_2 = (UINT64) Point_P[SecondLoop]*TempValue64;
 958            Carry64 = (Result64_1 >> 32);
 959            Result64_1 = (Result64_1 & 0xffffffffUL);
 960            Result64_1 = Result64_1 + Result64_2;
 961            Carry64 += (Result64_1 >> 32);
 962            Point_Result[SecondLoop] = (UINT32) (Result64_1 & 0xffffffffUL);
 963        } /* End of for */
 964        while (Carry64 != 0) {
 965          Result64_1 = ((UINT64) Point_Result[SecondLoop]) + Carry64;
 966          Carry64 = Result64_1 >> 32;
 967          Point_Result[SecondLoop] = (UINT32) (Result64_1 & 0xffffffffUL);
 968          SecondLoop++;
 969        } /* End of while */
 970        Point_Result++;
 971    } /* End of for */
 972
 973    for (FirstLoop = 0;FirstLoop <= LoopCount;FirstLoop++) {
 974        (*pBI_Result)->pIntegerArray[FirstLoop] = (*pBI_Result)->pIntegerArray[FirstLoop + LoopCount];
 975    } /* End of for */
 976    if ((*pBI_Result)->pIntegerArray[LoopCount] != 0)
 977        (*pBI_Result)->ArrayLength = LoopCount + 1;
 978    else
 979        (*pBI_Result)->ArrayLength = LoopCount;
 980
 981    (*pBI_Result)->IntegerLength = (*pBI_Result)->ArrayLength*4;
 982    BigInteger_ClearHighBits(*pBI_Result);
 983
 984    if (BigInteger_UnsignedCompare(*pBI_Result, pBI_P) >= 0) {
 985        BigInteger_Sub(*pBI_Result, pBI_P, &pBI_U);
 986        BigInteger_Copy(pBI_U, pBI_Result);
 987    } /* End of if */
 988    BigInteger_ClearHighBits(*pBI_Result);
 989} /* End of BigInteger_Montgomery_Reduction */
 990
 991
 992VOID BigInteger_Montgomery_ExpMod (
 993    IN PBIG_INTEGER pBI_G,
 994    IN PBIG_INTEGER pBI_E,
 995    IN PBIG_INTEGER pBI_P,
 996    OUT PBIG_INTEGER *pBI_Result)
 997{
 998    UINT Bits_Of_P;
 999    UINT32 Index, Index2, AllocLength;
1000        UINT32 Sliding_Value , Sliding_HighValue, Sliding_LowValue;

1001    PBIG_INTEGER pBI_Temp1 = NULL, pBI_Temp2 = NULL;
1002    PBIG_INTEGER pBI_X = NULL, pBI_R = NULL, pBI_RR = NULL, pBI_1 = NULL;
1003    BIG_INTEGER *pBI_A[SLIDING_WINDOW];
1004    UINT8 *pRValue = NULL;
1005
1006    AllocLength = (pBI_G->IntegerLength + pBI_E->IntegerLength + pBI_P->IntegerLength + 300);
1007    BigInteger_AllocSize(&pBI_Temp1, AllocLength);
1008    BigInteger_AllocSize(&pBI_Temp2, AllocLength);
1009
1010    /* Calculate the bits of P and E, the highest bit is 1 */
1011    BigInteger_BitsOfBI(pBI_P, &Bits_Of_P);
1012
1013    if ((pBI_E->IntegerLength == 1) && (pBI_E->pIntegerArray[0] == 1)) {
1014        BigInteger_Div(pBI_G, pBI_P, &pBI_Temp1, pBI_Result);
1015        goto memory_free;
1016    } /* End of if */
1017
1018    if ((pBI_E->IntegerLength == 1) && (pBI_E->pIntegerArray[0] == 2)) {
1019        BigInteger_Mul(pBI_G, pBI_G, &pBI_Temp1);
1020        BigInteger_Div(pBI_Temp1, pBI_P, &pBI_Temp2, pBI_Result);
1021        goto memory_free;
1022    } /* End of if */
1023
1024    /*
1025     * Main algorithm
1026     */
1027    BigInteger_Init(&pBI_R);
1028    BigInteger_Init(&pBI_RR);
1029    BigInteger_Bin2BI(Value_1, 1, &pBI_1);
1030    BigInteger_AllocSize(&pBI_X, AllocLength);
1031    BigInteger_AllocSize(&pBI_U, AllocLength); // for BigInteger_Montgomery_Reduction
1032    BigInteger_AllocSize(&pBI_S, AllocLength); // for BigInteger_Square
1033    BigInteger_AllocSize(&pBI_O, AllocLength); // for BigInteger_Square
1034
1035    for (Index = 0; Index < SLIDING_WINDOW; Index++) {
1036        pBI_A[Index] = NULL;
1037                BigInteger_AllocSize(&pBI_A[Index], 193);
1038    } /* End of for */
1039    BigInteger_Bin2BI(WPS_DH_P_VALUE, 192, &pBI_Temp1);
1040    if (NdisCmpMemory(pBI_P->pIntegerArray, pBI_Temp1->pIntegerArray, pBI_P->IntegerLength) == 0) {
1041        BigInteger_Bin2BI(WPS_DH_X_VALUE, 184, &pBI_X);
1042        BigInteger_Bin2BI(WPS_DH_R_VALUE, 193, &pBI_R);
1043        BigInteger_Bin2BI(WPS_DH_RRModP_VALUE, 192, &pBI_RR);
1044        Bits_Of_R = 1537;
1045    } else {
1046        if ((Bits_Of_P % 8) == 0) {
1047            AllocLength = pBI_P->IntegerLength + 1;
1048        } else {
1049            AllocLength = pBI_P->IntegerLength;
1050        } /* End of if */
1051        pRValue = (UINT8 *) kmalloc(sizeof(UINT8)*AllocLength, GFP_ATOMIC);
1052        if (pRValue == NULL)
1053        {
1054                DBGPRINT(RT_DEBUG_ERROR, ("%s():Alloc memory failed\n", __FUNCTION__));
1055                goto memory_free;
1056        }
1057        NdisZeroMemory(pRValue, sizeof(UINT8)*AllocLength);
1058        pRValue[0] = (UINT8) (1 << (Bits_Of_P & 0x7));
1059        BigInteger_Bin2BI(pRValue, AllocLength , &pBI_R);
1060
1061        BigInteger_Mul(pBI_R, pBI_R, &pBI_Temp1);
1062        BigInteger_Div(pBI_Temp1, pBI_P, &pBI_A[1], &pBI_RR);
1063
1064        /* X = 1*R (mod P) */
1065        BigInteger_Div(pBI_R, pBI_P, &pBI_Temp2, &pBI_X);
1066    } /* End of if */
1067
1068    /* A = G*R (mod P) => A = MonMod(G, R^2 mod P) */
1069    BigInteger_Mul(pBI_G, pBI_RR, &pBI_Temp1);
1070    BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P , pBI_R, &pBI_A[1]);
1071    for (Index = 2; Index < SLIDING_WINDOW; Index++) {
1072        BigInteger_Mul(pBI_A[Index - 1], pBI_A[1], &pBI_Temp1);
1073            BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_A[Index]);
1074    } /* End of for */
1075
1076    for (Index = pBI_E->IntegerLength ; Index > 0 ; Index--) {
1077        for (Index2 = 0; Index2 < 4 ; Index2++) {
1078            BigInteger_Square(pBI_X, &pBI_Temp1);
1079                        BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_X);
1080            } /* End of for */
1081
1082                Sliding_Value = BigInteger_GetByteValue(pBI_E, Index);
1083                Sliding_HighValue = (Sliding_Value >> 4);
1084                if (Sliding_HighValue != 0) {
1085            BigInteger_Mul(pBI_A[Sliding_HighValue], pBI_X, &pBI_Temp1);
1086                        BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_X);
1087                } /* End of if */
1088
1089        for (Index2 = 0; Index2 < 4 ; Index2++) {
1090            BigInteger_Square(pBI_X, &pBI_Temp1);
1091                        BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_X);
1092            } /* End of for */
1093
1094                Sliding_LowValue = Sliding_Value & 0x0f;
1095                if (Sliding_LowValue != 0) {
1096            BigInteger_Mul(pBI_A[Sliding_LowValue], pBI_X, &pBI_Temp1);
1097                        BigInteger_Montgomery_Reduction(pBI_Temp1, pBI_P, pBI_R, &pBI_X);
1098                } /* End of if */
1099    } /* End of for */
1100    BigInteger_Montgomery_Reduction(pBI_X, pBI_P , pBI_R, pBI_Result);
1101
1102    BigInteger_Free(&pBI_X);
1103    BigInteger_Free(&pBI_R);
1104    BigInteger_Free(&pBI_RR);
1105    BigInteger_Free(&pBI_1);
1106    BigInteger_Free(&pBI_U);
1107    BigInteger_Free(&pBI_S);
1108    BigInteger_Free(&pBI_O);
1109    for(Index = 0; Index < SLIDING_WINDOW; Index++)
1110                        BigInteger_Free(&pBI_A[Index]);
1111    if (pRValue != NULL)
1112        kfree(pRValue);
1113
1114memory_free:
1115    BigInteger_Free(&pBI_Temp1);
1116    BigInteger_Free(&pBI_Temp2);
1117} /* End of BigInteger_Montgomery_ExpMod */
1118
1119/* End of crypt_biginteger.c */
1120