Forth http://fforum.winglion.ru/ |
|
*битовое преобразование числа http://fforum.winglion.ru/viewtopic.php?f=19&t=1236 |
Страница 1 из 3 |
Автор: | mOleg [ Чт апр 17, 2008 14:55 ] |
Заголовок сообщения: | *битовое преобразование числа |
Дано число U разрядностью в CELL. Необходимо преобразовать число таким образом, чтобы все значащие биты сгруппировались в младших разрядах числа, а незначащие - в старших. То есть: 1010101110110000 --> 0000000011111111 Код: \ битовое преобразование числа : transform ( U --> u ) ; |
Автор: | chess [ Чт апр 17, 2008 18:25 ] |
Заголовок сообщения: | |
Решение на ассм(на форте гораздо более громоздко, поэтому не привожу) Код: REQUIRE IDN ~CHESS\ASSM\SP-ASSM.F : transform ( U --> u ) B^B B++ L1: C=A C=L\C $ 1 Ca 1B<< A>> L1 J0<> $ -1 A=aB ; \ EOF STARTLOG SEE transform 0x12493111 transform HEX CR . DECIMAL лог Код: CODE transform
5A52FF 33DB XOR EBX , EBX 5A5301 43 INC EBX 5A5302 8BC8 MOV ECX , EAX 5A5304 0FBCC9 BSF ECX , ECX 5A5307 8D4901 LEA ECX , 1 [ECX] 5A530A D1E3 SHL EBX , 1 5A530C D3E8 SHR EAX , CL 5A530E 75F2 JNE 5A5302 5A5310 8D43FF LEA EAX , FF [EBX] 5A5313 C3 RET NEAR END-CODE 3FF Ok |
Автор: | mOleg [ Чт апр 17, 2008 18:30 ] |
Заголовок сообщения: | |
chess писал(а): Решение на ассм
И на каком форте это можно проверить? Где лежит необходимая библиотека? Предпочтительно было бы решение на чистом форте, между прочим. |
Автор: | chess [ Чт апр 17, 2008 18:34 ] |
Заголовок сообщения: | |
mOleg писал(а): И на каком форте это можно проверить?
Где лежит необходимая библиотека? Форт - дистрибутив 4.19(без CVS) АССМ все там же: http://www.chess2007.nm.ru/~chess.zip |
Автор: | mOleg [ Чт апр 17, 2008 18:37 ] |
Заголовок сообщения: | |
мое решение (анси вариант): Код: \ битовое преобразование числа
: transform ( U --> u ) 1 SWAP BEGIN DUP WHILE DUP 1 AND IF SWAP 2* SWAP THEN 1 RSHIFT REPEAT DROP 1 - ; |
Автор: | Jelsay [ Чт апр 17, 2008 21:34 ] |
Заголовок сообщения: | |
Код: VARIABLE A
: COUNTED ( N -- ) BEGIN 2 /MOD SWAP IF A @ 1+ A ! THEN DUP 0= UNTIL DROP ; : MAKE ( -- N) A @ 0= IF 0 ELSE 1 A @ 1- 0 DO 2* 1+ LOOP THEN ; : BOSS COUNTED MAKE ; 2 BASE ! 001100110111 DUP . CR BOSS . KEY DROP BYE |
Автор: | Jelsay [ Чт апр 17, 2008 21:35 ] |
Заголовок сообщения: | |
Код: VARIABLE A
: COUNTED ( N -- ) BEGIN 2 /MOD SWAP IF A @ 1+ A ! THEN DUP 0= UNTIL DROP ; : MAKE ( -- N) A @ 0= IF 0 ELSE 1 A @ 1- 0 DO 2* 1+ LOOP THEN ; : BOSS COUNTED MAKE ; 2 BASE ! 001100110111 DUP . CR BOSS . KEY DROP BYE |
Автор: | forther [ Чт апр 17, 2008 21:58 ] |
Заголовок сообщения: | |
Код: : transform -1 begin over while 2* >r dup 1- and r> repeat nip invert ;
уже голова не по-сифортовски не думает, но работать должно ... а как сравнивать будем, по скорости или по размеру? |
Автор: | chess [ Пт апр 18, 2008 11:05 ] |
Заголовок сообщения: | |
forther писал(а): а как сравнивать будем, по скорости или по размеру?
Можно оценить и так и так. Чтобы повысить быстродействие сделал вариант программы без медленной команды сканирования битов. Программа JELSAY некорректно работает с граничными значениями(не учтено, что входное число беззнаковое). Быстродействие ее около 12000 тиков, поэтому данные по ней не привожу. По остальным программам соотношение и по времени исполнения и по объему кода одинаково и равно примерно 3:2:1 соответственно для программ от mOlega, forthera и моей на ассме. Здесь конечные значения времени ближе к пропускной способности, а не к латентности, так как код работает уже в кэше. Код: REQUIRE IDN ~CHESS\ASSM\SP-ASSM.F ЛОГ: transformO ( U --> u ) 1 SWAP BEGIN DUP WHILE DUP 1 AND IF SWAP 2* SWAP THEN 1 RSHIFT REPEAT DROP 1 - ; : transformF -1 BEGIN OVER WHILE 2* >R DUP 1- AND R> REPEAT NIP INVERT ; L: transformC B^B B~ $ 0 A=#? L1: L2 J0= 1B<< C=A A-- A&C L1 JMP L2: B~ A=B L; : dtF DUP A^A CPUID DA=TSC 0xAAAAAAAA transformF DUP A^A CPUID DA=TSC ROT - . ; : dtO DUP A^A CPUID DA=TSC 0xAAAAAAAA transformO DUP A^A CPUID DA=TSC ROT - . ; : dtC DUP A^A CPUID DA=TSC 0xAAAAAAAA transformC DUP A^A CPUID DA=TSC ROT - . ; STARTLOG SEE transformO SEE transformF SEE transformC CR dtO dtO dtO dtO dtO dtO dtO dtO dtO dtO CR CR dtF dtF dtF dtF dtF dtF dtF dtF dtF dtF CR CR dtC dtC dtC dtC dtC dtC dtC dtC dtC dtC CR Код: CODE transformO
5A52FF C745FC01000000 MOV FC [EBP] , # 1 5A5306 8D6DFC LEA EBP , FC [EBP] 5A5309 90 XCHG EAX, EAX 5A530A 90 XCHG EAX, EAX 5A530B 90 XCHG EAX, EAX 5A530C 0BC0 OR EAX , EAX 5A530E 0F8426000000 JE 5A533A ( transformO+3B ) 5A5314 8BC8 MOV ECX , EAX 5A5316 81E101000000 AND ECX , # 1 5A531C 7417 JE 5A5335 5A531E 8B5500 MOV EDX , 0 [EBP] 5A5321 894500 MOV 0 [EBP] , EAX 5A5324 8BC2 MOV EAX , EDX 5A5326 8D044500000000 LEA EAX , 0 [EAX*2] 5A532D 8B5500 MOV EDX , 0 [EBP] 5A5330 894500 MOV 0 [EBP] , EAX 5A5333 8BC2 MOV EAX , EDX 5A5335 C1E801 SHR EAX , 1 5A5338 EBD2 JMP 5A530C 5A533A B8FFFFFFFF MOV EAX , # FFFFFFFF 5A533F 034500 ADD EAX , 0 [EBP] 5A5342 8D6D04 LEA EBP , 4 [EBP] 5A5345 C3 RET NEAR END-CODE CODE transformF 5A535F 8945FC MOV FC [EBP] , EAX 5A5362 B8FFFFFFFF MOV EAX , # FFFFFFFF 5A5367 8D6DFC LEA EBP , FC [EBP] 5A536A 90 XCHG EAX, EAX 5A536B 90 XCHG EAX, EAX 5A536C 837D0000 CMP 0 [EBP] , # 0 5A5370 0F8416000000 JE 5A538C ( transformF+2D ) 5A5376 8D044500000000 LEA EAX , 0 [EAX*2] 5A537D 50 PUSH EAX 5A537E 8B4500 MOV EAX , 0 [EBP] 5A5381 8D48FF LEA ECX , FF [EAX] 5A5384 23C1 AND EAX , ECX 5A5386 894500 MOV 0 [EBP] , EAX 5A5389 58 POP EAX 5A538A EBE0 JMP 5A536C 5A538C F7D0 NOT EAX 5A538E 8D6D04 LEA EBP , 4 [EBP] 5A5391 C3 RET NEAR END-CODE CODE transformC 5A53AB 33DB XOR EBX , EBX 5A53AD F7D3 NOT EBX 5A53AF 81F800000000 CMP EAX , # 0 5A53B5 7409 JE 5A53C0 5A53B7 D1E3 SHL EBX , 1 5A53B9 8BC8 MOV ECX , EAX 5A53BB 48 DEC EAX 5A53BC 23C1 AND EAX , ECX 5A53BE EBF5 JMP 5A53B5 5A53C0 F7D3 NOT EBX 5A53C2 8BC3 MOV EAX , EBX 5A53C4 C3 RET NEAR END-CODE 870 395 318 303 303 303 303 303 303 303 261 270 222 205 203 201 201 203 203 203 188 171 156 146 133 133 133 133 133 133 Ok ( [30].. 65535 65535 65535 65535 65535 ) |
Автор: | chess [ Пт апр 18, 2008 11:50 ] |
Заголовок сообщения: | |
Для сравнения работы оптимизаторов SPF и VFX приведу код для программ от forthera и mOlega который дает транслятор VFX. Много общего. Вершина стека параметров в VFX как и в SWIFT-е в EBX, а не в EAX (SPF). Это рациональней, так как аккумулятор свободен и с ним можно работать более короткими и быстрыми командами не затрагивая стек параметров. А так результаты близки к тому что дает SPF. Про быстродействие VFX-кода этих программ сказать пока ничего не могу. Код: : transformF -1 BEGIN OVER WHILE 2* >R DUP 1- AND R> REPEAT NIP INVERT ; )
see transformF TRANSFORMF ( 004ABBC0 8D6DFC ) LEA EBP, [EBP+-04] ( 004ABBC3 895D00 ) MOV [EBP], EBX ( 004ABBC6 BBFFFFFFFF ) MOV EBX, FFFFFFFF ( 004ABBCB 90 ) NOP ( 004ABBCC 90 ) NOP ( 004ABBCD 90 ) NOP ( 004ABBCE 90 ) NOP ( 004ABBCF 90 ) NOP ( 004ABBD0 837D0000 ) CMP [EBP], 00 ( 004ABBD4 0F8412000000 ) JZ/E 004ABBEC ( 004ABBDA D1E3 ) SHL EBX, 1 ( 004ABBDC 53 ) PUSH EBX ( 004ABBDD 8B5D00 ) MOV EBX, [EBP] ( 004ABBE0 4B ) DEC EBX ( 004ABBE1 235D00 ) AND EBX, [EBP] ( 004ABBE4 5A ) POP EDX ( 004ABBE5 895D00 ) MOV [EBP], EBX ( 004ABBE8 8BDA ) MOV EBX, EDX ( 004ABBEA EBE4 ) JMP 004ABBD0 ( 004ABBEC F7D3 ) NOT EBX ( 004ABBEE 8D6D04 ) LEA EBP, [EBP+04] ( 004ABBF1 C3 ) NEXT, ( 50 bytes, 22 instructions ) : transformO ( U --> u ) 1 SWAP BEGIN DUP WHILE DUP 1 AND IF SWAP 2* SWAP THEN 1 RSHIFT REPEAT DROP 1 - ; see transformO TRANSFORMO ( 004ABC20 8D6DFC ) LEA EBP, [EBP+-04] ( 004ABC23 C7450001000000 ) MOV DWord Ptr [EBP], 00000001 ( 004ABC2A 90 ) NOP ( 004ABC2B 90 ) NOP ( 004ABC2C 90 ) NOP ( 004ABC2D 90 ) NOP ( 004ABC2E 90 ) NOP ( 004ABC2F 90 ) NOP ( 004ABC30 85DB ) TEST EBX, EBX ( 004ABC32 0F8419000000 ) JZ/E 004ABC51 ( 004ABC38 8BD3 ) MOV EDX, EBX ( 004ABC3A 83E301 ) AND EBX, 01 ( 004ABC3D 8BDA ) MOV EBX, EDX ( 004ABC3F 0F8408000000 ) JZ/E 004ABC4D ( 004ABC45 8B5500 ) MOV EDX, [EBP] ( 004ABC48 D1E2 ) SHL EDX, 1 ( 004ABC4A 895500 ) MOV [EBP], EDX ( 004ABC4D D1EB ) SHR EBX, 1 ( 004ABC4F EBDF ) JMP 004ABC30 ( 004ABC51 8B5D00 ) MOV EBX, [EBP] ( 004ABC54 83C3FF ) ADD EBX, -01 ( 004ABC57 8D6D04 ) LEA EBP, [EBP+04] ( 004ABC5A C3 ) NEXT, ( 59 bytes, 23 instructions |
Автор: | mOleg [ Пт апр 18, 2008 14:21 ] |
Заголовок сообщения: | |
Jelsay писал(а): : BOSS COUNTED MAKE ;
Jelsay, обратите пожалуйста свое внимание на тот факт, что главное слово задачи предопределено. Сделано это не просто так, а чтобы было во-первых понятнее, а во-вторых легче тестировать ваше решение. Спасибо за участие!) |
Автор: | mOleg [ Пт апр 18, 2008 14:40 ] |
Заголовок сообщения: | |
мне пока что больше нравится решение Forter-а из за вот-этого: dup 1- and если кто не понял - это сброс младшего значащего бита в нуль. Я же биты не сбрасывал, а сдвигал. |
Автор: | forther [ Пт апр 18, 2008 22:08 ] |
Заголовок сообщения: | |
chess писал(а): Чтобы повысить быстродействие сделал вариант программы без медленной команды сканирования битов.
А сколько было до повышения быстродействия? Не могли бы вы использовать для сравнения свой первый вариант? |
Автор: | Jelsay [ Сб апр 19, 2008 10:40 ] |
Заголовок сообщения: | |
Цитата: Программа JELSAY некорректно работает с граничными значениями(не учтено, что входное число беззнаковое
прошу прощения - в качестве оправдания прошу учесть что я написал и отладил её менее чем за минуту совершенно не думая об оптимизациях |
Автор: | Pretorian [ Сб апр 19, 2008 15:14 ] |
Заголовок сообщения: | |
А если при встрече каждой единицы в числе (после первой) число 1 сдвигать влево (типа умножения на 2? |
Страница 1 из 3 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |