Forum: Mikrocontroller und Digitale Elektronik Bitmanipulation beschleunigen


von sigma9 (Gast)


Lesenswert?

Hallo,

ich versuche eine Bitmanipulation wie sie beim Zoomen für ein LC-Display 
vorkommt zu beschleunigen.

gewünscht: aus einem 7-bit Input (i6...i0) soll ein 28-bit Output 
(o27...o0) erzeugt werden nach folgender Regel:

i0   -> o0=o1=o2=03
i1   -> o4=o5=o6=07
i2   -> o8=o9=o10=011
i3   -> o12=o13=o14=15
i4   -> o16=o17=o18=019
i5   -> o20=o21=o22=023
i6   -> o24=o25=o26=027

also in Worten: jedes Bit im Input soll Gruppen von 4 gleichen Bits im 
Output ergeben, die dort entsprechend nebeneinander liegen.

Folgende Code-Varianten fallen mir ein:

1
//-------------------------------
2
uint32_t  variant1 (uint8_t in)
3
//-------------------------------
4
{
5
  uint32_t  result    = 0L;
6
  uint32_t  one_bit_set = 1L;
7
  
8
  for (uint8_t bit = 0; bit < 7; bit++)
9
  {
10
    for (uint8_t zr = 0; zr < 4; zr++)
11
    {
12
      if (in & (1 << bit)) result += one_bit_set;
13
      one_bit_set <<= 1;
14
    }
15
  }
16
  return result;
17
}
18
19
20
21
//--------------------------------
22
uint32_t  variant1a (uint8_t in)
23
//--------------------------------
24
{
25
  uint32_t  result    = 0L;
26
  uint32_t  one_bit_set = 1L;
27
  
28
  for (uint8_t bit = 0; bit < 7; bit++)
29
  {
30
    if (in & (1 << bit)) result += one_bit_set;
31
    one_bit_set <<= 4;
32
  }
33
  result *= 15;
34
  return result;
35
}
36
37
38
39
//-------------------------------
40
uint32_t  variant2 (uint8_t in)
41
//-------------------------------
42
{
43
  return pgm_read_dword(&pattern_table_ROM[in]);
44
}
45
46
47
48
//-------------------------------
49
uint32_t  variant3 (uint8_t in)
50
//-------------------------------
51
{
52
  return pattern_table_RAM[in];
53
}
54
55
56
57
//-------------------------------
58
uint32_t  variant4 (uint8_t in)
59
//-------------------------------
60
{
61
  uint8_t  a,b,c,d;
62
  
63
  a = __builtin_avr_insert_bits (0x11110000, in, 0);
64
  b = __builtin_avr_insert_bits (0x33332222, in, 0);
65
  c = __builtin_avr_insert_bits (0x55554444, in, 0);
66
  d = __builtin_avr_insert_bits (0xffff6666, in, 0);
67
68
  return (uint32_t) a + (((uint32_t) b) << 8) + (((uint32_t) c) << 16) + (((uint32_t) d) << 24);
69
}


