]> git.cryptolib.org Git - avr-crypto-lib.git/blob - bigint/bigint-stub.c
1a675597bd9921ba46da8d436d4d54d7675ee07b
[avr-crypto-lib.git] / 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