delsum скачать - delsum исходный код скачать

delsum

Другие категории

v0.2.1

Скачать

`delsum`

delsum - это приложение CLI для поиска контрольных точек, используемых в файле.

В настоящее время есть три подкоманды:

check : Учитывая спецификацию алгоритма контрольной суммы и список файлов, это просто выводит контрольные суммы этих файлов.
part : Учитывая спецификацию алгоритма контрольной суммы и список файлов с соответствующими контрольными суммами, это находит части файлов, которые имеют данную контрольную сумму
reverse : Учитывая список файлов с соответствующими контрольными суммами, он находит используемые параметры контрольной суммы

`check`

Эта подкоманда вычисляет контрольную сумму с данным алгоритмом.

Пример:

 $ delsum check -m 'crc width=32 poly=0x4c11db7 init=0xffffffff xorout=0xffffffff refin=true refout=true' file_a file_b file_c
700b14f5,e1207917,79741cb2

Алгоритм может быть указан непосредственно в качестве аргумента с -m или в списке алгоритмов в файле.

Начало или конец диапазона для расчета контрольной суммы дана с -S или -E , а также может быть отрицательным, чтобы сделать их по сравнению с концом. Например, для расчета контрольной суммы всех байтов, кроме последних двух, один определяет -S 0 и -E-3 (она включена, поэтому -3 все еще является частью суммы).

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

`part`

Эта подкоманда находит все части списка файлов, в которых совпадают все заданные контрольные суммы. Части файла, который соответствует совпадению, должны быть такими же, как и файлы.

Пример:

 $ delsum part -m 'modsum width=16 module=ffff' -c 1234,5678,abcd file_a file_b file_c
modsum width=16 module=ffff:
    0x8:-0x3

В этом случае контрольная сумма соответствует части 0x8:-0x3 , где -0x3 относительна с конца. Это инклюзивный диапазон, что означает, что контрольная сумма, которая переходит от начала до конца, будет иметь диапазон 0x0:-0x1 . Если бы файлы были размером 15, 16 и 18 байтов соответственно, то этот вывод означал бы, что

file_a имеет контрольную сумму 1234 от байта 8 по 13
file_b имеет контрольную сумму 5678 от байта 8 до 14
file_c имеет контрольную сумму abcd от байта 8 по 16

Можно также, чтобы конец частей был относительным с начала файла (а не конца), используя флаг -s . Кроме того, -S и -E позволяют ограничивать, где диапазоны начинаются и заканчиваются, указав диапазоны (также включительно). Например, когда обычно диапазоны 0x1:0xa , 0x3:0x10 и 0x4:0xb будут выводиться, указание -S0x0:0x3 позволит только начальную часть диапазонов между 0 и 3 включительно, поэтому 0x4 не будет напечатано. Это может помочь избежать ложных срабатываний, а также может сократить время выполнения.

Есть небольшая вероятность того, что он выведет что -то вроде 0x1,0x6:0x5,0x10 . Это просто означает, что каждая комбинация возможна. В этом случае можно было бы иметь 0x1:0x5 , 0x1:0x10 и 0x6:0x10 . В то время как 0x6:0x5 теоретически будет также выбором, он недопустим, так как он задом наперед.

Используя линейность контрольной суммы, весь этот процесс может быть выполнен в примерно логическом времени, но просто имейте в виду, что он имеет большие (линейные) накладные расходы пространства, и у вас может закончено запустить память, если вы запустите ее на кучу 500 МБ файлов.

Можно также дать список алгоритмов в файле в качестве ввода в -M . Это может быть полезно, так как это позволяет просто разместить там наиболее распространенный алгоритм контрольной суммы и посмотреть, есть ли какие -либо алгоритмы в любой части файлов, имеет нужную контрольную сумму. Для доступных алгоритмов и того, как их указать, см. Здесь.

`reverse`

Эта подкоманда находит параметры алгоритма контрольной суммы.

С заданными файлами и контрольной суммой он ищет те параметры алгоритма, для которых все файлы имеют заданные контрольные суммы.

Обратите внимание, что, по крайней мере, фундаментальный алгоритм и ширина контрольной суммы должны быть указаны (например, crc width=32 ). Для доступных алгоритмов и того, как их указать, см. Здесь.

Пример:

 $ delsum reverse -m 'crc width=32' -c 700b14f5,e1207917,79741cb2 file_a file_b file_c
crc width=32 poly=0x4c11db7 init=0xffffffff xorout=0xffffffff refin=true refout=true

Как правило, вам нужно 3 файла, и для алгоритмов, отличных от modsum , по крайней мере, один из файлов должен иметь разные длины. Также можно указать некоторые параметры алгоритма (с использованием, например -m 'crc width=32 init=0' ), который требует меньше файлов или приносит меньше ложных срабатываний.

