CS 3410: Computer System Organization and Programming

CS 3410, “Computer System Organization and Programming,” is your chance to learn how computers really work. You already have plenty of experience programming them at a high level, but how does your code in Java or Python translate into the actual operation of a chunk of silicon? We’ll cover systems programming in C, assembly programming in RISC-V, the architecture of microprocessors, the way programs interact with operating systems, and how to correctly and efficiently harness the power of parallelism.

Syllabus

Communications

Announcements and Q&A: Ed

We will be using Ed for all announcements and communication about the course. Each assignment will also have a pinned post at the top of the Ed Discussion forum which you should check regularly, especially before you begin work on an assignment. We recommend checking Ed often, and don’t miss the announcement emails.

For time sensitive matters, please email cs3410-staff@cornell.edu. This is the fastest way to get a response as it goes straight to many inboxes.

For sensitive topics that need to be handled exclusively by the instructor(s), please email cs3410-prof@cornell.edu or meet with the instructor(s) during their bookable office hours. Please do not email the instructor(s) directly using a netID email address; it is important to keep all 3410 communication in one place.

Accessing Ed

Log in to Ed with your netid@cornell.edu email address. You can also access the Ed Discussion through the link on Canvas.

How to use Ed

99% of all matters can be handled on Ed. Do not reach out to the instructor or a TA if your question/problem is one other students might have. Asking on Ed will get you your answer faster and also help others benefit from your asking. Additionally, if you can answer someone else’s question yourself, please do (but be careful not to post solutions)!

If you’re not sure whether something is OK to post, contact the course staff privately. You can do that by marking your question as “Private” when you post it.

Never post screenshots of code.

Screenshots are inaccessible, hard to copy and paste, and hard to read on small screens (e.g., phones). Use Ed’s “code block” feature and paste the actual code.

Assignments: Gradescope

You will submit your solutions to assignments and receive feedback and grades through Gradescope. The weekly topic mastery quizzes will also be posted on Gradescope, as well as graded exams.

We try to grade anonymously, i.e., the course staff won’t know who we’re grading. So please do not put your name or NetID anywhere in the files you upload to Gradescope. (Gradescope knows who you are!)

Accessing Gradescope

Log in to Gradescope with your netid@cornell.edu email address. You can also access Gradescope through the link on Canvas.

Textbooks

This course does not closely follow any one text. You will be responsible for understanding the material presented in lecture and the lecture notes. You can find the lecture note that corresponds to each lecture on the schedule.

That said, we will post readings to accompany each lecture (also found on the schedule page). We will be using three textbooks:

1. Computer Organization and Design RISC-V Edition: The Hardware Software Interface, 2nd Edition by David A. Patterson and John L. Hennessy (ISBN: 9780128245583)
   • This textbook will be provided digitially to you via the Cornell Academic Materials Program.
2. Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
   • This textbook can be downloaded for free from the book’s webpage.

Course Policies

Lectures

PollEverywhere

For in-class activities and polls, we will be using PollEverywhere instead of iClickers. Your participation using PollEverywhere factors into your semester grade. PollEverywhere requires you to bring an Internet-connected device, preferably one that can scan a QR code.

Typically, answering all but 1 of the questions for a given day will give you full points for the day. (This doesn’t really work when there is only one question, obviously.) There will often be a question at the very start of class. Because of the leniency baked into the scoring, we will not manually adjust your participation score if you are late to class, must leave early, your car battery dies, you were in the bathroom for a question, you are feeling ill, you have to quarantine, etc. We know there are very good reasons to miss a PollEverywhere activity, but if we adjust scores by hand the software recognizes the inconsistency and refuses to sync future scores.

Electronic Devices

Electronic devices are known distractors for users and those nearby.

• Phones: Phone use is only allowed to participate in PollEverywhere activities.

• Laptops: Laptop use is allowed only in the left-hand part of the lecture hall, facing the front.

• Tablets: If you use your tablet like a laptop (propped up and you type on it) then please use it in the laptop section. If you use your tablet like a notebook (write on it with a stylus and keep it at an angle such that those behind you do not see what your are writing) you may use it in any section.

Labs

Your physical and mental attendance at the Lab Section that you are enrolled in is required. If you work on a lab for the entire lab section, you will get credit regardless of how far you get. If you show up and do non-lab work (even if it is work for CS 3410) or if you don’t show up to lab but argue that you did the work on your own you will not get credit for the lab.

You are responsible for ensuring that your attendance was recorded properly before the end of your lab. You can check your lab attendance grade on Canvas under the grades tab or from the lab itself. We are unable to retroactively change your lab attendance grade.

Missing (i.e., not getting credit for) more than 3 labs will lower your final grade by one grade per missed lab. For example, if you earn an A- in the class but you miss 5 labs, you will receive a B in the class.This flexibility is there to account for unavoidable absences. Furthermore, due to the add/drop period, the first lab is optional (but strongly recommended!).

To help maintain a high staff-to-student ratio we require that you attend the lab section that you are enrolled in. If you need to change Lab Sections, do so officially on Student Center, but use the swap feature so as not to lose your spot in the lecture.

Office Hours

• TA office hours are a great place to get help with assignments, weekly topic mastery questions, and technical support (e.g., setting up the course infrastructure, VS Code, using Git). See Office Hours for details.

• Instructor office hours are for lecture material, conceptual questions, and sensitive issues. For debugging and assignment help, please use TA office hours instead (or post on Ed)!

Students with Disabilities

Your access in this course is important to us. Please register with Student Disability Services (SDS) to document your eligibility early in the semester and let us know so that we have adequate time to arrange your approved academic accommodations.

Exam Accomodations

If you have an accommodation of extended time or access to a low-distraction room, we have mechanisms in place to meet your needs. If your letter has been sent 2 weeks prior to the prelim, you can verify our awareness of your needs by checking your “score” on the Exam Accommodation Assignment. You will also receive an email confirming our awareness of your needs no later than the Friday before the exam. If, however, your accommodation is granted within 2 weeks of the prelim or you have a unique exam accommodation (for example, you need the exam to be printed in a larger font), please email cs3410-prof@cornell.edu to make sure we accommodate you in a proper and timely manner.

Lecture Accommodations

If you have an accommodation that has to do with the lecture (you need a particular seat or require that the instructor wear a particular mic), please send an email to cs3410-prof@cornell.edu to make us aware of your needs.

Efforts have been made to comply with all accessibility requirements. If you experience any access barriers in this course, such as with printed content, graphics, online materials, or any communication barriers, please reach out to the instructor or your SDS counselor right away. If you need an immediate accommodation, please speak with the instructor after class or email the instructor and SDS at sds_cu@cornell.edu. If you have or think you may have a disability, please contact SDS for a confidential discussion: sds_cu@cornell.edu, 607-254-4545, https://sds.cornell.edu.

If you experience personal or academic stress or need to talk to someone who can help, contact the instructors or:

• Engineering academic advising
• Arts & Sciences academic advising
• Learning Strategies Center
• Let’s Talk Drop-in Counseling at Cornell Health
• Empathy Assistance and Referral Service (EARS)

Please also explore other mental health resources available at Cornell.

Academic Integrity

All submitted work must be completed exclusively by you. Please adhere to the following rules of collaboration:

• Do not look at or be in possession of other students’ (current or former) solutions.
• Do not look at code that you did not write (including code online or generated by an AI tool).
• Do not show other students your work or (screen) share solutions, not even to help each other.
• Do not write documentation together.
• Do not design or write a test suite together.
• Cite your sources.
• Definitely ask the course staff if you’re not sure whether or not something is OK.

Discussing an assignment with others is fine as long as you do not actually look at each other’s work or discuss matters in such detail that the implementation is essentially finished. As a general rule, if you walk away from your discussion without any written (or snapshotted) notes and then start working on the assignment later on your own, you should be fine.

Most academic integrity violations occur in a moment of panic and stress. If you are tempted to make a bad choice, please do not. The grade penalty for cheating is typically a -100% on the entire assignment, which is significantly worse than simply not turning it in. Other repercussions are detailed on the official university page on Academic Integrity. (As a side note, many academic integrity violations come about when students code up an assignment for hours at the same time, sitting right next to each other. This level of fine-grain interaction usually produces effectively one submission produced by two people. This is not okay; your source code must not bear remarkable syntactic similarity to someone else’s because of your collaboration.)

This AI policy does not apply to the weekly Topic Mastery Quizzes Quizzes. You may help each other with these as much as you like. The goal is to learn the material. If you don’t, that will be obvious when assignments and prelims are graded.

Accepting Responsibility (AR)

This course is participating in Accepting Responsibility (AR), which is a pilot supplement to the Cornell Code of Academic Integrity (AI). For details about the AR process and how it supplements the AI Code, see the AR website.

Use of Generative Artificial Intelligences (GenAI)

Mastering the essential, foundational concepts of this course takes effort and practice. Accordingly, the use of generative artificial intelligence (GenAI) tools is generally discouraged in this course, but will be allowed as an experiment for Spring 2025 under the following conditions:

• Be careful about any use of GenAI. It is known to produce incorrect responses. You are responsible for the correctness of all your work. Although GenAI could be useful as a tutor or helper in programming, it must not become the sole creator of your work.
• You may only use Microsoft Copilot Enterprise using Cornell’s institutional license. You can log in using your NetID.
  • This policy is in place for your protection. By using Copilot Enterprise under Cornell’s license, Microsoft cannot view your conversations with Copilot, and your prompts, answers, and viewed content are not used to train the underlying large language models. Another side benefit of using Cornell’s paid license is that the answers that are provided are likely to be of higher quality than other, free GenAI tools (e.g., a personal ChatGPT or Copilot account).
  • More details about using Microsoft Copilot Enterprise at Cornell can be found here.
• If you use GenAI on an assignment, you must cite it by providing the following information:
  • the prompt you used,
  • the answer provided by Copilot,
  • a short statement about how useful the interaction was to you.

Late Policy for Assignments

Gradescope will accept each assignment (with the exception of the final assignment) up to 3 days late. For each day you submit an assignment late, Gradescope records that you have used a slip day. Each slip day allows you to submit an assignment 24 hours later without penalty. You may never submit an assignment more than 3 days late.

5% of your semester grade is for Punctuality Points. You earn these points by not using more than 10 slip days across assignments 1-10. No slip days will be accepted for the last assignment. At the end of the semester, we will use your slip day usage to calculate your Punctuality Points using the following formula: $$5 - \frac{1}{4} \max(0, \mathit{slip~days~used} - 10)$$ Here are some possible scenarios:

Late Policy for Topic Mastery Quizzes

There is a 48 hour grace period for all online exercises and Topic Mastery Quizzes. Submissions within the grace period incur no late penalty. Many surveys will not have that grace period because either we do not control them (TA assessments, course evaluations) or your on-time response is required to effectively manage the course (e.g., prelim conflicts, etc.) After the grace period, the quizzes will be unavailable and there is no possibility of viewing or submitting them.

Regrade Policy

If you feel that your project or exam was not graded according to the stated rubrics, you may submit a regrade request within one week of the project or exam’s return. Regrade requests are submitted via Gradescope. Please note, regrade requests are a venue for discussion about the application of rubrics, not the rubrics themselves.

If your regrade involves us grading different files than your original submission, please send the changed file(s) to cs3410-staff@cornell.edu. In your regrade request, be sure to mention that the file(s) to be graded are in the staff inbox. Also please explain how these files differ from the original ones you submitted and whether you deem these changes to be significant or minor. (Course staff will assume the changes are major unless you convince them that the changes are minor.) All regrades that involve us grading new files will incur a blanket 25/100 point deduction. If we deem your changes significant (more than just changing a few lines of C code), the regrade will incur an additional 15/100 point deduction. This will be applied even if you submitted wrong/release/corrupted/empty files the first time around. (Again, we strongly suggest you download and check the files you submit to Gradescope at submission time.)

Inclusiveness

You should expect and demand to be treated by your classmates and the course staff with respect. You belong here, and we are here to help you learn and enjoy this course. If any incident occurs that challenges this commitment to a supportive and inclusive environment, please let the instructors know so that the issue can be addressed. We are personally committed to this and subscribe to the Computer Science Department’s Values of Inclusion.

Assessment

Grading

Your semester grade will be calculated approximately as follows :

• Assignments: 35%
• Exams (Prelim1, Prelim2, Final): 45%
• Weekly Topic Mastery Quizzes: 10%
• Assignment Punctuality Points: 5%
• Surveys: 2%
• Online Exercises: 3%
• Grade adjustments:
  • Up to 3% bonus for up to 22 Poll Everywhere attendance points (capped at 100% total). This means that attending at least 22 out of the 28 lectures will award you an extra 3% bonus. In general, you will be awarded a bonus $\mathrm{min}(3n / 22,3)$ percentage points if you attended $n$ lectures.
  • Possible grade deductions for excessive lab absences.

Assignments

Generally, assignments are released weekly on Thursdays and are due on Wednesdays at 11:59PM. See the course schedule. All assignments are to be done indvidually. You’ll turn in assignments via Gradescope. You may use generative AI on all assignments as long as you follow our policy.

Exams

There are two preliminary examinations and a final exam. See the course schedule.

Bring your student ID to all of your exams. We will be taking attendance by having you swipe it through a card reader upon arrival.

Topic Mastery Quizzes

Weekly topic mastery quizzes (TMQs) will help reinforce the lessons from a given week’s lectures. We’ll release the quiz on Sunday. The material will be covered in lectures that week. The quiz due date is the following Friday. These quizzes are also distributed on Gradescope.

As the goal of these quizzes is to give you practice with the lecture material, the grading scheme is very forgiving:

• Don’t like your score? You are welcome to retake the quiz as many times as you like before the due date. We’ll keep your best attempt.

• Your lowest quiz score in grading, so one quiz in the semester is a “freebie.” Also, your quiz grade will be capped at 90%, meaning if you get 9/10 you do not have to retake the quiz to receive a “perfect” quiz score. Note: this cap will be implemented via post-processing by the instructor, so you will not see this cap reflected on Gradescope.

• You may submit each quiz up to 48 hours late without penalty. See the relevant late policy here.

Spring 2025 Course Schedule

Reading Abbreviations

• [P&H]: Computer Organization and Design RISC-V Edition: The Hardware Software Interface, 2nd Edition by David A. Patterson and John L. Hennessy (ISBN: 9780128245583)
• [C]: Modern C by Jens Gustedt
• [OSTEP]: Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau

Lab Sections

Lab sections are split 50/50 between Thursday and Friday. The work in each lab is meant to help you get started on the assignment that is out that week. There is nothing separate to turn in from lab; the work you do in lab will get turned in as part of that week’s assignment.

Exams

There are three exams:

• Two preliminary exams:
  • Prelim 1 on February 20 at 7:30pm
  • Prelim 2 on April 10 at 7:30pm
• The Final exam on May 17 at 2:00pm

Office Hours

We look forward to seeing you in office hours! Check out the schedule of available office hours in this Google Calendar, which is also embedded below.

With TAs

Check the calendar below for the locations of office hours (e.g., Rhodes 529, Ives 107, or a Zoom link).

In-person office hours use a simple whiteboard queueing mechanism; Zoom office hours use Queue Me In.

Office hours do not happen on official Cornell days off and breaks. (We will attempt to make the calendar reflect this fact, but please trust this statement over the calendar.)

With the Instructors

Instructor office hours are appropriate for discussing technical content and course logistics. They are less appropriate for getting help with a specific assignment; please see TAs for that.

• To book a session with Prof. Weatherspoon, please book an appointment here.
• To book a session with Prof. Susag, please book an appointment here.

Meet the Course Staff

Instructors

Hakim Weatherspoon

(he/him)

Professor

Hometown

Ithaca, NY

Ask me about

sports, entrepreneurship, finding a major, finding a career

Zach Susag

(he/him)

CS PhD

Hometown

St. Paul, MN

Ask me about

graduate school, Linux, programming languages, barbeque

Graduate TAs

Keting Chen

(he/him)

CS PhD

Hometown

Chengdu, China

Ask me about

tennis, calligraphy

Salman Abid

(he/him)

CS PhD

Hometown

Karachi, Pakistan

Ask me about

futsal, LitRPGs, the history of chai

Jiahan Xie

(he/him)

CS MS

Hometown

Ningbo, China

Ask me about

violin, movies

Melissa Reifman

(she/her)

CS MEng

Hometown

Upper Saddle River, NJ

Ask me about

cooking, comedy, theater

Kevin Cui

(he/him)

CS MEng

Hometown

Philadelphia, PA

Ask me about

climbing, laufey, chess

Returning Undergraduate TAs

Michael Avellino

(he/him)

CS

Hometown

East Lansing, MI

Ask me about

F1, skiing, and Mario Kart

Angelica Borowy

(she/her)

CS

Hometown

Lake Worth, FL

Ask me about

game development, rock/grunge music, guitar

Serena Duncan

(she/her)

CS

Hometown

State College, PA

Ask me about

Broadway shows, traveling, food

Peter Engel

(he/him)

Math

Hometown

Madison, WI

Ask me about

twitter.com, McDonald's

Alan Han

(he/him)

CS MEng

Hometown

Cleveland, OH

Ask me about

music, swimming, football

David Suh

(he/him)

CS & Archaeology

Hometown

Rochester, NY

Ask me about

skiing, video games

Reese Thompson

(he/him)

CS

Hometown

Horseheads, NY

Ask me about

skiing, hiking, my project team

Jake Berko

(he/him)

CS

Hometown

Cherry Hill, NJ

Ask me about

skiing, pickleball, music

Santiago Blaumann

(he/him)

CS (minor in Physics)

Hometown

Piscataway, NJ

Ask me about

Skiing, Snowboarding, Wine

Will Bradley

(he/him)

CS & Math

Hometown

Rochester, MN

Ask me about

music theater, politics, Lean 4

Caitlyn Cahill

(she/her)

CS

Hometown

Canton, MA

Ask me about

traveling, skiing, Boston sports

Edward Duan

(he/him)

CS

Hometown

Syosset, NY

Ask me about

Chinese yoyo

Alex Koiv

(he/him)

CS

Hometown

Brooklyn, NY

Ask me about

photography, bowling

Andy Li

(he/him)

CS

Hometown

Nanjing, China

Ask me about

databases, hiking, South Park

Timmy Li

(he/him)

CS

Hometown

Gainesville, FL

Ask me about

