avatar tianjara.net | blog icon Andrew Harvey's Blog

Entries from June 2009.

Deque Implementation Design
29th June 2009

For Assignment 1 of COMP2911 we got the task of implementing a deque, using arrays and linked lists (in Java). Here is the design I used for the implementation.


This was quite a challenge.

One approach was to have an array of size capacity, and also store some left and right index pointers to know where the deque ranges in the array.


My first idea (actually inspired by my tutor) was basically, to add to the right of the deque you start at the left and push right, to add to the left of the deque you start at the right and push left. When the two ends collide, you make a new array larger keeping the left and right parts of the deque at the leftmost and rightmost parts of the array.

series1This turned out to have some problems. All worked well, except for a couple of things. Such as show here,

series2, because now you are left in the middle and your not just pushing straight from one side to another.

This next situation below was also troublesome because you have to be careful where you store your left/right index pointers. You need to carefully think of what if they overlap? And if they are equal or overlap, is your arrayDeque full or empty?

series3iSo what I did is look at the different ways to store the left/right index pointers. In all these diagrams orange means the location of the left index pointer, and the violet is the location of the right index pointer.

a) In this diagram I point to the next available space.

series3i1b) In this diagram I point to the location of the most recently added item. At the very beginning I loop them over.

series3i2All this just lead to much confusion for me and many bugs and problems. So I had a look at an entirely new approach. It turned out much better, and I learnt that if things aren't working out and you just keep getting lots of bugs then sometimes trying another approach can really help out. I also learnt that its really hard to know the best way to do something right from the start you really have to try something and if its not working to well than just try something else and see how it goes. So here is what I finally did.

db_1Initially I just ignored the fact that I had a limited size array, and that things are actually mod array size. I just had two index pointers (shown in orange and blue) which pointed to the next free space at the left and right ends of the deque. I kept these as ints and they I don't think of them as wrapping round. If you forget about the array based implementation and go back to the original problem of a deque you see that really all you need is a big long line with a left end and right end pointer. Now all you have to do is remember that whenever you are dealing with implementation level things such as accessing the array, to use index mod capacity, rather than the raw index value (which may be out of the array range). That and you need to have a check to know when to resize your array.

Under this scheme the number of items in your deque is rightIndex - leftIndex - 1, therefore your array is full if and only if (rightIndex - leftIndex - 1) >= capacity. (Where capacity is the size of the array). If this is true then you need to resize your array.

The method I choose was to simply shift the deque along (either direction) so that the leftIndex is at -1.


This was much simpler. Basically I made a link object that stored an item and a left and a right pointer (to other link objects). I would store the leftmost and rightmost link items for the deque and that is all. I guess I could have stored size as part of the deque object and updated it whenever new link items were added or removed to the deque, but as we were given no requirements to do it one way or another I made it so that the size method would go though the whole deque and do a summation every time it was called.

The only thing I really had to watch was to ensure that I kept the left and right pointers for each link item up to date with changes, and this was my primary source of bugs.

Tags: comp2911, computing.
Very Useful Ubuntu/Unix Commands
29th June 2009

Just some Ubuntu/Unix commands that I seem to find very useful but can be hard to remember at times.

PDF Concatenation

pdftk in1.pdf in2.pdf cat output out1.pdf

Its annoying that nautilus doesn't integrate this by default, so I could select some PDF's then right click and choose merge. Luckily I can do this with the fairly simple Nautilus Actions Configuration app. But this takes time and the average user doesn't have the time to research these things on how to do it themselves. Of course this could be extended further to match what you can do from the command line, such as choose some method of ordering the files, or choose to do weird things such as rotate every second page. Sure you want to keep things simple, so as a start it would be great to see something basic. There are probably even nautilus scripts in the repositories out there that do this exact thing, but you spend half your time finding them and installing them. I think this should be enabled by default, or put in some options page somewhere.

Truncate an mp3 file

mpgsplit input.mp3 [00:00:20-00:00:58] -o output.mp3

It appears that this doesn't re-encode so it seems to run very fast.

Mount an ISO

sudo mount -o loop ~/disk.iso /media/cdrom0

Strip audio from a video file

ffmpeg -ab 320k -i in.mov outaudio.mp3

Unfortunately when I left out the bit rate, it defaulted to 14K or something much lower than what the source file was using.

Search all files in the current directory for some string

