[crypto] Expose carry flag from big integer addition and subtraction

Expose the effective carry (or borrow) out flag from big integer
addition and subtraction, and use this to elide an explicit bit test
when performing x25519 reduction.

Signed-off-by: Michael Brown <mcb30@ipxe.org>

8 files changed, 140 insertions, 85 deletions

diff --git a/src/arch/arm32/include/bits/bigint.h b/src/arch/arm32/include/bits/bigint.h
index 39d3dc347..95de32d83 100644
--- a/src/arch/arm32/include/bits/bigint.h
+++ b/src/arch/arm32/include/bits/bigint.h
@@ -43,8 +43,9 @@ bigint_init_raw ( uint32_t *value0, unsigned int size,
  * @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 )) void
+static inline __attribute__ (( always_inline )) int
 bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
 		 unsigned int size ) {
 	bigint_t ( size ) __attribute__ (( may_alias )) *value =
@@ -54,8 +55,9 @@ bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
 	uint32_t *discard_end;
 	uint32_t discard_addend_i;
 	uint32_t discard_value_i;
+	int carry;
 
-	__asm__ __volatile__ ( "adds %2, %0, %8, lsl #2\n\t" /* clear CF */
+	__asm__ __volatile__ ( "adds %2, %0, %9, lsl #2\n\t" /* clear CF */
 			       "\n1:\n\t"
 			       "ldmia %0!, {%3}\n\t"
 			       "ldr %4, [%1]\n\t"
@@ -68,9 +70,11 @@ bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
 				 "=l" ( discard_end ),
 				 "=l" ( discard_addend_i ),
 				 "=l" ( discard_value_i ),
+				 "=@cccs" ( carry ),
 				 "+m" ( *value )
-			       : "0" ( addend0 ), "1" ( value0 ), "l" ( size )
-			       : "cc" );
+			       : "0" ( addend0 ), "1" ( value0 ),
+				 "l" ( size ) );
+	return carry;
 }
 
 /**
@@ -79,8 +83,9 @@ bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
  * @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 )) void
+static inline __attribute__ (( always_inline )) int
 bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
 		      unsigned int size ) {
 	bigint_t ( size ) __attribute__ (( may_alias )) *value =
@@ -90,8 +95,9 @@ bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
 	uint32_t *discard_end;
 	uint32_t discard_subtrahend_i;
 	uint32_t discard_value_i;
+	int borrow;
 
-	__asm__ __volatile__ ( "add %2, %0, %8, lsl #2\n\t"
+	__asm__ __volatile__ ( "add %2, %0, %9, lsl #2\n\t"
 			       "cmp %2, %0\n\t" /* set CF */
 			       "\n1:\n\t"
 			       "ldmia %0!, {%3}\n\t"
@@ -105,10 +111,11 @@ bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
 				 "=l" ( discard_end ),
 				 "=l" ( discard_subtrahend_i ),
 				 "=l" ( discard_value_i ),
+				 "=@cccc" ( borrow ),
 				 "+m" ( *value )
 			       : "0" ( subtrahend0 ), "1" ( value0 ),
-				 "l" ( size )
-			       : "cc" );
+				 "l" ( size ) );
+	return borrow;
 }
 
 /**
diff --git a/src/arch/arm64/include/bits/bigint.h b/src/arch/arm64/include/bits/bigint.h
index 50493499e..5f79dc0c3 100644
--- a/src/arch/arm64/include/bits/bigint.h
+++ b/src/arch/arm64/include/bits/bigint.h
@@ -43,8 +43,9 @@ bigint_init_raw ( uint64_t *value0, unsigned int size,
  * @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 )) void
+static inline __attribute__ (( always_inline )) int
 bigint_add_raw ( const uint64_t *addend0, uint64_t *value0,
 		 unsigned int size ) {
 	bigint_t ( size ) __attribute__ (( may_alias )) *value =
@@ -54,6 +55,7 @@ bigint_add_raw ( const uint64_t *addend0, uint64_t *value0,
 	uint64_t discard_addend_i;
 	uint64_t discard_value_i;
 	unsigned int discard_size;
+	int carry;
 
 	__asm__ __volatile__ ( "cmn xzr, xzr\n\t" /* clear CF */
 			       "\n1:\n\t"
@@ -68,9 +70,11 @@ bigint_add_raw ( const uint64_t *addend0, uint64_t *value0,
 				 "=r" ( discard_size ),
 				 "=r" ( discard_addend_i ),
 				 "=r" ( discard_value_i ),
+				 "=@cccs" ( carry ),
 				 "+m" ( *value )
-			       : "0" ( addend0 ), "1" ( value0 ), "2" ( size )
-			       : "cc" );
+			       : "0" ( addend0 ), "1" ( value0 ),
+				 "2" ( size ) );
+	return carry;
 }
 
 /**
@@ -79,8 +83,9 @@ bigint_add_raw ( const uint64_t *addend0, uint64_t *value0,
  * @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 )) void
+static inline __attribute__ (( always_inline )) int
 bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0,
 		      unsigned int size ) {
 	bigint_t ( size ) __attribute__ (( may_alias )) *value =
@@ -90,6 +95,7 @@ bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0,
 	uint64_t discard_subtrahend_i;
 	uint64_t discard_value_i;
 	unsigned int discard_size;
+	int borrow;
 
 	__asm__ __volatile__ ( "cmp xzr, xzr\n\t" /* set CF */
 			       "\n1:\n\t"
@@ -104,10 +110,11 @@ bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0,
 				 "=r" ( discard_size ),
 				 "=r" ( discard_subtrahend_i ),
 				 "=r" ( discard_value_i ),
+				 "=@cccc" ( borrow ),
 				 "+m" ( *value )
 			       : "0" ( subtrahend0 ), "1" ( value0 ),
-				 "2" ( size )
-			       : "cc" );
+				 "2" ( size ) );
+	return borrow;
 }
 
 /**
diff --git a/src/arch/loong64/include/bits/bigint.h b/src/arch/loong64/include/bits/bigint.h
index 234d8dfa7..0222354df 100644
--- a/src/arch/loong64/include/bits/bigint.h
+++ b/src/arch/loong64/include/bits/bigint.h
@@ -43,8 +43,9 @@ bigint_init_raw ( uint64_t *value0, unsigned int size,
  * @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 )) void
+static inline __attribute__ (( always_inline )) int
 bigint_add_raw ( const uint64_t *addend0, uint64_t *value0,
 		 unsigned int size ) {
 	bigint_t ( size ) __attribute__ (( may_alias )) *value =
@@ -53,20 +54,20 @@ 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;
+	uint64_t carry;
 
 	__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, %6\n\t"
+			       "sltu %5, %4, %6\n\t"
 			       "add.d %4, %4, %3\n\t"
-			       "sltu %5, %4, %3\n\t"
-			       "or %5, %5, %6\n\t"
+			       "sltu %6, %4, %3\n\t"
+			       "or %6, %5, %6\n\t"
 			       /* Store value[i] */
 			       "st.d %4, %1, 0\n\t"
 			       /* Loop */
@@ -79,11 +80,12 @@ bigint_add_raw ( const uint64_t *addend0, uint64_t *value0,
 				 "=r" ( discard_size ),
 				 "=r" ( discard_addend_i ),
 				 "=r" ( discard_value_i ),
-				 "=r" ( discard_carry ),
 				 "=r" ( discard_temp ),
+				 "=r" ( carry ),
 				 "+m" ( *value )
 			       : "0" ( addend0 ), "1" ( value0 ),
-				 "2" ( size ), "5" ( 0 ) );
+				 "2" ( size ), "6" ( 0 ) );
+	return carry;
 }
 
 /**
@@ -92,8 +94,9 @@ bigint_add_raw ( const uint64_t *addend0, uint64_t *value0,
  * @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 )) void
+static inline __attribute__ (( always_inline )) int
 bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0,
 		      unsigned int size ) {
 	bigint_t ( size ) __attribute__ (( may_alias )) *value =
@@ -102,20 +105,20 @@ bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0,
 	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;
+	uint64_t borrow;
 
 	__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"
+			       "sltu %5, %4, %6\n\t"
+			       "sub.d %4, %4, %6\n\t"
+			       "sltu %6, %4, %3\n\t"
 			       "sub.d %4, %4, %3\n\t"
-			       "or %5, %5, %6\n\t"
+			       "or %6, %5, %6\n\t"
 			       /* Store value[i] */
 			       "st.d %4, %1, 0\n\t"
 			       /* Loop */
