linux/arch/s390/lib/div64.c
<<
>>
Prefs
   1/*
   2 *  arch/s390/lib/div64.c
   3 *
   4 *  __div64_32 implementation for 31 bit.
   5 *
   6 *    Copyright (C) IBM Corp. 2006
   7 *    Author(s): Martin Schwidefsky (schwidefsky@de.ibm.com),
   8 */
   9
  10#include <linux/types.h>
  11#include <linux/module.h>
  12
  13#ifdef CONFIG_MARCH_G5
  14
  15/*
  16 * Function to divide an unsigned 64 bit integer by an unsigned
  17 * 31 bit integer using signed 64/32 bit division.
  18 */
  19static uint32_t __div64_31(uint64_t *n, uint32_t base)
  20{
  21        register uint32_t reg2 asm("2");
  22        register uint32_t reg3 asm("3");
  23        uint32_t *words = (uint32_t *) n;
  24        uint32_t tmp;
  25
  26        /* Special case base==1, remainder = 0, quotient = n */
  27        if (base == 1)
  28                return 0;
  29        /*
  30         * Special case base==0 will cause a fixed point divide exception
  31         * on the dr instruction and may not happen anyway. For the
  32         * following calculation we can assume base > 1. The first
  33         * signed 64 / 32 bit division with an upper half of 0 will
  34         * give the correct upper half of the 64 bit quotient.
  35         */
  36        reg2 = 0UL;
  37        reg3 = words[0];
  38        asm volatile(
  39                "       dr      %0,%2\n"
  40                : "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" );
  41        words[0] = reg3;
  42        reg3 = words[1];
  43        /*
  44         * To get the lower half of the 64 bit quotient and the 32 bit
  45         * remainder we have to use a little trick. Since we only have
  46         * a signed division the quotient can get too big. To avoid this
  47         * the 64 bit dividend is halved, then the signed division will
  48         * work. Afterwards the quotient and the remainder are doubled.
  49         * If the last bit of the dividend has been one the remainder
  50         * is increased by one then checked against the base. If the
  51         * remainder has overflown subtract base and increase the
  52         * quotient. Simple, no ?
  53         */
  54        asm volatile(
  55                "       nr      %2,%1\n"
  56                "       srdl    %0,1\n"
  57                "       dr      %0,%3\n"
  58                "       alr     %0,%0\n"
  59                "       alr     %1,%1\n"
  60                "       alr     %0,%2\n"
  61                "       clr     %0,%3\n"
  62                "       jl      0f\n"
  63                "       slr     %0,%3\n"
  64                "       ahi     %1,1\n"
  65                "0:\n"
  66                : "+d" (reg2), "+d" (reg3), "=d" (tmp)
  67                : "d" (base), "2" (1UL) : "cc" );
  68        words[1] = reg3;
  69        return reg2;
  70}
  71
  72/*
  73 * Function to divide an unsigned 64 bit integer by an unsigned
  74 * 32 bit integer using the unsigned 64/31 bit division.
  75 */
  76uint32_t __div64_32(uint64_t *n, uint32_t base)
  77{
  78        uint32_t r;
  79
  80        /*
  81         * If the most significant bit of base is set, divide n by
  82         * (base/2). That allows to use 64/31 bit division and gives a
  83         * good approximation of the result: n = (base/2)*q + r. The
  84         * result needs to be corrected with two simple transformations.
  85         * If base is already < 2^31-1 __div64_31 can be used directly.
  86         */
  87        r = __div64_31(n, ((signed) base < 0) ? (base/2) : base);
  88        if ((signed) base < 0) {
  89                uint64_t q = *n;
  90                /*
  91                 * First transformation:
  92                 * n = (base/2)*q + r
  93                 *   = ((base/2)*2)*(q/2) + ((q&1) ? (base/2) : 0) + r
  94                 * Since r < (base/2), r + (base/2) < base.
  95                 * With q1 = (q/2) and r1 = r + ((q&1) ? (base/2) : 0)
  96                 * n = ((base/2)*2)*q1 + r1 with r1 < base.
  97                 */
  98                if (q & 1)
  99                        r += base/2;
 100                q >>= 1;
 101                /*
 102                 * Second transformation. ((base/2)*2) could have lost the
 103                 * last bit.
 104                 * n = ((base/2)*2)*q1 + r1
 105                 *   = base*q1 - ((base&1) ? q1 : 0) + r1
 106                 */
 107                if (base & 1) {
 108                        int64_t rx = r - q;
 109                        /*
 110                         * base is >= 2^31. The worst case for the while
 111                         * loop is n=2^64-1 base=2^31+1. That gives a
 112                         * maximum for q=(2^64-1)/2^31 = 0x1ffffffff. Since
 113                         * base >= 2^31 the loop is finished after a maximum
 114                         * of three iterations.
 115                         */
 116                        while (rx < 0) {
 117                                rx += base;
 118                                q--;
 119                        }
 120                        r = rx;
 121                }
 122                *n = q;
 123        }
 124        return r;
 125}
 126
 127#else /* MARCH_G5 */
 128
 129uint32_t __div64_32(uint64_t *n, uint32_t base)
 130{
 131        register uint32_t reg2 asm("2");
 132        register uint32_t reg3 asm("3");
 133        uint32_t *words = (uint32_t *) n;
 134
 135        reg2 = 0UL;
 136        reg3 = words[0];
 137        asm volatile(
 138                "       dlr     %0,%2\n"
 139                : "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" );
 140        words[0] = reg3;
 141        reg3 = words[1];
 142        asm volatile(
 143                "       dlr     %0,%2\n"
 144                : "+d" (reg2), "+d" (reg3) : "d" (base) : "cc" );
 145        words[1] = reg3;
 146        return reg2;
 147}
 148
 149#endif /* MARCH_G5 */
 150