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 20:55 | Nová verze

V červenci loňského roku vydal Microsoft alfa verzi nového Skypu pro Linux využívajícího WebRTC. Dnes byla vydána beta verze Skypu pro Linux 5.0. Nově lze uskutečnit videohovory ze Skypu pro Linux také na aktuální verze Skypu pro Android, iOS, Windows i Mac.

Ladislav Hagara | Komentářů: 0
dnes 20:10 | Nová verze

Byla vydána verze 1.5 open source systému pro filtrování nevyžádané pošty Rspamd (GitHub, ChangeLog). Z novinek lze zmínit například nový MIME parser. Místo libiconv se nově používá libicu. Přepracováno bylo webové rozhraní nebo také modul Lua TCP.

Ladislav Hagara | Komentářů: 0
dnes 09:44 | Pozvánky

Již tento víkend 4. a 5. března proběhne v Praze na Karlově náměstí 13 konference InstallFest 2017. Na programu je celá řada zajímavých přednášek a workshopů. Jaké linuxové distribuce používají návštěvníci chystající se na konferenci? Odpověď na Twitteru.

Ladislav Hagara | Komentářů: 3
dnes 08:44 | Nová verze

Minulý týden byla vydána verze 8.0.0 minimalistické linuxové distribuce (JeOS, Just enough Operating System) pro Kodi (dříve XBMC) a multimediálního centra LibreELEC (Libre Embedded Linux Entertainment Center). Jedná se o fork linuxové distribuce OpenELEC (Open Embedded Linux Entertainment Center). LibreELEC 8.0.0 přichází s Kodi 17.0 Krypton.

Ladislav Hagara | Komentářů: 0
včera 12:30 | IT novinky

Nadace Raspberry Pi představila (YouTube) Raspberry Pi Zero W. Jedná se o vylepšenou verzi miniaturního počítače Raspberry Pi Zero s Wi-Fi a Bluetooth. Koupit jej lze za 10 dolarů. V prodeji je také oficiální krabička.

Ladislav Hagara | Komentářů: 17
včera 00:55 | Komunita

Pocket (dříve Read It Later) (Wikipedie) je oblíbená služba umožňující uložit si článek z webu na později. V červnu 2015 s vydáním Firefoxu 38.0.5 se do té doby doplněk Pocket stal integrovanou součásti Firefoxu, a to i přes odpor celé řady uživatelů tohoto webového prohlížeče. Mozilla po měsících ustoupila a z integrované součásti se stal opět doplněk. Včera bylo oznámeno, že Mozilla službu Pocket kupila (Mozilla Blog, Pocket Blog).

Ladislav Hagara | Komentářů: 20
27.2. 23:55 | Pozvánky

Tentokrát jsme si pro vás připravili neobvyklou akci. Ve středu 1. 3. v 17:30 nás přivítá sdružení CZ.NIC ve svých prostorách v Milešovské ulici číslo 5 na Praze 3, kde si pro nás připravili krátkou prezentaci jejich činnosti.

… více »
xkucf03 | Komentářů: 0
27.2. 18:30 | Komunita

Jednodeskový počítač Raspberry Pi slaví již 5 let. Prodej byl spuštěn 29. února 2012. O víkendu proběhne v Cambridgi velká narozeninová party. Na YouTube bylo při této příležitosti zveřejněno video představující zajímavé projekty postavené na Raspberry Pi.

Ladislav Hagara | Komentářů: 3
27.2. 18:30 | Nová verze

Byla vydána verze 2017.1.1 svobodného multiplatformního leteckého simulátoru FlightGear. Kódový název a výchozí letiště této verze je Bergen. Přehled novinek v Changelogu.

Ladislav Hagara | Komentářů: 0
27.2. 10:50 | Zajímavý software

Mozilla.cz informuje o dvou nových experimentálních funkcích v programu Firefox Test Pilot (zprávička). Snooze Tabs slouží k odkládání panelů na později. Pokud vám někdo pošle odkaz, ale vy nemáte čas si stránku hned přečíst, můžete si naplánovat otevření panelu na později. Stačí kliknout na tlačítko a vybrat, kdy chcete panel otevřít. Firefox panel schová a ve vybraný čas znovu otevře. Pulse umožňuje ohodnotit, jak dobře stránka funguje, např. jak rychle se ve Firefoxu načetla. Podle nasbíraných hodnocení pak bude Mozilla prohlížeč ladit.

Ladislav Hagara | Komentářů: 10
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (13%)
 (2%)
 (72%)
 (3%)
 (10%)
Celkem 744 hlasů
 Komentářů: 72, poslední dnes 11:16
    Rozcestník

    Dotaz: CRC

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