JS串行加法器

时间:2022-05-28 巨輪人气:0

在重温《编码：隐匿在计算机软硬件背后的语言》第12章——二进制加法器时，心血来潮用JS写了一个模拟串行加法器。

测试断言工具TestUtils.js

function assertTrue(actual){
    if(!actual)
        throw "Error actual: " + actual + " is not true."
}

function assertFalse(actual){
    if(actual)
        throw "Error actual: " + actual + " is not false."
}

function assertIntEquals(expected, actual){
    if(typeof expected != "number")
        throw "Error expected: " + expected +" is not a number."

    if(typeof actual != "number")
        throw "Error actual: " + actual +" is not a number."

    if(expected != actual)
        throw "Error expected: " + expected + " and actual: " + actual +" is different."
}

十进制数与二进制数之间转换工具utils.js

function int2LowEightBitArray(num){
    var result = []
    for(var i = 0; i < 8; i++)
        result.push(((num >> i) & 1) == 1)
    return result
}

function lowEightBitArray2Int(array){
    var result = 0
    for(var i = 0; i < 8; i++){
        if(array[i])
            result += (1 << i)
    }
    return result
}

function lowNineBitArray2Int(array){
    var result = 0
    for(var i = 0; i < 9; i++){
        if(array[i])
            result += (1 << i)
    }
    return result
}

//用补码表示负数
function int2EightBitArray(num){
    if(num < -128 || num > 127){
        throw "Out of boundary(-128, 127)."
    }
    var result = []
    for(var i = 0; i < 8; i++)
        result.push(((num >> i) & 1) == 1)
    return result
}

function eightBitArray2Int(array){
    var result = 0
    for(var i = 0; i < 7; i++){
        if(array[i])
            result += (1 << i)
    }
    if(array[i])
        result += -128
    return result
}

function int2SixteenBitArray(num){
    if(num < -(1 << 15) || num > (1 << 15) - 1){
        throw "Out of boundary({left}, {right})."
            .replace("{left}", -(1 << 15))
            .replace("{right}", (1 << 15) - 1)
    }
    var result = []
    for(var i = 0; i < 16; i++)
        result.push(((num >> i) & 1) == 1)
    return result
}

function sixteentBitArray2Int(array){
    var result = 0
    for(var i = 0; i < 15; i++){
        if(array[i])
            result += (1 << i)
    }
    if(array[i])
        result += -(1 << 15)
    return result
}

加法器模型model.js

class DoubleInGate{
    #id
    #in1
    #in2
    #gateTypeName
    #func
    #out
    #lastOut
    #outReceiver
    #outReceiverInName

    constructor(id, gateTypeName, in1 = false, in2 = false, func){
        this.#id = id
        this.#gateTypeName = gateTypeName
        this.#in1 = in1
        this.#in2 = in2
        this.#func = func
        this.#out = this.#func(this.in1, this.in2)
        // this.#lastOut = this.#out
    }
    
    updateIn1(flag){
        this.#in1 = flag
        this.#updateOut()
    }
    
    updateIn2(flag){
        this.#in2 = flag
        this.#updateOut()
    }
    
    getOut(){
        return this.#out;
    }

    updateBothIn(in1 = false, in2 = false){
        this.#in1 = in1
        this.#in2 = in2
        this.#updateOut()
    }
    
    setOutReceiver(outReceiver, inName){
        this.#outReceiver = outReceiver
        this.#outReceiverInName = inName
    }

