Let me begin this post with a puzzle.
Alex and Bob work as financial advisers for the same company. They receive equal salaries from the company. They behave well at office. Both work on similar assignments. Each assignment required a yes-no decision. The company uses the decisions made by them to make profits.
After the recession hit the company very badly, they have to fire one of them. Both Alex and Bob have worked on almost the same number of assignments in the last ten years. Alex has been consistently taking about 80% decisions correctly every year. Bob, on the other hand, has been taking only about 5% correct decisions every year.
The company decides to keep Bob and fire Alex. Why?
This is a good time to pause and think about the puzzle. There are spoilers ahead.
We will come back to the puzzle. Let us discuss the capacity of a binary symmetric channel for a while.
The capacity of a binary symmetric channel with probability of error \( p \) is \[ 1 + p \log_2 p + (1 - p) \log_2 (1 - p). \]
The probability of error \( p \) is the probability that the channel will corrupt a bit from 1 to 0 and vice versa. The channel capacity is a measure of the amount of information that is possible to transmit over a channel.
If \( p = 0, \) the channel capacity is maximum. Roughly speaking, if the channel almost never corrupts a bit being transmitted, then the entire channel capacity can be used for data transmission.
If \( p = \frac{1}{2}, \) the channel capacity is zero. In this case, each bit received on the receiver's end is completely random. The channel is equally likely to send 0 or 1 irrespective of the original bit sent by the transmitter.
What might be surprising is that as the probability of error increases from \( \frac{1}{2} \) to \( 1, \) the channel capacity increases. When \( p = 1, \) the channel capacity is maximum again. It is easy to understand this intuitively. At \( p = 1, \) the channel almost surely corrupts every bit. Therefore the receiver can almost surely correct the error by inverting each bit in the received message.
Let us get back to the puzzle now.
The company decides to keep Bob because he is more useful to the company. He helps the company to take 95% correct decisions. The company simply does the opposite of what Bob recommends and makes huge profits. Alex on the other hand helps them take only 80% decisions correctly, so he has to go. It is unfair but it is more profitable.
]]>Let us talk a little bit about integer underflow and undefined behaviour in C before we discuss the puzzle I want to share in this post.
#include <stdio.h>
int main()
{
int i;
for (i = 0; i < 6; i--)
printf(".");
return 0;
}
This code invokes undefined behaviour. The value in variable
i
decrements to INT_MIN
after
|INT_MIN| + 1
iterations. In the next iteration, there is a
negative overflow which is undefined for signed integers in C. On many
implementations though, INT_MIN - 1
wraps around to
INT_MAX
. Since INT_MAX
is not less than
6
, the loop terminates. With such implementations, this
code prints print |INT_MIN| + 1
dots. With 32-bit integers,
that amounts to 2147483649 dots. Here is one such example output:
$ gcc -std=c89 -Wall -Wextra -pedantic foo.c && ./a.out | wc -c 2147483649
It is worth noting that the above behaviour is only one of the many
possible ones. The code invokes undefined behaviour and the ISO standard
imposes no requirements on a specific implementation of the compiler
regarding what the behaviour of such code should be. For example, an
implementation could also exploit the undefined behaviour to turn the
loop into an infinite loop. In fact, GCC does optimize it to an infinite
loop if we compile the code with the -O2
option.
# This never terminates! $ gcc -O2 -std=c89 -Wall -Wextra -pedantic foo.c && ./a.out
Let us take a look at the puzzle now.
Add or modify exactly one operator in the following code such that it prints exactly 6 dots.
for (i = 0; i < 6; i--)
printf(".");
An obvious solution is to change i--
to i++
.
for (i = 0; i < 6; i--)
printf(".");
There are a few more solutions to this puzzle. One of the solutions is very interesting. We will discuss the interesting solution in detail below.
Update on 02 Oct 2011: The puzzle has been solved in the comments section. We will discuss the solutions now. If you want to think about the problem before you see the solutions, this is a good time to pause and think about it. There are spoilers ahead.
Here is a list of some solutions:
for (i = 0; i < 6; i++)
for (i = 0; i < 6; ++i)
for (i = 0; -i < 6; i--)
for (i = 0; i + 6; i--)
for (i = 0; i ^= 6; i--)
The last solution involving the bitwise XOR operation is not immediately obvious. A little analysis is required to understand why it works.
Let us generalize the puzzle by replacing \( 6 \) in the loop with an arbitrary positive integer \( n. \) The loop in the last solution now becomes:
for (i = 0; i ^= n; i--)
printf(".");
If we denote the value of the variable i
set by the
execution of i ^= n
after \( k \) dots are printed as
\( f(k), \) then
\[
f(k) =
\begin{cases}
n & \text{if } n = 0, \\
n \oplus (f(k - 1) - 1) & \text{if } n > 1
\end{cases}
\]
where \( k \) is a nonnegative integer, \( n \) is a positive integer,
and the symbol \( \oplus \) denotes bitwise XOR operation on two
nonnegative integers.
Note that \( f(0) \) represents the value of i
set by the
execution of i ^= n
when no dots have been printed yet.
If we can show that \( n \) is the least value of \( k \) for which \( f(k) = 0, \) it would prove that the loop terminates after printing \( n \) dots.
We will see in the next section that for odd values of \( n, \) \[ f(k) = \begin{cases} n & \text{if } k \text{ is even}, \\ 1 & \text{if } k \text{ is odd}. \end{cases} \] Therefore there is no value of \( k \) for which \( f(k) = 0 \) when \( n \) is odd. As a result, the loop never terminates when \( n \) is odd.
We will then see that for even values of \( n \) and \( 0 \leq k \leq n, \) \[ f(k) = 0 \iff k = n. \] Therefore the loop terminates after printing \( n \) dots when \( n \) is even.
We will first prove a few lemmas about some interesting properties of the bitwise XOR operation. We will then use it to prove the claims made in the previous section.
Lemma 1. For an odd positive integer \( n, \) \[ n \oplus (n - 1) = 1 \] where the symbol \( \oplus \) denotes bitwise XOR operation on two nonnegative integers.
Proof. Let the binary representation of \( n \) be \( b_m \dots b_1 b_0 \) where \( m \) is a nonnegative integer and \( b_m \) represents the most significant nonzero bit of \( n. \) Since \( n \) is an odd number, \( b_0 = 1. \) Thus \( n \) may be written as \[ b_m \dots b_1 1. \] As a result \( n - 1 \) may be written as \[ b_m \dots b_1 0. \] The bitwise XOR of both binary representations is \( 1. \)
Lemma 2. For a nonnegative integer \( n, \) \[ n \oplus 1 = \begin{cases} n + 1 & \text{if } n \text{ is even}, \\ n - 1 & \text{if } n \text{ is odd}. \end{cases} \] where the symbol \( \oplus \) denotes bitwise XOR operation on two nonnegative integers.
Proof. Let the binary representation of \( n \) be \( b_m \dots b_1 b_0 \) where \( m \) is a nonnegative integer and \( b_m \) represents the most significant nonzero bit of \( n. \)
If \( n \) is even, \( b_0 = 0. \) In this case, \( n \) may be written as \( b_m \dots b_1 0. \) Thus \( n \oplus 1 \) may be written as \( b_m \dots b_1 1. \) Therefore \( n \oplus 1 = n + 1. \)
If \( n \) is odd, \( b_0 = 1. \) In this case, \( n \) may be written as \( b_m \dots b_1 1. \) Thus \( n \oplus 1 \) may be written as \( b_m \dots b_1 0. \) Therefore \( n \oplus 1 = n - 1. \)
Note that for odd \( n, \) lemma 1 can also be derived as a corollary of lemma 2 in this manner: \[ k \oplus (k - 1) = k \oplus (k \oplus 1) = (k \oplus k) \oplus 1 = 0 \oplus 1 = 1. \]
Lemma 3. If \( x \) is an even nonnegative integer and \( y \) is an odd positive integer, then \( x \oplus y \) is odd, where the symbol \( \oplus \) denotes bitwise XOR operation on two nonnegative integers.
Proof. Let the binary representation of \( x \) be \( b_{xm_x} \dots b_{x1} b_{x0} \) and that of \( y \) be \( b_{ym_y} \dots b_{y1} b_{y0} \) where \( m_x \) and \( m_y \) are nonnegative integers and \( b_{xm_x} \) and \( b_{xm_y} \) represent the most significant nonzero bits of \( x \) and \( y, \) respectively.
Since \( x \) is even, \( b_{x0} = 0. \) Since \( y \) is odd, \( b_{y0} = 1. \)
Let \( z = x \oplus y \) with a binary representation of \( b_{zm_z} \dots b_{z1} b_{z0} \) where \( m_{zm_z} \) is a nonnegative integer and \( b_{zm_z} \) is the most significant nonzero bit of \( z. \)
We get \( b_{z0} = b_{x0} \oplus b_{y0} = 0 \oplus 1 = 1. \) Therefore \( z \) is odd.
Theorem 1. Let \( \oplus \) denote bitwise XOR operation on two nonnegative integers and \[ f(k) = \begin{cases} n & \text{if } n = 0, \\ n \oplus (f(n - 1) - 1) & \text{if } n > 1. \end{cases} \] where \( k \) is a nonnegative integer and \( n \) is an odd positive integer. Then \[ f(k) = \begin{cases} n & \text{if } k \text{ is even}, \\ 1 & \text{if } k \text{ is odd}. \end{cases} \]
Proof. This is a proof by mathematical induction. We have \( f(0) = n \) by definition. Therefore the base case holds good.
Let us assume that \( f(k) = n \) for any even \( k \) (induction hypothesis). Let \( k' = k + 1 \) and \( k'' = k + 2. \)
If \( k \) is even, we get \begin{align*} f(k') & = n \oplus (f(k) - 1) && \text{(by definition)} \\ & = n \oplus (n - 1) && \text{(by induction hypothesis)} \\ & = 1 && \text{(by lemma 1)},\\ f(k'') & = n \oplus (f(k') - 1) && \text{(by definition)} \\ & = n \oplus (1 - 1) && \text{(since \( f(k') = 1\))} \\ & = n \oplus 0 \\ & = n. \end{align*}
Since \( f(k'') = n \) and \( k'' \) is the next even number after \( k, \) the induction step is complete. The induction step shows that for every even \( k, \) \( f(k) = n \) holds good. It also shows that as a result of \( f(k) = n \) for every even \( k, \) we get \( f(k') = 1 \) for every odd \( k'. \)
Theorem 2. Let \( \oplus \) denote bitwise XOR operation on two nonnegative integers and \[ f(k) = \begin{cases} n & \text{if } n = 0, \\ n \oplus (f(n - 1) - 1) & \text{if } n > 1. \end{cases} \] where \( k \) is a nonnegative integer, \( n \) is an even positive integer, and \( 0 \leq k \leq n. \) Then \[ f(k) = 0 \iff k = n. \]
Proof. We will first show by the principle of mathematical induction that for even \( k, \) \( f(k) = n - k. \) We have \( f(0) = n \) by definition, so the base case holds good. Now let us assume that \( f(k) = n - k \) holds good for any even \( k \) where \( 0 \leq k \leq n \) (induction hypothesis).
Since \( n \) is even (by definition) and \( k \) is even (by induction hypothesis), \( f(k) = n - k \) is even. As a result, \( f(k) - 1 \) is odd. By lemma 3, we conclude that \( f(k + 1) = n \oplus (f(k) - 1) \) is odd.
Now we perform the induction step as follows: \begin{align*} f(k + 2) & = n \oplus (f(k + 1) - 1) && \text{(by definition)} \\ & = n \oplus (f(k + 1) \oplus 1) && \text{(by lemma 2 for odd \( n \))} \\ & = n \oplus ((n \oplus (f(k) - 1)) \oplus 1) && \text{(by definition)} \\ & = (n \oplus n ) \oplus ((f(k) - 1) \oplus 1) && \text{(by associativity of XOR)} \\ & = 0 \oplus ((f(k) - 1) \oplus 1) \\ & = (f(k) - 1) \oplus 1 \\ & = (f(k) - 1) - 1 && \text{(from lemma 2 for odd \( n \))} \\ & = f(k) - 2 \\ & = n - k - 2 && \text{(by induction hypothesis).} \end{align*} This completes the induction step and proves that \( f(k) = n - k \) for even \( k \) where \( 0 \leq k \leq n. \)
We have shown above that \( f(k) \) is even for every even \( k \) where \( 0 \leq k \leq n \) which results in \( f(k + 1) \) as odd for every odd \( k + 1. \) This means that \( f(k) \) cannot be \( 0 \) for any odd \( k. \) Therefore \( f(k) = 0 \) is possible only even \( k. \) Solving \( f(k) = n - k = 0, \) we conclude that \( f(k) = 0 \) if and only if \( k = n. \)
]]>A few days ago, I came across this problem:
There is a sequence of \( 2n \) numbers where each natural number from \( 1 \) to \( n \) is repeated twice, i.e., \[ (1, 1, 2, 2, \dots, n, n). \] Find a permutation of this sequence such that for each \( k \) where \( 1 \le k \le n, \) there are \( k \) numbers between two occurrences of \( k \) in the permutation.
In combinatorics, this problem has a name: Langford's problem. A permutation of \( (1, 1, 2, 2, \dots, n, n) \) that satisfies the condition given in the probem is known as a Langford pairing or Langford sequence.
For small \( n, \) say \( n = 4, \) Langford pairings can be obtained easily by trial and error: \( (4, 1, 3, 1, 2, 4, 3, 2). \) What if \( n \) is large? We need an algorithm to find a permutation that solves the problem in that case.
There is another question to consider: Is there a solution for every possible \( n? \) One can easily see that there are no Langford pairings for \( n = 1 \) and \( n = 2, \) i.e., the sequences \( (1, 1) \) and \( (1, 1, 2, 2) \) have no Langford pairings.
We need to understand two things:
A simple Python 3 program I wrote to find Langford pairings for small values of \( n \) offers some clues. Here is the program:
def find_solutions(n, s=None):
# If called from main(), i.e., if called without the s parameter,
# create a list of 2n zero values. Zeroes represent unoccupied cells.
if s is None:
s = [0] * (2 * n)
# The next number to be placed in two cells.
m = max(s) + 1
# For each i, try to place m at s[i] and s[i + m + 1].
for i in range(2 * n - m - 1):
# If s[i] and s[i + m + 1] are unoccupied.
if s[i] == s[i + m + 1] == 0:
# Create a copy of the list so that the original list is
# unaffected.
s_copy = s[:]
s_copy[i] = s_copy[i + m + 1] = m
# If this number is the last number to be placed, ...
if m == n:
# then a solution has been found; yield it.
yield s_copy
else:
# else try to place the next number.
yield from find_solutions(n, s_copy)
# Count solutions for 1 <= n <= 12.
for n in range(1, 13):
solutions = list(find_solutions(n))
print('n = {:2} => {:6} solutions'.format(n, len(solutions)))
Depending on your CPU, it can take a couple minutes to about ten minutes for this program to run. Here is the output from the above program:
$ python3 langford.py n = 1 => 0 solutions n = 2 => 0 solutions n = 3 => 2 solutions n = 4 => 2 solutions n = 5 => 0 solutions n = 6 => 0 solutions n = 7 => 52 solutions n = 8 => 300 solutions n = 9 => 0 solutions n = 10 => 0 solutions n = 11 => 35584 solutions n = 12 => 216288 solutions
Note that we always talk about Langford pairings (in plural) in this post. That's because either a sequence has no Langford pairings or it has two or more Langford pairings. There is never a sequence that has only one Langford pairing. That's because if we find at least one Langford pairing for a sequence, the reverse of that Langford pairing is also a Langford pairing. Therefore, when Langford pairings exist for a sequence, they must at least be two in number. Since they occur in pairs, they are always even in number. This is why we don't have to write "one or more Langford pairings" in this post. We can always write "Langford pairings" instead.
From the output above, we can form a conjecture:
For convenience, let us denote the sequence \( (1, 1, 2, 2, \dots, n, n) \) as \( S_n. \) We will now prove the above conjecture in two parts:
Let \( S_n = (1, 1, 2, 2, \dots, n, n) \) be a sequence such that it has Langford pairings. Let us pick an arbitrary Langford pairing \( s \) of \( S_n \) and split this Langford pairing \( s \) into two mutually exclusive subsequences \( s_1 \) and \( s_2 \) such that:
For example, if we pick \( s = (1, 7, 1, 2, 5, 6, 2, 3, 4, 7, 5, 3, 6, 4) \) which is a Langford pairing of \( S_7, \) we split \( s \) into \begin{align*} s_1 & = (1, 1, 5, 2, 4, 5, 6), \\ s_2 & = (7, 2, 6, 3, 7, 3, 4). \end{align*}
We can make a few observations:
Do these observations hold good for every Langford pairing of any aribrary \( S_n \) for every positive integer value of \( n? \) Yes, they do. We will now prove them one by one:
Let us consider an even number \( k \) from a Langford pairing. If the first occurrence of \( k \) lies at the \( i \)th position in the pairing, then its second occurrence lies at the \( (i + k + 1) \)th position. Since \( k \) is even, \( i \) and \( i + k + 1 \) have different parities, i.e., if \( i \) is odd, then \( i + k + 1 \) is even and vice versa. Therefore, if the first occurrence of \( k \) lies at an odd numbered position, its second occurrence must lie at an even numbered position and vice versa. Thus one occurrence of \( k \) must belong to \( s_1 \) and the other must belong to \( s_2. \) This proves the first observation.
Now let us consider an odd number \( k \) from a Langford pairing. If the first occurrence of \( k \) lies at the \( i \)th position in the pairing, then its second occurrence lies at the \( (i + k + 1) \)th position. Since \( k \) is odd, \( i \) and \( i + k + 1 \) have the same parity. Therefore, either both occurrences of \( k \) belong to \( s_1 \) or both belong to \( s_2. \) This proves the third observation.
Each subsequence, \( s_1 \) or \( s_2 \) has \( n \) numbers because we split a Langford pairing \( s \) with \( 2n \) numbers equally between the two subsequences. We have shown that each subsequence has \( \left\lfloor \frac{n}{2} \right\rfloor \) even numbers. Therefore the number of odd numbers in each subsequence is \( n - \left\lfloor \frac{n}{2} \right\rfloor = \left\lceil \frac{n}{2} \right\rceil. \)
From the third observation, we know that the odd numbers always occur in pairs in each subsequence because both occurrences of an odd number occur together in the same subsequence. Therefore, the number of odd numbers in each subsequence must be even. Since the number of odd numbers in each subsequence is \( \left\lceil \frac{n}{2} \right\rceil \) as proven for the fourth observation, we conclude that \( \left\lceil \frac{n}{2} \right\rceil \) must be even.
Now let us see what must \( n \) be like so that \( \left\lceil \frac{n}{2} \right\rceil \) is even.
Let us express \( n \) as \( 4q + r \) where \( q \) is a nonnegative integer and \( r \in \{0, 1, 2, 3\}. \)
We see that \( \left\lceil \frac{n}{2} \right\rceil \) is even if and only if either \( n \equiv 0 \pmod{4} \) or \( n \equiv 3 \pmod{4} \) holds good.
We have shown that if a sequence \( S_n \) has Langford pairings, then either \( n \equiv 0 \pmod{4} \) or \( n \equiv 3 \pmod{4}. \) This proves the necessity of the condition.
If we can show that we can construct a Langford pairing for \( (1, 1, 2, 2, \dots, n, n ) \) for both cases, i.e., \( n \equiv 0 \pmod{4} \) as well as \( n \equiv 3 \pmod{4}, \) then it would complete the proof.
Let us define some notation to make it easier to write sequences we will use in the construction of a Langford pairing:
\( (i \dots j)_{even} \) denotes a sequence of even positive integers from \( i \) to \( j, \) exclusive, arranged in ascending order.
For example, \( (1 \dots 8)_{even} = (2, 4, 6) \) and \( (1 \dots 2)_{even} = (). \)
\( (i \dots j)_{odd} \) denotes a sequence of odd positive integers from \( i \) to \( j, \) exclusive, arranged in ascending order.
For example, \( (1 \dots 8)_{odd} = (3, 5, 7) \) and \( (1 \dots 3)_{odd} = (). \)
\( s' \) denotes the reverse of the sequence \( s. \)
For example, for a sequence \( s = (2, 3, 4, 5), \) we have \( s' = (2, 3, 4, 5)' = (5, 4, 3, 2). \)
\( s \cdot t \) denotes the concatenation of sequences \( s \) and \( t. \)
For example, for sequences \( s = (1, 2, 3) \) and \( t = (4, 5) , \) we have \( s \cdot t = (1, 2, 3) \cdot (4, 5) = (1, 2, 3, 4, 5). \)
Let \( x = \left\lceil \frac{n}{4} \right\rceil. \) Therefore, \[ x = \begin{cases} \frac{n}{4} & \text{if } n \equiv 0 \pmod{4}, \\ \frac{n + 1}{4} & \text{if } n \equiv 3 \pmod{4}. \end{cases} \]
Let us now define the following eight sequences: \begin{align*} a & = (2x - 1), \\ b & = (4x - 2), \\ c & = (4x - 3), \\ d & = (4x), \\ p & = (0 \dots a)_{odd}, \\ q & = (0 \dots a)_{even}, \\ r & = (a \dots b)_{odd}, \\ s & = (a \dots b)_{even}. \end{align*}
Now let us construct a Langford pairing for both cases: \( n \equiv 0 \pmod{4} \) and \( n \equiv 3 \pmod{4}. \) We will do this case by case.
If \( n \equiv 0 \pmod{4}, \) we construct a Langford pairing with the following concatenation: \[ s' \cdot p' \cdot b \cdot p \cdot c \cdot s \cdot d \cdot r' \cdot q' \cdot b \cdot a \cdot q \cdot c \cdot r \cdot a \cdot d. \]
Let us do an example with \( n = 12. \)
For \( n = 12, \) we get \( x = \frac{n}{4} = 3. \) Therefore, \begin{alignat*}{2} a & = (2x - 1) && = (5), \\ b & = (4x - 2) && = (10), \\ c & = (4x - 3) && = (11), \\ d & = (4x) && = (12), \\ p & = (0 \dots a)_{odd} && = (1, 3), \\ q & = (0 \dots a)_{even} && = (2, 4), \\ r & = (a \dots b)_{odd} && = (7, 9), \\ s & = (a \dots b)_{even} && = (6, 8). \end{alignat*} After performing the specified concatenation, we get the following Langford pairing: \[ ( 8, 6, 3, 1, 10, 1, 3, 11, 6, 8, 12, 9, 7, 4, 2, 10, 5, 2, 4, 11, 7, 9, 5, 12 ). \]
Let us now show that any construction of a sequence as per this specified concatenation always leads to a Langford pairing.
Each sequence \( a, \) \( b, \) \( c, \) and \( d \) has one number each. Each sequence \( p, \) \( q, \) \( r, \) and \( s \) has \( x - 1 \) numbers each.
The two occurrences of \( a \) have \( q, \) \( c, \) and \( r \) in between, i.e., \( (x - 1) + 1 + (x - 1) = 2x - 1 = a \) numbers in between. Similarly, we can check that the two occurrences of \( b \) have \( b \) numbers in between, likewise for \( c \) and \( d. \)
The two occurrences of \( 1 \) belong to belong to \( p. \) Between these two occurrences of \( 1, \) we have only one element of \( b. \) We can show that for each \( k \) in \( p, \) there are \( k \) numbers in between. For any \( k \) in \( p, \) there is the sequence \( (0..k)'_{odd} \cdot b \cdot (0..k)_{odd} \) in between the two occurrences of \( k, \) i.e, there are \( \frac{k - 1}{2} + 1 + \frac{k - 1}{2} = k \) numbers in between.
If \( n \equiv 3 \pmod{4}, \) we construct a Langford pairing with the following concatenation: \[ s' \cdot p' \cdot b \cdot p \cdot c \cdot s \cdot a \cdot r' \cdot q' \cdot b \cdot a \cdot q \cdot c \cdot r. \]
Note that this concatenation of sequences is almost the same as the concatenation in the previous section with the following two differences:
Let us do an example with \( n = 11. \) For \( n = 12, \) we get \( x = \frac{n + 1}{4} = 3. \) Therefore, the sequences \( a, \) \( b, \) \( c, \) \( p, \) \( q, \) \( r, \) and \( s \) are same as those in the last example in the previous section. After performing the specified concatenation, we get the following Langford pairing: \[ (8, 6, 3, 1, 10, 1, 3, 11, 6, 8, 5, 9, 7, 4, 2, 10, 5, 2, 4, 11, 7, 9). \]
We can verify that for every \( k \) in a Langford pairing constructed in this manner, there are \( k \) numbers in between. The verification steps are similar to what we did in the previous section.
]]>Here is a C puzzle that involves some analysis of the machine code generated from it followed by manipulation of the runtime stack. The solution to this puzzle is implementation-dependent. Here is the puzzle:
Consider this C code:
#include <stdio.h>
void f()
{
}
int main()
{
printf("1\n");
f();
printf("2\n");
printf("3\n");
return 0;
}
Define the function f()
such that the output of the above
code is:
1
3
Printing 3
in f()
and exiting is not allowed
as a solution.
If you want to think about this problem, this is a good time to pause and think about it. There are spoilers ahead.
The solution essentially involves figuring out what code we can place in
the body of f()
such that it causes the program to skip
over the machine code generated for the printf("2\n")
operation. I'll share two solutions for two different implementations:
Let us first see step by step how I approached this problem for GCC. We
add a statement char a = 7;
to the function
f()
. The code looks like this:
#include <stdio.h>
void f()
{
char a = 7;
}
int main()
{
printf("1\n");
f();
printf("2\n");
printf("3\n");
return 0;
}
There is nothing special about the number 7
here. We just
want to define a variable in f()
and assign some value to
it.
Then we compile the code and analyze the machine code generated for
f()
and main()
functions.
$ gcc -c overwrite.c && objdump -d overwrite.o overwrite.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <f>: 0: 55 push %rbp 1: 48 89 e5 mov %rsp,%rbp 4: c6 45 ff 07 movb $0x7,-0x1(%rbp) 8: c9 leaveq 9: c3 retq 000000000000000a <main>: a: 55 push %rbp b: 48 89 e5 mov %rsp,%rbp e: bf 00 00 00 00 mov $0x0,%edi 13: e8 00 00 00 00 callq 18 <main+0xe> 18: b8 00 00 00 00 mov $0x0,%eax 1d: e8 00 00 00 00 callq 22 <main+0x18> 22: bf 00 00 00 00 mov $0x0,%edi 27: e8 00 00 00 00 callq 2c <main+0x22> 2c: bf 00 00 00 00 mov $0x0,%edi 31: e8 00 00 00 00 callq 36 <main+0x2c> 36: b8 00 00 00 00 mov $0x0,%eax 3b: c9 leaveq 3c: c3 retq
When main()
calls f()
, the microprocessor
saves the return address (where the control must return to after
f()
is executed) in stack. The line at offset
1d in the listing above for main()
is the call
to f()
. After f()
is executed, the instruction
at offset 22 is executed. Therefore the return address that
is saved on stack is the address at which the instruction at offset
22 would be present at runtime.
The instructions at offsets 22 and 27
highlighted in orange are the instructions for the
printf("2\n")
call. These are the instructions we want to
skip over. In other words, we want to modify the return address in the
stack from the address of the instruction at offset 22 to
that of the instruction at offset 2c. This is equivalent to
skipping 10 bytes (0x2c - 0x22 = 10) of machine code or adding 10 to the
return address saved in the stack.
Now how do we get hold of the return address saved in the stack when
f()
is being executed? This is where the variable
a
we defined in f()
helps. The instruction at
offset 4 highlighted in olive is the instruction generated
for assigning 7
to the variable a
.
From the knowledge of how microprocessor works and from the machine code
generated for f()
, we find that the following sequence of
steps are performed during the call to f()
:
f()
pushes the content of the RBP (base
pointer) register into the stack.
f()
copies the content of the RSP (stack
pointer) register to the RBP register.
f()
stores the byte value 7
at the memory address specified by the content of RBP minus 1. This
achieves the assignment of the value 7
to the variable
a
.
After 7
is assigned to the variable a
, the
stack is in the following state:
Address | Content | Size (in bytes) |
---|---|---|
&a + 5 |
Return address (old RIP) | 8 |
&a + 1 |
Old base pointer (old RBP) | 8 |
&a |
Variable a |
1 |
If we add 9 to the address of the variable a
, i.e.,
&a
, we get the address where the return address is
stored. We saw earlier that if we increment this return address by 10
bytes, it solves the problem. Therefore here is the solution code:
#include <stdio.h>
void f()
{
char a;
(&a)[9] += 10;
}
int main()
{
printf("1\n");
f();
printf("2\n");
printf("3\n");
return 0;
}
Finally, we compile and run this code and confirm that the solution works fine:
$ gcc overwrite.c && ./a.out 1 3
Now we will see another example solution, this time for Visual Studio 2005.
Like before we define a variable a
in f()
. The
code now looks like this:
#include <stdio.h>
void f()
{
char a = 7;
}
int main()
{
printf("1\n");
f();
printf("2\n");
printf("3\n");
return 0;
}
Then we compile the code and analyze the machine code generated from it.
C:\>cl overwrite.c Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42 for 80x86 Copyright (C) Microsoft Corporation. All rights reserved. overwrite.c Microsoft (R) Incremental Linker Version 8.00.50727.42 Copyright (C) Microsoft Corporation. All rights reserved. /out:overwrite.exe overwrite.obj C:\>dumpbin /disasm overwrite.obj Microsoft (R) COFF/PE Dumper Version 8.00.50727.42 Copyright (C) Microsoft Corporation. All rights reserved. Dump of file overwrite.obj File Type: COFF OBJECT _f: 00000000: 55 push ebp 00000001: 8B EC mov ebp,esp 00000003: 51 push ecx 00000004: C6 45 FF 07 mov byte ptr [ebp-1],7 00000008: 8B E5 mov esp,ebp 0000000A: 5D pop ebp 0000000B: C3 ret 0000000C: CC int 3 0000000D: CC int 3 0000000E: CC int 3 0000000F: CC int 3 _main: 00000010: 55 push ebp 00000011: 8B EC mov ebp,esp 00000013: 68 00 00 00 00 push offset $SG2224 00000018: E8 00 00 00 00 call _printf 0000001D: 83 C4 04 add esp,4 00000020: E8 00 00 00 00 call _f 00000025: 68 00 00 00 00 push offset $SG2225 0000002A: E8 00 00 00 00 call _printf 0000002F: 83 C4 04 add esp,4 00000032: 68 00 00 00 00 push offset $SG2226 00000037: E8 00 00 00 00 call _printf 0000003C: 83 C4 04 add esp,4 0000003F: 33 C0 xor eax,eax 00000041: 5D pop ebp 00000042: C3 ret Summary B .data 57 .debug$S 2F .drectve 43 .text
Just like in the previous objdump
listing, in this listing
too, the instruction at offset 4
highlighted in olive shows
where the variable a
is allocated and the instructions at
offsets 25
, 2A
, and 2F
highlighted in orange show the instructions we want to skip, i.e.,
instead of returning to the instruction at offset 25
, we
want the microprocessor to return to the instruction at offset
32
. This involves skipping 13 bytes (0x32 - 0x25 = 13) of
machine code.
Unlike the previous objdump
listing, in this listing we see
that the Visual Studio I am using is a 32-bit on, so it generates
machine code to use 32-bit registers like EBP, ESP, etc. Thus the stack
looks like this after 7
is assigned to the variable
a
:
Address | Content | Size (in bytes) |
---|---|---|
&a + 5 |
Return address (old EIP) | 4 |
&a + 1 |
Old base pointer (old EBP) | 4 |
&a |
Variable a |
1 |
If we add 5 to the address of the variable a
, i.e.,
&a
, we get the address where the return address is
stored. Here is the solution code:
#include <stdio.h>
void f()
{
char a;
(&a)[5] += 13;
}
int main()
{
printf("1\n");
f();
printf("2\n");
printf("3\n");
return 0;
}
Finally, we compile and run this code and confirm that the solution works fine:
C:\>cl /w overwrite.c Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.42 for 80x86 Copyright (C) Microsoft Corporation. All rights reserved. overwrite.c Microsoft (R) Incremental Linker Version 8.00.50727.42 Copyright (C) Microsoft Corporation. All rights reserved. /out:overwrite.exe overwrite.obj C:\>overwrite.exe 1 3
The machine code that the compiler generates for a given C code is highly dependent on the implementation of the compiler. In the two examples above, we have two different solutions for two different compilers.
Even with the same brand of compiler, the way it generates machine code for a given code may change from one version of the compiler to another. Therefore, it is very likely that the above solution would not work on another system (such as your system) even if you use the same compiler that I am using in the examples above.
However, we can arrive at the solution for an implementation of the
compiler by determining what number to add to &a
to get
the address where the return address is saved on stack and what number
to add to this return address to make it point to the instruction we
want to skip to after f()
returns.
Here is a real life problem from a factory. There are illiterate workers who cannot identify decimal digits. The management team of the factory is trying to figure if there is a way for these workers to operate a digital weighing scale to fill buckets with a certain mass of a given material. For example, they may be asked to fill 5.3 kg of a certain material in the bucket, i.e., decimal fractions are involved.
If the factory were using a beam balance, this would have been an easy problem to solve. The workers could then place the required weight in one pan and keep pouring the material in the other pan until the beam appears to be balanced.
However this factory uses a digital weighing scale which involves recognizing decimal digits to read the measurement. What do you think is the easiest way to train the workers to do their job without having to teach them how to count?
I have a solution in mind which would involve configuring the digital weighing scale in a certain way for every measurement the workers have to make. I will propose this solution to the management team of the factory. But I would like to know any suggestions you have and take them into account as well before proposing my solution. I will also share the solution I have in mind after learning about your suggestions.
Update on 08 July 2010: Prunthaban has suggested a solution in the comments section which is pretty much what I had in mind too. I will propose this solution to the factory. The solution works like this: Say the worker has to fill 5.3 kg of a certain material into the bucket. A literate supervisor first places 5.3 kg of that material on the weighing scale. The instrument now shows "5.3 kg" on its display. Now the remainder of the solution assumes that the digital weighing balance has a calibration wheel to calibrate the instrument. The supervisor turns the calibration wheel until the display shows "0.0" kg while the 5.3 kg of material is still placed on it. Now the material is removed from the balance and the display shows "-5.3 kg". Now all a worker needs to do is pour the given material on this calibrated balance until the display shows "0.0 kg". As long as the workers can be taught to recognize the digit "0", this solution should work fine.
Update on 05 Aug 2010: The above solution was successfully implemented in OCL India Limited, the factory where this problem was faced. The digital weighing balance they bought indeed had a calibration wheel, so the above solution worked for them. Thank you, Prunthaban and others who participated in this discussion.
]]>Here is a fun quiz I prepared recently:
Hint: The meaning of C is completely different in all the questions.
Update: The quiz has been cracked in the comments section. The answers are provided below. If you want to think about the problem before you see the solutions, this is a good time to pause and think about it. There are spoilers ahead.
Here are the answers with a brief description about each answer:
Dennis : C :: Bjarne : C++
Dennis Ritchie created C and Bjarne Stroustrup created C++.
Sa : C :: Pa : G
The Sanskrit names of musical notes in an octave are Sa, Re, Ga, Ma, Pa, Dha, Ni, Sa. The equivalent names in many English-speaking countries are C, D, E, F, G, A, B, C.
6 : C :: 53 : I
Carbon has symbol C and atomic number 6. Iodine has symbol I and atomic number 53.
100 : C :: 500: D
In Roman numerals, 100 is represented by C and 500 by D.
50 : C :: 122 : F
50 degrees Farenheit equals 122 degrees Centigrade (50 °C = 122 °F).
Update: A similar quiz by Prasanna mentioned in the comments section has been cracked.
Here is Prasanna's quiz along with the answers:
195 : C :: 209 : J
In EBCDIC, the character 'C' has the code 195 and the character 'J' has the code 209.
Bohai : C :: Oolong : T
Bohai Sea and Oolong tea.