← Back to branch summary

~ubuntu-branches/ubuntu/precise/linux-lowlatency/precise

« back to all changes in this revision

Viewing changes to arch/s390/lib/div64.c

  • Committer: Package Import Robot
  • Author(s): Alessio Igor Bogani
  • Date: 2011-10-26 11:13:05 UTC
  • Revision ID: package-import@ubuntu.com-20111026111305-tz023xykf0i6eosh
Tags: upstream-3.2.0
Import upstream version 3.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
arch/s390/lib/div64.c
 
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
 */
 
19
static 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
 */
 
76
uint32_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
 
 
129
uint32_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 */