原创 FIFO学习（转）

 2010-9-30 13:57  2329 4 4 分类: FPGA/CPLD

1．什么是FIFO？
FIFO是英文First In First Out 的缩写，是一种先进先出的数据缓存器，他与普通存储器的区别是没有外部读写地址线，这样使用起来非常简单，但缺点就是只能顺序写入数据，顺序的读出数据，其数据地址由内部读写指针自动加1完成，不能像普通存储器那样可以由地址线决定读取或写入某个指定的地址。

2．什么情况下用FIFO？
FIFO一般用于不同时钟域之间的数据传输，比如FIFO的一端时AD数据采集，另一端时计算机的PCI总线，假设其AD采集的速率为16位 100K SPS，那么每秒的数据量为100K×16bit=1.6Mbps,而PCI总线的速度为33MHz，总线宽度32bit,其最大传输速率为1056Mbps,在两个不同的时钟域间就可以采用FIFO来作为数据缓冲。另外对于不同宽度的数据接口也可以用FIFO，例如单片机位8位数据输出，而DSP可能是16位数据输入，在单片机与DSP连接时就可以使用FIFO来达到数据匹配的目的。

3．FIFO的一些重要参数
FIFO的宽度：也就是英文资料里常看到的THE WIDTH，它只的是FIFO一次读写操作的数据位，就像MCU有8位和16位，ARM 32位等等，FIFO的宽度在单片成品IC中是固定的，也有可选择的，如果用FPGA自己实现一个FIFO，其数据位，也就是宽度是可以自己定义的。

FIFO的深度：THE DEEPTH，它指的是FIFO可以存储多少个N位的数据（如果宽度为N）。如一个8位的FIFO，若深度为8，它可以存储8个8位的数据，深度为12 ，就可以存储12个8位的数据，FIFO的深度可大可小，个人认为FIFO深度的计算并无一个固定的公式。在FIFO实际工作中，其数据的满/空标志可以控制数据的继续写入或读出。在一个具体的应用中也不可能由一些参数算数精确的所需FIFO深度为多少，这在写速度大于读速度的理想状态下是可行的，但在实际中用到的FIFO深度往往要大于计算值。一般来说根据电路的具体情况，在兼顾系统性能和FIFO成本的情况下估算一个大概的宽度和深度就可以了。而对于写速度慢于读速度的应用，FIFO的深度要根据读出的数据结构和读出数据的由那些具体的要求来确定。
满标志：FIFO已满或将要满时由FIFO的状态电路送出的一个信号，以阻止FIFO的写操作继续向FIFO中写数据而造成溢出（overflow）。
空标志：FIFO已空或将要空时由FIFO的状态电路送出的一个信号，以阻止FIFO的读操作继续从FIFO中读出数据而造成无效数据的读出（underflow）。
读时钟：读操作所遵循的时钟，在每个时钟沿来临时读数据。
写时钟：写操作所遵循的时钟，在每个时钟沿来临时写数据。
读指针：指向下一个读出地址。读完后自动加1。
写指针：指向下一个要写入的地址的，写完自动加1。
读写指针其实就是读写的地址，只不过这个地址不能任意选择，而是连续的。

4．FIFO的分类
根均FIFO工作的时钟域，可以将FIFO分为同步FIFO和异步FIFO。同步FIFO是指读时钟和写时钟为同一个时钟。在时钟沿来临时同时发生读写操作。异步FIFO是指读写时钟不一致，读写时钟是互相独立的。

