CORDIC - sin cos for graphics etc.

Post your cool example code here.
Post Reply
User avatar
Pito
Posts: 1628
Joined: Sat Mar 26, 2016 3:26 pm
Location: Rapa Nui

CORDIC - sin cos for graphics etc.

Post by Pito » Tue Nov 01, 2016 5:18 pm

This is a simple example of CORDIC SIN and COS calculation which could be used when fast calc is required (ie for TFT graphics).
Other math functions like TAN could be calculated with Cordic too, afaik..
https://en.wikipedia.org/wiki/CORDIC

The below Example compares CORDIC 16bit calculation against floating point sin() and cos().
Mind the below 10-iteration cordic is ~3digits precise (you may increase the precision with more iterations), it returns BOTH sin and cos, and it is ~8-10x faster than the floating point (Maple Mini STM32 @72MHz)..

32bit CORDIC and a routine for the coef calc is here http://www.dcs.gla.ac.uk/~jhw/cordic/

Code: Select all

// CORDIC based SIN and COS in 16 bit signed fixed point math
// Based on http://www.dcs.gla.ac.uk/~jhw/cordic/
// Pito 11/2016, for Maple Mini @72MHz
// Function is valid for arguments in range -pi/2 -- pi/2
// For values pi/2--pi: value = half_pi-(theta-half_pi) and similarly for values -pi---pi/2
//
// 1.0 = 16384
// 1/k = 0.6072529350088812561694
// pi = 3.1415926536897932384626
// Some useful Constants
#define cordic_1K 0x000026DD
#define half_pi 0x00006487
#define MUL 16384.000000
#define CORDIC_NTAB 16
int cordic_ctab [] = {0x00003243, 0x00001DAC, 0x00000FAD, 0x000007F5, 0x000003FE, 
0x000001FF, 0x000000FF, 0x0000007F, 0x0000003F, 0x0000001F, 0x0000000F, 0x00000007, 
0x00000003, 0x00000001, 0x00000000, 0x00000000, };

void cordic(int theta, int *s, int *c, int n)
{
  int k, d, tx, ty, tz;
  int x=cordic_1K,y=0,z=theta;
  n = (n>CORDIC_NTAB) ? CORDIC_NTAB : n;
  for (k=0; k<n; ++k)
  {
    d = z>>15;
    //get sign. for other architectures, you might want to use the more portable version
    //d = z>=0 ? 0 : -1;
    tx = x - (((y>>k) ^ d) - d);
    ty = y + (((x>>k) ^ d) - d);
    tz = z - ((cordic_ctab[k] ^ d) - d);
    x = tx; y = ty; z = tz;
  }  
 *c = x; *s = y;
}


void setup() {
  // put your setup code here, to run once:
  
  	Serial1.begin(115200);  // Serial1 used here

    float p, p1;
    volatile float dummy;
    int s, c;
    int i, t, t1;    
    // make a few calculations in form of a Table to compare results and speed
    for(i=0;i<50;i++)
    {
        p = (i/50.0)*M_PI/2; 
        p1 = p * MUL;   
            
        t = micros();
        cordic(p1, &s, &c, 10); // 10 Cordic iterations
        t = micros() - t;
        
        t1 = micros();
        dummy = sin(p);
        dummy = cos(p);
        t1 = micros() - t1;
               
        Serial1.print(p,4);
        Serial1.print("   sin ");
        Serial1.print(s/MUL,4);
        Serial1.print(" ");
        Serial1.print(sin(p),4);
        Serial1.print("   cos ");
        Serial1.print(c/MUL,4);
        Serial1.print(" ");
        Serial1.print(cos(p),4);
        Serial1.print("  COR_micros= ");
        Serial1.print(t);
        Serial1.print("  FP_micros= ");
        Serial1.println(t1); 
        
    }   

        while(1);
}

void loop() {
  // put your main code here, to run repeatedly:

}
10 iterations:

Code: Select all

