Der Nachfolger des WDR-Computerclub mit Wolfgang Back und Wolfgang Rudolph - ...und immer ein Bit übrigbehalten!


Das Forum zur C-Control-1
Welche C-Control-Varianten existieren?
Übersicht - Suchen - Neueste 50 Beiträge - Neuer Beitrag - Login - Registrieren
INFO - FAQ - CC2-Forum - CCPro-Forum 

 Schnelle 32Bit Wurzelfunktion Kategorie: Open-Micro/Open-Mini/Open-Midi/Open-Macro/Open-Maxi (von Joe - 3.05.2015 16:58)
Joe nutzt:  CC1-M-Unit V1.1, Open-Micro, Open-Macro
Hallo OMICRO u. OMACRO Anwender,

im Rahmen eines Projektes habe ich mich auch mit Arithmetik geschrieben in Inline Assembler  fuer die OMACRO und OMICRO beschäftigt.
Da die im ersten Beitrag verwendete Wurzelfunktion rel. langsam ist, da bei der Wurzel von 2^32 insgesamt 65535 Durchläufe erfoderlich sind, suchte ich nach einer schnelleren loesung fuer die Wurzelfunktion.
Bei AVR ATMEL Controllern gibt es eine  
' 16 und 32 Bit Wurzel//Squareroot nach
' http://members.chello.nl/j.beentjes3/Ruud/sqrt32avr.htm
' dabei ist die 32 Bit Square root = Wurzel ziehen mit Ergebnis in 16 Bit
' nicht gerundet
Zuerst hatte ich das 16 Bit Programm umgesetzt, da dabei der benutzte Rechenvorgang leichter verständlich ist. Anschliessend habe ich 32 Bit Programm umgesetzt. Dieses Programm weist aber ab der Wurzel von ca. 2^30  einen Rechenfehler bei der OMACRO auf. Das Problem konnte ich bisher nicht vollstaendig loesen. Vielleicht hat von Euch jemand eine Idee, wie es zu loesen ist.

Viel Spass an den OMICROs und OMACROS wuenscht

Joe F

############### 32B_RUU7.BAS #################################
' 32B_RUU7.BAS vom D0. 09.04.2015 Josef Fenk;
'
' Umfang: 766 Basic Bytes; 0 Sys-Bytes; 24  RAM-Bytes
' 32 Bit Arithmetik
' mit Subroutinen fuer
' schnelle 16bit x 16 Bit Multiplikation mit Ergebnis in 32 Bit
'
' 32 Bit Wurzel//Squareroot nach
' http://members.chello.nl/j.beentjes3/Ruud/sqrt32avr.htm
' 32 Bit Square root = Wurzel ziehen mit Ergebnis in 16 Bit
' nicht gerundet
' Printausgabe der Zahlen als ganzzahlige Integerwerte ohne Vorzeichen

' Zahlenwertebereich der 32 bit Arithmetik ohne Vorzeichen
' Dezimal        64    00   00   00    
' 32-Bit-Zahl $0040 $0000 0000 0000 dezimal ausgeben:
' statt 0 bis 4.294.967.295 funktioniert es nur bis ca.  1.073.741.824
' der fehler liegt vermutlich im anderen Verhalten der Assembler-Befehle
' zwischen AVR und 68HC908 Controller bei Zeile 282 bis 283
' AVR A-Befehle
' cp R24,R16== low register und
' cpc R25,R17= high register
' Ersatzbefehle bei OMACRO Assembler
'! ldhx Ar_a        ' statt cp R24,R16== low register und cpc R25,R17= high register
'! cphx Ar_b+2      ' ldhx und cphx benutzt; vermutlich entsteht der Wurzelfehler ab 2^30 bei diesem Befehl
' die Wurzelfunktion bei 2^32 ist rel schnell, da nur 15 Durchl„ufe erforderlich sind


' einige Teile des Programms basieren auf der
' Version 32BITASM.BAS von Dietmar Harlos ADPC vom 29. Juni 2006;

' ---------------------------------------------------------------------------
' --- Betriebssystem konfigurieren ------------------------------------------
INCLUDE "OMAC.DEF"           'Include-Datei mit Definitionen vom April 2010

