diff options
Diffstat (limited to 'qemu/roms/ipxe/src/arch/x86/include/bits/bigint.h')
| -rw-r--r-- | qemu/roms/ipxe/src/arch/x86/include/bits/bigint.h | 318 |
1 files changed, 318 insertions, 0 deletions
diff --git a/qemu/roms/ipxe/src/arch/x86/include/bits/bigint.h b/qemu/roms/ipxe/src/arch/x86/include/bits/bigint.h new file mode 100644 index 000000000..d3449af5a --- /dev/null +++ b/qemu/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 */ |