codeblog http://tpreclik.dyndns.org/codeblog Sat, 08 Jan 2011 15:40:52 +0000 en hourly 1 http://wordpress.org/?v=3.2.1 Ranking and Unranking of Rubik’s cubes http://tpreclik.dyndns.org/codeblog/?p=66 http://tpreclik.dyndns.org/codeblog/?p=66#comments Tue, 26 Feb 2008 21:06:50 +0000 Tobias Preclik http://tobias.preclik.de/codeblog/?p=66

Have you ever seen someone solving the Rubik’s cube within a minute? I did and I was amazed! Afterwards I walked through Lissabon staring at the cube and desperately trying to figure out how to solve it. By now I finally learned how to proceed. You can find an intuitive approach on Lars Petrus’ website. As with many complicated toys a lot of math is involved. In this case a lot of group theory and combinatorics. But actually I am no big fan of sober complicated math. Nevertheless I was eager to tinker with the cube and began by writing a program which had an explicit representation of the cubes’ face colors and operations to arbitrarily rotate the sides. The explicit representation is good if you want to modify the cube. However often it is just necessary to identify a particular cube state. Imagine you want to enumerate all cube states starting from the solution then you can use for example a breadth-first search. As with general graphs you need to remember states which you already encountered. For that purpose you should use a more compact representation of the cube. Suppose there are $n$ Rubik’s cube states in total, then the minimum number of bits to represent a state is clearly $\lceil \log_2 n \rceil$. You achieve that goal if you are able to assign a unique number $x \in \{0, \dots, n - 1\}$ to each different possible cube state. This number is also called rank and the conversion from the explicit representation to the rank is referred to as ranking. The reverse is of course unranking.

The Rubik’s cube consists of 12 edge pieces, 8 corner pieces and a fixed cross with the center pieces at the end of the axes. Suppose you disassemble the cube and reassemble it, then you can choose an arbitrary permutation of the edges as well as the corners resulting in $12! \cdot 8!$ different relative positions of the pieces (which are often also called cubies). Additionally you can choose the orientation of the pieces. The edge pieces have two possible orientations each and the corner pieces three. Thus the total number of Rubik’s cube states is $12! \cdot 8! \cdot 3^8 \cdot 2^{12}$. However only 1/12 of those states can be solved – we will get to that later. Assuming we can determine the orientations of the edges $\bar{o}_i \in \{0, 1\}$ (flipped or not), then encoding them in a single number is fairly easy. Each edge position $i$ corresponds to a single bit. If the edge is flipped then we set the corresponding bit. For corner orientations $\hat{o}_i \in \{0, 1, 2\}$ we proceed actually the same way but this time we use a number representation with basis three: $\hat{o}_{7} \cdot 3^{7} + \dots + \hat{o}_1 \cdot 3 + \hat{o}_0$

We have encoded the edge and corner orientations but still need to encode their permutations. To do that each piece gets a unique id so edge ids range from 0 to 11 and corner ids from 0 to 7. To facilitate explanation we also introduce positions which have ids just like the pieces. The position with id $x$ equals the position where the piece with id $x$ is located when the cube is in the solved state. Now it is easy to determine the permutations of the edges and corners respectively. Just iterate over all positions and check the ids of the pieces there. The result will be a permutation for the edges (e.g. (0, 6, 4, 7, 1, 3, 2, 5)) as well as for the corners. Now we need to rank both permutations. If we can enumerate all possible permutations systematically then we can assign ranks by numbering the permutations serially. Often the permutations are enumerated lexicographically which leads to the following for size 3:

Rank Permutations
0

1

2

3

4

5

 (0, 1, 2)

(0, 2, 1)

(1, 0, 2)

(1, 2, 0)

(2, 0, 1)

(2, 1, 0)

The lexiographic ranking could be described by the following recursion:

$rank\left( (p_0), 1 \right) = 0$
$rank((p_0, \dots, p_{n-1}), n) = p_0 \cdot (n-1)! + rank( (q_1, \dots, q_{n-1}), n - 1)$
\textnormal{where}\quad$q_i = \begin{cases}p_i - 1 & \textnormal{if}~p_i > p_0\\ p_i & \textnormal{else}\end{cases}$

However a different ordering will come in handy later – we will need an ordering where every second permutation is even and every other odd. Even permutations can always be generated by an even number of transpositions. It can be proved that it is not possible to generate an even permutation with an odd number of transpositions and the other way round. The sign or signature of a permutation $p$ is defined as:

$sgn(p) = \begin{cases}+1 & \textnormal{if}~p~\textnormal{even}\\-1 & \textnormal{else}\end{cases}$

Thus we need a ranking with an alternating sign. Let us try an induction approach. Assume we have such a ranking for permutations of size $n-1$, how can we extend it without losing the property of the alternating sign? In principle we need to take each of the permutations and insert the number $n-1$ at every possible place of the permutation which equals to $n$ possibilities. If we insert it last, the new permutation will have the same number of transpositions as the previous permutation because the number $n$ is at it’s correct place. If we insert it one place to the left, then we need an additional transposition. For each place further left we need another transposition. For example if we start with the even permutation (2, 0, 1) and append 3 to extend it to size 4, (2, 0, 1, 3) is again even. However as we shift the 3 to the left, the sign of the permutation will alternate. So in summary we can extend each permutation of size $n-1$ to $n$ permutations of size $n$ with alternating sign. If $n$ is odd we have a proper ranking at hand. However if it is even, then every n-th sign will repeat once. To remedy this deficiency we need to reverse the $n$ extended permutations of every second permutation we extend if $n$ is even. Have a look at the following table which demonstrates the ranking with alternating sign:

Rank Permutations Rank Permutations Rank Permutations
0 (0) 0

