24 бита число в строку, используя быстрое деление на 10.

и http://forum.easyelectronics.ru/viewtopic.php?p=240893&sid=8d8b529647d46d09ac70820dbbf982e8#p240893
Все комментарии в теле файла. От 87 до 640 тактов в зависимости от числа. У меня быстрее не вышло.
; Файл предназначен для запуска симуляции в среде Atmel Studio.
; Просто создайте новый проект, процессор атмега328
; и скопируйте содержимое файла в редактор студии.
;
; Сперва пара слов о хранении аргументов.
; Это первый аргумент, в таком виде он используется у меня в математической библиотеке.
; обычно на входе в процедуру - это агрумент, на выходе - результат.
; столь большой размер (64 бита) обусловлен необходимостью вместить, например, результат умножения 32x32 бита.
; впрочем, для других операций он используется лишь частично. Младший байт находится в var10
.def var10=r2
.def var11=r3
.def var12=r4
.def var13=r5
.def var14=r6
.def var15=r7
.def var16=r8
.def var17=r9
; Кроме первого, существует и второй аргумент, поменьше. Размером до 32х бит максимум. Но сегодня он нас не так сильно интересует, чтобы его обсуждать...
; Для конверсии числа в строку нам потребуется буфер в области данных. В случае 24х бит максимальная длина строки будет 8 символов.
; Забегая вперёд, хочу отметить, что строка в буфер записывается наоборот, сперва млашая циферка, и по нарастающей.
; Но, учитывая что конвертеры число-строка обычно используются для отображения - это не являет какую-либо проблему.
; Просто изблекать строку с предекрементом указателя и кормить отображалке - получится правильный порядок циферок на экранчике или куда оно там будет отображать.
; если циферки надо будет приклеивать к строке - тоже нет особых проблем...
.dseg
strbuf: .byte 8
; Поехали...
.cseg
; Здесь мы настропаляем стек
start: ldi r16, low(RAMEND)
ldi r17, high(RAMEND)
out spl, r16
out sph, r17
; Создаём указатель на буфер
ldi xl, low (strbuf)
ldi xh, high(strbuf)
; а тут заполняем первый аргумент тестовым числом
.equ number = 12345678; 16777215
ldi r16, low(number)
mov var10, r16
ldi r16, high(number)
mov var11, r16
ldi r16, byte3(number)
mov var12, r16
; До этого момента все действия заняли у нас с процессором 12 тактов.
; вызываем конвертер
rcall Bin2str24b
; Это HALT. На него перед запуском дебаггера надо поставить breakpoint.
; После срабатывания брейкпоинта можно посмотреть на счётчик тактов и сформированную в памяти строку.
rjmp pc
; Это собственно, готовая подпрограмма.
;****************************************************************************
; Преобразование 24 бит беззнакового числа в строку
; по следам публикаций http://we.easyelectronics.ru/Soft/preobrazuem-v-stroku-chast-2-chisla-s-fiksirovannoy-i-plavayuschey-tochkoy.html
; и http://forum.easyelectronics.ru/viewtopic.php?p=240893&sid=8d8b529647d46d09ac70820dbbf982e8#p240893
; низкооптимизированная версия, заточенная на минимизацию использованных регистров
; назначение регистров var10:11:12 - число, var10 lsb
; На выходе - "обратная строка" по указателю в X, lsb впереди, msb сзади.
; var17 = счётчик глубины строки (максимум 8)
; портит r16, var1x
; 87 такт на числе 5 (наилучшее время)
; 640 тактов на числе 16777215 (наихудшее время)
;****************************************************************************
Bin2str24b: clr var17 ; str count clear
clr var16 ; zero
; Цикл - последовательное деление на 10
bin24tostrloop:
clr var15 ; Начало алгоритма быстрого деления 24 бит на константу 10
; var11~15 = var1x * 0xcccccd (abc* xyz)
ldi r16, 0xCC
mul r16, var12 ; a*x | a*y
mov var13, r0
mov var14, r0
add var14, r1
adc var15, r1
inc r16
mul r16, var12 ; a*z
add var12, r0
adc var13, r1
adc var14, var16 ; +zero
adc var15, var16 ; +zero
dec r16
mul r16, var11 ; b*x | b*y
mov var12, r0
add var13, r0
adc var14, r1
adc var15, var16
add var13, r1
adc var14, var16 ; +zero
adc var15, var16 ; +zero
inc r16
mul r16, var11 ; b*z
mov var11, r0
add var12, r1
adc var13, var16 ; +zero
adc var14, var16 ; +zero
adc var15, var16 ; +zero
dec r16
mul r16, var10 ; c*x | c*y
add var12, r0
adc var13, r1
adc var14, var16 ; +zero
adc var15, var16 ; +zero
add var11, r0
adc var12, r1
adc var13, var16 ; +zero
adc var14, var16 ; +zero
adc var15, var16 ; +zero
inc r16
mul r16, var10 ; c*z
add var11, r1
adc var12, var16 ; +zero
adc var13, var16 ; +zero
adc var14, var16 ; +zero
adc var15, var16 ; +zero
; сдвиг результата вправо на 3 бита
lsr var15
ror var14
ror var13
;-----------------------------
lsr var15
ror var14
ror var13
;-----------------------------
lsr var15
ror var14
ror var13
;----------------------------- ; Конец алгоритма быстрого деления на 10
; multiple quotient back (*10)
; математика в этой вселенной устроена таким образом, что если разделить число на 10, округлить и умножить на 10 снова
; то все разряды, кроме последнего не будут отличаться! Вы, может быть удивитесь, но это так.
; И при поразрядном умножении, только младшие разряд множителя участвуют в формировании результата. Я проверял, это всегда так!
; Поэтому, чтобы найти остаток деления, не обязательно множить и вычитать всё число. Достаточно проделать этот трюк только с последним разрядом.
; можете меня не благодарить, ваш КЭП.
ldi r16, 10
mul var13, r16 ; Нас интересует только младший разряд, остальные не участвуют в формировании остатка
sub var10, r0 ; вычитаем из оригинала делённое- умноженное - округлённое.
ldi r16, 0x30
add r16, var10 ; bcd 2 ascii
st x+, r16 ; store it
inc var17 ; count++
; результат деления опять помещаем в делимое и повторяем процесс при необходимости
mov var10, var13
mov var11, var14
mov var12, var15
or var13, var15 ; zero?
or var13, var14
breq pc+2
rjmp bin24tostrloop
ret
И 16-битная версия того же кода, работает ожидаемо быстрее — от 48 до 208 тактов.
;****************************************************************************
; авторство кода http://forum.easyelectronics.ru/viewtopic.php?p=240893&sid=8d8b529647d46d09ac70820dbbf982e8#p240893
; назначение регистров var10:11 - число, на выходе строка
; Временные регистры: var13 - temporary lsb; var14:15 = var10/0x0A var16 = zero
; На выходе - "обратная строка" по указателю в X, lsb впереди, msb сзади.
; var17 = счётчик глубины строки
; 48 тактов на числе 5 (наилучшее время)
; 208 тактов на числе 12345 (наихудшее время)
;****************************************************************************
Bin2str16a: clr var17 ; strlen count init
; начало алгоритма быстрого деления на 10
clr var16 ; zero
bin16tobcdloop:
ldi r16, 0xcd
mul r16, var10
mov var13, r1
ldi r16, 0xcc
mul r16, var11
mov var14, r0
mov var15, r1
mul r16, var10
add var13, r0
adc var14, r1
adc var15, var16 ; +zero
ldi r16, 0xcd
mul r16, var11
add var13, r0
adc var14, r1
adc var15, var16 ; +zero
// quotient >>= 3
lsr var15
ror var14
lsr var15
ror var14
lsr var15
ror var14
; Конец алгоритма быстрого деления на 10. до этого момента - 28 тактов.
// multiple quotient back (*10)
ldi r16, 10
mul var14, r16 ; Нас интересует только младший разряд, остальные не участвуют в формировании остатка
sub var10, r0
; В этот момент - в var14:15 число, делённое на 10, в var10 - остаток
ldi r16, 0x30
add r16, var10 ; bcd 2 ascii
st x+, r16 ; store it
inc var17 ; count++
; результат деления опять помещаем в делимое и повторяем при необходимости
mov var10, var14
mov var11, var15
or var15, var14 ; zero?
brne bin16tobcdloop
ret
Кроме того, существуют версии с удвоением BCD числа — по быстродействию они стоят на втором месте, но несколько отличаются тем, что возвращают результат в виде BCD числа в регистрах. С одной стороны, это влечёт за собой потребность в преобразовании BCD в символы, с другой — все разряды уже находятся на своих местах, что упрощает форматированный вывод чисел с фиксированной десятичной точкой.
;**********************************************************************
; Bin to BCD 24bit
; input: var10:var11:var12 - binary, varl0 least
; output: var20:var21:var22:var23 - packed BCD, var23 least
; uses r16 var13 var14 var15
; cycle used: 737
; origin: https://radiokot.ru/forum/viewtopic.php?p=1417529&sid=8ed218c5348bd5e02624f30a7fdd3a18#p1417529
; autor: akl
;**********************************************************************
bin2bcd24: ldi r16, 0x33
mov var13, r16
ldi r16, 0x03
mov var14, r16
ldi r16, 0x30
mov var15, r16
clr var20
clr var21
clr var22
clr var23
ldi R16, 24
bcd24loop: add var23, var13
sbrs var23, 3 ;if carry to bit 3
sub var23, var14
sbrs var23, 7 ;if carry to bit 7
sub var23, var15
add var22, var13
sbrs var22, 3 ; \n" /*if carry to bit 3,*/
sub var22, var14
sbrs var22, 7 ; \n" /*if carry to bit 7,*/
sub var22, var15
add var21, var13
sbrs var21, 3 ;\n" /*if carry to bit 3,*/
sub var21, var14
sbrs var21, 7 ;\n" /*if carry to bit 7,*/
sub var21, var15
add var20, var13
sbrs var20, 3 ;\n" /*if carry to bit 3,*/
sub var20, var14
sbrs var20, 7 ;\n" /*if carry to bit 7,*/
sub var20, var15
lsl var10
rol var11
rol var12
rol var20
rol var21
rol var22
rol var23
dec r16
brne bcd24loop ;repeat for all bits*/
ret
И его шестнадцатибитная версия:
;**********************************************************************
; Bin to BCD 16 bit
; input: var10:var11 - binary, varl0 least
; output: var20:var21:var22 - packed BCD, var20 least
; uses r16 var13 var14 var15
; cycle used: 383
;**********************************************************************
bin2bcd16: ldi r16, 0x33
mov var13, r16
ldi r16, 0x03
mov var14, r16
ldi r16, 0x30
mov var15, r16
clr var20
clr var21
clr var22
ldi R16, 16
bcd16loop: add var22, var13
sbrs var22, 3 ; \n" /*if carry to bit 3,*/
sub var22, var14
sbrs var22, 7 ; \n" /*if carry to bit 7,*/
sub var22, var15
add var21, var13
sbrs var21, 3 ;\n" /*if carry to bit 3,*/
sub var21, var14
sbrs var21, 7 ;\n" /*if carry to bit 7,*/
sub var21, var15
add var20, var13
sbrs var20, 3 ;\n" /*if carry to bit 3,*/
sub var20, var14
sbrs var20, 7 ;\n" /*if carry to bit 7,*/
sub var20, var15
lsl var10
rol var11
rol var20
rol var21
rol var22
dec r16
brne bcd16loop ;repeat for all bits*/
ret
Что же касается AVR204 — то достаточно заглянуть в заголовок, увидеть там
;* Number of words :25
;* Number of cycles :751/768 (Min/Max)
Чтобы понять, в каком углу камеры находится место этого алгоритма.
- 0
- 03 ноября 2020, 14:23
- Gornist
- 1
Файлы в топике:
main_asm.zip
Cразу глядя на подачу документа

