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

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

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

  1. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Очень, очень интересно!!! В какой книженции ты все это вычитал?
    Достойная замена может быть для btc. А вот логарифмировать регистр ecx предполагается с помощью все той же команды bsf =))) Шутка... Блин, а нельзя вот так вот быстро и чтобы был сразу нужный номер бита? Хотя да, для единичных бит действительно можно построить байтовую таблицу логарифмов. Но лазать в нее придется в худшем случае целых 4 раза, тут не грех вспомнить и о гребенке. А если без таблицы? Мож сопр поможет? Сопр должен мгновенно двоичный лог брать. Или вот, можно через сопр преобразовать целое в single и посмотреть у него экспоненту.
     
  2. Mikl_

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    persicum
    Рекомендую, Генри Уорен "Алгоритмические трюки для программистов" (Henry Warren "Hacker's Delight")
     
  3. valterg

    valterg Active Member

    Публикаций:
    0
    Регистрация:
    19 авг 2004
    Сообщения:
    2.105
    persicum
    Если ты про сопроцессор, то забудь. Недавно разбирался с потерей точности в Фортран-проге.
    Залез в библиотеку Интела и обнаружил, что они уже с 7-й версии считают логарифм и синусы
    через SSE. Так быстрее. А главное точнее. У сопра в LN(2) последний бит неверный :-(
     
  4. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    valterg
    Дробный логарифм здесь не нужен. А целый - это двоичная экспонента числа, получается ес-но точно (при fild), но ес-но не быстрее, а дольше bsf\bsr, т.к. число нужно загрузить, выгрузить, загрузить эксп-ту и вычесть смещение (про fxtract и говорить нечего - это вообще тормоз)
     
  5. persicum

    persicum New Member

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

    Mikl_ New Member

    Публикаций:
    0
    Регистрация:
    14 ноя 2006
    Сообщения:
    907
    persicum
    При последовательном получении номеров бит также можно учесть, что если сейчас был бит с номером 15, то у следующих битов 5-ый бит равен 1 и т.д.
     
  7. sarin

    sarin Member

    Публикаций:
    0
    Регистрация:
    2 июн 2005
    Сообщения:
    30
    В продолжение темы:
    Код (Text):
    1. ...
    2. unsigned char a, b, c, d;
    3. unsigned long f; // abcdabcdabcdabcdabcdabcdabcdabcd binary
    4. ...
    5.  
    6. a = 0;b = 0;c = 0;d = 0;
    7.  
    8. if (f & 0x80000000) a |= 0x80;
    9. if (f & 0x8000000) a |= 0x40;
    10. if (f & 0x800000) a |= 0x20;
    11. if (f & 0x80000) a |= 0x10;
    12. if (f & 0x8000) a |= 0x08;
    13. if (f & 0x800) a |= 0x04;
    14. if (f & 0x80) a |= 0x02;
    15. if (f & 0x8) a |= 0x01;
    16.  
    17. if (f & 0x40000000) b |= 0x80;
    18. if (f & 0x4000000) b |= 0x40;
    19. if (f & 0x400000) b |= 0x20;
    20. if (f & 0x40000) b |= 0x10;
    21. if (f & 0x4000) b |= 0x08;
    22. if (f & 0x400) b |= 0x04;
    23. if (f & 0x40) b |= 0x02;
    24. if (f & 0x4) b |= 0x01;
    25.  
    26. if (f & 0x20000000) c |= 0x80;
    27. if (f & 0x2000000) c |= 0x40;
    28. if (f & 0x200000) c |= 0x20;
    29. if (f & 0x20000) c |= 0x10;
    30. if (f & 0x2000) c |= 0x08;
    31. if (f & 0x200) c |= 0x04;
    32. if (f & 0x20) c |= 0x02;
    33. if (f & 0x2) c |= 0x01;
    34.  
    35. if (f & 0x10000000) d |= 0x80;
    36. if (f & 0x1000000) d |= 0x40;
    37. if (f & 0x100000) d |= 0x20;
    38. if (f & 0x10000) d |= 0x10;
    39. if (f & 0x1000) d |= 0x08;
    40. if (f & 0x100) d |= 0x04;
    41. if (f & 0x10) d |= 0x02;
    42. if (f & 0x1) d |= 0x01;
    A такой расчёт можно оптимизировать по скорости?

    Видятся два варианта расчёта:

    1-й: "сдвинутый"

    Код (Text):
    1. eax = f
    2. bh = a
    3. bl = b
    4. ch = c
    5. cl = d
    6.  
    7. ; #1
    8. rcl eax,1
    9. rcl bh,1
    10. rcl eax,1
    11. rcl bl,1
    12. rcl eax,1
    13. rcl ch,1
    14. rcl eax,1
    15. rcl cl,1
    16. ; #2
    17. rcl eax,1
    18. rcl bh,1
    19. rcl eax,1
    20. rcl bl,1
    21. rcl eax,1
    22. rcl ch,1
    23. rcl eax,1
    24. rcl cl,1
    25. ...
    26. ; #8
    27. rcl eax,1
    28. rcl bh,1
    29. rcl eax,1
    30. rcl bl,1
    31. rcl eax,1
    32. rcl ch,1
    33. rcl eax,1
    34. rcl cl,1
    2-й: "тестовый"

    Код (Text):
    1. eax = f
    2. bh = a
    3. bl = b
    4. ch = c
    5. cl = d
    6.  
    7.  test eax,0x80000000
    8.  jz @@:
    9.  Or Bh,0x80
    10. @@:
    11.  test eax,0x8000000
    12.  jz @@:
    13.  Or Bh,0x40
    14. @@:
    15. ...
    16.  test eax,0x10
    17.  jz @@:
    18.  Or Cl,0x2
    19. @@:
    20.  test eax,0x1
    21.  jz @@:
    22.  Or Cl,0x1
    23. @@:
    Есть ли ещё варианты с учетом того что обрабатывается большой поток данных ? Имеет ли смысл "отлавливать" нулевые значения и пропускать дальнейшие проверки eax?
     
  8. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Это классическая задачка на сборку\раздвижку бит с использованием умножения на константу. Умножение f*magic это по сути сумма из N сдвинутых чисел f, где N и сдвиги определяются кол-вом и позициями единичных бит константы magic. Пример
    Код (Text):
    1. mov eax,[f]
    2. and eax,88888888h ;выделяем нужные биты
    3. imul eax,2481h ;умножаем на magic = 1001001001b, чтобы биты собрались в группы по 4
    4. and eax,0F000F000h ;выделяем 2 нужные группы
    5. mov edx,eax            ;сдвигаем и объединяем
    6. shr eax,12
    7. shr edx,24
    8. or edx,eax
    9. mov [a],edx
    Для b,c,d аналогично - только меняются константы в and и shr. Для лучшего распараллеливания можно одновременно (вперемежку) выполнять выделение пар чисел a,b и затем c,d или даже все 4 сразу
     
  9. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159
    Mikl__
    Аналогичного добра много и в онлайне:
    http://www.jjj.de/bitwizardry/bitwizardrypage.html
    http://aggregate.org/MAGIC/
    http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
     
  10. Intro

    Intro Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    164
    Интересно когда нить появится команды асма для подсчёта количества бит, есть ряд алгоритмов котором эта команда сильна помогла.
     
  11. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Intro
    есть такая, POPCNT
     
  12. Intro

    Intro Member

    Публикаций:
    0
    Регистрация:
    29 авг 2009
    Сообщения:
    164
    Кто подскажет какая самая быстрый код для подсчёта кол. бит, можно х86 в плоть до SSE но не выше.
    X:=i;
    dec(x,(x shr 1) AND $5555555555555555);
    x:= (x AND $3333333333333333) + ((x shr 2) AND $3333333333333333);
    x:= (x + (x shr 4)) AND $0f0f0f0f0f0f0f0f;
    inc(x,x shr 8);
    inc(x,x shr 16);
    inc(x,x shr 32);
    x:=x and $FF; // 50 takt athlon XP 2200 }

    x:= (x AND $55555555) + ((x AND $AAAAAAAA) shr 1);
    x:= (x AND $33333333) + ((x AND $CCCCCCCC) shr 2);
    x:= (x AND $0F0F0F0F) + ((x AND $F0F0F0F0) shr 4);
    x:= (x AND $00FF00FF) + ((x AND $FF00FF00) shr 8);
    x:= (x AND $0000FFFF) + ((x AND $FFFF0000) shr 16);
    это два варианта, нужен самый быстрый, можно асме но только что бы можно было в делфи вставить.
     
  13. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Intro
    Табличный самый быстрый.
     
  14. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Intro
    во-во, сделай таблицу на 65536 и получай сумму битов в слове за одно действие!
     
  15. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    persicum
    А почему именно на 65536? А если L1 всего 32К, не лучше ли тогда использовать таблицу на 256 значений?
     
  16. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    621
    Из AMD Code Optimization Guide
    Код (Text):
    1. unsigned int popcount(unsigned int v)
    2. {
    3.     unsigned int retVal;
    4.     __asm {
    5.     MOV EAX,[v]     ;v
    6.     MOV EDX,EAX     ;v
    7.     SHR EAX,1       ;v>>1
    8.     AND EAX,055555555h  ;(v>>1)&0x55555555
    9.     SUB EDX,EAX     ;w=v-((v>>1)&0x55555555)
    10.     MOV EAX,EDX     ;w
    11.     SHR EDX,2       ;w>>2
    12.     AND EAX,033333333h  ;w&0x33333333
    13.     AND EDX,033333333h  ;(w>>2)&0x33333333
    14.     ADD EAX,ED      ;x=(w&0x33333333)+((w>>2)&0x33333333)
    15.     MOV EDX,EAX     ;x
    16.     SHR EAX,4       ;x>>4
    17.     ADD EAX,EDX     ;x+(x>>4)
    18.     AND EAX,00F0F0F0Fh  ;y=(x+(x>>4)&0x0F0F0F0F)
    19.     IMUL    EAX,001010101h  ;y*0x01010101
    20.     SHR EAX,24      ;result=(y*0x01010101)>>24
    21.     MOV retVal,EAX
    22.     }
    23.     return(retVal);
    24. }
     
  17. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Black_mirror
    А при чём здесь L1? Достаточно L2.
     
  18. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.922
    насколько быстрее POPCNT чем подсчет сложениями и сдвигами?
     
  19. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    621
    POPCNT вроде-бы за 2 такта выполняется.
     
  20. murder

    murder Member

    Публикаций:
    0
    Регистрация:
    3 июн 2007
    Сообщения:
    621
    На атлонах

    http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/40546.pdf

    страница 247