Сейчас на форуме: jinoweb (+6 невидимых)

 [email protected] —› Программирование —› Определить алго для патч-движка
Посл.ответ Сообщение


Ранг: 275.9 (наставник), 340thx
Активность: 0.22=0.22
Статус: Участник
RBC

Создано: 26 сентября 2018 13:35 · Поправил: Kindly
· Личное сообщение · #1

пытаюсь сделать свой патч-движок, наподобие xdelta, но столкнулся с основной проблемой, итак, краткое описание алгоритма:
сравнить два файла побайтно между собой и записать разницу в "diff"-файл с указанием размера отличающихся байт и смещения (или размер от начала файла), чтобы при применении патча было ясно по какому смещению, какую сигнатуру записать и какого размера и т.д., формат моего diff, примерно, следующий:

заголовок/размер old/размер new/offset/size/differentbytes/offset/size/differentbytes/...

на выхлопе получается гораздо большой diff файл, сравнительно xdelta, т.к. на каждую различительную сигнатуру у меня уходит 8 байт (4 offset и 4 на размер). особенно это ощущается, если байты могут отличаться один через один, и тогда на каждое сравнение всего одного байта уходит +8 байт драгоценного места и в итоге diff файл может увеличиться в разы.

обдумывал разные варианты, но все они сводятся примерно к этому же, но остался последний вариант, который требует решения, если таковое возможно

идея такова.

1. выполнить побайтное сравнение всех байтов поочередно от 00 до FF.
2. записать сколько раз каждый отличающийся байт присутствует в файле и высчитать все размеры смещений, например:

сканируем количество отличающихся байт AA и записываем сколько штук различий, к примеру:

AA:1000
и мы знаем, что в файле записать этот байт надо 1000 раз, но по предварительно вычисленным размерам друг до друга, например:

AA:1000:03,50,129,180,189,206,300,315,423,1070,1288,2030, и т.д. вплоть до числа 0xFFFFFFF7

если записывать это дело в строку, то уйдет опять же приличное количество места.
в идеале хотелось бы знать, существует ли алгоритм, который позволяет закодировать ленту чисел в одно свое "магическое" число, а потом позволить раскодировать/разложить это "магическое" число на исходные числа в ленте по порядку, чтобы можно было крутить в цикле и записывать нужный байт в нужное место по расшифрованному значению, на подобие:

for I:=1 to 1000 do
begin
buf := Encrypt(i,offset);
end;

for I:=1 to 1000 do
begin
offset := Decrypt(buf[i]);
Write($AA,offset);
end;

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

-----
Array[Login..Logout] of Life




Ранг: 262.5 (наставник), 337thx
Активность: 0.340.25
Статус: Участник

Создано: 26 сентября 2018 17:47 · Поправил: TryAga1n
· Личное сообщение · #2

Можно использовать первый адрес для патча как "нулевой", а последующие - как смещения, относительно "нулевого". Если патчить РЕ файл, то для каждой секции находить "нулевой" адрес. Экономия мизерная конечно, но уже что-то.
********************
Можно маленький пример diff, буквально на одну строчку, с описанием, что откуда? Чтобы нагляднее было думать)




Ранг: 271.4 (наставник), 331thx
Активность: 0.321.49
Статус: Участник

Создано: 26 сентября 2018 18:16 · Поправил: f13nd
· Личное сообщение · #3

Kindly пишет:
существует ли алгоритм, который позволяет закодировать ленту чисел в одно свое "магическое" число

Ну так ты сам ответ дал. Взять поле оффсета и поле количества байт не кратное 8 битам. Пусть алгоритм оценивает какой оффсет получился максимальный, какое количество байт максимальное, сохраняет максимальные количества бит этих значений. Скажем 5 бит на длину оффсета (до 32 двоичных разрядов, максимальный оффсет 0xFFFFFFFF), 3 на размер (максимальный размер 255), итого 1 байт описывает "магическое число". Потом на сдвигах заполняешь свое магическое число, пусть (0;0) плюс выравнивание последнего байта будет означать конец этой структуры. Сразу за ним в том же порядке данные.

-----
2 оттенка серого


| Сообщение посчитали полезным: Kindly

Ранг: 2.5 (гость)
Активность: 0=0
Статус: Участник

Создано: 26 сентября 2018 18:43
· Личное сообщение · #4

Может хранить в формате VCDIFF? --> Тут <-- описание формата, вдруг подойдёт и не надо будет изобретать велосипед




Ранг: 275.9 (наставник), 340thx
Активность: 0.22=0.22
Статус: Участник
RBC

Создано: 26 сентября 2018 19:32
· Личное сообщение · #5

TryAga1n пишет:
Если патчить РЕ файл, то для каждой секции находить "нулевой" адрес.

патчиться будут любые форматы.

TryAga1n пишет:
Можно маленький пример diff, буквально на одну строчку, с описанием, что откуда? Чтобы нагляднее было думать)

