<jittershader name="binarysearch">
	<param name="stride" type="float" default="131072" />
	<param name="pbufinfo" type="float" default="512" />
	<param name="sortpbufinfo" type="float" default="512" />
	<language name="cg" version="1.0">
		<bind param="stride" program="fp" />
		<bind param="pbufinfo" program="fp" />
		<bind param="sortpbufinfo" program="fp" />
		<program name="passthru" type="vertex" source="sh.passthru.vp.cg" entry="passthru" />
		<program name="fp" type="fragment" entry="BinarySearch">
<![CDATA[
#define W 512.0
#define H 512.0

#define N W*H
#define LOGN 18

float2 convert1dto2d( float coord1d, float width ){
  float2 coord2d;
  coord2d.y = coord1d/width;
  coord2d.x = floor(frac(coord2d.y) * width);
  coord2d.y = floor(coord2d.y);
  return coord2d;
}

float Search( float curpos, float elem, float stride, uniform samplerRECT data, float texw ){
  float2 adr2d = convert1dto2d( curpos, texw );
  float val = f1texRECT( data, adr2d );
  float dir = (elem <= val) ? -1.0 : 1.0;
  return dir*stride + curpos;
}

float SearchFinal( float curpos, float elem, float stride, uniform samplerRECT data, float texw ){
  float2 adr2d = convert1dto2d( curpos, texw );
  float val = f1texRECT( data, adr2d );
  float dir = (elem <= val) ? 0.0 : 1.0;
  return dir*stride + curpos;
}


float BinarySearch( varying float2 elem2d : WPOS,
                    uniform float stride,
                    uniform float pbufinfo,
                    uniform float sortbufinfo,
                    uniform samplerRECT sortlist : texunit0) : COLOR
{
  elem2d = floor(elem2d);
  float elem1d = elem2d.y*pbufinfo + elem2d.x;
  float curpos = stride;

  //loop over logn - 1 search passes -- hardcoded logn
  for(int i=0; i<LOGN-1; i++){
    stride = floor(stride*0.5);
    curpos = Search( curpos, elem1d, stride, sortlist, sortbufinfo );
  }

  //last two passes are special
  curpos = Search(curpos, elem1d, 1.0, sortlist, sortbufinfo ); //logn-th pass
  curpos = SearchFinal(curpos, elem1d, 1.0, sortlist, sortbufinfo ); // last pass

  return curpos;
}
]]>		
		</program>
	</language>
</jittershader>
