CS代写 CMPSC 311 – Introduction to Systems Programming

CMPSC 311 – Introduction to Systems Programming
Bit/Byte Operations
Professors
Sencun Zhu and (Slides are mostly by Professor Patrick McDaniel

Copyright By PowCoder代写 加微信 powcoder

and Professor Abutalib Aghayev)
CMPSC 311 – Introduction to Systems Programming

Number Systems
• All base-X systems have the following characteristic:
Base-10 (decimal)
• Digits: 0,1,2,3,4,5,6,7,8,9
Base-2(binary)
• Digits: 0,1
• Place values: 2
• Example: 1011 = 1×1+1×2+0x4+1×8
Base-16 (hexadecimal)
• Digits: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F • Place values: 160 , 161, 162, …
• Example: 0xAFC = Cx1+Fx16+Ax256
• Place values: 10
• Example: 123 = 3×1+2×10+1×100
CMPSC 311 – Introduction to Systems Programming

Converting Decimal to Binary
• while n != 0:
• next binary digit (from right to left) = n % 2 • n = n /2
235 (base-10) = 11101011 (base-2)
CMPSC 311 – Introduction to Systems Programming

Converting Decimal and Binary to Hex
• Converting decimal to hexadecimal • while n != 0:
• next hex digit (from right to left) = n % 16 • n = n / 16
235 (base-10) = EB (base-16)
• Converting binary to hexadecimal
• group binary digits to into groups of 4 bits (nibbles) starting from right • Convert each nibble to hexadecimal digit
235 (base-10) = 11101011 (base-2) = 1110 1011 = EB
• Be familiar with hex notation: 0xDEADBEEF has 8 nibbles, 4 bytes (or octets) • Hexadecimal to binary: just convert each nibble to binary
CMPSC 311 – Introduction to Systems Programming

Conversion Summary
• Binary to decimal
• sum of binary digits times powers of 2
• Hexadecimal to decimal
• sum of hex digits times power of 16
• Decimal to binary • division method
• Decimal to hex
• division method
• or, convert to binary and use binary to hex method below
• Binary to hex
• group binary digits to nibbles, convert nibbles to hex digits
• Hex to binary
• convert each hex digit to binary
CMPSC 311 – Introduction to Systems Programming

Byte Ordering Example
• How should bytes within a multi-byte word be ordered in memory? • Big Endian: Least significant byte has highest address (SPARC)
• Little Endian: Least significant byte has lowest address (x86)
• Example: int x = 305419896
• Variable x has 4-byte representation 0x12345678 • Address given by &x is 0x100
Big Endian Little Endian
0x100 0x101 0x102 0x103
0x100 0x101 0x102 0x103
CMPSC 311 – Introduction to Systems Programming

Examining Data Representations
• Code to find endianness of the architecture • Casting pointer to uint8_t * creates byte array
#include < Result (Linux on x86): int main(void) { int a = 305419896; #include < (uint8_t *start, int show_bytes (“a lives at address %p printf directives %p Print pointer %x Print hexadecimal show_bytes ((uint8_t *)&a, a lives at address 0x7ffebf803174 0x7ffebf803174 0x78 0x7ffebf803175 0x56 0x7ffebf803176 0x34 0x7ffebf803177 0x12 CMPSC 311 - Introduction to Systems Programming Boolean Algebra • Developed by in 19th Century • Algebraic representation of logic that based on “True” (as 1) and “False” (as 0) A&B = 1 when both A=1 and B=1 ~A = 1 when A=0 A|B = 1 when either A=1 or B=1 Exclusive-Or (Xor) A^B = 1 when either A=1 or B=1, but not both CMPSC 311 - Introduction to Systems Programming Bit-Level Operations in C • Operations &, |, ~, ^ Available in C • Apply to any “integral” data type • long, int, short, char, unsigned • View arguments as bit vectors • Argumentsappliedbit-wise • Examples (Char data type) • ~0x41 ➙ 0xBE • ~010000012 ➙ 101111102 • ~0x00 ➙ 0xFF • ~000000002 ➙ 111111112 • 0x69 & 0x55 ➙ 0x41 • 011010012 & 010101012 ➙ 010000012 • 0x69 | 0x55 ➙ 0x7D • 011010012 | 010101012 ➙ 011111012 CMPSC 311 - Introduction to Systems Programming Contrast: Logic Operations in C • Contrast to Logical Operators (&&, ||, !) • View 0 as “False” • Anything nonzero as “True” • Always return 0 or 1 • Earlytermination CMPSC 311 - Introduction to Systems Programming Representing & Manipulating Sets • Representation • Width w bit vector represents subsets of {0, ..., w–1} for set “A” • aj=1 if j∈A { 0, 2, 4, 6 } { 0, 3, 5, 6 } Operations On Sets: & Intersection |Union ^ Symmetric difference ~ Complement 01000001 { 0, 6 } 01111101 {0,2,3,4,5,6} 00111100 { 2, 3, 4, 5 } 10101010 { 1, 3, 5, 7 } CMPSC 311 - Introduction to Systems Programming Representing Signed Numbers One’s complement Two’s complement 7 = 2n-1 – 1 • Computing one’s complement negative representation: • Complement the positive number • Computing two’s complement negative representation: • Complement the positive number and add 1 • Most architectures use two’s complement • Given n-bit signed integer: • Positive range: 0 – 2n-1 -1 • Negative range: -2n-1 -8 = -2n-1 [-32768,32767] unsigned short int [-214748648, 2147483647] [0, 65535] CMPSC 311 - Introduction to Systems Programming unsigned int [0, 4294967295] [-2147483648, long int 4 8 %ld Beware of integer overflows • Spot the bug in the following: for (uint32_t n = 10; n >=0; –n) {
printf(“do I ever terminate?\n”);
• What does the following print?
int x = 0xffffffff;
printf(“%d\n”, x);
CMPSC 311 – Introduction to Systems Programming

Shift Operations
• A shift operator (<< or >>) moves bits to the right or left, throwing away bits and adding bits as necessary
X = X << 3; (throw away) Read as this: shift the bits of the value 3 places to the left (“new” bits) CMPSC 311 - Introduction to Systems Programming Putting it all together • Suppose you want to place multiple values in the same 32-bit integer • Value a in least significant byte • Value b in 2nd byte • Value c in 3rd byte • Value d in 4th byte Bits Values CMPSC 311 - Introduction to Systems Programming Using bit operations ... uint32_t pack_bytes(uint32_t a, uint32_t b, uint32_t c, uint32_t d) { // Setup some local values uint32_t retval = 0x0, tempa, tempb, tempc, tempd; tempa = a&0xff; // Make sure you are only getting the bottom 8 bits tempb = (b&0xff) << 8; // Shift value to the second byte tempc = (c&0xff) << 16; // Shift value to the third byte tempd = (d&0xff) << 24; // Shift value to the top byte retval = tempa|tempb|tempc|tempd; // Now combine all of the values // Print out all of the values printf("A: 0x%08x\n", tempa); printf("B: 0x%08x\n", tempb); printf("C: 0x%08x\n", tempc); printf("D: 0x%08x\n", tempd); // Return the computed value return retval; A: 0x00000011 B: 0x00002200 C: 0x00330000 D: 0x44000000 Packed bytes : 0x44332211 printf("Packed bytes : 0x%08x\n", pack_bytes(0x111, 0x222, 0x333, 0x444)); CMPSC 311 - Introduction to Systems Programming 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com