bigtypes.h

基于SD卡的软实现CSP程序

	//////// addition/subtraction ////////
	
#if defined(NO_TEMPLATE_INLINE_ASSEMBLY) && defined(ASSEMBLY_INTEL_SYNTAX)
	void BorlandAdd( void *a, void *b, u32 c )
	{
		ASSEMBLY_BLOCK // BorlandC, x86, 32-bit words
		{
			mov esi, b
			mov edi, a
			mov ecx, c
		        
			// unrolled loop since word count is a multiple of 4 >= 4
			mov eax, [ esi ]
			xor edx, edx  // edx used later to index later words >= 4
		        
			add [ edi ]
			, eax  // and now we can use ADD instead of ADC on the first addition
			mov eax, [ esi + 4 ]
			adc [ edi + 4 ], eax
			mov eax, [ esi + 8 ]
			adc [ edi + 8 ], eax
			mov eax, [ esi + 12 ]
			adc [ edi + 12 ], eax
		        
			jecxz done_already
		        
		next_word:
			inc edx
			inc edx
		        
			// unrolled loop since word count is a multiple of 4 >= 4
			mov eax, [ esi + edx * 8 ]
			adc [ edi + edx * 8 ], eax
			mov eax, [ esi + edx * 8 + 4 ]
			adc [ edi + edx * 8 + 4 ], eax
			mov eax, [ esi + edx * 8 + 8 ]
			adc [ edi + edx * 8 + 8 ], eax
			mov eax, [ esi + edx * 8 + 12 ]
			adc [ edi + edx * 8 + 12 ], eax
		        
			loop next_word
		        
		done_already:
		}
	}
	
#endif
	
	// a += b
	BIGONETYPE void add ( T &a, T &b )
	{
#if defined(NO_TEMPLATE_INLINE_ASSEMBLY) && defined(ASSEMBLY_INTEL_SYNTAX)
		const u32 qc1 = BIGWORDCOUNT( T ) / 4 - 1;
		
		BorlandAdd( a, b, qc1 );
		
#elif defined(ASSEMBLY_INTEL_SYNTAX)
		
		const u32 qc1 = BIGWORDCOUNT( T ) / 4 - 1;
		
		ASSEMBLY_BLOCK // VS.NET, x86, 32-bit words
		{
		        mov esi, b
		        mov edi, a
		        mov ecx, qc1
		
		        // unrolled loop since word count is a multiple of 4 >= 4
		        mov eax, [ esi ]
		        xor edx, edx  // edx used later to index later words >= 4
		
		        add [ edi ], eax  // and now we can use ADD instead of ADC on the first addition
		        mov eax, [ esi + 4 ]
		        adc [ edi + 4 ], eax
		        mov eax, [ esi + 8 ]
		        adc [ edi + 8 ], eax
		        mov eax, [ esi + 12 ]
		        adc [ edi + 12 ], eax
		
		        jecxz done_already
		
	        next_word:
		        inc edx
		        inc edx
		
		        // unrolled loop since word count is a multiple of 4 >= 4
		        mov eax, [ esi + edx * 8 ]
		        adc [ edi + edx * 8 ], eax
		        mov eax, [ esi + edx * 8 + 4 ]
		        adc [ edi + edx * 8 + 4 ], eax
		        mov eax, [ esi + edx * 8 + 8 ]
		        adc [ edi + edx * 8 + 8 ], eax
		        mov eax, [ esi + edx * 8 + 12 ]
		        adc [ edi + edx * 8 + 12 ], eax
		
		        loop next_word
		
	        done_already:
		}
#else
		register word carry = 0;
		
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word a_i = a[ ii ];
			word b_i = b[ ii ];
			a[ ii ] += b_i + carry;
		
			carry = ( ( a_i & ( WORDALLBITS >> 1 ) ) + ( b_i & ( WORDALLBITS >> 1 ) ) + carry ) >> ( WORDBITS - 1 );
			carry += ( a_i >> ( WORDBITS - 1 ) ) + ( b_i >> ( WORDBITS - 1 ) );
			carry >>= 1;
		}
		
#endif
		
	}
	
	// ++n
	BIGONETYPE void increment( T &n )
	{
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
			if ( ++n[ ii ] )
				break;
	}
	
