Перевод байта в десятичную строку.

Уважаемые теоретики/оптимизаторы! Не подскажете ли что путное по сабжу?

Имеется, допустим, 0xFE(число в регистре), нужно получить '254',0.

Все что мне в голову приходит выглядит чересчур тяжеловесным, вот к примеру

Код (Text):

1.         xor edx, edx
2.         mov bl, 10
3.         movzx ax, Number
4.  
5.         div bl
6.         xchg ah, dl
7.         rol edx, 8
8.         div bl
9.         xchg ah, dl
10.         rol edx, 8
11.         mov dl, al
12.         add edx, 303030h
13.  
14.         mov eax, DecString
15.         mov [eax], edx

Наверняка есть способ умнее...

 

если число не больше байта, то самый короткий способ деления на 10 выглядит как AAM. Т.е. помещаешь в AL свое число, делаешь AAM и в результате имеешь в AL остаток от деления на 10. Теперь остается присобачить это к общему алгоритму

 

А вот так не подойдет )



mov ecx, 0feh

mov ebx, 303030h

@@loop:

inc bl

cmp bl, 3Ah

jnz @f

and bl, 0F0h

inc bh

cmp bh, 3Ah

jnz @f

and bh, 0F0h

add ebx, 10000h

@@:

loop @@lop

 

Если важна скорость, то в данном случае можно использовать табличку - "всего-то" 256*4 байт.

Заполнить например так:

Код (Text):

1.  
2. dummy   dd      0
3. table   rd      256
4.  
5. build_table:
6.         xor     eax, eax
7.         xor     edx, edx
8. .l:     lea     ecx, [eax+303030h]
9.         bswap   ecx
10.         mov     [edx*4+table-1], ecx
11.         inc     eax
12.         aaa
13.         cmp     ah, 10
14.         jc      @f
15.         add     eax, 0F600h
16.  @@:    inc     dl
17.         jnz     .l

Зато преобразование - одной командой

Код (Text):

1.  
2.         mov     eax, [eax*4+table]

(можно сократить таблицу в 2 раза, если хранить только чётные числа)



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

 

Broken Sword

Действительно, AAM - самый короткий способ деления на 10. Но это тоже самое деление, только специализированное. Поэтому код будет изящнее, но по скорости выигрыш не значительный (по Фогу для P3: AAM 15 тактов против 19 для DIV r8, а для P4 56 против 60).



_Juicy

> "Наверняка есть способ умнее..."

Если оптимизировать быстродействие, то можно поизвращаться.

К примеру, использовать поразрядное уравновешивание с весами Wi = 100,100,50,20,10,10.

Одно сравнение выглядит так:

Код (Text):

1. Вариант 1 (поразрядное прибавление):
2.     ;mov bl,30h
3.     cmp al,Wi
4.     setb dl
5.     sub dl,1
6.     and dl,Mi ;маска для 50: -5 = FBh, для 20: -2 = FEh, для остальных FFh, т.е. можно исключить
7.     sub bl,dl
8.     and dl,Wi
9.     sub al,dl
10.  
11. Вариант 2: (поразрядное вычитание)
12.     ;mov bl,32h для сотен или 39h для десятков
13.     sub al,Wi
14.     sbb dl,dl
15.     and dl,Mi ;маска
16.     add bl,dl
17.     and dl,Wi
18.     add al,dl

По скорости варианты 1 и 2 получаются эквивалентны, но с sbb получается покороче.

Используя 6 таких сравнений получаем немалый объем кода (> 100 байт), но выигрываем по скорости особенно на P4.

Wintest от bogrus'а дает такие цифры (число тактов):

Код (Text):

1. Метод         P3     P4
2. ---------    ----  -----
3. _Juicy        55    160
4. уравновеш     40     80

Но, по-видимому, это изврат...



PS: Можно еще поизвращаться c анализом двоичных разрядов и сложением BCD (типа того как в теме 0000h - 9999h). Но пока ничего толкового не вижу.

 

Вот еще вариант )



mov ax, 0feh

aam

mov dl, al

xchg al, ah

aam

shl eax, 8

mov al, dl

or eax, 303030h

 

Деление на 10 (метод изобрел Terje Mathisen, код А.Фог) с остатком, можно попробовать заменить таким куском:

Код (Text):

