Алгоритм перевода чисел до 9999 в строку

[Avizpr]

В глубинах сети обнаружил этот алгоритм:
В начале eax содержит переводимое в строку положительное число. edx содержит довольно странное округление (2^32)/1000!
2^32 = 4294967296 т.е. если округлять правильно, то будет 4294967, а с этим числом уже не работает.
Хотелось бы спросить, у уважаемых людей, как расширить его (алгоритм) на числа больше чем 10 000?

PHP код:


        mov   eax, 207
    mov     edx,4294968          ;2^32/1000
        mov     ebx,10               ;per digit
        mul     edx                  ;extend first digit
        mov     ecx,edx              ;digit 1 in CL
        mul     ebx                  ;second digit
        mov     ch,dl                ;digit 2 in CH
        mul     ebx                  ;third digit
        bswap   ecx                  ;digits 1 & 2 up high
        mov     ch,dl                ;digit 3 in CH
        mul     ebx                  ;digit 4 in DL
        lea     ecx,[edx+ecx+'0000'] ;combine and make ASCII
        bswap   ecx                  ;re-order bytes
        cmp     cl,30h
        jnz     B2As42

        cmp     ch,30h
        jnz     B2As41

        test    ecx,0F0000h
        jnz     B2As40

        and     ecx,03F202020h
        JMP        endd

B2As40: mov     cx,2020h
        JMP        endd

B2As41: mov     cl,20h

B2As42: JMP        endd

endd: 


[f.hump]

когда-то для MASM написал такое:

.CONST
ALIGNN 16
strint_mask	DWORD	0F0F0F0Fh, 0F0F0F0Fh, 0F0F0F0Fh, 0F0F0F0Fh
strint_offs	DWORD	30303030h, 30303030h, 30303030h, 30303030h
strint_shuf        DWORD	0D0C0F0Eh, 09080B0Ah, 05040706h, 01000302h
__________________________
.CODE

ALIGN 16
?Int64ToCStr_SSSE3@@YAHPEAD_JH@Z PROC
	MOV r11, rsi
	MOV r10, rdi

	MOV [rcx], rdx
	FILD QWORD PTR [rcx]
	FBSTP TBYTE PTR [rcx]

	MOV rsi, rcx
	MOV rdi, rcx

	MOVDQA xmm4, XMMWORD PTR [strint_mask]
	MOVDQA xmm5, XMMWORD PTR [strint_offs]

	MOVDQU xmm2, [rcx]
	MOVDQU xmm3, [rcx]

	PSRLD xmm3, 4
	PAND xmm2, xmm4
	PAND xmm3, xmm4
	POR xmm2, xmm5
	POR xmm3, xmm5

	MOVDQA xmm5, xmm3

	PUNPCKLBW xmm3, xmm2
	PUNPCKHBW xmm5, xmm2

	PSHUFB xmm3, XMMWORD PTR[strint_shuf]

	MOVDQU [rcx+3], xmm3
	
	MOVD edx, xmm5
	MOV [rcx+1], dx

	MOV BYTE PTR [rcx], 5Fh

	BTS edx, 19
	JNC nosign
		MOV BYTE PTR [rcx], 2Dh		
		ADD rsi, 1		
	nosign:

	MOV BYTE PTR [rcx+19], 0
	MOV eax, 19

	CMP r8d, 0
	JNE donomo
		MOV rdx, rsi
		SUB rdx, rdi

		MOV al, 30h
		ADD rdi, 1
		MOV rcx, 18

		REPE SCASB

		SUB rdi, 1

		MOV rax, rsi
		MOV rsi, rdi
		MOV rdi, rax

		MOV eax, edx
		ADD eax, ecx
		ADD ecx, 2
		ADD eax, 1

		REP MOVSB
	donomo:

	MOV rsi, r11
	MOV rdi, r10
	
	RET
?Int64ToCStr_SSSE3@@YAHPEAD_JH@Z ENDP

объявлено так

