2014-10-26

How to download some labeled messages from Gmail to a Unix computer

This blog post explains how to download some Gmail messages (distinguished by a label) to a computer running in Unix. The download method shown works in headless mode, so it can be run from cron etc.

Preparation instructions

  • You will need a computer running Unix and which can run Fetchmail. Your mail will be downloaded to a file (in mbox format) onto that computer.
  • If Fetchmail is not installed to that computer, you need to install it (which needs root privileges) or get the admin install it for you.
  • You will have to add your Gmail e-mail address and password to a config file which will be stored on the Unix computer running fetchmail. If this is not secure enough for you, then please don't continue.

Gmail setup instructions

  • Create a Gmail account if you don't already have one.
  • Log in to Gmail in a web browser (can be on any computer).
  • In Settings (the gear button) / Forwarding and POP/IMAP, select Enable IMAP, and save the changes. Click on the Save button.
  • Create two labels, one of them (let's call it foo auto) will be used by Gmail to track which messages have been downloaded already. After a download, Gmail will automatically remove that label. The other label (let's call it foo manual) is for your reference only.
  • If you already have some e-mail in your inbox to be downloaded, apply both labels to them, manually (or by searching).
  • If needed, set up a filter (in Settings / Filters / Create new filter) which will apply both labels to incoming messages you want to be get downloaded.
  • Go to https://www.google.com/settings/security/lesssecureapps in your browser, and enable less secure apps (such as Fetchmail).

Unix computer setup instructions

  • Log in to the Unix computer you wan to download the messages to. Typically such login is done using SSH.
  • Install fetchmail, put it to $PATH (usually /usr/bin/fetchmail from package). Version 6.3.9 works, but probably older versions work too. On Debian and Ubuntu, it is as easy as running (without the $):
    $ sudo apt-get install fetchmail
  • Create a directory which will hold your downloaded mail. For example:
    $ mkdir downloaded.mail
    $ cd    downloaded.mail
  • Create a plain text config file with the contents below, and copy it to the Unix computer, to the downloaded.mail directory. Typically the copying is done using scp or rsync. Don't forget to change the USERNAME, PASSWORD and foo auto settings to reflect your Gmail account. (If it's inconvenient for you to edit files on the Unix computer, change it first locally, and then copy it again).
    defaults:
    mda "exec >>download.mbox && echo From MAILER-DAEMON Thu Mar 29 23:43:41 2007 && cat"
    poll imap.gmail.com
    proto IMAP
    user "USERNAME@gmail.com"
    pass "PASSWORD"
    # Gmail will auto-remove this label as soon as the message has been downloaded,
    # so it won't get downloaded again at the next run.
    folder "foo auto"
    ssl
    # Also download read messages.
    fetchall
  • Make sure the config file on the Unix computer has the filename download.fetchmailrc. Here is an example how to rename it:
    $ mv download.fetchmailrc.txt download.fetchmailrc
  • Revoke other users' access to the config file, protect your password from being stolen. Please note the star at the end:
    $ chmod 700 download.fetchmailrc*
  • Create the output mbox file and protect it:
    $ : >>download.mbox
    $ chmod 700 download.mbox
  • In the downloaded.mail directory, run:
    $ fetchmail -f download.fetchmailrc

    This will download and append all your Gmail messages with the label foo auto to the file download.mbox to the downloaded.mail directory on the Unix computer, and remove the label foo auto, so when you run the command again, messages already downloaded won't be downloaded again. (Gmail labels are global, so you have to define additional labels if you want to download mail to several computers.)

  • If you get this error:
    .../.fetchmail.pid: Permission denied
    Then add --pidfile fetchmail.pid (without the quotes) to your fetchmail command-line.
  • If you get this error:
    fetchmail: Authorization failure on ...@gmail.com@...
    fetchmail: Query status=3 (AUTHFAIL)

    Then visit http://www.google.com/accounts/DisplayUnlockCaptcha from any web browser, unlock it, and run the fetchmail command again.

  • If needed, set up a cron job which will download automatically for you. Typically you can download once per minute, once per hour or once per day using cron jobs.

Incremental download instructions

  • Log in to the Unix computer you wan to download the messages to. Typically such login is done using SSH.
  • Change to the downloaded.mail directory:
    $ cd downloaded.mail
  • In the downloaded.mail directory, run:
    $ fetchmail -f download.fetchmailrc

    Messages already downloaded won't be downloaded again, because they don't have to foo auto label anymore. (Gmail labels are global, so you have to define additional labels if you want to download mail to several computers.)

2014-10-21

On the speed of memset

This blog post presents some of the speed measurements I've done with alternative implementations of memset.

I was filling a 1 GB memory area 20 times (equivalent to memset(a, 0, 1 << 30) each) with various different implementations, and measuring the speed. I've compiled the program for i386 (gcc -m32) and amd64 (gcc -m64), I ran it on desktop PC running 64-bit Linux 3.13.0 on a Xeon CPU (Intel(R) Xeon(R) CPU E5-1650 v2 @ 3.50GHz) with 32 GB of RAM. I was compiling the code with GCC 4.6.3, with optimization level gcc -O2, because gcc -O3 optimized the 1-byte-at-a-time loop to a 4-bytes-at-a-time loop.

