Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Поиск в бинарном файле [D5, WinXP]

Страницы: < 1 2 3 4 5 6 7 8 9 10 ... 13 14 >
Dimaxx © (2004-09-24 23:32:00)
Сабж. Нужен алгоритм действительно быстрого поиска последовательности байт любой длины в файлах любого размера (до гигабайта). Читать кусками по-деревенски не катит. Раньше у меня был алгоритм, но с падением Фуджика все пропало.

GuAV (2004-10-07 20:11:00) [21]
Реализация [242] для поиска из [193]
@@WideScan: Cmp ECx, 16 Jb @@SmallScan Mov Al,[EAx] Mov Ah, Al MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 Push ECx Test EDx, 7 Jz @@Scan5 Mov ECx, EDx And ECx, 7 And EDx, not 7 MovQ MM7, [EDx] PCMPEQB MM7, MM6 PACKSSWB MM7, MM7 MovD EAx, MM7 And EAx, SmallTestArray[ECx*4].DWord Jnz @@1stbytes Mov EAx, ECx Mov ECx, [ESp] Add EDx, 8 Sub ECx, EAx @@Scan5: MovQ MM7, [EDx] PCMPEQB MM7, MM6 PACKSSWB MM7, MM7 MovD EAx, MM7 Test EAx, EAx Jnz @@CharFound2 Add EDx,8 Sub ECx,8 Jg @@Scan5 @@Exit_False2: Emms Pop EAx Xor EAx, EAx Ret @@1stbytes: Mov [ESp], ECx Mov ECx, 8 @@CharFound2: Dec Ecx Test EAx,0Fh Jnz @@Check2 Shr EAx,4 Jmp @@CharFound2 @@Loop2: Dec Ecx Test Al,Al Js @@Check2 Shr EAx,8 Jmp @@Loop2 @@Check2: Test ECx,ECx Js @@Exit_False2 Emms Pop EAx Sub EAx, ECx Ret

> пересечемся в аське

никак. только мыло.

Defunct (2004-10-07 19:33:00) [22]
2 GuruAV: я смотрю вы из Харькова, не хотите быть соавтором статьи в ВАКовском журнале "Проблемы программирования"? Если да, тогда давайте пересечемся в аське.

GuAV (2004-10-07 16:10:00) [23]
По поводу поиска по восем байт без AV мысль такая.

сначала Test Buffer, 7 и если не нуль то
{
читать в mmreg 8 байт из [Buffer and (not 7)]

в начало могут попасть байты из длины и счета ссылок, чтобы их проигнорировать, тестить результат PCMPEQB / PACKUSWBвот такой маской (адресовать в самой маске по [Buffer and 7)])

SmallTestArray: array[0..7] of LongWord = ($00000000, $F0000000, $FF000000, $FFF00000, $FFFF0000, $FFFFF000, $FFFFFF00, $FFFFFFF0);поправить буфер Buffer:=Buffer and (not 7)
}
потом читать по 8 байт из буфера (он уже QWord aligned)

потом читать остаток, если он есть. Причём 8 байт, хотя осталось меньше. Тестить масокй из аналогичного массива. Буфер остался QWord Aligned, поэтому чтение не пересечет 4к-границу, т.е. AV не будет.

