How’s it made?

The guts

This project has the following components:

• 1 wooden cigar box from a hobby shop ($7)
• 1 clone Arduino Mega from Amazon ($9)
• 4 faders and 8 pots from digikey ($18)
• 1 1602A LCD from Amazon ($8)
• 1 rotary knob with pushbutton from Amazon ($3)
• 4 LEDs in different colors (freeee – I have a bunch already)
• 1 SPDT switch from Amazon ($1)
• 1 hot glue gun and hot glue sticks from hobby shop ($15)

Manufacturing

I first drew out a few templates on graph paper of what I wanted the end product to look like. Then I took each variation and taped it to the box’s top and tried to visualize using it in that form factor. Once I had decided on the way it was to be laid out, I went to the shop.
I taped over (with clear tape) where I would cut and drill so the layout template wouldn’t tear off, then I used a drill press to put holes in the right places and the jigsaw to my the slots and the LCD hole.

The Assembly

The first parts I put in were the faders. I used Gorilla Glue to tack them in position, and I let them cure for about 2 days. Then I put in all the other pots, switches, and hot-glued the LCD in place. Finally I put in the LEDs and hot-glued them in place.

Here’s a picture before all the hardware was in:

MIDI Control Surface w/ Some Components

I used solid core wire and high quality solder to build the wiring harness. The last step in assembly was to cut a slot for the USB cable go through the side of the box and wire up the microcontroller.

The uC

I used the Arduino Mega form factor, but did not use the IDE. The code I used was AVR-libc based and was an extension of the littleKernel project I had been working on. I eventually added the optiboot bootloader so I didn’t need to pull the Mega from the box to update the code. I’ll get around to putting the code up eventually (probably).

What does it do?

Here, a feature list makes sense:

• MIDI TX and RX lights
• Power good light
• Debug light (always good to have)
• Reset switch
• 12 control surfaces which can be independently mapped to different MIDI channels and Change Control numbers
• LCD and scroll knob user interface for setting up the aforementioned options
• A settings Save and Recall function using the uC EEPROM
• A settings Dump and Load function using the serial interface

All in all, this was a really fun project. Perhaps I’ll put up a demo of me using it with a DAW…
Anyhow, here are the pics of the final product and an early prototype for reference! Thanks for reading!

The post Presenting…. The MIDI Control Surface (Rev. A) appeared first on Jacob N Calvert.

Introducing littleKernel

As the name implies, it is a little kernel. I’ve built this little multitasking kernel for a project I’ve got in mind down the road. For now though, I’m going to learn as much as I can about multitasking while improving my own littleKernel project.

The project down the road

I love to make music. Whether it be from a physical instrument, digital instrument, or a combination — I love doing it. I’ve built the hardware for a 12 channel MIDI control surface. I built a 4 channel prototype earlier this year, but wanted to do a bigger, more multi-functional version of that. I’ll post pics later on, but this project is the primary reason for home-rolling a multitasking kernel for a microcontroller.
Until next time…

The post I’ve been busy working, but I’ve started a side project appeared first on Jacob N Calvert.

malloc

in C or

 new SomeClass()

in C++. I’m almost finished with a memory manager in C so hopefully I can get a self-hosted system soon.
Alternatively, when I’m not doing OS development, I’m improving my Java multithreading and network programming skills. I recently wrote a library for “hooking up” multiple services via multicast and being able to pass around messages in a bus-like fashion. It’s very rudimentary but it was helpful in learning Java threading and networking. I’ll post the source up here when it’s more mature.
Thanks for reading and have a Happy Independence Day!

The post July Update appeared first on Jacob N Calvert.

These structures are mostly being built in a linked list style with the exception of the List struct which is built on an array that will auto-resize. You might ask, “why are you doing this, when there are already templated vectors and maps and such in the STL?” Mainly because I can!! I enjoy these things, and I wanted to try my hand at some of the most commonly used structures, but also I wanted to make them template based so that they are generic enough to be reusable in my other projects.
Currently, I have the following structures done:

• List
• Queue
• Stack

And the following are planned:

• Heap
• Red-Black Tree
• Binary Search Tree
• Others???

I’ll keep adding to them hopefully until I have a whole set of generic data structures to use. If you’re interested in the code or usage, hop over to my GitHub account to see the project code and some examples. I hope to keep adding useful examples to the repository little by little. Thanks for reading!!

The post Generic Data Structures appeared first on Jacob N Calvert.

