iPXE
Typedefs | Functions | Variables
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(%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")
 
__asm__ __volatile__ ("xor %0, %0\n\t" "\n1:\n\t" "lodsl\n\t" "adcl %%eax, (%3,%0,4)\n\t" "inc %0\n\t" "loop 1b\n\t" :"=&r"(index), "=&S"(discard_S), "=&c"(discard_c) :"r"(value0), "1"(addend0), "2"(size) :"eax")
 
__asm__ __volatile__ ("xor %0, %0\n\t" "\n1:\n\t" "lodsl\n\t" "sbbl %%eax, (%3,%0,4)\n\t" "inc %0\n\t" "loop 1b\n\t" :"=&r"(index), "=&S"(discard_S), "=&c"(discard_c) :"r"(value0), "1"(subtrahend0), "2"(size) :"eax")
 
__asm__ __volatile__ ("xor %0, %0\n\t" "\n1:\n\t" "rcll $1, (%2,%0,4)\n\t" "inc %0\n\t" "loop 1b\n\t" :"=&r"(index), "=&c"(discard_c) :"r"(value0), "1"(size))
 
__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))
 
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))
 
const bigint_t (size) __attribute__((may_alias)) *reference
 
__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 (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 %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")
 
__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")
 
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
 
void * discard_D
 
long discard_c
 
static uint32_tvalue0
 
void * discard_S
 
int result
 
static const uint32_treference0
 
static unsigned int unsigned int bit
 
unsigned int index = ( bit / ( 8 * sizeof ( value->element[0] ) ) )
 
unsigned int subindex = ( bit % ( 8 * sizeof ( value->element[0] ) ) )
 
static unsigned int source_size
 
static unsigned int uint32_tdest0
 
static unsigned int uint32_t unsigned int dest_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

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
value0Element 0 of big integer to initialise
sizeNumber of elements
dataRaw data
lenLength of raw data
addend0Element 0 of big integer to add
value0Element 0 of big integer to be added to
sizeNumber of elements
subtrahend0Element 0 of big integer to subtract
value0Element 0 of big integer to be subtracted from
sizeNumber of elements
value0Element 0 of big integer
sizeNumber of elements
value0Element 0 of big integer
sizeNumber of elements
bitBit to test
Return values
is_setBit is set
Parameters
value0Element 0 of big integer
sizeNumber of elements
Return values
max_bitHighest bit set + 1 (or 0 if no bits set)
Parameters
source0Element 0 of source big integer
source_sizeNumber of elements in source big integer
dest0Element 0 of destination big integer
dest_sizeNumber of elements in destination big integer
value0Element 0 of big integer to finalise
sizeNumber of elements
outOutput buffer
lenLength of output buffer

◆ __volatile__() [1/10]

__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 
)

◆ __volatile__() [2/10]

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

◆ __volatile__() [3/10]

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

◆ __volatile__() [4/10]

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

◆ __volatile__() [5/10]

__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
value0Element 0 of big integer
sizeNumber of elements
Return values
is_zeroBig integer is equal to zero
Parameters
value0Element 0 of big integer
reference0Element 0 of reference big integer
sizeNumber of elements
Return values
geqBig integer is greater than or equal to the reference

◆ __volatile__() [6/10]

__asm__ __volatile__ ( "xor %  0)

◆ bigint_t()

const bigint_t ( size  )

◆ __volatile__() [7/10]

__asm__ __volatile__ ( )

◆ return()

return ( value->element &  (1<< subindex)[index])

◆ __volatile__() [8/10]

__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/10]

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

◆ __volatile__() [10/10]