find . -exec grep "searchthisstring" '{}' \; -print
find . -exec grep -q "searchthisstring" '{}' \; -print

Trim and nup pdfs

pdfnup --nup 2x2 --pages 26-140 --trim "1cm 1cm 1cm 1cm" infile.pdf

Wake from Suspend

sudo rtcwake -u -s 12600 -m on

... then you need to manually put the computer in suspend and 12600 seconds later the computer will resume.




sudo shutdown -h now sudo shutdown -r now

... the -h means halt (shutdown), -r means reboot.

Tar and Gz all the files in a directory

tar -cvfz file.tar.gz *

Get file info from an HTTP server without downloading

wget -S --spider http://www.site.com/file
Tags: computing, linux.
SBS Latest Online Video RSS Feed
28th June 2009

[An updated (but more complex) script can be found in this post]

I needed an excuse to practice some Perl. So this was my first try.

The Perl script below will convert http://www.sbs.com.au/shows/ajax/getplaylist/playlistId/94/ to an RSS feed. That 94 playlist is a list recent episodes from the TV broadcaster SBS available online. This may not work if the source file's structure changes.


# This script will download the ajax xml file containing the latest full episode videos added to the SBS.com.au site.

#Adapted from the code at http://www.perl.com/pub/a/2001/11/15/creatingrss.html by Chris Ball.

# I declar this code to be in the public domain.


use strict;
use warnings;

use LWP::Simple;
use HTML::TokeParser;
use XML::RSS;
use Date::Format;

# Constants
my $playlisturl = "http://www.sbs.com.au/shows/ajax/getplaylist/playlistId/94/"; # Latest Full Ep
#my $playlisturl = "http://www.sbs.com.au/shows/ajax/getplaylist/playlistId/95/"; # Latest Sneek Peek

# LWP::Simple Download the xml file using get();.
my $content = get( $playlisturl ) or die $!;

# Create a TokeParser object, using our downloaded HTML.
my $stream = HTML::TokeParser->new( \$content ) or die $!;

# Create the RSS object.
my $rss = XML::RSS->new( version => '2.0' );

# Prep the RSS.
 title            => "SBS Latest Full Episodes",
 link             => $playlisturl,
 language         => 'en',
 lastBulidDate    => time2str("%a, %d %b %Y %T GMT", time),
 description      => "Gives the most recent full episodes avaliable from SBS.com.au"

 title    => "sbs.com.au Latest Full Episodes",
 url    => "http://www.sbs.com.au/web/images/sbslogo_footer.jpg",
 link    => $playlisturl

# Declare variables.
my ($tag);

# vars from sbs xml
my ($eptitle, $epthumb, $eptime, $baseurl, $img, $url128, $url300, $url1000, $code1char, $code2char, $code1);

#get_tag skips forward in the HTML from our current position to the tag specified, and
#get_trimmed_text  will grab plaintext from the current position to the end position specified. 

# Find an <a> tag.
while ( $tag = $stream->get_tag("a") ) {
 # Inside this loop, $tag is at a <a> tag.
 # But do we have a "title" token, too?
 if ($tag->[1]{title}) {
 # We do!
 $eptitle = $tag->[1]{title};
 #print $eptitle."\n";

 # The next step is an <img></img> set.
 $tag = $stream->get_tag('img');
 $epthumb = $tag->[1]{src};

 #get the flv urls from the img url
 #eg. http://videocdn.sbs.com.au/u/thumbnails/SRS_FE_Global_Village_Ep_19_44_48467.jpg
 #print $epthumb."\n";
 $baseurl = substr($epthumb, 40, length($epthumb)-40-4);
 $url128 = "http://videocdn.sbs.com.au/u/video/".$baseurl."_128K.flv";
 $url300 = "http://videocdn.sbs.com.au/u/video/".$baseurl."_300K.flv";
 $url1000 = "http://videocdn.sbs.com.au/u/video/".$baseurl."_1000K.flv";

 $code1char = substr($baseurl,0,3);
 $code2char = substr($baseurl,4,2);

 my %epcode_hash = (
 'DOC'    => 'Documentary',
 'MOV'    => 'Movie',
 'SRS'    => 'Series',
 $code1 = $epcode_hash{$code1char};

 $tag = $stream->get_tag('p');

 # Now we can grab $eptime, by using get_trimmed_text
 # up to the close of the <p> tag.
 $eptime = $stream->get_trimmed_text('/p');

 # We need to escape ampersands, as they start entity references in XML.
 $eptime =~ s/&/&amp;/g;

 # Add the item to the RSS feed.
 title         => $eptitle,
 permaLink     => $url1000,
 enclosure    => { url=>$url1000, type=>"video/x-flv"},
 description     => "<![CDATA[<img src=\"$epthumb\" width=\"100\" height=\"56\" /><br>
 Links: <a href=\"$url128\">128k</a>, <a href=\"$url300\">300k</a>, <a href=\"$url1000\">1000k</a><br>
 Type: $code1<br>]]>");

print "Content-Type: application/xml; charset=ISO-8859-1"; # To help your browser display the feed better in your browser.
#$rss->save("sbslatestfullep.rss"); #this will save the RSS XML feed to a file when you run the script.
print $rss->as_string; #this will send the RSS XML feed to stdout when you run the script.
Tags: rss.
SENG4921 - Oral Exam Prep
27th June 2009

Here are the notes I made for and took into the SENG4921 oral exam.

As an after thought, you can see I wasn't prepared for all the options but this is the best I could do in the time. Some of my arguments here may not be very valid, but this is my preparation as it stands, not a blog post into the questions (that's my excuse for being sloppy).

