x86-64 machine code, x32 ABI, 64 58 55 54 53 49 48 46 44 bytes
xxd output:
00000000: 87fc 5859 5e5a 6629 d17d 0548 96f7 d9eb ..XY^Zf).}.H....
00000010: 01ca 6683 f940 7d0f 48d3 ee48 31f0 87d1 ..f..@}.H..H1...
00000020: 7805 48d1 e0e2 f951 5089 fcc3 x.H....QP...
In assembly, with comments:
xor_double:
xchg esp,edi # save stack pointer and points new stack at the input
# long doubles are 80-bit floating point numbers,
# with the low 8 bytes giving the significand and the high 2 bytes giving the exponent
# Conveniently, long doubles have an alignment of sixteen, so the "stack" now looks like:
# rsp --> significand of first argument
# rsp+8 --> exponent of first argument (plus six bytes of junk)
# rsp+10 --> significand of second argument
# rsp+18 --> exponent of second argument (plus six bytes of junk)
# So, just 4 pops puts all the arguments into registers:
pop rax # rax=sig1
pop rcx # rcx=junk48:exp1
pop rsi # rsi=sig2
pop rdx # rdx=junk48:exp2
# check which argument is greater and swap the two if the second is greater. Otherwise swap them
sub cx,dx # find difference of exponents
jge good # jmp if exp1 >= exp2
# exp1 < exp2, switch around the arguments
xchg rsi,rax
neg ecx
# note that dx is unchanged and is now the biggest exponent- this will also be true in the other branch
# This next two opcodes assemble together to EB 01 CA. If decoded from here, that is "JMP $+1 ; .byte CA", which skips the CA byte
# But the "jge good" earlier jumps to the middle of EB 01 and so it is instead decoded as "01 CA", or "add edx,ecx"
.byte 0xEB
good:
add edx,ecx
# dx=cx-dx+dx=original value of cx, the biggest exponent
switched:
cmp cx,0x40 #ratio >= 2**64, just return initial number
jge dontxor
shr rsi,cl #shift the smaller significand so they line up
xor rax,rsi
# the significand of a floating point number always has 1 as its MSB.
# so if it's missing, shift the bits around to restore it
# i.e. multiply significand by two and subtract one off the exponent until the MSB is 1
xchg ecx,edx
subnormal_loop: #multiply significand by two and subtract exponent by 1 until either exponent is zero or the number is normal
js dontxor #done
shl rax
loop subnormal_loop #decrements ecx and jmp if not zero
dontxor:
# return output in long_double[1]
# put exponent in place
push rcx
# put significand in place
push rax
# restore the stack pointer
mov esp,edi
ret
Takes a pointer to an array of 80-bit x87 long doubles and returns in the 2nd element of the array. Uses the x32 ABI (not to be confused with x86-32), which is just like the usual System V ABI, but all pointers are 32 bits.
The padding outside the actual 10-byte long doubles is allowed to be garbage, not zero, which means we have to be careful when comparing or using FLAGS results from operations on exponents: 16-bit operand-size is necessary because we loaded the whole qword including high garbage into the full register.
Because it uses the x32 calling convention, you can compile this and link it with a C program to test it, with the function prototype void xor_double(long double[2])
. You will need to compile it as x32, though.
The strategy is to shift the smaller number's significand to the right, by the difference in exponent. This aligns the significand to the place-value position of the significand of the larger, like they were fixed-point. (This may mean shifting out all the bits if the exponents are different by 64 or more, but x86 scalar shifts mask the count by &63 or &31 so we need to special-case that).
Then xor the aligned significands and use this as the 64-bit significand with the larger exponent.
80-bit long double has an explicit leading 1 in the 64-bit significand, unlike 64-bit double (IEEE binary64) using an implicit 1 (implied by a non-zero exponent field). That means shift/xor Just Works on the significand field directly.
But we still need to renormalize when equal exponents cause the leading 1 bits cancel between significands. Other than subnormals (where the exponent field is zero), long double
values with bit 63 clear are not valid. (8087 and 80287 allow them as "unnormal" according to Wikipedia, but hardware operations on such a value on 387 and later treat them as invalid, producing NaN. All x86-64 CPUs include 387-compatible FPUs, and we need 64-bit mode to make it convenient to deal with a 64-bit significand.)
The renormalization uses a loop
command, which decrements the exponent and jumps back to the start of the loop. This is necessary because if the significand is zero, the exponent must also be cleared or the result is an invalid floating point number. This actually clears rcx
in that case, not just cx
, which potentially makes the program take (much) longer, but is harmless otherwise.
The renormalization loop also handles the case of two equal inputs, where xoring aligned significands leaves zero. We shift left (and decrement the exponent) until a 1 bit appears at the top of the significand (normal case), or the exponent field becomes zero. (Producing a subnormal or a zero).
This handles the equal-input case because left-shifting an all-zero significand will never shift a 1 to the top, so eventually the exponent becomes zero. If there is a 1 bit somewhere but the exponent becomes zero before it gets to the top, in that case it is a valid subnormal value. (Too small to be representable as a normalized float.) The question doesn't require us to support subnormal inputs or outputs so the actual correct value isn't required in this case, although it probably is correct. This ended up being shorter than lzcnt
/ shl
plus branching for special cases.
At the end, it returns a long double*
, which "conveniently" points to [rsp]
right after the function call. Returning a pointer into the calling function's stack frame is perhaps somewhat malicious compliance with the calling conventions, but it works!
Some general notes on registers:
- I avoid
rbx
, rbp
, and rsp
as registers because the System V ABI forbids changing them without saving their previous value, which costs some bytes.
- I avoid
r8-r15
because they cost an extra byte for most uses.
- In most cases using a 32-bit register saves some bytes, so I only use
cx
and dx
when the junk in the higher bits of the registers would get in the way.
- Using
rax
instead of any other register for one of the significands saves a byte on xchg
, since xchg rax,[anything]
is two bytes instead of three.
ecx
has many special uses. It is the only register allowed for shr [reg],cl
, and rcx
is the only one used by loop
. That is why the xchg ecx,edx
is required to put the exponent in this special register.
Try it online! Note that TIO doesn't appear to support the x32 ABI, so I simulated it by using mmap
to create a new stack at a 32 bit address.