Introduction to Hashing

Hashing is a method to store data in an array so that storing, searching, inserting and deleting data is fast. For this every record needs an unique key.The basic idea is not to search for the correct position of a record with comparisons but to compute the position within the array. The function that returns the position is called the 'hash function' and the array is called a 'hash table'.

Main idea: Use an array of size m and the key k as address of the array.
A hash function h is used to map keys to [0::m-1].
Key technical issues :
- What is a good h? A good function avoids (but does not eliminate)collisions, and is quick to compute.
- How do we resolving collisions? Retrieval time is a function of collisions.
- What if we run out of space in the table?
- Can we rearranging keys upon an insertion?

A hash function is any well-defined procedure or mathematical function that converts a large, possibly variable-sized amount of data into a small datum, usually a single integer that may serve as an index to an array. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes.A hash function may map two or more keys to the same hash value.Hash functions are related to (and often confused with) check sums,check digits, fingerprints, randomization functions, error correcting codes, and cryptographic hash functions. Although these concepts overlap to some extent, each has its own uses and requirements and is designed and optimized differently.

A hash table or hash map is a data structure that uses a hash function to efficiently map certain identifiers or keys (e.g., person names) to associated values (e.g., their telephone numbers).n general, a hashing function may map several different keys to the same index. Therefore, each slot of a hash table is associated with (implicitly or explicitly) a set of records, rather than a single record. For this reason, each slot of a hash table is often called a bucket, and hash values are also called bucket indices.

RS422 Standard

RS-422 is a telecommunications standard for binary serial communications between devices. It is the protocol or specifications that must be followed to allow two devices that implement this standard to speak to each other. RS-422 is an updated version of the original serial protocol known as RS-232.

This standard was introduced in 1975 to offer improvements over the older RS-232 standard. It provides a balanced line with optional termination. The standard uses a voltage differential of 2v min to 5v max to represent the binary 0's and 1's. The specification allows data rates up to 10M baud at 40 feet maximum cable length.
The maximum cable length that can be driven will depend on the baud rate, the driver/receiver IC's, the cable type, and the amount of electrical noise in the surrounding environment. RS-422 can be used for point-to-point communication or for multi-drop one-master/many-slave systems.

The RS-422 standard only defines the characteristic requirements for the balanced line drivers and receivers. It does not specify one specific connector, signal names or operations. RS-422 interfaces are typically used when the data rate or distance criteria cannot be met with RS-232. The RS-422 standard allows for operation of up to 10 receivers from a single transmitter. The standard does not define operations of multiple tri-stated transmitters on a link.

RS-422 is a balanced four wire system. The signal sent from the DTE device is transmitted to the DCE device through two wires and the signal sent from the DEC device to the DTE device is transmitted through the other two wires. The signals on each pair of wires are the mirror opposite of each other, i.e., a "1" datum is transmitted as a plus 2 volt reference on one wire and a minus 2 volt reference on the other wire. To send a "0" datum, a minus 2 volt reference is transmitted through one wire and a plus 2 volt reference on the other wire. That is the opposite of what was done to transmit a \'1\' datum.

The RS-422-A interfaces between the Data Terminal Equipment (DTE) and Data Communication Equipment (DCE) or in any point-to-point interconnection of signals between digital equipment. It employs the electrical characteristics of balanced-voltage digital interface circuits.

RS485 Standard

RS-485 is a telecommunications standard for binary serial communications between devices. It is the protocol or specifications that need to be followed to allow devices that implement this standard to speak to each other. A RS-485 compliant network is a multi-point communications network. The RS-485 standard specifies up to 32 drivers and 32 receivers on a single (2-wire) bus. RS-485 drivers are now even able to withstand bus contention problems and bus fault conditions. A RS-485 network can be constructed as either a balanced 2 wire system or a 4 wire system. If a RS-485 network is constructed as a 2 wire system, then all of the nodes will have equal ranking. A RS-485 network constructed as a 4 wire system, has one node designated as the master and the remaining nodes are designated as slaves. The maximum cable length can be as much as 4000 feet because of the differential voltage transmission system used. The typical use for RS485 is a single PC connected to several addressable devices that share the same cable.

