← Back to branch summary

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

« back to all changes in this revision

Viewing changes to arch/arm/include/asm/div64.h

  • 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/arm/include/asm/div64.h
 
1
#ifndef __ASM_ARM_DIV64
 
2
#define __ASM_ARM_DIV64
 
3
 
 
4
#include <asm/system.h>
 
5
#include <linux/types.h>
 
6
 
 
7
/*
 
8
 * The semantics of do_div() are:
 
9
 *
 
10
 * uint32_t do_div(uint64_t *n, uint32_t base)
 
11
 * {
 
12
 *      uint32_t remainder = *n % base;
 
13
 *      *n = *n / base;
 
14
 *      return remainder;
 
15
 * }
 
16
 *
 
17
 * In other words, a 64-bit dividend with a 32-bit divisor producing
 
18
 * a 64-bit result and a 32-bit remainder.  To accomplish this optimally
 
19
 * we call a special __do_div64 helper with completely non standard
 
20
 * calling convention for arguments and results (beware).
 
21
 */
 
22
 
 
23
#ifdef __ARMEB__
 
24
#define __xh "r0"
 
25
#define __xl "r1"
 
26
#else
 
27
#define __xl "r0"
 
28
#define __xh "r1"
 
29
#endif
 
30
 
 
31
#define __do_div_asm(n, base)                                   \
 
32
({                                                              \
 
33
        register unsigned int __base      asm("r4") = base;     \
 
34
        register unsigned long long __n   asm("r0") = n;        \
 
35
        register unsigned long long __res asm("r2");            \
 
36
        register unsigned int __rem       asm(__xh);            \
 
37
        asm(    __asmeq("%0", __xh)                             \
 
38
                __asmeq("%1", "r2")                             \
 
39
                __asmeq("%2", "r0")                             \
 
40
                __asmeq("%3", "r4")                             \
 
41
                "bl     __do_div64"                             \
 
42
                : "=r" (__rem), "=r" (__res)                    \
 
43
                : "r" (__n), "r" (__base)                       \
 
44
                : "ip", "lr", "cc");                            \
 
45
        n = __res;                                              \
 
46
        __rem;                                                  \
 
47
})
 
48
 
 
49
#if __GNUC__ < 4
 
50
 
 
51
/*
 
52
 * gcc versions earlier than 4.0 are simply too problematic for the
 
53
 * optimized implementation below. First there is gcc PR 15089 that
 
54
 * tend to trig on more complex constructs, spurious .global __udivsi3
 
55
 * are inserted even if none of those symbols are referenced in the
 
56
 * generated code, and those gcc versions are not able to do constant
 
57
 * propagation on long long values anyway.
 
58
 */
 
59
#define do_div(n, base) __do_div_asm(n, base)
 
60
 
 
61
#elif __GNUC__ >= 4
 
62
 
 
63
#include <asm/bug.h>
 
64
 
 
65
/*
 
66
 * If the divisor happens to be constant, we determine the appropriate
 
67
 * inverse at compile time to turn the division into a few inline
 
68
 * multiplications instead which is much faster. And yet only if compiling
 
69
 * for ARMv4 or higher (we need umull/umlal) and if the gcc version is
 
70
 * sufficiently recent to perform proper long long constant propagation.
 
71
 * (It is unfortunate that gcc doesn't perform all this internally.)
 
72
 */
 
73
#define do_div(n, base)                                                 \
 
