crypt_biginteger.c

ralink 2870 usb无线网卡 最新驱动

        Number <<= 1;
        Index++;
    } /* End of while */
    *Bits_Of_P = (pBI->ArrayLength*sizeof(UINT32)) - Index;
} /* End of BigInteger_BitsOfBN */


INT BigInteger_GetBitValue (
    IN PBIG_INTEGER pBI,
    IN UINT Index)
{
    UINT Array = 0;
    UINT Shift = 0;

    if (Index > 0) {
        Array = (Index - 1) >> 0x5;
        Shift = (Index - 1) & 0x1F;
    }
    if (Array > pBI->ArrayLength)
        return 0;

    return ((pBI->pIntegerArray[Array] >> Shift) & 0x1);
} /* End of BigInteger_GetBitValue */


UINT8 BigInteger_GetByteValue (
    IN PBIG_INTEGER pBI,
    IN UINT Index)
{
    UINT Array = 0;
    UINT Shift = 0;

    if (Index > 0) {
        Array = (Index - 1) >> 0x2;
        Shift = (Index - 1) & 0x3;
    }
    if ((Array > pBI->ArrayLength) || (Index > pBI->IntegerLength))
        return 0;


    return (UINT8) UINT32_GETBYTE(pBI->pIntegerArray[Array], Shift - 1);
} /* End of BigInteger_GetByteValue */


VOID BigInteger_Copy (
    IN PBIG_INTEGER pBI_Copied,
    OUT PBIG_INTEGER *pBI_Result)
{
    BigInteger_AllocSize(pBI_Result, pBI_Copied->IntegerLength);
    NdisCopyMemory((*pBI_Result)->pIntegerArray, pBI_Copied->pIntegerArray, (sizeof(UINT32)*(*pBI_Result)->ArrayLength));
    (*pBI_Result)->ArrayLength = pBI_Copied->ArrayLength;
    (*pBI_Result)->IntegerLength = pBI_Copied->IntegerLength;
    (*pBI_Result)->Signed = pBI_Copied->Signed;
} /* End of BigInteger_Copy */


INT BigInteger_UnsignedCompare (
    IN PBIG_INTEGER pFirstOperand, 
    IN PBIG_INTEGER pSecondOperand)
{
    INT BIArrayIndex;

    if (pFirstOperand->IntegerLength > pSecondOperand->IntegerLength)
        return 1;

    if (pFirstOperand->IntegerLength < pSecondOperand->IntegerLength)
        return -1;

    if (pFirstOperand->IntegerLength == pSecondOperand->IntegerLength) {
        for(BIArrayIndex = (pFirstOperand->ArrayLength - 1);BIArrayIndex >= 0 ; BIArrayIndex--)
        {
            if (pFirstOperand->pIntegerArray[BIArrayIndex] > pSecondOperand->pIntegerArray[BIArrayIndex])
                return 1;
            else if (pFirstOperand->pIntegerArray[BIArrayIndex] < pSecondOperand->pIntegerArray[BIArrayIndex])
                return -1;                
        } /* End of for */
    } /* End of if */

    return 0;    
} /* End of BigInteger_Compare */ 


