Размещено на http://www.allbest.ru/

27

КУРСОВАЯ РАБОТА

ПО ДИСЦИПЛИНЕ «ПРОГРАММИРОВАНИЕ»

Содержание

1. Работа с процессором FPU

2. Программы вычисления TG и ARCTG

Список используемой литературы

1. Работа с процессором FPU

С учетом того, что большинство современных приложений и игр требуют огромного количества вычислений именно над вещественными числами (числа с плавающей точкой), то общая производительность процессора зависит от того, насколько быстро он их обрабатывает. Для этих целей в процессоре существует специальный модуль, получивший название Floating-Point Unit (FPU) - модуль вычислений с плавающей точкой. В то же время производительность этого модуля зависит не только от рабочей частоты процессора, но и от его конструктивных особенностей.

В начале эволюции IBM-совместимых компьютеров вычисления над вещественными числами брал на себя математический сопроцессор, конструктивно выполненный отдельно от центрального процессора. Однако уже в 486-м процессоре Intel применила встроенный модуль вычислений с плавающей точкой, значительно увеличив при этом скорость работы процессора с вещественными числами. Впоследствии на встроенный FPU перешли и другие производители процессоров для персональных компьютеров.

Отметим, что при работе с вещественными числами существует тот же нюанс, что и в целочисленных операциях - команда не может быть выполнена за один такт ядра процессора (смотрите статью "Зачем процессору конвейер", "КВ" №3/2003). И если в 486-х процессорах для обработки целочисленных команд уже начал использоваться пятиступенчатый конвейер, то FPU был по-прежнему не конвейерного типа, т.е. следующая команда с плавающей точкой всегда должна была дожидаться выполнения предыдущей. Это существенно тормозило работу процессора с мультимедийными приложениями. А последние в то время уже начали стремительно набирать обороты в своих "запросах". Поэтому вполне естественно, что Intel, начиная с процессоров Pentium, стала применять конвейер не только в целочисленных, но и в вещественных операциях. Корпорация AMD, в свою очередь, пошла по несколько иному пути - вместо конвейеризации FPU она начала внедрять в свою продукцию технологию 3DNow!, которая также была направлена на повышение производительности в операциях с вещественными числами. Эта технология столкнулась с множеством проблем в своей реализации. Думаю, многие помнят, как AMD K6-2, призванный конкурировать с Pentium II в целочисленных операциях, на процентов тридцать отставал от него в обработке вещественных чисел.

Но, как говорится, на ошибках учатся, поэтому в Athlon'ах и последующих процессорах корпорация AMD перешла на конвейерный тип FPU. Более того, в новых процессорах AMD применила в модуле вычислений с плавающей точкой не только суперконвейеризацию, но и суперскалярность - в одном процессоре стало располагаться, грубо говоря, три модуля FPU, каждый из которых принимает участие в вычислениях с плавающей точкой. Другими словами, с выходом процессоров Athlon/Duron продукция AMD перестала уступать в скорости вычислений над вещественными числами своему конкуренту - корпорации Intel. А это сыграло очень существенную роль в расстановке сил этих извечных соперников на современном процессорном рынке.

FPU (Floating Point Unit) используется для ускорения и упрощения вычислений с плавающей точкой.

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

До некоторых моделей 80486 FPU исполнялся в виде отдельной микросхемы, устанавливаемой опционально. В некоторых 486 и во всех Pentium (и выше), FPU интегрирован в процессор, поэтому можно считать, что он присутствует в каждом более-менее современном компьютере. Начиная с Pentium Pro FPU имеет дополнительные команды, упрощающие сравнение чисел. В любом случае, если FPU недоступен, или не поддерживает какие-либо ф-ции, то возможна их программная эмуляция.

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

Числа FPU

Сопроцессор поддерживает числа следующих форматов:

· FP формат. Числа в формате с плавающей точкой, соответствуют стандарту IEEE 754. Могут быть следующих типов:

