Puzzle

Precedence and other issues

Hi Professor Ford,

I am your student in course comp238, and it seems to be a stupid question. but still I want to make clear about what I thought about the "precedence of logical operators".

In class, you mentioned that operator "and" and operator "or" have same precedence. And at same time you said that if no parentheses are added there will be ambiguity. In this sense, I guess there is no sense to define any two operator with same precedence which also will give ambiguity for operating sequence. In one word, "and" and "or" operators are just not SAME precedence at all.

I checked with text book, on page no. 10, it is said "Another general rule of precednece is that the conjunction operator takes precedence over the disjunction operator, so that ....". Also on table 7 at same page "Precedence of Logical Operators" clearly listed that "not" operator has 1 precedence, "and" has 2 precendence, "or" has 3 precendence, "conditional" operator has 4 precendence, "biconditional" has 5 precendence.

One more evidence is that when I program with C++, the logical operator "&&" which is "and" is always taking first precedence over "||" , "or " operator.

Hope it does bother you.

Best regards,

QingZhe Huang

One's Complement and Two's Complement

The section U of course COMP228 is like hell! The instructor is a chinese woman who is continually nervous, shy, avoiding to face questions proposed by students, lack of confidence of what she was trying to express. In one word, she is unqualified.

1's complement and 2's complement is rather a typical illustration of evolution of computer architechure which demonstrated the practicalism of human toword computer science. Computer from very beginning is just a tool for human and people are just want to use it with convenience. So, in this sense, almost all aspect of computer design is from the purpose of convenience and efficience. There is no nonsense empty-talk involved which is a common phenomenon in many humanic "science", if we can call them sciences. 1's complement and 2's complement is only the choice of no-choice. I often say that in computer science, it always seems that Nature-Creator leaves only one choice which means we have no other choice. Only in this sense, we can say that "no choice is our best choice". So is the situation of 1's and 2's complement.

I originally heard this in York university in Toronto. I still remember the professor vividly demonstrated step by step that it is our only solution to problem of representing of "signed numbers". However, in Concordia, this woman instructor made nobody understand what it really means.

Just imagine that one byte can have 256 unique combinations of bits which can represent number of 0-255. But for "signed numbers", we need to reserve one bit for "signs". And it is for our convenience we use MSB(most significant bit) to represent signs. It is only by convention that we use the left-most(logically) bit to represent minus number when it is 1 and 0 for positive numbers. Therefore within one byte we are left with 7bits to represent numbers apart from one sign number.

(Signed Number)

Sign number (MSB)	combination of other 7 bits	Range of number
1	128	0000,0000 ---0111,1111 (0 to 127)
0	128	1000,0000 ---1111,1111 (0 to -127)

This is pretty straight forward to represent signed number. However, it is quite useless. As we have to implement two algorithm for minus and plus operation.

So, in order to simplify the two operation into one operation, like 5-3 = 5+(-3), which always use plus operation. We introduce the 1's complement, that is flip all number to make its minus couterpart.

