Assembler 16bit signed Multiplikation

[StefanK (Gast)]

Hallo,

ich habe kurz eine Frage... ich habe die im Listing angehängte Assembler 
Funktion geschrieben um eine A(3,12) (signed, 12bit Nachkomma) 
Multiplikation durchzuführen. Die Assembler Funktion wird extern in mein 
C Projekt eingebunden.
Die Multiplikation findet auf einem 8bit AVR statt.

Ich brauche damit incl. Funktionsaufruf 59 cycle während die C 
implementierung gut 160 cycles benötigt.

Die Routine funktioniert bei den bisher getesteten Argumenten. Bezüglich 
der temprären Register habe ich nach 
http://www.nongnu.org/avr-libc/user-manual/FAQ.html#faq_reg_usage (What 
registers are used by the C compiler?) sogenannte Call-used register 
verwendet.

Kann bei meiner Implementierung dann noch etwas schief gehen (bezüglich 
Registersicherung oder andere nicht bedachte Umstände)?

Falls nicht: habt ihr Verbesserungsvorschläge?

C:

fixRes = (int16_t)(((int32_t)a * b)>>12);

Assembler:

.global mul_s16_fixQ12
.func mul_s16_fixQ12
mul_s16_fixQ12:
  ;int16 a: r25|r24
  ;int16 b: r23|r22
  movw r20, r24          ; mulsu needs r16-r23
  clr r2                 ; clear r2 cause it is used to add carries
  muls r23, r21          ; (signed)aMSB * (signed)bMSB
  movw r24, r0           ; store result R25:R24
  mul r22, r20           ; aLSB * bLSB
  movw r26, r0           ; store result R26:R27
  mulsu r23, r20         ; (signed)aMSB * bLSB
  sbc r25, r2
  add r27, r0
  adc r24, r1
  adc r25, r2
  mulsu r21, r22         ; (signed)bMSB * aLSB
  sbc r25, r2
  add r27, r0
  adc r24, r1
  adc r25, r2
  ; result is now in R25:R24:R27:R26
  ;                  MSB         LSB
  ; fixedPoint with precision 12 -> drop R26 (8bit)
  ; still 4 shifts left
  lsr r25
  ror r24
  ror r27

  lsr r25
  ror r24
  ror r27
  
  lsr r25
  ror r24
  ror r27
  
  lsr r25
  ror r24
  ror r27
  
  adc r27, r2           ; use last bit shifted out to round 
  
  mov r25, r24          ; store result in 16bit return registers
  mov r24, r27
  ret
.endfunc

[Karl H. (kbuchegg)]

Lies nochmal nach, was du mit den Register r0, r1 und r2 machen musst.
r0 ist egal, aber r1 und r2 darfst du nicht einfach zerstören.

[Anja (Gast)]

StefanK schrieb:
> adc r27, r2           ; use last bit shifted out to round

was machst Du wenn bei der Addition wieder ein Übertrag auftritt?

Ausserdem mußt Du Sicherstellen daß das Produkt immer kleiner als 7.999 
ist ansonsten gibt es unter Umständen ein falsches Vorzeichen.

(die C-Implementierung ist aber an der Stelle auch nicht besser).

Gruß Anja

[StefanK (Gast)]

Karl Heinz Buchegger schrieb:
> Lies nochmal nach, was du mit den Register r0, r1 und r2 machen musst.
> r0 ist egal, aber r1 und r2 darfst du nicht einfach zerstören.

Vielen Dank, hab ich doch glatt überlesen. R2 änder ich nicht, aber für 
R1 muss ich noch das clr einfügen.

Anja schrieb:
> was machst Du wenn bei der Addition wieder ein Übertrag auftritt?
>
> Ausserdem mußt Du Sicherstellen daß das Produkt immer kleiner als 7.999
> ist ansonsten gibt es unter Umständen ein falsches Vorzeichen.

hab jetzt ein weiteres adc hinzugefügt für den eventuellen Übertrag. 
Vielen Dank für den Hinweis.

Bei dem sicherstellen des Produktes < 7.999 bin ich leider überfragt. 
Ich hab durch Simulationen geprüft, dass mein Wertebereich im Regelfall 
nicht größer ist.
Wie könnte ich im Assembler Code möglichst geschickt einen Überlauf 
erkennen und darauf reagieren?
Ich bin ja eigentlich eher in C zuhause, da würd ich den sowas in der 
Richtung machen

bool mult( int16_t* pRes, int16_t a, int16_t b )
{ 
    (... vor shift)
    bool temp;
    if(R25 == 0x00 || R25 == 0xFF )
        temp = true;
    else
        temp = false;

    (... shift und zuweisung...)
    return temp;
}

leider bin ich in Assembler noch nicht zu sowas fähig. Die Überprüfung 
selbst ist für mich mit entsprechendem cycle-aufwand machbar (wenn ich 
kein Denkfehler gemacht habe). Probleme bereiten mir so Dinge wir 
Übergabe des Werts als Zeiger und die Bool Geschichte.


Mit Hilfe der beiden anderen Anmerkungen korrigierter ASM

  ;(... vorheriges wie gehabt...)
  adc r27, r2           ; use last bit shifted out to round
  adc r24, r2           ; add carry
  
  mov r25, r24          ; store result in 16bit return registers
  mov r24, r27

  clr r1

  ret
.endfunc

[Karl H. (kbuchegg)]

StefanK schrieb:
> Karl Heinz Buchegger schrieb:
>> Lies nochmal nach, was du mit den Register r0, r1 und r2 machen musst.
>> r0 ist egal, aber r1 und r2 darfst du nicht einfach zerstören.
>
> Vielen Dank, hab ich doch glatt überlesen. R2 änder ich nicht,

echt?

>   adc r27, r2           ; use last bit shifted out to round
>   adc r24, r2           ; add carry


Hmmm

[spess53 (Gast)]

Hi

>>   adc r27, r2           ; use last bit shifted out to round
>>   adc r24, r2           ; add carry

>Hmmm

Und was ändern die an r2?

MfG Spess

[Karl H. (kbuchegg)]

spess53 schrieb:
> Hi
>
>>>   adc r27, r2           ; use last bit shifted out to round
>>>   adc r24, r2           ; add carry
>
>>Hmmm
>
> Und was ändern die an r2?

Hast recht. War auch nur ein Schnellschuss, damit er sich Gedanken macht 
wie er da ein r2 verwenden kann, wo er doch r2 gar nicht verändert :-)

Aber das hier

  clr r2                 ; clear r2 cause it is used to add carries

bedingt einen push/pop

[Johann L. (gjlayde)]

StefanK schrieb:
> R2 änder ich nicht, ...

Lügt, ohne rot zu werden:

> clr r2

Ist der unigned-shift am Ende ok? Soll doch eine signed-Berechnung sein.

Übrigens: avr-gcc kann inzwischen auch 16*16=32 Multiplikationen 
effizient ausführen, ohne die Operanden auf 32 Bit aufzublasen und dann 
die ganze Multiplikation auf 32-Bit Ebene zu machen :-)

FYI, hier der Code:
http://gcc.gnu.org/viewcvs/trunk/gcc/config/avr/libgcc.S?r1=175620&r2=175619&pathrev=175620

[Karl H. (kbuchegg)]

Johann L. schrieb:

> Übrigens: avr-gcc kann inzwischen auch 16*16=32 Multiplikationen
> effizient ausführen, ohne die Operanden auf 32 Bit aufzublasen und dann
> die ganze Multiplikation auf 32-Bit Ebene zu machen :-)

Wie schreibt sich das dann auf C Ebene?

uint16_t a, b;
uint32_t c;


   c = a * b;

ist ja eigentlich dann nicht richtig. Die 'Überlaufbits' in der 
Multiplkation müssten ignoriert werden.


   c = (uint32_t)a * b;

kommt da der Optimizer drauf, dass die 32*32 Bit Multiplikation nur 
deswegen entsteht, weil beide Operatoren von 16 auf 32 Bit aufgeblasen 
wurden?

[StefanK (Gast)]

Vielen Dank an alle,

das push/pop für R2 hat gefehlt. Ich nutze jetzt stattdessen R18, das ja 
verändert werden darf.

Johann L. schrieb:
> Ist der unigned-shift am Ende ok? Soll doch eine signed-Berechnung sein.

Der unsigned shift sollte ok sein, da er ja ja bei signed sowas wie 
0xFF3C hat, das heißt beim shift wird immer die nächsthöhere 1 ins 
relevante Register geschoben (solange der von Anja erwähnte Überlauf 
nicht eintritt).
Der signed shift hält ja die 1 an dem MSbit des Registers (also z.b. das 
MSB des Multiplikationsergebnisses), da bringt es mir ja nix, weil ichs 
das ja verwerfe (wenn ich nicht wieder was überseh...).


Johann L. schrieb:
> Übrigens: avr-gcc kann inzwischen auch 16*16=32 Multiplikationen
> effizient ausführen, ohne die Operanden auf 32 Bit aufzublasen und dann
> die ganze Multiplikation auf 32-Bit Ebene zu machen :-)
>
> FYI, hier der Code:
> http://gcc.gnu.org/viewcvs/trunk/gcc/config/avr/li...

Ich kenn mich leider nicht besonders damit aus.. wie ruf ich sowas denn 
dann in C auf?

Viele Grüße

[Johann L. (gjlayde)]

Karl Heinz Buchegger schrieb:
> Johann L. schrieb:
>
>> Übrigens: avr-gcc kann inzwischen auch 16*16=32 Multiplikationen
>> effizient ausführen, ohne die Operanden auf 32 Bit aufzublasen und dann
>> die ganze Multiplikation auf 32-Bit Ebene zu machen :-)
>
> Wie schreibt sich das dann auf C Ebene?
>
> uint16_t a, b;
> uint32_t c;
>

So:

>    c = (uint32_t)a * b;
>
> kommt da der Optimizer drauf, dass die 32*32 Bit Multiplikation nur
> deswegen entsteht, weil beide Operatoren von 16 auf 32 Bit aufgeblasen
> wurden?

Ja. Allerdings gibt's das erst in avr-gcc 4.7 und wenn's MUL-Befehle 
hat.
Ohne MUL gewinnt man glaub nicht wirklich was.


StefanK schrieb:
> Johann L. schrieb:
>> Übrigens: avr-gcc kann inzwischen auch 16*16=32 Multiplikationen
>> effizient ausführen, ohne die Operanden auf 32 Bit aufzublasen und dann
>> die ganze Multiplikation auf 32-Bit Ebene zu machen :-)
>>
>> FYI, hier der Code:
>> http://gcc.gnu.org/viewcvs/trunk/gcc/config/avr/li...

Hier nochmal dir Link zur eigentlichen S-Datei, ist besser zu lesen alsn 
Patch.

> Ich kenn mich leider nicht besonders damit aus.. wie ruf ich sowas denn
> dann in C auf?

Puh, da fragst du was... In ANSI-C überhaupt nicht, weil die Funktion en 
(__mulhisi3 bzw. __umulhisi3) nicht dem ABI entsprechen: Sie machten

r25:r22 = r19:r18 * r21:r20

Am einfachsten bekommt man das ABI-konform, indem man am Funktionsanfang

movw  A0, r22
movw  B0, r24

einfügt und dann C-Prototypen definiert:

#include <stdint.h>

extern uint32_t __umulhisi3 (uint16_t, uint16_t);
extern int32_t __mulhisi3 (int16_t, int16_t);

und die Funktionen wie normale C-Funktionen aufruft.