Название	Размер (в битах)	Размер мантиссы	Смещение порядка	Диапазон нормализованных значений
Single Precision Одинарная точность	32	23	127	2-126	2127
Double Precision Двойная точность	64	52	1023	2-1022	21023
Double Extended Precision Двойная расширенная точность	80	64	16 383	2-16382	216383

· При загрузке числа, сопроцессор переводит его в формат двойной расширенной точности, но точность вычислений зависит от CW.PC

· Формат FP числа следующий: по смещению ноль находится мантисса, далее - экспонента+смещение порядка, и старший бит - знак (0-положительное, 1 - отрицательное). Размеры чисел указаны в таблице выше.

· 32 и 64 битные числа не содержат первый бит мантиссы, он считается равным единице. Таким образом числа 32, 64 и 80 битного размера могут без искажения содержать 24, 53 и 64 битные числа

· Пример: переведем число 123,375 в FP формат

· Целая часть 123=1111011

· Дробная часть получается следующим образом:

0.375 меньше 1/2	0
0.375 больше 1/4	1
0.375-1/4 равно 1/8	1

· Получим число 011 в двоичной системе. Т.е можно умножать числo на 2, записывая младший бит целого результата, пока число не ноль или не закончились свободные биты числа. Также, если количество свободных бит известно, можно умножить дробную часть на соответствующую степень двойки, не удаляя ведущие ноли.

· Получилось, что число 123,375 равно 1111011,011

· Умножим на такую степень двойки, чтобы получилось число вида 1,xxx: 1111011,011= 1,111011011*2 в степени 6

· Число 1,111011011 называется мантиссой, 6 - экспонентой, 1 - целая часть мантиссы.

32 бита:	0100 0010 1111 0110 1100 0000 0000 0000
64 бита:	0100 0000 0101 1110 1101 1000 0000.... 0000
80 бит:	0100 0000 0000 0101 1111 0110 1100 0000.... 0000

· Для указания FP чисел в MASM используются типы real4, real8 и real10. Пример: AnyNumber real8 123.456

· Можно указывать данные типы директивами dd, dq и dt соответственно, но они не сообщат об ошибке, если число не FP (если число не содержит точки)

· Числа могут иметь специальные значения:

o +0 и -0 : Все биты числа (кроме старшего у -0) равны нолю.

o + и - Бесконечность: Все биты экспоненты установлены, мантисса вида 1,00..00

o + и - Денормализованное число: Все биты экспоненты сброшены, мантисса вида 0,xxxx (не нулевая).

o SNaN (сигнальное не-число): Все биты экспоненты установлены, мантисса вида 1,0xxxx (не нулевая)

o QNaN (тихое не-число): Все биты экспоненты установлены, мантисса вида 1,1xxxx (не нулевая)

o Неопределенность: Все биты экспоненты установлены, мантисса вида 1,10..00 ;Знаковый бит установлен.

При операциях с SNaN возникает исключение #I (Если не установлен бит CR.IM). Причем, если SNaN real4 или real8 исключение происходит при загрузке, а если real10, то при математической операции над ним, что позволяет использовать эти числа для разных методов отладки и тестирования программы. Свободные биты мантиссы могут быть использованы для хранения дополнительной информации.

· Целые знаковые числа. Обычные числа, описанные в Главе #2. Могут быть размером 16, 32 и 64 бита.

· 64 битные числа имеют тип QWORD, и объявляются директивой dq. При выгрузке NaN'ов получается число, старший бит которого установлен, а остальные - сброшены.

· Packed BCD (Binary-coded decimal) числа, размером 80 бит. Каждые 4 бита такого числа могут принимать значения от 0 до 9, бит #79 - знак, 78-72 не имеют значения. При выгрузке NaN'ов, получается число, 18 старших битов которого установлены, а остальные - сброшены.

· Пример: десятичное число - 12345 в формате Packed BCD равно 80 00 00 00 00 00 00 01 23 45h. В памяти байты расположены наоборот.

