Lecture 7 Bit Manipulation in System Programming

• CSCI 2122 focuses on bit manipulation in system programming

Key Ideas: Bits and Bytes

• CPU instructions work with registers containing multiple bits (8, 16, 32, 64).
• CPU instructions do not directly handle single bits.
• C and similar languages cannot directly manipulate single bits.
• Bits should be stored in bytes (char) or words (int, long int).
• Bytes/words are manipulated to test, toggle, set, or reset specific bits.

Reading and Writing Bits

• To read a single bit, determine the byte/word containing the bit, load the byte/word from memory, and extract the bit's value.
• To modify a single bit:
• Find the relevant byte or word.
• Load the byte or word from memory.
• Extract the bit value if necessary.
• Alter the byte/word to change the specific bit.
• Write the updated byte/word back to memory.

Bitstreams vs Bitmaps

• A bitstream is a sequence of bits packed into one or more bytes or words.
• Example: char stream[] = {0xb6, 0x57, 0x1c, 0xd0}.
• A bitmap uses bits in bytes to indicate presence or absence of elements in a set, so a 1-bit means item present, 0-bit means item absent.

Real World examples

• TCP header Flags field uses single bits to indicate Boolean states.
• Unix file permissions use a bitmap for read (r), write (w), and execute (x) rights for Owner, Group, and Others.
• RGBA color channels use bits, such as 0xFFFFFF00 for 100% opaque Yellow.

Bit Ordering

• When treating a sequence of bytes as a bitstream, it is important which bit is bit 0
• There is an important differentiation between MSB (Most Significant Bit) and BSB (Least Significant Bit)

MSB vs LSB

• If the MSB of byte 0 is bit 0: bit0 = (bytes[0] >> 7) & 0x1;
• If the LSB of byte 0 is bit 0: bit0 = bytes[0] & 0x1;

Usage of MSB vs LSB

• If specified, follow that specification
• MSB as bit 0 is best for debugging byte streams
• Use LSB as bit 0 if the program uses bitmaps internally

Finding Bits

• In a bitstream/bitmap of n bytes, bit B is in byte B / 8.
• All bytes are the same size
• Example: For the byte array {0xb6, 0x57, 0x1c, 0xd0}, bit 4 is in byte 0 (4 / 8 = 0), bit 30 is in byte 3 (30 / 8 = 3), and bit 17 is in byte 2 (17 / 8 = 2).
• When using words (int or long int), divide by sizeof(word) * 8

Bitmasks Defined

• A bitmask is a byte/word used with bitwise operations to extract/modify a specific bit by "masking" others, with positive and negative types.

Bitmask Types

• Positive bitmask: a 1-bit indicates the bit(s) to extract/modify (e.g., 00100000 or 0x20 to manipulate bit 5).
• Negative bitmask: a 0-bit indicates the bit(s) to modify (e.g., 11011111 or 0xdf to manipulate bit 5).
• A negative mask is the bitwise negation of a positive mask.

Creating Bitmasks

• For bit b, a positive bitmask is created by shifting 1 left b times: 1 << b.
• Example: for bitmask 00100000, char bitmask = 1 << 5;
• A negative bitmask is created by creating a positive mask and negating it: ~(1 << b).
• Example: char bitmask = ~(1 << 5); would create 11011111

Common Operations

• Test(bits, i): returns the value of bit i of bits.
• Set(bits, i): makes bit I of bits to 1.
• Reset(bits, i): makes bit I of bits to 0.
• Toggle(bits, i): flips bit i of bits.
• The operations all compute the target bit's byte/word, the bit's location in the byte/word, the bitmask, and then perform the operation with the bitmask

Test and Set Code

• Is bit 0 the MSB or LSB?
• Test:
• Locate byte of target bit, int idx = b / 8;
• Locate bit in byte, int bidx = b % 8;
• Compute mask to isolate bit, char mask = 1 << bidx;
• Test if the bit is not 0, return bits[idx] & mask != 0;
• Set:
• Locate byte of target bit, int idx = b / 8;
• Locate bit in byte, int bidx = b % 8;
• Compute mask to set bit, char mask = 1 << bidx;
• Set bit to 1 by ORing with the mask, bits[idx] = bits[idx] | mask;

Reset and Toggle Code

• Reset:
• Locate byte of target bit, int idx = b / 8;
• Locate bit in byte, int bidx = b % 8;
• Compute mask to reset bit, char mask = ~(1 << bidx);
• Set bit to 0 by ANDing with mask, bits[idx] = bits[idx] & mask;
• Toggle:
• Locate byte of target bit, int idx = b / 8;
• Locate bit in byte, int bidx = b % 8;
• Compute mask to set bit, char mask = 1 << bidx;
• Set bit to 0 by XORing with mask, bits[idx] = bits[idx] ^ mask;