Geum.ru

Низкоуровневое программирование для Дzenствующих

Вид материалаДокументы

Содержание


Edmond / HI-TECH
СловоБредие Птицы летают, потому что мы ходим.
Подобный материал:
1   ...   26   27   28   29   30   31   32   33   ...   42





Edmond / HI-TECH

/\ & ()

(алгоритмы и оптимизация)

Извечное преобразование слов машины в слова людей


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

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

Многие из нас привыкли, что преобразование числа в строку осуществляется отдельной функцией. Да, с точки зрения достижение максимума скорости такой подход был бы верен, однако с точки зрения совершенства архитектуры – нет. Перед вами не сами функции перевода строки в число или наоборот. Сами по себе переводить они не могут, ибо не учитывают ошибок, которые могут быть допущены при конвертировании (а если учитывают, то список этих ошибок мал).
На основе этих элементарных контекстных функций могут быть основаны сложнейшие процедуры, начиная от банального перевода строк в числа и наоборот, заканчивая конвейерной обработкой данных в компиляторах ets. Интерфейсы этих функций построены таким образом, чтобы их было легко использовать как при преобразовании UNICODE, так и ANSI строк.
Вам предлагается оптимизировать их по скорости либо по размеру, соблюдая жёсткие рамки интерфейса на входе и выходе функций. Однако вы можете:
  1. Менять алгоритм
  2. По-другому переплетать код

Ваши предложения и примеры мы ждём на форуме ссылка скрыта. Либо, если по каким-то причинам вам не доступен форум, я буду рад вашим замечаниям по email Edmond@wasm.ru

Лучшие варианты по размеру и скорости будут опубликованы в качестве первых релизов проекта ULIB/TplOut в феврале 2004 года.

;; Модуль x_to_x

;; Базовая версия

;; (c) Edmond/HI-TECH


;; ####################### DATA #####################################

.data


CONSTANT_1999999Ah dd 1999999Ah

CONSTANT_1000000000 dd 1000000000

CONSTANT_10 dd 10

CONSTANT_5 dd 5


.code

;; ######################## CODE ####################################

;; FUN::ВСDInt32_to_Str

;;------------------------------

; CONV::ASMCALL

; FORMALS::

; int32 = ecx type:dword

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

; buffer = edi type:pointer

; - указатель на буфер, в который должна быть помещена строка.

; RET::

; Функция возвращает строку в буфер, и edi указывает на последнюю

; секцию символов, помещённые в буфер.

; Регистр ebx содержит последнюю секцию, помещённую в буфер.

;

; DPN::

; Элементарная функция, которая преобразовывает число

; в BCD строку

; в обратном виде (то есть от младшего разряда к старшему)

;------------------------------

; ALG:

Comment #

Функция делит число на 10, а остатоки от деления состовляют строку

Здесь функция имеет два цикла:

1. Большой цикл

2. Малый цикл

В малом цикле результат выполнения функции

накапливается в регистре ebx

И в конце цикла помещается в строку.

#

;; ==================================================================


Int_to_Str@@Div10 MACRO


;; %%%%%%%%%%%%%%%%%%%%%%%%%%

Comment #

Макро, который скрывает код для деления числа на 10

А так же код, который участвует в малом цикле

#

; USE:

; eax - текущее число для mul

; ebx - аккумулятор для собрания 4 символов строки

; ecx - число x

; edx - число x/10

;; %%%%%%%%%%%%%%%%%%%%%%%%%%


mul CONSTANT_1999999Ah

;; Сохранение результата для последующих операций

mov eax,edx

;; Умножение eax на 10

add eax,eax

lea eax,[eax+eax*4]

;; Получаем остаток в ecx

sub ecx,eax

;; Помещаем в eax следующее значение x/10,

;; которое хранилось в edx

mov eax,edx

;; результат в ebx

shrd ebx,ecx,8

;; Помещаем в ecx текущее число

mov ecx,eax


ENDM

;; ===========================================


BCDInt32_to_Str proc


;; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Comment #

::Алгоритм.

Функция выполняет последовательное деление

исходного числа на число 10.

Остатки при деление и есть десятичными разрядами числа.

::Особенности алгоритма

Деление выполняется при помощи умножения с переполнением.

#

; USE:

; eax - текущее число для mul

; ebx - аккумулятор для собрания 4 символов строки

; ecx - число x

; edx - число x/10

;; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


;; +++++++ Большой цикл +++++++++++++++++++++++++

ALIGN 16

@@:

mov eax,ecx

xor ebx,ebx

;;++++++++++++++++++++++++++++++++++++++++++++++++

comment /-------------

Точки входа BCDInt32_to_Str_xx существуют

для возможности использовать

данный код

более гибче в других функциях

---------------------/

BCDInt32_to_Str_1::

Int_to_Str@@Div10

BCDInt32_to_Str_2::

Int_to_Str@@Div10

BCDInt32_to_Str_3::

Int_to_Str@@Div10

BCDInt32_to_Str_4::

Int_to_Str@@Div10

;;++++++++++++++++++++++++++++++++++++++++++++++++

mov eax,ebx

;; (Если вы добавите эту строчку вы получите ASCII строку)

;; -- add eax,30303030h --

test ecx,ecx

stosd

jnz short @B

;; +++++++ Большой цикл +++++++++++++++++++++++++

ret

BCDInt32_to_Str endp

;; #############################################################


;; #############################################################

;; FUN::BCDInt64_to_Str

;;------------------------------

; CONV::ASMCALL

; FORMALS::

; int64 = edx:eax type:qword

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

; buffer = edi type:pointer

; - указатель на буфер, в который должна быть помещена строка.

; RET::

; Функция возвращает число в буфер, регистр edi указывает

; на последнию секцию

; символов, помещённые в буфер, а в регистре ebx -- их содержит.

; DPN::

; Элементарная функция, которая преобразовывает число int6

; 4 в BCD строку,

; в обратном виде (то есть от младшего разряда к старшему).

;------------------------------

; ALG:

Comment #

Функция разбивает 64-битное число на два,

и использует участки кода функции BCDInt32_to_Str для того,

чтобы преобразовать части числа.

Особенностью работы функции является запись 32 битного результата

в память.

Поскольку функция BCDInt32_to_Str возвращает результат выполнения

в регистре ebx и результат может не полностью помещатся

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

результат BCDInt32_to_Str продолжил заполнения этого регистра.

#

;; ==================================================================


BCDInt64_to_Str proc

;; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Comment #

#

; USE:

; all

;; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

;; 1. При помощи команды div CONSTANT_1000000000

;; нельзя делить числа

;; большие FFFFFFFFFFFFF, поэтому это следует учесть.

test edx,0f0000000h

jnz @F

;; 2. В том случае, если условие не выполнилось,

;; число можно разделить при помощи

;; Одной команды DIV

start:

div CONSTANT_1000000000

push eax

mov ecx,edx

call BCDInt32_to_Str

;; 3. !!!

;; После вызова этой функции, регистр ebx хранит последние

;; помещённые в память

;; четыре байта. При этом доказано, что какое бы на входе

;; ни было число,

;; ebx заполнен только младшим разрядом, то есть,

;; ebx = 000000xxh

;; Таким образом, чтобы последующие числа не были разорваны нулями

;; мы корректируем ebx, так, как будто уже выполнился

;; первая часть кода в BCDInt32_to_Str

;; И передаём управление не на начало процедуры BCDInt32_to_Str

;; а на BCDInt32_to_Str_2

;; Эти операции выполняет код

;; Помещаем старшую числа для преобразования

pop ecx

sub edi,4 ;; Уменьшаем edi,

;; чтобы число записалось вместо старого

mov eax,ecx

ror ebx,8

;; Я делаю jmp вместо call, и управление вернётся к функции,

;; которая вызвала данную

jmp BCDInt32_to_Str_2


;; 4. В том случае, если число больше значения FFFFFFFFFFFFF

;; Алгоритм усложняется

;; 4.1 Сперва мы покомпонентно делим число на 1000000000

@@: mov ecx,eax

mov eax,edx

xor edx,edx

div CONSTANT_1000000000

;; После этой команды в eax - остаётся самый старший разряд числа

;; Мы сохраняем его в стеке, так как он понадобится позднее.

push eax

xchg ecx,eax

div CONSTANT_1000000000

;; 4.2 После этой команды, в регистре edx окажется младшая

;; часть числа,

;; которую можно перевести в строку функцией BCDInt32_to_Str


;; Сохраняем старшую часть

push eax

;; В ecx - параметр функции

