Everything is bits#

Representing & Manipulating Sets#

Shift Operations#

Representation: unsigned and signed#

Conversion, casting#

Mappings between unsigned and two’s complement numbers keep bit representations and reinterpret.

For example, casting a signed value to its unsigned form, the most significant bit from large negative weight becomes to large positive weight and vice versa.

Expanding, truncating#

Addition, negation, multiplication, shifting#

1
int s, t, u, v;
2

3
s = (int)((unsigned)u + (unsigned)v);
4
t = u + v;
5

6
// will give s == t

Handy tricks#

If you want convert a value $u$ to its negative form by hand or in mind, either unsigned or signed.

Just do: $\sim u+1$

When Should I Use Unsigned ?#

CAUTION

Don’t use without understanding implications!

• Do use when performing modular arithmetic
  • Multiplication arithmetic
• Do use when using bits to represent sets
  • Logical right shift, no sign extension

Byte-Oriented Memory Organization#

• Programs refer to data by address
  • Conceptually, envision it as a very large array of bytes
    • In reality, it’s not, but can think of it that way
  • An address is like an index into that array
    • and, a pointer variable stores an address
• System provides private address spaces to each “process”
  • So, a program can clobber its own data, but not that of others

Machine Words#

• Any given computer has a “Word Size”
  • Nominal size of integer-valued data
    • and of addresses
  • Until recently, most machines used 32 bits (4 bytes) as word size
    • Limits addresses to 4 GB ($2^{32}$ bytes)
  • Increasingly, machines have 64‐bit word size
    • Potentially, could have 18 EB (exabytes) of addressable memory
    • That’s $18.4\times 10^{18}$ bytes
  • Machines still support multiple data formats
    • Fractions or multiples of word size
    • Always integral number of bytes

Word‐Oriented Memory Organization#

• Addresses Specify Byte Locations
  • Address of first byte in word
  • Addresses of successive words differ by 4 (32‐bit) or 8 (64‐bit)

Byte Ordering#

• Big Endian: Sun, PPC Mac, Internet
  • Least significant byte has highest address
• Little Endian: x86, ARM processors running Android, iOS, and Windows
  • Least significant byte has lowest address

Representation Strings#

In C, either little endian or big endian machine, strings in memory represented in the same way, because a string is essentially an array of characters ends with \x00, each character is one byte encoded in ASCII format and single byte (character) do not obey the byte ordering rule.

Representing#

• Bits to right of “binary point” represent fractional powers of 2
• Represents rational number: $\displaystyle \sum _{k=-j}^{i} b_{k} \cdot 2^{k}$

Observations#

• Divide by 2 by shifting right (unsigned)
• Multiply by 2 by shifting left
• Numbers of form $0.111111\dots_{2}$ are just below $1.0$
  • $\displaystyle \frac{1}{2} +\frac{1}{4} +\frac{1}{8} +\dots+\frac{1}{2^{i}} +\dots\rightarrow 1.0$
  • Use notation $1.0−\epsilon$ ($\epsilon$ depends on how many bits you have to the right of the binary point. If it gets smaller the more, the more of those bits you have there, and it gets closer to $1$)

Limitation 1#

• Can only exactly represent numbers of the form $\displaystyle\frac{x}{2^{k}}$
  • Other rational numbers have repeating bit representations, but cause computer system can only hold a finite number of bits, so $0.1+0.2\neq 0.3$

Limitation 2#

• Just one setting of binary point within the $w$ bits
  • Limited range of numbers (very small values ? very large ? we have to move the binary point to represent sort of wide as wide a range as possible with as much precision given the number of bits)

IEEE Standard 754#

Established in 1985 as uniform standard for floating point arithmetic. Before that, many idiosyncratic formats.

Although it provided nice standards for rounding, overflow, underflow… It is hard to make fast in hardware (Numerical analysts predominated over hardware designers in defining standard)

Encoding#