RS485 meets the requirements for a truly multi-point communications network, and the standard specifies up to 32 drivers and 32 receivers on a single (2-wire) bus. With the introduction of "automatic" repeaters and high-impedance drivers / receivers this "limitation" can be extended to hundreds (or even thousands) of nodes on a network. RS485 extends the common mode range for both drivers and receivers in the "tri-state" mode and with power off. Also, RS485 drivers are able to withstand "data collisions" (bus contention) problems and bus fault conditions.

SPECIFICATIONS RS485
- Mode of Operation DIFFERENTIAL
- Total Number of Drivers and Receivers on One Line 1 DRIVER & 32 RECEIVER
- Maximum Cable Length 4000 FT.
- Maximum Data Rate 10Mb/s
- Maximum Driver Output Voltage -7V to +12V
- Driver Output Signal Level (Loaded Min.) Loaded +/-1.5V
- Driver Output Signal Level (Unloaded Max) Unloaded +/-6V
- Driver Load Impedance (Ohms) 54
- Max. Driver Current in High Z State Power On +/-100uA
- Max. Driver Current in High Z State Power Off +/-100uA
- Slew Rate (Max.) N/A
- Receiver Input Voltage Range -7V to +12V
- Receiver Input Sensitivity +/-200mV
- Receiver Input Resistance (Ohms) >=12k

RS232 Standard

RS232 is a asynchronous serial communication protocol widely used in computers and digital systems. It is called asynchronous because there is no separate synchronizing clock signal as there are in other serial protocols like SPI and I2C.
In RS232 there are two data lines RX and TX. TX is the wire in which data is sent out to other device. RX is the line in which other device put the data it need to sent to the device.
Voltage levels in RS232 are HIGH=-12V and LOW=+12V.

RS-232 Specifications :
- Cabling : Single-ended
- Number of Devices : 1 transmit, 1 receive
- Communication Mode : Full duplex
- Distance(max) : 50 feet at 19.2kbps
- Data Rate(max) : 1Mbps
- Signaling : Unbalanced
- Mark(data 1) : -5V (min) -15V (max)
- Space(data 0) : 5V (min) 15V (max)
- Input Level(min) : ±3V
- Output Current : 500mA
- Impedance : 5kW (Internal)
- Bus Architecture : Point-to-Point

RS232 Data Transmission :
Transmission
1. When there is no transmission the TX line sits HIGH (STOP CONDITION).
2. When the device needs to send data it pulls the TX line low for 104uS (This is the start bit which is always 0).
3. Then it sends each bit with duration of = 104uS.
4. Finally it sets TX lines to HIGH for at least 104uS (This is stop bit and is always 1).
Reception :
1. The receiving device is waiting for the start bit i.e. the RX line to go LOW.
2. When it gets start bit it waits for half bit time i.e. 104/2 = 51uS, i.e.it is in middle of start bit, it reads it again to make sure it is a valid start bit and not a spike.
3. Then it waits for 104uS and now it is in middle of first bit. It then reads the value of RX line.
4. In the same way it reads all the 8 bits.
5. Now the receiver has the data.

Limitations of RS232 Standard :
* The large voltage swings and requirement for positive and negative supplies increases power consumption of the interface and complicates power supply design. The voltage swing requirement also limits the upper speed of a compatible interface.
* Single-ended signaling referred to a common signal ground limits the noise immunity and transmission distance.
* Multi-drop connection among more than two devices is not defined. While multi-drop "work-arounds" have been devised, they have limitations in speed and compatibility.
* Asymmetrical definitions of the two ends of the link make the assignment of the role of a newly developed device problematic; the designer must decide on either a DTE-like or DCE-like interface and which connector pin assignments to use.
* The handshaking and control lines of the interface are intended for the setup and takedown of a dial-up communication circuit; in particular, the use of handshake lines for flow control is not reliably implemented in many devices.
* No method is specified for sending power to a device. While a small amount of current can be extracted from the DTR and RTS lines, this is only suitable for low power devices such as mice.
* The 25-way connector recommended in the standard is large compared to current practice.

Data Communication Modes

Today computer is available in many offices and homes and therefore there is a need to share data and programs among various computers with the advancement of data communication facilities. The communication between computers has increased and it thus it has extended the power of computer beyond the computer room. Now a user sitting at one place can communicate computers of any remote sites through communication channel.

