"Arithmetic Cyclic Rotate"

[aroxx]

Hallo,

ich habe in einem short 5 Datenblöcke a 3 Bits gespeichert der Wert der höchsten Bits bleibt dabei immer frei.
Jetzt möchte ich den Datenblock mit den Bits 0,1,2 per cyclic rotate an die Stelle 12,13,14 schreiben und zwar ohne am 15. Bit etwas zu ändern. z.b.:
0100 0000 0000 0111 -> 0111 1000 0000 0000

Eine Lösung wäre sowas in der Art:

short value = 42;
short tmp = value % 8;
value = (valule >> 3) + (tmp << 12);

Hat jemand vielleicht eine Idee wie und ob man das noch performanter machen kann - am besten ohne diese Hilfsvariable?
Bisher habe ich es mit rol / ror asm Befehlen bzw. arithmetic (vorzeichenerhaltende) shifts versucht, aber keine Idee schien vielversprechend

Vielen Dank für eure Ideen!

 

[kuddlmuddl]

ich habe in einem short 5 Datenblöcke a 3 Bits gespeichert

Warum? Nutzt du C oder C++? In C++ gibts nämlich für fixed size bitset und sonst vector<bool>.
Geht es um speed oder um platz?
Bzw auch ohne ++:
Warum nutzt du nicht jeweils ein byte (uint8_t) und weist direkt zu?
Und was machst du wenn dein short 32bit hat? Wenn schon, dann doch lieber uint16_t.

 

[black90]

- überlegemodus abgeschlossen -

0100 0000 0000 0111 (16391)
-----------------------------------

0111 0000 0000 0000 (shift links 12 der 16391)
0000 1000 0000 0000 (shift rechts 3 der 16391 wegen 16Bit - 1Bit Vorzeichen - 12 Bit wegen oben)

XOR auf beide, fertig. Müsstest nur noch die aufgefüllten Nullen abhacken per AND.
32767 = Volle Bits außer Vorzeichen Bit.
0111 1000 0000 0000

result = ((16391 << 12) ^ (16391 >> 3)) & 32767

/edit
Glaube das geht einfacher. Modulo dividiert mit 32767 und gibt den Rest aus, somit müsste obiges deutlich flotter sein.

result = (16391 << 12) % 32767

 

[Shio]

kann heute Abend nicht zählen

 

[Miuwa]

Generell sind leftshifts von integern, die zum Overflow führen UB. Ich bin mir nicht sicher, ob das hier auch ein Problem ist, weil shorts bei arithmetischen Operation erstmal zu ints promoted werden und es dann bei den typischen short/int größen keinen overlfow geben sollte. Aber generell würde ich bei sowas immer mit unsigned integer/shorts arbeiten - insbesondere wie von kuddlmuddl vorgeschlagen uint16_t usw.

 

[black90]

Bei signed gibt es immer overflows, wenn es möglich ist muss man davon ausgehen.
Der Trick sind halt solche geschichten oben, wo dann nur 15 Bit statt 16 Bit betrachtet werden.
Das Vorzeichen muss dennoch manuell gesetzt werden.

 

[Miuwa]

@black: In dem Fall eben nicht zwangsweise: ein short hat normalerweise 16 ein int 32 bit. Wenn eine Zahl ursprünglich in eine short variable gepasst hat, dann kann ich sie nach der automatischen "integral promotion" um mindestens 16bit shiften bevor ich einen overflow bekomme.

 

[aroxx]

Warum? Nutzt du C oder C++? In C++ gibts nämlich für fixed size bitset und sonst vector<bool>.
Geht es um speed oder um platz? uint16_t.

Es geht um beides. Speed hängt nämlich in dem Fall ziemlich vom Platz ab.
Wenn ich ein bitset anlege hab ich Angst, dass es mir das alignment zerstört und ich damit weniger performance bekomme

@black90 sehr sehr gute Idee. Ich benchmarke das morgen oder spätestens am Montag mal!

 

[Miuwa]

Mal rein aus Interesse: Wofür brauchst du das rotate eigentlich? Sprich was ist dann die nächste Aktion. Und hast du mal getestet, wieviel langsamer eine Version mit einem uint8_t pro Datum ist?

 

[wusu]

Welches Problem willst du eigentlich loesen? Welche Architektur/Sprache? Ich vermute x-y Problem ...
Shifts/Rotates auf signed ints machen meiner Meinung nach keinen Sinn.
Rotate kannst du dir selber in C++ stricken:

template <typename T>
T rotate_right(T value, unsigned int shifts)
{
	const unsigned int steps = shifts % (sizeof(T)*CHAR_BIT); // undefined if shifts >= sizeof(T)*CHAR_BIT -> modulo required
	return (value << (sizeof(T)*CHAR_BIT - steps)) | (value >> steps);
}

template <typename T>
T rotate_left(T value, unsigned int shifts)
{
	const unsigned int steps = shifts % (sizeof(T)*CHAR_BIT); // undefined if shifts >= sizeof(T)*CHAR_BIT -> modulo required
	return (value >> (sizeof(T)*CHAR_BIT - steps)) | (value << steps);
}

Wenn du dein Vorzeichen unbedingt behalten musst, fuege beide nach der Rotation zusammen:

