Что такое эквивалент "cksum" в Python для очень больших файлов и как он работает?

Question

У меня проблема в том, что мне нужно проверять огромные сжатые файлы после загрузки (обычно более 10-20 ГБ на файл) по контрольным суммам, которые, по-видимому, были сгенерированы с помощью cksum

(Чтобы быть более точным: моему сценарию python необходимо загружать большие сжатые файлы с ftp-сервера ncbi, который должен был предоставлять контрольные суммы md5 для проверки загрузок, но вместо этого предоставлял только некоторые другие неопределенные значения хэша / контрольной суммы файла. После некоторых проб и ошибок Я обнаружил, что эти контрольные суммы были идентичны выводам инструмента unix cksum, который, по-видимому, генерирует контрольные суммы CRC. Итак, чтобы сравнить / проверить их, мне нужно сгенерировать cksum-эквивалентные контрольные суммы для загруженных файлов.)

Похоже, что инструмент unix cksum дает совершенно разные значения контрольной суммы, чем предполагаемый эквивалентный инструмент unix crc32 (или питон zlib.crc32()функция, если на то пошло). Когда я искал проблему в Google, я не мог понять объяснений, почему это происходит, тем более что они кажутся идентичными в некоторых системах? Может быть, это потому, что я работаю на 64-битной системе (но тогда: кто не работает в настоящее время)?

Используя встроенные модули Python, я могу легко генерировать контрольные суммы md5- и CRC32, но ни один из них не эквивалентен выходу cksum, ни в десятичном, ни в шестнадцатеричном представлении.

Я нашел здесь предыдущий пост о stackru, указывающий на фрагмент, который, кажется, решает эту проблему. Но хотя он работает с небольшими файлами, A.) Я не понимаю ни слова, поэтому мне сложно его адаптировать и B.) он не работает с большими файлами.

для полноты: вот фрагмент (версия python3):

#!/usr/bin/env python
import sys

crctab = [ 0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc,
        0x17c56b6b, 0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f,
        0x2f8ad6d6, 0x2b4bcb61, 0x350c9b64, 0x31cd86d3, 0x3c8ea00a,
        0x384fbdbd, 0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9,
        0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75, 0x6a1936c8,
        0x6ed82b7f, 0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3,
        0x709f7b7a, 0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e,
        0x95609039, 0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,
        0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81, 0xad2f2d84,
        0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d, 0xd4326d90, 0xd0f37027,
        0xddb056fe, 0xd9714b49, 0xc7361b4c, 0xc3f706fb, 0xceb42022,
        0xca753d95, 0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,
        0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077,
        0x30476dc0, 0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c,
        0x2e003dc5, 0x2ac12072, 0x128e9dcf, 0x164f8078, 0x1b0ca6a1,
        0x1fcdbb16, 0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,
        0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde, 0x6b93dddb,
        0x6f52c06c, 0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08,
        0x571d7dd1, 0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d,
        0x40d816ba, 0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e,
        0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692, 0x8aad2b2f,
        0x8e6c3698, 0x832f1041, 0x87ee0df6, 0x99a95df3, 0x9d684044,
        0x902b669d, 0x94ea7b2a, 0xe0b41de7, 0xe4750050, 0xe9362689,
        0xedf73b3e, 0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,
        0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683,
        0xd1799b34, 0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59,
        0x608edb80, 0x644fc637, 0x7a089632, 0x7ec98b85, 0x738aad5c,
        0x774bb0eb, 0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f,
        0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53, 0x251d3b9e,
        0x21dc2629, 0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5,
        0x3f9b762c, 0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48,
        0x0e56f0ff, 0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,
        0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2,
        0xe6ea3d65, 0xeba91bbc, 0xef68060b, 0xd727bbb6, 0xd3e6a601,
        0xdea580d8, 0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604,
        0xc960ebb3, 0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,
        0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6,
        0x9ff77d71, 0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad,
        0x81b02d74, 0x857130c3, 0x5d8a9099, 0x594b8d2e, 0x5408abf7,
        0x50c9b640, 0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,
        0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8, 0x68860bfd,
        0x6c47164a, 0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e,
        0x18197087, 0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b,
        0x0fdc1bec, 0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088,
        0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654, 0xc5a92679,
        0xc1683bce, 0xcc2b1d17, 0xc8ea00a0, 0xd6ad50a5, 0xd26c4d12,
        0xdf2f6bcb, 0xdbee767c, 0xe3a1cbc1, 0xe760d676, 0xea23f0af,
        0xeee2ed18, 0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,
        0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5,
        0x9e7d9662, 0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06,
        0xa6322bdf, 0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03,
        0xb1f740b4 ]

UNSIGNED = lambda n: n & 0xffffffff

def memcrc(b):
    n = len(b)
    i = c = s = 0
    for c in b:
        tabidx = (s>>24)^c
        s = UNSIGNED((s << 8)) ^ crctab[tabidx]
    while n:
        c = n & 0o0377
        n = n >> 8
        s = UNSIGNED(s << 8) ^ crctab[(s >> 24) ^ c]
    return UNSIGNED(~s)

