`hex.add_count_bits`¶

(n=2 when operating on 16-255 bit-numbers)
dst[:n] += src.#on-bits (between 0->4)
dst is hex.vec n, src is hex.
@Assumes: dst and src do not alias.

@Assumes: dst and src do not alias

Signature¶

def add_count_bits n, dst, src @ count_switch, do_add, add_switch, add4_switch, xor_switch, after_add, is_carry, should_inc, do_inc, clean { ... }

Defined in hex/math_basic.fj — lines 11–75 (view on GitHub).

Complexity¶

Time: 2.27@-1 // (2@-10 + 2 + 4 + 3 + 0.25*[16@/15])
Space: 0.5@+109 + n(1.5@+13) // (2@-10 + 16(1+4+1+2) + 4 + (n-1)(1.5@+13))

See the complexity glossary for what @, w, dw, dbit, n mean.

Source¶

Click to view the macro body

def add_count_bits n, dst, src @ count_switch,  do_add,  add_switch, add4_switch,  xor_switch,  \
        after_add, is_carry,  should_inc, do_inc,  clean {
    //part1
    wflip src+w, count_switch, src

    pad 16
    //part2
  count_switch:
    ;clean              //  0
    ;do_add
    ;do_add
    dst+dbit+4;do_add
    ;do_add             //  4
    dst+dbit+4;do_add
    dst+dbit+4;do_add
    dst+dbit+5;do_add
    ;do_add             //  8
    dst+dbit+4;do_add
    dst+dbit+4;do_add
    dst+dbit+5;do_add
    dst+dbit+4;do_add   // 12
    dst+dbit+5;do_add
    dst+dbit+5;do_add
    dst+dbit+5;count_switch+3*dw

    //part3
  do_add:
    wflip dst+w, add_switch, dst

    pad 64
    //part4
  add_switch:
    rep(16, d) stl.fj             0,    xor_switch+(d^(d+1))*dw
    rep(16, d) stl.fj    dst+dbit+4,    xor_switch+(d^(d+2))*dw
    rep(16, d) stl.fj    dst+dbit+5,    xor_switch+(d^(d+3))*dw
    rep(16, d) stl.fj    dst+dbit+5,    add4_switch+d*dw
  add4_switch:
    rep(16, d) stl.fj    dst+dbit+4,    xor_switch+(d^(d+4))*dw

    pad 32
    //part5
  xor_switch:
    .tables.clean_table_entry__table 16, dst, after_add
    rep(16, i) stl.fj    is_carry+dbit,    xor_switch+i*dw

  after_add:
    //part6
    wflip dst+w, add_switch, is_carry
  is_carry:
    //part7
    ;should_inc
    pad 2
  should_inc:
    //part8
    ;clean
    is_carry+dbit;do_inc
  do_inc:
    //part9 (optional)
    .inc n-1, dst+dw
    ;clean

  clean:
    //part10
    wflip src+w, count_switch
}

Depends on¶

Next: hex.count_bits →