@@ -128,11 +131,12 @@ bigint_subtract_raw ( const uint64_t *subtrahend0, uint64_t *value0,
 				 "=r" ( discard_size ),
 				 "=r" ( discard_subtrahend_i ),
 				 "=r" ( discard_value_i ),
-				 "=r" ( discard_carry ),
 				 "=r" ( discard_temp ),
+				 "=r" ( borrow ),
 				 "+m" ( *value )
 			       : "0" ( subtrahend0 ), "1" ( value0 ),
-				 "2" ( size ), "5" ( 0 ) );
+				 "2" ( size ), "6" ( 0 ) );
+	return borrow;
 }
 
 /**
diff --git a/src/arch/riscv/include/bits/bigint.h b/src/arch/riscv/include/bits/bigint.h
index 5b22b9ac7..ab1070d88 100644
--- a/src/arch/riscv/include/bits/bigint.h
+++ b/src/arch/riscv/include/bits/bigint.h
@@ -43,8 +43,9 @@ bigint_init_raw ( unsigned long *value0, unsigned int size,
  * @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 )) void
+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 =
@@ -54,19 +55,19 @@ bigint_add_raw ( const unsigned long *addend0, unsigned long *value0,
 	unsigned long *discard_value;
 	unsigned long discard_addend_i;
 	unsigned long discard_value_i;
-	unsigned long discard_carry;
 	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, %4\n\t"
-			       "sltu %5, %3, %4\n\t"
+			       "add %3, %3, %5\n\t"
+			       "sltu %4, %3, %5\n\t"
 			       "add %3, %3, %2\n\t"
-			       "sltu %4, %3, %2\n\t"
-			       "or %4, %4, %5\n\t"
+			       "sltu %5, %3, %2\n\t"
+			       "or %5, %4, %5\n\t"
 			       /* Store value[i] */
 			       STOREN " %3, (%1)\n\t"
 			       /* Loop */
@@ -77,12 +78,13 @@ bigint_add_raw ( const unsigned long *addend0, unsigned long *value0,
 				 "=&r" ( discard_value ),
 				 "=&r" ( discard_addend_i ),
 				 "=&r" ( discard_value_i ),
-				 "=&r" ( discard_carry ),
 				 "=&r" ( discard_temp ),
+				 "=&r" ( carry ),
 				 "+m" ( *value )
 			       : "r" ( valueN ),
 				 "i" ( sizeof ( unsigned long ) ),
-				 "0" ( addend0 ), "1" ( value0 ), "4" ( 0 ) );
+				 "0" ( addend0 ), "1" ( value0 ), "5" ( 0 ) );
+	return carry;
 }
 
 /**
@@ -91,8 +93,9 @@ bigint_add_raw ( const unsigned long *addend0, unsigned long *value0,
  * @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 )) void
+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 =
@@ -102,19 +105,19 @@ bigint_subtract_raw ( const unsigned long *subtrahend0, unsigned long *value0,
 	unsigned long *discard_value;
 	unsigned long discard_subtrahend_i;
 	unsigned long discard_value_i;
-	unsigned long discard_carry;
 	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 %5, %3, %4\n\t"
-			       "sub %3, %3, %4\n\t"
-			       "sltu %4, %3, %2\n\t"
+			       "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 %4, %4, %5\n\t"
+			       "or %5, %5, %4\n\t"
 			       /* Store value[i] */
 			       STOREN " %3, (%1)\n\t"
 			       /* Loop */
