Как реализовать функцию _BitScanReverse () для MS? - PullRequest
Новая
       2

Как реализовать функцию _BitScanReverse () для MS?

3 голосов
/ 30 мая 2011

От MSDN Поиск данных маски от старшего значащего бита (MSB) до младшего значащего бита (LSB) для установленного бита (1).

беззнаковый символ _BitScanReverse ( беззнаковый длинный * указатель, длинная маска без знака )

Параметры [out] Индекс Загружается с позицией бита первого найденного бита (1).

[in] Маска 32-разрядное или 64-разрядное значение для поиска.

Возвращаемое значение 0, если маска равна нулю; ненулевое значение в противном случае.

Примечания Если установленный бит найден, позиция бита первого найденного установленного бита возвращается в первом параметре. Если установленный бит не найден, возвращается 0; в противном случае возвращается 1


Подскажите пожалуйста, как реализовать безопасную и быструю _BitScanReverse () функцию на OS X ? Нужно ли использовать сборку или есть более простой способ?

Ответы [ 2 ]

3 голосов
/ 30 мая 2011

GCC имеет несколько подобных встроенных модулей:

- Встроенная функция: int __builtin_clz (без знака int x)

Возвращает количество старших 0-битов в x, начиная с самой старшей битовой позиции. Если х равен 0, результат не определен.

- Встроенная функция: int __builtin_ctz (без знака int x)

Возвращает количество завершающих 0 битов в x, начиная с позиции младшего разряда. Если х равен 0, результат не определен

Если у вас есть количество нулей, вы сможете определить, где находится первая 1. : -)

0 голосов
/ 30 мая 2011

Приведенный ниже код - это то, что я написал некоторое время назад для Linux - он находит бит с наибольшим установленным значением, который, я думаю, является тем, о чем вы просите. Он не соответствует вашим точным спецификациям, но должен легко адаптироваться.

Дополнительные примечания:

  • Возвращение 0 означает, что бит 0 был установлен; если биты не найдены, возвращается 64.
  • Этот ассемблер написан для соглашения о вызовах, используемого GCC под Linux. Я не знаю, чем это отличается в Mac OS X - вам нужно проверить.
  • Ввод 64-разрядного целого без знака.
  • Каждая архитектура ЦП записывается в отдельный исходный файл .S и выборочно компилируется с использованием 'gcc' в зависимости от создаваемой цели. Я не использую встроенный ассемблер.

x86: 

/*
 * Find the highest set bit in a bitboard.
 *
 * %eax: &bb
 */
.globl x86_msb;
.type x86_msb,@function;
x86_msb:
    mov 4(%eax), %edx
    bsr %edx, %eax
    jz msb_z1
    add $32, %eax
    ret
msb_z1:
    mov (%eax), %edx
    bsr %edx, %eax
    jz msb_z2
    ret
msb_z2:
    mov $64, %eax
    ret

x86_64: 

/*
 * Return the offset of the highest set bit in the bitmask
 *
 * %rdi: &bb
 */
.globl x64_msb;
.type x64_msb,@function;
x64_msb:
    movq (%rdi), %rdi
    bsrq %rdi, %rax
    jz msb_empty
    ret
msb_empty:
    mov $64, %eax
    ret

Вот реализации Windows (файл .asm):

x86: 

;;
;; Return the offset of the highest set bit in the bitmask
;;
;; ECX: &bb
;;
public @x86_msb@4
@x86_msb@4:
    mov edx, dword ptr [ecx + 4]    ; bb (high)
    bsr eax, edx
    jz msb_z1
    add eax, 32
    ret
msb_z1:
    mov edx, dword ptr [ecx]        ; bb (low)
    bsr eax, edx
    jz msb_z2
    ret
msb_z2:
    mov eax, 64
    ret                         ; bb is empty

x86_64: 

;;
;; Return the offset of the highest set bit in the bitmask
;;
;; RCX: &bb
;;
x64_msb PROC
    mov r8, qword ptr [rcx] ; r8 = bb
    bsr rax, r8         ; rax = lsb(bb)
    jz msb_empty
    ret
msb_empty:
    mov eax, 64         ; bb was empty
    ret
x64_msb ENDP
...