/* Micro-C Switch Code generation Part */
/* $Id$ */

#define EXTERN extern
#include "mc.h"
#include "mc-code.h"
#include "mc-codegen.h"

#if CASE_CODE

extern void genswitch(int cslist,int cslabel,int dlabel);

/*
  value label pair
      cslist = list3(value,next,label)  label==0 means skip
  continuous cslist
      chunks:  list4(cslist,next,delta,list3(count,min,max))
  mergeable chunks count list
      merge:   list4(continuous number of chunk,next,delta,case_count);
  index list
      index:   list4(label,next,max,min);
 */

#define chunk_max(chunks) caddr(cadddr(chunks))
#define chunk_min(chunks) cadr(cadddr(chunks))
#define index_max(index)  caddr(index)
#define index_min(index)  cadddr(index)
#define index_label(index)  car(index)

#define CASE_TABLE_COUNT 3
#define CASE_INDEX_COUNT 3


/*
   group continous case value
 */

static int
make_chunk(int cslist)
{
    int delta,delta1,list,p,count;
    // cslist is already sorted
    delta = 0;
    list = list4(cslist,0,1,list3(0,car(cslist) /* min */,0)); 
    count=1;
    for(p=0;cadr(cslist);cslist = cadr(cslist),count++) {
        // compute new delta
	delta1 = car(cadr(cslist))-car(cslist);
        // empty case
	if (!caddr(cslist)) count--;
	if (delta==0) {
            // 2nd element
	    caddr(list) = delta = delta1;
	    if (p) cadr(p)=0;  // terminate previous chunk
	} else if (delta1!=delta) {
	    // not contiguous, start new list
	    caddr(cadddr(list)) = car(cslist);      // max
	    car(cadddr(list)) = count; count=0;
            delta = 0;
	    list = list4(cadr(cslist),list,1,list3(0,0,0));
	    cadr(cadddr(list)) = car(cadr(cslist)); // min
            // prepare terminate point for next turn
	    p=cslist;
	}
    }
    if (p) cadr(p)=0;  // terminate previous chunk
    car(cadddr(list)) = count;
    caddr(cadddr(list)) = car(cslist);   // max
    return list;
}

#define CASE_MERGE_RATE 70

static int gcd(int i,int j)
{
    int k;
    if (i<j) { k=i; i=j; j=k;}
    for(;;) {
	if ((k=i%j)==0) return j;
	i = j; j = k;
    }
}

/*
    check two chunks are mergeable or not.
 */

static int
merge_chunk_p(int *delta,int max,int min,int *count,int delta1,int count1) 
{
    int range = max-min;
    int g;
    // compute possible merge delta
    g = gcd(*delta,delta1);
    g = gcd(g,range);
    range /= g;
    *count = count1 = count1+*count;
    *delta = g;
#if 1
    if (count1*128>(range*128*CASE_MERGE_RATE/100)) {
	printf("# min %d, max %d, count %d, delta %d, rate %g t=%d\n",
	    min,max,count1,g,
		 ((double)count1)*100.0/range,
	       count1*128>(range*128*CASE_MERGE_RATE/100)
	);
    }
#endif
    //    count/((max-min)/delta) > 0.8
    return count1*128>(range*128*CASE_MERGE_RATE/100);
}


static int
merge_chunk(int chunks)
{
    int list = chunks;
    int tail,last,max,min,i;
    int count,c_count,p,widest,delta=1;
    int merge = 0;
    while(cadr(list)) {
	p = cadddr(list);
	c_count = count = car(p); max=caddr(p);
	widest = 1; last = list;
	delta = caddr(list);
        // check possible merge against the end of the chunks
	for(i=1,tail=cadr(list);cadr(tail); tail=cadr(tail),i++) {
	    p = cadddr(tail);
	    min = cadr(p);
	    if (merge_chunk_p(&delta,max,min,&count,caddr(tail),car(p))) {
                // It is mergeable.
		widest = i+1; last = tail; c_count=count;
	    }
	}
	merge = list4(widest,merge,delta,c_count);
        // skip merged chunks
	list = cadr(last);
    }
    // last one can remain.
    if (list) merge = list4(1,merge,caddr(list),car(cadddr(list)));
    return merge;
}

static int
table_jump(int count,int delta,int cslist)
{
    int list;
    for(;count-->0;cslist=cadr(cslist)) {
	list = car(cslist);
	printf("# table cases delta=%d count=%d min=%d max=%d\n",
		caddr(cslist),car(cadddr(cslist)),
				cadr(cadddr(cslist)),caddr(cadddr(cslist))
		);
	for(;list; list=cadr(list)) {
	    if (caddr(list))
		cmpdimm(car(list),csvalue1,caddr(list),0);
	}
    }
    return cslist;
}