1. mov   edx,eax        ; eax = x < 10004h (сохраняем для вычисления остатка)
2. lea   ebx,[eax*2+eax+3]
3. lea   ecx,[eax*2+eax+3]
4. shl   ebx,4
5. mov   eax,ecx
6. shl   ecx,8
7. add   eax,ebx
8. shl   ebx,8
9. add   eax,ecx
10. add   eax,ebx
11. shr   eax,17        ; eax = x/10 (частное)
12. lea   ecx,[eax*8+eax]
13. add   ecx,eax       ; ecx = (x/10)*10
14. sub   edx,ecx       ; edx = x - (x/10)*10 (остаток)

Но с таблицей конечно будет сверх быстро в потоке

 

Предлагаю такой вариант.

Код (Text):

1. .386
2. .model flat, stdcall
3. option casemap:none
4.  
5. include windows.inc
6. include kernel32.inc
7. include user32.inc
8.  
9. includelib user32.lib
10. includelib kernel32.lib
11.  
12. .data
13. buffer db 4 dup(0),0
14. format db "%x",0
15. .code
16. start:
17.     mov eax,0
18.     dec eax
19.     invoke wsprintf,offset buffer,offset format,eax
20.     invoke MessageBox,0,offset buffer,0,0
21.     call ExitProcess
22. end start

 

NoName



А в чём приимущества такого метода ?



Ещё вариант с табличкой, не очень быстрый, т.к. три умножения, но места требует меньше:

(можно подоптимизировать его чуток, это просто рыба)

Код (Text):

1. al2ascii:
2.         xor     ebx, ebx
3.         movzx   eax, al
4.         mov     cl, 0CDh
5.         mul     cl
6.         mov     edx, eax
7.         shr     eax, 8+3
8.         shr     edx, 8+3-4
9.         and     edx, 0Fh
10.         mov     bl, [al2ascii_table+edx]
11.         shl     ebx, 8
12.  
13.         mul     cl
14.         mov     edx, eax
15.         shr     eax, 8+3
16.         shr     edx, 8+3-4
17.         and     edx, 0Fh
18.         mov     bl, [al2ascii_table+edx]
19.         shl     ebx, 8
20.  
21.         mul     cl
22.         shr     eax, 8+3-4
23.         and     al, 0Fh
24.         mov     bl, [al2ascii_table+eax]  
25.  
26.         mov     eax, ebx
27.         ret
28.  
29.  
30. al2ascii_table  db '0','1',00,'2','3','3','4',00,'5','6',00,'7','8','8','9',00

 

NoName

В твоем коде не передан параметр для ExitProcess.

 

q_q



Это оптимизация по размеру

 

