Команды сдвига

Команды сдвига предназначены для сдвига (изменения индексов) битов в своём операнде. Операнд при этом можно рассматривать как битовый вектор, элементы которого пронумерованы от 0 до N так же, как и для рассмотренных выше логических команд. Команды сдвига имеют формат

КОП op1,op2

где op1 может быть r8,m8,r16 или m16, а op2 – иметь значение единицы или быть коротким регистром cl.[40] Мы рассмотрим сначала команды сдвига вида КОП op1,1, а затем обобщим их на случай команд вида КОП op1,cl.

Команда сдвига операнда на один бит влево имеет показанный ниже вид

shl op1,1

и её выполнение можно так описать в виде цикла на Паскале:

CF:=op1[N]; for i:=N downto 1 do op1[i]:=op1[i-1]; op1[0]:=0

Как видим, при сдвиге битового вектора на одну позицию влево самый левый бит не теряется, а попадает во флаг переноса CF, а на освободившееся справа место записывается нулевой бит. Все команды сдвига устанавливают флаги по значению результата по тем же правилам, что и команды сложения и вычитания. Например, флагу – признаку отрицательного результата SF приваивается самый левый бит результата, т.е. SF:=op1[N]. Однако среди флагов, изменяемых командами сдвигов, в практическом программировании имеет смысл рассматривать только флаг переноса CF и флаг нуля ZF (он устанавливается в единицу, если, как обычно, получается полностью нулевой вектор-результат).

Команда сдвига влево часто называется логическим сдвигом влево, у кода операции этой команды есть синоним sal, который называется арифметическим сдвигом влево. Логический и арифмети­ческий сдвиги выполняются одинаково, а различие в их названиях будет понятно из дальнейшего изложения.

В том случае, если мы будем трактовать операнд команды сдвига влево на один бит как целое число, то результатом сдвига является умножение этого числа на два. При этом результат умножения получается правильным, если во флаг переноса CF попадает незначащий бит результата. Таким обра­зом, для беззнакового числа при правильном умножении на 2 должно быть CF=0, а для знакового опе­ранда результат получается правильным только тогда, когда значение флага переноса совпадает со знаковым (крайним слева) битом результата, т.е. после выполнения команды сдвига справедливо равенство CF=op1[N].

Рассмотрим теперь команды сдвига на один разряд вправо. По аналогии со сдвигом на один разряд влево, сдвиг на один разряд вправо можно трактовать как деление целого числа на два. Однако, так как деление на два должно выполняться по разным правилам для знаковых и беззнаковых целых чисел (вспомним различные команды div и idiv), то существуют две разные команды сдвига операнда на один бит вправо. Команда логического сдвига на один разряд вправо

shr op1,1

выполняется по правилу:

CF:=op1[0]; for i:=0 to N-1 do op1[i]:=op1[i+1]; op1[N]:=0

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

sar op1,1

она выполняется по правилу:

CF:=op1[0]; for i:=0 to N-1 do op1[i]:=op1[i+1]

Как видим, крайний левый бит аргумента при арифметическом сдвиге вправо не меняется. Особым здесь является случай, когда операнд равен минус единице, тогда операция деления этого операнда на два не эквивалентна операции арифметического сдвига вправо на один бит. Легко прове­рить, что (-1) div 2 = 0, а результат арифметического сдвига вправо операнда со значением –1 снова даёт -1 (т.е. sar -1,1 = -1).

Заметим далее, что, как и "настоящие" команды деления, сдвиг вправо даёт два результата: частное на месте своего операнда и остаток от деления на 2 во флаге CF. Действительно, легко видеть, что

CF:=op1 mod 2 для беззнакового операнда и

CF:= abs (op1 mod 2) для знакового операнда.

Таким образом, для проверки того, является ли целое число X нечётным, можно использовать следующие две команды

shl X,1

jc ODD; Нечётное X

Программисты, однако, не любят этот способ проверки на нечётность, так как при этом портится операнд X. Лучше проверять целое число X на нечётность двумя командами

