Log   |   Assignments   |   Source   |   Discussion   |   Feedback   |   About Me  |

This page details the discussions from each lecture.

2011-03-14

Ctrl-Alt-Delete Behaviour In Windows/Linux
Under DOS, this key combination is detected by the BIOS routine that handles keyboard input and soft-reboots the computer. This happens only when there is no other program in the system that intercepts the keyboard input.
In newer operating systems, keyboard interrupts are serviced by custom routines and the designers are free to assign any behaviour to the Ctrl-Alt-Del combination. Hence, under Windows (recent versions) and Linux (with GUI), pressing Ctrl-Alt-Del will invoke a special dialog box, with options to logout or kill processes etc. Under a Linux shell (Without X, say runlevel 1/2/3/4), Ctrl-Alt-Del still results in a soft reboot, since the kernel captures the combination and initiates a reboot.

2011-03-04

On 2011-03-01, we were asked to think about what would happen if a device raises an interrupt when the CPU is powered up. We learned today that CPUs usually disable all interrupts on power up. This makes sense, because the locations supposed to contain the ISRs will be empty at power up. So, interrupts will remain disabled until basic system initialisation is completed and ISRs are set up. In PCs, this is done by the BIOS and in embedded systems without a BIOS, the programmer herself has to do this.

We also learned about what happens during an interrupt:
  • CPU - Disable interrupts
  • CPU - Save CPU status registers / PC
  • CPU - Transfer control to interrupt handler
  • ISR - Save the program status to the stack, if required
  • ISR - Perform requested actions
  • ISR - Unsave the program status
  • ISR - EI instruction enables interrupts and returns control to CPU.
The RETI instruction does not enables the interrupts immediately, but only after one cycle. This is to ensure that the ISR is not interrupted between the EI and RET instructions. These things are very important, since badly written ISRs can result in bizarre system behaviour. For example, if a routine is used in two ISRs and is not designed to be re-entrant, the programmer *has* to ensure that the two interrupts are never nested. The issue with asynchronous systems is that reproducing failure is difficult. Hence, it is always best to think a lot before starting to write ISRs.

Dealing With Multiple Interrupts When multiple devices are present, the interrupts can be handled using a polling mechanism. However, this is slow and can be used only when the devices are slow and all the devices support buffering of data.
So, in modern systems, a priority based interrupt system is used. There will be a Priority Interrupt Controller which can handle a number of devices. The PIC assigns priorities to each devices based on which pin the device is connected.

The Priority Interrupt Controller


The Intel 8259 was the PIC used in the original IBM PC. In recent hardware, this has been replaced by the Intel APIC.

Catastrophic Situations in a Computer
We had a discussion about catastrophic failures in computer systems, like power failure, misbehaving hardware etc. We had a brief discussion on detecting memory errors and correcting them. What I found very interesting was the discussion on using the Non-Maskable Interrupt (NMI) to handle power failures. I knew that NMIs existed, but never knew what they were used for. The professor told us that the NMI can be used to perform an emergency shut-down procedure when a power failure is detected. This is possible because the computer power supply usually has a capacitor in the output stage and so power is retained for a few milliseconds even after input power is lost. During this period, the CPU can detect the power failure and perform activities like saving values in registers to an EEPROM, parking hard disk heads etc. The professor also told us about PDP-11 systems that completely save their state on power failure and start from that point on restoring power. I found this good article on NMIs here .

Just before winding up the class, the professor asked us to think about how to enable interrupts in an 8086 system, without using the EI instruction. I think if we load the values that we want to be stored back to the CPU registers in the stack and execute an IRET instruction, we can enable interrupts. I am not sure if this would be possible in all operating modes, though.

2011-03-02

Today, the professor gave us an introduction to good coding practices and asked us to find out the coding guidelines and standards. It is very important to follow coding standards for the multiple reasons
  • Source code has to be readable so that maintainence is easy.
  • If we follow a set of guidelines, the code tends to be unambiguous and hence less prone to bugs.