It turned out that there was no measurable difference in the i386 and amd64 version of the programs. Here are relative speeds (higher numbers are proportionally faster) of user times:

  • 1.480: memset, doing rep stosd, 4 bytes at a time
  • 1.000: 16 writes of 4 bytes each in loop the body (like Duff's device)
  • 1.000: 1 write of 8 bytes in the loop body
  • 1.000: 1 write of 4 bytes in the loop body
  • 0.675: 1 write of 2 bytes in the loop body
  • 0.329: 1 write of 1 byte in the loop body (char *cp = a, *cpend = a + sizeof(a) / sizeof(a[0]); for (; cp != cpend; ++cp) *cp = 0;)

I can interpret the numbers except for memset the following way: the cache doesn't help at this size; CPU does correct branch prediction (or taking the branch is fast enough), or taking a branch is faster than writing to memory; the data bus between the CPU and the memory can take 4 bytes at a time.

But why is the assembly instruction rep stosd that much faster than any of the loops? What's the magic behind it? It looks like my CPU had an optimized rep stosd and rep stosb built in, called ERMSB. More details in the PDF available from here (search for memset within the downloaded PDF).

2014-09-25

Change 1 character puzzle #2

Add or replace at most 1 character in the longest line of the following program so that it will print 20 dots. There are at least 10 solutions.

#include <stdio.h>
int main() {
  int i, n = 20; for (i = -n; n > i; i++) putchar('.');
  return 0;
}

SPOILER ALERT! Here are 10 solutions:

int i, n = 10; for (i = -n; n > i; i++) putchar('.');
int i, n = 20; for (i = -0; n > i; i++) putchar('.');
int i, n = 20; for (i = -!n; n > i; i++) putchar('.');
int i, n = 20; for (i = n-n; n > i; i++) putchar('.');
int i, n = 20; for (i = -n; !n > i; i++) putchar('.');
int i, n = 20; for (i = -n; 0 > i; i++) putchar('.');
int i, n = 20; for (i = -n; n * i; i++) putchar('.');
int i, n = 20; for (i = -n; n & i; i++) putchar('.');
int i, n = 20; for (i = -n; n = i; i++) putchar('.');
int i, n = 20; for (i = -n; n , i; i++) putchar('.');

Change 1 character puzzle #1

Add or replace at most 1 character in the longest line of the following program so that it will print 20 dots. There are at least 3 solutions.

#include <stdio.h>
int main() {
  int i, n = 20; for (i = 0; i < n; i--) putchar('.');
  return 0;
}

SPOILER ALERT! Here are 3 solutions:

int i, n = 20; for (i = 0; -i < n; i--) putchar('.');
int i, n = 20; for (i = 0; i < n; n--) putchar('.');
int i, n = 20; for (i = 0; i + n; i--) putchar('.');

2014-09-08

How to keep to your commitments without using up too much willpower

This blog post explains how hyperbolic discounting causes you to change your mind, and how to trick it so that you can keep to your commitments without using up too much willpower.

A student who doesn't learn as much as he wants to

A student has an exam on Friday. He has 4 days (Monday, Tuesday, Wednesday and Thursday) to learn. The more he learns, the more points he will get for the exam. On each learning day, he may choose to skip learning and go to a party instead. It happens that the previous week he decides that he will learn for 3 days, but during the week it turns out that he learns only once, and goes to parties on 3 days. How can this happen?

Explanation with hyperbolic discounting

This can be explained by assuming that the mind does hyperbolic discounting, i.e. it computes today's utility of a future event by dividing the utility of the event divided by the number of days of delay. See the more specific example below:

Hyperbolic discounting for time for the utility of u today:

  • same thing tomorrow: u/2
  • same thing in 2 days: u/3
  • same thing in 3 days: u/4
  • same thing in 4 days: u/5
  • same thing in 5 days: u/6

Utility function for today:

  • take the exam, get x points (where x is the number of days previously spent learning for the exam, x in 0..4): 60*x
  • party: 29
  • have a rest: 0
  • learn: 0
Previous Sunday:
  • learn on Monday–Friday: 60*4/6 = 40
  • party on Monday–Friday: 29/2+29/3+29/4+29/5 = 37.216...
  • party on Monday–Tuesday, learn on Wednesday and Thursday: 29/2+29/3+60*2/6 = 44.166...
  • learn on Monday–Tuesday, party on Wednesday and Thursday: 60*2/6+29/4+29/5 = 33.05
  • party on Monday, learn on Tuesday–Thursday: 29/2+60*3/6 = 44.5
  • party on Monday–Wednesday, learn on Thursday: 29/2+29/3+29/4+60/6 = 41.416...
  • ... (there are a few other cases)
  • what will happen: The student decides to party on Monday, and to learn on Tuesday--Thursday.

Monday:

  • learn on Monday–Thursday: 60*4/5 = 48
  • party on Monday, learn on Tuesday–Thursday: 29+60*3/5 = 65
  • party on Monday–Tuesday, learn on Wednesday–Thursday: 29+29/2+60*2/5 = 67.5
  • party on Monday–Wednesday, learn on Thursday: 29+29/2+29/3+60/5 = 65.166...
  • party on Monday–Thursday: 29+29/3+29/3+29/4 = 55.583...
  • ... (there are a few other cases)
  • what will happen: The student parties on Monday, and decides to party on Tuesday, and to learn on Wednesday--Thursday.

Tuesday:

  • learn on Tuesday–Thursday: 60*3/4 = 45
  • party on Tuesday, learn on Wednesday–Thursday: 29+60*2/4 = 59
  • party on Tuesday–Wednesday, learn on Thursday: 29+29/2+60/4 = 58.5
  • party on Tuesday–Thursday: 29+29/3+29/3 = 48.333...
  • ... (there are a few other cases)
  • what will happen: The student parties on Tuesday, and decides to learn on Wednesday--Thursday.

Wednesday:

  • learn on Wednesday–Thursday: 60*2/3 = 40
  • party on Wednesday, learn on Thursday: 29+60/3 = 49
  • party Wednesday–Thursday: 29+29/2 = 43.5
  • ... (there is one more case)
  • what will happen: The student parties on Wednesday, and decides to learn on Thursday.

Thursday:

  • learn on Thursday: 60/2 = 30
  • party on Thursday: 29
  • what will happen: The student learns on Thursday.

Friday:

  • take the exam on Friday: 60
  • don't take the exam on Friday: 0
  • party on Friday: 29
  • what will happen: The student takes the exam, scoring 1 point.

So hyperbolic discounting causes the student to change his mind several times during the week: he will do something else on Tuesday and Wednesday than what he decides on Sunday. On Sunday he was planning to learn later next week, and get 3 point on the exam. But he will end up learning only on one day, and getting only 1 point on the exam.

How to keep to your commitments you've made to yourself?

Instead of hyperbolic discounting, let's calculate with exponential discounting.

Exponential discounting for time for the utility of u today:

  • same thing tomorrow: u/2
  • same thing in 2 days: u/4
  • same thing in 3 days: u/8
  • same thing in 4 days: u/16
  • same thing in 5 days: u/32

It can be proven that with exponential discounting you would never change your mind: the relative utility of outcomes remains the same as time passes, there won't be any inconsistencies.

Unfortunately, some experiments show that hyperbolic discounting is hardwired into your mind, and you have no conscious power over it, you can't replace it with exponential discounting at will.

Excercising willpower is easier said than done, particularly that each person has a limited amount of willpower, and if it gets depleted, one has to wait for it to get refilled. So depending on the challenges you had previously on that day, you may have no willpower left to stay away from the party.

Another option you have is limiting and committing yourself to the same choice for a prolonged period of time. For example, if the student commits himself to do the same activity on Monday, Tuesday and Wednesday, then he will choose learning on all the 4 days, and he will actually do it.

2014-08-16

On generating integer-sided triangles with an integer area/perimeter ratio

This blog post contains come comments about finding all triangles whose sizes are integers and the area/perimeter ratio is the integer r. This is related to Project Euler problem 283.

The blog post contains a nice analysis and some pseudocode for generating all possible (a, b, c) size triplets for the given ratio r. Unfortunately both the analysis and the pseudocode contains some mistakes.

Here is the corrected version:

def find_triangles_correct(r):
  for u in divisors of 2r:
    for v in 1 to floor(sqrt(3) * u):
      if gcd(u, v) == 1:
        lhs = 4*r*r*(u*u+v*v)
        for d1 in positive divisors of lhs:
          if d1 <= lhs / d1:
            d2 = lhs / d1
            if not (u < v and d1*u < (2r(v*v-u*u))):
              if ((d1+2ru) mod v) = 0 and ((d2+2ru) mod v) = 0:
                a = (d1 + 2ru) / v + 2rv / u
                b = (d2 + 2ru) / v + 2rv / u
                c = (d1 + d2 + 4ru) / v
                yield a, b, c
Some mistakes and other inaccuracies in the original:
  • The variable r were silently renamed to m.
  • The formulas for a, b and c were not included.
  • The analysis incorrectly states that v must be smaller than floor(sqrt(3)*u)). The correct statement is: v must be smaller than sqrt(3)*u. Before the correction some solutions such as (6, 8, 10) for r=1 were not generated.
  • The condition d1 <= lhs / d1 had a >= instead.

