Ricky Manning's blog

Just another WordPress.com site

Learning to program in C — 9th Jun 2016

Learning to program in C

In Running Bash on Ubuntu on Windows 10, I mentioned that I have been learning to program in C as part of a change of roles within the development team. I also mentioned that I have been doing so, primarily, via the book The C Programming Language 2nd Edition (also known as K&R).

This is a book that takes no prisoners. It was written in the days before the world-wide web, before personal computers were mainstream, when PCs didn’t always have permanent storage and when RAM was recorded in KBs. Modern high-level abstraction layers like .NET and the Java VM that manage your code and hide what is really happening under the hood didn’t yet exist.

If you were reading the K&R book in 1988 when it was first published, the chances are, therefore, that you were already a serious programmer with a keen interest in computing and already had some experience programming at such a low-level of abstraction — and it shows.

I’ve been using this book, on and off whilst also studying some of the other things that I need to learn for the new role. When doing so, I have been following along with the examples and exercises along the way. I’m only into the third chapter so far and already some of the exercises have already been devilishly difficult (at least for beginners).

Here’s the one of the most recent ones that I’ve been looking at, exercise 2-6:

Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.

The solution to this involved chaining together multiple bitwise operations, but the exercise was preceded with only the briefest of introductions in bitwise operations. Perhaps other developers would take a different view, but bitwise operations strike me as the kind of thing that “modern” languages and platforms abstract away when possible. That is to say, that these are not the kind of problems that .NET developers such as myself encounter particularly often. They are also often the result of trying to cram as much information into as small a space as possible so as to consume fewer resources, such as RAM — again, the kind of thing that isn’t often much of a concern to developers in today’s world of cheap, fast and plentiful hardware.

So this is a new kind of problem and suffice it to say that the solution required a lot of thinking through. A less brutal book would have you practicing a few bitwise operations first. This style is both a blessing and a curse though; it certainly tests you, but when you arrive at a solution you feel like you’ve really achieved something and you will be all the better for it.

Anyway, on to the solution. I solved it first by writing two arbitrary 8-bit bytes, each representing an unsigned integer, on a piece of paper, in binary code form…

x-and-y-in-binary-uncoloured

…and then picking a value for p (4) and n (3) before highlighting the bits that I need to overwrite in x (red, below), and the bits that I need to overwrite them with from y (blue, below).

x-and-y-in-binary

The result, which I have called z, is shown below:

z-in-binary

So, I now had two steps that I knew needed to turn into code:

  1. Get the rightmost n bits from y
  2. Replace the n bits starting with p with the bits from step one

The book provides an example called getbits(x,p,n):

/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
return (x >> (p+1-n)) & ~(~0 << n);
}

view raw
getbits.c
hosted with ❤ by GitHub

It occurred to me that this would do nicely for step 1 above (i.e. Get the first n bits from y). I also knew the signature for setbits() because the exercise brief defined it. I then set about coding all of this up:

/* 2-6 Write a function setbits(x,p,n,y) that returns x with the n bits that
begin at position p set to the rightmost n bits of y, leaving the other bits
unchanged, page 49 */
#include
unsigned setbits(unsigned x, int p, int n, unsigned y);
unsigned getbits(unsigned x, int p, int n);
int main()
{
printf("%u\n", setbits(209, 4, 3, 187));
}
/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
return (x >> (p+1-n)) & ~(~0 << n);
}
/* setbits: replace bits p -> p+n of x with rightmost n bits from y */
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
int bits, result;
bits = getbits(y, n-1, n);
/* result = ; */
return result;
}

view raw
setbits-pt1.c
hosted with ❤ by GitHub

I could now retrieve the bits that I needed, so I then moved onto step 2 (i.e. Replace the n bits starting with p with the bits from step one).

I studied the bitwise operators in the book and came to the conclusion that there wasn’t a single one that could do what I wanted.

