From 4bd4efef59a3f71149393516b7bd283eeab18363 Mon Sep 17 00:00:00 2001 From: bg Date: Thu, 4 Mar 2010 18:34:50 +0000 Subject: [PATCH] adding modulo-reduction to bigint --- bigint/bigint.c | 73 ++++++++++++++++++++++++++++----- bigint/bigint.h | 5 ++- host/bigint_test.rb | 80 ++++++++++++++++++++++++++++++++++++- test_src/main-bigint-test.c | 78 +++++++++++++++++++++++++++++++++++- 4 files changed, 223 insertions(+), 13 deletions(-) diff --git a/bigint/bigint.c b/bigint/bigint.c index fb2f524..d83edb6 100644 --- a/bigint/bigint.c +++ b/bigint/bigint.c @@ -344,19 +344,18 @@ void bigint_shiftleft(bigint_t* a, uint16_t shift){ t >>= 8; } a->wordv[i] = (uint8_t)t; + byteshift++; }else{ /* shift to the right */ - bitshift = 8 - bitshift; - for(i=a->length_B+byteshift-1; i>byteshift; --i){ - t |= (a->wordv[i])<<(8-bitshift); + for(i=a->length_B+byteshift-1; i>byteshift-1; --i){ + t |= (a->wordv[i])<<(bitshift); a->wordv[i] = (uint8_t)(t>>8); t <<= 8; } - t |= (a->wordv[i])<<(8-bitshift); + t |= (a->wordv[i])<<(bitshift); a->wordv[i] = (uint8_t)(t>>8); } - } - a->length_B += byteshift+1; + a->length_B += byteshift; bigint_adjust(a); } @@ -422,7 +421,6 @@ void bigint_set_zero(bigint_t* a){ void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ if(a->length_B==0 || b->length_B==0){ bigint_set_zero(dest); - depth -= 1; return; } if(a->length_B==1 || b->length_B==1){ @@ -488,7 +486,6 @@ void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ /* now we have split up a and b */ uint8_t tmp_b[2*n+2], m_b[2*(n+1)]; bigint_t tmp, tmp2, m; - /* calculate h=xh*yh; l=xl*yl; sx=xh+xl; sy=yh+yl */ tmp.wordv = tmp_b; tmp2.wordv = tmp_b+n+1; m.wordv = m_b; @@ -562,12 +559,70 @@ void bigint_square(bigint_t* dest, const bigint_t* a){ bigint_mul_u(&tmp, &xl, &xh); bigint_shiftleft(&tmp, 1); bigint_add_scale_u(dest, &tmp, n); - } +/******************************************************************************/ +void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){ + bigint_t tmp; + uint8_t tmp_b[b->length_B+1]; + uint16_t i,j,byteshift=bitscale/8; + uint8_t borrow=0; + int16_t t; + if(a->length_B < b->length_B+byteshift){ + cli_putstr_P(PSTR("\r\nERROR: bigint_sub_u_bitscale result negative")); + bigint_set_zero(a); + return; + } + tmp.wordv = tmp_b; + bigint_copy(&tmp, b); + bigint_shiftleft(&tmp, bitscale&7); + + for(j=0,i=byteshift; iwordv[i] - tmp.wordv[j] - borrow; + a->wordv[i] = (uint8_t)t; + if(t<0){ + borrow = 1; + }else{ + borrow = 0; + } + } + while(borrow){ + if(i+1 > a->length_B){ + cli_putstr_P(PSTR("\r\nERROR: bigint_sub_u_bitscale result negative (2) shift=")); + cli_hexdump_rev(&bitscale, 2); + bigint_set_zero(a); + return; + } + a->wordv[i] -= borrow; + if(a->wordv[i]!=0xff){ + borrow=0; + } + ++i; + } + bigint_adjust(a); +} + +/******************************************************************************/ + +void bigint_reduce(bigint_t* a, const bigint_t* r){ + uint8_t rfbs = GET_FBS(r); + if(r->length_B==0){ + return; + } + while(a->length_B > r->length_B){ + bigint_sub_u_bitscale(a, r, (a->length_B-r->length_B)*8+GET_FBS(a)-rfbs-1); + } + while(GET_FBS(a) > rfbs+1){ + bigint_sub_u_bitscale(a, r, GET_FBS(a)-rfbs-1); + } + while(bigint_cmp_u(a,r)>=0){ + bigint_sub_u(a,a,r); + } + bigint_adjust(a); +} diff --git a/bigint/bigint.h b/bigint/bigint.h index 39bb173..d8dfb14 100644 --- a/bigint/bigint.h +++ b/bigint/bigint.h @@ -42,7 +42,7 @@ typedef struct{ /******************************************************************************/ void bigint_adjust(bigint_t* a); -void bigint_copy(bigint_t* dest, const bigint_t* src); +void bigint_copy(bigint_t* dest, const bigint_t* src); void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b); void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale); void bigint_sub_u(bigint_t* dest, const bigint_t* a, const bigint_t* b); @@ -57,7 +57,8 @@ void bigint_set_zero(bigint_t* a); void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b); void bigint_mul_s(bigint_t* dest, const bigint_t* a, const bigint_t* b); 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); +void bigint_reduce(bigint_t* a, const bigint_t* r); /******************************************************************************/ #endif /*BIGINT_H_*/ diff --git a/host/bigint_test.rb b/host/bigint_test.rb index 9048f89..71f1195 100644 --- a/host/bigint_test.rb +++ b/host/bigint_test.rb @@ -234,6 +234,55 @@ def square_test(a) return false end +################################################################################ +# reduce_test # +################################################################################ + +def reduce_test(a,b) + begin + line = $sp.gets() + line = "" if line==nil + puts("DBG got: "+line) if $debug + if /^Error:.*/.match(line) + puts line + return false + end + end while not /[\s]*enter a:[\s]*/.match(line) + $sp.print(a.to_s(16)+" ") + begin + line = $sp.gets() + line = "" if line==nil + puts("DBG got: "+line) if $debug + if /^Error:.*/.match(line) + puts line + return false + end + end while not /[\s]*enter b:[\s]*/.match(line) + $sp.print(b.to_s(16)+" ") + begin + line = $sp.gets() + line = "" if line==nil + puts("DBG got: "+line) if $debug + if /^Error:.*/.match(line) + puts line + return false + end + end while not m=/[\s]*([+-]?[0-9a-fA-F]*)[\s]+%[\s]+([+-]?[0-9a-fA-F]*)[\s]*=[\s]*([+-]?[0-9a-fA-F]*)/.match(line) + a_ = m[1].to_i(16) + b_ = m[2].to_i(16) + c_ = m[3].to_i(16) + line.chomp! + if(a_== a && b_ == b && c_ == (a%b)) + $logfile.printf("[pass]: %s\n", line) + return true + else + $logfile.printf("[fail (%s%s%s)]: %s", (a==a_)?"":"a", (b==b_)?"":"b", (c_==a+b)?"":"c",line) + $logfile.printf(" ; should %s %% %s = %s\n", a.to_s(16), b.to_s(16), (a%b).to_s(16)) + return false + end + return false +end + ################################################################################ # run_test_add # ################################################################################ @@ -322,6 +371,33 @@ def run_test_square(skip=0) end while length_a_B<4096/8 end +################################################################################ +# run_test_reduce # +################################################################################ + +def run_test_reduce(skip=0) + length_a_B = skip+1 + length_b_B = skip+1 + begin + $size = length_a_B + (0..16).each do |i| + a = rand(256**length_a_B) + b = rand(256**length_a_B)+1 + v = reduce_test(a, b) + screen_progress(v) + end + (0..16).each do |i| + b_size = rand(length_b_B+1) + a = rand(256**length_a_B) + b = rand(256**b_size)+1 + v = reduce_test(a, b) + screen_progress(v) + end + length_a_B += 1 + length_b_B += 1 + end while length_a_B<4096/8 +end + ################################################################################ # MAIN # ################################################################################ @@ -395,10 +471,12 @@ tests = Hash.new tests['a'] = proc {|x| run_test_add(x) } tests['m'] = proc {|x| run_test_mul(x) } tests['s'] = proc {|x| run_test_square(x) } +tests['r'] = proc {|x| run_test_reduce(x) } init_str = Hash.new init_str['a'] = 'add-test' init_str['m'] = 'mul-test' init_str['s'] = 'square-test' +init_str['r'] = 'reduce-test' srand(0xdeadbeef) @@ -413,7 +491,7 @@ if opts['a'] end end else - 'ams'.each_char do |x| + 'amsr'.each_char do |x| if tests[x] puts init_str[x] init_system(init_str[x]) diff --git a/test_src/main-bigint-test.c b/test_src/main-bigint-test.c index 3d5bd21..85bcb09 100644 --- a/test_src/main-bigint-test.c +++ b/test_src/main-bigint-test.c @@ -163,6 +163,34 @@ void test_square_bigint(void){ } } +void test_reduce_bigint(void){ + bigint_t a, b, c; + cli_putstr_P(PSTR("\r\nreduce test\r\n")); + for(;;){ + cli_putstr_P(PSTR("\r\nenter a:")); + if(bigint_read_hex_echo(&a)){ + cli_putstr_P(PSTR("\r\n end reduce test")); + return; + } + cli_putstr_P(PSTR("\r\nenter b:")); + if(bigint_read_hex_echo(&b)){ + free(a.wordv); + cli_putstr_P(PSTR("\r\n end reduce test")); + return; + } + cli_putstr_P(PSTR("\r\n ")); + bigint_print_hex(&a); + cli_putstr_P(PSTR(" % ")); + bigint_print_hex(&b); + cli_putstr_P(PSTR(" = ")); + bigint_reduce(&a, &b); + bigint_print_hex(&a); + cli_putstr_P(PSTR("\r\n")); + free(a.wordv); + free(b.wordv); + } +} + void test_simple(void){ bigint_t a, b, c; uint8_t a_b[1], b_b[1], c_b[2]; @@ -226,6 +254,26 @@ void test_mul_simple(void){ } // f4 b86a 2220 0774 437d 70e6 **2 = e9f00f29ca1c876a7a682bd1e04f6925caffd6660ea4 +/* +uint8_t square_test_data[] PROGMEM = { + 0xA0, 0x3C, 0x23, 0x9F, 0x7A, 0xFC, 0x60, 0xEB, 0x96, 0xC2, 0xA8, 0xAC, 0xC3, 0xC9, 0x9E, 0xEC, + 0x4A, 0xF0, 0x1C, 0xB2, 0x36, 0x68, 0xD6, 0x4D, 0x3E, 0x4F, 0x8E, 0x55, 0xEA, 0x52, 0x46, 0x68, + 0x6E, 0x18, 0x88, 0x37, 0x03, 0x70, 0xBD, 0x01, 0x60, 0xE2, 0xD6, 0x12, 0xA0, 0x0E, 0xD2, 0x72, + 0x0D, 0x9D, 0x9F, 0x03, 0xC5, 0x81, 0xCA, 0x6E, 0x88, 0x1E, 0xF5, 0xD8, 0x14, 0x15, 0x30, 0xEB, + 0x28, 0x7C, 0x80, 0x07, 0x34, 0x05, 0x5D, 0xAA, 0xDC, 0xA8, 0xAA, 0x88, 0xC5, 0xE5, 0xC9, 0xFE, + 0x9C, 0xA1, 0xCE, 0xC2, 0x09, 0x0D, 0xC4, 0xC8, 0xD3, 0xE7, 0x3A, 0xF3, 0xEF, 0xDF, 0xAE, 0x07, + 0xEC, 0xC7, 0x83, 0x50, 0x9F, 0x6D, 0xB9, 0x28, 0x77, 0xC0, 0xFE, 0x69, 0xB2, 0x2E, 0x55, 0x90, + 0x50, 0xED, 0xE0, 0xA1, 0x4D, 0x3D, 0x38, 0xC9, 0x0E, 0xCD, 0x04, 0x3B, 0x64, 0x3F, 0x56, 0xC5, + 0xC3, 0x9E, 0x89, 0x81, 0x44, 0x60, 0xBA, 0x8E, 0x88, 0xA4, 0xA3, 0x42, 0x7B, 0x06, 0x93, 0x1C, + 0x6B, 0x04, 0x29, 0xF9, 0xDD, 0xFF, 0xB0, 0x48, 0x2F, 0x6D, 0xD1, 0x0F, 0x7D, 0xA6, 0x26, 0xD8, + 0xEF, 0x5E, 0x04, 0x18, 0xD1, 0x61, 0x46, 0x37, 0x87, 0xE2, 0x97, 0xDF, 0x10, 0xB4, 0x9A, 0x39, + 0xB1, 0xD0, 0xCA, 0x91, 0x48, 0x1E, 0x5D, 0xA1, 0x38, 0x89, 0x02, 0xC1, 0x49, 0x86, 0xB7, 0xAE, + 0x69, 0x20, 0xFA, 0x0E, 0x39, 0xDA, 0xA5, 0xEF, 0x7F, 0xB2, 0x81, 0xB8, 0xC0, 0x3A, 0xF8, 0xDB, + 0xBC, 0x45, 0xF6, 0xDA, 0xCD, 0xBE, 0x27, 0xBE, 0xF6, 0x20, 0x79, 0xF3, 0xC3, 0xC8, 0xFF, 0x85, + 0x43, 0x9F, 0xB1, 0x9B, 0x72, 0x88, 0xDD, 0xA4, 0x0D, 0xFC, 0xC6, 0xB5, 0x74, 0x67, 0x29, 0xF5 +}; +*/ + void test_square_simple(void){ bigint_t a, c; @@ -243,6 +291,32 @@ void test_square_simple(void){ bigint_print_hex(&c); } +// [fail (c)]: A862 % 2752 = 0D1A ; should a862 % 2752 = b1a +void test_reduce_simple(void){ + bigint_t a, b, c; + + uint8_t a_b[2] = {0x62, 0xA8}; + uint8_t b_b[2] = {0x52, 0x27}; + uint8_t c_b[2]; + a.wordv=a_b; + a.length_B = 2; + a.info=0x00; + bigint_adjust(&a); + b.wordv=b_b; + b.length_B = 2; + b.info=0x00; + bigint_adjust(&b); + c.wordv = c_b; + bigint_copy(&c, &a); + bigint_reduce(&c, &b); + cli_putstr_P(PSTR("\r\n test: ")); + bigint_print_hex(&a); + cli_putstr_P(PSTR(" % ")); + bigint_print_hex(&b); + cli_putstr_P(PSTR(" = ")); + bigint_print_hex(&c); +} + void testrun_performance_bigint(void){ @@ -255,6 +329,7 @@ const char echo_test_str[] PROGMEM = "echo-test"; const char add_test_str[] PROGMEM = "add-test"; const char mul_test_str[] PROGMEM = "mul-test"; const char square_test_str[] PROGMEM = "square-test"; +const char reduce_test_str[] PROGMEM = "reduce-test"; const char quick_test_str[] PROGMEM = "quick-test"; const char performance_str[] PROGMEM = "performance"; const char echo_str[] PROGMEM = "echo"; @@ -263,7 +338,8 @@ cmdlist_entry_t cmdlist[] PROGMEM = { { add_test_str, NULL, test_add_bigint }, { mul_test_str, NULL, test_mul_bigint }, { square_test_str, NULL, test_square_bigint }, - { quick_test_str, NULL, test_mul_simple }, + { reduce_test_str, NULL, test_reduce_bigint }, + { quick_test_str, NULL, test_reduce_simple }, { echo_test_str, NULL, test_echo_bigint }, { performance_str, NULL, testrun_performance_bigint }, { echo_str, (void*)1, (void_fpt)echo_ctrl }, -- 2.39.5