Задачка о битреверсивном счётчике

persicum
jz @quit поставь после dec edx

 

Black_mirror
То есть нужно зеркально отразить биты.

 

Наш табличный вариант к первой задаче:

Код (Text):

1. AlignedEntry:
2.     TimerStart
3.     xor ecx, ecx
4.     mov esi, ValTable
5.     mov edx, 0xff * 4
6.     mov ebx, edx
7.     mov edi, edx
8.     mov ebp, edx
9.  
10. MainCycle:
11.     mov eax, ecx
12.     ;
13.     ; eax ready
14.     ;
15.     and ecx, 0x00ffffff
16.     or ecx, [esi + edx + 0]
17.     sub edx, 4
18.     jnc MainCycle
19.    
20.     movzx ecx, cx
21.     or ecx, [esi + ebx + 1]
22.     add ebx, edx
23.     mov edx, 0xff * 4
24.     jns MainCycle
25.    
26.     movzx ecx, cl
27.     or ecx, [esi + edi + 2]
28.     add edi, ebx
29.     mov ebx, edx
30.     jns MainCycle
31.    
32.     mov ecx, [esi + ebp + 3]
33.     add ebp, edi
34.     mov edi, edx
35.     jns MainCycle
36.  
37.     TimerStop
38.     retn

Код целиком:

Код (Text):

1. format PE GUI
2.  
3. section '.text' code readable executable
4.  
5.  
6. macro TimerStart
7. {
8.     rdtsc
9.     shrd eax, edx, $10
10.     push eax
11. }
12.  
13. macro TimerStop
14. {
15.     rdtsc
16.     pop ecx
17.     shrd eax, edx, $10
18.     sub eax, ecx
19. }
20.  
21. macro AlignedEntry [dummy]
22. {
23.     HeadSize = MainCycle - EntryPoint
24.     Alignment = -($ + HeadSize)
25.     times Alignment and $0f nop
26.  
27. entry $
28. EntryPoint:
29. }
30.  
31.  
32. ; 0 1 2 3 4 5 6 7 8 9 a b c d e f       ; normal
33. ; 0 8 4 c 2 a 6 e 1 9 5 d 3 b 7 f       ; bitrev
34. ; 8 9 a b c d e f 4 5 6 7 2 3 1 0       ; selfref-next (unused)
35.  
36. macro GenerateTable     python*
37. {
38. Nibble = [0x00, 0x08, 0x04, 0x0c, 0x02, 0x0a, 0x06, 0x0e, 0x01, 0x09, 0x05, 0x0d, 0x03, 0x0b, 0x07, 0x0f]
39.  
40. def GenerateReverseTable():
41.     print('ValTable:')
42.     print('dd 0     ; extra')
43.     print('db 0, 0, 0')
44.     for i in range(0x0f, -1, -1):
45.         s = 'dd '
46.         for j in range(0x0f, -1, -1):
47.             byte = Nibble[i] + (Nibble[j] << 0x04)
48.             s = s + '{:#04x}, '.format(byte)
49.         print(s.rstrip(', '))
50.  
51. GenerateReverseTable()
52. }
53.  
54.  
55. ValTable:
56. dd 0        ; extra
57. db 0, 0, 0
58. dd 0xff, 0x7f, 0xbf, 0x3f, 0xdf, 0x5f, 0x9f, 0x1f, 0xef, 0x6f, 0xaf, 0x2f, 0xcf, 0x4f, 0x8f, 0x0f
59. dd 0xf7, 0x77, 0xb7, 0x37, 0xd7, 0x57, 0x97, 0x17, 0xe7, 0x67, 0xa7, 0x27, 0xc7, 0x47, 0x87, 0x07
60. dd 0xfb, 0x7b, 0xbb, 0x3b, 0xdb, 0x5b, 0x9b, 0x1b, 0xeb, 0x6b, 0xab, 0x2b, 0xcb, 0x4b, 0x8b, 0x0b
61. dd 0xf3, 0x73, 0xb3, 0x33, 0xd3, 0x53, 0x93, 0x13, 0xe3, 0x63, 0xa3, 0x23, 0xc3, 0x43, 0x83, 0x03
62. dd 0xfd, 0x7d, 0xbd, 0x3d, 0xdd, 0x5d, 0x9d, 0x1d, 0xed, 0x6d, 0xad, 0x2d, 0xcd, 0x4d, 0x8d, 0x0d
63. dd 0xf5, 0x75, 0xb5, 0x35, 0xd5, 0x55, 0x95, 0x15, 0xe5, 0x65, 0xa5, 0x25, 0xc5, 0x45, 0x85, 0x05
64. dd 0xf9, 0x79, 0xb9, 0x39, 0xd9, 0x59, 0x99, 0x19, 0xe9, 0x69, 0xa9, 0x29, 0xc9, 0x49, 0x89, 0x09
65. dd 0xf1, 0x71, 0xb1, 0x31, 0xd1, 0x51, 0x91, 0x11, 0xe1, 0x61, 0xa1, 0x21, 0xc1, 0x41, 0x81, 0x01
66. dd 0xfe, 0x7e, 0xbe, 0x3e, 0xde, 0x5e, 0x9e, 0x1e, 0xee, 0x6e, 0xae, 0x2e, 0xce, 0x4e, 0x8e, 0x0e
67. dd 0xf6, 0x76, 0xb6, 0x36, 0xd6, 0x56, 0x96, 0x16, 0xe6, 0x66, 0xa6, 0x26, 0xc6, 0x46, 0x86, 0x06
68. dd 0xfa, 0x7a, 0xba, 0x3a, 0xda, 0x5a, 0x9a, 0x1a, 0xea, 0x6a, 0xaa, 0x2a, 0xca, 0x4a, 0x8a, 0x0a
69. dd 0xf2, 0x72, 0xb2, 0x32, 0xd2, 0x52, 0x92, 0x12, 0xe2, 0x62, 0xa2, 0x22, 0xc2, 0x42, 0x82, 0x02
70. dd 0xfc, 0x7c, 0xbc, 0x3c, 0xdc, 0x5c, 0x9c, 0x1c, 0xec, 0x6c, 0xac, 0x2c, 0xcc, 0x4c, 0x8c, 0x0c
71. dd 0xf4, 0x74, 0xb4, 0x34, 0xd4, 0x54, 0x94, 0x14, 0xe4, 0x64, 0xa4, 0x24, 0xc4, 0x44, 0x84, 0x04
72. dd 0xf8, 0x78, 0xb8, 0x38, 0xd8, 0x58, 0x98, 0x18, 0xe8, 0x68, 0xa8, 0x28, 0xc8, 0x48, 0x88, 0x08
73. dd 0xf0, 0x70, 0xb0, 0x30, 0xd0, 0x50, 0x90, 0x10, 0xe0, 0x60, 0xa0, 0x20, 0xc0, 0x40, 0x80, 0x00
74.  
75.  
76.  
77. AlignedEntry:
78.     TimerStart
79.     xor ecx, ecx
80.     mov esi, ValTable
81.     mov edx, 0xff * 4
82.     mov ebx, edx
83.     mov edi, edx
84.     mov ebp, edx
85.  
86. MainCycle:
87.     mov eax, ecx
88.     ;
89.     ; eax ready
90.     ;
91.     and ecx, 0x00ffffff
92.     or ecx, [esi + edx + 0]
93.     sub edx, 4
94.     jnc MainCycle
95.    
96.     movzx ecx, cx
97.     or ecx, [esi + ebx + 1]
98.     add ebx, edx
99.     mov edx, 0xff * 4
100.     jns MainCycle
101.    
102.     movzx ecx, cl
103.     or ecx, [esi + edi + 2]
104.     add edi, ebx
105.     mov ebx, edx
106.     jns MainCycle
107.    
108.     mov ecx, [esi + ebp + 3]
109.     add ebp, edi
110.     mov edi, edx
111.     jns MainCycle
112.  
113.     TimerStop
114.     retn

 

