1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Сканирование бит

Тема в разделе "WASM.A&O", создана пользователем persicum, 2 апр 2008.

  1. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    "Вам "шашечки" или ехать?" Пойми -- быстро - длинный код (стараются развернуть циклы, убрать лишние проверки), короткий код - наглядно, не самое быстрое исполнение
    Понимаю, что дальше длинный код, который так не любит ТС, но преимущества - принимаю решение о том, есть ли единичные биты сразу среди 16 или 8 битов и остальные прелести параллельной обработки
    Код (Text):
    1.      test eax,eax
    2.      jz quit; "облом"
    3.      test ax,ax; проверяем 1 и 2 байт
    4.      jz a3
    5.      test al,al
    6.      jz a1; проверили сразу 8 бит - ничего нет - идем далее
    7. a2: mov ch,al
    8.      mov cl,al
    9.      neg cl
    10.      and al,cl; выделили крайний справа единичный бит
    11.   --- табличное преобразование номера бита
    12.   --- тут делаешь свои темные делишки ---
    13.      mov al,ch
    14.      not cl; cl=al-1
    15.      and al,cl; обнулили крайний справа единичный бит
    16.      jnz a2
    17. a1: test ah,ah
    18.      jz a3; проверили сразу 8 бит - ничего нет - идем далее
    19. a4: mov ch,ah
    20.      mov cl,ah
    21.      neg cl
    22.      and ah,cl; выделили крайний справа единичный бит
    23.   --- табличное преобразование номера бита
    24.   --- добавляем к номеру бита 8
    25.   --- тут делаешь свои темные делишки ---
    26.      mov ah,ch
    27.      not cl; cl=ah-1
    28.      and ah,cl; обнулили крайний справа единичный бит
    29.      jnz a4
    30. a3: bswap eax; проверяем 3-ий и 4-ый байты
    31.      test ax,ax
    32.      jz quit
    33.      test ah,ah; проверяем 3-ий байт
    34.      jz a5; проверили сразу 8 бит - ничего нет - идем далее
    35. a6: mov ch,ah
    36.      mov cl,ah
    37.      neg cl
    38.      and ah,cl; выделили крайний справа единичный бит
    39.   --- табличное преобразование номера бита
    40.   --- добавляем к номеру бита 16
    41.   --- тут делаешь свои темные делишки ---
    42.      mov ah,ch
    43.      not cl; cl=ah-1
    44.      and ah,cl; обнулили крайний справа единичный бит
    45.      jnz a6
    46.      test al,al
    47.      jz quit
    48. a5: mov ch,al
    49.      mov cl,al
    50.      neg cl
    51.      and al,cl; выделили крайний справа единичный бит
    52.   --- табличное преобразование номера бита
    53.   --- добавляем к номеру бита 24
    54.   --- тут делаешь свои темные делишки ---
    55.      mov al,ch
    56.      not cl; cl=al-1
    57.      and al,cl; обнулили крайний справа единичный бит
    58.      jnz a5
    59. quit:
    ЗЫ. А вообще, метод предложеный crypto, наверное, еще быстрее...
     
  2. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Mikl__
    Тогда уж и я внесу свою ИМХО-лепту:
    Создаешь таблицу из 256*9 записей длины 9, в которой для каждого байта B будет храниться запись вида N,I1,...,IN, где N - количество единичных битов в байте, I1,...,IN - номера позиций этих битов. За одно обращение ты получаешь для данного байта B адрес соответствующей ему записи, в цикле получаешь все позиции (цикл будет оптимальным, поскольку лишнего в нем ничего не будет).
    Для следующего байта делаешь то же самое, только к номерам позиций добавляешь 8 и т.д.
    Сравниваешь предварительно байт с 0.
     
  3. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    crypto
    Это было в #16 - зачем же ты убрал это сообщение?
     
  4. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Mikl__
    Я подумал, что решение весьма громоздко, поскольку не знаю контекста (что за "темные делишки"). Потому и удалил, а ты прочитать успел :-)
     
  5. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    crypto
    А как насчет этого - идея сырая, но смысл как у кода Хемминга
    Код (Text):
    1. test eax,eax
    2.     jz exit; бит равных 1 нет совсем
    3.     test eax,55555555h
    4.     setz bl; единичные биты нечетные
    5.     test eax,33333333h
    6.     setz bh
    7.     test eax,0F0F0F0Fh
    8.     setz cl;
    9.     test eax,0000FFFFh
    10.      setz ch
    11. --- анализ bl, bh, cl, cd и вывод номера каких битов=1
     
  6. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Mikl__
    Пусть аффтар все эти идеи потестит, протикает и выдаст нам свое решение :-)
     
  7. wasm_test

    wasm_test wasm test user

    Публикаций:
    0
    Регистрация:
    24 ноя 2006
    Сообщения:
    5.582
    Размер таблицы можно значительно сократить, если учесть, что все 8 бит установлены только в одном числе (-1), которое можно проверить явно. и на номера бит можно отвести по 3 бита (на число бит тоже 3 бита). 3*(7+1)=24 = 3 байта на каждую запись :)
     
  8. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    Great
    Спасибо за оптимизацию, только это приведет к дополнительным вычислениям:
    Кол-во данных*Кол-во кода >= CONST (Неопределенность Гейзенберга для программирования).
     
  9. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.922
    реализация зависит от "выходного формата", можно использовать и bt, если дополнить подпрограмму "сканирование бит" ещё каким-нибудь кодом.

    P.S. ещё зависит от объёма данных (а вдруг не eax ;)
     
  10. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    А чего тестить? Оставлю bsf. Гребенка хороша для каких-нить олимпиадных задач и когда запрещено пользоваться bsf. А байтовый вариант требует 256 ветвтлений, что я тоже кодить не буду.. А вот как улучшить bsf предложений не было...
     
  11. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    persicum
    Отставляй ;)
    Только учти, что bsf\bsr - сложные инструкции и их латентность сильно варьируется на разных процах (2 тика в Core-2, 8 в AMD и P4, и аж 16 в P4E). btc побыстрее, но тоже не "сахар" (1-2-9 тиков соотв-но). Можешь сам прикинуть на каком проце при скольки ед.битах связка bsf+btc будут выигрывать или проигрывать простому циклу с shr
    PS: неизвестно, что там у тебя скрывается под "темными делишками" с найденным битом - может тут и оптимизировать то незачем...
     
  12. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    да ничего особо "криминального" - просто написал очередную прогу для раздувания объемов информации. Валяется на ник фронт ру. Учитывая, что цены на носители стремительно падают, не такое уж и большое зло... Объем работы, зависящий от найденного бита, зависит от наличия SSE2. Если оно есть, то тогда я разумеется стараюсь загрузить все xmm регистры по максимуму и с ними хорошенько поработать, а если нет, ну тогда пара асмовских комманд - тут действительно поиск бита может быть time consuming.
    Но мне не жалко тех товарищей, у которых нетути sse2...
     
  13. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    В догонку, определение номера выделенного бита в eax, при этом не используем bs
    Код (Text):
    1.      xor ebx,ebx
    2.      test eax,eax
    3.      jz quit
    4.      test eax,10101010101010101010101010101010b
    5.      setnz bh
    6.      shr ebx,1
    7.      test eax,11001100110011001100110011001100b
    8.      setnz bh
    9.      shr ebx,1
    10.      test eax,11110000111100001111000011110000b
    11.      setnz bh
    12.      shr ebx,1
    13.      test eax,11111111000000001111111100000000b
    14.      setnz bh
    15.      shr ebx,1
    16.      test eax,11111111111111110000000000000000b
    17.      setnz bh
    18.      shr ebx,4; в ebx номер бита
     
  14. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Поздравляю, ты изобрел коды Рида_мюллера =)))
     
  15. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Опять у тебя все не полюдски, на этот раз нужно перевернуть этот код с головы на ноги.
    Начинать вместо test eax,eax с test eax,FFFFFFFFh, что одно и тоже, но эстетика и математическая полнота требуют. Потом двигать влево, потом тестить FFFF0000, FF00FF00, F0F0F0F0 и т.д.

    Но и ты учти, что наивысшая энтропия достигается при равновероятном числе нулей и единиц, стало быть латентность test,jz,shr нужно удвоить, ибо эта связка будет в половине случаев работать в холостую.А bsf не работает в холостую, на нулях не вспотыкается.
     
  16. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    persicum
    Мог бы мне и не отвечать, но на самом деле приятно, что "изобрел коды Рида-мюллера =)))" хотя в #25 я писал "смысл как у кода Хемминга" - какие-то ассоциации с корректирующими кодами в голове крутились
    Где было "не по-людски" в первый раз? "Начинать вместо test eax,eax " - если нет взведенного бита - то и проверять нечего - quit, а уж как обнаружить в eax ноль - через and, or, add - дело вкуса. "Потом двигать влево" - установить бит в bh, затем сдвинуть влево, чтобы следующая инструкция setnz bh сбросила все результаты в ноль/единицу? - а вот при сдвиге ebx вправо все результаты накапливаются в bl. Далее persicum пишет, вероятно, для leo, хотя
    Цитата из leo в #31, а вот моя в #6
     
  17. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Мдя, со сдвигом влево код длиннее получается =(((
    Зато все по правильному, по кашерному =)))

    Код (Text):
    1.  xor ebx,ebx
    2.  test eax,$FFFFFFFF
    3.  jz @nobit
    4.  
    5.  test eax,$FFFF0000
    6.  setnz bl
    7.  or bh,bl
    8.  
    9.  shl ebx,1
    10.  test eax,$FF00FF00
    11.  setnz bl
    12.  or bh,bl
    13.  shl ebx,1
    14.  test eax,$F0F0F0F0
    15.  setnz bl
    16.  or bh,bl
    17.  shl ebx,1
    18.  test eax,$CCCCCCCC
    19.  setnz bl
    20.  or bh,bl
    21.  shl ebx,1
    22.  test eax,$AAAAAAAA
    23.  setnz bl
    24.  or bh,bl
    25.  
    26.  shr ebx,8
    27.  //----в ebx - номер бита
    28.  
    29. @nobit:
     
  18. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Придумал!!!
    Заместа трех коммандочек
    Код (Text):
    1.  setnz bl
    2.  or bh,bl
    3.  shl ebx,1
    можно использовать две их штук:
    Код (Text):
    1. setnz cl
    2. lea ebx,[ecx+ebx*2]
    Так што паритет, хотя твой вариант с bh опять-таки был довольно изобретательным...
     
  19. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    persicum
    Код (Text):
    1. ;Выделение самого правого единичного бита (число в eax, результат в ecx)
    2.    mov ecx,eax
    3.    neg ecx
    4.    and ecx,eax
    5.    ...
    6.    xor eax,ecx; удаляем самый правый единичный бит
     
  20. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Наверное, слова насчет "правильности" ты сочел просто за стеб, но по мне этож ведь схема Горнера, а в ней логичнее стартовать с коффициентов наивысших степеней и умножать, а не делить.

    На счет NEG - без поллитра не сообразить, ща запущу отладчик и посмотрю, что там с битами делается... На первый взгляд напоминает Брезенхема - непонятно как, но работает.=)))