    #updateOut(){
        this.#lastOut = this.#out
        this.#out = this.#func(this.#in1, this.#in2)
        if(this.#out != this.#lastOut){
            this.#send(this.#out)
        }
    }

    #send(flag){
        if(this.#outReceiver){
            this.#outReceiver.receive(this.#outReceiverInName, flag)
        }
    }

    receive(inName, flag){
        if(inName == "in1"){
            this.updateIn1(flag)
        }else if(inName == "in2"){
            this.updateIn2(flag)
        }
    }

    toString(){
        return "{gateTypeName} id: {id}, in1: {in1}, in2: {in2}, out:{out}"
            .replace("{gateTypeName}", this.#gateTypeName)
            .replace("{id}", this.#id)
            .replace("{in1}", this.#in1)
            .replace("{in2}", this.#in2)
            .replace("{out}", this.#out)
    }
}

//与门
class AndGate extends DoubleInGate{
    constructor(id, in1 = false, in2 = false){
        super(id, "AndGate", in1, in2, (i1, i2) => i1 && i2)
    }
}

//或门
class OrGate extends DoubleInGate{
    constructor(id, in1 = false, in2 = false){
        super(id, "OrGate", in1, in2, (i1, i2) => i1 || i2)
    }
}

//异或门
class XorGate extends DoubleInGate{
    constructor(id, in1 = false, in2 = false){
        //^在js按位异或, 而在java中不是
        super(id, "XorGate", in1, in2, (i1, i2) => (i1 || i2) && !(i1 && i2)) 
    }
}

class SingleInGate{
    #id
    #in
    #out
    #lastOut
    #func
    #outReceiver
    #outReceiverInName

    constructor(id, in_, func){
        this.#id = id
        this.#in = in_
        this.#func = func
        this.#out = this.#func(this.#in)
        // this.#lastOut = this.#out
    }

    updateIn(flag){
        this.#in = flag
        this.#updateOut()
    }

    getOut(){
        return this.#out
    }

    //注册输出端口接收者，（类观察者模式）
    setOutReceiver(outReceiver, inName){
        this.#outReceiver = outReceiver
        this.#outReceiverInName = inName
    }

    #updateOut(){
        this.#lastOut = this.#out
        this.#out = this.#func(this.#in)
        if(this.#out != this.#lastOut){
            this.#send(this.#out)
        }
    }

    #send(flag){
        if(this.#outReceiver){
            this.#outReceiver.receive(this.#outReceiverInName, flag)
        }    
    }

    receive(inName, flag){
        if(inName == "in"){ //TODO 或许有更灵活的写法
            this.updateIn(flag)
        }
    }
}

class NullGate extends SingleInGate{
    constructor(id, in_= false){
        super(id, in_, a=>a)
    }
}

class NotGate extends SingleInGate{
    constructor(id, in_= false){
        super(id, in_, a=>!a)
    }
}

class Adder{
    #id
    #inA
    #inB
    
    #outS
    #outC
    #lastOutS
    #lastOutC

    #outSReceiver
    #outSReceiverInName
    #outCReceiver
    #outCReceiverInName

    constructor(id, inA=false, inB=false, outS, outC){
        this.#id = id
        this.#inA = inA
        this.#inB = inB
        this.#outS = outS
        this.#outC = outC
    }

    updateInA(flag, func){
        this.#inA = flag
        this.updateOutSAndOutC(func)
    }

    updateInB(flag, func){
        this.#inB = flag
        this.updateOutSAndOutC(func)
    }

    updateBothIn(inA, inB, func){
        this.#inA = inA
        this.#inB = inB
        this.updateOutSAndOutC(func)
    }

    getOutS(){
        return this.#outS
    }

    getOutC(){
        return this.#outC
    }

    #updateOutS(flag){
        this.#lastOutS = this.#outS
        this.#outS = flag
        if(this.#outS != this.#lastOutS){
            this.#sendOutS(this.#outS)
        }
    }
    
    #updateOutC(flag){
        this.#lastOutC = this.#outC
        this.#outC = flag
        if(this.#outC != this.#lastOutC){
            this.#sendOutC(this.#outC)
        }
    }
    
    updateOutSAndOutC(func){
        if(func){
            var results = func()
            this.#updateOutS(results[0])
            this.#updateOutC(results[1])
        }
    }

    setOutSReceiver(outSReceiver, inName){
        this.#outSReceiver = outSReceiver
        this.#outSReceiverInName = inName
    }

    setOutCReceiver(outCReceiver, inName){
        this.#outCReceiver = outCReceiver
        this.#outCReceiverInName = inName
    }

    receive(inName, flag){
        if(inName == "inA"){
            this.updateInA(flag)
        }else if(inName == "inB"){
            this.updateInB(flag)
        }
    }

    #sendOutS(flag){
        if(this.#outSReceiver){
            this.#outSReceiver.receive(this.#outSReceiverInName, flag)
        }
    }

    #sendOutC(flag){
        if(this.#outCReceiver){
            this.#outCReceiver.receive(this.#outCReceiverInName, flag)
        }
    }
}

class HalfAdder extends Adder{
    #xorGate
    #andGate

    constructor(id, inA=false, inB=false){
        var xorGate = new XorGate(undefined, inA, inB);
        var andGate = new AndGate(undefined, inA, inB);
        super(id, inA, inB, xorGate.getOut(), andGate.getOut())
        this.#xorGate = xorGate
        this.#andGate = andGate 
    }

