47602 (Микропроцессор i8086/i8088), страница 3

На основании вышеизложенного примем решение использовать алгоритм подсчёта битов в элементе массива. Расчёт же контрольного кода сделаем адаптивным, то есть для массивов, размер которых не превышает разрядность контрольного кода, используем битовое маскирование, а для массивов большего размера – подсчёт количества «чётных» элементов.

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

2.2. Отладка и тестирование

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

- формирование контрольного массив данных и его заполнение с помощью генератора псевдослучайных чисел;

- вычисление контрольного кода чётности и его сохранение с помощью основной подпрограммы;

- вывод на экран значений элементов массива и контрольного кода чётности;

- интерактивное изменение какого-либо элемента исходного массива;

- пересчёт контрольного кода массива и сравнение с сохраненным ранее.

Тестовая программа будет разработана, как и основная подпрограмма, с использованием языка программирования Ассемблер.

В общем случае тестовая программа не обязательно должна разрабатываться на том же языке программирования, что и основной алгоритм, – можно было бы использовать любой язык программирования, позволяющий взаимодействовать с Ассемблером. Причём, разные языки программирования обеспечивают необходимое взаимодействие с помощью различных механизмов и определяют собственные ограничения. Так, C и C++ поддерживают подключение двоичных модулей, которые могут быть получены как результат компиляции ассемблерной программы. Turbo Pascal, например, поддерживает ассемблерные вставки на уровне исходных текстов.

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

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

2. Вывод на экран числовых значений - будет использоваться для отображения значений элементов массива и контрольного кода чётности. Если преобразовать число к строковому виду, то для непосредственного отображения можно будет использовать алгоритм вывода на экран текстового сообщения. Таким образом, реализация алгоритма может быть упрощена за счёт его разбиения на две составляющие:

- преобразовать число к строковому виду;

- вывести строку на экран.

3. Преобразование числа к строковому виду.

Наиболее распространенные варианты представления чисел – десятичное, восьмеричное, шестнадцатеричное и двоичное.

Символы ‘0’…’9’ располагаются в таблице ASCII-кодов последовательно, поэтому просто реализуется преобразование чисел в десятичное представление. Также десятичная форма отображения чисел является достаточно компактной. С учётом этого примем решение выводить числа на экран в десятичном виде.

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

5. Генерация случайных чисел

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

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

Самый часто применяемый тип алгоритмов генерации псевдослучайных последовательностей – линейные конгруэнтные генераторы, описываемые общим рекуррентным соотношением:

Ij+1 = (aIj + c) MOD m

При правильно выбранных числах a и c эта последовательность возвращает

все числа от нуля до m–1 псевдослучайным образом и её периодичность сказывается только на последовательностях порядка m. Если число a подобрано очень тщательно, может оказаться, что число c равно нулю. Так, классический стандартный генератор Льюиса, Гудмана и Миллера использует a=16807 (75) при m=231-1, а генераторы Парка и Миллера используют a=48271 и a=69621 (при том же m).

Реализуем последний из описанных вариантов, используя в качестве начального значения I текущее значение тактов таймера, которое хранится в виде двойного слова в области данных BIOS по адресу 0040: 006C.

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

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

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

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

2.3. Подсчёт контрольного кода четности

Для вычисления контрольного кода чётности будем использовать подсчёт битов в исходных элементах массива. С учётом ёмкости контрольного числа в 32 бита для массивов, размер которых не более 32 байта, используем битовое маскирование результирующего кода, а для массивов большего размера – подсчёт байтов, количество битов в которых чётно.

Блок-схема алгоритма имеет вид:

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

2.4. Битовое маскирование

Традиционно массивы в графическом виде представляются в виде последовательности элементов, упорядоченных слева направо, а двоичные числа – справа налево:

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

С учётом этого факта несложно построить алгоритм формирования контрольного числа, в котором последовательно будут проверяться элементы массива и в зависимости от результата проверки соответствующие биты контрольного числа будут устанавливаться в 1 или 0. Текстовое описание такого алгоритма:

1. Обнулить контрольное число

2. Установить указатель на последний элемент массива

3. Проверить на четность очередной элемент массива

4. Если чётный, установить флаг переноса в 1. Иначе установить в 0.

5. Выполнить битовый сдвиг контрольного числа с учётом флага переноса на 1 разряд в сторону старших разрядов.

6. Если все элементы массива обработаны, закончить.

7. Иначе перейти к предыдущему элементу массива и продолжить с пункта 3

Графическое представление алгоритма в виде блок-схемы:

2.5. Подсчет в массиве байтов с четным количеством бит

Подсчёт количества байтов с чётным количеством бит реализовать достаточно просто:

Обнулить результат

Установить указатель на первый элемент массива

Проверить на чётность очередной элемент массива

Если чётный, добавить к результату 1

Если все элементы массива обработаны, закончить

Иначе перейти к предыдущему элементу массива и продолжить с пункта 3

Графическое представление алгоритма в виде блок-схемы:

2.6. Проверка элементов массива на чётность

Для проверки отдельных байтов массива на чётность удобно использовать команду test, которая вычисляет результат действия побитового логического «И» над приёмником и источником и устанавливает флаги SF, ZF и PF в соответствии с результатом, при этом результат не сохраняется. Если после выполнения команды test флаг PF будет установлен в 1, количество бит в байте чётно.

1. Вывод на экран текстовых сообщений

Наиболее простое решение – использовать для вывода текста функцию 9h DOS (прерывание INT21h), которая получает адрес строки для вывода через регистр dx, причем строка должна завершаться символом $.

2. Преобразование числа к строковому виду

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

в десятичное представление. [4, 201]

Суть используемого алгоритма заключается в выполнении следующих действий:

Разделить исходное число на 10.

Добавить к остатку ASCII-код нуля.

Записать полученную цифру в стек.

Увеличить счётчик цифр.

Если ещё есть что делить, продолжить с п.1

По количеству цифр: извлечь цифру из стека и дописать в конец результирующей строки.

Дописать в конец результирующей строки символ $.

Базовый алгоритм рассчитан на работу с 16-разрядными числами. Так как в разрабатываемой программе код чётности будет представлен в виде 32-разрядного числа, модифицируем исходный алгоритм для работы с двойными словами. Такая модификация выполняется достаточно просто заменой в исходном коде наименований регистров: ax на eax, bx на ebx, dx на edx.

3. Ввод числовых данных

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

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

Подготовить буфер ввода данных

Вызвать функцию DOS 0Ah для ввода с клавиатуры

Проверить количество введенных символов. Если = 0, ошибка

Выполнить проверку ввода десятичного числа

В целях обеспечения возможности повторного использования, а также для более простого понимания алгоритма в нём выделен отдельный подалгоритм проверки ввода десятичного числа.

4. Алгоритм проверки ввода десятичного числа

Алгоритм проверки ввода десятичного числа можно представить в виде текстового описания:

1) Проверить количество символов. Если больше 5, ошибка

2) Обнулить результат

3) Читать символ из буфера ввода

4) Если код символа меньше «0» или больше «9», ошибка