Subversion Repositories HelenOS

Rev

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

Rev Author Line No. Line
991 cejka 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
 
1653 cejka 29
/** @addtogroup softint SoftInt
30
 * @brief   Software implementation of basic arithmetic operations.
31
 * @{
32
 */
33
/**
34
 * @file
35
 * SW implementation of 32 and 64 bit division and modulo.
36
 */
37
 
991 cejka 38
#include <division.h>
39
 
40
#define ABSVAL(x) ( (x) > 0 ? (x) : -(x))
41
#define SGN(x) ( (x) >= 0 ? 1 : 0 )
42
 
43
static unsigned int divandmod32(unsigned int a, unsigned int b, unsigned int *remainder)
44
{
45
    unsigned int result;
46
    int steps = sizeof(unsigned int) * 8;
47
 
48
    *remainder = 0;
49
    result = 0;
50
 
51
    if (b == 0) {
52
        /* FIXME: division by zero */
53
        return 0;
54
    }
55
 
56
    if ( a < b) {
57
        *remainder = a;
58
        return 0;
59
    }
60
 
61
    for ( ; steps > 0; steps--) {
62
        /* shift one bit to remainder */
63
        *remainder = ( (*remainder) << 1) | (( a >> 31) & 0x1);
64
        result <<= 1;
65
 
66
        if (*remainder >= b) {
67
                *remainder -= b;
68
                result |= 0x1;
69
        }
70
        a <<= 1;
71
    }
72
 
73
    return result;
74
}
75
 
76
 
77
static unsigned long long divandmod64(unsigned long long a, unsigned long long b, unsigned long long *remainder)
78
{
79
    unsigned long long result;
80
    int steps = sizeof(unsigned long long) * 8;
81
 
82
    *remainder = 0;
83
    result = 0;
84
 
85
    if (b == 0) {
86
        /* FIXME: division by zero */
87
        return 0;
88
    }
89
 
90
    if ( a < b) {
91
        *remainder = a;
92
        return 0;
93
    }
94
 
95
    for ( ; steps > 0; steps--) {
96
        /* shift one bit to remainder */
97
        *remainder = ( (*remainder) << 1) | ((a >> 63) & 0x1);
98
        result <<= 1;
99
 
100
        if (*remainder >= b) {
101
                *remainder -= b;
102
                result |= 0x1;
103
        }
104
        a <<= 1;
105
    }
106
 
107
    return result;
108
}
109
 
110
/* 32bit integer division */
111
int __divsi3(int a, int b)
112
{
113
    unsigned int rem;
114
    int result;
115
 
116
    result = (int)divandmod32(ABSVAL(a), ABSVAL(b), &rem);
117
 
118
    if ( SGN(a) == SGN(b)) return result;
119
    return -result;
120
}
121
 
122
/* 64bit integer division */
123
long long __divdi3(long long a, long long b)
124
{
125
    unsigned long long rem;
126
    long long result;
127
 
128
    result = (long long)divandmod64(ABSVAL(a), ABSVAL(b), &rem);
129
 
130
    if ( SGN(a) == SGN(b)) return result;
131
    return -result;
132
}
133
 
134
/* 32bit unsigned integer division */
135
unsigned int __udivsi3(unsigned int a, unsigned int b)
136
{
137
    unsigned int rem;
138
    return divandmod32(a, b, &rem);
139
}
140
 
141
/* 64bit unsigned integer division */
142
unsigned long long __udivdi3(unsigned long long a, unsigned long long b)
143
{
144
    unsigned long long  rem;
145
    return divandmod64(a, b, &rem);
146
}
147
 
148
/* 32bit remainder of the signed division */
149
int __modsi3(int a, int b)
150
{
151
    unsigned int rem;
152
    divandmod32(a, b, &rem);
153
 
154
    /* if divident is negative, remainder must be too */
155
    if (!(SGN(a))) {
156
        return -((int)rem);
157
    }
158
 
159
    return (int)rem;
160
}
161
 
162
/* 64bit remainder of the signed division */
163
long long __moddi3(long long a,long  long b)
164
{
165
    unsigned long long rem;
166
    divandmod64(a, b, &rem);
167
 
168
    /* if divident is negative, remainder must be too */
169
    if (!(SGN(a))) {
170
        return -((long long)rem);
171
    }
172
 
173
    return (long long)rem;
174
}
175
 
176
/* 32bit remainder of the unsigned division */
177
unsigned int __umodsi3(unsigned int a, unsigned int b)
178
{
179
    unsigned int rem;
180
    divandmod32(a, b, &rem);
181
    return rem;
182
}
183
 
184
/* 64bit remainder of the unsigned division */
185
unsigned long long __umoddi3(unsigned long long a, unsigned long long b)
186
{
187
    unsigned long long rem;
188
    divandmod64(a, b, &rem);
189
    return rem;
190
}
191
 
192
unsigned long long __udivmoddi3(unsigned long long a, unsigned long long b, unsigned long long *c)
193
{
194
    return divandmod64(a, b, c);
195
}
196
 
1653 cejka 197
/** @}
198
 */