    #returnOutArray(){
        return [this.#xorGate.getOut(), this.#andGate.getOut()]
    }

    updateInA(flag){
        super.updateInA(flag, ()=>{
            this.#xorGate.updateIn1(flag)
            this.#andGate.updateIn1(flag)
            return this.#returnOutArray()
        })
    }

    updateInB(flag){
        super.updateInB(flag, ()=>{
            this.#xorGate.updateIn2(flag)
            this.#andGate.updateIn2(flag)
            return this.#returnOutArray()
        })
    }

    updateBothIn(inA, inB){
        super.updateBothIn(inA, inB, ()=>{
            this.#xorGate.updateBothIn(inA, inB)
            this.#andGate.updateBothIn(inA, inB)
            return this.#returnOutArray()
        })
    }

}

class FullAdder extends Adder{
    #inC
    #halfAdder1
    #halfAdder2
    #orGate

    constructor(id, inA = false, inB = false, inC = false){
        var halfAdder1 = new HalfAdder(undefined, inA, inB)
        var halfAdder2 = new HalfAdder(undefined, inC, halfAdder1.getOutS())
        var orGate = new OrGate(undefined, halfAdder1.getOutC(), halfAdder2.getOutC())
        super(id, inA, inB, halfAdder2.getOutS(), orGate.getOut())
        this.#inC = inC
        this.#halfAdder1 = halfAdder1
        this.#halfAdder2 = halfAdder2
        this.#orGate = orGate

        this.#halfAdder1.setOutSReceiver(halfAdder2, "inB")
        this.#halfAdder1.setOutCReceiver(orGate, "in1")
        this.#halfAdder2.setOutCReceiver(orGate, "in2")
    }

    #returnOutArray(){
        return [this.#halfAdder2.getOutS(), this.#orGate.getOut()]
    }

    updateInA(flag){
        super.updateInA(flag, ()=>{
            this.#halfAdder1.updateInA(flag)
            return this.#returnOutArray()
        })
    }

    updateInB(flag){
        super.updateInB(flag, ()=>{
            this.#halfAdder1.updateInB(flag)
            return this.#returnOutArray()
        })
    }

    updateInC(flag){
        this.#inC = flag
        this.#halfAdder2.updateInA(flag)
        this.updateOutSAndOutC(()=>{
            return this.#returnOutArray()
        })
    }

    updateBothIn(inA, inB){
        super.updateBothIn(inA, inB, ()=>{
            this.#halfAdder1.updateBothIn(inA, inB)
            return this.#returnOutArray()
        })
    }

    updateThreeIn(inA, inB, inC){
        super.updateBothIn(inA, inB)
        this.#inC = inC

        this.#halfAdder1.updateBothIn(inA, inB)
        this.#halfAdder2.updateBothIn(inC, this.#halfAdder1.getOutS())
        this.#orGate.updateBothIn(this.#halfAdder1.getOutC(), this.#halfAdder2.getOutC())

        this.updateOutSAndOutC(()=>{
            return this.#returnOutArray()
        })
    }

    receive(inName, flag){
        super.receive(inName, flag)
        if(inName == "inC"){
            this.updateInC(flag)
        }
    }
}

class EightBitBinaryAdder{
    #inC
    #outC
    #lastOutC

    #inA
    #inB
    #outS

    #fullAdders
    #fullAdderNum

    #outCReceiver
    #outCReceiverInName

    #outCInOutSFlag

    constructor(outCInOutSFlag = false){
        this.#outCInOutSFlag = outCInOutSFlag
        this.#inC = false
        this.#fullAdderNum = 8
        this.#fullAdders = []

        this.#inA = []
        this.#inB = []

        for(var i = 0; i < this.#fullAdderNum; i++){
            this.#inA.push(false)
            this.#inB.push(false)
        }

        //新键8个全加器
        for(var i = 0; i < this.#fullAdderNum; i++){
            this.#fullAdders.push(new FullAdder("f" + i))
            if(i != 0){
                this.#fullAdders[i - 1].setOutCReceiver(this.#fullAdders[i], "inC")
            }
        }

        this.updateOut()
    }