5．FIFO设计的难点
FIFO设计的难点在于怎样判断FIFO的空/满状态。为了保证数据正确的写入或读出，而不发生益处或读空的状态出现，必须保证FIFO在满的情况下，不能进行写操作。在空的状态下不能进行读操作。怎样判断FIFO的满/空就成了FIFO设计的核心问题。由于同步FIFO几乎很少用到，这里只描述异步FIFO的空/满标志产生问题。
在用到触发器的设计中，不可避免的会遇到亚稳态的问题（关于亚稳态这里不作介绍，可查看相关资料）。在涉及到触发器的电路中，亚稳态无法彻底消除，只能想办法将其发生的概率将到最低。其中的一个方法就是使用格雷码。格雷码在相邻的两个码元之间只由一位变换(二进制码在很多情况下是很多码元在同时变化)。这就会避免计数器与时钟同步的时候发生亚稳态现象。但是格雷码有个缺点就是只能定义2^n的深度，而不能像二进制码那样随意的定义FIFO的深度，因为格雷码必须循环一个2^n，否则就不能保证两个相邻码元之间相差一位的条件，因此也就不是真正的各雷码了。第二就是使用冗余的触发器，假设一个触发器发生亚稳态的概率为P，那么两个及联的触发器发生亚稳态的概率就为P的平方。但这回导致延时的增加。亚稳态的发生会使得FIFO出现错误，读/写时钟采样的地址指针会与真实的值之间不同，这就导致写入或读出的地址错误。由于考虑延时的作用，空/满标志的产生并不一定出现在FIFO真的空/满时才出现。可能FIFO还未空/满时就出现了空/满标志。这并没有什么不好，只要保证FIFO不出现overflow or underflow 就OK了。
很多关于FIFO的文章其实讨论的都是空/满标志的不同算法问题。
在Vijay A. Nebhrajani的《异步FIFO结构》一文中，作者提出了两个关于FIFO空/满标志的算法。
第一个算法：构造一个指针宽度为N+1，深度为2^N字节的FIFO（为便方比较将格雷码指针转换为二进制指针）。当指针的二进制码中最高位不一致而其它N位都相等时，FIFO为满（在Clifford E. Cummings的文章中以格雷码表示是前两位均不相同，而后两位LSB相同为满，这与换成二进制表示的MSB不同其他相同为满是一样的）。当指针完全相等时，FIFO为空。这也许不容易看出，举个例子说明一下：一个深度为8字节的FIFO怎样工作（使用已转换为二进制的指针）。FIFO_WIDTH=8，FIFO_DEPTH= 2^N = 8，N = 3，指针宽度为N+1=4。起初rd_ptr_bin和wr_ptr_bin均为“0000”。此时FIFO中写入8个字节的数据。wr_ptr_bin =“1000”，rd_ptr_bin=“0000”。当然，这就是满条件。现在，假设执行了8次的读操作，使得rd_ptr_bin =“1000”，这就是空条件。另外的8次写操作将使wr_ptr_bin 等于“0000”，但rd_ptr_bin 仍然等于“1000”，因此FIFO为满条件。
显然起始指针无需为“0000”。假设它为“0100”，并且FIFO为空，那么8个字节会使wr_ptr_bin =“1100”，, rd_ptr_bin 仍然为“0100”。这又说明FIFO为满。
在Vijay A. Nebhrajani的这篇《异步FIFO结构》文章中说明了怎样运用格雷码来设置空满的条件，但没有说清为什么深度为8的FIFO其读写指针要用3+1位的格雷码来实现，而3+1位的格雷码可以表示16位的深度，而真实的FIFO只有8位，这是怎么回事？而这个问题在Clifford E. Cummings的文章中得以解释。三位格雷码可表示8位的深度，若在加一位最为MSB，则这一位加其他三位组成的格雷码并不代表新的地址，也就是说格雷码的0100表示表示7，而1100仍然表示7，只不过格雷码在经过一个以0位MSB的循环后进入一个以1为MSB的循环，然后又进入一个以0位MSB的循环，其他的三位码仍然是格雷码，但这就带来一个问题，在0100的循环完成后，进入1000，他们之间有两位发生了变换，而不是1位，所以增加一位MSB的做法使得该码在两处：0100~1000，1100~0000有两位码元发生变化，故该码以不是真正的格雷码。增加的MSB是为了实现空满标志的计算。Vijay A. Nebhrajani的文章用格雷码转二进制，再转格雷码的情况下提出空满条件，仅过两次转换，而Clifford E. Cummings的文章中直接在格雷码条件下得出空满条件。其实二者是一样的，只是实现方式不同罢了。

