LXR linux/lib/div64.c

   1/*
   2 * Copyright (C) 2003 Bernardo Innocenti <bernie@develer.com>
   3 *
   4 * Based on former do_div() implementation from asm-parisc/div64.h:
   5 *      Copyright (C) 1999 Hewlett-Packard Co
   6 *      Copyright (C) 1999 David Mosberger-Tang <davidm@hpl.hp.com>
   7 *
   8 *
   9 * Generic C version of 64bit/32bit division and modulo, with
  10 * 64bit result and 32bit remainder.
  11 *
  12 * The fast case for (n>>32 == 0) is handled inline by do_div(). 
  13 *
  14 * Code generated for this function might be very inefficient
  15 * for some CPUs. __div64_32() can be overridden by linking arch-specific
  16 * assembly versions such as arch/ppc/lib/div64.S and arch/sh/lib/div64.S.
  17 */
  18
  19#include <linux/export.h>
  20#include <linux/kernel.h>
  21#include <linux/math64.h>
  22
  23/* Not needed on 64bit architectures */
  24#if BITS_PER_LONG == 32
  25
  26uint32_t __attribute__((weak)) __div64_32(uint64_t *n, uint32_t base)
  27{
  28        uint64_t rem = *n;
  29        uint64_t b = base;
  30        uint64_t res, d = 1;
  31        uint32_t high = rem >> 32;
  32
  33        /* Reduce the thing a bit first */
  34        res = 0;
  35        if (high >= base) {
  36                high /= base;
  37                res = (uint64_t) high << 32;
  38                rem -= (uint64_t) (high*base) << 32;
  39        }
  40
  41        while ((int64_t)b > 0 && b < rem) {
  42                b = b+b;
  43                d = d+d;
  44        }
  45
  46        do {
  47                if (rem >= b) {
  48                        rem -= b;
  49                        res += d;
  50                }
  51                b >>= 1;
  52                d >>= 1;
  53        } while (d);
  54
  55        *n = res;
  56        return rem;
  57}
  58
  59EXPORT_SYMBOL(__div64_32);
  60
  61#ifndef div_s64_rem
  62s64 div_s64_rem(s64 dividend, s32 divisor, s32 *remainder)
  63{
  64        u64 quotient;
  65
  66        if (dividend < 0) {
  67                quotient = div_u64_rem(-dividend, abs(divisor), (u32 *)remainder);
  68                *remainder = -*remainder;
  69                if (divisor > 0)
  70                        quotient = -quotient;
  71        } else {
  72                quotient = div_u64_rem(dividend, abs(divisor), (u32 *)remainder);
  73                if (divisor < 0)
  74                        quotient = -quotient;
  75        }
  76        return quotient;
  77}
  78EXPORT_SYMBOL(div_s64_rem);
  79#endif
  80
  81/**
  82 * div64_u64 - unsigned 64bit divide with 64bit divisor
  83 * @dividend:   64bit dividend
  84 * @divisor:    64bit divisor
  85 *
  86 * This implementation is a modified version of the algorithm proposed
  87 * by the book 'Hacker's Delight'.  The original source and full proof
  88 * can be found here and is available for use without restriction.
  89 *
  90 * 'http://www.hackersdelight.org/HDcode/newCode/divDouble.c.txt'
  91 */
  92#ifndef div64_u64
  93u64 div64_u64(u64 dividend, u64 divisor)
  94{
  95        u32 high = divisor >> 32;
  96        u64 quot;
  97
  98        if (high == 0) {
  99                quot = div_u64(dividend, divisor);
 100        } else {
 101                int n = 1 + fls(high);
 102                quot = div_u64(dividend >> n, divisor >> n);
 103
 104                if (quot != 0)
 105                        quot--;
 106                if ((dividend - quot * divisor) >= divisor)
 107                        quot++;
 108        }
 109
 110        return quot;
 111}
 112EXPORT_SYMBOL(div64_u64);
 113#endif
 114
 115/**
 116 * div64_s64 - signed 64bit divide with 64bit divisor
 117 * @dividend:   64bit dividend
 118 * @divisor:    64bit divisor
 119 */
 120#ifndef div64_s64
 121s64 div64_s64(s64 dividend, s64 divisor)
 122{
 123        s64 quot, t;
 124
 125        quot = div64_u64(abs64(dividend), abs64(divisor));
 126        t = (dividend ^ divisor) >> 63;
 127
 128        return (quot ^ t) - t;
 129}
 130EXPORT_SYMBOL(div64_s64);
 131#endif
 132
 133#endif /* BITS_PER_LONG == 32 */
 134
 135/*
 136 * Iterative div/mod for use when dividend is not expected to be much
 137 * bigger than divisor.
 138 */
 139u32 iter_div_u64_rem(u64 dividend, u32 divisor, u64 *remainder)
 140{
 141        return __iter_div_u64_rem(dividend, divisor, remainder);
 142}
 143EXPORT_SYMBOL(iter_div_u64_rem);
 144