O HAI THIS BLOG PURPZIEZ 2 B UZED AZ MAH PLESIOUS MEM. :)

2009/04/11

updateCRC(&CRC, &byte);

ちとCRCをムニャる必要が出て来たので,例の本をゴニョると,byte streamに対して計算するアルゴリズムが載っていたので,2時間くらいモニョモニョしてVHDLで実装した.

先ず,popularな生成多項式をWikipediaからパクってきてpackageに.
library ieee;
use ieee.std_logic_1164.all;

package CRC_GENERATOR_PKG is

constant cCRC_1_GENERATOR : std_logic_vector;
constant cCRC_4_ITU_GENERATOR : std_logic_vector;
constant cCRC_5_ITU_GENERATOR : std_logic_vector;
constant cCRC_5_USB_GENERATOR : std_logic_vector;
constant cCRC_6_ITU_GENERATOR : std_logic_vector;
constant cCRC_7_GENERATOR : std_logic_vector;
constant cCRC_8_ATM_GENERATOR : std_logic_vector;
constant cCRC_8_CCITT_GENERATOR : std_logic_vector;
constant cCRC_8_Dallas_Maxim_GENERATOR : std_logic_vector;
constant cCRC_8_GENERATOR : std_logic_vector;
constant cCRC_8_SAE_J1850_GENERATOR : std_logic_vector;
constant cCRC_10_GENERATOR : std_logic_vector;
constant cCRC_11_GENERATOR : std_logic_vector;
constant cCRC_12_GENERATOR : std_logic_vector;
constant cCRC_15_CAN_GENERATOR : std_logic_vector;
constant cCRC_16_CCITT_GENERATOR : std_logic_vector;
constant cCRC_16_DNP_GENERATOR : std_logic_vector;
constant cCRC_16_IBM_GENERATOR : std_logic_vector;
constant cCRC_24_Radix_64_GENERATOR : std_logic_vector;
constant cCRC_30_GENERATOR : std_logic_vector;
constant cCRC_32_IEEE_802_3_GENERATOR : std_logic_vector;
constant cCRC_32_Castagnoli_GENERATOR : std_logic_vector;
constant cCRC_32_Koopman_GENERATOR : std_logic_vector;
constant cCRC_64_ISO_3309_GENERATOR : std_logic_vector;
constant cCRC_64_ECMA_182_GENERATOR : std_logic_vector;

end package CRC_GENERATOR_PKG;

package body CRC_GENERATOR_PKG is

type tCRC_TYPE is (
CRC_1,
CRC_4_ITU,
CRC_5_ITU,
CRC_5_USB,
CRC_6_ITU,
CRC_7,
CRC_8_ATM,
CRC_8_CCITT,
CRC_8_Dallas_Maxim,
CRC_8,
CRC_8_SAE_J1850,
CRC_10,
CRC_11,
CRC_12,
CRC_15_CAN,
CRC_16_CCITT,
CRC_16_DNP,
CRC_16_IBM,
CRC_24_Radix_64,
CRC_30,
CRC_32_IEEE_802_3,
CRC_32_Castagnoli,
CRC_32_Koopman,
CRC_64_ISO_3309,
CRC_64_ECMA_182
);

type tCRC_LENGTH is array (tCRC_TYPE) of integer range 1 to 64;
constant cCRC_LENGTH : tCRC_LENGTH := (
CRC_1 => 1,
CRC_4_ITU => 4,
CRC_5_ITU => 5,
CRC_5_USB => 5,
CRC_6_ITU => 6,
CRC_7 => 7,
CRC_8_ATM => 8,
CRC_8_CCITT => 8,
CRC_8_Dallas_Maxim => 8,
CRC_8 => 8,
CRC_8_SAE_J1850 => 8,
CRC_10 => 10,
CRC_11 => 11,
CRC_12 => 12,
CRC_15_CAN => 15,
CRC_16_CCITT => 16,
CRC_16_DNP => 16,
CRC_16_IBM => 16,
CRC_24_Radix_64 => 24,
CRC_30 => 30,
CRC_32_IEEE_802_3 => 32,
CRC_32_Castagnoli => 32,
CRC_32_Koopman => 32,
CRC_64_ISO_3309 => 64,
CRC_64_ECMA_182 => 64
);