Please note that the algorithm yields each triangle once, in an unspecified order of a, b and c within the triangle.

2014-08-12

How the lifetime of temporaries is extended because of references in C++

This blog post summarizes what I learned about C++ today about how the lifetime of temporaries is extended because of references.

Normally a temporary is destroyed at the end of the statement, for example temporary string returned by GetName() lives until the end of the line defining name. (There is also the return value optimization which may eliminate the temporary.)

#include <stdio.h>

#include <string>
using std::string;
string GetName() {
  return string("foo") + "bar";
}
int main() {
  string name = GetName();
  printf("name=(%s)\n", name.c_str());
  return 0;
}

However, it's possible to extend the life of the temporary by assigning it to a reference-typed local variable. In that case, the temporary will live until the corresponding reference variable goes out of scope. For example, this will also work and it's equivalent to above:

#include <stdio.h>
int main() {
  const string &name = GetName();
  printf("name=(%s)\n", name.c_str());
  return 0;
}

Please note that there is no lifetime extension if the function returns a reference, and also in some other cases related to function boundaries. See more details about reference initialization.

2014-07-29

How to discard committer info from git history

This blog post explains how to overwrite the git committer name, git committer e-mail and git committer date in previous commits in a git repository. This is useful e.g. after a series of git commit -C ... calls, which copy the author name, e-mail and date from the specified commit, but use the committer name, e-mail and date from the environment of the command.

Please note that rewriting git history is potentially dangerous because it can lead to data loss and synchronization issues with others who pull from the repository. Read more about it in Git Tools – Rewriting History.

First make sure you don't have any uncommitted changes: git status -s shouldn't print anything.

Then checkout the relevant branch, and run this command on a Unix systems (or within Git Bash on Windows), without the leading $:

$ git filter-branch -f --commit-filter '
    GIT_COMMITTER_NAME="$GIT_AUTHOR_NAME"
    GIT_COMMITTER_EMAIL="$GIT_AUTHOR_EMAIL"
    GIT_COMMITTER_DATE="$GIT_AUTHOR_DATE"
    git commit-tree "$@"' HEAD

Repeat running this command in each local branch you care about. For each branch, it will rewrite the history of the entire branch from its roots.

If you are sure that you didn't have a data loss, then run:

$ rm -rf .git/refs/original

2014-07-08

Programming tips for students

This blog post gives you advice to make the best use of your time for learning how to program and enjoying programming in your pre-college years.

General, technology-independent recommendations

The best situation is if you have an experienced programming mentor, or some friends or schoolmates who are a bit ahead of you, and you have the chance to observe what these people do, and can ask questions. If that's the case, you are probably better off observing and asking these people than to follow the advice below.

If you are an absolute beginner, read Message to the students first. It contains many links where you can start learning how to program.

If you or your school can afford buying books, see the list of recommended books. The home or school library may have outdated and moderately useful course material, it's worth getting and reading the best books instead settling with what's already available.

Learn English to the extent that you can read and understand everything related to programming, and you can ask technical questions clearly in written form. If you have several languages to start learning, always pick English as the first language. It's much more useful to improve your English skills to fluent (so you can give a presentation to an audience of 1000 people in English just as easily as in your mother tongue) than to improve your skills in any other language from basic to medium.

Learn typing quickly, and without looking at the keyboard. Z-Type is a nice way to practice.

Get a large screen (at least full HD resolution is strongly recommended) and a comfortable keyboard and mouse. Try many different keyboards and mice -- most of them are cheap. (Cheap, wired ones can be much better than expensive ones.) Pick one keyboard layout (US English or your local one) and stick to it.

Learn how to ask questions so you get the answer you need quickly. Start learning from How To Ask Questions the Smart Way.

There are many great websites which teach you programming for free, even if you have no prior experience. See a list of them in Message to the students.

To become a skilled and experienced programmer, practice, i.e. write lots of code. Start that early. A minute spent on writing code is better spent than an hour of reading a book or a web page about programming.

If you get stuck, ask a question on StackOverflow. It's free. You will get several answers in 5 minutes from experienced programmers, you can pick the best answer, or ask for clarification. To modify specific behavior of specific web pages, write JavaScript which modifies the DOM, and use Greasemonkey with Firefox to run it each time to visit the page. Google Chrome can also run Greasemonkey scripts.

If you need something, write a small program for (parts of) it. That's easy to start on Linux and shell scripts and Python.

