/* *****************************************

		Prime Numbers

    (c) 1995 by Topical Software

    Demo programm of DOS-Extender Swallow

  ***************************************** */

#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <dos.h>
#include <alloc.h>
#include <math.h>
#include <time.h>
#include "swallow.h"

/* We use a huge bit-field to store whether a number was prime or not.
  (0=prime, 1=not prime)

  Because huge addresses are not supported by Swallow (and would be too slow)
  we have to split the field into pieces, which addresses are stored in
  MainTable.
*/

#define ERR_USERABORT -1
#define ERR_OUTOFMEM -2

#define MAXNUMBER 0x40000000			// maximum number
#define BYTEARRAYSHIFT 3			// bits per byte
#define MAINTABLESHIFT (14 + BYTEARRAYSHIFT)	// address bits per main table entry

typedef unsigned char ByteArray[1 << (MAINTABLESHIFT - BYTEARRAYSHIFT)];
						// one piece of the bit-field

#define BYTEARRAYMASK ((long)(sizeof(ByteArray) - 1) << BYTEARRAYSHIFT)
				// mask to get address bits within ByteArray
#define BITMASK ((1 << BYTEARRAYSHIFT) - 1)
				// mask to get address within byte
ByteArray far *MainTable[(MAXNUMBER) >> MAINTABLESHIFT];
				// table of bit-field pieces

int MainTableEntrys = 0;	// current entries


// public function to calculate square root 
void PublicSqrt(long int far *value) {
  *value = sqrt(*value) + 0.5;
}

// time stopping routines and variables }

#define TickCount ((int far *) MK_FP(Seg0040, 0x6c))

long int StartTime;

void StartStopping(void) {
  StartTime = clock();
}

void ShowDuration(void) {
int Duration;
long int Milliseconds;

  Duration = clock() - StartTime;
  Milliseconds = (long)(Duration) * 100.0 * 0x100 / 0x1234;
  cprintf("The search took %i.%03i seconds.\r\n",
    (int)(Milliseconds / 100), (int)(Milliseconds % 100 * 10));
}

/* Show search result
   HighestNumber - highest number to check
   Count - count of prime numbers <= HighestNumber, or:
      ERR_OUTOFMEM = Out of memory
      ERR_USERABORT = User abort
*/
void ShowResult(long int HighestNumber, long int Count) {

  cprintf("                                                              \r\n");
  switch (Count) {
    case ERR_OUTOFMEM: cprintf("Not enough memory available!\r\n\r\n");
		       break;
    case ERR_USERABORT: cprintf("Abort by user!\r\n\r\n");
			break;
    default:
      ShowDuration();
      cprintf("Within the first %li numbers are %li prime numbers.\r\n\r\n",
	HighestNumber, Count);
  }
}

/* show status and check user abort
   message - 0="Checking", 1="Marking"
   -> 0 - no user abort
      !=0 - user abort
*/
int CheckBreak(int Message, long int CurNumber, long int Primes, long int Marking) {

  if (Message == 0)
    cprintf("Check number %li (%li primes)", CurNumber, Primes);
  else
    cprintf("Check %li, mark number %li (%li primes)", CurNumber, Marking, Primes);
  clreol();
  putch('\r');
  return((kbhit() && getch() == 0x1b));
}

// free complete bit-field
void FreeMainTable() {
int i;

  for (i = 0; i < MainTableEntrys; ++i)
    if (MainTable[i]) farfree(MainTable[i]);
  MainTableEntrys = 0;
}


