Bytearray bitweise shiften

[Ralph S. (jjflash)]

Im Rahmen eines Projektes mit Schieberegistern (es werden definitiv mehr 
als 4 Schieberegister werden) benötigte ich eine bitweise 
Schiebefunktion für Arrays und ich habe doch tatsächlich keine 
Funktionen im Netz dafür gefunden (okay, soooo arg lange habe ich nicht 
gesucht).

Also selbst machen.

Das Ergebnis möchte ich hier posten für den Fall, dass das jemand 
ebenfalls gebrauchen kann. Der Einfachkeit halber habe ich das als 
Konsolenprogramm für den PC zuerst geschrieben, um die Funktionen zu 
testen. Das Ergebnis kann im Anhang gesehen werden, die Funktionen:

   uint8_t shiftarray_left(uint8_t anz, uint8_t carryin, uint8_t *parray);
   uint8_t shiftarray_right(uint8_t anz, uint8_t carryin, uint8_t *parray);

habe ich für AVR, STM32, STM8 und MCS51 getestet, sollten jedoch - weil 
reines C - auch mit jedem anderen in C programmierbaren Controller 
funktionieren.

Eine gute (Sonntags)nachtruhe,

JJ

[Mario M. (thelonging)]

Je nach Einsatzzweck und Schieberegisterlänge kann es sinnvoller sein, 
mit Pointer(n) und Bitmaske(n) nur das aus-/eingehende Bit zu 
bearbeiten. Just my 2 ct.

[Ralph S. (jjflash)]

Mario M. schrieb:
> Je nach Einsatzzweck und Schieberegisterlänge kann es sinnvoller sein,
> mit Pointer(n) und Bitmaske(n) nur das aus-/eingehende Bit zu
> bearbeiten. Just my 2 ct.

Na ja, ich brauchte aber die "verschobenen" Bits im Array und nicht nur 
die Carryflags

[Falk B. (falk)]

Ralph S. schrieb:
> habe ich für AVR, STM32, STM8 und MCS51 getestet, sollten jedoch - weil
> reines C - auch mit jedem anderen in C programmierbaren Controller
> funktionieren.

Naja, rein logisch mögen dein Funktionen korrekt sein, aber besonders 
auf kleinen uCs ohne Barrelshifter sind viele deiner Operationen eher 
"langsam".

cf= (*parray >> 7) & 0x01;

Sowas braucht 7 Schiebeoperationen auf dem AVR, je nach 
Compilerschlauheit auch noch ne Zählvariable für die Anzahl der 
Schiebungen. Man muss das Carrybit nicht zwingend in Bit 0 schieben und 
verarbeiten, das geht auch anders. Z.B. so.

uint8_t shiftarray_left(uint8_t cnt, uint8_t c_in, uint8_t *data) {
  uint8_t c_out, tmp;

  data += (cnt-1);
  for (; cnt > 0; cnt--) {
    tmp = *data;
    c_out= tmp & 0x80;
    tmp <<= 1;
    if (c_in) tmp |= 1;
    *data =  tmp;
    c_in = c_out;
    data--;
  }
  return c_out;
}

Es reicht, den logischen Wert zu speichern und auszuwerten. Das 
übersetzt sich in sehr kompaktes und schnelles ASM ohne sinnloses 
Rumschieben.

[Falk B. (falk)]

Und so nach rechts. Alles das Gleiche, nur andere Bitmasken, siehe 
Bitmanipulation.

uint8_t shiftarray_right(uint8_t cnt, uint8_t c_in, uint8_t *data) {
  uint8_t c_out, tmp;

  for (; cnt > 0; cnt--) {
    tmp = *data;
    c_out = tmp & 0x01;
    tmp >>= 1;
    if (c_in) tmp |= 0x80;
    *data =  tmp;
    c_in = c_out;
    data++;
  }
  return c_out;
}

[Ralph S. (jjflash)]

