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

Собственно сабж. По следам публикаций http://we.easyelectronics.ru/Soft/preobrazuem-v-stroku-chast-1-celye-chisla.html
и http://forum.easyelectronics.ru/viewtopic.php?p=240893&sid=8d8b529647d46d09ac70820dbbf982e8#p240893

Все комментарии в теле файла. От 80 до 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		; it`s 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

Комментарии (7)

RSS свернуть / развернуть
Cразу глядя на подачу документа

уже неинтересно что именно написано. Посмешан в кучу код и комментарии к нему. Даже у меня на 24" мониторе надо постоянно двигать все это влево\вправо чтобы прочитать.
Так что не читал, но не одобряю…
0
А достали меня обрывки исходников, болтающиеся по сети. А так есть хотя бы часть вероятности, что тот кто утянет исходник, утянет его в комплекте с авторским пояснением.
(тут дальше идёт брюзжание про изнеженных людей, забывших про то время, когда все тексты имели одно оформление — 80x25 и ничего, всем нравились блин)
0
Ну вот и отформатируй на 80 колонок, а то скроллить код по горизонтали в этом движке крайне неудобно, если он по высоте не умещается в один экран — скроллбар оказывается за экраном.
0
А вообще на 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 команды), меня это более чем устроило.
0
Даже интересно стало, насколько вычитание степеней быстрее?
Итак, делаем вот такое вычитане степеней:

;****************************************************************************
; Печать 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 — то скромное преимущество совсем пропадёт.
0
Комментарий в вашем стиле, туше?
0
Чего бы нет?
В конце-то концов я насильно не заставляю вас читать.
0
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.