Андрианов. И.А. Методические указания к практическим работам

Подождите немного. Документ загружается.

и компиляции его в объектный файл, код из которого присоединяется к ис-

полняемому файлу на этапе компоновки. Здесь нужно учитывать некоторые

моменты.

Во-первых, язык C++ поддерживается возможностью создания несколь-

ких функций с одинаковыми именами, но с разным количеством и типами

аргументами (перегрузка функций – изучалась в курсе «программирование на

языке высокого уровня»). При этом к имени функции в объектном файле до-

писываются специальные символы, обозначающие типы аргументов (это на-

зывается декорирование имен). Чтобы отключить декорирование имён, нуж-

но объявлять прототип функции в C++ с помощью директивы extern “C”.

Во-вторых, C++ при создании объектного файла в начало всех идентифи-

каторов добавляет знак подчеркивания. Также необходимо учитывать поря-

док расположения параметров в стеке при вызове функций и порядок их ос-

вобождения. Чтобы всё это выполнялось автоматически, достаточно в дирек-

тиве .model указать спецификатор языка C.

В качестве примера приведём ту же функцию, что и в примере выше, но

уже написанную целиком на ассемблере в отдельном модуле, а также текст

программы на C++, откуда она вызывается.

Файл myfunc.asm:

.486

.model flat, c

.code

;функция разворачивает биты в байте

;входной байт - в стеке, результат будет в al

turn PROC b:BYTE

mov bl,b ;помещаем исходный байт в bl

mov eax,0 ;а здесь будет результат

mov ecx,8 ;цикл будет на 8 итераций

L1:

shr bl, 1 ;выдвигаем младший бит в CF

rcl al, 1 ;задвигаем бит из CF в bl

loop L1

ret

turn ENDP

end

Обратите внимание – здесь в последнем end не пишется имя точки входа, так

как точкой входа будет функция main в C++.

Файл bturn.cpp:

#include <iostream>

using namespace std;

extern "C" unsigned char turn (unsigned char c);

int main(){

unsigned int i;

cin >> i;

i = turn(i);

cout << i <<endl;

return 0;

}

Если проект C++ создан с настройками по умолчанию, то при компонов-

ке, скорее всего, возникнет ошибка – не найдена функция myfuncs. Для её

устранения нужно указать объектный файл в настройках компоновщика (в

Visual C++ это делается через меню Project – Properties – Linker – Command

Line, где в Additional Options нужно написать имя файла myfuncs.obj). Аль-

тернативный вариант – добавить файл myfuncs.asm в проект (но тогда, воз-

можно, придётся настраивать поддержку ассемблера в Visual Studio). В дру-

гих средах разработки можно также найти аналогичные настройки.

Контрольные вопросы и задания

1. Если в C++ не отключено декорирование имён, то какое имя будет поме-

щено в объектный файл для функции int func(int x, double y) ?

2. В ассемблерных вставках нельзя использовать директиву OFFSET. А как

ещё можно загрузить в регистр адрес переменной?

3. Каким образом процедура на ассемблере должна возвращать значение,

чтобы из C++ её можно было вызывать как функцию?

4. Пусть в ассемблерном модуле стоит директива .model flat, stdcall, и вы не хо-

тите её изменять. Каким образом вызывать процедуры этого модуля из C++?

5. Каким образом в используемом вами компиляторе C++ сгенерировать ас-

семблерный листинг результата компиляции программы?

6. Предложите несколько способов, которые можно использовать при опти-

мизации кода с целью ускорения его работы.

Задания по программированию

1. Решите на языке С++ задачу №37 из проверяющей системы (в ней тре-

буется подсчитать количество простых чисел в диапазоне от 1 до n, где n не

превышает 10 млн.) Ввод и вывод сделайте средствами C++, а само вычисле-

ние простых чисел выполните с помощью ассемблерной вставки. В качестве

алгоритма рекомендуется использовать решето Эратосфена (изучалось в кур-

се «структуры и алгоритмы обработки данных»). Постарайтесь максималь-

