A funny (but probably useless) formula. The left-hand side is the XOR of integers from 1 to n, the operators are the usual C bitwise operators.

1 ^ ... ^ n = (n >> 1) & 1 ^ (n&1 ? 1 : n)

It's totally trivial to prove (just write the sequence of XOR values and look at the pattern), but, before you think about it, it's not that obvious that a closed formula exists.

Of course, this formula directly yields a closed-form expression of the XOR of integers from m to n, for any m and n: just compute the XOR of integers from 1 to m-1 and from 1 to n and XOR them together. Thanks to Nathan D. Ryan for suggesting this.

I just wrote wikifirc, a small IRC bot to follow recent changes for specific Wikipedia pages or users in realtime. You can use it as an IRC watchlist, as a way to follow changes by your friends, and maybe more. A very tiny tool, but just in case someone needs this... It's intended to read and send IRC messages from stdin and stdout, so you probably need irctk, which still isn't stable yet but will be properly released Real Soon Now. More information about wikifirc is available in the README.

This post is of a more general and "philosophical" nature, which means that it might sound totally obvious if you agree with me and have already thought the same things. I am just writing this in the hope that there are people who haven't realized that they agree with this, or disagree with this, or had never even thought about this. (On a related note...)

How do you define your identity? Several things come to mind. Your name, nationality, gender, body, date of birth, nationality, the schools you attended, the places you traveled to, your friendships, your family, important experiences you had, stuff you own, important things you did, your hobbies, your tastes, your job, your beliefs, your values, your opinions...

But which ones really define your identity? Or, to be more precise, which ones would you say define yourself as a person? It would be things without which you think you wouldn't be the "same" person anymore. This idea is not mine (it has been suggested by Douglas Hofstadter, at least), it is not clear-cut at all and might not really be meaningful because it's pretty hard to tell what being the "same" person really means. Still, it gives a criterion to rate the answers to the previous question. Would you be able to imagine being you, but with a different name? Probably. Could you imagine being the same person with a different nationality? I think I could, but this is less clear. Are your hobbies really important, in that they are something that you cannot imagine not doing? Or are they just things which you happened to take some interest in, but whose nature isn't that important. (When you say that you enjoy singing or reading, do you mean this because it's important to you or just because it's just a pleasant way to spend your time?)

The question there is not about whether things would have turned out differently if you had made different choices, but about things would have been superficially different but fundamentally the same. Don't be mistaken either by the fact that citizens of a same country, or students of a same university, or people of the same gender, are usually expected to display some solidarity as compared to the outside world. If you make choice x, you tend to socialize and sympathize with x-ers, but had you made choice y, you would have sympathized with y-ers. So, solidarity with x-ers does not mean that x is an obvious part of your identity if you could imagine yourself choosing y and showing solidarity to y-ers instead.

