Class 02 Notes

Bits & Bytes

- Why do computers use binary representations?

ENIAC (1946) used decimal represenation.  Could store 20 numbers of 10
digits each.  This required 20 X 10 X 10 X 2 = 4000 vacuum tubes.

Overall, machine had 19,000 tubes, 1,500 relays.  Consumed 174 kilowatts.

Bistable element: Simple to build from low quality components.

- Byte oriented memory organization

Provide user with image that memory is contiguous range of bytes

IA32 Linux: 0 to 3 X 2^30-1 (3 Gigabytes)
x86-64 Linux: 0 to 2^48-1   (256 Terabytes)

In reality, complex system to support this image.  Not all bytes are
really there.  Done on per-process basis.  Some sharing of read-only info.

Compiler + run-time system manages allocation:

Static, stack, heap
Read/Write/Execute

Use Hexadecimal to represent numbers 0-15.  Hint: memory A, C, F

Do some examples

- Look at some examples

Use GDB to examine parts of program hello.c:

  gcc -O2 -g hello.c -o hello
 
Look at variable buf.
  Stored at address 'print /x &buf'
  Determine entries with 'print /x buf'
     or 'x/8b buf'  See that it contains reversed bytes of two entries
  See strings in buf with 'x/8b buf[0]'

  H  e  l  l  o  \0
 48 65 6c 6c 6f  0   (ASCII representation)

Examine object code
  Disassemble with objdump -d hello(.exe) > hello.d
  Look at code for main.
  Compare to gdb 

Byte Ordering
  Little Endian: LSB at lowest address

  Little Endian: DEC, Intel
  Big Endian: IBM, Sun, Motorola

  (Many chips can go either way)
 
  Advantages: Little Endian more logical.  Big Endian prints better

  Show examples with show_bytes.c

Boolean Algebra

  History: Developed by George Boole.
  Applied by Claude Shannon, 1937 (relay networks)

  Basic operators: And/Or/Not
  
  Relationship to rings

  Compare ({0,1}^w,|,&,~,0,1) with ({0,2^{w-1}-1},+,*,-,0,1) & with

  Sets of same cardinality

  a|b = b|a              a+b = b+a
  a&b = b&a              a&b = b&a
  a|(b|c) = (a|b)|c      a+(b+c) = (a+b)+c

  ...

  a|(b&c) = a|b & b|c	 NO
  a&a = a                NO

  NO			 a+(-a) = 0
  Sets of same cardinality

Compare ({0,1}^w,^,&,~,0,1) with ({0,2^{w-1}-1},+,*,-,0,1) & with

  a^b = b^a              a+b = b+a
  a&b = b&a              a&b = b&a
  a^(b^c) = (a^b)^c      a+(b+c) = (a+b)+c

  ...

  a|(b&c) = a|b & b|c	 NO
  a&a = a                NO

  NO			 a+(-a) = 0

  Bit-wise versions

  Algebra: And/Xor/Not
    This is a ring
  
Interesting application: DES

Split word W into two parts  L_0, R_0

On each step:
   L_i = R_{i-1}
   R_i = L_{i-1} ^ F(R_{i-1}, K_i)

   Where: K_i is a subset of the bits chosen from a larger key
	  F(X,Y) is a function that generates a (pseudo) random bit pattern

Do this for 16 steps

Inversion:
  R_{i-1} = L_{i}
  L_{i-1} = R_i ^ F(R_{i-1}, K_i)  (Xor inverse property)
          = R_i ^ F(L_{i}, K_i)