导读
读了此文能得到什么
缘起
环形缓冲区
研究起加法器在Linux中的应用是因为最近从研究了环形缓冲区，其中对环形缓冲区优化的时候去看了Linux内核源码中的kfifo.c代码。这里简单提一嘴什么是环形缓冲区，英文名RingBuffer或者CyclicBuffer，是一个先进先出的队列，多用作网络编程缓存区等。
环形缓冲区可以看成是一个手尾相接的环，但其实他在内存中并不是一个环，而是一个连续的内存空间，只是抽象成一个环。在读写内容的时候，分别有读写两个指针指向下一次读写地址。
当写到队尾的时候，指针会重置回头部开始续写，如此连续的动作可以被看成是一个环。
按照常规想法，我在写第一个版本的环形缓冲区的时候，定义了读写两个指针，然后每次手动去判断什么时机应该把指针重置回头部，这么写比较简单，也是常规人类的思维方式。但是当后来查看了Linux源码的kfifo队列时，发现了更优的写法和有趣的问题，于是继续探索产出此文。
Linux内核中的kfifo
环形缓冲区作为内存中一个连续的内存空间，要想很好使用起来的话，需要几个必备函数：计算读写指针偏移量（相对起始位置）、计算缓冲区是否写满、计算缓冲区是否为空、计算缓冲区可写长度。其中这4个方法都会涉及到指针的复位、偏移量的计算。
我在kfifo的源码中发现，Linux中的写法是用持续自增的uint来记录读写指针。
#ifndef _LINUX_KFIFO_H
#define _LINUX_KFIFO_H
#include <linux/kernel.h>
#include <linux/spinlock.h>
struct kfifo {
unsigned char *buffer; /* the buffer holding the data */
unsigned int size; /* the size of the allocated buffer */
unsigned int in; /* data is added at offset (in % size) */
unsigned int out; /* data is extracted from off. (out % size) */
};
/*
* __kfifo_add_in internal helper function for updating the in offset
*/
static inline void __kfifo_add_in(struct kfifo *fifo,
unsigned int off)
{
smp_wmb();
fifo->in += off;
}/*
* __kfifo_add_out internal helper function for updating the out offset
*/
static inline void __kfifo_add_out(struct kfifo *fifo,
unsigned int off)
{
smp_mb();
fifo->out += off;
}然后利用取余运算算出读写偏移量（指针和缓冲区大小取余），利用kfifo->in - kfifo->out来计算出剩余可写长度。
/**
* kfifo_len - returns the number of used bytes in the FIFO
* @fifo: the fifo to be used.
*/
static inline unsigned int kfifo_len(struct kfifo *fifo)
{
register unsigned int out;
out = fifo->out;
smp_rmb();
return fifo->in - out;
}有趣的现象
环形缓冲区的相关细节以后有机会单独开文章聊了，这次就针对其中一个加法器部分。在看见如上的代码的时候，我脑海里闪出的第一个念头就是，如果in和out指针是持续自增的，当缓冲区读写一定次数以后，uint来到最大值的时候再次操作缓冲区，会产生一个什么样的结果？会崩溃？会溢出？还是完全正常的运行？
验证疑问
#include <stdio.h>
#include <limits.h>
int main() {
int a = INT_MAX + 2;
int b = INT_MAX - 2;
printf("a - b = %d", a - b);
return 0;
}针对上面的疑问，导致缓冲区是否可以正常运行的关键在于指针是否正常，于是我快速敲写了上面的代码进行验证，设置a、b两个值，直接对两个值进行Max一左一右的赋值，Run出来的结果意料之中又意料之外。
/Users/jasper/CLionProjects/untitled/cmake-build-debug/untitled
a - b = 4
进程已结束,退出代码0
运行结果显示差值正好是 ±2 计算出来的4。
深入
再得到了上面的结论之后，我变拿着结论去尝试反推过程，搜索过程繁不赘述，其中有同事帮忙搜索后提到可能是加法器的原理，用加法器能够解释的通。
加法器
说到这里就不得不提到计算机中的加减乘除余等运算原理，这里我们暂时只关注加减法运算。
大家知道计算机的所有运算都是由硬件电路提供的，在电路中这里涉及到的是门电路：与门、或门、异或门。大家所学的数学运算，只有加法是可以用门电路直接表达出来的，所以减法运算其实也是利用加法来实现的。下面我们来讲数学运算和电路结合起来。
门电路
这里的输入输出的【真/假】在电路中的真实表现为高低电平（与地线的压差），了解些数电模电的同学应该很容易理解，其他同学就当做逻辑【真假】理解就行。
与门
与门是实现逻辑“乘”运算的电路，有两个输入端，一个输出端，两个输入端都为真，输出才真
输入A |
输入B |
输出 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
或门
或门只要有一个条件为真，输出就真
输入A |
输入B |
输出 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
异或门
异或门若两个输入相同则输出假，两个输入不同则输出真
输入A |
输入B |
输出 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
半加器
在讲解了前置所需的基础知识门电路后，终于来到了真正的加法运算实现的讲解。这里我们要把进制切换到2进制来思考。
我们常见的加法运算有需要进位和不需要进位的。
当不需要考虑上一位的进位值来直接求 a（输入a） + b（输入b）= sum的加法器叫做半加器。他的电路表达如下：
半加器是由 与门 和 异或门 组合而成，利用两种门电路的运算特性，来抽象实现 a + b。
我们用模拟器来演示一下a + b = sum的过程。
当我们给a和b其中任何一个值赋值为1，另一个为0的时候：
异或门表现理解为输入a=1，输入b=0，则输出为1，用异或门的输出代表求和sum。
与门的表现理解为输入a=1，输入b=0，则输出为0，用与门的输出代表进位carry。
表示出1 + 0 求和等于 1。
当我们给a和b都赋值为1的时候：
异或门表现理解为输入a=1，输入b=1，则输出为0。
与门的表现理解为输入a=1，输入b=1，则输出为1。
表示出1 + 1 求和等于2，当前位是0，结果向前进一位1。
至此我们理解了半加器的加法运算过程，结合了物理电路结构，很巧妙的将物理结构代入到了计算机逻辑结构中。
全加器
在半加器中，我们发现会存在进位的情况，进位会给到下一位计算中参与求和运算。
全加器，就是在半加器的基础上，除了接收a、b两个输入，还额外接收一个进位输入c。
需要进位的情况，a（输入a） + b（输入b） + c（上一位计算进位值）= sum，他的电路表达如下：
两个半加器组合可以实现一个全加器（考虑进位），我们来操作一下模拟器理解一下：
当上一位没有Cin进位输入的时候，输出结果就跟半加器相同。
当上一位有Cin进位输入的时候，如果a和b都没有输入，则求和sum等于1（进位给到的那个1）。
当上一位有Cin进位输入的时候，如果a和b只有其中一个有输入1，则求和sum等于0，进位1（1+1=2，当前位0，进位1）。
当上一位有Cin进位输入的时候，如果a和b都有输入1，则求和sum等于1，进位1（1+1+1=3，当前位1，进位1）。
4位全加器
门电路组成了半加器，半加器组成了全加器，事情演化到了这一步，我们来到了全加器与全加器的结合，4个全加器组成了一个4位全加器，也就是1字节加法器。
这里原理相同，就不做逐步的演示截图了，a + b + Cin = sum，可以计算出1字节的两个值相加，求和与进位值。
Int全加器
事情终于演化到了最有趣的环节，我们终于可以将电路和我们最初的疑问关联在一起，4个1字节全加器就组成了4字节全加器，也就是一个Int型全加器。到了这一步，我们终于可以模拟出（INT_MAX+2） -（INT_MAX-2）了。
减法运算
前文的知识铺垫大家已经知道了减法也是用加法计算来实现的，那么原理是什么呢？
我们用时钟来举例子，比如现在时针是12点，我们让时针指向1点的方式有几种？
答案是2种：12点往前推1个小时，或者12点往回倒退11个小时。
如此便引入了补码和反码的概念，数学关联性很多，关联知识体系也很庞大，我们指引入到补码和反码这层概念。
正数的原码、反码、补码均相同。
原码：用最高位表示符号位，其余位表示数值位的编码称为原码。其中，正数的符号位为 0，负数的符号位为 1。
负数的反码：把原码的符号位保持不变，数值位逐位取反，即可得原码的反码。
负数的补码：在反码的基础上加 1 即得该原码的补码。
减法相当于加上一个负数，所以可以使用加法来代替减法。但是这就出现了如何处理符号位的问题，short、int、long的位数不同符号位自然也不同，为了避免运算前还需要判断符号位的位置，前人提出了将符号位也引入计算的机制，也就是补码。
减法运算公式：
a减b相当于：a +（负数b）相当于：a的补码 + b的补码 相当于：a的补码 + b的反码加1
模拟
模拟a
在上一步我们的减法运算公式分析为：a减b相当于：a +（负数b）相当于：a的补码 + b的补码 相当于：a的补码 + b的反码加1
这一步我们来逐步模拟一下，模拟环境为无符号Int。
INT_MAX 等价于 1111 1111 1111 1111，
a = INT_MAX + 2 等价于 0000 0000 0000 0001 等价于1
看一下模拟电路的运算过程：
电路左边代表INT_MAX，全部为1，右边代表+2，最下面的加法结果为0000 0000 0000 0001，这里也就解释了为什么MAX再继续增加后会自动重置回来，MAX+2，经历了0，1两个数字，最后停在了1上，其实右边的Cout进位了1，所以真要解释为什么会重置回来，其实是因为进位了1，只是左边的数字没有人再接收进位出去的1了，导致进位被丢弃，所以最终计算机内表现逻辑为INT_MAX+2=1
模拟b
INT_MAX 等价于 1111 1111 1111 1111，
a = INT_MAX - 2 等价于 1111 1111 1111 1111 + 负2的反码加1 等价于 1111 1111 1111 1111 + 1111 1111 1111 1101加1
等价于1111 1111 1111 1111 + 1111 1111 1111 1110 等价于 1111 1111 1111 1101
同样进位1被丢弃，最终b=1111 1111 1111 1101
模拟a-b
最终模拟a-b也就是模拟（INT_MAX+2） -（INT_MAX-2）等价于 0000 0000 0000 0001 - 1111 1111 1111 1101
等价于0000 0000 0000 0001 + 1111 1111 1111 1101的反码加1
等价于0000 0000 0000 0001 + 0000 0000 0000 0011
等价于0000 0000 0000 0100
等价于4
总结
最终我们借助电路模拟器的模拟以及相关知识的补习，理解了INT_MAX加减2的正确运行情况，以及环形缓冲区之所以能用Int自增当做读写指针并且高效正确运行的原理。
思考
在加物理与数学与计算机相结合的过程中，我们理解了本来单靠数学解释不通的事情，这让我发现原来我们的思维都存在些或多或少的思维固化，也感叹计算机前人的极致思考。
参考
Code版本有很多，可以自行搜索，本文以v2.6.35为例
kfifo.h：kfifo.h - include/linux/kfifo.h - Linux source code (v2.6.35) - Bootlin
kfifo.c：kfifo.c - kernel/kfifo.c - Linux source code (v2.6.35) - Bootlin
在想数电模拟器：CircuitVerse - Online Digital Logic Circuit Simulator
全加器 & 4位加法器：CircuitVerse - Ripple Carry Adder