на данный момент:
30 10 00 00 30 10 00 00 A0 00 00 00 40 00 00 00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 60 01 00 00 10 00 00 00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF 00 02 00 00 20 00 00 00 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

где первые два дворда это размеры сравниваемых файлов (могут отличаться), далее:
A0 00 00 00 - offset
40 00 00 00 - size of diffs
FF-ки - различительные байты с указанным размером, после них все идентично: оффсет/размер/набор новых байтов и т.д.

да, можно еще сделать так:
от начала файла с нуля считать расстояние, но по факту получается то же самое, если записывать:

3,10,15,20
и лепить отличающиеся байты в один массив
AAA1A2A3A4A5A60102030405

то получается: от 3 позиции до 10 длина 7 байтов, стало быть по оффсету:
3 запишем: AAA1A2A3A4A5A6
теперь считаем вторую пару 20-15:
по оффсету 15 запишем следующие пять байт:
0102030405

как ни крути, надо записывать пару, а пара это два дворда с учетом больших файлов до 4Гб, поэтому расстояние до смещения может быть не в один байт.

так что относительно "нулевого" смещения или писать оффсеты с размером - по сути одинаково затратно на выхлопе.

rthax пишет:
Может хранить в формате VCDIFF?

инструменты такие уже есть, с тем же xdelta, который поддерживает этот алго более 15 лет мне не тягаться. хочется чего-то своего

брал для теста 80мб файлы с разным набором байтов - моя поделка выплевывает результат в 20 раз быстрее, чем xdelta. но если сравнивать похожие файлы, например большие exe разных версий, то xdelta хоть и медленнее в 20 раз, но создаст diff-файл меньше как минимум в десятки раз.

f13nd
тут мне надо попереваривать инфу по поводу битов и сдвигов

-----
Array[Login..Logout] of Life





Ранг: 271.4 (наставник), 331thx
Активность: 0.321.49
Статус: Участник

Создано: 26 сентября 2018 19:44 · Поправил: f13nd
· Личное сообщение · #6

Kindly пишет:
тут мне надо попереваривать инфу по поводу битов и сдвигов

n-длина оффсета, k-длина размера, (n+k)*i = номер первого бита оффсета, (n+k)*i + n = номер первого бита длины, остается набросать две функции, которые будут выбирать или устанавливать нужное количество бит по нужному смещению:
Code:
  1. get(o, l) {
  2.         mask = 0;
  3.         for (= 0; i < l; i++) mask = (mask << 1) | 1;
  4.         a = qword(& !7);
  5.         a = a >> (& 7);
  6.         a = a & mask;
  7.         return a;
  8. }


-----
2 оттенка серого


| Сообщение посчитали полезным: BlackCode

Ранг: 262.5 (наставник), 337thx
Активность: 0.340.25
Статус: Участник

Создано: 26 сентября 2018 20:04
· Личное сообщение · #7

Kindly пишет:
FF-ки - различительные байты с указанным размером

Не совсем понял что есть "различительные байты". Оригинальные байты?




Ранг: 275.9 (наставник), 340thx
Активность: 0.22=0.22
Статус: Участник
RBC

Создано: 26 сентября 2018 20:28
· Личное сообщение · #8

f13nd
попробую перевести на асм в дельфе, там видно будет.

TryAga1n пишет:
Не совсем понял что есть "различительные байты".

может не так выразился, отличающиеся, т.е. набор байтов в новом сравниваемом файле, которые будут записаны в diff и в последствии записываться функцией применения патча в старый файл.

-----
Array[Login..Logout] of Life





Ранг: 568.2 (!), 465thx
Активность: 0.550.57
Статус: Участник
оптимист

Создано: 27 сентября 2018 00:24
· Личное сообщение · #9

Используй как в таблице релоков
смещение офсет(равное 1000)байт те 1000.2000.3000 и т.д.р
размер(можно коло во перезаписываемых байт)
теперь таблица смещение относительно офсета(смещение максимум 0FFF) И последний байт на что заменить (00FF) получается dword

-----
Чтобы правильно задать вопрос, нужно знать большую часть ответа. Р.Шекли.




Ранг: 431.7 (мудрец), 390thx
Активность: 0.730.32
Статус: Участник

Создано: 27 сентября 2018 07:57 · Поправил: dosprog
· Личное сообщение · #10

А чем не устраивает формат "CRK"?






Ранг: 275.9 (наставник), 340thx
Активность: 0.22=0.22
Статус: Участник
RBC

Создано: 28 сентября 2018 18:00
· Личное сообщение · #11

dosprog пишет:
А чем не устраивает формат "CRK"?

текстовый

All
копнул тему глубже - алгоритмы используются серъезные для разного рода оптимизаций как для VCDIFF, так и для других похожих. ваять свой велосипед нету столько знаний и смысла, тему закрываю.

-----
Array[Login..Logout] of Life



 [email protected] —› Программирование —› Определить алго для патч-движка
Эта тема закрыта. Ответы больше не принимаются.
   Для печати Для печати