0.0000   sin 0.0013 0.0000   cos 0.9999 1.0000  COR_micros= 8  FP_micros= 5
0.0314   sin 0.0326 0.0314   cos 0.9994 0.9995  COR_micros= 8  FP_micros= 59
0.0628   sin 0.0637 0.0628   cos 0.9980 0.9980  COR_micros= 8  FP_micros= 57
0.0942   sin 0.0939 0.0941   cos 0.9955 0.9956  COR_micros= 8  FP_micros= 57
0.1257   sin 0.1249 0.1253   cos 0.9921 0.9921  COR_micros= 8  FP_micros= 57
0.1571   sin 0.1557 0.1564   cos 0.9878 0.9877  COR_micros= 8  FP_micros= 58
0.1885   sin 0.1865 0.1874   cos 0.9825 0.9823  COR_micros= 8  FP_micros= 57
0.2199   sin 0.2169 0.2181   cos 0.9761 0.9759  COR_micros= 8  FP_micros= 59
0.2513   sin 0.2474 0.2487   cos 0.9689 0.9686  COR_micros= 7  FP_micros= 58
0.2827   sin 0.2775 0.2790   cos 0.9606 0.9603  COR_micros= 8  FP_micros= 57
0.3142   sin 0.3109 0.3090   cos 0.9504 0.9511  COR_micros= 8  FP_micros= 63
0.3456   sin 0.3398 0.3387   cos 0.9405 0.9409  COR_micros= 8  FP_micros= 64
0.3770   sin 0.3689 0.3681   cos 0.9294 0.9298  COR_micros= 8  FP_micros= 63
0.4084   sin 0.3978 0.3971   cos 0.9175 0.9178  COR_micros= 8  FP_micros= 63
0.4398   sin 0.4262 0.4258   cos 0.9047 0.9048  COR_micros= 8  FP_micros= 64
0.4712   sin 0.4543 0.4540   cos 0.8909 0.8910  COR_micros= 8  FP_micros= 63
0.5027   sin 0.4818 0.4818   cos 0.8763 0.8763  COR_micros= 8  FP_micros= 63
0.5341   sin 0.5089 0.5090   cos 0.8608 0.8607  COR_micros= 8  FP_micros= 63
0.5655   sin 0.5356 0.5358   cos 0.8445 0.8443  COR_micros= 8  FP_micros= 64
0.5969   sin 0.5609 0.5621   cos 0.8278 0.8271  COR_micros= 8  FP_micros= 63
0.6283   sin 0.5864 0.5878   cos 0.8100 0.8090  COR_micros= 7  FP_micros= 63
0.6597   sin 0.6113 0.6129   cos 0.7913 0.7902  COR_micros= 8  FP_micros= 63
0.6912   sin 0.6389 0.6374   cos 0.7693 0.7705  COR_micros= 7  FP_micros= 63
0.7226   sin 0.6627 0.6613   cos 0.7490 0.7501  COR_micros= 7  FP_micros= 63
0.7540   sin 0.6857 0.6845   cos 0.7279 0.7290  COR_micros= 8  FP_micros= 63
0.7854   sin 0.7062 0.7071   cos 0.7081 0.7071  COR_micros= 7  FP_micros= 60
0.8168   sin 0.7279 0.7290   cos 0.6857 0.6845  COR_micros= 8  FP_micros= 92
0.8482   sin 0.7490 0.7501   cos 0.6627 0.6613  COR_micros= 8  FP_micros= 91
0.8796   sin 0.7693 0.7705   cos 0.6389 0.6374  COR_micros= 8  FP_micros= 91
0.9111   sin 0.7913 0.7902   cos 0.6113 0.6129  COR_micros= 8  FP_micros= 91
0.9425   sin 0.8100 0.8090   cos 0.5864 0.5878  COR_micros= 8  FP_micros= 91
0.9739   sin 0.8278 0.8271   cos 0.5609 0.5621  COR_micros= 8  FP_micros= 91
1.0053   sin 0.8445 0.8443   cos 0.5356 0.5358  COR_micros= 7  FP_micros= 91
1.0367   sin 0.8608 0.8607   cos 0.5089 0.5090  COR_micros= 7  FP_micros= 92
1.0681   sin 0.8763 0.8763   cos 0.4818 0.4818  COR_micros= 8  FP_micros= 92
1.0996   sin 0.8909 0.8910   cos 0.4543 0.4540  COR_micros= 8  FP_micros= 92
1.1310   sin 0.9047 0.9048   cos 0.4262 0.4258  COR_micros= 7  FP_micros= 92
1.1624   sin 0.9175 0.9178   cos 0.3978 0.3971  COR_micros= 8  FP_micros= 92
1.1938   sin 0.9294 0.9298   cos 0.3689 0.3681  COR_micros= 7  FP_micros= 92
1.2252   sin 0.9405 0.9409   cos 0.3398 0.3387  COR_micros= 8  FP_micros= 92
1.2566   sin 0.9515 0.9511   cos 0.3072 0.3090  COR_micros= 8  FP_micros= 92
1.2881   sin 0.9606 0.9603   cos 0.2775 0.2790  COR_micros= 8  FP_micros= 88
1.3195   sin 0.9689 0.9686   cos 0.2474 0.2487  COR_micros= 8  FP_micros= 88
1.3509   sin 0.9761 0.9759   cos 0.2169 0.2181  COR_micros= 8  FP_micros= 88
1.3823   sin 0.9825 0.9823   cos 0.1865 0.1874  COR_micros= 8  FP_micros= 87
1.4137   sin 0.9878 0.9877   cos 0.1557 0.1564  COR_micros= 8  FP_micros= 88
1.4451   sin 0.9921 0.9921   cos 0.1249 0.1253  COR_micros= 7  FP_micros= 88
1.4765   sin 0.9955 0.9956   cos 0.0939 0.0941  COR_micros= 8  FP_micros= 87
1.5080   sin 0.9980 0.9980   cos 0.0637 0.0628  COR_micros= 8  FP_micros= 90
1.5394   sin 0.9994 0.9995   cos 0.0326 0.0314  COR_micros= 8  FP_micros= 88
14 iterations:

