Learn about data structures & algorithms used in eg. iPods, phones...

Dave!

Hey folks,

I've just finished my second year studying java and my second semester studying data structures and algorithms in java... I'm not fantastic at it or anything! But I'm fairly interested in it.

I was walking along earlier listening to my mp3 player and started wondering what kind of coding, etc., it is running. It's probably more likely to be C, etc., than Java, but as far as I know the principles are the same. It's an iPhone so it will have all sorts of fancy ways to interact with it, touchscreen etc., but again, I'm sure the underlying data structures are the same in principle as the kind of thing I've been studying (maps, graphs, trees, arrays, lists...).

Also when you ask it to carry out an action like say 'shuffle', then it would carry out some sort of algorithm on the data.

I'm just wondering are there any sites, books, etc., that would give information on the kind of programming that is typically used on hardware devices and gadgets? Should I take it that Apple don't release all the code for their gadgets to the public for free? Are there basic principles that underlie all / most mp3 players, and iPods just put a fancy GUI on it?

I'm just looking for how to learn a bit more about practical use of the principles I've learned, because so far it's all been a bit abstract, just using test classes to make sure it's all working, and so on.

I'm (hopefully!) going into my final year after this summer, and we'll have to do a bit of a more advanced project, possibly using hardware to interact with the program, etc., so it couldn't hurt to learn a bit more.

Cheers

Dave

NeverSayDie

Don't do much work in the area myself, but to help with your googling, the general term for this field is "embedded development". Should find lots of sites with info on various different aspects of it.

Cantab.

DaveMcG wrote: »

Hey folks,

I've just finished my second year studying java and my second semester studying data structures and algorithms in java... I'm not fantastic at it or anything! But I'm fairly interested in it.

I was walking along earlier listening to my mp3 player and started wondering what kind of coding, etc., it is running. It's probably more likely to be C, etc., than Java, but as far as I know the principles are the same. It's an iPhone so it will have all sorts of fancy ways to interact with it, touchscreen etc., but again, I'm sure the underlying data structures are the same in principle as the kind of thing I've been studying (maps, graphs, trees, arrays, lists...).

Also when you ask it to carry out an action like say 'shuffle', then it would carry out some sort of algorithm on the data.

I'm just wondering are there any sites, books, etc., that would give information on the kind of programming that is typically used on hardware devices and gadgets? Should I take it that Apple don't release all the code for their gadgets to the public for free? Are there basic principles that underlie all / most mp3 players, and iPods just put a fancy GUI on it?

I'm just looking for how to learn a bit more about practical use of the principles I've learned, because so far it's all been a bit abstract, just using test classes to make sure it's all working, and so on.

I'm (hopefully!) going into my final year after this summer, and we'll have to do a bit of a more advanced project, possibly using hardware to interact with the program, etc., so it couldn't hurt to learn a bit more.

Cheers

Dave

VHDL/Verilog. Get yourself a Xilinx board.

sobriquet

With respect to the specific code that Apple and the like use, obviously (?) it's not available, but people have released homebrew firmware for MP3 players and the like. This'll include the kind of code you're thinking about. Try rockbox.org for a start, it seems to be the most popular or visible at least.

In terms of what goes into it, well writing C for embedded platforms is going to be quite different from the Java you're used to. If you're weak doing data structures and algorithms in Java, doing the same in C will be painful. It's worthwhile though.

Another thing to remember is that if you're going to go that route, get some decent texts or tutorials in writing vanilla algorithms in C - the likes of rockbox.org will be a mature codebase, untangling something like that takes time. Just a thought, but implementing something from the requested feature list would make a great final year project. Having to learn C, learn a large codebase and how to integrate into it, and even getting it accepted by the developers would look great on a CV.

ianhobo

hey,

Your right, most of this stuff is indeed written in either C or C++. How much detail did you go into when you studied the data structures? how "low" did you go?

It's an iPhone so it will have all sorts of fancy ways to interact with it, touchscreen etc., but again, I'm sure the underlying data structures are the same in principle as the kind of thing I've been studying (maps, graphs, trees, arrays, lists...).

Data types and structures such as trees, binary trees, tables, don't natively exist in C. There is no type BinaryTree etc. If you want it, you have to implement it yourself. So its important to understand the higher level explanations that you would have gotten in java.
If you want a list, you have to create a simple data structure which contains data, and which is able to point to or reference the next element along. You then chain them together in software according to the overall concept.

typedef struct
{
     int          myData;
     MEMBER      *next;

}MEMBER;

If you add in one more "MEMBER *pointer" into the structure, you on your way to creating a binary tree

Also when you ask it to carry out an action like say 'shuffle', then it would carry out some sort of algorithm on the data.

That sort of stuff would be relatively simple, its just random numbers. But more complex algorithms would be present for things like sorting all the songs and albums. For searching the internal database for a name or artist. These can get very complicated very quickly, particular where you want them to be fast! (as will always be the case in consumer devices )

The iPod touch would be a big project. It probably has an operating system written in C, but another layer on top managing the user interaction and display. If you want to learn about MP3 players, heres a good link to some free code. This is the software to run a MP3 player running on an 8051 processor. If might be worth having a look at it, and the website in general. I haven't looked at the source in a while though. Its all written in C and assembly, but the earlier version might be easier to understand. Bear in mind, all of the mp3 decoding stuff is handled by a hardware decoding chip, no software. The mp3 data is simply sent to the correct pin on the mp3 decoding chip, which decodes it all itself.

http://www.pjrc.com/tech/mp3/firmware.html


Its the same in your iPod, there is a dedicated hardware chip for video and audio processing.

To learn more about algorithms and data structes, simply search for that in google! at a quick glance, this microsfot tutorial seemed quite good

http://msdn.microsoft.com/en-us/library/ms379570.aspx

Your right to interested in these sort of things. They are the core of any embedded device, and good design will never take place if you don't know how to handle your data properly!

Hope that sort of helps, sorry if its all dis-jointed!

DublinDilbert

You could look up the USB mass storage specification, as that is extremely widely used, most mp3 players, every usb memory key, external HD....

Dave!

Thanks all, esp ianhobo! We got fairly low with the data structures... Pretty much the same way you described above. So I understand the concepts and how to implement (most of) them in java. If I could code in C, would I be right in assuming that it would simply be a case of implementing them in the different language, but with the same principles?

That microsoft page is pretty freakin handy, and woulda been helpful to have over the last year while I've been struggling to understand some of the concepts! Cheers

ianhobo

No worries

would I be right in assuming that it would simply be a case of implementing them in the different language, but with the same principles?

Yep, once you understand what's going on conceptually, you would then get specific in your required language, but your high level design would generally remain the same across various languages, just the specific implementation details would change. A queue will always be a queue, a binary tree is always a binary tree, only the way its achieved in a specific language will differ

Dave!

As I suspected! That makes the prospect of crossing from one language to another somewhat less daunting...