有偿求助环形缓冲器用法—300RMB

发表于 2010-1-6 14:27

本帖最后由冷漠于 2010-1-7 08:57 编辑

请看下面链接：
https://bbs.21ic.com/icview-151866-1-1.html

谁能帮我证明一下，下面公式在生命期间是正确的：看看它是不是歪理？

mCount = pIn - pOut ； // 也就是说，pIn 总是大于 pOut 。mCount “ 永远”是正整数。

采用什么方法，能够使得在任何（合理范围）情况下，都保证上面计算公式是正确的？（合理，例如 char8 或者 int16 范围内。假定取缓冲区长度ILEN=16。）

所谓生命期间是指 pIn / pOut 的有限合理范围内，例如串口接收程序接收一帧限定255字节。 pIn / pOut 是什么类型无所谓的，并不限于所长的程序，谁能用自己的环形缓冲区处理程序证明更好。

发表于 2010-1-6 14:36

本来想看看这300RMB是个什么样的问题，结果：

指定的版块不存在，请返回。

[ 点击这里返回上一页 ]

发表于 2010-1-6 15:05

mCount = pIn - pOut

只有在缓存大小设置成256,2^16,2^32，并且强制类型转换成对应无符号数才可能成立

forrest11 · 发表于 2010-1-6 16:33

本帖最后由 lxyppc 于 2010-1-6 16:48 编辑

这个是我经常用的方式，对两个索引的改变分别需要一个自增(++)的操作，当RING_SIZE为2^n时，取余会被编译成一个&运算，mCount可以由两个索引的关系得到
缓冲满了之后就不能再向里面写数据，新来数据会丢失掉。也可以继续写，但是要同时更新pOut的位置

typedef unsigned char  Ele_t;
typedef unsigned int size_t;
typedef enum
{
  OK = 1,
  Empty = !OK,
  Full = !OK,
  Fail = !OK,
}Result_t;
#define RING_SIZE    19
Ele_t ringBuffer[RING_SIZE] = {0};

struct
{
Ele_t* pBuffer;
size_t pIn;
size_t pOut;
}Ring = {
.pIn = 0,
.pOut = 0,
.pBuffer = ringBuffer,
};

Result_t PushRing(Ele_t ele)
{
  if( (Ring.pIn%RING_SIZE) == (Ring.pOut%RING_SIZE) ){
if(Ring.pIn != Ring.pOut){
   return Full;
}
  }
  Ring.pBuffer[Ring.pIn%RING_SIZE] = ele;
  Ring.pIn++;
  return OK;
}

Result_t PopRing(Ele_t* ele)
{
  if( (Ring.pIn%RING_SIZE) == (Ring.pOut%RING_SIZE) ){
if(Ring.pIn == Ring.pOut){
   return Empty;
}
  }
  *ele = Ring.pBuffer[Ring.pOut%RING_SIZE];
  Ring.pOut++;
  return OK;
}

size_t GetRingCount()
{
  size_t size = (Ring.pIn - Ring.pOut) % RING_SIZE;
  if( (size == 0) && (Ring.pIn != Ring.pOut) ){
size = RING_SIZE;
  }
  return  size;
}

void PurgeRing()
{
  Ring.pIn = Ring.pOut = 0;
}

发表于 2010-1-6 20:56

本帖最后由冷漠于 2010-1-7 09:00 编辑

写的真棒。很少有人悟到这一点。没说的，300元拿走。（与我联系：lengmo1978@126.com ）
size_t GetRingCount()
{
  size_t size = (Ring.pIn - Ring.pOut) % RING_SIZE;
  if( (size == 0) && (Ring.pIn != Ring.pOut) ){
size = RING_SIZE;
  }
  return  size;
}

上面这一段能否改成：
size_t GetRingCount( )
{
size = Ring.pIn - Ring.pOut
return  size;
}
也即证明了mCount=pIn-pOut。

发表于 2010-1-6 23:33

呵呵，又开始打赌了？

俺不参赌，俺只围观

发表于 2010-1-7 00:56

哇

发表于 2010-1-7 08:53

4楼的不错，原来理解肤浅了

发表于 2010-1-7 09:29

写的真棒。很少有人悟到这一点。没说的，300元拿走。
上面这一段能否改成：
size_t GetRingCount( )
{
size = Ring.pIn - Ring.pOut
return size;
}
冷漠发表于 2010-1-6 20:56

