65 	uint32_t r, a, b, u0, v0, u1, v1, he, hr;  in br_rsa_i31_compute_privexp()  local
161 	 * u0, u1, v0 and v1. Initial values are:  in br_rsa_i31_compute_privexp()
162 	 *   a = e    u0 = 1   v0 = 0  in br_rsa_i31_compute_privexp()
165 	 *   a = u0*e - v0*r  in br_rsa_i31_compute_privexp()
170 	 *   0 <= v0 <= e  in br_rsa_i31_compute_privexp()
175 	 * adjust u0, u1, v0 and v1 to maintain the invariants:  in br_rsa_i31_compute_privexp()
182 	 * key or public exponent is not valid). The (u0,v0) or (u1,v1)  in br_rsa_i31_compute_privexp()
191 	 *  - When a is divided by 2, u0 and v0 must be divided by 2.  in br_rsa_i31_compute_privexp()
194 	 *    u0 and v0, respectively.  in br_rsa_i31_compute_privexp()
195 	 *  - When a is subtracted from b, u0 and v0 are subtracted from  in br_rsa_i31_compute_privexp()
203 	 *     * If r is odd, then u0 and v0 must have the same parity;  in br_rsa_i31_compute_privexp()
204 	 *       if they are both odd, then adding r to u0 and e to v0  in br_rsa_i31_compute_privexp()
208 	 *     * If r is even, then u0 must be even; if v0 is odd, then  in br_rsa_i31_compute_privexp()
209 	 *       adding r to u0 and e to v0 makes them both even, and the  in br_rsa_i31_compute_privexp()
212 	 *    Thus, all we need to do is to look at the parity of v0,  in br_rsa_i31_compute_privexp()
213 	 *    and add (r,e) to (u0,v0) when v0 is odd. In order to avoid  in br_rsa_i31_compute_privexp()
220 	 *     * u1 <= u0 and v1 <= v0: just do the subtractions  in br_rsa_i31_compute_privexp()
222 	 *     * u1 > u0 and v1 > v0: compute:  in br_rsa_i31_compute_privexp()
223 	 *         (u0, v0) <- (u0 + r - u1, v0 + e - v1)  in br_rsa_i31_compute_privexp()
225 	 *     * u1 <= u0 and v1 > v0: compute:  in br_rsa_i31_compute_privexp()
226 	 *         (u0, v0) <- (u0 + r - u1, v0 + e - v1)  in br_rsa_i31_compute_privexp()
228 	 *    The fourth case (u1 > u0 and v1 <= v0) is not possible  in br_rsa_i31_compute_privexp()
238 	 *    solely on the comparison between v0 and v1.  in br_rsa_i31_compute_privexp()
243 	v0 = 0;  in br_rsa_i31_compute_privexp()
261 		/* a <- a-b, u0 <- u0-u1, v0 <- v0-v1 */  in br_rsa_i31_compute_privexp()
262 		ctl = GT(v1, v0);  in br_rsa_i31_compute_privexp()
265 		v0 -= (v1 - (e & -ctl)) & -sab;  in br_rsa_i31_compute_privexp()
267 		/* b <- b-a, u1 <- u1-u0 mod r, v1 <- v1-v0 mod e */  in br_rsa_i31_compute_privexp()
268 		ctl = GT(v0, v1);  in br_rsa_i31_compute_privexp()
271 		v1 -= (v0 - (e & -ctl)) & -sba;  in br_rsa_i31_compute_privexp()
276 		/* a <- a/2, u0 <- u0/2, v0 <- v0/2 */  in br_rsa_i31_compute_privexp()
277 		ctl = v0 & 1;  in br_rsa_i31_compute_privexp()
280 		v0 ^= (v0 ^ ((v0 >> 1) + (he & -ctl))) & -da;  in br_rsa_i31_compute_privexp()
298 	 * Now we have u0*e - v0*r = 1. Let's compute the result as:  in br_rsa_i31_compute_privexp()
299 	 *   d = u0 + v0*k  in br_rsa_i31_compute_privexp()
305 	m[1] = v0 & 0x7FFFFFFF;  in br_rsa_i31_compute_privexp()
306 	m[2] = v0 >> 31;  in br_rsa_i31_compute_privexp()