/* Micro-C Switch Code generation Part */

/************************************************************************
** Copyright (C) 2006 Shinji Kono
** 連絡先： 琉球大学情報工学科 河野 真治  
** （E-Mail Address: kono@ie.u-ryukyu.ac.jp）
**
**    このソースのいかなる複写，改変，修正も許諾します。ただし、
**    その際には、誰が貢献したを示すこの部分を残すこと。
**    再配布や雑誌の付録などの問い合わせも必要ありません。
**    営利利用も上記に反しない範囲で許可します。
**    バイナリの配布の際にはversion messageを保存することを条件とします。
**    このプログラムについては特に何の保証もしない、悪しからず。
**
**    Everyone is permitted to do anything on this program 
**    including copying, modifying, improving,
**    as long as you don't try to pretend that you wrote it.
**    i.e., the above copyright notice has to appear in all copies.  
**    Binary distribution requires original version messages.
**    You don't have to ask before copying, redistribution or publishing.
**    THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE.
***********************************************************************/

#include <stdio.h>
#include "mc.h"
#include "mc-parse.h"
#include "mc-codegen.h"
#include "mc-code.h"

#if CASE_CODE

extern void genswitch(int cslist,int cslabel);

/*
  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);



  A list of value label pair is generated in do_case, in sorted list.

  The list is separated in continous cslists which has a same
  delta in make_chunk(int cslist).

  merge_chunk(int chunks) tries to findout possible merge of continous
  cslist. If merge_chunk_p() accepts reasonably densed switch talbe,
  the cslists are merged.

  switch_index() makes hierachical indexed branches, using switch_leaf().
  switch_leaf(). switch_leaf() generates table jump if it is suitable.
  Otherwise it generates multi-stage cascading jump. siwtch_make_index()
  generates multi-stage index in a recursive way.


 */

#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 10
#define CASE_INDEX_COUNT CASE_TABLE_COUNT  // have to be equal

static int djmp;

static void
check_djmp()
{
    if (control && dlabel && djmp)
	jmp(dlabel);
    djmp = 0;
}

/*
   group continuous case value
 */