第二种算法：Clifford E. Cummings的文章中提到的STYLE. #2。它将FIFO地址分成了4部分，每部分分别用高两位的MSB 00 、01、 11、 10决定FIFO是否为going full 或going empty (即将满或空)。如果写指针的高两位MSB小于读指针的高两位MSB则FIFO为“几乎满”，

若写指针的高两位MSB大于读指针的高两位MSB则FIFO为“几乎空”。

在Vijay A. Nebhrajani的《异步FIFO结构》第三部分的文章中也提到了一种方法，那就是方向标志与门限。设定了FIFO容量的75%作为上限，设定FIFO容量的25%为下限。当方向标志超过门限便输出满/空标志，这与Clifford E. Cummings的文章中提到的STYLE. #2可谓是异曲同工。他们都属于保守的空满判断。其实这时输出空满标志FIFO并不一定真的空/满。
说到此，我们已经清楚地看到，FIFO设计最关键的就是产生空/满标志的算法的不同产生了不同的FIFO。但无论是精确的空满还是保守的空满都是为了保证FIFO工作的可靠。

6．关于FIFO的一点的思考

关于FIFO丢数据的问题，其实各位对同一个问题的理解有偏差，才造成了相互误解。如果在理想状况下（时钟同步不回出现错码），FIFO由读写指针控制是不会丢数的，（这不是废话吗，现实中哪来的理想状况！）且慢，我的意思是说丢数据并不是读写谁快谁慢造成的，在正确的设置空满标志算法的情况下，数据的overflow 和underflow 是不会发生的。而往往现实中因为亚稳态的存在，才出现了丢数的情况，也就是说是只要读写时钟不同步，在采样的过程中采样出错，使得本该是0100的变成了1101等等，就会出现读写的错误，我们称其为丢数，其原因就是在时钟同步指针的时候出现亚稳态，由于二进制码加1的时候很多位同时变化，所以很容易出现亚稳态。因此才用格雷码将此问题发生的概率比降到最小，其次用多余的触发器使其概率进一步降低，也就是说错误难免，但我们可以将其发生的概率降到最低，并且在出现错误时也不会错的态离谱（详见Vijay A. Nebhrajani的《异步FIFO结构》第二篇）。
二进制码指针并非不好用，在前面也提到了它有自身的优势，由于通过设置握手信号，指针可以有多位同时变化，二进制指针每次移动可以跳跃过任意的长度，这样给FIFO的某些功能的实现带来了方便(例如，硬件直接控制FIFO从缓存的数据流中丢弃一个出错的包)；而格雷码指针一般只能做递增或递减的移动。设置握手信号虽然可以保证指针不出错，但这样你来我往的经过三四个回合才能开始传数据，所以对于高速的场合就不适用了。

以上是我的学习FIFO的一些体会，文中很多观点和理解主要来自Vijay A. Nebhrajani的《异步FIFO结构》和Clifford E. Cummings的《Simulation and Synthesis Techniques for Asynchronous FIFO design》和《Simulation and Synthesis Techniques for Asynchronous
FIFO Design with Asynchronous Pointer Comparisons》以及网上的有关FIFO的一些文章看过前两篇文章的同学可能更容易理解我所说的问题，没有看过的也许会觉得我说的不知所云。了解FIFO的工作原理是每个数字设计者应该掌握i的，但在实际应用中还是推荐大家使用EDA软件提供的FIFO模块，他们都是经过验证的，不会有什么问题。

******************************************************************************

在现代IC设计中，特别是在模块与外围芯片的通信设计中，多时钟域的情况不可避免。当数据从一个时钟域传递到另一个域，并且目标时钟域与源时钟域不相关时，这些域中的动作是不相关的，从而消除了同步操作的可能性，并使系统重复地进入亚稳定状态[1]。在有大量的数据需要进行跨时钟域传输且对数据传输速度要求比较高的场合，异步 FIFO是一种简单、快捷的解决方案。

