Первая страница » Статьи » Об арифметике

Немного об арифметике

Автор: Влад Князев
Редактор: Александр Бельченко
май-июнь 2004

Предисловие

Возможно, многих удивит моя крамольная мысль о том, что все компьютеры одинаковы, и нет принципиальной разницы между, скажем, Pentium и PIC. «Как это нет?!», — скажете Вы, — «ведь они совершенно различны! Их производительности отличаются на несколько порядков!» Да, в этом Вы будете совершенно правы. Но я имею в виду принципиальную разницу. Если задача в принципе разрешима с помощью компьютера, то абсолютно нет никакой разницы с помощью какого компьютера (контроллера) ее решать.

Мое такое утверждение будет справедливо только в том случае, если отсутствуют какие-либо ограничения на объем памяти компьютера и на время решения задачи. В самом деле, любую инструкцию Pentium можно рассматривать как некоторую программу для PIC (на самом деле примерно так и есть), и вообще, можно сделать программный эмулятор любого компьютера на любом другом компьютере (контроллере). Поэтому неважно, сколько времени будет выполняться программа с помощью эмулятора, и какая программная память для этого понадобится. Ведь ограничений то нет!

Но это возможно лишь теоретически — на практике такое просто невозможно себе представить. Никому не нужны программы, которые выполняются бесконечно долго и занимают бесконечно большую память. Поэтому, как только мы наложим какие-либо ограничения на скорость выполнения программы или размер памяти, так сразу появится разница между Pentium и PIC. И неизбежно возникнет вопрос, в чем причина этой разницы.

Процессоры, которые мы выбираем

Конечно, сравнивать Pentium и PIC между собой занятие бесполезное, уж слишком большая разница между ними. Давайте сравнивать архитектуры процессоров одной «весовой» категории, например, того же PIC и AVR, а также MCS-51. Сравнение даже близких по своим характеристикам процессоров тоже является занятием весьма хлопотным, и всесторонним, но, я думаю, в пользе такого сравнения вряд ли кто будет сомневаться. Хочу сразу сказать, что сейчас мы будем анализировать только одну их характеристику: их способность к арифметическим вычислениям. Пусть это будет еще одна «копейка» в копилке сравнительного анализа характеристик этих контроллеров.

В свое время, из чистого любопытства, я в телеконференции попросил показать коды, для сравниваемых контроллеров, полученные в результате трансляции простой Си-функции:

int max(int a, int b)
        {
        if (a >= b)
                return a;
        return b;
        }

Ответы были весьма любопытны. Прежде, чем их анализировать, я хотел бы обратить Ваше внимание именно на то, что в данном примере речь идет об обработке данных длиной 2 байта со знаком. И здесь, соответственно, возникают два вопроса: как обрабатываются числа со знаком и как обрабатываются 16-разрядные числа на 8-разрядном контроллере. Мы их будем рассматривать порознь.

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

Для начала пример для MCS51:

; if (a >= b) ; CLR C MOV A, R7 SUBB A, R5 MOV A, R4 XRL A, #080H MOV R0, A MOV A, R6 XRL A, #080H SUBB A, R0 JC ?C0001 . . . . . .

Теперь то же самое для PIC16:

movf ?_max+1,w xorlw 128 movwf btemp movf ?_max+3,w xorlw 128 subwf btemp,w btfss STATUS, Z goto u1545 movf ?_max+2,w subwf ?_max,w u1545: btfss STATUS, C goto L39 . . . . .

Ну и, наконец, для AVR:

CP R16, R18 CPC R17, R19 BRLT ?001 . . . . . .

Я намеренно оставляю эти коды без комментариев. Объяснением этого мы с Вами и займемся далее. Но чтобы разобраться в действительности как же работает компьютер с числами, мне кажется, нужно рассмотреть арифметику подробнее. Поэтому давайте немного отвлечемся от темы, и посмотрим, как мы сами работаем с числами. Знание обычной «человеческой» арифметики, я думаю, нам не помешает.

«Человеческая» арифметика и «машинная» арифметика

Для начала попробуйте решить пару простейших задач — сложные вычисления здесь не потребуются.

