; IMPORTANT NOTE ; -------------- ; This source code is given AS IT IS to the Amiga community, following ; a suggestion from Hans Guijt. Explicit permission is given to use it for ; any non-profit purpose, either in parts or as a whole, without any ; further permission from the author. The author himself reserves the right ; to use this source code at any time in the future again. For commercial ; use of this source code, prior written permission from the auther is ; required. ; Contact electronic mail addresses: grimm@particle.phys.ethz.ch ; oliver.grimm@desy.de ; Postal address: Oliver Grimm ; Steinbecker Str. 69 ; 21244 Buchholz ; Germany ; (Addresses as of March 1999) ; FASTPRIM was written in 1989/1991/1993 by Oliver Grimm ; ; Programmentwicklung: ; ; V1.0 (? 1989) - erste Version ; V1.1 (April 1991) - Device-Handling ; V1.2 (August 1993) - Bit-Modell; Byte-Modell ca. 15 % schneller; ; Zeitmessung; Zählroutine; schnelles Ctrl-c; ; variabler Ausgabebeginn; gepufferte Speicherroutine ; V1.3 (Sept. 1994) - Versionsinformation; Datei wird sofort geöffnet SysBase = 4 LVOOpenLibrary = -552 LVOCloseLibrary = -414 LVOAllocMem = -198 LVOFreeMem = -210 LVOFindTask = -294 LVOSetExcept = -312 LVOWrite = -48 LVORead = -42 LVOOpen = -30 LVOClose = -36 LVOOutput = -60 LVODelay = -198 LVODateStamp = -192 WRITEBUF = 1000 ; Länge des Schreib-Puffers ; Kommandozeile auswerten cmp.b #'-',(a0) ; wird Bit-Modell erzwungen ? bne.s noBitForce move.b #1,Method lea 1(a0),a0 noBitForce: bsr GetNum ; Primzahlen bis wohin berechnen ? move.l d3,Max bsr SkipSpace bsr GetNum ; Ausgabebeginn einlesen wenn vorhanden move.l d3,FirstOut cmp.l #1,FirstOut ; FirstOut mindestens 2 bhi.s FirstOK move.l #2,FirstOut FirstOK: bsr SkipSpace cmp.b #10,(a0) ; Filename angegeben ? beq.s noFilename move.l a0,Filename FindLF: cmp.b #10,(a0)+ ; Linefeed in Null umwandeln bne.s FindLF move.b #0,-1(a0) noFilename: move.l SysBase,a6 ; eigenen Task finden sub.l a1,a1 jsr LVOFindTask(a6) move.l d0,Task ; in ReplyPort eintragen ;move.l d0,a0 ; wenn mit RUN gestartet, Abbruch ;move.l 172(a0),d0 ;asl.l #2,d0 ; BCPL-Zeiger ;move.l d0,a0 ;move.l 44(a0),d0 ;beq.s noRun ;moveq #20,d2 ; Rückgabewert in die Shell ;bra Quit ; dos.library öffnen und Ausgabe-Handle besorgen noRun: moveq #20,d2 ; nochmal Rückgabewert, falls dos.library lea DosName(pc),a1 ; öffnen nicht möglich moveq #0,d0 jsr LVOOpenLibrary(a6) move.l d0,DosBase beq Quit move.l DosBase(pc),a6 ; Ausgabe-Handle ins Fenster jsr LVOOutput(a6) move.l d0,Handle beq noHandle move.l Task(pc),a0 move.l 42(a0),OldExceptCode ; alten Exceptionzeiger sichern move.l #ExceptCode,42(a0) ; neuen eintagen move.l SysBase,a6 move.l #4096,d0 ; Execptions bei CTRL-c an move.l d0,d1 jsr LVOSetExcept(a6) ; Haupt-Programm cmp.l #1,Max ; wurde überhaupt eine Zahl größer 1 angegeben ? bhi.s CommOK move.l #UsageText,Error bra noMemory CommOK: move.l #MemoryErr,Error move.l Max(pc),d0 add.l #8,d0 move.l d0,MemLen tst.b Method bne.s Bit_forced move.l SysBase,a6 ; Speicher allokieren move.l MemLen(pc),d0 move.l #65536,d1 ; mit Null initialisieren jsr LVOAllocMem(a6) move.l d0,Memory bne.s GotMem Bit_forced: move.b #1,Method ; nicht genug Speicher für Quick-Calc move.l SysBase,a6 ; oder Bit-Modell erzwungen move.l MemLen(pc),d0 asr.l #3,d0 move.l d0,MemLen move.l #65536,d1 jsr LVOAllocMem(a6) move.l d0,Memory beq noMemory GotMem: move.l #WRITEBUF,d0 ; Save-Puffer allokieren move.l #65536,d1 jsr LVOAllocMem(a6) move.l d0,SaveBuf beq noBufMem clr.l Error ; Errorstatus auf Null setzen move.l #StartText,d2 bsr Print tst.l Filename ; Primzahlen speichern ? beq.s BeginnCalc move.l DosBase(pc),a6 ; dann Datei schon jetzt öffnen move.l Filename(pc),d1 move.l #1006,d2 jsr LVOOpen(a6) move.l d0,FileHandle bne.s BeginnCalc move.l #OpenErr,d2 bsr Print clr.l Filename BeginnCalc: bsr GetTime ; Zeitmessung starten move.l d0,Time tst.b Method bne.s Slow move.l #FastText,d2 ; Byte-Modell bsr Print bsr QuickCalc bra.s Fertig Slow: move.l #SlowText,d2 ; Bit-Modell bsr Print bsr MemCalc Fertig: bsr GetTime sub.l Time(pc),d0 add.l #25,d0 divu #50,d0 ext.l d0 move.l d0,Time tst.b Flag ; Berechnung abgebrochen ? beq.s noAbort move.l #AbortText,d2 bsr Print bra CloseAll noAbort: move.l #ReadyText,d2 bsr Print move.l #End_of_Count,AbortAdr move.l Memory(pc),a2 ; Primzahlen zählen moveq #1,d2 move.l Max(pc),d4 moveq #0,d5 tst.b Method bne.s CountMem lea 2(a2),a0 add.l Max(pc),a2 CountQuick: cmp.l a2,a0 bhi.s End_of_Count tst.b (a0)+ bne.s CountQuick addq.l #1,d5 bra.s CountQuick CountMem: addq.l #1,d2 cmp.l d4,d2 bhi.s End_of_Count move.l d2,d0 ; Bytenummer asr.l #3,d0 move.b d2,d1 ; Bitnummer and.b #7,d1 bne.s noSkip ; wenn Bitnummer 0 und ganzes Byte ist $ff, cmp.b #$ff,0(a2,d0.l) ; dann 8 Positionen überspringen, da keine bne.s noSkip ; Primzahl in diesem Byte addq.l #7,d2 bra.s CountMem noSkip: btst.b d1,0(a2,d0.l) bne.s CountMem addq.l #1,d5 bra.s CountMem End_of_Count: clr.l AbortAdr move.l d5,PrimeNum ; Anzahl sichern move.b Flag(pc),CountFlag bne.s CountOK lea CountText(pc),a2 bsr PrintNum CountOK: move.l #CountText,d2 bsr Print clr.b Flag Save: tst.l Filename ; Primzahlen speichern ? beq.s noSave move.l #SaveText,d2 bsr Print moveq #0,d6 ; Primzahlen speichern bsr WritePrim move.l #SaveAbText,d2 ; Text Aborted/Done ausgeben tst.b Flag bne.s notDone move.l #DoneText,d2 notDone: bsr Print noSave: clr.b Flag moveq #1,d6 ; Primzahlen auf Screen ausgeben bsr WritePrim ; alle Resourcen wieder schließen End_of_Output: lea EndText+56(pc),a2 ; Anzahl/Zeit ausgeben move.l Time(pc),d5 ; wenn 0, dann 'less than 1' ausgeben beq.s tooShort bsr PrintNum tooShort: tst.b CountFlag ; falls nicht gezählt, nur Zeit ausgeben bne.s noCount lea EndText+20(pc),a2 move.l PrimeNum(pc),d5 bsr PrintNum noCount: move.l #EndText,d2 bsr Print CloseAll: tst.l FileHandle beq.s noFile_to_close move.l DosBase(pc),a6 ; Datei schließen move.l FileHandle(pc),d1 jsr LVOClose(a6) noFile_to_close: move.l SysBase,a6 move.l SaveBuf(pc),a1 move.l #WRITEBUF,d0 jsr LVOFreeMem(a6) noBufMem: move.l Memory(pc),a1 move.l MemLen(pc),d0 jsr LVOFreeMem(a6) noMemory: move.l Error(pc),d2 ; eventuell Fehlermeldung/Usage-Text ausgeben beq.s noError bsr Print noError: move.l SysBase,a6 moveq #0,d0 ; Exceptions wieder aus move.l #4096,d1 jsr LVOSetExcept(a6) move.l Task(pc),a0 ; alter Exceptionzeiger move.l OldExceptCode(pc),42(a0) moveq #0,d2 ; Rückgabe in Shell: kein Fehler noHandle: move.l SysBase,a6 move.l DosBase(pc),a1 jsr LVOCloseLibrary(a6) Quit: move.l d2,d0 ; Rückgabewert ins richtige Register rts ; ; ------------------------ Subroutinen ---------------------------- ; ; Die Zahl, deren ASCII-Darstellung ab der Adresse aus a0 steht, wird ; in d3 zurückgegeben; a0 zeigt auf das erste Zeichen nach der Zahl GetNum: moveq #0,d3 GetLoop: moveq #0,d2 move.b (a0)+,d2 sub.b #'0',d2 bmi.s noNumber cmp.b #9,d2 bhi.s noNumber move.l d3,d1 ; 'mulu #10,d3', aber mehr als 16 Bit benötigt asl.l #2,d1 add.l d1,d3 add.l d3,d3 add.l d2,d3 bra.s GetLoop noNumber: lea -1(a0),a0 rts ; Die Zahl in d5 wird nach Adresse a2 geschrieben; mit Tab am Ende PrintNum: move.l d5,d2 lea 1(a2),a1 moveq #9,d1 lea Table(pc),a0 NextDigit: moveq #"0",d0 Dec1: addq.b #1,d0 sub.l (a0),d2 bcc.s Dec1 subq.b #1,d0 add.l (a0),d2 move.b d0,(a1)+ lea 4(a0),a0 dbra d1,NextDigit move.l a2,a0 noZero: move.b #" ",(a0)+ ; führende Nullen löschen cmp.b #"0",(a0) beq.s noZero rts ; Textausgabe, in d2 Zeiger auf den Text Print: move.l DosBase(pc),a6 move.l Handle(pc),d1 moveq #0,d3 move.l d2,a0 Count: addq.l #1,d3 tst.b (a0)+ bne.s Count subq.l #1,d3 jsr LVOWrite(a6) rts ; WritePrim gibt alle Primzahlen aus. Ist d6 Null in eine Datei, sonst auf ; den Bildschirm WritePrim: move.l Memory(pc),a3 clr.l BufCnt move.l FirstOut(pc),d5 subq.l #1,d5 WriteLoop: addq.l #1,d5 cmp.l Max(pc),d5 bhi.s End_of_Write tst.b Method bne.s MemMethod tst.b 0(a3,d5.l) bra.s Check MemMethod: move.l d5,d0 ; Bytenummer asr.l #3,d0 move.b d5,d1 ; Bitnummer and.b #7,d1 btst.b d1,(a3,d0.l) Check: bne.s WriteLoop ; wenn Byte bzw. Bit Null, dann Primzahl tst.b Flag ; Ctrl-c gedrückt ? bne.s End_of_Write tst.b d6 ; Screen oder Datei ? bne.s Screen move.l BufCnt(pc),d0 move.l SaveBuf(pc),a0 move.l d5,0(a0,d0.l) ; d5 in Puffer schreiben addq.l #4,BufCnt cmp.l #WRITEBUF-6,BufCnt ; Puffer voll ? bls.s WriteLoop bsr StoreBuf ; dann sichern bra.s WriteLoop Screen: lea Buffer(pc),a2 ; Primzahl in d5 in Shell ausgeben bsr PrintNum move.l #Buffer+1,d2 bsr Print bra.s WriteLoop End_of_Write: tst.b d6 ; in Datei, dann restlichen Puffer sichern bne.s noBufFlush tst.l BufCnt beq.s noBufFlush bsr StoreBuf noBufFlush: rts StoreBuf: move.l DosBase(pc),a6 ; Puffer sichern und Zähler zurücksetzen move.l FileHandle(pc),d1 move.l SaveBuf(pc),d2 move.l BufCnt(pc),d3 jsr LVOWrite(a6) clr.l BufCnt rts ; GetTime übergibt in d0 die Systemzeit in 1/50 Sekunden GetTime: move.l DosBase(pc),a6 move.l #TimeBuf,d1 jsr LVODateStamp(a6) move.l TimeBuf(pc),d2 mulu #24*60,d2 ; Tage in Minuten umrechnen add.l TimeBuf+4(pc),d2 ; Minuten des Tages addieren moveq #0,d0 move.l #2999,d1 Min_to_Tick: add.l d2,d0 ; Minuten in Ticks wandeln (*60*50) dbra d1,Min_to_Tick add.l TimeBuf+8(pc),d0 ; Ticks addiereen rts ; SkipSpace überspingt alle Spaces,Tabs,Shift-Spaces ab Adresse a0 SkipSpace: lea 1(a0),a0 cmp.b #32,-1(a0) ; Space beq.s SkipSpace cmp.b #160,-1(a0) ; Shift-Space beq.s SkipSpace cmp.b #9,-1(a0) ; Tab beq.s SkipSpace lea -1(a0),a0 rts ; Exception-Handler wird aufgerufen, wenn CTRL-c gedrückt ExceptCode: move.l AbortAdr(pc),d1 ; Rücksprungadresse in Task ändern, beq.s noAdress ; wenn gewünscht move.l Task(pc),a0 move.l 54(a0),a0 ; Zeiger auf Stack move.l d1,(a0) ; PC ändern noAdress: move.b #1,Flag rts ; ; --- Es folgen die beiden Berechnungsroutinen --- ; ; 1.) maximale Geschwindigkeit QuickCalc: move.l #QuickEnd,AbortAdr ; für Exception move.l Memory(pc),a0 move.l Max(pc),d2 move.l a0,a2 add.l d2,a2 ; oberes Ende der Liste moveq #2,d0 QuickWeiter: move.l d0,d1 mulu d1,d1 cmp.l d2,d1 bhi.s QuickEnd ; Algorithmus beenden move.l a0,a1 ; alle nicht-Primzahlen markieren add.l d0,a1 bra.s QuickLab QuickLoop: move.b #1,(a1) QuickLab: add.l d0,a1 cmp.l a2,a1 bls.s QuickLoop QuickSuche: addq.l #1,d0 tst.b 0(a0,d0.l) bne.s QuickSuche bra.s QuickWeiter QuickEnd: clr.l AbortAdr rts ; 2.) Speichersparend ; benötigt nur 1/8 des Speicherplatzes MemCalc: move.l #QuickEnd,AbortAdr move.l Memory(pc),a0 move.l Max(pc),d2 moveq #2,d0 MemWeiter: move.l d0,d1 mulu d1,d1 cmp.l d2,d1 bhi.s QuickEnd ; Algorithmus beenden move.l d0,d1 ; alle nicht-Primzahlen markieren bra.s MemLab MemLoop: move.l d1,d4 ; Bytenummer asr.l #3,d4 move.b d1,d3 ; Bitnummer and.b #7,d3 bset.b d3,(a0,d4.l) MemLab: add.l d0,d1 cmp.l d2,d1 bls.s MemLoop MemSuche: addq.l #1,d0 move.l d0,d1 asr.l #3,d1 move.b d0,d3 and.b #7,d3 btst.b d3,0(a0,d1.l) bne.s MemSuche bra.s MemWeiter ; ; --- Datenbreich --- ; Version: dc.b "$VER: FastPrim 1.3 (9.9.1994)",0 DosName: dc.b "dos.library",0 StartText: dc.b 10,$9b,"33;1mFASTPRIM V1.3" dc.b $9b,"0;33m by Oliver Grimm",10 dc.b "Written 1989-1994 - All rights reserved.",$9b,"0m",10,10,0 FastText: dc.b "Calculating prime numbers using fast byte model ...",10 dc.b "Press Ctrl-c to abort.",10,10,0 SlowText: dc.b "Calculating prime numbers using memory-efficient bit model ...",10 dc.b "Press Ctrl-c to abort.",10,10,0 UsageText: dc.b 10,$9b,"1mUsage:",$9b,"22m Fastprim",$9b,"33m [-]Number [Number] [Filename]",$9b,"0m",10,10 dc.b "Parameters in [] are optional.",10 dc.b "The first number determines the upper limit of calculation, the optional",10 dc.b "minus sign forces the use of the bit model (see doc file). Output will",10 dc.b "begin with the first prime number equal or higher than the second number.",10 dc.b "Furthermore, prime numbers can be stored in the file given by FILENAME.",10,10,0 ReadyText: dc.b "Calculation complete - Number of Prime's:",0 CountText: dc.b " ------- ",10,10,0 EndText: dc.b 10,10,"Number of Prime's: ------- Calculation time: less than 1 s",10,10,0 AbortText: dc.b 10,10," --- Calculation terminated ---",10,10,0 SaveText: dc.b "Writing prime numbers to file ... ",0 DoneText: dc.b "Done.",10,10,0 SaveAbText: dc.b "Aborted.",10,10,0 OpenErr: dc.b "Unable to open file, no prime numbers will be stored.",10,10,10,0 MemoryErr: dc.b "Error: Insufficient free store",10,10,0 DeviceErr: dc.b "Error: Unable to open input device",10,10,0 HandlerErr: dc.b "Error: Unable to install input handler",10,10,0 Method: dc.b 0 ; Null, wenn QuickCalc Flag: dc.b 0 ; Ctrl-c Handler-Flag CountFlag: dc.b 0 ; Endtext unterdrücken, falls zählen nicht fertig even Task: dc.l 0 DosBase: dc.l 0 OldExceptCode: dc.l 0 Handle: dc.l 0 Memory: dc.l 0 ; Zeiger auf Primzahl-Speicher MemLen: dc.l 0 ; dessen Länge SaveBuf: dc.l 0 ; Puffer für Save-Funktion BufCnt: dc.l 0 ; aktuelle Position in Puffer Filename: dc.l 0 ; Zeiger auf Filenamen, wenn Speichern gewünscht FileHandle: dc.l 0 Buffer: ds.b 11 ; für Primzahl-Ausgabe dc.b 9,0 ; Tabulator TimeBuf: ds.l 3 ; für DateStamp Time: dc.l 0 Max: dc.l 0 ; Primzahl-Obergrenze FirstOut: dc.l 0 PrimeNum: dc.l 0 ; Anzahl der Primzahlen AbortAdr: dc.l 0 ; Zieladresse bei Ctrl-c Error: dc.l 0 ; Adresse des Fehlertextes oder NULL Table: dc.l 1000000000 dc.l 100000000 dc.l 10000000 dc.l 1000000 dc.l 100000 dc.l 10000 dc.l 1000 dc.l 100 dc.l 10 dc.l 1