Mercurial > pygar

     1 

     2 import FIFO::*;

     3 import ConfigReg::*;

     4 import RWire::*;

     5 

     6 import List::*;

     7 import Monad::*;

     8 

     9 interface SFIFO#(type alpha_T, type search_T);

    10    method Action enq(alpha_T x);

    11    method Action deq();

    12    method alpha_T first();

    13    method Action clear();

    14    method Bool find(search_T x);   

    15    method Bool find2(search_T x);

    16    method Bool notEmpty();

    17    method Bool notFull();

    18 endinterface

    19 

    20 module mkSFIFO#(function Bool searchfunc(search_T s, alpha_T x)) (SFIFO#(alpha_T, search_T))

    21     provisos

    22       (Bits#(alpha_T,asz));

    23 

    24     Reg#(alpha_T) f0 <- mkConfigRegU;

    25     Reg#(alpha_T) f1 <- mkConfigRegU;

    26 

    27     Reg#(Bool)   vf0 <- mkConfigReg(False);

    28     Reg#(Bool)   vf1 <- mkConfigReg(False);

    29 

    30     PulseWire edge1      <- mkPulseWire();

    31       

    32     method Action enq(alpha_T x) if (!(vf0 && vf1));

    33       if (edge1 || !vf0)//empty or we're dequeueing

    34 	begin

    35           vf0 <= True; //True

    36 	  vf1 <= False;

    37 	   f0 <= x;

    38   	end

    39       else // !vf1 

    40         begin

    41           vf1 <= True;

    42            f1 <= x;

    43  	end

    44     endmethod

    45 										

    46     method Action deq() if (vf0);

    47       edge1.send();

    48       vf0 <= vf1;

    49        f0 <= f1;

    50       vf1 <= False;

    51     endmethod  

    52 

    53     method alpha_T first() if(vf0);

    54       return (f0);

    55     endmethod  

    56 

    57     method Action clear();

    58       vf0 <= False;

    59       vf1 <= False;

    60     endmethod

    61 

    62     method Bool find(search_T sv);

    63       Bool nvf0 = edge1 ? False: vf0;

    64       Bool nvf1 = vf1;

    65 

    66       return (nvf0 && searchfunc(sv, f0) || 

    67               nvf1 && searchfunc(sv, f1));

    68     endmethod

    69 

    70     method Bool find2(search_T sv);

    71       Bool nvf0 = edge1 ? False: vf0;

    72       Bool nvf1 = vf1;

    73       

    74       return (nvf0 && searchfunc(sv, f0) || 

    75               nvf1 && searchfunc(sv, f1));

    76     endmethod

    77 

    78     method notEmpty() = vf0._read;

    79 

    80     method Bool notFull();

    81       return !(vf0 && vf1);

    82     endmethod

    83 

    84 endmodule

    85 

    86 module mkSFIFO1#(function Bool searchfunc(search_T s, alpha_T x)) (SFIFO#(alpha_T, search_T))

    87     provisos

    88       (Bits#(alpha_T,asz), Eq#(alpha_T));

    89 

    90     Reg#(alpha_T) f0 <- mkConfigRegU;

    91 

    92     Reg#(Bool)   vf0 <- mkConfigReg(False);

    93 

    94     PulseWire edge1      <- mkPulseWire();

    95       

    96     method Action enq(alpha_T x) if (!vf0);

    97       vf0 <= True; //True

    98       f0 <= x;

    99     endmethod

   100 										

   101     method Action deq() if (vf0);

   102       edge1.send();

   103       vf0 <= False;

   104     endmethod  

   105 

   106     method alpha_T first() if(vf0);

   107       return (f0);

   108     endmethod  

   109 

   110     method Action clear();

   111       vf0 <= False;

   112     endmethod

   113 

   114     method Bool find(search_T sv);

   115       Bool nvf0 = edge1 ? False: vf0;

   116 

   117       return (nvf0 && searchfunc(sv, f0));

   118     endmethod

   119 

   120     method Bool find2(search_T sv);

   121       Bool nvf0 = edge1 ? False: vf0;

   122       return (nvf0 && searchfunc(sv, f0));

   123     endmethod

   124 

   125     method notEmpty() = vf0._read;

   126 

   127     method Bool notFull();

   128       return !vf0;

   129     endmethod

   130 

   131 endmodule

   132 

   133 module mkSizedSFIFOInternal#(Integer n, 

   134 			     function Bool searchfunc1(search_T s, alpha_T x), 

   135 			     function Bool searchfunc2(search_T s, alpha_T x))  (SFIFO#(alpha_T, search_T))

   136 				

   137    provisos ( Bits#(alpha_T,alpha_SZ) );

   138 

   139   List#(Reg#(alpha_T)) registers <- replicateM(n, mkRegU);

   140   List#(Reg#(Bool))   valids <- replicateM(n, mkReg(False));

   141 

   142   function Nat getNextFree (List#(Reg#(Bool)) vs);

   143 

   144     Nat res = fromInteger(n - 1);

   145 

   146     for (Integer x = n - 1; x > -1; x = x - 1)

   147       res = !vs[x]._read() ? fromInteger(x) : res;

   148 

   149     return res;

   150   

   151   endfunction

   152 

   153   function Bool notFullHelper();

   154   

   155     Bool full = True;

   156 

   157     for (Integer x = 0; x < n; x = x + 1)

   158       full = full && valids[x]._read();

   159 

   160     return !full;

   161   

   162   endfunction

   163 

   164   method Action enq( alpha_T item ) if ( notFullHelper() );

   165     

   166     Nat k = getNextFree(valids);

   167     select(valids, k)._write(True);

   168     select(registers, k)._write(item);

   169     

   170   endmethod

   171 

   172   method Action deq() if ( valids[0]._read() );

   173     

   174     for (Integer x = 0; x < (n-1); x = x + 1)

   175     begin

   176     

   177       (registers[x]) <= registers[x + 1]._read();

   178       (valids[x]) <= valids[x + 1]._read();

   179     

   180     end

   181     (valids[n-1]) <= False;

   182   endmethod  

   183 

   184   method alpha_T first() if ( valids[0]._read() );

   185     return registers[0]._read();  

   186   endmethod

   187 

   188   method Bool find(search_T sv);

   189     Bool res = False;

   190     

   191     for (Integer x = 0; x < n; x = x + 1)

   192        if ( valids[x]._read() && searchfunc1(sv, registers[x]._read()) )

   193           res = True;

   194     

   195     return res;

   196     

   197   endmethod

   198 

   199   method Bool find2(search_T sv);

   200     Bool res = False;

   201     

   202      for (Integer x = 0; x < n; x = x + 1)

   203         if ( valids[x]._read() && searchfunc2(sv, registers[x]._read()) )

   204            res = True;

   205     

   206     return res;

   207     

   208   endmethod

   209 

   210   method Action clear();

   211   

   212     for (Integer x = 0; x < n; x = x + 1)

   213       (valids[x]) <= False;

   214     

   215   endmethod

   216 

   217   method Bool notEmpty();

   218     return valids[0]._read(); 

   219   endmethod

   220 

   221   method Bool notFull();

   222     return notFullHelper();

   223   endmethod

   224 

   225 endmodule

   226 

   227 module mkSizedSFIFO#(Integer n, function Bool searchfunc(search_T s, alpha_T x))  (SFIFO#(alpha_T, search_T))

   228     provisos

   229       (Bits#(alpha_T,asz));

   230    

   231    let foo <- mkSizedSFIFOInternal(n, searchfunc, searchfunc);

   232    return foo;

   233 

   234 endmodule
author	punk
date	Tue, 27 Apr 2010 09:03:28 -0400
parents	74716e9a81cc
children