static int
make_chunk(int cslist)
{
    register 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 50

static int gcd(int i0,int j0)
{
    register int k,i=i0,j=j0;
    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;
    int c = 128*CASE_MERGE_RATE/100;
    // compute possible merge delta
    g = gcd(*delta,delta1);
    g = gcd(g,range);
    range /= g;
    *count = count1 = count1+*count;
    *delta = g;
#if 0
    if (count1*128>(range*128*CASE_MERGE_RATE/100)) {
	if (lsrc) 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*c);
}

static void
free_chunks(int chunks)
{
    int p;
    while(chunks) {
	p = car(chunks);
	chunks = cadr(chunks); // free_glist3 will destroy cadr
	free_glist3(p);
    }
}

static int
merge_chunk(int chunks)
{
    register int list = chunks;
    register int tail,last,max,min,i;
    register int c_count,p,widest;
    register int merge = 0;
    int count,delta=1;

    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;
}

/*
    Generates series of compare immideate. It is suitable for
    small amount of jump and random value.
 */
static int
cascade_compare(int count,int cslist)
{
    int list;
    for(;count-->0;cslist=cadr(cslist)) {
	list = car(cslist);
#ifdef DEBUG_MERGE
	if (lsrc) printf("## cascade cases delta=%d count=%d min=%d max=%d\n",
		caddr(cslist),car(cadddr(cslist)),
				cadr(cadddr(cslist)),caddr(cadddr(cslist))
		);
#endif
	for(;list; list=cadr(list)) {
	    if (caddr(list))
		cmpdimm(car(list),csvalue1,caddr(list),0);
                //      value     register  label    mode
	}
    }
    // have to be fall thru
    return cslist;
}

/*
    Make table jump code, suitable for fixed delta and large size
    table.
 */
static int
table_jump(int count,int delta,int chunks)
{
    int list,i;
    int l,max=0,min;
    if (!code_table_jump_p(delta))
	return cascade_compare(count,chunks);

    min=cadr(cadddr(chunks));
    // find max
    for(i=0,list=chunks;i<count;list=cadr(list),i++) {
	max=caddr(cadddr(list));
    }

    if (lsrc) printf("## table count %d delta %d max %d min %d\n",
	    count,delta,max,min);

    l = fwdlabel();
    if (car(csvalue1)!=REGISTER) error(-1);
    code_table_jump(l,cadr(csvalue1),delta,max,min,dlabel);
    control=0;
    code_table_open(l);
    i = min;
    for(;count-->0;chunks=cadr(chunks)) {
	list = car(chunks);
	for(;list; list=cadr(list)) {
	    if (caddr(list)) {
		for(;i<car(list);i+=delta) {
		    code_table_value(dlabel,l);
		}
		code_table_value(caddr(list),l);
		i+=delta;
	    }
	}
    }
    code_table_close();
    return chunks;
}


/*
     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;
    if (lsrc) 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);
    djmp = 1;
    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 gmax,int level)
{
    int index=0;
    int icount=0;
    int l,min,max;
    control=1;
    if (count <= CASE_INDEX_COUNT) {
	check_djmp();
	fwddef(cslabel);
	switch_make_index_leaf(-1,index0,level);
    } else {
	// too large index, make hihger index
	while (index0) {
	    check_djmp();
	    l = backdef();
	    min = index_min(index0);
	    index0=switch_make_index_leaf(CASE_INDEX_COUNT,index0,level);
	    if (index0) {
		max = index_min(index0)-1;
	    } else {
		max = gmax;
	    }
	    index = list4(l,index,max,min);
	    count-=CASE_INDEX_COUNT;
	    icount++;
	}
	// process higher indexes in a recursive way
	switch_make_index(reverse0(index),icount,cslabel,gmax,level+1);
    }
}

/*
     generate leaf switch branch or table jump
 */

static int
switch_leaf(int count,int merge,int chunks)
{
    control=1;
    for(;count-- !=0 && merge;merge=cadr(merge)) {
#ifdef DEBUG_MERGE
	if (lsrc) printf("## merge count %d delta %d c_count %d\n",
		car(merge),caddr(merge),cadddr(merge));
#endif
	if (cadddr(merge)>CASE_TABLE_COUNT) {
	    chunks = table_jump(car(merge),caddr(merge),chunks);
	} else {
	    chunks = cascade_compare(car(merge),chunks);
	}
    }
    // table_jump has no fall thru, but cascade_compare does.
    if (control) djmp = 1;
    return chunks;
}

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

static void
switch_index(int merge,int chunks,int cslabel,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))) {
	    // too large for single stage cascading or
	    // we already have indexies and this is the last one.
	    icount++;
	    min = car(car(chunks));
	    check_djmp();
	    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) {
	// yes we have indexes
	index = reverse0(index);
        // check lower bound
	// switch_index_jmp(index,dlabel?dlabel:blabel); 
        //   nonsense because no control here.
	switch_make_index(index,icount,cslabel,gmax,0);
    } else {
	fwddef(cslabel);
	switch_leaf(-1,merge,chunks);
    }
    if (control&&dlabel) djmp = 1;
}

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


void
genswitch(int cslist,int cslabel)
{
    int chunks,merge,gmax;
#if 0
    int i;
    int j;
    for(i=cslist;i;i=cadr(i)) {
	if (lsrc) printf("## case %d L_%d\n",car(i),caddr(i));
    }
#endif
    control=1;
    if (chk) return;
    /* find stepwise chunks */
    chunks=make_chunk(cslist);
#if 0
    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);
    if (lsrc) printf("## chunks %d = sum ",j);
    j = 0;
    for(i=merge;i;i=cadr(i)) {
	if (lsrc) printf(" %d/%d",car(i),caddr(i));
	j+=car(i);
    }
    if (lsrc) printf(" sum = %d\n",j);
#endif
    /* make index branch or table jump */
    gmax = chunk_max(chunks);
    chunks = reverse0(chunks);
    if (!dlabel) dlabel = blabel;
    djmp = 0;
    switch_index(merge,chunks,cslabel,gmax);
    free_chunks(chunks);
    if (dlabel!=blabel)
	check_djmp();
}

#endif



/* end */