Effizientes Zero-Stuffing in C

[SPI (Gast)]

Hallo Leute,

ich habe hier eine Anwendung wo ich im uC intern ein 16-Bit Datenwort 
habe, welches in ein 32-Bit Wort umgewandelt werden muss, allerdings 
gefüllt mit einem 0-Bit an jeder zweiten Stelle.
Hintergrund ist der, dass ich an einer SPI ein Modul angeschlossen habe, 
welches allerdings nur auf jede zweite Flanke der SPI clock das Bit 
aufnehmen kann.

Also wenn ich 1101 0101 1111 0110 habe, sollte daraus ganz einfach dann
10100010 00100010 10101010 00101000 werden.

Wie kann man so etwas möglichst Effizient umsetzen (abgesehen von den 
üblichen Bit-Shifting und Verknüpfungsmethoden)?

Danke

[MaWin (Gast)]

Man könnte 4 bytes aus einer 16er Tabelle entnehmen, indiziert mit 
jeweils einem nibble, oder 2 Worte aus einer 256er Tabelle indiziert mit 
jeweils einem byte.

[(prx) A. K. (prx)]

SPI schrieb:
> an einer SPI ein Modul angeschlossen habe, welches allerdings nur auf
> jede zweite Flanke der SPI clock das Bit aufnehmen kann.

Ist das so dokumentiert?

[Jens M. (schuchkleisser)]

Machts was aus wenn das Bit zweimal gleich übertragen wird?
Dann evtl. eine Hardware nutzen.
Oder: einfach eine Funktion mit 8 ifs die 8 bit bekommt und 16 bit 
ausspuckt.

Sind je nach Controller auch nur ~25 Befehle in Maschinensprache.

[Peter D. (peda)]

SPI schrieb:
> welches allerdings nur auf jede zweite Flanke der SPI clock das Bit
> aufnehmen kann.

Das ist doch bei SPI immer so, oder meintest Du, an jeder 4. Flanke.
Man könnte auch mit einem RC-Glied und EXOR aus jeder Flanke einen Puls 
machen.

[A. S. (Gast)]

Das sind maximal 16 if. Egal wie formuliert.

uint32_t d=0;
uint16_t s=...;

   if(s&1) d|=1;
   if(s&2) d|=2;
   ... 
   if(s&0x8000) d|= 0x40000000)

oder

   d= (s&1)<<0 + (s&2)<<2 + ... (s&0x8000)<<30;

oder 

   uint16_t m=0x8000;

   while(m) {d<<=1; if(s&m) d++; m>>=1;}

//falls die 0 davor soll. Sonst entsprechend die Versionen drehen!

probier da einfach verschiedene intuitive Varianten und schaue, ob es 
schnell genug ist. Manchmal erkennt der Compiler, was zu tun ist. Erst 
wenn da ein Flaschenhals ist, kümmere Dich darum.

Gerade die erste Version kann je nach Prozessor in 1-2 Takten je Bit 
umgesetzt werden.

[Christopher B. (chrimbo)]

A. S. schrieb:

if(s&2) d|=2;

typo:

if(s&2) d|=4;

[Axel S. (a-za-z0-9)]

(prx) A. K. schrieb:
> SPI schrieb:
>> an einer SPI ein Modul angeschlossen habe, welches allerdings nur auf
>> jede zweite Flanke der SPI clock das Bit aufnehmen kann.
>
> Ist das so dokumentiert?

Und vor allem: wie synchronisiert man das wieder, wenn es mal aus dem 
Tritt gekommen ist?

[SPI (Gast)]

(prx) A. K. schrieb:
> SPI schrieb:
>> an einer SPI ein Modul angeschlossen habe, welches allerdings nur auf
>> jede zweite Flanke der SPI clock das Bit aufnehmen kann.
>
> Ist das so dokumentiert?

