x»3l

-x»3l

Наличие команд сравнения допускает решения из трех инструкций.

(д;>0)-(д;<0) (д;гО)-(д;<0)

С •

И последнее замечание: почти всегда работает формула -х»31 возникает только при х = -2".

х»21

2.8. Трехзначная функция сравнения

Трехзначная функция сравнения представляет собой определенное обобщение функции sign и определяется следующим образом:

стр(х,у) =

-1, О, 1,

х<у, Х = У, х>у.

Данное определение справедливо для любых переменных"- и знаковых и беззнаковых. Все, что говорится в этом разделе, если явно не оговорено иное, применимо к обоим случаям.

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

{х>у)-{х<у) {х>у)-{х<у)

Решение для беззнаковых целых чисел на компьютере PowerPC приведено ниже [10]. На этой машине "перенос" означает "не заем".

subf R5, Ry, Rx # R5 <-- Rx-Ry

subfc R6, Rx, Ry # R6 <-- Ry- Rx, установлен перенос

subfe R7, Ry, Rx # R7 <-- Rx-Ry+перенос, установлен перенос

subfe R8, R7, R5 # R8 <-- R5-R7+nepeHoc, (установлен перенос)

Если ограничиться командами из базового набора RISC-команд, то эффективного метода вычисления этой функции нет. Для вычисления х<у , х<у и других команд сравнения потребуется выполнить пягь команд (см. раздел 2.11), что приводит к решению, содержащему 12 команд (при использовании определенной общности вычислений х<у и у<х). На RISC-мащинах с базовым набором команд лучшим путем решения будет использование команд сравнения и ветвления (в худшем случае потребуется выполнить шесть команд).

2.9. Перенос знака

Функция переноса знака (известная в Fortran как ISIGN), определяется следующим образом:

abs(jc), у>0.

ISIGN(a;,y) =

-abs(jc), у<0.

2.8. ТРЕХЗНАЧНАЯ ФУНКЦИЯ СРАВНЕНИЯ

; ошибка

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

1*-у»Ъ\; Г<-(хФу)з>31;

ISIGN(jf,y) = (abs(x)®f)-t= lSlGN{x, y) = {x®t)-l =

= {bs(x) + t)®t ={x+t)®t

2.10. Декодирование поля *Ч) означает 2**п"

Иногда О или отрицательное значение для некоторой величины не имеет смысла. Поэтому она кодируется нулевым значением в и-м поле, которое интерпретируется как 2", а ненулевое значение имеет обычный двоичный смысл. Например, у PowerPC длина поля в команде загрузки непосредственно заданной строки слов (Iswi) занимает 5 битов. Нелогично использовать эту команду для загрузки нуля байтов, поскольку длина представляет собой непосредственно заданную величину, но было бы очень полезно иметь возможность загрузить 32 байта. Длина поля кодируется значениями от О до 31, которые могут, например, означать длины от 1 до 32, но соглашение "нуль означает 32" приводит к более простой логике, в особенности когда процессор должен также поддерживать соот-ветствуюшую команду с переменной (задаваемой в регистре) длиной, которая выполняет простое бинарное кодирование (например, команду Iswx на PowerPC).

Кодирование целых чисел от 1 до 2" в поле, ноль в котором означает 2", тривиально: просто маскировать биты целого числа с помощью маски 2"-1. Выполнить же декодирование без проверок и переходов не так-то просто. Ниже приведено несколько возможных вариантов для работы с третьим битом. Все эти варианты требуют выполнения трех команд, не считая возможных загрузок констант.

((х-1)&7) + 1 ((*-1)-8)+9 ((+7)8)-7 8-(-х&7)

((х + 7)&7) + 1 ((х+7)-8)+9 ((х-1)&8) + х -{-x\S)

2.11. Предикаты сравнения

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

На таких машинах, как MIPS, Compaq Alpha, и нашей модели RISC есть команды сравнения, которые непосредственно вычисляют большинство отношений и помещают однобитовый результат 0/1 в регистр общего назначения, а потому для таких машин приводимые ниже формулы не представляют особого интереса.

При вычислении функций сравнения двух операндов весьма полезной оказывается машинная команда "nabs", вычисляющая отрицательное абсолютное значение. В отличие от функции абсолютного значения, она никогда не приводит к переполнению. Если среди ко-

манд машины нет функции "nate", но есть более привычная команда "abs", то вместо nabs (ж)

можно использовать -abs(jc). Если х- максимальное отрицательное число, переполнение

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

Используемая ниже функция "nlz" возвращает количество ведущих нулевых битов аргумента. Описание функции doz (разность или ноль) приводится в разделе 2.18.

х=у: abs(jc-y)-l

abs(a;-у+ 0x80000000)

nlz(x-y)<K26

-(nlz(x-y)»5

-.{х-у\у-х) ХФу: nabs(jc-y)

nlz(x-y)-32

х-у\у-х х<у: {х-у)®[{х®у)&.{{х-у)®х)\

{х&у)\{{ху)&{х-у)) nabs(doz(y,Jc)) [24]

х<у: (жЬу)&((х®у)Ь(у-х))

х<у

х<у

[xsy)-»\ + Х&.-У

) \

(&у)((ху)&(х-у)) (&у)((у)&(х-у)) (у)&((хФу)Ь(у-х))

[24]

Для х>у, х>у и прочих отношений необходимо в соответствующих формулах поменять местами хиу. Команду сложения с 0x80000000 можно заменить любой другой командой, которая инвертирует значение старшего бита.

Другой класс формул основан на том, что предикат х<у вычисляется по знаку величины xjl-yjl, а вычисление данной разности не может привести к переполнению. В тех случаях, когда сдвиги приводят к потере информации, результат можно уточнить путем вычитания единицы.

х<у: х<у:

хз>1

X3>lj-

у»1

у»1

f&y&l

2.11. ПРЕДИКАТЫ СРАВНЕНИЯ