-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_W==0 || y->length_W==0){
- return;
- }
- while(x->wordv[i]==0 && y->wordv[i]==0){
- ++i;
- }
- uint8_t g_b[i+2], x_b[x->length_W-i], y_b[y->length_W-i];
- uint8_t u_b[x->length_W-i], v_b[y->length_W-i];
- uint8_t a_b[y->length_W+2], c_b[y->length_W+2];
- uint8_t b_b[x->length_W+2], d_b[x->length_W+2];
-
- g.wordv = g_b;
- x_.wordv = x_b;
- y_.wordv = y_b;
- memset(g_b, 0, i);
- g_b[i]=1;
- g.length_W = i+1;
- g.info=0;
- x_.info = y_.info = 0;
- x_.length_W = x->length_W-i;
- y_.length_W = y->length_W-i;
- memcpy(x_.wordv, x->wordv+i, x_.length_W);
- memcpy(y_.wordv, y->wordv+i, y_.length_W);
- for(i=0; (x_.wordv[0]&(1<<i))==0 && (y_.wordv[0]&(1<<i))==0; ++i){
- }
-
- bigint_adjust(&x_);
- bigint_adjust(&y_);
-
- if(i){
- bigint_shiftleft(&g, i);
- bigint_shiftright(&x_, i);
- bigint_shiftright(&y_, i);
- }
- u.wordv = u_b;
- v.wordv = v_b;
- a_.wordv = a_b;
- b_.wordv = b_b;
- c_.wordv = c_b;
- d_.wordv = d_b;
-
- bigint_copy(&u, &x_);
- bigint_copy(&v, &y_);
- a_.wordv[0] = 1;
- a_.length_W = 1;
- a_.info = 0;
- d_.wordv[0] = 1;
- d_.length_W = 1;
- d_.info = 0;
- bigint_set_zero(&b_);
- bigint_set_zero(&c_);
- do{
- while((u.wordv[0]&1)==0){
- bigint_shiftright(&u, 1);
- if((a_.wordv[0]&1) || (b_.wordv[0]&1)){
- bigint_add_s(&a_, &a_, &y_);
- bigint_sub_s(&b_, &b_, &x_);
- }
- bigint_shiftright(&a_, 1);
- bigint_shiftright(&b_, 1);
- }
- while((v.wordv[0]&1)==0){
- bigint_shiftright(&v, 1);
- if((c_.wordv[0]&1) || (d_.wordv[0]&1)){
- bigint_add_s(&c_, &c_, &y_);
- bigint_sub_s(&d_, &d_, &x_);
- }
- bigint_shiftright(&c_, 1);
- bigint_shiftright(&d_, 1);
-
- }
- if(bigint_cmp_u(&u, &v)>=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_W);
- if(gcd){
- bigint_mul_s(gcd, &v, &g);
- }
- if(a){
- bigint_copy(a, &c_);
- }
- if(b){
- bigint_copy(b, &d_);
- }
+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_W == 0 || y->length_W == 0) {
+ return;
+ }
+ while (x->wordv[i] == 0 && y->wordv[i] == 0) {
+ ++i;
+ }
+ uint8_t g_b[i + 2], x_b[x->length_W - i], y_b[y->length_W - i];
+ uint8_t u_b[x->length_W - i], v_b[y->length_W - i];
+ uint8_t a_b[y->length_W + 2], c_b[y->length_W + 2];
+ uint8_t b_b[x->length_W + 2], d_b[x->length_W + 2];
+
+ g.wordv = g_b;
+ x_.wordv = x_b;
+ y_.wordv = y_b;
+ memset(g_b, 0, i);
+ g_b[i] = 1;
+ g.length_W = i + 1;
+ g.info = 0;
+ x_.info = y_.info = 0;
+ x_.length_W = x->length_W - i;
+ y_.length_W = y->length_W - i;
+ memcpy(x_.wordv, x->wordv + i, x_.length_W);
+ memcpy(y_.wordv, y->wordv + i, y_.length_W);
+ for (i = 0; (x_.wordv[0] & (1 << i)) == 0 && (y_.wordv[0] & (1 << i)) == 0;
+ ++i) {
+ }
+
+ bigint_adjust(&x_);
+ bigint_adjust(&y_);
+
+ if (i) {
+ bigint_shiftleft(&g, i);
+ bigint_shiftright(&x_, i);
+ bigint_shiftright(&y_, i);
+ }
+ u.wordv = u_b;
+ v.wordv = v_b;
+ a_.wordv = a_b;
+ b_.wordv = b_b;
+ c_.wordv = c_b;
+ d_.wordv = d_b;
+
+ bigint_copy(&u, &x_);
+ bigint_copy(&v, &y_);
+ a_.wordv[0] = 1;
+ a_.length_W = 1;
+ a_.info = 0;
+ d_.wordv[0] = 1;
+ d_.length_W = 1;
+ d_.info = 0;
+ bigint_set_zero(&b_);
+ bigint_set_zero(&c_);
+ do {
+ while ((u.wordv[0] & 1) == 0) {
+ bigint_shiftright(&u, 1);
+ if ((a_.wordv[0] & 1) || (b_.wordv[0] & 1)) {
+ bigint_add_s(&a_, &a_, &y_);
+ bigint_sub_s(&b_, &b_, &x_);
+ }
+ bigint_shiftright(&a_, 1);
+ bigint_shiftright(&b_, 1);
+ }
+ while ((v.wordv[0] & 1) == 0) {
+ bigint_shiftright(&v, 1);
+ if ((c_.wordv[0] & 1) || (d_.wordv[0] & 1)) {
+ bigint_add_s(&c_, &c_, &y_);
+ bigint_sub_s(&d_, &d_, &x_);
+ }
+ bigint_shiftright(&c_, 1);
+ bigint_shiftright(&d_, 1);
+
+ }
+ if (bigint_cmp_u(&u, &v) >= 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_W);
+ if (gcd) {
+ bigint_mul_s(gcd, &v, &g);
+ }
+ if (a) {
+ bigint_copy(a, &c_);
+ }
+ if (b) {
+ bigint_copy(b, &d_);
+ }