1		 (0, 1)

(1, 0)		 0

1

2

3

4

5

 (0, 1, 2)

(0, 2, 1)

(2, 0, 1)

(1, 0, 2)

(1, 2, 0)

(2, 1, 0)
Rank Permutations Rank Permutations Rank Permutations
0

1

2

3

4

5

6

7

 (0, 1, 2, 3)

(0, 1, 3, 2)

(0, 3, 1, 2)

(3, 0, 1, 2)

(3, 0, 2, 1)

(0, 3, 2, 1)

(0, 2, 3, 1)

(0, 2, 1, 3)

 8

9

10

11

12

13

14

15

 (2, 0, 1, 3)

(2, 0, 3, 1)

(2, 3, 0, 1)

(3, 2, 0, 1)

(3, 1, 0, 2)

(1, 3, 0, 2)

(1, 0, 3, 2)

(1, 0, 2, 3)

 16

17

18

19

20

21

22

23

 (1, 2, 0, 3)

(1, 2, 3, 0)

(1, 3, 2, 0)

(3, 1, 2, 0)

(3, 2, 1, 0)

(2, 3, 1, 0)

(2, 1, 3, 0)

(2, 1, 0, 3)

This scheme results in the following recursion:

\footnotesize rank\left( (p_0), 1 \right) = 0\\ rank\left( (p_0, \dots, p_{n-1}), n \right) =\\n \cdot rank\left( (p_0, \dots, p_{i-1}, p_{i+1}, \dots, p_{n-1}), n-1 \right) +\\ \begin{cases}i & \textnormal{if}~rank\left( (p_0, \dots, p_{i-1}, p_{i+1}, \dots, p_{n-1}), n-1 \right)~\textnormal{odd}~\land~n~\textnormal{even}\\ n-1-i & \textnormal{else}\end{cases}\\ \textnormal{where}~p_i = n-1

So what did we achieve already? We have an encoding of the edge orientations (\bar{o} \in \{0, \dots, 2^{12}-1\}), the corner orientations (\hat{o} \in \{0, \dots, 3^{8}-1\}), the edge permutation (\bar{p} \in \{0, \dots, 12!-1\}) and the corner permutation (\hat{p} \in \{0, \dots, 8!-1\}). If we just take the binary representations and concatenate them we reach an encoding length of $\lceil \log_2 2^{12} \rceil + \lceil \log_2 3^{8} \rceil + \lceil \log_2 12! \rceil + \lceil \log_2 8! \rceil$ = 12 + 13 + 29 + 16 = 70bits which already fits in 9 bytes. However we can easily improve upon that by using a mixed base encoding: The tupel $(\bar{o}, \hat{o}, \bar{p}, \hat{p})$ can be encoded as $\bar{o} \cdot (3^8 \cdot 12! \cdot 8!) + \hat{o} \cdot (12! \cdot 8!) + \bar{p} \cdot 8! + \hat{p}$ which results in a number ranging from 0 to $2^{12} \cdot 3^8 \cdot 12! \cdot 8! - 1$.

If we want to be able to encode all possible Rubik’s cube states we are done. However if we only want to identify solvable states we can save some more bits. As already mentioned before only 1 in 12 states can be solved. This fact is well known and the following explanations thereof are merely the rephrased laws as they are presented on Ryan Heise’s website. The first restriction is due to the number of flipped edges. When starting from the solved stated no matter what you do there will always be an even number of flipped edges. For this to be true we have to chose a frame of reference which suits our needs. Let us define an edge to be not flipped if we can position it correctly by only rotating the front (F), left (L), back (B) and right (R) sides. Therefore all rotations of the F, L, B or R sides will never flip any edges. However when rotating the top (T) or down (D) side of the cube, four edges are flipped at once. Consequently we can safely omit a bit of the encoded edge orientations because we can always reconstruct it by counting the number of bits set. If the number of flipped edges is odd we know that the omitted edge was also flipped.

The corner orientations are also restricted. Each of the corner pieces can have three orientations. To be able to identify the orientation state let’s use the sticker colors: A corner has always either a red (x)or an orange sticker. If that sticker either points upwards or downwards the corner is defined to be correctly oriented and we assign the orientation 0. If we need to twist the corner once counterclockwise to be correctly oriented we assign orientation 1 and otherwise 2. With this frame of reference it is easy to see that the sum over the corner orientations remains equal if we only rotate the top and down side of the cube. If we rotate any other side, the orientations of all four affected corners change. Two corner orientations increase by two and the others by one (modulo 3). So the total sum of corner orientations stays always 0 \equiv 1+1+2+2 \mod 3. Again we can omit information – this time we just divide the encoding of the corner orientation by 3 and round off. We can reconstruct it any time by multiplying by 3 and adding 0, 1 or 2 to make it divisible by 3.

The last and trickiest part is the restriction of the edge and corner permutations. As mentioned earlier you can decompose every permutation into a sequence of transpositions. The number of edge transpositions plus the number of corner transpositions is preserved by any move to be even. Thus if the edge permutation is even, the corner permutation is even and likewise if the edge permutation is odd, the corner permutation is also odd. Since the encoding of the edge and corner permutations were constructed to have an alternating sign (see above) the rank is even if and only if the permutation is even. That’s why we can skip the least significant bit of either of the permutations ranks. It can be reconstructed by copying the least significant bit of the other permutation rank.

