Initial import of qemu-2.4.1HEADmaster

1 files changed, 318 insertions, 0 deletions

diff --git a/roms/ipxe/src/arch/x86/include/bits/bigint.h b/roms/ipxe/src/arch/x86/include/bits/bigint.h
new file mode 100644
index 00000000..d3449af5
--- /dev/null
+++ b/roms/ipxe/src/arch/x86/include/bits/bigint.h
@@ -0,0 +1,318 @@
+#ifndef _BITS_BIGINT_H
+#define _BITS_BIGINT_H
+
+/** @file
+ *
+ * Big integer support
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <stdint.h>
+#include <string.h>
+
+/** Element of a big integer */
+typedef uint32_t bigint_element_t;
+
+/**
+ * Initialise big integer
+ *
+ * @v value0		Element 0 of big integer to initialise
+ * @v size		Number of elements
+ * @v data		Raw data
+ * @v len		Length of raw data
+ */
+static inline __attribute__ (( always_inline )) void
+bigint_init_raw ( uint32_t *value0, unsigned int size,
+		  const void *data, size_t len ) {
+	long pad_len = ( sizeof ( bigint_t ( size ) ) - len );
+	void *discard_D;
+	long discard_c;
+
+	/* Copy raw data in reverse order, padding with zeros */
+	__asm__ __volatile__ ( "\n1:\n\t"
+			       "movb -1(%2,%1), %%al\n\t"
+			       "stosb\n\t"
+			       "loop 1b\n\t"
+			       "xorl %%eax, %%eax\n\t"
+			       "mov %3, %1\n\t"
+			       "rep stosb\n\t"
+			       : "=&D" ( discard_D ), "=&c" ( discard_c )
+			       : "r" ( data ), "g" ( pad_len ), "0" ( value0 ),
+				 "1" ( len )
+			       : "eax" );
+}
+
+/**
+ * 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
+ */
+static inline __attribute__ (( always_inline )) void
+bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
+		 unsigned int size ) {
+	long index;
+	void *discard_S;
+	long discard_c;
+
+	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
+			       "\n1:\n\t"
+			       "lodsl\n\t"
+			       "adcl %%eax, (%3,%0,4)\n\t"
+			       "inc %0\n\t" /* Does not affect CF */
+			       "loop 1b\n\t"
+			       : "=&r" ( index ), "=&S" ( discard_S ),
+				 "=&c" ( discard_c )
+			       : "r" ( value0 ), "1" ( addend0 ), "2" ( size )
+			       : "eax" );
+}
+
+/**
+ * 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
+ */
+static inline __attribute__ (( always_inline )) void
+bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
+		      unsigned int size ) {
+	long index;
+	void *discard_S;
+	long discard_c;
+
+	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
+			       "\n1:\n\t"
+			       "lodsl\n\t"
+			       "sbbl %%eax, (%3,%0,4)\n\t"
+			       "inc %0\n\t" /* Does not affect CF */
+			       "loop 1b\n\t"
+			       : "=&r" ( index ), "=&S" ( discard_S ),
+				 "=&c" ( discard_c )
+			       : "r" ( value0 ), "1" ( subtrahend0 ),
+				 "2" ( size )
+			       : "eax" );
+}
+
+/**
+ * Rotate big integer left
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ */
+static inline __attribute__ (( always_inline )) void
+bigint_rol_raw ( uint32_t *value0, unsigned int size ) {
+	long index;
+	long discard_c;
+
+	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
+			       "\n1:\n\t"
+			       "rcll $1, (%2,%0,4)\n\t"
+			       "inc %0\n\t" /* Does not affect CF */
+			       "loop 1b\n\t"
+			       : "=&r" ( index ), "=&c" ( discard_c )
+			       : "r" ( value0 ), "1" ( size ) );
+}
+
+/**
+ * Rotate big integer right
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ */
+static inline __attribute__ (( always_inline )) void
+bigint_ror_raw ( uint32_t *value0, unsigned int size ) {
+	long discard_c;
+
+	__asm__ __volatile__ ( "clc\n\t"
+			       "\n1:\n\t"
+			       "rcrl $1, -4(%1,%0,4)\n\t"
+			       "loop 1b\n\t"
+			       : "=&c" ( discard_c )
+			       : "r" ( value0 ), "0" ( size ) );
+}
+
+/**
+ * Test if big integer is equal to zero
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ * @ret is_zero		Big integer is equal to zero
+ */
+static inline __attribute__ (( always_inline, pure )) int
+bigint_is_zero_raw ( const uint32_t *value0, unsigned int size ) {
+	void *discard_D;
+	long discard_c;
+	int result;
+
+	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Set ZF */
+			       "repe scasl\n\t"
+			       "sete %b0\n\t"
+			       : "=&a" ( result ), "=&D" ( discard_D ),
+				 "=&c" ( discard_c )
+			       : "1" ( value0 ), "2" ( size ) );
+	return result;
+}
+
+/**
+ * Compare big integers
+ *
+ * @v value0		Element 0 of big integer
+ * @v reference0	Element 0 of reference big integer
+ * @v size		Number of elements
+ * @ret geq		Big integer is greater than or equal to the reference
+ */
+static inline __attribute__ (( always_inline, pure )) int
+bigint_is_geq_raw ( const uint32_t *value0, const uint32_t *reference0,
+		    unsigned int size ) {
+	const bigint_t ( size ) __attribute__ (( may_alias )) *value =
+		( ( const void * ) value0 );
+	const bigint_t ( size ) __attribute__ (( may_alias )) *reference =
+		( ( const void * ) reference0 );
+	void *discard_S;
+	void *discard_D;
+	long discard_c;
+	int result;
+
+	__asm__ __volatile__ ( "std\n\t"
+			       "\n1:\n\t"
+			       "lodsl\n\t"
+			       "scasl\n\t"
+			       "loope 1b\n\t"
+			       "setae %b0\n\t"
+			       "cld\n\t"
+			       : "=q" ( result ), "=&S" ( discard_S ),
+				 "=&D" ( discard_D ), "=&c" ( discard_c )
+			       : "0" ( 0 ), "1" ( &value->element[ size - 1 ] ),
+				 "2" ( &reference->element[ size - 1 ] ),
+				 "3" ( size )
+			       : "eax" );
+	return result;
+}
+
+/**
+ * Test if bit is set in big integer
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ * @v bit		Bit to test
+ * @ret is_set		Bit is set
+ */
+static inline __attribute__ (( always_inline )) int
+bigint_bit_is_set_raw ( const uint32_t *value0, unsigned int size,
+			unsigned int bit ) {
+	const bigint_t ( size ) __attribute__ (( may_alias )) *value =
+		( ( const void * ) value0 );
+	unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) );
+	unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) );
+
+	return ( value->element[index] & ( 1 << subindex ) );
+}
+
+/**
+ * Find highest bit set in big integer
+ *
+ * @v value0		Element 0 of big integer
+ * @v size		Number of elements
+ * @ret max_bit		Highest bit set + 1 (or 0 if no bits set)
+ */
+static inline __attribute__ (( always_inline )) int
+bigint_max_set_bit_raw ( const uint32_t *value0, unsigned int size ) {
+	long discard_c;
+	int result;
+
+	__asm__ __volatile__ ( "\n1:\n\t"
+			       "bsrl -4(%2,%1,4), %0\n\t"
+			       "loopz 1b\n\t"
+			       "rol %1\n\t" /* Does not affect ZF */
+			       "rol %1\n\t"
+			       "leal 1(%k0,%k1,8), %k0\n\t"
+			       "jnz 2f\n\t"
+			       "xor %0, %0\n\t"
+			       "\n2:\n\t"
+			       : "=&r" ( result ), "=&c" ( discard_c )
+			       : "r" ( value0 ), "1" ( size ) );
+	return result;
+}
+
+/**
+ * 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 ) {
+	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 %3, %2\n\t"
+			       "rep stosl\n\t"
+			       : "=&D" ( discard_D ), "=&S" ( discard_S ),
+				 "=&c" ( discard_c )
+			       : "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 ) {
+	void *discard_D;
+	void *discard_S;
+	long discard_c;
+
+	__asm__ __volatile__ ( "rep movsl\n\t"
+			       : "=&D" ( discard_D ), "=&S" ( discard_S ),
+				 "=&c" ( discard_c )
+			       : "0" ( dest0 ), "1" ( source0 ),
+				 "2" ( dest_size )
+			       : "eax" );
+}
+
+/**
+ * Finalise big integer
+ *
+ * @v value0		Element 0 of big integer to finalise
+ * @v size		Number of elements
+ * @v out		Output buffer
+ * @v len		Length of output buffer
+ */
+static inline __attribute__ (( always_inline )) void
+bigint_done_raw ( const uint32_t *value0, unsigned int size __unused,
+		  void *out, size_t len ) {
+	void *discard_D;
+	long discard_c;
+
+	/* Copy raw data in reverse order */
+	__asm__ __volatile__ ( "\n1:\n\t"
+			       "movb -1(%2,%1), %%al\n\t"
+			       "stosb\n\t"
+			       "loop 1b\n\t"
+			       : "=&D" ( discard_D ), "=&c" ( discard_c )
+			       : "r" ( value0 ), "0" ( out ), "1" ( len )
+			       : "eax" );
+}
+
+extern void bigint_multiply_raw ( const uint32_t *multiplicand0,
+				  const uint32_t *multiplier0,
+				  uint32_t *value0, unsigned int size );
+
+#endif /* _BITS_BIGINT_H */