CSC373/406: Lecture 1 (Binary Representations; Logic)

Course: CSC373/406 (Computer Systems I)

Instructor: James Riely

• Adminstrative information
• Labs pragmatics
• Linux basics
• Computer Systems: Overview
• C Language Introduction

Course homepage: http://fpl.cs.depaul.edu/jriely/class/373/publish

• Lecture slides are available in two HTML formats: one slide per page and all slides on one page.
• Lecture slides may not be available before the class.
• Lecture slides may change after class.

http://groups.google.com/group/csc373spring2012

• I will reply to messages I receive to the course mailing list.
• The mailing list is archived.
• If you do not wish to receive messages, you may unsubscribe, or subscribe to a digest.

93-100 = A
90-92  = A-
88-89  = B+
83-87  = B
80-82  = B-        
etc...

DePaul's academic integrity policy

http://www.cdm.depaul.edu/onlinelearning/Pages/OnlinePolicies.aspx

If you live in Chicago, you can take the exams at the Loop or Suburban campuses. If you live outside the Chicago area, you will need to find a proctor.

Your online section is paired with an on-campus section. These classes are recorded and uploaded into the Course Management system so you can view them within 24 hours of the live class. The first class is 2011/03/27-29. The lecture will be available online the following day.

My coordinates:

• I work at home some days. (Generally I am in the office on days I teach and on Fridays.)

Contact by phone:

• I do not often check voice-mail.

Contact by email:

• I check email about twice a day.
• It may take as long as a few days for me to reply to mail.
• Please check that the email address on your CampusConnect record is correct.

For labs, we will use a server running linux.

The server name is riely373.cdm.depaul.edu. The ip address is 140.192.39.11

• If you prefer to refer to the server by a shorter name, such as riely373, then add the following line to /etc/hosts (linux, OSX) or C:\WINDOWS\System32\drivers\etc\hosts (windows):

  140.192.39.11	riely373
  

  The hosts file will then look something like this:

  127.0.0.1       localhost
  140.192.39.11	riely373
  

  Don't delete any entries unless you know what you are doing!

In the rest of the notes, I will use the server name riely373 rather than the ip address. You should substitute the ip address when attempting to connect with the server.

• The server is behind a firewall which blocks all access except using ssh.

• I have given all enrolled students an account on the machine.

  Your account name is the first three letters of you last name, all lowercase. It may also include your first initial. It's one of these: ald alh all ber bon bre bur cat cou ega esp fan fed hay hoo kra kur kva lea luk maj mei nil pau pol porf porp sch spe tho wag wil wir xia

  Your password is your depaul id number, including leading zeros.

  If your name is not listed, email me and I will make an account for you.

  These accounts are temporary and will be deleted when the class is finished. I reserve the right to read any files that you post to the account.

In the rest of the notes, I will use the username stu. You should substitute your own username when attempting to connect with the server.

You can access the machine by going to a command line and typing:

ssh stu@riely373.cdm.depaul.edu

Using PuTTY, connect to server riely373.cdm.depaul.edu with username stu. For FileZilla, use port 22.

To do the homeworks, you will need an ssh client.

For a gui sftp client (all platforms), get FileZilla

• Windows: On windows, install PuTTY (use putty-???-installer.exe).

  Windows explorer does not support sftp.

• Ubunutu Linux: The command line programs ssh, scp and sftp are installed by

  sudo apt-get install openssh-client
  

  File browser supports sftp. Select Go->Location (C-l). In the location bar, type sftp://username@riely373.cdm.depaul.edu/.

• OSX: The command line programs ssh, scp and sftp come pre-installed on OSX.

  Mac Finder does not support sftp.

  To get drag/drop Finder integration is a bit of a pain. To do it, install MacFUSE and sshfs. (Just drag sshfs.app to /Applications.) To mount a directory, run sshfs.app. (This copy of sshfs is private; the public verion, available here, no longer contains the very simple gui.)

We will use gcc on riely373.

Some of you may wish to run gcc locally on your home computer.

• Windows: There are many versions of gnu utilities for windows, including MinGW, Cygwin, and GNUwin32

  Unless you already use cygwin, I recommend that you install MinGW (use the installer executable).

• Ubunutu Linux: sudo apt-get install build-essentials

• OSX: Install Xcode (also on your installation DVD).

More linux/C links

Linux Commands - A practical reference Nice one page summary of some more advanced commands.

LinuxCMD.org Tutorial examples organized by functionality.

Command: ls

Arguments: Optional list of files and or directory names