• MSB s is sign bit $s$
• exp field encodes $E$ (but is not equal to $E$)
• frac field encodes $M$ (but is not equal to $M$)

1
# manually calculate
2
((-1)**0)*(1+1/2+1/4+1/16+1/32+1/128+1/256+1/1024+1/2048+1/8192)*(2**13) == 15213.0
3

4
# by struct package
5
import struct
6

7
bits = 0b01000110011011011011010000000000
8
f = struct.unpack("f", struct.pack("I", bits))[0]
9

10
print(f)

Visualization: Floating Point Encodings#

Example and properties#

Special Properties of the IEEE Encoding#

• Floating Point Zero Same as Integer Zero
  • All bits = 0
• Can (Almost) Use Unsigned Integer Comparison
  • Must first compare sign bits
  • Must consider $-0=0$
  • NaNs problematic
    • What should comparison yield ?
  • Otherwise OK
    • Denormalized vs. Normalized
    • Normalized vs. Infinity

Floating Point Operations: Basic Idea#

$x+_{f} y=round( x+y)$

$x\times _{f} y=round( x\times y)$

Rounding#

Rounding Modes (illustrate with $ rounding)

Round to Even

It means, if you have a value that’s less than half way then you round down, if more than half way, round up. When you have something that’s exactly half way, then what you do is round towards the nearest even number.

Floating Point Multiplication#

$( -1)^{s_{1}} \cdot M_{1} \cdot 2^{E_{1}} \cdot ( -1)^{s_{2}} \cdot M_{2} \cdot 2^{E_{2}} =( -1)^{s} \cdot M \cdot 2^{E}$

• Sign $s$ is $s_{1}$^$s_{2}$
• Significand $M$ is $M_{1} \cdot M_{2}$
• Exponent $E$ is $E_{1}+E_{2}$

Floating Point Addition#

$( -1)^{s_{1}} \cdot M_{1} \cdot 2^{E_{1}} +( -1)^{s_{2}} \cdot M_{2} \cdot 2^{E_{2}} =( -1)^{s} \cdot M \cdot 2^{E}$ (Assume $E_{1}>E_{2}$)

• Sign $s$, significand $M$
  • Result of signed align & add
• Exponent $E$
  • $E_{1}$

Mathematical Properties of Floating Point Add#

• Compare to those of Abelian Group
  • Closed under addition ? (Yes)
    • But may generate infinity or NaN
  • Commutative ? (Yes)
  • Associative ? (No)
    • Overflow and inexactness of rounding
    • (3.14+1e10)-1e10 = 0, 3.14+(1e10-1e10) = 3.14
  • $0$ is additive identity ? (Yes)
  • Every element has additive inverse ? (Almost)
    • Except for infinities & NaNs
• Monotonicity
  • $a\geqslant b\Rightarrow a+c\geqslant b+c$ ? (Almost)
    • Except for infinities & NaNs

Mathematical Properties of Floating Point Mult#

• Compare to Commutative Ring
  • Closed under multiplication ? (Yes)
    • But may generate infinity or NaN
  • Multiplication Commutative ? (Yes)
  • Multiplication is Associative ? (No)
    • Possibility of overflow, inexactness of rounding
    • (1e20*1e20)*1e-20 = inf, 1e20*(1e20*1e-20) = 1e20
  • $1$ is multiplicative identity ? (Yes)
  • Multiplication distributes over addition ? (No)
    • Possibility of overflow, inexactness of rounding
    • 1e20*(1e20-1e20) = 0.0, 1e20*1e20-1e20*1e20 = NaN
• Monotonicity
  • $a\geqslant b\ \&\ c\geqslant 0\Rightarrow a\cdot c\geqslant b\cdot c$ ? (Almost)
    • Except for infinities & NaNs

Conversions / Casting#

CAUTION

Casting between int, float, and double changes bit representation!

• double/float to int
  • Truncates fractional part
  • Like rounding toward zero
  • Not defined when out of range or $NaN$: Generally sets to $TMin$
