Circular Buffer Pointer Addition and Subtraction
This tutorial is to teach you how to add and subtract a value to a pointer value in a circular buffer without going over the size, or below 0, so that it loops back around. The goal is to do this without using any loops, negative numbers, or if statements. We just want a generic mathematical formula that can be used. We also want one formula that does both addition or subtraction depending on if you pass a positive or negative number.
Circular Buffer
As an example we will use one with a size of 8 (0-7). Lets call it var[buffersize] buffersize=7 Size=buffersize+1.
| 7 |
| 6 |
| 5 |
| 4 |
| 3 |
| 2 |
| 1 |
| 0 |
Now to add or subtract to this we need to know a few things the size (S), the current pointer location (P), and the value we are adding or subtracting(X) and we will call the new value N.
We can't just say N=P-X or N=P+X. It works in some cases but in others it causes the value to exceed 7 or drop below 0, and we can't have that. We could use if statements and loops but that is slow.
If you want you can try to solve it yourself then check back and see if we came up with the same formula. If you come up with a better solution, let me know in the comments. Just remember, no negative numbers, 'if' statements, loops, and it must be compatible in across programming languages.
Here are some example values and their solutions:
S=8, P=5, and X=1
We know that 5+1=6 and 5-1=4. It stays inside the boundaries so it is ok.
Now lets try S=8, P=5, X=15. Now we have a problem, if you add 15 to 5 you exceed 7 and if you subtract 15 from 5 you drop below 0. This is bad, we want it to loop around. Count the tiles and loop back, you will find that adding you get 4 and subtracting you get 6.
So we are going to make one formula for addition, which is fairly easy to do, then another for subtraction which is not so easy.
Addition
I came up with N=(P+X)%S
Lets test it out on the previous examples.
1.S=8, P=5, and X=1
(5+1)%8=6%8=6.
2.S=8, P=5, X=15
(5+15)%8=20%8=4
The answers match up with what we found counting. Awesome, now for subtraction which is a little more tricky because we don't want to deal with any negative numbers.
Subtraction
Language Differences
So you may say alright subtraction must be N=(P-X)%S. Lets look at why N=(P-X)%S does not work in C based languages.
To understand this we have to understand the difference between "%" in C and "%" in other languages.
In C "%" is a remainder operator. The remainder will share the same sign as the division solution.
In other languages "%" is a modulo operator and will always give a positive result.
This causes -2%8 to either equal 2 or -6 depending on which language you are using.
You may notice that to get the correct answer with C, you just need to add that answer to the size and you will also get 2.
Solution
The formula I came up with is N=(S-(X%S)+P)%S
So lets test it out on those examples again.
1.S=8, P=5, and X=1
(8-(1%8)+P)%8=(8-1+5)%8=12%8=4
So far so good! Now to test one of cases that causes all the trouble.
2.S=8, P=5, X=15
(8-(15%8)+5)%8=(8-7+5)%8=6%8=6
It works! This should speed up your code if you have been using if statements or something like that previously.
Universal Formula
So if you want a formula that does both addition and subtraction so you can just pass a positive or negative value to a function.
((s*x*x)+(p + x)) % s
Formula List
S=buffer size, X=value being added (negative for subtraction), and P= the current pointer position.
Addition
N=(P+X)%S
Subtraction
Non C Languages Only:
N=(P+X)%S
C Languages Only:
N=(S+(P-X))%S
All Languages (Don't quote me on that, test to make sure)
N=(S-(X%S)+P)%S
Or if you prefer you can write it like this:
N=((S+P)-(X%S))%S
Universal, Addition and Subtraction
((s*x*x)+(p + x)) % s
Lets test it out with a sample program. I wrote this in c++ as a windows console app in visual studio.
In this program the value for each pointer is the same as the pointer. For example var[6]=6, var[5]=5. This is just to demonstrate that it is working correctly.
So here it is with the different equations
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
const int buffersize = 7;
int var[buffersize];
int p;
int s;
int quit;
void setup();
void loop();
void add(int x);
void sub(int x);
int _tmain(int argc, _TCHAR* argv[])
{
while (1)
{
setup();//this gives each pointer the same value as its address. We will print it later.
loop();//test a bunch of values being added or subtracted to each pointer.
cout << "Enter \"0\" to quit:";
cin >> quit;
if (quit == 0)
{
return 0;
}
}
}
void setup()
{
s = buffersize + 1;
for (int i = 0; i < 7; i++)
{
var[i] = i;
}
}
void loop()
{
for (int i = 0; i < 7; i++)
{
p = i;
for (int j = 0; j < 21; j++)
{
add(j);
sub(j);
}
}
}
void add(int x)
{
cout << p << "+" << x << "=" <<(p + x) % s<<endl;
}
void sub(int x)
{
cout << p << "-" << x << "=" << (s - (x%s) + p) % s<<endl;
}
And here is the output
0+0=0
0-0=0
0+1=1
0-1=7
0+2=2
0-2=6
0+3=3
0-3=5
0+4=4
0-4=4
0+5=5
0-5=3
0+6=6
0-6=2
0+7=7
0-7=1
0+8=0
0-8=0
0+9=1
0-9=7
0+10=2
0-10=6
0+11=3
0-11=5
0+12=4
0-12=4
0+13=5
0-13=3
0+14=6
0-14=2
0+15=7
0-15=1
0+16=0
0-16=0
0+17=1
0-17=7
0+18=2
0-18=6
0+19=3
0-19=5
0+20=4
0-20=4
1+0=1
1-0=1
1+1=2
1-1=0
1+2=3
1-2=7
1+3=4
1-3=6
1+4=5
1-4=5
1+5=6
1-5=4
1+6=7
1-6=3
1+7=0
1-7=2
1+8=1
1-8=1
1+9=2
1-9=0
1+10=3
1-10=7
1+11=4
1-11=6
1+12=5
1-12=5
1+13=6
1-13=4
1+14=7
1-14=3
1+15=0
1-15=2
1+16=1
1-16=1
1+17=2
1-17=0
1+18=3
1-18=7
1+19=4
1-19=6
1+20=5
1-20=5
2+0=2
2-0=2
2+1=3
2-1=1
2+2=4
2-2=0
2+3=5
2-3=7
2+4=6
2-4=6
2+5=7
2-5=5
2+6=0
2-6=4
2+7=1
2-7=3
2+8=2
2-8=2
2+9=3
2-9=1
2+10=4
2-10=0
2+11=5
2-11=7
2+12=6
2-12=6
2+13=7
2-13=5
2+14=0
2-14=4
2+15=1
2-15=3
2+16=2
2-16=2
2+17=3
2-17=1
2+18=4
2-18=0
2+19=5
2-19=7
2+20=6
2-20=6
3+0=3
3-0=3
3+1=4
3-1=2
3+2=5
3-2=1
3+3=6
3-3=0
3+4=7
3-4=7
3+5=0
3-5=6
3+6=1
3-6=5
3+7=2
3-7=4
3+8=3
3-8=3
3+9=4
3-9=2
3+10=5
3-10=1
3+11=6
3-11=0
3+12=7
3-12=7
3+13=0
3-13=6
3+14=1
3-14=5
3+15=2
3-15=4
3+16=3
3-16=3
3+17=4
3-17=2
3+18=5
3-18=1
3+19=6
3-19=0
3+20=7
3-20=7
4+0=4
4-0=4
4+1=5
4-1=3
4+2=6
4-2=2
4+3=7
4-3=1
4+4=0
4-4=0
4+5=1
4-5=7
4+6=2
4-6=6
4+7=3
4-7=5
4+8=4
4-8=4
4+9=5
4-9=3
4+10=6
4-10=2
4+11=7
4-11=1
4+12=0
4-12=0
4+13=1
4-13=7
4+14=2
4-14=6
4+15=3
4-15=5
4+16=4
4-16=4
4+17=5
4-17=3
4+18=6
4-18=2
4+19=7
4-19=1
4+20=0
4-20=0
5+0=5
5-0=5
5+1=6
5-1=4
5+2=7
5-2=3
5+3=0
5-3=2
5+4=1
5-4=1
5+5=2
5-5=0
5+6=3
5-6=7
5+7=4
5-7=6
5+8=5
5-8=5
5+9=6
5-9=4
5+10=7
5-10=3
5+11=0
5-11=2
5+12=1
5-12=1
5+13=2
5-13=0
5+14=3
5-14=7
5+15=4
5-15=6
5+16=5
5-16=5
5+17=6
5-17=4
5+18=7
5-18=3
5+19=0
5-19=2
5+20=1
5-20=1
6+0=6
6-0=6
6+1=7
6-1=5
6+2=0
6-2=4
6+3=1
6-3=3
6+4=2
6-4=2
6+5=3
6-5=1
6+6=4
6-6=0
6+7=5
6-7=7
6+8=6
6-8=6
6+9=7
6-9=5
6+10=0
6-10=4
6+11=1
6-11=3
6+12=2
6-12=2
6+13=3
6-13=1
6+14=4
6-14=0
6+15=5
6-15=7
6+16=6
6-16=6
6+17=7
6-17=5
6+18=0
6-18=4
6+19=1
6-19=3
6+20=2
6-20=2
Enter "0" to quit:And here it is with the universal formula
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;
const int buffersize = 7;
int var[buffersize];
int p;
int s;
int quit;
void setup();
void loop();
void add(int x);
void sub(int x);
int _tmain(int argc, _TCHAR* argv[])
{
while (1)
{
setup();//this gives each pointer the same value as its address. We will print it later.
loop();//test a bunch of values being added or subtracted to each pointer.
cout << "Enter \"0\" to quit:";
cin >> quit;
if (quit == 0)
{
return 0;
}
}
}
void setup()
{
s = buffersize + 1;
for (int i = 0; i < 7; i++)
{
var[i] = i;
}
}
void loop()
{
for (int i = 0; i < 7; i++)
{
p = i;
for (int j = 0; j < 20; j++)
{
add(j);
sub(j);
}
}
}
void add(int x)
{
cout << "Add" << s << " Pointer:" << p << "+" << x << "=" << ((s*x*x) + (p + x)) % s << endl;
}
void sub(int x)
{
x = x*-1;
//cout <<"correct"<< p << "-" << x << "=" << (s - (x%s) + p) % s<<endl;
//cout << "Buffer Size:" << s << " Pointer:" << p << "-" << x << "=" << ((s*x) + (p - x)) % s << endl;
//cout << "Test" << s << " Pointer:" << p << "-" << x << "=" << ((s + p) - (x%s)) % s << endl;
cout << "Sub" << s << " Pointer:" << p << "-" << x << "=" << ((s*x*x)+(p + x)) % s <<endl;
}
Add8 Pointer:0+0=0
Sub8 Pointer:00=0
Add8 Pointer:0+1=1
Sub8 Pointer:0-1=7
Add8 Pointer:0+2=2
Sub8 Pointer:0-2=6
Add8 Pointer:0+3=3
Sub8 Pointer:0-3=5
Add8 Pointer:0+4=4
Sub8 Pointer:0-4=4
Add8 Pointer:0+5=5
Sub8 Pointer:0-5=3
Add8 Pointer:0+6=6
Sub8 Pointer:0-6=2
Add8 Pointer:0+7=7
Sub8 Pointer:0-7=1
Add8 Pointer:0+8=0
Sub8 Pointer:0-8=0
Add8 Pointer:0+9=1
Sub8 Pointer:0-9=7
Add8 Pointer:0+10=2
Sub8 Pointer:0-10=6
Add8 Pointer:0+11=3
Sub8 Pointer:0-11=5
Add8 Pointer:0+12=4
Sub8 Pointer:0-12=4
Add8 Pointer:0+13=5
Sub8 Pointer:0-13=3
Add8 Pointer:0+14=6
Sub8 Pointer:0-14=2
Add8 Pointer:0+15=7
Sub8 Pointer:0-15=1
Add8 Pointer:0+16=0
Sub8 Pointer:0-16=0
Add8 Pointer:0+17=1
Sub8 Pointer:0-17=7
Add8 Pointer:0+18=2
Sub8 Pointer:0-18=6
Add8 Pointer:0+19=3
Sub8 Pointer:0-19=5
Add8 Pointer:1+0=1
Sub8 Pointer:10=1
Add8 Pointer:1+1=2
Sub8 Pointer:1-1=0
Add8 Pointer:1+2=3
Sub8 Pointer:1-2=7
Add8 Pointer:1+3=4
Sub8 Pointer:1-3=6
Add8 Pointer:1+4=5
Sub8 Pointer:1-4=5
Add8 Pointer:1+5=6
Sub8 Pointer:1-5=4
Add8 Pointer:1+6=7
Sub8 Pointer:1-6=3
Add8 Pointer:1+7=0
Sub8 Pointer:1-7=2
Add8 Pointer:1+8=1
Sub8 Pointer:1-8=1
Add8 Pointer:1+9=2
Sub8 Pointer:1-9=0
Add8 Pointer:1+10=3
Sub8 Pointer:1-10=7
Add8 Pointer:1+11=4
Sub8 Pointer:1-11=6
Add8 Pointer:1+12=5
Sub8 Pointer:1-12=5
Add8 Pointer:1+13=6
Sub8 Pointer:1-13=4
Add8 Pointer:1+14=7
Sub8 Pointer:1-14=3
Add8 Pointer:1+15=0
Sub8 Pointer:1-15=2
Add8 Pointer:1+16=1
Sub8 Pointer:1-16=1
Add8 Pointer:1+17=2
Sub8 Pointer:1-17=0
Add8 Pointer:1+18=3
Sub8 Pointer:1-18=7
Add8 Pointer:1+19=4
Sub8 Pointer:1-19=6
Add8 Pointer:2+0=2
Sub8 Pointer:20=2
Add8 Pointer:2+1=3
Sub8 Pointer:2-1=1
Add8 Pointer:2+2=4
Sub8 Pointer:2-2=0
Add8 Pointer:2+3=5
Sub8 Pointer:2-3=7
Add8 Pointer:2+4=6
Sub8 Pointer:2-4=6
Add8 Pointer:2+5=7
Sub8 Pointer:2-5=5
Add8 Pointer:2+6=0
Sub8 Pointer:2-6=4
Add8 Pointer:2+7=1
Sub8 Pointer:2-7=3
Add8 Pointer:2+8=2
Sub8 Pointer:2-8=2
Add8 Pointer:2+9=3
Sub8 Pointer:2-9=1
Add8 Pointer:2+10=4
Sub8 Pointer:2-10=0
Add8 Pointer:2+11=5
Sub8 Pointer:2-11=7
Add8 Pointer:2+12=6
Sub8 Pointer:2-12=6
Add8 Pointer:2+13=7
Sub8 Pointer:2-13=5
Add8 Pointer:2+14=0
Sub8 Pointer:2-14=4
Add8 Pointer:2+15=1
Sub8 Pointer:2-15=3
Add8 Pointer:2+16=2
Sub8 Pointer:2-16=2
Add8 Pointer:2+17=3
Sub8 Pointer:2-17=1
Add8 Pointer:2+18=4
Sub8 Pointer:2-18=0
Add8 Pointer:2+19=5
Sub8 Pointer:2-19=7
Add8 Pointer:3+0=3
Sub8 Pointer:30=3
Add8 Pointer:3+1=4
Sub8 Pointer:3-1=2
Add8 Pointer:3+2=5
Sub8 Pointer:3-2=1
Add8 Pointer:3+3=6
Sub8 Pointer:3-3=0
Add8 Pointer:3+4=7
Sub8 Pointer:3-4=7
Add8 Pointer:3+5=0
Sub8 Pointer:3-5=6
Add8 Pointer:3+6=1
Sub8 Pointer:3-6=5
Add8 Pointer:3+7=2
Sub8 Pointer:3-7=4
Add8 Pointer:3+8=3
Sub8 Pointer:3-8=3
Add8 Pointer:3+9=4
Sub8 Pointer:3-9=2
Add8 Pointer:3+10=5
Sub8 Pointer:3-10=1
Add8 Pointer:3+11=6
Sub8 Pointer:3-11=0
Add8 Pointer:3+12=7
Sub8 Pointer:3-12=7
Add8 Pointer:3+13=0
Sub8 Pointer:3-13=6
Add8 Pointer:3+14=1
Sub8 Pointer:3-14=5
Add8 Pointer:3+15=2
Sub8 Pointer:3-15=4
Add8 Pointer:3+16=3
Sub8 Pointer:3-16=3
Add8 Pointer:3+17=4
Sub8 Pointer:3-17=2
Add8 Pointer:3+18=5
Sub8 Pointer:3-18=1
Add8 Pointer:3+19=6
Sub8 Pointer:3-19=0
Add8 Pointer:4+0=4
Sub8 Pointer:40=4
Add8 Pointer:4+1=5
Sub8 Pointer:4-1=3
Add8 Pointer:4+2=6
Sub8 Pointer:4-2=2
Add8 Pointer:4+3=7
Sub8 Pointer:4-3=1
Add8 Pointer:4+4=0
Sub8 Pointer:4-4=0
Add8 Pointer:4+5=1
Sub8 Pointer:4-5=7
Add8 Pointer:4+6=2
Sub8 Pointer:4-6=6
Add8 Pointer:4+7=3
Sub8 Pointer:4-7=5
Add8 Pointer:4+8=4
Sub8 Pointer:4-8=4
Add8 Pointer:4+9=5
Sub8 Pointer:4-9=3
Add8 Pointer:4+10=6
Sub8 Pointer:4-10=2
Add8 Pointer:4+11=7
Sub8 Pointer:4-11=1
Add8 Pointer:4+12=0
Sub8 Pointer:4-12=0
Add8 Pointer:4+13=1
Sub8 Pointer:4-13=7
Add8 Pointer:4+14=2
Sub8 Pointer:4-14=6
Add8 Pointer:4+15=3
Sub8 Pointer:4-15=5
Add8 Pointer:4+16=4
Sub8 Pointer:4-16=4
Add8 Pointer:4+17=5
Sub8 Pointer:4-17=3
Add8 Pointer:4+18=6
Sub8 Pointer:4-18=2
Add8 Pointer:4+19=7
Sub8 Pointer:4-19=1
Add8 Pointer:5+0=5
Sub8 Pointer:50=5
Add8 Pointer:5+1=6
Sub8 Pointer:5-1=4
Add8 Pointer:5+2=7
Sub8 Pointer:5-2=3
Add8 Pointer:5+3=0
Sub8 Pointer:5-3=2
Add8 Pointer:5+4=1
Sub8 Pointer:5-4=1
Add8 Pointer:5+5=2
Sub8 Pointer:5-5=0
Add8 Pointer:5+6=3
Sub8 Pointer:5-6=7
Add8 Pointer:5+7=4
Sub8 Pointer:5-7=6
Add8 Pointer:5+8=5
Sub8 Pointer:5-8=5
Add8 Pointer:5+9=6
Sub8 Pointer:5-9=4
Add8 Pointer:5+10=7
Sub8 Pointer:5-10=3
Add8 Pointer:5+11=0
Sub8 Pointer:5-11=2
Add8 Pointer:5+12=1
Sub8 Pointer:5-12=1
Add8 Pointer:5+13=2
Sub8 Pointer:5-13=0
Add8 Pointer:5+14=3
Sub8 Pointer:5-14=7
Add8 Pointer:5+15=4
Sub8 Pointer:5-15=6
Add8 Pointer:5+16=5
Sub8 Pointer:5-16=5
Add8 Pointer:5+17=6
Sub8 Pointer:5-17=4
Add8 Pointer:5+18=7
Sub8 Pointer:5-18=3
Add8 Pointer:5+19=0
Sub8 Pointer:5-19=2
Add8 Pointer:6+0=6
Sub8 Pointer:60=6
Add8 Pointer:6+1=7
Sub8 Pointer:6-1=5
Add8 Pointer:6+2=0
Sub8 Pointer:6-2=4
Add8 Pointer:6+3=1
Sub8 Pointer:6-3=3
Add8 Pointer:6+4=2
Sub8 Pointer:6-4=2
Add8 Pointer:6+5=3
Sub8 Pointer:6-5=1
Add8 Pointer:6+6=4
Sub8 Pointer:6-6=0
Add8 Pointer:6+7=5
Sub8 Pointer:6-7=7
Add8 Pointer:6+8=6
Sub8 Pointer:6-8=6
Add8 Pointer:6+9=7
Sub8 Pointer:6-9=5
Add8 Pointer:6+10=0
Sub8 Pointer:6-10=4
Add8 Pointer:6+11=1
Sub8 Pointer:6-11=3
Add8 Pointer:6+12=2
Sub8 Pointer:6-12=2
Add8 Pointer:6+13=3
Sub8 Pointer:6-13=1
Add8 Pointer:6+14=4
Sub8 Pointer:6-14=0
Add8 Pointer:6+15=5
Sub8 Pointer:6-15=7
Add8 Pointer:6+16=6
Sub8 Pointer:6-16=6
Add8 Pointer:6+17=7
Sub8 Pointer:6-17=5
Add8 Pointer:6+18=0
Sub8 Pointer:6-18=4
Add8 Pointer:6+19=1
Sub8 Pointer:6-19=3
Enter "0" to quit:Alright, if you can think of a better formula that adds or subtracts a pointer value in a circular buffer let me know.