Project #1: Run-length Encoding (Computer Architecture, Fall 2021)

Related tags

Miscellaneous ca-pa1
Overview

4190.308 Computer Architecture (Fall 2021)

Project #1: Run-length Encoding

Due: 11:59PM, September 26 (Sunday)

Introduction

In this project, you need to perform a variant of run-length encoding to the given array of bytes in memory. The purpose of this project is to make you familiar with the binary representations of strings/integers and the logical operations supported in the C programming language. Another goal is to make your Linux or MacOS development environment ready and to get familiar with our project submission server.

Background: Run-length Encoding

Run-length encoding (RLE) is a form of lossless data compression in which runs of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. This is most efficient on data that contains many such runs, for example simple graphic images such as icons, line drawings, and animations. For files that do not have many runs, RLE could increase the file size. For more details on RLE, please refer to https://en.wikipedia.org/wiki/Run-length_encoding.

Our Simplified Run-length Encoding

In memory, every data is represented as a sequence of binary digits. Therefore, we just count those runs that consist of all 0's or all 1's. Because we have only two kinds of runs, we do not store the data value. Instead, we repeatedly store the length of the run with all 0's and then that with all 1's. We allocate three bits to represent the length of each run. Our simplified run-length encoding works as follows.

  1. First, find a run with all 0's in the input. If the length is less than 8, emit the three bits that correspond to the length of the run.

  2. And then find the next run with all 1's in the input. Again, if the length is less than 8, emit the three bits that denote the length of the run.

  3. Basically, step 1 and 2 are repeated until the end of the input.

  4. If the length of the run is longer than 7 in step 1 or 2, it should be represented as a series of full runs (i.e., the run with the length 7) except for the last run. For example, the run 00000000 is represented as 0000000 + 0 where there is no run with 1's between them. This leads to the following encoding result. (In this case, please note that any other combinations such as 0000 + 000 are not allowed.)

111 000 001 
 ^   ^   ^
 |   |   |   
 |   |   the length of the next run with all 0's (1)
 |   the length of the next run with all 1's (0)
 the length of the first run with all 0's (7)
  1. If the total number of output bits is not a multiple of 8 after encoding, we pad 0's until it becomes a multiple of 8. This is because a byte is the smallest unit that can be stored in memory. Hence, the output has the following format:
| AAA BBB CCC DDD  ...         |  Padding  |
|------------------------------|-----------|
|          (3*n bits)          | (0~7 bits)|

Here, AAA is the length of the first run with all 0's, BBB is the length of the next run with all 1's, and CCC and DDD are the lengths of the next runs with all 0's and 1's, respectively. You should pad 0's in the last byte so that the toal number of bits becomes a multiple of 8.

Putting it all together, the final encoded value for the 8-bit input 0x00 becomes 0xe0 0x80 as can be seen in the following.

Original value: 00000000
Encoded value:  111 000 001 0000000   == 0xe0 0x80
                 ^   ^   ^  ^^^^^^^
                 |   |   |     |
                 |   |   |    padding (to make the output 8*n bits)
                 |   |   the length of the next run with all 0's (1)
                 |   the length of the next run with all 1's (0)
                 the length of the first run with all 0's (7)

Example

Let's see an example. Assume that we want to encode the string The quick brown fox using our simplified run-length encoding scheme. Each character in the text string in C is represented as 8-bit unsigned integer according to the ASCII standard. The following shows the actual values (in hexadecimal) to represent the given string.

T  h  e     q  u  i  c  k   
54 68 65 20 71 75 69 63 6b 20 

b  r  o  w  n     f  o  x    
62 72 6f 77 6e 20 66 6f 78 

In memory, the string is stored as binary digits as follows:

T        h        e                 
01010100 01101000 01100101 00100000 
q        u        i        c        k        
01110001 01110101 01101001 01100011 01101011 00100000
b        r        o        w        n
01100010 01110010 01101111 01110111 01101110 00100000
f        o        x
01100110 01101111 01111000 