type tCRC_GENERATOR is array (tCRC_TYPE) of std_logic_vector(64 downto 0);
constant cCRC_GENERATOR : tCRC_GENERATOR := (
CRC_1 =>
-- x^1 + x^0
(64 downto 1+1 => '0') & "11",
CRC_4_ITU =>
-- x^4 + x^1 + x^0
(64 downto 4+1 => '0') & "10011",
CRC_5_ITU =>
-- x^5 + x^4 + x^2 + x^0
(64 downto 5+1 => '0') & "110101",
CRC_5_USB =>
-- x^5 + x^2 + x^0
(64 downto 5+1 => '0') & "100101",
CRC_6_ITU =>
-- x^6 + x^1 + x^0
(64 downto 6+1 => '0') & "1000011",
CRC_7 =>
-- x^7 + x^3 + x^0
(64 downto 7+1 => '0') & "10001001",
CRC_8_ATM =>
-- x^8 + x^2 + x^1 + x^0
(64 downto 8+1 => '0') & "100000111",
CRC_8_CCITT =>
-- x^8 + x^7 + x^3 + x^2 + x^0
(64 downto 8+1 => '0') & "110001101",
CRC_8_Dallas_Maxim =>
-- x^8 + x^5 + x^4 + x^0
(64 downto 8+1 => '0') & "100110001",
CRC_8 =>
-- x^8 + x^7 + x^6 + x^4 + x^2 + x^0
(64 downto 8+1 => '0') & "111010101",
CRC_8_SAE_J1850 =>
-- x^8 + x^4 + x^3 + x^2 + x^0
(64 downto 8+1 => '0') & "100011101",
CRC_10 =>
-- x^10 + x^9 + x^5 + x^4 + x^1 + x^0
(64 downto 10+1 => '0') & "11000110011",
CRC_11 =>
-- x^11 + x^9 + x^8 + x^7 + x^2 + x^0
(64 downto 11+1 => '0') & "101110000101",
CRC_12 =>
-- x^12 + x^11 + x^3 + x^2 + x^1 + x^0
(64 downto 12+1 => '0') & "1100000001111",
CRC_15_CAN =>
-- x^15 + x^14 + x^10 + x^8 + x^7 + x^4 + x^3 + x^0
(64 downto 15+1 => '0') & "1100010110011001",
CRC_16_CCITT =>
-- x^16 + x^12 + x^5 + x^0
(64 downto 16+1 => '0') & "10001000000100001",
CRC_16_DNP =>
-- x^16 + x^13 + x^12 + x^11 + x^10 + x^8 + x^6 + x^5 + x^2 + x^0
(64 downto 16+1 => '0') & "10011110101100101",
CRC_16_IBM =>
-- x^16 + x^15 + x^2 + x^0
(64 downto 16+1 => '0') & "11000000000000101",
CRC_24_Radix_64 =>
-- x^24 + x^23 + x^18 + x^17 + x^14 + x^11 + x^10 + x^7 + x^6 + x^5
-- + x^4 + x^3 + x^1 + x^0
(64 downto 24+1 => '0') & "1100001100100110011111011",
CRC_30 =>
-- x^30 + x^29 + x^21 + x^20 + x^15 + x^13 + x^12 + x^11 + x^8 + x^7
-- + x^6 + x^2 + x^1 + x^0
(64 downto 30+1 => '0') & "1100000001100001011100111000111",
CRC_32_IEEE_802_3 =>
-- x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7
-- + x^5 + x^4 + x^2 + x^1 + x^0
(64 downto 32+1 => '0') & "100000100110000010001110110110111",
CRC_32_Castagnoli =>
-- x^32 + x^28 + x^27 + x^26 + x^25 + x^23 + x^22 + x^20 + x^19 + x^18
-- + x^14 + x^13 + x^11 + x^10 + x^9 + x^8 + x^6 + x^0
(64 downto 32+1 => '0') & "100011110110111000110111101000001",
CRC_32_Koopman =>
-- x^32 + x^30 + x^29 + x^28 + x^26 + x^20 + x^19 + x^17 + x^16 + x^15
-- + x^11 + x^10 + x^7 + x^6 + x^4 + x^2 + x^1 + x^0
(64 downto 32+1 => '0') & "101110100000110111000110011010111",
CRC_64_ISO_3309 =>
-- x^64 + x^4 + x^3 + x^1 + x^0
"10000000000000000000000000000000000000000000000000000000000011011",
CRC_64_ECMA_182 =>
-- x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45
-- + x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29
-- + x^27 + x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12
-- + x^10 + x^9 + x^7 + x^4 + x^1 + x^0
"10100001011110000111000011110101110101001111010100011011010010011"
);