но эффективно реализовать данный участок кода.

2. Можно не только вызывать ассемблерные процедуры из языка высоко-

го уровня, но и наоборот. В данной задаче вам предлагается запрограммиро-

вать такой пример.

Напишите ассемблерный модуль, содержащий процедуру BubbleSort для

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

этой процедуре должен передаваться адрес массива, количество элементов в

нём и адрес функции сравнения пар элементов.

Затем напишите на языке C++ функцию сравнения CmpFunc, которой пе-

редаётся два целых числа и она возвращает -1, если первое число меньше

второго, 0, если они равны, и +1, если первое число больше второго.

В функции main заполните массив случайными числами и вызовите про-

цедуру BubbleSort, передав ей адрес массива, число элементов и адрес функ-

ции CmpFunc. Отсортированный массив выведите на консоль.

Практическая работа 7. Представление вещественных чисел

в памяти ЭВМ, работа с математическим сопроцессором

Краткие теоретические сведения и примеры

1. Перевод в двоичную систему и обратно. Как и целые, вещественные

числа в памяти ЭВМ хранятся также в двоичной системе. Например, число

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

сти машинного представления, рассмотрим перевод вещественных чисел в

двоичную систему и обратно.

Целую часть числа мы переводить умеем (см. практ. работу 1), поэтому

будем рассматривать лишь дробную часть. Проще всего перевести из двоич-

ной системы в десятичную – нужно сложить те степени двойки, для которых

в дробной части числа стоит единица. Например, 0.01001 = 2

-2

-5

=0.28125

Для перевода из десятичной системы в двоичную рассмотрим два спосо-

ба. Первый вариант – перебирать по очереди степени двойки - 2

-1

, 2

-2

, 2

-3

т.д. Каждую такую степень сравниваем с нашим числом. Если она больще, в

ответ пишем ноль. Если меньше или равна, в ответ пишем 1 и вычитаем из

нашего числа.

Для примера выполним перевод 0.59375. Вначале пробуем степень

-1

=0.5. Она не превышает числа, поэтому в ответ пишем 1 и вычитаем – ос-

таётся 0.59375-0.5 = 0.09375. Теперь пробуем 2

-2

=0.25 – она больше 0.09375,

поэтому в ответ просто пишем ноль. Следующая степень 2

-3

=0,125 получи-

лась снова больше нашего числа - в ответ снова идёт ноль. Далее пробуем

-4

=0.0625 – она подходит, в ответ идёт 1, после вычитания остаётся 0,03125.

Наконец, следующая степень 2

-5

равна как раз 0,03125, поэтому в ответ идёт

1 и вычисление завершено. Ответ - 0.10011.

Примечание. Заметим, что многие числа, которые в виде десятичной

дроби имеют конечную длину, в двоичной системе конечным числом цифр

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

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

просто ограничиваются некоторым количеством цифр в зависимости от

того, какая точность нам требуется или сколько битов используется в ма-

шинном представлении.

Если при переводе в двоичную систему получается число бесконечной

длины, и мы хотим найти период повторения цифр в дробной части, то мож-

но использовать второй способ перевода [2]. Исходное число записывается в

виде простой дроби, числитель и знаменатель переводятся в двоичную сис-

тему и выполняется деление столбиком. Если в процессе деления получим

делимое, которое уже встречалось ранее, то период найден.

Для примера возьмём число 0.3. Его простая дробь выглядит как 3/10 или

в двоичной системе как 11/1010. Производим деление столбиком:

11|1010

---------

0.01001

_1100

1010

_10000

1010

1100

Видим, что делимое 1100 повторилось – значит, дальше в ответе цифры

тоже начнут повторяться. Период получился равным 1001, итоговое число

можно записать как 0.0(1001), где период обозначается круглыми скобками.

Примечание. Возможно, в 21-м веке уже не все студенты помнят, как

выполняется деление в столбик (в связи с повсеместным использованием

калькуляторов и компьютеров). Данный материал выходит за рамки мето-