So the overall number of bits required is $\lceil \log_2 \frac{2^{12} \cdot 3^8 \cdot 12! \cdot 8!}{2 \cdot 3 \cdot 3}\rceil = 66$. Unfortunately this still requires 9 bytes. However we still might be able to improve upon that by only ranking asymmetric, solvable Rubik’s cube states. For instance if you intend to compute the number of states reachable from the solved state which can be optimally solved in $i$ moves, you can count instead only the asymmetric states because all symmetric ones can be solved with exactly the same number of moves. Since the numbers in this sequences get quickly very big you better safe every possible byte/bit you need to remember. Later you can reconstruct the true number of reachable states. The sequence I talk about can be also found in the The On-Line Encyclopedia of Integer Sequences: Number of positions that the 3 X 3 X 3 Rubik cube puzzle can be in after exactly n moves. But that’s a whole different story. Have fun!

  • S. Skiena, The algorithm design manual, New York, NY, USA: Springer-Verlag New York, Inc., 1998.
    [Bibtex] 
    @book{skiena98,
  author = {Steven S. Skiena},
  title = {The algorithm design manual},
  year = {1998},
  isbn = {0-387-94860-0},
  publisher = {Springer-Verlag New York, Inc.},
  address = {New York, NY, USA},
  URL = {http://www2.toki.or.id/book/AlgDesignManual/}
}
  • R. Heise, Laws of the cube.
    [Bibtex] 
    @misc{heise,
  author = {Ryan Heise},
  title = {Laws of the cube},
  URL = {http://www.ryanheise.com/cube/cube_laws.html}
}
]]> http://tpreclik.dyndns.org/codeblog/?feed=rss2&p=66 1 Digital Television with Linux http://tpreclik.dyndns.org/codeblog/?p=28 http://tpreclik.dyndns.org/codeblog/?p=28#comments Tue, 10 Apr 2007 14:15:07 +0000 Tobias Preclik http://tobias.preclik.de/blog/?p=28 Analog TV is dead. Well almost. Digital television is state of the art. In 2005 the terrestrial digital video broadcasting (DVB-T) in the region Nuremberg in Germany started. Therefore I decided to buy a digital receiver some time ago. I chose an external receiver connected via USB 2.0 manufactured by AVerMedia which was branded as: “AVerTV DVB-T USB2.0″

To get some more information let us use the usbutils.


# lsusb -v
...
Bus 001 Device 003: ID 07ca:a801 AVerMedia Technologies, Inc.
Device Descriptor:
bLength 18
bDescriptorType 1
bcdUSB 2.00
bDeviceClass 0 (Defined at Interface level)
bDeviceSubClass 0
bDeviceProtocol 0
bMaxPacketSize0 64
idVendor 0x07ca AVerMedia Technologies, Inc.
idProduct 0xa801
bcdDevice 0.00
iManufacturer 1 AVerTV
iProduct 2 A801
iSerial 0
bNumConfigurations 1
...

Every digital as well as analog television receiver has a tuner module integerated. A little research revealed that the “AVerTV DVB-T USB2.0 (A801)” has a DiB3000M-C/P tuner (also called frontend). Since the device is a so called budget – in contrast to a full featured – dvb-t receiver, it has no MPEG decoder chip to decode the compressed video signal in hardware. Thus the receiver is cheaper but the decoding has to be done by the host cpu itself which is quite computationally expensive.

System Configuration

The AVerTV DVB-T receiver needs to load a firmware when it is plugged into the usb port. You need to download this firmware and place it into the appropriate directory. Download it from linuxtv.org. Grab the latest dvb-usb-avertv-a800-*.fw file and move it into your distributions firmware directory (in Gentoo for example /lib/firmware).

As usual you need the appropriate device drivers for the receiver. You will also want USB 2.0 support (EHCI HCD) and firmware loading. If you compiled a customized kernel you need to check the following options in your kernel configuration: 

→ Device Drivers
  → Multimedia devices
    → Digital Video Broadcasting Devices
      → DVB For Linux (CONFIG_DVB=y)
      → DVB Core Support (CONFIG_DVB_CORE=y/m)
      → Support for various USB DVB devices (CONFIG_DVB_USB=y/m)
      → AVerMedia AverTV DVB-T USB 2.0 (A800) (CONFIG_DVB_USB_A800=y/m)
      → DiBcom USB DVB-T devices (based on the DiB3000M-C/P) (CONFIG_DVB_USB_DIBUSB_MC=y/m)
      → Customise DVB Frontends
        → DiBcom 3000 M-C (CONFIG_DVB_DIB3000MC=y/m)

For further instructions refer to your distributions manuals for compiling your own kernel. Most distributions probably ship with kernels which have those kernel modules readily compiled anyway. Just try modprobing them:

# modprobe dvb-usb-a800

All other necessary kernel modules will be loaded automatically. The kernel log should now report something like:


# dmesg | tail
usb 1-3: new high speed USB device using ehci_hcd and address 6
usb 1-3: configuration #1 chosen from 1 choice
dvb-usb: found a 'AVerMedia AverTV DVB-T USB 2.0 (A800)' in warm state.
dvb-usb: will pass the complete MPEG2 transport stream to the software demuxer.
DVB: registering new adapter (AVerMedia AverTV DVB-T USB 2.0 (A800)).
DVB: registering frontend 0 (DiBcom 3000MC/P)...
input: IR-receiver inside an USB DVB receiver as /class/input/input5
dvb-usb: schedule remote query interval to 150 msecs.
dvb-usb: AVerMedia AverTV DVB-T USB 2.0 (A800) successfully initialized and connected.

DVB Television Software

To watch television you now need the appropriate software. The DVB-T support in TV applications under Linux is spare. Mainly there is the giant beast MythTV and the little beasts MPlayer and VDR. For installing these either use the package system of your distribution or compile them by hand. In either case make sure the DVB-T support is activated. If you intend to use MythTV be sure you read the requirements first.

MythTV

