Given that a byte can represent any of the values 0 through 255, anyone could arbitrarily make up a mapping between characters and numbers. For example, a video card manufacturer could decide that 1 represents A, so when value 1 is sent to the video card it displays a capital 'A' on the screen. A printer manufacturer might decide for some obscure reason that 1 represented a lower-case 'z', meaning that complex conversions would be required to display and print the same thing.

To avoid this happening, the American Standard Code for Information Interchange or ASCII was invented. This is a 7-bit code, meaning there are 2⁷ or 128 available codes.

The range of codes is divided up into two major parts; the non-printable and the printable. Printable characters are things like characters (upper and lower case), numbers and punctuation. Non-printable codes are for control, and do things like make a carriage-return, ring the terminal bell or the special NULL code which represents nothing at all.

127 unique characters is sufficient for American English, but becomes very restrictive when one wants to represent characters common in other languages, especially Asian languages which can have many thousands of unique characters.

To alleviate this, modern systems are moving away from ASCII to Unicode, which can use up to 4 bytes to represent a character, giving much more room!

ASCII, being only a 7-bit code, leaves one bit of the byte spare. This can be used to implement parity which is a simple form of error checking. Consider a computer using punch-cards for input, where a hole represents 1 and no hole represents 0. Any inadvertent covering of a hole will cause an incorrect value to be read, causing undefined behaviour.

Parity allows a simple check of the bits of a byte to ensure they were read correctly. We can implement either odd or even parity by using the extra bit as a parity bit.

In odd parity, if the number of 1's in the 7 bits of information is odd, the parity bit is set, otherwise it is not set. Even parity is the opposite; if the number of 1's is even the parity bit is set to 1.

In this way, the flipping of one bit will case a parity error, which can be detected.

XXX more about error correcting

Numbers do not fit into bytes; hopefully your bank balance in dollars will need more range than can fit into one byte! All most all general-purpose architectures are at least 32 bit computers. This means that their internal registers are 32-bits (or 4-bytes) wide, and that operations generally work on 32-bit values. We refer to 4 bytes as a word; this is analogous to language where letters (bits) make up words in a sentence, except in computing every word has the same size! The size of a C int variable is 32 bits. Modern architectures are 64 bits, which doubles the size the processor works with to 8 bytes.

Computers deal with a lot of bytes; that's what makes them so powerful! We need a way to talk about large numbers of bytes, and a natural way is to use the "International System of Units" (SI) prefixes as used in most other scientific areas. So for example, kilo refers to 10³ or 1000 units, as in a kilogram has 1000 grams.

