» CS 352 Lecture 1 – Alien Protocols

CS 352 Lecture 1 – Alien Protocols

September 7, 2016 by Chris Johnson. Filed under cs352, fall 2016, lectures.

Dear students,

Welcome to CS 352: Computer Architecture. Ernest Hemingway is said to have written a story in just six words: “For sale: baby shoes, never worn.” The story of this class can be stated with just two words: “Abstractions leak.”

Our forebears have worked very hard to make computers understand our computational desires at a reasonably high level, but the choices they have made at the lower levels have such a profound impact on how our technology behaves that we cannot ignore them. We must dive beneath the high level and see what they did. We will, of course, return to the high level, but we will return as amphibians, capable of operating at all levels of abstraction.

I don’t remember a lot of stuff from my architecture classes—except for a couple of things from graduate school, when I was more conscious. One was that Dr. Ward often illustrated step-by-step solutions to hardware problems in his Powerpoint presentations. On the last step, he would demonstrate that the solution produced the desired result with a bold, “Viola!”

I have another vivid memory of him offering extra credit for an exam if we submitted a coffee mug design to the annual mug design contest. Some alumnus put up the money each year to have departmental mugs made. Each of the faculty and graduating seniors got one, and so did the winner. As Dr. Ward was explaining the extra credit, I had a flash of inspiration from the sign on the wall right above his head. Immediately after class I sketched up my design and submitted it. Guess who won? Let me show you my mug.

A third thing that happened was that I suddenly realized that I needed to typeset a lot of mathematics, and my existing tools did a pretty horrible job. Microsoft Word and OpenOffice (supplanted these days by LibreOffice) were cumbersome. Little did I know inside me a hole was opening up that only LaTeX could fill.

But these are all irrelevant pieces of information about me. I share them only because my goal for this class is influenced by my earlier experiences. My goal now is to try make the concepts of this class more relevant and memorable to you as a computer scientist. I may fail in this task. So, I will look for ways to offer extra credit and have you typeset mathematical formulae.

We’ll be doing some of these things in this class:

Examine low-level hardware components
Assemble RAM, an ALU, and a processor
Design an instruction set
Write assembly code for ARM processors
Learn some C++ and a hardware description language
Speed up data retrieval and storage with hierarchical memory
Accelerate tasks through pipelining
Immerse ourselves in addressable memory
Playing with Raspberry Pis

I am also going to use this class to help you brush up on your Linux and C++ skills. In that spirt, today we will complete a little exercise to warm us up to thinking at a lower level. Here’s a challenge for you and a neighbor to solve in the next few minutes:

An alien planet picks up on Morse code signals that NASA broadcast in 1972. Each letter of the Morse alphabet is represented by a sequence of 1-4 dots and dashes. The aliens’ technology allows them to emit only a signal of 0s and 1s, one at a time. Suppose they want to send back the message goodbye world, which translates to:
--. --- --- -.. -... -.-- .    . .- .-. - ....
How can they encode their message so it can be translated back on Earth? Write pseudocode on paper. Test out your solution. If you were CMO (chief Morse officer) at NASA, could you understand what the aliens said?

We will discuss your proposals and then implement a solution as a class, using the opportunity to revisit C++ and Makefiles.

Often when we meet for lecture, I will ask you to do some reading or activities and jot down some observations or reactions on a quarter sheet of paper to be turned in at the beginning of the next class. Since I have a large pile of these to read and sort through, I ask that you form this quarter sheet by dividing a piece of paper in half exactly twice, once vertically and once horizontally.

Consider these quarter sheets as personal and relevant notes to me. Without them, I can only guess what’s going on inside your head.

I will have a box in front of the room for you to turn these “quarter notes” in. That box will be whisked away soon after class starts. To receive participation credit, you must have your note in the box before it disappears. Don’t worry too much if you miss some. There will be occasional extra credit opportunities to regain participation points.

Here’s your TODO list of things to complete before next class:

Read the syllabus.
Install your own Linux.
Read Joel Spolsky’s The Law of Leaky Abstractions.
Write down 2-3 questions or observations about the class or from your reading on a quarter note.

See you next class!

Sincerely,

P.S. Here’s the code we together…

Socket.h

