Преобразование байта в три десятичные цифры

в тему автор известный Чен

Спойлер

Код:: ;----------; ; 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

Demiurg писал(а):

Чем мой пример не угодил?

Хороший метод, я последнее время пишу больше на С, так только так в основном и делаю - вычитанием числа в степени 10-100-1000...

Я тот метод делал по какой-то аппноте AVR 2хх - 16, 24, 32 бит - работает чётко, не мог понять - каким образом.

BOB51 писал(а):

Если честно "стандартное преобразование" данных 0-99 (типовые часики, считалки) наиболее просто решаются табличным способом.

На самом деле гениальная идея! Я даже решил усовершенствовать мой предыдущий алгоритм с делением с остатком, используя этот приём. Идея следующая: из преобразуемой в строку величины будут по очереди выделяться сотни, а затем с помощью таблицы эти сотни будут преобразовываться в пары цифр и сохраняться в памяти для дальнейшей работы. Получилось вот что:

Спойлер

Код:: ;============== .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 для двух байт начиная от ввода величины, и заканчивая сохранением в память полученных цифр. Интересно сравнить быстродействие.

а что для тебя важнее, время выполнения (число тактов) или размер кода (число байт)?
из твоих речей я делаю вывод, что важнее время выполнения.
а вызов 4 раза
rcall subroutine
в итоге занимает 28 тактов.
а также при вычислении десятков делаются лишние вычитания и лишнее сложение в старшем байте, а это тоже потеря времени.
если так важно минимизировать время, а размер коде не критичен, то "тело" subroutine следует поставить вместо ее вызовов, а на последнем проходе работать только с младшим байтом. это сэкономит 28 + х + 1 тактов, где х число десятков.
и при 9 десятках получится экономия 38 тактов.

B@R5uk писал(а):

Было бы здорово, если кто-нибудь прикинул время работы алгоритма Double dabble для двух байт начиная от ввода величины, и заканчивая сохранением в память полученных цифр. Интересно сравнить быстродействие.

Хочешь сделать хорошо, сделай сам! В быстродействии алгоритм сильно проигрывает (во всяком случае для двух байт):

Спойлер

Код:: ;============== .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-й цифры ; Конец процедуры ;==============

Starichok51, я в курсе про развёртывание циклов и подпрограмм, но это, на мой взгляд, в данном случае концептуально не правильно. Мне больше интересен баланс между размером и быстродействием. Хотя, да, пара rcall/ret выполняется очень долго и это меня немного гложет. С другой стороны, преобразование числа в строку как правило нужно для отображения результатов на дисплее или на семисегментных индикаторах. Отображать с частотой выше 25-50 Гц нет смысла: всё равно глаз и мозг человека просто не успеют поймать и обработать информацию. Так что к процедуре, которая вызывается раз в 20-40 мс, нет смысла предъявлять жёсткие требования по быстродействию. И уж тем более жертвовать ради этого драгоценными байтами ПЗУ. Так что я исследую варианты на предмет быстродействия, но не переусердствую. Хотя ваше предложение увеличивает код всего на 28 байт, в то время как "излишек" табличного метода аж целых 100 байт.

Иногда бывает полезно сразу организовывать счетчики в BCD формате. И преобразовывать не нужно.

B@R5uk писал(а): Мне больше интересен баланс между размером и быстродействием.

в общем, это правильно.

B@R5uk писал(а):Так что к процедуре, которая вызывается раз в 20-40 мс, нет смысла предъявлять жёсткие требования по быстродействию.

а зачем так часто?
я вывожу на экран 3 раза в секунду, вместе с обработкой кнопок или энкодера, чтобы сразу видеть результат действия кнопок и энкодера. чаще выводить вообще нет никакого смысла.
да и сильно высокого быстродействия тоже не нужно.
в системах реального времени после прохода полного программного цикла процессор все равно "топчется на месте" в ожидании начала следующего временного интервала.
например, у меня программный таймер отрабатывает интервалы по 10 мс. а полный цикл, вместе с выводом на экран 1602 по довольно медленному протоколу I2C занимает примерно 6,5 мс (точно уже не помню). и оставшиеся 3,5 мс процессор топчется на месте, ожидая наступление следующего 10-миллисекундного интервала.
так куда тут спешить с преобразованием числа в отдельные цифры?
тем более, с огромными затратами на вывод 32 символов вместе с командами позиционирования курсора по I2C...
так что, твоя гонка за производительность такого преобразования вообще не имеет смысла.
даже с внутренним генератором на 1 МГц у меня всегда оставался огромный запас времени, чтобы потоптаться на месте в ожидании окончания временного интервала.
а поскольку мне спешить некуда, то для меня важнее минимальная длина кода всей программы.
тут я раньше (но не помню где) показывал свой алгоритм разбиения числа на цифры с вызовом подпрограмм деления. а деление, как известно, занимает много времени.
но меня на общем времени выполнения всей нужной работы потеря времени на несколько операций деления никогда не лимитировала.

