Func.cpp

/*
 * Copyright (C) 2004 Bryant Lee
 *
 * This file is part of FPeriod.
 *
 * FPeriod is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * FPeriod is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with FPeriod; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

/**
 * Represents a polynomial function in terms x[-s,t] mod N
 *
 * Written by: Bryant Lee
 * Date: 10/31/04
 **/

#include "Func.h"
#include "FuncNode.h"
#include "StringOps.h"

#include <math.h> //for pow()

#include <fstream> //for printing

#include <string>
#include <list>

//non-member function definitions
bool isDigit(char c);
list<FuncNode*>* deepCopyList(const list<FuncNode*> &inputList);
void printList(ofstream & fout, const list<FuncNode*> &inputList);
void clearFuncNodeList(list<FuncNode*> &inputList);

extern int UINTSIZE;

//constructor
Func::Func(const string & iStr, int iShiftSize, bool opt) {
  unsigned int i = 0;
  int tIndex = 0, tConst = 0;
  string sub;
  
  //trim
  str = iStr;
  trim(str);
 
  //shiftsize
  shiftSize = iShiftSize;

  if(str[0] == 't' || str[0] == 'T') { //table function
    vector<string> subList;
    unsigned int j;

    type = 0;
    
    split(str, ',', subList);

    subList[0] = subList[0].substr(2,subList[0].length() - 2); //remove "t("
    trim(subList[0]);
    
    //get span
    span = atoi(subList[0].c_str());
    tablesize = (int) pow(shiftSize, span);
    
    //make the table
    fTable = new int[tablesize];

    for(i = 0, j = 0; i < subList[1].length() && j < tablesize; i++) {
      if(subList[1][i] != ' ' && subList[1][i] != '\t') {
	fTable[j] = subList[1][i] - 48; //convert char to integer
	j++;
      }
    }
  }
  else { //poly function
    type = 1;
    fTable = NULL;

    //special case: allow starting negative coefficient by prepending 0
    if(str[0] == '-')
      str.insert(0,"0");

    //parse the string and make a list
    while(i < str.length()) {
      if(str[i] == 'x') { //term
	unsigned int j = i + 1;
	while(str[j] != '[') {
	  j++;
	}
	unsigned int k = j + 1;
	while(str[k] != ']') {
	  k++;
	}
	sub = str.substr(j + 1, k - j - 1);
	trim(sub);
	tIndex = atoi(sub.c_str());
	fList.push_back(new FuncNode(1, tIndex));
      
	i = k + 1; //ITERATE
      }
      else if(isDigit(str[i])) {
	unsigned int j = i;
	while(j < str.length() && isDigit(str[j])) {
	  j++;
	}
	sub = str.substr(i, j - i);
	tConst = atoi(sub.c_str());
	fList.push_back(new FuncNode(3, tConst));
      
	i = j; //ITERATE
      }
      else if(str[i] == '+' ||
	      str[i] == '-' ||
	      str[i] == '*' ||
	      str[i] == '^') {
	int tOp = 0;
      
	switch(str[i]) {
	case '+':
	  tOp = 1;
	  break;
	case '-':
	  tOp = 2;
	  break;
	case '*':
	  tOp = 3;
	  break;
	case '^':
	  tOp = 4;
	  break;
	default:
	  break;
	}

	fList.push_back(new FuncNode(2, tOp));
      
	i++; //ITERATE
      }
      else {
	//ignore unidentified characters
	i++; //ITERATE
      }
    }

    if(opt) { //OPTIMIZED poly function
      type = 2;
  
      //Make a list of all terms used in function
      vector<int>::iterator new_end;
      list<FuncNode*>::iterator it;

      //Find all terms
      for(it = fList.begin(); it != fList.end(); it++) {
	if((*it)->type == 1) {
	  optTerms.push_back((*it)->val);
	}
      }

      sort(optTerms.begin(), optTerms.end()); //sort
      new_end = unique(optTerms.begin(),
		       optTerms.end()); //put duplicates at end

      optTerms.erase(new_end, optTerms.end()); //erase duplicates

      //Init optFindTerm
      unsigned int numTerms = optTerms.size();

      //key = term #, val = coord in "compact" array
      for(i = 0; i < numTerms; i++) {
	optFindTerm.insert(pair<int,int>(optTerms[i], i));
      }

      //DEBUG
      /*
      cout << "optFindTerm\n";
      map<int,int>::const_iterator mit;
      for(mit = optFindTerm.begin(); mit != optFindTerm.end(); mit++) {
	cout << mit->first << " " << mit->second << "\n";
      }
      cout << "END optFindTerm\n";
      */
      //END DEBUG
      
      //Create lookup table
      byte itTerms[numTerms];
      
      //zero itTerms
      for(i = 0; i < numTerms; i++)
	itTerms[i] = 0;

      do {
	optLookupMap.insert(pair<StorageKey, byte>(StorageKey(itTerms, numTerms),timage_by_inputs(itTerms, numTerms, optFindTerm)));
      }while(!iterateWord(itTerms, numTerms, shiftSize));

      //DEBUG
      /*
      cout << "Lookup Map\n";
      map<StorageKey,byte>::const_iterator mit;
      for(mit = optLookupMap.begin(); mit != optLookupMap.end(); mit++) {
	mit->first.print();
	cout << " -> " << (int) mit->second << "\n";
      }
      cout << "END Lookup Map\n";
      */
      //END DEBUG
    }
  }
}

