Quel est le meilleur moyen C++ de multiplier les entiers non signés de manière modulaire en toute sécurité?

Imaginons que vous êtes à l'aide de <cstdint> et les types comme std::uint8_t et std::uint16_t, et souhaitez effectuer des opérations comme += et *= sur eux. Vous souhaitez que l'arithmétique sur ces nombres s'enroule de manière modulaire, comme typique en C/C++. Ce travaille normalement, et vous trouver expérimentalement fonctionne avec std::uint8_t, std::uint32_t et std::uint64_t, mais pas std::uint16_t.

Plus précisément, la multiplication avec std::uint16_t échoue parfois de manière spectaculaire, avec des builds optimisés produisant toutes sortes de résultats étranges. La raison? Indéterminé comportement dû au dépassement d'entier signé. Le compilateur optimise en fonction de l'hypothèse que le comportement indéfini ne se produit pas, et commence ainsi à élaguer des morceaux de code de votre programme. Le comportement indéfini spécifique est le suivant:

std::uint16_t x = UINT16_C(0xFFFF);
x *= x;

La raison en est les règles de promotion de C++et le fait que vous, comme presque tout le monde ces jours-ci, utilisez une plate-forme sur laquelle std::numeric_limits<int>::digits == 31. C'est-à-dire que int est 32 bits (digits compte les bits mais pas le bit de signe). {[16] } est promu à signed int, bien qu'il ne soit pas signé, et 0xFFFF * 0xFFFF déborde pour l'arithmétique signée 32 bits.

Démo du problème général:

// Compile on a recent version of clang and run it:
// clang++ -std=c++11 -O3 -Wall -fsanitize=undefined stdint16.cpp -o stdint16

#include <cinttypes>
#include <cstdint>
#include <cstdio>

int main()
{
     std::uint8_t a =  UINT8_MAX; a *= a; // OK
    std::uint16_t b = UINT16_MAX; b *= b; // undefined!
    std::uint32_t c = UINT32_MAX; c *= c; // OK
    std::uint64_t d = UINT64_MAX; d *= d; // OK

    std::printf("%02" PRIX8 " %04" PRIX16 " %08" PRIX32 " %016" PRIX64 "n",
        a, b, c, d);

    return 0;
}

Vous obtiendrez une belle erreur:

main.cpp:11:55: runtime error: signed integer overflow: 65535 * 65535
    cannot be represented in type 'int'

La façon d'éviter cela, bien sûr, est de lancer au moins unsigned int avant de multiplier. Seul le cas exact où le nombre de bits du type non signé est exactement égal à la moitié du nombre de bits de int est problématique. Tout plus petit entraînerait l'incapacité de la multiplication à déborder, comme avec std::uint8_t; tout plus grand entraînerait le mappage exact du type à l'un des rangs de promotion, comme avec std::uint64_t matching unsigned long ou unsigned long long selon la plate-forme.

Mais cela craint vraiment: il faut savoir quel type est problématique en fonction de la taille de int sur la plate-forme actuelle. Existe-t-il un meilleur moyen d'éviter un comportement indéfini avec une multiplication d'entiers non signés sans les labyrinthes #if?

28
demandé sur Myria 2014-07-17 09:39:54

3 réponses

Certains modèles de métaprogrammation avec SFINAE, peut-être.

#include <type_traits>

template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) <= sizeof(unsigned int)) , int>::type = 0>
T safe_multiply(T a, T b) {
    return (unsigned int)a * (unsigned int)b;
}

template <typename T, typename std::enable_if<std::is_unsigned<T>::value && (sizeof(T) > sizeof(unsigned int)) , int>::type = 0>
T safe_multiply(T a, T b) {
    return a * b;
}

Démo.

Edit: de plus simple:

template <typename T, typename std::enable_if<std::is_unsigned<T>::value, int>::type = 0>
T safe_multiply(T a, T b) {
    typedef typename std::make_unsigned<decltype(+a)>::type typ;
    return (typ)a * (typ)b;
}

Démo.

9
répondu T.C. 2014-07-17 07:17:35

Voici une solution relativement simple, qui force une promotion à unsigned int au lieu de int pour un type non signé plus étroit qu'un int. Je ne pense pas qu'un code soit généré par promote, ou du moins pas plus de code que la promotion entière standard; cela forcera simplement la multiplication, etc. pour utiliser des ops non signés au lieu de ceux signés:

#include <type_traits>
// Promote to unsigned if standard arithmetic promotion loses unsignedness
template<typename integer> 
using promoted =
  typename std::conditional<std::numeric_limits<decltype(integer() + 0)>::is_signed,
                            unsigned,
                            integer>::type;

// function for template deduction
template<typename integer>
constexpr promoted<integer> promote(integer x) { return x; }

// Quick test
#include <cstdint>
#include <iostream>
#include <limits>
int main() {
  uint8_t i8 = std::numeric_limits<uint8_t>::max(); 
  uint16_t i16 = std::numeric_limits<uint16_t>::max(); 
  uint32_t i32 = std::numeric_limits<uint32_t>::max(); 
  uint64_t i64 = std::numeric_limits<uint64_t>::max();
  i8 *= promote(i8);
  i16 *= promote(i16);
  i32 *= promote(i32);
  i64 *= promote(i64);

  std::cout << " 8: " << static_cast<int>(i8) << std::endl
            << "16: " << i16 << std::endl
            << "32: " << i32 << std::endl
            << "64: " << i64 << std::endl;
  return 0;
}
7
répondu rici 2014-07-17 07:03:17

Cet article concernant une solution C au cas de uint32_t * uint32_t multiplication sur un système dans lequel int est 64 bits a une solution très simple à laquelle je n'avais pas pensé: multiplication non signée 32 bits sur 64 bits provoquant un comportement indéfini?

Cette solution, traduite en mon problème, est simple:

static_cast<std::uint16_t>(1U * x * x)

Le simple fait d'impliquer 1U dans le côté gauche de la chaîne d'opérations arithmétiques comme celle-ci va promouvoir le premier paramètre au rang plus élevé de unsigned int et std::uint16_t, puis ainsi de suite en bas de la chaîne. La promotion garantira que la réponse est à la fois non signée et que les bits demandés restent présents. Le casting final le réduit ensuite au type souhaité.

C'est vraiment simple et élégant, et j'aurais aimé y avoir pensé il y a un an. Merci à tous ceux qui ont répondu avant.

6
répondu Myria 2017-05-23 11:45:47