71  * __qdivrem(u, v, rem) returns u/v and, optionally, sets *rem to u%v.
75  * divisor are 4 `digits' in this base (they are shorter if they have
82 	digit *u, *v, *q;  in __qdivrem()  local
89 	 * Take care of special cases: divide by zero, and u < v.  in __qdivrem()
106 	v = &vspace[0];  in __qdivrem()
114 	 *	v = (v[1]v[2]...v[n]) sub B  in __qdivrem()
115 	 *	v[1] != 0  in __qdivrem()
116 	 *	1 < n <= 4 (if n = 1, we use a different division algorithm)  in __qdivrem()
117 	 *	m >= 0 (otherwise u < v, which we already checked)  in __qdivrem()
118 	 *	m + n = 4  in __qdivrem()
120 	 *	m = 4 - n <= 2  in __qdivrem()
127 	u[4] = LHALF(tmp.ul[L]);  in __qdivrem()
129 	v[1] = HHALF(tmp.ul[H]);  in __qdivrem()
130 	v[2] = LHALF(tmp.ul[H]);  in __qdivrem()
131 	v[3] = HHALF(tmp.ul[L]);  in __qdivrem()
132 	v[4] = LHALF(tmp.ul[L]);  in __qdivrem()
133 	for (n = 4; v[1] == 0; v++) {  in __qdivrem()
141 			 *	for j = 1..4:  in __qdivrem()
142 			 *		q[j] = floor((r*B + u[j]) / v),  in __qdivrem()
143 			 *		r = (r*B + u[j]) % v;  in __qdivrem()
146 			t = v[2];	/* nonzero, by definition */  in __qdivrem()
152 			rbj = COMBINE(rbj % t, u[4]);  in __qdivrem()
167 	for (m = 4 - n; u[1] == 0; u++)  in __qdivrem()
169 	for (i = 4 - m; --i >= 0;)  in __qdivrem()
171 	q += 4 - m;  in __qdivrem()
177 	 * D1: choose multiplier 1 << d to ensure v[1] >= B/2.  in __qdivrem()
180 	for (t = v[1]; t < B / 2; t <<= 1)  in __qdivrem()
184 		shl(&v[1], n - 1, d);		/* v <<= d */  in __qdivrem()
190 	v1 = v[1];	/* for D3 -- note that v[1..n] are constant */  in __qdivrem()
191 	v2 = v[2];	/* for D3 */  in __qdivrem()
197 		 * Let qhat = min((u[j]*B + u[j+1])/v[1], B-1), and  in __qdivrem()
198 		 * let rhat = (u[j]*B + u[j+1]) mod v[1].  in __qdivrem()
199 		 * While rhat < B and v[2]*qhat > rhat*B+u[j+2],  in __qdivrem()
201 		 * Note that if rhat >= B, v[2]*qhat < rhat*B.  in __qdivrem()
224 		 * We split this up so that we do not require v[0] = 0,  in __qdivrem()
228 			t = u[i + j] - v[i] * qhat - t;  in __qdivrem()
238 		 * Fix it by adding v[1..n] to u[j..j+n].  in __qdivrem()
243 				t += u[i + j] + v[i];  in __qdivrem()
265 		tmp.ul[L] = COMBINE(uspace[3], uspace[4]);  in __qdivrem()
270 	tmp.ul[L] = COMBINE(qspace[3], qspace[4]);  in __qdivrem()