Форум программистов, компьютерный форум, киберфорум
Наши страницы
Assembler для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/2: Рейтинг темы: голосов - 2, средняя оценка - 4.50
TheCore
Заблокирован
1

Как написать на masm под х86 функцию поиска кол-ва вхождений последовательности байт в большом массиве байт?

20.02.2016, 10:47. Просмотров 449. Ответов 6
Метки нет (Все метки)

Привет!
В общем читаю я файл (большой) и хочу найти кол-во вхождений в этот файл некоторой последовательности байт, допустим "AC DF EE FF", как можно на ассемблере (буду вставлять в виде ассемблеровской вставки в код на С++) написать экстремально быстрый поиск этой последовательности?
В общем на входе:
C++
1
2
3
4
char* haystack; //массив байтов заранее не известного содержимого
char* hsSize; //размер haystack
char* needle; // последовательность байт, которую нужно искать в haystack
char* nSize; //размер needle
В общем в haystack могут быть любые данные, такие "ААААААААFCFCAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", а может быть и белый шум...

В общем нужен код ассемблеровской вставки с экстремально быстрым поиском
Моде задействовать SSE2 ? или ещё чего? Это только приветствуется!

Почему ассемблер? Хочу минимизировать кол-во инструкций при поиске.

Знаю, что для человека, хорошо знакомого с masm-ом, накидь пару строк не составит труда, по этому надеюсь на ваше помощь в великие гуру хардкора

Добавлено через 19 минут
Между прочим, я как бы не студент и халявщик))) Я просто хочу ускорить свой софт и пока что раздумываю над тем, как можно это сделать. Просто бурта форс с небольшой оптимизацией меня как - то не впечатлил:
Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
unsigned int FileScanner::smartBruteForce(QByteArray &data, QByteArray &needle)
{
    unsigned int count = 0;
    unsigned int dataSize = data.size();
    unsigned int needleSize = needle.size();
    unsigned int needleSizeCut = needleSize - 1;
    char* dp = data.data();
    char* np = needle.data();
    char lastNeedle = *(np + needleSize - 1);
 
    for(unsigned int i = 0; i < dataSize - needleSize + 1; i++)
    {
        if(*(dp + (i + needleSizeCut)) != lastNeedle) //This is smart technology ))))
            continue;
        unsigned int j;
        for(j = 0; j < needleSize; j++)
        {
            if(*(dp + (i + j)) != *(np + j))
                break;
        }
        if(j == needleSize)
            count++;
    }
    return count;
}


Ещё думал над КМП методом (Алгоритм Кнута–Морриса-Пратта), но он относительно хорош для поиска одного вхождения, а не всех или я пока что не особо в него в ник...
Думал даже на GPU ускорить, но тут всю скорость просрёшь на копирование данных в видео память...
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.02.2016, 10:47
Ответы с готовыми решениями:

Как использовать функцию, выдающую через переменную типа байт результат, объём которого больше, чем байт?
Есть сканер отпечатков. Для него есть компонент ActiveX. У этого компонента есть функции. Среди них...

Определение в массиве из 15 байт количества байт, в которых сброшены 6 и 4 биты
Помогите пожалуйста разработать программу на языке ассемблера, определяющую в массиве из 15 байт...

Алгоритм поиска последовательностей в массиве байт
Известно: есть массив байт массив разделен на блоки: &lt;head&gt; &lt;line1&gt; &lt;line2&gt; &lt;kan1&gt; &lt;kan2&gt;...

Если команда состоит из двух байт, то как прописать каждый байт отдельно?
Если команда состоит из двух байт , то как прописать каждый байт отдельно? Например , нужно...

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

