/********************************************************************
 *                                                                  *
 * THIS FILE IS PART OF THE OggVorbis 'TREMOR' CODEC SOURCE CODE.   *
 *                                                                  *
 * USE, DISTRIBUTION AND REPRODUCTION OF THIS LIBRARY SOURCE IS     *
 * GOVERNED BY A BSD-STYLE SOURCE LICENSE INCLUDED WITH THIS SOURCE *
 * IN 'COPYING'. PLEASE READ THESE TERMS BEFORE DISTRIBUTING.       *
 *                                                                  *
 * THE OggVorbis 'TREMOR' SOURCE CODE IS (C) COPYRIGHT 1994-2003    *
 * BY THE Xiph.Org FOUNDATION http://www.xiph.org/                  *
 *                                                                  *
 ********************************************************************

 function: floor backend 1 implementation

 ********************************************************************/

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "ogg/ogg.h"
#include "vorbis/ivorbiscodec.h"
#include "vorbis/codec_internal.h"
#include "codebook.h"
#include "misc.h"

//extern const ogg_int32_t FLOOR_fromdB_LOOKUP[];
extern ogg_int32_t FLOOR_fromdB_LOOKUP[];

#define floor1_rangedB 140 /* floor 1 fixed at -140dB to 0dB range */
#define VIF_POSIT 63

/***********************************************/

static void mergesort(char *index,ogg_uint16_t *vals,ogg_uint16_t n){
  ogg_uint16_t i,j;
  char *temp,*A = index,*B = (char*) alloca(n*sizeof(*B));

  for(i=1;i<n;i<<=1){
    for(j=0;j+i<n;){
      int k1=j;
      int mid=j+i;
      int k2=mid;
      int end=(j+i*2<n?j+i*2:n);
      while(k1<mid && k2<end){
	if(vals[A[k1]]<vals[A[k2]])
	  B[j++]=A[k1++];
	else
	  B[j++]=A[k2++];
      }
      while(k1<mid) B[j++]=A[k1++];
      while(k2<end) B[j++]=A[k2++];
    }
    for(;j<n;j++)B[j]=A[j];
    temp=A;A=B;B=temp;
  }
 
  if(B==index)
	  for(j=0;j<n;j++)B[j]=A[j];
}