а ты можешь назвать такую программу (прошивку), где потеря 200 тактов процессора была бы катастрофической?

Я как-то изобретал частотомер по принципу взаимообоюдного счёта (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 ; Конец процедуры ;==============

Последний раз редактировалось B@R5uk Вт июн 25, 2019 16:27:51, всего редактировалось 1 раз.

Я вот на что обратил внимание. Тут приводится количество тактов в примерах. Есть но, вы привели голые примеры. Результаты преобразования чисел временные. Нет никакого смысла держать их в регистрах. Понимаю, что проекты разные, есть мк с маленьким объёмом ОЗУ. Но это не так часто. Поэтому: в примерах нет сохранения, восстановления регистров. Команд чтения записи в из ОЗУ. Лично я привёл свой пример полностью. И в моем примере ещё и прибавление 0x30 к разрядам чисел для вывода на дисплей.

чтение/запись в/из ОЗУ и прибавление 0x30 к разрядам чисел будут ВСЕГДА, поэтому при сравнении алгоритмов нет смысла прибавлять эти такты.
а сохранение и восстановление регистров - не факт, что могут понадобиться при выводе числа на дисплей.
и сохранение и восстановление регистров не имеют никакого отношения к собственной длине алгоритма преобразования.

Demiurg, вы просто не читали мои примеры. Вернее, читали только первый и предыдущий посты, где я привёл код для преобразования байта. В листингах для преобразования слова у меня результаты сохраняются в ОЗУ, это просто необходимость, позволяющая обойтись меньшим числом рабочих регистров.

Так же, я не согласен с тем, что прибавление 0x30 будет всегда. Для вывода результата на семисегментник скорее "голые цифры" результата будут использоваться как индексы кода семисегментника в таблице, расположенной в ПЗУ МК. Для сравнения быстродействия алгоритмов важнее не конечная длительность выполнения со всеми тонкостями конкретной реализации, а разница между длинами выполнения смыслового ядра алгоритма. Другое дело, когда я привёл один вариант оформления, вы — другой, то будет невозможно сделать сравнительный анализ. По этой причине я переписал все предыдущие варианты на свой лад в одном стиле; как раз чтобы было удобно сравнивать их преимущества и недостатки. (За одно и поднаучился чему-нибудь новому). Впрочем, как заметил Starichok51, даже здесь есть подвох: можно переписать алгоритм, развернув и упростив циклы, сэкономив время, а можно сделать вызов процедур для часто повторяющегося кода и сэкономить место.

Ассемблер дело такое... многогранное. Зависит от многих факторов. Размер Flash, SRAM микроконтроллера. Проект. Быстродействие, размер всего куска кода. Я всего лишь показал, что когда указываете количество тактов и размер куска кода, честно указывайте сопутствующие накладные расходы.
Я на асме плотно сидел более 10 лет. Под конец реализовывал древовидные меню и именно эта соломинка сломала хребет верблюду. После этого я пересел на си.

Поковырялся я тут и написал процедуры преобразования 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 ;==============

Надеюсь, нигде не накосячил, если что, проверяйте. :tea:

Добавлено after 17 minutes 38 seconds:

akl писал(а):

Метод последовательного вычитания быстр и начинает проигрывать при преобразовании больших чисел, когда вес оных превышает возможности ассемблера (4 байта). Пользуюсь и тем и другим.
Например, преобразование 40 разрядного числа только на старшей части регистрового файла AVR.

{код Double Dabble}

Всё с точностью наоборот. Если для одного байта метод Double Dabble ещё может поконкурировать с методом вычитаний (смотри мой код выше), то для бо́льшего числа байтов он сильно проигрывает, и чем дальше — тем сильнее. И это не удивительно. Каждый новый байт преобразуемого числа добавляет 2,5 разряда десятичного числа. А два разряда — это 5 операций с прибавлением/вычитанием троек и две операции сдвига. Плюс 8 новых итераций всего цикла. Квадратичная сложность + нерациональное исполнение = большой код и ещё большее время выполнения. В то время как для метода вычитаний цикл становится длиннее всего на одну итерацию, а общее число циклов увеличивается на 2.

Метод Double Dabble, на сколько я понимаю, хорош для аппаратного преобразования двоичных чисел в десятичные. При этом то, что делается в коде с помощью последовательных сложений/вычитаний по условию, в железе будет выполняться одновременно с помощью блоков жёсткой логики. Синхронный регистр надо будет протактировать ровно столько раз, сколько двоичных разрядов в исходном числе. Сложность получается линейная, а не квадратичная, как при написании программы для МК.

Пока получается, что метод вычитаний практически вне конкуренции. Мои попытки реализовать метод деления с остатком, конечно, дают результат, но он мне пока не кажется очень уж убедительным. Интересно, есть ли какие-нибудь другие методы преобразования?

B@R5uk писал(а):

Интересно, есть ли какие-нибудь другие методы преобразования?

Вот тут подборка по разным методам.

Приводимый ниже рекордно быстрый алгоритм годится только для архитектуры MSP430X. В ней имеется таймер реального времени RTC_B, в состав которого входит регистр BIN2BCD. Странно, что в документации slau272a и slau208k на семействa F5xx/F6xx и FR57xx, соответственно, об этом регистре нет ни слова в тексте. Есть лишь краткое упоминание этого регистра в составе регистров RTC, где ему посвящено лишь одно предложение, поэтому его очень легко не заметить. Согласно ДШ, в этот регистр следует сначала записать 12-битное число, а при чтении из него получите 16-битное BCD этого числа. Проще не бывает. Вот пример преобразования 12-битного числа в R4 в BCD в R5. Процедура занимает всего 6 циклов !!!

Код:: mov.w R4, &BIN2BCD mov.w &BIN2BCD, R5

Почему в документации упомянуты лишь 12-битные исходные числа? Ведь максимальное 12-битное число - это 4095, а четырех BCD знаков в 16-битном регистре достаточно для представления чисел вплоть до 9999. Это для меня осталось загадкой. Я попробовал переводить числа вплоть до 9999 - все действительно работает! Более того, оказалось, что при записи в этот регистр чисел от 10000 до 16383 (т.е. 14-битных) в регистре остается лишь последние 4 цифры BCD, а для чисел от 16384 до 65535 процессор оставляет лишь 14 младших бит числа и переводит полученный результат в BCD. Я проверял всё это на процессоре MSP430FR5728

Ser60 писал(а):

Вот тут подборка по разным методам.

Спасибо! Там есть действительно интересные подходы. Попробую что-нибудь замутить. Например, деление с остатком на 10 с помощью сдвигов и сложений весьма интригует.

cpi tmp1, 0x0A ; Повтор цикла, пока остатком
brne loop_1 ; не станут единицы

во-первых, нельзя проверять только младший байт, при этом tmp2 и tmp3 могут быть не равны нулю.
во-вторых, почему ты решил, что в остатке должно быть РОВНО 10 (проверка на неравенство)?
в-третьих, в погоне за уменьшением количества программных строк (размера кода) ты тратишь лишнее время на вычитание и последующего сложение всех трех байт, когда старший и средний байты уже равны нулю и из них вычитать ничего не надо.

Starichok51 писал(а):

во-первых, нельзя проверять только младший байт, при этом tmp2 и tmp3 могут быть не равны нулю.
во-вторых, почему ты решил, что в остатке должно быть РОВНО 10

Потому что, когда делитель станет равен 10, то остатком будут единицы. Регистры tmpX — это делитель, степени десятки, которые загружаются из памяти. И только один из них (последний) имеет в качестве младшего байта величину 0x0A. Пожалуй, не очень удачный комментарий у меня получился.

Добавлено after 8 minutes 14 seconds:

Starichok51 писал(а):

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

Сначала хотел сделать пачку циклов, но потом подумал, что формула для времени перестанет быть простой и красивой, а код будет длинным, и сделал как сделал. Там ещё куча времени сэкономится на загрузке из памяти: вместо трёх тактов операция займёт один, и количество загрузок будет не три для всех циклов, а от трёх до одной.

Добавлено after 3 minutes 31 second:
Starichok51, спасибо, что проявляете интерес и контролируете код. :)))

