Message ID | 1306352426-1899-1-git-send-email-arend@broadcom.com (mailing list archive) |
---|---|
State | Not Applicable, archived |
Headers | show |
On Wed, 25 May 2011 21:40:26 +0200 Arend van Spriel wrote: > diff --git a/include/linux/cordic.h b/include/linux/cordic.h > new file mode 100644 > index 0000000..28443a6 > --- /dev/null > +++ b/include/linux/cordic.h > @@ -0,0 +1,48 @@ > +/** > + * struct - i/q coordinate. * struct cordic_iq - i/q coordinate > + * > + * @i: real part of coordinate (in phase). > + * @q: imaginary part of coordinate (quadrature). > + */ > +struct cordic_iq { > + s32 i; > + s32 q; > +}; --- ~Randy *** Remember to use Documentation/SubmitChecklist when testing your code *** -- To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 05/25/2011 02:40 PM, Arend van Spriel wrote: > The brcm80211 driver in the staging tree has a cordic function to > determine cosine and sine for a given angle. Feedback received from > John Linville suggested that these kind of functions should be made > available to others as a library function in the kernel tree. > > V1: > - code taken from brcm80211 driver and added kernel-doc comments. > - code compiled and tested for x86 architecture using brcm80211 driver. > - code compiled for x86_64, ARM, and MIPS architectures. > > Cc: linux-kernel@vger.kernel.org > Cc: linux-wireless@vger.kernel.org > Cc: "John W. Linville"<linville@tuxdriver.com> > Cc: Greg Kroah-Hartman<gregkh@suse.de> > Cc: Dan Carpenter<error27@gmail.com> > Reviewed-by: Roland Vossen<rvossen@broadcom.com> > Reviewed-by: Henry Ptasinski<henryp@broadcom.com> > Reviewed-by: Franky (Zhenhui) Lin<frankyl@broadcom.com> > Signed-off-by: Arend van Spriel<arend@broadcom.com> > --- > include/linux/cordic.h | 48 +++++++++++++++++++++++ > lib/Kconfig | 7 +++ > lib/Makefile | 2 + > lib/cordic.c | 99 ++++++++++++++++++++++++++++++++++++++++++++++++ > 4 files changed, 156 insertions(+), 0 deletions(-) > create mode 100644 include/linux/cordic.h > create mode 100644 lib/cordic.c There is a similar routine in b43, thus this library function will likely have at least 2 users. > diff --git a/include/linux/cordic.h b/include/linux/cordic.h > new file mode 100644 > index 0000000..28443a6 > --- /dev/null > +++ b/include/linux/cordic.h > @@ -0,0 +1,48 @@ > +/* > + * Copyright (c) 2011 Broadcom Corporation > + * > + * Permission to use, copy, modify, and/or distribute this software for any > + * purpose with or without fee is hereby granted, provided that the above > + * copyright notice and this permission notice appear in all copies. > + * > + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES > + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF > + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY > + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES > + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION > + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN > + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. > + */ > +#ifndef __CORDIC_H_ > +#define __CORDIC_H_ > + > +#include<linux/types.h> > + > +/** > + * struct - i/q coordinate. > + * > + * @i: real part of coordinate (in phase). > + * @q: imaginary part of coordinate (quadrature). > + */ > +struct cordic_iq { > + s32 i; > + s32 q; > +}; > + > +/** > + * cordic_calc_iq() - calculates the i/q coordinate for given angle. > + * > + * @theta: angle in degrees for which i/q coordinate is to be calculated. > + * @coord: function output parameter holding the i/q coordinate. > + * > + * The function calculates the i/q coordinate for a given angle using > + * cordic algorithm. The coordinate consists of a real (i) and an > + * imaginary (q) part. The real part is essentially the cosine of the > + * angle and the imaginary part is the sine of the angle. The returned > + * values are scaled by 2^16 for precision. The range for theta is > + * for -180 degrees to +180 degrees. Passed values outside this range are > + * converted before doing the actual calculation. > + */ > +void cordic_calc_iq(s32 theta, struct cordic_iq *coord); > + > +#endif /* __CORDIC_H_ */ > diff --git a/lib/Kconfig b/lib/Kconfig > index ff9e5a3..5c70204 100644 > --- a/lib/Kconfig > +++ b/lib/Kconfig > @@ -279,4 +279,11 @@ config AVERAGE > > If unsure, say N. > > +config CORDIC > + tristate "Cordic function" > + help > + The option provides arithmetic function using cordic algorithm > + so its calculations are in fixed point. Modules can select this > + when they require this function. Module will be called cordic. > + > endmenu > diff --git a/lib/Makefile b/lib/Makefile > index 704959d..9e3c1b0 100644 > --- a/lib/Makefile > +++ b/lib/Makefile > @@ -117,6 +117,8 @@ obj-$(CONFIG_AVERAGE) += average.o > > obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o > > +obj-$(CONFIG_CORDIC) += cordic.o > + > hostprogs-y := gen_crc32table > clean-files := crc32table.h > > diff --git a/lib/cordic.c b/lib/cordic.c > new file mode 100644 > index 0000000..3952258 > --- /dev/null > +++ b/lib/cordic.c > @@ -0,0 +1,99 @@ > +/* > + * Copyright (c) 2011 Broadcom Corporation > + * > + * Permission to use, copy, modify, and/or distribute this software for any > + * purpose with or without fee is hereby granted, provided that the above > + * copyright notice and this permission notice appear in all copies. > + * > + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES > + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF > + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY > + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES > + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION > + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN > + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. > + */ > +#include<linux/module.h> > +#include<linux/cordic.h> > + > +#define CORDIC_ANGLE_GEN 39797 > +#define CORDIC_PRECISION_SHIFT 16 > +#define CORDIC_NUM_ITER (CORDIC_PRECISION_SHIFT + 2) > + > +#define FIXED(X) ((s32)((X)<< CORDIC_PRECISION_SHIFT)) > +#define FLOAT(X) (((X)>= 0) \ > + ? ((((X)>> (CORDIC_PRECISION_SHIFT - 1)) + 1)>> 1) \ > + : -((((-(X))>> (CORDIC_PRECISION_SHIFT - 1)) + 1)>> 1)) > + > +static const s32 AtanTbl[] = { In Documentation/CodingStyle, variables with mixed-case names are frownid upon. > + 2949120, > + 1740967, > + 919879, > + 466945, > + 234379, > + 117304, > + 58666, > + 29335, > + 14668, > + 7334, > + 3667, > + 1833, > + 917, > + 458, > + 229, > + 115, > + 57, > + 29 > +}; > + > +/* > + * cordic_calc_iq() - calculates the i/q coordinate for given angle > + * > + * theta: angle in degrees for which i/q coordinate is to be calculated > + * coord: function output parameter holding the i/q coordinate > + */ > +void cordic_calc_iq(s32 theta, struct cordic_iq *coord) As "coord" is only for output, why not have this be a function returning a struct cordic_iq? > +{ > + s32 angle, valtmp; > + unsigned iter; > + int signx = 1; > + int signtheta; > + > + coord->i = CORDIC_ANGLE_GEN; > + coord->q = 0; > + angle = 0; > + > + theta = FIXED(theta); > + signtheta = (theta< 0) ? -1 : 1; > + theta = ((theta + FIXED(180) * signtheta) % FIXED(360)) - > + FIXED(180) * signtheta; > + > + if (FLOAT(theta)> 90) { > + theta -= FIXED(180); > + signx = -1; > + } else if (FLOAT(theta)< -90) { > + theta += FIXED(180); > + signx = -1; > + } > + > + for (iter = 0; iter< CORDIC_NUM_ITER; iter++) { > + if (theta> angle) { > + valtmp = coord->i - (coord->q>> iter); I think the whitespace should be the same on both sides of the >> operator. Either "coord->q>>iter" or "coord->q >> iter" would be OK. I know checkpatch.pl does not complain, but it does for other binary operators. > + coord->q += (coord->i>> iter); > + angle += AtanTbl[iter]; > + } else { > + valtmp = coord->i + (coord->q>> iter); > + coord->q -= (coord->i>> iter); > + angle -= AtanTbl[iter]; > + } > + coord->i = valtmp; > + } > + > + coord->i *= signx; > + coord->q *= signx; > +} > +EXPORT_SYMBOL(cordic_calc_iq); > + > +MODULE_DESCRIPTION("Cordic functions"); > +MODULE_AUTHOR("Broadcom Corporation"); > +MODULE_LICENSE("Dual BSD/GPL"); Larry -- To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 05/26/2011 10:09 AM, Arend van Spriel wrote: > On 05/25/2011 10:04 PM, Randy Dunlap wrote: >> On Wed, 25 May 2011 21:40:26 +0200 Arend van Spriel wrote: >>> +/** >>> + * struct - i/q coordinate. >> * struct cordic_iq - i/q coordinate > The kernel-doc processing is pretty smart here. In the current form I > get the html as attached. From that perspective your proposed change is > not needed, but if your point is that it would be more clear to the mere > mortal reading through the source code I can change it. > > Gr. AvS Attached html does not get through the mail server. So here is part of the html source: <h2>struct cordic_iq - i/q coordinate.</h2> <b>struct cordic_iq</b> {<br> <i>s32</i> <b>i</b>;<br> <i>s32</i> <b>q</b>;<br> };<br> <h3>Members</h3> <dl> <dt><b>i</b> <dd>real part of coordinate (in phase). <dt><b>q</b> <dd>imaginary part of coordinate (quadrature). </dl> Gr. AvS
On 05/25/2011 10:35 PM, Larry Finger wrote: > On 05/25/2011 02:40 PM, Arend van Spriel wrote: >> The brcm80211 driver in the staging tree has a cordic function to >> determine cosine and sine for a given angle. Feedback received from >> John Linville suggested that these kind of functions should be made >> available to others as a library function in the kernel tree. > There is a similar routine in b43, thus this library function will likely have > at least 2 users. I know (forgot to mention it in the commit message). Henry Ptasinski (broadcom colleague) actually verified both functions against Matlab implementation (or Scilab, if you prefer open-source ;-) ). The b43 version has a more limited range of the angle input in which the calculation is accurate. >> +static const s32 AtanTbl[] = { > In Documentation/CodingStyle, variables with mixed-case names are frownid upon. No frowning needed. I will change it ;-) > >> +/* >> + * cordic_calc_iq() - calculates the i/q coordinate for given angle >> + * >> + * theta: angle in degrees for which i/q coordinate is to be calculated >> + * coord: function output parameter holding the i/q coordinate >> + */ >> +void cordic_calc_iq(s32 theta, struct cordic_iq *coord) > As "coord" is only for output, why not have this be a function returning a > struct cordic_iq? Only to avoid passing the structure over the stack. Given the fact that it is only 8 bytes (4 bytes extra) I think it is ok to change it. Gr. AvS
On Thu, 26 May 2011 10:09:24 +0200 Arend van Spriel wrote: > On 05/25/2011 10:04 PM, Randy Dunlap wrote: > > On Wed, 25 May 2011 21:40:26 +0200 Arend van Spriel wrote: > >> +/** > >> + * struct - i/q coordinate. > > * struct cordic_iq - i/q coordinate > > The kernel-doc processing is pretty smart here. In the current form I > get the html as attached. From that perspective your proposed change is > not needed, but if your point is that it would be more clear to the mere > mortal reading through the source code I can change it. Hm, I see. scripts/kernel-doc gets the struct name from the source code in this case. too smart ;) AFAIK, everywhere else we use /** * struct structname - description and that's what Documentation/kernel-doc-nano-HOWTO.txt calls for, and yes, it would be more readable to us mortals also, so please change it. thanks, --- ~Randy *** Remember to use Documentation/SubmitChecklist when testing your code *** -- To unsubscribe from this list: send the line "unsubscribe linux-wireless" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/include/linux/cordic.h b/include/linux/cordic.h new file mode 100644 index 0000000..28443a6 --- /dev/null +++ b/include/linux/cordic.h @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2011 Broadcom Corporation + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ +#ifndef __CORDIC_H_ +#define __CORDIC_H_ + +#include <linux/types.h> + +/** + * struct - i/q coordinate. + * + * @i: real part of coordinate (in phase). + * @q: imaginary part of coordinate (quadrature). + */ +struct cordic_iq { + s32 i; + s32 q; +}; + +/** + * cordic_calc_iq() - calculates the i/q coordinate for given angle. + * + * @theta: angle in degrees for which i/q coordinate is to be calculated. + * @coord: function output parameter holding the i/q coordinate. + * + * The function calculates the i/q coordinate for a given angle using + * cordic algorithm. The coordinate consists of a real (i) and an + * imaginary (q) part. The real part is essentially the cosine of the + * angle and the imaginary part is the sine of the angle. The returned + * values are scaled by 2^16 for precision. The range for theta is + * for -180 degrees to +180 degrees. Passed values outside this range are + * converted before doing the actual calculation. + */ +void cordic_calc_iq(s32 theta, struct cordic_iq *coord); + +#endif /* __CORDIC_H_ */ diff --git a/lib/Kconfig b/lib/Kconfig index ff9e5a3..5c70204 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -279,4 +279,11 @@ config AVERAGE If unsure, say N. +config CORDIC + tristate "Cordic function" + help + The option provides arithmetic function using cordic algorithm + so its calculations are in fixed point. Modules can select this + when they require this function. Module will be called cordic. + endmenu diff --git a/lib/Makefile b/lib/Makefile index 704959d..9e3c1b0 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -117,6 +117,8 @@ obj-$(CONFIG_AVERAGE) += average.o obj-$(CONFIG_CPU_RMAP) += cpu_rmap.o +obj-$(CONFIG_CORDIC) += cordic.o + hostprogs-y := gen_crc32table clean-files := crc32table.h diff --git a/lib/cordic.c b/lib/cordic.c new file mode 100644 index 0000000..3952258 --- /dev/null +++ b/lib/cordic.c @@ -0,0 +1,99 @@ +/* + * Copyright (c) 2011 Broadcom Corporation + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ +#include <linux/module.h> +#include <linux/cordic.h> + +#define CORDIC_ANGLE_GEN 39797 +#define CORDIC_PRECISION_SHIFT 16 +#define CORDIC_NUM_ITER (CORDIC_PRECISION_SHIFT + 2) + +#define FIXED(X) ((s32)((X) << CORDIC_PRECISION_SHIFT)) +#define FLOAT(X) (((X) >= 0) \ + ? ((((X) >> (CORDIC_PRECISION_SHIFT - 1)) + 1) >> 1) \ + : -((((-(X)) >> (CORDIC_PRECISION_SHIFT - 1)) + 1) >> 1)) + +static const s32 AtanTbl[] = { + 2949120, + 1740967, + 919879, + 466945, + 234379, + 117304, + 58666, + 29335, + 14668, + 7334, + 3667, + 1833, + 917, + 458, + 229, + 115, + 57, + 29 +}; + +/* + * cordic_calc_iq() - calculates the i/q coordinate for given angle + * + * theta: angle in degrees for which i/q coordinate is to be calculated + * coord: function output parameter holding the i/q coordinate + */ +void cordic_calc_iq(s32 theta, struct cordic_iq *coord) +{ + s32 angle, valtmp; + unsigned iter; + int signx = 1; + int signtheta; + + coord->i = CORDIC_ANGLE_GEN; + coord->q = 0; + angle = 0; + + theta = FIXED(theta); + signtheta = (theta < 0) ? -1 : 1; + theta = ((theta + FIXED(180) * signtheta) % FIXED(360)) - + FIXED(180) * signtheta; + + if (FLOAT(theta) > 90) { + theta -= FIXED(180); + signx = -1; + } else if (FLOAT(theta) < -90) { + theta += FIXED(180); + signx = -1; + } + + for (iter = 0; iter < CORDIC_NUM_ITER; iter++) { + if (theta > angle) { + valtmp = coord->i - (coord->q >> iter); + coord->q += (coord->i >> iter); + angle += AtanTbl[iter]; + } else { + valtmp = coord->i + (coord->q >> iter); + coord->q -= (coord->i >> iter); + angle -= AtanTbl[iter]; + } + coord->i = valtmp; + } + + coord->i *= signx; + coord->q *= signx; +} +EXPORT_SYMBOL(cordic_calc_iq); + +MODULE_DESCRIPTION("Cordic functions"); +MODULE_AUTHOR("Broadcom Corporation"); +MODULE_LICENSE("Dual BSD/GPL");