Code: Select all

0.0000   sin 0.0001 0.0000   cos 0.9999 1.0000  COR_micros= 10  FP_micros= 5
0.0314   sin 0.0315 0.0314   cos 0.9994 0.9995  COR_micros= 10  FP_micros= 59
0.0628   sin 0.0630 0.0628   cos 0.9980 0.9980  COR_micros= 10  FP_micros= 59
0.0942   sin 0.0941 0.0941   cos 0.9954 0.9956  COR_micros= 10  FP_micros= 59
0.1257   sin 0.1255 0.1253   cos 0.9921 0.9921  COR_micros= 10  FP_micros= 59
0.1571   sin 0.1564 0.1564   cos 0.9877 0.9877  COR_micros= 10  FP_micros= 59
0.1885   sin 0.1876 0.1874   cos 0.9823 0.9823  COR_micros= 10  FP_micros= 59
0.2199   sin 0.2181 0.2181   cos 0.9758 0.9759  COR_micros= 10  FP_micros= 59
0.2513   sin 0.2489 0.2487   cos 0.9686 0.9686  COR_micros= 10  FP_micros= 59
0.2827   sin 0.2791 0.2790   cos 0.9602 0.9603  COR_micros= 10  FP_micros= 59
0.3142   sin 0.3093 0.3090   cos 0.9509 0.9511  COR_micros= 10  FP_micros= 63
0.3456   sin 0.3387 0.3387   cos 0.9409 0.9409  COR_micros= 10  FP_micros= 63
0.3770   sin 0.3682 0.3681   cos 0.9297 0.9298  COR_micros= 10  FP_micros= 63
0.4084   sin 0.3973 0.3971   cos 0.9177 0.9178  COR_micros= 10  FP_micros= 63
0.4398   sin 0.4259 0.4258   cos 0.9048 0.9048  COR_micros= 10  FP_micros= 63
0.4712   sin 0.4541 0.4540   cos 0.8911 0.8910  COR_micros= 10  FP_micros= 64
0.5027   sin 0.4820 0.4818   cos 0.8761 0.8763  COR_micros= 10  FP_micros= 63
0.5341   sin 0.5091 0.5090   cos 0.8607 0.8607  COR_micros= 10  FP_micros= 63
0.5655   sin 0.5361 0.5358   cos 0.8442 0.8443  COR_micros= 10  FP_micros= 64
0.5969   sin 0.5623 0.5621   cos 0.8269 0.8271  COR_micros= 10  FP_micros= 64
0.6283   sin 0.5877 0.5878   cos 0.8090 0.8090  COR_micros= 10  FP_micros= 63
0.6597   sin 0.6127 0.6129   cos 0.7903 0.7902  COR_micros= 10  FP_micros= 63
0.6912   sin 0.6375 0.6374   cos 0.7704 0.7705  COR_micros= 10  FP_micros= 63
0.7226   sin 0.6615 0.6613   cos 0.7501 0.7501  COR_micros= 10  FP_micros= 63
0.7540   sin 0.6846 0.6845   cos 0.7289 0.7290  COR_micros= 9  FP_micros= 63
0.7854   sin 0.7071 0.7071   cos 0.7072 0.7071  COR_micros= 10  FP_micros= 60
0.8168   sin 0.7290 0.7290   cos 0.6845 0.6845  COR_micros= 10  FP_micros= 91
0.8482   sin 0.7501 0.7501   cos 0.6615 0.6613  COR_micros= 10  FP_micros= 91
0.8796   sin 0.7704 0.7705   cos 0.6375 0.6374  COR_micros= 9  FP_micros= 91
0.9111   sin 0.7903 0.7902   cos 0.6127 0.6129  COR_micros= 10  FP_micros= 91
0.9425   sin 0.8090 0.8090   cos 0.5877 0.5878  COR_micros= 10  FP_micros= 92
0.9739   sin 0.8270 0.8271   cos 0.5621 0.5621  COR_micros= 10  FP_micros= 91
1.0053   sin 0.8444 0.8443   cos 0.5359 0.5358  COR_micros= 17  FP_micros= 92
1.0367   sin 0.8607 0.8607   cos 0.5091 0.5090  COR_micros= 10  FP_micros= 91
1.0681   sin 0.8765 0.8763   cos 0.4816 0.4818  COR_micros= 10  FP_micros= 92
1.0996   sin 0.8911 0.8910   cos 0.4540 0.4540  COR_micros= 10  FP_micros= 92
1.1310   sin 0.9048 0.9048   cos 0.4259 0.4258  COR_micros= 10  FP_micros= 92
1.1624   sin 0.9177 0.9178   cos 0.3972 0.3971  COR_micros= 10  FP_micros= 91
1.1938   sin 0.9298 0.9298   cos 0.3679 0.3681  COR_micros= 10  FP_micros= 92
1.2252   sin 0.9409 0.9409   cos 0.3386 0.3387  COR_micros= 10  FP_micros= 92
1.2566   sin 0.9511 0.9511   cos 0.3088 0.3090  COR_micros= 10  FP_micros= 93
1.2881   sin 0.9602 0.9603   cos 0.2789 0.2790  COR_micros= 10  FP_micros= 88
1.3195   sin 0.9686 0.9686   cos 0.2487 0.2487  COR_micros= 10  FP_micros= 88
1.3509   sin 0.9758 0.9759   cos 0.2180 0.2181  COR_micros= 10  FP_micros= 88
1.3823   sin 0.9824 0.9823   cos 0.1872 0.1874  COR_micros= 10  FP_micros= 88
1.4137   sin 0.9877 0.9877   cos 0.1563 0.1564  COR_micros= 10  FP_micros= 87
1.4451   sin 0.9921 0.9921   cos 0.1252 0.1253  COR_micros= 10  FP_micros= 88
1.4765   sin 0.9954 0.9956   cos 0.0941 0.0941  COR_micros= 11  FP_micros= 88
1.5080   sin 0.9980 0.9980   cos 0.0630 0.0628  COR_micros= 10  FP_micros= 88
1.5394   sin 0.9994 0.9995   cos 0.0314 0.0314  COR_micros= 10  FP_micros= 88
Last edited by Pito on Wed Nov 02, 2016 6:19 pm, edited 1 time in total.
Pukao Hats Cleaning Services Ltd.