extern int Int64ToCStr_SSSE3(char * dest, __int64 val, int padding_on);
// amps below 1000000000000000000 (10^18) are accepted
//padding_on is not zero - zeros are appended to the result string until 18-charecter string is formed

работать будет только в x64, и на большинстве AMD CPU работать не будет вообще

[Avizpr]

Красота алгоритма, который я привел в том, что там нет деления))
И есть магия чисел

[Avizpr]

Наверняка есть какая нибудь математика, под это все, т.к. вот алгоритм перевода чисел в ASCII строки до 100 миллионов! (этот я не проверял)
Как же они находят критерии для округления множителей 2^32 и 2^45 ???!!!

PHP код:

        mov     ebx,eax              ;original in ebx
        mov     edx,3518437209       ;2^45/10000
        mul     edx                  ;extend quotient
        shr     edx,13               ;quotient
        imul    eax,edx,10000        ;reconstruct for remainder
        neg     eax
        push    edx
        add     eax,ebx              ;remainder=orig-10000*quot
        mov     edx,4294968          ;2^32/1000
        mov     ebx,10               ;per digit
        mul     edx                  ;extend first digit
        mov     ecx,edx              ;digit 1 in CL
        mul     ebx                  ;second digit
        mov     ch,dl                ;digit 2 in CH
        mul     ebx                  ;third digit
        bswap   ecx                  ;digits 1 & 2 up high
        mov     ch,dl                ;digit 3 in CH
        mul     ebx                  ;digit 4 in DL
        lea     ecx,[edx+ecx+'0000'] ;combine and make ASCII
        bswap   ecx                  ;re-order bytes
        pop     eax
        mov     [edi+4],ecx
        mov     edx,4294968          ;2^32/1000
        mov     ebx,10               ;per digit
        mul     edx                  ;extend first digit
        mov     ecx,edx              ;digit 1 in CL
        mul     ebx                  ;second digit
        mov     ch,dl                ;digit 2 in CH
        mul     ebx                  ;third digit
        bswap   ecx                  ;digits 1 & 2 up high
        mov     ch,dl                ;digit 3 in CH
        mul     ebx                  ;digit 4 in DL
        lea     ecx,[edx+ecx+'0000'] ;combine and make ASCII
        bswap   ecx                  ;re-order bytes
        mov     [edi],ecx 


[f.hump]

если честно, то я вообще не понимаю зачем над числом меньшим 10^18 проводить какие-либо арифметические операции для того чтобы сконвертировать его в строку если есть такая шикарная инструкция как FBSTP

[f.hump]

в целом, если говорить про алгоритм, то если поискать, окажется, что основан на следующей идее

цифра[i] = int(10*frac(число*0.1^i)) // i>0

ну, и чтобы работать не с плавающей точкой, а с целыми, вместо факторов 0.1^i используются факторы

фактор[i] = int(ceil((2^32 * 0.1^i) * 2^сдвиг[i]))
сдвиг[i] = int(log2(10^i))

итог:

цифра[i] = (10*(((число * фактор[i]) >> сдвиг[i]) & 0xFFFFFFFF)) >> 32;

[Mikl___]

Avizpr
в той же "глубине, где ты нарыл" этот алгоритм есть топик magic numbers -- почитай его внимательно
А это "теоретическая часть"
Деление на константу можно сделать на обратное число. Чтобы произвести беззнаковое целочисленное деление q = x / d, вам вначале нужно посчитать число, обратное делителю, f = 2r / d, где r определяет позицию двоично-десятичной точки (точка основания системы счисления). Затем нужно умножить x на f и сдвинуть полученный результат на r позиций вправо. Максимальное значение r равно 32+b, где b равно числу двоичных цифр в d минус 1. (b - это самое большое целое число, для которого 2b <= d). Используйте r = 32+b, чтобы покрыть максимальное количество возможных значений делимого x.
Этот метод требует некоторых приемов, чтобы скомпенсировать ошибки округления. Следующий алгоритм даст вам верные результаты для деления беззнакового целого числа с усечением, то есть тот же результат, что дает инструкция DIV (спасибо Terje Mathisen, который изобрел этот метод):
b = (количество значимых битов в d) - 1
r = 32 + b
f = 2r / d
Если f - целое число, тогда d - это степень от 2: переходим к случаю A.
Если f - не целое число, тогда проверяем, меньше ли дробная часть f 0.5.
Если дробная часть f < 0.5: переходим к случаю B.
Если дробная часть f > 0.5: переходим к случаю C.
случай A: (d = 2b)
результат = x SHR b

