Dotaz: CRC

[Jardík]

Na wiki jsem našel jakýsi algoritmus na CRC v pseudokódu:

// Most significant bit first (big-endian)
  // x^16+x^12+x^5+1 = (1) 0001 0000 0010 0001 = 0x1021
  function crc(byte array string[1..len], int len) {
     rem  := 0
     // A popular variant complements rem here
      for i from 1 to len {
         rem  := rem xor (string[i] leftShift (n-8))   // n = 16 in this example
          for j from 1 to 8 {   // Assuming 8 bits per byte
              if rem and 0x8000 {   // if leftmost (most significant) bit is set
                 rem  := (rem leftShift 1) xor 0x1021
             } else {
                 rem  := rem leftShift 1
             }
             rem  := rem and 0xffff      // Trim remainder to 16 bits
         }
     }
     // A popular variant complements rem here
      return rem
 }

Je to CRC-16. Řekněme, že chcu počítat CRC-4, budu si předpočítávat tabulku, takže pro každý byte si spočítám element:

// pro každý 8b byte "nějakejByte"
byte rem := 0 xor (nějakejByte leftShift (4-8))
for j from 1 to 8 { // 
  if rem and 0x8 {
    rem  := (rem leftShift 1) xor poly
  }
  else {
    rem  := rem leftShift 1
  }
  rem := rem and 0x7
}
tabulka[nějakejByte] := rem

Vyjde mi tam posun vlevo o -4 (4-8) ??? To se mi nezdá.

---

---

Odpovědi

[AraxoN]

Povedal by som, že ten úvodný shift-left je tam len preto, že v origináli používa polynóm s dvoma bajtami. Pri CRC-4 budeš mať polynóm kratší a nemusíš to robiť.

Ale popravde doteraz ma CRC do detailov nezaujímalo, takže sa môžem v tejto nočnej hodine epicky mýliť...

[Jardík]

Tak já na to ještě koukal, prostudoval pár dokumentů, očučel pár zdrojáků (boost, zlib), a nějak to splácal v D parametricky ala boost a místo neustálého převracení bitů v reflected módu tam hodil generátor ze zlibu, který vygeneruje reflected tabulku s reflected polynomem.

module jardik.checksum.crc;

import jardik.inttypes;
import std.traits;

public struct CRCIntTraits(const size_t _CRC_BITS,
                            _IntType = UIntFast!(_CRC_BITS))
{
    static const size_t CRC_BITS = _CRC_BITS;
    alias IntType = _IntType;
    
    static assert(isIntegral!(IntType), "Integral type required");
    static assert(IntType.sizeof * 8 >= CRC_BITS, "Integral doesn't have enough bits");
    
    static const IntType ZERO = 0;
    static const IntType ONE = 1;
    static const IntType CRC_HIBIT = ONE << (CRC_BITS-1);
    
    static if (CRC_BITS < IntType.sizeof * 8)
    {
        static const IntType CRC_MASK = ~cast(IntType)(~ZERO << CRC_BITS);
        
        static pure IntType crcMask(IntType val) {
            return val & CRC_MASK;
        }
    }
    else {
        static const IntType CRC_MASK = ~ZERO;
        
        static pure IntType crcMask(IntType val) {
            return val;
        }
    }
}

private pure IntType reflect(const size_t NUM_BITS,
                             IntType)
                            (IntType value)
{
    alias IntTraits = CRCIntTraits!(NUM_BITS, IntType);
    
    IntType result = IntTraits.ZERO;
    
    for (size_t i = 0; i < NUM_BITS; ++i)
    {
        if (value & IntTraits.ONE) {
            result |= (IntTraits.ONE << (NUM_BITS - 1 - i));
        }
        value >>= 1;
    }
    return result;
}

public struct CRCPoly(const size_t _CRC_BITS)
{
    static const size_t CRC_BITS = _CRC_BITS;
    alias IntTraits = CRCIntTraits!(CRC_BITS);
    alias IntType = IntTraits.IntType;
    
    IntType normalValue;
    IntType reflectedValue;
    
    static CRCPoly fromData(U)(in U[] polyData)
    {
        IntType value = IntTraits.ZERO;
        foreach(n; polyData)
        {
            assert(n < CRC_BITS);
            value |= IntTraits.ONE << n;
        }
        
        return normal(value);
    }
    
