Subtrahieren von gepackten 8-Bit-Ganzzahlen in einer 64-Bit-Ganzzahl von 1 parallel, SWAR ohne Hardware-SIMD

77

Wenn ich eine 64-Bit-Ganzzahl habe, die ich als Array gepackter 8-Bit-Ganzzahlen mit 8 Elementen interpretiere. Ich muss die Konstante 1von jeder gepackten Ganzzahl subtrahieren, während ich den Überlauf behandle, ohne dass das Ergebnis eines Elements das Ergebnis eines anderen Elements beeinflusst.

Ich habe diesen Code im Moment und er funktioniert, aber ich brauche eine Lösung, die die Subtraktion jeder gepackten 8-Bit-Ganzzahl parallel ausführt und keine Speicherzugriffe ausführt. Auf x86 könnte ich solche SIMD-Anweisungen verwenden psubb, die gepackte 8-Bit-Ganzzahlen parallel subtrahieren, aber die Plattform, für die ich codiere, unterstützt keine SIMD-Anweisungen. (RISC-V in diesem Fall).

Ich versuche also, SWAR (SIMD innerhalb eines Registers) auszuführen, um die Übertragsausbreitung zwischen Bytes von a manuell aufzuheben, uint64_tund mache etwas Äquivalentes dazu:

uint64_t sub(uint64_t arg) {
    uint8_t* packed = (uint8_t*) &arg;

    for (size_t i = 0; i < sizeof(uint64_t); ++i) {
        packed[i] -= 1;
    }

    return arg;
}

Ich denke, Sie könnten dies mit bitweisen Operatoren tun, aber ich bin mir nicht sicher. Ich suche nach einer Lösung, die keine SIMD-Anweisungen verwendet. Ich suche nach einer Lösung in C oder C ++, die ziemlich portabel ist oder nur die Theorie dahinter, damit ich meine eigene Lösung implementieren kann.

cam-weiß
quelle
5
Müssen sie 8-Bit sein oder könnten sie stattdessen 7-Bit sein?
Tadman
Es muss ihnen 8-Bit leid tun :(
cam-white
12
Techniken für solche
Harold
1
Erwarten Sie, dass ein Byte mit Null in 0xff umbrochen wird?
Alnitak

Antworten:

75

Wenn Sie eine CPU mit effizienten SIMD-Anweisungen haben, ist auch SSE / MMX paddb( _mm_add_epi8) möglich. Die Antwort von Peter Cordes beschreibt auch die GNU C-Vektorsyntax (gcc / clang) und die Sicherheit für UB mit striktem Aliasing. Ich empfehle dringend, auch diese Antwort zu überprüfen.

Das Selbermachen uint64_tist vollständig portabel, erfordert jedoch weiterhin Sorgfalt, um Ausrichtungsprobleme und striktes Aliasing von UB beim Zugriff auf ein uint8_tArray mit a zu vermeiden uint64_t*. Sie haben diesen Teil aus der Frage herausgelassen, indem Sie mit Ihren Daten in einem uint64_tbereits begonnen haben, aber für GNU C may_aliaslöst ein typedef das Problem (siehe Peters Antwort dafür oder memcpy).

Andernfalls können Sie Ihre Daten als zuordnen / deklarieren uint64_tund darauf zugreifen, uint8_t*wenn Sie einzelne Bytes möchten. unsigned char*darf alles aliasen, um das Problem für den speziellen Fall von 8-Bit-Elementen zu umgehen. (Wenn uint8_tes überhaupt existiert, ist es wahrscheinlich sicher anzunehmen, dass es eine ist unsigned char.)


Beachten Sie, dass dies eine Änderung gegenüber einem früheren falschen Algorithmus ist (siehe Versionsverlauf).

Dies ist ohne Schleife für eine beliebige Subtraktion möglich und wird für eine bekannte Konstante wie 1in jedem Byte effizienter . Der Haupttrick besteht darin, die Ausführung jedes Bytes durch Setzen des High-Bits zu verhindern und dann das Subtraktionsergebnis zu korrigieren.

Wir werden die hier angegebene Subtraktionstechnik leicht optimieren . Sie definieren:

SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)

