#include <stdlib.h>
#include <stdint.h>
#include <sys/types.h>

#include "lib.h"

static uint32_t mask32[] = {
  0x00000001, 0x00000002, 0x00000004, 0x00000008,
  0x00000010, 0x00000020, 0x00000040, 0x00000080,
  0x00000100, 0x00000200, 0x00000400, 0x00000800,
  0x00001000, 0x00002000, 0x00004000, 0x00008000,
  0x00010000, 0x00020000, 0x00040000, 0x00080000,
  0x00100000, 0x00200000, 0x00400000, 0x00800000,
  0x01000000, 0x02000000, 0x04000000, 0x08000000,
  0x10000000, 0x20000000, 0x40000000, 0x80000000,
};

int32_t __ashlsi3(int32_t val, int s) /* 32bit left shift arithmetic */
{
  return __lshlsi3(val, s);
}

uint32_t __lshlsi3(uint32_t val, int s) /* 32bit left shift logical */
{
  uint32_t v = 0;
  int i;

  s &= (32 - 1);

  for (i = 0; i < 32; i++) {
    if (i >= s) {
      if (val & mask32[i - s])
	v |= mask32[i];
    }
  }

  return v;
}

int32_t __ashrsi3(int32_t val, int s) /* 32bit right shift arithmetic */
{
  uint32_t v = 0;
  int i;

  s &= (32 - 1);

  for (i = 0; i < 32; i++) {
    if (i + s < 32) {
      if (val & mask32[i + s])
	v |= mask32[i];
    } else {
      if (val & mask32[31])
	v |= mask32[i];
    }
  }

  return v;
}

uint32_t __lshrsi3(uint32_t val, int s) /* 32bit right shift logical */
{
  uint32_t v = 0;
  int i;

  s &= (32 - 1);

  for (i = 0; i < 32; i++) {
    if (i + s < 32) {
      if (val & mask32[i + s])
	v |= mask32[i];
    }
  }

  return v;
}

union v64 {
#if BYTE_ORDER == BIG_ENDIAN
  struct {
    int32_t h;
    int32_t l;
  } s32;
  struct {
    uint32_t h;
    uint32_t l;
  } u32;
#elif BYTE_ORDER == LITTLE_ENDIAN
  struct {
    int32_t l;
    int32_t h;
  } s32;
  struct {
    uint32_t l;
    uint32_t h;
  } u32;
#else
#error unknown endian
#endif
  int64_t s64;
  uint64_t u64;
};

int64_t __ashldi3(int64_t val, int s) /* 64bit left shift arithmetic */
{
  return __lshldi3(val, s);
}

uint64_t __lshldi3(uint64_t val, int s) /* 64bit left shift logical */
{
  union v64 v;

  s &= (64 - 1);
  v.s64 = val;

  if (s < 32) {
    v.u32.h <<= s;
    v.u32.h  |= (v.u32.l >> (32 - s));
    v.u32.l <<= s;
  } else {
    v.u32.h   = (s < 64) ? (v.u32.l << (s - 32)) : 0;
    v.u32.l   = 0;
  }

  return v.u64;
}

int64_t __ashrdi3(int64_t val, int s) /* 64bit right shift arithmetic */
{
  union v64 v;

  s &= (64 - 1);
  v.s64 = val;

  if (s < 32) {
    v.u32.l >>= s;
    v.u32.l  |= (v.u32.h << (32 - s));
    v.s32.h >>= s;
  } else {
    v.u32.l   = (v.s32.h >> (s - 32));
    v.s32.h >>= 31;
  }

  return v.s64;
}

uint64_t __lshrdi3(uint64_t val, int s) /* 64bit right shift logical */
{
  union v64 v;

  s &= (64 - 1);
  v.s64 = val;

  if (s < 32) {
    v.u32.l >>= s;
    v.u32.l  |= (v.u32.h << (32 - s));
    v.u32.h >>= s;
  } else {
    v.u32.l   = (s < 64) ? (v.u32.h >> (s - 32)) : 0;
    v.u32.h   = 0;
  }

  return v.u64;
}

static uint32_t _div_u32(uint32_t val, uint32_t div, int isrem)
{
  uint32_t div2n, quot, rem;
  unsigned int n;

  if (div == 0)
    abort();

  div2n = div;
  for (n = 1; ((div2n < val) && ((int32_t)div2n > 0)); n <<= 1)
    div2n <<= 1;

  rem = val;
  for (quot = 0; rem >= div; quot += n) {
    for (; div2n > rem; n >>= 1)
      div2n >>= 1;
    rem -= div2n;
  }

  return isrem ? rem : quot;
}

static uint64_t _div_u64(uint64_t val, uint64_t div, int isrem)
{
  uint64_t div2n, quot, rem;
  unsigned int n;

  if (div == 0)
    abort();

  div2n = div;
  for (n = 1; ((div2n < val) && ((int64_t)div2n > 0)); n <<= 1)
    div2n = __lshldi3(div2n, 1);

  rem = val;
  for (quot = 0; rem >= div; quot += n) {
    for (; div2n > rem; n >>= 1)
      div2n = __lshrdi3(div2n, 1);
    rem -= div2n;
  }

  return isrem ? rem : quot;
}

int32_t __divsi3(int32_t val, int32_t div)
{
  int32_t r;
  int minus = 0;

  if (val < 0) {
    val = -val;
    minus = !minus;
  }
  if (div < 0) {
    div = -div;
    minus = !minus;
  }

  r = _div_u32(val, div, 0);

  return minus ? -r : r;
}

int32_t __modsi3(int32_t val, int32_t div)
{
  int32_t r;
  int minus = 0;

  if (val < 0) {
    val = -val;
    minus = !minus;
  }
  if (div < 0) {
    div = -div;
  }

  r = _div_u32(val, div, 1);

  return minus ? -r : r;
}

uint32_t __udivsi3(uint32_t val, uint32_t div)
{
  return _div_u32(val, div, 0);
}

uint32_t __umodsi3(uint32_t val, uint32_t div)
{
  return _div_u32(val, div, 1);
}

int64_t __divdi3(int64_t val, int64_t div)
{
  int64_t r;
  int minus = 0;

  if (val < 0) {
    val = -val;
    minus = !minus;
  }
  if (div < 0) {
    div = -div;
    minus = !minus;
  }

  r = _div_u64(val, div, 0);

  return minus ? -r : r;
}

int64_t __moddi3(int64_t val, int64_t div)
{
  int64_t r;
  int minus = 0;

  if (val < 0) {
    val = -val;
    minus = !minus;
  }
  if (div < 0) {
    div = -div;
  }

  r = _div_u64(val, div, 1);

  return minus ? -r : r;
}

uint64_t __udivdi3(uint64_t val, uint64_t div)
{
  return _div_u64(val, div, 0);
}

uint64_t __umoddi3(uint64_t val, uint64_t div)
{
  return _div_u64(val, div, 1);
}

static uint32_t _mul_u32(uint32_t val, uint32_t mul)
{
  uint32_t val2n, r;
  unsigned int n;

  val2n = val;
  for (n = 1; ((n < mul) && ((int32_t)val2n > 0)); n <<= 1)
    val2n <<= 1;

  for (r = 0; mul > 0; mul -= n) {
    for (; n > mul; n >>= 1)
      val2n >>= 1;
    r += val2n;
  }

  return r;
}

static uint64_t _mul_u64(uint64_t val, uint64_t mul)
{
  uint64_t val2n, r;
  unsigned int n;

  val2n = val;
  for (n = 1; ((n < mul) && ((int64_t)val2n > 0)); n <<= 1)
    val2n <<= __lshldi3(val2n, 1);

  for (r = 0; mul > 0; mul -= n) {
    for (; n > mul; n >>= 1)
      val2n = __lshrdi3(val2n, 1);
    r += val2n;
  }

  return r;
}

int32_t __mulsi3(int32_t val,  int32_t mul)
{
  int32_t r;
  int minus = 0;

  if (val < 0) {
    val = -val;
    minus = !minus;
  }
  if (mul < 0) {
    mul = -mul;
    minus = !minus;
  }

  r = _mul_u32(val, mul);

  return minus ? -r : r;
}

uint32_t __umulsi3(uint32_t val, uint32_t mul)
{
  return _mul_u32(val, mul);
}

int64_t __muldi3(int64_t val, int64_t mul)
{
  int64_t r;
  int minus = 0;

  if (val < 0) {
    val = -val;
    minus = !minus;
  }
  if (mul < 0) {
    mul = -mul;
    minus = !minus;
  }

  r = _mul_u64(val, mul);

  return minus ? -r : r;
}

uint64_t __umuldi3(uint64_t val, uint64_t mul)
{
  return _mul_u64(val, mul);
}
