X86-64 Great integer representation?

Question

How do high-performance native x86-64 large integer libraries represent a large integer in memory? (or is it different? Is there the most common way?)

Naively, I thought about storing them as strings with trailing numbers 0 in base 2 ⁶⁴ .

For example, suppose X is in memory as:

 [8 bytes] Dn . . [8 bytes] D2 [8 bytes] D1 [8 bytes] D0 [8 bytes] 0 

Let B = 2 ⁶⁴

Then

X = D _n * B ⁿ + ... + D ₂ * B ² + D ₁ * B ¹ + D ₀

An empty string (i.e. 8 bytes of zero) means zero.

Is this a smart way? What are the pros and cons of this path? Is there a better way?

How would you handle a signature? Does 2 padding work with this variable length value?

(Found this: http://gmplib.org/manual/Integer-Internals.html What is a limb?)

Answer 1

I would think that this would be the smallest value of the array. I implemented adding custom sizes to assembler. The CPU provides a flag that allows you to easily perform these kinds of operations. You write a loop that performs an operation in byte-sized blocks. The carry flag is included in the next operation using the Add With Transfer command (ADC opcode).

Answer 2

Here I have some examples of handling large integers.

Adding

The principle is pretty simple. You need to use CF (carry flag) for any larger overflow. Let's think about adding two 128-bit numbers.

 num1_lo: dq 1<<63 num1_hi: dq 1<<63 num2_lo: dq 1<<63 num2_hi: dq 1<<62 ;Result of addition should be 0xC0000000 0x000000001 0x00000000 0x00000000 mov eax, dword [num1_lo] mov ebx, dword [num1_lo+4] mov ecx, dword [num1_hi] mov edx, dword [num1_hi+4] add eax, dword [num2_lo] adc ebx, dword [num2_lo+4] adc ecx, dword [num2_hi] adc edx, dword [num2_hi+4] jc .overflow 

Subtraction

Very similar to a supplement, although you now call CF loan.

 mov eax, dword [num1_lo] mov ebx, dword [num1_lo+4] mov ecx, dword [num1_hi] mov edx, dword [num1_hi+4] sub eax, dword [num2_lo] sbb ebx, dword [num2_lo+4] sbb ecx, dword [num2_hi] sbb edx, dword [num2_hi+4] jb .overflow ;or jc 

Multiplication

This is much more complicated. You need to multiply each part of the fisrt number by each part of the second number and add the results. You do not need to multiply only the two higher parts, which are undoubtedly overflowing. Pseudocode:

 long long int /*128-bit*/ result = 0; long long int n1 = ; long long int n2 = ; #define PART_WIDTH 32 //to be able to manipulate with numbers in 32-bit registers int i_1 = 0; /*iteration index*/ for(each n-bit wide part of first number : n1_part) { int i_2 = 0; for(each n-bit wide part of second number : n2_part) { result += (n1_part << (i_1*PART_WIDTH))*(n2_part << (i_2*PART_WIDTH)); i_2++; } i++; } 

Department

even harder. A user at Brendan forum OsDev.org posted a pseudo-code example for dividing n-bit integers. I insert it here because the principle is the same.

 result = 0; count = 0; remainder = numerator; while(highest_bit_of_divisor_not_set) { divisor = divisor << 1; count++; } while(remainder != 0) { if(remainder >= divisor) { remainder = remainder - divisor; result = result | (1 << count); } if(count == 0) { break; } divisor = divisor >> 1; count--; }