@@ -125,13 +128,14 @@ bigint_subtract_raw ( const unsigned long *subtrahend0, unsigned long *value0,
 				 "=&r" ( discard_value ),
 				 "=&r" ( discard_subtrahend_i ),
 				 "=&r" ( discard_value_i ),
-				 "=&r" ( discard_carry ),
 				 "=&r" ( discard_temp ),
+				 "=&r" ( borrow ),
 				 "+m" ( *value )
 			       : "r" ( valueN ),
 				 "i" ( sizeof ( unsigned long ) ),
 				 "0" ( subtrahend0 ), "1" ( value0 ),
-				 "4" ( 0 ) );
+				 "5" ( 0 ) );
+	return borrow;
 }
 
 /**
diff --git a/src/arch/x86/include/bits/bigint.h b/src/arch/x86/include/bits/bigint.h
index 5580030ee..4026ca481 100644
--- a/src/arch/x86/include/bits/bigint.h
+++ b/src/arch/x86/include/bits/bigint.h
@@ -52,8 +52,9 @@ bigint_init_raw ( uint32_t *value0, unsigned int size,
  * @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 flag
  */
-static inline __attribute__ (( always_inline )) void
+static inline __attribute__ (( always_inline )) int
 bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
 		 unsigned int size ) {
 	bigint_t ( size ) __attribute__ (( may_alias )) *value =
@@ -61,17 +62,20 @@ bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
 	long index;
 	void *discard_S;
 	long discard_c;
+	int carry;
 
 	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
 			       "\n1:\n\t"
 			       "lodsl\n\t"
-			       "adcl %%eax, (%4,%0,4)\n\t"
+			       "adcl %%eax, (%5,%0,4)\n\t"
 			       "inc %0\n\t" /* Does not affect CF */
 			       "loop 1b\n\t"
 			       : "=&r" ( index ), "=&S" ( discard_S ),
-				 "=&c" ( discard_c ), "+m" ( *value )
+				 "=&c" ( discard_c ), "=@ccc" ( carry ),
+				 "+m" ( *value )
 			       : "r" ( value0 ), "1" ( addend0 ), "2" ( size )
 			       : "eax" );
+	return carry;
 }
 
 /**
@@ -80,8 +84,9 @@ bigint_add_raw ( const uint32_t *addend0, uint32_t *value0,
  * @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 flag
  */
-static inline __attribute__ (( always_inline )) void
+static inline __attribute__ (( always_inline )) int
 bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
 		      unsigned int size ) {
 	bigint_t ( size ) __attribute__ (( may_alias )) *value =
@@ -89,18 +94,21 @@ bigint_subtract_raw ( const uint32_t *subtrahend0, uint32_t *value0,
 	long index;
 	void *discard_S;
 	long discard_c;
+	int borrow;
 
 	__asm__ __volatile__ ( "xor %0, %0\n\t" /* Zero %0 and clear CF */
 			       "\n1:\n\t"
 			       "lodsl\n\t"
-			       "sbbl %%eax, (%4,%0,4)\n\t"
+			       "sbbl %%eax, (%5,%0,4)\n\t"
 			       "inc %0\n\t" /* Does not affect CF */
 			       "loop 1b\n\t"
 			       : "=&r" ( index ), "=&S" ( discard_S ),
-				 "=&c" ( discard_c ), "+m" ( *value )
+				 "=&c" ( discard_c ), "=@ccc" ( borrow ),
+				 "+m" ( *value )
 			       : "r" ( value0 ), "1" ( subtrahend0 ),
 				 "2" ( size )
 			       : "eax" );
+	return borrow;
 }
 
 /**
diff --git a/src/crypto/x25519.c b/src/crypto/x25519.c
index 19f9a2c02..ab5d2e8b0 100644
--- a/src/crypto/x25519.c
+++ b/src/crypto/x25519.c
@@ -564,6 +564,7 @@ void x25519_invert ( const union x25519_oct258 *invertend,
  */
 static void x25519_reduce_by ( const x25519_t *subtrahend, x25519_t *value ) {
 	x25519_t tmp;
+	int underflow;
 
 	/* Conditionally subtract subtrahend
 	 *
@@ -571,8 +572,8 @@ static void x25519_reduce_by ( const x25519_t *subtrahend, x25519_t *value ) {
 	 * time) if the subtraction underflows.
 	 */
 	bigint_copy ( value, &tmp );
-	bigint_subtract ( subtrahend, value );
-	bigint_swap ( value, &tmp, bigint_msb_is_set ( value ) );
+	underflow = bigint_subtract ( subtrahend, value );
+	bigint_swap ( value, &tmp, underflow );
 }
 
 /**
diff --git a/src/include/ipxe/bigint.h b/src/include/ipxe/bigint.h
index a85761815..2a0a200c5 100644
--- a/src/include/ipxe/bigint.h
+++ b/src/include/ipxe/bigint.h
@@ -70,23 +70,25 @@ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  *
  * @v addend		Big integer to add
  * @v value		Big integer to be added to
+ * @ret carry		Carry out
  */
-#define bigint_add( addend, value ) do {				\
+#define bigint_add( addend, value ) ( {					\
 	unsigned int size = bigint_size (addend);			\
 	bigint_add_raw ( (addend)->element, (value)->element, size );	\
-	} while ( 0 )
+	} )
 
 /**
  * Subtract big integers
  *
  * @v subtrahend	Big integer to subtract
  * @v value		Big integer to be subtracted from
+ * @ret borrow		Borrow out
  */