• int to double
  • Exact conversion, as long as int has $\leqslant 53$ bit word size
• int to float
  • Will round according to rounding mode

Definitions#

• Architecture: (also ISA: instruction set architecture) The parts of a processor design that one needs to understand or write assembly/machine code
  • Examples: instruction set specification, registers
• Microarchitecture: Implementation of the architecture
  • Examples: cache sizes and core frequency

Assembly / Machine Code View#

Turning C into Object Code#

• Code in files p1.c p2.c
• Compile with command: gcc -Og p1.c p2.c -o p
  • Use basic optimizations (-Og) [New to recent versions of GCC]
  • Put resulting binary in file p

Assembly Characteristics: Data Types#

• “Integer” data of 1, 2, 4 or 8 bytes
  • Data values
  • Address (untyped pointers)
• Floating Point data of 4, 8 or 10 bytes
• Code: Byte sequences encoding series of instructions
• No aggregate types such as arrays or structures
  • Just contiguously allocated bytes in memory

Assembly Characteristics: Operations#

• Perform arithmetic function on register or memory data
• Transfer data between memory and register
  • Load data from memory into register
  • Store register data into memory
• Transfer control
  • Conditional branches
  • Unconditional jumps to/from procedures

Object Code#

• Assembler
  • Translates .s into .o
  • Binary encoding of each instruction
  • Nearly-complete image of executable code
  • Missing linkages between code in different files
• Linker
  • Resolves references between files
  • Combines with static run-time libraries
    • E.g., code for malloc, printf
  • Some libraries are dynamically linked
    • Linking occurs when program begins execution

x86‐64 Integer Registers#

Moving Data#

• movq src, dst
• Operand Types
  • Immediate: Constant integer data
    • E.g., $0x400, $-533
    • Like C constant, but prefixed with $
    • Encoded with 1, 2, or 4 bytes
  • Register: One of 16 integer registers
    • E.g., %rax, %r13
    • But %rsp reserved for special use
    • Others have special uses for particular instructions
  • Memory: 8 consecutive bytes of memory at address given by register
    • Simplest example: (%rax)
    • Various other “address modes”

Complete Memory Addressing Modes#

• D(Rb, Ri, S), Mem[Reg[Rb] + S * Reg[Ri] + D]
  • D: Constant “displacement” 1, 2, or 4 bytes
  • Rb: Base register: Any of 16 integer registers
  • Ri: Index register: Any, except for %rsp
  • S: Scale (1, 2, 4, or 8)
• Special Cases
  • (Rb, Ri): Mem[Reg[Rb] + Reg[Ri]]
  • D(Rb, Ri): Mem[Reg[Rb] + Reg[Ri] + D]
  • (Rb, Ri, S): Mem[Reg[Rb] + S * Reg[Ri]]

Address Computation Instruction#

• leaq src, dst
  • src is address mode expression
  • Set dst to address denoted by expression
• Uses
  • Computing addresses without a memory reference
    • E.g., translation of p = &x[i];
  • Computing arithmetic expressions of the form x + k * y
    • k equals to 1, 2, 4, or 8

Here is an example of computing arithmetic expression with leaq:

1
long m12(long x) {
2
  return x * 12;
3
}

Converted to ASM by compiler:

1
leaq (%rdi, %rdi, 2), %rax # t <- x + x * 2
2
salq $2, %rax              # return t << 2

A bit more complex one:

1
long arith(long x, long y, long z) {
2
  long t1 = x + y;
3
  long t2 = z + t1;
4
  long t3 = x + 4;
5
  long t4 = y * 48;
6
  long t5 = t3 + t4;
7
  long rval = t2 * t5;
8

9
  return rval;
10
}

1
arith:
2
  leaq (%rdi, %rsi), %rax     # t1
3
  addq %rdx, %rax             # t2
4
  leaq (%rsi, %rsi, 2), %rdx
5
  salq $4, %rdx               # t4
6
  leaq 4(%rdi, %rdx), %rcx    # t5