· Эти числа имеют тип TBYTE, для объявления в программе используется директива dt

· Пример: десятичное число 123456789 можно объявить так: dt 123456789h

Использование FPU

Для работы с FPU существует отдельная группа команд, название которых начинается с символа "f".

Сопроцессор работает параллельно CPU, и, поэтому, раньше (до 287) необходимо было перед многими командами FPU вставлять команду fwait, чтобы приостановить выполнение до окончания вычислений.

В последующих сопроцессорах эта команда встроена в инструкции FPU, поэтому ее использовать не нужно. Но остались также не ожидающие команды, имеющие приставку "n". Пример fsave/fnsave - одно и тоже действие, но первая команда вызовет исключение, если оно произошло до этого, но еще не вызывалось. На самом деле эти две команды - одни и те же, но перед fsave компилятор добавляет команду fwait.

Операндом команд является, как правило, один из регистров st(), или ячейка памяти. Другой операнд обычно подразумевается st(0). Команды с операндом "память" могут иметь приставку "i", что означает операнд - обычное число, без приставки - в FP формате.

Большинство команд не работает с регистрами общего назначения. Для работы с числом из регистра общего назначения можно, например, использовать стэк:

Пример: сложение eax с ecx, используя FPU

Это именно пример использования FPU, для сложения двух регистров есть команда add.

push eax

fild dword ptr [esp]

push ecx

fiadd dword ptr [esp]

pop eax ;очистим стэк

fistp dword ptr [esp]

pop eax ;eax= результат

Несмотря на то, что многие команды работают только с st(0), можно легко использовать число из другого FP регистра, поменяв значения регистров командой fxch.

Некоторые команды имеют суффикс "r", что означает назначение операции - второй операнд.

Также, если в команде присутствует суффикс "p", то происходит выталкивание числа из стэка сопроцессора.

Процедуры, работающие с FPU обычно придерживаются следующего соглашения:

На входе и выходе стэк сопроцессора пуст. Иногда для возврата FP числа используется st(0).

Можно использовать все регистры FPU, за исключением CW.

Команд FPU не много, и их легко отличить по первой букве "f", поэтому не будет дано их описание.

Программирование процессоров Intel описано в документах из раздела "Manuals" ~10 мб, они очень полезны для программиста на Assembler'е.

Также описание команд можно найти в пакете MASM32, и в комплекте с компилятором.

Программная модель.

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

Формат контекста в памяти зависит от разрядности кода и операнда. Состоит из:

· Control Word (CW) - слово управления или Control Register (CR) - регистр управления. Позволяет задать некоторые свойства работы сопроцессора.

15	14	13	12	11-10	9-8	7	6	5	4	3	2	1	0
			X	RC	PC			P M	U M	O M	Z M	D M	I M

· Для записи слова управления обычно используется команда fldcw, для считывания - fstcw, fnstcw

· После команд finit/fninit и fsave/fnsave CW устанавливается равным 37Fh Значения бит слова управления:

o 0-5 *M маскируют исключения сопроцессора. Если бит установлен, исключение не происходит.

o Об обработке исключений будет рассказано в следующих главах рассылки. Если обработчик исключения не установлен, то по происхождению ошибки (например, деления на ноль) "Программа выполнит ошибку и будет закрыта". Эти биты чаще всего установлены.

§ #I - некорректная операция: #IS переполнение/антипереполнение стэка, #IA некорректная арифметическая операция

§ #D - Денормализованный операнд

§ #Z - Деление на ноль

§ #O - Переполнение числа

§ #U - Антипереполнение числа

§ #P - Округление

o 8-9 PC - контроль точности: 00 -24 бита, 01 - зарезервировано, 10 - 53 бита и 11 - 64 бита.

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

o 10-11 RC - контроль направления округления. 00 - к ближайшему числу, 01 - к минус бесконечности, 10 - к плюс бесконечности, 11 - к нолю (усечение).

o 12 X не используется, и присутствует для совместимости 287.

