ВходНаше всё Теги codebook 无线电组件 Поиск Опросы Закон Четверг
28 марта
897519
fk0, легенда (19.01.2019 14:05 - 14:13, просмотров: 741)
Вдогонку, надеюсь Evgeny_CD перенесёт куда-то в нужный раздел, на сахаре тема не поднималась. Вообще технология бинарных диффов и бинарных патчей достатчно развита. Существуют даже условные "стандарты" (RFC3284, он же VCDIFF, реализуется программой Xdelta). Основное применение разностного кодирования: передача меньшего объёма информации для получения одинаковой копии результирующего файла на разных сторонах, при условии что обоим сторонам известен какой-то базовый вариант, который потом был изменён одной из сторон. Разностное (дельта) кодирование использует, например, широко известная программа rsync (https://en.wikipedia.org/wiki/Rsync) служащая для синхронизации файлов и целых каталогов между разными компьютерами. Существует даже расширение HTTP-протокола использующее дельта-кодирование для передачи обновлённой версии файла (при условии, что в кеше браузера, например, сохранена предыдущая). Такой механизм гораздо более эффективен, что передача полной копии сжатого файла. Cyanogen Mod (дистрибутив ОС "Android") использует бинарные диффы для обновления мобильных телефонов. Существуют так же алгоритмы словарного сжатия, основанные на использовании разностного кодирования... Для текстовых файлов разностное кодирование широко используется во всех системах контроля версий (CVS, Subversion, Git...) Существуют и не стандартизированные алгоритмы разностного кодирования (для бинарных файлов), в частности следовало бы отметить bsdiff (входит в состав FreeBSD): * ссылка на описание: http://www.daemonology.net/bsdiff/ * исходные тексты: http://www.daemono …diff/bsdiff-4.3.tar.gz (приаттачил к сообщению); * детальное описание алгоритма: http://www.daemono ….net/papers/bsdiff.pdf Данный алгоритм работает в целом медленее чем VCDIFF (RFC3284), но обеспечивает патчи часто существенно меньшего размера. Что подходит для ситуаций, когда данные передаются не в реальном времени (время анализа, получения диффа и восстановления файла может занять больше времени, чем передача данных за это же время через канал связи). Например, для обновления прошивки для встраиваемой техники. Например, прошивка изначально содержит первую версию рабочей программы и некий загрузчик, который может получить по какому-либо однонаправленному каналу связи (последовательный порт, USB, micro SD карточка) обновление, представленное в виде бинарного диффа и исправляющее не сжатую (над сжатыми файлами алгоритм будет работать плохо) первую версию рабочей программы до нужной версии, которая затем может быть записана обратно в flash-память или может не записываться, а исполняться из ОЗУ. С точки зрения программиста никаких специальных действий не требуется, нужно просто сделать дифф между первой версией и целевой -- специальная подготовка рабочей программы не нужна. В типовых условиях, когда в рабочей программе только исправляются ошибки и вносятся небольшие изменения по добавлению нового функционала, диффы получаются очень маленькие, по крайней мере из того, что видел я: размер диффа составлял менее 10% от объёма программы (его реально было передать через сеть и хранить, и накладывать при каждом запуске: изменить то, что во flash не было возможности). В исходных текстах можно видеть, что код программы bspatch достаточно простой: применение патча достигается участком кода длиной в ~50 строк, так что технологию легко применить даже в самых маленьких микроконтроллерах. Создание же диффа достаточно сложно, требует и высокой производительности и больших объёмов памяти, благо эта задача прекрасно решается на ПК. Единственное что, может быть такая особенность как использование позиционно-независимого кода (RISC-процессор, MIPS) даёт меньший размер диффа, чем позиционно-зависимый код (но легко перейти от второго к первому, путём незначительного проигрыша в размере и скорости кода), который весь "прошит" конкретными адресами, которые постоянно меняются, в то время как когда адресация идёт через GOT таблицу, то смещения в GOT для одних и тех же функций и переменных скорей остаются неизменными (в этом плане PC-относительная адресация, принятая для ARM вместо GOT, принятого для MIPS, тоже может быть не выгодна).
[ZX]