#ifndef SOCKET_H
#define SOCKET_H

#include <cstdlib>
#include <unistd.h>
#include <cstring>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h>
#include <string>

/* ------------------------------------------------------------------------- */

class Socket {
  public:
    Socket();
    Socket(int id);
    Socket(const std::string &host, int port);
    ~Socket();

    bool HasByte();
    unsigned char ReadByte();
    void WriteByte(unsigned char byte);

    int GetID();

  protected:
    bool is_byte_buffered;
    unsigned char byte;
    int id;
};

/* ------------------------------------------------------------------------- */

class ServerSocket : public Socket {
  public:
    ServerSocket(int port);
    Socket Accept(); 

  private:
};

/* ------------------------------------------------------------------------- */

class ClientSocket : public Socket {
  public:
    ClientSocket(const std::string &host, int port);

  private:
};

/* ------------------------------------------------------------------------- */

#endif

Socket.cpp

#include <iostream>

#include "Socket.h"

/* ------------------------------------------------------------------------- */

Socket::Socket() {
  // Secure a socket.
  id = socket(AF_INET, SOCK_STREAM, 0);
  if (id < 0) {
    perror("socket()");
    exit(1);
  }
}

/* ------------------------------------------------------------------------- */

Socket::Socket(int id) :
  id(id) {
}

/* ------------------------------------------------------------------------- */

Socket::Socket(const std::string &host, int port) {

  // Secure a socket.
  id = socket(AF_INET, SOCK_STREAM, 0);
  if (id < 0) {
    perror("socket()");
    exit(1);
  }

  struct hostent *server = gethostbyname(host.c_str());
  if (server == NULL) {
    perror("gethostbyname()");
    exit(1);
  }

  struct sockaddr_in server_address;
  bzero((char *) &server_address, sizeof(server_address));
  server_address.sin_family = AF_INET;
  bcopy((char *) server->h_addr, (char *) &server_address.sin_addr.s_addr, server->h_length);
  server_address.sin_port = htons(port);

  int status = connect(id, (struct sockaddr *) &server_address, sizeof(server_address));
  if (status < 0) {
    perror("connect()");
    exit(1);
  }
  
}

/* ------------------------------------------------------------------------- */

Socket::~Socket() {
  close(id);
}

/* ------------------------------------------------------------------------- */

bool Socket::HasByte() {
  if (is_byte_buffered) {
    return true;
  } else {
    int nbytes = read(id, &byte, 1);
    is_byte_buffered = nbytes > 0;
    return is_byte_buffered;
  } 
}

/* ------------------------------------------------------------------------- */

unsigned char Socket::ReadByte() {
  if (is_byte_buffered) {
    is_byte_buffered = false;
    return byte;
  } else {
    int nbytes = read(id, &byte, 1);
    if (nbytes == 0) {
      perror("ReadByte() - nothing to read!");
      exit(1);
    } else {
      return byte;
    }
  }  
}

/* ------------------------------------------------------------------------- */

void Socket::WriteByte(unsigned char byte) {
  write(id, &byte, 1); 
}

/* ------------------------------------------------------------------------- */

int Socket::GetID() {
  return id;
}

/* ------------------------------------------------------------------------- */

ServerSocket::ServerSocket(int port) :
  Socket() {

  // Bind socket to a given port. 
  struct sockaddr_in server_address;
  server_address.sin_family = AF_INET;
  server_address.sin_addr.s_addr = INADDR_ANY;
  server_address.sin_port = htons(port);
  
  int status = bind(id, (struct sockaddr *) &server_address, sizeof(server_address));
  if (status < 0) {
    perror("bind()");
    exit(1);
  }

  // Start listening for clients.
  status = listen(id, 1);
  if (status < 0) {
    perror("listen()");
    exit(1);
  }
}

/* ------------------------------------------------------------------------- */

Socket ServerSocket::Accept() {
  // Accept a client.
  struct sockaddr_in client_address;
  socklen_t client_length;
  int client_socket = accept(id, (struct sockaddr *) &client_address, &client_length);
  if (client_socket < 0) {
    perror("accept()");
    exit(1);
  }

  return Socket(client_socket);
}

/* ------------------------------------------------------------------------- */

client.cpp

#include <iostream>
#include <map>