mit Hdefiniert als 0x8080808080808080U(dh die MSBs jeder gepackten ganzen Zahl). Für eine Dekrementierung yist 0x0101010101010101U.

Wir wissen, dass yalle MSBs klar sind, sodass wir einen der Maskenschritte überspringen können (dh y & ~Hder gleiche wie yin unserem Fall). Die Berechnung läuft wie folgt ab:

  1. Wir setzen die MSBs jeder Komponente xauf 1, damit sich ein Kredit nicht über das MSB hinaus zur nächsten Komponente ausbreiten kann. Nennen Sie dies den eingestellten Eingang.
  2. Wir subtrahieren 1 von jeder Komponente, indem wir 0x01010101010101von der korrigierten Eingabe subtrahieren . Dies führt dank Schritt 1 nicht zu Ausleihen zwischen Komponenten. Nennen Sie dies den angepassten Ausgang.
  3. Wir müssen jetzt das MSB des Ergebnisses korrigieren. Wir xor die angepasste Ausgabe mit den invertierten MSBs der ursprünglichen Eingabe, um die Korrektur des Ergebnisses abzuschließen.

Die Operation kann wie folgt geschrieben werden:

#define U64MASK 0x0101010101010101U
#define MSBON 0x8080808080808080U
uint64_t decEach(uint64_t i){
      return ((i | MSBON) - U64MASK) ^ ((i ^ MSBON) & MSBON);
}

Dies wird vorzugsweise vom Compiler eingefügt (verwenden Sie Compiler-Anweisungen , um dies zu erzwingen), oder der Ausdruck wird als Teil einer anderen Funktion inline geschrieben.

Testfälle:

in:  0000000000000000
out: ffffffffffffffff

in:  f200000015000013
out: f1ffffff14ffff12

in:  0000000000000100
out: ffffffffffff00ff

in:  808080807f7f7f7f
out: 7f7f7f7f7e7e7e7e

in:  0101010101010101
out: 0000000000000000

Leistungsdetails

Hier ist die x86_64-Assembly für einen einzelnen Aufruf der Funktion. Für eine bessere Leistung sollte es in der Hoffnung eingefügt werden, dass die Konstanten so lange wie möglich in einem Register leben können. In einer engen Schleife, in der die Konstanten in einem Register leben, benötigt das tatsächliche Dekrement fünf Anweisungen: oder + nicht + und + addiere + xor nach der Optimierung. Ich sehe keine Alternativen, die die Optimierung des Compilers übertreffen würden.

uint64t[rax] decEach(rcx):
    movabs  rcx, -9187201950435737472
    mov     rdx, rdi
    or      rdx, rcx
    movabs  rax, -72340172838076673
    add     rax, rdx
    and     rdi, rcx
    xor     rdi, rcx
    xor     rax, rdi
    ret

Mit einigen IACA-Tests des folgenden Snippets:

// Repeat the SWAR dec in a loop as a microbenchmark
uint64_t perftest(uint64_t dummyArg){
    uint64_t dummyCounter = 0;
    uint64_t i = 0x74656a6d27080100U; // another dummy value.
    while(i ^ dummyArg) {
        IACA_START
        uint64_t naive = i - U64MASK;
        i = naive + ((i ^ naive ^ U64MASK) & U64MASK);
        dummyCounter++;
    }
    IACA_END
    return dummyCounter;
}

Wir können zeigen, dass auf einer Skylake-Maschine das Dekrementieren, Xor und Vergleichen + Springen mit knapp 5 Zyklen pro Iteration durchgeführt werden kann:

Throughput Analysis Report
--------------------------
Block Throughput: 4.96 Cycles       Throughput Bottleneck: Backend
Loop Count:  26
Port Binding In Cycles Per Iteration:
--------------------------------------------------------------------------------------------------
|  Port  |   0   -  DV   |   1   |   2   -  D    |   3   -  D    |   4   |   5   |   6   |   7   |
--------------------------------------------------------------------------------------------------
| Cycles |  1.5     0.0  |  1.5  |  0.0     0.0  |  0.0     0.0  |  0.0  |  1.5  |  1.5  |  0.0  |
--------------------------------------------------------------------------------------------------