-#define bigint_subtract( subtrahend, value ) do {			\
+#define bigint_subtract( subtrahend, value ) ( {			\
 	unsigned int size = bigint_size (subtrahend);			\
 	bigint_subtract_raw ( (subtrahend)->element, (value)->element,	\
 			      size );					\
-	} while ( 0 )
+	} )
 
 /**
  * Shift big integer left
@@ -389,10 +391,10 @@ void bigint_init_raw ( bigint_element_t *value0, unsigned int size,
 		       const void *data, size_t len );
 void bigint_done_raw ( const bigint_element_t *value0, unsigned int size,
 		       void *out, size_t len );
-void bigint_add_raw ( const bigint_element_t *addend0,
-		      bigint_element_t *value0, unsigned int size );
-void bigint_subtract_raw ( const bigint_element_t *subtrahend0,
-			   bigint_element_t *value0, unsigned int size );
+int bigint_add_raw ( const bigint_element_t *addend0,
+		     bigint_element_t *value0, unsigned int size );
+int bigint_subtract_raw ( const bigint_element_t *subtrahend0,
+			  bigint_element_t *value0, unsigned int size );
 void bigint_shl_raw ( bigint_element_t *value0, unsigned int size );
 void bigint_shr_raw ( bigint_element_t *value0, unsigned int size );
 int bigint_is_zero_raw ( const bigint_element_t *value0, unsigned int size );
diff --git a/src/tests/bigint_test.c b/src/tests/bigint_test.c
index 166c771b9..271d76723 100644
--- a/src/tests/bigint_test.c
+++ b/src/tests/bigint_test.c
@@ -58,24 +58,24 @@ void bigint_done_sample ( const bigint_element_t *value0, unsigned int size,
 	bigint_done ( value, out, len );
 }
 
-void bigint_add_sample ( const bigint_element_t *addend0,
-			 bigint_element_t *value0, unsigned int size ) {
+int bigint_add_sample ( const bigint_element_t *addend0,
+			bigint_element_t *value0, unsigned int size ) {
 	const bigint_t ( size ) *addend __attribute__ (( may_alias ))
 		= ( ( const void * ) addend0 );
 	bigint_t ( size ) *value __attribute__ (( may_alias ))
 		= ( ( void * ) value0 );
 
-	bigint_add ( addend, value );
+	return bigint_add ( addend, value );
 }
 
-void bigint_subtract_sample ( const bigint_element_t *subtrahend0,
-			      bigint_element_t *value0, unsigned int size ) {
+int bigint_subtract_sample ( const bigint_element_t *subtrahend0,
+			     bigint_element_t *value0, unsigned int size ) {
 	const bigint_t ( size ) *subtrahend __attribute__ (( may_alias ))
 		= ( ( const void * ) subtrahend0 );
 	bigint_t ( size ) *value __attribute__ (( may_alias ))
 		= ( ( void * ) value0 );
 
-	bigint_subtract ( subtrahend, value );
+	return bigint_subtract ( subtrahend, value );
 }
 
 void bigint_shl_sample ( bigint_element_t *value0, unsigned int size ) {
@@ -253,16 +253,19 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0,
  * @v addend		Big integer to add
  * @v value		Big integer to be added to
  * @v expected		Big integer expected result
+ * @v overflow		Expected result overflows range
  */
