Bit weise schieben im Byte Array ( shift carry )

[Moritz G. (mbydq2)]

Ich habe ein ähnliches Problem wie: 
Beitrag "Bit weise schieben im Array shift"
Bei mir ist aber nicht nur das erste Byte besetzt.
könnte man es so:

inline void schiebenueberbyte(*array[UnteresByte]){
asm("
push r0\n
push r1\n
loadword r0,r25\n
shiftleft r0\n
slc r1\n
inc r25\n
clear r0\n
adc r26,r0\n
storebyte r1,r25\n
pop r1\n
pop r0
");}

machen?
Dann müsste ich nur noch:

for(z=sizeof(array);--z;) schiebenueberbyte(&array[z-1];

machen.
Gibt es einen Befehl der das Carrybit addiert, oder muss man das machen 
wie ich es oben versuche?

[Klaus W. (mfgkw)]

Gibt es einen guten Grund, das nicht vom C-Compiler machen zu lassen? 
Also eine uint16_t oder uint32_t zu nehmen und mit << zu schieben?

[Moritz G. (mbydq2)]

Klaus Wachtler schrieb:
> Gibt es einen guten Grund, das nicht vom C-Compiler machen zu lassen?
> Also eine uint16_t oder uint32_t zu nehmen und mit << zu schieben?

Also einen cast von einem char Array zu einem int array und dann 
schieben?
Auf die Art kann ich natürlich nur von 0 zu 1, von 2 zu 3, von 4 zu 5, 
u.s.w. schieben.

Ich habe mich ein wenig in inline-asm eingelesen und herausgefunden, 
dass man es im Grunde schon so "clear r0; adc r26,r0" macht, nur dass 
man r1 nimmt und es

__zero_reg__

 nennt und nie für etwas anderes als NULL benutzt. Für Adressen nimmt 
man aber Post-Increment.
Das push und pop macht man nicht, sondern überlässt es dem Compiler die 
Register auszuwählen.
nach meinem aktuellen Wissensstand müsste es so aussehen:
inline void schiebenueberbyte(char* array){
asm(
"ld %A1,%a0+\n"
"ld %B1,%a0\n"
"lsl %A1\n"
"rol %B1\n"
"st %B1,%a0\n"
:"e" (array):
);
}

[Moritz G. (mbydq2)]

Ich habe zwar nicht verstanden was ich hier mache und weiß nicht ob es 
funktioniert, aber so:

void schiebenueberbyte(char* array){
//char temp1, temp2;
__asm(
"ld __tmp_reg__,%a0+\n"
"lsl __tmp_reg__\n"
"ld __tmp_reg__,%a0\n"
"rol __tmp_reg__\n"
"st %a0,__tmp_reg__\n"
://keine Variable verändert.
:"e"(array)
:"memory"
);
}

beschwert sich der Compiler nicht.
Ich hätte ja gerne verstanden wie man Register weder für Input noch für 
Output benutzt ohne sie fest zu vergeben, aber ich checke das constrain 
Zeug nicht. Glücklicherweise brauchte ich eh nur eines und da nimmt man 
wohl eh immer ein festes, das man nicht einmal zur cloberliste 
hinzufügen muss.

[Peter D. (peda)]

uint8_t array[SIZE];

uint8_t shift_left( uint8_t bit_in )
{
  uint8_t bit_out = array[SIZE-1] >> 7; // last carry was shifted out

  for( uint8_t i = SIZE-1;; i-- ){
    array[i] <<= 1;
    if( i == 0 )
      break;
    if( array[i-1] & 0x80 )
      array[i] |= 1;                  // insert carry
  }
  if( bit_in )
    array[0] |= 1;
  return bit_out;
}

Peter

[Johann L. (gjlayde)]

Moritz G. schrieb:
> Ich habe zwar nicht verstanden was ich hier mache und weiß nicht ob es
> funktioniert, aber so:
> ...
> beschwert sich der Compiler nicht.
> Ich hätte ja gerne verstanden wie man Register weder für Input noch für
> Output benutzt ohne sie fest zu vergeben, aber ich checke das constrain
> Zeug nicht.

Geht es dir darum, irgendwie ein Array zu schieben oder geht es dir 
darum, Inline Assembler besser zu verstehen?

In deinem Fall wird array verändert, die richtigen Constraints sind also

asm ("..." : "+e" (array) :: "memory);

bei

asm ("..." : "e" (array) :: "memory);

kann ich mir nicht vorstellen, daß der Compiler nicht meckert, es sei 
denn du hast geschrieben

asm ("..." :: "e" (array)

was aber nicht korrekt ist, weil array wie gesagt verändert wird.

Zudem kannst ein ganzes Array so nicht schieben, weil von einem 
Inline-Assembler Schnippel bis zum nächsten Carry nicht überlebt.

[Moritz G. (mbydq2)]

@ Peter Dannegger Beitrag #2383987:

Danke Peter.
Ja so geht es auch, aber es sieht im Vergleich zum ASM so kompliziert 
aus. Vielleicht macht der Compiler das selbe daraus?

[Peter D. (peda)]

Moritz G. schrieb:
> Ja so geht es auch, aber es sieht im Vergleich zum ASM so kompliziert
> aus.

Aber dafür ist es verstehbar und portabel.
Es läuft auch mit jedem anderen MC bzw. Compiler.

Wenn Du nicht wirklich den letzten CPU-Zyklus ausquetschen mußt, würde 
ich das vorziehen.

Als ich mit C angefangen hab, wollte ich auch C mit Assembler mixen.
Schnell habe ich aber gemerkt, das ist Unsinn, man kann alles in C 
schreiben.


Peter

[Karl H. (kbuchegg)]

Moritz G. schrieb:
> @ Peter Dannegger Beitrag #2383987:
>
> Danke Peter.
> Ja so geht es auch, aber es sieht im Vergleich zum ASM so kompliziert
> aus.

Dafür dürfte es im Gegensatz zu deiner Lösung aber funktionieren.

Wenn man in einem Array schiebt, würde ich mal als Minimum irgendeine 
Form einer SChleife erwarten, denn irgendwie müssen ja die Bits von 
einem Byte des Arrays zum nächsten kommen und das hängt dann wieder 
davon ab, wieviele Bytes im Array sind.

In deinem Assemblercode kann ich aber nix entdecken, was auch nur 
irgendwie einer Schleife gleich kommt.

Und das hier
> Ich habe zwar nicht verstanden was ich hier mache und weiß
> nicht ob es funktioniert
spricht ja wohl für sich.

[Moritz G. (mbydq2)]

Johann L. schrieb:
> Geht es dir darum, irgendwie ein Array zu schieben oder geht es dir
> darum, Inline Assembler besser zu verstehen?

Beides

> In deinem Fall wird array verändert, die richtigen Constraints sind also

asm ("..." : "+e" (array) :: "memory);

> bei

asm ("..." : "e" (array) :: "memory);

> kann ich mir nicht vorstellen, daß der Compiler nicht meckert, es sei
> denn du hast geschrieben

asm ("..." :: "e" (array)

> was aber nicht korrekt ist, weil array wie gesagt verändert wird.

Aber ich habe den Pointer doch gar nicht verändern wollen. Dass er 
verändert wird ist mir egal. Ich will, dass der Compiler die Adresse in 
z.B. das Y-Register legt. Er soll sie aber nicht retten und auch die 
anderen Register sind mir egal. Ich will ja nur den Array an sich 
verändern nicht den Pointer.
Rein geht also der Pointer. Verändert wird der Pointer, Speicher und ein 
zusätzliches Register. Raus geht eigentlich gar nichts, also keine der 
Variablen der Funktion (void).

> Zudem kannst ein ganzes Array so nicht schieben, weil von einem
> Inline-Assembler Schnippel bis zum nächsten Carry nicht überlebt.

Das muss es auch nicht. Ich verändere immer nur das obere Byte und fange 
hinten/oben an. Der ASM-Schnipsel soll nur das Byte bei array[1] 
schieben, sonst nichts.

[Moritz G. (mbydq2)]

Karl Heinz Buchegger schrieb:

> Wenn man in einem Array schiebt, würde ich mal als Minimum irgendeine
> Form einer SChleife erwarten, denn irgendwie müssen ja die Bits von
> einem Byte des Arrays zum nächsten kommen und das hängt dann wieder
> davon ab, wieviele Bytes im Array sind.
> In deinem Assemblercode kann ich aber nix entdecken, was auch nur
> irgendwie einer Schleife gleich kommt.

Die Schleife ist extern. Ich hoffe Sie haben nicht zu lange gesucht.

> Und das hier
>> Ich habe zwar nicht verstanden was ich hier mache und weiß
>> nicht ob es funktioniert
> spricht ja wohl für sich.

Genau daher benutzt man sogar Schriftsprache.

[Karl H. (kbuchegg)]

Moritz G. schrieb:


> Beides
> Das muss es auch nicht. Ich verändere immer nur das obere Byte und fange
> hinten/oben an. Der ASM-Schnipsel soll nur das Byte bei array[1]
> schieben, sonst nichts.

Vielleicht solltest du erst mal die Aufgabenstellung genauer definieren, 
ehe da nach untauglichen Lösungen gesucht wird.

Wie Peter schon sagte: In den meisten Fällen kommt man mit C alleine 
wunderbar über die Runden. Sofern man C kann, natürlich. Die paar 
Prozentpunkte Performance, die man möglicherweise auf der Strecke lässt, 
spielen keine Rolle.

[Karl H. (kbuchegg)]

Moritz G. schrieb:
> Karl Heinz Buchegger schrieb:
>
>> Wenn man in einem Array schiebt, würde ich mal als Minimum irgendeine
>> Form einer SChleife erwarten, denn irgendwie müssen ja die Bits von
>> einem Byte des Arrays zum nächsten kommen und das hängt dann wieder
>> davon ab, wieviele Bytes im Array sind.
>> In deinem Assemblercode kann ich aber nix entdecken, was auch nur
>> irgendwie einer Schleife gleich kommt.
>
> Die Schleife ist extern.

In Peters Lösung aber nicht.
Und das ist der Unterschied. Seine Lösung schiebt das komplette Array um 
1 Bit.

Und daher sieht seine Lösung dann eben auch ein wenig umfangreicher aus.

[Moritz G. (mbydq2)]

Ja stimmt schon:
1. Mit C geht es, auch wenn es etwas umständlicher vom Algorithmus ist.
2. Ich habe reichlich Zyklen zur Verfügung.
Ich will eigentlich eine Polynomdivision für einen CRC-10 auf 40 bis 60 
bit machen. Wenn es da keine andere Methode gibt müsste ich eben die 6 
Byte ~48 mal schieben. Bei 280 mal dachte ich es würde sich lohnen über 
eine Variante nachzudenken, bei der nicht mit maskieren gearbeitet wird 
sondern die vorhandene Hardware explizit genutzt wird.
Vielleicht ist der Compiler ja schlau genug zu verstehen, dass

array[i] <<= 1;
if( i == 0 ) break;
if( array[i-1] & 0x80 ) array[i] |= 1;}

nur ein "lsl" und "rol" ist und nimmt die Verzweigungen heraus.
Neben der Latenz ist es auch eine Persönlichkeitssache: Ich kann es 
nicht ausstehen wenn es besser ginge, auch wenn ich noch 1000 Zyklen 
über habe.

[Johann L. (gjlayde)]

Moritz G. schrieb:

> Ich will eigentlich eine Polynomdivision für einen CRC-10 auf 40 bis 60
> bit machen. Wenn es da keine andere Methode gibt müsste ich eben die 6
> Byte ~48 mal schieben.

Modulare Arithmetik über einem endlichen Körper oder über Z/nZ macht man 
eleganter und auch effizienter folgendermassen:

 c' = a · b
 c  = c' mod n

ist teuer, denn c' hat die doppelte Bitbreite wie n, und zudem ist 
Polynomdivision bzw. Division mit Rest teuer und nervig zu 
implementieren.

Stattdessen wird die Basisarithmetik so aufgemöbelt, daß sie direkt

 c = a · b mod n

berechnet. Für eine Addition kann das zB so aussehen:

 c = a + b
 if c >= n then c := c-n

oder wenn es in Charakteristik 2 ist (zB Polynomring über Z/2Z wie bei 
CRC üblich) ist einfach

 c = a + b = a XOR b

Fur die Multiplikation zweier Polynome im Polynomring genügt es, mit X 
(der unabhängigen Variablen) oder mit einer Konstante aus dem Ring 
multiplizieren zu können.

Multiplikation mit X ist einfach:

$$\begin{align} X \cdot (a_{n-1}&X^{n-1} + a_{n-2}X^{n-2} + \cdots) \mod p(X) \\ &\equiv a_{n-1}X^n + a_{n-2}X^{n-1} + \cdots \mod p(X) \\ &\equiv a_{n-1}X^n + a_{n-2}X^{n-1} + \cdots -a_{n-1}p(X) \mod p(X)\\ &\equiv a_{n-1}X^n + a_{n-2}X^{n-1} + \cdots -a_{n-1}p(X) \end{align}$$

Das Polynom in der untersten Zeile ist normiert falls p(X) normiert ist 
denn der Term bei a_{n-1} hebt sich weg. Somit beschränkt sich die 
Multiplikation mit X darauf, ein vielfaches des Basispolynoms zu 
subtrahieren. Ditto für die Multiplikation mit X^m, und damit erhält man 
in der Polynom-Arithmetik immer normierte Ergebnisse und braucht keine 
Polynomdivision — es sei denn mann will wirklich Dividieren im 
Polynomring.

For die Skalare aus dem Grundbereich macht man es analog; auch da brauch 
es keine Division mit Rest um a · b oder a +/- b zu berechnen; und falls 
der Grundbereich Z/2Z ist — also z.B. Bits wie bei CRC üblich — sind die 
Basisoperationen trivial.

[Moritz G. (mbydq2)]

Moritz G. schrieb:

> Vielleicht ist der Compiler ja schlau genug zu verstehen, dass

array[i] <<= 1;
if( array[i-1] & 0x80 ) array[i] |= 1;

> nur ein "lsl" und "rol" ist und nimmt die Verzweigungen heraus.

Nein, das ist/tut er nicht.
Ich habe mir das Compilat (*.s) angeguckt und das:

"lsl %0\n"
"tst %1\n"
"brge .L2\n"
"ori %0,lo8(1)\n"
".L2:\n"

gefunden.
Besser wäre aber:

"lsl %1\n"
"rol %0\n"

Zugegeben es ist eigentlich egal, weil ich genug Zeit habe und der 
Prozessor eh nicht OoO ist, aber diese eine Funktion macht einen 
Großteil des Programms aus, da sind -50% schon bedenkenswert.

[Moritz G. (mbydq2)]

Die Lösung ist lächerlich einfach:
(ohne Schleife)
unsigned char A[6];

__asm(
 "lsl %0\n"
 "rol %1\n"
 "rol %2\n"
 "rol %3\n"
 "rol %4\n"
 "rol %5\n"
 :"+r" (uc6_A[0]), "+r" (uc6_A[1]), "+r" (uc6_A[2]), "+r" (uc6_A[3]), "+r" (uc6_A[4]), "+r" (uc6_A[5])
 :);

So ist es vier mal so schnell verglichen mit der Compilerversion mit 
Loop-Unrolling.
Hier ist ASM überlegen, da C einfach keinen guten Schiebebefehl hat.

[Jörg W. (dl8dtl) (Moderator)]

Moritz G. schrieb:
> Hier ist ASM überlegen, da C einfach keinen guten Schiebebefehl hat.

C braucht keinen "guten" Schiebebefehl, es genügt völlig, dass es
einen Schiebebefehl überhaupt hat.

Dass ein C-Compiler deshalb nicht jeden `corner case' optimieren
kann, ist eine andere Frage, aber das liegt nicht an der Sprache
selbst, die das nicht hergeben würde, sondern nur daran, wie der
Compiler tatsächlich implementiert ist.