Ein Nachteil ist, daß immer die zwei unnötigen MOVW am Anfang stehen. 
Daher sind die Funktionen auch nicht-ABI-konfirm aufgesetzt.

Um den Code "direkt" verwenden zu können, muss man GNU-C bemühen um das 
Interface ans ABI anzupassen:

static inline uint32_t 
umulhisi3 (uint16_t a, uint16_t b)
{
    register uint16_t ra asm ("18") = a;
    register uint16_t rb asm ("20") = b;
    register uint32_t rc asm ("24");

    asm ("%~call __umulhisi3"
         : "=r" (rc)
         : "r" (ra), "r" (rb));

    return rc;
}

Ditto für die signed-Version.

Das erlaubt dem Compiler dann, die Register-Allocation an den Aufruf 
anzupassen, und MOVs können ggf. entfallen, wenn der Alligator die 
Register geschickt wählt.

[StefanK (Gast)]

Johann L. schrieb:
> Hier nochmal dir Link zur eigentlichen S-Datei, ist besser zu lesen alsn
> Patch.

Ich find den Link leider nicht.

Muss ich den Assembler Code dann aus dem Link dann in eine eigene .s 
kopieren oder existiert der schon in einer Bibliothek die ich einbinden 
muss?

Viele Grüße

[Johann L. (gjlayde)]

StefanK schrieb:
> Johann L. schrieb:
>> Hier nochmal dir Link zur eigentlichen S-Datei, ist besser zu lesen alsn
>> Patch.

> Ich find den Link leider nicht.

Oh, die Zeile ging wohl verschütt. Hier nochmal:

http://gcc.gnu.org/viewcvs/trunk/gcc/config/avr/libgcc.S?revision=175620&content-type=text%2Fplain&view=co&pathrev=175620

> Muss ich den Assembler Code dann aus dem Link dann in eine eigene .s
> kopieren oder existiert der schon in einer Bibliothek die ich einbinden
> muss?

Es ist erst ab avr-gcc 4.7 in der Bibliother, und dann brauchst du auch 
keine Verrenkungen zu machen sondern einfach nur C-Code wie Karl Heinz 
ihn oben nachfragte.

Ich bin allerdings davon ausgegeangen, daß du diese Version noch nicht 
einsetzt, da sie erst in der Entwicklung ist.

Den relevanten Teil hab ich mal rauskopiert, den speicherst du nicht 
als *.s sondern als *.sx und verwendest es ansonsten wie ein normales 
C-File, d.h. du wirfst es avr-gcc wie eine c-Datei zum Fraß vor.

Idealerweise machst du Für jede Funktion eine Datei. Ansonsten saugst du 
die beim Verwenden der einen Version immer auch die anderen in den Code.

BTW: Wer hat denn das Syntax-Highlight für "avrasm" verbrochen?
Sieht ja scheusslich aus...

/* Copyright (C) 1998, 1999, 2000, 2007, 2008, 2009
   Free Software Foundation, Inc.
   Contributed by Denis Chertykov <[e-mail]>

This file is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3, or (at your option) any
later version.

This file is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

Under Section 7 of GPL version 3, you are granted additional
permissions described in the GCC Runtime Library Exception, version
3.1, as published by the Free Software Foundation.

You should have received a copy of the GNU General Public License and
a copy of the GCC Runtime Library Exception along with this program;
see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
<http://www.gnu.org/licenses/>.  */

#define __zero_reg__ r1
#define __tmp_reg__ r0

  .section .text.libgcc, "ax", @progbits

#if defined (__AVR_HAVE_JMP_CALL__)
#define XCALL call
#define XJMP  jmp
#else
#define XCALL rcall
#define XJMP  rjmp
#endif

.macro DEFUN name
.global \name
.func \name
\name:
.endm

.macro ENDF name
.size \name, .-\name
.endfunc
.endm


/*******************************************************
      Widening Multiplication  32 = 16 x 16
*******************************************************/
                              
