CS33 : Introduction to Computer OrganizationJochen Haber3400 Boelter [email protected]:Farnoosh Javadi ([email protected])Xingyu Ma ([email protected])Mo Xu ([email protected])Teng Xu ([email protected])Lecture: MW 4PM-6PMOffice Hours:M: 6PM-7PMW: 6PM-7PMBH4532BDiscussion:As Enrolled- 2 hours per weekSec 1A BH5419 F: 2PM-4PM Teng XuSec 1B BH5419 F: 4PM-6PM Xingyu MaSec 1C BH5273 F: 4PM-6PM Mo XuSec 1D BH9436 F: 4PM-6PM Farnoosh JavadiText:Randal E. Bryant and David R. O’Hallaron. “Computer Systems: A Programmer’s Perspective” 2nd Edition, Prentice Hall 2010.Mid Term Lab 1Pretty easy except for detecting overflow in multiply assuming signed numbers.Adder truth tablecarry_newx[i] y[i] carry_old carry_new0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 1 carry_new = ( ( x[i] & y[i] ) & !carry_old ) | ( ( x[i] | y[i] ) & carry_old ) ;z[i]x[i] y[i] carry_old z[i]0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1 z[i] = ( ( x[i] ^ y[i] ) & !carry_old ) | ( !( x[i] ^ y[i] ) & carry_old )overflowx[w-1] y[w-1] z[w-1] o0 0 0 00 0 1 10 1 0 00 1 1 01 0 0 01 0 1 01 1 0 11 1 1 0 ( x[w-1] & y[w-1] & !z[w-1] ) | ( !( x[w-1] | y[w-1] ) & z[w-1] ) Multiplication: shift and add.4 bit signed multiplier: both numbers plus: 3+3 bits max. for negative outcome, 7 bits max.Problem is how to do this using only Boolean functions. Using arithmetic functions, it is easy.a * b = c then if c / a != b: overflow.One solution. Convert to unsigned problem and correct sign later. Then we can use a carry outinto the sign or left of the sign to detect overflow.Example 5 * 3 5 * 4 3 2 1 0 3 2 1 0 0101 10100 + 01010 += 01111 Carry out into the sign bit. = 10100 Carry out past the sign bit.Another way: counting from the right, starting with one. Get the most significant bit number ofboth operands, add them up. That is how many bits it will take. For Boolean, this means thatevery bit, the sign and beyond, must be zero.2 2Basically this rule implements for a * b that log a + log b, rounded up equals the number of bits2required for a * b. When either a or b are negative, we take log of the absolute value and then thenumber of bits is one greater to account for the sign.- 56 -Lab 2.1Write a memory dump: void dumper( unsigned char *x, int n, int sgn )Which prints out memory like this, in hexadecimal.When sgn = +1Address +x00 +x04 +x08 +x0c7fffb80aaab0 00000000 00000000 004003e3 012345677fffb80aaac0 b80aabf8 00007fff b80aaabc 00007fff7fffb80aaad0 3a40fb88 00000030 b80aaabc 00007fff7fffb80aaae0 b80aab00 00007fff 00400537 000000007fffb80aaaf0 b80aaafc 00007fff 00000000 012345677fffb80aab00 00000000 00000000 3a41ecdd 000000307fffb80aab10 00000000 00000000 b80aabe8 00007fff7fffb80aab20 00000000 00000001 00400514 00000000When sgn = -17fffb80aaaf0 b80aaafc 00007fff 00000000 012345677fffb80aaae0 b80aab00 00007fff 00400537 000000007fffb80aaad0 3a40fb88 00000010 b80aaabc 00007fff7fffb80aaac0 b80aaafc 00007fff b80aaabc 00007fff7fffb80aaab0 00000000 00000000 004003e3 012345677fffb80aaaa0 00000000 00000000 b80aaaf0 00007fff7fffb80aaa90 b80aaae0 00007fff 004005e7 000000007fffb80aaa80 00000000 00000007 b80aaa70 00007fffx is a pointer to somewhere in the stack (the address of any automatic variable), n is the numberof 16 byte addresses to print and sgn is +/-1 to guide which direction (ascending or descendingaddresses) in memory to print. But x could point to anywhere.Whatever x is, please round it down to a multiple of 16 so that every starting address ends in 0.The column header is not required.The first column is the memory address of the first four byte dump. The next four columns arethe data at the addresses +0, +4, +8 and +12. In the printout, remember to reverse the order ofeach four byte chunk to make it read in right endian. Things which are 8 byte things will staylittle endian but let’s not worry about that. This lab will give you some experience using pointers to look at things and overall problems indealing with hexadecimal data. All of this can be done in .c or .cpp.Assignment due midnight, Sunday Oct 20. Estimated time to complete: 2 hours. You will besacked by 2 points if you do not complete this part on time.The lab will re-open on Monday, Oct 21 with Lab 2.2 where you will use the dumper and someother assignments to do some neat things. We are going to redecorate the stack.- 57 -A template for the assignment is: - 58 -Factorial computer.Structures: a way of aggregating data into one place. Outcome of declaration is a new data typeand creates a map of a contiguous area.History: first widely used in COBOL (1959) (Common Business OrientedLanguage) supposedly self documenting. “Amazing” Grace MurrayHopper.Fortran (1953) scientific language John Backus.PL/I (1965) combines features of COBOL and Fortran, adds elements ofLISP, very strong with structures, pointers first introduced, dynamicmemory allocation. IBMstruct <new data type name> { <type> <var1> ; <type> <var2> ; . . } <optional name> ;struct movies { char title[50]; int year; } ;After this declaration, movies is a data type. If the <optional name> is present, it creates aninstance of the data type. You can now declare:movies yours, mine ;Or evenmovies favorites[50] ;Memory layout for yours, mine is 50 character title followed by year. For favorites:title[0] title[1] title[2] ... title[48] title[49] year[0] For favorites:title[0][0] title[0][1] title[0][2] ... title[0][48] title[0][49] year[0] title[1][0] title[1][1] title[1][2] ... title[1][48] title[1][49] year[1] - 59 -An element can be an array:struct newtype1 { int a ; float b[10] ; int c ; } x ;Or another structurestruct newtype2 { int a ; struct inner { float b ; int c[10] ; } y ; int *d ; } x ;Imagine the layout.The scope of the variable name lies inside of the structure. That is the name is not known outsideof the structure unless you refer to the variable with its qualification:x.a, x.y.c[5]You cannot refer to c[5] without the qualification unless char c[] exists outside of the structure.This means that you can have c both