But to multiply really big numbers, we represent the two multiplicands as polynomials where each term is in the form cxⁿ, where x is the base in the number system, c is its coefficent modifier and n is the power to which the base is modified. For example, we can represent 4587 as 4x³ + 5x² + 8x¹ + 7x⁰, where x = 10.
Now, two numbers in this polynomial base representation can be multiplied to give the result. Here’s a small example:

321 = 3*10^2 + 2*10^1 + 1*10^0 ==> 3x^2 + 2x + 1

123 = 1*10^2 + 2*10^1 + 3*10^0 ==> 1x^2 + 2x + 3

321 * 123 = (3x^2 + 2x + 1)*(1x^2 + 2x + 3) = 3x^4 + 6x^3 + 9x^2 + 2x^3 + 4x^2 + 6x + x^2 +2x + 3 
= 3x^4 + 8x^3 + 14x^2 + 8x + 3

Now plugging in x = 10 ==>  3(10)^4 + 8(10)^3 + 14(10)^2 + 8(10) + 3 = 39483

Now verify with a calculator that 123*321 = 39483

Cool, huh?

We can use this knowledge to multiply some really, really big numbers. Since we have a way to calculate them product using polynomials, the question now is this: how do we multiply these polynomials when the order is large (like order-50 or order-n)? This is where the Toom-k algorithm becomes helpful.
First, let’s represent the polynomials as arrays where the position i indicates the power and the value at i represents the coefficient.

3x^2 + 2x + 1

will be represented as

[1, 2, 3]

Toom-k states that we can divide the polynomial array into sub-arrays of length (n/k) and perform (2*k)-1 recursive calls on those sub-arrays, then recombine them in O(n) time, and have a solution. For this article I want to focus on Toom-3, or otherwise called the Toom-Cook algorithm. To simplfiy the algorithm, we’ll require the length of our input arrays to be divisible by 3. Call the two input polynomials P and Q. P and Q get partitioned into n/3 or otherwise stated, they are divided into thirds. Call these sub-arrays A, B, C, D, E, and F where these are each of size n/3. Create 5 more arrays of size n/3 called G, H, J, L, M. Their values are as follows:
G = A+C, H = D+F, J = G-B, K = H-E, L = 2(J+A)-C, M = 2(K+D)-F
Here comes some serious math.
In this method of representing polynomials as arrays, an order-n polynomial takes up an array of length (n+1). Like in our previous example:

3x^2 + 2x + 1 is order-2

so n = 2, but its array representation takes up (n+1) = 3 length

[1, 2, 3]

Since this is known, then we can determine that multiplying two polynomials together of any order-n will generate in our system of representation an array of length (2*n)-1.
Ok, back to the Toom-3. We now create 5 more arrays of length (2*n)-1 named R, S, T, U, V. They are defined as R = AD, S = CF, T = (G+B)(H+E), U = JK, V = LM.
One more set of arrays of length (2*n/3)-1 named W, X, Y, Z and are defined as W = (V-T)/3, X = (T-U)/2, Y = U-S, Z = (Y-W)/2 + 2R.
Now we need to recombine these arrays into the final solution form. The product P*Q is defined as follows:
P*Q = Rx^(4n/3) + Zx^n + (X+Y-R)x^(2n/3) + (X-Z)x^(n/3) + S
This formula can look confusing, but it makes sense with some code to go with it:

BigInt* make_array(BigInt size)
{
	BigInt*res = new BigInt[size];
	for(BigInt i = 0; i < size; i ++)
	{
		res[i] = 0;
	}
	return res;
}
BigInt* Toom3(BigInt* P, BigInt*Q, BigInt n)
{
	BigInt pq_size = (2*n) -1 ;
	BigInt *PQ_Res = make_array(pq_size);
	BigInt sub_eq_size = n/3;
	BigInt *A = new BigInt[sub_eq_size], *B =new BigInt[sub_eq_size], *C=new BigInt[sub_eq_size], *D=new BigInt[sub_eq_size], *E=new BigInt[sub_eq_size], *F=new BigInt[sub_eq_size];
	memcpy(C,&P[0], sizeof(BigInt) * sub_eq_size);
	memcpy(B,&P[sub_eq_size], sizeof(BigInt) * sub_eq_size);
	memcpy(A,&P[sub_eq_size*2], sizeof(BigInt) * sub_eq_size);
	memcpy(F,&Q[0], sizeof(BigInt) * sub_eq_size);
	memcpy(E,&Q[sub_eq_size], sizeof(BigInt) * sub_eq_size);
	memcpy(D,&Q[sub_eq_size*2], sizeof(BigInt) * sub_eq_size);

	BigInt *G = new BigInt[sub_eq_size], *H =new BigInt[sub_eq_size], *J =new BigInt[sub_eq_size], *K =new BigInt[sub_eq_size], *L =new BigInt[sub_eq_size],*M =new BigInt[sub_eq_size];
	BigInt* GpB=new BigInt[sub_eq_size], *HpE=new BigInt[sub_eq_size];
	for(BigInt i = 0; i < sub_eq_size; i++)
	{
		G[i] = A[i] + C[i];
		H[i] = D[i] + F[i];
		J[i] = G[i] - B[i];
		K[i] = H[i] - E[i];
		L[i] = (2* (J[i] + A[i])) - C[i];
		M[i] = (2* (K[i] + D[i])) - F[i];
		GpB[i] = G[i] + B[i];
		HpE[i] = H[i] + E[i];
	}
	BigInt *R, *S, *T, *U, *V; //finally!
	R = mult(A, D, sub_eq_size, sub_eq_size);
	S = mult(C, F, sub_eq_size, sub_eq_size);
	U = mult(J, K, sub_eq_size, sub_eq_size);
	V = mult(L, M, sub_eq_size, sub_eq_size);
	T = mult(GpB, HpE, sub_eq_size, sub_eq_size);
	
	BigInt *W=new BigInt[2*n/3 -1], *X=new BigInt[2*n/3 -1], *Y=new BigInt[2*n/3 -1], *Z=new BigInt[2*n/3 -1]; // i just thought i was done.
	for(BigInt i = 0; i < 2*n/3 -1; i++)
	{
		W[i] = (V[i] - T[i])/3;
		X[i] = (T[i] - U[i])/2;
		Y[i] = U[i] - S[i];
		Z[i] = ((Y[i] - W[i])/2) + (2*R[i]);
	}
	for(BigInt i = 0; i < 2*n/3 -1; i++)
	{
		PQ_Res[i] 		+= S[i];
		PQ_Res[i + (n/3)]	+= (X[i] - Z[i]);
		PQ_Res[i + (2*n/3)] 	+= (X[i] + Y[i] - R[i]);
		PQ_Res[i + (n)] 	+= Z[i];
		PQ_Res[i + (4*n)/ 3] 	+= R[i];
	}
	return PQ_Res;
}

This method can be analyzed in its runtime using the Master Recurrence Theorem. Take Toom-3 for example. Its running time is T(n) = θ(1) + 5T(n/3) + θ(n). Using the Recurrence theorem we can show that the running time of Toom-3 is n^log₃5.For any general Toom-k, it can be shown that since we do (2*k) – 1 recursions and we split the arrays in to sub-arrays of size (n/k), the running time of Toom-k is T(n) = θ(1) + ((2*k)-1)T(n/k) + θ(n) which when used against the Recurrence theorem we show that it is of n^log_k(2*k)-1 time complexity. I found this very interesting and I hope you do too!!

The post Toom-k Polynomial Multiplication appeared first on Jacob N Calvert.

Bit fields are a way to efficiently store multiple boolean values in one or more bytes. If you can imagine an 8 bit integer as binary, each bit would have to be either a 1 or a 0, corresponding to an “On” or “Off” value. With just one 8 bit variable, you can store 8 on/off values for your program. The syntax on how to set, unset, and retrieve these values can be a little confusing however. The method for using these helpful little bit fields involves some binary math with the binary operators AND, OR, and NOT. In C based languages these are written as &, |, and, ~, respectively. I’ll give an example in C that will hopefully make this math clearer. First we need to define some values as our flags. Each flag has to have a value that is a power of 2. For example:

enum FLAGS
{
	FLAG_A = 0x01,// 1
	FLAG_B = 0X02,// 2
	FLAG_C = 0X04,// 4
	FLAG_D = 0X08,// 8
	FLAG_E = 0X10,// 16
	FLAG_F = 0X20 // 32

	// so on and so forth
};

These could just as easily be written as the actual integer values, however I’ll stick to HEX notation for this example. Next we need a variable of at least 6 bits to hold our flags’ on or off state. Let’s use an integer type, and set all the flags to “Off.”

static int THE_OPTION = 0x00;