Question 1: free choice

"Each student should prepare a topic of their own free choice concerned with some aspect of software, hardware, IT professional issues or ethics. This could be —but does not have to be— based on, or derived from, the discussions, seminars, debates, student run seminars and lectures given this semester. The question should be broad enough to not overlap with the other two questions. At the examination the student will be asked to present his/her topic and discussion.
If the free choice question deals directly with one of the Seminar or Lecture questions, then this will generally eliminate that question if one of the randomly chosen 3 for question 2 or 3. Note carefully that the elimination occurs after the random choice, not before."

After a little thought I think I will focus on DRM in this question. I think this is a good choice because,

  1. Its not covered in the other seminar and lecture questions,
  2. I know enough about the topic to be able to talk about it,
  3. There are actually some valid ethical questions that can be raised and debated here,
  4. ...

So the deal is I only have 5 minutes to talk about the professional issues and ethics surrounding DRM. I need to identify the issues involved, analyse the professional and/or ethical consequences and present the outcome. I will need to be careful that I address the right things as I only have 5 minutes.

The examiners will be looking for:
  • clear identification of the issues;
  • analysis of the professional and/or ethical consequences;
  • careful presentation of the outcomes.
There are no correct answers, but a good answer will give a clear indication of consequences and issues.

Identification of Issues

DRM is digital rights management. DRM technologies attempt to control use of digital media by preventing access, copying or conversion to other formats by end users.

Lastly DRM systems do not work, as most have been cracked. Once the DRM has been cracked by one person (who may be an expert) then can distribute this clean version to all over say BitTorrent. DVD's CSS was cracked,

From personal experience a while ago I downloaded an e-book (actually a standards document) from the UNSW library/publisher of the standard. It was a PDF document and they told me that it would expire after a week or so. It turns out that it used some JavaScript hide the text when the system date was at whatever was a week after the PDF was downloaded (so the web server was creating the PDF on the fly putting the expiry date and the download details into the PDF). This could be easily bypassed by disabling JavaScript, using a free PDF reader that does not support JavaSript, and so on. Furthermore you could easily use some software to extract the content of the PDF and resave it without the DRM. (Will I go to jail if I ever vist the US because of the DMCA?? Or even from Australian laws?)

Professional and/or ethical consequences

Ken noted in his introduction article that "In this course, we will be particularly concerned with developing your capacity to reason about the possible outcomes." Hence I will try to focus on the affects/consequences of DRM. Taking a consequential approach to ethical thinking requires one to consider the possible consequences. So some consequences of DRM that should be addressed when taking a ethical approach to DRM are,

These are all possible outcomes, yet they may not all be an ethical concern. This depends on your individual ethical principles. For me if DRM leads people to move to pirated material rather than paying the owner, then this under my ethical principles this is not a concern. This is strictly a business move and the consumer will not be harmed by doing this. If the company doesn't want people to pirate the matrial instead of buying it then they can simply remove their DRM and sell it DRM free.

But from a utilitarian perspective, DRM does little to stop the original creator receiving remuneration (if anything it may result in less remuneration), instead it causes great unhappiness. In this respect it is unethical.