The bitwise operators are as follows:

  • & (bitwise AND)
  • | (bitwise inclusive OR)
  • ^ (bitwise exclusive OR)
  • << (left shift)
  • >> (right shift)
  • ~ (one’s complement)

This was going to require multiple sub-steps, combining multiple bitwise operations.

If you use bitwise AND (e.g. a = b & c) then all bits that are equal to 1 in both operands will be set to 1 in the result, with every other bit being set to 0 (see examples below):

bitwise-AND

If you use bitwise inclusive OR (e.g. a = b | c) then all bits that are set to 1 in either of the two operands are set to 1, with every other bit being set to 0 (see examples below):

bitwise-OR

If you use bitwise exclusive OR (e.g. a = b ^ c) then bits are set to 1 in the result only if they differ in both operands, with every other bit being set to 0

bitwise-XOR

The left shift and right shift operations move the bits left and right respectively, replacing the vacated bits with 0s

bitwise-shift

The one’s complement operation (e.g. a = ~b) reverses all bits

bitwise-ones-complement

From here I could work backwards to find the solution. I needed to end up in a position where I could use the bitwise inclusive OR operation on a version of x with bits 4, 3 & 2 set to 0 and a new variable with the n bits from y, as follows:

x-y-z-bitwise-OR

In order to get to that I needed to do two things: shift the bits from to the left by the difference between of p+1 and n, and then mask off the required bits from y.

I added the following line after getbits() in order to shift the result to the left:

bits = bits << (p+1-n);

Masking off the bits in x was a bit more tricky, but I achieved as follows:

  • create a new unsigned int variable and set it to the one’s complement of 0 (all bits set to 1)
  • shift the bits to the left by a factor of n (all bits set to 1 apart from the first n which are 0s.
  • perform a one’s complement on the mask and shift the bits left by a factor of p+1-n (all bits will now be set to 0 apart from the n bits starting at p which will be set to 1s)
  • perform another one’s complement on the mask (all bits will now be set to 1s apart from the n bits starting at p which will be set to 0s)
  • and then finally perform a bitwise AND between the new x and the mask.

The code for the above looked like this:

mask = ~0;
mask = mask << n;
mask = (~mask) << (p+1-n);
mask = ~mask;
x = x & mask;

Now I had the bits and the new x, all that I had to do was the final bitwise OR

return x | bits;

The final solution has been embedded below:

/* 2-6 Write a function setbits(x,p,n,y) that returns x with the n bits that
begin at position p set to the rightmost n bits of y, leaving the other bits
unchanged, page 49 */
#include <stdio.h>
unsigned setbits(unsigned x, int p, int n, unsigned y);
unsigned getbits(unsigned x, int p, int n);
int main()
{
unsigned x, y;
int p, n;
x = 209U;
p = 4;
n = 3;
y = 187U;
printf("%u\n", setbits(x, p, n, y));
}
/* getbits: get n bits from position p */
unsigned getbits(unsigned x, int p, int n)
{
return (x >> (p+1-n)) & ~(~0 << n);
}
/* setbits: replace bits p -> p+1-n of x with rightmost n bits from y */
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
unsigned bits, mask;
/* get the rightmost n bits from y and shift them to position p */
bits = getbits(y, n-1, n);
bits = bits << (p+1-n);
/* create a mask containing all 1s apart from bits p to p+1-n */
mask = ~0;
mask = mask << n;
mask = (~mask) << (p+1-n);
mask = ~mask;
/* mask off the bits in x that we want to overwrite */
x = x & mask;
/* return the overwritten bits in x */
return x | bits;
}

view raw
setbits-pt2.c
hosted with ❤ by GitHub

Of course, I could condense of this into fewer lines — into one line, even — but for the time being at least, I think  that it is easier understood as it is.

Running Bash on Ubuntu on Windows 10 — 2nd Jun 2016

Running Bash on Ubuntu on Windows 10

