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