As Cohen outlined professions come with these extra "professional" responsibilities. Including "public interest is paramount", public trust, but also client's interests. Most (if not all) DRM systems are not in the public's interest. They are riddled with problems and do very little to stop piracy. They turn honest customers into outlaws. The key thing that consumers need to be aware of is they are not purchasing products from the iTunes store rather they are purchasing a licence to use the music in a restricted set of conditions.

Question 2: Seminar Questions

1. "Engineering"

I think Wikipedia's summary of Engineering describes what is generally understood by the term 'Engineering'.

Engineering is the application of scientific and technical knowledge to solve human problems. Engineers use imagination, judgement, reasoning and experience to apply science, technology, mathematics, and practical experience. The result is the design, production, and operation of useful objects or processes.

Of course as a profession it comes with all the things that make it a professions such as responsibility to the public, client's interest, public trust, an so on.

Software and Computer Engineering can claim to be engineering professions as they meet this description of Engineering that I just quoted. Software and Computer Engineers apply scientific (mostly mathematical, or even Computer Science if you want) and technical knowledge to solve problems. They use experience and so no to apply this to the task at hand. They also do a lot of design work and the actual production of the software/hardware.

Computer programming vs. Software Engineering vs. Software Development

As a job title. Sure your official job title may be "Computer Programmer" or you may graduate with a "Computer Science" degree. That doesn't mean you never do any "engineering".


My opinion of what is generally understood by "Engineering" as a profession is (to quote Wikipedia here), "Engineering is the application of scientific and technical knowledge to solve human problems. Engineers use imagination, judgement, reasoning and experience to apply science, technology, mathematics, and practical experience. The result is the design, production, and operation of useful objects or processes." And of course as a profession it comes with all the things that make it a professions such as responsibility to the public, client's interest, public trust, an so on.


2/3. ACM Code of Ethics/Therac 25

4. Technical Issues with the Therac 25 Case

At the end of the day (as with many famous disasters) there were many times where if something was done better the problem may not have occured.

6. Killer Robot

Randy Samuels - Wrote the code that cause the robot to malfunction.

8. Intellectual Property

From an ethical analysis,

Affects Computer Scientists and Software Engineers.

From an economic view,

9. Datavallience

Two types of dataveillance.

Three examples,

Professionals have a responsibility to act in the public's interest (as well as the clients interest). They also have codes of ethics to adhear to. Many ethical principles would lead to the conclusion that the people who are having their information monitored should be notified of this. To act in the public interest, the public needs to know when they are being monitored. This gives them the choice, to either use encryption, stop using the service, or something else. However professionals should make an exception to this rule when the matter is of national security or something other when it can be justified that not notifying is acting in the publics interest. This is what ethics is all about. Dealing with these exceptions to the rule.

  1. What is dataveillance?
  2. Is it immoral to collect data about other people?
  3. What personal data is currently being collected?
  4. What new opportunities are there to collect even more personal data?
  5. How can dataveillance be regulated?
  6. What advice would you give to non-specialists about safeguarding personal information?

It depends on the situation. The ethical approach I subscribe to is that the person who is having data collected on them, should be made aware of what is being collected, and that it is being collected.

Question 3: Lecture Questions

1. Theoretical Underpinnings of Ethics

"Essentially, you are being asked to demonstrate how different ethical principles could be used to produce different outcomes.  The important part of your answer will be the identification of the different principles and how your reasoning would proceed from those principles."


And now on to the part relevant the the question at hand,

To make a moral judgement you need to make a judgement, have some justification for that judgement, and also have some principle that lead you to believe that that justification was right. (judgement > justification > principle) If you don’t have this, you don’t have a moral judgement.

2. Professionalism and Ethical Responsibilities

Other things of interest,

3. Open source from an Economical Approach

Closed source (Sales Force): For every $1 spent on software development, $10 is spent on marketing Open Source (SugarCRM): for every $4 spent on development, $1 is spent on marketing

6. Freehills Talk/Software Patents

Quick Summary

Ethical issues for Software Engineers/Computer Scientists

This comes down to your ethical principles. My ethical principle resolve around helping others, advancing knowledge, and working together for maximum benefit. So under my ethics software patents are unethical because they hinder the progress and development of (in the case of software patents), software. For example, someone patents the GIF encoding scheme, this can be used to lock out people from using this method. It also locks the scheme up so in the theoretical case where someone patents X, which lasts for 20 years. Person B invents X two years later but cannot use or distribute that invention because of the patent.