    updateBothIn(arrayA, arrayB){
        // this.#inC = inC
        this.#inA = arrayA
        this.#inB = arrayB

        for(var i = 0; i < this.#fullAdderNum; i++){
            if(i == 0){
                this.#fullAdders[i].updateInC(this.#inC)
            }
            this.#fullAdders[i].updateBothIn(arrayA[i], arrayB[i])
        }
        this.updateOut()
    }

    //输出默认值
    updateOut(){
        this.#outS = []

        for(var i = 0; i < this.#fullAdderNum; i++){
            this.#outS.push(this.#fullAdders[i].getOutS())
            if(i == this.#fullAdderNum - 1){
                this.#lastOutC = this.#outC
                this.#outC = this.#fullAdders[i].getOutC()

                if(this.#lastOutC != this.#outC)
                    this.#sendOutC(this.#outC)

                if(this.#outCInOutSFlag)
                    this.#outS.push(this.#outC)

            }
        }
    }

    updateInC(flag){
        this.#inC = flag
        this.updateBothIn(this.#inA, this.#inB, flag)
    }

    receive(inName, flag){
        if(inName == "inC"){
            this.updateInC(flag)
        }
    }

    #sendOutC(flag){
        if(this.#outCReceiver){
            this.#outCReceiver.receive(this.#outCReceiverInName, flag)
        }
    }

    setOutCReceiver(outCReceiver, inName){
        this.#outCReceiver = outCReceiver
        this.#outCReceiverInName = inName
    }

    getOut(){
        return this.#outS
    }
}

class SixteenBitBinaryAdder{
    #inC
    #outC
    #lastOutC

    #inA
    #inB
    #outS

    #eightBitBinaryAdder1
    #eightBitBinaryAdder2

    #bitNum = 16

    #outCReceiver
    #outCReceiverInName

    #outCInOutSFlag

    constructor(outCInOutSFlag){
        this.#outCInOutSFlag = outCInOutSFlag
        this.#inC = false
        this.#eightBitBinaryAdder1 = new EightBitBinaryAdder()
        this.#eightBitBinaryAdder2 = new EightBitBinaryAdder()

        this.#inA = []
        this.#inB = []

        for(var i = 0; i < this.#bitNum; i++){
            this.#inA.push(false)
            this.#inB.push(false)
        }

        this.#eightBitBinaryAdder1.setOutCReceiver(this.#eightBitBinaryAdder2, "inC")

        this.updateOut()
    }

    updateBothIn(arrayA, arrayB){
        this.#inA = arrayA
        this.#inB = arrayB
        this.#eightBitBinaryAdder1.updateBothIn(arrayA.slice(0, 8), arrayB.slice(0, 8))
        this.#eightBitBinaryAdder2.updateBothIn(arrayA.slice(8), arrayB.slice(8))
        this.updateOut()
    }

    updateOut(){
        this.#outS = this.#eightBitBinaryAdder1.getOut().concat(this.#eightBitBinaryAdder2.getOut())
        //发送send(OutC)
    }
    getOut(){
        return this.#outS
    }

    //TODO
    // updateInC(flag){
    //     this.#inC = flag

    //     this.updateBothIn(this.#inA, this.#inB, flag)
    // }

    // receive(inName, flag){
    //     if(inName == "inC"){
    //         this.updateInC(flag)
    //     }
    // }

    #sendOutC(flag){
        if(this.#outCReceiver){
            this.#outCReceiver.receive(this.#outCReceiverInName, flag)
        }
    }

    setOutCReceiver(outCReceiver, inName){
        this.#outCReceiver = outCReceiver
        this.#outCReceiverInName = inName
    }

}

运行验证代码testModel.js
验证通过判据：后台没有打印输出异常。

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Test</title>
    <script src="../js/test/TestUtils.js"></script>
    <script src="../js/model.js"></script>
    <script src="../js/utils.js"></script>
</head>
<body>

    <script>
        var g1 = new NullGate("g1")
        var g2 = new NullGate("g2")
        var g3 = new NullGate("g3")
        var g4 = new NullGate("g4")
        var g5 = new NullGate("g5")
        var g6 = new NullGate("g6")

        g1.setOutReceiver(g2, "in")
        g2.setOutReceiver(g3, "in")
        g3.setOutReceiver(g4, "in")
        g4.setOutReceiver(g5, "in")
        g5.setOutReceiver(g6, "in")

        g1.updateIn(true)
        assertTrue(g6.getOut())
    </script>

    <script>
        //与门
        var andGate = new AndGate("a01")
        assertFalse(andGate.getOut())