mov ecx,edx

call BCDInt32_to_Str

;; 4.3 Восстанавливаем из стека сохранённые части 64-bits числа

;; в edx:eax

pop eax

pop edx

div CONSTANT_1000000000

;; 4.4 Аналогично, теперь мы имеем разбитое на две части число.

;; Старшуй часть, которая в eax, сохраняем на потом,

;; а младшую (edx), переводим

;; в строку.

push eax

Comment /------------------

Пара команд

sub edi,4

ror ebx,8

Находятся здесь потому как они корректируют контекст

после выполнения функции BCDInt32_to_Str.

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

ebx заполняется только младшим разрядом. ebx = 000000xxh

Чтобы строка BCD не разделялась нулями, которых нет,

мы корректируем значения ebx и edi, и вызываем выполнение

с точки входа BCDInt32_to_Str_2

-------------------/

sub edi,4

mov ecx,edx

mov eax,edx

ror ebx,8

call BCDInt32_to_Str_2

Comment /------------------

Пара команд

sub edi,4

shl ebx,16

Находятся здесь потому, так как они корректируют контекст

после выполнения функции BCDInt32_to_Str_2.

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

ebx заполняется только двумя младшими байтами: ebx = 0000xxxxh.

Чтобы строка BCD не разделялась нулями, которых нет,

мы корректируем значения ebx и edi, и вызываем выполнение

с точки входа BCDInt32_to_Str_3

-------------------/


;; Помещаем старшую числа для преобразования

pop ecx

;; Уменьшаем edi

sub edi,4

;; Контекст для точки вызова

mov eax,ecx

shl ebx,16

;; после этого ebx = xxxx0000h

;; Я делаю jmp вместо call, и управление вернётся к функции, которая

;; вызвала данную

jmp BCDInt32_to_Str_3

BCDInt64_to_Str endp

;; ##################################################################


;; Варианты функций для непроверенной не BCD строки

IF not CM$__string_check


;; ##################################################################

;; FUN::Str_to_Int32

;;------------------------------

; CONV::ASMCALL

; FORMALS::

; pbuffer = esi type:offset buffser

; - буффер строки ASCII заканчивающийся нулём

; RET::

; int32 = edx

; - число

; errcode = eax

; - код ошибки. Если ошибок не было errcode = 0

; pbuffer = esi

; - указывает на последний символ,

; который был прочитан функцией.

; DPN::

; Функция конвертирует строку ASCII в число int32. В случае

; ошибки, функция возвращает ненулевое значение в eax, которое

; равно символу, не соответствующиму ASCII цифрам.

; Таким образом, не обязательно, чтобы строка завершалась нулём.

; Но вызвавшая функция сама должна оценить ситуацию.

;

;------------------------------

; ALG:

Comment # Алгоритм

Функция считывает каждый символ из строки.

Преобразовывает ASCII символ в BCD (ASCII-30)

и запоминает его (edx).

При каждом следующем считывании она

увеличивает запомненное число на 10,

и прибавляет к нему новое, взятое из строки.

#

;; ==================================================================

Str_to_Int32 proc

;; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Comment #

#

; USE:

; eax, edx

;; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

xor eax,eax

xor edx,edx


ALIGN 16

@@: ; ------- Цикл ------------

lodsb

sub al,30h

;; Если меньше -- конец

jb short @F

cmp al,9

ja short @F

lea edx,[edx+edx*4]

lea edx,[eax+edx*2]

jmp short @B

@@:

add al,30h

ret

Str_to_Int32 endp

;; ##################################################################


;; ##################################################################

;; FUN::Str_to_Int64

;;------------------------------

; CONV::ASMCALL

; FORMALS::

; buffer = esi type:pointer

; - указатель на строку, заканчивающююся нулём.

; RET::

; int64 = edx:eax

; - число

; ecx - Последний символ, обработанный функцией

; esi - Указатель на последний символ,

; обработанный функцией

; DPN::

; Функция преобразовывает строку в INT64 число.

;;------------------------------

; ALG:

Comment # Алгоритм

Перевод осуществляется в два этапа.

Сперва переводится в число старшая часть числа

После младшая

И в конце результат корректируется.


Основная идея разделения перевода строки в 64 число,

состоит в следующем:

1. Мы переводим строку в число, пока число

не превысит крайнего значения 32-bits

