division.c

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2006 Josef Cejka
00003  * All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  *
00009  * - Redistributions of source code must retain the above copyright
00010  *   notice, this list of conditions and the following disclaimer.
00011  * - Redistributions in binary form must reproduce the above copyright
00012  *   notice, this list of conditions and the following disclaimer in the
00013  *   documentation and/or other materials provided with the distribution.
00014  * - The name of the author may not be used to endorse or promote products
00015  *   derived from this software without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
00018  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
00019  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
00020  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
00021  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
00022  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00023  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00024  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00025  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
00026  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00027  */
00028 
00037 #include <division.h>
00038 
00039 #define ABSVAL(x) ( (x) > 0 ? (x) : -(x))
00040 #define SGN(x) ( (x) >= 0 ? 1 : 0 )
00041                                       
00042 static unsigned int divandmod32(unsigned int a, unsigned int b, unsigned int *remainder)
00043 {
00044         unsigned int result;
00045         int steps = sizeof(unsigned int) * 8; 
00046         
00047         *remainder = 0;
00048         result = 0;
00049         
00050         if (b == 0) {
00051                 /* FIXME: division by zero */
00052                 return 0;
00053         }
00054         
00055         if ( a < b) {
00056                 *remainder = a;
00057                 return 0;
00058         }
00059 
00060         for ( ; steps > 0; steps--) {
00061                 /* shift one bit to remainder */
00062                 *remainder = ( (*remainder) << 1) | (( a >> 31) & 0x1);
00063                 result <<= 1;
00064                 
00065                 if (*remainder >= b) {
00066                                 *remainder -= b;
00067                                 result |= 0x1;
00068                 }
00069                 a <<= 1;
00070         }
00071 
00072         return result;
00073 }
00074 
00075 
00076 static unsigned long long divandmod64(unsigned long long a, unsigned long long b, unsigned long long *remainder)
00077 {
00078         unsigned long long result;
00079         int steps = sizeof(unsigned long long) * 8; 
00080         
00081         *remainder = 0;
00082         result = 0;
00083         
00084         if (b == 0) {
00085                 /* FIXME: division by zero */
00086                 return 0;
00087         }
00088         
00089         if ( a < b) {
00090                 *remainder = a;
00091                 return 0;
00092         }
00093 
00094         for ( ; steps > 0; steps--) {
00095                 /* shift one bit to remainder */
00096                 *remainder = ( (*remainder) << 1) | ((a >> 63) & 0x1);
00097                 result <<= 1;
00098                 
00099                 if (*remainder >= b) {
00100                                 *remainder -= b;
00101                                 result |= 0x1;
00102                 }
00103                 a <<= 1;
00104         }
00105 
00106         return result;
00107 }
00108 
00109 /* 32bit integer division */
00110 int __divsi3(int a, int b) 
00111 {
00112         unsigned int rem;
00113         int result;
00114         
00115         result = (int)divandmod32(ABSVAL(a), ABSVAL(b), &rem);
00116 
00117         if ( SGN(a) == SGN(b)) return result;
00118         return -result;
00119 }
00120 
00121 /* 64bit integer division */
00122 long long __divdi3(long long a, long long b) 
00123 {
00124         unsigned long long rem;
00125         long long result;
00126         
00127         result = (long long)divandmod64(ABSVAL(a), ABSVAL(b), &rem);
00128 
00129         if ( SGN(a) == SGN(b)) return result;
00130         return -result;
00131 }
00132 
00133 /* 32bit unsigned integer division */
00134 unsigned int __udivsi3(unsigned int a, unsigned int b)
00135 {
00136         unsigned int rem;
00137         return divandmod32(a, b, &rem);
00138 }
00139 
00140 /* 64bit unsigned integer division */
00141 unsigned long long __udivdi3(unsigned long long a, unsigned long long b)
00142 {
00143         unsigned long long  rem;
00144         return divandmod64(a, b, &rem);
00145 }
00146 
00147 /* 32bit remainder of the signed division */
00148 int __modsi3(int a, int b)
00149 {
00150         unsigned int rem;
00151         divandmod32(a, b, &rem);
00152         
00153         /* if divident is negative, remainder must be too */
00154         if (!(SGN(a))) {
00155                 return -((int)rem);
00156         }
00157         
00158         return (int)rem;
00159 }
00160 
00161 /* 64bit remainder of the signed division */
00162 long long __moddi3(long long a,long  long b)
00163 {
00164         unsigned long long rem;
00165         divandmod64(a, b, &rem);
00166         
00167         /* if divident is negative, remainder must be too */
00168         if (!(SGN(a))) {
00169                 return -((long long)rem);
00170         }
00171         
00172         return (long long)rem;
00173 }
00174 
00175 /* 32bit remainder of the unsigned division */
00176 unsigned int __umodsi3(unsigned int a, unsigned int b)
00177 {
00178         unsigned int rem;
00179         divandmod32(a, b, &rem);
00180         return rem;
00181 }
00182 
00183 /* 64bit remainder of the unsigned division */
00184 unsigned long long __umoddi3(unsigned long long a, unsigned long long b)
00185 {
00186         unsigned long long rem;
00187         divandmod64(a, b, &rem);
00188         return rem;
00189 }
00190 
00191 unsigned long long __udivmoddi3(unsigned long long a, unsigned long long b, unsigned long long *c)
00192 {
00193         return divandmod64(a, b, c);
00194 }
00195 

Generated on Sun Jun 18 18:00:18 2006 for HelenOS Userspace (ia64) by  doxygen 1.4.6