Shift mit Carry

[Gustav (Gast)]

Geht das "schöner" (kürzer/schneller)? Plattform avr-gcc ATmega.

static void shift_left(uint8_t data[]) {
  uint8_t i;
  for (i = 31; i > 0; i--) data[i] = (data[i] << 1) | (data[i-1] >> 7);
  data[0] <<= 1;
}

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

Nicht schöner, nicht kürzer, nicht optimal, nicht portabel, aber 
schneller:

static uint8_t rol32(uint8_t *p, uint8_t c) //inlined
{
    uint8_t r = p[3] & 0x80;
    *(uint32_t *)p <<= 1;
    if (c) p[0] |= 1;
    return r;
}

void g(uint8_t *data)
{
    uint8_t c = 0;
    for (uint8_t i = 0; i < 32; i += 4)
        c = rol32(data+i, c);
}

Deutlich länger, aber nochmal etwas schneller:

void g(uint8_t *data)
{
    uint8_t c;
    c = rol32(data+0, 0);
    c = rol32(data+4, c);
    c = rol32(data+8, c);
    c = rol32(data+12, c);
    c = rol32(data+16, c);
    c = rol32(data+20, c);
    c = rol32(data+24, c);
    c = rol32(data+28, c);
}

[Eric B. (beric)]

Gustav schrieb:
> Geht das "schöner" (kürzer/schneller)? Plattform avr-gcc ATmega.
>
>

static void shift_left(uint8_t data[]) {
>   uint8_t i;
>   for (i = 31; i > 0; i--) data[i] = (data[i] << 1) | (data[i-1] >> 7);
>   data[0] <<= 1;
> }

Ich glaube da ist noch ein Bug drinne:

data[i] = (data[i] << 1) | (data[i-1] >> 7);


byte   : |data[i-1]              |data[i]                |
vorher : |a7 a6 a5 a4 a3 a2 a1 a0|b7 b6 b5 b4 b3 b2 b1 b0|
           `-------------------------/--/--/--/--/--/--/.
                                    /  /  /  /  /  /  / v
nachher: |a7 a6 a5 a4 a3 a2 a1 a0|b6 b5 b4 b3 b2 b1 b0 a7|

Und b7 ist weg!

[Gustav (Gast)]

Dass der Wert, der ganz links steht, verschwindet, hat ein Leftshift so 
an sich. Das ist auch so erwünscht.

@A. K.

Danke, ich werde mal testen!

[Gustav (Gast)]

Habe mal beides disassembliert. Sicher, dass deine Variante (unten) auch 
schneller ist??

    22ca:  dc 01         movw  r26, r24
    22cc:  90 96         adiw  r26, 0x20  ; 32
    22ce:  fc 01         movw  r30, r24
    22d0:  7f 96         adiw  r30, 0x1f  ; 31
    22d2:  2e 91         ld  r18, -X
    22d4:  22 0f         add  r18, r18
    22d6:  32 91         ld  r19, -Z
    22d8:  33 1f         adc  r19, r19
    22da:  33 27         eor  r19, r19
    22dc:  33 1f         adc  r19, r19
    22de:  23 2b         or  r18, r19
    22e0:  2c 93         st  X, r18
    22e2:  e8 17         cp  r30, r24
    22e4:  f9 07         cpc  r31, r25
    22e6:  a9 f7         brne  .-22       ; 0x22d2 <shift_left+0x8>
    22e8:  80 81         ld  r24, Z
    22ea:  88 0f         add  r24, r24
    22ec:  80 83         st  Z, r24
    22ee:  08 95         ret

    323e:  fc 01         movw  r30, r24
    3240:  9c 01         movw  r18, r24
    3242:  20 5e         subi  r18, 0xE0  ; 224
    3244:  3f 4f         sbci  r19, 0xFF  ; 255
    3246:  80 e0         ldi  r24, 0x00  ; 0
    3248:  93 81         ldd  r25, Z+3  ; 0x03
    324a:  90 78         andi  r25, 0x80  ; 128
    324c:  40 81         ld  r20, Z
    324e:  51 81         ldd  r21, Z+1  ; 0x01
    3250:  62 81         ldd  r22, Z+2  ; 0x02
    3252:  73 81         ldd  r23, Z+3  ; 0x03
    3254:  44 0f         add  r20, r20
    3256:  55 1f         adc  r21, r21
    3258:  66 1f         adc  r22, r22
    325a:  77 1f         adc  r23, r23
    325c:  40 83         st  Z, r20
    325e:  51 83         std  Z+1, r21  ; 0x01
    3260:  62 83         std  Z+2, r22  ; 0x02
    3262:  73 83         std  Z+3, r23  ; 0x03
    3264:  88 23         and  r24, r24
    3266:  19 f0         breq  .+6        ; 0x326e <shift_left.lto_priv.21+0x30>
    3268:  80 81         ld  r24, Z
    326a:  81 60         ori  r24, 0x01  ; 1
    326c:  80 83         st  Z, r24
    326e:  34 96         adiw  r30, 0x04  ; 4
    3270:  89 2f         mov  r24, r25
    3272:  e2 17         cp  r30, r18
    3274:  f3 07         cpc  r31, r19
    3276:  41 f7         brne  .-48       ; 0x3248 <shift_left.lto_priv.21+0xa>
    3278:  08 95         ret

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

Gustav schrieb:
> Sicher, dass deine Variante (unten) auch schneller ist??

Denke schon. Deine schleift 32x, meine 8x.

[Eric B. (beric)]

Gustav schrieb:
> Dass der Wert, der ganz links steht, verschwindet, hat ein Leftshift so
> an sich. Das ist auch so erwünscht.

Ah, LSB versus MSB. Ich hatte wohl noch zuviel Blut im Kaffee und dachte 
du würdest hier alle b7-s verlieren...

[Gustav (Gast)]

Stimmt, bei 32 Bit schleift es weniger. ;)

[Michael U. (amiga)]

Hallo,

mit ähnlichem habe ich vor Jahren mal experimentiert und Jörg Wunsch hat 
mir damals bei der inline-ASM Geschichte geholfen.
War für eine DCF77-Uhr, die alle Impulse in ein 64Bit Register schiebt 
und das neue Bit anhängt.

Schiebt zwar nach rechts und hängt ganz links an, das zum links schieben 
umzubauen und auf 32 statt 64 Bit zu kürzen sollte aber ja kein Problem 
sein.

                  dcf77_bit_cnt++;         // Bitcount erhöhen
                  asm volatile             // shift long long right und höchstwertiges Bit bleibt 0
                    (
                      "lds __tmp_reg__, %0 + 7" "\n\t"
                      "lsr __tmp_reg__" "\n\t"
                      "sts %0 + 7, __tmp_reg__" "\n\t"
                      "lds __tmp_reg__, %0 + 6" "\n\t"
                      "ror __tmp_reg__" "\n\t"
                      "sts %0 + 6, __tmp_reg__" "\n\t"
                      "lds __tmp_reg__, %0 + 5" "\n\t"
                      "ror __tmp_reg__" "\n\t"
                      "sts %0 + 5, __tmp_reg__" "\n\t"
                      "lds __tmp_reg__, %0 + 4" "\n\t"
                      "ror __tmp_reg__" "\n\t"
                      "sts %0 + 4, __tmp_reg__" "\n\t"
                      "lds __tmp_reg__, %0 + 3" "\n\t"
                      "ror __tmp_reg__" "\n\t"
                      "sts %0 + 3, __tmp_reg__" "\n\t"
                      "lds __tmp_reg__, %0 + 2" "\n\t"
                      "ror __tmp_reg__" "\n\t"
                      "sts %0 + 2, __tmp_reg__" "\n\t"
                      "lds __tmp_reg__, %0 + 1" "\n\t"
                      "ror __tmp_reg__" "\n\t"
                      "sts %0 + 1, __tmp_reg__" "\n\t"
                      "lds __tmp_reg__, %0" "\n\t"
                      "ror __tmp_reg__" "\n\t"
                      "sts %0, __tmp_reg__"
                    : "+m" (dcf77_daten)
                    );
                  if (dcf77_time_cnt < 87) // Bit war 1 
                    {
                      asm volatile        // höchstwertiges Bit des long long auf 1 setzen
                        (
                          "lds __tmp_reg__, %0 + 7" "\n\t"
                          "set" "\n\t"                      // T setzen
                          "bld __tmp_reg__, 7" "\n\t"       // und in Bit 7 kopieren
                          "sts %0 + 7, __tmp_reg__" "\n\t"
                        : "+m" (dcf77_daten)
                        );
                    }

Ist jetzt nur schnell rauskopiert...

Gruß aus Berlin
Michael

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

Michael U. schrieb:
> und auf 32 statt 64 Bit zu kürzen

Da wär eher angesagt, es auf 32 Bytes = 256 Bits zu verlängern.

[Michael U. (amiga)]

Hallo,

sorry, DAS hatte ich glatt übersehen...

Gruß aus Berlin
Michael