' ---------------------------------------------------------------------------
' --- Definitionen Variable fuer das Hauptprogramm
DEFINE Ar_a  AS LONG   'Erster  32-Bit-Akkumulator (1. Operand & Rechenergebnis)
DEFINE Ar_b  AS LONG   'Zweiter 32-Bit-Akkumulator (2. Operand)
DEFINE Ar_c  AS LONG   'Dritter 32-Bit-Akkumulator (temp. fuer DIV und PRINT32)

DEFINE Ar_aw1 AS WORD[1] OF Ar_a  ' low word doppelbyte 1-ter Eingabewert
DEFINE Ar_aw2 AS WORD[2] OF Ar_a  ' high word
DEFINE Ar_a1 AS BYTE[1] OF Ar_a   'L_Byte
DEFINE Ar_a2 AS BYTE[2] OF Ar_a   'Mid_L_Byte  
DEFINE Ar_a3 AS BYTE[3] OF Ar_a   'Mid_H_Byte  
DEFINE Ar_a4 AS BYTE[4] OF Ar_a   'Higest Byte  

DEFINE Ar_bw AS WORD[1] OF Ar_b   ' 2-ter eingabe wert und benutzt bei Berechnun
DEFINE Ar_b1 AS BYTE[1] OF Ar_b   'L_Byte
DEFINE Ar_b2 AS BYTE[2] OF Ar_b   'Mid_L_Byte
DEFINE Ar_b3 AS BYTE[3] OF Ar_b   'Mid_H_Byte  
DEFINE Ar_b4 AS BYTE[4] OF Ar_b   'Highest Byte  

DEFINE Ar_cw AS WORD[1] OF Ar_c   ' Ausgabe Rest in div Proc
DEFINE Ar_c1 AS BYTE[1] OF Ar_c   'L_Byte benutzt bei div. Berechnung und Ausgabe
DEFINE Ar_c2 AS BYTE[2] OF Ar_c   'H_Byte bzw. Middle Byte von 32Bit wie oben
DEFINE Ar_c3 AS BYTE[3] OF Ar_c   'Mid_H_Byte  
DEFINE Ar_c4 AS BYTE[4] OF Ar_c   'Highest Byte  

DEFINE tem1 BYTE    ' benutzt bei Ausgabe
DEFINE tem2 BYTE
DEFINE tem3 BYTE
DEFINE tem4 BYTE

DEFINE i_z  BYTE        ' Zaehlbyte
DEFINE j_l  BYTE

DEFINE Ausg     BYTE
DEFINE Ausg8 Bit[8] OF Ausg

DEFINE CCR_1 BYTE      'ausgabe CCR
DEFINE CCR_2 BYTE
DEFINE CCR_3 BYTE
DEFINE CCR_4 BYTE
DEFINE CCR_5 BYTE
'***** Definition der Digitalen Ein- / Ausgabeports
'DEFINE Tast_P4    PORT[04]       'Warte-Taste


' Hauptprogramm-----------------------------------------------

' ---------------------------------------------------------------------------
#Start
     Ar_a4=0:Ar_a3=0:Ar_a2=0:Ar_a1=0:Ar_b4=0:Ar_b3=0:Ar_b2=0:Ar_b1=0
     CCR_1=0:CCR_2=0:CCR_3=0:CCR_4=0:CCR_5=0:i_z=0
     PRINT
     PRINT "Eingabe_Mult_a,b 0...65535"
     INPUT Ar_aw1     'Eingabe 16 Bitzahl
     Ar_bw=Ar_aw1      ' fuer quadratberechnung gleicher wert zugewiesen
     PRINT "Eingabe_Ar_aw1=";Ar_aw1 ',"i_z=";i_z  ',"Ar_b=";Ar_bw