Вопрос первый: какое из чисел больше — 1 или 255? Я думаю, все, не задумываясь, скажут: конечно, 255 больше 1. Вопрос второй: какое число меньше — 1 или –1? И опять же, долго не думая, все скажут, что число –1 меньше 1. Но это справедливо лишь для нашей повседневной арифметики. Но справедливы ли наши ответы в случае компьютерной «машинной» арифметики?

Для простоты предположим, что у нас имеется простой 8-разрядный компьютер, и числа из нашего примера представляются 8-ю двоичными разрядами. Что получается в этом случае? А получается очень интересная картина. Для единообразия запишем три наших числа в шестнадцатеричном коде. При этом число 1 представляется в виде 0x01, число 255 — в виде 0xFF, и число –1 — в виде 0xFF(!). То есть получается, что –1 = 255. Те, кто не знает арифметики (компьютерной), могут не поверить и сказать, что такого быть не может. Другие, в ответ на это, могут справедливо возразить, что это вполне естественно, поскольку числа в компьютере представляются в дополнительном коде и код числа –1 будет равен 255 в десятичной системе счисления. Но как компьютер различает числа –1 и 255? Если сказать коротко — никак. А чтобы понять, откуда появляется различие, давайте продолжим наше исследование.

Вспомним, как мы с вами производим арифметические вычисления. Как правило, мы настолько часто их делаем, что порой не задумываемся, как именно мы это делаем. Я думаю, что сейчас наступил самый подходящий момент, чтобы задуматься.

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

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

Наконец, вспомним, как мы выполняем операции над числами со знаком. Во-первых, знак числа отображается при помощи символов «+» или «-», которые не являются цифрами. Они выбраны достаточно условно, искусственно. Сами операции мы выполняем над модулями чисел, а знак результата получается не автоматически, а по вполне определенным правилам.

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

Иное дело — компьютер и компьютерная арифметика. Здесь, на выполнение арифметических операций накладываются те ограничения и условия, которыми мы с вами не скованы в нашей обычной арифметике. Прежде всего, компьютер оперирует с числами фиксированной разрядности, и, независимо от разрядности чисел, возникает вероятность переполнения разрядной сетки, когда результат не может разместиться в заданном фиксированном количестве разрядов. И это событие (переполнение) должно фиксироваться, чтобы вычисления не стали ошибочными. Сама фиксация может быть выполнена или аппаратными средствами в АЛУ (арифметико-логическом устройстве), или программным путем.

Далее, в случае обработки чисел со знаком, необходимо выбирать такое представление знака числа, чтобы знак результата формировался автоматически. А это означает, что знак числа должен участвовать в операции наряду со значащими цифрами. С этой целью в современных компьютерах для представления чисел используется дополнительный код. В этом коде знак числа представляется в виде цифры в старшем разряде: 0 соответствует положительному числу, 1 — отрицательному. Естественно, что диапазон представимых чисел со знаком (точнее, их модулей) при фиксированной длине слова будет в два раза меньше.

Само понятие дополнительного кода означает, что два числа, одинаковые по модулю, но разные по знаку, дополняют друг друга до нуля. Формула для представления отрицательного числа в дополнительной двоичной форме выглядит так: ~(|x|) + 1 — инвертировать все разряды в модуле числа и прибавить к результату единицу.

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

Немного истории

В современных компьютерах используется представление чисел со знаком в дополнительном коде. Однако такое представление несколько затрудняет анализ результата на переполнение: для этого требуются дополнительные схемы в АЛУ. В настоящее время введение дополнительных схем не представляет трудностей и делается без проблем. Однако, в прошлом, когда элементную базу компьютеров составляли транзисторы (или даже электронные лампы!), введение дополнительных схем представляло определенные трудности.

Поэтому для упрощения схем фиксации переполнения использовался так называемый модифицированный дополнительный код. В этом коде знак числа представлялся не одним, а двумя знаковыми разрядами. При этом если в результате операции в знаковые разряды записывались одинаковые цифры (00 для положительных чисел, и 11 - для отрицательных), то результат операция считался корректным. Если же в результате знаковые разряды содержали разные цифры (01 или 10), то это говорило о том, что при выполнении операции возникло переполнение. Для фиксации переполнения было достаточно одной схемы «исключающее ИЛИ».

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

Детальный разбор ассемблерных листингов для 8-битных микроконтроллеров

