/*-
 * This file is dual licensed under the MIT and the University of Illinois
 * Open Source Licenses.
 *
 *-
 * University of Illinois/NCSA
 * Open Source License
 *
 * Copyright (c) 2009-2014 by the contributors listed below
 *
 * All rights reserved.
 *
 * Developed by:
 *
 * LLVM Team
 *
 * University of Illinois at Urbana-Champaign
 *
 * http://llvm.org
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal with the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * * Redistributions of source code must retain the above copyright notice,
 *   this list of conditions and the following disclaimers.
 *
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimers in the
 *   documentation and/or other materials provided with the distribution.
 *
 * * Neither the names of the LLVM Team, University of Illinois at
 *   Urbana-Champaign, nor the names of its contributors may be used to
 *   endorse or promote products derived from this Software without specific
 *   prior written permission.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * WITH THE SOFTWARE.
 *
 *-
 * Copyright (c) 2009-2014 by the contributors listed below
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 *
 * -
 * List of contributors:
 *
 * Craig van Vliet <cvanvliet@auroraux.org>
 * Edward O'Callaghan <eocallaghan@auroraux.org>
 * Howard Hinnant <hhinnant@apple.com>
 * Matt Thomas <matt@NetBSD.org>
 * Joerg Sonnenberger <joerg@NetBSD.org>
 */

#include <machine/limits.h>
#include <machine/stdint.h>

typedef union
{
	_uint128_t all;
	struct {
		unsigned long low;
		unsigned long high;
	} s;
} utwords;

/* Effects: if rem != 0, *rem = a % b
 * Returns: a / b
 */

/* Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide */

static _uint128_t
__udivmodti4(_uint128_t a, _uint128_t b, _uint128_t *rem)
{
	const unsigned n_udword_bits = sizeof(unsigned long) * CHAR_BIT;
	const unsigned n_utword_bits = sizeof(_uint128_t) * CHAR_BIT;
	utwords n, d, q, r;
	unsigned sr;

	n.all = a;
	d.all = b;

	/* special cases, X is unknown, K != 0 */
	if (n.s.high == 0) {
		if (d.s.high == 0) {
			/* 0 X
			 * ---
			 * 0 X
			 */
			if (rem)
				*rem = n.s.low % d.s.low;
			return n.s.low / d.s.low;
		}
		/* 0 X
		 * ---
		 * K X
		 */
		if (rem)
			*rem = n.s.low;
		return 0;
	}
	/* n.s.high != 0 */
	if (d.s.low == 0) {
		if (d.s.high == 0) {
			/* K X
			 * ---
			 * 0 0
			 */
			if (rem)
				*rem = n.s.high % d.s.low;
			return n.s.high / d.s.low;
		}
		/* d.s.high != 0 */
		if (n.s.low == 0) {
			/* K 0
			 * ---
			 * K 0
			 */
			if (rem) {
				r.s.high = n.s.high % d.s.high;
				r.s.low = 0;
				*rem = r.all;
			}
			return n.s.high / d.s.high;
		}
		/* K K
		 * ---
		 * K 0
		 */
		if ((d.s.high & (d.s.high - 1)) == 0) { /* if d is a power of 2 */
			if (rem) {
				r.s.low = n.s.low;
				r.s.high = n.s.high & (d.s.high - 1);
				*rem = r.all;
			}
			return n.s.high >> __builtin_ctzl(d.s.high);
		}
		/* K K
		 * ---
		 * K 0
		 */
		sr = __builtin_clzl(d.s.high) - __builtin_clzl(n.s.high);
		/* 0 <= sr <= n_udword_bits - 2 or sr large */
		if (sr > n_udword_bits - 2) {
			if (rem)
				*rem = n.all;
			return 0;
		}
		++sr;
		/* 1 <= sr <= n_udword_bits - 1 */
		/* q.all = n.all << (n_utword_bits - sr); */
		q.s.low = 0;
		q.s.high = n.s.low << (n_udword_bits - sr);
		/* r.all = n.all >> sr; */
		r.s.high = n.s.high >> sr;
		r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
	} else {  /* d.s.low != 0 */
		if (d.s.high == 0) {
			/* K X
			 * ---
			 * 0 K
			 */
			if ((d.s.low & (d.s.low - 1)) == 0) { /* if d is a power of 2 */
				if (rem)
					*rem = n.s.low & (d.s.low - 1);
				if (d.s.low == 1)
					return n.all;
				sr = __builtin_ctzl(d.s.low);
				q.s.high = n.s.high >> sr;
				q.s.low = (n.s.high << (n_udword_bits - sr)) |
				    (n.s.low >> sr);
				return q.all;
			}
			/* K X
			 * ---
			 * 0 K
			 */
			sr = 1 + n_udword_bits + __builtin_clzl(d.s.low) -
			    __builtin_clzl(n.s.high);
			/* 2 <= sr <= n_utword_bits - 1
			 * q.all = n.all << (n_utword_bits - sr);
			 * r.all = n.all >> sr;
			 * if (sr == n_udword_bits)
			 * {
			 *     q.s.low = 0;
			 *     q.s.high = n.s.low;
			 *     r.s.high = 0;
			 *     r.s.low = n.s.high;
			 * }
			 * else if (sr < n_udword_bits)  // 2 <= sr <= n_udword_bits - 1
			 * {
			 *     q.s.low = 0;
			 *     q.s.high = n.s.low << (n_udword_bits - sr);
			 *     r.s.high = n.s.high >> sr;
			 *     r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
			 * }
			 * else              // n_udword_bits + 1 <= sr <= n_utword_bits - 1
			 * {
			 *     q.s.low = n.s.low << (n_utword_bits - sr);
			 *     q.s.high = (n.s.high << (n_utword_bits - sr)) |
			 *              (n.s.low >> (sr - n_udword_bits));
			 *     r.s.high = 0;
			 *     r.s.low = n.s.high >> (sr - n_udword_bits);
			 * }
			 */
			q.s.low =  (n.s.low << (n_utword_bits - sr)) &
			    ((long)(int)(n_udword_bits - sr) >> (n_udword_bits-1));
			q.s.high = ((n.s.low << ( n_udword_bits - sr)) &
			    ((long)(int)(sr - n_udword_bits - 1) >> (n_udword_bits-1))) |
			    (((n.s.high << (n_utword_bits - sr)) |
				(n.s.low >> (sr - n_udword_bits))) &
				((long)(int)(n_udword_bits - sr) >> (n_udword_bits-1)));
			r.s.high = (n.s.high >> sr) &
			    ((long)(int)(sr - n_udword_bits) >> (n_udword_bits-1));
			r.s.low =  ((n.s.high >> (sr - n_udword_bits)) &
			    ((long)(int)(n_udword_bits - sr - 1) >> (n_udword_bits-1))) |
			    (((n.s.high << (n_udword_bits - sr)) |
				(n.s.low >> sr)) &
				((long)(int)(sr - n_udword_bits) >> (n_udword_bits-1)));
		} else {
			/* K X
			 * ---
			 * K K
			 */
			sr = __builtin_clzl(d.s.high) - __builtin_clzl(n.s.high);
			/*0 <= sr <= n_udword_bits - 1 or sr large */
			if (sr > n_udword_bits - 1) {
				if (rem)
					*rem = n.all;
				return 0;
			}
			++sr;
			/* 1 <= sr <= n_udword_bits */
			/* q.all = n.all << (n_utword_bits - sr); */
			q.s.low = 0;
			q.s.high = n.s.low << (n_udword_bits - sr);
			/* r.all = n.all >> sr;
			 * if (sr < n_udword_bits)
			 * {
			 *     r.s.high = n.s.high >> sr;
			 *     r.s.low = (n.s.high << (n_udword_bits - sr)) | (n.s.low >> sr);
			 * }
			 * else
			 * {
			 *     r.s.high = 0;
			 *     r.s.low = n.s.high;
			 * }
			 */
			r.s.high = (n.s.high >> sr) &
			    ((long)(int)(sr - n_udword_bits) >> (n_udword_bits-1));
			r.s.low = (n.s.high << (n_udword_bits - sr)) |
			    ((n.s.low >> sr) &
				((long)(int)(sr - n_udword_bits) >> (n_udword_bits-1)));
		}
	}
	/* Not a special case
	 * q and r are initialized with:
	 * q.all = n.all << (n_utword_bits - sr);
	 * r.all = n.all >> sr;
	 * 1 <= sr <= n_utword_bits - 1
	 */
	unsigned carry = 0;
	for (; sr > 0; --sr) {
		/* r:q = ((r:q)  << 1) | carry */
		r.s.high = (r.s.high << 1) | (r.s.low  >> (n_udword_bits - 1));
		r.s.low  = (r.s.low  << 1) | (q.s.high >> (n_udword_bits - 1));
		q.s.high = (q.s.high << 1) | (q.s.low  >> (n_udword_bits - 1));
		q.s.low  = (q.s.low  << 1) | carry;
		/* carry = 0;
		 * if (r.all >= d.all)
		 * {
		 *     r.all -= d.all;
		 *      carry = 1;
		 * }
		 */
		const _int128_t s =
		    (_int128_t)(d.all - r.all - 1) >> (n_utword_bits - 1);
		carry = s & 1;
		r.all -= d.all & s;
	}
	q.all = (q.all << 1) | carry;
	if (rem)
		*rem = r.all;
	return q.all;
}

_uint128_t __udivti3(_uint128_t a, _uint128_t b);

_uint128_t
__udivti3(_uint128_t a, _uint128_t b)
{
	return __udivmodti4(a, b, 0);
}