Reference no: EM131418495

Assignment

[1] A common text-based file format is to have multiple records in a file, one per line, where the fields of each record are separated by some character which is either unlikely to be found in a field or completely illegal in a field. For example, you may be familiar with comma-separated value (CSV) files, where fields are separated by commas, and if a field has a comma, the field is surrounded by double quotation marks (at least when I looked at a libreoffice .csv file.)

On Unix-type systems, there are a number of files of interest where the fields are separated by ":" and no field may contain a ":". For example, the file /etc/passwd contains one record per account (system or user). Each record in this file has the following fields:

- the user name,
- the encrypted password (on most/all modern systems, that field has a single 'x', which indicates the encrypted password is found in another (read-protected) file),
- the numeric user id,
- the numeric group id,
- optional textual information such as the user's human name (the so-called "GeCOS" field),
- the account's home directory, and
- a program to run when this account logs in (usually a command interpreter, but often
/bin/false for admin accounts which are not intended to be logged into, or for users whose accounts have been disabled).

For this problem, define a struct pwent which holds all of the information in one /etc/passwd record. Hold each character string field (all except the numeric ids) in character arrays. For this problem, you may limit the user name to at most 15 characters long, the encrypted password to at most 20 characters long, the optional text to at most 50 characters long, the home directory to at most 25 characters long, and the program to at most 25 characters long. If you process a record with any string longer than the given limits, your program should store as much of the string in the struct as will fit in the given space and otherwise carry on normally.

Write a function struct pwent get_pwent(int rec_num, FILE * in) which takes a file pointer giving access to a file whose format is that of an /etc/passwd file, and a desired record number. We define the first record in the file to be record one, the second to be record two, and so on. This function finds the rec_num-th line in the file, reads the data into a struct pwent variable, and then returns that variable. If there is no such record in the file (e.g., the calling function wants the -1-st record, or the 333-rd record in a 100-record file) get_pwent() returns a struct where the user is an empty string. (This is not the best way of designating "failure", but since we do not yet know how to return two separate values, it will do for this week.)

Your function may have to go backwards in the file to read a given record. In fact, we have not yet learned how functions can "remember" information from one call to the next, so when your function is called it has no idea where it is in the file. Thus it can rewind the file to the beginning (with the rewind() function, see its man page) and then skip an appropriate number of lines forward until it gets to the one it wants.

A clever application of what we discussed in class makes get_pwent() easy to write. If you don't do it the easy way, you may find yourself working very hard. ("Think twice, code once.")

Write a main program which looks at the first command-line argument, if any, and if the first command line argument is not a number, it opens that file (attempts to open it, anyway) for reading. If the first command line argument is a number, main() opens /etc/passwd for reading.

If there are no numeric arguments, main() calls get_pwent() repeatedly with rec_num 1, 2, 3, and so on, until get_pwent() returns a struct whose user name is the empty string. Each valid entry is printed in a table as shown below. At this point main() closes the file and terminates.

If there are numeric command-line arguments, main() processes each one in turn, calling get_pwent() with that argument, and printing out information about each struct returned. When all numeric arguments have been processed main() closes the file and terminates.

Suppose file a7p1.dat contains the following lines
root:x:0:0::/root:/bin/tcsh
rootbash:x:0:0::/root:/bin/bash
bin:x:1:1:bin:/bin:/bin/false
daemon:x:2:2:daemon:/sbin:/bin/false
adm:x:3:4:adm:/var/log:/bin/false
lp:x:4:7:lp:/var/spool/lpd:/bin/false
sync:x:5:0:sync:/sbin:/bin/sync
shutdown:x:6:0:shutdown:/sbin:/sbin/shutdown
halt:x:7:0:halt:/sbin:/sbin/halt
bob:x:1000:100:Robert S. Schmoe,Room 244,Bloggins Building:/home/bob:/bin/ksh
and you run your program as follows, you get output as shown:
a7p1 a7p1.dat 1 3 10 6 17 4