Вот ещё рыба. тоже табличка, но код по меньше немного. Умножений нет, но используется daa (да здравствует четвёртый пень! и партиальные регистры. На скорость не тестил, но думаю должно быть неплохо на P6/Athlon, если доработать немного. Вариантов тут много может быть.

Код (Text):

1.  
2. al2ascii:
3.         movzx   ecx, al
4.         shr     ecx, 4
5.         and     eax, 0Fh
6.         mov     al, [eax+magic_table+16]
7.         and     al, 3Fh
8.         mov     dh, [ecx+magic_table+16]
9.         shr     dh, 6
10.         mov     dl, [ecx+magic_table]
11.         add     al, dl
12.         daa
13.         adc     ah, dh
14.  
15.         mov     edx, eax
16.         and     eax, 0Fh
17.         shl     eax, 16
18.         mov     al, dh
19.         shr     dl, 4
20.         mov     ah, dl
21.         or      eax, 303030h
22.         ret
23.  
24.                 ;   0   1   2   3   4   5   6   7   8   9   a   b   c   d   e   f
25. magic_table     db 00h,16h,32h,48h,64h,80h,96h,12h,28h,44h,60h,76h,92h,08h,24h,40h
26.                 db 00h,01h,02h,03h,04h,05h,06h,47h,48h,49h,50h,51h,52h,93h,94h,95h

ЗЫ: daa можно разложить: проверять значения нибблов, и прибавлять 6, если больше 10 (это легко делать без ветвлений). Но в районе 50ти будут ошибки, т.к. таким способом не удаётся учесть перенос между нибблами :-( Пока красивого решения я не вижу, поэтому оставил daa.

 

Да и формат "%x" не тот, это он лишь бы ляпнуть

 

.....



mov ax, 0feh

mov bl, 100

div bl

xchg ah, al

shl eax, 8

xchg ah, al

mov bl, 10

div bl

xchg ah, al

add eax, 303030h

 

bogrus

Кому нада поменяет

 

Ну ежели пошли таблички, то вот довольно быстрый вариант с таблицей 16*4 = 64 байт.

Используется сложение неупакованных BCD по аналогии с темой "0000h - 9999h".

Код (Text):

1. ;таблица - это BCD представление чисел i*16 = 0,16,32,48 ..., i = 0..15
2. HiBCD dd 0,0106h,0302h,0408h,0604h,0800h,0906h,010102h,
3.       dd 010208h,010404h,010600h,010706h,010902h,020008h,020204h,020400h
4.  
5.     movzx eax,byte [Number]
6.     mov  ecx,eax
7.  
8.     ;преобразуем младшие 4 бита в BCD
9.     and  eax,0Fh  
10.     sub  eax,0Ah
11.     sbb  edx,edx  ;x>=10: edx=0; x<10: edx=FFFFFFFh
12.     and  edx,010Ah
13.     add  edx,eax  ;x>=10: dh=0, dl=(x-10); x<10: dh = 1, dl = x
14.     xor  edx,100h ;инвертируем единичку в dh
15.  
16.     ;берем BCD старших разрядов из таблицы
17.     shr  ecx,4    
18.     mov  eax,[ecx*4+HiBCD]
19.     add  eax,00F6F6F6h    ;корректируем для учета переносов при сложении
20.  
21.     add  eax,edx  ;складываем старший и младший BCD
22.     ;корректируем переносы
23.     mov  ecx,eax  
24.     shr  ecx,4    ;если переноса не было, то старший hex байта = F, иначе 0
25.     and  ecx,060606h
26.     and  eax,0F0F0Fh
27.     sub  eax,ecx     ;там где не было переноса вычитается 6
28.     or   eax,303030h
29.  
30.     bswap eax        ;0123 -> 3210
31.     shr eax,8        ;0321

 

По-моему константу 00F6F6F6h можно сразу прибавить ко всем ячейкам таблицы.

xor edx,100h поменять на xor dh,1

вместо eax (and eax,0Fh и sub eax,0Ah) использовать al лучше - это на байт меньше.



Вообще, с таблицами можно много вариантов придумать, но у всех недостаток - чем быстрее, тем больше таблицу нада :-(

 

S_T_A_S_



Насчет константы 0F6F6F6h - ес-но. Мне просто лень было с этим возиться.



А вот замечания насчет DH и AL, не столь очевидны. Размер мы конечно экономим (я кстати поначалу так и сделал), но при add edx,eax на P3 получаем приличный штраф - у меня получилось около 4 тактов, хотя это возможно вместе с изменением условий выравнивания\декодирования. Проблема парциальных регистров на P3 хорошо известна, но почему-то ей часто пренебрегают



Раз речь зашла о "мелочах", то у меня встречное замечание. В исходной задаче требовалось сохранить результат в строке DecString. Спрашивается: зачем в алгоритмах с поразрядным вычислением результата накапливать байты в r32, а не сразу сохранять готовый байт в строке. ИМХО - лишние сдвиги и парциальные регистры, а блок сохранения простаивает, хотя мог бы работать параллельно (за счет буферизации все равно никакой записи в память не происходит - все байтики автоматом копятся в буфере записи).



По поводу таблиц - это верно. В моем варианте с BCD можно уменьшить таблицу наполовину до 8*4=32 байт, но придется добавить дополнительное сравнение 5 младшых разрядов с 20, т.е. дополнительные байты и такты.

А вообще-то думается вполне компромиссным вариантом является замена div на быстрое деление по Mathisen-Fog или еще как. Кстати, пытался я упростить\ускорить вариант Фога с учетом, того что число < 256 и можно использовать приближенное деление 13/128 или 26/256 с коррекцией на 1 по знаку остатка. Но заметно лучше не получается.

 

пример х=0 до 120, надо x/10, тогда



eax=x

and eax, 0xFFFFFFFE; или sar eax, 1; add eax, eax

lea edx, [eax+4*eax]

lea eax, [edx+8*eax]

sar eax, 7

eax=x/10

 

а вообже не понимаю к чему такая погоня за скоростью в данной ситуации? чем плохо то, что уже созданно?