From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out.tiscali.be (spoolo1.tiscali.be [62.235.13.210]) by dsl2.external.hp.com (Postfix) with ESMTP id 2759A48DC for ; Sat, 25 Oct 2003 05:13:03 -0600 (MDT) Message-ID: <3F9A5ACA.1010403@tiscali.be> Date: Sat, 25 Oct 2003 11:13:14 +0000 From: Joel Soete MIME-Version: 1.0 To: Randolph Chung Cc: parisc-linux@lists.parisc-linux.org Subject: Re: [parisc-linux] Re: teaching the kernel to do division References: <20031023072157.GX24406@tausq.org> <20031023233935.GZ24406@tausq.org> In-Reply-To: <20031023233935.GZ24406@tausq.org> Content-Type: text/plain; charset=us-ascii; format=flowed Sender: parisc-linux-admin@lists.parisc-linux.org Errors-To: parisc-linux-admin@lists.parisc-linux.org List-Help: List-Post: List-Subscribe: , List-Id: parisc-linux developers list List-Unsubscribe: , List-Archive: Hi Rnadolph and all, I reach to figure out what your pb is. This new algo is Ok and the previous formula was definitely wrong (even in 2.4 :( ). So it could be interesting to fix it also. For this I start from basic math: Dividend = divisor * quotient + reminder ie D = d * q + r (D, d, q, r: being integers) I can also split D in two 32bits words and write D = D1 * 2^32 + D0 But I always have only one equation with two unknown var (q and r). Is somebody knows where can I find the right solution? (or should I find it back in objdump from : uint32_t div64(uint64_t *n, uint32_t base) { uint32_t rem; rem = *n % base; *n = *n / base; return rem; }) Thanks in advance, Joel Randolph Chung wrote: >>does anyone want to look into fixing it, and/or writing an optimized >>version of that function for pa? :-) it needs to do basically this (but >>be standalone) > > > Here's one way to do it, but maybe it can be optimized a bit. Any > suggestions before i send it upstream? > > randolph > > Index: lib/div64.c > =================================================================== > RCS file: /var/cvs/linux-2.6/lib/div64.c,v > retrieving revision 1.1 > diff -u -p -r1.1 div64.c > --- lib/div64.c 29 Jul 2003 17:02:19 -0000 1.1 > +++ lib/div64.c 23 Oct 2003 23:36:08 -0000 > @@ -25,26 +25,28 @@ > > uint32_t __div64_32(uint64_t *n, uint32_t base) > { > - uint32_t low, low2, high, rem; > + uint64_t rem = *n; > + uint64_t b = base; > + uint64_t res = 0, d = 1; > > - low = *n & 0xffffffff; > - high = *n >> 32; > - rem = high % (uint32_t)base; > - high = high / (uint32_t)base; > - low2 = low >> 16; > - low2 += rem << 16; > - rem = low2 % (uint32_t)base; > - low2 = low2 / (uint32_t)base; > - low = low & 0xffff; > - low += rem << 16; > - rem = low % (uint32_t)base; > - low = low / (uint32_t)base; > + if (b > 0) { > + while (b < rem) { > + b <<= 1; > + d <<= 1; > + } > + } > + > + do { > + if (rem >= b) { > + rem -= b; > + res += d; > + } > + b >>= 1; > + d >>= 1; > + } while (d); > > - *n = low + > - ((uint64_t)low2 << 16) + > - ((uint64_t)high << 32); > - > - return rem; > + *n = res; > + return rem; > } > > EXPORT_SYMBOL(__div64_32); >