I had little success with setting up MythTV. This with partially due to some broken QT library dependencies. The most scary requirement is the MySQL database though which is certainly not what I expected for a TV application.

MPlayer

I will describe MPlayer here since it is way easier to configure than MythTV for example and is one of the most powerful media players out there. Unfortunately DVB-T tuning is fairly slow and channel switching not very convenient since a new window is opened each time when switching channels. Furthermore audio and video tend to get out of sync. Nevertheless it is probably the easiest to setup.

After you have installed MPlayer you need to scan for TV channels. Therefore you can use the linuxtv-dvb-apps. Install them and run dvbscan once without parameters. It will list many files, which contain information about the frequencies used in many DVB-T areas. Select the filename appropriate for you and run dvbscan with the file as a parameter. Redirect the standard output to a file. If dvbscan ran successfully you can move the output file to the MPlayer’s configuration directory. For example:


# dvbscan /usr/share/dvb/dvb-t/de-Nuernberg > new-channels.conf
# mv new-channels.conf ~/.mplayer/channels.conf

To get a list of available channel names try this:


# awk -F: '{ print $1 }' ~/.mplayer/channels.conf

To watch a channel start MPlayer with "dvb://channel name" as a parameter. To switch channels you can use the keys h and k. If you have some more cpu time to spare you can add a deinterlace filter with -vf pp=fd to the command line:


# mplayer "dvb://channel name" -vf pp=fd

VDR

The aim of the VDR project was originally to build your own digital satellite receiver and video disk recorder – hence the name. But the software is flexible enough to be used as a simple TV application on your desktop. In the background a daemon runs which operates the DVB device and can supply the video stream.

Since I bought a budget receiver the daemon must decode the MPEG2 stream from the device. Therefore the separate plugin Softdevice exists. The Softdevice plugin takes the stream decodes it and usually directly passes the images to the framebuffer. For our purpose – watching TV on our day-to-day desktop environment – the video image will be written to shared memory instead. A frontend application will get the images from the shared memory and display them inside a window. The Softdevice plugin provides exactly such a frontend which is called ShmClient. The configuration in Gentoo can be done in few steps:


$ # Install the backend
$ emerge vdr
...
$ # Install the Softdevice plugin
$ emerge vdr-softdevice
...
$ # Activate the Softdevice plugin
$ emerge --config vdr-softdevice
...
$ # Configure the plugin to decode into shared memory
$ echo SOFTDEVICE_VIDEO_OUT="shm" >> /etc/conf.d/vdr.softdevice

Warning Sign Note: The Softdevice plugin version 0.3.1 contains a bug which prevents users with 64-bit operating systems from using the keyboard. The bug is fixed in newer versions (currently only CVS).

As with MPlayer we must scan for channels now. Again we will use the dvbscan application but the output format is different now. For further instructions refer to the above section.


$ dvbscan -o vdr /usr/share/dvb/dvb-t/de-Nuernberg > new-channels.conf
$ mv new-channels.conf /etc/vdr/channels.conf

Now we are ready to test our setup:


$ # Start the background daemon
$ /etc/init.d/vdr start
$ # Start the TV client application
$ ShmClient

When starting for the first time you will be prompted to configure your key bindings. The results will be stored into /etc/vdr/remote.conf. In case something went wrong delete it and restart the daemon – you will be prompted for the key bindings again. If everything worked out you can add the daemon to the default runlevel in order that it will be started each time the computer boots. Furthermore the kernel module should be loaded automatically in the future. In Gentoo these steps require:


$ # Add VDR to the default runlevel
$ rc-update add vdr default
$ # Automatically load the device driver
$ echo dvb-usb-a800 >> /etc/modules.autoload.d/kernel-2.6

VDR has many more nifty plugins. Especially the remote plugin comes in handy if you intend to control the TV application by an infrared remote-control. Look at the dmesg output above. It tells us that a new input device (“IR-receiver inside an USB DVB receiver” in this case) has been registered as /class/input/input5. All input devices (mice, keyboards, infrared receivers) get a device node usually called /dev/input/eventX (with an appended number X) and all those input devices can be used by the remote plugin. Unfortunately it is not always clear which name is assigned to the device thus a custom udev rule is needed which assigns a static name like /dev/input/dvb-ir. Refer to the VDR Wiki for further instructions. For me the following did the trick:


$ # Add custom udev rule which basically says: Add a symbolic link called "/dev/input/dvb-ir" as soon as you encounter a device
which is normally called input with something appended and whose device name is "IR-receiver ..."
$ echo 'KERNELS=="input*", ATTRS{name}=="IR-receiver inside an USB DVB receiver", SYMLINK+="input/dvb-ir"' >> /etc/udev/rules.d/10-local.rules

To install and configure the remote plugin in Gentoo:


$ # Install the remote plugin
$ emerge vdr-remote
...
$ # Activate the remote plugin
$ emerge --config vdr-remote
...
$ # Instruct the plugin to use the infrared device (you can also leave this alone then the device will be hopefully autodetected and it takes some more time for the VDR daemon to start up)
$ echo 'REMOTE_PLUGIN_INPUT_DEVICE="/dev/input/dvb-ir"' >> /etc/conf.d/vdr.remote
$ # Restart the VDR daemon
$ /etc/init.d/vdr restart

As with the keyboard you will be prompted for the remote-controller key bindings when the daemon restarts. Again those will be appended to /etc/vdr/remote.conf. The entries will look like:

remote-dvb-ir.Mute 0000000100010071

The first part (remote-) refers to the VDR plugin, the second part (dvb-ir.) specifies the input device, the third part (Mute) the action name and the last part is the key code which is assigned to the action. If you want to repeat the setup of the remote control bindings, remove all entries which start with remote-dvb-ir..

