| #ifndef _BITS_BIGINT_H |
| #define _BITS_BIGINT_H |
| |
| /** @file |
| * |
| * Big integer support |
| */ |
| |
| FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); |
| FILE_SECBOOT ( PERMITTED ); |
| |
| /** Element of a big integer */ |
| typedef unsigned long bigint_element_t; |
| |
| /** |
| * 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 |
| * @ret carry Carry out |
| */ |
| static inline __attribute__ (( always_inline )) int |
| bigint_add_raw ( const unsigned long *addend0, unsigned long *value0, |
| unsigned int size ) { |
| bigint_t ( size ) __attribute__ (( may_alias )) *value = |
| ( ( void * ) value0 ); |
| unsigned long *valueN = ( value0 + size ); |
| unsigned long *discard_addend; |
| unsigned long *discard_value; |
| unsigned long discard_addend_i; |
| unsigned long discard_value_i; |
| unsigned long discard_temp; |
| unsigned long carry; |
| |
| __asm__ __volatile__ ( "\n1:\n\t" |
| /* Load addend[i] and value[i] */ |
| LOADN " %2, (%0)\n\t" |
| LOADN " %3, (%1)\n\t" |
| /* Add carry flag and addend */ |
| "add %3, %3, %5\n\t" |
| "sltu %4, %3, %5\n\t" |
| "add %3, %3, %2\n\t" |
| "sltu %5, %3, %2\n\t" |
| "or %5, %4, %5\n\t" |
| /* Store value[i] */ |
| STOREN " %3, (%1)\n\t" |
| /* Loop */ |
| "addi %0, %0, %8\n\t" |
| "addi %1, %1, %8\n\t" |
| "bne %1, %7, 1b\n\t" |
| : "=&r" ( discard_addend ), |
| "=&r" ( discard_value ), |
| "=&r" ( discard_addend_i ), |
| "=&r" ( discard_value_i ), |
| "=&r" ( discard_temp ), |
| "=&r" ( carry ), |
| "+m" ( *value ) |
| : "r" ( valueN ), |
| "i" ( sizeof ( unsigned long ) ), |
| "0" ( addend0 ), "1" ( value0 ), "5" ( 0 ) ); |
| return carry; |
| } |
| |
| /** |
| * 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 |
| * @ret borrow Borrow out |
| */ |
| static inline __attribute__ (( always_inline )) int |
| bigint_subtract_raw ( const unsigned long *subtrahend0, unsigned long *value0, |
| unsigned int size ) { |
| bigint_t ( size ) __attribute__ (( may_alias )) *value = |
| ( ( void * ) value0 ); |
| unsigned long *valueN = ( value0 + size ); |
| unsigned long *discard_subtrahend; |
| unsigned long *discard_value; |
| unsigned long discard_subtrahend_i; |
| unsigned long discard_value_i; |
| unsigned long discard_temp; |
| unsigned long borrow; |
| |
| __asm__ __volatile__ ( "\n1:\n\t" |
| /* Load subtrahend[i] and value[i] */ |
| LOADN " %2, (%0)\n\t" |
| LOADN " %3, (%1)\n\t" |
| /* Subtract carry flag and subtrahend */ |
| "sltu %4, %3, %5\n\t" |
| "sub %3, %3, %5\n\t" |
| "sltu %5, %3, %2\n\t" |
| "sub %3, %3, %2\n\t" |
| "or %5, %5, %4\n\t" |
| /* Store value[i] */ |
| STOREN " %3, (%1)\n\t" |
| /* Loop */ |
| "addi %0, %0, %8\n\t" |
| "addi %1, %1, %8\n\t" |
| "bne %1, %7, 1b\n\t" |
| : "=&r" ( discard_subtrahend ), |
| "=&r" ( discard_value ), |
| "=&r" ( discard_subtrahend_i ), |
| "=&r" ( discard_value_i ), |
| "=&r" ( discard_temp ), |
| "=&r" ( borrow ), |
| "+m" ( *value ) |
| : "r" ( valueN ), |
| "i" ( sizeof ( unsigned long ) ), |
| "0" ( subtrahend0 ), "1" ( value0 ), |
| "5" ( 0 ) ); |
| return borrow; |
| } |
| |
| /** |
| * Shift big integer left |
| * |
| * @v value0 Element 0 of big integer |
| * @v size Number of elements |
| * @ret out Bit shifted out |
| */ |
| static inline __attribute__ (( always_inline )) int |
| bigint_shl_raw ( unsigned long *value0, unsigned int size ) { |
| bigint_t ( size ) __attribute__ (( may_alias )) *value = |
| ( ( void * ) value0 ); |
| unsigned long *valueN = ( value0 + size ); |
| unsigned long *discard_value; |
| unsigned long discard_value_i; |
| unsigned long discard_temp; |
| unsigned long carry; |
| |
| __asm__ __volatile__ ( "\n1:\n\t" |
| /* Load value[i] */ |
| LOADN " %1, (%0)\n\t" |
| /* Shift left */ |
| "slli %2, %1, 1\n\t" |
| "or %2, %2, %3\n\t" |
| "srli %3, %1, %7\n\t" |
| /* Store value[i] */ |
| STOREN " %2, (%0)\n\t" |
| /* Loop */ |
| "addi %0, %0, %6\n\t" |
| "bne %0, %5, 1b\n\t" |
| : "=&r" ( discard_value ), |
| "=&r" ( discard_value_i ), |
| "=&r" ( discard_temp ), |
| "=&r" ( carry ), |
| "+m" ( *value ) |
| : "r" ( valueN ), |
| "i" ( sizeof ( unsigned long ) ), |
| "i" ( ( 8 * sizeof ( unsigned long ) - 1 ) ), |
| "0" ( value0 ), "3" ( 0 ) ); |
| return carry; |
| } |
| |
| /** |
| * Shift big integer right |
| * |
| * @v value0 Element 0 of big integer |
| * @v size Number of elements |
| * @ret out Bit shifted out |
| */ |
| static inline __attribute__ (( always_inline )) int |
| bigint_shr_raw ( unsigned long *value0, unsigned int size ) { |
| bigint_t ( size ) __attribute__ (( may_alias )) *value = |
| ( ( void * ) value0 ); |
| unsigned long *valueN = ( value0 + size ); |
| unsigned long *discard_value; |
| unsigned long discard_value_i; |
| unsigned long discard_temp; |
| unsigned long carry; |
| |
| __asm__ __volatile__ ( "\n1:\n\t" |
| /* Load value[i] */ |
| LOADN " %1, %6(%0)\n\t" |
| /* Shift right */ |
| "srli %2, %1, 1\n\t" |
| "or %2, %2, %3\n\t" |
| "slli %3, %1, %7\n\t" |
| /* Store value[i] */ |
| STOREN " %2, %6(%0)\n\t" |
| /* Loop */ |
| "addi %0, %0, %6\n\t" |
| "bne %0, %5, 1b\n\t" |
| : "=&r" ( discard_value ), |
| "=&r" ( discard_value_i ), |
| "=&r" ( discard_temp ), |
| "=&r" ( carry ), |
| "+m" ( *value ) |
| : "r" ( value0 ), |
| "i" ( -( sizeof ( unsigned long ) ) ), |
| "i" ( ( 8 * sizeof ( unsigned long ) - 1 ) ), |
| "0" ( valueN ), "3" ( 0 ) ); |
| return ( !! carry ); |
| } |
| |
| /** |
| * 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 unsigned long *source0, unsigned int source_size, |
| unsigned long *dest0, unsigned int dest_size ) { |
| bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest = |
| ( ( void * ) dest0 ); |
| const unsigned long *sourceN = ( source0 + source_size ); |
| unsigned long *destN = ( dest0 + dest_size ); |
| unsigned long *discard_source; |
| unsigned long *discard_dest; |
| unsigned long discard_source_i; |
| |
| __asm__ __volatile__ ( "\n1:\n\t" |
| /* Copy dest[i] */ |
| LOADN " %2, (%0)\n\t" |
| STOREN " %2, (%1)\n\t" |
| /* Loop */ |
| "addi %0, %0, %6\n\t" |
| "addi %1, %1, %6\n\t" |
| "bne %0, %4, 1b\n\t" |
| "j 3f\n\t" |
| "\n2:\n\t" |
| /* Zero dest[i] */ |
| STOREN " zero, (%1)\n\t" |
| /* Loop */ |
| "addi %1, %1, %6\n\t" |
| "\n3:\n\t" |
| "bne %1, %5, 2b\n\t" |
| : "=&r" ( discard_source ), |
| "=&r" ( discard_dest ), |
| "=&r" ( discard_source_i ), |
| "=m" ( *dest ) |
| : "r" ( sourceN ), |
| "r" ( destN ), |
| "i" ( sizeof ( unsigned long ) ), |
| "0" ( source0 ), "1" ( dest0 ) ); |
| } |
| |
| /** |
| * 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 unsigned long *source0, |
| unsigned int source_size __unused, |
| unsigned long *dest0, unsigned int dest_size ) { |
| bigint_t ( dest_size ) __attribute__ (( may_alias )) *dest = |
| ( ( void * ) dest0 ); |
| unsigned long *destN = ( dest0 + dest_size ); |
| unsigned long *discard_source; |
| unsigned long *discard_dest; |
| unsigned long discard_source_i; |
| |
| __asm__ __volatile__ ( "\n1:\n\t" |
| /* Copy dest[i] */ |
| LOADN " %2, (%0)\n\t" |
| STOREN " %2, (%1)\n\t" |
| /* Loop */ |
| "addi %0, %0, %5\n\t" |
| "addi %1, %1, %5\n\t" |
| "bne %1, %4, 1b\n\t" |
| : "=&r" ( discard_source ), |
| "=&r" ( discard_dest ), |
| "=&r" ( discard_source_i ), |
| "=m" ( *dest ) |
| : "r" ( destN ), |
| "i" ( sizeof ( unsigned long ) ), |
| "0" ( source0 ), "1" ( dest0 ) ); |
| } |
| |
| /** |
| * Multiply big integer elements |
| * |
| * @v multiplicand Multiplicand element |
| * @v multiplier Multiplier element |
| * @v result Result element |
| * @v carry Carry element |
| */ |
| static inline __attribute__ (( always_inline )) void |
| bigint_multiply_one ( const unsigned long multiplicand, |
| const unsigned long multiplier, |
| unsigned long *result, unsigned long *carry ) { |
| unsigned long discard_low; |
| unsigned long discard_high; |
| unsigned long discard_carry; |
| |
| __asm__ __volatile__ ( /* Perform multiplication */ |
| "mulhu %1, %5, %6\n\t" |
| "mul %0, %5, %6\n\t" |
| /* Accumulate low half */ |
| "add %3, %3, %0\n\t" |
| "sltu %2, %3, %0\n\t" |
| "add %1, %1, %2\n\t" |
| /* Accumulate carry (cannot overflow) */ |
| "add %3, %3, %4\n\t" |
| "sltu %2, %3, %4\n\t" |
| "add %4, %1, %2\n\t" |
| : "=r" ( discard_low ), |
| "=&r" ( discard_high ), |
| "=r" ( discard_carry ), |
| "+r" ( *result ), |
| "+r" ( *carry ) |
| : "r" ( multiplicand ), |
| "r" ( multiplier ) ); |
| } |
| |
| #endif /* _BITS_BIGINT_H */ |
