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

Black_mirror

Что-то не совсем понимаю, как из него получить число. Для меня этот полином соответствует числу 100101b... не более.

Ну если быть уж совсем точным, то на самом деле даже 2^12 за счёт того, что младший бит после mul всё равно в edx не попадёт. Т.е. бит может быть и 0, и 1, что удваивает число магических чисел.

Ну... я изначально написал перебор на Java (---публика неистовствует, гнилые помидоры килограммами летят на сцену---)
Но после этого Вашего заявления решил опробовать силы в макросах. Ввиду моей недалёкости в этой теме, это оказалось серьёзным вызовом.
Вот результат:

Код (Text):

1. include 'general.inc'
2.  
3. start:
4.         mov edx,magic
5.         mul edx
6.         and edx,1Fh
7.         mov eax,dword[table+edx*4]
8. ret
9.  
10. align 16
11. table           rb 4*32
12.  
13. times 32 store dword 1 shl (32-%) at table + 4*(magic shr (33-%) and 1Fh)
14.  
15. macro redef_add_digit
16. {
17.         purge add_digit
18.         macro add_digit pos*
19.         \{
20.                 local numBuf,symBuf,dig_accepted
21.                 repeat 2
22.                         retVal = retVal shl 1 or (%-1)
23.                        
24.                         dig_accepted = 1
25.                         repeat pos
26.                                 load numBuf byte from (%-1)
27.                                 if numBuf = retVal and 1Fh
28.                                         dig_accepted = 0
29.                                         break
30.                                 end if
31.                         end repeat
32.                         if dig_accepted = 1
33.                                 store byte retVal and 1Fh at pos
34.                                 define matched -
35.                                         rept 31 testPos
36.                                         \\{
37.                                                 match =testPos,pos
38.                                                 \\\{
39.                                                         restore matched
40.                                                         define matched +
41.                                                 \\\}
42.                                         \\}
43.                                         match +,matched
44.                                         \\{
45.                                                 rept 1 buf:pos+1 \\\{ define symBuf buf \\\}
46.                                                 redef_add_digit
47.                                                 add_digit symBuf
48.                                                 restore symBuf
49.                                         \\}
50.                                 restore matched
51.                         end if
52.                         match =32,pos
53.                         \\{
54.                                 magicCntr = magicCntr + 1
55.                                 display d=magicCntr,":",9,b=retVal,13,10
56.                                 if mIndex = magicCntr
57.                                         magic = retVal
58.                                 end if
59.                         \\}
60.                         retVal = retVal shr 1
61.                 end repeat
62.         \}
63. }
64.  
65. macro define_magic magic_index*
66. {
67.         virtual at 0
68.                 rb 32
69.                
70.                 retVal = 0
71.                 magicCntr = 0
72.                 store byte 0 at 0
73.                
74.                 define mIndex magic_index
75.                 redef_add_digit
76.                         add_digit 1
77.                 purge add_digit
78.                 restore mIndex
79.                
80.         end virtual
81. }
82.  
83. define_magic 1

Как нетрудно догадаться, индекс 1 в define_magic 1 указывает номер выбранного магического числа и может находиться в пределах между 1 и 4096, иначе компиляция провалится.
У меня компиляция длится ~5 секунд. Но зато работает.

Релевантное содержимое из моего general.inc в качестве бонуса :

Код (Text):