The VDR application is my TV application of choice. It is stable, feature-rich and good to handle. If I missed some steps above or you think something should be added please drop me a note.

]]> http://tpreclik.dyndns.org/codeblog/?feed=rss2&p=28 1 Programming the Game Boy http://tpreclik.dyndns.org/codeblog/?p=16 http://tpreclik.dyndns.org/codeblog/?p=16#comments Tue, 06 Mar 2007 21:42:57 +0000 Tobias Preclik http://tobias.preclik.de/blog/?p=16 The original Game Boy has a modified 8-bit Z80 micro processing unit which is running at about 4.2 MHz. It features a serial port (link cable) for multiplayer games, a sound unit and a screen with an resolution of 160×144px. In 2001 a major successor was released: The Game Boy Advance. It relys upon an 32-bit ARM processor running at 16.8MHz. For backwards compatibility a Z80 is integrated clocked at 8.4MHz.

A long time ago (back in school) I read about a Game Boy programming device. I was quite amazed and immediately knew “I want such a device!”. Later on in the first term of my computer-science studies I met Johannes Bauer who has very good electronics knowledge. I told him about that device and the project was born. We ordered the parts immediately. Though the assembling of the programmer began two years later… Well now we finished it and the Game Boy is quite out of date – but who cares? At least they are cheaper now…

The page where I read about the programmer is still available. It is Lukas Zimmermann’s homepage. There you can find the circuit diagram, the pcb layout and a complete list of necessary parts. There is only one uncommon part which is hard to find: The Game Boy cartridge connector. Therefore we bought a more or less working Game Boy at a junk market for about 2€.

We disassembled it and heated the circuit board on which the connector was attached using a heat gun. The board was trash afterwards but the connector was quite safe.

Next we had to etch the circuit board. We printed the pcb layout using a laser printer onto a sheet of magazine paper. Afterwards we taped the paper to a copper laminated board. Now the laser printer toner must be transfered from the sheet of paper to the board. Therefore we used a custom pouch laminator which Johannes modified himself earlier – hail to the king, baby! If you do not have such a device ready at hand ;) just search for “homemade pcbs” to find some introducing informations. Anyway, the circuit paths should now be protected by the laser printed toner and the board is ready to be etched. Besides we also tried to use exposure and photoresist boards but we had no luck with that. The toner transfer method turned out to be way more accurate.

When the board is ready you may want to have a close look at the circuit paths again. Check each and every pair of circuit path endpoints for connectivity. To do that a continuity tester with an integrated beeper comes in very handy. If you double-checked the paths you can start to populate the board. First solder the bridges and afterwards the parts since some of the bridges are situated below the ICs. Besides – before you make the same mistake as we did – Lukas provides a layout including the connector and one excluding the connector, so be aware of that. Instead of etching another board we chose to solder a ribbon cable directly to the connector.

I concealed one nasty detail so far. To program the Game Boy it is not sufficient to own a game. The game volumes (so called cartridges) have a ROM soldered which means if you want to replace the software you have to replace the read-only memory by a flash memory. Reiner Ziegler describes on his homepage which game catridges can be modified and by which flash memories the ROM must be replaced. If you need a list of which game has which hardware features look here. We first tried to replace the ROM of an MBC1 cartridge by an AT29C040A flash which turned out to be a complete flop since it had a different sector size as the one Reiner Ziegler suggested. But the second attempt with an AM29F040B-90 flash in a PLCC package was a success.

However the first hurdle is to open the cartridge case – it has an uncommon screw. I cannot remember what we used for this purpose. Then the ROM chip needs to be removed carefully. Therefore we distributed some solder across the pins and heated it until one side of the ROM could be lifted. After this has been repeated for the second side the remaining solder can be removed using for example a desoldering wick. After that bend the pins of the flash chip to the outside and solder it slightly rotated, as Reiner Ziegler describes it. The rest is a sisyphean challenge.

If you come that far it is time to download the software readplus which communicates with the programming device. It is available for Windows and for Linux. Please be aware that it does not check the command line arguments thoroughly – it took me hours to figure out that it expects “1″ instead of “/dev/parport0″ as the parallel port interface option. Never mind. Readplus must be run with administrator privileges/as root since it needs direct access to the parallel port. That’s why you also need the ppdev kernel module loaded on linux. For the first attempt you will want to run the “cartridge reader test”:


# ./readplus -t

Like that you can check each of the connector pins of your programming device if the correct levels are applied. Be aware that if you measure at the back of the connector the pins at the front can still have no contact – which happened in our case… If all goes well you can try to program the cartridge or alternatively if you have not yet modified a cartridge read one of your Game Boy games. The readplus software has a bug in the checksum calculation so don’t get worried. Instead you can double-check the md5sum with a ROM image which you downloaded (or fix the checksum calculation ;) ).

The Game Boy can be programmed either in Assembler or in C. If you want to code in C you can use the Game Boy Development Kit (GBDK). It comes with a libc and other helpful library functions. A simple hello world sample code can be done in few lines. For example:


#include <gb/gb.h>
#include <stdio.h>

int main() {
puts(“Hello world…”);
puts(“Press any key to continue…”);
waitpad(0xFF);
waitpadup();

puts(“See you later!”);

return 0;
}

The code can be compiled and programmed to the cartridge for example using…


# lcc -o helloworld.gb helloworld.c
# readplus -p helloworld.gb

