utilities.h File Reference

#include <stdio.h>
#include <stdint.h>

Include dependency graph for utilities.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	NUMBER_OF_BENCHMARK_EXPERIMENTS   500
#define	NUMBER_OF_TEST_EXPERIMENTS   500
#define	addition_with_carry_u64(output, output_carry, input_carry, input_a, input_b)
#define	subtraction_with_borrow_u64(output, output_borrow, input_borrow, input_a, input_b)
#define	constant_time_shift_to_right_u64(shiftOut, highIn, lowIn, shift, DigitSize)    (shiftOut) = ((lowIn) >> (shift)) ^ ((highIn) << ((DigitSize) - (shift)));
#define	constant_time_shift_to_left_u64(shiftOut, highIn, lowIn, shift, DigitSize)    (shiftOut) = ((highIn) << (shift)) ^ ((lowIn) >> ((DigitSize) - (shift)));

Functions
void	multiplication_u64 (uint64_t *output_low, uint64_t *output_high, uint64_t input_a, uint64_t input_b)
void	conditional_move_u64 (uint64_t *output, uint8_t input_decision, uint64_t input_a, uint64_t input_b)
uint64_t	constant_time_is_nonzero_u64 (uint64_t x)
uint64_t	constant_time_is_zero_u64 (uint64_t x)
uint64_t	constant_time_is_lessthan_u64 (uint64_t x, uint64_t y)
uint8_t	constant_time_compare (const uint8_t *input_a, const uint8_t *input_b, uint64_t input_length)
void	constant_time_conditional_mov (uint8_t *output, const uint8_t *input, uint64_t input_length, uint8_t input_selector)
void	multiprecision_shift_to_right (uint64_t *input_a_output_shifted_a, uint64_t input_words_length)
void	multiprecision_shift_to_left (uint64_t *input_a_output_shifted_a, uint64_t input_words_length)
void	multiprecision_addition (uint64_t *output, const uint64_t *input_a, const uint64_t *input_b, uint64_t input_length)
void	multiprecision_subtraction (uint64_t *output, const uint64_t *input_a, const uint64_t *input_b, uint64_t input_length)
uint8_t	multiprecision_is_smaller (const uint64_t *input1, const uint64_t *input2, uint64_t input_length)

Macro Definition Documentation

addition_with_carry_u64

#define addition_with_carry_u64	(		output,
			output_carry,
			input_carry,
			input_a,
			input_b
	)

Value:

    { uint64_t tmp = (input_a) + (uint64_t)(input_carry);                               \
    (output) = (input_b) + tmp;                                                         \
    (output_carry) = (constant_time_is_lessthan_u64(tmp, (uint64_t)(input_carry)) | constant_time_is_lessthan_u64((output), tmp)); }

Definition at line 34 of file utilities.h.

    { uint64_t tmp = (input_a) + (uint64_t)(input_carry);                               \
    (output) = (input_b) + tmp;                                                         \
    (output_carry) = (constant_time_is_lessthan_u64(tmp, (uint64_t)(input_carry)) | constant_time_is_lessthan_u64((output), tmp)); }

constant_time_shift_to_left_u64

#define constant_time_shift_to_left_u64	(		shiftOut,
			highIn,
			lowIn,
			shift,
			DigitSize
	)		(shiftOut) = ((highIn) << (shift)) ^ ((lowIn) >> ((DigitSize) - (shift)));

Definition at line 48 of file utilities.h.

constant_time_shift_to_right_u64

#define constant_time_shift_to_right_u64	(		shiftOut,
			highIn,
			lowIn,
			shift,
			DigitSize
	)		(shiftOut) = ((lowIn) >> (shift)) ^ ((highIn) << ((DigitSize) - (shift)));

Definition at line 45 of file utilities.h.

NUMBER_OF_BENCHMARK_EXPERIMENTS

#define NUMBER_OF_BENCHMARK_EXPERIMENTS   500

Definition at line 15 of file utilities.h.

NUMBER_OF_TEST_EXPERIMENTS

#define NUMBER_OF_TEST_EXPERIMENTS   500

Definition at line 16 of file utilities.h.

subtraction_with_borrow_u64

#define subtraction_with_borrow_u64	(		output,
			output_borrow,
			input_borrow,
			input_a,
			input_b
	)

Value:

    { uint64_t tmp = (input_a) - (input_b);                                                                         \
    uint64_t borrowReg = (constant_time_is_lessthan_u64((input_a), (input_b)) | ((input_borrow) & constant_time_is_zero_u64(tmp)));   \
    (output) = tmp - (uint64_t)(input_borrow);                                                                      \
    (output_borrow) = borrowReg; }

Definition at line 39 of file utilities.h.

    { uint64_t tmp = (input_a) - (input_b);                                                                         \
    uint64_t borrowReg = (constant_time_is_lessthan_u64((input_a), (input_b)) | ((input_borrow) & constant_time_is_zero_u64(tmp)));   \
    (output) = tmp - (uint64_t)(input_borrow);                                                                      \
    (output_borrow) = borrowReg; }

Function Documentation

conditional_move_u64()

void conditional_move_u64	(	uint64_t *	output,
		uint8_t	input_decision,
		uint64_t	input_a,
		uint64_t	input_b
	)

Definition at line 40 of file utilities.c.

                                                                                                        {
    uint8_t x1;
    uint64_t x2;
    uint64_t x3;
    x1 = (!(!input_decision));
    x2 = ((int8_t) (0x0 - x1) & UINT64_C(0xffffffffffffffff));
    x3 = ((x2 & input_b) | ((~x2) & input_a));
    *output = x3;
}

constant_time_compare()

uint8_t constant_time_compare	(	const uint8_t *	input_a,
		const uint8_t *	input_b,
		uint64_t	input_length
	)

Definition at line 62 of file utilities.c.

                                                                                                     {
    uint64_t r = 0;
    uint64_t i;
 
    for (i = 0; i < input_length; i++)
        r |= input_a[i] ^ input_b[i];
 
    r = (-r);
    r = r >> 63;
    return (uint8_t)(1 - r);
}

References i.

Referenced by multiprecision_is_smaller().

Here is the caller graph for this function:

constant_time_conditional_mov()

void constant_time_conditional_mov	(	uint8_t *	output,
		const uint8_t *	input,
		uint64_t	input_length,
		uint8_t	input_selector
	)

Definition at line 74 of file utilities.c.

                                                                                                                         {
    uint64_t i;
    for (i = 0; i < input_length; i++)
        output[i] ^= input_selector & (input[i] ^ output[i]);
}

References i.

Referenced by fp2_sqrt_fast().

Here is the caller graph for this function:

constant_time_is_lessthan_u64()

uint64_t constant_time_is_lessthan_u64	(	uint64_t	x,
		uint64_t	y
	)

Definition at line 58 of file utilities.c.

                                                               {
    return (uint64_t) ((x ^ ((x ^ y) | ((x - y) ^ y))) >> 63);
}

Referenced by isogeny_walks_3_fp(), isogeny_walks_3_fp(), and multiprecision_is_smaller().

Here is the caller graph for this function:

constant_time_is_nonzero_u64()

uint64_t constant_time_is_nonzero_u64

(

uint64_t

x

)

Definition at line 50 of file utilities.c.

                                                  {
    return (uint64_t) ((x | (0 - x)) >> 63);
}

Referenced by constant_time_is_zero_u64().

Here is the caller graph for this function:

constant_time_is_zero_u64()

uint64_t constant_time_is_zero_u64

(

uint64_t

x

)

Definition at line 54 of file utilities.c.

                                               {
    return (uint64_t) (1 ^ constant_time_is_nonzero_u64(x));
}

References constant_time_is_nonzero_u64().

Here is the call graph for this function:

multiplication_u64()

void multiplication_u64	(	uint64_t *	output_low,
		uint64_t *	output_high,
		uint64_t	input_a,
		uint64_t	input_b
	)

Definition at line 7 of file utilities.c.

                                                                                                         {
    register uint64_t al, ah, bl, bh, temp;
    uint64_t albl, albh, ahbl, ahbh, res1, res2, res3, carry;
    uint64_t mask_low = (uint64_t) (-1) >> (sizeof(uint64_t) * 4), mask_high =
            (uint64_t) (-1) << (sizeof(uint64_t) * 4);
 
    al = input_a & mask_low;                         // Low part
    ah = input_a >> (sizeof(uint64_t) * 4);          // High part
    bl = input_b & mask_low;
    bh = input_b >> (sizeof(uint64_t) * 4);
 
    albl = al * bl;
    albh = al * bh;
    ahbl = ah * bl;
    ahbh = ah * bh;
    *output_low = albl & mask_low;                   // C00
 
    res1 = albl >> (sizeof(uint64_t) * 4);
    res2 = ahbl & mask_low;
    res3 = albh & mask_low;
    temp = res1 + res2 + res3;
    carry = temp >> (sizeof(uint64_t) * 4);
    *output_low ^= temp << (sizeof(uint64_t) * 4);    // C01
 
    res1 = ahbl >> (sizeof(uint64_t) * 4);
    res2 = albh >> (sizeof(uint64_t) * 4);
    res3 = ahbh & mask_low;
    temp = res1 + res2 + res3 + carry;
    *output_high = temp & mask_low;                   // C10
    carry = temp & mask_high;
    *output_high ^= (ahbh & mask_high) + carry;       // C11
}

multiprecision_addition()

void multiprecision_addition	(	uint64_t *	output,
		const uint64_t *	input_a,
		const uint64_t *	input_b,
		uint64_t	input_length
	)

Definition at line 98 of file utilities.c.

                                                                                                                        {
    uint64_t i, carry = 0;
    for (i = 0; i < input_length; i++) {addition_with_carry_u64(output[i], carry, carry, input_a[i], input_b[i]); }
}

References addition_with_carry_u64, and i.

multiprecision_is_smaller()

uint8_t multiprecision_is_smaller	(	const uint64_t *	input1,
		const uint64_t *	input2,
		uint64_t	input_length
	)

Definition at line 111 of file utilities.c.

                                                                                                           {
    uint8_t ret = 0;
    uint8_t is_equal[input_length], is_smaller[input_length];
    uint64_t i, j;
    for(i = 0; i < input_length; i++) {
        uint8_t *ta = (uint8_t *) &input_a[i];
        uint8_t *tb = (uint8_t *) &input_b[i];
        is_equal[i] = constant_time_compare(ta, tb, 8);
        is_smaller[i] = constant_time_is_lessthan_u64(input_a[i], input_b[i]);
    }
 
    for(i = input_length - 1; (int)i >= 0; i--) {
        uint8_t t = 1;
        for(j = input_length - 1; j > i; j--) {
            t &= is_equal[j];
        }
        ret |= (is_smaller[i] & t);
    }
 
    return ret;
}

References constant_time_compare(), constant_time_is_lessthan_u64(), i, and j.

Referenced by fp_is_smaller(), and fp_sample().

Here is the call graph for this function:

Here is the caller graph for this function:

multiprecision_shift_to_left()

void multiprecision_shift_to_left	(	uint64_t *	input_a_output_shifted_a,
		uint64_t	input_words_length
	)

Definition at line 89 of file utilities.c.

                                                                                                   {
    uint64_t i;
    for (i = input_words_length - 1; i > 0; i--) {
        constant_time_shift_to_left_u64(input_a_output_shifted_a[i], input_a_output_shifted_a[i],
                                        input_a_output_shifted_a[i - 1], 1, 64);
    }
    input_a_output_shifted_a[0] <<= 1;
}

References constant_time_shift_to_left_u64, and i.

multiprecision_shift_to_right()

void multiprecision_shift_to_right	(	uint64_t *	input_a_output_shifted_a,
		uint64_t	input_words_length
	)

Definition at line 80 of file utilities.c.

                                                                                                    {
    uint64_t i;
    for (i = 0; i < input_words_length - 1; i++) {
        constant_time_shift_to_right_u64(input_a_output_shifted_a[i], input_a_output_shifted_a[i + 1],
                                         input_a_output_shifted_a[i], 1, 64);
    }
    input_a_output_shifted_a[input_words_length - 1] >>= 1;
}

References constant_time_shift_to_right_u64, and i.

Referenced by fp_half().

Here is the caller graph for this function:

multiprecision_subtraction()

void multiprecision_subtraction	(	uint64_t *	output,
		const uint64_t *	input_a,
		const uint64_t *	input_b,
		uint64_t	input_length
	)

Definition at line 103 of file utilities.c.

                                                                                                                           {
    uint64_t i;
    uint8_t borrow = 0;
    for (i = 0; i < input_length; i++) {
        subtraction_with_borrow_u64(output[i], borrow, borrow, input_a[i], input_b[i]);
    }
}

References i, and subtraction_with_borrow_u64.