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
meaning D# played for 4 sixteenth notes. How did I get that? Well 1087 in binary is
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
or 4 in decimal. The notes rightmost 8 bits are the pitch and those bits are
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
./a.out < test.txt > output.txt
The output file should contain
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
With the same input, the hacker edition would output
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
The hacker edition would output
Part 2 – Implementing a stack
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.
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:
Your program should output
The commands you need to implement are as follows:
Push a number onto the stack, printing nothing. For example, PUSH 5, pushes the number 5 onto the stack.
Pops a number off the stack and prints it followed by a newline. If the stack is empty POP will print the string NULL.
Prints the top number on the stack. If the stack is empty it will print the string NULL. It does not alter the stack
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
Again, calling PRINTSTACK on an empty stack will print nothing.
Removes all numbers from the stack
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.
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.
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.
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.
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.