div.fj

ns hex {
    //  Time Complexity: n^2(2@+8) + n*nb(34@+92)   so if nb==n:  n^2(36@+100)
    // Space Complexity: n(4@+81)  + nb(16@+243)    so if nb==n:  n(20@+324)
    //   if b==0: goto div0
    //   q = a/b  (unsigned division)
    //   r = a%b  (unsigned modulo)
    // @NOTE: a,b are UNSIGNED numbers. If you want a division with signed ints, use the idiv macro.
    //
    // q,a are hex[:n], while r,b are hex[:nb]. div0 is the bit-address this function will jump to in-case b is zero.
    // @requires hex.sub.init & hex.cmp.init (or hex.init)
    def div n, nb, q, r, a, b, div0 @ loop, after_loop,\
            half_b__sub_if_bigger, do_sub, jump_to_flip, flip_op,   \
            _r, _b, _a, i, ret,   end {
        .if0 nb, b, div0

        // init all inner variables
        .zero nb+1, _r
        .mov nb, _b, b
        .mov n, _a, a

        // loop n times
        .set #n, i, n-1
      loop:
        // {_r:_a} <<= 4
        .shl_hex n+nb+1, _a

        // q <<= 4.  (now q's 4 ls-bits are cleared, to be filled later with _r/_b).
        .shl_hex n, q

        // This next section makes:  q += _r/_b  &&  _r %= _b.
        .shl_hex nb+1, _b     // b*=16
        stl.fcall half_b__sub_if_bigger, ret
        jump_to_flip+dbit+0;  // set do_sub to point to q+1
        stl.fcall half_b__sub_if_bigger, ret
        jump_to_flip+dbit+1;  // set do_sub to point to q+3
        stl.fcall half_b__sub_if_bigger, ret
        jump_to_flip+dbit+0;  // set do_sub to point to q+2
        stl.fcall half_b__sub_if_bigger, ret
        jump_to_flip+dbit+1;  // set do_sub to point to q

        .dec #n, i
        .sign #n, i, after_loop, loop

        // _b<<=1;  if _r>=_b: goto do_sub.
      half_b__sub_if_bigger:
        hex.shr_bit nb+1, _b
        hex.cmp nb+1, _r, _b, ret, do_sub, do_sub

      do_sub:
        hex.sub nb+1, _r, _b
        // In this part q gets another "1" bit, depends on where "jump_to_flip" points to:
      jump_to_flip:
        ;flip_op
        pad 4
      flip_op:
        q+dbit+3; ret
        q+dbit+2; ret
        q+dbit+0; ret
        q+dbit+1; ret

      _b:  .vec nb+1
      _a:  .vec n
      _r:  .vec nb+1
      i:  .vec #n
      ret: ;0

      after_loop:
        .mov nb, r, _r
      end:
    }

    //  Time Complexity: n^2(2@+8) + n*nb(34@+92)   so if nb==n:  n^2(36@+100)
    // Space Complexity: n(8.5@+132)  + nb(21.5@+309)    so if nb==n:  n(30@+441)
    //   if b==0: goto div0
    //   q = a/b  (signed division)
    //   r = a%b  (signed modulo - signed according to rem_opt:)
    //     if rem_opt is 0: sign(r)==sign(b)  // Most programming languages implement this option.
    //     if rem_opt is 1: sign(r)==sign(a)
    //     if rem_opt is 2: sign(r) is always positive
    //       (On any other rem_opt value, will jump to "div0". This check is guaranteed to be after the b==0 check).
    //     Anyway, a == q*b + r.
    // @NOTE: a,b are SIGNED numbers. If you want a division with unsigned ints, use the div macro.
    //
    // q,a are hex[:n], while r,b are hex[:nb]. div0 is the bit-address this function will jump to in-case b is zero.
    // @requires hex.sub.init & hex.cmp.init (or hex.init)
    def idiv n, nb, q, r, a, b, div0, rem_opt\
            @ set_negative_a, test_b, set_negative_b, update_rem_opt_0, update_rem_opt_2, add_b, sub_b,\
            negative_a, negative_b, one_negative, do_div, neg_b_2, neg_ans, end, fix_rem {
        .if0 nb, b, div0
        stl.comp_if1 ((rem_opt < 0) | (rem_opt > 2)), div0

        bit.zero negative_a
        bit.zero negative_b
        bit.zero one_negative

        .sign n, a, set_negative_a, test_b
      set_negative_a:
        bit.not negative_a
        bit.not one_negative
        .neg n, a
      test_b:
        .sign nb, b, set_negative_b, do_div
      set_negative_b:
        bit.not negative_b
        bit.not one_negative
        .neg nb, b

      do_div:
        .div n, nb, q, r, a, b, div0

        bit.if0 negative_a, neg_b_2
        .neg n, a
        .neg nb, r
      neg_b_2:
        bit.if0 negative_b, neg_ans
        .neg nb, b
      neg_ans:
        bit.if0 one_negative, fix_rem
        .neg n, q

      fix_rem:
        stl.comp_if1 rem_opt == 0, update_rem_opt_0
        stl.comp_if1 rem_opt == 2, update_rem_opt_2
        ;end

      update_rem_opt_0:
        bit.if one_negative, end, add_b

      update_rem_opt_2:
        bit.if0 negative_a, end
        bit.if negative_b, add_b, sub_b

      add_b:
        hex.add nb, r, b
        hex.dec n, q
        ;end

      sub_b:
        hex.sub nb, r, b
        hex.inc n, q
        ;end

      negative_a:
        bit.bit
      negative_b:
        bit.bit
      one_negative:
        bit.bit
      end:
    }
}