If you don't want others exploiting or using or building on your invention then don't share the details with anyone.

We are forgetting that many people (think Linux) don't need the incentive of a patent to invent things or make them useful to the public. Patents hinder the publics access to certain processes.

If everyone was free to take others hard work and put it to good use, and build upon it and share that then progress would move faster than ever before.

But this is just my view of the matter. I do grant that I have this view because for me, progress (in terms of new and better software, etc) comes by people working on their own will because they want to for the fun of it (an example open source software, much of it was done with little commercial incentive). No money is wasted on lawyers who make no progress to the field. Instead everyone can work on pushing progress forward.

The ethics is solid. In fact patents were originally designed very ethically. Look at the consequential utilitarianism approach.

But things have changed. Software patents have not helped with this.

Back to patents.

7. Law

Well as an ethical professional engineer you have an obligation/duty to act in the client's and the public's interest. As such you should notify the company of the situation and let them make a decision based on that. This is acting in the clients interest. Even with out this certain ethical principles such as openness may require you to notify the other party

Contrasted to an ordinary businessman who has no duty (thought they ought to do at least what is minimally decent) to act in the publics interest.

Different Standards when choosing to obey a law or not. Illegal? Litigation Risk? 'Professional' Standard(will your peers reject you)? Ethics(will your friends and children reject you)?

9. Internet Censorship


Professional/Ethical Ideas / Social/Technical

A social issue is over-legislating. eg. . For example certain materials (which probably includes child pornography) is illegal to view, so if you happen to accidentally find this material on the internet and you want to report it to the police so they can track down the perpetrator, you are in a conundrum. If you tell the police about it, then you must have viewed the material yourself which is illegal so you may face criminal charges, hence you cannot report it.

Another social issue. Is it just illegal content? Should the government be deciding what to view or not?

Technical Issue. What about things like VPN's, tor...? The internet is huge and dynamic? What about a tag system.

Tags: ethics, seng4921.
The Cause of Slow Loading Wordpress Pages Over https
24th June 2009

For as long as I could remember, loading pages in my wordpress.com blog dashboard was really slow. I should have realised what was happening sooner but I never took the time to investigate. Whether I went to the edit posts page (/wp-admin/edit.php), new post (/wp-admin/post-new.php) there seemed to be numerous connections back to wordpress.com once parts of the page were loaded. These requests were to s-ssl.wordpress.com. Taking a look at the source, all the css and js files linked to from the html of the page were over the https protocol, and rightly so because I always go over the https protocol. What I didn't realise is that Firefox will not cache files from https by default. So if I go to about:config and change browser.cache.disk_cache_ssl to true then these static css and js files will be cached. I restart my browers and all of a sudden pages load much faster and much more tolerable. The only problem is that its not just css and js files transfered over https that are cached but html files as well. I'm not sure how to get Firefox just to cache css and js files from https, but I have to leave that for another day.

Tags: web.
Re: 7.30 Report "Uncertain future for newspapers"
24th June 2009

