Homework 8 Solutions

22C:122, Fall 1998

1. To multiply R5 by 3, 5, 10 and 100, consider using the following instruction sequences on the Hawk:

   	ADDSL R5,R5,1	; multiply by 3
   
   	ADDSL R5,R5,2	; multiply by 5
   
   	ADDSL R5,R5,2
   	ADDSL R5,0,1	; multiply by 10 (10 = 2 x 5)
   
   	ADDSL R5,R5,2
   	ADDSL R5,R5,2
   	ADDSL R5,0,2	; multiply by 100 (100 = 5 x 5 x 4)
   

2. An analysis of instruction frequency based on source code would determine the frequency of each abstract operator in the source programming language. Thus, we would find the frequency of each source-language addressing mode, the frequency of each source-language constant type, the frequency of each source-language arithmetic operation, and the frequency of each source-language abstract control structure.

   While there is not a one-to-one mapping between these and the instructions of any particular hardware, there is usually a straightforward reduction of source-language constructs to hardware constructs. For example, each while loop (a source language operator) requires one conditional forward branch and one unconditional backward branch. As a result, source-code analysis can provide considerable information to the designer of an instruction set prior to the first draft of that instruction set.

3. While there are 8 nibbles of 4-bits each in a 32 bit word, carry propagation between BCD add operations will be easier if we only use 7 nibbles per word, reserving the 8th for carry detection. This leads to the following add routine:

   	add(s1,s2,dst)
   	int * s1;
   	int * s2;  /* all parameters are arrays of 2 elements */
   	int * dst; /* element 0 is the least significant 7 digits */
   	{
   		int t1, t2, t5, res, carry;
   		t1 = s1[0] + 0x06666666;
   		t2 = t1 + s2[0];
   		t5 = ~(t2 ^ (t1 ^ s2[0])) & 0x11111110;
   		res = t2 - (t5 >> 2) | (t5 >> 3);
   		carry = (res & 0xF0000000);
   		dst[0] = (res & 0x0FFFFFFF);
   		t1 = s1[1] + 0x06666666 + carry;
   		t2 = t1 + s2[1];
   		t5 = ~(t2 ^ (t1 ^ s2[1])) & 0x11111110;
   		dst[1] = t2 - (t5 >> 2) | (t5 >> 3);
   	}