In data communication four basic terms are frequently used. They are :
* Data: A collection of facts in raw forms that become information after processing.
* Signals: Electric or electromagnetic encoding of data.
* Signaling: Propagation of signals across a communication medium.
* Transmission: Communication of data achieved by the processing of signals.

There are three ways for transmitting data from one point to another :
- Simplex :Data only flows in one direction.A good example of simplex
communications is a radio station and your car radio. Simplex is not often
used in computer communications because there is no way to verify when or if data is received. However, simplex communications is a very efficient way to distributed vast amounts of information to a large number of receivers.
- Half Duplex : In this mode, devices allow both transmission and receiving, but not at the same time. Essentially only one device can transmit at a time while all other half-duplex devices receive. RS-485 works in half-duplex mode.
- Full Duplex : In this mode, devices can transmit and receive data at the same time. RS232 and RS422 are examples of Full Duplex communications. There are separate transmit and receive signal lines that allow data to flow in both directions simultaneously.

Difference between buffer and cache ?

A buffer is a region of memory used to temporarily hold output or input data.Buffers can be implemented in either hardware or software, but the vast majority of buffers are implemented in software. Buffers are used when there is a difference between the rate at which data is received and the rate at which it can be processed.

The terms "buffer" and "cache" are not mutually exclusive and the functions are frequently combined; however, there is a difference in intent. A buffer is a temporary memory location, that is traditionally used because CPU instructions cannot directly address data stored in peripheral devices. Thus, addressable memory is used as intermediate stage.

Additionally such a buffer may be feasible when a large block of data is assembled or disassembled (as required by a storage device), or when data may be delivered in a different order than that in which it is produced. Also a whole buffer of data is usually transferred sequentially (for example to hard disk), so buffering itself sometimes increases transfer performance. These benefits are present even if the buffered data are written to the buffer once and read from the buffer once.

A cache also increases transfer performance. A part of the increase similarly comes from the possibility that multiple small transfers will combine into one large block. But the main performance-gain occurs because there is a good chance that the same datum will be read from cache multiple times, or that written data will soon be read. A cache's sole purpose is to reduce accesses to the underlying slower storage. Cache is also usually an abstraction layer that is designed to be invisible from the perspective of neighboring layers.

Page/Disk Cache and Web Cache

PAGE CACHE :
Page Cache or disk cache is transparent buffer of disk-backed pages kept in main memory (RAM) by the operating system for quicker access. All memory that is not directly allocated to applications is usually utilized for page cache. Since non-dirty pages in the page cache have identical copies in secondary storage(hard disk), discarding and re-using their space is much quicker than paging out application memory, and is often preferred.The page cache also aids in writing to a disk. Pages that have been modified in memory for writing to disk, are marked "dirty" and have to be flushed to disk before they can be freed. When a file write occurs, the page backing the particular block is looked up. If it is already found in cache, the write is done to that page in memory. Otherwise, when the write perfectly falls on page size boundaries, the page is not even read from disk, but allocated and immediately marked dirty. Otherwise,the page(s)are fetched from disk and requested modifications are done.

WEB CACHE :
Web caching is the caching of web documents(e.g.,HTML pages, images) to reduce bandwidth usage, server load, and perceived lag. A web cache stores copies of documents passing through it; subsequent requests may be satisfied from the cache if certain conditions are met.
With a local cache in operation, user web object requests go via the local cache which then retains a copy of the said web object. This results in all subsequent requests for the same object being fulfilled from the local cache instead of from the site of origin. This process of web caching minimizes the amount of times identical web objects are transferred from remote websites by retaining copies of requested URLs in a cache. A web cache can be installed utilizing both software and hardware, and can run on various different platforms.
With a local cache in operation, subsequent requests for previously cached URLs result in the cached copy of the object being returned to the user; creating little or no extra network traffic, improving efficiency and reducing waiting time.

CPU Caching

The cache on your CPU has become a very important part of today's computing. The cache is a very high speed and very expensive piece of memory, which is used to speed up the memory retrieval process. Without the cache memory every time the CPU requested data it would send a request to the main memory which would then be sent back across the memory bus to the CPU. This is a slow process in computing terms. The idea of the cache is that this extremely fast memory would store and data that is frequently accessed and also if possible the data that is around it.

CPU's however use a 2 level cache system. The level 1 cache is the fastest and smallest memory, level 2 cache is larger and slightly slower but still smaller and faster than the main memory. The main problem with having too much cache memory is that the CPU will always check the cache memory before the main system memory.

