128-битное деление, встроенное в Visual C ++

Мне интересно, действительно ли в Visual C ++ нет встроенной функции 128-битного деления?

Существует встроенная функция умножения 64x64 = 128 бит, называемая _umul128(), которая хорошо соответствует инструкции ассемблера MUL x64.

Естественно, я предположил, что будет также внутреннее деление 128/64 = 64 бит (моделирование инструкции DIV), но, к моему удивлению, ни Visual C ++, ни Intel C ++, похоже, не имеют его, по крайней мере, он не указан в intrin.h.

Кто-нибудь может это подтвердить? Я попытался найти имена функций в исполняемых файлах компилятора с помощью команды grep, но не смог найти _umul128, так что, думаю, я посмотрел не в том месте.

Обновление: по крайней мере, теперь я нашел шаблон umul128 (без ведущего подчеркивания) в c1.dll Visual C ++ 2010. Все остальные встроенные функции перечислены вокруг него, но, к сожалению, нет "udiv128" или тому подобное :( Так кажется, что они действительно «забыли» его реализовать.

Чтобы уточнить: я ищу не только 128-битный тип данных, но и способ разделить 128-битный скалярный int на 64-битный int в C ++. Либо встроенная функция, либо встроенная 128-битная целочисленная поддержка решила бы мою проблему.

Изменить: Ответ отрицательный, в Visual Studio 2010 до 2017 года не было _udiv128 встроенных функций, но они доступны в Visual Studio 2019 RTM.


visual-c++ intrinsics integer-division 128-bit
person cxxl    schedule 09.12.2011    source источник
comment
Это не часть ЭЛТ. Это встроенная функция, поставляется бесплатно с процессором. Но только в 64-битном режиме. Никакой халявы для div, пока вы не получите 128-битный процессор. Учитывая смехотворно широкий диапазон pow (2, 128), вам следует искать библиотеку произвольной точности. Таких много вокруг.   -  person Hans Passant    schedule 10.12.2011
comment
@TreeMonkie: __int18 не поддерживается VS, см. stackoverflow.com/questions/6759592/   -  person cxxl    schedule 10.12.2011
comment
@Hans: извините, я не понимаю. Это просто НЕ внутренняя функция, даже в 64-битном режиме. И мне нужно это, чтобы написать библиотеку произвольной точности :)   -  person cxxl    schedule 10.12.2011
comment
Что ж, тогда нет смысла искать коробочное решение. Вы знаете, как делать математику произвольной точности с бумагой и карандашом еще в начальной школе. 128 бит требует много бумаги, но у компьютеров их много.   -  person Hans Passant    schedule 10.12.2011
comment
@cxxl: я считаю, что 128-битные int не поддерживаются напрямую ... однако вы можете использовать их при использовании встроенных функций SSE. Я верю - но не цитируйте меня по этому поводу - что это __m128. Мне не совсем понятно из вопроса, пригодится ли SSE в этом сценарии или нет ...   -  person Daniel Placek    schedule 10.12.2011
comment
Обратите внимание, что если частное превышает RAX, div и idiv вызывают #DE исключение. Это делает его опасным для использования, если вы не проверите high_half < denominator или что-то в этом роде.   -  person Peter Cordes    schedule 31.01.2019

Ответы (4)


arrow_upward
2
arrow_downward

Я не специалист, но откопал вот это:

http://research.swtch.com/2008/01/division-via-multiplication.html

Интересный материал. Надеюсь, это поможет.

РЕДАКТИРОВАТЬ: Это тоже полезно: http://www.gamedev.net/topic/508197-x64-div-intrinsic/

person Daniel Placek    schedule 10.12.2011
comment
На самом деле это довольно неприятно. Даже если вы обнаружите, что требуется обратный + сдвиг, вам остается умножить свой 128-битный номер на обратное и взять верхние 64 бита из результата, что является серьезным PITA. - person yonil; 28.05.2016
comment
Также мне трудно поверить, что все это каким-то образом превзойдет инструкцию DIV / IDIV. - person yonil; 28.05.2016

arrow_upward
11
arrow_downward

Если вы не против небольших хаков, это может помочь (только в 64-битном режиме, не тестировалось):

#include <windows.h>
#include <stdio.h>

unsigned char udiv128Data[] =
{
  0x48, 0x89, 0xD0, // mov rax,rdx
  0x48, 0x89, 0xCA, // mov rdx,rcx
  0x49, 0xF7, 0xF0, // div r8
  0x49, 0x89, 0x11, // mov [r9],rdx
  0xC3              // ret
};

unsigned char sdiv128Data[] =
{
  0x48, 0x89, 0xD0, // mov rax,rdx
  0x48, 0x89, 0xCA, // mov rdx,rcx
  0x49, 0xF7, 0xF8, // idiv r8
  0x49, 0x89, 0x11, // mov [r9],rdx
  0xC3              // ret
};

