А как выглядит наиболее изящный алгоритм перевода цел. числа в строку?

Я обычно использую вот это:

num2string proc string:dword;принимает адрес строки
;число в eax
;в edx возвращает длину строки
xor ecx,ecx
lea edi,[ecx+10]
@ufgk:
inc ecx
xor edx,edx
div edi
add edx,'0'
push edx
test eax,eax
jnz @ufgk
@kuyf:
cld
mov edi,string;адрес строки с числом
mov edx,ecx
@kjgf:
pop eax
stosb
loop @kjgf
ret
num2string endp

 

del

 

FASM:

Код (Text):

1. .data
2.  
3.     text_buffer rb 15
4.     null_terminator db 0
5.  
6. .code
7.  
8. ;
9. ; INPUT:
10. ;   EAX = value to convert
11. ; OUTPUT:
12. ;   EDI = pointer to null-terminated string value
13. ;
14. UInt32toASCII:
15.     push    10
16.     pop ecx
17.  
18.     mov edi, null_terminator
19.  
20. @@:
21.     xor edx, edx
22.     div ecx
23.  
24.     add dl, '0'
25.     dec edi
26.     mov [edi], dl
27.  
28.     test    eax, eax
29.     jnz @r
30.  
31.     ret

 

А там случайно не lea вместо mov edi, null_terminator?

 

Нет там mov.
Написали же - это fasm.

Код (Text):

1. mov edi, null_terminator

- занести в edi адрес null_terminator.
Тоже что

Код (Text):

1. mov edi,offset null_terminator

в masm/tasm.
А значение переменной читается так:

Код (Text):

1. mov edi, [null_terminator]

 

user32!wsprintfA хорошая вещь

а вообще, маскимум 10 итераций(цифр) - можно развернуть цикл.
И заменить деление на 10 умножением. Может есть смысл подумать об умножении на (2^32/10^9), чтобы старшая цифра выравнивалась по двоичной сетке разрядов и вылезала в верхние 32разряда:
x=(a9*10^9+a8*10^8+...)
a9=x*(2^32/10^9)

 

Удобная потому что уже сделана M$ но до изящества ей далеко....
http://www.wasm.ru/forum/viewtopic.php?id=18476

 

ещё такой вариант:

Код (Text):

1. ;eax - value
2. ;string - нульзавершённая строка
3. lea edi,[string+4]
4. mov ecx,10
5. xor edx,edx
6. xor ebx,ebx
7. @conv:div  ecx
8.           shld [edi],ebx,8
9.           shl  ebx,8  
10.           add  dl,48
11.           xchg bl,dl
12.           test eax,eax
13. jne @conv
14. mov  [edi-4],ebx

правда ограничение по длине числа - 8 десятичных знаков.

 

Перевод беззнакового целого в строку без деления.

Код (Text):

1. mov ecx,Value
2. mov edi,S
3. xor ebx,ebx
4. xor esi,esi
5. @conv:mov  edx,3435973837
6.       mov  eax,ecx
7.       mul  edx
8.       shr  edx,3
9.       lea  eax,[edx*8+edx-48]
10.       add  eax,edx
11.       sub  ecx,eax
12.       shld [edi+8],esi,8
13.       shld esi,ebx,8
14.       shl  ebx,8
15.       xchg bl,cl
16.       add  ecx,edx
17. jne @conv
18. mov  [edi],ebx
19. mov  [edi+4],esi

 

murder
в ~2,5 раза тормознее этого
и не всегда удобно что незвестен адрес конца полученной строки для дописывания в неё.

 

Хм.. вроде тоже самое, но строка записывается в обратном порядке а потом переворачивается в отдельном цикле.

Добавлено:
моя версия ~ 1150000 тиков
версия IceStudent ~ 1050000 тиков
версия AsmGuru62 ~ 3840000 тиков
версия Proteus ~ 4400000 тиков
версия AMD ~ 590000 тиков
Delphi str ~ 4940000 тиков
версия Ravager ~ 4360000 тиков

Тестировал на числе 123456789, 10000 итераций + один вызов для вывода результата теста.

 

В коде IceStudent заменил строки

Код (Text):

1. lea edx,[edx*4+edx]
2. add edx,edx
3. sub ebx,edx
4. add bl,'0'

на следующее

Код (Text):

1. lea edx,[edx*4+edx-24]
2. add edx,edx
3. sub ebx,edx

время сократилось с ~1050000 до ~810000 (22% прирост)

У себя за менил pushad/popad на push/pop edi,esi,ebx (как у IceStudent).
время сократилось с ~1150000 до ~1120000 (2% прирост)

 

Сорсы с алгоритмом замера дайте плиз, проверить хочется на своей машине.

 

airyashov
зайди по ссылке в #7

