c++ crt и asm как делятся многобайтные числа

тип long long в С\С++ хранится в 2х регистрах и при вычислении деления компилятор вызывает ту программу в сполере. А каким методом эта программа эти числа делит? Раскажите пожалуйста или дайте ссылку.

Спойлер: asm

.xlist
include cruntime.inc
include mm.inc
.list
;***
;lldiv - signed long divide
;
;Purpose:
; Does a signed long divide of the arguments. Arguments are
; not changed.
;
;Entry:
; Arguments are passed on the stack:
; 1st pushed: divisor (QWORD)
; 2nd pushed: dividend (QWORD)
;
;Exit:
; EDX:EAX contains the quotient (dividend/divisor)
; NOTE: this routine removes the parameters from the stack.
;
;Uses:
; ECX
;
;Exceptions:
;
;*******************************************************************************
CODESEG
_alldiv PROC NEAR
.FPO (3, 4, 0, 0, 0, 0)
push edi
006316B0 push edi
push esi
006316B1 push esi
push ebx
006316B2 push ebx
; Set up the local stack and save the index registers. When this is done
; the stack frame will look as follows (assuming that the expression a/b will
; generate a call to lldiv(a, b)):
;
; -----------------
; | |
; |---------------|
; | |
; |--divisor (b)--|
; | |
; |---------------|
; | |
; |--dividend (a)-|
; | |
; |---------------|
; | return addr** |
; |---------------|
; | EDI |
; |---------------|
; | ESI |
; |---------------|
; ESP---->| EBX |
; -----------------
;
DVND equ [esp + 16] ; stack address of dividend (a)
DVSR equ [esp + 24] ; stack address of divisor (b)
; Determine sign of the result (edi = 0 if result is positive, non-zero
; otherwise) and make operands positive.
xor edi,edi ; result sign assumed positive
006316B3 xor edi,edi
mov eax,HIWORD(DVND) ; hi word of a
006316B5 mov eax,dword ptr [esp+14h]
or eax,eax ; test to see if signed
006316B9 or eax,eax
jge short L1 ; skip rest if a is already positive
006316BB jge L1 (6316D1h)
inc edi ; complement result sign flag
006316BD inc edi
mov edx,LOWORD(DVND) ; lo word of a
006316BE mov edx,dword ptr [esp+10h]
neg eax ; make a positive
006316C2 neg eax
neg edx
006316C4 neg edx
sbb eax,0
006316C6 sbb eax,0
mov HIWORD(DVND),eax ; save positive value
006316C9 mov dword ptr [esp+14h],eax
mov LOWORD(DVND),edx
006316CD mov dword ptr [esp+10h],edx
L1:
mov eax,HIWORD(DVSR) ; hi word of b
006316D1 mov eax,dword ptr [esp+1Ch]
or eax,eax ; test to see if signed
006316D5 or eax,eax
jge short L2 ; skip rest if b is already positive
006316D7 jge L2 (6316EDh)
inc edi ; complement the result sign flag
006316D9 inc edi
mov edx,LOWORD(DVSR) ; lo word of a
006316DA mov edx,dword ptr [esp+18h]
neg eax ; make b positive
006316DE neg eax
neg edx
006316E0 neg edx
sbb eax,0
006316E2 sbb eax,0
mov HIWORD(DVSR),eax ; save positive value
006316E5 mov dword ptr [esp+1Ch],eax
mov LOWORD(DVSR),edx
006316E9 mov dword ptr [esp+18h],edx
L2:
;
; Now do the divide. First look to see if the divisor is less than 4194304K.
; If so, then we can use a simple algorithm with word divides, otherwise
; things get a little more complex.
;
; NOTE - eax currently contains the high order word of DVSR
;
or eax,eax ; check to see if divisor < 4194304K
006316ED or eax,eax
jnz short L3 ; nope, gotta do this the hard way
006316EF jne L3 (631709h)
mov ecx,LOWORD(DVSR) ; load divisor
006316F1 mov ecx,dword ptr [esp+18h]
mov eax,HIWORD(DVND) ; load high word of dividend
006316F5 mov eax,dword ptr [esp+14h]
xor edx,edx
006316F9 xor edx,edx
div ecx ; eax <- high order bits of quotient
006316FB div eax,ecx
mov ebx,eax ; save high bits of quotient
006316FD mov ebx,eax
mov eax,LOWORD(DVND) ; edx:eax <- remainder:lo word of dividend
006316FF mov eax,dword ptr [esp+10h]
div ecx ; eax <- low order bits of quotient
00631703 div eax,ecx
mov edx,ebx ; edx:eax <- quotient
00631705 mov edx,ebx
jmp short L4 ; set sign, restore stack and return
00631707 jmp L4 (63174Ah)
;
; Here we do it the hard way. Remember, eax contains the high word of DVSR
;
L3:
mov ebx,eax ; ebx:ecx <- divisor
00631709 mov ebx,eax
mov ecx,LOWORD(DVSR)
0063170B mov ecx,dword ptr [esp+18h]
mov edx,HIWORD(DVND) ; edx:eax <- dividend
0063170F mov edx,dword ptr [esp+14h]
mov eax,LOWORD(DVND)
00631713 mov eax,dword ptr [esp+10h]
L5:
shr ebx,1 ; shift divisor right one bit
00631717 shr ebx,1
rcr ecx,1
00631719 rcr ecx,1
shr edx,1 ; shift dividend right one bit
0063171B shr edx,1
rcr eax,1
0063171D rcr eax,1
or ebx,ebx
0063171F or ebx,ebx
jnz short L5 ; loop until divisor < 4194304K
00631721 jne L5 (631717h)
div ecx ; now divide, ignore remainder
00631723 div eax,ecx
mov esi,eax ; save quotient
00631725 mov esi,eax
;
; We may be off by one, so to check, we will multiply the quotient
; by the divisor and check the result against the orignal dividend
; Note that we must also check for overflow, which can occur if the
; dividend is close to 2**64 and the quotient is off by 1.
;
mul dword ptr HIWORD(DVSR) ; QUOT * HIWORD(DVSR)
00631727 mul eax,dword ptr [esp+1Ch]
mov ecx,eax
0063172B mov ecx,eax
mov eax,LOWORD(DVSR)
0063172D mov eax,dword ptr [esp+18h]
mul esi ; QUOT * LOWORD(DVSR)
00631731 mul eax,esi
add edx,ecx ; EDX:EAX = QUOT * DVSR
00631733 add edx,ecx
jc short L6 ; carry means Quotient is off by 1
00631735 jb L6 (631745h)
;
; do long compare here between original dividend and the result of the
; multiply in edx:eax. If original is larger or equal, we are ok, otherwise
; subtract one (1) from the quotient.
;
cmp edx,HIWORD(DVND) ; compare hi words of result and original
00631737 cmp edx,dword ptr [esp+14h]
ja short L6 ; if result > original, do subtract
0063173B ja L6 (631745h)
jb short L7 ; if result < original, we are ok
0063173D jb L7 (631746h)
cmp eax,LOWORD(DVND) ; hi words are equal, compare lo words
0063173F cmp eax,dword ptr [esp+10h]
jbe short L7 ; if less or equal we are ok, else subtract
00631743 jbe L7 (631746h)
L6:
dec esi ; subtract 1 from quotient
00631745 dec esi
L7:
xor edx,edx ; edx:eax <- quotient
00631746 xor edx,edx
mov eax,esi
00631748 mov eax,esi
;
; Just the cleanup left to do. edx:eax contains the quotient. Set the sign
; according to the save value, cleanup the stack, and return.
;
L4:
dec edi ; check to see if result is negative
0063174A dec edi
jnz short L8 ; if EDI == 0, result should be negative
0063174B jne L8 (631754h)
neg edx ; otherwise, negate the result
0063174D neg edx
neg eax
0063174F neg eax
sbb edx,0
00631751 sbb edx,0
;
; Restore the saved registers and return.
;
L8:
pop ebx
00631754 pop ebx
pop esi
00631755 pop esi
pop edi
00631756 pop edi
ret 16
00631757 ret 10h

 

Есть такой чел - Агнер Фог, так вон он уже полжизни собирает всякие трюки компиляторов аля как у вас выше
их там сотни -тыши уже

https://www.agner.org/optimize/

 

https://mathsanew.com/articles/implementing_large_integers_division.pdf
Дисциплина называется "длинная арифметика" (long math), этакая тайна древней Атлантиды, которую уже давно никто не помнит как реализовать.

Также можно вспомнить nn.c, которая оперирует с дайджестами, по сути целыми числами любой невероятной длины. Интересующая тебя процедура - NN_Div.

 

на русском всётаки лучше

--- Сообщение объединено, 7 дек 2024 ---

а есть обьяснение на русском для двух регистров - там както по другому?

 

Эх жалко такого пояснения для "Деление (N+M)-разрядного беззнакового целого на число размером M байтов (стр. 32)" не хватает

 

пальцем в небо, но выложу