BCD арифметика для реализации МК61 на msp430

Пишу на msp430 симулятор МК61. Микроконтроллеры msp430 имеют возможность складывать 4-разрядные BCD числа, команда dadd SRC,TRG складывает SRC с TRG и флагом переноса CARRY. Хотелось бы выйти на максимально эффективный алгоритм умножения (пока только мантиссы), использующийся сейчас школьный алгоритм (умножение столбиком) на умножение двух 8-разрядных чисел расходует 784 такта без нормализации получившегося числа. При этом приходится использовать 16 разрядные BCD источник и приемник размещенные в регистрах msp430 (благо их хватило). Ассемблерный лист привожу. Вижу как улучшить основной цикл умножения - но только на один такт, но это касается только оптимизации по командам. Знаю что можно использовать аппаратное умножение старших моделей семейства msp430 но, это будет а) не спортивно и б) не нативно задуманному BCD ядру. Приглашаю желающих присоединиться.

;
; множимое  R4:R5:R6:R7
; множитель R8:R9
;  промежуточное слагаемое для i разряда умножения R10:R11:R12:R13
;  счетчик множителя i разряда R14

; загружаем множимое
                mov.w   #0,             R4                      ; 1T
                mov.w   #0,             R5                      ; 1T
                mov.w   @SP61+,         R6
                mov.w   @SP61,          R7
; загружаем множитель
                mov.w   @IXP+,          R8
                mov.w   @IXP,           R9

                push.w  R10
                push.w  R11

; очистка промежуточного слагаемого
                mov.w   #0,             R10                     ; 1T
                mov.w   #0,             R11                     ; 1T
                mov.w   #0,             R12                     ; 1T
                mov.w   #0,             R13                     ; 1T
                mov.w   #0x000F,        R15                     ; 2T

                jmp     loop_mul_while
loop_mul:
                mov.w   R9,             R14                     ; 1T установка разрядного счетчика
                clrc                                            ; 1T
; / делим на 10 множитель
                rrc.w   R8                                      ; 1T
                rrc.w   R9                                      ; 1T
                rra.w   R8                                      ; 1T
                rrc.w   R9                                      ; 1T
                rra.w   R8                                      ; 1T
                rrc.w   R9                                      ; 1T
                rra.w   R8                                      ; 1T
                rrc.w   R9                                      ; 1T =8T

                and.w   R15,            R14                     ; 1T
                xor.w   #0xFFFF,        R14                     ; 1T подготовка разрядного счетчика
                add.w   #1,             R14                     ; 1T к инкременту до 0 (-R14)
                jc      loop_mul_end                            ; 2T R==0 mul abort
loop_mul_beg:
                dadd.w  R7,             R13                     ; 1T   CARRY=0
                dadd.w  R6,             R12                     ; 1T
                dadd.w  R5,             R11                     ; 1T
                dadd.w  R4,             R10                     ; 1T R4:R5:R6:R7 + R10:R11:R12:R13
                add.w   #1,             R14                     ; 1T увеличиваем разрядный счетчик
                jnc     loop_mul_beg                            ; 2T =7T

loop_mul_end:
; Переходим к следующему разряду множителя, то есть множимое * 10
                add.w   R7,             R7                      ; 1T
                addc.w  R6,             R6                      ; 1T
                addc.w  R5,             R5                      ; 1T
                addc.w  R4,             R4                      ; 1T
                add.w   R7,             R7                      ; 1T
                addc.w  R6,             R6                      ; 1T
                addc.w  R5,             R5                      ; 1T
                addc.w  R4,             R4                      ; 1T
                add.w   R7,             R7                      ; 1T
                addc.w  R6,             R6                      ; 1T
                addc.w  R5,             R5                      ; 1T
                addc.w  R4,             R4                      ; 1T
                add.w   R7,             R7                      ; 1T
                addc.w  R6,             R6                      ; 1T
                addc.w  R5,             R5                      ; 1T
                addc.w  R4,             R4                      ; 1T =16T
loop_mul_while:
                mov.w   R8,             R14                     ; 1T
                bis.w   R9,             R14                     ; 1T
                and.w   R14,            R14                     ; 1T множитель равен 0, исчерпан
                jnz     loop_mul                                ; 2T

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