2. Результат запоминается

3. Переводится оставшая (младшая) часть числа,

и при этом подсчитывается количество

разрядов, вошедшее в это число.

4. Основываясь на колличестве разрядов,

старшая половина корректируется

и суммируется с младшей частью.

#

;; ==================================================================

Str_to_Int64 proc

;; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Comment #

#

; USE:

; eax,edx,ecx

;; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

xor eax,eax

xor edx,edx

mov ecx,eax

;; ECX будет содержать число 10*n,

;; где n - число разрядров прошедших к анализу.

inc ecx

ALIGN 16

@@: ; ------- Цикл ------------

lodsb

sub al,30h

;; Если меньше -- конец

jb short endproc

cmp al,9

ja short endproc

lea edx,[edx+edx*4]

lea edx,[eax+edx*2]

;; Если сумматор превысит это значение,

;; значит преобразование старшей части завершено

Str_to_Int64_next::


;; ffffffffh/ah = 19999999h

cmp edx,19999999h

jna @B

@@:

;; Когда закончилось преобразование

;; старшей части запоминаем её в стеке

push edx

xor edx,edx

@@: ; ------- Цикл ------------

lodsb

sub al,30h

;; Если меньше -- конец

jb short @F

cmp al,9

ja short @F


shl ecx,1

;; edx = edx*10+eax

lea edx,[edx+edx*4]

lea edx,[eax+edx*2]

;; ecx = ecx*10 (shl ecx, 1 уже была выше)

lea ecx,[ecx+ecx*4]

;; Следует следить за тем, чтобы сумматор множетеля разрядности

;; не переполнился

cmp ecx,1000000000

jae short above_19999999h

jmp @B


@@:

;; Преобразование младшей части закончено.

;; В стеке была сохранена старшая часть числа

;; Помещаем её в eax.

pop eax


;; Процедура корректирования результата преобразований

;; младшей и старшей части.

Str_to_Int64_correct::

correct:


;; Контекст

;; eax - старшая часть числа

;; edx - младшая часть числа

;; ecx - множитель


;; 1. Сохраняем в стеке младшую часть.

push edx

mul ecx

;; После этой команды в edx:eax хранится 64-bits число

;; Теперь к нему нужно прибавить оставшуюся часть результата,

;; которая находится в стеке

pop ecx

;; edx:eax = edx:eax+ecx

add eax,ecx

adc edx,0

;; Последний символ возвращается в cl

xor ecx,ecx

mov cl, byte ptr [esi-1]

ret


above_19999999h:

;; Управление приходит сюда, только в том случае,

;; если число слишком

;; большое для команд lea и поэтому нужно воспользоваться

;; другим алгоритмом.

;; Контекст:

;; edx - содержит текущее число, которое больше, чем 19999999h

;; ecx - содержит число переведённых разрядов

;; в стеке лежит старшая часть числа.

;; Поскольку теперь уже всё равно придётся иметь дело

;; с умножением 64 битного

;; числа, мы делаем приведение


pop eax ;; eax = старшая часть числа

call correct

;; Теперь edx:eax - содержат 64-bits текущее число.


mov ecx,eax

;; Прибавляем последний разряд

xor eax,eax

lodsb

sub al,30h

;; Если меньше -- конец

jb short @F

cmp al,9

ja short @F


;; старшая часть числа * 10

;; младшая * 10

push eax

mov eax,ecx

mov ecx,edx

shl ecx,1

mul CONSTANT_10

lea ecx,[ecx+ecx*4]

add edx,ecx

pop ecx

;; edx:eax = edx:eax + ecx (ecx = последний символ - 30h)

add eax,ecx

adc edx,0

;; Преобразование законченно

xor ecx,ecx

mov cl,[esi]

inc esi

ret


;; Управление приходит на эту метку,

;; если мы вернулись при преобразовании последнего символа

@@:

add al,30h

xchg ecx,eax

ret

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

endproc:

xor eax,eax

mov al,byte ptr [esi-1]

mov ecx,eax

mov eax,edx

xor edx,edx

ret

Str_to_Int64 endp

;; ##################################################################


 

# СловоБредие

Птицы летают, потому что мы ходим.