test X,1

jne ODD; Нечётное X

Следующая группа команд сдвига – так называемые циклические сдвиги. Эти команды рассматривают свой операнд как замкнутый в кольцо: после бита с номером N располагается бит с номером 0, а перед битом с номером 0 – бит с номером N. Ясно, что при циклическом сдвиге операнд сохраняет все свои биты, меняются только номера этих битов. Команда циклического сдвига влево

rol op1,1

выполняется по правилу

shl op1,1; op1[0]:=CF

Команда циклического сдвига вправо

ror op1,1

выполняется по правилу

shr op1,1; op1[N]:=CF

Команда циклического сдвига через флаг переноса включают в кольцо сдвигаемых битов дополнительный бит – флаг переноса CF, который включается между битами с номерами 0 и N. Таким образом, в сдвиге участвуют N+1 бит. Команда циклического сдвига влево через флаг переноса

rcl op1,1

выполняется по правилу

t:=CF; rol op1,1; op1[0]:=t

Здесь t – некоторая вспомогательная (врéменная) переменная.

Команда циклического сдвига вправо через флаг переноса

rcr op1,1

выполняется по правилу

t:=CF; ror op1,1; op1[N]:=t

Команды циклического сдвига в практике программирования используются редко – когда надо проанализировать биты операнда и в операнде можно изменять порядок этих битов.

Теперь нам осталось описать команды сдвига, вторым операндом которых служит регистр cl. Каждая такая команда (КОП – любой из кодов операций сдвигов)

КОП op1,cl

Выполняется по правилу

for cl:=cl downto 1 do КОП op1,1; cl:=0

Таким образом, значение регистра cl задаёт число разрядов, на которые в цикле происходит сдвиг операнда, после цикла, как обычно, счётчик цикла (в данном случае регистр cl) обнуляется. Ясно, что задавать сдвиги более чем на N разрядов не имеет большого смысла.

Главное назначение логических команд – обрабатывать отдельные биты и группы битов в байтах и словах. Разберём несколько примеров использования логических команд в программировании на Ассемблере. Сначала составим фрагмент программы, в котором подсчитывается и выводится число битов со значением "1" во внутреннем машинном представлении переменной X размером в слово:

X dw?

...

inint X

mov ax,X

sub cx,cx; число "1"

L: cmp ax,0

jz Pech

shl ax,1

adc cx,0; cx:=cx+CF

jmp L

Pech: outint cx

Заметим, что операция подсчёта числа битов машинного слова со значением "1" является весьма важной в архитектуре некоторых ЭВМ. В качестве примера рассмотрим отечественную ЭВМ третьего поколения БЭСМ‑6, которая производилась в 70-х годах прошлого века [3]. В этой ЭВМ сигналы прерывания устанавливали в "1" биты в специальном 48-разрядном регистре прерываний (каждый бит соответствовал своему типу прерывания). В этой архитектуре существовала специальная машинная команда для подсчёта количества "1" в своём аргументе, что позволяло быстро определить число ещё необработанных сигналов прерывания.

Рассмотрим теперь использование логических команд при обработке упакованных структур данных. Пусть, например, на языке Паскаль дано описание упакованного массива с элементами ограниченного целого типа:

Const N=10000;

Var A: packed array [0..N] of 0..15;

X: byte;

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

Рассмотрим фрагмент программы на Ассемблере, который работает с описанным выше упакованным массивом A. Реализуем, например, оператор присваивания X:=A[i]. Каждый элемент массива требует для своего хранения 4 бита памяти, так что будем в одном байте хранить два последовательных элемента массива A:

N equ 10000

Data segment

A db N/2 dup (?); N/2 º N div 2

X db?

...

Data ends

...

mov bx,i

xor ax,ax; ax:=0

shr bx,1

mov al,A[bx]; в al два элемента

jc L1; i-ый элемент – правый

mov cl,4; число сдвигов

shr al,cl

L1: and al,1111b; выделение A[i]

