By definition, applying the initial Permutation of DES is shuffling bits per
01 02 03 04 05 06 07 08 58 50 42 34 26 18 10 02
09 10 11 12 13 14 15 16 60 52 44 36 28 20 12 04
17 18 19 20 21 22 23 24 \ 62 54 46 38 30 22 14 06
25 26 27 28 29 30 31 32 ----\ 64 56 48 40 32 24 16 08
33 34 35 36 37 38 39 40 ----/ 57 49 41 33 25 17 09 01
41 42 43 44 45 46 47 48 / 59 51 43 35 27 19 11 03
49 50 51 52 53 54 55 56 61 53 45 37 29 21 13 05
57 58 59 60 61 62 63 64 63 55 47 39 31 23 15 07
where the left table represents, in reading order, bits of the 64-bit input from first (most significant) to last; and the right table represents, in reading order, the Left then Right 32-bit registers, per that same convention.
That transformation has great regularity: each line of the output (in reading order) is a column of the input (from bottom to top). That's a property of a transpose except for inverted order. IP is a mirror of the input according to the / diagonal, followed by a regular shuffling of lines (lines 1 2 3 4 5 6 7 8 go to lines 4 8 3 7 2 6 1 5).
This structure of IP has a hardware rationale: the transpose allows an implementation with Left and Right registers implemented each as four 8-bit shift registers, with 1 bit entering in each of the 8 shift registers for each plaintext octet sequentially fed into the DES hardware. And the shuffling brings next to each others the bits that interact when XORing the Left and Right registers.
The question's code makes use of 5 "Half-Butterfly Permutations" (as I name them by analogy with the butterfly diagram) indexed with $k$ taking all values from 0 to 4. Each splits the 32-bit lleft
and right
registers into $2^{5-k}$ segments each $2^k$-bit, and exchanges odd-numbered segments of one register with the higher (even-numbered) segment of the other, with thus a shift by $2^k$-bit.
One general HBP is implemented with 3 instructions involving a total of 6 bitwise operations directly supported by C. It uses XOR in a way similar to exchanging x
and y
with the idiom x^=y; y^=x; x^=y;
taking advantage of associativity and commutativity to avoid a work value; but uses one due to the shifting and masking.
There are some irregularities in the code to perform the prescribed shuffling of lines. Also, the code wants to end with the 32-bit lleft
and right
pre-rotated on the left by 1 bit, because then the low-order 6 bits of these registers are properly aligned to serve as index in an S-box (after XOR with sub-key); and the HBP with $k=0$ is performed between these two rotations, because that removes the shifts in that HBP.
Here is how it goes step by step. We start from
01 02 03 04 05 06 07 08 most significant byte of lleft
09 10 11 12 13 14 15 16 :
17 18 19 20 21 22 23 24 :
25 26 27 28 29 30 31 32 least significant byte of lleft
33 34 35 36 37 38 39 40 most significant byte of right
41 42 43 44 45 46 47 48 :
49 50 51 52 53 54 55 56 :
57 58 59 60 61 62 63 64 least significant byte of right
then perform the Half-Butterfly Permutation with $k=2$
work = ((leftt >> 4) ^ right) & 0x0f0f0f0f;
right ^= work;
leftt ^= (work << 4);
giving
37 38 39 40 05 06 07 08 most significant byte of lleft
45 46 47 48 13 14 15 16 :
53 54 55 56 21 22 23 24 :
61 62 63 64 29 30 31 32 least significant byte of lleft
33 34 35 36 01 02 03 04 most significant byte of right
41 42 43 44 09 10 11 12 :
49 50 51 52 17 18 19 20 :
57 58 59 60 25 26 27 28 least significant byte of right
then perform the HBP with $k=4$
work = ((leftt >> 16) ^ right) & 0x0000ffff;
right ^= work;
leftt ^= (work << 16);
giving
49 50 51 52 17 18 19 20 most significant byte of lleft
57 58 59 60 25 26 27 28 :
53 54 55 56 21 22 23 24 :
61 62 63 64 29 30 31 32 least significant byte of lleft
33 34 35 36 01 02 03 04 most significant byte of right
41 42 43 44 09 10 11 12 :
37 38 39 40 05 06 07 08 :
45 46 47 48 13 14 15 16 least significant byte of right
then perform the HBP with $k=1$
work = ((right >> 2) ^ leftt) & 0x33333333;
leftt ^= work;
right ^= (work << 2);
giving
49 50 33 34 17 18 01 02 most significant byte of lleft
57 58 41 42 25 26 09 10 :
53 54 37 38 21 22 05 06 :
61 62 45 46 29 30 13 14 least significant byte of lleft
51 52 35 36 19 20 03 04 most significant byte of right
59 60 43 44 27 28 11 12 :
55 56 39 40 23 24 07 08 :
63 64 47 48 31 32 15 16 least significant byte of right
then perform the HBP with $k=3$
work = ((right >> 8) ^ leftt) & 0x00ff00ff;
leftt ^= work;
right ^= (work << 8);
giving
49 50 33 34 17 18 01 02 most significant byte of lleft
51 52 35 36 19 20 03 04 :
53 54 37 38 21 22 05 06 :
55 56 39 40 23 24 07 08 least significant byte of lleft
57 58 41 42 25 26 09 10 most significant byte of right
59 60 43 44 27 28 11 12 :
61 62 45 46 29 30 13 14 :
63 64 47 48 31 32 15 16 least significant byte of right
then perform the pre-rotation of right
by one bit to the left
right = (right << 1) | ((right >> 31) & 1);
giving
49 50 33 34 17 18 01 02 most significant byte of lleft
51 52 35 36 19 20 03 04 :
53 54 37 38 21 22 05 06 :
55 56 39 40 23 24 07 08 least significant byte of lleft
58 41 42 25 26 09 10 59 most significant byte of right
60 43 44 27 28 11 12 61 :
62 45 46 29 30 13 14 63 :
64 47 48 31 32 15 16 57 least significant byte of right
then perform the HBP with $k=0$, eased by the previous rotation
work = (leftt ^ right) & 0xaaaaaaaa;
leftt ^= work;
right ^= work;
giving
58 50 42 34 26 18 10 02 most significant byte of lleft
60 52 44 36 28 20 12 04 :
62 54 46 38 30 22 14 06 :
64 56 48 40 32 24 16 08 least significant byte of lleft
49 41 33 25 17 09 01 59 most significant byte of right
51 43 35 27 19 11 03 61 :
53 45 37 29 21 13 05 63 :
55 47 39 31 23 15 07 57 least significant byte of right
then perform the pre-rotation of leftt
by one bit to the left
leftt = (leftt << 1) | (leftt >> 31) & 1);
giving
50 42 34 26 18 10 02 60 most significant byte of lleft
52 44 36 28 20 12 04 62 :
54 46 38 30 22 14 06 64 :
56 48 40 32 24 16 08 58 least significant byte of lleft
49 41 33 25 17 09 01 59 most significant byte of right
51 43 35 27 19 11 03 61 :
53 45 37 29 21 13 05 63 :
55 47 39 31 23 15 07 57 least significant byte of right
Skipping the pre-rotations and accordingly adjusting the HBP with $k=0$ would have given exactly the permutation specified for IP.
work
then performing two^=
has merely exchanged 16 bits ofleftt
andright
, as selected by the mask, moving them right and left by the shift count. The technique is sort of an extension of the idiomx^=y; y^=x; x^=y;
swapping integer variablesx
andy
, with added selection of bits, and shifts. Hint3: Track what each 32 bits ofleftt
andright
contains: initially, after the last in said group of three instructions, and after the additional two instructions. And when you get it, answer your own question! $\endgroup$