CPSC405 Fall 2012 Project 1
Due
Turn in by Friday 7 September for 10% bonus XP
Absolute Due date: 14 September.
Part 1: Bitwise operators and a music synth
Last year I was looking at some music software someone wrote. The melody was contained in a compressed file. When I uncompressed it, the file consisted of a single 2 byte integer per line. Each integer represented one note’s pitch and duration. The bit structure of the integer is as follows:
d d d d d d d d p p p p p p p p
The p byte represents a notes pitch. Note’s are numbered starting with a low C being note 0. The C above that then is represented as 12.
For example, the integer 63 (00111111) represents the note 63. The d byte represents the duration of the note in 16th notes. For example, 00000100 represents a note whose duration is 4 sixteenth notes. You are to write a program that takes as input a sequence of lines as described above and outputs (to standard out) the note number and duration separated by a tab.
For example, if 1087 is input you are to output
63 4
meaning D# played for 4 sixteenth notes. How did I get that? Well 1087 in binary is
00000100 00111111
Looking at the bit structure given above and repeated here
d d d d d d d d p p p p p p p p
I see that the first (leftmost) 8 bits represent the note’s duration (what ‘d’ stands for in the bit pattern) and the last (rightmost) 8 bits represents the note’s pitch. So the note’s duration is
00000100
or 4 in decimal. The notes rightmost 8 bits are the pitch and those bits are
00111111
or 63,
So I output 63 4.
If I have my test cases in the file test.txt the following should work: ./a.out < test.txt
If I have a file test.txt containing
24639
1085
571
576
575
And execute
./a.out < test.txt > output.txt
The output file should contain
63 96
61 4
59 2
64 2
63 2
Note: there is a single tab character between the numbers and no space before the newline.
Note 2: Full XP will only be given to solutions using bitwise operators (e.g., &, <<, and/or >>). Want to know more about bitwise operators? Puzzle over this program. What does it output and why?
#include <stdio.h> #include <stdlib.h>
int main(int argc, char *argv[])
{
int bitmask = 56;
int i = 501;
i = bitmask & i;
i = i >> 3;
printf("%i \n", i);
}
Part 1: Hacker edition (optional)
Create a new program based on your solution for the above which outputs note names and octaves. For example, as mentioned above Low C is represented by a 0 and your program above would output ‘0’. For this hacker version you would output the note name (‘C’ in this case) along with the octave (0 in this case). For example, given the text file:
The program above would output
0 4
12 4
24 2
36 2
48 2
With the same input, the hacker edition would output
C0 4
C1 4
C2 2
C3 2
C4 2
Why? Think of a piano keyboard.
In this example picture the keyboard starts (leftmost note) with C in the lowest (0) octave. If this ‘C’ is represented by 0 then when we have a pitch of 0 in the input, we output C0 (C in the zero octave). If we march up the keyboard note-by-note (C, C#, D, D#, E …) when we get to 12, we are at C again this time at octave 1. So for a pitch of 12 we output C1, a pitch of 24, we output C2, and so on. If we encounter a pitch of 26 we would output D2.
With the input
24639
1085
571
576
575
The hacker edition would output
D#5 96
C#5 4
B4 2
E5 2
D#5 2
Part 2 – Implementing a stack
Introduction
In previous classes you covered the basics of pointers, allocating memory from the heap, and writing code for linked lists. In this class we covered how these basics work in C. For example malloc(sizeof(int)) allocates memory from the heap and free(memorypointer) deallocates memory. This assignment is geared at applying your pointer/memory skills to C.
Task
The program template you should use is template.c Your task is to implement a simple stack based reverse Polish notation calculator using a linked list. For example, if I type the 4 lines:
PUSH 5
PUSH 4
ADD
POP
Your program should output
9
The commands you need to implement are as follows:
PUSH
Push a number onto the stack, printing nothing. For example, PUSH 5, pushes the number 5 onto the stack.
POP
Pops a number off the stack and prints it followed by a newline. If the stack is empty POP will print the string NULL.
PEEK
Prints the top number on the stack. If the stack is empty it will print the string NULL. It does not alter the stack
PRINTSTACK
Prints the entire stack starting from the top. Each number is on a separate line followed by a newline. If the stack is empty PRINTSTACK will print nothing. For example
PUSH 19
PUSH 50
PUSH 21
PRINTSTACK
will print
21
50
19
Again, calling PRINTSTACK on an empty stack will print nothing.
CLEAR
Removes all numbers from the stack
ADD
pops 2 numbers from the stack, adds them, and puts the result on the stack. If there are not two numbers on the stack nothing is pushed on the stack and nothing is printed.
SUBTRACT
Pops one number from the stack (n1); pops another (n2); subtracts n1 from n2 and puts the result on the stack. If there are not two numbers on the stack nothing is pushed on the stack and nothing is printed.
Examples
Should output
29
48
The following
POP
PUSH 19
PUSH 50
PUSH 21
PRINTSTACK
SUBTRACT
PEEK
ADD
POP
POP
Should output
NULL
21
50
19
29
48
NULL
How to submit
Submit your code to the Submit-O-Matic. Each part must be submitted separately. You can submit your code multiple times to get the score you want.
Points awarded:
Part 1
30XP for code that produces correct Submit-O-Matic results, uses bitwise operators, and is well-structured. 5 points will be deducted if you do not use bitwise operators. If your code produces correct results locally but does not produce correct results on Submit-o-Matic you can get15 XP. -1,000 points if your program produces an infinite loop on Submit-O-Matic
Part 1 Hacker edition.
10XP for code that produces correct Submit-O-Matic results.
Part 2
65XP for code that produces correct Submit-O-Matic results and code review shows understanding of linked lists and dynamic memory allocation. 5XP additional for well-structured, well-commented code. 25XP if your code produces correct results locally.