'     GOTO Direkt
'     PRINT "CCR_1     CCR_2     CCR_3     CCR_4     CRR_5"
'     Ausg=CCR_1
'     GOSUB Bit_Aus
'     PRINT "  ";
'     Ausg=CCR_2
'     GOSUB Bit_Aus
'     PRINT "  ";
'     Ausg=CCR_3
'     GOSUB Bit_Aus
'     PRINT "  ";
'     Ausg=CCR_4
'     GOSUB Bit_Aus
'     PRINT "  ";
'     Ausg=CCR_5
'     GOSUB Bit_Aus
 
     PRINT
'     PRINT "Ar_a4","Ar_a3","Ar_a2","Ar_a1","Ar_b4","Ar_b3","Ar_b2","Ar_b1"
'     PRINT Ar_a4,Ar_a3,Ar_a2,Ar_a1,Ar_b4,Ar_b3,Ar_b2,Ar_b1
     GOSUB multi_16x16
     Ar_a4=Ar_c4:Ar_a3=Ar_c3:Ar_a2=Ar_c2:Ar_a1=Ar_c1  ' zuweisung der ergebnisse
     PRINT "Ausgabe_Mul_a*a=quadrat"
     GOSUB anzeigen
     
'   #Direkt
     GOSUB sqrt_32    'Ergebnis in Ar_b
     PRINT
     PRINT "Ausgabe_Wurzel"
     Ar_a4=0:Ar_a3=0:Ar_a2=Ar_b2:Ar_a1=Ar_b1  ' zuweisung der ergebnisse
     PRINT "Ar_bw=";Ar_bw
     GOSUB anzeigen
     PRINT
 '    PRINT "Ar_a4","Ar_a3","Ar_a2","Ar_a1","Ar_b4","Ar_b3","Ar_b2","Ar_b1"
'    PRINTHEX=ON
'    PRINT Ar_a4,Ar_a3,Ar_a2,Ar_a1,Ar_b4,Ar_b3,Ar_b2,Ar_b1
'     PRINTHEX=OFF
'     PRINT "CCR_1     CCR_2     CCR_3     CCR_4     CRR_5"
'     Ausg=CCR_1
'     GOSUB Bit_Aus
'     PRINT "  ";
'     Ausg=CCR_2
'     GOSUB Bit_Aus
'     PRINT "  ";
'     Ausg=CCR_3
'     GOSUB Bit_Aus
'     PRINT "  ";
'     Ausg=CCR_4
'     GOSUB Bit_Aus
'     PRINT "  ";
'     Ausg=CCR_5
'     GOSUB Bit_Aus

 
GOTO Start
End2Host=ON

END

' ****** Subroutinen ---------------------------------------------------------------------------
'************  Subroutinen *****
#Bit_Aus       ' Bitausgabe
  FOR j_l=0 TO 7
     IF Ausg8=0 THEN
        PRINT "L";
        ELSE
        PRINT "H";
     ENDIF
     Ausg=Ausg SHL 1
  NEXT j_l
 
RETURN



' Akkumulatoren ausgeben
PROC anzeigen
  PrintHex=ON
  PRINT "Akku_a: $";Ar_a4;Ar_a3;Ar_a2;Ar_a1;" dezimal ausgeben: ";
  print32
  PRINT
  tem4=Ar_a4:tem3=Ar_a3:tem2=Ar_a2:tem1=Ar_a1 ' Zwischenspeichern, damit Werte erhalten bleiben
  Ar_a4=Ar_b4:Ar_a3=Ar_b3:Ar_a2=Ar_b2:Ar_a1=Ar_b1
  PRINT "Akku_b: $";Ar_b4;Ar_b3;Ar_b2;Ar_b1;" dezimal ausgeben: ";
  print32
  PRINT
  Ar_a4=Ar_c4:Ar_a3=Ar_c3:Ar_a2=Ar_c2:Ar_a1=Ar_c1
  PRINT "Akku_c: $";Ar_c4;Ar_c3;Ar_c2;Ar_c1;" dezimal ausgeben: ";
  print32
  Ar_a4=tem4:Ar_a3=tem3:Ar_a2=tem2:Ar_a1=tem1
  PrintHex=OFF
RETURN
' *******************************************************************
' ab hier 32Bit Arithmetik
' schnelle Square root = Wurzel ziehen
' sowie ausgabe der Ergabniszahl als integer wert ohne vorzeichen
'********************************************************************