Background

I recently agreed to a change of role within the development team at my company. As a result, amongst other things, I have been learning to program in C. For the uninitiated, C is a powerful programming language that originated in the 1970s, and still persists to this day. It can be compiled and executed on most modern Operating Systems (including Windows, Mac OSX and Linux). It is generally used when high-speed performance and efficiency are essential.

The particular application that I will be contributing to is my company’s own customisation of Asterisk (an open-source PBX). Asterisk is written in C and, for our purposes at least, runs on CentOS (a flavour of Linux). I had primarily been a Windows/.NET developer, making GUI applications in a fully featured IDE such as Visual Studio 2013 so I was expecting a steep learning curve.

I only really knew enough about the Linux command line environment so that I could deploy a CentOS template in our VM system, connect to it via a PuTTY terminal and then install and monitor our customisation of Asterisk. I never spent more time than I needed to in this environment, opting to perform text file/configuration file editing in the basic editor provided by the excellent WinSCP — an FTP client.

So, to recap, in a relatively short period of time, I needed to learn C, Asterisk and to become comfortable operating in a Linux command line environment.

Learning C

Programming in a Command Line Environment

We ordered in some classic books like The C Programming Language (2nd Edition) by Kernighan and Ritchie (also known as K&R, and appears to be affectionately known as The Bible, amongst programmers of a certain vintage) and Asterisk: The Definitive Guide amongst others. I deployed a CentOS VM (Virtual Machine) for playing with, installed the various GNU development utilities and I got going.

Here’s a screenshot of the obligatory “Hello World” example written in C, with Vim, in a PuTTY terminal.

hello-world-vim

I’m sure you’ll all agree that it is horrible. Syntax highlighting is a must, as far as I am concerned, which is why I initially opted from Vim over a more basic editor, but what’s with all the impossible to read dark blue? It is not much better in Nano, either, for that matter.

hello-world-nano

It wasn’t long before I began to get frustrated with this and look to customise the color scheme. I chanced upon the Zenburn colour scheme and followed the instructions in order to implement it. With a few extra tweaks (e.g. including line numbers) I arrived at a much better destination.

hello-world-vim-zenburn

This was an improvement, but I still missed editing in a graphical editor on Windows as opposed to in a command line editor in a PuTTY terminal. I’m far more efficient in this environment. Especially when copying and pasting.

Returning to the comfort of Windows

I decided to return to Windows and I downloaded Atom and Visual Studio Code, alternating between the two in order to determine which one I preferred.

I found both to be a pleasure to work in, although there’s one that I find I keep going back to first. Atom appears to have won this particular battle.

Despite deciding to code in a Windows environment, I still wanted my code to compile and run in a Linux one, so, alongside Atom, I needed to have a WinSCP window open at all times (for copying files across to the CentOS VM) and also a PuTTY terminal (for issuing the compile requests and for executing the resulting binaries).

I settled on this set-up, despite its clunkiness. This, until I heard that Microsoft and Canonical were teaming up to bring the Ubuntu Bash Shell to Windows 10. The potential advantage of this over the setup that I was running with at the time, was that this offers the opportunity to write and compile code for the target environment (Linux), in a non-target environment (Windows) because the Ubuntu layer shares the same file system as the Windows one.

Experimenting with Bash on Ubuntu on Windows

Obtaining a VM running a Windows 10 Preview build

Keen to experiment with this feature, I deployed a Windows 10 VM and got to work, retrieving and installing the latest Windows 10 Insider preview build.

NOTE: I’ll be using RDP to connect to the machine so I had to allow remote connections, which were disabled by default on my VM (press WinKey > type “allow remote” >  select Allow remote access to your computer > select Remote Desktop group > check “Allow remote connections to this computer” > press OK).

Register your machine for preview builds

In order get the preview build, I simply went onto the Windows 10 Insider page, clicked on the Get Started link and filled out the necessary information. I promptly received an email from Microsoft which contained instructions on how to obtain the latest preview build.

