[FPGA 实现及PCIe IP 核知识点] CRC系列5 - PCIe Gen6 8Byte CRC

(本文估计是第一篇验证PCIe Gen6 8Byte CRC的文章)
到了PCIe Gen6,当速率运行在64.0 GT/s或者更高,PCIe Link将采用Flit Mode。一个Symbol的大小仍然还是8-bit,即1个Byte。一个Flit由256个Byte组成,其中包含:
绿:236个Byte给TLP使用(Byte0 - Byte235)

蓝:6个Byte给Data Link Layer作为Payload(Byte236 - Byte241)

黄:8个Byte用来存放CRC(Byte242 - Byte249)

橙:6个Byte用来存放ECC (Byte250 - Byte255)

如下图所示:

1.png

8-ByteCRC将用来保护TLP和DLLP的数据,即Byte0-Byte241,共242个Byte的数据。
根据目前版本Spec的说法:
CRC的生成多项式(GeneratorPolynomial)被定义在伽罗华有限域GF(28)中,具体与有限域相关的基础知识大家可能需要找大学的教材来复习一下了,本文主要罗列必要的推导过程和结论。

生成多项式为 g(x) = (x+α)(x+α2)… (x+α8)

α是本原多项式(PrimitivePolynomial)x8+x5+x3+x+1=0的根

如果α是本原多项式x8+x5+x3+x+1=0的根,则:
α8+α5+α3+α+1 = 0

-α8 = α5+α3+α+1

α8 = α5+α3+α+1 (因为有限域中的加减法都是异或操作)

Note:在GF(28)域中可以定义不同的本原多项式。PCIe Spec选择了其中一种。本原多项式在有限域中主要用来限制两数相乘,当其结果超出有限域范围的时候,可以把本原多项式当成一个除数,把超出有限域范围的结果再通过求余数的方式再将结果返回到有限域中。

接下来,我们可以利用这个多项式,求解α的多次幂。由于α是一个8-bit的数,可以直接用8位二进制进行表示如下:

    α0 相当于 0000 0001
    α1 相当于 0000 0010
    α2 相当于 0000 0100
    α3 相当于 0000 1000
    α4 相当于 0001 0000
    α5 相当于 0010 0000
    α6 相当于 0100 0000
    α7 相当于 1000 0000

α8 的最高位超出了8-bit的范围,这个时候可以使用本原多项式将结果通过求余的方式返回到8-bit的范围内。
具体过程如下:

    因为:α8+α5+α3+α+1 = 0
    所以:-α8 = α5+α3+α+1
    由于有限域中的加减法都是异或操作
    所以:α8 = α5+α3+α+1
    因此:
    α8 相当于α5+α3+α+1 即α5+α3+α1+α0
    即:
    0010 0000 ^ 0000 1000 ^0000 0010 ^ 0000 0001= 0010 1011b

我们可以持续迭代计算,当结果出现比α7 更高次幂的时候,我们可以通过使用本原多项式将结果通过求余的方式返回到8-bit的数据范围内。下面是通过Python脚本计算α多次幂的程序:

def GF28_element(n = 256):
    """
    This function will help to calculate a**172
    a is the root of x**8 + x**5 + x**3 + x + 1= 0
    a**0 = 0000 0001
    a**1 = 0000 0010
    a**2 = 0000 0100
    a**3 = 0000 1000
    a**4 = 0001 0000
    a**5 = 0010 0000
    a**6 = 0100 0000
    a**7 = 1000 0000
    a**8 = 0010 1011
    """
    a = n*[0]
    a[0] = 1
    for i in range(n):
        #start from bit1 and skip bit0.
        if i > 0:
            #when bit7 == 1, then need xorpolynomial
            if (a[i-1] & 0x80 == 0x80):
                a[i] = ((a[i-1] << 1) ^0x2B)&0xFF
            else:
                a[i] =(a[i-1]<<1)&0xFF
        else:
            continue

        print "a**(%03d) = 0x%02x :::[7:0] -"%(i, a[i]),
        print getbit(a[i],8,reverse = 1)[0]

下面是Python脚本运行完的部分结果:

>>>x.GF28_root(260)
a**(001) = 0x02 :::[7:0] - [0, 0, 0, 0, 0, 0, 1, 0]
a**(002) = 0x04 :::[7:0] - [0, 0, 0, 0, 0, 1, 0, 0]
a**(003) = 0x08 :::[7:0] - [0, 0, 0, 0, 1, 0, 0, 0]
a**(004) = 0x10 :::[7:0] - [0, 0, 0, 1, 0, 0, 0, 0]
a**(005) = 0x20 :::[7:0] - [0, 0, 1, 0, 0, 0, 0, 0]
a**(006) = 0x40 :::[7:0] - [0, 1, 0, 0, 0, 0, 0, 0]
a**(007) = 0x80 :::[7:0] - [1, 0, 0, 0, 0, 0, 0, 0]
a**(008) = 0x2b :::[7:0] - [0, 0, 1, 0, 1, 0, 1, 1]
a**(009) = 0x56 :::[7:0] - [0, 1, 0, 1, 0, 1, 1, 0]
a**(010) = 0xac :::[7:0] - [1, 0, 1, 0, 1, 1, 0, 0]
… …
a**(250)= 0xab ::: [7:0] - [1, 0, 1, 0, 1, 0, 1, 1]
a**(251)= 0x7d ::: [7:0] - [0, 1, 1, 1, 1, 1, 0, 1]
a**(252)= 0xfa ::: [7:0] - [1, 1, 1, 1, 1, 0, 1, 0]
a**(253)= 0xdf ::: [7:0] - [1, 1, 0, 1, 1, 1, 1, 1]
a**(254)= 0x95 ::: [7:0] - [1, 0, 0, 1, 0, 1, 0, 1]
a**(255)= 0x01 ::: [7:0] - [0, 0, 0, 0, 0, 0, 0, 1]
a**(256)= 0x02 ::: [7:0] - [0, 0, 0, 0, 0, 0, 1, 0]
a**(257)= 0x04 ::: [7:0] - [0, 0, 0, 0, 0, 1, 0, 0]
a**(258)= 0x08 ::: [7:0] - [0, 0, 0, 0, 1, 0, 0, 0]
a**(259)= 0x10 ::: [7:0] - [0, 0, 0, 1, 0, 0, 0, 0]

我们可以看到,α255与α0的值是相同的,所以GF(28)域总共有255个元素,所有元素都可以通过α的多少次幂得到。当α幂次超过255后,其8-bit的表达式则开始重复。即,αn = α(n+255)

于是根据生成多项式g(x)= (x+α)(x+α2)… (x+α8),可以展开为:

2.png

这个g(x)相当于一个除数,它能够使得输入的数据与g(x)长除后,其余数会落进GF(28)域中。结合我们之前的CRC电路的设计,如下:

3.png

唯一不同的地方是之前的CRC电路都是针对1个bit一个bit的位移,而GF(28)域的CRC,其移位寄存器的宽度是8-bit的。其中,GF(28)的加法运算就是将8-bit数与另外8-bit数进行异或,其结果还是一个8-bit数。需要知道的是这三个8-bit数都是GF(28)域中的元素。
GF(28)乘法操作稍微复杂一些,首先两个8-bit数进行相乘,可以先转换成二项式,然后做二项式的乘法,其结果一般都会超过GF(28)的范围,这时候和我们计算α多次幂时一样,需要利用本原多项式,将结果通过求余的方式转换回GF(28)域,这样一来,就实现了GF(28)域的乘法操作。
GF(28) CRC电路每一拍都会输入一个8-bit的数,然后参与电路的计算,一直到最后一个Byte输入进电路,然后停止。这个时候,停留在B0到B7寄存器中的值就是通过原始数据计算出来的GF(28)的CRC值。

由于GF(28) CRC电路中要使用到α的多次幂的结果,使用上面的GF28_element函数可以得到以下结果:

4.png

下面是Python脚本验证PCIe Gen6 8-Byte CRC的具体code:

def gen6_8Bcrc(data=242*[0]):
    """
    gen6_8Bcrc is a verification code of PCIeGen6 8Byte CRC.
    """

    crc_o = 8*[0]
    crc  = 8*[0]
    #data = 242*[0]

    for i in range(242):
        tmp = (crc_o[7] ^ data[i]) & 0xFF
        crc[0] = gf8m(tmp, 0x69, 0x12B)
        crc[1] = gf8m(tmp, 0x4d, 0x12B) ^crc_o[0]
        crc[2] = gf8m(tmp, 0x41, 0x12B) ^crc_o[1]
        crc[3] = gf8m(tmp, 0x33, 0x12B) ^crc_o[2]
        crc[4] = gf8m(tmp, 0xd5, 0x12B) ^crc_o[3]
        crc[5] = gf8m(tmp, 0xfe, 0x12B) ^crc_o[4]
        crc[6] = gf8m(tmp, 0x68, 0x12B) ^crc_o[5]
        crc[7] = gf8m(tmp, 0xd5, 0x12B) ^crc_o[6]
        crc_o[0] = crc[0]
        crc_o[1] = crc[1]
        crc_o[2] = crc[2]
        crc_o[3] = crc[3]
        crc_o[4] = crc[4]
        crc_o[5] = crc[5]
        crc_o[6] = crc[6]
        crc_o[7] = crc[7]
        print "#%d  ---- "%i,
        for j in range(8):
            print "0x%02x"%crc_o[j],
            if j==7:
                print ""

