← Back to branch summary

~vojtech-horky/helenos/numa

« back to all changes in this revision

Viewing changes to uspace/lib/softint/generic/division.c

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
uspace/lib/softint/generic/division.c
 
1
/*
 
2
 * Copyright (c) 2006 Josef Cejka
 
3
 * All rights reserved.
 
4
 *
 
5
 * Redistribution and use in source and binary forms, with or without
 
6
 * modification, are permitted provided that the following conditions
 
7
 * are met:
 
8
 *
 
9
 * - Redistributions of source code must retain the above copyright
 
10
 *   notice, this list of conditions and the following disclaimer.
 
11
 * - Redistributions in binary form must reproduce the above copyright
 
12
 *   notice, this list of conditions and the following disclaimer in the
 
13
 *   documentation and/or other materials provided with the distribution.
 
14
 * - The name of the author may not be used to endorse or promote products
 
15
 *   derived from this software without specific prior written permission.
 
16
 *
 
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
27
 */
 
28
 
 
29
/** @addtogroup softint
 
30
 * @{
 
31
 */ 
 
32
/**
 
33
 * @file
 
34
 * SW implementation of 32 and 64 bit division and modulo.
 
35
 */
 
36
 
 
37
#include <division.h>
 
38
 
 
39
#define ABSVAL(x) ( (x) > 0 ? (x) : -(x))
 
40
#define SGN(x) ( (x) >= 0 ? 1 : 0 )
 
41
                                      
 
42
static unsigned int divandmod32(unsigned int a, unsigned int b, unsigned int *remainder)
 
43
{
 
44
        unsigned int result;
 
45
        int steps = sizeof(unsigned int) * 8; 
 
46
        
 
47
        *remainder = 0;
 
48
        result = 0;
 
49
        
 
50
        if (b == 0) {
 
51
                /* FIXME: division by zero */
 
52
                return 0;
 
53
        }
 
54
        
 
55
        if ( a < b) {
 
56
                *remainder = a;
 
57
                return 0;
 
58
        }
 
59
 
 
60
        for ( ; steps > 0; steps--) {
 
61
                /* shift one bit to remainder */
 
62
                *remainder = ( (*remainder) << 1) | (( a >> 31) & 0x1);
 
63
                result <<= 1;
 
64
                
 
65
                if (*remainder >= b) {
 
66
                                *remainder -= b;
 
67
                                result |= 0x1;
 
68
                }
 
69
                a <<= 1;
 
70
        }
 
71
 
 
72
        return result;
 
73
}
 
74
 
 
75
 
 
76
static unsigned long long divandmod64(unsigned long long a, unsigned long long b, unsigned long long *remainder)
 
77
{
 
78
        unsigned long long result;
 
79
        int steps = sizeof(unsigned long long) * 8; 
 
80
        
 
81
        *remainder = 0;
 
82
        result = 0;
 
83
        
 
84
        if (b == 0) {
 
85
                /* FIXME: division by zero */
 
86
                return 0;
 
87
        }
 
88
        
 
89
        if ( a < b) {
 
90
                *remainder = a;
 
91
                return 0;
 
92
        }
 
93
 
 
94
        for ( ; steps > 0; steps--) {
 
95
                /* shift one bit to remainder */
 
96
                *remainder = ( (*remainder) << 1) | ((a >> 63) & 0x1);
 
97
                result <<= 1;
 
98
                
 
99
                if (*remainder >= b) {
 
100
                                *remainder -= b;
 
101
                                result |= 0x1;
 
102
                }
 
103
                a <<= 1;
 
104
        }
 
105
 
 
106
        return result;
 
107
}
 
108
 
 
109
/* 32bit integer division */
 
110
int __divsi3(int a, int b) 
 
111
{
 
112
        unsigned int rem;
 
113
        int result;
 
114
        
 
115
        result = (int)divandmod32(ABSVAL(a), ABSVAL(b), &rem);
 
116
 
 
117
        if ( SGN(a) == SGN(b)) return result;
 
118
        return -result;
 
119
}
 
120
 
 
121
/* 64bit integer division */
 
122
long long __divdi3(long long a, long long b) 
 
123
{
 
124
        unsigned long long rem;
 
125
        long long result;
 
126
        
 
127
        result = (long long)divandmod64(ABSVAL(a), ABSVAL(b), &rem);
 
128
 
 
129
        if ( SGN(a) == SGN(b)) return result;
 
130
        return -result;
 
131
}
 
132
 
 
133
/* 32bit unsigned integer division */
 
134
unsigned int __udivsi3(unsigned int a, unsigned int b)
 
135
{
 
136
        unsigned int rem;
 
137
        return divandmod32(a, b, &rem);
 
138
}
 
139
 
 
140
/* 64bit unsigned integer division */
 
141
unsigned long long __udivdi3(unsigned long long a, unsigned long long b)
 
142
{
 
143
        unsigned long long  rem;
 
144
        return divandmod64(a, b, &rem);
 
145
}
 
146
 
 
147
/* 32bit remainder of the signed division */
 
148
int __modsi3(int a, int b)
 
149
{
 
150
        unsigned int rem;
 
151
        divandmod32(a, b, &rem);
 
152
        
 
153
        /* if divident is negative, remainder must be too */
 
154
        if (!(SGN(a))) {
 
155
                return -((int)rem);
 
156
        }
 
157
        
 
158
        return (int)rem;
 
159
}
 
160
 
 
161
/* 64bit remainder of the signed division */
 
162
long long __moddi3(long long a,long  long b)
 
163
{
 
164
        unsigned long long rem;
 
165
        divandmod64(a, b, &rem);
 
166
        
 
167
        /* if divident is negative, remainder must be too */
 
168
        if (!(SGN(a))) {
 
169
                return -((long long)rem);
 
170
        }
 
171
        
 
172
        return (long long)rem;
 
173
}
 
174
 
 
175
/* 32bit remainder of the unsigned division */
 
176
unsigned int __umodsi3(unsigned int a, unsigned int b)
 
177
{
 
178
        unsigned int rem;
 
179
        divandmod32(a, b, &rem);
 
180
        return rem;
 
181
}
 
182
 
 
183
/* 64bit remainder of the unsigned division */
 
184
unsigned long long __umoddi3(unsigned long long a, unsigned long long b)
 
185
{
 
186
        unsigned long long rem;
 
187
        divandmod64(a, b, &rem);
 
188
        return rem;
 
189
}
 
190
 
 
191
unsigned long long __udivmoddi3(unsigned long long a, unsigned long long b, unsigned long long *c)
 
192
{
 
193
        return divandmod64(a, b, c);
 
194
}
 
195
 
 
196
/** @}
 
197
 */