Масса Хэмминга (число 1 в ряду) смешивание C со сборкой
Я пытаюсь посчитать, сколько число 1, в числах массива.
Сначала у меня есть код на C lenguaje(работает нормально):
int popcount2(int* array, int len){
int i;
unsigned x;
int result=0;
for (i=0; i<len; i++){
x = array[i];
do{
result+= x & 0x1;
x>>= 1;
} while(x);
}
return result;
}
Теперь мне нужно перевести цикл do-while в Assembly, используя 3-6 строк кода. Я написал некоторый код, но результат не правильный (я новичок в мире сборки)
int popcount3(int* array, int len){
int i;
unsigned x;
int result=0;
for (i=0; i<len; i++){
x = array[i];
asm(
"ini3: \n"
"adc $0,%[r] \n"
"shr %[x] \n"
"jnz ini3 \n"
: [r]"+r" (result)
: [x] "r" (x) );
}
}
Я использую GCC (на Linux) с процессором Intel.
4 ответа
Самое приятное, что вы можете сделать, это использовать встроенный popcount функция, как предложено Полом Р., но так как вам нужно написать это в сборке, это сработало для меня:
asm (
"start: \n"
"and %0, %1 \n"
"jz end \n"
"shr $0, %1 \n"
"jnc start \n"
"inc %1 \n"
"jmp start \n"
"end: \n"
: "+g" (result),
"+r" (x)
:
: "cc"
);
В первых двух строках вы просто проверяете содержимое x (и идти до конца, если это ноль Jump Zero). Чем ты сдвигаешься x один бит вправо и:
В конце смены
CFфлаг содержит последний бит, сдвинутый из целевого оператора. *
Если нет CF установить, просто пойти, чтобы начать (Jump Not Carry) иначе увеличьте результат, а затем перейдите к началу.
И прекрасная мысль о сборке заключается в том, что вы можете делать вещи разными способами...
asm (
"start: \n"
"shr $1, %1 \n"
"jnc loop_cond \n"
"inc %0 \n"
"and %1, %1 \n"
"loop_cond: \n"
"jnz start \n"
: "+g" (result),
"+r" (x)
:
: "cc"
);
Здесь вы снова используете SHift Right инструкция, если нет CF присутствует просто перейти в состояние цикла.
В противном случае снова увеличиваем результат и вызываем двоичный AND (INC действительно изменить ZF).
С помощью LOOP а также ECX
Мне было любопытно, как это сделать в 3-х инструкциях (я подумал, что ваш учитель не даст вам нижний предел в 3, если это невозможно), и я понял, что x86 также имеет LOOP инструкция:
Каждый раз, когда выполняется инструкция LOOP, регистр счетчика уменьшается, а затем проверяется на 0. Если счетчик равен 0, цикл завершается, и выполнение программы продолжается с инструкцией, следующей за инструкцией LOOP. Если счетчик не равен нулю, выполняется близкий переход к операнду назначения (цели), который, вероятно, является инструкцией в начале цикла. *
И вы можете добавить входной аргумент, используя ограничение ввода GCC:
c-cрегистр.
asm (
"start: \n"
"shr $1, %1 \n"
"adc $0, %0 \n"
"loop start \n"
: "+g" (result)
: "r" (x),
"c" (8) // Assuming 8b type (char)
);
Просто чтобы убедиться, что он компилируется для правильной сборки:
0x000000000040051f <+25>: mov $0x8,%ecx
0x0000000000400524 <+30>: mov -0x8(%rbp),%eax
0x0000000000400527 <+33>: shr %edx
0x0000000000400529 <+35>: adc $0x0,%eax
0x000000000040052c <+38>: loop 0x400527 <main+33>
Я думаю, что первый должен иметь чуть лучшую производительность, особенно если установлен только 1 бит, такой подход всегда k*8 итерации.
SSE4 и одиночная инструкция
Я знаю, что вы должны использовать цикл, но просто для удовольствия... С расширением SSE4 вы можете сделать это всего лишь одной инструкцией POPCNT:
Эта инструкция вычисляет количество битов, установленных на 1 во втором операнде (источник) и возвращает счет в первом операнде (регистр назначения). *
Я думаю (у меня на ноутбуке довольно старый процессор, поэтому я не могу проверить это для вас), вы должны сделать это с помощью одной простой инструкции:
asm (
"POPCNT %1, %0 \n"
: "=r" (result)
: "mr" (x)
: "cc"
);
(Если вы попробуете это и у вас есть расширение SSE4, пожалуйста, дайте мне знать, если оно работает)
Спектакль
Я измерил время, необходимое для выполнения 100000000 поп-аккаунтов, сравнивая мои первый и второй методы с методами Дэвида Уолферда. [Необработанные данные]
+--------------+------------+------------+------------+
| | 0x00000000 | 0x80000001 | 0xffffffff |
+--------------+------------+------------+------------+
| 1st solution | 0.543 | 5.040 | 3.833 |
| LOOP | 11.530 | 11.523 | 11.523 |
| Davids | 0.750 | 4.893 | 4.890 |
+--------------+------------+------------+------------+
Если кто-нибудь может сравнить эти 3 с SSE4 POPCNT инструкция я был бы рад.
Вы начинаете с действительно неэффективного алгоритма - если вы используете лучший алгоритм, вам не нужно тратить время на ассемблер. Посмотрите Восхищение Хакера и / или Бит Тиддлинг Хаки для намного более эффективных методов.
Также обратите внимание, что более новые процессоры x86 имеют инструкцию POPCNT, которая выполняет все вышеперечисленное в одной инструкции (и вы можете вызывать ее через встроенную функцию, так что нет необходимости в asm).
И, наконец, gcc имеет встроенную функцию: __builtin_popcount, который снова делает все, что вам нужно - он будет использовать POPCNT на более новых процессорах и эквивалентный asm на более старых процессорах.
Когда мне нужно было создать поп-счет, я в конечном итоге использовал метод 5 и 3 из упомянутых Bit Twiddling Hacks @PaulR. Но если бы я хотел сделать это с помощью цикла, может быть, что-то вроде этого:
#include <stdio.h>
#include <stdlib.h>
int popcount2(int v) {
int result = 0;
int junk;
asm (
"shr $1, %[v] \n\t" // shift low bit into CF
"jz done \n" // and skip the loop if that was the only set bit
"start: \n\t"
"adc $0, %[result] \n\t" // add CF (0 or 1) to result
"shr $1, %[v] \n\t"
"jnz start \n" // leave the loop after shifting out the last bit
"done: \n\t"
"adc $0, %[result] \n\t" // and add that last bit
: [result] "+r" (result), "=r" (junk)
: [v] "1" (v)
: "cc"
);
return result;
}
int main(int argc, char *argv[])
{
for (int x=0; x < argc-1; x++)
{
int v = atoi(argv[x+1]);
printf("%d %d\n", v, popcount2(v));
}
}
adc почти всегда более эффективен, чем ветвление на CF.
"=r" (junk) является фиктивным выходным операндом, который находится в том же регистре, что и v ("1" ограничение). Мы используем это, чтобы сообщить компилятору, что оператор asm уничтожает v вход. Мы могли бы использовать [v] "+r"(v) чтобы получить операнд чтения-записи, но мы не хотим переменную C v быть обновленным.
Обратите внимание, что счетчик отключения цикла для этой реализации является позицией самого высокого установленного бита. (bsr, или же 32 - clz(v)). Реализация @rcgldr, которая очищает младший установленный бит на каждой итерации, обычно будет быстрее, когда число установленных битов невелико, но не все они находятся в нижней части целого числа.
сборка с использованием 3-6 строк кода.
В этом примере используется цикл из 4 инструкций:
popcntx proc near
mov ecx,[esp+4] ;ecx = value to popcnt
xor eax,eax ;will be popcnt
test ecx,ecx ;br if ecx == 0
jz popc1
popc0: lea edx,[ecx-1] ;edx = ecx-1
inc eax ;eax += 1
and ecx,edx ;ecx &= (ecx-1)
jnz short popc0
popc1: ret
popcntx endp
В этом примере используется цикл из 3 инструкций, но он будет медленнее, чем версия цикла из 4 инструкций на большинстве процессоров.
popcntx proc near
mov eax,[esp+4] ;eax = value to popcnt
mov ecx,32 ;ecx = max # 1 bits
test eax,eax ;br if eax == 0
jz popc1
popc0: lea edx,[eax-1] ;eax &= (eax-1)
and eax,edx
loopnz popc0
popc1: neg ecx
lea eax,[ecx+32]
ret
popcntx endp
Это альтернативный пример без зацикливания:
popcntx proc near
mov ecx,[esp+4] ;ecx = value to popcnt
mov edx,ecx ;edx = ecx
shr edx,1 ;mov upr 2 bit field bits to lwr
and edx,055555555h ; and mask them
sub ecx,edx ;ecx = 2 bit field counts
; 0->0, 1->1, 2->1, 3->1
mov eax,ecx
shr ecx,02h ;mov upr 2 bit field counts to lwr
and eax,033333333h ;eax = lwr 2 bit field counts
and ecx,033333333h ;edx = upr 2 bit field counts
add ecx,eax ;ecx = 4 bit field counts
mov eax,ecx
shr eax,04h ;mov upr 4 bit field counts to lwr
add eax,ecx ;eax = 8 bit field counts
and eax,00f0f0f0fh ; after the and
imul eax,eax,01010101h ;eax bit 24->28 = bit count
shr eax,018h ;eax bit 0->4 = bit count
ret
popcntx endp