Options: -l

Description: Lists the specified files and or directories. For a directory, all its files and directories are listed. If no file or directory is specified, the current directory is assumed.

Example:

$ ls
csc373          mail            nachos-3.4.tar  test
examples        nachos-3.4      new             test.txt

Example:

$ pwd
/home/prof

Command: rm

Arguments: file list

Options: -i -r

Description: Removes (deletes) the specified files

-i   Ask before removing each file (Good idea since it is not possible to reverse a removal)
-r   Recursively remove directories and subdirectories in
     the list. Files will be removed in these directories
     first and then the directory itself. (Useful but dangerous)]]

Example:

$ rm test.txt 
$ rm -r test

Arguments: existing_file new_file

Options: -i

Description: Renames existing_file to have the name new_file -i Prompts if mv would overwrite an existing file.

Example:

$ ls
code             output.c         test.cpp         thrd.c~
file             sample_busy      test.txt
homework2        sample_busy.cpp  thrd
output           test             thrd.c
$ mv output.c input.c
$ ls
code             output           test.cpp         thrd.c~
file             sample_busy      test.txt
homework2        sample_busy.cpp  thrd
input.c          test             thrd.c

Arguments: existing_file new_copy

Description: Copy existing_file to the file new_copy. If new_copy doesn't exist, create it. If it does exist, first delete its contents.

If new_copy is a directory, a copy of existing_file is created in directory new_copy with the same file name - existing_file.

Example:

$ cp sample.cpp prog1.cpp

Arguments: new_subdirectory_name

Description: Create a subdirectory of the current directory

Example:

$ mkdir hw1

Arguments: target_directory

Options:

Description: Change the current directory (working directory) to the specified target_directory. If no target_directory is specified, change to the login/home directory.

Example:

$ cd hw1

The following changes the current directory to the parent directory:

$ cd ..

There are several tools available for viewing files. The most popular command is "less" invoked as follows:

$ less foo

• Space bar to move forward one page.
• b to move backward one page,
• Enter to move forward one line,
• / to search for key_word in the text,
• q to quit.

To scroll the contents of a file to the screen, you can use the cat command. This command gets its name from concatenate: it reads its input file name(s) and writes them to the screen. If you give it more than one file name:

$ cat foo bar

