/***********************************/
/*                                 */
/*   Factorization of integers     */
/*   uses the onHand/RuputerAPI    */
/*                                 */
/*   William A. Stein, 6:23pm      */
/*                                 */
/***********************************/

/*
When you compile, an executable named factor.exf will be generated.
Then, after uploading it and starting, the softkeyboard will appear
in numerical input mode.  Enter a number, and then its factorization
will appear.

===============================================================================
 Copyright (c) 2000.  William Stein

 This is free open-source software. Enjoy!
===============================================================================
*/


#include <stdio.h>
#include <string.h>

#include "softkey.h"
#include "psdos.h"
#include "lcdbios.h"
#include "wbios.h"
#include "rupsys.h"
#include "font.h"


typedef unsigned long integer;
#define MAX_PRIME_DIVISORS 64

static const RECT CLRLCD={0,0,101,63};

void    factor(integer N, integer *primes, integer *exponents);
integer get_input();
void    display_answer(integer N, integer *primes, integer *exponents);


/*-----------------------------------------------------------*/
/*	 Main					      	  						 */
/*-----------------------------------------------------------*/

int main(void)
{
  integer N;
  integer primes[MAX_PRIME_DIVISORS], 
          exponents[MAX_PRIME_DIVISORS];

  screen(1);              /* Graphic mode             */
  gv_place(0,0);          /* XY coordinates  X:0, Y:0 */
  endWaiting();           /* Stop startup animation.  */

  N = get_input();
  if (N <= 0) 
    dos_exit(0);
  primes[0]=0;                  /* initial to length 0 */
  gv_kput(3,10,"Factoring...",5,0,0);
  factor(N,primes,exponents);   /* recursive trial division algorithm */
  display_answer(N,primes,exponents);
}


/********************  SYSTEM I/O ****************/

#define Key_enter		0x0008		
#define Key_menu		0x0002		

void display_text(char* s0, char* s1, char* s2)
{
  char* Mess[3];
  Mess[0] = s0; 
  Mess[1] = s1;
  Mess[2] = s2;

  pv_clear((RECT *)&CLRLCD);          /* Clear screen. */
  if (dispMess((char**) Mess, 3 ) == -1) 
    dos_exit(0);
}

/* the library function that's supposed to do this doesn't work!! */

integer str_to_integer(char* str)
{
  integer N = 0;
  integer t = 1;
  int i;
  
  if (strlen(str) > 9) {
    display_text("The maximum","number of digits", "is 9.");
    return 0;
  }

  for (i = strlen(str)-1; i>=0; i--) { 
    if (str[i] < '0' || str[i] > '9') {
      display_text("The input", str, "is not valid.");
      return 0;
    }
    N += t * ((int)(str[i]-'0'));
    t = t * 10;
  }

  return N;
}

integer get_input(void)
{
  integer N;
  char s[64];

  char str[32];
  int i;

  KANJI_PUT Inputstr = {{0,32},str,5,0,0};
  STRSTS ctrl = { picNAME , 5,  2,2,0,0,0,31};

  for (i=0; i<32; i++)
     str[i]='\0';

  if (softkey(&ctrl,Inputstr.str,0,0) == -1)
    dos_exit(0);

  return str_to_integer(Inputstr.str);
}



void display_answer(integer N, integer *primes, integer *exponents)
{ 
  char buf[64], num[64];
  char* s;
  int i;
  int bt;

  buf[0] = '\0';
  s = buf;

  for (i=0; i<MAX_PRIME_DIVISORS; i++) {
    if (primes[i] == 0) break;
    if (i>0) 
      sprintf(s, "*");
    s += strlen(s);
    sprintf(s,"%lu", primes[i]);
    s += strlen(s);
    if (exponents[i] > 1) {
      sprintf(s,"^%lu", exponents[i]);
      s += strlen(s);
    }
  }

  sprintf(num, "%lu", N);
  display_text(num, "=", buf);
}


/******************* MATHS *******************/

/* The algorithm is trial division, which should be fine.
   Our integers are of type "int", so they are quite tiny. */

integer split(integer N)
{
  static integer dif[] = {6, 4, 2, 4, 2, 4, 6, 2};
  integer m;
  integer ONE = 1, TWO = 2, THREE = 3, FIVE = 5;

  int i;

  if (N==ONE) {
    return ONE;
  } else if (N % TWO == 0) {
    return TWO;
  } else if (N % THREE == 0) {
    return THREE;
  } else if (N % FIVE == 0) {
    return FIVE;
  }


  for (m=7, i=1; m*m <= N;) {
    if (N % m == 0) 
      return m;
    m += dif[(i++)%8 ];
  }

  return N;
}

void factor(integer N, integer *primes, integer *exponents)
{
  int i, j;
  integer n, m;
  char buf0[64], buf1[64], buf2[64];

  integer primes_m[MAX_PRIME_DIVISORS], 
          exponents_m[MAX_PRIME_DIVISORS];
  primes_m[0];

  n = split(N);
  m = N / n;

  if (m == 1) {   /* N is prime */
    primes[0] = n;
    exponents[0] = 1;
    primes[1] = 0;
    return;
  }

  factor(n, primes, exponents);
  factor(m, primes_m, exponents_m);

  /* combine together the results */
  for (i=0; i<MAX_PRIME_DIVISORS; i++) {
    if (primes_m[i] == 0) break;
    for (j=0; j<MAX_PRIME_DIVISORS; j++) {
      if (primes[j] == 0) {
	primes[j]   = primes_m[i];
	exponents[j]= exponents_m[i];
	primes[j+1] = 0;
	break;
      } else if (primes[j] == primes_m[i]) {
	exponents[j] += exponents_m[i];
	break;
      }
    }
  }
  return;
}