| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Алгоритм сравнения файлов.
DevilDevil © (2007-01-25 01:34:00)Вопрос: существует ли какой-нибудь быстрый способ сравнения файлов... точнее нахождения всех общих цепочек байт?
по моему естественно:
1) оба файла надо сначала занести в память
2)
function EqualBytes(P1, P2 : pointer; MaxLength : DWORD) : DWORD;
asm
push esi
push edi
mov esi, eax
mov edi, edx
{} mov edx, ecx
shr ecx, 2
jz @normecx
Repe cmpsd
je @normecx
mov ecx, 3
sub esi, 4
sub edi, 4
jmp @cmpbytes
@normecx:
mov ecx, edx
and ecx, 3
jz @Exit
@cmpbytes:
Repe cmpsb
je @exit
dec esi
@Exit:
sub eax, esi
neg eax
pop edi
pop esi
end;
Игорь Шевченко (2007-01-25 17:58:00) [1]DevilDevil © (25.01.07 17:09) [20]
> спасибо, Diff я уже нашёл...
> только exe он не сравнивает...
То есть, слова про вдумчивое изучение алгоритма я очевидно в воздух говорил...
DevilDevil (2007-01-25 17:09:00) [2]
> Игорь Шевченко © (25.01.07 16:52) [19]
спасибо, Diff я уже нашёл...
только exe он не сравнивает...
Игорь Шевченко (2007-01-25 16:52:00) [3]
> Кстати о diff, погуглил ничего вразумительного пока не нашёл
> (исходники всмысле), буду рад любой помощи, в том числе
> и предоставление ссылки на исходники diff.
Например:
http://www.codeproject.com/tools/difftool.asp
http://www.thefreecountry.com/programming/filecomparison.shtml
Сергей М. (2007-01-25 16:37:00) [4]
> способ сравнения файлов
> приведённый мной пример расставил все точки над "и"
Этот пример не имеет ни малейшего отношения к файлам.
Сергей М. (2007-01-25 16:30:00) [5]
> Вопрос: существует ли какой-нибудь быстрый способ сравнения
> файлов
см. тот же diff.
Вполне эффективно сравнивает файлы и выводит протокол совпадений/несовпадений .
Только он, diff, не решает поставленную тобой задачу, ибо она и значально не корректна в своей постановке.
> как определить смещение в exe файле, с которого начинается
> код?
А никак.
Потому что сама постановка вопроса лишена смысла.
Гугли по "структура PE-модуля" - и да посетит тебе откровение.
DevilDevil (2007-01-25 16:23:00) [6]
> Сергей М. © (25.01.07 13:40) [15]
Вопрос: существует ли какой-нибудь быстрый способ сравнения файлов... точнее нахождения всех общих цепочек байт, максимальной длинны?
К этой формулировке придраться можно ещё больше. Вопрос тем не менее остаётся открытым; надеюсь, приведённый мной пример расставил все точки над "и", и Вы поняли мою задачу.
Кстати о diff, погуглил ничего вразумительного пока не нашёл (исходники всмысле), буду рад любой помощи, в том числе и предоставление ссылки на исходники diff.
P.S. меня интересует именно быстрый алгоритм. Метод полного перебора очень долгий, предположительно 15-60 минут для файлов в 400кб.
Доп вопрос: как определить смещение в exe файле, с которого начинается код? Если учесть, что код выровнен по 4-х байтной границе (по крайней мере в Delphi), есть смысл проверять код по 4 байта за раз, начиная с этих точек. Такой подход может потерять до 3-х байт в каждой цепочке байт, зато увеличит скорость обработки на пару порядков.
Сергей М. (2007-01-25 13:40:00) [7]
> они должны отсеиваться
Чтой-то вдруг ?
Где это фигурирует в условиях задачи ?
В точном соответствии с твоими условиями записи 0,0,1 0,6,1 0,11,1 означают:
при поиске и сравнении цепочек длиной в один элемент обнаружено, что
в первом файле элемент "1" по смещению 0 встречается во втором файле по смещениям 0, 6, 11.
Что здесь противоречит условиям задачи ?
DevilDevil (2007-01-25 13:30:00) [8]2Сергей М. © (25.01.07 13:20) [12]
а они должны отсеиваться
novill (2007-01-25 13:21:00) [9]а может сначала разберешь алгоритмы архивации?
Сергей М. (2007-01-25 13:20:00) [10]
> DevilDevil © (25.01.07 13:06) [10]
А куда у тебя делись , к примеру, записи:
0,0,1
0,6,1
0,11,1
..
?
Моль съела ?)
Они ведь точно так же удовлетворяют заданному тобой условию поиска ..
Игорь Шевченко (2007-01-25 13:15:00) [11]Умные люди ищут в сети исходники программы diff (они есть) и вдумчиво их изучают. Там очень хороший алгоритм применен.
DevilDevil (2007-01-25 13:06:00) [12]для начала:
Смещение в первом файле, смещение во втором файле, длина цепочки
0, 0, 4
5, 6, 4
11, 11, 4
P.S. но в идеале:
0, 0, 4
5, 0, 5
11, 0, 4
дело в том, что я хочу уметь написать что то типа патчера + архиватора... для Delphi приложений (и уж тем более тематических приложений (БД, игры, ДВИЖКИ)) должно дать хорошую степень сжатия....... с учётом того, что программа-распаковщик знает, откуда брать исходный файл, чтобы получить результирующий ;)
novill (2007-01-25 12:59:00) [13]> [7] DevilDevil © (25.01.07 12:41)
а что вот стаким алогритм должен делать?
файл1 "1234 12345 1234"
файл2 "12345 1234 12345"
Сергей М. (2007-01-25 12:48:00) [14]
> Смещение в первом файле, смещение во втором файле
Эдак ты далеко зайдешь.
Пусть есть два файла с одинаковым содержимым: ХХХ
Приведи результирующий список для данного примера, как ты себе его представляешь ...
DevilDevil (2007-01-25 12:41:00) [15]
> Сергей М. © (25.01.07 11:39) [5]
Смещение в первом файле, смещение во втором файле, длина цепочки
Sinys (2007-01-25 11:57:00) [16]Что-то типа not(P1 and P2) не покатит? если больше нуля то баста
Сергей М. (2007-01-25 11:39:00) [17]
> DevilDevil © (25.01.07 11:16) [4]
А что в результате нужно получить ?
Список записей вида "смещение начала цепочки"+"длина цепочки" ?
DevilDevil (2007-01-25 11:16:00) [18]
> Сергей М. © (25.01.07 10:31) [3]
В моём случае файлы не привысят 600кб.
Ну так есть какой-нибудь алгоритм?
Сергей М. (2007-01-25 10:31:00) [19]
> 1) оба файла надо сначала занести в память
Хорошо когда эти файлы небольшие, а если не полезут ?
Решение тут напрашивается само собой - некэширующий файл-маппинг небольших фиксированных по размеру (кратному 64к) фрагментов обоих файлов.
DevilDevil (2007-01-25 10:19:00) [20]up
| |
Страницы: 