Jemand fit in AVR Assembler?

[Christian (dragony)]

Ich habe da ein Problem, was ich nicht vernünftig gelöst bekomme.

Ein Datenwert 24-Bit signed ist in den Registern r16:r19 gespeichert. 
Ich will jetzt den Wert solange durch 2 teilen, bis er in die Register 
r16:r18 passt, also effektiv den Datenwert in 16-Bit signed umwandeln.

Unsigned ist leicht:

0:
tst r18
breq 1f
lsr r18
ror r17
ror r16
rjmp 0b
1:

Signed bekomme ich nicht vernünftig hin. asr macht bei negativen 
Ausgangswerten aus dem r18 irgendwann ein 0xFF. Bei positiven wird es zu 
0x00. Einfach auf 255 und 0 testen geht nicht, da bei negativen Werten 
nicht nur r18 255 sein muss, sondern r17 auch noch negativ. Mit 
Verzweigungen bekomme ich es hin, aber das muss doch einfacher gehen....

Hat jemand eine Idee?

[foobar (Gast)]

Was soll das bringen?  Ohne die Anzahl der durchgeführten Shifts zu 
wissen ist der 16-Bit-Wert nichtssagend.  Mach's wie alle anderen auch: 
schmeiß die unteren 8 Bit einfach weg.

[Christian (dragony)]

Doch, bringt was. Es ist eine Statistik, die am Ende "Summe" durch 
"Anzahl" teilt. Teile ich beide Werte durch 2, kommt am Ende das gleiche 
bei raus (+ Rundungsfehler, der egal ist). Ich habe das hier aber der 
Einfachheit halber weggelassen.

[Irgend W. (Firma: egal) (irgendwer)]

foobar schrieb:
> Was soll das bringen?  Ohne die Anzahl der durchgeführten Shifts
> zu
> wissen ist der 16-Bit-Wert nichtssagend.  Mach's wie alle anderen auch:
> schmeiß die unteren 8 Bit einfach weg.

Das ist mit großem Abstand das einfachste. Bei allem anderen ist das 
Problem das das Signed-Bit ja immer an der höchstwertigen Stelle des 
24Bit bzw. 16Bit wertes stehen muss. Wenn du z.B. den 24Bit-Wert um eine 
Position verschiebst steht das Signed ja an keiner gültigen Stelle mehr. 
Erst wenn du achtmal schiebst gibt es wieder einen gültigen 16Bit 
Signed-Wert.

Eventuell das Signed-Bit extrahieren/entfernen und separat speichern und 
nach dem ganzen geschiebe wieder an der richtigen Stelle des 16Bit 
Wertes einfügen.

[Ralf (Gast)]

Irgend W. schrieb:
> Eventuell das Signed-Bit extrahieren/entfernen und separat speichern

Sinnvollerweise im T-Flag via BST/BLD.

[Oliver S. (oliverso)]

Irgend W. schrieb:
> Das ist mit großem Abstand das einfachste. Bei allem anderen ist das
> Problem das das Signed-Bit ja immer an der höchstwertigen Stelle des
> 24Bit bzw. 16Bit wertes stehen muss. Wenn du z.B. den 24Bit-Wert um eine
> Position verschiebst steht das Signed ja an keiner gültigen Stelle mehr.
> Erst wenn du achtmal schiebst gibt es wieder einen gültigen 16Bit
> Signed-Wert.

Daher haben so ungefähr alle Prozessoren seit Erfindung des sign-bits 
einen arithmethischen Shift-Befehl. Auf dem AVR ist das asr.

Aus der Beschreibung:

„This operation effectively divides a signed value by two without 
changing its sign“

Oliver

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Irgend W. schrieb:
> Bei allem anderen ist das Problem das das Signed-Bit ja immer an der
> höchstwertigen Stelle des 24Bit bzw. 16Bit wertes stehen muss.
Es gibt kein "Signed-Bit".
Das "linkeste" Bit zeigt zwar an, ob es eine negative Zahl ist, aber ein 
simples Invertieren dieses vermeintlichen "Signed-Bits" macht eben aus 
einer negativen Zahl keine positive Zahl mit gleichem Betrag.

Christian schrieb:
> Ein Datenwert 24-Bit signed ist in den Registern r16:r19 gespeichert.
> Ich will jetzt den Wert solange durch 2 teilen, bis er in die Register
> r16:r18 passt
Definiere "in r16:r18 passt". Willst du den Wert da irgendwie "maximal 
ausssteuern"?
Also sowas wie das hier:

00001111 00110011 00100100 --> 000000000 01111001 10011001
11000111 01010101 11001100 --> 111111111 10001110 10101011
11110001 01010101 11001100 --> 111111111 10001010 10101110
11111110 00001110 00111000 --> 111111111 10000011 10001110

Wozu braucht man sowas?

> asr macht bei negativen Ausgangswerten aus dem r18 irgendwann ein 0xFF.
> Bei positiven wird es zu 0x00. Einfach auf 255 und 0 testen geht nicht
Du musst, wenn das r18 FF oder 00 wird, den ganzen Klimbim einfach noch 
1 Bit weiterschieben. Das wars.

Christian schrieb:
> also effektiv den Datenwert in 16-Bit signed umwandeln.
Um aus einem 24-Bit Wert einen "gleichwertigen" 16-Bit Wert zu machen, 
schneidet (wie schon erwähnt) der Rest der Welt einfach die 
minderwertigen 8 Bits weg:

00001111 00110011 00100100 --> 00001111 00110011
11000111 01010101 11001100 --> 11000111 01010101 
11110001 01010101 11001100 --> 11110001 01010101
11111110 00001110 00111000 --> 11111110 00001110

Das ist dann in etwa eine Division durch 256.

[Christian (dragony)]

Ne abschneiden ist nicht drin. /256 wäre zu ungenau, deshalb /2.
Mittlerweile habe ich aber eine Lösung gefunden. Einfach nach einem brvs 
mit dem noch gesetztem C-Flag ein ror auf alle Register machen. Das 
kommt mir zwar irgendwie n bissl sehr "hackig" vor, aber bei allen 
Testbeispielen hat es funktioniert.

[Hermann Kokoschka (Gast)]

Christian schrieb:
> Ne abschneiden ist nicht drin. /256 wäre zu ungenau, deshalb /2.

Zeig doch bitte mal anhand Deiner Test in Binärdarstellung
wo der Unterschied ist.

Mal interessehalber gefragt.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Christian schrieb:
> Ne abschneiden ist nicht drin.
Du willst doch von 24 auf 16 Bits kommen. Wie soll das gehen, ohne 
dass was weggeschnitten wird?

> /256 wäre zu ungenau, deshalb /2.
Und was kommt heraus, wenn du 8 mal durch 2 teilst?