#if defined(NO_TEMPLATE_INLINE_ASSEMBLY) && defined(ASSEMBLY_INTEL_SYNTAX)
	void BorlandSubtract( void *a, void *b, u32 c )
	{
		ASSEMBLY_BLOCK // BorlandC, x86, 32-bit words
		{
			mov esi, b
			mov edi, a
			mov ecx, c
		        
			// unrolled loop since word count is a multiple of 4 >= 4
			mov eax, [ esi ]
			xor edx, edx  // edx used later to index later words >= 4
		        
			add [ edi ]
			, eax  // and now we can use ADD instead of ADC on the first addition
			mov eax, [ esi + 4 ]
			adc [ edi + 4 ], eax
			mov eax, [ esi + 8 ]
			adc [ edi + 8 ], eax
			mov eax, [ esi + 12 ]
			adc [ edi + 12 ], eax
		        
			jecxz done_already
		        
		next_word:
			inc edx
			inc edx
		        
			// unrolled loop since word count is a multiple of 4 >= 4
			mov eax, [ esi + edx * 8 ]
			adc [ edi + edx * 8 ], eax
			mov eax, [ esi + edx * 8 + 4 ]
			adc [ edi + edx * 8 + 4 ], eax
			mov eax, [ esi + edx * 8 + 8 ]
			adc [ edi + edx * 8 + 8 ], eax
			mov eax, [ esi + edx * 8 + 12 ]
			adc [ edi + edx * 8 + 12 ], eax
		        
			loop next_word
		        
		done_already:
		}
	}
	
#endif
	
	// a -= b
	BIGONETYPE void subtract( T &a, T &b )
	{
#if defined(NO_TEMPLATE_INLINE_ASSEMBLY) && defined(ASSEMBLY_INTEL_SYNTAX)
		const u32 qc1 = BIGWORDCOUNT( T ) / 4 - 1;
		
		BorlandSubtract( a, b, qc1 );
		
#elif defined(ASSEMBLY_INTEL_SYNTAX)
		
		const u32 qc1 = BIGWORDCOUNT( T ) / 4 - 1;
		
		ASSEMBLY_BLOCK // VS.NET, x86, 32-bit words
		{
		        mov esi, b
		        mov edi, a
		        mov ecx, qc1
		
		        // unrolled loop since word count is a multiple of 4 >= 4
		        mov eax, [ esi ]
		        xor edx, edx  // edx used later to index later words >= 4
		        sub [ edi ], eax  // first subtraction doesn't need to borrow
		        mov eax, [ esi + 4 ]
		        sbb [ edi + 4 ], eax
		        mov eax, [ esi + 8 ]
		        sbb [ edi + 8 ], eax
		        mov eax, [ esi + 12 ]
		        sbb [ edi + 12 ], eax
		
		        jecxz done_already
		
	        next_word:
		        inc edx
		        inc edx
		
		        // unrolled loop since word count is a multiple of 4 >= 4
		        mov eax, [ esi + edx * 8 ]
		        sbb [ edi + edx * 8 ], eax
		        mov eax, [ esi + edx * 8 + 4 ]
		        sbb [ edi + edx * 8 + 4 ], eax
		        mov eax, [ esi + edx * 8 + 8 ]
		        sbb [ edi + edx * 8 + 8 ], eax
		        mov eax, [ esi + edx * 8 + 12 ]
		        sbb [ edi + edx * 8 + 12 ], eax
		
		        loop next_word
		
	        done_already:
		}
#else
		register word borrow = 0;
		
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word a_i = a[ ii ];
			word b_i = b[ ii ];
			a[ ii ] -= b_i + borrow;
		
			borrow = ( ( a_i & ( WORDALLBITS >> 1 ) ) - ( b_i & ( WORDALLBITS >> 1 ) ) - borrow ) >> ( WORDBITS - 1 );
			borrow += ( b_i >> ( WORDBITS - 1 ) ) - ( a_i >> ( WORDBITS - 1 ) );
			++borrow;
			borrow >>= 1;
		}
		
