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

mOleg

WingLion писал(а):

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

работать не будет, так как сдвиги нужно в обе стороны делать!

Alexander

mOleg писал(а):

я спрашивал о том, есть ли в используемом вами форте команда LSHIFT

Ответ - да. Поправил код:

Код:

: 2POWER ( n - 2^n ) 1 SWAP LSHIFT ;

или

Код:

ICODE 2POWER
   #1 # EAX MOV  EBX ECX MOV  EAX CL SHL  EAX EBX MOV
   RET
END-CODE

продолжаем

Код:

( ПОЗИЦИЯ СТАРШЕГО ЗНАЧАЩЕГО БИТА )
ICODE ?MSB ( # -- n )
   #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

( ПОЛУЧАЕМ НОМЕРА БИТОВ РАВНЫХ ЕДИНИЦЫ )
: PREPARE ( # -- n1 .. nk k)
   DEPTH >R BEGIN  DUP ?MSB  ?DUP NOT IF  R>DROP EXIT  THEN
               TUCK 1- 2POWER -  ?DUP 0= UNTIL   DEPTH R> - 1+ ;

( ПОЛУЧАЕМ ЗЕРКАЛЬНОЕ ПОБИТОВОЕ ОТРАЖЕНИЕ ЧИСЛА )
: REVERSE ( # -- # )
   PREPARE  0 TUCK ?DO  SWAP #32 SWAP- 2POWER +  LOOP ;

( ОПЕРАЦИЯ ДЛЯ МАССИВА ЧИСЕЛ )
: REVADDR ( addr # -  )
   0 ?DO  DUP @  REVERSE OVER !  CELL+  LOOP  DROP ;

тестируем код

Код:

: .SHOW ( addr # - )
  0 ?DO  DUP I CELLS + @  U.  LOOP DROP ;

HEX CREATE TESTARRAY  AA , AAAA , AAAAAAAA ,

TESTARRAY 3 REVADDR

TESTARRAY 3 .SHOW

Alexander

Функцию REVERSE оптимизируем руками:

Код:

ICODE REVERSE
   #32 # ECX MOV
   1 # EAX MOV
1 L: EBX SHR
   EAX EAX ADC
   1 # ECX SUB
   1 L# JNZ
   EAX EBX MOV
   RET
END-CODE

: REVADDR ( addr # -  ) 
   0 ?DO  DUP @  REVERSE OVER !  CELL+  LOOP  DROP ;

Решение упростилось.

mOleg

Alexander писал(а):

Функцию REVERSE оптимизируем руками:

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

, хотя ассемблерное тоже подходит.
(Да, имя результирующего слова было задано, и оно не REVADDR а revarr.)

P.S. очень понравилось слово R>DROP - это не опечатка?

mOleg

mOleg писал(а):

WingLion писал(а):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
работать не будет, так как сдвиги нужно в обе стороны делать!

все получается, только хитрее:

Код:

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

\ произвести реверс бит указанного числа
: revcell ( u --> u )
          DUP 0xFF00FF00 AND SWAP 0x00FF00FF AND 0x10 ROL OR
          DUP 0xF0F0F0F0 AND SWAP 0x0F0F0F0F AND 0x08 ROL OR
          DUP 0xCCCCCCCC AND SWAP 0x33333333 AND 0x04 ROL OR
          DUP 0xAAAAAAAA AND SWAP 0x55555555 AND 0x02 ROL OR
          0x01 ROL ; 

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

Alexander

mOleg писал(а):

слово R>DROP - это не опечатка

нет не опечатка. просто выталкивает верхушку стека возврата в неиспользуемый регистр.

mOleg писал(а):

И еще, ассемблерное решение не очень интересно, потому как интересно решение на чистом форте

Ладно придумаем как задейтвовать флаг переноса. Доки ссылаются на использование слов U<, U>

вопрос

mOleg писал(а):

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

самое скоростное как и с последовательностью битов будет "массив решений", где индекс указывет на свой собственный реверс, при этом, конечно, 32 бита - многовато, но побайтно (256 байт) легко. если очень нужно быстро, то 16-битные полу-числа - это один сегмент досовский, немного

mrack

вопрос писал(а):

самое скоростное как и с последовательностью битов будет "массив решений", где индекс указывет на свой собственный реверс, при этом, конечно, 32 бита - многовато, но побайтно (256 байт) легко. если очень нужно быстро, то 16-битные полу-числа - это один сегмент досовский, немного

аха гдето я это даже видел

WingLion

mOleg писал(а):

работать не будет, так как сдвиги нужно в обе стороны делать!

С нормальными циклическими сдвигами должно работать

WingLion

формально же N LSHIFT делает то же самое, что и 32 N - RSHIFT, если сдвиги циклические

Alexander

Вот очередное определение отражения 32-разрядной ячейки.
Все только в стандартных словах Форта.

Код:

: REVERSE ( # - # )
   0  32 0 DO  SWAP 0 D2*  I LSHIFT ROT +  LOOP  NIP ;

mOleg

вопрос писал(а):

самое скоростное как и с последовательностью битов будет "массив решений", где индекс указывет на свой собственный реверс, при этом, конечно, 32 бита - многовато, но побайтно (256 байт) легко. если очень нужно быстро, то 16-битные полу-числа - это один сегмент досовский, немного

ну, 16-битные числа это крутовато, а вот для байтового массива решение

Код:

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

\ произвести реверс бит указанного байта
: revbyte ( b --> b )
          0 8 FOR 2* OVER 1 AND OR
                  SWAP 2/ SWAP
              TILL NIP ;

\ массив с инвертированными байтами
CREATE brarr  256 FOR 256 R@ - revbyte B, TILL

\ произвести реверс ячейки
: revcell ( u --> u )
          0 4 FOR 8 LSHIFT
                  OVER 0xFF AND brarr + B@ OR
                  SWAP 8 RSHIFT SWAP
              TILL NIP ;

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

mOleg

Alexander писал(а):

Вот очередное определение отражения 32-разрядной ячейки.
Все только в стандартных словах Форта.

Код:: REVERSE ( # - # ) 0 32 0 DO SWAP 0 D2* I LSHIFT ROT + LOOP NIP ;

вот адаптация для СПФа вашего алгоритма:

Код:

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

\ произвести реверс бит указанного числа
: revcell ( u - u ) 0  32 0 DO  SWAP 0 D2*  I LSHIFT ROT +  LOOP  NIP ;

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

mOleg

сравниваем скорость решений.

проц P4M 512RAM 2GHz   Compaq evo n610c 
        Calls       Ticks          AverageTicks

mrack1    100 |      595,835,848 |      5,958,358
mrack     100 |      606,864,448 |      6,068,644
mOleg     100 |    1,500,738,032 |     15,007,380
winglion  100 |      168,612,552 |      1,686,125
winglion1 100 |       94,206,068 |        942,060
winglion2 100 |      146,995,208 |      1,469,952
mOlega    100 |      380,644,224 |      3,806,442
Alexander 100 |    1,260,778,612 |     12,607,786

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

intel Celeron M 1,5 ГГц ОЗУ 240МБ 
        Calls       Ticks          AverageTicks

mrack     100 |      310,687,011 |      3,106,870
mrack1    100 |      194,321,586 |      1,943,215
alexf     100 |      863,461,611 |      8,634,616
mOleg     100 |      730,044,537 |      7,300,445
mOlegb    100 |      157,327,697 |      1,573,276
wingl1    100 |      66,184,951  |        661,849

mOleg

да, все примеры лежат здесь: http://www.forth.org.ru/~mOleg/samples/2007-11-11/

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

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