GuAV (2004-10-07 02:23:00) [24]
@@CompareWholeString: Test EBx, EBx Jz @@Constant_Exists Cmp EDx, EBx Jna @@Exit_False Push ESi Push EDi Add EDi, EBx Add ESi, EBx @@CWs_1: Test EBx, 1 Jz @@CWs_2 Sub ESi, 1 Sub EDi, 1 MOV AL, [ESi] CMP AL, [EDi] JNE @@SkipBTest1 @@CWs_2: Test EBx, 2 Jz @@CWs_4 Sub ESi, 2 Sub EDi, 2 MOV AX, [ESi] CMP AX, [EDi] JNE @@SkipBTest1 @@CWs_4: Test EBx, 4 Jz @@CWs_8 Sub ESi, 4 Sub EDi, 4 MOV EAX, [ESi] CMP EAX, [EDi] JNE @@SkipBTest1 @@CWs_8: MOV ECX, EBX @@CW_Loop: SUB ECX, 8 JL @@Constant_Exists1 SUB ESi, 8 SUB EDi, 8 MovQ MM3, [ESi] MovQ MM2, [EDi] PCMPEQB MM3, MM2 PACKSSWB MM3, MM3 MovD EAX, MM3 Cmp EAX, -1 JE @@CW_Loop @@SkipBTest: Mov ECx, EDx @@SkipBTest1: Cmp EDx,4 Pop EDi Pop ESi Jg @@Scan Jmp @@LastDWord @@Constant_Exists1: Pop EDi Pop ESi @@Constant_Exists: Pop EAx Sub EAx, EDx

GuAV (2004-10-07 02:05:00) [25]
[239] опять не рабочий код дал, блин... вот рабочий:
@@CompareWholeString: Test EBx, EBx Jz @@Constant_Exists Cmp EDx, EBx Jna @@Exit_False MOV ECX, EBX @@CWs_1: Test ECx, 1 Jz @@CWs_2 Sub ECx, 1 MOV AL, [ESi+ECx] CMP AL, [EDi+ECx] JNE @@SkipBTest @@CWs_2: Test ECx, 2 Jz @@CWs_4 Sub ECx, 2 MOV AX, [ESi+ECx] CMP AX, [EDi+ECx] JNE @@SkipBTest @@CWs_4: Test ECx, 4 Jz @@CWs_8 Sub ECx, 4 MOV EAX, [ESi+ECx] CMP EAX, [EDi+ECx] JNE @@SkipBTest @@CWs_8: @@CW_Loop: SUB ECX, 8 JL @@Constant_Exists MovQ MM3, [ESi+ECx] MovQ MM2, [EDi+ECx] PCMPEQB MM3, MM2 PACKSSWB MM3, MM3 MovD EAX, MM3 Cmp EAX, -1 JE @@CW_Loop @@SkipBTest: Mov ECx, EDx Cmp EDx,4 Jg @@Scan Jmp @@LastDWord @@Constant_Exists: Pop EAx Sub EAx, EDx

GuAV (2004-10-07 01:49:00) [26]
@@CompareWholeString: Test EBx, EBx Jz @@Constant_Exists Cmp EDx, EBx Jna @@Exit_False MOV ECX, EBX @@CWs_1: Test ECx, 1 Jz @@CWs_2 MOV AL, [ESi+ECx] CMP AL, [EDi+ECx] Sub ECx, 1 @@CWs_2: Test ECx, 2 Jz @@CWs_4 MOV AX, [ESi+ECx] CMP AX, [EDi+ECx] Sub ECx, 4 @@CWs_4: Test ECx, 4 Jz @@CWs_8 MOV EAX, [ESi+ECx] CMP EAX, [EDi+ECx] Sub ECx, 8 @@CWs_8: @@CW_Loop: SUB ECX, 8 JL @@Constant_Exists MovQ MM3, [ESi+ECx] MovQ MM2, [EDi+ECx] PCMPEQB MM3, MM2 PACKSSWB MM3, MM3 MovD EAX, MM3 Cmp EAX, -1 JE @@CW_Loop @@SkipBTest: Mov ECx, EDx Cmp EDx,4 Jg @@Scan Jmp @@LastDWord @@Constant_Exists: Pop EAx Sub EAx, EDx

Defunct © (07.10.04 01:09) [238]
Не думаю что я справлюсь раньше. Пока я ещё не полностью понимаю работу имеющесйся. Однако, завтра у меня будет много времени.

Defunct (2004-10-07 01:09:00) [27]
У меня промелькнула идея которая не только может значительно ускорить функцию, но и решит проблему с validate 0. Как вы думаете, если при MMX сканировании и при CharPos (раскрученном цикле) формировать массив найденных символов и потом с ним и работать. (т.е. например, просмотрели 8 символов, нашли 3 совпадения и дальше уже работает с совпадениями, все найденные совпадения не подходят - тогда продолжаем смотреть следующие 8 символов).

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