__asm__ __volatile__ ( "\n1:\n\t" "movb 1%2,%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
multiplicand0Element 0 of big integer to be multiplied
multiplier0Element 0 of big integer to be multiplied
result0Element 0 of big integer to hold result
sizeNumber of elements

Definition at line 43 of file x86_bigint.c.

45  {
46  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
47  ( ( const void * ) multiplicand0 );
48  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
49  ( ( const void * ) multiplier0 );
50  bigint_t ( size * 2 ) __attribute__ (( may_alias )) *result =
51  ( ( void * ) result0 );
52  unsigned int i;
53  unsigned int j;
54  uint32_t multiplicand_element;
55  uint32_t multiplier_element;
56  uint32_t *result_elements;
57  uint32_t discard_a;
58  uint32_t discard_d;
59  long index;
60 
61  /* Zero result */
62  memset ( result, 0, sizeof ( *result ) );
63 
64  /* Multiply integers one element at a time */
65  for ( i = 0 ; i < size ; i++ ) {
66  multiplicand_element = multiplicand->element[i];
67  for ( j = 0 ; j < size ; j++ ) {
68  multiplier_element = multiplier->element[j];
69  result_elements = &result->element[ i + j ];
70  /* Perform a single multiply, and add the
71  * resulting double-element into the result,
72  * carrying as necessary. The carry can
73  * never overflow beyond the end of the
74  * result, since:
75  *
76  * a < 2^{n}, b < 2^{n} => ab < 2^{2n}
77  */
78  __asm__ __volatile__ ( "mull %4\n\t"
79  "addl %%eax, (%5,%2,4)\n\t"
80  "adcl %%edx, 4(%5,%2,4)\n\t"
81  "\n1:\n\t"
82  "adcl $0, 8(%5,%2,4)\n\t"
83  "inc %2\n\t"
84  /* Does not affect CF */
85  "jc 1b\n\t"
86  : "=&a" ( discard_a ),
87  "=&d" ( discard_d ),
88  "=&r" ( index )
89  : "0" ( multiplicand_element ),
90  "g" ( multiplier_element ),
91  "r" ( result_elements ),
92  "2" ( 0 ) );
93  }
94  }
95 }
#define __attribute__(x)
Definition: compiler.h:10
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
int result
Definition: bigint.h:148
const bigint_t(size) __attribute__((may_alias)) *reference
unsigned int uint32_t
Definition: stdint.h:12
__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")
__asm__(".section \".rodata\", \"a\", " PROGBITS "\n\t" "\nprivate_key_data:\n\t" ".size private_key_data, ( . - private_key_data )\n\t" ".equ private_key_len, ( . - private_key_data )\n\t" ".previous\n\t")
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21
void * memset(void *dest, int character, size_t len) __nonnull

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

Variable Documentation

◆ size

unsigned int size
Initial value:
{
long index
unsigned int index
Definition: bigint.h:208

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:
{
long pad_len = ( sizeof ( bigint_t ( size ) ) - len )
static unsigned int const void size_t len
Definition: bigint.h:27
const bigint_t(size) __attribute__((may_alias)) *reference
static unsigned int size
Definition: bigint.h:26

Definition at line 27 of file bigint.h.

◆ discard_D

void * discard_D

◆ discard_c

long discard_c

◆ value0

static uint32_t * value0

◆ discard_S

void * discard_S

◆ result

return result

◆ reference0

const uint32_t* reference0

Definition at line 168 of file bigint.h.

Referenced by bigint_is_geq_sample().

◆ bit

unsigned int unsigned int bit
Initial value:
{
const bigint_t ( size ) __attribute__ (( may_alias )) *value =
( ( const void * ) value0 )
static uint32_t * value0
Definition: bigint.h:54
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
const bigint_t(size) __attribute__((may_alias)) *reference
static __attribute__((always_inline)) void bigint_init_raw(uint32_t *value0
Initialise big integer.
static unsigned int size
Definition: bigint.h:26

Definition at line 205 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().

◆ index

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

Definition at line 208 of file bigint.h.

◆ subindex

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

Definition at line 209 of file bigint.h.

◆ source_size

unsigned int source_size

Definition at line 249 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 249 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:
{
long pad_size = ( dest_size - source_size )
static unsigned int uint32_t unsigned int dest_size
Definition: bigint.h:250
static unsigned int source_size
Definition: bigint.h:249

Definition at line 250 of file bigint.h.

Referenced by bigint_grow_sample(), and bigint_shrink_sample().

◆ __unused

unsigned int size __unused

Definition at line 276 of file bigint.h.

◆ out

unsigned int size void* out

Definition at line 299 of file bigint.h.