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í
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 17:02 | Pozvánky
Přijďte si popovídat o open source obecně a openSUSE konkrétně s dalšími uživateli a vývojáři. Oslava nového vydání openSUSE Leap se uskuteční 16. prosince od 17:00 v nových prostorách firmy SUSE v Praze. K dispozici bude nějaké občerstvení a DVD pro ty, kdo je sbírají nebo ještě mají mechaniku. Po párty v kanceláři se bude pokračovat v některé z hospod v okolí.
Miška | Komentářů: 0
dnes 14:55 | Zajímavý software

Byla vydána verze Alpha 1.0 otevřeného operačního systému pro chytré hodinky AsteroidOS. Podporovány jsou hodinky LG G Watch, LG G Watch Urbane, Asus ZenWatch 2 a Sony Smartwatch 3. Ukázka ovládání hodinek na YouTube. Jaroslav Řezník přednášel o AsteroidOS na chytrých hodinkách (videozáznam) na letošní konferenci OpenAlt.

Ladislav Hagara | Komentářů: 0
dnes 13:30 | Zajímavý software

Byly uvolněny zdrojové kódy známé rogue-like hry DoomRL. Počátky hry jsou v roce 2002. Je napsána ve FreePascalu a zdrojový kód je nyní k dispozici na GitHubu pod licencí GNU GPL 2.0. Autor pracuje na nové hře Jupiter Hell, která je moderním nástupcem DoomRL a na jejíž vývoj shání peníze prostřednictvím Kickstarteru.

Blaazen | Komentářů: 0
dnes 13:15 | Pozvánky

Přijďte s námi oslavit vydání Fedory 25. Na programu budou přednášky o novinkách, diskuse, neřízený networking atd. Release Party se bude konat 16. prosince v prostorách společnosti Etnetera. Na party budou volně k dispozici také propagační materiály, nová DVD s Fedorou 25 a samozřejmě občerstvení. Přednášky budou probíhat v češtině. Pro více informací se můžete podívat na web MojeFedora.cz. Jen připomínám, že tentokrát jsme zavedli

… více »
frantisekz | Komentářů: 0
včera 16:38 | Komunita

Byly zveřejněny videozáznamy přednášek a workshopů z letošní konference OpenAlt konané 5. a 6. listopadu v Brně. K videozáznamům lze přistupovat ze stránky na SuperLectures nebo přes program konference, detaily o vybrané přednášce nebo workshopu a dále kliknutím na ikonku filmového pásu. Celkově bylo zpracováno 65 hodin z 89 přednášek a workshopů.

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

Bylo oznámeno, že bude proveden bezpečnostní audit zdrojových kódů open source softwaru pro implementaci virtuálních privátních sítí OpenVPN. Audit provede Matthew D. Green (blog), uznávaný kryptolog a profesor na Univerzitě Johnse Hopkinse. Auditována bude verze 2.4 (aktuálně RC 1, stabilní verze je 2.3.14). Audit bude financován společností Private Internet Access [reddit].

Ladislav Hagara | Komentářů: 4
včera 06:00 | Komunita

Na YouTube byl publikován Blender Institute Reel 2016, ani ne dvouminutový sestřih z filmů, které vznikly za posledních 10 let díky Blender Institutu. V institutu aktuálně pracují na novém filmu Agent 327. Dění kolem filmu lze sledovat na Blender Cloudu. Videoukázka Agenta 327 z června letošního roku na YouTube.

Ladislav Hagara | Komentářů: 0
včera 01:02 | Zajímavý článek

Minulý týden byly vydány verze 1.2.3 a 1.1.7 webového poštovního klienta Roundcube. V oznámení o vydání bylo zmíněno řešení bezpečnostního problému nalezeného společností RIPS a souvisejícího s voláním funkce mail() v PHP. Tento týden byly zveřejněny podrobnosti. Útočník mohl pomocí speciálně připraveného emailu spustit na serveru libovolný příkaz. Stejně, jak je popsáno v článku Exploit PHP’s mail() to get remote code execution z roku 2014.

Ladislav Hagara | Komentářů: 1
8.12. 16:00 | Nová verze

Byla vydána verze 0.98 svobodného nelineárního video editoru Pitivi. Z novinek lze zmínit například přizpůsobitelné klávesové zkratky. Videoukázka práce s nejnovější verzí Pitivi na YouTube.

Ladislav Hagara | Komentářů: 1
8.12. 15:00 | Zajímavý software

Stop motion je technika animace, při níž je reálný objekt mezi jednotlivými snímky ručně upravován a posouván o malé úseky, tak aby po spojení vyvolala animace dojem spojitosti. Jaký software lze pro stop motion použít na Linuxu? Článek na OMG! Ubuntu! představuje Heron Animation. Ten bohužel podporuje pouze webové kamery. Podpora digitálních zrcadlovek je začleněna například v programu qStopMotion.

Ladislav Hagara | Komentářů: 5
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 808 hlasů
 Komentářů: 50, poslední 29.11. 15:50
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: 446×
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.