Tuesday, August 9, 2011

I was originally going to post this as a tweet, but verbosity got the better of me. Colleagues whom I have worked with (you know who you are) will attest to this fact...

I frequently consider how things may have turned differently based on my own choices; jumping directly into employment versus attending university. Choosing a career as a software engineer as apposed to pursuing interests in chemistry and biology.

I like to think that all-in-all everything worked out okay... On the other hand, there are so many possibilities that I will no longer be able to explore, and that is very disappointing. I will likely never know what it would be like to attend a university, graduate with a PhD (which would probably be in computer science, chemistry and/or biology -- the two being closely related.)

I have even contemplated the idea of assembling a small team for developing small to medium scale games. I don't think there is a way for a small group to compete with triple-A titles, which again is disappointing. Of course this is a pipe-dream. I don't know artists capable of creating the media required, nor any software engineers who would be willing to participate project which has an unknown chance of commercial success. I think these kinds of projects are a Euro short and a decade late.

Well, maybe not a decade late, but at least I don't have the means to bankroll such an endeavor from my personal account. Perhaps it would be interesting to sketch out a graph of my life based on decisions made and not made and see what the projections look like...

If only for more productive hours in the day; but that is another brain-dump entirely.

Monday, July 11, 2011

Using dlopen() for fast engine prototyping...

I recently became tired of the cycle of hacking on the renderer, starting the whole engine, checking where and how it's failing, exiting the engine and the pointless time wasted during this process. Typically it's only a specific area I'm working on, thus perhaps one or two C source code files are actually changed, so it doesn't make sense to reload the entire engine and all media assets.

I started working on a smaller project for rapid-fire prototyping, μEngine. Currently it's a pretty basic project. It provides the basic framework for detecting that a shared object has changed, unloading the current version from memory, loading the new library, resolving the required symbols, and continuing the "rendering" loop (which actually doesn't perform any OpenGL rendering yet.)

Here's an example of the engine running:

~/uengine/src (master) $ make && ./uengine 
make: Nothing to be done for `all'.
... .libs/libuengine.so
... .libs/libuengine.so
... .libs/libuengine.so

While the engine was running, I edited libuengine.c, which is compiled by Automake into a shared object:

$ sed -i 's/0xdeadbeef/0xcafebabe/' libuengine.c && make
  CC     libuengine.lo
  CCLD   libuengine.la

Now I want to terminate the program (and I'm too lazy to have written a signal handler yet) so μEngine's main-loop is setup to terminate when dlsym_main returns a zero value.

$ sed -i 's/0xcafebabe/0x0/' libuengine.c && make 
  CC     libuengine.lo
  CCLD   libuengine.la

μEngine also links with libengine (which provides all of the math/geometry/etc functionality for Trinity), libdecl (which provides access to id Software style declaration files), and liblwo2 (which, well, loads LWO2 model files.)

This little experiment is far from complete. I still need to setup an OpenGL and GLX context, handle X11 input, and keep track of any ARB fp/vp or GLSL programs loaded. GPU programs will be reloaded in much the same way as the shared object itself.

There is of course a few frames delay between invocation of make and the new library being loaded, because should stat fail to obtain the file modification time (because it's still being written out) μEngine just continues with the old shared library until stat succeeds. The modification time is checked every "frame."

I think this should help with faster prototyping, since μEngine has the ability to access all of the assets and libengine library functions that Trinity can, but without the requirement of loading all the assets for a full world map into memory at start up.

Saturday, May 28, 2011

More BSP compiler hacking...

I've started working on my engine's BSP compiler (based on Q3Map2/XMAP2) looking to add proper shader parsing and areaportal detection. Currently the shaders are all parsed by libdecl which avoids duplication of code between the engine and utilities.

The engine does not yet use portal based rendering (which is why you can see light clipping through the wall in the images.) The BSP compiler has portal debugging enabled, which outputs an extra surface with a translucent shader for areaportal visualization and debugging.

This is a very simple demo map, however you can already see several issues. The BSP compiler needs to carve the polygons into discrete areas (e.g. the floor polygon should not span two areas.) There are still a few areaportal bugs in the BSP compiler, and of course the engine must be updated to use areaportal based rendering.

 Image showing light leaking through the wall/areaportal.
Image showing the triangles rendered; the floor and walls should be carved at the areaportal boundary.

Who knows, maybe I'll even get this finished before id Tech 4 is (hopefully) released under the GNU General Public License.

Friday, April 22, 2011

HP LaserJet Pro CP1525nw Review

I received the CP1525nw on Thursday, and it turns out this is a really great printer for GNU/Linux (which probably means the other HP network-compatible printers are good, too.)

Basically I unpacked it, plugged in Ethernet and power cables, it fetched an IP address from DHCP and displayed it on the small LCD. You can do some basic configuration through this LCD/few-button interface, but it's not worth the trouble; just note the IP address, enter it into a browser, and setup from there.

You can't setup the wireless via the LCD interface (unless you make use of this silly PIN code system which my router doesn't support anyway.)

Everything is configurable over the web interface, and by default mostly everything is enabled and unsecured. I disabled features I wouldn't use, configured the wireless, assigned a static IP, and secured the interface with a password.

Note that while you can configure the wireless it won't actually become active until the Ethernet cable is disconnected. You can't use both interfaces (Ethernet and WiFi) at the same time.

Everything went very smoothly and you don't need any proprietary software, even for setup, which is wonderful. :-)

Complaints thus far, although I haven't had the chance to use it much due to only having a few sheets of blank paper lying around, are as follows:
  • No duplex printing, although you can of course manually duplex your documents by printing even/odd pages in separate jobs.
  • Paper tray is a bit small: 150 sheets. It would be nice to have a 500 sheet tray which would accomidate an entire ream of paper.
Not big issues, and the print quality is very good, so I would recommend this printer. CUPS configuration was quick and painless, and CUPS has a built-in driver.

Saturday, April 9, 2011

Ultrasonic modem update

I did a little more digging into underwater ultrasonic digital communication. There is a publication from DTIC which looks interesting. It includes some rather boring source code, but provides a lot of good advice in the text.

Available for purchase is An Ultrasonic Sensor Based Low-Power Acoustic Modem for Underwater Communication in Underwater Wireless Sensor Networks by Heungwoo Nam and Sunshin An. It's €25 for the publication, so I'll probably purchase it (unless some anonymous person with access would email me.)

Of course, this is leading to the ultimate conclusion of setting up an EE workbench and buying a bunch of expensive equipment (solder station, oscilloscope, function generator, multimeter, etc.)

I seem to have expensive hobbies. :-( I should really spend some money on a good vacation, which I sorely need.

Thursday, April 7, 2011

Printer for Home Office...

Dear Lazyweb,

I'm currently looking for a printer for my home so that I don't have to wait until I'm at the office and use the printers there... Unfortunately it seems many laser printers (especially Canon, which Verkkokauppa are pushing to sell) either don't have Linux support, or have only proprietary drivers. What ever happened to just accepting a Postscript file?

Canon are especially nasty in that they provide a "source" package, which is really just the source code for some of the utilities, but the core library is still proprietary. Every time I see a shared object or binary inside a source package, I die a little inside...

Besides Xerox printers (very expensive) HP seem to have a couple of good options:
Both accept the following languages:
  • HP PCL 6
  • HP PCL 5c
  • HP Postscript Level 3 Emulation
According to this forum post it looks like it should work out-of-the-box with CUPS, without any proprietary drivers which is a precondition for my purchase...

Verkkokauppa have a rather silly return policy. Maybe this was inaccurate as I only asked one of their sales people, but apparently should you purchase something from their shop in person, then you do not have the option to return it (except if the product is defective.) However, should you purchase online (even to pick-up from the store) you have a 2 week return period...

I am leaning towards the CP1525nw because it seems like it will work with CUPS without proprietary crap, and the wireless network feature means I can put the printer in a walk-in closet or similar and keep it out of the way. Unfortunately it's a 1-2 week order time from the supplier.

It seems a reasonable deal for around the €200 to €300 range.

Sunday, April 3, 2011

Expression parsing and evaluation...

Something which has been annoying for me for a while was the lack of proper expression parsing in libdecl, my engine's declaration parsing library.

This library is responsible for parsing the sound and table/material declarations as defined by id Software, and making them available to the renderer (or other backend: sound engine, etc) in easy to read structures guaranteed to have sane and correct values. libdecl is the component which will complain about your syntax, the backend doesn't have to care about any of this. Really makes the code look a lot nicer. :-)

I was debating the best way to parse expressions, because they can either be very simple, or quite complicated. I realized that I could not rely on line terminators, because it's very common to see an expression span multiple lines with all kinds of tabs and white-space in the file... Of course the lexer ignores white-space, but keeps track of the line count.

After a bit of thinking about this, I decided to rip out the current shunting yard algorithm from the renderer, move it into libdecl, clean it up and rework it quite a bit. Now, it does the following:
  1. Get a token from the lexer,
  2. Check this token matches our expected rules,
    1. the token is an operator or operand, or
    2. the token is a table name. (Detected from 1st-pass.)
  3. If our checks pass, go ahead with the normal algorithm, otherwise,
  4. Push the token back to the lexer, and return the completed expression in Postfix notation.
Here's a hypothetical example that I wrote with more comments than necessary...

/* "material" keyword is optional when inside the material directory */
material textures/screenBlur
        sort postProcess

        /* first stage */
                if glslPrograms != 0 &&
                        !isMultiplayer  /* don't blur the screen in multi-player */
                map textures/blur       /* any image format supported */

        /* ... */

Obviously simply parsing the "if" expression until the end of the line would fail, furthermore, "if" expressions may be written as if ... or if (...), so matching on parentheses won't work either.

It turns out the easiest thing to do is first a pre-pass which only looks at tables (so that we know "foobarTable" is valid), then a secondary pass which looks at everything (sounds, tables, materials.)

In this example "glslPrograms" and "isMultiplayer" are built-in variables which the parser correctly detects as operands. Therefore we'll only stop parsing after reading the "map" token, realize it's not a valid operator or operand, push it back to the lexer, and return the expression (after some processing.)

This solution seems to be quite elegant, despite the 2-pass algorithm, and handles all the cases correctly.

The next step is to get rid of static stack allocation. Some expressions are very long, so the stack is setup for 64 elements, but this is ridiculous for "time * 0.001" (for example.)

Wednesday, March 23, 2011

The Matrix at your local Apotek?

Couldn't help but laugh when I opened these (Paracetamol and Ibuprofen) as I usually buy a different brand of Ibuprofen which is your standard white pill.

That's why they are cost approximately 8 euros for 30 tablets! Damn, I don't need it decorated like an Easter egg, as long as it works...

Sunday, February 20, 2011

New home for Revenge (Radeon Reverse Engineering Tool)

Thanks to Marek Olšák for having a backup copy of my Git repository online! The hard drive containing much of my personal code which was on people.freedesktop.org (until those directories were lost) is half way around the world.

Revenge now has a new home on http://gitorious.org/omcfadde/revenge.

I have bumped the version to 2.0.0, which introduces some minor configure.ac fixes: mostly PKG_CHECK_MODULES for libpci, sdl, and zlib. I have also updated email addresses and revenge.sh for non-developers.

Honestly I do not expect this code to get much interest now that we have documentation from AMD; but it's useful for historical/nostalgic reasons.

If I were to do it over again today: I would start with the kernel MMIO tracer (which would deal with the fglrx kernel module) then extend this to handle dumping MMIO access from a userspace process too. The kernel is the perfect place to do so, and would be far more reliable than userspace.

If you have any questions or bug reports, feel free to ask them here and I will try to provide you with timely answers/fixes.

Saturday, February 19, 2011

Math function micro-optimization...

Preamble for planet.freedesktop.org

Sorry about the poor formatting on planet.freedesktop.org; it seems it and BlogSpot don't quite get along, therefor you won't see any color hilights. It looks much better (and easier to read) on my actual blog page, honest!

Updated version includes float-to-int optimization and comments; sorry if this bumps this rather long post to the top again; this is not my intention. planet.freedesktop.org admins: is there some way to disable bumping when a post is updated? (Perhaps selectively, in case the bump is important. e.g. updated dates for an event.)

This analysis was performed using a modified version of Chris Lomont's inverse square-root testing code. The accompanying publication is worth reading before looking at any of this data.

I've started looking into whether there would be any performance difference in a few optimized math functions should -fstrict-aliasing be enabled. I did not believe strict-aliasing would have much of an effect on these optimized functions (and it turns out I was correct) but the benefit is seen when compiling other code which includes these inline functions.

Without strict-aliasing compatibility, including the header file containing the incompatible functions/macros taints the entire file, meaning you cannot use -fstrict-aliasing where it may be helpful for your general code.

Here are the results for the standard 1.0 / sqrt(x) frequently used in graphics engines. Even though today's renderers typically use carefully crafted SIMD functions for the critical path, this is still useful for quickly normalizing vectors in game code, etc.

The Lomont version of the function is a tiny bit faster and a tiny bit more accurate, but nothing to write home about.

Clearly it can be seen that this micro-optimization is an excellent for x86 and x86_64. Don't try it on ARM; it's far slower than just taking the hit on 1.0 / sqrt(x)

I don't know whether this optimization could be modified for ARM; any assembly experts out there?
Timing Exact function
1752 ms used for 100000000 passes, avg 1.752e-05 ms
Timing Carmack function
463 ms used for 100000000 passes, avg 4.63e-06 ms
Timing Carmack function (strict-aliasing)
455 ms used for 100000000 passes, avg 4.55e-06 ms
Timing Lomont function
453 ms used for 100000000 passes, avg 4.53e-06 ms
Timing Lomont function (strict-aliasing)
455 ms used for 100000000 passes, avg 4.55e-06 ms

The absolute value function is mostly used for comparisons (e.g. fabs(y - x) > epsilon and some other specialized functions: finding on which side of a plane an AABB resides, it's distance from said plane, AABB radius, etc. Therefor it's useful to optimize this function where possible...
Timing Exact fabsf function
268 ms used for 100000000 passes, avg 2.68e-06 ms
Timing Bit-Masking fabsf function
304 ms used for 100000000 passes, avg 3.04e-06 ms
Timing Bit-Masking fabsf function (strict-aliasing)
305 ms used for 100000000 passes, avg 3.05e-06 ms
However, apparently it's quite a bit faster to just call libc's fabsf function! I saw this originally in the Quake 3 Arena source code, so maybe things were different with the compilers and hardware of the time.

These macros/functions are used when you want to know the sign of a float (i.e. is the value positive or negative) without performing any comparison (for performance reasons.) It seems that the strict-aliasing versions perform about identical to the macros.
Timing Exact float sign bit not set function
327 ms used for 100000000 passes, avg 3.27e-06 ms
313 ms used for 100000000 passes, avg 3.13e-06 ms
Timing Bit-Masking float sign bit not set function (strict-aliasing)
312 ms used for 100000000 passes, avg 3.12e-06 ms

Timing Exact float sign bit set function
342 ms used for 100000000 passes, avg 3.42e-06 ms
305 ms used for 100000000 passes, avg 3.05e-06 ms
Timing Bit-Masking float sign bit set function (strict-aliasing)
305 ms used for 100000000 passes, avg 3.05e-06 ms

Don't use "d = (int) f" if you want fast code. fld and fistp work nicely on x86 and x86_64.
Timing Exact float-to-int function
1252 ms used for 100000000 passes, avg 1.252e-05 ms
Timing Fast float-to-int function
336 ms used for 100000000 passes, avg 3.36e-06 ms

Done. By Chris Lomont 2003. Modified by Oliver McFadden 2011
These measurements were taken on my laptop with an Intel(R) Core(TM)2 Duo CPU P9500 @ 2.53GHz processor and the test program compiled with gcc version 4.4.5 (Debian 4.4.5-6)

Whether this makes any huge difference in frames-per-second is debatable, really I had a bit of time and was bored. :-) Anyway, I wouldn't say anything until testing under real-world conditions.

It does look like the bit-masking fabs can be thrown away, though, and the fast float-to-int is a major win (although beware of possible rounding differences.)

Looking for a copy of my Revenge tool

Dear Lazyweb,

If anyone happens to have a copy of the Revenge (Radeon Reverse-Engineering Tool) Git repository, tarball, or code in any format, please comment on this post.

I know one released tarball was named "revenge-1.0.1.tar.gz", but it is unfortunately lost due to the home directories being lost on people.freedesktop.org. I believe there were newer versions, too.

I am reasonably (~90%) sure that I have the Git repository stored on one of my computers, unfortunately the computer in question is currently half the world away, and not online.

Perhaps this post will serve as a reminder to backup your code in more than one location (excluding your workstation.) Yeah, my bad. :-(

Underwater ultrasonic data modulation?

I'm currently looking for a bit of a combination hardware and software project to fill the boredom, so I've been thinking about underwater ROV's. Traditionally these use a surface tether for command communication (presumably with some basic protocol) and a feed from the camera and sensors.

I'm wondering what kind of distance I could get with modulated ultrasonic transducers?

I am quite sure how to design a suitable protocol; in fact I can reuse a lot of the bit-message code used in Quake 3 (there are lots of gems in there.) That provides me with compact messages, and with Huffman compression and an optimized table (based on either simulated or real-world packet capture) the compression ratio becomes pretty good. I think it would even be possible to send the surface a low-resolution/low-FPS video feed, while recording the high-resolution real-time feed to a solid-state drive.

The challenging part would be modulating the data; I have no idea how to choose a carrier frequency and modulation scheme for low-frequency (longer range, less ambient noise) ultrasonic transducers.

Furthermore, assuming the ROV and surface use the same frequency, the link would be half-duplex. This should be fine in theory as the protocol could be designed around this, but ultrasonic is still sound, so picking up an echo is a definite possibility (less so in open water.) I don't see this being too much of a problem (famous last words) because the protocol would be designed to be inherently unreliable: packet sequence number checking, CRC check, sanity check on values.

Far more concerning would be the potential to output too much power and thus be damaging to divers ears underwater. I guess that would just be a matter of capping the output power at the maximum exposure limit for the length of the dive, minus an N percent safety margin.

At least those Full Face Mask underwater communication systems seem to work very well for voice, and do not have any exposure limits that I know about. Quick Google search shows one rated for "50 to 500 meters depending on Sea Conditions and noise levels." Of course, this is voice which is much higher bandwidth than a simple command stream and perhaps 640x480 compressed 1 FPS video.

Anyone out there know about modulation schemes? There's a little on Google, but not too much; possibly I don't know what I'm looking for, though.

Just a random brain-dump idea I've been thinking over; at least writing this post breaks the boredom somewhat and might even motivate me to work on code for the sinking ship that is Nokia. Last I checked the stock was down ~20% and dropping since Stephen Elop's announcement. Ah, back to my general state of pessimistic realism.

Saturday, January 29, 2011

!@#$ing drunkards outside...

Yet another early morning reminder of how much I dislike New Zealand and it's people...

I think if I should ever manage to return to living in Finland I'm going to buy our team many rounds of beer. See you guys sometime in the next few decades. :(