short result = (value & 0x8000) | (rotated & 0x7FFF);

Ansonsten schau dir diese x86-Befehle an, vielleicht hilfts ja: rol/ror rcl/rcr shl/shr sal/sar.

 

[goldmomo]

Hi,

der Compiler optimiert deinen Code sowieso für das Target (wenn eingeschaltet).
Ob er dann ein ror/rol/asr/lsr/lsl/.. oder bitfield-opcodes nimmt kannst du dir im generierten Code ansehen.
Z.b. wird er bei deinen modulo 8 bestimmt keine Division machen und sich den Rest holen, sondern wohl eher ein and mit 7 einfügen.

Würde mir hier den Kopf nicht zerbrechen, die wenigen Operationen sind bestimmt keine bedeutender Faktor der Gesamtperformance.

 

[black90]

Jup, Performance Killer finden sich in Schleifen :>
Aber manchmal tut man Dinge einfach weil man sie tun kann...

Hab heute die Operatoren in Ruby umgeschrieben, nur um dann zu merken dass es so sinnlos war dass es in Java und C gar nicht geht Oder?

 

[Miuwa]

Naja, ich sag mal so: Wenn man über große Arrays iteriert, aber jeweils nur einfache Operationen durchführt, dann kann sich so eine 2,5:1 Kompression schon bemerkbar machen. Ich will doch mal stark hoffen, dass niemand zu solchen Optimierungen greift ohne vorher zu verifizieren, dass damit tatsächlich zumindest EIN Performanceproblem gelöst wird.

 

[Magogan]

value = (value >> 3) | ((value & 0x7) << 12);

Du solltest aber mit unsigned short arbeiten, wenn du das höchste Bit nicht in jedem Fall auf 0 setzt. Ich bin mir nicht sicher, ob das bei short mit Einsen aufgefüllt wird, wenn du nach rechts schiebst und das höchste Bit 1 ist.

Overflows bei Shifts haben kein undefiniertes Verhalten, sondern sind klar definiert. 1025 << 12 ergibt 4096 (bei 16 Bit), da die unteren 16-12=4 Bit 0001 sind. Probleme gibt es nur, wenn die Shift Amount (also um wie viel geschoben wird) größer oder gleich der Bitbreite der geschobenen Zahl ist. Das ist dann tatsächlich undefiniertes Verhalten.

 

[Miuwa]

Overflows bei Shifts haben kein undefiniertes Verhalten, sondern sind klar definiert. [...] Probleme gibt es nur, wenn die Shift Amount (also um wie viel geschoben wird) größer oder gleich der Bitbreite der geschobenen Zahl ist. Das ist dann tatsächlich undefiniertes Verhalten.

Nope, das ist (für vorzeichenbehaftete Typen) nicht die einzige Anforderung.

Aus dem aktuellen Working Draft des C++ Standards (5.8 Shift operators [expr.shift]):

2.The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned
type, [...]. Otherwise, if E1 has a signed type and non-negative value, and E1×2E2 is representable
in the corresponding unsigned type of the result type, then that value, converted to the result type, is the
resulting value; otherwise, the behavior is undefined.

Das Verhalten von x<<y ist also undefiniert, falls der Wert von x*2^y zu groß ist um ihn mit der vorzeichenlosen Version, des "Ergebnistyps" darzustellen (also genau das, was ich persönlich als overflow bezeichnen würde - im Standard kommt der Begriff overflow meines Wissens nicht vor). Ein left shift eines negativen x ist immer UB.

Wichtig für das konkrete Beispiel ist aber auch der Absatz darüber:

The operands shall be of integral or unscoped enumeration type and integral promotions are performed. The type of the result is that of the promoted left operand.

Was uns zu 4.5 Integral promotions [conv.prom] führt

1 A prvalue of an integer type other than [...] whose integer conversion
rank (4.13) is less than the rank of int can be converted to a prvalue of type int if int can represent all
the values of the source type; [...]

D.h. vor dem shift wird der linke operand (hier x) erstmal zu einem int promoted.

Ebenfalls relevant (4.7 Integral conversions [conv.integral])

3. If the destination type is signed, the value is unchanged if it can be represented in the destination type;
otherwise, the value is implementation-defined.

Bei

short y= x << z;

passiert also folgendes (falls x ein short ist und int und short 32 bzw. 16Bit-Datentypen sind):
- x wird zu einem int promoted
- die Bits werden um z Stellen nach links geshiftet.
- falls x*2^z > 2^32-1 triit UB auf.
- falls 2^32-1 >= x*2^z > 2^31-1 ist das Ergebnis Implementation Defined (also nicht UB aber trotzdem nicht unbedingt portabel)
- Das Ergebnis wird in einen short konvertiert und y zugewiesen.
- Falls x*2^z > 2^15-1, ist das Ergebnis Implementation Defined

Soweit ich das sagen kann verhält sich deine Lösung immer Korrekt und (dank integral promotion) vermutlich auch die anderen Vorschläge, aber ich denke wir sind uns alle einig, dass Bitmanipulationen besser auf vorzeichlosen Datentypen mit fester Breite durchgeführt werden sollten (hier also uin16_t).