summaryrefslogtreecommitdiff
path: root/src/libbiguint/bu_div_internal.c
blob: d1be78951335969ebcf7b0c104fc9a72d096a62d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* ISC license. */

#include <errno.h>
#include <skalibs/uint32.h>
#include <skalibs/biguint.h>

/*
   q = a/b, a = a mod b. Assumes b != 0 and qn >= alen - blen + 1.
*/

void bu_div_internal (uint32 *a, unsigned int an, uint32 const *b, unsigned int bn, uint32 *q, unsigned int qn)
{
  unsigned int alen = bu_len(a, an) ;
  unsigned int blen = bu_len(b, bn) ;
  bu_zero(q, qn) ;
  if (alen < blen) return ;
  {
    uint32 bb[alen + 1] ;
    unsigned int i = 1 + ((alen - blen) << 5) ;
    bu_zero(bb, alen - blen) ;
    bu_copy_internal(bb + alen - blen, b, blen) ;
    bb[alen] = 0 ;

    while (bu_cmp(a, alen, bb, alen+1) >= 0)
    {
      bu_slb(bb + alen - blen, blen + 1) ;
      i++ ;
    }
    while (i && (bu_cmp(a, alen, bb, alen+1) < 0))
    {
      bu_srb(bb, alen + 1) ;
      i-- ;
    }

    while (i--)
    {
      bu_slb(q, alen - blen + 1) ;
      if (bu_cmp(a, alen, bb, alen) >= 0)
      {
        bu_sub(a, alen, a, alen, bb, alen) ;
        q[0] |= 1 ;
      }
      bu_srb(bb, alen) ;
    }
  }
}