дических указаний, но его легко найти в сети Internet.

Одно и то же вещественное число можно записать по-разному. Например,

15.73 = 1.573*10 = 0.1573*10

= 1573*10

-2

. Вариант записи, в которой перед

десятичной точкой стоит ровно одна ненулевая цифра, называется нормали-

зованным представлением, а его получение – нормализацией. Для числа

15.73 нормализованным представлением будет 1.573 * 10

, где 1.573 – ман-

тисса, 1 – показатель степени (иногда еще его называют порядок).

Для двоичных чисел нормализация выполняется аналогично – например,

число 1011.01101 после нормализации выглядит как 1.01101101 * 2

. В памя-

ти ЭВМ вещественные числа хранятся в основном в нормализованном виде

(за некоторым исключением).

2. Представление в памяти ЭВМ. Рассмотрим теперь представление ве-

щественных чисел в памяти ЭВМ [2]. В стандарте IEEE 754-1985 описаны 3

формата, их описание приведено в таблице 3.

Таблица 3

Форматы вещественных чисел

Формат

Описание

С одинарной точностью

(в masm - REAL4, в С++ -

float)

Длина 32 бита, из них слева направо: 1 бит – знак,

8 битов – показатель степени, 23 бита – дробная

часть мантиссы. Диапазон примерно от 2

-126

до

127

(и отрицательные)

С двойной точностью (в

masm - REAL8, в C++ -

double)

Длина 64 бита, из них слева направо: 1 бит – знак,

11 битов – показатель степени, 52 бита – дробная

часть мантиссы. Диапазон примерно от 2

-1022

до

1023

(и отрицательные)

Расширенное с двойной

точностью (в masm -

REAL10, в C++ - long

double)

Длина 80 бит, из них слева направо: 1 бит – знак,

16 битов – показатель степени, 63 бита – дробная

часть мантиссы. Диапазон примерно от 2

-16382

до

16383

(и отрицательные)

Рассмотрим отдельно каждую часть представления числа. Бит знака равен

1, если число отрицательное, и 0, если положительное.

В поле мантиссы хранится только дробная часть, потому что для любого

нормализованного двоичного числа цифра перед точкой – всегда единица.

При хранении чисел в памяти для экономии места она опускается, но подра-

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

число можно представить точно – разрядность мантиссы ограничена.

В поле показателя степени хранится показатель в виде 8-разрядного беззнако-

вого целого числа, к которому прибавлено 127. Например, для числа 1.101*2

зна-

чение показателя равно 5+127=132, или в двоичном виде 10000100.

Для примера найдём представление с одинарной точностью числа

1101.101. Вначале выполним его нормализацию – получим 1.101101*2

Дробная часть мантиссы равна 101101, справа к ней допишем нули так, что-

бы получилось 23 бита: 10110100000000000000000. В поле показателя степе-

ни будет 3+127=130, в двоичном виде это 10000010. Бит нуля равен 0. Итого

получилось 01000001010110100000000000000000, или в более коротком ше-

стнадцатеричном виде 415A0000.

Заметим, что не все вещественные числа можно представить в памяти

ЭВМ в нормализованном виде. Если число очень близко к нулю, то в норма-

лизованном варианте показатель степени может быть настолько большим,

что не влезет в отведенное поле. Возьмём, например, число 101010*2

127

. В

нормализованном виде оно превратится в 1.01010*2

132

, то есть в поле показа-

теля степени должно быть 132+127=259. В значение с одинарной точностью

такой показатель степени уже не поместится. Если в результате вычислений

получилось такое число, оно будет сохранено в денормализованном виде, а в

сопроцессоре возникнет ситуация потери точности (underflow). Особенно-

сти работы сопроцессора с такими числами выходят за рамки данных мето-

дических указаний.

В стандарте IEEE754-1985 представления вещественных чисел кроме соб-

ственно чисел, предусмотрено ещё несколько специальных значений [2] –

они приведены в таблице 4.