Black_mirror

Может на десерт? Или основное блюдо ещё впереди?
Про запрет на rcr ничего не сказано. Размачиваю счёт:

Код (Text):

1. start:
2.     xor ecx,ecx
3.     repeat 32
4.         add eax, 1 shl (32-%)
5.         rcr ecx,1
6.     end repeat
7.     mov eax,ecx
8. ret

 

l_inc
rcr не вписывается в условия

 

Насколько я понял можно использовать только mov, add, sub, mul, xor, and, or, not

 

KeSqueer
Почему не вписывается? Не цикл, не условная пересылка, не деление, не сканирование бит. Хотя можно и без rcr... в лоб:

Код (Text):

1. start:
2.     xor ecx,ecx
3.     repeat 32
4.         mov ebx,eax
5.         and ebx, not(1 shl (%-1))
6.         sub ebx,1
7.         adc ecx,ecx
8.     end repeat
9.     mov eax,ecx
10. ret

Или adc тоже не вписывается?

 

l_inc
Мне бы хотелось видеть решение без побитового разбора. У Уорена для обращения всех бит приводится такой код:

Код (Text):

1. t=((x>>1)^x)&0x55555555; x^=t|(t<<1);
2. t=((x>>2)^x)&0x33333333; x^=t|(t<<2);
3. t=((x>>4)^x)&0x0F0F0F0F; x^=t|(t<<4);
4. t=((x>>8)^x)&0x00FF00FF; x^=t|(t<<8);
5. t=((x>>16)^x)&0x0000FFFF; x^=t|(t<<16);

Но у нас всего один единичный бит, поэтому решение должно быть существенно проще. Чем-то эта задача похожа на задачу о замене деления умножением. Мне кажется что её можно решить не более чем за 10 команд.

 

Black_mirror
Ух... интересный код... Про решето были мысли, конечно, ещё в предыдущей задаче, но ничего путного не дали.
Но чтоб такое выдумать...
Ладно... бум думать...

 

P.S. Так логические сдвиги всё-таки допускаются?

 

l_inc
Ну если учесть что сдвиг влево на k(или вправо на 31-k) можно получить умножением на 2^k, то особого смысла их запрещать нету. Сделав после умножения OR EAX,EDX можно получить циклический сдвиг, так что они тоже пусть будут.

 

Black_mirror
В общем, хитрый мул как-то не удаётся. Мой лучший вариант на данный момент — тупое просеивание. Не десять инструкций, но на жизнь право имеет:

Код (Text):

1. start:
2.     mov eax,1
3.     xor ecx,ecx
4.    
5.     mov edx,eax
6.     and edx,0x0000FFFF
7.     sub edx,eax
8.     adc ecx,ecx
9.    
10.     mov edx,eax
11.     and edx,0x00FF00FF
12.     sub edx,eax
13.     adc ecx,ecx
14.  
15.     mov edx,eax
16.     and edx,0x0F0F0F0F
17.     sub edx,eax
18.     adc ecx,ecx
19.  
20.     mov edx,eax
21.     and edx,0x33333333
22.     sub edx,eax
23.     adc ecx,ecx
24.  
25.     mov edx,eax
26.     and edx,0x55555555
27.     sub edx,eax
28.     adc ecx,ecx
29.    
30.     mov eax,80000000h
31.     shr eax,cl
32. ret

 

Ах да... mov eax,1 в начале не нужен.

 

Ну и без xor eax,eax в начале тоже можно обойтись.

 

Т.е. блин... без xor ecx,ecx.

 

l_inc
У меня хитрый mul в 4 команды поместился и еще 32 слова на табличку, теперь думаю чего бы можно сделать без таблицы.

 

Почему должно? ИМХО как раз нет. Уоррен приводит решение для общего вида, не учитывающее количество единичных битов. Если нужно учитывать, придется тестировать биты, а ты запретил.

Однако известно, что бит может содержаться только в одном из байтов. Поэтому можно развернуть все байты в байтах, а потом сделать переставить байты. Чуть-чуть проще, а не существенно

t=((x>>1)^x)&0x55555555; x^=t|(t<<1);
t=((x>>2)^x)&0x33333333; x^=t|(t<<2);
t=((x>>4)^x)&0x0F0F0F0F; x^=t|(t<<4);
bswap(t);

 

где то на форуме такой алг лежал

Код (Text):

1. mov eax,0001010111b
2. mov ebx,0F0F0F0Fh
3. mov ecx,33333333h
4. mov edx,55555555h
5. bswap eax
6. and  ebx,eax
7. xor   eax,ebx
8. shl    ebx,4
9. shr    eax,4
10. or     eax,ebx
11. and  ecx,eax
12. xor   eax,ecx
13. shl    ecx,2
14. shr    eax,2
15. or     eax,ecx
16. and  edx,eax
17. xor   eax,edx
18. shl    edx,1
19. shr    eax,1
20. or     eax,edx

 

J0E
bswap(x);
Причём решение остаётся общим. Решения для частных случаев именно должны быть проще. Иначе в решении для частного случая нет смысла.
Black_mirror

А размер таблички не считается? Вроде ж никто не говорил, что в этой задаче тоже оптимизация по скорости. Как насчёт таблички размером в 2^31 слов плюс одна инструкция?
А с четырьмя инструкциями каждый может :

Код (Text):

1. start:
2.     mov edx,magic
3.     mul edx
4.     and edx,1Fh
5.     mov eax,dword[table+edx*4]
6. ret
7. align 16
8. table       rb 4*32
9.  
10. magic = 10001100101001110101101111100000b
11. repeat 32
12.     store dword 1 shl (32-%) at table + 4*(magic shr (33-%) and 1Fh)
13. end repeat

Таких магических чисел, как выяснилось, 2^11. Вы вручную подбирали?

 

Зачем вручную, когда макросы есть?) У меня был взят полином x^5+x^2+1, наугад, потом просто проверил, что число подходит. А вот откуда магических числе 2^11 весьма интересно, если их генерировать полиномами, то должно быть существенно меньше.