#include "Socket.h"

using std::map;
using std::string;

int main(int argc, char **argv) {
  map<char, string> char_to_morse;
  char_to_morse['a'] = ".-";
  char_to_morse['b'] = "-...";
  char_to_morse['c'] = "-.-.";
  char_to_morse['d'] = "-..";
  char_to_morse['e'] = ".";
  char_to_morse['f'] = "..-.";
  char_to_morse['g'] = "--.";
  char_to_morse['h'] = "....";
  char_to_morse['i'] = "..";
  char_to_morse['j'] = ".---";
  char_to_morse['k'] = "-.-";
  char_to_morse['l'] = ".-..";
  char_to_morse['m'] = "--";
  char_to_morse['n'] = "-.";
  char_to_morse['o'] = "---";
  char_to_morse['p'] = ".--.";
  char_to_morse['q'] = "--.-";
  char_to_morse['r'] = ".-.";
  char_to_morse['s'] = "...";
  char_to_morse['t'] = "-";
  char_to_morse['u'] = "..-";
  char_to_morse['v'] = "...-";
  char_to_morse['w'] = ".--";
  char_to_morse['x'] = "-..-";
  char_to_morse['y'] = "-.--";
  char_to_morse['z'] = "--..";

  map<string, char> morse_to_char;
  for (auto pair : char_to_morse) {
    morse_to_char[pair.second] = pair.first;
  }

  Socket socket(argv[1], atoi(argv[2]));

  string token_so_far = "";

  while (socket.HasByte()) {
    unsigned char a = socket.ReadByte();
    unsigned char b = socket.ReadByte();
    if (a == 0 && b == 0) {
      std::cout << " ";
    } else if (a == 0 && b == 1) {
      std::cout << morse_to_char[token_so_far];
      token_so_far = "";
    } else if (a == 1 && b == 0) {
      token_so_far += '.';
    } else if (a == 1 && b == 1) {
      token_so_far += '-';
    } 
  }

  // 00 - word separator
  // 01 - letter separator
  // 10 - .
  // 11 - -

  return 0;
}

server.cpp

#include <iostream>
#include <map>

#include "Socket.h"

using std::string;
using std::map;

int main(int argc, char **argv) {
  ServerSocket server(atoi(argv[1]));
  Socket client = server.Accept();

  string message = "goodbye world";

  map<char, string> char_to_morse;
  char_to_morse['a'] = ".-";
  char_to_morse['b'] = "-...";
  char_to_morse['c'] = "-.-.";
  char_to_morse['d'] = "-..";
  char_to_morse['e'] = ".";
  char_to_morse['f'] = "..-.";
  char_to_morse['g'] = "--.";
  char_to_morse['h'] = "....";
  char_to_morse['i'] = "..";
  char_to_morse['j'] = ".---";
  char_to_morse['k'] = "-.-";
  char_to_morse['l'] = ".-..";
  char_to_morse['m'] = "--";
  char_to_morse['n'] = "-.";
  char_to_morse['o'] = "---";
  char_to_morse['p'] = ".--.";
  char_to_morse['q'] = "--.-";
  char_to_morse['r'] = ".-.";
  char_to_morse['s'] = "...";
  char_to_morse['t'] = "-";
  char_to_morse['u'] = "..-";
  char_to_morse['v'] = "...-";
  char_to_morse['w'] = ".--";
  char_to_morse['x'] = "-..-";
  char_to_morse['y'] = "-.--";
  char_to_morse['z'] = "--..";
  
  // TODO: emit message over client
  for (int i = 0; i < message.size(); ++i) {
    if (message[i] == ' ') {
      client.WriteByte(0);
      client.WriteByte(0);
    } else {
      auto morse = char_to_morse.find(message[i]);
      if (morse != char_to_morse.end()) {
        // if message[i] == 'g', then morse->second == '.--'    
        for (int mi = 0; mi < morse->second.size(); ++mi) {
          if (morse->second[mi] == '.') {
            client.WriteByte(1);
            client.WriteByte(0);
          } else {
            client.WriteByte(1);
            client.WriteByte(1);
          }
        }

        client.WriteByte(0);
        client.WriteByte(1);
      }
    }
  }

  return 0;
}