CD Actual 15

home *** CD-ROM | disk | FTP | other *** search

/ CD Actual 15 / CDACTUAL15.iso / cdactual / program / asm / LMPRIME1.ZIP / LMPRIME1.ASM next >

Wrap

Assembly Source File | 1991-11-26 | 17.9 KB | 795 lines

TITLE LMPRIME1 ; Bill Parke's PRIME14 modified for 80386 PAGE 60,132 BELL EQU 7 TAB EQU 9 CR EQU 13 LF EQU 10 IS8087 EQU 0 ; Change to 1 for use with an 80x87 math coprocessor .386 START SEGMENT USE16 ASSUME CS:START,DS:START,ES:START,SS:START ORG 100H FIRST: JMP BEGIN DB 'Copyright Les Moskowitz 1991' NPS1 DB CR,LF,'There are$' NPS2 DB ' primes$' NPS2A DB ' between$' NPS3 DB ' and$' ERROR DB 'Error in ',BELL DHELP DB 'Syntax: LMPRIME1 n1 n2 [/]',CR,LF DB TAB,TAB,'where 0 < n1 < n2 < 4,294,967,295',CR,LF DB TAB,TAB,'Optional / will suppress listing of individual primes' CRLF DB CR,LF,'$' NOT386 DB BELL,CR,LF,'Sorry - This program needs an 80386 cpu.',CR,LF,'$' IF IS8087 CW DW 0000101110111111B ; 8087 control word - round up ENDIF STSI DD 0 LSTB DD 0 INIM DB 0 ERIN DB 0 FLG1 DB 0 ; Used to test for n1 < 3. FLG2 DB 0 ; 0 - show all primes; 1 - suppress primes ; The next 4 items must be in this order NO1A DD ? NPRINT1 DD ? ; Starting number NPRINT2 DD ? ; Ending number NO2A DD ? SSIZE DW 0 ; Sieve size (numbers) = square root of n2 THISPRIME DT ? ; Current prime in packed BCD format TMPBUF DQ 0 SIFLAG DB 0 ; 0 - working on 1-ssize, 1 - working on n1-n2 SSIZE2 DD 0 ; Sieve size divided by 8 ARGSIZE DW ? N23 DD ? NPRIME DD 0 ; Number of primes EXTRA DB 0 DIGITS DW ? ; Required digits (including leading space) NLINE DW ? ; Number of primes to print per line TLINE DW ? SSIZEF DW 1 ; Odd numbers starting with 1 NP$ DB 10 DUP ('0') NP1 DB '0$ ' NPADDR DW OFFSET NP$ BEGIN: CALL CHK386 ; Make sure this is a 386 cpu JC SHORT EXIT ; If not, then exit CALL SETUP ; Get command line input and initialize JC SHORT EXIT ; Exit, if we got an error BEG2: CALL BUFFER ; Set up 64k buffer for our data MOV BL,1 CALL NOCOMP ; Eliminate all composite numbers CALL FINI ; Print our remaining prime numbers PUSH DS POP ES MOV SI,OFFSET NPRINT2 MOV DI,OFFSET NO2A CMPSD JE SHORT EXIT MOV SSIZEF,1 XOR EAX,EAX MOV SI,OFFSET NPRINT2 MOV DI,OFFSET NPRINT1 MOVSD ; NPRINT2 --> NPRINT1 MOVSD ; NO2A --> NPRINT2 INC NPRINT1 MOV DI,OFFSET SSIZE CALL SQROOT ; Store square root of NPRINT2 in SSIZE CALL SET4 JMP BEG2 EXIT: PUSH CS POP ES MOV AL,ERIN OR AL,AL ; Was there an error ? JNZ SHORT EXITE ; Yes - exit immediately CALL SUMMARY ; Indicate the total number of primes CALL SCRLF MOV AX,4C00H INT 21H ; Exit - everything ok EXITE: MOV AH,9 ; Print out the error message INT 21H MOV AH,4CH INT 21H ; Exit with error level set to ERIN CHK386 PROC NEAR ; Set the carry flag if not an 80386 cpu PUSHF POP BX MOV AX,0FFFH AND AX,BX PUSH AX POPF PUSHF POP AX AND AX,0F000H CMP AX,0F000H JE SHORT NO ; We're finished - it's an 8086 OR BX,0F000H PUSH BX POPF PUSHF POP AX AND AX,0F000H JNZ SHORT YES ; We're finished - it's an 80386 or 80486 NO: STC MOV DX,OFFSET NOT386 RET YES: CLC RET CHK386 ENDP SETUP PROC NEAR ; Initialize everything XOR EAX,EAX ; Make sure these registers are XOR EBX,EBX ; initially set to zero. XOR ECX,ECX ; NOTE - DOS doesn't automatically XOR EDX,EDX ; do this for the high order bytes XOR ESI,ESI ; in 32-bit registers. CALL SCRLF MOV SI,80H LODSB MOV CL,AL MOV AL,'/' MOV DI,81H REPNE SCASB ; Total number of primes only? SETZ FLG2 ; Set the flag to 1 if found CMP BYTE PTR [DI],'?' JNE SHORT SET0 MOV DX,OFFSET DHELP INC ERIN STC RET SET0: MOV SI,81H MOV DI,OFFSET TMPBUF CALL GETNUM ; Get first number from the command line JNC SHORT SET2 ; Continue unless we got an error SET1: INC ERIN ; If there's an error, then we're finished MOV DX,OFFSET ERROR STC RET SET2: JCXZ SHORT SET3 PUSH SI MOV SI,OFFSET TMPBUF MOV DI,OFFSET NPRINT1 CALL DECBIN32 ; Store n1 in NPRINT1 as binary number POP SI PUSH NPRINT1 POP NO1A JC SET1 ; Exit if number exceeds 4,294,967,296 MOV DI,OFFSET TMPBUF CALL GETNUM ; Get second number from the command line JC SET1 ; Exit if we got an error PUSH DS XOR AX,AX MOV DS,AX MOV SI,44AH LODSB ; AL now contains the screen width POP DS INC CL MOV DIGITS,CX DIV CL DEC CL CMP AH,0 JNE SHORT KEEP DEC AL KEEP: CBW MOV NLINE,AX INC AX MOV TLINE,AX ADD NPADDR,10 SUB NPADDR,CX SET3: MOV SI,OFFSET TMPBUF MOV DI,OFFSET NPRINT2 CALL DECBIN32 ; Store n2 in NPRINT2 as binary number PUSH NPRINT2 POP NO2A JC SET1 ; Exit if number exceeds 4,294,967,296 MOV DI,OFFSET SSIZE CALL SQROOT ; Store square root of NPRINT2 in SSIZE SET4: MOV EBX,DWORD PTR [DI] SHR EBX,3 MOV SSIZE2,EBX MOV ECX,NPRINT2 ; n2 MOV ESI,NPRINT1 ; n1 MOV DX,OFFSET DHELP OR ESI,0 ; Is n1 = 0 ? JZ SHORT SET5 ; Yes - print help message and exit CMP ESI,ECX ; Is n1 < n2 ? JB SHORT SET6 MOV DX,OFFSET ERROR SET5: INC ERIN ; No - print error message and exit STC RET SET6: CMP ESI,3 SETB FLG1 OR ESI,1 ; Make nprint1 odd TEST CX,1 ; Is nprint2 odd? JNZ SHORT SET7 ; Yes - jump DEC ECX ; No - we don't need the last even number OR FLG1,00000010B SET7: MOV EBX,ESI ; Nprint1 AND EBX,0FH ; Start to print after div by 16 SHR BX,1 ; Get bit index for starting number MOV EAX,ESI ; N23 will be the number represented SHR EAX,4 ; by bit 0 of the byte at SHL EAX,4 ; STSI. INC EAX MOV N23,EAX SHR ESI,4 ; Divide first number by 16 MOV STSI,ESI MOV AX,CX ; Nprint2 AND AX,0FH ; Extra to print SHR AX,1 ; But only odds MOV EXTRA,AL MOV EDX,ECX ; Save index of last byte-mask to print SHR EDX,4 ; Divide second number by 16 MOV EBP,STSI CMP EBP,SSIZE2 JB SHORT SET8 SUB EDX,STSI ADD EDX,SSIZE2 SET8: MOV EBP,EDX MOV LSTB,EDX ; Last byte pointer INC EDX SUB EDX,SSIZE2 CMP EDX,65536 MOV ARGSIZE,DX JAE SHORT SET10 CMP DX,3584 ; Test is not necessary if DX<2^16 - 2^16/8 JBE SHORT SET9 ; (n2 can be any number up to 2^32) SUB EDX,65536 ; Otherwise, make sure that NEG EDX ; our test range lies SHL EDX,3 ; within 1 64k sector MOV EAX,EDX MUL EAX ; EDX:EAX now contains maximum allowable n2 JC SHORT SET9 ; We're ok if EDX>0, otherwise MOV EDX,NPRINT2 ; Check EAX against the requested value CMP EDX,EAX JA SHORT SET10 SET9: MOV CL,BL AND CL,00000111B ; CL cannot exceed 7 MOV INIM,1 SHL INIM,CL ; Get initial mask XOR EDX,EDX XOR ESI,ESI CLC RET ; Replace value in nprint2 with 1048545+n1-2(n1+1048545)^.5 ; Note - If n1 > 4293918750, then n1+1048545 will be greater than 4294967295 ; which will cause a carry error. In this case, set nprint2 equal to ; 4294443023, which is halfway between 4293918750 and 4294967295. ; n1 and n2 must satisfy the relationship: n2/16 + (n2^.5)/8 < 65536 + n1/16 SET10: TEST FLG1,10B JZ SHORT SET11 INC ECX SET11: MOV NO2A,ECX MOV DI,OFFSET NPRINT2 MOV ECX,NPRINT1 ADD ECX,1048545 JNC SHORT SET12 MOV EAX,4294443023 JMP SHORT SET13 SET12: MOV NPRINT2,ECX CALL SQROOT ; Store square root of NPRINT2 in NPRINT2 MOV SI,OFFSET NPRINT2 LODSD SHL EAX,1 SUB ECX,EAX MOV EAX,ECX SET13: STOSD MOV DI,OFFSET SSIZE CALL SQROOT ; Store square root of NPRINT2 in SSIZE JMP SET4 SETUP ENDP BUFFER PROC NEAR MOV AX,OFFSET STK POP BX MOV SP,AX PUSH BX MOV BX,AX PUSH DS POP AX ADD BX,15 SHR BX,4 ADD AX,BX MOV ES,AX MOV DS,AX XOR EAX,EAX MOV SI,AX MOV DI,AX MOV CX,16384 REP STOSD ; Zero 64K buffer RET BUFFER ENDP ; At this point everything has been initialized. We now start to eliminate ; all the composite numbers from 1-ssize and from n1-n2. NOCOMP PROC NEAR ASSUME ES:NOTHING,DS:NOTHING MOV SIFLAG,0 ADD SSIZEF,2 ; Next odd number JC SHORT NCMP1 CMP SSIZE,0 JE SHORT NCMPX MOV AX,SSIZEF CMP AX,SSIZE JA SHORT NCMP1 NCMPX: INC CL ; pointer in 8 bits ROL BL,1 ; bit mask, 8 bit roll and set Composite JNC SHORT NCMP2 XOR CL,CL ; Reset the bit counter back to zero INC SI CMP ESI,EBP JB SHORT NCMP2 NCMP1: RET NCMP2: MOV AL,[SI] AND AL,BL ; is it a prime, i.e. still a zero bit? JNZ NOCOMP ; no, its bit is set to 1 PUSH BX PUSH CX ; save bit counter PUSH ESI ; save byte pointer MOV BX,SSIZEF MOV DI,BX MOV EAX,EBX SHR DI,3 AND BX,7 MUL EAX MOV DX,BX MOV ESI,EAX MOV CX,AX CMP SSIZE,0 JE SHORT NCMP3 MOV AX,SSIZEF CMP AX,SSIZE JB SHORT NCMP3 POP ESI POP CX POP BX RET NCMP3: SHR ESI,4 AND CX,0FH SHR CX,1 CMP ESI,EBP JB SHORT NCMP6 MOV SIFLAG,1 CMP ESI,SSIZE2 JB NCMP12 MOV ESI,SSIZE2 ; We get here if ESI > EBP and JMP NCMP7 ; SSIZE2 <= SI NCMP4: ADD SI,DI ; point to next non-prime byte JC NCMP12 ADD CX,DX ; point to next non-prime bit in byte CMP CL,8 JB SHORT NCMP5 SUB CL,8 INC SI ; Don't allow SI to cross the JZ NCMP12 ; segment boundary NCMP5: CMP ESI,EBP JBE SHORT NCMP6 XOR SIFLAG,1 ; Reverse the flag JZ NCMP12 ; Jump if it was previously 1 CMP STSI,ESI JBE NCMP12 MOV ESI,EBP ; We get here if EBP < ESI < STSI SUB SI,ARGSIZE INC SI JMP SHORT NCMP7 NCMP6: CMP SIFLAG,1 JE SHORT NCMP11 CMP ESI,SSIZE2 JB SHORT NCMP11 CMP STSI,ESI JBE SHORT NCMP11 MOV SIFLAG,1 ; We get here if ESI <= EBP and MOV ESI,SSIZE2 ; SSIZE2 <= SI < STSI ; We get here the first time we enter the second area (n1 through n2). This ; area re-calculates our byte pointer (SI) and our bit pointer (CL). NCMP7: PUSH EBX PUSH EDX XOR DX,DX MOV BX,DX MOV EAX,N23 MOV BX,SSIZEF DIV EBX ; remainder in EDX MOV ECX,EDX CMP ECX,0 JE SHORT NCMP9 NEG ECX ADD ECX,EBX TEST ECX,1 ; Is it odd? JE SHORT NCMP8 ; No it's even - jump ADD ECX,EBX ; Yes NCMP8: SHR ECX,1 NCMP9: CMP ECX,8 JB SHORT NCMP10 SUB ECX,8 INC ESI CMP ESI,EBP JBE NCMP9 POP EDX POP EBX JMP SHORT NCMP12 NCMP10: POP EDX POP EBX NCMP11: MOV AL,1 SHL AL,CL OR [SI],AL ; mask this bit to show non-prime JMP NCMP4 NCMP12: POP ESI ; byte pointer POP CX ; bit counter POP BX JMP NOCOMP NOCOMP ENDP ; At this point we have all our prime numbers set. The only thing left to ; do is to print them on the screen. FINI PROC NEAR ASSUME DS:START,ES:START PUSH CS POP DS MOV DI,OFFSET NP$ MOV ECX,LSTB ; last byte pointer MOV EAX,STSI CMP EAX,SSIZE2 JBE SHORT FINI1 MOV EAX,SSIZE2 FINI1: MOV ESI,EAX ; initial byte pointer MOV AL,INIM ; initial mask TEST FLG1,1 JZ SHORT FINI2 DEC TLINE MOV EDX,2 ; Force the first prime to be 2 INC NPRIME MOV AL,2 CMP FLG2,1 ; Suppress individual primes ? JE SHORT FINI2 CALL PRT3 MOV AL,2 FINI2: CMP ECX,ESI JE SHORT FINI4 FINI3: CALL PRTEST JNC FINI3 INC SI ; Prepare to address the next byte CMP SI,CX ; Have we reached the end ? JB FINI3 ; Not yet - go check out this byte FINI4: XOR CX,CX MOV CL,EXTRA MOV CH,1 SHL CH,CL ROL CH,1 FINI5: CALL PRTEST CMP AL,CH JNE FINI5 RET FINI ENDP PRINT PROC NEAR BSF BX,AX SHL BX,1 INC BX DEC TLINE ; # on line JNZ SHORT PRT1 ; Jump if more numbers for this line CALL SCRLF ; Scroll screen 1 line PUSH NLINE ; Move this number POP TLINE ; into this area PRT1: XOR EDX,EDX MOV DX,SI MOV EAX,STSI CMP EAX,SSIZE2 JB SHORT PRT2 ADD EDX,STSI SUB EDX,SSIZE2 PRT2: SHL EDX,4 ADD EDX,EBX PRT3: PUSH CX PUSH SI PUSH ES PUSH CS POP ES MOV DI,OFFSET NP$ CALL BINDEC32 ; Convert binary EDX to decimal ES:DI MOV SI,[NPADDR] MOV AH,2 MOV CX,DIGITS OUTDS: LODSB MOV DL,AL INT 21H LOOP OUTDS POP ES POP SI POP CX RET PRINT ENDP PRTEST PROC NEAR MOV AH,AL AND AH,ES:[SI] ; Test this bit to see if it's a prime PUSH AX ; Store AX JNZ SHORT PRTEST1 ; Jump if not a prime INC NPRIME CMP FLG2,1 JE SHORT PRTEST1 CALL PRINT PRTEST1:POP AX ; Recall AX ROL AL,1 ; Get ready to look at the next bit RET PRTEST ENDP PRTX PROC NEAR MOV DI,OFFSET NP$ CALL BINDEC32 ; Convert binary EDX to decimal ES:DI MOV SI,[NPADDR] MOV AH,2 MOV CX,DIGITS OUTDS2: LODSB CMP BYTE PTR [SI],' ' JE SHORT PRTX2 MOV DL,AL INT 21H PRTX2: LOOP OUTDS2 RET PRTX ENDP GETNUM PROC NEAR GETN0: CMP BYTE PTR [SI],' ' ; Ignore any leading blanks JNE SHORT SKIPE INC SI JMP GETN0 SKIPE: XOR CX,CX ; Initialize the digit counter GETN1: LODSB ; Get the first digit CMP AL,CR ; Carriage return? JE SHORT GETNE ; Yes - we've gotten all our digits CMP AL,' ' ; Space? JE SHORT GETNE ; Yes - we've gotten all our digits CMP AL,3AH ; Below 3Ah? (this will determine carry flag) CMC ; Reverse the carry flag JC SHORT CKNE ; Jump if AL > 3Ah CMP AL,30H ; If AL >= 30h then AL is an ASCII number. CKNE: JB SHORT GETNC ; If AL < 30h, we're finished. INC CL ; Otherwise, increase the digit counter STOSB ; store this digit and JMP GETN1 ; look for our next digit GETNC: RET ; Return with carry flag set GETNE: CMP CL,11 ; First set the carry less than 11 digits CMC ; Then reverse (clear) the carry flag RET ; Return GETNUM ENDP ; Convert ascii decimal value in DS:SI to binary dword - result goes into ES:DI ; EAX register destroyed DECBIN32 PROC NEAR PUSH EBX XOR EBX,EBX ; zero initial binary double word MOV EAX,EBX ; and our decimal digit holder JMP SHORT DECBS ; skip first multiplication DECBL: IMUL EBX,10 ; multiply EBX by 10 DECBS: LODSB ; get next decimal SUB AL,30H ; drop ascii bias ADD EBX,EAX ; add next decimal to word LOOP DECBL ; continue for the rest of the digits MOV EAX,EBX STOSD POP EBX RET DECBIN32 ENDP SCRLF PROC NEAR MOV DX,OFFSET CRLF MOV AH,9 INT 21H RET SCRLF ENDP ; Convert 32 bit binary number in EDX to decimal - result in ES:DI BINDEC32 PROC NEAR IF IS8087 PUSH DI PUSH CX PUSH SI MOV DWORD PTR TMPBUF+4,0 MOV DWORD PTR TMPBUF,EDX FINIT FILD TMPBUF ; Load EDX FBSTP THISPRIME ; Store it as a packed BCD MOV SI,OFFSET THISPRIME MOV AL,'0' STOSB MOV AL,[SI+4] MOV AH,AL ROL AL,4 AND AX,0F0FH OR AX,3030H STOSW MOV CX,8 LODSD BINLOOP:ROL EAX,4 PUSH EAX AND AL,0FH OR AL,30H STOSB POP EAX LOOP BINLOOP POP SI POP CX POP DI PUSH DI ELSE PUSH BX PUSH CX PUSH SI PUSH DI MOV ESI,EDX ; save binary double word XOR AX,AX ; zero high decimal accumulator MOV BX,AX ; BX will hold high packed BCD MOV DX,AX ; DX will hold low packed BCD MOV CX,32 ; use all 32 bits of double word BIND1: SHL ESI,1 ; shift low word left XCHG DX,AX ; use DX low 4 digits first ADC AL,AL ; add al to al with carry bit DAA ; decimal adj al XCHG AL,AH ; now do the same with ah ADC AL,AL ; double and add carry DAA ; decimal adj XCHG AL,AH ; restore ax order XCHG DX,AX ; save resultant low BCD quartet XCHG BX,AX ; now use BX high 4 digits ADC AL,AL ; add al to al with carry bit DAA ; decimal adj al XCHG AL,AH ; now do the same with ah ADC AL,AL ; double and add carry DAA ; decimal adj XCHG AL,AH ; restore ax order XCHG BX,AX ; save resultant high BCD quartet ADC AL,AL ; accum highest digits in AL DAA ; as a pair of BCDs LOOP BIND1 ; do all 32 bits MOV SI,OFFSET TMPBUF ; our temporary buffer for packed BCD MOV [SI],BX ; middle word MOV [SI+2],DX ; low word MOV CX,1 ; local count MOV DX,3 ; anticipate two more words to unpack MOV AH,AL ; save nibble pair PUSH AX MOV AL,'0' STOSB POP AX JMP SHORT UNPL ; start with first nibble pair BINDU: ; expand packed BCD to ascii string XCHG DX,CX ; save external count LODSW ; get packed BCD word MOV CX,2 ; local count MOV BX,AX ; save ax MOV AL,AH ; start with ah UNPL: SHR AL,4 ; shift hi nibble OR AL,30H ; add ascii bias STOSB ; save MOV AL,AH ; get back ah AND AL,0FH ; mask lo nibble OR AL,30H ; add ascii bias STOSB ; save MOV AX,BX ; get back word MOV AH,AL ; save low byte LOOP UNPL ; local loop XCHG CX,DX ; restore external count LOOP BINDU ; finish all packed BCDs POP DI POP SI POP CX POP BX PUSH DI ENDIF BLANKL: CMP BYTE PTR [DI],'0' ; Replace leading zeros with blanks, JNE SHORT BLANKE MOV BYTE PTR [DI],' ' INC DI JMP BLANKL BLANKE: POP DI RET BINDEC32 ENDP SUMMARY PROC NEAR CMP NPRIME,1 JNE SHORT SUMM1 MOV SI,OFFSET NPS1 MOV DWORD PTR [SI+7],'$si ' ; If 1 prime, change "There are" to "There is" MOV SI,OFFSET NPS2 MOV BYTE PTR [SI+6],'$' ; and change "primes" to "prime" SUMM1: MOV DX,OFFSET NPS1 ; CR,LF,'There are$' MOV AH,9 INT 21H MOV EDX,NPRIME ; Total number of primes OR EDX,0 ; Any primes ? JE SHORT SUMM2 ; If 0, change to the word "no" CALL PRTX ; Otherwise print the number JMP SHORT SUMM3 ; and continue with the text SUMM2: MOV DWORD PTR NP1,'$on ' ; ' no$' MOV DX,OFFSET NP1 MOV AH,9 INT 21H SUMM3: MOV DX,OFFSET NPS2 ; ' primes$' MOV AH,9 INT 21H MOV DX,OFFSET NPS2A ; ' between$' MOV AH,9 INT 21H MOV EDX,[NO1A] ; Starting number CALL PRTX MOV DX,OFFSET NPS3 ; ' and$' MOV AH,9 INT 21H MOV EDX,[NPRINT2] ; Ending number CALL PRTX RET SUMMARY ENDP IF IS8087 SQROOT PROC NEAR ; Store square root of NPRINT2 in ES:DI FINIT FLDCW CW ; Set 8087 control word MOV DWORD PTR TMPBUF+4,0 ; Needed in case nprint2 > 2,147,483647 PUSH NPRINT2 POP DWORD PTR TMPBUF FILD TMPBUF ; Load nprint2 into the 8087 FSQRT ; Calculate the exact square root FIST DWORD PTR ES:[DI] ; Store it, rounding to the next higher integer RET SQROOT ENDP ELSE SQROOT PROC NEAR ; Estimate square root of nprint2 using PUSH EAX ; 2**(k-1) + nprint2/2**(k+1) where k PUSH ECX ; is the largest integer for which PUSH EDX ; nprint2 = 2**2k MOV EAX,NPRINT2 MOV EDX,EAX BSR ECX,EAX INC CX SHR CX,1 ; k MOV AX,1 SHL EAX,CL ; 2**k INC CX ; k+1 SHR EDX,CL ; nprint2/2**(k+1) SHR EAX,1 ; 2**(k-1) ADD AX,DX INC AX STOSW POP EDX POP ECX POP EAX RET SQROOT ENDP ENDIF EVEN STK EQU $+512 START ENDS END FIRST