def gf8m(a, b, p):
    """
    gf8m will help to do gf8 multiply withpolynominal
    Inputs:
    a : operator a
    b : operator b
    p : polynominal in binary
    """
    tmp1,tmp2 = getbit(a, 8)
    data = 0
    for i in range(8):
        if tmp1[i] == 1:
            data = data ^ (b << i)
    return gf8d(data, p)

def gf8d(a, p):
    """
    try to divde a by p:
    """
    a_list, length = getbit(a, 0, reverse = 1)
    crc8 = 8*[0]
    crc_o = 8*[0]
    p_list, tmp = getbit(p, 0)

    for i in range(length):
        for j in range(8):
            if j == 0:
                if p_list[j]:
                    crc8[0] = a_list[i] ^crc_o[7]
                else:
                    crc8[0] = a_list[i]
            else:
                if p_list[j]:
                    crc8[j] = crc_o[j-1] ^crc_o[7]
                else:
                    crc8[j] = crc_o[j-1]

        for j in range(8):
            crc_o[j]    =  crc8[j]

    data = 0
    for i in range(8):
        data = data + (crc_o[i] << i)
    return data

如果输入的数据是242个Byte,并且都为0,那么输出的8Byte CRC也是0,如下:

>>>x.gen6_8Bcrc()
#0  ---- 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
#1  ---- 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
#2  ---- 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
… …
#239  ---- 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
#240  ---- 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
#241  ---- 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00

如果我们将输入的第一个Byte(最小的那个Byte,即B0) 由0x00,改为0x01,那么得到的8Byte CRC将是:

>>> data=242*[0]
>>> data[0]=0x01
>>> x.gen6_8Bcrc(data)
#0  ----  0x69 0x4d 0x41 0x33 0xd5 0xfe 0x68 0xd5
#1  ----  0x22 0x01 0x5e 0xd2 0x0a 0x89 0x09 0x51
#2  ----  0x80 0xc8 0x5a 0x3f 0x65 0x95 0x58 0xbe
… …
#239  ----  0xa3 0x11 0xac 0x54 0x14 0x37 0xe2 0x1f
#240  ----  0x6b 0x29 0x1f 0xcb 0xdf 0xdb 0x43 0x69
#241  ----  0x0b 0x3b 0xc3 0x1a 0xe9 0xa7 0xb9 0x61

8Byte CRC Byte0 等于0x0b
8Byte CRC Byte1 等于0x3b
8Byte CRC Byte2 等于0xc3
… …

同时,PCIe Spec的附录K也提供了生成矩阵,其使用方法如下:

图片

首先将242-Byte的数据按照高位到低位的顺序排列,一共有1936个bit组成,其中第一个bit是B241.7,代表最高Byte的第7bit,然后是第6bit,然后依次到第0bit,然后切换到次Byte,即B240.7,然后依次排列到最小的一个Byte,即B0.7,B0.6一直到B0.0。一共1936个bit称为矩阵的一行。与一个1936x64的矩阵相乘,这个矩阵被放置在了附录K中。其排列是一行由8个Byte组成,我们也需要将其排列成64个bit,按照最左边Byte的第7bit,第6bit,依次到最右边的最后一个Byte的第7bit,第6bit,然后到最后一个bit。
一个1936的单行矩阵与1936x64的矩阵相乘,将得到64个bit,这64个bit,即8Byte CRC的结果。其Python对应脚本为:

gen=[
[0xa7, 0xad, 0x46,0xa7, 0x3e, 0x67, 0x9d, 0x2d],
[0xc6, 0xc3, 0x23,0xc6, 0x1f, 0xa6, 0xdb, 0x83],
… …
[0xc2, 0x59, 0x65,0xf9, 0x34, 0xad, 0x76, 0x16],
[0x61, 0xb9, 0xa7,0xe9, 0x1a, 0xc3, 0x3b, 0x0b]
]

Flit242B= [
0x00,0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00,0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
… …
0x00,0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x01 ]


def matrixm():
    bit = 64*[0]

    # j loop for 64
    for j in range(64):
        for i in range(1936):
            r_bit = (Flit242B[i>>3]>> (7-(i%8))) & 0x1
            c_bit = (gen[i][j>>3]>> (7-(j%8))) & 0x1
            bit[j] = bit[j] ^ (r_bit &c_bit)
    print bit

得到的结果为:

>>>y.matrixm()
[0, 1,1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0,1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0,1, 1, 0, 0, 0, 0, 1, 0, 1, 1]

可以看出,结果的最高8个bit(从左开始)来自8Byte CRC的Byte7,其次是Byte6直到Byte0。
这与CRC电路得到的结果顺序是反的。
另外需要注意的是CRC电路的输入是从最小的Byte开始,而矩阵乘法中原数据摆放是将最大的Byte放在最左侧。当然,大家也可以输入不同的原始数据验证。

编辑 重设标签(回车键确认) 标为违禁 关闭 合并 删除
匿名用户

匿名