        andGate.updateIn1(true)
        assertFalse(andGate.getOut())

        andGate.updateIn2(true)
        assertTrue(andGate.getOut())

        //或门
        var orGate = new OrGate("o01")
        assertFalse(orGate.getOut())

        orGate.updateIn1(true)
        assertTrue(orGate.getOut())

        orGate.updateIn2(true)
        assertTrue(orGate.getOut())

        //异或门
        var xorGate = new XorGate("x01")
        assertFalse(xorGate.getOut())

        xorGate.updateIn1(true)
        assertTrue(xorGate.getOut())

        xorGate.updateIn2(true)
        assertFalse(xorGate.getOut())

        xorGate.updateBothIn(false, true)
        assertTrue(xorGate.getOut())

    </script>
    <script>
        //半加器
        var ha = new HalfAdder("h01")
        assertFalse(ha.getOutS())
        assertFalse(ha.getOutC())
        
        ha.updateInB(true)
        assertTrue(ha.getOutS())
        assertFalse(ha.getOutC())

        ha.updateInA(true)
        assertFalse(ha.getOutS())
        assertTrue(ha.getOutC())

        ha.updateBothIn(true, false)
        assertTrue(ha.getOutS())
        assertFalse(ha.getOutC())
    </script>

    <script>
        //全加器
        var fa = new FullAdder("fa01")
        assertFalse(fa.getOutC())
        assertFalse(fa.getOutS())

        function test(inA, inB, inC, expectedS, expectedC){
            fa.updateThreeIn(inA, inB, inC)
            if(expectedS)
                assertTrue(fa.getOutS())
            else
                assertFalse(fa.getOutS())

            if(expectedC)
                assertTrue(fa.getOutC())
            else
                assertFalse(fa.getOutC())
        }

        test(false, false, false, false, false)
        test(false, true, false, true, false)
        test(true, false, false, true, false)
        test(true, true, false, false, true)
        test(false, false, true, true, false)
        test(false, true, true, false, true)
        test(true, false, true, false, true)
        test(true, true, true, true, true)
        
    </script>

    <script>
        for(var i = 0 ; i < 256; i++){
            assertIntEquals(i, lowEightBitArray2Int(int2LowEightBitArray(i)))
        }
    </script>
    <script>
        var ebba = new EightBitBinaryAdder(true)

        for(var i = 0; i < 256; i++){
            for(var j = 0; j < 256; j++){i
                ebba.updateBothIn(int2LowEightBitArray(i), int2LowEightBitArray(j))
                assertIntEquals(i + j, lowNineBitArray2Int(ebba.getOut()))
            }
        }

    </script>
    <script>
        for(var i = -128; i <= 127; i++){
            assertIntEquals(i, eightBitArray2Int(int2EightBitArray(i)))
        }
    </script>
    <script>
        var ebba = new EightBitBinaryAdder()

        for(var i = -64; i < 64; i++){
            for(var j = -64; j < 64; j++){
                ebba.updateBothIn(int2EightBitArray(i), int2EightBitArray(j))
                assertIntEquals(i + j, eightBitArray2Int(ebba.getOut()))
            }
        }
    </script>
    <script>
        for(var i = -(1<<15); i <= (1<<15) - 1; i++){
            assertIntEquals(i, sixteentBitArray2Int(int2SixteenBitArray(i)))
        }
    </script>

    <script>
        var sbba = new SixteenBitBinaryAdder()

        sbba.updateBothIn(int2SixteenBitArray(1156), int2SixteenBitArray(9999))
        assertIntEquals(9999 + 1156, sixteentBitArray2Int(sbba.getOut()))

        //‭16384‬ * ‭16384‬ = 268435456 如果这样算会十分耗时
        // for(var i = -(1<<14); i < (1<<14); i++){
        //     for(var j = -(1<<14); j < (1<<14); j++){
        //         sbba.updateBothIn(int2SixteenBitArray(i), int2SixteenBitArray(j))
        //         assertIntEquals(i + j, sixteentBitArray2Int(sbba.getOut()))
        //     }
        // }
        for(var i = -100; i < 100; i++){
            for(var j = -100; j < 100; j++){
                sbba.updateBothIn(int2SixteenBitArray(i), int2SixteenBitArray(j))
                assertIntEquals(i + j, sixteentBitArray2Int(sbba.getOut()))
            }
        }
    </script>
</body>
</html>

加载全部内容