constant cCRC_1_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_1 )(cCRC_LENGTH(CRC_1 ) downto 0);
constant cCRC_4_ITU_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_4_ITU )(cCRC_LENGTH(CRC_4_ITU ) downto 0);
constant cCRC_5_ITU_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_5_ITU )(cCRC_LENGTH(CRC_5_ITU ) downto 0);
constant cCRC_5_USB_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_5_USB )(cCRC_LENGTH(CRC_5_USB ) downto 0);
constant cCRC_6_ITU_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_6_ITU )(cCRC_LENGTH(CRC_6_ITU ) downto 0);
constant cCRC_7_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_7 )(cCRC_LENGTH(CRC_7 ) downto 0);
constant cCRC_8_ATM_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_8_ATM )(cCRC_LENGTH(CRC_8_ATM ) downto 0);
constant cCRC_8_CCITT_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_8_CCITT )(cCRC_LENGTH(CRC_8_CCITT ) downto 0);
constant cCRC_8_Dallas_Maxim_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_8_Dallas_Maxim)(cCRC_LENGTH(CRC_8_Dallas_Maxim) downto 0);
constant cCRC_8_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_8 )(cCRC_LENGTH(CRC_8 ) downto 0);
constant cCRC_8_SAE_J1850_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_8_SAE_J1850 )(cCRC_LENGTH(CRC_8_SAE_J1850 ) downto 0);
constant cCRC_10_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_10 )(cCRC_LENGTH(CRC_10 ) downto 0);
constant cCRC_11_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_11 )(cCRC_LENGTH(CRC_11 ) downto 0);
constant cCRC_12_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_12 )(cCRC_LENGTH(CRC_12 ) downto 0);
constant cCRC_15_CAN_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_15_CAN )(cCRC_LENGTH(CRC_15_CAN ) downto 0);
constant cCRC_16_CCITT_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_16_CCITT )(cCRC_LENGTH(CRC_16_CCITT ) downto 0);
constant cCRC_16_DNP_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_16_DNP )(cCRC_LENGTH(CRC_16_DNP ) downto 0);
constant cCRC_16_IBM_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_16_IBM )(cCRC_LENGTH(CRC_16_IBM ) downto 0);
constant cCRC_24_Radix_64_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_24_Radix_64 )(cCRC_LENGTH(CRC_24_Radix_64 ) downto 0);
constant cCRC_30_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_30 )(cCRC_LENGTH(CRC_30 ) downto 0);
constant cCRC_32_IEEE_802_3_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_32_IEEE_802_3 )(cCRC_LENGTH(CRC_32_IEEE_802_3 ) downto 0);
constant cCRC_32_Castagnoli_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_32_Castagnoli )(cCRC_LENGTH(CRC_32_Castagnoli ) downto 0);
constant cCRC_32_Koopman_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_32_Koopman )(cCRC_LENGTH(CRC_32_Koopman ) downto 0);
constant cCRC_64_ISO_3309_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_64_ISO_3309 )(cCRC_LENGTH(CRC_64_ISO_3309 ) downto 0);
constant cCRC_64_ECMA_182_GENERATOR : std_logic_vector := cCRC_GENERATOR(CRC_64_ECMA_182 )(cCRC_LENGTH(CRC_64_ECMA_182 ) downto 0);

end package body CRC_GENERATOR_PKG;

次に,生成多項式とbit per byteをgenericで指定して,例のアルゴリズムをそのままtwo-process手法で実装.
library ieee;
use ieee.std_logic_1164.all;
use work.CRC_GENERATOR_PKG.all;

package BYTE_CRC_PKG is

