bigint.h File Reference

Big integer support. More...

#include <stdint.h>
#include <string.h>

Go to the source code of this file.

Typedefs
typedef uint32_t	bigint_element_t
	Element of a big integer. More...

Functions
	FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
static	__attribute__ ((always_inline)) void bigint_init_raw(uint32_t *value0
	Initialise big integer. More...
__asm__	__volatile__ ("\n1:\n\t" "movb -1(%3,%1), %%al\n\t" "stosb\n\t" "loop 1b\n\t" "xorl %%eax, %%eax\n\t" "mov %4, %1\n\t" "rep stosb\n\t" :"=&D"(discard_D), "=&c"(discard_c), "+m"(*value) :"r"(data), "g"(pad_len), "0"(value0), "1"(len) :"eax")
__asm__	__volatile__ ("xor %0, %0\n\t" "\n1:\n\t" "lodsl\n\t" "adcl %%eax, (%4,%0,4)\n\t" "inc %0\n\t" "loop 1b\n\t" :"=&r"(index), "=&S"(discard_S), "=&c"(discard_c), "+m"(*value) :"r"(value0), "1"(addend0), "2"(size) :"eax")
__asm__	__volatile__ ("xor %0, %0\n\t" "\n1:\n\t" "lodsl\n\t" "sbbl %%eax, (%4,%0,4)\n\t" "inc %0\n\t" "loop 1b\n\t" :"=&r"(index), "=&S"(discard_S), "=&c"(discard_c), "+m"(*value) :"r"(value0), "1"(subtrahend0), "2"(size) :"eax")
__asm__	__volatile__ ("xor %0, %0\n\t" "\n1:\n\t" "rcll $1, (%3,%0,4)\n\t" "inc %0\n\t" "loop 1b\n\t" :"=&r"(index), "=&c"(discard_c), "+m"(*value) :"r"(value0), "1"(size))
__asm__	__volatile__ ("clc\n\t" "\n1:\n\t" "rcrl $1, -4(%2,%0,4)\n\t" "loop 1b\n\t" :"=&c"(discard_c), "+m"(*value) :"r"(value0), "0"(size))
static	__attribute__ ((always_inline, pure)) int bigint_is_zero_raw(const uint32_t *value0
	Test if big integer is equal to zero. More...
__asm__	__volatile__ ("xor %0, %0\n\t" "repe scasl\n\t" "sete %b0\n\t" :"=&a"(result), "=&D"(discard_D), "=&c"(discard_c) :"1"(value0), "2"(size))
__asm__	__volatile__ ("\n1:\n\t" "movl -4(%3, %1, 4), %k2\n\t" "cmpl -4(%4, %1, 4), %k2\n\t" "loope 1b\n\t" "setae %b0\n\t" :"=q"(result), "=&c"(discard_c), "=&r"(discard_tmp) :"r"(value0), "r"(reference0), "0"(0), "1"(size))
	return (value->element[index] &(1<< subindex))
__asm__	__volatile__ ("\n1:\n\t" "bsrl -4(%2,%1,4), %0\n\t" "loopz 1b\n\t" "rol %1\n\t" "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))
__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")
__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")
__asm__	__volatile__ ("\n1:\n\t" "movb -1(%3,%1), %%al\n\t" "stosb\n\t" "loop 1b\n\t" :"=&D"(discard_D), "=&c"(discard_c), "+m"(*out_bytes) :"r"(value0), "0"(out), "1"(len) :"eax")
void	bigint_multiply_raw (const uint32_t *multiplicand0, const uint32_t *multiplier0, uint32_t *value0, unsigned int size)
	Multiply big integers. More...

Variables
static unsigned int	size
static unsigned int const void *	data
static unsigned int const void size_t	len
long	pad_len = ( sizeof ( *value ) - len )
void *	discard_D
long	discard_c
static uint32_t *	value0
long	index = ( bit / ( 8 * sizeof ( value->element[0] ) ) )
void *	discard_S
int	result
static const uint32_t *	reference0
long	discard_tmp
static unsigned int unsigned int	bit
unsigned int	subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) )
static unsigned int	source_size
static unsigned int uint32_t *	dest0
static unsigned int uint32_t unsigned int	dest_size
long	pad_size = ( dest_size - source_size )
static unsigned int source_size	__unused
static unsigned int size void *	out

Detailed Description

Big integer support.

Definition in file bigint.h.

Typedef Documentation

bigint_element_t

typedef uint32_t bigint_element_t

Element of a big integer.

Definition at line 15 of file bigint.h.

Function Documentation

FILE_LICENCE()

FILE_LICENCE

(

GPL2_OR_LATER_OR_UBDL

)

__attribute__() [1/2]

static __attribute__ ( (always_inline)  )

inlinestatic

Initialise big integer.

Finalise big integer.

Shrink big integer.

Grow big integer.

Find highest bit set in big integer.

Test if bit is set in big integer.

Rotate big integer right.

Rotate big integer left.

Subtract big integers.

Add big integers.

Parameters

value0	Element 0 of big integer to initialise
size	Number of elements
data	Raw data
len	Length of raw data
addend0	Element 0 of big integer to add
value0	Element 0 of big integer to be added to
size	Number of elements
subtrahend0	Element 0 of big integer to subtract
value0	Element 0 of big integer to be subtracted from
size	Number of elements
value0	Element 0 of big integer
size	Number of elements
value0	Element 0 of big integer
size	Number of elements
bit	Bit to test

Return values

is_set

Bit is set

Parameters

value0	Element 0 of big integer
size	Number of elements

Return values

max_bit

Highest bit set + 1 (or 0 if no bits set)

Parameters

source0	Element 0 of source big integer
source_size	Number of elements in source big integer
dest0	Element 0 of destination big integer
dest_size	Number of elements in destination big integer
value0	Element 0 of big integer to finalise
size	Number of elements
out	Output buffer
len	Length of output buffer

__volatile__() [1/11]

__asm__ __volatile__	(	"\n1:\n\t" "movb -	1%3,%1,
		%%al\n\t" "stosb\n\t" "loop 1b\n\t" "xorl %%	eax,
		%%eax\n\t" "mov %	4
	)

Referenced by __attribute__(), _dump_regs(), apm_poweroff(), bigint_multiply_raw(), bios_cpu_nap(), bios_currticks(), bios_getchar(), bios_handle_cup(), bios_handle_dectcem_reset(), bios_handle_dectcem_set(), bios_handle_ed(), bios_inject(), bios_inject_startup(), bios_iskey(), bios_putchar(), bios_reboot(), bochsbp(), bzimage_exec(), call_bootsector(), com32_cfarcall(), com32_exec_loop(), com32_farcall(), com32_intcall(), comboot_exec_loop(), comboot_force_text_mode(), copy_from_real_libkir(), copy_to_real_libkir(), efix86_cpu_nap(), elfboot_exec(), extmemsize_88(), extmemsize_e801(), fake_e820(), gdbmach_breakpoint(), gdbmach_handler(), gdbmach_update(), hook_comboot_interrupts(), i386_readq(), i386_writeq(), int13_hook_vector(), int13_load_eltorito(), int13_load_mbr(), int13con_init(), int22(), interrupt(), IOAPI_INLINE(), iounmap_pages(), librm_test_exec(), meme820(), multiboot_exec(), nbi_boot16(), nbi_boot32(), pcibios_discover(), pcibios_read(), pcibios_write(), pxe_activate(), pxe_start_nbp(), rdtsc_raw(), rdtsc_scaled(), rtc_entropy_check(), rtc_get_noise(), rtc_hook_isr(), sdi_exec(), undi_load(), undinet_call(), undinet_poll(), vesafb_font(), vesafb_init(), vesafb_mode_info(), vesafb_mode_list(), vesafb_restore(), and vesafb_set_mode().

__volatile__() [2/11]

__asm__ __volatile__	(	"xor %	0,
		%0\n\t" "\n1:\n\t" "lodsl\n\t" "adcl %%	eax
	)

__volatile__() [3/11]

__asm__ __volatile__	(	"xor %	0,
		%0\n\t" "\n1:\n\t" "lodsl\n\t" "sbbl %%	eax
	)

__volatile__() [4/11]

__asm__ __volatile__	(	"xor %	0,
		%0\n\t" "\n1:\n\t" "rcll	$1
	)

__volatile__() [5/11]

__asm__ __volatile__

(

"clc\n\t" "\n1:\n\t" "rcrl

$1

)

__attribute__() [2/2]

static __attribute__ ( (always_inline, pure)  ) const

inlinestatic

Test if big integer is equal to zero.

Compare big integers.

Parameters

value0	Element 0 of big integer
size	Number of elements

Return values

is_zero

Big integer is equal to zero

Parameters

value0	Element 0 of big integer
reference0	Element 0 of reference big integer
size	Number of elements

Return values

geq	Big integer is greater than or equal to the reference

__volatile__() [6/11]

__asm__ __volatile__

(

"xor %

0

)

__volatile__() [7/11]

__asm__ __volatile__	(	"\n1:\n\t" "movl -	4%3, %1, 4,
		%k2\n\t" "cmpl -	4%4, %1, 4
	)

return()

return

(

value->element &

(1<< subindex)[index]

)

__volatile__() [8/11]

__asm__ __volatile__	(	"\n1:\n\t" "bsrl -	4%2,%1,4,
		%0\n\t" "loopz 1b\n\t" "rol %1\n\t" "rol %1\n\t" "leal	1%k0,%k1, 8,
		%k0\n\t" "jnz 2f\n\t" "xor %	0
	)

__volatile__() [9/11]

__asm__ __volatile__	(	"rep movsl\n\t" "xorl %%	eax,
		%%eax\n\t" "mov %	4
	)

__volatile__() [10/11]

__asm__ __volatile__

(

)

__volatile__() [11/11]

__asm__ __volatile__

(

"\n1:\n\t" "movb -

1%3,%1

)

bigint_multiply_raw()

void bigint_multiply_raw	(	const uint32_t *	multiplicand0,
		const uint32_t *	multiplier0,
		uint32_t *	result0,
		unsigned int	size
	)

Multiply big integers.

Parameters

multiplicand0	Element 0 of big integer to be multiplied
multiplier0	Element 0 of big integer to be multiplied
result0	Element 0 of big integer to hold result
size	Number of elements

Definition at line 43 of file x86_bigint.c.

                                                                  {
        const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
                ( ( const void * ) multiplicand0 );
        const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
                ( ( const void * ) multiplier0 );
        bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
                ( ( void * ) result0 );
        unsigned int i;
        unsigned int j;
        uint32_t multiplicand_element;
        uint32_t multiplier_element;
        uint32_t *result_elements;
        uint32_t discard_a;
        uint32_t discard_d;
        long index;

        /* Zero result */
        memset ( result, 0, sizeof ( *result ) );

        /* Multiply integers one element at a time */
        for ( i = 0 ; i < size ; i++ ) {
                multiplicand_element = multiplicand->element[i];
                for ( j = 0 ; j < size ; j++ ) {
                        multiplier_element = multiplier->element[j];
                        result_elements = &result->element[ i + j ];
                        /* Perform a single multiply, and add the
                         * resulting double-element into the result,
                         * carrying as necessary.  The carry can
                         * never overflow beyond the end of the
                         * result, since:
                         *
                         *     a < 2^{n}, b < 2^{n} => ab < 2^{2n}
                         */
                        __asm__ __volatile__ ( "mull %5\n\t"
                                               "addl %%eax, (%6,%2,4)\n\t"
                                               "adcl %%edx, 4(%6,%2,4)\n\t"
                                               "\n1:\n\t"
                                               "adcl $0, 8(%6,%2,4)\n\t"
                                               "inc %2\n\t"
                                                       /* Does not affect CF */
                                               "jc 1b\n\t"
                                               : "=&a" ( discard_a ),
                                                 "=&d" ( discard_d ),
                                                 "=&r" ( index ),
                                                 "+m" ( *result )
                                               : "0" ( multiplicand_element ),
                                                 "g" ( multiplier_element ),
                                                 "r" ( result_elements ),
                                                 "2" ( 0 ) );
                }
        }
}

References __asm__(), __attribute__, __volatile__(), bigint_t, index, memset(), multiplier, result, and size.

Variable Documentation

size

unsigned int size

Initial value:

{
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
                ( ( void * ) value0 )

Definition at line 26 of file bigint.h.

data

unsigned int const void* data

Definition at line 26 of file bigint.h.

len

unsigned int size void size_t len

Initial value:

{
        bigint_t ( size ) __attribute__ (( may_alias )) *value =
                ( ( void * ) value0 )

Definition at line 27 of file bigint.h.

pad_len

long pad_len = ( sizeof ( *value ) - len )

Definition at line 30 of file bigint.h.

Referenced by bzimage_load_initrd(), efi_file_read_initrd(), ib_pull(), ib_push(), inet6_aton(), iob_pad(), iscsi_tx_data_out(), iscsi_tx_login_request(), rsa_encode_digest(), tls_new_ciphertext(), and vmbus_send().

discard_D

void * discard_D

Definition at line 31 of file bigint.h.

Referenced by call_bootsector(), copy_from_real_libkir(), copy_to_real_libkir(), meme820(), nbi_boot16(), nbi_boot32(), pcibios_discover(), pcibios_read(), pcibios_write(), pxe_start_nbp(), and undinet_call().

discard_c

long discard_c

Definition at line 32 of file bigint.h.

Referenced by bios_putchar(), copy_from_real_libkir(), copy_to_real_libkir(), cpuid_supported(), int13_load_mbr(), int13con_init(), pcibios_write(), pxe_start_nbp(), rdrand_get_noise(), rdtsc_probe(), and tcpip_continue_chksum().

value0

static uint32_t * value0

Definition at line 57 of file bigint.h.

Referenced by bigint_add_sample(), bigint_bit_is_set_sample(), bigint_done_sample(), bigint_init_sample(), bigint_is_geq_sample(), bigint_is_zero_sample(), bigint_max_set_bit_sample(), bigint_rol_sample(), bigint_ror_sample(), and bigint_subtract_sample().

index

unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) )

Definition at line 61 of file bigint.h.

discard_S

void * discard_S

Definition at line 62 of file bigint.h.

Referenced by copy_from_real_libkir(), copy_to_real_libkir(), nbi_boot16(), nbi_boot32(), and tcpip_continue_chksum().

result

return result

Definition at line 160 of file bigint.h.

Referenced by ath5k_get_interpolated_value(), ath5k_hw_get_capability(), atl1e_mdio_read(), bigint_mod_exp_raw(), bigint_mod_exp_sample(), bigint_mod_multiply_raw(), bigint_mod_multiply_sample(), bigint_multiply_raw(), bigint_multiply_sample(), bnx2_poll(), cs89x0_probe(), dhe_key(), ethtool_adv_to_mii_adv_x(), hfa384x_copy_from_bap(), hfa384x_copy_to_bap(), hfa384x_drvr_getconfig(), hfa384x_drvr_setconfig(), hfa384x_prepare_bap(), isqrt(), memmap_settings_fetch(), mii_adv_to_ethtool_adv_x(), myri10ge_command(), prism2_poll(), prism2_probe(), prism2_transmit(), rdrand_get_noise(), velocity_mii_read(), and vmxnet3_command().

reference0

const uint32_t* reference0

Definition at line 180 of file bigint.h.

Referenced by bigint_is_geq_sample().

discard_tmp

long discard_tmp

Definition at line 183 of file bigint.h.

bit

unsigned int unsigned int bit

Initial value:

{
        const bigint_t ( size ) __attribute__ (( may_alias )) *value =
                ( ( const void * ) value0 )

Definition at line 208 of file bigint.h.

Referenced by _tg3_flag(), _tg3_flag_clear(), _tg3_flag_set(), arbel_bitmask_alloc(), arbel_bitmask_free(), ath5k_hw_bitswap(), b44_wait_bit(), base64_decode(), base64_encode(), bigint_bit_is_set_sample(), bitmap_set(), bitmap_test(), cpuid_exec(), deflate_init(), hermon_bitmask_alloc(), hermon_bitmask_free(), hub_clear_changes(), i2c_recv_bit(), i2c_send_bit(), isqrt(), linda_i2c_write_bit(), mii_bit_xfer(), qib7322_i2c_write_bit(), spi_bit_transfer(), vmbus_signal_monitor(), vxgetlink(), and vxsetlink().

subindex

unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) )

Definition at line 212 of file bigint.h.

source_size

unsigned int source_size

Definition at line 252 of file bigint.h.

Referenced by bigint_grow_sample(), bigint_shrink_sample(), and efi_load_image_wrapper().

dest0

static unsigned int source_size uint32_t * dest0

Definition at line 252 of file bigint.h.

Referenced by bigint_grow_sample(), and bigint_shrink_sample().

dest_size

static unsigned int source_size uint32_t unsigned int dest_size

Initial value:

{
        bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest =
                ( ( void * ) dest0 )

Definition at line 253 of file bigint.h.

Referenced by bigint_grow_sample(), and bigint_shrink_sample().

pad_size

long pad_size = ( dest_size - source_size )

Definition at line 256 of file bigint.h.

__unused

unsigned int size __unused

Definition at line 281 of file bigint.h.

out

unsigned int size void* out

Definition at line 306 of file bigint.h.