-#define bigint_add_ok( addend, value, expected ) do {			\
+#define bigint_add_ok( addend, value, expected, overflow ) do {		\
 	static const uint8_t addend_raw[] = addend;			\
 	static const uint8_t value_raw[] = value;			\
 	static const uint8_t expected_raw[] = expected;			\
 	uint8_t result_raw[ sizeof ( expected_raw ) ];			\
 	unsigned int size =						\
 		bigint_required_size ( sizeof ( value_raw ) );		\
+	unsigned int msb = ( 8 * sizeof ( value_raw ) );		\
 	bigint_t ( size ) addend_temp;					\
 	bigint_t ( size ) value_temp;					\
+	int carry;							\
 	{} /* Fix emacs alignment */					\
 									\
 	assert ( bigint_size ( &addend_temp ) ==			\
@@ -273,12 +276,15 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0,
 	DBG ( "Add:\n" );						\
 	DBG_HDA ( 0, &addend_temp, sizeof ( addend_temp ) );		\
 	DBG_HDA ( 0, &value_temp, sizeof ( value_temp ) );		\
-	bigint_add ( &addend_temp, &value_temp );			\
+	carry = bigint_add ( &addend_temp, &value_temp );		\
 	DBG_HDA ( 0, &value_temp, sizeof ( value_temp ) );		\
 	bigint_done ( &value_temp, result_raw, sizeof ( result_raw ) );	\
 									\
 	ok ( memcmp ( result_raw, expected_raw,				\
 		      sizeof ( result_raw ) ) == 0 );			\
+	if ( sizeof ( result_raw ) < sizeof ( value_temp ) )		\
+		carry += bigint_bit_is_set ( &value_temp, msb );	\
+	ok ( carry == overflow );					\
 	} while ( 0 )
 
 /**
@@ -287,8 +293,10 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0,
  * @v subtrahend	Big integer to subtract
  * @v value		Big integer to be subtracted from
  * @v expected		Big integer expected result
+ * @v underflow		Expected result underflows range
  */