GuAV (2004-10-07 00:33:00) [28]
Defunct © (07.10.04 00:14) [236]

не знал про это. тогда так:

@@WideScan: Cmp ECx, 16 Jb @@SmallScan Mov Al,[EAx] Mov Ah, Al MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 Push EBx Push EDx Mov EBx, ECx And EBx, not 7 Add EBx, EDx Test EDx, 4 Jz @@WSc_Scan5 MovD MM7, [EDx] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) MovD EAx, MM7 // get mixed dword Test EAx, EAx Jnz @@WSc_DFound Add EDx, 4 Sub EBx, 4 // do not check dword again @@WSc_Scan5: MovQ MM7, [EDx]
и далее по тексту.
то есть, если был DWord align, то при WSc_Scan5 будет QWord align, а не быть его может только в извращённых условиях типа validate0, под которые подстраиваемся, но не оптимизируем.

Defunct (2004-10-07 00:14:00) [29]
Guru, а вы учитываете выравнивание на границу QWord при MMX сканировании? На очень больших строках будет существенный проигрыш если не учитываете.

Это же было не от фонаря сделано [193]:

MovQ MM7, [Edi]
PCMPEQB MM7, MM6
PACKSSWB MM7, MM7
MovD EAx, MM7
Test EAx, EAx
Jnz @@CharFound
Add EDi, 8
Mov EAx, Edi
And EAx, 7
Sub EDi,EAx // Aligning index
Sub ECx,8
Add ECx,EAx
Cmp ECx,4
Jnge @@LastDword

У меня получалось добиться индекса 133 в SB2, но тогда мой тест (просмотр 12.5Gb) выполнялся на 2 секунды дольше.

Defunct (2004-10-07 00:03:00) [30]
с новым SmallScan [232] стало гораздо хуже:

PosGuru&Def 4 194 134 328

Defunct (2004-10-07 00:00:00) [31]
2 GuruAV

На P4 - очень хорошо:
PosGuru&Def 4 188 134 322 PosDef_MMX C 194 139 333

на P2 тоже стало лучше но не на много:
PosGuru&Def 4 1148 692 1840 PosDef_MMX C 1168 699 1867 PosJOH_MMX_a 8 1139 933 2072

GuAV (2004-10-06 23:49:00) [32]
kaZaNoVa © (06.10.04 23:24) [231]
Как только, так сразу.

GuAV (2004-10-06 23:42:00) [33]
[230] не то выложил. не работает. вот что имелось ввиду:
@@SmallScan:
Mov Al, [EAx]
Push ECx
Xchg EDx, EDi
Repne ScasB
Jne @@SSc_Done
Xchg EDx, EDi
Pop EAx
Sub EAx, ECx
Ret
@@SSc_Done:
Xchg EDx, EDi
Pop EAx
Xor EAx, EAx
Ret

kaZaNoVa (2004-10-06 23:24:00) [34]
2ALL выложите плиз полный окончательный вариант "ускоренной POS" ;)

GuAV (2004-10-06 23:22:00) [35]
Мой smallscan тоже не выходит за буфер. кроме того вместе с предыдущим кодом у меня быстрее чем [193]
@@SmallScan: Mov Al, [EAx] Push ECx Xchg EDx, EDi Shr ECx, 2 Jz @@SSc_SkipD Repne ScasD Je @@SSc_D @@SSc_SkipD: Mov ECx, [ESp] And ECx, 3 Jz @@SSc_Done Repne ScasB Jne @@SSc_Done Xchg EDx, EDi Pop EAx Sub EAx, ECx Ret @@SSc_Done: Xchg EDx, EDi Pop EAx Xor EAx, EAx Ret @@SSc_D: Add ECx, ECx Xchg EDx, EDi Add ECx, ECx Pop EAx Sub EAx, ECx Ret
Проверте на Р4, плиз.

