abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 17:25 | IT novinky

Do prodeje (Farnell) se dostal jednodeskový počítač Tinker Board (unboxing). Jedná se o konkurenci Raspberry Pi 3 od společnosti Asus. Porovnání (jpg) těchto počítačů například na CNXSoft. Cena Tinker Boardu je 55 £.

Ladislav Hagara | Komentářů: 0
dnes 14:44 | Zajímavý projekt

Byla zveřejněna pravidla hackerské soutěže Pwn2Own 2017, jež proběhne od 15. do 17. března v rámci bezpečnostní konference CanSecWes ve Vancouveru. Soutěžit se bude o více než milion dolarů v pěti kategoriích. Letos se bude útočit i na Ubuntu. Jedná se již o 10. ročník této soutěže.

Ladislav Hagara | Komentářů: 1
dnes 13:33 | Nová verze

Po sedmi měsících vývoje od vydání verze 5.7 byla vydána verze 5.8 (YouTube) toolkitu Qt. Z novinek lze zmínit například Qt Lite pro vestavěná zařízení. Nově jsou plně podporovány moduly Qt Wayland Compositor (YouTube) a Qt SCXML (YouTube). Současně byla vydána verze 4.2.1 integrovaného vývojového prostředí (IDE) Qt Creator.

Ladislav Hagara | Komentářů: 0
dnes 11:52 | Pozvánky

Lednový Prague Containers Meetup se koná ve čtvrtek 26. ledna 2017 od 18:00 v Apiary, Pernerova 49, Praha 8. Přijďte se podívat na přednášky o Enterprise Kubernetes a Jenkins as a code.

little-drunk-jesus | Komentářů: 0
dnes 11:40 | Pozvánky

Program letošního ročníku konference Prague PostgreSQL Developer Days, která se koná již 15. a 16. února 2017 na ČVUT FIT, Thákurova 9, Praha 6, byl dnes zveřejněn. Najdete ho na stránkách konference včetně anotací přednášek a školení. Registrace na konferenci bude otevřena zítra (24. ledna) v brzkých odpoledních hodinách.

TomasVondra | Komentářů: 0
včera 02:20 | Zajímavý článek

David Revoy, autor open source webového komiksu Pepper&Carrot nebo portrétu GNU/Linuxu, upozorňuje na svém blogu, že nový Inkscape 0.92 rozbíjí dokumenty vytvořené v předchozích verzích Inkscape. Problém by měl být vyřešen v Inkscape 0.92.2 [reddit].

Ladislav Hagara | Komentářů: 0
včera 02:02 | Komunita

Øyvind Kolås, hlavní vývojář grafických knihoven GEGL a babl, které využívá grafický program GIMP, žádá o podporu na Patreonu. Díky ní bude moci pracovat na vývoji na plný úvazek. Milník 1000 $, který by stačil na holé přežití, se již téměř podařilo vybrat, dalším cílem je dosažení 2500 $, které mu umožní běžně fungovat ve společnosti.

xkomczax | Komentářů: 12
21.1. 23:54 | Pozvánky

DevConf.cz 2017, již devátý ročník jedné z největších akcí zaměřených na Linux a open source ve střední Evropě, proběhne od pátku 27. ledna do neděle 29. ledna v prostorách Fakulty informačních technologií Vysokého učení technického v Brně. Na programu je celá řada zajímavých přednášek a workshopů. Letos je povinná registrace.

Ladislav Hagara | Komentářů: 0
21.1. 22:11 | Nová verze

Byla vydána verze 1.0.0 emulátoru terminálu Terminology postaveného nad EFL (Enlightenment Foundation Libraries). Přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 0
20.1. 17:00 | Nová verze

Byl vydán Docker 1.13. Přehled novinek na YouTube a v poznámkách k vydání na GitHubu. Docker umožňuje běh aplikací v softwarových kontejnerech (Wikipedia).

Ladislav Hagara | Komentářů: 7
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (11%)
 (2%)
 (73%)
 (3%)
 (10%)
Celkem 377 hlasů
 Komentářů: 29, poslední dnes 18:00
Rozcestník
Reklama

Dotaz: CRC

Jardík avatar 6.12.2013 21:48 Jardík | skóre: 40 | blog: jarda_bloguje
CRC
Přečteno: 451×
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á.
Věřím v jednoho Boha.

Řešení dotazu:


Odpovědi

AraxoN avatar 8.12.2013 00:30 AraxoN | skóre: 45 | blog: slon_v_porcelane | Košice
Rozbalit Rozbalit vše Re: CRC
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ť...
A fine is a tax for doing wrong. A tax is a fine for doing well.
Řešení 1× (Jardík (tazatel))
8.12.2013 01:23 Jardík
Rozbalit Rozbalit vše Re: CRC
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 avatar 8.12.2013 01:41 Jardík | skóre: 40 | blog: jarda_bloguje
Rozbalit Rozbalit vše Re: CRC
Jinak odkazy pro zájemce:
Věřím v jednoho Boha.

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.