iPXE
Functions | Variables
bigint.c File Reference

Big integer support. More...

#include <stdint.h>
#include <string.h>
#include <assert.h>
#include <ipxe/profile.h>
#include <ipxe/bigint.h>

Go to the source code of this file.

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
 
void bigint_mod_multiply_raw (const bigint_element_t *multiplicand0, const bigint_element_t *multiplier0, const bigint_element_t *modulus0, bigint_element_t *result0, unsigned int size, void *tmp)
 Perform modular multiplication of big integers. More...
 
void bigint_mod_exp_raw (const bigint_element_t *base0, const bigint_element_t *modulus0, const bigint_element_t *exponent0, bigint_element_t *result0, unsigned int size, unsigned int exponent_size, void *tmp)
 Perform modular exponentiation of big integers. More...
 

Variables

static struct profiler bigint_mod_multiply_profiler __profiler
 Modular multiplication overall profiler. More...
 

Detailed Description

Big integer support.

Definition in file bigint.c.

Function Documentation

◆ FILE_LICENCE()

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )

◆ bigint_mod_multiply_raw()

void bigint_mod_multiply_raw ( const bigint_element_t multiplicand0,
const bigint_element_t multiplier0,
const bigint_element_t modulus0,
bigint_element_t result0,
unsigned int  size,
void *  tmp 
)

Perform modular multiplication of big integers.

Parameters
multiplicand0Element 0 of big integer to be multiplied
multiplier0Element 0 of big integer to be multiplied
modulus0Element 0 of big integer modulus
result0Element 0 of big integer to hold result
sizeNumber of elements in base, modulus, and result
tmpTemporary working space

Definition at line 63 of file bigint.c.

67  {
68  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplicand =
69  ( ( const void * ) multiplicand0 );
70  const bigint_t ( size ) __attribute__ (( may_alias )) *multiplier =
71  ( ( const void * ) multiplier0 );
72  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
73  ( ( const void * ) modulus0 );
74  bigint_t ( size ) __attribute__ (( may_alias )) *result =
75  ( ( void * ) result0 );
76  struct {
77  bigint_t ( size * 2 ) result;
78  bigint_t ( size * 2 ) modulus;
79  } *temp = tmp;
80  int rotation;
81  int i;
82 
83  /* Start profiling */
84  profile_start ( &bigint_mod_multiply_profiler );
85 
86  /* Sanity check */
87  assert ( sizeof ( *temp ) == bigint_mod_multiply_tmp_len ( modulus ) );
88 
89  /* Perform multiplication */
90  profile_start ( &bigint_mod_multiply_multiply_profiler );
91  bigint_multiply ( multiplicand, multiplier, &temp->result );
92  profile_stop ( &bigint_mod_multiply_multiply_profiler );
93 
94  /* Rescale modulus to match result */
95  profile_start ( &bigint_mod_multiply_rescale_profiler );
96  bigint_grow ( modulus, &temp->modulus );
97  rotation = ( bigint_max_set_bit ( &temp->result ) -
98  bigint_max_set_bit ( &temp->modulus ) );
99  for ( i = 0 ; i < rotation ; i++ )
100  bigint_rol ( &temp->modulus );
101  profile_stop ( &bigint_mod_multiply_rescale_profiler );
102 
103  /* Subtract multiples of modulus */
104  profile_start ( &bigint_mod_multiply_subtract_profiler );
105  for ( i = 0 ; i <= rotation ; i++ ) {
106  if ( bigint_is_geq ( &temp->result, &temp->modulus ) )
107  bigint_subtract ( &temp->modulus, &temp->result );
108  bigint_ror ( &temp->modulus );
109  }
110  profile_stop ( &bigint_mod_multiply_subtract_profiler );
111 
112  /* Resize result */
113  bigint_shrink ( &temp->result, result );
114 
115  /* Sanity check */
116  assert ( bigint_is_geq ( modulus, result ) );
117 
118  /* Stop profiling */
119  profile_stop ( &bigint_mod_multiply_profiler );
120 }
#define __attribute__(x)
Definition: compiler.h:10
#define bigint_max_set_bit(value)
Find highest bit set in big integer.
Definition: bigint.h:149
#define bigint_ror(value)
Rotate big integer right.
Definition: bigint.h:104
#define bigint_grow(source, dest)
Grow big integer.
Definition: bigint.h:159
static void profile_stop(struct profiler *profiler)
Stop profiling.
Definition: profile.h:171
uint8_t multiplier
Port multiplier number.
Definition: edd.h:32
#define bigint_is_geq(value, reference)
Compare big integers.
Definition: bigint.h:127
int result
Definition: bigint.h:148
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
#define bigint_shrink(source, dest)
Shrink big integer.
Definition: bigint.h:172
static void profile_start(struct profiler *profiler)
Start profiling.
Definition: profile.h:158
const bigint_t(size) __attribute__((may_alias)) *reference
#define bigint_rol(value)
Rotate big integer left.
Definition: bigint.h:94
uint8_t * tmp
Definition: entropy.h:156
static unsigned int rotation
Definition: rotate.h:14
#define bigint_mod_multiply_tmp_len(modulus)
Calculate temporary working space required for moduluar multiplication.
Definition: bigint.h:217
#define bigint_multiply(multiplicand, multiplier, result)
Multiply big integers.
Definition: bigint.h:186
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
#define bigint_subtract(subtrahend, value)
Subtract big integers.
Definition: bigint.h:83