Помните монолог в «Грозе»: «А почему люди не летают?» А глупый это вопрос. Я так вам скажу: «Если бы люди летали, они бы думали, что ходят». Человек – такое существо, не умеющее ценить то, что у него есть. Вот и возникают вопросы вроде: «А почему люди не птицы?». Я бы так сказал: «Научитесь сперва ходить, а потом за крылья беритесь». Да нет же. Спрашивается, чего человеку не хватает? Крыльев что ли?

Вот и началось это всё воздухоплавание ?

К чему это я? Гм…. Мистика. Завтра буря магнитная будет. Говорят связь сдохнет, болезни прорежутся, порча напортится, сглаз сгладится, и вообще. Мракобесие. Интернет упадёт, и не только он. Ой, горе то какое!!! Свят, свят.. Тфу, тфу, тфу через плечё, как бы не случилось чё.

А у меня ещё недавно примус сломался. Теперь гренки жарить не на чем. А как это я утром без гренок!!! Вот телефончик добрые люди дали с WASM, какой-то там xzazet примусы чинит. Где-то я уже это имя слышал. А ещё программисты рассказывают, что в эхе TNX (кажется) есть этот, как его… - забыл. Имя такое на языке верится, а не скажешь. Как то на В… В… Владимир Путин? Нет… Но тоже страшный такой…. Он ещё что-то про подсолнечное масло рассказывал…. Вот я и говорю Магнитные бури, тёмные пятна…. ЧЕРТОВЩИНА КАКАЯ-ТО!!!!!



* * *
(продолжение)

Родился, значит, у Александра Санька. Сан Саныч, внук камердинера. Отличный парень рос. Добрый, послушный, в общем радость родителям, гордость деду. Только малость странный парнишка - задумчивый больно. Сидит, бывало, по часу, и все о чем-то думает, как вспоминает что. Ну, дети, они разные ведь - может и пройдет с возрастом, а может, качество какое развивается.

Ну, значит, стукнуло ему шесть лет. День рождения. Отец и матерью задумали подарок сделать. Ну, отец так исподволь, ненавязчиво к сыну - о чем, мол, мечтаешь? Может, там водителем хочешь быть, или пожарником? Ну, под игру подводит, вдруг сын заветное выскажет. А Шурка-малый и скажи: "Хочу, папа, шар биллиардный. Круглый, белый". Ну, отец вспомнил, что в воскресенье с дружком по работе свиделся, а тот и похвастайся, какой в районном клубе отдыха биллиард поставили, с шарами красивыми. Малый под рукой был, разговор слыхал. Вот, чудит теперь. Ну да пусть.

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

Через год - Шурку в школу. Тут его усидчивость и проявилась. Отличник стал. Что ни день - пятерку тащит. Учителя в радости, способный ученик, хороший такой. Математику любил очень. Попозже стал в библиотеку ходить, учебники с книгами читать. Знания - как вода в сухой песок, все в голову льется. Стали его, значит, как школьную гордость показывать, карточку фотографическую на доску почета повесили, почетным звеньевым в классе сделался. На олимпиадах места первые, призовые получал. Родители не нарадуются, дед особенно счастлив - вот, не зря бар да господ на корню вывели, смену вот настоящую, рабоче-крестьянскую растим.

Победил Шурка на олимпиаде республиканской. Школу-то он раньше срока закончил. Слово модное появилось - вундеркинд. Еще только Саньке 14, а его уж в университет зовут, профессура за ним вьется, мол, науку вперет не то что семимимильными шагами, а бегом просто, никакая заграница не угонится. Да и Шурка повзрослел быстро.

Ну, отец - передовик производства, фронтовик, дед-революционер, льготники, решили значит, один ему машину взять, без очереди (себе держал, под старость), а второй-квартиру переписать (дети призрят, а внуку - радость). Ну, а мать, значит, выяснить решила, что сын хочет - может, по миру поездить, на иностранные государства посмотреть, или еще что. Гений, прямо сказать, натура загадочная, чтоб не вышло чего. Ну вот к сыну мама и подходит с вопросом. Что ж, сын, хорошо-то все, а ты все думаешь о чем-то. Или печалишься может? Или нехватает чего? Сан Саныч сразу маму успокаивает, отлично все, мама, вот, безделицы сущей нет, да только голову себе не забивайте. Как безделицы? Говори - тебе звезду с неба завсегда пожалста.

Ну тут Шурик-то и выдал.

(продолжение следует...)