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

Задачка 2^n => n (без BSF/BSR, переходов и таблиц)

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

  1. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    В регистре разрядностью N(можно решать задачу для некоторого конкретного N) имеется число вида 2^n (с одним единичным разрядом). Нужно построить функцию, которая(без BSF/BSR, переходов и таблиц) вычислит номер единичного бита. Или хотя бы взаимооднозначно отобразит множество чисел вида 2^n во множество чисел 0 .. (N-1). В последнем случае нужно построить и обратную функцию.
    Например, пусть для N=8, нам удалось построить такую функцию:
    Код (Text):
    1. 00000001 -> 000   0
    2. 00000010 -> 001   1
    3. 00000100 -> 010   2
    4. 00001000 -> 101   3
    5. 00010000 -> 011   4
    6. 00100000 -> 111   5
    7. 01000000 -> 110   6
    8. 10000000 -> 100   7
    Теперь нужно либо построить функцию которая из второго столбца получит первый, либо получит из него третий столбец(тогда построение обратной функции будет уже тривиальным).
     
  2. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    На ум лезет подсчет кол-ва единиц в числе x-1 через умножения на магик-намберы...
    Хотя для небольших N, это м.б. и не лучший способ
     
  3. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Для одной тетрады можно по битовой табличке MagicNumber сделать:
    x4 = (MagicNumber >> y4*3) & 7; //MagicNumber = 0x3002044
     
  4. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    492
    Адрес:
    г. Владимир
    //del
    (пересмотрел алгоритм Копперсмита и понял, что он содержит в себе циклы)
     
  5. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    DEEP
    :-) Смешно. Хотел придумать ещё больший overkill для наглядности, но Ваш вариант переплюнуть не смог. В пределах двадцати байт и двадцати тактов x86 этот алгоритм реализуете? Потому что первая половина задания реализуется где-то в таких пределах, если не меньше.
     
  6. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    492
    Адрес:
    г. Владимир
    l_inc
    Ну вообще-то я говорил серьёзно, подумав о на самом деле произвольном N.
    А теперь вот всю ночь не усну — буду думать, как вообще возможно аппроксимировать логарифм с приемлемой экстраполяцией (т.к. ТС явно указывает на неограниченность N) на фиксированных двадцати тактах ЦП, без циклов.
     
  7. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    DEEP
    Ваш вариант в любом случае — перебор. Кроме того:
    Но могу уточнить вопрос: "В пределах двадцати байт и двадцати тактов x86 для N=32 этот алгоритм реализуете?"
    Рассчитываете, что теперь уснёте раньше? :-)
     
  8. s_d_f

    s_d_f New Member

    Публикаций:
    0
    Регистрация:
    15 май 2008
    Сообщения:
    342
    А почему без BSF/BSR, переходов и таблиц?

    Код (Text):
    1. cnt_shl=1
    2. mov edx,-1 ; -1 останется если в eax не 2^n
    3. xor ecx,ecx
    4. N=32
    5. REPEAT N
    6.     cmp eax,cnt_shl
    7.     cnt_shl=cnt_shl shl 1
    8.     cmovz edx,ecx
    9.     inc ecx
    10. ENDM
     
  9. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    492
    Адрес:
    г. Владимир
    l_inc
    Ладно, тогда ещё одна идея на сон грядущий, уже из области дискры, а не матана.

    Рассмотрим биты регистра. Модифицируем таблицу из поста [1], и обозначим её за T:
    Код (Text):
    1. 00000001 -> 000
    2. 00000010 -> 001
    3. 00000100 -> 010
    4. 00001000 -> 011
    5. 00010000 -> 100
    6. 00100000 -> 101
    7. 01000000 -> 110
    8. 10000000 -> 111
    Составим новую таблицу T` в log2(N) строк, где справа в i-й строке будет взведён i-й бит, а слева будет битовая маска, составленная OR`ом из всех левых частей таблицы T, для которых в правой части T этот бит взведён.
    Так, для T из поста [0], имеем T`:
    Код (Text):
    1. 10101010 -> 001
    2. 11001100 -> 010
    3. 11110000 -> 100
    В итоге, мы можем построить функцию из [1] за логарифмическое время.


    Так, для N=8, задача решается за 8 тактов:
    Код (Text):
    1. TEST AL, 11110000b;
    2. SETNE CL;
    3. TEST AL, 11001100b;
    4. SETNE BL;
    5. TEST AL, 10101010b;
    6. SETNE AL;
    7. LEA EAX, [EAX + ECX*4];
    8. LEA EAX, [EAX + EBX*2];
    [UPD #1:]
    Ах да, на всякий случай поясню принцип действия.
    Всё что мы делаем — это набираем номер искомого бита поразрядно.
    Если
    то это значит, что в номере взведён i-тый разряд.

    [UPD #2:]
    Код для N=32 (вход — EAX, выход — ECX):
    Код (Text):
    1. XOR EDX, EDX;
    2.  
    3. TEST EAX, 11111111111111110000000000000000b;
    4. SETNE DL;
    5. MOV ECX, EDX;
    6.  
    7. TEST EAX, 11111111000000001111111100000000b;
    8. SETNE DL;
    9. LEA ECX, [ECX*2 + EDX];
    10.  
    11. TEST EAX, 11110000111100001111000011110000b;
    12. SETNE DL;
    13. LEA ECX, [ECX*2 + EDX];
    14.  
    15. TEST EAX, 11001100110011001100110011001100b;
    16. SETNE DL;
    17. LEA ECX, [ECX*2 + EDX];
    18.  
    19. TEST EAX, 10101010101010101010101010101010b;
    20. SETNE DL;
    21. LEA ECX, [ECX*2 + EDX];
    Итого — 16 тактов.
     
  10. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    DEEP
    Это всё уже было. Самый быстрый вариант такой. С табличкой в n байт. Теперь табличка почему-то не допускается, но без неё среднюю колонку ни в правую не перевести ни в левую (из таблицы первого поста).
     
  11. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    492
    Адрес:
    г. Владимир
    l_inc
    Ну вот, опять не ко двору.

    Злые вы, уйду я от вас =)
     
  12. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    l_inc
    Но "квазитаблицу" <= 32 бит, наверное неразумно запрещать, т.к. она по сути не отличается от прочих "выкрутасов" с magic number'ами
     
  13. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    leo
    Думаю, что "квазитаблицу" и не запрещали. Но, наверное, решение должно всё-таки как-то масштабироваться хотя бы на 32, а может и на 64 бита. Не выльются ли выкрутасы с квазитаблицей в выкрутасы с таблицей без значительных накладных?
    DEEP
    Да ладно. :-) Обещаю не критиковать дальнейшие предложения.
     
  14. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    Что касается получения из первого столбца второго(где числа уникальны, но не упорядочены), то там требуется всего две команды. А вот пример побитового восстановления первого столбца из второго(для 32 разрядов можно поступить аналогично, только магических чисел понадобится 5 и добавится еще 10 команд):
    Код (Text):
    1. 10000000 <- 100  
    2. 01000000 <- 110  
    3. 00100000 <- 111  
    4. 00010000 <- 011  
    5. 00001000 <- 101  
    6. 00000100 <- 010  
    7. 00000010 <- 001  
    8. 00000001 <- 000
    9.  
    10. eax - число от 0 до 7 из второго столбца
    11.  
    12. mov edx, not 11101000b
    13. mov ecx, not 01110100b
    14. mov ebx, not 00111010b
    15.  
    16. shr eax,1
    17. sbb esi,esi
    18. xor ebx,esi
    19.  
    20. shr eax,1
    21. sbb esi,esi
    22. xor ecx,esi
    23.  
    24. neg eax
    25. xor eax,edx
    26.  
    27. and eax,ebx
    28. and eax,ecx
     
  15. Maratyszcza

    Maratyszcza New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2006
    Сообщения:
    32
    Код (Text):
    1. ; Ktobyvydumali?
    2. magic_rabbit dq 4340000000000000h, 4340000000000000h
    3.  
    4. movd xmm0, eax
    5. orpd xmm0, [magic_rabbit]
    6. subsd xmm0, [magic_rabbit]
    7. pextrw eax, xmm0, 3
    8. shr eax, 4
    9. sub eax, 400h
     
  16. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    l_inc
    Не выльются, т.к. идея с квазитаблицей заключается не в том, чтобы применять ее к каждой тетраде, а в том, чтобы свести задачку к поиску нужной тетрады - а эта задачка элементарно решается методом умножения. Например, для 32 бит:
    Код (Text):
    1. ;eax - вх.число
    2. lea ecx,[eax*2-1] ;преобразуем 0100..0 в 0111..1
    3. and ecx,11111111h ;выдяляем младшие биты каждой тетрады
    4. imul ecx,11111111h ;суммируем эти биты
    5. shr ecx,28         ;получаем кол-во тетрад, включая искомую
    6. lea ecx,[ecx*4-4]  ;число бит до тетрады с установленным битом
    7.  
    8. mov edx,ecx
    9. shr eax,ecx         ;выделяем тетраду
    10. lea ecx,[eax+eax*2] ;индекс таблицы
    11. mov eax,0x3002044   ;таблица
    12. shr eax,ecx
    13. and eax,7           ;номер бита в тераде
    14. add eax,edx         ;номер бита в дворде
     
  17. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    leo
    Ну что сказать. Это... круто.
     
  18. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    leo
    Можно несколько улучшить, если вычислять номер бита в байте:

    Код (Text):
    1. imul ecx,eax,17171717h
    2. shr ecx,29; 2^n -> 0 1 2 5 3 7 6 4  0 1 2 5 3 7 6 4  0 1 2 5 3 7 6 4  0 1 2 5 3 7 6 4
    3. lea ecx, [101 110 011 111 100 010 001 000 0001000b + ecx*3];таблица перестановки + вычисление сдвига
    4. shr ecx,cl
    5. and ecx,7;теперь числа в правильном порядке
    6.  
    7. lea eax,[eax*2-1]
    8. and eax,01010101h
    9. imul eax,01010101h
    10. shr eax,24
    11. lea eax,[eax*8-8+ecx]
    Небольшая оптимизация второй части:
    Код (Text):
    1. shr eax,cl
    2. imul eax,00081018h
    3. shr eax,24
    4. add eax,ecx
     
  19. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    Black_mirror
    Первая идея с использованием imul для независимого вычисления смещения внутри байта\тетрады - это круто, но "оптимизация второй части" опять вносит зависимость и тем самым снижает ценность первой. Поэтому лучше обе части оставить независимыми и вернуться к тетрадам, т.к. это позволит еще больше упростить первую часть и вообще отказаться от таблицы:
    Код (Text):
    1. ;eax - вх.число, не равное 0
    2. lea ecx,[eax*2-1]  ;преобразуем 0100..0 в 0111..1
    3. imul eax,11111111h ;загоняем искомую тетраду вверх в 28-31 биты
    4. and ecx,11111111h  ;выдяляем младшие биты каждой тетрады
    5. imul ecx,11111111h ;суммируем эти биты
    6. cdq                ;edx=-1 для тетрады 1000b, иначе =0
    7. shr eax,29         ;= 0,1,2,4
    8. shr ecx,28         ;кол-во тетрад, включая искомую
    9. add eax,edx        ;= 0,1,2,3
    10. lea eax,[eax+ecx*4-4] ;искомый номер бита
    В итоге обе части должны выполняться паралельно и общее время будет определяться задержкой вычисления номера тетрады
     
  20. Proteus

    Proteus Member

    Публикаций:
    0
    Регистрация:
    19 июн 2004
    Сообщения:
    344
    Адрес:
    Russia