Поиск в бинарном файле

← →
Defunct © (2004-10-05 13:50) [200]

> Поздравляю! Пора заново открывать PosChallenge.
пасиба

GuAV © (05.10.04 12:19) [197]
> Не всё так однозначно...

Попробуйте для Celeron"a найти наилучшее соотношение символов в строке, которое обробатывается как маленькая строка. Поменяйте цифры в сл. коде:

....
Cmp ECx,32
Jb @Small_String
...
...
Cmp ECx, 16
Jb @@SmallScan

Sha © (05.10.04 12:25) [198]
> Подправь свою функцию, чтобы проходила тест Validation0 (здесь учтены предложения GuAV):

Ок вечерком, посмотрю.

← →
GuAV © (2004-10-05 22:15) [201]

> Попробуйте для Celeron"a найти наилучшее соотношение символов
> в строке, которое обробатывается как маленькая строка. Поменяйте
> цифры в сл. коде:

Лучше не становится, только хуже.

ИМХО, ещё быстрее будет, если искать в обратном порядке. Можно сначала что-то типа And ECx, 7 и просмотреть остаток, потом вернуть ECx и сделать And ECx not 7 и искать строку используя ММХ... это ИМХО сделает запрет выхода за буфер проще.... попробую сам сделать... если получится, выложу.

← →
Defunct © (2004-10-05 23:31) [202]

> ИМХО, ещё быстрее будет, если искать в обратном порядке.

Не совсем понял вашу идею. Можно пояснить? мы же ищем первое вхождение, а если сканировать в обратном порядке, тогда можно получить неверный результат.

PS: для инициализации MMX требуется значительное время, сканирование целесообразно делать на MMX только для больших строк.

← →
GuAV © (2004-10-06 01:03) [203]

> а если сканировать в обратном порядке, тогда можно получить
> неверный результат

Я сам уже понял, когда написал 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 ECx Mov EBx, ECx And EBx, not 7 And ECx, 7 Jz @@ReverseScan Xor ECx, ECx @@RemainingDword: MovD MM7, [EDx+EBx] // 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 @@FoundInDWord Add ECx, 4 Jna @@ReverseScan MovD MM7, [EDx+EBx+4] // 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 @@FoundInDWord Jmp @@ReverseScan @@FoundInDWord: Inc Ecx Test Al,Al Js @@InDWord_pos Shr EAx,8 Jmp @@FoundInDWord @@InDWord_pos: Emms Pop EAx Test ECx, ECx Js @@InDWord_Failed Mov EAx, ECx Add EAx, EBx Pop EBx Ret @@InDWord_Failed: Xor EAx, EAx Pop EBx Ret @@ReverseScan: Mov ECx, EBx @@ScanLoop: Sub ECx, 8 Js @@ScanLoopExit MovQ MM7, [EDx+ECx] PCMPEQB MM7, MM6 PACKSSWB MM7, MM7 MovD EAx, MM7 Test EAx, EAx Jz @@ScanLoop @@ScanLoopFound: MovQ MM7, [EDx+ECx] PCMPEQB MM7, MM6 MovD EAx, MM7 Test EAx, EAx Jnz @@SLFoundInDword Add ECx,4 PSRLQ MM7,32 MovD EAx, MM7 @@SLFoundInDword: Inc Ecx Test Al,Al Js @@SLInDWord_pos Shr EAx,8 Jmp @@SLFoundInDword @@SLInDWord_pos: Mov EAx, ECx Pop ECx Pop EBx Emms Ret @@ScanLoopExit: Pop ECx Pop EBx Xor EAx, EAx Emms Ret

← →
Ihor Osov'yak © (2004-10-06 01:06) [204]

Ребята, влом отслеживать полет изменений кода.. :-)
Если можно, полный код в студию...

← →
GuAV © (2004-10-06 01:16) [205]

