Ещё один способ расчёта CRC16

[uni]

Доброго, уважаемые форумчане.

Интересует конкретная реализация алгоритма расчёта 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();
    }    
}

[Dmitriy40]

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

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

[uni]

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

[Dmitriy40]

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

[uni]

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

Используется синтаксис 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() ) );
        }
    }
}