//destructor
Func::~Func() {
  clearFuncNodeList(fList);
  delete fTable;
}

//put image of word x in output argument
void Func::image(byte *word, int wordLength, byte * output) {
  int i;

  for(i = 0; i < wordLength; i++) {
    output[i] = timage(word, wordLength, i);
  }
}

//put image of word x in output argument
//NOTE: the 4th parameter, blocks, can be derived from wordLength, but
//we avoid the division by passing it as a param.
void Func::image(unsigned int * word, int wordLength, unsigned int *output,
		 unsigned int blocks) {
  int i;

  //zero output[]
  for(i = 0; i < (int)blocks; i++) {
    output[i] = 0;
  }

  int blocki = 0, offseti = 0;
  for(i = 0; i < wordLength; i++) {
    output[blocki] |= (timage(word, wordLength, i) << offseti);

    offseti++;
    if(offseti >= UINTSIZE) {
      blocki++;
      offseti -= UINTSIZE;
    }
  }
}

//generates the index-th term of the image of x
byte Func::timage(byte *word, int wordLength, int index) {
  byte ret = 0;

  if(type == 0) { //table function
    unsigned int sum = 0, i, access;

    for(i = 0; i < span; i++) {
      access = (index + i) % wordLength;
      sum += word[access] * (int)pow(shiftSize, span - (i+1));
    }

    ret = fTable[sum];
  }
  else if(type == 1) { //poly function
    list<FuncNode*> *currList = deepCopyList(fList);
    list<FuncNode*>::iterator it, pit, sit;
    FuncNode *curr, *pre, *succ;
  
    //Perform ^
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && (*it)->val == 4) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;
	curr->val = (int) pow(pre->termValue(word, wordLength, index),
			      succ->termValue(word, wordLength, index));
	curr->val = curr->val % shiftSize;

	//no need to check for negative residual because power function
	//cannot make a positive integer negative.

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }

    //Perform *
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && (*it)->val == 3) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;
	curr->val = (pre->termValue(word, wordLength, index) *
		     succ->termValue(word, wordLength, index)) % shiftSize;

	//no need to check for negative residual because *
	//cannot make a positive integer negative.

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }

    //Perform +/-
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && ((*it)->val == 1 || (*it)->val == 2)) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;

	if(curr->val == 2) { //perform -
	  curr->val = (pre->termValue(word, wordLength, index) -
		       succ->termValue(word, wordLength, index)) % shiftSize;

	  //check for negative residual
	  if(curr->val < 0)
	    curr->val += shiftSize;

	}else { //curr.val == 1, perform +
	  curr->val = (pre->termValue(word, wordLength, index) +
		       succ->termValue(word, wordLength, index)) % shiftSize;
	}      

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }
  
    //special case when F = x[j] for a single j and no operations
    curr = *(currList->begin());
    if(curr->type == 1) {
      curr->val = curr->termValue(word, wordLength, index) % shiftSize;
      if(curr->val < 0)
	curr->val += shiftSize;
      curr->type = 3;
    }

    //We must capture the return value before we call
    //clearFuncNodeList()
    ret = curr->val;

    //DEBUG
    //printList(*currList);
  
    //deletes the actual FuncNodes, not just their pointers
    clearFuncNodeList(*currList);

    //delete the list
    delete currList;
  }
  else { //type == 2, optimized poly
    unsigned int numTerms = optTerms.size();
    byte itTerms[numTerms];
    unsigned int i; //iterator
    int a; //temporary variable

    for(i = 0; i < numTerms; i++) {
      a = (index + optTerms[i]) % wordLength;

      if(a < 0) {
	a += wordLength; //adjust for c's negative residuals
      }

      itTerms[i] = word[a];
    }
   
    ret = optLookupMap.find(StorageKey(itTerms, numTerms))->second;
   
    //DEBUG
    /*
    cout << "Word: ";
    printArray(word, wordLength);
    cout << "Index: " << index << "\n";
    cout << "itTerms: ";
    printArray(itTerms, numTerms);
    cout << "ret: " << ret << "\n";
    */
  }

  return ret;
}

//generates the index-th term of the image of x
unsigned int Func::timage(unsigned int *word, int wordLength, int index) {
  unsigned int ret = 0;

  if(type == 0) { //table func
    unsigned int sum = 0, i;

    int access;
    int blocki, offseti;
    access = index; //the actual index into the word

    blocki = index / UINTSIZE; //the block

    //the divide could also be done by while loop...
    /*
    blocki = 0; //the block
    t1 = index - UINTSIZE;
    while(t1 >= 0) {
      blocki++;
      t1 -= UINTSIZE;
    }
    */
    
    //NOTE: this does offseti = index % UINTSIZE 
    offseti = index - UINTSIZE*blocki; //offset within the block

    for(i = 0; i < span; i++) {
      if((word[blocki] >> (offseti)) & 1) {
	sum |= (1 << (span - (i+1)));
      }
      
      access++;
      if(access >= wordLength) { //wrap-around to beginning of word
	access = 0;
	blocki = 0;
	offseti = 0;
      }
      else {
	offseti++;
	if(offseti >= UINTSIZE) {
	  blocki++;
	  offseti = 0;
	}
      }
    }

    ret = fTable[sum];
  }
  else if(type == 1){ //poly func
    list<FuncNode*> *currList = deepCopyList(fList);
    list<FuncNode*>::iterator it, pit, sit;
    FuncNode *curr, *pre, *succ;
  
    //Perform ^
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && (*it)->val == 4) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;
	curr->val = (int) pow(pre->termValue(word, wordLength, index),
			      succ->termValue(word, wordLength, index));
	curr->val = curr->val % shiftSize;

	//no need to check for negative residual because power function
	//cannot make a positive integer negative.

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }

    //Perform *
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && (*it)->val == 3) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;
	curr->val = (pre->termValue(word, wordLength, index) *
		     succ->termValue(word, wordLength, index)) % shiftSize;

	//no need to check for negative residual because *
	//cannot make a positive integer negative.

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }

    //Perform +/-
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && ((*it)->val == 1 || (*it)->val == 2)) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;

	if(curr->val == 2) { //perform -
	  curr->val = (pre->termValue(word, wordLength, index) -
		       succ->termValue(word, wordLength, index)) % shiftSize;

	  //check for negative residual
	  if(curr->val < 0)
	    curr->val += shiftSize;

	}else { //curr.val == 1, perform +
	  curr->val = (pre->termValue(word, wordLength, index) +
		       succ->termValue(word, wordLength, index)) % shiftSize;
	}      

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }
  
    //special case when F = x[j] for a single j and no operations
    curr = *(currList->begin());
    if(curr->type == 1) {
      curr->val = curr->termValue(word, wordLength, index) % shiftSize;
      if(curr->val < 0)
	curr->val += shiftSize;
      curr->type = 3;
    }

    //We must capture the return value before we call
    //clearFuncNodeList()
    ret = curr->val;

    //DEBUG
    //printList(*currList);
  
    //deletes the actual FuncNodes, not just their pointers
    clearFuncNodeList(*currList);

    //delete the list
    delete currList;
  }
  else { //type == 2, optimized poly
    unsigned int numTerms = optTerms.size();
    byte itTerms[numTerms];
    unsigned int i; //iterator
    int a; //temporary variable

    for(i = 0; i < numTerms; i++) {
      a = (index + optTerms[i]) % wordLength;

      if(a < 0) {
	a += wordLength; //adjust for c's negative residuals
      }

      if(a < UINTSIZE) { // if a < UINTSIZE, avoid divide ops
	itTerms[i] = (word[0] & (1 << a)) >> a;
      }
      else {
	itTerms[i] = (word[a/UINTSIZE] & (1 << (a % UINTSIZE))) >> (a % UINTSIZE);
      }
    }
   
    ret = optLookupMap.find(StorageKey(itTerms, numTerms))->second;
   
    //DEBUG
    /*
    cout << "Word: ";
    printArray(word, wordLength);
    cout << "Index: " << index << "\n";
    cout << "itTerms: ";
    printArray(itTerms, numTerms);
    cout << "ret: " << ret << "\n";
    */
  }

  return ret;
}