Now, we convert each run according to our run-length encoding scheme.

T             h           e             []        q
0 1 0 1 0 1 000 11 0 1 0000 11 00 1 0 1 00 1 000000 
=> 001 001 001 001 001 001 011 010 001 001 100 010 010 001 001 001 010 001 110

          u             i             c           k             []        b
111 000 1 0 111 0 1 0 1 0 11 0 1 00 1 0 11 000 11 0 11 0 1 0 11 00 1 000000
=> 011 011 001 001 011 001 001 001 001 001 010 001 001 010 001 001 010 011 010 001 010 001 001 001 010 010 001 110

          r           o           w           n           []        f
11 000 1 00 111 00 1 00 11 0 1111 0 111 0 111 0 11 0 111 000 1 000000
=> 010 011 001 010 011 010 001 010 010 001 100 001 011 001 011 001 010 001 011 011 001 110

          o           x         
11 00 11 00 11 0 1111 0 1111 000 
=> 010 010 010 010 010 001 100 001 100 011

The final output will be as follows.

T             h           e             []        q
0 1 0 1 0 1 000 11 0 1 0000 11 00 1 0 1 00 1 000000 
=> 001 001 001 001 001 001 011 010 001 001 100 010 010 001 001 001 010 001 110
=> 00100100 10010010 01011010 00100110 00100100 01001001 01000111 0
=> 0x24     0x92     0x5a     0x26     0x24     0x49     0x47     0x36

          u             i             c           k             []        b
111 000 1 0 111 0 1 0 1 0 11 0 1 00 1 0 11 000 11 0 11 0 1 0 11 00 1 000000
=> 011 011 001 001 011 001 001 001 001 001 010 001 001 010 001 001 010 011 010 001 010 001 001 001 010 010 001 110
=> 0110110 01001011 00100100 10010010 10001001 01000100 10100110 10001010 00100100 10100100 01110
           0x4b     0x24     0x92     0x89     0x44     0xa6     0x8a     0x24     0xa4     0x72

          r           o           w           n           []        f
11 000 1 00 111 00 1 00 11 0 1111 0 111 0 111 0 11 0 111 000 1 000000
=> 010 011 001 010 011 010 001 010 010 001 100 001 011 001 011 001 010 001 011 011 001 110
=> 010 01100101 00110100 01010010 00110000 10110010 11001010 00101101 1001110
       0x65     0x34     0x52     0x30     0xb2     0xca     0x2d     0x9c

          o           x           
11 00 11 00 11 0 1111 0 1111 000  
=> 010 010 010 010 010 001 100 001 100 011 
=> 0 10010010 01001000 11000011 00011000 (3 bits padded)
     0x92     0x48     0xc3     0x18     

Problem specification

1. encode()

Write the C function named encode() that encodes the input binary data using our run-length encoding scheme. The prototype of encode() is as follows:

int encode(const char* const src, const int srclen, char* const dst, const int dstlen);

The first argument src points to the memory address of the input data. The length of the input data (in bytes) is specified in the second argument srclen. The encoded result should be stored starting from the address pointed to by dst. Finally, the dstlen argument indicates the number of bytes allocated for the result by the caller.

The function encode() returns the actual length of the output in bytes including the encoded data and padded bits. If the size of the output exceeds the dstlen, it should return -1 and the contents of the output is ignored. When srclen is zero, encode() returns zero. In any case, the contents of the memory outside of the allocated buffer should not be corrupted.

2. decode()

Write the C function named decode() that decodes the input data encoded with our simplified run-length encoding scheme. The prototype of decode() is as follows:

int decode(const char* const src, const int srclen, char* const dst, const int dstlen);

The first argument src points to the memory address of the input encoded data. The length of the input data (in bytes) is specified in the second argument srclen. The decoded (original) data should be stored starting from the address pointed to by dst. Finally, the dstlen argument indicates the number of bytes allocated for the result by the caller.

