打印

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

[复制链接]
11097|65
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
冷漠|  楼主 | 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 是什么类型无所谓的,并不限于所长的程序,谁能用自己的环形缓冲区处理程序证明更好。

相关帖子

沙发
Thunder_f| | 2010-1-6 14:36 | 只看该作者
本来想看看这300RMB是个什么样的问题,结果:

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

[ 点击这里返回上一页 ]

使用特权

评论回复
板凳
宇容创行| | 2010-1-6 15:05 | 只看该作者
mCount = pIn - pOut

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

使用特权

评论回复
地板
lxyppc| | 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;
}

使用特权

评论回复
评分
参与人数 2威望 +2 收起 理由
forrest11 + 1
冷漠 + 1
5
冷漠|  楼主 | 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。

使用特权

评论回复
6
程序匠人| | 2010-1-6 23:33 | 只看该作者
呵呵,又开始打赌了?

俺不参赌,俺只围观

使用特权

评论回复
7
因特网用户| | 2010-1-7 00:56 | 只看该作者

使用特权

评论回复
8
一只小绵羊| | 2010-1-7 08:53 | 只看该作者
4楼的不错,原来理解肤浅了

使用特权

评论回复
9
lxyppc| | 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元我不要了,我只要版主能给个酷。哈哈

使用特权

评论回复
10
lxyppc| | 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;
}

使用特权

评论回复
11
冷漠|  楼主 | 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;
}

对吗?

使用特权

评论回复
12
宇容创行| | 2010-1-7 10:18 | 只看该作者
RING_SIZE 为2^n 时 % 可以优化成 ( &(RING_SIZE-1))

使用特权

评论回复
13
zhouxin1980| | 2010-1-7 10:23 | 只看该作者
8位机中读写Ring.pOut也是要互斥保护的,中断可能在读一半的时候改写。

使用特权

评论回复
14
冷漠|  楼主 | 2010-1-7 10:24 | 只看该作者

12楼正解。

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

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

使用特权

评论回复
15
zhouxin1980| | 2010-1-7 10:26 | 只看该作者
那和农民用的count有什么区别?而且指针可能是16位的?

使用特权

评论回复
16
01dxwlm| | 2010-1-7 10:37 | 只看该作者
看我以前写过的关于用队列来实现SCI的例子,有完整的程序供可以参考。

使用特权

评论回复
17
HWM| | 2010-1-7 10:40 | 只看该作者
互个鬼斥保护。

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

使用特权

评论回复
18
arm_fan168| | 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条指令完成不了。不信你可以用编译器的模拟器试试。

使用特权

评论回复
19
冷漠|  楼主 | 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位?让圈圈给他讲讲课。

使用特权

评论回复
20
inter_zhou| | 2010-1-7 11:13 | 只看该作者
可能是我理解的太肤浅了吧!

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

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
xlsbz + 1
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

17

主题

921

帖子

4

粉丝