unsigned __int64 (__fastcall *udiv128)(unsigned __int64 numhi,
                                       unsigned __int64 numlo,
                                       unsigned __int64 den,
                                       unsigned __int64* rem) =
  (unsigned __int64 (__fastcall *)(unsigned __int64,
                                   unsigned __int64,
                                   unsigned __int64,
                                   unsigned __int64*))udiv128Data;

__int64 (__fastcall *sdiv128)(__int64 numhi,
                              __int64 numlo,
                              __int64 den,
                              __int64* rem) =
  (__int64 (__fastcall *)(__int64,
                          __int64,
                          __int64,
                          __int64*))sdiv128Data;

int main(void)
{
  DWORD dummy;
  unsigned __int64 ur;
  __int64 sr;
  VirtualProtect(udiv128Data, sizeof(udiv128Data), PAGE_EXECUTE_READWRITE, &dummy);
  VirtualProtect(sdiv128Data, sizeof(sdiv128Data), PAGE_EXECUTE_READWRITE, &dummy);
  printf("0x00000123456789ABCDEF000000000000 / 0x0001000000000000 = 0x%llX\n",
         udiv128(0x00000123456789AB, 0xCDEF000000000000, 0x0001000000000000, &ur));
  printf("-6 / -2 = %lld\n",
         sdiv128(-1, -6, -2, &sr));
  return 0;
}
person Alexey Frunze    schedule 10.12.2011
comment
Для MSVC можно использовать раздел #pragma, чтобы поместить эти функции в сегмент кода во время компиляции. - person Marat Dukhan; 18.12.2011
comment
Почему нельзя использовать встроенную сборку? - person Autodidact; 02.02.2018
comment
@SandeepDatta Раньше компилятор не поддерживал 64-битный код. Поддерживается ли сейчас? - person Alexey Frunze; 06.02.2018
comment
Настоятельно рекомендую const unsigned char code[]; вы хотите, чтобы это было const, чтобы оно вошло в .rdata. Я не знаю, находится ли это уже рядом с разделом кода и, следовательно, исполняемым, например, .rodata входит в сегмент TEXT в Linux / ELF, но это должно помочь. И сделайте указатели на функции const или static const (или constexpr), чтобы их можно было (надеюсь) оптимизировать, вместо того, чтобы компилировать их в фактические косвенные вызовы памяти. На самом деле нет преимуществ в том, чтобы помещать их в массивы по сравнению с отдельно скомпилированным .asm файлом. Чистый недостаток, если вызов компилируется как косвенный вызов. - person Peter Cordes; 31.01.2019
comment
Кроме того, измените порядок первых двух аргументов на противоположный, чтобы большая половина уже была в RDX. (Вы можете написать встроенную функцию-оболочку, которая будет оптимизироваться, чтобы скрыть эту деталь, если вы хотите, чтобы источник имел hi,lo, den.) - person Peter Cordes; 31.01.2019
comment
Также не забудьте включить предупреждение о том, что это приведет к ОШИБКЕ с #DE (исключение разделения), если частное переполняет 64-битный регистр. - person Peter Cordes; 31.01.2019

arrow_upward
7
arrow_downward

Небольшое улучшение - на одну инструкцию меньше

extern "C" digit64 udiv128(digit64 low, digit64 hi, digit64 divisor, digit64 *remainder);

; Arguments
; RCX       Low Digit
; RDX       High Digit
; R8        Divisor
; R9        *Remainder

; RAX       Quotient upon return

.code
udiv128 proc
    mov rax, rcx    ; Put the low digit in place (hi is already there)
    div r8      ; 128 bit divide rdx-rax/r8 = rdx remainder, rax quotient
    mov [r9], rdx   ; Save the reminder
    ret     ; Return the quotient
udiv128 endp
end
person Dick Bertrand    schedule 09.07.2014

arrow_upward
4
arrow_downward

Это доступно сейчас. Вы можете использовать _div128 и _ 2_

Внутренняя функция _div128 делит 128-битное целое число на 64-битное целое число. Возвращаемое значение содержит частное, а внутренняя функция возвращает остаток через параметр указателя. _div128 специфичен для Microsoft.

В прошлом году было заявлено, что он доступен в Dev16, но я не уверен, какая это версия. Я предполагаю, что это VS 16.0 A.K.A VS2019, но документация на MSDN показывает, что он идет дальше VS2015

person phuclv    schedule 08.05.2019
comment
Согласно документации, он доступен в Visual Studio 2019 RTM. Я только что проверил, что он еще не доступен в Visual Studio 2017, соответственно. версия компилятора 19.16.27030.1. - person cxxl; 10.05.2019