C - Using bit-shift operators for base conversion

Question

I'm trying to convert some data from hex to base64 in C, I found an algorithm online but I would really like to know how it works rather than just implenting it and firing it off. If someone could please explain how the following is working I would appreciate it. I have been reading about the shift operators and I don't seem to understand them as much as I thought I did...it's not quite clicking for me.

for (x = 0; x < dataLength; x += 3) 
{
  /* these three 8-bit (ASCII) characters become one 24-bit number */
  n = data[x] << 16;

  if((x+1) < dataLength)
     n += data[x+1] << 8;

  if((x+2) < dataLength)
     n += data[x+2];

  /* this 24-bit number gets separated into four 6-bit numbers */
  n0 = (uint8_t)(n >> 18) & 63;
  n1 = (uint8_t)(n >> 12) & 63;
  n2 = (uint8_t)(n >> 6) & 63;
  n3 = (uint8_t)n & 63;

This code was taken from Wikibooks, it is NOT mine, I'm just trying to understand the bitshifting and how it's allowing me to convert the data.

Thank you for your help, I really appreciate it.

Source: Base64

Answer 1

First of all, the input data is not hex as you say. It's simply data stored as bytes. The code will give you the base64 representation of it (although the code you posted lacks the part which will map n0, n1, n2, n3 to printable ASCII characters).

Suppose the first three bytes of the input are (in binary representation, each letter represents a 0 or 1):

abcdefgh, ijklmnop, qrstuvwx

The first part of the code will combine them to a single 24-bit number. This is done by shifting the first one 16 bits to the left and the second one 8 bits to the left and adding:

  abcdefgh0000000000000000      (abcdefgh << 16)
+ 00000000ijklmnop00000000      (ijklmnop << 8)
  0000000000000000qrstuvwx
  ------------------------
  abcdefghijklmnopqrstuvwx

Then it separates this into four 6-bit numbers by shifting and and'ing. For example, the second number is calculated by shifting 12 bits to the right and and'ing with 111111

n     =   abcdefghijklmnopqrstuvwx

n>>12 =   000000000000abcdefghijkl
63    =   000000000000000000111111

And'ing gives:
          000000000000000000ghijkl

Answer 2

Ok here is a bit of explanation..

data[x] is an array of chars, a char is usuall 8bits.. (random 8bits number 01010101) n is a 32bit number here is a random 32bit number(01011111000011110000111100001111)think there are 32bits there :)

remember n is 32bits and data is only 8bits.. lets go through the first line

 n = data[x] << 16;

<<16 has precedence over the equal sign so its evaluated first.

data[x] << 16 means move the bits in memory that data[x] represents by 16bits to the left. suppose data[x] = 'a' this is represented by 01100001 in memory(1 bytes), so lets move is 16bits to the left

n = 00000000 01100001 00000000 00000000

next we have

if((x+1) < dataLength)
 n += data[x+1] << 8;

this says move the next char data[x+1] 8 bits and add it to n; so lets move it 8 bits first

( I assumed it was 'a' again)
00000000 00000000 01100001 00000000 
(this is done in some register in your processor)

now lets add it to n

00000000 01100001 01100001 00000000

next part is

 if((x+2) < dataLength)
 n += data[x+2];

lets do the same thing here, notice there is no bit shifting, since the last 8bits of n are free!! all we need to do is add it to n

b = 01100010 (assumed data[x+2] = 'b') adding it to n

  00000000 01100001 01100001 01100010

great so now we have a 24bits number(actually n is 32bits but the last 24bits is what we need)

next part

n0 = (uint8_t)(n >> 18) & 63; 
(take note n0 is only 8bits wide or a single unsigned byte)

take n and move it to the left by 18bits and "and" it with 63

n = 00000000 01100001 01100001 01100010
n moved 18bits to right is  00000000 00000000 00000000 00011000

now n is cast to an unsigned int of 8bits (uint8_t)

so now it becomes 00011000

last part is the & operator(bitwise and) 

    00011000 & 
    00111111
n0= 00011000 

now repeat this for the rest