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?
* Compression (lossless, lossy, image, audio, texture, video)
* 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.
https://fgiesen.wordpress.com/2013/02/17/optimizing-sw-occlu...
(articles 6, 7, 8, others are not closely related)
As far as I know modern hardware has been non-scanline-based for ages btw.
For a 3D renderer, I recommend fgiesen's series as linked above, and the older series by Nicolas Capens: http://forum.devmaster.net/t/advanced-rasterization/6145
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.
Whoa, I want to hear about this. I have a couple of DSP firmware images I've shied away from reverse engineering as I don't know the platforms.
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.
https://www.packtpub.com/game-development/sfml-game-developm...
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.
Another great book is "Game Engine Architecture" https://www.crcpress.com/Game-Engine-Architecture-Second-Edi...
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.
http://www.dataorienteddesign.com/dodmain/node5.html
https://eliasdaler.wordpress.com/2015/08/10/using-lua-and-cp...
https://github.com/junkdog/artemis-odb/wiki/Introduction-to-...
Good luck and have fun!
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.
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
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.
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 :)
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.
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.
* An MVC web framework.
* A GUI validation library.
* A JavaScript UI library.
* An iteratee implementation.
* An Erlang-style actors library in another language.
* Implementing for-yield, async-await, etc on top of delimited continuations.
* Interpreters, typecheckers, code generators.
* Some of an ECMAScript implementation.
* Concurrent data structures: futures/promises, queues, etc.
* A simple roguelike game.
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.
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.
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.
That's pretty much how http://sciter.com was born.
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.
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
See Mike's PCJr page near end of this post:
* Floating point manipulation and numerical computation
* Rolling some own crypto (strictly for fun use)
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.
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.
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).
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?
> 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).
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.
[1] https://en.wikipedia.org/wiki/IBM_Informix-4GL -- I am flabbergasted to see 4GL is still in use 30 years on.
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.
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.