Вернемся к нашему примеру. Обратите внимание на схожесть кодов у таких, казалось бы, совершенно разных по архитектуре процессоров, как MCS-51 и PIC16. Если не принимать во внимание места размещения аргументов, то и в первом и втором случаях мы видим использование операции XOR (XRL, xorlw), причем дважды. В обоих случаях используется операция

XOR     #128    ; 128 = 0x80

А что означает данная операция? Не более как инвертирование старшего знакового разряда. С другой стороны, в случае с AVR ничего подобного нет. Отчего же так? Чтобы ответить на этот вопрос, давайте рассмотрим подробнее регистры состояния программ для каждого из процессоров. Нас будут интересовать в данном случае только флажки признаков результата операции.

Итак, у MCS51 в регистре PSW мы имеем следующие флажки признаков:

C — флаг переноса;
AC — флаг вспомогательного переноса;
OV — флаг переполнения;
P — флаг четности.

У PIC16 в регистре STATUS мы можем увидеть:

C — флаг переноса;
DC — флаг вспомогательного переноса;
Z — флаг нулевого результата.

Ну, и у AVR в регистре SREG имеются флажки:

C — флаг переноса;
Z — флаг нулевого результата;
N — флаг отрицательного результата;
V — флаг переполнения;
S — флаг знака;
H — флаг вспомогательного переноса.

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

Хочется обратить особое внимание на наличие специального признака S у AVR. Согласно руководству по системе команд AVR, значение S всегда устанавливается равным значению операции N+V (по модулю 2 — опять исключающее ИЛИ!), и именно значение этого признака используется при сравнении чисел со знаком. Наличие этого признака у AVR как раз свидетельствует о том, что в AVR обеспечивается аппаратная поддержка вычислений со знаком.

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

Как я уже сказал, операция сравнения двух чисел в компьютере выполняется одинаково как для чисел со знаком, так и для чисел без знака. Образно говоря, процессор «не знает», какие числа он сравнивает, но в результате сравнения устанавливаются все флажки признаков, которые имеются у процессора. И только программист, используя команды переходов по соответствующим признакам, интерпретирует тем самым форму представления чисел. Поэтому, если говорить об аппаратной поддержке вычислений со знаком, то для этого процессор должен иметь соответствующие флажки признаков и, одновременно, команды условных переходов по этим признакам.

А если указанные необходимые средства отсутствуют?

Тогда корректное выполнение операций сравнения чисел со знаком должно выполняться программно. В этом случае анализ результата сравнения производится косвенным путем с использованием тех флажков, которые имеются у данного процессора. А для этого потребуется ряд дополнительных команд, что мы и видим в случае PIC или MCS-51. Хочу добавить, что когда я работал над компилятором для I8080 (Z80), у меня тоже возникла подобная проблема. Правда, я оформил процедуру сравнения чисел со знаком в виде служебной подпрограммы, вызов которой генерировался компилятором в соответствующих случаях. Это позволяло сэкономить память, но увеличивало время выполнения операции сравнения.

Наши рассуждения будут неполными, если мы не разберемся, как же все-таки выполняется операция сравнения чисел со знаком. Дело в том, что в AVR при формировании признака результата (S) учитываются как знаки исходных операндов, так и знак результата. Если взглянуть на инструкцию сравнения CP, то мы увидим: во-первых, данная инструкция просто выполняет операцию вычитания, без запоминания результата. Цель этой инструкции — установка флажков признаков. Во-вторых, можно увидеть, как именно устанавливаются эти признаки. И, в-третьих, посмотрев инструкции условных переходов, можно увидеть каким образом эти признаки используются.

Несколько соглашений о нотации. Договоримся, что логические операции мы будем записывать символами, используемыми в языке Си для аналогичных целей: ~ — операция «НЕ», ^ — операция «исключающее ИЛИ», | — операция «ИЛИ». Для операции «И» специального символа мы использовать не будем. Далее, обозначим операнды инструкции CP как R_D и R_S, и, наконец, старшие знаковые разряды операндов и результата — как D₇, S₇ и R₇ соответственно. При этом не будем забывать, что у положительного числа знаковый разряд равен 0, или, в нашей нотации — ~D₇, ~S₇ и ~R₇.

