Check assumptions on integer implementation at compile time #798

sipa commented at 12:45 AM on August 13, 2020: contributor

A compile-time check is implemented in a new src/assumptions.h which verifies several aspects that are implementation-defined in C:

size of bytes
conversion between unsigned and (negative) signed types
right-shifts of negative signed types.

sipa commented at 12:56 AM on August 13, 2020: contributor

It seems fairly easy to turn this into a compile time check, by using (that_expression - 1) as the size of array.

However, maybe we want to include endianness into the check, and I'm not sure that can be done at compile time.

sipa cross-referenced this on Aug 13, 2020 from issue WIP: "safegcd" field and scalar inversion by peterdettman

gmaxwell commented at 1:51 AM on August 13, 2020: contributor

as the size of array.

Var arrays are C99 and "optional" in later standards and not supported by MSVC.

sipa commented at 1:53 AM on August 13, 2020: contributor

@gmaxwell Yes, but this isn't relying on vararrays - the expression is a compile-time constant.

In fact, it has to be constant. A vararray of negative size could compile. So you have to do something like define a struct with a member array (where a vararray isn't allowed).

sipa commented at 2:08 AM on August 13, 2020: contributor

@gmaxwell this seems to work in gcc/clang/icc/msvc: https://godbolt.org/z/6dsar5

gmaxwell commented at 5:29 AM on August 13, 2020: contributor

Yeah, I tested it with GCC 2.95 on i386 and tinyc and it seems to be happy there too. One downside is that when it fails you get an extremely opaque error.

sipa force-pushed on Aug 13, 2020

sipa commented at 6:39 AM on August 13, 2020: contributor

Added conversions from signed to signed, and a check for CHAR_BIT. Anything else? Do we have any unusual assumptions on the size of int etc?

real-or-random commented at 10:16 AM on August 13, 2020: contributor

@sipa Are you aware of #792 ? :P

real-or-random commented at 11:32 AM on August 13, 2020: contributor

One downside is that when it fails you get an extremely opaque error.

We could use static_assert if it's supported by the compiler but I don't think it's worth the additional #ifdefs. These errors should be super rare, so it's acceptable that they're somewhat opaque. And it's probably better to have a compiler error instead of a runtime error.

I read up a little bit on these techniques. The issues with VLAs was something else: In some cases this array trick silently didn't do anything when the expression is non-constant, e.g., when you have a compiler like GCC that supports VLAs as an extension and you happen to pass a non-constant value, then it can't be a compiler error even if the size is negative. This hit the Linux kernel for example.

But what we do here is robust against this failure mode because VLAs are never supported on a file level / global scope. I verified this in godbolt. Even GCC errors out if you pass a non-constant value. (Clang fails at another stage but the message is pretty harsh: fields must have a constant size: 'variable length array in structure' extension will never be supported :D) The difference in the Linux kernel is probably that they don't want to collect all the assumptions in a single place and they want a statement instead.

Approach ACK

Maybe we want to move the assumptions to a separate header like in Bitcoin Core (https://github.com/bitcoin/bitcoin/blob/master/src/compat/assumptions.h). That's cleaner and it's easier to point people to the file, e.g., in the README.

gmaxwell commented at 6:43 PM on August 13, 2020: contributor

A separate file might make it marginally more likely to get a more useful error message (e.g. telling you what file it was in) from more compilers.

Add support for (signed) __int128 02b6c87b52

sipa force-pushed on Aug 13, 2020

sipa commented at 6:51 PM on August 13, 2020: contributor

A separate file might make it marginally more likely to get a more useful error message (e.g. telling you what file it was in) from more compilers.

That's a good point.

Moved.

gmaxwell commented at 7:44 PM on August 13, 2020: contributor

You might want to a comment above it that says something like:

/* This library, like most software, relies on a number of compiler implementation defined (not undefined) behaviours. Although the behaviours we require are essentially universal we test them specifically here to reduce the odds of experiencing an unwelcome surprise. */

sipa force-pushed on Aug 13, 2020

sipa commented at 8:09 PM on August 13, 2020: contributor

@gmaxwell Added.

in src/assumptions.h:30 in 4a81f79a55 outdated

  25 | +           implementation-defined. Verify that they function as reinterpreting the lower
  26 | +           bits of the input in two's complement notation. Do this for conversions:
  27 | +           - from uint(N)_t to int(N)_t with negative result
  28 | +           - from uint(2N)_t to int(N)_t with negative result
  29 | +           - from int(2N)_t to int(N)_t with negative result
  30 | +           - from int(2N)_t to int(N)_t with positivie result */

gmaxwell commented at 10:42 PM on August 13, 2020:

positive

sipa commented at 11:09 PM on August 13, 2020:

Fixed.

sipa force-pushed on Aug 13, 2020

gmaxwell commented at 11:21 PM on August 13, 2020: contributor

Include it in gen_context.c too. Sorry for dribbling changes.

sipa force-pushed on Aug 13, 2020

sipa commented at 11:25 PM on August 13, 2020: contributor

Done. Also added to bench_internal.c, tests_exhaustive.c, and valgrind_ctime_test.c.

gmaxwell commented at 12:15 AM on August 14, 2020: contributor

ACK fdb6dbc9e765588280e06d5a7050aa40d7e6c551

sipa renamed this:
~~Check assumptions on integer implementation at runtime~~
Check assumptions on integer implementation at compile time
on Aug 14, 2020

in src/assumptions.h:62 in fdb6dbc9e7 outdated

  57 | +        /* To int128_t. */
  58 | +        ((int128_t)(((uint128_t)0xB1234567C8901234ULL << 64) + 0xD5678901E2345678ULL) == (int128_t)(-(int128_t)0x8E1648B3F50E80DCULL * 0x8E1648B3F50E80DDULL + 0x5EA688D5482F9464ULL)) &&
  59 | +#endif
  60 | +
  61 | +        /* Right shift on negative signed values is implementation defined. Verify that it
  62 | +           acts as a conversion to unsigned, right shift, and conversion back to signed.

real-or-random commented at 10:17 AM on August 14, 2020:

I think this text is wrong. If it acted as a conversion to unsigned and then shift, they would exactly not be sign-extending, no?

sipa commented at 9:19 PM on August 14, 2020:

You're right. And the fact that it's different is exactly the reason why we need signed types at all...

sipa commented at 11:13 PM on August 14, 2020:

Fixed.

real-or-random commented at 10:19 AM on August 14, 2020: contributor

Added conversions from signed to signed, and a check for CHAR_BIT. Anything else? Do we have any unusual assumptions on the size of int etc?

ACK except nit. We should then add more assumptions from #792 later.

Compile-time check assumptions on integer types 7c068998ba

sipa force-pushed on Aug 14, 2020

sipa commented at 2:00 AM on August 15, 2020: contributor

@real-or-random Sounds good.

gmaxwell commented at 5:52 AM on August 15, 2020: contributor

ACK 7c068998bac3e4a254d8542458b2068e38fca435

real-or-random commented at 10:19 AM on August 15, 2020: contributor

ACK 7c068998bac3e4a254d8542458b2068e38fca435 code review and tested

real-or-random merged this on Aug 16, 2020

real-or-random closed this on Aug 16, 2020

jasonbcox referenced this in commit 35167d3d0d on Sep 29, 2020

deadalnix referenced this in commit d243ddf31b on Sep 30, 2020

sipa cross-referenced this on Oct 17, 2020 from issue Update secp256k1 by str4d