Ihor Osov"yak © (06.10.04 01:06) [204]
пока что [193]. Однако он ещё не проходит тест на выход из буфера.

[203] - я привел ошибочный код. как сейчас понял зря.

← →
Ihor Osov'yak © (2004-10-06 01:20) [206]

2 [205] GuAV © (06.10.04 01:16)

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

← →
GuAV © (2004-10-06 01:28) [207]

Хотя в тесте от Sha тоже ошибка. Или фича. Мы ведь договорились, что строка начинается на границе двойного слова или как ? [183]
Видимо прийдётся делать Validate для Validate 0 8-))

← →
Ihor Osov'yak © (2004-10-06 01:49) [208]

2 [207] GuAV © (06.10.04 01:28)
ну, иногда лучше перебдить, чем недобдить..
Предположим фантастический вариант - я содал тело строки ручками.. не на границе двойного слова. И передал как параметр.. :-)
Лично я не сторонник таких финтов, но в принцыпе такое может быть. Поэтому я бы дал предпочтение функции, прошедшей валидацию от Sha.

← →
GuAV © (2004-10-06 01:58) [209]

Тогда берите любую функцию от JOH. Они прошли даже мой агрессивный тест, когда даже к 0-терминатору обратится нельзя.

← →
GuAV © (2004-10-06 02:07) [210]

Хотя поскольку ошибка приведёт AV именно в месте его причины, а не далеко после процедуры можно просто завернуть её в try... except on EAccesViolation do Result:=0 end;
Этот код может кому-то не понравится, но он нужен только в случае вольностей упомянутых в [208], в "нормальном" режиме функция не приводит к AV.

← →
GuAV © (2004-10-06 03:12) [211]

Тут появиась мысль, ка сделать фцию, проходящую любые подобные validate0. Надо сделать вначале test edx, 3; jnz odd_align и там обработать такую ситуацию, обработав эти 1..3 байт и вернуться. Код обработки может быть и не оптимальным, лишь бы он корректно работал.

← →
Sha © (2004-10-06 09:47) [212]

> GuAV © (06.10.04 01:28) [207]
> Хотя в тесте от Sha тоже ошибка. Или фича. Мы ведь
> договорились, что строка начинается на границе двойного слова или как ? [183]

У меня так и сделано.
Длина строки = 4n+3.
Конец строки (терминатор) фиксирован на нижней границе страницы.
Начало строки плавает. Но всегда находится на грацице двойного слова.

← →
Sha © (2004-10-06 09:48) [213]

Конец строки (терминатор) фиксирован на верхней границе страницы.

← →
GuAV © (2004-10-06 12:13) [214]

Sha © (06.10.04 09:47) [212]
Я поняла в чём дело.
Call @@CharPos
Отсюда вход с not alined EDX.

← →
GuAV © (2004-10-06 12:13) [215]

Sha © (06.10.04 09:47) [212]
Я понял в чём дело.
Call @@CharPos
Отсюда вход с not alined EDX.

← →
Defunct © (2004-10-06 16:33) [216]

>Sha [198]

Функция [193] прошла тест [198] так что можете смело использовать.

> Ihor Osov"yak © (06.10.04 01:06) [204]

[193] - полный рабочий вариант кода.
[195] - тесты PosDef_MMX = [193]

← →
Sha © (2004-10-06 17:02) [217]

> Defunct © (06.10.04 16:33) [216]
> Функция [193] прошла тест [198] так что можете смело использовать.

На моем компьютере не проходит.

← →
Defunct © (2004-10-06 17:25) [218]

> Sha

хм..

if Validate0 {[198]} and
Validate1 and
Validate2 and
Validate3 and
Validate4 and
Validate5 and
Validate6 and
Validate7 and
Validate8 and
Validate9 and
Validate10 and
Validate11 then

PosDef_MMX Passed

Если вас не затруднит, можете посмотреть где именно происходит выход за границу последнего Dword, потому как проверял на разных компах, везде проходит. (сам я не могу найти).