User avatar
RogerClark
Posts: 7485
Joined: Mon Apr 27, 2015 10:36 am
Location: Melbourne, Australia
Contact:

Re: CORDIC - sin cos for graphics etc.

Post by RogerClark » Tue Nov 01, 2016 7:43 pm

Thanks

I am sure that will be useful for some projects in the future

User avatar
zoomx
Posts: 541
Joined: Mon Apr 27, 2015 2:28 pm
Location: Mt.Etna, Italy

Re: CORDIC - sin cos for graphics etc.

Post by zoomx » Wed Nov 02, 2016 11:49 am

I agree!

User avatar
mankan
Posts: 18
Joined: Tue Oct 13, 2015 7:57 pm

Re: CORDIC - sin cos for graphics etc.

Post by mankan » Wed Nov 02, 2016 6:14 pm

Depending on precision needed the following sequence could do: 1,2,2,3,2,2,1,-1,-2,-2,-3,-2,-2,-1. I used it once in a SW modem on PIC.
/Marcus

User avatar
Pito
Posts: 1628
Joined: Sat Mar 26, 2016 3:26 pm
Location: Rapa Nui

Re: CORDIC - sin cos for graphics etc.

Post by Pito » Wed Nov 02, 2016 6:23 pm

BTW I did above CORDIC on Xilinx Spartan6 and it returned 5digits precise sin() and cos() in 200ns (no overclocking) :)
Depending on precision needed the following sequence could do: 1,2,2,3,2,2,1,-1,-2,-2,-3,-2,-2,-1. I used it once in a SW modem on PIC.
It could be done with an 1,0,1,0 sequence and a simple RC low pass filter too :P
Pukao Hats Cleaning Services Ltd.

