Subversion Repositories HelenOS

Rev

Rev 2479 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
991 cejka 1
/*
2071 jermar 2
 * Copyright (c) 2006 Josef Cejka
991 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
 
1740 jermar 29
/** @addtogroup softint
1653 cejka 30
 * @{
31
 */
32
/**
33
 * @file
34
 * SW implementation of 32 and 64 bit division and modulo.
35
 */
36
 
991 cejka 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
 
1653 cejka 196
/** @}
197
 */