diff options
Diffstat (limited to 'cpu/alu.ml')
| -rw-r--r-- | cpu/alu.ml | 148 |
1 files changed, 124 insertions, 24 deletions
@@ -53,20 +53,114 @@ let nadder n a b = let a, b = nadder_with_carry n a b (const "0") in b ^. a +let neg n a = nadder n (not a) (one n) + let rec nsubber n a b = - zeroes n (* TODO *) + let r, c = nadder_with_carry n a (not b) (const "1") in + c ^. r + + + + +(* Some operations on Redundant Binary Representation + Each binary digit is encoded on 2 bits + + A n-digits number in RBR is written + [a_0, a'_0, a_1, a'_1, ..., a_(n-1), a'_(n-1)] + +*) + +(* [a] and [b] are encoded on 2n bits + [c_in] and [c_out] on 2 bits *) + +let rec rbr_nadder_with_carry n a b c_in = + + if n = 0 then (zeroes 0), c_in else + + let fa1s, fa1r = fulladder (a ** 1) (b ** 0) (b ** 1) in + let fa2s, fa2r = fulladder (c_in ** 1) (a ** 0) fa1s in + + let rec_s, rec_c = + rbr_nadder_with_carry (n - 1) + (a % (2, 2*n - 1)) + (b % (2, 2*n - 1)) + (fa1r ++ fa2r) + + in (c_in ** 0) ++ fa2s ++ rec_s, rec_c + + +let rbr_nadder n a b = + let s, c = rbr_nadder_with_carry n a b (zeroes 2) in + c ^. s + + +let bin_of_rbr n a c = + + (* Split even and odd bits *) + let rec split_bits n a = + if n = 0 then (zeroes 0, zeroes 0) + else + let even, odd = split_bits (n-1) (a % (2, 2*n - 1)) in + (a ** 0) ++ even, (a ** 1) ++ odd + + in + let a_even, a_odd = split_bits n a in + + nadder n a_even a_odd + + + +(* TODO : move to utils module *) +let rec range a b = if a > b then [] else a :: (range (a+1) b) + +(* Sépare en deux listes de même taille une liste de taille paire *) +let rec split_list = function + | [] -> [], [] + | [_] -> assert false + | x::y::tl -> let a, b = split_list tl in x::a, y::b + +let nmulu n a b start_signal = + let next_busy, set_next_busy = loop 1 in + let busy = start_signal ^| (reg 1 next_busy) in + + (* 'mule' est intialisé à b au début de la multiplication, + puis à chaque cycle est shifté de 1 bit vers la droite (donc perd le bit de poid faible) *) + let mule, set_mule = loop n in + let mule = set_mule (mux start_signal (((reg n mule) % (1, n-1)) ++ const "0") b) in + (* 'adde' est initialisé à a étendu sur 32 bits au début de la multiplication, + puis à chaque cycle est shifté de 1 bit vers la gauche (donc multiplié par 2) *) + let adde, set_adde = loop (2*n) in + let adde = set_adde (mux start_signal (const "0" ++ ((reg (2*n) adde) % (0, 2*n-2))) (a ++ (zeroes n))) in + + (* 'res' est un accumulateur qui contient le résultat que l'on calcule, + il est initialisé à 0 au début de la multiplication, et à chaque cycle + si mule[0] est non nul, on lui rajoute adde (c'est correct) *) + let res, set_res = loop (2*n) in + let t_res = mux start_signal (reg (2*n) res) (zeroes (2*n)) in + let res = set_res (mux (mule ** 0) t_res (nadder (2*n) adde t_res)) in + let work_remains = nonnull (n - 1) (mule % (1, n-1)) in + + let finished = + set_next_busy (busy ^& work_remains) ^. + (not work_remains) ^& busy in + + res % (0, n-1), res % (n, 2*n-1), finished + + + +let rec ndivu n a b start_signal = + zeroes (n-3) ++ const "110", zeroes (n-3) ++ const "110", start_signal + (* TODO : unsigned division, returns quotient and remainder *) -let rec nmul n a b = - zeroes n, zeroes n (* TODO : retuns lo and hi part of 32-bit answer *) +let rec nmul n a b start_signal = + zeroes (n-3) ++ const "101", zeroes (n-3) ++ const "101", start_signal + (* TODO : signed multiplication ; returns low part and high part *) -let rec ndiv n a b = - zeroes n, zeroes n (* TODO : returns quotient and remainder *) -let rec nmulu n a b = - zeroes n, zeroes n (* TODO : same as nmul but unsigned *) +let rec ndiv n a b start_signal = + zeroes (n - 3) ++ const "011", zeroes (n - 3) ++ const "011", start_signal + (* TODO : signed division *) -let rec ndivu n a b = - zeroes n, zeroes n (* TODO : save as ndiv but unsigned *) (* Shifts *) @@ -123,26 +217,31 @@ let alu_comparer n f0 f a b = let lte = mux (f ** 1) lte_signed lte_unsigned in mux f0 eq_ne lte -let alu_arith f1 f a b = +let alu_arith f0 f a b start_signal = (* See table for ALU below *) let add = nadder 16 a b in let sub = nsubber 16 a b in - let mul, mul2 = nmul 16 a b in - let div, div2 = ndiv 16 a b in - let mulu, mulu2 = nmulu 16 a b in - let divu, divu2 = ndivu 16 a b in + let mul, mul2, mul_end_signal = nmul 16 a b start_signal in + let div, div2, div_end_signal = ndiv 16 a b start_signal in + let mulu, mulu2, mulu_end_signal = nmulu 16 a b start_signal in + let divu, divu2, divu_end_signal = ndivu 16 a b start_signal in let q00 = mux (f ** 0) add sub in let q01 = mux (f ** 0) mul div in let q03 = mux (f ** 0) mulu divu in let q10 = mux (f ** 1) q00 q01 in let q11 = mux (f ** 1) q00 q03 in - let q = mux f1 q10 q11 in + let q = mux f0 q10 q11 in let r01 = mux (f ** 0) mul2 div2 in let r03 = mux (f ** 0) mulu2 divu2 in let r10 = mux (f ** 1) (zeroes 16) r01 in let r11 = mux (f ** 1) (zeroes 16) r03 in - let r = mux f1 r10 r11 in - q, r + let r = mux f0 r10 r11 in + let s01 = mux (f ** 0) mul_end_signal div_end_signal in + let s03 = mux (f ** 0) mulu_end_signal divu_end_signal in + let s10 = mux (f ** 1) start_signal s01 in + let s11 = mux (f ** 1) start_signal s03 in + let end_signal = mux f0 s10 s11 in + q, r, end_signal let alu_logic f a b = (* See table for ALU below *) @@ -155,9 +254,9 @@ let alu_shifts f a b = let q1 = mux (f ** 0) (op_lsr 16 a b) (op_asr 16 a b) in mux (f ** 1) (op_lsl 16 a b) q1 -let alu f1 f0 f a b = +let alu f1 f0 f a b start_signal = (* - f0 f1 f action + f1 f0 f action -- -- - ------ 0 0 0 add 0 0 1 sub @@ -176,12 +275,13 @@ let alu f1 f0 f a b = 1 1 2 lsr 1 1 3 asr *) - let arith, arith_r = alu_arith f1 f a b in + let arith, arith_r, arith_end_signal = alu_arith f0 f a b start_signal in let logic = alu_logic f a b in let shifts = alu_shifts f a b in - let q0 = mux f1 logic shifts in - let s = mux f0 arith q0 in - let r = mux f0 arith_r (zeroes 16) in - s, r + let q0 = mux f0 logic shifts in + let s = mux f1 arith q0 in + let r = mux f1 arith_r (zeroes 16) in + let end_signal = mux f1 arith_end_signal start_signal in + s, r, end_signal |