Деление и модуль с использованием одной инструкции divl (i386, amd64)

Question

Я пытался придумать встроенную сборку для GCC, чтобы получить и деление и модуль, используя один divl инструкция. К сожалению, я не так хорош в сборке. Может ли кто-нибудь помочь мне в этом? Спасибо.

Answer 1

Да - divl произведет частное в eax, а остаток в edx. Используя синтаксис Intel, например:

mov eax, 17
mov ebx, 3
xor edx, edx
div ebx
; eax = 5
; edx = 2

Answer 2

Вы ищете что-то вроде этого:

__asm__("divl %2\n"
       : "=d" (remainder), "=a" (quotient)
       : "g" (modulus), "d" (high), "a" (low));

Хотя я согласен с другими комментаторами, что обычно GCC сделает это за вас, и вам следует избегать встроенной сборки, когда это возможно, иногда вам нужна эта конструкция.

Например, если старшее слово меньше, чем модуль, тогда безопасно выполнить деление следующим образом. Тем не менее, GCC не достаточно умен, чтобы понять это, потому что в общем случае деление 64-битного числа на 32-битное число может привести к переполнению, и поэтому он вызывает библиотечную процедуру для выполнения дополнительной работы. (Замените на 128-битный /64-битный для 64-битных ISA.)

Answer 3

Вы не должны пытаться оптимизировать это самостоятельно. GCC уже делает это.

volatile int some_a = 18, some_b = 7;

int main(int argc, char *argv[]) {
    int a = some_a, b = some_b;
    printf("%d %d\n", a / b, a % b);
    return 0;
}

Бег

gcc -S test.c -O

доходность

main:
.LFB11:
    .cfi_startproc
    subq    $8, %rsp
    .cfi_def_cfa_offset 16
    movl    some_a(%rip), %esi
    movl    some_b(%rip), %ecx
    movl    %esi, %eax
    movl    %esi, %edx
    sarl    $31, %edx
    idivl   %ecx
    movl    %eax, %esi
    movl    $.LC0, %edi
    movl    $0, %eax
    call    printf
    movl    $0, %eax
    addq    $8, %rsp
    .cfi_def_cfa_offset 8
    ret

Обратите внимание, что остаток, %edx, не перемещается, поскольку он также является третьим аргументом, передаваемым в printf.

РЕДАКТИРОВАТЬ: 32-разрядная версия менее запутанным. Прохождение -m32 дает

main:
    pushl   %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $16, %esp
    movl    some_a, %eax
    movl    some_b, %ecx
    movl    %eax, %edx
    sarl    $31, %edx
    idivl   %ecx
    movl    %edx, 8(%esp)
    movl    %eax, 4(%esp)
    movl    $.LC0, (%esp)
    call    printf
    movl    $0, %eax
    leave
    ret

Answer 4

К счастью, вам не нужно прибегать к встроенной сборке, чтобы добиться этого. gcc сделает это автоматически, когда сможет.

$ cat divmod.c

struct sdiv { unsigned long quot; unsigned long rem; };

struct sdiv divide( unsigned long num, unsigned long divisor )
{
        struct sdiv x = { num / divisor, num % divisor };
        return x;
}

$ gcc -O3 -std=c99 -Wall -Wextra -pedantic -S divmod.c -o -

        .file   "divmod.c"
        .text
        .p2align 4,,15
.globl divide
        .type   divide, @function
divide:
.LFB0:
        .cfi_startproc
        movq    %rdi, %rax
        xorl    %edx, %edx
        divq    %rsi
        ret
        .cfi_endproc
.LFE0:
        .size   divide, .-divide
        .ident  "GCC: (GNU) 4.4.4 20100630 (Red Hat 4.4.4-10)"
        .section        .note.GNU-stack,"",@progbits

Answer 5

Вот пример кода ядра Linux о divl

    /*
 * do_div() is NOT a C function. It wants to return
 * two values (the quotient and the remainder), but
 * since that doesn't work very well in C, what it
 * does is:
 *
 * - modifies the 64-bit dividend _in_place_
 * - returns the 32-bit remainder
 *
 * This ends up being the most efficient "calling
 * convention" on x86.
 */
#define do_div(n, base)                     \
({                              \
    unsigned long __upper, __low, __high, __mod, __base;    \
    __base = (base);                    \
    if (__builtin_constant_p(__base) && is_power_of_2(__base)) { \
        __mod = n & (__base - 1);           \
        n >>= ilog2(__base);                \
    } else {                        \
        asm("" : "=a" (__low), "=d" (__high) : "A" (n));\
        __upper = __high;               \
        if (__high) {                   \
            __upper = __high % (__base);        \
            __high = __high / (__base);     \
        }                       \
        asm("divl %2" : "=a" (__low), "=d" (__mod)  \
            : "rm" (__base), "0" (__low), "1" (__upper));   \
        asm("" : "=A" (n) : "a" (__low), "d" (__high)); \
    }                           \
    __mod;                          \
})