Ich habe hier ein relativ spezielles Konstrukt.
Quasi eine SPI die selber im Slave-Mode arbeitet und mit genau 6.144 MHz 
getaktet wird,  weil ich ein Stereo PDM-Mems Mikrofon-Signal samplen 
will.
Die Mikrofone kriegen aber nur eine 3.072 MHz clock (diese pushen 
jeweils aber auf steigende und fallende Flanke raus). Also muss ich die 
SPI doppelt so schnell takten.
gleichzeitig will ich aus dem SPI Modul ein I2S Signal rausgeben, 
welches seine Bits aber zu der 3.072 MHz clock referenziert haben soll. 
Also pusht die SPI doppelt so viele Bits raus wie nötig.


Danke für euren Support, ich werde mich mal dran versuchen.

[Wolfgang (Gast)]

SPI schrieb:
> Wie kann man so etwas möglichst Effizient umsetzen

Was ist dein Kriterium für Effizienz?
Speicherplatz, Rechenzeit, Zeilenzahl Quellcode ...?

[Yalu X. (yalu) (Moderator)]

SPI schrieb:
> uC

Dann geht das mit zwei einfachen Zuweisungen:

OUTPORT = data16;
data32  = INPORT;

Dazu müssen die zu INPORT und OUTPORT gehörenden I/O-Pins extern wie
folgt verschaltet werden:

               INPORT
0 oooooooooooooooooooooooooooooooo 31
  ┴│┴│┴│┴│┴│┴│┴│┴│┴│┴│┴│┴│┴│┴│┴│┴│
  ┌┘ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
  │┌─┘ │ │ │ │ │ │ │ │ │ │ │ │ │ │
  ││┌──┘ │ │ │ │ │ │ │ │ │ │ │ │ │
  │││┌───┘ │ │ │ │ │ │ │ │ │ │ │ │
  ││││┌────┘ │ │ │ │ │ │ │ │ │ │ │
  │││││┌─────┘ │ │ │ │ │ │ │ │ │ │
  ││││││┌──────┘ │ │ │ │ │ │ │ │ │
  │││││││┌───────┘ │ │ │ │ │ │ │ │
  ││││││││┌────────┘ │ │ │ │ │ │ │
  │││││││││┌─────────┘ │ │ │ │ │ │
  ││││││││││┌──────────┘ │ │ │ │ │
  │││││││││││┌───────────┘ │ │ │ │
  ││││││││││││┌────────────┘ │ │ │
  │││││││││││││┌─────────────┘ │ │
  ││││││││││││││┌──────────────┘ │
  │││││││││││││││┌───────────────┘
  ││││││││││││││││
0 oooooooooooooooo 15
       OUTPORT

Falls dein µC nicht die benötigten 48 I/O-Pins hat, kannst du die
Konvertierung auch in kleineren Häppchen, bspw. byteweise vornehmen.
Das ist immer noch einfacher und schneller, als die Daten bitweise
zu bearbeiten.

[Jens M. (schuchkleisser)]

Man kann auch den RB1632 von RubeGoldbergSemiconductors kaufen, gut, 
momentan schwer erhältlich, aber der wurde speziell dafür entwickelt. 
Das reduziert das ganze auf ein IC, angesteuert mit /Rd, /Wr, 16 DI und 
32 DO, kann 5 oder 3,3V bei bis zu 33MHz.
Ist im TQFP48 erhältlich, also relativ platzsparend.

Oder man baut die Funktion nach, z.B. mit 6 Schieberegistern, I²C- oder 
SPI-Portextendern oder (so vorhanden) 4 Portlatches aus der 
74er-Familie.

[Fpgakuechle K. (Gast)]

Jens M. schrieb:

> Oder man baut die Funktion nach, z.B. mit 6 Schieberegistern, I²C- oder
> SPI-Portextendern oder (so vorhanden) 4 Portlatches aus der
> 74er-Familie.

Oder mit einem CPLD.

[Hannes J. (Firma: _⌨_) (pnuebergang)]

Zero-Stuffing ist was anderes. Das hier ist ein Spezialfall (x := 0 oder 
y: = 0) von "Morton numbers" bzw. eigentlich "Morton code".

Die klassischen Algorithmen findet man ab hier
https://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious 
Alle vier Algorithmen lassen sich unter der Vorgabe dass z.B. y = 0 ist 
noch vereinfachen.

