2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Ещё один способ расчёта CRC16
Сообщение10.02.2020, 09:17 
Аватара пользователя


09/05/06
115
Доброго, уважаемые форумчане.

Интересует конкретная реализация алгоритма расчёта CRC16 для полинома 0x1021 на базе имеющегося, приведённого в этой статье:

Простой и эффективный расчёт Modbus CRC16 в ПЛК и МК без побитового сдвига и таблиц

Ниже там в комментариях я привёл вариант для c#, но сейчас мне нужно то же самое, но для другого полинома. Не могу понять как именно получились промежуточные константы из исходного полинома. Пробовал сдвигать туда-сюда, но стандартная проверка со строкой "123456789" и начальным значением 0xFFFF не получается пока. Тут нужно немного дискретной математики, а я, признаться, не совсем до конца понял как именно нужно сдвигать полином вместо самого текущего значения crc.

Помогите найти константы для алгоритма.

код: [ скачать ] [ спрятать ]
Используется синтаксис C#
/*  
@echo off && cls
set dotnet=%windir%\Microsoft.NET\Framework
for %%n in (2.0.50727,3.5,4.0.30319) do if exist "%dotnet%\v%%n\csc.exe" set csc="%dotnet%\v%%n\csc.exe"
( %csc% /nologo /out:"%~0.exe" %0 && "%~0.exe" ) && del "%~0.exe"
exit
*/
 
using System;
using System.Collections.Generic;

class Program
{
    public static byte[] Crc16( byte[] bytes )
    {
        int hi = 0xFF, lo = 0xFF;

        foreach ( var t in bytes )
        {
            var b = ( byte ) ( lo ^ t );

            lo = hi; hi = b;

            if ( ( hi & 0x01 ) != 0 ) { hi ^= 0x02; lo ^= 0x40; }
            if ( ( hi & 0x02 ) != 0 ) { hi ^= 0x04; lo ^= 0x80; }
            if ( ( hi & 0x04 ) != 0 ) hi ^= 0x09;
            if ( ( hi & 0x08 ) != 0 ) hi ^= 0x12;
            if ( ( hi & 0x10 ) != 0 ) hi ^= 0x24;
            if ( ( hi & 0x20 ) != 0 ) hi ^= 0x48;
            if ( ( hi & 0x40 ) != 0 ) hi ^= 0x90;
            if ( ( hi & 0x80 ) != 0 ) { hi ^= 0x20; lo ^= 0x01; }
        }

        return new [] { ( byte ) lo, ( byte ) hi };
    }
       
    static void Main( string[] args )
    {
        var query = new List<byte> { 0x01, 0x03, 0x00, 0x02, 0x00, 0x01 };

        query.AddRange( Crc16( query.ToArray() ) );

        Console.WriteLine( BitConverter.ToString( query.ToArray() ) );

        Console.ReadKey();
    }    
}

 Профиль  
                  
 
 Re: Ещё один способ расчёта CRC16
Сообщение10.02.2020, 10:17 
Заслуженный участник


20/08/14
11062
Россия, Москва

(Как я бы поступил в таком случае)

Я бы взял любое ненулевое начальное значение CRC16, посчитал бы его значение обычным способом (битовым сдвигом и XOR) при подаче 8 разных байтов на вход (с одним битом в байте), сделал бы XOR нового и начального значения — и получил бы желаемые маски вообще без погружения в математику. ;-) Я так часто заполняю таблицы при старте программ. Тупо, но надёжно.

 Профиль  
                  
 
 Re: Ещё один способ расчёта CRC16
Сообщение11.02.2020, 10:54 
Аватара пользователя


09/05/06
115
Похоже, что так просто не получится. Прочитал, что "CRC-CCITT отличается от классического CRC-16, так как использует другой полином и порядок данных". Начал код с циклами сравнивать и обнаружил такую подставу. Для modbus'а и моего случая сдвиг в разные стороны и порядок обхода бит также. Раньше не обратил на это внимание. Ещё поиграюсь, может выйдет каменный цветок.

 Профиль  
                  
 
 Re: Ещё один способ расчёта CRC16