References __attribute__, assert(), bigint_grow, bigint_is_geq, bigint_max_set_bit, bigint_mod_multiply_tmp_len, bigint_multiply, bigint_rol, bigint_ror, bigint_shrink, bigint_subtract, bigint_t(), multiplier, profile_start(), profile_stop(), result, rotation, size, and tmp.

◆ bigint_mod_exp_raw()

void bigint_mod_exp_raw ( const bigint_element_t base0,
const bigint_element_t modulus0,
const bigint_element_t exponent0,
bigint_element_t result0,
unsigned int  size,
unsigned int  exponent_size,
void *  tmp 
)

Perform modular exponentiation of big integers.

Parameters
base0Element 0 of big integer base
modulus0Element 0 of big integer modulus
exponent0Element 0 of big integer exponent
result0Element 0 of big integer to hold result
sizeNumber of elements in base, modulus, and result
exponent_sizeNumber of elements in exponent
tmpTemporary working space

Definition at line 133 of file bigint.c.

138  {
139  const bigint_t ( size ) __attribute__ (( may_alias )) *base =
140  ( ( const void * ) base0 );
141  const bigint_t ( size ) __attribute__ (( may_alias )) *modulus =
142  ( ( const void * ) modulus0 );
143  const bigint_t ( exponent_size ) __attribute__ (( may_alias ))
144  *exponent = ( ( const void * ) exponent0 );
145  bigint_t ( size ) __attribute__ (( may_alias )) *result =
146  ( ( void * ) result0 );
147  size_t mod_multiply_len = bigint_mod_multiply_tmp_len ( modulus );
148  struct {
149  bigint_t ( size ) base;
150  bigint_t ( exponent_size ) exponent;
151  uint8_t mod_multiply[mod_multiply_len];
152  } *temp = tmp;
153  static const uint8_t start[1] = { 0x01 };
154 
155  memcpy ( &temp->base, base, sizeof ( temp->base ) );
156  memcpy ( &temp->exponent, exponent, sizeof ( temp->exponent ) );
157  bigint_init ( result, start, sizeof ( start ) );
158 
159  while ( ! bigint_is_zero ( &temp->exponent ) ) {
160  if ( bigint_bit_is_set ( &temp->exponent, 0 ) ) {
161  bigint_mod_multiply ( result, &temp->base, modulus,
162  result, temp->mod_multiply );
163  }
164  bigint_ror ( &temp->exponent );
165  bigint_mod_multiply ( &temp->base, &temp->base, modulus,
166  &temp->base, temp->mod_multiply );
167  }
168 }
#define __attribute__(x)
Definition: compiler.h:10
#define bigint_ror(value)
Rotate big integer right.
Definition: bigint.h:104
#define bigint_init(value, data, len)
Initialise big integer.
Definition: bigint.h:48
#define bigint_is_zero(value)
Test if big integer is equal to zero.
Definition: bigint.h:116
uint32_t start
Starting offset.
Definition: netvsc.h:12
void * memcpy(void *dest, const void *src, size_t len) __nonnull
int result
Definition: bigint.h:148
const bigint_t(size) __attribute__((may_alias)) *reference
uint8_t * tmp
Definition: entropy.h:156
unsigned char uint8_t
Definition: stdint.h:10
uint16_t base
Base address.
Definition: edd.h:14
#define bigint_mod_multiply(multiplicand, multiplier, modulus, result, tmp)
Perform modular multiplication of big integers.
Definition: bigint.h:202
#define bigint_mod_multiply_tmp_len(modulus)
Calculate temporary working space required for moduluar multiplication.
Definition: bigint.h:217
uint8_t size
Entry size (in 32-bit words)
Definition: ena.h:16
#define bigint_bit_is_set(value, bit)
Test if bit is set in big integer.
Definition: bigint.h:139

References __attribute__, base, bigint_bit_is_set, bigint_init, bigint_is_zero, bigint_mod_multiply, bigint_mod_multiply_tmp_len, bigint_ror, bigint_t(), memcpy(), result, size, start, and tmp.

Variable Documentation

◆ __profiler

struct profiler bigint_mod_multiply_subtract_profiler __profiler
static
Initial value:
=
{ .name = "bigint_mod_multiply" }

Modular multiplication overall profiler.

Modular multiplication subtract step profiler.

Modular multiplication rescale step profiler.

Modular multiplication multiply step profiler.

Definition at line 38 of file bigint.c.