Цель данной книги — предоставить читателю базовый практический материал для создания сложных полнофункциональных программ на языке ассемблера. Каждая из десяти глав Практикума посвящена определенной теме. Характер подобранного материала — прикладной. Исчерпывающе рассмотрены вопросы организации взаимодействия программы на ассемблере с внешним миром. Приведены варианты ассемблерной реализации многих известных и востребованных на практике алгоритмов. Изложение базовых вопросов прикладного программирования сопровождается рассмотрением многих интересных задач. Книга предназначена для студентов и специалистов, применяющих ассемблер для решения задач прикладного и системного программирования. Для наиболее качественного и эффективного изучения материала книги рекомендуется использовать данный Практикум параллельно с Учебником и Справочником того же автора. Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки дипломированных специалистов «Информатика и вычислительная техника»
Благодарности 9
Введение
Структура книги
От издательства
Глава 1. Программирование целочисленных арифметических операций
Двоичные числа
Сложение двоичных чисел
Вычитание двоичных чисел
Умножение двоичных чисел
Деление двоичных чисел
Двоично-десятичные числа (BCD-числа)
Неупакованные BCD-числа
Упакованные BCD-числа
Генерация последовательности случайных чисел
Конгруэнтный метод генерации последовательности случайных чисел
Аддитивный генератор случайных чисел
Программа генерации высокослучайных двоичных наборов
Глава 2. Сложные структуры данных
Основные понятия
Способы распределения памяти
Множество
Массив
Описание массивов
Работа с массивами
Структура
Вложенные структуры
Массивы структур -- таблицы
Список
Последовательные списки
Связные списки
Сеть
Создание двусвязного списка состояний конечного автомата
Создание односвязного списка переходов для состояния конечного автомата
Дерево
Представление дерева в памяти
Лексикографическое дерево
Элементы компиляции программ
Формальное описание языка программирования
Описание процесса трансляции программы
Глава 3. Процедуры в программах ассемблера
Реализация рекурсивных процедур
Реализация вложенных процедур
Разработка динамических (DLL) библиотек
Шаг 1. Разработка текста DLL-библиотеки
Шаг 2. Трансляция и компоновка исходного текста DLL-библиотеки
Шаг 3. Создание lib-файла
Шаг 4. Сборка приложения с использованием DLL-библиотеки
Шаг 5. Проверка работоспособности приложения с использованием DLL-библиотеки
Глава 4. Обработка цепочек элементов
Прямой поиск в текстовой строке
Поиск с предварительным анализом искомой подстроки
Глава 5. Работа с консолью в программах на ассемблере
Функции BIOS для работы с консолью
Функции BIOS для работы с клавиатурой
Функции BIOS для работы с экраном
Функции MS DOS для работы с консолью
Функции MS DOS для ввода данных с клавиатуры
Функции MS DOS для вывода данных на экран
Работа с консолью в среде Windows
Организация ввода-вывода в консольном приложении Windows
Глава 6. Преобразование чисел
Ввод чисел с консоли
Ввод целых десятичных чисел из диапазона 0..99
Ввод целых десятичных чисел из диапазона 0..4 294 967 295
Ввод целых десятичных чисел из диапазона 0..999 999 999 999 999 999
Ввод целых десятичных чисел из диапазона 0..
Ввод вещественных чисел
Вывод чисел на консоль
Вывод шестнадцатеричных чисел
Вывод целых десятичных чисел из диапазона 0..99
Вывод целых десятичных чисел из диапазона 0..
Вывод целых десятичных чисел из диапазона 0..999 999 999 999 999 999
Вывод вещественных чисел
Глава 7. Работа с файлами в программах на ассемблере
Работа с файлами в MS DOS (имена 8.3)
Создание, открытие, закрытие и удаление файла
Чтение, запись, позиционирование в файле
Получение и изменение атрибутов файла
Работа с дисками, каталогами и организация поиска файлов
Работа с файлами в MS DOS (длинные имена)
Создание, открытие, закрытие и удаление файла
Получение и изменение атрибутов файла
Работа с дисками, каталогами и организация поиска файлов
Файловый ввод-вывод в Win32
Обработка ошибок
Создание, открытие, закрытие и удаление файла
Чтение, запись, позиционирование в файле
Получение и изменение атрибутов файла
Работа с дисками, каталогами и организация поиска файлов
Файлы, отображаемые в память
Глава 8. Профайлер
Расширение традиционной архитектуры Intel
Команды RDMSR и WRMSR
Команда CPUID -- получение информации о текущем процессоре
Использование счетчика меток реального времени TSC
Глава 9. Вычисление CRC
CRC-арифметика
Прямой алгоритм вычисления CRC
Табличные алгоритмы вычисления CRC
Основы
Прямой табличный алгоритм CRC16
Прямой табличный алгоритм CRC32
"Зеркальный" табличный алгоритм CRC32
Глава 10. Программирование XMM-расширения
Программирование XMM-расширения
Описание упакованных и скалярных данных
Примеры использования команд XMM-расширения
Препроцессор команд XMM-расширения
Поддержка XMM-команд в файле iaxmm.inc
Поддержка XMM-команд путем препроцессорной обработки
Заключение
Список литературы
ОТРЫВОК
Если вы можете измерить и выразить числами то, о чем говорите, -- кое-что вы об этом знаете; если же вы не можете этого измерить и выразить числами -- знание ваше ограничено и неудовлетворительно: возможно, что это начало знания, но едва ли вы в мыслях продвинулись до уровня научной теории.
Лорд Кельвин (конец XIX века)
...наука начинается с тех пор, как начинают измерять.
Д. И. Менделеев
В этой главе мы рассмотрим проблему измерения скорости работы программ. Интерес к данной теме у программистов всегда повышен и подобен интересу рыболовов к размерам выловленной рыбы. Когда программист разрабатывает алгоритм реализации некоторой задачи, то он обязательно пытается оценить скорость, с которой будет работать программа по этому алгоритму. В процессе изложения материала мы уже не раз предлагали для решения одной задачи несколько способов, но при этом оставляли открытым вопрос об оценке их эффективности. В этом разделе попытаемся ликвид
ировать этот пробел, при этом попутно рассмотрим несколько общих вопросов, связанных с микропроцессорами архитектуры Intel (Intel и AMD). Основное внимание мы уделим некоторым средствам микропроцессора Intel, предназначенным для оценки эффективности функционирующих на них программ. В значительной степени рассматриваемый ниже материал также применим и к микропроцессорам AMD, так как эти микропроцессоры имеют подобные средства.
Расширение традиционной архитектуры Intel
С появлением микропроцессоров пятого поколения (Pentium, Pentium MMX...) программисту следует различать два слоя микропроцессоров архитектуры Intel: базовый и модельно-зависимый.
Слой базовой архитектуры включает в себя элементы архитектуры, поддержку и неизменность которых производитель (Intel) гарантирует. Это набор и структура системных регистров и регистров общего назначения, архитектура памяти и т. д.
Модельно-зависимый слой архитектуры включает в себя средства, поддержка которых зависит от конкретной модели процессора (как правило, снизу вверх). Для того чтобы программа, исполняемая процессором, могла получить сведения о возможностях этого процессора, в систему команд включена команда CPUID. Данная команда позволяет программе в любой момент времени получить сведения о классе, модели и архитектурных особенностях текущего процессора. По-дробное описание данной команды приведено ниже.
Физически модельно-зависимые средства представляют собой набор модельно-зависимых регистров -- MSR (Model Specific Registers). Наличие и назначение этих регистров по определению зависит от конкретной модели процессора, что, в свою очередь, не гарантирует их поддержку будущими процессорами архитектуры Intel. MSR-регистры обеспечивают управление различными аппаратно- и программно-зависимыми средствами, включая следующие:
счетчики мониторинга производительности;
расширения отладки;
поддержка исключения машинной ошибки и архитектуры машинного контроля (MCA);
регистры MTRR для поддержки расширенных средств кэширования.
Чтение и запись в MSR-регистры осуществляются командами RDMSR и WRMSR. Большинство MSR-регистров инициализируются при программной инициализации процессора, многие из них можно впоследствии установить в соответствии с конкретными потребностями программы. Приведем краткое описание команд RDMSR, WRMSR и CPUID.
Команды RDMSR и WRMSR
Команда RDMSR (ReaD from Model Specific Register) выполняет чтение из MSR-регистра. Действие команды заключается в проверке двух условий: во-первых, проверяется наличие нулевого уровня привилегированности кода, во-вторых, проверяется наличие в регистре ECX значения, адресующего один из MSR-регистров. Если хотя бы одно из этих условий не выполняется, то выполнение команды RDMSR заканчивается. Если выполняются оба условия, то значение MSR-регистра, адресуемого содержимым регистра ECX, помещается в пару 32-битных регистров EDX:EAX.
Команда WRMSR (WRite to Model Specific Register) производит запись значения в один из 64-разрядных MSR-регистров. Действие команды заключается в проверке тех же двух условий: во-первых, проверяется наличие нулевого уровня привилегированности кода, во-вторых, проверяется наличие в регистре ECX значения, адресующего один из MSR-регистров. Если хотя бы одно из этих условий не выполняется, то работа команды заканчивается. Если выполняются оба условия, то значение пары 32-битных регистров EDX:EAX пересылается в 64-битный MSR-регистр, номер которого задан в регистре ECX.
Команда CPUID -- получение информации о текущем процессоре
Для получения информации о процессоре необходимо в регистр EAX поместить параметр -- одно из значений 0, 1 или 2.
Если EAX = 0, то в регистрах EAX, EBX, EDX, ECX формируется следующая информация:
EAX = n, где n -- максимально допустимое значение параметра, которое может быть помещено в регистр EAX для задания режима сбора информации;
(EBX)+(EDX)+(ECX) -- в этих регистрах содержится строка-идентификатор процессора "GenuineIntel".
Если EAX = 1, то в регистрах процессора сформируется следующая информация:
EAX = n -- информация о микропроцессоре (см. табл. 8.1 и 8.2);
EDX = n -- информация о возможностях процессора (см. табл. 8.3).
Если EAX = 2, то в регистрах EAX, EBX, ECX и EDX формируется информация о кэш-памяти первого уровня и TLB-буферах. Первый байт регистра EAX содержит число, означающее, сколько раз необходимо последовательно выполнить команду CPUID для получения полной информации о кэш-памяти первого уровня и TLB-буферах. Другие байты регистра EAX и все байты регистров EBX, ECX и EDX содержат однобайтовые дескрипторы, характеризующие кэш-память и TLB-буферы (см. табл. 8.4). Старший бит каждого регистра характеризует достоверность информации в регистре. Если он равен нулю, то информация достоверна,
иначе -- регистр не используется.
Таблица 8.1. Поля регистра EAX после выполнения команды CPUID (при EAX = 1)
Биты EAX Назначение
0...3 Версия изменений модели
4...7 Модель в семействе (см. табл. 8.2)
8...11 Семейство микропроцессоров (см. табл. 8.2)
12...13 Тип процессора (00 -- обычный процессор; 01 -- Overdrive-процессор; 10 -- процессор для использования в двухпроцессорных системах)
Таблица 8.2. Значения бит 4...7 и 8...11 регистра EAX
Биты EAX (8...11) Биты EAX (4...7) Тип процессора
0100 0000 или 0001 I486DX
0100 0010 I486SX
0101 0010 Pentium 75-200
0101 0100 Pentium MMX 166-200
0110 0001 Pentium Pro
0110 0011 Pentium II, модель 3
0110 0101 Pentium II, модель 5, Pentium II Xeon
0110 0110 Celeron, модель 6
0110 0111 Pentium III и Pentium III Xeon
0110 0011 Pentium II OverDrive
Таблица 8.3. Поля регистра EDX после выполнения команды CPUID (при EAX=1)
Биты EDX Назначение (если биты установлены)
0 Присутствует сопроцессор с набором команд i387
1 Поддержка расширенных возможностей обработки прерываний в режиме виртуального процессора i8086
2 Процессор поддерживает точки прерывания ввода-вывода (точки останова по обращению к портам) для предоставления расширенных возможностей отладки и доступ к регистрам DR4 и DR5. Флаг CR4.DE=1
3 Процессор поддерживает 4-мегабайтные страницы
4 Поддержка счетчика меток реального времени TSC
5 Поддержка команд RDMSR и WRMSR для работы с модельно-зависимыми регистрами
6 Процессор поддерживает физические адреса, большие, чем 32 бита, расширенный формат элемента таблицы страниц, дополнительный уровень трансляции страничного адреса и 2-мегабайтные страницы
7 Поддержка исключения 18 -- машинного контроля
8 Поддержка инструкции CMPXCHG8B
9 Микропроцессор содержит программно-доступный контроллер прерываний APIC
10 Резерв
11 Поддержка инструкций SYSENTER и SYSEXIT быстрых системных вызовов
12 Поддержка регистра управления кэшированием MTRR_CAP (относится к MSR-регистрам)
13 Поддержка работы с битом G, определяющим глобальность страницы в PTDE и PTE. Бит CR4.PGE = 1
14 Поддержка архитектуры машинного контроля (MSR-регистр MCG_CAP)
15 Поддержка инструкций CMOV, FCMOVCC, FCOMI условной пересылки
16 Поддержка инструкций CMOVCC, FMOVCC и FCOMI (если установлен бит 0)
17 Процессор поддерживает 36-разрядную физическую адресацию с 4-мегабайтными страницами
18 Процессор поддерживает собственную идентификацию по уникальному 96-битному номеру и эта поддержка активна
19-22 Резерв
23 Поддержка целочисленного MMX-расширения
24 Процессор поддерживает команды FXSAVE и FXRSTOR
25 Поддержка MMX-расширения с плавающей точкой
24-31 Резерв
Таблица 8.4. Значения дескрипторов, описывающих кэш-память, и дескрипторов TLB
Содержание дескриптора Значение
00h Нулевой дескриптор
01h Буфер TLB-команд: размер страницы -- 4 Кбайт, ассоциативный 4-канальный, 32 входа
02h Буфер TLB-команд: размер страницы -- 4 Кбайт, ассоциативный, 2 входа
03h Буфер TLB-данных: размер страницы -- 4 Кбайт, ассоциативный 4-канальный, 64 входа
04h Буфер TLB-данных: размер страницы -- 4 Кбайт, ассоциативный 4-направленный, 8 входов
06h Кэш команд: размер 8 Кбайт, наборно-ассоциативный 4-канальный, длина строки 32 байта
08h Кэш команд: размер 16 Кбайт, наборно-ассоциативный 2-канальный, длина строки 32 байта
0ah Кэш данных: размер 8 Кбайт, ассоциативный 2-направленный, длина строки 32 байта
0ch Кэш данных: размер 16 Кбайт, ассоциативный 2-или 4-направленный, длина строки 32 байта
40h Кэш-память второго уровня (L2) отсутствует
41h Объединенный кэш: размер 128 Кбайт, наборно-ассоциативный 4-канальный, длина строки 32 байта
42h Объединенный кэш: размер 256 Кбайт, наборно-ассоциативный 4-направленный, длина строки 32 байта
43h Объединенный кэш: размер 512 Кбайт, наборно-ассоциативный 4-направленный, длина строки 32 байта
44h Объединенный кэш: размер 1 Мбайт, наборно-ассоциативный 4-направленный, длина строки 32 байта
45h Объединенный кэш: размер 2 Мбайт, наборно-ассоциативный 4-направленный, длина строки 32 байта
Рассмотрим подробнее средства для мониторинга производительности, которые включают счетчик меток реального времени TSC (Time Stamp Counter) и счетчики событий CTR0, CTR1.
Использование счетчика меток реального времени TSC
Счетчик меток реального времени TSC (Time Stamp Counter) -- регистр, содержимое которого инкрементируется с каждым тактом процессорного ядра. Каждый раз при аппаратном сбросе (сигналом RESET) отсчет в этом счетчике начинается с нуля. Разрядность регистра обеспечивает счет без переполнения в течение сотен лет. Счетчик продолжает счет как при исполнении инструкции HLT, так и при остановке процессора по сигналу STPCLK# (для энергосбережения). Чтение счетчика обеспечивает инструкция RDTSC, установкой бита CR4.TSD ее можно сделать привилегированной (доступной лишь при CPL = 0). Чтен
ие и запись TSC возможны также по инструкциям обращения к MSR (при CPL = 0), причем запись может выполняться только в младшие 32 бита, а старшие биты при операции записи обнуляются. Присутствие счетчика TSC определяется по инструкции CPUID (EAX = 1). Если в результате ее вызова бит 4 регистра EDX равен 1, то процессор поддерживает счетчик меток реального времени TSC.
Команда RDTSC (ReaD from Time Stamp Counter -- чтение 64-разрядного счетчика меток реального времени TSC (Time Stamp Counter)) не имеет операндов. Машинный код этой команды -- 0f 31. Команда проверяет состояние второго бита регистра CR4.TSD (Time Stamp Disable -- отключить счетчик меток реального времени):
если CR4.TSD = 0, то выполнение команды RDTSC разрешается на любом уровне привилегий;
если CR4.TSD = 1, то выполнение команды RDTSC разрешается только на нулевом уровне привилегий.
Если после данной проверки выполнение команды разрешено на текущем уровне привилегий, то выполняется сохранение значения 64-битного MSR-счетчика TSC в паре 32-битных регистров EDX:EAX. Если выполнение команды запрещено, то работа команды заканчивается.
Разработаем две макрокоманды, использование которых позволит нам получать количественную оценку работы кода, начиная от полной программы и заканчивая отдельной командой. Эти макрокоманды не будут отличаться компактностью, но этого от них и не требуется, так как они являются лишь средством оценки эффективности, используемым на этапе отладки и в конечном коде их наличие не требуется.
На взгляд автора, применение этих макрокоманд должно подчиняться следующему алгоритму. Вызов первой макрокоманды, назовем ее profiler_in, должен зафиксировать момент, относительно которого будет производиться отсчет тактов процессора, то есть в начале профилируемого участка программы. Вызов второй макрокоманды profiler_out должен зафиксировать момент окончания работы на этом участке программы. Необходимо иметь в виду, что это "грязное" время работы программы, по которому можно производить только приблизительную оценку ее скорости работы. Для этого есть внут
ренняя и внешние причины. Внутренняя причина заключается в том, что полученная величина включает время, затраченное на работу некоторых команд, составляющих тело самой макрокоманды. Этот недостаток исправить легко. Что касается внешних причин, то они объективны по отношению к программе пользователя и мешают получению истинного времени профилирования. В качестве таких внешних причин могут быть программы операционной системы, которые могут приостанавливать на время программу пользователя. Внешней причиной является и отладчик, так как при работе в нем
вообще нет смысла производить оценку скорости.
Ниже приведены макрокоманды profiler_in и profiler_out с тестовым примером для проверки их работы. Данные макрокоманды производят корректировку результата своей работы, с тем чтобы исключить обсужденные выше внутренние причины "грязного" времени работы программы. Заметим, что не всякий транслятор ассемблера "знает" о новых командах микропроцессора, в том числе и о команде RDTSC. По этой причине мы ее моделируем, инициализируя в сегменте кода 2 байта значениями машинного кода этой команды db 0fh,31h.
;----------------------------------------------------------
;prg08_01.asm -- программа демонстрации использования макрокоманд profiler_in
;и profiler_out для оценки производительности фрагментов кода.
;----------------------------------------------------------
;... ... ...
bin_dec_fpu macro string_bin_qword:REQ, string_pack:REQ, adr_string_pack:REQ, len_string_pack:REQ, adr_string:REQ, len_string:REQ
local cycl
;----------------------------------------------------------
;макрокоманда вывода на консоль десятичного числа:
;на входе:
;string_bin_qword -- адрес 64-битной ячейки (описанной dt) с преобразуемым
;двоичным целым числом
;string_pack -- адрес 80-битной ячейки (описанной dt), в которую сохраняется
;упакованное 10-е значение
;adr_string_pack -- ячейка с адресом string_pack (описанной dd)
;len_string_pack -- длина string_pack
;adr_string -- ячейка с адресом string (описанной dd). В string помещаются
;символы десятичных цифр для вывода.
;len_string -- размер string (18 байт)
;---------преобразуем bin->dec ----------------------------
finit
fild string_bin_qword ;заносим в сопроцессор двоичное целое число
fbstp string_pack ;извлекаем упакованное десятичное
;---------распакуем----------------------------------------
lds si,adr_string_pack
add si,len_string_pack-2 ;на конец string_pack (18 упак. дес. цифр)
les di,adr_string
mov cx,9 ;9 пар упакованных десятичных цифр
xor ax,ax
cycl: xor ax,ax
std ;string_pack обрабатываем с конца
lodsb ;в аl очередные 2 упакованные десятичные цифры
;распаковываем -- ah=младшая, al=старшая
shl ax,4
rol al,4
or ax,3030h ;преобразуем в символьное представление
xchg ah,al ;ah=младшая, al=старшая
cld ;в string записываем с начала
stosw
loop cycl
;---------выводим на консоль-------------------------------
mov bx,1 ;стандартный дескриптор -- экран
mov cx,len_string
lds dx,adr_string ;формируем указатель на строку string
mov ah,40h ;номер функции DOS
int 21h ;выводим
jc exit ;переход в случае ошибки
endm
profiler_in macro val_1:REQ
;val_1 -- ячейка памяти 64 бита (2?32) для сохранения момента
;начала профилирования ("грязного")
pushad ;сохранение всех регистров общего назначения в стеке
db 0fh,31h ;RDTSC
mov val_1+4,edx
mov val_1,eax
popad ;восстановление всех регистров общего назначения из стека
endm
profiler_out macro val_1:REQ, val_2:REQ
;val_1 -- ячейка памяти 64 бита (2?32), в которой при входе в макрос сохранен
;момент начала профилирования командой profiler_in. Далее в макросе эта ячейка
;содержит результат профилирования -- число тактов процессора
;val_2 -- ячейка памяти 64 бита (2?32), в которой сохраняется момент ("грязный")
;окончания профилирования
pushad ;сохранение всех регистров общего назначения в стеке
db 0fh,31h ;RDTSC -- окончание профилирования
mov val_2+4,edx
mov val_2,eax
;профилируем pushad и popad с учетом двух shrd
pushad
popad
db 0fh,31h ;RDTSC
;теперь необходимо получить чистое время профилирования, для чего результат
;необходимо скорректировать (уменьшить) на количество тактов процессора,
;потребное для выполнения пар команд PUSHAD\POPAD и MOV
sub eax, val_2
jnc $+4 ;учет заема из старшего разряда
dec edx
sub edx, val_2+4 ;в edx:eax кол-ва тактов для выполнения 2-х команд
;PUSHAD\POPAD и 2-х SHRD
mov eax,val_1
sub val_2,eax
mov eax,val_1+4
jnc $+7 ;учет заема из старшего разряда при выполнении предыдущего вычитания
dec val_2+4
sub val_2+4,eax
;в val_2:val_2+4 -- чистое количество тактов процессора для выполнения
;профилируемого участка
popad ;восстановление всех регистров общего назначения из стека
;выводим
bin_dec_fpu val_2_q, string_pack, adr_string_pack, len_string_pack, adr_string, len_string
endm
.data
val_2 label dword
val_2_q dq 0
val_1 label dword
dq 0
;в string_pack исходное значение из val_2_q в упакованном десятичном формате
string_pack dt 0
len_string_pack=$-string_pack
adr_string_pack dd string_pack
string db 18 dup (0) ;максимальный результат состоит из 18 десятичных цифр
len_string=$-string
adr_string dd string
.code
;... ... ...
;профилируем выполнение команд работы со стеком
profiler_in val_1
push eax
pop eax
profiler_out val_1, val_2
exit: ;выход из программы
;... ... ...
Составьте тестовые примеры и "поиграйтесь" с данной программой. Обратите внимание, что при задании пустой последовательности команд между парой макросов profiler_in и profiler_out все равно получается некоторая величина профилирования. Она постоянна, ее источник -- сами команды RDTSC, которые требуют тактов процессора для своего исполнения. Эту величину можно скорректировать разными способами, но можно и не трогать, а учитывать при подведении окончательных результатов тестирования нужного вам фрагмента кода. На компьютере автора эта величина равна 52.
В этой программе для визуализации результатов профилирования разработана макрокоманда bin_dec_fpu, производящая перевод значения из двоичной системы в десятичную.
Assembler: практикум (+дискета). / В. Юров - СПб: Питер, 2003. - 400 с.
|