// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/12/Math.jack

/**
 * A library of commonly used mathematical functions.
 * Note: Jack compilers implement multiplication and division using OS method calls.
 */
class Math {

    /** Initializes the library. */
    function void init() {
        return;
    }

    /** Returns the absolute value of x. */
    function int abs(int x) {
        if (x < 0) {
            return -x;
        }
        
        return x;
    }

    /** Returns the product of x and y. 
     *  When a Jack compiler detects the multiplication operator '*' in the 
     *  program's code, it handles it by invoking this method. In other words,
     *  the Jack expressions x*y and multiply(x,y) return the same value.
     */
    function int multiply(int x, int y) {
        var int sum, shiftedX, tim, tmp1, tmp2, org_x, org_y;
        let org_x = x;
        let org_y = y;
        let x = Math.abs(x);
        let y = Math.abs(y);
        let sum = 0;
        let shiftedX = x;
        let tim = 1;
        let tmp1 = y + 1;
        while((tim < tmp1) & (0 < tim)) {
           let tmp2 = y & tim;
           if(~(tmp2 = 0)) {
               let sum = sum + shiftedX;
           }
           //左シフトでも良いがシフト演算できたのかわからないので足した(*2としてもmultiply(x, 2)となるのでほぼ同じ)
           let tim = tim + tim;
           let shiftedX = shiftedX + shiftedX;
        }
        
        if(org_x < 0) {
            let sum = -sum;
        }
        if(org_y < 0) {
            let sum = -sum;
        }
        
        return sum;
    }

    /** Returns the integer part of x/y.
     *  When a Jack compiler detects the multiplication operator '/' in the 
     *  program's code, it handles it by invoking this method. In other words,
     *  the Jack expressions x/y and divide(x,y) return the same value.
     */
    function int divide(int x, int y) {
        var int q, sum, tmp, org_x, org_y;
        
        let org_x = x;
        let org_y = y;
        let x = Math.abs(x);
        let y = Math.abs(y);
        
        //x/yの整数部分を返す. xとyは0より大きいことが前提
        if(y > x) {
            return 0;
        }
        
        //y >= 16384のときyを2倍すると16ビットint(補数あり)の範囲を超えるため、場合分けが必要
        if(y < 16384) {
            let q = Math.divide(x, y + y);
            let sum = Math.divide_sum(x, y + y);
            //let tmp = x - (q * y * 2);
            let tmp = x - sum;
            if(tmp < y) {
                // x / (2 * q * y) が 1より小さいとき
                let tmp = q + q;
            } else {
                // x / (2 * q * y) が 1より大きい(かつ2よりは小さい)とき
                let tmp = q + q + 1;
            }
        } else {
            if(x < y) {
                let tmp = 0;
            } else {
                let tmp = 1;
            }
        }
        
        if(org_x < 0) {
            let tmp = -tmp;
        }
        if(org_y < 0) {
            let tmp = -tmp;
        }
        
        return tmp;
    }

    function int divide_sum(int x, int y) {
        var int sum, tmp;
        //x/yの整数部分を返す. xとyは0より大きいことが前提
        if(y > x) {
            return 0;
        }
        
        //y >= 16384のときyを2倍すると16ビットint(補数あり)の範囲を超えるため、場合分けが必要
        if(y < 16384) {
            let sum = Math.divide_sum(x, y + y);
            let tmp = x - sum;
            if(tmp < y) {
                // x / (2 * q * y) が 1より小さいとき
                return sum;
            } else {
                // x / (2 * q * y) が 1より大きい(かつ2よりは小さい)とき
                return sum + y;
            }
        } else {
            if(x < y) {
                return 0;
            } else {
                return y;
            }
        }
    }

    /** Returns the integer part of the square root of x. */
    function int sqrt(int x) {
        var int btim, y, tmp1, tmp2;
        let btim = 181;
        
        let y = 0;
        while(btim > 0) {
            let tmp2 = y + btim - 1;
            //tmp2が181より大きい数だと(y + btim) * (y + btim)がオーバーフローするため
            if(tmp2 < 181) {
                let tmp1 = (y + btim) * (y + btim) - 1;
                // - 1はxが32767のときのため(if(tmp1 <= x) ができないため)
                if(tmp1 < x) {
                    let y = y + btim;
                }
            }
            let btim = btim / 2;
        }
        
        return y;
    }

    /** Returns the greater number. */
    function int max(int a, int b) {
        if (a < b) {
            return b;
        }
        
        return a;
    }

    /** Returns the smaller number. */
    function int min(int a, int b) {
        if (a < b) {
            return a;
        }
        
        return b;
    }
}