電子發(fā)燒友App
1. 為什么需要FIFO
FIFO 是First-In First-Out的縮寫(xiě)，它是一個(gè)具有先入先出特點(diǎn)的緩沖區(qū)。
可以理解成一個(gè)大的水池，水對(duì)應(yīng)數(shù)據(jù)，注水速度對(duì)應(yīng)數(shù)據(jù)輸入的頻率，放水速度對(duì)應(yīng)數(shù)據(jù)處理的速度，當(dāng)注水速度和放水速度相同時(shí)，我們不需要使用水池來(lái)緩沖，但是當(dāng)注水速度大于放水速度，或者注水速度突然變大時(shí)（突發(fā)），為了保證水池不溢出（數(shù)據(jù)不丟失），就需要水池（緩沖區(qū)）來(lái)處理這種突發(fā)情況，并設(shè)置合理大小的水池空間（FIFO的深度）。
或者為了降低CPU負(fù)擔(dān)，提高數(shù)據(jù)處理效率，可以在積累到一定的數(shù)據(jù)量之后，再一次性處理。
在FPGA中，F(xiàn)IFO一般是使用RAM存儲(chǔ)器作為緩沖區(qū)，可以分為同步FIFO或異步FIO，一般用于數(shù)據(jù)緩沖，或者不同時(shí)鐘域之間的數(shù)據(jù)傳遞。
在單片機(jī)中，一般是基于一維數(shù)組和結(jié)構(gòu)體實(shí)現(xiàn)的循環(huán)隊(duì)列（Queue），或者叫環(huán)形隊(duì)列。
FIFO的使用，既可以保證數(shù)據(jù)的完整性，還可以讓數(shù)據(jù)被及時(shí)的處理。
本文介紹，基于C語(yǔ)言的循環(huán)隊(duì)列緩沖區(qū)原理、設(shè)計(jì)與實(shí)現(xiàn)。
2. FIFO的存取順序
定義一個(gè)一維數(shù)組當(dāng)作存儲(chǔ)區(qū)，數(shù)組長(zhǎng)度為6，再定義兩個(gè)讀寫(xiě)指針變量。
初始化時(shí)，F(xiàn)IFO為空，讀寫(xiě)指針相等，并都置為0。
寫(xiě)入一個(gè)數(shù)據(jù)1之后，寫(xiě)指針遞增，讀指針不變：
再寫(xiě)兩個(gè)數(shù)據(jù)2和3，寫(xiě)指針遞增，讀指針不變：
寫(xiě)了三個(gè)數(shù)據(jù)之后，我們讀出一個(gè)數(shù)據(jù)1，寫(xiě)指針不變，讀指針遞增：
讀出一個(gè)數(shù)據(jù)2，再寫(xiě)兩個(gè)數(shù)據(jù)4和5，讀寫(xiě)指針變化：
再寫(xiě)一個(gè)數(shù)據(jù)6，此時(shí)超過(guò)數(shù)組長(zhǎng)度，但是數(shù)組頭部還有空間，所以寫(xiě)指針回到數(shù)組起始地址0：
再寫(xiě)一個(gè)數(shù)據(jù)7，此時(shí)判斷FIFO滿(mǎn)：
可能會(huì)有朋友疑惑，不是還有一個(gè)空位置可以存放數(shù)據(jù)嗎？
如果再存入一個(gè)數(shù)據(jù)之后，讀寫(xiě)指針相等，此時(shí)可以判斷是滿(mǎn)狀態(tài)嗎？
顯然是不能，因?yàn)楫?dāng)FIFO為空時(shí)，也是讀寫(xiě)指針相等，所以這種情況就無(wú)法判斷滿(mǎn)和空。
這里就涉及到FIFO設(shè)計(jì)中，最重要的滿(mǎn)和空的判斷條件，需要遵循FIFO讀寫(xiě)的兩個(gè)規(guī)則：
FIFO為空時(shí)，不能執(zhí)行讀操作
FIFO為滿(mǎn)時(shí)，不能執(zhí)行寫(xiě)操作
為了避免這種情況發(fā)生，我們空出一個(gè)元素位置，寫(xiě)指針指向的位置永遠(yuǎn)為空，這樣就會(huì)有兩種滿(mǎn)的情況：
rd < wr
rd > wr
對(duì)于第一種情況，當(dāng)(wr + 1) % FIFO_SIZE == rd時(shí)，可以認(rèn)為FIFO滿(mǎn)，F(xiàn)IFO_SIZE是指數(shù)組長(zhǎng)度；
對(duì)于第二種情況，當(dāng)wr + 1 == rd時(shí)，可以認(rèn)為FIFO滿(mǎn)。
以上兩種情況可以合并為一種，即(wr + 1) % FIFO_SIZE == rd時(shí)，判斷FIFO滿(mǎn)。
所以這種判斷方式，會(huì)犧牲一個(gè)存儲(chǔ)位置，實(shí)際可以存儲(chǔ)的元素個(gè)數(shù)為FIFO_SIZE-1。
同理，獲取當(dāng)前FIFO內(nèi)元素的個(gè)數(shù)，也可以分為兩種情況：
當(dāng)wr > rd時(shí)， count = wr - rd
當(dāng)wr < rd時(shí)，count = wr + FIFO_SIZE - rd
3. FIFO的代碼實(shí)現(xiàn)
根據(jù)以上FIFO存取邏輯，我們可以使用一維數(shù)組來(lái)構(gòu)造一個(gè)環(huán)形緩沖區(qū)，讀寫(xiě)地址循環(huán)遞增，分別實(shí)現(xiàn)FIFO初始化、讀寫(xiě)操作、判斷空滿(mǎn)、獲取元素個(gè)數(shù)等函數(shù)，并封裝成模塊。
xqueue.h
?
?
?
?
/* ?*?Copyright(C),?2010-2023,?CSDN?@?whik1194 ?*?Time???????:?2023年4月9日 ?*?Author?????:?https://blog.csdn.net/whik1194 ?*?GitHub?????:?https://gitee.com/whik/xqueue ?*/ #ifndef?__XQUEUE_H__ #define?__XQUEUE_H__ #include?"stdint.h" /*?FIFO數(shù)據(jù)的類(lèi)型，可以是結(jié)構(gòu)體類(lèi)型?*/ #define?qdata_t?uint8_t /*?FIFO長(zhǎng)度，實(shí)際存放的數(shù)據(jù)=FIFO_SIZE-1?*/ #define?FIFO_SIZE?6 typedef?enum?{ ????QUEUE_OK, ????QUEUE_FULL, ????QUEUE_EMPTY }qstatus_t; typedef?struct?{ ????uint16_t?addr_wr;????????/*?寫(xiě)地址?*/ ????uint16_t?addr_rd;????????/*?讀地址?*/ ????uint16_t?length;?????????/*?FIFO長(zhǎng)度，實(shí)際存放的數(shù)據(jù)=length-1?*/ ????qdata_t?fifo[FIFO_SIZE]; }queue_t; qstatus_t?queue_reset(queue_t?*q); qstatus_t?queue_read(queue_t?*q,?qdata_t?*pdata); qstatus_t?queue_write(queue_t?*q,?qdata_t?data); int?queue_isFull(queue_t?*q); int?queue_isEmpty(queue_t?*q); int?queue_print(queue_t?*q); #endif
xqueue.c文件
/* ?*?Copyright(C),?2010-2023,?CSDN?@?whik1194 ?*?Time????
???:?2023年4月9日 ?*?Author????
?:?https://blog.csdn.net/whik1194 ?*?GitHub????
?:?https://gitee.com/whik/xqueue ?*/ #include?"xqueue.h" #include?"stdio.h" /*?FIFO復(fù)位?*/ qstatus_t?queue_reset(queue_t?*q) { ???
?int?i?=?0; ????q->addr_wr?=?0; ????
q->addr_rd?=?0; ??
??q->length?=?FIFO_SIZE; ????for(i?=?0;?i?length;?i++)
????????q->fifo[i]?=?0;
????return?QUEUE_OK; } /*?FIFO寫(xiě)入數(shù)據(jù)?*/ qstatus_t?queue_write(queue_t?*q,?qdata_t?data) { ??
??if(queue_isFull(q)) ????{ ????????
printf("Write?failed(%d),?queue?is?full ",?data); ?
???????return?QUEUE_FULL; ??
??} ????q->fifo[q->addr_wr]?=?data; ????q->addr_wr?=?(q->addr_wr?+?1)?%?q->length; ??
??printf("write?success:?%02d ",?data); ????
queue_print(q); ?
???return?QUEUE_OK; } /*?FIFO讀出數(shù)據(jù)?*/ qstatus_t?queue_read(queue_t?*q,?qdata_t?*pdata) { ??
??if(queue_isEmpty(q)) ????{ ????
????printf("Read?failed,?queue?is?empty "); ????
????return?QUEUE_EMPTY; ??
??} ????*pdata?=?q->fifo[q->addr_rd]; ????q->addr_rd?=?(q->addr_rd?+?1)?%?q->length; ????printf("read?success:?%02d ",?*pdata); ??
??queue_print(q); ????return?QUEUE_OK; } /*?FIFO是否為空?*/ int?queue_isEmpty(queue_t?*q) {
????return?(q->addr_wr?==?q->addr_rd); } /*?FIFO是否為滿(mǎn)?*/ int?queue_isFull(queue_t?*q) { ??
??return?((q->addr_wr?+?1)?%?q->length?==?q->addr_rd); } /*?FIFO內(nèi)數(shù)據(jù)的個(gè)數(shù)?*/ int?queue_count(queue_t?*q) {
????if(q->addr_rd?<=?q->addr_wr) ???
?????return?(q->addr_wr?-?q->addr_rd); ????//addr_rd?>?addr_wr; ?
???return?(q->length?+?q->addr_wr?-?q->addr_rd); } /*?打印當(dāng)前FIFO內(nèi)的數(shù)據(jù)和讀寫(xiě)指針的位置?*/ int?queue_print(queue_t?*q) { ?
???int?i?=?0; ????int?j?=?0; ????for(i?=?0;?i?addr_rd;?i++) ?????
???printf("?????"); ????printf("rd=%d",?q->a
ddr_rd); ????printf(" "); ?
???for(i?=?0;?i?length;?i++) ????{ ????????if(q->addr_wr?>?q->addr_rd) ?????
???{ ????????????if(i?>=?q->addr_rd?&&?i?addr_wr) ??????????
??????printf("[%02d]?",?q->fifo[i]); ????????????else ?????????????
???printf("[??]?"); ????????} ???
?????else//addr_rd?>?addr_wr ?????
???{ ????????????if(i?addr_wr?||?i?>=?q->addr_rd) ????
???
?????????printf("[%02d]?",?q->fifo[i]); ?????
???????else ????????????????printf("[??]?"); ??????
??} ????} ????printf("------count?=?%d ",?queue_count(q)); ???
?for(i?=?0;?i?addr_wr;?i++) ???????
?printf("?????"); ????printf("wr=%d",?q->addr_wr); ??
??printf(" "); ????return?QUEUE_OK; }
實(shí)際應(yīng)用：
/* ?*?Copyright(C),?2010-2023,?CSDN?@?whik1194 ?*?Time?????
??:?2023年4月9日 ?*?Author?????:?https://blog.csdn.net/whik1194 ?*?GitHub?????:?https://github.com/whik/xqueue ?*/ #include?
#include? #include?"xqueue.h" int?main(int?argc,?char?*argv[]) { ??
??queue_t?queue; ????qdata_t?data; ?
???queue_reset(&queue);
????queue_write(&queue,?1); ???
?queue_write(&queue,?2); ???
?queue_write(&queue,?3); ????
queue_read(&queue,?&data);
????queue_read(&queue,?&data); ??
??queue_write(&queue,?4); ?
???queue_write(&queue,?5); ?
???queue_write(&queue,?6); ???
?queue_write(&queue,?7); ??
??queue_read(&queue,?&data); ?
???queue_read(&queue,?&data); ??
??queue_read(&queue,?&data); ???
?queue_write(&queue,?8); ????
queue_write(&queue,?9); ??
??queue_write(&queue,?10);
????queue_read(&queue,?&data);
????system("pause"); ????return?0; }
運(yùn)行結(jié)果:
循環(huán)隊(duì)列元素的數(shù)據(jù)類(lèi)型，可以根據(jù)需要指定，也可以是結(jié)構(gòu)體類(lèi)型。
編輯：黃飛
?
工商網(wǎng)監(jiān)
評(píng)論