crypto/weakcryptospi/source/bigint/algorithms.cpp
author Mikko Sunikka <mikko.sunikka@nokia.com>
Fri, 06 Nov 2009 13:21:00 +0200
changeset 17 cd501b96611d
permissions -rw-r--r--
Revision: 200945 Kit: 200945
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
17
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     1
/*
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     2
* Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     3
* All rights reserved.
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     4
* This component and the accompanying materials are made available
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     5
* under the terms of the License "Eclipse Public License v1.0"
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     6
* which accompanies this distribution, and is available
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     7
* at the URL "http://www.eclipse.org/legal/epl-v10.html".
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     8
*
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
     9
* Initial Contributors:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    10
* Nokia Corporation - initial contribution.
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    11
*
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    12
* Contributors:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    13
*
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    14
* Description: 
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    15
*
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    16
*/
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    17
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    18
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    19
#include "words.h"
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    20
#include "algorithms.h"
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    21
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    22
word Add(word *C, const word *A, const word *B, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    23
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    24
	assert (N%2 == 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    25
	word carry = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    26
	for (unsigned int i = 0; i < N; i+=2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    27
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    28
		dword u = (dword) carry + A[i] + B[i];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    29
		C[i] = LOW_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    30
		u = (dword) HIGH_WORD(u) + A[i+1] + B[i+1];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    31
		C[i+1] = LOW_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    32
		carry = HIGH_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    33
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    34
	return carry;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    35
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    36
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    37
word Subtract(word *C, const word *A, const word *B, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    38
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    39
	assert (N%2 == 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    40
	word borrow=0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    41
	for (unsigned i = 0; i < N; i+=2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    42
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    43
		dword u = (dword) A[i] - B[i] - borrow;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    44
		C[i] = LOW_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    45
		u = (dword) A[i+1] - B[i+1] - (word)(0-HIGH_WORD(u));
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    46
		C[i+1] = LOW_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    47
		borrow = 0-HIGH_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    48
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    49
	return borrow;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    50
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    51
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    52
int Compare(const word *A, const word *B, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    53
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    54
	while (N--)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    55
		if (A[N] > B[N])
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    56
			return 1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    57
		else if (A[N] < B[N])
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    58
			return -1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    59
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    60
	return 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    61
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    62
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    63
// It is the job of the calling code to ensure that this won't carry.
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    64
// If you aren't sure, use the next version that will tell you if you need to
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    65
// grow your integer.
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    66
// Having two of these creates ever so slightly more code but avoids having
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    67
// ifdefs all over the rest of the code checking the following type stuff which
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    68
// causes warnings in certain compilers about unused parameters in release
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    69
// builds.  We can't have that can we!
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    70
/*
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    71
Allows avoid this all over bigint.cpp and primes.cpp
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    72
ifdef _DEBUG
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    73
	TUint carry = Increment(Ptr(), Size());
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    74
	assert(!carry);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    75
else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    76
	Increment(Ptr(), Size())
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    77
endif
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    78
*/
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    79
void IncrementNoCarry(word *A, unsigned int N, word B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    80
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    81
	assert(N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    82
	word t = A[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    83
	A[0] = t+B;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    84
	if (A[0] >= t)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    85
		return;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    86
	for (unsigned i=1; i<N; i++)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    87
		if (++A[i])
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    88
			return;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    89
	assert(0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    90
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    91
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    92
word Increment(word *A, unsigned int N, word B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    93
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    94
	assert(N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    95
	word t = A[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    96
	A[0] = t+B;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    97
	if (A[0] >= t)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    98
		return 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
    99
	for (unsigned i=1; i<N; i++)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   100
		if (++A[i])
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   101
			return 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   102
	return 1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   103
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   104
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   105
//See commments above about IncrementNoCarry
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   106
void DecrementNoCarry(word *A, unsigned int N, word B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   107
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   108
	assert(N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   109
	word t = A[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   110
	A[0] = t-B;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   111
	if (A[0] <= t)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   112
		return;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   113
	for (unsigned i=1; i<N; i++)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   114
		if (A[i]--)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   115
			return;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   116
	assert(0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   117
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   118
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   119
word Decrement(word *A, unsigned int N, word B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   120
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   121
	assert(N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   122
	word t = A[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   123
	A[0] = t-B;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   124
	if (A[0] <= t)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   125
		return 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   126
	for (unsigned i=1; i<N; i++)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   127
		if (A[i]--)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   128
			return 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   129
	return 1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   130
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   131
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   132
void TwosComplement(word *A, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   133
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   134
	Decrement(A, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   135
	for (unsigned i=0; i<N; i++)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   136
		A[i] = ~A[i];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   137
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   138
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   139
static word LinearMultiply(word *C, const word *A, word B, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   140
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   141
	word carry=0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   142
	for(unsigned i=0; i<N; i++)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   143
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   144
		dword p = (dword)A[i] * B + carry;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   145
		C[i] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   146
		carry = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   147
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   148
	return carry;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   149
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   150
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   151
static void AtomicMultiply(word *C, const word *A, const word *B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   152
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   153
/*
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   154
	word s;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   155
	dword d;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   156
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   157
	if (A1 >= A0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   158
		if (B0 >= B1)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   159
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   160
			s = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   161
			d = (dword)(A1-A0)*(B0-B1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   162
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   163
		else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   164
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   165
			s = (A1-A0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   166
			d = (dword)s*(word)(B0-B1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   167
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   168
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   169
		if (B0 > B1)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   170
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   171
			s = (B0-B1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   172
			d = (word)(A1-A0)*(dword)s;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   173
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   174
		else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   175
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   176
			s = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   177
			d = (dword)(A0-A1)*(B1-B0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   178
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   179
*/
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   180
	// this segment is the branchless equivalent of above
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   181
	word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   182
	unsigned int ai = A[1] < A[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   183
	unsigned int bi = B[0] < B[1];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   184
	unsigned int di = ai & bi;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   185
	dword d = (dword)D[di]*D[di+2];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   186
	D[1] = D[3] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   187
	unsigned int si = ai + !bi;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   188
	word s = D[si];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   189
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   190
	dword A0B0 = (dword)A[0]*B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   191
	C[0] = LOW_WORD(A0B0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   192
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   193
	dword A1B1 = (dword)A[1]*B[1];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   194
	dword t = (dword) HIGH_WORD(A0B0) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   195
	C[1] = LOW_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   196
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   197
	t = A1B1 + HIGH_WORD(t) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   198
	C[2] = LOW_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   199
	C[3] = HIGH_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   200
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   201
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   202
static word AtomicMultiplyAdd(word *C, const word *A, const word *B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   203
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   204
	word D[4] = {A[1]-A[0], A[0]-A[1], B[0]-B[1], B[1]-B[0]};
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   205
	unsigned int ai = A[1] < A[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   206
	unsigned int bi = B[0] < B[1];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   207
	unsigned int di = ai & bi;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   208
	dword d = (dword)D[di]*D[di+2];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   209
	D[1] = D[3] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   210
	unsigned int si = ai + !bi;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   211
	word s = D[si];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   212
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   213
	dword A0B0 = (dword)A[0]*B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   214
	dword t = A0B0 + C[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   215
	C[0] = LOW_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   216
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   217
	dword A1B1 = (dword)A[1]*B[1];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   218
	t = (dword) HIGH_WORD(t) + LOW_WORD(A0B0) + LOW_WORD(d) + LOW_WORD(A1B1) + C[1];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   219
	C[1] = LOW_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   220
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   221
	t = (dword) HIGH_WORD(t) + LOW_WORD(A1B1) + HIGH_WORD(A0B0) + HIGH_WORD(d) + HIGH_WORD(A1B1) - s + C[2];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   222
	C[2] = LOW_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   223
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   224
	t = (dword) HIGH_WORD(t) + HIGH_WORD(A1B1) + C[3];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   225
	C[3] = LOW_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   226
	return HIGH_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   227
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   228
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   229
static inline void AtomicMultiplyBottom(word *C, const word *A, const word *B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   230
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   231
	dword t = (dword)A[0]*B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   232
	C[0] = LOW_WORD(t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   233
	C[1] = HIGH_WORD(t) + A[0]*B[1] + A[1]*B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   234
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   235
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   236
#define MulAcc(x, y)								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   237
	p = (dword)A[x] * B[y] + c; 					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   238
	c = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   239
	p = (dword)d + HIGH_WORD(p);					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   240
	d = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   241
	e += HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   242
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   243
#define SaveMulAcc(s, x, y) 						\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   244
	R[s] = c;										\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   245
	p = (dword)A[x] * B[y] + d; 					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   246
	c = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   247
	p = (dword)e + HIGH_WORD(p);					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   248
	d = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   249
	e = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   250
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   251
#define MulAcc1(x, y)								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   252
	p = (dword)A[x] * A[y] + c; 					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   253
	c = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   254
	p = (dword)d + HIGH_WORD(p);					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   255
	d = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   256
	e += HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   257
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   258
#define SaveMulAcc1(s, x, y) 						\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   259
	R[s] = c;										\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   260
	p = (dword)A[x] * A[y] + d; 					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   261
	c = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   262
	p = (dword)e + HIGH_WORD(p);					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   263
	d = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   264
	e = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   265
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   266
#define SquAcc(x, y)								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   267
	p = (dword)A[x] * A[y];	\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   268
	p = p + p + c; 					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   269
	c = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   270
	p = (dword)d + HIGH_WORD(p);					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   271
	d = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   272
	e += HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   273
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   274
#define SaveSquAcc(s, x, y) 						\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   275
	R[s] = c;										\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   276
	p = (dword)A[x] * A[y];	\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   277
	p = p + p + d; 					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   278
	c = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   279
	p = (dword)e + HIGH_WORD(p);					\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   280
	d = LOW_WORD(p);								\
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   281
	e = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   282
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   283
// VC60 workaround: MSVC 6.0 has an optimization problem that makes
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   284
// (dword)A*B where either A or B has been cast to a dword before
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   285
// very expensive. Revisit a CombaSquare4() function when this
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   286
// problem is fixed.               
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   287
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   288
// WARNING: KeithR.  05/08/03 This routine doesn't work with gcc on hardware
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   289
// either.  I've completely removed it.  It may be worth looking into sometime
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   290
// in the future.
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   291
/*#ifndef __WINS__
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   292
static void CombaSquare4(word *R, const word *A)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   293
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   294
	dword p;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   295
	word c, d, e;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   296
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   297
	p = (dword)A[0] * A[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   298
	R[0] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   299
	c = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   300
	d = e = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   301
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   302
	SquAcc(0, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   303
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   304
	SaveSquAcc(1, 2, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   305
	MulAcc1(1, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   306
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   307
	SaveSquAcc(2, 0, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   308
	SquAcc(1, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   309
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   310
	SaveSquAcc(3, 3, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   311
	MulAcc1(2, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   312
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   313
	SaveSquAcc(4, 2, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   314
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   315
	R[5] = c;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   316
	p = (dword)A[3] * A[3] + d;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   317
	R[6] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   318
	R[7] = e + HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   319
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   320
#endif */
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   321
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   322
static void CombaMultiply4(word *R, const word *A, const word *B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   323
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   324
	dword p;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   325
	word c, d, e;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   326
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   327
	p = (dword)A[0] * B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   328
	R[0] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   329
	c = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   330
	d = e = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   331
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   332
	MulAcc(0, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   333
	MulAcc(1, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   334
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   335
	SaveMulAcc(1, 2, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   336
	MulAcc(1, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   337
	MulAcc(0, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   338
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   339
	SaveMulAcc(2, 0, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   340
	MulAcc(1, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   341
	MulAcc(2, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   342
	MulAcc(3, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   343
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   344
	SaveMulAcc(3, 3, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   345
	MulAcc(2, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   346
	MulAcc(1, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   347
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   348
	SaveMulAcc(4, 2, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   349
	MulAcc(3, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   350
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   351
	R[5] = c;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   352
	p = (dword)A[3] * B[3] + d;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   353
	R[6] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   354
	R[7] = e + HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   355
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   356
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   357
static void CombaMultiply8(word *R, const word *A, const word *B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   358
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   359
	dword p;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   360
	word c, d, e;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   361
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   362
	p = (dword)A[0] * B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   363
	R[0] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   364
	c = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   365
	d = e = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   366
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   367
	MulAcc(0, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   368
	MulAcc(1, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   369
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   370
	SaveMulAcc(1, 2, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   371
	MulAcc(1, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   372
	MulAcc(0, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   373
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   374
	SaveMulAcc(2, 0, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   375
	MulAcc(1, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   376
	MulAcc(2, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   377
	MulAcc(3, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   378
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   379
	SaveMulAcc(3, 0, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   380
	MulAcc(1, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   381
	MulAcc(2, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   382
	MulAcc(3, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   383
	MulAcc(4, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   384
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   385
	SaveMulAcc(4, 0, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   386
	MulAcc(1, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   387
	MulAcc(2, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   388
	MulAcc(3, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   389
	MulAcc(4, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   390
	MulAcc(5, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   391
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   392
	SaveMulAcc(5, 0, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   393
	MulAcc(1, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   394
	MulAcc(2, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   395
	MulAcc(3, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   396
	MulAcc(4, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   397
	MulAcc(5, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   398
	MulAcc(6, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   399
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   400
	SaveMulAcc(6, 0, 7);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   401
	MulAcc(1, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   402
	MulAcc(2, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   403
	MulAcc(3, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   404
	MulAcc(4, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   405
	MulAcc(5, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   406
	MulAcc(6, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   407
	MulAcc(7, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   408
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   409
	SaveMulAcc(7, 1, 7);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   410
	MulAcc(2, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   411
	MulAcc(3, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   412
	MulAcc(4, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   413
	MulAcc(5, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   414
	MulAcc(6, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   415
	MulAcc(7, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   416
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   417
	SaveMulAcc(8, 2, 7);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   418
	MulAcc(3, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   419
	MulAcc(4, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   420
	MulAcc(5, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   421
	MulAcc(6, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   422
	MulAcc(7, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   423
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   424
	SaveMulAcc(9, 3, 7);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   425
	MulAcc(4, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   426
	MulAcc(5, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   427
	MulAcc(6, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   428
	MulAcc(7, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   429
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   430
	SaveMulAcc(10, 4, 7);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   431
	MulAcc(5, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   432
	MulAcc(6, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   433
	MulAcc(7, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   434
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   435
	SaveMulAcc(11, 5, 7);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   436
	MulAcc(6, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   437
	MulAcc(7, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   438
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   439
	SaveMulAcc(12, 6, 7);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   440
	MulAcc(7, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   441
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   442
	R[13] = c;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   443
	p = (dword)A[7] * B[7] + d;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   444
	R[14] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   445
	R[15] = e + HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   446
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   447
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   448
static void CombaMultiplyBottom4(word *R, const word *A, const word *B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   449
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   450
	dword p;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   451
	word c, d, e;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   452
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   453
	p = (dword)A[0] * B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   454
	R[0] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   455
	c = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   456
	d = e = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   457
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   458
	MulAcc(0, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   459
	MulAcc(1, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   460
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   461
	SaveMulAcc(1, 2, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   462
	MulAcc(1, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   463
	MulAcc(0, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   464
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   465
	R[2] = c;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   466
	R[3] = d + A[0] * B[3] + A[1] * B[2] + A[2] * B[1] + A[3] * B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   467
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   468
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   469
static void CombaMultiplyBottom8(word *R, const word *A, const word *B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   470
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   471
	dword p;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   472
	word c, d, e;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   473
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   474
	p = (dword)A[0] * B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   475
	R[0] = LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   476
	c = HIGH_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   477
	d = e = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   478
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   479
	MulAcc(0, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   480
	MulAcc(1, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   481
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   482
	SaveMulAcc(1, 2, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   483
	MulAcc(1, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   484
	MulAcc(0, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   485
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   486
	SaveMulAcc(2, 0, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   487
	MulAcc(1, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   488
	MulAcc(2, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   489
	MulAcc(3, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   490
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   491
	SaveMulAcc(3, 0, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   492
	MulAcc(1, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   493
	MulAcc(2, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   494
	MulAcc(3, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   495
	MulAcc(4, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   496
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   497
	SaveMulAcc(4, 0, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   498
	MulAcc(1, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   499
	MulAcc(2, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   500
	MulAcc(3, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   501
	MulAcc(4, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   502
	MulAcc(5, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   503
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   504
	SaveMulAcc(5, 0, 6);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   505
	MulAcc(1, 5);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   506
	MulAcc(2, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   507
	MulAcc(3, 3);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   508
	MulAcc(4, 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   509
	MulAcc(5, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   510
	MulAcc(6, 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   511
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   512
	R[6] = c;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   513
	R[7] = d + A[0] * B[7] + A[1] * B[6] + A[2] * B[5] + A[3] * B[4] +
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   514
				A[4] * B[3] + A[5] * B[2] + A[6] * B[1] + A[7] * B[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   515
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   516
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   517
#undef MulAcc
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   518
#undef SaveMulAcc
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   519
static void AtomicInverseModPower2(word *C, word A0, word A1)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   520
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   521
	assert(A0%2==1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   522
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   523
	dword A=MAKE_DWORD(A0, A1), R=A0%8;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   524
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   525
	for (unsigned i=3; i<2*WORD_BITS; i*=2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   526
		R = R*(2-R*A);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   527
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   528
	assert(R*A==1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   529
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   530
	C[0] = LOW_WORD(R);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   531
	C[1] = HIGH_WORD(R);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   532
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   533
// ********************************************************
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   534
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   535
#define A0		A
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   536
#define A1		(A+N2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   537
#define B0		B
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   538
#define B1		(B+N2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   539
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   540
#define T0		T
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   541
#define T1		(T+N2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   542
#define T2		(T+N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   543
#define T3		(T+N+N2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   544
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   545
#define R0		R
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   546
#define R1		(R+N2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   547
#define R2		(R+N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   548
#define R3		(R+N+N2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   549
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   550
// R[2*N] - result = A*B
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   551
// T[2*N] - temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   552
// A[N] --- multiplier
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   553
// B[N] --- multiplicant
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   554
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   555
void RecursiveMultiply(word *R, word *T, const word *A, const word *B, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   556
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   557
	assert(N>=2 && N%2==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   558
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   559
	if (N==2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   560
		AtomicMultiply(R, A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   561
	else if (N==4)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   562
		CombaMultiply4(R, A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   563
	else if (N==8)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   564
		CombaMultiply8(R, A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   565
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   566
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   567
		const unsigned int N2 = N/2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   568
		int carry;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   569
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   570
		int aComp = Compare(A0, A1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   571
		int bComp = Compare(B0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   572
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   573
		switch (2*aComp + aComp + bComp)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   574
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   575
		case -4:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   576
			Subtract(R0, A1, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   577
			Subtract(R1, B0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   578
			RecursiveMultiply(T0, T2, R0, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   579
			Subtract(T1, T1, R0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   580
			carry = -1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   581
			break;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   582
		case -2:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   583
			Subtract(R0, A1, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   584
			Subtract(R1, B0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   585
			RecursiveMultiply(T0, T2, R0, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   586
			carry = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   587
			break;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   588
		case 2:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   589
			Subtract(R0, A0, A1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   590
			Subtract(R1, B1, B0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   591
			RecursiveMultiply(T0, T2, R0, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   592
			carry = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   593
			break;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   594
		case 4:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   595
			Subtract(R0, A1, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   596
			Subtract(R1, B0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   597
			RecursiveMultiply(T0, T2, R0, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   598
			Subtract(T1, T1, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   599
			carry = -1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   600
			break;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   601
		default:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   602
			SetWords(T0, 0, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   603
			carry = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   604
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   605
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   606
		RecursiveMultiply(R0, T2, A0, B0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   607
		RecursiveMultiply(R2, T2, A1, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   608
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   609
		// now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   610
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   611
		carry += Add(T0, T0, R0, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   612
		carry += Add(T0, T0, R2, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   613
		carry += Add(R1, R1, T0, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   614
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   615
		assert (carry >= 0 && carry <= 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   616
		Increment(R3, N2, carry);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   617
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   618
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   619
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   620
// R[2*N] - result = A*A
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   621
// T[2*N] - temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   622
// A[N] --- number to be squared
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   623
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   624
void RecursiveSquare(word *R, word *T, const word *A, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   625
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   626
	assert(N && N%2==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   627
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   628
	if (N==2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   629
		AtomicMultiply(R, A, A);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   630
	else if (N==4)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   631
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   632
		// VC60 workaround: MSVC 6.0 has an optimization problem that makes
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   633
		// (dword)A*B where either A or B has been cast to a dword before
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   634
		// very expensive. Revisit a CombaSquare4() function when this
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   635
		// problem is fixed.               
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   636
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   637
// WARNING: KeithR. 05/08/03 This routine doesn't work with gcc on hardware
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   638
// either.  I've completely removed it.  It may be worth looking into sometime
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   639
// in the future.  Therefore, we use the CombaMultiply4 on all targets.
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   640
//#ifdef __WINS__
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   641
		CombaMultiply4(R, A, A);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   642
/*#else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   643
		CombaSquare4(R, A);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   644
#endif*/
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   645
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   646
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   647
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   648
		const unsigned int N2 = N/2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   649
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   650
		RecursiveSquare(R0, T2, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   651
		RecursiveSquare(R2, T2, A1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   652
		RecursiveMultiply(T0, T2, A0, A1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   653
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   654
		word carry = Add(R1, R1, T0, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   655
		carry += Add(R1, R1, T0, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   656
		Increment(R3, N2, carry);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   657
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   658
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   659
// R[N] - bottom half of A*B
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   660
// T[N] - temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   661
// A[N] - multiplier
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   662
// B[N] - multiplicant
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   663
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   664
void RecursiveMultiplyBottom(word *R, word *T, const word *A, const word *B, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   665
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   666
	assert(N>=2 && N%2==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   667
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   668
	if (N==2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   669
		AtomicMultiplyBottom(R, A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   670
	else if (N==4)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   671
		CombaMultiplyBottom4(R, A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   672
	else if (N==8)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   673
		CombaMultiplyBottom8(R, A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   674
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   675
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   676
		const unsigned int N2 = N/2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   677
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   678
		RecursiveMultiply(R, T, A0, B0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   679
		RecursiveMultiplyBottom(T0, T1, A1, B0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   680
		Add(R1, R1, T0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   681
		RecursiveMultiplyBottom(T0, T1, A0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   682
		Add(R1, R1, T0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   683
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   684
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   685
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   686
// R[N] --- upper half of A*B
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   687
// T[2*N] - temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   688
// L[N] --- lower half of A*B
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   689
// A[N] --- multiplier
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   690
// B[N] --- multiplicant
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   691
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   692
void RecursiveMultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   693
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   694
	assert(N>=2 && N%2==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   695
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   696
	if (N==2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   697
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   698
		AtomicMultiply(T, A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   699
		((dword *)R)[0] = ((dword *)T)[1];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   700
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   701
	else if (N==4)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   702
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   703
		CombaMultiply4(T, A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   704
		((dword *)R)[0] = ((dword *)T)[2];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   705
		((dword *)R)[1] = ((dword *)T)[3];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   706
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   707
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   708
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   709
		const unsigned int N2 = N/2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   710
		int carry;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   711
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   712
		int aComp = Compare(A0, A1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   713
		int bComp = Compare(B0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   714
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   715
		switch (2*aComp + aComp + bComp)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   716
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   717
		case -4:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   718
			Subtract(R0, A1, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   719
			Subtract(R1, B0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   720
			RecursiveMultiply(T0, T2, R0, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   721
			Subtract(T1, T1, R0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   722
			carry = -1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   723
			break;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   724
		case -2:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   725
			Subtract(R0, A1, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   726
			Subtract(R1, B0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   727
			RecursiveMultiply(T0, T2, R0, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   728
			carry = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   729
			break;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   730
		case 2:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   731
			Subtract(R0, A0, A1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   732
			Subtract(R1, B1, B0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   733
			RecursiveMultiply(T0, T2, R0, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   734
			carry = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   735
			break;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   736
		case 4:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   737
			Subtract(R0, A1, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   738
			Subtract(R1, B0, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   739
			RecursiveMultiply(T0, T2, R0, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   740
			Subtract(T1, T1, R1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   741
			carry = -1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   742
			break;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   743
		default:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   744
			SetWords(T0, 0, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   745
			carry = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   746
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   747
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   748
		RecursiveMultiply(T2, R0, A1, B1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   749
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   750
		// now T[01] holds (A1-A0)*(B0-B1), T[23] holds A1*B1
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   751
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   752
		CopyWords(R0, L+N2, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   753
		word c2 = Subtract(R0, R0, L, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   754
		c2 += Subtract(R0, R0, T0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   755
		word t = (Compare(R0, T2, N2) == -1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   756
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   757
		carry += t;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   758
		carry += Increment(R0, N2, c2+t);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   759
		carry += Add(R0, R0, T1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   760
		carry += Add(R0, R0, T3, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   761
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   762
		CopyWords(R1, T3, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   763
		assert (carry >= 0 && carry <= 2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   764
		Increment(R1, N2, carry);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   765
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   766
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   767
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   768
// R[NA+NB] - result = A*B
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   769
// T[NA+NB] - temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   770
// A[NA] ---- multiplier
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   771
// B[NB] ---- multiplicant
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   772
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   773
void AsymmetricMultiply(word *R, word *T, const word *A, unsigned int NA, const word *B, unsigned int NB)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   774
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   775
	if (NA == NB)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   776
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   777
		if (A == B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   778
			RecursiveSquare(R, T, A, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   779
		else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   780
			RecursiveMultiply(R, T, A, B, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   781
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   782
		return;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   783
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   784
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   785
	if (NA > NB)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   786
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   787
		TClassSwap(A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   788
		TClassSwap(NA, NB);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   789
		//std::swap(A, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   790
		//std::swap(NA, NB);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   791
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   792
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   793
	assert(NB % NA == 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   794
	assert((NB/NA)%2 == 0); 	// NB is an even multiple of NA
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   795
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   796
	if (NA==2 && !A[1])
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   797
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   798
		switch (A[0])
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   799
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   800
		case 0:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   801
			SetWords(R, 0, NB+2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   802
			return;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   803
		case 1:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   804
			CopyWords(R, B, NB);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   805
			R[NB] = R[NB+1] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   806
			return;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   807
		default:
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   808
			R[NB] = LinearMultiply(R, B, A[0], NB);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   809
			R[NB+1] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   810
			return;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   811
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   812
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   813
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   814
	RecursiveMultiply(R, T, A, B, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   815
	CopyWords(T+2*NA, R+NA, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   816
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   817
	unsigned i;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   818
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   819
	for (i=2*NA; i<NB; i+=2*NA)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   820
		RecursiveMultiply(T+NA+i, T, A, B+i, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   821
	for (i=NA; i<NB; i+=2*NA)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   822
		RecursiveMultiply(R+i, T, A, B+i, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   823
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   824
	if (Add(R+NA, R+NA, T+2*NA, NB-NA))
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   825
		Increment(R+NB, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   826
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   827
// R[N] ----- result = A inverse mod 2**(WORD_BITS*N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   828
// T[3*N/2] - temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   829
// A[N] ----- an odd number as input
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   830
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   831
void RecursiveInverseModPower2(word *R, word *T, const word *A, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   832
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   833
	if (N==2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   834
		AtomicInverseModPower2(R, A[0], A[1]);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   835
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   836
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   837
		const unsigned int N2 = N/2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   838
		RecursiveInverseModPower2(R0, T0, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   839
		T0[0] = 1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   840
		SetWords(T0+1, 0, N2-1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   841
		RecursiveMultiplyTop(R1, T1, T0, R0, A0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   842
		RecursiveMultiplyBottom(T0, T1, R0, A1, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   843
		Add(T0, R1, T0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   844
		TwosComplement(T0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   845
		RecursiveMultiplyBottom(R1, T1, R0, T0, N2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   846
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   847
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   848
#undef A0
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   849
#undef A1
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   850
#undef B0
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   851
#undef B1
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   852
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   853
#undef T0
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   854
#undef T1
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   855
#undef T2
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   856
#undef T3
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   857
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   858
#undef R0
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   859
#undef R1
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   860
#undef R2
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   861
#undef R3
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   862
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   863
// R[N] --- result = X/(2**(WORD_BITS*N)) mod M
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   864
// T[3*N] - temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   865
// X[2*N] - number to be reduced
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   866
// M[N] --- modulus
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   867
// U[N] --- multiplicative inverse of M mod 2**(WORD_BITS*N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   868
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   869
void MontgomeryReduce(word *R, word *T, const word *X, const word *M, const word *U, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   870
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   871
	RecursiveMultiplyBottom(R, T, X, U, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   872
	RecursiveMultiplyTop(T, T+N, X, R, M, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   873
	if (Subtract(R, X+N, T, N))
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   874
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   875
#ifdef _DEBUG
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   876
		word carry = Add(R, R, M, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   877
		assert(carry);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   878
#else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   879
		Add(R, R, M, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   880
#endif
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   881
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   882
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   883
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   884
// do a 3 word by 2 word divide, returns quotient and leaves remainder in A
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   885
static word SubatomicDivide(word *A, word B0, word B1)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   886
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   887
	// assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a word
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   888
	assert(A[2] < B1 || (A[2]==B1 && A[1] < B0));
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   889
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   890
	dword p, u;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   891
	word Q;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   892
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   893
	// estimate the quotient: do a 2 word by 1 word divide
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   894
	if (B1+1 == 0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   895
		Q = A[2];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   896
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   897
		Q = word(MAKE_DWORD(A[1], A[2]) / (B1+1));
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   898
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   899
	// now subtract Q*B from A
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   900
	p = (dword) B0*Q;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   901
	u = (dword) A[0] - LOW_WORD(p);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   902
	A[0] = LOW_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   903
	u = (dword) A[1] - HIGH_WORD(p) - (word)(0-HIGH_WORD(u)) - (dword)B1*Q;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   904
	A[1] = LOW_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   905
	A[2] += HIGH_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   906
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   907
	// Q <= actual quotient, so fix it
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   908
	while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0))
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   909
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   910
		u = (dword) A[0] - B0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   911
		A[0] = LOW_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   912
		u = (dword) A[1] - B1 - (word)(0-HIGH_WORD(u));
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   913
		A[1] = LOW_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   914
		A[2] += HIGH_WORD(u);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   915
		Q++;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   916
		assert(Q);	// shouldn't overflow
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   917
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   918
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   919
	return Q;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   920
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   921
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   922
// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   923
static inline void AtomicDivide(word *Q, const word *A, const word *B)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   924
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   925
	if (!B[0] && !B[1]) // if divisor is 0, we assume divisor==2**(2*WORD_BITS)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   926
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   927
		Q[0] = A[2];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   928
		Q[1] = A[3];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   929
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   930
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   931
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   932
		word T[4];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   933
		T[0] = A[0]; T[1] = A[1]; T[2] = A[2]; T[3] = A[3];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   934
		Q[1] = SubatomicDivide(T+1, B[0], B[1]);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   935
		Q[0] = SubatomicDivide(T, B[0], B[1]);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   936
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   937
#ifdef _DEBUG
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   938
		// multiply quotient and divisor and add remainder, make sure it equals dividend
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   939
		assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]<B[0])));
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   940
		word P[4];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   941
		AtomicMultiply(P, Q, B);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   942
		Add(P, P, T, 4);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   943
		assert(Mem::Compare((TUint8*)P, 4*WORD_SIZE, (TUint8*)A, 4*WORD_SIZE)==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   944
#endif
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   945
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   946
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   947
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   948
// for use by Divide(), corrects the underestimated quotient {Q1,Q0}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   949
static void CorrectQuotientEstimate(word *R, word *T, word *Q, const word *B, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   950
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   951
	assert(N && N%2==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   952
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   953
	if (Q[1])
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   954
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   955
		T[N] = T[N+1] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   956
		unsigned i;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   957
		for (i=0; i<N; i+=4)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   958
			AtomicMultiply(T+i, Q, B+i);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   959
		for (i=2; i<N; i+=4)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   960
			if (AtomicMultiplyAdd(T+i, Q, B+i))
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   961
				T[i+5] += (++T[i+4]==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   962
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   963
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   964
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   965
		T[N] = LinearMultiply(T, B, Q[0], N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   966
		T[N+1] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   967
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   968
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   969
#ifdef _DEBUG
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   970
	word borrow = Subtract(R, R, T, N+2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   971
	assert(!borrow && !R[N+1]);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   972
#else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   973
	Subtract(R, R, T, N+2);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   974
#endif
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   975
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   976
	while (R[N] || Compare(R, B, N) >= 0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   977
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   978
		R[N] -= Subtract(R, R, B, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   979
		Q[1] += (++Q[0]==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   980
		assert(Q[0] || Q[1]); // no overflow
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   981
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   982
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   983
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   984
// R[NB] -------- remainder = A%B
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   985
// Q[NA-NB+2] --- quotient	= A/B
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   986
// T[NA+2*NB+4] - temp work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   987
// A[NA] -------- dividend
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   988
// B[NB] -------- divisor
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   989
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   990
void Divide(word *R, word *Q, word *T, const word *A, unsigned int NA, const word *B, unsigned int NB)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   991
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   992
	assert(NA && NB && NA%2==0 && NB%2==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   993
	assert(B[NB-1] || B[NB-2]);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   994
	assert(NB <= NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   995
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   996
	// set up temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   997
	word *const TA=T;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   998
	word *const TB=T+NA+2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
   999
	word *const TP=T+NA+2+NB;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1000
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1001
	// copy B into TB and normalize it so that TB has highest bit set to 1
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1002
	unsigned shiftWords = (B[NB-1]==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1003
	TB[0] = TB[NB-1] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1004
	CopyWords(TB+shiftWords, B, NB-shiftWords);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1005
	unsigned shiftBits = WORD_BITS - BitPrecision(TB[NB-1]);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1006
	assert(shiftBits < WORD_BITS);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1007
	ShiftWordsLeftByBits(TB, NB, shiftBits);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1008
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1009
	// copy A into TA and normalize it
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1010
	TA[0] = TA[NA] = TA[NA+1] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1011
	CopyWords(TA+shiftWords, A, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1012
	ShiftWordsLeftByBits(TA, NA+2, shiftBits);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1013
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1014
	if (TA[NA+1]==0 && TA[NA] <= 1)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1015
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1016
		Q[NA-NB+1] = Q[NA-NB] = 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1017
		while (TA[NA] || Compare(TA+NA-NB, TB, NB) >= 0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1018
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1019
			TA[NA] -= Subtract(TA+NA-NB, TA+NA-NB, TB, NB);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1020
			++Q[NA-NB];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1021
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1022
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1023
	else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1024
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1025
		NA+=2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1026
		assert(Compare(TA+NA-NB, TB, NB) < 0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1027
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1028
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1029
	word BT[2];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1030
	BT[0] = TB[NB-2] + 1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1031
	BT[1] = TB[NB-1] + (BT[0]==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1032
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1033
	// start reducing TA mod TB, 2 words at a time
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1034
	for (unsigned i=NA-2; i>=NB; i-=2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1035
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1036
		AtomicDivide(Q+i-NB, TA+i-2, BT);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1037
		CorrectQuotientEstimate(TA+i-NB, TP, Q+i-NB, TB, NB);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1038
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1039
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1040
	// copy TA into R, and denormalize it
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1041
	CopyWords(R, TA+shiftWords, NB);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1042
	ShiftWordsRightByBits(R, NB, shiftBits);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1043
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1044
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1045
static inline unsigned int EvenWordCount(const word *X, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1046
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1047
	while (N && X[N-2]==0 && X[N-1]==0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1048
		N-=2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1049
	return N;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1050
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1051
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1052
// return k
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1053
// R[N] --- result = A^(-1) * 2^k mod M
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1054
// T[4*N] - temporary work space
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1055
// A[NA] -- number to take inverse of
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1056
// M[N] --- modulus
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1057
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1058
unsigned int AlmostInverse(word *R, word *T, const word *A, unsigned int NA, const word *M, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1059
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1060
	assert(NA<=N && N && N%2==0);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1061
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1062
	word *b = T;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1063
	word *c = T+N;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1064
	word *f = T+2*N;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1065
	word *g = T+3*N;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1066
	unsigned int bcLen=2, fgLen=EvenWordCount(M, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1067
	unsigned int k=0, s=0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1068
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1069
	SetWords(T, 0, 3*N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1070
	b[0]=1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1071
	CopyWords(f, A, NA);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1072
	CopyWords(g, M, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1073
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1074
	FOREVER
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1075
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1076
		word t=f[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1077
		while (!t)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1078
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1079
			if (EvenWordCount(f, fgLen)==0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1080
			{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1081
				SetWords(R, 0, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1082
				return 0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1083
			}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1084
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1085
			ShiftWordsRightByWords(f, fgLen, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1086
			if (c[bcLen-1]) bcLen+=2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1087
			assert(bcLen <= N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1088
			ShiftWordsLeftByWords(c, bcLen, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1089
			k+=WORD_BITS;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1090
			t=f[0];
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1091
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1092
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1093
		unsigned int i=0;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1094
		while (t%2 == 0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1095
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1096
			t>>=1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1097
			i++;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1098
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1099
		k+=i;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1100
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1101
		if (t==1 && f[1]==0 && EvenWordCount(f, fgLen)==2)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1102
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1103
			if (s%2==0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1104
				CopyWords(R, b, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1105
			else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1106
				Subtract(R, M, b, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1107
			return k;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1108
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1109
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1110
		ShiftWordsRightByBits(f, fgLen, i);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1111
		t=ShiftWordsLeftByBits(c, bcLen, i);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1112
		if (t)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1113
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1114
			c[bcLen] = t;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1115
			bcLen+=2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1116
			assert(bcLen <= N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1117
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1118
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1119
		if (f[fgLen-2]==0 && g[fgLen-2]==0 && f[fgLen-1]==0 && g[fgLen-1]==0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1120
			fgLen-=2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1121
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1122
		if (Compare(f, g, fgLen)==-1)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1123
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1124
			TClassSwap<word*>(f,g);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1125
			TClassSwap<word*>(b,c);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1126
			s++;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1127
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1128
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1129
		Subtract(f, f, g, fgLen);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1130
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1131
		if (Add(b, b, c, bcLen))
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1132
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1133
			b[bcLen] = 1;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1134
			bcLen+=2;
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1135
			assert(bcLen <= N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1136
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1137
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1138
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1139
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1140
// R[N] - result = A/(2^k) mod M
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1141
// A[N] - input
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1142
// M[N] - modulus
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1143
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1144
void DivideByPower2Mod(word *R, const word *A, unsigned int k, const word *M, unsigned int N)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1145
{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1146
	CopyWords(R, A, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1147
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1148
	while (k--)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1149
	{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1150
		if (R[0]%2==0)
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1151
			ShiftWordsRightByBits(R, N, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1152
		else
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1153
		{
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1154
			word carry = Add(R, R, M, N);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1155
			ShiftWordsRightByBits(R, N, 1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1156
			R[N-1] += carry<<(WORD_BITS-1);
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1157
		}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1158
	}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1159
}
cd501b96611d Revision: 200945
Mikko Sunikka <mikko.sunikka@nokia.com>
parents:
diff changeset
  1160