- If you’ve ever sent a large file to a friend, you may have compressed it before doing so. File compression relies on using a smaller number of bytes than normal to represent data. For example, all ASCII characters normally require 8 bits. However, we could actually use fewer bits to represent more common letters like “a,” “e,” and “s.”
- One example of compression is Morse code. In Morse code, every alphabetic letter is represented with a series of dots and dashes. The most common letter “e” is represented by the shortest possible series, a single dot. The letter “t” is represented by a single dash. So if you hear a dot followed by a dash, it must be “et” right? Unfortunately, the letter “a” is represented by a dot followed by a dash, so it can easily be confused with “et.” Morse code does not lend itself easily to decodability, but rather relies on some interpretation on the part of the human decoder.
- In Morse code, the representation of the letter “e” is a prefix for the letter “a.” To avoid confusion, we might consider coming up with an encoding system in which no letter’s representation is a prefix for another letter’s representation. Indeed, David Huffman did just that.
To prepare a string for Huffman coding, we need to analyze the frequencies of letters in it like so:
As before, we want to use a small number of bits for “E” because it appears more frequently than the other letters. Huffman proposes doing so by considering a forest of trees, each of which represents a letter:
Now, we begin to combine these one-node trees starting with the two with the smallest frequencies (“B” and “C” in this case):
- After combining the first two trees, we’ll hereafter represent the letter on the left with the 0 bit and the letter on the right with the 1 bit. Note we could flip this around (1 for the left and 0 for the right) and it wouldn’t matter.
We now have four trees whose root nodes have the frequency values 0.2 (the combination of the frequencies of “B” and “C”), 0.15, 0.2, and 0.45. The two smallest values are 0.15 and 0.2, so we combine those two. It doesn’t matter which 0.2 value we pick, so we’ll pick the one that represents the “B”-“C” tree:
We do this a few more times to end up with a single tree:
- Notice that all the frequencies add up to a total frequency of 1.0.
- To convert each letter into its Huffman representation, we simply traverse the tree. For the letter “E,” we step right just once, so the representation is the number 1. For the letter “A,” we step left once and right once, so the representation is the number 01. “D” is 001, “C” is 0001, “B” is 0000. None of the letter’s representations are a prefix for another letter’s representation!
- Whereas in ASCII, the letters “A” through “E” are all represented by 8 bits, in the encoding we just derived, “E” is represented by 1 bit, “A” is represented by 2 bits, and even maximally, the letters “B” and “C” are represented by 4 bits.
- We can’t simply compress a message with this encoding and send it on its way. We need to send along the logic of the tree so that the recipient of the message can decode it. When we chose 0 and 1 for “B” and “C” in the very first step, we chose arbitrarily. If the recipient were to try to reconstruct this tree, he might instead choose 1 for “B” and 0 for “C.”
- If we need to send the tree along with the message, we should probably only bother compressing the message if it’s fairly large. If the message is only 3 characters long, then we’re going to use more bytes sending along the tree plus the compressed message than we would just by sending the original uncompressed message.
A Huffman node is simple enough to represent in C:
typedef struct node
{
char symbol;
float frequency;
struct node* left;
struct node* right;
}
node;
- Question: what guarantees that no letter is a prefix for another letter in Huffman coding? The letters are always the leaves in a Huffman tree and a leaf cannot lead to another leaf.
How many bits do we need to flip to convert “A” to “a”? Just one, the third from the left:
A 01000001
a 01100001
Previously, we did this conversion using if statements and addition. However, we could also have done it using a single operator, the bitwise “or” operator. Recall that the logical “or” returns true if either of its operands is true. Similarly, the bitwise “or” operator returns 1 if either of its operands is 1. Consider then the result of applying this operator between the following two binary numbers:
01000001
| 00100000
In the leftmost place, 0 “or” 0 gives us 0. In the next place to the right, 1 “or” 0 returns 1. And so on until we get:
01100001
- This is the binary representation of “a.” The bottom number above is what’s called a mask. We thus got “a” by applying this mask to “A.” In C, this would be written as
01000001 | 00100000. The bitwise “or” operator is represented as |, not to be confused with the other “or” operator ||. Actually, we could even write this in C as 'A' | 32.
To go from “a” to “A,” we need to turn a 1 bit to a 0. We simply invert our mask and use the bitwise “and” operator:
01100001
& 11011111
- The bitwise “and” operator, represented by
&, returns 1 only if both operands are 1.
Take a look at a program which converts a user-provided letter to lowercase:
/****************************************************************************
* tolower.c
*
* David J. Malan
* malan@harvard.edu
*
* Converts an uppercase character to lowercase.
*
* Demonstrates bitwise operators.
***************************************************************************/
#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
int main(void)
{
// prompt user for an uppercase character
char c;
do
{
printf("Uppercase character please: ");
c = GetChar();
}
while (c < 'A' || c > 'Z');
// print number in lowercase
printf("%c\n", c | 0x20);
// that's all folks
return 0;
}
- We use a do-while loop to ensure that the user provides us with an uppercase letter. Once we have the letter, we print out the result of applying the “or” operator to it and the number 0x20, the hexadecimal representation of
00100000 or 32. To see how 0x20 represents 00100000, remember that 2 in binary is 0010 and 0 in binary is 0000. Since each hexadecimal digit represents 4 bits, we simply put those two binary numbers side by side and we get 00100000. Hexadecimal is convenient for representing very large numbers. Try for yourself to understand how 0xdf is a hexadecimal representation of the other mask we discussed above, 11011111.
As another demonstration of bitwise operators, check out binary.c:
/****************************************************************************
* binary.c
*
* David J. Malan
* malan@harvard.edu
*
* Displays a number in binary.
*
* Demonstrates bitwise operators.
***************************************************************************/
#include <cs50.h>
#include <stdio.h>
int main(void)
{
// prompt user for number
int n;
do
{
printf("Non-negative integer please: ");
n = GetInt();
}
while (n < 0);
// print number in binary
for (int i = sizeof(int) * 8 - 1; i >= 0; i--)
{
int mask = 1 << i;
if (n & mask)
printf("1");
else
printf("0");
}
printf("\n");
// that's all folks
return 0;
}
- In this program, we prompt the use for a non-negative number. Then we iterate over each of its bits, starting with the 31st, the highest-order and leftmost. On each iteration, we create a new bit mask using
<<, the left bitshift operator. This operator shifts the bits of the left operand by a number equal to the right operand. So we take the integer 1 (represented in binary as 31 0’s followed by a 1) and shift its bits to the left by 31 on the first iteration of the loop. This gives us the integer represented in binary as a 1 followed by 31 0’s. Incidentally, bitshifting a number to the left has the effect of doubling it since each digit represents a power of 2.
- After creating a mask with a 1 in a single digit’s place, writing
n & mask will be true if n has a 1 in that same digit’s place. Otherwise, it will be false. If it’s true, we print out a 1 for that digit’s place and if it’s false, we print out a 0 for that digit’s place.
- Let’s say we wanted to keep track of whether each of 300 students is present in a room. We might consider using an array of
bool. Unfortunately, a bool is represented by 8 bits in C when we really only need 1 bit. If you wanted to decrease the amount of memory required to store your array, you might use bitwise operators to manipulate the individual bits in a byte.
- Question: is there an “exclusive or” operator? Yes, it is represented as
^. It returns true if one and only one of its operands is a 1. There are also the “not” (~) and right bitshift (>>) operators among others.
You open up your web browser and navigate to facebook.com. What’s actually happening? Your computer is communicating with Facebook’s servers via HTTP, hypertext transfer protocol. HTTP is merely a set of conventions which dictate how browsers and servers should interact with each other, much like the set of conventions which dictate how humans interact with humans, e.g. by shaking hands and greeting each other. When your web browser navigates to facebook.com, it’s effectively extending its hand for a handshake along with a message like so:
GET / HTTP/1.1
Host: www.facebook.com
GET / denotes that we’re requesting the homepage. HTTP/1.1 alerts Facebook to the fact that we’re speaking version 1.1 of HTTP. The Host parameter indicates that the particular website we’re asking to access.
- What does Facebook return when we make this request? It returns some HTML (hypertext markup language) source code. We can view this source code by right clicking and selecting “View source” in most major browsers. A lot of this source code is hard for a human to read, but we can parse certain aspects. For example, you can see a number of years which must be the options in the dropdown menu for selecting birth year on sign-up.
- Facebook’s source code might look like a mess, but in fact it’s simply been minified, or optimized for space. The browser will understand it even without the pretty indentation or meaningful variable names, so to save on bytes being transferred from the server, all unnecessary whitespace and extra characters can be cut out. If Facebook gets 1 billion web hits per day, then every extra byte in the source code translates to 1 billion extra bytes that Facebook’s servers have to transfer.
- If we want to see a prettier version of Facebook’s source code, we can go to View->Developer->Developer Tools in Chrome (or something similar in IE or Firefox). This will pop up a window at the bottom of the browser. When we click on the Elements tab, the HTML of Facebook will be presented to us as a tree structure.
The very first line of code in an HTML file is the following:
<!DOCTYPE HTML>
- This just tells the browser that we’re about to present it with some HTML5.
HTML is composed of tags which begin and end with angle brackets. The root tag is <html>. Within that, there are the <head> and <body> tags. Within the <head> tag is the <title> tag, which is responsible for the text that appears in the tab in your browser:
<title id="pageTitle">Welcome to Facebook - Log In, Sign Up or Learn More</title>
As with other programming languages, we’ll write the “hello, world” version of HTML:
<!DOCTYPE html>
<html>
<head>
<title>hello, world</title>
</head>
<body>
hello, world
</body>
</html>
- In general, tags come in pairs: a start and an end. The end tag has a forward slash inside of it. For example,
<html> is the start tag and </html> is the end tag. In HTML, you have to tell the browser when to start doing something and when to stop doing something. If you want text to be bold, you have to tell the browser to start making text bold and to stop making text bold.
- If we take the HTML source code above, copy and paste it into TextEdit on a Mac (or Notepad on Windows or gedit on Linux), and save it as
hello.html, we can drag it into a browser to see the text “hello, world” rendered. This will also be displayed in the tab, as per the <title> tag.
We can spruce up our HTML by linking to two files written in two other languages, CSS and JavaScript:
<!DOCTYPE html>
<html>
<head>
<link href="styles.css" rel="stylesheet"/>
<script src="scripts.js"></script>
<title>hello, world</title>
</head>
<body>
hello, world
</body>
</html>
- The
<link> tag has two attributes, href and rel, which modify its behavior. This tag tells the browser to include a CSS file named styles.css which dictates certain aesthetics. You can think of the <link> tag as the functional equivalent of the #include directive in C. Here, the <script> tag pulls in JavaScript code.
To make some of our text bold, we use the <b> tag:
<!DOCTYPE html>
<html>
<head>
<title>hello, world</title>
</head>
<body>
hello, <b>world</b>
</body>
</html>
Let’s try to add a link to another webpage:
<!DOCTYPE html>
<html>
<head>
<title>hello, world</title>
</head>
<body>
hello, <b>world</b>
my favorite website is youtube.com
</body>
</html>
- The first problem here is that “my” is rendered on the same line as “world.” Just because we hit Enter in our source code doesn’t mean that the browser will interpret that as a newline. To insert a linebreak, we have to insert a
<br/> tag. This tag is an example of a tag that doesn’t come in a pair.
Unfortunately, “youtube.com” isn’t clickable. To make it actually lead to YouTube, we need to use the <a> tag:
<!DOCTYPE html>
<html>
<head>
<title>hello, world</title>
</head>
<body>
hello, <b>world</b>
my favorite website is
<a href="http://www.youtube.com">youtube.com</a>
</body>
</html>
- Already, you have all the tools you need to launch a phishing attack. You can change the value of the
href attribute to something malicious and the clickable text to something innocuous.