The function decode() returns the actual length of the output in bytes. If the size of the output exceeds the dstlen, it should return -1 and the contents of the output is ignored. When srclen is zero, decode() returns zero. In any case, the contents of the memory outside of the allocated buffer should not be corrupted.

Skeleton code

We provide you with the skeleton code for this project. It can be downloaded from Github at https://github.com/snu-csl/ca-pa1/. If you don't have the git utility, you need to install it first. You can install the git utility on Ubuntu by running the following command:

$ sudo apt install git

For MacOS, install the Xcode command line tools which come with git.

To download and build the skeleton code, please follow these steps:

$ git clone https://github.com/snu-csl/ca-pa1.git
$ cd ca-pa1
$ make
gcc -g -O2 -Wall   -c -o pa1.o pa1.c
gcc -g -O2 -Wall   -c -o pa1-main.o pa1-main.c
gcc -o pa1 pa1.o pa1-main.o 

The result of a sample run looks like this:

$ ./pa1
-------- TEST #0 Encoding
[Input] length (bytes): 1
11111111
[Encode] length (bytes): 0

[Answer] length (bytes): 2
000 111 000 001 000 0
-------- ENCODING WRONG! 2

-------- TEST #0 Decoding
[Decode] length (bytes): 0

-------- DECODING WRONG! 2

(... more test cases below ...)

Restrictions

  • You are not allowed to use any array even in the comment lines. Any source file that contains the symbol [ or ] will be rejected by the server.

  • Do not include any header file in the pa1.c file. You are not allowed to use any library functions (including printf()) inside the pa1.c file.

  • Your solution should finish within a reasonable time. If your code does not finish within a predefined threshold (e.g., 5 sec), it will be killed.

Hand in instructions

  • In order to submit your solution, you need to register an account to the submission server at https://sys.snu.ac.kr
    • You must enter your real name & student ID
    • Wait for an approval from the TA
  • Note that the submission server is only accessible inside the SNU campus network. If you want off-campus access to the submission server, please send your IP to the TAs via email (snucsl.ta AT gmail)
  • Upload only the pa1.c file to the submission server

Logistics

  • You will work on this project alone.
  • Only the upload submitted before the deadline will receive the full credit. 25% of the credit will be deducted for every single day delay.
  • You can use up to 4 slip days during this semester. If your submission is delayed by 1 day and if you decided to use 1 slip day, there will be no penalty. In this case, you should explicitly declare the number of slip days you want to use in the QnA board of the submission server after each submission. Saving the slip days for later projects is highly recommended!
  • Any attempt to copy others' work will result in heavy penalty (for both the copier and the originator). Don't take a risk.

Have fun!

Jin-Soo Kim
Systems Software and Architecture Laboratory
Dept. of Computer Science and Engineering
Seoul National University

You might also like...
An 8-bit minicomputer with a fully custom architecture
An 8-bit minicomputer with a fully custom architecture

JDH-8 An fully custom 8-bit minicomputer with a unique architecture and the express goal of playing PONG. The program above is running in the emulator

The purpose of these streams is to be educational and entertaining for viewers to learn about systems architecture, reverse engineering, software security, etc., and NOT to encourage nor endorse malicious game hacking.
The purpose of these streams is to be educational and entertaining for viewers to learn about systems architecture, reverse engineering, software security, etc., and NOT to encourage nor endorse malicious game hacking.

Memestream This repository holds the code that I develop during my live game "modding" 😉 sessions. When I stream, I like to speedrun making a success

FastPath_MP: An FPGA-based multi-path architecture for direct access from FPGA to NVMe SSD

FastPath_MP Description This repository stores the source code of FastPath_MP, an FPGA-based multi-path architecture for direct access from FPGA to NV

Khepri is a Cross-platform agent, the architecture and usage like Coblat Strike but free and open-source.
Khepri is a Cross-platform agent, the architecture and usage like Coblat Strike but free and open-source.

Khepri Free,Open-Source,Cross-platform agent and Post-exploiton tool written in Golang and C++ Description Khepri is a Cross-platform agent, the archi