if __name__ == '__main__':
    fname = sys.argv[-1]
    buffer = open(fname, 'rb').read()
    print("%d\t%d\t%s" %  (memcrc(buffer), len(buffer), fname))

Может кто-нибудь помочь мне понять это?

• в чем именно проблема с разницей между cksum и crc32?
• это просто факт, что один основан на 32-битном, а другой 64-битном?
• Могу ли я просто преобразовать значения, полученные обоими, и если да, то как?
• какова цель crctab в приведенном выше фрагменте и как там работает преобразование?

Answer 1

Я не знаю, почему в вашем вопросе. Все, что я могу сказать, это то, что стандарты хороши тем, что у вас есть из чего выбирать.

cksum указан в POSIX для использования другой CRC, чем более распространенный CRC-32, который вы найдете в zlib, Python, используемый в zip- и gzip-файлах и т.д. CRC-32/CKSUM имеет эту спецификацию (из каталога CRC Грега Кука):

width=32 poly=0x04c11db7 init=0x00000000 refin=false refout=false xorout=0xffffffff check=0x765e7680 residue=0xc704dd7b name="CRC-32/CKSUM"

Более распространенный CRC-32 имеет эту спецификацию:

width=32 poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926 residue=0xdebb20e3 name="CRC-32/ISO-HDLC"

Утилита cksum в моей системе (macOS) вычисляет CRC-32/CKSUM, но у нее также есть опции для вычисления CRC-32/ISO_HDLC, а также двух других фактических контрольных сумм, первая из команды BSD Unix sum и второй из команды AT&T System V Unix sum.

Очевидно, что недостатка в результатах, которые может дать cksum, нет.

Нет, это не имеет ничего общего с 32-битными или 64-битными системами.

Нет, вы не можете конвертировать значения.

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

Answer 2

Я пробовал преобразовать ваш код в класс, аналогичный API-интерфейсу стандартного Python. hashlib:

class crc32:
    def __init__(self):
        self.nchars = 0
        self.crc = 0
    
    def update(self, buf):
        crc = self.crc
        for c in buf:
            crc = crctab[(crc >> 24) ^ c] ^ ((crc << 8) & 0xffffffff)
        self.crc = crc
        self.nchars += len(buf)

    def digest(self):
        crc = self.crc
        n = self.nchars
        while n:
            c = n & 0xff
            crc = crctab[(crc >> 24) ^ c] ^ ((crc << 8) & 0xffffffff)
            n >>= 8
        return UNSIGNED(~crc)

Я расширил UNSIGNEDчтобы попытаться сделать это быстрее и изменить порядок некоторых операторов, чтобы они были более похожи на стандартную библиотеку zlib (используемую Python), пока я пытался понять различия. Кажется, они используют другой многочлен для создания таблицы, но в остальном все то же самое.

Приведенный выше код можно использовать как:

with open('largefile', 'rb') as fd:
  digest = crc32()
  while buf := fd.read(4096):
    digest.update(buf)
  print(digest.digest())

который выводит ожидаемое значение 1135714720 для файла, созданного:

echo -n hello world > test.txt

Приведенный выше код должен работать с большими файлами, но с учетом производительности Python это займет слишком много времени, чтобы быть полезным. Файл размером 75 МБ у меня занимает ~11 секунд, а cksumзанимает всего ~0,2 секунды. У вас должно получиться кое-что, используя Cython для его ускорения, но это немного сложнее, и если вы боретесь с существующим кодом, это будет довольно кривой обучения!

У меня был еще один спектакль, и я получил исполнение, подобное cksum с Cython код выглядит так:

cdef unsigned int *crctab_c = [
  // copy/paste crctab from above
]

cdef class crc32_c:
    cdef unsigned int crc, nchars

    def __init__(self):
        self.nchars = 0
        self.crc = 0
    
    cdef _update(self, bytes buf):
        cdef unsigned int crc, i, j
        cdef unsigned char c
        crc = self.crc
        for c in buf:
            i = (crc >> 24) ^ c
            j = crc << 8
            crc = crctab_c[i] ^ j
        self.crc = crc
        self.nchars += len(buf)

    def update(self, buf):
        return self._update(buf)

    def digest(self):
        crc = self.crc
        n = self.nchars
        while n:
            c = n & 0xff
            crc = crctab_c[(crc >> 24) ^ c] ^ ((crc << 8) & 0xffffffff)
            n >>= 8
        return (~crc) & 0xffffffff

после компиляции этого кода с помощью Cython его можно использовать аналогично предыдущему классу. Производительность довольно хороша: Python теперь занимает ~200 мс для файла размером 75 МБ и в основном такой же, как cksum, но намного медленнее, чем zlib, который занимает всего ~80 мс.