← →
Sha © (2004-10-06 17:43) [219]

> Defunct © (06.10.04 17:25) [218]
> if Validate0 {[198]} and

Такой if встречается в 2-х местах (Validate & ValidateAll).
Исправил оба?

> Если вас не затруднит, ...
Давай на "ты". Конечно, посмотрю. Но чуть позже.

← →
Defunct © (2004-10-06 17:51) [220]

> Такой if встречается в 2-х местах (Validate & ValidateAll).
Исправил оба?

Исправил только ValidateAll,
все теперь порядок, вижу где выходит.

сейчас подправлю.

← →
Jeer © (2004-10-06 18:04) [221]

Грандиозно мужики !
Живо мне напомнило успешные попытки втиснуть в 64K и добиться нужного быстродействия для бортового компьютера на i8080 (580)
решения навигационных задач подводного средства движения в далекие 70-е годы.

Так держать !

← →
Defunct © (2004-10-06 18:07) [222]

Или я что-то там не понял, или тест работает не совсем корректно.

Хочу немного уточнить задачу.

Допустим строка из одного символа "a", она ведь поидее выровняна до DWord т.е. реальная длинна = |-8| + 4 = 12

-8 Dword
-4 Dword
0 "a"
1 0
2 мусор
3 мусор

У меня происходит чтение строки
@CharPos:
Mov EAx, [EDx]
за DWord выхода нет, но Validation0 вызывает исключение именно на этой строчке. Поставил проверку на 0 (думал может туда случайно проходит вызов при буфере = 0) ничего не изменилось.

← →
Sha © (2004-10-06 18:13) [223]

> Defunct

Ломается при таком обращении ConstantPos("ef9","efg").
Первая пересылка
@@Scan4: Mov Ch,[EAx]
проходит нормально, т.к. адрес в edx выровнен.
При заходе на вторую пересылку адрес в edx уже на 1 больше.
Старший байт читаемого слова лежит на защищенной странице => AV.

← →
Sha © (2004-10-06 18:18) [224]

Defunct © (06.10.04 18:07) [222]

Строку из одного "a" тест никогда не генерирует.
В тесте используются строки длиной 4*n+3 - они с учетом
терминатора всегда занимают целое число двойных слов.

← →
Defunct © (2004-10-06 18:26) [225]

Еще один загадочный эксепшин. Идет проверка, не выходит ли подстрока за границу буфера, и если не выходит, тогда происходит сканирование в обратном порядке (с конца строки). Опять же 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% где-то в тесте что-то не учтено.

← →
Sha © (2004-10-06 18:27) [226]

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

← →
Defunct © (2004-10-06 18:29) [227]

> При заходе на вторую пересылку адрес в edx уже на 1 больше.

Понял

← →
Sha © (2004-10-06 18:32) [228]

> Defunct © (06.10.04 18:26) [225]
> 100% где-то в тесте что-то не учтено.

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

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

Такой 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:

Мой 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, плиз.

2ALL выложите плиз полный окончательный вариант "ускоренной POS" ;)

[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

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

с новым SmallScan [232] стало гораздо хуже:

PosGuru&Def 4 194 134 328

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 © (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, под которые подстраиваемся, но не оптимизируем.

У меня промелькнула идея которая не только может значительно ускорить функцию, но и решит проблему с validate 0. Как вы думаете, если при MMX сканировании и при CharPos (раскрученном цикле) формировать массив найденных символов и потом с ним и работать. (т.е. например, просмотрели 8 символов, нашли 3 совпадения и дальше уже работает с совпадениями, все найденные совпадения не подходят - тогда продолжаем смотреть следующие 8 символов).

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

@@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]
Не думаю что я справлюсь раньше. Пока я ещё не полностью понимаю работу имеющесйся. Однако, завтра у меня будет много времени.

[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

Поиск в бинарном файле Найти похожие ветки