要加几个限制条件：
1. typedef unsigned char size_t;
2. #define  RING_SIZE  1<<(sizeof(size_t)*8) //作此定义之后中间的取余操作就可以省略了
3. PushRing 改成先加再写入然后判断
// 此时如果缓冲指针已经到了最后一个位置，新来的数据会被压在此处，但是写入指针不会再增长，实际可用的缓冲大小为 (RING_SIZE-1)
Result_t PushRing(Ele_t ele)
{
  size_t pInTemp = Ring.pIn + 1;
  Ring.pBuffer[Ring.pIn] = ele;
  if( (pInTemp%RING_SIZE) == (Ring.pOut%RING_SIZE) ){
return Full;
  }
  Ring.pIn = pInTemp;
  return OK;
}

P.S. 300元我不要了，我只要版主能给个酷。哈哈

发表于 2010-1-7 09:33

size_t GetRingCount()
{
  //由于RING_SIZE等于1<<(sizeof(size_t)*8)，后面取余的操作可以省略
  //size_t size = (Ring.pIn - Ring.pOut) % RING_SIZE;
  return Ring.pIn - Ring.pOut;
  //由于PushRing中提前判断了pIn与pOut是否相等，因此size == 0不会出现，可以省略
  //if( (size == 0) && (Ring.pIn != Ring.pOut) ){
  //  size = RING_SIZE;
  //}
  //return  size;
}

发表于 2010-1-7 10:13

本帖最后由冷漠于 2010-1-7 10:16 编辑

高！思考过、做过的人就是不一样。

Result_t PushRing(Ele_t ele)
{
if( Ring.pOut + RING_SIZE == Ring.pIn )
return Full;

Ring.pBuffer[Ring.pIn++ % RING_SIZE] = ele;
return OK;
}

对吗？

发表于 2010-1-7 10:18

RING_SIZE 为2^n 时 % 可以优化成 ( &(RING_SIZE-1))

发表于 2010-1-7 10:23

8位机中读写Ring.pOut也是要互斥保护的，中断可能在读一半的时候改写。

发表于 2010-1-7 10:24

本帖最后由冷漠于 2010-1-7 13:33 编辑

12楼正解。所以设 RING_SIZE=16. 可以减化%计算代码。

发表于 2010-1-7 10:26

那和农民用的count有什么区别？而且指针可能是16位的？

发表于 2010-1-7 10:37

看我以前写过的关于用队列来实现SCI的例子，有完整的程序供可以参考。

发表于 2010-1-7 10:40

互个鬼斥保护。

收发各建一环队，各队的插入和提取在其头尾操作。要碰头，不是空了就是满了，只要有空满标志即可，不会打架地。

发表于 2010-1-7 11:04

本帖最后由 arm_fan168 于 2010-1-7 11:07 编辑

当RING_SIZE为2^n时，取余会被编译成一个&运算，mCount可以由两个索引的关系得到
lxyppc 发表于 2010-1-6 16:33

[/quote]
这个说法比较不可靠，%运算没有这么简单，就算除数是2^n，对于没有除法指令的MCU，没个10条20条指令完成不了。不信你可以用编译器的模拟器试试。

发表于 2010-1-7 11:12

本帖最后由冷漠于 2010-1-7 11:15 编辑

这位网友比Keil、lxyppc 还高明：

此言谬矣。
size_t GetRingCount()
{
  size_t size = (Ring.pIn - Ring.pOut) % RING_SIZE;
  if( (size == 0) && (Ring.pIn != Ring.pOut) ){
size = RING_SIZE;
  }
  return  size;
}
Ring.pOut也是要互斥保护的，除非是32位的ARM。农民的mCount是8位变量，根本不需要互斥保护，冷漠还需要学习很多

。

他看不懂C ？连我这样菜鸟都看懂了：typedef unsigned char Ele_t; 是8/16位？让圈圈给他讲讲课。

xlsbz · 发表于 2010-1-7 11:13

可能是我理解的太肤浅了吧！

我认为就像HWM所说的那样啊，不至于搞那么麻烦吧！
到处都是看到UCOS的影子，感觉怪怪的！

有偿求助环形缓冲器用法—300RMB

相关帖子

评分

12楼正解。

评分

浏览过的版块

社区建设奖章

欢快之小溪

伴坛终老

技术奇才奖章

无冕之王奖章

沉静之湖泊

十世金身

技术导师奖章

技术领袖奖章

坚毅之洋流

终身成就奖章

湍急之河流

以坛为家

荣誉元老奖章