/* 64 bit math for the few ops that actually need it, such as granpos
   tracking */

typedef struct {
  ogg_int32_t hi;
  ogg_uint32_t lo;
} ogg_int64_t;

static ogg_int64_t add64_64(ogg_int64_t a,ogg_int64_t b){
  if(a.lo+b.lo<a.lo)a.hi++;
  a.lo+=b.lo;
  a.hi+=b.hi;
  return a;
} 

static ogg_int32_t ladd64_64(ogg_int64_t a,ogg_int64_t b){
  return (ogg_int32_t)(add64_64(a,b).lo);
} 

static ogg_int64_t set64_int(ogg_int32_t b){
  ogg_int64_t a;
  a.lo=b;
  if(b<0)
    a.hi=-1;
  else
    a.hi=0;
  return a;
} 

static ogg_int64_t add64_int(ogg_int64_t a,ogg_int32_t b){
  ogg_int64_t temp=set64_int(b);
  return add64_64(a,temp);
} 

static ogg_int64_t neg64(ogg_int64_t a){
  a.lo=~a.lo;
  a.hi=~a.hi;
  return add64_int(a,1);
} 


static ogg_int16_t cmp64_64(ogg_int64_t a,ogg_int64_t b){
  if(a.hi<b.hi)return -1;
  if(a.hi>b.hi)return  1;
  if(a.lo<b.lo)return -1;
  if(a.lo>b.lo)return  1;
  return 0;
}

static ogg_int16_t cmp64_64off(ogg_int64_t a,ogg_int32_t offa,
		       ogg_int64_t b,ogg_int32_t offb){
  a=add64_int(a,offa);
  b=add64_int(b,offb);
  return cmp64_64(a,b);
}

static ogg_int16_t cmp64_int(ogg_int64_t a,ogg_int32_t b){
  ogg_int64_t bb=set64_int(b);
  return cmp64_64(a,bb);
}

static ogg_int64_t asr64(ogg_int64_t a, ogg_int16_t b){
  if(b>=32){
    a.lo=a.hi>>(b-32);
    a.hi=a.hi>>31;
  }else{
    a.lo=(a.lo>>b)|(a.hi<<(32-b));
    a.hi=(a.hi>>b);
  }
  return a;
}

static ogg_int64_t asl64(ogg_int64_t a, ogg_int16_t b){
  if(b>=32){
    a.hi=a.lo<<(b-32);
    a.lo=0;
  }else{
    a.hi=(a.hi<<b)|(a.lo>>(32-b));
    a.lo=(a.lo<<b);
  }
  return a;
}

/* simple binary long division using subtractions */
static ogg_int64_t div64_int(ogg_int64_t a, ogg_int32_t b){
  ogg_int16_t sign=0,bit=0;
  ogg_int64_t ret={0,0};

  if(!b)return ret;

  if(a.hi<0){
    sign=1;
    a=neg64(a);
  }
  if(b<0){
    sign= !sign;
    b= -b;
  }

  /* normalize b */
  while(!b&0x40000000L){
    b<<=1;
    bit++;
  }

  /* hi section */
  for(;bit>=0;bit--){
    if(a.hi>=b){
      ret.hi|=1<<bit;
      a.hi-=b;
    }
    a.hi<<=1;
    a.hi|=a.lo>>31;
    a.lo<<=1;
  }

  /* lo section */
  for(bit=31;bit>=0;bit--){
    if(a.hi>=b){
      ret.lo|=1<<bit;
      a.hi-=b;
    }
    a.hi<<=1;
    a.hi|=a.lo>>31;
    a.lo<<=1;
  }

  if(sign) return neg64(ret);
  return(ret);
}

/* long multiplication, much like ogg_int32_t division; 32 adds */
static ogg_int64_t mul64_int(ogg_int64_t a, ogg_int32_t b){
  ogg_int16_t sign=0,bit;
  ogg_int64_t ret={0,0};

  if(!b)return ret;

  if(a.hi<0){
    sign=1;
    a=neg64(a);
  }
  if(b<0){
    sign= !sign;
    b= -b;
  }
  
  for(bit=0;bit<31;bit++){
    if(b&1)ret=add64_64(ret,a);
    b>>=1;
    a=asl64(a,1);
  }

  if(sign) return neg64(ret);
  return(ret);
}