You are viewing simonkagstrom

Simon Kågström's blog [entries|friends|calendar]
simonkagstrom

[ website | My Website ]
[ userinfo | livejournal userinfo ]
[ calendar | livejournal calendar ]

Blog gone, google+ instead [30 Dec 2011|08:55am]
There hasn't been many posts here the last year or so. The main reason is that I'm spending more time on social networks now, and time is limited!

Anyway, I think Google+ combines blogging and social networking in a good way, so I'm basically closing this blog now. My Google+ page is being updated though, and contains much of the stuff that I used to write about here.

Promenadstad - Pedalstad [08 Jul 2011|11:11am]
Jag har precis kommit tillbaka från en tågresa till Frankrike som gick via Tyskland och Nederländerna. Syftet med resan var cykelsemester i Loire, men det jag tänkte tala om här är Amsterdam... och Stockholm. Jag fick nämligen upp ögonen för vissa saker i Amsterdam, en slags vision kan man kalla det, och det alldeles utan att provröka deras specialcigaretter.

Såhär tror jag nämligen det är: Stockholms stadshusmajoritets vision om promenadstaden behöver i själva verket bli pedalstaden. Amsterdam är nämligen en alldeles utmärkt promenadstad, och det tror jag beror på att man satsar stenhårt på cykeltrafiken. Vi hyrde cyklar och provade på cykeltrafiken i Amsterdam, och här är några observationer på allt positivt de lyckats med:


  • Bil- och cykeltrafiken är inte separerad.

    Amsterdam satsar på cykeltrafik, men utan att för den delen förbjuda biltrafik. Bilar och cyklar delar på gatuutrymmet, men i cyklarnas tempo. I början väjde vi undan när en bil närmade sig bakifrån, som man gärna gör i Stockholm, men i Amsterdam försökte aldrig bilarna köra om, så ganska snart var man van och cyklade på som vanligt.

    I Stockholm anlägger man istället gärna supersmala cykelremsor, och cykelbanelagen förbjuder cyklister att använda gatan. Snacka om snedprioritering.

  • Trafiken är anpassad till cyklarnas tempo.

    Jag tänkte inte på hastighetsbegränsningar längs gatorna (överhuvudtaget var det få skyltar), men trafiken går i praktiken i cykeltempo. Förutom de uppenbara fördelarna för cyklister så gynnar det även fotgängare och gatuliv: bilar bullrar avsevärt värre i 50 km/h än 20-30. Att sitta på uteservering längs gatorna i Amsterdam är ett tyst och skönt nöje, något man knappast kan säga om Stockholm.

    Hur kul är det med promenadstad längs bullergator?

  • Cyklar får köra mot enkelriktat.

    Cyklister i Amsterdam får köra mot enkelriktat som regel (undantag finns troligtvis). I det lugna trafiktempot är detta ingen säkerhetsrisk och det ökar förstås avsevärt framkomligheten.

  • Inga kantstenar.

    I Stockholm är gång- och cykelbanan (där det finns en separat) ofta separerade med hårda kantstenar. Kör man på en sådan faller man hårt. I Amsterdam däremot har man på de flesta ställen rundade stolpar som man kan åka mellan om man behöver stanna. Superenkelt och supersmart.

  • Cykelbanor är rödmarkerade.

    Även i Stockholm markerar man cykelbanor med avvikande färg. Efter någon säsong är färgen borta och omöjlig att se. I Amsterdam använder man istället rödfärgade plattor eller röd asfalt som markerar cykelbanor (och gememsamma bil- och cykelgator). Mycket smartare.



Amsterdam Bicycle Lane

Så sammantaget fick jag mycket positiva upplevelser i Amsterdam, och jag önskar att Stockholm kunde närma sig Amsterdam. Helt enkelt tycker jag översiktsplanen skulle fokusera på att bygga pedalstaden, så får man en promenadstad på köpet. Så frågan är hur man fixar till detta? Jag är ju knappast någon expert på området, men några saker tror jag är:
  • Förtätning.

    Just detta finns ju faktiskt med i översiktsplanen, så här går det åt rätt håll. Det är egentligen ganska enkelt: Tät stad lämpar sig för cykling, kollektivtrafik och promenad, gles stad blir bilberoende. Gatuliv får man på köpet med en tät stad.

  • Sänk hastigheten för trafiken.

    I innerstaden och närförort tycker jag 30km/h skulle vara den normala hastighetsgränsen. I denna hastighet kan cyklister och bilister samsas om samma gator mycket enklare, och i praktiken förlorar knappast bilisterna någon tid på det heller. Precis som i Amsterdam blir ju också gatulivet mycket trevligare om man slipper bilbullret.

  • Infartsparkeringar.

    Med tunnelbanan har Stockholm bättre kollektivtrafik än Amsterdam (eller borde kunna ha). Lite infartsparkeringar vid strategiska punkter tillsammans med högre trängselskatt skulle säkert få bort en del av biltrafiken och öka framkomligheten för cyklister.

  • Cykling mot enkelriktat.

    Med 30-gräns på enkelriktade gator borde det vara enkelt att tillåta cykeltrafik mot körriktningen. Det finns ju redan nu här och där, men längs separerade cykelbanor.

  • "Bicycle superhighways".

    "Cykelmotorvägar" som den mellan Malmö-Lund Karin Svensson-Smith föreslagit skulle avsevärt underlätta långpendling via cykel. Vi cyklade till Vaxholm för någon månad sedan, och jag kan intyga att det inte är någon höjdare att cykla på en smal vägren längs 90-väg.

    Så rejält snabba cykelhighways till förorterna hade verkligen gjort tillvaron drägligare.


Cykel heter för övrigt Fiets på holländska!

[20 Jun 2011|06:05pm]
I've finally put together a new Cibyl release! To recap, Cibyl is a programming environment and binary translator which translates MIPS binaries into Java bytecode. In effect, in enables C/C++ programs to be ported to pure-Java environments such as J2ME and blackberry phones.



The release contains many new features in version 21, of which these are the most important:
  • There are now binary releases of the SDK, complete with toolchain, both for Linux and for Windows (cygwin). This should make it much easier to use than before.

  • The cibyl environment is globally installable now, so you can copy it to e.g., /usr/local/ if you wish

  • Major optimization improvements: DWARF debugging information is used to reduce function call overhead

  • Minor optimization improvements: better peephole optimization, instruction improvements, better memset/memcpy implementations (all by Marcus Groeber)

  • The build-system has been completely rewritten, and is now cmake-based and much better than before

  • Various bug fixes and code cleanup