Read cache is used to store copies of data and instructions that are retrieved from main memory or mass storage. If the central processing unit (CPU) needs to access the same data or instructions again, it can use the copy in read cache. This is much faster the going back to main memory or mass storage again. Write cache is a temporary store for data that needs to be written to main memory or mass storage. The CPU can move the data into cache very quickly, and then continue executing instructions. The data is subsequently moved to its permanent location by the cache controller, a process that takes more time because main memory and mass storage devices are much slower to access than cache memory.

Introduction to Caching

Caching is a well-known concept where programs continually access the same set of instructions, a massive performance benefit can be realized by storing those instructions in RAM. This prevents the program from having to access the disk thousands or even millions of times during execution by quickly retrieving them from RAM.
A cache is made up of a pool of entries. Each entry has a datum (a nugget of data) - a copy of the same datum in some backing store. Each entry also has a tag, which specifies the identity of the datum in the backing store of which the entry is a copy.
When the cache client (a CPU, web browser, operating system) needs to access a datum presumed to exist in the backing store, it first checks the cache. If an entry can be found with a tag matching that of the desired datum, the datum in the entry is used instead. This situation is known as a cache hit. The alternative situation, when the cache is consulted and found not to contain a datum with the desired tag, has become known as a cache miss. The previously uncached datum fetched from the backing store during miss handling is usually copied into the cache, ready for the next access.
When a system writes a datum to the cache, it must at some point write that datum to the backing store as well. The timing of this write is controlled by what is known as the write policy.
- In a write-through cache, every write to the cache causes a synchronous write to the backing store.
- In a write-back (or write-behind) cache, writes are not immediately mirrored to the store. Instead, the cache tracks which of its locations have been written over and marks these locations as dirty. The data in these locations is written back to the backing store when those data are evicted from the cache, an effect referred to as a lazy write.
- No-write allocation is a cache policy which caches only processor reads, thus avoiding the need for write-back or write-through when the old value of the datum was absent from the cache prior to the write.

Parallel port

A parallel port is a type of interface found on computers (personal and otherwise) for connecting various peripherals. It is also known as a printer port or Centronics port. The IEEE 1284 standard defines the bi-directional version of the port. Parallel ports can be used to connect a host of popular computer peripherals:
* Printers
* Scanners
* CD burners
* External hard drives
* Iomega Zip removable drives
* Network adapters
* Tape backup drives

Parallel ports were originally developed by IBM as a way to connect a printer to your PC. When a PC sends data to a printer or other device using a parallel port, it sends 8 bits of data (1 byte) at a time. These 8 bits are transmitted parallel to each other, as opposed to the same eight bits being transmitted serially (all in a single row) through a serial port. The standard parallel port is capable of sending 50 to 100 kilobytes of data per second.

Pins (parallel connection)

Pin number Name
1 _STR - Strobe
2-9 Data Bits D0-D7
10 ACK - Acknowledgement
11 Busy
12 Paper Out
13 Online Signal
14 Auto feed
15 Error
16 Reset
17 Offline Signal
18-25 Ground

9 Pin Serial Port Connector

Connector may be reversed depending on which side is viewed. All pins are numbered.

Pin No. Function
1 DCD (Data Carrier Detect)
2 RX (Receive Data)
3 TX (Transmit Data)
4 DTR (Data Terminal Ready)
5 GND (Signal Ground)
6 DSR (Data Set Ready)
7 RTS (Request To Send)
8 CTS (Clear To Send)
9 RI (Ring Indicator)
Voltage sent over the pins can be in one of two states, On or Off. On (binary value "1") means that the pin is transmitting a signal between -3 and -25 volts, while Off (binary value "0") means that it is transmitting a signal between +3 and +25 volts.
An important aspect of serial communications is the concept of flow control. This is the ability of one device to tell another device to stop sending data for a while. The commands Request to Send (RTS), Clear To Send (CTS), Data Terminal Ready (DTR) and Data Set Ready (DSR) are used to enable flow control.

Introduction to Serial Ports

Serial ports are a type of computer interface that complies with the RS-232 standard. They are 9-pin connectors that relay information, incoming or outgoing, one byte at a time. Each byte is broken up into a series of eight bits, hence the term serial port. Serial ports are one of the oldest types of interface standards.

