From 872dff3138536a68b6dd96b182a386d242bee6cb Mon Sep 17 00:00:00 2001 From: bg Date: Sun, 17 Feb 2013 10:35:16 +0100 Subject: [PATCH] optimization of reduce for small delta --- bigint/bigint.c | 82 ++++++++++++++++++++++++++----------------------- 1 file changed, 44 insertions(+), 38 deletions(-) diff --git a/bigint/bigint.c b/bigint/bigint.c index d2d1fc7..7ba80b3 100644 --- a/bigint/bigint.c +++ b/bigint/bigint.c @@ -683,6 +683,7 @@ void bigint_square(bigint_t* dest, const bigint_t* a){ } /******************************************************************************/ + void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){ bigint_t tmp, x; bigint_word_t tmp_b[b->length_W + 1]; @@ -719,41 +720,44 @@ void bigint_reduce(bigint_t* a, const bigint_t* r){ if(r->length_W==0 || a->length_W==0){ return; } - if((r->length_W*sizeof(bigint_word_t)<=4) && (a->length_W*sizeof(bigint_word_t)<=4)){ - uint32_t p=0, q=0; - memcpy(&p, a->wordv, a->length_W*sizeof(bigint_word_t)); - memcpy(&q, r->wordv, r->length_W*sizeof(bigint_word_t)); - p %= q; - memcpy(a->wordv, &p, a->length_W*sizeof(bigint_word_t)); - bigint_adjust(a); -// cli_putstr("\r\nDBG: (0) = "); bigint_print_hex(a); - return; - } - uint16_t shift; - while(a->length_W > r->length_W){ - shift = (a->length_W - r->length_W) * 8 * sizeof(bigint_word_t) + GET_FBS(a) - rfbs - 1; - /* - if((a->wordv[a->length_W-1] & ((1LL< r->wordv[r->length_W-1]){ - // cli_putc('~'); - cli_putstr("\r\n ~ [a] = "); - cli_hexdump_rev(&a->wordv[a->length_W-1], 4); - cli_putstr(" [r] = "); - cli_hexdump_rev(&r->wordv[r->length_W-1], 4); - shift += 1; - } - */ -// cli_putstr("\r\nDBG: (p) shift = "); cli_hexdump_rev(&shift, 2); -// cli_putstr(" a_len = "); cli_hexdump_rev(&a->length_W, 2); -// cli_putstr(" r_len = "); cli_hexdump_rev(&r->length_W, 2); -// uart_flush(0); - bigint_sub_u_bitscale(a, r, shift); -// cli_putstr("\r\nDBG: (1) = "); bigint_print_hex(a); - } - while((GET_FBS(a) > rfbs) && (a->length_W == r->length_W)){ - shift = GET_FBS(a)-rfbs-1; -// cli_putstr("\r\nDBG: (q) shift = "); cli_hexdump_rev(&shift, 2); - bigint_sub_u_bitscale(a, r, shift); -// cli_putstr("\r\nDBG: (2) = "); bigint_print_hex(a); + + if(bigint_length_b(a) + 3 > bigint_length_b(r)){ + if((r->length_W*sizeof(bigint_word_t)<=4) && (a->length_W*sizeof(bigint_word_t)<=4)){ + uint32_t p=0, q=0; + memcpy(&p, a->wordv, a->length_W*sizeof(bigint_word_t)); + memcpy(&q, r->wordv, r->length_W*sizeof(bigint_word_t)); + p %= q; + memcpy(a->wordv, &p, a->length_W*sizeof(bigint_word_t)); + bigint_adjust(a); + // cli_putstr("\r\nDBG: (0) = "); bigint_print_hex(a); + return; + } + uint16_t shift; + while(a->length_W > r->length_W){ + shift = (a->length_W - r->length_W) * 8 * sizeof(bigint_word_t) + GET_FBS(a) - rfbs - 1; + /* + if((a->wordv[a->length_W-1] & ((1LL< r->wordv[r->length_W-1]){ + // cli_putc('~'); + cli_putstr("\r\n ~ [a] = "); + cli_hexdump_rev(&a->wordv[a->length_W-1], 4); + cli_putstr(" [r] = "); + cli_hexdump_rev(&r->wordv[r->length_W-1], 4); + shift += 1; + } + */ + // cli_putstr("\r\nDBG: (p) shift = "); cli_hexdump_rev(&shift, 2); + // cli_putstr(" a_len = "); cli_hexdump_rev(&a->length_W, 2); + // cli_putstr(" r_len = "); cli_hexdump_rev(&r->length_W, 2); + // uart_flush(0); + bigint_sub_u_bitscale(a, r, shift); + // cli_putstr("\r\nDBG: (1) = "); bigint_print_hex(a); + } + while((GET_FBS(a) > rfbs) && (a->length_W == r->length_W)){ + shift = GET_FBS(a)-rfbs-1; + // cli_putstr("\r\nDBG: (q) shift = "); cli_hexdump_rev(&shift, 2); + bigint_sub_u_bitscale(a, r, shift); + // cli_putstr("\r\nDBG: (2) = "); bigint_print_hex(a); + } } while(bigint_cmp_u(a,r)>=0){ bigint_sub_u(a,a,r); @@ -768,7 +772,7 @@ void bigint_reduce(bigint_t* a, const bigint_t* r){ /* calculate dest = a**exp % r */ /* using square&multiply */ -void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){ +void bigint_expmod_u_sam(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){ if(a->length_W==0 || r->length_W==0){ return; } @@ -1031,9 +1035,11 @@ void bigint_changeendianess(bigint_t* a){ +/******************************************************************************/ - - +void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){ + bigint_expmod_u_sam(dest, a, exp, r); +} -- 2.39.2