VOID BigInteger_Add (
    IN PBIG_INTEGER pFirstOperand, 
    IN PBIG_INTEGER pSecondOperand, 
    OUT PBIG_INTEGER *pBI_Result)
{
    INT CompareResult;
    UINT32 BIArrayIndex;
    UINT64 Sum, Carry;
    PBIG_INTEGER pTempBI = NULL;

    if  ((pFirstOperand == NULL) || (pFirstOperand->pIntegerArray == NULL)
      || (pSecondOperand == NULL) || (pSecondOperand->pIntegerArray == NULL)) {
        DEBUGPRINT("BigInteger_Add: first or second operand is NULL.\n");
        return;
    } /* End of if */

    if (*pBI_Result == NULL)
        BigInteger_Init(pBI_Result);

    CompareResult = BigInteger_UnsignedCompare(pFirstOperand, pSecondOperand);
    if ((CompareResult == 0) & ((pFirstOperand->Signed * pSecondOperand->Signed) < 0)) {
        BigInteger_AllocSize(pBI_Result, 1);
        return ;
    } /* End of if */

    /*
     *  Singed table
     *  A + B || A > B || A < B
     *  ------------------------
     *  +   + ||   +   ||   +
     *  +   - ||   +   ||   -
     *  -   + ||   -   ||   +
     *  -   - ||   -   ||   -
     */
    if ((pFirstOperand->Signed * pSecondOperand->Signed) > 0) {
        if (pFirstOperand->IntegerLength > pSecondOperand->IntegerLength) {
                BigInteger_AllocSize(pBI_Result, pFirstOperand->IntegerLength + 1);
        } else { 
                BigInteger_AllocSize(pBI_Result, pSecondOperand->IntegerLength + 1);
        } /* End of if */

        Carry = 0;
        for (BIArrayIndex=0; BIArrayIndex < (*pBI_Result)->ArrayLength; BIArrayIndex++)
        {

            Sum = 0;
            if (BIArrayIndex < pFirstOperand->ArrayLength)
                Sum += (UINT64) pFirstOperand->pIntegerArray[BIArrayIndex];

            if (BIArrayIndex < pSecondOperand->ArrayLength)
                Sum += (UINT64) pSecondOperand->pIntegerArray[BIArrayIndex];

            Sum += Carry;
            Carry = Sum  >> 32;
            (*pBI_Result)->pIntegerArray[BIArrayIndex] = (UINT32) (Sum & 0xffffffffUL);
        } /* End of for */        
        (*pBI_Result)->Signed = pFirstOperand->Signed;
        BigInteger_ClearHighBits(*pBI_Result);     
    } else {
        if  ((pFirstOperand->Signed == 1) & (pSecondOperand->Signed == -1)) {            
            BigInteger_Copy(pSecondOperand, &pTempBI);
            pTempBI->Signed = 1;
            BigInteger_Sub(pFirstOperand, pTempBI, pBI_Result);
        } else if ((pFirstOperand->Signed == -1) & (pSecondOperand->Signed == 1)) {
            BigInteger_Copy(pFirstOperand, &pTempBI);
            pTempBI->Signed = 1;
            BigInteger_Sub(pSecondOperand, pTempBI, pBI_Result);
        } /* End of if */
    } /* End of if */    

    BigInteger_Free(&pTempBI);    
} /* End of BigInteger_Add */