In traditional computers, serial ports were configured as follows:
Serial Ports Interrupt Memory Address
COM 1 IRQ 4 0x3f8
COM 2 IRQ 3 0x2f8
COM 3 IRQ 4 0x3e8
COM 4 IRQ 3 0x2e8
Devices configured to use serial ports COM 1 and COM 3 could not be active at the same time, as they shared interrupt IRQ 4. The same was true of COM 2 and COM 4 port devices. The serial port is much more than just a connector. It converts the data from parallel to serial and changes the electrical representation of the data.
Serial flow is a stream of bits over a single wire (such as on the transmit or receive pin of the serial connector). For the serial port to create such a flow, it must convert data from parallel (inside the computer) to serial on the transmit pin (and conversely).
The advantage is that a serial port needs only one wire to transmit the 8 bits (while a parallel port needs 8). The disadvantage is that it takes 8 times longer to transmit the data than it would if there were 8 wires. Serial ports lower cable costs and make cables smaller. Serial ports, also called communication (COM) ports, are bi-directional. Bi-directional communication allows each device to receive data as well as transmit it.
Serial ports rely on a special controller chip, the Universal Asynchronous Receiver/Transmitter (UART), to function properly. The UART chip takes the parallel output of the computer's system bus and transforms it into serial form for transmission through the serial port. In order to function faster, most UART chips have a built-in buffer of anywhere from 16 to 64 kilobytes. This buffer allows the chip to cache data coming in from the system bus while it is processing data going out to the serial port.

Hamming Distance (HD)

Hamming distance (Hamming metric) In the theory of block codes intended for error detection or error correction, the Hamming distance d(u, v) between two words u and v, of the same length, is equal to the number of symbol places in which the words differ from one another. If u and v are of finite length n then their Hamming distance is finite since d(u, v) ← n.
It can be called a distance since it is non-negative, nil-reflexive, symmetric, and triangular:
0 ← d(u, v)
d(u, v) = 0 iff u = v
d(u, v) = d(v, u)
d(u, w) ← d(u, v) + d(v, w)
The Hamming distance is important in the theory of error-correcting codes and error-detecting codes: if, in a block code, the codewords are at a minimum Hamming distance d from one another, then
(a) if d is even, the code can detect d – 1 symbols in error and correct ½d – 1 symbols in error;
(b) if d is odd, the code can detect d – 1 symbols in error and correct ½(d – 1) symbols in error.

How to Calculate Hamming Distance ?
- Ensure the two strings are of equal length. The Hamming distance can only be calculated between two strings of equal length.
String 1: "1001 0010 1101"
String 2: "1010 0010 0010"
- Compare the first two bits in each string. If they are the same, record a "0" for that bit. If they are different, record a "1" for that bit. In this case, the first bit of both strings is "1," so record a "0" for the first bit.
- Compare each bit in succession and record either "1" or "0" as appropriate.
String 1: "1001 0010 1101"
String 2: "1010 0010 0010"
Record: "0011 0000 1111"
- Add all the ones and zeros in the record together to obtain the Hamming distance.
Hamming distance = 0+0+1+1+0+0+0+0+1+1+1+1 = 6

Error Detection Methods Cont...

- Cyclic Redundancy Check (CRC) :
This error detection method computes the remainder of a polynomial division of a generator polynomial into a message. The remainder, which is usually 16 or 32 bits, is then appended to the message. When another remainder is computed, a non-zero value indicates an error. Depending on the generator polynomial's size, the process can fail in several ways, however, it is very difficult to determine how effective a given CRC will be at detecting errors. The probability that a random code word is valid (not detectable as an error), is completely a function of the code rate: 1 - 2-(n - k). Where n is the number of bits of formed from k original bits of data ,(n - k) is the number of redundant bits, r.
Use of the CRC technique for error correction normally requires the ability to send retransmission requests back to the data source.

- Hamming distance based checks :
If we want to detect d bit errors in an n bit word we can map every n bit word into a bigger n+d+1 bit word so that the minimum Hamming distance between each valid mapping is d+1. This way, if one receives a n+d+1 word that doesn't match any word in the mapping (with a Hamming distance x <= d+1 from any word in the mapping) it can successfully detect it as an erroneous word. Even more, d or fewer errors will never transform a valid word into another, because the Hamming distance between each valid word is at least d+1, and such errors only lead to invalid words that are detected correctly. Given a stream of m*n bits, we can detect x <= d bit errors successfully using the above method on every n bit word. In fact, we can detect a maximum of m*d errors if every n word is transmitted with maximum d errors.