    static CRCPoly normal(IntType value) {
        return CRCPoly(value, reflect!(CRC_BITS)(value));
    }
    
    static CRCPoly reflected(IntType value) {
        return CRCPoly(reflect!(CRC_BITS)(value), value);
    }
}

unittest
{
    import std.stdio;
    import core.exception;
    
    printf(">> Testing CRC poly generator\n");
    
    // CRC-4-ITU
    try {
        immutable ubyte[] crc4polyData = [0,1];
        
        const uint crc4polyCheck = 0x3U;
        const uint crc4polyReflectedCheck = 0xCU;
        
        auto crc4poly = CRCPoly!(4).fromData(crc4polyData).normalValue;
        auto crc4polyReflected = CRCPoly!(4).fromData(crc4polyData).reflectedValue;
        
        assert(crc4poly == crc4polyCheck);
        assert(crc4polyReflected == crc4polyReflectedCheck);
        printf("   ... CRC-4 poly passed.\n");
    }
    catch (AssertError) {
        printf("   ... CRC-4 poly failed.\n");
    }
    
    // CRC-32
    try {
        immutable ubyte[] crc32polyData = [0,1,2,4,5,7,8,10,11,12,16,22,23,26];
        
        const uint crc32polyCheck = 0x04C11DB7U;
        const uint crc32polyReflectedCheck = 0xEDB88320U;
        
        auto crc32poly = CRCPoly!(32).fromData(crc32polyData).normalValue;
        auto crc32polyReflected = CRCPoly!(32).fromData(crc32polyData).reflectedValue;
        
        assert(crc32poly == crc32polyCheck);
        assert(crc32polyReflected == crc32polyReflectedCheck);
        printf("   ... CRC-32 poly passed.\n");
    }
    catch (AssertError) {
        printf("   ... CRC-32 poly failed.\n");
    }
    
    // CRC-64-ECMA
    try {
        immutable ubyte[] crc64polyData = [
            0,1,4,7,9,10,12,13,17,19,21,22,23,24,27,29,31,
            32,33,35,37,38,39,40,45,46,47,52,53,54,55,57,62
        ];
        
        const ulong crc64polyCheck = 0x42F0E1EBA9EA3693UL;
        const ulong crc64polyReflectedCheck = 0xC96C5795D7870F42UL;
        
        auto crc64poly = CRCPoly!(64).fromData(crc64polyData).normalValue;
        auto crc64polyReflected = CRCPoly!(64).fromData(crc64polyData).reflectedValue;
        
        assert(crc64poly == crc64polyCheck);
        assert(crc64polyReflected == crc64polyReflectedCheck);
        
        printf("   ... CRC-64 poly passed.\n");
    }
    catch (AssertError) {
        printf("   ... CRC-64 poly failed.\n");
    }
}



public class CRCTableGen(// number of CRC bits
                         const size_t _CRC_BITS,
                         // integer type backing the CRC table entry
                         _IntType = UIntFast!(_CRC_BITS),
                         // whether to reflect CRC table entries
                         const bool REFLECT = false)
{
    enum : size_t { CRC_BITS = _CRC_BITS }
    alias IntType = _IntType;
    alias IntTraits = CRCIntTraits!(CRC_BITS, IntType);
    alias FastIntType = UIntFast!(CRC_BITS);
    alias FastIntTraits = CRCIntTraits!(CRC_BITS, FastIntType);
    
    public static pure IntType[] generate(in CRCPoly!CRC_BITS poly)
    {
        IntType[] table = new IntType[256];
        generateImpl(table, poly);
        return table;
    }
    
    public static pure IntType[] generate(IntType[] reuseTable,
                                          in CRCPoly!CRC_BITS poly)
    {
        IntType[] table = reuseTable.length < 256 ? new IntType[256] : reuseTable;
        generateImpl(table, poly);
        return table;
    }
    
    static if (!REFLECT)
    {
        private static pure void generateImpl(IntType[] table,
                                              in CRCPoly!CRC_BITS poly)
        {
            FastIntType remainder;
            FastIntType polyVal = poly.normalValue;
            
            for (size_t divident = 0; divident < 256; ++divident)
            {
                remainder = FastIntTraits.ZERO;
                
                for (size_t mask = 0x80; mask != 0; mask >>= 1)
                {
                    if (divident & mask)
                        remainder ^= FastIntTraits.CRC_HIBIT;
                    
                    if (remainder & FastIntTraits.CRC_HIBIT) {
                        remainder <<= 1;
                        remainder ^= polyVal;
                    }
                    else {
                        remainder <<= 1;
                    }
                }
                
                table[divident] = cast(IntType)FastIntTraits.crcMask(remainder);
            }
        }
    }
    else
    {
        private static pure void generateImpl(IntType[] table,
                                              in CRCPoly!CRC_BITS poly)
        {
            FastIntType rem;
            FastIntType polyVal = poly.reflectedValue;
            size_t k;
            
            for (size_t divident = 0; divident < 256; ++divident)
            {
                rem = cast(FastIntType)divident;
                for (k = 0; k < 8; ++k)
                    rem = rem & 1 ? polyVal ^ (rem >> 1) : (rem >> 1);
                
                table[divident] = cast(IntType)FastIntTraits.crcMask(rem);
            }
        }
    }
}

