- /* --- Start the main loop --- */
-
- for (;;) {
-
- /* --- While @u@ is even --- */
-
- {
- mpscan sc, xsc, ysc;
- size_t n = 0, nn = 0;
-
- MP_SCAN(&sc, u);
- MP_SCAN(&xsc, X); MP_SCAN(&ysc, Y);
- for (;;) {
- MP_STEP(&sc);
- MP_STEP(&xsc); MP_STEP(&ysc);
- if (MP_BIT(&sc))
- break;
- if ((f & f_ext) && (MP_BIT(&xsc) | MP_BIT(&ysc))) {
- if (n) {
- X = mp_lsr(X, X, n);
- Y = mp_lsr(Y, Y, n);
- n = 0;
- }
- X = mp_add(X, X, b);
- Y = mp_sub(Y, Y, a);
- MP_SCAN(&xsc, X);
- MP_SCAN(&ysc, Y);
- MP_STEP(&xsc); MP_STEP(&ysc);
- }
- n++; nn++;
- }
-
- if (nn) {
- u = mp_lsr(u, u, nn);
- if ((f & f_ext) && n) {
- X = mp_lsr(X, X, n);
- Y = mp_lsr(Y, Y, n);
- }
- }
- }
-
- /* --- While @v@ is even --- */
-
- {
- mpscan sc, xsc, ysc;
- size_t n = 0, nn = 0;
-
- MP_SCAN(&sc, v);
- MP_SCAN(&xsc, x); MP_SCAN(&ysc, y);
- for (;;) {
- MP_STEP(&sc);
- MP_STEP(&xsc); MP_STEP(&ysc);
- if (MP_BIT(&sc))
- break;
- if ((f & f_ext) && (MP_BIT(&xsc) | MP_BIT(&ysc))) {
- if (n) {
- x = mp_lsr(x, x, n);
- y = mp_lsr(y, y, n);
- n = 0;
- }
- x = mp_add(x, x, b);
- y = mp_sub(y, y, a);
- MP_SCAN(&xsc, x);
- MP_SCAN(&ysc, y);
- MP_STEP(&xsc); MP_STEP(&ysc);
- }
- n++; nn++;
- }
-
- if (nn) {
- v = mp_lsr(v, v, nn);
- if ((f & f_ext) && n) {
- x = mp_lsr(x, x, n);
- y = mp_lsr(y, y, n);
- }
- }
- }
-
- /* --- End-of-loop fiddling --- */
-
- if (MP_CMP(u, >=, v)) {
- u = mp_sub(u, u, v);
- if (f & f_ext) {
- X = mp_sub(X, X, x);
- Y = mp_sub(Y, Y, y);
- }
- } else {
- v = mp_sub(v, v, u);
- if (f & f_ext) {
- x = mp_sub(x, x, X);
- y = mp_sub(y, y, Y);
- }
+ while (MP_LEN(v)) {
+ mp *t;
+ mp_div(&q, &u, u, v);
+ if (f & f_ext) {
+ t = mp_mul(MP_NEW, X, q);
+ t = mp_sub(t, x, t);
+ MP_DROP(x); x = X; X = t;
+ t = mp_mul(MP_NEW, Y, q);
+ t = mp_sub(t, y, t);
+ MP_DROP(y); y = Y; Y = t;