1 /* ISC license. */
2
3 #include <skalibs/biguint.h>
4
5 /*
6 q = a/b, a = a mod b. Assumes b != 0 and qn >= alen - blen + 1.
7 */
8
bu_div_internal(uint32_t * a,unsigned int an,uint32_t const * b,unsigned int bn,uint32_t * q,unsigned int qn)9 void bu_div_internal (uint32_t *a, unsigned int an, uint32_t const *b, unsigned int bn, uint32_t *q, unsigned int qn)
10 {
11 unsigned int alen = bu_len(a, an) ;
12 unsigned int blen = bu_len(b, bn) ;
13 bu_zero(q, qn) ;
14 if (alen < blen) return ;
15 {
16 uint32_t bb[alen + 1] ;
17 unsigned int i = 1 + ((alen - blen) << 5) ;
18 bu_zero(bb, alen - blen) ;
19 bu_copy_internal(bb + alen - blen, b, blen) ;
20 bb[alen] = 0 ;
21
22 while (bu_cmp(a, alen, bb, alen+1) >= 0)
23 {
24 bu_slb(bb + alen - blen, blen + 1) ;
25 i++ ;
26 }
27 while (i && (bu_cmp(a, alen, bb, alen+1) < 0))
28 {
29 bu_srb(bb, alen + 1) ;
30 i-- ;
31 }
32
33 while (i--)
34 {
35 bu_slb(q, alen - blen + 1) ;
36 if (bu_cmp(a, alen, bb, alen) >= 0)
37 {
38 bu_sub(a, alen, a, alen, bb, alen) ;
39 q[0] |= 1 ;
40 }
41 bu_srb(bb, alen) ;
42 }
43 }
44 }
45