Определение алгоритма CRC из данных + CRC - встроенное приложение. - PullRequest
Новая
       12

Определение алгоритма CRC из данных + CRC - встроенное приложение.

5 голосов
/ 30 декабря 2008

У меня есть набор данных, защищенных 16-битными контрольными суммами, которые мне нужно исправить. Местоположение контрольной суммы известно, точные области, на которых они рассчитаны, и точный алгоритм, используемый для их расчета, не известны. 16 бит, LSB первый. Я подозреваю, что это своего рода 16-битный CRC, но я не смог найти код, который фактически вычисляет контрольные суммы.

Пример: 

00    4E00FFFF26EC14091E00A01830393630  
10    30313131313030393030363030313030  
20    30303131313030393030363030313030  
30    30303131313030393030363030313030  
40    3030FFFF225E363436304D313037**0CE0**  
50    64000000000000008080808080800000  
60    00000000**BE6E**FC01E001EB0013010500

Контрольные суммы хранятся в 4E и 64. Я не знаю, рассчитываются ли они, начиная со смещения в первом слове в начале каждого раздела данных или начиная с этого, или во всем диапазоне. Я попробовал несколько общих алгоритмов CRC и полиномов без удачи. Там нет ссылки или спецификации для этого приложения.

Вот еще один раздел данных с различными CRC для сравнения. 

00    4E00FFFF26C014091600A01030393132  
10    30313131313030393030313230313030  
20    30303131313030393030313230313030  
30    30303131313030393030313230313030  
40    3030FFFF225E343231324F313044**8348**  
50    64000000000000008080808080800000  
60    00000000**72F8**E001EB00130105000E01

Мой вопрос: кто-нибудь может определить алгоритм? Есть ли способ рассчитать полином CRC и другие факторы из данных и CRC?

Спасибо!

Редактировать:

Поиск моей разборки для общего многочлена CRC16 0xA001 выявил эту функцию: 

34F86 ; =============== S U B R O U T I N E =======================================
34F86
34F86
34F86 Possible_Checksum:                    ; CODE XREF: MEM_EXT_4:00034FEEP
34F86                                         ; MEM_EXT_4:0003503AP ...
34F86                 mov     [-r0], r9       ; Move Word
34F88                 mov     r4, r12         ; Move Word
34F8A                 mov     r5, r13         ; Move Word
34F8C                 shr     r4, #14         ; Shift Right
34F8E                 shl     r5, #2          ; Shift Left
34F90                 or      r5, r4          ; Logical OR
34F92                 mov     r4, r12         ; Move Word
34F94                 mov     DPP0, r5        ; Move Word
34F98                 and     r4, #3FFFh      ; Logical AND
34F9C                 movb    rl3, [r4]       ; Move Byte
34F9E                 mov     DPP0, #4        ; Move Word
34FA2                 movbz   r9, rl3         ; Move Byte Zero Extend
34FA4                 mov     r15, #0         ; Move Word
34FA6
34FA6 loc_34FA6:                              ; CODE XREF: MEM_EXT_4:00034FC8j
34FA6                 mov     r4, [r14]       ; Move Word
34FA8                 xor     r4, r9          ; Logical Exclusive OR
34FAA                 and     r4, #1          ; Logical AND
34FAC                 jmpr    cc_Z, loc_34FBA ; Relative Conditional Jump
34FAE                 mov     r4, [r14]       ; Move Word
34FB0                 shr     r4, #1          ; Shift Right
34FB2                 xor     r4, #0A001h     ; Logical Exclusive OR
34FB6                 mov     [r14], r4       ; Move Word
34FB8                 jmpr    cc_UC, loc_34FC0 ; Relative Conditional Jump
34FBA ; ---------------------------------------------------------------------------
34FBA
34FBA loc_34FBA:                              ; CODE XREF: MEM_EXT_4:00034FACj
34FBA                 mov     r4, [r14]       ; Move Word
34FBC                 shr     r4, #1          ; Shift Right
34FBE                 mov     [r14], r4       ; Move Word
34FC0
34FC0 loc_34FC0:

Ответы [ 2 ]

3 голосов
/ 31 декабря 2008

Код, который вы отправили из loc_34FA6 вниз, в основном следующий: 

unsigned short
crc16_update(unsigned short crc, unsigned char nextByte)
{
    crc ^= nextByte;

    for (int i = 0; i < 8; ++i) {
        if (crc & 1)
            crc = (crc >> 1) ^ 0xA001;
        else
            crc = (crc >> 1);
    }

    return crc;
}

Это CRC-16 с полиномом 0xA001. Как только вы узнаете диапазон данных, для которых применяется CRC-16, вы инициализируете CRC равным 0xFFFF и вызываете эту функцию для каждого байта в последовательности. Сохраните возвращаемое значение и передайте его в следующий раз. Значение, возвращаемое в конце, является вашим окончательным CRC.

Я не уверен, что делает пролог ...

1 голос
/ 07 января 2009

В более общем смысле, частью концепции CRC является то, что когда вы вычисляете CRC некоторого файла данных, а затем добавляете CRC в конце, вы получаете файл, CRC которого представляет собой некоторое значение, которое зависит от длины файл, но не его содержимое. (Для некоторых алгоритмов CRC это даже не зависит от длины файла.)

Итак, если вы подозреваете, что приложение, которое вы пытаетесь перепроектировать, использует, скажем, CRC16, и у вас есть программа, которая вычисляет CRC16, и у вас есть несколько выборок одинаковой длины, просто вычислите CRC16 этих файлов данных. (которые включают контрольную сумму). Если он возвращается с одними и теми же данными контрольной суммы каждый раз (для файлов одинаковой длины), то они должны содержать контрольную сумму CRC с использованием одинаковой ширины и полинома.

Например, однажды мне пришлось перепроектировать некоторые файлы, в которых, по мнению разработчика, он был умен, изменив алгоритм CRC32, изменив две константы. Мне не нужно было находить объектный код, который проверял контрольную сумму, разбирать ее, а затем выяснять ее трудным путем. Этот простой тест прибил его.

...