So, now that you have a list of things that are part of your real identity, the next question is, obviously, what's so special about those? Somehow, you're probably assuming that these traits not only make you a different person, but also a better person. (You might argue that what you perceive as your identity includes sad and painful experiences, but my point is that you're probably thinking that they made you wiser.) So, how do you justify that? Think about, say, the important decision of choosing to go to university x instead of university y. Had you chosen y instead, you would have missed all those important defining experiences X that you had and all your important friendships and interactions with other x students. However, you would have had other experiences Y, which you have no way of knowing. Your belief that set X is fundamentally different and somehow more defining that unknown set Y is totally intuitive and not falsifiable!

This should annoy you. Once again, if you're like me, you tend to dismiss as hopelessly stupid the people who, being born in country x and not really knowing anything else, are proud of their x citizenship, and are x nationalists, convinced of the universal superiority of x. Of course x might be actually superior, but by the Copernican principle, it's quite unlikely that you should happen to be born precisely there. It's better to avoid this kind of arbitrary belief in the superiority of something, yet the above reasoning puts us in the same uncomfortable situation. What can we do?

The tempting thing to do is something argued by Paul Graham in Keep Your Identity Small. Those things that you consider as part of your identity make you poorer. If you say you are fundamentally x and couldn't be anything else, then you will never be able to take deliberate steps to try y out. Conversely, if you say that you happen to be x but could have been y, it also means that you leave open the possibility of becoming y in the future. That's what Graham says, but the reasoning above gives us another reason to keep our identity small: because it's hard to justify why you put something there. At least, we could try to limit the damage and derive our important choices and stances from a few basic abstract principles. The hope, after all, is to find out who you are really, ie. the axioms of your identity, and not their observable consequences.

This leads to pretty weird questions. If you're into computers, is it part of your identity to try to understand your computer? Or understand computers? Or understand the general mechanisms of information processing and retrieval? Is this musical instrument part of your identity, or the general notion of music playing? or performance art? or just art? Is it a given piece of music, or a music genre, or rather some precise point of that piece of music? And then, of course, comes the risk of trying to hide behind the abstract (ie. "I don't love football, I love the concept of people competing against one another to move a certain object according to certain rules"), and the question of whether all this reasoning really has universal value anyway. You might think of bullfighting as a convoluted and not very kind way to slaughter bulls, but someone who love bullfighting might have abstract explanations of why it has universal symbolics, which must mean a lot to them, but would not convince anyone else. Is there really a connection between those things that define you that you could explain in a convincing way to other people?

The worse is that you may feel the existence of a connection, but not be able to explicit it. Your identity, reduced to basic principles, is the key to explain what your various interests, hobbies, experiences and achievements have in common, and you may have that tantalizing impression that this unexplainable fascination you have for the Korean writing system, or overtone singing, or Bach fugues, is somehow related to the rest, but you couldn't explain how. And this is but a feeling, and there is no way to make sure that this isn't just wishful thinking, or a posteriori justification of those various quirks that you irrationally argue are essential parts of your identity.

Then, of course, along with the risk of being unable to make sense of all this mess, there is the risk that you might be missing the most important things--that you may have beliefs which are so deep that you don't even notice them anymore. This is quite harmful too, but how could you know?

And then there are all the practical difficulties with keeping your identity small. Someone who considers x as part of their core identity will tend to sympathize with other die-hard x-ers more than people who think that they just happen to be x, so this is not the best way to be close to people. Furthermore, if having a lot of fundamental guiding traits reduces the area of what you can do, it can also orient you and help you, whereas if you try to exclude as little as possible, you have more options to consider and more choices to make. (I am interested in everything, I can do everything, where do I start?) Last, you might become less willing to engage in a large project x, lest the fact of having investing time in x makes you irreversibly a member of x, preventing you from switching sides to y if you feel like it.

This last point, actually, is another think to keep in mind: since your life will only last that long, those unimportant choices you made just become part of your identity with time as you get less and less time to prove to others and to yourself that you could have lived differently. Some things, like your name or date of birth, are a given and will not tend to define you more with time, but others do. You can say, "I lived 20 years in the USA, but I do not consider that part of my identity because I could have lived elsewhere and because I could perfectly imagine moving elsewhere if I wanted to; I just happened to live the last 20 years in the USA." But imagine that same sentence with 60 instead of 20. No matter what, in that case, the bulk of your life was spent in the USA; it's much harder to toss it away as something that just happened but wasn't important.

Something I hate about Android is that there are almost no bridges between the usual *nix command-line world and the brave new world of Java. If things had been done properly, for instance, you would be able to ssh to your phone and run a trivial bash one-liner to save the current GPS coordinates to the SD card every 30 seconds, instead of having to write a verbose Java application to do that (or installing a third-party app which will come with all sorts of bells and whistles). Also, if things had been done properly, there wouldn't be obscure terminal glitches and bizarre and gratuitous deviations from the FHS...

Now, my Android phone fell, the screen broke, and I am left with a perfectly functional ARM-based computer with a lot of usable hardware, such as:

• Wifi with master mode support
• Speakers and headphone plug
• Microphone and camera
• GPS
• Vibrator and notification LED
• GSM
• Bluetooth

I have root access to the device, I can get a shell through adb, there are a lot of cool things that I could do with this if only using Android from the command-line wasn't that much of a pain. So here are a few notes I took as I explored all of this, in case someone finds them useful. The phone is a HTC Desire, the ROM is Cyanogen 7.1.0 if I remember correctly (not that it matters), I am root, and NAND protection is disabled (aka. S-OFF).

Connecting to WiFi (managed mode)

It is not that hard to connect to WiFi (using wpa_supplicant and dhcpcd) except for a few quirks. I assume that you are familiar with wpa_supplicant configuration files and with wpa_cli's rudimentary interface (just a tip if you didn't know: you just need to type non-ambiguous prefixes for commands).