1000 is a nice round number in base 10, but in binary it is 1111101000 which is not a particularly "round" number. However, 1024 (or 2¹⁰) is a round number — (10000000000 — and happens to be quite close to the base 10 meaning value of "kilo" (1000 as opposed to 1024). Thus 1024 bytes naturally became known as a kilobyte. The next SI unit is "mega" for 106 and the prefixes continue upwards by 10³ (corresponding to the usual grouping of three digits when writing large numbers). As it happens, 220 is again close to the SI base 10 definition for mega; 1048576 as opposed to 1000000. Increasing the base 2 units by powers of 10 remains functionally close to the SI base 10 value, although each increasing factor diverges slightly further from the base SI meaning. Thus the SI base-10 units are "close enough" and have become the commonly used for base 2 values.

It can be very useful to commit the base 2 factors to memory as an aid to quickly correlate the relationship between number-of-bits and "human" sizes. For example, we can quickly calculate that a 32 bit computer can address up to four gigabytes of memory by noting that 232 can recombine to 2(2 + 30) or 22 × 230, which is just 4 × 230, where we know 230 is a gigabyte. A 64-bit value could similarly address up to 16 exabytes (24 × 260); you might be interested in working out just how big a number this is. To get a feel for how big that number is, calculate how long it would take to count to 264 if you incremented once per second.

Apart from the confusion related to the overloading of SI units between binary and base 10, capacities will often be quoted in terms of bits rather than bytes. Generally this happens when talking about networking or storage devices; you may have noticed that your ADSL connection is described as something like 1500 kilobits/second. The calculation is simple; multiply by 1000 (for the kilo), divide by 8 to get bytes and then 1024 to get kilobytes (so 1500 kilobits/s=183 kilobytes per second).

The SI standardisation body has recognised these dual uses and has specified unique prefixes for binary usage. Under the standard 1024 bytes is a kibibyte, short for kilo binary byte (shortened to KiB). The other prefixes have a similar prefix (Mebibyte, MiB, for example). Tradition largely prevents use of these terms, but you may seem them in some literature.

The easiest way to convert between bases is to use a computer, after all, that's what they're good at! However, it is often useful to know how to do conversions by hand.

The easiest method to convert between bases is repeated division. To convert, repeatedly divide the quotient by the base, until the quotient is zero, making note of the remainders at each step. Then, write the remainders in reverse, starting at the bottom and appending to the right each time. An example should illustrate; since we are converting to binary we use a base of 2.

Reading from the bottom and appending to the right each time gives 11001011, which we saw from the previous example was 203.

Usually represented by !, not simply inverts the value, so 0 becomes 1 and 1 becomes 0

To remember how the and operation works think of it as "if one input and the other are true, result is true

To remember how the or operation works think of it as "if one input or the other input is true, the result is true

Exclusive or, written as xor is a special case of or where the output is true if one, and only one, of the inputs is true. This operation can surprisingly do many interesting tricks, but you will not see a lot of it in the kernel.

In low level code, it is often important to keep your structures and variables as space efficient as possible. In some cases, this can involve effectively packing two (generally related) variables into one.

Remember each bit represents two states, so if we know a variable only has, say, 16 possible states it can be represented by 4 bits (i.e. 2⁴=16 unique values). But the smallest type we can declare in C is 8 bits (a char), so we can either waste four bits, or find some way to use those left over bits.

We can easily do this by the process of masking. This uses the rules of logical operations to extract values.

The process is illustrated in the figure below. We can keep two separate 4-bit values "inside" a single 8-bit character. We consider the upper four-bits as one value (blue) and the lower 4-bits (red) as another. To extract the lower four bits, we set our mask to have the lower-4 bits set to 1 (0x0F). Since the logical and operation will only set the bit if both bits are 1, those bits of the mask set to 0 effectively hide the bits we are not interested in.

Figure 1.3.2.1.1 Masking

To get the top (blue) four bits, we would invert the mask; in other words, set the top 4 bits to 1 and the lower 4-bits to 0. You will note this gives a result of 1010 0000 (or, in hexadecimal 0xA0) when really we want to consider this as a unique 4-bit value 1010 (0x0A). To get the bits into the right position we use the right shift operation 4 times, giving a final value of 0000 1010.

#include <stdio.h>

#define LOWER_MASK 0x0F
#define UPPER_MASK 0xF0

int main(int argc, char* argv[])
{
        /* Two 4-bit values stored in one
         * 8-bit variable */
        char value = 0xA5;
        char lower = value & LOWER_MASK;
        char upper = (value & UPPER_MASK) >> 4;

        printf("Lower: %x\n", lower);
        printf("Upper: %x\n", upper);
}

Setting the bits requires the logical or operation. However, rather than using 1's as the mask, we use 0's. You should draw a diagram similar to the above figure and work through setting bits with the logical or operation.

Often a program will have a large number of variables that only exist as flags to some condition. For example, a state machine is an algorithm that transitions through a number of different states but may only be in one at a time. Say it has 8 different states; we could easily declare 8 different variables, one for each state. But in many cases it is better to declare one 8 bit variable and assign each bit to flag flag a particular state.

Flags are a special case of masking, but each bit represents a particular boolean state (on or off). An n bit variable can hold n different flags. See the code example below for a typical example of using flags -- you will see variations on this basic code very often.

#include <stdio.h>

/*
 *  define all 8 possible flags for an 8 bit variable
 *      name  hex     binary
 */
#define FLAG1 0x01 /* 00000001 */
#define FLAG2 0x02 /* 00000010 */
#define FLAG3 0x04 /* 00000100 */
#define FLAG4 0x08 /* 00001000 */
/* ... and so on */
#define FLAG8 0x80 /* 10000000 */

int main(int argc, char *argv[])
{
	char flags = 0; /* an 8 bit variable */

	/* set flags with a logical or */
	flags = flags | FLAG1; /* set flag 1 */
	flags = flags | FLAG3; /* set flag 3

	/* check flags with a logical and.  If the flag is set (1)
	 * then the logical and will return 1, causing the if
	 * condition to be true. */
	if (flags & FLAG1)
		printf("FLAG1 set!\n");

	/* this of course will be untrue. */
	if (flags & FLAG8)
		printf("FLAG8 set!\n");

	/* check multiple flags by using a logical or
	 * this will pass as FLAG1 is set */
	if (flags & (FLAG1|FLAG4))
		printf("FLAG1 or FLAG4 set!\n");

	return 0;
}