Get the release from cibyl.org, and the source code at github!

Lots of thanks to Marcus Groeber, who contributed the Windows build and a lot of optimization improvemenets and bug fixes, as well as Maik Merten and Ehud Shabtai for various bugfixes and improvements.

MPD + Despotify + MCI500h = music [27 Mar 2011|09:13am]
I'm finally getting somewhere with the rooted MCi500h. After initially having based the development environment on buildroot, I never managed to get networking running. Instead, I switched to a Debian Etch-based distribution, which runs fine with the old 2.4.27 kernel.

I also got the source code for the kernel from Philips, which helps a bit with how to use the system. Looking at their patches (which I've uploaded to github), you can see that they violate the kernel conventions in many places with a lot of magic IOCTLs, special hacks and ugly workarounds. Well, well. I don't intend to replace the kernel anyway.


Anyway, my long-term plan is the following:
  • A Debian-based distribution which you can install stuff as you want in

  • The Music Player Daemon to playback music. MPD provides lots of nice features and supports basically all major music formats. It also has very good client support.

  • A web server with a web-based MPD client

  • Spotify-support via Despotify through MPD

  • A MPD-client running on the built-in display and controlled via the remote

  • FM radio support etc

And so far, I've written a set of patches for Despotify to enable libtremor support for integer decoding (the MCI500h ARM is FPU-less). For MPD, I've added Despotify input/playlist plugins and fixes a few bugs which I stumbed upon. The "distribution" and a set of tools is also found in a repository at github. So I've built a binary release for testing which can be downloaded from googlecode.

Left to do is basically the interface stuff plus adapting to the Philips-specific hacks. For example, volume control is done via (I think) i2c (naturally, not using the kernel driver interface but an IOCTL-based one). This will be quite a bit of work, but at least there is something to base the rest on now.

New Kcov and Dissy releases [13 Feb 2011|08:59am]
I'm the main developer of a number of small projects: Cibyl, Kcov, Dissy as well as a few others. I do releases sometimes, but often features are hidden in the development trunk for a long time. Releases are simply boring to do and doesn't actually bring anything for me personally :-)

However, this weekend, I've finally put out new releases of two of my projects: Kcov and Dissy. Kcov, first, is a code coverage tool which uses DWARF debugging information to instrument the executable with breakpoints (it's based on bcov):



The new release, version 5, improves usability a bit by allowing filtering by both paths and patterns (previously only patterns), and has a lot of internal changes which doesn't show outside of the source code. Download from github.

The second project, Dissy, is a graphical frontend to the objdump disassembler. I use it myself pretty much daily, so I think it's the most useful of the things I've written.



Dissy version 10 has many improvements: The workspace can be saved and reloaded later, instructions can be commented, the window size is remembered on restart and more branch instructions are recognized. A number of bugs have also been fixed. Download from googlecode.


Thanks to the contributors to both projects!

More work on the MCi500h [05 Feb 2011|12:47pm]
In the last post, I wrote about rooting the Philips MCI500h stereo. The question was what to do with it. Well, what I started looking at is a combination of one or more of despotify, MPD, the music player daemon and Rockbox. You might wonder how all that went.


I've made some progress, but got stuck on a slightly tricky and irritating issue. I setup a buildroot-based enviroment for building my own rootfs, and started looking at despotify. After some initial troubles, I've managed to build a version that actually starts on the MCI500h. However: There is no network access, either from despotify or from the busybox command line tools. I believe this is an issue with the aging kernel (2.4.27) and the newer uClibc I used when building the rootfs. The problems look like this:
g2 trunk 6869 Island:# nslookup www.dn.se
Server:    192.168.1.1
Address 1: 192.168.1.1

nslookup: can't resolve 'www.dn.se'
g2 trunk 6869 Island:# ping 192.168.1.104
PING 192.168.1.104 (192.168.1.104): 56 data bytes
ping: can't create raw socket: Function not implemented
g2 trunk 6869 Island:# telnet 192.168.1.104
telnet: socket: Function not implemented

and obviously neither despotify nor MPD are very interesting without network support.

I did verify that OGG Vorbis plays on the device though. libvorbis uses floating point and is much too slow for the processor to decode, but using the tremor integer-only decoder, it plays fine from mplayer. This leads me to believe that despotify should be possible once the networking issue is solved. I've also built despotify against tremor and verified that on the host.


So how does one continue? Well, I'd urge other interested developers to take a look at this - I've setup a few git repositories on github. What I plan to test is to build with other C libraries. Eglibc is an obvious possibility, at least if it's possible to swap in the existing (old) glibc libraries instead of it. Newlib might be an alternative as well, although I'm not sure if it's possible to build all tools using that. I've also tried to build uClibc and the other tools using the old 2.4.27 kernel. I've made some progress there, uClibc builds but busybox fails because of the old kernel. This path unfortunately requires some ugly hacks for buildroot, so it might not be feasible in the end.

Finally, I've requested the GPLed source code from Philips. I've still heard nothing from them, but I hope they'll realise that they are legally obliged to send me the sources.

Rooting the Philips MCI500h micro stereo [16 Jan 2011|11:31am]
This entry describes how to get a root shell on your Philips MCI500h micro stereo, with a few easy steps. Basically, what we need to do is to enable SSH and then SSH into it. There are three, very simple steps to do this:
  • Set the dbg_startsshd NVRAM parameter to true

  • Reboot the MCI500h

  • Login via SSH



The Philips NVRAM daemon listens to port 6481, which conveniently is a web interface. Just pointing your browser to that port will give you a list of the current NVRAM contents. What we want to do is to set dbg_startsshd to true, which we can do via the web interface like this:

In your web browser, go to http://[your-mci500h-ip]:6481/dbg_startsshd?true , and you should see a screen with OK. If you reload http://[your-mci500h-ip]:6481 in your browser, you will see the new setting.