Start using a version control system (e.g. Git, Subversion) as soon as you have written a program of at least 100 lines of code. (But definitely start after 1000 lines.) The rule of thumb is: if you (or others) worked more than 15 minutes on it in total, then add the code to version control system. Start early with using a version control system, don't procrastinate. Put every program file you write to a repository managed by a version control system. Commit often, about once per hour, but definitely at least once per day. Make backups regularly (at least once per week) of everything you write. The simplest way to do it is to copy everything to an external hard drive, and disconnect the hard drive after the copy has finished. Using online backup services and version control systems (e.g. Git, Subversion) also serves as an additional backup for some of the code you write — but also make a traditional backup.

Find good programmers around you (parents, relatives, schoolmates, friends, teachers). Ask lots of technical questions (any question you think they may be able to answer) in person. With their permission, observe them while they are working with the computer. Afterwards, ask why they did something the way they did it. Ask their opinion about technologies they are working with. Ask their favorite programming language etc., and ask why. Figure out their favorite technical topic, and ask them about it (it may take several hours to listen to the answer, but these are one of the best spent hours). If you trust them and you respect their skills, ask their advice. Ask enough questions before you decide if they are smart or not.

Participate in programming contests. You can practice for Google Code Jam online. For less competitive, and easier to solve problems, see Project Euler. topcoder also has great problems and a great community.

Arrange your windows on screen so that they don't overlap at all. Cycling through overlapping windows contribute a lot to lost productivity. Use virtual desktops. On Linux, use a tiling window manager if necessary. Edit your program in one window, and see the results in another window (e.g. web browser, command-line, PDF viewer). Make both windows visible at the same time (without overlap). Once set up, don't cycle through them, don't resize them and don't move them: just see them both at the same time, and work in either one. If necessary, create more than 2 windows (maybe 2 * 2 or 3 * 2), without overlap.

Recommended sites, products and technologies

Install Linux as (try to) use it as your main operating system. Linux is very much customizable and scriptable (all the command-line tools described in the book The Unix Programming Environment are available). Be careful, installing another operating system (such as Linux) may lead to data loss and may render your computer temporarily unusable (but an expert can fix that). So make a full backup first, or install Linux to an otherwise unused computer. If Linux is not an option, try to use a Mac instead, and install free software from MacPorts. The Mac OS X is a variant of Unix, with the tools described in the book The Unix Programming Environment available.

To get quick and high quality answers to your technical questions: StackOverflow and other StackExchange sites.

To host the source code of your open-source projects (including a version control system, a wiki, an issue tracker and a code review tool): github and Google Code project hosting. There are many other providers, so compare the features and the code ownership, publicity and copyright issues before choosing.

Free C++ IDE: Code::Blocks.

Free code editor for HTML and scripting languages (Python, PHP, Ruby, JavaScript, Perl, TCL, XML, HTML, CSS): Komodo Edit.

Use GNU Make or some other incremental build tool to make sure that the relevant parts of your program gets recompiled.

Recommended books for programming students

This blog post lists the best books I can recommend to students who want to learn how to program. Please note that programming is more about doing than reading, see Message to the students for a more general picture.

Basics not tied to a specific programming language:

  • Absolute beginners should follow the Message to the students guide first, and finish some online courses about programming.
  • Rivest et al.: Introduction to Algorithms, 3rd edition.
  • Henry S. Warren, Jr: Hacker's Delight, 2nd edition. Chapter 2 (one of the best chapters) is available for download for free.
  • Donald E. Knuth: The Art of Computer Programming, Volume 1, Volume 2, Volume 3.
  • Brian W. Kernighan and Rob Pike: The Unix Programming Environment, 1984.
  • Steve McConnell: Code Complete, 2nd edition.

Basics for some important programming languages and technologies::

Gems specific to programming languages and technologies beyond the basics:

  • C++: Scott Meyers: Effective C++, 3rd edition.
  • Java: Joshua Bloch: Effective Java, 2nd edition.
  • Java: Joshua Bloch and Neal Gafter: Java Puzzlers, 2005.

2014-06-20

Message to the students

Dear Student,

This is your life. Make it happy, productive and full for yourself! The smarter and more skilled you are, the more choices and flexibility you have (what to work on, who to work with, where to work and live, when to switch jobs). Follow your curiosity! If you are particularly interested in a topic, use as much as possible of your free time to study, to practice and to do it. 10000 hours is enough to become a world-class expert or champion. Start now! Find teachers, researchers (on the university), craftsmen, and other people doing or learning the same thing (your friends, or any related group on meetup.com), and cooperate with them. Find the best books about the topic online, and read them. You have to do the research to find the people and books which can help you. It's your life and for your happiness, so do it now, and continue doing it! Listen to recommendations and suggestions, use them to figure out what you like, and then in most of your free time focus your attention on topics which fascinate you.

If you are too busy reading through the rest, then try these web resources for learning programming:

If you are unsure if programming or computer science is for you, ask a programmer, or read on for figuring out! If you are interested, but if you are not sure if your friends would think it's cool, then ask yourself: whose life is it, and what would matter for you 10 years from now. If you are sure that programming is not your cup of tea, then take a look at Coursera, where you can learn more than 600 subjects online. (All the websites recommended here are free to use, all you need is a desktop or laptop computer with internet access.) It's like a class (it takes several weeks, you have to learn for a few hours each week). Teachers from a few of the best universities have uploaded the material in Coursera, and they will also check your homework. You can browse through the list of courses, or you can search for your favorite topics. (There are even some courses about programming.) Unfortunately, not all courses can be started immediately, for some of them you have to wait a few months (just add them to your watchlist). If there is too much choice for you and you don't know which one to pick, then start with A Brief History of Humankind (no homework, you just have to watch the videos, the German version of the book is available). You may even want to buy the book by the same author.