https://vgsemenov.wordpress.com/2011/11/08/%D0%B0%D0%BB%D0%B3%D0%BE%D1%8...

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

То есть решили не заморачиваться с арифметикой в десятичной системе, а работать через переходник? Потерю точности учли? Исходный FP какой разрядности?

Исходное число одинарной точности (в имеющемся процессоре "плавающие" команды есть).
Я так понял диапазон порядка 2^127=1,7*10^38, не ясно как увязать это с мантиссой при преобразовании? Простое преобразование BIN>BCD у меня вопросов не вызывает.

Откуда такой диапазон взят? С одинарной точностью смысла нет симулить МК61.

Диапазон чисел, с которыми производит вычисления библиотека FPP одинарной точности.

Наибольшее положительное число
Двоичное : FF7FFFFFh
Десятичное : 3.402823 x 10 38

Наименьшее положительное число
Двоичное : 00000001h
Десятичное : 2.938736 x 10 -39
Ноль : 00000000h, 0 = 0.0

Наименьшее отрицательное число
Двоичное :00800000h
Десятичное :-2.938736 x 10 -39

Наибольшее отрицательное число
Двоичное : FFFFFFFFh
Десятичное :-3.402823 x 10 38

Разрешение: 119.2093 x 10 -9 2 е.

Тут все процедуры в том числе и конверсии из FPP -> BCD
http://www.gaw.ru/html.cgi/txt/soft/MSP430/lib.htm

В имеющемся процессоре есть блок только одинарной точности, но он умеет выполнять четыре действия арифметики. Я сейчас занялся изучением его ассемблера из-за явной неэффективности си-компилятора по причине экзотической архитектуры мультиклетовского процессора. Тест "Счастливые билеты" на си показал около 10млн. оп./с на 80МГц. В связи с изучением ассемблера понадобилось разбираться с преобразованиями, ранее сталкивался с преобразованием только целых чисел при пересчёте замеров АЦП в милливольты.
Сейчас уже новая модель есть с двойной точностью, но у меня в наличии есть только платка со старым кристаллом, которую изначально приобретал чисто на опыты.
На МК-61 я пока даже не замахиваюсь :)
На мой взгляд, десятичное представление нужно только для ввода-вывода, а внутри можно и в двоичном виде считать, это заметно упростит алгоритмы.

Электромонтёр wrote: Тест "Счастливые билеты" на си показал около 10млн. оп./с на 80МГц.

Я его почему то не нашел не могли бы поточней заслать, по ссылке только тест счастливые билеты для МК61.

Электромонтёр wrote: На МК-61 я пока даже не замахиваюсь :)

А хотелось бы замахнуться? На мультиклете конечно совершенно не к чему, не то это чудо что бы на нем кальк делать. Вот интересно было бы на чем нибудь с DSP сделать, типа Элвиса :) тоже кстати из Свердловска контора как и мультиклетчики.

Электромонтёр wrote: На мой взгляд, десятичное представление нужно только для ввода-вывода, а внутри можно и в двоичном виде считать, это заметно упростит алгоритмы.

