* Languages (bytecode interpreter, AST interpreter, parser/lexer for a simple language, simple JIT, understanding instruction scheduling)
* DSP programming (writing programs for fast, branchless math)
* Comfort with binary and binary formats (start with packfiles .zip/.tar, move onto reverse engineering simple formats for e.g. games)
* Understanding the difference between RAM and address spaces (e.g. understanding virtual memory, mmap, memory-mapped IO, dynamic linking, the VDSO, page faulting, shared memory)
* Device drivers (easier on Linux, understanding userspace/kernel interaction, ioctls, how hardware and registers work, how to read spec sheets and hardware manuals)
* Graphics (modern software rasterizer that's not scanline-based, understanding 3D and projective transforms, GPU programming and shaders, basic lighting (reflection and illumination) models, what "GPU memory" is, what scanout is, how full scenes are accumulated all along the stack)
I could go heavily into depth for any one of these. Ask me questions if you're interested! They're all fun and I always have more to learn.
Also, the longer you get into any given track, the more you realize they all connect in the end.
2D renderers? Do you mean rendering 2D shapes? In that case, scanline is probably the most efficient thing you can do, but most renderers are not scanline. The only modern 2D scanline renderer I know of is in the Flash Player code.
Yes, 2d shapes. I'm writing vector drawing software and I use agg as backend (which use scanlines). In the long term it could be a good think to use or implement a more modern back-end.
Modern, fast 2D rasterization is a really hard problem, one which I'm currently writing a long-form article on. The classic Red Book stencil trick + Loop-Blinn from 2005 is the current state of the art, I think. I'd love to do more research there.
In terms of a software rasterizer, which can often be faster, it's just a matter of elbow grease and engineering. Use SIMD. Implement tons of special cases.
Write a simple polygon plotter to get you started -- just fill a triangle with white with simple edge functions. Then work your way up to arbitrary polygons. And then look into the theory behind antialiasing and such.
I learned by reverse engineering DSP code in another platform which was used for obfuscation. I had a chat with a friend and he suggested the TI DSP starter kits. I'm not familiar with any of them, though.
A basic game engine! I was exposed to so many concepts over time, building on a code base I understood from the ground up.
It was the first time my code (c++ no less!) felt completely deterministic, that I understood every piece of data down to the byte level, heap/stack/gpu locality at any point of execution, and especially the lifecycle and memory management.
If anyone is interested in creating an indie/hobby game engine, I'd recommend the following:
- game loop with independent render FPS and a constant simulation tick delta (otherwise it runs non-deterministic due to floating point)
- "entities, components, systems" architecture (ECS)
- data-driven content (load level and game object data from JSON or similar, and programmatically build your scene)
- basic event or messaging system
Honestly, I can't think of a field that covers as wide a range of CS topics at the depth I've seen in lower level game development.
If you focus on understanding and implementing the popular patterns and algorithms recommended by the indie community, its not the most daunting of projects. There's so much great information, and a few good books that break down and walk through a working implementation you can build on once you understand it from the ground up.
SFML is a C++ library that handles window management, input, sound, etc...
For reference, a friend and I went through the book chapter by chapter a couple years ago. He was new to programming, and I'd made a few simple games and read scattered info in the past. The book had a good pace and filled in a lot of the gaps I had.
This book is a lot deeper, but I found it a great reference. I probably spent more time reading this book and going back over my engine code to refactor based on what I learned (rather than use it as a direct example implementation.
At that stage, there were a few good articles online that were focused on the ECS pattern. Here's a couple, but try to find something that matches your language, there's plenty of info out there.
I really recommend a raytracer, especially to anyone interested in graphics. It's straightforward, powerful, infinitely expandable with optional features, and opens up a ton of discussion about performance, code complexity, and general organization. Plus it's fun, in an instant gratification kind of way.
Every now and then I get interested in demoscene programming. I've never even been able to get a triangle to render on the screen - except with something like XNA.
Do you think there's any value in going back to say, DOS based VGA programming? People in #osdev thought I was a bit strange for wanting to write a bootable kernel that only put pixels on the screen, but I really enjoy the idea of starting with plotting pixels, then moving on to more complex effects.
Are you more interested in actually writing to PC VGA registers, or just the idea of writing a pixel-by-pixel renderer? There are bindings for SDL and SFML in a lot of languages, and the web technology option mentioned by the sibling comment.
If you like the idea of "DOS-based VGA programming" (taken literally), you could also find a DOS compiler or assembler and run it in DosBox. All of IBM's hardware-level documentation can still be found online: http://www.mcamafia.de/pdf/pdfref.htm
Or with different desktop GUI toolkits for different languages: C++ w/Qt, C++ w/ wxWidgets, wxPython, Perl/Tk, Python +Tkinter, Delphi, Lazarus, or many other lang/toolkit combos. Even many BASICs have that ability built-in (from the early days of personal computers).
The value of DOS based VGA programming is that, although hard things are damn near impossible, easy things are easy. https://www.mail-archive.com/kragen-hacks@canonical.org/msg0... is a 64-byte .COM file I wrote in assembly that draws circles on the screen; you can get to mode 13h with two instructions, and then you have a linear framebuffer with 64000 bytes, one byte per pixel, at your disposal located at A0000h.
So there are some awesome things about this:
- It's really easy to get started. You can literally take the code on that page, assemble it, verify that you get the right hexadecimal output, and run it in dosbox.
- Just about anything you do in the segment you point at the framebuffer will make something appear on the screen and not crash your program. So your bugs will be harder to debug, but they will also be cool.
- For example, running a pointer off the bottom of the screen puts you back on top of the screen instead of in the middle of your stack or heap or something. There are 4 lines of pixels that aren't shown, but often you don't care.
- The pixels are more or less square.
- Since each pixel is one byte, pixels correspond nicely to addressable memory locations.
- The first few colors in the default VGA palette are primary colors.
- Once you draw something, you can get awesome effects by changing the palette. Color-cycling, for example. This was really cool when actually redrawing the screen sixty times a second was computationally infeasible.
There are also a lot of shitty things about it:
- 320×200 is not very much resolution. Nothing will look sharp, except possibly the corners of your pixels.
- Palettes make it easy to draw something, and they even provide a kind of high-level interface that lets you kind of search and replace colors, in a way. (It's really more like macro-expanding your colors I guess.) But they make gradients and alpha-blending really hard to achieve, unless you stick to grayscale or sepia or something. TrueColor video modes are much better for those.
As for triangles, I'm sure you can figure out how to do them, but keep in mind that geometric algorithms easily turn into a rat's-nest of special cases. I've written polygon-filling routines a few times, and they can easily have the same algorithmic complexity as an entire ray tracer, which looks a hell of a lot cooler.
having written one as a slightly larger python thingy, i can fully attest to that.
now that it is kind of done, i want to make it faster :) for example, having a home-grown vector_3d class kind of sucks (performance wise). it might be better to have vector_3d be actually based on, say, numpy.array ? once that is done, and i start seeing some real improvement, it might be possible to go the other route as well i.e. write the hot-spots in c++/c, and interface that with python.
or go with lua all the way ? or maybe try a hybrid approach (which would allow you to see how embeddable the language really is)
possibilities are endless, and as you so rightly said, gratification is instantaneous :)
Simply replacing your own vector_3d class with numpy.array() won't actually speed you up that much as the overhead of creating all the tiny 3 element arrays kills you (I think I got only a 2x speed up from going from a pure python vector_3d to numpy arrays). Numpy is optimised for the creation of a small number of big arrays.
The massive enormous speed ups come from creating massive arrays and implicitly working on them in parallel. So instead of iterating through every pixel and creating a origin and direction vector for each one you create a Total_number_of_pixels X 3 numpy array and pass that to your ray tracing function. Due to the way numpy broadcasts arrays the amount of rewriting you need to do is incredibly minimal and the speed ups over pure python are astronomical.
> The massive enormous speed ups come from creating massive arrays and implicitly working on them in parallel. So instead of iterating through every pixel and creating a origin and direction vector for each one you create a Total_number_of_pixels X 3 numpy array and pass that to your ray tracing function. Due to the way numpy broadcasts arrays the amount of rewriting you need to do is incredibly minimal and the speed ups over pure python are astronomical.
thank you for your insight! this is very useful indeed.
Just to give an idea of the speed up from going from processing individual arrays to batch processing - an Image I was rendering went from 2 hours to 20 seconds (and that was with further obvious speed ups left on the table as well).
Oh, and make sure you're using 64-bit version of python as you'll be slinging multi-gigabyte arrays around all over the place.
I haven't find a good introductory yet complete resource about build a complete database. I'm on the hunt for it (building also a relational language).
While not exactly what you're looking for, The Definitive Guide to SQLite takes you from writing a SELECT statement all the way to an overview of SQLite internals. O'Reilly also published a booklet called Inside SQLite that goes a bit deeper into the subject. I suggest SQLite because the source code is superb (seriously, some of the most readable, most logically organized and best commented C code you'll ever see) and it's a fairly small codebase with a huge community.
And then there is Database Systems, The Complete Book where the second half of the book offers in deep coverage of the implementation of database systems.
This area is one where it look more impenetrable. You find good info about compilers and even build "computers" from scratch but databases is black magic.
Specially, because RDBMS look like are at all or nothing. I wonder if is possible to pick "only" the transactional/storage and made by myself the query/optimizer/api on top. I will be happy if is possible to build on top of something like sqlite, unfortunately, I don't know C at all (work with F#,C#, Delphi, Python).
In the other hand, know the basic steps could be good enough...
Same category of probably not a great idea to use and claim is better than what's out there ( it won't be ) but boy howdy will it teach you about distributed systems and pitfalls that will absolutely help you when you are working on one at your day job.
Seconded. One of my plethora of hobby projects has been an interpreter or compiler (it changes from month to month) for Common Lisp, for an esoteric platform. It's a huge amount of fun, and I have learnt so much about software from it.
Hmm, rasterizer was just a starting point for me on the way to understand "how browser works".
Having just a rasterizer is like naked VM without bytecode compiler.
So I decided to add HTML/CSS engines to it.
But if you have HTML/CSS then why not to add scripting to it? So added VM executing bytecodes, GC and compiler producing those bytecodes. Having VM I thought that it would be cool to have built-in persistence in it - you need to persist UI state somehow, right? So it got integrated NoSQL database on board.
Reading from a raw filesystem dump was both interesting and rewarding as it works on a problem domain that exists in reality, not just on some simplified playground. If you target something as primitive as FAT, the challenge isn't terribly high.
A screen-oriented text editor with undo and search/replace. Can you make it handle a 10MB file without "simple" operations having annoying delays? How about 100MB? 1GB? 100GB? With no line breaks in the file?
With both emacs and vim you can certainly edit 500MB file. I concatenated all sources of recent Linux kernel 4.6.3 once. From what I remember it was all .c, .h and .S files. Resulting file has 542MB and 19'726'498 lines. I did it to test the text editor I am working on.
Some stats:
$ time vim -c 'edit kernel-total' -c q
real 0m8.162s
user 0m7.687s
sys 0m0.398s
$ vim kernel-total ^Z
$ ps aux | awk "/kernel-total$/ || NR == 1"
USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
hawski 10467 2.7 17.1 805120 670988 pts/2 T 17:41 0:07 vim kernel-total
$ time emacs kernel-total -f kill-emacs
real 0m7.155s
user 0m6.869s
sys 0m0.237s
$ emacs kernel-total ^Z
$ ps aux | awk "/kernel-total$/ || NR == 1"
USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
hawski 10825 43.8 14.8 857484 581152 pts/2 T 17:47 0:07 emacs kernel-total
With vim editing is quite smooth and with emacs it feels laggy. I only edited a bit, like entering a new line here and there, moving few pages down, going to the end of the file and to the top again. Saving is sluggish.
I don't think so. Can a text editor do search and replace on a 100 GB file without a delay? You could construct an index, but that's not going to happen instantaneously either.
> Can a text editor do search and replace on a 100 GB file without a delay?
I meant that things like simply scrolling through a few pages or inserting/deleting a single character in the middle of the file shouldn't cause noticeable delays. Doing an operation that spans the entire file is different.
Because if you're familiar with conventional real register architectures, the stack VM forces you to rethink it, in a much simpler way. It's a useful simplifying abstraction.
There used to be a lot of interest in, and articles about, stack machines (real ones, not VMs) back in the days of mags like BYTE and PC Mag. Good reading.
Actually, implementing your own crypto for real is not so crazy. The best algorithms are surprisingly simple, and easy to make side-channel resistant. The only real difficulty I have so far is with modulo arithmetic on big numbers (for elliptic curves and one time authentication).
With proper test vectors and some code review, crypto is in fact quite easy. More dangers lie un the use of crypto, especially when the API is flexible or complex. And of course good old exploitable bugs.
No. Never roll your own crypto for production. If you only know one thing about security as a programmer, then it has to be this.
But you are right that crypto algorithms aren't specifically hard to implement compared with, say, computer graphics, image processing, gui programming or whatever.
But! The big difference is that crypto is attacked by other smart people. The bugs and design flaws in your scientific computing library are not hunted down by intelligent agents to purposefully break it. If people attacked your Paint clone to the same extent they attack computer security programs, then it would become just as hard to write them correctly as it is with crypto.
There are so many kinds of ways to get it wrong that beginners don't even know about. It's an "unknown unknowns" situation.
Have you seen the size of the reference implementations for chacha20, blake2b, or poly1305? Those are tiny,
a couple hundred lines for all three! There is very little room for errors to sneak in. Between test vectors, compiler warnings, and Valgrind, we can be pretty sure all bugs have been shaked out. Add in good old code review and the safety of this stuff is pretty much guaranteed.
Of course, I would never make the mistake of rolling my own OpenSSL clone (too big, bad API, some bad primitives), or even my own AES implementation (slow or prone to timing attacks).
Of course, I don't make the mistake of going blind. I read the literature before making any choice. If I don't know why some construction is considered safe, I don't use it. Due diligence first. And I certainly don't implement the first primitive that my search engine gets its hands on. I go for the most vetted alternatives.
Even experts wouldn't do this on their own. It takes teams and a lot of time. A lot of thought can go into a few hundred lines of code. It needs math oriented people, it needs OS-oriented people, people who are experienced with exploiting systems.
As I said, it's good to do it for fun and to learn, but there's no reason to do it for production. It's almost always a case of ignorance and overconfidence.
The problem is that in computer security defense is a lot harder than offense. If you make just one mistake, it can often lead to a compromised system.
Anyway, there's a lot of discussion on this topic around security.stackexchange, quora, reddit etc. The consensus is that it's a terrible idea.
Did you miss the part where I mentioned code review? And the one where I said I would never invent my own primitives?
> A lot of thought can go into a few hundred lines of code.
I can attest to that. I can also confirm that most such though went in the design of the primitive itself. Most implementations in pure C are pretty straightforward, almost naive. Seriously, take a look.
> It needs math oriented people,
Mostly to design the primitives, and perform modulo arithmetic on huge numbers. That's about it.
> it needs OS-oriented people,
Only if you're writing the random number generator of an OS kernel. For the rest, portable C code is enough. You don't even need heap allocation.
> people who are experienced with exploiting systems.
Not quite. You need people who are able to write correct code, thus avoiding undefined behaviour. By the way this applies to everything, not just crypto.
> there's no reason to do it for production.
Dependency management. It's not a very good reason, but if you only use one or two primitives, importing libsodium may not be worth it.
> The problem is that in computer security defense is a lot harder than offense. If you make just one mistake, it can often lead to a compromised system.
It doesn't have to be the crypto library's fault. A single buffer overrun anywhere, and you risk giving your keys to the attacker —if that didn't already served the whole server on a silver platter. You won't be secure just because you use OpenSSL or libsodium as intended. Even if your crypto library is bug free and immune to side-channel attacks.
The greater risk is not crypto code. It's user code. Implementing your own crypto code is not going to increase the risk by much —or at all, if you're sane enough to turn on warnings, use Valgrind/Purify, write tests, and have your code reviewed.
> Anyway, there's a lot of discussion on this topic around security.stackexchange, quora, reddit etc. The consensus is that it's a terrible idea.
With all due respect, fuck consensus. Read the expert's writings. Daniel J. Bernstein in particular has written some very good stuff on why he started to write the NaCl library. Or on how he designed his primitives to be simple, and as such easily analysable by his peers. Or on how easily one can avoid timing attacks (hint: don't use AES).
I'm not saying it's impossible to do. It depends on how "deep" you want to go. "Rolling your own crypto" can have different meanings. It can mean designing a new hash algorithm or encryption algorithm, or opening up a crypto book and reading some pseudocodes and formulas and then implementing them, or it can mean something more high level.
The higher you go the less error-prone it becomes.
Anyway, if you think you can realistically estimate the risks involved and you have the skills to do it, then perhaps you can. You'd definitely be in the top 0.1% of developers or even better. For the vast vast majority (the rest of us), it's not worth doing. It's very likely that we'd do something where we don't even know that we don't even know we should pay attention to. Again, unknown unknowns. When I read about bugs and exploits in security code, I always realize how difficult it is to get it right.
By the way, why do you think that the consensus is the way it is? Is it spread by security and crypto developers so that there's less competition?
Agreed on the depth argument. It seems we misunderstood each other. I shall write an article on "Rolling your Own Crypto" shortly, and lay out the possibilities and the safety implications. I'm no expert, but I believe my opinion is well informed.
> Anyway, if you think you can realistically estimate the risks involved and you have the skills to do it, then perhaps you can. You'd definitely be in the top 0.1% of developers or even better.
I am definitely not in the top 0.1%. However, for the goal of implementing existing crypto primitives, for which test vectors are available, I'm confident I can implement the primitives I'm interested in correctly (zero bug, immune to timing attacks). My only roadblock for now is modulo arithmetic of big numbers. For this, I am currently content with ripping off existing implementations. However, to ensure that my implementations are indeed bug-free, I will need external review.
And again, the current best primitives tend to be simpler than most.
About the unknown unknowns… well, side channel attacks are an open area of research right now, so I won't pretend I can be immune to any of those, except timing attacks. (Those are surprisingly easy to prevent: just don't let any variable-time operation depend on a secret input. for symmetric encryption, this means no branch and no array indexing that depends on either the message or the secret key. Some primitives make this easier than others.)
> By the way, why do you think that the consensus is the way it is?
Because a blanket "never invent/implement/mess-with your own crypto" is easier to spread, and safer than anything more accurate: any subtlety can and will be misinterpreted by some fool, who will then happily implement easily broken crypto. My upcoming article on the subject will indeed start by "don't do it". I'll have to introduce the subtleties very carefully, lest I encourage some idiot to screw up.
Come to think of it, I probably deserve the downvotes I got, even though I stand by what I wrote: with crypto, partial knowledge tends to be dangerously unwieldy. Many missteps are as silent as they are deadly (sometimes literally so: see Tor, or WiFi enabled pacemakers).
The problem is that fools don't know they are fools. Most programmers don't know about timing attacks even. Some don't properly understand buffer attacks etc.
There's a phase in developers' lives when they are overconfident. Having learned a language or two, they can reasonably implement things they need, they can use databases, create guis etc. At this point they might conjure up some "clever" way to store passwords or encrypt data by original schemes invented by them. This is always wrong.
And to reiterate: people often don't know that they don't have the necessary skills.
OMG, memories... at once point in the pleistocene era, I was tasked with writing a manual for what was then Informix 4GL[1], and to get comfortable with the language, I spent a week writing a user forum app, with topics and message threads, messages stored as "blobs" in the SQL DB. Tried to get my co-workers in the pubs group to use it. They thought it was cute but all said hahaha no.
By far the project that teaches me the most was writing an inliner for a toy language we developed as a part of a course at uni.
Most people don't really realise that the more complex an inliner gets, the more similarities it gets to a rabid animal you can just barely restrain on a leash.
My prof said he had laughed at my "how hard can it be?"-attitude . I worked my ass off and ended up being asked whether he could use the inliner in a language often mentioned on HN today :)
The inliner was superseded by a much better one in 2003 written by a much smarter person than I, though.
An emulator for a real chip, like a 68000. I wrote one for a Prime minicomputer (Prime died in the early 90's). Telnet to em.prirun.com on port 8001 to try it out!
The advantage of emulating a real system/chip is that if you can find old software for it, you avoid the step of having to invent your own programs: real, running programs already exist.
Most people refuse to write one because it's so easy not to. Why bother?
It will make you a better coder for the rest of your life.
Let's make a list of "power projects" like this. A bytecode interpreter, a software rasterizer... What else?