Brandon Sanderson, Riot Games :(, skiing

Ryan Mistretta

(he/him)

CS

Hometown

Goshen, NY

Ask me about

skiing, tennis, football

Tawakalt Bisola Okunola

(she/her)

CS

Hometown

Mansfield, TX

Ask me about

linguistics, Afrobeats, rap

Noah Plant

(he/him)

CS

Hometown

Sendai, Japan

Ask me about

tennis, board games, Japanese food.

Savitta Sivapalan

(she/her)

CS

Hometown

Bronx, NY

Ask me about

art, movies

Ilya Strugatskiy

(he/him)

CS & Math

Hometown

Larchmont, NY

Ask me about

hiking, Durak

Melvin Van Cleave

(he/him)

CS (minors in Math & Physics)

Hometown

Cincinnati, OH

Ask me about

physics, music, fitness

New Undergraduate TAs

Omar Abuhammoud

(he/him)

CS

Hometown

Brooklyn, NY

Ask me about

games, guitar

Galiba Anjum

(she/her)

CS & IS

Hometown

Bronx, NY

Ask me about

cats, manhwas, gacha games

Bhuwan Bhattarai

(he/him)

CS

Hometown

Columbia, MD

Ask me about

soccer, skiing, Nepal

Luciano Bogomolni

(he/him)

CS

Hometown

Miami, FL

Ask me about

skiing, technology, astrophysics

Nathan Chu

(he/him)

CS

Hometown

Los Angeles, CA

Ask me about

philosophy, League of Legends

Ozan Ersöz

(he/him)

CS

Hometown

Istanbul, Turkey

Ask me about

traveling, pipe organs, skiing

Maximilian Fanning

(he/him)

CS & Plant Science

Hometown

Seattle, WA

Ask me about

music (banjo!), theater tech

Srija Ghosh

(she/her)

CS

Hometown

Lexington, MA

Ask me about

sitcoms, mystery books, chocolate

Andrew Hu

(he/him)

CS

Hometown

Columbus, NJ

Ask me about

cats, fencing, video games

Yunoo Kim

(she/her)

CS

Hometown

Austin, TX

Ask me about

writing, linguistics, Stardew Valley

Alex McGowan

(he/him)

CS

Hometown

Denver, CO

Ask me about

fantasy/sci-fi novels, video games, Christianity

Michael Micalizzi

(he/him)

CS

Hometown

Oceanside, NY

Ask me about

music, volleyball, food

Sharafa Mohammed

(she/her)

CS

Hometown

Edison, NJ

Ask me about

food, event planning, sewing

Kayla Ng

(she/her)

CS

Hometown

Tappan, NY

Ask me about

coffee, apple cider, snowboarding

Asen Ou

(he/him)

CS

Hometown

Seoul, South Korea

Ask me about

Cars, Food, Dogs

John Palsberg

(he/him)

CS

Hometown

Los Angeles, CA

Ask me about

piano, video games

Analeah Real

(she/her)

CS

Hometown

Brooklyn, NY

Ask me about

Animal Crossing, snowboarding, dance

Kelly Yue

(she/her)

CS

Hometown

New York City, NY

Ask me about

steak, xiaolongbao

Vivian Zhou

(she/her)

CS

Hometown

Brooklyn, NY

Ask me about

movies, music

Resources

RISC-V Infrastructure

RISC-V Infrastructure

Tools

• Unix Shell
• Git
• SSH
• Makefiles

C Programming

• Compilation
• Language Basics
• Basic Types
• Prototypes & Headers
• Control Flow
• Declared Types
• Bit Packing
• Pointers
• Arrays
• Strings
• Macros
• Memory Allocation

RISC-V Assembly

RISC-V Assembly

Using the CS 3410 Infrastructure

The coursework for CS 3410 mainly consists of writing and testing programs in C and RISC-V assembly. You will need to use the course’s provided infrastructure to compile and run these programs.

Course Setup Video

We have provided a video tutorial detailing how to get started with the course infrastructure. Feel free to read the instructions below instead—they are identical to what the video describes.

Setting Up with Docker

This semester, you will use a Docker container that comes with all of the infrastructure you will need to run your programs.

The first step is to install Docker. Docker has instructions for installing it on Windows, macOS, and on various Linux distributions. Follow the instructions on those pages to get Docker up and running.

For Windows users: to type the commands in these pages, you can choose to use either the Windows Subsystem for Linux (WSL) or PowerShell. PowerShell comes built in, but you have to install WSL yourself. On the other hand, WSL lets your computer emulate a Unix environment, so you can use more commands as written. If you don’t have a preference, we recommend WSL.

Check your installation by opening your terminal and entering:

docker --version

Now, you’ll want to download the container we’ve set up. Enter this command:

docker pull ghcr.io/sampsyo/cs3410-infra

This command will take a while. When it’s done, let’s make sure it works! First, create the world’s tiniest C program by copying and pasting this command into your terminal:

printf '#include <stdio.h>\nint main() { printf("hi!\\n"); }\n' > hi.c

(Or, you can just use a text editor and write a little C program yourself.)

Now, here are two commands that use the Docker container to compile and run your program.

docker run -i --init --rm -v ${PWD}:/root ghcr.io/sampsyo/cs3410-infra gcc hi.c
docker run -i --init --rm -v ${PWD}:/root ghcr.io/sampsyo/cs3410-infra qemu a.out

If your terminal prints “hi!” then you’re good to go!

You won’t need to learn Docker to do your work in this course. But to explain what’s going on here:

• docker run [OPTIONS] ghcr.io/sampsyo/cs3410-infra [COMMAND] tells Docker to run a given command in the CS 3410 infrastructure container.
• Docker’s -it options make sure that the command is interactive and emulates TTY terminal output, in case you need to interact with whatever’s going on inside the container, and --rm tells it not to keep around an “image” of the container after the command finishes (which we definitely don’t need).
• --init ensures that certain basic responsibilities are handled inside the container; in particular, signal handling and reaping of zombie processes (which you’ll learn about in a few weeks).
• -v ${PWD}:/root uses a Docker volume to give the container access to your files, like hi.c.

After all that, the important part is the actual command we’re running. gcc hi.c compiles the C program (using GCC) to a RISC-V executable called a.out. Then, qemu a.out runs that program (using QEMU).

Make rv and rv-debug Aliases

The Docker commands above are a lot to type every time, and worse, they don’t even include everything you’ll need to invoke our container! To make this easier, we can use a shell alias.

On macOS, Linux, and WSL

Try copying and pasting these commands:

alias rv='docker run -i --init -e NETID=<YOUR_NET_ID> --rm -v "$PWD":/root ghcr.io/sampsyo/cs3410-infra'

Now you can use much shorter commands to compile and run code. Just put rv or rv-debug before the command you want to run, like this:

rv gcc hi.c
rv qemu a.out

NOTE: For the -e NETID=<YOUR_NET_ID> option, use your actual Cornell NetID for the NETID value.

Unfortunately, this alias will only last for your current terminal session. To make it stick around when you open a new terminal window, you will need to add the alias rv=... command to your shell’s configuration file.

First type this command to find out which shell you’re using:

echo $SHELL

It’s probably bash or zsh, in which case you need to edit the shell preferences file in your home directory. Here is a command you can copy and paste, but fill in the appropriate file name (.bashrc or .zshrc) according to your shell:

echo "alias rv='docker run -i --init -e NETID=<YOUR_NET_ID> --rm -v "$PWD":/root ghcr.io/sampsyo/cs3410-infra'" >> ~/.bashrc

Change that ~/.bashrc at the end to ~/.zshrc if your shell is zsh.

On Windows with PowerShell (Not WSL)

(Remember, if you’re using WSL on Windows, please use the previous section.)

In PowerShell, we will create a shell function instead of an alias.

We assume that you have created a cs3410 directory on your computer where you’ll be storing all your code files.

First, open Windows PowerShell ISE (not the plain PowerShell) by typing it into the Windows search bar. There will be an editor component at the top, right under Untitled1.ps1.

There, paste the following (with an appropriate value for NETID, as above):

Function rv_d {
   if (($args.Count) -eq 0) {
      docker run -i --init -e NETID=<YOUR_NET_ID> --rm -v "${PWD}":/root ghcr.io/sampsyo/cs3410-infra
   }
   else {
      $app_args=""
      foreach ($a in $args[1..($args.count-2)]) {
         $app_args = $app_args + $a + " "
      }
      $app_args = $app_args.Substring(0,$app_args.Length-1);
      docker run -i --init -e NETID=<YOUR_NET_ID> --rm -v "${PWD}":/root ghcr.io/sampsyo/cs3410-infra $args[0] $app_args
   }
}

This will create a function called rv_d that takes zero, one, or more arguments (we’ll see what those are in a bit). We’re naming it rv_d and not just rv (as done in the next section) because PowerShell already has a definition for rv. The “d” stands for Docker.

Then, in the top left corner, click “File → Save As” and name your creation. Here, we’ll use function_rv_d. Finally, navigate to the cs3410 folder that stores all your work and once you’re there, hit “Save.”

Assuming you don’t delete it, that file will forever be there. This is how we put it to work:

Every time you’d like to run those long docker commands, open PowerShell (the plain one, not the ISE) and navigate to your cs3410 folder. Then, enter the following command:

. .\function_rv_d.ps1 

This will run the code in that script file, therefore defining the rv_d function in your current PowerShell session. Then, navigate to wherever the .c file you’re working on is located (we assume it’s called file.c) and to compile it, simply type rv_d gcc file.c. To run the compiled code, enter rv_d qemu a.out. Try it out with your hi.c file. Finally, though it’s more of a curiosity right now, running just rv_d with no arguments with give you a prompt in a bash shell, within the Docker container itself.

Debugging C Code

GDB is an incredibly useful tool for debugging C code. It allows you to see where errors happen and step through your code one line at a time, with the ability to see values of variables along the way. Learning how to use GDB effectively will be very important to you in this course.

Entering GDB Commandline Mode

First, make sure to compile your source files with the -g flag. This flag will add debugging symbols to the executable that will allow GDB to debug much more effectively. For example, running:

rv gcc -g -Wall -Wextra -Wpedantic -Wshadow -Wformat=2 -std=c23 hi.c

In order to use gdb in the 3410 container, you need to open two terminals: one for running qemu with the debug mode in the background; and the other for invoking gdb and iteract with it.

1. First, open a new terminal, and type the following commands:

   • docker run -i --rm -v `pwd`:/root --name cs3410 ghcr.io/sampsyo/cs3410-infra:latest. Feel free the change the “name” from cs3410 to any name you prefer.
   • gcc -g -Wall ... (more flags) EXECUTABLE SOURCE.c. Once you have entered the container, compile your source file with the -g flag and any other recommended commands.
   • qemu -g 1234 EXECUTABLE ARG1 ... (more arguments). Now you can start executing qemu with the debug mode and invoke the executable file EXECUTABLE with any arguments you need to pass in.

2. Then, open another terminal, and type the following commands:

   • docker exec -i cs3410 /bin/bash, where cs3410 is the placeholder for the name of the container you are running in the background via the first terminal.
   • gdb --args EXECUTABLE ARG1 ... (more arguments) to start executing the GDB.
   • target remote localhost:1234: execute this inside the GDB. It instructs GDB to perform remote debugging by connecting it to listen to the specified port.
   • Start debugging!

3. Once you quit a GDB session, you need to go back to the first terminal to spin up the qemu again (Step 1.3) and then invoke GDB again (Step 2.2 and onwards).

Checking for Common C Errors

Here are some important limitations of this method:

1. You’ll have to run that script file every time you open a new PowerShell session.
2. This function assumes you’ll only be using it to execute rv_d gcc file.c and rv_d qemu a.out (where file.c and a.out are the .c file and corresponding executable in question). For anything else, this rv_d function doesn’t work. For those, you’d have to type in the entire Docker command and then whatever else after. Another incentive to go the WSL route.

Set Up Visual Studio Code

You can use any text editor you like in CS 3410. If you don’t know what to pick, many students like Visual Studio Code, which is affectionately known as VSCode.

It’s completely optional, but you might want to use VSCode’s code completion and diagnostics. Here are some suggestions:

• Install VSCode’s C/C++ extension. There is a guide to installing it in the docs.
• Configure VSCode to use the container. Put the contents of this file in .devcontainer/devcontainer.json inside the directory where you’re doing your work for a given assignment.
• Tell VSCode to use the RISC-V setup. Put the contents of this file in .vscode/c_cpp_properties.json in your work directory.

Unix Shell Tutorial

This is a modified version of Tutorials 1 and 2 of a Unix tutorial from the University of Surrey.

Listing Files and Directories

When you first open a terminal window, your current working directory is your home directory. To find out what files are in your home directory, type:

$ ls

(As with all examples in these pages, the $ is not part of the command. It is meant to evoke the shell’s prompt, and you should type only the characters that come after it.)

There may be no files visible in your home directory, in which case you’ll just see another prompt.

By default, ls will skip some hidden files. Hidden files are not special: they just have filenames that begin with a . character. Hidden files usually contain configurations or other files meant to be read by programs instead of directly by humans. To see everything, including the hidden files, use:

$ ls -a

ls is an example of a command which can take options, a.k.a. flags. -a is an example of an option. The options change the behavior of the command. There are online manual pages that tell you which options a particular command can take, and how each option modifies the behavior of the command. (See later in this tutorial.)

Making Directories

We will now make a subdirectory in your home directory to hold the files you will be creating and using in the course of this tutorial. To make a subdirectory called “unixstuff” in your current working directory type:

$ mkdir unixstuff

To see the directory you have just created, type:

$ ls 

Changing Directories

The command cd [directory] changes the current working directory to [directory]. The current working directory may be thought of as the directory you are in, i.e., your current position in the file-system tree.

To change to the directory you have just made, type:

$ cd unixstuff

Type ls to see the contents (which should be empty).

Exercise. Make another directory inside unixstuff called backups.

The directories . and ..

Still in the unixstuff directory, type

$ ls -a

As you can see, in the unixstuff directory (and in all other directories), there are two special directories called . and ... In UNIX, . means the current directory, so typing:

$ cd .

(with is a space between cd and .) means stay where you are (the unixstuff directory). This may not seem very useful at first, but using . as the name of the current directory will save a lot of typing, as we shall see later in the tutorial.

In UNIX, .. means the parent directory. So typing:

$ cd ..

will take you one directory up the hierarchy (back to your home directory). Try it now!

Typing cd with no argument always returns you to your home directory. This is very useful if you are lost in the file system.

Pathnames

Pathnames enable you to work out where you are in relation to the whole file-system. For example, to find out the absolute pathname of your home-directory, type cd to get back to your home-directory and then type:

$ pwd

pwd means “print working directory”. The full pathname will look something like this:

/home/youruser/unixstuff

which means that unixstuff is inside youruser (your home directory), which is in turn in a directory called home, which is in the “root” top-level directory, called /.

Exercise. Use the commands ls, cd, and pwd to explore the file system.

Understanding Pathnames

First, type cd to get back to your home-directory, then type

$ ls unixstuff

to list the conents of your unixstuff directory.

Now type

$ ls backups

You will get a message like this -

backups: No such file or directory

The reason is, backups is not in your current working directory. To use a command on a file (or directory) not in the current working directory (the directory you are currently in), you must either cd to the correct directory, or specify its full pathname. To list the contents of your backups directory, you must type

$ ls unixstuff/backups

You can refer to your home directory with the tilde ~ character. It can be used to specify paths starting at your home directory. So typing

$ ls ~/unixstuff

will list the contents of your unixstuff directory, no matter where you currently are in the file system.

Summary

Copying Files

cp [file1] [file2] makes a copy of file1 in the current working directory and calls it file2.

We will now download a file from the Web so we can copy it around. First, cd to your unixstuff directory:

$ cd ~/unixstuff

Then, type:

$ curl -O https://www.cs.cornell.edu/robots.txt

The curl command puts this text file into a new file called robots.txt. Now type cp robots.txt robots.bak to create a copy.

Moving Files

mv [file1] [file2] moves (or renames) file1 to file2.

To move a file from one place to another, use the mv command. This has the effect of moving rather than copying the file, so you end up with only one file rather than two. It can also be used to rename a file, by moving the file to the same directory, but giving it a different name.

We are now going to move the file robots.bak to your backup directory.

First, change directories to your unixstuff directory (can you remember how?). Then, inside the unixstuff directory, type:

$ mv robots.bak backups/robots.bak

Type ls and ls backups to see if it has worked.

Removing files and directories

To delete (remove) a file, use the rm command. As an example, we are going to create a copy of the robots.txt file then delete it.

Inside your unixstuff directory, type:

$ cp robots.txt tempfile.txt
$ ls
$ rm tempfile.txt
$ ls

You can use the rmdir command to remove a directory (make sure it is empty first). Try to remove the backups directory. You will not be able to since UNIX will not let you remove a non-empty directory.

Exercise. Create a directory called tempstuff using mkdir , then remove it using the rmdir command.

Displaying the contents of a file on the screen

Before you start the next section, you may like to clear the terminal window of the previous commands so the output of the following commands can be clearly understood. At the prompt, type:

$ clear

This will clear all text and leave you with the $ prompt at the top of the window.

The command cat can be used to display the contents of a file on the screen. Type:

$ cat robots.txt

As you can see, the file is longer than than the size of the window, so it scrolls past making it unreadable.

The command less writes the contents of a file onto the screen a page at a time. Type:

$ less robots.txt

Press the [space-bar] if you want to see another page, and type [q] if you want to quit reading.

The head command writes the first ten lines of a file to the screen.

First clear the screen, then type:

$ head robots.txt

Then type:

$ head -5 robots.txt

What difference did the -5 do to the head command?

The tail command writes the last ten lines of a file to the screen. Clear the screen and type:

$ tail robots.txt

Exercise. How can you view the last 15 lines of the file?

Searching the Contents of a File

Using less, you can search though a text file for a keyword (pattern). For example, to search through robots.txt for the word “jpeg”, type

$ less robots.txt

then, still in less, type a forward slash [/] followed by the word to search

/jpeg

As you can see, less finds and highlights the keyword. Type [n] to search for the next occurrence of the word.

grep is one of many standard UNIX utilities. It searches files for specified words or patterns. First clear the screen, then type:

$ grep jpeg robots.txt

As you can see, grep has printed out each line containing the word “jpeg”.

To search for a phrase or pattern, you must enclose it in single quotes (the apostrophe symbol). For example to search for spinning top, type

$ grep 'web crawlers' robots.txt

Some of the other options of grep are:

• -v: display those lines that do NOT match
• -n: precede each matching line with the line number
• -c: print only the total count of matched lines

Summary

Don’t stop here! We highly recommend completing the online UNIX tutorial, beginning with Tutorial 3.

Manual Pages

Unix has a built-in “help system” for showing documentation about commands, called man. Try typing this:

$ man grep

That command launches less to read more than you ever wanted to know about the grep command. If you want to know how to use a given command, try man <that_command>.

Saving Time on the Command Line

Tab completion is an extremely handy service available on the command line. It can save you time and frustration by avoiding retyping filenames all the time. Say you want to run this command to find all the occurrences of “gif” in robots.txt:

$ grep gif robots.txt

Try just typing part of the command first:

$ grep gif ro

Then hit the [tab] key. Your shell should complete the name of the robots.txt file.

History

Type history at the command line to see your command history.

$ history

The Up Arrow

Use the up arrow on the command line instead of re-typing your most recent command. Want the command before that? Type the up arrow again!

Try it out! Hit the up arrow! If you’ve been stepping through these tips, you’ll probably see the command history.

Ctrl+r

If you need to find a command you typed 10 commands ago, instead of typing the up arrow 10 times, hold the [control] key and type [r]. Then, type a few characters contained within the command you’re looking for. Ctrl+r will reverse search your history for the most recent command that has that string.

Try it out! Assuming you’ve been working your way through all these tutorials, typing Ctrl+r and then grep will show you your last grep command. Hit return to execute that command again.

Git

Git is an extremely popular tool for software version control. Its primary purpose is to track your work, ensuring that as you make incremental changes to files, you will always be able to revert to, see, and combine old versions. When combined with a remote repository (in our case GitHub), it also ensures that you have an online backup of your work. Git is also a very effective way for multiple people to work together: collaborators can upload their work to a shared repository. (It certainly beats emailing versions back and forth.)

In CS 3410, we will use git as a way of disseminating assignment files to students and as a way for you to transfer, store, and backup your work. Please work in the class git repository that is created for you and not a repository of your own. (Publishing your code to a public repository is a violation of academic integrity rules.)

A good place to start when learning git is the free Pro Git book. This reference page will provide only a very basic intro to the most essential features of git.

Installing Git

If you do not have git installed on your own laptop, you can install it from the official website. If you encounter any problems, ask a TA.

Activate your Cornell GitHub Account

Before we can create a repository for you in this class, we will need you to activate your Cornell github account. Go to https://github.coecis.cornell.edu and log in with your Cornell NetID and password.

Create a Repository

Create a new repository on GitHub: Go to the top right of the GitHub home page, where you’ll see a bell, a plus sign, and your profile icon (which is likely just a pixely patterned square unless you uploaded your own). Click on the downward pointing triangle to the right of the plus sign, and you’ll see a drop-down menu that looks like this:

Click on “New repository” and then create a new repository like this:

Note that the default setting is to make your repository public (visible to everyone). Any repository that contains code for this course should be made private; a public repository shares your code with others which constitutes an academic integrity violation.

Now click on the green “Create Repository” button.

Set Up Credentials

Before you can clone your repository (get a local copy to work on), you will need to set up SSH credentials with GitHub.

First, generate an SSH key if you don’t already have one. Just type this command:

$ ssh-keygen -C "<netid>@cornell.edu"

and use your NetID. The prompts will let you protect your key with a passphrase if you want.

Next, follow the instructions from GitHub to add the new SSH key to your GitHub account. To summarize, go to Settings -> SSH and GPG Keys -> New SSH key, and then paste the contents of a file named something like ~/.ssh/id_rsa.pub.

Clone the Repository

Cloning a git repository means that you create a local copy of its contents. You should clone the repository onto your own local machine (lab computer or laptop).

Find the green button on the right side of the GitHub webpage for your repository that says “Code”. Click it, then choose the “SSH” tab. Copy the URL there, which will look like this:

git@github.coecis.cornell.edu:abc123/play_repo.git

In a terminal, navigate to the folder where you would like to put your repository, and type:

$ git clone <PASTE>

That is, just type git clone (then a space) and paste the URL from GitHub. Run this command to download the repository from GitHub to your computer.

At this point, you’ll get authentication errors if your SSH key isn’t set up correctly. So try that again if you get messages like “Please make sure you have the correct access rights and the repository exists.”

Look Around

Type cd play_repo to enter the repository. Type ls and you’ll see that your repo currently has just one file in it called README.md.

Type git status to see an overview of your repository. This command will show the status of your repository and the files that you have changed. At first, this command won’t show much.

Tracking Files with Git

There are 3 steps to track a file with git and send it to GitHub: stage, commit, and push.

Stage

To try it out, let’s make a new file. Create a new file called <netid>.txt (use your NetID in there). Now type git add NetID.txt from the directory containing the file to stage the file. Staging informs git of the existence of the file so it can track its changes.

Type git status again. You will see the file you added highlighted in green. This means that the file is staged, but we still have two more steps to go to send your changes to GitHub. (You might consider going back to the GitHub web interface to confirm that your new <netid>.txt file doesn’t show up there yet.)

Commit

A commit is a record of the state of the repository at a specific time. To make a commit, run this command:

$ git commit -m "Added my favorite color!"

The message after -m is a commit message, which is an explanation of the changes that you have made since you last committed. Good commit messages help you keep track of the work you’ve done.

This commit is now on your local computer. Try refreshing the GitHub repository page to confirm that it’s still not on the remote repository.

Push

To send our changes to the server, type this:

$ git push

The git push command sends any commits you have on your local machine to the remote machine. You should imagine you are pushing them over the internet to GitHub’s servers. Try refreshing the GitHub repository page again—now you should see your file there!

Pull

You will also want to retrieve changes from the remote server. This is especially helpful if you work on the repository from different machines. Type this command:

$ git pull

For now, this should just say that everything’s up to date. But if there were any new changes on the server, this would download them.

Typical Usage Pattern

Here is a good git workflow you should follow:

1. git pull: Type this before you start working to make sure you’re working on the most up to date version of your code (also in case the staff had to push any updates to you).
2. Work on your files.
3. git add file.txt: Type this for each file you either modified or added to the repo while you were working. Not sure what you touched or what’s new? Type git status and git will tell you!
4. git commit -m "very helpful commit message": Save your changes in a commit. Write a message to remind your future self what you did.
5. git push: Remember that, without the push, the changes are only your machine. If your laptop falls in a lake, then they’re gone forever. Push them to the server for safekeeping.

Git can be a little overwhelming, and sometimes the error messages can be hard to understand. Most of the time, following the instructions git gives you will help; if you run into real trouble, though, please ask a TA. If things get really messed up, don’t be afraid to clone a new copy of your repository and go from there.

It is completely OK to only know a few of the most common git commands and to not really understand how the whole thing works. Many professional programmers get immense value out of git while only ever using add, commit, push, and pull. Don’t worry about learning everything about git up front—you are already ready to use it productively!

Even More Commands

Here are a few other commands you might find useful. This is far from everything—there is a lot more in the git documentation.

Log

Type this command:

$ git log <netid>.txt

You’ll see the history of README.md. You will see the author, time, and commit message for every commit of this file, along with the commit hash, which is how Git labels your commits and how you reference them if you need to. At this point, you’ll only see a single commit. But if you were to change the file and run git commit again, you would see the new change in the log.

You can also type git log with no filename afterward to get a history of all commits in your entire repository.

Stash

If you want to revert to the state of the last commit after making some new changes, you can type git stash. Stashed changes are retrievable, but it might be a hassle to do so.

git stash only works on changes that have not yet been committed. If you accidentally commit a change and want to wipe it out before pulling work from other machines, use git reset HEAD~1 to undo the last commit (and then stash).

Introduction to SSH

SSH (Secure SHell) is a tool that lets you connect to another computer over the Internet to run commands on it. You run the ssh command in your terminal to use it.

The Cornell CS department has several machines available to you, if you want to use them to do your work. SSH is the (only) way to connect to these machines.

Accessing Cornell Resources from Off Campus

Cornell’s network requires you to be on campus to connect to Cornell machines. (This is a security measure: it is meant to prevents attacks from off campus.)

To access Cornell machines when you’re elsewhere, Cornell provides a mechanism called a Virtual Private Network (VPN) that lets you pretend to be on campus. Read more about Cornell’s VPN if you need it.

Log On

Make sure you are connected to the VPN or Cornell’s WiFi. Open a terminal window and type:

ssh <netid>@ugclinux.cs.cornell.edu

but replace with your actual NetID (don’t include the <>). Type yes and hit enter to accept the new SSH host key. Now type your NetID password.

You’re in! You should see a shell prompt; you can follow the Unix shell tutorial to learn how to use it.

Here, ugclinux.cs.cornell.edu is the name of a collection of servers that Cornell runs for this purpose. That’s what you’d replace with a different domain name to connect to a different machine.

scp

Suppose you have a file on the ugclinux machines and you want to get a copy locally onto your machine. The scp command can do this. It works like a super-powered version of the cp command that can copy between machines.

Say your file game.c is located at /home/yourNetID/mygame/game.c on ugclinux. On your local machine (i.e., when not connected over SSH already), type:

$ scp yourNetID@ugclinux.cs.cornell.edu:mygame/game.c .  

Here are the parts of that command:

$ scp <user>@<host>:<source> <dest>  

<user> and <host> are the same information you use to connect to the remote machine with the ssh command. <source> is the file on that remote machine that you want to obtain, and <dest> is the place where you want to copy that file to.

Makefile Basics

This document is meant to serve as a very brief reference on how to read the Makefiles provided in this class. This tutorial is meant to be just enough to help you read the Makefiles you provide, and is not meant to be a complete overview of Makefiles or enough to help you make your own. If you are interested in learning more, there are some good tutorials online, such as this walkthrough.

A Makefile is often used with C to help with automating the (repetitive) task of compiling multiple files. This is especially helpful in cases where there are multiple pieces of your codebase you want to compile separately, such as choosing to test a program or run that program.

Variables

To illustrate how this works, let us examine a few lines in the Makefile that will be used for the minifloat assignment. Our first line of code is to define a variable CFLAGS:

CFLAGS=-Wall -Wpedantic -Werror -Wshadow -Wformat=2 -Wconversion -std=c99

As in other settings, defining this variable CFLAGS allows us to use the contents (a string in this case) later in our Makefile. Our specific choice of CFLAGS here is to indicate that we are defining the flags (for C) that we will be using in this Makefile. Later, when we use this variable in-line, the Makefile will simply replace the variable with whatever we defined it as, thus allowing us to use the same flags consistently for every command we run.

Commands

The rest of our Makefile for this assignment will consist of commands. A command has the following structure:

name: dependent_files
  operation_to_run

The name of a command is what you run in your terminal after make, such as make part1 or make all (this gets a bit more complicated in some cases). The dependent_files indicate which files this command depends on – the Makefile will only run this command if one of these files changed since the last time we ran it. Finally, the operation is what actually gets run in our console, such as when we run gcc main.c -o main.o.

Example Command

To make this more concrete, let us examine our first command for part1:

part1: minifloat.c minifloat_test_part1.c minifloat_test_part1.expected
    $(CC) $(CFLAGS) minifloat.c minifloat_test_part1.c -o minifloat_test_part1.out

This command will execute when we run make part1, but only if one of minifloat.c, minifloat_test_part1.c or minifloat_test_part1.expected have been modified since we last ran this command. What actually runs is the next line, with the $(CC), $(CFLAGS), and a bunch of filenames. $(CC) is a standard Makefile variable that is replaced by our C compiler – in our case, this is gcc. The $(CFLAGS) variable here is what we defined earlier, so we include all of the flags we desired. Finally, the list of files is exactly the same as we might normally run with gcc. In total, then, this entire operation will be translated to:

$(CC) $(CFLAGS) minifloat.c minifloat_test_part1.c -o minifloat_test_part1.out
-->
gcc $(CFLAGS) minifloat.c minifloat_test_part1.c -o minifloat_test_part1.out
-->
gcc -Wall -Wpedantic -Werror -Wshadow -Wformat=2 -Wconversion -std=c99 minifloat.c minifloat_test_part1.c -o minifloat_test_part1.out

This compilation would be a huge pain to type out everytime, especially with all of those flags (and easy to mess up), but with the Makefile, we can run all this with just make part1. We can do the same with make part2 to run the next set of commands instead.

Clean

One final node is that it is conventional (though not required) to include a make clean that removes any generated files, often for being able to clean up our folder or push our work to a Git repository. In our particular file, we have defined clean to remove the generated .out files and any .txt files that were used for testing:

clean:
    rm -f *.out.stackdump
    rm -f *.out
    rm -f *.txt

Complete Makefile

For reference, the entirity of our Makefile is included here:

CFLAGS=-Wall -Wpedantic -Werror -Wshadow -Wformat=2 -Wconversion -std=c99
CC = gcc

all: part1 part2 part3

part1: minifloat.c minifloat_test_part1.c minifloat_test_part1.expected
    $(CC) $(CFLAGS) minifloat.c minifloat_test_part1.c -o minifloat_test_part1.out

part2: minifloat.c minifloat_test_part2.c
    $(CC) $(CFLAGS) minifloat.c minifloat_test_part2.c -o minifloat_test_part2.out

part3: minifloat.c minifloat_test_part3.c
    $(CC) $(CFLAGS) minifloat.c minifloat_test_part3.c -o minifloat_test_part3.out

clean:
    rm -f *.out.stackdump
    rm -f *.out
    rm -f *.txt

.PHONY: all clean

C Programming

Much of the work in CS 3410 involves programming in C. This section of the site contains some overviews of most of the C features you will need in CS 3410.

For authoritative details on C and its standard library, the C reference on cppreference.com (despite the name) is a good place to look. For example, here’s a list of all the functions in the stdio.h header, and here’s the documentation specifically about the fputs function.

Compiling and Running C Code

Before you proceed with this page, follow the instructions to set up the course’s RISC-V infrastructure.

Your First C Program

Copy and paste this program into a text file called first.c:

#include <stdio.h> 

int main() {
    printf("Hello, CS 3410!\n");
    return 0;
}

Next, run this command:

$ rv gcc -o first first.c

Here are some things to keep in mind whenever these pages ask you to run a command:

• The $ is not part of the command. This is meant to evoke the command-line prompt in many shells, and it is there to indicate to you that the text that follows is a command that you should run. Do not include the $ when you type the command.
• Our course’s RISC-V infrastructure setup has you create an rv alias for running commands inside the infrastructure container. We will not always include an rv prefix on example commands we list in these pages. Whenever you need to run a tool that comes from the container, use the rv prefix or some other mechanism to make sure the command runs in the container.
• As with all shell commands, it really matters which directory you’re currently “standing in,” called the working directory. Here, first.c and first are both filenames that implicitly refer to files within the working directory. So before running this command, be sure to cd to the place where your first.c file exists.

If everything worked, you can now run this program with this command:

$ rv qemu first
Hello, CS 3410!

(Just type the rv qemu first part. The next line, without the $, is meant to show you what the command should print as output after you hit return.)

This command uses QEMU, an emulator for the RISC-V instruction set, to run the program we just compiled, which is in the file named first.

Recommended Options

While the simple command gcc -o first first.c works fine for this simple example, we officially recommend that you always use a few additional command-line options that make the GCC compiler more helpful. Here are the ones we recommend:

-Wall -Wextra -Wpedantic -Wshadow -Wformat=2 -std=c23

In other words, here’s our complete recommended command for compiling your C code:

$ rv gcc -Wall -Wextra -Wpedantic -Wshadow -Wformat=2 -std=c23 hi.c

Many assignments will include a Makefile that supplies these options for you.

Checking for Common C Errors

Memory-related bugs in C programs are extremely common! The worst thing about them is that they can cause obscure problems silently, without even crashing with a reasonable error message. Fortunately, GCC has built-in tools called sanitizers that can (much of the time, but not always) catch these bugs and give you reasonable error messages.

To use the sanitizers, add these flags to your compiler command:

-g -fsanitize=address -fsanitize=undefined

So here’s a complete compiler command with sanitizers enabled:

$ rv gcc -Wall -Wextra -Wpedantic -Wshadow -Wformat=2 -std=c23 -g -fsanitize=address -fsanitize=undefined hi.c

Then run the resulting program to check for errors.

We recommend trying the sanitizers whenever your code does something mysterious or unpredictable. It’s an unfortunate fact of life that, unlike many other languages, bugs in C code can silently cause weird behavior; sanitizers can help counteract this deeply frustrating problem.

C Basics

This section is an overview of the basic constructs in any C program.

Variable Declarations

C is a statically typed languages, so when you declare a variable, you must also declare its type.

int x; 
int y; 

Variable declarations contain the type (int in this example) and the variable name (x and y in this example). Like every statement in C, they end with a semicolon.

Assignment

Use = to assign new values to variables:

int x;
x = 4;

As a shorthand, you can also include the assignment in the same statement as the declaration:

int y = 6;

Expressions

An expression is a part of the code that evaluates to a value, like 10 or 7 * (4 + 2) or 3 - x. Expressions appear in many places, including on the right-hand side of an = in an assignment. Here are a few examples:

int x; 
x = 4 + 3 * 2;
int y = x - 6; 
x = x * y;

Functions

To define a function, you need to write these things, in order: the return type, the function name, the parameter list (each with a type and a name), and then the body. The syntax looks like this:

<return type> <name>(<parameter type> <parameter name>, ...) {
    <body>
}

Here’s an example:

int myfunc(int x, int y) {
  int z = x - 2 * y; 
  return z * x;
}

Function calls look like many other languages: you write the function name and then, in parentheses, the arguments. For example, you can call the function above using an expression like myfunc(10, 4).

The main Function

Complete programs must have a main function, which is the first one that will get called when the program starts up. main should always have a return type of int. It can optionally have arguments for command-line arguments (covered later).

Here’s a complete program:

int myfunc(int x, int y) {
  int z = x - 2 * y; 
  return z * x;
}

int main() {
  int z = myfunc(1, 2);
  return 0;
}

The return value for main is the program’s exit status. As a convention, an exit status of 0 means “success” and any nonzero number means some kind of exceptional condition. So, most of the time, use return 0 in your main.

Includes

To use functions declared somewhere else, including in the standard library, C uses include directives. They look like this:

#include <hello.h>
#include "goodbye.h"

In either form, we’re supplying the filename of a header file. Header files contain declarations for functions and variables that C programs can use. The standard filename extension for header files in C is .h. You should use the angle-bracket version for library headers and the quotation-mark version for header files you write yourself.

Printing

To print output to the console, use printf, a function from the C standard library which takes:

• A string to print out, which may include format specifiers (more on these in a moment).
• For each format specifier, a value to fill in for each format specifier.

The first string might have no format specifiers at all, in which case the printf only has a single argument. Here’s what that looks like:

#include <stdio.h>

int main() {
  printf("Hello, world!\n");
}

The \n part is an escape sequence that indicates a newline, i.e., it makes sure the next thing we output goes on the next line.

Format specifiers start with a % sign and include a few more characters describing how to print each additional argument. For example, %d prints a given argument as a decimal integer. Here’s an example:

#include <stdio.h> 

int main() {
  int x = 3; 
  int y = 4; 
  printf("x + y = %d.\n", x + y);
}

Here are some format specifiers for printing integers in different bases:

And here are some common format specifiers for other data types:

See the C reference for details on the full set of available format specifiers.

Basic Types in C

Some Common Data Types

A surprising quirk about C is that the sizes of some types can be different in different compilers and platforms! So this table lists common byte sizes for these types on popular platforms.

Characters

Every character is corresponds to a number. The mapping between characters and numbers is called the text encoding, and the ubiquitous one for basic characters in the English language is called ASCII. Here is a table with some of the most common characters in ASCII:

For all the characters in ASCII (and beyond), see this ASCII table.

Booleans

C does not have a bool data type available by default. Instead, you need to include the stdbool.h header:

#include <stdbool.h>

That lets you use the bool type and the true and false expressions. If you get an error like unknown type name 'bool', just add the include above to fix it.

Prototypes and Headers

Declare Before Use

In C, the order of declarations matters. This program with two functions works fine:

#include <stdio.h>

void greet(const char* name) {
  printf("Hello, %s!\n", name);
}

int main() {
  greet("Eva");
  return 0;
}

But what happens if you just reverse the two function definitions?

#include <stdio.h>

int main() {
  greet("Eva");
  return 0;
}

void greet(const char* name) {
  printf("Hello, %s!\n", name);
}

The compiler gives us this somewhat confusing error message:

error: implicit declaration of function 'greet'

The problem is that, in C, you have to declare every name before you can use it. So the declaration of greet has to come earlier in the file than the call to greet("Eva").

Declarations, a.k.a. Prototypes

This declare-before-use rule can make it awkward to define functions in the order you want, and it seems to be a big problem for mutual recursion. Fortunately, C has a mechanism to let you declare a name before you define what it means. All the functions we’ve seen so far have been definitions (a.k.a. implementations), because they include the body of the function. A function declaration (a.k.a. prototype) looks the same, except that we leave off the body and just write a semicolon instead:

void greet(const char* name);

A declaration like this tells the compiler the name and type of the function, and it amounts to a promise that you will later provide a complete definition.

Here’s a version of our program above that works and keeps the function definition order we want (main and then greet):

#include <stdio.h>

void greet(const char* name);

int main() {
  greet("Eva");
  return 0;
}

void greet(const char* name) {
  printf("Hello, %s!\n", name);
}

By including the declaration at the top of the file, we are now free to call greet even though the definition comes later.

Header Files

It is so common to need to declare a bunch of functions so you can call them later that C has an entire mechanism to facilitate this: header files. A header is a C source-code file that contains declarations that are meant to be included in other C files. You can then “copy and paste” the contents of header files into other C code using the #include directive.

Even though the C language makes no formal distinction between what you can do in headers and in other files, it is a universal convention that headers have the .h filename extension while “implementation” files use the .c extension. For example, we could put our greet declaration into a utils.h header file:

void greet(const char* name);

Then, we might put this in main.c:

#include <stdio.h>
#include "utils.h"

int main() {
  greet("Eva");
  return 0;
}

void greet(const char* name) {
  printf("Hello, %s!\n", name);
}

The line #include "utils.h" instructs the C preprocessor to look for the file called utils.h and paste its entire contents in at that location. Because the preprocessor runs before the compiler, this two-file version of our project looks exactly the same to the compiler as if we had merged the two files by hand. You can read more about #include directives, including about the distinction between angle brackets and quotation marks.

Multiple Source Files

Eventually, your C programs will grow large enough that it’s inconvenient to keep them in one .c file. You could distribute the contents across several files and then #include them, but there is a better way: we can compile source files separately and then link them.

To make this work in our example, we will have three files. First, our header file utils.h, as before, just contains a declaration:

void greet(const char* name);

Next, we’re write an accompanying implementation file, utils.c:

#include <stdio.h>
#include "utils.h"

void greet(const char* name) {
  printf("Hello, %s!\n", name);
}

As a convention, C programmers typically write their programs as pairs of files: a header and an implementation file, with the same base name and different extensions (.h and .c). The idea is that the header declares exactly the set of functions that the implementation file defines. So in that way, the header file acts as a short “table of contents” for what exists in the longer implementation file.

Let’s call the final file main.c:

#include "utils.h"

int main() {
  greet("Eva");
  return 0;
}

Notably, we use #include "utils.h" to “paste in” the declaration of greet, but we don’t have its definition here.

Now, it’s time to compile the two source files, utils.c and main.c. Here are the commands to do that:

$ gcc -c utils.c -o utils.o
$ gcc -c main.c -o main.o

(Remember to prefix these commands with rv to use our RISC-V infrastructure.)

The -c flag tells the C compiler to just compile the single source file into an object file, not an executable. An object file contains all code for a single C source program, but it is not directly runnable yet—for one thing, it might not have a main function. Using -o utils.o tells the compiler to put the output in a file called utils.o. As a convention, the filename extension for object files is .o.

You’ll notice that we only compiled the .c files, not the .h files. This is intentional: header files are only for #includeing into other files. Only the actual implementation files get compiled.

Finally, we need to combine the two object files into an executable. This step is called linking. Here’s how to do that:

$ gcc utils.o main.o -o greeting

We supply the compiler with two object files as input and tell it where to put the resulting executable with -o greeting. Now you can run the program:

$ ./greeting

(Use rv qemu greeting to use the course RISC-V infrastructure.)

Control Flow

Logical Operators

Here are some logical operators you can use in expressions:

false && expr2 will always evaluate to false, and true || expr2 will always evaluate to true, regardless of what expr2 evaluates to. This is called “short circuiting”: C evaluates the left-hand side of these expressions first and, if the truth value of that expression means that the other one doesn’t matter, it won’t evaluate the right-hand side at all.

Conditionals

Here is the syntax for if/else conditions:

if (condition) {
  // code to execute if condition is true
} else if (another_condition) {
  // code to execute if condition is false but another_condition is true
} else {
  // code to execute otherwise
}

The else if and else parts are optional.

Switch/Case

A switch statement can be a succinct alternative to a cascade of if/elses when you are checking several possibilities for one expression.

switch (expression) {
  case constant1:
    // code to execute if expression equals constant1
    break;
  case constant2:
    // code to execute if expression equals constant2
    break;
  // ...
  default:
    // code to be executed if expression doesn't match any case
}

While Loop

while (condition) {
  // code to execute as long as condition is true
}

For Loop

for (initialization; condition; increment) {
  // code to execute for each iteration
}

Roughly speaking, this for loop behaves the same way as this while equivalent:

initialization;
while (condition) {
  // code to execute for each iteration
  increment;
}

break and continue

To exit a loop early, use a break; statement. A break statement jumps out of the innermost enclosing loop or switch statement. If the break statement is inside nested contexts, then it exits only the most immediately enclosing one.

To skip the rest of a single iteration of a loop, but not cancel the loop entirely, use continue.

Declaring Your Own Types in C

Structures

The struct keyword lets you declare a type that bundles together several values, possibly of different types. To access the fields inside a struct variable, use dot syntax, like thing.field. Here’s an example:

struct rect_t {
  int left;
  int bottom;
  int right;
  int top;
};

int main() {
  struct rect_t myRect;
  myRect.left = -4;
  myRect.bottom = 1;
  myRect.right = 8;
  myRect.top = 6;

  printf("Bottom left = (%d,%d)\n", myRect.left, myRect.bottom);
  printf("Top right = (%d,%d)\n", myRect.right, myRect.top);

  return 0;
}

This program declares a type struct rect_t and then uses a variable myRect of that type.

Enumerations

The enum keyword declares a type that can be one of several options. Here’s an example:

enum threat_level_t {
  LOW,
  GUARDED,
  ELEVATED,
  HIGH,
  SEVERE
};

void printOneLevel(enum threat_level_t threat) {
  switch (threat) {
    case LOW:
      printf("Green/Low.\n");
      break;
    // ...omitted for brevity...
    case SEVERE:
      printf("Red/Severe.\n");
      break;
  }
}

void printLevels() {
  printf("Threat levels are:\n");
  for (int i = LOW; i <= SEVERE; i++) {
    printOneLevel(i);
  }
}

This code declares a type enum threat_level_t that can be one of 5 values.

Type Aliases

You can use the typedef keyword to give new names to existing types. Use typedef <old type> <new name>;, like this:

typedef int whole_number;

Now, you can use whole_number to mean the same thing as int.

Short Names for Structs and Enums

You may have noticed that struct and enum declarations make types that are kind of long and hard to type. For example, we declared a type enum threat_level_t. Wouldn’t it be nice if this type could just be called threat_level_t?

typedef is also useful for defining these short names. You could do this:

enum _threat_level_t { ... }
typedef enum _threat_level_t threat_level_t;

And that does work! But there’s also a shorter way to do it, by combining the enum and the typedef together:

typedef enum {
  ...
} threat_level_t;

That defines an anonymous enumeration and then immediately gives it a sensible name with typedef.

Below is a helpful table which summarizes the different ways that you can declare and initialize a struct (or an enum).

struct rect_t {
  int left;
  int bottom;
  int right;
  int top;
};

struct rect_t myRect;
myRect.left = 1;
...

struct _rect_t {
  int left;
  int bottom;
  int right;
  int top;
};
typedef struct _rect_t rect_t;

struct _rect_t myRect;
myRect.left = 1;
...

rect_t myRect;
myRect.left = 1;
...

typedef struct _rect_t {
  int left;
  int bottom;
  int right;
  int top;
} rect_t;

struct _rect_t myRect;
myRect.left = 1;
...

rect_t myRect;
myRect.left = 1;
...

typedef struct {
  int left;
  int bottom;
  int right;
  int top;
} rect_t;

rect_t myRect;
myRect.left = 1;
...

Bit Packing

Structs work well when you want to combine several types that have “nice” sizes: 1, 4, or 8 bytes, for example. But they can waste space if you actually only need a few bits for your values. For example, we learned that the float type is 32 bits: 1 sign bit, 8 exponent bits, and 23 significand bits. If we wanted to “fake” a floating-point number with a struct, we couldn’t use a 1-bit and 23-bit type. The best we can do is to use 8 bits, 8 bits, and 32 bits:

#include <stdio.h>
#include <stdint.h>

typedef struct {
    uint8_t sign;
    uint8_t exponent;
    uint32_t significand;
} fake_float_t;

int main() {
    printf("size: %lu\n", sizeof(fake_float_t));
}

That struct uses a total of 6 bytes for its fields. But compilers often need to insert padding to make sure values are aligned for efficient memory access, so the struct can be bigger than that. Here, we use sizeof to measure the actual total size of the struct, which is 8 bytes—twice as big as a real 4-byte float!

This section will show you how to pack these irregularly-sized values into integers—a trick that you can call bit packing. The big idea is to treat integer types like uint32_t just as sequences of bits rather than as actual integers, and to use C’s built-in bit-manipulation operations to insert and extract ranges of bits. The key operations are:

• Masking, with the bitwise “and” operator, &.
• Combining, with the bitwise “or” operator, |.
• Shifting, with the bitwise shift operators >> and <<.

You may find it helpful to look over the full list of arithmetic and bit manipulation operators in C.

Shifting

In C, i << n shifts the bits in an integer i leftward by n places, filling in the bottom n bits with zeroes. Mathematically, this has the effect of multiplying i by $2^n$:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t n = 21;
    printf("double n: %u\n", n << 1);
}