//print
void Func::print(ofstream & fout) {
  if(type == 0) {
    unsigned int i;

    fout << "(";
    fout << span;
    fout << ", ";

    for(i = 0; i < tablesize; i++) {
      fout << fTable[i];
    }
    
    fout << ")";
    fout << "\n";
  }
  else {
    printList(fout, fList);
  }
}

//deletes the FuncNodes (the ones pointed to by elements in list)
void clearFuncNodeList(list<FuncNode*> &inputList) {
  list<FuncNode*>::iterator it;

  for(it = inputList.begin(); it != inputList.end(); it++) {
    delete (*it);
  }
}

//print a list
void printList(ofstream & fout, const list<FuncNode*> &inputList) {
  list<FuncNode*>::const_iterator it;

  for(it = inputList.begin(); it != inputList.end(); it++) {
    (*it)->print(fout);
  }

  fout << "\n";
}

//deep copy the list
list<FuncNode*>* deepCopyList(const list<FuncNode*> &inputList) {
  list<FuncNode*> *newList = new list<FuncNode*>;
  list<FuncNode*>::const_iterator it;
  
  for(it = inputList.begin(); it != inputList.end(); it++) {
    newList->push_back((*it)->deepCopy());
  }

  return newList;
}

//returns true if c is a digit
bool isDigit(char c) {
  return (c >= 48 && c <= 57); //calculated by ascii
}

// (used in opt polynomial functions only: for precomputing to lookup table)
// generates value of function based on inputs
byte Func::timage_by_inputs(byte *itTerms, int numTerms,
			    const map<int,int> &optFindTerm) {
  byte ret = 0;

  list<FuncNode*> *currList = deepCopyList(fList);
  list<FuncNode*>::iterator it, pit, sit;
  FuncNode *curr, *pre, *succ;
  
  if(type == 0) {
    cout << "ERROR: please terminate program\n";
  }
  else {
    //Perform ^
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && (*it)->val == 4) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;
	curr->val = (int) pow(pre->termValue_by_inputs(itTerms, numTerms, optFindTerm),
			      succ->termValue_by_inputs(itTerms, numTerms, optFindTerm));
	curr->val = curr->val % shiftSize;

	//no need to check for negative residual because power function
	//cannot make a positive integer negative.

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }

    //Perform *
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && (*it)->val == 3) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;
	curr->val = (pre->termValue_by_inputs(itTerms, numTerms, optFindTerm) *
		     succ->termValue_by_inputs(itTerms, numTerms, optFindTerm)) % shiftSize;

	//no need to check for negative residual because *
	//cannot make a positive integer negative.

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }

    //Perform +/-
    for(it = currList->begin(); it != currList->end(); it++) {
      if((*it)->type == 2 && ((*it)->val == 1 || (*it)->val == 2)) {
	curr = *it;
      
	it--; //go to pre
	pre = *it;
	pit = it;
	it++;
	it++; //go to succ
	succ = *it;
	sit = it;
	it--; //go to curr
      
	curr->type = 3;

	if(curr->val == 2) { //perform -
	  curr->val = (pre->termValue_by_inputs(itTerms, numTerms, optFindTerm) -
		       succ->termValue_by_inputs(itTerms, numTerms, optFindTerm)) % shiftSize;

	  //check for negative residual
	  if(curr->val < 0)
	    curr->val += shiftSize;

	}else { //curr.val == 1, perform +
	  curr->val = (pre->termValue_by_inputs(itTerms, numTerms, optFindTerm) +
		       succ->termValue_by_inputs(itTerms, numTerms, optFindTerm)) % shiftSize;
	}      

	//clean up
	currList->erase(pit);
	currList->erase(sit);
	delete pre;
	delete succ;
      }
    }
  
    //special case when F = x[j] for a single j and no operations
    curr = *(currList->begin());
    if(curr->type == 1) {
      curr->val = curr->termValue_by_inputs(itTerms, numTerms, optFindTerm) % shiftSize;
      if(curr->val < 0)
	curr->val += shiftSize;
      curr->type = 3;
    }

    //We must capture the return value before we call
    //clearFuncNodeList()
    ret = curr->val;

    //DEBUG
    //printList(*currList);
  
    //deletes the actual FuncNodes, not just their pointers
    clearFuncNodeList(*currList);

    //delete the list
    delete currList;
  }

  return ret;
}

//return true if this is an opt function
bool Func::isOpt() {
  return (type == 2);
}