Variante 1: trivial, nur zu Veranschaulichung was ich will.
Benötigt 564...648 Takte (je nachdem wie viel Einsen im Input

Variante 1a: nutzt mult (Host ist AVRmega mit intrinsischem mult8)
Benötigt 386...407 Takte (je nachdem wie viel Einsen im Input

Variante 2: nutzt Tabelle mit 128 dwords im ROM.
Benötigt 33 Takte, aber 128*4 = 512 Bytes im ROM - könnte ich gerade 
noch mit leben.

Variante 3: nutzt Tabelle mit 128 dwords im RAM.
Benötigt 4 Takte, aber 128*4 = 512 Bytes im RAM: unschlagbar schnell, 
aber leider habe ich nicht soviel RAM zur Verfügung.

Variante 4: nutzt GCC Funktion "insert bits".
Benötigt 95 Takte: das ist das schnellste, was mir ohne Tabelle 
eingefallen ist.

Irgendwelche Ideen zur Beschleunigung von den (Assembler)-Gurus?

Jeder Tipp herzlich willkommen - Danke im Voraus.

/sigma9

von Dr. Google (Gast)


Lesenswert?

eine solche tabelle kann man mit switch case realisieren.

von dunno.. (Gast)


Lesenswert?

Eine if-anweisung pro gruppe und die zwischenergebnisse zusammenaddieren 
ist dir zu unelegant?

von DerJan (Gast)


Lesenswert?

Ich kenne mich nur mit PICs aus aber das wäre mein Ansatz (für 8biter):
1
//-------------------------------
2
uint32_t  variant_jan (uint8_t in)
3
//-------------------------------
4
{
5
  union {
6
    uint32_t all;
7
    uint8_t array[4];
8
  } result;
9
10
  result.all = 0;
11
12
13
  if (in&0x01){
14
    result.array[0] += 0x0F;
15
  }
16
    
17
  if (in&0x02){
18
    result.array[0] += 0xF0;
19
  }
20
21
  if (in&0x04){
22
    result.array[1] += 0x0F;
23
  }
24
    
25
  if (in&0x08){
26
    result.array[1] += 0xF0;
27
  }
28
29
  if (in&0x10){
30
    result.array[2] += 0x0F;
31
  }
32
    
33
  if (in&0x20){
34
    result.array[2] += 0xF0;
35
  }
36
37
  if (in&0x40){
38
    result.array[3] += 0x0F;
39
  }
40
    
41
  if (in&0x80){
42
    result.array[3] += 0xF0;
43
  }
44
45
  return (result.all);
46
}

Da jeweils nur auf 8 bit zugegriffen wird sollt es recht zügig gehen.
Bei einem PIC würde ich im List file noch nachschauen, dass bei den IF 
Abfragen der Befehl "Is bit set" verwendet wird und nicht die verundung 
ausgeführt wird.

von sigma9 (Gast)


Lesenswert?

@derJan

sehr gute Idee! Der wesentliche Trick ist, das man alles auf 8 bit 
Arithmetik runterbrechen kann. Das wird sehr schnell. ausprobiert -> 35 
Takte. Respekt!

btw der GCC macht es sehr pfiffig:
1
 608:  60 e0         ldi  r22, 0x00  ; 0
2
 60a:  70 e0         ldi  r23, 0x00  ; 0
3
 60c:  20 e0         ldi  r18, 0x00  ; 0
4
 60e:  90 e0         ldi  r25, 0x00  ; 0
5
 610:  80 fd         sbrc  r24, 0
6
 612:  6f e0         ldi  r22, 0x0F  ; 15
7
 614:  81 fd         sbrc  r24, 1
8
 616:  60 51         subi  r22, 0x10  ; 16
9
 618:  82 fd         sbrc  r24, 2
10
 61a:  7f e0         ldi  r23, 0x0F  ; 15
11
 61c:  83 fd         sbrc  r24, 3
12
 61e:  70 51         subi  r23, 0x10  ; 16
13
 620:  84 fd         sbrc  r24, 4
14
 622:  2f e0         ldi  r18, 0x0F  ; 15
15
 624:  85 fd         sbrc  r24, 5
16
 626:  20 51         subi  r18, 0x10  ; 16
17
 628:  86 fd         sbrc  r24, 6
18
 62a:  9f e0         ldi  r25, 0x0F  ; 15
19
 62c:  88 23         and  r24, r24
20
 62e:  0c f4         brge  .+2        ; 0x632 <variant_jan+0x2a>
21
 630:  90 51         subi  r25, 0x10  ; 16
22
 632:  82 2f         mov  r24, r18
23
 634:  08 95         ret


Danke dafür.

von dunno.. (Gast)


Lesenswert?

thumbs up für das mit der union!!

besser zu lesen als mein ansatz.

von sigma9 (Gast)


Lesenswert?

@dunno:

Ich verstehe nicht genau was du meinst, denke aber des es sehr ähnlich 
meiner Variante 2 ist:
1
//-------------------------------
2
uint32_t  variant_dunno (uint8_t in)
3
//-------------------------------
4
{
5
  uint32_t  result      = 0L;
6
  uint32_t  four_bits_set = 15L;
7
  
8
  for (uint8_t bit = 0; bit < 7; bit++)
9
  {
10
    if (in & (1 << bit)) result += four_bits_set;
11
    four_bits_set <<= 4;
12
  }
13
  return result;
14
}

Braucht 371...392 Takte und ist also nur unwesentlich schneller als 
Variante2

von sigma9 (Gast)


Lesenswert?

@Dr Google:

verstehe ich nicht. Ich will ja am liebsten keine Tabelle benutzen wegen 
des zu hohej RAM/ROM Verbrauchs.

Oder ich habe dich komplett missverstanden...

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Du kannst folgendes machen:
1
#include <stdint.h>
2
3
uint32_t variant5 (uint8_t in)
4
{
5
    uint32_t out = 0;
6
    if (in & (1u << 0)) out |= 0xful << (4*0);
7
    if (in & (1u << 1)) out |= 0xful << (4*1);
8
    if (in & (1u << 2)) out |= 0xful << (4*2);
9
    if (in & (1u << 3)) out |= 0xful << (4*3);
10
    if (in & (1u << 4)) out |= 0xful << (4*4);
11
    if (in & (1u << 5)) out |= 0xful << (4*5);
12
    if (in & (1u << 6)) out |= 0xful << (4*6);
13
    if (in & (1u << 7)) out |= 0xful << (4*7);
14
    return out;
15
}

avr-gcc-6 -Os macht daraus:
1
variant5:
2
  mov r18,r24
3
  sbrs r24,0
4
  rjmp .L10
5
  ldi r22,lo8(15)
6
  ldi r23,0
7
  ldi r24,0
8
  ldi r25,0
9
.L2:
10
  sbrc r18,1
11
  ori r22,240
12
  sbrc r18,2
13
  ori r23,15
14
  sbrc r18,3
15
  ori r23,240
16
  sbrc r18,4
17
  ori r24,15
18
  sbrc r18,5
19
  ori r24,240
20
  sbrc r18,6
21
  ori r25,15
22
  sbrc r18,7
23
  ori r25,240
24
  ret
25
.L10:
26
  ldi r22,0
27
  ldi r23,0
28
  ldi r24,0
29
  ldi r25,0
30
  rjmp .L2

Ist zwar nicht optimal aber allemal besser als Schleifen.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

...und mit folgendem kleinen hässlichen Hack wird der Code nochmals 
kleiner:
1
uint32_t variant5 (uint8_t in)
2
{
3
    uint32_t out = 0;
4
    asm ("" : "+r" (out));
5
    if (in & (1u << 0)) out |= 0xful << (4*0);
6
    if (in & (1u << 1)) out |= 0xful << (4*1);
7
    if (in & (1u << 2)) out |= 0xful << (4*2);
8
    if (in & (1u << 3)) out |= 0xful << (4*3);
9
    if (in & (1u << 4)) out |= 0xful << (4*4);
10
    if (in & (1u << 5)) out |= 0xful << (4*5);
11
    if (in & (1u << 6)) out |= 0xful << (4*6);
12
    if (in & (1u << 7)) out |= 0xful << (4*7);
13
    return out;
14
}
1
variant5:
2
  mov r18,r24
3
  ldi r22,0
4
  ldi r23,0
5
  ldi r24,0
6
  ldi r25,0
7
  sbrc r18,0
8
  ori r22,15
9
  sbrc r18,1
10
  ori r22,240
11
  sbrc r18,2
12
  ori r23,15
13
  sbrc r18,3
14
  ori r23,240
15
  sbrc r18,4
16
  ori r24,15
17
  sbrc r18,5
18
  ori r24,240
19
  sbrc r18,6
20
  ori r25,15
21
  sbrc r18,7
22
  ori r25,240
23
  ret

von Peter II (Gast)


Lesenswert?

Johann L. schrieb:
> asm ("" : "+r" (out));

was bewirkt das?

von sigma9 (Gast)


Lesenswert?

@Johann L:


ich verstehe komplett was da passiert - nur wäre ich da nie drauf 
gekommen.
Das ist halt der Unterschied zwischen Gurus und Bemühten ;=)

Was ich bis jetzt übersehen hatte - das hängt natürlich auch alles vom 
optimization level ab. Gemessen:

       o3   02   o1   oS

v4     38   34   95   94
jan    34   33   44   42
dunno  65  358  377  463
johann 32   31   34   32


Da ich fast immer mit -oS arbeite, ist dein Algorithmus noch 
überzeugender.

Chapeau!

von DerJan (Gast)


Lesenswert?

super Sache.

und was macht :
asm ("" : "+r" (out));
jetzt?

würde mich auch interresieren

von Nico W. (nico_w)


Lesenswert?

Wenn ich das richtig verstanden habe, wird dadurch die Variable 'out' 
direkt in ein Register geschoben und auf diese darf gelesen und 
geschrieben werden. Und das ist am Ende auch das Ergebnis (ret).

: Bearbeitet durch User
von Peter II (Gast)


Lesenswert?

Nico W. schrieb:
> Wenn ich das richtig verstanden habe, wird dadurch die Variable 'out'
> direkt in ein Register geschoben und auf diese darf gelesen und
> geschrieben werden. Und das ist am Ende auch das Ergebnis (ret).

das erwarte ich als Selberverständlichkeit von einem Compiler.

von Mampf F. (mampf) Benutzerseite


Lesenswert?

Mein Vorschlag^^
1
//-------------------------------
2
uint32_t  variant1 (uint8_t in)
3
//-------------------------------
4
{
5
  uint32_t  result    = 0L;
6
  
7
  for (uint8_t bit = 0; bit < 7; bit++)
8
    result |= (in & (1<<bit)) ? (0xfL << (bit << 2)) : 0;
9
10
  return result;
11
}

von Falk B. (falk)


Lesenswert?

@ Peter II (Gast)

>> Wenn ich das richtig verstanden habe, wird dadurch die Variable 'out'
>> direkt in ein Register geschoben und auf diese darf gelesen und
>> geschrieben werden. Und das ist am Ende auch das Ergebnis (ret).

>das erwarte ich als Selberverständlichkeit von einem Compiler.

Das macht der gcc ja auch ohne den Hack, der macht es nur noch einen 
TICK schneller. Ist eine OptimierungsoptimierungOptimierung. Ich würde 
sie einfach weglassen.

von sigma9 (Gast)


Lesenswert?

Mampf F. schrieb:
> //-------------------------------
> uint32_t  variant1 (uint8_t in)
> //-------------------------------
> {
>   uint32_t  result    = 0L;
>
>   for (uint8_t bit = 0; bit < 7; bit++)
>     result |= (in & (1<<bit)) ? (0xfL << (bit << 2)) : 0;
>
>   return result;
> }


war (fast) meine Version 0. Braucht wegen der 32bit-Arithmetik 797 
Takte...

von sigma9 (Gast)


Lesenswert?

Falk B. schrieb:
> @ Peter II (Gast)
>
>>> Wenn ich das richtig verstanden habe, wird dadurch die Variable 'out'
>>> direkt in ein Register geschoben und auf diese darf gelesen und
>>> geschrieben werden. Und das ist am Ende auch das Ergebnis (ret).
>
>>das erwarte ich als Selberverständlichkeit von einem Compiler.
>
> Das macht der gcc ja auch ohne den Hack, der macht es nur noch einen
> TICK schneller. Ist eine OptimierungsoptimierungOptimierung. Ich würde
> sie einfach weglassen.


Offensichtlich hilft man dem GCC beim Optimieren:

-oS: 32 (mit asm"") <-> 44 (ohne) ist 25% Unterschied!
-o2: 31             <-> 33 fast gleich!

Der Hack bewirkt also, dass trotz generellem Optimeren auf Grösse
die gewünschte Routine schnell wird.

GCC macht mit -oS:
1
00000404 <variant5_mit_asm>:
2
 404:  28 2f         mov  r18, r24
3
 406:  60 e0         ldi  r22, 0x00  ; 0
4
 408:  70 e0         ldi  r23, 0x00  ; 0
5
 40a:  cb 01         movw  r24, r22
6
 40c:  20 fd         sbrc  r18, 0
7
 40e:  6f 60         ori  r22, 0x0F  ; 15
8
 410:  21 fd         sbrc  r18, 1
9
 412:  60 6f         ori  r22, 0xF0  ; 240
10
 414:  22 fd         sbrc  r18, 2
11
 416:  7f 60         ori  r23, 0x0F  ; 15
12
 418:  23 fd         sbrc  r18, 3
13
 41a:  70 6f         ori  r23, 0xF0  ; 240
14
 41c:  24 fd         sbrc  r18, 4
15
 41e:  8f 60         ori  r24, 0x0F  ; 15
16
 420:  25 fd         sbrc  r18, 5
17
 422:  80 6f         ori  r24, 0xF0  ; 240
18
 424:  26 fd         sbrc  r18, 6
19
 426:  9f 60         ori  r25, 0x0F  ; 15
20
 428:  27 fd         sbrc  r18, 7
21
 42a:  90 6f         ori  r25, 0xF0  ; 240
22
 42c:  08 95         ret
23
24
0000042e <variant5_ohne_asm>:
25
 42e:  28 2f         mov  r18, r24
26
 430:  80 ff         sbrs  r24, 0
27
 432:  05 c0         rjmp  .+10       ; 0x43e <variant5_ohne_asm+0x10>
28
 434:  6f e0         ldi  r22, 0x0F  ; 15
29
 436:  70 e0         ldi  r23, 0x00  ; 0
30
 438:  80 e0         ldi  r24, 0x00  ; 0
31
 43a:  90 e0         ldi  r25, 0x00  ; 0
32
 43c:  03 c0         rjmp  .+6        ; 0x444 <variant5_ohne_asm+0x16>
33
 43e:  60 e0         ldi  r22, 0x00  ; 0
34
 440:  70 e0         ldi  r23, 0x00  ; 0
35
 442:  cb 01         movw  r24, r22
36
 444:  21 fd         sbrc  r18, 1
37
 446:  60 6f         ori  r22, 0xF0  ; 240
38
 448:  22 fd         sbrc  r18, 2
39
 44a:  7f 60         ori  r23, 0x0F  ; 15
40
 44c:  23 fd         sbrc  r18, 3
41
 44e:  70 6f         ori  r23, 0xF0  ; 240
42
 450:  24 fd         sbrc  r18, 4
43
 452:  8f 60         ori  r24, 0x0F  ; 15
44
 454:  25 fd         sbrc  r18, 5
45
 456:  80 6f         ori  r24, 0xF0  ; 240
46
 458:  26 fd         sbrc  r18, 6
47
 45a:  9f 60         ori  r25, 0x0F  ; 15
48
 45c:  27 fd         sbrc  r18, 7
49
 45e:  90 6f         ori  r25, 0xF0  ; 240
50
 460:  08 95         ret


...und mit -o2
1
000002fa <variant5_mit_asm>:
2
 2fa:  28 2f         mov  r18, r24
3
 2fc:  60 e0         ldi  r22, 0x00  ; 0
4
 2fe:  70 e0         ldi  r23, 0x00  ; 0
5
 300:  cb 01         movw  r24, r22
6
 302:  20 fd         sbrc  r18, 0
7
 304:  6f 60         ori  r22, 0x0F  ; 15
8
 306:  21 fd         sbrc  r18, 1
9
 308:  60 6f         ori  r22, 0xF0  ; 240
10
 30a:  22 fd         sbrc  r18, 2
11
 30c:  7f 60         ori  r23, 0x0F  ; 15
12
 30e:  23 fd         sbrc  r18, 3
13
 310:  70 6f         ori  r23, 0xF0  ; 240
14
 312:  24 fd         sbrc  r18, 4
15
 314:  8f 60         ori  r24, 0x0F  ; 15
16
 316:  25 fd         sbrc  r18, 5
17
 318:  80 6f         ori  r24, 0xF0  ; 240
18
 31a:  26 fd         sbrc  r18, 6
19
 31c:  9f 60         ori  r25, 0x0F  ; 15
20
 31e:  27 ff         sbrs  r18, 7
21
 320:  08 95         ret
22
 322:  90 6f         ori  r25, 0xF0  ; 240
23
 324:  08 95         ret
24
25
00000326 <variant5_ohne_asm>:
26
 326:  28 2f         mov  r18, r24
27
 328:  80 ff         sbrs  r24, 0
28
 32a:  13 c0         rjmp  .+38       ; 0x352 <variant5_ohne_asm+0x2c>
29
 32c:  6f e0         ldi  r22, 0x0F  ; 15
30
 32e:  70 e0         ldi  r23, 0x00  ; 0
31
 330:  80 e0         ldi  r24, 0x00  ; 0
32
 332:  90 e0         ldi  r25, 0x00  ; 0
33
 334:  21 fd         sbrc  r18, 1
34
 336:  60 6f         ori  r22, 0xF0  ; 240
35
 338:  22 fd         sbrc  r18, 2
36
 33a:  7f 60         ori  r23, 0x0F  ; 15
37
 33c:  23 fd         sbrc  r18, 3
38
 33e:  70 6f         ori  r23, 0xF0  ; 240
39
 340:  24 fd         sbrc  r18, 4
40
 342:  8f 60         ori  r24, 0x0F  ; 15
41
 344:  25 fd         sbrc  r18, 5
42
 346:  80 6f         ori  r24, 0xF0  ; 240
43
 348:  26 fd         sbrc  r18, 6
44
 34a:  9f 60         ori  r25, 0x0F  ; 15
45
 34c:  27 fd         sbrc  r18, 7
46
 34e:  05 c0         rjmp  .+10       ; 0x35a <variant5_ohne_asm+0x34>
47
 350:  08 95         ret
48
 352:  60 e0         ldi  r22, 0x00  ; 0
49
 354:  70 e0         ldi  r23, 0x00  ; 0
50
 356:  cb 01         movw  r24, r22
51
 358:  ed cf         rjmp  .-38       ; 0x334 <variant5_ohne_asm+0xe>
52
 35a:  90 6f         ori  r25, 0xF0  ; 240
53
 35c:  08 95         ret

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Falk B. schrieb:
> Ist eine OptimierungsoptimierungOptimierung. Ich würde sie
> einfach weglassen.

Jau.

Zur Erklärung:

> asm ("" : "+r" (out));

verhindert eine Optimierung :-)

Die Routine beginnt mit
1
uint32_t out = 0;
2
if (in & (1u << 0)) out |= 0xful << (4*0);
und avr-gcc macht daraus effektiv
1
uint32_t out = (in & 1) ? 0xful : 0ul;
was schlechter ist als erste 0ul zu laden und darauf ein OR 0xf zu 
veranstalten.

Das asm beschreibt eine Operation, die out als Eingabe und Ausgabe hat; 
gcc weiß nach dem asm also nicht mehr, dass out=0 ist, und daher kann 
die o.g. "Optimierung" nicht angewandt werden.

Wenn man aber wirklich darauf angewiesen ist, dass der Code diesen Grad 
an Effizienz hat, dann sollte man besser gleich die ganze Routine in 
Assembler schreiben...

von sigma9 (Gast)


Lesenswert?

@Johann:

> Wenn man aber wirklich darauf angewiesen ist, dass der Code diesen Grad
> an Effizienz hat, dann sollte man besser gleich die ganze Routine in
> Assembler schreiben...

vollkommen d'accord.
Ob man nun 32 Takte oder 44 erreicht, ist - zumindest bei meiner 
Anwendung - wirklich egal, verglichen mit ~750 unoptimiert dagegen 
sicher nicht.

Das Zoomen war nur ein Hotspot...

Hab jedenfalls wieder was gelernt - danke.

von Peter II (Gast)


Lesenswert?

Johann L. schrieb:
> verhindert eine Optimierung :-)

danke für die Erläuterung.

könnte man dann nicht gleich
1
uint32_t out = 0;
2
if (in & (1u << 0)) out = 0xful << (4*0);

also ohne das oder.

von sigma9 (Gast)


Lesenswert?

Peter II schrieb:
> Johann L. schrieb:
>> verhindert eine Optimierung :-)
>
> danke für die Erläuterung.
>
> könnte man dann nicht gleich
> uint32_t out = 0;
> if (in & (1u << 0)) out = 0xful << (4*0);
>
> also ohne das oder.


kommt nicht ganz des gleiche heraus:
1
00000444 <variant5_mit_asm>:
2
 444:  28 2f         mov  r18, r24      ; 1
3
 446:  60 e0         ldi  r22, 0x00  ; 0    ; 1
4
 448:  70 e0         ldi  r23, 0x00  ; 0    ; 1
5
 44a:  cb 01         movw  r24, r22      ; 1
6
 44c:  20 fd         sbrc  r18, 0        ; 2
7
 44e:  6f 60         ori  r22, 0x0F  ; 15    ; 1
8
 450:  21 fd         sbrc  r18, 1        ; 2
9
 452:  60 6f         ori  r22, 0xF0  ; 240    ; 1
10
 454:  22 fd         sbrc  r18, 2        ; 2
11
 456:  7f 60         ori  r23, 0x0F  ; 15    ; 1
12
 458:  23 fd         sbrc  r18, 3        ; 2
13
 45a:  70 6f         ori  r23, 0xF0  ; 240    ; 1
14
 45c:  24 fd         sbrc  r18, 4        ; 2
15
 45e:  8f 60         ori  r24, 0x0F  ; 15    ; 1
16
 460:  25 fd         sbrc  r18, 5        ; 2
17
 462:  80 6f         ori  r24, 0xF0  ; 240    ; 1
18
 464:  26 fd         sbrc  r18, 6        ; 2
19
 466:  9f 60         ori  r25, 0x0F  ; 15    ; 1
20
 468:  27 fd         sbrc  r18, 7        ; 2
21
 46a:  90 6f         ori  r25, 0xF0  ; 240    ; 1
22
 46c:  08 95         ret          ; 4 = 32"
23
24
25
000004a2 <variant5_ohne_asm_ohne_or>:
26
 4a2:  28 2f         mov  r18, r24      ; 1
27
 4a4:  80 ff         sbrs  r24, 0        ; 2
28
 4a6:  05 c0         rjmp  .+10           ; 2
29
 4a8:  6f e0         ldi  r22, 0x0F  ; 15    ; 1
30
 4aa:  70 e0         ldi  r23, 0x00  ; 0    ; 1
31
 4ac:  80 e0         ldi  r24, 0x00  ; 0    ; 1
32
 4ae:  90 e0         ldi  r25, 0x00  ; 0    ; 1
33
 4b0:  03 c0         rjmp  .+6            ; 2
34
 4b2:  60 e0         ldi  r22, 0x00  ; 0    ; 1
35
 4b4:  70 e0         ldi  r23, 0x00  ; 0    ; 1
36
 4b6:  cb 01         movw  r24, r22      ; 1
37
 4b8:  21 fd         sbrc  r18, 1        ; 2
38
 4ba:  60 6f         ori  r22, 0xF0  ; 240    ; 1
39
 4bc:  22 fd         sbrc  r18, 2        ; 2
40
 4be:  7f 60         ori  r23, 0x0F  ; 15    ; 1
41
 4c0:  23 fd         sbrc  r18, 3        ; 2
42
 4c2:  70 6f         ori  r23, 0xF0  ; 240    ; 1
43
 4c4:  24 fd         sbrc  r18, 4        ; 2
44
 4c6:  8f 60         ori  r24, 0x0F  ; 15    ; 1
45
 4c8:  25 fd         sbrc  r18, 5        ; 2
46
 4ca:  80 6f         ori  r24, 0xF0  ; 240    ; 1
47
 4cc:  26 fd         sbrc  r18, 6        ; 2
48
 4ce:  9f 60         ori  r25, 0x0F  ; 15    ; 1
49
 4d0:  27 fd         sbrc  r18, 7        ; 2
50
 4d2:  90 6f         ori  r25, 0xF0  ; 240    ; 1
51
 4d4:  08 95         ret          ; 4 = 39"


In jedem Fall bin ich jedes Mal verblüfft über die Tricks des GCC.

von Nico W. (nico_w)


Lesenswert?

Peter II schrieb:
> könnte man dann nicht gleich

Unter -Os zumindest erzeugt das einen identischen Code.
Zumindest unter GCC 4.9.2.
GCC 6.1.1 merkt bei mir, wenn die beiden Funktionen in der gleichen 
Datei stehen, dass diese Identisch sind, und ersetzt den Aufruf von 
version5 mit version6 automatisch.

: Bearbeitet durch User
von sigma9 (Gast)


Lesenswert?

Nico W. schrieb:
> Peter II schrieb:
>> könnte man dann nicht gleich
>
> Unter -Os zumindest erzeugt das einen identischen Code.

hmmm - bei mir nicht (s.o.)
habe allerdings nicht allerneueste Toolchain (4.9.2) umd avrlib (1.8.2)

von Nico W. (nico_w)


Lesenswert?

sigma9 schrieb:
> hmmm - bei mir nicht (s.o.)

Ich habe jetzt
1
uint32_t out = 0;
2
if (in & (1u << 0)) out |= 0xful << (4*0);
mit
1
uint32_t out = 0;
2
if (in & (1u << 0)) out = 0xful << (4*0);
verglichen.

von sigma9 (Gast)


Lesenswert?

Nico W. schrieb:
> sigma9 schrieb:
>> hmmm - bei mir nicht (s.o.)
>
> Ich habe jetztuint32_t out = 0;
> if (in & (1u << 0)) out |= 0xful << (4*0);
> mituint32_t out = 0;
> if (in & (1u << 0)) out = 0xful << (4*0);
> verglichen.


hast Recht: "ohne asm() + ohne or" ist bei mir auch code-identisch mit 
"ohne asm()" und ja, der 4.9.2 merkt nicht, dass die gleich sind.

von eProfi (Gast)


Lesenswert?

>   d = __builtin_avr_insert_bits (0xffff6666, in, 0);
aha, nach 6 kommt f

Eine andere Idee:
1
  int8_t c=PORTD; //zum Test, damit nichts wegoptimiert wird
2
  register union{uint32_t i32;uint8_t b[4];}u;
3
  switch(c&3){
4
    case   0:u.b[0]=0x00;break;
5
    case   1:u.b[0]=0x0f;break;
6
    case   2:u.b[0]=0xf0;break;
7
    case   3:u.b[0]=0xff;break;
8
    }
9
  switch(c&12){ //oder switch((in>>=2)&3){ //case 0, case 1, case 2, case 3
10
    case   0:u.b[1]=0x00;break;
11
    case   4:u.b[1]=0x0f;break;
12
    case   8:u.b[1]=0xf0;break;
13
    case  12:u.b[1]=0xff;break;
14
    }
15
  switch(c&48){
16
    case   0:u.b[2]=0x00;break;
17
    case  16:u.b[2]=0x0f;break;
18
    case  32:u.b[2]=0xf0;break;
19
    case  48:u.b[2]=0xff;break;
20
    }
21
  switch(c&192){
22
    case   0:u.b[3]=0x00;break;
23
    case  64:u.b[3]=0x0f;break;
24
    case 128:u.b[3]=0xf0;break;
25
    case 192:u.b[3]=0xff;break;
26
    }

Wenn der gcc das gut optimiert (Jump-Adressberechnung aus den cases) ...

Außerdem stellt sich die Frage, ob ein uint32_t sinnvoll ist, denn er 
muss ja wieder auf die einzelnen Bytes im Memory aufgeteilt werden.
Besser direkt die Bytes (mittels Pointer?) schreiben.

von sigma9 (Gast)


Lesenswert?

eProfi schrieb:
>>   d = __builtin_avr_insert_bits (0xffff6666, in, 0);
> aha, nach 6 kommt f
>


in diesem Fall schon: Input hat 7 (nicht 8!) Bits, Output daher 28 
(nicht 32). Daher wollte ich in diesem Fall die obersten 4 Bits auf 0 
setzen - genau das macht dieser Code.


> Eine andere Idee:  int8_t c=PORTD; //zum Test, damit nichts wegoptimiert
> wird
>   register union{uint32_t i32;uint8_t b[4];}u;
>   switch(c&3){
>     case   0:u.b[0]=0x00;break;
>     case   1:u.b[0]=0x0f;break;
>     case   2:u.b[0]=0xf0;break;
>     case   3:u.b[0]=0xff;break;
>     }
>   switch(c&12){ //oder switch((in>>=2)&3){ //case 0, case 1, case 2,
> case 3
>     case   0:u.b[1]=0x00;break;
>     case   4:u.b[1]=0x0f;break;
>     case   8:u.b[1]=0xf0;break;
>     case  12:u.b[1]=0xff;break;
>     }
>   switch(c&48){
>     case   0:u.b[2]=0x00;break;
>     case  16:u.b[2]=0x0f;break;
>     case  32:u.b[2]=0xf0;break;
>     case  48:u.b[2]=0xff;break;
>     }
>   switch(c&192){
>     case   0:u.b[3]=0x00;break;
>     case  64:u.b[3]=0x0f;break;
>     case 128:u.b[3]=0xf0;break;
>     case 192:u.b[3]=0xff;break;
>     }
>
> Wenn der gcc das gut optimiert (Jump-Adressberechnung aus den cases) ...
>

aha... das ist mal ne völlig andere Idee: werde ich probieren.


> Außerdem stellt sich die Frage, ob ein uint32_t sinnvoll ist, denn er
> muss ja wieder auf die einzelnen Bytes im Memory aufgeteilt werden.
> Besser direkt die Bytes (mittels Pointer?) schreiben.


ja und nein: zum Aufsammeln schon - da macht die lib alle shifts etc 
schon richtig. Zum Reinschreiben sicher nicht - aber das Umcasten 
(direkt oder mittels union) ist ja nix anderes als "direkt die Bytes 
mittels Pointer schreiben". So machen das die (bisher) schnellsten 
Lösungen ja auch.

von sigma9 (Gast)


Lesenswert?

eProfi schrieb:
>   register union{uint32_t i32;uint8_t b[4];}u;

....

>     case 192:u.b[3]=0xff;break;
>     }


habs getestet: -oS ergibt 65 Takte
1
0000058c <variant_eprofi>:
2
 58c:  28 2f         mov  r18, r24
3
 58e:  83 70         andi  r24, 0x03  ; 3
4
 590:  82 30         cpi  r24, 0x02  ; 2
5
 592:  41 f0         breq  .+16       ; 0x5a4 <variant_eprofi+0x18>
6
 594:  83 30         cpi  r24, 0x03  ; 3
7
 596:  41 f0         breq  .+16       ; 0x5a8 <variant_eprofi+0x1c>
8
 598:  81 30         cpi  r24, 0x01  ; 1
9
 59a:  11 f0         breq  .+4        ; 0x5a0 <variant_eprofi+0x14>
10
 59c:  60 e0         ldi  r22, 0x00  ; 0
11
 59e:  05 c0         rjmp  .+10       ; 0x5aa <variant_eprofi+0x1e>
12
 5a0:  6f e0         ldi  r22, 0x0F  ; 15
13
 5a2:  03 c0         rjmp  .+6        ; 0x5aa <variant_eprofi+0x1e>
14
 5a4:  60 ef         ldi  r22, 0xF0  ; 240
15
 5a6:  01 c0         rjmp  .+2        ; 0x5aa <variant_eprofi+0x1e>
16
 5a8:  6f ef         ldi  r22, 0xFF  ; 255
17
 5aa:  32 2f         mov  r19, r18
18
 5ac:  3c 70         andi  r19, 0x0C  ; 12
19
 5ae:  34 30         cpi  r19, 0x04  ; 4
20
 5b0:  59 f0         breq  .+22       ; 0x5c8 <variant_eprofi+0x3c>
21
 5b2:  20 f4         brcc  .+8        ; 0x5bc <variant_eprofi+0x30>
22
 5b4:  31 11         cpse  r19, r1
23
 5b6:  0b c0         rjmp  .+22       ; 0x5ce <variant_eprofi+0x42>
24
 5b8:  70 e0         ldi  r23, 0x00  ; 0
25
 5ba:  09 c0         rjmp  .+18       ; 0x5ce <variant_eprofi+0x42>
26
 5bc:  38 30         cpi  r19, 0x08  ; 8
27
 5be:  31 f0         breq  .+12       ; 0x5cc <variant_eprofi+0x40>
28
 5c0:  3c 30         cpi  r19, 0x0C  ; 12
29
 5c2:  29 f4         brne  .+10       ; 0x5ce <variant_eprofi+0x42>
30
 5c4:  7f ef         ldi  r23, 0xFF  ; 255
31
 5c6:  03 c0         rjmp  .+6        ; 0x5ce <variant_eprofi+0x42>
32
 5c8:  7f e0         ldi  r23, 0x0F  ; 15
33
 5ca:  01 c0         rjmp  .+2        ; 0x5ce <variant_eprofi+0x42>
34
 5cc:  70 ef         ldi  r23, 0xF0  ; 240
35
 5ce:  32 2f         mov  r19, r18
36
 5d0:  30 73         andi  r19, 0x30  ; 48
37
 5d2:  30 31         cpi  r19, 0x10  ; 16
38
 5d4:  59 f0         breq  .+22       ; 0x5ec <variant_eprofi+0x60>
39
 5d6:  20 f4         brcc  .+8        ; 0x5e0 <variant_eprofi+0x54>
40
 5d8:  31 11         cpse  r19, r1
41
 5da:  0b c0         rjmp  .+22       ; 0x5f2 <variant_eprofi+0x66>
42
 5dc:  40 e0         ldi  r20, 0x00  ; 0
43
 5de:  09 c0         rjmp  .+18       ; 0x5f2 <variant_eprofi+0x66>
44
 5e0:  30 32         cpi  r19, 0x20  ; 32
45
 5e2:  31 f0         breq  .+12       ; 0x5f0 <variant_eprofi+0x64>
46
 5e4:  30 33         cpi  r19, 0x30  ; 48
47
 5e6:  29 f4         brne  .+10       ; 0x5f2 <variant_eprofi+0x66>
48
 5e8:  4f ef         ldi  r20, 0xFF  ; 255
49
 5ea:  03 c0         rjmp  .+6        ; 0x5f2 <variant_eprofi+0x66>
50
 5ec:  4f e0         ldi  r20, 0x0F  ; 15
51
 5ee:  01 c0         rjmp  .+2        ; 0x5f2 <variant_eprofi+0x66>
52
 5f0:  40 ef         ldi  r20, 0xF0  ; 240
53
 5f2:  20 7c         andi  r18, 0xC0  ; 192
54
 5f4:  20 34         cpi  r18, 0x40  ; 64
55
 5f6:  59 f0         breq  .+22       ; 0x60e <variant_eprofi+0x82>
56
 5f8:  20 f4         brcc  .+8        ; 0x602 <variant_eprofi+0x76>
57
 5fa:  21 11         cpse  r18, r1
58
 5fc:  0b c0         rjmp  .+22       ; 0x614 <variant_eprofi+0x88>
59
 5fe:  90 e0         ldi  r25, 0x00  ; 0
60
 600:  09 c0         rjmp  .+18       ; 0x614 <variant_eprofi+0x88>
61
 602:  20 38         cpi  r18, 0x80  ; 128
62
 604:  31 f0         breq  .+12       ; 0x612 <variant_eprofi+0x86>
63
 606:  20 3c         cpi  r18, 0xC0  ; 192
64
 608:  29 f4         brne  .+10       ; 0x614 <variant_eprofi+0x88>
65
 60a:  9f ef         ldi  r25, 0xFF  ; 255
66
 60c:  03 c0         rjmp  .+6        ; 0x614 <variant_eprofi+0x88>
67
 60e:  9f e0         ldi  r25, 0x0F  ; 15
68
 610:  01 c0         rjmp  .+2        ; 0x614 <variant_eprofi+0x88>
69
 612:  90 ef         ldi  r25, 0xF0  ; 240
70
 614:  84 2f         mov  r24, r20
71
 616:  08 95         ret


und mit Optimierung -o2 54 Takte
1
0000040a <variant_eprofi>:
2
     40a:  28 2f         mov  r18, r24
3
     40c:  23 70         andi  r18, 0x03  ; 3
4
     40e:  22 30         cpi  r18, 0x02  ; 2
5
     410:  09 f4         brne  .+2        ; 0x414 <variant_eprofi+0xa>
6
     412:  4c c0         rjmp  .+152      ; 0x4ac <variant_eprofi+0xa2>
7
     414:  23 30         cpi  r18, 0x03  ; 3
8
     416:  09 f4         brne  .+2        ; 0x41a <variant_eprofi+0x10>
9
     418:  47 c0         rjmp  .+142      ; 0x4a8 <variant_eprofi+0x9e>
10
     41a:  21 30         cpi  r18, 0x01  ; 1
11
     41c:  21 f1         breq  .+72       ; 0x466 <variant_eprofi+0x5c>
12
     41e:  60 e0         ldi  r22, 0x00  ; 0
13
     420:  28 2f         mov  r18, r24
14
     422:  2c 70         andi  r18, 0x0C  ; 12
15
     424:  24 30         cpi  r18, 0x04  ; 4
16
     426:  21 f1         breq  .+72       ; 0x470 <variant_eprofi+0x66>
17
     428:  25 30         cpi  r18, 0x05  ; 5
18
     42a:  c0 f1         brcs  .+112      ; 0x49c <variant_eprofi+0x92>
19
     42c:  28 30         cpi  r18, 0x08  ; 8
20
     42e:  d1 f1         breq  .+116      ; 0x4a4 <variant_eprofi+0x9a>
21
     430:  2c 30         cpi  r18, 0x0C  ; 12
22
     432:  09 f4         brne  .+2        ; 0x436 <variant_eprofi+0x2c>
23
     434:  7f ef         ldi  r23, 0xFF  ; 255
24
     436:  28 2f         mov  r18, r24
25
     438:  20 73         andi  r18, 0x30  ; 48
26
     43a:  20 31         cpi  r18, 0x10  ; 16
27
     43c:  f1 f0         breq  .+60       ; 0x47a <variant_eprofi+0x70>
28
     43e:  21 31         cpi  r18, 0x11  ; 17
29
     440:  48 f1         brcs  .+82       ; 0x494 <variant_eprofi+0x8a>
30
     442:  20 32         cpi  r18, 0x20  ; 32
31
     444:  c1 f1         breq  .+112      ; 0x4b6 <variant_eprofi+0xac>
32
     446:  20 33         cpi  r18, 0x30  ; 48
33
     448:  09 f4         brne  .+2        ; 0x44c <variant_eprofi+0x42>
34
     44a:  3f ef         ldi  r19, 0xFF  ; 255
35
     44c:  28 2f         mov  r18, r24
36
     44e:  20 7c         andi  r18, 0xC0  ; 192
37
     450:  20 34         cpi  r18, 0x40  ; 64
38
     452:  c1 f0         breq  .+48       ; 0x484 <variant_eprofi+0x7a>
39
     454:  21 34         cpi  r18, 0x41  ; 65
40
     456:  c8 f0         brcs  .+50       ; 0x48a <variant_eprofi+0x80>
41
     458:  20 38         cpi  r18, 0x80  ; 128
42
     45a:  51 f1         breq  .+84       ; 0x4b0 <variant_eprofi+0xa6>
43
     45c:  20 3c         cpi  r18, 0xC0  ; 192
44
     45e:  09 f4         brne  .+2        ; 0x462 <variant_eprofi+0x58>
45
     460:  9f ef         ldi  r25, 0xFF  ; 255
46
     462:  83 2f         mov  r24, r19
47
     464:  08 95         ret
48
     466:  6f e0         ldi  r22, 0x0F  ; 15
49
     468:  28 2f         mov  r18, r24
50
     46a:  2c 70         andi  r18, 0x0C  ; 12
51
     46c:  24 30         cpi  r18, 0x04  ; 4
52
     46e:  e1 f6         brne  .-72       ; 0x428 <variant_eprofi+0x1e>
53
     470:  7f e0         ldi  r23, 0x0F  ; 15
54
     472:  28 2f         mov  r18, r24
55
     474:  20 73         andi  r18, 0x30  ; 48
56
     476:  20 31         cpi  r18, 0x10  ; 16
57
     478:  11 f7         brne  .-60       ; 0x43e <variant_eprofi+0x34>
58
     47a:  3f e0         ldi  r19, 0x0F  ; 15
59
     47c:  28 2f         mov  r18, r24
60
     47e:  20 7c         andi  r18, 0xC0  ; 192
61
     480:  20 34         cpi  r18, 0x40  ; 64
62
     482:  41 f7         brne  .-48       ; 0x454 <variant_eprofi+0x4a>
63
     484:  9f e0         ldi  r25, 0x0F  ; 15
64
     486:  83 2f         mov  r24, r19
65
     488:  08 95         ret
66
     48a:  21 11         cpse  r18, r1
67
     48c:  ea cf         rjmp  .-44       ; 0x462 <variant_eprofi+0x58>
68
     48e:  90 e0         ldi  r25, 0x00  ; 0
69
     490:  83 2f         mov  r24, r19
70
     492:  08 95         ret
71
     494:  21 11         cpse  r18, r1
72
     496:  da cf         rjmp  .-76       ; 0x44c <variant_eprofi+0x42>
73
     498:  30 e0         ldi  r19, 0x00  ; 0
74
     49a:  d8 cf         rjmp  .-80       ; 0x44c <variant_eprofi+0x42>
75
     49c:  21 11         cpse  r18, r1
76
     49e:  cb cf         rjmp  .-106      ; 0x436 <variant_eprofi+0x2c>
77
     4a0:  70 e0         ldi  r23, 0x00  ; 0
78
     4a2:  c9 cf         rjmp  .-110      ; 0x436 <variant_eprofi+0x2c>
79
     4a4:  70 ef         ldi  r23, 0xF0  ; 240
80
     4a6:  c7 cf         rjmp  .-114      ; 0x436 <variant_eprofi+0x2c>
81
     4a8:  6f ef         ldi  r22, 0xFF  ; 255
82
     4aa:  ba cf         rjmp  .-140      ; 0x420 <variant_eprofi+0x16>
83
     4ac:  60 ef         ldi  r22, 0xF0  ; 240
84
     4ae:  b8 cf         rjmp  .-144      ; 0x420 <variant_eprofi+0x16>
85
     4b0:  90 ef         ldi  r25, 0xF0  ; 240
86
     4b2:  83 2f         mov  r24, r19
87
     4b4:  08 95         ret
88
     4b6:  30 ef         ldi  r19, 0xF0  ; 240
89
     4b8:  c9 cf         rjmp  .-110      ; 0x44c <variant_eprofi+0x42>


Fazit: sehr gut, aber nicht die schnellste Varante (31/32 Takte)

von Mampf F. (mampf) Benutzerseite


Lesenswert?

Was ist hiermit? Braucht aber 32 Bytes als LUT:
1
uint16_t lut[16]={
2
    0x0000, 0x000f, 0x00f0, 0x00ff, 0x0f00, 0x0f0f, 0x0ff0, 0x0fff,
3
    0xf000, 0xf00f, 0xf0f0, 0xf0ff, 0xff00, 0xff0f, 0xfff0, 0xffff
4
};
5
6
uint32_t  variant1 (uint8_t in)
7
{
8
    uint32_t result = 0;
9
    uint16_t *rptr = (uint16_t*) &result;
10
    
11
    *rptr = lut[in & 0xf];
12
    rptr++; in >>= 4;
13
    *rptr = lut[in & 0xf];
14
    return result;
15
}

: Bearbeitet durch User
von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Mampf F. schrieb:
> Was ist hiermit?

Kein gültiger C-Code :-)

von Mampf F. (mampf) Benutzerseite


Lesenswert?

Johann L. schrieb:
> Mampf F. schrieb:
>> Was ist hiermit?
>
> Kein gültiger C-Code :-)

Hö? Der Compiliert aber bei mir mit meinem AVRGCC ?

Was ist nicht gültig?

von dk5ee (Gast)


Lesenswert?

Jan's Version, nochmal komprimiert. kann das jemand mal auswerten, hab 
kein avrgcc hier..
1
//-------------------------------
2
uint32_t  variant_janders (uint8_t in)
3
//-------------------------------
4
{
5
  union {
6
    uint32_t all;
7
    uint8_t array[4];
8
  } result;
9
10
  for (uint8_t i=0;i<4;i++) {
11
    uint8_t tempvar=0; //für weniger arrayzugriffe
12
    if (in&0x01){ //ungerades bit
13
      tempvar = 0x0F;
14
    }
15
    if (in&0x02){ //gerades bit
16
      tempvar += 0xF0;
17
    }
18
    result.array[i]=tempvar; //merken
19
    in>>=2; //nächste 2 bits
20
  } 
21
  return (result.all);
22
}

von eProfi (Gast)


Lesenswert?

Danke fürs Ausprobieren!
Da muss man natürlich noch Hand anlegen!
Kann man ein Register auf den PC (Program Counter) addieren?
Habe ich nichts gefunden, nur über den Umweg Z-Register jmp(z).
IJMP Indirect Jump to (Z) PC ← Z None 2
aber wie kriegt man den PC ins Z? Push PC, Pop Z

@mampf, ja, auch eine sehr gute Idee!
>    uint32_t result = 0;
= 0 ist überflüssig

>    *rptr = lut[in & 0xf];
>     rptr++; in >>= 4;
>    *rptr = lut[in & 0xf];
besser / kürzer:
     *rptr++ = lut[in & 15];
     *rptr   = lut[in >> 4];


Oder mit einer union (weiß nicht, ob das register was bringt, lieber den 
Hack von oben probieren):
  register union{uint32_t L;uint16_t w[2];}u;
  u.w[0]=lut[in & 15];
  u.w[1]=lut[in >> 4];
  return u.L;

Oder wenn der GCC sich wegen der uint16_t recht anstellt:
uint8_t lut0[16]={
    0x00, 0x0f, 0xf0, 0xff, 0x00, 0x0f, 0xf0, 0xff,
    0x00, 0x0f, 0xf0, 0xff, 0x00, 0x0f, 0xf0, 0xff
};
uint8_t lut1[16]={
    0x00, 0x00, 0x00, 0x00, 0x0f, 0x0f, 0x0f, 0x0f,
    0xf0, 0xf0, 0xf0, 0xf0, 0xff, 0xff, 0xff, 0xff
};
  register union{uint32_t L; uint16_t b[4];}u; uint8_t tmp;
  u.b[0]=lut0[tmp = in & 15];
  u.b[1]=lut1[tmp];
  u.b[2]=lut0[tmp = in >> 4];
  u.b[3]=lut1[tmp];
  return u.L;

Die 32 Cycles schaffen wir damit aber nicht.
Die Skip-Befehle haben es schon in sich!

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Mampf F. schrieb:
> Johann L. schrieb:
>> Mampf F. schrieb:
>>> Was ist hiermit?
>>
>> Kein gültiger C-Code :-)
>
> Hö? Der Compiliert aber bei mir mit meinem AVRGCC ?
>
> Was ist nicht gültig?
1
In function 'variant1':
2
warning: dereferencing type-punned pointer might break strict-aliasing rules [-Wstrict-aliasing]
3
     uint16_t *rptr = (uint16_t*) &result;
4
     ^~~~~~~~

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

...und ich verstehe nicht ganz was die Tabellen sollen.  Jede der "lut"s 
hat ja bereits fast die Größe des oben vorgestellten Codes.

: Bearbeitet durch User
von Peter II (Gast)


Lesenswert?

das schnellste wird wohl eine große lut sein.
1
uint32_t  variant1 (uint8_t in)
2
{
3
  Switch( in ) {
4
     case 0: return xx;
5
     case 1: return xx;
6
     case 2: return xx;
7
     case 255: return xx;
8
}

sollte der GCC als ein Sprung umsetzen. Kostet halt 512byte Flash.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Peter II schrieb:
> das schnellste wird wohl eine große lut sein.
>
>
1
uint32_t  variant1 (uint8_t in)
2
> {
3
>   Switch( in ) {
4
>      case 0: return xx;
5
>      case 1: return xx;
6
>      case 2: return xx;
7
>      case 255: return xx;
8
> }
>
> sollte der GCC als ein Sprung umsetzen. Kostet halt 512byte Flash.

Wird gerne auch als LUT umgesetzt, und die liegt dam im RAM *autsch* 
(außer für AVR_TINY oder mit -fno-tree-switch-conversion).  Und die 
Metrik des TO ist -Os, was durch die LUT oder Jump-Tabelle komplett 
geshreddert wird :-)

Und der o.g. Code von

Beitrag "Re: Bitmanipulation beschleunigen"

wird ja noch etwas kleiner, da nur 7 Bits benötigt werden, d.h.

> if (in & (1u << 7)) out |= 0xful << (4*7);

kann entfallen.

: Bearbeitet durch User
von eProfi (Gast)


Lesenswert?

>  Kostet halt 512byte Flash.
Oh nein, das reicht nicht. Wir brauchen ja 4 Bytes pro Eintrag, und die 
müssen geladen werden und einen Absprung brauchen wir ja auch für jeden 
Case, also 256*(8+2)=2,5 K.

Da ist eine echte Table (im progmem oder wie das heißt) besser:
uint32 lut[256] PROGMEM ={0x00000000, 0x0000000f, 0x000000f0, 
0x000000ff,
.....}
    return lut[in];

von eProfi (Gast)


Lesenswert?

Ah, stimmt, nur 7 Bits, also alles halb so groß (256 --> 128).

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Womit sich einmal mehr bestätigt:
1
Jedwede Optimierung bringt beliebig schlechte Resultate,
2
sofern man sie nur lange genug weiter optimiert.

(frei nach Knuth :-)

von eProfi (Gast)


Lesenswert?

Kurze Zwischenfrage, wenn viele Experten hier "zusammensitzen":

Ich habe auf diesem PC nur einen uralten (2010) GCC 4.4.4 drauf.
Vielleicht ist das bei moderneren besser gelöst:

#define MOSI (1<<PCx)
  for(uint8_t m=128;m;DDRD&m?PORTC|=MOSI:(PORTC&=~MOSI),m=m/2);

GCC checkt genau, was ich will, übersetzt es aber sehr umständlich, er 
nimmt einen 16-bit Schleifenzähler und zählt von 0000 bis 0008.
1
     e2a:  90 e8         ldi  r25, 0x80  ; 128
2
     e2c:  20 e0         ldi  r18, 0x00  ; 0 LoopCntL
3
     e2e:  30 e0         ldi  r19, 0x00  ; 0 LoopCntH
4
     e30:  8a b1         in  r24, 0x0a  ; 10
5
     e32:  89 23         and  r24, r25
6
     e34:  09 f4         brne  .+2        ; 0xe38 <__stack+0x539>
7
     e36:  21 c1         rjmp  .+578      ; 0x107a <__stack+0x77b>
8
     e38:  47 9a         sbi  0x08, 7  ; 8
9
     e3a:  88 b1         in  r24, 0x08  ; 8
10
     e3c:  96 95         lsr  r25           ;m>>=1
11
     e3e:  2f 5f         subi  r18, 0xFF  ; 255 CntL++
12
     e40:  3f 4f         sbci  r19, 0xFF  ; 255 CntH++
13
     e42:  28 30         cpi  r18, 0x08  ; 8   8 Loops?
14
     e44:  31 05         cpc  r19, r1       ;r1 ist ZERO
15
     e46:  a1 f7         brne  .-24       ; 0xe30 <__stack+0x531>
16
...
17
    107a:  47 98         cbi  0x08, 7  ; 8
18
    107c:  88 b1         in  r24, 0x08  ; 8
19
    107e:  de ce         rjmp  .-580      ; 0xe3c <__stack+0x53d>
Anstatt dass er die Maske m mit als "Zähler" verwendet und nach dem
LSR m gleich mit bne zurückspringt.

Mag das bitte jemand mit aktueller GCC-Version für mich probieren?

von eProfi (Gast)


Lesenswert?

Das DDRD habe ich nur als Beispiel genommen, damit er irgendein 
volatile-Register nimmt und keine Konstante.

von sigma9 (Gast)


Lesenswert?

@eProfi:

>
> Die 32 Cycles schaffen wir damit aber nicht.
> Die Skip-Befehle haben es schon in sich!


Die LUT mit 16/32 Bytes wäre zu tolerieren, doch es gibt für mich ein 
anderes Problem: ich brauche diesen Code nicht nur für 4-fach aufblähen 
(danach hatte ich zu Anfang gefragt), sondern auch für 3 und 2. Die (bis 
jetzt) Rekordlösung von Johann hat zudem den Charme, dass sie sich ganz 
leicht auch für 3 oder 2 modifizieren lässt. Alle hier diskutierten 
Varianten mit LUT leider nicht -  die nutzen aus, dass 4 = 8/2 ist.

Im Moment tendiere ich daher zu dieser.

@alle:
klar ist ne Tabelle mit einem 7-bit Index unschlagbar hinsichtlich 
Geschwindigkeit - aber auch viel zu gross für mich.

@Johann:
Ich liebe auch den Begriff kaputtoptimieren.

@alle,leicht OT:
Ich bin dankbar für die hier gebotene Hilfe der Schwarm-Intelligenz.
Allerdings stelle ich mir immer wieder die Frage, wie ich meine eigenen 
Fähigkeiten verbessern könnte. Viel hat mir geholfen, den Sourcecode 
eines nicht-trivialen Programmes zu studieren, ich erwähne als Beispiel 
einen TCP/IP-Stack. Den habe ich solange {angeschaut, modifiziert, durch 
den Compiler gejagt}loop, bis ich (denke ich...) jede Zeile verstanden 
hatte.
Frage also: wo finde ich anderen Quellcode, der frei ist, zum AVR passt 
und an dem man was lernen kann? Irgendwelche Vorschläge?

von H.Joachim S. (crazyhorse)


Lesenswert?

sigma9 schrieb:
> Ich bin dankbar für die hier gebotene Hilfe der Schwarm-Intelligenz.
> Allerdings stelle ich mir immer wieder die Frage, wie ich meine eigenen
> Fähigkeiten verbessern könnte.

Naja, das ist so eine Sache. Es gibt immer wieder irgendwelche 
hochoptimierten Lösungen - zum Glück werden sie rel. selten tatsächlich 
benötigt. Wenn sie nötig sind, muss man danach suchen - meistens sind 
sie aber gar nicht erforderlich. Ich beschäftige mich dann damit, wenn 
Engpässe auftauchen. Manchmal macht es auch einfach Spass, ohne jeden 
Nutzen. Ist auch ein Argument, allerdings nicht wirtschaftlich. Wenn es 
rein passt und ich mit der Laufzeit leben kann, ist die Lösung die 
beste, die ich am schnellsten hingeschrieben haben oder die erste 
Optimierung, die die Anforderungen erschlägt. Man kann sich da endlos 
verzetteln, ist aber akademisch. Man fühlt sich gut, erreicht 
letztendlich aber nur, dass statt x% x+y% im Leerlauf verbracht werden. 
Nutzen Null, Aufwand gross. Persönliche "Investitionen" in den grossen 
Überblick sind hilfreicher als gesuchte und vielleicht gefundene 
Optimierungen in Kleinigkeiten.
Ich erinnere mich noch gut an meine Z80-Zeit, Thema sich selbst 
modifizierende Programme. Damit konnte man scheinbar unmögliches möglich 
machen, Speicherbedarf und Laufzeit war oft genug ein Thema - da konnte 
man sich richtig austoben. Heute nimmt man einfach den ausreichenden 
Prozessor, fertig. Einen gewissen Bedarf an Optimierungen gibts, wenn 
man auf fertiger Hardware irgendwas nachträglich reinbasteln muss. Und 
da muss man wieder unterscheiden: ist es Hobby oder Geschäft?

von Tim T. (tim_taylor) Benutzerseite


Lesenswert?

Also ohne groß drüber nachzudenken:
1
uint32_t variant(uint8_t input) {
2
3
 uint32_t result = 0;
4
5
 if (input & 0x01) result = 0x0000000f;
6
 if (input & 0x02) result |= 0x000000f0; 
7
 if (input & 0x04) result |= 0x00000f00;
8
 if (input & 0x08) result |= 0x0000f000;
9
 if (input & 0x10) result |= 0x000f0000;
10
 if (input & 0x20) result |= 0x00f00000;
11
 if (input & 0x40) result |= 0x0f000000;
12
13
 return result;
14
}

Und was der Compiler draus baut:
1
+0000001C:   FD80        SBRC      R24,0
2
+0000001D:   C005        RJMP      PC+0x0006
3
+0000001E:   E020        LDI       R18,0x00
4
+0000001F:   E030        LDI       R19,0x00
5
+00000020:   E040        LDI       R20,0x00
6
+00000021:   E050        LDI       R21,0x00
7
+00000022:   C004        RJMP      PC+0x0005
8
+00000023:   E02F        LDI       R18,0x0F
9
+00000024:   E030        LDI       R19,0x00
10
+00000025:   E040        LDI       R20,0x00
11
+00000026:   E050        LDI       R21,0x00
12
13
10:        if (input & 0x02) result |= 0x000000f0; 
14
+00000027:   FD81        SBRC      R24,1
15
+00000028:   6F20        ORI       R18,0xF0
16
17
11:        if (input & 0x04) result |= 0x00000f00;
18
+00000029:   FD82        SBRC      R24,2
19
+0000002A:   603F        ORI       R19,0x0F
20
21
12:        if (input & 0x08) result |= 0x0000f000;
22
+0000002B:   FD83        SBRC      R24,3
23
+0000002C:   6F30        ORI       R19,0xF0
24
25
13:        if (input & 0x10) result |= 0x000f0000;
26
+0000002D:   FD84        SBRC      R24,4
27
+0000002E:   604F        ORI       R20,0x0F
28
29
14:        if (input & 0x20) result |= 0x00f00000;
30
+0000002F:   FD85        SBRC      R24,5
31
+00000030:   6F40        ORI       R20,0xF0
32
33
15:        if (input & 0x40) result |= 0x0f000000;
34
+00000031:   FD86        SBRC      R24,6
35
+00000032:   605F        ORI       R21,0x0F
36
37
+00000033:   01B9        MOVW      R22,R18
38
+00000034:   01CA        MOVW      R24,R20
39
+00000035:   9508        RET

Sind dann mit Rücksprung 25 Takte...

von sigma9 (Gast)


Lesenswert?

H.Joachim S. schrieb:

> Naja, das ist so eine Sache. Es gibt immer wieder irgendwelche
> hochoptimierten Lösungen - zum Glück werden sie rel. selten tatsächlich
> benötigt. Wenn sie nötig sind, muss man danach suchen - meistens sind
> sie aber gar nicht erforderlich.


Völlig einverstanden. Im hier diskutierten Fall habe ich bei 800 Takten 
angefangen: zääääääher Display-Aufbau, nicht zu gebrauchen. Ob ich nun 
bei 45 (optimiert) oder 32 (hochoptimiert) ende, ist idT nur von 
akademischem Interesse und der Kitzel, herausfinden, was geht.


> Ich beschäftige mich dann damit, wenn
> Engpässe auftauchen. Manchmal macht es auch einfach Spass, ohne jeden
> Nutzen.


Meine Erfahrung ist: ja, es macht Spaß, aber es ist eben nicht ohne 
jeden Nutzen. Kurzfristig mag das so aussehen, aber es kommt immer der 
Tag, an dem einem eine früher (mit Spaß!) erworbene Erkenntnis den A.sch 
rettet.


> Ist auch ein Argument, allerdings nicht wirtschaftlich. Wenn es
> rein passt und ich mit der Laufzeit leben kann, ist die Lösung die
> beste, die ich am schnellsten hingeschrieben haben oder die erste
> Optimierung, die die Anforderungen erschlägt.


Korrekt - leider. Dieses Denken ist weit verbreitet und auch 
nachvollziehbar. Nur: wirkliche neue Erkenntnisse/Ergebnisse gibt es 
damit nicht. Man lese zB über die Entwicklung des ersten Transistors bei 
IBM - hoch spannend.

> Man kann sich da endlos
> verzetteln, ist aber akademisch. Man fühlt sich gut, erreicht
> letztendlich aber nur, dass statt x% x+y% im Leerlauf verbracht werden.
> Nutzen Null, Aufwand gross. Persönliche "Investitionen" in den grossen
> Überblick sind hilfreicher als gesuchte und vielleicht gefundene
> Optimierungen in Kleinigkeiten.

Zustimmung.

> Ich erinnere mich noch gut an meine Z80-Zeit, Thema sich selbst
> modifizierende Programme. Damit konnte man scheinbar unmögliches möglich
> machen, Speicherbedarf und Laufzeit war oft genug ein Thema - da konnte
> man sich richtig austoben.


Oh ja: ich erinnere mich, dass ich riesige Z80-ASM Sourcen 
umstrukturiert habe, um möglichst viele JP durch JR ersetzen, bringt 
jeweils EIN Byte Speicher. Die logische Struktur der Programme ging 
dabei völlig vor die Hunde.



> Heute nimmt man einfach den ausreichenden
> Prozessor, fertig. Einen gewissen Bedarf an Optimierungen gibts, wenn
> man auf fertiger Hardware irgendwas nachträglich reinbasteln muss. Und
> da muss man wieder unterscheiden: ist es Hobby oder Geschäft?


Auch wahr. Heute hat niemand mehr Zeit=Geld, etwas wirklich zu 
verstehen.
Dass dabei riesige Verluste entstehen, nur weil das Rad jedes Mal neu 
erfunden werden muss - egal, Hauptsache der Quartalsbericht stimmt.

Trotzdem kann ich für mich privat (Hobby) den Anspruch haben, Zeit 
"sinnlos" zu investieren und etwas zu lernen/verstehen. Dahin ging meine 
Frage.



/s

von sigma9 (Gast)


Lesenswert?

Tim T. schrieb:
> Also ohne groß drüber nachzudenken:
> uint32_t variant(uint8_t input) {
>

....

> +00000034:   01CA        MOVW      R24,R20
> +00000035:   9508        RET
>
> Sind dann mit Rücksprung 25 Takte...



na also: ist der GCC als doch intelligent genug zu erkennen, dass 
trotz 32bit Variable über 4 Register beim verodern mit solchen 
Konstanten jeweils nur ein Register angefasst werden muss - nichts 
anderes erreichen die anderen Lösungen (z.B. mit type casting oder 
union) von Hand.

Sehr schön. Nur Nachteil für mich (ja, ich weiß, neue Bedingungen, nicht 
im TO): ich brauche das auch für 3-fach und 2-fach aufblähen.
Johanns Lösung ist portierbar und bleibt bei ca 35 Takten.

Trotzdem Danke für den Beitrag: hält jetzt den Rekord für das 4er 
Problem

von Yalu X. (yalu) (Moderator)


Lesenswert?

Tim T. schrieb:
> Also ohne groß drüber nachzudenken:
>
> uint32_t variant(uint8_t input) {
>  ...
> }

Und worin liegt jetzt der wesentliche Unterschied zu Johanns Code?

von Mampf F. (mampf) Benutzerseite


Lesenswert?

Johann L. schrieb:
> In function 'variant1':
> warning: dereferencing type-punned pointer might break strict-aliasing
> rules [-Wstrict-aliasing]
>      uint16_t *rptr = (uint16_t*) &result;
>      ^~~~~~~~

Ach, das ist doch nur für Leute, die nicht wissen, was sie tun ;-)

von sigma9 (Gast)


Lesenswert?

Mampf F. schrieb:
> Johann L. schrieb:
>> In function 'variant1':
>> warning: dereferencing type-punned pointer might break strict-aliasing
>> rules [-Wstrict-aliasing]
>>      uint16_t *rptr = (uint16_t*) &result;
>>      ^~~~~~~~
>
> Ach, das ist doch nur für Leute, die nicht wissen, was sie tun ;-)


...und wenn man statt type-casting beides in eine union steckt, 
resultiert das gleiche (siehe andere Lösungen) und der Compiler ist auch 
glücklich.

von H.Joachim S. (crazyhorse)


Lesenswert?

sigma9 schrieb:
> Kurzfristig mag das so aussehen, aber es kommt immer der
> Tag, an dem einem eine früher (mit Spaß!) erworbene Erkenntnis den A.sch
> rettet.

Exakt dieses Problem wirst du wahrscheinlich nie wieder haben bzw. wenn 
du es irgendwann mal wieder brauchst die Lösung zumindest halb vergessen 
:-).
Wichtiger ist die Erkenntnis, dass im Zweifelsfall (fast immer) noch was 
geht wenn es nötig wird.

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.