Free,Open-Source,Cross-platform agent and Post-exploiton tool written in Golang and C++, the architecture and usage like Cobalt Strike
Free,Open-Source,Cross-platform agent and Post-exploiton tool written in Golang and C++, the architecture and usage like Cobalt Strike

Khepri Free,Open-Source,Cross-platform agent and Post-exploiton tool written in Golang and C++ Description Khepri is a Cross-platform agent, the archi

Unicorn is a lightweight, multi-platform, multi-architecture CPU emulator framework, based on QEMU.
Unicorn is a lightweight, multi-platform, multi-architecture CPU emulator framework, based on QEMU.

Unicorn Engine Unicorn is a lightweight, multi-platform, multi-architecture CPU emulator framework, based on QEMU. Unicorn offers some unparalleled fe

Decentralized architecture for loss tolerant semi-autonomous robotics

gestalt-arch Decentralized architecture for loss tolerant semi-autonomous robotics Objective We demonstrate a decentralized robot control architecture

Protobuf for Proxyman app - Include Apple Silicon & Intel architecture

Protobuf for Proxyman macOS app Protobuf for Proxyman app - Include Apple Silicon & Intel architecture How to build Open the project on the latest Xco

Satellite Flight Software: Command-Centric Architecture

Core of Command Centric Architecture C2A Command Centric Architecture OBC 搭載フライトソフトウェアフレームワーク C2A core 各 C2A で共通利用される C2A の中核部のコード 基本的には,各々の C2A user

Owner
SNU Systems Software & Architecture Laboratory
SNU Systems Software & Architecture Laboratory
Class Code for CSCE 240 Fall 2021

Class Code for CSCE 240 Fall 2021

null 8 Dec 3, 2021
PLP Project Programming Language | Programming for projects and computer science and research on computer and programming.

PLPv2b PLP Project Programming Language Programming Language for projects and computer science and research on computer and programming. What is PLP L

PLP Language 5 Aug 20, 2022
C Program to input a string and adjust memory allocation according to the length of the string.

C-String C Program to input a string and adjust memory allocation according to the length of the string. With the help of this program, we have replic

Kunal Kumar Sahoo 1 Jan 20, 2022
This is a metamod plugin for Fall Guys maps in Sven Co-op (Steam version) (Windows or Linux)

metamod-fallguys This is a metamod plugin for Fall Guys maps in Sven Co-op (Steam version) (Windows or Linux) Installation Copy everything from build

hzqst 6 Nov 22, 2022
CSC404: Computer Graphics [CG] & CSL402: Computer Graphics Lab [CG Lab]

COMPUTER-GRAPHICS-AND-COMPUTER-GRAPHICS-LAB CSC404: CG & CSL402: CG LAB [SEMESTER IV] Syllabus CG - Reference Books THE WALL MEGA SATISH - AUTHOR CG C

AMEY THAKUR 7 Apr 28, 2022
Lingo - Text encoding for modern C++

Lingo Lingo is an encoding aware string library for C++11 and up. It aims to be a drop in replacement for the standard library strings by defining new

Rick de Water 29 Oct 18, 2022
A C++ concepts and range based character encoding and code point enumeration library

Travis CI (Linux:gcc) Text_view A C++ Concepts based character encoding and code point enumeration library. This project is the reference implementati

Tom Honermann 121 Sep 9, 2022
Single header lib for JPEG encoding. Public domain. C99. stb style.

tiny_jpeg.h A header-only public domain implementation of Baseline JPEG compression. Features: stb-style header only library. Does not do dynamic allo

Sergio Gonzalez 209 Nov 22, 2022
Read file to console, automatically recognize file encoding, include ansi, utf16le, utf16be, utf8. Currently output ansi as gbk for chinese text search.

rgpre A tool for rg --pre. Read file to console, automatically recognize file encoding, include ansi, utf16le, utf16be, utf8. Currently output ansi as

null 3 Mar 18, 2022