unittest
{
    import std.stdio;
    import core.exception;
    
    const auto poly = CRCPoly!(32)(0x04C11DB7U, 0xEDB88320U);
    
    uint[] crcTable = CRCTableGen!(32, uint, false).generate(poly);
    uint[] crcTableReflected = CRCTableGen!(32, uint, true).generate(poly);
    
    File f = File("crc32test.txt", "w");
    
    f.writeln(" NORMAL  | REFLECT  ");
    f.writeln("---------|----------");
    for (size_t i = 0; i < 256; ++i)
    {
        f.writefln("%08X | %08X", crcTable[i],
                   crcTableReflected[i]);
    }
    
    
    auto crc4poly = CRCPoly!(4).normal(0b1011U);
    ubyte[] crc4table = CRCTableGen!(4, ubyte, false).generate(crc4poly);
    
    f = File("crc4test.txt", "w");
    
    size_t i;
    for (i = 0; i < 256-8; i+=8)
    {
        f.writefln("0x%02X, 0x%02X, 0x%02X, 0x%02X, 0x%02X, 0x%02X, 0x%02X, 0x%02X,",
                   crc4table[i], crc4table[i+1], crc4table[i+2], crc4table[i+3],
                   crc4table[i+4], crc4table[i+5], crc4table[i+6], crc4table[i+7]);
    }
    f.writefln("0x%02X, 0x%02X, 0x%02X, 0x%02X, 0x%02X, 0x%02X, 0x%02X, 0x%02X",
               crc4table[i], crc4table[i+1], crc4table[i+2], crc4table[i+3],
               crc4table[i+4], crc4table[i+5], crc4table[i+6], crc4table[i+7]);
}

public class CRC(const size_t CRC_BITS,
                 _TableIntType = FastInt!(CRC_BITS),
                 const bool _REFLECT_DATA = false,
                 const bool _REFLECT_REM = _REFLECT_DATA)
{
    alias IntTraits = CRCIntTraits!(CRC_BITS);
    alias IntType = IntTraits.IntType;
    
    alias TableIntType = _TableIntType;
    alias TableGen = CRCTableGen!(CRC_BITS, TableIntType, _REFLECT_DATA);
    
    alias PolyType = CRCPoly!(CRC_BITS);
    
    const(TableIntType)[] m_table;
    IntType m_init;
    IntType m_xor;
    IntType m_val;
    
    public this(in PolyType poly, IntType initVal, IntType xorVal)
    {
        this(TableGen.generate(poly), initVal, xorVal);
    }
    
    public this(const(TableIntType)[] table, IntType initVal, IntType xorVal)
    {
        m_table = table;
        m_init = initVal;
        m_xor = xorVal;
        m_val = m_init;
    }
    
    public void reset()
    {
        m_val = m_init;
    }
    
    public void update(string str)
    {
        update(cast(const(ubyte[]))str);
    }
    
    static if (_REFLECT_DATA)
    {
        public void update(in ubyte[] buf)
        {
            size_t tableIndex;
            
            foreach (IntType b; buf)
            {
                tableIndex = cast(size_t)((m_val ^ b) & cast(IntType)0xFFU);
                m_val = cast(IntType)(m_table[tableIndex] ^ (m_val >> 8));
            }
        }
    }
    else
    {
        public void update(in ubyte[] buf)
        {
            size_t tableIndex;
            
            foreach (IntType b; buf)
            {
                static if (CRC_BITS < 8)
                    tableIndex = cast(size_t)(b ^ (m_val << (8 - CRC_BITS)));
                else
                    tableIndex = cast(size_t)(b ^ (m_val >> (CRC_BITS - 8)));
                
                m_val = IntTraits.crcMask(cast(IntType)(m_table[tableIndex] ^ (m_val << 8)));
            }
        }
    }
    
    public IntType peek() const
    {
        static if (_REFLECT_REM == _REFLECT_DATA) {
            return IntTraits.crcMask(m_val ^ m_xor);
        }
        else {
            return IntTraits.crcMask(reflect!(CRC_BITS, IntType)(m_val) ^ m_xor);
        }
    }
    
    public IntType finish()
    {
        IntType crcVal = peek();
        reset();
        return crcVal;
    }
}

