в листинге 6.2 функция zbytel(jc) вычисляется без использования команд ветвления.

Идея заключается в том, чтобы преобразовать каждый нулевой байт в 0x80, а каждый ненулевой - в нулевой, после чего достаточно воспользоваться функцией подсчета ведущих нулевых битов. Если в компьютере есть команда для вычисления количества ведущих нулевых битов и команда или-не, то для поиска нулевого байта потребуется восемь команд. Похожий алгоритм описан в [42].

Листинг 6.2. Поиск первого слева нулевого байта без использования ветвления

int zbytel (unsigned х) {

unsigned у; int n;

Исходный байт: 00 80 другие у = (Х & 0X7F7F7F7F) + 0x7F7F7F7F; 7F 7F IXXXXXXX у = -(у I X I 0X7F7F7F7F); 80 00 ОООООООО

п = nlz(у) >> 3; п = О ... 4; 4 если в х

return п,- нет нулевого байта

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

п = (32 - nlz(-y & (у - 1))) » 3;

Таким образом, если в компьютере имеются команды или-не и и-не, решение поставленной задачи будет получено за 12 команд.

Следует отметить, что на PowerPC в большинстве случаев процедура поиска первого спрааа нулевого байта не нужна; вместо нее можно воспользоваться командой загрузки слова с обратным порядком байтов Iwbrx.

Процедура из листинга 6.2 крайне ценна для 64-разрядных компьютеров. Дело в том, что на 64-разрядном компьютере эта процедура (с необходимыми вполне очевидными изменениями) вьшолняется примерно за то же количество команд (семь или десять - в зависимости от способа генерации констант), что и на 32-разрядной. Процедура с использованием команд ветвления (листинг 6.1) в худшем случае потребует для вьшолнения 23 команды.

Если требуется только проверить, есть ли в данном слове нулевой байт, то после второго присвоения у можно добавить команду ветвления при нулевом значении (или, напротив, ненулевом).

Если команда nlz отсутствует, поиск первого нулевого байта усложняется. В листинге 6.3 показан один из вариантов поиска нулевого байта в слове без использования функции nlz (приведена только исполняемая часть кода).

Листинг 6.3. Поиск первого слева нулевого байта без использования функции nl

Исходный байт; 00 80 другие у = (х & 0X7F7F7F7F) + 0x7F7F7F7F; 7F 7F IxxxXXXX у = -(у I X I 0X7F7F7F7F); 80 00 00000000

Эти шаги отображают: if (у == 0) return 4; 00000000 ==> 4,

else if (у > OxOOOOFFFF) 80хххххх ==> О,

return (у » 31) * 1; 0080XXXX ==> 1,

else 000080XX ==> 2,

return (у » 15) * 3; 00000080 ==> 3,

Этот код требует выполнения от 10 до 13 базовых RISC-команд (10 команд в случае, когда в слове нет нулевого байта). Таким образом, этот алгоритм, пожалуй, уступает коду из листинга 6.1, хотя и имеет меньшее количество команд вегвления. К сожалению, масштабирование данного алгоритма для 64-разрядных компьютеров не эффективно.

Рассмотрим еще одну возможность избежать использования функции nlz. Значение у, вычисленное в листинге 6.3, состоит из четырех байтов, каждый из которых равен либо 0x00, либо 0x80. Остаток от деления такого числа на Ox7F представляет собой исходное число, единичные биты которого (их не более четырех) перемещены в четыре крайние справа позиции. Таким образом, остаток от беззнакового деления в диапазоне от О до 15 однозначно идентифицирует исходное число, например:

remu (0x80808080,127) = 15, remu (0x80000000,127) = 8, remu(0x00008080,127) = 3.

Это значение можно использовать при поиске нулевого байта в качестве индекса в таблице размером 16 байт. Таким образом, часть кода, которая начинается со строки if (у == о), можно заменить следующим (здесь у - беззнаковое):

static char table[16] = {4, 3, 2, 2, 1, 1, 1, 1,

О, О, О, О, О, о, о, 0};

return table[у%127] ;

Вместо 127 можно воспользоваться числом 31, но, разумеется, с другим массивом table.

На практике методы, использующие остаток от деления на 127 или 31, не применяются, так как получение остатка от деления занимает 20 и более тактов даже при непосредственной аппаратной реализации этой команды. Тем не менее код из листинга 6.3 можно усовершенствовать, заменив часть кода, начинающуюся со строки if (у == 0), одной из двух следующих строк:

return table[hopu(y, 0x02040810) & 15]; return table[у*0х00204081 >> 28];

Здесь hopu (а, b) означает старшие 32 бита беззнакового произведения а и Ь. Во второй строке в соответствии с соглашением, принятым в языках высокого уровня, предполагается, что значение произведения представляет собой младшие 32 бита результата. Этот метод вполне практичен, особенно на компьютерах с быстрым умножением, а также на тех, у которых есть команда сдвига-и-сложения, так как в последнем случае умножение на 0x00204081 реализуется как

у(1 + 2+2" + 2) = у(1 + 2)(1 + 2").

При использовании такого 4-тактового умножения общее время вычислений составляет 13 тактов (7 тактов для вычисления у, 4 - для выполнения команд сдвига-и-сложения, 2 - для сдвига вправо на 28 и индексирования массива table); кроме того, этот код не содержит команд условного перехода.

Этот алгоритм достаточно просто масштабируется для применения на 64-разрядных компьютерах. В алгоритме с остатком от деления используем инструкцию

return table[у%511];

Здесь table содержит 256 элементов со значениями 8, О, 1, О, 2, О, 1, О, 3, О, 1, О, 2, О, 1, 0,4,... (т.е. table [i] равно количеству завершающих нулевых битов в О-В мультипликативных методах используется одна из двух инструкций:

return table[hopu(у, 0x0204081020408100) & 255] ; return table [у*0х0002040810204081»56] ;

Здесь table имеет размер 256 и значения 8, 7, 6, 6, 5,5,5,5,4, 4,4,4,4,4,4,4, 3,.... Умножение на 0x2040810204081 можно выполнить за 13 тактов следующим образом:

<,<-у(1 + 2), <,,(1 + 2"), /,/,(1 + 2»).

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

Если на 32-разрядном компьютере нет отдельной команды или-не, то вместо команды не во втором присвоении у в листинге 6.3 можно использовать один из трех описанных выше операторов return с массивом table [i] = {О, о, о, о, О, О, О, О, 1, 1, 1, 1, 2, 2, 3, 4}. Эта схема не работает для 64-битового компьютера.

Рассмотрим еще одну интересную вариацию процедуры из листинга 6.2, которая не использует функцию nlz. Пусть a,b,cvid - однобитовые переменные, означающие предикаты "первый байтд: ненулевой", "второй байтд: ненулевой" и т.д. Тогда

zbytel(x) = в +аА +в*с +abcd .

Здесь умножение реализуется при помощи команды и, что дает процедуру, показанную в листинге 6.4 (приведена только выполняемая часть кода).

Листинг 6.4. Поиск первого слева нулевого байта вычислением полинома

у = (х & 0X7F7F7F7F) + 0x7F7F7F7F;

у = у I X; 1 в ненулевых байтах

tl = у » 31; tl = а

t2 = (у » 23) & tl; t3 = (у >> 15) & t2; t4 = (у » 7) & t3; return tl + t2 + t3 + t4;

t2 = ab t3 = abc t4 = abed

Всего требуется выполнить 15 базовых RISC-команд. Этот алгоритм работает не очень быстро, зато часть вычислений можно распараллелить. На суперскалярном компьютере, которая способна выполнять параллельно до трех независимых арифметических,команд, выполнение алгоритма займет 10 тактов.

Внесение небольших изменений позволяет легко найти первый справа нулевой байт:

zbyter(x) =abcd +bcd +cd+d. (Здесь дая вычислений потребуется на одну команду и больше, чем в коде из листинга 6.4)

Некоторые обобщения

Функции zbytel и zbyter могут использоваться при поиске байта, содержащего некоторое заданное число. Для этого над аргументом х и словом, в каждом байте которого содержится нужное значение, производится операция исключающего или, и в получив-