GuAV (2004-10-06 22:19:00) [36]
Такой WideScan не вылазит за буфер ни на байт.
Имхо надо сделать остальное типа так же.
@@WideScan: Cmp ECx, 16 Jb @@SmallScan Mov Al,[EAx] Mov Ah, Al MovD MM6, EAx PUNPCKLWD MM6, MM6 PUNPCKLDQ MM6, MM6 Push EBx Push EDx Mov EBx, ECx And EBx, not 7 Add EBx, EDx @@WSc_Scan5: MovQ MM7, [EDx] PCMPEQB MM7, MM6 PACKSSWB MM7, MM7 MovD EAx, MM7 Test EAx, EAx Jnz @@WSc_QFound Add EDx, 8 Cmp EDx, EBx Jl @@WSc_Scan5 Mov EBx, ECx And EBx, 7 // is anything left ? Jz @@WSc_Done Test EBx, 4 // dword or more left ? Jz @@WSc_Last123 @@WSc_LastDword2: MovD MM7, [EDx] // load a part of buffer that needs to be scaned PCMPEQB MM7, MM6 // make a bit mask (mm6 filled by 1st char of da constant) MovD EAx, MM7 // get mixed dword Test EAx, EAx Jnz @@WSc_DFound Add EDx, 4 @@WSc_Last123: MovD EAx, MM6 // no MMX anymore Test EBx, 2 Jz @@WSc_LastOne Cmp AL, [EDx] Jz @@WSc_AtLast1 Inc EDx Cmp AL, [EDx] Jz @@WSc_AtLast1 Inc EDx @@WSc_LastOne: Test EBx, 1 Jz @@WSc_Done Cmp AL, [EDx] Jz @@WSc_AtLast1 @@WSc_Done: Pop EDx Xor EAx, EAx Pop EBx Emms Ret @@WSc_AtLast1: Inc EDx @@WSc_AtLast: Mov EAx, EDx Pop EDx Sub EAx, EDx Pop EBx Emms Ret @@WSc_QFound: MovQ MM7, [EDx] PCMPEQB MM7, MM6 MovD EAx, MM7 Test EAx, EAx Jnz @@WSc_DFound Add EDx,4 PSRLQ MM7,32 MovD EAx, MM7 @@WSc_DFound: Inc EDx Test EAx, $000000FF Jnz @@WSc_AtLast Inc EDx Test EAx, $0000FF00 Jnz @@WSc_AtLast Inc EDx Test EAx, $00FF0000 Jnz @@WSc_AtLast Inc EDx Jmp @@WSc_AtLast @Small_String:

Sha (2004-10-06 18:32:00) [37]
> Defunct © (06.10.04 18:26) [225]
> 100% где-то в тесте что-то не учтено.

При этом хорошо бы еще сказать что именно не учтено :)

Давай начнем с исправления очевидной ошибки в ConstantPos('ef9','efg');

Defunct (2004-10-06 18:29:00) [38]
> При заходе на вторую пересылку адрес в edx уже на 1 больше.

Понял

Sha (2004-10-06 18:27:00) [39]
в Sha © (06.10.04 18:13) [223] случайно выкусил не тот код.
Ошибка происходит, там где ты ее нашел.

Defunct (2004-10-06 18:26:00) [40]
Еще один загадочный эксепшин. Идет проверка, не выходит ли подстрока за границу буфера, и если не выходит, тогда происходит сканирование в обратном порядке (с конца строки). Опять же Exception?

Cmp Cl, Bl <-- проверка на выход за границу буфера
Jb @NotFound2 <-- буфер меньше длинны подстроки - выход

Push ECx
Mov ECx, EBx
@Loop2:
Mov Al, [ESi+ECx]
Cmp Al, [EDx+ECx-1] <--- Exceptoin здесь
Jnz @Scan7
Loop @Loop2

100% где-то в тесте что-то не учтено.

Страницы: < 1 2 3 4 5 6 7 8 9 10 ... 13 14 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »