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

у, <-JC,« и I »(32 - и) I jc„«(и - 32)

>о Jfo « «

Чтобы при и=32 получился корректный результат, в первом присваивании должна обязательно использоваться команда или, а не плюс. Если известно, что О S и S 32, то последний член в первом выражении можно опустить, тем самым реализуя сдвиг двойного слова за шесть команд.

Аналогично, беззнаковый сдвиг двойного слова вправо можно вычислить так:

Уо <-JCo»« «(32 - и) IJC, »(и - 32)

у, <-ж,»и

Знаковый сдвиг двойного слова вправо реализовать сложнее из-за нежелательного распространения знакового разряда в одном из членов. Вот как выглядит простейший код для вычисления этой операции:

if и < 32

thenyo «-jCo3>n(jc,«(32-n) else Уо <-jc,»(n-32) у, <- jc,»n

Если в компьютере есть команда условной пересылки {conditional move), то код реализуется за восемь команд без переходов. Если же команды условной пересылки нет, то понадобится выполнить десять команд, с созданием маски для устранения нежелательного распространения знака в одном из членов.

Уо<-лГо»иж,« у, <-ж,з>и

32-и

Гд;,»(и-32)1&Г(32-и)з>31

2.17. Сложение, вычитание и абсолютное значение многобайтовых величин

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

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

1. Замаскировать старший бит в каждом байте операнда и выполнить сложение (избежав таким образом переносов через границы байтов).

2. Учесть старшие биты каждого байта, т.е. выполнить сложение старших битов операндов (и при необходимости перенос в этот бит).

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

Сложение: s*-{x& 0X7F7F7F7F) + (у & Ox7F7F7F7F) S <- ((д; Ф у) & 0x80808080) ® s

Вычитание: d*-(x\ 0x80808080) - (у & Ox7F7F7F7F) d*-{(x®y)\ 0X7F7F7F7F)

На компьютере, оснащенном полным набором логических команд, реализация описанных выше вычислений потребует выполнения восьми команд (с учетом загрузки числа 0x7F7F7F7F). (В приведенных формулах команды и и или с числом 0x80808080 можио заменить соответственно командами и-не и или-не с числом 0x7F7F7F7F.)

Существует и другая методика для случая, когда слово состоит из двух полей. Сложение при этом можно реализовать посредством прибавления 32-битовых чисел с последующим вычитанием нежелательного переноса из полученной суммы. Ранее уже отмечалось, что выражение {х + у)®х®у дает переносы в каждом разряде. Использование

этой и аналогичной формулы для вычитания дает нам приведенный ниже код для сложения/вычитания двух полуслов по модулю 2** (реализуется семью командами).

Сложение: Вычитание:

s<r-x + y dix-y

с«-($ФхФу)&0х00010000 6«-(</ФхФу)&Ох00010000

s*-s-c d*-d+b

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

я «- X & 0x80808080 Выделяем биты знаков

6 <- я » 7 Целое число, равное 1, если х отрицательно

»1«-(я-6)я OxFF для отрицательногоX

у <- (X Ф m)+* Дополнение и прибавление 1 для отрицательных чисел

Вместо третьей формулы можно использовать т *-а+а-Ь. Прибавление b в четвертой строке не может вызвать переноса через границу байта, так как в каждом байте значение старшего бита х Фт равно 0.

2.18. Функции Doz, Max, Min

Функция doz для знаковых Ефгументов определяется следующим образом:

doz(jf,y) =

х-у, ху, . о, х<у.

функцию doz называют также "вычитанием в первом классе", так как, если вычитаемо( больше уменьшаемого, результат равен 0. Эху функцию удобно использовать при вычисленш двух других функций- тах(лг,у) и min (лг, у). В смзи с этим следует отметил., что функци? doz(jc,y) может быть и отрицательной, если при вычислении разности произошло переполнение. В Fortran эта функция используется в реализации функции IDIM, хотя в этом языке программирования при возникновении переполнения результат считается неопределенным.

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

d<r-x-y

dQz{x,y)=d& (ds((x®y)&(d®i:)))»31

niax(*,y) = y+doz(*,y) min (дг, у) = д; - doz (JC, у)

Вычислить функцию doz(jc,y) можно за семь команд, если в наборе имеется команда

эквивалентности, или за восемь команд в противном случае. Для вычисления функций max и min необходимо выполнить еще одну команду.

В случае беззнаковых гументов используем беззнаковые версии указанных функций.

d *-х-у

dozu(*,y)=d&-, ((-*&y)((x = y)&d))»31

шахи(дс,у) = у+ dozu{jf,y) min (дг, у) = дг - dozu (JC, у)

В компьютере ШМ RISC/6000 (и его предшественнике 801) есть отдельная команда для вычисления функтши doz(jf,y), так что на этих машинах функции тах(дг,у) и min(jc,y) с целыми знаковыми аргументами вычисляются за две команды, что весьма эффективно (непосредственная реализация этих функций требует больших затрат).

На машинах, имеющих команду условной пересылки, возможна двухкомандная реализация деструктивных функций max и min. Например, при использовании нашего RISC-компьютера с расширенным набором команд выражение jc<-max(jf,y) можно вычислить следующим образом:

cmplt 2, X, у ; Установить z = 1, если х < у, иначе z = О movne X, Z, у ; Если z не равен О, то присвоить х = у

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