0

I'm trying to find or figure out the algorithm for converting a signed 64-bit int (twos-complement, natch) to closest value IEEE double (64-bit), staying within bitwise operations.What I'm looking for is for the generic "C-like" pseudocode; I'm implementing a toy JVM on a platform that is not C and doesn't have a native int64 types, so I'm operating on 8 byte arrays (details of that are mercifully outside this scope) and that's the domain the data needs to stay in.

So: input is a big-endian string of 64 bits, signed twos-complement. Output is a big-endian string of 64 bits in IEEE double format that represents as near the original int64 value as possible. In between is some set of masks, shifts, etc! Algorithm absolutely does not need to be especially clever or optimized. I just want to be able to get to the result and ideally understand what the process is.

Having trouble tracking this down because I suspect it's an unusual need. This answer addresses a parallel question (I think) in x86 SSE, but I don't speak SSE and my attempts and translation leave me more confused than enlightened.

Would love someone to either point in the right direction for a recipe or ideally explain the bitwise math behind so I actually understand it. Thanks!

Ben Zotto
  • 70,108
  • 23
  • 141
  • 204
  • Do you have a specific question about the conversion? Getting the mantissa is trivial and the exponent you can get by going a "highest set bit" log approximation, right? – Carl Norum Nov 23 '20 at 03:19
  • @CarlNorum: Unfortunately you've already somewhat lost me. I understand what the bitwise components of a double represent theoretically but I'm pretty fuzzy on how I'd stuff those bits to reflect the most accurate representation of the int64. (Save the sign bit which is obvious.) When you say the mantissa is trivial.. can you give me another hint? :) I'm also not familiar with highest set bit log approximation, but I'll go off looking for that. tHanks – Ben Zotto Nov 23 '20 at 03:26
  • Well the significand will have the same (binary) digits as your existing 64-bit int. It's *already* a power-of-two number. – Carl Norum Nov 23 '20 at 03:30
  • 1
    OK I wrote a basic (probably bad) implementation. Let me tidy it up and I'll write an answer. – Carl Norum Nov 23 '20 at 03:41

1 Answers1

1

Here's a simple (and wrong in several ways) implementation, including a test harness.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double do_convert(int64_t input)
{
    uint64_t sign = (input < 0);
    uint64_t magnitude;

    // breaks on INT64_MIN
    if (sign)
        magnitude = -input;
    else
        magnitude = input;    

    // use your favourite algorithm here instead of the builtin
    int leading_zeros = __builtin_clzl(magnitude);
    uint64_t exponent = (63 - leading_zeros) + 1023;
    uint64_t significand = (magnitude << (leading_zeros + 1)) >> 12;

    uint64_t fake_double = sign << 63
                         | exponent << 52
                         | significand;

    double d;
    memcpy(&d, &fake_double, sizeof d);

    return d;
}

int main(int argc, char** argv)
{
    for (int i = 1; i < argc; i++)
    {
        long l = strtol(argv[i], NULL, 0);
        double d = do_convert(l);
        printf("%ld %f\n", l, d);
    }

    return 0;
}

The breakages here are many - the basic idea is to first extract the sign bit, then treat the number as positive the rest of the way, which won't work if the input is INT64_MIN. It also doesn't handle input 0 correctly because it doesn't correctly deal with the exponent in that case. These extensions are left as an exercise for the reader. ;-)

Anyway - the algorithm just figures out the exponent by calculating log2 of the input number and offsetting by 1023 (because floating point) and then getting the significand by shifting the number up far enough to drop off the most significant bit, then shifting back down into the right field position.

After all that, the assembly of the final double is pretty straightforward.

Edit:

Speaking of exercises for the reader - I also implemented this program using _builtin_clzl(). You can expand that part as necessary.

Carl Norum
  • 219,201
  • 40
  • 422
  • 469