summaryrefslogtreecommitdiffstats
path: root/src/arch/loong64/include/bits/bigint.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/arch/loong64/include/bits/bigint.h')
-rw-r--r--src/arch/loong64/include/bits/bigint.h336
1 files changed, 336 insertions, 0 deletions
diff --git a/src/arch/loong64/include/bits/bigint.h b/src/arch/loong64/include/bits/bigint.h
new file mode 100644
index 000000000..89e0b8679
--- /dev/null
+++ b/src/arch/loong64/include/bits/bigint.h
@@ -0,0 +1,336 @@
+#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 */
generated by cgit v1.2.3-55-g7522 (git 2.39.0) at 2026-07-30 08:21:20 +0200