Длина строки на ассемблере

Метки:  , ,

Вычисление длины строки на ассемблере, как одна из наиболее часто возникающих задач, занимала умы разработчиков еще на заре компьютерной эпохи :) Однако впоследствии, с появлением и развитием операционных систем, и, соответственно, доступностью многочисленных встроенных сервисных функций работы со строками (в числе которых предоставляется и функция вычисления длины строки), подобные помысли практически перестали волновать умы представителей сообщества. С развитием высокоуровневых языков все меньше людей задумываются о том, "а как же там на низком уровне всё это реализовано", редко кого волнует оптимизация кода по быстродействию. Даже разработчики, что-либо пишущие на ассемблере, охотнее обращаются к встроенному функционалу, предоставляемому программным интерфейсом, нежели собственными наработкам, и их можно понять, поскольку производительности предоставляемых системой функций, да и языка в целом вполне хватает для того, что бы в большинстве задач не отвлекаться на пару сотен лишних тактов.
К вычислению/заданию длины строки в исходном коде применимы две основных стратегии:

  • Статическая - когда длины строк известны заранее и задаются в исходном коде в виде констант;
  • Динамическая - когда длины строк заранее неизвестны (данные, полученные в процессе работы) и вычисляются в ходе выполнения кода;

Со статическим определением длины строки всё довольно-таки просто, чаще всего подход реализуется следующим образом:

и впоследствии используется в коде как-то вот так:

invoke TextOut,[pHMain],0,0,_text,SIZEOF._text

А вот с динамическим определением длины строки не все так однозначно. Основная, доступная разработчикам системная функция, это lstrlen, экспортируемая (предоставляемая) библиотекой kernel32.dll. Исключительно из любопытства хотелось бы оценить качество кода встроенных функции Windows и посмотреть, так ли они хороши, как должны быть. Попробуем поизучать код функции lstrlen, так сказать, "под микроскопом", то есть в отладчике, отладив код любой типовой программы, использующей данную функцию. После передачи управления на библиотечную функцию я просто протрассировал её до блока вычисления длины строки и скопировал найденный код, вот что у меня получилось:

Вы знаете, результатом я был приятно удивлен, потому как, честно говоря рассчитывал на худшее. Оказывается, сам вложенный цикл прохода по строке (строки 9-12), на который должно тратиться основное процессорное время, достаточно хорошо оптимизирован как по байт-коду, так и по скорости выполнения. Он состоит из четырех "быстрых" команд (минимальное количество микроопераций (μops) и задержек (latency)): mov, inc, test, jne. Однако тут существует другая проблема, в той или иной мере свойственная всем системным функциям современных операционных систем - это "обвес" функции и "вложенные" вызовы. Все дело в том, что от момента, кода ваш код вызывает функцию lstrlen и до выполнения непосредственно блока сравнения, происходит N-ое количество операций: вызовы сторонних функций, выполняющих дополнительную работу, сохранение/восстановление многочисленных стековых фреймов, проверки различных локальных и глобальных переменных и далее по списку. Отсюда можно сделать вывод, что при однократном вызове функции lstrlen существенной "просадки" скорости выполнения не будет, однако при многочисленных циклических вызовах на этот "лишний" с точки зрения вашей программы код будет уходить уже существенное процессорное время. Тем не менее, с этим уже ничего не поделаешь, это реалии всех операционных систем, код системных библиотек которых взаимосвязан, и тем самым привязан к различным дополнительным алгоритмам.

Собственная реализация для ASCIIZ-строк

Откровенно говоря, поскольку идея собственной реализации вычисления длины строки на ассемблере является одной из базовых в творчестве каждого кодера, у меня она родилась достаточно давно, еще в те далекие времена, когда на нашем информационном пространстве свирепствовал MSDOS версии 3.30, а железо было представлено отечественными машинками ЕС-1840 и ЕС-1841. Причина была достаточно прозаична, требовались функции для реализации тех или иных частей приложений/загрузчиков/осей. К сожалению (а может и к счастью), вся эта масса кривого кода давно уже переместилась в информационный ад (при условии, что он существует), а те дискеты, на которых она когда-то размещалось, скорее всего догнивают под многометровым слоем цивилизационных отходов где-то на региональной мусорной свалке. Но кое-что память человеческая сумела сохранить.

16-битный код

Для тех, кто глубокими ночами, в зашторенной комнате с приглушенным светом и закрытой на ключ дверью, балуется 16-битным кодом реального режима, могу предложить такую вот реализацию функции:

Символом завершения для строки является ноль (0), но вы можете использовать и любой другой. Соответственно, на вход функции подается смещение строки в регистре si, а на выходе получаем длину строки в регистре bx. Получилась функция размером в 10 байт.

32-битный код

Однако вернемся в реалии наших дней. По аналогии набросал функцию с 32-разрядными инструкциями, код которой выглядит следующим образом:

На выходе (в регистре eax) получаем длину строки без учета нуль-терминатора (завершающего нуля). Не смотря на все старания код получился не оптимальным. Как-то, бродя по Сети в поисках информации и изучая различные прототипы подсчета длины строки на ассемблере, я обнаружил интересную тему на форуме KolibriOS. Один из найденных в топике вариантов алгоритма был, откровенно говоря, лучше оптимизирован:

В этом примере используется интересный прием: если фактическое значение очередного байта строки равно 0, то при выполнении инструкции сравнения со значением 1 выставляется (взводится) флаг переноса (ведь значение меньше), который не модифицируется следующей по коду инструкцией inc, тем самым сохраняясь до инструкции сравнения jnc (может быть заменена на инструкции jl/jb). Теперь о размере кода, если мне не изменяет мой старый-добрый HIEW, код фрагмента занимает 15 байт "без обвеса" (кода сохранения/восстановления стекового фрейма), что на целых три байта короче моего (описанного выше) кода. По скорости выполнения данный фрагмент чуть быстрее за счет минимизации инструкций подготовки/завершения основного цикла.

Еще некоторое количество хороших реализаций функции подсчета длины строки можно найти на ресурсе Мэнхантера.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *