Verilog实现常见数据结构计划（二）栈

姓名：徐铭伟   学号：21011210001   学院：通信工程学院

【嵌牛导读】使用Verilog实现硬件堆栈

【嵌牛鼻子】硬件堆栈的Verilog实现

【嵌牛提问】如何使用Verilog实现硬件堆栈

【嵌牛正文】

文章目录

一、栈的 C 语言实现

                1.1 顺序栈的结构定义

                1.2 顺序栈的初始化

                1.3 顺序栈的写入

                1.4 顺序栈的读出

二、栈的 Verilog 实现

                2.1 Verilog 实现代码

                2.2 仿真测试

一、栈的 C 语言实现

1.1  顺序栈的数据结构定义

data为栈中每个元素的数据值；top为栈顶的指针，在计算机体系中也称作sp 指针。

/* 数据结构定义 */

typedef struct

{

    int data[MAXSIZE];  // 栈数据空间

    int top;            // 栈顶指针

}SqStack;  // 顺序栈

1.2 顺序栈的初始化

在栈中，我们定义sp 指针初始指向-1，表示这是一个空栈，而当 sp 指向 0 时则代表栈中存有一个数据。

// 栈初始化

void Stack_Init(SqStack *S)

{

    S->top = -1;

    for (unsigned int i = 0; i < MAXSIZE; i++)

        S->data[i] = 0;

}

1.4 顺序栈的读出

从栈中读出数据又称弹栈或出栈，在执行读数据操作之前需要判断栈是否已经读空，方法是当 sp 指针指回 -1 时认为栈已经读空。若栈未空，则先读出当前 sp 指针指向空间的数据，然后将 sp 指针自减，指向上一个存储单元。

// 弹栈操作

char Pop(SqStack *S, int *e)

{ 

    if( S->top == -1 )

    {

        return -1;          // 栈空

    }

    *e = S->data[S->top];  // 弹出的数据赋值给e

    S->top--;              // 栈顶自减

    return 1;

}

二、栈的 Verilog 实现

堆栈是现代计算机设备不可或缺的组成部分之一，局部变量、跳转语句、函数跳转的现场保存等，都需要使用堆栈（栈）来实现。目前主流的计算机及嵌入式处理器大都采用内存实现堆栈的方式，即在主存中开辟一块空间来保存堆栈数据。然而在一些低端嵌入式微控制器，例如 PIC 单片机中则会使用硬件堆栈，因为它们的内存不够大而且对堆栈大小的需求也不高。

基于上述的软件堆栈原理，本节使用 Verilog HDL 实现硬件同步堆栈并给出仿真测试。

2.1 Verilog 实现代码

以下为栈缓存的 verilog 实现代码。

① sp 指针在空栈时为 -1 （补码形式），并且约束其在栈顶和栈底的自增条件。

② 栈的判满和判空使用两个一段状态机实现。

③ 参数WRITE_GUARD可配置此栈缓存为写满保护或无写满保护模式。写满保护模式即是当栈满后，再将新数据压栈时不会将栈顶的旧数据冲刷掉。WRITE_GUARD = "ON"时打开写满保护、WRITE_GUARD = "OFF"时关闭写满保护。

//**********************************************

//COPYRIGHT(c)2021, XXX University

//All rights reserved.

//

//File name    : Sync_Stack.v

//Module name  : Sync_Stack

//Full name    :

//Author : XXX

//Email :

//

//Version :

//This File is  Created on 2021-09-24 13:27:27

//------------------Discription-----------------

//

//----------------------------------------------

//-------------Modification history-------------

//Last Modified by : XXX

//Last Modified time: 2021-09-24 13:27:27

//Discription :

//----------------------------------------------

//TIMESCALE

`timescale 1ns/1ns

//DEFINES

//`include ".v"

//----------------------------------------------

/*** 硬件堆栈 LIFO ***/

module Sync_Stack #(

parameter WRITE_GUARD =  "ON" , // 模式配置：“ON”开启栈顶写保护； “OFF”关闭写保护

parameter DATA_WIDTH = 32  , // 数据位宽

parameter STACK_WIDTH = 8   // log2(堆栈大小)

)

(

                input sclk , // 同步时钟

                input rst_n , // 低复位

                input wr_en , // 写使能

                input [DATA_WIDTH-1:0] din , // 写数据

                output reg full , // 写满标志

                input rd_en , // 读使能

                output reg [DATA_WIDTH-1:0] dout , // 读数据

                output reg empty // 读空标志

);

localparam STACK_DEPTH = 2**STACK_WIDTH;

reg [DATA_WIDTH-1:0] syc_ram [STACK_DEPTH-1:0]; // RAM

reg [STACK_WIDTH:0] sp; // SP指针

wire [STACK_WIDTH:0] index = $signed(sp) + 1; // ram元素索引

// RAM读写控制

generate

// 堆栈写满保护模式

if( WRITE_GUARD == "ON" ) begin

reg guard_flag; // 栈顶写满保护标志

always @(posedge sclk or negedge rst_n) begin : wr_rd

integer i;

if ( rst_n == 1'b0 ) begin

for( i=0; i<STACK_DEPTH; i=i+1 )

syc_ram[i] <= 'd0;

dout <= 'd0;

guard_flag <= 1'b0;

end

else begin

if( wr_en & rd_en ) begin

dout <= din;

guard_flag <= 1'b0;

end

else if( wr_en && (index < STACK_DEPTH) ) begin

if( index < (STACK_DEPTH - 1) ) begin

syc_ram[index] <= din;

end

else begin

if( guard_flag == 1'b0 ) begin

syc_ram[index] <= din;

guard_flag <= 1'b1;

end

end

end

else if( rd_en ) begin

dout <= syc_ram[index];

guard_flag <= 1'b0;

end

end

end

end

// 无写满保护模式

else begin

always @(posedge sclk or negedge rst_n) begin : wr_rd

integer i;

if ( rst_n == 1'b0 ) begin

for( i=0; i<STACK_DEPTH; i=i+1 )

syc_ram[i] <= 'd0;

dout <= 'd0;

end

else begin

if( wr_en & rd_en ) begin

dout <= din;

end

else if( wr_en && (index < STACK_DEPTH) ) begin

syc_ram[index] <= din;

end

else if( rd_en ) begin

dout <= syc_ram[index];

end

end

end

end

endgenerate

// SP指针控制

always @(posedge sclk or negedge rst_n) begin

if ( rst_n == 1'b0 ) begin

sp <= -1;

end

else begin

if( wr_en & rd_en ) begin

sp <= sp;

end

else if( wr_en && (index < STACK_DEPTH - 1) ) begin

sp <= sp + 1'b1;

end

else if( rd_en && (index > 'd0) ) begin

sp <= sp - 1'b1;

end

else begin

sp <= sp;

end

end

end

// 栈满判断状态机

reg full_state;

always @(posedge sclk or negedge rst_n) begin

if ( rst_n == 1'b0 ) begin

full_state <= 1'b0;

full  <= 1'b0;

end

else begin

case( full_state )

// 未满状态

1'b0 : begin

if( wr_en && (index == STACK_DEPTH - 1) ) begin

full  <= 1'b1;

full_state <= 1'b1;

end

else begin

full  <= 1'b0;

full_state <= 1'b0;

end

end

// 栈满状态

1'b1 : begin

if( rd_en ) begin

full  <= 1'b0;

full_state <= 1'b0;

end

else begin

full  <= 1'b1;

full_state <= 1'b1;

end

end

endcase

end

end

// 栈空判断状态机

reg empty_state;

always @(posedge sclk or negedge rst_n) begin

if ( rst_n == 1'b0 ) begin

empty_state <= 1'b1;

empty <= 1'b1;

end

else begin

case( empty_state )

// 未空状态

1'b0 : begin

if( rd_en && (index == 'd0) ) begin

empty  <= 1'b1;

empty_state <= 1'b1;

end

else begin

empty  <= 1'b0;

empty_state <= 1'b0;

end

end

// 栈空状态

1'b1 : begin

if( wr_en ) begin

empty  <= 1'b0;

empty_state <= 1'b0;

end

else begin

empty  <= 1'b1;

empty_state <= 1'b1;

end

end

endcase

end

end

endmodule

2.2 仿真测试

Testbench 代码如下所示。

//**********************************************

//COPYRIGHT(c)2021, XXX University

//All rights reserved.

//

//File name    : testbench.v

//Module name  : testbench

//Full name    :

//Author : XXX

//Email :

//

//Version :

//This File is  Created on 2021-09-24 13:27:08

//------------------Discription-----------------

//

//----------------------------------------------

//-------------Modification history-------------

//Last Modified by : XXX

//Last Modified time: 2021-09-24 13:27:08

//Discription :

//----------------------------------------------

//TIMESCALE

`timescale 1ns/1ns

//DEFINES

//`include ".v"

//----------------------------------------------

`define DATA_WIDTH 32

`define STACK_WIDTH 4

module testbench;

reg sclk  ;

reg rst_n  ;

reg wr_en  ;

reg [`DATA_WIDTH-1:0] din    ;

wire full  ;

reg rd_en  ;

wire [`DATA_WIDTH-1:0] dout  ;

wire empty  ;

// 生成时钟

initial begin

sclk = 0;

forever #5 sclk = ~sclk;

end

// Main

initial begin

rst_n = 0;

wr_en = 0;

din = 0;

rd_en = 0;

#50

rst_n = 1;

#50

repeat( 2**`STACK_WIDTH + 1 ) begin

@(posedge sclk) begin

wr_en <= 1'b1;

din  <= din + 1;

end

end

@(posedge sclk)

wr_en <= 1'b0;

repeat( 2**`STACK_WIDTH + 1 ) begin

@(posedge sclk) begin

rd_en <= 1'b1;

end

end

@(posedge sclk)

rd_en <= 1'b0;

#50

repeat( 2**`STACK_WIDTH/2 ) begin

@(posedge sclk) begin

wr_en <= 1'b1;

din  <= din + 1;

end

end

@(posedge sclk)

wr_en <= 1'b0;

#50

repeat( 2**`STACK_WIDTH/2 ) begin

@(posedge sclk) begin

wr_en <= 1'b1;

din  <= din + 1;

end

end

@(posedge sclk)

wr_en <= 1'b0;

repeat( 2**`STACK_WIDTH/2 ) begin

@(posedge sclk) begin

rd_en <= 1'b1;

end

end

@(posedge sclk)

rd_en <= 1'b0;

#50

repeat( 2**`STACK_WIDTH/2 ) begin

@(posedge sclk) begin

rd_en <= 1'b1;

end

end

@(posedge sclk)

rd_en <= 1'b0;

#100

$stop;

end

// 同步堆栈例化

Sync_Stack #(

.WRITE_GUARD("ON"),

.DATA_WIDTH (`DATA_WIDTH),

.STACK_WIDTH(`STACK_WIDTH)

) U_Sync_Stack (

.sclk  (sclk),

.rst_n (rst_n),

.wr_en (wr_en),

.din  (din),

.full  (full),

.rd_en (rd_en),

.dout  (dout),

.empty (empty)

);

endmodule

开启写满保护模式的栈缓存读写波形如下。测试中栈深度为 16 ，对其写 17 次，可见第 17 个数据“32’d17”并没有写入栈中。随后对其读 17 次，可以看到之前写入的数据都按 LIFO 顺序被读了出来。

关闭写满保护模式的波形如下。测试激励同上，可以看到读取时原来的数据 “32’d16” 的位置被 “32’d17” 覆盖了。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 199,340评论 5赞 467
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 83,762评论 2赞 376
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 146,329评论 0赞 329
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,678评论 1赞 270
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,583评论 5赞 359
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 47,995评论 1赞 275
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,493评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,145评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,293评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,250评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,267评论 1赞 328
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,973评论 3赞 316
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,556评论 3赞 303
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,648评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,873评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,257评论 2赞 345
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 41,809评论 2赞 339