VOID BigInteger_Sub (
    IN PBIG_INTEGER pFirstOperand, 
    IN PBIG_INTEGER pSecondOperand, 
    OUT PBIG_INTEGER *pBI_Result)
{
    INT CompareResult;
    UINT32 BIArrayIndex, Carry;
    PBIG_INTEGER pTempBI = NULL, pTempBI2 = NULL;
    
    if  ((pFirstOperand == NULL) || (pFirstOperand->pIntegerArray == NULL)
      || (pSecondOperand == NULL) || (pSecondOperand->pIntegerArray == NULL)) {
        DEBUGPRINT("BigInteger_Sub: first or second operand is NULL.\n");
        return;
    } /* End of if */

    if (*pBI_Result == NULL)
        BigInteger_Init(pBI_Result);

    CompareResult = BigInteger_UnsignedCompare(pFirstOperand, pSecondOperand);
    if ((CompareResult == 0) & ((pFirstOperand->Signed * pSecondOperand->Signed) > 0)) {
        BigInteger_AllocSize(pBI_Result, 1);
        return ;
    } /* End of if */

    BigInteger_Init(&pTempBI);
    BigInteger_Init(&pTempBI2);

    /*
     *  Singed table
     *  A - B || A > B || A < B
     *  ------------------------
     *  +   + ||   +   ||   -
     *  +   - ||   +   ||   +
     *  -   + ||   -   ||   -
     *  -   - ||   -   ||   +
     */
    if ((pFirstOperand->Signed * pSecondOperand->Signed) > 0) {
        if (CompareResult == 1) {
            BigInteger_Copy(pFirstOperand, &pTempBI);
            BigInteger_Copy(pSecondOperand, &pTempBI2);
        } else if (CompareResult == -1) {
            BigInteger_Copy(pSecondOperand, &pTempBI);
            BigInteger_Copy(pFirstOperand, &pTempBI2);
        } /* End of if */ 

        BigInteger_Copy(pTempBI, pBI_Result);    
        Carry = 0;
        for (BIArrayIndex=0; BIArrayIndex < (*pBI_Result)->ArrayLength; BIArrayIndex++)
        {
            if (BIArrayIndex < pTempBI2->ArrayLength) {
                if ((*pBI_Result)->pIntegerArray[BIArrayIndex] >= (pTempBI2->pIntegerArray[BIArrayIndex] - Carry)) {
                    (*pBI_Result)->pIntegerArray[BIArrayIndex] = (*pBI_Result)->pIntegerArray[BIArrayIndex] - pTempBI2->pIntegerArray[BIArrayIndex] - Carry;
                    Carry = 0;
                } else {
                    (*pBI_Result)->pIntegerArray[BIArrayIndex] = 0xffffffffUL - pTempBI2->pIntegerArray[BIArrayIndex] - Carry + (*pBI_Result)->pIntegerArray[BIArrayIndex] + 1;
                    Carry = 1;
                } /* End of if */
            } else {
                if ((*pBI_Result)->pIntegerArray[BIArrayIndex] >= Carry) {
                    (*pBI_Result)->pIntegerArray[BIArrayIndex] -= Carry;
                    Carry = 0;
                } else {
                    (*pBI_Result)->pIntegerArray[BIArrayIndex] = 0xffffffffUL - Carry;
                    Carry = 1;
                } /* End of if */            
            } /* End of if */
        } /* End of for */

        if  (((pFirstOperand->Signed == 1) & (pSecondOperand->Signed == 1) & (CompareResult == -1))
          || ((pFirstOperand->Signed == -1) & (pSecondOperand->Signed == -1) & (CompareResult == 1)))
            (*pBI_Result)->Signed = -1;
        
        BigInteger_ClearHighBits(*pBI_Result);        
    } else {
        if  ((pFirstOperand->Signed == 1) & (pSecondOperand->Signed == -1)) {
            BigInteger_Copy(pSecondOperand, &pTempBI);
            pTempBI->Signed = 1;
            BigInteger_Add(pFirstOperand, pTempBI, pBI_Result);
        } else if ((pFirstOperand->Signed == -1) & (pSecondOperand->Signed == 1)) {
            BigInteger_Copy(pFirstOperand, &pTempBI);
            pTempBI->Signed = 1;
            BigInteger_Add(pTempBI, pSecondOperand, pBI_Result);
            (*pBI_Result)->Signed = -1;
        } /* End of if */
    } /* End of if */ 
    
    BigInteger_Free(&pTempBI);
    BigInteger_Free(&pTempBI2);     
} /* End of BigInteger_Sub */


VOID BigInteger_Mul (
    IN PBIG_INTEGER pFirstOperand, 
    IN PBIG_INTEGER pSecondOperand, 
    OUT PBIG_INTEGER *pBI_Result)
{

    UINT32 BIFirstIndex, BISecondIndex;
    UINT64 FirstValue, SecondValue, Sum, Carry;
   
    if  ((pFirstOperand == NULL) || (pFirstOperand->pIntegerArray == NULL)
      || (pSecondOperand == NULL) || (pSecondOperand->pIntegerArray == NULL)) {
        DEBUGPRINT("BigInteger_Mul: first or second operand is NULL.\n");
        return;
    } /* End of if */
   
    /* The first or second operand is zero */
    if  (((pFirstOperand->IntegerLength  == 1) && (pFirstOperand->pIntegerArray[0]  == 0))
       ||((pSecondOperand->IntegerLength == 1) && (pSecondOperand->pIntegerArray[0] == 0))) {
        BigInteger_AllocSize(pBI_Result, 1);
        goto output;
    } /* End of if */

    /* The first or second operand is one */
    if  ((pFirstOperand->IntegerLength  == 1) && (pFirstOperand->pIntegerArray[0]  == 1)) {
        BigInteger_Copy(pSecondOperand, pBI_Result);
        goto output;
    } /* End of if */
    if  ((pSecondOperand->IntegerLength  == 1) && (pSecondOperand->pIntegerArray[0]  == 1)) {
        BigInteger_Copy(pFirstOperand, pBI_Result);
        goto output;
    } /* End of if */

    BigInteger_AllocSize(pBI_Result, pFirstOperand->IntegerLength + pSecondOperand->IntegerLength);

    for (BIFirstIndex=0; BIFirstIndex < pFirstOperand->ArrayLength; BIFirstIndex++)
    {
        Carry = 0;
        FirstValue = (UINT64) pFirstOperand->pIntegerArray[BIFirstIndex];
        if (FirstValue == 0) {
            continue;
        } else {
            for (BISecondIndex=0; BISecondIndex < pSecondOperand->ArrayLength; BISecondIndex++)
            {
                SecondValue = ((UINT64) pSecondOperand->pIntegerArray[BISecondIndex])*FirstValue;
                Sum = (UINT64) ((*pBI_Result)->pIntegerArray[BIFirstIndex + BISecondIndex] + SecondValue + Carry);               
                Carry = Sum >> 32;
                (*pBI_Result)->pIntegerArray[BIFirstIndex + BISecondIndex] = (UINT32) (Sum & 0xffffffffUL);
            } /* End of for */
            while (Carry != 0) {
                Sum = (UINT64) (*pBI_Result)->pIntegerArray[BIFirstIndex + BISecondIndex];
                Sum += Carry;

                Carry = Sum >> 32;
                (*pBI_Result)->pIntegerArray[BIFirstIndex + BISecondIndex] = (UINT32) (Sum & 0xffffffffUL);
                BISecondIndex++;
            } /* End of while */
        } /* End of if */
    } /* End of for */

output:
    (*pBI_Result)->Signed = pFirstOperand->Signed * pSecondOperand->Signed;
    BigInteger_ClearHighBits(*pBI_Result);
} /* End of BigInteger_Mul */