Таблица 4

Специальные значения в двоичных

вещественных числах одинарной точности

Значение

Знак, показатель, мантисса

Положительный ноль

0 00000000 00000000000000000000000

Отрицательный ноль

1 00000000 00000000000000000000000

Положительная бесконечность

0 11111111 00000000000000000000000

Отрицательная бесконечность

1 11111111 00000000000000000000000

Тихое NaN (QNaN)

x 11111111 1xxxxxxxxxxxxxxxxxxxxxx

Громкое NaN (SNaN)

x 11111111 0xxxxxxxxxxxxxxxxxxxxxx

В таблице под символом x понимается любое значение (0 или 1). Для

SNaN поле мантиссы должно содержать хотя бы одну единицу.

Значения бесконечностей можно сравнивать между собой и с другими

числами, но при выполнении операций с ними может возникнуть переполне-

ние (overflow).

Значение NaN является признаком нечислового значения. В некоторых

математических библиотеках используется такой подход: если функция не

может вычислить результат (например, корень из отрицательного числа), она

не создаёт исключительную ситуацию, а просто возвращает NaN.

3. Работа с FPU. Рассмотрим теперь кратко применение сопроцессора для

вычислений с вещественными числами.

Примечание. Вообще, название «сопроцессор» возникло вследствие того, что

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

щее время он встраивается в центральный процессор, и всё чаще используется

термин FPU (floating point unit – модуль вычисления с плавающей точкой).

В состав FPU входят 8 80-разрядных регистров R0-R7. Эти регистры ор-

ганизованы в виде стека, поэтому напрямую к ним обращаются редко –

обычно используют относительные имена ST(0) – ST(7) или вообще приме-

няют команды, не требующих указания регистров. Здесь ST(0) – вершина

стека (один из 8 регистров), ST(1) – элемент в стеке перед ним и т.д.

Типичный пример вычисления выглядит так. В стек помещается операнд

из памяти. Затем выполняется операция, где второй операнд указывается в её

аргументе. Либо можно второй операнд также поместить в стек и затем вы-

полнить операцию над обоими аргументами в стеке. После выполнения вы-

числений результат с вершины стека передаётся в память.

Рассмотрим команды, которые нам потребуются. Fld – поместить в стек

вещественное число из памяти, fild – поместить в стек целое число из памяти

(преобразовав в вещественное), fst – скопировать число с вершины стека в

память, fstp - скопировать число с вершины стека в память и удалить из сте-

ка, fist - скопировать число с вершины стека в память в целочисленную ячей-

ку, округлив до целого. Арифметические команды: fadd – сложение, fsub –

вычитание, fdiv – деление, fmul - умножение и др.

Приведём пример вычисления суммы двух вещественных чисел.

include masm32rt.inc

.data

out_format BYTE "%f", 0

var_a REAL8 1.5

var_b REAL8 2.3

sum REAL8 ?

.code

main PROC

fld var_a ;поместить в стек

fadd var_b ;сложить

fst sum ;результат с вершины стека – в память

invoke crt_printf, ADDR out_format, sum

exit

main ENDP

end main

Рассмотрим теперь более сложный пример. Пусть надо вычислить значение

выражения 3.1*(2.8+3.2). Сложное выражение удобно вначале перевести в обрат-

ную польскую (постфиксную) запись, где знак операции стоит не между аргумен-

тами, а после них (эта тема изучалась в курсе «Структуры и алгоритмы обра-

ботки данных»). Для данного примера получится 3.1 2.8 3.2 + *.

Затем идём слева направо по этому выражению и если встретим аргумент,

то поместим его в стек, а если встретим операцию, то выполним её. Пример

программы, где использовался данный подход:

include masm32rt.inc

.data

out_format BYTE "%f", 0

args REAL8 3.1, 2.8, 3.2

res REAL8 ?

.code

main PROC

fld args[0] ;аргумент в стек

fld args[1*TYPE args] ;аргумент в стек

fld args[2*TYPE args] ;аргумент в стек

fadd ;первая операция

fmul ; вторая операция

fst res ;результат из стека в память

invoke crt_printf, ADDR out_format, res

exit

main ENDP

end main

Рассмотрим теперь, как выполняется сравнение чисел. Для этого можно

использовать команду fcom с одним аргументом – она вычитает из st(0) зна-

чение аргумента в памяти и выставляет соответствующие флаги FPU. Далее с

помощью команды fstsw ax программа переписывает содержимое регистра

состояния сопроцессора в регистр ax центрального процессора. Затем содер-

жимое регистра ah переписывается в регистр флагов центрального процессо-

ра при помощи команды sahf. Биты кодов условий сопроцессора отобража-

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

анализа кодов условий можно пользоваться командами условных переходов

для беззнаковых целых чисел – ja, jb, jae и т.п. Пример кода:

fld varA ;загружаем в стек переменную varA

fcom varB ;сравниваем с переменной varB

fstsw ax ;переписываем флаги FPU в ax

sahf ;переписываем флаги из ah во flags

jb L1 ;если меньше, идём на метку

FPU поддерживает довольно большое число и других команд – например,

fsqrt – вычисление квадратного корня, fsin – вычисление синуса, fabs – вы-

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

нической документации (например, на сайте www.intel.com), более подроб-

ные примеры – в учебниках из списка литературы.

Контрольные вопросы и задания

1. Даны вещественные числа в двоичной системе счисления: 0.1, 0.11,

0.10101. Представьте их в виде десятичных простых несократимых дробей.

2. Даны вещественные числа: 0.25, 2.375, 5.1875. Переведите их в двоичную

систему счисления.

3. Переведите числа 0.03 и 0.7 в двоичную систему счисления методом деле-

ния столбиком. Получайте знаки ответа до тех пор, пока не определите пери-

од повторения и не убедитесь, что в двоичной системе данные числа точно не

представляются. При записи ответа укажите период в круглых скобках.

4. Переведите заданные числа в двоичное представление в памяти ЭВМ с

одинарной (REAL4) и двойной (REAL8) точностью и запишите в шестнадца-

теричном виде: 3.25, 4.0

5. Переведите заданные числа из шестнадцатеричного представления с оди-

нарной точностью (REAL4) в десятичную систему: 3E000000h, C0F00000h.

6. Приведите пример операции с двумя нормализованными вещественными

числами, результат которой не получится нормализовать. Как будет пред-

ставлено такое число в памяти? Какой флаг установится в сопроцессоре?

7. Переведите в обратную польскую (постфиксную) запись выражение

((3.5+2.7)*2-3.1)/2.2.

Задания по программированию

1. Впишите недостающую часть в программу на ассемблере, вычисляющую

выражение ((3.5+2.7)*2-3.1)/2.2:

include masm32rt.inc

.data

args REAL8 3.5 2.7 2 3.1 2.2

result REAL8 ?

out_format BYTE "%f", 0; строка формата для printf

.code

main PROC

;впишите сюда команды сопроцессору

invoke crt_printf, ADDR out_format, result

exit

main ENDP

end main

При решении применяйте только команды математического сопроцессора и

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

2. Решите на языке ассемблера задачу №679 из электронной проверяющей

системы кафедры. Ниже приведено условие задачи.

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

ружностей с точностью до двух знаков после запятой.

Входные данные – разделенные пробелом вещественные числа x

и x

– координаты центров и радиус первой и второй окружности.

Выходные данные – площадь пересечения

Пример входных данных: 20.0 30.0 15.0 40.0 30.0 30.0

Пример выходных данных: 608.37

Практическая работа 8. Самокорректирующиеся коды

для хранения и передачи информации в вычислительных системах

Краткие теоретические сведения и примеры

Для повышения надёжности хранения и передачи информации применя-

ются самокорректирующиеся коды, способные обнаруживать и даже исправ-

лять наиболее вероятные возникающие ошибки. Одним из наиболее извест-