случай B: (дробная часть f < 0.5)
округляем f вниз до ближайшего целого числа
результат = ((x+1) * f) SHR r

случай C: (дробная часть f > 0.5)
округляем f вверх до ближайшего целого числа
результат = (x * f) SHR r
Пример:
Предположите, что вы хотите разделить на 5.
5 = 00000101b.
b = (количество значимых двоичных чисел) - 1 = 2
r = 32+2 = 34
f = 234 / 5 = 3435973836.8 = 0CCCCCCCC.CCC...(hexadecimal)
Дробная часть больше, чем половина: используем случай C. Округляем f вверх до 0CCCCCCCDh.

Следующий код делит EAX на 5 и возвращает результат в EDX:

        MOV     EDX,0CCCCCCCDh
        MUL     EDX
        SHR     EDX,2

После умножения EDX содержит значение, сдвинутое вправо на 32. Так как r = 34, вам нужно сдвинуть еще на 2, чтобы получить окончательный результат. Чтобы поделить на 10, вам нужно всего лишь заменить последнюю строку на 'SHR EDX,3'.
В случае B у вас будет следующее:

        INC     EAX
        MOV     EDX,f
        MUL     EDX
        SHR     EDX,b

Этот код работает для всех значений x, кроме 0FFFFFFFFH, которое дает ноль из-за переполнения в инструкции INC. Если возможно, что x = 0FFFFFFFFH, тогда замените этот код на:

        MOV     EDX,f
        ADD     EAX,1
        JC      DOVERFL
        MUL     EDX
DOVERFL:SHR     EDX,b

Если значение x ограничено, тогда вам следует использовать меньшее значение r, то есть меньшее количество цифр. Может быть несколько причин для того, чтобы сделать это:

• вы можете установить r = 32 и избежать 'SHR EDX,b' в конце.
• 
  вы можете установить r = 16+b и использовать инструкции умножения, которые дают 32-х битный результат, вместо 64-х битного. Тогда можно освободить регистр EDX: IMUL EAX,0CCCDh / SHR EAX,18
• вы можете выбрать значение r, которое будет чаще приводить к случаю C, а не B, чтобы избежать инструкции 'INC EAX'.

Максимальное значение x в этих случаях равно по крайней мере 2r-b, иногда выше. Вы должны делать систематические тесты, если хотите узнать точное максимально значение x, при котором ваш код будет работать корректно.
Вы можете заменить медленную инструкцию умножения более быстрыми инструкциями, как это объяснено в главе 26.5.
Следующий пример делит EAX на 10 и возвращает результат в EAX. Я выбрал r=17, а не 19, потому что это дает код, который легче оптимизировать, и он покрывает такое же количество значений x. f = 217 / 10 = 3333h, случай B: q = (x+1)*3333h:

        LEA     EBX,[EAX+2*EAX+3]
        LEA     ECX,[EAX+2*EAX+3]
        SHL     EBX,4

        MOV     EAX,ECX
        SHL     ECX,8
        ADD     EAX,EBX
        SHL     EBX,8
        ADD     EAX,ECX
        ADD     EAX,EBX
        SHR     EAX,17

Проведенные тесты показывают, что этот код работает правильно для всех значений x < 10004h.

[Avizpr]

Mikl___ благодарю!
У меня не хватило соображалки поискать там про magic numbers...