VOID BigInteger_Square (
    IN PBIG_INTEGER pBI, 
    OUT PBIG_INTEGER *pBI_Result)
{
    INT BIFirstIndex, BISecondIndex;
	UINT32 HBITS_Value, LBITS_Value, Temp1_Value, Temp2_Value, Carry32;
	UINT32 *Point_Of_S, *Point_Of_Result, *Point_Of_BI;
    UINT64 Result64_1, Result64_2, Carry64, TempValue64;    

    if ((pBI == NULL) || (pBI->pIntegerArray == NULL)) {
        DEBUGPRINT("\tBigInteger_Square: the operand is NULL.\n");
        return;
    } /* End of if */
   
    /* The operand is zero */
    if  ((pBI->IntegerLength  == 1) && (pBI->pIntegerArray[0]  ==  0)) {
        BigInteger_AllocSize(pBI_Result, 1);
        goto output;
    } /* End of if */

    BigInteger_AllocSize(pBI_Result, (pBI->IntegerLength*2) + 20);
    BigInteger_AllocSize(&pBI_S, (pBI->IntegerLength*2) + 20);
    BigInteger_AllocSize(&pBI_O, (pBI->IntegerLength*2) + 20);

    /*
     * Input: pBI = {a_0, a_1, a_2, a_3, ..., a_n}
     * Step1. calculate a_0^2, a_1^2, a_2^2, a_3^2 ... a_n^2
     */
	Point_Of_S = pBI_S->pIntegerArray;
    for (BIFirstIndex=0; BIFirstIndex < pBI->ArrayLength; BIFirstIndex++)
    {
    	HBITS_Value = UINT32_HBITS(pBI->pIntegerArray[BIFirstIndex]);
		LBITS_Value = UINT32_LBITS(pBI->pIntegerArray[BIFirstIndex]);
		Temp1_Value = HBITS_Value*LBITS_Value;
		Temp2_Value = (Temp1_Value & 0x7fff) << 0x11;
		Point_Of_S[0] = (LBITS_Value*LBITS_Value) + Temp2_Value;
		Point_Of_S[1] = (HBITS_Value*HBITS_Value) + ((Temp1_Value >> 0xf) & 0x1ffff);
		if (Point_Of_S[0] < Temp2_Value)
			Point_Of_S[1] += 1;

		Point_Of_S += 2;
    } /* End of for */

    /*
     * Step2. calculate a_0*{a_1, a_2, a_3, a_4, ..., a_n}
     */
    Point_Of_BI = pBI->pIntegerArray;
    Point_Of_Result = (*pBI_Result)->pIntegerArray;
    Point_Of_Result[0] = 0;
    TempValue64 = (UINT64) Point_Of_BI[0];
    Point_Of_Result++;
    Carry64 = 0;
    for (BIFirstIndex=1; BIFirstIndex < pBI->ArrayLength; BIFirstIndex++)
    {
        Result64_1 =  (UINT64) Point_Of_BI[BIFirstIndex]*TempValue64;
        Result64_1 += Carry64;              
        Carry64 = (Result64_1 >> 32);
        Point_Of_Result[0] = (UINT32) (Result64_1 & 0xffffffffUL);
        Point_Of_Result++;