then cat will first write foo to the screen and then bar. Redirecting this output to a file (we won't go into redirection here)
like this:

$ cat foo bar > bas

would give you a file named bas whose content is the contents of bar concatenated to foo. This is a good way to add files together.

To print a file, you'll need to use ftp or the secure shell client to transfer the file to a PC. You can then print the file as you would any other file on the PC.

To view the unix online manual, you need to know the exact name of a manual topic; e.g., fork. In some cases you may not know the exact name. You can try the man command with the -k option (for keyword)

$ man -k fork

The output shows all manual topic names in the first column related to the keyword entered (fork).

Once you know the name of the manual page for a topic use the man command again with that specific topic:

$ man fork

To edit your programs, you will need a text editor.

nano is the easiest to use.

Having said that, the most popular editors in UNIX/Linux are vim and emacs. You can learn about vi at

http://heather.cs.ucdavis.edu/~matloff/UnixAndC/Editors/ViIntro.html

and emacs at

http://heather.cs.ucdavis.edu/~matloff/UnixAndC/Editors/Emacs.html

Here is a short primer on emacs. To start emacs type

$emacs

To open a file file.c using emacs, type

$emacs file.c

You can start editing know. When you want to save your file, type

Ctrl-X Ctrl-S (This means pressing the Ctrl key and pressing x and then s, while still pressing the Ctrl key)

To save a file under a different name, type

Ctrl-X Ctrl-W

To exit emacs, type

Ctrl-X Ctrl-C

Here is a short list of important emacs editing commands

To move the cursor forward or backward, type

Ctrl-F or Ctrl-B

respectively.To move the cursor up or down, type

Ctrl-P and Ctrl-N

respectively. To delete a character pointed to by the cursor, type

Ctrl-D

To cut and paste, move the cursor to the first character of the part you want to cut and paste. Then type

Ctrl-SPACE (SPACE is the space bar)

Then move the cursor down to the last character of the part you want to cut. Then type

Ctrl-W

to cut the text. You can then move the cursor to the position where you want to paste, and type

Ctrl-Y

to paste. You can paste the cut text again and again with Ctrl-Y.

You should be able to modify the properties of the VT102 terminal emulator in SSH to customize some of teh key bindings.

For additional info about UNIX/Linux go to Norman Matloff's intro to Unix

Datalab (bitNor)

file:hello.c [source]

00001: #include <stdio.h> 00002: 00003: int main() 00004: { 00005: printf("hello, world\n"); 00006: } 00007:

To compile a single file C program in a file named hello.c use the gcc compiler.

$ gcc hello.c -o hello

This compiles the program hello.c, links it with any standard c library routines called (e.g. i/o routines) and produces the executable file named hello.

Now run hello:

$ ./hello

The following unix commands can make some sense of binary data

• wc
• xxd
• strings
• objdump

Computer organization is based on the byte

 4 bits == nibble
 8 bits == byte
32 bits == word (32 bit machine)
64 bits == word (64 bit machine)

 ----------------------
 DECIMAL | HEX | BINARY
 --------|-----|-------
       0 |   0 |  0000
       1 |   1 |  0001
       2 |   2 |  0010
       3 |   3 |  0011
         |     |
       4 |   4 |  0100
       5 |   5 |  0101
       6 |   6 |  0110
       7 |   7 |  0111
         |     |
       8 |   8 |  1000
       9 |   9 |  1001
      10 |   A |  1010
      11 |   B |  1011
         |     |
      12 |   C |  1100
      13 |   D |  1101
      14 |   E |  1110
      15 |   F |  1111

file:hello.c [source]

00001: #include <stdio.h> 00002: 00003: int main() 00004: { 00005: printf("hello, world\n"); 00006: } 00007:

• #include is a preprocessor directive: it literally includes other code into your program (prototypes for constants, functions, etc.), which then gets compiled as though it were part of what you wrote
• Your program must contain a function called main
• Elementary i/o in C is performed by 2 functions: scanf for input, and printf for output
• Both take format strings which specify the data types to read (or a combination of data types plus text to print)
  • Composed of ordinary characters (not %)
    • Copied unchanged into the output
  • Conversion specifications (start with %)
    • Fetches one or more arguments

      char    %c
      char[]  %s  // string
      int     %d  // signed decimal (base 10)
      int     %u  // unsigned decimal (base 10)
      int     %x  // unsigned hexidecimal (base 16)
      int     %p  // pointer (like %x but with leading 0x)
      float   %f
      

• There really should be a return statement at the end of the program: return 0;

file:format.c [source]

00001: #include <stdio.h> 00002: 00003: int main() 00004: { 00005: printf ("Characters: %c %c \n", 'a', 65); 00006: printf ("Characters: %d %d \n", 'a', 65); 00007: printf ("Decimals: %d %d\n", 1977, 65000000); 00008: printf ("Preceding with blanks: %10d \n", 1977); 00009: printf ("Preceding with zeros: %010d \n", 1977); 00010: printf ("Some different radixes: %d %x %o %#x %#o \n", 00011: 100, 100, 100, 100, 100); 00012: printf ("floats: %4.2f %+.0e %E \n", 3.1416, 3.1416, 3.1416); 00013: printf ("%s \n", "A string"); 00014: int x; 00015: float y; 00016: printf("Enter a decimal and a floating point number\n"); 00017: scanf("%d %f", &x, &y); 00018: printf("You entered %d %lf\n", x, y); 00019: 00020: char s[1]; 00021: printf("Enter a string\n"); 00022: scanf("%s", s); 00023: printf("You entered %s\n", s); 00024: return 0; 00025: } 00026:

1 and 0 are like true and false

1 and 0 are like true and false

• How do we map truth values to bytes?
  • One truth value per bit (logical)
  • One truth value per byte (bitwise)
• How do we map truth values to words?
  • One truth value per bit (logical)
  • One truth value per word (bitwise)
• Recall the meaning of logical AND, (inclusive) OR, (exclusive) XOR, and NOT

• Operations for logical not, and, inclusive-or:

  ! && ||
  

• Apply to any integral data type, signed or unsigned

  char short int long
  

• Operators always return 0 or 1

  !1  == 0   !!1  == 1
  !0  == 1   !!0  == 0
  !55 == 0   !!55 == 
  

• Operations for bitwise not, and, inclusive-or, and exclusive-or:

  ~ & | ^
  

• Apply to any integral data type, signed or unsigned

  char short int long
  

• Bits have two possible values, 0 or 1.
• 0 represents false and 1 represents true.
• View arguments as bit vectors
• Operations applied bit-wise

Examples using one byte. The examples show the number in base-2 (binary) notation.

 x   == 01000001
~x   == 10111110

 x   == 00000000
~x   == 11111111

 x   == 01101001
 y   == 01010101
 x&y == 01000001

 x   == 01101001
 y   == 01010101
 x|y == 01111101

 x   == 01101001
 y   == 01010101
 x^y == 00111100

the following hold for any x

 ~(~x) == x

the following hold for any x

x & x         == x
x & 00000000  == 00000000
x & 11111111  == x

x | x         == x
x | 00000000  == x
x | 11111111  == 11111111

What about

x & 00001111  == 
x | 00001111  == 

XOR is important in cryptography

the following hold for any x and y

x ^ x         ==  0
x ^ 00000000  ==  x
x ^ 11111111  == ~x

x ^ y == (~x | ~y) & ~(x & y)
x ^ y == (x & ~y) | (~x & y)

• Left Shift: x << y
  • Shift bit-vector x left y positions
    • Throw away extra bits on left
    • Fill with 0’s on right
• Right Shift: x >> y
  • Shift bit-vector x right y positions
    • Throw away extra bits on right
  • Logical shift
    • Fill with 0's on left
  • Arithmetic shift
    • Replicate most significant bit on left
    • Useful with two’s complement integer representation (which we will talk about next week)

Left shift:

 x    == 01100010
 x<<1 == 11000100
 x<<2 == 10001000
 x<<3 == 00010000
 x<<4 == 00100000
 x<<5 == 01000000
 x<<6 == 10000000
 x<<7 == 00000000
 x<<8 == 00000000

Right shift:

        (logical)      (arithmetic)
 x    == 01100010       01100010
 x>>1 == 00110001       00110001
 x>>2 == 00011000       00011000
 x>>3 == 00001100       00001100
 x>>4 == 00000110       00000110
 x>>5 == 00000011       00000011
 x>>6 == 00000001       00000001
 x>>7 == 00000000       00000000
 x>>8 == 00000000       00000000

        (logical)      (arithmetic)
 x    == 11100010       11100010
 x>>1 == 01110001       11110001
 x>>2 == 00111000       11111000
 x>>3 == 00011100       11111100
 x>>4 == 00001110       11111110
 x>>5 == 00000111       11111111
 x>>6 == 00000011       11111111
 x>>7 == 00000001       11111111
 x>>8 == 00000000       11111111

file:bitops.c [source]

00001: // shows the effect of various bit operations 00002: #include <stdio.h> 00003: 00004: #include "show-bytes.c" 00005: int main() { 00006: int x,y; 00007: unsigned int z; 00008: printf("Enter 2 numbers\n"); 00009: scanf("%x %x", &x, &y); 00010: z = x; 00011: printf("x in binary is "); 00012: print_binary(x); 00013: printf("\ny in binary is "); 00014: print_binary(y); 00015: printf("\n\nx & y = "); 00016: print_binary(x&y); 00017: printf("\nx | y = "); 00018: print_binary(x|y); 00019: printf("\nx ^ y = "); 00020: print_binary(x^y); 00021: printf("\n\nx = "); 00022: print_binary(x); 00023: printf("\n~x = "); 00024: print_binary(~x); 00025: printf("\nx<<1 = "); 00026: print_binary(x << 1); 00027: printf("\nx<<2 = "); 00028: print_binary(x << 2); 00029: printf("\nx>>3 = "); 00030: print_binary(x>>3); 00031: printf("\n\nx in decimal = %d\n", x); 00032: printf("~x in decimal = %d\n", ~x); 00033: printf("x<<1 in decimal = %d\n", x<<1); 00034: printf("x<<2 in decimal = %d\n", x<<2); 00035: printf("x>>1 in decimal = %d\n", x>>1); 00036: printf("\n"); 00037: printf("\nz = "); 00038: print_binary(z); 00039: printf("\n~z = "); 00040: print_binary(~z); 00041: printf("\nz<<1 = "); 00042: print_binary(z << 1); 00043: printf("\nz<<2 = "); 00044: print_binary(z << 2); 00045: printf("\nz>>3 = "); 00046: print_binary(z>>3); 00047: printf("\n\nz in decimal = %u\n", z); 00048: printf("~z in decimal = %u\n", ~z); 00049: printf("z<<1 in decimal = %u\n", z<<1); 00050: printf("z<<2 in decimal = %u\n", z<<2); 00051: printf("z>>1 in decimal = %u\n", z>>1); 00052: printf("\n"); 00053: return 0; 00054: } 00055:

Datalab (bitXor)

Revised: 2008/03/17 13:01