static int
cascade_compare(int count,int cslist)
{
    int list;
    for(;count-->0;cslist=cadr(cslist)) {
	list = car(cslist);
	printf("# cascade cases delta=%d count=%d min=%d max=%d\n",
		caddr(cslist),car(cadddr(cslist)),
				cadr(cadddr(cslist)),caddr(cadddr(cslist))
		);
	for(;list; list=cadr(list)) {
	    if (caddr(list))
		cmpdimm(car(list),csvalue1,caddr(list),0);
                //      value     register  label    mode
	}
    }
    return cslist;
}


/*
     generate index jmp
 */

static void
switch_index_jmp(int index,int label)
{
    int value = index_min(index);
    cmpdimm(value,csvalue1,label,LT);
    //      value     register  label    mode
}

/*
     generate leaf index branch
 */

static int
switch_make_index_leaf(int count,int index,int level)
{
    control=1;
    printf("# index leaf count=%d level=%d\n",count,level);
    for(;count-- !=0 && cadr(index);index=cadr(index)) {
	switch_index_jmp( cadr(index), index_label(index) );
    }
    if (!cadr(index)) {
	// don't check max boundary
	jmp(index_label(index));
	return 0;
    }
    if (count!= -1) error(-1);
    if (control&&dlabel) jmp(dlabel);
    return index;
}

/*
     generate index switch branch (no table).
     if necessary generate higher index.
 */

static void
switch_make_index(int index0,int count,int cslabel,int level)
{
    int index=0;
    int icount=0;
    int l,min,max;
    control=1;
    while (index0 && count > CASE_INDEX_COUNT) {
	l = backdef();
	min = index_min(index0);
	index0=switch_make_index_leaf(CASE_INDEX_COUNT,index0,level);
	max = index_min(index0)-1;
	index = list4(l,index,max,min);
	count-=CASE_INDEX_COUNT;
	icount++;
    }
    if (index) {
	switch_make_index(reverse0(index),icount,cslabel,level+1);
    } else {
	fwddef(cslabel);
	switch_make_index_leaf(-1,index0,level);
    }
    if (control&&dlabel) jmp(dlabel);
}

/*
     generate leaf switch branch or table jump
 */

static int
switch_leaf(int count,int merge,int cslist)
{
    control=1;
    for(;count-- !=0 && merge;merge=cadr(merge)) {
	printf("# merge count %d delta %d c_count %d\n",
		car(merge),caddr(merge),cadddr(merge));
	if (cadddr(merge)>CASE_TABLE_COUNT)
	    cslist = table_jump(car(merge),caddr(merge),cslist);
	else
	    cslist = cascade_compare(car(merge),cslist);
    }
    if (control&&dlabel) jmp(dlabel);
    return cslist;
}

/*
    make index if necessary or
    generate case branch or table jump 
 */

static void
switch_index(int merge,int chunks,int cslabel,int dlabel,int gmax)
{
    int m,l,max,min;
    int chnkcnt = 0;
    int icount = 0;
    int count = 0;
    int index = 0;
    for(m=merge;m;m=cadr(m)) {
	if (!index && !cadr(m)) break;  // no index for single chunk
        chnkcnt++;
	count += cadddr(m);
	if (count > CASE_INDEX_COUNT || (index && !cadr(m))) {
	    icount++;
	    min = car(car(chunks));
	    l = backdef();
	    chunks= switch_leaf(chnkcnt,merge,chunks);
	    max = chunks?car(car(chunks)):gmax;
            index = list4(l,index,max,min);
	    merge = cadr(m); count = 0; chnkcnt = 0;
	}
    }
    if (index) {
	index = reverse0(index);
        // check lower bound
	// switch_index_jmp(index,dlabel?dlabel:blabel); 
        //   nonsense because no control here.
	switch_make_index(index,icount,cslabel,0);
    } else {
	fwddef(cslabel);
	switch_leaf(-1,merge,chunks);
    }
    if (control&&dlabel) jmp(dlabel);
}

/*  generate switch table, index, cascading branch */


void
genswitch(int cslist,int cslabel,int dlabel)
{
    int chunks,merge,gmax;
    int i,j;
    control=1;
#if 0
    for(i=cslist;i;i=cadr(i)) {
	printf("# case %d L_%d\n",car(i),caddr(i));
    }
#endif
    /* find stepwise chunks */
    chunks=make_chunk(cslist);
#if 1
    j = 0;
    for(i=cslist;i;i=cadr(i)) {
        j++;
    }
#endif
    /* possible merge of loose stepwise chunks */
    merge = merge_chunk(chunks);
#if 0
    //  chunks: list3(widest,next,delta);
    printf("# chunks %d = sum ",j);
    j = 0;
    for(i=merge;i;i=cadr(i)) {
	printf(" %d/%d",car(i),caddr(i));
	j+=car(i);
    }
    printf(" sum = %d\n",j);
#endif
    /* make index branch or table jump */
    gmax = chunk_max(chunks);
    chunks = reverse0(chunks);
    switch_index(merge,chunks,cslabel,dlabel,gmax);
}

#endif



/* end */