Error Detection and Correction

Error detection and correction are techniques to ensure that data is transmitted without errors, even across unreliable media or networks. Error detection is the ability to detect the presence of errors caused by noise or other impairments during transmission from the transmitter to the receiver. Error correction is the additional ability to reconstruct the original, error-free data.
Because of the extremely low bit-error rates in data transmissions, most error detection methods and algorithms are designed to address the detection or correction of a single bit error.

Data Detection Methods :
Errors introduced by communications faults, noise or other failures into valid data, especially compressed data were redundancy has been removed as much as possible, can be detected and/or corrected by introducing redundancy into the data stream.

- Parity Schemes
A parity bit is an error detection mechanism that can only detect an odd number of errors. The stream of data is broken up into blocks of bits, and the number of 1 bits is counted. Then, a "parity bit" is set (or cleared) if the number of one bits is odd (or even). (This scheme is called even parity; odd parity can also be used.) If the tested blocks overlap, then the parity bits can be used to isolate the error, and even correct it if the error affects a single bit.
There is a limitation to parity schemes. A parity bit is only guaranteed to detect an odd number of bit errors (one, three, five, and so on). If an even number of bits (two, four, six and so on) are flipped, the parity bit appears to be correct, even though the data is corrupt.

- Checksum
A checksum of a message is an arithmetic sum of message code words of a certain word length, for example byte values, and their carry value. The sum is negated by means of ones-complement, and stored or transferred as an extra code word extending the message. On the receiver side, a new checksum may be calculated from the extended message. If the new checksum is not 0, an error has been detected.

Overview of Interrupt Service Routine (ISR)

An interrupt service routine (ISR) is a software routine that hardware invokes in response to an interrupt. ISRs examine an interrupt and determine how to handle it. ISRs handle the interrupt, and then return a logical interrupt value. If no further handling is required because the device is disabled or data is buffered, the ISR notifies the kernel with a SYSINTR_NOP return value. An ISR must perform very fast to avoid slowing down the operation of the device and the operation of all lower priority ISRs. When an ISR notifies the kernel of a specific logical interrupt value, the kernel examines an internal table to map the logical interrupt value to an event handle.

Although an ISR might move data from a CPU register or a hardware port into a memory buffer, in general it relies on a dedicated interrupt thread, called the interrupt service thread (IST), to do most of the required processing.

The system supports two different types of ISRs:
- The driver can register an InterruptService routine to handle line-based or message-based interrupts. (This is the only type available prior to Windows Vista.) The system passes a driver-supplied context value.
- The driver can register an InterruptMessageService routine to handle message-based interrupts. The system passes both a driver-supplied context value and the message ID of the interrupt message.

Overview Of Interrupt Handling

An interrupt handler, also known as an interrupt service routine (ISR), is a callback subroutine in an operating system or device driver whose execution is triggered by the reception of an interrupt. Interrupt handlers have a multitude of functions, which vary based on the reason the interrupt was generated and the speed at which the Interrupt Handler completes its task.

An interrupt handler is a low-level counterpart of event handlers. These handlers are initiated by either hardware interrupts or interrupt instructions in software, and are used for servicing hardware devices and transitions between protected modes of operation such as system calls.
When an interrupt is processed, a specific sequence of events takes place. You should write the interrupt service request (ISR) and interrupt service thread (IST) for your device driver with the following sequence of events in mind :

- When an interrupt occurs, the microprocessor jumps to the kernel exception handler.
- The exception handler disables all interrupts of an equal and lower priority at the microprocessor, and then calls the appropriate ISR for the physical interrupt request (IRQ).
- The ISR returns a logical interrupt, in the form of an interrupt identifier, to the interrupt handler and typically masks the board-level device interrupt.
- The interrupt handler re-enables all interrupts at the microprocessor, with the exception of the current interrupt, which is left masked at the board, and then signals the appropriate IST event.
- The IST is scheduled, services the hardware, and then finishes processing the interrupt.
- The IST calls the InterruptDone function, which in turn calls the OEMInterruptDone function in the OAL.

