Forth
http://fforum.winglion.ru/

Задача: Сложить два числа
http://fforum.winglion.ru/viewtopic.php?f=19&t=2810
Страница 1 из 1

Автор:  WingLion [ Сб фев 18, 2012 15:59 ]
Заголовок сообщения:  Задача: Сложить два числа

Да-да, именно сложить два числа.
Условие:

1. на стеке лежат адреса двух многоразрядных чисел (беззнаковые целые с количеством разрядов 16*N, N задано изначально)
Достаточно получить решение для N=4,8,16 и не обязательно для всех остальных.
2. Надо эти два числа сложить имея 16 разрядный процессор с минимальным набором Форт-команд:
DUP DROP, SWAP, >R, R>, - стандартные
BSWAP - обмен байтов в слове на вершине стека
ADD, SUB, AND, OR, XOR, - стандартные
@, !, - стандартные
LIT, - 16-битный литерал
CALL, - вызов подпрограммы
RET, - возврат из подпрограммы
JMPZ, - переход, если на стеке 0 (флаг со стека не убирается)
JMPZm, - переход, если на стеке 0 (флаг со стека убирается)
NOP - нет операции
(Последнее для задачи явно не нужно, но из песни (процессора) слов не выкинешь)

Все команды шестнадцатиразрядные, флага переноса нет

Результатом должна быть сумма, расположенная на месте одного из операндов
Ограничений на занимаемую память формально нет. Можно делать переменные, константы, буферы и т.п. нельзя только наглеть и делать мега/гигабайтные таблицы.
Так же нельзя делать циклы, ожидающие, когда помрет Ишак или Эмир...

Автор:  Hishnik [ Сб фев 18, 2012 17:22 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

Если речь о форт-процессоре, можно организовать флаг переноса. Но если все-таки не хочется, имитируем перенос на 8-битных порциях - складываем младшие байты, если больше 255, то запоминаем эту единичку в переменной, прикидывающуюся флагом переноса.

Автор:  WingLion [ Сб фев 18, 2012 17:35 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

Хищник писал(а):
Если речь о форт-процессоре, можно организовать флаг переноса. Но если все-таки не хочется, имитируем перенос на 8-битных порциях - складываем младшие байты, если больше 255, то запоминаем эту единичку в переменной, прикидывающуюся флагом переноса.


Во-во... Я эту тему поднял только лишь потому, что на другом форуме в обсуждении форт-процессора один "знаток" заявляет, что там этого сделать нельзя (флаг переноса реализовать на VHDL - для него проблема, а складывать не имея флага переноса он не умеет)

: ADC ... ; \ место под определение команды сложения с переносом

: ADD_N \ сложение N-словных чисел
0 >R \ закидываем на стек возвратов нулевой флаг переноса
\ ------
OVER @ OVER @ \ достаем первые слова операндов
ADC \ складываем - этой операции нет в процесоре, но она эмулируется программно
\ при этом используется флаг переноса на стеке возвратов и туда же он
\ записывается после исполнения сложения
OVER ! \ достаем адрес второго операнда и записываем в него результат
1+ SWAP 1+ SWAP \ увеличиваем адреса, чтобы достать следующие слова операндов
\ повторяем N раз в коде все от \ --- до этого места
\ или организовываем цикл
; \ завершаем фортовое определение

Автор:  gudleifr [ Сб фев 18, 2012 17:46 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

Хищник писал(а):
если больше 255, то запоминаем эту единичку в переменной, прикидывающуюся флагом переноса.
Это называется "полусумматор". Cравнений и переменных там не надо, просто два сложения - сначала с "флагом", затем со следующим
байтом. Возможно, проще будет сначала слагаемые "разрядить" (XXYY -- 00XX 00YY). Кстати, надо учесть, что порядок байтов в слове для разных процессоров может отличаться.

Автор:  Hishnik [ Сб фев 18, 2012 17:47 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

WingLion писал(а):
флаг переноса реализовать на VHDL - для него проблема

В XST (который основной синтезатор в ISE) при сложении 16-разрядных чисел можно получить как 16-разрядный результат, так и 17-разрядный.

Код:
signal sum : std_logic_vector(16 downto 0); --  тут 17 разрядов
signal a, b : std_logic_vector(15 downto 0); -- а тут 16

...

sum <= a + b;

В старшем разряде sum бит переноса появится сам собой. Если же sum будет определен как 15 downto 0, бит переноса проигнорируется.

Автор:  Hishnik [ Сб фев 18, 2012 17:50 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

gudleifr писал(а):
Cравнений и переменных там не надо, просто два сложения - сначала с "флагом", затем со следующим
байтом.

Это уже вопросы улучшения кода. Часто сначала удобнее написать "лобовое" решение, которое позволит увидеть каждое действие воочию. А потом уже будем добиваться такого же результата, но более эффективно.

Автор:  WingLion [ Сб фев 18, 2012 18:40 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

: ADCB \ на стеке два слова с зануленными старшими байтами
ADD \ простое сложение
R> \ читаем флаг со стека возвратов
IF 1+ THEN \ прибавляем единицу, если флаг был взведен
\ кто не знает, как на форт-процессоре элементарный
\ оператор IF делается - идет лесом-лесом-налево-направо-и-снова-лесом
DUP FF00 AND \ вытаскивание переноса
>R \ и сохранение его на стеке возвратов
0FF AND \ результат в младшем байте
; \ конец определения сложения двух байтов с переносом

: ADC \ сложение двух слов с переносом
OVER @ 0FF AND \ достаем первый байт операнда 1
OVER @ 0FF AND \ достаем первый байт операнда 2
ADCB \ складываем байты с переносом
\ перенос на стеке возвратов результат не больше байта
OVER @ FF00 AND OR \ микшируем частичный результат
OVER ! \ и записываем его
OVER @ BSWAP 0FF AND \ достаем второй байт операнда 1
OVER @ BSWAP 0FF AND \ достаем второй байт операнда 2
ADCB \ складываем байты с переносом перенос на стеке возвратов
BSWAP \ результат пермещаем в старший байт
OVER @ 0FF AND OR \ микшируем вторую часть результата
OVER ! \ и записываем его
; \ заканчиваем определение

Автор:  in4 [ Вс фев 19, 2012 14:29 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

WingLion писал(а):
: ADCB \ на стеке два слова с зануленными старшими байтами
ADD \ простое сложение
R> \ читаем флаг со стека возвратов
IF 1+ THEN \ прибавляем единицу, если флаг был взведен

Если флаг представлен 0..1, то можно его просто прибавлять, не проверяя IF-ом!
Например, так:
Код:
BSWAP ADD

Автор:  WingLion [ Вс фев 19, 2012 18:20 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

in4 писал(а):
Если флаг представлен 0..1, то можно его просто прибавлять, не проверяя IF-ом!


Тогда IF перелезет на проверку результата и превращение переноса со значением 256 в единицу.

Автор:  in4 [ Чт фев 23, 2012 18:45 ]
Заголовок сообщения:  Re: Задача: Сложить два числа

Не перелезет, IF вообще не будет нужен! Нет переноса (флаг =0) - его прибавление ничего не изменит. Есть перенос (флаг =1) - он прибавлением и учтется.
Может, не заметился BSWAP , который переносит перенос в младший байт?

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

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/