stack usage measurement

[avr-crypto-lib.git] / bigint / bigint.c

diff --git a/bigint/bigint.c b/bigint/bigint.c
index f57d285fc0ae7f2d65cf60f3115a73ff74fced57..7004e0dc1cb6640cadcf5ec2929e8f67f75fc40c 100644 (file)
--- a/bigint/bigint.c
+++ b/bigint/bigint.c
@@ -26,9 +26,16 @@
  */
  
 
+#define STRING2(x) #x
+#define STRING(x) STRING2(x)
+#define STR_LINE STRING(__LINE__)
+
 #include "bigint.h"
 #include <string.h>
-
+/*
+#include "cli.h"
+#include "bigint_io.h"
+*/
 #ifndef MAX
  #define MAX(a,b) (((a)>(b))?(a):(b))
 #endif
@@ -388,6 +395,10 @@ void bigint_set_zero(bigint_t* a){
 /* using the Karatsuba-Algorithm */
 /* x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + yh*yl */
 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);
+               return;
+       }
        if(dest==a || dest==b){
                bigint_t d;
                uint8_t d_b[a->length_B+b->length_B];
@@ -396,10 +407,6 @@ void bigint_mul_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){
                bigint_copy(dest, &d);
                return;
        }
-       if(a->length_B==0 || b->length_B==0){
-               bigint_set_zero(dest);
-               return;
-       }
        if(a->length_B==1 || b->length_B==1){
                if(a->length_B!=1){
                        XCHG_PTR(a,b);
@@ -575,7 +582,6 @@ void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){
        }
        while(borrow){
                if(i+1 > a->length_B){
-                       cli_hexdump_rev(&bitscale, 2);
                        bigint_set_zero(a);
                        return;
                }
@@ -591,19 +597,18 @@ 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){
+//     bigint_adjust(r);
        uint8_t rfbs = GET_FBS(r);
 
-       if(r->length_B==0){
+       if(r->length_B==0 || a->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) && (a->length_B == r->length_B)){
                bigint_sub_u_bitscale(a, r, GET_FBS(a)-rfbs-1);
        }
-
        while(bigint_cmp_u(a,r)>=0){
                bigint_sub_u(a,a,r);
        }
@@ -615,45 +620,46 @@ 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){
-       bigint_t tmp, tmp2, x;
-       uint8_t x_b[MAX(r->length_B, a->length_B)], tmp_b[r->length_B*2], tmp2_b[r->length_B*2];
-       int16_t i;
-       uint8_t j;
-       x.wordv = x_b;
-       tmp.wordv = tmp_b;
-       tmp2.wordv = tmp2_b;
-       bigint_copy(&x, a);
-       bigint_reduce(&x, r);
-       bigint_copy(&tmp, &x);
-       if(a->length_B==0 || exp->length_B==0 || r->length_B==0){
+       if(a->length_B==0 || r->length_B==0){
                return;
        }
-       i=exp->length_B-1;
-       if(exp->wordv[i]!=1){
-               for(j=1<<(GET_FBS(exp)-1); j>0; j>>=1){
-                       bigint_square(&tmp2, &tmp);
-                       bigint_reduce(&tmp2, r);
-                       if(exp->wordv[i]&j){
-                               bigint_mul_u(&tmp, &tmp2, &x);
-                               bigint_reduce(&tmp, r);
-                       }else{
-                               bigint_copy(&tmp, &tmp2);
+
+       bigint_t res, base;
+       uint8_t base_b[MAX(a->length_B,r->length_B*2)], res_b[r->length_B*2];
+       uint16_t i;
+       uint8_t j, t;
+       res.wordv = res_b;
+       base.wordv = base_b;
+       bigint_copy(&base, a);
+       bigint_reduce(&base, r);
+       res.wordv[0]=1;
+       res.length_B=1;
+       res.info = 0;
+       bigint_adjust(&res);
+       for(i=0; i+1<exp->length_B; ++i){
+               t=exp->wordv[i];
+               for(j=0; j<8; ++j){
+                       if(t&1){
+                               bigint_mul_u(&res, &res, &base);
+                               bigint_reduce(&res, r);
                        }
+                       bigint_square(&base, &base);
+                       bigint_reduce(&base, r);
+                       t>>=1;
                }
        }
-       for(--i; i>=0; --i){
-               for(j=0x80; j>0; j>>=1){
-                       bigint_square(&tmp2, &tmp);
-                       bigint_reduce(&tmp2, r);
-                       if(exp->wordv[i]&j){
-                               bigint_mul_u(&tmp, &tmp2, &x);
-                               bigint_reduce(&tmp, r);
-                       }else{
-                               bigint_copy(&tmp, &tmp2);
-                       }
+       t=exp->wordv[i];
+       while(t){
+               if(t&1){
+                       bigint_mul_u(&res, &res, &base);
+                       bigint_reduce(&res, r);
                }
+               bigint_square(&base, &base);
+               bigint_reduce(&base, r);
+               t>>=1;
        }
-       bigint_copy(dest, &tmp);
+       SET_POS(&res);
+       bigint_copy(dest, &res);
 }
 
 /******************************************************************************/
@@ -755,14 +761,28 @@ void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, c
 
 /******************************************************************************/
 
-void bigint_inverse(bigint_t* dest, bigint_t* a, bigint_t* m){
+void bigint_inverse(bigint_t* dest, const bigint_t* a, const bigint_t* m){
        bigint_gcdext(NULL, dest, NULL, a, m);
        while(dest->info&BIGINT_NEG_MASK){
                bigint_add_s(dest, dest, m);
        }
 }
 
+/******************************************************************************/
+
+void bigint_changeendianess(bigint_t* a){
+       uint8_t t, *p, *q;
+       p = a->wordv;
+       q = p+a->length_B-1;
+       while(p<q){
+               t = *p;
+               *p = *q;
+               *q = t;
+               ++p; --q;
+       }
+}
 
+/******************************************************************************/