DEFUN __mulhisi3
#if defined (__AVR_HAVE_MUL__)

;; r25:r22 = r19:r18 * r21:r20

#define A0 18
#define B0 20
#define C0 22

#define A1 A0+1
#define B1 B0+1
#define C1 C0+1
#define C2 C0+2
#define C3 C0+3
 
    ; C = (signed)A1 * (signed)B1
    muls  A1, B1
    movw  C2, R0

    ; C += A0 * B0
    mul   A0, B0
    movw  C0, R0

    ; C += (signed)A1 * B0
    mulsu A1, B0
    sbci  C3, 0
    add   C1, R0
    adc   C2, R1
    clr   __zero_reg__
    adc   C3, __zero_reg__

    ; C += (signed)B1 * A0
    mulsu B1, A0
    sbci  C3, 0
    XJMP  __xmulhisi3_exit

#undef A0
#undef A1
#undef B0
#undef B1
#undef C0
#undef C1
#undef C2
#undef C3

#else /* !__AVR_HAVE_MUL__ */
.error
#endif /* __AVR_HAVE_MUL__ */
ENDF __mulhisi3


DEFUN __umulhisi3
#if defined (__AVR_HAVE_MUL__)

;; r25:r22 = r19:r18 * r21:r20

#define A0 18
#define B0 20
#define C0 22

#define A1 A0+1
#define B1 B0+1
#define C1 C0+1
#define C2 C0+2
#define C3 C0+3

    ; C = A1 * B1
    mul   A1, B1
    movw  C2, R0

    ; C += A0 * B0
    mul   A0, B0
    movw  C0, R0

    ; C += A1 * B0
    mul   A1, B0
    add   C1, R0
    adc   C2, R1
    clr   __zero_reg__
    adc   C3, __zero_reg__

    ; C += B1 * A0
    mul   B1, A0
    XJMP  __xmulhisi3_exit

#undef A0
#undef A1
#undef B0
#undef B1
#undef C0
#undef C1
#undef C2
#undef C3

#else /* !__AVR_HAVE_MUL__ */
.error
#endif /* __AVR_HAVE_MUL__ */
ENDF __umulhisi3

;;; Helper for __mulhisi3 resp. __umulhisi3.

#define C0 22
#define C1 C0+1
#define C2 C0+2
#define C3 C0+3

DEFUN __xmulhisi3_exit
    add   C1, R0
    adc   C2, R1
    clr   __zero_reg__
    adc   C3, __zero_reg__
    ret
ENDF __xmulhisi3_exit

#undef C0
#undef C1
#undef C2
#undef C3

[StefanK (Gast)]

Alles klar, vielen Dank.

Ich hätte nur noch eine Frage bezüglich der Endung: Was ist der 
Unterschied zwischen .s und .sx?

[Johann L. (gjlayde)]

StefanK schrieb:
> Alles klar, vielen Dank.
>
> Ich hätte nur noch eine Frage bezüglich der Endung: Was ist der
> Unterschied zwischen .s und .sx?

.s: assembler
.sx: assembler-with-cpp

d.h. bei .sx läuft der C-Präprozessor drüber, bei .s nicht.

Unter Linux geht auch .S anstatt .sx. Unter Windoofs würd ich .S aber 
nicht verwenden weil es Probleme mit Groß/Kleinschreibung hat und ich 
schon erlebt habe, daß es zu doof ist, .s von .S zu unterscheiden. Wenn 
man dann eine clean-Rule im Makefile hat für .s, kannst du dir 
vorstellen wie's weitergeht.

Wenn einem diese Endungen nicht passen und man zB .keks lieber mag, gibt 
man einfach ein -x assembler-with-cpp schoko.keks an.

Hab eben mal die Ticks gezählt für 32 = 16*16 (signed), das müsste in 
weniger als 30 gehen (incl. RET), für die unsigned-Version noch was 
fixer.