/*
 *  vecSHIFT.c
 *  
 *  A 128 bit AltiVec implementation of the SHIFT algorithm
 *
 *  Created by Michael Feiri on Fri Jan 04 2002.
 *  Copyright (c) 2001 Michael Feiri. All rights reserved.
 *
 */

#include <stdio.h>

#undef NUMWORDS
#undef MAXMARKS
#define NUMWORDS 2	/* 2 words (2*128=256) -> we can create rulers up to a length of 255 */
                        /* but thanks to "principle #1" we can safely get rulers up to (256*2)-1=511 */
#define MAXMARKS 19	/* depth of stacks -> we can place up to 18 marks (plus the "0" mark means OGR-19) */

unsigned int vecSHIFT(int maxmarks, int maxlength); /* prototype */

unsigned int vecSHIFT(int maxmarks, int maxlength) {

    int depth;                    /* current mark we are placing (corresponds to the D in the PDF) */
    unsigned int count[MAXMARKS]; /* current ruler length (e.g. LENGTH[])*/
    vector unsigned int list[MAXMARKS][NUMWORDS];   /* list bitmap */
    vector unsigned int dist[MAXMARKS][NUMWORDS];   /* dist bitmap */
    vector unsigned int ZEROS = (vector unsigned int)(0);
    vector unsigned int MAGIC = (vector unsigned int)(0x80000000, 0, 0, 0);
    vector unsigned int Vs = (vector unsigned int)(1);
    vector unsigned int Vm = (vector unsigned int)(0xFFFFFFFE);
    unsigned int nodes=0;
            
    
    /* Start at the very beginning (one mark set at position zero) */
    depth = 1;
    count[0] = 0;
    count[1] = 0;

    list[depth][0] = MAGIC;
    list[depth][1] = ZEROS;
    dist[depth][0] = ZEROS;
    dist[depth][1] = ZEROS;
    
    /* search through the search space **** */
    while (1) {
         
        nodes++;
    
        /*if the length of our ruler does not exceeds the maximum length we can proceed */
        if (++count[depth] <= maxlength/* SearchSpaceReduction(3.3) maxlimit[depth]*/) {
        
            /* Check if LIST[D]&DIST[D]=0  ( we can set a new marks ) */
            if ( vec_all_eq(vec_and(list[depth][0],dist[depth][0]), ZEROS) &&
                 vec_all_eq(vec_and(list[depth][1],dist[depth][1]), ZEROS) )
            {
            
                /* set the new DIST[D+1] */
                dist[depth+1][0] = vec_or(list[depth][0] , dist[depth][0]);
                dist[depth+1][1] = vec_or(list[depth][1] , dist[depth][1]);
   
                /* set the new LIST[D] and LIST[D+1] */
                list[depth][1] = vec_sel(vec_sld(list[depth][0],list[depth][1],12),list[depth][1],Vm);
                list[depth][0] = vec_sel(vec_sld(ZEROS,list[depth][0],12),list[depth][0],Vm);
                list[depth][1] = vec_rl(list[depth][1],Vs);
                list[depth][0] = vec_rl(list[depth][0],Vs);
                
                list[depth+1][0] = vec_or(list[depth][0],MAGIC);
                list[depth+1][1] = list[depth][1];
                            
                /* did we find a ruler with the desired number of marks golomb? */
                if (depth == (maxmarks)){
                    int i;
                    printf("FOUND A RULER!!!\n");
                    for(i=0; i<=maxmarks; i++ ) printf("%4d",count[i]);
                    printf("\n");
                }
                /* if we didnt distribute all marks we need to go deeper... */
                else {
                    count[depth+1] = count[depth]; /* pass on our current length */
                    depth++;			   /* one level deeper */

                    continue; /* go to the start of our while(1) loop
                                 the choose[depth] will be incremented by one (e.g. the length of our ruler) */
                }

            }
            /* LIST[D]&DIST[D]!=0 ergo we need to shift the entire LIST[] array one to the right */
            else {
            
                nodes--; /* we only want to have the number of checked valid rulers */
                
                list[depth][1] = vec_sel(vec_sld(list[depth][0],list[depth][1],12),list[depth][1],Vm);
                list[depth][0] = vec_sel(vec_sld(ZEROS,list[depth][0],12),list[depth][0],Vm);
                list[depth][1] = vec_rl(list[depth][1],Vs);
                list[depth][0] = vec_rl(list[depth][0],Vs);
                
            }
            /* Go back to the start of our while(1) loop
               the count[depth] will be incremented by one (e.g. the length of our ruler) */
        }
        /*if the length of our ruler exceeds the maximum length we need to go up one depth */
        else {
           if (--depth == 0) return nodes;/* break; // EXIT if we reached end of search space */
        }
    }

    return nodes; /* never reached */
}

#ifndef AS_MODULE

#include <sys/time.h>
#include <sys/resource.h>

double dtime()
{
struct rusage rusage;
double q;

 getrusage(RUSAGE_SELF,&rusage);

 q = (double)(rusage.ru_utime.tv_sec);
 q = q + (double)(rusage.ru_utime.tv_usec) * 1.0e-06;
	
 return q;
}

int main (int argc, const char * argv[]) {

    double starttime, benchtime;
    unsigned int nodes;
    
    printf("\nvecSHIFT started...\n");
    
    starttime = dtime();
    nodes = vecSHIFT(11,85);
    benchtime = dtime() - starttime;
    
    printf("Nodes per second = %.3f ( %u nodes/ %.3f seconds)\n",nodes/benchtime,nodes,benchtime);    
 
    return 0;
}

#endif