CSC 209 lab 13 exercises, week of 9 August 2022

Attendance

Remember that you can check that your attendance has been recorded properly at https://wwwcgi.teach.cs.toronto.edu/~ajr/cgi-bin/auth/present

Exercise one (not for credit)

Imagine a board of 100 numbers:

Remove the 1, since that is neither a prime number nor composite.

Start with the 2, and leave that alone, but punch out (remove from the board) the numbers 4, 6, 8, 10, and so on — all of the multiples of 2.

Next go to the 3. Leave that alone, but punch out the numbers 6 (already punched out), 9, 12 (already punched out), and so on — all of the multiples of 3.

When we get to the 4, we see that it is punched out, so we don't have to do anything.

Then we punch out all of the multiples of 5, excluding 5 itself; and so on.

When we're done, we have left a list of the prime numbers less than (or equal to) 100.

Write a program using threads to do these "punching out"s in parallel.

Create an array of type int from 2 to 100, to be considered as booleans. (The easiest way to do this is with "int sieve[101];" and ignore sieve[0] and sieve[1].)

Set all of the values to true (1).

Then create a thread for each of the numbers from 2 to 100 inclusive, which will do the "punching out" for that number. These threads must run in parallel.

After you "pthread_join" (wait for) all the threads, print the numbers corresponding to all of the 1 values left in the array.

Note that this evades any concurrency issues — if two threads set a particular int to zero simultaneously, no harm is done.

Unlike the real Sieve of Eratosthenes, you will not be doing the optimization of, for example, seeing that 4 is already punched out and not bothering to do the algorithm for 4. This would raise concurrency issues.

NOTE: In standard software tools fashion, your output should be just the prime numbers, no more and no less, with one number per line (like the output of "seq").

Exercise two (for credit)

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char s[100];

    gets(s);
    if (atoi(s) == 12)
        printf("do something\n");
    printf("in any case, do something else\n");
    return(0);
}

These days, gcc (even without −Wall!) complains about this program, for the reasons we shall see here.
For now, compile and run it, ignoring the warnings.

Try typing the secret value 12, and try typing other numbers.

This seems fine, but it it uses the gets() function.

What is wrong with the gets() function? The problem is that it does not take a parameter specifying the size of the array, so it is impossible for it to be written properly and it is impossible for any program which calls it to be correct! If you type more than 99 characters, your program will exceed the 's' array bounds. If you're lucky, your program will simply crash.

1. Cause this program to crash with "segmentation fault".

2. Fix the bug without changing the size of s, nor changing anything else unrelated. That is to say, all of your changes must be justifiable in terms of either fixing the bug, or avoiding warning messages from gcc −Wall. (Try doing a diff with the original, or a "diff −b".)

Exercise three (for credit)

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

int main()
{
    extern int authenticate();
    if (authenticate() == 2) {
        printf("Login incorrect.\n");
        return(1);
    }
    printf("Access to secret stuff achieved\n");
    return(0);
}


int authenticate()
{
    char buf[80];
    printf("Password: ");
    if (fgets(buf, sizeof buf, stdin) == NULL)
        return(0);
    else if (strcmp(buf, "sesame\n") == 0)
        return(1);
    else
        return(2);
}

1. Compile and run this. The password is "sesame". Try running it with and without the correct password.

2. Suppose you did not know that the password was sesame but you could see the rest of the source code. Run the program and get it to print "Access to secret stuff achieved" without typing "sesame".

3. Fix the bug.

Exercise four (not for credit)

To submit

Submit your fixed bug.c and auth.c programs by the end of Friday August 12, with commands such as

        submit -c csc209h -a lab13 bug.c auth.c

This lab will be graded out of 2, one point for each file. To get the point for a file, three things must be true:

1. you have fixed the bug
2. your file compiles with "gcc −Wall" with no errors or warning messages
3. you have not changed anything else which is not related to fixing the bug. In particular, for bug.c, you have not changed the size of the array.