Mercurial > dropbear

comparison bn_mp_gcd.c @ 190:d8254fc979e9 libtommath-orig LTM_0.35

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import of libtommath 0.35
author Matt Johnston <matt@ucc.asn.au>
date Fri, 06 May 2005 08:59:30 +0000
parents d29b64170cf0
children
comparison
equal deleted inserted replaced
142:d29b64170cf0 190:d8254fc979e9
41 if ((res = mp_init_copy (&u, a)) != MP_OKAY) { 41 if ((res = mp_init_copy (&u, a)) != MP_OKAY) {
42 return res; 42 return res;
43 } 43 }
44 44
45 if ((res = mp_init_copy (&v, b)) != MP_OKAY) { 45 if ((res = mp_init_copy (&v, b)) != MP_OKAY) {
46 goto __U; 46 goto LBL_U;
47 } 47 }
48 48
49 /* must be positive for the remainder of the algorithm */ 49 /* must be positive for the remainder of the algorithm */
50 u.sign = v.sign = MP_ZPOS; 50 u.sign = v.sign = MP_ZPOS;
51 51
55 k = MIN(u_lsb, v_lsb); 55 k = MIN(u_lsb, v_lsb);
56 56
57 if (k > 0) { 57 if (k > 0) {
58 /* divide the power of two out */ 58 /* divide the power of two out */
59 if ((res = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) { 59 if ((res = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) {
60 goto __V; 60 goto LBL_V;
61 } 61 }
62 62
63 if ((res = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) { 63 if ((res = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) {
64 goto __V; 64 goto LBL_V;
65 } 65 }
66 } 66 }
67 67
68 /* divide any remaining factors of two out */ 68 /* divide any remaining factors of two out */
69 if (u_lsb != k) { 69 if (u_lsb != k) {
70 if ((res = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) { 70 if ((res = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) {
71 goto __V; 71 goto LBL_V;
72 } 72 }
73 } 73 }
74 74
75 if (v_lsb != k) { 75 if (v_lsb != k) {
76 if ((res = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) { 76 if ((res = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) {
77 goto __V; 77 goto LBL_V;
78 } 78 }
79 } 79 }
80 80
81 while (mp_iszero(&v) == 0) { 81 while (mp_iszero(&v) == 0) {
82 /* make sure v is the largest */ 82 /* make sure v is the largest */
85 mp_exch(&u, &v); 85 mp_exch(&u, &v);
86 } 86 }
87 87
88 /* subtract smallest from largest */ 88 /* subtract smallest from largest */
89 if ((res = s_mp_sub(&v, &u, &v)) != MP_OKAY) { 89 if ((res = s_mp_sub(&v, &u, &v)) != MP_OKAY) {
90 goto __V; 90 goto LBL_V;
91 } 91 }
92 92
93 /* Divide out all factors of two */ 93 /* Divide out all factors of two */
94 if ((res = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) { 94 if ((res = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) {
95 goto __V; 95 goto LBL_V;
96 } 96 }
97 } 97 }
98 98
99 /* multiply by 2**k which we divided out at the beginning */ 99 /* multiply by 2**k which we divided out at the beginning */
100 if ((res = mp_mul_2d (&u, k, c)) != MP_OKAY) { 100 if ((res = mp_mul_2d (&u, k, c)) != MP_OKAY) {
101 goto __V; 101 goto LBL_V;
102 } 102 }
103 c->sign = MP_ZPOS; 103 c->sign = MP_ZPOS;
104 res = MP_OKAY; 104 res = MP_OKAY;
105 __V:mp_clear (&u); 105 LBL_V:mp_clear (&u);
106 __U:mp_clear (&v); 106 LBL_U:mp_clear (&v);
107 return res; 107 return res;
108 } 108 }
109 #endif 109 #endif