Good luck!

]]> http://tpreclik.dyndns.org/codeblog/?feed=rss2&p=16 4 Unwrap sphere textures http://tpreclik.dyndns.org/codeblog/?p=9 http://tpreclik.dyndns.org/codeblog/?p=9#comments Sun, 11 Feb 2007 15:49:38 +0000 Tobias Preclik http://tobias.preclik.de/blog/?p=9 When rendering 3d graphics today there exists an underlying geometric model which is visually spiced up by wrapping texture bitmaps round the basic surface. So each time a pixel of the object is drawn on the screen the geometric three dimensional coordinates are known. To derive the pixel’s color the coordinates must be mapped to a point in the texture image. Therefore texture coordinates are stored at each vertex of the geometric model. When drawing pixels which are not vertices the texture coordinates are interpolated using the neighbouring vertices. But where do those texture coordinates come from? There are basically two possibilities. Either the coordinates are specified manually (for example with the help of the modelling software) or the coordinates are generated automagically.

texture-on-sphere.pngLet’s have a deeper look at how an automatic mapping might work with a sphere. To specify the coordinates in the texture image, $u \in [0; 1]$ is used for the horizontal direction and $v \in [0; 1]$ for the vertical direction. For the sphere two coordinates $\theta$ and $\phi$ are also enough to mark a point on the surface (remember geographical latitude and longitude). The following equations relate spherical coordinates and cartesian coordinates:

$\left( \begin{array}{c} x \\ y \\ z \end{array} \right) = r \left( \begin{array}{c} \sin \theta \cos \phi \\ \sin \theta \sin \phi \\ \cos \theta \end{array} \right) \qquad \theta \in [0; \pi], \phi \in [0; 2 \pi] $

So a possible mapping for the $(\theta, \phi)$ to the $(u, v)$ coordinates is easy to define – just normalize the range:

$u = \frac{\phi}{2 \pi} \qquad v = \frac{\theta}{\pi}$

Back to our above scenario. To draw a pixel of the sphere object the color needs to be determined. So the cartesian coordinates $(x, y, z)$ are converted to sphere coordinates $(\theta, \phi)$. Those can be used to convert to the texture coordinates $(u, v)$. By looking up the color in the texture image at position $(u, v)$ we know the pixel’s color and draw it to the screen buffer.

Now let’s reverse this process. We start with a readily rendered scene or an ordinary photo. For example some ball or orange is depicted. How can we generate the texture image? For each pixel in the texture we start with the $(u, v)$ coordinates, convert them to sphere coordinates and finally calculate the cartesian coordinates.

$\left( \begin{array}{c} x \\ y \\ z \end{array} \right) = \left( \begin{array}{c} c_x \\ c_y \\ c_z \end{array} \right) + r \left( \begin{array}{c} \sin \left( v \pi \right) \cos \left( u \pi \right) \\ \sin \left( v \pi \right) \sin \left( u \pi \right) \\ \cos \left( v \pi \right) \end{array} \right)$

Since the back of the sphere is missing the above equations use $\theta = u \pi$ instead of $\theta = u 2 \pi $.
Up until now we skipped an important step. The three dimensional coordinates have to be somehow mapped to the screen which requires a projection from three dimensions to two. There exist different types of projections. For simplicity let’s stick with the easiest one: Orthographic projection. To project the sphere to the screen the depth coordinate is thrown away. In our case the second component. Otherwise not all pixels of the projected image are used to generate the texture.

In my subversion repository you can find an implementation which is capable of reading several image formats and writing a png file (link). The command line application requires the SDL, SDL_image and libpng libraries (the latter two dependencies can be removed quite easily). A possible execution might look like:

# make
...
# ./untexture
usage: untexture <bitmap> <centerx> <centery> <radius>
# ./untexture res/orange.jpg 1234 1337 311

Some appetizers:

An orange A generated orange texture
tennisball.jpg tennisball-texture.jpg
]]> http://tpreclik.dyndns.org/codeblog/?feed=rss2&p=9 5 Wake-on-Lan http://tpreclik.dyndns.org/codeblog/?p=7 http://tpreclik.dyndns.org/codeblog/?p=7#comments Fri, 09 Feb 2007 15:32:50 +0000 Tobias Preclik http://tobias.preclik.de/blog/?p=7 I like accessing my machine at home from university. I tend to forget to commit my source code changes or upload other import files. Thus it comes in handy if I have secure shell access. But what if I forgot to switch on the computer? Cycling home 30 minutes, press the power button, cycling to university again. Since I am usually late every morning I forget to press the power button quite often. Since 1h is just too much time wasted there must be a better solution.

There exist several ways to remotely switch on your computer: Wake-on-Ring/Modem, Wake-on-Lan, Wake-on-Pci, …

Since I can reach my home network from university Wake-on-Lan fits my needs. I have a Asus A8N-E mainboard which supports as most modern mainboards do WOL. Be sure to activate it in the BIOS settings. For my mainboard I had to activate Wake-on-Pci (there exists no seperate WOL option though it has an onboard ethernet controller).

Different network controllers support different wake-up modes. To find out the supported modes of your network controller and to activate WOL you may want to install ethtool.

# ethtool eth0
Settings for eth0:
Supported ports: [ MII ]
Supported link modes:   10baseT/Half 10baseT/Full
100baseT/Half 100baseT/Full
1000baseT/Full
Supports auto-negotiation: Yes
Advertised link modes:  10baseT/Half 10baseT/Full
100baseT/Half 100baseT/Full
1000baseT/Full
Advertised auto-negotiation: Yes
Speed: 100Mb/s
Duplex: Full
Port: MII
PHYAD: 1
Transceiver: external
Auto-negotiation: on
Supports Wake-on: g
Wake-on: d
Link detected: yes

Have a look at the line “Supports Wake-on:” line. It contains all supported modes abbreviated by a letter. Have a look at the ethtool manpage for further explanations. In principal the network card can trigger wake-signals on different events: Physical activity (p), broadcast messages (b), arp packets (a), … or so called MagicPackets (g). Which modes are supported depends on the hardware and the driver. For example the 3Com Vortex device driver requires that you explicitly activate Wake-on-Lan support when loading the kernel module.
MagicPackets are network packets which use most often UDP as a transport protocol and contain as a payload FF FF FF FF FF FF followed by 16 times the MAC address of the network controller to wakeup. Of course everybody (in the local area network) can craft such a special packet and send it to your computer. That’s why there exist MagicPackets which have a password appended which is checked by your network controller. Forget about it – anyone who is able to send those packets to you is able to eavesdrop the MagicPacket’s password!

To activate Wake-on-Lan you must configure your network controller each time before you shutdown your computer. To do that by hand you can use ethtool:

# ethtool -s eth0 wol g

Before you shutdown your computer write down your network controllers MAC address:

# ifconfig eth0 | grep HWaddr
eth0      Link encap:Ethernet  HWaddr 00:C0:1D:C0:FF:EE

Now you can shut it down. To wakeup the computer you need to send the MagicPacket. Therefore several different utilities exist. I am using etherwake.

# ether-wake 00:C0:1D:C0:FF:EE

If that does not wake the machine, maybe the network interfaces were shut down while powering off your computer. To prevent this, have a look at your distributions documentation or search the internet. For Gentoo I had to set the option RC_DOWN_INTERFACE to no in /etc/conf.d/rc. It controls if the parameter i will be passed to the /sbin/halt command.
If it worked you will probably want to activate WOL on every shutdown process. For Gentoo this can be achieved by adding the above ethtool command to /etc/conf.d/local.stop. Each time the computer starts the wake mode of the network controller will be reset to disabled. If you are dualbooting with Windows you will also have to activate the WOL features in Windows. Open the device manager and go to the preferences of your network controller where you can activate WOL. The checkbox with the cryptical description is what you want to check if you want to use MagicPackets.
So what can we do now? If your router allows secure shell access, login there from remote and send a MagicPacket to your computer. Alternatively you can use WOL for example if you have a server in your LAN and want to shut it down or put it into standby when it is idle. Then everytime someone tries to access the machine it will automatically wakeup. In this case you will probably not use MagicPackets but wake on ARP packets.

]]> http://tpreclik.dyndns.org/codeblog/?feed=rss2&p=7 5 Heaps of size n http://tpreclik.dyndns.org/codeblog/?p=4 http://tpreclik.dyndns.org/codeblog/?p=4#comments Fri, 09 Feb 2007 13:53:49 +0000 Tobias Preclik http://tobias.preclik.de/blog/?p=4 heap_a.pngheap_b.pngThe ordering of the elements in a heap of size $n$ is not unique. That is no magic observation. Have a look at the heap images. Both contain the same elements, both fulfill the heap property and are different. So how many different orderings are there? To answer this question we need some observations. The easiest one: The root at the very top of the heap contains the biggest element. Both children in the binary tree are again heaps – but with how many elements?

Let’s have a deeper look at a typical binary tree (in context of a heap): Heaps usually require that the binary tree is balanced and nearly complete. Which means that on level $i$ (all nodes that are i edges away from root) there exist $2^i$ nodes. There is one exception. The last level may contain less or equal than $2^i$ elements but those must be filled from the left to the right. So how many elements has a complete binary heap where the last level has also $2^i$ elements? Assuming that the tree is of height h we can sum up the number of nodes per level: $\sum_{i=0}^{h}2^i = 2^{h+1}-1$.

Let us name the left child of the root node $c_{left}$ and the right one $c_{right}$. Both nodes are again roots of smaller heaps. Both are again nearly complete heaps but with height $h - 1$. If they are complete we can easily calculate the number of elements they contain: $\sum_{i=0}^{h-1}2^i = 2^h-1$. Unfortunately they are not complete since the last level is usually not completely filled. So let’s ignore the last level $h-1$ and calculate the number of elements each of the heaps must at least have: $\sum_{i=0}^{h-2}2^i = 2^{h-1}-1$

Now we must find out how the elements of the last level are distributed to the heap with root $c_{left}$ and the heap with root $c_{right}$. There are $m = n - \sum_{i=0}^{h-1}2^i = n - (2^h - 1)$ elements in the last level (where $n$ is the size of the heap). If the last level is not filled up to the half then all nodes belong to the heap with root $c_{left}$. Otherwise $c_{left}$ gets $\frac{1}{2}2^h$ additional nodes and $c_{right}$ gets $m - \frac{1}{2}2^h$ nodes. In summary this yields:

$n_{left} = \begin{cases}2^{h-1} - 1 + m & \text{if $m \leq \frac{1}{2}2^h$} \\ 2^{h-1} - 1 + \frac{1}{2}2^h & \text{else} \end{cases}$

$n_{right} = \begin{cases}2^{h-1} - 1 & \text{if $m \leq \frac{1}{2}2^h$} \\ 2^{h-1} - 1 + (m - \frac{1}{2}2^h) & \text{else}\end{cases}$

Now we can phrase a preliminary recursion formular. In principal the number of different heaps of size $n$ can be calculated by multiplying the number of different child-heaps. But this still ignores the fact that we can distribute the heap values differently to the left and right heap. In the following formula those permutations are hidden in the factor $f$:

$heapnum(n) = f \cdot heapnum(n_{left}) \cdot heapnum(n_{right})$

To calculate the value $f$ we need to find out, how we can distribute the values of the original heap to the children. We already observed that the largest value is at the top of the heap and thus will never be distributed. So what about the children roots? One of the children heaps must contain the second largest value, otherwise the heap property cannot be fulfilled. This fact leads to two cases: Either the second largest value belongs to the left child-heap or the right child-heap.