Если у вас есть только файлы данной длины, но также заботитесь только о контрольной сумме этой длины, для алгоритма, а не modsum вы можете просто установить init=0 .

Обычно это довольно быстро; Например, время выполнения алгоритма реверсирования CRC в большинстве случаев находится вокруг O(n*log^2(n)*log(log(n))) где n представляет собой размер файла, который является благодаря алгоритму быстрого GCD, реализованного в библиотеках NTL и GF2X.

Для некоторых параметров, вероятно, поиск только комбинаций:

wordsize ищут способности 2 -го кратного 8, которые меньше или равны width
refin и refout поиск refin = refout

Чтобы найти эти параметры, либо укажите их вручную, либо используйте аргумент CLI --extended-search .

Алгоритмы

В настоящее время есть три семейства алгоритмов: modsum , fletcher и crc . Они указаны в следующем: algofamiliy width=123 para1=ff para2=true para3=10 name="algoname" . Обратите внимание, что все численные параметры, кроме width и wordsize находятся в шестнадцатеричной.

Общие ценности

В настоящее время это совместно складывает все типы сумм:

width : ширина контрольной суммы в битах
out_endian : эндсиан контрольной суммы, может быть little или big
wordsize : количество бит слова в входном тексте. wordsize=16 быть кратный 8 и от 8 module 64.
in_endian : эндсиан входных слов, может быть little или big .

`modsum`

Простая модульная сумма с width параметров, init и module .

Соответствует

 sum = init
for byte in file:
    sum = (sum + byte) % module
return sum

Обратите внимание, что для module 0 он эквивалентен 2^width .

Значения по умолчанию для module и init являются 0.

`fletcher`

Флетчер, похожая на сумму с width параметров, init , addout , module и swap .

Соответствует

 sum1 = init
sum2 = 0
for byte in file:
    sum1 = (sum1 + byte) % module
    sum2 = (sum2 + sum1) % module
sum1 = (sum1 + addout.sum1) % module
sum2 = (sum2 + addout.sum2) % module
if not swap:
    returm (sum2 << (width/2)) | sum1
else:
    returm (sum1 << (width/2)) | sum2

Он выводится в «упакованной» форме, где SUM1 хранится в нижней ширине/2 бита и Sum2 в более высокой ширине/2 (или на противоположной, если включена swap ). Параметры:

width : ширина всей упакованной контрольной суммы. Обязательный.
module : значение, с помощью которого можно уменьшить. module = 0 означает 2^(width/2) и является значением по умолчанию.
init : значение для инициализации обычной контрольной суммы с. По умолчанию к 0.
addout : упакованное значение, которое добавлено в конце суммы. Высокая часть всегда добавляется в высокую часть контрольной суммы в конце, независимо от swap . По умолчанию к 0.
swap : логический флаг, который указывает на то, что обычная сумма должна находиться в более высокой половине упакованной контрольной суммы. По умолчанию false .

`crc`

Алгоритм CRC с параметрами в соответствии с моделью Rocksoft^TM, как задокументировано в «Безболезненное руководство по обнаружению ошибок CRC».

У него есть следующие параметры:

width : ширина в битах контрольной суммы (и степени поли). Обязательный.
poly : Полином генератора, в нормальных обозначениях. Обязательно (за исключением reverse ).
init : начальное значение состояния CRC. По умолчанию к 0.
xorout : окончательное значение для XOR к сумме. По умолчанию к 0.
refin : логический флаг, указывающий, отражать ли биты входных байтов. По умолчанию false .
refout : логический флаг, указывающий, отражать ли биты окончательной контрольной суммы, прежде чем добавлять xorout . По умолчанию false .

Обратите внимание, что другие значения для wordsize с in_endian=little (стандарт) такие же, как обмен байтами в каждой группе битов wordsize , прежде чем вычислять проверку wordsize=8 .

Как это работает

Некоторое (неполное) объяснение используемых алгоритмов найдено здесь.

Установка

Здесь есть сборка Linux, в которой здесь составлена библиотека NTL, но имейте в виду, что она скомпилирована без большинства современных расширений x86 и, следовательно, не может воспользоваться некоторыми оптимизированными процедурами в gf2x , что делает CRC повернуть намного быстрее. Я также слишком тупой, чтобы сделать сборку Windows, так что извините за это.

Эта программа связывается с NTL , gf2x и gmp .

Если вы находитесь в системе на основе Debian, вы можете установить их с

 apt-get install libgmp-dev libgf2x-dev libntl-dev

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

Если у вас установлен cargo , то должно быть возможно скомпилировать его в корне каталога проекта с