Für mehr Spaß gibt es auch Erweiterungen auf 3D, z.B. 
https://www.forceflow.be/2013/10/07/morton-encodingdecoding-through-bit-interleaving-implementations/

[A. S. (Gast)]

Wieso eigentlich 16 Bit Eingang? SPI-Midule sind doch oft 8-bittig 
organisiert, so dass 16er oder 256er Tabellen sehr effektiv sein 
dürften.

[900ss (900ss)]

Ich würde es auch, je nach Laufzeit/Speichplatz Bedingungen über LUTs 
lösen. Wenn viel Platz ist, große LUTs, das spart Laufzeit.

[Minimalist (Gast)]

SPI schrieb:
> ich habe hier eine Anwendung wo ich im uC intern ein 16-Bit Datenwort
> habe,

Welcher uC denn genau? Denn die modernen Attiny bzw die XMegas könnten 
das mit eventsystem und CCL höchstwahrscheinlich in Hardware.

[M. Н. (Gast)]

Yalu X. schrieb:
> SPI schrieb:
>> uC
>
> Dann geht das mit zwei einfachen Zuweisungen:

Je nach uC und wie die interne Bus-Matrix zu den GPIOs aussieht, kann 
das auch mal in die Hose gehen und deutlich langsamer sein. Die 
Zugriffszeiten auf GPIOs sind teilweise sehr hoch.

[Jason (Gast)]

M. H. schrieb:
> Yalu X. schrieb:
>> SPI schrieb:
>>> uC
>>
>> Dann geht das mit zwei einfachen Zuweisungen:
>
> Je nach uC und wie die interne Bus-Matrix zu den GPIOs aussieht, kann
> das auch mal in die Hose gehen und deutlich langsamer sein. Die
> Zugriffszeiten auf GPIOs sind teilweise sehr hoch.

Hast Du ein Beispiel für einen µC bei dem die Zeiten sehr hoch sind?

[Nils (Gast)]

Kommt auf die CPU drauf an.

Viele CPUs haben heutzutage Cryptographie Beschleuniger oder 
Befehlssätze hierfür. Ist das bei Dir der Fall, dann schau Dir mal die 
Galois multiplier an.

Wenn Du eine Zahl mit sich selbst durch einen Galois Multiplier 
schickst, dann bekommst Du exakt das Ergebniss, welches Du brauchst.

[SPI (Gast)]

Jens M. schrieb:
> RubeGoldbergSemiconductors

Die Audio-Sample

A. S. schrieb:
> Wieso eigentlich 16 Bit Eingang? SPI-Midule sind doch oft 8-bittig
> organisiert, so dass 16er oder 256er Tabellen sehr effektiv sein
> dürften.



Das SPI Modul arbeitet nativ auf 32-Bit basis.
Ich werde jetzt den Ansatz mit der LUT nehmen.
Ram und Rechenleistung habe ich eh genügend, ist ein relativ dicker uC. 
Dann ein uint16_t Array mit 256 Einträgen.

[Jason (Gast)]

Jason schrieb:
> M. H. schrieb:
>> Yalu X. schrieb:
>>> SPI schrieb:
>>>> uC
>>>
>>> Dann geht das mit zwei einfachen Zuweisungen:
>>
>> Je nach uC und wie die interne Bus-Matrix zu den GPIOs aussieht, kann
>> das auch mal in die Hose gehen und deutlich langsamer sein. Die
>> Zugriffszeiten auf GPIOs sind teilweise sehr hoch.
>
> Hast Du ein Beispiel für einen µC bei dem die Zeiten sehr hoch sind?

War schon klar, dass da mal wieder nichts kommt. War also nur dummes 
Geschwätz.

[(prx) A. K. (prx)]

Die alten LPC2000 beispielsweise waren bei GPIO nicht sonderlich 
schnell. Aber sowas kann man auch beim LUT-Verfahren erleben. Wenn man 
die Tables im ROM lässt, handelt man sich u.U. einige Waitstates ein.

[Ben B. (Firma: Funkenflug Industries) (stromkraft)]

Auf was für einen Prozessor soll das laufen?

Look-up-Tables sind halt teilweise unschön weil man zuerst die Positon 
in der Tabelle berechnen muß und dann muß auch noch aus dem Speicher 
gelesen werden. Multiplikation mit 2 ist zum Glück auch auf einem 
billigst-Controller schnell gemacht (ein Bitshift nach links und 
fertig), aber eine moderne Desktop-CPU ist evtl. mit der ganzen 
Operation aus Bitshifts schneller fertig als wenn sie noch irgendwas aus 
dem Speicher laden muß. Vor allem wenn die Tabelle gerade nicht im Cache 
liegt.

[Stefan F. (Gast)]

Ben B. schrieb:
> Look-up-Tables sind halt teilweise unschön weil man zuerst die Positon
> in der Tabelle berechnen muß und dann muß auch noch aus dem Speicher
> gelesen werden.

Vielleicht ein ein switch/case mit 16 Einträgen schneller

[(prx) A. K. (prx)]

Sinnloses Stochern im Nebel, wenn man den konkreten Prozessor nicht 
kennt.

[900ss (900ss)]

Ben B. schrieb:
> die Positon in der Tabelle berechnen muß

Was willst du da berechnen in diesem Fall? Genau in diesem Fall braucht 
man das nicht. Und deshalb ist es auch schnell wenn der LUT-Zugriff 
nicht aus den schon erwähnten Gründen alles kaputt macht.

[Frank M. (ukw) (Moderator)]

SPI schrieb:
> Ram und Rechenleistung habe ich eh genügend, ist ein relativ dicker uC.

Gut zu wissen, dass es ein "relativ dicker uC" ist und Du den konkret 
nicht nennen willst. Dann können wir ja noch schön weiter die Glaskugel 
bemühen.

[rbx (Gast)]

Ben B. schrieb:
> Multiplikation mit 2 ist zum Glück auch auf einem
> billigst-Controller schnell gemacht

(+1)
Es ist auch netter, wenn man schon eine funktionierende Programmvariante 
hat, als gewissermaßen schon mit Optimieren anzufangen, bevor 
irgendetwas läuft.
Die sequentielle Herangehensweise ist recht naheliegend, wie jetzt genau 
(und ob überhaupt) hängt eben auch von der konkreten Hardware ab.

SPI schrieb:
> Wie kann man so etwas möglichst Effizient umsetzen (abgesehen von den
> üblichen Bit-Shifting und Verknüpfungsmethoden)?

..also zeig mal ein Programm und erzähl was über die konkrete 
Hardware-Situation, und dann sehen wir weiter ;)

[SPI (Gast)]

Frank M. schrieb:
> SPI schrieb:
>> Ram und Rechenleistung habe ich eh genügend, ist ein relativ dicker uC.
>
> Gut zu wissen, dass es ein "relativ dicker uC" ist und Du den konkret
> nicht nennen willst. Dann können wir ja noch schön weiter die Glaskugel
> bemühen.

Ist die Aurix TC3xx Plattform

[Klaus W. (mfgkw)]

900ss D. schrieb:
> Was willst du da berechnen in diesem Fall? Genau in diesem Fall braucht
> man das nicht. Und deshalb ist es auch schnell wenn der LUT-Zugriff
> nicht aus den schon erwähnten Gründen alles kaputt macht.

Ich denke, er meinte daß der vom Compiler generierte Code ja aus der 
Anfangsadresse des Feldes und dem uint8_t als Index die Adresse der 
resultierenden uint16_t im Feld berechnen muß.

     erg16 = meineLUT[aktuelleuint8];

Das verbirgt ja die Berechnung meineLUT+aktuelleuint8 (glücklicherweise 
ist die Elementgröße 1, sonst wäre die Berechnung noch viel schlimmer).

[Johann L. (gjlayde)]

SPI schrieb:
> Ist die Aurix TC3xx Plattform

TriCore hat ne eigene Instruktion für die gesuchte Operation (und die 
Umkehrung): BMERGE und BSPLIT.

[Ben B. (Firma: Funkenflug Industries) (stromkraft)]

> Was willst du da berechnen in diesem Fall?
> Genau in diesem Fall braucht man das nicht.
Nur weil Du das nicht brauchst, heißt das nicht, daß die CPU das nicht 
braucht. Sorry, aber typische Antwort von Fachidioten, die evtl. die 
weltbesten Programmierer sind, aber keine Ahnung mehr davon haben, wie 
das Ganze technisch-elementar funktioniert.

Edit: Und denen das leider auch scheißegal ist. Jedenfalls solange der 
Compiler alle ihre Probleme löst.

[900ss (900ss)]

Ben B. schrieb:
> Nur weil Du das nicht brauchst, heißt das nicht, daß die CPU das nicht
> braucht.

Genau das ist der feine Unterschied. Ich(!) brauche für die Berechnung 
keinen extra Code schreiben. Das macht der Compiler für mich. Das eine 
Berechnung (verborgen) stattfindet, ist schon klar und auch dass die 
Laufzeit bedeutet.

Das du genau diese Berechnung "im Hintergrund" gemeint hattest, war mir 
nicht klar. Ob du deshalb gleich persönlich wegen musst (Fachidiot) weiß 
ich nicht. Ich habe dich nur gefragt was du meinst.

Ben B. schrieb:
> weil man zuerst die Positon in der Tabelle berechnen

"Weil man...."   ja der Compiler nicht ich.

[900ss (900ss)]

Ben B. schrieb:
> Und denen das leider auch scheißegal ist.

Vorurteile haben wir aber nicht, nein. :)
Ich frage mich auch wie du darauf schließt.

[TotoMitHarry (Gast)]

wenn man das ganze in einer for schleife löst würde das ganze doch in 
einem Loop unrolling optimiert werden?

Dann kann man sich auch den LUT sparen.

[Ben B. (Firma: Funkenflug Industries) (stromkraft)]

> Vorurteile haben wir aber nicht, nein. :)
> Ich frage mich auch wie du darauf schließt.

Beste Antwort:
> Ich(!) brauche für die Berechnung keinen extra Code schreiben.
> Das macht der Compiler für mich.
[..]
> "Weil man...."   ja der Compiler nicht ich.

[900ss (900ss)]

Klaus W. schrieb:
> Ich denke, er meinte daß der vom Compiler generierte Code

Ja, ich glaube auch dass er das meinte. Ich war irritiert seiner Frage 
wegen und deshalb fragte ich was er genau meint. Es ist 
selbstverständlich dass diese Berechnung zum Zugriff stattfinden muss. 
Bei mir macht das allerdings der Compiler, da brauch ich nichts rechnen 
;)
Eine Kröte muss man schlucken. Ich denke trotzdem, es ist die schnellste 
Methode trotz auch noch zusätzlichem Speicherzugriff auf die LUT.

[(prx) A. K. (prx)]

900ss D. schrieb:
> Ich denke trotzdem, es ist die schnellste
> Methode trotz auch noch zusätzlichem Speicherzugriff auf die LUT.

Schneller als der exakt die gewünschte Funktion bietende 
Prozessorbefehl?

[Johann L. (gjlayde)]

Naja, die Instruktion bekommt man nicht per C wie vom TO gefragt, as 
bräuchte ein Inline Asm mit dem BMERGE.

[(prx) A. K. (prx)]

Johann L. schrieb:
> Naja, die Instruktion bekommt man nicht per C wie vom TO gefragt, as
> bräuchte ein Inline Asm mit dem BMERGE.

Oder eine Intrinsic-Funktion. Müsste man halt die Doku des 
Entwicklungssystems durchforsten.

[900ss (900ss)]

(prx) A. K. schrieb:
> Schneller als der exakt die gewünschte Funktion bietende
> Prozessorbefehl?

Nein, in dem Fall, wo die CPU einen entsprechenden Befehl hat wohl 
nicht.

Aber ohne diesen würde ich darauf setzen.

Vielleicht sollte man einen Wettbewerb machen. Der Funkenflug kann ja 
seine moderne CPU auch ins Rennen bringen.
Da kommen sicher auch verschiedene Architekturen zusammen, was auch ganz 
interessant wäre, wie das dort umgesetzt wird.

[Ben B. (Firma: Funkenflug Industries) (stromkraft)]