　　异步 FIFO用一种时钟写入数据，而用另外一种时钟读出数据。读写指针的变化动作由不同的时钟产生。因此，对FIFO空或满的判断是跨时钟域的。如何根据异步的指针信号产生正确的空、满标志，是异步 FIFO设计成败的关键。本文提出一种新颖的异步 FIFO设计方案，它通过先比较读写地址并结合象限检测法产生异步的空/满标志，再把异步的空/满标志同步到相应的时钟域。通过仿真验证，该方法是稳定有效的。

　　1异步信号传输问题的分析

　　在一个ASIC或FPGA库中，每种触发器都有时序要求。对于使用上升沿触发的触发器来说，建立时间(Setup Time)是在时钟上升沿到来之前，触发器数据保持稳定的最小时间；而保持时间(Hold Time)是在时钟上升沿到来之后，触发器数据还应该保持的最小时间[2]。如图1所示，在时钟上升沿前后的这个窗口内数据应该保持不变，否则会使触发器工作在一个不确定的状态，即亚稳态。当触发器处于亚稳态，且处于亚稳态的时间超过了一个时钟周期时，这种不确定的状态将会影响到下一级的触发器，最终导致连锁反应，从而使整个系统功能失常。当一个信号跨越某个时钟域时，对新时钟域的电路来说它就是一个异步信号。由于异步信号之间的时序是毫无关系的，因此必然存在Setup Time/Hold Time冲突。为了避免亚稳态问题，采用如图2所示的双锁存器法[3]，即在一个信号进入另一个时钟域前，将该信号用两个锁存器连续锁存两次，最后得到的采样结果就可以消除亚稳态。

　　消除亚稳态只是保证了信号电平的稳定，要在不同时钟域中准确传输数据还需要一个接口电路。异步 FIFO就是一种不同时钟域之间传递多位数据的常用方法。

　　2异步 FIFO设计

　　异步 FIFO是一种先进先出电路，用在需要实时数据接口的部分，用来存储、缓冲在两个异步时钟之间的数据传输。主要由双口存储器、读地址产生逻辑、写地址产生逻辑、空/满标志产生逻辑四部分构成。图3是一种常用的异步 FIFO设计方案，其中，读地址(rptr)和空标志(rempty)由读时钟 (rclk)产生，而写地址(wptr)和满标志(wfull)由写时钟(wclk)产生。把写地址与读地址相互比较以产生空/满标志。由于读写地址的变化由不同的时钟产生，所以对FIFO空或满的判断是跨时钟域的。如何避免异步传输带来的亚稳态以及正确地产生空/满标志是设计异步 FIFO的难点。

　　2.1 读写地址产生逻辑

　　读写地址线一般有多位，如果在不同的时钟域内直接同步二进制码的地址指针，则有可能产生亚稳态。例如，读指针从011变化到100时，所有位都要变化，读指针的每一位在读时钟的作用下，跳变不一致，即产生毛刺。如果写时钟恰好在读指针的变化时刻采样，得到的采样信号可能是000～111中的任何一个，从而导致空/满信号判断错误。由实践可知，同步多个异步输入信号出现亚稳态的概率远远大于同步一个异步信号的概率[3]。解决这一问题的有效方法是采用格雷码。格雷码的主要特点是相邻的两个编码之间只有一位变化。图4是格雷码产生的逻辑框图。在读使能或写使能信号有效、并且空/满标志无效的情况下，读写指针开始累加，进行FIFO读或写操作。二进制码与格雷码的转换是一个“异或”运算：gnext=(bnext>>1)^bnext。格雷码gnext 经寄存器输出格雷码指针ptr。这种方法采用了两组寄存器，虽然面积较大，但是有助于提高系统的工作频率。

　　2.2 空/满标志产生逻辑