int floor1_info_unpack(vorbis_info_floor1*	info,
						vorbis_info*		vi,
						oggpack_buffer*		opb,
						CAkVorbisAllocator&	VorbisAllocator)
{
	codec_setup_info* ci = (codec_setup_info *)&vi->csi;
	int j,k,count = 0,maxclass = -1,rangebits;

	/* read partitions */
	info->partitions		= oggpack_read(opb,5); /* only 0 to 31 legal */
	int AllocSize			= info->partitions*sizeof(*info->partitionclass);
	info->partitionclass	= (char *)VorbisAllocator.Alloc(AllocSize);
	vi->AddAllocatedMemory(AllocSize,"info->partitionclass");

	for(j = 0 ; j < info->partitions ; ++j)
	{
		info->partitionclass[j] = oggpack_read(opb,4); /* only 0 to 15 legal */
		if(maxclass<info->partitionclass[j])
		{
			maxclass=info->partitionclass[j];
		}
	}

	/* read partition classes */
	AllocSize	= (maxclass+1)*sizeof(*info->Class);
	info->Class	= (floor1class *)VorbisAllocator.Alloc(AllocSize);
	vi->AddAllocatedMemory(AllocSize,"info->Class");

	for(j = 0 ; j < maxclass + 1 ; ++j)
	{
		info->Class[j].class_dim	= oggpack_read(opb,3)+1; /* 1 to 8 */
		info->Class[j].class_subs	= oggpack_read(opb,2); /* 0,1,2,3 bits */
		if(oggpack_eop(opb)<0)
		{
			goto err_out;
		}
		if(info->Class[j].class_subs)
		{
			info->Class[j].class_book = oggpack_read(opb,8);
			if(info->Class[j].class_book>=ci->books)
			{
				goto err_out;
			}
		}
		else
		{
			info->Class[j].class_book=0;
		}
		if(info->Class[j].class_book>=ci->books)
		{
			goto err_out;
		}
		for(k=0;k<(1<<info->Class[j].class_subs);k++)
		{
			info->Class[j].class_subbook[k] = oggpack_read(opb,8)-1;
			if(info->Class[j].class_subbook[k]>=ci->books && info->Class[j].class_subbook[k]!=0xff)
			{
				goto err_out;
			}
		}
	}

	/* read the post list */
	info->mult	= oggpack_read(opb,2)+1;     /* only 1,2,3,4 legal now */ 
	rangebits	= oggpack_read(opb,4);

	for(j = 0,k = 0;j < info->partitions ; ++j)
	{
		count+=info->Class[info->partitionclass[j]].class_dim; 
	}

	info->postlist		= (ogg_uint16_t *)VorbisAllocator.Alloc((count+2)*sizeof(*info->postlist));
	info->forward_index	= (char *)VorbisAllocator.Alloc((count+2)*sizeof(*info->forward_index));
	info->loneighbor	= (char *)VorbisAllocator.Alloc(count*sizeof(*info->loneighbor));
	info->hineighbor	= (char *)VorbisAllocator.Alloc(count*sizeof(*info->hineighbor));
	AllocSize			= (count+2)*sizeof(*info->postlist) + (count+2)*sizeof(*info->forward_index) + count*sizeof(*info->loneighbor) + count * sizeof(*info->hineighbor);
	vi->AddAllocatedMemory(AllocSize,"info->pflh");

	count=0;
	for(j=0,k=0;j<info->partitions;j++)
	{
		count += info->Class[info->partitionclass[j]].class_dim; 
		for( ; k < count ; ++k)
		{
			int t = info->postlist[k+2] = oggpack_read(opb,rangebits);
			if(t >= (1<<rangebits))
			{
				goto err_out;
			}
		}
	}

	if(oggpack_eop(opb))
	{
		goto err_out;
	}

	info->postlist[0]	= 0;
	info->postlist[1]	= 1<<rangebits;
	info->posts			= count + 2;

	/* also store a sorted position index */
	for(j=0;j<info->posts;j++)info->forward_index[j]=j;
	mergesort(info->forward_index,info->postlist,info->posts);

	/* discover our neighbors for decode where we don't use fit flags
	(that would push the neighbors outward) */
	for(j=0;j<info->posts-2;j++)
	{
		int lo=0;
		int hi=1;
		int lx=0;
		int hx=info->postlist[1];
		int currentx=info->postlist[j+2];
		for(k=0;k<j+2;k++)
		{
			int x=info->postlist[k];
			if(x>lx && x<currentx)
			{
				lo = k;
				lx = x;
			}
			if(x<hx && x>currentx)
			{
				hi = k;
				hx = x;
			}
		}
		info->loneighbor[j] = lo;
		info->hineighbor[j] = hi;
	}

	return 0;

err_out:

	return -1;
}

static int ilog(unsigned int v){
  int ret=0;
  while(v){
    ret++;
    v>>=1;
  }
  return(ret);
}

static int render_point(int x0,int x1,int y0,int y1,int x){
  y0&=0x7fff; /* mask off flag */
  y1&=0x7fff;
    
  {
    int dy=y1-y0;
    int adx=x1-x0;
    int ady=abs(dy);
    int err=ady*(x-x0);
    
    int off=err/adx;
    if(dy<0)return(y0-off);
    return(y0+off);
  }
}

static void render_line(int x0,int x1,int y0,int y1,ogg_int32_t *d)
{
	int dy		= y1-y0;
	int adx		= x1-x0;
	int ady		= abs(dy);
	int base	= dy/adx;
	int sy		= (dy<0?base-1:base+1);
	int x		= x0;
	int y		= y0;
	int err		= 0;

	ady -= abs(base*adx);

	d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);

	while(++x<x1)
	{
		err = err + ady;
		if(err >= adx)
		{
			err -= adx;
			y += sy;
		}
		else
		{
			y += base;
		}
		
		d[x]= MULT31_SHIFT15(d[x],FLOOR_fromdB_LOOKUP[y]);
	}
}