#endif
		
	}
	
	// --n
	BIGONETYPE void decrement( T &n )
	{
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
			if ( n[ ii ] -- )
				break;
	}
	
	
	//////// negation ////////
	
	// n = -n
	BIGONETYPE void negate( T &n )
	{
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
			n[ ii ] = ~n[ ii ];
			
		increment( n );
	}
	
	
	//////// multiplication ////////
	
	// a *= a, unsigned
	BIGONETYPE void usquare( T &a )
	{
		T a0, a1;
		
		set ( a0, a )
		
		;
		set ( a1, a )
		
		;
		zero( a );
		
		u32 shifts = 0;
		
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word w_i = a0[ ii ];
			
			u16 ctr = WORDBITS;
			
			while ( w_i )
			{
				if ( w_i & 1 )
				{
					if ( shifts )
					{
						shiftLeft( a1, shifts );
						shifts = 0;
					}
					
					add ( a, a1 )
					
					;
				}
				
				w_i >>= 1;
				++shifts;
				--ctr;
			}
			
			shifts += ctr;
		}
	}
	
	// m = a * b (&a != &b != &m), unsigned
	BIGTWOTYPES void umultiply( T &a0, T &b0, Bigger &m )
	{
		Bigger a;
		usetlow( a, a0 );
		
		zero( m );
		
		u32 shifts = 0;
		
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word w_i = b0[ ii ];
			
			u16 ctr = WORDBITS;
			
			while ( w_i )
			{
				if ( w_i & 1 )
				{
					if ( shifts )
					{
						shiftLeft( a, shifts );
						shifts = 0;
					}
					
					add ( m, a )
					
					;
				}
				
				w_i >>= 1;
				++shifts;
				--ctr;
			}
			
			shifts += ctr;
		}
	}
	
	// a *= b (&a != &b), unsigned
	BIGTWOTYPES void umultiply( Bigger &a0, T &b0 )
	{
		Bigger a;
		
		set ( a, a0 )
		
		;
		
		zero( a0 );
		
		u32 shifts = 0;
		
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word w_i = b0[ ii ];
			
			u16 ctr = WORDBITS;
			
			while ( w_i )
			{
				if ( w_i & 1 )
				{
					if ( shifts )
					{
						shiftLeft( a, shifts );
						shifts = 0;
					}
					
					add ( a0, a )
					
					;
				}
				
				w_i >>= 1;
				++shifts;
				--ctr;
			}
			
			shifts += ctr;
		}
	}
	
	// a *= a, signed
	BIGONETYPE void ssquare( T &a )
	{
		T a0, a1;
		
		if ( BIGHIGHBIT( a ) )
			negate( a );
			
		set ( a0, a )
		
		;
		set ( a1, a )
		
		;
		zero( a );
		
		u32 shifts = 0;
		
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word w_i = a0[ ii ];
			
			u16 ctr = WORDBITS;
			
			while ( w_i )
			{
				if ( w_i & 1 )
				{
					if ( shifts )
					{
						shiftLeft( a1, shifts );
						shifts = 0;
					}
					
					add ( a, a1 )
					
					;
				}
				
				w_i >>= 1;
				++shifts;
				--ctr;
			}
			
			shifts += ctr;
		}
	}
	
	// m = a * b (&a != &b != &m), signed
	BIGTWOTYPES void smultiply( T &a0, T &b0, Bigger &m )
	{
		Bigger a;
		ssetlow( a, a0 );
		
		word sign_a = BIGHIGHBIT( a );
		
		if ( sign_a )
			negate( a );
			
		T b;
		
		set ( b, b0 )
		
		;
		
		word sign_b = BIGHIGHBIT( b );
		
		if ( sign_b )
			negate( b );
			
		zero( m );
		
		u32 shifts = 0;
		
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word w_i = b[ ii ];
			
			u16 ctr = WORDBITS;
			
			while ( w_i )
			{
				if ( w_i & 1 )
				{
					if ( shifts )
					{
						shiftLeft( a, shifts );
						shifts = 0;
					}
					
					add ( m, a )
					
					;
				}
				
				w_i >>= 1;
				++shifts;
				--ctr;
			}
			
			shifts += ctr;
		}
		
		if ( sign_a ^ sign_b )
			negate( m );
	}
	
	// a *= b (&a != &b), signed
	BIGTWOTYPES void smultiply( Bigger &a0, T &b0 )
	{
		Bigger a;
		ssetlow( a, a0 );
		
		word sign_a = BIGHIGHBIT( a );
		
		if ( sign_a )
			negate( a );
			
		T b;
		
		set ( b, b0 )
		
		;
		
		word sign_b = BIGHIGHBIT( b );
		
		if ( sign_b )
			negate( b );
			
		zero( a0 );
		
		u32 shifts = 0;
		
		for ( u32 ii = 0; ii < BIGWORDCOUNT( T ); ++ii )
		{
			word w_i = b[ ii ];
			
			u16 ctr = WORDBITS;
			
			while ( w_i )
			{
				if ( w_i & 1 )
				{
					if ( shifts )
					{
						shiftLeft( a, shifts );
						shifts = 0;
					}
					
					add ( a0, a )
					
					;
				}
				
				w_i >>= 1;
				++shifts;
				--ctr;
			}
			
			shifts += ctr;
		}
		
		if ( sign_a ^ sign_b )
			negate( a0 );
	}
	
	
	//////// division/remainder ////////
	
	// {q, r} = a / b (&q != &r), unsigned
	BIGONETYPE void udivide( T &a, T &b0, T &q, T &r )
	{
		T b;
		
		set ( b, b0 )
		
		;
		set ( r, a )
		
		;
		zero( q );
		
		u32 shifts = 1;
		
		// sort of: shift b left until b > r, then shift back one
		if ( !BIGHIGHBIT( b ) && ugreater( r, b ) )
		{
			s32 ii, jj;
			
			// shift by words if possible
			
			for ( ii = BIGWORDCOUNT( T ) - 1; ii >= 0; --ii )
				if ( r[ ii ] )
					break;
					
			for ( jj = ii; jj >= 0; --jj )
				if ( b[ jj ] )
					break;
					
			if ( ii != jj )
			{
				shifts = ( ii - jj ) * WORDBITS;
				shiftLeft( b, shifts );
				++shifts;
			}
			
			while ( !BIGHIGHBIT( b ) && ugreater( r, b ) )
			{
				shiftLeft1( b );
				
				++shifts;
			}
			
			while ( ugreater( b, r ) )
			{
				ushiftRight1( b );
				
				--shifts;