C++ Logo

sg12

Advanced search

Re: [ub] Signed shifting

From: Jeffrey Yasskin <jyasskin_at_[hidden]>
Date: Mon, 17 Nov 2014 11:11:21 -0800
* The last thread on two's-complement representation managed to find
one modern Unisys system that uses one's-complement, and the thread
reported that this one supports Java, so it has to have a way to
execute two's-complement shifts. We shouldn't be building a standard
for imaginary systems.

* Even if 'int' needs to support non-two's-complement, the referenced
code (https://github.com/teor2345/tor/blob/ced74e0144e967f838416e6af92cba65c007d89b/src/ext/curve25519_donna/curve25519-donna.c#L56)
uses int64_t, which <C99 7.18.1.1 Exact-width integer types> says is
already two's complement. C++14 defers to C99 for this. We could
define shifts on two's complement types that would stay
implementation-defined on anything else.

* Programmers are used to writing "X << N" to mean "X * 2^N". Without
a good reason, we shouldn't make them use worse syntax for this, even
for signed numbers. "Applying [bit-shifts] to signed numbers is a bug"
is just incorrect given compilers' and hardware's actual behavior.
(Appealing to the fact that it's undefined behavior in the current
standard is just begging the question.)

* If we wanted to provide a library function to represent shifting,
I'm having trouble coming up with a good name for it. A free library
function operating on integers is terrible: times_two_to_the(X, N)? A
member function for the constant-time class that competes with "<< N"
is also hard to produce: X.times_two_to_the(N)? X.times_pow2(N)? The
main objection to the constant-time library in LEWG was that we
weren't sure anyone would use it. Insisting that folks switch from
operators to functions would increase that risk.

Jeffrey

On Sat, Nov 15, 2014 at 9:15 AM, Jens Maurer <Jens.Maurer_at_[hidden]> wrote:
>
> A preliminary observation: The C++ standard (in contrast to the C
> standard) does not explicitly prescribe one of two's complement,
> one's complement, sign-magnitude for signed integer representations,
> but certainly those three choices are allowed by C++.
>
> On 11/14/2014 11:45 PM, Jeffrey Yasskin wrote:
>> We could suggest that the programmers explicitly multiply by a power
>> of 2 instead, but they're using the <<s at least partly to get
>> constant-time operation, and relying on multiplication for this would
>> depend even more on implementation details than they already are.
>
> This seems to rely on two's complement representation for negative
> numbers, which is (from the standard's perspective) a non-portable
> assumption.
>
> In my opinion, users expecting constant-time operations would be
> better served with a (small) library that allows them to express their
> intent, instead of misusing shifts for multiplication. For example,
> the following would help (after adding a "multiplication-by-power-of-two"
> function):
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4145.html
>
>> Separately, a related piece of code uses a signed right-shift to
>> repeat the sign bit across all the bits of a number:
>> https://boringssl.googlesource.com/boringssl/+/e18d821dfcc32532caeeb1a2d15090672f592ce3/crypto/internal.h#157.
>> This is implementation-defined rather than undefined, so the
>> programmers can probably use #if to check for the behavior they
>> expect, as at
>> https://github.com/teor2345/tor/blob/ced74e0144e967f838416e6af92cba65c007d89b/src/ext/curve25519_donna/curve25519-donna.c#L466
>
> Well, that's still a bit disappointing, since you get an #error if your
> compiler doesn't provide the expected semantics.
>
> If we can identify a small set of basic operations that people want to
> use, we should give them a (small) library instead of asking them to do
> non-portable things.
>
>> Is there space to improve the situation here?
>
> Yes, but (in my opinion), it's not in the direction of changing the
> core language for these purposes.
>
> Bit-shifts are for unsigned numbers; applying them to signed numbers
> is a bug, in my opinion.
>
> Jens
> _______________________________________________
> ub mailing list
> ub_at_[hidden]
> http://www.open-std.org/mailman/listinfo/ub

Received on 2014-11-17 20:11:42