Сообщение11.02.2020, 11:44 
Заслуженный участник


20/08/14
11062
Россия, Москва
Насколько помню по своим разбирательствам, если не брать пред- и пост-условия (инициализацию значения CRC и финальный XOR после расчёта), то возможны лишь четыре варианта: куда сдвигать CRC и в каком порядке анализировать входные биты, причём они разбиваются на две пары с "зеркальными" полиномами. При битовой реализации их можно проверить все довольно легко и быстро. А вообще да, это засада, надо внимательнее смотреть алгоритм расчёта (я например для себя люблю инициализировать значение CRC хитрым образом, не константой, например длиной пакета).

 Профиль  
                  
 
 Re: Ещё один способ расчёта CRC16
Сообщение11.02.2020, 19:08 
Аватара пользователя


09/05/06
115
Пришлось думать :) нет, чтобы по-человечески описать.

код: [ скачать ] [ спрятать ]
Используется синтаксис C#
using System;
using System.Collections.Generic;

namespace Crc16
{
    class Program
    {
        public static byte[] Crc16( byte[] bytes )
        {
            int hi = 0xFF, lo = 0xFF;

            foreach ( var b in bytes )
            {
                var t = ( byte ) ( lo ^ b );

                lo = hi;
                hi = t;

                // Место флага (старшего разряда) занимает появляющийся при сдвиге влево нулевой разряд.
                // Его комбинация (XOR) с младшим разрядом полинома 0x1021 должна всегда давать единицу.
                // Поскольку флаг всегда равен единице, то мы должны обнулить младший разряд полинома,
                // чтобы получить результат итерации аналогичный другим методам.

                // По-простому: мы двигаем на каждой из 8 итераций не текущее значение crc, а полином, но
                // в обратную сторону. Причём сдвиг циклический, т.к. в оригинале при сдвиге влево каждый
                // раз получается один нулевой битик. Мы суём его на место старшего разряда, который нас
                // безвременно покидает.

                // 0001000000100001 1021 - полином

                // Расчёт констант:
                // 0000 1000 0001 0000 (0x1021 >> 1) & 0x7FFF = 0x0810
                // 0000 0100 0000 1000 (0x1021 >> 2) & 0xBFFF = 0x0408
                // 0000 0010 0000 0100 (0x1021 >> 3) & 0xDFFF = 0x0204
                // 0000 0001 0000 0010 (0x1021 >> 4) & 0xEFFF = 0x0102
                // 0000 0000 1000 0001 (0x1021 >> 5) & 0xF7FF = 0x0081
                // 1000 0000 0100 0000 (0x1021 >> 6) & 0xFBFF = 0x8040
                // 0100 0000 0010 0000 (0x1021 >> 7) & 0xFDFF = 0x4020
                // 0010 0000 0001 0000 (0x1021 >> 8) & 0xFEFF = 0x2010
                if ( ( hi & 0x80 ) != 0 ) { hi ^= 0x08; lo ^= 0x10; }
                if ( ( hi & 0x40 ) != 0 ) { hi ^= 0x04; lo ^= 0x08; }
                if ( ( hi & 0x20 ) != 0 ) { hi ^= 0x02; lo ^= 0x04; }
                if ( ( hi & 0x10 ) != 0 ) { hi ^= 0x01; lo ^= 0x02; }
                if ( ( hi & 0x08 ) != 0 ) { hi ^= 0x00; lo ^= 0x81; }
                if ( ( hi & 0x04 ) != 0 ) { hi ^= 0x80; lo ^= 0x40; }
                if ( ( hi & 0x02 ) != 0 ) { hi ^= 0x40; lo ^= 0x20; }
                if ( ( hi & 0x01 ) != 0 ) { hi ^= 0x20; lo ^= 0x10; }
            }

            return new [] { ( byte ) lo, ( byte ) hi };
        }
           
        static void Main( string[] args )
        {
            var query = new List<byte> { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39 };

            query.AddRange( Crc16( query.ToArray() ) );

            // Вывод: 31-32-33-34-35-36-37-38-39-29-B1
            Console.WriteLine( BitConverter.ToString( query.ToArray() ) );
        }
    }
}
 

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group