src/arch/x86/include/bits/bigint.h

#ifndef _BITS_BIGINT_H
#define _BITS_BIGINT_H

/** @file
 *
 * Big integer support
 */

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
FILE_SECBOOT ( PERMITTED );

#include <stdint.h>

/** Element of a big integer */
typedef uint32_t bigint_element_t;

/**
 * Add big integers
 *
 * @v addend0		Element 0 of big integer to add
 * @v value0		Element 0 of big integer to be added to
 * @v size		Number of elements
 * @ret carry		Carry flag
 */
static inline __attribute__ (( always_inline )) int
bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
		 unsigned int size ) {
	bigint_t ( size ) __attribute__ (( may_alias )) *value =
		( ( void * ) value0 );
	long index;
	void *discard_S;
	long discard_c;
	int carry;

	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
			       "\n1:\n\t"
			       "lodsl\n\t"
			       "adcl %%eax, (%5,%0,4)\n\t"
			       "inc %0\n\t" /* Does not affect CF */
			       "loop 1b\n\t"
			       : "=&r" ( index ), "=&S" ( discard_S ),
				 "=&c" ( discard_c ), "=@ccc" ( carry ),
				 "+m" ( *value )
			       : "r" ( value0 ), "1" ( addend0 ), "2" ( size )
			       : "eax" );
	return carry;
}

/**
 * Subtract big integers
 *
 * @v subtrahend0	Element 0 of big integer to subtract
 * @v value0		Element 0 of big integer to be subtracted from
 * @v size		Number of elements
 * @ret borrow		Borrow flag
 */
static inline __attribute__ (( always_inline )) int
bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
		      unsigned int size ) {
	bigint_t ( size ) __attribute__ (( may_alias )) *value =
		( ( void * ) value0 );
	long index;
	void *discard_S;
	long discard_c;
	int borrow;

	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
			       "\n1:\n\t"
			       "lodsl\n\t"
			       "sbbl %%eax, (%5,%0,4)\n\t"
			       "inc %0\n\t" /* Does not affect CF */
			       "loop 1b\n\t"
			       : "=&r" ( index ), "=&S" ( discard_S ),
				 "=&c" ( discard_c ), "=@ccc" ( borrow ),
				 "+m" ( *value )
			       : "r" ( value0 ), "1" ( subtrahend0 ),
				 "2" ( size )
			       : "eax" );
	return borrow;
}

/**
 * Shift big integer left
 *
 * @v value0		Element 0 of big integer
 * @v size		Number of elements
 * @ret out		Bit shifted out
 */
static inline __attribute__ (( always_inline )) int
bigint_shl_raw ( uint32_t *value0, unsigned int size ) {
	bigint_t ( size ) __attribute__ (( may_alias )) *value =
		( ( void * ) value0 );
	long index;
	long discard_c;
	int out;

	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
			       "\n1:\n\t"
			       "rcll $1, (%4,%0,4)\n\t"
			       "inc %0\n\t" /* Does not affect CF */
			       "loop 1b\n\t"
			       : "=&r" ( index ), "=&c" ( discard_c ),
				 "=@ccc" ( out ), "+m" ( *value )
			       : "r" ( value0 ), "1" ( size ) );
	return out;
}

/**
 * Shift big integer right
 *
 * @v value0		Element 0 of big integer
 * @v size		Number of elements
 * @ret out		Bit shifted out
 */
static inline __attribute__ (( always_inline )) int
bigint_shr_raw ( uint32_t *value0, unsigned int size ) {
	bigint_t ( size ) __attribute__ (( may_alias )) *value =
		( ( void * ) value0 );
	long discard_c;
	int out;

	__asm__ __volatile__ ( "clc\n\t"
			       "\n1:\n\t"
			       "rcrl $1, -4(%3,%0,4)\n\t"
			       "loop 1b\n\t"
			       : "=&c" ( discard_c ), "=@ccc" ( out ),
				 "+m" ( *value )
			       : "r" ( value0 ), "0" ( size ) );
	return out;
}

/**
 * Grow big integer
 *
 * @v source0		Element 0 of source big integer
 * @v source_size	Number of elements in source big integer
 * @v dest0		Element 0 of destination big integer
 * @v dest_size		Number of elements in destination big integer
 */
static inline __attribute__ (( always_inline )) void
bigint_grow_raw ( const uint32_t *source0, unsigned int source_size,
		  uint32_t *dest0, unsigned int dest_size ) {
	bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest =
		( ( void * ) dest0 );
	long pad_size = ( dest_size - source_size );
	void *discard_D;
	void *discard_S;
	long discard_c;

	__asm__ __volatile__ ( "rep movsl\n\t"
			       "xorl %%eax, %%eax\n\t"
			       "mov %4, %2\n\t"
			       "rep stosl\n\t"
			       : "=&D" ( discard_D ), "=&S" ( discard_S ),
				 "=&c" ( discard_c ), "+m" ( *dest )
			       : "g" ( pad_size ), "0" ( dest0 ),
				 "1" ( source0 ), "2" ( source_size )
			       : "eax" );
}

/**
 * Shrink big integer
 *
 * @v source0		Element 0 of source big integer
 * @v source_size	Number of elements in source big integer
 * @v dest0		Element 0 of destination big integer
 * @v dest_size		Number of elements in destination big integer
 */
static inline __attribute__ (( always_inline )) void
bigint_shrink_raw ( const uint32_t *source0, unsigned int source_size __unused,
		    uint32_t *dest0, unsigned int dest_size ) {
	bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest =
		( ( void * ) dest0 );
	void *discard_D;
	void *discard_S;
	long discard_c;

	__asm__ __volatile__ ( "rep movsl\n\t"
			       : "=&D" ( discard_D ), "=&S" ( discard_S ),
				 "=&c" ( discard_c ), "+m" ( *dest )
			       : "0" ( dest0 ), "1" ( source0 ),
				 "2" ( dest_size )
			       : "eax" );
}

/**
 * Multiply big integer elements
 *
 * @v multiplicand	Multiplicand element
 * @v multiplier	Multiplier element
 * @v result		Result element
 * @v carry		Carry element
 */
static inline __attribute__ (( always_inline )) void
bigint_multiply_one ( const uint32_t multiplicand, const uint32_t multiplier,
		      uint32_t *result, uint32_t *carry ) {
	uint32_t discard_a;

	__asm__ __volatile__ ( /* Perform multiplication */
			       "mull %3\n\t"
			       /* Accumulate carry */
			       "addl %5, %0\n\t"
			       "adcl $0, %1\n\t"
			       /* Accumulate result */
			       "addl %0, %2\n\t"
			       "adcl $0, %1\n\t"
			       : "=&a" ( discard_a ),
				 "=&d" ( *carry ),
				 "+m" ( *result )
			       : "g" ( multiplicand ),
				 "0" ( multiplier ),
				 "r" ( *carry ) );
}

#endif /* _BITS_BIGINT_H */