-#define bigint_subtract_ok( subtrahend, value, expected ) do {		\
+#define bigint_subtract_ok( subtrahend, value, expected,		\
+			    underflow ) do {				\
 	static const uint8_t subtrahend_raw[] = subtrahend;		\
 	static const uint8_t value_raw[] = value;			\
 	static const uint8_t expected_raw[] = expected;			\
@@ -297,6 +305,7 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0,
 		bigint_required_size ( sizeof ( value_raw ) );		\
 	bigint_t ( size ) subtrahend_temp;				\
 	bigint_t ( size ) value_temp;					\
+	int borrow;							\
 	{} /* Fix emacs alignment */					\
 									\
 	assert ( bigint_size ( &subtrahend_temp ) ==			\
@@ -307,12 +316,13 @@ void bigint_mod_exp_sample ( const bigint_element_t *base0,
 	DBG ( "Subtract:\n" );						\
 	DBG_HDA ( 0, &subtrahend_temp, sizeof ( subtrahend_temp ) );	\
 	DBG_HDA ( 0, &value_temp, sizeof ( value_temp ) );		\
-	bigint_subtract ( &subtrahend_temp, &value_temp );		\
+	borrow = bigint_subtract ( &subtrahend_temp, &value_temp );	\
 	DBG_HDA ( 0, &value_temp, sizeof ( value_temp ) );		\
 	bigint_done ( &value_temp, result_raw, sizeof ( result_raw ) );	\
 									\
 	ok ( memcmp ( result_raw, expected_raw,				\
 		      sizeof ( result_raw ) ) == 0 );			\
+	ok ( borrow == underflow );					\
 	} while ( 0 )
 
 /**
@@ -724,16 +734,28 @@ static void bigint_test_exec ( void ) {
 
 	bigint_add_ok ( BIGINT ( 0x8a ),
 			BIGINT ( 0x43 ),
-			BIGINT ( 0xcd ) );
+			BIGINT ( 0xcd ), 0 );
 	bigint_add_ok ( BIGINT ( 0xc5, 0x7b ),
 			BIGINT ( 0xd6, 0xb1 ),
-			BIGINT ( 0x9c, 0x2c ) );
+			BIGINT ( 0x9c, 0x2c ), 1 );
 	bigint_add_ok ( BIGINT ( 0xf9, 0xd9, 0xdc ),
 			BIGINT ( 0x6d, 0x4b, 0xca ),
-			BIGINT ( 0x67, 0x25, 0xa6 ) );
+			BIGINT ( 0x67, 0x25, 0xa6 ), 1 );
 	bigint_add_ok ( BIGINT ( 0xdd, 0xc2, 0x20, 0x5f ),
 			BIGINT ( 0x80, 0x32, 0xc4, 0xb0 ),
-			BIGINT ( 0x5d, 0xf4, 0xe5, 0x0f ) );
+			BIGINT ( 0x5d, 0xf4, 0xe5, 0x0f ), 1 );
+	bigint_add_ok ( BIGINT ( 0x5e, 0x46, 0x4d, 0xc6, 0xa2, 0x7d, 0x45,
+				 0xc3 ),
+			BIGINT ( 0xd6, 0xc0, 0xd7, 0xd4, 0xf6, 0x04, 0x47,
+				 0xed ),
+			BIGINT ( 0x35, 0x07, 0x25, 0x9b, 0x98, 0x81, 0x8d,
+				 0xb0 ), 1 );
+	bigint_add_ok ( BIGINT ( 0x0e, 0x46, 0x4d, 0xc6, 0xa2, 0x7d, 0x45,
+				 0xc3 ),
+			BIGINT ( 0xd6, 0xc0, 0xd7, 0xd4, 0xf6, 0x04, 0x47,
+				 0xed ),
+			BIGINT ( 0xe5, 0x07, 0x25, 0x9b, 0x98, 0x81, 0x8d,
+				 0xb0 ), 0 );
 	bigint_add_ok ( BIGINT ( 0x01, 0xed, 0x45, 0x4b, 0x41, 0xeb, 0x4c,
 				 0x2e, 0x53, 0x07, 0x15, 0x51, 0x56, 0x47,
 				 0x29, 0xfc, 0x9c, 0xbd, 0xbd, 0xfb, 0x1b,
@@ -745,7 +767,7 @@ static void bigint_test_exec ( void ) {
 			BIGINT ( 0x75, 0xdb, 0x41, 0x80, 0x73, 0x0e, 0x23,
 				 0xe0, 0x3d, 0x98, 0x70, 0x36, 0x11, 0x03,
 				 0xcb, 0x35, 0x0f, 0x6c, 0x09, 0x17, 0xdc,
-				 0xd6, 0xd0 ) );
+				 0xd6, 0xd0 ), 0 );
 	bigint_add_ok ( BIGINT ( 0x06, 0x8e, 0xd6, 0x18, 0xbb, 0x4b, 0x0c,
 				 0xc5, 0x85, 0xde, 0xee, 0x9b, 0x3f, 0x65,
 				 0x63, 0x86, 0xf5, 0x5a, 0x9f, 0xa2, 0xd7,
@@ -802,19 +824,19 @@ static void bigint_test_exec ( void ) {
 				 0x68, 0x76, 0xf5, 0x20, 0xa1, 0xa8, 0x1a,
 				 0x9f, 0x60, 0x58, 0xff, 0xb6, 0x76, 0x45,
 				 0xe6, 0xed, 0x61, 0x8d, 0xe6, 0xc0, 0x72,
-				 0x1c, 0x07 ) );
+				 0x1c, 0x07 ), 0 );
 	bigint_subtract_ok ( BIGINT ( 0x83 ),
 			     BIGINT ( 0x50 ),
-			     BIGINT ( 0xcd ) );
+			     BIGINT ( 0xcd ), 1 );
 	bigint_subtract_ok ( BIGINT ( 0x2c, 0x7c ),
 			     BIGINT ( 0x49, 0x0e ),
-			     BIGINT ( 0x1c, 0x92 ) );
+			     BIGINT ( 0x1c, 0x92 ), 0 );
 	bigint_subtract_ok ( BIGINT ( 0x9c, 0x30, 0xbf ),
 			     BIGINT ( 0xde, 0x4e, 0x07 ),
-			     BIGINT ( 0x42, 0x1d, 0x48 ) );
+			     BIGINT ( 0x42, 0x1d, 0x48 ), 0 );
 	bigint_subtract_ok ( BIGINT ( 0xbb, 0x77, 0x32, 0x5a ),
 			     BIGINT ( 0x5a, 0xd5, 0xfe, 0x28 ),
-			     BIGINT ( 0x9f, 0x5e, 0xcb, 0xce ) );
+			     BIGINT ( 0x9f, 0x5e, 0xcb, 0xce ), 1 );
 	bigint_subtract_ok ( BIGINT ( 0x00, 0x00, 0xff, 0xff, 0xff, 0xff,
 				      0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
 				      0xff, 0xff, 0xff, 0xff, 0xff, 0xff ),
@@ -823,7 +845,7 @@ static void bigint_test_exec ( void ) {
 				      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 ) );
+				      0x00, 0x00, 0x00, 0x00, 0x00, 0x2b ), 1 );
 	bigint_subtract_ok ( BIGINT ( 0x7b, 0xaa, 0x16, 0xcf, 0x15, 0x87,
 				      0xe0, 0x4f, 0x2c, 0xa3, 0xec, 0x2f,
 				      0x46, 0xfb, 0x83, 0xc6, 0xe0, 0xee,
@@ -835,7 +857,7 @@ static void bigint_test_exec ( void ) {
 			     BIGINT ( 0xca, 0xab, 0x9f, 0x54, 0x4e, 0x48,
 				      0x75, 0x8c, 0x63, 0x28, 0x69, 0x78,
 				      0xe8, 0x8a, 0x3d, 0xd8, 0x4b, 0x24,
-				      0xb8, 0xa4, 0x71, 0x6d, 0x6b ) );
+				      0xb8, 0xa4, 0x71, 0x6d, 0x6b ), 1 );
 	bigint_subtract_ok ( BIGINT ( 0x5b, 0x06, 0x77, 0x7b, 0xfd, 0x34,
 				      0x5f, 0x0f, 0xd9, 0xbd, 0x8e, 0x5d,
 				      0xc8, 0x4a, 0x70, 0x95, 0x1b, 0xb6,
@@ -901,7 +923,7 @@ static void bigint_test_exec ( void ) {
 				      0x29, 0x8c, 0x43, 0x9f, 0xf0, 0x9d,
 				      0xda, 0xc8, 0x8c, 0x71, 0x86, 0x97,
 				      0x7f, 0xcb, 0x94, 0x31, 0x1d, 0xbc,
-				      0x44, 0x1a ) );
+				      0x44, 0x1a ), 0 );
 	bigint_shl_ok ( BIGINT ( 0xe0 ),
 			BIGINT ( 0xc0 ) );
 	bigint_shl_ok ( BIGINT ( 0x43, 0x1d ),