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

Тема в разделе "WASM.A&O", создана пользователем Black_mirror, 22 мар 2010.

  1. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    В 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.
     
  2. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Алгоритм таков - ищешь первый слева бит равный нулю, его ставишь в единицу, а все предыдущие в ноль
     
  3. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    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
     
  4. reverser

    reverser New Member

    Публикаций:
    0
    Регистрация:
    27 янв 2004
    Сообщения:
    615
    Вот как это сделал я (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
     
  5. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    reverser
    Красивое решение. К сожалению неверное.

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

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

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

    reverser New Member

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

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

    reverser New Member

    Публикаций:
    0
    Регистрация:
    27 янв 2004
    Сообщения:
    615
    Сорри, забыл упомянуть. Приведенный код - это добавление только одной единички. Возможно, не самый быстрый вариант, но с "быстрой" маской как-то не придумалось. Да и не факт, что при обновлении маски можно обойтись без цикла.
     
  8. l_inc

    l_inc New Member

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

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    reverser
    Теперь согласен. :) Извиняюсь. Когда писал #8 не вник в этот пост.
     
  10. valterg

    valterg Active Member

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

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    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
     
  12. Ravager

    Ravager New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2008
    Сообщения:
    34
    Код (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
     
  13. Ravager

    Ravager New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2008
    Сообщения:
    34
    Упс, только заметил, что reverser написал то же самое...
     
  14. Ravager

    Ravager New Member

    Публикаций:
    0
    Регистрация:
    10 июл 2008
    Сообщения:
    34
    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:
     
  15. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    628
    Ravager
    XOR изящно смотрится.
     
  16. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    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-%)
     
  17. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    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:
     
  18. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Продолжая тему...

    Код (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:
     
  19. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    l_inc
    Шикарный вариант, похоже по скорости ничего больше сравнивать не придётся)


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

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    поправка, получить нужно 2^(31-n)