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