# this will fail unless you are S-OFF
mount -o remount,rw /
mount -o remount,rw /system
# took some time to find out
insmod /system/lib/modules/bcm4329.ko 
# yes, the wifi interface is called "eth0"...
mkdir /eth0
cd /
# edit /etc/wifi/wpa_supplicant.conf to define your APs
wpa_supplicant -B -Dwext -ieth0 -c/etc/wifi/wpa_supplicant.conf
# use wpa_cli to select the AP to associate with
wpa_cli -p /eth0/
pkill dhcpcd
# remove dhcp leases
rm -Rf /data/misc/dhcp/*
dhcpcd eth0
# beware: DNS is slow and not very reliable, if pinging a domain doesn't work
# try pinging an IP before declaring failure

Setting the time

The time is reset each time you remove the battery, and of course you must set it from the command line. To do so, if you have an Internet connection, an easy way is: ntpd -p 64.90.182.55. (Alternatively, substitute the IP of your favorite public NTP server.) Don't forget to do this, or you can get weird errors (for instance, openvpn will complain about certificates not being valid yet).

Getting Debian

Since Android does not come with any sort of package manager, the standard way to install stuff on Android is by chrooting in a Debian install. This process is pretty well documented here and here so I won't explain it all over again. As Daniel Wallenborn pointed out, recent open source applications such as Lil' Debi or Debian Kit can now be used to make this process even simpler. Notice however that the first guide forgets to say that you should export TERM=xterm and export PATH="/bin:/usr/bin:/usr/sbin:$PATH just after chrooting. If you follow the first guide, you will get a VNC server, so you can VNC to your phone and interact with graphical programs. (Graphical programs from the chrooted Debian, of course, not from Android.) Not extremely useful, but pretty neat.

Creating a WiFi access point (master mode)

This is much more difficult. First, you must load the WiFi module with an alternative firmware. (Obviously, rmmod it first if it is already loaded. Or, to be sure, reboot the phone...)

insmod /system/lib/modules/bcm4329.ko firmware_path=/system/vendor/firmware/fw_bcm4329_apsta.bin

Now, using iwconfig directly doesn't seem to work. The only reproducible way I found to reliably create an AP is to use the mysterious binary program res/raw/ultra_bcm_config from android-wifi-tether. Check out the code, send this file to the phone (using adb push or anything else) and run (where AP is the name of the access point you would like to create and CHAN is the channel):

ultra_bcm_config eth0 softap_htc AP none "" CHAN

I wonder what this program does. Next, perform:

iwconfig eth0 essid AP
ifconfig eth0 address 192.168.2.1

Now, you need to serve DHCP leases. Android uses dnsmasq to do this.

mkdir -p /var/run
cat > /data/dnsmasq.conf <<EOF
dhcp-authoritative 
interface=eth0
dhcp-range=192.168.2.100,192.168.2.105,12h
user=root
no-negcache
EOF
dnsmasq -C /data/dnsmasq.conf

You should now be able to connect to the phone and get a DHCP lease. Hurray!

Changing your MAC

The usual command ip link set eth0 address 00:11:22:33:44:55 will sometimes work. If it doesn't, reboot and try again.

Creating a captive portal

I didn't even try to get a data connection over GSM operational from the command-line (I would probably need the screen to enter the SIM PIN anyway) and I didn't try yet to "reverse-tether" and create an AP to share an ethernet connection (going through a laptop, ie. the laptop has ethernet connection, the phone is plugged to the laptop and shares the connection over WiFi). Hence, the phone cannot have Internet access when it creates an access point. Yet, there are a lot of neat things to do with a battery-powered WiFi AP that you can carry in your pocket. A WiDrop? Access to a static Wikipedia mirror?

Yet, to do that, you need to present these services to the user. As far as I know, there is no standard describing how this should be done, and the best you can do is intercept all HTTP traffic and hope that the user is running a web browser... Here is a simple solution which does not require you to install real fat captive portal software. Warning, just in case you're skim-reading through this, the setup described here only tries to intercept HTTP connections, not every kind of traffic--don't do this if the phone has an Internet connection somehow and you want to be sure the clients are blocked for real.

First, we need to ensure that clients can get DNS service. Since usual DNS servers are not reachable (because the phone has no Internet connection), we need to (a.) run a DNS server on the device and (b.) intercept all DNS requests to third party hosts and answer them ourselves. Pretty easy to do, since dnsmasq can serve as a lightweight DNS server:

cat >> /data/dnsmasq.conf <<EOF
address=/#/192.168.2.1 
EOF
iptables -t nat -A PREROUTING -p udp --dport 53 -j REDIRECT

Second, we need to redirect all HTTP connections towards ourselves, just in case someone tries an HTTP connection without using DNS first (you never know, especially if the client has a DNS cache or something like that).

iptables -t nat -A PREROUTING -p tcp --dport 80 -j DNAT --to-destination 192.168.2.1

Third, we need to run an HTTP server on the device. The easiest way to do that is to run it within the Debian chroot. It just works.

Fourth, we need the HTTP server to answer even if a weird path is requested. The quick and dirty way to do this is to set up the 404 page as a redirection to the index page. For instance, with lighttpd:

server.error-handler-404 = "/index.html"

Of course, this messes up the HTTP status code, though. Finding a better solution is left as an exercise. (For my purposes, I don't really care.)

Knowing the battery status

Don't even think about using acpi! I hunted for relevant stuff in /sys but couldn't find anything, so the only approach I found is:

dmesg | grep batt: | tail -1

Lars Rasmusson pointed out that relevant files are /sys/devices/platform/msm-battery/power_supply/battery/voltage_*. It might depend on your phone model, but it is probably a good idea to run find power_supply /sys.

Activating the vibrator

The vibrator is a useful way to get notified about what happens.

# the bigger the value, the longer the vibration will last
echo 100 > /sys/devices/virtual/timed_output/vibrator/enable

If you want to trigger the vibrator from a program which isn't run as root (e.g. the HTTP server), don't forget to change the permissions of the file.

Activating the flashlight

# values can be between 1 and 255, though the led seems to power down by itself
# for values over 128, maybe because the hardware cannot sustain them for long
echo 1 /sys/devices/platform/flashlight.0/leds/flashlight/brightness

Playing music

An extremely pleasant surprise: there is a command to play a sound file!

stagefright -a -o file.mp3

An extremely unpleasant surprise: the command isn't documented and is extremely limited. Probably a debugging tool that someone forgot to remove.

Webcam acquisition

Don't get your hopes up, I didn't manage to get this to work. If you're only interested in stuff that works, you can stop reading this post here. Ogurets pointed out that webcam aquisition is possible using ad-hoc code on some chipsets to invoke ioctl, for instance with the vc088x SoC. Ogurets writes: This stuff is very hardware-dependent, you could quickly check your hardware by listing /dev: if you have "cif", "video", "venc", "v8-tv" devs, then you have a VC088x SoC and the code will work for you. Otherwise, you could download kernel source code for your device (the manufacturer has to publish it due to GPL) and find proper ioctls for your camera, then write a similar program for yourself. I have not tested this code on the HTC Desire, however. For completeness I reproduce below my original steps to try to get the webcam to work, even though they seem much less promising.

Now, here are some notes about what I tried. There is no /dev/video0 device and there doesn't seem to be any comparable device anywhere, so my guess is there is no V4L support. I ran mplayer and vlc from the Debian chroot in the hope that things could automagically work, but to no avail. Apparently, the Android piece of software which handles the webcam is called Stagefright, the documentation of which is a blogpost by a Google intern and the source code itself (think there must be better docs? think again). The job is split between Java (which provide the bindings that regular app developers use) and C++ (the native code you're not supposed to be writing) which performs the actual work including stuff like hardware acceleration of some codecs. Apparently, someone did something clever: an stagefright interface for libav. Sadly, the only documentation available, this time, is a Youtube video. I managed to compile it after days of stupid mistakes (if you want to try it yourself, make sure you check out the right branch, use tools/build_libstagefright with the NDK variable set to the path to the Android NDK (which contains the cross-compiler), and use make V=1 to troubleshoot issues). Sadly, it either hangs or fails with unhelpful error messages at runtime. Maybe it's because the guy doesn't have the same phone model. The next way would be to use gdb or something like that, but I'm a bit discouraged... please tell me if you managed to make this work.

A community project is an interaction between a community of users who create a resource and a host which stores and serves this resource. Extremely useful and valuable resources such as Wikipedia have been created in this way, and it is easy to feel compelled to contribute to such projects to "give back" to the community. However, in some cases, you could end up benefiting the host more than the community, because the terms of the relationship between community and host are unfair.

Here is an example of this. CDDB was an early collaborative effort to create a database of audio CDs. It started as a one-man effort to which anyone could contribute by email. As time passed, it was incorporated, then bought, then renamed, and access to the database became burdened with restrictions to serve the commercial interests of the host. The users who contributed to the project had actually helped someone to create their product, and that someone ended up using the product against the community's interests.

What went wrong here? Does this mean that the Wikimedia foundation could start to act unethically towards the community? Fortunately not: there is a difference in forkability between Wikipedia and CDDB. I say that a community project is forkable if anyone in the community can take a copy of the content and host it somewhere else. Forkability ensures that the host cannot take the content away from the community. Furthermore, it is a strong guarantee of the optimality of the hosting service, because it ensures that anyone can start to compete with the host.

There are two facets to forkability, which are:

Legal forkability.

Do you have the right to fork? This is satisfied if the resource is under a free license; it is not satisfied if users keep their copyright but grant the current hosting service a right to host the content, or (worse) if they assign their copyright to the host. To publish their content, users should waive the rights that stand in the way, not privilege the current host in any way.

Practical forkability.

Do you have the capacity to fork? This is satisfied if dumps of the resource are provided by the hosting service in an open format (ie. not requiring specific proprietary software); it can still be satisfied if the hosting service allows users to crawl the resource. It is not satisfied if the hosting service tries to prevent crawling or forbids it in their TOS.

Some community projects today are forkable:

• Wikimedia projects are under the free CC-BY-SA license and dumps are available. (Incidentally, these dumps aren't just an abstract guarantee against wrongdoing; they are extremely useful resources for researchers or for people who need a local mirror of Wikipedia.)
• StackExchange projects such as StackOverflow are under CC-BY-SA too and dumps are available (though, sometimes, Stack Exchange thinks they can decide how their users' content should be attributed -- a host should specify a suggested mode of attribution but should not assume that users will not be more lenient).
• MusicBrainz (a modern alternative to CDDB) is available under a combination of public domain and CC-BY-NC-SA and provides dumps.
• OpenStreetMap provides dumps, and though its legal situation isn't clear (it seems that you have to assign copyright to the OpenStreetMap foundation who guarantee that the content will always be available under a free license), I'm pretty sure that this is fine in practice.
• Project Gutenberg has a convoluted license for its ebooks, but you can strip it from the public domain books and get public domain content, and you are welcome to mirror it.

Sadly, examples of non-forkable projects today are also numerous:

• Google Maps welcomes people to contribute, but it is not forkable.
• Most reviews websites are not forkable. For instance, the Yelp TOS require you to grant them a license to use your content, and prohibits any practical attempts to crawl the content. Reviews on websites such as Amazon are also examples of collaboration to create non-forkable content.
• ReCAPTCHA is not really a community project but is worth mentioning because you get the same sort of enthusiasm ("awesome! I can help digitize books by completing captchas") before you realize that reCAPTCHA is really Google, that Google never guarantees that you will be able to fork the content that you helped to digitize, and that they are using reCAPTCHA to improve StreetView which is definitely not-forkable.

I don't know of any forkable alternative to Yelp or reCAPTCHA, though I can't see any good reason why such alternatives couldn't exist and thrive (except that they are hard to bootstrap).

So, before you contribute to a community project, make sure that the resource doesn't just belong to the host, but really belongs to the community (and just happens to be hosted in a centralized place). Forkable community projects are, in my opinion, the only ethical alternatives to federated projects; they are a bit worse because they require one master host to exist and because there will always be some degree of inertia before people start to fork, but they are the best that we can do whenever centralization is a technical requirement.