· Status Word (SW) - слово состояния

15	14	13-11	10	9	8	7	6	5	4	3	2	1	0
B	C 3	TOP	C 2	C 1	C 0	E S	S F	P E	U E	O E	Z E	D E	I E

· Значения бит слова состояния:

o 0-5 *E устанавливаются при возникновении соответствующих исключений.

o 6 SF устанавливается при ошибке работы со стэком

o 7 ES устанавливается при возникновении немаскированного исключения.

o 8,9,10,14 C* отображают результат операций сравнения и арифметических операций. Для организации ветвлений обычно использовалась последовательность команд fstsw ax / sahf, за которыми следовала команда условного перехода. Начиная с Pentium Pro, введены команды сравнения, непосредственно устанавливающие eflags. Их использовать предпочтительней.

o 11-13 TOP указывает на вершину стэка сопроцессора.

o 15 B не используется, оставлен для совместимости.

· Tag Word (TW) - слово тегов Слово, каждые два бита которого отображают тип информации в регистрах R0-R7. Т.е биты #0-1 отображают состояние R0, #2-3 - R1 и т.д.

· Каждая пара бит может принимать следующие значения:

· 00 - Действителен, 01 - Ноль, 10 - NaN, бесконечность, денормализованное или неподдерживаемое число, 11 - Пустой.

· TW модифицируется FPU автоматически, при восстановлении контекста используется только пустой / не пустой.

· Контекст сопроцессора содержит также адрес последней выполненной инструкции и ее операнда (селектор и смещение в 32 битном режиме) и 11 бит последней команды (старшие 5 бит заполнены нолями, а у инструкции они равны 11011b)

· R0-R7 8 десятибайтных регистров, образующих стэк FPU. Обращение к ним происходит по именам st(номер0-7) Номер относителен вершины стэка (SW.TOP).

Пример

Пример использования сопроцессора. Команды FPU используются в процедуре CalcXY, работу которой желательно посмотреть под отладчиком. Окно стэка сопроцессора отображается командой wf.

Программа - часы. Можно двигать удерживая левую кнопку мыши, выход - щелчок правой. Алгоритм работы более-менее стандартный:

После создания окна и т.д. установим таймер, который будет посылать сообщения WM_TIMER с заданным интервалом. Обработчик сообщения объявит недействительным содержимое окна, и WM_PAINT нарисует часы.

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

.486

.model flat,stdcall

