шемся слове осуществляется поиск нужного байта. Например, чтобы найти АЗСП-пробел (0x20) в слове х, необходимо найти нулевой байт в слове х Ф 0x20202020.

Аналогично, для поиска одинаковых байтов в словах д: иу выполняется поиск нулевого байта в слове х®у.

Код из листинга 6.2 и его модификшфш с неболышши изменениями можно использовать и для поиска, не связанного с границами байта. Например, пусть требуется найти нулевое значение (если таковое есть) в первых четырех битах, следующих за ними 12 битах или в послед-шх. 16. Для этого можно использовать код из листинга 6.2 с маской Ox77FF7FFF [51] (если длина поля равна 1, то в соответствующем разряде маски устанавливается 0).

Поиск в заданном диапазоне значений

Код из листинга 6.2 можно легко модифицировать для поиска байта, значение которого находигся в диапазоне от О до некоторого заданного значения, меньщего 128. В приведенном ниже фрагменте вычисляется индекс первого слева банта, значение которого находится в диапазоне от О до 9.

у = (Х & 0X7F7F7F7F) + 0x76767676; у = У х;

у = у 0X7F7F7F7F; Байты > 9 = OxFF

у = -У; Байты > 9 = 0x00

Байты <= 9 = 0x80

п = nlz(у) >> 3;

Рассмотрим более общий случай. Предположим, что в слове требуется найти первый слева байт, значение которого находится в диапазоне от а до fc, причем разность верхней и нижней границ этого диапазона меньще 128. Натфимер, в ASCII прописные буквы имеют значения от 0x41 до 0x5А. Чтобы найти первую прописную букву в слове, вычтем из него число 0x41414141 так, чтобы при этом не возникло распространения заемов за пределы байта. После этого поиск байта, содержащего значение из диапазона от О до 0x19 (разность 0x5 А-Ох41), вьшолняется так же, как и в приведенном выше коде. Используя формулы для вычитания из раздела 2.17 с очевидными упрощениями для у = 0x41414141, получим

d = (Х I 0x80808080) - 0X41414141; d = -((Х I 0X7F7F7F7F) * d); у = (d & 0X7F7F7F7F) + 0x66666666; у = У d;

у = у 0X7F7F7F7F; Байты, не равные 41-5А, становятся FF у = -У; Байты, не равные 41-5А, становятся 00

Байты, равные 41-5А, становятся 80

п = nlz(у) >> 3;

Для некоторых диапазонов значений возможен более простой код. Например, чтобы найти первый байт, содержащий значение в диапазоне от 0x30 до 0x39 (десятичная цифра в кодировке ASCII), необходимо выполнить операцию исключающего или с исходным словом и числом 0x30303030, а затем воспользоваться приведенным выше кодом для поиска байта со значением из диапазона от О до 9 (это упрощение применимо в тех случаях, когда п старших битов верхней и нижней границ диапазона совпадают и нижняя граница заканчивается 8 - и нулевыми битами).

Эти методы могут быть адаптированы для работы с большими диапазонами без дополнительных команд. Например, для поиска индекса первого слева байта, значение ко-

Toporo находится в диапазоне от О до 137 (0x89), строку программы поиска байта со значением от О до 9 у = у I X следует заменить строкой у = у & х.

Аналогично, заменив строку у » у 1 d в программе поиска первого слева байта со значением от 0x41 до 0x5А строкой у = у & d, получим код для поиска первого слева байта, содержащего значение в диапазоне от 0x41 до OxDA.

6.2. Поиск строки единичных битов заданной длины

Задача заключается в поиске в слове, находящемся в регистре, первой строки из единичных битов, длина которой не менее п. В результате поиска возвращается позиция первого бита строки; если такой строки в слове не обнаружено, выдается некоторое специальное значение. Вариантами этой задачи являются задача ответа на вопрос о существовании данной строки (возвращается значение да или нет) и задача поиска строки, состоящей ровно из п единичных битов. Задача находит применение в программах распределения дискового пространства, в частности при дефрагментации диска (перемещения данных на диске таким образом, чтобы в результате все блоки, в которых хранится некоторый файл, располагались непрерывно, друг за другом). Эта задача была предложена мне Альбертом Чангом (Albert Chang), который указал, что при ее решении можно использовать функцию определения количества ведущих нулевых битов.

