diff options
Diffstat (limited to 'lib/libmpa')
| -rw-r--r-- | lib/libmpa/arch/arm/mpa_a32.S | 428 | ||||
| -rw-r--r-- | lib/libmpa/arch/arm/sub.mk | 0 | ||||
| -rw-r--r-- | lib/libmpa/include/mpa.h | 238 | ||||
| -rw-r--r-- | lib/libmpa/include/mpalib.h | 432 | ||||
| -rw-r--r-- | lib/libmpa/include/mpalib_config.h | 125 | ||||
| -rw-r--r-- | lib/libmpa/mpa_addsub.c | 561 | ||||
| -rw-r--r-- | lib/libmpa/mpa_cmp.c | 171 | ||||
| -rw-r--r-- | lib/libmpa/mpa_conv.c | 92 | ||||
| -rw-r--r-- | lib/libmpa/mpa_div.c | 413 | ||||
| -rw-r--r-- | lib/libmpa/mpa_expmod.c | 85 | ||||
| -rw-r--r-- | lib/libmpa/mpa_gcd.c | 372 | ||||
| -rw-r--r-- | lib/libmpa/mpa_init.c | 69 | ||||
| -rw-r--r-- | lib/libmpa/mpa_io.c | 538 | ||||
| -rw-r--r-- | lib/libmpa/mpa_mem_static.c | 177 | ||||
| -rw-r--r-- | lib/libmpa/mpa_misc.c | 189 | ||||
| -rw-r--r-- | lib/libmpa/mpa_modulus.c | 144 | ||||
| -rw-r--r-- | lib/libmpa/mpa_montgomery.c | 266 | ||||
| -rw-r--r-- | lib/libmpa/mpa_mul.c | 228 | ||||
| -rw-r--r-- | lib/libmpa/mpa_primetable.h | 242 | ||||
| -rw-r--r-- | lib/libmpa/mpa_primetest.c | 291 | ||||
| -rw-r--r-- | lib/libmpa/mpa_random.c | 81 | ||||
| -rw-r--r-- | lib/libmpa/mpa_shift.c | 237 | ||||
| -rw-r--r-- | lib/libmpa/sub.mk | 45 |
23 files changed, 5424 insertions, 0 deletions
diff --git a/lib/libmpa/arch/arm/mpa_a32.S b/lib/libmpa/arch/arm/mpa_a32.S new file mode 100644 index 0000000..590de2b --- /dev/null +++ b/lib/libmpa/arch/arm/mpa_a32.S @@ -0,0 +1,428 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + .syntax unified + .thumb + .section .text + .align 2 + + .global __mpa_full_adder + .global __mpa_full_sub + .global __mpa_full_adder_ackum + .global __mpa_div_dword + .global __mpa_mul_add_word + .global __mpa_mul_add_word_cum + .global __mpa_montgomery_mul_add + .global __mpa_montgomery_sub_ack + +@ -------------------------------------------------------------------- +@ Function: __mpa_full_adder +@ +@ A word_t sized full adder. Incoming carry is in *carry. +@ The sum will be put in *sum and the +@ outgoing carry will be returned in *carry +@ +@ void __mpa_full_adder( mpa_word_t a, +@ mpa_word_t b, +@ mpa_word_t* sum, +@ mpa_word_t* carry) +@ + .thumb_func + .type __mpa_full_adder, %function +__mpa_full_adder: + push {r9} + ldr r9, [r3] @ r9 holds incoming carry + adds r1, r1, r0 @ r1 holds b + a + mov r12, #0 @ + adc r0, r12, #0 @ r0 holds carry of a + b + adds r1, r1, r9 @ r1 holds a + b + incoming carry + str r1, [r2] @ *sum <- r1 + adc r0, r0, #0 @ r0 holds acc carry + str r0, [r3] @ *carry <- r0 + pop {r9} + bx lr + +@ -------------------------------------------------------------------- +@ Function: __mpa_full_sub +@ +@ A word_t sized full subtraction function. Incoming carry is in *carry +@ The difference will be put in *diff and the outgoing carry will be returned +@ in *carry +@ +@ void __mpa_full_sub(mpa_word_t a, +@ mpa_word_t b, +@ mpa_word_t* diff, +@ mpa_word_t* carry); +@ + .thumb_func + .type __mpa_full_sub, %function +__mpa_full_sub: + push {r9} + ldr r9, [r3] @ r9 holds incomming carry + subs r1, r0, r1 @ r1 holds a - b + mov r12, #0 + sbc r0, r12, #0 @ r0 holds carry + subs r1, r1, r9 @ r1 holds a - b - carry + str r1, [r2] @ *diff <- r1 + sbc r0, r0, #0 @ r0 <- r0 - carry + rsbs r0, r0, #0 @ r0 <- 0 - r0 outgoing carry + str r0, [r3] @ *carry <- r0 + pop {r9} + bx lr + +@ -------------------------------------------------------------------- +@ Function: __mpa_full_adder_ackum +@ +@ A word_t sized full adder with ackumulate. *d = *d + e + *carry +@ Outgoing carry is in *carry +@ +@ void __mpa_full_adder_ackum( mpa_word_t* d, +@ mpa_word_t e, +@ mpa_word_t* carry) +@ + .thumb_func + .type __mpa_full_adder_ackum, %function +__mpa_full_adder_ackum: + push {r9} + ldr r12, [r0] @ r12 <- *d + mov r9, #0 @ + ldr r3, [r2] @ r3 holds incoming carry + adds r1, r1, r12 @ r1 <- e + *d + adc r9, r9, #0 @ r9 <- carry + adds r1, r1, r3 @ r1 <- r1 + *carry + str r1, [r0] @ *d <- sum + adc r0, r9, #0 @ r0 <- outgoing carry + str r0, [r2] @ *carry <- carry + pop {r9} + bx lr + + +@ -------------------------------------------------------------------- +@ Function: __mpa_div_dword +@ +@ Wrapper for the soft div. Calculates quotient and remainder of +@ ((x1 << WORD_SIZE) + x0 ) / y +@ +@ mpa_word_t __mpa_div_dword(mpa_word_t x0, +@ mpa_word_t x1, +@ mpa_word_t y, +@ mpa_word_t* rem) +@ +@ returns the quotient in r0 and the remainder in *rem +@ +@ At entrace +@ r0 low32 of num +@ r1 high32 of num +@ r2 y (becomes high32 of den) +@ r3 addr of rem + .thumb_func + .type __mpa_div_dword, %function +__mpa_div_dword: + push {r4, r5, r6, r7, r8, r9, lr}@ + + mov r12, #0 @ r12 holds low32 of den + @ r2 holds high32 of den + mov lr, #1 @ lr holds high32 of qbit + movs r4, #0 @ r4 holds low32 of qbit + cmp r2, #-1 @ if den >= 0 + bgt normalize @ branch to normalize + mov r9, #0 @ r9 holds low of quot + mov r8, #0 @ r8 holds high of quot + +soft_div_main: + cmp r12, r0 @ cmp low(den) low(num) + mov r6, #0 @ + it hi @ + movhi r6, #1 @ r6 is 1 if low(den) > low(num) + cmp r2, r1 @ cmp high(den) high(num) + mov r5, #0 @ + it hi @ + movhi r5, #1 @ r5 if 1 if high(den) > high(num) + it eq @ + moveq r5, r6 @ if high is equal let low decide + cbnz r5, shift_right @ if r5 == 1 branch + + adds r9, r9, r4 @ quot += qbit + adc r8, r8, lr @ + subs r0, r0, r12 @ num -= den + sbcs r1, r2 @ + +shift_right: +@ +@ These right shifts should be done as +@ +@ lsrs r2, r2, #1 @ right shift den >>= 1 +@ rrx r12, r12 +@ lsrs lr, lr, #1 @ right shift qbit >>= 1 +@ rrx r4, r4 +@ +@ but due to a compiler error in the STE toolchain (2012-05-03) +@ we must implement this as: + + and r7, r2, #1 + mov r2, r2, lsr #1 + mov r7, r7, lsl #31 + mov r12, r12, lsr #1 + orr r12, r12, r7 + + and r7, lr, #1 + mov lr, lr, lsr #1 + mov r7, r7, lsl #31 + mov r4, r4, lsr #1 + orr r4, r4, r7 + +@ +@ end of compiler bug fix +@ + orrs r5, r4, lr @ while qbit != 0 + bne soft_div_main @ do mainloop + +store_and_exit: + cmp r3, #0 @ if (r != NULL) + it ne @ + strne r0, [r3] @ store remainder into *r + mov r0, r9 @ + pop {r4, r5, r6, r7, r8, r9, pc}@ clean up and exit + +normalize: + adds r4, r4, r4 @ qbit <<= 1 + adc lr, lr, lr @ + adds r12, r12, r12 @ den <<= 1 + adcs r2, r2 @ + cmp r2, #-1 @ while den >= 0 + bgt normalize @ do normalize + + mov r9, #0 @ + orrs r6, r4, lr @ if qbit == 0 + beq store_and_exit @ done, branch to store r and exit + + mov r8, r9 @ set quot = 0 (r9 = 0 r8 = 0) + b soft_div_main @ and branch to main loop + + +@ -------------------------------------------------------------------- +@ Function: __mpa_mul_add_word +@ +@ Multiplies a and b and adds the incoming carry tp produce the product. +@ Outgoing carry is stored in *carry +@ +@ void __mpa_mul_add_word(mpa_word_t a, +@ mpa_word_t b, +@ mpa_word_t* p, +@ mpa_word_t* carry) +@ +@ + .thumb_func + .type __mpa_mul_add_word, %function +__mpa_mul_add_word: + push {r9} + umull r1, r9, r1, r0 @ r1, r9 <- a * b + ldr r0, [r3] @ r0 <- incoming carry + adds r1, r1, r0 @ add incoming carry to product + str r1, [r2] @ store low32 of product + adc r0, r9, #0 @ add carry to high32 + str r0, [r3] @ store outgoing carry + pop {r9} + bx lr + +@ -------------------------------------------------------------------- +@ Function: __mpa_mul_add_word_cum +@ +@ Multiplies a and b and adds the incoming carry and the cumulative +@ product. +@ Outgoing carry is stored in *carry +@ +@ void __mpa_mul_add_word_cum(mpa_word_t a, +@ mpa_word_t b, +@ mpa_word_t* p, +@ mpa_word_t* carry) +@ +@ + .thumb_func + .type __mpa_mul_add_word_cum, %function +__mpa_mul_add_word_cum: + push {r9} + umull r12, r9, r1, r0 @ r9, r12 <- a * b + ldr r0, [r2] @ r0 holds incoming product + ldr r1, [r3] @ r1 holds incoming carry + adds r0, r0, r12 @ r0 holds incoming product + new low32 + adc r9, r9, #0 @ add carry to high32 + adds r0, r0, r1 @ add incoming carry + str r0, [r2] @ store outgoing product + adc r0, r9, #0 @ store outgoing carry in r0 + str r0, [r3] @ and write to [r3] + pop {r9} + bx lr + + +@ -------------------------------------------------------------------- +@ Function: __mpa_montgomery_mul_add +@ +@ Calculates dest = dest + src * w +@ Dest must be big enough to hold the result +@ +@ void __mpa_montgomery_mul_add(mpanum dest, +@ mpanum src, +@ mpa_word_t w) +@ + .thumb_func + .type __mpa_montgomery_mul_add, %function +__mpa_montgomery_mul_add: + push {r4, r5, r6, r7, lr} + add r7, sp, #12 + push {r8, r9, r10, r11} + cbz r2, mm_mul_add_exit @ if w == 0 return + ldr r3, [r1, #4] @ r3 holds src->size + add r9, r0, #8 @ r9 holds &dest->d (dest_begin) + cmp r3, #1 @ + mov r3, r9 @ r3 holds &dest->d (ddig) + blt mm_mul_add_check_size @ if src->size == NULL jump + add r12, r1, #8 @ r12 holds &src->d + mov lr, #0 @ + movs r3, #0 @ + movs r4, #0 @ r4 holds carry + movs r5, #0 @ r5 holds inx + +mm_main_loop: + ldr r6, [r12, r5, lsl #2] @ r6 holds src->d[idx] + adds r3, #4 + ldr r11, [r9, r5, lsl #2] @ r11 holds dest->d[idx] + umull r10, r8, r6, r2 @ r8, r10 holds src->d[idx] * w + mla r8, r6, lr, r8 @ r8 <- r6*0 + r8 ?? + adds r6, r11, r4 @ r6 <- dest->d[idx] + carry + adc r4, lr, #0 @ r4 holds C + adds r6, r6, r10 @ r6 holds low32 of result + str r6, [r9, r5, lsl #2] @ store into dest->d[idx] + add r5, r5, #1 @ idx++ + ldr r6, [r1, #4] @ r6 holds src->size + adc r4, r4, r8 @ r4 holds high32 of result + cmp r5, r6 @ while (idx < src->size) + blt mm_main_loop @ do jump + + adds r1, r0, r3 @ + cmp r4, #0 @ check carry + add r3, r1, #8 @ r3 holds &dest->d[idx] + beq mm_mul_add_check_size @ jump if no carry + movs r1, #0 + +mm_carry_loop: + ldr r2, [r3] @ r2 holds dest->d[idx] + adds r2, r2, r4 @ r2 <- r2 + carry + str r2, [r3], #4 @ store at dest->d[idx++] + adcs r4, r1, #0 @ r4 holds new C + bne mm_carry_loop @ if r4 != 0 jump + +mm_mul_add_check_size: + sub r1, r3, r9 @ r1 holds ddig - dest_begin + ldr r2, [r0, #4] @ r2 holds dest->size + asrs r1, r1, #2 @ mult by 2 to go from byte addr to word + cmp r1, r2 @ + it gt @ + strgt r1, [r0, #4] @ store new size if idx > dest->size + +mm_mul_add_exit: + pop {r8, r9, r10, r11} + pop {r4, r5, r6, r7, pc} + + +@ -------------------------------------------------------------------- +@ Function: __mpa_montgomery_sub_ack +@ Calculates dest = dest - src +@ Assumption: dest >= src and both non-negative +@ and dest > src. +@ +@ +@ void __mpa_montgomery_sub_ack(mpanum dest, +@ mpanum src) +@ + .thumb_func + .type __mpa_montgomery_sub_ack, %function +__mpa_montgomery_sub_ack: + push {r4, r5, r7, r9, lr} + ldr r2, [r1, #4] + add r9, r0, #8 + mov lr, #0 + add r7, sp, #8 + cmp r2, #0 + bgt LBB1_10 + movs r2, #0 + b LBB1_6 +LBB1_2: + cbz r4, LBB1_6 + movs r1, #0 + LBB1_4: + add r5, r0, r2, lsl #2 + adds r3, #4 + adds r2, #1 + ldr r4, [r5, #8] + subs r4, r4, r12 + str r4, [r5, #8] + sbcs r5, r1, #0 + rsb r12, r5, #0 + bne LBB1_4 + add r9, r0, r3 +LBB1_6: + ldr r3, [r0, #4] + cmp r2, r3 + blt LBB1_12 + sub r1, r9, #4 + subs r2, r3, #1 +LBB1_8: + adds r3, r2, #1 + cmp r3, #1 + blt LBB1_12 + ldr r3, [r1] + cmp r3, #0 + it ne + popne {r4, r5, r7, r9, pc} + str r2, [r0, #4] + subs r2, #1 + subs r1, #4 + b LBB1_8 +LBB1_10: + movs r3, #8 + movs r2, #0 + mov r12, #0 +LBB1_11: + add r5, r1, r2, lsl #2 + ldr r4, [r9] + adds r3, #4 + adds r2, #1 + ldr r5, [r5, #8] + subs r5, r4, r5 + sbc r4, lr, #0 + subs r5, r5, r12 + str r5, [r9], #4 + sbc r4, r4, #0 + ldr r5, [r1, #4] + rsb r12, r4, #0 + cmp r2, r5 + blt LBB1_11 + b LBB1_2 +LBB1_12: + pop {r4, r5, r7, r9, pc} + + diff --git a/lib/libmpa/arch/arm/sub.mk b/lib/libmpa/arch/arm/sub.mk new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/lib/libmpa/arch/arm/sub.mk diff --git a/lib/libmpa/include/mpa.h b/lib/libmpa/include/mpa.h new file mode 100644 index 0000000..c5aa5de --- /dev/null +++ b/lib/libmpa/include/mpa.h @@ -0,0 +1,238 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef GUARD_MPA_H +#define GUARD_MPA_H + +#include "mpalib.h" + +/************************************************************************\ + * MACRO DEFINITIONS +\************************************************************************/ + +#define WORD_SIZE MPA_WORD_SIZE +#define BYTES_PER_WORD (MPA_WORD_SIZE >> 3) +#define NIBBLES_PER_WORD (MPA_WORD_SIZE >> 2) +#define LOG_OF_WORD_SIZE MPA_LOG_OF_WORD_SIZE +#define LOG_OF_BYTES_PER_WORD MPA_LOG_OF_BYTES_PER_WORD +#define WORD_ALL_BITS_ONE ((mpa_word_t)-1) + +/* number of bytes to hold x bits, x must be positive integer */ +#define BITS_TO_BYTES(x) (((x)+7) >> 3) +/* convert from bytes to bits */ +#define BYTES_TO_BITS(x) ((x) << 3) + +/* convert from words to bytes */ +#define WORDS_TO_BYTES(x) ((x) << LOG_OF_BYTES_PER_WORD) +/* convert from bytes to minimum number of words needed to hold x bytes */ +#define BYTES_TO_WORDS(x) (((x) + BYTES_PER_WORD - 1) >> LOG_OF_BYTES_PER_WORD) + +/* convert from bits to words and vice versa */ +#define WORDS_TO_BITS(x) ((x) * MPA_WORD_SIZE) +#define BITS_TO_WORDS(x) (((x) + MPA_WORD_SIZE - 1) / MPA_WORD_SIZE) + +#define __MAX(a, b) ((a) < (b) ? (b) : (a)) +#define __MIN(a, b) ((a) < (b) ? (a) : (b)) + +/* macros to access internal variables in a mpa_numbase */ + +#define MPA_NEG_SIGN -1 +#define MPA_POS_SIGN 1 + +#define __mpanum_alloced(x) ((x)->alloc) +#define __mpanum_size(x) ((mpa_usize_t)((x)->size >= 0 ? \ + (x)->size : -(x)->size)) +#define __mpanum_sign(x) ((x)->size >= 0 ? MPA_POS_SIGN : MPA_NEG_SIGN) + +/* macros to set internal variables in mpa_numbase */ + +/* SetSign take either MPA_POS_SIGN or MPA_NEG_SIGN as argument */ +#define __mpanum_set_sign(x, s) \ + do { \ + if (__mpanum_sign(x) != (s)) \ + (x)->size = -(x)->size; \ + } while (0) +#define __mpanum_is_zero(x) ((x)->size == 0) +#define __mpanum_neg(x) ((x)->size = -((x)->size)) + +/* Get most significant word of x, call only on non-zero x */ +#define __mpanum_msw(x) ((x)->d[__mpanum_size(x)-1]) +#define __mpanum_lsw(x) ((x)->d[0]) + +/* Get word idx of x, if idx >= size, return 0 + * This macro is used in the montgomery multiplication to allow + * operands to have shorter alloc than n + */ +#define __mpanum_get_word(idx, x) ((idx >= __mpanum_size(x)) ? \ + 0 : ((x)->d[idx])) + +/* n = 0..NIBBLES_PER_WORD-1 */ +#if defined(MPA_LITTLE_ENDIAN) +#define NIBBLE_OF_WORD(n, w) (((w) >> ((n) << 2)) & 0xf) +#elif defined(MPA_BIG_ENDIAN) +#define NIBBLE_OF_WORD(n, w) (((w) >> ((7-(n)) << 2)) & 0xf) +#else +#error "You must define either MPA_LITTLE_ENDIAN or MPA_BIG_ENDIAN, see mpalib_config.h" +#endif + +/* In order to avoid warnings on unused arguments */ +#ifndef IDENTIFIER_NOT_USED +#define IDENTIFIER_NOT_USED(x) (void)(&x) +#endif + +/* + * Is NULL defined? + */ +#if !defined(NULL) +#define NULL (void *)0 +#endif + +/************************************************************* + * + * GLOBAL CONSTANTS AND VARIABLES + * + *************************************************************/ + +/* + * defined in mpa_misc.c + */ +extern const mpa_num_base const_largest_deci_base; +extern const mpa_num_base Const_1_LShift_Base; +extern const mpa_num_base const_one; + +/************************************************************* + * + * INTERNAL FUNCTIONS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * From mpa_mem_static. + * + */ + +/*------------------------------------------------------------ + * + * From mpa_addsub.c + * + */ +void __mpa_full_adder(mpa_word_t a, + mpa_word_t b, mpa_word_t *sum, mpa_word_t *carry); + +void __mpa_full_sub(mpa_word_t a, + mpa_word_t b, mpa_word_t *diff, mpa_word_t *carry); + +void __mpa_full_adder_ackum(mpa_word_t *d, mpa_word_t e, mpa_word_t *carry); + +void __mpa_abs_add(mpa_word_t *sum, + mpa_usize_t *sum_size, + const mpa_word_t *op1, + mpa_usize_t op1_size, + const mpa_word_t *op2, mpa_usize_t op2_size); + +void __mpa_abs_add_ackum(mpanum dest, const mpanum src); + +void __mpa_abs_sub(mpa_word_t *diff, + mpa_usize_t *diff_size, + const mpa_word_t *op1, + mpa_usize_t op1_size, + const mpa_word_t *op2, mpa_usize_t op2_size); + +/*------------------------------------------------------------ + * + * From mpa_cmp.c + * + */ + +int __mpa_abs_cmp(const mpanum op1, const mpanum op2); + +int __mpa_abs_greater_than(const mpanum op1, const mpanum op2); + +int __mpa_abs_less_than(const mpanum op1, const mpanum op2); + +/*------------------------------------------------------------ + * + * From mpa_mul.c + * + */ +void __mpa_mul_add_word(mpa_word_t a, + mpa_word_t b, mpa_word_t *p, mpa_word_t *carry); + +void __mpa_mul_add_word_cum(mpa_word_t a, + mpa_word_t b, mpa_word_t *p, mpa_word_t *carry); + +void __mpa_abs_mul_word(mpanum dest, const mpanum op1, mpa_word_t op2); + +void __mpa_abs_mul(mpanum dest, const mpanum op1, const mpanum op2); + +/*------------------------------------------------------------ + * + * From mpa_div.c + * + */ + +mpa_word_t __mpa_div_dword(mpa_word_t n0, + mpa_word_t n1, mpa_word_t d, mpa_word_t *r); + +void __mpa_div_q_r_internal_word(mpanum q, + mpanum r, + const mpanum op1, const mpa_word_t op2); + +void __mpa_div_q_r(mpanum q, + mpanum r, + const mpanum op1, const mpanum op2, mpa_scratch_mem pool); + +/*------------------------------------------------------------ + * + * From mpa_shift.c + * + */ + +void __mpa_shift_words_left(mpanum op, mpa_word_t q); +void __mpa_shift_words_right(mpanum op, mpa_word_t q); + +/*------------------------------------------------------------ + * + * From mpa_montgomery.c + * + */ + +void __mpa_montgomery_sub_ack(mpanum dest, mpanum src); + +void __mpa_montgomery_mul_add(mpanum dest, mpanum src, mpa_word_t w); + +void __mpa_montgomery_mul(mpanum dest, + mpanum op1, mpanum op2, mpanum n, mpa_word_t n_inv); + +/*------------------------------------------------------------ + * + * From mpa_misc.c + * + */ +void __mpa_set_unused_digits_to_zero(mpanum n); + +#endif /* include guard */ diff --git a/lib/libmpa/include/mpalib.h b/lib/libmpa/include/mpalib.h new file mode 100644 index 0000000..a467e39 --- /dev/null +++ b/lib/libmpa/include/mpalib.h @@ -0,0 +1,432 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef GUARD_MPALIB_H +#define GUARD_MPALIB_H + +/************************************************************* + * + * How functions are exported. + * + *************************************************************/ +#define MPALIB_EXPORT + +/************************************************************* + * + * Include common configuration definitions + * + *************************************************************/ +#include "mpalib_config.h" + +/************************************************************* + * + * TYPE DEFINITIONS + * + *************************************************************/ + +#if defined(MPA_SUPPORT_DWORD_T) +typedef unsigned long long mpa_dword_t; +#endif + +/*! \struct mpa_numbase_struct + * The internal representation of a multi precision integer. + * + * \param alloc The size of the allocated array d in number of mpa_word_t. + * + * \param size The number of used words in *d to represent the number, or + * minus the number if the mpa_numbase is representing a + * negative number. The mpa_numbase + * is representing zero if and only if size == 0. + * + * \param d The digits of the integer. The digits are in radix + * 2^WORD_SIZE. + * The digits are stored in a little endian format, i.e. + * the least significant word_t is stored in d[0]. + * + * \internal ** NOTE ** + * If you change this struct, you must update the const variables + * in mpa_misc.c and mpa_primetest.c + * And the + * MPA_NUMBASE_METADATA_SIZE_IN_U32 + * below. + */ +typedef struct mpa_numbase_struct { + mpa_asize_t alloc; + mpa_usize_t size; + mpa_word_t d[]; +} mpa_num_base; + +/*/ mpanum is the type we use as parameters to function calls in this library */ +typedef mpa_num_base *mpanum; + +/*! + * The Context struct for a Montgomery multiplication + * + * \internal ** NOTE ** + * If you change this struct, you must update the + * MPA_FMM_CONTEXT_METADATA_SIZE_IN_U32 + * below. + * + */ +typedef struct mpa_fmm_context_struct { + mpanum r_ptr; + mpanum r2_ptr; + mpa_word_t n_inv; + uint32_t m[]; +} mpa_fmm_context_base; + +typedef mpa_fmm_context_base *mpa_fmm_context; + +struct mpa_scratch_mem_sync; +typedef void (mpa_scratch_mem_sync_fn)(struct mpa_scratch_mem_sync *sync); + +typedef struct mpa_scratch_mem_struct { + uint32_t size; /* size of the memory pool, in bytes */ + uint32_t bn_bits; /* default size of a temporary variables */ + uint32_t last_offset; /* offset to the last one */ + mpa_scratch_mem_sync_fn *get; + mpa_scratch_mem_sync_fn *put; + struct mpa_scratch_mem_sync *sync; + uint32_t m[]; /* mpa_scratch_item are stored there */ +} mpa_scratch_mem_base; +typedef mpa_scratch_mem_base *mpa_scratch_mem; + +struct mpa_scratch_item { + uint32_t size; /* total size of this item */ + /* the offset of the previous and next mpa_scratch_item */ + uint32_t prev_item_offset; + uint32_t next_item_offset; + /* followed by a mpa_num_base, being the big number to save */ +}; + +/************************************************************* + * + * EXPORTED VARIABLES + * + *************************************************************/ + +/************************************************************* + * + * MACROS + * + *************************************************************/ + +#define MPA_STRING_MODE_HEX_UC 16 +#define MPA_STRING_MODE_HEX_LC 17 + +#define MPA_EVEN_PARITY 0 +#define MPA_ODD_PARITY 1 + +/*! Returns true if the mpanum 'a' is even (zero included) */ +#define mpa_is_even(a) (mpa_parity((a)) == MPA_EVEN_PARITY) +/*! Returns true if the mpanum 'a' is odd */ +#define mpa_is_odd(a) (mpa_parity((a)) == MPA_ODD_PARITY) +/* Short hand for setting the value of 'a' to the value of 'b' */ +#define mpa_set(a, b) mpa_copy((a), (b)) + +/* */ +/* Define how to convert between sizes given in uint32_t and mpa_word_t */ +/* */ +#define ASIZE_TO_U32(x) (((sizeof(mpa_word_t) * (x)) + 3) / 4) +#define U32_TO_ASIZE(x) \ + ((mpa_asize_t)(((4 * (x)) + (sizeof(mpa_word_t) - 1)) / \ + sizeof(mpa_word_t))) + +/************************************************************* + * + * STATIC MEMORY MODE DEFINES + * + *************************************************************/ + +/* + * The number of extra uint32_t in the internal representation. + * This is used in the static memory mode. + * It is chosen to be complient with the requirments of GlobalPlatform. + */ +#define MPA_NUMBASE_METADATA_SIZE_IN_U32 2 + +#define MPA_SCRATCHMEM_METADATA_SIZE_IN_U32 (sizeof(mpa_scratch_mem_base)/ 4) + +/* + * The size (in uint32_t) of the constituent variables + * of mpa_fmm_context apart from m[] + */ + +#define MPA_FMM_CONTEXT_METADATA_SIZE_IN_U32 (sizeof(mpa_fmm_context_base)/4) + +/* + * This macro returns the size of the complete mpa_num_base struct that + * can hold n-bits integers. This is used in the static memory mode. + */ +#define mpa_StaticVarSizeInU32(n) \ + ((((n)+31)/32) + MPA_NUMBASE_METADATA_SIZE_IN_U32) + +/* + * + */ +#define mpa_StaticTempVarSizeInU32(max_bits) \ + (2 * mpa_StaticVarSizeInU32((max_bits)) - \ + MPA_NUMBASE_METADATA_SIZE_IN_U32) + +/* + * + */ +#define mpa_scratch_mem_size_in_U32(nr_temp_vars, max_bits) \ + (((nr_temp_vars) * (mpa_StaticTempVarSizeInU32((max_bits)) + \ + sizeof(struct mpa_scratch_item))) + \ + sizeof(struct mpa_scratch_mem_struct)) + +/* + * + */ +#define mpa_fmm_context_size_in_U32(n) \ + (2 * (mpa_StaticVarSizeInU32((n)) + 2) + \ + MPA_FMM_CONTEXT_METADATA_SIZE_IN_U32) + +/************************************************************* + * + * FUNCTION PROTOTYPES + * + * All externally available functions from this lib. + * + *************************************************************/ + +/* + * From mpa_init.c + */ + +/* + * mpa_init_scratch_mem + * Initiate a chunk of memory to be used as a scratch pool. + * The size of the pool (in uint32_t) must corresponde to the + * size returned by the macro mpa_ScratchMemSizeInU32 + * with the same parameters 'nr_vars' and 'max_bits' + * + * \param pool The pool to initialize + * \param size the size, in bytes, of the pool + * \prama bn_bits default size, in bits, of a big number + * \param get increase reference counter to pool + * \param put decrease reference counter to pool + * \param sync argument to supply to get() and put() + */ +MPALIB_EXPORT void mpa_init_scratch_mem_sync(mpa_scratch_mem pool, size_t size, + uint32_t bn_bits, mpa_scratch_mem_sync_fn get, + mpa_scratch_mem_sync_fn put, + struct mpa_scratch_mem_sync *sync); + +MPALIB_EXPORT void mpa_init_scratch_mem(mpa_scratch_mem pool, size_t size, + uint32_t bn_bits); + + +/* + * mpa_init_static + * Initiate a mpanum to hold an integer of a certain size. + * The parameter 'len' is the return value of the macro + * mpa_StaticVarSizeInU32 called with the max bit size as parameter. + * + * \param src The mpanum to be initialized + * \param len The allocated size in uint32_t of src + */ +MPALIB_EXPORT void mpa_init_static(mpanum src, uint32_t len); + +MPALIB_EXPORT void mpa_init_static_fmm_context(mpa_fmm_context_base *context, + uint32_t len); + +/* + * From mpa_addsub.c + */ +MPALIB_EXPORT void mpa_add(mpanum dest, const mpanum op1, const mpanum op2, + mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_sub(mpanum dest, const mpanum op1, const mpanum op2, + mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_add_word(mpanum dest, const mpanum op1, mpa_word_t op2, + mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_sub_word(mpanum dest, const mpanum op1, mpa_word_t op2, + mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_neg(mpanum dest, const mpanum src); + +/* + * From mpa_mul.c + */ + +MPALIB_EXPORT void mpa_mul(mpanum dest, const mpanum op1, const mpanum op2, + mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_mul_word(mpanum dest, const mpanum op1, mpa_word_t op2, + mpa_scratch_mem pool); + +/* + * From mpa_div.c + */ + +MPALIB_EXPORT void mpa_div(mpanum q, mpanum r, + const mpanum op1, const mpanum op2, + mpa_scratch_mem pool); + +/* + * From mpa_modulus.c + */ + +MPALIB_EXPORT void mpa_mod(mpanum dest, const mpanum op, const mpanum n, + mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_add_mod(mpanum dest, const mpanum op1, const mpanum op2, + const mpanum n, mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_sub_mod(mpanum dest, const mpanum op1, const mpanum op2, + const mpanum n, mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_mul_mod(mpanum dest, const mpanum op1, const mpanum op2, + const mpanum n, mpa_scratch_mem pool); + +MPALIB_EXPORT int mpa_inv_mod(mpanum dest, const mpanum op, const mpanum n, + mpa_scratch_mem pool); + +/* + * From mpa_cmp.c + */ + +MPALIB_EXPORT int32_t mpa_cmp(const mpanum op1, const mpanum op2); + +MPALIB_EXPORT int32_t mpa_cmp_short(const mpanum op1, int32_t op2); + +/* + * From mpa_conv.c + */ + +MPALIB_EXPORT void mpa_set_S32(mpanum dest, int32_t short_val); + +MPALIB_EXPORT int32_t mpa_get_S32(int32_t *dest, mpanum src); + +MPALIB_EXPORT void mpa_set_word(mpanum dest, mpa_word_t src); + +MPALIB_EXPORT mpa_word_t mpa_get_word(mpanum src); + +/* + * From mpa_shift.c + */ + +MPALIB_EXPORT void mpa_shift_left(mpanum dest, const mpanum src, + mpa_word_t steps); + +MPALIB_EXPORT void mpa_shift_right(mpanum dest, const mpanum src, + mpa_word_t steps); + +/* + * From mpa_gcd.c + */ +MPALIB_EXPORT void mpa_gcd(mpanum dest, const mpanum src1, const mpanum src2, + mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_extended_gcd(mpanum gcd, mpanum dest1, mpanum dest2, + const mpanum src1, const mpanum src2, + mpa_scratch_mem pool); + +/* + * From mpa_io.c + */ +MPALIB_EXPORT int mpa_get_str_size(void); + +MPALIB_EXPORT int mpa_set_str(mpanum dest, const char *digitstr); + +MPALIB_EXPORT char *mpa_get_str(char *str, int mode, const mpanum n); + +MPALIB_EXPORT int mpa_set_oct_str(mpanum dest, const uint8_t *buffer, + size_t buffer_len, bool negative); + +MPALIB_EXPORT int mpa_get_oct_str(uint8_t *buffer, size_t *buffer_len, + const mpanum n); + +/* + * From mpa_expmod.c + */ +MPALIB_EXPORT void mpa_exp_mod(mpanum dest, const mpanum op1, const mpanum op2, + const mpanum n, const mpanum r_modn, + const mpanum r2_modn, const mpa_word_t n_inv, + mpa_scratch_mem pool); + +/* + * From mpa_misc.c + */ + +MPALIB_EXPORT void mpa_wipe(mpanum src); + +MPALIB_EXPORT void mpa_copy(mpanum dest, const mpanum src); + +MPALIB_EXPORT void mpa_abs(mpanum dest, const mpanum src); + +MPALIB_EXPORT int mpa_highest_bit_index(const mpanum src); + +MPALIB_EXPORT uint32_t mpa_get_bit(const mpanum src, uint32_t idx); + +MPALIB_EXPORT int mpa_can_hold(mpanum dest, const mpanum src); + +MPALIB_EXPORT int mpa_parity(const mpanum src); + +MPALIB_EXPORT mpanum mpa_constant_one(void); + +/* + * From mpa_Random.c + */ + +typedef uint32_t (*random_generator_cb)(void *buf, size_t blen); + +MPALIB_EXPORT void mpa_set_random_generator(random_generator_cb callback); + +MPALIB_EXPORT void mpa_get_random(mpanum dest, mpanum limit); + +/* + * From mpa_montgomery.c + */ +MPALIB_EXPORT int mpa_compute_fmm_context(const mpanum modulus, mpanum r_modn, + mpanum r2_modn, mpa_word_t *n_inv, + mpa_scratch_mem pool); + +MPALIB_EXPORT void mpa_montgomery_mul(mpanum dest, mpanum op1, mpanum op2, + mpanum n, mpa_word_t n_inv, + mpa_scratch_mem pool); + +/* + * From mpa_mem_static.c + */ +MPALIB_EXPORT mpanum mpa_alloc_static_temp_var(mpanum *var, + mpa_scratch_mem pool); +MPALIB_EXPORT mpanum mpa_alloc_static_temp_var_size(int size_bits, + mpanum *var, + mpa_scratch_mem pool); +MPALIB_EXPORT void mpa_free_static_temp_var(mpanum *var, mpa_scratch_mem pool); + +/* + * From mpa_primetest.c + */ +MPALIB_EXPORT int mpa_is_prob_prime(mpanum n, int conf_level, + mpa_scratch_mem pool); + +#endif /* include guard */ diff --git a/lib/libmpa/include/mpalib_config.h b/lib/libmpa/include/mpalib_config.h new file mode 100644 index 0000000..08ab5e0 --- /dev/null +++ b/lib/libmpa/include/mpalib_config.h @@ -0,0 +1,125 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef GUARD_MPA_CONFIG_H +#define GUARD_MPA_CONFIG_H + +#include <limits.h> +#include <stdint.h> +#include <stdbool.h> + +/************************************************************************\ + * Common definitions + * You should go through these carefully and adjust to your environment + \************************************************************************/ + +/* + * Definitions of different sized integers and unsigned + * + * mpa_word_t: should be an unsigned int of size equal to the most + * efficient add/sub/mul/div word size of the machine. + * + * mpa_int_t should be a signed int of the same size as the mpa_word_t + * + * mpa_halfw_t: half size of mpa_word_t + * + * mpa_asize_t: an unsigned int of suitable size to hold the number of + * allocated bytes for the representation. We cannot use size_t + * since that is 64 bit long on 64 bit machines, and that is + * ridiciously large. + * + * mpa_usize_t: a signed int suitable to hold the number of used mpa_word_t to + * represent the integer. + * + * mpa_byte_t: the native unsigned byte type. + */ +typedef uint32_t mpa_word_t; +typedef int32_t mpa_int_t; +typedef uint16_t mpa_halfw_t; +typedef uint32_t mpa_asize_t; +typedef int32_t mpa_usize_t; +typedef uint8_t mpa_byte_t; + +/* Number of bits in mpa_word_t */ +#define MPA_WORD_SIZE 32 + +/* Largest representable number in a mpa_int_t */ +#define MPA_INT_MAX INT32_MAX + +/* Smallest representable number in a mpa_int_t */ +#define MPA_INT_MIN INT32_MIN + +/* The Log2(MPA_WORD_SIZE) */ +#define MPA_LOG_OF_WORD_SIZE 5 + +/* The Log2 of number of bytes in a mpa_word_t */ +#define MPA_LOG_OF_BYTES_PER_WORD 2 + +/* The largest power of 10 representable in a mpa_word_t */ +#define LARGEST_DECIMAL_BASE_IN_WORD 1000000000 + +/* the number of decimal digits minus 1 in LARGEST_DECIMAL_BASE_IN_WORD */ +#define LARGEST_DECIMAL_BASE_DIGITS 9 + +/* The largest string size to represent a big number as a string */ +#define MPA_STR_MAX_SIZE (4096 + 2) + +/* define MPA_BIG_ENDIAN or MPA_LITTLE_ENDIAN */ +#define MPA_LITTLE_ENDIAN +/*#define MPA_BIG_ENDIAN */ + +/* + * comment out the line below if your system does not support "unsigned + * long long" + */ +#define MPA_SUPPORT_DWORD_T + +/* + * define if you want to use ARM assembler code for certain cruicial + * functions + */ +/* #define USE_ARM_ASM */ + +/* + * Include functionality for converting to and from strings; mpa_set_string + * and mpa_get_string. + */ +#define MPA_INCLUDE_STRING_CONVERSION + +/* + * Quick fix to be able to better define these mem functions later + */ +#define MACRO_DEF_MPA_MEMFUNCS + +#ifdef MACRO_DEF_MPA_MEMFUNCS +#include <stdlib.h> +#include <string.h> +#define mpa_memset memset +#define mpa_memcpy memcpy +#define mpa_memmove memmove +#endif + +#endif /* include guard */ diff --git a/lib/libmpa/mpa_addsub.c b/lib/libmpa/mpa_addsub.c new file mode 100644 index 0000000..ede3ab7 --- /dev/null +++ b/lib/libmpa/mpa_addsub.c @@ -0,0 +1,561 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * HELPERS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * These functions have ARM assembler implementations + * + */ +#if !defined(USE_ARM_ASM) + +/* -------------------------------------------------------------------- + * Function: __mpa_full_adder + * + * A word_t sized full adder. Incoming carry is in *carry. + * The sum will be put in *sum and the + * outgoing carry will be returned in *carry + */ +void __mpa_full_adder(mpa_word_t a, + mpa_word_t b, mpa_word_t *sum, mpa_word_t *carry) +{ +#if defined(MPA_SUPPORT_DWORD_T) + mpa_dword_t _s; + _s = (mpa_dword_t) (a) + (mpa_dword_t) (b) + (mpa_dword_t) (*carry); + *sum = (mpa_word_t) (_s); + *carry = ((mpa_word_t) (_s >> MPA_WORD_SIZE)); +#else + *sum = a + *carry; + *carry = (*sum < a); + *sum += b; + *carry += (*sum < b); +#endif +} + +/* -------------------------------------------------------------------- + * Function: __mpa_full_sub + * + * A word_t sized full subtraction function. Incoming carry is in *carry. + * The difference will be put in *diff and the outgoing carry will be returned + * in *carry. + */ +void __mpa_full_sub(mpa_word_t a, + mpa_word_t b, mpa_word_t *diff, mpa_word_t *carry) +{ +#if defined(MPA_SUPPORT_DWORD_T) + mpa_dword_t _d; + _d = (mpa_dword_t) (a) - (mpa_dword_t) (b) - (mpa_dword_t) (*carry); + *diff = (mpa_word_t) (_d); + *carry = 0 - (mpa_word_t) (_d >> WORD_SIZE); +#else + mpa_word_t _d; + *diff = a - *carry; + *carry = (*diff > a); + _d = *diff - b; + *carry += (_d > *diff); + *diff = _d; +#endif +} + +/*------------------------------------------------------------ + * + * __mpa_full_adder_ackum + * + * A word_t sized full adder with ackumulate. *d = *d + e + *carry + * Outgoing carry is in *carry + */ +void __mpa_full_adder_ackum(mpa_word_t *d, mpa_word_t e, mpa_word_t *carry) +{ +#if defined(MPA_SUPPORT_DWORD_T) + mpa_dword_t _s; + _s = (mpa_dword_t) (*d) + (mpa_dword_t) (e) + (mpa_dword_t) (*carry); + *d = (mpa_word_t) (_s); + *carry = ((mpa_word_t) (_s >> MPA_WORD_SIZE)); +#else + mpa_word_t _s; + _s = *d + *carry; + *carry = (_s < *d); + *d = _s + e; + *carry += (*d < _s); +#endif +} + +#endif /* of USR_ARM_ASM */ + +/* -------------------------------------------------------------------- + * Function: __mpa_abs_add + * + * Calculate |op1| + |op2|. + * op1 and op2 are pointers to word_t arrays holding the value. + * *Sum must be big enough to hold the result. + */ +void __mpa_abs_add(mpa_word_t *sum, + mpa_usize_t *sum_size, + const mpa_word_t *op1, + mpa_usize_t op1_size, + const mpa_word_t *op2, mpa_usize_t op2_size) +{ + const mpa_word_t *smaller; + const mpa_word_t *larger; + mpa_word_t *sum_begin; + mpa_usize_t smaller_wsize; /* size in words of the smallest */ + mpa_usize_t larger_wsize; /* size in words of the largest */ + mpa_word_t carry; + mpa_usize_t i; + + /* make sure we know which is the larger one */ + if (op1_size > op2_size) { + larger = op1; + smaller = op2; + larger_wsize = op1_size; + smaller_wsize = op2_size; + } else { /* op2 is the larger or same size */ + larger = op2; + smaller = op1; + larger_wsize = op2_size; + smaller_wsize = op1_size; + } + + sum_begin = sum; + carry = 0; + i = 0; + while (i < smaller_wsize) { + __mpa_full_adder(*(smaller++), *(larger++), sum++, &carry); + i++; + } + while (carry && (i < larger_wsize)) { + __mpa_full_adder(0, *(larger++), sum++, &carry); + i++; + } + + if (i < larger_wsize) { + /* carry did not propagate all the way, copy the rest */ + mpa_memcpy(sum, larger, WORDS_TO_BYTES(larger_wsize - i)); + sum += larger_wsize - i; + } + + if (carry != 0) + *(sum++) = carry; + *sum_size = (mpa_word_t) (sum - sum_begin); +} + +/* -------------------------------------------------------------------- + * Function: __mpa_abs_add_ackum + * + * Calculate dest = dest + src. Both dest and src must be positive + * dest must be big enough to hold the result. + */ +void __mpa_abs_add_ackum(mpanum dest, const mpanum src) +{ + const mpa_word_t *sdig; /* source digits */ + mpa_word_t *ddig; /* dest digits */ + mpa_word_t *dest_begin; + + mpa_word_t carry; + mpa_usize_t i; + + i = src->size - dest->size; + if (i <= 0) + i = 0; + mpa_memset(dest->d + dest->size, 0, (1 + i) * BYTES_PER_WORD); + + dest_begin = dest->d; + sdig = src->d; + ddig = dest->d; + i = 0; + carry = 0; + while (i < src->size) { + __mpa_full_adder_ackum(ddig++, *(sdig++), &carry); + /* + * _s = (mpa_dword_t)*(ddig) + (mpa_dword_t)*(sdig++) + + * (mpa_dword_t)carry; + * *(ddig++) = (mpa_word_t)(_s); + * carry = (mpa_word_t)(_s >> WORD_SIZE); + */ + i++; + } + while (carry) { + __mpa_full_adder_ackum(ddig++, 0, &carry); + /* + * _s = (mpa_dword_t)*(ddig) + (mpa_dword_t)carry; + * *(ddig++) = (mpa_word_t)(_s); + * carry = (mpa_word_t)(_s >> WORD_SIZE); + */ + } + i = (mpa_word_t) (ddig - dest_begin); + if (i > dest->size) + dest->size = i; +} + +/* -------------------------------------------------------------------- + * Function: __mpa_abs_sub + * + * Calculate |op1| - |op2|, where |op1| >= |op2| must hold. + * op1 and op2 are pointers to word_t arrays holding the value. + * *Diff must be big enough to hold the result. diff_size is + * updated with the number of significant words in *diff. + */ +void __mpa_abs_sub(mpa_word_t *diff, + mpa_usize_t *diff_size, + const mpa_word_t *op1, + mpa_usize_t op1_size, + const mpa_word_t *op2, mpa_usize_t op2_size) +{ + mpa_word_t carry; + mpa_usize_t i; + + carry = 0; + i = 0; + while (i < op2_size) { + __mpa_full_sub(*(op1++), *(op2++), diff++, &carry); + i++; + } + /* + * Here we have no more digits in op2, we only need to keep on + * subtracting 0 from op1, and deal with carry. + */ + while (carry && (i < op1_size)) { + __mpa_full_sub(*(op1++), 0, diff++, &carry); + i++; + } + + if (i < op1_size) { + /* + * Carry did not propagate all the way, now we only need to + * copy the rest. + */ + mpa_memcpy(diff, op1, WORDS_TO_BYTES(op1_size - i)); + diff += op1_size - i; + } + /* check size of diff */ + i = op1_size; + while ((i > 0) && (*(--diff) == 0)) + i--; + *diff_size = i; +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: mpa_add + * + * Adds op1 and op2 and puts the result in dest. Dest could be one of the + * operands. + */ +void mpa_add(mpanum dest, + const mpanum op1, const mpanum op2, mpa_scratch_mem pool) +{ + int sign_1; + int sign_2; + mpa_word_t size_1; + mpa_word_t size_2; + mpanum tmp_dest; + int mem_marker; + + size_1 = __mpanum_size(op1); + size_2 = __mpanum_size(op2); + + sign_1 = __mpanum_sign(op1); + sign_2 = __mpanum_sign(op2); + + /* Handle the case when dest is one of the operands */ + mem_marker = ((dest == op1) || (dest == op2)); + if (mem_marker) + mpa_alloc_static_temp_var(&tmp_dest, pool); + else + tmp_dest = dest; + + /* Check if we must do a subtraction or a addition. + * Remember, we're not allowed to modify op1 or op2. + */ + + if (sign_1 == sign_2) { /* same signs */ + /* tmp_dest = |op1| + |op2| or tmp_dest = -(|op1| + |op2|) */ + __mpa_abs_add(tmp_dest->d, &(tmp_dest->size), op1->d, size_1, + op2->d, size_2); + + if (sign_1 == MPA_NEG_SIGN) + __mpanum_neg(tmp_dest); + + } else { /* different signs */ + if (sign_1 == MPA_POS_SIGN) { /* op1 positive, op1 + (-op2) */ + if (__mpa_abs_greater_than(op1, op2)) { + /* |op1| > |op2| */ + + /* tmp_dest = |op1| - |op2| */ + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), + op1->d, size_1, op2->d, size_2); + + } else { /* |op2| >= |op1| */ + /* tmp_dest = - ( |op2| - |op1|) */ + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), + op2->d, size_2, op1->d, size_1); + __mpanum_neg(tmp_dest); + } + + } else { /* op2 positive, (-op1) + op2 */ + if (__mpa_abs_greater_than(op1, op2)) { + /* |op1| > |op2| */ + + /* tmp_dest = - (|op1| - |op2|) */ + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), + op1->d, size_1, op2->d, size_2); + __mpanum_neg(tmp_dest); + } else { /* |op2| >= |op1| */ + /* tmp_dest = |op2| - |op1| */ + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), + op2->d, size_2, op1->d, size_1); + } + } + } + + mpa_copy(dest, tmp_dest); + if (mem_marker) + mpa_free_static_temp_var(&tmp_dest, pool); +} + +/* -------------------------------------------------------------------- + * Function: mpa_sub + * + * Calculated op1 - op2 and stores the result in dest. Dest could be one of + * the operands. + */ +void mpa_sub(mpanum dest, + const mpanum op1, const mpanum op2, mpa_scratch_mem pool) +{ + int sign_1; + int sign_2; + mpa_word_t size_1; + mpa_word_t size_2; + mpanum tmp_dest; + int mem_marker; + + size_1 = __mpanum_size(op1); + size_2 = __mpanum_size(op2); + + sign_1 = __mpanum_sign(op1); + sign_2 = __mpanum_sign(op2); + + /* Handle the case when dest is one of the operands */ + mem_marker = ((dest == op1) || (dest == op2)); + if (mem_marker) + mpa_alloc_static_temp_var(&tmp_dest, pool); + else + tmp_dest = dest; + + /* + * Check if we must do a subtraction or a addition. Remember, + * we're not allowed to modify op1 or op2. + */ + if (sign_1 == sign_2) { /* same signs */ + if (sign_1 == MPA_POS_SIGN) { /* both positive, op1 - op2 */ + if (__mpa_abs_greater_than(op1, op2)) { + /* |op1| > |op2| */ + + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), + op1->d, size_1, op2->d, size_2); + } else { /* |op1| <= |op2| */ + /* tmp_dest = - (|op2| - |op1|) */ + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), + op2->d, size_2, op1->d, size_1); + __mpanum_neg(tmp_dest); + } + } else { + /* both negative, (-op1) - (-op2) = -(op1 - op2) */ + + if (__mpa_abs_greater_than(op1, op2)) { + /* |op1| > |op2| */ + + /* tmp_dest = -(|op1| - |op2|) */ + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), + op1->d, size_1, op2->d, size_2); + __mpanum_neg(tmp_dest); + } else { /* |op1| <= |op2| */ + /* tmp_dest = |op2| - |op1| */ + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), + op2->d, size_2, op1->d, size_1); + } + } + } else { /* different signs */ + if (sign_1 == MPA_POS_SIGN) { /* op1 positive, op1 - (-op2) */ + /* tmp_dest = |op1| + |op2| */ + __mpa_abs_add(tmp_dest->d, &(tmp_dest->size), op1->d, + size_1, op2->d, size_2); + } else { /* op2 positive, (-op1) - op2 = - (op1 + op2) */ + /* tmp_dest = -(|op1| + |op2|) */ + __mpa_abs_add(tmp_dest->d, &(tmp_dest->size), op1->d, + size_1, op2->d, size_2); + __mpanum_neg(tmp_dest); + } + } + + mpa_copy(dest, tmp_dest); + if (mem_marker) + mpa_free_static_temp_var(&tmp_dest, pool); +} + +/* -------------------------------------------------------------------- + * Function: mpa_neg + * + * Assigns dest the value of src, but with a change of sign. Dest and src + * could be the same variable. + */ +void mpa_neg(mpanum dest, const mpanum src) +{ + mpa_copy(dest, src); + __mpanum_neg(dest); +} + +/* -------------------------------------------------------------------- + * Function: mpa_add_word + * + * Add a word_t (op2) to op1 and put result in dest + */ +void mpa_add_word(mpanum dest, + const mpanum op1, mpa_word_t op2, mpa_scratch_mem pool) +{ + int sign_1; + mpanum tmp_dest; + mpa_word_t size_1; + int mem_marker; + + if (op2 == 0) { + mpa_copy(dest, op1); + return; + } + + if (__mpanum_is_zero(op1)) { + dest->size = 1; + dest->d[0] = op2; + return; + } + + sign_1 = __mpanum_sign(op1); + size_1 = __mpanum_size(op1); + + /* handle the case when dest is the operand */ + mem_marker = (dest == op1); + if (mem_marker) + mpa_alloc_static_temp_var(&tmp_dest, pool); + else + tmp_dest = dest; + + /* find out if we should do an add or a sub, op2 is always positive */ + if (sign_1 == MPA_POS_SIGN) { /* add */ + /* tmp_dest = |op1| + op2 */ + __mpa_abs_add(tmp_dest->d, &(tmp_dest->size), op1->d, size_1, + &op2, 1); + } else { /* sub, op1 is negative: (-op1) + op2 */ + if (__mpanum_size(op1) > 1 || __mpanum_lsw(op1) > op2) { + /* |op1| > |op2| */ + + /* tmp_dest = - (|op1| - op2) */ + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), op1->d, + size_1, &op2, 1); + __mpanum_neg(tmp_dest); + } else { /* op2 >= |op1| */ + /* tmp_dest = op2 - |op1| */ + tmp_dest->d[0] = op2 - op1->d[0]; + tmp_dest->size = (tmp_dest->d[0] == 0) ? 0 : 1; + } + } + + mpa_copy(dest, tmp_dest); + if (mem_marker) + mpa_free_static_temp_var(&tmp_dest, pool); +} + +/* -------------------------------------------------------------------- + * Function: mpa_sub_word + * + * Calculate op1 - op2, op2 is a word_t and always positive. + */ +void mpa_sub_word(mpanum dest, + const mpanum op1, mpa_word_t op2, mpa_scratch_mem pool) +{ + int sign_1; + mpanum tmp_dest; + mpa_word_t size_1; + char mem_marker; + + if (op2 == 0) { + mpa_copy(dest, op1); + return; + } + + if (__mpanum_is_zero(op1)) { + dest->size = -1; + dest->d[0] = op2; + return; + } + + sign_1 = __mpanum_sign(op1); + size_1 = __mpanum_size(op1); + + /* handle the case when dest is the operand */ + mem_marker = (dest == op1); + if (mem_marker) + mpa_alloc_static_temp_var(&tmp_dest, pool); + else + tmp_dest = dest; + + /* + * Find out if we should do an add or a sub, op2 is always positive + * + * dest = op1 - op2 if op1 > op2 >= 0 + * dest = -(op2 - op1) if op2 >= op1 >= 0 + * dest = -(|op1| + op2) if op1 < 0 + * + */ + if (sign_1 == MPA_POS_SIGN) { + if (__mpanum_size(op1) > 1 || __mpanum_lsw(op1) > op2) { + __mpa_abs_sub(tmp_dest->d, &(tmp_dest->size), op1->d, + size_1, &op2, 1); + } else { + tmp_dest->d[0] = op2 - op1->d[0]; + tmp_dest->size = (tmp_dest->d[0] == 0) ? 0 : -1; + } + } else { + __mpa_abs_add(tmp_dest->d, &(tmp_dest->size), op1->d, size_1, + &op2, 1); + __mpanum_neg(tmp_dest); + } + + mpa_copy(dest, tmp_dest); + if (mem_marker) + mpa_free_static_temp_var(&tmp_dest, pool); +} diff --git a/lib/libmpa/mpa_cmp.c b/lib/libmpa/mpa_cmp.c new file mode 100644 index 0000000..5d36bde --- /dev/null +++ b/lib/libmpa/mpa_cmp.c @@ -0,0 +1,171 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * HELPERS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: __mpa_abs_cmp + * + * Returns 0 if |op1| == |op2| + * >0 if |op1| > |op2| + * <0 if |op1| < |op2| + */ +int __mpa_abs_cmp(const mpanum op1, const mpanum op2) +{ + int wpos; + char same; + + /* if they're really the same, return 0 */ + if (op1 == op2) + return 0; + + /* check the sizes */ + if (__mpanum_size(op1) != __mpanum_size(op2)) + return __mpanum_size(op1) - __mpanum_size(op2); + + if (__mpanum_is_zero(op1) && __mpanum_is_zero(op2)) + return 0; + + /* Ok, so we have the same size and they're not zero. Check words */ + wpos = __mpanum_size(op1) - 1; + same = 1; + while (same && (wpos >= 0)) { + same = (op1->d[wpos] == op2->d[wpos]); + wpos--; + } + if (same) + return 0; + wpos++; + return (op1->d[wpos] > op2->d[wpos] ? 1 : -1); +} + +/* -------------------------------------------------------------------- + * Function: __mpa_abs_greater_than + * + * Returns 1 if |op1| > |op2| and otherwise returns 0. + */ +int __mpa_abs_greater_than(const mpanum op1, const mpanum op2) +{ + return (__mpa_abs_cmp(op1, op2) > 0 ? 1 : 0); +} + +/* -------------------------------------------------------------------- + * Function: __mpa_abs_less_than + * + * Returns 1 if |op1| < |op2| and otherwise returns 0. + */ +int __mpa_abs_less_than(const mpanum op1, const mpanum op2) +{ + return (__mpa_abs_cmp(op1, op2) < 0 ? 1 : 0); +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: mpa_cmp + * + * Returns 0 if op1 == op2 + * >0 if op1 > op2 + * <0 if op1 < op2 + */ +int32_t mpa_cmp(const mpanum op1, const mpanum op2) +{ + int sign_1; + int abscmp; + + /* if they have different signs, it's straight forward */ + sign_1 = __mpanum_sign(op1); + if (sign_1 != __mpanum_sign(op2)) + return sign_1; + + /* handle the special case where op1->size = 0 */ + if (__mpanum_size(op1) == 0) + return __mpanum_size(op2) == 0 ? 0 : -__mpanum_sign(op2); + + /* so they have the same sign. compare the abs values and decide + * based on sign_1. + */ + + abscmp = __mpa_abs_cmp(op1, op2); + if (sign_1 != MPA_POS_SIGN) + return -abscmp; + return abscmp; +} + +/* -------------------------------------------------------------------- + * Function: mpa_cmp_short + * + * Compares op1 to the word_t op2 and returns: + * >0 if op1 > op2, + * 0 if op1 == op2 + * <0 if op1 < op2 + */ +int32_t mpa_cmp_short(const mpanum op1, int32_t op2) +{ +#if (MPA_WORD_SIZE == 32) + + int sign_1; + int sign_2; + mpa_word_t op2abs; + + sign_1 = __mpanum_sign(op1); + sign_2 = (op2 < 0) ? MPA_NEG_SIGN : MPA_POS_SIGN; + + /* handle the special case where op1->size = 0 */ + if (op1->size == 0) + return op2 == 0 ? 0 : -sign_2; + + /* check if op1 is larger than an int32_t */ + if (__mpanum_size(op1) > 1) + return sign_1; + + /* check if they have different signs */ + if (sign_1 != sign_2) + return sign_1; + + /* here they have the same sign and we can compare absolute values */ + + op2abs = ((op2 < 0) ? (mpa_word_t) -op2 : (mpa_word_t) op2); + + if (__mpanum_lsw(op1) == op2abs) + return 0; + + return (__mpanum_lsw(op1) > op2abs) ? sign_1 : -sign_1; + +#else +#error "Write code for digit size != 32" +#endif +} diff --git a/lib/libmpa/mpa_conv.c b/lib/libmpa/mpa_conv.c new file mode 100644 index 0000000..d7de0dd --- /dev/null +++ b/lib/libmpa/mpa_conv.c @@ -0,0 +1,92 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/*------------------------------------------------------------ + * + * mpa_set_S32 + * + */ +void mpa_set_S32(mpanum dest, int32_t short_val) +{ +#if (MPA_WORD_SIZE == 32) + if (short_val != 0) + dest->size = (short_val < 0) ? -1 : 1; + else + dest->size = 0; + dest->d[0] = (short_val < 0) ? -short_val : short_val; +#else +#error "Write code for digit size != 32" +#endif +} + +/*------------------------------------------------------------ + * + * mpa_get_S32 + * + * Returns zero if the src fits within an int32_t + * otherwise it returns non-zero and the dest value is undefined. + */ +int32_t mpa_get_S32(int32_t *dest, mpanum src) +{ +#if (MPA_WORD_SIZE == 32) + if (__mpanum_size(src) > 1) + return -1; + if (__mpanum_lsw(src) > INT32_MIN && __mpanum_sign(src) == MPA_NEG_SIGN) + return -1; + if (__mpanum_lsw(src) > INT32_MAX && __mpanum_sign(src) == MPA_POS_SIGN) + return -1; + + *dest = __mpanum_get_word(0, src) * __mpanum_sign(src); + return 0; + +#else +#error "Write code for digit size != 32" +#endif +} + +/*------------------------------------------------------------ + * + * mpa_set_word + * + */ +void mpa_set_word(mpanum dest, mpa_word_t src) +{ + dest->d[0] = src; + dest->size = (src == 0) ? 0 : 1; +} + +/*------------------------------------------------------------ + * + * mpa_get_word + * + * Returns the absolute value of the least significant word of src + */ +mpa_word_t mpa_get_word(mpanum src) +{ + return __mpanum_get_word(0, src); +} diff --git a/lib/libmpa/mpa_div.c b/lib/libmpa/mpa_div.c new file mode 100644 index 0000000..dd764f9 --- /dev/null +++ b/lib/libmpa/mpa_div.c @@ -0,0 +1,413 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * HELPER FUNCTIONS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * These functions have ARM assembler implementations + * + */ +#if !defined(USE_ARM_ASM) + +static mpa_dword_t __mpa_soft_div(mpa_dword_t num, mpa_word_t den_in, + mpa_word_t *rem) +{ + mpa_dword_t quot = 0, qbit = 1; + mpa_dword_t den = den_in; + + while ((int64_t) den >= 0) { + den <<= 1; + qbit <<= 1; + } + + while (qbit) { + if (den <= num) { + num -= den; + quot += qbit; + } + den >>= 1; + qbit >>= 1; + } + + if (rem) + *rem = (mpa_word_t) num; + + return quot; +} + +/* -------------------------------------------------------------------- + * Function: __mpa_div_dword + * + * Calculates quotient and remainder of (n1*base + n0) / d. + * It is assumed that the quotient is small enough to fit a single word. + */ +mpa_word_t __mpa_div_dword(mpa_word_t n0, + mpa_word_t n1, mpa_word_t d, mpa_word_t *r) +{ +#if defined(MPA_SUPPORT_DWORD_T) + mpa_dword_t n; + /* mpa_dword_t tmp_q; */ + + n = ((mpa_dword_t) n1 << WORD_SIZE) + n0; + return __mpa_soft_div(n, d, r); + /* tmp_q = n / d; */ + /* *r = (mpa_word_t)(n % d); */ + /* return tmp_q; */ +#else +#error write non-dword code for __mpa_div_dword +#endif +} + +#endif /* USE_ARM_ASM */ + +/* -------------------------------------------------------------------- + * Function: __mpa_div_q_r_internal + * + * Finds the quotient and remainder when |op1| is divided by |op2|. + * q, r, op1 and op2 must all be distinct and not null. + * E.i. we get q and r such that |op1| = q*|op2| + r, 0<= r < |op2|. + * Assumptions: |op1| >= |op2| and |op2| >= 2^(WORD_SIZE) + * + */ +static void __mpa_div_q_r_internal(mpanum q, + mpanum r, + const mpanum op1, + const mpanum op2, mpa_scratch_mem pool) +{ + mpa_word_t normshift; + int base_diff; + int i; + int cmp_same; + mpa_usize_t n; /* size of op1 */ + mpa_usize_t t; /* size of op2 */ + mpa_word_t w1; + mpa_word_t w2; + mpa_word_t w3; + mpa_word_t w4; + mpa_word_t w5; + mpanum p; + mpanum y; + mpanum x; + + /* + * get temp storage + */ + mpa_alloc_static_temp_var(&p, pool); + mpa_alloc_static_temp_var(&y, pool); + mpa_copy(y, op2); + + /* + * May need a large value for r since op1 may be an "oversized" + * value that is reduced. x is used for that internally and it's + * initial value is op1. + */ + mpa_alloc_static_temp_var(&x, pool); + mpa_copy(x, op1); + __mpanum_set_sign(x, MPA_POS_SIGN); + __mpanum_set_sign(y, MPA_POS_SIGN); + + /* + * Normalization + */ + normshift = 0; + w1 = __mpanum_msw(y); + while (w1 < ((mpa_word_t)1 << (WORD_SIZE - 1))) { + normshift++; + w1 <<= 1; + } + if (normshift) { + mpa_shift_left(x, x, normshift); + mpa_shift_left(y, y, normshift); + } + + n = x->size; + t = y->size; + base_diff = (int)n - t; + + mpa_wipe(q); + + /* + * check if op1 >= op2*base^(base_diff) + */ + /* mpa_shift_left(y, y, base_diff * WORD_SIZE); */ + __mpa_shift_words_left(y, base_diff); + + i = __mpanum_size(y); + cmp_same = 1; + while (cmp_same != 0 && i > 0) { + i--; + cmp_same = (__mpanum_get_word(i, x) == __mpanum_get_word(i, y)); + } + if (!cmp_same && (__mpanum_get_word(i, x) > __mpanum_get_word(i, y))) { + q->d[base_diff] = 1; + mpa_sub(x, x, y, pool); + } + + /* start main division loop */ + i = x->size - 1; + while (i >= (int)t) { + if (__mpanum_get_word(i, x) == + __mpanum_get_word(t + base_diff - 1, y)) { + q->d[i - t] = WORD_ALL_BITS_ONE; + } else { + q->d[i - t] = + __mpa_div_dword(__mpanum_get_word(i - 1, x), + __mpanum_get_word(i, x), + __mpanum_get_word(t + base_diff + - 1, y), + NULL); + } + while (1) { + /* set incoming carry to zero for all three ops */ + w1 = 0; + w3 = 0; + w5 = 0; + __mpa_mul_add_word(q->d[i - t], + __mpanum_get_word(t + base_diff - 1, + y), &w2, &w1); + + if (w1 > __mpanum_get_word(i, x)) + goto loop_dec; + + __mpa_mul_add_word(q->d[i - t], + __mpanum_get_word(t + base_diff - 2, + y), &w4, &w3); + + __mpa_full_adder(w2, w3, &w3, &w5); + w2 = 0; /* used as carry */ + __mpa_full_adder(w1, w5, &w5, &w2); + if (w2 || w5 > __mpanum_get_word(i, x)) + goto loop_dec; + if (w5 < __mpanum_get_word(i, x)) + break; + if (w3 > __mpanum_get_word(i - 1, x)) + goto loop_dec; + if (w3 < __mpanum_get_word(i - 1, x)) + break; + if (w4 > __mpanum_get_word(i - 2, x)) + goto loop_dec; + break; +loop_dec: + q->d[i - t]--; + } + + /* mpa_shift_right(y, y, WORD_SIZE); */ + __mpa_shift_words_right(y, 1); + base_diff--; + mpa_mul_word(p, y, q->d[i - t], pool); + mpa_sub(x, x, p, pool); + if (__mpanum_sign(x) == MPA_NEG_SIGN) { + mpa_add(x, x, y, pool); + q->d[i - t]--; + } + i--; + } + /* + * Find size of q + */ + i = n - t; + while (i >= 0 && q->d[i] == 0) + i--; + q->size = i + 1; + /* + * Divide r by the normalization value and copy to output + */ + mpa_shift_right(x, x, normshift); + mpa_copy(r, x); + + /* + * release p, y, and x + */ + mpa_free_static_temp_var(&p, pool); + mpa_free_static_temp_var(&y, pool); + mpa_free_static_temp_var(&x, pool); +} + +/* -------------------------------------------------------------------- + * Function: __mpa_div_q_r_internal_word + * + * Finds the quotient and remainder when |op1| is divided by |op2|, where + * op2 is a word. + * q, r and op1 must all be distinct and not null. + * E.i. we get q and r such that |op1| = q*|op2| + r, 0<= r < |op2|. + * Assumptions: |op1| >= |op2|. + + */ +void __mpa_div_q_r_internal_word(mpanum q, + mpanum r, + const mpanum op1, const mpa_word_t op2) +{ + int pos1; + mpa_word_t q_word; + mpa_word_t r_word; + mpa_word_t n1; + mpa_word_t n0; + int i; + + if (__mpanum_size(op1) == 1) { + mpa_set_word(q, op1->d[0] / op2); + mpa_set_word(r, op1->d[0] % op2); + return; + } + mpa_copy(r, op1); + mpa_set_word(q, 0); + + pos1 = (int)__mpanum_size(r) - 1; + n1 = 0; + n0 = r->d[pos1]; + while (pos1 >= 0) { + q_word = __mpa_div_dword(n0, n1, op2, &r_word); + q->d[pos1] = q_word; + r->d[pos1] = r_word; + n1 = r->d[pos1]; + n0 = r->d[--pos1]; + } + /* set sizes of r and q */ + r->size = (r->d[0] == 0 ? 0 : 1); + i = __mpanum_size(op1) - 1; + while (i >= 0 && q->d[i] == 0) + i--; + q->size = i + 1; +} + +/* -------------------------------------------------------------------- + * Function: __mpa_div_q_r + * + * Calculates the quotient and remainder when op1 is divided by op2. + * q, r, op1 and op2 must all be distinct and not null, except that op1 + * may be equal to op2. + * There must be enough space allocated in q and r to handle the results. + * If op2 is zero a division with zero will be executed and the above layers + * can handle that as it pleases. + * The sign of q and r are shown in the table: + * __________________________________ + * | Sign(q/r) | op1 >= 0 | op1 < 0 | + * |--------------------------------| + * | op2 > 0 | +/+ | -/- | + * |--------------------------------| + * | op2 < 0 | -/+ | +/- | + * |________________________________| + */ +void __mpa_div_q_r(mpanum q, + mpanum r, + const mpanum op1, const mpanum op2, mpa_scratch_mem pool) +{ + int q_sign; + int cmp; + + if (__mpanum_is_zero(op1)) { + mpa_set_word(q, 0); + mpa_set_word(r, 0); + return; + } + if (__mpanum_is_zero(op2)) { + /* generate a divide by zero error */ + q_sign = 42 / op2->size; + return; + } + + q_sign = + (__mpanum_sign(op1) != + __mpanum_sign(op2)) ? MPA_NEG_SIGN : MPA_POS_SIGN; + cmp = __mpa_abs_cmp(op1, op2); + if (cmp == 0) { + mpa_set_word(q, 1); + mpa_set_word(r, 0); + return; + } + if (cmp > 0) { /* |op1| > |op2| */ + if (__mpanum_size(op2) > 1) + __mpa_div_q_r_internal(q, r, op1, op2, pool); + else + __mpa_div_q_r_internal_word(q, r, op1, op2->d[0]); + } else { /* |op1| < |op2| */ + mpa_set_word(q, 0); + mpa_copy(r, op1); + return; + } + __mpanum_set_sign(q, q_sign); + __mpanum_set_sign(r, __mpanum_sign(op1)); +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: mpa_div + * + * Returns the quotient and the remainder of op1 divided by op2. + * q and r must be distinct variables. + * This function returns q and r such that + * op1 = q*op2 + r + * where 0 <= r < |op2| + */ +void mpa_div(mpanum q, + mpanum r, const mpanum op1, const mpanum op2, mpa_scratch_mem pool) +{ + mpanum tmp_q; + mpanum tmp_r; + char mem_marker_q; + char mem_marker_r; + + /* handle the case when q is one of the operands or zero */ + if (q == op1 || q == op2 || q == 0) { + mpa_alloc_static_temp_var(&tmp_q, pool); + mem_marker_q = 1; + } else { + tmp_q = q; + mem_marker_q = 0; + } + + /* handle the case when r is one of the operands or zero */ + if (r == op1 || r == op2 || r == 0) { + mpa_alloc_static_temp_var(&tmp_r, pool); + mem_marker_r = 1; + } else { + tmp_r = r; + mem_marker_r = 0; + } + + __mpa_div_q_r(tmp_q, tmp_r, op1, op2, pool); + + if (q != 0) + mpa_copy(q, tmp_q); + if (mem_marker_q) + mpa_free_static_temp_var(&tmp_q, pool); + if (r != 0) + mpa_copy(r, tmp_r); + if (mem_marker_r) + mpa_free_static_temp_var(&tmp_r, pool); +} diff --git a/lib/libmpa/mpa_expmod.c b/lib/libmpa/mpa_expmod.c new file mode 100644 index 0000000..d02c784 --- /dev/null +++ b/lib/libmpa/mpa_expmod.c @@ -0,0 +1,85 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/*------------------------------------------------------------ + * + * mpa_exp_mod + * + * Calculates dest = op1 ^ op2 mod n + * + */ +void mpa_exp_mod(mpanum dest, + const mpanum op1, + const mpanum op2, + const mpanum n, + const mpanum r_modn, + const mpanum r2_modn, + const mpa_word_t n_inv, mpa_scratch_mem pool) +{ + mpanum A; + mpanum B; + mpanum xtilde; + mpanum *ptr_a; + mpanum *ptr_b; + mpanum *swapper; + int idx; + + mpa_alloc_static_temp_var(&A, pool); + mpa_alloc_static_temp_var(&B, pool); + mpa_alloc_static_temp_var(&xtilde, pool); + + /* transform to Montgomery space */ + /* use internal version since xtidle is big enough */ + __mpa_montgomery_mul(xtilde, op1, r2_modn, n, n_inv); + + mpa_copy(A, r_modn); + ptr_a = &A; + ptr_b = &B; + __mpa_set_unused_digits_to_zero(A); + __mpa_set_unused_digits_to_zero(B); + for (idx = mpa_highest_bit_index(op2); idx >= 0; idx--) { + __mpa_montgomery_mul(*ptr_b, *ptr_a, *ptr_a, n, n_inv); + if (mpa_get_bit(op2, idx) == 1) { + __mpa_montgomery_mul(*ptr_a, *ptr_b, xtilde, n, n_inv); + } else { + swapper = ptr_a; + ptr_a = ptr_b; + ptr_b = swapper; + } + } + + /* transform back form Montgomery space */ + __mpa_montgomery_mul(*ptr_b, (const mpanum)&const_one, *ptr_a, + n, n_inv); + + mpa_copy(dest, *ptr_b); + + mpa_free_static_temp_var(&A, pool); + mpa_free_static_temp_var(&B, pool); + mpa_free_static_temp_var(&xtilde, pool); +} diff --git a/lib/libmpa/mpa_gcd.c b/lib/libmpa/mpa_gcd.c new file mode 100644 index 0000000..79b82c5 --- /dev/null +++ b/lib/libmpa/mpa_gcd.c @@ -0,0 +1,372 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * HELPER FUNCTIONS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * __mpa_divby2 + * + */ +static void __mpa_divby2(mpanum op) +{ + mpa_word_t i; + /* The bit of the word which will be shifted into another word. */ + mpa_word_t rbit; + int msw_became_zero; + + if (__mpanum_is_zero(op)) + return; + + msw_became_zero = ((__mpanum_msw(op) >> 1) == 0) ? 1 : 0; + + op->d[0] = op->d[0] >> 1; + for (i = 1; i < __mpanum_size(op); i++) { + rbit = op->d[i] & 0x01; + op->d[i] = op->d[i] >> 1; + op->d[i - 1] ^= (rbit << (WORD_SIZE - 1)); + } + /* update the size of dest */ + if (__mpanum_sign(op) == MPA_NEG_SIGN) + op->size += msw_became_zero; + else + op->size -= msw_became_zero; +} + +/*------------------------------------------------------------ + * + * __mpa_mulby2 + * + */ +/* +static void __mpa_mulby2(mpanum op) +{ + mpa_word_t i; + mpa_word_t rbit; + mpa_word_t need_extra_word; + + if (__mpanum_is_zero(op)) + return; + + need_extra_word = (__mpanum_msw(op) & (1 << (WORD_SIZE - 1)))?1:0; + + if (need_extra_word) + i = __mpanum_size(op); + else + i = __mpanum_size(op) - 1; + while (i > 0) { + rbit = op->d[i-1] >> (WORD_SIZE - 1); + op->d[i] = op->d[i] << 1; + op->d[i] ^= rbit; + i--; + } + rbit = op->d[0] >> (WORD_SIZE - 1); + + if (__mpanum_sign(op) == MPA_POS_SIGN) + op->size += need_extra_word; + else + op->size -= need_extra_word; +} +*/ + +/* -------------------------------------------------------------------- + * Function: __mpa_egcd + * + * Given non-negative integers x and y where y < x, we compute + * gcd, a and b such that + * a*x + b*y = gcd + * + * gcd must be distrinct and non-zero, that is, + * it cannot point to the same mpanum as x_in or y_in or be a null pointer. + */ +static void __mpa_egcd(mpanum gcd, + mpanum a, + mpanum b, + const mpanum x_in, + const mpanum y_in, mpa_scratch_mem pool) +{ + mpanum A; + mpanum B; + mpanum C; + mpanum D; + mpanum x; + mpanum y; + mpanum u; + mpa_word_t k; + + /* have y < x from assumption */ + if (__mpanum_is_zero(y_in)) { + if (a != 0) + mpa_set_word(a, 1); + if (b != 0) + mpa_set_word(b, 0); + mpa_copy(gcd, x_in); + return; + } + mpa_alloc_static_temp_var(&x, pool); + mpa_copy(x, x_in); + mpa_alloc_static_temp_var(&y, pool); + mpa_copy(y, y_in); + + k = 0; + while (mpa_is_even(x) && mpa_is_even(y)) { + k++; + __mpa_divby2(x); + __mpa_divby2(y); + } + + mpa_alloc_static_temp_var(&u, pool); + mpa_copy(u, x); + mpa_copy(gcd, y); + mpa_alloc_static_temp_var(&A, pool); + mpa_set_word(A, 1); + mpa_alloc_static_temp_var(&B, pool); + mpa_set_word(B, 0); + mpa_alloc_static_temp_var(&C, pool); + mpa_set_word(C, 0); + mpa_alloc_static_temp_var(&D, pool); + mpa_set_word(D, 1); + + while (!__mpanum_is_zero(u)) { + while (mpa_is_even(u)) { + __mpa_divby2(u); + if (mpa_is_odd(A) || mpa_is_odd(B)) { + mpa_add(A, A, y, pool); + mpa_sub(B, B, x, pool); + } + __mpa_divby2(A); + __mpa_divby2(B); + } + + while (mpa_is_even(gcd)) { + __mpa_divby2(gcd); + if (mpa_is_odd(C) || mpa_is_odd(D)) { + mpa_add(C, C, y, pool); + mpa_sub(D, D, x, pool); + } + __mpa_divby2(C); + __mpa_divby2(D); + } + + if (mpa_cmp(u, gcd) >= 0) { + mpa_sub(u, u, gcd, pool); + mpa_sub(A, A, C, pool); + mpa_sub(B, B, D, pool); + } else { + mpa_sub(gcd, gcd, u, pool); + mpa_sub(C, C, A, pool); + mpa_sub(D, D, B, pool); + } + } + + /* copy results */ + if (a != 0) + mpa_copy(a, C); + if (b != 0) + mpa_copy(b, D); + mpa_shift_left(gcd, gcd, k); + + mpa_free_static_temp_var(&A, pool); + mpa_free_static_temp_var(&B, pool); + mpa_free_static_temp_var(&C, pool); + mpa_free_static_temp_var(&D, pool); + mpa_free_static_temp_var(&x, pool); + mpa_free_static_temp_var(&y, pool); + mpa_free_static_temp_var(&u, pool); +} + +/* -------------------------------------------------------------------- + * Function: __mpa_gcd + * Computes the gcd of x and y where y <= x. + * Destination variable gcd must be allocated. + */ +static void __mpa_gcd(mpanum gcd, + const mpanum x_in, + const mpanum y_in, mpa_scratch_mem pool) +{ + mpanum x; + mpanum y; + mpanum t; + mpa_word_t k; + + /* have y < x from assumption */ + if (__mpanum_is_zero(y_in)) { + mpa_copy(gcd, x_in); + return; + } + mpa_alloc_static_temp_var(&x, pool); + mpa_copy(x, x_in); + mpa_alloc_static_temp_var(&y, pool); + mpa_copy(y, y_in); + + k = 0; + while (mpa_is_even(x) && mpa_is_even(y)) { + k++; + __mpa_divby2(x); + __mpa_divby2(y); + } + + mpa_alloc_static_temp_var(&t, pool); + while (!__mpanum_is_zero(x)) { + while (mpa_is_even(x)) + __mpa_divby2(x); + + while (mpa_is_even(y)) + __mpa_divby2(y); + + mpa_sub(t, x, y, pool); + /* abs val of t */ + __mpanum_set_sign(t, MPA_POS_SIGN); + __mpa_divby2(t); + if (mpa_cmp(x, y) >= 0) + mpa_copy(x, t); + else + mpa_copy(y, t); + } + + mpa_shift_left(gcd, y, k); + mpa_free_static_temp_var(&t, pool); + mpa_free_static_temp_var(&x, pool); + mpa_free_static_temp_var(&y, pool); +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: mpa_gcd + * + * Computes the GCD of src1 and src2 + */ +void mpa_gcd(mpanum dest, + const mpanum src1, const mpanum src2, mpa_scratch_mem pool) +{ + int cmp; + int sign1; + int sign2; + + /* remember sign and take abs value */ + sign1 = __mpanum_sign(src1); + sign2 = __mpanum_sign(src2); + __mpanum_set_sign(src1, MPA_POS_SIGN); + __mpanum_set_sign(src2, MPA_POS_SIGN); + + cmp = mpa_cmp(src1, src2); + if (cmp == 0) { + mpa_copy(dest, src1); + goto cleanup; + } + if (cmp < 0) { /* src1 < src2, swap data */ + __mpa_gcd(dest, src2, src1, pool); + } else { + __mpa_gcd(dest, src1, src2, pool); + } + +cleanup: + /* restore sign */ + __mpanum_set_sign(src1, sign1); + __mpanum_set_sign(src2, sign2); +} + +/* -------------------------------------------------------------------- + * Function: mpa_extended_gcd + * + * Computes gcd, dest1 and dest2 such that + * dest1*src1 + dest2*src2 = gcd + * + * May be called with gcd, dest1 and/or dest2 == 0. + * + */ +void mpa_extended_gcd(mpanum gcd, + mpanum dest1, + mpanum dest2, + const mpanum src1, + const mpanum src2, mpa_scratch_mem pool) +{ + int cmp; + int sign1; + int sign2; + int mem_marker; + mpanum tmp_gcd; + + if (dest1 == 0 && dest2 == 0) { + if (gcd != 0) + mpa_gcd(gcd, src1, src2, pool); + return; + } + + /* remember sign and take abs value */ + sign1 = __mpanum_sign(src1); + sign2 = __mpanum_sign(src2); + __mpanum_set_sign(src1, MPA_POS_SIGN); + __mpanum_set_sign(src2, MPA_POS_SIGN); + + cmp = mpa_cmp(src1, src2); + if (cmp == 0) { + if (gcd != 0) + mpa_copy(gcd, src1); + if (dest1 != 0) + mpa_set_word(dest1, 1); + if (dest2 != 0) + mpa_set_word(dest2, 0); + goto cleanup; + } + + mem_marker = (gcd == 0 || gcd == src1 || gcd == src2); + if (mem_marker) + mpa_alloc_static_temp_var(&tmp_gcd, pool); + else + tmp_gcd = gcd; + + if (cmp < 0) /* src1 < src2, swap data */ + __mpa_egcd(tmp_gcd, dest2, dest1, src2, src1, pool); + else + __mpa_egcd(tmp_gcd, dest1, dest2, src1, src2, pool); + + if (gcd != 0) + mpa_copy(gcd, tmp_gcd); + if (mem_marker) + mpa_free_static_temp_var(&tmp_gcd, pool); + +cleanup: + /* restore sign */ + __mpanum_set_sign(src1, sign1); + __mpanum_set_sign(src2, sign2); + /* change resulting signs if needed */ + if (sign1 == MPA_NEG_SIGN && dest1 != 0) + __mpanum_neg(dest1); + if (sign2 == MPA_NEG_SIGN && dest2 != 0) + __mpanum_neg(dest2); +} diff --git a/lib/libmpa/mpa_init.c b/lib/libmpa/mpa_init.c new file mode 100644 index 0000000..35a6356 --- /dev/null +++ b/lib/libmpa/mpa_init.c @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include "mpa.h" + +/* + * mpa_init_static + */ +void mpa_init_static(mpanum src, uint32_t len) +{ + src->alloc = U32_TO_ASIZE(len - MPA_NUMBASE_METADATA_SIZE_IN_U32); + src->size = 0; + if (src->alloc > 0) + src->d[0] = 0; +} + +/*------------------------------------------------------------ + * + * mpa_InitStaticFMMContext + * + */ +void mpa_init_static_fmm_context(mpa_fmm_context_base *context, uint32_t len) +{ + mpa_asize_t m_alloc; + + m_alloc = + U32_TO_ASIZE((mpa_asize_t) len - + (mpa_asize_t) MPA_FMM_CONTEXT_METADATA_SIZE_IN_U32); + /* clear the array before halfing into r and r2 */ + mpa_memset(context->m, 0, m_alloc * BYTES_PER_WORD); + m_alloc /= 2; + + /* setup context content */ + context->n_inv = 0; + + context->r_ptr = (void *)context->m; + context->r_ptr->alloc = + m_alloc - U32_TO_ASIZE(MPA_NUMBASE_METADATA_SIZE_IN_U32); + context->r_ptr->size = 0; + + context->r2_ptr = (void *)(context->m + m_alloc); + context->r2_ptr->alloc = + m_alloc - U32_TO_ASIZE(MPA_NUMBASE_METADATA_SIZE_IN_U32); + context->r2_ptr->size = 0; +} diff --git a/lib/libmpa/mpa_io.c b/lib/libmpa/mpa_io.c new file mode 100644 index 0000000..3290ac3 --- /dev/null +++ b/lib/libmpa/mpa_io.c @@ -0,0 +1,538 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ + +#include <assert.h> +#include <mpa.h> +#include <trace.h> + +/* + * Big #ifdef to get rid of string conversion routines + */ +#if defined(MPA_INCLUDE_STRING_CONVERSION) + +/************************************************************* + * + * HELPERS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: __mpa_isspace + * + * Returns 1 if c is a while space character + */ +static int __mpa_isspace(char c) +{ + return c == '_' || /* allow underscore which makes long hex */ + /* numbers easier to read */ + c == ' ' || /* space */ + c == '\n' || /* new line */ + c == '\r' || /* carriage return */ + c == '\t'; /* tab */ +} + +/* -------------------------------------------------------------------- + * Function: __mpa_is_char_in_base + * + * Returns 1 if c is either a white space char or a char in the current base, + * and 0 otherwise. + */ +static int __mpa_is_char_in_base(int base, int c) +{ + if (__mpa_isspace(c)) + return 1; + + switch (base) { + case 10: + return (c >= '0') && (c <= '9'); + case 16: + return ((c >= '0') && (c <= '9')) || + ((c >= 'A') && (c <= 'F')) || + ((c >= 'a') && (c <= 'f')); + default: + return 0; + } +} + +/* -------------------------------------------------------------------- + * Function: __mpa_digit_value + * + * Returns the integer value of the hexadecimal character c. + */ +static int __mpa_digit_value(int c) +{ + if ((c >= '0') && (c <= '9')) + return c - '0'; + if ((c >= 'A') && (c <= 'F')) + return c - 'A' + 10; + if ((c >= 'a') && (c <= 'f')) + return c - 'a' + 10; + + /* defensive */ + return 0; +} + +/* -------------------------------------------------------------------- + * Function: __mpa_digitstr_to_binary_wsize + * + * Returns the maximum number of words needed to binary represent a number + * consisting of "digits" digits and each digits is in base "base". + */ +static mpa_word_t __mpa_digitstr_to_binary_wsize_base_16(int digits) +{ + return (digits + 7) >> 3; +} + +/* -------------------------------------------------------------------- + * Function: __mpa_nibble_to_char + * + * caseing = 1 is lower case, 0 is uppercase + */ +static char __mpa_nibble_to_char(mpa_word_t c, int caseing) +{ + c &= 0xf; + if (c < 0xa) + return '0' + (char)c; + return caseing == 0 ? 'A' - 0xA + (char)c: 'a' - 0xa + (char)c; +} + +/* -------------------------------------------------------------------- + * Function: __mpa_word_to_hexstr + * + * caseing 8= 1 is lower case, 0 is uppercase + */ +static void __mpa_word_to_hexstr(char *str, mpa_word_t w, int caseing) +{ + int i; + for (i = NIBBLES_PER_WORD; i > 0; i--) { + str[i - 1] = + __mpa_nibble_to_char(NIBBLE_OF_WORD(i - 1, w), caseing); + } +} + +/* -------------------------------------------------------------------- + * Function: __mpa_mpanum_to_hexstr + * + * caseing = 1 is lower case, 0 is uppercase + */ +static int __mpa_mpanum_to_hexstr(char *str, int caseing, const mpanum n) +{ + int d_idx; + char digits[NIBBLES_PER_WORD]; + int i; + char *cptr; + int hex_digits; + + /* get high word with data in, watch out for zero case */ + d_idx = __mpanum_size(n); + if (d_idx == 0) { + *str++ = '0'; + *str = '\0'; + return 1; + } + d_idx--; + + cptr = str; + + /* the msw is special, since if we should not print leading zeros. + */ + __mpa_word_to_hexstr(digits, n->d[d_idx], caseing); + + /* find the left-most non-zero digit */ + i = NIBBLES_PER_WORD; + while (i-- > 0) + if (digits[i] != '0') + break; + while (i >= 0) + *str++ = digits[i--]; + + /* convert each word to a hex string */ + d_idx--; + while (d_idx >= 0) { + __mpa_word_to_hexstr(digits, n->d[d_idx], caseing); + i = NIBBLES_PER_WORD - 1; + while (i >= 0) + *str++ = digits[i--]; + d_idx--; + } + hex_digits = (int)(str - cptr); + *str++ = '\0'; + return hex_digits; +} + +/* -------------------------------------------------------------------- + * Function: __mpa_count_leading_zero_bits + * + * + */ +static mpa_word_t __mpa_count_leading_zero_bits(mpa_word_t w) +{ + mpa_word_t mask; + mpa_word_t zeros; + + if (w == 0) + return MPA_WORD_SIZE; + mask = ((mpa_word_t)1 << (MPA_WORD_SIZE - 1)); + zeros = 0; + while (!(w & mask)) { + zeros++; + mask >>= 1; + } + return zeros; +} + +/* -------------------------------------------------------------------- + * Function: mpa_SizeInBase + * + * Returns the number of characters needed to print |n| in base 255. + */ +static mpa_word_t __mpa_size_in_base_255(const mpanum n) +{ + mpa_word_t totalbits; + /* number of leading zero bits in the msw of n */ + mpa_word_t zerobits_msw; + + if (__mpanum_is_zero(n)) + return 1; + + zerobits_msw = __mpa_count_leading_zero_bits( + n->d[__mpanum_size(n) - 1]); + totalbits = WORD_SIZE * __mpanum_size(n) - zerobits_msw; + + return (totalbits + 7) / 8; +} + +/* -------------------------------------------------------------------- + * Function: mpa_get_str_size + * + * Return the max size of the string representing a Big Number + */ +int mpa_get_str_size(void) +{ + return MPA_STR_MAX_SIZE; +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: mpa_set_str + * + * Assigns dest the value of the digitstr, where digitstr is a character + * string. + * If the digitstr starts with a valid number, the valid part will be + * converted and the rest of the digitstr will not be parsed further. + * digitstr is assumed to be in base 16. + * Returns -1 if the digitstr was malformed, and the number of base digits + * converted (not including leading zeros) if the conversion was OK. + * If the digitstr is a null-ptr we return -1. + * If the digitstr is empty, we don't touch dest and just returns 0. + * If the digitstr only consists of white spaces, we set dest to zero + * returns 0. + */ +int mpa_set_str(mpanum dest, const char *digitstr) +{ + /* length of digitstr after removal of base indicator and spaces */ + int dlen; + int negative; /* ==1 if number is negative, 0 otherwise */ + int c; /* value of characters in digitstr */ + /* a buffer holding the integer values of the digits */ + static unsigned char buf[MPA_STR_MAX_SIZE]; + /* number of digits in digitstr which has been place in buf */ + int bufidx; + const char *endp; /* points to the end of digitstr */ + int retval; + /* + * Pointer intto dest->d where we should put the next word during + * conversion. + */ + mpa_word_t *w; + int i; /* loop variable */ + + /* some basic sanity checks first */ + if (*digitstr == 0) + return 0; + + /* remove leading spaces */ + do { + c = (unsigned char)*digitstr++; + } while (__mpa_isspace(c)); + + /* check negative sign */ + negative = 0; + if (c == '-') { + negative = 1; + c = (unsigned char)*digitstr++; + } + if (c == '\0') { + mpa_set_word(dest, 0); + return 0; + } + + /* see if we have a '0x' prefix */ + if (c == '0') { + c = (unsigned char)*digitstr++; + if (c == 'x' || c == 'X') + c = (unsigned char)*digitstr++; + } + + /* skip leading zeros and spaces */ + while (c == '0' || __mpa_isspace(c)) + c = (unsigned char)*digitstr++; + + /* check if we had a simple "0" string */ + if (c == '\0') { + mpa_set_word(dest, 0); + return 0; + } + + /* find the end of digitstr */ + endp = digitstr; + while (*endp != 0) + endp++; + + /* + 1 since we have one character in 'c' */ + dlen = (int)(endp - digitstr) + 1; + if (dlen > MPA_STR_MAX_SIZE) { + EMSG("data len (%d) > max size (%d)", dlen, MPA_STR_MAX_SIZE); + retval = -1; + goto cleanup; + } + + /* convert to a buffer of bytes */ + bufidx = 0; + while (__mpa_is_char_in_base(16, c)) { + if (!__mpa_isspace(c)) + buf[bufidx++] = __mpa_digit_value(c); + c = (unsigned char)*digitstr++; + } + + if (bufidx == 0) { + retval = -1; + goto cleanup; + } + if (__mpa_digitstr_to_binary_wsize_base_16(bufidx) > + __mpanum_alloced(dest)) { + EMSG("binary buffer (%d) > alloced buffer (%d)", + __mpa_digitstr_to_binary_wsize_base_16(bufidx), + __mpanum_alloced(dest)); + retval = -1; + goto cleanup; + } + + retval = bufidx; + w = dest->d; + mpa_set_word(dest, 0); + /* start converting */ + *w = 0; + i = BYTES_PER_WORD; + dest->size = 1; + bufidx--; /* dec to get inside buf range */ + while (bufidx > 1) { + *w ^= ((((mpa_word_t)buf[bufidx - 1] << 4) ^ (buf[bufidx])) << + ((mpa_word_t)(BYTES_PER_WORD - i) << 3)); + i--; + bufidx -= 2; + if (i == 0) { + w++; + *w = 0; + i = BYTES_PER_WORD; + dest->size++; + } + } + if (bufidx == 1) + *w ^= ((((mpa_word_t)buf[bufidx - 1] << 4) ^ (buf[bufidx])) << + ((mpa_word_t)(BYTES_PER_WORD - i) << 3)); + if (bufidx == 0) + *w ^= ((mpa_word_t)buf[bufidx] << + ((mpa_word_t)(BYTES_PER_WORD - i) << 3)); + + if (negative) + __mpanum_neg(dest); + +cleanup: + return retval; +} + +/* -------------------------------------------------------------------- + * Function: mpa_get_str + * + * Prints a representation of n into str. + * The length allocated is the space needed to print n plus additional + * chars for the minus sign and the terminating '\0' char. + * A pointer to str is returned. If something went wrong, we return 0. + * + * mode is one of the following: + * MPA_STRING_MODE_HEX_UC hex notation using upper case + * MPA_STRING_MODE_HEX_LC hex notation using lower case + * + */ +char *mpa_get_str(char *str, int mode, const mpanum n) +{ + char *s = str; + + assert(str); + + /* insert a minus sign */ + if (__mpanum_sign(n) == MPA_NEG_SIGN) { + *s = '-'; + s++; + } + switch (mode) { + case MPA_STRING_MODE_HEX_UC: + __mpa_mpanum_to_hexstr(s, 0, n); + break; + case MPA_STRING_MODE_HEX_LC: + __mpa_mpanum_to_hexstr(s, 1, n); + break; + default: + return 0; + } + + return str; +} + +#endif /* #if defined (MPA_INCLUDE_STRING_CONVERSION) */ + +static mpa_word_t set_word(const uint8_t *in, size_t in_len) +{ + int i; + mpa_word_t out; + + out = 0; + for (i = in_len - 1; i >= 0; i--) + out |= (mpa_word_t)in[i] << ((in_len - i - 1) * 8); + return out; +} + +int mpa_set_oct_str(mpanum dest, const uint8_t *buffer, size_t buffer_len, + bool negative) +{ + const uint8_t *buf = buffer; + int bufidx = buffer_len; + mpa_word_t *w; + + /* Strip of leading zero octets */ + while (bufidx > 0) { + if (*buf != 0) + break; + bufidx--; + buf++; + } + + if (bufidx == 0) { + mpa_set_word(dest, 0); + return 0; + } + + /* + * bufidx is now indexing one byte past past the last byte in the octet + * string relative to buf. + */ + + if ((size_t) (bufidx - 1) > (BYTES_PER_WORD * __mpanum_alloced(dest))) + return -1; /* No space */ + + w = dest->d; + mpa_set_word(dest, 0); + /* start converting */ + dest->size = 0; + while (bufidx > 0) { + int l = __MIN(BYTES_PER_WORD, bufidx); + + bufidx -= l; + *w = set_word(buf + bufidx, l); + w++; + dest->size++; + } + + if (negative) + __mpanum_neg(dest); + + return 0; +} + +static void get_word(mpa_word_t in, uint8_t out[BYTES_PER_WORD]) +{ + int i; + + for (i = BYTES_PER_WORD - 1; i >= 0; i--) { + out[i] = in & UINT8_MAX; + in >>= 8; + } +} + +int mpa_get_oct_str(uint8_t *buffer, size_t *buffer_len, const mpanum n) +{ + size_t req_blen = __mpa_size_in_base_255(n); + uint8_t first_word[BYTES_PER_WORD]; + size_t bufidx = 0; + int d_idx; + int i; + + if (*buffer_len < req_blen) { + *buffer_len = req_blen; + return -1; + } + /* get high word with data in, watch out for zero case */ + d_idx = __mpanum_size(n); + if (d_idx == 0) { + memset(buffer, 0, *buffer_len); + goto out; + } + d_idx--; + + /* Strip of leading zero octets */ + get_word(n->d[d_idx], first_word); + + for (i = 0; i < BYTES_PER_WORD; i++) { + if (first_word[i] != 0) { + memcpy(buffer, first_word + i, BYTES_PER_WORD - i); + bufidx = BYTES_PER_WORD - i; + break; + } + } + d_idx--; + + while (d_idx >= 0) { + if (bufidx > req_blen) + return -1; + get_word(n->d[d_idx], buffer + bufidx); + + bufidx += BYTES_PER_WORD; + d_idx--; + } + +out: + *buffer_len = req_blen; + return 0; +} + +/* end of file mpa_io.c */ diff --git a/lib/libmpa/mpa_mem_static.c b/lib/libmpa/mpa_mem_static.c new file mode 100644 index 0000000..1debbb4 --- /dev/null +++ b/lib/libmpa/mpa_mem_static.c @@ -0,0 +1,177 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" +#include <util.h> +#include <trace.h> + +/* + * mpa_init_scratch_mem_sync + */ +void mpa_init_scratch_mem_sync(mpa_scratch_mem pool, size_t size, + uint32_t bn_bits, mpa_scratch_mem_sync_fn get, + mpa_scratch_mem_sync_fn put, + struct mpa_scratch_mem_sync *sync) +{ + pool->size = size; + pool->last_offset = 0; /* nothing is allocated yet in the pool */ + pool->bn_bits = bn_bits * 2; + pool->get = get; + pool->put = put; + pool->sync = sync; +} + +void mpa_init_scratch_mem(mpa_scratch_mem pool, size_t size, uint32_t bn_bits) +{ + mpa_init_scratch_mem_sync(pool, size, bn_bits, NULL, NULL, NULL); +} + +/* + * The allocation of the temporary Big Number is called when a temporary + * variable is used in Big Number computation: Big Number operations (add,...), + * crypto algorithms (rsa, ecc,,...) + * The allocation algorithm takes Big Numbers from a pool, characterized by + * (cf. struct mpa_scratch_mem_struct): + * - the total size (in bytes) of the pool + * - the default size (bits) of a big number that will be required + * it equals the max size of the computation (for example 4096 bits), + * multiplied by 2 to allow overflow in computation + * - the offset of the last Big Number item allocated in the pool + * (struct mpa_scratch_item). This offset is 0 is nothing is allocated yet. + * + * Each item consists of (struct mpa_scratch_item) + * - the size of the item + * - the offsets, in the pool, of the previous and next items + * + * The allocation allocates an item for a given size of Big Number. + * The allocation is performed in the pool after the last + * allocated items. This means: + * - the heap is never used. + * - there is no assumption on the size of the allocated Big Number. Only + * the size of the pool will limit the allocation. This allow to + * allocate "small" Big Numbers, such in ECC where we know they are + * less than 521 bits. + * - a constant time allocation and free as there is no list scan + * - but a potentially fragmented memory as the allocation does not take into + * account "holes" in the pool (allocation is performed after the last + * allocated variable). Indeed, this it does not happen to be an issue + * as the variables are used as temporary variables, that is + * - have a short life cycle + * - if a variable A is allocated before a variable B, then A should be + * released after B. + * So the potential fragmentation is mitigated. + */ +mpanum mpa_alloc_static_temp_var_size(int size_bits, mpanum *var, + mpa_scratch_mem pool) +{ + uint32_t offset; + size_t size; + struct mpa_scratch_item *new_item; + struct mpa_scratch_item *last_item = NULL; + + if (pool->get) + pool->get(pool->sync); + + if (!pool->last_offset) + offset = sizeof(struct mpa_scratch_mem_struct); + else { + offset = pool->last_offset; + last_item = (struct mpa_scratch_item *) + ((vaddr_t)pool + offset); + offset += last_item->size; + } + + offset = ROUNDUP(offset, sizeof(uint32_t)); + if (offset > pool->size) + goto error; + + size = sizeof(struct mpa_scratch_item) + + mpa_StaticVarSizeInU32(size_bits) * sizeof(uint32_t); + size = ROUNDUP(size, sizeof(uint32_t)); + if (offset + size > pool->size) + goto error; + + new_item = (struct mpa_scratch_item *)((vaddr_t)pool + offset); + new_item->size = size; + new_item->prev_item_offset = pool->last_offset; + if (last_item) + last_item->next_item_offset = offset; + new_item->next_item_offset = 0; + pool->last_offset = offset; + + *var = (mpanum)(new_item + 1); + mpa_init_static(*var, mpa_StaticVarSizeInU32(size_bits)); + return *var; + +error: + *var = 0; + if (pool->put) + pool->put(pool->sync); + return 0; +} + + +mpanum mpa_alloc_static_temp_var(mpanum *var, mpa_scratch_mem pool) +{ + return mpa_alloc_static_temp_var_size(pool->bn_bits, var, pool); +} + +/*------------------------------------------------------------ + * + * mpa_free_static_temp_var + * + */ +void mpa_free_static_temp_var(mpanum *var, mpa_scratch_mem pool) +{ + struct mpa_scratch_item *item; + struct mpa_scratch_item *prev_item; + struct mpa_scratch_item *next_item; + uint32_t last_offset = 0; + + if (!var || !(*var)) + return; + + item = (struct mpa_scratch_item *)((vaddr_t)(*var) - + sizeof(struct mpa_scratch_item)); + if (item->prev_item_offset) { + prev_item = (struct mpa_scratch_item *)((vaddr_t)pool + + item->prev_item_offset); + prev_item->next_item_offset = item->next_item_offset; + last_offset = item->prev_item_offset; + } + + if (item->next_item_offset) { + next_item = (struct mpa_scratch_item *)((vaddr_t)pool + + item->next_item_offset); + next_item->prev_item_offset = item->prev_item_offset; + last_offset = pool->last_offset; + } + + pool->last_offset = last_offset; + if (pool->put) + pool->put(pool->sync); +} + diff --git a/lib/libmpa/mpa_misc.c b/lib/libmpa/mpa_misc.c new file mode 100644 index 0000000..a7a996d --- /dev/null +++ b/lib/libmpa/mpa_misc.c @@ -0,0 +1,189 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * GLOBAL CONSTANTS + * + *************************************************************/ + +const mpa_num_base const_largest_deci_base = { + 1, 1, {LARGEST_DECIMAL_BASE_IN_WORD} }; +const mpa_num_base Const_1_LShift_Base = { 2, 2, {0, 1} }; +const mpa_num_base const_one = { 1, 1, {1} }; + +/************************************************************* + * + * HELPERS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: __mpa_set_unused_digits_to_zero + * + * + */ +void __mpa_set_unused_digits_to_zero(mpanum n) +{ + int i; + + /* + * Pointer arithmetics on *mpa_word_t will put the + * pointer at the right place. + */ + i = __mpanum_size(n); + mpa_memset((n->d) + i, 0, (n->alloc - i) * BYTES_PER_WORD); +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * mpa_wipe + * + * fills the digits with zero and set size = 0; + * + */ +void mpa_wipe(mpanum var) +{ + mpa_memset(var->d, 0, var->alloc * BYTES_PER_WORD); + var->size = 0; +} + +/*------------------------------------------------------------ + * + * mpa_copy + * + * Copies src to dest. + * + * Doesn't check if src fits into dest + * + */ +void mpa_copy(mpanum dest, const mpanum src) +{ + if (dest == src) + return; + + mpa_memcpy(dest->d, src->d, __mpanum_size(src) * BYTES_PER_WORD); + dest->size = src->size; +} + +/* -------------------------------------------------------------------- + * Function: mpa_abs + * Computes the absolut value of src and puts it in dest + * dest and src can be the same mpanum + */ +void mpa_abs(mpanum dest, const mpanum src) +{ + mpa_copy(dest, src); + __mpanum_set_sign(dest, MPA_POS_SIGN); +} + +/* -------------------------------------------------------------------- + * Function: mpa_highest_bit_index + * Returns the index of the highest 1 in |src|. + * The index starts at 0 for the least significant bit. + * If src == zero, it will return -1 + * + */ +int mpa_highest_bit_index(const mpanum src) +{ + mpa_word_t w; + mpa_word_t b; + + if (__mpanum_is_zero(src)) + return -1; + + w = __mpanum_msw(src); + + for (b = 0; b < WORD_SIZE; b++) { + w >>= 1; + if (w == 0) + break; + } + return (int)(__mpanum_size(src) - 1) * WORD_SIZE + b; +} + +/*------------------------------------------------------------ + * + * mpa_get_bit + * + * Returns the value of the idx:th bit in src. + * if idx is larger than the number of bits in src, + * it returns zero. + * + */ +uint32_t mpa_get_bit(const mpanum src, uint32_t idx) +{ + mpa_word_t w; /* word of bitIndex */ + unsigned long b; /* bit number in that word */ + + w = idx >> LOG_OF_WORD_SIZE; + b = idx & (WORD_SIZE - 1); + + if (w > __mpanum_size(src)) + return 0; + b = (1ul << b); + return ((src->d[w] & b) != 0); +} + +/*------------------------------------------------------------ + * + * mpa_CanHold + * + * returns 1 if dest can hold src without overflowing, 0 otherwise + */ +int mpa_can_hold(mpanum dest, const mpanum src) +{ + return (__mpanum_alloced(dest) >= __mpanum_size(src) ? 1 : 0); +} + +/*------------------------------------------------------------ + * + * mpa_parity + * + */ +int mpa_parity(const mpanum src) +{ + return (((__mpanum_lsw(src) & 0x01) == + 0) ? MPA_EVEN_PARITY : MPA_ODD_PARITY); +} + +/*------------------------------------------------------------ + * + * mpa_constant_one + * + */ +mpanum mpa_constant_one(void) +{ + return (mpanum)&const_one; +} diff --git a/lib/libmpa/mpa_modulus.c b/lib/libmpa/mpa_modulus.c new file mode 100644 index 0000000..5942942 --- /dev/null +++ b/lib/libmpa/mpa_modulus.c @@ -0,0 +1,144 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * mpa_mod + * + */ +void mpa_mod(mpanum dest, const mpanum op, const mpanum n, mpa_scratch_mem pool) +{ + mpa_div(NULL, dest, op, n, pool); +} + +/*------------------------------------------------------------ + * + * mpa_add_mod + * + */ +void mpa_add_mod(mpanum dest, + const mpanum op1, + const mpanum op2, const mpanum n, mpa_scratch_mem pool) +{ + mpanum tmp_dest; + + mpa_alloc_static_temp_var(&tmp_dest, pool); + + mpa_add(tmp_dest, op1, op2, pool); + mpa_div(NULL, dest, tmp_dest, n, pool); + + mpa_free_static_temp_var(&tmp_dest, pool); +} + +/*------------------------------------------------------------ + * + * mpa_sub_mod + * + */ +void mpa_sub_mod(mpanum dest, + const mpanum op1, + const mpanum op2, const mpanum n, mpa_scratch_mem pool) +{ + mpanum tmp_dest; + + mpa_alloc_static_temp_var(&tmp_dest, pool); + + mpa_sub(tmp_dest, op1, op2, pool); + mpa_div(NULL, dest, tmp_dest, n, pool); + + mpa_free_static_temp_var(&tmp_dest, pool); +} + +/*------------------------------------------------------------ + * + * mpa_mul_mod + * + */ +void mpa_mul_mod(mpanum dest, + const mpanum op1, + const mpanum op2, const mpanum n, mpa_scratch_mem pool) +{ + mpanum tmp_dest; + + mpa_alloc_static_temp_var(&tmp_dest, pool); + + mpa_mul(tmp_dest, op1, op2, pool); + mpa_div(NULL, dest, tmp_dest, n, pool); + + mpa_free_static_temp_var(&tmp_dest, pool); +} + +/*------------------------------------------------------------ + * + * mpa_inv_mod + * + */ +int mpa_inv_mod(mpanum dest, + const mpanum op, const mpanum n, mpa_scratch_mem pool) +{ + mpanum gcd; + mpanum tmp_dest; + int mem_marker; + int res; + + if (mpa_cmp_short(op, 1) == 0) { + mpa_set_S32(dest, 1); + return 0; + } + + mem_marker = (dest == op); + if (mem_marker) + mpa_alloc_static_temp_var(&tmp_dest, pool); + else + tmp_dest = dest; + + mpa_alloc_static_temp_var(&gcd, pool); + /* The function mpa_extended_gcd behaves badly if tmp_dest = op */ + mpa_extended_gcd(gcd, tmp_dest, NULL, op, n, pool); + res = mpa_cmp_short(gcd, 1); + + if (mem_marker) { + mpa_copy(dest, tmp_dest); + mpa_free_static_temp_var(&tmp_dest, pool); + } + + mpa_free_static_temp_var(&gcd, pool); + if (res == 0) { + while (mpa_cmp_short(dest, 0) < 0) + mpa_add(dest, dest, n, pool); + return 0; + } else { + return -1; + } +} diff --git a/lib/libmpa/mpa_montgomery.c b/lib/libmpa/mpa_montgomery.c new file mode 100644 index 0000000..ecea0fb --- /dev/null +++ b/lib/libmpa/mpa_montgomery.c @@ -0,0 +1,266 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * HELPERS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * These functions have ARM assembler implementations + * + */ +#if !defined(USE_ARM_ASM) + +/* -------------------------------------------------------------------- + * Function: __mpa_montgomery_mul_add + * Calculates dest = dest + src*w + * Dest must be big enough to hold the result + */ +void __mpa_montgomery_mul_add(mpanum dest, mpanum src, mpa_word_t w) +{ +#if defined(MPA_SUPPORT_DWORD_T) + mpa_dword_t a; + mpa_word_t *ddig; + int32_t idx; + mpa_word_t carry; + mpa_word_t *dest_begin; + + if (w == 0) + return; + dest_begin = dest->d; + ddig = dest->d; + carry = 0; + for (idx = 0; idx < src->size; idx++) { + a = (mpa_dword_t) *ddig + + (mpa_dword_t) src->d[idx] * (mpa_dword_t) w + + (mpa_dword_t) (carry); + *(ddig++) = (mpa_word_t) (a); + carry = (mpa_word_t) (a >> WORD_SIZE); + } + while (carry) { + a = (mpa_dword_t) (*ddig) + (mpa_dword_t) (carry); + *(ddig++) = (mpa_word_t) (a); + carry = (mpa_word_t) (a >> WORD_SIZE); + } + idx = (mpa_word_t) (ddig - dest_begin); + if (idx > dest->size) + dest->size = idx; + +#else +#error write non-dword code for __mpa_montgomery_mul_add +#endif +} + +/* -------------------------------------------------------------------- + * Function: __mpa_montgomery_sub_ack + * Calculates dest = dest - src + * Assumption: dest >= src and both non-negative + * and dest > src. + * + */ +void __mpa_montgomery_sub_ack(mpanum dest, mpanum src) +{ +#if defined(MPA_SUPPORT_DWORD_T) + mpa_word_t *ddig; + mpa_word_t carry; + int32_t idx; + mpa_dword_t a; + + ddig = dest->d; + carry = 0; + idx = 0; + while (idx < src->size) { + a = (mpa_dword_t) (*ddig) - (mpa_dword_t) src->d[idx] - + (mpa_dword_t) carry; + *(ddig++) = (mpa_word_t) (a); + carry = 0 - (mpa_word_t) (a >> WORD_SIZE); + idx++; + } + /* Here we have no more digits in op2, we only need to keep on + * subtracting 0 from op1, and deal with carry */ + while (carry) { + a = (mpa_dword_t) (*ddig) - (mpa_dword_t) carry; + *(ddig++) = (mpa_word_t) (a); + carry = 0 - (mpa_word_t) (a >> WORD_SIZE); + idx++; + } + if (idx >= dest->size) { + /* carry did propagate all the way, fix size */ + while (dest->size > 0 && *(--ddig) == 0) + dest->size--; + } +#else +#error write non-dword code for __mpa_montgomery_sub_ack +#endif +} + +#endif /* USE_ARM_ASM */ + +/*------------------------------------------------------------ + * + * __mpa_montgomery_mul + * + * NOTE: + * Dest need to be able to hold one more word than the size of n + * + */ +void __mpa_montgomery_mul(mpanum dest, mpanum op1, mpanum op2, mpanum n, + mpa_word_t n_inv) +{ + mpa_word_t u; + mpa_usize_t idx; + + /* set dest to zero (with all unused digits to zero as well) */ + mpa_wipe(dest); + + for (idx = 0; idx < n->size; idx++) { + u = (dest->d[0] + + __mpanum_get_word(idx, op1) * + __mpanum_get_word(0, op2)) * n_inv; + + __mpa_montgomery_mul_add(dest, op2, + __mpanum_get_word(idx, op1)); + __mpa_montgomery_mul_add(dest, n, u); + + /* Shift right one mpa_word */ + dest->size--; + for (mpa_usize_t i = 0; i < dest->size; i++) + dest->d[i] = dest->d[i + 1]; + *(dest->d + dest->size) = 0; /* set unused digit to zero. */ + } + + /* check if dest > n, if so set dest = dest - n */ + if (__mpa_abs_cmp(dest, n) >= 0) + __mpa_montgomery_sub_ack(dest, n); +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/* + * mpa_compute_fmm_context + */ +int mpa_compute_fmm_context(const mpanum modulus, + mpanum r_modn, + mpanum r2_modn, + mpa_word_t *n_inv, + mpa_scratch_mem pool) +{ + mpa_usize_t s; + int cmpresult; + mpanum tmp_n_inv; + mpanum gcd; + + /* create a small mpanum on the stack */ + uint32_t n_lsw_u32[MPA_NUMBASE_METADATA_SIZE_IN_U32 + ASIZE_TO_U32(1)]; + mpanum n_lsw = (void *)n_lsw_u32; + + /* + * compute r to be + * 1 << (__mpanum_size(Modulus) * WORD_SIZE) mod modulus + */ + s = __mpanum_size(modulus); + mpa_set_word(r_modn, 1); + mpa_shift_left(r_modn, r_modn, s * WORD_SIZE); + mpa_mod(r_modn, r_modn, modulus, pool); + + /* compute r^2 mod modulus */ + mpa_mul_mod(r2_modn, r_modn, r_modn, modulus, pool); + + /* Compute the inverse of modulus mod 1 << WORD_SIZE */ + n_lsw->alloc = 1; + n_lsw->size = 1; + n_lsw->d[0] = __mpanum_lsw(modulus); + + mpa_alloc_static_temp_var(&tmp_n_inv, pool); + mpa_alloc_static_temp_var(&gcd, pool); + + mpa_extended_gcd(gcd, tmp_n_inv, NULL, n_lsw, + (const mpanum)&Const_1_LShift_Base, pool); + cmpresult = mpa_cmp_short(gcd, 1); + + if (cmpresult != 0) + goto cleanup; + + /* + * We need the number n' (n_inv) such that + * + * R*r' - N*n' == 1 + * + * and Extended_GCD gives us the solution to + * + * R*r' + N*n' == 1 + * + * So if n' is negative, we just forget about the sign. + * If n' is positive, we need to subtract R to get + * the right residue class. + */ + if (__mpanum_sign(tmp_n_inv) == MPA_POS_SIGN) { + mpa_sub(tmp_n_inv, tmp_n_inv, + (const mpanum)&Const_1_LShift_Base, pool); + } + /* then take the absolute value */ + *n_inv = __mpanum_lsw(tmp_n_inv); + +cleanup: + + mpa_free_static_temp_var(&gcd, pool); + mpa_free_static_temp_var(&tmp_n_inv, pool); + + if (cmpresult != 0) + return -1; + return 0; +} + +/*------------------------------------------------------------ + * + * mpa_montgomery_mul + * + * wrapper that uses a temp variables for dest, since + * that need to be one word larger that n. + */ +void mpa_montgomery_mul(mpanum dest, + mpanum op1, + mpanum op2, + mpanum n, mpa_word_t n_inv, mpa_scratch_mem pool) +{ + mpanum tmp_dest; + + mpa_alloc_static_temp_var(&tmp_dest, pool); + + __mpa_montgomery_mul(tmp_dest, op1, op2, n, n_inv); + + mpa_copy(dest, tmp_dest); + mpa_free_static_temp_var(&tmp_dest, pool); +} diff --git a/lib/libmpa/mpa_mul.c b/lib/libmpa/mpa_mul.c new file mode 100644 index 0000000..4875f08 --- /dev/null +++ b/lib/libmpa/mpa_mul.c @@ -0,0 +1,228 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * HELPERS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * These functions have ARM assembler implementations + * + */ +#if !defined(USE_ARM_ASM) + +/* -------------------------------------------------------------------- + * Function: __mpa_mul_add_word + * + * Multiplies a and b and adds the incoming carry to produce the product p + * outgoing carry is stored in *carry. + */ +void __mpa_mul_add_word(mpa_word_t a, + mpa_word_t b, mpa_word_t *p, mpa_word_t *carry) +{ +#if defined(MPA_SUPPORT_DWORD_T) + mpa_dword_t prod; + + prod = (mpa_dword_t) (a) * (mpa_dword_t) (b) + (mpa_dword_t) (*carry); + *p = (mpa_word_t) prod; + *carry = (mpa_word_t) (prod >> MPA_WORD_SIZE); +#else +#error "error, write non-dword_t code for __mpa_mul_add_word" +#endif +} + +/* -------------------------------------------------------------------- + * Function: __mpa_mul_add_word_cum + * + * Multiplies a and b and adds the incoming carry and the cumulative + * product stored in *p. + * Outgoing carry is stored in *carry. + */ +void __mpa_mul_add_word_cum(mpa_word_t a, + mpa_word_t b, mpa_word_t *p, mpa_word_t *carry) +{ +#if defined(MPA_SUPPORT_DWORD_T) + mpa_dword_t prod; + + prod = + (mpa_dword_t) (a) * (mpa_dword_t) (b) + (mpa_dword_t) (*p) + + (mpa_dword_t) (*carry); + *p = (mpa_word_t) prod; + *carry = (mpa_word_t) (prod >> MPA_WORD_SIZE); +#else +#error "error: write non-dword_t code for __mpa_mul_add_word_cum" +#endif +} + +#endif /* USE_ARM_ASM */ + +/* -------------------------------------------------------------------- + * Function: __mpa_abs_mul_word + * + * Simpler multiplication when one operand is known to be a word. + * Calculates |op1| * op2, op2 is always positive (larger than zero). + * Dest needs to be distinct from op1. + */ +void __mpa_abs_mul_word(mpanum dest, const mpanum op1, mpa_word_t op2) +{ + mpa_word_t i; + mpa_word_t carry; + mpa_word_t *prod; + const mpa_word_t *a; + + /* clear dest digits */ + mpa_memset(dest->d, 0, dest->alloc * BYTES_PER_WORD); + + a = op1->d; + prod = dest->d; + carry = 0; + for (i = 0; i < __mpanum_size(op1); i++) { + __mpa_mul_add_word(*a, op2, prod + i, &carry); + a++; + } + dest->size = i; + if (carry) { + *(prod + i) = carry; + dest->size++; + } +} + +/* -------------------------------------------------------------------- + * Function: __mpa_abs_mul + * + * Calculates |op1| * |op2| and puts result in dest. + * dest must be big enough to hold result and cannot be + * the same as op1 or op2. + */ +void __mpa_abs_mul(mpanum dest, const mpanum op1, const mpanum op2) +{ + mpa_word_t i = 0; + mpa_word_t j = 0; + mpa_word_t carry = 0; + mpa_word_t *prod; + const mpa_word_t *a; + const mpa_word_t *b; + + /* clear dest digits */ + mpa_memset(dest->d, 0, dest->alloc * BYTES_PER_WORD); + + a = op1->d; + prod = dest->d; + for (i = 0; i < __mpanum_size(op1); i++) { + b = op2->d; + carry = 0; + for (j = 0; j < __mpanum_size(op2); j++) { + __mpa_mul_add_word_cum(*a, *b, prod + j, &carry); + b++; + } + if (carry) + *(prod + j) = carry; + a++; + prod++; + } + dest->size = i + j - 1; + if (carry) + dest->size++; +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * Function: mpa_mul + * + * dest = op1 * op2 + */ +void mpa_mul(mpanum dest, + const mpanum op1, const mpanum op2, mpa_scratch_mem pool) +{ + mpanum tmp_dest; + char mem_marker; + + if (__mpanum_is_zero(op1) || __mpanum_is_zero(op2)) { + mpa_set_word(dest, 0); + return; + } + + /* handle the case when dest is one of the operands */ + mem_marker = (dest == op1 || dest == op2); + if (mem_marker) + mpa_alloc_static_temp_var(&tmp_dest, pool); + else + tmp_dest = dest; + + __mpa_abs_mul(tmp_dest, op1, op2); + + if (__mpanum_sign(op1) != __mpanum_sign(op2)) + __mpanum_neg(tmp_dest); + + mpa_copy(dest, tmp_dest); + if (mem_marker) + mpa_free_static_temp_var(&tmp_dest, pool); +} + +/* -------------------------------------------------------------------- + * Function: mpa_mul_word + * + * Calculates op1 * op2, where op2 is a word, puts result in dest. + */ +void mpa_mul_word(mpanum dest, + const mpanum op1, mpa_word_t op2, mpa_scratch_mem pool) +{ + int sign_1; + mpanum tmp_dest; + char mem_marker; + + if (__mpanum_is_zero(op1) || op2 == 0) { + mpa_set_word(dest, 0); + return; + } + + sign_1 = __mpanum_sign(op1); + + /* handle the case when dest is the operand */ + mem_marker = (dest == op1); + if (mem_marker) + mpa_alloc_static_temp_var(&tmp_dest, pool); + else + tmp_dest = dest; + + __mpa_abs_mul_word(tmp_dest, op1, op2); + + if (sign_1 == MPA_NEG_SIGN) + __mpanum_neg(tmp_dest); + mpa_copy(dest, tmp_dest); + if (mem_marker) + mpa_free_static_temp_var(&tmp_dest, pool); +} diff --git a/lib/libmpa/mpa_primetable.h b/lib/libmpa/mpa_primetable.h new file mode 100644 index 0000000..38c0616 --- /dev/null +++ b/lib/libmpa/mpa_primetable.h @@ -0,0 +1,242 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef GUARD_PRIMETABLE_H +#define GUARD_PRIMETABLE_H + +#include <stdint.h> + +/* Primes Number Table + * All numbers up to 49999 are represented + * by a bit in the following array. + * A 0 means composite and a 1 mean a prime. + * For an odd number 3<= n <= 49999 we can find out + * if n is a prime by doing: + * n = (n-3)>>1; + * IsPrime = (PRIME_TABLE[n>>5] >> (n & 0x1f)) & 0x1) == 1; + * E.i., the primality of each odd number is stored as a bit. + */ +const uint32_t MAX_TABULATED_PRIME = 49999; +const uint32_t NR_STORED_PRIMES = 5133; +const uint32_t PRIME_TABLE[782] = { + 0x325a65b7, 0x40b6894d, 0xc3252619, 0x90cb4106, 0x2d021a64, 0x5244b090, + 0x94c308a2, 0x25144168, + 0x99212018, 0x841a4c90, 0x21128325, 0x8a452442, 0x36182102, 0x05a05a04, + 0x09288450, 0x32824494, + 0x4026184c, 0xc009224b, 0xa0892110, 0x60108264, 0x004c1699, 0x84022480, + 0x41344b40, 0x110412d8, + 0xa05144a4, 0x4802132c, 0x1821a003, 0x34804922, 0x04044108, 0x092086d2, + 0x12006030, 0x04309169, + 0xc10d8242, 0x00886980, 0x60225001, 0x0a48b011, 0x02532006, 0x04904a69, + 0x0029104a, 0x26510804, + 0x2880c100, 0xd2458408, 0xa2184d12, 0x01a60840, 0x40291281, 0x10422484, + 0x0c001928, 0x1208a051, + 0x80c20094, 0x0520d000, 0x1b002289, 0x94930004, 0x6030c141, 0x88080240, + 0x24110036, 0x6106132c, + 0x1244a408, 0x22902c10, 0x0c801244, 0x08601281, 0x008a0434, 0x40141965, + 0x13258200, 0x30480980, + 0x6812c041, 0x19080080, 0x90c32186, 0x21840008, 0x08240212, 0x80494806, + 0x00169021, 0x12440483, + 0x84996020, 0x29804104, 0xcb400440, 0x200040a0, 0x04240824, 0x902c244b, + 0x10406194, 0x49304a01, + 0x11409000, 0x02d00822, 0x2480c820, 0x00050210, 0xa41a4492, 0x60164009, + 0x920014c1, 0x04000422, + 0x29021b4c, 0x02680242, 0x22484500, 0x0c329941, 0x81050048, 0x14012000, + 0x49025220, 0x43088218, + 0x16002104, 0x64840229, 0x89243042, 0x22124c84, 0x01801200, 0x8800108a, + 0x02990d00, 0x20201044, + 0x42618483, 0x301800a0, 0x08b4010c, 0x51010648, 0x94c30002, 0x41120a44, + 0x40042081, 0x04400c82, + 0x21340908, 0x81000252, 0x06030830, 0x09008008, 0xca019008, 0x32892110, + 0x05064a0c, 0x8a009402, + 0x20520514, 0x00a00068, 0x90208248, 0xa4412016, 0x08001060, 0x12040098, + 0x12422c82, 0x41148100, + 0x012c3080, 0x240b40a4, 0x08908008, 0x50650003, 0x82000120, 0x21005848, + 0x83408602, 0x128a2404, + 0x08929049, 0x43050050, 0x24016086, 0x04229000, 0x034c0019, 0x00110982, + 0x40a40241, 0x0941220a, + 0xa0080c12, 0x68144021, 0x12409002, 0x96006c32, 0x20840904, 0x81000051, + 0x20906520, 0x0c008860, + 0x520c0252, 0x904a0910, 0x01205041, 0x02402219, 0x06000c00, 0x45304320, + 0x89443200, 0x00410082, + 0x6080d125, 0x8204b088, 0xb0004400, 0x04205a00, 0x40018083, 0x024a2004, + 0x40149045, 0x81290601, + 0x00422100, 0x01324240, 0x18002419, 0x10912022, 0x61840100, 0x10680250, + 0x200b0c20, 0x29140020, + 0x8a410448, 0x84080c00, 0x05204104, 0x40499050, 0x10006004, 0x00828029, + 0x0308a008, 0x80004106, + 0x4d224825, 0x48401400, 0x84832502, 0x00140121, 0x800c009a, 0xa24004b2, + 0x01120001, 0x8a2430c1, + 0x14090020, 0x28841a00, 0x48090282, 0x30424494, 0x08248809, 0x4124a013, + 0x00884880, 0x44201205, + 0x02082608, 0x16512800, 0x05244820, 0x092800d8, 0x82520004, 0x49145004, + 0x88218001, 0xa0900110, + 0x04001940, 0x80290602, 0x10422490, 0x40808108, 0x91202408, 0xb4c20080, + 0x64009860, 0x00442201, + 0x16810086, 0x00308960, 0x18600050, 0x840900a0, 0x40001005, 0x4200a04a, + 0x00190020, 0x05804208, + 0x83008012, 0x20c24514, 0x04040840, 0xc001a64a, 0xa04b2000, 0x28101020, + 0x51449291, 0x10522020, + 0x00944301, 0x08251090, 0x040a0004, 0x21128220, 0x08219081, 0x90804902, + 0x0c265008, 0xc2018491, + 0x020844a0, 0x00921141, 0x4204040a, 0x04806084, 0x4520d821, 0x1b400001, + 0x92502482, 0x01000048, + 0x814920ca, 0x84030400, 0x68008004, 0x4044940b, 0xb4000030, 0x28064800, + 0x40200090, 0x20982120, + 0x40929000, 0x0024a003, 0x24890084, 0x0c105000, 0x53008298, 0x14120800, + 0x64100100, 0x09440010, + 0x00494806, 0x21009301, 0x0200248b, 0x00812112, 0x0d064044, 0x00080440, + 0x224a0130, 0x08b48044, + 0x50090418, 0x00420992, 0x60328041, 0x18001408, 0x80900182, 0x64008308, + 0x10610040, 0x86410804, + 0x29060109, 0xd8002003, 0x00882030, 0x0802434c, 0x0a490442, 0x20c020b0, + 0x4082080d, 0x9020a011, + 0x20802914, 0x08301a04, 0x08009400, 0x04420020, 0x24104821, 0x01290202, + 0x02100400, 0x0006c100, + 0x88012041, 0xa0102402, 0x0080004c, 0x00601203, 0x10824134, 0x04220809, + 0x53200002, 0x848b6810, + 0x01209264, 0x49048610, 0x00000920, 0x21848020, 0x814c1042, 0x80120880, + 0x01801221, 0x18208448, + 0x26102c12, 0x08044140, 0x83409292, 0x100804a0, 0x4022080c, 0x92250008, + 0x144a0086, 0x60001840, + 0x42083001, 0x04800106, 0x0400c101, 0x10610208, 0x020304b4, 0x0880000c, + 0x88058448, 0x06014110, + 0x00045b08, 0x81208013, 0x10922500, 0x4012100d, 0x80012200, 0x80012016, + 0x08104a45, 0x53481000, + 0x960009a0, 0x00b0c308, 0x010820c0, 0x24184082, 0x28141024, 0x084510c0, + 0x04880402, 0x21240808, + 0x49410650, 0x02906030, 0x00a01069, 0xc1040200, 0x00014116, 0x2420c024, + 0x02488008, 0x00420182, + 0x00340261, 0x11603200, 0xa2190420, 0x48804304, 0x00009401, 0x12002432, + 0x21804808, 0xc3291080, + 0x104845a0, 0x44041020, 0x1009a202, 0xb0420100, 0x20124840, 0x08040018, + 0x00810404, 0x21900208, + 0x0948205a, 0x264000b4, 0x6004000c, 0x08202489, 0xa0800d12, 0x08261244, + 0x88290200, 0x20902504, + 0x08b49124, 0x0308040a, 0x14424012, 0x20000800, 0x13040088, 0x14032404, + 0x21008a00, 0x10050242, + 0x04410080, 0x09124100, 0x50202002, 0x02084820, 0x08201148, 0x08401610, + 0x02002194, 0x4080802c, + 0x9004a408, 0x00024190, 0x00225221, 0x50083600, 0x80402422, 0x64a44041, + 0x81000000, 0x82580802, + 0x08148209, 0x02042049, 0x80114122, 0x0c80100c, 0x48408090, 0x20804530, + 0x08228160, 0xd1010002, + 0x90882004, 0x21009024, 0x0a001618, 0x021100a2, 0x44844901, 0x88401082, + 0xa0100082, 0x00024020, + 0x58200489, 0x00992c32, 0x20804804, 0xc0608482, 0x00480430, 0x0092004d, + 0x93010409, 0x04034102, + 0x24100004, 0x120c0010, 0x800101a4, 0x00048008, 0x882500c2, 0x02004c00, + 0x6000430c, 0x40409000, + 0x02980802, 0x25065a00, 0x014894c1, 0x22100014, 0x48960060, 0x5100a040, + 0x84820900, 0x04001061, + 0x11080601, 0x96000002, 0x60004308, 0x19090000, 0x204044a0, 0x28028120, + 0x52413043, 0x26890530, + 0x09044840, 0x0a0104c0, 0x101200a4, 0x48220045, 0x01008202, 0x00096880, + 0x00200205, 0x12409099, + 0x10420c84, 0x44840201, 0x01011240, 0x22410c34, 0x20108021, 0xc0009400, + 0xa0104122, 0x01064008, + 0xc8201200, 0x10102000, 0x0c941028, 0x1004a000, 0x30024004, 0x04104020, + 0x1a04a498, 0x12120880, + 0x61208041, 0x01490200, 0x06004012, 0x00805001, 0x8220b003, 0x80806810, + 0x09240000, 0x09488242, + 0x22120004, 0x0c208900, 0x40208613, 0x90022900, 0x48120004, 0x010c2410, + 0x04d10180, 0x45000a68, + 0x002512c2, 0x200a4c10, 0x0002d100, 0x8a200000, 0x16102c00, 0x04804240, + 0x01489010, 0x20d80104, + 0x04801804, 0x810c0008, 0x00010110, 0x04221200, 0x59003009, 0x06010922, + 0x64204060, 0x90280210, + 0x82580002, 0x29948205, 0x18243080, 0x14904100, 0x29800b00, 0x08219011, + 0x02400024, 0x00200069, + 0xc001a251, 0x04020014, 0x20320260, 0x42049418, 0x10c02822, 0x60004901, + 0x11443008, 0x00004004, + 0x4182420c, 0x9040804b, 0x22800102, 0x28804244, 0xc3289010, 0x004a25a0, + 0x08840040, 0x402c2610, + 0x90030182, 0x04028044, 0x00480291, 0x04c10020, 0x00000028, 0x106120d0, + 0x040b0004, 0x68109320, + 0xc8408448, 0x22010020, 0x05060804, 0x024804c3, 0x02506400, 0x44901804, + 0x11088042, 0x04002016, + 0x2400d801, 0x10048081, 0x00020182, 0x21300140, 0x08251098, 0x800104a2, + 0x09001200, 0x524010c1, + 0x82010810, 0x0c205048, 0x83010002, 0x028004b4, 0x0000812c, 0x00002400, + 0x10490180, 0x64009a00, + 0x18042410, 0x90402104, 0x00b44848, 0x81092002, 0x84090030, 0x08805000, + 0x02241082, 0x86004912, + 0x00024200, 0x4b090080, 0x20d000a0, 0x44141144, 0x40212200, 0x008a0912, + 0x0d304821, 0x08408208, + 0x94830424, 0x01200141, 0x88403212, 0x20084002, 0x21040101, 0x100480c2, + 0xb0002802, 0x09a01808, + 0x80408201, 0x22900404, 0x48308825, 0x81040613, 0x30004890, 0x01000201, + 0x03040600, 0x84422404, + 0x40000108, 0x102d0052, 0x02024400, 0x00048001, 0x0a24840a, 0x82006410, + 0x2ca05048, 0x08090040, + 0x32c04000, 0x00020000, 0x800ca040, 0x30420190, 0x0d120260, 0x40403089, + 0x04820104, 0x04100921, + 0x9048021a, 0x80500080, 0x48840005, 0x1a012049, 0xb0884420, 0x2000010c, + 0x40601282, 0x10820434, + 0x00021140, 0x42008650, 0x04002090, 0x45100045, 0x02442400, 0x04410882, + 0x2484c320, 0x88002052, + 0x02510080, 0x40064028, 0xd0412400, 0xa0890c00, 0x20a40200, 0x00009200, + 0x000a4400, 0x00b40001, + 0x11250410, 0x80404184, 0x61008244, 0x1a000000, 0x14410002, 0x25208101, + 0x814102c8, 0x82124004, + 0x49008020, 0x0a009440, 0x26102800, 0x21825808, 0x824810d2, 0x22000100, + 0x04320024, 0x10210003, + 0x00c90104, 0x28100025, 0x11481299, 0x84000482, 0x0090c008, 0x19000288, + 0x044a4404, 0x60869204, + 0x1005a040, 0x02090c20, 0x08201100, 0x41608293, 0x12180080, 0x04209101, + 0x800d2412, 0x14096912, + 0x20020021, 0x01002098, 0x92100980, 0x44844268, 0x00290240, 0x00520c22, + 0x48900300, 0x10210488, + 0x14182012, 0x20204200, 0x82080440, 0x20020404, 0x0c801104, 0x40000001, + 0x90810116, 0x20104800, + 0x1a000600, 0x80902c24, 0x40100221, 0x8048000a, 0x000008b6, 0x01801020, + 0x98442008, 0x32802502, + 0x0c041208, 0x40019442, 0x20582110, 0x0cb48800, 0x40000002, 0x80026102, + 0x00028000, 0x4b041291, + 0x00110102, 0x00948868, 0x08043050, 0x220b0082, 0x01140108, 0x42202441, + 0x14114810, 0x20000240, + 0xc0001202, 0x30080194, 0x40800024, 0x10288050, 0x80806886, 0x49021020, + 0x49080000, 0x82822100, + 0x40204300, 0x90291008, 0x24080010, 0x68000105, 0x40242089, 0xa4000002, + 0x00021104, 0x08218012, + 0x22000530, 0x04161009, 0xc2002210, 0x84032004, 0x40200060, 0x094c0010, + 0x10510824, 0x60244200, + 0x09481008, 0x00414c04, 0x01825005, 0x00619400, 0x02082122, 0x00200204, + 0x80080280, 0x02400190, + 0x08348944, 0x02040200, 0xa4420102, 0x0c100224, 0x18403201, 0x00010084, + 0x04248929, 0x08442090, + 0x801a0424, 0x6802c300, 0xc2418000, 0x20812010, 0x20244008, 0x00289051, + 0x00802480, 0x0c201048, + 0x91012001, 0x04402002, 0x0c100841, 0x41008280, 0x82002c20, 0x0094c840, + 0x11003250, 0x005100a0, + 0x0006820c, 0x4a403000, 0x06884130, 0x09061840, 0x09000010, 0x10906020, + 0x0820812c, 0x0101a240, + 0x14c80982, 0x60220004, 0x13001080, 0x80c00d00, 0x05100a09, 0x9900100a, + 0x20000430, 0x40049021, + 0x40408083, 0x34002130, 0x21044148, 0xc0010240, 0x00020584, 0x0000004c +}; + +#endif /* include guard */ diff --git a/lib/libmpa/mpa_primetest.c b/lib/libmpa/mpa_primetest.c new file mode 100644 index 0000000..f8d67fa --- /dev/null +++ b/lib/libmpa/mpa_primetest.c @@ -0,0 +1,291 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +#define USE_PRIME_TABLE + +#if defined(USE_PRIME_TABLE) +#include "mpa_primetable.h" +#endif + +#define DEF_COMPOSITE 0 +#define DEF_PRIME 1 +#define PROB_PRIME -1 + +/* Product of all primes < 1000 */ +static const mpa_num_base const_small_prime_factors = { + 44, + 44, + {0x2ED42696, 0x2BBFA177, 0x4820594F, 0xF73F4841, + 0xBFAC313A, 0xCAC3EB81, 0xF6F26BF8, 0x7FAB5061, + 0x59746FB7, 0xF71377F6, 0x3B19855B, 0xCBD03132, + 0xBB92EF1B, 0x3AC3152C, 0xE87C8273, 0xC0AE0E69, + 0x74A9E295, 0x448CCE86, 0x63CA1907, 0x8A0BF944, + 0xF8CC3BE0, 0xC26F0AF5, 0xC501C02F, 0x6579441A, + 0xD1099CDA, 0x6BC76A00, 0xC81A3228, 0xBFB1AB25, + 0x70FA3841, 0x51B3D076, 0xCC2359ED, 0xD9EE0769, + 0x75E47AF0, 0xD45FF31E, 0x52CCE4F6, 0x04DBC891, + 0x96658ED2, 0x1753EFE5, 0x3AE4A5A6, 0x8FD4A97F, + 0x8B15E7EB, 0x0243C3E1, 0xE0F0C31D, 0x0000000B} +}; + +/* + * If n is less than this number (341550071728321 decimal) the Miller-Rabin + * test (using specific bases) constitutes a primality proof. + */ +static const mpa_num_base const_miller_rabin_proof_limit = { + 2, + 2, + {0x52B2C8C1, 0x000136A3} +}; + +static const mpa_num_base const_two = { + 1, + 1, + {0x00000002} +}; + +/* foward declarations */ +static int is_small_prime(mpanum n); +static int has_small_factors(mpanum n, mpa_scratch_mem pool); +static int primality_test_miller_rabin(mpanum n, int conf_level, + mpa_scratch_mem pool); + +/*------------------------------------------------------------ + * + * mpa_is_prob_prime + * + * Returns: + * 0 if n is definitely composite + * 1 if n is definitely prime + * -1 if n is composite with a probability less than 2^(-conf_level) + * + */ +int mpa_is_prob_prime(mpanum n, int conf_level, mpa_scratch_mem pool) +{ + int result = 0; + + /* Check if it's a small prime */ + result = is_small_prime(n); + if (result != PROB_PRIME) + goto cleanup; + + /* Test if n is divisible by any prime < 1000 */ + if (has_small_factors(n, pool)) { + result = DEF_COMPOSITE; + goto cleanup; + } + /* Check with Miller Rabin */ + result = primality_test_miller_rabin(n, conf_level, pool); + +cleanup: + return result; +} + +#if defined(USE_PRIME_TABLE) +/*------------------------------------------------------------ + * + * check_table + * + */ +static uint32_t check_table(uint32_t v) +{ + return (PRIME_TABLE[v >> 5] >> (v & 0x1f)) & 1; +} +#endif + +/*------------------------------------------------------------ + * + * is_small_prime + * + * Returns 1 if n is prime, + Returns 0 if n is composite + * Returns -1 if we cannot decide + * + */ +static int is_small_prime(mpanum n) +{ + mpa_word_t v; + + /* If n is larger than a mpa_word_t, we can only decide if */ + /* n is even. If it's odd we cannot tell. */ + if (__mpanum_size(n) > 1) + return ((mpa_parity(n) == MPA_EVEN_PARITY) ? 0 : -1); + + v = mpa_get_word(n); /* will convert negative n:s to positive v:s. */ + if ((v | 1) == 1) /* 0 and 1 are not prime */ + return DEF_COMPOSITE; + if (v == 2) /* 2 is prime */ + return DEF_PRIME; + if ((v & 1) == 0) + return DEF_COMPOSITE; /* but no other even number */ + +#if defined(USE_PRIME_TABLE) + if (mpa_cmp_short(n, MAX_TABULATED_PRIME) > 0) + return -1; + v = (v - 3) >> 1; + return check_table(v); +#else + return -1; +#endif +} + +/*------------------------------------------------------------ + * + * has_small_factors + * + * returns 1 if n has small factors + * returns 0 if not. + */ +static int has_small_factors(mpanum n, mpa_scratch_mem pool) +{ + const mpa_num_base *factors = &const_small_prime_factors; + int result; + mpanum res; + + mpa_alloc_static_temp_var(&res, pool); + mpa_gcd(res, n, (const mpanum)factors, pool); + result = (mpa_cmp_short(res, 1) == 0) ? 0 : 1; + mpa_free_static_temp_var(&res, pool); + + return result; +} + +/*------------------------------------------------------------ + * + * primality_test_miller_rabin + * + */ +static int primality_test_miller_rabin(mpanum n, int conf_level, + mpa_scratch_mem pool) +{ + int result; + bool proof_version; + static const int32_t proof_a[7] = { 2, 3, 5, 7, 11, 13, 17 }; + int cnt; + int idx; + int t; + int e = 0; + int cmp_one; + mpanum a; + mpanum q; + mpanum n_minus_1; + mpanum b; + mpanum r_modn; + mpanum r2_modn; + mpa_word_t n_inv; + + mpa_alloc_static_temp_var(&r_modn, pool); + mpa_alloc_static_temp_var(&r2_modn, pool); + + if (mpa_compute_fmm_context(n, r_modn, r2_modn, &n_inv, pool) == -1) { + result = DEF_COMPOSITE; + goto cleanup_short; + } + + mpa_alloc_static_temp_var(&a, pool); + mpa_alloc_static_temp_var(&q, pool); + mpa_alloc_static_temp_var(&n_minus_1, pool); + mpa_alloc_static_temp_var(&b, pool); + + proof_version = + (mpa_cmp(n, (mpanum) &const_miller_rabin_proof_limit) < 0); + + if (proof_version) + cnt = 7; + else /* MR has 1/4 chance in failing a composite */ + cnt = (conf_level + 1) / 2; + + mpa_sub_word(n_minus_1, n, 1, pool); + mpa_set(q, n_minus_1); + t = 0; + /* calculate q such that n - 1 = 2^t * q where q is odd */ + while (mpa_is_even(q)) { + mpa_shift_right(q, q, 1); + t++; + } + + result = PROB_PRIME; + for (idx = 0; idx < cnt && result == PROB_PRIME; idx++) { + if (proof_version) { + mpa_set_S32(a, proof_a[idx]); + if (mpa_cmp(n, a) == 0) { + result = DEF_PRIME; + continue; + } + } else { + /* + * Get random a, 1 < a < N by + * asking for a random in range 0 <= x < N - 2 + * and then add 2 to it. + */ + mpa_sub_word(n_minus_1, n_minus_1, 1, pool); + /* n_minus_1 is now N - 2 ! */ + mpa_get_random(a, n_minus_1); + mpa_add_word(n_minus_1, n_minus_1, 1, pool); + /* and a is now 2 <= a < N */ + mpa_add_word(a, a, 2, pool); + } + + mpa_exp_mod(b, a, q, n, r_modn, r2_modn, n_inv, pool); + e = 0; + +inner_loop: + cmp_one = mpa_cmp_short(b, 1); + if ((cmp_one == 0) && (e > 0)) { + result = DEF_COMPOSITE; + continue; + } + + if ((mpa_cmp(b, n_minus_1) == 0) || + ((cmp_one == 0) && (e == 0))) { + /* probably prime, try another a */ + continue; + } + + e++; + if (e < t) { + mpa_exp_mod(b, b, (mpanum) &const_two, n, r_modn, + r2_modn, n_inv, pool); + goto inner_loop; + } + result = DEF_COMPOSITE; + } + + if (result == PROB_PRIME && proof_version) + result = DEF_PRIME; + + mpa_free_static_temp_var(&a, pool); + mpa_free_static_temp_var(&q, pool); + mpa_free_static_temp_var(&n_minus_1, pool); + mpa_free_static_temp_var(&b, pool); +cleanup_short: + mpa_free_static_temp_var(&r_modn, pool); + mpa_free_static_temp_var(&r2_modn, pool); + + return result; +} diff --git a/lib/libmpa/mpa_random.c b/lib/libmpa/mpa_random.c new file mode 100644 index 0000000..2ee0031 --- /dev/null +++ b/lib/libmpa/mpa_random.c @@ -0,0 +1,81 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" +#include <tee_api_types.h> + +static random_generator_cb get_rng_array; + +void mpa_set_random_generator(random_generator_cb callback) +{ + get_rng_array = callback; +} + +static uint8_t get_random_byte(void) +{ + uint8_t buf; + while (get_rng_array(&buf, 1) != TEE_SUCCESS) + ; + + return buf; +} + +/*------------------------------------------------------------ + * + * mpa_get_random + * + */ +void mpa_get_random(mpanum dest, mpanum limit) +{ + int done = 0; + + mpa_wipe(dest); + if (__mpanum_alloced(dest) < __mpanum_size(limit)) + dest->size = __mpanum_alloced(dest); + else + dest->size = __mpanum_size(limit); + while (!done) { + for (int idx = 0; idx < dest->size; idx++) { + mpa_word_t w = 0; + for (int j = 0; j < BYTES_PER_WORD; j++) + w = (w << 8) ^ get_random_byte(); + dest->d[idx] = w; + } + if (dest->size < __mpanum_size(limit)) { + done = 1; + } else { + mpa_word_t hbi = + (mpa_word_t) mpa_highest_bit_index(limit); + /* 1 <= hbi <= WORD_SIZE */ + hbi = (hbi % WORD_SIZE) + 1; + if (hbi < WORD_SIZE) { + hbi = (1 << hbi) - 1; + dest->d[dest->size - 1] &= hbi; + } + done = (mpa_cmp(dest, limit) < 0) ? 1 : 0; + } + } +} diff --git a/lib/libmpa/mpa_shift.c b/lib/libmpa/mpa_shift.c new file mode 100644 index 0000000..0d64910 --- /dev/null +++ b/lib/libmpa/mpa_shift.c @@ -0,0 +1,237 @@ +/* + * Copyright (c) 2014, STMicroelectronics International N.V. + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + */ +#include "mpa.h" + +/************************************************************* + * + * HELPER FUNCTIONS + * + *************************************************************/ + +/*------------------------------------------------------------ + * + * __mpa_shift_words_left + * + */ +void __mpa_shift_words_left(mpanum op, mpa_word_t q) +{ + mpa_word_t i; + + if (q == 0 || __mpanum_is_zero(op)) + return; + for (i = __mpanum_size(op) + q - 1; i > q - 1; i--) + op->d[i] = op->d[i - q]; + + mpa_memset(op->d, 0, BYTES_PER_WORD * q); + + /* update the size of op */ + if (op->size > 0) + op->size += q; + else + op->size -= q; +} + +/*------------------------------------------------------------ + * + * __mpa_shift_words_right + * + */ +void __mpa_shift_words_right(mpanum op, mpa_word_t q) +{ + mpa_word_t i; + + if (q == 0 || __mpanum_is_zero(op)) + return; + + if (q >= __mpanum_size(op)) { + mpa_set_word(op, 0); + return; + } + + for (i = 0; i < __mpanum_size(op) - q; i++) + op->d[i] = op->d[i + q]; + + /* update the size of dest */ + if (op->size > 0) + op->size -= q; + else + op->size += q; +} + +/************************************************************* + * + * LIB FUNCTIONS + * + *************************************************************/ + +/* -------------------------------------------------------------------- + * mpa_shift_left + * + * Shifts src left by "steps" step and put result in dest. + * It does not care about signs. Dest will have same sign as src. + */ +void mpa_shift_left(mpanum dest, mpanum src, mpa_word_t steps) +{ + mpa_word_t q; /* quotient of steps div WORD_SIZE */ + mpa_word_t r; /* remainder of steps div WORD_SIZE */ + mpa_word_t i; + /* the bits of the word which will be shifted into another word */ + mpa_word_t rbits; + mpa_word_t need_extra_word; + + /* + * Copy first, then check, since even a shifted zero should + * be copied. + */ + mpa_copy(dest, src); + __mpa_set_unused_digits_to_zero(dest); + if (steps == 0 || __mpanum_is_zero(dest)) + return; + + r = steps & (WORD_SIZE - 1); /* 0 <= r < WORD_SIZE */ + q = steps >> LOG_OF_WORD_SIZE; /* 0 <= q */ + + /* + * The size of dest will always increase by at least q. + * If we're shifting r bits and the r highest bits in + * the MSW of dest is zero, we don't need the extra word + * Note: + * We cannot do + * if (_mpanumMSW(dest) >> (WORD_SIZE - r)) + * since some compilers (MS) does not shift the word + * if the shift quantity is larger or equal to the word size... + * Otherwise it would be natural to say that (a >> b) is just zero + * if b is larger than the number of bit of a, but no no... + */ + need_extra_word = 0; + + if (r == 0) { /* and q > 0 */ + /* + * We have a simple shift by words + */ + for (i = __mpanum_size(dest) + q - 1; i > q - 1; i--) + dest->d[i] = dest->d[i - q]; + } else { + if (__mpanum_msw(dest) & + (((((mpa_word_t)1 << r) - 1u)) << (WORD_SIZE - r))) + need_extra_word = 1; + /* + * We have a combination of word and bit shifting. + * + * If need_extra_word is 1, the MSW is special and handled + * here + */ + i = __mpanum_size(dest) + q + need_extra_word; + if (need_extra_word) { + rbits = dest->d[i - q - 1] >> (WORD_SIZE - r); + dest->d[i] ^= rbits; + } + i--; + dest->d[i] = dest->d[i - q] << r; + while (i > q) { + rbits = dest->d[i - q - 1] >> (WORD_SIZE - r); + dest->d[i] ^= rbits; + i--; + dest->d[i] = dest->d[i - q] << r; + } + } + mpa_memset(dest->d, 0, BYTES_PER_WORD * q); + /* update the size of dest */ + if (dest->size > 0) + dest->size += q + need_extra_word; + else + dest->size -= q + need_extra_word; +} + +/*------------------------------------------------------------ + * + * mpa_shift_right + * + * Shifts src right by "steps" step and put result in dest. + * It does not care about signs. Dest will have same sign as src. + * + */ +void mpa_shift_right(mpanum dest, mpanum src, mpa_word_t steps) +{ + mpa_word_t q; /* quotient of steps div WORD_SIZE */ + mpa_word_t r; /* remainder of steps div WORD_SIZE */ + mpa_word_t i; + /* the bits of the word which will be shifted into another word */ + mpa_word_t rbits; + + /* + * Copy first, then check, since even a shifted zero should + * be copied. + */ + mpa_copy(dest, src); + __mpa_set_unused_digits_to_zero(dest); + if (steps == 0 || __mpanum_is_zero(dest)) + return; + + r = steps & (WORD_SIZE - 1); /* 0 <= r < WORD_SIZE */ + q = steps >> LOG_OF_WORD_SIZE; /* 0 <= q */ + + if (q >= __mpanum_size(dest)) { + mpa_set_word(dest, 0); + return; + } + + /* + * Here we have: + * 0 <= r < WORD_SIZE - 1 + * 0 <= q < _mpanumSize(dest) + */ + if (r == 0) { /* and q > 0 */ + /* Simple shift by words */ + for (i = 0; i < __mpanum_size(dest) - q; i++) + dest->d[i] = dest->d[i + q]; + } else { + /* combination of word and bit shifting */ + for (i = 0; i < __mpanum_size(dest) - q - 1; i++) { + dest->d[i] = dest->d[i + q]; + rbits = dest->d[i + q + 1] & ((1UL << r) - 1); + dest->d[i] = + (dest->d[i] >> r) ^ (rbits << (WORD_SIZE - r)); + } + /* final word is special */ + dest->d[i] = dest->d[i + q] >> r; + } + + /* update the size of dest */ + if (dest->size > 0) + dest->size -= q; + else + dest->size += q; + + /* Take care of the case when we shifted out all bits from MSW */ + if (__mpanum_msw(dest) == 0) { + if (dest->size > 0) + dest->size--; + else + dest->size++; + } +} diff --git a/lib/libmpa/sub.mk b/lib/libmpa/sub.mk new file mode 100644 index 0000000..38c1610 --- /dev/null +++ b/lib/libmpa/sub.mk @@ -0,0 +1,45 @@ +global-incdirs-y += include + +ifneq ($(sm),core) # User-mode +cflags-lib-$(CFG_ULIBS_GPROF) += -pg +endif + +srcs-y += mpa_misc.c +cflags-remove-mpa_misc.c-y += -pedantic +cflags-mpa_misc.c-y += -Wno-sign-compare + +srcs-y += mpa_montgomery.c +cflags-remove-mpa_montgomery.c-y += -Wdeclaration-after-statement + +srcs-y += mpa_primetest.c +cflags-remove-mpa_primetest.c-y += -pedantic + +srcs-y += mpa_conv.c +cflags-mpa_conv.c-y += -Wno-sign-compare + +srcs-y += mpa_div.c +cflags-mpa_div.c-y += -Wno-sign-compare + +srcs-y += mpa_gcd.c +cflags-mpa_gcd.c-y += -Wno-sign-compare + +srcs-y += mpa_mem_static.c +cflags-mpa_mem_static.c-y += -Wno-sign-compare + +srcs-y += mpa_mul.c +cflags-mpa_mul.c-y += -Wno-sign-compare + +srcs-y += mpa_random.c +cflags-mpa_random.c-y += -Wno-sign-compare + +srcs-y += mpa_shift.c +cflags-mpa_shift.c-y += -Wno-sign-compare + +srcs-y += mpa_addsub.c +srcs-y += mpa_cmp.c +srcs-y += mpa_expmod.c +srcs-y += mpa_init.c +srcs-y += mpa_io.c +srcs-y += mpa_modulus.c + +subdirs-$(arch_arm) += arch/$(ARCH) |