Let’s observe the case where the second largest element belongs to the right child-heap. We still have to choose the value for the root of the left child-heap. Since we need at least $n_{left}-1$ smaller values for the rest of the left heap, the $n_{left}$-smallest element is the first one we may choose. The last possible value is the third largest in the heap (where the largest is at the parent root and the second largest at the right child-heap’s root). For each of these roots we may choose the remaining heap values among the values smaller than the chosen root:

$\sum_{i=n_{left}}^{n-2} \binom{i - 1}{n_{left}-1}$

The number of permutations of the right child-heap is fixed independent of the values we chose for the left child-heap. We must always choose $n_{right} -1$ elements among the remaining values, which results in $\binom{n-2-n_{left}}{n_{right}-1}$.

Now let’s have a look at the second case where the second largest element moves into the left child-heap. Here the number of permutations of the left child-heap is fixed no matter which values we will choose for the other heap:

$\binom{n-2-n_{right}}{n_{left}-1}$

Analog to the previous case we can derive the formula for the permutations of the right child-heap:

$\sum_{i=n_{right}}^{n-2} \binom{i - 1}{n_{right}-1}$

Unfortunately we still miss a special case: If the right heap is empty, one of the above binomial coefficients will always become zero, which is obviously not what we expect. Thus for this case we must only choose the values for the left child-heap:

$\binom{n-2}{n_{left}-1}$

Sticking all parts together we can compute the factor $f$:

$f = \binom{n-2-n_{left}}{n_{right}-1} \cdot \left( \sum_{i=n_{left}}^{n-2} \binom{i - 1}{n_{left}-1} \right) $

$+ \binom{n-2-n_{right}}{n_{left}-1} \cdot \left( \sum_{i=n_{right}}^{n-2} \binom{i - 1}{n_{right}-1} \right)$

$+ \begin{cases}\binom{n-2}{n_{left}-1} & \text{if $n_{right} = 0$} \\ 0 & \text{else}\end{cases}$

Example:

Have a look at the heap image at the top. The heap contains five nodes thus $n = 5$. The left child-heap contains three nodes thus $n_{left} = 3$ and the right one only a single node ($n_{right} = 1$). By using the above formula we calculate $f$:

$f = \binom{0}{0} \cdot \left( \sum_{i=3}^3 \binom {i-1}{2} \right) + \binom{2}{2} \cdot \left( \sum_{i=1}^3 \binom{i-1}{0} \right) + 0 = 1 + 3 = 4$

So there is one possibility if the second largest value is in the right child-heap – this is one of the images. And if the second largest value is in the left child-heap there are three different configurations: The values 3, 2 and 0 can be at the root of the right child-heap. The number of different orderings is calculated by the $heapnum$ recursion.

I have written a small C++ code which uses (more or less) the above forumals to calculate the number of different heaps of size $n$. The source code can be found here. The results for $n \in \left\{ 1, \dots, 27 \right\}$ are:


$ seq 1 27 | ./heapnum
1
1
2
3
8
20
80
210
896
3360
19200
79200
506880
2745600
21964800
108108000
820019200
5227622400
48881664000
319258368000
3143467008000
25540669440000
299677188096000
2261626278912000
25732281217843200
241240136417280000
3258308336025600000

If you do not trust my results – that’s good since I tend to make mistakes :) – you may want to have a look at the On-Line Encyclopedia of Integer Sequences. Search for example for “1,1,2,3,8,20,80,210″. If you take a careful look at the sequence you will notice that it is different (for example for $n = 15$) from mine. Wait! They also provide a maple script. If you execute the maple script it will output exactly the same sequence as mine (except for overflows for large n).

Maybe one last question which should be clarified: Does that hold for arbitrary values in the heap? To answer the question imagine a heap of size n which contains only nodes with value x. Then there exists of course only a single heap ordering. So the equations only hold for heaps with pairwise different values.

Update:

I updated the program code to support arbitrary precision integers using the gmp library. To compile with gmp support:


$ g++ -O3 -DHAVE_GMP -DMAX_K=1024 -o heapnum heapnum.cpp -lgmpxx -lgmp
$ seq 1 1024 | ./heapnum > heapnum.out
]]> http://tpreclik.dyndns.org/codeblog/?feed=rss2&p=4 0 My very own blog… http://tpreclik.dyndns.org/codeblog/?p=3 http://tpreclik.dyndns.org/codeblog/?p=3#comments Fri, 12 Jan 2007 17:24:03 +0000 Tobias Preclik http://tobias.preclik.de/blog/?p=3 Well, now I got a shiny new blog. cute isn’t it? Stay tuned…

]]> http://tpreclik.dyndns.org/codeblog/?feed=rss2&p=3 0 Defrosting revealed http://tpreclik.dyndns.org/codeblog/?p=44 http://tpreclik.dyndns.org/codeblog/?p=44#comments Thu, 08 Jul 2004 21:08:05 +0000 Tobias Preclik http://tobias.preclik.de/blog/?p=44 This quick article is meant to reveal the “tricks” behind defrosting your refrigerator in a quick and efficient manner. There’s no need to occupy your neighbors fridge. Just get your hair-dryer or ask your neighboring bonny if you haven’t got one at hand. Now let’s get our hands on.

Dump the content of your fridge somewhere (assumed that your fridge isn’t as empty as mine) and attach the hair-dryer next to the ice box. In order that you can figure it out properly study the instruction photos.

Now plug in the dryer and take a nap until the ice box is completely defrosted.

Until the fridge’s cold again cool your beer in the bucket with the icy water. That’s all to it…

Cheers!

Icy Beer Hair Dryer Attached
Defrosting Overview Defrosting Overview
]]> http://tpreclik.dyndns.org/codeblog/?feed=rss2&p=44 0