Используя принятые соглашения, мы можем записать саму инструкцию сравнения как

CP RD, RS

операцию, выполняемую по этой инструкции, как R_D – R_S. Далее, смотрим на флажки признаков. Хотя данная инструкция изменяет все флажки признаков, но нас будут в данном случае интересовать признаки V, N и S:

V = D₇ ~S₇ ~R₇ | ~D₇ S₇ R₇
N = R₇
S = V ^ N

Данные выражения можно интерпретировать следующим образом. Переполнение (V) возникает в тех случаях, кода из отрицательного числа вычитается положительное И результат вычитания является положительным, ИЛИ из положительного числа вычитается отрицательное И результат является также отрицательным. Естественно, что в нашей повседневной арифметике такого быть не может, но здесь арифметика машинная. Хочу также добавить, что правило установки флажка V определяется именно этой арифметикой, и не зависит от типа процессора.

Флажок знака N устанавливается в соответствии со знаком результата (в данном случае, результат фиктивный). Флажок S устанавливается, если переполнения нет И результат отрицательный ИЛИ есть переполнение И результат положительный. Наличие данного флажка у процессора необязательно и, хотя подобные флажки могут быть у многих процессоров, о них, как правило, просто не упоминают. Гораздо важнее знать, что из этого следует.

А чтобы понять, что именно из этого следует, нужно вновь обратиться к системе команд AVR и рассмотреть имеющиеся там инструкции условных переходов. Поскольку, в нашем примере условию ИСТИНА соответствует условие БОЛЬШЕ ИЛИ РАВНО (>=), то условию ЛОЖЬ (а переход будет выполняться именно по этому условию) будет соответствовать условие МЕНЬШЕ (<). Среди прочих инструкций условных переходов имеется соответствующая инструкция BRLT (BRanch if Less Than — переход, если меньше). То есть переход выполняется, если выполняется условие меньше со знаком. Признаком такого условия является установка флажка S в единицу, или, если записать это по-другому:

V ^ N = 1

В общем с AVR все ясно: есть специальные инструкции, есть специальные флажки — и нет проблем. А как же быть в случае PIC или MCS51?

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

С этой целью можно упростить выражение для признака условия «меньше чем» со знаком, т.е. значения флажка S. Поскольку у нас N = R₇, то выражение для S можно переписать в виде

S = V ^ N = V ^ R₇ = ~V R₇ | V ~R₇

Подставив в это выражение, исходное выражение для V и упростив полученное выражение, мы получим некоторую логическую функцию для S в более удобном для программной реализации виде:

S = ~S₇D₇ | ~S₇R₇ | R₇D₇ = ~S₇ (D₇ | R₇) | R₇D₇

Теперь мы, зная выражение для вычисления требуемого условия, можем легко составить программу для выполнения операции сравнения чисел со знаком. Нам потребуются инструкции логических операций «И», «ИЛИ» и «НЕ», которые имеются у любого процессора. Естественно, что в результате вычисления условия должен устанавливаться флажок признака, имеющийся у процессора, и для которого существует соответствующая инструкция условного перехода.

Я намеренно так подробно анализирую такой вариант реализации, казалось бы, простейшей операции, как говорится: «Шок — это по-нашему!». А если говорить серьезно, то достоинства короткого пути можно оценить, только полностью преодолев длинный путь. И мы его преодолели. Однако если Вы попытаетесь написать программу только на основе полученных выражений, то она наверняка получится намного более громоздкой, чем это сделано во фрагментах кодов, приведенных выше. И в чем же тут причина?

Причина здесь в том, что как раз и существует значительно более короткий путь. Если более внимательно рассмотреть и проанализировать фрагменты кодов, то можно легко его увидеть. В самом деле, вместо того чтобы анализировать знаки исходных операндов и результата, разработчики компиляторов применили искусный и, вместе с тем простой, прием. Они просто добавили к исходным операндам (точнее к их старшим байтам) смещение, равное 128. Или, если говорить о 16-разрядных операндах в целом - 32768. Ведь операция

XOR #128