Similarly, i >> n shifts the bits rightward by n places, so it multiplies i by $2^{-n}$.

These shift operations are useful for moving bit patterns around within the range of bits in the value. Let’s try moving a value around in a uint32_t and printing out the bits:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t n = 21;
    printf("%032b\n", n);
    printf("%032b\n", n << 8);
    printf("%032b\n", n << 16);
    printf("%032b\n", n << 24);
}

That %032b specifier tells printf to pad the value out to 32 bits for consistency. If you run this program, you can see the bit-pattern for the value 21 moving around within the range of 32 bits:

00000000000000000000000000010101
00000000000000000001010100000000
00000000000101010000000000000000
00010101000000000000000000000000

Combining

The bitwise “or” operator, written in C with a single |, is useful for combining different values that have been shifted to different places. The insight is that x | 0 == x for any bit x, and our shifted values have zeroes wherever they are “inactive.” Let’s try shifting two different small values to two different positions and then combining them:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t x = 21;
    uint32_t y = 17;
    printf("x:      %032b\n", x);
    printf("y<<8:   %032b\n", y << 8);
    printf("x|y<<8: %032b\n", x | (y << 8));
}

If you run this program, you can see the bit patterns for 21 and 17 coexisting happily, side-by-side. Because we know these values fit in 8 bits, we can think of the first value occupying bits 0 through 7 (numbered from the least significant bit) and the next one occupying bits 8 through 15 in the combined value.