В чужом коде разбираться — тот ещё труд, по себе знаю.

B@R5uk писал(а):Регистры tmpX — это делитель,

пардон, перепутал регистры, извиняюсь.

B@R5uk писал(а):Там ещё куча времени сэкономится на загрузке из памяти: вместо трёх тактов операция займёт один

с загрузкой таблицы из памяти очень невыгодное решение в плане производительности - команда LPM выполняется за 3 машинных цикла (ну, пусть будем их звать тактами). а загрузка непосредственного операнда занимает 1 машинный цикл (такт).
но поскольку ты решил обойтись одним циклом, то такая потеря времени на загрузку из программной памяти неизбежна.
да на хрена тебе и всем нам красивая формула? ты, что ли, гонишься за красотой формулы или за скоростью алгоритма?
и не обязательно делать 7 циклов.
будет один цикл в 3 прохода, когда нужно вычитать 3 байта (10 миллионов, 1 миллион и 100 тысяч),
1 цикл в 2 прохода (10 тысяч и 1 тысяча),
1 цикл в 2 прохода (100 и 10).

Ser60 писал(а):

В ней имеется таймер реального времени RTC_B, в состав которого входит регистр BIN2BCD.

Необходимость быстрого преобразования двоичного кода в двоично-десятичный достаточно экзотична в отношении задач на МК и зависит от реализации этих задач.
Немного поясню.
Быстрое преобразование BIN2BCD позволяет сэкономить энергию автономного химического источника и совершенно никак не влияет на общую скорость выполнения общей задачи. Десятичное представление нужно для восприятия величин человеком, реакция которого в части этого восприятия составляет порядки СЕКУНДЫ. Что делает усилия по увеличению скорости этого преобразования практически бессмысленными.
С другой стороны, для построения часов реального времени разрядность счета этого времени будет определять требования к процедуре BIN2BCD и в коде и в железе.
Это я к тому, что счет времени посредством раздельных переменных для секунд-минут-часов-... позволяет отказаться от многоразрядного BIN2BCD. Так в совершенно древних МК существует команда десятичной настройки DAW, которая в один машинный цикл превращает двоичное число в диапазоне 0х00 ... 0х63 в тетрадно-десятичное число 00 ... 99.

