Represent 128 bit integer as two 64 bit integers in C++

Question

I have a situation in my application where the application is using a 128 bit integer (specifically, a __uint128_t), and at some point the application needs to encode this 128 bit integer as two 64 bit integers (__uint64_t).

(Just assume for the sake of this question that it must encode them like that -- this question is not about alternative ways to encode it)

How can I do this? I must be able to encode and decode.

void encode(__uint128_t src, __uint64_t &dest1, __uint64_t &dest2)
{
    // ...
}

void decode(__uint64_t src1, __uint64_t src2, __uint128_t &dest)
{
    // ...
}

Example usage:

__uint128_t bigIntBefore = 999999999999999999;
__uint64_t smallInt1;
__uint64_t smallInt2;
encode(bigIntBefore, smallInt1, smallInt2);

// ... later

__uint128_t bigIntAfter;
decode(smallInt1, smallInt2, bigIntAfter);
// bigIntAfter should have a value of '999999999999999999'

An int128 is likely already a struct containing 2 int 64’s. — vandench, Oct 10 '18 at 22:43
Where is your 128 bit integer type coming from? A compiler extension, library, what? — Shawn, Oct 10 '18 at 22:43
@Shawn Not exactly sure, I thought `__uint128_t` and `__uint64_t` were somewhat standard. I'll try to find out. (I'm a C++ noob forgive me) — James Wierzba, Oct 10 '18 at 22:46
@JamesWierzba: They quite non-standard... the standard is [this](https://en.cppreference.com/w/cpp/header/cstdint). — einpoklum, Oct 10 '18 at 22:48
Ask yourself this: How would you encode/decode a 64-bit `unsigned int` from/to two 32-bit `unsigned int`s? How about a 32-bit `unsigned int` from/to two 16-bit `unsigned int`s? How about encoding/decoding any of these types from/to a sequence of 8-bit `unsigned int`s? — jamesdlin, Oct 10 '18 at 22:51
Any identifier with a `__` anywhere in it is a non-standard implementation detail ([or someone made a big mistake in their naming scheme](https://stackoverflow.com/questions/4421706/what-are-the-basic-rules-and-idioms-for-operator-overloading)). You need to use this stuff with a degree of caution because how it's implemented can change whenever the compiler implementors feel like it. Some implementation details will be documented and guaranteed to be stable by the implementors, but the rest exist in a grey area and shouldn't be used without grave need. — user4581301, Oct 10 '18 at 23:20

einpoklum · Accepted Answer · 2018-10-10T22:53:20.033

2

Umm, why not just do:

void encode(__uint128_t src, __uint64_t &dest1, __uint64_t &dest2)
{
    constexpr const __uint128_t bottom_mask = (__uint128_t{1} << 64) - 1;
    constexpr const __uint128_t top_mask = ~bottom_mask;
    dest1 = src & bottom_mask;
    dest2 = (src & top_mask) >> 64;
}

void decode(__uint64_t src1, __uint64_t src2, __uint128_t &dest)
{
    dest = (__uint128_t{src2} << 64) | src1;
}

?

Of course, this might be kind of futile, since __uint128_t may already be just 2 64-bit values. Also, prefer returning a value rather than using lvalue-references:

std::pair<__uint64_t,__uint64_t> encode(__uint128_t src)
{
    constexpr const __uint128_t bottom_mask = (__uint128_t{1} << 64) - 1;
    constexpr const __uint128_t top_mask = ~bottom_mask;
    return { src & bottom_mask, (src & top_mask) >> 64 };
}

__uint128_t decode(__uint64_t src1, __uint64_t src2)
{
    return (__uint128_t{src2} << 64) | src1;
}

edited Oct 10 '18 at 22:53

answered Oct 10 '18 at 22:47

einpoklum

118,144
57
340
684

Alternatively: `dest1 = src; dest2 = src / (__uint128_t{UINT64_MAX} + 1);` and `return src1 + src2 * (__uint128_t{UINT64_MAX} + 1);` respectively. – melpomene Oct 10 '18 at 22:59
Hey einpoklum, why do we need masks for encode step? Can't we just do `dest1 = src` and `dest2 = src >> 64;` instead of `dest1 = src & bottom_mask;` and `dest2 = (src & top_mask) >> 64;` – James Wierzba Oct 31 '18 at 18:37
@JamesWierzba: Yes, we could, I was just emphasizing what bits go where. – einpoklum Oct 31 '18 at 19:01
I see. Also, is this safe? The behavior of assigning a larger integer to a smaller integer is dependent on the compiler, no? We are assuming here that the assignment is taking the lower order 64 bits, is this __always__ the case? – James Wierzba Oct 31 '18 at 19:05
@JamesWierzba: The behavior of assigning a larger unsigned integer to a smaller unsigned integer _is_ well defined, to my knowledge; see [this answer](https://stackoverflow.com/a/27889221/1593077) here on the site. – einpoklum Oct 31 '18 at 19:07

Represent 128 bit integer as two 64 bit integers in C++

1 Answers1