Нахождение подстроки в сборке

Question

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

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

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

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

Answer 1

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

Если у вас есть оборудование, вы можете использовать функции сравнения строк 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Алгоритмы Морриса-Пратта и Рабина-Карпа могут быть более эффективными.

Answer 2

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

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

Answer 3

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