OEMInterruptDone re-enables the current interrupt.

Edge Triggered Interrupts

An edge-triggered interrupt is a class of interrupts that are signalled by a level transition on the interrupt line, either a falling edge (1 to 0) or a rising edge (0 to 1). A device wishing to signal an interrupt drives a pulse onto the line and then releases the line to its quiescent state. If the pulse is too short to be detected by polled I/O then special hardware may be required to detect the edge. This type of interrupt is useful for a fleeting signal that doesn't last long enough for the processor to recognize it using polled I/O or for when the signal can last a long time, but the significant event is when that signal first goes active.
Edge-triggered interrupt modules can be acknowledged immediately, no matter how the interrupt source behaves. The type of the interrupt source does not matter. It can be a pulse, a firmware-clear signal, or some external signal that eventually is cleared somehow. Edge-triggered interrupts keep firmware’s code complexity down, reduce the number of conditions firmware needs to be aware of, and provide more flexibility when interrupts are acknowledged. This keeps development time down and quality up.
Multiple devices may share an edge-triggered interrupt line if they are designed to. The interrupt line must have a pull-down or pull-up resistor so that when not actively driven it settles to one particular state.Devices signal an interrupt by briefly driving the line to its non-default state, and let the line float (do not actively drive it) when not signaling an interrupt. This type of connection is also referred to as open collector. The line then carries all the pulses generated by all the devices.
Edge-triggered interrupts do not suffer the problems that level-triggered interrupts have with sharing. Service of a low-priority device can be postponed arbitrarily, and interrupts will continue to be received from the high-priority devices that are being serviced. If there is a device that the CPU does not know how to service, it may cause a spurious interrupt, or even periodic spurious interrupts, but it does not interfere with the interrupt signaling of the other devices.

Level Triggered Interrupts

Level-triggered Interrupt : It is the class of interrupts where the presence of an unserviced interrupt is indicated by a high level (1), or low level (0), of the interrupt request line. A device wishing to signal an interrupt drives the line to its active level, and then holds it at that level until serviced. It ceases asserting the line when the CPU commands it to or otherwise handles the condition that caused it to signal the interrupt.

Level-triggered interrupts force firmware engineers to take into account what is generating the interrupt source. If the interrupt source is just a pulse from a state machine, then the device drivers do not need to do any additional work. If the interrupt source is asserted when a counter equals zero, the device driver must first write a non-zero value to the counter before it can acknowledge the interrupt. If the interrupt source is a signal from a different block with its own device driver or an external device under its own firmware control the device driver has no control over when the interrupt source is cleared. Its only choice is to disable that interrupt so that it can exit the interrupt handler.

There are also serious problems with sharing level-triggered interrupts. As long as any device on the line has an outstanding request for service the line remains asserted, so it is not possible to detect a change in the status of any other device. Deferring servicing a low-priority device is not an option, because this would prevent detection of service requests from higher-priority devices. If there is a device on the line that the CPU does not know how to service, then any interrupt from that device permanently blocks all interrupts from the other devices.

Overview of Interrupts

An interrupt is an unexpected hardware initiated subroutine call or jump that temporarily suspends the running of the current program.
Interrupts occur when a peripheral device asserts an interrupt input pin of the micro-processor. Provided the interrupt is permitted, it will be acknowledged by the processor at the end of the current memory cycle. The processor then services the interrupt by branching to a special service routine written to handle that particular interrupt. Upon servicing the device, the processor is then instructed to continue with what is was doing previously by use of the "return from interrupt" instruction.
Interrupts in general can be divided into two kinds- maskable and non-maskable.
A maskable interrupt is an interrupt whose trigger event is not always important, so the programmer can decide that the event should not cause the program to jump. A non-maskable interrupt (like the reset button) is so important that it should never be ignored. The processor will always jump to this interrupt when it happens.

The function that is called or the particular assembly code that is executed when the interrupt happens is called the Interrupt Service Routine (ISR). Other terms of note are: An interrupt flag (IFG) this is the bit that is set that triggers the interrupt, leaving the interrupt resets this flag to the normal state. An interrupt enable (IE) is the control bit that tells the processor that a particular maskable interrupt should or should not be ignored.