　　正确地产生空/满标志是设计任何类型FIFO的关键点。空/满标志产生的原则是：写满而不溢出，能读空而不多读。传统的异步 FIFO把读写地址信号同步后再进行同步比较以产生空满标志，由于读写地址的每一位都需要两级同步电路，大量使用寄存器必然要占用很大的面积。这种方法不适合设计大容量的FIFO。当读、写指针相等也就是指向同一个内存位置时，FIFO可能处于满或空两种状态，必须区分FIFO是处于空状态还是满状态。传统的做法是把读、写地址寄存器扩展一位，最高位设为状态位，其余低位作为地址位。当读写指针的地址位和状态位全部吻合时，FIFO处于空状态；当读写指针的地址位相同而状态位相反时，FIFO处于满状态。传统的异步 FIFO工作频率低、面积大。下面将介绍一种产生空/满标志的新方法。

通过异步比较读写指针ptr以及读写指针的最高两位进行判断，产生两个异步的空/满标志信号(aempty/afull)送入读写模块进行同步，最后向外部输出两个同步的空/满信号(rempty/wfull)。空/满信号的产生过程：如图5所示，对于深度是2n的异步 FIFO，按照其读指针rptr[n:0]和写指针wptr[n:0]最高两位的不同取值，可把地址空间分为四个像限[4]。当写指针比读指针落后一个像限时，意味着写指针即将从后面追上读指针，FIFO处于“可能将满”状态，在图6所示的空满信号产生逻辑框图中声明一个 direction信号并把它置为1；当读写指针完全相等并且direction为1时，则FIFO处于满状态并且把满信号afull置为0(低电平有效)；当读指针比写指针落后一个像限时，意味着读指针即将追上写指针，FIFO处于“可能将空”状态，或者当写操作复位信号wrst有效时，再进行读操作，则FIFO也处于“可能将空”状态，此时把direction信号置为0；当读写指针完全相等并且direction为0时，则FIFO处于空状态，空标志信号aempty置为0。

　　读写地址异步相比较产生低电平有效的空/满标志，其中异步满信号(afull)要同步到写时钟域 (wclk)，异步空信号(aempty)要同步到读时钟域(rclk)，以消除亚稳态的影响，并向外界输出同步的空/满信号。下面以满信号 (wfull)为例说明同步信号的产生过程：满信号afull是因为写地址追上了读地址并比读地址多循环一次所产生，此时不能再向FIFO中写入数据，否则会造成FIFO写溢出。由于写地址(wptr)的变化产生FIFO满标志afull，即afull的下降沿与wptr同属于写时钟域。当读地址增加时，表明已经从FIFO中读走了一个数据，afull由有效的低电平变为无效的高电平，即afull的上升沿与rptr同属于读时钟域。可见，afull由高变低与写时钟(wclk)同步，而由低变高则与读时钟(rclk)同步。由于满标志afull只影响FIFO的写入，故将其同步到写时钟域。如图6所示，采用双锁存器法将afull过渡到写时钟域，最后得到的满信号wfull就属于写时钟域。同理可以得到空标志信号rempty。用Verilog代码实现如下：
　　wire dirset=~((wptr[n]^rptr[n-1]) & ~(wptr[n-1]^rptr[n]));
　　wire dirrst=~((~(wptr[n]^rptr[n-1]) & (wptr[n-1]^rptr[n])) |~wrst);
　　always @(posedge high or negedge dirset or negedge dirrst)
　　if (!dirrst) direction <= 1′b0;
　　else if (!dirset) direction <= 1′b1;
　　else direction <= high;
　　assign aempty=~((wptr==rptr) && !direction);
　　assign afull=~((wptr==rptr) && direction);
　　always @(posedge rclk or negedge aempty)
　　if (!aempty) {rempty,rempty2} <= 2′b11;
　　else {rempty,rempty2} <= {rempty2,~aempty};
　　always @(posedge wclk or negedge afull)
　　if (!afull) {wfull,wfull2} <= 2′b11;
　　else {wfull,wfull2} <= {wfull2,~afull };