Далее предполагается, что компьютер имеет команду (либо подпрограмму) вычисления функции nlz, определяющей количество ведущих нулевых битов.

Первым в голову приходит простейший алгоритм: вычислить количество ведущих нулевых битов и выполнить сдвиг влево на полученное число. Затем вычисляется количество ведущих единичных битов (инвертируя слово и подсчитывая количество ведущих нулевых битов). Если количество нулевых битов в этой группе не меньше заданной длины строки, значит, искомая группа найдена. Если количество нулевых битов меньше требуембго, выполняется сдвиг слова влево на количество нулевых битов и все действия повторяются сначала. Соответствующий код приведен ниже. Если найдены п идущих подряд единичных битов, возвращается число от О до 31, указывающее позицию первого бита первой такой строки. В противном случае возвращается значение 32, указывающее на то, что соответствующая строка не найдена.

int ffstri(unsigned x, int n) {

int k, p;

p = 0; Инициализация возвращаемой позиции

while (x != 0) {

return 32;

Алгоритм вполне применим, если цикл выполняется всего несколько раз, напркцер когда в слове х есть относительно большие группы нулевых и единичных битов. Это ус ловие вполне обычно для приложений, выполняющих распределение дискового пространства. Однако в худшем случае выполнение этого алгоритма занимает довольно много времени: например, при х=0х55555555 и п>2 вьшолняется около 178 команд из полного множества RISC-команд.

Алгоритм, который лучше справляется с наихудшим случаем, основан на последовательности команд сдвига влево и и. Чтобы понять, как он работает, рассмотрим поиск строки из восьми или более последовательных единичных битов в 32-битовом слове х. Ниже показано, как можно выполнить этот поиск.

*<-x&(*«l) x<-x&(x«2) x<-x&(x«4)

После первого присвоения единичные биты в х указывают начальные положения строк единичных битов с длиной 2. После второго присвоения единичные биты в х указывают начальные положения строк с длиной 4 (строк длиной 2, следующих за другими строками длиной 2). После третьего присвоения единичные биты в х указывают начальные позиции строк длиной 8. Применение функции nlz к получившемуся слову возвращает положение первого бита строки, длина которой не меньше 8. Если такой строки нет, возвращается 32.

Для разработки алгоритма, который бы работал с любыми длинами л от 1 до 32, следует взглянуть на задачу несколько иначе. Прежде всего заметим, что три приведенные выше присвоения можно выполнять в любом порядке. Обратный порядок может быть даже более удобным. Для иллюстрации общего метода рассмотрим случай л=10.

X, <-x &(х«5) х,«-х,&(х,«2)

Х,<-х2&(х2«1) X, <-Хз&(Хз«1)

Первая инструкция выполняет сдвиг на п/2. После этого задача сводится к поиску строки из пяти последовательных единичных битов в Xj. Это может быть сделано путем сдвига влево на [5/2J = 2 бита и выполнением команды и, после чего выполняется поиск

строки из трех единичных битов (3=5-2). Последние два оператора определяют начальные позиции строк длиной 3 в слове х. Сумма величин всех сдвигов всегда равна и -1. Соответствующий код показан в листинге 6.5. Время работы кода при п от 1 до 32 составляет от 3 до 36 команд из полного множества RISC-команд.

Если п не очень велико, имеет смысл развернуть цикл (на 32-разрядном компьютере достаточно повторить тело цикла пять раз) и опустить проверку п > 1. Код с развернутым циклом не содержит условных переходов и выполняется за 20 команд (последнее присвоение п можно опустить). Тем не менее для малых значений п лучше использовать код с циклом. В случае малых значений п поиск по алгоритму с развернутым циклом выполняется медленнее, потому что как только переменная п становится равной 1, ее значение больше не изменяется и, таким образом, все последующие действия не изменят значений ни х , ни п. В смысле количества выполняемых инструкций развернутый цикл работает быстрее обычного цикла при п > 5.