Now we’re ready to set, unset, and test some flags! To set the option to “On” for a certain flag, we must turn the bit “On” in our variable. To do this we use the OR operation. I explain why in the example below.

FLAG_C = 4, in 8-bit binary this is 00000100
THE_OPTION = 0, in 8-bit binary	    00000000

if we OR them:

THE_OPTION |= FLAG_C

the binary math looks like:

	00000000
OR	00000100
-------------
	00000100

This is a simple example but the point holds. To apply a flag, we apply the OR operator. To remove an option, we use the AND operator.

THE_OPTION = 0B00000100; //binary notation for 4

THE_OPTION &= ~FLAG_C; // THE_OPTION AND-EQUALS NOT FLAG_C

the binary math looks like:

	00000100
AND	11111011
-------------
	00000000

To check the status of a flag in THE_OPTION, one can simply check:

if(THE_OPTION & FLAG_F)
{
	//do things
}

These can also be chained, for instance

#include "stdio.h"
enum FLAGS
{
	FLAG_A = 0x01,// 1
	FLAG_B = 0X02,// 2
	FLAG_C = 0X04,// 4
	FLAG_D = 0X08,// 8
	FLAG_E = 0X10,// 16
	FLAG_F = 0X20 // 32

	// so on and so forth
};

static int THE_OPTION = 0x00;
void test_options()
{
	char line[512], *p;
	p = &line;
	p += sprintf(p,"THE_OPTION contains ");
	if(FLAG_A & THE_OPTION)
	{
		p += sprintf(p, "FLAG_A and ");
	}
	if(FLAG_B & THE_OPTION)
	{
		p += sprintf(p, "FLAG_B and ");
	}
	if(FLAG_C & THE_OPTION)
	{
		p += sprintf(p, "FLAG_C and ");
	}
	if(FLAG_D & THE_OPTION)
	{
		p += sprintf(p, "FLAG_D and ");
	}
	if(FLAG_E & THE_OPTION)
	{
		p += sprintf(p, "FLAG_E and ");
	}
	if(FLAG_F & THE_OPTION)
	{
		p += sprintf(p, "FLAG_F and ");
	}
	printf("%s, that is all.\n", line);
}
int main()
{

	THE_OPTION = (FLAG_A | FLAG_C | FLAG_F);
	test_options();

	THE_OPTION &= ~FLAG_A;
	test_options();

	THE_OPTION &= ~(FLAG_C | FLAG_F);
	test_options();

	THE_OPTION = 0XFF;
	test_options();
	return 0;
}

That will print

THE_OPTION contains FLAG_A and FLAG_C and FLAG_F and , that is all.
THE_OPTION contains FLAG_C and FLAG_F and , that is all.
THE_OPTION contains , that is all.
THE_OPTION contains FLAG_A and FLAG_B and FLAG_C and FLAG_D and FLAG_E and FLAG_F and , that is all.

This post is by no means an exhaustive list of the ways bit fields can be used, however these are the basic ways you can use them. Bit fields are a good choice in applications where memory is limited, or there are lots of boolean data points that need to be stored since one 32 bit variable can hold all the same data as 32 bool types in C. I hope this post was clear and somewhat educational! If you have anything to add send me some mail over on the contact page!

The post Binary bit fields and flags appeared first on Jacob N Calvert.

The most standout addition in my opinion is the ‘return type deduction’ feature which allows functions to use ‘auto’ return types that will be deduced at runtime. There are a few limits on this functionality however. Recursion can only happen if there is at least one return statement that can be evaluated to a non-auto type. For example:

// this factorial works
auto factorial(int i)
{
    if(i == 0 || i == 1)
    {
        return 1;
    }
    else
    {
        return i * factorial(i-1);
    }
}
// this one will not
auto factorial2(int i)
{
    if(i > 1)
    {
        return i * factorial(i-1);
    }
    else
    {
        return 1;
    }
}

This feature is very neat and somewhat ‘Pythonic.’ In C++11 the lambda feature already allows this auto typing but in C++14 it will be available to all functions.
Another notable addition to C++ in the latest upcoming release is the introduction of binary literals. With this, you can explicitly specify binary numbers with syntax like:

int nine = 0B1001;

There are many, many more language features being added in C++14; too many to note in detail. Check out more at the Wikipedia article for C++1y or at the standards status page for C++.

The post C++ 2014: auto return deduction and more! appeared first on Jacob N Calvert.