　　异步比较法的关键是用异步比较结果的信号的下降沿作为最终比较结果的复位信号，而其上升沿则用传统的双锁存器法进行同步[5]。最终得到的信号的上升沿与下降沿都属于同一个时钟域。与传统的先将地址信号同步再进行同步比较的方法相比，异步比较法避免了使用大量的同步寄存器，而效率则更高，实现也更简单。

　　2.3 保守的空/满标志

　　设计中FIFO空/满标志的设置是保守的，即FIFO空/满标志的置位是立即有效的，而其失效则是在一段时间之后。例如一旦读指针追上写指针，就会立即声明一个低电平有效的异步空信号aempty。此信号会立即把图6所示的set触发器置位，使触发器输出为1，即向外部输出同步的空信号rempty，并且保证了FIFO一旦为空，读指针就不增加，避免了FIFO的读溢出。当写地址增加时，表明FIFO已经非空，空标志aempty由低变高，此时可以进行安全的读操作。aempty信号的失效与写时钟同步。空信号rempty是在读时钟域中同步aempty信号得到的。由于同步器使用了两个触发器，因此空信号rempty的失效要经过至少两个时钟周期的延迟。所以，空信号的声明是及时的，而空信号的失效是保守的。也就是说，虽然FIFO已经非空了，但是空信号rempty要经过几个周期的延迟才能变为无效。满信号也有类似的情况。

　　虽然空/满标志的设置是保守的，但这并不影响FIFO功能的正确性,经验证保守的空/满标志能够满足FIFO的设计要求。

　　3 仿真验证和综合

　　根据以上分析，以深度为16、数据宽度为8位的异步 FIFO为例，用VerilogHDL编写了各个模块，并采用Synopsys公司的仿真工具VCS进行了仿真验证。设写时钟(wclk)周期为100MHz,读时钟(rclk)周期为 133MHz，FIFO写、读时序仿真结果分别如图7、图8所示。当FIFO写满时，满标志wfull马上由0变1，禁止写数据并且写地址也不再增加，FIFO只读不写；当FIFO读空时，空标志rempty马上由0变1，禁止读数据并且读地址也不再增加，FIFO只写不读。空/满信号的变化情况满足设计要求。

　　仿真验证通过后，采用Synopsys公司的Design Compiler工具进行综合。把采用异步比较法设计的FIFO与传统的先将地址信号同步再进行比较设计的FIFO相比较，在中芯国际0.35μm库上 DC综合结果如表1所示。可见相对于传统的异步 FIFO，改进后的异步 FIFO电路速度快、面积小，从而降低了功耗，提高了系统的稳定性。

　　为了解决数据在不同时钟域间传递所产生的亚稳态问题，本文讨论了一种新颖的异步 FIFO设计方案。采用VerilogHDL以及由顶向下的模块设计方法实现了这种方案。经验证该方案能安全地实现数据跨时钟域的传递，并且性能比传统方案有了明显的改善。

******************************************************************************

同步FIFO的Verilog代码

上一篇 / 下一篇 2009-10-25 22:39:06 / 个人分类：FPGA设计基础知识

查看( 660 ) / 评论( 3 ) / 评分( 0 / 0 )

http://www.edabc.net/blog/?uid-20-action-viewspace-itemid-584

http://www.edabc.net/blog/?uid-26-action-viewspace-itemid-602

/******************************************************
          Acontrollerdescription.
******************************************************/
module fifo_syn(datain,
                     rd,
                     wr,
                    rst,
                    clk,
                dataout,
                   full,
                   empty);

input [7:0] datain;
input rd, wr, rst, clk;
output [7:0] dataout;
output full, empty;

reg [7:0] dataout;
reg full_in, empty_in;
reg [7:0] mem [15:0];
reg [3:0] rp, wp;

assign full = full_in;
assign empty = empty_in;
// memory read out         稍作修改
   always@(posedge clk) begin
    if(rd && ~empty_in) dataout = mem[rp];