/* Count prime numbers within the first "HighestNumber" numbers
   -> ERR_OUTOFMEM = Out of memory
      ERR_USERABORT = Use abort
      >=0 count of prime numbers
*/
long int CountPrimes1(long int MaxNumber) {
int i;
int OldTime;
long int Count;
long int CurNumber, TmpNumber;

  // prepare bit-field 
  memset(MainTable, 0, sizeof(MainTable));
  MainTableEntrys = (MaxNumber + ((long)1 << MAINTABLESHIFT) - 1) >> MAINTABLESHIFT;
  for (i = 0; i < MainTableEntrys; ++i) {
    if (!(MainTable[i] = farcalloc(1, sizeof(ByteArray)))) {
      return(ERR_OUTOFMEM);
    }
  }
  Count = 0;
  OldTime = *TickCount - 6;

  // Search number by number 
  for (CurNumber = 2; CurNumber <= MaxNumber; ++CurNumber) {
    if (*TickCount - OldTime > 0) {
      OldTime = *TickCount;
      if (CheckBreak(0, CurNumber, Count, 0))
	return(ERR_USERABORT);
    }
    if (!((*MainTable[CurNumber >> MAINTABLESHIFT])
       [(CurNumber & BYTEARRAYMASK) >> BYTEARRAYSHIFT] &
       1 << (CurNumber & BITMASK))) {
      // there is a prime number
      ++Count;
      for (TmpNumber = CurNumber; TmpNumber <= MaxNumber; TmpNumber += CurNumber) {
	(*MainTable[TmpNumber >> MAINTABLESHIFT])
	  [(TmpNumber & BYTEARRAYMASK) >> BYTEARRAYSHIFT] |=
	  1 << (TmpNumber & BITMASK);
      }
    }
  }

  // that's all 
  return(Count);
}


/* Count prime numbers within the first "HighestNumber" numbers
   -> ERR_OUTOFMEM = Out of memory
      ERR_USERABORT = Use abort
      >=0 count of prime numbers
   only the odd numbers are regarded
*/
long int CountPrimes2(long int MaxNumber) {
int i;
int OldTime;
long int Count;
long int CurNumber, TmpNumber;
long int CurIndex, TmpIndex, Increment;
long int MaxIndex;

  // prepare bit-field, it has only half of the size 
  memset(MainTable, 0, sizeof(MainTable));
  MaxIndex = (MaxNumber + 1) >> 1;
  MainTableEntrys = (MaxIndex + ((long)1 << MAINTABLESHIFT) - 1) >> MAINTABLESHIFT;
  for (i = 0; i < MainTableEntrys; ++i) {
    if (!(MainTable[i] = farcalloc(1, sizeof(ByteArray)))) {
      return(ERR_OUTOFMEM);
    }
  }
  Count = 1;
  OldTime = *TickCount - 6;

  // Search number by number, only the odd ones
  for (CurNumber = 3; CurNumber <= MaxNumber; CurNumber += 2) {
    CurIndex = CurNumber >> 1;
    if (*TickCount - OldTime > 0) {
      OldTime = *TickCount;
      if (CheckBreak(0, CurNumber, Count, 0))
	return(ERR_USERABORT);
    }
    if (!((*MainTable[CurIndex >> MAINTABLESHIFT])
       [(CurIndex & BYTEARRAYMASK) >> BYTEARRAYSHIFT] &
       1 << (CurIndex & BITMASK))) {
      // there is a prime number 
      ++Count;
      Increment = 2 * CurNumber;
      // mark all _odd_ multiples of the prime number as non-primes 
      for (TmpNumber = CurNumber + Increment; TmpNumber <= MaxNumber; TmpNumber += Increment) {
	TmpIndex = TmpNumber >> 1;
	(*MainTable[TmpIndex >> MAINTABLESHIFT])
	  [(TmpIndex & BYTEARRAYMASK) >> BYTEARRAYSHIFT] |=
	  1 << (TmpIndex & BITMASK);
      }
    }
  }

  // that's all
  return(Count);
}


