Страница 2 из 3
Re: Преобразование байта в три десятичные цифры
Добавлено: Пн июн 24, 2019 12:47:12
oleg110592
в тему автор известный Чен
Спойлер
Код: Выделить всё
;-----------------------------------------------------------------------------;
; Universal decimal string conversion (8/16 bit unsigned)
;
; Register Variables:
; Call: var1:0 = 16 bit value to be converted
; len = String length
; tmp1:0 = <Don't care> (high register must be assigned)
; tmp2 = <Don't care>
;
; Result: var1:0 = <Unknown>
; len = <Not changed>
; tmp1:0 = <Unknown>
; tmp2 = 0
;
; Size: 30 words
; Clock: depends on output routine
; Stack: 10 bytes max (+output routine)
;
; Examples: var1 len output
; 100 0 "100"
; 1234 0 "1234"
; 0 7 " 0"
; 100 5 " 100"
; 100 2 "100"
mk_decu8: clr var1 ;8 bit entry
mk_decu16: ;16 bit entry
clr tmp2 ;digit counter
inc tmp2 ;---- decimal string generating loop
clr tmp0 ;var1 /= 10;
ldi tmp1,16 ;
lsl var0 ;
rol var1 ;
rol tmp0 ;
cpi tmp0,10 ;
brcs PC+3 ;
subi tmp0,10 ;
inc var0 ;
dec tmp1 ;
brne PC-8 ;/
subi tmp0,-'0' ;Push the remander (a decimal digit)
push tmp0 ;/
cp var0,tmp1 ;if(var =! 0)
cpc var1,tmp1 ; continue digit loop;
brne PC-16 ;/
cp tmp2,len ;Adjust string length (this can be removed for auto-length)
brcc PC+5 ;
inc tmp2 ;
ldi var0,' ' ;
push var0 ;
rjmp PC-5 ;/
pop var0 ;Put decimal string
rcall xmit ;<-- Put a char (var0) to memory, console or any display device
dec tmp2 ;
brne PC-3 ;/
ret
отсюда AVR assembler libraries
http://elm-chan.org/cc_e.html
Re: Преобразование байта в три десятичные цифры
Добавлено: Пн июн 24, 2019 13:08:13
Frogfot
[uquote="Demiurg",url="/forum/viewtopic.php?p=3655806#p3655806"]Чем
мой пример не угодил?[/uquote]
Хороший метод, я последнее время пишу больше на С, так только так в основном и делаю - вычитанием числа в степени 10-100-1000...
Я тот метод делал по какой-то аппноте AVR 2хх - 16, 24, 32 бит - работает чётко, не мог понять - каким образом.
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 06:57:35
B@R5uk
[uquote="BOB51",url="/forum/viewtopic.php?p=3649422#p3649422"]Если честно "стандартное преобразование" данных 0-99 (типовые часики, считалки) наиболее просто
решаются табличным способом.[/uquote]
На самом деле гениальная идея! Я даже решил усовершенствовать мой предыдущий алгоритм с делением с остатком, используя этот приём. Идея следующая: из преобразуемой в строку величины будут по очереди выделяться сотни, а затем с помощью таблицы эти сотни будут преобразовываться в пары цифр и сохраняться в памяти для дальнейшей работы. Получилось вот что:
Спойлер
Код: Выделить всё
;==============
.def val1 = r16
.def val2 = r17
.def tmp1 = r18
.def tmp2 = r19
.def cntr = r20
;==============
; Процедура преобразует двухбайтную величину в строку цифр
; и сохраняет её в памяти
; Время выполнения 217 тактов
; Размер 84 слова (168 байт) включая таблицу
ldi val1, 0x5F ; Преобразуемая
ldi val2, 0xEA ; в десятичный вид величина
ldi YH, 0x00 ; Адрес в ОЗУ
ldi YL, 0x60 ; для сохранения результата
ldi ZH, HIGH(2 * t10div) ; Таблица разложения чисел 0..99
ldi tmp1, 0x00 ; 2^6 * 10^3
ldi tmp2, 0xFA
rcall subroutine ; Первая и вторая цифры
ldi tmp1, 0x80 ; 2^6 * 10^1
ldi tmp2, 0x02
rcall subroutine ; Третья и четвёртая цифры
st Y+, val1 ; Пятая цифра
; Конец процедуры
;==============
; Подпрограмма выделяет очередную пару десятичных цифр числа и сохраняет их в памяти
; Технически процедура осуществляет деление с остатком, где частное является числом
; из диапазона 0..99, которое разделяется на две цифры с помощью таблицы
; Время выполнения 103 тактов включая вызов
subroutine: ldi cntr, 0x07 ; Счётчик битов выделяемой сотни
clr ZL ; Подготовка выделяемой сотни
subroutine_1: lsl ZL ; Удвоение выделяемой сотни
sub val1, tmp1 ; Вычитание из делимого
sbc val2, tmp2 ; величины текущего бита результата
brcs subroutine_2 ; Если был перенос -- значение бита 0
inc ZL ; Инкремент выделяемой сотни если бит равен 1
rjmp subroutine_3
subroutine_2: add val1, tmp1 ; Восстановление
adc val2, tmp2 ; делимого
subroutine_3: lsr tmp2 ; Величина
ror tmp1 ; следующего бита результата
dec cntr ; Повтор
brne subroutine_1 ; для всех битов
subroutine_4: lpm tmp1, Z ; Разложение
mov tmp2, tmp1 ; выделенной
swap tmp1 ; сотни на две
andi tmp1, 0x0F ; десятичные цифры
andi tmp2, 0x0F ; с помощью таблицы
st Y+, tmp1 ; Сохранение
st Y+, tmp2 ; результата в памяти
ret
;==============
; Таблица преобразования величин диапазона 0..99 в десятичные цифры
.org 0x0300
t10div: .dw 0x0100,0x0302,0x0504,0x0706,0x0908,0x1110,0x1312,0x1514,0x1716,0x1918
.dw 0x2120,0x2322,0x2524,0x2726,0x2928,0x3130,0x3332,0x3534,0x3736,0x3938
.dw 0x4140,0x4342,0x4544,0x4746,0x4948,0x5150,0x5352,0x5554,0x5756,0x5958
.dw 0x6160,0x6362,0x6564,0x6766,0x6968,0x7170,0x7372,0x7574,0x7776,0x7978
.dw 0x8180,0x8382,0x8584,0x8786,0x8988,0x9190,0x9392,0x9594,0x9796,0x9998
;==============
За счёт того, что алгоритм работает с сотнями, то есть с 7-битными величинами, а не с десятками (4-битные величины), а так же за счёт табличного деления с остатком на 10, производительность в сравнении с обычными циклами вычитания степеней десяток улучшилось. Однако алгоритм с циклами всё ещё не хочет уступать своих позиций:
Спойлер
Код: Выделить всё
;==============
.def val1 = r16
.def val2 = r17
.def tmp1 = r18
.def tmp2 = r19
.def tmp3 = r20
.def sbtr = r21
;==============
; Процедура преобразует двухбайтную величину в строку цифр
; и сохраняет её в памяти
; Время выполнения 78 + 6 * {сумма цифр, кроме последней} тактов
; Размер 27 слов (54 байта)
ldi val1, 0x5F ; Преобразуемая
ldi val2, 0xEA ; в десятичный вид величина
ldi YH, 0x00 ; Адрес в ОЗУ
ldi YL, 0x60 ; для сохранения результата
ldi tmp1, 0x10 ; 10^4
ldi tmp2, 0x27
rcall subroutine ; Первая цифра
ldi tmp1, 0xE8 ; 10^3
ldi tmp2, 0x03
rcall subroutine ; Вторая цифра
ldi tmp1, 0x64 ; 10^2
ldi tmp2, 0x00
rcall subroutine ; Третья цифра
ldi tmp1, 0x0A ; 10^1
ldi tmp2, 0x00
rcall subroutine ; Четвёртая цифра
st Y+, val1 ; Пятая цифра
; Конец процедуры
;==============
; Подпрограмма выделяет очередную цифру десятичного числа и сохраняет её в памяти
; Время выполнения 16 + 6 * {выделяемая цифра} тактов включая вызов
subroutine: clr tmp3 ; Подготовка выделяемой цифры
subroutine_1: sub val1, tmp1 ; Вычитание позиционного значения
sbc val2, tmp2 ; выделяемой цифры
brcs subroutine_2 ; Окончание цикла, если перенос вычитания
inc tmp3 ; Инкремент выделяемой цифры
rjmp subroutine_1 ; Повтор цикла вычитания
subroutine_2: add val1, tmp1 ; Коррекция остатка
adc val2, tmp2 ; после лишнего вычитания
st Y+, tmp3 ; Сохранение результата в памяти
ret
;==============
Худший случай для алгоритма с циклами — это величина 5999x, которую он будет преобразовывать в течении 78 + 6 * 32 = 270 тактов. А в лучшем случае он работает 78 тактов. То есть в среднем 174 такта, что заметно лучше 217 для моего алгоритма. И размер кода значительно меньше. Хотя теперь мой алгоритм хотя бы в наихудшем случае работает немного быстрее, для байта он даже в этом случае проигрывал.
Было бы здорово, если кто-нибудь прикинул время работы алгоритма
Double dabble для двух байт начиная от ввода величины, и заканчивая сохранением в память полученных цифр. Интересно сравнить быстродействие.
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 07:44:38
Starichok51
а что для тебя важнее, время выполнения (число тактов) или размер кода (число байт)?
из твоих речей я делаю вывод, что важнее время выполнения.
а вызов 4 раза
rcall subroutine
в итоге занимает 28 тактов.
а также при вычислении десятков делаются лишние вычитания и лишнее сложение в старшем байте, а это тоже потеря времени.
если так важно минимизировать время, а размер коде не критичен, то "тело" subroutine следует поставить вместо ее вызовов, а на последнем проходе работать только с младшим байтом. это сэкономит 28 + х + 1 тактов, где х число десятков.
и при 9 десятках получится экономия 38 тактов.
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 08:23:43
B@R5uk
[uquote="B@R5uk",url="/forum/viewtopic.php?p=3656329#p3656329"]Было бы здорово, если кто-нибудь прикинул время работы алгоритма
Double dabble для двух байт начиная от ввода величины, и заканчивая сохранением в память полученных цифр. Интересно сравнить быстродействие.[/uquote]Хочешь сделать хорошо, сделай сам! В быстродействии алгоритм сильно проигрывает (во всяком случае для двух байт):
Спойлер
Код: Выделить всё
;==============
.def val1 = r16
.def val2 = r17
.def cntr = r18
.def tmp1 = r19
.def tmp2 = r20
.def tmp3 = r21
;==============
; Процедура преобразует двухбайтную величину в строку цифр
; методом Double Dabble и сохраняет её в памяти
; Время выполнения 313 тактов
; Размер 38 слов (76 байт)
ldi val1, 0x5F ; Преобразуемая
ldi val2, 0xEA ; в десятичный вид величина
ldi cntr, 0x10 ; Счётчик числа битов исходной величины
ldi YH, 0x00 ; Адрес в ОЗУ
ldi YL, 0x60 ; для сохранения результата
clr tmp1 ; Инициализация
clr tmp2 ; регистров для хранения
clr tmp3 ; выделяемых цифр
loop: ; Разряды 0 и 1
subi tmp1, 0xCD ; Прибавление значения 3 к каждому
sbrs tmp1, 3 ; полубайту промежуточных величин
subi tmp1, 0x03 ; если их значение больше 4 для
sbrs tmp1, 7 ; правильного осуществления переноса
subi tmp1, 0x30 ; цифр 5+ в следующую ячейку
; Разряды 2 и 3
subi tmp2, 0xCD
sbrs tmp2, 3
subi tmp2, 0x03
sbrs tmp2, 7
subi tmp2, 0x30
; Последний 5-й разряд коррекции не требует
lsl val1 ; Перенос битов исходной величины
rol val2 ; в регистры промежуточных результатов
rol tmp1 ; Побитовый
rol tmp2 ; сдвиг
rol tmp3 ; промежуточных результатов
dec cntr ; Повтор для всех
brne loop ; оставшихся битов
st Y+, tmp3 ; Сохранение 1-й цифры
mov tmp3, tmp2 ; Разделение
swap tmp3 ; второй
andi tmp2, 0x0F ; и третьей
andi tmp3, 0x0F ; цифр
st Y+, tmp3 ; Сохранение 2-й цифры
st Y+, tmp2 ; Сохранение 3-й цифры
mov tmp3, tmp1 ; Разделение
swap tmp3 ; четвёртой
andi tmp1, 0x0F ; и пятой
andi tmp3, 0x0F ; цифр
st Y+, tmp3 ; Сохранение 4-й цифры
st Y+, tmp1 ; Сохранение 5-й цифры
; Конец процедуры
;==============
, я в курсе про развёртывание циклов и подпрограмм, но это, на мой взгляд, в данном случае концептуально не правильно. Мне больше интересен баланс между размером и быстродействием. Хотя, да, пара
rcall/ret выполняется очень долго и это меня немного гложет. С другой стороны, преобразование числа в строку как правило нужно для отображения результатов на дисплее или на семисегментных индикаторах. Отображать с частотой выше 25-50 Гц нет смысла: всё равно глаз и мозг человека просто не успеют поймать и обработать информацию. Так что к процедуре, которая вызывается раз в 20-40 мс, нет смысла предъявлять жёсткие требования по быстродействию. И уж тем более жертвовать ради этого драгоценными байтами ПЗУ. Так что я исследую варианты на предмет быстродействия, но не переусердствую. Хотя ваше предложение увеличивает код всего на 28 байт, в то время как "излишек" табличного метода аж целых 100 байт.
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 10:18:08
akl
Иногда бывает полезно сразу организовывать
счетчики в BCD формате. И преобразовывать не нужно.
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 11:07:38
Starichok51
B@R5uk писал(а): Мне больше интересен баланс между размером и быстродействием.
в общем, это правильно.
B@R5uk писал(а):Так что к процедуре, которая вызывается раз в 20-40 мс, нет смысла предъявлять жёсткие требования по быстродействию.
а зачем так часто?
я вывожу на экран 3 раза в секунду, вместе с обработкой кнопок или энкодера, чтобы сразу видеть результат действия кнопок и энкодера. чаще выводить вообще нет никакого смысла.
да и сильно высокого быстродействия тоже не нужно.
в системах реального времени после прохода полного программного цикла процессор все равно "топчется на месте" в ожидании начала следующего временного интервала.
например, у меня программный таймер отрабатывает интервалы по 10 мс. а полный цикл, вместе с выводом на экран 1602 по довольно медленному протоколу I2C занимает примерно 6,5 мс (точно уже не помню). и оставшиеся 3,5 мс процессор топчется на месте, ожидая наступление следующего 10-миллисекундного интервала.
так куда тут спешить с преобразованием числа в отдельные цифры?
тем более, с огромными затратами на вывод 32 символов вместе с командами позиционирования курсора по I2C...
так что, твоя гонка за производительность такого преобразования вообще не имеет смысла.
даже с внутренним генератором на 1 МГц у меня всегда оставался огромный запас времени, чтобы потоптаться на месте в ожидании окончания временного интервала.
а поскольку мне спешить некуда, то для меня важнее минимальная длина кода всей программы.
тут я раньше (но не помню где) показывал свой алгоритм разбиения числа на цифры с вызовом подпрограмм деления. а деление, как известно, занимает много времени.
но меня на общем времени выполнения всей нужной работы потеря времени на несколько операций деления никогда не лимитировала.
а ты можешь назвать такую программу (прошивку), где потеря 200 тактов процессора была бы катастрофической?
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 11:33:46
B@R5uk
Я как-то изобретал частотомер по принципу взаимообоюдного счёта (reciprocal frequency counting). Я осуществил это через подсчёт числа приходящих импульсов в прерывании захвата таймера. Одновременно с подсчётом в прерывании проверялось достаточно ли времени длился счёт импульсов и замерялась эта самая длительность для последующих расчётов частоты. В принципе, подпрограмма прерывания отрабатывала достаточно быстро, но при высокой входной частоте была опасность того, что ресурсов процессора не хватит на обсчёт и вывод результата измерения частоты (это делалось в главном цикле). Эта проблема решается включением предделителя частоты при её завышении, но желание сделать быстрый код у меня осталось. Плюс просто спортивный и академический интерес.
Кстати, я тут поковырялся и обнаружил вот что. Если цикл алгоритма Double Dabble для одного байта развернуть в прямой код и выкинуть всё лишнее, то скорость выполнения (равная 44 такта) составит достойную конкуренцию алгоритму с вычитаниями, скорость работы которого равна 11/36/61 тактов в лучшем/среднем/худшем случаях:
Спойлер
Код: Выделить всё
;==============
.def dig3 = r16
.def dig2 = r17
.def dig1 = r18
;==============
; Процедура преобразует байт
; в строку цифр методом Double Dabble
; Время выполнения 44 такта
; Размер 44 слова (88 байт)
ldi dig3, 0xFF ; Преобразуемая в десятичный вид величина
clr dig2 ; Инициализация регистров
clr dig1 ; для хранения выделяемых цифр
; 1
lsl dig3 ; Первые два сдвига не требуют коррекции
rol dig2
; 2
lsl dig3
rol dig2
; 3
lsl dig3 ; Коррекция только младшего полубайта
rol dig2 ; для 3-го, 4-го и 5-го сдвигов
subi dig2, 0xFD
sbrs dig2, 3
subi dig2, 0x03
; 4
lsl dig3
rol dig2
subi dig2, 0xFD
sbrs dig2, 3
subi dig2, 0x03
; 5
lsl dig3
rol dig2
subi dig2, 0xFD
sbrs dig2, 3
subi dig2, 0x03
; 6
lsl dig3 ; 6-й и 7-й сдвиги требуют полной коррекции
rol dig2 ; байта с единицами и десятками
subi dig2, 0xCD
sbrs dig2, 3
subi dig2, 0x03
sbrs dig2, 7
subi dig2, 0x30
; 7
lsl dig3 ; 7-й и 8-й сдвиги задействуют старшую
rol dig2 ; цифру, которая не требует коррекции
rol dig1
subi dig2, 0xCD
sbrs dig2, 3
subi dig2, 0x03
sbrs dig2, 7
subi dig2, 0x30
; 8
lsl dig3
rol dig2
rol dig1
; =
mov dig3, dig2 ; Разделение 2-й и 3-й цифр результата
swap dig2
andi dig2, 0x0F
andi dig3, 0x0F
; Конец процедуры
;==============
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 13:32:59
Demiurg
Я вот на что обратил внимание. Тут приводится количество тактов в примерах. Есть но, вы привели голые примеры. Результаты преобразования чисел временные. Нет никакого смысла держать их в регистрах. Понимаю, что проекты разные, есть мк с маленьким объёмом ОЗУ. Но это не так часто. Поэтому: в примерах нет сохранения, восстановления регистров. Команд чтения записи в из ОЗУ. Лично я привёл свой пример полностью. И в моем примере ещё и прибавление 0x30 к разрядам чисел для вывода на дисплей.
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 14:44:59
Starichok51
чтение/запись в/из ОЗУ и прибавление 0x30 к разрядам чисел будут ВСЕГДА, поэтому при сравнении алгоритмов нет смысла прибавлять эти такты.
а сохранение и восстановление регистров - не факт, что могут понадобиться при выводе числа на дисплей.
и сохранение и восстановление регистров не имеют никакого отношения к собственной длине алгоритма преобразования.
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 16:18:16
B@R5uk
Demiurg, вы просто не читали мои примеры. Вернее, читали только первый и предыдущий посты, где я привёл код для преобразования байта. В листингах для преобразования слова у меня результаты сохраняются в ОЗУ, это просто необходимость, позволяющая обойтись меньшим числом рабочих регистров.
Так же, я не согласен с тем, что прибавление 0x30 будет всегда. Для вывода результата на семисегментник скорее "голые цифры" результата будут использоваться как индексы кода семисегментника в таблице, расположенной в ПЗУ МК. Для сравнения быстродействия алгоритмов важнее не конечная длительность выполнения со всеми тонкостями конкретной реализации, а разница между длинами выполнения смыслового ядра алгоритма. Другое дело, когда я привёл один вариант оформления, вы — другой, то будет невозможно сделать сравнительный анализ. По этой причине я переписал все предыдущие варианты на свой лад в одном стиле; как раз чтобы было удобно сравнивать их преимущества и недостатки. (За одно и поднаучился чему-нибудь новому). Впрочем, как заметил Starichok51, даже здесь есть подвох: можно переписать алгоритм, развернув и упростив циклы, сэкономив время, а можно сделать вызов процедур для часто повторяющегося кода и сэкономить место.
Re: Преобразование байта в три десятичные цифры
Добавлено: Вт июн 25, 2019 17:17:57
Demiurg
Ассемблер дело такое... многогранное. Зависит от многих факторов. Размер Flash, SRAM микроконтроллера. Проект. Быстродействие, размер всего куска кода. Я всего лишь показал, что когда указываете количество тактов и размер куска кода, честно указывайте сопутствующие накладные расходы.
Я на асме плотно сидел более 10 лет. Под конец реализовывал древовидные меню и именно эта соломинка сломала хребет верблюду. После этого я пересел на си.
Re: Преобразование байта в три десятичные цифры
Добавлено: Пт июн 28, 2019 15:17:32
B@R5uk
Поковырялся я тут и написал процедуры преобразования 3-байтной величины в строку цифр.
Метод Double Dabble
Размер: 122 байта
Время: 713 тактов
Регистры: 8 штук + Y
Спойлер
Код: Выделить всё
;==============
.def val1 = r16
.def val2 = r17
.def val3 = r18
.def cntr = r19
.def tmp1 = r20
.def tmp2 = r21
.def tmp3 = r22
.def tmp4 = r24
;==============
; Процедура преобразует трёхбайтную величину в строку цифр
; методом Double Dabble и сохраняет её в памяти
; Время выполнения 713 тактов
; Размер 61 слов (122 байта)
ldi val1, 0xFF ; Величина,
ldi val2, 0x23 ; преобразуемая
ldi val3, 0xF4 ; в десятичный вид
ldi cntr, 0x18 ; Счётчик числа битов исходной величины
ldi YH, 0x00 ; Адрес в ОЗУ
ldi YL, 0x60 ; для сохранения результата
clr tmp1 ; Инициализация
clr tmp2 ; регистров
clr tmp3 ; для хранения
clr tmp4 ; выделяемых цифр
loop: ; Разряды 0 и 1
subi tmp1, 0xCD ; Прибавление значения 3 к каждому
sbrs tmp1, 3 ; полубайту промежуточных величин
subi tmp1, 0x03 ; если их значение больше 4 для
sbrs tmp1, 7 ; правильного осуществления переноса
subi tmp1, 0x30 ; цифр 5+ в следующую ячейку
; Разряды 2 и 3
subi tmp2, 0xCD
sbrs tmp2, 3
subi tmp2, 0x03
sbrs tmp2, 7
subi tmp2, 0x30
; Разряды 4 и 5
subi tmp3, 0xCD
sbrs tmp3, 3
subi tmp3, 0x03
sbrs tmp3, 7
subi tmp3, 0x30
; Разряд 6, 7-ой разряд коррекции не требует
subi tmp4, 0xFD
sbrs tmp4, 3
subi tmp4, 0x03
; =
lsl val1 ; Перенос битов исходной
rol val2 ; величины в регистры
rol val3 ; промежуточных результатов
rol tmp1 ; Побитовый
rol tmp2 ; сдвиг
rol tmp3 ; промежуточных
rol tmp4 ; результатов
dec cntr ; Повтор для всех
brne loop ; оставшихся битов
; =
mov val1, tmp4 ; Разделение
swap val1 ; 1-й и
andi val1, 0x0F ; 2-й
andi tmp4, 0x0F ; цифр
st Y+, val1 ; Сохранение 1-й цифры
st Y+, tmp4 ; Сохранение 2-й цифры
; =
mov val1, tmp3 ; Разделение
swap val1 ; 3-й и
andi val1, 0x0F ; 4-й
andi tmp3, 0x0F ; цифр
st Y+, val1 ; Сохранение 3-й цифры
st Y+, tmp3 ; Сохранение 4-й цифры
; =
mov val1, tmp2 ; Разделение
swap val1 ; 5-й и
andi val1, 0x0F ; 6-й
andi tmp2, 0x0F ; цифр
st Y+, val1 ; Сохранение 5-й цифры
st Y+, tmp2 ; Сохранение 6-й цифры
; =
mov val1, tmp1 ; Разделение
swap val1 ; 7-й и
andi val1, 0x0F ; 8-й
andi tmp1, 0x0F ; цифр
st Y+, val1 ; Сохранение 7-й цифры
st Y+, tmp1 ; Сохранение 8-й цифры
; Конец процедуры
;==============
Размер: 230 байт
Время: 423 такта
Регистры: 9 штук + Y + Z
Спойлер
Код: Выделить всё
;==============
.def val1 = r16
.def val2 = r17
.def val3 = r18
.def cntr = r19
.def quo1 = r20
.def quo2 = r21
.def tmp1 = r22
.def tmp2 = r23
.def tmp3 = r24
;==============
; Процедура преобразует трёхбайтную величину в строку цифр
; и сохраняет её в памяти. Для этого исходная величина делится
; с остатком на 10000, затем частное и остаток в свою очередь
; делятся с остатком на 100 и полученные сотни раскладываются
; с помощью таблицы на цифры, их составляющие.
; Время выполнения 423 такта
; Размер 115 слов (230 байт) включая таблицу
ldi val1, 0xFF ; Величина
ldi val2, 0x23 ; преобразуемая
ldi val3, 0xF4 ; в десятичный вид
ldi YH, 0x00 ; Адрес в ОЗУ
ldi YL, 0x60 ; для сохранения результата
ldi ZH, HIGH(2 * t10div) ; Таблица разложения чисел 0..99
; =
ldi cntr, 0x0B ; Счётчик битов частного
clr quo1 ; Обнуление
clr quo2 ; частного
ldi tmp1, 0x00 ; Делитель 10000,
ldi tmp2, 0x40 ; умноженный
ldi tmp3, 0x9C ; на 2^10
loop: lsl quo1 ; Удвоение
rol quo2 ; частного
sub val1, tmp1 ; Вычитание из делимого
sbc val2, tmp2 ; величины текущего
sbc val3, tmp3 ; бита частного
brcs branch_1 ; Если был перенос -- значение бита 0
inc quo1 ; Инкремент частного, если бит равен 1
nop
rjmp branch_2
branch_1: add val1, tmp1 ; Восстановление
adc val2, tmp2 ; делимого
adc val3, tmp3
branch_2: lsr tmp3 ; Величина
ror tmp2 ; следующего
ror tmp1 ; бита частного
dec cntr ; Повтор
brne loop ; для всех битов
; =
rcall subroutine ; Выделение и сохранение первой четвёрки цифр
mov quo1, val1 ; Копирование остатка от деления
mov quo2, val2 ; на 10000 для преобразования в цифры
rcall subroutine ; Выделение и сохранение второй четвёрки цифр
; Конец процедуры
;==============
; Подпрограмма преобразует число из диапазона 0..9999 в строку цифр и сохраняет её
; в памяти. Технически это осуществляется делением входных данных с остатком
; на 100 и последующим табличным разложением частного и остатка на искомые цифры.
subroutine: ldi cntr, 0x07 ; Счётчик битов частного
clr ZL ; Обнуление частного
ldi tmp1, 0x00 ; Делитель 100,
ldi tmp2, 0x19 ; умноженный на 2^6
subroutine_1: lsl ZL ; Удвоение частного
sub quo1, tmp1 ; Вычитание из делимого
sbc quo2, tmp2 ; величины текущего бита частного
brcs subroutine_2 ; Если был перенос -- значение бита 0
inc ZL ; Инкремент частного, если бит равен 1
rjmp subroutine_3
subroutine_2: add quo1, tmp1 ; Восстановление
adc quo2, tmp2 ; делимого
subroutine_3: lsr tmp2 ; Величина
ror tmp1 ; следующего бита частного
dec cntr ; Повтор
brne subroutine_1 ; для всех битов
lpm tmp1, Z ; Разложение
mov tmp2, tmp1 ; найденного
swap tmp1 ; частного на
andi tmp1, 0x0F ; десятичные цифры
andi tmp2, 0x0F ; с помощью таблицы
st Y+, tmp1 ; Сохранение
st Y+, tmp2 ; результата в памяти
mov ZL, quo1 ; Копирование остатка в индексный регистр
lpm tmp1, Z ; Разложение
mov tmp2, tmp1 ; полученного
swap tmp1 ; от деления остатка
andi tmp1, 0x0F ; на десятичные цифры
andi tmp2, 0x0F ; с помощью таблицы
st Y+, tmp1 ; Сохранение
st Y+, tmp2 ; результата в памяти
ret
;==============
; Таблица преобразования величин диапазона 0..99 в десятичные цифры
.org 0x0300
t10div: .dw 0x0100,0x0302,0x0504,0x0706,0x0908,0x1110,0x1312,0x1514,0x1716,0x1918
.dw 0x2120,0x2322,0x2524,0x2726,0x2928,0x3130,0x3332,0x3534,0x3736,0x3938
.dw 0x4140,0x4342,0x4544,0x4746,0x4948,0x5150,0x5352,0x5554,0x5756,0x5958
.dw 0x6160,0x6362,0x6564,0x6766,0x6968,0x7170,0x7372,0x7574,0x7776,0x7978
.dw 0x8180,0x8382,0x8584,0x8786,0x8988,0x9190,0x9392,0x9594,0x9796,0x9998
;==============
Размер: 70 байт
Время: 169 + 7 * {сумма цифр, кроме последней} тактов (от 169 до 547 тактов)
Регистры: 7 + Y + Z
Спойлер
Код: Выделить всё
;==============
.def val1 = r16
.def val2 = r17
.def val3 = r18
.def dig = r19
.def tmp1 = r20
.def tmp2 = r21
.def tmp3 = r22
;==============
; Процедура преобразует трёхбайтную величину в строку цифр
; и сохраняет её в памяти. Для этого исходная величина с помощью
; циклов вычитаний делится с остатком на последовательные степени
; десяток в убывающем порядке, взятые из таблицы в ПЗУ.
; Время выполнения 169 + 7 * {сумма цифр, кроме последней} такта.
; Лучше время 169 тактов, худшее -- 547 тактов
; Размер 35 слов (70 байт) включая таблицу
ldi val1, 0x76 ; Величина,
ldi val2, 0x96 ; преобразуемая
ldi val3, 0x98 ; в десятичный вид
ldi YH, 0x00 ; Адрес в ОЗУ
ldi YL, 0x60 ; для сохранения результата
ldi ZH, HIGH(2 * pow10t) ; Таблица степеней десяток
ldi ZL, LOW(2 * pow10t)
loop_1: lpm tmp1, Z+ ; Загрузка
lpm tmp2, Z+ ; из ПЗУ очередной
lpm tmp3, Z+ ; степени десятки
clr dig ; Очистка счётчика вычитаний
loop_2: sub val1, tmp1 ; Вычитание
sbc val2, tmp2 ; из преобразуемой величины
sbc val3, tmp3 ; текущей степени десяток
brcs branch ; Наличие переноса -- окончание счёта
inc dig ; Инкремент счётчика вычитаний
rjmp loop_2 ; Повтор вычитания
branch: add val1, tmp1 ; Коррекция
adc val2, tmp2 ; лишнего
adc val3, tmp3 ; вычитания
st Y+, dig ; Сохранение найденной цифры в ОЗУ
cpi tmp1, 0x0A ; Повтор цикла, пока остатком
brne loop_1 ; не станут единицы
st Y+, val1 ; Сохранение последней цифры
; Конец процедуры
;==============
; Таблица степеней десяток начиная с 10^7 в убывающем порядке
pow10t: .dw 0x9680, 0x4098, 0x0F42, 0x86A0, 0x1001, 0x0027, 0x03E8, 0x6400
.dw 0x0000, 0x000A, 0x0000
;==============
Надеюсь, нигде не накосячил, если что, проверяйте.
Добавлено after 17 minutes 38 seconds:
[uquote="akl",url="/forum/viewtopic.php?p=3641961#p3641961"]Метод последовательного вычитания быстр и начинает проигрывать при преобразовании больших чисел, когда вес оных превышает возможности ассемблера (4 байта). Пользуюсь и тем и другим.
Например, преобразование 40 разрядного числа только на старшей части регистрового файла AVR.
{код Double Dabble}[/uquote]Всё с точностью наоборот. Если для одного байта метод Double Dabble ещё может поконкурировать с методом вычитаний (смотри мой код выше), то для бо́льшего числа байтов он сильно проигрывает, и чем дальше — тем сильнее. И это не удивительно. Каждый новый байт преобразуемого числа добавляет 2,5 разряда десятичного числа. А два разряда — это 5 операций с прибавлением/вычитанием троек и две операции сдвига. Плюс 8 новых итераций всего цикла. Квадратичная сложность + нерациональное исполнение = большой код и ещё большее время выполнения. В то время как для метода вычитаний цикл становится длиннее всего на одну итерацию, а общее число циклов увеличивается на 2.
Метод Double Dabble, на сколько я понимаю, хорош для аппаратного преобразования двоичных чисел в десятичные. При этом то, что делается в коде с помощью
последовательных сложений/вычитаний по условию, в железе будет выполняться
одновременно с помощью блоков жёсткой логики. Синхронный регистр надо будет протактировать ровно столько раз, сколько двоичных разрядов в исходном числе. Сложность получается линейная, а не квадратичная, как при написании программы для МК.
Пока получается, что метод вычитаний практически вне конкуренции. Мои попытки реализовать метод деления с остатком, конечно, дают результат, но он мне пока не кажется очень уж убедительным. Интересно, есть ли какие-нибудь другие методы преобразования?
Re: Преобразование байта в три десятичные цифры
Добавлено: Пт июн 28, 2019 17:26:15
Ser60
[uquote="B@R5uk",url="/forum/viewtopic.php?p=3658147#p3658147"]Интересно, есть ли какие-нибудь другие методы преобразования?[/uquote] Вот
тут подборка по разным методам.
Приводимый ниже рекордно быстрый алгоритм годится только для архитектуры MSP430X. В ней имеется таймер реального времени RTC_B, в состав которого входит регистр BIN2BCD. Странно, что в документации slau272a и slau208k на семействa F5xx/F6xx и FR57xx, соответственно, об этом регистре нет ни слова в тексте. Есть лишь краткое упоминание этого регистра в составе регистров RTC, где ему посвящено лишь одно предложение, поэтому его очень легко не заметить. Согласно ДШ, в этот регистр следует сначала записать 12-битное число, а при чтении из него получите 16-битное BCD этого числа. Проще не бывает. Вот пример преобразования 12-битного числа в R4 в BCD в R5. Процедура занимает всего 6 циклов !!!
Почему в документации упомянуты лишь 12-битные исходные числа? Ведь максимальное 12-битное число - это 4095, а четырех BCD знаков в 16-битном регистре достаточно для представления чисел вплоть до 9999. Это для меня осталось загадкой. Я попробовал переводить числа вплоть до 9999 - все действительно работает! Более того, оказалось, что при записи в этот регистр чисел от 10000 до 16383 (т.е. 14-битных) в регистре остается лишь последние 4 цифры BCD, а для чисел от 16384 до 65535 процессор оставляет лишь 14 младших бит числа и переводит полученный результат в BCD. Я проверял всё это на процессоре MSP430FR5728
Re: Преобразование байта в три десятичные цифры
Добавлено: Пт июн 28, 2019 18:33:06
B@R5uk
[uquote="Ser60",url="/forum/viewtopic.php?p=3658216#p3658216"]Вот
тут подборка по разным методам.[/uquote]Спасибо! Там есть действительно интересные подходы. Попробую что-нибудь замутить. Например, деление с остатком на 10 с помощью сдвигов и сложений весьма интригует.
Re: Преобразование байта в три десятичные цифры
Добавлено: Сб июн 29, 2019 04:43:14
Starichok51
cpi tmp1, 0x0A ; Повтор цикла, пока остатком
brne loop_1 ; не станут единицы
во-первых, нельзя проверять только младший байт, при этом tmp2 и tmp3 могут быть не равны нулю.
во-вторых, почему ты решил, что в остатке должно быть РОВНО 10 (проверка на неравенство)?
в-третьих, в погоне за уменьшением количества программных строк (размера кода) ты тратишь лишнее время на вычитание и последующего сложение всех трех байт, когда старший и средний байты уже равны нулю и из них вычитать ничего не надо.
Re: Преобразование байта в три десятичные цифры
Добавлено: Сб июн 29, 2019 05:30:21
B@R5uk
[uquote="Starichok51",url="/forum/viewtopic.php?p=3658395#p3658395"]во-первых, нельзя проверять только младший байт, при этом tmp2 и tmp3 могут быть не равны нулю.
во-вторых, почему ты решил, что в остатке должно быть РОВНО 10[/uquote]Потому что, когда делитель станет равен 10, то остатком будут единицы. Регистры tmpX — это делитель, степени десятки, которые загружаются из памяти. И только один из них (последний) имеет в качестве младшего байта величину 0x0A. Пожалуй, не очень удачный комментарий у меня получился.
Добавлено after 8 minutes 14 seconds:
[uquote="Starichok51",url="/forum/viewtopic.php?p=3658395#p3658395"]...ты тратишь лишнее время на вычитание и последующего сложение всех трех байт, когда старший и средний байты уже равны нулю и из них вычитать ничего не надо.[/uquote]Сначала хотел сделать пачку циклов, но потом подумал, что формула для времени перестанет быть простой и красивой, а код будет длинным, и сделал как сделал. Там ещё куча времени сэкономится на загрузке из памяти: вместо трёх тактов операция займёт один, и количество загрузок будет не три для всех циклов, а от трёх до одной.
Добавлено after 3 minutes 31 second:
Starichok51, спасибо, что проявляете интерес и контролируете код.
В чужом коде разбираться — тот ещё труд, по себе знаю.
Re: Преобразование байта в три десятичные цифры
Добавлено: Сб июн 29, 2019 06:12:22
Starichok51
B@R5uk писал(а):Регистры tmpX — это делитель,
пардон, перепутал регистры, извиняюсь.
B@R5uk писал(а):Там ещё куча времени сэкономится на загрузке из памяти: вместо трёх тактов операция займёт один
с загрузкой таблицы из памяти очень невыгодное решение в плане производительности - команда LPM выполняется за 3 машинных цикла (ну, пусть будем их звать тактами). а загрузка непосредственного операнда занимает 1 машинный цикл (такт).
но поскольку ты решил обойтись одним циклом, то такая потеря времени на загрузку из программной памяти неизбежна.
да на хрена тебе и всем нам красивая формула? ты, что ли, гонишься за красотой формулы или за скоростью алгоритма?
и не обязательно делать 7 циклов.
будет один цикл в 3 прохода, когда нужно вычитать 3 байта (10 миллионов, 1 миллион и 100 тысяч),
1 цикл в 2 прохода (10 тысяч и 1 тысяча),
1 цикл в 2 прохода (100 и 10).
Re: Преобразование байта в три десятичные цифры
Добавлено: Сб июн 29, 2019 06:45:45
КРАМ
[uquote="Ser60",url="/forum/viewtopic.php?p=3658216#p3658216"]В ней имеется таймер реального времени RTC_B, в состав которого входит регистр BIN2BCD.[/uquote]
Необходимость быстрого преобразования двоичного кода в двоично-десятичный достаточно экзотична в отношении задач на МК и зависит от реализации этих задач.
Немного поясню.
Быстрое преобразование BIN2BCD позволяет сэкономить энергию автономного химического источника и совершенно никак не влияет на общую скорость выполнения общей задачи. Десятичное представление нужно для восприятия величин человеком, реакция которого в части этого восприятия составляет порядки СЕКУНДЫ. Что делает усилия по увеличению скорости этого преобразования практически бессмысленными.
С другой стороны, для построения часов реального времени разрядность счета этого времени будет определять требования к процедуре BIN2BCD и в коде и в железе.
Это я к тому, что счет времени посредством раздельных переменных для секунд-минут-часов-... позволяет отказаться от многоразрядного BIN2BCD. Так в совершенно древних МК существует команда десятичной настройки DAW, которая в один машинный цикл превращает двоичное число в диапазоне 0х00 ... 0х63 в тетрадно-десятичное число 00 ... 99.
Re: Преобразование байта в три десятичные цифры
Добавлено: Сб июн 29, 2019 07:24:23
Starichok51
про реакцию человека правильно замечено.
и не только зрительное восприятие, но и при работе с кнопками скорость владения пальцами у обычных людей не слишком шустрая.
поэтому я не встречал промышленных приборов, где вывод на дисплей (экран и т.п.) составляет более 3 раз в секунду.
и я в своих поделках обрабатываю кнопки и энкодер и вывожу на экран 3 раза в секунду.
поэтому большая скорость преобразования чисел в символы тут совершенно не нужна.
и это не обязательно, что это будут ЧАСЫ.
любой прибор обязан функционировать в реальном времени. для этого он обычно тактируется аппаратным таймером и программным таймером.
аппаратный таймер отмеряет малые промежутки времени и делает другую необходимую работу.
программный таймер отрабатывает большой промежуток времени и определяет весь программный цикл в реальном времени.
причем полное время программного цикла всегда делается так, что оно больше времени работы всего кода. а далее процессор "топчется на месте", ожидая конца программного цикла.
это общее правило грамотного построения программы (прошивки).
а поскольку у нас всегда имеется приличный запас времени до конца программного цикла, то тем более незачем спешить с преобразованием чисел в символы.
я рассматриваю это тему, как "академический" интерес в создании быстрого алгоритма. но практического смысла от этой быстроты я не вижу.
поэтому в своих изделиях я применяю последовательное деление на 10, получая в остатке следующую цифру, начиная с самой младшей.
да, подпрограмма деления "медленная", но на общем фоне программного цикла это вообще не имеет никакого значения.