11. "Reflected" Table-Driven Implementations “反射”表驱动实现
Despite the fact that the above code is probably optimized about as much as it could be, this did not stop some enterprising individuals from making things even more complicated. To understand how this happened, we have to enter the world of hardware.
尽管上述代码可能已经尽可能地优化了,但这并没有阻止一些有进取心的人把事情变得更加复杂。要了解这是如何发生的,我们必须进入硬件世界。
DEFINITION: A value/register is reflected if it's bits are swapped around its centre.
定义:如果一个值/寄存器的位围绕其中心交换,则反映该值/寄存器。
For example: 0101
is the 4-bit reflection of 1010
.
0011
is the reflection of 1100
.
0111-0101-1010-1111-0010-0101-1011-1100
is the reflection of 0011-1101-1010-0100-1111-0101-1010-1110
.
Turns out that UARTs (those handy little chips that perform serial IO) are in the habit of transmitting each byte with the least significant bit (bit 0) first and the most significant bit (bit 7) last (i.e. reflected). An effect of this convention is that hardware engineers constructing hardware CRC calculators that operate at the bit level took to calculating CRCs of bytes streams with each of the bytes reflected within itself. The bytes are processed in the same order, but the bits in each byte are swapped; bit 0 is now bit 7, bit 1 is now bit 6, and so on. Now this wouldn't matter much if this convention was restricted to hardware land. However it seems that at some stage some of these CRC values were presented at the software level and someone had to write some code that would interoperate with the hardware CRC calculation.
事实证明,UART(那些执行串行IO的方便的小芯片)习惯于首先传输最低有效位(位0),最后传输最高有效位(位数7)的每个字节(即反射)。这种约定的一个效果是,构建在比特级运行的硬件CRC计算器的硬件工程师需要计算字节流的CRC,每个字节都反映在其内部。字节以相同的顺序处理,但每个字节中的位被交换;位0现在是位7,位1现在是位6,以此类推。如果这个约定仅限于硬件领域,这就没什么关系了。然而,在某些阶段,这些CRC值中的一些似乎是在软件级别呈现的,必须有人编写一些与硬件CRC计算互操作的代码。
In this situation, a normal sane software engineer would simply reflect each byte before processing it. However, it would seem that normal sane software engineers were thin on the ground when this early ground was being broken, because instead of reflecting the bytes, whoever was responsible held down the byte and reflected the world, leading to the following "reflected" algorithm which is identical to the previous one except that everything is reflected except the input bytes.
在这种情况下,一个正常理智的软件工程师会在处理每个字节之前简单地反映出来。然而,当这个早期的基础被打破时,正常理智的工程师似乎很薄弱,因为负责的人没有反映字节,而是压低了字节,反映了世界,导致了以下“反映”算法,该算法与前一个算法相同,除了除了输入字节之外,其他所有内容都被反映出来。
Message (non augmented) >-----+
|
Bytes 0 1 2 3 v
+----+----+----+----+ |
| | | | |>----XOR
+----+----+----+----+ |
^ |
| |
XOR |
| |
+----+----+----+----+0 |
+----+----+----+----+ v
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+ |
+----+----+----+----+<-----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+
+----+----+----+----+255
Notes:
-
The table is identical to the one in the previous algorithm except that each entry has been reflected.
+除了每个条目都被反映出来之外,该表与之前算法中的表完全相同。
-
The initial value of the register is the same as in the previous algorithm except that it has been reflected.
+寄存器的初始值与之前的算法中的值相同,除了它已被反映出来。
-
The bytes of the message are processed in the same order as before (i.e. the message itself is not reflected).
+消息的字节按照与以前相同的顺序进行处理(即消息本身不被反映)。
-
The message bytes themselves don't need to be explicitly reflected, because everything else has been!
+消息字节本身不需要显式反映,因为其他一切都已经反映出来了!
At the end of execution, the register contains the reflection of the final CRC value (remainder). Actually, I'm being rather hard on whoever cooked this up because it seems that hardware implementations of the CRC algorithm used the reflected checksum value and so producing a reflected CRC was just right. In fact reflecting the world was probably a good engineering solution - if a confusing one.
在执行结束时,寄存器包含最终CRC值(余数)的反映。事实上,我对炮制这件事的人相当严厉,因为CRC算法的硬件实现似乎使用了反射的校验和值,因此产生反射的CRC是正确的。事实上,反映世界可能是一个很好的工程解决方案——即使是一个令人困惑的解决方案。
We will call this the REFLECTED algorithm.
我们称之为反射算法。
Whether or not it made sense at the time, the effect of having reflected algorithms kicking around the world's FTP sites is that about half the CRC implementations one runs into are reflected and the other half not. It's really terribly confusing. In particular, it would seem to me that the casual reader who runs into a reflected, table-driven implementation with the bytes "fed in the wrong end" would have Buckley's chance of ever connecting the code to the concept of binary mod 2 division.
无论当时是否有意义,在世界各地的FTP站点上运行反射算法的效果是,大约一半的CRC实现被反射,另一半没有。这真的非常令人困惑。特别是,在我看来,如果一个偶然的读者遇到一个反射的、表驱动的实现,其中字节“输入错误的一端”,那么巴克利就有机会将代码与二进制模2除法的概念联系起来。
It couldn't get any more confusing could it? Yes it could.
它不能再让人困惑了,不是吗?是的,可以。
12. "Reversed" Polys
As if reflected implementations weren't enough, there is another concept kicking around which makes the situation bizaarly confusing. The concept is reversed Polys.
好像反射实现还不够,还有另一个概念让情况变得混乱。这个概念是相反的Polys。
It turns out that the reflection of good polys tend to be good polys too! That is, if G=11101 is a good poly value, then 10111 will be as well. As a consequence, it seems that every time an organization (such as CCITT) standardizes on a particularly good poly ("polynomial"), those in the real world can't leave the poly's reflection alone either. They just HAVE to use it. As a result, the set of "standard" poly's has a corresponding set of reflections, which are also in use. To avoid confusion, we will call these the "reversed" polys.
事实证明,好的polys的反射往往也是好的polys!也就是说,如果G=11101是一个好的poly值,那么10111也是。因此,似乎每次一个组织(如CCITT)对一个特别好的poly(“多项式”)进行标准化时,现实世界中的组织也不能放过poly的反射。他们只需要使用它。因此,一组“标准”多边形有一组相应的反射,这些反射也在使用中。为了避免混淆,我们将这些称为“反向”poly。
X25 standard: 1-0001-0000-0010-0001
X25 reversed: 1-0000-1000-0001-0001
CRC16 standard: 1-1000-0000-0000-0101
CRC16 reversed: 1-0100-0000-0000-0011
Note that here it is the entire poly that is being reflected/reversed, not just the bottom W bits. This is an important distinction. In the reflected algorithm described in the previous section, the poly used in the reflected algorithm was actually identical to that used in the non-reflected algorithm; all that had happened is that the bytes had effectively been reflected. As such, all the 16-bit/32-bit numbers in the algorithm had to be reflected. In contrast, the ENTIRE poly includes the implicit one bit at the top, and so reversing a poly is not the same as reflecting its bottom 16 or 32 bits.
请注意,这里反射/反转的是整个多边形,而不仅仅是底部的W位。这是一个重要的区别。在前一节描述的反射算法中,反射算法中使用的多边形实际上与非反射算法中的多边形相同;所发生的只是字节已被有效地反映出来。因此,算法中的所有16位/32位数字都必须反映出来。相比之下,整多边形在顶部包含隐式的一个位,因此反转多边形并不等于反映其底部的16或32位。
The upshot of all this is that a reflected algorithm is not equivalent to the original algorithm with the poly reflected. Actually, this is probably less confusing than if they were duals.
所有这一切的结果是,反射算法并不等同于具有多边形反射的原始算法。事实上,这可能比它们是对偶的情况更不令人困惑。
If all this seems a bit unclear, don't worry, because we're going to sort it all out "real soon now". Just one more section to go before that.
如果这一切看起来有点不清楚,别担心,因为我们“很快”就会解决这一切。在那之前还有一节。
13. Initial and Final Values 初始值和最终值
In addition to the complexity already seen, CRC algorithms differ from each other in two other regards:
除了已经看到的复杂性之外,CRC算法在另外两个方面也有所不同:
-
The initial value of the register.
+寄存器的初始值。
-
The value to be XORed with the final register value.
+与最终寄存器值进行异或运算的值。
For example, the "CRC32" algorithm initializes its register to FFFFFFFF and XORs the final register value with FFFFFFFF.
例如,“CRC32”算法将其寄存器初始化为FFFFFFF,并用FFFFFFF对最终寄存器值进行异或运算。
Most CRC algorithms initialize their register to zero. However, some initialize it to a non-zero value. In theory (i.e. with no assumptions about the message), the initial value has no affect on the strength of the CRC algorithm, the initial value merely providing a fixed starting point from which the register value can progress. However, in practice, some messages are more likely than others, and it is wise to initialize the CRC algorithm register to a value that does not have "blind spots" that are likely to occur in practice. By "blind spot" is meant a sequence of message bytes that do not result in the register changing its value. In particular, any CRC algorithm that initializes its register to zero will have a blind spot of zero when it starts up and will be unable to "count" a leading run of zero bytes. As a leading run of zero bytes is quite common in real messages, it is wise to initialize the algorithm register to a non-zero value.
大多数CRC算法将其寄存器初始化为零。但是,有些会将其初始化为非零值。理论上(即没有关于消息的假设),初始值对CRC算法的强度没有影响,初始值仅提供寄存器值可以从中前进的固定起点。然而,在实践中,一些消息比其他消息更有可能,明智的做法是将CRC算法寄存器初始化为一个没有实践中可能出现的“盲点”的值。“盲点”是指不会导致寄存器改变其值的消息字节序列。特别是,任何将寄存器初始化为零的CRC算法在启动时都会有一个盲点为零,并且无法“计数”零字节的前导运行。由于零字节的前导运行在真实消息中很常见,因此将算法寄存器初始化为非零值是明智的。
14. Defining Algorithms Absolutely 绝对定义算法
At this point we have covered all the different aspects of table-driven CRC algorithms. As there are so many variations on these algorithms, it is worth trying to establish a nomenclature for them. This section attempts to do that.
至此,我们已经介绍了表驱动CRC算法的所有不同方面。由于这些算法有很多变体,因此值得尝试为它们建立一个命名法。本节试图做到这一点。
We have seen that CRC algorithms vary in:
我们已经看到CRC算法在以下方面有所不同:
- Width of the poly (polynomial).
+多项式的宽度。
- Value of the poly.
+poly的价值。
- Initial value for the register.
+寄存器的初始值。
- Whether the bits of each byte are reflected before being processed.
+每个字节的位在处理之前是否被反映出来。
- Whether the algorithm feeds input bytes through the register or xors them with a byte from one end and then straight into the table.
+该算法是通过寄存器馈送输入字节,还是从一端用一个字节对其进行异或运算,然后直接输入到表中。
- Whether the final register value should be reversed (as in reflected versions).
+是否应反转最终寄存器值(如反射版本)。
- Value to XOR with the final register value.
+值与最终寄存器值XOR。
In order to be able to talk about particular CRC algorithms, we need to able to define them more precisely than this. For this reason, the next section attempts to provide a well-defined parameterized model for CRC algorithms. To refer to a particular algorithm, we need then simply specify the algorithm in terms of parameters to the model.
为了能够讨论特定的CRC算法,我们需要能够更精确地定义它们。因此,下一节将尝试为CRC算法提供一个定义良好的参数化模型。要引用特定的算法,我们只需根据模型的参数指定算法。
15. A Parameterized Model For CRC Algorithms
In this section we define a precise parameterized model CRC algorithm
which, for want of a better name, we will call the "Rocksoft^tm Model
CRC Algorithm" (and why not? Rocksoft^tm could do with some free
advertising