viki2000
Posts: 3
Joined: Tue Jun 13, 2017 9:07 pm

Re: CORDIC - sin cos for graphics etc.

Post by viki2000 » Tue Jun 13, 2017 9:16 pm

Could you please show the full working code which you used to print the results with 10 or 14 iterations?
The code above does not have “M_PI” constant declared as in original “#define M_PI 3.1415926535897932384626” and the constant “half_pi” is not used “#define half_pi 0x00006487”.
I have tried to implement it on PIC24 16bit MCU, running at 80MHz.
I get some errors on the cordic subroutine, where sin and cos are calculated:
https://goo.gl/wnrIez

Here is my code written for CCS C compiler:

Code: Select all

#include <24HJ64GP202.h>
#use delay(internal=80MHz)

#FUSES FRC_PLL
#FUSES NOWDT                    //No Watch Dog Timer
#FUSES NOWRTB                   //Boot block not write protected
#FUSES NOBSS                    //No boot segment
#FUSES NORBS                    //No Boot RAM defined
#FUSES NOWRTSS                  //Secure segment not write protected
#FUSES NOSSS                    //No secure segment
#FUSES NORSS                    //No secure segment RAM
#FUSES NOWRT                    //Program memory not write protected
#FUSES NOPROTECT                //Code not protected from reading
#FUSES IESO                     //Internal External Switch Over mode enabled
#FUSES NOOSCIO                  //OSC2 is clock output
#FUSES IOL1WAY                  //Allows only one reconfiguration of peripheral pins
#FUSES CKSFSM                   //Clock Switching is enabled, fail Safe clock monitor is enabled
#FUSES WINDIS                   //Watch Dog Timer in non-Window mode
#FUSES PUT128                   //Power On Reset Timer value 128ms
#FUSES NOALTI2C1                //I2C1 mapped to SDA1/SCL1 pins
#FUSES NOJTAG                   //JTAG disabled

#pin_select U1TX=PIN_B6
#pin_select U1RX=PIN_B7
#use rs232(UART1, BAUD=115200, ERRORS)

// CORDIC based SIN and COS in 16 bit signed fixed point math
// Based on http://www.dcs.gla.ac.uk/~jhw/cordic/
// Function is valid for arguments in range -pi/2 -- pi/2
// For values pi/2--pi: value = half_pi-(theta-half_pi) and similarly for values -pi---pi/2
//
// 1.0 = 16384
// 1/k = 0.6072529350088812561694
// pi = 3.1415926536897932384626
// Some useful Constants

#define M_PI 3.1415926535897932384626
#define cordic_1K 0x26DD //=9949=16384*0.60726, 0.60726 is "cordic gain"
// cordic gain: COS(45)*COS(26.565)*COS(14.036)*COS(7.125)*COS(3.576)*COS(1.790)*COS(0.895)*COS(0.448) = 0.60726
#define half_pi 0x6487 //=25735=16384*(M_PI/2), PI/2 is 90°...25735=0x6487
#define MUL 16384.0
#define CORDIC_NTAB 16 //Maximum Cordic iterations
       