(Natürlich würden Sie auf x86-64 nur oder movqin eine XMM-Registrierung für laden paddb, daher ist es möglicherweise interessanter zu sehen, wie es für eine ISA wie RISC-V kompiliert wird.)

Nanofarad
quelle
4
Ich benötige meinen Code, um auf RISC-V-Computern ausgeführt zu werden, die (noch) keine SIMD-Anweisungen haben, geschweige denn Unterstützung für MMX
cam-white
2
@ cam-white Verstanden - das ist wahrscheinlich das Beste, was Sie dann tun können. Ich werde auf Godbolt hüpfen, um die Versammlung auf RISC zu überprüfen. Edit: Keine RISC-V-Unterstützung für Godbolt :(
Nanofarad
7
Es gibt RISC-V - Unterstützung auf Godbolt tatsächlich, zum Beispiel wie diese (E: scheint , dass der Compiler bei der Erstellung der Maske übermäßig kreativ bekommt ..)
harold
4
Weiterführende Literatur darüber , wie die Parität (auch als „Carry-out - Vektor“ genannt) Trick kann in verschiedenen Situationen eingesetzt werden: emulators.com/docs/LazyOverflowDetect_Final.pdf
JPA
4
Ich habe eine weitere Bearbeitung vorgenommen. Native GNU C-Vektoren vermeiden tatsächlich Probleme mit striktem Aliasing. Ein Vektor von uint8_tdarf uint8_tDaten aliasen . Anrufer Ihrer Funktion (die uint8_tDaten in a übertragen müssen uint64_t) müssen sich um striktes Aliasing sorgen! Daher sollte das OP wahrscheinlich nur Arrays deklarieren / zuweisen, uint64_tda dies char*in ISO C ++ als Alias ​​zulässig ist, aber nicht umgekehrt.
Peter Cordes
16

Für RISC-V verwenden Sie wahrscheinlich GCC / clang.

Unterhaltsame Tatsache: GCC kennt einige dieser SWAR-Bithack-Tricks (in anderen Antworten gezeigt) und kann sie für Sie verwenden, wenn Sie Code mit nativen GNU C-Vektoren für Ziele ohne Hardware-SIMD-Anweisungen kompilieren . (Aber wenn Sie für RISC-V klirren, wird es nur naiv für skalare Operationen abgewickelt, sodass Sie es selbst tun müssen, wenn Sie eine gute Leistung über Compiler hinweg wünschen.)

Ein Vorteil der nativen Vektorsyntax besteht darin, dass beim Targeting einer Maschine mit Hardware-SIMD diese verwendet wird, anstatt Ihren Bithack oder etwas Schreckliches automatisch zu vektorisieren.

Es macht es einfach, vector -= scalarOperationen zu schreiben ; Die Syntax Just Works überträgt implizit den Skalar für Sie.


Beachten Sie auch, dass eine uint64_t*Last von a ein uint8_t array[]striktes Aliasing für UB ist. Seien Sie also vorsichtig damit. (Siehe auch Warum muss glibc's strlen so kompliziert sein, um schnell zu laufen? Betreff: SWAR-Bithacks in reinem C sicher strikt aliasing machen). Möglicherweise möchten Sie, dass so etwas deklariert, uint64_tdass Sie mit dem Zeiger auf andere Objekte zugreifen können, z. B. wie dies char*in ISO C / C ++ funktioniert.

Verwenden Sie diese, um uint8_t-Daten in ein uint64_t zu übertragen und mit anderen Antworten zu verwenden:

// GNU C: gcc/clang/ICC but not MSVC
typedef uint64_t  aliasing_u64 __attribute__((may_alias));  // still requires alignment
typedef uint64_t  aliasing_unaligned_u64 __attribute__((may_alias, aligned(1)));

Die andere Möglichkeit, aliasing-sichere Lasten auszuführen, ist memcpyin a uint64_t, wodurch auch die alignof(uint64_tAusrichtungsanforderung entfällt . Bei ISAs ohne effiziente nicht ausgerichtete Lasten wird gcc / clang jedoch nicht inline und optimiert, memcpywenn nicht nachgewiesen werden kann, dass der Zeiger ausgerichtet ist, was für die Leistung katastrophal wäre.

TL: DR: Am besten deklarieren Sie Ihre Daten alsuint64_t array[...] oder ordnen sie dynamisch zu uint64_t, oder vorzugsweise.alignas(16) uint64_t array[]; Dies stellt die Ausrichtung auf mindestens 8 Bytes oder 16 Bytes sicher, wenn Sie dies angeben alignas.

Da dies uint8_tmit ziemlicher Sicherheit der Fall ist unsigned char*, ist es sicher, auf die Bytes eines uint64_tVia zuzugreifen uint8_t*(bei einem uint8_t-Array jedoch nicht umgekehrt). In diesem speziellen Fall, in dem es sich um einen schmalen Elementtyp handelt unsigned char, können Sie das Problem des strengen Aliasing umgehen, da chares speziell ist.


Beispiel für die native Vektorsyntax von GNU C:

GNU C-native Vektoren dürfen immer einen Alias ​​mit ihrem zugrunde liegenden Typ haben (z. B. int __attribute__((vector_size(16)))können sicher Alias ​​sein, intaber nicht floatoder uint8_toder irgendetwas anderes.

#include <stdint.h>
#include <stddef.h>

// assumes array is 16-byte aligned
void dec_mem_gnu(uint8_t *array) {
    typedef uint8_t v16u8 __attribute__ ((vector_size (16), may_alias));
    v16u8 *vecs = (v16u8*) array;
    vecs[0] -= 1;
    vecs[1] -= 1;   // can be done in a loop.
}

Bei RISC-V ohne HW-SIMD können Sie vector_size(8)nur die Granularität ausdrücken, die Sie effizient verwenden können, und doppelt so viele kleinere Vektoren erstellen.

Aber vector_size(8)kompiliert sehr dumm für x86 mit GCC und clang: GCC verwendet SWAR-Bithacks in GP-Integer-Registern, Clang entpackt in 2-Byte-Elemente, um ein 16-Byte-XMM-Register zu füllen, und packt dann neu. (MMX ist so veraltet, dass GCC / Clang sich nicht einmal die Mühe macht, es zu verwenden, zumindest nicht für x86-64.)

Aber mit vector_size (16)( Godbolt ) bekommen wir das erwartete movdqa/ paddb. (Mit einem All-One-Vektor generiert von pcmpeqd same,same). Da -march=skylakewir immer noch zwei separate XMM-Operationen anstelle einer YMM erhalten, "vektorisieren" aktuelle Compiler leider auch keine Vektoroperationen automatisch in breitere Vektoren: /

Für AArch64 ist es nicht so schlecht zu verwenden vector_size(8)( Godbolt ); ARM / AArch64 kann nativ in 8- oder 16-Byte-Blöcken mit doder qRegistern arbeiten.

Sie möchten also wahrscheinlich vector_size(16)tatsächlich kompilieren, wenn Sie eine tragbare Leistung für x86, RISC-V, ARM / AArch64 und POWER wünschen . Einige andere ISAs machen jedoch SIMD innerhalb von 64-Bit-Integer-Registern, wie MIPS MSA, denke ich.

vector_size(8)erleichtert das Betrachten des asm (nur ein Register mit Daten): Godbolt Compiler Explorer

# GCC8.2 -O3 for RISC-V for vector_size(8) and only one vector

dec_mem_gnu(unsigned char*):
        lui     a4,%hi(.LC1)           # generate address for static constants.
        ld      a5,0(a0)                 # a5 = load from function arg
        ld      a3,%lo(.LC1)(a4)       # a3 = 0x7F7F7F7F7F7F7F7F
        lui     a2,%hi(.LC0)
        ld      a2,%lo(.LC0)(a2)       # a2 = 0x8080808080808080
                             # above here can be hoisted out of loops
        not     a4,a5                  # nx = ~x
        and     a5,a5,a3               # x &= 0x7f... clear high bit
        and     a4,a4,a2               # nx = (~x) & 0x80... inverse high bit isolated
        add     a5,a5,a3               # x += 0x7f...   (128-1)
        xor     a5,a4,a5               # x ^= nx  restore high bit or something.

        sd      a5,0(a0)               # store the result
        ret

Ich denke, es ist die gleiche Grundidee wie bei den anderen Antworten ohne Schleifen. Verhindern Sie das Tragen und korrigieren Sie das Ergebnis.

Dies sind 5 ALU-Anweisungen, schlimmer als die beste Antwort, denke ich. Es sieht jedoch so aus, als ob die kritische Pfadlatenz nur 3 Zyklen beträgt, wobei zwei Ketten mit jeweils 2 Befehlen zum XOR führen. Die Antwort von @Reinstate Monica - ζ - wird zu einer 4-Zyklus-Dep-Kette (für x86) kompiliert. Der 5-Zyklus-Schleifendurchsatz wird durch die Einbeziehung eines Naiven subin den kritischen Pfad eingeschränkt, und die Schleife führt zu einem Engpass bei der Latenz.

Dies ist jedoch bei Klirren nutzlos. Es wird nicht einmal in der Reihenfolge hinzugefügt und gespeichert, in der es geladen wurde, sodass es nicht einmal ein gutes Software-Pipelining durchführt!

# RISC-V clang (trunk) -O3
dec_mem_gnu(unsigned char*):
        lb      a6, 7(a0)
        lb      a7, 6(a0)
        lb      t0, 5(a0)
...
        addi    t1, a5, -1
        addi    t2, a1, -1
        addi    t3, a2, -1
...
        sb      a2, 7(a0)
        sb      a1, 6(a0)
        sb      a5, 5(a0)
...
        ret
Peter Cordes
quelle
13

Ich möchte darauf hinweisen, dass der Code, den Sie geschrieben haben, tatsächlich vektorisiert wird, sobald Sie anfangen, sich mit mehr als einem einzelnen uint64_t zu befassen.

https://godbolt.org/z/J9DRzd

Robthebloke
quelle
1
Können Sie erklären oder einen Hinweis darauf geben, was dort passiert? Es scheint ziemlich interessant zu sein.
n314159
2
Ich habe versucht, dies ohne SIMD-Anweisungen zu tun, aber ich fand das trotzdem interessant :)
cam-white
8
Andererseits ist dieser SIMD-Code schrecklich. Der Compiler hat völlig falsch verstanden, was hier passiert. E: Es ist ein Beispiel für "Dies wurde eindeutig von einem Compiler gemacht, weil kein Mensch so dumm wäre"
Harold
1
@PeterCordes: Ich habe mehr nach dem Vorbild eines __vector_loop(index, start, past, pad)Konstrukts gedacht, das eine Implementierung als for(index=start; index<past; index++)[dh jede Implementierung könnte Code mit ihm verarbeiten, indem sie lediglich ein Makro definiert] behandeln könnte, das aber eine lockere Semantik hätte, um einen Compiler zum Verarbeiten von Dingen einzuladen Jede Zweierpotenzgröße bis zu pad, wobei der Anfang nach unten und das Ende nach oben verlängert werden, wenn sie nicht bereits ein Vielfaches der Blockgröße sind. Nebenwirkungen in jedem Block wären nicht sequenziert, und wenn a breakinnerhalb der Schleife auftritt, werden andere Wiederholungen ...
Supercat
1
@PeterCordes: While restrictist hilfreich (und wäre hilfreicher, wenn der Standard ein Konzept von "zumindest potenziell basierend auf" erkennen und dann "basierend auf" und "zumindest potenziell basierend auf" direkt ohne doofe und nicht praktikable Eckfälle definieren würde) Mein Vorschlag würde es einem Compiler auch ermöglichen, mehr Ausführungen der Schleife als angefordert durchzuführen - etwas, das die Vektorisierung erheblich vereinfachen würde, für das der Standard jedoch keine Vorkehrungen trifft.
Supercat
11

Sie können sicherstellen, dass die Subtraktion nicht überläuft, und dann das hohe Bit korrigieren:

uint64_t sub(uint64_t arg) {
    uint64_t x1 = arg | 0x80808080808080;
    uint64_t x2 = ~arg & 0x80808080808080;
    // or uint64_t x2 = arg ^ x1; to save one instruction if you don't have an andnot instruction
    return (x1 - 0x101010101010101) ^ x2;
}
Falk Hüffner
quelle
Ich denke, es funktioniert für alle 256 möglichen Werte eines Bytes; Ich habe es auf Godbolt (mit RISC-V- Klirren ) godbolt.org/z/DGL9aq gesetzt , um die Ergebnisse der konstanten Ausbreitung für verschiedene Eingaben wie 0x0, 0x7f, 0x80 und 0xff (in die Mitte der Zahl verschoben) zu betrachten. Sieht gut aus. Ich denke, die beste Antwort läuft auf dasselbe hinaus, aber sie erklärt es auf kompliziertere Weise.
Peter Cordes
Compiler könnten hier besser Konstanten in Registern konstruieren. Clang verbringt eine Menge Anweisungen damit, zu konstruieren splat(0x01)und splat(0x80)anstatt eine Schicht voneinander zu entfernen. Selbst wenn Sie es so in die Quelle godbolt.org/z/6y9v-u schreiben , wird der Compiler nicht dazu gebracht, besseren Code zu erstellen. es macht nur eine konstante Ausbreitung.
Peter Cordes
Ich frage mich, warum es nicht einfach die Konstante aus dem Speicher lädt. Das ist es, was Compiler für Alpha (eine ähnliche Architektur) tun.
Falk Hüffner
GCC für RISC-V tut Lastkonstanten aus dem Speicher. Es sieht so aus, als ob Clang etwas optimiert werden muss, es sei denn, Daten-Cache-Fehler werden erwartet und sind im Vergleich zum Befehlsdurchsatz teuer. (Dieses Gleichgewicht kann sich sicherlich seit Alpha geändert haben, und vermutlich sind unterschiedliche Implementierungen von RISC-V unterschiedlich. Compiler könnten auch viel besser abschneiden, wenn sie erkennen, dass es sich um ein sich wiederholendes Muster handelt, das sie verschieben / ODER erweitern können, nachdem sie mit einer LUI / Addition begonnen haben für 20 + 12 = 32 Bits sofortiger Daten. AArch64s Bitmuster-Sofortdaten könnten diese sogar als Sofortdaten für AND / OR / XOR (Smart Decode vs. Dichtewahl) verwenden
Peter Cordes
Es wurde eine Antwort hinzugefügt , die GCCs Native-Vector-SWAR für RISC-V zeigt
Peter Cordes
7

Ich bin mir nicht sicher, ob dies das ist, was Sie wollen, aber es führt die 8 Subtraktionen parallel zueinander aus:

#include <cstdint>

constexpr uint64_t mask = 0x0101010101010101;

uint64_t sub(uint64_t arg) {
    uint64_t mask_cp = mask;
    for(auto i = 0; i < 8 && mask_cp; ++i) {
        uint64_t new_mask = (arg & mask_cp) ^ mask_cp;
        arg = arg ^ mask_cp;
        mask_cp = new_mask << 1;
    }
    return arg;
}

Erläuterung: Die Bitmaske beginnt mit einer 1 in jeder der 8-Bit-Zahlen. Wir xor es mit unserem Argument. Wenn wir an dieser Stelle eine 1 hatten, haben wir 1 abgezogen und müssen aufhören. Dies erfolgt durch Setzen des entsprechenden Bits auf 0 in new_mask. Wenn wir eine 0 hatten, setzen wir sie auf 1 und müssen den Übertrag ausführen, sodass das Bit 1 bleibt und wir die Maske nach links verschieben. Sie sollten selbst prüfen, ob die Generierung der neuen Maske wie beabsichtigt funktioniert, aber eine zweite Meinung wäre nicht schlecht.

PS: Ich bin mir nicht sicher, ob die Überprüfung, ob mask_cpdie Schleife nicht null ist, das Programm verlangsamen kann. Ohne sie wäre der Code immer noch korrekt (da die 0-Maske einfach nichts bewirkt) und es wäre für den Compiler viel einfacher, das Abrollen der Schleife durchzuführen.

n314159
quelle
forläuft nicht parallel, bist du verwirrt mit for_each?
LTPCGO
3
@LTPCGO Nein, es ist nicht meine Absicht, diese for-Schleife zu parallelisieren, dies würde den Algorithmus tatsächlich beschädigen. Dieser Code funktioniert jedoch parallel für die verschiedenen 8-Bit-Ganzzahlen in der 64-Bit-Ganzzahl, dh alle 8 Subtraktionen werden gleichzeitig ausgeführt, benötigen jedoch bis zu 8 Schritte.
n314159
Mir ist klar, dass das, was ich gefragt habe, vielleicht etwas unvernünftig war, aber das war ziemlich nahe an dem, was ich brauchte, danke :)
cam-white
4
int subtractone(int x) 
{
    int f = 1; 

    // Flip all the set bits until we find a 1 at position y
    while (!(x & f)) { 
        x = x^f; 
        f <<= 1; 
    } 

    return x^f; // return answer but remember to flip the 1 at y
} 

Sie können dies mit bitweisen Operationen tun, indem Sie die obigen Schritte ausführen, und Sie müssen nur Ihre Ganzzahl in 8-Bit-Teile teilen, um 8-mal in diese Funktion zu senden. Der folgende Teil stammt aus Wie teilt man eine 64-Bit-Zahl in acht 8-Bit-Werte auf? mit mir in der obigen Funktion hinzufügen

uint64_t v= _64bitVariable;
uint8_t i=0,parts[8]={0};
do parts[i++] = subtractone(v&0xFF); while (v>>=8);

Es ist C oder C ++ gültig, unabhängig davon, wie jemand darauf stößt

LTPCGO
quelle
5
Dies entspricht jedoch nicht der Arbeit, was die Frage von OP ist.
Nickelpro
Ja, @nickelpro ist richtig, dies würde jede Subtraktion nacheinander durchführen. Ich möchte alle 8-Bit-Ganzzahlen gleichzeitig subtrahieren. Ich freue mich über die Antwort, danke bro
cam-white
2
@nickelpro, als ich mit der Antwort begann, wurde die Bearbeitung nicht vorgenommen, die den parallelen Teil der Frage darstellte, und so habe ich sie erst nach der Übermittlung bemerkt. Ich werde sie verlassen, falls sie für andere nützlich ist, da sie zumindest die Frage beantwortet Teil, um bitweise Operationen durchzuführen, und es könnte dazu gebracht werden, parallel zu arbeiten, indem for_each(std::execution::par_unseq,...anstelle von whiles verwendet wird
LTPCGO
2
Es ist mein schlechtes, ich habe die Frage eingereicht und dann festgestellt, dass ich nicht gesagt habe, dass sie parallel bearbeitet werden muss
cam-white
2

Sie werden nicht versuchen, den Code zu finden, aber für eine Dekrementierung um 1 können Sie die Gruppe um 8 1s dekrementieren und dann überprüfen, ob die LSBs der Ergebnisse "umgedreht" wurden. Jedes nicht umgeschaltete LSB zeigt an, dass ein Übertrag von den benachbarten 8 Bits aufgetreten ist. Es sollte möglich sein, eine Folge von ANDs / ORs / XORs ohne Verzweigungen zu erarbeiten.

Hot Licks
quelle
Das mag funktionieren, aber betrachten Sie den Fall, in dem sich ein Übertrag über eine Gruppe von 8 Bits in eine andere ausbreitet. Die Strategie in den guten Antworten (zuerst das MSB oder etwas anderes einzustellen), um sicherzustellen, dass sich der Übertrag nicht ausbreitet, ist wahrscheinlich mindestens so effizient, wie dies sein könnte. Das aktuell zu schlagende Ziel (dh die guten verzweigungslosen Antworten ohne Schleife) sind 5 RISC-V-Asm-ALU-Befehle mit Parallelität auf Befehlsebene, wodurch der kritische Pfad nur 3 Zyklen beträgt und zwei 64-Bit-Konstanten verwendet werden.
Peter Cordes
0

Konzentrieren Sie die Arbeit auf jedes Byte ganz alleine und setzen Sie es wieder dort ab, wo es war.

uint64_t sub(uint64_t arg) {
   uint64_t res = 0;

   for (int i = 0; i < 64; i+=8) 
     res += ((arg >> i) - 1 & 0xFFU) << i;

    return res;
   }
nonock
quelle