7
  imulq $rcx, %rax            # rval
8
  ret

Condition Codes (Implicit Setting)#

Think of it as a side effect by arithmetic operations.

leaq won’t effect flags.

Condition Codes (Explicit Setting)#

• Compare Instrucion
  • cmpq src2, src1: computing src1 - src2 without setting destination
• Test Instruction
  • testq src2, src1: computing src1 & src2 without setting destination
  • Useful to have one of the operands be a mask

Reading Condition Codes#

• setX Instructions
  • Set low‐order byte of destination (must one of addressable byte registers) to 0 or 1 based on combinations of condition codes
  • Does not alter remaining 7 bytes
    • Typically use movzbl (Move with Zero-Extend from Byte to Long) to finish job
      • 32‐bit instructions also set upper 32 bits to 0

NOTE

Any computation where the result is a 32-bit result, it will zero out the higher 32-bits of the register. And its different for example the byte level operations only affect the bytes, the word operations only affect two bytes.

NOTE

sil, dil, spl, bpl are all 1 byte registers.

1
int gt(long x, long y) {
2
  return x > y;
3
}

1
cmpq   %rsi, %rdi # Compare x:y
2
setg   %al        # Set %al to 1 when >
3
movzbl %al, %eax  # Zero rest of %rax
4
ret

Jumping#

• jX Instructions
  • Jump to different part of code depending on condition codes

Using Conditional Moves#

• Conditional Move Instructions
  • Instruction supports: if (Test) Dest <- Src
  • Supported in post-1995 x86 processors
  • GCC tries to use them (but, only when known to be safe)
    • Branches are very disruptive to instruction flow through pipelines
    • Conditional moves do not require control transfer

Here is a simple example of conditional move:

1
long absdiff(long x, long y) {
2
  long result;
3
  if (x > y)
4
    result = x - y;
5
  else
6
    result = y - x;
7
  return result;
8
}

1
absdiff:
2
  movq   %rdi, %rax # x
3
  subq   %rsi, %rax # result = x - y
4
  movq   %rsi, %rdx
5
  subq   %rdi, %rdx # eval = y - x
6
  cmpq   %rsi, %rdi # x:y
7
  cmovle %rdx, %rax # if <=, result = eval
8
  ret

”Do-While” Loop#

C Code:

1
long pcount_do(unsigned long x) {
2
  long result = 0;
3
  do {
4
    result += x & 0x1;
5
    x >>= 1;
6
  } while (x);
7
  return result;
8
}

Goto Version:

1
long pcount_goto(unsigned long x) {
2
  long result = 0;
3
loop:
4
  result += x & 0x1;
5
  x >>= 1;
6
  if (x) goto loop;
7
  return result;
8
}

Assembly Code:

1
  movl $0, %eax   # result = 0
2
.L2:              # loop:
3
  movq %rdi, %rdx
4
  andl $1, %edx   # t = x & 0x1
5
  addq %rdx, %rax # result += t
6
  shrq %rdi       # x >>= 1
7
  jne  .L2        # if (x) goto loop
8
  rep; ret

1
do {
2
  Body
3
} while (Test);

1
loop:
2
  Body
3
  if (Test)
4
    goto loop

”While” Loop#

1
while (Test) {
2
  Body
3
}

1
  goto test
2
loop:
3
  Body
4
test:
5
  if (Test)
6
    goto loop
7
done:

1
while (Test) {
2
  Body
3
}

1
  if (!Test)
2
    goto done;
3
  do {
4
    Body
5
  } while (Test);
6
done:

1
  if (!Test)
2
    goto done;
3
loop:
4
  Body
5
  if (Test)
6
    goto loop;
7
done:

”For” Loop#

1
for (Init; Test; Update)
2
  Body

1
Init;
2
while (Test) {
3
  Body
4
  Update;
5
}

Switch Statement Example#

