|
|
| Посл.отвђт | Сообщенiе |
|
|
Дата: Сен 3, 2003 17:45:29 Предлагаю на растерзание эту функцию, а точнее две функции. В принципе приветсвуются обе оптимизации 1. По размеру 2. По скорости. Но ОБЯЗАТЕЛЬНОЕ УСЛОВИЕ -- ВЫХОДНЫЕ И ВХОДНЫЕ ДАННЫЕ не изменяются |
|
|
Дата: Сен 3, 2003 17:46:56 · Поправил: Edmond Лучший результат попадёт в спец проект ULIB, который появистя в феврале. Код: ================================================ .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:: ; Элементарная функция, которая преобразовывает число int64 в 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 ;; Помещаем старшую числа для преобразования sub edi,4 ;; Уменьшаем edi mov eax,ecx ;; Контекст для точки вызова shl ebx,16 ;; после этого ebx = xxxx0000h ;; Я делаю jmp вместо call, и управление вернётся к функции, которая ;; вызвала данную jmp BCDInt32_to_Str_3 BCDInt64_to_Str endp ;; ########################################################## ================================================ |
|
|
Дата: Сен 3, 2003 18:43:29 И что, вся эта груда кода только и делает, что число в строку переводит? 8-0 |
|
|
Дата: Сен 3, 2003 18:48:08 masquer Почему груда??? Там просто комментов много. И вовторых тут ДВЕ ФУНКЦИИ В третих не строку а в BCD вариант. Это так называемые функции низкого уровня. Полуфабрикаты для других функций. |
|
|
Дата: Сен 3, 2003 18:51:54 masquer Ой, я ошибся, и :)))))))))))) И по ошибке поместил все функции %))) |
|
|
Дата: Сен 4, 2003 11:03:43 Дополнение Перед вами код четырёх функций преобразования. Это не просто функции, а так называемые Элементарные контекстные функции. Многие из нас привыкли, что преобразование числа в строку осуществляется отдельной функцией. Да, с точки зрения достижение максимума скорости такой подход был бы верен, однако с точки зрения совершенства архитектуры – нет. Перед вами не сами функции перевода строки в число или наоборот. Сами по себе переводить они не могут, ибо не учитывают ошибок, которые могут быть допущены при конвертировании (а если учитывают, то список этих ошибок мал). На основе этих элементарных контекстных функций могут быть основаны сложнейшие процедуры, начиная от банального перевода строк в числа и наоборот, заканчивая конвейерной обработкой данных в компиляторах ets. Интерфейсы этих функций построены таким образом, чтобы их было легко использовать как при преобразовании UNICODE, так и ANSI строк. Вам предлагается оптимизировать их по скорости либо по размеру, соблюдая жёсткие рамки интерфейса на входе и выходе функций. Однако вы можете: 1. Менять алгоритм 2. По-другому переплетать код В принципе интерфейс тоже можно изменить, если это позволяет улучшить производительность. ========================== Ошибки. Ошибоки не проверяются потому что их не нужно проверять. Это низшие функции, которыми пользуются шаблонизаторы, компиляторы. Там эти проверки осуществляются задолго ДО преобразовния. То есть тут нужно оптимизировать сами функции, оставляя суть входа. Хотя бы его. ОК, выход можно менять. |
|
|
Дата: Сен 9, 2003 00:51:43 · Поправил: Black_mirror
eaxtostr:;(eax - num, edi-str)
push 10 ;2
pop ecx ;1
push -'0' ;2
.l0:
xor edx,edx ;2
div ecx ;2
push edx ;1
test eax,eax ;2
jnz .l0 ;2
.l1:
pop eax ;1
add al,'0' ;2
stosb ;1
jnz .l1 ;2
ret ;1
После символов числа записывает нуль, edi указывает на байт, следующий после нуля. Разрушает ecx. Кто уложится в 20 байт? Или в 21, но чтоб edi указывал на символ сразу за числом? |
|
|
Дата: Сен 9, 2003 02:21:11 · Поправил: Black_mirror А вот для 64х-битного числа. 27 байт.
eaxebxtostr:;(eax:ebx - num, edi - str)
push 10 ;2
pop ecx ;1
push -'0' ;2
.l0:
xor edx,edx ;2
div ecx ;2
xchg eax,ebx ;1
div ecx ;2
xchg eax,ebx ;1
push edx ;1
mov edx,ebx ;2
or edx,eax ;2
jnz .l0 ;2
.l1:
pop eax ;1
add al,'0' ;2
stosb ;1
jnz .l1 ;2
; dec edi ;1
ret ;1
|
|
|
Дата: Сен 9, 2003 18:03:32 Black_mirror Супер!!!! Беру исходники в Либу!!! (Копирайты твои естественно) |
|
|
Дата: Сен 9, 2003 18:08:32 Кто уложится в 20 байт? Или в 21, но чтоб edi указывал на символ сразу за числом? Нууу, не знаю. Попробывать всегда можно. |
|
|
Дата: Сен 9, 2003 18:21:54 Нууу, не знаю. Попробывать всегда можно. Вчера прочитал Историю одного байта и вспомнил главную теорему оптимизации: В любой программе есть по крайней мере один лишний байт. |
|
|
Дата: Апр 7, 2004 19:01:45 · Поправил: volodya В одном моем здоровенном проекте на С++ я вынужден выполнять огромное множество преобразований integer to ascii. Преобразования выполняются в десятеричной системе счисления над беззнаковыми integers. Ясно, что STL-функции преобразования всего лишь являются надстройками над CRT -> медленно. Посмотрев код CRT, увидел, что тоже медленно. Вот мой результат: #include <string>
#include <iostream>
using namespace std;
string uitoa(int n)
{
char p[90];
char *sStr = p, *eStr;
unsigned int j = 0;
do
{
p[j++] = n%10 + '0';
} while ((n /= 10) > 0);
p[j] = '\0';
j--;
eStr = sStr + j;
for ( ; sStr < eStr; sStr++, eStr-- )
{
*sStr ^= *eStr;
*eStr ^= *sStr;
*sStr ^= *eStr;
}
string s = p;
return s;
}
void main()
{
cout << uitoa(348) << endl;
cout << uitoa(65457874) << endl;
cout << uitoa(45788) << endl;
cout << uitoa(9858782) << endl;
}
Предвидя некоторые возражения по поводу string s = p; return s; спешу сказать, что иначе, видимо, мне string вернуть не получится. Да, два раза происходит вызов конструктора, ну а что делать? |
|
Powered by miniBB 1.6 © 2001-2002
Время загрузки страницы (сек.): 0.065 |