murder
странно, а меня твой (до исправления) ~1900, а IceStudent ~800
Тестирую на 1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 0FFFFFFFEh
Время для всей последовательности, по 3 повтора (используется последний стабилизировавшийся замер).
(AMD Turion x2)
А ты первый\второй сверхтормозные проходы выбрасывать не забываешь?
И кстати 10000 повторов сильно повышают вероятность попасть на переключение задачи.
Leo всё это популярно объяснял, но линк где с ходу не нашёлся.

 

Вот исходник с 7 методами. Процедура int2strDAO - это оптимизированая версия процедуры IceStudent. Мне кажется, что у неё ещё есть неплохой потенциал для разгона.

Очень странно, но AMD-шная процедура выдаёт почти одинаковые результаты на Athlon XP 2500+ и Athlon X2 3800+, в то время как остальные процедуры работают медленнее на первом процессоре.

Прошу прощения за Делфи.

 

Мне тут в голову только что пришла бредовая идея =)

а что, если забацать вставку по таблице?
т.е. можно создать таблицу, в которой заранее будут в посимвольном представлении (если точнее, поразрядном: один десятичный разряд = один символ) прописаны числа от 1 до F, от 10 до F0, от 100 до F00 итд, т.е. всего 8*16 = 128 элементов. Затем, из "исходного" числа будет изыматься по 1 НЕХ-разряду за проход, и в соответствии с номером разряда, строка символов числа будет складываться побайтно с извлечённой из таблицы, примерно так:

Код (Text):

1. 0FEDBCAh = 16702650
2.  
3.                    1  0  | Ah
4.                 1  7  6  | B0h
5.    +         3  0  7  2  | C00h
6.           5  3  2  4  8  | D000h
7.        9  1  7  5  0  4  | E0000h
8.  1  5  7  2  8  6  4  0  | F00000h
9. ———————————————————————  |
10. 01 05 16 08 21 14 23 20  | <-- результат

В итоге должна получиться строка из байтов (на схеме - "результат").
Проходимся по ним командой ААМ - и она преобразует 2-значное число в его десятичное представление.
Пишем на место него младшую цифру (регистр AL), а АН складываем с предыдущим числом. Повторяем ААМ.

Затем складываем результат с паттерном символа "0" - и у нас есть готовое число!

[+]: Сомневаюсь конечно, что это будет быстрее чем предложенные здесь варианты, однако чем чёрт не шутит =)
Окажется быстрее - выложу реализацию.
*ушёл медитировать на код*

 

Перевод знакового целого в строку с FPU.

Код (Text):

1. int2a   proc    Val:DWORD,lpString:DWORD
2. LOCAL   BCD:TBYTE
3.     fild    [Val]
4.     fbstp   [BCD]
5.     lea     esi,    [BCD+10-2-4]
6.     mov     edi,    [lpString]
7.     mov     ecx,    5
8.     .if byte ptr[esi+1+4]
9.         mov byte ptr[edi],'-'
10.         inc edi
11.     .endif
12. @@:
13.     xor     eax,    eax
14.     mov     al,     [esi]
15.     dec     esi
16.     shl     ax,     4
17.     rol     al,     4
18.     or      ax,     '00'
19.     xchg    ah,     al
20.     mov     [edi],  ax
21.     add     edi,    2
22.     dec ecx
23.     jnz @B
24.     mov     byte ptr[edi],0
25.     ret
26. int2a endp

Duron 800:
int2a ~255506 тиков на 1000 повторов
int2strAMD ~76518 тиков на 1000 повторов

 

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

murder
int2strAsmGuru62 написана с ошибкой

S_Alex
fpu тут явно скорости не пребавляет

 

DEEP
Если изымать по 2 HEX-разряда, то будет в 2 раза меньше работы, но и размер таблицы возрастёт в 16 раз. Если сложение выполнять на MMX можно получить быстрый метод.

airyashov

Ну и хрен с ней.

Инструкция fbstp довольно шустро работает, но на дальнейшую распаковку Packed BCD числа уходит уйма времени.


Либо идея с AAM и таблицами тупая, либо я тупой.

 

murder:

Идея с таблицами обычно хороша в плане оптимизации по скорости, пока они за пределы кэша не вылезают.

Так что можно её ещё расширить, добавив таблицу с готовыми строками для нескольких первых значений (скажем, от 0 до 64K). Потом навесить на это таблицу со строковой арифметикой, чтобы частичные результаты в столбик складывать (с учётом переполнения):
'0' + '0' + 0 = (0) '0'
'0' + '0' + 1 = (0) '1'
'0' + '1' + 0 = (0) '1'
...
'9' + '9' + 0 = (1) '8'
'9' + '9' + 1 = (1) '9'

В общем, есть где развернуться, если бы в этом был смысл


ПС: А ещё можно по размеру кода оптимизировать, используя какую-нибудь готовую функцию Биоса (потому что привязываться к ОС неуниверсально.