bitlib.fj

// Every line is (a bit) bananas!
// Implementation of binary-variables operations, and vectors of it

// should be assembled with the runlib.fj file
// This file is independent of the bit-width, and uses the consts defined at runlib.fj

// Everything after // is ignored, and every whitespace is ignored (besides new line)
// An opcode is:  F;J  F;  ;J  or just  ;  (no F => F=0;  no J => J=next)

// Complexity note: phi is log2 of the total number of fj operations, counting wflips as one op.
// so 2 wflips with value=label (while label is padded with 2^n) causes phi-n space/time complexity

// The complexities are not updated in this file (should be lower/faster).



// ---------- Memory Variables:
// Size Complexity: 1


def bit value {
    ; value ? dw : 0
}

def bit {
    bit 0
}


// Size Complexity: n
ns bit {
    def vec n, value {
        rep(n, i) bit (value>>i)&1
    }

    def vec n {
        rep(n, i) bit
    }
}


// ---------- Memory Manipulation:


ns bit {
    // Complexity: phi+2
    def zero x {
        .xor x, x
    }

    // Complexity: n(phi+2)
    def zero n, x {
        rep(n, i) .zero x+i*dw
    }


    // Complexity: phi+3
    def one x {
        .zero x
        .not x
    }

    // Complexity: n(phi+3)
    def one n, x {
        rep(n, i) .one x+i*dw
    }


    ////Complexity: 2phi + 9
    //__if_mov dst src @ l0 l1 flip end {
    //    .if src l0 l1
    //    l0: .if dst end flip
    //    l1: .if dst flip end
    //    flip:   .not dst
    //    end:
    //}


    // safe even for dst==src !
    // Complexity: 2phi+5
    def mov dst, src @ do_mov, end {
        comp_if1 dst==src, end
      do_mov:
        .zero dst
        .xor dst, src
      end:
    }

    // Complexity: n(2phi+5)
    def mov n, dst, src {
        rep(n, i) .mov dst+i*dw, src+i*dw
    }


    //Complexity: 2phi+10
    def swap a, b @ a0, a1, notnot, end {
        .if a, a0, a1
      a0:
        .if b, end, notnot
      a1:
        .if b, notnot, end
      notnot:
        .not a
        .not b
      end:
    }

    // Complexity: n(2phi+10)
    def swap n, a, b {
        rep(n, i) .swap a+i*dw, b+i*dw
    }
}



// ---------- Conditional Jump


ns bit {
    // Complexity: phi+4
    def if x, l0, l1 @ label_ptr, base_jump_label {
        .xor label_ptr, x
      label_ptr:
        ;base_jump_label
        pad 2
      base_jump_label:
        ;l0
        label_ptr + dbit;l1
    }

    // Complexity: n(phi+4)
    def if n, x, l0, l1 {
        rep(n-1, i) ._.if_next_l0 x+i*dw, l1
        .if x+(n-1)*dw, l0, l1
    }
    ns _ {
        def if_next_l0 x, l1 @ l0 {
            ..if x, l0, l1
          l0:
        }
    }

    def if1 x, l1 @ end {
        .if x, end, l1
      end:
    }

    def if1 n, x, l1 @ end {
        .if n, x, end, l1
      end:
    }

    def if0 x, l0 @ end {
        .if x, l0, end
      end:
    }

    def if0 n, x, l0 @ end {
        .if n, x, l0, end
      end:
    }


    // Complexity: 2phi+8
    def cmp a, b, lt, eq, gt @ a_is1_label {
        .if1 a, a_is1_label
        .if b, eq, lt
      a_is1_label:
        .if b, gt, eq
    }

    // Complexity: n(2phi+8)
    def cmp n, a, b, lt, eq, gt {
        rep(n-1, i) ._.cmp_next_eq a+(n-1-i)*dw, b+(n-1-i)*dw, lt, gt
        .cmp a, b, lt, eq, gt
    }
    ns _ {
        def cmp_next_eq a, b, lt, gt @ eq {
            ..cmp a, b, lt, eq, gt
          eq:
        }
    }
}



// ---------- Logical Macros:


ns bit {
    // Complexity: phi+2
    def xor dst, src {
        .exact_xor dst + dbit, src
    }

    // Complexity: n(phi+2)
    def xor n, dst, src {
        rep(n, i) .xor dst+dw*i, src+dw*i
    }

    def exact_xor dst, src @ base_jump_label, cleanup {
        wflip src+w, base_jump_label, src
        pad 2
      base_jump_label:
        ;cleanup
        dst;
      cleanup:
        wflip src+w, base_jump_label
    }

    // Complexity: phi+3
    def double_exact_xor dst1, dst2, src @ base_jump_label, cleanup {
        wflip src+w, base_jump_label, src
        pad 2
      base_jump_label:
        ;cleanup
        dst1;
        dst2;
      cleanup:
        wflip src+w, base_jump_label
    }

    // Complexity: n(phi+3)
    def bit_var_xor n, bit, var, src {
        rep(n, i) .double_exact_xor bit+i, var+dbit+i*dw, src+i*dw
    }

    def xor_zero dst, src {
        .double_exact_xor dst+dbit, src+dbit, src
    }

    // Complexity: n(phi+3)
    def xor_zero n, dst, src {
        rep(n, i) .xor_zero dst+dw*i, src+dw*i
    }


    // Complexity: 2phi+7
    def or dst, src @ end {
        .if0 src, end
        .one dst
      end:
    }

    // Complexity: n(2phi+7)
    def or n, dst, src {
        rep(n, i) .or dst+dw*i, src+dw*i
    }


    // Complexity: 2phi+6
    def and dst, src @ end {
        .if1 src, end
        .zero dst
      end:
    }

    // Complexity: n(2phi+6)
    def and n, dst, src {
        rep(n, i) .and dst+dw*i, src+dw*i
    }


    // Complexity: 1
    def not dst {
        dst + dbit;
    }

    // Complexity: n
    def not n, dst {
        rep(n, i) .not dst+dw*i
    }

    def exact_not dst {
        dst;
    }
}



// ---------- Logical Shifts


ns bit {
    // Complexity: n(2phi+5)
    def shr n, x {
        .shr n, 1, x
    }

    // Complexity: n(2phi+5)
    def shr n, times, x {
        rep(n-times, i) .mov x+i*dw, x+(i+times)*dw
        .zero times, x+(n-times)*dw
    }


    // Complexity: n(2phi+5)
    def shl n, x {
        .shl n, 1, x
    }

    // Complexity: n(2phi+5)
    def shl n, times, x {
        rep(n-times, i) .mov x+(n-1-i)*dw, x+(n-1-i-times)*dw
        .zero times, x
    }


    // Complexity: n(2phi+5)
    def ror n, x @ temp_bit {
        .mov temp_bit, x
        rep(n-1, i) .mov x+i*dw, x+(i+1)*dw
        .mov x+(n-1)*dw, temp_bit
        skip
      temp_bit:
        bit
    }


    // Complexity: n(2phi+5)
    def rol n, x @ temp_bit {
        .mov temp_bit, x+(n-1)*dw
        rep(n-1, i) .mov x+(n-1-i)*dw, x+(n-1-i-1)*dw
        .mov x, temp_bit
        skip
      temp_bit:
        bit
    }
}



// ---------- Arithmetical Macros
// carry is both input and output


ns bit {
    // Unsafe for dst==carry (but there is no reason in calling it that way)
    // Complexity: 2phi+10
    def inc1 dst, carry @ end {
        .if0 carry, end
        .not dst
        .if0 dst, end
        .not carry
      end:
    }

    // Complexity: n(2phi+10)
    def inc n, x @ carry {
        .one carry
        rep(n, i) .inc1 x+i*dw, carry
        skip
      carry:
        bit
    }

    // Complexity: n(2phi+12)
    def dec n, x {
        .not n, x
        .inc n, x
        .not n, x
    }

    // Complexity: n(2phi+11)
    def neg n, x {
        .not n, x
        .inc n, x
    }


    // Unsafe for dst==carry (but there is no reason in calling it that way)
    // Complexity: 8phi+33
    def add1 dst, src, carry @ _src {
        .mov _src, src
        .inc1 dst, _src
        .inc1 dst, carry
        .or carry, _src
        skip
      _src:
        bit
    }

    // Complexity: n(8phi+33)
    def add n, dst, src @ carry {
        .zero carry
        rep(n, i) .add1 dst+i*dw, src+i*dw, carry
        skip
      carry:
        bit
    }

    // Complexity: n(8phi+35)
    def sub n, dst, src @ carry {
        .not n, src
        .one carry
        rep(n, i) .add1 dst+i*dw, src+i*dw, carry
        .not n, src
        skip
      carry:
        bit
    }
}