cmsc216.tex

% Adapted from Alex Reustle's CMSC351 Course Notes

% This program is free software: you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation, either version 3 of the License, or
% (at your option) any later version.

% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.

% You should have received a copy of the GNU General Public License
% along with this program.  If not, see <http://www.gnu.org/licenses/>.
\documentclass[english, 10pt]{article}

\usepackage{notes}
\usepackage{inconsolata}
\usepackage[shellescape]{gmp}
\allowdisplaybreaks%
\newcommand{\thiscoursecode}{CMSC 216}
\newcommand{\thiscoursename}{Introduction to Computer Systems}
\newcommand{\thisprof}{Dr.\ Ilchul Yoon}
\newcommand{\me}{Akilesh Praveen}
\newcommand{\thisterm}{Spring 2020}
\newcommand{\website}{http://cs.umd.edu/class/spring2020/cmsc216/}%chktex 8
\usepackage{ifpdf}
\ifpdf%
\DeclareGraphicsRule{*}{mps}{*}{}
\fi
% \listfiles

\usepackage[utf8]{inputenc}
 
\usepackage{listings}
\usepackage{xcolor}
\usetikzlibrary{patterns}
 
\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.94}
\definecolor{codered}{rgb}{0.5,0.15,0.15}
\definecolor{commentred}{rgb}{1,0.01,0.02}
 
\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},   
    commentstyle=\color{codegreen},
    keywordstyle=\color{red},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codered},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,
    xleftmargin=.15\textwidth,
    xrightmargin=.15\textwidth,
    linewidth=\textwidth,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=2,
    belowskip=3em,
    aboveskip=3em,
}

\lstset{style=mystyle}


% \VerbEnvir{align tikzpicture algorithm}
%%%Headers
\chead{216-Introduction to Computer Systems}
\lhead{\thisterm}

%%%%% TITLE %%%%%
\graphicspath{{../}}
\newcommand{\notefront}{%
\pagenumbering{arabic}
\begin{center}
{\small}
\textbf{\Huge{\noun{\thiscoursecode}}}
{\Huge \par}
{\Large{\noun{\thiscoursename}}}\\
\vspace{0.1in}
\vspace{0in}\includegraphics[scale=0.3]{umd_cs.jpg} \\
\vspace{0.1in}{\noun\me} \\
{\noun\thisprof} \ $\bullet$ \ {\noun\thisterm} \ $\bullet$ \ {\noun{University of Maryland}} \\
{\ttfamily \url{\website}} \\
\end{center}
}

 \tikzstyle{class}=[
    rectangle,
    draw=black,
    text centered,
    anchor=north,
    text=black,
    text width=2cm,
    shading=axis,
    bottom color={rgb:red,222;green,222;blue,222},
    top color=white,shading angle=45]

\begin{document}
% \renewcommand\familydefault{\sfdefault}
% \sffamily
  % Notes front
  \notefront%
  % Table of Contents and List of Figures
  \tocandfigures%
  
\section{Notes \& Preface}

This is a compilation of my notes for CMSC216 as a TA for the Spring 2020 offering of the course at the University of Maryland. All content covered in these notes was created by Dr. Ilchul Yoon and Dr. A.U. Shankar at the University of Maryland.
\newline

The actual content of this note repository is the content that I cover as a TA during my discussion section, combined with my personal insights for the course. I took this course with Nelson Padua-Perez in the Spring 2019 offering, so some of the notes that I'll drop in here are from my own notes when I took the course in 2019. As such, I would like to attribute certain code examples, analogies, and more to Mr. Perez. I believe that together, these will serve as great \textbf{supplementary material} for CMSC216, but I would still highly recommend attending all of your lecture and discussion sections to achieve success in CMSC216.
\newline

The notes template in use is Alex Reustle's template, which can be found on his github at the following location: \texttt{https://github.com/Areustle/CMSC351SP2016FLN}
\linebreak

I maintain this repository and as such, take responsibility for any mistakes. Please send errors to \texttt{apraveen@cs.umd.edu}
  
  
\section{Week 1 - Introduction to CMSC216}

CMSC216 is where you learn how a computer works on a much lower level than you've experienced before. There are 3 main components that the course will explore.

\subsection{Overview}

\begin{itemize}
	\item \textbf{UNIX} Threads, processes, and pipes as the building blocks of much bigger applications. We will be working with the UNIX operating system on the development environment at \texttt{grace.umd.edu}
	\item \textbf{C} is a high-performance language that works at a much lower level than Java. Things like memory management and advanced data structures are left up to the user. We'll cover concepts like memory management, pointers, and system calls.
	\item \textbf{Assembly} is even lower-level than C, and studying it will reveal how processors process instructions, store data, and maintain a stack and a heap. It's the lowest level you'll go in this class. For this semester's 216, you will be using MIPS assembly.
\end{itemize}

\subsection{Grace}

In this class, we will be using the \texttt{Grace} system to do all of our work. It's a little confusing to understand at first, so here's my way of thinking about it. In CMSC132, we did all of our work on our own computers. We pulled the skeleton code for the projects from the 132 website/repository, edited the code on our computers, and then uploaded our code to the submit server (via Eclipse) in order to test it.\newline

In CMSC216, we have been given access to this big computer that UMD CS owns known as \texttt{Grace}. You, as a student, have been given a small chunk of that machine to call your own (for the semester). In this class, we will access your files on the \texttt{Grace} system using a program known as \texttt{ssh} (that's how MobaXTerm works) and do all of our editing + running code on \texttt{Grace} itself. In fact, we will also be submitting our projects from \texttt{Grace} to the UMD CS submit server.\newline

Here are the relevant links for getting it all set up. You'll need to setup  \texttt{Grace} and \texttt{gcc} (the C compiler that we'll be using within \texttt{Grace}).\newline\newline
\begin{itemize}
	\item \texttt{\href{http://www.cs.umd.edu/~nelson/classes/resources/GraceSystem.shtml}{http://www.cs.umd.edu/~nelson/classes/resources/GraceSystem.shtml}}
	\item \texttt{\href{http://www.cs.umd.edu/~nelson/classes/resources/setting_gcc_alias.shtml}{http://www.cs.umd.edu/~nelson/classes/resources/setting\_gcc\_alias.shtml}} 
\end{itemize}
 



\subsection{Useful UNIX Commands}

Although the UNIX environment may seem confusing at first, learning it is essential to navigating the Grace environment. Below are some of the basic commands that you may find useful when getting started.

\begin{itemize}
	\item \textbf{\texttt{ssh}} $\rightarrow$ If you are not using MobaXTerm, you will have to access grace using the \texttt{ssh} command. For the purpose of logging in for CMSC216, I recommend adding the \texttt{-y} flag in order to bypass the warning it will give you. E.g. \texttt{ssh -y yourdirectoryid@grace.umd.edu}
	\item \textbf{\texttt{ls}} $\rightarrow$ The \texttt{ls} command lists all the files in your current directory. You can use the \texttt{-l} flag to get more detailed information. E.g. \texttt{ls}, \texttt{ls -l}
	\item \textbf{\texttt{cd}} $\rightarrow$ The \texttt{cd} command changes the directory you're currently in, mainly to directories that you can see with \texttt{ls}. Typing \texttt{cd ..} will navigate one directory 'up' from your current directory, and \texttt{cd} without anything else will return you to your home directory. E.g. \texttt{cd 216public}
	\item \textbf{\texttt{pwd}} $\rightarrow$ This command displays your current directory. Useful for finding out where exactly you are in the UNIX file hierarchy. E.g. \texttt{pwd}
	\item \textbf{\texttt{cp}} $\rightarrow$ Copies files. If you use the \texttt{-r} flag, you're telling the command to recursively copy. If you want to use \texttt{cp} on directories, remember to use that flag.
	\item \textbf{\texttt{rm}} $\rightarrow$ This command stands for 'remove'. It can be used to remove singular files, or can alternatively be used with the \texttt{-r} flag to recursively remove directories. E.g. \texttt{rm hello.c}, \texttt{rm -r project1} (project1 would be a folder.
	\item \textbf{\texttt{.}}, \textbf{\texttt{..}}, \textbf{\texttt{~}}, and \textbf{\texttt{/}} $\rightarrow$ These abbreviations are pretty important. They can be used to navigate a filesystem in Unix and generate some clever commands. In order, they mean 'current directory', 'parent directory', 'user home folder', and 'root directory'. Below are some examples.
	\begin{itemize}
		\item \textbf{\texttt{cp *.c ../}} $\rightarrow$ Copies all files that end with \texttt{.c} to the parent directory.
		\item \textbf{\texttt{cd /}} $\rightarrow$ Changes directories to the root directory.
		\item \textbf{\texttt{cp -r ~/216public/projects/project1 .}} $\rightarrow$ Recursively copies (this means that it copies directories as well as files) the project1 directory and everything in it into the current directory.
	\end{itemize}
\end{itemize}

Lots of these UNIX commands are super useful once you get to know them, but it may be hard becoming acquainted with how they work from the outset. It's a far cry from the GUI you had in CMSC132, so here are a few tips.

\begin{itemize}
	\item If you're just starting out and still need a graphical representation of the filesystem, I'd highly recommend setting up \textbf{MobaXTerm}. The program provides just a little more graphical representation than just a pure terminal, and allows you to navigate the Grace filesystem more freely. I like to think of it as training wheels as you get acquainted with Grace.
	\item I'd highly recommend getting used to making folders, deleting folders, deleting files, and navigating up and down through the filesystem with rapid sequences of \texttt{ls} and \texttt{cd}. As with all things, practice makes perfect, and pretty soon you'll be a command line wizard.
\end{itemize}

\subsection{Machine}

A computer is composed of several parts, but a great way to think about it is a few main components connected by a \textbf{bus}. \newline

\begin{itemize}
	\item \textbf{Memory} can just be thought of as a contiguous array of bytes. At the end of the day, this is the stuff that has to be written to/read from.
	\item \textbf{I/O Devices} are connected to the CPU via a bus, like mentioned above. By performing read/write operations to the right adaptor, the CPU is able to interface with different I/O devices.
	\item \textbf{CPU} is the central processing unit of the computer. It handles computational operations (arithmetic, logic, etc.) and interfaces with the memory and I/O devices via the bus. The CPU is also responsible for performing the \textbf{fetch-execute cycle}.
\end{itemize}

A bus is like one main connector that's responsible for making sure the CPU, memory, and I/O devices are all able to interface with each other.\newline\newline
Note that in this course, we won't be going too in-depth into hardware (that's more Computer Engineering), but it's great background knowledge to have as you approach this class, which is why I have included it here.

\section{Week 2}

\subsection{The Math Library}

We won't be using the math library much in C, but for the times that we do, just remember this one simple flag that we add to the gcc command. As an example, if you try to write some code that includes the math library like below, you'll find that it won't compile with a regular \texttt{gcc} command. 

{\centering
\begin{lstlisting}[language=C]
#include <stdio.h>
#include <math.h>

int main() {
   double value;

   printf("Enter a number: ");
   scanf("%lf", &value);     /* Notice the use of %lf */

   printf("sqrt %f: \n", sqrt(value));
   printf("power of 2: %f\n", pow(value, 2));
   printf("sin: %f\n", sin(value));

   return 0;
}
\end{lstlisting}
}

Remember that the \texttt{-lm} flag essentially enables us to use the math library. In other words, if you want to compile the above file and have it work properly, (let's assume it's called \texttt{math\_example.c}) then you'll want to compile it using the following command.\newline

\texttt{gcc -lm math\_example.c}

\subsection{Using Emacs}

Most of the instruction for this course will be done in \texttt{emacs}, a highly versatile text editor that you can use in GUI form or from the command line. It's always an option to use other text editors in this class, but I would recommend using \texttt{emacs}, as it's what all the in-class demos are in. There is a way to setup IDEs like Visual Studio Code to function with Grace, but I won't cover them here. I believe that although graphical IDEs have their advantages, you'll get plenty of experience with them in CMSC330 and CMSC4XX, so for now, develop your skills in a command line editor like \texttt{emacs} or \texttt{vi}.\newline

For your benefit, here are some basic commands in \texttt{emacs} that I've found useful over the time that I took 216.\newline\newline
\textbf{Note:} When I indicate to type \texttt{M}, that means you need to press the 'meta' key. On most machines, the 'meta' key is the 'alt/option'. When I indicate to type \texttt{C}, I mean the 'control' key. The reason I'm using this notation is because it's the same notation that online guides use to describe \texttt{emacs} shortcuts.

\begin{itemize}
	\item \textbf{\texttt{C-x C-s}} $\rightarrow$ Saves the file you're working on. Remember to do this frequently on Grace, as you can't guarantee that your connection to Grace will stay intact.
	\item \textbf{\texttt{C-x C-c}} $\rightarrow$ Closes the file that you're working on. If you haven't saved, it will prompt you to save.
	\item \textbf{\texttt{C-x u}} $\rightarrow$ Undo the previous command that you ran.
	\item \textbf{\texttt{C-s}} $\rightarrow$ Search forwards (this will search for text that'll be ahead of where your cursor is now.)
	\item \textbf{\texttt{C-r}} $\rightarrow$ Search backwards (this will search for text that'll be behind where your cursor is now.)
	\item \textbf{\texttt{C-l}} $\rightarrow$ This command will center the window around your cursor. A great technique when you have large C files that you're editing.
	\item \textbf{\texttt{M-x column-number-mode}} $\rightarrow$ Shows column numbers. Useful if you want to check if you're above the 80 character limit.
\end{itemize}

\subsection{Debugging}

There are three main debugging tools that we use in 216: Valgrind, GDB, and splint. For now, we won't focus too much on Valgrind, as it's more oriented towards helping programmers get rid of memory leaks and other memory-related issues. We will focus on GDB and Splint.

\subsubsection{GDB}

GDB Is the C equivalent of the Eclipse Debugger. It lets you do everything that the Eclipse Debugger allowed you to do in CMSC131 and CMSC132. The only real drawback here is that it's all done from the command line, so the graphic part of the interface is a little lacking. However, it's an essential tool that I'd highly recommend using to figure out errors in your code.\newline

Online references will tell you that there are a lot of commands that you need to know to effectively use GDB, but here are some of the ones that I've found useful.

\begin{itemize}
	\item \textbf{\texttt{q}} $\rightarrow$ exits gdb. Useful.
	\item \textbf{\texttt{start}} $\rightarrow$ starts running your code with a temporary breakpoint at the first line of main(). This allows you to set more breakpoints before the code actually starts executing.
	\item \textbf{\texttt{l}} $\rightarrow$ lists the code that you have.
	\item \textbf{\texttt{b}} $\rightarrow$ typing p with a number next to it sets a breakpoint at a line. E.g. \texttt{b 3}
	\item \textbf{\texttt{n}} $\rightarrow$ the equivalent of step over in the Eclipse debugger
	\item \textbf{\texttt{s}} $\rightarrow$ the equivalent of step into in the Eclipse debugger
	\item \textbf{\texttt{c}} $\rightarrow$ will continue running your code until the next breakpoint
	\item \textbf{\texttt{p}} $\rightarrow$ will print the value of an expression or a variable. E.g. \texttt{p valid\_character('x')}.
\end{itemize}

In order to start GDB, you'll first need to compile your C code into an \texttt{a.out} file. Not only that, but I would recommend that you compile your code with the \texttt{-ggdb} flag, to ensure that GDB initializes your program correctly. In order to run GDB with your newly compiled program, remember to just type \texttt{gdb a.out}\newline 

\section{Week 3}

This week we go over a lot of general C-specific programming concepts in discussion, and that material is heavier than what we usually do in discussion. In that sense, I'll try and go over the more basic stuff that I think will be highly useful as you work on your projects.

\subsection{Comma is an Operator}

The comma in C is an operator. The best way to think about this in use is when you're declaring multiple variables at once, like when you say \texttt{int i, j = 2}.

Remember, commas are \textbf{also} used as separators in C. A great example would be if you're giving a function multiple parameters, like in \texttt{printf("\%d and \%d", i, j)}. When you consider the comma as an operator in C, it's always important to understand where it's an operator vs. where it's a separator. 

Although we don't think about the comma operator quite a lot, one of the main reasons for understanding it would be initialization of multiple variables in a loop. Take a look at the following example from my notes (from a previous offering of the CMSC216 course).

{\centering
\begin{lstlisting}[language=C]
// Comma Operator Example by Nelson Padua-Perez

for (j=0, k=10; j<=limit; j++, k+= 10) {
	printf("j->%d, k->%d\n", j, k);
} 
\end{lstlisting}
}

Notice how you initialize and increment multiple variables within a single for-loop.


\subsection{Identifier Scope}

Scope exists in C in a similar way that it does in other languages. All you have to remember is that if you declare variables within code blocks, they won't be accessible outside those blocks. In that regard, this phenomenon is quite similar to how Java handles scopes.

\subsection{C Program Memory Organization}

As we delve deeper into systems-level programming, it's important to visualize how C actaully manages the memory that your programs use. The interesting part about this is that this diagram is an exact representation of system memory, so you're finally able to see 'under the hood' of your programs.\newline

You can see that the lowest address is represented by \texttt{0x0} and the highest address is represented by \texttt{0xffffffff}. These addresses are actual locations in memory, represented in hexadecimal format (hence ffffffff being the highest address in the representation).

\begin{center}

\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp1982436807499255] 
\draw   (330,23) -- (400,23) -- (400,265) -- (330,265) -- cycle ;
%Shape: Rectangle [id:dp02798297576071851] 
\draw  [fill={rgb, 255:red, 184; green, 233; blue, 134 }  ,fill opacity=1 ] (332.25,227) -- (397.75,227) -- (397.75,262.5) -- (332.25,262.5) -- cycle ;
%Shape: Rectangle [id:dp8690208046922276] 
\draw  [fill={rgb, 255:red, 74; green, 144; blue, 226 }  ,fill opacity=1 ] (332.25,197.83) -- (397.75,197.83) -- (397.75,223.33) -- (332.25,223.33) -- cycle ;
%Shape: Rectangle [id:dp6529311675516911] 
\draw  [fill={rgb, 255:red, 245; green, 166; blue, 35 }  ,fill opacity=1 ] (331.75,158.83) -- (397.25,158.83) -- (397.25,194.58) -- (331.75,194.58) -- cycle ;
%Up Arrow [id:dp9371264302671377] 
\draw  [fill={rgb, 255:red, 80; green, 227; blue, 194 }  ,fill opacity=1 ] (354,148.03) -- (364.13,137) -- (374.25,148.03) -- (369.19,148.03) -- (369.19,164.58) -- (359.06,164.58) -- (359.06,148.03) -- cycle ;
%Shape: Rectangle [id:dp8515554275840291] 
\draw  [fill={rgb, 255:red, 208; green, 2; blue, 27 }  ,fill opacity=1 ] (332.25,25.5) -- (397.75,25.5) -- (397.75,65.5) -- (332.25,65.5) -- cycle ;
%Down Arrow [id:dp38470823955499234] 
\draw  [fill={rgb, 255:red, 80; green, 227; blue, 194 }  ,fill opacity=1 ] (355,72.1) -- (359.44,72.1) -- (359.44,58) -- (368.31,58) -- (368.31,72.1) -- (372.75,72.1) -- (363.88,81.5) -- cycle ;

% Text Node
\draw (365,211.25) node   [align=left] {{\fontfamily{pcr}\selectfont Data}};
% Text Node
\draw (365,244.75) node   [align=left] {{\fontfamily{pcr}\selectfont Text}};
% Text Node
\draw (364.5,176.71) node   [align=left] {{\fontfamily{pcr}\selectfont Heap}};
% Text Node
\draw (365,45.5) node   [align=left] {{\fontfamily{pcr}\selectfont Stack}};
% Text Node
\draw (299,24) node   [align=left] {0xffffffff};
% Text Node
\draw (301,262) node   [align=left] {0x0};



\end{tikzpicture}

\end{center}


Your program is allocated a certain block of memory- within it are the following 4 components. Keep in mind that this too, is an abstraction. You can further explore how programs are represented in memory in classes like CMSC411, but this is just about as far as we'll go in 216.

\begin{itemize}
	\item \textbf{Text} is where the code for your program goes. It's really not much more complex than that.
	\item \textbf{Data} is where global variables and variables that are static belong.
	\item \textbf{Heap} is where dynamically allocated memory lives. In Java, this stuff was managed for you. In C, you will have to manage it yourself, allocating memory and effectively increasing the size of the heap if you need more space while your program is running, and deallocating (freeing) memory to decrease the size of the heap. More on this when we discuss dynamically allocated memory.
	\item \textbf{Stack} is where local variables and function parameters live. It grows downwards (eventually meeting the heap and causing a stackoverflow) as functions are called. If you'll think back to 'stack frames' from recursion in CMSC132, this is the exact same concept.
\end{itemize}

\subsection{Storage}

There are two types of ways variables are stored in C- automatic and static. This basically goes hand-in-hand with block scopes and file scopes, but the important takeaways are these. First of all, in the example below, after the function \texttt{foo} is called, the variable \texttt{n} is thrown away.

{\centering
\begin{lstlisting}[language=C]
int foo(int k) {
	int n = 216;
	return n;
}
\end{lstlisting}
}

In that regard, the variable \texttt{n} has automatic storage. If a variable has static storage, it basically exists throughout the duration of your program's running time. Such variables are initialized only once.\newline

An important note: \texttt{static} in C does not mean the same thing as it does in Java. Here are the two main things that I think are worth remembering about static variables in C:

\begin{itemize}
	\item Static variables need not necessarily be initialized. If you don't bother initializing a static variable (you still have to declare it- this is not Python, language of the heathen) it will automatically initialize to zero.
	\item Static variables retain their values between function invocations. In other words, they are not stored using automatic storage.
\end{itemize}

{\centering
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

void compute_static(int x) {                                                    
   static int value = 100; /* What would happen if we don't initialize it? */         
                                                                                
   printf("(static) x: %d, value: %d, sum: %d \n", x, value, value + x);        
                                                                                
   ++value;                                                                     
} 
\end{lstlisting}
}

In the example above, if you called \texttt{compute\_static} twice, then your output would be \texttt{(static) x: 1, value: 100, sum: 101} and \texttt{(static) x: 1, value: 101, sum: 102}, as 'value' would retain its data between function calls.

\subsection{Linkage}

Linkage is essentially the science behind having C code spread across multiple files and making sure it all compiles and works properly.\newline

We want to sometimes split code between multiple files for organizational purposes. Currently, the projects you're working on are small, but in order to make your programs versatile, modular and better organized, it's a great idea to split code between files.\newline

When you attempt this, there may be issues that follow. For example, you may encounter a situation where you want to name a function \texttt{print\_sum()} in two files. How would we deal with such a duplicate?\newline

Problems of this sort can be solved by adjusting the \textbf{linkage} of these functions.\newline

For actual code examples, please check the linkage-examples in the 216public directory. They're extremely thorough. My goal here is to provide a quick few tips on what I think are the most important parts.\newline

Essentially, there are three types of linkage that you should remember to guide you through writing code in multiple C files.

\begin{itemize}
	\item \textbf{\texttt{None}} $\rightarrow$ No linkage. This is how you usually declare your variables, and as you'd expect, doesn't do anything special in regards to linkage. Think of it this way: A variable with no linkage belongs to a single function, and cannot be shared. In other words, there is \textit{only one copy per declaration}.
	\item \textbf{\texttt{Internal}} $\rightarrow$ Internal linkage is just a fancy way of saying you're using the \textbf{\texttt{static}} keyword. All declarations of a single identifier in file refer to the same thing. In other words, there is \textit{only one copy per file}.
	\item \textbf{\texttt{External}} $\rightarrow$ External linkage is signified by the \texttt{extern} identifier, and it basically means that a name can only refer to a single entity in your entire program. In other words, there is \textit{only one copy per program}.
\end{itemize}

\subsection{Enumerated Types}

Enumerated Types, or enums, in C are pretty useful, and quite comparable to their equivalents in Java. The best way to understand enums (in my opinion) is to think of examples. Some good ones are an enum for the days of the week (Monday, Tuesday, etc.), seasons (Summer, Spring, Fall, Winter), or even suits in a deck of cards (Spades, Clubs, Hearts, Diamonds). Below is an example of the latter.

{\centering
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez
#include <stdio.h>
int main() {
	enum Suit {SPADES, HEARTS,DIAMONDS = 42, CLUBS};
	enum Suit suit1, suit2;
	suit1 = SPADES;
	suit2 = CLUBS;
	if (suit1 < suit2) printf("Spades are first.\n");
	else printf("Clubs are first.\n");
	printf("Spades = %d, Clubs = %d\n",suit1, suit2);
	return 0;
}
\end{lstlisting}
}

The functionality here is pretty basic, but one thing that I think is worth remembering (and quite nifty if you can use it well) is that enum representations are based in integers. This means that, for example, you can get away with adding the month enum for January (0) and the month enum for February (1) and end up with February (1).\newline

Again, the code above is a great example of how you can leverage the integer-like characteristics of enums.

\subsection{Implicit Type Conversion and Casting in C}

Switching between data types is pretty similar to how it was in Java, but here's a quick review of the stuff that matters. As you write your projects, you'll realize these things, but it's important to remember when it's a good idea to cast and when it isn't. Here are some general tips for you.\newline

\begin{itemize}
	\item \texttt There are a few ways to represent numbers in C. For relatively small numbers, \texttt{short}s are the way to go. If you want to represent a number that's a little bigger, use an \texttt{int}. The difference between these two on the systems that we'll be working with is that \texttt{int}s are twice the size of \texttt{short}s. (4 bytes vs. 2 bytes) If you want to represent a decimal number, You'll probably just want to use a \texttt{float}.
	\item In my opinion, most projects that we'll deal with here can be accomplished perfectly well with just \texttt{int}s and \texttt{float}s.
		\item We can also cast in C, and it works almost the same was as it did in Java. Just remember, in Java we had the concept of wrapper classes that allowed us to do fancy things with certain data types. In C, we don't enjoy that luxury, so we are restricted to just basic data type casting. Below is an example.
	
	
	{\centering
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

#include <stdio.h>                                                                    
                                                                                      
int main() {                                                                          
   float x = 2.98;
   int y = (int)x;
}
\end{lstlisting}
}

\item That works exactly as you think it does. It converts 2.98 to 2 as it would in Java. Remember, don't overthink it, and don't try to call any wrapper class methods that you remember from Java. As long as you keep that in mind, you should be good to convert between data types in C.
\end{itemize}

	{\centering
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

#include <stdio.h>                                                                    
                                                                                      
int main() {                                                                          
   int x = 2000000000;                                                                
   long result_long;                                                                  
                                                                                      
   printf("Value of x: %d\n", x);                                                     
   printf("Multiplying by 3 (with %%d format): %d\n", 2000000000 * 3);                
   printf("Multiplying by 3 (with %%ld format): %ld\n", 2000000000 * 3);              
   printf("Multiplying by 3L (with %%d format): %d\n", 2000000000 * 3L);              
   printf("Multiplying by 3L (with %%ld format): %ld\n", 2000000000 * 3L);            
                                                                                      
   result_long = 2000000000 * 3;  /* Does it solve the problem? */                    
   printf("Storing result in long type variable: %ld\n", result_long);                
                                                                                      
   return 0;                                                                          
}
\end{lstlisting}
}

The above example from Nelson isn't that basic, but I feel like it gives you a good insight into how type conversion can find use. Give that example a try to see a cool application of using multiple data types to handle larger values.

\section{Week 4}

This week we cover pointers, a few functions in C that you may find useful, and GDB in emacs. The main focus of these notes will be pointers, and chances are that you've seen a lot of this stuff in lecture as well. Make sure to take some time to try out the examples that we've got for you so you understand the basics of how pointers work, as they're a fundamental part of C.

\subsection{Pointers \& Memory Maps}

Let's go over pointers in C. You may have already covered this subject in lecture, but I'd like to point out some of the nuances that helped me understand pointers when I was taking 216. \newline

First of all, take note that pointers are just another type of variable. Just like you have \texttt{int}s and \texttt{char}s in C, which take up a certain amount of space and store a certain type of data, a \textbf{pointer} is a data type that stores an \textbf{address}. \newline

There are a bunch of ways to think of pointers, but I think the easiest way to understand them is to use memory maps. Think of them as as a tool to help us better understand how pointers work- they are essentially just visual representations of memory in C. \newline

I think that pointers and memory maps go hand in hand in 216, so I'll include some examples (some of my own, plus the examples we go over in discussion) that I think will help you become proficient with both pointers and memory maps. \newline

As a side note, you can take a look at Nelson's sample memory map online if you need some extra guidance. (This should have been covered in discussion). \newline

\texttt{\href{http://www.cs.umd.edu/~nelson/classes/resources/MemoryMapExample.pdf}{http://www.cs.umd.edu/~nelson/classes/resources/MemoryMapExample.pdf}}




\subsection{Example - Integer \& Integer Pointer\newline} 


{
\centering



\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp058944761853589434] 
\draw   (369,30) -- (420,30) -- (420,59.14) -- (369,59.14) -- cycle ;
%Shape: Rectangle [id:dp8289049315294679] 
\draw   (370,103.33) -- (421,103.33) -- (421,132.48) -- (370,132.48) -- cycle ;
%Straight Lines [id:da15432785379816327] 
\draw    (395.5,117.9) -- (394.37,62) ;
\draw [shift={(394.33,60)}, rotate = 448.85] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (330,44) node   [align=left] {{\fontfamily{pcr}\selectfont int a}};
% Text Node
\draw (394.5,44.57) node   [align=left] {5};
% Text Node
\draw (325.67,116.33) node   [align=left] {{\fontfamily{pcr}\selectfont int * b}};



\end{tikzpicture}

	
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

#include <stdio.h>                                                                    
                                                                                      
int main() {                                                                          

	int a = 5;

	int * b = &a;   
	
	return 1;
}
\end{lstlisting}


}

This is about as simple as we can get with pointers. There are a variety of types of pointers that exist (one for each data type in C), but just remember that they're essentially just variables that store addresses.\newline

In this example, we can see that \texttt{a} is an integer, and \texttt{b} is an integer pointer. Although I've drawn an arrow from the inside of \texttt{b}'s box to \texttt{a}'s box, don't let that confuse you. \newline

Think of it like this- \texttt{a} \textbf{contains} the integer value 5. \texttt{b} \textbf{contains} the address of \texttt{a}. By convention in C, we say that \texttt{b} points to \texttt{a}. We just show this by drawing an arrow that starts in \texttt{b}'s box and points to \texttt{a}.

\subsection{Example - Multiple Pointer Types\newline}

{
\centering




\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp058944761853589434] 
\draw   (353,164) -- (404,164) -- (404,193.14) -- (353,193.14) -- cycle ;
%Shape: Rectangle [id:dp8289049315294679] 
\draw   (354,237.33) -- (405,237.33) -- (405,266.48) -- (354,266.48) -- cycle ;
%Straight Lines [id:da15432785379816327] 
\draw    (379.5,251.9) -- (378.37,196) ;
\draw [shift={(378.33,194)}, rotate = 448.85] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp0020066675833932957] 
\draw   (223.67,28.67) -- (274.67,28.67) -- (274.67,57.81) -- (223.67,57.81) -- cycle ;
%Shape: Rectangle [id:dp16429220233511355] 
\draw   (224.67,102) -- (275.67,102) -- (275.67,131.14) -- (224.67,131.14) -- cycle ;
%Straight Lines [id:da051837340435018975] 
\draw    (250.17,116.57) -- (249.04,60.67) ;
\draw [shift={(249,58.67)}, rotate = 448.85] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp1385770633532739] 
\draw   (465.67,28.67) -- (516.67,28.67) -- (516.67,57.81) -- (465.67,57.81) -- cycle ;
%Shape: Rectangle [id:dp03270745379570461] 
\draw   (467.33,105.33) -- (518.33,105.33) -- (518.33,134.48) -- (467.33,134.48) -- cycle ;
%Straight Lines [id:da3069083126116453] 
\draw    (492.17,116.57) -- (491.04,60.67) ;
\draw [shift={(491,58.67)}, rotate = 448.85] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (284.67,177.33) node   [align=left] {{\fontfamily{pcr}\selectfont double my\_double}};
% Text Node
\draw (378.5,178.57) node   [align=left] {9.0};
% Text Node
\draw (272.33,251.67) node   [align=left] {{\fontfamily{pcr}\selectfont double * double\_ptr}};
% Text Node
\draw (159.33,44) node   [align=left] {{\fontfamily{pcr}\selectfont int my\_integer}};
% Text Node
\draw (249.17,43.24) node   [align=left] {6};
% Text Node
\draw (151,113.67) node   [align=left] {{\fontfamily{pcr}\selectfont int * integer\_ptr}};
% Text Node
\draw (399.33,44) node   [align=left] {{\fontfamily{pcr}\selectfont char my\_char}};
% Text Node
\draw (491.17,43.24) node   [align=left] {e};
% Text Node
\draw (395,118.33) node   [align=left] {{\fontfamily{pcr}\selectfont char * char\_ptr}};


\end{tikzpicture}


	
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

#include <stdio.h>                                                                    
                                                                                      
int main() {                                                                          

	int my\_integer = 6;
	double my\_double = 9.0;
	char my\_char = 'e';
	
	int * int\_ptr = &my\_integer;
	double * double\_ptr = &my\_double;
	char * char\_ptr = &my\_char;
	
}
\end{lstlisting}


}

Here's a similar case to up above, but I just wanted to demonstrate that there are different types of pointers. Now, keep in mind that all of these pointers essentially hold addresses, and it's not like the address of a double looks much different from the address of a character or the address of an integer.\newline

If you're wondering why C is so specific and asks you to define the type of pointer, the answer lies in how we will treat the data that's within the pointer. Sure, it may be that all pointers hold addresses, but what happens if we try to add the contents of \texttt{double\_ptr} and \texttt{integer\_ptr}? If C only had one pointer type and we tried to add the contents of those two pointers together, there would be no way of knowing that we made a mistake until runtime. In that sense, C maintains different types of pointers to ensure type compatibility. The same address could be given by the C memory manager to an integer pointer or a double pointer, but in order to make sure that you're treating whatever is stored at that address in a type-compatible way, C makes sure to note the type of what you're pointing to.


\subsection{Example - Pointer To a String (Char Array) \newline}

{
\centering






\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp16429220233511355] 
\draw   (245.67,207) -- (296.67,207) -- (296.67,236.14) -- (245.67,236.14) -- cycle ;
%Straight Lines [id:da051837340435018975] 
\draw    (271.17,221.57) -- (271.98,148.5) ;
\draw [shift={(272,146.5)}, rotate = 450.64] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp8412783566407918] 
\draw   (243.67,117) -- (294.67,117) -- (294.67,146.14) -- (243.67,146.14) -- cycle ;
%Shape: Rectangle [id:dp7327342661859714] 
\draw   (294.67,117) -- (345.67,117) -- (345.67,146.14) -- (294.67,146.14) -- cycle ;
%Shape: Rectangle [id:dp03554725186896712] 
\draw   (345.67,117) -- (396.67,117) -- (396.67,146.14) -- (345.67,146.14) -- cycle ;
%Shape: Rectangle [id:dp5893017620753757] 
\draw   (396.67,117) -- (447.67,117) -- (447.67,146.14) -- (396.67,146.14) -- cycle ;
%Shape: Rectangle [id:dp8682717330515748] 
\draw   (447.67,117) -- (498.67,117) -- (498.67,146.14) -- (447.67,146.14) -- cycle ;

% Text Node
\draw (169,217.67) node   [align=left] {{\fontfamily{pcr}\selectfont char[5] my\_string}};
% Text Node
\draw (269.17,131.57) node   [align=left] {\textbackslash 0};
% Text Node
\draw (320.17,131.57) node   [align=left] {\textbackslash 0};
% Text Node
\draw (371.17,131.57) node   [align=left] {\textbackslash 0};
% Text Node
\draw (422.17,131.57) node   [align=left] {\textbackslash 0};
% Text Node
\draw (473.17,131.57) node   [align=left] {\textbackslash 0};


\end{tikzpicture}



	
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

#include <stdio.h>                                                                    
                                                                                      
int main() {                                                                          

	char my_string[5];
	
}
\end{lstlisting}


}

Finally, here's a look at how we would store a string. I picked a string because it's essentially an array of characters, so we get to see how both are represented in memory maps. \newline

Here, don't let the notation confuse you. Although I've declared the string \texttt{my\_string} in special notation, it's still essentially a pointer to a character. In this case, \texttt{my\_string} is a pointer to the first of 5 characters that C has allocated as \texttt{NULL} for us. I've taken the liberty to fill the allocated blocks in as null bytes. 

\subsection{Lab Examples}

I'll also go over the examples that we went over in lab, but a little less in-depth, as they're usually a bunch of concepts put together. We'll focus on what I think are the important portions of each example.

\subsection{Example from Lab - ptr\_review.c}

Here, we'll talk a little bit about\texttt{ptr\_review.c} \newline (This file can be found at \texttt{~/216public/labs/Week4/lab1}) \newline

This is just going over the basics of pointers, and it has a few functions that demonstrate a few things, but I'd just like to go over a few of the questions posed in the actual file.

{
\centering
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

int main(void) {   /* notice use of void in main */                                   
   float *p, *m;   /* have garbage value */                                           
   float pressure; /* has garbage value */                                            
   int area = 10;                                                                     
   int a[3] = {777, 888};  /* missing value? */                                       
                                                                                      
   p = &pressure;  /* & returns address */                                            
   m = p;          /* both m and p point to the same entity */                        
   printf("Value1 %.2f\n", *m); /* are we ever getting a segmentation fault?*/
   
   ...
	
   return 0;
   
}

\end{lstlisting}
}

\begin{itemize}
	\item Using the keyword \texttt{void} in main essentially means that your program will be taking no arguments. That's the long and short of it.
	\item When we define \texttt{p} and \texttt{m} as pointers and don't assign anything to them, they essentially contain garbage values. If you want a visual representation of that, just imagine two pointer variables with arrows pointing into the unknown. We don't know what they're pointing to, nor do we want to find out.
	\item It's the same deal if we define a float without assigning it a value- it contains a garbage value.
	\item When they set \texttt{m} equal to \texttt{p}, they're making it so both pointers are pointing to the same variable. If that confuses you, think of it the other way- pointers contain addresses, and it just so happens that after executing \texttt{m = p;}, both \texttt{m} and \texttt{p} contain the same addresses.
\end{itemize}

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp16429220233511355] 
\draw   (245.67,207) -- (296.67,207) -- (296.67,236.14) -- (245.67,236.14) -- cycle ;
%Straight Lines [id:da051837340435018975] 
\draw    (271.17,221.57) -- (318.07,132.27) ;
\draw [shift={(319,130.5)}, rotate = 477.71] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp5176612453446056] 
\draw   (352.67,207) -- (403.67,207) -- (403.67,236.14) -- (352.67,236.14) -- cycle ;
%Straight Lines [id:da9913485463278986] 
\draw    (378.17,221.57) -- (320.09,132.18) ;
\draw [shift={(319,130.5)}, rotate = 416.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp7874256794735744] 
\draw   (292.67,100) -- (343.67,100) -- (343.67,129.14) -- (292.67,129.14) -- cycle ;

% Text Node
\draw (232,218.67) node   [align=left] {{\fontfamily{pcr}\selectfont m}};
% Text Node
\draw (337,219.67) node   [align=left] {{\fontfamily{pcr}\selectfont p}};
% Text Node
\draw (250,112.67) node   [align=left] {{\fontfamily{pcr}\selectfont pressure}};


\end{tikzpicture}

}

\begin{itemize}
	\item Finally, when it asks if we are ever getting a segfault, the short answer is \textbf{maybe}. In C, dereferencing a pointer that we have not yet initialized is considered \textbf{undefined behavior}. It could provide us with garbage data, give us a segfault because we tried to access corrupted data, or give us a segfault because we tried to access data locked off by the system. We don't really know what will happen in this case, so we're calling it undefined behavior. In grace, variables that aren't initialized are given a value of 0 or NULL, so we won't see this effect here. However, running in any other C environment will yield undefined behavior.
\end{itemize}

\subsection{Example from Lab - ptr\_add\_sub\_overview.c}

Here, we'll talk a little bit about \texttt{ptr\_add\_sub\_overview.c} \newline (This file can be found at\texttt{~/216public/labs/Week4/lab1}) \newline

This example is all about pointer arithmetic, and it relies on the fact that you understand that arrays are stored in contiguous memory. Let's think about the following example. If you had an array that was represented in C memory like this:\newline\newline

{
\centering




\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp5176612453446056] 
\draw   (228.67,212) -- (279.67,212) -- (279.67,241.14) -- (228.67,241.14) -- cycle ;
%Straight Lines [id:da9913485463278986] 
\draw    (254.17,226.57) -- (258.9,132.5) ;
\draw [shift={(259,130.5)}, rotate = 452.88] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp7874256794735744] 
\draw   (234.67,99) -- (285.67,99) -- (285.67,128.14) -- (234.67,128.14) -- cycle ;
%Shape: Rectangle [id:dp04481985338500627] 
\draw   (285.67,99) -- (336.67,99) -- (336.67,128.14) -- (285.67,128.14) -- cycle ;
%Shape: Rectangle [id:dp7253813806088456] 
\draw   (336.67,99) -- (387.67,99) -- (387.67,128.14) -- (336.67,128.14) -- cycle ;
%Shape: Rectangle [id:dp7617124294428573] 
\draw   (387.67,99) -- (438.67,99) -- (438.67,128.14) -- (387.67,128.14) -- cycle ;
%Shape: Rectangle [id:dp12383450763178705] 
\draw   (438.67,99) -- (489.67,99) -- (489.67,128.14) -- (438.67,128.14) -- cycle ;

% Text Node
\draw (213,224.67) node   [align=left] {{\fontfamily{pcr}\selectfont p}};
% Text Node
\draw (260.17,113.57) node   [align=left] {1};
% Text Node
\draw (311.17,113.57) node   [align=left] {6};
% Text Node
\draw (362.17,113.57) node   [align=left] {6};
% Text Node
\draw (413.17,113.57) node   [align=left] {1};
% Text Node
\draw (464.17,113.57) node   [align=left] {2};


\end{tikzpicture}


}


In this case, since arrays are stored in contiguous memory, so essentially what we are claiming with pointer arithmetic is that, if we dereference \texttt{p} now, we will get the number 1. If we \textbf{add} 1 to p (the actual pointer) and then dereference it, we will get the number 6. The file explores similar examples. Here are some highlights.

\begin{itemize}
	\item Just like we discussed earlier, here's an application of simple pointer addition. As a reminder you can add numbers other than 1.
	\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

char name[MAX] = "The House is Blue";                                              
   char *p = name, *q;                                                                
   int i;                                                                             
                                                                                      
   /* You can add and subtract integer values from pointers.   */                     
   /* For example, if you add one to a pointer to a character  */                     
   /* array, the pointer will now be referring to the next     */                     
   /* character.  You can add any integer value (not just one) */                     
                                                                                      
   /* Printing the string using pointer arithmetic */                                 
   while (*p != '\0') {                                                               
      printf("%c", *p);                                                               
      p = p + 1;                                                                      
   }
   
}

\end{lstlisting}

	\item You can also take advantage of the fact that arrays are stored in contiguous memory by subtracting pointers to find 'distance' between them. Note that this only works with pointers of the same type.
	
\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

   /* You can tell how many elements are between two pointers */                      
   /* by subtracting pointers */                                                      
   p = name + 1;                                                                      
   q = &name[5];                                                                      
   printf("Elements #1: %ld\n", q - p);                                               
   printf("Elements #2: %ld\n", p - q);

\end{lstlisting}

\item Finally, you can leverage pointer arithmetic to help you index arrays as well. Here's an example of that below.


\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

   /* Indexing is a pointer operation */                                              
   printf("Indexing as pointer operation\n");                                         
   p = name;                                                                          
   for (i = 0; i < strlen(name); i++) {                                               
      printf("%c\n", p[i]);                                                           
   }

\end{lstlisting}

	
\end{itemize}

\subsection{Example from Lab - str\_review.c}

Here, we'll talk a little bit about\texttt{str\_review.c} \newline (This file can be found at \texttt{~/216public/labs/Week4/lab1}) \newline

This example is pretty light compared to the rest- and it is just a review of how strings are stored in C. The main overarching concept you need to understand here is two things:

\begin{itemize}
	\item Strings are not given an actual data type in C. They are simply arrays of characters with a small caveat.
	\item That being said, strings are always stored in a certain way. They are a character array terminated with a null byte. (No null byte at the end means you don't have a string- you have a regular old character array)
\end{itemize}

Take a look at my String example above for the memory map representation.

\subsection{Using getchar() and putchar()}

The two functions \texttt{getchar} and \texttt{putchar} are pretty curious, in that we have much more functional replacements for them- \texttt{scanf} and \texttt{printf}, respectively. However, learning these is a cool way to prep yourself for how basic I/O in assembly works, so I think that it's worth it to at least gloss over these for now. \newline

Let's look over the code provided for us in discussion and touch on the main points.

\begin{lstlisting}[language=C]
// example from Nelson Padua-Perez

#include <stdio.h>                                                                    
                                                                                      
#define MAX_LEN 80                                                                    
                                                                                      
int main() {                                                                          
   char value[MAX_LEN + 1];                                                           
   int letter; /* Why integer? */                                                     
                                                                                      
   printf("Enter a letter: ");                                                        
   scanf("%1s", value);                                                               
   printf("Value entered: \"%s\"\n", value);                                          
   getchar();   /* getchar() reads a single character; why we need it? */             
   printf("Enter a letter: ");                                                        
   letter = getchar();                                                                
   printf("Letter entered: ");                                                        
   putchar(letter);      /* putchar() prints a single character */                    
   printf("\n");                                                                      
                         /* try ungetc to put characters back */                      
                                                                                      
   return 0;                                                                          
}  
\end{lstlisting}

\begin{itemize}
	\item First of all, both \texttt{getchar} and \texttt{putchar} deal with integers, despite the fact that they are meant to take in/print characters. Don't let this confuse you, they're simply storing them by the ASCII value.
	\item Both of these get and print a single character, and in my opinion, there's no real reason to need them except in very special cases, but this is how I/O will be conducted in Assembly, so I think it's worth taking a look at this now.
	\item Your main takeaway from this should be that \texttt{getchar} and \texttt{putchar} are functions that we can use to do I/O in C, and even though they're a little more crude than we'd like for most applications, they still exist, and are helpful tools when we're trying to understand Assembly.
\end{itemize}

\section{Week 5}

\subsection{Grep - A 'CTRL-F' From the Command Line}

When working with the command line, we have the unique opportunity to see older versions of computer tools that we are accustomed to today. In modern environments, if you want to find something on a webpage, textbook, or even in your \texttt{.java} file in Eclipse, the first thing that probably comes to you head is the command '\texttt{CTRL + F}'. In a command line environment, the command that preceded this functionality is known as \texttt{grep}. 

\subsubsection{Why is it called that?}
The name of the command itself has an interesting origin. The most basic text editor on UNIX systems is regarded by many as \texttt{ed}, and on that text editor, one was able to globally search the file for a regular expression (which you'll learn morere about in CMSC330), then print what was found using the command '\texttt{g/re/p}'. This gave way to the name "grep".

\subsubsection{Why it's useful}

As you'd imagine, grep can be used to simply search the files we have for keywords. Let's take a look at some examples. You can follow along if you head over to \texttt{216public/labs/Week5/lab 1/grep\_example}.

Let's take a look at the text files that we will be searching through, as examples.

\begin{lstlisting}[language=C]
The college is in
the east coast.  
\end{lstlisting}
\begin{center}
\textbf{data.txt}
\end{center}


\begin{lstlisting}[language=C]
The project is about hashing,
files, structures,
pointers
and dynamic memory allocation (and more pointers).  
\end{lstlisting}
\begin{center}
\textbf{summary.txt}
\end{center}


These two files are in the same directory, and for the purpose of the examples I'll go over, let's assume that we're currently in the directory that contains both these files.\newline

\texttt{grep} works like this: you provide it a key phrase and a file location, and it'll take care of the rest. If you want more technical information on how grep commands should be structured, I encourage you to take a look at \texttt{man grep}. \newline

If you execute the command \texttt{grep college data.txt}, then grep will print out the line that it found your keyword on. (the output for that command will be \texttt{The college is in}.)\newline

Where \texttt{grep} really shines is when you want to mix in some of the cool UNIX keywords we've been learning. As a quick example, let's say you wanted to search for all the occurrences of 'is' in all the text files you had in the file. To do that, you'd simply execute the following command.\newline

\texttt{grep is *}\newline

That would yield the following:\newline

\texttt{data.txt:The college is in\newline
summary.txt:The project is about hashing,
}\newline

In a more practical example, let's think about how you could use this when writing your projects. Let's say you had a particularly tough project with 20 public tests. You're failing a bunch of them, but you suspect it's because the tests are calling a function you know you haven't implemented properly yet, named \texttt{get\_classroom\_number()}.\newline

Assuming that public test files are named as they usually are in this class, and that you're in your project directory, if you wanted to figure out which public tests were testing for the \texttt{get\_classroom\_number()} function, all you have to do is cook up a \texttt{grep} command to do that for you. Here's what we'd be looking at in this case:\newline

\texttt{grep get\_classroom\_number() public*}\newline

This would search for the keyword \texttt{get\_classroom\_number()} in every file that started with 'public', which is exactly what we want. (Remember your UNIX special characters!). Additionally, here's one extra little trick that might make grepping a little bit easier- if you want to see the line numbers that your searches actually appear on, go ahead and use the \texttt{-n} flag when you run grep. The previous example would then look like this:\newline

\texttt{grep -n get\_classroom\_number() public*}

\subsection{Memcpy, Memmove, and Memset}

In C, we sometimes want to simply just manipulate blocks of memory. Although we were previously able to do this with strings, we can also do this at a much less abstracted level, and just mess with the memory itself.\newline

I suggest that you follow along using the lab example named \texttt{mem\_cpy\_set.c} located at: \newline \texttt{216public/labs/Week5/lab 1}

\begin{itemize}
	\item \textbf{\texttt{void *memcpy(void *dest, const void *src, size\_t n)}} - memcpy is a function that simply copies memory from one block to another, and that's the gist of it. The two main uses we have for this are to (1) copy strings from one location to another (but for this case, you're probably better off using strcpy or strncpy) and (2) to copy structs from one location to another. As you can see, the function asks for an unsigned integer 'n', which we can usually mark off as the \texttt{sizeof(struct\_you\_want\_to\_copy)}.
	\item \textbf{\texttt{void *memmove(void *dest, const void *src, size\_t n)}} - This one is basically the same as memcpy, but you'll want to use this when the memory you need to copy \textbf{to} overlaps with the memory you want to copy \textbf{from}.
	\item \textbf{\texttt{void *memset(void *str, int c, size\_t n)}} - This is a pretty niche command, and the gist of it is this. It'll take the block of memory that you specify, and set it all to a certain value that you specify. I can see this being useful if you wanted to set all the values in a contiguous array to the number '1' as a default value, or something like that.\newline

\end{itemize}

As a final side note, you can get more information on all three of these functions by using \texttt{man}. However, you will need to provide the '3' flag when you invoke the man command, so your commands would look like the following.

\begin{itemize}
	\item \texttt{man 3 memcpy}
	\item \texttt{man 3 memset}
	\item \texttt{man 3 memmove}
\end{itemize}

\section{Week 6}

This week is a quiz week, so we held open office hours during discussion and answered specific questions. Honestly, for reviews for quizzes, I would highly recommend checking Piazza for the answers and clarifications that you're looking for. In this guide, since we really just went over specifics during discussion before the quiz, I'm going to skip over this and get straight to what we covered after the quiz.

\subsection{Preprocessor}

To follow along with these notes, I'd recommend taking a look at '\texttt{PreprocessorI.pdf (Lab)} from the Week 6 section on the 'Schedule' page of the course website.\newline

Here, we'll be talking a little bit about C's preprocessing and compiling. Preprocessing is essentially the stuff that C provides for your code right before it compiles, e.g. replacing macros with their appropriate text values.

\subsubsection{Compiling a C Program}

When you compile a C program, a few things happen behind the scenes. First, a source file (\texttt{.c}) is compiled into an object file (\texttt{.o}). Think of the object file as an intermediary step between a C file and an executable. An object file isn't necessarily an executable let, but it's about halfway there. This'll help us a lot more when we talk about \texttt{make}, but for now, that's all you really need to remember.\newline

After an object file is created, it can be compiled into an executable, which is usually done by the linker. Essentially, the linker just does some cleanup work with symbols that you've defined, global variables, and other data.\newline


{
\centering






\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Flowchart: Process [id:dp9087722479160656] 
\draw   (100,59) -- (180,59) -- (180,129) -- (100,129) -- cycle ;
%Flowchart: Process [id:dp18707723736432025] 
\draw   (215.33,59) -- (295.33,59) -- (295.33,129) -- (215.33,129) -- cycle ;
%Flowchart: Process [id:dp26379991992077745] 
\draw   (330.67,59) -- (410.67,59) -- (410.67,129) -- (330.67,129) -- cycle ;
%Straight Lines [id:da45725440322215305] 
\draw    (179.67,94) -- (213,94) ;
\draw [shift={(215,94)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da739474493577637] 
\draw    (295.67,94) -- (329,94) ;
\draw [shift={(331,94)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (140,94) node   [align=left] {{\fontfamily{pcr}\selectfont {\small source file}}};
% Text Node
\draw (255.33,94) node   [align=left] {{\fontfamily{pcr}\selectfont {\small object file}}};
% Text Node
\draw (370.67,94) node   [align=left] {{\small {\fontfamily{pcr}\selectfont executable}}};


\end{tikzpicture}



}

\subsubsection{Preproccessor Defined Symbols}

There are a few symbols that C will recognize and replace with text during preprocessing. For example, typing \texttt{\_\_DATE\_\_} in your C file will cause C to replace it with the date of compilation when you actually compile your program. Here's a list of these macros. (I've decided to exclude \texttt{\_\_STDC\_\_} only because we basically never see a use for it during 216.

\begin{itemize}
	\item \textbf{\texttt{\_\_FILE\_\_}} $\rightarrow$ filename of the source file that this macro is in.
	\item \textbf{\texttt{\_\_LINE\_\_}} $\rightarrow$ the line number that this macro is typed on. I've used this for debugging before- for example, let's say you're using a bunch of print statements throughout your code to see where it got to before a segfault. Instead of printing something like 'got here' for every statement, maybe write something where you \texttt{printf} something with \texttt{\_\_LINE\_\_} in it, then copy paste that statement into your code a bunch of times. It's a super easy way to see how far you get.
	\item \textbf{\texttt{\_\_DATE\_\_}} $\rightarrow$ the date of compilation. Not much to say here, it's more gimmicky than anything.
	\item \textbf{\texttt{\_\_TIME\_\_}} $\rightarrow$ same as above, except it's the time of compilation.
\end{itemize}

I would think of these like your \texttt{\#define} keywords. In this case, C is just looking for these particular strings, and replacing them with their corresponding replacements. These are useful mainly only for niche cases, like if you wanted your code to print out when it was compiled.\newline

Also, you've probably seen this a bunch by now, but \texttt{\#define} is basically just telling the C compiler to find all occurrences of one thing, and replace it with another thing. For example, doing something like \texttt{\#define MAX\_CHAR\_AMT 80} would cause the C compiler to find every occurrence of the string '\texttt{MAX\_CHAR\_AMT}' in your code and replace it with \texttt{80}. In that sense, the most prominent use for this in 216 is to define maximum size limits. If you need a reference, most projects will have these limits defined either in the base C files or the header files that they provide.

\subsubsection{Conditional Compilation}

Conditional compilation is an interesting topic, and I think the slides explain it pretty well. However, I think there are simpler examples than what's provided in the slides that'll help us understand it on a basic level.\newline

I suggest taking a look at \texttt{\href{https://www.programmingsimplified.com/c/tutorial/conditional-compilation}{https://www.programmingsimplified.com/c/tutorial/conditional-compilation}} for a really simple example that'll get you started.\newline

The main use of conditional compilation is basically that- if code should be written the same (i.e. the same C file) on two systems, but should be compiled differently based on other files that influence it or the system it's being compiled on, then conditional compilation is what you need. We don't see too much of this stuff in your projects, but it's good to know in case it pops up on an exam.

\subsubsection{File Inclusion}

File inclusion is sort of a self explanatory topic. Although we go over it formally in discussion and the preprocessor slides, I think the best way to understand this is to see real world examples. Luckily, you've done a few projects so far, and they're essentially working examples of how file inclusion should be done in C. For this topic, I invite you to take a look at your projects and see where header files are included, if there's ever multiple header files included, and, if you really want to explore, feel free to go back and mess with old projects. Change header files around, try to make a C file include multiple header files, change the order in which they're included, etc. You've been working with file inclusion this whole time, so feel free to experiment a bit with it and really get familiar. That, plus the theoretical background that the slides provide should be all you need.

\section{Week 7}

This week, we're going over new things after the Exam. We'll talk a little about Make, which allows us to easily compile our projects in C, Struct Abstraction, which is about as far as C goes in terms of emulating object oriented features, and dynamic memory allocation.

\subsection{Make}

To follow along with these notes, I'd recommend taking a look at '\texttt{Make.pdf (Lab)} from the Week 7 section on the 'Schedule' page of the course website.\newline

Before, if you wanted to compile a bunch of files at once, you'd just toss them all into one gcc command, like so:\newline

\texttt{gcc hashtable.c public01.c}\newline

Now this is fine, but as you can imagine, if you have a much larger C project with plenty of files (some depending on others, some not depending on others), you might run into some issues if you have to manually \texttt{gcc} everything each time you want to run your code. Luckily, C's got a solution for you!\newline

\subsubsection{Compiling into Object Code First}

Just a little note before we get into it- we've been skipping a step in terms of how code gets compiled. Just like I talked about above,  in the Preprocessor section, C gets compiled from source code to an object file to an executable, and so far, we've just been compiling straight from source code to executable. In order to fully understand \texttt{make}, we're going to want to note that we will now be compiling first into object files, then into source code.

\subsubsection{Dependencies}

First thing you need to know about \texttt{make}- it's all about dependencies. Let's say we had some C files, and for this example, let's go ahead and take a look at the example that they provide in the slides.\newline

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp04584351351591953] 
\draw   (300.5,51) -- (379.5,51) -- (379.5,79.5) -- (300.5,79.5) -- cycle ;
%Shape: Rectangle [id:dp869537413731065] 
\draw   (222.5,121) -- (301.5,121) -- (301.5,149.5) -- (222.5,149.5) -- cycle ;
%Shape: Rectangle [id:dp09744507127214364] 
\draw   (380.5,120.5) -- (459.5,120.5) -- (459.5,149) -- (380.5,149) -- cycle ;
%Shape: Rectangle [id:dp6441175322103412] 
\draw   (300.5,172) -- (379.5,172) -- (379.5,200.5) -- (300.5,200.5) -- cycle ;
%Shape: Rectangle [id:dp970334445840234] 
\draw   (161.5,169.5) -- (240.5,169.5) -- (240.5,198) -- (161.5,198) -- cycle ;
%Shape: Rectangle [id:dp4273912861487811] 
\draw   (441,169.5) -- (520,169.5) -- (520,198) -- (441,198) -- cycle ;
%Straight Lines [id:da5700845683815001] 
\draw    (338,79.75) -- (265.25,120.28) ;
\draw [shift={(263.5,121.25)}, rotate = 330.88] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da1587431355483161] 
\draw    (338,79.75) -- (421.69,119.39) ;
\draw [shift={(423.5,120.25)}, rotate = 205.35] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da7368979653415088] 
\draw    (262,150.25) -- (205.4,168.63) ;
\draw [shift={(203.5,169.25)}, rotate = 342.01] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da015222657466875456] 
\draw    (262,150.25) -- (339.57,171.72) ;
\draw [shift={(341.5,172.25)}, rotate = 195.47] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da20417970212364012] 
\draw    (420.5,149.25) -- (343.42,171.69) ;
\draw [shift={(341.5,172.25)}, rotate = 343.77] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da3319626117155393] 
\draw    (420.5,149.25) -- (478.09,167.64) ;
\draw [shift={(480,168.25)}, rotate = 197.71] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (340,65.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX}};
% Text Node
\draw (262,135.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.o}};
% Text Node
\draw (420,134.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.o}};
% Text Node
\draw (340,186.25) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.h}};
% Text Node
\draw (480.5,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.c}};
% Text Node
\draw (203.5,184.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.c}};


\end{tikzpicture}


}

\subsubsection{A Broad Overview of Public Tests with Make}

As you can see, we have a pretty solid dependency tree here. Main takeaways: C files (the source files) are generally at the bottom of the tree, and they (combined with H files) compile into O files. To reiterate, (C) source files combine with (H) header files as they're compiled, and they become (O) object files. These object files are then compiled into one big executable, so you can run it very easily. The reason I like this provided example so much is because it's very similar to the public tests that you're provided in your projects. You've got \texttt{puzzles.c}, which we can say is like the file that you'll usually fill out and write yourself. You've got \texttt{puzzles.h}, which we can assume is some file full of constants and function prototypes that was probably provided to you when you copied the project over from \texttt{216public}, and finally, you've got \texttt{publicX.c}, which is the public test you're trying to run. In this case, in order for \texttt{publicX} to be created, the \texttt{make} utility has to combine the data from \texttt{publicX.c}, \texttt{puzzles.h}, and \texttt{puzzles.c}.\newline

Let's go over the questions provided in the slides.\newline

\begin{itemize}
	\item \textbf{What needs to be compiled if \texttt{publicX.c} is changed?}\newline
		
		

\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp04584351351591953] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ] (300.5,51) -- (379.5,51) -- (379.5,79.5) -- (300.5,79.5) -- cycle ;
%Shape: Rectangle [id:dp869537413731065] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (222.5,121) -- (301.5,121) -- (301.5,149.5) -- (222.5,149.5) -- cycle ;
%Shape: Rectangle [id:dp09744507127214364] 
\draw   (380.5,120.5) -- (459.5,120.5) -- (459.5,149) -- (380.5,149) -- cycle ;
%Shape: Rectangle [id:dp6441175322103412] 
\draw   (300.5,172) -- (379.5,172) -- (379.5,200.5) -- (300.5,200.5) -- cycle ;
%Shape: Rectangle [id:dp970334445840234] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (161.5,169.5) -- (240.5,169.5) -- (240.5,198) -- (161.5,198) -- cycle ;
%Shape: Rectangle [id:dp4273912861487811] 
\draw   (441,169.5) -- (520,169.5) -- (520,198) -- (441,198) -- cycle ;
%Straight Lines [id:da5700845683815001] 
\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ]   (338,79.75) -- (265.25,120.28) ;
\draw [shift={(263.5,121.25)}, rotate = 330.88] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da1587431355483161] 
\draw    (338,79.75) -- (421.69,119.39) ;
\draw [shift={(423.5,120.25)}, rotate = 205.35] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da7368979653415088] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (262,150.25) -- (205.4,168.63) ;
\draw [shift={(203.5,169.25)}, rotate = 342.01] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da015222657466875456] 
\draw    (262,150.25) -- (339.57,171.72) ;
\draw [shift={(341.5,172.25)}, rotate = 195.47] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da20417970212364012] 
\draw    (420.5,149.25) -- (343.42,171.69) ;
\draw [shift={(341.5,172.25)}, rotate = 343.77] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da3319626117155393] 
\draw    (420.5,149.25) -- (478.09,167.64) ;
\draw [shift={(480,168.25)}, rotate = 197.71] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (340,65.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX}};
% Text Node
\draw (262,135.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.o}};
% Text Node
\draw (420,134.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.o}};
% Text Node
\draw (340,186.25) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.h}};
% Text Node
\draw (480.5,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.c}};
% Text Node
\draw (201,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.c}};


\end{tikzpicture}\newline

	Well, since we're changing the \texttt{.c} source file, we can safely assume that the object file that it will eventually become needs to be recompiled, so let's travel up one node on the dependency tree and mark that as 'need to be recompiled'. However, it doesn't stop there. \newline
	
	

\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp04584351351591953] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (300.5,51) -- (379.5,51) -- (379.5,79.5) -- (300.5,79.5) -- cycle ;
%Shape: Rectangle [id:dp869537413731065] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (222.5,121) -- (301.5,121) -- (301.5,149.5) -- (222.5,149.5) -- cycle ;
%Shape: Rectangle [id:dp09744507127214364] 
\draw   (380.5,120.5) -- (459.5,120.5) -- (459.5,149) -- (380.5,149) -- cycle ;
%Shape: Rectangle [id:dp6441175322103412] 
\draw   (300.5,172) -- (379.5,172) -- (379.5,200.5) -- (300.5,200.5) -- cycle ;
%Shape: Rectangle [id:dp970334445840234] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (161.5,169.5) -- (240.5,169.5) -- (240.5,198) -- (161.5,198) -- cycle ;
%Shape: Rectangle [id:dp4273912861487811] 
\draw   (441,169.5) -- (520,169.5) -- (520,198) -- (441,198) -- cycle ;
%Straight Lines [id:da5700845683815001] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (338,79.75) -- (265.25,120.28) ;
\draw [shift={(263.5,121.25)}, rotate = 330.88] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da1587431355483161] 
\draw    (338,79.75) -- (421.69,119.39) ;
\draw [shift={(423.5,120.25)}, rotate = 205.35] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da7368979653415088] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (262,150.25) -- (205.4,168.63) ;
\draw [shift={(203.5,169.25)}, rotate = 342.01] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da015222657466875456] 
\draw    (262,150.25) -- (339.57,171.72) ;
\draw [shift={(341.5,172.25)}, rotate = 195.47] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da20417970212364012] 
\draw    (420.5,149.25) -- (343.42,171.69) ;
\draw [shift={(341.5,172.25)}, rotate = 343.77] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da3319626117155393] 
\draw    (420.5,149.25) -- (478.09,167.64) ;
\draw [shift={(480,168.25)}, rotate = 197.71] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (340,65.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX}};
% Text Node
\draw (262,135.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.o}};
% Text Node
\draw (420,134.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.o}};
% Text Node
\draw (340,186.25) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.h}};
% Text Node
\draw (480.5,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.c}};
% Text Node
\draw (201,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.c}};


\end{tikzpicture}\newline

Since we recompiled the object file that needs to ultimately be compiled into \texttt{publicX}, we can also assume that it needs to be recompiled as well.\newline

At this point, we're done. We've done all the recompiling that we need to for this particular case, and since we haven't changed any of the dependencies for \texttt{puzzles.o}, we can see that it wasn't affected, and therefore, does not need to be recompiled. Let's solve the other questions in a similar manner.\newline

	\item \textbf{What needs to be compiled if \texttt{puzzles.c} is changed?}\newline
	
	This actually ends up working the same way as the previous example, just on a different side of the tree. Take a look.\newline
	
	

\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp04584351351591953] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (300.5,51) -- (379.5,51) -- (379.5,79.5) -- (300.5,79.5) -- cycle ;
%Shape: Rectangle [id:dp869537413731065] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ] (222.5,121) -- (301.5,121) -- (301.5,149.5) -- (222.5,149.5) -- cycle ;
%Shape: Rectangle [id:dp09744507127214364] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (380.5,120.5) -- (459.5,120.5) -- (459.5,149) -- (380.5,149) -- cycle ;
%Shape: Rectangle [id:dp6441175322103412] 
\draw   (300.5,172) -- (379.5,172) -- (379.5,200.5) -- (300.5,200.5) -- cycle ;
%Shape: Rectangle [id:dp970334445840234] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ] (161.5,169.5) -- (240.5,169.5) -- (240.5,198) -- (161.5,198) -- cycle ;
%Shape: Rectangle [id:dp4273912861487811] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (441,169.5) -- (520,169.5) -- (520,198) -- (441,198) -- cycle ;
%Straight Lines [id:da5700845683815001] 
\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ]   (338,79.75) -- (265.25,120.28) ;
\draw [shift={(263.5,121.25)}, rotate = 330.88] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da1587431355483161] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (338,79.75) -- (421.69,119.39) ;
\draw [shift={(423.5,120.25)}, rotate = 205.35] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da7368979653415088] 
\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ]   (262,150.25) -- (205.4,168.63) ;
\draw [shift={(203.5,169.25)}, rotate = 342.01] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da015222657466875456] 
\draw    (262,150.25) -- (339.57,171.72) ;
\draw [shift={(341.5,172.25)}, rotate = 195.47] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da20417970212364012] 
\draw    (420.5,149.25) -- (343.42,171.69) ;
\draw [shift={(341.5,172.25)}, rotate = 343.77] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da3319626117155393] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (420.5,149.25) -- (478.09,167.64) ;
\draw [shift={(480,168.25)}, rotate = 197.71] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (340,65.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX}};
% Text Node
\draw (262,135.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.o}};
% Text Node
\draw (420,134.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.o}};
% Text Node
\draw (340,186.25) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.h}};
% Text Node
\draw (480.5,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.c}};
% Text Node
\draw (201,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.c}};


\end{tikzpicture}\newline

	Now you may notice that the recurring theme here is that \texttt{publicX} is always recompiled. This is fine! It's intentional! It only makes sense that if we're changing some of the source to what's going to end up in our final executable, our executable needs to be recompiled. The real issue that \texttt{make} is solving for us here is that \textbf{not everything on the lower limbs of the dependency tree needs to be recompiled if we change just one or two little source files}.
	
	\item \textbf{What needs to be compiled if \texttt{puzzles.h} is changed?}\newline
	
	Now this is the big one. If you'll notice on the tree, just about all of our object files and executable depend on \texttt{puzzles.h}. Let's confirm this by drawing and highlighting our dependency tree once again.\newline
	
	

\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp04584351351591953] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (300.5,51) -- (379.5,51) -- (379.5,79.5) -- (300.5,79.5) -- cycle ;
%Shape: Rectangle [id:dp869537413731065] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (222.5,121) -- (301.5,121) -- (301.5,149.5) -- (222.5,149.5) -- cycle ;
%Shape: Rectangle [id:dp09744507127214364] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (380.5,120.5) -- (459.5,120.5) -- (459.5,149) -- (380.5,149) -- cycle ;
%Shape: Rectangle [id:dp6441175322103412] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (300.5,172) -- (379.5,172) -- (379.5,200.5) -- (300.5,200.5) -- cycle ;
%Shape: Rectangle [id:dp970334445840234] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ] (161.5,169.5) -- (240.5,169.5) -- (240.5,198) -- (161.5,198) -- cycle ;
%Shape: Rectangle [id:dp4273912861487811] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ] (441,169.5) -- (520,169.5) -- (520,198) -- (441,198) -- cycle ;
%Straight Lines [id:da5700845683815001] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (338,79.75) -- (265.25,120.28) ;
\draw [shift={(263.5,121.25)}, rotate = 330.88] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da1587431355483161] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (338,79.75) -- (421.69,119.39) ;
\draw [shift={(423.5,120.25)}, rotate = 205.35] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da7368979653415088] 
\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ]   (262,150.25) -- (205.4,168.63) ;
\draw [shift={(203.5,169.25)}, rotate = 342.01] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da015222657466875456] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (262,150.25) -- (339.57,171.72) ;
\draw [shift={(341.5,172.25)}, rotate = 195.47] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da20417970212364012] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (420.5,149.25) -- (343.42,171.69) ;
\draw [shift={(341.5,172.25)}, rotate = 343.77] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da3319626117155393] 
\draw [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ]   (420.5,149.25) -- (478.09,167.64) ;
\draw [shift={(480,168.25)}, rotate = 197.71] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (340,65.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX}};
% Text Node
\draw (262,135.25) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.o}};
% Text Node
\draw (420,134.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.o}};
% Text Node
\draw (340,186.25) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.h}};
% Text Node
\draw (480.5,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont puzzles.c}};
% Text Node
\draw (201,183.75) node   [align=left] {{\fontfamily{pcr}\selectfont publicX.c}};


\end{tikzpicture}\newline

	Even though we didn't change any of the \texttt{.c} files, we changed one of the key nodes in our dependency tree, and for that, we have paid the price. Since both of our object files and ultimately our executable depends on these files, it looks like everything needs to be recompiled after our changes to \texttt{puzzles.h}.


\end{itemize}

So that's how we deal with compilation in makefiles. I invite you to take a look at your old projects that have makefiles in them and change some files around and keep running \texttt{make}. Try drawing your own dependency trees and seeing what recompiles when you make edits to different files. Once you do that enough, you should be ready for any \texttt{make}-related stuff that pops up on an exam.\newline

For more nitty-gritty details on \texttt{make}, definitely take a look at the slides, they have the information you need. However, more or less, exams will probably ask you to either cook up a makefile on your own or decide what will be recompiled if you change some files. I want to make sure that you get the basic concept of all this, so as long as you do what I detail above and remember some of the key points from the slides, you should be in very good shape for exams.

\subsubsection{Makefile Examples}

By popular demand, here's a section on how to make your own Makefile. I'm going to walk us through the example in the 'Make' slides, and give us an example from a project that was just due.\newline

First, let's go through the example for the tree I've drawn out above. Like we talked about earlier, let's look at the main components. We have:

\begin{itemize}
	\item \textbf{\texttt{publicX}} $\rightarrow$ our main executable. This one's going to require everything else to be built in order for it to work.
	\item \textbf{\texttt{publicX.o} and \texttt{puzzles.o}} $\rightarrow$ the object files, the aggregate of the \texttt{.c} and the \texttt{.h} files. These are going to need the C script files and header files to be compiled in order to be built.
	\item \textbf{\texttt{publicX.c}, \texttt{puzzles.h}, and \texttt{puzzles.c}} $\rightarrow$ the C script and header files, this is where our work ends and the compiler's starts. We need to start off making targets for these, then take care of the elements on the tree that point to them from there.
\end{itemize}

Taking this into account, let's start by creating an empty file called \texttt{Makefile}. \newline

Something you should keep in mind when creating Makefiles is that there shouldn't be 'rules' for the C script or header files. We don't need to define any rules for C to 'compile' the C files or the H files because we're the ones who wrote them. We should therefore start with the object files. Here are the first targets we're going to add to our Makefile.

\begin{lstlisting}[language=bash]
publicX.o: publicX.c puzzles.h
	gcc -c publicX.c 
	
puzzles.o: puzzles.c puzzles.h
	gcc -c puzzles.c
\end{lstlisting}

Now that we've got our C files, H files, and object files covered, let's move up the tree. In this case, the next step is pretty clear. We've taken care of the middle level of the 'make tree', now we just need to get to the remaining level. In other words, we need to add the target for the \texttt{publicX} executable, which will be built from the object files.

\begin{lstlisting}[language=bash]
publicX: publicX.o puzzles.o
	gcc-o publicX publicX.o puzzles.o

publicX.o: publicX.c puzzles.h
	gcc -c publicX.c 
	
puzzles.o: puzzles.c puzzles.h
	gcc -c puzzles.c
\end{lstlisting}

Notice how we're using the \texttt{-o} flag when calling gcc for the executable. Make sure that you don't miss that step. When you're using \texttt{gcc} on C script files and header files, use the \texttt{-c} flag as you usually would. When you're using \texttt{gcc} on object files, make sure to use the \texttt{-o} flag.\newline

Now, let's take a look at a more practical example. Namely, the \texttt{Makefile} included with project 3. By analyzing this, you should be more or less set to create a \texttt{Makefile} for project 4.\newline

However, and this is important, don't use the actual targets and rules in project 3's \texttt{Makefile} as examples to copy over to project 4. They make use of \textbf{implicit rules, which are not allowed in project 4}.\newline

Instead, I want to talk about the other features of the project 3 \texttt{Makefile}, which you'll find indispensable when creating your own \texttt{Makefile} for project 4.\newline

First, notice the lines for \texttt{CC, CFLAGS, and PROGS}.

\begin{lstlisting}[language=C]
CC = gcc
CFLAGS = -ansi -Wall -g -O0 -Wwrite-strings -Wshadow \
         -pedantic-errors -fstack-protector-all 
PROGS = user_interface public01 public02 public03 public04 public05 \
	public06 public07 public08 public09
\end{lstlisting}

This is basically like \#define, but for your \texttt{Makefile}. Whenever you invoke these keywords later in your file, you'll get the lengthy version on the right side of their corresponding equals sign. You'd invoke them like the following example from the same \texttt{Makefile}.

\begin{lstlisting}[language=C]
all: $(PROGS)
\end{lstlisting}

Here, you can see that the \texttt{all} target refers to everything included in the \texttt{PROGS} macro that was defined above. This is another keyword to remember- make sure to include a target for \texttt{all} that basically compiles everything in your project. This keyword marks the stuff that'll be compiled if the user just types \texttt{make} with nothing else after it- in other words, it's where you'd setup the default \texttt{make} process.\newline

Let's talk about the other special targets in the project 3 \texttt{Makefile}, as I've spliced from the file below.

\begin{lstlisting}[language=C]
.PHONY: all clean

all: $(PROGS)

clean:
	rm -f *.o $(PROGS) *.tmp

\end{lstlisting}

We've already talked about \texttt{all}, so let's address \texttt{clean} and \texttt{.PHONY}. First, \texttt{clean}- this means exactly what you think it means. The role of the clean target is to remove all the stuff that \texttt{make} created when it was run. In other words, if you run \texttt{make clean}, it's expected that you have code in your \texttt{Makefile}'s \texttt{clean} target that performs the appropriate \texttt{rm} command on all the files that it would have otherwise been producing. This includes all object files and executables, and in the case of this implementation, all temporary files (\texttt{.tmp}).\newline

\texttt{.PHONY} is also pretty simple once you understand what it means- it's sometimes the case where you'd (albeit, making a terrible design choice) have an executable file named 'clean', or 'all', and you'd want to make targets to produce them. In that case, you would like the \texttt{make} utility to know that those are, in fact, targets for executables that you're looking to produce, and not the rules you've defined for the special keywords \texttt{all} and \texttt{clean}. In other words, you're just telling \texttt{Make} to ignore your silly file naming and to continue with business as usual. Some more common tags that could be put in your \texttt{.PHONY} rule include the following: \texttt{install, info, check, distclean, TAGS}. You are welcome to google them if you'd like, but we won't see any of those other tags in 216.


\subsection{Struct Abstraction}

For this section, we'll be talking about Struct Abstraction. For reference, this material can be found at:\newline 

\texttt{216public/labs/Week7/lab2/struct\_abstraction} \newline

I suggest you take a look at the README like we did in discussion, but to get a broad overview of this concept, I want to add a little of my own insight. \newline

Java babied us a lot with its object oriented features and other conveniences, but you'll find that C is a lot less scaffolded. In other words, C does not provide us with the same conveniences that Java does. Struct Abstraction is a fairly niche topic, but it's essentially a reminder to us that we can \textit{sort of} emulate an object oriented feature of Java by naming a struct, yet hiding its implementation. Personally, I haven't found a particular use for it in my 216 projects, but I think it's good knowledge to have. Take a look at the README and work through the example like we did in class, but other than that, make sure you know the gist of it: It's a neat little trick in C that allows us to kind of emulate object oriented behavior by 'hiding' the implementation of a struct.

\subsection{Dynamic Memory Allocation (Review)}

Dynamic memory allocation is one of the most important topics in C, and usually one of the hardest for students to understand. If you haven't fully understood this yet, I would highly suggest either referring back to your lecture notes for the subject, watching older 216 lecture videos on the topic online, or looking at reference material from elsewhere. This will only serve as a quick review + some of my extra insight.\newline

For this section, we'll be looking at the reference material found in the following location:\newline

\texttt{public/labs/Week7/lab2}

\subsubsection{Malloc() vs. Calloc()}

I remember this came up as an exam question during my year, so I think this is an important distinction to remember. When you're looking at allocating memory in C, there are two ways to ask C's memory manager for the space that you need. I like to think of this with the hotel room analogy. When you use \texttt{malloc()}, it's like you've arrived at a hotel and ask the clerk to give you a room (and of course, for the sake of the analogy, let's say you provided a size for the room). Nevermind if it's clean or not, and you don't care what the previous guests left in the room. You just want to know that you have the room, and you'll take care of cleaning it and setting your friends up in it later. \texttt{malloc()} is a function that gives you the memory you're looking for, but it doesn't bother cleaning it out for you- the values at the pointer that \texttt{malloc()} returns can be just about anything- so it's a solid idea not to dereference whatever's there. Now if you use \texttt{calloc()}, that's a different story. That's like asking the clerk for a room, but also adding, "Hey, can you make sure it's cleaned spotless for me?". That way, everything in that room is set to a nice default value and is nice and ready for you to look at- no need to clean it. For example, using \texttt{malloc()} for a string and printing it is a terrible idea, but using \texttt{calloc()} for a string and printing it will work totally fine, as the latter sets the memory to default values.

\subsubsection{Two Pointers to the Same Memory}

C's memory manager isn't smart, but it isn't stupid. If you have two pointers to the same memory that you allocated, using \texttt{free()} to return that chunk of memory to the C memory manager will totally work. Here's an example.\newline

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp7660242978805989] 
\draw   (152.5,144.5) -- (222.5,144.5) -- (222.5,184.5) -- (152.5,184.5) -- cycle ;
%Shape: Rectangle [id:dp9835474491940359] 
\draw   (327.5,68) -- (397.5,68) -- (397.5,108) -- (327.5,108) -- cycle ;
%Shape: Rectangle [id:dp6382246899126394] 
\draw   (397.5,68) -- (467.5,68) -- (467.5,108) -- (397.5,108) -- cycle ;
%Shape: Rectangle [id:dp40751687076886434] 
\draw   (467.5,68) -- (537.5,68) -- (537.5,108) -- (467.5,108) -- cycle ;
%Shape: Rectangle [id:dp1956486484356338] 
\draw   (537.5,68) -- (607.5,68) -- (607.5,108) -- (537.5,108) -- cycle ;
%Straight Lines [id:da2803570019045192] 
\draw    (187.5,164.5) -- (326.25,88.21) ;
\draw [shift={(328,87.25)}, rotate = 511.2] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (116,162.5) node   [align=left] {{\fontfamily{pcr}\selectfont ptr\_1}};
% Text Node
\draw (453,49) node   [align=left] {Memory you received from {\fontfamily{pcr}\selectfont malloc()}};


\end{tikzpicture}
}

Here, let's say we used \texttt{malloc()} to grab some memory for \texttt{ptr\_1}. Nevermind what the type of it is, that isn't important.\newline

Now, let's say we set a new pointer \texttt{ptr\_2} equal to \texttt{ptr\_1}. In other words, we now have two pointers pointing to this memory that you've malloc'd.\newline

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp7660242978805989] 
\draw   (152.5,144.5) -- (222.5,144.5) -- (222.5,184.5) -- (152.5,184.5) -- cycle ;
%Shape: Rectangle [id:dp9835474491940359] 
\draw   (327.5,68) -- (397.5,68) -- (397.5,108) -- (327.5,108) -- cycle ;
%Shape: Rectangle [id:dp6382246899126394] 
\draw   (397.5,68) -- (467.5,68) -- (467.5,108) -- (397.5,108) -- cycle ;
%Shape: Rectangle [id:dp40751687076886434] 
\draw   (467.5,68) -- (537.5,68) -- (537.5,108) -- (467.5,108) -- cycle ;
%Shape: Rectangle [id:dp1956486484356338] 
\draw   (537.5,68) -- (607.5,68) -- (607.5,108) -- (537.5,108) -- cycle ;
%Straight Lines [id:da2803570019045192] 
\draw    (187.5,164.5) -- (326.25,88.21) ;
\draw [shift={(328,87.25)}, rotate = 511.2] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp8693066240275549] 
\draw   (134,22.5) -- (204,22.5) -- (204,62.5) -- (134,62.5) -- cycle ;
%Straight Lines [id:da23910938451416597] 
\draw    (169,42.5) -- (326.07,86.71) ;
\draw [shift={(328,87.25)}, rotate = 195.72] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (116,162.5) node   [align=left] {{\fontfamily{pcr}\selectfont ptr\_1}};
% Text Node
\draw (453,49) node   [align=left] {memory you received from {\fontfamily{pcr}\selectfont malloc()}};
% Text Node
\draw (103,37.5) node   [align=left] {{\fontfamily{pcr}\selectfont ptr\_2}};


\end{tikzpicture}

}

Now, if we want to return this memory back to the memory manager, we can do that very easily by doing either of the following:\newline

\texttt{free(ptr\_2);} or \texttt{free(ptr\_1);}\newline

The reason that this works is that, as far as C is concerned, the actual pointer that you have to the memory that it gave you doesn't matter. At the end of the day, \texttt{free()} takes in a memory address, and C will check to see if it's given you memory at that address. If it decides that it has indeed given you memory at that address, it'll take it back. That's why calling \texttt{free()} on either \texttt{ptr\_1} or \texttt{ptr\_2} will work just fine.

\subsubsection{Malloc with Structs}

One more key point that I want to touch on is that you'll want to use \texttt{sizeof} correctly when allocating memory for structs. When you're allocating memory for a struct, always make sure to allocate memory for the size of the \textbf{struct}, not the size of the \textbf{pointer} to the struct. This is a common mistake, and usually results in segfaults.\newline

\subsubsection{Freeing in the Reverse Order you Malloc}

Here's a good rule of thumb that I like to follow for projects. Whenever you're allocating memory, you'll usually go in a top-down manner. If you have a struct like the one below:\newline

\begin{lstlisting}[language=C]
 typedef struct whale {
   char *name;
   int *weight;
} Whale;
\end{lstlisting}

You'll want to allocate memory for it in order. First, allocate memory for the \texttt{whale} struct itself. Then, remember that the whale struct is only big enough to contain two pointers. If we want those pointers to actually \textbf{point} to anything, we're going to have to allocate that memory too. Thus, we allocate memory for the string \texttt{name} and the int \texttt{weight} as well.\newline

Now, we've got all the memory space we need. Great. But how would we give it back to the program when we're done? Again, follow this rule of thumb: \textbf{free in the reverse order that you malloc}. If you allocated memory for the whale first, then string, then int, go ahead and free the int, the string, then finally the whale. If you don't follow this order and decide to free the whale first, you've effectively lost access to the pointers contained in the whale, and now you won't be able to free that memory. That results in a memory leak, and we definitely don't want that. So again, if you used malloc to allocate memory for \textbf{A}, \textbf{B}, then \textbf{C}, a great rule of thumb is to free \textbf{C}, then \textbf{B}, then finally, \textbf{A}.

Again, these are just a few tips and tricks regarding dynamic memory allocation, but this is an important concept to fully understand in 216. I can't stress the importance of referring to other notes or looking at old lectures until you truly understand dynamic memory allocation.\newline

\subsubsection{Using Valgrind to Find Memory Leaks}

The memory leaks I mentioned above are silent killers- all it takes are a few badly ordered \texttt{free()} function calls, and you've got yourself a memory leak. A great way to check for these quickly is to run \texttt{valgrind}.\newline

It's actually really simple to do so. If you want to check if your executable has any memory leaks, go ahead and use \texttt{make} or \texttt{gcc} to compile it into your executable or an \texttt{a.out} file, then run the following:\newline

\texttt{valgrind a.out} or \texttt{valgrind your\_executable}\newline

If all goes well, \texttt{valgrind} should let you know that 'all blocks were freed'. If not, it will complain and let you know that some pointers were not freed. From there, you can go ahead and examine your code to see where you were making the mistake.\newline

Here's an excellent quick and basic tutorial for using valgrind to check for memory leaks that I used when I was taking 216. If you want further reference, I encourage you to check it out.\newline

\texttt{\href{http://cs.ecs.baylor.edu/~donahoo/tools/valgrind/}{http://cs.ecs.baylor.edu/~donahoo/tools/valgrind/}}

\section{Week 8}

\subsection{Sorting in C}

Sometimes, be it for a project or on an exam, you'll need to quickly sort a list of items (or more specifically, an array of structs). \texttt{qsort()} is basically the quick and easy way to get that done in C. Let's take a look at the actual function definition found on the manpage.\newline

\texttt{void qsort(void *base, size\_t nmemb, size\_t size, int(*compar)(const void *, const void *));}\newline

As all manpage entries are, this may seem confusing at first, so let me break it down for you. \textbf{\texttt{base}} is referring to the array you want to sort in the first place. \textbf{\texttt{nmemb}} is the length of your array, so C knows the bounds of the memory space that it's playing around with. \textbf{\texttt{size}} is the size of the elements in said array, so C knows how big the chunks are that it needs to inevitably move around when it performs the sort. Finally, \textbf{\texttt{compar}} would be your comparator function. This is something I urge you to recall from 132- if you'll recall what a comparator function is, it essentially just tells you if one of the input parameters is 'greater' than the other. If you forgot what a comparator is, another great analog is the \texttt{.compareTo()} method in Java.\newline

There's not much more to it than that. If you ever need your array sorted in C, unless you're explicitly told to write your own algorithm, don't reinvent the wheel. Go ahead and use the \texttt{qsort()} function.

\subsection{The Root User}

On every UNIX system, there is an all-powerful user (superuser) known as \texttt{root}. It's the first user created whenever you install a UNIX machine, and in a weirdly poetic way, all other users are born from it, making it the parent and creator of every other user on a machine.\newline

All you need to know is that it is identified by the name \textbf{root}, it's known as a \textbf{superuser}, and for the purposes of this class, it can basically do anything and everything on the system. In other words, it's the most powerful user on a system.

\subsection{Octal and File Permissions}

Let's talk about file permissions on a UNIX system. Before we do that though, let's do a quick review of the octal number system. You should have the most experience with the decimal system, which uses the digits 0 through 9. Next up, as a CS major, you should be familiar with the binary system, which only uses digits 0 and 1. A key concept to remember is that you can also convert between both, and in that sense, you need to understand that you can represent \textit{any number} in binary or decimal representation, it'll just look different.\newline

That being said, in order to set file permissions on a UNIX system, we take advantage of the \textbf{octal} number system. Just like the latin root \textbf{it} implies, there are 8 total digits that we'll be using, 0 through 7. Now that we understand octal, we can move on to talking about file permissions.\newline

The easiest way to understand something like this is to have hands-on experience. Luckily, we have the grace system at our fingertips to try out stuff like this. Head to your \texttt{216} directory if you'd like to follow along. Go ahead and use \texttt{mkdir} to make a new folder so we can view its permissions. I'm going to name mine 'spaghetti'. If you use the command \texttt{ls -l}, the verbose \texttt{ls} command should show you the file permissions of everything in your current directory (including that of our new directory). Let's focus on what \texttt{ls -l} tells us about the directory for now.\newline

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp42760139883003023] 
\draw  [color={rgb, 255:red, 205; green, 205; blue, 205 }  ,draw opacity=1 ] (195.33,132.67) -- (686.33,132.67) -- (686.33,159.33) -- (195.33,159.33) -- cycle ;
%Straight Lines [id:da027412161022483783] 
\draw    (469.67,206.67) -- (442.17,168.29) ;
\draw [shift={(441,166.67)}, rotate = 414.37] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp36561122366047005] 
\draw   (51,132) -- (64.33,132) -- (64.33,160.67) -- (51,160.67) -- cycle ;
%Straight Lines [id:da43107557729764845] 
\draw    (58.33,62) -- (57.69,126.67) ;
\draw [shift={(57.67,128.67)}, rotate = 270.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp11069137081996394] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (64.33,132) -- (97.67,132) -- (97.67,160.67) -- (64.33,160.67) -- cycle ;
%Shape: Rectangle [id:dp5105405899279477] 
\draw  [color={rgb, 255:red, 245; green, 166; blue, 35 }  ,draw opacity=1 ] (97.67,132) -- (131,132) -- (131,160.67) -- (97.67,160.67) -- cycle ;
%Shape: Rectangle [id:dp1241998432620336] 
\draw  [color={rgb, 255:red, 80; green, 227; blue, 194 }  ,draw opacity=1 ] (131,132) -- (164.33,132) -- (164.33,160.67) -- (131,160.67) -- cycle ;
%Straight Lines [id:da031602023639908494] 
\draw    (81,232) -- (82.29,168.67) ;
\draw [shift={(82.33,166.67)}, rotate = 451.17] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da3521048722446102] 
\draw    (114.33,232) -- (115.63,168.67) ;
\draw [shift={(115.67,166.67)}, rotate = 451.17] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da6073172586106217] 
\draw    (147.67,232) -- (148.96,168.67) ;
\draw [shift={(149,166.67)}, rotate = 451.17] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (48.67,137.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Large \textbf{drwxr-xr-x} 2 apraveen users 2.0K Mar 29 21:02 spaghetti}}};
% Text Node
\draw (346.67,214.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {We don't really care about this stuff\\for now, it's just more misc. info about\\the directory. (e.g. owner, filename, etc.)};
% Text Node
\draw (52.67,41.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {A};
% Text Node
\draw (74.67,236.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {B};
% Text Node
\draw (108,236.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {C};
% Text Node
\draw (140.67,237.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {D};


\end{tikzpicture}
}

Let's walk through the diagram that I've made out of the \texttt{ls -l} command above. There isn't any octal in the picture, but I encourage you to keep the idea in your mind for now. First and foremost, let's forget about the grayed out box for now. That's extra stuff that \texttt{ls -l} provides us with, but it won't be that useful when we're talking about file permissions.\newline

\textbf{(A)} represents 'directory'. It's as simple as that- if this entity that we were analyzing using \texttt{ls -l} weren't a directory, we'd simply not see the 'd' there. \textbf{(B)}, the first 3 characters, represent permissions associated with the owner of the file. Since we see a \texttt{r}, \texttt{w}, and an \texttt{x}, we can see that the owner her permissions to \textit{read}, \textit{write}, and \textit{execute} whatever this entity is. In this case, it makes total sense; I made the folder just now, so I should be able to do whatever I want to it. \textbf{(C)}, the second 3 characters, are permissions associated with a group. For now, all you need to remember is that the group that we're referring to is the group to which this particular file/directory belongs. Finally, \textbf{(D)}, the last 3 characters, represent the permissions for everyone. Obviously, we have to be the most careful about these- e.g. if we accidentally give everyone \textit{write} access to all our files, we could have disastrous consequences.\newline

In order to change these set permissions, we can use the \texttt{chmod} command in conjunction with a 3-digit octal parameter, such as \texttt{chmod 700 spaghetti}. Specifically, we would do something like this:\newline

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp11069137081996394] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (152.33,105.33) -- (185.67,105.33) -- (185.67,134) -- (152.33,134) -- cycle ;
%Shape: Rectangle [id:dp5105405899279477] 
\draw  [color={rgb, 255:red, 245; green, 166; blue, 35 }  ,draw opacity=1 ] (185.67,105.33) -- (219,105.33) -- (219,134) -- (185.67,134) -- cycle ;
%Shape: Rectangle [id:dp1241998432620336] 
\draw  [color={rgb, 255:red, 80; green, 227; blue, 194 }  ,draw opacity=1 ] (219,105.33) -- (252.33,105.33) -- (252.33,134) -- (219,134) -- cycle ;
%Straight Lines [id:da3925814990937547] 
\draw    (270.33,270.67) -- (170.2,136.93) ;
\draw [shift={(169,135.33)}, rotate = 413.18] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8411143149408029] 
\draw    (271.67,226.67) -- (202.21,135.59) ;
\draw [shift={(201,134)}, rotate = 412.66999999999996] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da2927838400275865] 
\draw    (274.33,188) -- (238.82,137.63) ;
\draw [shift={(237.67,136)}, rotate = 414.81] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (162.67,112.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {\#};
% Text Node
\draw (196,111.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {\#};
% Text Node
\draw (230,112.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {\#};
% Text Node
\draw (94.67,109.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont chmod}};
% Text Node
\draw (271.33,261.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {Octal number representing the rwx permissions for owner};
% Text Node
\draw (274,219) node [anchor=north west][inner sep=0.75pt]   [align=left] {Octal number representing the rwx permissions for group};
% Text Node
\draw (276,179.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {Octal number representing the rwx permissions for all};


\end{tikzpicture}

}

Think back to when we talked about converting between number systems. Each number in the 3-digit octal parameter that we provide chmod actually represents a configuration for \texttt{rwx}. Specifically, it's that octal number converted to binary. In order to decode what each permission means, we'd convert each digit in the octal input parameter to its binary counterpart, then figure out which permissions were 'active' based on the presence of a 0 or a 1. For example, let's say we wanted to give our file read/write/execute access for everyone. We would execute \texttt{chmod 777 spaghetti}. Below is a diagram explaining the details.\newline

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp11069137081996394] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (152.33,105.33) -- (185.67,105.33) -- (185.67,134) -- (152.33,134) -- cycle ;
%Shape: Rectangle [id:dp5105405899279477] 
\draw  [color={rgb, 255:red, 245; green, 166; blue, 35 }  ,draw opacity=1 ] (185.67,105.33) -- (219,105.33) -- (219,134) -- (185.67,134) -- cycle ;
%Shape: Rectangle [id:dp1241998432620336] 
\draw  [color={rgb, 255:red, 80; green, 227; blue, 194 }  ,draw opacity=1 ] (219,105.33) -- (252.33,105.33) -- (252.33,134) -- (219,134) -- cycle ;
%Straight Lines [id:da3925814990937547] 
\draw    (270.33,270.67) -- (170.2,136.93) ;
\draw [shift={(169,135.33)}, rotate = 413.18] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8411143149408029] 
\draw    (271.67,226.67) -- (202.21,135.59) ;
\draw [shift={(201,134)}, rotate = 412.66999999999996] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da2927838400275865] 
\draw    (274.33,188) -- (238.82,137.63) ;
\draw [shift={(237.67,136)}, rotate = 414.81] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8093183970331216] 
\draw    (367,190) -- (391.67,190) ;
\draw [shift={(393.67,190)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9695792273639827] 
\draw    (366.33,230.67) -- (391,230.67) ;
\draw [shift={(393,230.67)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da1626297191907251] 
\draw    (366.33,266) -- (391,266) ;
\draw [shift={(393,266)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (162.67,112.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {7};
% Text Node
\draw (196.67,111.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {7};
% Text Node
\draw (230,112.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {7};
% Text Node
\draw (94.67,109.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont chmod}};
% Text Node
\draw (275.33,179.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 111} in Binary};
% Text Node
\draw (275.33,219) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 111} in Binary};
% Text Node
\draw (274.67,257) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 111} in Binary};
% Text Node
\draw (403.33,179.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {rwx};
% Text Node
\draw (406,223.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {rwx};
% Text Node
\draw (404.67,258.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {rwx};
% Text Node
\draw (264.67,110.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont spaghetti}};


\end{tikzpicture}


}

Like I explained above, you'll notice that we're taking two basic steps. \newline

\begin{itemize}
	\item \texttt{First}, convert each octal input digit to binary.
	\item \texttt{Second}, see where the ones and zeroes are in that binary output, and that'll tell you which of the rwx parameters are active.
\end{itemize}

For example, if you wanted rwx permissions for everyone like we set above, except this time, we'd only allow all users outside of the owner and the file group to only read the file, we'd edit the last digit in the octal input parameter to reflect that, like so:\newline


{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp11069137081996394] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (152.33,105.33) -- (185.67,105.33) -- (185.67,134) -- (152.33,134) -- cycle ;
%Shape: Rectangle [id:dp5105405899279477] 
\draw  [color={rgb, 255:red, 245; green, 166; blue, 35 }  ,draw opacity=1 ] (185.67,105.33) -- (219,105.33) -- (219,134) -- (185.67,134) -- cycle ;
%Shape: Rectangle [id:dp1241998432620336] 
\draw  [color={rgb, 255:red, 80; green, 227; blue, 194 }  ,draw opacity=1 ] (219,105.33) -- (252.33,105.33) -- (252.33,134) -- (219,134) -- cycle ;
%Straight Lines [id:da3925814990937547] 
\draw    (270.33,270.67) -- (170.2,136.93) ;
\draw [shift={(169,135.33)}, rotate = 413.18] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8411143149408029] 
\draw    (271.67,226.67) -- (202.21,135.59) ;
\draw [shift={(201,134)}, rotate = 412.66999999999996] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da2927838400275865] 
\draw    (274.33,188) -- (238.82,137.63) ;
\draw [shift={(237.67,136)}, rotate = 414.81] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8093183970331216] 
\draw    (367,190) -- (391.67,190) ;
\draw [shift={(393.67,190)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9695792273639827] 
\draw    (366.33,230.67) -- (391,230.67) ;
\draw [shift={(393,230.67)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da1626297191907251] 
\draw    (366.33,266) -- (391,266) ;
\draw [shift={(393,266)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (162.67,112.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {7};
% Text Node
\draw (196.67,111.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {7};
% Text Node
\draw (230,111.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {4};
% Text Node
\draw (94.67,109.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont chmod}};
% Text Node
\draw (275.33,179.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 100} in Binary};
% Text Node
\draw (275.33,219.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 111} in Binary};
% Text Node
\draw (274.67,257) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 111} in Binary};
% Text Node
\draw (403.33,179.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {r--};
% Text Node
\draw (406,223.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {rwx};
% Text Node
\draw (404.67,258.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {rwx};
% Text Node
\draw (264.67,110.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont spaghetti}};


\end{tikzpicture}

}

This is a great way to see the intuitive conversion we have from octal digit to binary to rwx permission. Just remember the two steps I've listed above, and make sure you understand this example, and you should be set. Here are a few more commonly used \texttt{chmod} commands that you may see in the future. In order to fully understand this, I highly recommend you take the examples I'm listing below and work through diagrams like the one I've made above for each of them. If you do that, you'll be in great shape for the exam, where this is fairly likely to show up. (It was on my exam when I took this class).\newline

For these examples, assume again that we have a file named \textbf{spaghetti} that we'd like to change the permissions of. \newline

\begin{itemize}
	\item \texttt{chmod 700 spaghetti} $\rightarrow$ Read write and execute permission for owner, with no access to anyone else (remember, 0 is like --- in rwx notation).
	\item \texttt{chmod 500 spaghetti} $\rightarrow$ Read and execute permissions for owner with no access to anyone else.
	\item \texttt{chmod 755 spaghetti} $\rightarrow$ Read, write, and execute permission for the owner, and read and execute for the group and the rest of the users. If you'll look on grace, you'll see that this is frequently employed by our instructors when they post new material.
\end{itemize}

As a little closing note, you can use \texttt{chmod -R} to recursively change file permissions in the same way that you'd use \texttt{cp -r} to perform a recursive copy. This comes in handy if you're trying to change the permissions of everything within a directory, including subdirectories.

\subsection{Aside: Bash Scripting}

\textit{Full disclosure- this section on bash scripting won't be required knowledge for your exam. If you're reviewing and are just preparing for an exam, no need to retain the 'Bash Scripting' material I'll be talking about.}\newline

The first thing you need to know is that, sitting on top of UNIX, you're interacting with a program called a \textbf{shell}. It's basically a little environment that takes in commands that you give it, and it provides information back to you. From a shell, you're allowed to list the contents of a directory, make new ones, kick off other programs, and do plenty of other stuff. One such shell that became wildly popular is the \textbf{bash shell}, which is what we're using on grace today.

Bash scripting is an essential part of any UNIX workflow. Let's say you wanted fire off a few command line commands in consecutive order, or wanted to perform a repetetive task. For example, let's assume you wanted to make \textit{n} folders in quick succession, each following a specific naming scheme. The most readable way to do something like that is to have a set of command line commands that you wanted to execute, each one right after the other. In other words, you wanted a \textbf{bash script} to do that work for you.\newline

We'll also be covering a little bit of miscellaneous information regarding how scripts are used. There are a few nifty tidbits that I think are worth pulling from today's discussion.\newline

The first thing you'll want to make note of is that we can use the return values of programs in bash scripts. When you're writing bash scripts that interact with the command line, just keep in mind that C is the framework upon which UNIX was built. In other words, it's only natural that UNIX and its commands (including its bash scripting language) play nice with C. The key here is knowing that you can check the return value of a C program's 'main' function via bash.\newline

At the end of the day, there are just two things that you really need to know about bash scripts. First of all, remember that they are simply just executable sets of command line instructions, with a few programming constructs (conditional statements, loops) thrown in. A great example of a problem you could solve with a bash script is if you wanted to check whether a folder named 'tests' existed, and if it didn't, create it and fill it with a bunch of empty \texttt{.c} files.

\subsection{Bitwise Operations}

Since this is a computer systems course, it's good to start thinking in terms of \textit{bits}. In simple terms, you're going to want to start thinking of the binary representations of a lot of things. Bitwise operations are simply the operations that we conduct at this level- they work with the individual bits, or binary digits, of data that we store in our programs. Specifically, we're talking about simple operations like 'and', 'or', and 'xor' with 1's and 0's.\newline

Here's a little bit of computer systems background for you- the reason we like to go all the way down to binary and perform operations there is because these 'bitwise' operations are much faster than their costlier, high-overhead counterparts- especially on simpler processors. Even on modern, faster machines, bitwise operations are still worth considering due to their lower resource consumption. On older machines, it was just as simple as knowing that bitwise operations simply took less steps; if you want a really simple analogy: it was easier for a computer to think in the language that it use by default. On newer machines, we could honestly probably say that bitwise operations take about the same amount of time as regular addition, multiplication, division, etc, thanks to things like instructional pipelines and more sophisticated architecture (CMSC411). However, as I said above, they still ultimately require less resources to perform. TL;DR - they're more efficient, and you should use them cleverly when you can to save your computer some work.\newline

\subsubsection{How We Can Do This in C}

So there's some background on bitwise operations in general, but here's some insight as to how we can do it in C. The reason we're learning this in CMSC216 and not in CMSC330 or CMSC132 is simply because this is a pretty low-level operation, so although there are probably ways to get around to doing this in Java or Ruby, the most applicable use case would probably be for when you're writing in C, which probably implies you're already trying to skimp on memory and resource usage.\newline

That being said, there are \textbf{6} bitwise operators that you should remember in C.\newline

\begin{itemize}
	\item \textbf{\texttt{\&}} $\rightarrow$ bitwise AND, used the same way as the AND logic gate from CMSC250.
	\item \textbf{\texttt{|}} $\rightarrow$ bitwise (inclusive) OR, used the same way as the OR logic gate from CMSC250.
	\item \textbf{\texttt{\^}} $\rightarrow$ bitwise exclusive OR, again, used the same way as the XOR logic gate from CMSC250.
	\item \textbf{\texttt{<<}} $\rightarrow$ bit-shift left. Don't let the name confuse you- this is one of the simplest bitwise operations. You're literally taking all the digits in a binary number, and shifting them left by one digit place. It's also good to note that you're filling the blank digits (the ones with nothing to their left) with zeros. I'll include a diagram below of bitshifts in a left and right direction.
	\item \textbf{\texttt{>>}} $\rightarrow$ bit-shift right. Again, the same deal as above. This time, you'll be moving all the digits in a number to the right, and filling in the void created by a digit with nothing to its right with a zero.
	\item \textbf{\texttt{-}} $\rightarrow$ bitwise NOT. Same as in CMSC250.
	
\end{itemize}

These operations are best explained by a few code examples, and as such, I'm going to link an excellent website that provides some very clear and simple examples. The lecture slides are also a fantastic resource for this stuff, particularly for examples, so make sure to check them out.\newline

{
\textit{
\href{https://www.tutorialspoint.com/cprogramming/c\_bitwise\_operators.htm}{https://www.tutorialspoint.com/cprogramming/c\_bitwise\_operators.htm}
}
}


\subsubsection{Bit-Shift Example}

Here's an example of a bit-shift in case you needed it. I think this is the easiest bitwise operation, but since we haven't covered it in CMSC250, it's worth seeing at least one example. Essentially, all you're doing is taking the digits in a binary number, and shifting them to either the left or right. Note that the shifts I'm demonstrating below are by an increment of 1, but it's of course totally conceptually valid to perform a bit shift by any amount.

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp8828034661335886] 
\draw   (62,54.33) -- (90.33,54.33) -- (90.33,88.67) -- (62,88.67) -- cycle ;
%Shape: Rectangle [id:dp42716850197078593] 
\draw   (90,54.33) -- (118.33,54.33) -- (118.33,88.67) -- (90,88.67) -- cycle ;
%Shape: Rectangle [id:dp2677016614924078] 
\draw   (118,54.33) -- (146.33,54.33) -- (146.33,88.67) -- (118,88.67) -- cycle ;
%Shape: Rectangle [id:dp649622133852392] 
\draw   (146,54.33) -- (174.33,54.33) -- (174.33,88.67) -- (146,88.67) -- cycle ;
%Straight Lines [id:da27298157713196614] 
\draw    (182.33,69.33) -- (230.48,89.24) ;
\draw [shift={(232.33,90)}, rotate = 202.46] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp8749912286413047] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (242,75) -- (270.33,75) -- (270.33,109.33) -- (242,109.33) -- cycle ;
%Shape: Rectangle [id:dp6848359777047052] 
\draw   (270,75) -- (298.33,75) -- (298.33,109.33) -- (270,109.33) -- cycle ;
%Shape: Rectangle [id:dp14299815968721497] 
\draw   (298,75) -- (326.33,75) -- (326.33,109.33) -- (298,109.33) -- cycle ;
%Shape: Rectangle [id:dp013551429357448685] 
\draw   (326,75) -- (354.33,75) -- (354.33,109.33) -- (326,109.33) -- cycle ;
%Curve Lines [id:da1886869831462753] 
\draw    (370.33,114) .. controls (363.26,129.44) and (357.42,123.77) .. (344.44,113.17) ;
\draw [shift={(343,112)}, rotate = 398.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da1230078485232381] 
\draw    (341,115.33) .. controls (333.92,130.77) and (328.09,125.11) .. (315.11,114.51) ;
\draw [shift={(313.67,113.33)}, rotate = 398.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da7649309990507515] 
\draw    (310.33,116.67) .. controls (303.26,132.11) and (297.42,126.44) .. (284.44,115.84) ;
\draw [shift={(283,114.67)}, rotate = 398.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da4422858400777201] 
\draw    (279.67,116) .. controls (272.59,131.44) and (266.75,125.77) .. (253.77,115.17) ;
\draw [shift={(252.33,114)}, rotate = 398.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da17352984816469474] 
\draw    (165,92.67) .. controls (157.92,108.11) and (152.09,102.44) .. (139.11,91.84) ;
\draw [shift={(137.67,90.67)}, rotate = 398.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da7261581249081148] 
\draw    (135.67,94) .. controls (128.59,109.44) and (122.75,103.77) .. (109.77,93.17) ;
\draw [shift={(108.33,92)}, rotate = 398.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da17384339034333252] 
\draw    (105,95.33) .. controls (97.92,110.77) and (92.09,105.11) .. (79.11,94.51) ;
\draw [shift={(77.67,93.33)}, rotate = 398.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da12512001747665702] 
\draw    (74.33,94.67) .. controls (67.26,110.11) and (61.42,104.44) .. (48.44,93.84) ;
\draw [shift={(47,92.67)}, rotate = 398.99] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp2693737975748981] 
\draw   (354.33,75) -- (382.67,75) -- (382.67,109.33) -- (354.33,109.33) -- cycle ;
%Straight Lines [id:da2729018598573574] 
\draw    (400.67,91.33) -- (457.12,70.69) ;
\draw [shift={(459,70)}, rotate = 519.9100000000001] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp46228873953180216] 
\draw   (463.33,55.67) -- (491.67,55.67) -- (491.67,90) -- (463.33,90) -- cycle ;
%Shape: Rectangle [id:dp8830986432067672] 
\draw   (491.33,55.67) -- (519.67,55.67) -- (519.67,90) -- (491.33,90) -- cycle ;
%Shape: Rectangle [id:dp6271802218982883] 
\draw   (519.33,55.67) -- (547.67,55.67) -- (547.67,90) -- (519.33,90) -- cycle ;
%Shape: Rectangle [id:dp6353911181595879] 
\draw   (547.33,55.67) -- (575.67,55.67) -- (575.67,90) -- (547.33,90) -- cycle ;
%Shape: Rectangle [id:dp6434846921441273] 
\draw   (62,202.33) -- (90.33,202.33) -- (90.33,236.67) -- (62,236.67) -- cycle ;
%Shape: Rectangle [id:dp704281929476223] 
\draw   (90,202.33) -- (118.33,202.33) -- (118.33,236.67) -- (90,236.67) -- cycle ;
%Shape: Rectangle [id:dp8216884247708056] 
\draw   (118,202.33) -- (146.33,202.33) -- (146.33,236.67) -- (118,236.67) -- cycle ;
%Shape: Rectangle [id:dp0928403616119251] 
\draw   (146,202.33) -- (174.33,202.33) -- (174.33,236.67) -- (146,236.67) -- cycle ;
%Straight Lines [id:da0043525204585196375] 
\draw    (182.33,217.33) -- (230.48,237.24) ;
\draw [shift={(232.33,238)}, rotate = 202.46] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp5144438115376195] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ] (242,223) -- (270.33,223) -- (270.33,257.33) -- (242,257.33) -- cycle ;
%Shape: Rectangle [id:dp9092849562629273] 
\draw   (270,223) -- (298.33,223) -- (298.33,257.33) -- (270,257.33) -- cycle ;
%Shape: Rectangle [id:dp10713472317521311] 
\draw   (298,223) -- (326.33,223) -- (326.33,257.33) -- (298,257.33) -- cycle ;
%Shape: Rectangle [id:dp1356208368179469] 
\draw   (326,223) -- (354.33,223) -- (354.33,257.33) -- (326,257.33) -- cycle ;
%Shape: Rectangle [id:dp8726666412670342] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (354.33,223) -- (382.67,223) -- (382.67,257.33) -- (354.33,257.33) -- cycle ;
%Straight Lines [id:da9357925218727965] 
\draw    (400.67,239.33) -- (457.12,218.69) ;
\draw [shift={(459,218)}, rotate = 519.9100000000001] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp45290242099217615] 
\draw   (463.33,203.67) -- (491.67,203.67) -- (491.67,238) -- (463.33,238) -- cycle ;
%Shape: Rectangle [id:dp6339724163630963] 
\draw   (491.33,203.67) -- (519.67,203.67) -- (519.67,238) -- (491.33,238) -- cycle ;
%Shape: Rectangle [id:dp06338056921526669] 
\draw   (519.33,203.67) -- (547.67,203.67) -- (547.67,238) -- (519.33,238) -- cycle ;
%Shape: Rectangle [id:dp5798463851786051] 
\draw   (547.33,203.67) -- (575.67,203.67) -- (575.67,238) -- (547.33,238) -- cycle ;
%Curve Lines [id:da15477687323030198] 
\draw    (76.33,239.33) .. controls (80.79,252.7) and (90.11,247.22) .. (101.39,240.32) ;
\draw [shift={(103,239.33)}, rotate = 508.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da24670710934772389] 
\draw    (106.33,240) .. controls (110.79,253.37) and (120.11,247.89) .. (131.39,240.98) ;
\draw [shift={(133,240)}, rotate = 508.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da7950664670344985] 
\draw    (137,239.33) .. controls (141.46,252.7) and (150.78,247.22) .. (162.06,240.32) ;
\draw [shift={(163.67,239.33)}, rotate = 508.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da0768678421657879] 
\draw    (167,240) .. controls (171.46,253.37) and (180.78,247.89) .. (192.06,240.98) ;
\draw [shift={(193.67,240)}, rotate = 508.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da8369600258660683] 
\draw    (253,260) .. controls (257.46,273.37) and (266.78,267.89) .. (278.06,260.98) ;
\draw [shift={(279.67,260)}, rotate = 508.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da7185883705444674] 
\draw    (283,260.67) .. controls (287.46,274.04) and (296.78,268.56) .. (308.06,261.65) ;
\draw [shift={(309.67,260.67)}, rotate = 508.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da4989214227414751] 
\draw    (313.67,260) .. controls (318.12,273.37) and (327.44,267.89) .. (338.73,260.98) ;
\draw [shift={(340.33,260)}, rotate = 508.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da6259249545462894] 
\draw    (343.67,260.67) .. controls (348.12,274.04) and (357.44,268.56) .. (368.73,261.65) ;
\draw [shift={(370.33,260.67)}, rotate = 508.57] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (31.33,23) node [anchor=north west][inner sep=0.75pt]   [align=left] {Q: Perform a left shift on the binary number {\fontfamily{pcr}\selectfont 0110}};
% Text Node
\draw (32.67,61) node [anchor=north west][inner sep=0.75pt]   [align=left] {A:};
% Text Node
\draw (70.67,61.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (98.67,61.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (126.67,61.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (154.67,61.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (250.67,82) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont \textcolor[rgb]{1,0,0}{0}}};
% Text Node
\draw (278.67,82) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (306.67,82) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (334.67,82) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (239.33,56) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\tiny \textcolor[rgb]{1,0,0}{overflow}}}};
% Text Node
\draw (362.67,82) node [anchor=north west][inner sep=0.75pt]  [color={rgb, 255:red, 126; green, 211; blue, 33 }  ,opacity=1 ] [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (341.33,54) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\tiny \textcolor[rgb]{0.49,0.83,0.13}{{\fontfamily{pcr}\selectfont empty- set to 0}}}};
% Text Node
\draw (38,112.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small (move all digits left by 1)}};
% Text Node
\draw (472,62.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (500,62.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (528,62.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (556,62.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (474,98) node [anchor=north west][inner sep=0.75pt]   [align=left] {Answer: {\fontfamily{pcr}\selectfont 1100}};
% Text Node
\draw (31.33,171) node [anchor=north west][inner sep=0.75pt]   [align=left] {Q: Perform a right shift on the binary number {\fontfamily{pcr}\selectfont 1010}};
% Text Node
\draw (32.67,209) node [anchor=north west][inner sep=0.75pt]   [align=left] {A:};
% Text Node
\draw (70.67,209.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (98.67,209.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (126.67,209.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (154.67,209.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (250.67,230) node [anchor=north west][inner sep=0.75pt]  [color={rgb, 255:red, 126; green, 211; blue, 33 }  ,opacity=1 ] [align=left] {{\fontfamily{pcr}\selectfont \textcolor[rgb]{0.49,0.83,0.13}{0}}};
% Text Node
\draw (278.67,230) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (306.67,230) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (334.67,230) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (352.67,202) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\tiny \textcolor[rgb]{1,0,0}{overflow}}}};
% Text Node
\draw (362.67,230) node [anchor=north west][inner sep=0.75pt]  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,opacity=1 ] [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (226,202) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\tiny \textcolor[rgb]{0.49,0.83,0.13}{{\fontfamily{pcr}\selectfont empty- set to 0}}}};
% Text Node
\draw (40.67,262.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small (move all digits right by 1)}};
% Text Node
\draw (472,210.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (500,210.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (528,210.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0}};
% Text Node
\draw (556,210.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 1}};
% Text Node
\draw (474,246) node [anchor=north west][inner sep=0.75pt]   [align=left] {Answer: {\fontfamily{pcr}\selectfont 0101}};


\end{tikzpicture}\newline\newline

}

\subsubsection{Aside: Multiplication and Division by Powers of 2 using BSL/BSR}

Additionally, there's one other cool nuance with bit-shifts that I want to point out. Notice how we're working with binary. Think back to the decimal number system for a bit. If you wanted to perform a quick division by 10, let's say in this case, we wanted to divide 360 by 10 (with no remainder), your elementary school intuition says that all you need to do is drop the zero at the end. But what did we really do?\newline

In actuality, you're performing a sort of bit-shift here. Think of it this way- instead of dropping the zero at the end when you performed \texttt{360/10}, you simply just performed the decimal equivalent of bit-shifting 360 to the right. Additionally, if you ever wanted to multiply a number by 10, I invite you to think back to elementary school. Multiplication by 10 was by far the easiest, because all you had to do was throw an extra zero onto the end of a number. Let's think of that in a similar way- you weren't just throwing a zero onto the end of your number, you were performing the decimal equivalent of bit-shifting it to the left. This all relies on the idea that the number 10 is the basis of the decimal system. So the question is- can we replicate the same special behavior with the binary number system and the number 2? The answer is yes.\newline

In that same way, if we wanted to divide a number that we had in binary very quickly by two, all we have to do is bit-shift it once to the right. For example- if we wanted to divide 6 by 2, we could take a look at their binary notations.\newline

In binary, 6 is \texttt{110}. If we wanted to divide that by 2, we can perform a bit-shift right and get our result, which would be \texttt{011}.\newline

In a similar way, if we wanted to quickly multiply a number by 2, it's as easy as performing a bit-shift left on it. In that way, we can easily turn 3 (\texttt{011}) into 6 (\texttt{110}) in a simple, inexpensive operation.\newline

Here's the main takeaway. By taking advantage of the way binary is structured, we can very easily multiply and divide by 2 (and by repeating the process, by powers of 2) using only bit-shift operations.

\subsection{Number Systems \& How to Convert Between Them}

It's almost guaranteed on an exam that you'll have \textit{some} question that asks you something along the lines of the following:\newline

\textit{Convert XXXXX into hexadecimal/binary/octal/decimal.}\newline

Luckily, once you understand one of these questions, you basically understand them all. First things first, here's a review of the number systems that you'll probably see in CMSC216:\newline

\begin{itemize}
	\item \textbf{Decimal} is our best friend, and the number system that you're used to. Also called base-10, it's the number notation that you're most familiar with. I'd recommend using this as an intermediary step when for conversions if you end up getting stuck.
	\item \textbf{Binary} is the computer's best friend. A number system only composed of \texttt{1}'s and \texttt{0}'s, this is the home of all the bitwise operations.
	\item \textbf{Octal} is that one number system you learned for understanding file permissions earlier this week. Using the numbers \texttt{0} through \texttt{7}, it's got just enough niche use cases in computing for it to be worth getting somewhat comfortable with.
	\item \textbf{Hexadecimal} is the biggest number system we've gotten to dealing with in this class so far, and it essentially makes use of 16 digits. In order, those are \texttt{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}. Think of it this way- in the same way our regular base-10 number system 'overflows' and goes back over to 0 after we add 1 to 9, the hexadecimal system overflows and goes back to 0 after we add 1 to F, which is \textit{its} upper limit.
\end{itemize}

Converting between these number systems is usually just a matter of division. Here are a few examples to get you started, but in my opinion, this is just a matter of practice. Once you've done this a few times between a few different number systems, you may as wel have done it hundreds of times. It's all just in how quick you are with the actual division. I'd recommend not only doing the worksheet I'm linking below, but also practicing converting between each of the 4 system types I've pointed out above. (16 problems is a lot though, so space them out over a few days, maybe).\newline


{
\centering







\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Straight Lines [id:da41461429072144007] 
\draw    (145,84.67) -- (238.33,84.01) ;
\draw [shift={(240.33,84)}, rotate = 539.6] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da6413874070721497] 
\draw    (266.67,73.33) .. controls (301.14,41.81) and (360.84,43.28) .. (391.61,71.37) ;
\draw [shift={(393,72.67)}, rotate = 224.04] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da2654695661421509] 
\draw    (398,71.33) .. controls (432.48,39.81) and (492.18,41.28) .. (522.95,69.37) ;
\draw [shift={(524.33,70.67)}, rotate = 224.04] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da6320211359785352] 
\draw    (338,100) -- (424.99,195.85) ;
\draw [shift={(426.33,197.33)}, rotate = 227.78] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da34124387637791287] 
\draw    (450,96) -- (456.21,192.67) ;
\draw [shift={(456.33,194.67)}, rotate = 266.33] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da7492008776478719] 
\draw    (578.67,92) -- (492.33,189.17) ;
\draw [shift={(491,190.67)}, rotate = 311.62] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9525951020629994] 
\draw    (461.33,226.33) -- (553.23,274.41) ;
\draw [shift={(555,275.33)}, rotate = 207.62] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (41.33,244.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {Q: Convert 574 (base 10) to Hexadecimal};
% Text Node
\draw (95.33,75.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 574}}};
% Text Node
\draw (149.33,100.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{divide by 16}}};
% Text Node
\draw (252,76.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 35 R:\textcolor[rgb]{0.29,0.56,0.89}{14}}}};
% Text Node
\draw (293.33,33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{divide by 16}}};
% Text Node
\draw (385.33,75) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 2 R:\textcolor[rgb]{0.31,0.89,0.76}{3}}}};
% Text Node
\draw (422,31.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{divide by 16}}};
% Text Node
\draw (516,72.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 0 R:\textcolor[rgb]{0.49,0.83,0.13}{2}}}};
% Text Node
\draw (423.33,200.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE \textcolor[rgb]{0.29,0.56,0.89}{E} \textcolor[rgb]{0.31,0.89,0.76}{3} \textcolor[rgb]{0.49,0.83,0.13}{2}}}};
% Text Node
\draw (506.2,209.11) node [anchor=north west][inner sep=0.75pt]  [rotate=-0.41] [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{(Comes out backwards)}}};
% Text Node
\draw (560,264.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 23E}}};
% Text Node
\draw (43.33,272.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {A: 23E};
% Text Node
\draw (330.56,4.83) node [anchor=north] [inner sep=0.75pt]   [align=left] {\textbf{Example 1: Converting Decimal to Hexadecimal}};


\end{tikzpicture}\newline\newline


}

Notice that when we performed the conversion, the numbers initially came out backwards. There are cases for when our conversion comes out backwards and when it comes out forwards, and I would encourage you to practice till you figure out when each comes out. I leave that as an exercise to the reader. Generally, you should be able to use common sense to figure out which order your resulting digits should go in, though. If anything, try and convert it back and see if your conversion worked.\newline

{
\centering



\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Straight Lines [id:da41461429072144007] 
\draw    (53,103) -- (127.67,103) ;
\draw [shift={(129.67,103)}, rotate = 180] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da6413874070721497] 
\draw    (151.33,90.67) .. controls (185.81,59.15) and (226.75,59.97) .. (256.96,88.03) ;
\draw [shift={(258.33,89.33)}, rotate = 224.04] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da8972634232951618] 
\draw    (266,88) .. controls (300.47,56.48) and (341.42,57.3) .. (371.63,85.37) ;
\draw [shift={(373,86.67)}, rotate = 224.04] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da6638141996376121] 
\draw    (381.33,85.33) .. controls (415.81,53.81) and (456.75,54.63) .. (486.96,82.7) ;
\draw [shift={(488.33,84)}, rotate = 224.04] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da8323805553481021] 
\draw    (495.33,83.33) .. controls (529.81,51.81) and (570.75,52.63) .. (600.96,80.7) ;
\draw [shift={(602.33,82)}, rotate = 224.04] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da5460404441346167] 
\draw    (210.67,117) -- (352.61,199.66) ;
\draw [shift={(354.33,200.67)}, rotate = 210.22] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da23307743789617097] 
\draw    (325.67,114) -- (366.79,198.2) ;
\draw [shift={(367.67,200)}, rotate = 243.97] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da6652803279257993] 
\draw    (433,115.33) -- (382.05,198.3) ;
\draw [shift={(381,200)}, rotate = 301.56] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9395976129715173] 
\draw    (545,114.67) -- (398.07,198.34) ;
\draw [shift={(396.33,199.33)}, rotate = 330.34000000000003] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da4636114313346177] 
\draw    (659.67,126.67) -- (414.25,198.77) ;
\draw [shift={(412.33,199.33)}, rotate = 343.63] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (41.33,244.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {Q: Convert 29 (base 10) to Binary};
% Text Node
\draw (17.33,92.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 29}}};
% Text Node
\draw (56,78.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{divide by 2}}};
% Text Node
\draw (135.33,92.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 14 R:\textcolor[rgb]{0.29,0.56,0.89}{1}}}};
% Text Node
\draw (170,49.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{divide by 2}}};
% Text Node
\draw (247.33,92.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 7 R:\textcolor[rgb]{0.31,0.89,0.76}{0}}}};
% Text Node
\draw (43.33,273) node [anchor=north west][inner sep=0.75pt]   [align=left] {A: 10111};
% Text Node
\draw (332.56,9) node [anchor=north] [inner sep=0.75pt]   [align=left] {\textbf{Example 2: Converting Decimal to Binary}};
% Text Node
\draw (287.33,48.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{divide by 2}}};
% Text Node
\draw (370,92.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 3 R:\textcolor[rgb]{0.49,0.83,0.13}{1}}}};
% Text Node
\draw (482.67,92.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 1 R:\textcolor[rgb]{0.97,0.91,0.11}{1}}}};
% Text Node
\draw (598,92.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE 0 R:\textcolor[rgb]{0.96,0.65,0.14}{1}}}};
% Text Node
\draw (348,207) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE \textcolor[rgb]{0.29,0.56,0.89}{1}\textcolor[rgb]{0.31,0.89,0.76}{0}\textcolor[rgb]{0.72,0.91,0.53}{1}\textcolor[rgb]{0.97,0.91,0.11}{1}\textcolor[rgb]{0.96,0.65,0.14}{1}}}};
% Text Node
\draw (432.67,217.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{(notice how it isn't backwards this time)}}};
% Text Node
\draw (402.67,46.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{divide by 2}}};
% Text Node
\draw (516.67,43.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\small \textcolor[rgb]{0.61,0.61,0.61}{divide by 2}}};


\end{tikzpicture}\newline\newline


}

These two have been examples of converting Decimal to other number systems, but what if we wanted to convert back to Decimal from there? The process is fairly simple, and it leverages our decimal-based knowledge of the other number system. Example 3 is one such example, where we're converting from an unfamiliar base back into decimal. The procedure looks a little different, but is based in the same principles of division.\newline

{
\centering



\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Straight Lines [id:da9525951020629994] 
\draw    (274,59) -- (120.96,91.58) ;
\draw [shift={(119,92)}, rotate = 347.98] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da07598835439545237] 
\draw    (301.33,58.33) -- (467.04,90.95) ;
\draw [shift={(469,91.33)}, rotate = 191.13] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da156754651471259] 
\draw    (287,59.33) -- (287.63,90.67) ;
\draw [shift={(287.67,92.67)}, rotate = 268.85] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9803275422425445] 
\draw    (124.33,112.67) -- (225.73,138.18) ;
\draw [shift={(227.67,138.67)}, rotate = 194.12] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da6322152821009867] 
\draw    (464.33,112) -- (338.97,135.63) ;
\draw [shift={(337,136)}, rotate = 349.33000000000004] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da49628645319206577] 
\draw    (287,105.83) -- (287.63,137.17) ;
\draw [shift={(287.67,139.17)}, rotate = 268.85] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (144,249.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {Q: Convert AF6 (Hexadecimal) to Decimal};
% Text Node
\draw (255.33,169) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE =2806}}};
% Text Node
\draw (146,278) node [anchor=north west][inner sep=0.75pt]   [align=left] {A: 2806};
% Text Node
\draw (295.89,6.83) node [anchor=north] [inner sep=0.75pt]   [align=left] {\textbf{Example 3: Converting Hexadecimal to Decimal}};
% Text Node
\draw (266,36) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\LARGE \textcolor[rgb]{0.82,0.01,0.11}{A}\textcolor[rgb]{0.96,0.65,0.14}{F}\textcolor[rgb]{0.55,0.34,0.16}{6}}}};
% Text Node
\draw (83.33,95.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\large \textcolor[rgb]{0.82,0.01,0.11}{10 * (16*16)}}}};
% Text Node
\draw (243.33,95.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\large \textcolor[rgb]{0.96,0.65,0.14}{15 * (16)}}}};
% Text Node
\draw (468,95.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\large \textcolor[rgb]{0.55,0.34,0.16}{6}}}};
% Text Node
\draw (211.33,144.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\large \textcolor[rgb]{0.82,0.01,0.11}{2560}\textcolor[rgb]{0,0,0}{ + }\textcolor[rgb]{0.96,0.65,0.14}{240}\textcolor[rgb]{0,0,0}{ +}\textcolor[rgb]{0.82,0.01,0.11}{ }\textcolor[rgb]{0.55,0.34,0.16}{6}}}};


\end{tikzpicture}



}


\subsection{Two's Complement}

Yes, number systems are undoubtedly cool, and the ability of computers to keep track of two states (on and off) make binary easily the most convenient number system to use on a computer, but this poses a new problem. In the way that we think about numbers, let's say that we end up subtracting a little too much and go end up below zero. If you're doing subtraction on paper in school, this can be handled pretty easily- you just slap a negative sign on the front of your number and call it a day. Unfortunately, computers (at a low level) are not smart enough to afford us this same convenience.\newline

Luckily, some very clever engineers figured out how to account for negative numbers. In fact, they came up with multiple ways to represent them, but in the case of 216, we'll focus on a method known as \textbf{Two's Complement}, which is basically the industry standard in this case.\newline

Having the ability to represent negative numbers using only binary allows us to represent many mathematical problems fairly easily on computers.\newline