Was ist (((((((((512/2)/2)/2.../2)? Richtig: 2.

Und was ist 512/256?

> Mittlerweile habe ich aber eine Lösung gefunden. Einfach nach einem brvs
> mit dem noch gesetztem C-Flag ein ror auf alle Register machen.
Wie ich schon sagte: einfach noch ein Bit weiterschieben...

[c-hater (Gast)]

Christian schrieb:

> Doch, bringt was. Es ist eine Statistik, die am Ende "Summe" durch
> "Anzahl" teilt. Teile ich beide Werte durch 2, kommt am Ende das gleiche
> bei raus (+ Rundungsfehler, der egal ist). Ich habe das hier aber der
> Einfachheit halber weggelassen.

Dann ist doch die ganze Operation völlig überflüssig. Teile einfach die 
24-Bit-Werte durch die Anzahl und alles ist gut. Und ohne zusätzliche 
Rundungsverluste (außer dem unvermeidlichen durch die Integer-Division).

[Haremari (Gast)]

Interessante Problemstellung.

Ich würde anfangs einmal überprüfen, ob alle 9 Bits in r18[7:0] und 
r17[7] entweder komplett 1 oder komplett 0 sind. Dann wären wir sofort 
fertig. Andernfalls ist klar, dass wir mindestens einmal shiften müssen.

Wenn Register r18 nach dem ASR denselben Wert enthält wie vorher, dann 
ist es zwangsläufig entweder 0x00 oder 0xff. In dem Fall waren vor dem 
Shift die oberen 8 Bits gleich, nach dem Shift folglich die oberen 9 
Bits. Das heißt, in dem Fall wären wir nach dem Shift fertig. 
Andernfalls müssen wir weitershiften.

        mov r1, r17
        lsl r1      ;r17[7] in carry kopieren
        eor r1, r1
        adc r1, r18 ;ist r18 + carry = 0?
        breq fertig ;wenn ja, kein shift nötig
weiter: mov r1, r18
        asr r18     ;sonst so lange shiften...
        ror r17
        ror r16
        eor r1, r18 ;...bis r18 gleich blieb
        brne weiter
fertig: ret

Vermutlich bekommt man die initiale Prüfung noch irgendwie auf 3 
Instruktionen + Branch eingedampft, wenn man den Ehrgeiz hat.

[Hermann Kokoschka (Gast)]

Christian schrieb:
> Ne abschneiden ist nicht drin. /256 wäre zu ungenau, deshalb /2

Lothar M. schrieb:
> Und was kommt heraus, wenn du 8 mal durch 2 teilst?

Hermann Kokoschka schrieb:
> Zeig doch bitte mal anhand Deiner Test in Binärdarstellung
> wo der Unterschied ist.

Wird der TO sich dazu jemals äussern?
UND WANN wird das sein?

[avr (Gast)]

Wie hast du dir denn die Variante mit Verzweigungen vorgestellt? So ist 
es eigentlich immer noch ziemlich linear, wenn auch etwas langsamer als 
die Variante vom vorherigen Post.

0:
tst r18
breq 1f
cpi r18, 255
sbrc r17, 7
breq 1f
asr r18
ror r17
ror r16
rjmp 0b
1:

[Johann L. (gjlayde)]

Solange schieben, bis die oberen 9 Bits gleich sind.
Wenn das der Fall ist, gilt r19:r16 = sign_extend(r18:r16) und man kann 
die Schleife abbrechen weil r19 aus Kopien des Sign-Bits von r18 
besteht:

tmp = 0

.L_loop:
    mov tmp, r18
    lsl tmp
    sbc tmp, tmp
    ;; Test whether r19 = 0bhhhhhhhh where h = r18.7.
    cp  tmp, r19
    breq .L_done
    ;; Shift right
    asr r19
    lsr r18
    lsr r17
    lsr r16
    rjmp .L_loop
.L_done:

Das Ergebnis ist dann der gesuchte 24-Bit signed Wert in r18.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Johann L. schrieb:
> Solange schieben, bis die oberen 9 Bits gleich sind.
Mal angenommen, wir gehen von einer 24-Bit Binärzahl wie z.B.

11111101 01010101 0101010101 = 0xFD5555 = -174763

aus. Dann kommt nach diesem seltsamen "Ausrichten" und 3 
Schiebevorgängen eine 16-Bit Zahl mit

10101010 1010101010 = 0xAAAA = -174763 = -21846

heraus. Aber 0xAAAA kommt eben auch heraus, wenn ich das hier 5 mal 
schiebe:

11010101 01010101 0101010101 = 0xD55555 = -2796203

Wenn man gnauer nachdenkt, dann sieht man, dass es für jedes 16-Bit 
Resultat somit 8 mögliche 24-Bit-Eingangswerte gibt.

Fazit: ich frage mich noch immer, was
ich schon schrieb:
>>> Wozu braucht man sowas?

[Johann L. (gjlayde)]

Lothar M. schrieb:
> Johann L. schrieb:
>> Solange schieben, bis die oberen 9 Bits gleich sind.
> Mal angenommen, wir gehen von einer 24-Bit Binärzahl wie z.B.
>
> 11111101 01010101 01010101 = 0xFD5555 = -174763
>
> aus. Dann kommt nach diesem seltsamen "Ausrichten" und 3
> Schiebevorgängen eine 16-Bit Zahl mit
>
> 10101010 10101010 = 0xAAAA = -174763 = -21846
>
> heraus. Aber 0xAAAA kommt eben auch heraus, wenn ich das hier 5 mal
> schiebe:
>
> 11010101 01010101 01010101 = 0xD55555 = -2796203

Man müsste es 7× schieben?  Es gibt ja 1 redundantes Sign-Bit

11010101 01010101 01010101
-^------ = MSB
^------- = redundant
und nach dem Shiften wird man 8 redundante Sign-Bits im oberen Byte 
haben. Ergebnis nach 7× ASR:

11111111 10101010 10101010 = 0xAAAA = -21846

Wobei der TO einen 24-Bit Wert irgendwo in einem 32-Bit Wert hat, und 
die normalisierte Darstellung als 24-Bit Wert sucht.

> Fazit: ich frage mich noch immer, was
> ich schon schrieb:
>>> Wozu braucht man sowas?

Das weiß nur der TO.

Vermutlich hatte er Probleme damit, den 24-Bit Wert zu extrahieren und 
die Schleife zu basteln.  Wenn noch andere Werte parallel dazu zu 
skalieren sind, ist das ja einfach in die Schleife einzubauen.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

Johann L. schrieb:
> Man müsste es 7× schieben?
Richtig. Aber an der grundlegenden Frage ändert sich nichts...

Christian schrieb:
> aber bei allen Testbeispielen hat es funktioniert.
Zeig doch mal ein paar dieser Testbeispiele mit zusammengehörenden 
24-Bit und 16-Bit-Werten.

[Peter D. (peda)]

Wenn man sich mit Rechnen in Assembler schwer tut, dann kann man es doch 
einfach einen C-Compiler machen lassen. Der AVR-GCC kann bis int64_t 
bzw. uint64_t rechnen.
Man kann sogar Assembler- und C-Objekte zusammen linken. Der 
Gnu-Assembler ist Bestandteil der GCC Installation.

[Johann L. (gjlayde)]

Johann L. schrieb:
> Solange schieben, bis die oberen 9 Bits gleich sind.
> Wenn das der Fall ist, gilt r19:r16 = sign_extend(r18:r16) und man kann
> die Schleife abbrechen weil r19 aus Kopien des Sign-Bits von r18
> besteht:
>
>

> tmp = 0
> 
> [...]
>     ;; Shift right
>     asr r19
>     lsr r18
>     lsr r17
>     lsr r16
>     rjmp .L_loop
> .L_done:
>

> Das Ergebnis ist dann der gesuchte 24-Bit signed Wert in r18.

LSR ist natürlich die falsche Instruktion, zum Shift muss es ROR sein:

tmp = 0
;; Input  in R19:R16
;; Output in R18:R16
.L_loop:
    mov tmp, r18
    lsl tmp
    sbc tmp, tmp
    ;; Test whether r19 = 0bhhhhhhhh where h = r18.7.
    cp  tmp, r19
    breq .L_done
    ;; Shift right
    asr r19
    ror r18
    ror r17
    ror r16
    rjmp .L_loop
.L_done:

[Michael B. (laberkopp)]

Lothar M. schrieb:
> Fazit: ich frage mich noch immer, was
> ich schon schrieb:
>>>> Wozu braucht man sowas?

Das liegt daran, dass die Fragenden nur die Hälfte ihres Problems 
schildern.

Macht Dutzende Nachfragen nötig.

Er will

int32_t a;
int32_t b;

while ( ( (a&0xFFFF8000)!=0 && (a&0xFFFF8000)!=0xFFFF8000 )
|| ( (b&0xFFFF8000)!=0 && (b&0xFFFF8000)!=0xFFFF8000 ) )
{
   a>>=1;
   b>>=1;
}
return (int16_t)a/(int16_t)b;

also so lange a oder b mehr als 16 bit haben, werden beide gleichzeitiog
durch 2 geteilt (Stellenverlust = Auflösungsverlust wird in Kauf 
genommen)
damit man sie hinterher beispielsweise mit einer 16 bit Division teilen 
kann.

Er könnte 0x80000000 vorher addieren und hinterher 0x8000 subtrahieren.

[Ralf G. (ralg)]

Christian schrieb:
> Ein Datenwert 24-Bit signed ist in den Registern r16:r19 gespeichert.
> Ich will jetzt den Wert solange durch 2 teilen, bis er in die Register
> r16:r18 passt, also effektiv den Datenwert in 16-Bit signed umwandeln.

(sicherlich r16:r18 bzw. r16:r17?)
Du willst eine Zahl solange durch zwei teilen, bis diese gerade so nur 
noch 16Bit benötigt. Ist das so richtig interpretiert? (Wenn nein, 'rjmp 
ENDE')

Mal im Zehner-System gedacht:
Ich habe mehrere Zahlen, die mir zu groß sind. Die sollen alle nur vier 
Stellen haben.
z.B.:
1234567, 12345678, 12345
Jetzt 'shifte' ich das solange nach rechts, bis nur noch vier Stellen 
übrig sind. Ergibt: 1234, 1234, 1234

Christian schrieb:
> Doch, bringt was. Es ist eine Statistik,

Was soll das für eine Statistik werden?

ENDE:

Oder soll die betragsmäßig größte Zahl aus einer Liste als Referenz 
herhalten?

[Thilo L. (bc107)]

Ich denke, er will ALLE Zahlen um die gleiche Anzahl nach rechts 
schieben, bis die größte der Zahlen in 16bit passt.

[Eberhard H. (sepic)]

Christian schrieb:
> Hat jemand eine Idee?

Du willst eine vorzeichenbehaftete Ganzzahl (bzw. eine Festkommazahl) in 
eine (nicht standardisierte) Gleitkommazahl wandeln, lässt bei deinem 
Wandlungsprogramm aber den vielleicht nicht ganz unwichtigen Exponenten 
außen vor.

Für die Mittelwertbildung addierst du vermutlich erst alle 
24-bit-Integerwerte auf und willst für die Mittelwertbildung mit einer 
16-bit-Mantisse weiterrechnen (warum nicht mit allen 24 Bit rechnen?).

Zunächst würde ich die Integer-Werte in der üblichen Form R18:R17:R16 
darstellen und nicht umgekehrt (was am Prinzip aber nichts ändert).

Dann könnte ein Programm Int24ToFloat zum Wandeln einer 
vorzeichenbehafteten Ganzzahl in eine Gleitkommazahl in strukturierter 
AVR-Assembler-Sprache z. B. so ausschauen:

; signed integer number in r18:r17:r16
; exp is any of r19 through r31

Int24ToFloat:
    ldi exp,22          ; maximum # of shifts
    IF !r18,7           ; positive number
      FOR exp
        EXITIF r18,6    ; leading 1 detected
        lsl r16
        rol r17
        rol r18
      ENDF
    ELSE                ; negative number
      FOR exp
        EXITIF !r18,6   ; leading 0 detected
        lsl r16
        rol r17
        rol r18
      ENDF
    ENDI
    ret

; r18:r17 is wanted signed mantissa, exp is exponent
; decimal point is after the 1st mantissa bit (r18,6)
; for 16 bit result r16 can be dropped or used for rounding

Das wäre das übersetzte und bereinigte flache AVR-Assembler-Programm:

; signed integer number in r18:r17:r16
; exp is any of r19 through r31

Int24ToFloat:
    ldi     exp,22  ; maximum # of shifts
    SBRC    r18,7
    RJMP    _L1
_L5:
    SBRC    r18,6
    RJMP    _L3
    lsl     r16
    rol     r17
    rol     r18
    DEC     exp
    BRNE    _L5
    RJMP    _L3
_L1:
    SBRS    r18,6
    RJMP    _L3
    lsl     r16
    rol     r17
    rol     r18
    DEC     exp
    BRNE    _L1
_L3:
    ret

; r18:r17 is wanted signed mantissa, exp is exponent
; decimal point is after the 1st mantissa bit (r18,6)
; for 16 bit result r16 can be dropped or used for rounding

Wegen der nachfolgenden Mittelwertbildung ist ein Runden nach der 
Umwandlung überflüssig.

Nach der Division der Mantisse durch die Anzahl der Messwerte muss das 
Ergebnis anhand des gefundenen Exponenten ggf. in einen Integer-Wert 
zurückgewandelt werden (entsprechend viele ASR und ROR).

Ich muss zugeben, dass ich obige Programme (noch) nicht praktisch 
überprüft habe.

[Ralf (Gast)]

Thilo L. schrieb:
> Ich denke, er will ALLE Zahlen um die gleiche Anzahl nach rechts
> schieben, bis die größte der Zahlen in 16bit passt.

So habe ich das auch verstanden, wobei ALLE ZAHLEN 24bittig in R16-R18 
und das Vorzeichenbit einsam in R19 zu finden ist.
Also wäre R18>R16 solange nach rechts zu schieben (= /2) bis R18 und das 
höchste Bit von R17 Null sind und dort das Vorzeichenbit aus R19 nur 
wieder einzufügen!