1. macro dispBin num*
2. {
3.     local digPos,number
4.     number = num
5.     if number < 0
6.         number = number + 100000000h
7.     end if
8.     digPos = 0
9.     while 1 shl digPos <= number
10.         digPos = digPos + 1
11.     end while
12.     if digPos = 0
13.         display '0'
14.     else
15.         times digPos display number shr (digPos-%) and 1+'0'
16.     end if
17.     display 'b'
18. }
19.  
20. macro dispDec num*
21. {
22.     local tenPow,rest,number
23.     number = num
24.     if (number) < 0
25.         display '-'
26.         number = -number
27.     end if
28.     tenPow = 1
29.     while tenPow <= number
30.         tenPow = tenPow*10
31.     end while
32.     if tenPow = 1
33.         display '0'
34.     else
35.         rest = number
36.         while tenPow > 1
37.             tenPow = tenPow/10
38.             display rest/tenPow + '0'
39.             rest = rest mod tenPow
40.         end while
41.     end if
42. }
43.  
44. macro dispHex num*
45. {
46.     local digPos,dig,number
47.     number = num
48.     if number < 0
49.         number = number + 100000000h
50.     end if
51.     digPos = 0
52.     while 1 shl (digPos*4) <= number
53.         digPos = digPos + 1
54.     end while
55.     if digPos = 0
56.         display '0'
57.     else
58.         repeat digPos
59.             dig = number shr ((digPos-%)*4) and 0Fh+'0'
60.             if dig > '9'
61.                 dig = dig-'0'+('A'-10)
62.             end if
63.             display dig
64.         end repeat
65.     end if
66.     display 'h'
67. }
68.  
69. macro display [token]
70. {
71.     forward
72.         local matched
73.         if token eqtype ''
74.             display token
75.         else
76.             matched = 0
77.             irps type, =b =d =h \{ match type#==n,token \\{ matched = 1 \\} \}
78.             match =b==number,token \{ dispBin number \}
79.             match =d==number,token \{ dispDec number \}
80.             match =h==number,token \{ dispHex number \}
81.             if matched = 0
82.                 display token
83.             end if
84.         end if
85. }

 

P.S. Компилироваться будет скорее всего только в версиях, начиная с 1.69.

 

l_inc
У меня макросы были существенно проще:

Код (Text):

1. magic = 1
2. repeat 31
3. magic = (magic shl 1) xor ((magic shr 2) and 1) xor ((magic shr 4) and 1); полином прячется в этой строке
4. end repeat
5.  
6. table dd 80000000h
7. repeat 31
8. p = %
9. repeat 31
10. s = ((magic shl %) shr 32) and 31
11. if p=s
12. dd 80000000h shr %
13. end if
14. end repeat
15. end repeat

А ваши мой разум понять не в силах, или ему просто лень.

Интересно, а можно ли для заданного полинома по 5 битному остатку найти 2^n которое его даёт при делении без таблицы?

 

Black_mirror

Ну я бы так не сказал. У меня вот этот код:

Код (Text):

1. table dd 80000000h
2. repeat 31
3. p = %
4. repeat 31
5. s = ((magic shl %) shr 32) and 31
6. if p=s
7. dd 80000000h shr %
8. end if
9. end repeat
10. end repeat

реализован в две строки :

Код (Text):

1. table           rb 4*32
2. times 32 store dword 1 shl (32-%) at table + 4*(magic shr (33-%) and 1Fh)

Просто у меня макросы находят и выводят на экран таблицу из всех возможных магических чисел. То, которое получается из Вашего полинома, в этой таблице под номером 544 (т.е. вызов макроса define_magic 544 дал бы у меня то же самое магическое число).
Но вот Вашу логику получения магического числа из полинома не улавливаю. И почему именно этот полином даёт магическое число, а какой-нибудь другой нет?

 

мой 16 разрядный вариант - для 32 замените на eax и 80000000

Код (Text):

1. 0B15:0100 31C0          XOR     AX,AX
2. 0B15:0102 0D0080        OR      AX,8000
3. 0B15:0105 F8            CLC
4. 0B15:0106 D1E8          SHR     AX,1
5. 0B15:0108 EBF8          JMP     0102

 

писал в дебуге так что за внешний вид извиняйте уж

 

зы: за итерацию два значения одно после or другое после shr

 

Rockphorr
У тебя получается
0000
8000
4000
С000
6000

А надо
0000
8000
4000
C000
2000

 

murder
А самое главное, что алгоритм ещё и быстрый какой (время исполнения —> ∞).
И разумеется, алгоритм бы не обошёлся без clc для солидности.

 

l_inc
ну ладно раз такой преверед то сознаюсь не поставил скобки

mov cx,8000h
....
loop $next

murder
да, эту засаду я проглядел

 

l_inc
clc - это не солидность - просто cf влияет на сдвиги, без него неправильно а с ним так воще засада

 

Переходы нельзя использовать.

 

KeSqueer
Для предыдущей задачи можно. Там без переходов и не обойтись. Хотя согласен... по приведенному месиву инструкций трудно определить, к какой задаче относится попытка решения.

 

l_inc
на мне уж живого места нет - закусал своими замечаниями

 

Код (Text):

1.          ror     eax,31

 

Пример aaaa..zzzz:
http://board.flatassembler.net/topic.php?t=11180&start=9

 

edemko

Торопися не надо. Эта команда не зеркалит бит. А уж пиарить себя не по делу - это ВАЩЕ.

 

Rockphorr

Ну так... чем больше я их делаю, тем больше поводов Вы для них даёте.
P.S. cf никак не влияет на работу shr.

 

l_inc
я в справочнике уточню, на вскидку не скажу - поэтому и поставил на всякий случай
а вообще поломаю голову над решением перой задачки на досуге в выходные

 

Я ошибся, извините, пиар мне ни к чему и ни к месту. (укр.)Просто не подумав. Помилок я допускаюся часто, сприймайте мене таким, як є. Если вы говорите о лингвистике, это обычная практика. valterg, если бы вы внимательно просмотрели тот сорец, процедуру "feedback", закомпилили с bswap и без, так бы не говорили. Успехов, хотя я и сука. valterg, ссылки на фасмовском форуме тоже приводят сюда, все в порядке. Успыхыв.

Код (Text):

1.     mov eax,00001111'00000000'00000000'00000000b
2.  
3.     mov ecx,32
4.      @@:ror eax,1
5.     rcl edx,1
6.     loop    @b
7.  
8.     ; eax = 00001111'00000000'00000000'00000000b
9.     ; edx = 00000000'00000000'00000000'11110000b