end

// memory write in
always@(posedge clk) begin
if(wr && ~full_in) mem[wp]<=datain;
end

// memory write pointer increment
always@(posedge clk or negedge rst)
    if(!rst)
        wp<=0;
    else   wp <= (wr && ~full_in) ? (wp + 1'b1) : wp;
// memory read pointer increment
always@(posedge clk or negedge rst)
    if(!rst)
       rp <= 0;
    else rp <= (rd && ~empty_in)? (rp + 1'b1): rp;

// Full signal generate
always@(posedge clk or negedge rst) begin
    if(!rst) full_in <= 1'b0;
    else begin
      if( (~rd && wr)&&((wp==rp-1)||(rp==4'h0&&wp==4'hf)))
          full_in <= 1'b1;
      else if(full_in && rd) full_in <= 1'b0;
    end
end

// Empty signal generate
always@(posedge clk or negedge rst) begin
    if(!rst) empty_in <= 1'b1;
    else begin
      if((rd&&~wr)&&(rp==wp-1 || (rp==4'hf&&wp==4'h0)))
        empty_in<=1'b1;
      else if(empty_in && wr) empty_in<=1'b0;
    end
end
endmodule

*******************************************************************************

网上的读数据输出(dataout)部分不受读使能(rd)控制，显然不对，所以稍作修改，欢迎批评

**************************************************************************************

另一种风格的同步FIFO

module FIFO_Buffer(
Data_out,
stack_full,
stack_almost_full,
stack_half_full,
stack_almost_empty,
stack_empty,
Data_in,
write_to_stack,
read_from_stack,
clk,rst
);
parameter stack_width=32;
parameter stack_height=8;
parameter stack_ptr_width=3;
parameter AE_level=2;
parameter AF_level=6;
parameter HF_level=4;
output [stack_width-1:0] Data_out;

output                 stack_full,stack_almost_full,stack_half_full;
output                 stack_almost_empty,stack_empty;
input[stack_width-1:0] Data_in;
input                  write_to_stack,read_from_stack;
input                  clk,rst;

reg[stack_ptr_width-1:0] read_ptr,write_ptr;

reg[stack_ptr_width:0]   ptr_gap;
reg[stack_width-1:0]     Data_out;
reg[stack_width-1:0]     stack[stack_height-1:0];

assign stack_full=(ptr_gap==stack_height);
assign stack_almost_full=(ptr_gap==AF_level);
assign stack_half_full=(ptr_gap==HF_level);
assign stack_almost_empty=(ptr_gap==AE_level);
assign stack_empty=(ptr_gap==0);

always @(posedge clk or posedge rst)
   if(rst)begin
       Data_out<=0;
       read_ptr<=0;
       write_ptr<=0;
       ptr_gap<=0;
   end
   else if(write_to_stack &&(!stack_full)&&(!read_from_stack))begin
       stack[write_ptr]<=Data_in;
       write_ptr<=write_ptr+1;
       ptr_gap<=ptr_gap+1;
   end
   else if((!write_to_stack)&&(!stack_empty)&&read_from_stack)begin
       Data_out<=stack[read_ptr];
       read_ptr<=read_ptr+1;
       ptr_gap<=ptr_gap-1;
   end
   else if(write_to_stack &&read_from_stack&&stack_empty)begin
       stack[write_ptr]<=Data_in;
       write_ptr<=write_ptr+1;
       ptr_gap<=ptr_gap+1;
   end
   else if(write_to_stack &&read_from_stack&&stack_full)begin
       Data_out<=stack[read_ptr];
       read_ptr<=read_ptr+1;
       ptr_gap<=ptr_gap-1;
   end
   else if(write_to_stack&&read_from_stack&&(!stack_full)&&(!stack_empty))
   begin
       Data_out<=stack[read_ptr];
       stack[write_ptr]<=Data_in;
       read_ptr<=read_ptr+1;
       write_ptr<=write_ptr+1;
   end
endmodule