public class CRC32 : CRC!(32, uint, true, true)
{
    public this() {
        //super(PolyType.normal(0x04C11DB7U), 0xFFFFFFFFU, 0xFFFFFFFFU);
        super(PolyType.reflected(0xEDB88320U), 0xFFFFFFFFU, 0xFFFFFFFFU);
    }
    
    public this(const(uint)[] table) {
        super(table, 0xFFFFFFFFU, 0xFFFFFFFFU);
    }
}

unittest
{
    import std.stdio;
    import core.exception;
    
    printf(">> Testing CRC32\n");
    try {
        CRC32 crc32 = new CRC32();
        crc32.update("abc");
        ulong crc = crc32.finish();
        assert(crc == 0x352441C2U);
        printf("   ... passed.\n");
    }
    catch (AssertError) {
        printf("   ... failed.\n");
    }
    
    printf(">> Testing CRC4 poly = 0xB\n");
    try {
        auto crc4 = new CRC!(4, ushort, false, false)(CRCPoly!(4).normal(0xB), 0, 0);
        crc4.update("abcdef");
        assert(crc4.finish() == 0x2);
        printf("   ... passed.\n");
    }
    catch (AssertError) {
        printf("   ... failed.\n");
    }
    
    printf(">> Testing CRC4 poly = 0xB, reflected\n");
    try {
        auto crc4 = new CRC!(4, ushort, true, true)(CRCPoly!(4).normal(0xB), 0, 0);
        crc4.update("abcdef");
        assert(crc4.finish() == 0x8);
        printf("   ... passed.\n");
    }
    catch (AssertError) {
        printf("   ... failed.\n");
    }
    
    printf(">> Testing CRC16-CCITT\n");
    try {
        auto poly = CRCPoly!(16).normal(0x1021);
        auto crc16ccitt = new CRC!(16, ushort, false, false)(poly, 0xffff, 0);
        crc16ccitt.update("abcdef");
        assert(crc16ccitt.finish() == 0x34ED);
        printf("   ... passed.\n");
    }
    catch (AssertError) {
        printf("   ... failed.\n");
    }
    
    printf(">> Testing CRC16\n");
    try {
        auto poly = CRCPoly!(16).normal(0x8005);
        auto crc16 = new CRC!(16, ushort, true, true)(poly, 0, 0);
        crc16.update("abcdef");
        assert(crc16.finish() == 0x5805);
        printf("   ... passed.\n");
    }
    catch (AssertError) {
        printf("   ... failed.\n");
    }
    
    printf(">> Testing CRC-12\n");
    try {
        auto poly = CRCPoly!(12).normal(0x80F);
        auto crc = new CRC!(12, ushort, false, false)(poly, 0, 0);
        crc.update("abcdef");
        assert(crc.finish() == 0x6C7);
        printf("   ... passed.\n");
    }
    catch (AssertError) {
        printf("   ... failed.\n");
    }
    
    printf(">> Testing CRC-12 reflected\n");
    try {
        auto poly = CRCPoly!(12).normal(0x80F);
        auto crc = new CRC!(12, ushort, true, true)(poly, 0, 0);
        crc.update("abcdef");
        assert(crc.finish() == 0xFE6);
        printf("   ... passed.\n");
    }
    catch (AssertError) {
        printf("   ... failed.\n");
    }
}

int main()
{
    return 0;
}

[Jardík]

Jinak odkazy pro zájemce:

• Něco o CRC tu
• boost::crc
• A pak tu něco ze zlibu