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

Узнай цену своей работы

Формулировка задачи:

Привет! В общем читаю я файл (большой) и хочу найти кол-во вхождений в этот файл некоторой последовательности байт, допустим "AC DF EE FF", как можно на ассемблере (буду вставлять в виде ассемблеровской вставки в код на С++) написать экстремально быстрый поиск этой последовательности? В общем на входе:
char* haystack; //массив байтов заранее не известного содержимого
char* hsSize; //размер haystack
char* needle; // последовательность байт, которую нужно искать в haystack
char* nSize; //размер needle
В общем в haystack могут быть любые данные, такие "ААААААААFCFCAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", а может быть и белый шум... В общем нужен код ассемблеровской вставки с экстремально быстрым поиском Моде задействовать SSE2 ? или ещё чего? Это только приветствуется! Почему ассемблер? Хочу минимизировать кол-во инструкций при поиске. Знаю, что для человека, хорошо знакомого с masm-ом, накидь пару строк не составит труда, по этому надеюсь на ваше помощь в великие гуру хардкора
Между прочим, я как бы не студент и халявщик))) Я просто хочу ускорить свой софт и пока что раздумываю над тем, как можно это сделать. Просто бурта форс с небольшой оптимизацией меня как - то не впечатлил:
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 ускорить, но тут всю скорость просрёшь на копирование данных в видео память...

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

textual
Листинг программы
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                 ; выход!

Объяснение кода листинга программы

Ниже представлен код на языке Assembler со следующей постановкой задачи — «Как написать на masm под х86 функцию поиска кол-ва вхождений последовательности байт в большом массиве байт?» 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 mov cx,hsSize mov al,byte [needle] find: repne scasb jz ok jmp errorFind ok: push cx di mov cx,nSize dec di mov si,needle 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 Вывод: Кол-во вхождений последовательности '0knvbcdhg' в строке '45210fffdknvbcdhgff751fghdj001234' равно 2.

Оцени полезность:

7   голосов , оценка 4.143 из 5
Похожие ответы