Then reboot your stereo. It's not enough to press the power button, but unplugging it should do the trick, or telnetting to port 10023 and running the # command. After the stereo has booted up, ssh will be enabled and you should be able to ssh to it like below:
  ska@x41:~$ ssh root@192.168.1.129
  root@192.168.1.129's password: 
  Welcome to NXP Semiconductors PNX8706 Linux !!


  BusyBox v1.2.1 (2010.01.21-08:20+0000) Built-in shell (ash)
  Enter 'help' for a list of built-in commands.

  g2 trunk 6869 Island:# ls
  blob1.bin       wl.o            wl_recovery.ko
  g2 trunk 6869 Island:# uname -a
  Linux pnx0106 2.4.27-vrs1-6869 #1 Thu Jan 21 16:16:41 CST 2010 armv5EJl unknown
The root password is root, which I managed to guess the first time :-)


A few words about how I found this out as well. Well, I first downloaded the firmware image. This is a CRAMFS filesystem image, which can be uncompressed as described here.

Looking around in that image, I started looking in /etc/ and /usr/local, where the Philips-specific stuff is located. Seeing that /etc/init.d/rcS contained this line:
  [ "$(/usr/local/bin/nvram get dbg_startsshd)" = "true" -a -x /usr/bin/dropbear ] && \
  { echo "Starting dropbear SSH server...";
it was fairly easy to run strings on /usr/local/bin/nvramd and find these interesting strings:
  GET / SIMPLE
  GET /%s SIMPLE
  usage: nvram [get name] [set name=value] [unset name] [show]
  GET /%s?%s SIMPLE
  unset
  GET /%s? SIMPLE
  show
And after some poking, I found out how to set the NVRAM values. The password was easy to guess, thanks for that Philips :-)


So now that we've got root, what are we going to do with it?

Update: Instead of telnetting to 6481, just pass the new NVRAM variable via the web browser.

Cibyl and usability - now improved! [16 Jan 2011|09:30am]
In the emails I get about Cibyl, a common theme is problems with getting the environment setup. Especially getting a MIPS cross compiler to your system is more difficult than it might seem a first. Cibyl itself is also not really for the faint-hearted, especially for people that use Windows and other systems (which I never test on).

