hex.mul.init

This is where the add_mul “truth” tables are.
dst[1] is zeroed after finishing this multiplication.

Signature

def init @ add_res, after_add, end, switch_small_table, add_carry_small_table, set_carry_small_table, clean_small_table, switch, set_carry_0, set_carry_1, clean, add_carry, clean_add, clean_carry < ..add.dst, ..tables.ret > ret, dst, add_carry_dst { ... }

Defined in hex/mul.fj — lines 108–182 (view on GitHub).

Complexity

  • Time: @+24 (when jumping to dst, until finished)

  • Space: 1620+@

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

Requires init

The following must be initialised before this macro is invoked:

  • hex.tables.init_shared & hex.add.init (or hex.init)

Output labels

This macro exposes labels into the caller’s scope via >:

  • ret — The return address. Jumps to it after finishing the add_mul flow.

  • dst — hex[:2] variable. The code calculates dst[0]*dst[1] + add_carry_dst.

  • add_carry_dst — hex variable. It’s value is added to dst[0]*dst[1], and the carry is written back to it.

Source

Click to view the macro body

def init @ add_res, after_add, end,   switch_small_table, add_carry_small_table, set_carry_small_table, \
        clean_small_table,   switch, set_carry_0, set_carry_1, clean,   add_carry, clean_add, clean_carry \
        < ..add.dst, ..tables.ret > ret, dst, add_carry_dst {
    // general progression (after jumping to hex.mul.dst with value d):
    //  1. dst           -> switch+d          (set lower4  mul result in add_carry_dst+4)                                                                     (runtime=5)
    //  2. add_carry_dst -> add_carry+?       (set         add result in hex.add.dst  +4. sets dst to set_carry_{0/1}. sets add_carry_dst to clean_add)       (runtime=6)
    //  3. add_carry_dst -> clean_add+?       (clears the all 8 bits of add_carry_dst.    sets add_carry_dst back to add_carry)                               (runtime=9)
    //  4. dst           -> set_carry_{0/1}+d (set higher4 mul result in add_carry_dst+0. sets dst to clean)                                                  (runtime=5)
    //  5. add_res       -> dst-table+??      (set         add result in hex.tables.res    +0)                                                                (runtime=@-8)
    //  6. dst           -> clean+d           (clears the higher4 bits of dst.            sets dst back to switch)                                            (runtime=6)
    //  7. hex.mul.ret   -> ...                                                                                                                               (runtime=1)


    ;end

  ret: ;0
  dst: ;switch

  add_carry_dst: ;add_carry   // the 4-bit carry is in the lower 4bits in here


  add_res:
    wflip ..tables.ret+w, after_add, ..add.dst
    pad 256
  after_add:
    wflip ..tables.ret+w, after_add, .dst


    pad 16  // not really needed
  switch_small_table:
    rep(16, d) stl.fj \
        (d==0)              ? 0              :  (.add_carry_dst + dbit + (#d) + 3), \
        (d==((1<<(#d))>>1)) ? .add_carry_dst :  switch_small_table + (d^((1<<(#d)) >> 1))*dw
  set_carry_small_table:
    rep(16, d) stl.fj \
        (d==0)              ? 0       :  (.add_carry_dst+dbit+(#d)-1), \
        (d==((1<<(#d))>>1)) ? add_res :  set_carry_small_table + (d^((1<<(#d)) >> 1))*dw
  add_carry_small_table:
    rep(16, d) stl.fj \
        (d==0) ? .add_carry_dst+dbit+8 :  (..add.dst+dbit+(#d)+3), \
        (d==0) ? .add_carry_dst        : add_carry_small_table+(d^((1<<(#d))>>1))*dw
  clean_small_table:
    rep(16, d) stl.fj \
        (d==0) ? .dst+dbit+9 :  (.dst+dbit+(#d)+3), \
        (d==0) ? .ret        :  clean_small_table + (d^((1<<(#d)) >> 1))*dw


    pad 1024
  switch:
    rep(256, d) stl.fj              0,    switch_small_table    + (((d&0xf)*(d>>4)) & 0xf) * dw
  set_carry_0:
    rep(256, d) stl.fj    .dst+dbit+9,    set_carry_small_table +  (((d&0xf)*(d>>4)) >> 4) * dw
  set_carry_1:
    rep(256, d) stl.fj    .dst+dbit+8,    set_carry_small_table + ((((d&0xf)*(d>>4)) >> 4)+1) * dw
  clean:
    rep(256, d) stl.fj    .dst+dbit+8,    clean_small_table     +    (d>>4) * dw


    pad 1024  // needs to be 1024-padded
  add_carry:
    rep(256, d) stl.fj \
        .dst+dbit + (((d&0xf)+(d>>4) > 0xf) ? 9 : 8), \
        add_carry_small_table + (((d&0xf)+(d>>4)) & 0xf) * dw
  clean_add:
    rep(256, d) stl.fj \
        (d==0) ? .add_carry_dst+dbit+8 : (.add_carry_dst+dbit+(#d)-1), \
        (d==0) ? .dst                  : clean_add  +(d^((1<<(#d))>>1))*dw
  clean_carry:
    rep( 16, d) stl.fj \
        (d==0) ? .add_carry_dst+dbit+9 : (.add_carry_dst+dbit+(#d)-1), \
        (d==0) ? .dst                  : clean_carry+(d^((1<<(#d))>>1))*dw


  end:
}

Used by

Example uses

← Previous: hex.mul.clear_carry