про реакцию человека правильно замечено.
и не только зрительное восприятие, но и при работе с кнопками скорость владения пальцами у обычных людей не слишком шустрая.
поэтому я не встречал промышленных приборов, где вывод на дисплей (экран и т.п.) составляет более 3 раз в секунду.
и я в своих поделках обрабатываю кнопки и энкодер и вывожу на экран 3 раза в секунду.
поэтому большая скорость преобразования чисел в символы тут совершенно не нужна.
и это не обязательно, что это будут ЧАСЫ.
любой прибор обязан функционировать в реальном времени. для этого он обычно тактируется аппаратным таймером и программным таймером.
аппаратный таймер отмеряет малые промежутки времени и делает другую необходимую работу.
программный таймер отрабатывает большой промежуток времени и определяет весь программный цикл в реальном времени.
причем полное время программного цикла всегда делается так, что оно больше времени работы всего кода. а далее процессор "топчется на месте", ожидая конца программного цикла.
это общее правило грамотного построения программы (прошивки).
а поскольку у нас всегда имеется приличный запас времени до конца программного цикла, то тем более незачем спешить с преобразованием чисел в символы.
я рассматриваю это тему, как "академический" интерес в создании быстрого алгоритма. но практического смысла от этой быстроты я не вижу.
поэтому в своих изделиях я применяю последовательное деление на 10, получая в остатке следующую цифру, начиная с самой младшей.
да, подпрограмма деления "медленная", но на общем фоне программного цикла это вообще не имеет никакого значения.

Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры

Re: Преобразование байта в три десятичные цифры