Хеш CRC32 строки Python

Используя существующий алгоритм примера C, я хочу сгенерировать правильный хэш CRC32 для строки в python. Однако я получаю неверные результаты. Я маскирую результат каждой операции и пытаюсь скопировать логику исходного алгоритма. Код C был предоставлен тем же веб-сайтом, на котором есть инструмент проверки хэша строки веб-страницы, поэтому он, вероятно, будет правильным.

Ниже приведен полный файл Python, включая код C в комментариях, которые он пытается имитировать. Вся необходимая информация находится в файле.

P_32 = 0xEDB88320
init = 0xffffffff
_ran = True
tab32 = []

def mask32(n):
    return n & 0xffffffff

def mask8(n):
    return n & 0x000000ff

def mask1(n):
    return n & 0x00000001

def init32():
    for i in range(256):
        crc = mask32(i)
        for j in range(8):
            if (mask1(crc) == 1):
                crc = mask32(mask32(crc >> 1) ^ P_32)
            else:
                crc = mask32(crc >> 1)
        tab32.append(crc)
    global _ran
    _ran = False

def update32(crc, char):
    char = mask8(char)
    t = crc ^ char
    crc = mask32(mask32(crc >> 8) ^ tab32[mask8(t)])
    return crc

def run(string):
    if _ran:
        init32()
    crc = init
    for c in string:
        crc = update32(crc, ord(c))
    print(hex(crc)[2:].upper())

check0 = "The CRC32 of this string is 4A1C449B"
check1 = "123456789" # CBF43926
run(check0) # Produces B5E3BB64
run(check1) # Produces 340BC6D9

# Check CRC-32 on http://www.lammertbies.nl/comm/info/crc-calculation.html#intr

"""
/* http://www.lammertbies.nl/download/lib_crc.zip */

#define                 P_32        0xEDB88320L
static int              crc_tab32_init          = FALSE;
static unsigned long    crc_tab32[256];

    /*******************************************************************\
    *                                                                   *
    *   unsigned long update_crc_32( unsigned long crc, char c );       *
    *                                                                   *
    *   The function update_crc_32 calculates a  new  CRC-32  value     *
    *   based  on  the  previous value of the CRC and the next byte     *
    *   of the data to be checked.                                      *
    *                                                                   *
    \*******************************************************************/

unsigned long update_crc_32( unsigned long crc, char c ) {

    unsigned long tmp, long_c;

    long_c = 0x000000ffL & (unsigned long) c;

    if ( ! crc_tab32_init ) init_crc32_tab();

    tmp = crc ^ long_c;
    crc = (crc >> 8) ^ crc_tab32[ tmp & 0xff ];

    return crc;

}  /* update_crc_32 */

    /*******************************************************************\
    *                                                                   *
    *   static void init_crc32_tab( void );                             *
    *                                                                   *
    *   The function init_crc32_tab() is used  to  fill  the  array     *
    *   for calculation of the CRC-32 with values.                      *
    *                                                                   *
    \*******************************************************************/

static void init_crc32_tab( void ) {

    int i, j;
    unsigned long crc;

    for (i=0; i<256; i++) {

        crc = (unsigned long) i;

        for (j=0; j<8; j++) {

            if ( crc & 0x00000001L ) crc = ( crc >> 1 ) ^ P_32;
            else                     crc =   crc >> 1;
        }

        crc_tab32[i] = crc;
    }

    crc_tab32_init = TRUE;

}  /* init_crc32_tab */
"""

python hash crc32 bitmask
person Timothy Swan    schedule 14.01.2016    source источник
comment
из zipfile import crc32 вам не подходит?   -  person Yoav Glazner    schedule 15.01.2016
comment
Что ж, поздравляю; вы точно воспроизвели этот код C, потому что код C производит точно такой же результат.   -  person Tom Zych    schedule 15.01.2016
comment
@YoavGlazner Кажется, я не могу найти хорошую документацию по этому поводу.   -  person Timothy Swan    schedule 15.01.2016
comment
@TomZych Я бы прокомментировал исходный веб-сайт, но я нигде не могу найти функции «создать новый пост» или «ответить», хотя там написано, что у меня есть доступ для этого. Я бы не смог разместить ссылку здесь, потому что правила их веб-сайта гласят, что ссылки в сообщениях или комментариях запрещены.   -  person Timothy Swan    schedule 15.01.2016
comment
Вы имеете в виду, что хотите опубликовать, что код C дает ответы, которые не совпадают? Просто скомпилируйте его сами, затем вы можете опубликовать, что вы его нашли сами. Я подозреваю, что это может быть проблема порядка байтов.   -  person Tom Zych    schedule 15.01.2016

Ответы (1)


arrow_upward
2
arrow_downward

В текущей реализации есть только одна ошибка, и исправление на самом деле представляет собой всего одну строку кода в конце вашей функции запуска, а именно:

crc = crc ^ init

Что, если добавить к вашей функции запуска, выглядит так:

def run(string):
    if _ran:
        init32()
    crc = init
    for c in string:
        crc = update32(crc, ord(c))
    crc = crc ^ init    
    print(hex(crc)[2:].upper())

Это даст вам правильные результаты, которые вы ожидаете. Причина, по которой это необходимо, заключается в том, что после того, как вы закончите обновление CRC32, завершение его будет XOR с ним с 0xFFFFFFFF. Поскольку у вас были только функции инициализации и обновления, а не финализация, вы были в одном шаге от фактического crc.

Другая реализация C, которая немного более прямолинейна, это в этом немного легче увидеть весь процесс. Единственное, что немного неясно, это то, что init poly ~ 0x0 тот же (0xFFFFFFFF).

person Dom    schedule 14.01.2016
comment
Любопытный. Насколько быстрее реализация C? Казалось, что мой подход к Python займет недели, но я думаю, что кто-то сказал, что они нашли собственный хэш с помощью C за пару минут. - person Timothy Swan; 11.03.2016