So what is \textbf{Two's Complement}? Simply speaking, it's a notation based in binary that allows us to easily represent negative numbers.\newline

\subsubsection{The Cost of Using Two's Complement}

First, you'll need to take note that given \textit{n} bits to represent numbers with, using Two's complement, you'll only be able to represent numbers from $0$ to $2^{n-1}-1$. This is because we use what would be the \textit{most significant bit}, (that is, the bit which holds the highest value in binary) as the bit that tells us whether we're using a negative number or not. For example, if we were using 8 bit numbers:\newline

{
\centering


\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp33747664519688614] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (179.67,91.33) -- (204.67,91.33) -- (204.67,144.67) -- (179.67,144.67) -- cycle ;
%Shape: Rectangle [id:dp5961693254702363] 
\draw   (204.67,91.33) -- (229.67,91.33) -- (229.67,144.67) -- (204.67,144.67) -- cycle ;
%Shape: Rectangle [id:dp9559418602335925] 
\draw   (229.67,91.33) -- (254.67,91.33) -- (254.67,144.67) -- (229.67,144.67) -- cycle ;
%Shape: Rectangle [id:dp9773364694179354] 
\draw   (254.67,91.33) -- (279.67,91.33) -- (279.67,144.67) -- (254.67,144.67) -- cycle ;
%Shape: Rectangle [id:dp04039980622237671] 
\draw   (279.67,91.33) -- (304.67,91.33) -- (304.67,144.67) -- (279.67,144.67) -- cycle ;
%Shape: Rectangle [id:dp046623928889861777] 
\draw   (304.67,91.33) -- (329.67,91.33) -- (329.67,144.67) -- (304.67,144.67) -- cycle ;
%Shape: Rectangle [id:dp8107258504853246] 
\draw   (329.67,91.33) -- (354.67,91.33) -- (354.67,144.67) -- (329.67,144.67) -- cycle ;
%Shape: Rectangle [id:dp9098116937433045] 
\draw   (354.67,91.33) -- (379.67,91.33) -- (379.67,144.67) -- (354.67,144.67) -- cycle ;
%Straight Lines [id:da018443495168281476] 
\draw    (162.33,204.67) -- (188.13,151.14) ;
\draw [shift={(189,149.33)}, rotate = 475.73] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Curve Lines [id:da9876798074310865] 
\draw    (211,84.67) .. controls (211.67,54.67) and (369.67,60.67) .. (369.67,84.67) ;
%Straight Lines [id:da9752577230827041] 
\draw    (288.33,39.33) -- (288.33,57.33) ;
\draw [shift={(288.33,59.33)}, rotate = 270] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (181.67,94.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Huge \textcolor[rgb]{1,0,0}{0}}}};
% Text Node
\draw (206.67,94.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Huge 0}}};
% Text Node
\draw (231.67,94.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Huge 0}}};
% Text Node
\draw (256.67,94.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Huge 0}}};
% Text Node
\draw (281.67,94.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Huge 0}}};
% Text Node
\draw (306.67,94.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Huge 0}}};
% Text Node
\draw (331.67,94.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Huge 0}}};
% Text Node
\draw (356.67,94.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont {\Huge 0}}};
% Text Node
\draw (38.67,209.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {If this bit is 0, the number is positive\\If this bit is 1, the number is negative};
% Text Node
\draw (107.33,11.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {We can use the rest of these bits to represent our number};


\end{tikzpicture}\newline\newline

}

That being said, it's a good rule of thumb not to store numbers that exceed the second to most significant bit on Two's complement systems. (On an 8-bit system like in the diagram above, this would mean that the largest number we can store is \texttt{01111111}.\newline

Here's how you'd actually go about doing it. Let's say you had an integer \texttt{n}. If you wanted to store \texttt{n} on a system that uses Two's Complement, you'd look at \texttt{n}'s sign. If it were 0 or positive, you're all good. No Two's complement magic has to happen as long as \texttt{n} does not exceed the storage afforded to you on the available bits. (make sure not to use the most significant bit!) In other words, on an 8-bit system using Two's Complement, the largest number we'd be able to store is 125, or \texttt{01111111} like we mentioned above.\newline

\subsubsection{Negative Numbers}

However, if \texttt{n} were negative, it's a little more complicated. Here's what you would do in that case. For\newline

First, find the \textit{complement} of the number you're trying to represent. For this example, let's assume that we were trying to represent $-5$.\newline

For now, let's forget about the negative sign. In binary, 5 ends up being \texttt{0101}. The complement of this number is basically just the opposite of all the bits in the number, which would end up being \texttt{1010}.\newline

Next, you'll want to add 1 to the number. We do this so that when we end up doing math that involves negative numbers, it comes out correctly. As such, 5 in Two's Complement notation is \texttt{1011}.\newline

\subsubsection{The Most Significant Bit}

Remember when we made sure to keep that first most significant bit as zero if the number was positive? We did that on purpose, so that if we flipped the bits to find the complement, we would end up having a 1 in the most significant bit. In that sense, we can tell if our number is negative just by checking that first most significant bit. If it's a 1, we know for sure that our number is negative, and if it's a 0, we know for sure that our number is positive.

\subsubsection{How it All Comes Together}

Now you may be wondering: having that first most significant bit to tell us if numbers are positive or negative is a bit clever, but why would we perform these seemingly arbitrary operations on a binary number? Honestly, I think it's a little harder to convert negative numbers from Two's Complement notation back into decimal, only because the number isn't as immediately obvious as it would be in binary- in other words, it doesn't look as intuitive.\newline

The real magic behind two's complement is when you actually try to do math with it. If you do some basic binary addition with Two's Complement, you'll find that the negative numbers \textbf{actually work}.\newline

For example, if you try adding 2 and -2 (\texttt{0010} and \texttt{1110}), you'll end up with \texttt{0000} (truncate the overflow bit at the far left), which is 0! Try it with some other numbers, it just works!\newline

In conclusion, Two's Complement has a few nuances, but here's what you need to remember: It's a notation that, at the cost of the most significant bit, allows us to cleverly represent negative numbers in an environment with only binary, and is designed in such a way that addition, subtraction, and other operations work perfectly within it.

\subsection{Practice Worksheet}

TAs have been given specific instructions not to share the answers to this worksheet, but feel free to follow along and complete this for practice (and maybe drop by discussion or office hours for help getting the correct solutions if need be). The worksheet itself can be found at the following link:\newline

{
\textit{
\href{http://www.cs.umd.edu/class/spring2019/cmsc216/labs/BitwiseOpWorksheet.pdf}{http://www.cs.umd.edu/class/spring2019/cmsc216/labs/BitwiseOpWorksheet.pdf}\newline
}
}


For problems 1-5 on the worksheet, you'll find the reasoning in the 'Converting Between Number Systems' section and the 'Two's Complement' section to be the most helpful. For problems 6-8, you'll find the 'Bitwise Operations' section to be the most helpful.\newline

Simply understanding the logic behind the bitwise operations here isn't enough. Making sure you understand how to actually implement the bitwise operators in C is the key. Additionally, if you practice enough conversions from decimal into other number systems, and then enough from other number systems back into decimal in order to understand both of these processes, I'd say you're in great shape for the exam.

\section{Week 9}

\subsection{Introduction to Assembly}

This week, we're going to start talking about even lower-level programming: Assembly. It can be argued that Assembly is about the closest you can get to the hardware when you're writing industry-standard code for a computer or embedded system, and for good reason. It's extremely simple in nature, which is both a blessing and a curse. It's great in the sense that, from an educational point of view, you'll only be faced down with very simple programming problems to solve, ranging from simple arithmetic to basic recursion problems. It's not so great in the sense that you'll find yourself a little miffed when previously trivial tasks like printing a string with a concatenated integer, or a recursive call, suddenly become a little painful. One thing is for sure- Assembly is truly 'low-level programming'. \textit{Why use many features when few feature do trick?}

\subsubsection{MIPS Assembly}

Specifically, we'll be learning MIPS Assembly. The type of Assembly that 216 sections learn tends to switch from semester to semester, but MIPS is highly useful in its own right. If you were curious, MIPS stands for Microprocessor without Interlocked Pipeline Stages, and was created by a company that shared that same name. Popular systems that took advantage of MIPS or MIPS derivatives ranged from routers, internet modems, other embedded systems, and even the Nintendo N64.\newline

Basically, thanks to its popularity in the early days of computing, its influence on future RISC (Reduced Instruction Set Computer) architectures, and its relative ease to understand, we're fortunate enough to cover it in 216.

\subsubsection{System Memory Structure}

Before we get started, I think it's important to point out this diagram from lecture. Since we are programming on a very low level, understanding how the memory that we're toying with is structured is a great way to solidify our understanding of MIPS Assembly as a whole.\newline

This diagram, from Uppsala University (\texttt{it.uu.se}) is a perfect way to think of the memory that MIPS will be dealing with. If you haven't already, I would highly recommend checking out Prof. Shankar's video on QTSpim, where he talks us through what I'm about to go over.\newline

As a side note, you've probably already seen this diagram, but I'm going to recreate it for you going from the \textbf{lowest address at the top} down to the \textbf{highest address at the bottom}, like they have it displayed in \texttt{qtspim}, for consistency's sake.\newline

{
\centering





\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp25416966228394255] 
\draw   (116.67,12) -- (454.33,12) -- (454.33,292) -- (116.67,292) -- cycle ;
%Shape: Rectangle [id:dp7905442520555432] 
\draw  [fill={rgb, 255:red, 80; green, 227; blue, 194 }  ,fill opacity=1 ] (116.67,12) -- (454.33,12) -- (454.33,35.33) -- (116.67,35.33) -- cycle ;
%Shape: Rectangle [id:dp15378002183259654] 
\draw  [fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (116.67,35.33) -- (454.33,35.33) -- (454.33,79.33) -- (116.67,79.33) -- cycle ;
%Shape: Rectangle [id:dp8855964545796089] 
\draw  [fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (116.67,79.33) -- (454.33,79.33) -- (454.33,123.33) -- (116.67,123.33) -- cycle ;
%Shape: Rectangle [id:dp7116959279006391] 
\draw  [fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (116.67,123.33) -- (454.33,123.33) -- (454.33,161.33) -- (116.67,161.33) -- cycle ;
%Shape: Rectangle [id:dp6624445156874957] 
\draw  [fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=1 ] (116.67,194) -- (454.33,194) -- (454.33,232) -- (116.67,232) -- cycle ;
%Shape: Rectangle [id:dp7618368015684445] 
\draw  [fill={rgb, 255:red, 80; green, 227; blue, 194 }  ,fill opacity=1 ] (116.67,263.33) -- (454.33,263.33) -- (454.33,292) -- (116.67,292) -- cycle ;
%Shape: Rectangle [id:dp1493181266727368] 
\draw  [fill={rgb, 255:red, 80; green, 227; blue, 194 }  ,fill opacity=1 ] (116.67,232) -- (454.33,232) -- (454.33,263.33) -- (116.67,263.33) -- cycle ;
%Shape: Rectangle [id:dp8007385016550638] 
\draw  [fill={rgb, 255:red, 248; green, 231; blue, 28 }  ,fill opacity=0.16 ] (116.67,160.67) -- (454.33,160.67) -- (454.33,194) -- (116.67,194) -- cycle ;
%Up Arrow [id:dp7493047182637006] 
\draw  [fill={rgb, 255:red, 208; green, 2; blue, 27 }  ,fill opacity=1 ] (292.92,165.6) -- (278.08,174.67) -- (263.25,165.6) -- (270.67,165.6) -- (270.67,152) -- (285.5,152) -- (285.5,165.6) -- cycle ;
%Up Arrow [id:dp34905801452398144] 
\draw  [fill={rgb, 255:red, 208; green, 2; blue, 27 }  ,fill opacity=1 ] (263.67,189.07) -- (278.5,180) -- (293.33,189.07) -- (285.92,189.07) -- (285.92,202.67) -- (271.08,202.67) -- (271.08,189.07) -- cycle ;

% Text Node
\draw (118.67,15) node [anchor=north west][inner sep=0.75pt]   [align=left] {Reserved by Kernel};
% Text Node
\draw (118.67,48) node [anchor=north west][inner sep=0.75pt]   [align=left] {Text (code that you're actually written)};
% Text Node
\draw (461.33,4.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0x00000000}};
% Text Node
\draw (462,28.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0x04000000}};
% Text Node
\draw (460,70.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0x10000000}};
% Text Node
\draw (118.67,93.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {Static Data (known at compile time)};
% Text Node
\draw (118.67,126.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {Heap (dynamically allocated memory)};
% Text Node
\draw (120,210.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {Stack (important- we'll talk about this later!)};
% Text Node
\draw (119.33,242) node [anchor=north west][inner sep=0.75pt]   [align=left] {Kernel Text (can be viewed in qtspim)};
% Text Node
\draw (119.33,271.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {Kernel Data (can be viewed in qtspim)};
% Text Node
\draw (461.33,216.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0x80000000}};
% Text Node
\draw (461.33,251) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0x90000000}};
% Text Node
\draw (462,280.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont 0xffffffff}};


\end{tikzpicture}

\textit{(Lower in the diagram = higher memory address)}\newline


}

The reason I've included this is to go hand in hand with the explanations that are to follow. You'll notice a few key similarities to the machine diagram I posted earlier, from one of the first few weeks. This is because C was essentially built with Assembly as the basis; since Assembly preceded C, a lot of it was used as the basis for C and future languages. Many precedents set by Assembly are still evident in the modern languages of today.

\subsection{Running Assembly: Using \texttt{qtspim} and \texttt{spim}}

There are a few ways to run assembly, but we will be using \texttt{spim}, a simulator that runs MIPS assembly programs. \texttt{spim} also provides some basic debugging features, which I highly recommend getting accustomed to as you start to actually write MIPS code.\newline

Additionally, we use a GUI-based version of \texttt{spim} called \texttt{qtspim}, which incidentally provides a far more visually appealing representation of all the useful data that \texttt{spim} tracks. For the purpose of writing code and debugging, I highly recommend working with \texttt{qtspim} here.\newline

\subsubsection{Installing \texttt{qtspim}}

You can use \texttt{spim} and \texttt{qtspim} on Grace, or, if you want to run your Assembly code locally, you're welcome to get a local installation going. If you don't want to use \texttt{qtspim} via X-windows, I suggest you download it to your machine from this location:\newline

\texttt{\href{https://sourceforge.net/projects/spimsimulator/files/}{https://sourceforge.net/projects/spimsimulator/files/}}\newline

Personally, I recommend using \texttt{qtspim} locally and downloading/uploading files to grace when necessary. It's a lot faster and less frustrating to use.\newline

\subsubsection{First Look at \texttt{qtspim}'s Interface}

When you first launch \texttt{qtspim} (For the purpose of what we're about to work through, I highly recommend you grab \texttt{example\_0.s} from the location below.\newline

\texttt{216public/lecture\_examples/week8/Assembly-MIPS-2-Code.}\newline

First, let's look at what \texttt{qtspim} has to offer- but also what we don't need from it right now. When you run \texttt{qtspim example\_0.s} from either Grace or your local system, you'll be bombarded with a bunch of data. Let's clear up some of that confusion.\newline

First off, you'll see a little tab that shows you your floating point registers. I'm assuming that we've covered the concept of registers and other basic Assembly content in lecture, so I'm going to just skip to telling you that we don't need the Floating Point registers right now. We're interesting in storing data + viewing data from the integer registers, so let's only keep that tab open. (Check the diagram below if you need any help).\newline

Additionally, there's data that's in the Kernel space that we don't really care about for now either. Specifically, this is the data that we colored teal in the diagram above. Head over to the \textbf{Window} menubar option (again, highlighted in the below diagram) and uncheck the boxes for 'Kernel Data' and 'Kernel Text'. We're more interested in the User Data and User Text, which is the stuff that we provide.\newline 

{
\centering



\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Image [id:dp10873138490839307] 
\draw (344.61,147.67) node  {\includegraphics[width=286.92pt,height=221.5pt]{img/qtspim1.png}};
%Straight Lines [id:da8419523950188837] 
\draw    (73,68.67) -- (163.77,38.63) ;
\draw [shift={(165.67,38)}, rotate = 521.69] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da06871503564513304] 
\draw    (546.33,148.67) -- (312.76,22.95) ;
\draw [shift={(311,22)}, rotate = 388.28999999999996] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (0.67,71.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {We won't be needing\\these anytime soon.\\Go ahead and close\\this view.};
% Text Node
\draw (548.33,151.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {Open this menu to\\remove all the\\other 'extra' views\\that we won't need\\for now.};


\end{tikzpicture}\newline


}

Now that we've got the UI configured for our needs, let's explore how qtspim can give us more valuable insight into what our code is doing. First, let's examine what's going on in the 'User Text' tab on \texttt{qtspim}. This shows us our code at a glance, and it's exactly the same as the 'User Text' block in the diagram I provided above. However, it gives us just a little more than that. Let's focus in on a random line from the User Text section in \texttt{qtspim}.\newline\newline

{
\centering



\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Straight Lines [id:da19867976067670345] 
\draw [color={rgb, 255:red, 144; green, 19; blue, 254 }  ,draw opacity=1 ]   (355.67,74) -- (647.67,74) ;
%Straight Lines [id:da6150885554955349] 
\draw [color={rgb, 255:red, 144; green, 19; blue, 254 }  ,draw opacity=1 ]   (508.33,172.67) -- (507.03,84) ;
\draw [shift={(507,82)}, rotate = 449.16] [color={rgb, 255:red, 144; green, 19; blue, 254 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da4876031577213086] 
\draw [color={rgb, 255:red, 65; green, 117; blue, 5 }  ,draw opacity=1 ]   (175,74) -- (283.67,74) ;
%Straight Lines [id:da13731004918503975] 
\draw [color={rgb, 255:red, 65; green, 117; blue, 5 }  ,draw opacity=1 ]   (234.33,238.67) -- (230.38,84.67) ;
\draw [shift={(230.33,82.67)}, rotate = 448.53] [color={rgb, 255:red, 65; green, 117; blue, 5 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8916910085429156] 
\draw [color={rgb, 255:red, 139; green, 87; blue, 42 }  ,draw opacity=1 ]   (92.33,74) -- (159.67,74) ;
%Straight Lines [id:da7274101432312404] 
\draw [color={rgb, 255:red, 139; green, 87; blue, 42 }  ,draw opacity=1 ]   (126.33,108.67) -- (126.33,81.33) ;
\draw [shift={(126.33,79.33)}, rotate = 450] [color={rgb, 255:red, 139; green, 87; blue, 42 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da12542541209218405] 
\draw [color={rgb, 255:red, 208; green, 2; blue, 27 }  ,draw opacity=1 ]   (47.67,168) -- (48.32,81.33) ;
\draw [shift={(48.33,79.33)}, rotate = 450.43] [color={rgb, 255:red, 208; green, 2; blue, 27 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9635315027442365] 
\draw [color={rgb, 255:red, 208; green, 2; blue, 27 }  ,draw opacity=1 ]   (13.67,74) -- (83,74) ;

% Text Node
\draw (8,52) node [anchor=north west][inner sep=0.75pt]   [align=left] {{\fontfamily{pcr}\selectfont [00400034] 20440001 \ addi \$4, \$2, 1 \ \ \ \ \ \ ; 17: add \$a0, \$v0, 1 \# \$a0 = input + 1 }};
% Text Node
\draw (408,174.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {\textcolor[rgb]{0.56,0.07,1}{MIPS code that you've written}};
% Text Node
\draw (144,247.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {\textcolor[rgb]{0.25,0.46,0.02}{Actual Assembly instruction}};
% Text Node
\draw (60,113.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {\textcolor[rgb]{0.55,0.34,0.16}{Machine translation}\\\textcolor[rgb]{0.55,0.34,0.16}{of Assembly code}};
% Text Node
\draw (12,176.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {\textcolor[rgb]{0.82,0.01,0.11}{Address at which}\\\textcolor[rgb]{0.82,0.01,0.11}{operation will be}\\\textcolor[rgb]{0.82,0.01,0.11}{executed}};


\end{tikzpicture}\newline


}

Only after the semicolon does it show you the code your wrote. To the left of the semicolon, delimited by whitespace, \texttt{qtspim} also shows you: (in order from right to left)\newline

\begin{itemize}
	\item The actual Assembly instruction that your code becomes- it has a lot of similarities to your written Assembly, so feel free to make comparisons between both columns.
	\item The machine instruction that it becomes- slightly more indecipherable, but this is what's being transmitted to the machine in a much more raw sense.
	\item In square brackets, the memory address that this operation executes on. Yet another artifact of us being at the lowest level of the computer system.
\end{itemize}

The User Data section is a lot less interesting. If you take a look there right now, you'll see that the program has allocated the string 'Bye Bye', padded with newlines. This is where any data that you allocate statically will show up, e.g. strings that you wish to allocate and mess with.

\subsubsection{Working Through \texttt{example\_0.s}}

There are ways to execute your code in the command line version of this software, just called \texttt{spim}, but I think that the graphical version is a must, especially if you're learning this for the first time. Again, if your connection is not fast enough or you're having other problems with the X-window version of \texttt{qtspim} on Grace, I highly recommend a local installation of \texttt{qtspim}.\newline

Go ahead and begin execution of the \texttt{example\_0.s} (location mentioned above). The easiest way to do this is using the 'step' option to get through the pseudo-instructions. Here's the button I'm talking about:\newline

{
\centering



\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Image [id:dp9755553090645552] 
\draw (340.35,234.38) node  {\includegraphics[width=404.03pt,height=80.06pt]{img/qtspim2.png}};
%Shape: Rectangle [id:dp6048699266792336] 
\draw  [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ] (197,212) -- (227.5,212) -- (227.5,228.25) -- (197,228.25) -- cycle ;
%Straight Lines [id:da05231751219991798] 
\draw [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ]   (161,151.75) -- (207.75,210.19) ;
\draw [shift={(209,211.75)}, rotate = 231.34] [color={rgb, 255:red, 255; green, 0; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Shape: Rectangle [id:dp236835656014867] 
\draw  [color={rgb, 255:red, 126; green, 211; blue, 33 }  ,draw opacity=1 ] (247.5,212.5) -- (266,212.5) -- (266,228.25) -- (247.5,228.25) -- cycle ;
%Straight Lines [id:da38979108665986606] 
\draw [color={rgb, 255:red, 79; green, 147; blue, 0 }  ,draw opacity=1 ]   (352.5,90.75) -- (257.75,209.69) ;
\draw [shift={(256.5,211.25)}, rotate = 308.53999999999996] [color={rgb, 255:red, 79; green, 147; blue, 0 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;

% Text Node
\draw (63.5,96.5) node [anchor=north west][inner sep=0.75pt]   [align=left] {\textcolor[rgb]{1,0,0}{These will move through the}\\\textcolor[rgb]{1,0,0}{program instantly, don't use}\\\textcolor[rgb]{1,0,0}{for debugging}};
% Text Node
\draw (326.5,31.5) node [anchor=north west][inner sep=0.75pt]   [align=left] {\textcolor[rgb]{0.25,0.46,0.02}{This will step through}\\\textcolor[rgb]{0.25,0.46,0.02}{your program; it's what}\\\textcolor[rgb]{0.25,0.46,0.02}{we want}};


\end{tikzpicture}\newline

}

As you step through the program, take note of the changes in the registers under the 'Int Registers' tab. You'll be able to see these change in real time, as the program executes, and you'll see just how each of these operations work.\newline

At the end of the day, this program performs 3 notable tasks, each with nuances that I'd like you to take note of as you step through it within \texttt{qtspim}. The three main tasks that this program accomplishes are:\newline

\begin{itemize}
	\item It reads an integer from the console.
	\begin{itemize}
		\item Note that it stores the integer in a certain register, and when you check the Int Registers, it stores the value in \textbf{Hexadecimal}. Lots of mistakes arise during debugging when you misinterpret values here, so don't forget this little fact.
	\end{itemize}
	\item It adds one to the integer, then prints the result to the console.
	\begin{itemize}
		\item Note that you're adding a value using the \texttt{addi} command. In Assembly, when we add a number that we haven't previously declared or stored in a variable, we call it an \textbf{immediate}. Here, this command is the short form for 'add immediate'.
	\end{itemize}
	\item it prints the string 'Bye Bye' to the console.
	\begin{itemize}
		\item At this point, you may be seeing a pattern when you want to perform an advanced operation, like reading an integer, or printing said integer. First, you want to make sure the appropriate code (i.e. 1 in this case) is in the \texttt{\$v0} register. Next, you want to prepare any other variables you may need for this operation, usually putting them in a specific register. In our case, we're also loading the address of \texttt{str1} into \$a0. Once the necessary preparations have been made, all we have to do is invoke \texttt{syscall}, and the rest is taken care of for us.
	\end{itemize}
\end{itemize}

It's worth mentioning that, like we saw in this example, there are very clear limitations to Assembly from the outset. For advanced operations like printing a String, we have to go with these seemingly roundabout \texttt{syscall}-based operations in order to get it done. In this example, we saw two examples of how \texttt{syscall} can be used. There are a few more things that syscall can do, which I can list in this handy table.\newline

{

\begin{center}
 \begin{tabular}{||c c c c||} 
 \hline
 Operation & \texttt{syscall} Code & Arguments + Locations & Result \\ [0.5ex] 
 \hline\hline
 \texttt{print\_int} & 1 & \texttt{\$a0} (integer) & NA \\ 
 \hline
 \texttt{print\_float} & 2 & \texttt{\$f12} (float) & NA \\
 \hline
 \texttt{print\_double} & 3 & \texttt{\$f12} (double) & NA \\
 \hline
 \texttt{print\_string} & 4 & \texttt{\$a0} (string) & NA \\
 \hline
 \texttt{read\_int} & 5 & NA & Integer in \texttt{\$v0} \\
 \hline
 \texttt{read\_float} & 6 & NA & Float in \texttt{\$f0} \\
 \hline
 \texttt{read\_double} & 7 & NA & Double in \texttt{\$f0} \\
 \hline
 \texttt{read\_string} & 8 & \texttt{\$a0} (address of buffer), \texttt{\$a1} (length of string) & String starting at \texttt{\$a0} \\
 \hline
 \texttt{sbrk} & 9 & \texttt{\$a0} (amount) & Address in \texttt{\$a0} \\
 \hline
 \texttt{exit} & 10 & NA & NA \\
 \hline  
 
\end{tabular}
\end{center}

}

The only instruction that may not immediately seem intuitive to you is the \texttt{sbrk} syscall code. Don't worry too much about this one for now, but it's basically just \texttt{malloc()} for MIPS.\newline

Remember that Assembly wasn't created with our present-day programming paradigms in mind. In order to get around the limitations of Assembly, I'd recommend thinking back to the need it was built to fulfill in the first place- extremely low-level programming.

\section{Week 10}

\subsection{More on MIPS}

You'll find that we can do a lot of things with MIPS, and as you move through the exercises that we get, you'll figure out the nuances that come along with these tasks.\newline

You'll notice that with MIPS, we pay a lot more attention to the stack than we did when we were writing in C. This is because we usually need to mess around with more than a few variables at once, and an excellent reliable way to do that is by leveraging the stack.

\subsubsection{Function Implementation in C vs Assembly}

First of all, we will cover function implementation, and the differences between how this is done in C and how this is done in Assembly. I'll be recapping the examples in the \textbf{Week 9 - Assembly Slides III} lectures, so feel free to follow along there.\newline

In \textbf{C}, when a function is called, you have a pretty commonplace process. Local variables within that function are stored on the stack, code is executed, and a return value is sent back to the caller. This is exactly what we've been learning so far- shouldn't be anything new.\newline

In \textbf{Assembly (MIPS)}, we're looking at a similar process in concept, yet a little more fleshed out than what we explored in C. Before a function is called, we first put the arguments on the stack and set aside some space for the function's return value on the stack. Next, we jump to our actual function implementation. Within the actual function, we'll put the local variables on the stack (just as we did in C), execute the code (during this time, accessing our arguments and local variables), then we'll put our return value in the appropriate space on the stack. Finally, when we exit the function call, we'll grab the value of the return value from the stack.\newline

This is a pretty high level explanation of how functions are implemented, but it's important to keep this all in mind as we tackle larger problems. I'd say the most important takeaway is to understand that we'll be interacting with the stack a lot more in a very basic sense- things that we used to take for granted, like being able to create as many variables as we wanted in whichever scope was most convenient for us, will probably be a lot harder to do in MIPS.

\subsubsection{Misc. MIPS Takeaways}

Here are some key takeaways I would suggest remembering as we progress further with MIPS. These are tidbits from the MIPS lecture that I think are highly useful as we move along with this stuff.\newline

The \textbf{Stack Pointer} and \textbf{Frame Pointer} are new things that we have to deal with here. It's important to know the difference between them.

\begin{itemize}
	\item The \textbf{stack pointer}, \texttt{\$sp}, is how we keep track of the top of the stack. As our program continues to put stuff onto the stack, the stack pointer simply points to the next vacant space on the stack; to the newest free memory location.
	\item The \textbf{frame pointer}, \texttt{\$fp}, is how we keep track of where our return value will be on the stack. Unlike the stack pointer, this stays the same throughout a function call. As such, offsetting from this pointer is how we access arguments, the return value space, and local vars.
\end{itemize}

Let's also talk a little about MIPS conventions. In particular, you'll see programs structured in a certain way throughout the MIPS instruction you receive here.

\begin{itemize}
	\item The \textbf{prologue} is the region of your MIPS code where you make room on the stack and store your register values. It's where you'll be performing your 'setup' work.
	\item The \textbf{epilogue} is where you'll get those values back from the stack, and go ahead and deallocate room that you've added to the stack. It's analogous to 'cleanup' work.
	\item The \textbf{body} of your code is where you'll be performing the actual stuff- 
\end{itemize}

Additionally, I've been talking a lot about using the stack as a way to pass in function arguments. Technically, the MIPS convention is to use certain registers to pass values in for your arguments. However, some questions and prompts in this course may require you to \textbf{pass all arguments on the stack}, so make sure to keep an eye out.

\begin{itemize}
	\item \textbf{Function Arguments} will be passed in via registers \texttt{\$a0} through \texttt{\$a3}, and if more space ends up being needed, the stack.
	\item The \textbf{Return Value} will usually be found in registers \texttt{\$v0} and \texttt{\$v1}. If more space ends up being needed here, you'll again have to look to the stack. 
\end{itemize}

\subsubsection{Caller-saved vs. Callee-saved}

As you learn about different registers, there's a key point to be noted about the difference between Caller-Saved and Callee-Saved registers. There's a handy guide on the lecture slides (I'm thinking of putting one on this notes document too) that tells you which of the registers are Caller/Callee saved, but make sure you use the appropriate one for the case you're dealing with.\newline

\begin{itemize}
	\item If registers are \textbf{caller-saved}, functions can freely modify those registers, but if those functions call \textit{other functions}, they shouldn't assume that those registers no longer hold the values they set. In other words, if the original function that modified the caller-saved registers calls another function, it should assume that the contents of those registers have now been messed with and are therefore unusable.\textbf{A.k.a. 'temporary registers'; they won't be preserved across different procedure calls.}
	\item If registers are \textbf{callee-saved}, functions that are modifying them are allowed to call another function and know that those registers haven't been messed with, but in turn, they also need to do their due diligence and ensure that these registers retain their original values before returning. \textbf{A.k.a. 'saved registers'; they will be preserved across procedure calls.}
	
\end{itemize}

It may seem more confusing than it is, but just remember this: Caller-saved registers are not preserved across \textit{procedure} (or as we know them, function) calls, while Callee-saved registers are preserved across procedure calls.

\section{Week 11}

\subsection{Process Control- The Computer as a Restaurant}

At the end of the day, this is a systems class. One of the big concepts that we should take some time to understand is the idea of processes, and how those processes affect how we build programs. It may be a little weird at first, and very tempting to confuse them with threads (given that we took a look at them at the end of CMSC132), but I assure you that the two are very different. Here's some stuff that I'd say is very key to remember when learning about and studying for process control material.\newline

It turns out that we haven't seen \textit{this} before, but we've seen fairly similar content, and you may already be thinking in terms of processes when you imagine how computers execute programs. Understanding process control is key to understanding how a computer functions under the hood.\newline

This is meant to be supplementary material, in case the slides and lecture haven't done it for you. As such, I'm going to employ the use of a 'computer as a restaurant' metaphor that I've put together. I've labeled the restaurant analogy sections in case you want to skip over them, but hopefully they help if this process business is getting too abstract to understand.

\subsection{What's a Process? (Restaurant Analogy I)}

This is a word we haven't seen before. Again, the last thing you want to do is get a process confused with a thread.
If you want to get more information on the difference between those, go ahead and take a look at the example in lecture, when they go over the \texttt{ProcessControlA} slides.\newline

Let's use an analogy to better understand processes, and their relation to programs. If a \textbf{program} is like a \textbf{recipe} for a particular order at our restaurant, a \textbf{process} is the \textbf{cook} who follows that recipe. Just as you can have many cooks preparing food from the same recipe, you can have multiple processes running the same program. For the sake of our analogy, let's pretend that once a cook picks up a recipe, they'll be the only ones working on it until it's finished. In other words, every cook has a single recipe.\newline

Now how will those orders come to us? This is where the shell comes in. When the user types the name of a program into the shell, think of it like when you tell your waiter an order. What happens when you do that? Your waiter will go to the kitchen, and give a ticket with your order to the chefs. In a similar way, the \textbf{shell}, like a waiter, will take that order to the kitchen and assign the recipe (your actual program) to a cook (a process) and they'll get started on it. As such, when you type a program name into the shell, it kicks off a new process that will execute your program.\newline

Now, can we say that if you ordered a Spaghetti House Special and if your date ordered a Spaghetti House Special, your orders will be the exact same?  What if your date asked for parmesan cheese sprinkled on top and you absolutely hate that stuff? Furthermore, if the table next to you comes in 15 minutes later and orders the same thing, would you want them getting their Spaghetti House Special first? You'd probably want a way to make sure that your order is yours and yours only. Just like we need a way to keep track of each order being prepared, we also need a way to keep track of every process, just so we can keep tabs on them. Each process is assigned a special \textbf{Process ID}, or \textbf{PID}, to make them easily identifiable and trackable.

\subsection{Multitasking (Restaurant Analogy II)}

Let's say that the restaurant is pretty packed tonight, and a bunch of people have put in their orders. Your assumption is that all the cooks are in there, making everyone's food at the same time, but little do you know, this is a very special kitchen.\newline

Inside, there is only 1 total gas burning stove, one sink, and one set of pots and pans. The fact of the matter here is, only one cook can be working on their recipe at a time, and all the other cooks need to stand by. Horribly inefficient as this may seem, it's very similar to a computer. The fact is, a singular CPU can only handle a process at a time (we'll touch on multi-core processing in a bit), so if your system only has 1 core, it really only is doing one task at a time.\newline

However, these cooks are highly skilled. We're talking Michelin-star level- One cook will use the cooking station for a few minutes, then hand off the station to another cook for a few minutes so they can work for a bit, then take the station back. In a few minutes, they may hand the station off again to yet another cook. No one cook takes the cooking station for very long, and they end up working so fast that it seems like they're working in parallel.\newline

Similarly, a single CPU can give us the illusion of parallel processing by performing a similar technique known as \textbf{time slicing}. By allowing each process to use the processor for \textit{miniscule} bits of time, one after the other, the result was a bunch of processes that finished at relatively the same time. This technology is pretty old, but hey, it works.\newline

Let's tie this back together with our restaurant analogy. Let's say we continued with this seemingly unorthodox time slicing model, and we had 3 cooks preparing 3 different dishes, all of which were ordered one after the other by a family of 3 having dinner. Here are the details.\newline

\begin{itemize}
	\item \textbf{Spaghetti House Special} - \textit{No parmesan!} - 4 mins prep time
	\item \textbf{Pasta Salad} - \textit{Quick and easy} - 2 mins prep time
	\item \textbf{Minestrone Soup} - \textit{Difficult to pronounce} - 3 mins prep time
\end{itemize} 

It's important to note that this was ordered by a family, and as such, each of these dishes would be better if they came out at the same time. Think of it this way, as we bridge the gap between our analogy and these dishes. Think of each order as a process. If you're listening to music and you move your Spotify window across the screen, would you rather have your music stop abruptly while you move your window, then resume when it's done? Or would you suffer nanoseconds (or less!) of lag and have your music and window move happen at (what appears to us humans) the same time?\newline

Let's take a look at how this food comes out with and without time slicing.\newline

{
\centering



% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_04ajd8fkc}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_04ajd8fkc}
{\pgfqpoint{0pt}{0pt}}
{\pgfpoint{\mcSize+\mcThickness}{\mcSize+\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfqpoint{0pt}{0pt}}
\pgfpathlineto{\pgfpoint{\mcSize+\mcThickness}{\mcSize+\mcThickness}}
\pgfusepath{stroke}
}}
\makeatother

% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_x6lyfh0ey}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_x6lyfh0ey}
{\pgfqpoint{0pt}{-\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfqpoint{0pt}{\mcSize}}
\pgfpathlineto{\pgfpoint{\mcSize+\mcThickness}{-\mcThickness}}
\pgfusepath{stroke}
}}
\makeatother

% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_e9vm93gji}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_e9vm93gji}
{\pgfqpoint{-\mcThickness}{-\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfpointorigin}
\pgfpathlineto{\pgfpoint{0}{\mcSize}}
\pgfusepath{stroke}
}}
\makeatother
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp637455473892253] 
\draw  [pattern=_04ajd8fkc,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 245; green, 166; blue, 35}] (96.33,110.33) -- (208.33,110.33) -- (208.33,149.67) -- (96.33,149.67) -- cycle ;
%Shape: Rectangle [id:dp06586434884481551] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][pattern=_x6lyfh0ey,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 208; green, 2; blue, 27}] (208.33,110.33) -- (278.33,110.33) -- (278.33,149.67) -- (208.33,149.67) -- cycle ;
%Shape: Rectangle [id:dp27712049671195493] 
\draw  [pattern=_e9vm93gji,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 74; green, 144; blue, 226}] (278.33,110.33) -- (382.33,110.33) -- (382.33,149.67) -- (278.33,149.67) -- cycle ;
%Straight Lines [id:da6871721096179962] 
\draw    (159.67,72) -- (157.15,104.67) ;
\draw [shift={(157,106.67)}, rotate = 274.4] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9318490798518977] 
\draw    (245.67,70.67) -- (245.04,104) ;
\draw [shift={(245,106)}, rotate = 271.08] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8677348167680938] 
\draw    (337,70.67) -- (335.75,100.67) ;
\draw [shift={(335.67,102.67)}, rotate = 272.39] [color={rgb, 255:red, 0; green, 0; blue, 0 }  ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da946997040439277] 
\draw    (96.33,172.67) -- (96.33,155.33) ;
%Straight Lines [id:da4111242410426823] 
\draw    (382.33,174) -- (382.33,156.67) ;

% Text Node
\draw (123.33,50.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {Spaghetti};
% Text Node
\draw (224.67,50.33) node [anchor=north west][inner sep=0.75pt]   [align=left] {Salad};
% Text Node
\draw (317.33,51) node [anchor=north west][inner sep=0.75pt]   [align=left] {Soup};
% Text Node
\draw (73.33,187) node [anchor=north west][inner sep=0.75pt]   [align=left] {0 mins};
% Text Node
\draw (359.33,187.67) node [anchor=north west][inner sep=0.75pt]   [align=left] {9 mins};


\end{tikzpicture}


}

Now, despite the fact that we did finish in 9 minutes, how will this family feel? Whoever ordered the Spaghetti won't like it because it's been cooling for 5 minutes, whoever ordered the salad is going to think it's a bit soggy, as it's been soaking for 3, and whoever ordered the soup is going to think it's too hot, as it was just finished! This is the mealtime equivalent to having your music stop as you drag your music player window across the screen- just simply splitting the tasks and doing one after another ends up making both tasks a weird experience. Let's try again, this time with time-slicing.\newline\newline

{
\centering




% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_8effkoa4c}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_8effkoa4c}
{\pgfqpoint{0pt}{0pt}}
{\pgfpoint{\mcSize+\mcThickness}{\mcSize+\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfqpoint{0pt}{0pt}}
\pgfpathlineto{\pgfpoint{\mcSize+\mcThickness}{\mcSize+\mcThickness}}
\pgfusepath{stroke}
}}
\makeatother

% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_le9wi3r4q}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_le9wi3r4q}
{\pgfqpoint{0pt}{-\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfqpoint{0pt}{\mcSize}}
\pgfpathlineto{\pgfpoint{\mcSize+\mcThickness}{-\mcThickness}}
\pgfusepath{stroke}
}}
\makeatother

% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_vtbxw2bo1}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_vtbxw2bo1}
{\pgfqpoint{-\mcThickness}{-\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfpointorigin}
\pgfpathlineto{\pgfpoint{0}{\mcSize}}
\pgfusepath{stroke}
}}
\makeatother

% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_796dxsl5e}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_796dxsl5e}
{\pgfqpoint{0pt}{0pt}}
{\pgfpoint{\mcSize+\mcThickness}{\mcSize+\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfqpoint{0pt}{0pt}}
\pgfpathlineto{\pgfpoint{\mcSize+\mcThickness}{\mcSize+\mcThickness}}
\pgfusepath{stroke}
}}
\makeatother

% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_xq1so8yu3}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_xq1so8yu3}
{\pgfqpoint{0pt}{-\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfqpoint{0pt}{\mcSize}}
\pgfpathlineto{\pgfpoint{\mcSize+\mcThickness}{-\mcThickness}}
\pgfusepath{stroke}
}}
\makeatother

% Pattern Info
 
\tikzset{
pattern size/.store in=\mcSize, 
pattern size = 5pt,
pattern thickness/.store in=\mcThickness, 
pattern thickness = 0.3pt,
pattern radius/.store in=\mcRadius, 
pattern radius = 1pt}
\makeatletter
\pgfutil@ifundefined{pgf@pattern@name@_myqc9ofqq}{
\pgfdeclarepatternformonly[\mcThickness,\mcSize]{_myqc9ofqq}
{\pgfqpoint{-\mcThickness}{-\mcThickness}}
{\pgfpoint{\mcSize}{\mcSize}}
{\pgfpoint{\mcSize}{\mcSize}}
{
\pgfsetcolor{\tikz@pattern@color}
\pgfsetlinewidth{\mcThickness}
\pgfpathmoveto{\pgfpointorigin}
\pgfpathlineto{\pgfpoint{0}{\mcSize}}
\pgfusepath{stroke}
}}
\makeatother
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt        

\begin{tikzpicture}[x=0.75pt,y=0.75pt,yscale=-1,xscale=1]
%uncomment if require: \path (0,300); %set diagram left start at 0, and has height of 300

%Shape: Rectangle [id:dp637455473892253] 
\draw  [pattern=_8effkoa4c,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 245; green, 166; blue, 35}] (95.13,70.87) -- (149.8,70.87) -- (149.8,110.2) -- (95.13,110.2) -- cycle ;
%Shape: Rectangle [id:dp06586434884481551] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][pattern=_le9wi3r4q,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 208; green, 2; blue, 27}] (283.4,110.2) -- (321.13,110.2) -- (321.13,149.53) -- (283.4,149.53) -- cycle ;
%Shape: Rectangle [id:dp27712049671195493] 
\draw  [pattern=_vtbxw2bo1,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 74; green, 144; blue, 226}] (181.53,149.53) -- (231.27,149.53) -- (231.27,188.87) -- (181.53,188.87) -- cycle ;
%Straight Lines [id:da946997040439277] 
\draw    (95.13,211.87) -- (95.13,194.53) ;
%Straight Lines [id:da4111242410426823] 
\draw    (382.33,211.6) -- (382.33,194.27) ;
%Shape: Rectangle [id:dp7551289350159917] 
\draw  [pattern=_796dxsl5e,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 245; green, 166; blue, 35}] (231.27,70.87) -- (282.87,70.87) -- (282.87,110.2) -- (231.27,110.2) -- cycle ;
%Shape: Rectangle [id:dp509165568319727] 
\draw  [color={rgb, 255:red, 0; green, 0; blue, 0 }  ,draw opacity=1 ][pattern=_xq1so8yu3,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 208; green, 2; blue, 27}] (150.2,110.2) -- (181.53,110.2) -- (181.53,149.53) -- (150.2,149.53) -- cycle ;
%Shape: Rectangle [id:dp07516811217668684] 
\draw  [pattern=_myqc9ofqq,pattern size=6pt,pattern thickness=0.75pt,pattern radius=0pt, pattern color={rgb, 255:red, 74; green, 144; blue, 226}] (321.53,149.53) -- (375.4,149.53) -- (375.4,188.87) -- (321.53,188.87) -- cycle ;
%Straight Lines [id:da5341206271621973] 
\draw [color={rgb, 255:red, 245; green, 166; blue, 35 }  ,draw opacity=1 ]   (75,48) -- (114.27,81.11) ;
\draw [shift={(115.8,82.4)}, rotate = 220.14] [color={rgb, 255:red, 245; green, 166; blue, 35 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da6681580330461115] 
\draw [color={rgb, 255:red, 245; green, 166; blue, 35 }  ,draw opacity=1 ]   (75,48) -- (243.04,82.4) ;
\draw [shift={(245,82.8)}, rotate = 191.57] [color={rgb, 255:red, 245; green, 166; blue, 35 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da821619596279752] 
\draw [color={rgb, 255:red, 208; green, 2; blue, 27 }  ,draw opacity=1 ]   (182.73,28) -- (166.94,120.83) ;
\draw [shift={(166.6,122.8)}, rotate = 279.65999999999997] [color={rgb, 255:red, 208; green, 2; blue, 27 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da9096151285321349] 
\draw [color={rgb, 255:red, 208; green, 2; blue, 27 }  ,draw opacity=1 ]   (194.6,28.33) -- (299.52,123.06) ;
\draw [shift={(301,124.4)}, rotate = 222.07999999999998] [color={rgb, 255:red, 208; green, 2; blue, 27 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da615142619412103] 
\draw [color={rgb, 255:red, 74; green, 144; blue, 226 }  ,draw opacity=1 ]   (232.47,230.8) -- (210.46,168.29) ;
\draw [shift={(209.8,166.4)}, rotate = 430.61] [color={rgb, 255:red, 74; green, 144; blue, 226 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da874929815233198] 
\draw [color={rgb, 255:red, 74; green, 144; blue, 226 }  ,draw opacity=1 ]   (232.47,229.2) -- (334.81,178.49) ;
\draw [shift={(336.6,177.6)}, rotate = 513.64] [color={rgb, 255:red, 74; green, 144; blue, 226 }  ,draw opacity=1 ][line width=0.75]    (10.93,-3.29) .. controls (6.95,-1.4) and (3.31,-0.3) .. (0,0) .. controls (3.31,0.3) and (6.95,1.4) .. (10.93,3.29)   ;
%Straight Lines [id:da8841142957924004] 
\draw    (96.33,193.2) -- (382.33,192.8) ;

% Text Node
\draw (72.13,226.2) node [anchor=north west][inner sep=0.75pt]   [align=left] {0 mins};
% Text Node
\draw (358.13,226.87) node [anchor=north west][inner sep=0.75pt]   [align=left] {9 mins};
% Text Node
\draw (38.8,22.6) node [anchor=north west][inner sep=0.75pt]   [align=left] {Spaghetti};
% Text Node
\draw (170.8,9) node [anchor=north west][inner sep=0.75pt]   [align=left] {Salad};
% Text Node
\draw (213.97,237.4) node [anchor=north west][inner sep=0.75pt]   [align=left] {Soup};


\end{tikzpicture}\newline


}

Here's what this would look like if we made use of time-slicing. Notice how all the food still gets done by the end of 9 minutes, but each dish's preparation ended in a manner that seemed much more \textit{synchronous}. That is, they finished within relative closeness to each other, even though all of them ended up taking more time to individually finish. This all happened \textbf{despite} the fact that (check the diagram) only one cook was active in the kitchen at a given point in time. That's basically what we're getting at here. Even though we had one cooking station, we managed to finish all 3 meals within relative closeness of each other (each within just a few minutes of each other). Was this perfect? No, it wasn't. But it was better than just making all three sequentially.\newline

Process control's multitasking and context switching is built off this same phenomenon. There's no true way we can make a single CPU work on more processes than one, so we end up allowing each process to use the CPU for a tiny amount of time, one after the other. In this case, that's like letting each cook work their magic for only a few minutes, then handing off the kitchen to the next cook. The resulting process is this: Although all your processes may take \textit{slightly} longer to run individually, your computer can give the illusion of parallel processing by using this neat scheduling trick. \textbf{TL;DR} - By sacrificing a little bit of time (which is done specifically so that it's almost always hardly noticeable for humans), we can give the illusion of synchronous processing by using context switching for process multitasking.

\subsection{General Process Control Knowledge}

Ok, so that'll be it for our restaurant analogy, only because it gets a little harder to start stringing it together from there. However, there's more that you haven't covered in previous classes regarding process control that's highly interesting, and here's I'm going to go over it.\newline

Again, this is designed to help augment your studying, so I'm going to loosely go over material from the \textbf{Process Control Worksheets} to help you develop your knowledge and better understand those exercises. You'll be going over two this week (Week 11) and I'll link them here. You'll have an additional one for Week 12, and that'll be linked in the next section.

\subsubsection{Process Control Worksheet Links}

\begin{itemize}
	\item \textbf{Process Control Wksht 1} - \texttt{\href{http://www.cs.umd.edu/class/spring2020/cmsc216/labs/ProcessWorksheetI.pdf}{http://www.cs.umd.edu/class/spring2020/cmsc216/labs/ProcessWorksheetI.pdf}}
	\item \textbf{Process Control Wksht 2} - \texttt{\href{http://www.cs.umd.edu/class/spring2020/cmsc216/labs/ProcessWorksheetII.pdf}{http://www.cs.umd.edu/class/spring2020/cmsc216/labs/ProcessWorksheetII.pdf}}
\end{itemize}

\subsubsection{Process Control Ideas}

This section is designed to help you get your bearings and develop the knowledge surrounding the correct answers for the Process Control worksheets I and II. They're not the outright answers, but they're roughly 70\% of the thinking you need to get there.

\subsubsection{The Kernel}

The kernel is not something we've talked about a lot, but it's a central computing concept- quite literally. It's the centerpiece of every operating system, and serves as the main bridge of interaction between the user and the system's lowest level parts. The user's permitted to do a wide variety of things, but when it comes to things like File I/O, accessing external hardware, system memory, drives, and other 'system level tasks', you essentially have to ask the kernel politely for permission, after which it'll let you perform these actions. In simple terms, think of it this way: the kernel is the bridge that your programs and other applications use in order to talk to the CPU, memory, and external devices. It's usually cordoned off into its own allocated space, protected from read/writes from all other programs. This is known as the \textit{kernel space}.

\subsubsection{Thread v. Processes}

This one is explained pretty well in lecture, so go ahead and watch the video if you haven't already. Here's a quick rundown from me. Processes are considered the heavier players in this comparison, and threads are, in fact, just segments of processes. Here's a key point that might come in handy on exams, though. Threads \textbf{share} memory space. Specifically, they share \textbf{address space}, \textbf{file descriptors}, and the \textbf{heap}, yet they \textbf{don't share the stack}. Processes, on the other hand, get a whole place to themselves- they don't share memory space with other processes. Threads are essentially found within processes. There's plenty more difference, but that's the main stuff. Again, I highly recommend you watch the lecture segment on this.\\

This is also a fairly valid question when it comes to software architecture, and I think the following article does a pretty good job talking about the pros and cons of thread and processes, and how you should decide which to employ for your use-case.\\

\texttt{\href{https://www.backblaze.com/blog/whats-the-diff-programs-processes-and-threads/}{https://www.backblaze.com/blog/whats-the-diff-programs-processes-and-threads/}}

\subsubsection{The \texttt{init} Process}

The \texttt{init} process is the first process that kicks off when a computer starts, and is thus given a process ID (pid) of 1. As such, it's the parent of all other processes on your system.

\subsubsection{Signals}

Signals are basically how processes let each other know something has happened. For example, the kernel can send a \texttt{SIGSEGV} to a process letting it know that a segmentation fault has occurred. Basically, since processes are given their own space to work with, they can't talk to each other very easily. Signals are how their communication is handled.

\subsubsection{Forking}

Forking in the C world is how we create more processes. These processes are called child processes, and usually, forking hits a wall when a) there is no more space to allocate a new process, or b) there are no more available PIDs to be doled out for our new process.

\subsubsection{Zombie Processes (Scary)}

When a process finishes what it's supposed to do, it enters a state where it is known as a 'zombie process' before it's reaped. I talk about how to reap a process below, but make sure that you don't leave these lying around when your program finishes. Creating zombie processes (especially variable amounts of them) results in what's called a \textit{resource leak}, which is not good practice.

\section{Week 12}

More process control this week- but let's focus on zombie processes, reaping children, waiting, and the \texttt{exec} system call. Below is the worksheet that we'll be following along with in discussion. Again, this section is not meant to provide answers for you, but rather guide you in the right direction.

\subsection{General Process Control Knowledge (cont'd)}

\subsubsection{Process Control Worksheet Link}

\begin{itemize}
	\item \textbf{Process Control Wksht 3} - \texttt{\href{http://www.cs.umd.edu/class/spring2020/cmsc216/labs/ProcessWorksheetIII.pdf}{http://www.cs.umd.edu/class/spring2020/cmsc216/labs/ProcessWorksheetIII.pdf}}
\end{itemize}

\subsubsection{Reaping Child Processes}

Here's what you've got to remember when it comes to reaping children. This is essentially the true end of life for a child process- it's when even after it's finished executing, if some of its artifacts still remain in the system, those are all removed. \textbf{When a process is reaped by its parent, it's removed from the process table}. This is done via \texttt{wait()} or \texttt{waitpid()}.

\subsubsection{\texttt{wait()} and \texttt{waitpid()}}

\texttt{wait()} is how parent processes reap children. Basically, if you don't give it any parameters, it's just going to reap the first thing that it can reap- in this case, the first child process that terminates and enters the zombie state. Keep in mind that if we invoke \texttt{wait()} when there are no running child processes, then it will have no effect at all.\\

I think of \texttt{waitpid()} as a more specific version of \texttt{wait()}. They're both designed to do similar things, but \texttt{waitpid()} allows for a lot more customization. If you ever wanted to rewrite a \texttt{wait()} command using \texttt{waitpid()}, you'd want to take a look at the manpage for \texttt{waitpid()} and adjust some parameters.

\subsubsection{Signals and Processes}

As we learned already, processes are fairly isolated on a machine. Even to swap between them, an entire context switch has to occur. You can imagine that it's not easy, then, to allow two processes to communicate. Enter signals. Signals are the key for processes to communicate with each other. For example, if a parent process wants to figure out if its child process terminated and resulted in a segmentation fault, it would use a function like \texttt{WTERMSIG()} to 'catch' any signals generated by said child process upon termination.

\subsubsection{Checking \texttt{WEXITSTATUS(status)}}

The \texttt{WEXITSTATUS} function in C is indispensable. We can use it to determine how a child process terminated- but \textbf{not in all cases}! Specifically, if a child process terminates abnormally, we need to do some extra work before we use \texttt{WEXITSTATUS}. (Check for segfault, etc.)

\subsubsection{Using \texttt{exec*}- The Costume Change Analogy}

I like to think of an \texttt{exec*} system call as a full 'costume change' for a process. Even though a process may be in the middle of something when \texttt{exec*} is called, it now needs to replace everything it has and assume its new role as specified by the parameters of \texttt{exec*}. Specifically, the \textbf{code, static data, stack, and heap are all replaced}. However, just like an actor or actress performing a costume change, the actor/actress remains the same! In other words, despite the changing of the static data, stack, and heap, the \textbf{process remains the same}.\\

The \texttt{exec*} command can fail for a variety of reasons, but most of them are 'system' related. It could be issues that range from an I/O error that occurred when reading from your filesystem, to issues with your \texttt{PATH}, \texttt{argv} or \texttt{envp} values, to running into memory limits, to issues with a directory or file you specified.\\

When it does fail, it returns -1. However, when it succeeds, \textbf{it doesn't return}. This might sound totally absurd to you at first, but think about \textit{what exec* actually does.} Since the entire process is replaced (big costume change), it simply can't return anything to the program that made the call, because that program doesn't exist any longer! It's been replaced by this shiny new program specified in \texttt{exec*}'s parameters.

\section{Week 13}

For our final week of instruction, we've got a few more things about process control that you may find useful. Below is the worksheet that we'll be following for this week.


\begin{itemize}
	\item \textbf{Process Control Wksht 4} - \texttt{\href{http://www.cs.umd.edu/class/spring2020/cmsc216/labs/ProcessWorksheetIV.pdf}{http://www.cs.umd.edu/class/spring2020/cmsc216/labs/ProcessWorksheetIV.pdf}}
\end{itemize}
 
\subsection{UNIX vs. Standard I/O}

The main difference between these two \textbf{totally valid} methods of conducting input and output is that Standard I/O generally features buffers, while Unix I/O does not.\\

Usually, you don't want to mix the two of these.

\subsection{File Descriptor Table}

Every process has a \textbf{file descriptor table} that just keeps track of the files that are opened. In addition, the table keeps track of \texttt{stdin}, \texttt{stdout}, and \texttt{stderr} by default. These are opened to the file numbers 0, 1, and 2 by default.

\subsection{Forking?}

How does \texttt{fork()} play into all of this? Well, the \texttt{fork()} system call makes a new process with a copy of the stack, the heap, data, and text, along with the file descriptor table of the process that calls \texttt{fork()}.\\

However, don't get this mixed up with \texttt{exec*}! When you call \texttt{exec*}, the stack, heap, data, and text are overwritten, but the file descriptor table is not overwritten.

\subsection{Reference Count}

So what's a reference count all about? Basically, open file descriptors have reference counts, which mean exactly what you think they'd mean- it's just the number of times that \textit{it} is being referenced by something else. When a file's reference count drops to zero, it is no longer being referenced by anything, so C gets rid of it. As you close file descriptors using \texttt{close()}, you'll decrease the reference count for files.\\

\subsection{\texttt{dup2}}

What \texttt{dup2} allows us to do is copy from one file descriptor to another file descriptor. This allows us to do neat tricks like change standard out into a pipe to another process. That way, we can fool UNIX into thinking that it's printing to standard out when it might actually be printing to another file, for example.

\section{Closing Thoughts}

This document is complete as of May 4, 2020. Please send errors to \texttt{apraveen@cs.umd.edu}\newline

\textbf{New as of Mar. 2020: Due to the migration to online classes for the duration of the COVID-19 University Closure, this document will be updated more frequently for the convenience of students.}

\end{document}