18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
34 	 *   d <- (d + xu*y + f*m) / 2^31  in br_i31_montymul()
35 	 * We have xu <= 2^31-1 and f <= 2^31-1.  in br_i31_montymul()
36 	 * Thus, if d <= 2*m-1 on input, then:  in br_i31_montymul()
37 	 *   2*m-1 + 2*(2^31-1)*m <= (2^32)*m-1  in br_i31_montymul()
40 	 * We represent d over 31-bit words, with an extra word 'dh'  in br_i31_montymul()
53 		 *   d[v+1] <= 2^31-1  in br_i31_montymul()
54 		 *   xu*y[v+1] <= (2^31-1)*(2^31-1)  in br_i31_montymul()
55 		 *   f*m[v+1] <= (2^31-1)*(2^31-1)  in br_i31_montymul()
56 		 *   r <= 2^32-1  in br_i31_montymul()
57 		 *   (2^31-1) + 2*(2^31-1)*(2^31-1) + (2^32-1) = 2^63 - 2^31  in br_i31_montymul()
58 		 * After division by 2^31, the new r is then at most 2^32-1  in br_i31_montymul()
60 		 * Using a 32-bit carry has performance benefits on 32-bit  in br_i31_montymul()
61 		 * systems; however, on 64-bit architectures, we prefer to  in br_i31_montymul()
62 		 * keep the carry (r) in a 64-bit register, thus avoiding some  in br_i31_montymul()
63 		 * "clear high bits" operations.  in br_i31_montymul()
77 			uint64_t z;  in br_i31_montymul()  local
79 			z = (uint64_t)d[v + 1] + MUL31(xu, y[v + 1])  in br_i31_montymul()
81 			r = z >> 31;  in br_i31_montymul()
82 			d[v + 0] = (uint32_t)z & 0x7FFFFFFF;  in br_i31_montymul()
83 			z = (uint64_t)d[v + 2] + MUL31(xu, y[v + 2])  in br_i31_montymul()
85 			r = z >> 31;  in br_i31_montymul()
86 			d[v + 1] = (uint32_t)z & 0x7FFFFFFF;  in br_i31_montymul()
87 			z = (uint64_t)d[v + 3] + MUL31(xu, y[v + 3])  in br_i31_montymul()
89 			r = z >> 31;  in br_i31_montymul()
90 			d[v + 2] = (uint32_t)z & 0x7FFFFFFF;  in br_i31_montymul()
91 			z = (uint64_t)d[v + 4] + MUL31(xu, y[v + 4])  in br_i31_montymul()
93 			r = z >> 31;  in br_i31_montymul()
94 			d[v + 3] = (uint32_t)z & 0x7FFFFFFF;  in br_i31_montymul()
97 			uint64_t z;  in br_i31_montymul()  local
99 			z = (uint64_t)d[v + 1] + MUL31(xu, y[v + 1])  in br_i31_montymul()
101 			r = z >> 31;  in br_i31_montymul()
102 			d[v] = (uint32_t)z & 0x7FFFFFFF;  in br_i31_montymul()
124 	 * 'dh' word may be non-zero.  in br_i31_montymul()