6
Полный 30h
Эксперт быдлокодинга
1822 / 447 / 61
Регистрация: 04.11.2010
Сообщений: 1,226
20.02.2016, 16:08 2
Если речь идёт о некой последовательность фиксировано длинны ( в вашем примере 4 байта) то при помощи ассемблера ищется все по сути одной командой. А именно SCASD. Если нет, то немного по другому. Конкретизируйте размер искомого, произвольный или фиксированый . Если фиксированный, то укажите размер.
0
TheCore
Заблокирован
20.02.2016, 18:55  [ТС] 3
Цитата Сообщение от Полный 30h Посмотреть сообщение
Конкретизируйте размер искомого, произвольный или фиксированый .
Гмм размер произвольный, наверное от 1 до 100 байт
0
Полный 30h
Эксперт быдлокодинга
1822 / 447 / 61
Регистрация: 04.11.2010
Сообщений: 1,226
20.02.2016, 21:20 4
TheCore, я могу попробовать написать такой поиск, правда это будет на FASM и стыковать с С++я не умею. Напустите на свой файл и скорость уже меряйте сами. Так пойдёт?
0
TheCore
Заблокирован
20.02.2016, 21:44  [ТС] 5
Цитата Сообщение от Полный 30h Посмотреть сообщение
Так пойдёт?
К сожалению нет, т.к. fasm не проканает в качестве ассемблеровской вставки в С++... Спасибо за попытку помочь
0
Somebody
2809 / 1620 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
21.02.2016, 12:19 6
Цитата Сообщение от TheCore Посмотреть сообщение
Ещё думал над КМП методом (Алгоритм Кнута–Морриса-Пратта), но он относительно хорош для поиска одного вхождения, а не всех или я пока что не особо в него в ник...
Не особо вник, видимо. КМП тут как раз не помешал бы.
0
R71MT
7652 / 1589 / 323
Регистрация: 29.07.2014
Сообщений: 2,636
Записей в блоге: 5
21.02.2016, 15:06 7
Цитата Сообщение от TheCore Посмотреть сообщение
fasm не проканает в качестве ассемблерной вставки в С++.
..так главное-же принцип, а потом изменишь синтаксис на масм/тасм (или чё там у тебя)

Добавлено через 21 минуту
Цитата Сообщение от TheCore Посмотреть сообщение
допустим "AC DF EE FF",
..файл (в котором будешь искать подстроку) бинарный что-ли? Или обычный/текстовый?

Добавлено через 2 часа 7 минут
TheCore, Поиск вхождения под/строки в строку можно организовать так..
Чтоб не тратить время на поиск с каждой позиции строки, спервА найдём первый/искомый символ в строке.
Если такой символ есть, то начинаем с этой позиции сравнивать всю под/строку в строке. В принципе это стандартный алгоритм, хотя можно ещё каждый раз передвигать указатель в строке и сравнивать под/строку с новой позиции строки.

Вот тебе первый вариант на FASM'е.
Чтоб подмять его под MASM, достаточно (там где нужно) добавить директивы "OFFSET" и "PTR".
Тебе нужен только выделенный участок кода. В примере ниже мы получим результат "FALSE". Чтоб получить "TRUE" достаточно убрать нуль в начале под/строки. Думаю алгоритм понятен:

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
org  100h
jmp  start
 
mess0   db  13,10,'<==== TRUE $'  ; мессага если есть вхождение,
mess1   db  13,10,'<=== FALSE $'  ; .. и если нет вхождения под/строки
 
haystack  db  '45210fffdknvbcdhgff751fghdj001234'  ; строка (данные твоего файла)
hsSize    =   $ - haystack   ; длина строки
needle    db  '0knvbcdhg'    ; под/строка
nSize     =   $ - needle     ; длина под/строки
 
start:
;================================================================================
   mov   di,haystack         ; место для поиска SCASB'ом
   mov   cx,hsSize           ; кол-во повторов
   mov   al,byte [needle]    ; искать будем первый символ под/строки
find:                        ;
   repne scasb               ; прекратить при совпадении!
   jz    ok                  ; переход, если есть совпадение
   jmp   errorFind           ; иначе: ошибка!
ok:                          ;
   push  cx di               ; сохраняем счётчик и позицию в строке
   mov   cx,nSize            ; меняем счётчик на длину под/строки
   dec   di                  ; SCASB проскочил позицию. вернём её..
   mov   si,needle           ; SI указывает на адрес под/строки
   repe  cmpsb               ; сравниваем строки до не совпадения
   jz    stopFind            ; переход, если строки совпали
   pop   di cx               ; иначе: восстанавливаем счётчик и позицию в строке
   jmp   find                ; и продолжаем поиск в строке со-старой позиции
;================================================================================
stopFind:                    ; поиск дал результат!
   mov   ah,9                ;
   mov   dx,mess0            ;
   int   21h                 ;
   jmp   exit                ;
errorFind:                   ; прокол!
   mov   ah,9                ;
   mov   dx,mess1            ;
   int   21h                 ;
 
exit:                        ;
   xor   ax,ax               ;
   int   16h                 ;
   int   20h                 ; выход!
0
21.02.2016, 15:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.02.2016, 15:06

Как вывести 10 байт после определенных байт из файла
Здравствуйте. Есть к примеру файл с расширением *.bin, подскажите как реализовать вывод на экран 12...

А можно сделать так (разбить как нибудь или запятые вставить ), чтобы было не 8998989 байт, а 8,998,989 байт ?
Кстати, вот еще вопрос... В переменной (например, filesize) хранится размер файла. При выводе...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru