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

В EAX лежит 0. Требуется организовать максимально быстрый цикл do{...}while(EAX!=0), который последовательно перебирает все значения EAX, но увеличивать EAX начинает со старшего бита, а перенос распространяет к младшим разрядам, то есть EAX должен пробегать значения:

Код (Text):

1. 00000000
2. 80000000
3. 40000000
4. C0000000
5. 20000000
6. A0000000
7. .....
8. 5FFFFFFF
9. DFFFFFFF
10. 3FFFFFFF
11. BFFFFFFF
12. 7FFFFFFF
13. FFFFFFFF
14. 00000000

Кроме увеличения EAX никакой полезной нагрузки в цикле не требуется. Можно еще расмотреть вариант когда в других регистрах между итерациями сохраняется какая-то дополнительная информация(их тоже можно предварительно проинициализировать), которая может ускорить "увеличение" EAX.

 

Алгоритм таков - ищешь первый слева бит равный нулю, его ставишь в единицу, а все предыдущие в ноль

 

Black_mirror
Вряд ли это будет очень быстро, но для сравнения вариант:

Код (Text):

1. start:
2.     mov ebx,table
3.     mov ecx,0
4.     @@:
5.         mov eax,ecx
6.         xlatb
7.         ror eax,8
8.         xlatb
9.         ror eax,8
10.         xlatb
11.         ror eax,8
12.         xlatb
13.         ror eax,8
14.         bswap eax
15.         ;########expected eax value here########
16.     add ecx,1
17.     jnz @B
18.     xor eax,eax
19.     ;########and here :-)########
20. ret
21. align 16
22. table:
23.     cntr = 0
24.     repeat 256
25.         db cntr
26.         revmask = 0
27.         while (cntr shl % and 0FFh) shr % <> (cntr shl (%-1) and 0FFh) shr (%-1)
28.             revmask = revmask shr 1 or 80h
29.         end while
30.         revmask = revmask shr 1 or 80h
31.         cntr = cntr xor revmask
32.     end repeat

 

Вот как это сделал я (ARM assembler):

Код (Text):

1.         ; add 1 to cntrbitrev "backwards"
2.         ; start looking from top, toggling all bits until we hit a 0,
3.         ; which we toggle to 1 and then stop
4.         ; tmp2 = 0x80000000;
5.         ; bit1 = true;
6.         ; while ( bit1 ) {
7.         ;    bit1 = (cntrbitrev & tmp2) != 0;
8.         ;    cntrbitrev ^= tmp2;
9.         ;    if ( bit1 ) tmp2 >>= 1;
10.         ; }
11.         MOV   tmp2, #(1<<31)
12. Lrev        
13.         TST   cntrbitrev, tmp2  ; is the current bit set?
14.         EOR   cntrbitrev, tmp2  ; toggle it regardless of result
15.         MOVNE tmp2, tmp2, LSR#1 ; if set, shift mask
16.         BNE   Lrev              ; and loop again

 

reverser
Красивое решение. К сожалению неверное.

Во-первых, BNE ни разу не выполнится. Соответственно цикла вовсе не будет.

Во-вторых, даже если бы имелось в виду что-то вроде MOVNES, то никакого счётчика всё равно не будет. Будут все биты подряд каждую вторую итерацию в единицу переключаться. На самом же деле маска, с которой надо EORить, должна содержать не один единичный бит, а все единичные биты слева и все нулевые справа. Причём размеры единичной и нулевой части меняются нелинейно.

В-третьих, решение для ARM вообще нерелевантно, т.к. нужна оптимизация по скорости для x86.

 

"А мужики-то и не знают" (с)
Вообще-то оно работает как надо, в составе алгоритма FFT. Ну а что не x86, звиняйте. Запостил, что было под рукой, думал, авось пригодится.

P.S. если что, MOVNE и BNE используют флаги, выставленные TST.

 