' ---------------------------------------------------------------------------
' Schnelle Multiplikation 16Bit Wordvariable mit 16Bit Word Variable
' mit 32-Bit-Ergebnis
' von Josef Fenk Mo. 22.03.2015
' Eingabewerte_1=Multiplikand  muess in Ar_a2 bis Ar_a1 sein
' Eingabewerte_2=Multiplikator muess in Ar_b2 bis Ar_b1 sein
' Ausgabewerte=Produkt       sind in    Ar_c4 bis Ar_c1

' Verfahren der Multiplikation s. auch ATMEL application note AVR201
' Prod         Eingabe_A     Eingabe_B  Ergebnisse
'            A_H:A_L  x   B_H:B_L    C_H  C_ML C_ML C_L
'----------------------------------------------------------------------
' 1-te Mul.        A_L    x       B_L ==>            P1_H P1_L
' 2-te Mul.      A_H      x      B_L  ==> +c   P2_H P2_L
' 3-te Mul.          A_L  x B_H     ==> +c   P3_H P3_L
' 4-te Mul.      A_H      x  B_H     ==> P4_H P4_L
'-------------------------------------------------------------------------
' Summation der 4 Multiplikationen         C_M:C_MH:C_ML:C_L
'                   uebertragen in           Ar_c4:Ar_c3:Ar_c2:Ar_c1
' C_H bzw. P4_H wird beruecksichtigt, um 32 Bit Ergebnis auszugeben



PROC multi_16x16 INLASM
' 1-te Multiplikation
! lda Ar_a+3    ' Eingabe a1 low byte in accu
! ldx Ar_b+3    ' Eingabe b1 low byte in x register
! mul          ' Mul_1 P1_H byte in x; P1_L in accu
! sta Ar_c+3    ' accu=P1_L low byte in Ausgabe Ar_c1    
! stx Ar_c+2    ' P1_H high byte in Ar_c2
' 2-te Multiplikation
! lda Ar_a+2    ' Eingabe a1 high byte in accu
! ldx Ar_b+3    ' Eingabe b1 low byte in x
! mul           ' Mul_2  P2_H high byte in x-register; P2_L low byte in accu
! stx Ar_c+1    ' P2_H high byte in Ausgabe Ar_c3 mid_high byte abspeichern
! add Ar_c+2    ' P1_H zwischengespeichert in Ar_c2 zu P2_L low byte in accu addieren
! sta Ar_c+2    ' Ergebnis abgespeichert
! lda Ar_c+1    '
! adc #0        ' Ar_c3+ c ev. carry von add Ar_c+2 uebertragen
! sta Ar_c+1
! lda Ar_c      ' falls carry von vorher
! adc #0        ' nun carry uebertagen
! sta Ar_c      ' accu zurueck in c

' 3-te  Multiplikation
! lda Ar_a+3    ' Eingabe a1 low byte in accu
! ldx Ar_b+2    ' Eingabe b2 high byte in x register
! mul          ' Mul_3 P3_L low byte in accu; P3_H high byte in x
! add Ar_c+2   ' P3_L + (P2_L+P1_H) addition
! sta Ar_c+2    ' additionsergebnis accu in Ausgabe mittel byte speichern
! txa           ' P3_H in accu
! adc Ar_c+1    ' Ar_c3 + carry von voher addieren
! sta Ar_c+1
! lda Ar_c
! adc #0
! sta Ar_c      'alle uebertrage in c

' 4-te Multiplikation
! lda Ar_a+2   ' Eingabe high byte in accu
! ldx Ar_b+2   ' Eingabe b1 high byte in x
! mul          ' Mul4 P4_L low byte in accu; P4_H high byte in x-register, wird genutzt
! add Ar_c+1   ' P2_H in Ar_c3 zwischengespeichert nun zu P4_L in accu addieren
               ' P2_H+P4H mit ev. carry von vorherigen Additionen in Ar_c
