View source for Category:I600 Introduction to Computers and Informatics

In this course we'll give an introduction to variety of topics from hardware to software.
The course will follow roughly the same structure as [https://lagunita.stanford.edu/courses/Engineering/CS101/Summer2014/about Computer Science 101 at Stanford University] with more hands-on approach. This course substitutes Estonian courses I100 Sissejuhatus informaatikasse and [http://www.pld.ttu.ee/~teet/itarvutid.html I201 Arvutid].

Monday lectures will cover more theoretical stuff;
Thursday workshops are for getting started with new topics;
the homework assignments connect theoretical with practice and
Tuesday sessions are for follow up, asking/answering questions and presenting homework.
Attendance won't be tracked, the sessions are there if you need help.
Bring your laptops for Tuesday and Thursday sessions.


Course credits: 6 ECTS

Lecturer: Lauri Võsandi

E-mail: lauri [donut] vosandi [plus] i600 [ät] gmail [dotchka] com


=Grading=

Grade mapping:

* 0-50 points, fail
* 51-60 points, pass 1
* 61-70 points, satisfactory 2
* 71-80 points, average 3
* 81-90 points, good 4
* 91-100 points, very good 5

Grading is split between theory and practice

* Exam of 50 points, preparation in lectures and general discussion in workshops.
* Assignments, see instructions and points below.
* Extra points for improving quality of wiki articles, extracurricular work and also helping others, see points below.

Exam will be halfway between oral and written: You'll be given 30 minutes to prepare for several random questions and 15 minutes to discuss what you've answered.
If you don't have prior experience with the topics, it's highly recommended to take part of the sessions in order to pass the exam. You can use a calculator and this wiki page, don't rely on the access to terminal or other software tools. You can not access Internet or any remote computers.

Exam sections:

* Execution of ~10 processor instructions
* Bunch of randomly selected questions from this page
* Bunch of questions (how much RAM, how big disk, what wireless chipset) asked about a computer you'll be given
* Gain SSH access to a machine on the network, basic text file editing skills using nano

Exam times:

* 12. jan 10:00 - Oliver Aasmets
* 12. jan 10:30 - <Insert name>
* 12. jan 11:00 - <Insert name>
* 12. jan 11:30 - <Insert name>
* 12. jan 13:00 - Artur V. Kerge
* 12. jan 13:30 - <Insert name>
* 12. jan 14:00 -  Nazmul Hasan 
* 12. jan 14:30 - <Insert name>
* 12. jan 15:00 - Meelis Hass
* 12. jan 15:30 - <Insert name>
* 13. jan 10:00 - Veiko Velt
* 13. jan 10:30 - Etienne Barrier
* 13. jan 11:00 - Alina Kallas
* 13. jan 11:30 - Artur Ovtsinnikov
* 13. jan 13:00 - Sheela Gowry
* 13. jan 13:30 -  Dmitri Sim
* 13. jan 14:00 -  Ender
* 13. jan 14:30 -  Sander Mets
* 13. jan 15:00 - Kristjan Saaremets
* 13. jan 15:30 - Shan e mustafa

=Lecture: Computer hardware=

Jargon: CPU, RAM, ROM, HDD, SSD, PCI, PCI Express, USB 2.0, USB 3.0, VGA, HDMI, DVI, LCD, TFT, LED, OLED, AMOLED, CRT, PWM

[https://echo360.e-ope.ee/ess/echo/presentation/beef71c3-044c-43c9-a326-e1e62cbb5c9b Lecture recording #1]

[https://echo360.e-ope.ee/ess/echo/presentation/36786bbb-84b6-4604-be6f-c363bf22ce8d Lecture recording #2 starting 12:30]

[https://docs.google.com/presentation/d/1OzaqTBAUfMOzhG0HZeSJVSszCmFyn4ug35teYJWkyfM/edit?usp=sharing Lecture slides] Random access memory, permanent storage, buses, input devices, display technologies, networking

Potential exam questions:

* Different buses and their uses
* What are the differences between hard disk drive (HDD) and solid state drive (SSD)? [http://www.storagereview.com/ssd_vs_hdd]
* What is the purpose of Flash Translation Layer in terms of solid state drives?
* What are difference between volatile/non-volatile, RAM, ROM, EEPROM and where are they used?
* What is data retention?
* What are difference between asynchronous/synchronous, dynamic/static RAM and where are they used?
* What is [https://compsci2014.wikispaces.com/2.1.3+Explain+the+use+of+cache+memory cache]? What is cache coherence?
* What are differences between resistive and capacitive touchscreen? [http://www.alphr.com/realworld/357325/capacitive-or-resistive-whats-the-best-type-of-touchscreen]
* Explain how [http://www.bidouille.org/hack/mousecam computer mouse] works? [http://www.topdesignmag.com/mouse-history-in-photos/ History of computer mouse].
* Explain how [http://www.daskeyboard.com/blog/typing-through-time-the-history-of-the-keyboard/ computer keyboard] works? [http://computer.howstuffworks.com/keyboard.htm HowStuffworks article] [http://www.explainthatstuff.com/computerkeyboards.html Explain that Stuff article] [http://www.daskeyboard.com/blog/typing-through-time-the-history-of-the-keyboard/ Keyboard History]
* Explain how [https://en.wikipedia.org/wiki/Cathode_ray_tube cathode ray tube] (CRT) based screen technology works and name pros/cons. [https://www.youtube.com/watch?v=2czqYV3T_Kc]
* Explain how [https://en.wikipedia.org/wiki/Liquid-crystal_display liquid crystal displays] (LCD) work and name pros/cons. [https://www.youtube.com/watch?v=nCHgmCxGEzY]
* Name screen technologies making use of thin film transistor (TFT) technology? [https://en.wikipedia.org/wiki/Thin-film_transistor]
* Name uses for light polarization filters? [https://en.wikipedia.org/wiki/Polarizing_filter_%28photography%29] [https://en.wikipedia.org/wiki/Polarized_3D_system] 
* What are the benefits of [https://en.wikipedia.org/wiki/Twisted_pair twisted pair cabling] and [https://en.wikipedia.org/wiki/Differential_signaling differential signalling]?
* [https://en.wikipedia.org/wiki/Active_matrix Active matrix] vs [https://en.wikipedia.org/wiki/Passive_matrix_addressing passive matrix] in display technology

Security section: [http://www.bunniestudios.com/blog/?p=3554 Hacking SD cards]

Assignments:
* [https://wiki.itcollege.ee/index.php/I600_Introduction_to_Computers_and_Informatics#Assignment:_Investigating_PC_hardware Investigating PC hardware]
* [https://wiki.itcollege.ee/index.php/I600_Introduction_to_Computers_and_Informatics#Assignment:_Investigating_embedded_hardware Investigating embedded hardware]

=Lecture: Storage abstractions=

In this lecture we'll talk about permanent storage abstractions: block device, disk, partition, file system, directory/folder, file, journaling, FAT32, NTFS, ext4, HFS+

[https://docs.google.com/presentation/d/1dJ-HMSR9nW8OuZtSTYf5dlFyPsZKGqxlKoEwIHi9h6k/ Lecture slides] 

[https://echo360.e-ope.ee/ess/echo/presentation/36786bbb-84b6-4604-be6f-c363bf22ce8d Lecture recording] starts at 47:50.

* What is a [https://en.wikipedia.org/wiki/Block_%28data_storage%29 block device]?
* What is [https://en.wikipedia.org/wiki/Logical_block_addressing logical block addressing] and what are the benefits compared to older [https://en.wikipedia.org/wiki/Cylinder-head-sector cylinder-head-sector addressing] method in terms of harddisks?
* What is a [https://en.wikipedia.org/wiki/Disk_partitioning disk partition]?
* What is a [https://en.wikipedia.org/wiki/File_system file system]?
* What is [https://en.wikipedia.org/wiki/Journaling_file_system#Write_hazards journaling] in terms of filesystems and what are the benefits? Name some journaled filesystems in use nowadays.

=Lecture: Bootloaders, kernels=

In this lecture we'll discuss how a computer boots and how an operating system kernel is loaded.


[https://echo360.e-ope.ee/ess/echo/presentation/04eeebd1-c892-485a-9123-03abaa3ce3ca Lecture recording #1], first half we'll discuss about first assignment about investigating PC hardware, slides start at 43:40.

[https://echo360.e-ope.ee/ess/echo/presentation/26f1d40d-7830-4e5c-b783-e061c1e91cfc Lecture recording #2], first 15 minutes we'll discuss about second assignment about investigating embedded hardware, last slides about kernels are discussed from 16:00 up to 27:30. I forgot to switch video input for lecture recording so you'll have to browse slides from the link below :/

Lecture slides:
[https://docs.google.com/presentation/d/1ybYQEqCgN1KdVW1sLdwtfRogavgzzMQdUfTcAnxNAf4/ bootloaders],
[https://docs.google.com/presentation/d/1xDL27k3z_0I-IKzdjKkwhOhBrg0aOnM0w0u1zDwaEWY/ kernels].

Jargon: [https://en.wikipedia.org/wiki/BIOS BIOS] (basic input/output system), [https://en.wikipedia.org/wiki/Unified_Extensible_Firmware_Interface UEFI] (Unified Extensible Firmware Interface), bootloader, kernel, process, context switch, x86 real/protected mode, paged virtual memory, swap/pagefile, [https://en.wikipedia.org/wiki/User_space kernelspace/supervisor mode, userspace], [https://en.wikipedia.org/wiki/Protection_ring#Hypervisor_mode hypervisor mode] (ring -1), [https://en.wikipedia.org/wiki/System_Management_Mode#Problems system management mode] aka (ring -2).

Potential exam questions:

* What is the role of BIOS/UEFI in x86-based machines?
* Explain step by step how operating system is booted up, see slides for flowchart.
* Describe the functionality provided by general purpose operating system. See architecture of [https://en.wikipedia.org/wiki/Architecture_of_Windows_NT Windows NT], [http://www.elinux.org/Android_Architecture Android], [https://en.wikipedia.org/wiki/Architecture_of_OS_X OS X].
* What are the main differences between [https://en.wikipedia.org/wiki/Real_mode real mode] and [https://en.wikipedia.org/wiki/Protected_mode protected mode] of x86-based processor?
* What happens during context switch?
* What is the purpose of [https://en.wikipedia.org/wiki/Virtual_memory paged virtual memory]?


Security section: [https://en.wikipedia.org/wiki/DMA_attack DMA attack], [http://www.outsidaz.org/blog/2007/10/22/resetting-root-password-via-grubkernel-boot-options/ editing GRUB entries to gain root shell] without password prompt, [http://www.theinquirer.net/inquirer/news/2421402/serious-intel-cpu-security-exploit-spotted-in-old-x86-chips 20 years old security exploit in x86 processors].

=Lecture: Libraries, frameworks=

[https://echo360.e-ope.ee/ess/echo/presentation/26f1d40d-7830-4e5c-b783-e061c1e91cfc Lecture recording #1], from 00:27:30 up to 1:04:00.

[https://docs.google.com/presentation/d/1q9kGg5AI3AyXglxpJdLjLMpgRLdbF9dl62gauNmDEG8/edit Lecture slides]

Jargon: framework, library, [https://en.wikipedia.org/wiki/Application_binary_interface ABI], [https://en.wikipedia.org/wiki/Application_programming_interface API]

Security section: [http://www.fiercecio.com/story/hackers-exploiting-httpsys-bug-crash-iis-web-servers/2015-04-17 HTTP.sys bug crashes IIS web servers], [http://heartbleed.com/ OpenSSL bug Heartbleed].

=Lecture: Programming languages=

In this lecture we'll talk about programming languages

Lecture recording: [https://echo360.e-ope.ee/ess/echo/presentation/26f1d40d-7830-4e5c-b783-e061c1e91cfc starting from 1:04:00]

Lecture slides: [https://docs.google.com/presentation/d/1CCZntY7Z-AG_Mice5N2kclDGYI2xVVvRHgWUIs-SxYo/edit programming languages, stack machine]

Jargon: stack machine, lexer/lexeme, token, abstract syntax tree

Potential exam questions:

* What are the major steps of compilation?
* What are the differences between [https://en.wikipedia.org/wiki/Interpreted_language interpreted], [https://en.wikipedia.org/wiki/Just-in-time_compilation JIT-compilation] and [https://en.wikipedia.org/wiki/Compiler traditional compiling]?
* What is [https://en.wikipedia.org/wiki/Control_flow control flow]? Loops? Conditional statements?

Assignments:

* [https://wiki.itcollege.ee/index.php/Category:I600_Introduction_to_Computers_and_Informatics#Assignment:_Disassembling_Python Disassembling Python]
* [https://wiki.itcollege.ee/index.php/Category:I600_Introduction_to_Computers_and_Informatics#Assignment:_Investigating_compilers Investigating compilers]

=Lecture: Data encoding=

[https://echo360.e-ope.ee/ess/echo/presentation/ca8310e9-e82e-4e47-b90a-2e1801bcfada Lecture recording]

[https://docs.google.com/presentation/d/1QV_IMOadIEUTBW7Laqw59j8J7Y8HKwvSDmP-swEEx0s Lecture slides]

In this lecture we'll talk about bits, bytes, integers, strings, pixels, audio encodings, video encoding etc.

Potential exam questions:

* What is bit? Nibble? Byte? Word?
* Write 9375 in binary, hexadecimal?
* Write 0xDEADBEEF in decimal?
* What is [https://en.wikipedia.org/wiki/Quantization_%28signal_processing%29 quantization] in terms of signal processing?
* How are [https://en.wikipedia.org/wiki/Integer_%28computer_science%29 integers] stored in binary? What integer range can be described using n bits? How many bits are required to describe integer range from n .. m.
* How are [https://en.wikipedia.org/wiki/Single-precision_floating-point_format single precision] and [https://en.wikipedia.org/wiki/Double-precision_floating-point_format double precision] floating point numbers stored in binary according to [https://en.wikipedia.org/wiki/IEEE_floating_point IEEE754 standard]? [http://lauri.vosandi.com/hdl/arithmetic/floating-point-representation.html Floating-point multiplication]
* What is the difference between CMYK and RGB color models? How are YUV, HSV and HSL colorspaces related to RGB? What are sRGB and YCbCr and where are they used?
* How is data encoded on audio CD-s? What is the [http://lauri.vosandi.com/2013/07/audio-codecs.html capacity of an audio CD]?
* What is sampling rate? What is bit depth? What is resolution?
* What is bitrate?
* What is lossy/lossless compression?
* What is JPEG suitable for? Is JPEG lossy or lossless compression method?
* What is PNG suitable for? Does PNG support compression?
* How are time domain and frequency domain related in terms of signal processing? What is Fourier transform and where it is applied?

Jargon: 44.1kHz sampling rate, 16-bit audio, RGB565 pixel format, RGB888 pixel format

Relevant assignments:

* [https://wiki.itcollege.ee/index.php/Category:I600_Introduction_to_Computers_and_Informatics#Assignment:_Disassembling_Python Disassembling Python]
* [https://wiki.itcollege.ee/index.php/Category:I600_Introduction_to_Computers_and_Informatics#Assignment:_Investigating_compilers Investigating compilers]

=Lecture: Code execution in processor=

[https://docs.google.com/presentation/d/18wPDLydyZevMi9F0MX7F6eK-NMBZQzGN4mviF_ft8-E/edit Lecture slides]

[https://echo360.e-ope.ee/ess/echo/presentation/41440769-1cd5-4166-bd4e-299c2af3d3e0?ec=true Lecture recording #1]

[https://echo360.e-ope.ee/ess/echo/presentation/7aeb2a04-b0dc-4547-9dee-e541a5f9c99a?ec=true Lecture recording #2] up to 8:35, system calls

It's highly reccommended to play around with simulators [http://morriswmz.jit.su/static/simple-mips-pipelined.html here is one for MIPS processors].

In this lecture we'll talk about different processor architectures, instructions, pipelining, function calls, jumps, loops etc.

Assignments:

* [https://wiki.itcollege.ee/index.php/Category:I600_Introduction_to_Computers_and_Informatics#Assignment:_Disassembling_Python Disassembling Python]
* [https://wiki.itcollege.ee/index.php/Category:I600_Introduction_to_Computers_and_Informatics#Assignment:_Investigating_compilers Investigating compilers]

Exam question:

* Given ~10 instructions and their explainations, follow the instructions and elaborate after every step what happened in the processor?

=Lecture: Microcontrollers=

[https://docs.google.com/presentation/d/1qPyzBBfB1TseEzXjcp4-ZjqSnAwbjDmEqyIYcUGFLG0/edit Lecture slides]

[https://echo360.e-ope.ee/ess/echo/presentation/7aeb2a04-b0dc-4547-9dee-e541a5f9c99a?ec=true Lecture recording] starts at 8:35

Jargon: microprocessor, microcontroller, coprocessor, floating-point unit (FPU), digital signal processor (DSP), field programmable grid array (FPGA), sensors, actuators, digital input/output, analog input, general purpose input/output (GPIO), interrupt, interrupt handler, timer/counter, pulse-width modulation (PWM), 

Potential exam question:

* What distinguishes microcontroller from microprocessor?
* What are the differences between Hardvard architecture and von Neumann architecture?
* What is an interrupt?
* What is an timer?

=Lecture: Introduction to Boole algebra=

[https://docs.google.com/presentation/d/1Y1rXvt2oXROhW-LZ07B0Sg90D-_u8SlLUZeaxds7f1g/ Lecture slides]

Exam questions:

* Simplify A AND A OR B
* Show addition of X and Y in binary
* Show subtraction of X and Y  in binary
* Show multiplication of X and Y in binary


Assignments:
* [https://wiki.itcollege.ee/index.php/Category:I600_Introduction_to_Computers_and_Informatics#Assignment:_Designing_arithmetic-logic_unit Designing arithmetic-logic unit]

=Lecture: Hardware description languages=

[https://docs.google.com/presentation/d/1HO9iPfi8S3ZykuW7IHVm09QamLHiVo6s6lUGwWu4eD4/ Lecture slides]

[https://echo360.e-ope.ee/ess/echo/presentation/b7ca9eb3-5a9d-4e8c-8c1b-25c2891359ee Lecture recording] starts at 05:00

Potential exam questions:

* What are the uses for hardware description languages?
* What is latch?
* What is flip-flop?
* What is mux (multiplexer)?
* What is register? Register file?
* What is ALU?
* What is floating-point unit?
* What is a cache?
* What is a bus?
* Show the circuit diagram for A OR B AND C, NOT A AND B, <insert some other Boole formula here>?
* Show the truth table for <insert Boole formula here>?
* Write the equivalent Boole formula of a circuit diagram.


=Lecture: Publishing work=

[https://echo360.e-ope.ee/ess/echo/presentation/cd2c0e2b-5f48-4a39-89ca-b75801e5d00b Lecture recording]

[https://docs.google.com/presentation/d/1hCqRjGUx5Yv6iZN4xaz2UICLWbycnM46ctw2zX0g94U/ Lecture slides]

Potential exam questions:

* What are the major implications of MIT, BSD and GPL licenses?
* What are the differences between copyright, trademark, trade secret?
* Where would you use waterfall software development model? Where would you use agile?
* What is the purpose of a version control system?
* What would you store in a version control system?

=Lecture: Algorithms and data structures=

[https://echo360.e-ope.ee/ess/echo/presentation/1145600e-cef9-40b4-91da-3cc1174e27eb Lecture recording] unfortunately without audio :(

[https://docs.google.com/presentation/d/1vwJvvRerM0rYBaiE3pEX5GUXRHuVJvjTUDKo8fqTq_A/ Lecture slides]

Potential exam questions:

* What is time complexity of algorithm?
* What is space complexity of algorithm?
* What's a good algorithm?

=Lecture: History=

Topics: Computer history, Silicon Valley, standards

[https://echo360.e-ope.ee/ess/echo/presentation/584b21e6-4ead-4cb6-bc41-5c653bc5c3a2 Lecture recording]

[https://docs.google.com/presentation/d/1Ybld2ABpm9QJSLL-Bodr1a5XI5Hk_KM2q_nZVYu2L0c/edit?usp=sharing Lecture slides]

Potential example questions:

* What is [https://en.wikipedia.org/wiki/Moore's_law Moore's law]? What is [https://en.wikipedia.org/wiki/Rock's_law Rock's law]?
* What were the major contributing factors for success of Microsoft, Apple, Google, <your favourite company>?
* What were the major contributing factors to the success of Silicon Valley?

=Assignment: Investigating PC hardware=

Goal: Get familiar with your [https://en.wikipedia.org/wiki/X86 laptop hardware]. Get out of the comfort zone of your primary operating system and try out other operating systems. Learn about [https://en.wikipedia.org/wiki/Full_virtualization hardware virtualization].

Deadline: 16. September

Credits: 5 points plus extra point for being extra thorough about interpreting what you see.

Use what you learned in [[Getting started with Ubuntu]] workshop:

* '''Read the instructions before you act'''.
* Place your preferred ISO image to a memory stick using <code>dd</code> or Win32 Disk Imager and boot it on your personal laptop. You do '''not''' need to install Ubuntu on your harddisk, simply click '''Try Ubuntu''' once the operating system boots off the memory stick and carry out following tasks.
* Open up terminal by pressing <code>Ctrl-Alt-T</code>.
* Use <code>lsb_release -a</code> to check what operating system distribution you're running.
* Use <code>uname -sr</code> to check what operating system kernel you're running. 
* Use <code>cat /proc/cpuinfo</code> and check processor information. What CPU model and how many cores your computer has?
* Use <code>arch</code> to check what CPU architecture is being used by the operating system. Is it 32-bit or 64-bit?
* Use <code>cat /proc/meminfo</code> to check memory usage. How much RAM your computer has?
* Use <code>lspci -t -v -nn</code> to enumerate PCI and PCI Express devices, attempt to identify what is what.
* Use <code>lsusb</code> and <code>lsusb -t</code> to enumerate USB devices, again attempt to identify what is what.
* Use <code>fdisk -l</code> to enumerate disks and partitions. How big is your harddisk? How many and how big partitions it has?
* Use <code>lsblk</code> to enumerate block devices.
* Use <code>xrandr</code> to enumerate display outputs. What video output resolutions are available and which one is currently used?
* Use <code>cat /proc/asound/cards</code> to check which audio devices are available.
* Use <code>dmidecode</code> to see even more information about your computer.
* Use <code>ifconfig -a</code> or <code>ip addr list</code> to list all network interfaces.
* Use <code>iwconfig</code> or <code>iw list</code> to list all wireless network interfaces. Is your wireless network interface detected? If not take a guess why?
* Use <code>hcitool dev</code> to list bluetooth host controller. Is your bluetooth device detected?
* Use <code>glxinfo</code> to check what 3D rendering capabilities are available, is it hardware accelerated? (hint: is direct rendering enabled?)
* What [https://en.wikipedia.org/wiki/Sound_card audio card] is your machine using? What bus is it using?
* What [https://en.wikipedia.org/wiki/Graphics_processing_unit graphics controller] is your machine using? What bus is it using?
* What webcam is your machine using? What bus is it using?
* What [https://en.wikipedia.org/wiki/Ethernet wired network] chipset your computer has? What bus is it using? 
* What [https://en.wikipedia.org/wiki/IEEE_802.11 wireless network] chipset your computer has? What bus is it using?
* What [https://en.wikipedia.org/wiki/Bluetooth Bluetooth] device your computer has? What bus is it using?
* Is there a [https://en.wikipedia.org/wiki/Mobile_broadband_modem cellular modem] connected and how it's connected?
* Boot the ISO image in VirtualBox and follow the same steps as above, '''what are the differences and why'''?
* Answer to questions above and send it as [https://en.wikipedia.org/wiki/Plain_text plain text] e-mail to Lauri, make sure you '''use the address supplied above with the course code''', otherwise your mail is not searchable in my mailbox. Attach collected command outputs as [https://en.wikipedia.org/wiki/Plain_text plain text] file, do '''not''' send .odt, .doc files, these are not readable on my smartphone. When answering to questions phrase the text in a way that is understandable out of context, so I don't have to open up wiki to understand what you're talking about.

Note that I can't expect you to install Ubuntu on your physical machine, but I can help if you want to do that. You should have Ubuntu ready to go in a virtual machine at least for subsequent sessions. We're using Ubuntu because it's widely used on servers and in the cloud, so any Ubuntu skills will definitely come handy in future. If you're already familiar with Linux, it's suggested to take a look at other interesting operating systems such as [https://www.freebsd.org/ FreeBSD] or [http://www.openbsd.org/ OpenBSD]. Take a look at [https://www.kali.org/ Kali Linux] if you're interested in penetration testing.

=Assignment: Investigating embedded hardware=

Background: Most of the smartphones nowadays are using [https://en.wikipedia.org/wiki/System_on_a_chip SoC] built around [https://en.wikipedia.org/wiki/ARM_architecture ARM] processor. Raspberry Pi is an excellent piece of hardware to for checking out how an ARM-based machine looks like.

Goal: Get familiar with hardware ARM-based hardware.

Deadline: 23. September

Points: 4 points

Use what you learned in [[Getting started with Ubuntu]] and [[Getting started with Raspberry Pi]] workshops:

* Read the instructions before you get busy.
* Boot Raspbian on Raspberry Pi.
* Use the commands described in previous assignment to examine the environment of Raspbian on Raspberry Pi. What are the major differences compares to your laptop and virtual machine?
* What buses is Raspberry Pi making use of?
* What filesystems is Raspbian making use of?
* Answer to questions above and send it as e-mail to Lauri, make sure you '''use the address supplied above with the course code''', otherwise your mail is not searchable in my mailbox. Attach collected command outputs as [https://en.wikipedia.org/wiki/Plain_text plain text] file, do '''not''' send .odt, .doc files, these are not readable on a phone. When answering to questions phrase the text in a way that is understandable out of context, so it is not necessary to open up wiki to understand what you're talking about.

=Assignment: Investigating LAMP=

[https://en.wikipedia.org/wiki/LAMP_%28software_bundle%29 LAMP] software bundle is consists of Linux-based OS, [https://en.wikipedia.org/wiki/Apache_HTTP_Server Apache web server], [https://en.wikipedia.org/wiki/PHP PHP programming language] runtime and [https://en.wikipedia.org/wiki/MySQL MySQL database].
Most of the web applications on the Internet including Facebook are built on top of LAMP-styled software stack.
Use a Raspberry Pi or Ubuntu virtual machine to set up [https://www.raspberrypi.org/learning/lamp-web-server-with-wordpress/ WordPress], [https://doc.owncloud.org/server/8.1/admin_manual/installation/index.html ownCloud] or any well-known web application that makes use of a database such as MySQL.
To make your life easier also set up SSH public key authentication.

Goal: Get familiar with LAMP stack. Get comfortable with (SSH) public key authentication.

Deadline: 30. September

Points: 4 points

Tasks:

* If you're using Ubuntu virtual machine approach, see [[Accessing a virtual machine via SSH connection]]
* Use SSH to connect to your server over the network. If you're using Windows on your laptop use [http://www.chiark.greenend.org.uk/~sgtatham/putty/download.html PuTTY] to gain access to command line and [https://winscp.net/ WinSCP] to copy files, otherwise simply boot Ubuntu in a virtual machine and use <code>ssh username@hostname</code> to invoke commands and <code>sftp://username@hostname</code> in the file browser to access filesystem.
* Set up any of the web applications referenced above. You may be interested in reading also [http://howtoubuntu.org/how-to-install-lamp-on-ubuntu this] and [https://www.digitalocean.com/community/tutorials/how-to-install-wordpress-on-ubuntu-14-04 this].
* Demonstrate that the web application you installed works in next Tuesday session, screenshots/photos with explanation sent to e-mail above also suffice.
* Optional: Set up SSH public key authentication to <code>enos.itcollege.ee</code>.
* Optional: [https://www.raspberrypi.org/documentation/remote-access/ssh/passwordless.md Set up public key authentication to your Raspberry Pi]. Windows users might want to take a look at [https://winscp.net/eng/docs/ui_puttygen#obtaining_and_starting_puttygen PuTTYgen instructions].

Note: You don't have to necessarily use Raspberry Pi - Web application installed in Ubuntu VM is also accepted, also if you're maintaining similar installation of a production server that is accepted as well. [http://www.wampserver.com/en/ WAMP] on Windows is also accepted.

=Assignment: Set up basic IoT scenario=

[https://en.wikipedia.org/wiki/Internet_of_Things Internet of Things] is one of the emerging technologies (read: hype). IoT is essentially about getting everything online, including lightbulbs, switches, window shades etc. In this assignment LED symbolizes a light and the task is to implement code which allows user to switch the LED on and off over the network.

[[File:Raspberry-pi-gpio-18-led bb.png|600px]]

Goal: Get familiar how Python code can be started up. Build basic [https://en.wikipedia.org/wiki/Internet_of_Things IoT] appliance, a light that can be turned on and off via the Internet.

Deadline: 7. October

Points: 4 points

* Complete the [http://codeacademy.com/tracks/python Python track at CodeAcademy] if you haven't done that yet.
* Follow the wiki page Blinking LED section under [[Getting started with Raspberry Pi]].
* Get an LED blinking on command-line.
* Get LED blinking from Python code.
* Get basic HTTP server running in Python.
* Combine all of the above, build an HTTP server that can be used to turn LED on and off from via web browser.
* Optional: Take a peek at next assignment and upload working version to GitHub.
* Optional: [http://sourceforge.net/p/raspberry-gpio-python/wiki/PWM/ Smoothen the transitions using PWM].

=Assignment: Collaborating using Git=

Software development is usually done by several contributors, to facilitate efficient collaboration a distributed version control system is a must. In this assignment you'll upload your code to GitHub and modify fellow student's code to reflect changes in the Raspberry Pi setup:

[[File:Raspberry-pi-rgb-led bb.png|600px]]

Deadline: 14. October

Points: 5

Goal: Get familiar with distributed version control systems. Collaborate.

* Create [https://github.com/ GitHub] account if you haven't done so yet.
* Create a Git repository, eg http://github.com/your-username/rpi-iot-example
* Install Git on your Raspberry Pi by using <code>apt-get install git</code>.
* Clone the repository to your Raspberry Pi using <code>git clone http://github.com/your-username/rpi-iot-example</code>.
* Move the Python code created earlier to the Git repository directory.
* Use <code>git add</code> to add the files.
* Configure full name: <code>git config --global user.name "Firstname Surname"</code>
* Configure e-mail: <code>git config --global user.email first.last@domain.tld</code> 
* Use <code>git commit</code> to create the [http://blog.no-panic.at/2014/10/20/funny-initial-git-commit-messages/ initial commit].
* Use <code>git push</code> to push the commits to GitHub server.
* Set up [https://help.github.com/articles/generating-ssh-keys/ public key authentication between your laptop and GitHub servers], verify that <code>https://github.com/username.keys</code> gives the expected result.
* Use <code>git clone</code> to clone the repository to your laptop. Ubuntu should first <code>apt-get install git</code>, Windows and Mac users might want to take a look at [http://git-scm.com/download/ Git homepage]. If you're looking for graphical user interface take a look at [https://desktop.github.com/ GitHub Desktop] or [https://tortoisegit.org/ TortoiseGit].
* Create [https://en.wikipedia.org/wiki/README README] in the repository directory, populate it with relevant content - what is it about, who made it etc and commit the changes.
* In your Raspberry Pi setup replace the single-color LED with RGB LED as shown above.
* Clone '''fellow student's''' repository and adapt the code to reflect physical changes to the setup, the Python snippet should now permit changing the color of the light, have it blinking and turn it off. Other interesting modes are awarded with extra points.
* Use either [https://www.atlassian.com/git/tutorials/ Atlassian Tutorials], [http://rogerdudler.github.io/git-guide/ git - the simple guide] or [https://try.github.io/ Try Git] as a reference if you get lost.
* Document in the README what GPIO pins are used in the code for red, green and blue. Extra points for making the Python code [https://docs.python.org/2/library/argparse.html#module-argparse configurable from command-line].
* Late submissions will heavily lose points for failure to comply with [http://chris.beams.io/posts/git-commit/ decent commit messages].
* Send Lauri the URL of your repository at GitHub.

Git resources: [http://git-scm.com/book/en/v2 Pro Git Book] (read the basics to get kickstarted) and [https://www.codecademy.com/en/courses/learn-git/ Codecademy Git course].

=Assignment: Disassembling Python=

CPython is the default, most widely used implementation of the Python programming language. CPython is written in C. CPython compiles Python source into bytecode which is interpreted by a Python virtual (stack) machine. This is very similar to what is done with Java. Use [https://docs.python.org/2/library/dis.html dis] to disassemble a Python function into stack machine instructions. Follow [https://docs.python.org/2/library/dis.html#python-bytecode-instructions bytecode instructions] to determine what each instruction does.

Deadline: 21. October


==Example submission==

Consider following Python function, which calculates the sum of squares. For example sum_of_powers(2, 3) == 14 (1**2 + 2**2 + 3**2):

 def sum_of_powers(exponent, numbers):
     counter = 1
     return_value = 0
     while True:
         if counter > numbers:
             break
         return_value += counter ** exponent
         counter += 1
     return return_value
 
 # Following two lines are the ones which produce the instructions shown below
 from dis import dis
 dis(sum_of_powers)

Corresponding Python stack machine instructions extracted with <code>dis</code> are following. Columns correspond to: line number in the source code, instruction offset (in bytes), instruction name as listed [https://docs.python.org/2/library/dis.html in dis documentation], 

 22           0 LOAD_CONST               1 (1)               # Constant of 1 is pushed to stack
              3 STORE_FAST               2 (counter)         # Pushed value is popped and stored in variable counter
 
 23           6 LOAD_CONST               2 (0)               # Constant of 0 is pushed to stack
              9 STORE_FAST               3 (return_value)    # Pushed value is popped and stored in variable return_value
 
 24          12 SETUP_LOOP              43 (to 58)           # Loop until instruction no 58 is set up
 
 25     >>   15 LOAD_FAST                2 (counter)             # Value of variable <counter> is pushed to stack
             18 LOAD_FAST                1 (numbers)             # Value of variable <numbers> is pushed to stack
             21 COMPARE_OP               4 (>)                   # Two topmost values of stack are popped and compared,
                                                                 # boolean result is pushed back to the top of stack
             24 POP_JUMP_IF_FALSE       31                       # If top of the stack if False,
                                                                 # jump to instruction no 31 is performed.
                                                                 # Top of the stack is popped
 
 26          27 BREAK_LOOP                                       # Execution jumps out of the loop, the one
                                                                 # that was set up at inst no 12
             28 JUMP_FORWARD             0 (to 31)               # Placeholder probably due to the way pipeline is handled
 
 27     >>   31 LOAD_FAST                3 (return_value)        # Value of variable <return_value> is pushed to stack
             34 LOAD_FAST                2 (counter)             # Value of variable <counter> is pushed to stack
             37 LOAD_FAST                0 (exponent)            # Value of variable <exponent> is pushed to stack
             40 BINARY_POWER                                     # Exponentiation of two topmost values is performed and
                                                                 # substituted with the result
             41 INPLACE_ADD                                      # Two topmost values are added and substituted with the sum
             42 STORE_FAST               3 (return_value)        # Sum of the addition is stored in variable <return_value>
 
 28          45 LOAD_FAST                2 (counter)             # Value of variable <counter> is pushed to stack
             48 LOAD_CONST               1 (1)                   # Constant of 1 is pushed to stack
             51 INPLACE_ADD                                      # Two topmost values are added and substituted with the sum
             52 STORE_FAST               2 (counter)             # Sum is stored in the variable <counter>
             55 JUMP_ABSOLUTE           15                       # Code execution jumps to instruction no 15 (the beginning of the loop)
 
 29     >>   58 LOAD_FAST                3 (return_value)    # The value of variable <return_value> is pushed to stack
             61 RETURN_VALUE                                 # Return top of the stack to the function caller


In the Python VM the state consists of:

* Program counter (PC), the number of currently executed instruction
* The stack and most importantly top of stack (TOS)
* Constants extracted from source (co_consts)
* Variables names (co_names)
* Variables values (co_varnames)
* There are *no* registers!


Executing the function with arguments exponent=2 and numbers=3 will result in return value of 14, the arguments are already placed in the co_varnames array by the calling function. Also the constants used in the code are present, so you may assume following state in the Python interpreter just before entering the function body:

    -1. stack = []; co_varnames = [2, 3]; co_consts[?, 1, 0]

The steps that Python VM takes to get to the results are following:

     0. LOAD_CONST 1: stack = [1]
     3. STORE_FAST 2: stack = []; co_varnames = [2, 3, 1]
     6. LOAD_CONST 2: stack = [0];
     9. STORE_FAST 3: stack = []; co_varnames = [2, 3, 1, 0]
    12. SETUP_LOOP 43: stack = []; loop is set up, counter is 1
 
    Here we enter loop body for the first time
    
    15. LOAD_FAST 2: stack = [1]
    18. LOAD_FAST 1: stack = [1, 3]
    21. COMPARE_OP 4: stack = [False]
    24. POP_JUMP_IF_FALSE 31: stack = []; jump to instruction 31
    31. LOAD_FAST 3: stack = [0];
    34. LOAD_FAST 2: stack = [0, 1];
    37. LOAD_FAST 0: stack = [0, 1, 2];
    40. BINARY_POWER: stack = [0, 1]
    41. INPLACE_ADD: stack = [1]
    42. STORE_FAST 3: stack = []; co_varnames = [2, 3, 1, 1]
    45. LOAD_FAST 3: stack = [1];
    48. LOAD_CONST 1: stack = [1, 1];
    51. INPLACE_ADD: stack = [2]
    52. STORE_FAST 2: stack = []; co_varnames = [2, 3, 2, 1]
    53. JUMP_ABSOLUTE 15: jump to instruction no 15, counter is 2
 
    Here we enter loop body for the second time
    
    15. LOAD_FAST 2: stack = [2]
    18. LOAD_FAST 1: stack = [2, 3]
    21. COMPARE_OP: stack = [False]
    24. POP_JUMP_IF_FALSE 31: stack = []; jump to instruction 31
    31. LOAD_FAST 3: stack = [1]; here we have only 1**1
    34. LOAD_FAST 2: stack = [1, 2];
    37. LOAD_FAST 0: stack = [1, 2, 2];
    40. BINARY_POWER: stack = [1, 4]
    41. INPLACE_ADD: stack = [5]; here we already have 1**2 + 2**2
    42. STORE_FAST 3: stack = []; co_varnames = [2, 3, 2, 5]
    45. LOAD_FAST 3: stack = [2];
    48. LOAD_CONST 1: stack = [2, 1];
    51. INPLACE_ADD: stack = [3]
    52. STORE_FAST 2: stack = []; co_varnames = [2, 3, 3, 5]
    53. JUMP_ABSOLUTE 15: jump to instruction no 15, counter is 3
 
    Here we enter the loop body third time
    
    15. LOAD_FAST 2: stack = [3]
    18. LOAD_FAST 1: stack = [3, 3]
    21. COMPARE_OP: stack = [False]
    24. POP_JUMP_IF_FALSE 31: stack = []; jump to instruction 31
    31. LOAD_FAST 3: stack = [5]
    34. LOAD_FAST 2: stack = [5, 3];
    37. LOAD_FAST 0: stack = [5, 3, 2];
    40. BINARY_POWER: stack = [5, 9]
    41. INPLACE_ADD: stack = [14]; here we have 1**2 + 2**2 + 3**2
    42. STORE_FAST: stack = []; co_varnames = [2, 3, 3, 14]
    45. LOAD_FAST 3: stack = [3];
    48. LOAD_CONST 1: stack = [3, 1];
    51. INPLACE_ADD: stack = [4]
    52. STORE_FAST 2: stack = []; co_varnames = [2, 3, 4, 14]
    53. JUMP_ABSOLUTE 15: jump to instruction no 15, counter is 4
 
    Here we enter the loop body fourth (!!!) time
    
    15. LOAD_FAST 2; stack = [4]
    18. LOAD_FAST 1; stack = [4, 3]
    21. COMPARE_OP 4; stack = [True]
    24. POP_JUMP_IF_FALSE 31; stack = []; but the condition does not hold anymore so we jump out of the loop
    27. BREAK_LOOP; break out of the loop
    58. LOAD_FAST 3; stack = [14]
    61. RETURN_VALUE; return 14 to caller

==Assignment steps==

# Select one of the Fibonacci code examples below.
# Use <code>from dis import dis</code> and <code>dis(function_name_goes_here)</code> to disassemble the function to opcodes.
# Comment the stack machine instructions as shown above (3p).
# Invoke the Fibonacci number calculation function with n=2, follow the instructions and elaborate after each instruction executed a) the stack contents b) co_varnames contents c) co_names contents d) what happened as shown above. Note that certain code blocks will be executed repeatedly, which means you'll have more than '''30 instructions executed''' (2p).


Fibonacci with iterators:

<pre>
def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
</pre>

Fibonacci with recursion:

 def fib(n):
     if n==1 or n==2:
         return 1
     return fib(n-1) + fib(n-2)

Fibonacci with infinite loop and breaks:

 def fib3(n):
     a,b,i = 1,1,0
     while True:
         i += 1
         if i >= n: break
         b,a = a+b,b
     return a

Another variation:

 def fib4(n):
     a = 1
     b = 1
     i = 0
     while True:
         i += 1
         if i >= n: break
         s = a + b
         a = b
         b = s
     return a

=Assignment: Investigating compilers=

Use what you learned in the [https://wiki.itcollege.ee/index.php/Getting_started_with_GCC Getting started with GCC] session.
See assignment steps below.
Everything you need to understand ARM instructions should be [http://aelmahmoudy.users.sourceforge.net/electronix/arm/chapter2.htm here].
Another good resource seems to be [http://www.davespace.co.uk/arm/introduction-to-arm/ Introduction to ARM] by David Thomas.
See page 14 of [http://infocenter.arm.com/help/topic/com.arm.doc.ihi0042e/IHI0042E_aapcs.pdf Procedure Call Standard for the ARM® Architecture] if you want to learn more about how function calls are implemented on ARM.
See [http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0204j/Cihfddaf.html here] for more information about branching instructions: B, BL, BX.
<Insert extemely useful link here yourself>

Deadline: 4. November

==Example==

If you don't have Ubuntu installed on your machine skip next step and use SSH to perform these steps remotely at <code>enos.itcollege.ee</code>.
Otherwise install ARM cross-compiler:

 apt-get install gcc-arm-linux-gnueabi

Consider C snippet for calculating integer [https://en.wikipedia.org/wiki/Exponentiation exponentiation], place it in a file <code>power.c</code>:

 int power(long base, long exponent) {
     int counter;
     int result = 1;
     for (counter = 0; counter < exponent; counter++)
         result *= base;
     return result;
 }

===Generating assembly===

Compile ARM assembly of the code snippet:

 arm-linux-gnueabi-gcc -Os -S power.c -o power.s   # Cross-compile ARM assembly file power.s from C source code file power.c
 cat power.s                                       # Dump the assembly file on terminal

The compiler should produce something similar to following:

 	.arch armv5t
 	.fpu softvfp
 	.eabi_attribute 20, 1
 	.eabi_attribute 21, 1
 	.eabi_attribute 23, 3
 	.eabi_attribute 24, 1
 	.eabi_attribute 25, 1
 	.eabi_attribute 26, 2
 	.eabi_attribute 30, 2
 	.eabi_attribute 34, 0
 	.eabi_attribute 18, 4
 	.file	"power.c"
 	.text
 	.align	2
 	.global	power
 	.type	power, %function
 power:
 	@ args = 0, pretend = 0, frame = 0
 	@ frame_needed = 0, uses_anonymous_args = 0
 	@ link register save eliminated.
 	cmp	r1, #0
 	mov	r2, #1
 	ble	.L2
 	mov	r3, #0
 .L3:
 	add	r3, r3, #1
 	cmp	r3, r1
 	mul	r2, r0, r2
 	bne	.L3
 .L2:
 	mov	r0, r2
 	bx	lr
 	.size	power, .-power
 	.ident	"GCC: (Ubuntu/Linaro 4.7.3-12ubuntu1) 4.7.3"
 	.section	.note.GNU-stack,"",%progbits

===Commenting the assembly===

You can safely ignore the lines starting with dot, these are simply hints for the next stage of the compilation process.
Thus you're left only (!!!) 10 actual instructions. Here you can also see what kind of comments are expected from the submission:

 power:
 	cmp	r1, #0             /* Compare register r1 (second argument) contents against constant 0 */    
 	mov	r2, #1             /* Copy the constant 1 to register r2 */
 	ble	.L2                /* Jump to label .L2 if the comparison was false */
 	mov	r3, #0             /* Copy the constant 0 to register r3 */
 .L3:
 	add	r3, r3, #1         /* Perform r3 = r3 + 1 */
 	cmp	r3, r1             /* Compare register r3 and r1 (second argument) */
 	mul	r2, r0, r2         /* Perform r2 = r0 (first argument) * r2 */
 	bne	.L3                /* If r3 and r1 were different jump to label .L3
 .L2:
 	mov	r0, r2             /* Copy register r2 contents to register r0 */
 	bx	lr                 /* Jump back to caller */


===Analyzing the code===

Code analysis reveals that registers are mapped as following:

* <code>r0</code> - argument <code>base</code> and eventually return value
* <code>r1</code> - argument <code>exponent</code>
* <code>r2</code> - variable <code>result</code>
* <code>r3</code> - variable <code>counter</code>


We can also see how the <code>for</code> loop gets translated into assembly:

 power:
 	cmp	r1, #0
 	mov	r2, #1
 	ble	.L2
 	mov	r3, #0
 .L3:
 	add	r3, r3, #1 <---+
 	cmp	r3, r1         | 4 instructions are executed repeatedly
 	mul	r2, r0, r2     | if exponent is greater than 0
 	bne	.L3 -----------+
 .L2:
 	mov	r0, r2
 	bx	lr

===Stepping through the instructions===

When we execute the function with for example arguments base=5 and exponent=3 following happens in the processor.
Note that this will essentially calculates 5 ^ 3 (5 to the power of 3) which is 125.
Following has been done manually to illustrate how much time does it take to execute the the function.


 /* When processor enters the function body the arguments are already placed in registers r0=5 (base), r1=3 (exponent) */
 cmp r1, #0                        /* Compare exponent to 0 */
 mov r2, #1                        /* Place constant 1 in register r2,
                                      this corresponds to result = 1 in C code */
 ble .L2                           /* Exponent was not less than 0, so no jump to L2
 mov r3, #0                        /* Place constant 0 in register r3,
                                      this corresponds to variable counter */
 
 add r3, r3, #1                    /* Perform r3 = 0 + 1 which results in 1 being stored to r3
                                      this corresponds to first invocation of counter++ in C code */
 cmp r3, r1                        /* Compare counter (1 in this case) to exponent (3), this will be used by bne instruction below */
 mul r2, r0, r2                    /* Perform r2 = r0 * r2 which results in 1 * 5 = 5 being placed in r2
                                      this corresponds to first invocation of result *= base in C code */
 bne .L3                           /* The comparison resulted in counter being not equal to exponent, so we jump back to L3
                                      this corresponds to first invocation of counter < exponent in C code */
 
 add r3, r3, #1                    /* Perform r3 = 1 + 1 which results in 2 being stored to r3
                                      this corresponds to second invocation of counter++ in C code */
 cmp r3, r1                        /* Compare counter (2 in this case) to exponent (3), this will be used by bne instruction below */
 mul r2, r0, r2                    /* Perform r2 = r0 * r2 which results 5 * 5 = 25 being placed in r2
                                      this corresponds to second invocation of result *= base in C code */
 bne .L3                           /* The comparison resulted in counter being not equal to exponent, so we jump back to L3
                                      this corresponds to second invocation of counter < exponent in C code */
 
 add r3, r3, #1                    /* Perform r3 = 2 + 1 which results in 3 being stored to r3
                                      this corresponds to third invocation of counter++ in C code */
 cmp r3, r1                        /* Compare counter (3 in this case) to exponent (3), this will be used by bne instruction below */
 mul r2, r0, r2                    /* Perform r2 = r0 * r2 which results 25 * 5 = 125 being placed in r2
                                      this corresponds to third invocation of result *= base in C code */
 bne .L3                           /* The comparison resulted in counter being equal to exponent, so we DO NOT jump back to L3 */
 
 mov	r0, r2                     /* Copy register r2 contents (125) to register r0 */
 bx	lr                         /* Jump back to caller */
 /* Function returns with 125 placed in r0 this is where caller function should expect the return value */
 /* The other registers will still hold whatever values were left there: r1 = 3, r2 = 125, r3 = 3 */

===ARM registers===

If you get lost with the ARM register naming conventions use following as a guide.

ARM7 has 16x 32-bit registers:

  r0 (a1) - Argument/result/scratch register, this is where first function argument is usually placed
  r1 (a2) - Argument/result/scratch register, this is where second function argument is placed
  r2 (a3) - Argument/scratch register 3
  r3 (a4) - Argument/scratch register 4
  r4 (v1) - Variable register 1
  r5 (v2) - Variable register 2
  r6 (v3) - Variable register 3
  r7 (v4) - Variable register 4
  r8 (v5) - Variable register 5
  r9 (v6) - Variable register 6
 r10 (v7) - Variable register 7
 r11 (fp) - Frame pointer, variable register 8 
 r12 (ip) - Intra-procedure call scratch register
 r13 (sp) - Stack pointer
 r14 (lr) - Link register (to which memory address currently
                           executing function should return to?)
 r15 (pc) - Program counter (what is the memory address of instruction
      ^                      that we are going to execute next?)
      |
      +- These are simply aliases for the numbered registers and
         can be used interchangeably.

==Assignment steps==

# Select one of the Fibonacci calculation examples below and use ARM cross compiler as shown above to generate the assembly corresponding to the C source code (1p).
# Remove the compiler hints (lines starting with dot), this should leave you less than 20 instructions. If it's more than that try different optimization flags. Analyze and comment the assembly as shown above (1p).
# Use n=3 as argument and follow the instructions, what values are left in the registers after the function finishes (2p)?
# Optional/extra: Elaborate step by step what happens in the processor: what instruction is being executed and what values are left in registers after instruction finishes? (1p)
# Optional/extra: Recompile with different optimization levels: <code>-Os</code>, <code>-O0</code>, <code>-O1</code>, <code>-O2</code> and <code>-O3</code>. What differences did you notice? (1p)
# Optional/extra: Take a guess which one of the Fibonacci calculation functions below is the slowest? Which one is the fastest? Why? (1p)
# Send your conclusions as e-mail attachment to Lauri, attach the commented assembly, make sure you '''use the address supplied above with the course code''', otherwise your mail is not searchable in my mailbox.


Fibonacci calculation using <code>for</code>-loop:

 int fib(n) {
     int a = 1;
     int b = 1;
     int i;
     for (i = 0; i < n; i++) {
         int s = a + b;
         a = b;
         b = s;
     }
     return a;
 }

Fibonacci calculation using recursion:

 int fib2(n) {
     if (n == 1 || n== 2) {
         return 1;
     } else {
         return fib(n-1) + fib(n-2);
     }
 }

Fibonacci calculation using <code>while</code>-loop:

 int fib4(n) {
     int a = 1;
     int b = 1;
     int i = 0;
     while(1) {
         i += 1;
         if (i >= n) { break; }
         int s = a + b;
         a = b;
         b = s;
     }
     return a;
 }

=Assignment: Investigating microcontrollers=

In this assignment we use Arduino to implement traffic lights for [http://www.nobleled.com/uploads/110833/100_101.jpg crossroads].
If you don't care much about doing this assignment hands on, you can give a try [https://123d.circuits.io/ online].

==Assignment steps==

* Install Arduino IDE on your personal machine, on Windows/Mac check out [https://www.arduino.cc/ Arduino homepage] for instructions, on Ubuntu <code>apt-get install arduino</code> should suffice. You can also use school computers, Ubuntu has Arduino preinstalled.
* From Arduino IDE menu open up File -> Examples -> 01. Basic -> Blink
* In Arduino IDE menu Tools -> Board -> Arduino Mega2560
* In Arduino IDE menu Tools -> Serial port -> Select what makes sense
* On Ubuntu you may have to add yourself to the dialout group before you can access the serial ports. Use the command <code>sudo gpasswd -a $USER dialout</code>, log out and log in again to your PC.
* Press the second button in the toolbar to upload the code, make sure the changes take effect on the board. You should see on-board LED blinking.
* Connect some LED-s to the board. '''MAKE SURE YOU USE RESISTORS TO PROTECT LED-s AND THE BOARD'''
* Implement traffic light cycle using <code>digitalWrite</code> and <code>delay</code> in the <code>loop</code> function (3p)
* Use interrupts to read button presses, see example below. Pressing the button should toggle the LED now (1p)
* Extra: Use [https://www.arduino.cc/en/Reference/AnalogWrite PWM] to implement smoother blinking (1p)
* Extra: Use [http://lauri.vosandi.com/arduino/lcd1602-key-shield.html LCD1602] shield to display countdown (1p)
* Use [https://www.arduino.cc/en/Reference/Serial serial] interface to send messages to your PC.
* You can find useful code snippets for Robotics club equipment [http://lauri.vosandi.com/arduino here]

==Code example: reading button press with interrupts==

Set up a push button as shown below:

[[File:Arduino-pushbutton_bb.png|500px]]

Insert following code to Arduino IDE and upload it to Arduino, verify that it works:

 int led = 13;
 int button  = 2;
 int flag = LOW;
 
 void setup() {
     pinMode(led, OUTPUT);         // Set up pin 13 as digital output
     pinMode(button, INPUT);       // Set up pin 9 as digital input
     digitalWrite(button, HIGH);   // Turn in pull-up resistor
 
     // Associate interrupt handler with an event
     attachInterrupt(digitalPinToInterrupt(button), onButtonPressed, FALLING);
 }
 
 void onButtonPressed() {
     // Keep this as short as possible
     flag = HIGH;
 }
 
 void loop() {
     // Do something useful or let processor sleep here
     if (flag) {
         digitalWrite(led, HIGH);
         delay(2000);
         flag = LOW;
     }
 
     digitalWrite(led, LOW);
     delay(50);
 }

==Code example: Cycling through different traffic light states==

Add LED-s to the design:

[[File:Traffic-lights_bb.png|500px]]

Use following as hint to implement cycling through traffic light states:

 // Define pin numbers
 int car_green = 5;
 int car_yellow = 6;
 int car_red = 7;
 
 // For LED-s we're sinking the 5V voltage, hence LED is turned on when voltage on the pin is LOW
 int on = LOW;
 int off = HIGH;
 
 void setup() {
     pinMode(car_green, OUTPUT);
     pinMode(car_yellow, OUTPUT);
     pinMode(car_red, OUTPUT);
     digitalWrite(cars_yellow, off);
     Serial.begin(9600);
 }
 
 void loop() {
     Serial.println("Cars green, pedestrians red for 5 seconds");
     digitalWrite(cars_red, off);
     digitalWrite(cars_green, on);
     delay(5000);
 
     Serial.println("Green for cars is blinking 5 seconds");
     for(int j = 0; j < 10; j++) {
         digitalWrite(cars_green, j % 2 == 0);
         delay(500);
     }
 
     Serial.println("Cars red, pedestrians green for 5 seconds");
     digitalWrite(cars_green, off);
     digitalWrite(cars_red, on);
     delay(5000);
 }


==Skeleton of the final submission==

The real traffic light has of course a little bit more states:

 1. Cars green, pedestrians red for 10 seconds
 2. Cars green **blinking**, pedestrians red for 2 seconds
 3. Cars red, pedestrians green for 10 seconds
 4. Cars red, pedestrians green **blinking** for 2 seconds
 5. Cars yellow, pedestrians red for 2 seconds

So your final code will look something like this:

 // Define pin numbers here
 
 // Initially the flag is low
 int pedestrian_requested_crossing = LOW;
  
 void setup() {
     // Initialize necessary pins as digital outputs
     // Reset pins with digitalWrite
 
     // Initialize button pin as digital input
     // Enable pull-up resistor on button pin
     // Associate button interrupt handler function (onButtonPressed) below with the event on the button
 
 }
 
 void onButtonPressed() {
     // Here set pedestrian_requested_crossing flag to HIGH
     // Don't do anything else here!
 }
 
 void loop() {
     Serial.println("Cars green, pedestrians red for 5 seconds");
     digitalWrite(cars_red, off);
     digitalWrite(cars_green, on);
     // Set pedestrian lights here
     delay(5000);
 
     if (pedestrian_requested_crossing) {
 
         Serial.println("Green for cars is blinking 5 seconds");
         for(int j = 0; j < 10; j++) {
             digitalWrite(cars_green, j % 2 == 0);
             delay(500);
         }
 
         Serial.println("Cars red, pedestrians green for 5 seconds");
         digitalWrite(cars_green, off);
         digitalWrite(cars_red, on);
         // Set pedestrian lights here
         delay(5000);
 
         // Add another state here
 
         // And another state here
 
         // Reset flag here
     }
 }

=Assignment: Adders with NAND gates=

In this assignment we use chips to build an adder. Get max points (4p) by wiring up half adder and double your points (8p) if you can make full adder work as well :)

[[File:53-7400n-detailed.png]]


Each SN74HC03N chip contains four NAND gates arranged like this, observe the pit on the left. VCC corresponds to 5V power supply and GND corresponds to ground or 0V.


==Half adder==

Each [http://www.ti.com/lit/gpn/sn74hc03 SN74HC03] contains 4 NAND gates.
Use breadboard to wire up half adder with 7400 chips (4p):

[[File:Half-adder_bb.png|700px]]

The truth table for half adder:

   A  |  B  | Cout | Sum  | Human readable (how many bits are high?)
 -----+-----+------+------+-------------------------------------------
   0  |  0  |  0   |  0   | 0
 -----+-----+------+------+-------------------------------------------
   0  |  1  |  0   |  1   | 1
 -----+-----+------+------+-------------------------------------------
   1  |  0  |  0   |  1   | 1
 -----+-----+------+------+-------------------------------------------
   1  |  1  |  1   |  0   | 2

==Full adder==

You can double your points if you manage to wire up a full adder (+4p)

[[File:Nand-full-adder.png]]

On a breadboard it looks a bit messy, but if you pay attention to gate numbering as shown above it should make your life significantly easier.
The gates 1, 2, 3, 4 are placed in the leftmost chip; 5, 6, 7, 8 are placed in the middle one and gate 9 is the only one in the rightmost chip:



[[File:Full-adder_bb.png|700px]]


   A  |  B  | Cin | Cout | Sum  | Human readable (how many bits are high?)
 -----+-----+-----+------+------+-------------------------------------------
   0  |  0  |  0  |  0   |  0   | 0
 -----+-----+-----+------+------+-------------------------------------------
   0  |  0  |  1  |  0   |  1   | 1
 -----+-----+-----+------+------+-------------------------------------------
   0  |  1  |  0  |  0   |  1   | 1
 -----+-----+-----+------+------+-------------------------------------------
   0  |  1  |  1  |  1   |  0   | 2
 -----+-----+-----+------+------+-------------------------------------------
   1  |  0  |  0  |  0   |  1   | 1
 -----+-----+-----+------+------+-------------------------------------------
   1  |  0  |  1  |  1   |  0   | 2
 -----+-----+-----+------+------+-------------------------------------------
   1  |  1  |  0  |  1   |  0   | 2
 -----+-----+-----+------+------+-------------------------------------------
   1  |  1  |  1  |  1   |  1   | 3

==Unittest==

Use following code snippet on Arduino to test the circuit, it will shuffle through all the possible inputs and test whether the expected output is on the output pins.
If you see <code>sum</code> or <code>cout</code> outputs giving 0 all the time it's likely you have resistors of too low resistance in the circuit which is draining all the voltage on the NAND gate output pins.

 int PIN_A = 2;
 int PIN_B = 3;
 int PIN_CIN = 4;
 int PIN_SUM = 5;
 int PIN_COUT = 6;
 
 void setup() {
     // Set up serial
     Serial.begin(9600);
     
     // Set up operands
     pinMode(PIN_A, OUTPUT);
     pinMode(PIN_B, OUTPUT);
     pinMode(PIN_CIN, OUTPUT);
     digitalWrite(PIN_A, HIGH);
     digitalWrite(PIN_B, HIGH);
     digitalWrite(PIN_CIN, HIGH);
     
     // Set up measurement pins
     pinMode(PIN_SUM, INPUT);
     pinMode(PIN_COUT, INPUT);
     digitalWrite(PIN_SUM, HIGH); // Enable pull-up resistor
     digitalWrite(PIN_COUT, HIGH); // Enable pull-up resistor
 }
 
 void test(int a, int b, int cin) {
     int cout = a && b || a && cin || b && cin;
     int sum = a ^ b ^ cin;
     
     digitalWrite(PIN_A, a);
     digitalWrite(PIN_B, b);
     digitalWrite(PIN_CIN, cin);
     
     Serial.print("Writing: a=");
     Serial.print(a);
     Serial.print(", b=");
     Serial.print(b);
     Serial.print(", cin=");
     Serial.print(cin);
     Serial.print("  Expecting: sum=");
     Serial.print(sum);
     Serial.print(", cout=");
     Serial.print(cout);
     
     int measured_sum = digitalRead(PIN_SUM);
     int measured_cout = digitalRead(PIN_COUT);
 
     Serial.print("  Got: sum=");
     Serial.print(measured_sum);
     Serial.print(" cout=");
     Serial.print(measured_cout);
     
     Serial.print("  Test:");
     if (measured_sum != sum || measured_cout != cout) {
         Serial.print("  FAIL");
     } else {
         Serial.print("  GOOD");
     }
     Serial.println();
     delay(500);
 }
 
 void loop() {
     Serial.println("Running test");
     test(0, 0, 0);
     test(0, 0, 1);
     test(0, 1, 0);
     test(0, 1, 1);
     test(1, 0, 0);
     test(1, 0, 1);
     test(1, 1, 0);
     test(1, 1, 1);
 }

=Assignment: Debugging ALU design=

Bob had to ship the ALU design to the hardware manufacturer by yesterday. The project manager is angry about missed deadline. Bob still hasn't figured out why the ALU is not working properly. Help Bob by figuring out what's the problem.

If you're on Ubuntu install GHDL and GtkWave, otherwise simply use a school computer:

 sudo add-apt-repository ppa:pgavin/ghdl
 sudo apt-get update
 sudo apt-get install ghdl gtkwave git

Clone the repository

 git clone https://github.com/laurivosandi/vhdl-exercise

Use <code>make</code> to compile the components and run the testbench:

 cd path/to/vhdl-exercise
 make

Expected output of the testbench:

 alu_testbench.vhd:77:9:@360ns:(report note): Finished testing addition operation of ALU
 alu_testbench.vhd:106:9:@1us:(report note): Finished testing subtraction operation of ALU
 alu_testbench.vhd:135:9:@1640ns:(report note): Finished testing NAND operation of ALU
 alu_testbench.vhd:166:9:@2280ns:(report note): Finished testing NOR operation of ALU

However there are few bugs in <code>alu.vhd</code>, find the bugs and correct them. If this is your first experience with VHDL, take a look [http://lauri.vosandi.com/hdl/ here].

=Assignment: Publishing your work=

Deadline: 25. November

* Clean up your Git repositories and send the URL of a repository that you've actively worked on (for example the one from Java course) to Lauri, but before check the following:
** The repository should show changes you've made over at least few days.
** The repository has to contain only plaintext files unless there is a really good reason not to (eg. images).
** There has to be authorship information in the files.
** Add <code>.gitignore</code> file to your GitHub repositories to ignore temporary files, see [https://git-scm.com/docs/gitignore Git docs] for more details.
** Add [http://opensource.org/licenses LICENSE] file in the repository directory and commit the changes. LICENSE should answer to some important questions
*** Who is the copyright holder?
*** Under which conditions is redistribution permitted?
** Add nicely formatted README file, see [https://help.github.com/articles/markdown-basics/ Markdown] (online editor [http://dillinger.io here]) and [http://sphinx-doc.org/rest.html reStructuredText] for more details. README should answer to several silly questions:
*** What is the repository about?
*** Who made it?
*** How can the author be contacted? E-mail address, IRC chat channel on Freenode, Skype username?
*** How can the code be used? What hardware is necessary? How should the user wire the circuit to make it work? Add images if necessary.
*** What is the policy for including changes from third party developers?
* There will be more details here

=Extra points=

Here you can claim extra credit points for various tasks, this is mostly to improve the quality of wiki.itcollege.ee.
Once you have taken care of the task insert your name in the end of the line with corresponding date.

* Expand [[Getting started with Ubuntu#Installing in VirtualBox]] section with highlighted screenshots of VirtualBox. Points: 1p
* Create [[Claiming GitHub Student Developer Pack]] with screenshots how to add @itcollege.ee e-mail to your GitHub profile and claim [https://education.github.com/pack Student Developer Pack] Points: 2p