math.fj

// ---------- 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: 2@+6
    //   {carry:dst}++
    // carry,dst are bits.
    def inc1 dst, carry @ continue {
        .inc.inc1_with_carry0_jump dst, carry, continue
      continue:
    }

    ns inc {
        // Unsafe for dst==carry (but there is no reason in calling it that way)
        // If carry was 0, jump to carry0_jump.
        // Complexity: 2@+6
        //   {carry:dst}++
        // carry,dst are bits.
        def inc1_with_carry0_jump dst, carry, carry0_jump @ end {
            ..if0 carry, carry0_jump
            ..not dst
            ..if0 dst, end
            ..not carry
          end:
        }
    }

    //  Time Complexity: 5@+12 in average
    // Space Complexity: n(2@+6)
    //   x[:n]++
    // x is a bit[:n]
    def inc n, x @ carry, end {
        .one carry
        rep(n, i) .inc.inc1_with_carry0_jump x+i*dw, carry, end
        ;end
      carry:
        .bit
      end:
    }

    //  Time Complexity: 2n + 5@+12
    // Space Complexity: n(2@+6)
    //   x[:n]--
    // x is a bit[:n]
    def dec n, x {
        .not n, x
        .inc n, x
        .not n, x
    }

    //  Time Complexity: n + 5@+12
    // Space Complexity: n(2@+6)
    //   x[:n]--
    // x is a bit[:n]
    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: 8@+14
    //   {carry:dst} += src
    // dst,src,carry are bits.
    def add1 dst, src, carry @ _src {
        .mov _src, src
        .inc1 dst, _src
        .inc1 dst, carry
        .or carry, _src
        stl.skip
      _src:
        .bit
    }

    // Complexity: n(8@+14)
    //   dst[:n] += src[:n]
    // dst,src are bit[:n]
    def add n, dst, src @ carry {
        .zero carry
        rep(n, i) .add1 dst+i*dw, src+i*dw, carry
        stl.skip
      carry:
        .bit
    }

    // Complexity: n(8@+16)
    //   dst[:n] -= src[:n]
    // dst,src are bit[:n]
    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
        stl.skip
      carry:
        .bit
    }
}