[RFC V1] lib: cordic: add library module for cordic angle calculation

[RFC V1] lib: cordic: add library module for cordic angle calculation

[Arend van Spriel]

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

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");
-- 
1.7.4.1

Re: [RFC V1] lib: cordic: add library module for cordic angle calculation

[Randy Dunlap]

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 ***

Re: [RFC V1] lib: cordic: add library module for cordic angle calculation

[Larry Finger]

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

Re: [RFC V1] lib: cordic: add library module for cordic angle calculation

[Arend van Spriel]

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>
&nbsp; &nbsp; <i>s32</i> <b>i</b>;<br>
&nbsp; &nbsp; <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

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC V1] lib: cordic: add library module for cordic angle calculation

[Arend van Spriel]

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

-- 
Almost nobody dances sober, unless they happen to be insane.
-- H.P. Lovecraft --

Re: [RFC V1] lib: cordic: add library module for cordic angle calculation

[Randy Dunlap]

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 ***