Going through the backlog. Just a few comments on the 7.30 Report story (transcript) (video sorry for the format but its all I could see, I don't know where I got my m4v one from).

Very interesting stuff here, but I have a couple of points. Mind you I don't have much experience here, I'm not a journalist or an economist...

1. Government Subsidiary for Quality Journalism

One of my main concerns here is that you have two negative forces. On one hand you have the government paying for investigative journalism, but those journalists are having to fight the government to get the story to break. Would there be a need for investigative journalism in the government arena if the government was more open? You wouldn't need the journalist filing freedom of information requests if the department put this info into the public domain by default. The solution is for the government to be more open and transparent, something which they seem to do a lot of talk about (and are doing some things that make them open), but not nearly enough.

But the government or the government departments are probably unwilling to put information out there that may embarras them. Unfortuantly you probably need so driving for that motivates government departments to be more open. I see an online "village pump" where the community can gather and build up in numbers to support certain movements (such as access to certain statistics that may be part of a journalists investigation). Those numbers are a force that could provide pressure for an unwilling government department.

2. Coverage

Nick Davies said that "what you haven't got is citizen journalists covering the courts or the government departments or the police or the hospitals or the schools or doing investigations." He quoted lack of "skills, time or resources" as the reason for this. I don't believe this. A large chuck of the feeds I subscribe to are citizens blogging about copyright decisions made in court. Perhaps it is lack of cooperation of the government department. For example they charge huge unreasonable fees for your FOI application. I don't see the solution as get a big company who can pay the fees, rather use some other methods to pressure the department into providing the information needed for investigative journalism free or charge, free for all.

No tags
COMP2121 Quick Summary on Particular Aspects
23rd June 2009

Von-Newman vs. Harvard Architecture.

Von-Newman has a single memory space, share for data and program instructions. Harvard Architecture has separate memory spaces for data and instructions (so you cannot execute from the data memory).

2's compliment


It is important to know that the hardware does all arithmetic in 2's compliment. It is up to the programmer to interpret the number as signed or unsigned.

To convert a number from 2's compliment, for example -45 in 2's compliment is 11010011, we can do something like this,

$latex 1 \times (-2^7) + 1 \times 2^6 + 1 \times 2^6 + 0 \times 2^5 +1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = -45$

To go the other way from say -1 to the 2's compliment form 11111111 we use that $latex 2^p - X$ formula. I'm not exactly sure how its supposed to work so I've hacked it to make it work.

If the number you wish to convert is negative, let $latex X = -n$, so that X is positive then take $latex 2^p$ where p is the number of bits you are using (say 8), then subtract X. If the number to convert is less than $latex 2^p$ (where p is the number of bits, say 8 ) then leave it as is and that in your 2's compliment.

Now that was complicated. But its the only way I can get that advertised $latex 2^p - X$ formula to work with the given set of sample data (as in that table above).

Sign Extension

Why do we need sign extension? We need it in order to do operations on numbers than have different bit lengths (the number of bits used to represent the number).

Decimal to Binary

From a human kind of approach to convert 221 to binary, we see that $latex 2^7 = 128$, that is 7 is the largest power of 2 less than 221, so we have $latex 1 \times 2^7$. That gives us 128, so we still have 93 (221-128) to go. We try $latex 2^6$, this is less than 93. So far we have $latex 1 \times 2^7 + 1 \times 2^6$. 29 left now, but $latex 2^5$ is greater than 29, so we put a zero in that digit, ie. $latex 1 \times 2^7 + 1 \times 2^6 + 0 \times 2^5$. If we go on we get $latex 1 \times 2^7 + 1 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$. Taking the coefficients of the $latex \times 2^x$ terms we get the number 221 in binary, 11011101.

We can convert hexadecimal to binary by going from hex to decimal then decimal to binary. For hex to decimal,

$latex \mbox{F23AC} = 15 \times 16^4 + 2 \times 16^3 + 3 \times 16^2 + 10 \times 16^1 + 12 \times 16^0 = 992172$ (where F23AC is in hex and 992172 is in decimal)

Operations on Signed and Unsigned Multi byte Numbers

add al, bl
adc ah, bh
does a + b, result in is a.

There are 3 multiplication operations, MUL (Multiply Unsigned), MULS (Multiply Signed) and MULSU (Multiply Signed with Unsigned). They each do this. Notice the result is stored in r1:r0.

mulThus to do n*m = r where n is 2 bytes unsigned and m is 1 byte signed,
mulsu nl, m ;nl * (signed)m
movw rh:rl, r1:r0
mulsu nh, m ;(signed)nh * m
add rh, r0

We can also do 16bit * 16bit,

;* From AVR Instruction Set Guide, pg 99-100.
;* Signed multiply of two 16-bit numbers with 32-bit result.
;* r19:r18:r17:r16 = r23:r22 * r21:r20
clr r2
muls r23, r21 ;(signed)ah * (signed)bh
movw r19:r18, r1:r0
mul r22, r20 ;al * bl
movw r17:r16, r1:r0
mulsu r23, r20 ;(signed)ah * bl
sbc r19, r2
add r17, r0
adc r18, r1
adc r19, r2
mulsu r21, r22 ;(signed)bh * al
sbc r19, r2
add r17, r0
adc r18, r1
adc r19, r2

brge and brsh

Calculating Total Stack Space Needed

Draw a call tree, find the path with the most total weight, that total weight is the total stack size needed. Here is the sample question,

A C program consists of five functions. Their calling relations are shown as follows (the arguments and irrelevant C statements are omitted).

int main(void) {


int func1(…) {

int func2(…) {

func1() is a recursive function and calls itself 15 times for the actual parameters given in main(). Both func3() and func4() do not call any function. The sizes of all stack frames are shown as follows.

main(): 200 bytes. func1(): 100 bytes. func2(): 400 bytes. func3(): 1,400 bytes. func4(): 300 bytes. How much stack space is needed to execute this program correctly? (3 marks)

call_graphThere are three paths,
main() func1() func1() x 15 200+100+15x100 =1800 main() func2() func3() 200+400+1400 =2000 main() func2() func4() 200+400+300 =900
The path with the most total weight is main() > func2() > func3(), so this is the total stack space needed.

Nested Interrupts

nested_interrupt(Source: Hui Wu's Lecture Notes)

Keypads with 'abc' 'def' ... buttons

These keypads where to enter b you need to press the abc button twice in succession, but wait to long at it will chose a. Here is a psudo algorithm that seemed to fit this,

.def reg = rN
.def reg = rM
.def count = rX

//passvalue means that we register the given value ie. abc abc wait > b

clr reg (to some value that is != to a key value) ;set to default
clr count
rjmp keyloop

  check pins for a key
  if no key pressed rjmp keyloop, else continue

  //key was pressed, and value is stored in key
  reset someTimeCounter
  if (key == reg) {
     inc count
     if (count == 3)
     if (reg != default) ;so we don't initially passvalue
        passvalue(reg,count) ;send the last value
     reg = key ;store the new one
     count = 1

rjmp keyloop

if someTimeCounter expires and count != 0 //(count up, so expires after time to wait for anymore keypresses) (check count != 0, because if its 0 then we never had any key pressed that we need to send)
   reg = default

Switch Bounce Software Solution

When a switch makes contact, its mechanical springiness will cause the contact to bounce, or make and break, for a few millisecond (typically 5 to 10 ms). Two software solutions are wait and see and counter-based.

  1. If we detect it as closed, wait for a little bit and check again.
  2. Poll the switch constantly. For each poll if the switch is closed increment the counter. If we reach a certain value in a certain time then the switch was closed (or button pressed).

Serial Communication (Start and Stop bit)

"[The] start bit is used to indicate the start of a frame. Without the start bit, the receiver cannot distinguish between the idle line and the 1 bit because both are logical one. A stop bit is used to allow the receiver to transfer the data from the receive buffer to the memory." (Wu, Homework 6 Solutions)


uart(Source: Hui Wu, Lecture Notes)

Sample Q3a

(This code probably won't work and probably has errors (and maybe not just simple ones, but serious ones that mean that the logic is wrong))

A: .byte 20 ;array of size 10, element size 2 bytes

ldi XL, low(A)
ldi XH, high(A)

;add the contents of the array.
store 0
store 1
store 2
store 3
store 4
store 5
store 6
store 7
store 8
store 9

;find the largest value
ldi XL, low(A)
ldi XH, high(A)

;start with the 1st element of the array
ld r25, X+
ld r26, X+

ldi r20, 10 ;size of array
 cpi r20, 0
 breq endloop

 ld r21, X+
 ld r22, X+

 cp r25, r21
 cpc r26, c22
 brlo lowerthan
 ;we have a new max
 mov r25, r21
 mov r26, r22


 inc r20
 rjmp loop
endloop: rjmp endloop

.macro store
ldi r16, low(@0)
ldi r17, high(@0)

st X+, r16
st X+, r17

For some reason in my lecture notes I have "eg. fine 2nd or 3rd smallest or largest" so here is a modification to do something like that.

A: .byte 20 ;array of size 10, element size 2 bytes

ldi XL, low(A)
ldi XH, high(A)

;add the contents of the array.
store 0
store 1
store 2
store 3
store 4
store 5
store 6
store 7
store 8
store 9

;sort into accending
loopthough for the length of array, (by then we can be sure its sorted)
ldi r23, 10
 cpi r23, 0
 breq endlargeloop

 ;point X to the start of A
 ldi XL, low(A)
 ldi XH, high(A)

 ;start with the 1st element of the array
 ld r25, X+
 ld r26, X+

 ldi r20, 10 ;size of array
 cpi r20, 0
 breq endloop

 ;the next value
 ld r21, X+
 ld r22, X+

 cp r25, r21
 cpc r26, c22
 brge gethan
 ;r22:r21 < r26:r25
 ;swap the order
 st -X, r26
 st -X, r25
 st -X, r22
 st -X, r21

 ld r24, X+ ;to change the X pointer
 ld r24, X+

 ld r25, X+
 ld r26, X+


 inc r20
 rjmp loop

inf: rjmp inf

.macro store
ldi r16, low(@0)
ldi r17, high(@0)

st X+, r16
st X+, r17
Tags: comp2121, computing.
COMP2121 - Wk05 - Interrupts
20th June 2009

To explain interrupts, Wu used an example of a network card that is downloading a file. The network card has a buffer, and only once this buffer is full (or data stream is complete) should the CPU then copy the contents from the buffer to the RAM. So how does the CPU know when the network card's buffer is full and when to execute the copy? He described two ways here interrupt and polling.

Polling involves the CPU periodically asking the network card, are you full? Two problems with this method are a) there may be a delay as you have to wait for the poll request to be made and b) it wastes a lot of CPU time. Polling is implemented in software, not hardware.

An alternative to polling is using interrupts whereby the network card will send an interrupt signal to the CPU to get its attention. This needs special hardware to implement, however it is very efficient compared with polling.

An interrupt system must (among other things),

IRQ is an interrupt request signal.

A daisy chain arrangement (as seen below) allows multiple devices to send and IRQ. However the CPU cannot determine from the IRQ line which device sent the interrupt. So in a daisy chain system when the CPU receives an IRQ, it will send a signal to IO1 asking "did you send the IRQ?" if IO1 sent the request it will reply "yes", if not it will pass the question on to the next IO device and so on. The response is passed back in the same way.


Reset is an interrupt in AVR, and in the AVR Mega64 there are five different sources of reset. There is a flag in the MCU Control Register for each of these and can be used to determine the source of a reset interrupt. The watchdog timer is one source of reset.

Watchdog Timer

The watchdog timer is used to try to reset the system if an error such hang occurs. The watchdog timer in AVR can be enabled or disabled.

If the Watchdog timer is enabled, it needs to be periodically reset using the wdr instruction. When (if) the Watchdog times out, it will generate a short reset pulse.

Tags: comp2121, computing.
Channel TEN's contractor/outsourcer/... Posts TV Show Online Before It Airs
3rd June 2009

It seems that channel ten (or at least their contractor/outsourcer/whatever) decided to release episodes of a show its airing (Merlin) on the interent before their have aired on TV. Its not such a big deal because the show has already aired in the UK, but I would still say good on you channel 10 for going that extra mile and supporting the fans who want to watch the show through legal methods.

The links are (its a 13 episode season),

??? ??? http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-3fullep-210509_700.flv http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/merlin_ep4_220509_700.flv http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-5fullep-270509_700.flv http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-6fullep-270509_700.flv http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-7fullep-270509_700.flv http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-8fullep-270509_700.flv http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-9fullep-280509_700.flv ??? http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-11fullep-280509_700.flv http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-12fullep-270509_700.flv http://flash.vx.roo.com/streamingVX/19056/1395/geo/ausonly/2009/Q2/MERL-13fullep-280509_700.flv

But they are sure to change, esp the dates (but they were valid when I posted them (wget -S --spider filename, will verify if a file exists for you)), so you may need to change them (the dates) (ps. DownThemAll is great at trying many different file names to see which ones get a hit). On ten's web site they only list the most recent episode but if you look at your HTTP logs you can see the flv URL. There is no key in the file so you should be able to just change the episode number and then try all dates in the near months.

PS. In the odd chance than someone from TEN reads this you should note that Australia has poor interent (in terms of IP quota) as such we have a greater need to be able to download shows and watch later (so the download can be done off peak, or from a location with more generous IP quota). You should consider promoting friendly file formats straight for download. Perhaps then you will have a larger uptake of online viewers (I would find a short advertisement at the start and/or end of the video acceptable).

PSS. I'm not one of those people who thinks posting links to pirated material should be (or is) illegal or immoral. Among many other reasons, how is the person who posts the link supposed to know if the material they are linking to is infringing?

PSSS. This is not a vunrability and as such I don't think I am required under my own ethics to let them know. But regardless this is obviously intentional, and dispite all this I cannot report it to TEN anyway as there is no email listed on their contact us page.

No tags

RSS Feed