int floor1_memosize(vorbis_info_floor1 *info)
{
  return info->posts;
}

static int quant_look[4]={256,128,86,64};

ogg_int32_t *floor1_inverse1(	vorbis_dsp_state*	vd,
								vorbis_info_floor1*	info,
								ogg_int32_t*		fit_value)
{
	codec_setup_info* ci = (codec_setup_info *)&vd->vi.csi;
  
  int i,j,k;
  codebook *books=ci->book_param;   
  int quant_q=quant_look[info->mult-1];

  /* unpack wrapped/predicted values from stream */
  if(oggpack_read(&vd->opb,1)==1){
    fit_value[0]=oggpack_read(&vd->opb,ilog(quant_q-1));
    fit_value[1]=oggpack_read(&vd->opb,ilog(quant_q-1));

    /* partition by partition */
    /* partition by partition */
    for(i=0,j=2;i<info->partitions;i++){
      int classv=info->partitionclass[i];
      int cdim=info->Class[classv].class_dim;
      int csubbits=info->Class[classv].class_subs;
      int csub=1<<csubbits;
      int cval=0;

      /* decode the partition's first stage cascade value */
      if(csubbits){
	cval=vorbis_book_decode(books+info->Class[classv].class_book,&vd->opb);

	if(cval==-1)goto eop;
      }

      for(k=0;k<cdim;k++){
	int book=info->Class[classv].class_subbook[cval&(csub-1)];
	cval>>=csubbits;
	if(book!=0xff){
	  if((fit_value[j+k]=vorbis_book_decode(books+book,&vd->opb))==-1)
	    goto eop;
	}else{
	  fit_value[j+k]=0;
	}
      }
      j+=cdim;
    }

    /* unwrap positive values and reconsitute via linear interpolation */
    for(i=2;i<info->posts;i++){
      int predicted=render_point(info->postlist[info->loneighbor[i-2]],
				 info->postlist[info->hineighbor[i-2]],
				 fit_value[info->loneighbor[i-2]],
				 fit_value[info->hineighbor[i-2]],
				 info->postlist[i]);
      int hiroom=quant_q-predicted;
      int loroom=predicted;
      int room=(hiroom<loroom?hiroom:loroom)<<1;
      int val=fit_value[i];

      if(val){
	if(val>=room){
	  if(hiroom>loroom){
	    val = val-loroom;
	  }else{
	  val = -1-(val-hiroom);
	  }
	}else{
	  if(val&1){
	    val= -((val+1)>>1);
	  }else{
	    val>>=1;
	  }
	}

	fit_value[i]=val+predicted;
	fit_value[info->loneighbor[i-2]]&=0x7fff;
	fit_value[info->hineighbor[i-2]]&=0x7fff;

      }else{
	fit_value[i]=predicted|0x8000;
      }
	
    }

    return(fit_value);
  }
 eop:
  return(NULL);
}

int floor1_inverse2(	vorbis_dsp_state*	vd,
						vorbis_info_floor1*	info,
						ogg_int32_t*		fit_value,
						ogg_int32_t*		out)
{
	codec_setup_info* ci = (codec_setup_info *)&vd->vi.csi;
	int                  n=ci->blocksizes[vd->state.W]/2;
	int j;

  if(fit_value)
  {
		/* render the lines */
		int hx	= 0;
		int lx	= 0;
		int ly	= fit_value[0]*info->mult;
		for(j=1;j<info->posts;j++)
		{
			int current	= info->forward_index[j];
			int hy		= fit_value[current]&0x7fff;
			if(hy==fit_value[current])
			{
				hy*=info->mult;
				hx=info->postlist[current];

				render_line(lx,hx,ly,hy,out);

				lx=hx;
				ly=hy;
			}
		}
		for(j=hx;j<n;j++)
		{
			out[j]*=ly; /* be certain */    
		}
		return(1);
	}
	memset(out,0,sizeof(*out)*n);
	return(0);
}