Masking

Next, we want a way to extract bits out of one of these combined values. The idea is to use the bitwise “and” operator, &, together with a mask value that has ones exactly where the bits are that we’re interested in. We’ll use this property of the & operator:

• Wherever mask is 1, mask & x == x for any bit x.
• Wherever mask is 0, mask & x == 0 for any bit 0.

So a mask value has the effect of preserving values from x where it’s 1 and ignoring them (turning them into to 0) where it’s 0.

Let’s construct a mask to separate the two packed values from last time:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t x = 21;
    uint32_t y = 17;
    uint32_t comb = x | (y << 8);
    printf("comb:        %032b\n", comb);

    uint32_t x_mask = 0b00000000000000000000000011111111;
    uint32_t y_mask = 0b00000000000000001111111100000000;

    printf("comb&x_mask: %032b\n", comb & x_mask);
    printf("comb&y_mask: %032b\n", comb & y_mask);
}

Running this program will show how we’ve “separated” the combined value back into its constituent parts.

When writing masks, it can get really tiresome to write all those ones and zeroes out. It’s often more practical to write them as hexadecimal literals, remembering that every hex digit corresponds to 4 bits (a nibble): hex 0 is binary 0000, and hex F is binary 1111. So this program is equivalent:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint32_t x = 21;
    uint32_t y = 17;
    uint32_t comb = x | (y << 8);
    printf("comb:        %032b\n", comb);

    uint32_t x_mask = 0x000000FF;
    uint32_t y_mask = 0x0000FF00;

    printf("comb&x_mask: %032b\n", comb & x_mask);
    printf("comb&y_mask: %032b\n", comb & y_mask);
}

Putting it All Together

Now that we’ve separated the two values out by masking the combined value, there is one more step to recover the original values. We just need to shift them right with >> back to their original positions. Actually, x is already in its original position, so we don’t have to do anything to it. But y was shifted left by 8 bits originally, so to get its original value, we’ll shift the masked-out value right again by the same amount.

Here’s a complete program that shows the combination and extraction together:

#include <stdio.h>
#include <stdint.h>

uint32_t pack(uint8_t x, uint8_t y) {
    return x | (y << 8);
}

uint8_t get_x(uint32_t comb) {
    return comb & 0x000000FF;
}

uint8_t get_y(uint32_t comb) {
    return (comb & 0x0000FF00) >> 8;
}

int main() {
    uint32_t comb = pack(34, 10);
    printf("recovered x: %hhd\n", get_x(comb));
    printf("recovered y: %hhd\n", get_y(comb));
}

The pack function combines x and y into a single uint32_t. Then, the get_x and get_y functions use masking and shifting to undo this combination and extract the original values.

Bit packing is a superpower that you have unlocked by understanding how values are represented at the level of bits. Use it to save space when ordinary structs won’t cut it!

Pointers!

Pointers are central to programming in C, yet are often one of the most foreign concepts to new C coders.

A Motivating Example

Suppose we want to write a swap function that will take two integers and swap their values. With the programming tools we have so far, our function might look something like this:

void swap(int a, int b) {
  int temp = a;
  a = b;
  b = temp;
}

This won’t work how we want it to! If we call swap(foo, bar), the swap function gets copies of the values in foo and bar. Reassigning a and b just affects those copies—not foo and bar themselves! (This behavior is called call by value (or pass by value) as the values of the variables are passed as function arguments, not references.)

How can we give swap direct access to the places where the arguments are stored so it can actually swap them? Pointers are the answer.

Declaring a Pointer

For any type T, the type of a pointer to a value of that type is T*: that is, the same type with a star after it. For example, this code:

char* my_char_pointer;

(pronounced “char star my char pointer”) declares a variable with the name my_char_pointer. This variable is not a char itself! Instead, it is a pointer to a char.

Confusingly, the spaces don’t matter. The following three lines of code are all equivalent declarations of a pointer to an integer:

int* ptr;
int *ptr;
int * ptr;

ptr has the type “pointer to an integer.”

Initializing a Pointer

int* ptr = NULL;

The line above initializes the pointer to NULL, or zero. It means the pointer does not point to anything. This is a good idea if you don’t plan on having it point to something just yet. Initializing to NULL helps you avoid “dangling” pointers which can point to random memory locations that you wouldn’t want to access unintentionally. C will not do this for you.

You can check if a pointer is NULL with the expression ptr == NULL.

Assigning to a Pointer, and Getting Addresses

In the case of a pointer, changing its value means changing where it points. For example:

void func(int* x) {
  int* y = x;
  // ...

The assignment in that code makes y and x point to the same place.

But what if you want to point to a variable that already exists? C has an & operator, called the “address-of” (or “reference-of”) operator, that gets the pointer to a variable. For example:

int x = 5;
int* xPtr = &x;

Here, xPtr now points to x.

You can’t assign to the address of things; you can only use & in expressions (e.g., on the right-hand side of an assignment). So:

y = &x;  // this is fine
&x = y;  // will not compile!

This rule reflects the fact that you can get the location of any variable, but it is never possible to change the location of a variable.

Dereferencing Pointers

Once you have a pointer with a memory location in it, you will want to access the value that is being pointed at—either reading or changing the value in the box at the end of the arrow. For this, C has the * operator, known as the “dereference” operator because it follows a reference (pointer) and gives you the referred-to value.

You can both read from and write to a dereferenced pointer, so * expressions can appear on either side of an assignment. For example:

int number = *xPtr;  // read the value xPtr points to
printf("the number is %d\n", *xPtr);  // read it and then print it
*xPtr = 6;  // write the value that xPtr points to

Common Confusion with the * Operator

Do not be confused by the two contexts in which you will see the star (*) symbol:

• Declaring a pointer: int* p;
• Dereferencing a pointer (RHS): r = *p;
• Dereferencing a pointer (LHS): *p = r;

The star is part of the type name when declaring a pointer and is the dereference operator when used in assignments.

Swap with Pointers

Now that we have pointers, we can correctly write that swap function we wanted! The new version of swap uses a “pass by reference” model in which pointers to arguments are passed to the function.

void swap(int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

The Arrow Operator

Recall that we used the “dot” operator to access elements within a struct, like myRect.left. If you instead have a pointer to a struct, you need to dereference it first before you can access its fields, like (*myRect).left.

Fortunately, C has a shorthand for this case! You can also write myRect->left to mean the same thing. In other words, the -> operator works like the . operator except that it also dereferences the pointer on the left-hand side.

Pointer Arithmetic

If pointers are just addresses in memory, and addresses are just integers, you might wonder if you can do arithmetic on them like you can with ints. Yes, you can!

Adding n to a pointer to any type T causes the pointer to point n Ts further in memory. For example, the expression ptr + offset might compute a pointer that is “four ints later in memory” or “six chars later in memory.”

int x = 5;
int *ptr = ...;

x = x + 1;
ptr = ptr + 1;

In this code:

• x + 1: adds 1 to to the integer x, producing 6
• ptr + 1: adds the size of an int in bytes to ptr, shifting to point to the next integer in memory

Printing Pointers

You can print the address of a pointer to see what memory location it is pointing to. For example:

printf("Pointer address: %p\n", (void*)ptr);

This will output the memory address the pointer ptr is currently holding.

Arrays

An array is a sequence of same-type values that are consecutive in memory.

Declaring an Array

To declare an array, specify its type and size (i.e., the number of items in the sequence). For example, an array of four integers can be declared as follows:

int myArray[4];

A few variations on this declaration are:

int myArray[4] = {42, 45, 65, -5}; // initializes the values in the array
int myArray[4] = {0};              // initializes all the values in the array to 0
int myArray[] = {42, 45, 65, -5};  // initializes the values in the array, compiler intuits the array size

Accessing an Array

To refer to an element, specify the array name (e.g., my_array) and the position number (e.g., 0):

// Declare an array of five `int`s called `my_array`.
int my_array[5];
// Store the integer `8` at position `0` in array `my_array`.
my_array[0] = 8;
printf("I just initialized the element at index 0 to %d!\n", my_array[0]);

After executing the above code, my_array would look like this in memory (where larger addresses are higher on the screen):

Ex: Compute the sum an array

To sum the elements of an array, we can use a for loop to iterate over the array’s indices, adding the elements together as we go:

int sum_array(int *array, int n) {
  int sum = 0;
  for (int i = 0; i < n; ++i) {
    answer += array[i];
  }
  return sum;
}

int main() {
  int data[4] = {4, 6, 3, 8};
  int sum = sum_array(data, 4);
  printf("sum: %d\n", sum);
  return 0;
}

Accessing an Array using Pointer Arithmetic

In C, you can treat arrays as pointers: namely, to the first element in the sequence.

This means that, perhaps surprisingly, the syntax array[i] is shorthand for *(array + i): that is, a combination of pointer arithmetic and dereferencing. So you can think of array[i] as treating array as a pointer to the first element, then shifting the pointer over by i slots, and then dereferencing the pointer to that shifted location.

Passing Arrays as Parameters

You can also treat arrays as pointers when you pass them into functions. You already saw this above; we declared a function this way:

int sum_array(int *array, int n) { ... }

and then called it like sum_array(data, 4). Even though we declared data as an array, C lets you treat it as a pointer to the first element.

Common Pitfalls

• C has no array-bound checks. You won’t even get a warning! If you write past the end of an array, you will simply start overwriting the values of other data in memory.
• sizeof(array) will return a different value based on how the variable array was declared. If array is declared as int *array, then array will be considered the size of a pointer. If it was declared as int array[100] then it will be considered the size of 100 ints.

Multidimensional Arrays

C lets you declare multidimensional arrays, like int matrix[4][3]. However, it still lays everything out sequentially in memory. Here’s a visualization of what that matrix looks like conceptually and in memory:

This array occupies (4 * 3 * sizeof(double)) bytes of memory.

Strings

A string is an array of characters (chars), terminated by the null terminator character, '\0'. In general, the type of a string in C is char*.

String Literals

We have seen string literals so far—a sequence of characters written down in quotation marks, such as "Hello World\n".

The type of a string literal is const char*, so this is valid C:

const char* str = "Hello World\n";

The const shows up here because the characters in a string literal cannot be modified.

Mutable Strings

A mutable string has type char*, without the const. How can you declare a mutable string with a string literal, if string literals are always const? Here’s a trick you can use: remember that, in C, an array is like a pointer to its first element. So let’s declare the string as an array and give it an initializer:

char str[] = "Hello World\n";

This code behaves exactly as if we wrote:

char str[] = {'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd', '\n', '\0'};

It declares a variable str which is an array of 13 characters (remember that the size of an array may be implicit if we provide an initializer from which the compiler can determine the size), and initializes it by copying the characters of the string "Hello World\n" (including the null terminator) into that array.

String Equality

The expression str1 == str2 doesn’t check whether str1 and str2 are the same string! Remember, since both of these have a pointer type (char*), C will just compare the pointers.

Instead, if you want to check whether two strings contain equal contents, you will need to use a function like strcmp from the string.h header.

String Copying

Similarly, an assignment like str1 = str2; does not copy strings! It just just does pointer assignment, so now str1 points to the same region of memory as str2.

Use a function like strcpy if you need to copy characters.

C Macros

Let’s say you have a program that works with arrays of a certain size: say, 100 elements. The number 100 will show up in different parts of the code:

float stuff[100];

// ... elsewhere ...

for (int i = 0; i < 100; ++i) {
  do_something(stuff[i]);
}

Repeating the number 100 in multiple locations is not great for multiple reasons:

• It is not maintainable. If you ever need to change the size of the array, you need to carefully look for all the places where you mentioned 100 and change it to something else. If you happen to miss one, subtle bugs will arise.
• It is not readable. Writing code is as much about communicating with other programmers as it is about communicating with the machine! When a human sees the number 100 appear out of nowhere, it can be mysterious and worrisome. For this reason, programmers often call these arbitrary-seeming constants magic numbers (in a derogatory way).

C has a feature called the preprocessor that can cut down on duplication, eliminate magic numbers, and make code more readable. In particular, you can use a macro definition to give your constant a name:

#define NUMBER_OF_THINGS 100

The syntax #define <macro> <expression> defines a new name, the macro, and instructs the preprocessor to replace that name with the given expression. (Notably, there is no semicolon after preprocessor directives like #define.) It is a convention to always use SHOUTY_SNAKE_CASE for macro names to help visually distinguish them from ordinary C variable names.

In this example, the C preprocessor will “find and replace” all occurrences of NUMBER_OF_THINGS in our program and replace it with the expression 100. So it means exactly the same thing to rewrite our program above like this:

#define NUMBER_OF_THINGS 100

float stuff[NUMBER_OF_THINGS];

// ... elsewhere ...

for (int i = 0; i < NUMBER_OF_THINGS; ++i) {
  do_something(stuff[i]);
}

The C preprocessor runs before the actual compiler, so you can think of it as doing a textual “find and replace” operation before compiling your code.

Dynamic Memory Allocation

Motivation

Suppose we wanted to write a function that takes an integer, creates an array of the size specified by the integer, initializes each field, and returns the array back to the caller. Given the tools we have thus far, our code might look like this:

// Broken code! Do not do this!
int *initArray(int howLarge) {
  int myArray[howLarge];
  for (int i = 0; i < howLarge; i++) {
    myArray[i] = i;
  }
  return myArray;
}

The reason this code will not work is that the array is created on the stack. Variables on the stack exist only until the function ends, at which point the stack frame is popped. You can’t use the memory for that stack frame anymore, and it will get reused for some other data.

Dynamic memory allocation lets you obtain memory on the heap instead of the stack. Unlike stack frames, the heap is forever: it remains even when the function returns. Instead, you have to remember to explicitly free the memory when you are done using it.

Both the stack and the heap can grow and shrink over time, as the program creates and destroys stack frames and heap-allocated memory regions. Typically, systems lay out the stack at higher addresses in memory and the heap at lower addresses in memory; as they grow, the stack grows “down” and the heap grows “up.” Here’s a diagram that depicts this growth in the address space:

The diagram also includes static data (globals and constants) and code, which are other memory regions distinct from the heap and stack.

malloc

To use dynamic memory allocation functions, #include <stdlib.h>. Check out the reference for the stdlib.h header.

To allocate memory on the heap, use the malloc function. Here’s its declaration:

void* malloc(size_t size);

The return type of malloc is void*, which looks a little weird, but it means “a pointer to some type but I’m not sure which.” The only argument is a size: the number of bytes you want to allocate. (size_t is an unsigned integer type.)

How do you know how many bytes you need? The best way is to use C’s sizeof operator. Use sizeof(int), for example, to get the number of bytes that an int occupies. For example, here’s how to allocate space for an int on the heap:

int* intPtr = malloc(sizeof(int));

If you want to get fancy, you can even avoid repeating the int type by using sizeof’s ability to get the type of a variable for you:

int* intPtr = malloc(sizeof(*intPtr));

And here’s how to allocate space for an array of 500 floats:

float* floatArray = malloc(500 * sizeof(*floatArray));

(Please use sizeof instead of guessing the sizes of things, even if you think you know that an int occupies 4 bytes. Because types can be different sizes on different platforms, using sizeof will make your code portable.)

free

Unlike stack variables, you are responsible for freeing memory that you malloc! You do that with the free function. free just takes one argument: the pointer to some memory previously allocated with malloc.

Remember this rule: every time you call malloc, remember to put a free somewhere to balance it out.

initArray Revisited

Here’s a fixed version of the code above:

int *initArray(int howLarge) {
  int *array = malloc(howLarge * sizeof(*array));
  if (array != NULL) {
    for (int i = 0; i < howLarge; i++) {
      array[i] = i;
    }
  }
  return array;
}

Of course, the caller of initArray will need to call free when it is finished with the memory.

Notice how the above code checks whether malloc returns NULL. It is possible that the heap could run out of space and that there is not enough memory to fulfill the current request. In such cases, malloc will return NULL instead of a valid pointer to a location on the heap. It is a good idea to check the value returned by malloc and make sure that it is not NULL before trying to use the pointer. If the value is NULL, the program should gracefully abort with an error message explaining that a call to malloc failed (or if it can recover from the situation and continue—that is even better).

realloc

The realloc function can reallocate a block of memory at a different size. In general, realloc might allocate a new (larger or smaller) block of memory, copy the contents of the original to the new one, and free the old one. (But it might do something faster if it can avoid it, e.g., if there is room to expand the allocated region “in place.”)

RISC-V Assembly Resources

CS 3410 uses the 64-bit RISC-V (pronounced risk-five) instruction set architecture (ISA). RISC-V is a modern reduced instruction set computer (RISC) architecture. RISC-V is unique because it’s an open instruction set that anyone can implement without any kind of licensing. (That’s in contrast to the two most popular ISAs, Arm and x86, which both require expensive licenses to implement in hardware.)

Here are some references you might find helpful when writing and reading RISC-V assembly code.

Reference Materials

• This short reference sheet contains instruction encodings for RISC-V 32, RISC-V 64, and beyond.
• For the definitive description of what every instruction does and how it’s encoded, see the official ISA manual. It’s long, though, and can get a little bit technical.

Online Tools

• Cornell’s new experimental RISC-V interpreter supports 64-bit RISC-V, and replaces the previous 32-bit interpreter. Note that the old interpreter, which is now deprecated, was designed for the 32-bit ISA, while the new version more closely aligns with the 64-bit ISA taught in class.
• Venus is a powerful interactive RISC-V simulator. It is more complicated to use, but it supports more RISC-V instructions.

Introduction

Syllabus and Setup

Please carefully read over the syllabus. Seriously! There is a lot in there that you will want to know.

CS 3410 has made some significant changes compared to prior years. We have updated the curriculum to focus on the essential topics we believe are critical to anyone studying computer science. Among many other changes, this means that there is more focus on programming in C and assembly, we regretfully needed to sacrifice all the digital-design assignments that used the Logisim for visual circuit design, and there is much more of an emphasis on parallelism (because, in the modern era, all computers are parallel).

There are two things you need to do this week:

• An introductory survey on Gradescope. This is due on Friday.
• Set up the RISC-V infrastructure that you will need for all assignments. Please do your best to do this before your first lab section. However, we will do it during this weeks lab session. Further, if you need help, please post on Ed or find a TA in office hours.

This week’s lab is setting up the infrastructure, this is lab 0! Once your infrastructure is setup, the assignment is printf. The printf assignment serves as an introduction to the C programming language and lets you exercise your skills with numerical representation, binary, and other bases.

As with every assignment in this class, the lab is there to help you get started on the assignment. The lab instructors will help guide you through “step 0” for the printf assignment; then, the rest is up to you.

Course Overview

CS 3410 is about how computers actually work. That puts it in contrast to other kinds of courses that at other “levels” in the computer science stack:

• Classes like CS 1110, CS 2110, and CS 3110 are all about how to make computers do things. You used programming languages (Python, Java, and OCaml) to write programs without worrying to much about how those languages actually do what they do.
• Classes on application topics like robotics, machine learning, and graphics are all about things computers can do. These are important, of course, because they are the reason we study computing in the first place.
• Outside of CS, and below the 3410 “level,” there are many classes at Cornell on topics like electronics, chemistry, and physics that can tell you physical details of how computers work. That’s not what 3410 is about either: we will build abstractions over those physical phenomena to understand how computers work in the realm of logic.

Switches

The fundamental computational building block in the physical world is a switch. What we mean by a “switch” is: something that controls a physical phenomenon that you can abstractly think of as being in an “on” or “off” state. Some examples of switches include:

• A valve controls hydraulic states, i.e., whether water is flowing or not.
• A vacuum tube controls an electronic signal.
• The game Turing Tumble controls signals in the form of marbles. Yes, you can build real computers out of little plastic levers.

What you think of as a “real” computer controls electronic signals. Aside from vacuum tubes, a particularly easy-to-understand type of electronic switch is a relay. To make a relay, you need:

• An electromagnet (i.e., a magnet controlled by an electronic signal).
• A bendy piece of metal that can be attracted or repelled by that magnet.
• Another piece of metal next to that one. You position it carefully so there’s a tiny gap between the two pieces of metal. When the electromagnet is on, it either closes or opens that gap (depending on whether it attracts or repels the bendy piece of metal).
• Wires hooked up to the two pieces of metal. This way, you can think of the relay as a wire that is either connected or disconnected, depending on whether the electromagnet is charged.

The point is that a relay is a switch that both controls an electronic signal and is controlled by an electronic signal. That’s a really powerful idea, because it means you can wire up a whole bunch of relays to make them control each other! And that is basically what you need to build a computer.

Transistors

Computers today are universally built out of transistors. Transistors work like relays, in the sense that they let one electronic signal control another one. The difference is that they are solid-state devices, relying on the chemistry of the materials inside of them to do the current control instead of a physically moving bendy piece of metal. But abstractly, they do exactly the same thing.

The first transistor was built in Bell Labs in 1947. These days, you can buy them on Amazon for a few pennies apiece. You can build computers “from scratch” by buying a bunch of transistors on Amazon and wiring them up carefully.

Modern computers consist of billions of transistors, manufactured together in an integrated circuit. For example, Apple’s M4 is made up of 28 billion transistors. There is an entire industry of silicon manufacturing that is dedicated to building chunks of silicon and with many, many tiny transistors and wires on them.

Abstractly speaking, however, these integrated circuits are no different from a bunch of transistors you can buy on Amazon, wired up very carefully. Which are in turn (abstractly!) the same as relays, or valves, or Turing Tumble marble levers: they are all just a bunch of switches that control each other in careful ways.

One Plus One

Bits

Because computers are made of switches, data is made of bits. A bit is an abstraction of a physical phenomenon that can either be “on” or “off.” The mapping between the physical phenomenon and the 0 or 1 digit is arbitrary; this is just something that humans have to make up. For example

• In a hydraulic computer, maybe 0 is “no water” and 1 is “water is flowing.”
• In Turing Tumble, perhaps 0 is “marble goes left” and 1 is “marble goes right.”
• In an electronic computer, let’s use 0 to to mean “low voltage” and 1 to mean “high voltage.”

Binary Numbers

Armed with switches and a logical mapping, computers have a way to represent numbers! Just really small numbers: a bit suffices to represent all the integers in interval [0, 1]. It would be nice to be able to represent numbers bigger than 1.

We do that by combining multiple bits together and counting in binary, a.k.a. “base 2.”

In elementary school math class, you probably learned about “place values.” The rightmost digit in a decimal number is for the ones, the next one is for tens, and the next one is for hundreds. In other words, if you want to know what the string of decimal digits “631” means, you can multiply each digit by its place value and add the results together:

$$631_{10} = 1 \times 10^0 + 3 \times 10^1 + 6 \times 10^2$$

We’ll sometimes use subscripts, like $n_{b}$, to be explicit when we are writing a number in base $b$.

That’s the decimal, a.k.a. “base 10,” system for numerical notation. Base 2 works the same way, except all the place values are powers of 2 instead of powers of 10. So if you want to know what the string of binary digits “101” represents, we can do the same multiply-and-add dance:

$$101_2 = 1 \times 2^0 + 0 \times 2^1 + 1 \times 2^2$$

That’s five, so we might write $101_2 = 5_{10}$.

Some Important Bases

We won’t be dealing with too many different bases in this class. In computer systems, only three bases are really important:

• Binary (base 2).
• Octal (base 8).
• Hexadecimal (base 16), affectionately known as hex for short.

Octal works exactly as you might expect, i.e., we use the digits 0 through 7. For hexadecimal, we run out of normal human digits at 9 and need to invent 6 more digits. The universal convention is to use letters: so A has value 10 (in decimal), B has value 11, and F has value 15.

Converting Between Bases

Here are two strategies for converting numbers between different bases. In both algorithms, it can be helpful to write out the place values for the base you’re converting to. We’ll convert the decimal number 637 to octal as an example. In octal, the first few place values are 1, 8, 64, and 512.

Left to Right

First, compute the first digit (the most significant digit) finding the biggest place value you can that is less than that number. Then, find the largest number you can multiply by that place value. That’s your converted digit. Take that product (the place value times that largest number) and subtract it from your value. Now you have a residual value; start from the beginning of these instructions and repeat to get the rest of the digits.

Let’s try it by converting 637 to octal.

• The biggest place value under 636 is 512. $512 \times 2$ doesn’t stay “under the limit,” so we have to settle for $512 \times 1$. That means the first digit of the converted number is 1. The residual value is $637 - 512 \times 1 = 125$.
• The value that “fits under” 125 is $64 \times 1$. So the second digit is also 1. The residual value is $125 - 64 \times 1 = 61$.
• We’re now at the second-to-least-significant digit, with place value 8. The largest multiple that “fits under” 61 is $8 \times 7$, so the next digit is 7 and the residual value is $61 - 8 \times 7 = 5$.
• This is the ones place, so the final digit is 5.

So the converted value is $1175_8$.

Right to Left

First, compute the least significant digit by dividing the number by the base, $b$. Get both the quotient and remainder. The remainder is the number of ones you have, so that’s your least significant digit. The quotient is the number of $b$s you have, so that’s the residual value that we will continue with.

Next, repeat with that residual value. Remember, you can think of that as the number of $b$s that remain. So when we divide by $b$, the remainder is the number of $b$s and the quotient is the number of $b^2$s. So the remainder is the second-to-least-significant digit, and we can continue around the loop with the quotient. Stop the loop when the residual value becomes zero.

Let’s try it again with 637.

• $637 \div 8 = 79$ with remainder 5. So the least significant digit is 5.
• $79 \div 8 = 9$ with remainder 7. So the next-rightmost digit is 7.
• $9 \div 8 = 1$ with remainder 1. The next digit is 1.
• $1 \div 8 = 0$ with remainder 1. So the final, most significant digit is 1.

Fortunately, this method gave the same answer: $1175_8$.

Programming Language Notation

When writing, we often use the notation $1175_8$ to be explicit that we’re writing a number in base 8 (octal). Subscripts are hard to type in programming languages, so they use a different convention.

In many popular programming languages (at least Java, Python, and the language we will use in 3410: C), you can write:

• 0b10110 to use binary notation.
• 0x123abc to use hexadecimal notation.

Octal literals are a little less standardized, but in Python, you can use 0o123 (with a little letter “o”).

Addition

To add binary numbers, you can use the elementary-school algorithm for “long addition,” with carrying the one and all that. Just remember that, in binary, 1+1 = 10 and 1+1+1 (i.e., with a carried one) is 11.

Numbers

Addition

To add binary numbers, you can use the elementary-school algorithm for “long addition,” with carrying the one and all that. Just remember that, in binary, 1+1 = 10 and 1+1+1 (i.e., with a carried one) is 11.

Signed Numbers

This is all well and good for representing nonnegative numbers, but what if you want to represent $-10110$? Remember, everything must be a bit, so we can’t use the $-$ sign in our digital representation of negative numbers.

There is an “obvious” way that turns out to be problematic, and a less intuitive way that works out better from a mathematical and hardware perspective. The latter is what modern computers actually use.

Sign–Magnitude

The “obvious” way is sign–magnitude notation. The idea is to reserve the leftmost (most significant) bit for the sign: 0 means positive, 1 means negative.

For example, recall that $7_{10} = 111_{2}$. In a 4-bit sign–magnitude representation, we would represent positive $7$ as 0111 and $-7$ as 1111.

Sign–magnitude was used in some of the earliest electronic computers. However, it has some downsides that mean that it is no longer a common way to represent integers:

• It leads to more complicated circuits to implement fundamental operations like addition and subtraction. (We won’t go into why—you’ll have to trust us on this.)
• Annoyingly, it has two different zeros! There is as “positive zero” (0000 in 4 bits) and a “negative zero” (1000). That just kinda feels bad; there should only be one zero, and it should be neither positive nor negative.

Two’s Complement

The modern way is two’s complement notation. In two’s complement, there is still a sign bit, and it is still the leftmost (most significant) bit in the representation. 1 in the sign bit still means negative, and 0 means positive or zero.

For the positive numbers, things work like normal. In a 4-bit representation, 0001 means 1, 0010 means 2, 0011 means 3, and so on up to 0111, which means positive 7.

The key difference is that, in two’s complement, the negative numbers grow “up from the bottom.” (In the same sense that they grow “down from zero” in sign–magnitude.) That means that 1000 (and in general, “one followed by all zeroes”) is the most negative number: with 4 bits, that’s $-8$. Then count upward from there: so 1001 is $-7$, 1010 is $-6$, and so on up to 1111, which is $-1$.

Here’s another way to think about two’s complement: start with a normal, unsigned representation and negate the place value of the most significant bit. In other words: in an unsigned representation, the MSB has place value $2^{n-1}$. In a two’s complement representation, all the other place values remain the same, but the MSB has place value $-2^{n-1}$ instead.

Here are some cool facts about two’s complement numbers, when using $n$ bits:

• The all-zeroes bit string always represents 0.
• The all-ones bit string always represents $-1$.
• The biggest positive value, sometimes known as INT_MAX, is 0 followed by all ones. Its value is $2^{n-1}-1$.
• The biggest negative value, sometimes known s INT_MIN, is 1 followed by all zeroes. Its value is $-2^{n-1}$.
• Addition works the same as for normal, unsigned binary numbers. You can just ignore the fact that one of the bits is a sign bits, add the two numbers as if they were plain binary values, and you get the right answer in a two’s complement representation!
• To negate a number i, you can compute ~i + 1, where ~ means “flip all the bits, so every zero becomes one and every one becomes zero.”

Two’s Complement Example

Let’s use a six-bit two’s complement representation. What numbers (in standard decimal notation) do these bit patterns represent?

• 011000
• 111111
• 111011

The answers are:

• $24$. For positive numbers (where the sign bit is 0), you don’t have to think much about two’s complement; just read the remaining bits as a normal binary number.
• $-1$. Remember the tip from last time: the all-ones bit pattern is always $-1$.
• $-5$. There are many ways to get here. One option is to notice that this number is exactly $100_2$ less than the all-ones bit pattern, so it’s $-1 - 4$.

Introduction to C

Hello, C!

Much of the work for CS 3410 will consist of programming in C. If you have mainly programmed in the other Cornell-endorsed languages (Python, Java, and OCaml), the main difference you’ll notice in C is that it operates at a much lower level of abstraction. It gives you a far greater level of control over exactly what the computer does.

While this kind of low-level control is undeniably inconvenient and verbose, it has some extremely important advantages. The most common reasons to use a low-level language like C are:

• Performance. Higher-level languages trade off convenience for speed. Often, programming in a low-level language is the only way to get the kind of efficiency you need.
• Interactions with hardware. When you’re writing an operating system, a device driver, or anything else that interacts with hardware directly, you really need a low-level language.

There are other low-level languages that have the same advantages, such as C++ and Rust. However, C is unique because of its central position in the modern computing landscape. We can confidently say that almost everything you’ve ever done with a computer has eventually relied on software written in C. As just a few examples:

• The Linux kernel is written in C.
• The primary implementation of Python is written in C.
• The C standard library is the de facto standard way that software interacts with operating systems. Even Rust programs rely on C’s standard library for things like printing to the console and opening files.
• In general, whenever two different languages want to talk to each other, they go through C (via a foreign function interface).

Getting Started

Let’s write the smallest possible C program:

int main() {
    return 0;
}

Even this minimal program brings up a few basic things about C:

• In basic ways, the syntax looks a little like Java. There are curly braces and semicolons. There is even a type called int. (This is because the designers of Java based its syntax on C.)
• Unlike Java, however, there is no class definition here. You just write a main function at the top level; it’s not a method on some class. In fact, C doesn’t have classes or objects at all.
• C is a statically typed language (like Java but not like Python). This means that C makes you declare the types of everything you write down. This example shows one type: the return type of the main function is int.
• That return 0 for main determines the exit status for your program.

Let’s run our program. The commands you see here will assume you have followed our guide to setting up 3410’s RISC-V infrastructure, including setting up the rv alias. The rv alias works as a prefix that gives you access to the tools you need, so you can type any command you like after it. For example, you can type:

$ rv ls

and you’ll see similar results to running plain old ls.

Let’s compile the program, like this:

$ rv gcc minimal.c

where minimal.c is the name of the source file. GCC is the name of the compiler we’ll be using in this course.

That worked, but we actually recommend providing some more command-line options to the compiler whenever you use it. You can copy and paste our recommended options from the C compilation page. Then, add -o minimal to tell GCC where to put the output file (if you don’t, GCC picks the name a.out). So here’s a complete command:

$ rv gcc -Wall -Wextra -Wpedantic -Wshadow -Wformat=2 -std=c23 -o minimal minimal.c

That produces an executable file, minimal. Now let’s run it:

$ rv qemu minimal

That runs the QEMU emulator to execute the compiled minimal program. It won’t print anything at all!

Printing

Here’s a slightly more exciting program:

#include <stdio.h>

int main() {
    printf("Hello, 3410!\n");
    return 0;
}

We’ve added two lines:

• The #include is how you import libraries in C. The stdio.h file is part of the C standard library, which means it comes with every C compiler.
• The stdio.h file defines the printf function, which is how you print things in C. printf is more powerful than what we’re seeing here; we’ll see more of its power later.

The \n in the string is an escape sequence that means a newline character. That’s the same as in Java.

Now let’s declare and print a variable:

#include <stdio.h>

int main() {
    int n = 3410;
    printf("Hello, %d!\n", n);
    return 0;
}

We added a variable declaration of n, with type int. Read more about the basic types in C.

To print out the number, printf exploits format specifiers in the string that you pass to it. Format specifiers look like %d: they always start with %, followed by a few characters that tell printf how to format stuff. The d in this one stands for decimal, because that’s the base it uses.

If you have n format specifiers in your printf string, you should pass n extra arguments after the string to printf. It will print each extra argument using each specified format, in order.

Let’s try some other format specifiers. %b prints ints in binary, and %x prints them in hex:

#include <stdio.h>

int main() {
    int n = 3410;
    printf("Decimal: %d\n", n);
    printf("Binary: %b\n", n);
    printf("Hexadecimal: %x\n", n);
    return 0;
}

Read more about format specifiers for printf.

Playing with Numbers

C makes it easy to put our new knowledge about binary numbers and two’s complement into practice. We’ll use the int8_t type, which is an integer with exactly 8 bits. (In lots of “normal” code, you can just use int to get a default-sized integer—but for these examples, we really want to use just 8 bits.)

#include <stdio.h>
#include <stdint.h>

int main() {
    int8_t n = 7;
    printf("n = %hhd\n", n);
    return 0;
}

The %hhd format specifier is for printing the int8_t type in decimal. We also need to #include the stdint.h library to get the int8_t type.

We can also write our 8-bit number in binary notation:

#include <stdio.h>
#include <stdint.h>

int main() {
    int8_t n = 0b00000111;
    printf("n = %hhd\n", n);
    return 0;
}

This should also print 7. An important thing to reassure yourself is that, in the two programs above, the variable n contains exactly the same value. There is no difference between the same number specified in decimal notation and binary notation; the choice is just a convenience for the programmer, and the compiler will translate either one into exactly the same value for the computer. (And that value will be in binary because, of course, everything is bits.)

We can also use the sign bit. What’s this value if we flip the top bit of 7 from 0 to 1?

#include <stdio.h>
#include <stdint.h>

int main() {
    int8_t n = 0b10000111;
    printf("n = %hhd\n", n);
    return 0;
}

That prints -121. Maybe you can convince yourself this is correct by thinking of the largest negative value in 8 bits.

A Little More C

Let’s try the inversion trick from last time: the identity that, in two’s complement, ~x + 1 is equal to -x.

#include <stdio.h>
#include <stdint.h>

int main() {
    int8_t n = 7;
    printf("n (binary) = %hhb\n", n);
    printf("n (decimal) = %hhd\n", n);

    int8_t flipped = ~n + 1;
    printf("flipped (binary) = %hhb\n", flipped);
    printf("flipped (decimal) = %hhd\n", flipped);

    return 0;
}

That worked for 7. To see a little more of C, let’s try checking that this works for every number we can represent with a char.

#include <stdio.h>
#include <stdint.h>

int8_t flip(int8_t num) {
    return ~num + 1;
}

int main() {
    for (int8_t i = -128; i < 127; ++i) {
        //printf("i = %hhd\n", i);
        int8_t negated = -i;
        int8_t flipped = flip(i);
    printf("i = %hhd, neg = %hhd, flip = %hhd\n", i, negated, flipped);

        if (negated != flipped) {
            printf("mismatch!\n");
        }
    }
    return 0;
}

This example shows off C’s for loops and if conditions. If you’re familiar with Java, these should look pretty familiar. Read more about control flow in C.

It also demonstrates function definitions in C.

If you run this program, there are no mismatches! So we can be pretty sure this trick works for all the int8_t values, even if you don’t want to try doing the math.

Overflow

Computer representations of integers (usually) have a fixed width, i.e., the number of bits they use: for example, int8_t always has 8 bits. This has some fun consequences.

In our last example, we had to think through the minimum and maximum values you can store in an int8_t. What happens if you exceed this value?

The C language has pretty annoying rules about this. For signed numbers, it is actually a silent error (a concept known as undefined behavior) to exceed the maximum, e.g., to add 1 to the biggest possible signed number. But it’s legal to do this for unsigned numbers. So we’ll try it out with the type uint8_t, which is the unsigned (only-positive) version of our friend int8_t. Here’s a loop that just adds 1 to an int8_t value many times:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t num = 0;
    for (int i = 0; i < 500; ++i) {
        num += 1;
        printf("num = %hhu\n", num);
    }
    return 0;
}

If you run this program, you’ll see the number counting up from 1. When we reach 255, adding 1 takes us right back down to 0.

It can be helpful to think about the bits. 255 is the all-ones bit pattern: in 8 bits, 1111 1111. (Sometimes it’s helpful to put spaces in your binary numbers to group together 4 bits, just for legibility.) Adding one to this will “carry” all the way across, setting every bit to zero. The last carry bit would go in position 9, but because this is an 8-bit representation, the computer just drops that bit. And so, the result of the addition 1111 1111 + 0000 0001 is 0000 0000.

This behavior is called integer overflow and it is the source of many fun bugs in all kinds of software. Memorably, YouTube originally used a signed 32-bit number (i.e., an int) to represent the number of views for a video. That meant that the largest number of views that any video could have was $2^{32 - 1} - 1$, or 2,147,483,647 views. The first video to exceed this number of views was Psy’s “Gangnam Style”. YouTube made a cute announcement when they had to change that value to a 64-bit integer. That should be plenty of views for a long time (more than 9 quintillion views).

Prototypes, Headers, Libraries, and Linking

There is a lot more to explore about C programming that you will learn through doing assignments in 3410. But here is one more concept I think will be helpful to see early.

Declarations Must Precede Uses

Here’s a tiny program with one function call:

#include <stdio.h>

void greet(const char* name) {
    printf("Hello, %s!\n", name);
}

int main() {
    greet("3410");
}

(As an aside, void is the “return type” you use for functions that don’t return anything, and const char* is the type of a string literal. We’ll learn more about why the * is in there later in the course.)

A fun quirk about C is that it wants declarations to come before uses. That means that it won’t work to call greet before we define it, like in this broken program:

#include <stdio.h>

int main() {
    greet("3410");
}

void greet(const char *name) {
    printf("Hello, %s!\n", name);
}

Prototypes, a.k.a. Declarations

As you can imagine, this restriction can get frustrating, and unworkable if you need mutual recursion. The way to fix it is to use a prototype, a.k.a. a declaration. A function declaration looks a lot like a function definition but omits the body. So this program works:

#include <stdio.h>

void greet(const char *name);

int main() {
    greet("3410");
}

void greet(const char *name) {
    printf("Hello, %s!\n", name);
}

We just need to copy and paste the “signature” part of the function definition, put it at the top of the file, and add a semicolon. That makes it a declaration that means that the call to greet is legal.

Header Files

The need for these declarations is so common that programmers typically put them in a whole separate C source code file, called a header file. Header files are C files that, by convention, end with a .h instead of a .c and mostly just contain declarations. So we might put the declaration in greet.h:

void greet(const char *name);

We can use this declaration by #include-ing it:

#include <stdio.h>
#include "greet.h"

int main() {
    greet("3410");
}

void greet(const char *name) {
    printf("Hello, %s!\n", name);
}

Notice the difference between the #include <stdio.h> line and the #include "greet.h" line. The angle brackets search for built-in library headers; the quotation marks are for header files you write yourself and tell the compiler to look in the same directory as the source file.

In either case, #include works a lot like just “copying and pasting” the entire text of the file into your source program. So #include-ing greet.h looks the same to the compiler as a version that just includes the declaration right there.

Separating Source Files

Headers are also part of the mechanism that lets you break up long .c source files. Let’s say we want to create a separate greet.c library that just contains our greeting function:

#include <stdio.h>
#include "greet.h"

void greet(const char *name) {
    printf("Hello, %s!\n", name);
}

Then, our main.c can use the library like this:

#include <stdio.h>
#include "greet.h"

int main() {
    greet("3410");
}

By “copying and pasting” the contents of greet.h here, the #include sorta works as a way to “import” the greet function so we can use it in main.

Linking Multiple Files

Now, however, we need a way to combine the two .c files into a single executable. One option is to just give both source files on the command line:

$ rv gcc main.c greet.c -o main

Notice that we don’t list header files when compiling the whole thing: only .c files, not .h files. Header files are just for #include-ing into other files, so the compiler already sees the contents of those files implicitly.

There’s another way too: it can be useful to compile the .c files separately and then link them together. Here’s what that looks like:

$ rv gcc -c main.c -o main.o
$ rv gcc -c greet.c -o greet.o
$ rv gcc main.o greet.o -o main

The first two lines, with -c, compile the source files to object files that end in .o. Then, the last command links the two object files together into an executable.

Separating it out this way can save you time. If you only change greet.c, for example, then you only need to re-compile that file and then re-link; you can skip re-compiling the unchanged main.c.

Floating Point

Like other languages you’ve used before, C has a float type that works for numbers with a decimal point in them:

#include <stdio.h>

int main() {
    float n = 8.4f;
    printf("%f\n", n * 5.0f);
    return 0;
}

But how does float actually work? How do we represent fractional numbers like this at the level of bits? The answers have profound implications for the performance and accuracy of any software that does serious numerical computation.

For example, see if you can predict what the last line of this example will print:

#include <stdio.h>

int main() {
    float x = 0.00000001f;
    float y = 0.00000002f;

    printf("x = %e\n", x);
    printf("y = %e\n", y);
    printf("y - x = %e\n", y - x);

    printf("1+x = %e\n", 1.0f + x);
    printf("1+y = %e\n", 1.0f + y);
    printf("(1+y) - (1+x) = %e\n", (1.0f + y) - (1.0f + x));

    return 0;
}

Understanding how float actually works is the key to avoiding surprising pitfalls like this.

Real Numbers in Binary

Before we get to computer representations, let’s think about binary numbers “on paper.” We’ve seen plenty of integers in binary notation; we can extend the same thinking to numbers with fractional parts.

Let’s return to elementary school again and think about how to read the decimal number 19.64. The digits to the right of the decimal point have place values too: those are the “tenths” and “hundredths” places. So here’s the value that decimal notation represents:

$$19.64_{10} = 1 \times 10^1 + 9 \times 10^0 + 6 \times 10^{-1} + 4 \times 10^{-2}$$

Beyond the decimal point, the place values are negative powers of ten. We can use exactly the same strategy in binary notation, with negative powers of two. For example, let’s read the binary number 10.01:

$$10.01_2 = 1 \times 2^1 + 0 \times 2^0 + 0 \times 2^{-1} + 1 \times 2^{-2}$$

So that’s $2 + \frac{1}{4}$, or 2.25 in decimal.

The moral of this section is: binary numbers can have points too! But I suppose you call it the “binary point,” not the “decimal point.”

Fixed-Point Numbers

Next, computers need a way to encode numbers with binary points in bits. One way, called a fixed-point representation, relies on some sort of bookkeeping on the side to record the position of the binary point. To use fixed-point numbers, you (the programmer) have to decide two things:

• How many bits are we going to use to represent our numbers? Call this bit count $n$.
• Where will the binary point go? Call this position $e$ for exponent. By convention, $e=0$ means the binary point goes at the very end (so it’s just a normal integer), $e=-1$ means there is one bit after the binary point.

The idea is that, if you read your $n$ bits as an integer $i$, then the number those bits represent is $i \times 2^{e}$. (This should look a little like scientific notation, where you might be accustomed to writing numbers like $34.10 \times 10^{-5}$. It’s sort of like that, but with a base of 2 instead of 10.)

For example, let’s decide we’re going to use a fixed-point number system with 4 bits and a binary point right in the middle. In other words, $n = 4$ and $e = -2$. In this number system, the bit pattern 1001 represents the value $10.01_2$ or $2.25_{10}$.

It’s also possible to have positive exponents. If we pick a number system with $n = 4$ and $e = 2$, then the same bit pattern 1001 represents the value $1001_2 \times 2^2 = 100100_2$, or $36_{10}$. So positive exponents have the effect of tacking $e$ zeroes onto the end of the binary number. (Sort of like how, in scientific notation, $\times 10^e$ tacks $e$ zeroes onto the end.)

Let’s stick with 4 bits and try it out. If $e = -3$, what is the value represented by 1111? If $e = 1$, what is the value represented by 0101?

The best and worst thing about fixed-point numbers is that the exponent $e$ is metadata and not part of the actual data that the computer stores. It’s in the eye of the beholder: the same bit pattern can represent many different numbers, depending on the exponent that the programmer has in mind. That means the programmer has to be able to predict the values of $e$ that they will need for any run of the program.

That’s a serious limitation, and it means that this strategy is not what powers the float type. On the other hand, if programs can afford the complexity to deal with this limitation, fixed-point numbers can be extremely efficient—so they’re popular in resource-constrained application domains like machine learning and digital signal processing. Most software, however, ends up using a different strategy that makes the exponent part of the data itself.

Floating-Point Numbers

The float type gets its name because, unlike a fixed-point representation, it lets the binary point float around. It does that by putting the point position right into the value itself. This way, every float can have a different $e$ value, so different floats can exist on very different scales:

#include <stdio.h>

int main() {
    float n = 34.10f;
    float big = n * 123456789.0f;
    float small = n / 123456789.0f;
    printf("big = %e\nsmall = %e\n", big, small);
    return 0;
}

The %e format specifier makes printf use scientific notation, so we can see that these values have very different magnitudes.

The key idea is that every float actually consists of three separate unsigned integers, packed together into one bit pattern:

• A sign, $s$, which is a single bit.
• The exponent, an unsigned integer $e$.
• The significand (also called the mantissa), another unsigned integer $g$.

Together, a given $s$, $e$, and $g$ represent this number:

$$(-1)^s \times 1.g \times 2^{e-127}$$

…where $1.g$ is some funky notation we’ll get to in a moment. Let’s break it down into the three terms:

• $(-1)^s$ makes $s$ work as a sign bit: 0 for positive, 1 for negative. (Yes, floating point numbers use a sign–magnitude strategy: this means that +0.0 and -0.0 are distinct float values!)
• $1.g$ means “take the bits from $g$ and put them all after the binary point, with a 1 in the ones place.” The significand is the “main” part of the number, so (in the normal case) it always represents a number between 1.0 and 2.0.
• $2^{e-127}$ is a scaling term, i.e., it determines where the binary point goes. The $-127$ in there is a bias: this way, the unsigned exponent value $e$ can work to represent a wide range of both positive and negative binary-point position choices.

The float type is actually an international standard, universally implemented across programming languages and hardware platforms. So it behaves the same way regardless of the language you’re programming in and the CPU or GPU you run your code on. It works by packing the three essential values into 32 bits. From left to right:

• 1 sign bit
• 8 exponent bits
• 23 significand bits

To get more of a sense of how float works at the level of bits, now would be a great time to check out the amazing tool at float.exposed. You can click the bits to flip them and make any value you want.

Conversion Examples

As an exercise, we can try converting decimal numbers to floating-point representations by hand and using float.exposed to check our work. Let’s try representing the value 8.25 as a float:

1. First, let’s convert it to binary: $1000.01_2$
2. Next, normalize the number by shifting the binary point and multiplying by $2^{\text{something}}$: $1.00001 \times 2^3$
3. Finally, break down the three components of the float:
   • $s = 0$, because it’s a positive number.
   • $g$ is the bit pattern starting with 00001 and then a bunch of zeroes, i.e., we just read the bits after the “1.” in the binary number.
   • $e = 3 + 127$, where the 3 comes from the power of two in our normalized number, and we need to add 127 to account for the bias in the float representation.

Try entering these values (0, 00001000…, and 130) into float.exposed to see if it worked. It’s easiest to enter the exponent in the little text box and the significand by clicking bits in the bit pattern.

Can you convert -5.125 in the same way?

Checking In with C

To prove that float.exposed agrees with C, we can use a little program that reinterprets the bits it produces to a float and prints it out:

#include <stdio.h>
#include <stdint.h>
#include <string.h>

int main() {
    uint32_t bits = 0x41040000;

    // Copy the to a variable with a different type.
    float val;
    memcpy(&val, &bits, sizeof(val));

    // Print the bits as a floating-point number.
    printf("%f\n", val);
    return 0;
}

The memcpy function just copies bits from one location to another. Don’t worry about the details of how to invoke it yet; we’ll cover that later in 3410.

Also, we can use bit operators such as bit shift and a bit-wise AND with a mask to isolate the sign, exponent, and significand from the 32-bit float.

#include <stdio.h>
#include <stdint.h>
#include <string.h>

int main() {
    uint32_t bits = 0x41040000;
    uint32_t significand = bits & 0x007fffff; // mask and isolate the mantissa
    uint32_t exponent = (bits & 0x7f800000) >> 23; // mask and bit shift
    uint32_t sign = (bits & 80000000) >> 31; // mask and bit shift


    // Print the components of a floating-point number.
    printf("s = %b, e = %b, g = %b \n", sign, exponent, significand);
    return 0;
}

Special Cases

Annoyingly, we haven’t yet seen the full story for floating-point representations. The above rules apply to most float values, but there are a few special cases:

• To represent +0.0 and -0.0, you have to set both $e = 0$ and $g = 0$. (That is, use all zeroes for all the bits in both of those ranges.) We need this special case to “override” the significand’s implicit 1 that would otherwise make it impossible to represent zero. And requiring that $e=0$ ensures that there are only two zero values, not many different zeroes with different exponents.
• When $e = 0$ but $g \neq 0$, that’s a denormalized number. The rule is that denormalized numbers represent the value $(-1)^s \times 0.g \times 2^{-126}$. The important difference is that we now use $0.g$ instead of $1.g$. These values are useful to eke out the last drops of precision for extremely small numbers.
• When $e$ is “all ones” and $g = 0$, that represents infinity. (Yes, we have both +∞ and -∞.)
• When $e$ is “all ones” and $g \neq 0$, the value is called “not a number” or NaN for short. NaNs arise to represent erroneous computations

The rules around infinity and NaN can be a little confusing. For example, dividing zero by zero is NaN, but dividing other numbers by zero is infinity:

#include <stdio.h>

int main() {
    printf("%f\n", 0.0f / 0.0f);  // NaN
    printf("%f\n", 5.0f / 0.0f);  // infinity
    return 0;
}

Other Floating-Point Formats

All of this so far has been about one (very popular) floating-point format: float, also known as “single precision” or “32-bit float” or just f32. But there are many other formats that work using the same principles but with different details. A few to be aware of are:

• double, a.k.a. “double precision” or f64, is a 64-bit format. If offers even more accuracy and dynamic range than 32-bit floats, at the cost of taking up twice as much space. There is still only one sign bit, but you get 11 exponent bits and 52 significand bits.
• Half-precision floating point goes in the other direction: it’s only 16 bits in total (5 exponent bits, 10 significand bits).
• The bfloat16 or “brain floating point” format is a different 16-bit floating-point format that was invented recently specifically for machine learning. It is just a small twist on “normal” half-precision floats that reallocates a few bits from the significand to the exponent (8 exponent bits, 7 significand bits). It turns out that having extra dynamic range, at the cost of precision, is exactly what lots of deep learning models need. So it has very quickly become implemented in lots of hardware.

Some General Guidelines

Now that you know how floating-point numbers work, we can justify a few common pieces of advice that programmers often get about using them:

• Floating-point numbers are not real numbers. Expect to accumulate some error when you use them.
• Never use floating-point numbers to represent currency. When people say $123.45, they want that exact number of cents, not $123.40000152. Use an integer number of cents: i.e., a fixed-point representation with a fixed decimal point.
• If you ever end up comparing two floating-point numbers for equality, with f1 == f2, be suspicious. For example, try 0.1 + 0.2 == 0.3 to be disappointed. Consider using an “error tolerance” in comparisons, like abs(f1 - f2) < epsilon.
• Floating-point arithmetic is slower and costs more energy than integer or fixed-point arithmetic. You get what you pay for: the flexibility of floating-point operations mean that they are fundamentally more complex for the hardware to execute. That’s why many practical machine learning systems convert (quantize) models to a fixed-point representation so they can run efficiently.

For many more details and much more advice, I recommend “What Every Computer Scientist Should Know About Floating-Point Arithmetic” by David Goldberg.

Data Types in C

Type Aliases

Don’t like the names of types in C? You can create type aliases to give them new names:

#include <stdio.h>

typedef int number;

int main() {
    number x = 3410;
    int y = x / 2;
    printf("%d %d\n", x, y);
}

Use typedef <old type> <new type> to declare a new name.

This admittedly isn’t very useful by itself, but it will come in handy as types get more complicated to write. See the C reference pages on typedef for more.

Structures

In C, you can declare structs to package up multiple values into a single, aggregate value:

#include <stdio.h>

struct point {
    int x;
    int y;
};

void print_point(struct point p) {
    printf("(%d, %d)\n", p.x, p.y);
}

int main() {
    struct point location = {4, 10};
    location.y = 2;
    print_point(location);
}

Structs are a little like objects in other languages (e.g., Java), but they don’t have methods—only fields. You use “dot syntax” to read and write the fields. This example also shows off how to initialize a new struct, with curly brace syntax:

struct point location = {4, 10};

You supply all the fields, in order, in the curly braces of the initializer.

Again, there is a section in the C reference pages for more on struct declarations.

Short Names for Structs

The type of the struct in the previous example is struct point. It’s common to give structs like these short names, for which typedef can help:

#include <stdio.h>

typedef struct {
    int x;
    int y;
} point_t;

void print_point(point_t p) {
    printf("(%d, %d)\n", p.x, p.y);
}

int main() {
    point_t location = {4, 10};
    location.y = 2;
    print_point(location);
}

This version uses a typedef to give the struct the shorter name point_t instead of struct point. By convention, C programmers often use <something>_t for custom type names to make them stand out.

Enumerations

There is another kind of “custom” data type in C, called enum. An enum is for values that can be one of a short list of options. For example, we can use it for seasons:

#include <stdio.h>

typedef enum {
    SPRING,
    SUMMER,
    AUTUMN,
    WINTER,
} season_t;

int main() {
    season_t now = WINTER;
    season_t next = SPRING;
    printf("%d %d\n", now, next);
    return 0;
}

We’re using the same typedef trick as above to give this type the short name season_t instead of enum season.

Enums are useful to avoid situations where you would otherwise use a plain integer. They’re more readable and maintainable than trying to keep track of which number means which season in your head.

There is a reference page on enums too.

Arrays & Pointers

Arrays

Like other languages you have used before, C has arrays. Here’s an example:

#include <stdio.h>

int main() {
    int courses[7] = {1110, 1111, 2110, 2112, 2800, 3110, 3410};

    int course_total = 0;
    for (int i = 0; i < 7; ++i) {
        course_total += courses[i];
    }
    printf("the average course is CS %d\n", course_total / 7);

    return 0;
}

You declare an array of 7 ints like this:

int courses[7];

And you can also, optionally, provide an initial value for all of the things in the array, as we do in the example above:

int courses[7] = {1110, 1111, 2110, 2112, 2800, 3110, 3410};

You access arrays like courses[i]. This works for both reading and writing. You can read more about arrays in the C reference pages.

Pointers

Pointers are (according to me) the essential feature of C. They are what make it C. They are simultaneously dead simple and wildly complex. They can also be the hardest aspect of C programming to understand. So forge bravely on, but do not worry if they seem weird at first. Pointers will feel more natural with time, as you gain more experience as a C programmer.

Memory

Pointers are a way for C programs to talk about memory, so we first need to consider what memory is.

It’s helpful to think of a simplified computer architecture diagram, consisting of a processor and a memory. The processor is where your C code runs; it can do any computation you want, but it can’t remember anything. The memory is where all the data is stored; it remembers a bunch of bits, but it doesn’t do any computation at all. They are connected—imagine wires that allow them to send signals (made of bits) back and forth. There are two things the CPU can do with the memory: it can load the value at a given address of its choosing, and it can store a new value at an address.

Abstractly, we can think of memory as a giant array of bytes. Metaphorically speaking (not actually!), it might be helpful to imagine a C declaration like this:

uint8_t mem[SIZE];

where SIZE is the total number of bytes in your machine. Several billion, surely. In this metaphor, the processor reads from memory by doing something like mem[123], and it writes by doing mem[123] = 45 in C. The “address” works like an index into this metaphorical array of bytes.

Maybe the most important thing to take away from this metaphor is that an address is just bits. Because, after all, everything is just bits. You can think of those bits as an integer, i.e., the index of the byte you’re interested in within the imaginary mem array.

A Pointer is an Address

In C, a pointer is the kind of value for memory addresses. You can think of a pointer as logically pointing to the value at a given address, hence the name.

But I’ll say it again, because it’s important: pointers are just bits. Recall that a double variable and a int64_t variable are both 64-bit values—from the perspective of the computer, there is no difference between these kinds of values. They are both just groups of 64 bits, and only the way the program treats these bits makes them an integer or a floating-point number. Pointers are the same way: they are nothing more than 64-bit values, treated by programs in a special way as addresses into memory.

The size of pointers (the number of bits) depends on the machine you’re running on. In this class, all our code is compiled for the RISC-V 64-bit architecture, so pointers are always 64 bits. (If you’ve ever heard a processor called a “32-bit” or “64-bit” architecture, that number probably describes the size of pointers, among other values. Most modern “normal” computers (servers, desktops, laptops, and mobile devices) use 64-bit processors, but 32-bit and narrower architectures are still commonplace in embedded systems.)

Pointer Types and Reference-Of

In C, the type of a pointer to a value of type T is T*. For example, a pointer to an integer might have type int*, and pointer to a floating-point value might be a float*, and a pointer to a pointer to a character could have type char**.

To reiterate, all of these types are nothing more than 64-bit memory addresses. The only difference is in the way the program treats those addresses: e.g., the program promises to only store an int in memory at the address contained in an int*.

In C, you can think of all data in the program as “living” in memory. So every variable and every function argument exists somewhere in the giant metaphorical mem array we imagined above. That means that every variable has an address: the index in that huge array where it lives.

C has a built-in operator to obtain the address for any variable. The & operator, called the reference-of operator, takes a variable and gives you a pointer to the variable. For example, if x is an int variable, then &x is the address where x is stored in memory, with type int*.

Here’s an example where we use & to get the address of a couple of variables:

#include <stdio.h>

int main() {
    int x = 34;
    int y = 10;

    int* ptr_to_x = &x;
    int* ptr_to_y = &y;

    printf("ints are %lu bytes\n", sizeof(int));
    printf("pointers are %lu bytes\n", sizeof(int*));
    printf("x is located at %p\n", ptr_to_x);
    printf("y is located at %p\n", ptr_to_y);

    return 0;
}

We’re also using the %p format specifier for printf, which prints out memory addresses in hexadecimal format. (By convention, programmers almost always use hex when writing memory addresses.) Here’s what this program printed once on my machine:

ints are 4 bytes
pointers are 8 bytes
x is located at 0x1555d56bbc
y is located at 0x1555d56bb8

The built-in sizeof operator tells us that pointers are 8 bytes (64 bits) on our RISC-V 64 architecture, which makes sense. ints are 4 bytes, as they are on many modern platforms. The system is free to choose different addresses for variables, so don’t worry if the addresses are different when you run this program—that’s perfectly normal.

In this output, however, the system is telling us that it chose very nearby addresses for the x and y variables: the first 60 bits of these addresses are identical. The address of x ends in the 4 bits corresponding to the hex digit c (12 in decimal), and y lives at an address ending in 8. That means that x and y are located right next to each other in memory: y occupies the 4 bytes at addresses …6bb8, …6bb9, …6bba, and …6bbb, and then the 4 bytes for x begin at the very next address, …6bbc.

Everything Has an Address, Including Pointers

Just to emphasize the idea that, in C, all variables live somewhere in memory, let’s take a moment to appreciate that ptr_to_x and ptr_to_y are themselves variables. So they also have addresses:

#include <stdio.h>

int main() {
    int x = 34;
    int y = 10;

    int* ptr_to_x = &x;
    int* ptr_to_y = &y;

    printf("ints are %lu bytes\n", sizeof(int));
    printf("pointers are %lu bytes\n", sizeof(int*));
    printf("x is located at %p\n", ptr_to_x);
    printf("y is located at %p\n", ptr_to_y);
    printf("ptr_to_x is located at %p\n", &ptr_to_x);
    printf("ptr_to_y is located at %p\n", &ptr_to_y);

    return 0;
}

Always remember: pointers are just bits, pointer-typed variables follow the same rules as any other variables.

Pointers as References, and Dereferencing

While pointers are (like everything else) just bits, what makes them useful is that it’s also possible to think of them in a different way: as references to other values. From this perspective, pointers in C resemble references in other languages you have used: it is the power you need to create variables that refer to other values.

The key C feature that makes this view possible is its * operator, called the dereference operator. The C expression *p means, roughly, “take the pointer p and follow it to wherever it points in memory, so I can read or write that value (not p itself).”

You can use the * operator both to load from (read) and store to (write) memory. Imagine a pointer p of type int*. Here’s how you read from the place where p points:

int value = *p;

And here’s how you write to that location where p points:

*p = 5;

When you’re reading, *p can appear anywhere in a larger expression too, so you can use *p + 5 to load the value p points to and then add 5 to that integer.

All this means that you can use pointers and dereferencing to perform “remote control” accesses to other variables, in the same way that references work in other programming languages. Here’s an example:

#include <stdio.h>

int main() {
    int x = 34;
    int y = 10;

    int* ptr = &x;

    printf("initially, x = %d and y = %d and ptr = %p\n", x, y, ptr);
    *ptr = 41;
    printf("afterward, x = %d and y = %d and ptr = %p\n", x, y, ptr);

    return 0;
}

The point of this example is that modifying *ptr changes the value of x. It does not, however, change the value of ptr itself: that still points to the same place.

To emphasize that pointer-typed variables behave like any other variable, we can also try assigning to the pointer variable. It is absolutely critical to recognize the subtle difference between assigning to *ptr and assigning to ptr:

#include <stdio.h>

int main() {
    int x = 34;
    int y = 10;

    int* ptr = &x;

    printf("0: x = %d and y = %d and ptr = %p\n", x, y, ptr);
    *ptr = 41;
    printf("1: x = %d and y = %d and ptr = %p\n", x, y, ptr);
    ptr = &y;
    printf("2: x = %d and y = %d and ptr = %p\n", x, y, ptr);
    *ptr = 20;
    printf("3: x = %d and y = %d and ptr = %p\n", x, y, ptr);

    return 0;
}

The thing to pay attention to here is that assigning to ptr just changes ptr itself; it does not change x or y. (That’s the rule for assigning to any variable, not just pointers!) Then, when we assign to *ptr the second time, it updates y this time, because that’s where it points.

I hope this kind of “variables that reference other variables” thinking is familiar from using other languages, where references are extremely common. The difference in C is that there is no magic: we get reference behavior out of the “raw materials” of bits, by treating some 64-bit values as addresses in memory. Under the hood, this is how references in other languages are implemented too—but in C, we get direct access to the underlying bits.

Arrays are Mostly Just Pointers

Now that we know about pointers, let’s revisit arrays. In C, an array is a sequence of values all laid out next to each other in memory. We can use the & reference-of operator to check out the addresses of the elements in an array:

#include <stdio.h>

int main() {
    int courses[7] = {1110, 1111, 2110, 2112, 2800, 3110, 3410};

    printf("first element is at %p\n", &courses[0]);
    printf(" next element is at %p\n", &courses[1]);
    printf(" last element is at %p\n", &courses[6]);

    return 0;
}

When I ran this program on my machine once, it told me that the first element of the array was located at address 0x1555d56b90, the next element was at 0x1555d56b94, and so on, with each address increasing by 4 with each element. Remember that ints are 4 bytes on our platform, so these addresses mean that the elements are packed densely, each one next to the other.

You can think of the array having a base address $b$. Then, the address of an element at index $i$ has this address:

$$b + s \times i$$

where $s$ is the size of the elements, in bytes.

Treat an Array as a Pointer to the First Element

In fact, C lets you treat an array itself as if it were a pointer to the first element: i.e., the base address $b$. This works, for example:

#include <stdio.h>

int main() {
    int courses[7] = {1110, 1111, 2110, 2112, 2800, 3110, 3410};

    printf("first element is at %p\n", &courses[0]);
    printf("the array itself is %p\n", courses);

    return 0;
}

And C tells us that, if we treat courses as a pointer, it has the same address as its first element. From that perspective, it is helpful to think of an array variable as storing of the address of the first element of the array. One important takeaway from this realization is that C does not store the length of your array anywhere—just a pointer to the first element. It’s up to you to keep track of the length yourself somehow.

This means that, if you want to pass an array to a function, you can use a pointer-typed argument:

#include <stdio.h>

int sum_n(int* vals, int count) {
    int total = 0;
    for (int i = 0; i < count; ++i) {
        total += vals[i];
    }
    return total;
}

int main() {
    int courses[7] = {1110, 1111, 2110, 2112, 2800, 3110, 3410};

    int sum = sum_n(courses, 7);
    printf("the average course is CS %d\n", sum / 7);

    return 0;
}

If you do, it is always a good idea to pass the length of the array in a separate argument. The subscript syntax, like vals[i], works the same way for pointers as it does for arrays.

Pointer Arithmetic

Since we’ve seen that the elements of an array exist right next to each other in memory, can we access them by computing their addresses ourselves? Absolutely! C supports arithmetic operators like + and - on pointers, but they follow a special rule you will need to remember. Here’s an example:

#include <stdio.h>

void experiment(int* courses) {
    printf("courses     = %p\n", courses);
    printf("courses + 1 = %p\n", courses + 1);
}

int main() {
    int courses[7] = {1110, 1111, 2110, 2112, 2800, 3110, 3410};
    experiment(courses);
    return 0;
}

The important thing to notice here is that adding 1 to courses increased its value by 4, not by 1. That’s because the rule in C is that pointer arithmetic “moves” pointers by element-sized chunks. So because courses has type int*, its element size is 4 bytes. The rule says that, if you write the expression courses + n, that will actually add $n \times 4$ bytes to the address value of courses.

This may seem odd, but it’s extremely useful: it means that pointer arithmetic stays pointing to the first byte of an element. If you think of courses itself as a pointer to the first int in the array, then courses + 1 points to the (first byte of) the second int in the array. It would be inconvenient and annoying if doing +1 just took us to the second byte in the first element; nobody wants that.

A consequence is that we can use pointer arithmetic directly, along with the dereferencing operator *, to access the elements of an array:

#include <stdio.h>

void experiment(int* courses) {
    printf("courses[0] = %d\n", *(courses + 0));
    printf("courses[5] = %d\n", *(courses + 5));
}

int main() {
    int courses[7] = {1110, 1111, 2110, 2112, 2800, 3110, 3410};
    experiment(courses);
    return 0;
}

Now that you know how arrays and pointer arithmetic work, you don’t actually need the subscripting operator! Instead of writing arr[idx], you can always just use *(arr + idx). It means the same thing.

Here’s a fun but mostly useless fact about C programming. Since arr[idx] means exactly the same thing as *(arr + idx), and because + is commutative, this also means the same thing as *(idx + arr), which can—by the same rules—also be written as idx[arr]. So if you really want to confuse the people reading your code, you can always write your array indexing expressions backward:

#include <stdio.h>

void experiment(int* courses) {
    printf("courses[0] = %d\n", 0[courses]);
    printf("courses[5] = %d\n", 5[courses]);
}

int main() {
    int courses[7] = {1110, 1111, 2110, 2112, 2800, 3110, 3410};
    experiment(courses);
    return 0;
}

But this is, uh, not a great idea in the real world, where your code will actually be read by humans with thoughts and feelings.

Strings are Null-Terminated Character Arrays

Our new knowledge about pointers and arrays now lets us revisit another concept we’ve already been using in C: strings. You may recall that we previously told you not to worry about why strings in C have the type char*. Now we can demystify this fact: strings in C are arrays of char values, each of which is a single character.

On most modern systems (including our RISC-V target), char is a 1-byte (8-bit) type. So each char in a string is a number between 0 and $2^8-1$, i.e., 255. Programs use a text encoding to decide which number represents which textual character. An extremely popular encoding that includes the basic English alphabet is ASCII. But C saves you the trouble of looking up characters in the ASCII table; you can use a literal 'q' (note the single quotes!) to get a char with the numeric value corresponding to a lower-case q character.

As with any other array in C, a string just consists of a pointer to the first element (the first character in this case). So when you see char* str, you can think either “str is a string” or “str is the address of the first element of a string.”

Also as with any other array, we need a way to know how many elements there are in the array. Instead of keeping track of the length as an integer, as we have so far, C strings use a different convention: they use a null character, with value 0, to indicate the end of a string. You can write this special character as '\0'. This means that various functions that process strings work by iterating through all the characters and then stopping when the character is '\0'.

All this means that you can use everything you know about C arrays and apply them to strings. For example:

#include <stdio.h>

void print_line(char* s) {
    for (int i = 0; s[i] != '\0'; ++i) {
        fputc(s[i], stdout);
    }
    fputc('\n', stdout);
}

int main() {
    char message[7] = {'H', 'e', 'l', 'l', 'o', '!', '\0'};
    print_line(message);
    return 0;
}

This shows several C array features that are equally useful for strings (character arrays) as they are for any other array:

• Array initialization, with curly braces.
• Treating arrays as pointers to their first element, so we can pass our char array to a function expecting a char*.
• Using array subscript notation, like s[i], on the pointer to access the array’s elements.

One important thing to realize here is that, when we initialize this array “manually” using the array initialization syntax, we have to remember to include the null terminator '\0' ourselves. Ordinary string literals, like "Hello!", include a null terminator automatically. So these lines are roughly equivalent:

char message[7] = {'H', 'e', 'l', 'l', 'o', '!', '\0'};
char* message = "Hello!";

If you go the manual route and forget the null terminator, bad things will happen. Try to imagine what might go wrong in this program if we left off the '\0', for example. There are many possibilities, and none of them are good. (This is an example of undefined behavior in C, so there is no single answer.)

Fun Pointer Tricks

Here are some useful things you can do with pointers.

Pass by Reference

Pointers are useful for passing parameters by reference. C doesn’t actually have a way to “native” pass-by-reference; everything is passed as a value. But you can pass pointers as values and use those to refer to other values.

For example, this swap function doesn’t work because a and b are passed by value:

#include <stdio.h>

void swap(int x, int y) {
    int tmp = x;
    x = y;
    y = tmp;
}

int main() {
    int a = 34;
    int b = 10;
    printf("%d %d\n", a, b);
    swap(a, b);
    printf("%d %d\n", a, b);
}

But if we pass pointers instead, we can dereference those pointers so we modify the original variables in place. So this version works:

#include <stdio.h>

void swap(int* x, int* y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int main() {
    int a = 34;
    int b = 10;
    printf("%d %d\n", a, b);
    swap(&a, &b);
    printf("%d %d\n", a, b);
}

Null Pointers

Because pointers are just integers, you can set the to zero. Zero isn’t actually a valid memory address. That makes the zero value useful for signaling the absence of data. It’s particularly useful for writing functions with optional parameters.

In C, you can use NULL to get a pointer with value zero. Here’s an example that extends our swap function to optionally also produce the sum of the values:

#include <stdio.h>

void swap_and_sum(int* x, int* y, int* sum) {
    int tmp = *x;
    *x = *y;
    *y = tmp;

    if (sum != NULL) {
        *sum = *x + *y;
    }
}

int main() {
    int a = 34;
    int b = 10;
    printf("%d %d\n", a, b);
    int sum;
    swap_and_sum(&a, &b, &sum);
    swap_and_sum(&a, &b, NULL);
    printf("%d %d\n", a, b);
    printf("sum = %d\n", sum);
}

When a pointer might be null, always remember to include a != NULL check before using it. The possibility of accidentally dereferencing a null pointer is Sir Tony Hoare’s “billion-dollar mistake.”

Pointers to Pointers

The type of a pointer to a value of type T is T*. That includes when T itself is a pointer type! So you can create pointers to pointers, and so on. For example, int** is a pointer to a pointer to an int. (It’s not common to go any deeper than two levels, but nothing stops you…)

It’s a silly example, but we can make our swap function swap int*s instead of actual ints:

#include <stdio.h>

void swap(int** x, int** y) {
    int* tmp = *x;
    *x = *y;
    *y = tmp;
}

int main() {
    int a = 34;
    int b = 10;

    int* a_ptr = &a;
    int* b_ptr = &b;

    printf("%d %d\n", a, b);
    swap(&a_ptr, &b_ptr);
    printf("%d %d\n", a, b);
}

Pointers to Functions

Maybe you have taken CS 3110, so you know it’s cool to pass functions into other functions. C can do that too, kind of! By creating pointers to functions.

The syntax admittedly looks really weird. You write T1 (*name)(T2, T3) for a pointer to a function that takes argument types T2 and T3 and returns a type T1.

Here’s an example in action:

#include <stdio.h>

int incr(int x) {
    return x + 1;
}

int decr(int x) {
    return x - 1;
}

int apply_n_times(int x, int n, int (*func)(int)) {
    for (int i = 0; i < n; ++i) {
        x = func(x);
    }
    return x;
}

int main() {
    int n = 20;
    n = apply_n_times(n, 5, &incr);
    n = apply_n_times(n, 2, &decr);
    printf("n = %d\n", n);
}

Pointers to Anything

Remember that pointers are bits, and all pointers look the same: they are just memory addresses. So, if you just look at the bits, there is no difference between an int* and a float* and a char*. They are all just addresses.

For this reason, C has a special type that means “a pointer to something, but I don’t know what.” The type is spelled void*. It is useful in situations where you don’t care what’s being pointed to.

Here’s a simple program that uses a void* to wrap up a call to printf for showing addresses:

#include <stdio.h>

void print_ptr(void* p) {
    printf("%p\n", p);
}

int main() {
    int x = 34;
    float y = 10.0f;
    print_ptr(&x);
    print_ptr(&y);
}

The Stack, The Heap, the Dynamic Memory Allocation

The Stack

So far, all the data we’ve used in our C programs has been stored in local variables. These variables exist for the duration of the function call—and as soon as the function returns, the variables disappear. All this per-call local-variable storage is part of the function call stack, also known as just the stack.

You may have visualized the function call stack when you learned other programming languages. You can draw it with a box for every function call, which gets created (pushed) when you call the function and destroyed (popped) when the function returns. These boxes are called stack frames, or just frames for short (or sometimes, an activation record). For reasons that will become clear soon, when thinking about C programs, it’s important that we draw the stack growing “downward,” so the first call’s frame is at the top of the page.

Here is a mildly interesting C program that uses the stack:

#include <stdio.h>

const float EULER = 2.71828f;
const int COUNT = 10;

// Fill an array, `dest`, with `COUNT` values from an exponential series.
void fill_exp(float* dest) {
    dest[0] = 1.0f;
    for (int i = 1; i < COUNT; ++i) {
        dest[i] = dest[i - 1] * EULER;
    }
}

// Print the first `n` values in a float array.
void print_floats(float* vals, int n) {
    for (int i = 0; i < n; ++i) {
        printf("%f\n", vals[i]);
    }
}

int main() {
    float values[COUNT];
    fill_exp(values);
    print_floats(values, COUNT);
    return 0;
}

The values array is part of main’s stack frame. The calls to fill_exp and print_floats have pointer variables in their stack frames that point to the first element of this array.

Limitations of the Stack

The key limitation of putting your data on the stack comes from this observation: variables only live as long as the function call. So if you want data to remain after a function call returns, local variables (data in stack frames) won’t suffice.

The consequence of this observation is the following rule: never return a pointer to a local variable. When you do, you’re returning a pointer to data that is about to be destroyed. So it will be a mistake (undefined behavior in C) to use that pointer.

On the other hand, both of these things are perfectly safe:

• Passing a pointer to a local variable as an argument to a function. Our example above does this. This is fine because the data exists in the caller’s stack frame, which still exists as long as the callee is running (and longer).
• Returning a non-pointer value stored in a local variable. The compiler takes care of copying return values into the caller’s stack frame if necessary.

To get a sense for why this is limiting, consider our example above. It’s inconvenient that we have to write a fill_exp function that fills in an exponential series into an array that already exists. It seems more natural to instead write a create_exp function that returns an array populated with an exponential series. Something like this:

#include <stdio.h>

const float EULER = 2.71828f;
const int COUNT = 10;

// This function has a bug! Do not return pointers to local variables!
float* create_exp() {
    float dest[COUNT];
    dest[0] = 1.0f;
    for (int i = 1; i < COUNT; ++i) {
        dest[i] = dest[i - 1] * EULER;
    }
    return dest;
}

// Print the first `count` values in a float array.
void print_floats(float* vals, int count) {
    for (int i = 0; i < count; ++i) {
        printf("%f\n", vals[i]);
    }
}

int main() {
    float* values = create_exp();
    print_floats(values, COUNT);
    return 0;
}

That API looks cleaner; we can rely on the create_exp function to both create the array and to fill it up with the values we want. But this program has a serious bug—in C, it has undefined behavior. When I ran it on my machine, it just hung indefinitely. Of course, subtler and worse consequences are also possible.

To see what’s wrong, let’s think about what might happen with the stack in memory. All the stack frames, and all the local variables, exist at addresses in memory. When the call create_exp returns, its memory doesn’t literally get destroyed; the memory, literally speaking, still exists in my computer. But when we call print_floats on the following line, its stack frame takes the space previously occupied by the create_exp frame! So its local variables (vals and count) take up the same space that was previously occupied by the dest array.

The Heap

This create_exp example is not en edge case; in practice, real programs often need to store data that “outlives” a single function call. C has a separate region of memory just for this purpose. This region is called the heap.

The key distinction between the heap and the stack is that you, the programmer, have to manage data on the heap manually. The compiler takes care of managing data on the stack: it allocates space in stack frames for all your local variables automatically. Your code, on the other hand, needs to explicitly allocate and deallocate regions of memory on the heap whenever it needs to store data that lasts beyond the end of a function call.

C comes with a library of functions for managing memory on the heap, which live in a header called stdlib.h. The two most important functions are:

• malloc (short for memory allocate): Allocate a new region of memory on the heap, consisting of a number of bytes that you choose. Return a pointer to the first byte in the newly allocated region.
• free: Take a pointer to some memory previously allocated with malloc and deallocate it, freeing up the memory for use by some future allocation.

Here’s a version of our create_exp program that (correctly) uses the heap:

#include <stdio.h>
#include <stdlib.h>

const float EULER = 2.71828f;
const int COUNT = 10;

// Allocate a new array containing `COUNT` values from an exponential series.
float* create_exp() {
    float* dest = malloc(COUNT * sizeof(float));  // New!
    dest[0] = 1.0f;
    for (int i = 1; i < COUNT; ++i) {
        dest[i] = dest[i - 1] * EULER;
    }
    return dest;
}

// Print the first `count` values in a float array.
void print_floats(float* vals, int count) {
    for (int i = 0; i < count; ++i) {
        printf("%f\n", vals[i]);
    }
}

int main() {
    float* values = create_exp();
    print_floats(values, COUNT);
    free(values);  // Also new!
    return 0;
}

Let’s look at the new lines in more detail. First, the allocation:

float* dest = malloc(COUNT * sizeof(float));

The malloc function takes one argument: the number of bytes of memory you want to allocate. We want COUNT floating-point values, so we can compute that size in bytes by multiplying that array length by sizeof(float) (which gives us the number of bytes occupied by a single float). You almost always want to use sizeof in the argument of your malloc calls; this is clearer and more portable than trying to remember the size of a given type yourself.

Next, the deallocation:

free(values);

The free function also takes one argument: a pointer to memory that you previously allocated with malloc. This illustrates the cost of manual memory management: whenever you allocate memory, you take responsibility for deallocating it. That’s unlike the stack, where the compiler takes care of managing the life-cycle of the memory for you. (By the way, you should never call free on a pointer to the stack.)

The Heap Laws

Because you manually manage the memory on the heap, it’s possible to make mistakes. There are four big things you must avoid:

• Use after free. After you free memory, you are no longer allowed to use it. Your program may not load or store through any pointers into the freed memory.
• Double free. You may only free memory once. Do not call free on already-freed memory.
• Memory leak. You must pair every call to malloc with a corresponding call to free. Otherwise, your program will never “recycle” its memory, so the data will grow until you run out of memory.
• Out-of-bounds access. You must only use the pointer returned from malloc to access data inside the allocated range of bytes. You can use pointer arithmetic (or array subscripting) to read and write bytes in the range, but nothing before the beginning or after the end of the range.

Even if they seem simple, C programmers find in practice that these rules are extremely hard to follow consistently. As software gets more complex, it can be hard to keep track of when memory has been freed, when it still needs to be freed, and what to check to ensure that accesses are within bounds. Personally, I think following these rules is the hardest part of programming in C (and C++). And these problems, because they trigger undefined behavior in C, can have extremely serious consequences—not just crashes and misbehavior, but security vulnerabilities.

As an example to illustrate the severity of the problem, a 2019 study by Microsoft found that 70% of all the security vulnerabilities they tracked in their software stemmed from these kinds of memory bugs.

If you still aren’t convinced, you may recall the 2024 CrowdStrike outage last July (2024). Across the globe, approximately 8.5 million machines running Windows crashed and were unable to restart. Many core industries, such as airlines, banks, hospitals, payment systems, and more were affected costing approximately $10 billion. Ultimately, the root cause of the outage was an out-of-bounds read.

Please reflect on the fact that these problems are really only possible in languages like C and C++, where you are responsible for managing the heap yourself. In contrast, Python, Java, OCaml, Rust, and Swift are all memory safe languages, meaning that they manage the heap automatically for you. This is not just a convenience; these languages can rule out out these extremely dangerous memory bugs altogether. While they give up some performance or control to do so, programmers in these languages find these downside to be an acceptable trade-off to avoid the extreme challenge posed by memory bugs.

Catching Memory Bugs

Let’s try writing a program that intentionally violates the laws. Specifically, let’s try adding out-of-bounds reads to our create_exp program:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const float EULER = 2.71828f;
const int COUNT = 10;

// Allocate a new array containing `COUNT` values from an exponential series.
float* create_exp() {
    float* dest = malloc(COUNT * sizeof(float));  // New!
    dest[0] = 1.0f;
    for (int i = 1; i < COUNT; ++i) {
        dest[i] = dest[i - 1] * EULER;
    }
    return dest;
}

// Print the first `count` values in a float array.
void print_floats(float* vals, int count) {
    for (int i = 0; i < count; ++i) {
        printf("%f\n", vals[i]);
    }

    // Let's see what's nearby...
    char* ptr = (char*)vals;
    for (int j = 0; j < 100; ++j) {
        char* byte = ptr - j;
        printf("%p: %d %c\n", byte, *byte, *byte);
    }
}

// Generate a secret.
char* gen_secret() {
    char* secret = malloc(16);
    strcpy(secret, "seekrit!");
    return secret;
}

int main() {
    char* password = gen_secret();
    float* values = create_exp();

    print_floats(values, COUNT);

    free(values);
    free(password);
    return 0;
}

This program takes a pointer to our values array, and it first safely walks forward from there to print out the floats it contains. Then, it does something sneaky: it starts walking backward from the beginning of the array, immediately leaving the range of legal bytes it’s allowed to read.

Because this program violates the laws, it might do anything: it might crash, corrupt memory, or just give nonsense results. But when I ran this on my machine once, it walked all the way into the memory pointed to by password and printed out its contents. Spooky! This kind of out-of-bounds read is the basis for many real-world security vulnerabilities.

Since I’m telling you that these bugs are extremely easy to create, is there any way of catching them? Fortunately, GCC has a built-in mechanism for catching some memory bugs, called sanitizers. To use them, compile your program with the flags -g -fsanitize=address -fsanitize=undefined:

$ gcc -Wall -Wextra -Wpedantic -Wshadow -Wformat=2 -std=c23 -g -fsanitize=address -fsanitize=undefined heap_bug.c -o heap_bug

Sanitizers check your code dynamically, so this won’t print an error at compile time. Try running the resulting code:

$ qemu heap_bug

If everything works, the sanitizer will print out a long, helpful message telling you exactly what the program tried to do.

Crashing with a useful error is a much more helpful thing to do than behave unpredictably. So whenever you suspect your program might have a memory bug, try enabling the sanitizers to check.

Memory Layout

The stack and the heap are both regions in the giant metaphorical array that is memory. Both of them need to grow and shrink dynamically: the program can always malloc more memory on the heap, or it can call another function to push a new frame onto the stack. Computers therefore need to choose carefully where to put these memory segments so they have plenty of room to grow as the program executes.

In general:

• The heap starts at a low memory address and grows upward as the program allocates more memory.
• The stack starts at a high memory address and grows downward as the program calls more functions.

By starting these two segments at opposite “ends” of the address space, this strategy maximizes the amount of room each one has to grow.

There are also other common memory segments. These ones typically have a fixed size, so “room to grow” is not an issue:

• The data segment holds global variables and constants, which exist for the entire duration of the program. Aside from the global variables you declare yourself, string literals from your program go here.
• The text segment contains the program, as machine code instructions. Much more discussion of these instructions is coming in a couple of weeks.

Gates & Logic

Our goal over the next couple of lectures is to build a computer.

Let’s take it back to the beginning: computers are made out of logical switches. In the modern era, these switches are implemented using transistors. But let’s start with relays instead, because they’re easier to think about.

We won’t build a computer in one step. We’re going to use relays to build bigger components, and then think abstractly about what those components do. Then we can forget about the internals, i.e., how we built the thing, and we can build something even bigger out of that. Step by step, we will climb up the latter of abstraction and build a computer.

Truth Tables

To climb the abstraction latter, we need an abstract way to write down the behavior of a circuit element. Our tool for this is a truth table, which exhaustively describes how the circuit’s input and output signals behave in terms of bits.

Logical AND and OR gates have two inputs, A and B, and one output, out.

Recall how relays have a “default on” and a “default off” variant. (The electromagnet repulses or attracts the bendy piece of metal, respectively.) Truth tables are a good way to write down the difference between the variants.

Here is the truth table for a logical OR gate:

Truth tables have one column per input, and they have one row for every combination of input values.

Here’s the truth table for a logical AND gate:

Building Not

Let’s build a not function next. Here’s the truth table:

This circuit is also called an inverter.

Level Up: Building NAND and NOR

It’s important to write down the specification for the function we want. Our specifications will be truth tables. Here’s the truth table for NAND:

There are two inputs, A and B, and one output, NAND. Note that NAND is the opposite of AND; i.e. NAND is the inversion of AND.

Similarly for NOR, there are two inputs, A and B, and one output, NOR. NOR is the opposite of OR; i.e. NOR is the inversion of OR.

Further, XOR and XNOR have inputs A and B, where ouput, XOR is 1 when A and B are not equal and XNOR is 1 when A and B are equal; i.e. XNOR is the inversion of XOR.

Keep Leveling Up

We’re going to keep building larger and more interesting circuits out of smaller ones. This “leveling up” sort of feels like a video game. In fact, people have made video games out of this process! A cool one is Nandgame.

Try using Nandgame to build the circuits we already made. Then, try going farther and making AND and OR circuits.

Logic Notation

It’s going to be helpful to have a notation to write down these logic circuits as we make them more complicated. Here is some common mathy notation that people use to write these operators.

Each of these operators has a visual representation for wiring schematics, but they are too hard to include here. You can see them all on the Wikipedia page for logic gate.

Universal Gates, and a Recipe for Building Anything

Nandgame encourages you to be creative: to think carefully about how to use your “inventory” efficiently to build a new circuit. But there is an easier, more mechanical way that works to build anything: that is, given an arbitrary truth table, this method can give you a circuit.

Here are the steps:

1. Start with a truth table.
2. For every row where the output is 1, write out the minterms. The minterm is the logical expression that is an “and” of all the input variables, either with or without negation, according to the truth value of the given input. For example, if the row in the truth table has $a = 1$ and $b = 0$, then the minterm is $a\overline{b}$. The idea is that the minterm completely describes the input condition where that row is active.
3. Join all the minterms for those output-1 rows with “ors.” This is the sum-of-products expression.

That gives you a logical expression consisting only of not, and, and or that is 1 when the output in the truth table is 1 and 0 otherwise. You can construct a circuit out of these three gates to match the expression.

Because this sum-of-products process works for any truth table, and it only uses those three gates, you can conclude that the combination of and, not and or is all you really need: if you just have those three functions, you can build any other function.

It gets better: you can each all of and, or, and not through a clever combination of only nand gates. You can also build any of them out of just nor gates. (Try it in Nandgame if you want!) That means that, transitively, you can build any circuit out of just nand or just nor. People call these gates universal for that reason.

Practicing Sum-of-Products Constructions

Here are two functions you can build to try out your newfound skills in building arbitrary circuits out of and, or, and not:

1. Try building xnor, i.e., “not xor,” using this technique.
2. A multiplexer (aka a mux or a selector) has three inputs: s for “select,” in₀, and in₁. It has one output, out. When s is 0, out is equal to in₀. When s is 1, out is equal to in₁.

Because the multiplexer has 3 inputs, you will want to use 3-input and and or gates. You can, of course, implement these with a cascade of 2-input gates.

Arithmetic

If this technique really works to build “everything,” let’s try using it build math. Starting with addition.

Half Adder

To keep the circuit small, let’s add two 1-bit numbers.

Let’s start by writing out all the possible combinations, and the sum as a binary value. This is not quite a truth table, because the output is a 2-bit number and not a truth value, but it’s close:

To make this into a truth table, let’s separate the two bits of the output sum—and fill in the implicit 0 in the most significant bit. The normal way to do this is to label the two bits c, for the carry bit, and s, for the sum. The truth table looks like this:

Remember that a and b are the input columns, and c and s are the output columns.

This truth table is a little different from the other ones on this page because it has two outputs. But we can still use the same approach, just one output at a time. That is, we can write the logical formulas for the two outputs separately $c = ab$ and $s = \overline{a}b \vee a\overline{b}$.

It is “fun” to notice that there is another truth table that already matches the behavior of the sum value: namely, $s = a \oplus b$. So we can use two of the gates we built above to make this one-bit adder: an and gate for c and an xor gate for s.

This circuit is usually called a half adder. Why “half”? It’s missing an important feature that we’ll add next.

Full Adder

Adding one-bit numbers is nice, but we would like to add bigger numbers. The insight that will get us there is that, when we do “long addition” of binary numbers, we add up one bit at a time—and possibly “carry the one” to the next column. At each step in this process, we actually need to add three one-bit numbers together: each of the two input bits and—for every bit except the first—the carried bit from the previous column (which may be zero).

So the key to implementing a circuit that does “long addition” is to extend our one-bit adder above to take three inputs instead of two. This thing will be called a full adder. It has three one-bit inputs: $a$, $b$, and $c_{\mathrm{in}}$ for the carry-in bit. Just like the half adder, it has two one-bit outputs: the sum $s$ and the carry-out bit $c_{\mathrm{out}}$.

Try writing out a truth table for this circuit. One useful thing to remember is that, despite $c_{\mathrm{in}}$ having a different-looking name, the three inputs are really indistinguishable: we’re just adding up 3 one-bit numbers here.

We could absolutely use the sum-of-products approach to build the circuit for the full adder. But it turns out that there is a much simpler way to do it by using two half adders and some other logic. Can you build this circuit? You can try skipping to the “full adder” level in Nandgame to try it out.

n-Bit Adder

The full adder is the building block we need to construct an $n$-bit adder, for any $n$: a circuit that takes two $n$-bit numbers and adds them together, producing an $(n+1)$-bit result. You can make this circuit by chaining together a series of $n$ full adders, hooking the $c_{\mathrm{out}}$ of one to the $c_{\mathrm{in}}$ of the next.

By climbing the abstraction ladder, we have gradually gotten from relays, something we can physically understand, all the way to a binary calculator. We don’t have a computer yet, exactly, but we do have something pretty cool.

Binary Subtraction

Two’s complement subtraction works with the same n-bit adder circuit! In particular, subtraction is addition with a negated operand. I.e Negation is done by inverting all bits and adding one: $A - B = A + (-B) = A + (\overline{B} + 1)$

Thus, the n-bit adder works by setting the carry-in input to 1 and invertying the B operand bits.

n-Bit Adder that can add or subtract

Lastly, the n-bit adder can be modified such that it can add or subtract. In particular, the carry-in input is set to 0 for add or 1 for subtract. Then, an XOR gate can be used for the operand B such that it negates B if carry-in is set to subtract.

if subtracting, invert $B_0$

Stateful Logic

The Need for State

So far, we have climbed up the abstraction ladder to build circuits that can do lots of interesting computations on bits. We have an n-bit adder, for example, so maybe you can believe that—using the same principles—we can build more complicated operations: multiplication and even divisor, for example. But I contend that the principles we’ve been using have a fundamental limitation: they are stateless. To build a real computer, we will need a way to store and retrieve information.

To see what I mean by stateless, try inputting a bunch of numbers into an adder (or whatever) in Nandgame. Then, reset all the inputs back to zero. The circuit’s outputs also back down to zero, because they are a function of the current values of the inputs. The circuit has no memory of what happened in the past.

The reason this is a problem is that computers work by iteratively updating stored values, one step at a time. Extending our simplified view of computer architecture, let’s imagine a computer made of three parts:

• The processor logic, with circuits for addition and such.
• The data memory: a mapping from memory addresses to values.
• An instruction: a string of bits that encode some operation for the processor to take, such as “read the values from the data memory at addresses 0xaf and 0x1c and put the result at address 0xe9.”

If the bits of the instruction were exposed via buttons on your machine, you could do computations by sequentially keying in different instructions. The data memory itself clearly needs to be stateful, i.e., to do a thing that our circuits are incapable of so far to keep data around. But let’s pretend that’s someone else’s problem and focus just on the processor for now. Even so, this setup leaves something to be desired: a human would have to manually key in each instruction in sequence. That’s of course not how programs work in real computers; somehow, there’s a way to write a program down up front and then let the computer run through instructions of its own accord.

Let’s extend our architecture diagram with another memory: the instruction memory. This will contain a bunch of bit-strings like our example above, laid out in order. Again, I know this memory itself needs state, but let’s ignore that for now. To make the whole machine work, we will also need a way to keep track of the current instruction we are executing. In real machines, this thing is called the program counter (PC): a stateful element that holds the address in the instruction memory of the currently-executing instruction. This might start out at zero, so we read out the value of the 0th instruction; then, when that instruction is done doing all of its work, we need to increment it to 1 to run the next instruction, and so on.

This program counter needs to be stateful. It needs to keep track of the current value and hold it over time until we decide to change it. Today, we will build circuits that can work like this.