(1's complement)

Sign number (MSB)	combination of other 7 bits	Range of number
1	128	0000,0000 ---0111,1111 (0 to 127)
0	128	1111,1111 --- 1000,0000 (0 to -127)

You can see that 1's complement is just change our usual concept for minus number---"the absolute value bigger, the value is smaller." Actually it is opposite so that minus operation becomes plus operation.

But it still has the problem of "TWO" zeros: 0000,0000 for +0 and 1111,1111 for -0. Then we have a solution with 2's complement that after we flip, we add 1 to "move" all minus number by one to delete the annoying -0.

Sign number (MSB)	combination of other 7 bits	Range of number
1	128	0000,0000 ---0111,1111 (0 to 127)
0	128	1111,1111 --- 1000,0000 (-1 to -128)

We can notice that the difference is that 1111,1111 is becoming -1 instead of -0. So, all is perfect.

Reply from Dr. Ford by E-mail

You are right!

The "and" operator has precedence over "or" and the 
"conditional" operator has precedence over "biconditional".

I will clear this up in class tomorrow.

-- FORD

About Context Switch and DMA

It starts here...

Dear Sir, Regarding I/O, I have some doubts: 1. At what point of time, does the context switching happen? Before CPU sent INTA or just before transfer control to interrupt-service-routine? 　

Context switching is done before the "main body" of the interrupt service routine. It is done after INTA. Take note that INTA (interrupt acknowledge) is sent by the CPU to determine which device needs attention, and the address of the interrupt service routine for that device. Before executing the interrupt service routine, context switching must be implemented so that the CPU could go back to the interrupted work properly after doing the interrupt service routine. 　

　　 2. Suppose DMA starts transfer data, can CPU use data bus and address bus during the whole process of DMA copying data? Or in other words, is it true that DMA is using data bus and address bus continually during transfering data? 　

The CPU is always the master of the hardware system whether a DMA is being executed or not. To access the memory, for example, CPU takes control. Only when the CPU does not use the memory that the DMA controller takes over -- you call this stealing memory cycles from the CPU. Concerning the buses, concurrency is implemented -- if there are 3 buses, for example, 3 events could happen at the same time. There are instances that the CPU wouldn't need one or two or all the 3 of these buses, the DMA controller "steals" them. In other words, CPU activity and DMA data transfer are happening at the same time, but the buses are not assigned to DMA controller to the duration of the transfer. In fact, DMA priority is low that it is just "stealing" resources to do its task. And it continues...

At 05:39 PM 10/04/2003 +0000, you wrote: 　

Hi Sir, Thank you for your prompt reply. I still have a couple of questions: 1. >Context switching is done before the "main body" of the interrupt 　

　　 service routine. It is done after INTA. 　

When I discussed context switching here awhile ago, I was discussing the context switching related to the registers that will be destroyed or modified by the "main body" of the interrupt service routine. For example, the main body of the ISR modifies reg1 and reg2, then we need to push reg1 and reg2 before going into the body of the ISR. After the body of the ISR, reg2 and reg1 are popped out. That is what I meant there by context switching; this context switching is actually the first instructions in the ISR. The other context switching is preserving the returned address and the flags before the ISR is called. This is done by pushing the code pointers and condition flag register before the ISR, then ISR, then popping these code pointer and flag registers (in 8086, it means pushing CS, IP and Flag Registers). This is done automatically when there is a call to an interrupt (in the same way that when there is a call to a procedure, it is automatic that the returned address is pushed onto the stack before a procedure is executed). The interrupt vector is the actual address of the interrupt service routine. In 8086/Pentium, this address must be the value of CS and IP. So before destroying the content of IP and CS, the IP and CS (and the flag registers) are pushed onto the stack (This is the context switching that you are interested about), after that, the CS and IP modified by the interrupt vector (the segment address --> CS, and the offset --> IP). So here is the summary: 1. an INTR is made 2. an INTA is returned 3. an interrupting device is identified 3. a search in the IVT is made for that device 4. a vector interrupt (the address of the interrupt service subroutine) is known 5. the CS, IP, and flag registers are saved/pushed (one context switching) 6. the address in the vector interrupt is assigned to CS and IP 7. the CPU goes to that address (ISR) 8. the ISR first statements are generally pushing registers that would be modified by the main body of the ISR (another context switching) 9. performing ISR main body 10. popping out the registers pushed in step 8 11. the ISR is done 12. the last statement in ISR is iret (interrupt return) which means popping out CS, IP and flag register. 　

　　 You said that context switching is done after INTA. But after INTA, the interrupt vector will be returned from Port, right? and CPU need some calculation to get the "real" interrupt vector table address, (I am not quite sure about the interrupt vector meaning, I guess it is only an offset in IVT like 21h, 35h??). Then at this point, CPU need register to hold the interrupt vector for calculation of address, then the data in register would be destroyed. So, I guess the context switch should be done BEFORE INTA. This is my doubt. And if you can explain exactly how CPU get interrupt table address, I will be very grateful. 2. Thank you for your explanation for DMA. I now understand that DMA has low priority to use data bus and address bus. So, is it correct that DMA is actually "ask" CPU to let him to use bus by "bus request" and get confirmation by "bus grant"? I read it somewhere, but not sure. 　

Yes, in general literature of computer organization, this is correct. 　

　　 And more importantly, as I read the slides and noticed that DMA actually "steals" MEMORY CYCLE, not CPU clock cycle. So, I think there will not by sychronization between CPU clock and memory cycle, right? 　

Yes, the CPU has no idea when the DMA would complete its work. DMA controller will inform the CPU when the data transfer is done. 　

　　 Then at some point, DMA is actually using bus, and it is the turn for CPU to require DMA to give control of bus back to CPU. This is rather complicated situation! Can this happen if memory cycle are not same as CPU clock cycle? I am rather confused about memory cycle. 　

A memory cycle is the time it takes to do a memory read or memory write. It is about 10 times the clock cycle. One clock cycle is the time it takes to transfer data from one register to another register. Here is what usually happens: 1. CPU is doing something 2. DMAR is made to the CPU 3. Device receives DMAA 4. DMA I/O waits for free bus. This means step 5 won't be done unless step 4 yield a free bus 5. DMA I/O takes over the bus to access memory (send address, data and write to memory) 6. DMA frees the bus 7. steps4, 5 and 6 are repeated until all the data transfer is completed

MoreOver...

DMA Cycle stealing means that the DMA controller releases the bus after each byte is transferred. Transferring 512 bytes would therefore require that the DMA controller request the CPU bus (by asserting HRQ) 512 times. Each byte transferred causes DREQn* to be asserted so DREQn* will also be asserted 512 times. Since data is being transferred from the peripheral to memory, IOR* will be asserted. Why should we use literals?

Hi Professor,

I asked you some question about literals and constants in comp229, and you asked me to do some reading. Now I want to confirm the following:

1. Literals are similar to constants except that they are automatically defined by assembler.

2. Unlike constants which is defined by programmer, they are typically defined in form of * =X'05' by assembler at end of program (after end instruction) if no "LTORG" directive is used.

3. They are not using immediate addressing mode. They are simply a constant, referred by their addresses.

If above are correct, my question is what purpose do we use literals?

1. The purpose of using constants is that we can define them in one place and change them all once a time. But for literals, we use them like constants but value is not able to be defined somewhere like constants because we use whatever their value are. If we want to change the value, we have to track each of them and modify one by one. So, it has no advantages of constants.

2. The purpose of using immediate value is to write the value as part of instruction so that processor doesnot need to visit memory to fetch operand. For literals, they are similar to constants, that is, the instruction simply use their address for operand. During execution time, value of that address needs to be fetched. So literals have no advantages like immediate value.

Since it has no advantages of either constants and immeidate values, then why do we use literals?

Thank you very much for your time in advance,

Best regards,

Nick Huang/Qingzhe Huang

Because it is a literal...

Hi Mr. Nick Huang,

Literals are useful in long programs as they can be defined anywhere in the program and will automatically be grouped together at the LTAB by the assembler. For example, normally we define

EOF DB C'EOF'

and use the memory address EOF in instructions. In the case of literals, we can define them as * =C'EOF' anywhere and any number of times within the program and the assembler simply stores the data C'EOF' in appropriate place in memory and use the memory address in all the instructions using the literal (as =C'EOF'). Thus, the programmer does not have to worry (1) whether the constant has already been defined, (2) at what memory location the data is stored at etc. while coding. As you can imagine this avoids going back and forth in large programs thereby making the programmers life easy.

If you have any further question, we may discuss in the class tomorrow. R. Jayakumar

FAQ:

1. Since assembler can automatically detect whether format 4 of instruction should be used or not, why should

we design to allow programmer to explicitly show in assembly code that "format 4" is used by adding "+" at

beginning of code?

It gives programmer more flexibility to control.

2. Since assembly directive "Base ASymbol" informs assembler how to calculate base relative, then why should

we still need write "LDB ASymbol" to actually load "ASymbol" address into "base" register? Why don't we allow

assembler generates code automatically?

It simply gives programmer more flexibility and also more responsibility to take care.

Assignment 1

1. Problem 8, page 112

In our SIC/XE model, the “SYMTAB” does not store the references of an operand. So, we need to add one column in “SYMTAB” as “References” which is somewhat a linked list.

Symbol	Value	Flag	References
Alpha	1003, 1009	Error	1000, 1003

In the “pass 2” when operands are checked, also adds the referred location counter number to “SYMTAB” at column “References”. Then when error message is output, we can also output the referred lines or location counter number of the duplicated-declared operands.

★The following part is suggested by Mr. Fang.

★One more point here, the "value" column should also be a linked list to store all "duplicated defined" symbols. So, even in "pass 1", when duplicated defined symbols are encountered, not only the error flag should be written into "SYMTAB" for the symbol, but also the address should be stored in value column so that these "labels" are also able to be printed out. So, the value field should also be a linked list instead of a single address.★

2. Problem 12, page 116

The problem for assembler is that for the same mnemonic code like “ADD”, different object code needs to be generated according to its operand. In other words, mnemonic code is not one-to-one with machine code. As for a machine that the length of instruction is not fixed, the only possible way to differentiate instructions is by its unique OPCODE. Since the operands are different, the OPCODE must be different either. Otherwise processor is unable to decode instruction correctly. Therefore assembler need to do some extra job to check the type of operand to decide which OPCODE should be used accordingly. Taking “MASM” as an example, the same mnemonic “ADD” will have different OPCODE according to different operands.

To solve this problem, during “pass 2” the OPCODE will not be generated until the type of operand has been determined by checking the operand in “SYMTAB”. And accordingly in “SYMTAB” we need to add one more column for symbols----“Type”. So, when assembler parsed the definition of a symbol, it needs to store its “type” in “SYMTAB” for future reference.

3. Problem 8, page 118

a. LDA #3

This is using immediate addressing mode, that is the target address is “0003”. And its object code should be “012003”.

b. LDA #THREE

This is also using immediate addressing mode, however, the operand is a symbol “THREE”. The target address should be the value of this symbol in “SYMTAB”. Usually the value of a symbol in “SYMTAB” is its address. But the assembly directive

“THREE EQU 3” will let assembler to store value “3” into “SYMTAB” instead of its address which is the value in “location counter”. So, the target address becomes 003. And if we assume PC relative mode is used, the object code should be “012003”. It is same as a.

c. LDA THREE

This code is meaningless! As in “SYMTAB” the value of symbol “THREE” is 3 which is not the address of this symbol by “EQU” directive. And immediate addressing mode is not indicated. During execution time, processor will try to fetch value at memory address of “003” which is incorrect!

4. Problem 24, page 121

The reason of RDREC-COPY is an invalid expression is because “COPY” is not a symbol stored in “SYMTAB”. So, the obvious solution is to add file name---“COPY” into “SYMTAB” which has the same value or address as “FIRST” or the first label in program.

★The above is totally wrong!

The reason of RDREC-COPY is an invalid expression is because “COPY” and "RDREC" are not available at assembly time. They are only known at loading time by the loader, so, for assembler it should provide enough information for loader to modify the address at loading time when the exact address of “COPY” and "RDREC" are known. This can be done by adding modification records in object file. Suppose this expression appears in "COPY" block, then "RDREC" would be like a "EXTREF" which need to be modified in loading time.

5. Problem 5, page 122

My solution is to write whatever the immediate value or defined operand first into the operand part of object code and later add the undefined symbol value when its definition is met.

Symbol	Value
…	…
ENDFIL	*
…	…

So, the instruction “JEQ ENDFIL+3” would be interpreted first as 30 0003, please note that the value “+3” is write at the operand part and undefined symbol “ENDFIL” is entered SYMTAB. When definition of “ENDFIL” is later encountered, its address, say 2024, will be “ADD” to the operand part. That is 2024 + 0003 = 2027. So, forward reference is not replacing the operand part, instead “CALCULATED” at operand part.

Further to the question, say we want to handle minus sign of forward reference like:

“JEQ 3-ENDFIL” where operand may have different sign here. My solution is to add one sign column in reference linked list in SYMTAB as following:

Symbol	Value
…	…
ENDFIL	*
…	…

So, when updating forward reference according reference link list, assembler need to check the sign column to decide whether the value should be “POSITIVE” OR “NEGATIVE”. Say the ENDFIL address is 2024, now the operand should be 0003 + (-2024) = -2021.

Hosted by www.Geocities.ws