Нет тут к сожалению есть подводные камни в далеком прошлом читал статью про десятичную и бинарную арифметику (http://www.yur.ru/science/computer/IEEE754.htm), совсем не зря во все камни (8080, Z80, M68K) той эпохи включали команды двоично десятиной арифметики.

Здесь
С мультиклетом пока ассемблер разбираю, пока что пустой цикл 20 тактов жрёт, не пойму почему. Понятно, что раскидывания по клеткам нет, но 20 тактов!!! Весь цикл пять (микро)команд! Да, вдвое шустрее, чем на сях, но почему только вдвое?
Вообще мультиклет мне напоминает... ну RISC-ядро х86 процессора, с выброшенным транслятором х86 CISC команд, а мультиклетовцы предлагают писать программу из самодельных команд ("параграфов") из отдельных микрокоманд ("выражений"), зато есть неявный многопортовый регистровый файл, хранящий 63 (35, еррата!) последних результатов, но пользоваться им можно только внутри команд ("параграфов"). Распараллеливание есть, но с ограничениями, многоклеточность скрыта от программиста, но при написании микропрограмм про неё надо помнить.

Нашел на хабре еще более замечательную статью про плавучку в IEEE754 https://habrahabr.ru/post/112953/
смотрите раздел

4. Подводные камни в арифметике с плавающей запятой

Со скрипом вспоминаю лекции по АЛУ ЦВМ почти 25-летней давности, поэтому просьба сказать, где я ошибаюсь.

При двоичном умножении частичное произведение сдвигается на один разряд влево для каждого последующего разряда множителя. Если множитель равен 0, то частичное произведение равно 0; если множитель равен 1, то частичное произведение равно множимому.

Т.о. умножение двух 8-разрядных десятичных (?) чисел (тогда по 32 бита каждое) должно бы происходить примерно за 32*3=96 тактов (сравнение, сдвиг, сложение - на каждый разряд). Откуда получается 784 такта? Из-за двоично-десятичной формы?

    101 (5)
  *
   1010 (10)
  -----
    000  
   101
  000
 101
-------
110010  (50)

Сергей условно делаю так:
беру первый разряд множителя Mi, суммирую Mi раз Множимое двоично-десятичной командой суммирования DADD. Переход к следующему разряду Множителя Mi+1, вызывает сдвиг на десятичный разряд (т.е. по сути умножение на 10) множимого и опять суммирование Mi+1 раз. И так до последнего разряда Множителя M[8].

С двоичными да, понятно дальше некуда 1 в разряде множителя - суммируем множимое, сдвинутое на 1 разряд, 0 - в разряде множителя, суммируем 0 (т.е. вообще не суммируем ни чего).

Какие сложности с BCD:
1. В разряде не 0 или 1, а 4 бита от 0 до 9, поэтому приходится складывать от 0 до 9 раз
2. Сдвиг надо делать не на 1 бит, а на 4
3. Так как множимое двигается вправо, нужно обеспечить с права дополнительную разрядную сетку а значит двигаем всю разрядную сетку, а это 4 регистра 16-битных на 4 бита, соответсвенно 4х4 сдвига для множимого каждую итерацию.
4. Вероятно я чего то не понимаю и скорее всего есть более правильный и быстрый метод. Мне не нравится что я циклически складываю множимое Mi раз. Тут как раз и сидит наибольшая задержка так как сетка 64 битная т.е. все те же 4 регистра слагаемого, складываемые Mi раз итого 7 тактов (4 сложения 1 инкремент итератора 2 цикловый переход). 7 тактов на разряд казалось бы не так уж и много, однако в каждом может быть от 0 до 9, значит 9*7 - 63 такта. Разрядов 8 - а значит 63*8 = 504. Плюс сдвиг на 4х4 при переходах к следующему разряду множителя и промежуточному сложению.

Может быть отказаться тогда от использования BCD, если в итоге выходит сложнее? Я не вникал в архитектуру msp. Он 32-разрядный, вроде, на уровне регистров? Реализовать "классические" битовые сдвиги-сложения.

msp430 16 разрядный, регистры 16 разрядные.

Я не знаю что сказать, пока еще не готов "пасануть" :)

Опять же одинарной точности не подойдут FP, нужны двойной точности FP, мантисса 52 бита - как я понимаю для умножения придется воспользоваться удвоенной сеткой 52+52 = 104 разряда. 104 суммирования, 104 сдвига. Как минимум в районе 300 тактов. Обязательная трансляция в BCD. Ну если упрусь в стенку, придется в double уходить.

Временное-вещественное? 64бит мантисса и 16 бит порядок? Тогда можно пользовать команду умножение для ускорения, правда деление придётся в "классическом" виде организовывать... Или командой умножения всё-таки можно деление ускорить?
Интересен метод округления вещественных чисел - до ближайшего чётного, считается менее склонным к накоплению ошибок.

Электромонтёр wrote: Временное-вещественное?

Это что такое? почему Временное?

Электромонтёр wrote: 64бит мантисса и 16 бит порядок? Тогда можно пользовать команду умножение для ускорения,

Почему 64 бита? У дабла 52 бита мантисса, 64 бита оно все и мантисса и знак и порядок. Безусловно умножение аппаратное нужно использовать, если этот модуль есть. Я думаю там стандартные библиотеки и скорей всего нужно будет просто расслабиться перейти в Си и писать. Будет ужасно не эффективно - но... селя ви...

Электромонтёр wrote: правда деление придётся в "классическом" виде организовывать... Или командой умножения всё-таки можно деление ускорить?
Интересен метод округления вещественных чисел - до ближайшего чётного, считается менее склонным к накоплению ошибок.

Вот тут скажу что вся IEEE754 от ошибок округления не застрахована, по сравнению с BCD она будет врать на больших числах, что кстати показывают многие тесты калькуляторов от Фролова. Он как раз так проверяет какая арифметика используется :) Деление умножением не ускоришь, тем паче что оно уже будет в библиотеки для msp430 под double fp. Эххх ну это же будет просто монстроидальный размер прошивки, мелкие FRAM контроллеры на 16Кб отвалятся прям сразу же.

Это из описания форматов чисел с плавающей запятой 32 бит короткое вещественное ( одинарной точности ), 64 бита длинное вещественное ( двойной точности ) и 80 бит временное вещественное - внутренний формат сопроцессора i8087, почему такие названия, это наверное к интеловцам.
Почему 80 бит 64 бита мантисса и 16 бит порядок кратно 16 битной разрядности кристалла.
Энтузиаст цифровой радиосвязи столкнулся с тормозами вокодера из сишных сорцов на 200МГц ARM Cortex F4, начал разбираться, оказывается автор кодека использовал функцию возведения во вторую степень, которая и тормозила алгоритм, после замены её в ассемблере на умножения на себя (для возведения в квадрат) вокодер заработал на 60МГц!
Я выкладывал заметку с замерами быстродействия возведения в степень МК-161, так там два алгоритма для возведения в целую и дробную часть.
Кстати, попробуйте замерить быстродействие вашего мк на счастливых билетах, я свой вариант выкладывал, можно оценить эффективность компилятора, мой компилятор по быстродействию ужасен.

Электромонтёр wrote: Это из описания форматов чисел с плавающей запятой 32 бит короткое вещественное ( одинарной точности ), 64 бита длинное вещественное ( двойной точности ) и 80 бит временное вещественное - внутренний формат сопроцессора i8087, почему такие названия, это наверное к интеловцам.

Extended precision

Quote: The x86 extended precision format is an 80-bit format first implemented in the Intel 8087 math coprocessor and is supported by all processors that are based on the x86 design which incorporate a floating-point unit (FPU).

Электромонтёр wrote: Кстати, попробуйте замерить быстродействие вашего мк на счастливых билетах, я свой вариант выкладывал, можно оценить эффективность компилятора, мой компилятор по быстродействию ужасен.

То есть - есть тест на Си для счастливых билетов работающих с double fp?

Тест предельно простой, для оценки эффективности компиляторов, можно замерить время выполнения и оценить быстродействие микроконтроллера с компилированной сишной програмой.

Для двойной точности (double) согласно IEEE-754 нужно 8 байт (64-бита). По точности (15 цифр мантиссы и 3 порядка) это перекрывает МК61 с большим запасом. Если не привязываться к стандарту, то 5 байт на мантиссу и 1 на порядок дают 8-9 цифр порядка и 2-3 мантиссы.

Весь кайф будет ломать перевод в BCD, поскольку деление на 10 двоичного числа иногда идет с потерей точности (а иногда как я понимаю там вообще периодичная дробь). Фролов каким то очень бесхитростным тестом что то там e^X, а затем ln получившегося результата - показывал что на массе кальков не получается исходного числа, в отличие от МК61 :)

Один из подходов обсуждался в НиЖ 1980-х, в калькуляторах есть т.н. скрытые разряды, повышающие точность видимого числа. В инженерном МК-51 их было 2, как я помню. Там же был метод вычисления "цифра за цифрой". Можно поднять подшивку и посмотреть. Обнаружить их несложно: надо проделать цепочку вычислений потом вычесть из результата видимое на индикаторе число.
Что использовалось в МК-61 сказать затрудняюсь, на эмуляторе скрытых разрядов не видно.