Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id ; Thu, 7 Feb 2002 11:12:14 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id ; Thu, 7 Feb 2002 11:12:06 -0500 Received: from gra-vd1.iram.es ([150.214.224.250]:54444 "EHLO gra-vd1.iram.es") by vger.kernel.org with ESMTP id ; Thu, 7 Feb 2002 11:11:52 -0500 Message-ID: <3C62A735.6030906@iram.es> Date: Thu, 07 Feb 2002 17:11:33 +0100 From: Gabriel Paubert User-Agent: Mozilla/5.0 (X11; U; Linux ppc; en-US; rv:0.9.5) Gecko/20011016 X-Accept-Language: en-us MIME-Version: 1.0 To: Troy Benjegerdes CC: linux-kernel@vger.kernel.org Subject: Re: 64-bit divide cleanup (tested on ppc) In-Reply-To: <87r8oez0ks.fsf@fadata.bg> <20020127205141.L5808@mea-ext.zmailer.org> <20020128180001.G14339@altus.drgw.net> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org X-Mailing-List: linux-kernel@vger.kernel.org Hi Troy, sorry for the delay, I was sick :-( Troy Benjegerdes wrote: > Attached is a patch to get rid of asm/div64.h on arches that don't have > optimized asm routines. > > I didn't include removeing the various arch/div64.h file yet, since I want > some comments on this. > [snipped] > =================================================================== > RCS file: /cvsdev/hhl-2.4.17/linux/fs/ntfs/util.c,v > retrieving revision 1.1 > diff -u -r1.1 util.c > --- fs/ntfs/util.c 2001/11/30 22:28:59 1.1 > +++ fs/ntfs/util.c 2002/01/29 00:40:14 > @@ -13,7 +13,8 @@ > #include "util.h" > #include > #include > -#include /* For do_div(). */ > +#define USE_SLOW_64BIT_DIVIDES > +#include /* For do_div(). */ > #include "support.h" > > /* > @@ -233,7 +234,7 @@ > { > /* Subtract the NTFS time offset, then convert to 1s intervals. */ > ntfs_time64_t t = ntutc - NTFS_TIME_OFFSET; > - do_div(t, 10000000); > + do_div(&t, 10000000); > return (ntfs_time_t)t; > } > > Index: fs/smbfs/proc.c > =================================================================== > RCS file: /cvsdev/hhl-2.4.17/linux/fs/smbfs/proc.c,v > retrieving revision 1.1 > diff -u -r1.1 proc.c > --- fs/smbfs/proc.c 2001/11/30 22:28:58 1.1 > +++ fs/smbfs/proc.c 2002/01/29 00:40:17 > @@ -18,12 +18,14 @@ > #include > #include > > +#define USE_SLOW_64BIT_DIVIDES > +#include > + > #include > #include > #include > > #include > -#include > > #include "smb_debug.h" > #include "proto.h" > @@ -375,7 +377,7 @@ > /* FIXME: what about the timezone difference? */ > /* Subtract the NTFS time offset, then convert to 1s intervals. */ > u64 t = ntutc - NTFS_TIME_OFFSET; > - do_div(t, 10000000); > + do_div(&t, 10000000); > return (time_t)t; > } At least for these 2, your patch is wrong. 10000000 is not especially small and the algorithm you propose does not work for these. It is limited to about 65536 actually. > > Index: lib/vsprintf.c > =================================================================== > RCS file: /cvsdev/hhl-2.4.17/linux/lib/vsprintf.c,v > retrieving revision 1.1 > diff -u -r1.1 vsprintf.c > --- lib/vsprintf.c 2001/11/30 22:28:59 1.1 > +++ lib/vsprintf.c 2002/01/29 00:40:24 > @@ -19,9 +19,9 @@ > #include > #include > #include > +/* #define USE_SLOW_64BIT_DIVIDE */ > +#include > > -#include > - > /** > * simple_strtoul - convert a string to an unsigned long > * @cp: The start of the string > @@ -165,7 +165,7 @@ > if (num == 0) > tmp[i++]='0'; > else while (num != 0) > - tmp[i++] = digits[do_div(num,base)]; > + tmp[i++] = digits[do_div(&num,base)]; Forcing to use slow do_div version even when base is 8 or 16 is not nice. Heck I believe that seperating it into several cases and having a different 2 or 3 distinct loops (one for base 10, the other or 2 others for shifts by 3 or 4) could actually result in smaller code. On PPC and Alpha at lesat the compiler knows how to do a divide by 10 with a multiply high or however it's called instruction. Oh, and what abour removing the if and doing a do {...} while(num!=0) instead ? > if (i > precision) > precision = i; > size -= precision; > @@ -426,22 +426,31 @@ > } > continue; > } > - if (qualifier == 'L') > + > + switch (qualifier) { > + case 'L': > num = va_arg(args, long long); > - else if (qualifier == 'l') { > - num = va_arg(args, unsigned long); > + break; > + case 'l': > if (flags & SIGN) > - num = (signed long) num; > - } else if (qualifier == 'Z') { > + num = (signed long long) va_arg(args, long); > + else > + num = va_arg(args, unsigned long); > + break; > + case 'Z': > num = va_arg(args, size_t); > - } else if (qualifier == 'h') { > - num = (unsigned short) va_arg(args, int); > + break; > + case 'h': > if (flags & SIGN) > - num = (signed short) num; > - } else { > - num = va_arg(args, unsigned int); > + num = (signed long long) va_arg(args, int); > + else > + num = va_arg(args, unsigned int); > + break; > + default: > if (flags & SIGN) > - num = (signed int) num; > + num = (signed long long) va_arg(args, int); > + else > + num = va_arg(args, unsigned int); > } > str = number(str, end, num, base, > field_width, precision, flags); > Index: include/linux/div64.h > =================================================================== > RCS file: /cvsdev/hhl-2.4.17/linux/include/linux/div64.h > diff -N div64.h > --- /dev/null Tue May 5 13:32:27 1998 > +++ include/linux/div64.h Mon Jan 28 16:59:28 2002 > @@ -0,0 +1,85 @@ > +/* > + * include/linux/div64.h > + * > + * Primarily used by vsprintf to divide a 64 bit int N by a small integer base ^^^^^ Read the comments, here goes you 10000000 factor. The modulo once shifted left by 16 bits can easily overflow.... Perhaps you should patch it s/small/_small_/ to better see it. > + * We really do NOT want to encourage people to do slow 64 bit divides in > + * the kernel, so the 'default' version of this function panics if you > + * try and divide a 64 bit number by anything other than 8 or 16. > + * > + * If you really *really* need this, and are prepared to be flamed by > + * lkml, #define USE_SLOW_64BIT_DIVIDES before including this file. > + */ > +#ifndef __DIV64 > +#define __DIV64 > + > +#include > + > +/* configurable */ > +#undef __USE_ASM > + > + > +#ifdef __USE_ASM > +/* yeah, this is a mess, and leaves out m68k.... */ > +# if defined(CONFIG_X86) || define(CONFIG_ARCH_S390) || defined(CONFIG_MIPS) > +# define __USE_ASM__ > +# endif > +#endif > + > +#ifdef __USE_ASM__ > +#include > +#else /* __USE_ASM__ */ > +static inline int do_div(unsigned long long * n, unsigned long base) > +{ > + int res = 0; > + unsigned long long t = *n; > + if ( t == (unsigned long)t ){ /* this should handle 64 bit platforms */ > + res = ((unsigned long) t) % base; > + t = ((unsigned long) t) / base; > + } else { > +#ifndef USE_SLOW_64BIT_DIVIDES > + switch (base) { > + case 8: > + res = ((unsigned long) t & 0x7); > + t = t >> 3; > + break; > + case 16: > + res = ((unsigned long) t & 0xf); > + t = t >> 4; > + break; > + default: > + panic("do_div called with 64 bit arg and unsupported base\n", base); > + } > +#else /* USE_SLOW_64BIT_DIVIDES */ > + /* this was stolen from the old asm-parisc/div64.h */ > + /* > + * Copyright (C) 1999 Hewlett-Packard Co > + * Copyright (C) 1999 David Mosberger-Tang > + * > + * vsprintf uses this to divide a 64-bit integer N by a small s/small/_small_/ just to be sure that the comment is understood. For the 10000000 case, I believe a simple stupid looping algorithm is the only solution which does not result in code size explosion. Regards, Gabriel. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/