recoding.c File Reference

#include "precomp.h"

Include dependency graph for recoding.c:

Go to the source code of this file.

Functions
VOID SYMCRYPT_CALL	SymCryptFixedWindowRecoding (UINT32 W, _Inout_ PSYMCRYPT_INT piK, _Inout_ PSYMCRYPT_INT piTmp, _Out_writes_(nRecodedDigits) PUINT32 absofKIs, _Out_writes_(nRecodedDigits) PUINT32 sigofKIs, UINT32 nRecodedDigits)
VOID SYMCRYPT_CALL	SymCryptWidthNafRecoding (UINT32 W, _Inout_ PSYMCRYPT_INT piK, _Out_writes_(nRecodedDigits) PUINT32 absofKIs, _Out_writes_(nRecodedDigits) PUINT32 sigofKIs, UINT32 nRecodedDigits)
VOID SYMCRYPT_CALL	SymCryptPositiveWidthNafRecoding (UINT32 W, _In_ PCSYMCRYPT_INT piK, UINT32 nBitsExp, _Out_writes_(nRecodedDigits) PUINT32 absofKIs, UINT32 nRecodedDigits)

Function Documentation

SymCryptFixedWindowRecoding()

VOID SYMCRYPT_CALL SymCryptFixedWindowRecoding	(	UINT32	W,
		_Inout_ PSYMCRYPT_INT	piK,
		_Inout_ PSYMCRYPT_INT	piTmp,
		_Out_writes_(nRecodedDigits) PUINT32	absofKIs,
		_Out_writes_(nRecodedDigits) PUINT32	sigofKIs,
		UINT32	nRecodedDigits
	)

Definition at line 44 of file recoding.c.

{
    UINT32 T1 = 0;
    UINT32 T2 = 0;
    UINT32 mask = ~(0xffffffff << W);       // Window mask = 2^w - 1 (e.g. 0x0000003f for w = 6)
    UINT32 smask = 0x1 << (W-1);            // Sign mask   = 2^(w-1) (e.g. 0x00000020 for w = 6)
 
    SYMCRYPT_ASSERT( W < 32 );
 
    for (UINT32 i=0; i < nRecodedDigits - 1; i++)
    {
        T1 = SymCryptIntGetValueLsbits32( piK ) & mask;         // T1 = k mod 2^W
 
        // At this point if the w-th bit of T1 is 1 then we know that T1 > 2^(w-1)
        // (Since k = odd is a loop invariant).
        //
        // In this case, (case A), T1 & ~smask is equal to (k mod 2^w) - 2^(w-1) = k_i = |k_i|.
        //
        // Otherwise, (case B), we know that T1 < 2^(w-1). Therefore 2^(w-1) - T1 = |k_i|.
 
        sigofKIs[i] = SYMCRYPT_MASK32_ZERO( T1 & smask );       // If the sign of k_i is - this mask is set to 0xffffffff. (Case B)
 
        T2 = T1 & ~smask;                                       // |k_i| in case A
        T1 = smask - T1;                                        // |k_i| in case B
 
        absofKIs[i] = ((T1 & sigofKIs[i]) | (T2 & ~sigofKIs[i])) >> 1; // Setting (masked) the absolute value of k_i in absofKIs (divided by 2)
 
        SymCryptIntSubUint32( piK, T2, piTmp );                 // This gives k - k_i in case (A)
        SymCryptIntAddUint32( piK, T1, piK );                   // This gives k - k_i in case (B)
 
        SymCryptIntMaskedCopy( piTmp, piK, ~sigofKIs[i] );      // Copy the result to piK in case (B)
 
        SymCryptIntDivPow2( piK, W-1, piK );                    // k := k / 2^(w-1)
    }
 
    // The last sign is positive given k < GOrd => k_t < 2^w
    sigofKIs[nRecodedDigits - 1] = 0;
    // Belts and braces, select only the bottom w-1 bits (ensure all absofKIs represent odd values in range [1,2^(w-1)-1])
    absofKIs[nRecodedDigits - 1] = (SymCryptIntGetValueLsbits32( piK ) & mask & ~smask) >> 1;
}

Referenced by SymCryptEcpointScalarMulFixedWindow().

SymCryptPositiveWidthNafRecoding()

VOID SYMCRYPT_CALL SymCryptPositiveWidthNafRecoding	(	UINT32	W,
		_In_ PCSYMCRYPT_INT	piK,
		UINT32	nBitsExp,
		_Out_writes_(nRecodedDigits) PUINT32	absofKIs,
		UINT32	nRecodedDigits
	)

Definition at line 180 of file recoding.c.

{
    UINT32 T1 = 0;
    UINT32 cntrZ = W;       // Counter that specifies when we filled the last non-zero NAF digit
 
    SYMCRYPT_ASSERT( nRecodedDigits <= SymCryptIntBitsizeOfObject( piK ) );
 
    for (UINT32 i=0; i < nRecodedDigits; i++)
    {
        T1 = SymCryptIntGetBits( piK, i, SYMCRYPT_MIN(W, nBitsExp-i) );   // Get a batch of W bits (but don't go over nBitsExp)
 
        if ((cntrZ>=W) && ((T1 & 0x01) > 0))    // Only store odd digits
        {
            absofKIs[i] = T1;
            cntrZ = 0;
        }
        else
        {
            absofKIs[i] = 0;
        }
 
        cntrZ++;        // Prepare the counter for the next iteration
    }
}

Referenced by SymCryptModMultiExpWnafWithInterleaving().

SymCryptWidthNafRecoding()

VOID SYMCRYPT_CALL SymCryptWidthNafRecoding	(	UINT32	W,
		_Inout_ PSYMCRYPT_INT	piK,
		_Out_writes_(nRecodedDigits) PUINT32	absofKIs,
		_Out_writes_(nRecodedDigits) PUINT32	sigofKIs,
		UINT32	nRecodedDigits
	)

Definition at line 125 of file recoding.c.

{
    UINT32 T1 = 0;
    UINT32 mask = ~(0xffffffff << W);       // Window mask = 2^w - 1 (e.g. 0x0000003f for w = 6)
    UINT32 modulus = mask + 1;              // 2^w
    UINT32 smask = 0x1 << (W-1);            // Sign mask   = 2^(w-1) (e.g. 0x00000020 for w = 6)
 
    SYMCRYPT_ASSERT( W < 32 );
 
    for (UINT32 i=0; i < nRecodedDigits; i++)
    {
        T1 = SymCryptIntGetValueLsbits32( piK ) & mask;         // T1 = k mod 2^W
 
        if (T1 & 0x1)
        {
            if (T1 > smask)
            {
                sigofKIs[i] = 0xffffffff;
                absofKIs[i] = modulus - T1;                         // 2^W - T1 = |T1 - 2^W|
                SymCryptIntAddUint32( piK, absofKIs[i], piK );      // k-k_i
            }
            else
            {
                // Here (k mod 2^W) is already in the specified range
                sigofKIs[i] = 0x00000001;
                absofKIs[i] = T1;
                SymCryptIntSubUint32( piK, absofKIs[i], piK );      // k-k_i
            }
        }
        else
        {
            absofKIs[i] = 0;
            sigofKIs[i] = 0;
        }
 
        SymCryptIntDivPow2( piK, 1, piK );                      // k := k / 2
    }
}

Referenced by SymCryptEcpointMultiScalarMulWnafWithInterleaving().