Username		Pwd		UID		GID		GeCOS		Home Dir	Shell
root	|	x	|	0	|	0	|			/root	/bin/tcsh
bin	|	x	|	1	|	1	|	bin		/bin	/bin/false
bob	|	x	|	1000	|	100	|	Robert	S. Schm	/home/bob	/bin/ksh
lp	|	x	|	4	|	7	|	lp		/var/spool/	/bin/false
Warning!  a7p1.dat				does	not	have		a  record  17
daemon |      x  |				2	|	2 |		daemon		/sbin	/bin/false

Note the following about the output format:

(i) the username is printed right-justified in a 9-character field, followed by one space;
(ii) the password is printed right-justified in a 3-character field, both preceded and followed by one space;
(iii) the numeric userid and groupid are both printed right-justified in a 4-character field, both preceded and followed by one space;
(iv) the GeCOS field is printed left-justified in a 14-character field, both preceded and followed by one space;
(v) the home directory is printed left-justified in an 11-character field, both preceded and followed by one space;
(vi) the shell is printed, preceded by one space;
(vii) fields are separated by "|", as shown; and
(viii) strings wider than the allocated space are truncated to the stated field widths.

Note that the output field widths for the strings are not necessarily as wide as what you have read into your struct pwent. If the string is too wide for the field, your program must truncate the string; an example above is that "Robert S. Schmoe: : : " was truncated because it was too long for the space available.

Make up one or more sample data files, and make sure they get catted into your script file. Run your program enough times so that the TA could conceivably look at your data file(s) and program runs and be 99% sure that your program handles all of the issues outlined above. However: when creating tests, you should always go for quality, not quantity. Each test should attempt to exercise some feature of your program which no other test in your test suite exercises. You should have a test case which shows your program "operating normally", and then you should have one or more test cases which show your program correctly handling unusual situations, erroneous input, and so on. If a single test can demonstrate your program handling a number of different cases, that's great. And you can even help yourself and the TA to see what is being tested in many case. For example, if you want to demonstrate that your program correctly truncates a long home directory, your test file could have something like "/this/is/a/really/long/home/directory", so that it is obvious what the test is.

These comments apply to every program you write from now to the end of your life, not just A7P1.

[2] Consider the following definitions:

#define MAX_VALUES 50

typedef int IntArr_T[MAX_VALUES]; typedef struct
{
IntArr_T integers; /* array for up to MAX_VALUES integers */
int count; /* actual number of integers: 0 to MAX_VALUES */
} Integers_T;

The idea of this data structure is that the first count numbers are significant, but the rest of the numbers (if any) are completely irrelevant and not to be examined. For example, if the count of a particular Integers_T struct is 5, that means only the first 5 values in integers are of any concern; the rest of the values are of no concern.

Write a function onlyEvens() which takes one parameter, an Integers_T structure. The function creates a new Integers_T structure similar to the argument, except that

- the new structure's count variable is equal to the number of even integers in the argument array's first count locations; and

- the new structure's integers variable has only the even numbers from the valid values in the argument's array. onlyEvens() then returns the new structure.

Suppose the first 5 values in this struct's integers array are 2, 3, 5, 7 and 8. After calling onlyEvens(), in the returned struct count should be 2 and the first two elements of the array should be 2 and 8, in that order. The third, fourth, and following values are all irrelevant after the call.

To test the function, you must write a main program which declares and initializes a number of Integers_T structures. For each of these structures, your program must print out the contents of the structure which you pass to onlyEvens() as well as the returned structure. If you want to write a function to display the structure, that's not merely acceptable, it's a good idea. Whether you write a function to output the values or not, output at most 10 integers per line, as shown below.

Here is a sample run of a program which only does one test. Your program must do more tests. Are there any "special" cases you should test to convince the marker that you thought about the various situations which might occur?

%a7p2
Original structure has 18 integers:
12 11 -999 0 42 1331 131565131 333 1212 398761
-1 -2 -3 -4 -6 -9 12 77
New structure has 8 integers:
12 0 42 1212 -2 -4 -6 12

Things to think about:

- if you write a function to print the struct contents, does it make more sense for that function to be called from main() or from onlyEvens()?
- if you write a function to print the struct contents, what is "The (A?) Right Way" to output "Original" in some cases and "New" in others?

