Der schnellste Weg, um eine Maske mit n Einsen ab Position i . zu erstellen

Was ist der schnellste Weg (in Bezug auf CPU-Zyklen auf gängiger moderner Architektur), um eine Maske mit len Bits auf 1 gesetzt ab Position pos:

template <class UIntType>
constexpr T make_mask(std::size_t pos, std::size_t len)
{
    // Body of the function
}

// Call of the function
auto mask = make_mask<uint32_t>(4, 10);
// mask = 00000000 00000000 00111111 11110000 
// (in binary with MSB on the left and LSB on the right)

Gibt es außerdem irgendwelche Compiler-Intrinsics oder? BMI Funktion, die helfen kann?

Schnellste Weg? Ich würde so etwas verwenden:

template <class T>
constexpr T make_mask(std::size_t pos, std::size_t len)
{
  return ((static_cast<T>(1) << len)-1) << pos;
}

Wenn durch “ab pos“, meinst du, dass sich das niedrigste Bit der Maske an der Position befindet, die 2 . entspricht^Pos (wie in deinem Beispiel):

((UIntType(1) << len) - UIntType(1)) << pos

Wenn das möglich ist len ist ≥ die Anzahl der Bits in UIntType, vermeiden Sie undefiniertes Verhalten mit einem Test:

(((len < std::numeric_limits<UIntType>::digits)
     ? UIntType(1)<<len
     : 0) - UIntType(1)) << pos

(Falls das auch möglich ist pos ist std::numeric_limits<UIntType>::digits, benötigen Sie einen weiteren ternären Op-Test.)

Sie könnten auch verwenden:

(UIntType(1)<<(len>>1)<<((len+1)>>1) - UIntType(1)) << pos

wodurch der ternäre Betrieb auf Kosten von drei zusätzlichen Schichtführern vermieden wird; Ich bezweifle, dass es schneller wäre, aber ein sorgfältiges Benchmarking wäre erforderlich, um es sicher zu wissen.

Vielleicht mit einer Tabelle? Für Typ uint32_t Du kannst schreiben:

static uint32_t masks[] = { 0x0, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f...}; // only 32 such masks
return masks[len] << pos;

Was auch immer der int-Typ ist, die Anzahl der Masken ist nicht so groß und die Tabelle kann leicht durch Vorlagen generiert werden.

Für BMI, vielleicht mit BZHI? Ausgehend von allen Bits gesetzt, BZHI mit Wert 32-len und dann um pos verschieben.

Die Geschwindigkeit ist hier irrelevant, da der Ausdruck konstant ist, daher vom Optimierer vorberechnet und aller Wahrscheinlichkeit nach als unmittelbarer Operand verwendet wird. Was auch immer Sie verwenden, es kostet Sie 0 Zyklus.

Das größte Problem hierbei ist die Bandbreite der möglichen Eingaben. In C, Verschiebungen mit einer Anzahl größer als die Schriftbreite sind undefiniertes Verhalten. Allerdings sieht es so aus len kann sinnvollerweise von 0 bis zur Schriftbreite reichen. zB 33 verschiedene Längen für uint32_t. Mit pos=0 erhalten wir Masken von 0 bis 0xFFFFFFFF. (Ich gehe aus Gründen der Übersichtlichkeit nur von 32-Bit in Englisch und ASM aus, verwende aber generisches C++).

Wenn wir beide Enden dieses Bereichs als mögliche Eingaben ausschließen können, gibt es nur 32 mögliche Längen, und wir können eine Links- oder Rechtsverschiebung als Baustein verwenden. (Benutze ein assert() um den Eingabebereich in Debug-Builds zu überprüfen.)

Ich habe mehrere Versionen (aus anderen Antworten) der Funktion eingefügt
im Godbolt-Compiler-Explorer mit einigen Makros, um sie mit konstanter Länge, konstanter Pos oder beiden Eingangsvariablen zu kompilieren. Manche machen es besser als andere. KIIVs sieht gut aus für den Bereich, für den sie gültig ist (len=0..31, pos=0..31).

Diese Version funktioniert für len=1..32 und pos=0..31. Es erzeugt etwas schlechteres x86-64-ASM als KIIVs, also verwenden Sie KIIVs, wenn es ohne zusätzliche Überprüfungen funktioniert.

// right-shift a register of all-ones, then shift it into position.
// works for len=1..32 and pos=0..31
template <class T>
constexpr T make_mask_PJC(std::size_t pos, std::size_t len)
{
//  T all_ones = -1LL;
//  unsigned typebits = sizeof(T)*CHAR_BIT;  // std::numeric_limits<T>::digits
//  T len_ones = all_ones >> (typebits - len);
//  return len_ones << pos

  static_assert(std::numeric_limits<T>::radix == 2, "T isn't an integer type");
  return static_cast<T>(-1LL) >> (std::numeric_limits<T>::digits - len) << pos;  // pre-C++14 constexpr needs it all in one statement
}

// Same idea, but mask the shift count the same way x86 shift instructions do, so the compiler can do it for free.
// Doesn't always compile to ideal code with SHRX (BMI2), maybe gcc only knows about letting the shift instruction do the masking for the older SHR / SHL instructions
uint32_t make_mask_PJC_noUB(std::size_t pos, std::size_t len)
{
  using T=uint32_t;

  static_assert(std::numeric_limits<T>::radix == 2, "T isn't an integer type");

  T all_ones = -1LL;
  unsigned typebits = std::numeric_limits<T>::digits;
  T len_ones = all_ones >> ( (typebits - len) & (typebits-1));     // the AND optimizes away
  return len_ones << (pos & (typebits-1));

//  return static_cast<T>(-1LL) >> (std::numeric_limits<T>::digits - len) << pos;  // pre-C++14 constexpr needs it all in one statement
}

Wenn len alles sein kann in [0..32], habe ich keine großartigen Ideen für effizienten verzweigtlosen Code. Vielleicht ist die Verzweigung der richtige Weg.

uint32_t make_mask_fullrange(std::size_t pos, std::size_t len)
{
  using T=uint32_t;

  static_assert(std::numeric_limits<T>::radix == 2, "T isn't an integer type");

  T all_ones = -1LL;
  unsigned typebits = std::numeric_limits<T>::digits;
  //T len_ones = all_ones >> ( (typebits - len) & (typebits-1));
  T len_ones = len==0 ? 0 : all_ones >> ( (typebits - len) & (typebits-1));
  return len_ones << (pos & (typebits-1));

//  return static_cast<T>(-1LL) >> (std::numeric_limits<T>::digits - len) << pos;  // pre-C++14 constexpr needs it all in one statement
}