Computer Systems Fundamentals
Course Resources
| Administrivia: | Course Outline | Course Timetable | COMP1521 Handbook | Help Sessions | Hale |
| Meet the Team: | Our Team |
| Platforms: | Lectures (via YouTube) | Tut-Labs (via BbCollaborate) | Course Forum |
| Resources: | COMP1521 C Style Guide | Kernel C Style Guide | Linux Cheatsheet | C Reference |
| MIPS Resources: | MIPS Documentation | Quick Reference Card | Instruction Reference |
| MIPS Resources: | Text Editors for Assembly | MIPS Quick Tutorial | Assembly Style Guide |
| MIPS Resources: | mipsy | mipsy-web | MIPS debugging short video |
| Assessment: | Autotests, Submissions, Marks | Give online: submission | Give online: sturec |
| Assignments: | Assignment 1 | Assignment 2 |
| Past Papers: | Practice Exam (21T3 COMP1521 Final Exam) |
Course Content Week-by-Week
- Tutorial
- Laboratory
- Tuesday Week 1 Lecture Topics
- Wednesday Week 1 Lecture Topics
- Tutorial
- Laboratory
- Tuesday Week 2 Lecture Topics
- Wednesday Week 2 Lecture Topics
- Tutorial
- Laboratory
- Tuesday Week 4 Lecture Topics
- Wednesday Week 4 Lecture Topics
- Tutorial
- Laboratory
- Tuesday Week 5 Lecture Topics
- Wednesday Week 5 Lecture Topics
- Tutorial
- Laboratory
- Tuesday Week 10 Lecture Topics
- Wednesday Week 10 Lecture Topics
Course Content Topic-by-Topic
main:
# ... pass address of string as argument
la $a0, string
# ... 4 is printf "%s" syscall number
li $v0, 4
syscall
li $v0, 0 # return 0
jr $ra
.data
string:
.asciiz "I love MIPS\n"
add 17 and 25 and print result
#include <stdio.h>
int main(void) {
int x = 17;
int y = 25;
printf("%d\n", x + y);
return 0;
}
#include <stdio.h>
int main(void) {
int x, y, z;
x = 17;
y = 25;
z = x + y;
printf("%d", z);
printf("\n");
return 0;
}
add 17 and 25 and print result
main: # x,y,z in $t0,$t1,$t2
li $t0, 17 # x = 17;
li $t1, 25 # y = 25;
add $t2, $t1, $t0 # z = x + y
move $a0, $t2 # printf("%d", z);
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
li $v0, 0 # return 0
jr $ra
print integers 1..10 one per line
#include <stdio.h>
int main(void) {
for (int i = 1; i <= 10; i++) {
printf("%d\n", i);
}
return 0;
}
#include <stdio.h>
int main(void) {
int i;
i = 1;
loop:
if (i > 10) goto end;
i++;
printf("%d", i);
printf("\n");
goto loop;
end:
return 0;
}
print integers 1..10 one per line
main: # int main(void) {
# int i; // in register $t0
li $t0, 1 # i = 1;
loop: # loop:
bgt $t0, 10, end # if (i > 10) goto end;
move $a0, $t0 # printf("%d" i);
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
addi $t0, $t0, 1 # i++;
b loop # goto loop;
end:
li $v0, 0 # return 0
jr $ra
read a number and print whther its odd or even
#include <stdio.h>
int main(void) {
int x;
printf("Enter a number: ");
scanf("%d", &x);
if (x % 2 == 0) {
printf("Even\n");
} else {
printf("Odd\n");
}
return 0;
}
#include <stdio.h>
int main(void) {
int x, v0;
printf("Enter a number: ");
scanf("%d", &x);
v0 = x % 2;
if (v0 == 1) goto odd;
printf("Even\n");
goto end;
odd:
printf("Odd\n");
end:
return 0;
}
read a number and print whether its odd or even
main:
la $a0, string0 # printf("Enter a number: ");
li $v0, 4
syscall
li $v0, 5 # scanf("%d", x);
syscall
rem $t0, $v0, 2 # if (x % 2 == 0) {
beq $t0, 1, odd
la $a0, string1 # printf("Even\n");
li $v0, 4
syscall
b end
odd: # else
la $a0, string2 # printf("Odd\n");
li $v0, 4
syscall
end:
li $v0, 0 # return 0
jr $ra
.data
string0:
.asciiz "Enter a number: "
string1:
.asciiz "Even\n"
string2:
.asciiz "Odd\n"
calculate 1*1 + 2*2 + ... + 99 * 99 + 100 * 100
#include <stdio.h>
int main(void) {
int sum = 0;
for (int i = 0; i <= 100; i++) {
sum += i * i;
}
printf("%d\n", sum);
return 0;
}
#include <stdio.h>
// sum of first 100 squares.
int main(void) {
int i, sum, square;
sum = 0;
i = 0;
loop:
if (i > 100) goto end;
square = i * i;
sum = sum + square;
i = i + 1;
goto loop;
end:
printf("%d", sum);
printf("\n");
return 0;
}
calculate 1*1 + 2*2 + ... + 99 * 99 + 100 * 100
sum in $t0, i in $t1, square in $t2
sum in $t0, i in $t1, square in $t2
main:
li $t0, 0 # sum = 0;
li $t1, 0 # i = 0
loop:
bgt $t1, 100, end # if (i > 100) goto end;
mul $t2, $t1, $t1 # square = i * i;
add $t0, $t0, $t2 # sum = sum + square;
addi $t1, $t1, 1 # i = i + 1;
b loop
end:
move $a0, $t0 # printf("%d", sum);
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
li $v0, 0 # return 0
jr $ra
#include <stdio.h>
int x, y, z;
int main(void) {
x = 17;
y = 25;
z = x + y;
printf("%d", z);
printf("\n");
return 0;
}
add 17 and 25 using variables stored in memory and print result
main:
li $t0, 17 # x = 17;
la $t1, x
sw $t0, 0($t1)
li $t0, 25 # y = 25;
la $t1, y
sw $t0, 0($t1)
la $t0, x
lw $t1, 0($t0)
la $t0, y
lw $t2, 0($t0)
add $t3, $t1, $t2 # z = x + y
la $t0, z
sw $t3, 0($t0)
la $t0, z
lw $a0, 0($t0)
li $v0, 1 # printf("%d", z);
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
li $v0, 0 # return 0
jr $ra
.data
x: .space 4
y: .space 4
z: .space 4
add 17 and 25 using variables stored in memory and print result
main:
la $t0, x
lw $t1, 0($t0)
la $t0, y
lw $t2, 0($t0)
add $t3, $t1, $t2 # z = x + y
la $t0, z
sw $t3, 0($t0)
la $t0, z
lw $a0, 0($t0)
li $v0, 1 # printf("%d", z);
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
li $v0, 0 # return 0
jr $ra
.data
x: .word 17
y: .word 25
z: .space 4
#include <stdio.h>
int x[] = {17,25,0};
int main(void) {
x[2] = x[0] + x[1];
printf("%d", x[2]);
printf("\n");
return 0;
}
add 17 and 25 using variables stored in memory and print result
main:
la $t0, x
lw $t1, 0($t0)
lw $t2, 4($t0)
add $t3, $t1, $t2 # z = x + y
sw $t3, 8($t0)
lw $a0, 8($t0)
li $v0, 1 # printf("%d", z);
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
li $v0, 0 # return 0
jr $ra
.data
# int x[] = {17,25,0}
x: .word 17, 25, 0
#include <stdio.h>
#include <stdint.h>
int main(void) {
uint8_t b;
uint32_t u;
u = 0x03040506;
// load first byte of u
b = *(uint8_t *)&u;
// prints 6 if little-endian
// and 3 if big-endian
printf("%d\n", b);
}
main:
li $t0, 0x03040506
la $t1, u
sw $t0, 0($t1) # u = 0x03040506;
lb $a0, 0($t1) # b = *(uint8_t *)&u;
li $v0, 1 # printf("%d", a0);
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
li $v0, 0 # return 0
jr $ra
.data
u:
.space 4
simple example of accessing an array element
#include <stdio.h>
int x[10];
int main(void) {
x[3] = 17;
}
main:
li $t0, 3
mul $t0, $t0, 4
la $t1, x
add $t2, $t1, $t0
li $t3, 17
sw $t3, ($t2)
# ...
.data
x: .space 40
print array of ints
#include <stdio.h>
int numbers[5] = { 3, 9, 27, 81, 243};
int main(void) {
int i = 0;
while (i < 5) {
printf("%d\n", numbers[i]);
i++;
}
return 0;
}
print array of ints
#include <stdio.h>
int numbers[5] = { 3, 9, 27, 81, 243};
int main(void) {
int i = 0;
loop:
if (i >= 5) goto end;
printf("%d", numbers[i]);
printf("%c", '\n');
i++;
goto loop;
end:
return 0;
}
print array of ints
i in $t0
main:
li $t0, 0 # int i = 0;
loop:
bge $t0, 5, end # if (i >= 5) goto end;
la $t1, numbers # int j = numbers[i];
mul $t2, $t0, 4
add $t3, $t2, $t1
lw $a0, 0($t3) # printf("%d", j);
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
addi $t0, $t0, 1 # i++
b loop # goto loop
end:
li $v0, 0 # return 0
jr $ra
.data
numbers: # int numbers[10] = { 3, 9, 27, 81, 243};
.word 3, 9, 27, 81, 243
print an array using pointers
#include <stdio.h>
int numbers[5] = { 3, 9, 27, 81, 243};
int main(void) {
int *p = &numbers[0];
int *q = &numbers[4];
while (p <= q) {
printf("%d\n", *p);
p++;
}
return 0;
}
print an array using pointers
#include <stdio.h>
int numbers[5] = { 3, 9, 27, 81, 243};
int main(void) {
int *p = &numbers[0];
int *q = &numbers[4];
loop:
if (p > q) goto end;
int j = *p;
printf("%d", j);
printf("%c", '\n');
p++;
goto loop;
end:
return 0;
}
print an array using pointers
p in $t0, q in $t1
main:
la $t0, numbers # int *p = &numbers[0];
la $t0, numbers # int *q = &numbers[4];
addi $t1, $t0, 16 #
loop:
bgt $t0, $t1, end # if (p > q) goto end;
lw $a0, 0($t0) # int j = *p;
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
addi $t0, $t0, 4 # p++
b loop # goto loop
end:
li $v0, 0 # return 0
jr $ra
.data
numbers: # int numbers[10] = { 3, 9, 27, 81, 243};
.word 3, 9, 27, 81, 243
print 5 numbers -
this is closer to the code a compiler might produce
p in $s0
q in $s1
main:
la $s0, numbers # int *p = &numbers[0];
addi $s1, $s0, 16 # int *q = &numbers[4];
loop:
lw $a0, ($s0) # printf("%d", *p);
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
addi $s0, $s0, 4 # p++
ble $s0, $s1, loop # if (p <= q) goto loop;
li $v0, 0 # return 0
jr $ra
.data
numbers: # int numbers[10] = { 3, 9, 27, 81, 243};
.word 3, 9, 27, 81, 243
read 10 numbers into an array then print the 10 numbers
#include <stdio.h>
int numbers[10] = { 0 };
int main(void) {
int i;
i = 0;
while (i < 10) {
printf("Enter a number: ");
scanf("%d", &numbers[i]);
i++;
}
i = 0;
while (i < 10) {
printf("%d\n", numbers[i]);
i++;
}
return 0;
}
read 10 numbers into an array then print the 10 numbers
i in register $s0 registers $t1, $t2 & $t3 used to hold temporary results
i in register $s0 registers $t1, $t2 & $t3 used to hold temporary results
main:
li $s0, 0 # i = 0
loop0:
bge $s0, 10, end0 # while (i < 10) {
la $a0, string0 # printf("Enter a number: ");
li $v0, 4
syscall
li $v0, 5 # scanf("%d", &numbers[i]);
syscall #
mul $t1, $s0, 4 # calculate &numbers[i]
la $t2, numbers #
add $t3, $t1, $t2 #
sw $v0, ($t3) # store entered number in array
addi $s0, $s0, 1 # i++;
b loop0 # }
end0:
li $s0, 0 # i = 0
loop1:
bge $s0, 10, end1 # while (i < 10) {
mul $t1, $s0, 4 # calculate &numbers[i]
la $t2, numbers #
add $t3, $t1, $t2 #
lw $a0, ($t3) # load numbers[i] into $a0
li $v0, 1 # printf("%d", numbers[i])
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
addi $s0, $s0, 1 # i++
b loop1 # }
end1:
li $v0, 0 # return 0
jr $ra
.data
numbers: # int numbers[10];
.word 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
string0:
.asciiz "Enter a number: "
read 10 integers then print them in reverse order
#include <stdio.h>
int numbers[10];
int main() {
int count;
count = 0;
while (count < 10) {
printf("Enter a number: ");
scanf("%d", &numbers[count]);
count++;
}
printf("Reverse order:\n");
count = 9;
while (count >= 0) {
printf("%d\n", numbers[count]);
count--;
}
return 0;
}
read 10 integers then print them in reverse order
count in register $s0 registers $t1 and $t2 used to hold temporary results
count in register $s0 registers $t1 and $t2 used to hold temporary results
main:
li $s0, 0 # count = 0
read:
bge $s0, 10, print # while (count < 10) {
la $a0, string0 # printf("Enter a number: ");
li $v0, 4
syscall
li $v0, 5 # scanf("%d", &numbers[count]);
syscall #
mul $t1, $s0, 4 # calculate &numbers[count]
la $t2, numbers #
add $t1, $t1, $t2 #
sw $v0, ($t1) # store entered number in array
addi $s0, $s0, 1 # count++;
b read # }
print:
la $a0, string1 # printf("Reverse order:\n");
li $v0, 4
syscall
li $s0, 9 # count = 9;
next:
blt $s0, 0, end1 # while (count >= 0) {
mul $t1, $s0, 4 # printf("%d", numbers[count])
la $t2, numbers # calculate &numbers[count]
add $t1, $t1, $t2 #
lw $a0, ($t1) # load numbers[count] into $a0
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
addi $s0, $s0, -1 # count--;
b next # }
end1:
li $v0, 0 # return 0
jr $ra
.data
numbers: # int numbers[10];
.word 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
string0:
.asciiz "Enter a number: "
string1:
.asciiz "Reverse order:\n"
#include <stdio.h>
int
main() {
int i;
int numbers[10];
i = 0;
while (i < 10) {
printf("Enter a number: ");
scanf("%d", &numbers[i]);
i++;
}
i = 0;
while (i < 10) {
numbers[i] *= 42;
i++;
}
i = 0;
while (i < 10) {
printf("%d\n", numbers[i]);
i++;
}
return 0;
}
i in register $s0
registers $s1 and $s2 used to hold temporary results
main:
li $s0, 0 # i = 0
loop0:
bge $s0, 10, end0 # while (i < 10) {
la $a0, string0 # printf("Enter a number: ");
li $v0, 4
syscall
li $v0, 5 # scanf("%d", &numbers[i]);
syscall #
mul $s1, $s0, 4 # calculate &numbers[i]
la $s2, numbers #
add $s1, $s1, $s2 #
sw $v0, ($s1) # store entered number in array
addi $s0, $s0, 1 # i++;
b loop0
end0:
li $s0, 0 # i = 0
loop1:
bge $s0, 10, end1 # while (i < 10) {
mul $s1, $s0, 4 #
la $s2, numbers # calculate &numbers[i]
add $s1, $s1, $s2 #
lw $t0, ($s1) # load numbers[i] into $t0
mul $t0, $t0, 42 # numbers[i] *= 42;
sw $t0, ($s1) # store scaled number in array
addi $s0, $s0, 1 # i++;
b loop1
end1:
li $s0, 0
loop2:
bge $s0, 10, done # while (i < 10) {
mul $s1, $s0, 4 # printf("%d", numbers[i])
la $s2, numbers # calculate &numbers[i]
add $s1, $s1, $s2 #
lw $a0, ($s1) # load numbers[i] into $a0
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
addi $s0, $s0, 1 # i++
b loop2
done:
li $v0, 0 # return 0
jr $ra
.data
numbers:
.space 40 # int numbers[10];
string0:
.asciiz "Enter a number: "
string1:
.asciiz "Reverse order:\n"
print a 2d array
#include <stdio.h>
int numbers[3][5] = {{3,9,27,81,243},{4,16,64,256,1024},{5,25,125,625,3125}};
int main(void) {
int i = 0;
while (i < 3) {
int j = 0;
while (j < 5) {
printf("%d", numbers[i][j]);
printf("%c", ' ');
j++;
}
printf("%c", '\n');
i++;
}
return 0;
}
print a 2d array
#include <stdio.h>
int numbers[3][5] = {{3,9,27,81,243},{4,16,64,256,1024},{5,25,125,625,3125}};
int main(void) {
int i = 0;
loop1:
if (i >= 3) goto end1;
int j = 0;
loop2:
if (j >= 5) goto end2;
printf("%d", numbers[i][j]);
printf("%c", ' ');
j++;
goto loop2;
end2:
printf("%c", '\n');
i++;
goto loop1;
end1:
return 0;
}
print a 2d array
i in $s0
j in $s1
main:
li $s0, 0 # int i = 0;
loop1:
bge $s0, 3, end1 # if (i >= 3) goto end1;
li $s1, 0 # int j = 0;
loop2:
bge $s1, 5, end2 # if (j >= 5) goto end2;
la $t0, numbers # printf("%d", numbers[i][j]);
mul $t1, $s0, 20
add $t2, $t1, $t0
mul $t3, $s1, 4
add $t4, $t3, $t2
lw $a0, 0($t4)
li $v0, 1
syscall
li $a0, ' ' # printf("%c", ' ');
li $v0, 11
syscall
addi $s1, $s1, 1 # j++;
b loop2 # goto loop2;
end2:
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
addi $s0, $s0, 1 # i++
b loop1 # goto loop1
end1:
li $v0, 0 # return 0
jr $ra
.data
# int numbers[3][5] = {{3,9,27,81,243},{4,16,64,256,1024},{5,25,125,625,3125}};
numbers:
.word 3, 9, 27, 81, 243, 4, 16, 64, 256, 1024, 5, 25, 125, 625, 3125
#include <stdio.h>
#include <stdint.h>
int main(void) {
uint8_t bytes[32];
uint32_t *i = (int *)&bytes[1];
// illegal store - not aligned on a 4-byte boundary
*i = 0x03040506;
printf("%d\n", bytes[1]);
}
main:
li $t0, 1
sb $t0, v1 # will succeed because no alignment needed
sh $t0, v1 # will fail because v1 is not 2-byte aligned
sw $t0, v1 # will fail because v1 is not 4-byte aligned
sh $t0, v2 # will succeeed because v2 is 2-byte aligned
sw $t0, v2 # will fail because v2 is not 4-byte aligned
sh $t0, v3 # will succeeed because v3 is 2-byte aligned
sw $t0, v3 # will fail because v3 is not 4-byte aligned
sh $t0, v4 # will succeeed because v4 is 2-byte aligned
sw $t0, v4 # will succeeed because v4 is 4-byte aligned
sw $t0, v5 # will succeeed because v5 is 4-byte aligned
sw $t0, v6 # will succeeed because v6 is 4-byte aligned
li $v0, 0
jr $ra # return
.data
# data will be aligned on a 4-byte boundary
# most likely on at least a 128-byte boundary
# but safer to just add a .align directive
.align 2
.space 1
v1: .space 1
v2: .space 4
v3: .space 2
v4: .space 4
.space 1
.align 2 # ensure e is on a 4 (2**2) byte boundary
v5: .space 4
.space 1
v6: .word 0 # word directive aligns on 4 byte boundary
access fields of a simple struct
#include <stdio.h>
#include <stdint.h>
struct details {
uint16_t postcode;
char first_name[7];
uint32_t zid;
};
struct details student = {2052, "Alice", 5123456};
int main(void) {
printf("%d", student.zid);
putchar(' ');
printf("%s", student.first_name);
putchar(' ');
printf("%d", student.postcode);
putchar('\n');
return 0;
}
struct details {
uint16_t postcode;
char first_name[7];
uint32_t zid;
};
offset in bytes of fields of struct details
offset in bytes of fields of struct details
DETAILS_POSTCODE = 0
DETAILS_FIRST_NAME = 2
DETAILS_ZID = 9
main:
la $t0, student # printf("%d", student.zid);
add $t1, $t0, DETAILS_ZID
lw $a0, ($t1)
li $v0, 1
syscall
li $a0, ' ' # putchar(' ');
li $v0, 11
syscall
la $t0, student # printf("%s", student.first_name);
addi $a0, $t0, DETAILS_FIRST_NAME
li $v0, 4
syscall
li $a0, ' ' # putchar(' ');
li $v0, 11
syscall
la $t0, student # printf("%d", student.postcode);
addi $t1, $t0, DETAILS_POSTCODE
lhu $a0, ($t1)
li $v0, 1
syscall
li $a0, '\n' # putchar('\n');
li $v0, 11
syscall
li $v0, 0 # return 0
jr $ra
.data
student: # struct details student = {2052, "Alice", 5123456};
.half 2052
.asciiz "Andrew"
.word 5123456
access fields of a simple struct
struct details { uint16_t postcode; char first_name[7]; uint32_t zid; };
offset in bytes of fields of struct details
struct details { uint16_t postcode; char first_name[7]; uint32_t zid; };
offset in bytes of fields of struct details
DETAILS_POSTCODE = 0
DETAILS_FIRST_NAME = 2
DETAILS_ZID = 12
main:
la $t0, student # printf("%d", student.zid);
addi $t1, $t0, DETAILS_ZID
lw $a0, ($t1)
li $v0, 1
syscall
li $a0, ' ' # putchar(' ');
li $v0, 11
syscall
la $t0, student # printf("%s", student.first_name);
addi $a0, $t0, DETAILS_FIRST_NAME
li $v0, 4
syscall
li $a0, ' ' # putchar(' ');
li $v0, 11
syscall
la $t0, student # printf("%d", student.postcode);
addi $t1, $t0, DETAILS_POSTCODE
lhu $a0, ($t1)
li $v0, 1
syscall
li $a0, '\n' # putchar('\n');
li $v0, 11
syscall
li $v0, 0 # return 0
jr $ra
.data
student: # struct details student = {2052, "Alice", 5123456};
.half 2052
.asciiz "Andrew"
.space 3 # struct padding to ensure zid field is ona 4-byte boundary
.word 5123456
#include <stdio.h>
#include <stdint.h>
struct s1 {
uint32_t i0;
uint32_t i1;
uint32_t i2;
uint32_t i3;
};
struct s2 {
uint8_t b;
uint64_t l;
};
int main(void) {
struct s1 v1;
printf("&v1 = %p\n", &v1);
printf("&(v1.i0) = %p\n", &(v1.i0));
printf("&(v1.i1) = %p\n", &(v1.i1));
printf("&(v1.i2) = %p\n", &(v1.i2));
printf("&(v1.i3) = %p\n", &(v1.i3));
printf("\nThis shows struct padding\n");
struct s2 v2;
printf("&v2 = %p\n", &v2);
printf("&(v2.b) = %p\n", &(v2.b));
printf("&(v2.l) = %p\n", &(v2.l));
}
$ dcc struct_packing.c -o struct_packing $ ./struct_packing sizeof v1 = 32 sizeof v2 = 20 alignment rules mean struct s1 is padded &(v1.c1) = 0x7ffdfc02f560 &(v1.l1) = 0x7ffdfc02f564 &(v1.c2) = 0x7ffdfc02f568 &(v1.l2) = 0x7ffdfc02f56c struct s2 is not padded &(v2.c1) = 0x7ffdfc02f5a0 &(v2.l1) = 0x7ffdfc02f5a4 $
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
void print_bytes(void *v, int n);
struct s1 {
uint8_t c1;
uint32_t l1;
uint8_t c2;
uint32_t l2;
uint8_t c3;
uint32_t l3;
uint8_t c4;
uint32_t l4;
};
struct s2 {
uint32_t l1;
uint32_t l2;
uint32_t l3;
uint32_t l4;
uint8_t c1;
uint8_t c2;
uint8_t c3;
uint8_t c4;
};
int main(void) {
struct s1 v1;
struct s2 v2;
printf("sizeof v1 = %lu\n", sizeof v1);
printf("sizeof v2 = %lu\n", sizeof v2);
printf("alignment rules mean struct s1 is padded\n");
printf("&(v1.c1) = %p\n", &(v1.c1));
printf("&(v1.l1) = %p\n", &(v1.l1));
printf("&(v1.c2) = %p\n", &(v1.c2));
printf("&(v1.l2) = %p\n", &(v1.l2));
printf("struct s2 is not padded\n");
printf("&(v1.l1) = %p\n", &(v1.l1));
printf("&(v1.l2) = %p\n", &(v1.l2));
printf("&(v1.l4) = %p\n", &(v1.l4));
printf("&(v2.c1) = %p\n", &(v2.c1));
printf("&(v2.c2) = %p\n", &(v2.c2));
}
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main(void) {
double array[10];
for (int i = 0; i < 10; i++) {
printf("&array[%d]=%p\n", i, &array[i]);
}
printf("\nexample computation for address of array element \\n\n");
uintptr_t a = (uintptr_t)&array[0];
printf("&array[0] + 7 * sizeof (double) = 0x%lx\n", a + 7 * sizeof (double));
printf("&array[0] + 7 * %lx = 0x%lx\n", sizeof (double), a + 7 * sizeof (double));
printf("0x%lx + 7 * %lx = 0x%lx\n", a, sizeof (double), a + 7 * sizeof (double));
printf("&array[7] = %p\n", &array[7]);
}
non-portable code illustrating array indexing
this relies on pointers being implemented by memory addresses
which most compiled C implementations do
#include <stdio.h>
#include <stdint.h>
uint32_t array[10] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
int main(void) {
// use a typecast to assign array address to integer variable i
// better than uint64_t would be uintptr_t - an unsigned integer type the same size as a pointer.
uint64_t i = (uint64_t)&array;
i += 7 * sizeof array[0]; // add 28 to i
// use a typecast to assign i to a pointer vaiable
uint32_t *y = (uint32_t *)i;
printf("*y = %d\n", *y); // prints 17
// compare to pointer arithmetic where adding 1
// moves to the next array element
uint32_t *z = array;
z += 7;
printf("*z = %d\n", *z); // prints 17
}
#include <stdio.h>
#define X 3
#define Y 4
int main(void) {
int array[X][Y];
for (int x = 0; x < X; x++) {
for (int y = 0; y < Y; y++) {
array[x][y] = x + y;
}
}
for (int x = 0; x < X; x++) {
for (int y = 0; y < Y; y++) {
printf("%d ", array[x][y]);
}
printf("\n");
}
printf("sizeof array[2][3] = %lu\n", sizeof array[2][3]);
printf("sizeof array[1] = %lu\n", sizeof array[1]);
printf("sizeof array = %lu\n", sizeof array);
printf("&array=%p\n", &array);
for (int x = 0; x < X; x++) {
printf("&array[%d]=%p\n", x, &array[x]);
for (int y = 0; y < Y; y++) {
printf("&array[%d][%d]=%p\n", x, y, &array[x][y]);
}
}
}
non-portable code illustrating 2d-array indexing
this relies on pointers being implemented by memory addresses
which most compiled C implementations do
#include <stdio.h>
#include <stdint.h>
uint32_t array[3][4] = {{10, 11, 12, 13}, {14, 15, 16, 17}, {18, 19, 20, 21}};
int main(void) {
// use a typecast to assign array address to integer variable i
// `uintptr_t': unsigned integer type the same size as a pointer.
int index1 = 1;
int index2 = 2;
printf("array[%d][%d] = %d\n", index1, index2, array[index1][index2]); // prints 16
uint64_t i = (uint64_t)&array;
// i += (index1 * 4 * 4) + index2 * 4
i += (index1 * sizeof array[0]) + index2 * sizeof array[0][0];
// use a typecast to assign i to a pointer vaiable
uint32_t *y = (uint32_t *)i;
printf("*y = %d\n", *y); // prints 16
}
non-portable code illustrating access to a struct field
this relies on pointers being implemented by memory addresses
which most compiled C implementations do
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
struct simple {
char c;
uint32_t i;
double d;
};
struct simple s = { 'Z', 42, 3.14159 };
int main(void) {
// use a typecast to assign struct address to integer variable i
// `uintptr_t': unsigned integer type the same size as a pointer.
uintptr_t i = (uintptr_t)&s;
// 3 bytes of padding - likely but not guaranteed
i += (sizeof s.c) + 3;
// use a typecast to assign i to a pointer vaiable
uint32_t *y = (uint32_t *)i;
printf("*y = %d\n", *y); // prints 42
}
two useful functions that we will use
in a number of following programs
#include <stdio.h>
#include <stdint.h>
#include "print_bits.h"
// extract the nth bit from a value
int get_nth_bit(uint64_t value, int n) {
// shift the bit right n bits
// this leaves the n-th bit as the least significant bit
uint64_t shifted_value = value >> n;
// zero all bits except the the least significant bit
int bit = shifted_value & 1;
return bit;
}
// print the bottom how_many_bits bits of value
void print_bits(uint64_t value, int how_many_bits) {
// print bits from most significant to least significant
for (int i = how_many_bits - 1; i >= 0; i--) {
int bit = get_nth_bit(value, i);
printf("%d", bit);
}
}
C Function with No Parameters or Return Value
#include <stdio.h>
void f(void);
int main(void) {
printf("calling function f\n");
f();
printf("back from function f\n");
return 0;
}
void f(void) {
printf("in function f\n");
}
simple example of returning from a function
loops because main does not save return address
main:
la $a0, string0 # printf("calling function f\n");
li $v0, 4
syscall
jal f # set $ra to following address
la $a0, string1 # printf("back from function f\n");
li $v0, 4
syscall
li $v0, 0 # fails because $ra changes since main called
jr $ra # return from function main
f:
la $a0, string2 # printf("in function f\n");
li $v0, 4
syscall
jr $ra # return from function f
.data
string0:
.asciiz "calling function f\n"
string1:
.asciiz "back from function f\n"
string2:
.asciiz "in function f\n"
simple example of placing return address on stack
note stack grows down
main:
addi $sp, $sp, -4 # move stack pointer down to make room
sw $ra, 0($sp) # save $ra on $stack
la $a0, string0 # printf("calling function f\n");
li $v0, 4
syscall
jal f # set $ra to following address
la $a0, string1 # printf("back from function f\n");
li $v0, 4
syscall
lw $ra, 0($sp) # recover $ra from $stack
addi $sp, $sp, 4 # move stack pointer back to what it was
li $v0, 0 # return 0 from function main
jr $ra #
f:
la $a0, string2 # printf("in function f\n");
li $v0, 4
syscall
jr $ra # return from function f
.data
string0:
.asciiz "calling function f\n"
string1:
.asciiz "back from function f\n"
string2:
.asciiz "in function f\n"
simple example of placing return address on stack
begin, end, push pop are pseudo-instructions provided by mipsy but not spim
main:
push $ra # save $ra on $stack
la $a0, string0 # printf("calling function f\n");
li $v0, 4
syscall
jal f # set $ra to following address
la $a0, string1 # printf("back from function f\n");
li $v0, 4
syscall
pop $ra # recover $ra from $stack
li $v0, 0 # return 0 from function main
jr $ra #
# f is a leaf function so it doesn't need an epilogue or prologue
f:
la $a0, string2 # printf("in function f\n");
li $v0, 4
syscall
jr $ra # return from function f
.data
string0:
.asciiz "calling function f\n"
string1:
.asciiz "back from function f\n"
string2:
.asciiz "in function f\n"
simple example of returning a value from a function
#include <stdio.h>
int answer(void);
int main(void) {
int a = answer();
printf("%d\n", a);
return 0;
}
int answer(void) {
return 42;
}
simple example of returning a value from a function
note storing of return address $ra
code for function main
code for function main
main:
begin # move frame pointer
push $ra # save $ra onto stack
jal answer # call answer(), return value will be in $v0
move $a0, $v0 # printf("%d", a);
li $v0, 1 #
syscall #
li $a0, '\n' # printf("%c", '\n');
li $v0, 11 #
syscall #
pop $ra # recover $ra from stack
end # move frame pointer back
li $v0, 0 # return
jr $ra #
# code for function answer
answer:
li $v0, 42 # return 42
jr $ra #
example of function calls
#include <stdio.h>
int sum_product(int a, int b);
int product(int x, int y);
int main(void) {
int z = sum_product(10, 12);
printf("%d\n", z);
return 0;
}
int sum_product(int a, int b) {
int p = product(6, 7);
return p + a + b;
}
int product(int x, int y) {
return x * y;
}
example of function calls
note storing of return address $a0, $a1 and $ra on stack
main:
begin # move frame pointer
push $ra # save $ra onto stack
li $a0, 10 # sum_product(10, 12);
li $a1, 12
jal sum_product
move $a0, $v0 # printf("%d", z);
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
pop $ra # recover $ra from stack
end # move frame pointer back
li $v0, 0 # return 0 from function main
jr $ra # return from function main
sum_product:
begin # move frame pointer
push $ra # save $ra onto stack
push $a0 # save $a0 onto stack
push $a1 # save $a1 onto stack
li $a0, 6 # product(6, 7);
li $a1, 7
jal product
pop $a1 # recover $a1 from stack
pop $a0 # recover $a0 from stack
add $v0, $v0, $a0 # add a and b to value returned in $v0
add $v0, $v0, $a1 # and put result in $v0 to be returned
pop $ra # recover $ra from stack
end # move frame pointer back
jr $ra # return from sum_product
product: # product doesn't call other functions
# so it doesn't need to save any registers
mul $v0, $a0, $a1 # return argument * argument 2
jr $ra #
recursive function which prints first 20 powers of two in reverse
#include <stdio.h>
void two(int i);
int main(void) {
two(1);
}
void two(int i) {
if (i < 1000000) {
two(2 * i);
}
printf("%d\n", i);
}
simple example of placing return address ($ra) and $a0 on the stack
recursive function which prints first 20 powers of two in reverse
main:
begin # move frame pointer
push $ra # save $ra onto stack
li $a0, 1
jal two # two(1);
pop $ra # recover $ra from stack
end # move frame pointer back
li $v0, 0 # return 0
jr $ra #
two:
begin # move frame pointer
push $ra # save $ra onto stack
push $a0 # save $a0 onto stack
bge $a0, 1000000, two_end_if
mul $a0, $a0, 2
jal two
two_end_if:
pop $a0 # restore $a0 from $stack
li $v0, 1 # printf("%d");
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
pop $ra # recover $ra from stack
end # move frame pointer back
jr $ra # return from two
example of function where frame pointer useful
because stack grows during function execution
#include <stdio.h>
void f(int a) {
int length;
scanf("%d", &length);
int array[length];
// ... more code ...
printf("%d\n", a);
}
example stack growing during function execution
breaking the function return
f:
addi $sp, $sp, -8 # move stack pointer down to make room
sw $ra, 4($sp) # save $ra on $stack
sw $a0, 0($sp) # save $a0 on $stack
li $v0, 5 # scanf("%d", &length);
syscall
mul $v0, $v0, 4 # calculate array size
sub $sp, $sp, $v0 # move stack_pointer down to hold array
# ...
# breaks because stack pointer moved down to hold array
# so we won't restore the correct value
lw $ra, 4($sp) # restore $ra from $stack
addi $sp, $sp, 8 # move stack pointer back up to what it was when main called
jr $ra # return from f
using a frame pointer to handle stack growing during function execution
f:
begin # move frame pointer
push $ra # save $ra on stack
push $a0 # save $a0 on stack
li $v0, 5 # scanf("%d", &length);
syscall
mul $v0, $v0, 4 # calculate array size
sub $sp, $sp, $v0 # move stack_pointer down to hold array
# ... more code ...
pop $a0 # restore $a0
pop $ra # restore $ra
end
jr $ra # return
calculate the length of a string using a strlen like function
#include <stdio.h>
int my_strlen(char *s);
int main(void) {
int i = my_strlen("Hello Andrew");
printf("%d\n", i);
return 0;
}
int my_strlen(char *s) {
int length = 0;
while (*s != 0) {
length++;
s++;
}
return length;
}
simple example of placing return address ($ra) on the stack
calculate the length of a string using a strlen like function
main:
begin # move frame pointer
push $ra # save $ra onto stack
la $a0, string # my_strlen("Hello");
jal my_strlen
move $a0, $v0 # printf("%d", i);
li $v0, 1
syscall
li $a0, '\n' # printf("%c", '\n');
li $v0, 11
syscall
pop $ra # recover $ra from stack
end # move frame pointer back
li $v0, 0 # return 0 from function main
jr $ra #
my_strlen: # length in t0, s in $a0
li $t0, 0
loop: #
lb $t1, ($a0) # load *s into $t1
beq $t1, 0, end #
addi $t0, $t0, 1 # length++
addi $a0, $a0, 1 # s++
b loop #
end:
move $v0, $t0 # return length
jr $ra #
.data
string:
.asciiz "Hello Andrew"
#include <stdio.h>
#include <stdint.h>
/*
$ clang --version
Ubuntu clang version 11.0.0-2~ubuntu20.04.1
$ clang stack_inspect.c
$ a.out
0: Address 0x7ffe7d80defc contains 3 <- e[0]
1: Address 0x7ffe7d80df00 contains 7 <- e[1]
2: Address 0x7ffe7d80df04 contains 5 <- d
3: Address 0x7ffe7d80df08 contains 9 <- c
4: Address 0x7ffe7d80df0c contains 2a <- b
5: Address 0x7ffe7d80df10 contains 7d80df30 <- saved frame pointer of main (lower 32 bits)
6: Address 0x7ffe7d80df14 contains 7ffe <- saved frame pointer of main (upper 32 bits)
7: Address 0x7ffe7d80df18 contains 4011d3 <- saved return address of main (lower 32 bits)
8: Address 0x7ffe7d80df1c contains 0 <- saved return address of main (upper 32 bits)
9: Address 0x7ffe7d80df20 contains 7d80e020 <- STACK pointer (???) (lower 32 bits)
10: Address 0x7ffe7d80df24 contains 7ffe <- STACK pointer (???) (upper 32 bits)
11: Address 0x7ffe7d80df28 contains 9 <- a
12: Address 0x7ffe7d80df2c contains 0 <- padding (for next 64-bit pointer ^)
13: Address 0x7ffe7d80df30 contains 0 <- saved frame pointer of _start (lower 32 bits)
14: Address 0x7ffe7d80df34 contains 0 <- saved frame pointer of _start (upper 32 bits)
15: Address 0x7ffe7d80df38 contains 9fbb30b3 <- saved return address of _start (lower 32 bits)
16: Address 0x7ffe7d80df3c contains 7f98 <- saved return address of _start (upper 32 bits)
17: Address 0x7ffe7d80df40 contains 71 <- ???
18: Address 0x7ffe7d80df44 contains 0 <- ???
19: Address 0x7ffe7d80df48 contains 7d80e028 <- source information
20: Address 0x7ffe7d80df4c contains 7ffe <- source information
$ gcc --version
gcc (Ubuntu 10.3.0-1ubuntu1~20.04) 10.3.0
$ gcc stack_inspect.c
$ a.out # GCC stores local arrays first in the stack, so some things are missing from the start of the output.
9 <- c
2a <- b
<- TEXT pointer (???)
<- TEXT pointer (???)
0 <- padding (for next 64-bit pointer ^)
5 <- d
0: Address 0x7ffccc6e6e90 contains 3 <- e[0]
1: Address 0x7ffccc6e6e94 contains 7 <- e[1]
2: Address 0x7ffccc6e6e98 contains f08e2f00 <- ???
3: Address 0x7ffccc6e6e9c contains 8c526a01 <- ???
4: Address 0x7ffccc6e6ea0 contains cc6e6ec0 <- saved frame pointer of main (lower 32 bits)
5: Address 0x7ffccc6e6ea4 contains 7ffc <- saved frame pointer of main (upper 32 bits)
6: Address 0x7ffccc6e6ea8 contains 11c6a221 <- saved return address of main (lower 32 bits)
7: Address 0x7ffccc6e6eac contains 5582 <- saved return address of main (upper 32 bits)
8: Address 0x7ffccc6e6eb0 contains cc6e6fb0 <- STACK pointer (???) (lower 32 bits)
9: Address 0x7ffccc6e6eb4 contains 7ffc <- STACK pointer (???) (upper 32 bits)
10: Address 0x7ffccc6e6eb8 contains 0 <- padding (for next 64-bit pointer ^)
11: Address 0x7ffccc6e6ebc contains 9 <- a
12: Address 0x7ffccc6e6ec0 contains 0 <- saved frame pointer of _start (lower 32 bits)
13: Address 0x7ffccc6e6ec4 contains 0 <- saved frame pointer of _start (upper 32 bits)
14: Address 0x7ffccc6e6ec8 contains 6f6d70b3 <- saved return address of _start (lower 32 bits)
15: Address 0x7ffccc6e6ecc contains 7fba <- saved return address of _start (upper 32 bits)
16: Address 0x7ffccc6e6ed0 contains 71 <- ???
17: Address 0x7ffccc6e6ed4 contains 0 <- ???
18: Address 0x7ffccc6e6ed8 contains cc6e6fb8 <- source information
19: Address 0x7ffccc6e6edc contains 7ffc <- source information
20: Address 0x7ffccc6e6ee0 contains 6f898618 <- ??? (upper 32 bits)
*/
void f(int b, int c) {
int d = 5;
uint32_t e[2] = { 3, 7 };
for (int i = 0; i < 20; i++)
printf("%2d: Address %p contains %8x\n", i, &e[i], e[0 + i]);
}
int main(void) {
int a = 9;
f(42, a);
return 0;
}
Run at CSE like this
$ clang -Wno-everything invalid0.c -o invalid0 $ ./invalid0 42 77 77 77 77 77 77 77 77 77
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[10];
int b[10];
printf("a[0] is at address %p\n", &a[0]);
printf("a[9] is at address %p\n", &a[9]);
printf("b[0] is at address %p\n", &b[0]);
printf("b[9] is at address %p\n", &b[9]);
for (int i = 0; i < 10; i++) {
a[i] = 77;
}
// loop writes to b[10] .. b[12] which don't exist -
// on CSE servers (clang 7.0 x86_64/Linux)
// b[12] is stored where a[0] is stored
// on CSE servers (clang 7.0 x86_64/Linux)
// b[10] is stored where a[0] is stored
for (int i = 0; i <= 12; i++) {
b[i] = 42;
}
// prints 42 77 77 77 77 77 77 77 77 77 on x86_64/Linux
// prints 42 42 42 77 77 77 77 77 77 77 at CSE
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
Run at CSE like this
$ clang -Wno-everything invalid1.c -o invalid1 $ ./invalid1 i is at address 0x7ffe2c01cd58 a[0] is at address 0x7ffe2c01cd30 a[9] is at address 0x7ffe2c01cd54 a[10] would be stored at address 0x7ffe2c01cd58
doesn't terminate
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int i;
int a[10];
printf("i is at address %p\n", &i);
printf("a[0] is at address %p\n", &a[0]);
printf("a[9] is at address %p\n", &a[9]);
printf("a[10] would be stored at address %p\n", &a[10]);
// loop writes to a[10] .. a[11] which don't exist -
// but on CSE servers (clang 7.0 x86_64/Linux)
// i would be stored where a[11] is stored
for (i = 0; i <= 11; i++) {
a[i] = 0;
}
return 0;
}
Run at CSE like this
$ clang -Wno-everything invalid2.c -o invalid2 $ ./invalid2 answer=42
#include <stdio.h>
void f(int x);
int main(void) {
int answer = 36;
printf("answer is stored at address %p\n", &answer);
f(5);
printf("answer=%d\n", answer); // prints 42 not 36
return 0;
}
void f(int x) {
int a[10];
// a[18] doesn't exist
// on CSE servers (clang 7.0 x86_64/Linux)
// variable answer in main happens to be where a[19] would be
printf("a[18] would be stored at address %p\n", &a[18]);
a[18] = 42;
}
Run at CSE like this
$ clang -Wno-everything invalid3.c -o invalid3 $ ./invalid3
I hate you. $
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
void f(void);
int main(void) {
f();
printf("I love you and will never say,\n");
printf("I hate you.\n");
return 0;
}
void f(void) {
uint64_t a[1];
a[2] += 17;
// function f has it return address on the stack
// the call of function f from main should return to
// the next statement which is: printf("I love you and will never say,\n");
//
// on CSE servers (clang 7.0 x86_64/Linux)
// f's return address is stored where a[12] would be
//
// so changing a[2] changes where the function returns
//
// adding 17 to a[12] happens to cause it to return 2 statements later
// at: printf("I hate you.\n");
}
Run at CSE like this
$ clang invalid4.c -o invalid4 $ ./invalid4 authenticated is at address 0xff94bf44 password is at address 0xff94bf3c
Enter your password: 123456789
Welcome. You are authorized. $
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[]) {
int authenticated = 0;
char password[8];
printf("authenticated is at address %p\n", &authenticated);
printf("password[8] would be at address %p\n", &password[8]);
printf("Enter your password: ");
int i = 0;
int ch = getchar();
while (ch != '\n' && ch != EOF) {
password[i] = ch;
ch = getchar();
i = i + 1;
}
password[i] = '\0';
if (strcmp(password, "buffalo") == 0) {
authenticated = 1;
}
// a password longer than 8 characters will overflow the array password
// on CSE servers (clang 7.0 x86_64/Linux)
// the variable authenticated is at the address where
// where password[8] would be and gets overwritten
//
// This allows access without knowing the correct password
if (authenticated) {
printf("Welcome. You are authorized.\n");
} else {
printf("Welcome. You are unauthorized. Your death will now be implemented.\n");
printf("Welcome. You will experience a tingling sensation and then death. \n");
printf("Remain calm while your life is extracted.\n");
}
return 0;
}
two useful functions that we will use
in a number of following programs
#include <stdio.h>
#include <stdint.h>
#include "print_bits.h"
// extract the nth bit from a value
int get_nth_bit(uint64_t value, int n) {
// shift the bit right n bits
// this leaves the n-th bit as the least significant bit
uint64_t shifted_value = value >> n;
// zero all bits except the the least significant bit
int bit = shifted_value & 1;
return bit;
}
// print the bottom how_many_bits bits of value
void print_bits(uint64_t value, int how_many_bits) {
// print bits from most significant to least significant
for (int i = how_many_bits - 1; i >= 0; i--) {
int bit = get_nth_bit(value, i);
printf("%d", bit);
}
}
Demonstrate that shifting the bits of a positive int left 1 position is equivalent to multiplying by 2
``` $ dcc shift_as_multiply.c print_bits.c -o shift_as_multiply $ ./shift_as_multiply 4 2 to the power of 4 is 16
In binary it is: 00000000000000000000000000010000 $ ./shift_as_multiply 20 2 to the power of 20 is 1048576
In binary it is: 00000000000100000000000000000000 $ ./shift_as_multiply 31 2 to the power of 31 is 2147483648
In binary it is: 10000000000000000000000000000000 $ ```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include "print_bits.h"
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s <exponent>\n", argv[0]);
return 1;
}
int n = strtol(argv[1], NULL, 0);
uint32_t power_of_two;
int n_bits = 8 * sizeof power_of_two;
if (n >= n_bits) {
fprintf(stderr, "n is too large\n");
return 1;
}
power_of_two = 1;
power_of_two = power_of_two << n;
printf("2 to the power of %d is %u\n", n, power_of_two);
printf("In binary it is: ");
print_bits(power_of_two, n_bits);
printf("\n");
return 0;
}
Demonstrate use shift operators and subtraction to obtain a bit pattern of n 1s
``` $ dcc set_low_bits.c print_bits.c -o n_ones $ ./set_low_bits 3
The bottom 3 bits of 7 are ones: 00000000000000000000000000000111 $ ./set_low_bits 19
The bottom 19 bits of 524287 are ones: 00000000000001111111111111111111 $ ./set_low_bits 29
The bottom 29 bits of 536870911 are ones: 00011111111111111111111111111111 ```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include "assert.h"
#include "print_bits.h"
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s <exponent>\n", argv[0]);
return 1;
}
int n = strtol(argv[1], NULL, 0);
uint32_t mask;
int n_bits = 8 * sizeof mask;
assert(n >= 0 && n < n_bits);
mask = 1;
mask = mask << n;
mask = mask - 1;
printf("The bottom %d bits of %u are ones:\n", n, mask);
print_bits(mask, n_bits);
printf("\n");
return 0;
}
Demonstrate use shift operators and subtraction to obtain a bit pattern with a range of bits set.
``` $ dcc set_bit_range.c print_bits.c -o set_bit_range $ ./set_bit_range 0 7
Bits 0 to 7 of 255 are ones: 00000000000000000000000011111111 $ ./set_bit_range 8 15
Bits 8 to 15 of 65280 are ones: 00000000000000001111111100000000 $ ./set_bit_range 8 23
Bits 8 to 23 of 16776960 are ones: 00000000111111111111111100000000 $ ./set_bit_range 1 30
Bits 1 to 30 of 2147483646 are ones: 01111111111111111111111111111110 ```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include "print_bits.h"
int main(int argc, char *argv[]) {
if (argc != 3) {
fprintf(stderr, "Usage: %s <low-bit> <high-bit>\n", argv[0]);
return 1;
}
int low_bit = strtol(argv[1], NULL, 0);
int high_bit = strtol(argv[2], NULL, 0);
uint32_t mask;
int n_bits = 8 * sizeof mask;
assert(low_bit >= 0);
assert(high_bit >= low_bit);
assert(high_bit < n_bits);
int mask_size = high_bit - low_bit + 1;
mask = 1;
mask = mask << mask_size;
mask = mask - 1;
mask = mask << low_bit;
printf("Bits %d to %d of %u are ones:\n", low_bit, high_bit, mask);
print_bits(mask, n_bits);
printf("\n");
return 0;
}
Demonstrate use shift operators and subtraction to extract a bit pattern with a range of bits set.
``` $ dcc extract_bit_range.c print_bits.c -o extract_bit_range $ ./extract_bit_range 4 7 42
Value 42 in binary is: 00000000000000000000000000101010
Bits 4 to 7 of 42 are: 0010 $ ./extract_bit_range 10 20 123456789
Value 123456789 in binary is: 00000111010110111100110100010101
Bits 10 to 20 of 123456789 are: 11011110011 ```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include "print_bits.h"
int main(int argc, char *argv[]) {
if (argc != 4) {
fprintf(stderr, "Usage: %s <low-bit> <high-bit> <value>\n", argv[0]);
return 1;
}
int low_bit = strtol(argv[1], NULL, 0);
int high_bit = strtol(argv[2], NULL, 0);
uint32_t value = strtol(argv[3], NULL, 0);
uint32_t mask;
int n_bits = 8 * sizeof mask;
assert(low_bit >= 0);
assert(high_bit >= low_bit);
assert(high_bit < n_bits);
int mask_size = high_bit - low_bit + 1;
mask = 1;
mask = mask << mask_size;
mask = mask - 1;
mask = mask << low_bit;
// get a value with the bits outside the range low_bit..high_bit set to zero
uint32_t extracted_bits = value & mask;
// right shift the extracted_bits so low_bit becomes bit 0
extracted_bits = extracted_bits >> low_bit;
printf("Value %u in binary is:\n", value);
print_bits(value, n_bits);
printf("\n");
printf("Bits %d to %d of %u are:\n", low_bit, high_bit, value);
print_bits(extracted_bits, mask_size);
printf("\n");
return 0;
}
Print an integer in hexadecimal without using printf to demonstrate using bitwise operators to extract digits
``` $ dcc print_int_in_hex.c -o print_int_in_hex $ ./print_int_in_hex
Enter a positive int: 42 42 = 0x0000002A $ ./print_int_in_hex
Enter a positive int: 65535 65535 = 0x0000FFFF $ ./print_int_in_hex
Enter a positive int: 3735928559 3735928559 = 0xDEADBEEF $ ```
#include <stdio.h>
#include <stdint.h>
void print_hex(uint32_t n);
int main(void) {
uint32_t a = 0;
printf("Enter a positive int: ");
scanf("%u", &a);
printf("%u = 0x", a);
print_hex(a);
printf("\n");
return 0;
}
// print n in hexadecimal
void print_hex(uint32_t n) {
// sizeof returns number of bytes in n's representation
// each byte is 2 hexadecimal digits
int n_hex_digits = 2 * (sizeof n);
// print hex digits from most significant to least significant
for (int which_digit = n_hex_digits - 1; which_digit >= 0; which_digit--) {
// shift value across so hex digit we want
// is in bottom 4 bits
int bit_shift = 4 * which_digit;
uint32_t shifted_value = n >> bit_shift;
// mask off (zero) all bits but the bottom 4 bites
int hex_digit = shifted_value & 0xF;
// hex digit will be a value 0..15
// obtain the corresponding ASCII value
// "0123456789ABCDEF" is a char array
// containing the appropriate ASCII values (+ a '\0')
int hex_digit_ascii = "0123456789ABCDEF"[hex_digit];
putchar(hex_digit_ascii);
}
}
Convert an integer to a string of hexadecimal digits without using snprintf to demonstrate using bitwise operators to extract digits
``` $ dcc int_to_hex_string.c -o int_to_hex_string $ ./int_to_hex_string $ ./int_to_hex_string
Enter a positive int: 42 42 = 0x0000002A $ ./int_to_hex_string
Enter a positive int: 65535 65535 = 0x0000FFFF $ ./int_to_hex_string
Enter a positive int: 3735928559 3735928559 = 0xDEADBEEF $ ```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
char *int_to_hex_string(uint32_t n);
int main(void) {
uint32_t a = 0;
printf("Enter a positive int: ");
scanf("%u", &a);
char *hex_string = int_to_hex_string(a);
// print the returned string
printf("%u = 0x%s\n", a, hex_string);
free(hex_string);
return 0;
}
// return a malloced string containing the hexadecimal digits of n
char *int_to_hex_string(uint32_t n) {
// sizeof returns number of bytes in n's representation
// each byte is 2 hexadecimal digits
int n_hex_digits = 2 * (sizeof n);
// allocate memory to hold the hex digits + a terminating 0
char *string = malloc(n_hex_digits + 1);
// print hex digits from most significant to least significant
for (int which_digit = 0; which_digit < n_hex_digits; which_digit++) {
// shift value across so hex digit we want
// is in bottom 4 bits
int bit_shift = 4 * which_digit;
uint32_t shifted_value = n >> bit_shift;
// mask off (zero) all bits but the bottom 4 bites
int hex_digit = shifted_value & 0xF;
// hex digit will be a value 0..15
// obtain the corresponding ASCII value
// "0123456789ABCDEF" is a char array
// containing the appropriate ASCII values
int hex_digit_ascii = "0123456789ABCDEF"[hex_digit];
int string_position = n_hex_digits - which_digit - 1;
string[string_position] = hex_digit_ascii;
}
// 0 terminate the array
string[n_hex_digits] = 0;
return string;
}
Convert a hexadecimal string to an integer
``` $ dcc hex_string_to_int.c -o hex_string_to_int $ dcc hex_string_to_int.c -o hex_string_to_int $ ./hex_string_to_int 2A 2A hexadecimal is 42 base 10 $ ./hex_string_to_int FFFF
FFFF hexadecimal is 65535 base 10 $ ./hex_string_to_int DEADBEEF
DEADBEEF hexadecimal is 3735928559 base 10 $ ```
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
uint32_t hex_string_to_int(char *hex_string);
int hex_digit_to_int(int ascii_digit);
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s <hexadecimal-number>\n", argv[0]);
return 1;
}
char *hex_string = argv[1];
uint32_t u = hex_string_to_int(hex_string);
printf("%s hexadecimal is %u base 10\n", hex_string, u);
return 0;
}
uint32_t hex_string_to_int(char *hex_string) {
uint32_t value = 0;
for (int i = 0; hex_string[i] != 0; i++) {
int ascii_hex_digit = hex_string[i];
int digit_as_int = hex_digit_to_int(ascii_hex_digit);
value = value << 4;
value = value | digit_as_int;
}
return value;
}
// given the ascii value of a hexadecimal digit
// return the corresponding integer
int hex_digit_to_int(int ascii_digit) {
if (ascii_digit >= '0' && ascii_digit <= '9') {
// the ASCII characters '0' .. '9' are contiguous
// in other words they have consecutive values
// so subtract the ASCII value for '0' yields the corresponding integer
return ascii_digit - '0';
}
if (ascii_digit >= 'A' && ascii_digit <= 'F') {
// for characters 'A' .. 'F' obtain the
// corresponding integer for a hexadecimal digit
return 10 + (ascii_digit - 'A');
}
fprintf(stderr, "Bad digit '%c'\n", ascii_digit);
exit(1);
}
Examples of illegal bit-shift operations
#include <stdio.h>
#include <stdint.h>
int main(void) {
// int16_t is a signed type (-32768..32767)
// below operations are undefined for a signed type
int16_t i;
i = -1;
i = i >> 1; // undefined - shift of a negative value
printf("%d\n", i);
i = -1;
i = i << 1; // undefined - shift of a negative value
printf("%d\n", i);
i = 32767;
i = i << 1; // undefined - left shift produces a negative value
uint64_t j;
j = 1 << 33; // undefined - constant 1 is an int
j = ((uint64_t)1) << 33; // ok
return 0;
}
copy stdin to stdout xor'ing each byte with value given as argument
``` $ echo Hello Andrew|xor 42 bOFFE kDNXO] $ echo Hello Andrew|xor 42|cat -A bOFFE$ kDNXO] $ $ echo Hello |xor 42 bOFFE $ echo -n 'bOFFE '|xor 42
Hello $ echo Hello|xor 123|xor 123
Hello $ ```
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s <xor-value>\n", argv[0]);
return 1;
}
int xor_value = strtol(argv[1], NULL, 0);
if (xor_value < 0 || xor_value > 255) {
fprintf(stderr, "Usage: %s <xor-value>\n", argv[0]);
return 1;
}
int c;
while ((c = getchar()) != EOF) {
// exclusive-or
// ^ | 0 1
// ----|-----
// 0 | 0 1
// 1 | 1 0
int xor_c = c ^ xor_value;
putchar(xor_c);
}
return 0;
}
Represent a small set of possible values using bits
``` $ dcc pokemon.c print_bits.c -o pokemon $ ./pokemon 0000010000000000 BUG_TYPE 0000000000010000 POISON_TYPE 1000000000000000 FAIRY_TYPE 1000010000010000 our_pokemon type (1)
Poisonous 1001010000000000 our_pokemon type (2)
Scary ```
#include <stdio.h>
#include <stdint.h>
#include "print_bits.h"
#define POKEMON_TYPE_BITS 16
#define FIRE_TYPE 0x0001
#define FIGHTING_TYPE 0x0002
#define WATER_TYPE 0x0004
#define FLYING_TYPE 0x0008
#define POISON_TYPE 0x0010
#define ELECTRIC_TYPE 0x0020
#define GROUND_TYPE 0x0040
#define PSYCHIC_TYPE 0x0080
#define ROCK_TYPE 0x0100
#define ICE_TYPE 0x0200
#define BUG_TYPE 0x0400
#define DRAGON_TYPE 0x0800
#define GHOST_TYPE 0x1000
#define DARK_TYPE 0x2000
#define STEEL_TYPE 0x4000
#define FAIRY_TYPE 0x8000
int main(void) {
// example code to create a pokemon with 3 types
uint16_t our_pokemon = BUG_TYPE | POISON_TYPE | FAIRY_TYPE;
print_bits(BUG_TYPE, POKEMON_TYPE_BITS);
printf(" BUG_TYPE\n");
print_bits(POISON_TYPE, POKEMON_TYPE_BITS);
printf(" POISON_TYPE\n");
print_bits(FAIRY_TYPE, POKEMON_TYPE_BITS);
printf(" FAIRY_TYPE\n");
print_bits(our_pokemon, POKEMON_TYPE_BITS);
printf(" our_pokemon type (1)\n");
// example code to check if a pokemon is of a type:
if (our_pokemon & POISON_TYPE) {
printf("Poisonous\n"); // prints
}
if (our_pokemon & GHOST_TYPE) {
printf("Scary\n"); // does not print
}
// example code to add a type to a pokemon
our_pokemon |= GHOST_TYPE;
// example code to remove a type from a pokemon
our_pokemon &= ~ POISON_TYPE;
print_bits(our_pokemon, POKEMON_TYPE_BITS);
printf(" our_pokemon type (2)\n");
if (our_pokemon & POISON_TYPE) {
printf("Poisonous\n"); // does not print
}
if (our_pokemon & GHOST_TYPE) {
printf("Scary\n"); // prints
}
return 0;
}
Represent set of small non-negative integers using bit-operations
``` $ dcc bitset.c print_bits.c -o bitset $ ./bitset
Set members can be 0-63, negative number to finish
Enter set a: 1 2 4 8 16 32 -1
Enter set b: 5 4 3 33 -1 a = 0000000000000000000000000000000100000000000000010000000100010110 = 0x100010116 = 4295033110 b = 0000000000000000000000000000001000000000000000000000000000111000 = 0x200000038 = 8589934648 a = {1,2,4,8,16,32} b = {3,4,5,33} a union b = {1,2,3,4,5,8,16,32,33} a intersection b = {4} cardinality(a) = 6 is_member(42, a) = 0 ```
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include "print_bits.h"
typedef uint64_t set;
#define MAX_SET_MEMBER ((int)(8 * sizeof(set) - 1))
#define EMPTY_SET 0
set set_add(int x, set a);
set set_union(set a, set b);
set set_intersection(set a, set b);
int set_member(int x, set a);
int set_cardinality(set a);
set set_read(char *prompt);
void set_print(char *description, set a);
void print_bits_hex(char *description, set n);
int main(void) {
printf("Set members can be 0-%d, negative number to finish\n",
MAX_SET_MEMBER);
set a = set_read("Enter set a: ");
set b = set_read("Enter set b: ");
print_bits_hex("a = ", a);
print_bits_hex("b = ", b);
set_print("a = ", a);
set_print("b = ", b);
set_print("a union b = ", set_union(a, b));
set_print("a intersection b = ", set_intersection(a, b));
printf("cardinality(a) = %d\n", set_cardinality(a));
printf("is_member(42, a) = %d\n", (int)set_member(42, a));
return 0;
}
set set_add(int x, set a) {
return a | ((set)1 << x);
}
set set_union(set a, set b) {
return a | b;
}
set set_intersection(set a, set b) {
return a & b;
}
// return 1 iff x is a member of a, 0 otherwise
int set_member(int x, set a) {
assert(x >= 0 && x < MAX_SET_MEMBER);
return (a >> x) & 1;
}
// return size of set
int set_cardinality(set a) {
int n_members = 0;
while (a != 0) {
n_members += a & 1;
a >>= 1;
}
return n_members;
}
set set_read(char *prompt) {
printf("%s", prompt);
set a = EMPTY_SET;
int x;
while (scanf("%d", &x) == 1 && x >= 0) {
a = set_add(x, a);
}
return a;
}
// print out member of the set in increasing order
// for example {5,11,56}
void set_print(char *description, set a) {
printf("%s", description);
printf("{");
int n_printed = 0;
for (int i = 0; i < MAX_SET_MEMBER; i++) {
if (set_member(i, a)) {
if (n_printed > 0) {
printf(",");
}
printf("%d", i);
n_printed++;
}
}
printf("}\n");
}
// print description then binary, hex and decimal representation of value
void print_bits_hex(char *description, set value) {
printf("%s", description);
print_bits(value, 8 * sizeof value);
printf(" = 0x%08jx = %jd\n", (intmax_t)value, (intmax_t)value);
}
Print size and min and max values of floating point types
``` $ ./floating_types float 4 bytes min=1.17549e-38 max=3.40282e+38 double 8 bytes min=2.22507e-308 max=1.79769e+308 long double 16 bytes min=3.3621e-4932 max=1.18973e+4932 ```
#include <stdio.h>
#include <float.h>
int main(void) {
float f;
double d;
long double l;
printf("float %2lu bytes min=%-12g max=%g\n", sizeof f, FLT_MIN, FLT_MAX);
printf("double %2lu bytes min=%-12g max=%g\n", sizeof d, DBL_MIN, DBL_MAX);
printf("long double %2lu bytes min=%-12Lg max=%Lg\n", sizeof l, LDBL_MIN, LDBL_MAX);
return 0;
}
#include <stdio.h>
#include <math.h>
int main(void) {
double x = 1.0/0.0;
printf("%lf\n", x); //prints inf
printf("%lf\n", -x); //prints -inf
printf("%lf\n", x - 1); // prints inf
printf("%lf\n", 2 * atan(x)); // prints 3.141593
printf("%d\n", 42 < x); // prints 1 (true)
printf("%d\n", x == INFINITY); // prints 1 (true)
return 0;
}
#include <stdio.h>
#include <math.h>
int main(void) {
double x = 0.0/0.0;
printf("%lf\n", x); //prints nan
printf("%lf\n", x - 1); // prints nan
printf("%d\n", x == x); // prints 0 (false)
printf("%d\n", isnan(x)); // prints 1 (true)
return 0;
}
The value 0.1 can not be precisely represented as a double
As a result b != 0
#include <stdio.h>
int main(void) {
double a, b;
a = 0.1;
b = 1 - (a + a + a + a + a + a + a + a + a + a);
if (b != 0) { // better would be fabs(b) > 0.000001
printf("1 != 0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1\n");
}
printf("b = %g\n", b); // prints 1.11022e-16
return 0;
}
Demonstrate approximate representation of reals producing error. sometimes if we subtract or divide two approximations which are very close together we can can get a large relative error correct answer if x == 0.000000011 (1 - cos(x)) / (x * x) is very close to 0.5 code prints 0.917540 which is wrong by a factor of almost two
#include <stdio.h>
#include <math.h>
int main(void) {
double x = 0.000000011;
double y = (1 - cos(x)) / (x * x);
// correct answer y = ~0.5
// prints y = 0.917540
printf("y = %lf\n", y);
// division of similar approximate value
// produces large error
// sometimes called catastrophic cancellation
printf("%g\n", 1 - cos(x)); // prints 1.11022e-16
printf("%g\n", x * x); // prints 1.21e-16
return 0;
}
- 9007199254740993 is $2^{53} + 1$ \
it is smallest integer which can not be represented exactly as a double
- The closest double to 9007199254740993 is 9007199254740992.0
- aside: 9007199254740993 can not be represented by a int32_t \
it can be represented by int64_t
#include <stdio.h>
int main(void) {
// loop looks to print 10 numbers but actually never terminates
double d = 9007199254740990;
while (d < 9007199254741000) {
printf("%lf\n", d); // always prints 9007199254740992.000000
// 9007199254740993 can not be represented as a double
// closest double is 9007199254740992.0
// so 9007199254740992.0 + 1 = 9007199254740992.0
d = d + 1;
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/*```
$ dcc double_not_always.c -o double_not_always
$ ./double_not_always 42.3
d = 42.3
d == d is true
d == d + 1 is false
$ ./double_not_always 4200000000000000000
d = 4.2e+18
d == d is true
d == d + 1 is true
$ ./double_not_always NaN
d = nan
d == d is not true
d == d + 1 is false
````*/
int main(int argc, char *argv[]) {
assert(argc == 2);
double d = strtod(argv[1], NULL);
printf("d = %g\n", d);
if (d == d) {
printf("d == d is true\n");
} else {
// will be executed if d is a NaN
printf("d == d is not true\n");
}
if (d == d + 1) {
// may be executed if d is large
// because closest possible representation for d + 1
// is also closest possible representation for d
printf("d == d + 1 is true\n");
} else {
printf("d == d + 1 is false\n");
}
return 0;
}
Print the underlying representation of a float
The float can be supplied as a decimal or a bit-string
$ dcc explain_float_representation.c -o explain_float_representation $ ./explain_float_representation
0.15625 is represented in IEEE-754 single-precision by these bits:
00111110001000000000000000000000
sign | exponent | fraction 0 | 01111100 | 01000000000000000000000
sign bit = 0 sign = +
raw exponent = 01111100 binary = 124 decimal actual exponent = 124 - exponent_bias = 124 - 127 = -3
number = +1.01000000000000000000000 binary * 2**-3 = 1.25 decimal * 2**-3 = 1.25 * 0.125 = 0.15625
$ ./explain_float_representation -0.125
-0.125 is represented as a float (IEEE-754 single-precision) by these bits:
10111110000000000000000000000000
sign | exponent | fraction 1 | 01111100 | 00000000000000000000000
sign bit = 1 sign = -
raw exponent = 01111100 binary = 124 decimal actual exponent = 124 - exponent_bias = 124 - 127 = -3
number = -1.00000000000000000000000 binary * 2**-3 = -1 decimal * 2**-3 = -1 * 0.125 = -0.125
$ ./explain_float_representation 150.75
150.75 is represented in IEEE-754 single-precision by these bits:
01000011000101101100000000000000
sign | exponent | fraction 0 | 10000110 | 00101101100000000000000
sign bit = 0 sign = +
raw exponent = 10000110 binary = 134 decimal actual exponent = 134 - exponent_bias = 134 - 127 = 7
number = +1.00101101100000000000000 binary * 2**7 = 1.17773 decimal * 2**7 = 1.17773 * 128 = 150.75
$ ./explain_float_representation -96.125
-96.125 is represented in IEEE-754 single-precision by these bits:
11000010110000000100000000000000
sign | exponent | fraction 1 | 10000101 | 10000000100000000000000
sign bit = 1 sign = -
raw exponent = 10000101 binary = 133 decimal actual exponent = 133 - exponent_bias = 133 - 127 = 6
number = -1.10000000100000000000000 binary * 2**6 = -1.50195 decimal * 2**6 = -1.50195 * 64 = -96.125
$ ./explain_float_representation inf
inf is represented in IEEE-754 single-precision by these bits:
01111111100000000000000000000000
sign | exponent | fraction 0 | 11111111 | 00000000000000000000000
sign bit = 0 sign = +
raw exponent = 11111111 binary = 255 decimal number = +inf
$ ./explain_float_representation 00111101110011001100110011001101 sign bit = 0 sign = +
raw exponent = 01111011 binary = 123 decimal actual exponent = 123 - exponent_bias = 123 - 127 = -4
number = +1.10011001100110011001101 binary * 2**-4 = 1.6 decimal * 2**-4 = 1.6 * 0.0625 = 0.1
$ ./explain_float_representation 01111111110000000000000000000000 sign bit = 0 sign = +
raw exponent = 11111111 binary = 255 decimal number = NaN $ ```
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#include <float.h>
#include <string.h>
void display_float(char *argument);
uint32_t get_float_bits(float f);
void print_float_bits(uint32_t bits);
void print_bit_range(uint32_t value, int high, int low);
void print_float_details(uint32_t bits);
uint32_t extract_bit_range(uint32_t value, int high, int low);
uint32_t convert_bitstring_to_uint32(char *bit_string);
int main(int argc, char *argv[]) {
for (int arg = 1; arg < argc; arg++) {
display_float(argv[arg]);
}
return 0;
}
// Define the constants used in representation of a float in IEEE 754 single-precision
// https://en.wikipedia.org/wiki/Single-precision_floating-point_format
// explains format
#define N_BITS 32
#define SIGN_BIT 31
#define EXPONENT_HIGH_BIT 30
#define EXPONENT_LOW_BIT 23
#define FRACTION_HIGH_BIT 22
#define FRACTION_LOW_BIT 0
#define EXPONENT_OFFSET 127
#define EXPONENT_INF_NAN 255
void display_float(char *argument) {
uint32_t bits;
// is this argument a bit string or a float?
if (strlen(argument) > N_BITS - 4 && strspn(argument, "01") == N_BITS) {
bits = convert_bitstring_to_uint32(argument);
} else {
float number = strtof(argument, NULL);
bits = get_float_bits(number);
printf("\n%s is represented as IEEE-754 single-precision by these bits:\n\n", argument);
print_float_bits(bits);
}
print_float_details(bits);
}
void print_float_details(uint32_t bits) {
uint32_t sign_bit = extract_bit_range(bits, SIGN_BIT, SIGN_BIT);
uint32_t fraction_bits = extract_bit_range(bits, FRACTION_HIGH_BIT, FRACTION_LOW_BIT);
uint32_t exponent_bits = extract_bit_range(bits, EXPONENT_HIGH_BIT, EXPONENT_LOW_BIT);
int sign_char, sign_value;
if (sign_bit == 1) {
sign_char = '-';
sign_value = -1;
} else {
sign_char = '+';
sign_value = 1;
}
int exponent = exponent_bits - EXPONENT_OFFSET;
printf("sign bit = %d\n", sign_bit);
printf("sign = %c\n\n", sign_char);
printf("raw exponent = ");
print_bit_range(bits, EXPONENT_HIGH_BIT, EXPONENT_LOW_BIT);
printf(" binary\n");
printf(" = %d decimal\n", exponent_bits);
int implicit_bit = 1;
// handle special cases of +infinity, -infinity
// and Not a Number (NaN)
if (exponent_bits == EXPONENT_INF_NAN) {
if (fraction_bits == 0) {
printf("number = %cinf\n\n", sign_char);
} else {
// https://en.wikipedia.org/wiki/NaN
printf("number = NaN\n\n");
}
return;
}
if (exponent_bits == 0) {
// if the exponent_bits are zero its a special case
// called a denormal number
// https://en.wikipedia.org/wiki/Denormal_number
implicit_bit = 0;
exponent++;
}
printf("actual exponent = %d - exponent_bias\n", exponent_bits);
printf(" = %d - %d\n", exponent_bits, EXPONENT_OFFSET);
printf(" = %d\n\n", exponent);
printf("number = %c%d.", sign_char, implicit_bit);
print_bit_range(bits, FRACTION_HIGH_BIT, FRACTION_LOW_BIT);
printf(" binary * 2**%d\n", exponent);
int fraction_size = FRACTION_HIGH_BIT - FRACTION_LOW_BIT + 1;
double fraction_max = ((uint32_t)1) << fraction_size;
double fraction = implicit_bit + fraction_bits / fraction_max;
fraction *= sign_value;
printf(" = %g decimal * 2**%d\n", fraction, exponent);
printf(" = %g * %g\n", fraction, exp2(exponent));
printf(" = %g\n\n", fraction * exp2(exponent));
}
union overlay_float {
float f;
uint32_t u;
};
// return the raw bits of a float
uint32_t get_float_bits(float f) {
union overlay_float overlay;
overlay.f = f;
return overlay.u;
}
// print out the bits of a float
void print_float_bits(uint32_t bits) {
print_bit_range(bits, 8 * sizeof bits - 1, 0);
printf("\n\n");
printf("sign | exponent | fraction\n");
printf(" ");
print_bit_range(bits, SIGN_BIT, SIGN_BIT);
printf(" | ");
print_bit_range(bits, EXPONENT_HIGH_BIT, EXPONENT_LOW_BIT);
printf(" | ");
print_bit_range(bits, FRACTION_HIGH_BIT, FRACTION_LOW_BIT);
printf("\n\n");
}
// print the binary representation of a value
void print_bit_range(uint32_t value, int high, int low) {
for (int i = high; i >= low; i--) {
int bit = extract_bit_range(value, i, i);
printf("%d", bit);
}
}
// extract a range of bits from a value
uint32_t extract_bit_range(uint32_t value, int high, int low) {
uint32_t mask = (((uint32_t)1) << (high - low + 1)) - 1;
return (value >> low) & mask;
}
// given a string of 1s and 0s return the correspong uint32_t
uint32_t convert_bitstring_to_uint32(char *bit_string) {
uint32_t bits = 0;
for (int i = 0; i < N_BITS && bit_string[i] != '\0'; i++) {
int ascii_char = bit_string[N_BITS - 1 - i];
uint32_t bit = ascii_char != '0';
bits = bits | (bit << i);
}
return bits;
}
#include <stdio.h>
int main(void) {
printf("The unicode code point U+1F600 encodes in UTF-8\n");
printf("as 4 bytes: 0xF0 0x9F 0x98 0x80\n");
printf("We can output the 4 bytes like this: \xF0\x9F\x98\x80\n");
printf("Or like this: ");
putchar(0xF0);
putchar(0x9F);
putchar(0x98);
putchar(0x80);
putchar('\n');
}
#include <stdio.h>
#include <stdint.h>
void print_utf8_encoding(uint32_t code_point) {
uint8_t encoding[5] = {0};
if (code_point < 0x80) {
encoding[0] = code_point;
} else if (code_point < 0x800) {
encoding[0] = 0xC0 | (code_point >> 6);
encoding[1] = 0x80 | (code_point & 0x3f);
} else if (code_point < 0x10000) {
encoding[0] = 0xE0 | (code_point >> 12);
encoding[1] = 0x80 | ((code_point >> 6) & 0x3f);
encoding[2] = 0x80 | (code_point & 0x3f);
} else if (code_point < 0x200000) {
encoding[0] = 0xF0 | (code_point >> 18);
encoding[1] = 0x80 | ((code_point >> 12) & 0x3f);
encoding[2] = 0x80 | ((code_point >> 6) & 0x3f);
encoding[3] = 0x80 | (code_point & 0x3f);
}
printf("U+%x UTF-8: ", code_point);
for (uint8_t *s = encoding; *s != 0; s++) {
printf("0x%02x ", *s);
}
printf(" %s\n", encoding);
}
int main(void) {
print_utf8_encoding(0x42);
print_utf8_encoding(0x00A2);
print_utf8_encoding(0x10be);
print_utf8_encoding(0x1F600);
}
hello world implemented with a direct syscall
This isn't portable or readable but shows us what system calls look like.
This isn't portable or readable but shows us what system calls look like.
#include <unistd.h>
int main(void) {
char bytes[13] = "Hello, Zac!\n";
// argument 1 to syscall is the system call number, 1 is write
// remaining arguments are specific to each system call
// write system call takes 3 arguments:
// 1) file descriptor, 1 == stdout
// 2) memory address of first byte to write
// 3) number of bytes to write
syscall(1, 1, bytes, 12); // prints Hello, Zac! on stdout
return 0;
}
#include <unistd.h>
#define O_RDONLY 00
#define O_WRONLY 01
#define O_CREAT 0100
// cp <file1> <file2> with syscalls and no error handling
int main(int argc, char *argv[]) {
// system call number 2 is open, takes 3 arguments:
// 1) address of zero-terminated string containing file pathname
// 2) bitmap indicating whether to write, read, ... file
// O_WRONLY | O_CREAT == 0x41 == write to file, creating if necessary
// 3) permissions if file will be newly created
// 0644 == readable to everyone, writeable by owner
long read_file_descriptor = syscall(2, argv[1], O_RDONLY, 0);
long write_file_descriptor = syscall(2, argv[2], O_WRONLY | O_CREAT, 0644);
while (1) {
// system call number 0 is read - takes 3 arguments:
// 1) file descriptor
// 2) memory address to put bytes read
// 3) maximum number of bytes read
// returns number of bytes actually read
char bytes[4096];
long bytes_read = syscall(0, read_file_descriptor, bytes, 4096);
if (bytes_read <= 0) {
break;
}
// system call number 1 is write - takes 3 arguments:
// 1) file descriptor
// 2) memory address to take bytes from
// 3) number of bytes to written
// returns number of bytes actually written
syscall(1, write_file_descriptor, bytes, bytes_read);
}
return 0;
}
hello world implemented with libc
#include <unistd.h>
int main(void) {
char bytes[13] = "Hello, Zac!\n";
// write takes 3 arguments:
// 1) file descriptor, 1 == stdout
// 2) memory address of first byte to write
// 3) number of bytes to write
write(1, bytes, 12); // prints Hello, Zac! on stdout
return 0;
}
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
// cp <file1> <file2> implemented with libc and no error handling
int main(int argc, char *argv[]) {
// open takes 3 arguments:
// 1) address of zero-terminated string containing pathname of file to open
// 2) bitmap indicating whether to write, read, ... file
// 3) permissions if file will be newly created
// 0644 == readable to everyone, writeable by owner
int read_file_descriptor = open(argv[1], O_RDONLY);
int write_file_descriptor = open(argv[2], O_WRONLY | O_CREAT, 0644);
while (1) {
// read takes 3 arguments:
// 1) file descriptor
// 2) memory address to put bytes read
// 3) maximum number of bytes read
// returns number of bytes actually read
char bytes[4096];
ssize_t bytes_read = read(read_file_descriptor, bytes, 4096);
if (bytes_read <= 0) {
break;
}
// write takes 3 arguments:
// 1) file descriptor
// 2) memory address to take bytes from
// 3) number of bytes to written
// returns number of bytes actually written
write(write_file_descriptor, bytes, bytes_read);
}
// good practice to close file descriptions as soon as finished using them
// not necessary needed here as program about to exit
close(read_file_descriptor);
close(write_file_descriptor);
return 0;
}
6 ways to print Hello, stdio!
#include <stdio.h>
int main(void) {
char bytes[] = "Hello, stdio!\n"; // 15 bytes
// write 14 bytes so we don't write (terminating) 0 byte
for (int i = 0; i < (sizeof bytes) - 1; i++) {
fputc(bytes[i], stdout);
}
// or as we know bytes is 0-terminated
for (int i = 0; bytes[i] != '\0'; i++) {
fputc(bytes[i], stdout);
}
// or if you prefer pointers
for (char *p = &bytes[0]; *p != '\0'; p++) {
fputc(*p, stdout);
}
// fputs relies on bytes being 0-terminated
fputs(bytes, stdout);
// write 14 1 byte items
fwrite(bytes, 1, (sizeof bytes) - 1, stdout);
// %s relies on bytes being 0-terminated
fprintf(stdout, "%s", bytes);
return 0;
}
create file "hello.txt" containing 1 line: Hello, Zac!
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
FILE *output_stream = fopen("hello.txt", "w");
if (output_stream == NULL) {
perror("hello.txt");
return 1;
}
fprintf(output_stream, "Hello, Zac!\n");
// fclose will flush data to file, best to close file ASAP
// optional here as fclose occurs automatically on exit
fclose(output_stream);
return 0;
}
cp <file1> <file2>
implemented with fgetc
#include <stdio.h>
int main(int argc, char *argv[]) {
if (argc != 3) {
fprintf(stderr, "Usage: %s <source file> <destination file>\n", argv[0]);
return 1;
}
FILE *input_stream = fopen(argv[1], "rb");
if (input_stream == NULL) {
perror(argv[1]); // prints why the open failed
return 1;
}
FILE *output_stream = fopen(argv[2], "wb");
if (output_stream == NULL) {
perror(argv[2]);
return 1;
}
int c; // not char!
while ((c = fgetc(input_stream)) != EOF) {
fputc(c, output_stream);
}
fclose(input_stream); // optional here as fclose occurs
fclose(output_stream); // automatically on exit
return 0;
}
cp <file1> <file2>
implemented with libc and *zero* error handling
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int main(int argc, char *argv[]) {
// copy bytes one at a time from pathname passed as
// command-line argument 1 to pathname given as argument 2
int read_file_descriptor = open(argv[1], O_RDONLY);
int write_file_descriptor = open(argv[2], O_WRONLY | O_CREAT, 0644);
while (1) {
char bytes[1];
ssize_t bytes_read = read(read_file_descriptor, bytes, 1);
if (bytes_read <= 0) {
break;
}
write(write_file_descriptor, bytes, 1);
}
return 0;
}
$ dcc create_append_truncate_fopen.c
$ ./a.out
open("hello.txt", "w") -> -rw-r--r-- 1 andrewt andrewt 0 Oct 22 19:11 hello.txt
fputs("Hello, Andrew!\n") -> -rw-r--r-- 1 andrewt andrewt 0 Oct 22 19:11 hello.txt
fclose -> -rw-r--r-- 1 andrewt andrewt 15 Oct 22 19:11 hello.txt
fopen("hello.txt", "a") -> -rw-r--r-- 1 andrewt andrewt 15 Oct 22 19:11 hello.txt
fputs("Hello again, Andrew!\n") -> -rw-r--r-- 1 andrewt andrewt 15 Oct 22 19:11 hello.txt
fflush -> -rw-r--r-- 1 andrewt andrewt 36 Oct 22 19:11 hello.txt
open("hello.txt", "w") -> -rw-r--r-- 1 andrewt andrewt 0 Oct 22 19:11 hello.txt
fputs("Good Bye Andrew!\n") -> -rw-r--r-- 1 andrewt andrewt 0 Oct 22 19:11 hello.txt
assa:files% ./a.out
open("hello.txt", "w") -> -rw-r--r-- 1 andrewt andrewt 0 Oct 22 19:12 hello.txt
fputs("Hello, Andrew!\n") -> -rw-r--r-- 1 andrewt andrewt 0 Oct 22 19:12 hello.txt
fclose -> -rw-r--r-- 1 andrewt andrewt 15 Oct 22 19:12 hello.txt
fopen("hello.txt", "a") -> -rw-r--r-- 1 andrewt andrewt 15 Oct 22 19:12 hello.txt
fputs("Hello again, Andrew!\n") -> -rw-r--r-- 1 andrewt andrewt 15 Oct 22 19:12 hello.txt
fflush -> -rw-r--r-- 1 andrewt andrewt 36 Oct 22 19:12 hello.txt
open("hello.txt", "w") -> -rw-r--r-- 1 andrewt andrewt 0 Oct 22 19:12 hello.txt
fputs("Good Bye Andrew!\n") -> -rw-r--r-- 1 andrewt andrewt 0 Oct 22 19:12 hello.txt
$ ls -l hello.txt
-rw-r--r-- 1 andrewt andrewt 17 Oct 22 19:12 hello.txt
$ cat hello.txt
Good Bye Andrew!
$
#include <stdio.h>
#include <stdlib.h>
void show_file_state(char *message);
int main(int argc, char *argv[]) {
FILE *output_stream1 = fopen("hello.txt", "w"); // no error checking
// hello.txt will be created if it doesn't exist already
// if hello.txt previous existed it will now contain 0 bytes
show_file_state("open(\"hello.txt\", \"w\")");
fputs("Hello, Andrew!\n", output_stream1);
// the 15 bytes in "Hello, Andrew!\n" are buffered by the stdio library
// they haven't been written to hello.txt
// so it will still contain 0 bytes
show_file_state("fputs(\"Hello, Andrew!\\n\")");
fclose(output_stream1);
// The fclose will flush the buffered bytes to hello.txt
// hello.txt will now contain 15 bytes
show_file_state("fclose()");
FILE *output_stream2 = fopen("hello.txt", "a"); // no error checking
// because "a" was specified hello.txt will not be changed
// it will still contain 15 bytes
show_file_state("fopen(\"hello.txt\", \"a\")");
fputs("Hello again, Andrew!\n", output_stream2);
// the 21 bytes in "Hello again, Andrew!\n" are buffered by the stdio library
// they haven't been written to hello.txt
// so it will still contain 15 bytes
show_file_state("fputs(\"Hello again, Andrew!\\n\")");
fflush(output_stream2);
// The fflush will flush ahe buffered bytes to hello.txt
// hello.txt will now contain 36 bytes
show_file_state("fflush()");
FILE *output_stream3 = fopen("hello.txt", "w"); // no error checking
// because "w" was specified hello.txt will be truncated to zero length
// hello.txt will now contain 0 bytes
show_file_state("open(\"hello.txt\", \"w\")");
fputs("Good Bye Andrew!\n", output_stream3);
// the 17 bytes in "Good Bye Andrew!\" are buffered by the stdio library
// they haven't been written to hello.txt
// so it will still contain 0 bytes
show_file_state("fputs(\"Good Bye Andrew!\\n\")");
// if exit is called or main returns stdio flushes all stream
// this will leave hello.txt with 17 bytes
// but if a program terminates abnormally this doesn't happen
return 0;
}
void show_file_state(char *message) {
printf("%-32s -> ", message);
fflush(stdout);
system("ls -l hello.txt");
}
use fseek to access diferent bytes of a file with no error checking
the return value of the calls to fopen, fseek and fgetc should be checked to see if they worked!
the return value of the calls to fopen, fseek and fgetc should be checked to see if they worked!
#include <stdio.h>
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s <source file>\n", argv[0]);
return 1;
}
FILE *input_stream = fopen(argv[1], "rb");
// move to a position 1 byte from end of file
// then read 1 byte
fseek(input_stream, -1, SEEK_END);
printf("last byte of the file is 0x%02x\n", fgetc(input_stream));
// move to a position 0 bytes from start of file
// then read 1 byte
fseek(input_stream, 0, SEEK_SET);
printf("first byte of the file is 0x%02x\n", fgetc(input_stream));
// move to a position 41 bytes from start of file
// then read 1 byte
fseek(input_stream, 41, SEEK_SET);
printf("42nd byte of the file is 0x%02x\n", fgetc(input_stream));
// move to a position 58 bytes from current position
// then read 1 byte
fseek(input_stream, 58, SEEK_CUR);
printf("100th byte of the file is 0x%02x\n", fgetc(input_stream));
return 0;
}
use fseek to change a random bit in a file
the return value of the calls to fopen, fseek and fgetc
should be checked to see if they worked!
there
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "Usage: %s <source file>\n", argv[0]);
return 1;
}
FILE *f = fopen(argv[1], "r+"); // open for reading and writing
fseek(f, 0, SEEK_END); // move to end of file
long n_bytes = ftell(f); // get number of bytes in file
srandom(time(NULL)); // initialize random number
// generator with current time
long target_byte = random() % n_bytes; // pick a random byte
fseek(f, target_byte, SEEK_SET); // move to byte
int byte = fgetc(f); // read byte
int bit = random() % 8; // pick a random bit
int new_byte = byte ^ (1 << bit); // flip the bit
fseek(f, -1, SEEK_CUR); // move back to same position
fputc(new_byte, f); // write the byte
fclose(f);
printf("Changed byte %ld of %s from %02x to %02x\n",target_byte, argv[1], byte, new_byte);
return 0;
}
call stat on each command line argument as simple example of its use
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>
#include <stdlib.h>
void stat_file(char *pathname);
int main(int argc, char *argv[]) {
for (int arg = 1; arg < argc; arg++) {
stat_file(argv[arg]);
}
return 0;
}
void stat_file(char *pathname) {
printf("stat(\"%s\", &s)\n", pathname);
struct stat s;
if (stat(pathname, &s) != 0) {
perror(pathname);
exit(1);
}
printf("ino = %10ld # Inode number\n", s.st_ino);
printf("mode = %10o # File mode \n", s.st_mode);
printf("nlink =%10ld # Link count \n", (long)s.st_nlink);
printf("uid = %10u # Owner uid\n", s.st_uid);
printf("gid = %10u # Group gid\n", s.st_gid);
printf("size = %10ld # File size (bytes)\n", (long)s.st_size);
printf("mtime =%10ld # Modification time (seconds since 1/1/70)\n",
(long)s.st_mtime);
}
$ dcc mkdir.c $ ./a.out new_dir $ ls -ld new_dir drwxr-xr-x 2 z5555555 z5555555 60 Oct 29 16:28 new_dir $
#include <stdio.h>
#include <sys/stat.h>
// create the directories specified as command-line arguments
int main(int argc, char *argv[]) {
for (int arg = 1; arg < argc; arg++) {
if (mkdir(argv[arg], 0755) != 0) {
perror(argv[arg]); // prints why the mkdir failed
return 1;
}
}
return 0;
}
$ dcc list_directory.c $ ./a.out . list_directory.c a.out . .. $
#include <stdio.h>
#include <dirent.h>
// list the contents of directories specified as command-line arguments
int main(int argc, char *argv[]) {
for (int arg = 1; arg < argc; arg++) {
DIR *dirp = opendir(argv[arg]);
if (dirp == NULL) {
perror(argv[arg]); // prints why the open failed
return 1;
}
struct dirent *de;
while ((de = readdir(dirp)) != NULL) {
printf("%ld %s\n", de->d_ino, de->d_name);
}
closedir(dirp);
}
return 0;
}
$ dcc chmod.c $ ls -l chmod.c -rw-r--r-- 1 z5555555 z5555555 746 Nov 4 08:20 chmod.c $ ./a.out 600 chmod.c $ ls -l chmod.c -rw------- 1 z5555555 z5555555 787 Nov 4 08:22 chmod.c $ ./a.out 755 chmod.c chmod.c 755 $ ls -l chmod.c -rwxr-xr-x 1 z5555555 z5555555 787 Nov 4 08:22 chmod.c $
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
// change permissions of the specified files
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Usage: %s <mode> <files>\n", argv[0]);
return 1;
}
char *end;
// first argument is mode in octal
mode_t mode = strtol(argv[1], &end, 8);
// check first argument was a valid octal number
if (argv[1][0] == '\0' || end[0] != '\0') {
fprintf(stderr, "%s: invalid mode: %s\n", argv[0], argv[1]);
return 1;
}
for (int arg = 2; arg < argc; arg++) {
if (chmod(argv[arg], mode) != 0) {
perror(argv[arg]); // prints why the chmod failed
return 1;
}
}
return 0;
}
$ dcc rm.c $ ./a.out rm.c $ ls -l rm.c ls: cannot access 'rm.c': No such file or directory $
#include <stdio.h>
#include <unistd.h>
// remove the specified files
int main(int argc, char *argv[]) {
for (int arg = 1; arg < argc; arg++) {
if (unlink(argv[arg]) != 0) {
perror(argv[arg]); // prints why the unlink failed
return 1;
}
}
return 0;
}
broken attempt to implement cd
chdir() affects only this process and any it runs
#include <unistd.h>
#include <stdio.h>
int main(int argc, char *argv[]) {
if (argc > 1 && chdir(argv[1]) != 0) {
perror("chdir");
return 1;
}
return 0;
}
getcwd and chdir example
#include <unistd.h>
#include <limits.h>
#include <stdio.h>
#include <string.h>
int main(void) {
// use repeated chdir("..") to climb to root of the file system
char pathname[PATH_MAX];
while (1) {
if (getcwd(pathname, sizeof pathname) == NULL) {
perror("getcwd");
return 1;
}
printf("getcwd() returned %s\n", pathname);
if (strcmp(pathname, "/") == 0) {
return 0;
}
if (chdir("..") != 0) {
perror("chdir");
return 1;
}
}
return 0;
}
$ dcc rename.c $ ./a.out rename.c renamed.c $ ls -l renamed.c renamed.c $
#include <stdio.h>
// rename the specified file
int main(int argc, char *argv[]) {
if (argc != 3) {
fprintf(stderr, "Usage: %s <old-filename> <new-filename>\n",
argv[0]);
return 1;
}
char *old_filename = argv[1];
char *new_filename = argv[2];
if (rename(old_filename, new_filename) != 0) {
fprintf(stderr, "%s rename %s %s:", argv[0], old_filename,
new_filename);
perror("");
return 1;
}
return 0;
}
silly program which creates a 1000-deep directory hierarchy
#include <stdio.h>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <limits.h>
int main(void) {
for (int i = 0; i < 1000;i++) {
char dirname[256];
snprintf(dirname, sizeof dirname, "d%d", i);
if (mkdir(dirname, 0755) != 0) {
perror(dirname);
return 1;
}
if (chdir(dirname) != 0) {
perror(dirname);
return 1;
}
char pathname[1000000];
if (getcwd(pathname, sizeof pathname) == NULL) {
perror("getcwd");
return 1;
}
printf("\nCurrent directory now: %s\n", pathname);
}
return 0;
}
silly program which create a 1000 links to file
in effect there are 1001 names for the file
#include <stdio.h>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <limits.h>
#include <string.h>
int main(int argc, char *argv[]) {
char pathname[256] = "hello.txt";
// create a target file
FILE *f1;
if ((f1 = fopen(pathname, "w")) == NULL) {
perror(pathname);
return 1;
}
fprintf(f1, "Hello Andrew!\n");
fclose(f1);
for (int i = 0; i < 1000; i++) {
printf("Verifying '%s' contains: ", pathname);
FILE *f2;
if ((f2 = fopen(pathname, "r")) == NULL) {
perror(pathname);
return 1;
}
int c;
while ((c = fgetc(f2)) != EOF) {
fputc(c, stdout);
}
fclose(f2);
char new_pathname[256];
snprintf(new_pathname, sizeof new_pathname,
"hello_%d.txt", i);
printf("Creating a link %s -> %s\n",
new_pathname, pathname);
if (link(pathname, new_pathname) != 0) {
perror(pathname);
return 1;
}
}
return 0;
}
$ dcc spawn.c $ a.out
Tue 3 Nov 23:51:27 UTC 2022 /bin/date exit status was 0
simple example of posix_spawn run date --utc to print current UTC
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <spawn.h>
#include <sys/wait.h>
int main(void) {
pid_t pid;
extern char **environ;
char *date_argv[] = {"/bin/date", "--utc", NULL};
// spawn "/bin/date" as a separate process
if (posix_spawn(&pid, "/bin/date", NULL, NULL, date_argv, environ) != 0) {
perror("spawn");
exit(1);
}
// wait for spawned processes to finish
int exit_status;
if (waitpid(pid, &exit_status, 0) == -1) {
perror("waitpid");
exit(1);
}
printf("/bin/date exit status was %d\n", exit_status);
return 0;
}
$ dcc fork.c $ a.out
I am the parent because fork() returned 2884551.
I am the child because fork() returned 0. $
#include <stdio.h>
#include <unistd.h>
int main(void) {
// fork creates 2 identical copies of program
// only return value is different
pid_t pid = fork();
if (pid == -1) {
perror("fork"); // print why the fork failed
} else if (pid == 0) {
printf("I am the child because fork() returned %d.\n", pid);
} else {
printf("I am the parent because fork() returned %d.\n", pid);
}
return 0;
}
$ dcc exec.c $ a.out good-bye cruel world $
#include <stdio.h>
#include <unistd.h>
// simple example of program replacing itself with exec
int main(void) {
char *echo_argv[] = {"/bin/echo","good-bye","cruel","world",NULL};
execv("/bin/echo", echo_argv);
// if we get here there has been an error
perror("execv");
return 1;
}
simple example of classic fork/exec
run date --utc to print current UTC
use posix_spawn instead
use posix_spawn instead
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <spawn.h>
#include <sys/wait.h>
int main(void) {
pid_t pid = fork();
if (pid == -1) {
perror("fork"); // print why fork failed
} else if (pid == 0) { // child
char *date_argv[] = {"/bin/date", "--utc", NULL};
execv("/bin/date", date_argv);
perror("execvpe"); // print why exec failed
} else { // parent
int exit_status;
if (waitpid(pid, &exit_status, 0) == -1) {
perror("waitpid");
exit(1);
}
printf("/bin/date exit status was %d\n", exit_status);
}
return 0;
}
simple example of system
#include <stdio.h>
#include <stdlib.h>
int main(void) {
// system passes string to a shell for evaluation
// brittle and highly vulnerable to security exploits
// system is suitable for quick debugging and throw-away programs only
// run date --utc to print current UTC
int exit_status = system("/bin/date --utc");
printf("/bin/date exit status was %d\n", exit_status);
return 0;
}
spawn ls -ld adding as argument the arguments we have been given
#include <stdio.h>
#include <stdlib.h>
#include <spawn.h>
#include <sys/wait.h>
int main(int argc, char *argv[]) {
char *ls_argv[argc + 2];
ls_argv[0] = "/bin/ls";
ls_argv[1] = "-ld";
for (int i = 1; i <= argc; i++) {
ls_argv[i + 1] = argv[i];
}
pid_t pid;
extern char **environ;
if (posix_spawn(&pid, "/bin/ls", NULL, NULL, ls_argv, environ) != 0) {
perror("spawn");
exit(1);
}
int exit_status;
if (waitpid(pid, &exit_status, 0) == -1) {
perror("waitpid");
exit(1);
}
// exit with whatever status ls exited with
return exit_status;
}
spawn ls -ld adding as argument the arguments we have been given
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[]) {
char *ls = "/bin/ls -ld";
int command_length = strlen(ls);
for (int i = 1; i < argc; i++) {
command_length += strlen(argv[i]) + 1;
}
// create command as string
char command[command_length + 1];
strcpy(command, ls);
for (int i = 1; i <= argc; i++) {
strcat(command, " ");
strcat(command, argv[i]);
}
int exit_status = system(command);
return exit_status;
}
print all environment variables
#include <stdio.h>
int main(void) {
// print all environment variables
extern char **environ;
for (int i = 0; environ[i] != NULL; i++) {
printf("%s\n", environ[i]);
}
}
$ dcc get_status.c -o get_status $ STATUS=ok ./get_status
Environment variable 'STATUS' has value 'ok' $
#include <stdio.h>
#include <stdlib.h>
// simple example of accessing an environment variable
int main(void) {
// print value of environment variable STATUS
char *value = getenv("STATUS");
printf("Environment variable 'STATUS' has value '%s'\n", value);
return 0;
}
$ dcc set_status.c -o set_status $ dcc get_status.c -o get_status $ ./set_status
Environment variable 'STATUS' has value 'great' $
#include <stdio.h>
#include <stdlib.h>
#include <spawn.h>
#include <sys/wait.h>
// simple example of setting an environment variable
int main(void) {
// set environment variable STATUS
setenv("STATUS", "great", 1);
char *getenv_argv[] = {"./get_status", NULL};
pid_t pid;
extern char **environ;
if (posix_spawn(&pid, "./get_status", NULL, NULL,
getenv_argv, environ) != 0) {
perror("spawn");
exit(1);
}
int exit_status;
if (waitpid(pid, &exit_status, 0) == -1) {
perror("waitpid");
exit(1);
}
// exit with whatever status s exited with
return exit_status;
}
simple example of using environment variableto change program behaviour
run date -to print time
Perth time printed, due to TZ environment variable
Perth time printed, due to TZ environment variable
#include <stdio.h>
#include <unistd.h>
#include <spawn.h>
#include <sys/wait.h>
int main(void) {
pid_t pid;
char *date_argv[] = { "/bin/date", NULL };
char *date_environment[] = { "TZ=Australia/Perth", NULL };
// print time in Perth
if (posix_spawn(&pid, "/bin/date", NULL, NULL, date_argv,
date_environment) != 0) {
perror("spawn");
return 1;
}
int exit_status;
if (waitpid(pid, &exit_status, 0) == -1) {
perror("waitpid");
return 1;
}
printf("/bin/date exit status was %d\n", exit_status);
return 0;
}
simple example using a pipe with posix_spawn
to capture output from spawned process
#include <stdio.h>
#include <unistd.h>
#include <spawn.h>
#include <sys/wait.h>
int main(void) {
// create a pipe
int pipe_file_descriptors[2];
if (pipe(pipe_file_descriptors) == -1) {
perror("pipe");
return 1;
}
// create a list of file actions to be carried out on spawned process
posix_spawn_file_actions_t actions;
if (posix_spawn_file_actions_init(&actions) != 0) {
perror("posix_spawn_file_actions_init");
return 1;
}
// tell spawned process to close unused read end of pipe
// without this - spawned process would not receive EOF
// when read end of the pipe is closed below,
if (posix_spawn_file_actions_addclose(&actions, pipe_file_descriptors[0]) != 0) {
perror("posix_spawn_file_actions_init");
return 1;
}
// tell spawned process to replace file descriptor 1 (stdout)
// with write end of the pipe
if (posix_spawn_file_actions_adddup2(&actions, pipe_file_descriptors[1], 1) != 0) {
perror("posix_spawn_file_actions_adddup2");
return 1;
}
pid_t pid;
extern char **environ;
char *date_argv[] = {"/bin/date", "--utc", NULL};
if (posix_spawn(&pid, "/bin/date", &actions, NULL, date_argv, environ) != 0) {
perror("spawn");
return 1;
}
// close unused write end of pipe
// in some case processes will deadlock without this
// not in this case, but still good practice
close(pipe_file_descriptors[1]);
// create a stdio stream from read end of pipe
FILE *f = fdopen(pipe_file_descriptors[0], "r");
if (f == NULL) {
perror("fdopen");
return 1;
}
// read a line from read-end of pipe
char line[256];
if (fgets(line, sizeof line, f) == NULL) {
fprintf(stderr, "no output from date\n");
return 1;
}
printf("output captured from /bin/date was: '%s'\n", line);
// close read-end of the pipe
// spawned process will now receive EOF if attempts to read input
fclose(f);
int exit_status;
if (waitpid(pid, &exit_status, 0) == -1) {
perror("waitpid");
return 1;
}
printf("/bin/date exit status was %d\n", exit_status);
// free the list of file actions
posix_spawn_file_actions_destroy(&actions);
return 0;
}
simple example of use to popen to capture output from a process
#include <stdio.h>
#include <stdlib.h>
int main(void) {
// popen passes string to a shell for evaluation
// brittle and highly-vulnerable to security exploits
// popen is suitable for quick debugging and throw-away programs only
FILE *p = popen("/bin/date --utc", "r");
if (p == NULL) {
perror("");
return 1;
}
char line[256];
if (fgets(line, sizeof line, p) == NULL) {
fprintf(stderr, "no output from date\n");
return 1;
}
printf("output captured from /bin/date was: '%s'\n", line);
pclose(p); // returns command exit status
return 0;
}
simple example of using a pipe to with posix_spawn
to sending input to spawned process
#include <stdio.h>
#include <unistd.h>
#include <spawn.h>
#include <sys/wait.h>
int main(void) {
// create a pipe
int pipe_file_descriptors[2];
if (pipe(pipe_file_descriptors) == -1) {
perror("pipe");
return 1;
}
// create a list of file actions to be carried out on spawned process
posix_spawn_file_actions_t actions;
if (posix_spawn_file_actions_init(&actions) != 0) {
perror("posix_spawn_file_actions_init");
return 1;
}
// tell spawned process to close unused write end of pipe
// without this - spawned process will not receive EOF
// when write end of the pipe is closed below,
// because spawned process also has the write-end open
// deadlock will result
if (posix_spawn_file_actions_addclose(&actions, pipe_file_descriptors[1]) != 0) {
perror("posix_spawn_file_actions_init");
return 1;
}
// tell spawned process to replace file descriptor 0 (stdin)
// with read end of the pipe
if (posix_spawn_file_actions_adddup2(&actions, pipe_file_descriptors[0], 0) != 0) {
perror("posix_spawn_file_actions_adddup2");
return 1;
}
// create a process running /usr/bin/sort
// sort reads lines from stdin and prints them in sorted order
char *sort_argv[] = {"sort", NULL};
pid_t pid;
extern char **environ;
if (posix_spawn(&pid, "/usr/bin/sort", &actions, NULL, sort_argv, environ) != 0) {
perror("spawn");
return 1;
}
// close unused read end of pipe
close(pipe_file_descriptors[0]);
// create a stdio stream from write-end of pipe
FILE *f = fdopen(pipe_file_descriptors[1], "w");
if (f == NULL) {
perror("fdopen");
return 1;
}
// send some input to the /usr/bin/sort process
//sort with will print the lines to stdout in sorted order
fprintf(f, "sort\nwords\nplease\nthese\n");
// close write-end of the pipe
// without this sort will hang waiting for more input
fclose(f);
int exit_status;
if (waitpid(pid, &exit_status, 0) == -1) {
perror("waitpid");
return 1;
}
printf("/usr/bin/sort exit status was %d\n", exit_status);
// free the list of file actions
posix_spawn_file_actions_destroy(&actions);
return 0;
}
simple example of use to popen to capture output
#include <stdio.h>
#include <stdlib.h>
int main(void) {
// popen passes command to a shell for evaluation
// brittle and highly-vulnerable to security exploits
// popen is suitable for quick debugging and throw-away programs only
//
// tr a-z A-Z - passes stdin to stdout converting lower case to upper case
FILE *p = popen("tr a-z A-Z", "w");
if (p == NULL) {
perror("");
return 1;
}
fprintf(p, "plz date me\n");
pclose(p); // returns command exit status
return 0;
}
A simple example which launches two threads of execution.
$ gcc -pthread two_threads.c -o two_threads $ ./two_threads | more Hello this is thread #1 i=0 Hello this is thread #1 i=1 Hello this is thread #1 i=2 Hello this is thread #1 i=3 Hello this is thread #1 i=4 Hello this is thread #2 i=0 Hello this is thread #2 i=1 ...
#include <pthread.h>
#include <stdio.h>
// This function is called to start thread execution.
// It can be given any pointer as an argument.
void *run_thread (void *argument)
{
int *p = argument;
for (int i = 0; i < 10; i++) {
printf ("Hello this is thread #%d: i=%d\n", *p, i);
}
// A thread finishes when either the thread's start function
// returns, or the thread calls `pthread_exit(3)'.
// A thread can return a pointer of any type --- that pointer
// can be fetched via `pthread_join(3)'
return NULL;
}
int main (void)
{
// Create two threads running the same task, but different inputs.
pthread_t thread_id1;
int thread_number1 = 1;
pthread_create (&thread_id1, NULL, run_thread, &thread_number1);
pthread_t thread_id2;
int thread_number2 = 2;
pthread_create (&thread_id2, NULL, run_thread, &thread_number2);
// Wait for the 2 threads to finish.
pthread_join (thread_id1, NULL);
pthread_join (thread_id2, NULL);
return 0;
}
Simple example of running an arbitrary number of threads.
For example::
$ gcc -pthread n_threads.c -o n_threads $ ./n_threads 10 Hello this is thread 0: i=0 Hello this is thread 0: i=1 Hello this is thread 0: i=2 Hello this is thread 0: i=3 Hello this is thread 0: i=4 Hello this is thread 0: i=5 Hello this is thread 0: i=6 Hello this is thread 0: i=7 ...
#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
void *run_thread (void *argument)
{
int *p = argument;
for (int i = 0; i < 42; i++) {
printf ("Hello this is thread %d: i=%d\n", *p, i);
}
return NULL;
}
int main (int argc, char *argv[])
{
if (argc != 2) {
fprintf (stderr, "Usage: %s <n-threads>\n", argv[0]);
return 1;
}
int n_threads = strtol (argv[1], NULL, 0);
assert (0 < n_threads && n_threads < 100);
pthread_t thread_id[n_threads];
int argument[n_threads];
for (int i = 0; i < n_threads; i++) {
argument[i] = i;
pthread_create (&thread_id[i], NULL, run_thread, &argument[i]);
}
// Wait for the threads to finish
for (int i = 0; i < n_threads; i++) {
pthread_join (thread_id[i], NULL);
}
return 0;
}
Simple example of dividing a task between `n' threads.
Compile like:
$ gcc -O3 -pthread thread_sum.c -o thread_sum
One thread takes 10 seconds:
$ time ./thread_sum 1 10000000000 Creating 1 threads to sum the first 10000000000 integers Each thread will sum 10000000000 integers Thread summing integers 0 to 10000000000 finished sum is 49999999990067863552
Combined sum of integers 0 to 10000000000 is 49999999990067863552
real 0m11.924s user 0m11.919s sys 0m0.004s $
Four threads runs 4x as fast on a machine with 4 cores:
$ time ./thread_sum 4 10000000000 Creating 4 threads to sum the first 10000000000 integers Each thread will sum 2500000000 integers Thread summing integers 2500000000 to 5000000000 finished sum is 9374999997502005248 Thread summing integers 7500000000 to 10000000000 finished sum is 21874999997502087168 Thread summing integers 5000000000 to 7500000000 finished sum is 15624999997500696576 Thread summing integers 0 to 2500000000 finished sum is 3124999997567081472
Combined sum of integers 0 to 10000000000 is 49999999990071869440
real 0m3.154s user 0m12.563s sys 0m0.004s $
Note the result is inexact, because we use values can't be exactly represented as double and exact value printed depends on how many threads we use - because we break up the computation differently depending on the number of threads.
#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
struct job {
long start, finish;
double sum;
};
void *run_thread (void *argument)
{
struct job *j = argument;
long start = j->start;
long finish = j->finish;
double sum = 0;
for (long i = start; i < finish; i++) {
sum += i;
}
j->sum = sum;
printf (
"Thread summing integers %10lu to %11lu finished sum is %20.0f\n",
start, finish, sum);
return NULL;
}
int
main (int argc, char *argv[])
{
if (argc != 3) {
fprintf (
stderr,
"Usage: %s <n-threads> <n-integers-to-sum>\n",
argv[0]);
return 1;
}
int n_threads = strtol (argv[1], NULL, 0);
assert (0 < n_threads && n_threads < 1000);
long integers_to_sum = strtol (argv[2], NULL, 0);
assert (0 < integers_to_sum);
long integers_per_thread = (integers_to_sum - 1) / n_threads + 1;
printf (
"Creating %d threads to sum the first %lu integers\n"
"Each thread will sum %lu integers\n",
n_threads, integers_to_sum, integers_per_thread);
pthread_t thread_id[n_threads];
struct job jobs[n_threads];
for (int i = 0; i < n_threads; i++) {
jobs[i].start = i * integers_per_thread;
jobs[i].finish = jobs[i].start + integers_per_thread;
if (jobs[i].finish > integers_to_sum) {
jobs[i].finish = integers_to_sum;
}
// create a thread which will sum integers_per_thread integers
pthread_create (&thread_id[i], NULL, run_thread, &jobs[i]);
}
// Wait for threads to finish, then add results for an overall sum.
double overall_sum = 0;
for (int i = 0; i < n_threads; i++) {
pthread_join (thread_id[i], NULL);
overall_sum += jobs[i].sum;
}
printf (
"\nCombined sum of integers 0 to %lu is %.0f\n",
integers_to_sum, overall_sum);
return 0;
}
Simple example which launches two threads of execution, but which demonstrates the perils of accessing non-local variables from a thread.
$ gcc -pthread two_threads_broken.c -o two_threads_broken $ ./two_threads_broken|more Hello this is thread 2: i=0 Hello this is thread 2: i=1 Hello this is thread 2: i=2 Hello this is thread 2: i=3 Hello this is thread 2: i=4 Hello this is thread 2: i=5 Hello this is thread 2: i=6 Hello this is thread 2: i=7 Hello this is thread 2: i=8 Hello this is thread 2: i=9 Hello this is thread 2: i=0 Hello this is thread 2: i=1 Hello this is thread 2: i=2 Hello this is thread 2: i=3 Hello this is thread 2: i=4 Hello this is thread 2: i=5 Hello this is thread 2: i=6 Hello this is thread 2: i=7 Hello this is thread 2: i=8 Hello this is thread 2: i=9 $...
#include <pthread.h>
#include <stdio.h>
void *run_thread (void *argument)
{
int *p = argument;
for (int i = 0; i < 10; i++) {
// variable thread_number will probably have changed in main
// before execution reaches here
printf ("Hello this is thread %d: i=%d\n", *p, i);
}
return NULL;
}
int main (void)
{
pthread_t thread_id1;
int thread_number = 1;
pthread_create (&thread_id1, NULL, run_thread, &thread_number);
thread_number = 2;
pthread_t thread_id2;
pthread_create (&thread_id2, NULL, run_thread, &thread_number);
pthread_join (thread_id1, NULL);
pthread_join (thread_id2, NULL);
return 0;
}
Simple example demonstrating unsafe access to a global variable from threads.
$ gcc -O3 -pthread bank_account_broken.c -o bank_account_broken $ ./bank_account_broken Andrew's bank account has $108829 $
#define _POSIX_C_SOURCE 199309L
#include <pthread.h>
#include <stdio.h>
#include <time.h>
int bank_account = 0;
// add $1 to Andrew's bank account 100,000 times
void *add_100000 (void *argument)
{
for (int i = 0; i < 100000; i++) {
// execution may switch threads in middle of assignment
// between load of variable value
// and store of new variable value
// changes other thread makes to variable will be lost
nanosleep (&(struct timespec){.tv_nsec = 1}, NULL);
// RECALL: shorthand for `bank_account = bank_account + 1`
bank_account++;
}
return NULL;
}
int main (void)
{
// create two threads performing the same task
pthread_t thread_id1;
pthread_create (&thread_id1, NULL, add_100000, NULL);
pthread_t thread_id2;
pthread_create (&thread_id2, NULL, add_100000, NULL);
// wait for the 2 threads to finish
pthread_join (thread_id1, NULL);
pthread_join (thread_id2, NULL);
// will probably be much less than $200000
printf ("Andrew's bank account has $%d\n", bank_account);
return 0;
}
Simple example demonstrating safe access to a global variable from threads, using a mutex (mutual exclusion) lock
$ gcc -O3 -pthread bank_account_mutex.c -o bank_account_mutex $ ./bank_account_mutex Andrew's bank account has $200000 $
#include <pthread.h>
#include <stdio.h>
int bank_account = 0;
pthread_mutex_t bank_account_lock = PTHREAD_MUTEX_INITIALIZER;
// add $1 to Andrew's bank account 100,000 times
void *add_100000 (void *argument)
{
for (int i = 0; i < 100000; i++) {
pthread_mutex_lock (&bank_account_lock);
// only one thread can execute this section of code at any time
bank_account = bank_account + 1;
pthread_mutex_unlock (&bank_account_lock);
}
return NULL;
}
int main (void)
{
// create two threads performing the same task
pthread_t thread_id1;
pthread_create (&thread_id1, NULL, add_100000, NULL);
pthread_t thread_id2;
pthread_create (&thread_id2, NULL, add_100000, NULL);
// wait for the 2 threads to finish
pthread_join (thread_id1, NULL);
pthread_join (thread_id2, NULL);
// will always be $200000
printf ("Andrew's bank account has $%d\n", bank_account);
return 0;
}
! simple example which launches two threads of execution
! which increment a global variable
#include <pthread.h>
#include <stdio.h>
int andrews_bank_account = 200;
pthread_mutex_t andrews_bank_account_lock = PTHREAD_MUTEX_INITIALIZER;
int zacs_bank_account = 100;
pthread_mutex_t zacs_bank_account_lock = PTHREAD_MUTEX_INITIALIZER;
// Andrew sends Zac all his money dollar by dollar
void *andrew_send_zac_money(void *argument)
{
for (int i = 0; i < 100000; i++) {
pthread_mutex_lock (&andrews_bank_account_lock);
pthread_mutex_lock (&zacs_bank_account_lock);
if (andrews_bank_account > 0) {
andrews_bank_account--;
zacs_bank_account++;
}
pthread_mutex_unlock (&zacs_bank_account_lock);
pthread_mutex_unlock (&andrews_bank_account_lock);
}
return NULL;
}
// Zac sends Andrew all his money dollar by dollar
void *zac_send_andrew_money(void *argument)
{
for (int i = 0; i < 100000; i++) {
pthread_mutex_lock (&zacs_bank_account_lock);
pthread_mutex_lock (&andrews_bank_account_lock);
if (zacs_bank_account > 0) {
zacs_bank_account--;
andrews_bank_account++;
}
pthread_mutex_unlock (&andrews_bank_account_lock);
pthread_mutex_unlock (&zacs_bank_account_lock);
}
return NULL;
}
int main (void)
{
// create two threads sending each other money
pthread_t thread_id1;
pthread_create (&thread_id1, NULL, andrew_send_zac_money, NULL);
pthread_t thread_id2;
pthread_create (&thread_id2, NULL, zac_send_andrew_money, NULL);
// threads will probably never finish
// deadlock will likely likely occur
// with one thread holding andrews_bank_account_lock
// and waiting for zacs_bank_account_lock
// and the other thread holding zacs_bank_account_lock
// and waiting for andrews_bank_account_lock
pthread_join (thread_id1, NULL);
pthread_join (thread_id2, NULL);
return 0;
}
Simple example demonstrating safe access to a global variable from threads, using atomics
$ gcc -O3 -pthread bank_account_atomic.c -o bank_account_atomic $ ./bank_account_atomic Andrew's bank account has $200000 $
#include <pthread.h>
#include <stdio.h>
#include <stdatomic.h>
atomic_int bank_account = 0;
// add $1 to Andrew's bank account 100,000 times
void *add_100000 (void *argument)
{
for (int i = 0; i < 100000; i++) {
// NOTE: This *cannot* be `bank_account = bank_account + 1`,
// as that will not be atomic!
// However, `bank_account++` would be okay
// and, `atomic_fetch_add(&bank_account, 1)` would also be okay
bank_account += 1;
}
return NULL;
}
int main (void)
{
// create two threads performing the same task
pthread_t thread_id1;
pthread_create (&thread_id1, NULL, add_100000, NULL);
pthread_t thread_id2;
pthread_create (&thread_id2, NULL, add_100000, NULL);
// wait for the 2 threads to finish
pthread_join (thread_id1, NULL);
pthread_join (thread_id2, NULL);
// will always be $200000
printf ("Andrew's bank account has $%d\n", bank_account);
return 0;
}
! An example demonstrating the performance discrepancy
! between a Mutex guarding an unsigned int vs a single atomic_uint.
!
! Compile like:
! `clang -pthread -D <PERF_USE_NONE|PERF_USE_MUTEX|PERF_USE_ATOMIC> mutex_atomic_perf.c -o mutex_atomic_perf`
!
! It will then build the code using the preferred method of synchronisation.
! Note that *no synchronisation* will almost certainly give an incorrect sum -- this is to be expected.
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdatomic.h>
// Make sure at-most one flag has been provided,
// otherwise we will have a compiler error
#ifdef PERF_USE_NONE
#ifdef PERF_USE_MUTEX
#error "only *one* option can be specified"
#endif // PERF_USE_MUTEX
#ifdef PERF_USE_ATOMIC
#error "only *one* option can be specified"
#endif // PERF_USE_ATOMIC
#endif // PERF_USE_NONE
#ifdef PERF_USE_MUTEX
#ifdef PERF_USE_ATOMIC
#error "only *one* option can be specified"
#endif // PERF_USE_ATOMIC
#endif // PERF_USE_MUTEX
// If no flag has been provided, default to NONE
#ifndef PERF_USE_NONE
#ifndef PERF_USE_MUTEX
#ifndef PERF_USE_ATOMIC
#define PERF_USE_NONE
#endif // PERF_USE_ATOMIC
#endif // PERF_USE_MUTEX
#endif // PERF_USE_NONE
// No synchronisation -- just a plain `unsigned int`
#ifdef PERF_USE_NONE
unsigned int count = 0;
#endif // PERF_USE_NONE
// Mutex synchronisation -- a lock and a plain `unsigned int`
// that must be protected behind the lock
#ifdef PERF_USE_MUTEX
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
unsigned int count = 0;
#endif // PERF_USE_MUTEX
// Atomic synchronisation -- an `atomic_uint`
#ifdef PERF_USE_ATOMIC
atomic_uint count = 0;
#endif // PERF_USE_ATOMIC
void *thread(void *data) {
unsigned long n_increments = * (unsigned long *) data;
#ifdef PERF_USE_NONE
// If no synchronisation, just increment the count
for (int i = 0; i < n_increments; i++) {
count++;
}
#endif // PERF_USE_NONE
#ifdef PERF_USE_MUTEX
// If mutex synchronisation, acquire the
// lock, increment the count, then release
// the lock
for (int i = 0; i < n_increments; i++) {
pthread_mutex_lock(&lock);
count++;
pthread_mutex_unlock(&lock);
}
#endif // PERF_USE_MUTEX
#ifdef PERF_USE_ATOMIC
// If atomic synchronisation, just
// increment -- the synchronisation is
// handled automagically for us!
for (int i = 0; i < n_increments; i++) {
count++;
}
#endif // PERF_USE_ATOMIC
return NULL;
}
int main(int argc, char *argv[]) {
if (!argv[0] || !argv[1] || !argv[2]) {
fprintf(stderr, "Usage: %s <n threads> <n increments per thread>\n", argv[0]);
return EXIT_FAILURE;
}
unsigned long n_threads = strtoul(argv[1], NULL, 0);
unsigned long n_increments = strtoul(argv[2], NULL, 0);
pthread_t *threads = malloc(n_threads * sizeof(pthread_t));
for (int i = 0; i < n_threads; i++) {
pthread_create(&threads[i], NULL, thread, &n_increments);
}
for (int i = 0; i < n_threads; i++) {
pthread_join(threads[i], NULL);
}
printf("Final result: %d\n", (int) count);
}
! A small program that demonstrates lifetime issues
! with respect to differing threads
!
! When compiled with `dcc`:
! $ dcc -pthread thread_data_broken.c -o thread_data_broken
! $ ./thread_data_broken
! Hello there! Please patiently wait for your number!
! The number is 0x6c6c6548!
!
! Note that the 0x6c6c6548 value can easily change between
! compilers, platforms, or even individual executions.
! In this case, 0x6c6c6548 is the four ASCII bytes:
! 'l', 'l', 'e', 'H' -- the first four letters of "Hello there..."
! in little-endian byte ordering
!
! Curiously, the correct answer will occasionally appear:
! $ ./thread_data_broken
! Hello there! Please patiently wait for your number!
! The number is 0x42!
!
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
void *my_thread(void *data) {
int number = * (int *) data;
sleep(1);
printf("The number is 0x%x!\n", number);
return NULL;
}
pthread_t function_creates_thread(void) {
int super_special_number = 0x42;
pthread_t thread_handle;
pthread_create(&thread_handle, NULL, my_thread, &super_special_number);
return thread_handle;
}
/// This function is partially a red-herring.
/// It should be entirely innocent looking, and is perfectly
/// reasonable + valid C. It is used to make a memory
/// bug in function_creates_thread far more likely to trigger
void function_says_hello(void) {
char greeting[] = "Hello there! Please patiently wait for your number!\n";
printf("%s", greeting);
}
int main(void) {
pthread_t thread_handle = function_creates_thread();
function_says_hello();
pthread_join(thread_handle, NULL);
}
! A potential solution to the issue in thread_data_broken.c
!
! This program uses a heap allocation to make sure that
! the memory will not be deallocated before the thread
! has a chance to read it.
!
! This in turn means that the thread is responsible for freeing
! the passed-in data.
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
void *my_thread(void *data) {
int number = * (int *) data;
sleep(1);
printf("The number is 0x%x!\n", number);
free(data);
return NULL;
}
pthread_t function_creates_thread(void) {
int *super_special_number = malloc(sizeof(int));
*super_special_number = 0x42;
pthread_t thread_handle;
pthread_create(&thread_handle, NULL, my_thread, super_special_number);
return thread_handle;
}
void function_says_hello(void) {
char greeting[] = "Hello there! Please patiently wait for your number!\n";
printf("%s", greeting);
}
int main(void) {
pthread_t thread_handle = function_creates_thread();
function_says_hello();
pthread_join(thread_handle, NULL);
}
! A potential solution to the issue in thread_data_broken.c
!
! This program does not need an allocation in order to fix
! the previous lifetime issue. Instead it makes sure the thread
! has a chance to read the memory (and copy it into its own stack)
! before it is deallocated, by using a barrier.
!
! The barrier is initialised with a value of 2:
! - One for the caller thread, so it doesn't deallocate the memory immediately
! - One for the called thread, so it can signal when it has copied the memory
!
! Performance in execution speed is incredibly similar to malloc-version,
! but does not rely on additional allocation, which is an occasional
! real-world constraint.
!
! NOTE: `dcc` tends to not like this example code
! try running with `clang` or `gcc` instead.
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>
struct thread_data {
pthread_barrier_t *barrier;
int number;
};
void *my_thread(void *data) {
struct thread_data *thread_data = (struct thread_data *) data;
int number = thread_data->number;
pthread_barrier_wait(thread_data->barrier);
sleep(1);
printf("The number is 0x%x!\n", number);
return NULL;
}
pthread_t function_creates_thread(void) {
pthread_barrier_t barrier;
pthread_barrier_init(&barrier, NULL, 2);
struct thread_data data = {
.barrier = &barrier,
.number = 0x42,
};
pthread_t thread_handle;
pthread_create(&thread_handle, NULL, my_thread, &data);
pthread_barrier_wait(&barrier);
return thread_handle;
}
void function_says_hello(void) {
char greeting[] = "Hello there! Please patiently wait for your number!\n";
printf("%s", greeting);
}
int main(void) {
pthread_t thread_handle = function_creates_thread();
function_says_hello();
pthread_join(thread_handle, NULL);
}
Simple example demonstrating ensuring safe access to a global variable from threads using a semaphore.
$ gcc -O3 -pthread bank_account_semphore.c -o bank_account_semphore $ ./bank_account_semphore Andrew's bank account has $200000 $
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
int bank_account = 0;
sem_t bank_account_semaphore;
// add $1 to Andrew's bank account 100,000 times
void *add_100000 (void *argument)
{
for (int i = 0; i < 100000; i++) {
// decrement bank_account_semaphore if > 0
// otherwise wait until > 0
sem_wait (&bank_account_semaphore);
// only one thread can execute this section of code at any time
// because bank_account_semaphore was initialized to 1
bank_account = bank_account + 1;
// increment bank_account_semaphore
sem_post (&bank_account_semaphore);
}
return NULL;
}
int main (void)
{
// initialize bank_account_semaphore to 1
sem_init (&bank_account_semaphore, 0, 1);
// create two threads performing the same task
pthread_t thread_id1;
pthread_create (&thread_id1, NULL, add_100000, NULL);
pthread_t thread_id2;
pthread_create (&thread_id2, NULL, add_100000, NULL);
// wait for the 2 threads to finish
pthread_join (thread_id1, NULL);
pthread_join (thread_id2, NULL);
// will always be $200000
printf ("Andrew's bank account has $%d\n", bank_account);
sem_destroy (&bank_account_semaphore);
return 0;
}
All Links
- All Tutorial Questions
- All Tutorial Answers
-
- All Laboratory Exercises
- All Laboratory Sample Solutions
-
- All Weekly Test Questions
-
- All Weekly Test Sample Answers
-
- Course Intro
- Mips Basics
- Mips Control
- Mips Data
- Integers
- Mips Functions
- Bitwise Operations
- Floating Point
- Unicode
- Files
- Processes
- Threads
- Caching
- Virtual Memory
- Exam