| #ifndef _BITS_BIGINT_H |
| #define _BITS_BIGINT_H |
| |
| /** @file |
| * |
| * Big integer support |
| */ |
| |
| FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); |
| |
| #include <stdint.h> |
| #include <string.h> |
| #include <strings.h> |
| |
| /** Element of a big integer */ |
| typedef uint64_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 ( uint64_t *value0, unsigned int size, |
| const void *data, size_t len ) { |
| size_t pad_len = ( sizeof ( bigint_t ( size ) ) - len ); |
| uint8_t *value_byte = ( ( void * ) value0 ); |
| const uint8_t *data_byte = ( data + len ); |
| |
| /* Copy raw data in reverse order, padding with zeros */ |
| while ( len-- ) |
| *(value_byte++) = *(--data_byte); |
| while ( pad_len-- ) |
| *(value_byte++) = 0; |
| } |
| |
| /** |
| * 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 uint64_t *addend0, uint64_t *value0, |
| unsigned int size ) { |
| bigint_t ( size ) __attribute__ (( may_alias )) *value = |
| ( ( void * ) value0 ); |
| uint64_t *discard_addend; |
| uint64_t *discard_value; |
| uint64_t discard_addend_i; |
| uint64_t discard_value_i; |
| unsigned int discard_size; |
| __asm__ __volatile__ ( "move $t0, $zero\n" |
| "1:\n\t" |
| "ld.d %3, %0, 0\n\t" |
| "addi.d %0, %0, 8\n\t" |
| "ld.d %4, %1, 0\n\t" |
| |
| "add.d %4, %4, $t0\n\t" |
| "sltu $t0, %4, $t0\n\t" |
| |
| "add.d %4, %4, %3\n\t" |
| "sltu $t1, %4, %3\n\t" |
| |
| "or $t0, $t0, $t1\n\t" |
| "st.d %4, %1, 0\n\t" |
| "addi.d %1, %1, 8\n\t" |
| "addi.w %2, %2, -1\n\t" |
| "bnez %2, 1b" |
| : "=r" ( discard_addend ), |
| "=r" ( discard_value ), |
| "=r" ( discard_size ), |
| "=r" ( discard_addend_i ), |
| "=r" ( discard_value_i ), |
| "+m" ( *value ) |
| : "0" ( addend0 ), |
| "1" ( value0 ), |
| "2" ( size ) |
| : "t0", "t1" ); |
| } |
| |
| /** |
| * 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 uint64_t *subtrahend0, uint64_t *value0, |
| unsigned int size ) { |
| uint64_t *discard_subtrahend; |
| uint64_t *discard_value; |
| uint64_t discard_subtrahend_i; |
| uint64_t discard_value_i; |
| unsigned int discard_size; |
| unsigned int flag = 0; |
| |
| discard_subtrahend = (uint64_t*) subtrahend0; |
| discard_value = value0; |
| discard_size = size; |
| |
| do { |
| discard_subtrahend_i = *discard_subtrahend; |
| discard_subtrahend++; |
| discard_value_i = *discard_value; |
| |
| discard_value_i = discard_value_i - discard_subtrahend_i - flag; |
| |
| if ( *discard_value < (discard_subtrahend_i + flag)) { |
| flag = 1; |
| } else { |
| flag = 0; |
| } |
| |
| *discard_value = discard_value_i; |
| |
| discard_value++; |
| discard_size -= 1; |
| } while (discard_size != 0); |
| } |
| |
| /** |
| * 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 ( uint64_t *value0, unsigned int size ) { |
| uint64_t *discard_value; |
| uint64_t discard_value_i; |
| unsigned int discard_size; |
| uint64_t current_value_i; |
| unsigned int flag = 0; |
| |
| discard_value = value0; |
| discard_size = size; |
| do { |
| discard_value_i = *discard_value; |
| current_value_i = discard_value_i; |
| |
| discard_value_i += discard_value_i + flag; |
| |
| if (discard_value_i < current_value_i) { |
| flag = 1; |
| } else { |
| flag = 0; |
| } |
| |
| *discard_value = discard_value_i; |
| discard_value++; |
| discard_size -= 1; |
| } while ( discard_size != 0 ); |
| } |
| |
| /** |
| * 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 ( uint64_t *value0, unsigned int size ) { |
| uint64_t *discard_value; |
| uint64_t discard_value_i; |
| uint64_t discard_value_j; |
| unsigned int discard_size; |
| |
| discard_value = value0; |
| discard_size = size; |
| |
| discard_value_j = 0; |
| |
| do { |
| discard_size -= 1; |
| |
| discard_value_i = *(discard_value + discard_size); |
| |
| discard_value_j = (discard_value_j << 63) | (discard_value_i >> 1); |
| |
| *(discard_value + discard_size) = discard_value_j; |
| |
| discard_value_j = discard_value_i; |
| } while ( discard_size > 0 ); |
| } |
| |
| /** |
| * 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 uint64_t *value0, unsigned int size ) { |
| const uint64_t *value = value0; |
| uint64_t value_i; |
| |
| do { |
| value_i = *(value++); |
| if ( value_i ) |
| break; |
| } while ( --size ); |
| |
| return ( value_i == 0 ); |
| } |
| |
| /** |
| * 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 uint64_t *value0, const uint64_t *reference0, |
| unsigned int size ) { |
| const uint64_t *value = ( value0 + size ); |
| const uint64_t *reference = ( reference0 + size ); |
| uint64_t value_i; |
| uint64_t reference_i; |
| |
| do { |
| value_i = *(--value); |
| reference_i = *(--reference); |
| if ( value_i != reference_i ) |
| break; |
| } while ( --size ); |
| |
| return ( value_i >= reference_i ); |
| } |
| |
| /** |
| * 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 uint64_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] & ( 1UL << 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 uint64_t *value0, unsigned int size ) { |
| const uint64_t *value = ( value0 + size ); |
| int max_bit = ( 8 * sizeof ( bigint_t ( size ) ) ); |
| uint64_t value_i; |
| |
| do { |
| value_i = *(--value); |
| max_bit -= ( 64 - fls ( value_i ) ); |
| if ( value_i ) |
| break; |
| } while ( --size ); |
| |
| return max_bit; |
| } |
| |
| /** |
| * 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 uint64_t *source0, unsigned int source_size, |
| uint64_t *dest0, unsigned int dest_size ) { |
| unsigned int pad_size = ( dest_size - source_size ); |
| |
| memcpy ( dest0, source0, sizeof ( bigint_t ( source_size ) ) ); |
| memset ( ( dest0 + source_size ), 0, sizeof ( bigint_t ( pad_size ) ) ); |
| } |
| |
| /** |
| * 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 uint64_t *source0, unsigned int source_size __unused, |
| uint64_t *dest0, unsigned int dest_size ) { |
| |
| memcpy ( dest0, source0, sizeof ( bigint_t ( dest_size ) ) ); |
| } |
| |
| /** |
| * 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 uint64_t *value0, unsigned int size __unused, |
| void *out, size_t len ) { |
| const uint8_t *value_byte = ( ( const void * ) value0 ); |
| uint8_t *out_byte = ( out + len ); |
| |
| /* Copy raw data in reverse order */ |
| while ( len-- ) |
| *(--out_byte) = *(value_byte++); |
| } |
| |
| extern void bigint_multiply_raw ( const uint64_t *multiplicand0, |
| const uint64_t *multiplier0, |
| uint64_t *value0, unsigned int size ); |
| |
| #endif /* _BITS_BIGINT_H */ |