diff options
author | Michael Brown <mcb30@ipxe.org> | 2024-01-19 16:35:02 +0000 |
---|---|---|
committer | Michael Brown <mcb30@ipxe.org> | 2024-01-19 16:40:11 +0000 |
commit | 908174ec7e49d845c8b52a07a3db32534eade37d (patch) | |
tree | 629f597d76156716b292a1b96c30672d999d260c /src | |
parent | bac13ba1f658a1e742b9ceb958e670086affebe7 (diff) | |
download | ipxe-908174ec7e49d845c8b52a07a3db32534eade37d.zip ipxe-908174ec7e49d845c8b52a07a3db32534eade37d.tar.gz ipxe-908174ec7e49d845c8b52a07a3db32534eade37d.tar.bz2 |
[loong64] Replace broken big integer arithmetic implementations
The slightly incomprehensible LoongArch64 implementation for
bigint_subtract() is observed to produce incorrect results for some
input values.
Replace the suspicious LoongArch64 implementations of bigint_add(),
bigint_subtract(), bigint_rol() and bigint_ror(), and add a test case
for a subtraction that was producing an incorrect result with the
previous implementation.
Signed-off-by: Michael Brown <mcb30@ipxe.org>
Diffstat (limited to 'src')
-rw-r--r-- | src/arch/loong64/include/bits/bigint.h | 184 | ||||
-rw-r--r-- | src/tests/bigint_test.c | 9 |
2 files changed, 115 insertions, 78 deletions
diff --git a/src/arch/loong64/include/bits/bigint.h b/src/arch/loong64/include/bits/bigint.h index a37ac73..bec748b 100644 --- a/src/arch/loong64/include/bits/bigint.h +++ b/src/arch/loong64/include/bits/bigint.h @@ -53,34 +53,37 @@ bigint_add_raw ( const uint64_t *addend0, uint64_t *value0, uint64_t *discard_value; uint64_t discard_addend_i; uint64_t discard_value_i; + uint64_t discard_carry; + uint64_t discard_temp; 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" + __asm__ __volatile__ ( "\n1:\n\t" + /* Load addend[i] and value[i] */ + "ld.d %3, %0, 0\n\t" + "ld.d %4, %1, 0\n\t" + /* Add carry flag and addend */ + "add.d %4, %4, %5\n\t" + "sltu %6, %4, %5\n\t" + "add.d %4, %4, %3\n\t" + "sltu %5, %4, %3\n\t" + "or %5, %5, %6\n\t" + /* Store value[i] */ + "st.d %4, %1, 0\n\t" + /* Loop */ + "addi.d %0, %0, 8\n\t" "addi.d %1, %1, 8\n\t" "addi.w %2, %2, -1\n\t" - "bnez %2, 1b" + "bnez %2, 1b\n\t" : "=r" ( discard_addend ), "=r" ( discard_value ), "=r" ( discard_size ), "=r" ( discard_addend_i ), "=r" ( discard_value_i ), + "=r" ( discard_carry ), + "=r" ( discard_temp ), "+m" ( *value ) - : "0" ( addend0 ), - "1" ( value0 ), - "2" ( size ) - : "t0", "t1" ); + : "0" ( addend0 ), "1" ( value0 ), + "2" ( size ), "5" ( 0 ) ); } /** @@ -93,35 +96,43 @@ bigint_add_raw ( const uint64_t *addend0, uint64_t *value0, static inline __attribute__ (( always_inline )) void bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0, unsigned int size ) { + bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( void * ) value0 ); uint64_t *discard_subtrahend; uint64_t *discard_value; uint64_t discard_subtrahend_i; uint64_t discard_value_i; + uint64_t discard_carry; + uint64_t discard_temp; 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); + __asm__ __volatile__ ( "\n1:\n\t" + /* Load subtrahend[i] and value[i] */ + "ld.d %3, %0, 0\n\t" + "ld.d %4, %1, 0\n\t" + /* Subtract carry flag and subtrahend */ + "sltu %6, %4, %5\n\t" + "sub.d %4, %4, %5\n\t" + "sltu %5, %4, %3\n\t" + "sub.d %4, %4, %3\n\t" + "or %5, %5, %6\n\t" + /* Store value[i] */ + "st.d %4, %1, 0\n\t" + /* Loop */ + "addi.d %0, %0, 8\n\t" + "addi.d %1, %1, 8\n\t" + "addi.w %2, %2, -1\n\t" + "bnez %2, 1b\n\t" + : "=r" ( discard_subtrahend ), + "=r" ( discard_value ), + "=r" ( discard_size ), + "=r" ( discard_subtrahend_i ), + "=r" ( discard_value_i ), + "=r" ( discard_carry ), + "=r" ( discard_temp ), + "+m" ( *value ) + : "0" ( subtrahend0 ), "1" ( value0 ), + "2" ( size ), "5" ( 0 ) ); } /** @@ -132,30 +143,37 @@ bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0, */ static inline __attribute__ (( always_inline )) void bigint_rol_raw ( uint64_t *value0, unsigned int size ) { + bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( void * ) value0 ); uint64_t *discard_value; uint64_t discard_value_i; + uint64_t discard_carry; + uint64_t discard_temp; 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 ); + __asm__ __volatile__ ( "\n1:\n\t" + /* Load value[i] */ + "ld.d %2, %0, 0\n\t" + /* Shift left */ + "rotri.d %2, %2, 63\n\t" + "andi %4, %2, 1\n\t" + "xor %2, %2, %4\n\t" + "or %2, %2, %3\n\t" + "move %3, %4\n\t" + /* Store value[i] */ + "st.d %2, %0, 0\n\t" + /* Loop */ + "addi.d %0, %0, 8\n\t" + "addi.w %1, %1, -1\n\t" + "bnez %1, 1b\n\t" + : "=r" ( discard_value ), + "=r" ( discard_size ), + "=r" ( discard_value_i ), + "=r" ( discard_carry ), + "=r" ( discard_temp ), + "+m" ( *value ) + : "0" ( value0 ), "1" ( size ), "3" ( 0 ) + : "cc" ); } /** @@ -166,27 +184,37 @@ bigint_rol_raw ( uint64_t *value0, unsigned int size ) { */ static inline __attribute__ (( always_inline )) void bigint_ror_raw ( uint64_t *value0, unsigned int size ) { + bigint_t ( size ) __attribute__ (( may_alias )) *value = + ( ( void * ) value0 ); uint64_t *discard_value; uint64_t discard_value_i; - uint64_t discard_value_j; + uint64_t discard_carry; + uint64_t discard_temp; 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 ); + __asm__ __volatile__ ( "\n1:\n\t" + /* Load value[i] */ + "ld.d %2, %0, -8\n\t" + /* Shift right */ + "andi %4, %2, 1\n\t" + "xor %2, %2, %4\n\t" + "or %2, %2, %3\n\t" + "move %3, %4\n\t" + "rotri.d %2, %2, 1\n\t" + /* Store value[i] */ + "st.d %2, %0, -8\n\t" + /* Loop */ + "addi.d %0, %0, -8\n\t" + "addi.w %1, %1, -1\n\t" + "bnez %1, 1b\n\t" + : "=r" ( discard_value ), + "=r" ( discard_size ), + "=r" ( discard_value_i ), + "=r" ( discard_carry ), + "=r" ( discard_temp ), + "+m" ( *value ) + : "0" ( value0 + size ), "1" ( size ), "3" ( 0 ) + : "cc" ); } /** diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c index f09d7c7..76aca10 100644 --- a/src/tests/bigint_test.c +++ b/src/tests/bigint_test.c @@ -714,6 +714,15 @@ static void bigint_test_exec ( void ) { bigint_subtract_ok ( BIGINT ( 0xbb, 0x77, 0x32, 0x5a ), BIGINT ( 0x5a, 0xd5, 0xfe, 0x28 ), BIGINT ( 0x9f, 0x5e, 0xcb, 0xce ) ); + bigint_subtract_ok ( BIGINT ( 0x00, 0x00, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff ), + BIGINT ( 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x2a ), + BIGINT ( 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x2b ) ); bigint_subtract_ok ( BIGINT ( 0x7b, 0xaa, 0x16, 0xcf, 0x15, 0x87, 0xe0, 0x4f, 0x2c, 0xa3, 0xec, 0x2f, 0x46, 0xfb, 0x83, 0xc6, 0xe0, 0xee, |