/* Count prime numbers within the first "HighestNumber" numbers
   -> ERR_OUTOFMEM = Out of memory
      ERR_USERABORT = Use abort
      >=0 count of prime numbers
   only the odd numbers are regarded;
   additionally we search block by block to access memory only local
     - very important with virtual memory!
     - at first we check the first "BlockLen" numbers (=1 block) normally
     - now we mark multiples of the prime number within the 2. block
     - now we search the primes within the 2. block
     - now we mark multiples of the first 2 blocks within the 3.
     - and so on...
*/
long int CountPrimes3(long int MaxNumber) {
int i;
int OldTime;
long int Count;
long int CurNumber, TmpNumber;
long int CurIndex, TmpIndex, Increment;
long int MaxIndex;
long int BlockLen;
int BlockNumber;
long int BlockBegin, BlockEnd;
long int ScanBlockBegin, ScanBlockEnd;
long int ScanEnd;
int LastScanBlock, ScanBlock;
ByteArray far *CurBlock, far *CurScanBlock, far *TmpBlock;
long int Factor;

  // prepare bit-field, it has only half of the size;
  // additionally we need a temporary block for marking of primes within
  // current block
  memset(MainTable, 0, sizeof(MainTable));
  if (!(TmpBlock = farcalloc(1, sizeof(ByteArray)))) return(ERR_OUTOFMEM);
  MaxIndex = (MaxNumber + 1) >> 1;
  MainTableEntrys = (MaxIndex + ((long)1 << MAINTABLESHIFT) - 1) >> MAINTABLESHIFT;
  for (i = 0; i < MainTableEntrys; ++i) {
    if (!(MainTable[i] = farcalloc(1, sizeof(ByteArray)))) {
      farfree(TmpBlock[i]);
      return(ERR_OUTOFMEM);
    }
  }
  Count = 1;
  BlockLen = (((long)1 << MAINTABLESHIFT) << 1);
  OldTime = *TickCount - 6;

  // search block by block 
  for (BlockNumber = 0; BlockNumber < MainTableEntrys; ++BlockNumber) {

    // prepare copying primes from previous blocks 
    BlockBegin = (long)BlockNumber * BlockLen + 1;
    BlockEnd = BlockBegin + BlockLen - 2;
    if (BlockBegin < 3) BlockBegin = 3;
    if (BlockEnd > MaxNumber) BlockEnd = MaxNumber;
    ScanEnd = sqrt(BlockEnd) + 0.5;
    if (ScanEnd > BlockBegin) ScanEnd = BlockBegin - 2;
    CurBlock = MainTable[BlockNumber];
    LastScanBlock = ScanEnd >> (MAINTABLESHIFT + 1);

    // clear current block (all number are primes up to now) 
    memcpy(TmpBlock, CurBlock, sizeof(ByteArray));

    // copy prime number from previous block, block by block 
    for (ScanBlock = 0; ScanBlock <= LastScanBlock; ++ScanBlock) {

      // prepare copying 
      ScanBlockBegin = (long)ScanBlock * BlockLen + 1;
      ScanBlockEnd = ScanBlockBegin + BlockLen - 2;
      if (ScanBlockEnd > ScanEnd) ScanBlockEnd = ScanEnd;
      if (ScanBlockBegin < 3) ScanBlockBegin = 3;
      CurScanBlock = MainTable[ScanBlock];

      // scan known block bit by bit 
      for (CurNumber = ScanBlockBegin; CurNumber <= ScanBlockEnd; CurNumber += 2) {
	CurIndex = CurNumber >> 1;
	if (((*CurScanBlock)[(CurIndex & BYTEARRAYMASK) >> BYTEARRAYSHIFT] &
	   1 << (CurIndex & BITMASK))) {
	  // there is a known prime number 
	  if (*TickCount - OldTime > 0) {
	    OldTime = *TickCount;
	    if (CheckBreak(1, BlockBegin, Count, CurNumber)) {
	      farfree(TmpBlock);
	      return(ERR_USERABORT);
	    }
	  }
	  Increment = CurNumber << 1;
	  Factor = (BlockBegin + CurNumber - 1) / CurNumber;
	  if (!(Factor & 1)) ++Factor;

	  // mark multiples of the prime number as non-primes 
	  for (TmpNumber = Factor * CurNumber;
	      TmpNumber <= BlockEnd; TmpNumber += Increment) {
	    TmpIndex = TmpNumber >> 1;
	    (*TmpBlock)[(TmpIndex & BYTEARRAYMASK) >> BYTEARRAYSHIFT] |=
	      1 << (TmpIndex & BITMASK);
	  }
	}
      }
    }

    // now search primes within the current block 
    for (CurNumber = BlockBegin; CurNumber <= BlockEnd; CurNumber += 2) {
      CurIndex = CurNumber >> 1;
      if (!((*TmpBlock)[(CurIndex & BYTEARRAYMASK) >> BYTEARRAYSHIFT] &
	 1 << (CurIndex & BITMASK))) {

	// there is one 
	if (*TickCount - OldTime > 0) {
	  OldTime = *TickCount;
	  if (CheckBreak(0, CurNumber, Count, 0)) {
	    farfree(TmpBlock);
	    return(ERR_USERABORT);
	  }
	}
	++Count;
	(*CurBlock)[(CurIndex & BYTEARRAYMASK) >> BYTEARRAYSHIFT] |=
	  1 << (CurIndex & BITMASK);
	Increment = CurNumber << 1;

	// mark multples 
	for (TmpNumber = CurNumber + Increment; TmpNumber <= BlockEnd; TmpNumber += Increment) {
	  TmpIndex = TmpNumber >> 1;
	  (*TmpBlock)[(TmpIndex & BYTEARRAYMASK) >> BYTEARRAYSHIFT] |=
	    1 << (TmpIndex & BITMASK);
	}
      }
    }
  }
  farfree(TmpBlock);

  // phew... 
  return(Count);
}


