Re: Kernel area libmish stuff (Cordic algorithm)
Aloha! Peter Jeremy wrote: > For a totally different approach, try Cordic algorithms. Cordic > algorithms let you implement circular and hyperbolic functions > (including exponential, log and sqrt) using add, subtract, shift and > table lookup. (An n-bit result needs an n-entry x n-bit table, 2n > shifts and 3n adds/subtracts). I know there was an article in October > 1990 Dr Dobbs Journal and a web search should probably find plenty > more. Ray Andraka is somewhat of the Cordic guru on the net, albeit usually associated with FPGA-design. He has written several articles that describes Cordic algorithms, bot in general terms and specifically for FPGAs. Check for example his paper "A Survey of CORDIC Algorithms for FPGAs" which can be found here: http://www.andraka.com/papers.htm Also, Behrooz Parhami has written a book called "Computer Arithmetic - Algorithms and Hardware Design" that also contains a good intro to Cordic algorithms. I'm part of starting up a company that (a) builds hardware and (b) uses FreeBSD for different puposes. Albeit my time due to the starting of a company bit is very limited nowadays, I'm willing to at least try to answer questions relating these kinds of problems/areas (Cordics, arithmetic and such fun stuff). -- Cheers! Joachim - Alltid i harmonisk svängning --- FairLight -- FairLight -- FairLight -- FairLight --- Joachim Strömbergson ASIC SoC designer, nice to CUTE animals Phone: +46(0)31 - 27 98 47Web: http://www.ludd.luth.se/~watchman --- Spamfodder: [EMAIL PROTECTED] --- To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: Kernel area libmish stuff
On Sat, 10 Mar 2001 21:37:28 -0800, Farooq Mela <[EMAIL PROTECTED]> wrote: >Jordan DeLong wrote: >> I was thinking of just getting a sintable array and making a few simple >> functions, so the whole of libm doesn't need to be statically linked into the >> module (from my understanding, once loaded, this module wont ever get paged >+out, >> and thus it'd be _bad_ for it to be big). > >Well, you can't do any FP stuff inside the kernel, as stated by others. >But what you can do is use the fact that: > >sin(x) = x - (x^3)/3! + (x^5)/5! - (x^7)/7! ... Actually, whilst Taylor expansions are mathematically nice, they are generally a very poor implementation choice - primarily because they are infinite series and can be very slow to converge for large x. Trig functions are normally implemented as truncated Taylor series (you pick a finite expansion and tweak the co-efficients to minimise error), or ratios of polynomials. In both cases, the polynomials need to be `tuned' to suit the FP precision. If you do decide to go the fixed-point approach, remember that multiplication and division need fixups afterwards to re-align the binary point. (Multiplying two numbers with a 24 bit fraction gives a result with a 48 bit fraction). If you did pick a 24-bit fraction, you could probably pinch the co-efficients out of the `float' trig functions in msun. For a totally different approach, try Cordic algorithms. Cordic algorithms let you implement circular and hyperbolic functions (including exponential, log and sqrt) using add, subtract, shift and table lookup. (An n-bit result needs an n-entry x n-bit table, 2n shifts and 3n adds/subtracts). I know there was an article in October 1990 Dr Dobbs Journal and a web search should probably find plenty more. Peter To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: Kernel area libmish stuff
Jordan DeLong wrote: > I was thinking of just getting a sintable array and making a few simple > functions, so the whole of libm doesn't need to be statically linked into the > module (from my understanding, once loaded, this module wont ever get paged out, > and thus it'd be _bad_ for it to be big). Well, you can't do any FP stuff inside the kernel, as stated by others. But what you can do is use the fact that: sin(x) = x - (x^3)/3! + (x^5)/5! - (x^7)/7! ... and things like sin(-x) = -sin(x), etc, and integer arithmetic. You'd have to multiply X by a suitably large "base" value so that you dont have underflow, and compute it that way, and then divide the final answer by the base. Throughout your program, you'd have to change all your floating point arithmetic to use this sort of arithmetic - first multiplying by the base, doing all calculations, and dividing by the base once you arrive at the _final_ answer. A real pain, at best. The rest of the transcendental trig's can be built using identities like cos(x) = sin(x + pi/2), tan(x) = sin(x)/cos(x), etc. HTH -- farooq <[EMAIL PROTECTED]> "Life's not fair, but the root password helps." -BOFH To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: Kernel area libmish stuff
> > On Fri, 9 Mar 2001, Matt Dillon wrote: > > > > > You can't safely do FP instructions in the kernel. I do not > > > believe the FP context is saved/restored between processes in kernel > > > mode, only from user mode. The kernel saves and restores the fp > state > > > in the few places it uses FP instructions (for memory copying). > > > In anycase, I think there'd be a problem here. > > > > The last time I tried using FP in a device driver, it caused kernel > > panics (I hate it when that happens...) > > Seeing as the original requestor wanted to use FP functions to do number > crunching in screen savers, would adding a few strategic FP save/restore > calls in the syscons driver be enough to allow FP calculations in screen > saver modules? Please forget I ever said this. I took a look at what would be involved, and it's wa too deep for me to even begin about thinking about it. -- Matt Emmerton To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: Kernel area libmish stuff
> On Fri, 9 Mar 2001, Matt Dillon wrote: > > > You can't safely do FP instructions in the kernel. I do not > > believe the FP context is saved/restored between processes in kernel > > mode, only from user mode. The kernel saves and restores the fp state > > in the few places it uses FP instructions (for memory copying). > > In anycase, I think there'd be a problem here. > > The last time I tried using FP in a device driver, it caused kernel > panics (I hate it when that happens...) Seeing as the original requestor wanted to use FP functions to do number crunching in screen savers, would adding a few strategic FP save/restore calls in the syscons driver be enough to allow FP calculations in screen saver modules? -- Matt Emmerton To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: Kernel area libmish stuff
On Fri, 9 Mar 2001, Matt Dillon wrote: > You can't safely do FP instructions in the kernel. I do not > believe the FP context is saved/restored between processes in kernel > mode, only from user mode. The kernel saves and restores the fp state > in the few places it uses FP instructions (for memory copying). > In anycase, I think there'd be a problem here. The last time I tried using FP in a device driver, it caused kernel panics (I hate it when that happens...) -Richard --- Richard Hodges | Matriplex, inc. Product Manager | 769 Basque Way [EMAIL PROTECTED] | Carson City, NV 89706 775-886-6477| www.matriplex.com To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: Kernel area libmish stuff
You can't safely do FP instructions in the kernel. I do not believe the FP context is saved/restored between processes in kernel mode, only from user mode. The kernel saves and restores the fp state in the few places it uses FP instructions (for memory copying). In anycase, I think there'd be a problem here. -Matt :There's probably a way to include *some* of the libm functions (from :/usr/src/lib/msun, since /usr/src/lib/libm is deprecated). However, this :would require a considerable amount of Makefile magic, and also require that :the msun code be present in order to do a complete build of the kernel with :modules. : :I doubt that this requirement would make you many friends in -questions :) : :> I was thinking of just getting a sintable array and making a few simple :> functions, so the whole of libm doesn't need to be statically linked into :the :> module (from my understanding, once loaded, this module wont ever get :paged out, :> and thus it'd be _bad_ for it to be big). : :This is probably the best way to go, IMO. : :-- :Matt Emmerton To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Re: Kernel area libmish stuff
> Well here's the story: a few days ago my video card broke, so I'm without > X and such, and using a spare 486 box on the freebsd console. Out of lack of > other things to do, I did most of the porting of one of the screensavers in the > xscreensaver collection to the freebsd syscons. > > The problem I'm having now is I dunno the _right_ way to get the trig functions > from the userland libm in kernel space. _is_ there a right way? or can it be > statically linked into the screensaver module? (ouch) There's probably a way to include *some* of the libm functions (from /usr/src/lib/msun, since /usr/src/lib/libm is deprecated). However, this would require a considerable amount of Makefile magic, and also require that the msun code be present in order to do a complete build of the kernel with modules. I doubt that this requirement would make you many friends in -questions :) > I was thinking of just getting a sintable array and making a few simple > functions, so the whole of libm doesn't need to be statically linked into the > module (from my understanding, once loaded, this module wont ever get paged out, > and thus it'd be _bad_ for it to be big). This is probably the best way to go, IMO. -- Matt Emmerton To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
Kernel area libmish stuff
Well here's the story: a few days ago my video card broke, so I'm without X and such, and using a spare 486 box on the freebsd console. Out of lack of other things to do, I did most of the porting of one of the screensavers in the xscreensaver collection to the freebsd syscons. The problem I'm having now is I dunno the _right_ way to get the trig functions from the userland libm in kernel space. _is_ there a right way? or can it be statically linked into the screensaver module? (ouch) I was thinking of just getting a sintable array and making a few simple functions, so the whole of libm doesn't need to be statically linked into the module (from my understanding, once loaded, this module wont ever get paged out, and thus it'd be _bad_ for it to be big). Any thoughts? I get my new card in two days, hehe; so this project is over in two days regardless of if I finish it/find a good way to do this. Thanks, -Jordan To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message