rlm@8: 
rlm@8: import FIFO::*;
rlm@8: import ConfigReg::*;
rlm@8: import RWire::*;
rlm@8: 
rlm@8: import List::*;
rlm@8: import Monad::*;
rlm@8: 
rlm@8: interface SFIFO#(type alpha_T, type search_T);
rlm@8:    method Action enq(alpha_T x);
rlm@8:    method Action deq();
rlm@8:    method alpha_T first();
rlm@8:    method Action clear();
rlm@8:    method Bool find(search_T x);   
rlm@8:    method Bool find2(search_T x);
rlm@8:    method Bool notEmpty();
rlm@8:    method Bool notFull();
rlm@8: endinterface
rlm@8: 
rlm@8: module mkSFIFO#(function Bool searchfunc(search_T s, alpha_T x)) (SFIFO#(alpha_T, search_T))
rlm@8:     provisos
rlm@8:       (Bits#(alpha_T,asz));
rlm@8: 
rlm@8:     Reg#(alpha_T) f0 <- mkConfigRegU;
rlm@8:     Reg#(alpha_T) f1 <- mkConfigRegU;
rlm@8: 
rlm@8:     Reg#(Bool)   vf0 <- mkConfigReg(False);
rlm@8:     Reg#(Bool)   vf1 <- mkConfigReg(False);
rlm@8: 
rlm@8:     PulseWire edge1      <- mkPulseWire();
rlm@8:       
rlm@8:     method Action enq(alpha_T x) if (!(vf0 && vf1));
rlm@8:       if (edge1 || !vf0)//empty or we're dequeueing
rlm@8: 	begin
rlm@8:           vf0 <= True; //True
rlm@8: 	  vf1 <= False;
rlm@8: 	   f0 <= x;
rlm@8:   	end
rlm@8:       else // !vf1 
rlm@8:         begin
rlm@8:           vf1 <= True;
rlm@8:            f1 <= x;
rlm@8:  	end
rlm@8:     endmethod
rlm@8: 										
rlm@8:     method Action deq() if (vf0);
rlm@8:       edge1.send();
rlm@8:       vf0 <= vf1;
rlm@8:        f0 <= f1;
rlm@8:       vf1 <= False;
rlm@8:     endmethod  
rlm@8: 
rlm@8:     method alpha_T first() if(vf0);
rlm@8:       return (f0);
rlm@8:     endmethod  
rlm@8: 
rlm@8:     method Action clear();
rlm@8:       vf0 <= False;
rlm@8:       vf1 <= False;
rlm@8:     endmethod
rlm@8: 
rlm@8:     method Bool find(search_T sv);
rlm@8:       Bool nvf0 = edge1 ? False: vf0;
rlm@8:       Bool nvf1 = vf1;
rlm@8: 
rlm@8:       return (nvf0 && searchfunc(sv, f0) || 
rlm@8:               nvf1 && searchfunc(sv, f1));
rlm@8:     endmethod
rlm@8: 
rlm@8:     method Bool find2(search_T sv);
rlm@8:       Bool nvf0 = edge1 ? False: vf0;
rlm@8:       Bool nvf1 = vf1;
rlm@8:       
rlm@8:       return (nvf0 && searchfunc(sv, f0) || 
rlm@8:               nvf1 && searchfunc(sv, f1));
rlm@8:     endmethod
rlm@8: 
rlm@8:     method notEmpty() = vf0._read;
rlm@8: 
rlm@8:     method Bool notFull();
rlm@8:       return !(vf0 && vf1);
rlm@8:     endmethod
rlm@8: 
rlm@8: endmodule
rlm@8: 
rlm@8: module mkSFIFO1#(function Bool searchfunc(search_T s, alpha_T x)) (SFIFO#(alpha_T, search_T))
rlm@8:     provisos
rlm@8:       (Bits#(alpha_T,asz), Eq#(alpha_T));
rlm@8: 
rlm@8:     Reg#(alpha_T) f0 <- mkConfigRegU;
rlm@8: 
rlm@8:     Reg#(Bool)   vf0 <- mkConfigReg(False);
rlm@8: 
rlm@8:     PulseWire edge1      <- mkPulseWire();
rlm@8:       
rlm@8:     method Action enq(alpha_T x) if (!vf0);
rlm@8:       vf0 <= True; //True
rlm@8:       f0 <= x;
rlm@8:     endmethod
rlm@8: 										
rlm@8:     method Action deq() if (vf0);
rlm@8:       edge1.send();
rlm@8:       vf0 <= False;
rlm@8:     endmethod  
rlm@8: 
rlm@8:     method alpha_T first() if(vf0);
rlm@8:       return (f0);
rlm@8:     endmethod  
rlm@8: 
rlm@8:     method Action clear();
rlm@8:       vf0 <= False;
rlm@8:     endmethod
rlm@8: 
rlm@8:     method Bool find(search_T sv);
rlm@8:       Bool nvf0 = edge1 ? False: vf0;
rlm@8: 
rlm@8:       return (nvf0 && searchfunc(sv, f0));
rlm@8:     endmethod
rlm@8: 
rlm@8:     method Bool find2(search_T sv);
rlm@8:       Bool nvf0 = edge1 ? False: vf0;
rlm@8:       return (nvf0 && searchfunc(sv, f0));
rlm@8:     endmethod
rlm@8: 
rlm@8:     method notEmpty() = vf0._read;
rlm@8: 
rlm@8:     method Bool notFull();
rlm@8:       return !vf0;
rlm@8:     endmethod
rlm@8: 
rlm@8: endmodule
rlm@8: 
rlm@8: module mkSizedSFIFOInternal#(Integer n, 
rlm@8: 			     function Bool searchfunc1(search_T s, alpha_T x), 
rlm@8: 			     function Bool searchfunc2(search_T s, alpha_T x))  (SFIFO#(alpha_T, search_T))
rlm@8: 				
rlm@8:    provisos ( Bits#(alpha_T,alpha_SZ) );
rlm@8: 
rlm@8:   List#(Reg#(alpha_T)) registers <- replicateM(n, mkRegU);
rlm@8:   List#(Reg#(Bool))   valids <- replicateM(n, mkReg(False));
rlm@8: 
rlm@8:   function Nat getNextFree (List#(Reg#(Bool)) vs);
rlm@8: 
rlm@8:     Nat res = fromInteger(n - 1);
rlm@8: 
rlm@8:     for (Integer x = n - 1; x > -1; x = x - 1)
rlm@8:       res = !vs[x]._read() ? fromInteger(x) : res;
rlm@8: 
rlm@8:     return res;
rlm@8:   
rlm@8:   endfunction
rlm@8: 
rlm@8:   function Bool notFullHelper();
rlm@8:   
rlm@8:     Bool full = True;
rlm@8: 
rlm@8:     for (Integer x = 0; x < n; x = x + 1)
rlm@8:       full = full && valids[x]._read();
rlm@8: 
rlm@8:     return !full;
rlm@8:   
rlm@8:   endfunction
rlm@8: 
rlm@8:   method Action enq( alpha_T item ) if ( notFullHelper() );
rlm@8:     
rlm@8:     Nat k = getNextFree(valids);
rlm@8:     select(valids, k)._write(True);
rlm@8:     select(registers, k)._write(item);
rlm@8:     
rlm@8:   endmethod
rlm@8: 
rlm@8:   method Action deq() if ( valids[0]._read() );
rlm@8:     
rlm@8:     for (Integer x = 0; x < (n-1); x = x + 1)
rlm@8:     begin
rlm@8:     
rlm@8:       (registers[x]) <= registers[x + 1]._read();
rlm@8:       (valids[x]) <= valids[x + 1]._read();
rlm@8:     
rlm@8:     end
rlm@8:     (valids[n-1]) <= False;
rlm@8:   endmethod  
rlm@8: 
rlm@8:   method alpha_T first() if ( valids[0]._read() );
rlm@8:     return registers[0]._read();  
rlm@8:   endmethod
rlm@8: 
rlm@8:   method Bool find(search_T sv);
rlm@8:     Bool res = False;
rlm@8:     
rlm@8:     for (Integer x = 0; x < n; x = x + 1)
rlm@8:        if ( valids[x]._read() && searchfunc1(sv, registers[x]._read()) )
rlm@8:           res = True;
rlm@8:     
rlm@8:     return res;
rlm@8:     
rlm@8:   endmethod
rlm@8: 
rlm@8:   method Bool find2(search_T sv);
rlm@8:     Bool res = False;
rlm@8:     
rlm@8:      for (Integer x = 0; x < n; x = x + 1)
rlm@8:         if ( valids[x]._read() && searchfunc2(sv, registers[x]._read()) )
rlm@8:            res = True;
rlm@8:     
rlm@8:     return res;
rlm@8:     
rlm@8:   endmethod
rlm@8: 
rlm@8:   method Action clear();
rlm@8:   
rlm@8:     for (Integer x = 0; x < n; x = x + 1)
rlm@8:       (valids[x]) <= False;
rlm@8:     
rlm@8:   endmethod
rlm@8: 
rlm@8:   method Bool notEmpty();
rlm@8:     return valids[0]._read(); 
rlm@8:   endmethod
rlm@8: 
rlm@8:   method Bool notFull();
rlm@8:     return notFullHelper();
rlm@8:   endmethod
rlm@8: 
rlm@8: endmodule
rlm@8: 
rlm@8: module mkSizedSFIFO#(Integer n, function Bool searchfunc(search_T s, alpha_T x))  (SFIFO#(alpha_T, search_T))
rlm@8:     provisos
rlm@8:       (Bits#(alpha_T,asz));
rlm@8:    
rlm@8:    let foo <- mkSizedSFIFOInternal(n, searchfunc, searchfunc);
rlm@8:    return foo;
rlm@8: 
rlm@8: endmodule