The following are the general guidelines to be followed while developing an application:
    General
  • Do not use global variables, unless absolutely necessary.
  • Initialise variables. I have learned from experience that uninitialised variables can have strange and far-reaching consequences.
  • When in doubt, use paranthesis.
  • Design functions to return values instead of pointers. That is, an error in the called function should not create an error in the calling function.

  • Comments
  • The source code should document itself - it should be well-commented. All variable declarations should be accompanied by comments stating the purpose and data type of the variable. All functions should have a comment header, stating the purpose, parameters and return values. The source file itself should have a comment header, stating the program functionality, details of the author and revision history.

  • Code Structure
  • Write only one statement per line.
  • Code should be properly indented. Contents of structures, loops and logical blocks should be indented by a tab. It is always best to indent the code as you write it, rather than afterwards (Even if the IDE has an auto-indent feature).
  • If a function grows very large, consider splitting it into different, smaller functions. The cyclomatic complexity of a function should not exceed 10 unless it is really necessary.
  • Break complex logical conditions into multiple lines.
  • Use clear, unambiguous names for files, functions and variables. The names, however, shouldn't be too large that we spend more time typing in variable names in place of actual code. Constant names should be in upper case, for easy identification. Also, #define statements should be used for constants which are used at multiple places.
  • Put different logical sections of the program in different files, instead of having a single large source file. Large files are difficult to maintain and debug.
  • Never include a C file. Use header files to specify the interface and include the header alone.
  • Use a Makefile for building the sources.


References
Recommended C Style and Coding Standards
Standards and Style for Coding in ANSI C
C Coding Standards


2011-03-01

The professor had asked us to think about how to drive an LED from a microprocessor output on 2011-02-25. This was in context of the pin in M68000 which goes high when there is a stack error in system mode. I had thought about it, but didn't write it. He gave us the answer in yesterday's class.

Driving an LED from a digital circuit

We should have a buffer between the actual circuit and the LED, since digital ICs are not really designed to deliver current to a load. Also, even when connecting the buffer, it is best to connect the LED from the Vcc to the buffer, as shown above, since digital ICs can sink more current than they can source.

Edit 1: 2011-03-02
I'd left out the current limiting resistor (R), without which the LED would've lost it's magic smoke and died. I guess I got carried away when I got a chance to write about things from my past life as an electrical engineer. Thank you sir, for pointing it out. I will be more careful in the future.

2011-02-24

I just modified the UBCD iso image to include DEBUG.COM using a utility called isomaster. This utility was available in the Fedora repository itself and I'm sure the Ubuntu repo has it too. I am running UBCD on a virtual machine using the VMWare player since I didn't want to reboot my laptop a lot of times. I was able to do some basic stuff with DEBUG.COM, like listing and modifying the CPU registers, dumping values in the memory, disassembling values in the memory etc. Interestingly, like the professor told us, there is really a jump instruction at the address FFFF:0000.

The jump instruction at location FFFF:0000 in the x86

The first jump instruction points to F000:E05B and I found another jump instruction there, pointing to F000:3AE5.

Another jump instruction at location F000:E05B

The code in F000:3AE5 starts with a CLI (Clear IF / Disable interrupts) instruction and I assume this is the beginning of some initialisation routine, probably the ROM initialisation.

The ROM initialisation code at F000:3AE5 in the x86

I have not looked further into what the sequence of instructions at this location do. Also, I didn't understand why there are a series of jumps to the next instruction from location F000:3AF9 till F000:3B02.

