JS串行加法器
巨輪 人气: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>
加载全部内容