которая, казалось бы, просто инвертирует знаковый разряд, на самом деле эквивалентна добавлению смещения величиной 128 (но без переноса). И использование команд XRL или xorlw для этой цели легко объяснимо, так как данные команды не меняют значения флага переноса. А этот флажок необходим для корректного вычитания 16-разрядных данных. Это можно легко проверить на двоичных кодах, но я не буду здесь этого делать. А в десятичной системе это выглядит очень просто. Если взять для примера те числа, которые мы уже брали ранее 1 и –1, то получим:

-1 + 128 = 127
и
 1 + 128 = 129

Если рассматривать их шестнадцатеричные представления, мы будем иметь числа 0x7F и 0x81 соответственно. Другими словами, прибавление к операндам смещения, переводит их в область положительных чисел. А дальше выполняется обыкновенное вычитание 16-разрядных чисел, но уже без учета знака, при этом для анализа результата сравнения достаточно одного флажка C. И здесь эта операция для PIC и MCS51 выполняется по-разному, хотя отличие несущественно.

В MCS51 вычитание выполняется, начиная с младших байтов, поскольку команда вычитания SBB учитывает значение признака переноса. В PIC16 команда subfw не учитывает признак переноса, поэтому вычитание выполняется, начиная со старших разрядов. А вычитание младших байтов, выполняется, только если разность старших байтов равна нулю, что требует дополнительной команды условного перехода по нулю. Справедливости ради, нужно сказать, что в MCS51 также требуется команда предварительного сброса признака переноса. Более детальный анализ всей функции в целом желающие могут провести сами, после трансляции данной функции соответствующим компилятором.

Хочу добавить, что и здесь процессор AVR стоит особняком, поскольку для выполнения подобных операций у него имеется специальная команда сравнения с переносом CPC, которая резко упрощает процедуру сравнения чисел с произвольным количеством байт. Но и сам AVR в этом смысле не является абсолютным исключением, так как такую команду можно обнаружить в системе команд, например, контроллера Z8+ фирмы Zilog.

Заключение

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

Конечно, я не был бы самим собой, если бы обошелся без очередных «нравоучений». И я — первый их слушатель. Прежде всего, глядя на результат трансляции даже простейшей функции, можно сделать вывод, что выбор контроллера (процессора) во многом определяется решаемой задачей. Это вроде бы очевидная и банальная мысль, но иногда ее осознают с большим трудом.

В данном случае, если говорить о задачах вычислительного характера, связанных с большим количеством вычислений, AVR имеет из трех сравниваемых контроллеров очевидные преимущества. И если Вам придется решать подобные задачи, то, может быть, имеет смысл рассмотреть его в качестве первой кандидатуры для выбора. Если же он по ряду причин не подойдет, и Вы остановите свой выбор либо на семействе PIC, либо на семействе MCS51, то тогда надо быть готовым к потере производительности процессора при наличии в программе большого количества вычислений.

Отсюда вытекает следующее «нравоучение»: следует по возможности выбирать такое представление данных, которое является наиболее естественным для выбранного контроллера. Эта тоже вполне очевидно, и я мог бы не обращать на это Вашего внимания, если бы все всегда следовали этому правилу. Но часто это происходит с точностью до наоборот.

Если программисты, использующие ассемблер, следуют этому правилу чисто интуитивно (кому хочется писать лишние инструкции, не имея на то особой необходимости), то программисты Си не всегда обращают на это внимание. Здесь их поведение часто диаметрально противоположное. Действительно, чтобы определить данные типа int потребуется гораздо меньше усилий, чем для определения данных типа unsigned, и уж, тем более, меньше, чем для определения данных типа unsigned char. В результате возрастает размер программы и падает производительность процессора. Особенно часто это делают программисты на стадии освоения языка. И увидев такой результат, их энтузиазм в отношении языка тоже сразу падает.

Исходя из собственного опыта, я сделал для себя парадоксальный, на первый взгляд, вывод: чем подробнее и детальнее (а значит длиннее) исходный текст — тем короче сгенерированный код. И то, о чем я сказал в предыдущем абзаце, лишнее доказательство сделанного вывода. А чтобы убедиться в этом, достаточно проанализировать генерируемый для различных конструкций языка код. Уверяю Вас, сделав это, Вы найдете для себя немало полезного и поучительного. Все познается в сравнении. Эта мысль была высказана еще в глубокой древности, но она абсолютно верна и в наше время.

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

On Embedding