I also found this small piece of code which reboots the system! :) (Though I didn't understand how it works).
E 40:72 34 12
RCS
FFFF
RIP
0000
G


References:
Selected 8086 Instructions
DEBUG Tutorial
PC Debug Routines


2011-02-14

Today, the discussion started with what relocatable code is. We learned that if we want to relocate code in machine format, we need a program as complex as the CPU itself, since it will have to decode all the instructions and addressing modes. So, relocation is usually done on some intermediate form of the code, which marks the bytes which need to be changed during relocation. This format is called Relocatable Object Code and compilers create code in this format. Before execution, the linking loader makes the appropriate modifications on this intermediate form and makes it ready for exection.

The professor then explained to us that relocatable code is not really in executable format and it was not the answer to the question asked in the previous lecture. He told us about Position Independent Code and also that PIC is not necessary when an operating system is present. We encounter such issues when there is no OS around, like when a processor powers up. The issues that are to be handled at power up are:
  • All memory locations have unknown values (junk)
  • Where to start execution from?
One possible way to solve the power-up issue is to say that the processor always starts execution from address 0 and have a particular input signal (Say, the reset pin of the processor) at a known value till the user gives some input. During this state, the user can enter data directly into the required memory locations (including location 0) using a hardware interface (A keypad and two sets of flip-flops, one set for data and the other for address).

Another way is to use a ROM, with the required boot-up code in the start location. If we put the start address/ROM in the beginning of the address space, we can't change the size of the ROM without affecting the RAM address / hardware (ROM chip select lines). Also, I read here that many architectures map interrupt/exception vectors to start of the address space and putting a ROM at the beginning would make it impossible to change these vectors.

So, the start vector is made to point to a location near the end of the address space, with space of just one instruction left. This location can contain a jump to another location close by, forming a loop. In this case, the RAM addresses with start from 0 itself and a change in ROM will not affect that. Also, the RAM addresses can grow till it reaches the ROM address, which is close to the top of the address space.

I've programmed PIC micro-controllers, which usually start executing at the start vector (usually 0000H) and have worked with embedded code at work, but had not given any deep thought to how the start vector is decided or how the PC is initialised at power-up.

We were asked to think about how the CPU is brought to a known state on power-up. Also, what facility in a flip-flop is used to bring it to a know state?
I know that flip-flops have preset and clear lines, which sets the stored value to 1 and 0 respectively. The processor can have an internal/external power-on-reset circuitry which will give preset and clear signals as required.

Edit 1: 2011-02-24
The professor told us that the flip-flops have to be in a known state before the first clock pulse arrives and so we cannot use an input that depends on the clock. Hence, the present and clear inputs are asynchronous. That is, these inputs will set/reset the flip-flop, regardless of what state the clock input is in.

References:
Power-on-reset (Wikipedia)




2011-02-11

I found today's class very interesting. We learned about how parameters are passed to functions and how each instance of a function has its own set of local variables on the stack. We also saw that if the stack supports only the PUSH and POP operations, it would be impossible (or extremely difficult) to implement function calls properly. That is, when a function is called, the following data is pushed in to the stack (in the specified order):
  • Local variables of the called function
  • Parameters to be passed to the called function
  • Return address
As is clear from the above list, using just the POP instruction, it's not possible to access anything else without first removing the return address from the stack. In such cases, it is possible to access data without disturbing the contents of the stack, if the processor provides a Stack-Pointer Relative addressing mode. The PDP-11 and Motorola 68000 processors support SP relative addressing modes.

PDP-11 Addressing Modes
Code Mode Description
0 Register direct Operand is in the register
1 Register indirect Operand address is in the register
2 Auto-increment Register contains address of operand, increment after use
3 Auto-increment indirect Register contains address of address of operand, increment by 2 after use
4 Auto-decrement Register contains address of operand, decrement before use
5 Auto-decrement indirect Register contains address of address of operand, decrement before use
6 Index Base value of address provided in instruction and index in register
7 Index Indirect Base value of address of address in instruction, index in register
PC Relative Addressing Modes
27 Immediate Operand contained in the instruction
37 Absolute Address is contained in the instruction
67 Relative Address = OffsetGivenWithInstruction + PC + 2
77 Relative Indirect AddressOfAddress = OffsetGivenWithInstruction + PC + 2
SP Relative Addressing Modes
16 Indirect Operand is on stack-top
26 Auto-increment Operand is on stack-top, POP after use
36 Auto-increment indirect AddressOfOperand on stack-top, POP after use
46 Auto-decrement PUSH operand into the stack
66 Indexed Operand = SP+PositiveIndexProvided
76 Indexed indirect AddressOfOperand = SP+PositiveIndexProvided
The PC and SP addressing modes are new to me and they seem to be very interesting and treating PC (R6) and SP (R7) like general purpose registers is also a novel idea, providing the programmers with a lot of power. This also answers the question asked on 2011-02-04 about the CPU which allows modification of the PC.

References:
PDP-11 Architecture (Wikipedia)

We were asked to think about the following problem:
Is it possible to write a program which will run regardless of in which part of the memory it is loaded to? If so, how can it be done?
I searched on the internet and found two possible results -
  • Relocatable Code - This is object code created by the compiler, that can be re-located by either the linker (during link time) or by the loader (during run time).
  • Position Independent Code - Here, the code itself can run from any location, without help from any other programs (linker/loader). This is achieved by changing all absolute addresses to values relative to the PC.
Please refer to discussions on 2011-02-14 for more details.
References:
Position Independent Code (Wikipedia)
Relocation (Wikipedia)


Updated on 2011-02-14

2011-02-09


We learned more about user input validation in today's lab session. The following are general guidelines for validating data (Especially on web forms):
  • Always retain control of the program. It should never crash, no matter what input is given.
  • Data type checks should be done - A character should not be accepted in a number field.
  • In case of an invalid input, the error message should be given immediately so that the user can correct it then itself.
  • Provide clear error messages so that the user can identify the problem clearly.
  • In case of an error in the entry, allow the user to correct the mistake alone, rather than asking her to enter the whole input again.
  • User should have some freedom while entering data. For instance, leading and trailing spaces should not be considered invalid and can be ignored silently. Also, a few spaces between the sign and a number can be accepted. Comma separated numbers can also be accepted.
  • Always limit size of the input - Never allow the user to enter something larger than the space allocated for it
  • Even text input should be validated - For length and special characters which might lead to security breaches (< or > or scripting language keywords are not to be allowed inside a name field).
  • Ensure that no critical field is left blank.
On a lighter note, here is how Randall Munroe emphasises the importance of input validation in this XKCD cartoon - View.

We also learned about the dangers behind floating point numbers:
  • Mathematical expressions may not hold for floating point numbers. The simplest example for this is
    (a+b)+c != a+(b+c)
    in a computer (When a is large and b is small)!
  • We also saw multiple instances where loss of precision occurs in float operations and how to handle such situations.
    b*b >> 4*a*c in a Quadratic Equation:
    • Problem: (b*b - 4*a*c) evaluates to b*b in this case, resulting in one root calculated as b and the other 0
    • Solution: Calculate the non-zero root (with some loss of precision) and find the other root using the property that sum of roots is equal to c/a.

    b*b almost equal to 4*a*c
    • Problem: Precision is lost when (b*b - 4*a*c) is calculated.
    • Solution: Represent b*b as B+delta1 and 4*a*c as B+delta2 where delta* contains the decimal part alone. Now, we just need to subtract delta2 from delta1 and since both numbers are small, precision is not lost.
  • When using floating point numbers, inform the user about the number of guaranteed digits of precision, especially when there is possible loss of precision (as in above cases).
  • There is no use in printing a number with 12 decimal places when the IEEE754-32-bit format itself does not guarantee more than 7.
  • We realized that an algorithm might be perfect on paper, but can give totally wrong results when implemented in a computer system.

References:
Validating User Input.
Data Validation (Wikipedia).
IEE754 Format (Wikipedia).

2011-02-07 / 2011-02-08


These lectures were about addressing modes, data abstractions and temporary storage allocation.

The following questions were asked in class for use to think about:
Practical application where a function is to be called based on the value of an index?
Interrupt service routines are functions which are called based on the value of an index - the interrupt vector.

2011-02-04


Today, we learned about CPUs and instruction formats. We learned that the CPU's opcodes must be maintained as generic as possible and the operand that varies from time to time should be stored separately.

The following questions were asked in class for use to think about:

If we need to store only a single bit, which is the ideal position to store - MSB or LSB?
In which case will we need to use a random value for indexing an array?
I really don't know the answer to these two question. I'll try to look up the answer somehow.

Which is the CPU that allows modification of PC by user programs?
The PDP and VAX ISAs have instructions which allow direct manipulation of the PC. While looking for this answer, I also found out that these processors were "Orthogonal". That is, instructions can use any data type and through any addressing mode.

References:
www.osdata.com - Register Set
VAX (Wikipedia)
Orthogonal Instruction Set (Wikipedia)
Program Counter Addressing Mode


Write a program which accepts one character from the user and say whether it is a vowel or a consonant without using any logical operators.
I saw Kashyap's implementation, which is pretty smart. Now that I know that solution, my ideas seem to be biased towards similar solutions. I need to see if I can find a different way of doing it.

2011-02-01


Today's class was about presentation of data and how the information rendered on the user's screen seldom matches the creator's intend. Also, I learned that we should write our code/pages assuming only the minimum possible resources. I also learned that malloc should be used as few times as possible to avoid errors due to memory allocation failure. That is, we should allocate a sizeable amount of memory once and keep using it for different purposes, rather than allocating memory multiple times.

I also learnt about how serif fonts are not rendered properly on computer screens, especially at small sizes. I have always preferred sans-serif fonts and this is probably the reason.

I also learned that colours are not guaranteed to be rendered properly in all browsers. Long back, I have seen an option to "Restrict colors to web palette" in an image processing tool. I learned today that this option is for restricting the colours in the image to the 216 browser-safe colours.

The following questions where posed for us to think about:

What are the guidelines for setting up images on the web?
  • Use good quality photos (Not blurred or dark)
  • Specify width and height for all images - So that the page can load even before the image is loaded
  • Provide a text equivalent (alt text) so that the information is not missed out on browsers without image rendering capabilities
References:
Google Webmaster Tools Help - Images
HTML Techniques for Web Content Accessibility (W3C)

What hardware resources are required for using processes?
I am not very sure about this, but I think the hardware should support some mechanism for fast context switching such as multiple sets of registers and instructions for saving and restoring context. I will keep looking and try to find a better answer.

2011-01-31

In today's class we discussed the desirable properties of a document on the web, how rendering information is embedded in a markup language and about HTML entities. We also talked about regular expressions and usage of escape characters.

The following questions were posed in the class for us to think about:

Which is the program that uses only plain text (ASCII) and works perfectly?
I think the telnet program fits the description. It is used for communicating with remote servers in text mode. It does have an option for binary data transfer, but mostly used for communication in ASCII text only.

After discussing with others in the class, the HTTP protocol also came up as a possible answer, since HTTP too uses plain text only.

Try a regular expression with 200 escape characters
I tried doing this with the Boost library in C++, but got some strange compile errors citing mismatched parameters to the regex definition itself. I will try to debug this and post the updates.

2011-01-18


Practical applications of quadratic equations - Modelling dynamic systems - Differential equations - Solution requires solution to polynomial equations - Relation between nature of solution of the equation and behaviour of the system Traction - Conductor and catenary design
User-friendliness of computer systems - Usability for Left-handed / differently abled individuals - Relevance of technology - Rural populations cannot exploit technology even if they have access, due to language barriers
All computer programs should be designed to handle failures since failure is inevitable in systems built by humans
Packed decimal representation of numbers - Decimal arithmetic - Decimal adjust
Floating point representation - Guard digits

2011-01-17


Early computer systems - 6-bit representation - Need for more bits
Why 8 bits and not 7? - Data transmission - Minimum quantum of information - Numbers
8-bit character codes - ISO-8859 / MS-1252 - Multiple languages possible, but difficult in single document, since no way to represent what language the extra 128 characters contain.
Unicode - 64k characters - Indian language representations still not mature
Number representation - 2's complement - Unique representation for 0
Overflow detection in 2's complement operations
Problems requiring huge amount of processing:
Singular integrals - Integrand function has infinite values at one or more points in the domain of integration
Karmarkar's Algorithm

2011-01-14

Basic operation on text - Comparison
Properties of good mapping - Unique / Support comparison / Easy and unique reverse mapping
Rationale for ASCII codes
Text - Always 2D - Easy to read that way
Evolution of input methods for text editing

2011-01-12

Fundamental form of human expression - sound. But text, natural to humans and easily processed by machines
Set of symbols for communication with the computer
Indian languages vs English - Ambiguity - Punctuation marks/Caps - Header+Text in old Indian texts

2011-01-05

Machine = Resources + Methods to deal with resources - Method should never constrain the resource
Programming languages
limitations of functions

2011-01-04

Compare speed of execution of 8085 and 80386
Von Neumann architecture - self changing code
Memory - Address stabilisation time