COMP2017 9017
2 Introduction
Audio is a digitised waveform representing a sound. The sound has a frequency, which can be encoded
at a given sample rate, affecting the quality of the audio (bitrate). These properties are encoded as
sequences of amplitude values over time in memory.
Editing audio involves various operations such as clipping, inserting, and moving. Clipping refers
to selecting a portion of an audio file to keep or remove, inserting involves adding new portions at
specific points, while moving would change a portion’s relative position in time.
To support these operations, memory must be moved or copied and this can lead to inefficiencies.
Instead, an audio editor’s backend should use a shared backing store, where multiple operations ref erence the same underlying data.
3 Task
You will develop an audio editor backend that specialises in clipping and inserting data with a shared
backing - where changes made will affect all portions that reference it. Users of this software will
use the specified function prototypes to edit audio with simple operations. Your code should use data
structures and algorithms to efficiently support editing as well as the ability to read and write to a
buffer.
4 Structure
The audio data is sourced from a WAV file. The entire WAV file is read and stored into a buffer.
A track is a data structure that copies a continuous region of the buffer. A track can represent the
entire audio or specific parts.
Any number of tracks can be created and the track can contain metadata that is useful to support the
operations of this editor.
Each track is represented as an opaque data structure struct sound_seg that you must complete,
according to the needs of your implementation. Each structure represents one audio track.
// a track
struct sound_seg {
// TODO
};
The audio editor exposes functions in section 5, which you will complete.
The functionalities of your program are divided into parts with varying levels of complexity. Each
part has different requirements and is accompanied by specific assumptions. You should plan well for
a particular level of achievement before coding. Writing helper functions are encouraged.
You are also required to answer the short questions described in section 6.
Systems Programming Page 4 of 17
COMP2017 9017
5 Functionality
5.1 Part 1: WAV file interaction, basic sound manipulation
Conversion between a sound file and a track is a two-step process involving an intermediate buffer.
Functions to interact between WAV files and a buffer
void wav_load(const char* fname, int16_t* dest);
The wav_load() function reads raw audio samples from the specified WAV file fname and copies
them into the destination buffer dest. The WAV file’s header is discarded during the loading process,
leaving only the raw audio sample data in dest.
void wav_save(const char* fname, const int16_t* src, size_t len):
The wav_save() function creates or overwrite a WAV file, fname, using the audio samples pro vided in the source buffer src. The function constructs a valid WAV file, including the necessary
header, and writes the audio samples to the file.
Note: this function does not free the memory pointed to by src.
You can find more about the WAV file format here.
REQ 0.1: An existing sound file can be loaded from/to a buffer.
Testing method: sanity
ASM 0.1: the song will always be PCM, 16 bits per sample, mono, 8000Hz sample rate.
ASM 0.2: the provided path for wav_load(), wav_save() will always be valid. IO opera tions are always successful. dest will be large enough.
All other functions do not require reading a WAV file, and can be operated with int16_t arrays.
Functions to interact between a buffer and a track
struct sound_seg* tr_init();
void tr_destroy(struct sound_seg* track);
tr_init() allocates and returns heap memory for a new empty track. This function may also
initialise the structure to default values.
tr_destroy() releases all associated resources and deallocates the heap allocated pointer to
struct sound_seg.
REQ 1.1: tr_destroy() should free all memory the track is responsible for.
Testing method: random
Systems Programming Page 5 of 17
COMP2017 9017
size_t tr_length(struct sound_seg* track);
tr_length() will return the current number of samples contained within this track.
void tr_read(struct sound_seg* track,
int16_t* dest, size_t pos, size_t len)
tr_read() copies len audio samples from position pos in the track data structure to a buffer
dest. dest is an externally allocated buffer with guaranteed size of at least len.
void tr_write(struct sound_seg* track,
const int16_t* src, size_t pos, size_t len)
tr_write() function copies len audio samples from a buffer, src, to the specified position pos,
within the data structure track. Any previous data stored in the track for the range of pos to
pos+len is overwritten.
If the number of audio samples to be written to the track extend beyond the length of the track,
the track’s length is extended to accommodate the new data. Thus, a sequence of wav_load(),
tr_init(), and tr_write() effectively transfers a WAV file to a track.
An ordering requirement when performing writes is to always write to lower indices before higher
ones. This is only relevant for 5.3 onwards.
REQ 2.1: reads and writes make a copy of data from/to buf.
Testing method: sanity
REQ 2.2: write indices beyond the length of a track increases its length.
Testing method: random
You should make the functionality of tr_init(), tr_destroy(), tr_length(), tr_read(),
tr_write() your first priority. As the marking script uses them to check the behaviour of other
functions. Check section 7 for more details.
bool tr_delete_range(struct sound_seg* track, size_t pos, size_t len)
tr_delete_range() removes a portion from a track. The portion to remove begins at pos and
spans len samples. After deletion, subsequent reads of this track return the samples just before pos,
immediately followed by those at pos + len, effectively skipping the removed portion. On suc cess, delete_range returns true. A failure case exists if tr_insert() (5.3) is implemented,
and should return false.
Note: Samples removed by tr_delete_range() do not necessarily have to be freed from mem ory immediately, but should be freed when tr_destroy() is called.
REQ 3.1: reads and writes over deleted portion act as if adjacent parts are continuous.
Testing method: random
Prerequisites: REQ 2.2
Systems Programming Page 6 of 17
COMP2017 9017
Part 1 Checklist
1. Program is able to compile through makefile.
2. Using a main function, program is able to read a WAV file.
3. Using a main function, program is able to wav_load() and wav_save().
4. Program is able to dynamically create empty tracks.
5. length and read is functional.
6. write is functional.
7. delete_range is functional.
5.2 Part 2: Identify advertisements
There are different kinds of sound represented as audio and as with all computer science problems,
searching is essential. A search may identify a song of a bird in a natural setting, a musical tune,
or even spoken words. Fortunately, there are algorithms such as Cross Correlation2
that allow us to
analyse two digital waveforms and compute their similarity. Effectively allowing you to determine if,
and where, one sound appears in another.
In the modern world, audio media is often accompanied with an advertisement (ad). This is unwanted
noise and we do not accept this. You will identify and remove these ads using Cross Correlation.
You are to create a function to search for the existence and locations of an ad within a target track.
char* tr_identify(const struct sound_seg* target,
const struct sound_seg* ad)
Returns a dynamically-allocated string in the format of "<start>,<end>" indicating the start and
end indices of the ad occurrence in the target, inclusive. If there are no ads, return an empty string. If
there are multiple ads, return a string consisting of all the index pairs, separated by a single newline
character \n, such as "<start0>,<end0>\n<start1>,<end1>\n<start2>,<end2>"
REQ 4.1: tr_identify() is able to identify potentially-multiple, non-overlapping occur rences of ad in target.
Testing method: sanity
Prerequisites: REQ 2.2
Functionality is tested by directly overwriting portions of the target with copies of the ad, ensuring
identical amplitudes. The ads will always have the same amplitude and there is no scaling needed.
Functionality is tested by copying multiple ads over target, with their amplitude values summed."
Similarity is quantified by comparing correlation of the overwritten portion with the ad’s autocorre lation (cross correlation with the itself) at 0 relative time delay. As the reference, zero delay, this is
100% match. A portion is said to match if the ad is at least 95% of the reference 3
.
ASM 4.1: The occurrences of ads in target will be non-overlapping and sufficiently clear.
2
correlation with signals requires taking the complex conjugate, but as we are working with real signals, it
can be ignored and individual samples simply multiplied.
3
In the testcase, all correlation values larger than 95 are guaranteed to be ads. You do not have to consider
the case where correlation is larger than 100.
Systems Programming Page 7 of 17
COMP2017 9017
The return method for tr_identify() function is poorly designed. You may be asked to address
this issue with an explanation. See section 6 for more details.
Part 2 Checklist
1. Able to compute autocorrelation, the reference.
2. Able to compute cross-correlation and return string value(s).
5.3 Part 3: Complex insertions
The true value of the editor backend comes from mixing and clipping audio.
void tr_insert(struct sound_seg* src_track,
struct soung_seg* dest_track,
size_t destpos, size_t srcpos, size_t len);
tr_insert() performs a logical insertion of a portion from a source track into a destination track.
The portion to be inserted are len samples beginning at position srcpos in src_track. The
insertion point is at position destpos in dest_track.
After insertion, dest_track’s data before destpos remains unchanged, followed by the inserted
portion, and then the remaining original data from dest_track.
Note: This function is conceptually the inverse of delete_range().
This consequence of a tr_insert() operation results in a parent-to-child relationship. The parent
(src) and the child (dest) portions should have shared backing store and the data need only be stored
once, saving memory. Further insert() operations performed on the parent or child similarly
extend this shared backing, such that tr_write() to one sample in a portion of one track could
result in changes across many other tracks. As tr_delete_range and future tr_inserts do
not change track data but track structure, their changes are not propagated.
Note: for cases of self-insertions. The portion is determined at the time tr_insert() is called,
before the portion is inserted. Thus, inserting a portion into oneself is well-defined.
REQ 5.1: tr_insert() inserts a reference copy of src’s portion into dest
Testing method: random*. Due to complexity of this function, extra tiered restrictions have been
laid out - you may find that they significantly decrease programming complexity:
5.1.1: Every sample in the parent to be inserted, and samples adjacent destpos, shall not
already be a parent or child themselves.
5.1.2: Every sample in the parent to be inserted shall not already be a parent or child themselves.
5.1.3: Samples adjacent destpos shall not already be a parent or child.
5.1.4: Samples adjacent destpos shall not already be a parent.
5.1.5: Every sample in the parent to be inserted shall not already be a child.
5.1.6: No restrictions.
Prerequisities: all other requirements
Because the function tr_insert() operates on the same track, other functions must have stricter
requirements for the function to operate correctly.
Systems Programming Page 8 of 17
COMP2017 9017
For functions tr_read()/tr_write():
REQ 2.3: changes (write) to a child portion must be reflected in the parent, and vice versa
Testing method: random
For functions tr_delete_range()/tr_destroy():
REQ 3.2: A parent portion may not be deleted if it has children. Attempts to do so return
false. tr_destroy() nonetheless removes the portion.
Testing method: random
ASM 0.3: tr_destroy() will only be called at the end of the program, on all tracks to free
memory.
You should use a linked data structure to implement tr_insert.
Part 3 Checklist
1. Implement the trivialised version of tr_insert() by copying sample data (wasteful data
duplication).
2. Understand and model the behaviour of tr_insert().
3. Implement tr_insert() at 5.1.1 level.
4. Ensure requirements for other functions hold.
5. Implement tr_insert() at 5.1.6 level.
5.4 [COMP9017 ONLY] Part 4: Cleaning Up
Too many tr_insert() operations can lead to confusing parent-child relationships. The following
function aims to alleviate this issue.
void tr_resolve(struct sound_seg** tracks, size_t tracks_len);
tr_resolve() conditionally breaks parent-child relationships for specified tracks. Given an array
of track references tracks, if a portion Pi is a direct parent to another, Pj, and both portions can be
found in tracks, this will break their relationship, such that:
• Pj is no longer a child.
• Pi is no longer a parent if it does not have other children.
In the trivial case, if both Pi and Pj exist in track T and tr_resolve was called on T, the track will
effectively be flattened and the previously shared memory of those portions becomes duplicated data.
Consider tracks A, B, C, D, E with a shared portion between them and the corresponding parent->child
relationships as A->B, B->C, C->D, A->E. If tr_resolve was called on {B, C}, then after
calling tr_resolve():
• B->C no longer exists.
• A->B still exists, as A was not provided. By similar logic, C->D also exists.
Systems Programming Page 9 of 17
COMP2017 9017
• A->E still exists, as neither A nor E were provided.
• The portion in B can now be delete_range’d, as it is no longer a parent.
• A is a parent maintaining the portion (as before)
• C becomes a parent maintaining the portion (duplicated as a result of breaking from B)
tr_resolve() has now effectively split the shared backing store into two. The portions in A, B, E
in one, and C, D in another.
If tr_resolve() was called on {A, C} or {A, E}, although they share the same memory back ing, nothing will happen as they do not have a direct parent-child relationship.
REQ 6.1: tr_resolve() removes every direct parent-child relationship if the list provided
contains both parent and child.
Testing method: random.
Test case is private. Please write your own to verify.
Prerequisites: REQ 5.1
5.5 Performance
Memory usage and leaks are tracked in your program by dynamically replacing symbols malloc,
calloc, realloc and free.
4 You should only use the above standard dynamic memory allocation
functions.
Random testcases for tr_insert() enforce a max dynamic memory usage.
5.6 Global assumptions
To simplify logic, you can ignore index bounds checking.
ASM 7.1: indices covered by tr_read(), tr_delete_range(), and srcpos and len in
tr_insert() are always in range.
ASM 7.2: The starting position for tr_write() and destpos for tr_insert() ranges
from 0 to the target track length, inclusive.
6 Short answer questions
As part of the in-tutorial code review in week 8, you are required to analyse your code and prepare
for two of the below questions. You must supplement your answer with references to your code.
The examiner will also ask follow-up questions based on your response. COMP9017 students must
answer Q4.
Q1: How may you redesign the function prototype for identify, such that it more robustly returns
the list of ad starts and ends?
4Note that some functions, like printf, also use dynamic memory. Do not call them in your submission.
Systems Programming Page 10 of 17
COMP2017 9017
Q2: Referring to REQ 1.1, how did you identify which track is responsible for which memory, and
how did you ensure that all memory is freed? If you were not successful in ensuring, how did you
plan to?
Q3: [COMP2017 ONLY] Explain the time complexity of your tr_insert() and tr_read()
by referring to the relevant parts of your source code.
Q4: Demonstrate how you constructed test cases and the testing methods used to confirm your pro gram functions correctly. If you answer this question, the testcases must be in your final submission
in a folder named tests, and all tests should be run by the file tests/run_all_tests.sh.
7 Marking
7.1 Compilation requirements
Using the make program, your submission should compile into an object file, which the user/marker
will utilise.
Your submission must produce an object file named sound_seg.o using the command
make sound_seg.o. The marking script will compile this into a shared library to be used. Thus,
the flag -fPIC must be added.
You are free to (and encouraged to) add extra build rules and functions for your local testing, such as a
main function or debug flags. ASAN is encouraged during local testing, and will be automatically
added to your final submission.
5
When marking your code will be compiled and run entirely on the Ed workspace. The marker will
run the aformentioned make commands to compile your program and run the executable. If it does
not compile on the environment, then your code will receive no marks for your attempt. When
submitting your work ensure that any binary files generated are not pushed onto the repository.
7.2 Test structure
After your object file is compiled into a shared library, python scripts (ctypes) are used to interact
with the functions described in spec. In most cases, the script is responsible for:
• Creating temporary data,
• Orchestrating calling of functions,
• Comparing returned data with expected values.
This is used for both sanity and random tests. Thus, you can think of the test inputs and outputs as
not given from a separate program (and waits for you own program to respond and exit), but rather
driven in the same program, and the outputs are validated before your program ends.
5The marking script will attempt to add ASAN and PIC during compilation by appending the flags
-fno-sanitize=all -fPIC -Wvla -Werror -fsanitize=address -g. If this is not success ful, marking will silently fail.
Systems Programming Page 11 of 17
COMP2017 9017
7.3 Seeded testcases
All *_random testcases have the following structure:
1. random amount of tracks are created.
2. a random array is written to each track using tr_write().
3. a random operation between tr_write(), tr_delete_range(), and tr_insert() is
chosen if allowed.
4. tr_length() and tr_read() is done on random tracks and verified against expected val ues.
5. repeat random operation and verification for some cycles.
6. all tracks are properly managed where tr_destroy() is called and implemented correctly.
Memory leak check.
7. return value is checked (non-zero indicates failure). 6
If a failure is reached, the marking script attempts to return the input set that caused the failure, which
you can use locally to debug. Additionally, you are also able to manipulate random testcases for your
own testing - details have been provided in the EdStem lesson.
For each random testcase in a submission, the seed used is included in the feedback section and can
be used to deterministically regenerate inputs. During the marking phase, a predetermined set (15+)
of seeds will be used and the percentage passed will become your final mark for a specific test. The
assignment EdStem lesson provides more details for configuring random testcases.
From rudimentary analysis, passing insert_no_overlap_*_random for a single seed implies
you will also pass 95% of other seeds, and passing other random tests for a single seed implies 99+%.
If you only submit once and all 7 random testcases pass, you would expect a HD mark with very low
variance. Submitting more than once, and thus testing using multiple seeds, greatly increases this
confidence level; but even if you only submit once, the confidence of passing the reserved seeds far
exceed the confidence of passing a private testcase if only a static testcase is used.
All final test inputs will be posted after 17 April.
7.4 Marking criteria
The assignment is worth 10% of your final grade. This is marked out of 20, and breaks down as
follows. For marks awarded per testcase, please refer to Edstem.
Marks Item Notes
3/20 Code Style Manual marking
5/20 5.1 Correctness Automatic tests
4/20 5.2 Correctness Automatic tests
8/20 5.3 Correctness Automatic tests
For style, refer to the style guide. You will also be marked based on the modularity and organisation
of your code. For full marks, code should be organised in multiple source files, and use modular,
6Thus, please don’t return a nonzero value upon program exit.
Systems Programming Page 12 of 17
COMP2017 9017
task-specific functions. Organised data structures are essential here. Style marking is only applied for
reasonable attempts (5.1 Correctness).
[COMP9017 ONLY] 9017 students will have their above marks scaled by 0.9. 5.4 Correctness counts
for 2/20.
7.5 Restrictions
To successfully complete this assignment you must (submissions breaking these restrictions will re ceive a deduction of up to 6 marks per breach):
• The code must entirely be written in the C programming language.
• Must use dynamic memory for tracks.
• Free all dynamic memory that is used.
• NOT use any external libraries other than those in libc.
• NOT use VLAs.
• NOT have unclean repositories. This means no object, executable, or temporary files for any
commit in the repository, just your final submission.
• Only include header files that contain declarations of functions and extern variables. Do not
define functions within header files.
• Must use meaningful commits and meaningful comments on commits. 7
• Other restricted functions may come at a later date.
• Any and all comments must be written only in the English language.
• NOT manually use return code 42, reserved by ASAN.
The red flag items below will result in an immediate zero. Negative marks can be assigned if
you do not follow the spec or if your code is unnecessarily or deliberately obfuscated:
• Any attempts to deceive or disrupt the marking system.
• Use any of the below functions. You shouldn’t need to use these functions at all in your pro gram, and you are doing something terribly wrong if you are.
– _init, atexit(2), _exit(2), _Exit(3)
– dlopen(3), dlsym(3), dlclose(3)
– fork(2), vfork(2), execve(2), exec*(3), clone(2)
– kill(2), tkill(2), tgkill(2)
– getpid(2), getppid(2), ptrace(2), getpgrp(2), setpgrp(2)
8 Submission Checklist
• Submission have a valid makefile with the rule sound_seg.o and compiles.
• Reviewed all restrictions (not all are automatically checked)
• Program is organised into multiple source and header files (for larger programs).
• Not include any object file, binary, or junk data in your git repo.
• If you have used AI, references.zip formatted according to EdStem slides submitted with
source code.
7
"forcing the seed of a testcase" does not count as valid commit. Must cite reason and identified failure.
Systems Programming Page 13 of 17
COMP2017 9017
Glossary
assumption shortened: ASM. A property that is externally guaranteed to be true when your program
is run. When testing, situations which violate this property will not happen. Thus, handling
behaviour that falls outside of an assumption (e.g. out of bounds read) will not give you
marks. 4
child A portion that has been inserted from another part of a track. The portion is the child to the
portion that it was copied from. A sample may only belong to one parent. writes to the child
must be reflected in the parent. 8–10, 14
parent A portion that has been inserted into another part of a track. The portion is the parent to
only portions that exist due to that insert. A portion may be a parent to multiple children.
writes to the parent must be reflected in the childen. After inserting, it is possible for a parent
portion to be not contiguous. 8–10
portion refers to a part of a track. Contains zero or more samples. Portions are defined logically
rather than their indices in a track. Indices of portion samples may change if a delete_range
or insert modifies the length of the track.. 6–8, 14
random Property-based testing that test for the specified requirement, with inputs restricted by as sumptions. In this assignment, the python library hypothesis is used. 5, 8, 11, 12
requirement shortened: REQ. A property that your program is expected to hold when run. Marks
are given depending on how well your program holds them. Most requirements in parts 2 and 3
have prerequisites, properties that need to hold before the the current requirement is considered.
4
sample Audio is a digitised waveform representing a sound. The sound has a frequency, which can be
encoded at a given sample rate. A sample is simply a numberic value representing the strength
of sound at a particular time. In the context of this assignment, the data type for a sample is
int16_t.. 5, 7, 14
sanity A directed testcase targeting a specific functionality. For example, a sanity test for REQ 2.1
may be to create a track, write into it, modify the original buffer, then verifying if the buffer
and the track contents are different. Randomness may still be involved. 5, 11
shared backing store A shared backing store is a memory management technique where multiple
references to the same underlying data are used instead of copying or moving memory. . 4, 8,
10, 15
track A struct sound_seg object. It represents the user’s view of the API as users mix the
different objects together. 4–7, 10–14
Systems Programming Page 14 of 17
COMP2017 9017
9 Appendix
9.1 Worked function example
Parent track
Child track
Figure 1: This example uses two tracks. They are created and filled using a sequence of tr_init,
and tr_write of data.
Parent track
Child track
Parent track
len len+50
child_len
tr_write(parent, data, len, 50);
Figure 2: Either track can be extended via a call to tr_write. By calling write on the end of the
parent, new data is effectively concatenated.
Child track
Parent track
parent_len
s1
d1
child_len+len
spos1 spos1+len
dpos1 dpos1+len
tr_insert(parent, child, spos1, dpos1, len);
Figure 3: The initial insert extracts a portion s1 from the parent, and places the portion into the child,
also extending it. Due to shared backing store, there is a logical relationship between s1 and d1.
Systems Programming Page 15 of 17
COMP2017 9017
Child track
Parent track
parent_len
s1
d1
child_len+len*2
spos1 spos1+len
dpos1+len dpos1+len*2
s2
d2
spos2 spos2+len
dpos2 dpos2+len
tr_insert(parent, child, spos2, dpos2, len);
Figure 4: A second, overlapping insert occurs, placing d2 before d1. Note that 1) while the child is
extended and indices for d1 changed, the logical relashionship remains. 2) the overlapping samples
of s1 and s2 means that parts d1 and d2 (highlighted in purple), even though unrelated, also share
samples.
Child track
Parent track
parent_len
s1
d1
child_len+len*2-10
spos1 spos1+len
dpos1+len-10 dpos1+len*2-10
s2
d2
spos2 spos2+len
dpos2 dpos2+len-5
tr_delete_range(child, dpos2+len-5, 10);
Figure 5: tr_delete_range will fail if any of the specified samples is a parent (in this case, s1
and s2. Child samples such as a part of d2 can still be deleted (the command deletes the last 5
samples of d2, and 5 samples after the end, for 10 total). Because d2 no longer contains the last 5
samples, The last 5 samples of s2 (in red) also stops being a parent; there is no immedate change,
but those samples can now be deleted. Again noticed how the indices for d1 were shifted without
impacting the parent-child relationship.
Systems Programming Page 16 of 17
COMP2017 9017
10 Version history
We aim to resolve all spec updates within the first 3-5 days.
22/03/2025-23:07
• Clarified matching criteria for tr_identify.
• Removed const qualifier from tr_insert.
• Changed ASAN requirement from strictly forbid to strictly allow.
19/03/2025-11:12
• Clarify that most functions only interact with int16_t buffers, not WAV files, multiple times
in the spec
• clarified definition of sample, in the case of this assignment analogus to int16_t.
• If you plan to answer Q4 short answer, you must upload a folder called tests with your tests
in them.
• Added some banned function restrictions, which already exist in the testcase.
• Added prerequisite to tr_resolve
• Reworded tr_identify from "ads overwriting target" to "ads inserted on top of target".
Such that the ads in the target aren’t exactly the same.
14/03/2025-10:35
• Created version history.
• Added detailed description of marking process with python.
• Reword dest in REQ 5.1 to destpos.
• correct return value of tr_destroy from bool to void.
• Define what an unclean repo is.
• Clarfied that code must be written in C, and compile in EdStem.
• Improve wording of tr_resolve from "previously shared memory becomes duplicated data"
to "previously shared memory of those portions becomes duplicated data", to clarify only spe cific portions are flattened.
• Created submission checklist.
• Added suggestions of extra makefile rules for students’ own testing.
• Added linked to EdStem slides about manipulating EdStem testcases, and submitting AI refer ences.
• Added -Wvla -Werror as implicit compilation flags.
Systems Programming Page 17 of 17
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
