optimierte Byte-Array-Shifter

Question

Ich bin mir sicher, dass dies zuvor gefragt wurde, aber ich muss einen Shift-Operator auf einem Byte-Array variabler Länge Größe implementieren. Ich habe mich ein bisschen umgeschaut, aber ich habe keinen Standard dafür gefunden. Ich habe eine Implementierung gefunden, die funktioniert, aber ich bin mir nicht sicher, wie effizient das ist. Kennt jemand eine Standardmethode zum Verschieben eines Arrays oder zumindest eine Empfehlung, wie die Leistung meiner Implementierung gesteigert werden kann?

char* baLeftShift(const char* array, size_t size, signed int displacement,char* result) 
{ 
    memcpy(result,array,size); 
    short shiftBuffer = 0; 
    char carryFlag = 0; 
    char* byte; 
    if(displacement > 0) 
    { 
     for(;displacement--;) 
     { 
      for(byte=&(result[size - 1]);((unsigned int)(byte))>=((unsigned int)(result));byte--) 
      { 
       shiftBuffer = *byte; 
       shiftBuffer <<= 1; 
       *byte = ((carryFlag) | ((char)(shiftBuffer))); 
       carryFlag = ((char*)(&shiftBuffer))[1]; 
      } 
     } 
    } 
    else 
    { 
     unsigned int offset = ((unsigned int)(result)) + size; 
     displacement = -displacement; 
     for(;displacement--;) 
     { 
      for(byte=(char*)result;((unsigned int)(byte)) < offset;byte++) 
      { 
       shiftBuffer = *byte; 
       shiftBuffer <<= 7; 
       *byte = ((carryFlag) | ((char*)(&shiftBuffer))[1]); 
       carryFlag = ((char)(shiftBuffer)); 
      } 
     } 
    } 
    return result; 
} 

Answer 1

Wenn ich nur hinzufügen kann, was @dwelch sagt, könnten Sie dies versuchen.

1. Verschieben Sie einfach die Bytes an ihre endgültigen Positionen. Dann bleibt ein Shift-Zähler wie 3 übrig, wenn zum Beispiel jedes Byte noch um 3 Bits nach links in das nächsthöhere Byte verschoben werden muß. (Dies setzt voraus, dass die Bytes in aufsteigender Reihenfolge von rechts nach links angeordnet sind.) Dann rotieren Sie jedes Byte um 3 nach links. Eine Nachschlagetabelle ist möglicherweise schneller als eine einzelne Rotation. Dann sind in jedem Byte die 3 Bits, die verschoben werden sollen, jetzt am rechten Ende des Bytes.

2. Jetzt machen Sie eine Maske M, die (1<<3)-1 ist, die einfach die unteren 3 Bits eingeschaltet ist. Jetzt

3. , um von hohen Byte zu Byte niedriger Ordnung, dies zu tun:

   c[i] ^= M & (c[i]^c[i-1])

Das Bits c[i] von c[i-1] unter dem Maske M kopiert.

Verwenden Sie für das letzte Byte eine 0 anstelle von c[i-1].

Für Rechtsverschiebungen, gleiche Idee.

Answer 2

Mein erster Vorschlag wäre, die for-Schleifen um die Verschiebung zu beseitigen. Sie sollten in der Lage sein, die notwendigen Schichten ohne die for(;displacement--;) Schleifen zu machen. Für Verschiebungen mit einer Größe größer als 7 werden die Dinge ein wenig komplizierter, da sich Ihre inneren Schleifengrenzen ändern und Ihr Quellenoffset nicht mehr 1 ist. Das heißt, Ihr Eingangspuffer-Offset wird magnitude/8 und Ihre Verschiebung wird magnitude % 8.

Answer 3

Es sieht ineffizient aus und vielleicht bezog sich Nathan darauf.

vorausgesetzt, ein char ist 8 bits, wo dieser Code ausgeführt wird, gibt es zwei Dinge zu tun, zuerst die ganzen Bytes zu bewegen, zum Beispiel, wenn Ihre Eingabe-Array ist 0x00,0x00,0x12,0x34 und Sie nach links 8 Bits verschieben Sie dann bekommen 0x00 0x12 0x34 0x00, gibt es keinen Grund, das in einer Schleife 8 Mal ein Bit zu einer Zeit zu tun. Beginnen Sie also damit, die ganzen Zeichen in der Anordnung um (Verschiebung >> 3) Stellen zu verschieben und füllen Sie die mit Nullen erzeugten Löcher mit einer Art von (ra = (Verschiebung >> 3); ra> 3)] = Array [ra]; für (ra - = (Verschiebung >> 3); ra> (7- (Verschiebung & 7))). ein guter Compiler wird vorausberechnen (Verschiebung >> 3), Verschiebung & 7, 7- (Verschiebung & 7) und ein guter Prozessor wird genug Register haben, um alle diese Werte zu behalten. Sie könnten dem Compiler helfen, indem Sie separate Variablen für jedes dieser Elemente erstellen, aber je nach Compiler und wie Sie es verwenden, könnte es auch schlimmer werden.

Das Endergebnis ist jedoch Zeit der Code. Führen Sie eintausend 1-Bit-Verschiebungen dann tausend 2-Bit-Verschiebungen aus, usw. Zeit das Ganze, dann versuchen Sie einen anderen Algorithmus und Zeit es auf die gleiche Weise und sehen, ob die Optimierungen einen Unterschied machen, machen es besser oder schlechter. Wenn Sie im Voraus wissen, dass dieser Code immer nur für einzelne oder weniger als 8 Bit-Shifts verwendet wird, passen Sie den Timing-Test entsprechend an.

Ihre Verwendung der Carry-Flag impliziert, dass Sie wissen, dass viele Prozessoren Anweisungen speziell für die Verkettung unendlich lange Schichten mit der Standard-Register-Länge (für einzelne Bit zu einer Zeit) im Grunde durchlaufen haben. Was die C-Sprache nicht direkt unterstützt. Für die Verkettung einzelner Bitverschiebungen könnte man Assembler und wahrscheinlich den C-Code übertreffen. zumindest sind die einzelnen Bitverschiebungen schneller als der C-Code. Ein Hybrid der Verschiebung der Bytes dann, wenn die Anzahl der Bits zu verschieben (Verschiebung & 7) ist vielleicht weniger als 4 verwenden Sie den Assembler sonst verwenden Sie eine C-Schleife. Auch hier zeigen die Timing-Tests, wo die Optimierungen liegen.