74
({                                                                      \
 
75
        unsigned int __r, __b = (base);                                 \
 
76
        if (!__builtin_constant_p(__b) || __b == 0 ||                   \
 
77
            (__LINUX_ARM_ARCH__ < 4 && (__b & (__b - 1)) != 0)) {       \
 
78
                /* non-constant divisor (or zero): slow path */         \
 
79
                __r = __do_div_asm(n, __b);                             \
 
80
        } else if ((__b & (__b - 1)) == 0) {                            \
 
81
                /* Trivial: __b is constant and a power of 2 */         \
 
82
                /* gcc does the right thing with this code.  */         \
 
83
                __r = n;                                                \
 
84
                __r &= (__b - 1);                                       \
 
85
                n /= __b;                                               \
 
86
        } else {                                                        \
 
87
                /* Multiply by inverse of __b: n/b = n*(p/b)/p       */ \
 
88
                /* We rely on the fact that most of this code gets   */ \
 
89
                /* optimized away at compile time due to constant    */ \
 
90
                /* propagation and only a couple inline assembly     */ \
 
91
                /* instructions should remain. Better avoid any      */ \
 
92
                /* code construct that might prevent that.           */ \
 
93
                unsigned long long __res, __x, __t, __m, __n = n;       \
 
94
                unsigned int __c, __p, __z = 0;                         \
 
95
                /* preserve low part of n for reminder computation */   \
 
96
                __r = __n;                                              \
 
97
                /* determine number of bits to represent __b */         \
 
98
                __p = 1 << __div64_fls(__b);                            \
 
99
                /* compute __m = ((__p << 64) + __b - 1) / __b */       \
 
100
                __m = (~0ULL / __b) * __p;                              \
 
101
                __m += (((~0ULL % __b + 1) * __p) + __b - 1) / __b;     \
 
102
                /* compute __res = __m*(~0ULL/__b*__b-1)/(__p << 64) */ \
 
103
                __x = ~0ULL / __b * __b - 1;                            \
 
104
                __res = (__m & 0xffffffff) * (__x & 0xffffffff);        \
 
105
                __res >>= 32;                                           \
 
106
                __res += (__m & 0xffffffff) * (__x >> 32);              \
 
107
                __t = __res;                                            \
 
108
                __res += (__x & 0xffffffff) * (__m >> 32);              \
 
109
                __t = (__res < __t) ? (1ULL << 32) : 0;                 \
 
110
                __res = (__res >> 32) + __t;                            \
 
111
                __res += (__m >> 32) * (__x >> 32);                     \
 
112
                __res /= __p;                                           \
 
113
                /* Now sanitize and optimize what we've got. */         \
 
114
                if (~0ULL % (__b / (__b & -__b)) == 0) {                \
 
115
                        /* those cases can be simplified with: */       \
 
116
                        __n /= (__b & -__b);                            \
 
117
                        __m = ~0ULL / (__b / (__b & -__b));             \
 
118
                        __p = 1;                                        \
 
119
                        __c = 1;                                        \
 
120
                } else if (__res != __x / __b) {                        \
 
121
                        /* We can't get away without a correction    */ \
 
122
                        /* to compensate for bit truncation errors.  */ \
 
123
                        /* To avoid it we'd need an additional bit   */ \
 
124
                        /* to represent __m which would overflow it. */ \
 
125
                        /* Instead we do m=p/b and n/b=(n*m+m)/p.    */ \
 
126
                        __c = 1;                                        \
 
127
                        /* Compute __m = (__p << 64) / __b */           \
 
128
                        __m = (~0ULL / __b) * __p;                      \
 
129
                        __m += ((~0ULL % __b + 1) * __p) / __b;         \
 
130
                } else {                                                \
 
131
                        /* Reduce __m/__p, and try to clear bit 31   */ \
 
132
                        /* of __m when possible otherwise that'll    */ \
 
133
                        /* need extra overflow handling later.       */ \
 
134
                        unsigned int __bits = -(__m & -__m);            \
 
135
                        __bits |= __m >> 32;                            \
 
136
                        __bits = (~__bits) << 1;                        \
 
137
                        /* If __bits == 0 then setting bit 31 is     */ \
 
138
                        /* unavoidable.  Simply apply the maximum    */ \
 
139
                        /* possible reduction in that case.          */ \
 
140
                        /* Otherwise the MSB of __bits indicates the */ \
 
141
                        /* best reduction we should apply.           */ \
 
142
                        if (!__bits) {                                  \
 
143
                                __p /= (__m & -__m);                    \
 
144
                                __m /= (__m & -__m);                    \
 
145
                        } else {                                        \
 
146
                                __p >>= __div64_fls(__bits);            \
 
147
                                __m >>= __div64_fls(__bits);            \
 
148
                        }                                               \
 
149
                        /* No correction needed. */                     \
 
150
                        __c = 0;                                        \
 
151
                }                                                       \
 
152
                /* Now we have a combination of 2 conditions:        */ \
 
153
                /* 1) whether or not we need a correction (__c), and */ \
 
154
                /* 2) whether or not there might be an overflow in   */ \
 
155
                /*    the cross product (__m & ((1<<63) | (1<<31)))  */ \
 
156
                /* Select the best insn combination to perform the   */ \
 
157
                /* actual __m * __n / (__p << 64) operation.         */ \
 
158
                if (!__c) {                                             \
 
159
                        asm (   "umull  %Q0, %R0, %1, %Q2\n\t"          \
 
160
                                "mov    %Q0, #0"                        \
 
161
                                : "=&r" (__res)                         \
 
162
                                : "r" (__m), "r" (__n)                  \
 
163
                                : "cc" );                               \
 
164
                } else if (!(__m & ((1ULL << 63) | (1ULL << 31)))) {    \
 
165
                        __res = __m;                                    \
 
166
                        asm (   "umlal  %Q0, %R0, %Q1, %Q2\n\t"         \
 
167
                                "mov    %Q0, #0"                        \
 
168
                                : "+&r" (__res)                         \
 
169
                                : "r" (__m), "r" (__n)                  \
 
170
                                : "cc" );                               \
 
171
                } else {                                                \
 
172
                        asm (   "umull  %Q0, %R0, %Q1, %Q2\n\t"         \
 
173
                                "cmn    %Q0, %Q1\n\t"                   \
 
174
                                "adcs   %R0, %R0, %R1\n\t"              \
 
175
                                "adc    %Q0, %3, #0"                    \
 
176
                                : "=&r" (__res)                         \
 
177
                                : "r" (__m), "r" (__n), "r" (__z)       \
 
178
                                : "cc" );                               \
 
179
                }                                                       \
 
180
                if (!(__m & ((1ULL << 63) | (1ULL << 31)))) {           \
 
181
                        asm (   "umlal  %R0, %Q0, %R1, %Q2\n\t"         \
 
182
                                "umlal  %R0, %Q0, %Q1, %R2\n\t"         \
 
183
                                "mov    %R0, #0\n\t"                    \
 
184
                                "umlal  %Q0, %R0, %R1, %R2"             \
 
185
                                : "+&r" (__res)                         \
 
186
                                : "r" (__m), "r" (__n)                  \
 
187
                                : "cc" );                               \
 
188
                } else {                                                \
 
189
                        asm (   "umlal  %R0, %Q0, %R2, %Q3\n\t"         \
 
190
                                "umlal  %R0, %1, %Q2, %R3\n\t"          \
 
191
                                "mov    %R0, #0\n\t"                    \
 
192
                                "adds   %Q0, %1, %Q0\n\t"               \
 
193
                                "adc    %R0, %R0, #0\n\t"               \
 
194
                                "umlal  %Q0, %R0, %R2, %R3"             \
 
195
                                : "+&r" (__res), "+&r" (__z)            \
 
196
                                : "r" (__m), "r" (__n)                  \
 
197
                                : "cc" );                               \
 
198
                }                                                       \
 
199
                __res /= __p;                                           \
 
200
                /* The reminder can be computed with 32-bit regs     */ \
 
201
                /* only, and gcc is good at that.                    */ \
 
202
                {                                                       \
 
203
                        unsigned int __res0 = __res;                    \
 
204
                        unsigned int __b0 = __b;                        \
 
205
                        __r -= __res0 * __b0;                           \
 
206
                }                                                       \
 
207
                /* BUG_ON(__r >= __b || __res * __b + __r != n); */     \
 
208
                n = __res;                                              \
 
209
        }                                                               \
 
210
        __r;                                                            \
 
211
})
 
212
 
 
213
/* our own fls implementation to make sure constant propagation is fine */
 
214
#define __div64_fls(bits)                                               \
 
215
({                                                                      \
 
216
        unsigned int __left = (bits), __nr = 0;                         \
 
217
        if (__left & 0xffff0000) __nr += 16, __left >>= 16;             \
 
218
        if (__left & 0x0000ff00) __nr +=  8, __left >>=  8;             \
 
219
        if (__left & 0x000000f0) __nr +=  4, __left >>=  4;             \
 
220
        if (__left & 0x0000000c) __nr +=  2, __left >>=  2;             \
 
221
        if (__left & 0x00000002) __nr +=  1;                            \
 
222
        __nr;                                                           \
 
223
})
 
224
 
 
225
#endif
 
226
 
 
227
#endif