уже неинтересно что именно написано. Посмешан в кучу код и комментарии к нему. Даже у меня на 24" мониторе надо постоянно двигать все это влево\вправо чтобы прочитать.
Так что не читал, но не одобряю…

уже неинтересно что именно написано. Посмешан в кучу код и комментарии к нему. Даже у меня на 24" мониторе надо постоянно двигать все это влево\вправо чтобы прочитать.
Так что не читал, но не одобряю…
А достали меня обрывки исходников, болтающиеся по сети. А так есть хотя бы часть вероятности, что тот кто утянет исходник, утянет его в комплекте с авторским пояснением.
(тут дальше идёт брюзжание про изнеженных людей, забывших про то время, когда все тексты имели одно оформление — 80x25 и ничего, всем нравились блин)
А вообще на AVR самый быстрый алгоритм деления на 10 — это вычитание степеней десятки по ниспадающей. Такова система комманд. Это не голословно, сам убедился при переделке кода — "C&ESR Meter, v2, ремейк. Часть 1.":
Заменил подпрограмму bin2dec на подпрограмму на основе кода из аппноты AVR204. Исходная подпрограмма определяла BCD цифру последовательным делением (через вычитание) на коэффициенты 1000000, 100000, 10000, 1000, 100, 10, 1 до появления отрицательного результата. При таком алгоритме кол-во требуемых действий, как и время выполнения, зависит от кол-ва значимых цифр в числе и их номинала. Самый тяжелый случай, конвертация числа 9999999, время исполнения ~300мкс. Самый легкий, конвертация числа 1, время исполнения ~77мкс. Подпрограмма на основе аппноты AVR204 всегда находит BCD число за 32 итерации, т.е. выполняемое время от числа не зависит. Для обоих случаев время конвертации ~610мкс. Как минимум в два раза больше, но стабильное. Если учесть что время в микросекундах, и размер старой 136 байт, а новой 90 байт (-23 команды), меня это более чем устроило.
Даже интересно стало, насколько вычитание степеней быстрее?
Итак, делаем вот такое вычитане степеней:
И такой же по функционалу код с быстрым делением:
И что же мы видим? По среднему значению вычитание степеней быстрее…
быстрее…
… на два (два, Карл!) такта.
А если отучить процедуру от использования r17 — то скромное преимущество совсем пропадёт.
Итак, делаем вот такое вычитане степеней:
;****************************************************************************
; Печать bin8 в десятичной форме (r16) с заменой незначащих нулей пробелами
; 18 тактов на числе 5
; 45 тактов на числе 55
; 61 такт на числе 255
;****************************************************************************
PrnDec8sz: mov r17,r16
cpi r17,100
brcs _nohundreds
ldi r16,0x30
inc r16 ; отсчитываем сотни
subi r17,100
brcc pc-2
subi r17,-100
dec r16
st x+, r16 ; сохранение сотен
ldi r16,0x30
rjmp _hashundr
_nohundreds: cpi r17,10 ; проверяем, есть ли десятки?
brcs _nodecs
_hashundr: ldi r16,0x30
inc r16
subi r17,10
brcc pc-2
subi r17,-10
dec r16
st x+, r16 ; сохранение десятков
_nodecs: mov r16,r17
subi r16,-0x30
st x+, r16 ; сохранение единиц.
ret
И такой же по функционалу код с быстрым делением:
; 27 тактов на числе 1
; 47 тактов на числе 55
; 67 тактов на числе 255
Bin2str8: clr var17
ldi r16, 0xcd
mul var10, r16
lsr r1
lsr r1
lsr r1
mov var16, r1
ldi r16, 10
mul var16, r16
sub var10, r0
ldi r16, 0x30
add r16, var10
st x+, r16
inc var17
mov var10, var16
tst var10
brne Bin2str8+1
ret
И что же мы видим? По среднему значению вычитание степеней быстрее…
быстрее…
… на два (два, Карл!) такта.
А если отучить процедуру от использования r17 — то скромное преимущество совсем пропадёт.
Комментарии (7)
RSS свернуть / развернуть