*битовое отражение числа

mOleg

Произвести операцию битового отражения чисел двоичного числа, например, 011001010 --> 010100110.
Для массива чисел указанного размера size#, состоящего из указанного количества ячеек (CELLS).

\ для массива addr # произвести битовый реверс ячеек
: revarr ( addr # --> )
         ;

заклинания для ком.строки и тест находятся здесь: http://www.forth.org.ru/~mOleg/samples/2007-11-11/
Да. Предполагается, что задачка решается на SPF4.18,
а так же, что у вас последнее обновление содержимого папки devel с cvs (не ранее 1.11.07).

WingLion

Код:

HEX

: REVERSE_BITS
 DUP 1 LSHIFT  АААААААА AND SWAP 55555555 AND OR
 DUP 2 LSHIFT  CCCCCCCC AND SWAP 33333333 AND OR
 DUP 4 LSHIFT  F0F0F0F0 AND SWAP 0F0F0F0F AND OR
 DUP 8 LSHIFT  FF00FF00 AND SWAP 00FF00FF AND OR 
 DUP 10 LSHIFT  FFFF0000 AND SWAP 0000FFFF AND OR ;

если не наврал...

mOleg

не самое скоростное лобовое решение:

Код:

\ 11-11-2007 ~mOleg
\ Copyright [C] 2007 mOleg mininoleg@yahoo.com
\ пример решения задачки с форума
\ http://fforum.winglion.ru/viewtopic.php?t=1022&start=0&postdays=0&postorder=asc&highlight=

 REQUIRE FOR  devel\~mOleg\lib\util\for-next.f

\ произвести реверс бит указанного числа
: revcell ( u --> u )
          0 32 FOR 2* OVER 1 AND OR
                   SWAP 2/ SWAP
               TILL NIP ;

\ для массива addr # произвести битовый реверс
: revarr ( addr # --> )
         FOR DUP @ revcell OVER !
             CELL +
         TILL DROP ;

WingLion

Интереснее было бы, наверно, преобразование массива с таким реверсированием индекса (для БПФ), хотя, БПФ на Форте, лучше делать все же на форт-процессоре со спецфункциями.

Кстати, лобовое реверсирование адреса тут не пройдет, потому что массив обычно много меньше чем 2<sup>32</sup> CELLS

mrack

битове отражение скольки битных слов ?
вобще помоему можно использовать таблицу в 256 байт для восьмибитовый конвертации.
в коей адрес отраженного байта соответствует величине отражаемого.
если слово длинее 8 бит использовать комбинированный вариант.

Код:

Извиняюсь за отсутствие кода :)

mOleg

mrack писал(а):

битове отражение скольки битных слов ?

речь идет о ячейках. То есть 32 битных чисел.

Alexander

Конечно мое решение неоригально...
Идея. Находить всякий раз старший значащий бит. поменять позиции единичек. сложить.
Старший значащий бит:

Код:

ICODE ?MSB-POSITION ( n1 -- n2 )
   32 # ECX MOV
1 L:
   EBX EBX ADD
   2 L# JC
   1 # ECX SUB
   1 L# JNZ
2 L:
   ECX EBX MOV
   RET
END-CODE

Степень числа, вспомогателное средство:

Код:

: POWER ( n1 u2 -- n1^u2 )
   1 SWAP  0 ?DO  OVER *  LOOP  NIP ;

Степени двойки:

Код:

CREATE 2POWER
   2 0 POWER ,  2 1 POWER ,  2 2 POWER ,  2 3 POWER ,
   2 4 POWER ,  2 5 POWER ,  2 6 POWER ,  2 7 POWER ,
   2 8 POWER ,  2 9 POWER ,  2 10 POWER ,  2 11 POWER ,
   2 12 POWER ,  2 13 POWER ,  2 14 POWER ,  2 15 POWER ,
   2 16 POWER ,  2 17 POWER ,  2 18 POWER ,  2 19 POWER ,
   2 20 POWER ,  2 21 POWER ,  2 22 POWER ,  2 23 POWER ,
   2 24 POWER ,  2 25 POWER ,  2 26 POWER ,  2 27 POWER ,
   2 28 POWER ,  2 29 POWER ,  2 30 POWER ,  2 31 POWER ,

Получение степени двойки, вспомогательное средство:

Код:

: 2^X CELLS 2POWER + @ ;

Получение позиций в которых стоят единички:

Код:

: PREPARE
   BEGIN  DUP ?MSB-POSITION  ?DUP NOT IF  DROP EXIT THEN TUCK 1- 2^X  -  ?DUP 0= UNTIL ;

Получение числа написанного задом наперед в двоичной системе:

Код:

: REVERSE
   PREPARE 0  BEGIN  DEPTH 1 > WHILE  SWAP 32 SWAP- 2^X  + REPEAT ;

p.s.: SWIFTFORTH

mOleg

Alexander писал(а):

Конечно мое решение неоригально...
Идея. Находить всякий раз старший значащий бит. поменять позиции единичек. сложить.

ээ. я не понял, что за задача решалась 8(
ТЗ в начале темы и там явно прописано главное слово, которое должно выполняться.

P.S. разве в SWIFTFORTH нет команд RSHIFT и LSTHIFT?

WingLion

что бы было яснее, что же я там такое написал:

Код:

 \ произвести реверс бит указанного числа

: revcell ( u --> u )
 DUP 1 LSHIFT  AAAAAAAA AND SWAP 55555555 AND OR
 DUP 2 LSHIFT  CCCCCCCC AND SWAP 33333333 AND OR
 DUP 4 LSHIFT  F0F0F0F0 AND SWAP 0F0F0F0F AND OR
 DUP 8 LSHIFT  FF00FF00 AND SWAP 00FF00FF AND OR
 DUP 10 LSHIFT  FFFF0000 AND SWAP 0000FFFF AND OR ; 

\ для массива addr # произвести битовый реверс
: revarr ( addr # --> )
         FOR DUP @ revcell OVER !
             CELL +
         TILL DROP ;

Выяснилось, что код этот не работает, потому что LSHIFT не циклический сдвиг...

и циклического в SPF-e еще нету...

mOleg

WingLion писал(а):

Выяснилось, что код этот не работает, потому что LSHIFT не циклический сдвиг...
и циклического в SPF-e еще нету...

уже есть:

Код:

<shift.f>
 
\ 24-06-2007 ~mOleg
\ Copyright [C] 2007 mOleg mininoleg@yahoo.com
\ различные сдвиги 32битных чисел
 
 REQUIRE STREAM[   devel\~mOleg\lib\arrays\stream.f
 
\ циклически сдвинуть число U на указанное число бит влево
: ROL ( U # --> U ) STREAM[ x8AC8 8B4500 8D6D04 D3C0 C3 ] ;
 
\ циклически сдвинуть число U на указанное число бит вправо
: ROR ( U # --> U ) STREAM[ x8AC8 8B4500 8D6D04 D3C8 C3 ] ;
 
\ арифметический сдвиг влево числа U на указанное # число бит
: SAL ( U # --> U ) STREAM[ x8AC8 8B4500 8D6D04 D3F0 C3 ] ;
 
\ арифметический сдвиг вправо числа U на указанное # число бит
: SAR ( U # --> U ) STREAM[ x8AC8 8B4500 8D6D04 D3F8 C3 ] ;
 
?DEFINED test{ \EOF -- тестовая секция ---------------------------------------
 
test{ 0x12345678 4 ROL 0x23456781 <> THROW
      0x12345678 4 ROR 0x81234567 <> THROW
      0xF0000000 3 SAR 0xFE000000 <> THROW
      0x70000001 3 SAL 0x80000008 <> THROW
  S" passed" TYPE
}test

Alexander

Не бейте меня...я тут новенький...
Как я понял решалась задачка заменить значение 32х разрядной ячейки на зеркальное (если так можно сказать), так вот это и реализовано.
К тому же при доработке можно использовать с ячейками другой разрядности.
А так каждый волен использовать, то что ему по душе.
Кстати, исправил ошибку при 0 на входе функции PREPARE см. выше
Про Ассемблерный код читаем документацию на Pentium 4 с сайта [url]developer.intel.com[/url]

mOleg

Alexander писал(а):

Не бейте меня...я тут новенький...

ни в коем случае!

Alexander писал(а):

Как я понял решалась задачка заменить значение 32х разрядной ячейки на зеркальное (если так можно сказать), так вот это и реализовано.

массива таких ячеек, и указано имя слова, которое должно получиться.

Alexander писал(а):

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

дык

Alexander писал(а):

Про Ассемблерный код читаем документацию на Pentium 4 с сайта [url]developer.intel.com[/url]

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

mrack

Код:

 HEX 
 
 \ создаем массив замены четырехбитных масок
 : dmk 
 F 7 B 3 D 5 9 1 E 6 A 2 C 4 8 0
 10 ALLOCATE THROW  10 0 DO DUP I +  ROT SWAP C! LOOP ; 
 dmk VALUE ddmk

 : revarr_ ( c -- c' )
   \ число со стека разлогаем на состовляющие 
   8 0 DO DUP 0x00000F AND SWAP 4 RSHIFT LOOP DROP
   \ состовляющие складываем в обратном порядке заменяя на зеркальные
   0 8 0 DO ddmk ROT + C@ I 4 * LSHIFT  + LOOP ; 
 
 \ собсттвено переработка массива  
 : revarr ( adr u -- )
   0 DO DUP I CELLS + DUP @ revarr_ SWAP ! LOOP DROP ;
 DECIMAL 

результат теста на скорость

на чом: intel Celeron M 1,5 ГГц ОЗУ 240МБ 
Calls       Ticks              AverageTicks     Name     (Rets)
mrack включен оптимизатор
       100 |      321,011,920 |      3,210,119 | sample 
mOleg  включен оптимизатор
       100 |      750,729,945 |      7,507,299 | sample

mrack

вариант без ду лупов

Код:

HEX
 : dmk ( -- )
   F 7 B 3 D 5 9 1 E 6 A 2 C 4 8 0
   10 ALLOCATE THROW 
   10 0 DO DUP I +  ROT SWAP C! LOOP ; 
   dmk VALUE ddmk
 
 : revarr_ ( c -- c' )
   0 SWAP 8 BEGIN >R DUP F AND ddmk + C@ R@ 1- 4 * LSHIFT ROT + SWAP 4 RSHIFT R> 1- DUP 0= UNTIL 2DROP ;
 
 : revarr ( adr u -- )
   BEGIN >R DUP R@ 1- CELLS + DUP @ revarr_ SWAP ! R> 1- DUP 0= UNTIL 2DROP ;
DECIMAL

итог быстродействия

mrack
на чом: intel Celeron M 1,5 ГГц ОЗУ 240МБ 
Calls       Ticks              AverageTicks     Name     (Rets)
включен оптимизатор
       100 |      178,883,161 |      1,788,831 |

mOleg

модифицированный алгоритм WingLiona by mOleg

Код:

 REQUIRE FOR   devel\~mOleg\lib\util\for-next.f

: revcell ( u --> u )
          DUP 0x10 RSHIFT SWAP 0x10 LSHIFT OR
          DUP 0xFF00FF00 AND 8 RSHIFT SWAP 0x00FF00FF AND 8 LSHIFT OR
          DUP 0xF0F0F0F0 AND 4 RSHIFT SWAP 0x0F0F0F0F AND 4 LSHIFT OR
          DUP 0xCCCCCCCC AND 2 RSHIFT SWAP 0x33333333 AND 2 LSHIFT OR
          DUP 0xAAAAAAAA AND 1 RSHIFT SWAP 0x55555555 AND 1 LSHIFT OR
          ;

\ для массива addr # произвести битовый реверс
: revarr ( addr # --> )
         FOR DUP @ revcell OVER !
             CELL +
         TILL DROP ;

*битовое отражение числа

Кто сейчас на конференции