I’ve documented them here:

  • On your Windows 10 PC, click Settings>Update & security>Windows Update>Advanced options>Get Insider builds>Get Started, then follow the instructions on the screen to get your PC ready for Insider Preview builds.

insider

insider-get-started

insider-sign-in

insider-warning

This was simple enough, although I should add that after initially providing my details, I had to click Get Started again in Settings>Update & security>Windows Update>Advanced options>Get Insider builds. This may be because I was actually signed into the Windows 10 session with different credentials to those that I signed up to the Insider program with.

Set the preview build frequency

  • Once your PC restarts, you can revisit Windows Update>Advanced options to choose how often you’ll get new Windows Insider Preview builds.

insider-fast-ring

When the machine had rebooted, I logged back in, but this time with the Insider credentials from before. I chose the Fast Ring update scheme in Windows Update>Advanced options.

Install the latest preview build

  • Remember to keep your PC turned on and online to get the latest Preview builds.

I was getting frustrated that I wasn’t being offered the Preview build. I Googled around to no avail. I checked again after 10 minutes, then after half an hour, then an hour and again after two hours. Still nothing. The next morning, Preview build updates had been downloaded. I’m not sure of the cause; perhaps it just takes time for the machine to register itself for Preview updates. Whatever the reason, I installed the updates and rebooted the machine.

It took some time to configure the updates during the shutdown/reboot process, but once it was done, I had a Preview build watermark on my desktop.

insider-desktop-watermark

Installing Bash on Ubuntu

I installed Bash as per the instructions on the affiliated following MSDN blog post. In short, I turned on Developer mode, enabled WSL (Windows Subsystems for Linux) and ran the bash command.

developer-mode-on

wsl-on

search-bash

confirm-bash

I now had a proper Bash environment installed on my Windows 10 VM.

search-bash-postinstall

bash

Set up the Bash environment for Development

I needed certain development tools to be available before I could start programming in this environment. These were:

The fact that I was using “apt-get” above in order to retrieve these packages confirms that I am installing “real” Ubuntu binaries to my Bash environment.

Set up the Windows environment for Development

At this stage I was almost ready to get going. All I needed to do now was to retrieve the code I’d already written (from GitHub) and install Atom.

git-clone

git-clone-done

ls-programminc-etc

vim-hello-word

hello-world-atom

Conclusion

I’ve spent a lot of time playing with environments and tools whilst trying to learn to program in C and this looks like it has the potential to beat all of them. I should say that there is one alternative that I am yet to explore fully in Cygwin.

Cygwin is a much older approach and provides a similar bash environment for Windows with the caveat that native Linux binaries cannot be run. I can install e.g. Git, but it has to be recompiled for this environment, whereas in the Bash on Ubuntu on Windows environment, I can just grab the “real” Linux binaries from a package manager like apt-get.

I’ve also been looking at becoming more adept in the Vim text editor, having discovered the wonderful vimtutor application.

The only negative I’ve faced so far is in the performance of the VM once Atom and the rest of the development applications are running (it slows, badly). Our VM environment is not really optimised for development or high performance. It is mainly there for testing our software. We normally deploy a template, install the software under test, perform the tests and then destroy the machine.

One thing that I have enjoyed about it though, is unlike the text/graphics on the Windows 7 and Windows XP VMs on our system, the text/graphics on the Windows 10 VMs are rendered cleanly and fairly crisply. This means that working in a Windows 10 VM environment, visually, is far more pleasurable than on Windows 7 and Windows XP. It’s just a shame about the performance.

For the time being, I am going to try to persist with Vim in the Bash shell rather than Atom. I intend to report back in a few weeks, by which time, Bash on Ubuntu on Windows may have been released into the main update stream for Windows 10, at which point I’ll be more prepared to deploy it onto a bare metal machine.