;используем inc и lib файлы из пакета masm32 (с.м главу #8)

include c:\masm32\include\windows.inc

include c:\masm32\include\kernel32.inc

includelib c:\masm32\lib\kernel32.lib

include c:\masm32\include\user32.inc

includelib c:\masm32\lib\user32.lib

include c:\masm32\include\gdi32.inc

includelib c:\masm32\lib\gdi32.lib

;Константы для настройки программы

ClockX=61

ClockY=61

ClockColor=0FFFFFFh

BorderColor=0903030h

HourColor=0FF4040h

MinuteColor=0FFh

SecondColor=0

;Разница радиуса с максимальным

HourRadius=15

MinuteRadius=12

SecondRadius=5

.data

ColorArray dd HourColor,MinuteColor,SecondColor

RadiusArray dd HourRadius,MinuteRadius,SecondRadius

ProgramClassName db 'SmallClock',0 ;класс основного окошка

WinTitle db 'Clock',0

WClass WNDCLASSEX

MsgS MSG<>

DragCords dd ?

.code

;Процедура для вычисления координат точки на окружности,

; длинной MaxVal и определяемой прямоугольником EllipseRect

;Алгоритм работы:

; RadsLen=CurrentVal/MaxVal*2*PI

; XSize=EllppseRect.right-EllppseRect.left-1

; X=EllipseRect.left+XSize/2*(1+sin(RadsLen))

; YSize=EllipseRect.bottom-EllipseRect.top-1

; Y=EllipseRect.top+YSize/2*(1-cos(RadsLen))

;out: eax=x; edx=y

DivideBy2 real4 0.5 ;заменим деление на 2 умножением на 0.5.

;Это значительно быстрее. Об оптимизации будет рассказано позже.

CalcXY proc EllipseRect:ptr RECT,CurrentVal:DWORD,MaxVal:DWORD

mov ecx,[EllipseRect]

assume ecx:ptr RECT

fild [CurrentVal]

fidiv dword ptr [MaxVal]

fldpi

fmulp st(1),st(0)

fadd st(0),st(0) ;st(0)=RadsLen

fsincos

fild [ecx].bottom

fisub [ecx].top

fld1

fsub st(1),st(0)

fsubrp st(2),st(0)

fmulp st(1),st(0)

fmul [DivideBy2]

push edx

fistp dword ptr [esp]

pop edx

add edx,[ecx].top ;edx=y

fild [ecx].right

fisub [ecx].left

fld1

fsub st(1),st(0)

faddp st(2),st(0)

fmulp st(1),st(0)

fmul [DivideBy2]

push eax

fistp dword ptr [esp]

pop eax

add eax,[ecx].left ;eax=x

assume ecx:nothing

ret

CalcXY endp

;Макрос для уменьшения RECT'а со всех сторон.

;параметры: Rect - указатель на структуру RECT

; SubValue - значение, на которое нужно уменьшить RECT

SubRect macro Rect,SubValue

add [Rect].left,SubValue

add [Rect].top,SubValue

sub [Rect].right,SubValue

sub [Rect].bottom,SubValue

endm

start:

;зарегистрируем класс главного окна (см главу #7)

mov edi,offset WClass

assume edi:ptr WNDCLASSEX

invoke GetModuleHandle,0

mov [edi].hInstance,eax

invoke LoadIcon,0,IDI_APPLICATION

mov [edi].hIcon,eax

mov [edi].hIconSm,eax

invoke LoadCursor,0,IDC_ARROW

mov [edi].hCursor,eax

assume edi:nothing

invoke RegisterClassEx,edi

;Получим размер экрана для расположения окна по центру.

invoke GetSystemMetrics,SM_CXSCREEN

sub eax,ClockX

shr eax,1

xchg eax,ebx

invoke GetSystemMetrics,SM_CYSCREEN

sub eax,ClockY

shr eax,1

;создадим главное окно

invoke CreateWindowEx,WS_EX_TOOLWINDOW or WS_EX_TOPMOST,\

offset ProgramClassName,offset WinTitle,\

WS_VISIBLE or WS_POPUP,ebx,eax,ClockX,ClockY,\

0,0,[WClass.hInstance],0

xchg eax,ebx

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

invoke SetTimer,ebx,0,200,0

;создадим и установим регион для окна, чтобы окно было круглой формы.

invoke CreateEllipticRgn,-1,-1,ClockX+2,ClockY+2

invoke SetWindowRgn,ebx,eax,1

MsgLoop:

invoke GetMessage,offset MsgS,0,0,0

inc eax

jz EndMsgLoop

dec eax

jz EndMsgLoop

invoke TranslateMessage,offset MsgS

invoke DispatchMessage,offset MsgS

jmp MsgLoop

EndMsgLoop:

invoke ExitProcess,0

MainWindowProc proc hwnd:dword,uMsg:dword,wParam:dword,lParam: dword

local ps:PAINTSTRUCT

local ClientRect:RECT

local MemDC:dword

local CurrentTime:SYSTEMTIME

cmp [uMsg],WM_PAINT

jnz NotWmPaint

;обработчик WM_PAINT

invoke GetLocalTime,addr CurrentTime

invoke GetClientRect,[hwnd],addr ClientRect

invoke BeginPaint,[hwnd],addr ps

;создадим MemDC

invoke CreateCompatibleDC,ps.hdc

mov [MemDC],eax

invoke CreateCompatibleBitmap,ps.hdc,ClientRect.right,ClientRect.bottom

invoke SelectObject,[MemDC],eax

push eax ;хэндл предыдущего Bitmap

;нарисуем пустой циферблат

invoke CreateSolidBrush,ClockColor

invoke SelectObject,[MemDC],eax

push eax ;хэндл предыдущего Brush

invoke CreatePen,PS_SOLID,3,BorderColor

invoke SelectObject,[MemDC],eax

push eax ;хэндл предыдущего Pen

invoke Ellipse,[MemDC],0,0,ClientRect.right,ClientRect.bottom

;цикл рисования стрелок

push ebx

xor ebx,ebx

DrawClockLines:

mov eax,ebx

xor al,11b

invoke CreatePen,PS_SOLID,eax,dword ptr [ColorArray+ebx*4]

invoke SelectObject,[MemDC],eax

invoke DeleteObject,eax

invoke GetClientRect,[hwnd],addr ClientRect

mov eax,ClientRect.right

shr eax,1

mov ecx,ClientRect.bottom

shr ecx,1

invoke MoveToEx,[MemDC],eax,ecx,0

mov eax,dword ptr [RadiusArray+ebx*4]

SubRect ClientRect,eax

movzx eax,word ptr [CurrentTime.wHour+ebx*2]

or ebx,ebx

jnz NotDrawHour

lea ecx,[eax*4+eax] ;*5

movzx eax,word ptr [CurrentTime.wMinute]

cdq

push 12

div dword ptr [esp]

pop edx

add eax,ecx

NotDrawHour:

invoke CalcXY,addr ClientRect,eax,60

invoke LineTo,[MemDC],eax,edx

inc ebx

cmp bl,3

jnz DrawClockLines

pop ebx

invoke GetClientRect,[hwnd],addr ClientRect

invoke CreatePen,PS_SOLID,1,BorderColor

invoke SelectObject,[MemDC],eax

invoke DeleteObject,eax

;нарисуем метки времени (каждые 5 минут)

mov ecx,12

DrawTimeLabels:

push ecx

SubRect ClientRect,4

invoke CalcXY,addr ClientRect,dword ptr [esp+4],12

invoke MoveToEx,[MemDC],eax,edx,0

SubRect ClientRect,-4

invoke CalcXY,addr ClientRect,dword ptr [esp+4],12

invoke LineTo,[MemDC],eax,edx

pop ecx

loop DrawTimeLabels

;скопируем MemDC в DC окна

invoke BitBlt,ps.hdc,0,0,ClientRect.right,ClientRect.bottom,\

[MemDC],0,0,SRCCOPY

;удалим созданные объекты

push [MemDC]

call SelectObject ;2 pushed

invoke DeleteObject,eax

push [MemDC]

call SelectObject ;2 pushed

invoke DeleteObject,eax

push [MemDC]

call SelectObject ;2 pushed

invoke DeleteObject,eax

invoke DeleteDC,[MemDC]

invoke EndPaint,[hwnd],addr ps

xor eax,eax

ret

NotWmPaint:

cmp [uMsg],WM_TIMER

jnz NotWmTimer

;обработчик таймера. Все окно в Update Region

invoke InvalidateRect,[hwnd],0,0

xor eax,eax

ret

NotWmTimer:

;до WM_DESTROY - обработка сообщений от мыши

cmp [uMsg],WM_LBUTTONDOWN

jnz NotWmLButtonDown

mov eax,[lParam]

mov [DragCords],eax

invoke SetCapture,[hwnd]

jmp CallDefProc

NotWmLButtonDown:

cmp [uMsg],WM_LBUTTONUP

jnz NotWmLButtonUp

invoke ReleaseCapture

jmp CallDefProc

NotWmLButtonUp:

cmp [uMsg],WM_MOUSEMOVE

jnz NotWmMouseMove

cmp [wParam],MK_LBUTTON

jnz NotWmMouseMove

push eax

push eax

invoke GetCursorPos,esp

pop eax

movzx ecx,word ptr [DragCords]

sub eax,ecx

pop edx

movzx ecx,word ptr [DragCords+2]

sub edx,ecx

invoke SetWindowPos,[hwnd],0,eax,edx,0,0,SWP_NOSIZE

jmp CallDefProc

NotWmMouseMove:

cmp [uMsg],WM_RBUTTONUP

jz ExitFromClock

;стандартная часть процедуры обработки сообщений с.м главу #7.

cmp [uMsg],WM_DESTROY

jnz NotWmDestroy

ExitFromClock:

invoke PostQuitMessage,0

xor eax,eax

ret

NotWmDestroy:

CallDefProc:

invoke DefWindowProc,[hwnd],[uMsg],[wParam],[lParam]

ret

MainWindowProc endp

end start

2. Программы вычисления TG и ARCTG

число сопроцессор алгоритм ассемблерный

Алгоритмы CORDIC позволяют осуществлять:

- поворот вектора

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

- вычисление одновременно синуса и косинуса угла

- вычисление частичного арктангенса

- вычисление логарифма и экспоненты

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

Идея "поворотных" алгоритмов очень проста.

Поворот вектора (x, y) в декартовых координатах задается формулами:

x' = x*cos(alpha) - y*sin(alpha) = cos(alpha)*[x - y*tg(alpha)]

y' = x*sin(alpha) + y*cos(alpha) = cos(alpha)*[y + x*tg(alpha)]

Заменим теперь этот поворот совокупностью поворотов специального вида, иными словами, представим угол alpha в виде суммы:

inf -i

alpha = Sum { d(i) arctg(2) }, где d(i) = {+1, -1}

i=0

Оставим без доказательства тот факт, что надлежащим выборов знаков d(i) этот ряд сходится к любому наперед заданному углу в диапазоне примерно -98...+98 градусов.

Таким образом, учитывая, что tg[arctg(2)] = 2 (равносильно сдвигу вправо), искомый алгоритм запишется итеративной формулой:

theta = alpha

x[0] = x

y[0] = y

label:

x[i+1] = x[i] - sign(theta)*(y[i] >> i)

y[i+1] = y[i] + sign(theta)*(x[i] >> i)

theta -= sign(theta)*arctantable[i]

i++

goto label

Вы спросите - куда делся косинус, вынесенный в начале за скобки? Дело в том, что произведение inf -i C = П cos[arctg(2)] является константой, и по окончании итераций на него i=0 следует умножить результаты (имеющие размерность длины) единственный раз, т.е. в данном примере

x' = C*x[31]; y' = C*y[31].

Совершенно аналогично ищутся полярные координаты вектора (x, y), только в этом случае критерием является не sign(theta), а sign(y[i]). Когда y[i] станет близким к нулю, x[i] будет искомой длиной вектора, а суммарный угол поворота будет равен исходному. Не забудьте и в этом случае умножить x[i] на C.

Ниже приведены примеры ассемблерной реализации CORDIC.

; In procedures below the word 'pseudo' means the result is not scaled yet

.386p

COSCALE equ 4DBA76D2h

QUARTER equ 1 SHL 30

scale macro arg

xchg eax,arg

mov edx,COSCALE

imul edx

shld edx,eax,1

mov arg,edx

endm

a segment use16

assume cs:a, ds:a

org 100h

start:

mov esi,1 SHL 29

mov edi,0

mov edx,QUARTER SHR 1

call pseudorotate

scale esi

scale edi

call pseudopolarize

push edx

scale esi

pop edx

retn

; Subsequent pseudorotations

; x' = x - sign(theta)*(y>>i)

; y' = y + sign(theta)*(x>>i)

; x = esi, y = edi, theta = edx

cordic proc near

mov ebx,offset arctantab

mov cl,0

i_loop: or edx,edx ; or edi,edi \ modifying

jns posit_theta ; js posit_theta / code!

mov ebp,edi ; y

sar ebp,cl ; y>>i

add ebp,esi ; xtemp = x + y>>i

sar esi,cl ; x>>i

sub edi,esi ; y new = y - x>>i

mov esi,ebp ; x new = x + y>>i

add edx,[ebx]

add ebx,4

inc cl

cmp cl,28

jbe i_loop

retn

posit_theta: mov ebp,esi ; x

sar ebp,cl ; x>>i

add ebp,edi ; ytemp = y + x>>i

sar edi,cl ; y>>i

sub esi,edi ; x new = x - y>>i

mov edi,ebp ; y new = y + x>>i

sub edx,[ebx]

add ebx,4

inc cl

cmp cl,28

jbe i_loop

retn

cordic endp

; x=esi, y=edi, theta=edx

pseudorotate proc near

; Get angle within -QUARTER... +QUARTER

cmp edx,-QUARTER

jl conv_bounds

check_up: cmp edx,QUARTER

jng got_bounds

conv_bounds: neg esi

neg edi

add edx,2*QUARTER

got_bounds: mov word ptr cs:i_loop+2,79D2h

jmp cordic

pseudorotate endp

; Rotate vector (x,y) until its angle becomes 0, then x will be its length

; In: x = esi, y = edi

; Out: r = esi, theta = edx

pseudopolarize proc near

; Get the vector into the right half plane

xor edx,edx

or esi,esi

jns skip_x

neg esi

neg edi

mov edx,2*QUARTER

skip_x: mov word ptr cs:i_loop+2,78FFh

jmp cordic

pseudopolarize endp

arctantab:

dd 536870912, 316933406, 167458907, 85004756, 42667331, 21354465, 10679838,

5340245

dd 2670163, 1335087, 667544, 333772, 166886, 83443, 41722, 20861

dd 10430, 5215, 2608, 1304, 652, 326, 163, 81

dd 41, 20, 10, 5, 3, 1, 1, 0

a ends

end start

Список используемой литературы

Бэрри Н. Компьютерные сети. Пер. с англ. - М.: БИНОМ. - 1995. - 400 с.

Джамса К., Лалани С., Уикли С. Программирование в WWW для профессионалов. - Минск. - Попурри. - 1997. - 631 с.

Кент П. World Wide Web: Пер. с англ.. - М.: Компьютер. - 1996. - 311 с.

Кулаков Ю.А. Компьютерные сети. - Киев. - 1998. - 384 с.

Компьютерные сети. Принципы, технологии, протоколы / В.Г. Олифер, Н.А. Олифер. - СПб: Питер, 2001. - 672 с.

Максимов Н.В., Партыка Т.Л., Попов И.И. Технические средства информатизации: Учебник. - М.: ФОРУМ: ИНФРА-М, 2005. - 576 с.: ил. - (Профессиональное образование)

Милославская Н.Г., Толстой А.И. Интрасети: доступ в Internet. Защита: Учеб. пособие для вузов. - М.: ЮНИТИ - ДАНА, 2000 - 527 с.

Колесников Internet: для пользователя. - К.: Издательская группа BHV, 2000. - 304 с.

Новомлинский Л. Интернет-торговля. Часть 1// Сети и системы связи. 1998 - №8.

Новомлинский Л. Интернет-торговля. Часть 2// Сети и системы связи. 1998 - №9.

Пятибратов А.П. Вычислительные машины, сети и телекоммуникации/ Пятибратов А.П., Гудыно Л.П. - М.: Финансы и статистика. - 1998. - 400 с.

Сеть Internet. Применение в науке и бизнесе/ Горностаев Ю.М. и др. - М.: Россия - 1994. - 136 с.

Сеть Internet./ Горностаев Ю.М. и др. - М.: Россия. - 1993. - 88 с.

Сорокин Л. Аукционы в Интернате - будущее электронной коммерции // Мир электронной коммерции. - 2000. - №1.

Информатика: Учебник. - 3-е перераб. изд. / Под ред. проф. Н.В. Макаровой. - М.: Финансы и статистика, 2000. - 768 с.: ил.

Размещено на Allbest.ru