1
long switch_eg(long x, long y, long z) {
2
  long w = 1;
3
  switch (x) {
4
    case 1:
5
      w = y * z;
6
      break;
7
    case 2:
8
      w = y / z;
9
    /* Fall Through */
10
    case 3:
11
      w += z;
12
      break;
13
    case 5:
14
    case 6:
15
      w -= z;
16
      break;
17
    default:
18
      w = 2;
19
    }
20
  return w;
21
}

• Multiple case labels: 5 & 6
• Fall through cases: 2
• Missing cases: 4

Switch Statement Example in Assembly#

1
switch_eg:
2
  movq %rdx, %rcx
3
  cmpq $6, %rdi        # x:6
4
  ja   .L8             # use default
5
  jmp  *.L4(, %rdi, 8) # goto *JTab[x]

Note that w not initialized here.

TIP

ja .L8 considering the result is unsigned, so its a smart way to tackle negative number.

Jump Table Structure#

1
.section .rodata
2
  .align 8
3
.L4:
4
  .quad .L8 # x = 0
5
  .quad .L3 # x = 1
6
  .quad .L5 # x = 2
7
  .quad .L9 # x = 3
8
  .quad .L8 # x = 4
9
  .quad .L7 # x = 5
10
  .quad .L7 # x = 6

Stack Structure#

Calling Conventions#

Register Saving Conventions#

• Caller Saved
  • Caller saves temporary values in its frame before the call
• Callee Saved
  • Callee saves temporary values in its frame before using
  • Callee restores them before returning to caller

Recursion Example#

1
long pcount_r(unsigned long x) {
2
  if (x == 0)
3
    return 0;
4
  else:
5
    return (x & 1) + pcount_r(x >> 1);
6
}

1
pcount_r:
2
  movl  $0, %eax
3
  testq %rdi, %rdi
4
  je    .L6
5
  pushq %rbx
6
  movq  %rdi, %rbx
7
  andl  $1, %ebx
8
  shrq  %rdi
9
  call  pcount_r
10
  addq  %rbx, %rax
11
  popq  %rbx
12
.L6:
13
  rep; ret

• Handled Without Special Consideration (just using normal calling conventions)
  • Stack frames mean that each function call has private storage
    • Saved registers & local variables
    • Saved return pointer
  • Register saving conventions prevent one function call from corrupting another’s data
    • Unless the C code explicitly does so
  • Stack discipline follows call / return pattern
    • If P calls Q, then Q returns before P
    • Last-In, First-Out
• Also works for mutual recursion
  • P calls Q; Q calls P

One-dimensional Array#

1
#define ZLEN 5
2

3
typedef int zip_dig[ZLEN];
4

5
int get_digit(zip_dig z, int digit) {
6
  return z[digit];
7
}

1
movl (%rdi, %rsi, 4), %eax # z[digit]

1
void zincr(zip_dig z) {
2
  size_t i;
3
  for (i = 0; i < ZLEN; i++) {
4
    z[i]++;
5
  }
6
}

1
  movl $0, %eax            # i = 0
2
  jmp .L3                  # goto middle
3
.L4:                       # loop:
4
  addl $1, (%rdi, %rax, 4) # z[i]++
5
  addq $1, %rax            # i++
6
.L3:                       # middle
7
  cmpq $4, %rax            # i:4
8
  jbe .L4                  # if <=, goto loop
9
  rep; ret

Multidimensional (Nested) Arrays#

• T A[R][C]
  • 2D array of data type T
  • R rows, C columns
  • Type T element requires K bytes
• Array Size
  • R * C * K bytes
• Arrangement
  • Row-Major Ordering

1
#define ZLEN 5
2
#define PCOUNT 4
3

4
typedef int zip_dig[ZLEN];
5

6
zip_dig pgh[PCOUNT] = {
7
  {1, 5, 2, 0, 6},
8
  {1, 5, 2, 1, 3},
9
  {1, 5, 2, 1, 7},
10
  {1, 5, 2, 2, 1}
11
}

1
int *get_pgh_zip(int index) {
2
  return pgh[index];
3
}

