RLE compression (10p)¶
Note! These instructions may slightly change for clarification..
Course project 2019 is to implement Run Length Encoding data compression algorithm (see video) with y86-64 assembly language.
Shortly, the compression algorithm works the following way:
- Consider an array of data (string, numeric, etc)
- Iterate through the array to handle each data item
- Compare each symbol (data item) with the previous one to calculate how many consecutive same symbols there are
- If the symbol changes, save the count and the symbol (in this order) to somewhere in memory
- Stop the program
You have 9 characters in a string: AAAABBBCC So, you have 4 A's, 3 B's and 2 C's, that becomes 4A3B2C Your data is 12 numbers: 11166660333, that becomes 31461033 You have 5 characters in a string: JOULU (Christmas) So, there are 1 J's, 1 O's, 1 U's, 1 L's and 1 U's, that becomes 1J1O1U1L1U Note that in this case the data size was not reduced :(
RLE compression is/was commonly used with bitmap graphics. Typically, these image contain small number of colours (i.e. symbols) and have large areas with same colour, e.g. image background. RLE enconding is also not computationally demanding.
Example. Apparently smiley results better compression space saving than noisy image.
Implement the RLE compression algorithm based on the following requirements.
- Your program starts with label
main:. No initialization code before that
- Your data is given to the algorithm the following way
- Data values are 64 bits in size
- Data is stored in memory, starting address is
0x1200. Data is stored using the
- The size of the data array is given register
%r10, where the maximum size is 256 items
- Store your RLE encoded data representation to the stack, so that each each symbol takes two memory locations. Stack begins from address
- Number of consecutive symbols
- The symbol
1-(encoded size / original size)
- Example. data size 10 bytes and encoded size 4 bytes. The saving is: 1- (4 / 10) = 0.6 that is 60%
- Note, that encoding may result negative space saving if the encoded size is actually larger..
For testing you could initialize your program the following way, for example:
.pos 0x0 irmovq $10,%r10 main: # ... # your program # ... .pos 0x1000 Stack: .pos 0x1200 .quad 0x01 .quad 0x01 .quad 0x02 .quad 0x02 .quad 0x03 .quad 0x03 .quad 0x04 .quad 0x05 .quad 0x05 .quad 0x05
As a result, the stack should look like the following:
Addr : Data 0x0fb0: 0x0000000000000005 0x0fb8: 0x0000000000000003 0x0fc0: 0x0000000000000004 0x0fc8: 0x0000000000000001 0x0fd0: 0x0000000000000003 0x0fd8: 0x0000000000000002 0x0fe0: 0x0000000000000002 0x0fe8: 0x0000000000000002 0x0ff0: 0x0000000000000001 0x0ff8: 0x0000000000000002
Instructions for project¶
You should follow these instructions:
- Implement your course project alone
- You can of course discuss the project with peers, but write your code by yourself
- Plagiarism is a serious matter at university level
- Please include the names of the peers in your code comments
- Do not return code written by others
- Select a purpose for each register
- Some registers for global variables
- Some registers for program variables
- Some register (or stack) for passing arguments for functions
- Design which functions are needed? How to store them in memory? How to pass arguments and return values, etc?
- Does your assembly exercise code help?
- Using stack
- Remember that the stack grows "down" in memory
- Make sure your stack does not override program code in the memory
- In the end of the program, the bottom of the stack must contain only the expected values, but outside that range you can have extra stuff in stack (this is not considered a bug)
- Otherwise it is easy to get lost after a break in coding..
- Functions can be tested separately as small programs
- Test branch instructions with all possible input values
<0, =0, >0
- Usually checking only the
ZFflag is sufficient
Returning your course project for grading¶
Deadline is 31st December 2019. If you return the project late, we will reduce your grade -1 (for this course part), unless you have agreed late return with the course staff. Note that the exercise sessions end already at 12th December.
Your program should be very well commented for grading. Your program may have small bugs. But, do not return just something that looks like a program, it will not be graded. Your code need to show that you really have tried to implement the program!
The course staff will also check your code by hand.
Placeholder for the return box, appears here soon..
Maximum 10 points:
- A working program that follows the instructions: 8 points
- Small bugs and missing functionality allowed, but 1-2p will be reducted depending on the bug / missing functionality
- Code comments: 0-2 points
Concerning this part of the course:
- Lovelace exercises max 20 points
- Course project 10 points
- You need to have a half of the maximum points (15 / 30p) to pass the course
- You need to have points from both exercises and from course project
Please give your feedback to the box below or to the university's official website palaute.oulu.fi.
Give feedback on this content
Comments about the task?