How to do a double-chunk add with no undefined behaviour?
EDIT Public health warning - this question includes a false assumption about undefined behaviour. See accepted answer.
After a reading recent blog post, I've been thinking a lot about the practicality of avoiding all standards-undefined assumptions in C and C++ code. Here is a snippet cut out of C++, to do an unsigned 128-bit addition...
void c_UInt64_Pair::operator+= (const c_UInt64_Pair &p)
{
m_Low += p.m_Low;
m_High += p.m_High;
if (m_Low < p.m_Low) m_High++;
}
This clearly relies on assumptions about overflow behaviour. Obviously most machines can support a binary integer of the right kind (though perhaps building from 32-bit chunks or whatever), but there's apparently a growing chance that the optimiser may exploit the standards-undefined behaviour here. That is, the only way that the m_Low condition can pass is if m_Low += p.m_Low overflows, which is undefined behaviour, so the optimiser can legally decide that the condition always fails. In which case, this code is simply broken.
The question is, therefore...
How can you write a reasonably efficient version of the above without relying on undefined behaviour?
Assume that you have an appropriate 64-bit binary machine integer, but that you have a malicious compiler that will always interpret your undefined behaviour in the worst possible (or impossible) way. Also, assume that you don't have some special built-in, intrinsic, library or whatever to do it for you.
EDIT minor clarification - this isn't just about detecting overflow, but also ensuring that both m_Low and m_High end up with the correct modulo 2^64 results, which is also standards-undefined.
2 ответа
Из стандарта C++ 1998 г., 3.9.1(4): «Целые числа без знака, объявленные беззнаковыми, должны подчиняться законам арифметики по модулю 2^n, где n — количество битов в значении представление этого конкретного размера целого числа». Обратите внимание, что «целое число» здесь относится к любому целочисленному типу, а не только к int.
Следовательно, предполагая, что это целые числа без знака, как предполагает "UInt64" в типе, это определенное поведение в C++, и оно должно работать должным образом.
Если вам нужен действительно эффективный метод, вам придется писать код на чем-то другом, кроме C или C++. Для достаточно эффективности вы должны гарантировать, что переполнение никогда не произойдет, а также обнаружить и компенсировать, когда оно могло бы произойти.
В принципе, для каждого 64-битного компонента вам необходимо отдельно вычислить сложения, используя младшие 63 бита и старшие биты. Из этих отдельных вычислений вы можете определить, сколько было 64-битных файлов и был ли перенос.
Затем, когда вы добавляете старшие 64-бита, вы добавляете перенос, если он есть. Если в результате этого возникает перенос, то вы переполнили свою 128-битную переменную, и вам нужно вызвать исключение или иным образом обработать случай.