ных подобных кодов является код Хэмминга. Он применяется, например, в

некоторых микросхемах памяти, при организации массива RAID 2 для хра-

нени

я данных и других целей. Для объяснения того, как строится код Хэм-

минга, воспользуемся материалом электронного ресурса www.wikipedia.ru.

1. Построение кода Хэмминга. Пусть имеется кодовое слово из m битов.

Чтобы построить код, способный исправлять ошибки в одном бите, необхо-

димо к слову добавить k контрольных разрядов, где k определяется по сле-

дующей формуле:

12 ++> mk

или

)1(log

++≥ mkk

Например, для длины кодового слова m от 5 до 11 получается k

min

=4, при

m от 12 до 26 - k

min

=5, при m от 27 до 57 - k

min

=6.

Имея m+k разрядов, самокорректирующийся код можно построить сле-

дующим образом. Присвоим каждому из разрядов слева направо свой номер -

от 1 до m+k; запишем эти номера в двоичной системе счисления. Поскольку

> m + k, каждый номер можно представить, очевидно, k-разрядным двоич-

ным числом.

Предположим далее, что все m+k разрядов кода разбиты на контрольные

группы, которые частично перекрываются, причем так, что единицы в двоич-

ном представлении номера разряда указывают на его принадлежность к оп-

ределённым контрольным группам. Например: разряд № 5 принадлежит к 1-й

и 3-й контрольным группам, потому что в двоичном представлении его но-

мера 5

= …000101

- 1-й и 3-й разряды содержат единицы.

Среди m+k разрядов кода при этом имеется k разрядов, каждый из кото-

рых принадлежит только к одной контрольной группе:

Разряд № 1: 1

= …000001

принадлежит только к 1-й контрольной группе.

Разряд № 2: 2

= …000010

принадлежит только к 2-й контрольной группе.

Разряд № 4: 4

= …000100

принадлежит только к 3-й контрольной группе.

…

Разряд № 2

−

принадлежит только к k-й контрольной группе.

Эти k разрядов мы и будем считать контрольными. Остальные m разря-

дов, каждый из которых принадлежит, по меньшей мере, к двум контроль-

ным группам, будут информационными разрядами.

В каждой из k контрольных групп будем иметь по одному контрольному

разряду. В каждый из контрольных разрядов поместим такую цифру (0 или

1), чтобы общее количество единиц в его контрольной группе было четным.

Например, довольно распространен код Хэмминга с m=7 и k=4.

Пусть исходное слово (кодовое слово без контрольных разрядов) -

0110101

Обозначим P

- контрольный разряд №i; а D

- информационный разряд

№i, где i = 1,2,3,4…

Интересно посмотреть, как перекрываются контрольные группы в данном

случае. Первая группа контролирует разряды № 3,5,7,9,11 исходного кода,

вторая — 3,6,7,10,11 (№ группы = № контрольного разряда). Очевидно, что

они частично перекрываются.

Таблица 5

Пример построения кода Хэмминга

№ разряда:

1 2 3 4 5 6 7 8 9 10 11

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

Распределение

контрольных и

информа

ционных

разрядов

Информационное

кодовое

слово:

Кодовое слово с

контрольными

разрядами:

1 0 0 0 1 1 0 0 1 0 1

2. Обнаружение и исправление ошибки. Предположим теперь, для при-

мера, что при передаче данного кодового слова 10001100101 произошла

ошибка в 11–м разряде, так, что было принято новое кодовое слово

10001100100. Произведя в принятом коде проверку четности внутри кон-

трольных групп, мы обнаружили бы, что количество единиц нечетно в 1-й,2-

й и 4-й контрольных группах, и четно в 3-й контрольной группе. Это указы-

вает, во-первых, на наличие ошибки, во-вторых, означает, что номер оши-

бочно принятого разряда в двоичном представлении содержит единицы на

первом, втором и четвёртом местах и нуль - на третьем месте, т.к ошибка

только одна, и 3-я контрольная сумма оказалась верной.