To start with programming, play Lightbot first (it takes a few hours). There is also an iPhone and and Android app. Much of programming consists of sitting in front of a computer and typing the program. Learn touch typing (i.e. typing quickly without looking at the keyboard). Z-Type is a nice game in which you can practice typing English. Decide on a keyboard layout, and learn where the special symbols are (e.g. # and {). If typing is still slow and frustrating for you, don't give up: after a few months of practice, your fingers learn where the keys are. In the meantime, you can use Scratch to write some spectacular programs (even simple games) using mostly the mouse, with very little typing. Scratch can do 2D (2 dimensional) graphics only. Blocky is an alternative of Scratch. Try it if Scratch doesn't work well on your computer or it looks too complicated. If you are interested in 3D, use AgentCubes. Unfortunately it's not as user friendly as Scratch, it's more clunky, but it's still enjoyable.

Programming is a creative activity, mostly at the computer. The immediate output is the program code you type, and the final output is the program which runs, and makes people's life easier or more fun. (It's OK if it's fun only for you in the beginning.) The other aspect of it is computer science, which is done mostly at the whiteboard and reading books, mostly thinking about how a computation can be done can be done as quickly as possible for large inputs. (A typical computation: you have to visit 30 cities in a week (and do some activity in each of them), you know the distances between each 2 cities, and you want to make your trip as short as possible. In real-life problems there can be thousands of cities.) This is very similar to the non-geometry parts of math, so if you enjoy solving math puzzles, than probably you would also enjoy learning and doing computer science. You can start with the Principles of Computing lecture on Coursera, and then try the computer science section of Khan Academy. The best classic books in the topic are The Art of Computer Programming (start with the first 3 volumes) and Introduction to Algorithms. If you open these books, you'll see lots of math formulas and lots of graphs (with nodes, edges and labels) in them. That's normal, these are the everyday tools of a computer scientist.

So, back to programming. If there is nobody around to teach you, or you'd like to move at your own pace, start on Khan Academy, by clicking on the Learn Programming link. You don't need a teacher sitting or standing next to you, just follow the instructions on the website. Like there are many languages to tell other people what you want, there are many programming languages to instruct the computer. Khan Academy teaches you JavaScript, one of the most popular languages today. Another similar one is Crunchzilla, which also teaches you JavaScript in a visual way, step-by-step. Eventually, over the years, you should learn many programming languages, such as Python, Java, C, C++, Ruby. (This is the list  of best programming languages to learn changes quickly, maybe in 5 years from now it would be different.). If you want to build web pages, you should learn HTML and CSS, which are languages to describe text formatting and visual layouts of web pages. In addition to JavaScript, you can learn Python, Ruby, HTML, CSS and some other languages at Codecademy. You don't have to register or log in: just scroll to the bottom, select the language you want to learn (e.g. HTML/CSS), and then just follow the instructions, it will teach you step-by-step. There are also programming courses in Coursera, for example one of them teaches you to build your own game in Python. Unfortunately you have to wait several months for that to start. In the meantime, you can also learn game programming in JavaScript at CodeAvengers. If you are interested in building a mobile app for Android phones (no iPhone), then do a few of the tutorials at App Inventor.

If you like nice, eye-candy design with music, then Code Combat will teach you JavaScript in a fantasy (medieval) atmosphere: you have to rescue kidnapped town members from prisons guided by trolls etc. A similar website is Ruby Warrior, you can practice the Ruby language there, but it's more enjoyable if you have some prior programming experience, so don't start there. Both Code Combat and Ruby Warrior are quite resource-hungry, so you need a very modern and fast computer to play smoothly, and you have to close most other programs.

HTML (for text and structure), CSS (for visual layout) and JavaScript (for interactive elements such as animation and reaction to mouse clicks) are the 3 most important languages today to build websites: the code written in those languages are executed (interpreted) by the web browsers, and that code will determine how the web page will look and sound like and how it will behave. (There are many other programming languages for the server side, i.e. to make the website remember your data when you visit it from a different computer or browser.) As mentioned above, learn these 3 languages from Codecademy. You can also practice your CSS skills in a playful way on Flukeout (but you have to learn it first somewhere else). If you want to build a website, save it and show it off to your friends, Thimble is a nice and easy-to-use tool for that. It supports HTML, CSS and JavaScript. You have to register and log in first in order to be able to save your creation.

When real programmers work and write code, they usually work in a text-editor or an IDE (integrated development environment), and not in a web browser. To make it easy to start for you, most of the learning material mentioned above needs only a web browser with internet access. After you have finished one or two programming classes above, you should give it a try with the real text editor. There are step-by-step instructions for that in Python in the Programming with Python (do this first) and Data Processing with Python courses. Just follow the instructions, it tells you what to install and how to use it.

Once you get good at programming (i.e. you've finished many programming courses, and when you start the next one, you find it too easy), and enjoy it a lot, you should try your skills (and possibly win some prizes) in one of the programming contests. For example, there is Google Code Jam, you can start practicing any time with any Round 1 (or Round 1A). It works best if 3 or more of you work together, trying to solve one of the problems together, and then you go on separately for the 2nd problem, and at the end if anyone has a correct solution, they show the others how they did it. You can also ask your teacher if there are other programmings contest closeby where you live, and if there are some preparation classes you can attend. As soon as you know the basics of programming, the most you can learn from is solving contest problems and understanding other people's analyses and solutions. Project Euler is similarly useful, but it contains more math-oriented and theoretical problems. After solving the first few easy problems, you'll need your best math, programming and computer science skills to solve the rest.

Recommended reading before and during university for computer science students: What every computer science major should know.

Good luck and have fun!

What's the difference between StaticPython and PyRun?

This blog post explains the difference between StaticPython and PyRun.

Both StaticPython and PyRun are free, portable binary distributions of Python 2.x and 3.x, for Linux, Mac OS X (and PyRun also works on FreeBSD without Linux emulation). That is, a user without root access can quickly download, extract and run either StaticPython or PyRun, and it won't conflict with the (possibly old) Python versions installed to the system (by root). Windows users should use Portable Python instead.

An important difference is that StaticPython doesn't need any external files to run on Linux, while PyRun needs lots of system libraries (libssl.so.1.0.0, libcrypto.so.1.0.0, libz.so.1, libsqlite3.so.0, libz2.so.1, libpthread.so.0, libdl.so.2, libutil.so.1, libm.so.6, libc.so.6), and will not work on systems which don't have all of the required libraries installed (with the required version), so PyRun is much less portable.

Another important difference is that with PyRun you can compile and install C extensions, and with StaticPython you can't (even ctypes doesn't work with StaticPython). However, many extensions are precompiled: Stackless + greenlet + libssl + Tokyo Cabinet + libevent2 + Concurrence + AES + Syncless + MessagePack + Gevent MySQL + PyCrypto.

Another important difference is that PyRun integrates nicely with packaging (setuptools, pip etc.), and is a nice, self-contained replacement for virtualenv. StaticPython doesn't help you with packaging, you have to do Python library installation and distribution manually.

There are many small differences, e.g. PyRun is available for both 32-bit and 64-bit, ans StaticPython is 32-bit only. PyRun needs at least 14 megabytes of disk space (10 megabytes for the binary executable and about 4 megabytes for the mandatory system library dependencies), and StaticPython needs between 6 and 9 megabytes depending on which feature set you need.

My recommendation: If PyRun works on your system (because you have the right version of system libraries installed, and you have enough free disk space), then use PyRun, otherwise use StaticPython.

Caveat: I am the author of StaticPython.

2014-04-26

How to parse an integer in C++ (and C) with overflow detection

This blog post explains how to write C++ code which parses integers, in a type-safe way for any integral type, paying attention to overflows and underflow. The code with small modifications can be used in C as well, C++ language features are only used to allow arbitrary integral types.

It sounds like we could use a standard library function. But apparently there isn't any that would work:

  • Please note that sscanf(3) etc. don't do overflow detection, so we can't use that.
  • Please note that atoi(3) etc. can't indicate a parse error, so we can't use that.
  • Please note that strtol(3) etc. doesn't exist so it can't do overflow detection for anything smaller than a long, so we can't use that.
  • Please note that sscanf, atoi and strtol support NUL-terminated strings only, they can't parse a string (and report the expected parse error) which contains an '\0'.

So let's implement our own parser. Someone might expect that this is a trivial and boring task, but it will turn out that there are many pitfalls, and many tricky ideas to avoid all of them. Let's see.

The first attempt:

template<class T>bool parse_dec(char const *p, T *out) {
  T n = 0;
  while (*p + 0U - '0' <= 9U) {  // A digit.
    n = 10 * n + *p++ - '0';
  }
  *out = n;
  return true;  // Success.
}

There is only 1 trick in the implementation: how to detect whether *p is a digit (i.e. between '0' and '9'. For characters with too large ASCII code, the result of *p + 0U - '0' would be larger than 9, so the condition is false. For characters with too small ASCII code, the result is negative, but because of 0U it would be interpreted as unsigned, so it would be larger than 9U, so the condition is false. We don't use the standard library function isdigit(3), because on some systems it returns true for bytes other than '0' ... '9' (see the link above).

Problems:

  1. It doesn't check that the end of the string is reached at the end of the number.
  2. It parses the empty string as 0.
  3. It doesn't support negative numbers.
  4. It doesn't check for overflow or underflow.
It's easy to fix problems 1 and 2 by restructuring the loop and checking for '\0':
template<class T>bool parse_dec(char const *p, T *out) {
  T n = 0;
  do {
    if (*p + 0U - '0' > 9U) return false;  // Not a digit.
    n = 10 * n + *p++ - '0';
  } while (*p != '\0');
  *out = n;
  return true;  // Success.
}
To fix problem 3 (negative numbers), we need a way to detect whether the type T is signed, and then parse a leading -:
template<class T>bool parse_dec(char const *p, T *out) {
  const bool is_signed = (T)~(T)0 < (T)0;
  bool is_negative = false;
  if (is_signed && *p == '-') {
    is_negative = true;
    ++p;
  }
  T n = 0;
  do {
    if (*p + 0U - '0' > 9U) return false;  // Not a digit.
    n = 10 * n + *p++ - '0';
  } while (*p != '\0');
  *out = is_negative ? -n : n;
  return true;  // Success.
}

To understand the initialization of is_signed above, consider that in C and C++, the expression ~0 generates an int with all bits 1, thus it's -1, thus it's negative. The expression (unsigned)~0 is positive, it's the largest value for unsigned int. So by checking the sign of (T)~(T)0 we can determine whether T is a signed or unsigned integral type. The double cast is necessary to make it work even if sizeof(T) is smaller or larger than sizeof(int).

Please note that the ~ operator works for integral types, but it doesn't compile for pointer or floating point types etc. So if parse_dec is used with a wrong T, then a compile error would be reported at template instantiation time. To convert it to a template substitution failure, type_traits and enable_if can be used.

To fix problem 4 (overflow detection), we can add an if just before we assign the larger value to n. But how can we check for an overflow without triggering the overflow (and already losing some high bits from the result)? We can work like this: if we are parsing a positive, 8-bit signed int, then the maximum value is 127, so there is no overflow if the previous n is less than 12, or the previous n is 12, and the new digit is at most 7. That's exactly how the code below checks for overflow. It also calculates the upper limit of n (e.g. 12) and the new digit (e.g. 7) based on properties of T: whether it is signed, its size, and whether there was a - in the input.

template<class T>bool parse_dec(char const *p, T *out) {
  // ~(T)~(T)0 compiles for integral types, but it doesn't compile for pointer
  // or floating point types etc.
  const bool is_signed = (T)~(T)0 < (T)1;
  const T nmax = (is_signed ? (T)~((T)1 << (sizeof(T)*8-1)) : (T)~(T)0) / 10;
  bool is_negative = false;
  if (is_signed && *p == '-') {
    is_negative = true;
    ++p;
  }
  const char cmax = is_signed ? (is_negative ? 8 : 7) : 5;
  T n = 0;
  do {
    if (*p + 0U - '0' > 9U) return false;  // Not a digit.
    const char c = *p++ - '0';
    const T nneg = -n;
    if (nneg > nmax || (nneg == nmax && c > cmax)) return false;  // Overflow.
    n = 10 * n - c;
  } while (*p != '\0');
  *out = is_negative ? n : -n;
  return true;  // Success.
}

It's interesting to note that the last allowed digit (cmax) doesn't depend on sizeof(T), because the sequence containing of the last digit of powers of 2 is periodic with a period divisible by 8.

Please note that the upper limit signed integers is not symmetric to 0. For example, for uint8_t, the smallest allowed value is -128, and the largest one is 127. This difference is reflected in the initialization of cmax: 7 or 8.

Please note that we're updating n with the opposite sign, and we flip the sign only at the end. This is necessary to avoid signed integer overflow when parsing the smallest possible integer (e.g. -128 for 8-bit integers). Without the sign flip we'd temporarily have 128 in n, which is an overflow.

Please note that in each comparison in the code above we cast both sides explicitly to the same type. (In the 9U comparison both sides are of type unsigned int.) This is to make the code easy to understand even if the reader is not familiar with the integer automatic conversion and sign extension rules in C and C++.

Please note that in C and C++ the result is undefined if there is a signed integer overflow in the arithmetic operations. That's OK for us, because we make sure that our arithmetic operations (10 * n + c and the boring ones) happen to never overflow: either we explicitly check for overflow before, or the input contains only small numbers.

The example code above can be changed easily if the input is not a NUL-terminated string, but any array of characters with a known size, or a FILE* (using getc), or an std::istream (using get). This is left as an exercise to the reader.

Similar code can be written for parsing hex and octal, and combining them to autodetect the base based on the prefix (i.e. 0x or 0X for decimal, and 0 for octal.

For completeness, here is what kind of numbers our last parser accepts: those non-overflowing integers which fully match the regexp -[0-9]+ for signed T, and [0-9]+ for unsigned T. So leading whitespace is not allowed, trailing junk is not allowed, multiple leading 0s are allowed, a leading + is not allowed, and a leading - is allowed iff T is signed.

See the full code with some usage examples on Github.

2014-04-10

Announcing ssweb: single-shot webserver in Python

This blog post announces ssweb, a single-shot HTTP server library in Python 2.x. Single-shot means is that the webserver accepts only a single incoming HTTP connection, handles it, and then exits immediately.

Such a server can be used as a redirect target in the web-based OAuth authentication protocol, to receive the freshly generated OAuth token. In this case the program is a command-line tool running a HTTP server for a short amount of time, to make the passwordsless login more convenient for the user, without having to manually copy-paste token. If it doesn't sound useful, then it's most probably not useful for you right now.

Example usage:

$ wget -O ssweb.py http://raw.githubusercontent.com/pts/ssweb/master/ssweb.py
$ python ssweb.py
URL: http://127.0.0.1:40464/foo
{'res_body': 'Shot.', 'req_head': 'GET /foo HTTP/1.0\r\nHost: 127.0.0.1:40464\r\nUser-Agent: Python-urllib/1.17\r\n\r\n', 'client_addr': ('127.0.0.1', 40026), 'res_head': 'HTTP/1.0 200 OK\r\nContent-Type: text/plain\r\nContent-Length: 5\r\n\r\n', 'req_body': ''}
'Shot.'
$ python ssweb.py x
Please visit URL: http://127.0.0.1:59872/foo
... (after visiting the URL in Firefox)
{'res_body': 'Shot.', 'req_head': 'GET /foo HTTP/1.1\r\nHost: 127.0.0.1:59872\r\nUser-Agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:28.0) Gecko/20100101 Firefox/28.0\r\nAccept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8\r\nAccept-Language: en-US,en;q=0.5\r\nAccept-Encoding: gzip, deflate\r\nConnection: keep-alive\r\n\r\n', 'client_addr': ('127.0.0.1', 50702), 'res_head': 'HTTP/1.0 200 OK\r\nContent-Type: text/plain\r\nContent-Length: 5\r\n\r\n', 'req_body': ''}

2014-04-04

How to convert all YouTube links from http:// to https:// in Firefox history

This blog post explains how to convert the protocol from http:// to https:// in YouTube URLs in the browsing history of a Mozilla Firefox profile. YouTube has recently started redirecting logged-in users from http:// to https:// . This conversion is useful in the following situation:

  • The user uses his Firefox browsing history to track which YouTube videos he has already seen.
  • The user disables web site colors (e.g. using the PrefBar Firefox extension) so by looking at the color of a YouTube video link he can immediately see if he has visited that video page or not.
  • The user uses some Greasemonkey scripts to normalize YouTube video links on web pages (e.g. to remove &feature=related, so the normalized URLs will be added to the Firefox browsing history.
  • Bonus: The user uses the LinkVisitor Firefox extension to mass-toggle the visited status of URLs without actually visiting them in Firefox.

To do the protocol conversion from http:// to https:// , close Firefox and run this on Linux (without the leading $ sign):

$ sqlite3 ~/.mozilla/firefox/*.default/places.sqlite '
    UPDATE OR IGNORE moz_places   SET url="https" || SUBSTR(url, 5) WHERE url LIKE "http://youtube.com/%" OR url LIKE "http://www.youtube.com/%";
    UPDATE OR IGNORE moz_favicons SET url="https" || SUBSTR(url, 5) WHERE url LIKE "http://youtube.com/%" OR url LIKE "http://www.youtube.com/%";
    ANALYZE;
    VACUUM;
'

The ANALYZE and VACUUM parts are optional, they just speed up Firefox accessing these tables in the future.

The SQLite UPDATE queries above can be run on the relevant places.sqlite file on Mac OS X or Windows as well. (This blog post doesn't provide explicit instructions how to run those queries. Use Google web search or ask on Stack Overflow to figure out how.)

2014-01-19

How to run custom code before and after main in GCC?

This blog post explains how to register C or C++ code to be run at process startup (i.e. just before *main*) and process exit (e.g. when *main* returns or when *exit*(...) is called). Code to be run at loading and unloading of shared libraries and Linux kernel modules are not covered in this post.

The behavior described in this post has been tested with gcc-4.1 ... gcc-4.8 and clang-3.0 ... clang-3.4. Older versions of GCC and Clang may behave differently.

The behavior described in this post has been tested with (e)glibc-2.7 ... (e)glibc-2.15 and uClibc-0.9.30.1 ... uClibc-0.9.33). Earlier versions and other libc implementations may behave differently. For example, dietlibc-0.33 doesn't execute any of the registered code (so the example below prints just MAIN; MYATEX2; MYATEX1).

The new way (available since gcc-2.7) is declaring a function with attribute((constructor)) (this will make it run at process startup) and declaring a function with attribute((destructor)) (this will make it run at process exit). The double underscores around __attribute__ are there to prevent GCC warnings when compiling standard C (or C++) code. Example:

#include <unistd.h>

__attribute__((constructor)) static void myctor(void) {
  (void)!write(2, "HI\n", 3);
}

__attribute__((destructor)) static void mydtor(void) {
  (void)!write(2, "BYE\n", 4);
}

Upon specifying one of these attributes, GCC (or Clang) appends the function pointer to the sections .init_array (or sometimes .ctors) or .fini_array (or sometimes .dtors), respectively. (You can take a look at objdump -x prog to see if these sections are present.) The libc initialization and exit code will run all functions in these sections. There is a well-defined order (see below) in which these registered functions get run, but the order is within the same translation unit (C or C++ source file) only. It's undefined in which order the translation units are processed.

Please note that the process exit functions are not always called: for example, if the process receives a signal which terminates it (e.g. either from another process or from itself, or from itself, by calling abort()), or if the process calls _exit(...) (with an underscore), then none of the process exit functions are called.

Please note that it's possible to register more process exit functions at runtime, by calling atexit(3) or on_exit(3).

C++ static initialization is equivalent to attribute((constructor)):

#include <unistd.h>
#include <string>

static int get_answer() {
  (void)!write(1, "GA\n", 3);
  return 42;
}
 
/* The call to get_answer works in C++, but it doesn't work in C, because
 * the value of myanswer1 is not a compile-time constant.
 */
int myanswer = get_answer();
std::string hello("World");  /* Registers both a constructor and destructor. */

There is an older alternative for registering process startup and exit functions: by adding code to the body of the _init function in the .init section and to the body of _fini function in the .fini section. The headers of these functions are defined in crti.o and the footers are defined in crtn.o (both of which are part of the libc, use e.g. objdump -d .../crti.o to disassemble them). GCC itself uses this registration mechanism in crtbegin.o to register __do_global_dtors_aux and in crtend.o to register __do_global_ctors_aux.

It is possible to use this older registration alternative in your C or C++ code, but it's a bit inconvenient. Here are some helper macros which make it easy:

/* Usage: DEFINE_INIT(my_init1) { ... }
 * Defines function my_init1 which will be called at startup, before main().
 * As a side effect, defines `static void name() { ... }'.
 */
#define DEFINE_INIT(name) \
    static void name(void); \
    /* If we declared this static, it wouldn't get called. */ \
    __attribute__((section(".trash"))) void __INIT_HELPER__##name(void) { \
      static void (* volatile f)(void) = name; \
      __asm__ __volatile__ (".section .init"); \
      f(); \
      __asm__ __volatile__ (".section .trash"); \
    } \
    static void name(void)

/* Usage: DEFINE_FINI(my_fini1) { ... }
 * Defines function my_fini1 which will be called at process exit.
 * As a side effect, defines `static void name() { ... }'.
 */
#define DEFINE_FINI(name) \
    static void name(void); \
    /* If we declared this static, it wouldn't get called. */ \
    __attribute__((section(".trash"))) void __FINI_HELPER__##name(void) { \
      static void (* volatile f)(void) = name; \
      __asm__ __volatile__ (".section .fini"); \
      f(); \
      __asm__ __volatile__ (".section .trash"); \
    } \
    static void name(void)

For your reference, here are the corresponding much simpler macros for attribute((constructor)) and attribute((destructor)):

/* Usage: DEFINE_CONSTRUCTOR(my_init1) { ... }
 * Defines function my_init1 which will be called at startup, before main().
 * As a side effect, defines `static void name() { ... }'.
 */
#define DEFINE_CONSTRUCTOR(name) \
    __attribute__((constructor)) static void name(void)

/* Usage: DEFINE_DESTRUCTOR(my_init1) { ... }
 * Defines function my_fini1 which will be called at process exit.
 * As a side effect, defines `static void name() { ... }'.
 */
#define DEFINE_DESTRUCTOR(name) \
    __attribute__((destructor)) static void name(void)

It is possible to use the old and the new registration mechanisms at the same time. Here is a sample code which uses both, and C++ static initialization and atexit and on_exit as well.

#include <string.h>
#include <unistd.h>
#include <stdlib.h>

#ifdef __cplusplus
class C {
 public:
  C(const char *msg): msg_(msg) {
    (void)!write(1, "+", 1);  (void)!write(1, msg_, strlen(msg_));
  }
  ~C() {
    (void)!write(1, "-", 1);  (void)!write(1, msg_, strlen(msg_));
  }
 private:
  const char *msg_;
};
#endif

DEFINE_INIT(myinit1) { (void)!write(1, "MYINIT1\n", 8); }
DEFINE_CONSTRUCTOR(myctor1) { (void)!write(1, "MYCTOR1\n", 8); }

#ifdef __cplusplus
static int get_answer(const char *msg) {
  (void)!write(1, msg, strlen(msg));
  return 42;
}
C myobj1("MYOBJ1\n");
int myanswer1 = get_answer("ANSWER1\n");
C myobj2("MYOBJ2\n");
int myanswer2 = get_answer("ANSWER2\n");
#endif

DEFINE_INIT(myinit2) { (void)!write(1, "MYINIT2\n", 8); }
DEFINE_CONSTRUCTOR(myctor2) { (void)!write(1, "MYCTOR2\n", 8); }
DEFINE_FINI(myfini1) { (void)!write(1, "MYFINI1\n", 8); }
DEFINE_DESTRUCTOR(mydtor1) { (void)!write(1, "MYDTOR1\n", 8); }
DEFINE_FINI(myfini2) { (void)!write(1, "MYFINI2\n", 8); }
DEFINE_DESTRUCTOR(mydtor2) { (void)!write(1, "MYDTOR2\n", 8); }
static void myatex1() { (void)!write(1, "MYATEX1\n", 8); }
static void myatex2() { (void)!write(1, "MYATEX2\n", 8); }
static void myonexit(int exitcode, void *arg) {
  const char *msg = (const char*)arg;
  (void)exitcode;
  (void)!write(1, msg, strlen(msg));
}

int main(int argc, char **argv) {
  (void)argc; (void)argv;
  atexit(myatex1);
  on_exit(myonexit, (void*)"MYONEX1\n");
  (void)!write(1, "MAIN\n", 5);
  atexit(myatex2);
  on_exit(myonexit, (void*)"MYONEX2\n");
  return 0;
}

It is not intuitive in which order these are run. Here is the output:

MYINIT1
MYINIT2
+MYOBJ1
ANSWER1
+MYOBJ2
ANSWER2
MYCTOR2
MYCTOR1
MAIN
MYONEX2
MYATEX2
MYONEX1
MYATEX1
-MYOBJ2
-MYOBJ1
MYDTOR1
MYDTOR2
MYFINI1
MYFINI2

Please note that gcc-4.3 and below run MYDTOR1 and MYDTOR2 in the opposite order. All other compilers tested (see above which) use exactly this order. The order is libc-independent, because newer compiler versions with the same libc resulted in different order, while other libc versions with the same compiler version kept the order intact. Please note again that the order of .ctors, .dtors and others is undefined across translation units (C or C++ source files).