2020-06-10 20:30:09 +10:00
|
|
|
|
# Лабораторная работа №6
|
|
|
|
|
|
|
2020-06-11 13:22:10 +10:00
|
|
|
|
Входные данные тестов находятся в файле [.execme](.execme), там же находятся и сами тесты.
|
|
|
|
|
|
|
2020-06-10 20:30:09 +10:00
|
|
|
|
## Задание 1
|
2020-06-11 13:22:10 +10:00
|
|
|
|
|
|
|
|
|
|
Был реализован алгоритм вычисления контрольной суммы с использованием XOR.
|
|
|
|
|
|
|
|
|
|
|
|
Тестовые данные были проверены онлайн-калькулятором
|
|
|
|
|
|
https://www.scadacore.com/tools/programming-calculators/online-checksum-calculator/
|
|
|
|
|
|
|
|
|
|
|
|
## Задание 2
|
|
|
|
|
|
|
|
|
|
|
|
Был реализован алгоритм вычисления контрольной суммы Флетчера.
|
|
|
|
|
|
|
|
|
|
|
|
Тестовые данные были проверены онлайн-калькулятором
|
|
|
|
|
|
https://gchq.github.io/CyberChef/#recipe=Fletcher-16_Checksum()
|
|
|
|
|
|
|
|
|
|
|
|
## Задание 3
|
|
|
|
|
|
|
|
|
|
|
|
Был реализован быстрый алгоритм вычисления контрольной суммы CRC-16-IBM (он же CRC-16).
|
|
|
|
|
|
|
|
|
|
|
|
Тестовые данные были проверены онлайн-калькулятором
|
|
|
|
|
|
https://emn178.github.io/online-tools/crc16.html
|
|
|
|
|
|
|
|
|
|
|
|
## Задание 4
|
|
|
|
|
|
|
|
|
|
|
|
Для бенчмаркинга алгоритмов в программах был реализован ключ `-b`.
|
|
|
|
|
|
|
|
|
|
|
|
Результаты можно увидеть ниже:
|
|
|
|
|
|
```text
|
|
|
|
|
|
Allocating 512B file with random data...
|
|
|
|
|
|
XOR execution time: 0.000018s
|
|
|
|
|
|
Fletcher execution time: 0.000017s
|
|
|
|
|
|
CRC execution time: 0.000015s
|
|
|
|
|
|
|
|
|
|
|
|
Allocating 64KB file with random data...
|
|
|
|
|
|
XOR execution time: 0.000621s
|
|
|
|
|
|
Fletcher execution time: 0.001165s
|
|
|
|
|
|
CRC execution time: 0.000962s
|
|
|
|
|
|
|
|
|
|
|
|
Allocating 128MB file with random data...
|
|
|
|
|
|
XOR execution time: 0.876024s
|
|
|
|
|
|
Fletcher execution time: 1.921205s
|
|
|
|
|
|
CRC execution time: 1.235906s
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
Из этого можно сделать вывод, что наилучший из представленных алгоритм вычисления
|
|
|
|
|
|
контрольной суммы -- CRC-16. XOR-сумма имеет слишком много коллизий, а также нечувствительна
|
|
|
|
|
|
к перестановкам байтов, хотя она является наиболее быстрой. CRC-16 на больших файлах оказывается
|
|
|
|
|
|
ощутимо производительнее суммы Флетчера, хотя и требует на 256 байт больше памяти.
|
|
|
|
|
|
|
|
|
|
|
|
## Задание 5
|
|
|
|
|
|
|
|
|
|
|
|
В данном задании был использован алгоритм CRC-8-Maxim/Dallas для вычисления контрольных сумм
|
|
|
|
|
|
4Кб-блоков в файле, а также их сверки.
|
|
|
|
|
|
|
|
|
|
|
|
В тестах проверяется адекватность программ (создание контрольной суммы с последующей сверкой),
|
|
|
|
|
|
а так же поведение при повреждении файла.
|
