Поиск подстроки в сборке

Мне интересно, есть ли более эффективный метод поиска подстроки в сборке, чем то, что я сейчас планирую делать.

Я знаю, что строковая инструкция "scansb/scasw/scads" может сравнивать значение в EAX со значением, адресуемым EDI. Однако, насколько я понимаю, я могу искать только один символ за раз, используя эту методологию.

Итак, если я хочу найти местоположение «помощи» в строке «пожалуйста, помогите мне», я мог бы использовать scansb, чтобы найти смещение h, а затем перейти к другой функции, где я сравниваю остаток. Если остаток неверен, я возвращаюсь к scansb и снова пытаюсь выполнить поиск, на этот раз после предыдущей метки смещения.

Тем не менее, я бы не хотел делать это, а затем обнаружить, что есть более эффективный метод. Любой совет? заранее спасибо


string x86 algorithm assembly nasm
person BSchlinker    schedule 06.12.2010    source источник
comment
Сомневаюсь, что есть лучший способ. Возможно, вы захотите посмотреть на эту реализацию в AOA, но она выглядит так же: maven.smith.edu/~thiebaut/ArtOfAssembly/CH15/   -  person Madhur Ahuja    schedule 06.12.2010
comment
Также см. производительность Agner Fog strstr() и g++ встроенной strstr().   -  person jww    schedule 09.10.2018

Ответы (3)


arrow_upward
4
arrow_downward

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

Если у вас есть аппаратное обеспечение, вы можете использовать функции сравнения строк sse 4.2, которые работают очень быстро. См. обзор http://software.intel.com/sites/products/documentation/studio/composer/en-us/2009/compiler_c/intref_cls/common/intref_sse42_comp.htm и пример с использованием встроенных функций C http://software.intel.com/en-us/articles/xml-parsing-accelerator-with-intel-streaming-simd-extensions-4-intel-sse4/

Если у вас есть длинные подстроки или несколько шаблонов поиска, Boyer-Moore, Knuth-Morris-Pratt и Рабина-Карпа могут оказаться более эффективными.

person Gunther Piez    schedule 06.12.2010
comment
+1 Отличный момент. Думает немного продвинулся с тех пор, как я изучил asm. - person Andrei Pana; 06.12.2010

arrow_upward
0
arrow_downward

Я не думаю, что есть более эффективный метод (только некоторые оптимизации, которые можно выполнить для этого метода). Также может представлять интерес это.

person Andrei Pana    schedule 06.12.2010

arrow_upward
0
arrow_downward

scansb это вариант сборки для strcmp, а не для strstr. если вам нужен действительно эффективный метод, вам нужно использовать лучший алгоритм.

Например, если вы ищете в длинной строке, вы можете попробовать некоторые специальные алгоритмы: http://en.wikipedia.org/wiki/String_searching_algorithm

person ruslik    schedule 06.12.2010