! sta Ar_c+1   ' accu ergebnis in Ar_c3                
! lda Ar_c
! adc #0
! sta Ar_c
! txa          ' transfer x-register = P4_H in accu
! add Ar_c     'Ar_c zu accu addieren
! sta Ar_c     ' accu nach Ar_c4 highest byte kopieren
! rts
END PROC


' Procedure Wurzel aus 32 Bit Zahl
' Eingabewert=Radikand muss in Ar_a1 bis Ar_a4 sein
' Ausgabewert=Wurzelwert    in Ar_b1 bis Ar_b2
' Quadratwurzel von einer 32-Bit-Zahl, mathematisch korrekt gerundet!
' Wertebereich fuer Wurzeleingabe begrenzt auf
' bei 0...4.278.190.079==H: fe ff ff ff ==> Ausgabe 0...65408
' bei     4.294.967.295==H: ff ff ff ff ==> Ausgabe 256
' erweitert von JFenk auf 32 Bit; Mo. 23.03.2015
' die Anzahl der Schleifendurchlaeufe =15
' es ist fuer grosse Zahlen ein schnelleres Verfahren, als das früher beschriebene
'  Fast and short 32 bits AVR sqrt routine
'  R17:R16=SQRT(R5:R4:R3:R2) rounded down to integer
'  Registers:
'  Destroys the argument in R5:R4:R3:R2
'  Cycles incl call & ret = 263 - 305
'  Stack incl call = 4


PROCEDURE sqrt_32 INLASM '!!!
! mov #192,Ar_b4  'ldi   Ar_b4,0xc0==d192
! clr Ar_b3       'rotation mask in Ar_b4:Ar_b3
! mov #64,Ar_b2   'ldi   Ar_b2,0x40==d64
! clr Ar_b1       'sub   Ar_b1,Ar_b1           ; developing sqrt in Ar_b2:Ar_b1, C=0
! clc             ' loescht carry
#sq32_1
! inc i_z         ' Schleifenzaehler
! bcs sq32_2      'brcs  _sq32_2           ; C --> Bit is always 1
'! lda Ar_a3       'cp    Ar_a3,Ar_b1
! ldhx Ar_a        ' statt cp R24,R16== low register und cpc R25,R17= high register
! cphx Ar_b+2      ' ldhx und cphx benutzt; vermutlich entsteht der Wurzelfehler ab 2^30 bei diesem Befehl
! bcs sq32_3      'brcs  _sq32_3           ; C --> nope, bit is 0

#sq32_2
! lda Ar_a3       'sub   Ar_a3,Ar_b1
! sub Ar_b1
! sta Ar_a3
! lda Ar_a4       'sbc   Ar_a4,Ar_b2            ; Adjust argument for next bit
! sbc Ar_b2
! sta Ar_a4
! lda Ar_b1       'or    Ar_b1,Ar_b3
! ora Ar_b3
! sta Ar_b1
! lda Ar_b2       'or    Ar_b2,Ar_b4           ; Set bit to 1
! ora Ar_b4
! sta Ar_b2

#sq32_3
! lsr Ar_b4
! ror Ar_b3     ' Shift right mask, C --> end loop
! lda Ar_b2     ' eor   Ar_b2,Ar_b4
! eor Ar_b4
! sta Ar_b2
! lda Ar_b1     'eor   Ar_b1,Ar_b3           ; Shift right only test bit in result
! eor Ar_b3
! sta Ar_b1          
! rol Ar_a1     'Bit 0 only set if end of loop
! rol Ar_a2
! rol Ar_a3
! rol Ar_a4     ' Shift left remaining argument (C used at _sq32_1)
! brset 0,Ar_a1,Spr_1 ' sbrs  Ar_a1,0 ; Skip if 15 bits developed
! jmp sq32_1    ' rjmp  _sq32_1           ; Develop 15 bits of the sqrt
#Spr_1
'! jmp en_P     ' nur fuer Testzwecke, um den Wurzelfehler ab 2^30 zu testen
! clc
! bcs sq32_4    ' brcs  _sq32_4           ; C--> Last bits always 1
! lsl Ar_a2     ' Need bit 7 in C for cpc
! tpa            ' transfer CCR register to accu
! sta CCR_1     ' uebertragen status des CCR in CCR_r1 byte
! bcs Car_c      ' wenn carry=1 soll Ar_c1=0 sein u. carry =0 soll Ar_c1=1 sein
! inc Ar_c1   ' hier wird in Ar_c1 bit1 gesetzt als merker, dass Carry=0 war
#Car_c