int s, c;
// 45°...12867=0x3243, 26.565°...7596=0x1DAC, 14.036°, 7.125°, 3.576°, 1.790°,
// 0.895°, 0.448°, 0.224°, 0.112°, 0.056°, 0.028°, 0.014°, 0.007°, 0.003°
// tan(45°)=1, tan(26.565°)=0.5, tan(14.036°)=0.25, tan(7.125°)=0.125...
int cordic_ctab [16] = {0x00003243, 0x00001DAC, 0x00000FAD, 0x000007F5, 0x000003FE,
    0x000001FF, 0x000000FF, 0x0000007F, 0x0000003F, 0x0000001F, 0x0000000F, 0x00000007,
    0x00000003, 0x00000001, 0x00000000, 0x00000000};
   
void cordic(int theta, int *s, int *c, int n);

void main(){
     float p, p1;
     int i;

   while(TRUE)
   {
        for(i=0; i<1000; i=i+1){
            p = (i/1000.0)*M_PI/2;
            p1=p*MUL;             
            cordic(p1, &s, &c, 14); // 14 Cordic iterations
 
            //Send to serial port
            putc(make8(s,1)); //MSB                 
            putc(make8(s,0)); //LSB
            //delay_ms(100);
        }
   }
}

void cordic(int theta, int *s, int *c, int n){
  int k, d, tx, ty, tz;
  int x=cordic_1K,y=0,z=theta;
  n = (n>CORDIC_NTAB) ? CORDIC_NTAB : n;
  for (k=0; k<n; ++k)
  {
    //d = z>>15;
    //get sign. for other architectures, you might want to use the more portable version
    d = z>=0 ? 0 : -1;
    tx = x - (((y>>k) ^ d) - d);
    ty = y + (((x>>k) ^ d) - d);
    tz = z - ((cordic_ctab[k] ^ d) - d);
    x = tx; y = ty; z = tz;
  }
 *c = x; *s = y;
}

dannyf
Posts: 167
Joined: Wed May 11, 2016 4:29 pm

Re: CORDIC - sin cos for graphics etc.

Post by dannyf » Thu Jun 15, 2017 1:39 am

50 cordic calculations, 10 iterations each:

on a lowly pic24fj64ga002:
16bit: 125k ticks (1tick = 1 instruction cycle);
32bit: 178k
float: 294k

on a lowly stm32f100:
16bit: 101k
32bit: 93k
float: 223k

only if Microchip had done a better job marketing pic24...

viki2000
Posts: 3
Joined: Tue Jun 13, 2017 9:07 pm

Re: CORDIC - sin cos for graphics etc.

Post by viki2000 » Thu Jun 15, 2017 11:54 am

The problem was found with the help from the experts in another forum.
In the CCS C code the “>>” symbol was interpreted as logical shift instead of arithmetical shift.
Microchip gives next explanations for their XC compilers:
http://microchipdeveloper.com/tls2101:shift-operators
But the code was written and tested for CCS C compiler, so a workaround had to be done by writing an additional subroutine:

Code: Select all

#inline 
signed int16 math_shift(signed int16 x, signed int16 y) 
{ //Perform a mathematical right shift on a signed value 
   if (bit_test(x,15)) //if -ve 
      return -(-x>>y); //convert sign, shift, and convert back 
   return x>>y; //otherwise simple shift 
}
By replacing “>>” with “math_shift (x, y)” solved the problem.

dannyf
Posts: 167
Joined: Wed May 11, 2016 4:29 pm

Re: CORDIC - sin cos for graphics etc.

Post by dannyf » Thu Jun 15, 2017 7:14 pm

In the CCS C code the “>>” symbol was interpreted as logical shift instead of arithmetical shift.
That's the risk you take for using non c-complaint c compilers.

Btw, the fix can be made simpler by testing and flipping the most significant bit.

viki2000
Posts: 3
Joined: Tue Jun 13, 2017 9:07 pm

Re: CORDIC - sin cos for graphics etc.

Post by viki2000 » Thu Jun 15, 2017 7:30 pm

the fix can be made simpler by testing and flipping the most significant bit.
Can you provide a code for such arithmetic shift right?
I know only this other approach: http://www.microchip.com/forums/m98041.aspx , which is not simpler than first solution.

Post Reply