Das werde ich glatt ausprobieren (und für solche Verbesserungsvorschläge 
- keine Ironie - liebe ich dieses Forum).

Vielen Dank Falk

[Bruno V. (bruno_v)]

Ralph S. schrieb:
> Also selbst machen.

Hattest Du tatsächlich eine Anwendung, wo Du durch mehr als 32 Bit 
durchschieben solltest und die Größe/Gesamtmenge nicht von vornherein 
feststand? CRC für beliebige Datenströme wäre so ein Fall. Ist aber 
selten variabel und gleichzeitig >32 Bit.


Schieberegister klingt ehr nach festen Dimensionen, wo der Standardweg 
ein "Bitpointer" ist, also ein Bit-Set/Get mit Index++/-- ist.

[Mario M. (thelonging)]

Falk B. schrieb:
> cf= (*parray >> 7) & 0x01;
>
> Sowas braucht 7 Schiebeoperationen auf dem AVR, je nach
> Compilerschlauheit auch noch ne Zählvariable für die Anzahl der
> Schiebungen.

Also ist avr-gcc schlau, denn er macht für diesen Spezialfall folgenden 
Code daraus.

    rol r24
    clr r24
    rol r24

[Ob S. (Firma: 1984now) (observer)]

Mario M. schrieb:
> Falk B. schrieb:
>> cf= (*parray >> 7) & 0x01;
>>
>> Sowas braucht 7 Schiebeoperationen auf dem AVR, je nach
>> Compilerschlauheit auch noch ne Zählvariable für die Anzahl der
>> Schiebungen.
>
> Also ist avr-gcc schlau, denn er macht für diesen Spezialfall folgenden
> Code daraus.
>

>     rol r24
>     clr r24
>     rol r24
>

Nicht wirklich. In Asm braucht man nur:

rol r24

und der Drops ist gelutscht. Da hat man halt Zugriff auf das echte 
Carryflag. Nunja, zumindest wenn die Architektur überhaupt eins besitzt.

[Mario M. (thelonging)]

Ähm, es geht aber um AVR. Dessen "rotate"-Befehle sind reine 
Shift-Operationen.

[Ob S. (Firma: 1984now) (observer)]

Mario M. schrieb:

> Ähm, es geht aber um AVR.

Nicht nur. Der gepostetete Code ist C mit dem ausdrücklich genannten 
Ziel der Portabilität (siehe z.B. im OT genannte, bereits evaluierte 
Testfälle).

Die explizit genannten haben alle ein Carryflag, aber es gibt eben auch 
andere Architekturen, die keins besitzen.

[Kurt (sommerwin)]

Mit den Rotations Befehlen (links oder rechts) geht das ganz einfach

[Bruno V. (bruno_v)]

Ralph S. schrieb:
> Für solche Verbesserungsvorschläge keine Ironie - liebe ich dieses Forum

Dann vielleicht ohne manuelle Carry-Bit-Auswertung wenn es 
16-Bit-Register gibt?

uint8_t shiftarray_right(uint8_t cnt, uint8_t c_in, uint8_t *data) {
uint16_t s; 

  while(cnt-->0) {
    s = (c_in<<8)|*data;
    c_in = *data;
    *data++ = (uint8_t) (s>>1);
  }
  return c_in&1;
}

Anmerkungen: Das Schieben um 8 sollte von nahezu allen Compilern in 
direkten Byte-Zugriff umgesetzt werden.

Ein Erweitern auf uint16 vor dem Schieben ist nicht notwendig, (integral 
promotion)

Wenn der Prozessor 16-Bit-Register hat, sollte 16-Bit schieben nicht 
langsamer sein als 8bit. Für reine 8-Bit-Prozessoren kann ein 
Bitdangeling schneller sein.

sollte für links ähnlich kurz gehen.

[Ralph S. (jjflash)]

Bruno V. schrieb:
> attest Du tatsächlich eine Anwendung, wo Du durch mehr als 32 Bit
> durchschieben solltest und die Größe/Gesamtmenge nicht von vornherein
> feststand? CRC für beliebige Datenströme wäre so ein Fall. Ist aber
> selten variabel und gleichzeitig >32 Bit.

Momentan geht es um eine - für meine Begriffe - sehr sehr große 
Modelleisenbahnanlage, gemischt aus alten und neuen Teilen eines 
Bekannten. Das ist, für mich der Wahnsinn in Tüten, denn er hat 167 
verschiedene Lokomotiven (Sammler halt), die zum Teil sogar älter sind 
als ich (das Modell, das Original sowieso) und baut diese Lokomotiven 
auf Digitalsteuerung um, die Weichen (momentan sind es 72) jedoch nicht.

Die Anzahl der Weichen kann noch wachsen. Für dieses Ansteuern werden 
Schieberegister verwendet (hier braucht es noch kein bitweises Schieben 
über ein Array).

Er baut jedoch auch einen kleinen Rummelplatz auf (natürlich nicht so 
groß und schön wie im Miniaturwunderland), deren Beleuchtung und 
Lichtspiele mit SMD-Leds realisiert und mittels Schieberegistern 
angesteuert werden sollen. Die Lauflichter dieser Lichtspiele werden 
geshiftet und es steht noch nicht fest, wieviele es für einzelne Modelle 
es werden. Das bisher größte Modell hat 96 LED's. Mindestens hierfür 
bedarf es des Schiebens über ein Array.

[Bruno V. (bruno_v)]

Ralph S. schrieb:
> Die Lauflichter dieser Lichtspiele werden
> geshiftet und es steht noch nicht fest, wieviele es für einzelne Modelle
> es werden. Das bisher größte Modell hat 96 LED's. Mindestens hierfür
> bedarf es des Schiebens über ein Array.

Mag sein, dass es ein Missverständnis ist: ich sehe noch nicht, warum 
man über das Array schieben sollte.

Eine typische Implementierung: Ich habe 12 Bytes, in die ich die neuen 
Muster schreibe und die ich regelmäßig (x Mal pro Sekunde) alle en Block 
raushaue. Oder ich takte ein Muster zyklisch durch die Kette, jeweils 
eine LED weiter.

In beiden Fällen shiftet man nicht durchs Array. Stell Dir einfach die 
Frage, ob Du es auch bei 1000 Bytes machen würdest. Oder ob es auch auf 
festen Mustern (aka ROM) funktionieren sollte.

Beispiel

uint8_t LEDs[12];
// "on == 0": LED aus. "on != 0": an
extern void shift_LED(uint8_t on);

void rauspusten(uint8_t *LEDs, int n)
{
    while(n-->0)
    {
    uint8_t c = *LEDs++;
 
        // ausgerollt, weil alles andere den Aufwand hier nicht lohnt
        shift_next(c|0x80);
        shift_next(c|0x40);
        shift_next(c|0x20);
        shift_next(c|0x10);
        shift_next(c|0x08);
        shift_next(c|0x04);
        shift_next(c|0x02);
        shift_next(c|0x01);
    }
}

/* eine beliebige LED setzen/löschen */
void SetLED(uint8_t *LEDs, uint8_t idx)
{
     LEDs[idx/8]| |= 1<<(idx%8);      
}
void ClrLED(uint8_t *LEDs, uint8_t idx)
{
     LEDs[idx/8] &= ~(1<<(idx%8));      
}

(wenn man sizeof übergibt, kann man auch die Grenzen abfragen. Oder man 
arbeitet auf festen Arrays)

[Ralph S. (jjflash)]

Bruno V. schrieb:
> Mag sein, dass es ein Missverständnis ist: ich sehe noch nicht, warum
> man über das Array schieben sollte.

... ist es

[900ss (900ss)]

Ralph S. schrieb:
> ... ist es

Ich denke nicht :)
Sein Vorschlag: denke dir du müsstest das aus dem Rom lesen und ins 
Schieberegister schreiben. Das Rom kann man schlecht schieben ;)