component BYTE_CRC is
generic (
BPB : integer range 1 to integer'high := 8;
GENERATOR : std_logic_vector := cCRC_16_CCITT_GENERATOR;
ASYNC : boolean := false
);
port (
iCLK : in std_logic;
iCLR : in std_logic;
iINI : in std_logic;
iE : in std_logic;
iD : in std_logic_vector( BPB-1 downto 0);
oE : out std_logic;
oD : out std_logic_vector( BPB-1 downto 0);
oCRC : out std_logic_vector((GENERATOR'length-1)-1 downto 0)
);
end component BYTE_CRC;

end package BYTE_CRC_PKG;

package body BYTE_CRC_PKG is

-- NOTE: This body should keep to be empty to stub.

end package body BYTE_CRC_PKG;

library ieee;
use ieee.std_logic_1164.all;
use ieee.std_logic_arith.all;
use work.CRC_GENERATOR_PKG.all;

entity BYTE_CRC is
generic (
BPB : integer range 1 to integer'high := 8;
GENERATOR : std_logic_vector := cCRC_16_CCITT_GENERATOR;
ASYNC : boolean := false
);
port (
iCLK : in std_logic;
iCLR : in std_logic;
iINI : in std_logic;
iE : in std_logic;
iD : in std_logic_vector( BPB-1 downto 0);
oE : out std_logic;
oD : out std_logic_vector( BPB-1 downto 0);
oCRC : out std_logic_vector((GENERATOR'length-1)-1 downto 0)
);
begin
A_BPB_CHECK : assert ((GENERATOR'length-1) mod BPB = 0)
report BYTE_CRC'instance_name &
"GENERATOR'length-1 should be congrunet to 0 modulo BPB!!1"
severity error;
end entity BYTE_CRC;

architecture TP of BYTE_CRC is

pure function fLEAD_BIT_INDEX (
iX : std_logic_vector
) return integer is
begin
F_L : for l in iX'range loop
if (iX(l) = '1') then
return l;
end if;
end loop F_L;
return -1;
end function fLEAD_BIT_INDEX;

type tCRC_REMAINDER is
array (0 to 2**BPB-1) of
std_logic_vector((GENERATOR'length-1)-1 downto 0);

pure function fCRC_REMAINDER (
iG : std_logic_vector
) return tCRC_REMAINDER is
variable vLG : integer range -1 to iG'length-1;
variable vQ : std_logic_vector(BPB-1 downto 0);
variable vR : std_logic_vector(vQ'length+(iG'length-1)-1 downto 0);
variable vLR : integer range -1 to vR'length-1;
variable vG : std_logic_vector(vR'range);
variable vCRC_REMAINDER : tCRC_REMAINDER;
begin
vLG := fLEAD_BIT_INDEX(iG);
F_Q : for Q in 0 to 2**vQ'length-1 loop
vQ := conv_std_logic_vector(Q, vQ'length);
vR := vQ & ((iG'length-1)-1 downto 0 => '0');
vLR := fLEAD_BIT_INDEX(vR);
W_R : while (vLR >= vLG) loop
vG :=
(vG'length-1 downto vLR+1 => '0') &
iG(vLG downto 0) &
(vLR-vLG-1 downto 0 => '0');
vR := vR xor vG;
vLR := fLEAD_BIT_INDEX(vR);
end loop W_R;
-- synthesis translate_off
A_CRC_REMAINDER_CHECK :
assert (vR(vR'length-1 downto iG'length-1) =
(vR'length-1 downto iG'length-1 => '0'))
report fCRC_REMAINDER'instance_name &
"CRC remainder is out of range!!1"
severity error;
-- synthesis translate_on
vCRC_REMAINDER(Q) := vR((iG'length-1)-1 downto 0);
end loop F_Q;
return vCRC_REMAINDER;
end function fCRC_REMAINDER;

constant cCRC_REMAINDER : tCRC_REMAINDER := fCRC_REMAINDER(GENERATOR);

type tCRC is
array (((GENERATOR'length-1)/BPB)-1 downto 0) of
std_logic_vector(BPB-1 downto 0);

type t is record
E : std_logic;
D : std_logic_vector(BPB-1 downto 0);
RI : std_logic_vector(BPB-1 downto 0);
CRC : tCRC;
end record t;

constant c : t := (
E => '0',
D => (BPB-1 downto 0 => '0'),
RI => (BPB-1 downto 0 => '0'),
CRC => (tCRC'range => (BPB-1 downto 0 => '0'))
);

signal g : t;
signal r : t := c;

begin

P_COMB : process (iINI, iE, iD, r)
variable v : t := c;
begin
if (iINI = '1') then
v.E := '0';
v.D := (BPB-1 downto 0 => '0');
v.RI := (BPB-1 downto 0 => '0');
F_CRC_INITIALIZE : for i in tCRC'range loop
v.CRC(i) := (BPB-1 downto 0 => '0');
end loop F_CRC_INITIALIZE;
elsif (iE = '1') then
v.E := '1';
v.D := iD;
v.RI := iD xor r.CRC(tCRC'high);
F_CRC_UPDATE : for i in tCRC'range loop
if (i = tCRC'low) then
v.CRC(i) :=
cCRC_REMAINDER(conv_integer(unsigned(v.RI)))((i+1)*BPB-1 downto i*BPB);
else
v.CRC(i) :=
r.CRC(i-1) xor
cCRC_REMAINDER(conv_integer(unsigned(v.RI)))((i+1)*BPB-1 downto i*BPB);
end if;
end loop F_CRC_UPDATE;
else
v.E := '0';
v.D := r.D;
v.RI := r.RI;
v.CRC := r.CRC;
end if;

g <= v;
oE <= r.E;
oD <= r.D;
F_CRC_OUTPUT : for i in tCRC'range loop
oCRC((i+1)*BPB-1 downto i*BPB) <= r.CRC(i);
end loop F_CRC_OUTPUT;
end process P_COMB;

G_ASYNC : if (ASYNC = true) generate
begin
P_SEQ : process (iCLR, iCLK)
begin
if (iCLR = '1') then
r <= c;
elsif (iCLK'event and iCLK = '1') then
r <= g;
end if;
end process P_SEQ;
end generate G_ASYNC;

G_SYNC : if (ASYNC = false) generate
begin
P_SEQ : process (iCLK)
begin
if (iCLK'event and iCLK = '1') then
if (iCLR = '1') then
r <= c;
else
r <= g;
end if;
end if;
end process P_SEQ;
end generate G_SYNC;

end architecture TP;

最後に,やる気の無いテストベンチをでっち上げ.
library ieee;
use ieee.std_logic_1164.all;
use work.CRC_GENERATOR_PKG.all;
use work.BYTE_CRC_PKG.all;

entity BENCH_BYTE_CRC is
begin
end entity BENCH_BYTE_CRC;

architecture BENCH of BENCH_BYTE_CRC is

constant cCLK_CYCLE : time := 1 us;
constant cCLR_TIME : time := 10*cCLK_CYCLE;

signal sCLK : std_logic := '0';
signal sCLR : std_logic := '1';

type tST is (INIT, BYTE1, BYTE0);

signal sST : tST := INIT;
signal sINI : std_logic := '0';
signal sE : std_logic := '0';
signal sD : std_logic_vector(7 downto 0) := (7 downto 0 => '0');

signal sBYTE_CRC_oE : std_logic;
signal sBYTE_CRC_oD : std_logic_vector( 7 downto 0);
signal sBYTE_CRC_oCRC : std_logic_vector(15 downto 0);

begin

P_sCLK : process
begin
sCLK <= '0'; wait for cCLK_CYCLE/2;
sCLK <= '1'; wait for cCLK_CYCLE/2;
end process P_sCLK;

P_sCLR : process
begin
sCLR <= '1'; wait for cCLR_TIME;
sCLR <= '0'; wait;
end process P_sCLR;

P_sST_sINI_sE_sD : process (sCLK)
begin
if (sCLK'event and sCLK = '1') then
if (sCLR = '1') then
sST <= INIT;
sINI <= '1';
sE <= '0';
sD <= (7 downto 0 => '0');
else
case sST is
when INIT =>
sST <= BYTE1;
sINI <= '0';
sE <= '1';
sD <= X"6D";
when BYTE1 =>
sST <= BYTE0;
sINI <= '0';
sE <= '1';
sD <= X"27";
when BYTE0 =>
sST <= BYTE0;
sINI <= '0';
sE <= '0';
sD <= sD;
when others =>
sST <= INIT;
sINI <= '1';
sE <= '0';
sD <= (7 downto 0 => '0');
end case;
end if;
end if;
end process P_sST_sINI_sE_sD;

U_BYTE_CRC : BYTE_CRC
generic map (
BPB => 8,
GENERATOR => cCRC_16_IBM_GENERATOR,
ASYNC => false
)
port map (
iCLK => sCLK,
iCLR => sCLR,
iINI => sINI,
iE => sE,
iD => sD,
oE => sBYTE_CRC_oE,
oD => sBYTE_CRC_oD,
oCRC => sBYTE_CRC_oCRC
);

end architecture BENCH;

pipeline化をサボっているのでクロックが早くなるとダメになる事ウケアイ.
ま,quick'n'dirtyっつー事で. :)