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 01:44 | Zajímavý projekt

Kampaň na podporu chytrého telefonu Librem 5, jenž by měl respektovat bezpečnost, svobodu a soukromí uživatelů, úspěšně skončila. Bylo vybráno více než 2,1 milionu dolarů, tj. cíl kampaně byl splněn na více než 141 %. Objednáno bylo cca 3 000 telefonů. Telefon Librem 5 by měl být k dispozici v lednu 2019.

Ladislav Hagara | Komentářů: 1
včera 21:11 | Komunita

Ke zhlédnutí jsou videozáznamy přednášek z konferencí All Systems Go! (media.ccc.de) a GStreamer Conference 2017 (ubicast.tv) konaných o víkendu 21. a 22. října. All Systems Go! v Berlíně a GStreamer Conference 2017 v Praze.

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

MojeFedora.cz informuje (en), že Fedora 27 přináší snadný přístup k Red Hat Enteprise Linuxu. Virtualizační nástroj Boxy nyní umožňuje jednoduše stáhnout a nainstalovat Red Hat Enterprise Linux, který je pro vývojáře zdarma. Vytvořit lze neomezené množství virtuálních mašin s RHEL.

Ladislav Hagara | Komentářů: 1
včera 19:00 | Komunita

Konsorcium Linux Foundation oficiálně představilo licence pro komunitní otevřená data Community Data License Agreement (CDLA). První licence je copyleftová CDLA-Sharing a druhá permisivní CDLA-Permissive. Odpovědi na často kladené otázky ve FAQ.

Ladislav Hagara | Komentářů: 0
včera 13:55 | Pozvánky

Spolek OpenAlt zve příznivce otevřených technologií a otevřeného přístupu na 145. pražský sraz, který proběhne ve čtvrtek 26. října od 18:00 hodin v karlínském Pivovarském klubu. Najdete jej kousek od metra Florenc na adrese Křižíkova 17, Praha 8. Jedná se o poslední sraz před konferencí OpenAlt 2017, jež proběhne o víkendu 4. a 5. listopadu 2017 na FIT VUT v Brně. Běží registrace účastníků.

Ladislav Hagara | Komentářů: 0
včera 06:00 | Zajímavý software

Byla vydána verze 0.56 open source platformy Home Assistant (GitHub) pro monitorování a řízení inteligentní domácnosti naprogramované v programovacím jazyce Python verze 3 a bežící také například na Raspberry Pi. Pro vyzkoušení je k dispozici demo [reddit].

Ladislav Hagara | Komentářů: 0
22.10. 16:55 | Nová verze

Byla vydána verze 1.0 klienta F-Droid určeného pro instalaci aplikací do Androidu ze softwarového repozitáře F-Droid (Wikipedie), alternativy k Google Play, nabízející pouze svobodný a otevřený software. Podrobnosti v přehledu změn [Hacker News].

Ladislav Hagara | Komentářů: 7
22.10. 00:55 | Nová verze

Po téměř 13 měsících vývoje od verze 0.11.0 byla vydána verze 0.12.0 hardwarově nenáročného desktopového prostředí LXQt (Lightweight Qt Desktop Environment, Wikipedie) vzniklého sloučením projektů Razor-qt a LXDE. Přehled novinek v příspěvku na blogu.

Ladislav Hagara | Komentářů: 10
21.10. 12:33 | Zajímavý software

Článek ne Medium představuje nejnovější stabilní verzi 2.0 svobodné decentralizované mikroblogovací platformy a sociální sítě podobné Twitteru Mastodon (Wikipedie). Detailní přehled novinek na GitHubu [Hacker News].

Ladislav Hagara | Komentářů: 0
21.10. 06:00 | Komunita

V Praze na půdě Elektrotechnické fakulty ČVUT dnes probíhá RT-Summit 2017 – setkání vývojářů linuxového jádra a uživatelů jeho real-time verze označované jako preempt-rt. Přednášky lze sledovat online na YouTube.

Ladislav Hagara | Komentářů: 0
Jak se vás potenciálně dotkne trend odstraňování analogového audio konektoru typu 3,5mm jack z „chytrých telefonů“?
 (10%)
 (1%)
 (0%)
 (1%)
 (75%)
 (12%)
Celkem 236 hlasů
 Komentářů: 8, poslední 22.10. 23:02
    Rozcestník

    Dotaz: CRC

    Jardík avatar 6.12.2013 21:48 Jardík | skóre: 40 | blog: jarda_bloguje
    CRC
    Přečteno: 456×
    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.