Im Gegensatz zu euch kann ich Assembler.

[Egon D. (Gast)]

Ben B. schrieb:

> Im Gegensatz zu euch kann ich Assembler.

Im Gegensatz zu Dir leiden "wir" nicht unter
Größenwahn.

[Ben B. (Firma: Funkenflug Industries) (stromkraft)]

Heul leise!

[SPI (Gast)]

Johann L. schrieb:
> SPI schrieb:
>> Ist die Aurix TC3xx Plattform
>
> TriCore hat ne eigene Instruktion für die gesuchte Operation (und die
> Umkehrung): BMERGE und BSPLIT.

Dankeschön für diesen grandiosen Tipp!

Ich habe grad mal in core-architecture manual nachgesehen, und ja es 
stimmt, dieser Befehl macht faktisch genau das, was ich suche :-)

[Patrick C. (pcrom)]

SPI schrieb:
> Quasi eine SPI die selber im Slave-Mode arbeitet und mit genau 6.144 MHz
> getaktet wird,  weil ich ein Stereo PDM-Mems Mikrofon-Signal samplen
> will.
> Die Mikrofone kriegen aber nur eine 3.072 MHz clock (diese pushen
> jeweils aber auf steigende und fallende Flanke raus). Also muss ich die
> SPI doppelt so schnell takten.
> gleichzeitig will ich aus dem SPI Modul ein I2S Signal rausgeben,
> welches seine Bits aber zu der 3.072 MHz clock referenziert haben soll.
> Also pusht die SPI doppelt so viele Bits raus wie nötig.

Wuerde es nicht einfacher die hardware anzupassen ?
zB durch die frequenz durch uC halbieren zu lassen ?

Patrick aus die Niederlaende

[Frank M. (ukw) (Moderator)]

SPI schrieb:
> Dankeschön für diesen grandiosen Tipp!

Der ohne die Angabe Deines µCs gar nicht möglich gewesen wäre ;-)

[900ss (900ss)]

Es ist schon erstaunlich was für spezielle Instruktionen teilweise in 
den Architekturen implementiert sind.

[M. Н. (Gast)]

Jason schrieb:
> Jason schrieb:
>> M. H. schrieb:
>>> Yalu X. schrieb:
>>>> SPI schrieb:
>>>>> uC
>>>>
>>>> Dann geht das mit zwei einfachen Zuweisungen:
>>>
>>> Je nach uC und wie die interne Bus-Matrix zu den GPIOs aussieht, kann
>>> das auch mal in die Hose gehen und deutlich langsamer sein. Die
>>> Zugriffszeiten auf GPIOs sind teilweise sehr hoch.
>>
>> Hast Du ein Beispiel für einen µC bei dem die Zeiten sehr hoch sind?
>
> War schon klar, dass da mal wieder nichts kommt. War also nur dummes
> Geschwätz.

Du bist ja ganz schlau. Hängt natürlich von der Definition von langsam 
ab.
Bei STM32F4 sind bspw. die GPIO Zellen am hochgetakteten AHB Bus 
angehängt. Da ist ein Zugriff schon recht schnell. Trotzdem kann ein Pin 
Toggeln durch

GPIO->ODR ^= (1<<x);

dehr lange dauern im Vergleich zur Taktrate. Allein durch die 
vorangestellt Leseoperation des Registers. Bei 168 MHz Core-clock 
schafft mein F4 hier gerade mal 12 MHz Output Frequenz (Also 24 
Millionen toggles pro Sekunde).

je nachdem wie aufwändig es ist, die Operation intern auszufüheren, bist 
du hier aber noch relativ schnell.

Die absolute Katastrophe sind Cortex-A basierte systeme. Bspw. Das 
Raspberry pi. Die CPU ist soviel schneller getaktet als die Bus Matrix 
der GPIOs, dass die oben genannte Operation in Software definitiv 
schneller ist.

Ein AVR ist bspw sehr schnell mit seinen GPIOs. Da ist der GPIO 
single-Cycle angebunden. Da schafft man teils sogar schnellere IO 
Frequenzen als bei manchem ARM-basierten System, trotz geringerer 
Taktrate.