29  * without the usual one-word header. Value is split into 15-bit words,
30  * each stored in a 16-bit slot (top bit is zero) in little-endian
37  * Negate big integer conditionally. The value consists of 'len' words,
43 cond_negate(uint16_t *a, size_t len, uint32_t ctl)  in cond_negate()  argument
49 	xm = 0x7FFF & -ctl;  in cond_negate()
50 	for (k = 0; k < len; k ++) {  in cond_negate()
63  *   if neg = 1, then -m <= a < 0
71 finish_mod(uint16_t *a, size_t len, const uint16_t *m, uint32_t neg)  in finish_mod()  argument
80 	for (k = 0; k < len; k ++) {  in finish_mod()
85 		cc = (aw - mw - cc) >> 31;  in finish_mod()
94 	xm = 0x7FFF & -neg;  in finish_mod()
95 	ym = -(neg | (1 - cc));  in finish_mod()
97 	for (k = 0; k < len; k ++) {  in finish_mod()
102 		aw = aw - mw - cc;  in finish_mod()
110  *   a <- (a*pa+b*pb)/(2^15)
111  *   b <- (a*qa+b*qb)/(2^15)
112  * The division is assumed to be exact (i.e. the low word is dropped).
123 co_reduce(uint16_t *a, uint16_t *b, size_t len,  in co_reduce()  argument
132 	for (k = 0; k < len; k ++) {  in co_reduce()
140 		 *   0 <= wa <= 2^15 - 1  in co_reduce()
141 		 *   0 <= wb <= 2^15 - 1  in co_reduce()
142 		 *   |cca| <= 2^16 - 1  in co_reduce()
144 		 *   |za| <= (2^15-1)*(2^16) + (2^16-1) = 2^31 - 1  in co_reduce()
146 		 * Thus, the new value of cca is such that |cca| <= 2^16 - 1.  in co_reduce()
154 			a[k - 1] = za & 0x7FFF;  in co_reduce()
155 			b[k - 1] = zb & 0x7FFF;  in co_reduce()
162 	a[len - 1] = (uint16_t)cca;  in co_reduce()
163 	b[len - 1] = (uint16_t)ccb;  in co_reduce()
166 	cond_negate(a, len, nega);  in co_reduce()
167 	cond_negate(b, len, negb);  in co_reduce()
173  *   a <- (a*pa+b*pb)/(2^15) mod m
174  *   b <- (a*qa+b*qb)/(2^15) mod m
176  * m0i is equal to -1/m[0] mod 2^15.
183 co_reduce_mod(uint16_t *a, uint16_t *b, size_t len,  in co_reduce_mod()  argument
194 	for (k = 0; k < len; k ++) {  in co_reduce_mod()
209 			a[k - 1] = za & 0x7FFF;  in co_reduce_mod()
210 			b[k - 1] = zb & 0x7FFF;  in co_reduce_mod()
214 		 * The XOR-and-sub construction below does an arithmetic  in co_reduce_mod()
215 		 * right shift in a portable way (technically, right-shifting  in co_reduce_mod()
216 		 * a negative signed value is implementation-defined in C).  in co_reduce_mod()
221 		tta = (tta ^ M) - M;  in co_reduce_mod()
222 		ttb = (ttb ^ M) - M;  in co_reduce_mod()
227 	a[len - 1] = (uint32_t)cca;  in co_reduce_mod()
228 	b[len - 1] = (uint32_t)ccb;  in co_reduce_mod()
232 	 *   -m <= a < 2*m  in co_reduce_mod()
233 	 *   -m <= b < 2*m  in co_reduce_mod()
235 	 * The top word of 'a' and 'b' may have a 16-th bit set.  in co_reduce_mod()
238 	finish_mod(a, len, m, (uint32_t)cca >> 31);  in co_reduce_mod()
239 	finish_mod(b, len, m, (uint32_t)ccb >> 31);  in co_reduce_mod()
263 	 *   - If a is even, then a <- a/2 and u <- u/2 mod m.  in br_i15_moddiv()
264 	 *   - Otherwise, if b is even, then b <- b/2 and v <- v/2 mod m.  in br_i15_moddiv()
265 	 *   - Otherwise, if a > b, then a <- (a-b)/2 and u <- (u-v)/2 mod m.  in br_i15_moddiv()
266 	 *   - Otherwise, b <- (b-a)/2 and v <- (v-u)/2 mod m.  in br_i15_moddiv()
274 	 * if m has bit length k bits, then 2k-2 steps are sufficient.  in br_i15_moddiv()
277 	 * Though complexity is quadratic in the size of m, the bit-by-bit  in br_i15_moddiv()
290 	 * the division being exact.  in br_i15_moddiv()
294 	 * pa with -pa, and pb with -pb. The total length of a and b is  in br_i15_moddiv()
304 	size_t len, k;  in br_i15_moddiv()  local
308 	len = (m[0] + 15) >> 4;  in br_i15_moddiv()
310 	b = a + len;  in br_i15_moddiv()
312 	v = b + len;  in br_i15_moddiv()
313 	memcpy(a, y + 1, len * sizeof *y);  in br_i15_moddiv()
314 	memcpy(b, m + 1, len * sizeof *m);  in br_i15_moddiv()
315 	memset(v, 0, len * sizeof *v);  in br_i15_moddiv()
321 	for (num = ((m[0] - (m[0] >> 4)) << 1) + 14; num >= 14; num -= 14) {  in br_i15_moddiv()
332 		 * (a[j] << 15) + a[j - 1], and (b[j] << 15) + b[j - 1].  in br_i15_moddiv()
336 		c0 = (uint32_t)-1;  in br_i15_moddiv()
337 		c1 = (uint32_t)-1;  in br_i15_moddiv()
342 		j = len;  in br_i15_moddiv()
343 		while (j -- > 0) {  in br_i15_moddiv()
353 			c0 &= (((aw | bw) + 0xFFFF) >> 16) - (uint32_t)1;  in br_i15_moddiv()
388 			 *   a <- (a-b)/2 if: a is odd, b is odd, a_hi > b_hi  in br_i15_moddiv()
389 			 *   b <- (b-a)/2 if: a is odd, b is odd, a_hi <= b_hi  in br_i15_moddiv()
390 			 *   a <- a/2 if: a is even  in br_i15_moddiv()
391 			 *   b <- b/2 if: a is odd, b is even  in br_i15_moddiv()
395 			 * non-multiplication by 2.  in br_i15_moddiv()
419 			a_lo -= b_lo & -cAB;  in br_i15_moddiv()
420 			a_hi -= b_hi & -cAB;  in br_i15_moddiv()
421 			pa -= qa & -(int32_t)cAB;  in br_i15_moddiv()
422 			pb -= qb & -(int32_t)cAB;  in br_i15_moddiv()
423 			b_lo -= a_lo & -cBA;  in br_i15_moddiv()
424 			b_hi -= a_hi & -cBA;  in br_i15_moddiv()
425 			qa -= pa & -(int32_t)cBA;  in br_i15_moddiv()
426 			qb -= pb & -(int32_t)cBA;  in br_i15_moddiv()
431 			a_lo += a_lo & (cA - 1);  in br_i15_moddiv()
432 			pa += pa & ((int32_t)cA - 1);  in br_i15_moddiv()
433 			pb += pb & ((int32_t)cA - 1);  in br_i15_moddiv()
434 			a_hi ^= (a_hi ^ (a_hi >> 1)) & -cA;  in br_i15_moddiv()
435 			b_lo += b_lo & -cA;  in br_i15_moddiv()
436 			qa += qa & -(int32_t)cA;  in br_i15_moddiv()
437 			qb += qb & -(int32_t)cA;  in br_i15_moddiv()
438 			b_hi ^= (b_hi ^ (b_hi >> 1)) & (cA - 1);  in br_i15_moddiv()
444 		r = co_reduce(a, b, len, pa, pb, qa, qb);  in br_i15_moddiv()
445 		pa -= pa * ((r & 1) << 1);  in br_i15_moddiv()
446 		pb -= pb * ((r & 1) << 1);  in br_i15_moddiv()
447 		qa -= qa * (r & 2);  in br_i15_moddiv()
448 		qb -= qb * (r & 2);  in br_i15_moddiv()
449 		co_reduce_mod(u, v, len, pa, pb, qa, qb, m + 1, m0i);  in br_i15_moddiv()
460 	for (k = 1; k < len; k ++) {  in br_i15_moddiv()