From: bg Date: Wed, 23 Feb 2011 22:18:37 +0000 (+0100) Subject: starting to make bigint more portable/32-bit efficient X-Git-Url: https://git.cryptolib.org/?p=arm-crypto-lib.git;a=commitdiff_plain;h=5e75eafde9b0269aa78395bbeb3e79ff36a1f082 starting to make bigint more portable/32-bit efficient --- diff --git a/Makefile b/Makefile index e922e64..9015cec 100644 --- a/Makefile +++ b/Makefile @@ -160,7 +160,7 @@ endef $(foreach algo, $(ALGORITHMS), $(eval $(call Flash_Template, \ $(algo), \ - $(BIN_DIR)$(call lc, $(algo))/$(TEST_DIR)main-$(call lc, $(algo))-test.hex \ + $(BIN_DIR)$(call lc, $(algo))/$(TEST_DIR)main-$(call lc, $(algo))-test.elf \ ))) #------------------------------------------------------------------------------- diff --git a/arm-makefile.inc b/arm-makefile.inc index 396e108..10b5090 100644 --- a/arm-makefile.inc +++ b/arm-makefile.inc @@ -1,7 +1,7 @@ -TOOLCHAIN = arm-elf- +TOOLCHAIN = arm-none-eabi-# MCU_TARGET = cortex-m3 -OPTIMIZE = -O2 -DEBUG = -g +OPTIMIZE = -O0 +DEBUG = -gdwarf-2 WARNING = -pedantic -Wall -Wstrict-prototypes -Werror DEFS = -D$(call uc, $(subst -,_,$(MCU_TARGET))) FLASHCMD = $(TOOLCHAIN)gdb -x gdb-flash # diff --git a/bigint/bigint-stub.c b/bigint/bigint-stub.c new file mode 100644 index 0000000..451e8d7 --- /dev/null +++ b/bigint/bigint-stub.c @@ -0,0 +1,790 @@ +/* bigint.c */ +/* + This file is part of the AVR-Crypto-Lib. + Copyright (C) 2008 Daniel Otte (daniel.otte@rub.de) + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ +/** + * \file bigint.c + * \author Daniel Otte + * \date 2010-02-22 + * + * \license GPLv3 or later + * + */ + + +#define STRING2(x) #x +#define STRING(x) STRING2(x) +#define STR_LINE STRING(__LINE__) + +#include "bigint.h" +#include +/* +#include "cli.h" +#include "bigint_io.h" +*/ +#ifndef MAX + #define MAX(a,b) (((a)>(b))?(a):(b)) +#endif + +#ifndef MIN + #define MIN(a,b) (((a)<(b))?(a):(b)) +#endif + +#define SET_FBS(a, v) do{(a)->info &=0xF8; (a)->info |= (v);}while(0) +#define GET_FBS(a) ((a)->info&BIGINT_FBS_MASK) +#define SET_NEG(a) (a)->info |= BIGINT_NEG_MASK +#define SET_POS(a) (a)->info &= ~BIGINT_NEG_MASK +#define XCHG(a,b) do{(a)^=(b); (b)^=(a); (a)^=(b);}while(0) +#define XCHG_PTR(a,b) do{ a = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b))); \ + b = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b))); \ + a = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b)));}while(0) + +#define GET_SIGN(a) ((a)->info&BIGINT_NEG_MASK) + + +/******************************************************************************/ +/* +void bigint_copy(bigint_t* dest, const bigint_t* src){ + memcpy(dest->wordv, src->wordv, src->length_B); + dest->length_B = src->length_B; + dest->info = src->info; +} +*/ +/******************************************************************************/ + +/* this should be implemented in assembly */ +/* +void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + uint16_t t=0, i; + if(a->length_B < b->length_B){ + XCHG_PTR(a,b); + } + for(i=0; ilength_B; ++i){ + t = a->wordv[i] + b->wordv[i] + t; + dest->wordv[i] = (uint8_t)t; + t>>=8; + } + for(; ilength_B; ++i){ + t = a->wordv[i] + t; + dest->wordv[i] = (uint8_t)t; + t>>=8; + } + dest->wordv[i++] = t; + dest->length_B = i; + bigint_adjust(dest); +} +*/ +/******************************************************************************/ + +/* this should be implemented in assembly */ +void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale){ + uint16_t i,j=0; + uint16_t t=0; + if(scale>dest->length_B) + memset(dest->wordv+dest->length_B, 0, scale-dest->length_B); + for(i=scale; ilength_B+scale; ++i,++j){ + t = a->wordv[j] + t; + if(dest->length_B>i){ + t += dest->wordv[i]; + } + dest->wordv[i] = (uint8_t)t; + t>>=8; + } + while(t){ + if(dest->length_B>i){ + t = dest->wordv[i] + t; + } + dest->wordv[i] = (uint8_t)t; + t>>=8; + ++i; + } + if(dest->length_B < i){ + dest->length_B = i; + } + bigint_adjust(dest); +} + +/******************************************************************************/ + +/* this should be implemented in assembly */ +void bigint_sub_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + int8_t borrow=0; + int8_t r; + int16_t t; + uint16_t i, min, max; + min = MIN(a->length_B, b->length_B); + max = MAX(a->length_B, b->length_B); + r = bigint_cmp_u(a,b); + if(r==0){ + dest->length_B = 0; + dest->wordv[0] = 0; + bigint_adjust(dest); + return; + } + if(b->length_B==0){ + dest->length_B = a->length_B; + memcpy(dest->wordv, a->wordv, a->length_B); + dest->info = a->info; + SET_POS(dest); + return; + } + if(a->length_B==0){ + dest->length_B = b->length_B; + memcpy(dest->wordv, b->wordv, b->length_B); + dest->info = b->info; + SET_NEG(dest); + return; + } + if(r<0){ + bigint_sub_u(dest, b, a); + SET_NEG(dest); + }else{ + for(i=0; iwordv[i] - b->wordv[i] - borrow; + if(t<0){ + borrow = 1; + dest->wordv[i]=(uint8_t)t; + }else{ + borrow = 0; + dest->wordv[i]=(uint8_t)t; + } + } + for(;iwordv[i] - borrow; + if(t<0){ + borrow = 1; + dest->wordv[i]=(uint8_t)t; + }else{ + borrow = 0; + dest->wordv[i]=(uint8_t)t; + } + + } + SET_POS(dest); + dest->length_B = i; + bigint_adjust(dest); + } +} + +/******************************************************************************/ + +int8_t bigint_cmp_u(const bigint_t* a, const bigint_t* b){ + if(a->length_B > b->length_B){ + return 1; + } + if(a->length_B < b->length_B){ + return -1; + } + if(a->length_B==0){ + return 0; + } + uint16_t i; + i = a->length_B-1; + do{ + if(a->wordv[i]!=b->wordv[i]){ + if(a->wordv[i]>b->wordv[i]){ + return 1; + }else{ + return -1; + } + } + }while(i--); + return 0; +} + +/******************************************************************************/ + +void bigint_add_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + uint8_t s; + s = GET_SIGN(a)?2:0; + s |= GET_SIGN(b)?1:0; + switch(s){ + case 0: /* both positive */ + bigint_add_u(dest, a,b); + SET_POS(dest); + break; + case 1: /* a positive, b negative */ + bigint_sub_u(dest, a, b); + break; + case 2: /* a negative, b positive */ + bigint_sub_u(dest, b, a); + break; + case 3: /* both negative */ + bigint_add_u(dest, a, b); + SET_NEG(dest); + break; + default: /* how can this happen?*/ + break; + } +} + +/******************************************************************************/ + +void bigint_sub_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + uint8_t s; + s = GET_SIGN(a)?2:0; + s |= GET_SIGN(b)?1:0; + switch(s){ + case 0: /* both positive */ + bigint_sub_u(dest, a,b); + break; + case 1: /* a positive, b negative */ + bigint_add_u(dest, a, b); + SET_POS(dest); + break; + case 2: /* a negative, b positive */ + bigint_add_u(dest, a, b); + SET_NEG(dest); + break; + case 3: /* both negative */ + bigint_sub_u(dest, b, a); + break; + default: /* how can this happen?*/ + break; + } + +} + +/******************************************************************************/ + +int8_t bigint_cmp_s(const bigint_t* a, const bigint_t* b){ + uint8_t s; + if(a->length_B==0 && b->length_B==0){ + return 0; + } + s = GET_SIGN(a)?2:0; + s |= GET_SIGN(b)?1:0; + switch(s){ + case 0: /* both positive */ + return bigint_cmp_u(a, b); + break; + case 1: /* a positive, b negative */ + return 1; + break; + case 2: /* a negative, b positive */ + return -1; + break; + case 3: /* both negative */ + return bigint_cmp_u(b, a); + break; + default: /* how can this happen?*/ + break; + } + return 0; /* just to satisfy the compiler */ +} + +/******************************************************************************/ + +void bigint_shiftleft(bigint_t* a, uint16_t shift){ + uint16_t byteshift; + uint16_t i; + uint8_t bitshift; + uint16_t t=0; + byteshift = (shift+3)/8; + bitshift = shift&7; + memmove(a->wordv+byteshift, a->wordv, a->length_B); + memset(a->wordv, 0, byteshift); + if(bitshift!=0){ + if(bitshift<=4){ /* shift to the left */ + for(i=byteshift; ilength_B+byteshift; ++i){ + t |= (a->wordv[i])<wordv[i] = (uint8_t)t; + t >>= 8; + } + a->wordv[i] = (uint8_t)t; + byteshift++; + }else{ /* shift to the right */ + 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])<<(bitshift); + a->wordv[i] = (uint8_t)(t>>8); + } + } + a->length_B += byteshift; + bigint_adjust(a); +} + +/******************************************************************************/ + +void bigint_shiftright(bigint_t* a, uint16_t shift){ + uint16_t byteshift; + uint16_t i; + uint8_t bitshift; + uint16_t t=0; + byteshift = shift/8; + bitshift = shift&7; + if(byteshift >= a->length_B){ /* we would shift out more than we have */ + bigint_set_zero(a); + return; + } + if(byteshift == a->length_B-1 && bitshift>GET_FBS(a)){ + bigint_set_zero(a); + return; + } + if(byteshift){ + memmove(a->wordv, a->wordv+byteshift, a->length_B-byteshift); + memset(a->wordv+a->length_B-byteshift, 0, byteshift); + } + if(bitshift!=0){ + /* shift to the right */ + for(i=a->length_B-byteshift-1; i>0; --i){ + t |= (a->wordv[i])<<(8-bitshift); + a->wordv[i] = (uint8_t)(t>>8); + t <<= 8; + } + t |= (a->wordv[0])<<(8-bitshift); + a->wordv[0] = (uint8_t)(t>>8); + } + a->length_B -= byteshift; + bigint_adjust(a); +} + +/******************************************************************************/ + +void bigint_xor(bigint_t* dest, const bigint_t* a){ + uint16_t i; + for(i=0; ilength_B; ++i){ + dest->wordv[i] ^= a->wordv[i]; + } + bigint_adjust(dest); +} + +/******************************************************************************/ + +void bigint_set_zero(bigint_t* a){ + a->length_B=0; +} + +/******************************************************************************/ + +/* 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]; + d.wordv = d_b; + bigint_mul_u(&d, a, b); + bigint_copy(dest, &d); + return; + } + if(a->length_B==1 || b->length_B==1){ + if(a->length_B!=1){ + XCHG_PTR(a,b); + } + uint16_t i, t=0; + uint8_t x = a->wordv[0]; + for(i=0; ilength_B; ++i){ + t += b->wordv[i]*x; + dest->wordv[i] = (uint8_t)t; + t>>=8; + } + dest->wordv[i] = (uint8_t)t; + dest->length_B=i+1; + bigint_adjust(dest); + return; + } + if(a->length_B<=4 && b->length_B<=4){ + uint32_t p=0, q=0; + uint64_t r; + memcpy(&p, a->wordv, a->length_B); + memcpy(&q, b->wordv, b->length_B); + r = (uint64_t)p*(uint64_t)q; + memcpy(dest->wordv, &r, a->length_B+b->length_B); + dest->length_B = a->length_B+b->length_B; + bigint_adjust(dest); + return; + } + bigint_set_zero(dest); + /* split a in xh & xl; split b in yh & yl */ + uint16_t n; + n=(MAX(a->length_B, b->length_B)+1)/2; + bigint_t xl, xh, yl, yh; + xl.wordv = a->wordv; + yl.wordv = b->wordv; + if(a->length_B<=n){ + xh.info=0; + xh.length_B = 0; + xl.length_B = a->length_B; + xl.info = 0; + }else{ + xl.length_B=n; + xl.info = 0; + bigint_adjust(&xl); + xh.wordv = a->wordv+n; + xh.length_B = a->length_B-n; + xh.info = 0; + } + if(b->length_B<=n){ + yh.info=0; + yh.length_B = 0; + yl.length_B = b->length_B; + yl.info = b->info; + }else{ + yl.length_B=n; + yl.info = 0; + bigint_adjust(&yl); + yh.wordv = b->wordv+n; + yh.length_B = b->length_B-n; + yh.info = 0; + } + /* 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; + tmp.wordv = tmp_b; + tmp2.wordv = tmp_b+n+1; + m.wordv = m_b; + + bigint_mul_u(dest, &xl, &yl); /* dest <= xl*yl */ + bigint_add_u(&tmp2, &xh, &xl); /* tmp2 <= xh+xl */ + bigint_add_u(&tmp, &yh, &yl); /* tmp <= yh+yl */ + bigint_mul_u(&m, &tmp2, &tmp); /* m <= tmp2*tmp */ + bigint_mul_u(&tmp, &xh, &yh); /* h <= xh*yh */ + bigint_sub_u(&m, &m, dest); /* m <= m-dest */ + bigint_sub_u(&m, &m, &tmp); /* m <= m-h */ + bigint_add_scale_u(dest, &m, n); + bigint_add_scale_u(dest, &tmp, 2*n); +} + +/******************************************************************************/ + +void bigint_mul_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + uint8_t s; + s = GET_SIGN(a)?2:0; + s |= GET_SIGN(b)?1:0; + switch(s){ + case 0: /* both positive */ + bigint_mul_u(dest, a,b); + SET_POS(dest); + break; + case 1: /* a positive, b negative */ + bigint_mul_u(dest, a,b); + SET_NEG(dest); + break; + case 2: /* a negative, b positive */ + bigint_mul_u(dest, a,b); + SET_NEG(dest); + break; + case 3: /* both negative */ + bigint_mul_u(dest, a,b); + SET_POS(dest); + break; + default: /* how can this happen?*/ + break; + } +} + +/******************************************************************************/ + +/* square */ +/* (xh*b^n+xl)^2 = xh^2*b^2n + 2*xh*xl*b^n + xl^2 */ +void bigint_square(bigint_t* dest, const bigint_t* a){ + if(a->length_B<=4){ + uint64_t r=0; + memcpy(&r, a->wordv, a->length_B); + r = r*r; + memcpy(dest->wordv, &r, 2*a->length_B); + SET_POS(dest); + dest->length_B=2*a->length_B; + bigint_adjust(dest); + return; + } + if(dest==a){ + bigint_t d; + uint8_t d_b[a->length_B*2]; + d.wordv = d_b; + bigint_square(&d, a); + bigint_copy(dest, &d); + return; + } + uint16_t n; + n=(a->length_B+1)/2; + bigint_t xh, xl, tmp; /* x-high, x-low, temp */ + uint8_t buffer[2*n+1]; + xl.wordv = a->wordv; + xl.length_B = n; + xh.wordv = a->wordv+n; + xh.length_B = a->length_B-n; + tmp.wordv = buffer; + bigint_square(dest, &xl); + bigint_square(&tmp, &xh); + bigint_add_scale_u(dest, &tmp, 2*n); + 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){ + 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){ + 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){ +// bigint_adjust(r); + uint8_t rfbs = GET_FBS(r); + + 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); + } + bigint_adjust(a); +} + +/******************************************************************************/ + +/* 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){ + if(a->length_B==0 || r->length_B==0){ + return; + } + + 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+1length_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; + } + } + 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; + } + SET_POS(&res); + bigint_copy(dest, &res); +} + +/******************************************************************************/ +/* gcd <-- gcd(x,y) a*x+b*y=gcd */ +void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, const bigint_t* y){ + bigint_t g, x_, y_, u, v, a_, b_, c_, d_; + volatile uint16_t i=0; + if(x->length_B==0 || y->length_B==0){ + return; + } + while(x->wordv[i]==0 && y->wordv[i]==0){ + ++i; + } + uint8_t g_b[i+2], x_b[x->length_B-i], y_b[y->length_B-i]; + uint8_t u_b[x->length_B-i], v_b[y->length_B-i]; + uint8_t a_b[y->length_B+2], c_b[y->length_B+2]; + uint8_t b_b[x->length_B+2], d_b[x->length_B+2]; + + g.wordv = g_b; + x_.wordv = x_b; + y_.wordv = y_b; + memset(g_b, 0, i); + g_b[i]=1; + g.length_B = i+1; + g.info=0; + x_.info = y_.info = 0; + x_.length_B = x->length_B-i; + y_.length_B = y->length_B-i; + memcpy(x_.wordv, x->wordv+i, x_.length_B); + memcpy(y_.wordv, y->wordv+i, y_.length_B); + for(i=0; (x_.wordv[0]&(1<=0){ + bigint_sub_u(&u, &u, &v); + bigint_sub_s(&a_, &a_, &c_); + bigint_sub_s(&b_, &b_, &d_); + }else{ + bigint_sub_u(&v, &v, &u); + bigint_sub_s(&c_, &c_, &a_); + bigint_sub_s(&d_, &d_, &b_); + } + }while(u.length_B); + if(gcd){ + bigint_mul_s(gcd, &v, &g); + } + if(a){ + bigint_copy(a, &c_); + } + if(b){ + bigint_copy(b, &d_); + } +} + +/******************************************************************************/ + +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. +*/ +/** + * \file bigint.c + * \author Daniel Otte + * \date 2010-02-22 + * + * \license GPLv3 or later + * + */ + + +#define STRING2(x) #x +#define STRING(x) STRING2(x) +#define STR_LINE STRING(__LINE__) + +#include "bigint.h" +#include + +#define DEBUG 1 + +#if DEBUG +#include "cli.h" +#include "uart_lowlevel.h" +#include "bigint_io.h" +#endif + +#ifndef MAX + #define MAX(a,b) (((a)>(b))?(a):(b)) +#endif + +#ifndef MIN + #define MIN(a,b) (((a)<(b))?(a):(b)) +#endif + +#define SET_FBS(a, v) do{(a)->info &=~BIGINT_FBS_MASK; (a)->info |= (v);}while(0) +#define GET_FBS(a) ((a)->info&BIGINT_FBS_MASK) +#define SET_NEG(a) (a)->info |= BIGINT_NEG_MASK +#define SET_POS(a) (a)->info &= ~BIGINT_NEG_MASK +#define XCHG(a,b) do{(a)^=(b); (b)^=(a); (a)^=(b);}while(0) +#define XCHG_PTR(a,b) do{ a = (void*)(((uint32_t)(a)) ^ ((uint32_t)(b))); \ + b = (void*)(((uint32_t)(a)) ^ ((uint32_t)(b))); \ + a = (void*)(((uint32_t)(a)) ^ ((uint32_t)(b)));}while(0) + +#define GET_SIGN(a) ((a)->info&BIGINT_NEG_MASK) + +/******************************************************************************/ +void bigint_adjust(bigint_t* a){ + while(a->length_B!=0 && a->wordv[a->length_B-1]==0){ + a->length_B--; + } + if(a->length_B==0){ + a->info=0; + return; + } + bigint_word_t t; + uint8_t i = BIGINT_WORD_SIZE-1; + t = a->wordv[a->length_B-1]; + while((t&(1<<(BIGINT_WORD_SIZE-1)))==0 && i){ + t<<=1; + i--; + } + SET_FBS(a, i); +} + +/******************************************************************************/ + +void bigint_copy(bigint_t* dest, const bigint_t* src){ + memcpy(dest->wordv, src->wordv, src->length_B*sizeof(bigint_word_t)); + dest->length_B = src->length_B; + dest->info = src->info; +} + +/******************************************************************************/ + +/* this should be implemented in assembly */ +void bigint_add_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + uint16_t i; + bigint_wordplus_t t=0LL; + if(a->length_B < b->length_B){ + XCHG_PTR(a,b); + } + for(i=0; ilength_B; ++i){ +// t = (bigint_wordplus_t)(a->wordv[i]) + (bigint_wordplus_t)(b->wordv[i]) + t; + t += a->wordv[i]; + t += b->wordv[i]; + dest->wordv[i] = (bigint_word_t)t; + t>>=BIGINT_WORD_SIZE; + } + for(; ilength_B; ++i){ + t += a->wordv[i]; + dest->wordv[i] = (bigint_word_t)t; + t>>=BIGINT_WORD_SIZE; + } + dest->wordv[i++] = (bigint_word_t)t; + dest->length_B = i; + bigint_adjust(dest); +} + +/******************************************************************************/ + +/* this should be implemented in assembly */ +void bigint_add_scale_u(bigint_t* dest, const bigint_t* a, uint16_t scale){ + uint16_t i,j=0; + uint16_t scale_w; + uint32_t *dst; + bigint_wordplus_t t=0; + scale_w = (scale+sizeof(bigint_word_t)-1)/sizeof(bigint_word_t); + if(scale>dest->length_B*sizeof(bigint_word_t)){ + memset(((uint8_t*)dest->wordv)+dest->length_B*sizeof(bigint_word_t), 0, scale-dest->length_B*sizeof(bigint_word_t)); + } + // a->wordv = (const uint32_t*)(((uint8_t*)a->wordv)+(scale&3)); + dst = dest->wordv + (scale&(sizeof(bigint_word_t)-1)); + for(i=scale/sizeof(bigint_word_t); ilength_B+scale_w; ++i,++j){ + t += a->wordv[j]; + if(dest->length_B>i){ + t += dst[i]; + } + dst[i] = (bigint_word_t)t; + t>>=BIGINT_WORD_SIZE; + } + while(t){ + if(dest->length_B>i){ + t += dst[i]; + } + dst[i] = (bigint_word_t)t; + t>>=BIGINT_WORD_SIZE; + ++i; + } + if(dest->length_B < i){ + dest->length_B = i; + } + bigint_adjust(dest); +} + +/******************************************************************************/ + +/* this should be implemented in assembly */ +void bigint_sub_u(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + int8_t borrow=0; + int8_t r; + bigint_wordplus_signed_t t=0LL; + uint16_t i, min, max; + min = MIN(a->length_B, b->length_B); + max = MAX(a->length_B, b->length_B); + r = bigint_cmp_u(a,b); + if(r==0){ + bigint_set_zero(dest); + return; + } + if(b->length_B==0){ + bigint_copy(dest, a); + SET_POS(dest); + return; + } + if(a->length_B==0){ + bigint_copy(dest, b); + SET_NEG(dest); + return; + } + if(r<0){ + bigint_sub_u(dest, b, a); + SET_NEG(dest); + }else{ + for(i=0; iwordv[i]; + t -= b->wordv[i]; + t -= borrow; + if(t<0){ + borrow = 1; + dest->wordv[i]=(bigint_word_t)t; + }else{ + borrow = 0; + dest->wordv[i]=(bigint_word_t)t; + } + } + for(;iwordv[i] - borrow; + if(t<0){ + borrow = 1; + dest->wordv[i]=(bigint_word_t)t; + }else{ + borrow = 0; + dest->wordv[i]=(bigint_word_t)t; + } + + } + SET_POS(dest); + dest->length_B = i; + bigint_adjust(dest); + } +} + +/******************************************************************************/ + +int8_t bigint_cmp_u(const bigint_t* a, const bigint_t* b){ + if(a->length_B > b->length_B){ + return 1; + } + if(a->length_B < b->length_B){ + return -1; + } + if(a->length_B==0){ + return 0; + } + uint16_t i; + i = a->length_B-1; + do{ + if(a->wordv[i]!=b->wordv[i]){ + if(a->wordv[i]>b->wordv[i]){ + return 1; + }else{ + return -1; + } + } + }while(i--); + return 0; +} + +/******************************************************************************/ + +void bigint_add_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + uint8_t s; + s = GET_SIGN(a)?2:0; + s |= GET_SIGN(b)?1:0; + switch(s){ + case 0: /* both positive */ + bigint_add_u(dest, a,b); + SET_POS(dest); + break; + case 1: /* a positive, b negative */ + bigint_sub_u(dest, a, b); + break; + case 2: /* a negative, b positive */ + bigint_sub_u(dest, b, a); + break; + case 3: /* both negative */ + bigint_add_u(dest, a, b); + SET_NEG(dest); + break; + default: /* how can this happen?*/ + break; + } +} + +/******************************************************************************/ + +void bigint_sub_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + uint8_t s; + s = GET_SIGN(a)?2:0; + s |= GET_SIGN(b)?1:0; + switch(s){ + case 0: /* both positive */ + bigint_sub_u(dest, a,b); + break; + case 1: /* a positive, b negative */ + bigint_add_u(dest, a, b); + SET_POS(dest); + break; + case 2: /* a negative, b positive */ + bigint_add_u(dest, a, b); + SET_NEG(dest); + break; + case 3: /* both negative */ + bigint_sub_u(dest, b, a); + break; + default: /* how can this happen?*/ + break; + } + +} + +/******************************************************************************/ + +int8_t bigint_cmp_s(const bigint_t* a, const bigint_t* b){ + uint8_t s; + if(a->length_B==0 && b->length_B==0){ + return 0; + } + s = GET_SIGN(a)?2:0; + s |= GET_SIGN(b)?1:0; + switch(s){ + case 0: /* both positive */ + return bigint_cmp_u(a, b); + break; + case 1: /* a positive, b negative */ + return 1; + break; + case 2: /* a negative, b positive */ + return -1; + break; + case 3: /* both negative */ + return bigint_cmp_u(b, a); + break; + default: /* how can this happen?*/ + break; + } + return 0; /* just to satisfy the compiler */ +} + +/******************************************************************************/ + +void bigint_shiftleft(bigint_t* a, uint16_t shift){ + uint16_t byteshift, word_alloc; + int16_t i; + uint8_t bitshift; + bigint_word_t *p; + bigint_wordplus_t t=0; + if(shift==0){ + return; + } + byteshift = shift/8; + bitshift = shift&7; + for(i=0;i<=byteshift/sizeof(bigint_word_t); ++i){ + a->wordv[a->length_B+i] = 0; + } + if(byteshift){ + memmove(((uint8_t*)a->wordv)+byteshift, a->wordv, a->length_B*sizeof(bigint_word_t)); + memset(a->wordv, 0, byteshift); + } + p = (bigint_word_t*)(((uint8_t*)a->wordv)+byteshift); + word_alloc = a->length_B+(byteshift+sizeof(bigint_word_t)-1)/sizeof(bigint_word_t)+1; + a->wordv[word_alloc-1]=0; + if(bitshift!=0){ + for(i=0; ilength_B; ++i){ + t |= ((bigint_wordplus_t)p[i])<>= BIGINT_WORD_SIZE; + } + p[i] = (bigint_word_t)t; + } + a->length_B = word_alloc; + bigint_adjust(a); +} + +/******************************************************************************/ + +void bigint_shiftright(bigint_t* a, uint16_t shift){ + uint16_t byteshift; + uint16_t i; + uint8_t bitshift; + bigint_wordplus_t t=0; + byteshift = shift/8; + bitshift = shift&7; + if(byteshift >= a->length_B*sizeof(bigint_word_t)){ /* we would shift out more than we have */ + bigint_set_zero(a); + return; + } + if(byteshift == a->length_B*sizeof(bigint_word_t)-1 && bitshift>GET_FBS(a)){ + bigint_set_zero(a); + return; + } + if(byteshift){ + memmove(a->wordv, (uint8_t*)a->wordv+byteshift, a->length_B-byteshift); + memset((uint8_t*)a->wordv+a->length_B-byteshift, 0, byteshift); + } + byteshift /= sizeof(bigint_word_t); + if(bitshift!=0){ + /* shift to the right */ + for(i=a->length_B-byteshift-1; i>0; --i){ + t |= ((bigint_wordplus_t)(a->wordv[i]))<<(BIGINT_WORD_SIZE-bitshift); + a->wordv[i] = (bigint_word_t)(t>>BIGINT_WORD_SIZE); + t <<= BIGINT_WORD_SIZE; + } + t |= ((bigint_wordplus_t)(a->wordv[0]))<<(BIGINT_WORD_SIZE-bitshift); + a->wordv[0] = (bigint_word_t)(t>>BIGINT_WORD_SIZE); + } + a->length_B -= ((shift/8)+sizeof(bigint_word_t)-1)/sizeof(bigint_word_t); + bigint_adjust(a); +} + +/******************************************************************************/ + +void bigint_xor(bigint_t* dest, const bigint_t* a){ + uint16_t i; + for(i=0; ilength_B; ++i){ + dest->wordv[i] ^= a->wordv[i]; + } + bigint_adjust(dest); +} + +/******************************************************************************/ + +void bigint_set_zero(bigint_t* a){ + a->length_B=0; +} + +/******************************************************************************/ + +/* 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; + bigint_word_t d_b[a->length_B+b->length_B]; + d.wordv = d_b; + bigint_mul_u(&d, a, b); + bigint_copy(dest, &d); + return; + } + if(a->length_B==1 || b->length_B==1){ + if(a->length_B!=1){ + XCHG_PTR(a,b); + } + bigint_wordplus_t i, t=0; + bigint_word_t x = a->wordv[0]; + for(i=0; ilength_B; ++i){ + t += ((bigint_wordplus_t)b->wordv[i])*((bigint_wordplus_t)x); + dest->wordv[i] = (bigint_word_t)t; + t>>=BIGINT_WORD_SIZE; + } + dest->wordv[i] = (bigint_word_t)t; + dest->length_B=i+1; + bigint_adjust(dest); + return; + } + if(a->length_B<=4/sizeof(bigint_word_t) && b->length_B<=4/sizeof(bigint_word_t)){ + uint32_t p=0, q=0; + uint64_t r; + memcpy(&p, a->wordv, a->length_B*sizeof(bigint_word_t)); + memcpy(&q, b->wordv, b->length_B*sizeof(bigint_word_t)); + r = (uint64_t)p*(uint64_t)q; + memcpy(dest->wordv, &r, (a->length_B+b->length_B)*sizeof(bigint_word_t)); + dest->length_B = a->length_B+b->length_B; + bigint_adjust(dest); + return; + } + bigint_set_zero(dest); + /* split a in xh & xl; split b in yh & yl */ + uint16_t n; + n=(MAX(a->length_B, b->length_B)+1)/2; + bigint_t xl, xh, yl, yh; + xl.wordv = a->wordv; + yl.wordv = b->wordv; + if(a->length_B<=n){ + xh.info=0; + xh.length_B = 0; + xl.length_B = a->length_B; + xl.info = 0; + }else{ + xl.length_B=n; + xl.info = 0; + bigint_adjust(&xl); + xh.wordv = a->wordv+n; + xh.length_B = a->length_B-n; + xh.info = 0; + } + if(b->length_B<=n){ + yh.info=0; + yh.length_B = 0; + yl.length_B = b->length_B; + yl.info = b->info; + }else{ + yl.length_B=n; + yl.info = 0; + bigint_adjust(&yl); + yh.wordv = b->wordv+n; + yh.length_B = b->length_B-n; + yh.info = 0; + } + /* now we have split up a and b */ + bigint_word_t tmp_b[2*n+2], m_b[2*(n+1)]; + bigint_t tmp, tmp2, m; + tmp.wordv = tmp_b; + tmp2.wordv = tmp_b+n+1; + m.wordv = m_b; + + bigint_mul_u(dest, &xl, &yl); /* dest <= xl*yl */ + bigint_add_u(&tmp2, &xh, &xl); /* tmp2 <= xh+xl */ + bigint_add_u(&tmp, &yh, &yl); /* tmp <= yh+yl */ + bigint_mul_u(&m, &tmp2, &tmp); /* m <= tmp2*tmp */ + bigint_mul_u(&tmp, &xh, &yh); /* h <= xh*yh */ + bigint_sub_u(&m, &m, dest); /* m <= m-dest */ + bigint_sub_u(&m, &m, &tmp); /* m <= m-h */ + bigint_add_scale_u(dest, &m, n*sizeof(bigint_word_t)); + bigint_add_scale_u(dest, &tmp, 2*n*sizeof(bigint_word_t)); +} + +/******************************************************************************/ + +void bigint_mul_s(bigint_t* dest, const bigint_t* a, const bigint_t* b){ + uint8_t s; + s = GET_SIGN(a)?2:0; + s |= GET_SIGN(b)?1:0; + switch(s){ + case 0: /* both positive */ + bigint_mul_u(dest, a,b); + SET_POS(dest); + break; + case 1: /* a positive, b negative */ + bigint_mul_u(dest, a,b); + SET_NEG(dest); + break; + case 2: /* a negative, b positive */ + bigint_mul_u(dest, a,b); + SET_NEG(dest); + break; + case 3: /* both negative */ + bigint_mul_u(dest, a,b); + SET_POS(dest); + break; + default: /* how can this happen?*/ + break; + } +} + +/******************************************************************************/ + +/* square */ +/* (xh*b^n+xl)^2 = xh^2*b^2n + 2*xh*xl*b^n + xl^2 */ +void bigint_square(bigint_t* dest, const bigint_t* a){ + if(a->length_B*sizeof(bigint_word_t)<=4){ + uint64_t r=0; + memcpy(&r, a->wordv, a->length_B*sizeof(bigint_word_t)); + r = r*r; + memcpy(dest->wordv, &r, 2*a->length_B*sizeof(bigint_word_t)); + SET_POS(dest); + dest->length_B=2*a->length_B; + bigint_adjust(dest); + return; + } + if(dest==a){ + bigint_t d; + bigint_word_t d_b[a->length_B*2]; + d.wordv = d_b; + bigint_square(&d, a); + bigint_copy(dest, &d); + return; + } + uint16_t n; + n=(a->length_B+1)/2; + bigint_t xh, xl, tmp; /* x-high, x-low, temp */ + bigint_word_t buffer[2*n+1]; + xl.wordv = a->wordv; + xl.length_B = n; + xh.wordv = &(a->wordv[n]); + xh.length_B = a->length_B-n; + tmp.wordv = buffer; +// cli_putstr("\r\nDBG (a): xl: "); bigint_print_hex(&xl); +// cli_putstr("\r\nDBG (b): xh: "); bigint_print_hex(&xh); + bigint_square(dest, &xl); +// cli_putstr("\r\nDBG (1): xl**2: "); bigint_print_hex(dest); + bigint_square(&tmp, &xh); +// cli_putstr("\r\nDBG (2): xh**2: "); bigint_print_hex(&tmp); + bigint_add_scale_u(dest, &tmp, 2*n*sizeof(bigint_word_t)); +// cli_putstr("\r\nDBG (3): xl**2 + xh**2*n**2: "); bigint_print_hex(dest); + bigint_mul_u(&tmp, &xl, &xh); +// cli_putstr("\r\nDBG (4): xl*xh: "); bigint_print_hex(&tmp); + bigint_shiftleft(&tmp, 1); +// cli_putstr("\r\nDBG (5): xl*xh*2: "); bigint_print_hex(&tmp); + bigint_add_scale_u(dest, &tmp, n*sizeof(bigint_word_t)); +// cli_putstr("\r\nDBG (6): x**2: "); bigint_print_hex(dest); +// cli_putstr("\r\n"); +} + +/******************************************************************************/ + +#define cli_putstr(a) +#define bigint_print_hex(a) +#define cli_hexdump_rev(a,b) +#define uart_flush(a) + +void bigint_sub_u_bitscale(bigint_t* a, const bigint_t* b, uint16_t bitscale){ + bigint_t tmp; + bigint_word_t tmp_b[b->length_B+4]; + uint16_t i,j,word_shift=bitscale/(8*sizeof(bigint_word_t)); + uint8_t borrow=0; + bigint_wordplus_signed_t t; + + if(a->length_B < b->length_B+word_shift){ + cli_putstr("\r\nDBG: *bang*\r\n"); + bigint_set_zero(a); + return; + } + tmp.wordv = tmp_b; + bigint_copy(&tmp, b); + bigint_shiftleft(&tmp, bitscale&(BIGINT_WORD_SIZE-1)); + cli_putstr("\r\nDBG(sub_ub.0) tmp_shift = "); bigint_print_hex(&tmp); + for(j=0,i=word_shift; iwordv[i]; + t -= tmp.wordv[j]; + t -= borrow; + a->wordv[i] = (bigint_word_t)t; + if(t<0){ + borrow = 1; + }else{ + borrow = 0; + } + } + while(borrow){ + if(i+1 > a->length_B){ + cli_putstr("\r\nDBG: *boom*\r\n"); + 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){ +// bigint_adjust(r); + uint8_t rfbs = GET_FBS(r); + + cli_putstr("\r\nDBG: (a) = "); bigint_print_hex(a); + if(r->length_B==0 || a->length_B==0){ + return; + } + if((r->length_B*sizeof(bigint_word_t)<=4) && (a->length_B*sizeof(bigint_word_t)<=4)){ + uint32_t p=0, q=0; + memcpy(&p, a->wordv, a->length_B*sizeof(bigint_word_t)); + memcpy(&q, r->wordv, r->length_B*sizeof(bigint_word_t)); + p %= q; + memcpy(a->wordv, &p, a->length_B*sizeof(bigint_word_t)); + bigint_adjust(a); + cli_putstr("\r\nDBG: (0) = "); bigint_print_hex(a); + return; + } + uint16_t shift; + while(a->length_B > r->length_B){ + shift = (a->length_B-r->length_B)*8*sizeof(bigint_word_t)+GET_FBS(a)-rfbs-1; + cli_putstr("\r\nDBG: (p) shift = "); cli_hexdump_rev(&shift, 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+1) && (a->length_B == r->length_B)){ + shift = GET_FBS(a)-rfbs-1; + cli_putstr("\r\nDBG: (q) shift = "); cli_hexdump_rev(&shift, 2); + bigint_sub_u_bitscale(a, r, GET_FBS(a)-rfbs-1); + cli_putstr("\r\nDBG: (2) = "); bigint_print_hex(a); + } + while(bigint_cmp_u(a,r)>=0){ + bigint_sub_u(a,a,r); + cli_putstr("\r\nDBG: (3) = "); bigint_print_hex(a); + } + bigint_adjust(a); + cli_putstr("\r\nDBG: (a) = "); bigint_print_hex(a); + cli_putstr("\r\n"); +} + +/******************************************************************************/ + +/* 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){ + if(a->length_B==0 || r->length_B==0){ + return; + } + + bigint_t res, base; + bigint_word_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+1length_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; + } + } + 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; + } + SET_POS(&res); + bigint_copy(dest, &res); +} + +/******************************************************************************/ +/* gcd <-- gcd(x,y) a*x+b*y=gcd */ +void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, const bigint_t* y){ + bigint_t g, x_, y_, u, v, a_, b_, c_, d_; + volatile uint16_t i=0; + if(x->length_B==0 || y->length_B==0){ + return; + } + while(x->wordv[i]==0 && y->wordv[i]==0){ + ++i; + } + bigint_word_t g_b[i+2], x_b[x->length_B-i], y_b[y->length_B-i]; + bigint_word_t u_b[x->length_B-i], v_b[y->length_B-i]; + bigint_word_t a_b[y->length_B+2], c_b[y->length_B+2]; + bigint_word_t b_b[x->length_B+2], d_b[x->length_B+2]; + + g.wordv = g_b; + x_.wordv = x_b; + y_.wordv = y_b; + memset(g_b, 0, i); + g_b[i]=1; + g.length_B = i+1; + g.info=0; + x_.info = y_.info = 0; + x_.length_B = x->length_B-i; + y_.length_B = y->length_B-i; + memcpy(x_.wordv, x->wordv+i, x_.length_B); + memcpy(y_.wordv, y->wordv+i, y_.length_B); + for(i=0; (x_.wordv[0]&(1<=0){ + bigint_sub_u(&u, &u, &v); + bigint_sub_s(&a_, &a_, &c_); + bigint_sub_s(&b_, &b_, &d_); + }else{ + bigint_sub_u(&v, &v, &u); + bigint_sub_s(&c_, &c_, &a_); + bigint_sub_s(&d_, &d_, &b_); + } + }while(u.length_B); + if(gcd){ + bigint_mul_s(gcd, &v, &g); + } + if(a){ + bigint_copy(a, &c_); + } + if(b){ + bigint_copy(b, &d_); + } +} + +/******************************************************************************/ + +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 = (uint8_t*)(a->wordv); + q = ((uint8_t*)p)+a->length_B*sizeof(bigint_word_t)-1; + while(p. +*/ +/** + * \file bigint.h + * \author Daniel Otte + * \date 2010-02-22 + * + * \license GPLv3 or later + * + */ + +#ifndef BIGINT_H_ +#define BIGINT_H_ + +#include + +typedef uint32_t bigint_word_t; +typedef uint64_t bigint_wordplus_t; +typedef int64_t bigint_wordplus_signed_t; +#define BIGINT_WORD_SIZE 32 + +#define BIGINT_FBS_MASK (BIGINT_WORD_SIZE-1) /* the last five bits indicate which is the first bit set */ +#define BIGINT_NEG_MASK 0x80 /* this bit indicates a negative value */ +typedef struct{ + uint16_t length_B; + uint8_t info; + bigint_word_t *wordv; /* word vector, pointing to the LSB */ +}bigint_t; + + + +/******************************************************************************/ + +void bigint_adjust(bigint_t* a); +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); +int8_t bigint_cmp_u(const bigint_t * a, const bigint_t * b); +void bigint_add_s(bigint_t* dest, const bigint_t* a, const bigint_t* b); +void bigint_sub_s(bigint_t* dest, const bigint_t* a, const bigint_t* b); +int8_t bigint_cmp_s(const bigint_t* a, const bigint_t* b); +void bigint_shiftleft(bigint_t* a, uint16_t shift); +void bigint_shiftright(bigint_t* a, uint16_t shift); +void bigint_xor(bigint_t* dest, const bigint_t* a); +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); +void bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r); +void bigint_gcdext(bigint_t* gcd, bigint_t* a, bigint_t* b, const bigint_t* x, const bigint_t* y); +void bigint_inverse(bigint_t* dest, const bigint_t* a, const bigint_t* m); +void bigint_changeendianess(bigint_t* a); +/******************************************************************************/ + +#endif /*BIGINT_H_*/ diff --git a/bigint/bigint_io.c b/bigint/bigint_io.c new file mode 100644 index 0000000..d0dde86 --- /dev/null +++ b/bigint/bigint_io.c @@ -0,0 +1,159 @@ +/* bigint_io.c */ +/* + This file is part of the AVR-Crypto-Lib. + Copyright (C) 2010 Daniel Otte (daniel.otte@rub.de) + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#include "cli.h" +#include "hexdigit_tab.h" +#include "bigint.h" +#include +#include + +void bigint_print_hex(const bigint_t* a){ + if(a->length_B==0){ + cli_putc('0'); + return; + } + if(a->info&BIGINT_NEG_MASK){ + cli_putc('-'); + } +// cli_putc((a->info&BIGINT_NEG_MASK)?'-':'+'); /* print sign */ +/* if(a->wordv[a->length_B-1]<0x10){ + cli_putc(hexdigit_tab_uc[a->wordv[a->length_B-1]]); + cli_hexdump_rev(a->wordv, a->length_B-1); + } else { +*/ + // cli_hexdump_rev(a->wordv, a->length_B*sizeof(bigint_word_t)); +// } + uint32_t idx; + uint8_t print_zero=0; + uint8_t *p,x,y; + p = (uint8_t*)&(a->wordv[a->length_B-1])+sizeof(bigint_word_t)-1; + for(idx=a->length_B*sizeof(bigint_word_t); idx>0; --idx){ + x = *p >> 4; + y = *p & 0xf; + if(x!=0 || print_zero!=0){ + cli_putc(hexdigit_tab_lc[x]); + } + if(x){ + print_zero = 1; + } + if(y!=0 || print_zero!=0){ + cli_putc(hexdigit_tab_lc[y]); + } + if(y){ + print_zero = 1; + } + --p; + } +} + +#define BLOCKSIZE 32 + +static uint8_t char2nibble(char c){ + if(c>='0' && c <='9'){ + return c-'0'; + } + c |= 'A'^'a'; /* to lower case */ + if(c>='a' && c <='f'){ + return c-'a'+10; + } + return 0xff; +} + +static uint16_t read_byte(void){ + uint8_t t1, t2; + char c; + c = cli_getc_cecho(); + if(c=='-'){ + return 0x0500; + } + t1 = char2nibble(c); + if(t1 == 0xff){ + return 0x0100; + } + c = cli_getc_cecho(); + t2 = char2nibble(c); + if(t2 == 0xff){ + return 0x0200|t1; + } + return (t1<<4)|t2; +} + +uint8_t bigint_read_hex_echo(bigint_t* a){ + uint16_t allocated=0; + uint8_t shift4=0; + uint16_t t; + a->length_B = 0; + a->wordv = NULL; + a->info = 0; + for(;;){ + if(allocated-a->length_B < 1){ + bigint_word_t *p; + p = realloc(a->wordv, allocated+=BLOCKSIZE); + if(p==NULL){ + cli_putstr("\r\nERROR: Out of memory!"); + free(a->wordv); + return 0xff; + } + memset((uint8_t*)p+allocated-BLOCKSIZE, 0, BLOCKSIZE); + a->wordv=p; + } + t = read_byte(); + if(a->length_B==0){ + if(t&0x0400){ + /* got minus */ + a->info |= BIGINT_NEG_MASK; + continue; + }else{ + if(t==0x0100){ + free(a->wordv); + a->wordv=NULL; + return 1; + } + } + } + if(t<=0x00ff){ + ((uint8_t*)(a->wordv))[a->length_B++] = (uint8_t)t; + }else{ + if(t&0x0200){ + shift4 = 1; + ((uint8_t*)(a->wordv))[a->length_B++] = (uint8_t)((t&0x0f)<<4); + } + break; + } + } + /* we have to reverse the byte array */ + uint8_t tmp; + uint8_t *p, *q; + p = (uint8_t*)(a->wordv); + q = (uint8_t*)a->wordv+a->length_B-1; + while(q>p){ + tmp = *p; + *p = *q; + *q = tmp; + p++; q--; + } + a->length_B = (a->length_B+sizeof(bigint_word_t)-1)/sizeof(bigint_word_t); + if(shift4){ + bigint_adjust(a); + bigint_shiftright(a, 4); + }else{ + bigint_adjust(a); + } + return 0; +} diff --git a/bigint/bigint_io.h b/bigint/bigint_io.h new file mode 100644 index 0000000..e47391d --- /dev/null +++ b/bigint/bigint_io.h @@ -0,0 +1,28 @@ +/* bigint_io.h */ +/* + This file is part of the AVR-Crypto-Lib. + Copyright (C) 2010 Daniel Otte (daniel.otte@rub.de) + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#ifndef BIGINT_IO_H_ +#define BIGINT_IO_H_ + +#include "bigint.h" + +void bigint_print_hex(const bigint_t* a); +uint8_t bigint_read_hex_echo(bigint_t* a); + +#endif /* BIGINT_IO_H_ */ diff --git a/host/bigint_test.rb b/host/bigint_test.rb index 78de1a1..2ef9616 100644 --- a/host/bigint_test.rb +++ b/host/bigint_test.rb @@ -1,7 +1,7 @@ #!/usr/bin/ruby # bigint_test.rb =begin - This file is part of the ARM-Crypto-Lib. + This file is part of the AVR-Crypto-Lib. Copyright (C) 2008, 2009 Daniel Otte (daniel.otte@rub.de) This program is free software: you can redistribute it and/or modify @@ -246,6 +246,66 @@ def mul_test(a,b) return false end +################################################################################ +# add_scale_test # +################################################################################ + +def add_scale_test(a, b, scale) + 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 /[\s]*enter scale:[\s]*/.match(line) + $sp.print(scale.to_s(16)+"\n") + 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]*<<8\*[\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) + s_ = m[3].to_i(16) + c_ = m[4].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 + ################################################################################ # square_test # ################################################################################ @@ -311,9 +371,8 @@ def reduce_test(a,b) $sp.print(b.to_s(16)+" ") line='' begin - line_tmp = $sp.gets() - line_tmp = '' if line_tmp==nil - line += line_tmp + line = $sp.gets() + line = '' if line==nil puts("DBG got: "+line) if $debug if /^Error:.*/.match(line) puts line @@ -372,9 +431,8 @@ def expmod_test(a,b,c) $sp.print(c.to_s(16)+" ") line='' begin - line_tmp = $sp.gets() - line_tmp = '' if line_tmp==nil - line += line_tmp + line = $sp.gets() + line = '' if line==nil puts("DBG got: "+line) if $debug if /^Error:.*/.match(line) puts line diff --git a/mkfiles/bigint_c.mk b/mkfiles/bigint_c.mk new file mode 100644 index 0000000..23ce816 --- /dev/null +++ b/mkfiles/bigint_c.mk @@ -0,0 +1,14 @@ +# Makefile for BigInt +ALGO_NAME := BIGINT_C + +# comment out the following line for removement of BigInt from the build process +AUX += $(ALGO_NAME) + +$(ALGO_NAME)_DIR := bigint/ +$(ALGO_NAME)_INCDIR := memxor/ noekeon/ +$(ALGO_NAME)_OBJ := bigint.o bigint_io.o +$(ALGO_NAME)_TEST_BIN := main-bigint-test.o $(CLI_STD) \ + performance_test.o noekeon.o noekeon_prng.o memxor.o + +$(ALGO_NAME)_PERFORMANCE_TEST := performance + diff --git a/test_src/cli.c b/test_src/cli.c index 3ecdf6c..c609d9f 100644 --- a/test_src/cli.c +++ b/test_src/cli.c @@ -90,13 +90,12 @@ void cli_putstr(const char* s){ cli_tx(*s++); } - /** * \brief reads a line or max n characters from the console * Writes characters from the console into the supplied buffer until a '\r' * character is received or until n character a read (whatever happens first). * The string will always be terminated by a '\0' character, so the buffer - * should have at least a size of n+1. + * should have at least a size of n+1. */ uint8_t cli_getsn(char* s, uint32_t n){ char c; @@ -109,6 +108,22 @@ uint8_t cli_getsn(char* s, uint32_t n){ return (c=='\r')?0:1; } +/** + * \brief reads a line or max n characters from the console and echos the characters back + * Writes characters from the console into the supplied buffer until a '\r' + * character is received or until n character a read (whatever happens first). + * The string will always be terminated by a '\0' character, so the buffer + * should have at least a size of n+1. + */ +uint8_t cli_getsn_cecho(char* s, uint32_t n){ + uint8_t echo_backup,r ; + echo_backup = cli_echo; + cli_echo = 1; + r = cli_getsn(s, n); + cli_echo = echo_backup; + return r; +} + void cli_hexdump_byte(uint8_t byte){ cli_tx(hexdigit_tab[byte>>4]); cli_tx(hexdigit_tab[byte & 0xf]); @@ -309,7 +324,7 @@ uint8_t cli_completion(char* buffer, uint16_t maxcmdlength, const cmdlist_entry_ ref[0]='\0'; /* check if we are behind the first word */ while(buffer[i]){ - if(!isgraph(buffer[i++])) + if(!isgraph((uint8_t)(buffer[i++]))) return 0; } for(;;){ diff --git a/test_src/cli.h b/test_src/cli.h index 52c0159..1dab4a9 100644 --- a/test_src/cli.h +++ b/test_src/cli.h @@ -56,6 +56,7 @@ extern uint8_t cli_echo; void cli_putc(char c); uint16_t cli_getc(void); uint16_t cli_getc_cecho(void); +uint8_t cli_getsn_cecho(char* s, uint32_t n); uint8_t cli_getsn(char* s, uint32_t n); void cli_putstr(const char* s); void cli_hexdump(const void* data, uint32_t length); diff --git a/test_src/dump.c b/test_src/dump.c index 988bc87..58e26a0 100644 --- a/test_src/dump.c +++ b/test_src/dump.c @@ -70,8 +70,8 @@ void dump(char* s){ char tstr[9]; if(s){ s=strstrip(s); - if(isalpha(*s)){ - while(isalpha(*s)) + if(isalpha((uint8_t)(*s))){ + while(isalpha((uint8_t)(*s))) ++s; } char* eptr; diff --git a/test_src/hw_regs.h b/test_src/hw_regs.h index 71fb1f6..c6d859b 100644 --- a/test_src/hw_regs.h +++ b/test_src/hw_regs.h @@ -1,6 +1,6 @@ /* hw_regs.h */ /* - This file is part of the ARM-Crypto-Lib. + This file is part of the AVR-Crypto-Lib. Copyright (C) 2010 Daniel Otte (daniel.otte@rub.de) This program is free software: you can redistribute it and/or modify @@ -25,7 +25,9 @@ #define SET_REG(r,v) (*((volatile uint32_t*)(r))) = (v) #define GET_REG(r) (*((volatile uint32_t*)(r))) #define HW_REG(r) (*((volatile uint32_t*)(r))) -#define _BV(x) (1<<(x)) +#define HW16_REG(r) (*((volatile uint16_t*)(r))) +#define HW8_REG(r) (*((volatile uint8_t*)(r))) +#define _BV(x) (1UL<<(x)) #define SYSCTL_BASE 0x400FE000 #define DID0_OFFSET 0x000 @@ -87,6 +89,48 @@ #define RCC2_BYPASS2 11 #define RCC2_OSCSR2 4 +#define RCGC0_WDT0 3 +#define RCGC0_HIB 6 +#define RCGC0_MAXADC0SPD 8 +#define RCGC0_MAXADC1SPD 10 +#define RCGC0_ADC0 16 +#define RCGC0_ADC1 17 +#define RCGC0_CAN0 24 +#define RCGC0_CAN1 25 +#define RCGC0_WDT1 28 + +#define RCGC1_UART0 0 +#define RCGC1_UART1 1 +#define RCGC1_UART2 2 +#define RCGC1_SSI0 4 +#define RCGC1_SSI1 5 +#define RCGC1_I2C0 12 +#define RCGC1_I2C1 14 +#define RCGC1_TIMER0 16 +#define RCGC1_TIMER1 17 +#define RCGC1_TIMER2 18 +#define RCGC1_TIMER3 19 +#define RCGC1_COMP0 24 +#define RCGC1_COMP1 25 +#define RCGC1_COMP2 26 +#define RCGC1_I2S0 28 +#define RCGC1_EPI0 30 + +#define RCGC2_GPIOA 0 +#define RCGC2_GPIOB 1 +#define RCGC2_GPIOC 2 +#define RCGC2_GPIOD 3 +#define RCGC2_GPIOE 4 +#define RCGC2_GPIOF 5 +#define RCGC2_GPIOG 6 +#define RCGC2_GPIOH 7 +#define RCGC2_GPIOJ 8 +#define RCGC2_UDMA 13 +#define RCGC2_USB0 16 +#define RCGC2_EMAC0 28 +#define RCGC2_EPHY0 30 + + #define RIS_MOSCPUPRIS 8 #define RIS_USBPLLLRIS 7 #define RIS_PLLLRIS 6 diff --git a/test_src/main-bigint-test.c b/test_src/main-bigint-test.c new file mode 100644 index 0000000..4ec32ee --- /dev/null +++ b/test_src/main-bigint-test.c @@ -0,0 +1,563 @@ +/* main-bigint-test.c */ +/* + This file is part of the AVR-Crypto-Lib. + Copyright (C) 2008, 2009, 2010 Daniel Otte (daniel.otte@rub.de) + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ +/* + * bigint test-suit + * +*/ +#include +#include +#include +#include "config.h" +#include "cli.h" +#include "dump.h" +#include "uart_lowlevel.h" +#include "sysclock.h" +#include "hw_gptm.h" + +#include "noekeon.h" +#include "noekeon_prng.h" +#include "bigint.h" +#include "bigint_io.h" + +#include "performance_test.h" + +#include +#include +#include + +char* algo_name = "BigInt"; + +void uart0_putc(char byte){ + uart_putc(UART_0, byte); +} + +char uart0_getc(void){ + return uart_getc(UART_0); +} + +/***************************************************************************** + * additional validation-functions * + *****************************************************************************/ +void test_echo_bigint(void){ + bigint_t a; + cli_putstr("\r\necho test\r\n"); + for(;;){ + cli_putstr("\r\nenter hex number:"); + if(bigint_read_hex_echo(&a)){ + cli_putstr("\r\n end echo test"); + return; + } + cli_putstr("\r\necho: "); + bigint_print_hex(&a); + cli_putstr("\r\n"); + free(a.wordv); + } +} + +void test_add_bigint(void){ + bigint_t a, b, c; + cli_putstr("\r\nadd test\r\n"); + for(;;){ + cli_putstr("\r\nenter a:"); + if(bigint_read_hex_echo(&a)){ + cli_putstr("\r\n end add test"); + return; + } + cli_putstr("\r\nenter b:"); + if(bigint_read_hex_echo(&b)){ + free(a.wordv); + cli_putstr("\r\n end add test"); + return; + } + cli_putstr("\r\n "); + bigint_print_hex(&a); + cli_putstr(" + "); + bigint_print_hex(&b); + cli_putstr(" = "); + bigint_word_t *c_b; + c_b = malloc(((a.length_B>b.length_B)?a.length_B:b.length_B)*sizeof(bigint_word_t)+8); + if(c_b==NULL){ + cli_putstr("\n\rERROR: Out of memory!"); + free(a.wordv); + free(b.wordv); + continue; + } + c.wordv = c_b; + bigint_add_s(&c, &a, &b); + bigint_print_hex(&c); + cli_putstr("\r\n"); + free(a.wordv); + free(b.wordv); + free(c_b); + } +} + +void test_add_scale_bigint(void){ + bigint_t a, b, c; + uint16_t scale; + cli_putstr("\r\nadd-scale test\r\n"); + for(;;){ + cli_putstr("\r\nenter a:"); + if(bigint_read_hex_echo(&a)){ + cli_putstr("\r\n end add test"); + return; + } + cli_putstr("\r\nenter b:"); + if(bigint_read_hex_echo(&b)){ + cli_putstr("\r\n end add test"); + return; + } + cli_putstr("\r\nenter scale:"); + { + char str[8]; + cli_getsn_cecho(str, 7); + scale = atoi(str); + } + /* + if(bigint_read_hex_echo(&scale)){ + free(scale.wordv); + cli_putstr("\r\n end add test"); + return; + } + */ + cli_putstr("\r\n "); + bigint_print_hex(&a); + cli_putstr(" + "); + bigint_print_hex(&b); + cli_putstr("<<8*"); + cli_hexdump_rev(&scale, 2); + cli_putstr(" = "); + bigint_word_t *c_b; + c_b = malloc(((a.length_B>(b.length_B+scale))?a.length_B:(b.length_B+scale))*sizeof(bigint_word_t)+8); + if(c_b==NULL){ + cli_putstr("\n\rERROR: Out of memory!"); + free(a.wordv); + free(b.wordv); + continue; + } + bigint_copy(&c, &a); + c.wordv = c_b; + bigint_add_scale_u(&c, &b, scale); + bigint_print_hex(&c); + cli_putstr("\r\n"); + free(a.wordv); + free(b.wordv); + free(c_b); + } +} + +void test_mul_bigint(void){ + bigint_t a, b, c; + cli_putstr("\r\nmul test\r\n"); + for(;;){ + cli_putstr("\r\nenter a:"); + if(bigint_read_hex_echo(&a)){ + cli_putstr("\r\n end mul test"); + return; + } + cli_putstr("\r\nenter b:"); + if(bigint_read_hex_echo(&b)){ + free(a.wordv); + cli_putstr("\r\n end mul test"); + return; + } + cli_putstr("\r\n "); + bigint_print_hex(&a); + cli_putstr(" * "); + bigint_print_hex(&b); + cli_putstr(" = "); + bigint_word_t *c_b; + c_b = malloc((((a.length_B>b.length_B)?a.length_B:b.length_B)+1)*2*sizeof(bigint_word_t)); + if(c_b==NULL){ + cli_putstr("\n\rERROR: Out of memory!"); + free(a.wordv); + free(b.wordv); + continue; + } + c.wordv = c_b; + bigint_mul_s(&c, &a, &b); + bigint_print_hex(&c); + cli_putstr("\r\n"); + free(a.wordv); + free(b.wordv); + free(c_b); + } +} + +void test_square_bigint(void){ + bigint_t a, c; + cli_putstr("\r\nsquare test\r\n"); + for(;;){ + cli_putstr("\r\nenter a:"); + if(bigint_read_hex_echo(&a)){ + cli_putstr("\r\n end square test"); + return; + } + cli_putstr("\r\n "); + bigint_print_hex(&a); + cli_putstr("**2 = "); + bigint_word_t *c_b; + c_b = malloc(a.length_B*2*sizeof(bigint_word_t)); + if(c_b==NULL){ + cli_putstr("\n\rERROR: Out of memory!"); + free(a.wordv); + continue; + } + c.wordv = c_b; + bigint_square(&c, &a); + bigint_print_hex(&c); + cli_putstr("\r\n"); + free(a.wordv); + free(c_b); + } +} + +void test_reduce_bigint(void){ + bigint_t a, b; + cli_putstr("\r\nreduce test\r\n"); + for(;;){ + cli_putstr("\r\nenter a:"); + if(bigint_read_hex_echo(&a)){ + cli_putstr("\r\n end reduce test"); + return; + } + cli_putstr("\r\nenter b:"); + if(bigint_read_hex_echo(&b)){ + free(a.wordv); + cli_putstr("\r\n end reduce test"); + return; + } + cli_putstr("\r\n "); + bigint_print_hex(&a); + cli_putstr(" % "); + bigint_print_hex(&b); + cli_putstr(" = "); + bigint_reduce(&a, &b); + bigint_print_hex(&a); + cli_putstr("\r\n"); + free(a.wordv); + free(b.wordv); + } +} +/* d = a**b % c */ +void test_expmod_bigint(void){ + bigint_t a, b, c, d; + bigint_word_t *d_b; + cli_putstr("\r\nreduce test\r\n"); + for(;;){ + cli_putstr("\r\nenter a:"); + if(bigint_read_hex_echo(&a)){ + cli_putstr("\r\n end expmod test"); + return; + } + cli_putstr("\r\nenter b:"); + if(bigint_read_hex_echo(&b)){ + free(a.wordv); + cli_putstr("\r\n end expmod test"); + return; + } + cli_putstr("\r\nenter c:"); + if(bigint_read_hex_echo(&c)){ + free(a.wordv); + free(b.wordv); + cli_putstr("\r\n end expmod test"); + return; + } + d_b = malloc(c.length_B*sizeof(bigint_word_t)); + if(d_b==NULL){ + cli_putstr("\n\rERROR: Out of memory!"); + free(a.wordv); + free(b.wordv); + free(c.wordv); + continue; + } + d.wordv = d_b; + cli_putstr("\r\n "); + bigint_print_hex(&a); + cli_putstr("**"); + bigint_print_hex(&b); + cli_putstr(" % "); + bigint_print_hex(&c); + cli_putstr(" = "); + bigint_expmod_u(&d, &a, &b, &c); + bigint_print_hex(&d); + cli_putstr("\r\n"); + free(a.wordv); + free(b.wordv); + free(c.wordv); + free(d.wordv); + + } +} + +void test_gcdext_bigint(void){ + bigint_t a, b, c, d, e; + cli_putstr("\r\ngcdext test\r\n"); + for(;;){ + cli_putstr("\r\nenter a:"); + if(bigint_read_hex_echo(&a)){ + cli_putstr("\r\n end gcdext test"); + return; + } + cli_putstr("\r\nenter b:"); + if(bigint_read_hex_echo(&b)){ + free(a.wordv); + cli_putstr("\r\n end gcdext test"); + return; + } + c.wordv = malloc(((a.length_Bb.length_B)?a.length_B:b.length_B)*sizeof(bigint_word_t)); + e.wordv = malloc((1+(a.length_B>b.length_B)?a.length_B:b.length_B)*sizeof(bigint_word_t)); + + cli_putstr("\r\n gcdext( "); + bigint_print_hex(&a); + cli_putstr(", "); + bigint_print_hex(&b); + cli_putstr(") => "); + bigint_gcdext(&c, &d, &e, &a, &b); + cli_putstr("a = "); + bigint_print_hex(&d); + cli_putstr("; b = "); + bigint_print_hex(&e); + cli_putstr("; gcd = "); + bigint_print_hex(&c); + + cli_putstr("\r\n"); + free(a.wordv); + free(b.wordv); + free(c.wordv); + free(d.wordv); + free(e.wordv); + } +} + +void test_simple(void){ + bigint_t a, b, c; + bigint_word_t a_b[1], b_b[1], c_b[2]; + a.wordv=a_b; + b.wordv=b_b; + c.wordv=c_b; + a.length_B = 1; + b.length_B = 1; + a_b[0] = 1; + b_b[0] = 2; + bigint_add_u(&c, &a, &b); + cli_putstr("\r\n 1+2="); + bigint_print_hex(&c); +} +/* +void test_mul_simple(void){ + bigint_t a, b, c; + uint8_t a_b[5] = {0x79, 0x36, 0x9e, 0x72, 0xec}; + uint8_t b_b[5] = {0x4a, 0x47, 0x0d, 0xec, 0xfd}; + uint8_t c_b[12]; + a.wordv=a_b; + b.wordv=b_b; + c.wordv=c_b; + a.length_B = 5; + b.length_B = 5; + bigint_adjust(&a); + bigint_adjust(&b); + bigint_mul_s(&c, &a, &b); + cli_putstr("\r\n test: "); + bigint_print_hex(&c); +} +*/ + +// -3d1d 6db7 8251 f371 * -7a18 3791 d18b b7c5 = 1d25ce4fdf93390f8d6c709f4d711cf5 +// -20538248dece6d29068d * 400b1411b874f81394c6 = -81646b193d95136a6fedb73cee6d30c39fb950e +// -BC8B 7D53 4921 853D * 0DDA 6044 00CE DDE6 = -a33eb0c5847db8837589c22db395dce +void test_mul_simple(void){ + bigint_t a, b, c; + +// uint8_t a_b[10] = {0x8d, 0x06, 0x29, 0x6d, 0xce, 0xde, 0x48, 0x82, 0x53, 0x20}; +// uint8_t b_b[10] = {0xc6, 0x94, 0x13, 0xf8, 0x74, 0xb8, 0x11, 0x14, 0x0b, 0x40}; + uint8_t a_b[8] = {0x3d, 0x85, 0x21, 0x49, 0x53, 0x7d, 0x8b, 0xbc}; + uint8_t b_b[8] = {0xe6, 0xdd, 0xce, 0x00, 0x44, 0x60, 0xda, 0x0d}; + + uint8_t c_b[16]; + a.wordv=(bigint_word_t*)a_b; + b.wordv=(bigint_word_t*)b_b; + c.wordv=(bigint_word_t*)c_b; + a.length_B = 8/sizeof(bigint_word_t); + b.length_B = 8/sizeof(bigint_word_t); + a.info=0x80; + bigint_adjust(&a); + bigint_adjust(&b); + bigint_mul_s(&c, &a, &b); + cli_putstr("\r\n test: "); + bigint_print_hex(&a); + cli_putstr(" * "); + bigint_print_hex(&b); + cli_putstr(" = "); + bigint_print_hex(&c); +} + +// 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; + + uint8_t a_b[12] = {0xe6, 0x70, 0x7d, 0x43, 0x74, 0x07, 0x20, 0x22, 0x6a, 0xb8, 0xf4, 0x00}; + uint8_t c_b[24]; + a.wordv=(bigint_word_t*)a_b; + c.wordv=(bigint_word_t*)c_b; + a.length_B = 12/sizeof(bigint_word_t); + a.info=0x00; + bigint_adjust(&a); + bigint_square(&c, &a); + cli_putstr("\r\n test: "); + bigint_print_hex(&a); + cli_putstr("**2 = "); + 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[4] = {0x62, 0xA8, 0x00, 0x00}; + uint8_t b_b[4] = {0x52, 0x27, 0x00, 0x00}; + uint8_t c_b[4]; + a.wordv=(bigint_word_t*)a_b; + a.length_B = 1; + a.info=0x00; + bigint_adjust(&a); + b.wordv=(bigint_word_t*)b_b; + b.length_B = 1; + b.info=0x00; + bigint_adjust(&b); + c.wordv = (bigint_word_t*)c_b; + bigint_copy(&c, &a); + bigint_reduce(&c, &b); + cli_putstr("\r\n test: "); + bigint_print_hex(&a); + cli_putstr(" % "); + bigint_print_hex(&b); + cli_putstr(" = "); + bigint_print_hex(&c); +} + +/* gcdext( B5DDAD, 6CBBC2) */ +/* gcdext( CD319349, 9EFD76CC) */ +/* gcdext( 1609000771, 6FAC577D72) */ +/* */ +void test_gcdext_simple(void){ + bigint_t a, b, c, d, e; + + uint8_t a_b[8] = {0x71, 0x07, 0x00, 0x09, 0x16, 0x00, 0x00, 0x00}; + uint8_t b_b[8] = {0x72, 0x7D, 0x57, 0xAC, 0X6F, 0x00, 0x00, 0x00}; + uint8_t c_b[16], d_b[16], e_b[16]; + a.wordv=(bigint_word_t*)a_b; + a.length_B = 2; + a.info=0x00; + bigint_adjust(&a); + b.wordv=(bigint_word_t*)b_b; + b.length_B = 2; + b.info=0x00; + bigint_adjust(&b); + c.wordv = (bigint_word_t*)c_b; + d.wordv = (bigint_word_t*)d_b; + e.wordv = (bigint_word_t*)e_b; + bigint_gcdext(&c, &d, &e, &a, &b); + cli_putstr("\r\n test: gcd( "); + bigint_print_hex(&a); + cli_putstr(", "); + bigint_print_hex(&b); + cli_putstr(") => a = "); + bigint_print_hex(&d); + cli_putstr("; b = "); + bigint_print_hex(&e); + cli_putstr("; gcd = "); + bigint_print_hex(&c); +} + +void testrun_performance_bigint(void){ + +} +/***************************************************************************** + * main * + *****************************************************************************/ + +const char echo_test_str[] = "echo-test"; +const char add_test_str[] = "add-test"; +const char add_scale_test_str[] = "add-scale-test"; +const char mul_test_str[] = "mul-test"; +const char square_test_str[] = "square-test"; +const char reduce_test_str[] = "reduce-test"; +const char expmod_test_str[] = "expmod-test"; +const char gcdext_test_str[] = "gcdext-test"; +const char quick_test_str[] = "quick-test"; +const char performance_str[] = "performance"; +const char echo_str[] = "echo"; + +const cmdlist_entry_t cmdlist[] = { + { add_test_str, NULL, test_add_bigint }, + { add_scale_test_str, NULL, test_add_scale_bigint }, + { mul_test_str, NULL, test_mul_bigint }, + { square_test_str, NULL, test_square_bigint }, + { reduce_test_str, NULL, test_reduce_bigint }, + { expmod_test_str, NULL, test_expmod_bigint }, + { gcdext_test_str, NULL, test_gcdext_bigint }, + { quick_test_str, NULL, test_gcdext_simple }, + { echo_test_str, NULL, test_echo_bigint }, + { performance_str, NULL, testrun_performance_bigint }, + { echo_str, (void*)1, (void_fpt)echo_ctrl }, + { NULL, NULL, NULL } +}; + +int main (void){ + sysclk_set_freq(SYS_FREQ); + sysclk_mosc_verify_enable(); + uart_init(UART_0, 115200, 8, UART_PARATY_NONE, UART_STOPBITS_ONE); + gptm_set_timer_32periodic(TIMER0); + + cli_rx = uart0_getc; + cli_tx = uart0_putc; + + for(;;){ + cli_putstr("\r\n\r\nARM-Crypto-Lib VS ("); + cli_putstr(algo_name); + cli_putstr("; "); + cli_putstr(__DATE__); + cli_putc(' '); + cli_putstr(__TIME__); + cli_putstr(")\r\nloaded and running\r\n"); + cmd_interface(cmdlist); + } +} diff --git a/test_src/main-present-test.c b/test_src/main-present-test.c index 79b6df8..8dd2468 100644 --- a/test_src/main-present-test.c +++ b/test_src/main-present-test.c @@ -106,7 +106,6 @@ void testrun_self_present(void){ memset(buffer, 0xFF, 8); memset(key, 0xFF, 10); testrun_selfenc(key, buffer); - } void testrun_performance_present(void){ diff --git a/test_src/startup.c b/test_src/startup.c index f1c3619..bad3560 100644 --- a/test_src/startup.c +++ b/test_src/startup.c @@ -82,6 +82,7 @@ isr_fpt isr_vector[] __attribute__ ((section(".isr_vectors"))) = { default_isr, /* GPIO Port D */ default_isr, /* GPIO Port E */ uart0_isr, /* UART0 */ + // default_isr, /* UART0 */ default_isr, /* UART1 */ default_isr, /* SSI0 */ default_isr, /* I2C0 */ diff --git a/test_src/string-extras.c b/test_src/string-extras.c index f4c95a2..0c01a04 100644 --- a/test_src/string-extras.c +++ b/test_src/string-extras.c @@ -42,7 +42,7 @@ uint32_t stridentcnt(const char* a, const char* b){ uint16_t firstword_length(const char* s){ uint16_t ret=0; - while(isgraph(*s++)) + while(isgraph((uint8_t)(*s++))) ret++; return ret; } diff --git a/test_src/sysclock.c b/test_src/sysclock.c index 45d9217..02e226c 100644 --- a/test_src/sysclock.c +++ b/test_src/sysclock.c @@ -27,13 +27,15 @@ #define PIOSC_FREQ 16000000UL void sysclk_set_rawclock(void){ - uint32_t tmp_rcc; + volatile uint32_t tmp_rcc; tmp_rcc = 0; //HW_REG(SYSCTL_BASE+RCC_OFFSET); tmp_rcc &= ~(_BV(RCC_IOSCDIS) | _BV(RCC_MOSCDIS) | _BV(RCC_USESYSDIV)); tmp_rcc |= _BV(RCC_BYPASS) | _BV(RCC_PWRDN); tmp_rcc &= ~(3< -#define SYS_FREQ_80MHZ000 0x4 -#define SYS_FREQ_66MHZ667 0x5 -#define SYS_FREQ_57MHZ143 0x6 -#define SYS_FREQ_50MHZ000 0x7 -#define SYS_FREQ_44MHZ444 0x8 -#define SYS_FREQ_40MHZ000 0x9 -#define SYS_FREQ_36MHZ364 0xA -#define SYS_FREQ_33MHZ333 0xB -#define SYS_FREQ_30MHZ769 0xC -#define SYS_FREQ_28MHZ571 0xD -#define SYS_FREQ_26MHZ667 0xE -#define SYS_FREQ_25MHZ000 0xF -#define SYS_FREQ_23MHZ529 0x10 -#define SYS_FREQ_22MHZ222 0x11 -#define SYS_FREQ_21MHZ053 0x12 -#define SYS_FREQ_20MHZ000 0x13 -#define SYS_FREQ_19MHZ048 0x14 -#define SYS_FREQ_18MHZ182 0x15 -#define SYS_FREQ_17MHZ391 0x16 -#define SYS_FREQ_16MHZ667 0x17 -#define SYS_FREQ_16MHZ000 0x18 -#define SYS_FREQ_15MHZ385 0x19 -#define SYS_FREQ_14MHZ815 0x1A -#define SYS_FREQ_14MHZ286 0x1B -#define SYS_FREQ_13MHZ793 0x1C -#define SYS_FREQ_13MHZ333 0x1D -#define SYS_FREQ_12MHZ903 0x1E -#define SYS_FREQ_12MHZ500 0x1F -#define SYS_FREQ_12MHZ121 0x20 -#define SYS_FREQ_11MHZ765 0x21 -#define SYS_FREQ_11MHZ429 0x22 -#define SYS_FREQ_11MHZ111 0x23 -#define SYS_FREQ_10MHZ811 0x24 -#define SYS_FREQ_10MHZ526 0x25 -#define SYS_FREQ_10MHZ256 0x26 -#define SYS_FREQ_10MHZ000 0x27 -#define SYS_FREQ_9MHZ756 0x28 -#define SYS_FREQ_9MHZ524 0x29 -#define SYS_FREQ_9MHZ302 0x2A -#define SYS_FREQ_9MHZ091 0x2B -#define SYS_FREQ_8MHZ889 0x2C -#define SYS_FREQ_8MHZ696 0x2D -#define SYS_FREQ_8MHZ511 0x2E -#define SYS_FREQ_8MHZ333 0x2F -#define SYS_FREQ_8MHZ163 0x30 -#define SYS_FREQ_8MHZ000 0x31 -#define SYS_FREQ_7MHZ843 0x32 -#define SYS_FREQ_7MHZ692 0x33 -#define SYS_FREQ_7MHZ547 0x34 -#define SYS_FREQ_7MHZ407 0x35 -#define SYS_FREQ_7MHZ273 0x36 -#define SYS_FREQ_7MHZ143 0x37 -#define SYS_FREQ_7MHZ018 0x38 -#define SYS_FREQ_6MHZ897 0x39 -#define SYS_FREQ_6MHZ780 0x3A -#define SYS_FREQ_6MHZ667 0x3B -#define SYS_FREQ_6MHZ557 0x3C -#define SYS_FREQ_6MHZ452 0x3D -#define SYS_FREQ_6MHZ349 0x3E -#define SYS_FREQ_6MHZ250 0x3F -#define SYS_FREQ_6MHZ154 0x40 -#define SYS_FREQ_6MHZ061 0x41 -#define SYS_FREQ_5MHZ970 0x42 -#define SYS_FREQ_5MHZ882 0x43 -#define SYS_FREQ_5MHZ797 0x44 -#define SYS_FREQ_5MHZ714 0x45 -#define SYS_FREQ_5MHZ634 0x46 -#define SYS_FREQ_5MHZ556 0x47 -#define SYS_FREQ_5MHZ479 0x48 -#define SYS_FREQ_5MHZ405 0x49 -#define SYS_FREQ_5MHZ333 0x4A -#define SYS_FREQ_5MHZ263 0x4B -#define SYS_FREQ_5MHZ195 0x4C -#define SYS_FREQ_5MHZ128 0x4D -#define SYS_FREQ_5MHZ063 0x4E -#define SYS_FREQ_5MHZ000 0x4F -#define SYS_FREQ_4MHZ938 0x50 -#define SYS_FREQ_4MHZ878 0x51 -#define SYS_FREQ_4MHZ819 0x52 -#define SYS_FREQ_4MHZ762 0x53 -#define SYS_FREQ_4MHZ706 0x54 -#define SYS_FREQ_4MHZ651 0x55 -#define SYS_FREQ_4MHZ598 0x56 -#define SYS_FREQ_4MHZ545 0x57 -#define SYS_FREQ_4MHZ494 0x58 -#define SYS_FREQ_4MHZ444 0x59 -#define SYS_FREQ_4MHZ396 0x5A -#define SYS_FREQ_4MHZ348 0x5B -#define SYS_FREQ_4MHZ301 0x5C -#define SYS_FREQ_4MHZ255 0x5D -#define SYS_FREQ_4MHZ211 0x5E -#define SYS_FREQ_4MHZ167 0x5F -#define SYS_FREQ_4MHZ124 0x60 -#define SYS_FREQ_4MHZ082 0x61 -#define SYS_FREQ_4MHZ040 0x62 -#define SYS_FREQ_4MHZ000 0x63 -#define SYS_FREQ_3MHZ960 0x64 -#define SYS_FREQ_3MHZ922 0x65 -#define SYS_FREQ_3MHZ883 0x66 -#define SYS_FREQ_3MHZ846 0x67 -#define SYS_FREQ_3MHZ810 0x68 -#define SYS_FREQ_3MHZ774 0x69 -#define SYS_FREQ_3MHZ738 0x6A -#define SYS_FREQ_3MHZ704 0x6B -#define SYS_FREQ_3MHZ670 0x6C -#define SYS_FREQ_3MHZ636 0x6D -#define SYS_FREQ_3MHZ604 0x6E -#define SYS_FREQ_3MHZ571 0x6F -#define SYS_FREQ_3MHZ540 0x70 -#define SYS_FREQ_3MHZ509 0x71 -#define SYS_FREQ_3MHZ478 0x72 -#define SYS_FREQ_3MHZ448 0x73 -#define SYS_FREQ_3MHZ419 0x74 -#define SYS_FREQ_3MHZ390 0x75 -#define SYS_FREQ_3MHZ361 0x76 -#define SYS_FREQ_3MHZ333 0x77 -#define SYS_FREQ_3MHZ306 0x78 -#define SYS_FREQ_3MHZ279 0x79 -#define SYS_FREQ_3MHZ252 0x7A -#define SYS_FREQ_3MHZ226 0x7B -#define SYS_FREQ_3MHZ200 0x7C -#define SYS_FREQ_3MHZ175 0x7D -#define SYS_FREQ_3MHZ150 0x7E -#define SYS_FREQ_3MHZ125 0x7F +#define SYS_FREQ_80MHZ000 0x04UL +#define SYS_FREQ_66MHZ667 0x05UL +#define SYS_FREQ_57MHZ143 0x06UL +#define SYS_FREQ_50MHZ000 0x07UL +#define SYS_FREQ_44MHZ444 0x08UL +#define SYS_FREQ_40MHZ000 0x09UL +#define SYS_FREQ_36MHZ364 0x0AUL +#define SYS_FREQ_33MHZ333 0x0BUL +#define SYS_FREQ_30MHZ769 0x0CUL +#define SYS_FREQ_28MHZ571 0x0DUL +#define SYS_FREQ_26MHZ667 0x0EUL +#define SYS_FREQ_25MHZ000 0x0FUL +#define SYS_FREQ_23MHZ529 0x10UL +#define SYS_FREQ_22MHZ222 0x11UL +#define SYS_FREQ_21MHZ053 0x12UL +#define SYS_FREQ_20MHZ000 0x13UL +#define SYS_FREQ_19MHZ048 0x14UL +#define SYS_FREQ_18MHZ182 0x15UL +#define SYS_FREQ_17MHZ391 0x16UL +#define SYS_FREQ_16MHZ667 0x17UL +#define SYS_FREQ_16MHZ000 0x18UL +#define SYS_FREQ_15MHZ385 0x19UL +#define SYS_FREQ_14MHZ815 0x1AUL +#define SYS_FREQ_14MHZ286 0x1BUL +#define SYS_FREQ_13MHZ793 0x1CUL +#define SYS_FREQ_13MHZ333 0x1DUL +#define SYS_FREQ_12MHZ903 0x1EUL +#define SYS_FREQ_12MHZ500 0x1FUL +#define SYS_FREQ_12MHZ121 0x20UL +#define SYS_FREQ_11MHZ765 0x21UL +#define SYS_FREQ_11MHZ429 0x22UL +#define SYS_FREQ_11MHZ111 0x23UL +#define SYS_FREQ_10MHZ811 0x24UL +#define SYS_FREQ_10MHZ526 0x25UL +#define SYS_FREQ_10MHZ256 0x26UL +#define SYS_FREQ_10MHZ000 0x27UL +#define SYS_FREQ_9MHZ756 0x28UL +#define SYS_FREQ_9MHZ524 0x29UL +#define SYS_FREQ_9MHZ302 0x2AUL +#define SYS_FREQ_9MHZ091 0x2BUL +#define SYS_FREQ_8MHZ889 0x2CUL +#define SYS_FREQ_8MHZ696 0x2DUL +#define SYS_FREQ_8MHZ511 0x2EUL +#define SYS_FREQ_8MHZ333 0x2FUL +#define SYS_FREQ_8MHZ163 0x30UL +#define SYS_FREQ_8MHZ000 0x31UL +#define SYS_FREQ_7MHZ843 0x32UL +#define SYS_FREQ_7MHZ692 0x33UL +#define SYS_FREQ_7MHZ547 0x34UL +#define SYS_FREQ_7MHZ407 0x35UL +#define SYS_FREQ_7MHZ273 0x36UL +#define SYS_FREQ_7MHZ143 0x37UL +#define SYS_FREQ_7MHZ018 0x38UL +#define SYS_FREQ_6MHZ897 0x39UL +#define SYS_FREQ_6MHZ780 0x3AUL +#define SYS_FREQ_6MHZ667 0x3BUL +#define SYS_FREQ_6MHZ557 0x3CUL +#define SYS_FREQ_6MHZ452 0x3DUL +#define SYS_FREQ_6MHZ349 0x3EUL +#define SYS_FREQ_6MHZ250 0x3FUL +#define SYS_FREQ_6MHZ154 0x40UL +#define SYS_FREQ_6MHZ061 0x41UL +#define SYS_FREQ_5MHZ970 0x42UL +#define SYS_FREQ_5MHZ882 0x43UL +#define SYS_FREQ_5MHZ797 0x44UL +#define SYS_FREQ_5MHZ714 0x45UL +#define SYS_FREQ_5MHZ634 0x46UL +#define SYS_FREQ_5MHZ556 0x47UL +#define SYS_FREQ_5MHZ479 0x48UL +#define SYS_FREQ_5MHZ405 0x49UL +#define SYS_FREQ_5MHZ333 0x4AUL +#define SYS_FREQ_5MHZ263 0x4BUL +#define SYS_FREQ_5MHZ195 0x4CUL +#define SYS_FREQ_5MHZ128 0x4DUL +#define SYS_FREQ_5MHZ063 0x4EUL +#define SYS_FREQ_5MHZ000 0x4FUL +#define SYS_FREQ_4MHZ938 0x50UL +#define SYS_FREQ_4MHZ878 0x51UL +#define SYS_FREQ_4MHZ819 0x52UL +#define SYS_FREQ_4MHZ762 0x53UL +#define SYS_FREQ_4MHZ706 0x54UL +#define SYS_FREQ_4MHZ651 0x55UL +#define SYS_FREQ_4MHZ598 0x56UL +#define SYS_FREQ_4MHZ545 0x57UL +#define SYS_FREQ_4MHZ494 0x58UL +#define SYS_FREQ_4MHZ444 0x59UL +#define SYS_FREQ_4MHZ396 0x5AUL +#define SYS_FREQ_4MHZ348 0x5BUL +#define SYS_FREQ_4MHZ301 0x5CUL +#define SYS_FREQ_4MHZ255 0x5DUL +#define SYS_FREQ_4MHZ211 0x5EUL +#define SYS_FREQ_4MHZ167 0x5FUL +#define SYS_FREQ_4MHZ124 0x60UL +#define SYS_FREQ_4MHZ082 0x61UL +#define SYS_FREQ_4MHZ040 0x62UL +#define SYS_FREQ_4MHZ000 0x63UL +#define SYS_FREQ_3MHZ960 0x64UL +#define SYS_FREQ_3MHZ922 0x65UL +#define SYS_FREQ_3MHZ883 0x66UL +#define SYS_FREQ_3MHZ846 0x67UL +#define SYS_FREQ_3MHZ810 0x68UL +#define SYS_FREQ_3MHZ774 0x69UL +#define SYS_FREQ_3MHZ738 0x6AUL +#define SYS_FREQ_3MHZ704 0x6BUL +#define SYS_FREQ_3MHZ670 0x6CUL +#define SYS_FREQ_3MHZ636 0x6DUL +#define SYS_FREQ_3MHZ604 0x6EUL +#define SYS_FREQ_3MHZ571 0x6FUL +#define SYS_FREQ_3MHZ540 0x70UL +#define SYS_FREQ_3MHZ509 0x71UL +#define SYS_FREQ_3MHZ478 0x72UL +#define SYS_FREQ_3MHZ448 0x73UL +#define SYS_FREQ_3MHZ419 0x74UL +#define SYS_FREQ_3MHZ390 0x75UL +#define SYS_FREQ_3MHZ361 0x76UL +#define SYS_FREQ_3MHZ333 0x77UL +#define SYS_FREQ_3MHZ306 0x78UL +#define SYS_FREQ_3MHZ279 0x79UL +#define SYS_FREQ_3MHZ252 0x7AUL +#define SYS_FREQ_3MHZ226 0x7BUL +#define SYS_FREQ_3MHZ200 0x7CUL +#define SYS_FREQ_3MHZ175 0x7DUL +#define SYS_FREQ_3MHZ150 0x7EUL +#define SYS_FREQ_3MHZ125 0x7FUL void sysclk_set_rawclock(void); diff --git a/test_src/uart_defines.h b/test_src/uart_defines.h index aa2dd29..976f2ee 100644 --- a/test_src/uart_defines.h +++ b/test_src/uart_defines.h @@ -1,6 +1,6 @@ /* uart_defines.h */ /* - This file is part of the ARM-Crypto-Lib. + This file is part of the AVR-Crypto-Lib. Copyright (C) 2010 Daniel Otte (daniel.otte@rub.de) This program is free software: you can redistribute it and/or modify @@ -47,10 +47,4 @@ #define UART_ERROR_RX_BUFFER_INIT 5 #define UART_ERROR_TX_BUFFER_INIT 6 -#define UART_FLOWCTRL_NONE 0 -#define UART_FLOWCTRL_SOFT 1 - -#define UART_XON_CHAR 0x11 -#define UART_XOFF_CHAR 0x13 - #endif /* UART_DEFINES_H_ */ diff --git a/test_src/uart_i.c b/test_src/uart_i.c index 37c6c7d..9c002af 100644 --- a/test_src/uart_i.c +++ b/test_src/uart_i.c @@ -23,7 +23,7 @@ #include "hw_uart_regs.h" #include "uart_defines.h" #include "circularbytebuffer.h" -#include "uart_lowlevel.h" + static const uint32_t uart_base[] = { UART0_BASE, UART1_BASE, UART2_BASE }; @@ -54,10 +54,6 @@ static const uint32_t uart_rx_buffersize[] = {128, 128, 128}; static const uint32_t uart_tx_buffersize[] = {256, 256, 256}; -static -uint8_t uart_swflowctrl_en[] = {0, 0, 0}; -static -uint8_t uart_swflowctrl_halt[] = {0, 0, 0}; static circularbytebuffer_t uart_rx_buffer[3]; @@ -71,6 +67,7 @@ static void uart_rx_isr(uint8_t uartno); void uart0_isr(void){ + if(HW_REG(UART0_BASE+UARTMIS_OFFSET)&_BV(UART_TXMIS)){ // HW_REG(uart_base[0]+UARTDR_OFFSET) = 'X'; uart_tx_isr(UART_0); @@ -84,8 +81,7 @@ static void uart_tx_isr(uint8_t uartno){ uint32_t tmp; tmp = circularbytebuffer_cnt(&(uart_tx_buffer[uartno])); - while(tmp-- && (!(HW_REG(uart_base[uartno]+UARTFR_OFFSET)&_BV(UART_TXFF))) - && !(uart_swflowctrl_en[uartno] && uart_swflowctrl_halt[uartno])){ + while(tmp-- && (!(HW_REG(uart_base[uartno]+UARTFR_OFFSET)&_BV(UART_TXFF)))){ HW_REG(uart_base[uartno]+UARTDR_OFFSET) = (uint32_t)circularbytebuffer_get_fifo(&(uart_tx_buffer[uartno])); } @@ -95,21 +91,9 @@ void uart_tx_isr(uint8_t uartno){ static void uart_rx_isr(uint8_t uartno){ uint8_t c; - while(!HW_REG(uart_base[uartno]+UARTFR_OFFSET)&_BV(UART_RXFE)){ + while(!(HW_REG(uart_base[uartno]+UARTFR_OFFSET)&_BV(UART_RXFE))){ c = HW_REG(uart_base[uartno]+UARTDR_OFFSET); - if(uart_swflowctrl_en[uartno]){ - circularbytebuffer_append(c, &(uart_rx_buffer[uartno])); - }else{ - if(c==UART_XON_CHAR){ - uart_swflowctrl_halt[uartno] = 0; - }else{ - if(c==UART_XOFF_CHAR){ - uart_swflowctrl_halt[uartno] = 1; - }else{ - circularbytebuffer_append(c, &(uart_rx_buffer[uartno])); - } - } - } + circularbytebuffer_append(c, &(uart_rx_buffer[uartno])); } HW_REG(uart_base[uartno]+UARTICR_OFFSET) |= _BV(UART_RXIC); } @@ -117,20 +101,21 @@ void uart_rx_isr(uint8_t uartno){ void calc_baud_values(uint32_t baudrate, uint16_t* intdivider, uint8_t* fracdivider, uint8_t* highspeed){ uint32_t tmp; uint32_t uart_freq; + if(baudrate==0){ + return; + } uart_freq = sysclk_get_freq(); - *highspeed = (baudrate*16>uart_freq)?1:0; - tmp = (uint64_t)uart_freq*128/((*highspeed?8:16)*baudrate); + *highspeed = ((baudrate*16L)>uart_freq)?1:0; +// tmp = (((uint64_t)UART_FREQ)*128LL)/(((*highspeed)?8L:16L)*baudrate); + tmp = uart_freq<<((*highspeed)?(7-3):(7-4)); + tmp /= baudrate; tmp++; tmp>>=1; *fracdivider = (uint8_t)(tmp&0x3f); - *intdivider = tmp>>6; + *intdivider = (uint16_t)(tmp>>6); } uint8_t uart_init(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint8_t paraty, uint8_t stopbits){ - return uart_init_flow(uartno, baudrate, databits, paraty, stopbits, 0); -} - -uint8_t uart_init_flow(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint8_t paraty, uint8_t stopbits, uint8_t flowctrl){ uint32_t tmp; if(databits>=5){ databits-=5; @@ -153,12 +138,17 @@ uint8_t uart_init_flow(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint if(0==circularbytebuffer_init(uart_tx_buffersize[uartno], &(uart_tx_buffer[uartno]))){ return UART_ERROR_TX_BUFFER_INIT; } - /* enable clock for uart */ - HW_REG(SYSCTL_BASE+RCGC1_OFFSET) |= _BV(uartno); /* enable clock for gpio*/ HW_REG(SYSCTL_BASE+RCGC2_OFFSET) |= _BV(uart_rx_gpio[uartno]) | _BV(uart_tx_gpio[uartno]); + for(tmp=0; tmp<100; ++tmp) + ; HW_REG(SYSCTL_BASE+RCGC2_OFFSET) |= 1; - + for(tmp=0; tmp<100; ++tmp) + ; + /* enable clock for uart */ + HW_REG(SYSCTL_BASE+RCGC1_OFFSET) |= _BV(uartno); + for(tmp=0; tmp<100; ++tmp) + ; HW_REG(gpio_base[uart_rx_gpio[uartno]] + GPIO_ODR_OFFSET) &= ~_BV(uart_rx_pin[uartno]); /* open drain */ HW_REG(gpio_base[uart_tx_gpio[uartno]] + GPIO_ODR_OFFSET) &= ~_BV(uart_tx_pin[uartno]); /* open drain */ HW_REG(gpio_base[uart_rx_gpio[uartno]] + GPIO_PUR_OFFSET) &= ~_BV(uart_rx_pin[uartno]); /* pull-up */ @@ -185,20 +175,25 @@ uint8_t uart_init_flow(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint HW_REG(gpio_base[uart_rx_gpio[uartno]]+GPIO_DIR_OFFSET) &= ~_BV(uart_rx_pin[uartno]); /* configure tx pin as output */ HW_REG(gpio_base[uart_tx_gpio[uartno]]+GPIO_DIR_OFFSET) |= _BV(uart_tx_pin[uartno]); - + for(tmp=0; tmp<100; ++tmp) + ; /* disable uart */ HW_REG(uart_base[uartno]+UARTCTL_OFFSET) &= ~_BV(UART_UARTEN); /* set baudrate parameters */ - uint8_t highspeed; - calc_baud_values(baudrate, - (uint16_t*)&HW_REG(uart_base[uartno]+UARTIBRD_OFFSET), - (uint8_t*)&HW_REG(uart_base[uartno]+UARTFBRD_OFFSET), - &highspeed); + uint8_t highspeed, fbrd; + uint16_t ibrd; + calc_baud_values(baudrate, &ibrd, &fbrd, &highspeed); + tmp=HW_REG(uart_base[uartno]+UARTLCRH_OFFSET); + HW16_REG(uart_base[uartno]+UARTIBRD_OFFSET) = ibrd; + HW8_REG(uart_base[uartno]+UARTFBRD_OFFSET) = fbrd; + HW_REG(uart_base[uartno]+UARTLCRH_OFFSET) = tmp; /* wait until uart is no longer busy */ while(HW_REG(uart_base[uartno]+UARTFR_OFFSET)&_BV(UART_BUSY)) ; + /* flush FIFOs */ HW_REG(uart_base[uartno]+UARTLCRH_OFFSET) &= ~_BV(UART_FEN); + /* set line parameters (bits, paraty, stopbits*/ tmp = HW_REG(uart_base[uartno]+UARTLCRH_OFFSET); tmp &= ~0xff; @@ -215,13 +210,6 @@ uint8_t uart_init_flow(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint } else { HW_REG(uart_base[uartno]+UARTCTL_OFFSET) &= ~_BV(UART_HSE); } - /* set flow control */ - if(flowctrl==UART_FLOWCTRL_SOFT){ - uart_swflowctrl_en[uartno] = 1; - uart_swflowctrl_halt[uartno] = 0; - }else{ - uart_swflowctrl_en[uartno] = 0; - } /* uart interrupt enable */ HW_REG(uart_base[uartno]+UARTIM_OFFSET) |= _BV(UART_TXIM) | _BV(UART_RXIM); HW_REG(ISR_ENABLE_VECTOR+uart_isr_vector[uartno]/32) |= @@ -278,3 +266,12 @@ uint32_t uart_dataavail(uint8_t uartno){ } return(HW_REG(uart_base[uartno]+UARTFR_OFFSET)&_BV(UART_RXFE))?0:1; } + +void uart_flush(uint8_t uartno){ + if(uartno>UART_MAX){ + return; + } + while(uart_tx_buffer[uartno].fillcount>0){ + ; + } +} diff --git a/test_src/uart_lowlevel.c b/test_src/uart_lowlevel.c index 6c8583e..2261ebb 100644 --- a/test_src/uart_lowlevel.c +++ b/test_src/uart_lowlevel.c @@ -1,6 +1,6 @@ /* uart_lowlevel.c */ /* - This file is part of the ARM-Crypto-Lib. + This file is part of the AVR-Crypto-Lib. Copyright (C) 2010 Daniel Otte (daniel.otte@rub.de) This program is free software: you can redistribute it and/or modify @@ -18,23 +18,28 @@ */ #include -#include "sysclock.h" #include "hw_regs.h" #include "hw_uart_regs.h" #include "uart_defines.h" +#include "sysclock.h" void calc_baud_values(uint32_t baudrate, uint16_t* intdivider, uint8_t* fracdivider, uint8_t* highspeed){ uint32_t tmp; uint32_t uart_freq; + if(baudrate==0){ + return; + } uart_freq = sysclk_get_freq(); - *highspeed = (baudrate*16>uart_freq)?1:0; - tmp = (uint64_t)uart_freq*128/((*highspeed?8:16)*baudrate); + *highspeed = ((baudrate*16L)>uart_freq)?1:0; +// tmp = (((uint64_t)UART_FREQ)*128LL)/(((*highspeed)?8L:16L)*baudrate); + tmp = uart_freq<<((*highspeed)?(7-3):(7-4)); + tmp /= baudrate; tmp++; tmp>>=1; *fracdivider = (uint8_t)(tmp&0x3f); - *intdivider = tmp>>6; + *intdivider = (uint16_t)(tmp>>6); } - +//*/ static const uint32_t uart_base[] = { UART0_BASE, UART1_BASE, UART2_BASE }; @@ -109,13 +114,16 @@ uint8_t uart_init(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint8_t p HW_REG(gpio_base[uart_tx_gpio[uartno]]+GPIO_DIR_OFFSET) |= _BV(uart_tx_pin[uartno]); /* disable uart */ - HW_REG(uart_base[uartno]+UARTCTL_OFFSET) &= ~_BV(UARTEN); + HW_REG(uart_base[uartno]+UARTCTL_OFFSET) &= ~_BV(UART_UARTEN); /* set baudrate parameters */ uint8_t highspeed; - calc_baud_values(baudrate, - (uint16_t*)&HW_REG(uart_base[uartno]+UARTIBRD_OFFSET), - (uint8_t*)&HW_REG(uart_base[uartno]+UARTFBRD_OFFSET), - &highspeed); + uint16_t ibrd; + uint8_t fbrd; + calc_baud_values(baudrate, &ibrd, &fbrd, &highspeed); + tmp=HW_REG(uart_base[uartno]+UARTLCRH_OFFSET); + HW16_REG(uart_base[uartno]+UARTIBRD_OFFSET) = ibrd; + HW8_REG(uart_base[uartno]+UARTFBRD_OFFSET) = fbrd; + HW_REG(uart_base[uartno]+UARTLCRH_OFFSET) = tmp; /* wait until uart is no longer busy */ while(HW_REG(uart_base[uartno]+UARTFR_OFFSET)&_BV(UART_BUSY)) ; @@ -139,7 +147,7 @@ uint8_t uart_init(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint8_t p } HW_REG(uart_base[uartno]+UARTFR_OFFSET) = 0; HW_REG(uart_base[uartno]+UARTCTL_OFFSET) |= _BV(UART_RXE) | _BV(UART_TXE); - HW_REG(uart_base[uartno]+UARTCTL_OFFSET) |= _BV(UARTEN); + HW_REG(uart_base[uartno]+UARTCTL_OFFSET) |= _BV(UART_UARTEN); return UART_ERROR_OK; } diff --git a/test_src/uart_lowlevel.h b/test_src/uart_lowlevel.h index 1159fb1..68c30de 100644 --- a/test_src/uart_lowlevel.h +++ b/test_src/uart_lowlevel.h @@ -1,6 +1,6 @@ /* uart_lowlevel.h */ /* - This file is part of the ARM-Crypto-Lib. + This file is part of the AVR-Crypto-Lib. Copyright (C) 2010 Daniel Otte (daniel.otte@rub.de) This program is free software: you can redistribute it and/or modify @@ -27,10 +27,10 @@ #include "uart_defines.h" uint8_t uart_init(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint8_t paraty, uint8_t stopbits); -uint8_t uart_init_flow(uint8_t uartno, uint32_t baudrate, uint8_t databits, uint8_t paraty, uint8_t stopbits, uint8_t flowctrl); void uart_putc(uint8_t uartno, uint8_t byte); uint16_t uart_getc(uint8_t uartno); uint32_t uart_dataavail(uint8_t uartno); +void uart_flush(uint8_t uartno); #endif /* UART_LOWLEVEL_H_ */