bigint/bigint-stub.c

   1 /* bigint.c */
   2 /*
   3     This file is part of the AVR-Crypto-Lib.
   4     Copyright (C) 2008  Daniel Otte (daniel.otte@rub.de)
   5
   6     This program is free software: you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation, either version 3 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18 */
  19 /**
  20  * \file                bigint.c
  21  * \author              Daniel Otte
  22  * \date                2010-02-22
  23  *
  24  * \license         GPLv3 or later
  25  *
  26  */
  27
  28
  29 #define STRING2(x) #x
  30 #define STRING(x) STRING2(x)
  31 #define STR_LINE STRING(__LINE__)
  32
  33 #include "bigint.h"
  34 #include <string.h>
  35 /*
  36 #include "cli.h"
  37 #include "bigint_io.h"
  38 */
  39 #ifndef MAX
  40  #define MAX(a,b) (((a)>(b))?(a):(b))
  41 #endif
  42
  43 #ifndef MIN
  44  #define MIN(a,b) (((a)<(b))?(a):(b))
  45 #endif
  46
  47 #define SET_FBS(a, v) do{(a)->info &=0xF8; (a)->info |= (v);}while(0)
  48 #define GET_FBS(a)   ((a)->info&BIGINT_FBS_MASK)
  49 #define SET_NEG(a)   (a)->info |= BIGINT_NEG_MASK
  50 #define SET_POS(a)   (a)->info &= ~BIGINT_NEG_MASK
  51 #define XCHG(a,b)    do{(a)^=(b); (b)^=(a); (a)^=(b);}while(0)
  52 #define XCHG_PTR(a,b)    do{ a = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b))); \
  53                                  b = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b))); \
  54                                  a = (void*)(((uint16_t)(a)) ^ ((uint16_t)(b)));}while(0)
  55
  56 #define GET_SIGN(a) ((a)->info&BIGINT_NEG_MASK)
  57
  58
  59 /******************************************************************************/
  60 /*
  61 void bigint_copy(bigint_t *dest, const bigint_t *src){
  62         memcpy(dest->wordv, src->wordv, src->length_W);
  63         dest->length_W = src->length_W;
  64         dest->info = src->info;
  65 }
  66 */
  67 /******************************************************************************/
  68
  69 /* this should be implemented in assembly */
  70 /*
  71 void bigint_add_u(bigint_t *dest, const bigint_t *a, const bigint_t *b){
  72         uint16_t t=0, i;
  73         if(a->length_W < b->length_W){
  74                 XCHG_PTR(a,b);
  75         }
  76         for(i=0; i<b->length_W; ++i){
  77                 t = a->wordv[i] + b->wordv[i] + t;
  78                 dest->wordv[i] = (uint8_t)t;
  79                 t>>=8;
  80         }
  81         for(; i<a->length_W; ++i){
  82                 t = a->wordv[i] + t;
  83                 dest->wordv[i] = (uint8_t)t;
  84                 t>>=8;
  85         }
  86         dest->wordv[i++] = t;
  87         dest->length_W = i;
  88         bigint_adjust(dest);
  89 }
  90 */
  91 /******************************************************************************/
  92
  93 /* this should be implemented in assembly */
  94 /*
  95 void bigint_add_scale_u(bigint_t *dest, const bigint_t *a, uint16_t scale){
  96         uint16_t i,j=0;
  97         uint16_t t=0;
  98         if(scale>dest->length_W)
  99                 memset(dest->wordv+dest->length_W, 0, scale-dest->length_W);
 100         for(i=scale; i<a->length_W+scale; ++i,++j){
 101                 t = a->wordv[j] + t;
 102                 if(dest->length_W>i){
 103                         t += dest->wordv[i];
 104                 }
 105                 dest->wordv[i] = (uint8_t)t;
 106                 t>>=8;
 107         }
 108         while(t){
 109                 if(dest->length_W>i){
 110                         t = dest->wordv[i] + t;
 111                 }
 112                 dest->wordv[i] = (uint8_t)t;
 113                 t>>=8;
 114                 ++i;
 115         }
 116         if(dest->length_W < i){
 117                 dest->length_W = i;
 118         }
 119         bigint_adjust(dest);
 120 }
 121 */
 122 /******************************************************************************/
 123
 124 /* this should be implemented in assembly */
 125 void bigint_sub_u(bigint_t *dest, const bigint_t *a, const bigint_t *b){
 126         int8_t borrow=0;
 127         int8_t  r;
 128         int16_t t;
 129         uint16_t i, min, max;
 130         min = MIN(a->length_W, b->length_W);
 131         max = MAX(a->length_W, b->length_W);
 132         r = bigint_cmp_u(a,b);
 133         if(r==0){
 134                 dest->length_W = 0;
 135                 dest->wordv[0] = 0;
 136                 bigint_adjust(dest);
 137                 return;
 138         }
 139         if(b->length_W==0){
 140                 dest->length_W = a->length_W;
 141                 memcpy(dest->wordv, a->wordv, a->length_W);
 142                 dest->info = a->info;
 143                 SET_POS(dest);
 144                 return;
 145         }
 146         if(a->length_W==0){
 147                         dest->length_W = b->length_W;
 148                         memcpy(dest->wordv, b->wordv, b->length_W);
 149                         dest->info = b->info;
 150                         SET_NEG(dest);
 151                         return;
 152         }
 153         if(r<0){
 154                 bigint_sub_u(dest, b, a);
 155                 SET_NEG(dest);
 156         }else{
 157                 for(i=0; i<min; ++i){
 158                         t = a->wordv[i] - b->wordv[i] - borrow;
 159                         if(t<0){
 160                                 borrow = 1;
 161                                 dest->wordv[i]=(uint8_t)t;
 162                         }else{
 163                                 borrow = 0;
 164                                 dest->wordv[i]=(uint8_t)t;
 165                         }
 166                 }
 167                 for(;i<max; ++i){
 168                         t = a->wordv[i] - borrow;
 169                         if(t<0){
 170                                 borrow = 1;
 171                                 dest->wordv[i]=(uint8_t)t;
 172                         }else{
 173                                 borrow = 0;
 174                                 dest->wordv[i]=(uint8_t)t;
 175                         }
 176
 177                 }
 178                 SET_POS(dest);
 179                 dest->length_W = i;
 180                 bigint_adjust(dest);
 181         }
 182 }
 183
 184 /******************************************************************************/
 185
 186 int8_t bigint_cmp_u(const bigint_t *a, const bigint_t *b){
 187         if(a->length_W > b->length_W){
 188                 return 1;
 189         }
 190         if(a->length_W < b->length_W){
 191                 return -1;
 192         }
 193         if(a->length_W==0){
 194                 return 0;
 195         }
 196         uint16_t i;
 197         i = a->length_W-1;
 198         do{
 199                 if(a->wordv[i]!=b->wordv[i]){
 200                         if(a->wordv[i]>b->wordv[i]){
 201                                 return 1;
 202                         }else{
 203                                 return -1;
 204                         }
 205                 }
 206         }while(i--);
 207         return 0;
 208 }
 209
 210 /******************************************************************************/
 211
 212 void bigint_add_s(bigint_t *dest, const bigint_t *a, const bigint_t *b){
 213         uint8_t s;
 214         s  = GET_SIGN(a)?2:0;
 215         s |= GET_SIGN(b)?1:0;
 216         switch(s){
 217                 case 0: /* both positive */
 218                         bigint_add_u(dest, a,b);
 219                         SET_POS(dest);
 220                         break;
 221                 case 1: /* a positive, b negative */
 222                         bigint_sub_u(dest, a, b);
 223                         break;
 224                 case 2: /* a negative, b positive */
 225                         bigint_sub_u(dest, b, a);
 226                         break;
 227                 case 3: /* both negative */
 228                         bigint_add_u(dest, a, b);
 229                         SET_NEG(dest);
 230                         break;
 231                 default: /* how can this happen?*/
 232                         break;
 233         }
 234 }
 235
 236 /******************************************************************************/
 237
 238 void bigint_sub_s(bigint_t *dest, const bigint_t *a, const bigint_t *b){
 239         uint8_t s;
 240         s  = GET_SIGN(a)?2:0;
 241         s |= GET_SIGN(b)?1:0;
 242         switch(s){
 243                 case 0: /* both positive */
 244                         bigint_sub_u(dest, a,b);
 245                         break;
 246                 case 1: /* a positive, b negative */
 247                         bigint_add_u(dest, a, b);
 248                         SET_POS(dest);
 249                         break;
 250                 case 2: /* a negative, b positive */
 251                         bigint_add_u(dest, a, b);
 252                         SET_NEG(dest);
 253                         break;
 254                 case 3: /* both negative */
 255                         bigint_sub_u(dest, b, a);
 256                         break;
 257                 default: /* how can this happen?*/
 258                                         break;
 259         }
 260
 261 }
 262
 263 /******************************************************************************/
 264
 265 int8_t bigint_cmp_s(const bigint_t *a, const bigint_t *b){
 266         uint8_t s;
 267         if(a->length_W==0 && b->length_W==0){
 268                 return 0;
 269         }
 270         s  = GET_SIGN(a)?2:0;
 271         s |= GET_SIGN(b)?1:0;
 272         switch(s){
 273                 case 0: /* both positive */
 274                         return bigint_cmp_u(a, b);
 275                         break;
 276                 case 1: /* a positive, b negative */
 277                         return 1;
 278                         break;
 279                 case 2: /* a negative, b positive */
 280                         return -1;
 281                         break;
 282                 case 3: /* both negative */
 283                         return bigint_cmp_u(b, a);
 284                         break;
 285                 default: /* how can this happen?*/
 286                                         break;
 287         }
 288         return 0; /* just to satisfy the compiler */
 289 }
 290
 291 /******************************************************************************/
 292
 293 void bigint_shiftleft(bigint_t *a, uint16_t shift){
 294         uint16_t byteshift;
 295         uint16_t i;
 296         uint8_t bitshift;
 297         uint16_t t=0;
 298         byteshift = (shift+3)/8;
 299         bitshift = shift&7;
 300         memmove(a->wordv+byteshift, a->wordv, a->length_W);
 301         memset(a->wordv, 0, byteshift);
 302         if(bitshift!=0){
 303                 if(bitshift<=4){ /* shift to the left */
 304                         for(i=byteshift; i<a->length_W+byteshift; ++i){
 305                                 t |= (a->wordv[i])<<bitshift;
 306                                 a->wordv[i] = (uint8_t)t;
 307                                 t >>= 8;
 308                         }
 309                         a->wordv[i] = (uint8_t)t;
 310                         byteshift++;
 311                 }else{ /* shift to the right */
 312                         for(i=a->length_W+byteshift-1; i>byteshift-1; --i){
 313                                 t |= (a->wordv[i])<<(bitshift);
 314                                 a->wordv[i] = (uint8_t)(t>>8);
 315                                 t <<= 8;
 316                         }
 317                         t |= (a->wordv[i])<<(bitshift);
 318                         a->wordv[i] = (uint8_t)(t>>8);
 319                 }
 320         }
 321         a->length_W += byteshift;
 322         bigint_adjust(a);
 323 }
 324
 325 /******************************************************************************/
 326
 327 void bigint_shiftright(bigint_t *a, uint16_t shift){
 328         uint16_t byteshift;
 329         uint16_t i;
 330         uint8_t bitshift;
 331         uint16_t t=0;
 332         byteshift = shift/8;
 333         bitshift = shift&7;
 334         if(byteshift >= a->length_W){ /* we would shift out more than we have */
 335                 bigint_set_zero(a);
 336                 return;
 337         }
 338         if(byteshift == a->length_W-1 && bitshift>GET_FBS(a)){
 339                 bigint_set_zero(a);
 340                 return;
 341         }
 342         if(byteshift){
 343                 memmove(a->wordv, a->wordv+byteshift, a->length_W-byteshift);
 344                 memset(a->wordv+a->length_W-byteshift, 0,  byteshift);
 345         }
 346         if(bitshift!=0){
 347          /* shift to the right */
 348                 for(i=a->length_W-byteshift-1; i>0; --i){
 349                         t |= (a->wordv[i])<<(8-bitshift);
 350                         a->wordv[i] = (uint8_t)(t>>8);
 351                         t <<= 8;
 352                 }
 353                 t |= (a->wordv[0])<<(8-bitshift);
 354                 a->wordv[0] = (uint8_t)(t>>8);
 355         }
 356         a->length_W -= byteshift;
 357         bigint_adjust(a);
 358 }
 359
 360 /******************************************************************************/
 361
 362 void bigint_xor(bigint_t *dest, const bigint_t *a){
 363         uint16_t i;
 364         for(i=0; i<a->length_W; ++i){
 365                 dest->wordv[i] ^= a->wordv[i];
 366         }
 367         bigint_adjust(dest);
 368 }
 369
 370 /******************************************************************************/
 371
 372 void bigint_set_zero(bigint_t *a){
 373         a->length_W=0;
 374 }
 375
 376 /******************************************************************************/
 377
 378 /* using the Karatsuba-Algorithm */
 379 /* x*y = (xh*yh)*b**2n + ((xh+xl)*(yh+yl) - xh*yh - xl*yl)*b**n + yh*yl */
 380 void bigint_mul_u(bigint_t *dest, const bigint_t *a, const bigint_t *b){
 381         if(a->length_W==0 || b->length_W==0){
 382                 bigint_set_zero(dest);
 383                 return;
 384         }
 385         if(dest==a || dest==b){
 386                 bigint_t d;
 387                 uint8_t d_b[a->length_W+b->length_W];
 388                 d.wordv = d_b;
 389                 bigint_mul_u(&d, a, b);
 390                 bigint_copy(dest, &d);
 391                 return;
 392         }
 393         if(a->length_W==1 || b->length_W==1){
 394                 if(a->length_W!=1){
 395                         XCHG_PTR(a,b);
 396                 }
 397                 uint16_t i, t=0;
 398                 uint8_t x = a->wordv[0];
 399                 for(i=0; i<b->length_W; ++i){
 400                         t += b->wordv[i]*x;
 401                         dest->wordv[i] = (uint8_t)t;
 402                         t>>=8;
 403                 }
 404                 dest->wordv[i] = (uint8_t)t;
 405                 dest->length_W=i+1;
 406                 bigint_adjust(dest);
 407                 return;
 408         }
 409         if(a->length_W<=4 && b->length_W<=4){
 410                 uint32_t p=0, q=0;
 411                 uint64_t r;
 412                 memcpy(&p, a->wordv, a->length_W);
 413                 memcpy(&q, b->wordv, b->length_W);
 414                 r = (uint64_t)p*(uint64_t)q;
 415                 memcpy(dest->wordv, &r, a->length_W+b->length_W);
 416                 dest->length_W =  a->length_W+b->length_W;
 417                 bigint_adjust(dest);
 418                 return;
 419         }
 420         bigint_set_zero(dest);
 421         /* split a in xh & xl; split b in yh & yl */
 422         uint16_t n;
 423         n=(MAX(a->length_W, b->length_W)+1)/2;
 424         bigint_t xl, xh, yl, yh;
 425         xl.wordv = a->wordv;
 426         yl.wordv = b->wordv;
 427         if(a->length_W<=n){
 428                 xh.info=0;
 429                 xh.length_W = 0;
 430                 xl.length_W = a->length_W;
 431                 xl.info = 0;
 432         }else{
 433                 xl.length_W=n;
 434                 xl.info = 0;
 435                 bigint_adjust(&xl);
 436                 xh.wordv = a->wordv+n;
 437                 xh.length_W = a->length_W-n;
 438                 xh.info = 0;
 439         }
 440         if(b->length_W<=n){
 441                 yh.info=0;
 442                 yh.length_W = 0;
 443                 yl.length_W = b->length_W;
 444                 yl.info = b->info;
 445         }else{
 446                 yl.length_W=n;
 447                 yl.info = 0;
 448                 bigint_adjust(&yl);
 449                 yh.wordv = b->wordv+n;
 450                 yh.length_W = b->length_W-n;
 451                 yh.info = 0;
 452         }
 453         /* now we have split up a and b */
 454         uint8_t  tmp_b[2*n+2], m_b[2*(n+1)];
 455         bigint_t tmp, tmp2, m;
 456         tmp.wordv = tmp_b;
 457         tmp2.wordv = tmp_b+n+1;
 458         m.wordv = m_b;
 459
 460         bigint_mul_u(dest, &xl, &yl);  /* dest <= xl*yl     */
 461         bigint_add_u(&tmp2, &xh, &xl); /* tmp2 <= xh+xl     */
 462         bigint_add_u(&tmp, &yh, &yl);  /* tmp  <= yh+yl     */
 463         bigint_mul_u(&m, &tmp2, &tmp); /* m    <= tmp2*tmp  */
 464         bigint_mul_u(&tmp, &xh, &yh);  /* h    <= xh*yh     */
 465         bigint_sub_u(&m, &m, dest);    /* m    <= m-dest    */
 466     bigint_sub_u(&m, &m, &tmp);    /* m    <= m-h       */
 467         bigint_add_scale_u(dest, &m, n);
 468         bigint_add_scale_u(dest, &tmp, 2*n);
 469 }
 470
 471 /******************************************************************************/
 472
 473 void bigint_mul_s(bigint_t *dest, const bigint_t *a, const bigint_t *b){
 474         uint8_t s;
 475         s  = GET_SIGN(a)?2:0;
 476         s |= GET_SIGN(b)?1:0;
 477         switch(s){
 478                 case 0: /* both positive */
 479                         bigint_mul_u(dest, a,b);
 480                         SET_POS(dest);
 481                         break;
 482                 case 1: /* a positive, b negative */
 483                         bigint_mul_u(dest, a,b);
 484                         SET_NEG(dest);
 485                         break;
 486                 case 2: /* a negative, b positive */
 487                         bigint_mul_u(dest, a,b);
 488                         SET_NEG(dest);
 489                         break;
 490                 case 3: /* both negative */
 491                         bigint_mul_u(dest, a,b);
 492                         SET_POS(dest);
 493                         break;
 494                 default: /* how can this happen?*/
 495                         break;
 496         }
 497 }
 498
 499 /******************************************************************************/
 500
 501 /* square */
 502 /* (xh*b^n+xl)^2 = xh^2*b^2n + 2*xh*xl*b^n + xl^2 */
 503 void bigint_square(bigint_t *dest, const bigint_t *a){
 504         if(a->length_W<=4){
 505                 uint64_t r=0;
 506                 memcpy(&r, a->wordv, a->length_W);
 507                 r = r*r;
 508                 memcpy(dest->wordv, &r, 2*a->length_W);
 509                 SET_POS(dest);
 510                 dest->length_W=2*a->length_W;
 511                 bigint_adjust(dest);
 512                 return;
 513         }
 514         if(dest==a){
 515                 bigint_t d;
 516                 uint8_t d_b[a->length_W*2];
 517                 d.wordv = d_b;
 518                 bigint_square(&d, a);
 519                 bigint_copy(dest, &d);
 520                 return;
 521         }
 522         uint16_t n;
 523         n=(a->length_W+1)/2;
 524         bigint_t xh, xl, tmp; /* x-high, x-low, temp */
 525         uint8_t buffer[2*n+1];
 526         xl.wordv = a->wordv;
 527         xl.length_W = n;
 528         xh.wordv = a->wordv+n;
 529         xh.length_W = a->length_W-n;
 530         tmp.wordv = buffer;
 531         bigint_square(dest, &xl);
 532         bigint_square(&tmp, &xh);
 533         bigint_add_scale_u(dest, &tmp, 2*n);
 534         bigint_mul_u(&tmp, &xl, &xh);
 535         bigint_shiftleft(&tmp, 1);
 536         bigint_add_scale_u(dest, &tmp, n);
 537 }
 538
 539 /******************************************************************************/
 540
 541 void bigint_sub_u_bitscale(bigint_t *a, const bigint_t *b, uint16_t bitscale){
 542         bigint_t tmp;
 543         uint8_t tmp_b[b->length_W+1];
 544         uint16_t i,j,byteshift=bitscale/8;
 545         uint8_t borrow=0;
 546         int16_t t;
 547
 548         if(a->length_W < b->length_W+byteshift){
 549                 bigint_set_zero(a);
 550                 return;
 551         }
 552
 553         tmp.wordv = tmp_b;
 554         bigint_copy(&tmp, b);
 555         bigint_shiftleft(&tmp, bitscale&7);
 556
 557         for(j=0,i=byteshift; i<tmp.length_W+byteshift; ++i, ++j){
 558                 t = a->wordv[i] - tmp.wordv[j] - borrow;
 559                 a->wordv[i] = (uint8_t)t;
 560                 if(t<0){
 561                         borrow = 1;
 562                 }else{
 563                         borrow = 0;
 564                 }
 565         }
 566         while(borrow){
 567                 if(i+1 > a->length_W){
 568                         bigint_set_zero(a);
 569                         return;
 570                 }
 571                 a->wordv[i] -= borrow;
 572                 if(a->wordv[i]!=0xff){
 573                         borrow=0;
 574                 }
 575                 ++i;
 576         }
 577         bigint_adjust(a);
 578 }
 579
 580 /******************************************************************************/
 581
 582 void bigint_reduce(bigint_t *a, const bigint_t *r){
 583 //      bigint_adjust(r);
 584         uint8_t rfbs = GET_FBS(r);
 585
 586         if(r->length_W==0 || a->length_W==0){
 587                 return;
 588         }
 589         while(a->length_W > r->length_W){
 590                 bigint_sub_u_bitscale(a, r, (a->length_W-r->length_W)*8+GET_FBS(a)-rfbs-1);
 591         }
 592         while((GET_FBS(a) > rfbs+1) && (a->length_W == r->length_W)){
 593                 bigint_sub_u_bitscale(a, r, GET_FBS(a)-rfbs-1);
 594         }
 595         while(bigint_cmp_u(a,r)>=0){
 596                 bigint_sub_u(a,a,r);
 597         }
 598         bigint_adjust(a);
 599 }
 600
 601 /******************************************************************************/
 602
 603 /* calculate dest = a**exp % r */
 604 /* using square&multiply */
 605 void bigint_expmod_u(bigint_t *dest, const bigint_t *a, const bigint_t *exp, const bigint_t *r){
 606         if(a->length_W==0 || r->length_W==0){
 607                 return;
 608         }
 609
 610         bigint_t res, base;
 611         uint8_t base_b[MAX(a->length_W,r->length_W*2)], res_b[r->length_W*2];
 612         uint16_t i;
 613         uint8_t j, t;
 614         res.wordv = res_b;
 615         base.wordv = base_b;
 616         bigint_copy(&base, a);
 617         bigint_reduce(&base, r);
 618         res.wordv[0]=1;
 619         res.length_W=1;
 620         res.info = 0;
 621         bigint_adjust(&res);
 622         for(i=0; i+1<exp->length_W; ++i){
 623                 t=exp->wordv[i];
 624                 for(j=0; j<8; ++j){
 625                         if(t&1){
 626                                 bigint_mul_u(&res, &res, &base);
 627                                 bigint_reduce(&res, r);
 628                         }
 629                         bigint_square(&base, &base);
 630                         bigint_reduce(&base, r);
 631                         t>>=1;
 632                 }
 633         }
 634         t=exp->wordv[i];
 635         while(t){
 636                 if(t&1){
 637                         bigint_mul_u(&res, &res, &base);
 638                         bigint_reduce(&res, r);
 639                 }
 640                 bigint_square(&base, &base);
 641                 bigint_reduce(&base, r);
 642                 t>>=1;
 643         }
 644         SET_POS(&res);
 645         bigint_copy(dest, &res);
 646 }
 647
 648 /******************************************************************************/
 649 /* gcd <-- gcd(x,y) a*x+b*y=gcd */
 650 void bigint_gcdext(bigint_t *gcd, bigint_t *a, bigint_t *b, const bigint_t *x, const bigint_t *y){
 651          bigint_t g, x_, y_, u, v, a_, b_, c_, d_;
 652          volatile uint16_t i=0;
 653          if(x->length_W==0 || y->length_W==0){
 654                  return;
 655          }
 656          while(x->wordv[i]==0 && y->wordv[i]==0){
 657                  ++i;
 658          }
 659          uint8_t g_b[i+2], x_b[x->length_W-i], y_b[y->length_W-i];
 660          uint8_t u_b[x->length_W-i], v_b[y->length_W-i];
 661          uint8_t a_b[y->length_W+2], c_b[y->length_W+2];
 662          uint8_t b_b[x->length_W+2], d_b[x->length_W+2];
 663
 664          g.wordv = g_b;
 665          x_.wordv = x_b;
 666          y_.wordv = y_b;
 667          memset(g_b, 0, i);
 668          g_b[i]=1;
 669          g.length_W = i+1;
 670          g.info=0;
 671          x_.info = y_.info = 0;
 672          x_.length_W = x->length_W-i;
 673          y_.length_W = y->length_W-i;
 674          memcpy(x_.wordv, x->wordv+i, x_.length_W);
 675          memcpy(y_.wordv, y->wordv+i, y_.length_W);
 676          for(i=0; (x_.wordv[0]&(1<<i))==0 && (y_.wordv[0]&(1<<i))==0; ++i){
 677          }
 678
 679          bigint_adjust(&x_);
 680          bigint_adjust(&y_);
 681
 682          if(i){
 683                  bigint_shiftleft(&g, i);
 684                  bigint_shiftright(&x_, i);
 685                  bigint_shiftright(&y_, i);
 686          }
 687          u.wordv = u_b;
 688          v.wordv = v_b;
 689          a_.wordv = a_b;
 690          b_.wordv = b_b;
 691          c_.wordv = c_b;
 692          d_.wordv = d_b;
 693
 694          bigint_copy(&u, &x_);
 695          bigint_copy(&v, &y_);
 696          a_.wordv[0] = 1;
 697          a_.length_W = 1;
 698          a_.info = 0;
 699          d_.wordv[0] = 1;
 700          d_.length_W = 1;
 701          d_.info = 0;
 702          bigint_set_zero(&b_);
 703          bigint_set_zero(&c_);
 704          do{
 705                  while((u.wordv[0]&1)==0){
 706                          bigint_shiftright(&u, 1);
 707                          if((a_.wordv[0]&1) || (b_.wordv[0]&1)){
 708                                  bigint_add_s(&a_, &a_, &y_);
 709                                  bigint_sub_s(&b_, &b_, &x_);
 710                          }
 711                          bigint_shiftright(&a_, 1);
 712                          bigint_shiftright(&b_, 1);
 713                  }
 714                  while((v.wordv[0]&1)==0){
 715                          bigint_shiftright(&v, 1);
 716                          if((c_.wordv[0]&1) || (d_.wordv[0]&1)){
 717                                  bigint_add_s(&c_, &c_, &y_);
 718                                  bigint_sub_s(&d_, &d_, &x_);
 719                          }
 720                          bigint_shiftright(&c_, 1);
 721                          bigint_shiftright(&d_, 1);
 722
 723                  }
 724                  if(bigint_cmp_u(&u, &v)>=0){
 725                         bigint_sub_u(&u, &u, &v);
 726                         bigint_sub_s(&a_, &a_, &c_);
 727                         bigint_sub_s(&b_, &b_, &d_);
 728                  }else{
 729                         bigint_sub_u(&v, &v, &u);
 730                         bigint_sub_s(&c_, &c_, &a_);
 731                         bigint_sub_s(&d_, &d_, &b_);
 732                  }
 733          }while(u.length_W);
 734          if(gcd){
 735                  bigint_mul_s(gcd, &v, &g);
 736          }
 737          if(a){
 738                 bigint_copy(a, &c_);
 739          }
 740          if(b){
 741                  bigint_copy(b, &d_);
 742          }
 743 }
 744
 745 /******************************************************************************/
 746
 747 void bigint_inverse(bigint_t *dest, const bigint_t *a, const bigint_t *m){
 748         bigint_gcdext(NULL, dest, NULL, a, m);
 749         while(dest->info&BIGINT_NEG_MASK){
 750                 bigint_add_s(dest, dest, m);
 751         }
 752 }
 753
 754 /******************************************************************************/
 755
 756 void bigint_changeendianess(bigint_t *a){
 757         uint8_t t, *p, *q;
 758         p = a->wordv;
 759         q = p+a->length_W-1;
 760         while(p<q){
 761                 t = *p;
 762                 *p = *q;
 763                 *q = t;
 764                 ++p; --q;
 765         }
 766 }
 767
 768 /******************************************************************************/
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791