· Начало · Отвђтить · Статистика · Поиск · FAQ · Правила · Установки · Язык · Выход · WASM.RU · Noir.Ru ·

 WASM Phorum —› WASM.A&O —› Оптимизация Int_to_Str

Посл.отвђт Сообщен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