/* Count prime number within the first "HighestNumber" numbers

   -> ERR_OUTOFMEM = Out of memory
      ERR_USERABORT = Use abort
      >=0 count of prime numbers
   assembler version of CountPrimes3
   nothing extra is changed compared to the Pascal/C-Version

   Prim32.Asm contains the code of this procedure 
*/
long int CountPrimes4(long int MaxNumber, long int BlockLen);

// parameter input
void GetParameters(long int *MaxNumber, long int *BufferLen, int *Kind) {
long int Maximum;
char dummy;

  directvideo = 1;
  highvideo();
  cprintf("\r\nPrime Number Calculation                         (c) 1995 Topical Software\r\n\r\n");
  lowvideo();
  cprintf("This program searches all prime numbers within the first n\r\n");
  cprintf("numbers by the Sieve of Eratosthenes.\r\n\r\n");
  cprintf("There is: method 1 - simple search\r\n");
  cprintf("          method 2 - skip odd numbers\r\n");
  cprintf("          method 3 - like method 2, but with optimized access\r\n");
  cprintf("          method 4 - method 3, but with 32 bit assembler code\r\n\r\n");

  Maximum = farcoreleft() * 16;
  if (Maximum > MAXNUMBER) Maximum = MAXNUMBER;
  cprintf("Up to which number should be searched (< %li)? ", Maximum);
  while (scanf("%li", MaxNumber) != 1 || *MaxNumber <= 2) scanf("%1c", &dummy);
  cprintf("\r\nWhich system should be used (1..4; 0=Abort) ? ");
  while (scanf("%i", Kind) != 1 || *Kind < 0 || *Kind > 4) scanf("%1c", &dummy);
  if (*Kind == 4) {
    cprintf("\r\nHow much buffer memory should be used (4096..%li)? ", farcoreleft());
    while (scanf("%li", BufferLen) != 1 || *BufferLen < 10) scanf("%1c", &dummy);
  }
}


int main() {
long int MaxNumber, BufferLen, Count;
int Kind;

  SetBreakCheck(1);
  InitSwapFile(-1, 0);
  UseBaseMem();
  GetParameters(&MaxNumber, &BufferLen, &Kind);
  StartStopping();
  switch (Kind) {
    case 1:
      Count = CountPrimes1(MaxNumber); break;
    case 2:
      Count = CountPrimes2(MaxNumber); break;
    case 3:
      Count = CountPrimes3(MaxNumber); break;
    case 4:
      if (SwallowIsActive != swa_protected) {
	cprintf("\r\nSorry, 32 bit assembler code does not work within Real Mode.\r\n");
	Count = 0;
      } else
	Count = CountPrimes4(MaxNumber, BufferLen);
      break;
  }
  if (Kind) ShowResult(MaxNumber, Count);
  return(1);
}