Agreed, and that is the easier part :-)

I'm trying to find a middle-ground for people to get certainty (the implementation will tell you programmatically what the encoding is), while removing or reducing the surface area of undefined behavior. My suspicion is that we will end up with 2's complement for most cases. But that is not based on a scientific study.

-- Gaby

From: ub-bounces_at_[hidden] [mailto:ub-bounces_at_[hidden]] On Behalf Of Jeffrey Yasskin
Sent: Monday, November 17, 2014 12:32 PM
To: WG21 UB study group
Subject: Re: [ub] Signed shifting

We'd still need to define the behavior of signed shifting when encoding<T>==binary_system::twos_complement, for it to help this use case.

On Mon, Nov 17, 2014 at 11:59 AM, Gabriel Dos Reis <gdr_at_[hidden]<mailto:gdr_at_[hidden]>> wrote:
Or require implementations to tell you programmatically what they are using as binary representation:

    enum class binary_system {
          other,
          sign_magnitude,
          ones_complement,
          twos_complement
    };

    template<BuiltinIntegralType T>
          constexpr binary_system encoding = /* implementation defined */

-- Gaby

| -----Original Message-----
| From: ub-bounces_at_[hidden]<mailto:ub-bounces_at_[hidden]> [mailto:ub-bounces_at_[hidden]<mailto:ub-bounces_at_[hidden]>] On
| Behalf Of Jeffrey Yasskin
| Sent: Monday, November 17, 2014 11:11 AM
| To: WG21 UB study group
| Subject: Re: [ub] Signed shifting
|
| * 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/ced74e0144e967f838416e6af92cba6
| 5c007d89b/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]<mailto: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/+/e18d821dfcc32532caeeb1a2
| d15090672f592ce3/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/ced74e0144e967f838416e6af92cba65
| c007d89b/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]<mailto:ub_at_[hidden]>
| > http://www.open-std.org/mailman/listinfo/ub
| _______________________________________________
| ub mailing list
| ub_at_[hidden]<mailto:ub_at_[hidden]>
| http://www.open-std.org/mailman/listinfo/ub
_______________________________________________
ub mailing list
ub_at_[hidden]<mailto:ub_at_[hidden]>
http://www.open-std.org/mailman/listinfo/ub