So making Cibyl a bit simpler to use is something I should have done a long time ago, but finally got round to doing now. What I wanted to get rid of was this eye-sore when running make in the hello-world example:
  mips-linux-gcc -G0 -DCIBYL=1 -ggdb -msoft-float -fno-optimize-sibling-calls -nostdinc -Wall -Wa,--no-warn\
   -mips1 -mno-check-zero-division -Os -fno-pic -mno-abicalls -I/home/ska/projects/cibyl/old/cibyl/include \
   -I/home/ska/projects/cibyl/old/cibyl/include/generated -I.   -c main.c -o main.o
  main.c: In function 'main':
  main.c:26: warning: unused variable 'v2'
  mips-linux-ld -L/home/ska/projects/cibyl/old/cibyl/libs/lib/ -EB -nostdlib --whole-archive --emit-relocs main.o\
   /home/ska/projects/cibyl/old/cibyl/libs/crt0.o -T/home/ska/projects/cibyl/old/cibyl/build/linker.lds\
   --start-group -lcrt0  -lc -ljava --end-group -o program
  make[1]: Leaving directory `/home/ska/projects/cibyl/old/cibyl/examples/host-java/hello-world/c'
  install -d res
  install -d tmpclasses
  install -d classes
  touch .dirs
  /home/ska/projects/cibyl/old/cibyl/tools/cibyl-mips2java -DNOJ2ME -d tmpclasses\
   -I/home/ska/projects/cibyl/old/cibyl/include/generated c/program
  cp tmpclasses/program.data.bin res/program.data.bin
  cp /home/ska/projects/cibyl/old/cibyl/java/StandaloneMain.java tmpclasses/StandaloneMain.java
  cp /home/ska/projects/cibyl/old/cibyl/java/CRunTime.java tmpclasses/CRunTime.java
  cp /home/ska/projects/cibyl/old/cibyl/java/CibylConfig.java tmpclasses/CibylConfig.java
  cd tmpclasses && /usr/lib/jvm/java-6-sun//bin//javac -classpath :  *.java
  Note: CRunTime.java uses unchecked or unsafe operations.
  Note: Recompile with -Xlint:unchecked for details.
  touch tmpclasses/.rebuilt
  cp tmpclasses/*.class classes/
  touch classes/.rebuilt
A fairly good amount of ugly steps, right? Well, with the current GIT head, it looks like this instead:
  mips-cibyl-elf-gcc -Os -o program main.c
  cibyl-mips2java -d tmpclasses -DNOJ2ME program
  Generated: tmpclasses/Cibyl.class
  Generated: tmpclasses/Cibyl1.class
  cp `cibyl-config --sysroot`/usr/share/java/StandaloneMain.java tmpclasses
  cd tmpclasses && javac -source 1.4 *.java
  cd tmpclasses && jar cfm ../program.jar ../manifest.txt *.class program.data.bin
which is much better in my opinion. Here you actually have a chance of spotting warnings and errors in the output, and there are fewer steps. Also, the confusing extra options to GCC (which are there to generate more Cibyl-friendly code) are gone and the Java runtime system is installed automatically. The list of improvements is basically:
  • A crosstool-ng-built 4.4.5 toolchain. Newer than the old ELDK 4.0 toolchain, should be a bit better optimized.

  • The cibyl tools (cibyl-mips2java among others) are now installed alongside the toolchain.

  • The cibyl libs etc are installed in the toolchain sys-root, so as long as the cibyl tools can be found in the PATH, the location of the cibyl libraries and header files are also known.

  • I've switched the build system to cmake. Improves depedency handling a lot, but was a bit painful to get used to.

  • Similar to how e.g., SDL works, I've added a cibyl-config tool which can be used to get default directory paths etc

  • A few bugs in the DWARF-based function optimization have been fixed

I looked at setting up the toolchain with default compiler arguments and the Cibyl linker script built-in, but I couldn't get g++ to work then. So it now builds a defualt MIPS compiler and then with symlinks and small scripts, the arguments are tacked on.

It's probably time to release a new Cibyl version soon, and I intend to make binary releases in addition to the source tarball. Hopefully, even a windows binary release should be possible although someone else will have to build that.

Cibyl: improving register passing using DWARF information [01 Jan 2011|10:15am]
In the last post I wrote about how to retrieve information on function arguments and return values using DWARF debugging information. You might now wonder what that was all about, but no worries: I'll explain everything in this post. Some of you might already have guessed that it's related to Cibyl, my binary translator. The main issue at hand is this:
  • Translated C function calls are expensive to make in Java
and the rest of the post will explain the problem and a way of improving that situation. First, since Cibyl translates MIPS binaries into java bytecode, we'll need some background on MIPS and Java bytecode, focusing on the function calling conventions.

MIPS has 32 registers which, like for most microprocessors, are fixed (I.e., it doesn't use SPARC-style register windows). In the MIPS ABI, four registers are used for passing arguments to functions. These arguments, and any additional arguments, are backed by the stack, as illustrated in the figure below.



So to call a function with five 32-bit arguments, the caller would put the first four in registers a0..a3 (the blue boxes in the figure) and the fifth on the stack (the pink box). If there are fewer arguments, they are all placed in registers. Function return values are also passed via registers, using the v0/v1 register pair. For 32-bit return values, only v0 is used, and if more than 64-bits are needed, the rest will be copied via the stack.

The ABI also specifies a set of callee-saved registers (s0..s7) and a stack pointer (sp). The other registers are basically used for temporaries and are allowed to be overwritten by the callee. (I'm ignoring some special cases here, which can be handled with compiler options).


How does this translate into Java bytecode then? I've explained how Cibyl works in more details in other articles, but a recap can be good. The important part here is how MIPS registers are handled. A naïve implementation would use static integer class members in Java to represent registers, which would correspond nicely with how actual MIPS registers are implemented. All C functions can then be translated into Java prototypes void fn_name(void), since all register values are always available statically. In fact, this is how the very first Cibyl release was implemented. I say it's naïve because it's quite inefficient as well. It tends to generate code such as
	iconst_1
        putstatic CRunTime/t0 I
	iconst_2
        putstatic CRunTime/t1 I
	...
	getstatic CRunTime/t0 I
	getstatic CRunTime/t1 I
	iadd
	putstatic CRunTime/t2 I

and getstatics and putstatics are both slow and big (bytecode-wise).

So instead, Cibyl uses Java local variables to represent MIPS registers. This allows for much more efficient and compact bytecode to be generated, but instead gives us a problem with functions: You now need to pass all registers which pass values between caller and callee to the callee function. Luckily, this actually boils down to only the argument registers, and the stack pointer. All the other registers are either local temporaries, which we can just throw away, or callee-saved registers, which are saved automatically since function-locals are used.


Let's look at how a function call in Java bytecode works. Java bytecode is a stack-oriented architecture, i.e., all operations are done on values on an operand stack. For example, an integer addition is done by pushing two values on the operand stack, and executing an iadd instruction which will pop them and push back the result. The figure below shows how a function is called:



i.e., the caller will push some values on the operand stack and then invoke the method. Since Java is typesafe, the correct number of arguments must be on the operand stack, or the JVM will not load the program. On the call, the callee will receive the arguments not on the operand stack, but placed in local variables (the first n), which is where they would typically end up anyway. To return a value, it's again pushed on the operand stack and returned via the ireturn instruction (for integer return values). When control returns to the caller, it can find the value at the top of the stack. In the figure, the blue boxes represent the arguments and the code shows an example function call.

Fine. So most of you can now guess how Cibyl handles MIPS argument registers: a0...a3 is simply pushed on the operand stack and ends up as local variables in the function. In addition, the stack pointer sp is also pushed, as it's value is needed by both caller and callee. Other registers are simply allocated and used locally.


But how does Cibyl know which of the argument registers to pass? Now we're getting to the point! Trivially it could pass all argument registers to all functions, but that's unnecessary since not all functions have that many parameters. More function arguments also mean higher overhead, and we'd like to avoid that. So far, Cibyl has simply checked if the argument registers and the stack pointer are used by the function, and then pass the needed ones. Unfortunately, a0..a3 can sometimes be used as local temporaries as well - even though they are not function parameters. In this case, Cibyl would pass them in vain, inducing extra overhead for no gain. Luckily, through DWARF there is a better way.

The idea comes from Marcus Groeber, who noticed this while playing with Cibyl. The DWARF debugging information actually contains all information we need to find out which arguments registers are actually used as parameters. The last post describes how to look this up. So what's left to do in Cibyl is simply to note this down, and only pass the actual parameters. The same goes for the return values.

In effect, the prototypes in the generated Java methods now become basically the same as the original C functions. Some cases are still tricky, namely parameters and return values that are larger than 32 bits. For these, I simply revert back to the old behavior. These are fortunately pretty uncommon, in C and C++, mostly either small values or pointers are passed around.


I've not yet done any real performance measurements with the new approach, and indeed, I've managed to introduce a regression which I haven't yet tracked down. But around 3% of the instructions in a large program (Frodo, the C64 emulator) are pruned with this approach. I would guess that the reduced overhead should be measurable for most applications, although probably not dramatic.

So in conclusion: DWARF debugging information makes for an interesting way of optimizing function calls for Cibyl. It also brings the Java bytecode translation a bit close to the original C program, which should be nice for those that like to read Java bytecode assembly!


Update: The regression has been found and fixed. I've also moved the entire Cibyl source to github. Git is simply better than svn...

DWARF: function return value types and parameter types [30 Dec 2010|10:23am]
I've recently had to look deeper into the DWARF debugging standard. DWARF is the debugging format used in the ELF executable format, commonly used by debuggers, but also in tools like my Kcov code coverage tool. It's complex and quite a bit daunting to get the grips on. Anyway, I have a small project where I needed help from DWARF. What I wanted from DWARF is the following:
  • Looking up the type of function return values

  • Looking up the type and number of arguments to functions
And in this post, I'll explain how to do just this in code and illustrations. First some prerequisites though. You don't need to parse the ELF file manually (fortunately), but can rely on libraries to do this. Unfortunately, there are two DWARF libraries - which are not compatible with one antoher.

The two libraries are libdwarf and libdw/elfutils. libdwarf is the original one, while elfutils is a newer library which promises a slightly simplified and more modern API. They both install /usr/include/dwarf.h though, so you can only have one of the development libraries installed. elfutils is easier to find examples for, so I wanted to use that. Unfortunately, Kcov is written for libdwarf (by Thomas Neumann), so I first rewrote that to use libdw instead.


So on to some DWARF concepts and an overview of my problem. A deeper introduction can be found in the Introduction to the DWARF debugging format by Michael J. Eager, written for the standard committee. Here, I'll limit myself to the steps needed to solve my particular issue. The figure below illustrates the data structures used for function return values and parameters.



The basic structure in DWARF is the DIE, the Debugging Information Entry. Each of the big, rounded blobs in the figure are DIEs. These are structued in a tree of sorts, where a DIE can have children and siblings. Each DIE is identified by a tag, which describes what type of DIE we're dealing with. The colors of the rounded blobs signify the tags, or DIE types. A DIE can also have attributes, which describe, well, attributes of the DIE. For example, DIEs often have names (a function name), types (a reference to int, double, etc) and sizes (the size of a type).

Now, if we want to get the function return type and parameter types, it should be clear that we need to traverse the DIE tree to lookup functions and their children. From there, we can get the types through the DIE attributes. I'll describe in code how to do this with libdw from elfutils. The full code is listed here, and the code below is simplified, skipping error checks and some application-specific setuff. So let's begin.
  /* Initialize libdwarf */
  dbg = dwarf_begin_elf(this->elf, DWARF_C_READ, NULL);

... with initializing libdwarf from an ELF-structure. This returns a pointer to a DWARF context. We continue by iterating through the compilation units, which is done in two steps:
  while (dwarf_nextcu(dbg, offset, &offset, &hdr_size, 0, 0, 0) == 0) {
      Dwarf_Die result, cu_die;

      if (dwarf_offdie(dbg, last_offset + hdr_size, &cu_die) == NULL)
        break;
      last_offset = offset;

the first of which looks up the offset into the ELF of the compilation unit, and the second returns the DIE for this. As you can see in the figure, we're actually intersted in the child of the compilation unit - where the functions are.
      if (dwarf_child (&cu_die, &result) != 0)
        continue;

So dwarf_child just places the child DIE in the result variable. We then want to iterate through the childs siblings and do something for each function:
      do {
          switch (dwarf_tag(&result))
          {
          case DW_TAG_subprogram:
          case DW_TAG_entry_point:
          case DW_TAG_inlined_subroutine:
            this->handleDwarfFunction(&result);
            break;
          default:
            break;
          }
      } while(dwarf_siblingof(&result, &result) == 0);

And here we check the tag of the DIE and call a helper routine for each function. So onto handleDwarfFunction():

void CibylElf::handleDwarfFunction(Dwarf_Die *fun_die)
{
  attr = dwarf_attr_integrate(fun_die, DW_AT_type, &attr_mem);
  ret_size = mips_arg_size(elf, fun_die, attr);

We first lookup the DW_AT_type attribute of the function, which is the return type of the function. mips_arg_size() is a helper function which return the size of this attribute (if it can be derived). It's taken from elfutils and will iterate through typedefs etc to get to the actual type. We'll skip that here though. In the figure, the return value attribute is represented by the square box in the lower left. For the parameters, we'll need to recurse down to the children of the function:

  if (dwarf_child (fun_die, &result) != 0)
    return;

  do {
      switch (dwarf_tag (&result))
      {
      case DW_TAG_formal_parameter:
        attr = dwarf_attr_integrate(&result, DW_AT_type, &attr_mem);
        arg_size = mips_arg_size(elf, fun_die, attr);
        break;
      case DW_TAG_inlined_subroutine:
        /* Recurse further down */
        this->handleDwarfFunction(&result);
        break;
      default:
        break;
      }
  } while(dwarf_siblingof(&result, &result) == 0);
}

so, similar to what we had before, we lookup the child and then each sibling of the child. From the tag of it we can see if it is actually a parameter, and then convert the type attribute to the size by the mips_arg_size() helper.


So that's it. Not so difficult, right? Well, not when you know how to do it - but I can assure you that this took quite a bit of time to find out.

And what's the use of it then? That's for the next post!

Biblioteksböcker på Kindle 3 [11 Dec 2010|10:54am]
Som jag skrev om i ett tidigare inlägg har jag köpt en Amazon Kindle 3. Efter två månaders användning har jag läst kring 10 böcker på plattan, och kan säga att jag är nöjd än så länge. Jag har inte upptäckt några nya besvär förutom de jag skrev om i testet. Nåja, förutom ett då: ibland kan det vara trevligt att läsa böcker på svenska. Och böcker på svenska finns helt enkelt inte i Amazons butik.

Tough luck, tänkte jag i början, det får helt enkelt bli att läsa vanliga träböcker i det fallet. Men sen började jag googla litegrand på problemet. Det finns trots allt webbutiker som säljer e-böcker även i Sverige, och biblioteken lånar ju också ut e-böcker. Och visst går det att läsa svenska e-böcker på Kindlen i alla fall!


Men vad är problemet till att börja med? Jo, det stavas DRM - Digital Rights Management. Till skillnad från vanliga böcker är e-böcker krypterade och går bara att läsa på en specifik läsplatta. De kan också vara tidsbegränsade, som i fallet med låneböcker, och finns också tillgängliga i en drös olika format. Köper man bara böcker via Amazons butik märker man inget av detta, men annars kan det vara en ganska svettig upplevelse att köpa en e-bok. Här får man säga att träböckerna har fördelar: De är sällan krypterade och finns bara i två format: pocket och inbundna, varav bägge är kompatibla med läsaren (åtminstone om läsaren har tillräckligt starka glasögon).

Historien visar dock att i princip alla DRM-format knäcks förr eller senare. Bok-DRM:arna är inga undantag, utan både MobiPocket och EPub går utmärkt att komma runt. I resten av inlägget kommer jag att fokusera på MobiPocket, som var lite enklare att få kläm på i Linux. Med hjälp av stegen nedan kunde jag ladda ner svenska e-böcker från bibilioteket till min Kindle. Hurra för det!


Med MobiPocket handlar det inte om att bryta DRM:et som sådant, utan att ladda ner en e-bok med Kindlens ID (PID, Personligt ID), och sedan konvertera boken till Amazons nästan-Mobi-format AZW.

Så vad behöver man för att låna en E-bok till Kindlen? Jo, i korthet
  • Ett bibliotekskort (det har du väl redan, hoppas jag) och tillhörande PIN-kod

  • Kindlens serienummer som används för att generera PID:en

  • Ladda ner Mobi2Kindle, som är baserat på Igor Skochinskys skript

  • Generera sin Kindle-PID

  • Ladda ner E-boken från biblioteket med Kindle-PID:en

  • Konvertera E-boken till Kindlens format

  • Kopiera över den till Kindlen via USB

En lite längre, och illustrerad, beskrivning följer nedan.

Vi måste börja med att ta reda på kindlens serienummer. Det är dock en smal sak, slå igång din Kindle, gå till hemskärmen och öppna menyn. Välj sedan Settings, så har du serienumret på första sidan:

PICT2822

från detta behöver man generara Kindlens PID-nummer. Här behövs Mobi2Kindle, så checka ut dess subversion-repository. Du behöver även applicera den här patchen för att det skall fungera för Kindle 3. Mobi2Kindle är ett Mac-program, men är i själva verket bara ett GUI till kommandoradsverktyg som Igor skrivit, så vi gör helt enkelt
  mv mobi2kindle-read-only/Mobi2Kindle.app/Contents/Resources/azw/* .
för att få skripten dit vi vill. Därefter behöver vi omvandla Kindlens serienummer till ett PID. Det gör vi genom att köra
  python kindlepid.py B008XXXXXXXXX
  Mobipocket PID calculator for Amazon Kindle. Copyright (c) 2007, 2009 Igor Skochinsky
  Kindle 3 serial number detected
  Mobipocked PID for Kindle serial# B008XXXXXXXXX is ABCDEFG*AB
Sedan är det dags att gå till bibliotekens E-boksida, t ex Stockholms stadsbibliotek. Därefter gäller det att hitta en bra bok att låna, som också finns tillgänglig i Mobipocketformat, t ex Underbara dagar framför oss. Klicka på länken Låna boken:

underbara-dagar-framfor-oss

På nästa skärm fyller du i fälten för MobiPocket-nedladdning - ditt bibliotekskortsnummer, din pin-kod och din plattas PID-nummer. Sedan är det bara att klicka på hämta hem bok.

hamta-bok

När vi har boken nerladdad (som .prc eller .mobi), behöver vi konvertera den och överföra den till Kindlen. Konverteringen görs med den nerladdade filen och ditt PID-nummer:
  python kindlefix.py isbn.mobi "ABCDEFG*AB"
  The Kindleizer v0.2. Copyright (c) 2007, 2009 Igor Skochinsky
  Encryption: 2
  Mobi publication type: 2
  Mobi format version: 4
  Found the matching record; setting the CustomDRM flag for Kindle
  Output written to isbn.azw
och vips har vi en isbn.azw som vi kan ladda ner till Kindlen. Nerladdningen görs via USB eftersom Amazons konverteringstjänst via email inte sväljer AZW:er. Kopiera den konverterade boken till documents/-katalogen, avmontera så finns boken på din hemskärm efter det.

PICT2823

PICT2824

Det andra stora formatet, Epub, är lite krångligare att jobba med från Linux. Det är dock möjligt att gå runt, och bloggen I love cabbages har skript och instruktioner för hur det görs. I det fallet behövs dock en installation av Adobe Digital Editions, och det är något jag inte orkat kolla på än. Noterbart för Epub är att själva kryptot inte knäckts, men däremot är själva nyckeln ganska enkel att plocka ut. Lite som att installera världens bästa lås i dörren och sedan lämna nyckeln på dörrmattan.

Men Epub är något jag får undersöka mer senare. Hade Amazon bara bemödat sig att lägga ut svensk literatur hade jag nog inte brytt mig om extrajobbet och köpt via Amazons webbutik. Kanske något att fundera på?

Ett test av Amazon Kindle 3 [24 Oct 2010|10:37am]
Note for english speakers: This is a review of the Amazon Kindle 3 in swedish. There are plenty of reviews in english, so I saw no point in adding yet another one.

Eböcker är något jag följt med intresse under de senaste åren. Framförallt är det två typer av tillfällen som gör att jag suktat efter ebokens evangelium: Varje gång jag flyttat och varje gång jag varit ute på resa. Jag tycker om att läsa böcker, men läser egentligen aldrig en bok mer än en gång (två undantag: Svampar i skog och mark av Bo Nylén och Kaffeboken av Lars Elgklou). Bokhyllorna är därför fyllda av engångspocketar och, ännu värre, engångsinbundningar.

När det är dags för flytt blir det alltså till att packa ner tonvis med gammal gran och tall och konka över det till nya lägenheten. Det är vid dessa tillfällen jag önskar att jag hade ett eboksbibliotek istället, och speciellt efter den senaste flytten till en lägenhet på fjärde våningen utan hiss har behovet blivit akut.

Vad gäller resor är det väl ett mindre problem, men det är såklart jobbigt att behöva packa ner tunga böcker för att ha tillräckligt att läsa under tiden. Ja, sen luktar det ju så illa kring massafabrikerna också!


Hur som helst har jag hittils inte varit riktigt nöjd med utbudet av eboksläsare på marknaden, så jag har avvaktat trots många flyttar och ett par resor. Fram tills nu alltså. Nu har jag nämligen köpt mig en Amazon Kindle 3 (Wifi-varianten för US $139), och nedan följer några erfarenheter av hur första tiden med Kindlen har varit. Hittils har jag har läst ut en bok på den, Eating Animals av Jonathan Safran Foer.

Först kan jag nämna anledningarna till att det blev just en Kindle. Till att börja med behövs ju en riktig skärm. Kindle har, precis som de flesta eboksläsare, en skärm från e-ink som alltså inte är bakgrundbelyst. Ipad och liknande tingestar med vanliga LCD:er är inget som intresserar mig, i alla fall inte för att läsa böcker på.

PICT2803

En annan anledning är att det är lätt att köpa böcker på en Kindle. Det går att göra direkt från plattan, utan att koppla in den till datorn. Å andra sidan går det utmärkt att köpa böcker via datorn som sedan levereras automatiskt till plattan. Klart plus mot de lite enklare modellerna.

Sen är det två saker till: Liten och lätt och ganska billig. Väger ungenfär som en pocketbok, och jag betalade lite drygt 1700 kronor för plattan och ett fodral. Måste beställas från USA, men det är ju inget problem längre.


Så hur är den då? Vad är fördelarna och nackdelarna mot gammalt trä?


Vanliga böcker kan man ju inte anklaga för att ha skärm, men å andra sidan har de i allmänhet behaglig kontrast och alldeles utmärkt skärpa. Vad gäller kontrasten tycker jag E-inkskärmen står sig bra mot en riktig bok. Det går att jämföra med att läsa en gammal gulnad 60- eller 70-talsbok (låt säga t ex Den vedervärdige mannen från Säffle). Skärpan är OK, men inte fantastisk. Tittar man lite närmare ser man pixlarna ganska tydligt. Och om man "togglar" menyn får man dessutom en svag skugga av menykonturerna på boksidan (som försvinner när man vänder blad).

Kindlen har ett litet fysiskt tangentbord som används för att lägga till anteckningar, markera ord och söka efter böcker i Amazons butik. För sidvändning finns rejäla specialknappar för både höger- och vänsterhänta, enkelt och bekvämt. Själva tangentbordet är däremot klart svåranvänt, men å andra sidan skriver man inte så ofta på det. Men en klar miss är piltangenterna som sitter knivigt till och är alldeles för lätta att trycka vid sidan av. Detta är synd, eftersom piltangenterna behövs när man skall slå upp ord i den medföljande ordboken.

Just ordboken är mycket trevlig. Det enda jag önskar är att den kunde agera översättare också. Om man kunde översätta valda ord hade nog mina begränsade kunskaper räckt till att läsa tyska böcker också. (Detta är alltså inget jag testat, så det kanske finns?)


På tal om böcker: Hur är det egentligen med utbudet? Amazon listar 480,000 böcker som tillgängliga i Sverige, medan jänkarna själva kan läsa 710,000 böcker. Detta är alltså böcker på engelska - såvitt jag vet finns inte en enda bok på svenska att få tag på från Amazon. Riktigt varför förläggarna beter sig på det här sättet, både vad gäller antal och språkutbud, kan man fråga sig. Hallå, förläggare! Välkommen till internettidsåldern. Gränser, valutor och artificiella begränsningar hör gårdagen till!

PICT2804

En bra finess är hur som helst att man kan ladda ner första kapitlet av en bok för att provläsa lite innan man halar upp kapitalet. Mindre risk för felköp, och ett trevligt sätt att botanisera på.

Och så länge man håller sig till engelska språket är man ju välförsedd med litteratur. Frågan är hur bra läsupplevelsen blir, om vi förutsätter att själva boken är bra (låt säga t ex Oryx and Crake av Margret Atwood).

Jag skulle vilja säga att det är lite blandat. Typsnitten som används på Kindlen är lättlästa serifer (sans serifer finns att välja för "dagens ungdom"), och texten går att justera storleksmässigt efter personliga preferenser. Som gammal LaTeX-skrivare tycker jag däremot typsättningen är bedrövlig i många fall. Vissa böcker använder lååångt avstånd mellan stycken medan andra (korrekt) har inskjuten första rad i nya stycken. I Eating animals-fallet är citat skrivna högerjusterade - inte vänsterjusterade och centrerade som man skulle förvänta sig. Standardstorleken för texten varierar också mellan böcker.

PICT2806

PICT2805

Hallå, förläggare! Ingen skulle släppa en vanlig pappersbok som såg ut på det sättet, så varför skall eboksläsaren stå ut med eländet? Detta borde vara ett löst problem.

Men läser man bara vanlig skönlitteratur så är inte detta något stort besvär. Avsaknaden av sidnummer var också något jag störde mig på i början, men jag begriper att det inte är möjligt när man är fri att välja teckenstorlek själv. Istället får man gå på "procenten" för att veta hur långt man har kvar på boken. Och har man långt kvar behöver man inte vara orolig. Batteriet räcker ju upp till en månad, vilket verkar stämma vad jag sett hittils. Hela Eating Animals gick i alla fall att läsa ut utan att batteriet gick under ~70%.

Kindlen har också en del extrafinesser. Man kan få boken uppläst för sig, vilket säkert kan vara användbart om man vill vila trötta ögon (jag är ju tydligen skelare numera, så jag kanske borde börja fundera på detta). Det finns också en webbläsare som jag tycker är meningslös. Läsning är egentligen det enda en Kindle passar för.


På det hela taget kan jag säga att jag är nöjd efter en läst bok. Jag har nu en lång lista med böcker - varav de flesta är "samples" av första kapitel. Jag har också laddat ner gratisböcker från gutenberg.org, där man lätt får tag på klassikerna. Calibre kan användas för konvertering och trådlös utskickning till Kindlen. Hur som helst: Kafka i all ära, men det som ligger i kön just nu är The year of the flood av Margret Atwood.

För köpsugna kan jag alltså rekommendera kindlen. Fodralet tycker jag däremot är överflödigt, det ökar vikten ganska rejält och kostar också en slant. Fodralet går loss på omkring $30, och eftersom själva Kindlen bara kostar $139 så ökar det ju priset ganska påtagligt.

Kcov - gcov, lcov and bcov [24 Aug 2010|06:48pm]
(Short version: Kcov, a new project of mine for code coverage testing)

When developing software, I've often found measuring code coverage useful and important for development. A few years ago, I wrote shcov, which provides code coverage measurement for shell scripts. However, traditionally C and C++ code is more important, and the standard tool for measuring code coverage in UNIX is Gcov.

Gcov is unfortunately a bit crude: you have to compile your program with special switches, running the program outputs lots and lots of temporary files and collecting the data is done with a command-line tool. It also adds instructions count each basic block, so in addition it makes your program (slightly) slower. The output can be made nicer by using Lcov (I used the lcov HTML for shcov), but this introduces yet another step in the build/run/collection sequence. Because of all this, I seldomly use gcov despite its usefulness.

But can't code coverage collection be done in some better way? Yes, it can.

Thomas Neumann has written a nice tool called Bcov which improves a lot on the gcov experience: No need for special build switches, a single collection and a single report stage and lcov-style output directly. How does it do this? Well, Thomas realised that all the required information for code coverage is already present in the binary in the form of DWARF debugging information. After all, GDB and addr2line is clearly able to translate instruction addresses into code lines already.

Bcov, I presume, is short for Breakpoint COVerage. It uses ptrace to setup temporary breakpoints in the binary and then run the application until it stops, notes which line the instruction corresponds to and clears the breakpoint, lets it continue until it stops the next time and so on. So bcov replaces gcov and lcov, with the restriction that it doesn't count the number of hits per line, but simply if it has been hit, and all of that in less than 1500 lines of code!


So what is Kcov then? Well, while bcov is a great tool, I still have a few problems with it, so I decided to try to make it better. First, while it's much easier to use than gcov+lcov, it's still two steps (collection and reporting), and I'd like to reduce that to a single one. Second, many applications are long running (or even, like deamons, never terminate), and collecting all output at the end then is hard, so I'd like continuous output. Third, I think the same principle will work for the kernel, which explains the name. That particular part isn't finished yet though, so for now K will have to stand for something else.

The output is still Lcov-like:



and the usage is as simple as I wanted it:
  kcov /path/to/outdir executable [args for the executable]

and the output (you can see an example here) will end up in /path/to/outdir and written to disk around once per second. There are a couple of command-line options to control what should be included in the output, and skipping system headers often make sense.


A few words on the implementation as well (the source is kept at github). Bcov is written in C++, but my limited mental powers couldn't quite manage to get the hang of the source code, so I rewrote it in C. You can still see sections of Thomas source code in many places, especially the ptrace code and the report code. To build kcov, you'll need glib, libdwarf and libelf, which should be available on all Linux distributions.

Have fun, and thanks to Thomas for the excellent Bcov!

Twitter [08 Aug 2010|08:37am]
I've registered a twitter account. Will probably be updated more frequently than this blog.

New bike! [24 Jun 2010|10:10pm]
I've bought a new bike to replace myaging Monark bicycle. It's a Commencal Babylon 2, and looks like this together with it's rider:

new bike

Technically it's not really new though, I bought a used one. This particular bike also has a bit of a history, having been used in a tour of scandinavia by its previous owners.

Cibyl spotted in the wild: Waze [01 May 2010|09:26am]
There has been lots of talk about Wii stuff here the last year or so, but long-time readers of this blog will also remember Cibyl, my MIPS to Java bytecode binary translator project. I've not blogged a lot about it recently simply because I haven't worked a lot on it for quite a while. The two reason for this is that, well, Cibyl works pretty well as it is, and that I now have an Android phone, which can run native C. For me personally, Cibyl has bluntly put been a very complex but fun way of making it possible to play Space Quest on the restroom:



It's perhaps time to say a few words about Cibyl again though, because Cibyl has now been spotted in the wild! Namely in the form of Waze, the crowd-sourcing car navigation software. Waze targets smartphones, so you might be surprised in that it needs something like Cibyl. After all, both the iPhone and Android development environments allow native applications. However, there is one target which still is based on J2ME and is also quite important: BlackBerry. So the recently released beta version of Waze for BlackBerries is built and translated using Cibyl.

Waze is the world-wide and revamped version of Freemap Israel, which also had a J2ME port using Cibyl. J2ME on non-blackberry platforms is probably a dead-end now, so I don't think it makes much sense to carry it forward to Waze, but who knows?



I've obviously downloaded Waze to my Android-based Samsung Spica phone. Unfortunately (well), I haven't been able to use it since I don't have a car, but I follow the development. The map coverage in Stockholm has gone from almost nothing to almost complete in the areas I've looked at. After an article on Waze on Swedroid (the swedish android site, article in swedish), it seems like the Waze community in Stockholm has become a lot more active. There are now typically dozens of wazers on the map at any given time, whereas it used to be one or a few when I looked at it.

Update: Change the Waze image to display the blackberry version instead of Android.

What is it with Fort apocalypse? [25 Apr 2010|08:35am]
There is a connection statistics page for the c64-network.org, which also shows connection screenshots (a feature which was added in the last release). Most people are just connecting from the "blue startup screen", but apart from that the most popular game seems to be Fort Apocalypse.



while I also thought that was a nice game, it's hardly my favorite. That would be Bruce Lee.

Tors torn [28 Mar 2010|08:45am]
The view from our balcony will be something like this if these get built:

tors-torn-balkong

With Stockholms history of skyscrapers, I'm not sure this is such a great idea, but we'll see.

Problem spotting, part II [24 Mar 2010|08:57pm]
So what was the bug in the last post? (Screenshot below for those that missed it)



Well, I've already got two correct answers: It's a classical byte order problem. It comes from UAE-Wii, and I've had this problem for quite a long time. I only found out what was causing it last week, thanks to some questions by Fredric Blåholtz, and I actually realised what the problem was when going to bed one night.

The reason I didn't understand the issue quicker (maybe apart from general slowness!) was that the graphics works well in games. I therefore assumed that this was caused by the Wii resolution (640x480) and problems with scaling it to 640x512. Fredric showed me that it works fine on the host when using 640x480, so this couldn't be the problem.

But byte order can. With 16-bit color depth, the relevant part of drawing looks like this:
while (dpix < stoppos) {
            uae_u32 spix_val;
            uae_u32 dpix_val;
            uae_u32 out_val;
        
            dpix_val = xcolors[ham_linebuf[spix]];
            spix++;
            out_val = dpix_val;
            dpix_val = xcolors[ham_linebuf[spix]];
            spix++;
            out_val = (out_val << 16) | (dpix_val & 0xFFFF);
            *((uae_u32 *)&buf[dpix]) = out_val;
            dpix += 2;
}

and as you can see, it's done in chunks of 32-bit stores. Uh oh. Problem.

This particular source code is generated by a tool shipped with UAE. Autoconf is a true horror to work with though, so I resorted to just putting together the makefile for the Wii port by myself instead. And took a few shortcuts - like generating the files once and for all. So on the big-endian Wii, the two neighboring 16-bit pixels are swapped (see the last assignment to out_val). With half-resolution (320x256) the problem doesn't show, simply since the order of two same-colored pixels doesn't matter.

In hindsight, the problem is pretty obvious.

Spot the problem here [21 Mar 2010|05:11pm]
Can you see what's causing the garbled graphics in this image?



I'll explain in the next post. If someone comes up with the correct guess, they obtain the exclusive ownership of eight snowflakes in Stockholm.

navigation
[ viewing | most recent entries ]
[ go | earlier ]