Advantages of Interrupts :
Interrupts are used to ensure adequate service response times by the processing. Sometimes, with software polling routines, service times by the processor cannot be guaranteed, and data may be lost. The use of interrupts guarantees that the processor will service the request within a specified time period, reducing the likelihood of lost data.

Software Interrupt :
The Software Interrupt (SWI) is an instruction that can be placed anywhere within a program. It forces the microprocessor to act as if an interrupt has occurs. The vector for the 6800 is located at addresses $FFFA and $FFFB. The SWI is often used by Monitor Programs to set breakpoints, which stops the program at a particular location so that the contents of the memory and registers can be examined.

Interrupt Latency :
The time interval from when the interrupt is first asserted to the time the CPU recognizes it. This will depend much upon whether interrupts are disabled, prioritized and what the processor is currently executing.

Interrupt Response Time :
The time interval between the CPU recognizing the interrupt to the time when the first instruction of the interrupt service routine is executed. This is determined by the processor architecture and clock speed.

Concept of Buffers

In computing, a buffer is a region of memory used to temporarily hold data while it is being moved from one place to another. Typically, the data is stored in a buffer as it is retrieved from an input device (such as a keyboard) or just before it is sent to an output device (such as a printer). However, a buffer may be used when moving data between processes within a computer.
Buffering is used to improve several other areas of computer performance as well. Most hard disks use a buffer to enable more efficient access to the data on the disk. Video cards send images to a buffer before they are displayed on the screen (known as a screen buffer). Computer programs use buffers to store data while they are running. If it were not for buffers, computers would run a lot less efficiently and we would be waiting around a lot more.
Buffers are another way that receivers can ensure that they do not miss any data sent to them. Buffers can also be useful on the transmit side, where they can enable applications to work more efficiently by storing data to be sent as the link is available.
The buffers may be in hardware, software, or both. When the hardware buffers aren't large enough, a PC may also use software buffers, which are programmable in size and may be as large as system memory permits. The port's software driver transfers data between the software and hardware buffers.
In micro controllers, the buffers tend to be much smaller, and some chips have no hardware buffers at all. The smaller the buffers, the more important it is to use other techniques to ensure that no data is missed.

Handshaking Mechanism

Handshaking is an automated process of negotiation that dynamically sets parameters of a communications channel established between two entities before normal communication over the channel begins. It follows the physical establishment of the channel and precedes normal information transfer.
It is usually a process that takes place when a computer is about to communicate with a foreign device to establish rules for communication. When a computer communicates with another device like a modem, printer, or network server, it needs to handshake with it to establish a connection.
With handshaking signals, a transmitter can indicate when it has data to send, and a receiver can indicate when it is ready to receive data. The exact protocols that signals follow may vary, though many RS-232 and RS-485 links follow standard or conventional protocols.

In hardware handshaking, the receiver brings a line high when it is ready to receive data, and the transmitter waits for this signal before sending data. The receiver may bring the line low any time and the transmitter must detect this, stop sending, and wait for the line to return high before finishing the transmission.
Other links accomplish the same thing with software handshaking, by having the receiver send one code to indicate that it is ready to receive, and another to signal the transmitter to stop sending.

Data Formats

The data bits in a serial transmission may represent anything, including commands, sensor readings, status information, error codes, or text messages. The information may be encoded as binary or text data.

- Binary Data : The receiver interprets a received byte as a binary number with a value from 0 to 255. The bits are numbered 0 through 7, with each bit representing the bit's value (0 or 1) multiplied by a power of 2. A byte of 1111 1111 translates to 255 or FFh and 0001 0001 translates to 17 or 11h. In asynchronous mode, bit 0, the least-significant bit arrives first. Binary data works fine for many links but some links need to send messages or files containing text.

- Text Data : To send text, the program uses a code that assigns a numeric value to each text character. There are several coding conventions :
* ASCII : It consists of 128 codes and requires only seven data bits. An eighth bit, if used, may be 0 or a parity bit.
* ANSI : It consists of 256 codes with the higher codes representing special and accented characters.
Other formats use 16 bits per character, which allows 65,536 different characters.

One can also use text to transfer binary data by expressing the data in ASCII Hex format. Each byte is represented by a pair of ASCII codes that represent the byte's two hexadecimal characters. This format can represent any value using only the ASCII codes 30h through 39h (from 0 through 9) and 41h to 46h (for A through F).