Сорри, забыл упомянуть. Приведенный код - это добавление только одной единички. Возможно, не самый быстрый вариант, но с "быстрой" маской как-то не придумалось. Да и не факт, что при обновлении маски можно обойтись без цикла.

 

reverser

Ну кто знает, что там "надо".

Ага... значит даже MOVNES вместо MOVNE не имелось в виду... ещё лучше.
Т.к. у Вас не указано, я принял, что начальное значение cntrbitrev — нуль (по крайней мере по условию должно быть так). Соответственно, после TST будет выставлен флаг Z. Следовательно ни одного прыжка по BNE не будет => никакого цикла и в помине нету.
Уже не знаю, как там "в составе алгоритма FFT" "надо".

 

reverser

Теперь согласен. Извиняюсь. Когда писал #8 не вник в этот пост.

 

Делаем табличку для "реверсированных" байтов. Реверсируем, добавляем 1 с побайтным переносом, реверсируем назад.
Можно добавить таблицу "реверсированный +1"( значения будут 9-ти битными - бит переноса). Тогда все выльется в хитрую перекодировку по двум таблицам.

 

persicum

Код (Text):

1. xor eax,eax
2. @1:
3. not eax
4. bsr edx,eax
5. not eax
6. bts eax,edx
7. mov ecx,31
8. sub cl,dl
9. shl eax,cl
10. shr eax,cl
11. jmp @1

 

Код (Text):

1.     xor eax,eax
2.     lea ecx,[eax-1]
3.     rrr:
4.     mov edx,0x80000000
5.     kuyf:
6.     xor eax,edx
7.     test eax,edx
8.     ror edx,1
9.     jz kuyf
10.     ;expected eax value here
11.     loop rrr

 

Упс, только заметил, что reverser написал то же самое...

 

persicum, murder

Код (Text):

1.    
2.              xor eax,eax
3.     rrr:
4.     not eax
5.     mov ebx,-1
6.     bsr ecx,eax
7.     jz hh
8.     shl ebx,cl
9.     not eax
10.     xor eax,ebx
11.     ;expected eax value here
12.     jmp rrr
13.              hh:

 

Ravager
XOR изящно смотрится.

 

Black_mirror
Объединяя приведенные идеи, получаем самый быстрый вариант:

Код (Text):

1. start:
2.     xor eax,eax
3.     mov ecx,1
4.     @@:
5.         bsf ebx,ecx
6.         ;########expected eax value here########
7.         xor eax,dword[table+ebx*4]
8.     add ecx,1
9.     jnz @B
10.     xor eax,eax
11.     ;########and here########
12. ret
13. align 16
14. table:  times 32 dd -1 shl (32-%)

 

murder
К концу дня добрался до инета, а меня опередили уже 20 раз =(((
Вот мой код дельфоасмера - без претензий, но рабочий

Код (Text):

1.  
2.  xor edx,edx
3.  xor eax,eax
4.  
5. @loop:
6.  dec edx
7.  
8.  bsf ecx,edx
9.  jz @quit
10.  mov ebx,$80000000
11.  shr ebx,cl
12.  or  eax,ebx
13.  mov ebx,$ffffffff
14.  shr ebx,cl
15.  and eax,ebx //здесь
16.  
17.  jmp @loop
18. @quit:

 

Продолжая тему...

Код (Text):

1.  xor edx,edx
2.  xor eax,eax
3.  
4. @loop:
5.  dec edx
6.  
7.  bsf ecx,edx
8.  jz @quit
9.  shl eax,cl
10.  or  eax,$80000000
11.  shr eax,cl
12.  
13.  jmp @loop
14. @quit:

 

l_inc
Шикарный вариант, похоже по скорости ничего больше сравнивать не придётся)


Задачка на закуску:
В регистре EAX лежит число вида 2^n, нужно получить из него число 2^(32-n), без всяких циклов, условных пересылок, деления, сканирования бит, то есть можно использовать mov, add, sub, mul, xor, and, or, not (вроде этих команд достаточно).

 

поправка, получить нужно 2^(31-n)