Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > составить алгоритм расчета контрольной суммы

Автор: Hypertonyc 8.3.2011, 11:24

Здравствуйте.
Имеются клиент и сервер которые обмениваются данными по сети. На каждый пакет клиента сервер отвечает пакетом данных по 9 байт. Первые два и последний во всех пакетах одинаковые. Предпоследний - это контрольная сумма вычисленная по 3ему,4,5,6, и 7му байтам. Собственно в этом и проблема, никак не пойму алгоритма расчета. Очень прошу гляньте свежим взглядом, боюсь ответ на поверхности просто у меня "инерция мышления" уже.
Прилагаю исходник моей небольшой программки(C++) по расчету этой контр.суммы(думаю к ней комментариев не требуется) и список пакетов полученных с реального сервера этой системы.
P.S. большинство сумм в пакетах реально рассчитываются корректно по моему алгоритму, но в списке встречаются пакеты где контр.сумма=0x00(например #23808), а в моём алгоритме 0 ну никак не получится какие бы цифры не подставь(поэтому алгоритм отстой :()

Код


#include <windows.h>
#include <stdio.h>

WORD calc_crc(BYTE* bytes)
{
    WORD real_crc=0x0000;
    WORD tmp_crc=0x0000;

    for(int i=2;i<7;i++)
    {
        tmp_crc = bytes[i]<<(6-i);
        real_crc+=tmp_crc;        
    }
    while(real_crc>0xFF)
    {
        
        BYTE bt0=(real_crc & 0xFF00)>>8;
        BYTE bt1=(real_crc & 0x00FF);
        real_crc = bt0 + bt1;
    }
    
    return real_crc;
}

int main()
{
    BYTE bts[9]={0xaf,0xff,0x09,0x00,0x5c,0xff,0x00,0x00,0xfa};
    WORD crc=calc_crc(bts);
    printf("%#x\n",crc);
    scanf("%d",crc);
    return 0;
}

Автор: Hypertonyc 8.3.2011, 22:21

возможно не ясна причина моего внимания этому алгоритму.
так вот дело в том что я пишу свой сервер, который должен работать в том числе и с клиентами из описанной в первом посте системы.
схема работы системы:
- клиент шлет пакет с данными (N байт);
- сервер, приняв пакет, копирует заголовок принятого пакета (7 байт) рассчитывает по ним(7ми байтам) контрольную сумму(1 байт) и прикрепляет в конец пакета+конечный байт везде одинаковый(итого 9 байт);
- клиент приняв 9ти байтовый ответ шлет на сервер следующий пакет с данными;

так вот когда в мой сервер приходят данные он копирует шапку и по ней считает контр.сумму формирует 9байтовый ответ и шлет клиенту. Клиент не воспринимая ответ должным образом(т.к. ответ является некорректным(не совпадает тот самый предпоследний байт(контр.сумма)) ) вместо новых данных повторно посылает старые...и всё покругу пока не надоест smile

надеюсь что-нибудь понятно.

Автор: Hypertonyc 13.3.2011, 09:53

Автор: Peter 13.3.2011, 09:59

Кажется понятно. Неверно вычисляется контрольная сумма. Так?
Первое, что бросается в глаза при просмотре программы, это

Код

tmp_crc = bytes[i]<<(6-i);

tmp_crc имеет размер 2 байта, а bytes[i] - 1 байт. Если мы сдвигаем эту байтовую переменную влево (хоть вправо), всё равно получаем 1 байт. "Лишние" биты во второй байт не уползают, так как его нет. Если надо, чтобы они переползали во второй байт, надо однобайтную переменную сделать двухбайтной.

Код

tmp_crc = ((WORD)bytes[i])<<(6-i);

Автор: Hypertonyc 13.3.2011, 10:02

Цитата(Peter @ 13.3.2011, 09:59)

"Лишние" биты во второй байт не уползают, так как его нет.

ну вообще-то "уползают".(компилил в VC2008)

Добавлено через 1 минуту и 39 секунд
И вообще изначально мой алгоритм отстой из-за:

0xaf 0xff 0x09 0x80 0xd7 0x08 0x00 0x04 0xfa ((0x09*16 + 0x80*8 + 0xd7*4 + 0x08*2 + 0x00*1) -> 07fc > 0xFF -> 07+fc -> 0103 -> 0x04)
0xaf 0xff 0x09 0x84 0xd3 0x00 0x00 0x00 0xfa ((0x09*16 + 0x84*8 + 0xd3*4 + 0x00*2 + 0x00*1) -> 07fc > 0xFF -> 07+fc -> 0103 -> 0x00(!))

если все байты складывать, то получаются абсолютно одинаковые числа
что говорит о том что числа должны не просто складываться, а при каких-то условиях, либо там не сложение а другая операция,либо потом накладывается маска.

Автор: Peter 13.3.2011, 10:15

Именно, что не уползают. Считаем этот 23808-й пакет.
0x09 << 4 = 0x90
0x00 << 3 = 0x00
0x5c << 2 = 0x70
0xff << 1 = 0xfe
0x00 << 0 = 0x00
Складываем результаты (с учетом, что они присвоены двухбайтной переменной), получаем 0x01fe. Складываем первый и второй байты (0x01 и 0xfe) - получаем 0x0100. Преобразовываем его к одному байту (ведь только один байт контрольный) - получаем 0x00.

Добавлено через 6 минут и 19 секунд
Ошибся. Невнимательно посмотрел алгоритм. Там результат 0x0100 не к байту приводить надо, а опять на биты разбивать и складывать. И получится 0x0001.
Значит, чтобы получить 0x00, надо тело последнего цикла выполнять только 1 раз (т.е. цикла не будет) и результат приводить к байту.

Автор: Hypertonyc 13.3.2011, 10:31

Цитата(Peter @ 13.3.2011, 10:15)

Значит, чтобы получить 0x00, надо тело последнего цикла выполнять только 1 раз (т.е. цикла не будет) и результат приводить к байту.

а как тогда здесь 0х04 вышло?

0xaf 0xff 0x09 0x80 0xd7 0x08 0x00 0x04 0xfa

и еще интересно как это у Вас так : fe+01=100?

Автор: Peter 13.3.2011, 10:34

Да, здесь 0х04 не получается...
Значит, вопрос в том, чтобы подобрать алгоритм?

Автор: Hypertonyc 13.3.2011, 10:38

Цитата(Peter @ 13.3.2011, 10:34)

Значит, вопрос в том, чтобы подобрать алгоритм?

ИМЕННО!!!

Автор: Hypertonyc 14.3.2011, 16:27

Автор: Peter 14.3.2011, 17:26

В приложенном файле только два байта - пятый и шестой - изменяются, а третий и четвертый - нет. Так что какую-то зависимость от двух переменных подобрать можно, а от всех четырех - недостаточно информации.

Автор: Hypertonyc 14.3.2011, 21:05

увеличил количество пакетов и сделал автоматизированную проверку с выводом пакетов с неверной к.суммой в отдельный файл

списки пакетов:

http://rghost.ru/4766108 – все пакеты
http://rghost.ru/4766189 – результат программы(пакеты где контр.сумма рассчитана с ошибкой)

Код


#include <stdio.h>

unsigned short calc_crc(unsigned char* bytes)
{
    unsigned short real_crc=0x0000;
    unsigned short tmp_crc=0x0000;
    for(int i=2;i<7;i++)
    {
        tmp_crc = (bytes[i])<<(6-i);
        real_crc=(real_crc + tmp_crc);        
    }

    while(real_crc>0xFF)
    {      
        real_crc = ((real_crc & 0xFF00)>>8) + (real_crc & 0x00FF);
    }
    
    return real_crc;
}
void main(void)
{
    unsigned char bytes[9];
    int number=0,all=0,bad=0;
    unsigned short __CRC;

    FILE *file = fopen("list.txt","r");
    FILE *file_res = fopen("list_res.txt","w+");
    while(!feof(file))
    {
        all++;
        fscanf(file,"%d %hx %hx %hx %hx %hx %hx %hx %hx %hx\n",&number,&bytes[0],&bytes[1],&bytes[2],&bytes[3],&bytes[4],&bytes[5],&bytes[6],&bytes[7],&bytes[8]);

        __CRC = calc_crc(bytes);        
        if(bytes[7] != __CRC)
        {
            bad++;
            fprintf(file_res,"%06d 0x%02x 0x%02x 0x%02x 0x%02x 0x%02x 0x%02x 0x%02x 0x%02x 0x%02x : 0x%02x\n",bad,bytes[0],bytes[1],bytes[2],bytes[3],bytes[4],bytes[5],bytes[6],bytes[7],bytes[8],__CRC);
        }
    }
    printf("%03.2f%% not good\n",((float)bad/(float)all)*100.0);
    fclose(file_res);
    fclose(file);
    scanf("%d",&number);
}

p.s. результат программы 0.39% not good

Автор: Peter 15.3.2011, 10:43

Цифра 0.39% похожа на 1/256.
Я бы сравнил две соседние строчки, в первой из которых контрольный байт рассчитан правильно, а во второй - неправильно; и подумал бы, в чем может быть недостаток алгоритма.

Автор: volatile 16.3.2011, 13:06

Интересная головоломка!
Убил сегодня 2 часа разгадывая её. smile

Получилась вот такая процедурка
Не факт что на других данных будет все ок, но на тех данных что есть, всё гуд!
Проходит большой файл 'list.txt' (13Мб) = без единой ошибки.
Ловите

Код


typedef unsigned char u8;
typedef unsigned int ui;
inline ui shl (u8 val,int n){return u8((val<<n)|(val>>(8-n)));}
u8 calc_crc( const u8 * b)
{
   b += 2;
   ui crc = shl(b[0],4);
   crc += shl(b[1],3);
   crc += shl(b[2],2);
   crc -= (crc==259&&(b[2]&1))?(b[3]==0?crc:4):0;
   crc += shl(b[3],1);
   crc = (u8(crc))+(crc>>8);
   crc += (crc>>8);
   crc -= 2*(crc==2&&(b[3]&1)&&(!(b[3]==1&&(!(1&(b[2]+(b[1]>>7)))))));
   return u8(crc);
}

А задачка действительно очень интересная, даже поискал в нете, что-то подобное. Наткнулся только на ваши вопросы.
Если честно, думаю что решение должно быть конечно проще, но пока вот так вот, да и данных недостаточно.
Давно пытаетесь решить?