位屏蔽缓冲区索引如何导致环绕

Question

有人可以根据循环缓冲区索引解释位掩码是如何工作的。具体在以下代码中：

#define USART_RX_BUFFER_SIZE 128     /* 2,4,8,16,32,64,128 or 256 bytes */
#define USART_RX_BUFFER_MASK ( USART_RX_BUFFER_SIZE - 1 )


    ISR(USART_RX_vect)
    {
        unsigned char data;
        unsigned char tmphead;

        /* Read the received data */
        data = UDR0;
        /* Calculate buffer index */
        tmphead = ( USART_RxHead + 1 ) & USART_RX_BUFFER_MASK;
        USART_RxHead = tmphead;      /* Store new index */

        if ( tmphead == USART_RxTail )
        {
            /* ERROR! Receive buffer overflow */
        }

        USART_RxBuf[tmphead] = data; /* Store received data in buffer */
    }

我知道位屏蔽索引​​的结果是索引环绕；我的问题是为什么？另外，为什么“USART_RX_BUFFER_SIZE”必须是 2 的幂？

谢谢

乔

Answer 1

要理解这一点，您必须了解一些二进制，并且您必须了解二进制操作。

您可能知道，计算机中的所有内容都以二进制、1 和 0 的序列存储。这意味着理论上，内存中的任何数据字符串都可以被视为数字。由于您的代码是 usin char，因此我将重点介绍它们。

在 C 中，chars 有符号或无符号，为此使用 unsigned 很重要。我不会进入二进制的补码表示，但我只想说，如果你使用了 signed chars ，它会中断。Achar是单个字节，通常被认为是 8 位，如下所示：

00000000 -> 0
00001001 -> 9

基本上每个位代表 2 的幂（我在这里使用 MSB-first），所以第二个数字是2^1 + 2^3 = 1 + 8 = 9. 因此，您可以看到如何使用它来索引数组。

按位运算对某些数据的各个位进行操作。在这种情况下，您使用的是二进制和( &)，并且应用二进制和的行为称为位掩码。

data   - 00101100
mask   - 11110110
       ----------
result - 00101100

如您所见，结果只有在data和mask都为 1 的情况下才将位设置为1。

现在回到我们的二进制表示。由于每个位都是 2 的幂，因此可以使用 0 中的单个 1 来表示二进制中的 2 的幂。

01000000 - 64

就像1000 - 1 = 999, 01000000 - 1 = 00111111, 0011111163在哪里。

使用它我们可以发现，在计算下一个索引时，我们执行以下操作：

(a + 1) & 00111111

如果 a 是（例如）10，那么我们得到

(00001010 + 1) = 00001011 (11)
 00001011 & 00111111 = 00001011

所以屏蔽没有改变，但在 63 的情况下：

(00111111 + 1) = 01000000 (64)
 01000000 & 00111111 = 00000000 (0)

因此，与其尝试索引到 64（这是第 65 个元素，因此是一个错误），不如回到开头。

这就是缓冲区大小必须是 2 的幂的原因，如果不是，则掩码将无法正确计算，您将不得不使用模 ( %) 或比较，而不是位掩码。这很重要，因为按位运算符非常快，因为它们在大多数处理器中通常只是一条指令，并且只&需要很少的周期。模数可能是一条指令，但它可能是整数除法，这在大多数平台上传统上都很慢。比较需要多条指令、寄存器和至少 1 次跳转。