mov X,al

Сначала мы разделили индекс i на 2 и определили тот байт массива A, в котором находится пара элементов, один из которых нам нужен. На положение нужного нам элемента в байте указывает остаток от деления индекса i на 2: если остаток равен нулю (т.е. i чётное), то элемент расположен в левых четырёх битах байта, иначе – в правых. Для выделения нужного элемента, который занимает в байте только 4 бита из 8, мы использовали команду логического умножения and al,1111b, где второй операнд задан для удобства понимания смысла команды в виде двоичного числа, на что указывает буква b в конце этого числа.

Использование команды логического умножения для выделения нужной нам части байта или слова, и обнуление остальной части является типичной для программирования на Ассемблере. При этом константа, используемая для выделения нужной части (у нас это 00001111b), называ ется маской выделения или просто маской. Таким образом, мы поместили элемент массива X, который занимает 4 бита, в регистр al и дополнили этот элемент до 8 бит нулями слева. Заметим, что это не изменило величины нашего элемента, так как он беззнаковый (0..15).

Наш простой пример показывает, что при работе с упакованными данными скорость доступа к ним уменьшается в несколько раз и программист должен решить, стоит ли это достигнутой нами экономии памяти (в нашем примере мы сэкономили 5000 байт оперативной памяти). Обычно это типичная ситуация в программировании: выигрывая в скорости обработки данных, мы проигрываем в объёме памяти для хранения этих данных, и наоборот. Иногда, по аналогии с физикой, это называют "законом рычага", который гласит, что, выигрывая в силе, мы проигрываем в длине перемещения конца рычага, и наоборот.

Упражнение. Реализуйте для нашего примера оператор присваивания A[i]:=X.

В качестве последнего примера использования логических команд рассмотрим реализацию на Ассемблере некоторых операций языка Паскаль над множествами. Пусть на Паскале есть описания двух символьных множеств X и Y, а также символьной переменной Sym:

Var X,Y: set of char; Sym: char;

Напишем на Ассемблере фрагмент программы для реализации операции объединения двух множеств:

X:= X + Y;

Каждое такое множество будем хранить в памяти в виде 256 последовательных битов, т.е. 32 байт или 16 слов. Бит, расположенный в позиции I принимает значение 1, если символ с номером I присутствует во множестве, иначе этот бит имеет значение 0. Множества X и Y можно так описать на Ассемблере:

Data Segment

...

X dw 16 dup (?)

Y dw 16 dup (?)

...

Data ends

Тогда операцию объединения двух множеств можно реализовать, например, таким фрагментом на Ассемблере:

mov cx,16

xor bx,bx

L: mov ax,Y[bx]

or X[bx],ax

add bx,2

loop L

В заключение рассмотрим условный оператор языка Паскаля, включающий операцию отношения in (символ Sym входит во множество X):

if Sym in X then goto L;

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

...

X db 32 dup (?); 32*8=256 битов

Sym db?

...

mov al,Sym

mov cl,3

shr al,cl

xor bx,bx

mov bl,al; Индекс нужного байта в X

mov al,X[bx]; Байт с символом Sym

mov cl,Sym

and cl,111b; Позиция символа Sym в байте

shl al,cl; наш бит в al – крайний слева

shl al,1; Нужный бит в CF

jc L

Сначала, используя команду сдвига на 3 (это, как мы знаем, аналогично делению на 8), на регистр bx заносим индекс того байта в X, в котором находится бит, соответствующий символу Sym в множестве X. Затем этот байт выбирается на регистр al, а на регистр cl помещаем три последних бита номера символа Sym в алфавите – это и будет номер нужного нам бита в выбранном байте (правда, биты при этом нумеруем слева направо, начиная с нуля). После этого первой командой сдвига перемещаем нужный нам бит в крайнюю левую позицию в байте, а следующей командой сдвига – во флаг переноса. Теперь осталось только сделать условный переход по значению этого флага.

На этом мы закончим рассмотрение логических команд.