WebSVN – HelenOS-historic – Diff – /uspace/trunk/softint/generic/division.c


/*
 * Copyright (C) 2006 Josef Cejka
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/** @addtogroup softint
 
 * @{
 */
/**
 * @file
 * SW implementation of 32 and 64 bit division and modulo.
 */
 
#include <division.h>
 
#define ABSVAL(x) ( (x) > 0 ? (x) : -(x))
#define SGN(x) ( (x) >= 0 ? 1 : 0 )
                     
static unsigned int divandmod32(unsigned int a, unsigned int b, unsigned int *remainder)
{
    unsigned int result;
    int steps = sizeof(unsigned int) * 8;
   
    *remainder = 0;
    result = 0;
   
    if (b == 0) {
        /* FIXME: division by zero */
        return 0;
    }
   
    if ( a < b) {
        *remainder = a;
        return 0;
    }
 
    for ( ; steps > 0; steps--) {
        /* shift one bit to remainder */
        *remainder = ( (*remainder) << 1) | (( a >> 31) & 0x1);
        result <<= 1;
       
        if (*remainder >= b) {
                *remainder -= b;
                result |= 0x1;
        }
        a <<= 1;
    }
 
    return result;
}
 
 
static unsigned long long divandmod64(unsigned long long a, unsigned long long b, unsigned long long *remainder)
{
    unsigned long long result;
    int steps = sizeof(unsigned long long) * 8;
   
    *remainder = 0;
    result = 0;
   
    if (b == 0) {
        /* FIXME: division by zero */
        return 0;
    }
   
    if ( a < b) {
        *remainder = a;
        return 0;
    }
 
    for ( ; steps > 0; steps--) {
        /* shift one bit to remainder */
        *remainder = ( (*remainder) << 1) | ((a >> 63) & 0x1);
        result <<= 1;
       
        if (*remainder >= b) {
                *remainder -= b;
                result |= 0x1;
        }
        a <<= 1;
    }
 
    return result;
}
 
/* 32bit integer division */
int __divsi3(int a, int b)
{
    unsigned int rem;
    int result;
   
    result = (int)divandmod32(ABSVAL(a), ABSVAL(b), &rem);
 
    if ( SGN(a) == SGN(b)) return result;
    return -result;
}
 
/* 64bit integer division */
long long __divdi3(long long a, long long b)
{
    unsigned long long rem;
    long long result;
   
    result = (long long)divandmod64(ABSVAL(a), ABSVAL(b), &rem);
 
    if ( SGN(a) == SGN(b)) return result;
    return -result;
}
 
/* 32bit unsigned integer division */
unsigned int __udivsi3(unsigned int a, unsigned int b)
{
    unsigned int rem;
    return divandmod32(a, b, &rem);
}
 
/* 64bit unsigned integer division */
unsigned long long __udivdi3(unsigned long long a, unsigned long long b)
{
    unsigned long long  rem;
    return divandmod64(a, b, &rem);
}
 
/* 32bit remainder of the signed division */
int __modsi3(int a, int b)
{
    unsigned int rem;
    divandmod32(a, b, &rem);
   
    /* if divident is negative, remainder must be too */
    if (!(SGN(a))) {
        return -((int)rem);
    }
   
    return (int)rem;
}
 
/* 64bit remainder of the signed division */
long long __moddi3(long long a,long  long b)
{
    unsigned long long rem;
    divandmod64(a, b, &rem);
   
    /* if divident is negative, remainder must be too */
    if (!(SGN(a))) {
        return -((long long)rem);
    }
   
    return (long long)rem;
}
 
/* 32bit remainder of the unsigned division */
unsigned int __umodsi3(unsigned int a, unsigned int b)
{
    unsigned int rem;
    divandmod32(a, b, &rem);
    return rem;
}
 
/* 64bit remainder of the unsigned division */
unsigned long long __umoddi3(unsigned long long a, unsigned long long b)
{
    unsigned long long rem;
    divandmod64(a, b, &rem);
    return rem;
}
 
unsigned long long __udivmoddi3(unsigned long long a, unsigned long long b, unsigned long long *c)
{
    return divandmod64(a, b, c);
}
 
/** @}
 */
 

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

Subversion Repositories HelenOS-historic

(root)/uspace/trunk/softint/generic/division.c – Rev 1653 → 1740