Bitwise Operations and Subnetting
By Brandon James on 2019-07-29

Back in September of 2016 I wrote a subnet calculator in C and then blogged about it. This entry is based on that old blog post.

## Converting To and From Dotted Decimal Notation

IPv4 Addresses are simply unsigned 32-bit integers. This makes it easy to perform calculations on them using bitwise operations. It's common to see IP addresses represented as four seperate octets. This is done primarily for readablity, but it also aids in intuition when you start looking at the math behind IP subnets.

### Converting FROM Dotted Decimal Notation

In order to do anything useful, we first need to take the human provided dotted decimal notation and convert it to a 32 bit unsigned integer.

```unsigned int dotted_decimal_to_int(char ip[]){

// char is exactly 1 byte
unsigned char bytes = {0};

sscanf(ip, "%hhd.%hhd.%hhd.%hhd", &bytes, &bytes, &bytes, &bytes);

// set 1 byte at a time by left shifting (<<) and ORing (|)
return bytes | bytes << 8 | bytes << 16 | bytes << 24;

}
```

This function works by scanning the C string containing the IP address provided by the user into an array of bytes. It then returns an unsigned integer. Using 192.168.0.1 as an example, we first read the octets into an arry of bytes. This results in something similar to the following in memory:

Byte 0 Byte 1 Byte 2 Byte 3 Base
192 168 0 1 Decimal
11000000
10101000 00000000 00000001 Binary

As we return the unsigned int, the bytes are left shifted so that they are properly aligned and then a logical OR is applied to combine the bytes. The result of this is a 32-bit representation of the IP address. In this case, the resulting integer in decimal is 3,232,235,521. The table below shows what the left shift looks like in memory.

Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
Byte 00000000 00000000 00000000 00000001 N/A
Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
Byte 00000000 00000000 00000000 00000000 >>8
Result 00000000 00000000
Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
Byte 00000000 00000000 00000000 10101000 >>16
Result 10101000 00000000 00000000
Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
Byte 11000000 >>24
Result 11000000 00000000 00000000 00000000

And the OR operation:

Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
Byte 11000000 00000000 00000000 00000000
Byte 10101000 00000000 00000000 OR
Result 11000000 10101000 00000000 00000000
Byte 00000000 00000000 OR
Result 11000000 10101000 00000000 00000000
Byte 00000001 OR
Result 11000000 10101000 00000000 00000001

### Converting TO Dotted Decimal Notation

After we've finished performing our calculations, we need to return the subnet to a human readable format. This can be done with the following function:

```void printip(int ip){

// takes a 32 bit integer and prints it as 4 decimal separate octets

unsigned char bytes;

// set the byte to the first byte of the ip
bytes = ip;
bytes = ip >> 8; // right shift by a byte and repeat
bytes = ip >> 16;
bytes = ip >> 24;

printf("%d.%d.%d.%d\n", bytes, bytes, bytes, bytes);

return;

}
```

This function works by taking our 32-bit integer and breaking it into 4 separate bytes that can be evaluated separately. We do this by assigning each separate byte to a member of a char array. This is done by right shifting the number by 8 bits prior to each assignment. Note that the right shift operator causes the bits at the end get rotated to the front.

Using 192.168.0.1 as our example again:

Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
byte 11000000 10101000 00000000 00000001
byte 10101000 00000000 00000001 11000000 <<8
byte 00000000 00000001 11000000 10101000 <<16
byte 00000001 11000000 10101000 10101000 <<24

In the above example, after each shift we are setting the contents of byte 1 to the current index of our byte array. Then we simply use printf to display the integer in dotted decimal notation.

### Converting To and From CIDR Notation

Subnets are commonly referenced using CIDR notation (eg 192.168.0.0/24). Since CIDR notation is simply the number of most significant bits set, it's pretty easy to create a function to do the conversion.

```unsigned int cidr_to_mask(unsigned int cidrValue){

// left shift 1 by 32 - cidr, subtract 1 from the result and XORing
// it with a mask that has all bits set, yeilds the subnet mask
return -1 ^ ((1 << (32 - cidrValue)) - 1);

}
```

I'll show how this works by using a /24 mask. First we subtract 32 by 24, which yields 8. Then we left shift 1 8 times, which yields 1 00000000. Next, we subtract the result by 1, yielding 11111111. Finally, we XOR the result with -1 (when working with unsigned values, -1 sets all bits), which results in 11111111 11111111 11111111 00000000.

Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
00000000 00000000 00000000 00000001 <<8
Result 00000000 00000000 00000001 00000000 -1
Result 00000000 00000000 00000000 11111111
-1 11111111 11111111 11111111 11111111 XOR
Result 11111111 11111111 11111111 00000000

Additionally, if the user gives us a subnet mask using dotted decimal notation, we'll want to give them the mask in CIDR notation. This can be done by counting the number of bits set in the subnet mask.

```unsigned int cidr_to_mask(unsigned int cidrValue){

// left shift 1 by 32 - cidr, subtract 1 from the result and XORing
// it with a mask that has all bits set, yeilds the subnet mask
return -1 ^ ((1 << (32 - cidrValue)) - 1);

}
```

This function works as follows:

Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation CIDR
Mask - 1 11111111 11111111 11111110 00000000 AND
Result 11111111 11111111 11111110 00000000 1
Result - 1 11111111 11111111 11111101 00000000 AND
Result 11111111 11111111 11111100 00000000 2
Result - 1 11111111 11111111 ‭11111011‬ 00000000 AND
Result 11111111 11111111 ‭11111000‬ 00000000 3
Result 11111111 11111111 ‭11110111‬ 00000000 AND
Result 11111111 11111111 ‭11110000‬ 00000000 4

...

continue until no bits are set

Now that we've dealt with the human readability issues. Let's take a look at the operations that actually deal with subnet calculations.

First off, to calculate the Network or Subnet address, we simply take the IP address and netmask and apply the AND operation. The truth table below is for an IP address of 192.168.0.10 with a /24 mask.

Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
IP 11000000 10101000 00000000 00001010
Mask 11111111 11111111 11111111 00000000 AND
Result 11000000 10101000 00000000 00000000

In C this function is simply expressed as:

```unsigned int calc_network_address(unsigned int ipaddress, unsigned int netmask){
}
```

Calculating the broadcast address is as simple as adding the network address to the subnet's complement (ie the result of the NOT operation on the subnet mask). Again using the same network as our previous example.

Variable Byte 0 Byte 1 Byte 2 Byte 3 Operation
IP 11000000 10101000 00000000 00000000
~Mask 00000000 00000000 00000000 11111111 +
Result 11000000 10101000 00000000 11111111

The dotted decimal result is 192.168.0.255. This is another operation that is easily expressed in C.

```unsigned int calc_broadcast(unsigned int network, unsigned int netmask){