1
leaq (%rdi, %rdi, 4), %rax # 5*index
2
leaq pgh(, %rax, 4), %rax  # pgh + (20*index)

1
int get_pgh_digit(int index, int dig) {
2
  return pgh[index][dig];
3
}

1
leaq (%rdi, %rdi, 4), %rax # 5*index
2
addl %rax, %rsi            # 5*index + dig
3
movl pgh(, %rsi, 4), %eax  # M[pgh + 4*(5*index + dig)]

Multi-Level Array#

1
zip_dig cmu = {1, 5, 2, 1, 3};
2
zip_dig mit = {0, 2, 1, 3, 9};
3
zip_dig ucb = {9, 4, 7, 2, 0};
4

5
#define UCOUNT 3
6

7
int *univ[UCOUNT] = {mit, cmu, ucb};

• Variable univ denotes array of 3 elements
• Each element is a pointer (8 bytes)
• Each pointer points to array of int’s

1
int get_univ_digit(size_t index, size_t digit) {
2
  return univ[index][digit];
3
}

1
salq $2, %rsi              # 4*digit
2
addq univ(, %rdi, 8), %rsi # p = univ[index] + 4*digit
3
movl (%rsi), %eax          # return *p
4
ret

N x N Matrix#

• Fixed dimensions
  • Know value of N at compile time

1
#define N 16
2

3
typedef int fix_matrix[N][N];
4

5
/* Get element A[i][j] */
6
int fix_ele(fix_matrix A, size_t i, size_t j) {
7
  return A[i][j];
8
}

• Variable dimensions, explicit indexing
  • Traditional way to implement dynamic arrays

1
#define IDX(n, i, j) ((i)*(n)+(j))
2

3
/* Get element A[i][j] */
4
int vec_ele(size_t n, int *A, size_t i, size_t j) {
5
  return A[IDX(n,i,j)];
6
}

• Variable dimensions, explicit indexing
  • Now supported by gcc

1
/* Get element A[i][j] */
2
int var_ele(size_t n, int A[n][n], size_t i, size_t j) {
3
  return A[i][j];
4
}

1
/* Get element A[i][j] */
2
int var_ele(size_t n, int A[n][n], size_t i, size_t j) {
3
  return A[i][j];
4
}

1
imulq %rdx, %rdi           # n*i
2
leaq (%rsi, %rdi, 4), %rax # A + 4*n*i
3
movl (%rax, %rcx, 4), %eax # A + 4*n*i + 4*j
4
ret

Understanding Pointers & Array#

• Cmp: Compiles (Y/N)
• Bad: Possible bad pointer reference (Y/N)
• Size: Value returned by sizeof

Allocation#

• Structure represented as block of memory
  • Big enough to hold all of the fields
• Fields ordered according to declaration
  • Even if another ordering could yield a more compact representation
• Compiler determines overall size + positions of fields
  • Machine-level program has no understanding of the structures in the source code

Access#

Generating Pointer to Structure Member#

1
struct rec {
2
  int a[4];
3
  size_t i;
4
  struct rec *next;
5
};
6

7
int *get_ap(struct rec *r, size_t idx) {
8
  return &r->a[idx];
9
}

1
leaq (%rdi, %rsi, 4), %rax
2
ret

• Offset of each structure member determined at compile time
• Compute as r + 4*idx

1
struct rec {
2
  int a[4];
3
  int i;
4
  struct rec *next;
5
};
6

7
void set_val(struct rec *r, int val) {
8
  while (r) {
9
    int i = r->i;
10
    r->a[i] = val;
11
    r = r->next;
12
  }
13
}

1
.L11:                        # loop:
2
  movslq 16(%rdi), %rax      # i = M[r + 16]
3
  movl %esi, (%rdi, %rax, 4) # M[r + 4*i] = val
4
  movq 24(%rdi), %rdi        # r = M[r + 24]
5
  testq %rdi, %rdi           # Test r
6
  jne .L11                   # if != 0 goto loop