Не будем больше задерживаться на этой теме; заметим только, что определение наличия переполнения может основываться на значении nlz(abs(jc)) + nlz(abs(y)), но н при этом возможны неоднозначные случаи, когда значение данного выражения равно 31 или 32.

Деление

При знаковом делении ж + у переполнение возникает, если истинно выражение

у = ОI (д; = 0x80000000 & у =-1).

Большинство компьютеров сообщают о переполнении (или генерируют прерывание) при возникновении неопределенности типа 00.

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

abs(y Ф 0x80000000) I (abs(x) & 3bs(y = 0x80000000))] < О

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

Еще один метод предполагает первоначальное вычисление значения

г <-(ж Ф 0x80000000) I (у +1)

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

{(y\-y)&(z\-z))>0 (nabs(y)&nabs(z))>0

(nlz(y)nlz(z))»5

Вычисление этих выражений может быть реализовано за девять, семь и восемь команд соответственно (при наличии всех необходимых для вычисления команд). Для PowerPC наиболее эффективным оказывается последний из перечисленных методов.

При беззнаковом делении переполнение возникает тогда и только тогда, когда у = О.

2.13. Флаги условий после сложения, вычитания и умножения

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

• был ли перенос или нет (беззнаковое переполнение);

• было или нет знаковое переполнение;

• является ли полученный 32-битовый результат, интергфетируемый как знаковое целое число в дополнительном коде без учета переноса и переполнения, отрицательным, положительным или нулевым.

2.13. ФЛАШ УСЛОВИЙ ПОСЛЕ СЛОЖЕНИЯ, ВЫЧИТАНИЯ И УМНОЖЕНИЯ 45

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

При сложении возможны только 9 из 12 комбинаций этих трех событий. Невозможны следующие три комбинации: "нет переноса, переполнение, результат > О", "нет переноса, переполнение, результат = О" и "перенос, переполнение, результат < О". Таким образом, для флагов условий требуется четыре бита. Две из комбинаций флагов уникальны в том смысле, что могут произойти только при единственном значении исходных аргументов: комбинация "нет переноса, нет переполнения, результат = О" возникает только при сложении О с 0; комбинация "перенос, переполнение, результат = О" возникает только при сложении двух максимальных отрицательных чисел. Эти замечания справедливы и при наличии "входного переноса", т.е. при вычислении х+у+1.

В случае вычитания полагаем, что для вычисления разности х-у компьютер вычисляет сумму лг + У+1 с переносом, который образуется так же, как и при сложении (понятие "перенос" при вычитании трактуется наоборот: леренос, равный 1, означает, что результат помещается в одно слово, а перенос, равный О, означает, что результат в одно слово не помещается). Следовательно, при вычитании могут произойти только семь из всех возможных комбинаций событий. Невозможны те же три комбинации, что и при сложении, а кроме того, еще две комбинации: "нет переноса, нет переполнения, результат = О" и "перенос, переполнение, результат = О".

Если умножение на компьютере может давать произведение двойной длины, то желательно иметь две команды умножения: одну для знаковых операндов, а другую - для беззнаковых. (На 4-разрядной машине в результате умножения знаковых операндов произведение FxF = 01, а в случае перемножения беззнаковых операндов - FxF = El (в шестнадцатерич-ной записи)). Ни переноса, ни переполнения при выполнении этих команд умножения не возникает, так как результат умножения всегда может разместиться в двойном слове.

Если же произведение дает в результате одно (младшее) слово, то в случае, когда операнды и результат интерпретируются как целые беззнаковые числа, перенос означает, что результат не помещается в одно слово. Если же операнды и результат интерпретируются как знаковые целые числа в дополнительном коде, то, если результат не помещается в слово, устанавливается флаг переполнения. Таким образом, при умножении возможны только девять комбинаций событий. Невозможны комбинации "нет переноса, переполнение, результат > О", "нет переноса, переполнение, результат = О" и "перенос, нет переполнения, результат = О". Таким образом, при рассмотрении сложения, вычитания и умножения получаем, что реально могут встретиться только 10 комбинаций флагов условий из 12 возможных.

2.14. Циклический сдвиг

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

Циклический сдвиг влево на и разрядов: у<- *«« х»{32-п)\

\ J к )

Циклический сдвиг вправо на и разрядов: у <- хз>яj х<*:(32- b)J 46 ГЛАВА 2. ОСНОВЫ

2.15. Сложение/вычитание двойных слов

Взяв за основу любое из приведенных в подразделе "Беззнаковое сложение/вычитание" раздела 2.12 выражение для переполнения при беззнаковом сложении и вычитании, можно легко реализовать сложение и вычитание двойных слов, не используя при этом значение бита переноса. Пусть (z,,Zo) -результат сложения операндов (jc„jCo) и (урУо). Индекс 1 обозначает стшее полуслово, а индекс О - младшее. Считаем также, что при сложении используются все 32 бита регистров. Младшие слова интерпретируются как беззнаковые величины. Тогда

- "

(ж„&Уо)((ХоУо)&о)>31

Z, <-JC.+y,+c.

Всего для вычисления потребуется девять команд. Во второй строке можно исполь-

, допускающее получение конечного результата за четыре

зовать выражение с <-Zo<x,

команды на машинах, в наборе команд которых имеется оператор сравнения в форме, помещающей результат (О или 1) в регистр, как, например, команда SLTU {Set on Less Then Unsigned - беззнаковая проверка "меньше, чем") в MIPS [46].

Аналогичный код используется для вычисления разности двойных слов.

»31

(о&Уо)((Жо=Уо)&го)

z,<-Jc,-J,-ft

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

полнить восемь команд. Если вторую строку записать как b«

, ТО на машинах.

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

На большинстве машин сложение и вычитание двойных слов реализуется за пять команд, посредством представления данных в младшем слове с помощью 31 бита (старший бит всегда равен О, за исключением временного хранения в нем бита переноса или заема).

2.16. Сдвиг двойного слова

Пусть (jc,,JCo) - два 32-разрядных слова, которые требуется сдвинуть вправо или влево как единое 64-разрядное слово, в котором Х\ представляет старшее полуслово, и пусть (УрУо) представляет собой аналогично интерпретируемый результат сдвига. Будем считать, что величина сдвига и может принимать любые значения от О до 63. Предположим также, что машина может выполнять команду сдвига по модулю 64 или большему. Это означает, что если величина сдвига лежит в диапазоне от 32 до 63 или от -32 до -1, то в результате сдвига получится слово, состоящее из одних нулевых битов. Исключением является команда знакового сдвига вправо, так как в этом случае 32 разряда результата будут заполнены значением знакового разряда слова. (Рассматриваемый алгоритм не работает на процессорах Intel х86, сдвиг в которых вьшолняется по модулю 32.)