[3] An important data encryption technique involves raising numbers to very high powers, but with the results reduced modulo another number. As a very small example, we could raise 3 to the 100-th power mod 35:

3¹⁰⁰ mod 35 ≡ 11.
Note that 3¹⁰⁰ = 515377520732011331036461129765621272702107522001, which is well beyond the capacity of even a 64-bit integer. Fortunately, when we reduce the result modulo some other "reasonable" size number, the final result is also of "reasonable" size.

One implementation of the encryption technique mentioned above uses 200-digit integers, whose use requires a software library. In this question we will use integers which fit inside a uint64_t, so that you can use the arithmetic capabilities built into your ALU.

To do calculations like "3100 modulo some number", note that we can reduce the intermediate product after every multiplication. For example

94 mod 35 ≡ 9 • 9 • 9 • 9 mod 35
≡ (9 • 9 mod 35) • 9 • 9 mod 35
≡ (81 mod 35) • 9 • 9 mod 35
≡ 11 • 9 • 9 mod 35
≡ (11 • 9 mod 35) • 9 mod 35
≡ (99 mod 35) • 9 mod 35
≡ 29 • 9 mod 35
≡ 261 mod 35
≡ 16 mod 35 :

You will notice that, if we reduce each product modulo the modulus, no intermediate calculation result can be larger than the square of the modulus. (For example, with modulus 35, the largest possible intermediate calculation is 34 x 34 = 1156.)

In this question, you will compare the straightforward way of computing powers (i.e., a for loop) with the following clever idea. Specifically, write a recursive function uint64_t fast- Power(uint64_t k, uint64_t n, uint32_t m) which computes kn mod m (for n > 0) using the following algorithm:

if n > 1 is even
compute k^n/2 x k^n/2 mod m
else
compute k x k^n-1 mod m

Note that when n is even, you would not calculate k^n/2 twice; you would calculate that number once, store it in a variable, and then multiply that variable by itself. If you don't see why that is important, try it both ways and see what happens.

Write a function uint64_t normalPower(uint64_t k, uint64_t n, uint32_t m) which does the same calculation, but using the usual iterative algorithm.

Now write a main program which does the following:

(i) ensures that the program was called with two arguments (the number k to be raised to a power and m the modulus);
(ii) converts (attempts to convert) the arguments into a uint64_t and uint32_t, respectivly;
(iii) computes kⁿ mod m for each n D 10; 100; 1000; 10⁴; 10⁵; : : : 10¹⁰ using both the fast method and the normal method;
(iv) times how long each calculation takes; and
(v) outputs the results in a table similar to the one below.

As we saw in a recent assignment, our computers are just too fast to time things with only microsecond accuracy. So for this question, use clock_gettime() (see the man page for details) and use CLOCK_REALTIME as the clock choice. (You may want to play around with the other clock choices for your own amusement or (*cough*) education.) NOTE: if you are running an older version of Linux you might have to pay attention when the man page tells you that you need to link with a particular library.

Here is a sample table for k = 45 and m = 32607847, with no actual result times present. Make sure you format your numbers so the table is easy to read.

n	45^n mod 32607847	fast time	iterative time
10^0	45	Xyz	pqr
10^1	20220464	xyz	pqr
	. . .
10^10	nnnnnnn	xyz	pqr

Your program must compare your iterative result with your fast power result to make sure they are in agreement. But you need only print the result once.

When creating your script file, you must include a test with k = 1834 and m = 590627381. But you should consider whether one or more other tests should be included in your submission.

Warning: this may take a while to run, especially if you are using a 32-bit system. If you have a very recent, very fast CPU it shouldn't be too long, but if you have an older, low-power CPU, you should maybe start this up before you go out for a meal.

Did you use functions in any of these questions? Should you have? Did you document them correctly?

Does you program "blow up" on unexpected input, or does it deal with bad input in a "graceful" way?

How does your program deal with boundary conditions, if there are any?

Did you remember to put all required comments in? Does your program call out for any other comments in the body of the code?