! ldhx Ar_b+2   ' statt cpc R16,R24 +cpc R17,R25
! cphx Ar_a       ' vergleicht Ar_b2:Ar_b1==R17:R16 mit R2_5:R2_4==Ar_a4:Ar_a3
! tpa            ' transfer CCR register to accu
! sta CCR_2     ' uebertragen status des CCR in CCR_r1 byte
! bcs Car_s      ' falls carry=1 werden folgende teile uebrsprungen
! tap            ' accu wieder in CCR
! tpa            ' transfer CCR register to accu
! sta CCR_3     ' uebertragen status des CCR in CCR_r1 byte; sta veraendert CCR
! tap            ' accu wieder in CCR!!!!!! ganz wichtig, sonst ist Z bit status verloren
! bne Z_bit      'falls R1=ungleich=R2 ==>Z=0 erfolgt verzweigung
! brset 0,Ar_c1,Bit_t  'wenn vorher bei Car_c carry=0 ==> Ar_c1=1 dann erfolgt verzweigung
! sec            ' ansonsten wird carry gesetzt
! tpa            ' transfer CCR register to accu
! sta CCR_4     ' uebertragen status des CCR in CCR_r1 byte

#Bit_t           '
#Z_bit
#Car_s
#sq32_4
! tpa               ' transfer CCR status byte to accu
! sta CCR_5         ' in CCR_1 kopiert
     
! lda Ar_b1     'adc   Ar_b1,Ar_b4           ; Round up if C (Ar_b4=0)
! adc Ar_b4
! sta Ar_b1    
'#en_p          ' nur fuer Testzwecke eingebaut, um den Wurzelfehler ab 2^30 zu testen
! rts           ' Ergebnis wird ausgegeben in Ar_b
END PROCEDURE


' Subroutine zur dezimalen Ausgabe von 32-Bit-Zahlen= dez 10 stellig ohne Vorzeichen
' geaendert Sa. 14.03.2015 von JF, um integerzahlen ohne neg. Werte zu erhalten
' Wertebereich fuer Ausgabe begrenzt  
' auf  2^32 = 4.294.967.295==Hex: ff ff ff ff
' Urversion von Dietmar Harlos ADPC am 29. Juni 2006 in 32BITASM.BAS

PROC print32 INLASM
! mov Ar_a+3,Ar_c+3       'Akkumulator a nicht veraendern
! mov Ar_a+2,Ar_c+2
! mov Ar_a+1,Ar_c+1
! mov Ar_a,Ar_c
! ldx #10       ' divisior = 10 in x register laden
! clr OSTEMP
#print32_2
! inc OSTEMP    ' zaehlt hoch
! clrh          ' high byte of dividend =0 gesetzt
! lda Ar_c      ' lade dividend low byte in accu
! div           ' Division durch 10;quotient in accu; remainder in H
! sta Ar_c
! lda Ar_c+1
! div
! sta Ar_c+1
! lda Ar_c+2
! div
! sta Ar_c+2
! lda Ar_c+3
! div
! sta Ar_c+3
! pushh         'pushh = pshh  remainder in H auf stack speicher
! ora Ar_c+2    ' vergleich accu mit ar_c+2
! ora Ar_c+1
! ora Ar_c
! bne print32_2 'branch if not equal; test Z bit of CCR and branch if Z=0
#print32_3
! popa          'Ziffern holen von stack und ausgeben;  popa=0pula
! add #"0"
! jsr FwPutSci
! cli           ' clears interrupt bit I = bit 3 of CCR  
! dbnz OSTEMP,print32_3 'decrement and branch if not zero; wenn OSTEMP>0 sprung zu print32_3
! rts
END PROC

' ---------------------------------------------------------------------------
INCLUDE "OM_FW.PRO"

 Antwort schreiben

Bisherige Antworten: