Memory and Data StructuresStorage of bytesSystem StackSummary of data structuresMemory and Data StructuresArraysStacksQueues2CMPE12c Cyrus BazeghiMemory• This is the “RAM” in a system• We have seen labels and addresses point to pieces of memory storing:•words•bytes•strings•floats• Memory is just a collection of bits• We could use it to represent integers• Or as an arbitrary set of bits3CMPE12c Cyrus BazeghiMemoryInstead, treat memory as a giant array of bytes•Compiler or programmer decides what use to make of it.•The element numbering starts at 0•The element number is an address•In C to allocate some memory:char m[size_of_array];4CMPE12c Cyrus BazeghiStorage of bytes• MIPS architecture is “byte addressable” meaning that all addresses are “byte” addresses.• This means the smallest unit of memory we can allocate is a byte.• Use ‘lb’ (load byte) to access this unit.5CMPE12c Cyrus BazeghiExample.datamychar: .bytenewline: .byte ‘\n’….text…lb $t0, newlineli $v0, 12 # getcsyscallsb $v0, mycharbeq $t0,$v0, found_newline…found_newline: …Storage of bytes6CMPE12c Cyrus BazeghiStorage of bytesThe data is placed in memory like this at start up (assuming .data section starts at address 4). The mychar variable will change to the value of the character entered by the user once stored.370091500A 4812Memorynewline variablemychar variableaddresses7CMPE12c Cyrus BazeghiStorage of Integers• Use 4 bytes beginning at an address that is multiple of 4.• So if stored at address 20, uses bytes 20, 21, 22, and 23.• Use ‘lw’ (load word) instead of ‘lb’ (load byte).8CMPE12c Cyrus Bazeghi.datan: .word 1n2: .word -1newline: .byte ‘\n’str1: .asciiz “Enter a number ”.textmain: la $a0, str1li $v0, 4 # print stringsyscallli $v0, 5 # get integersyscalllw $t1, nadd $t2, $v0, $t1sw $t2, n2Storage of Integers9CMPE12c Cyrus Bazeghi40 00 00 00 01 4344 FF FF FF FF 4748 0A 45 6E 74 4B4C 65 72 20 61 4F50 20 6E 75 6D 5354 62 65 72 20 5758 00 5B5C 5FMemory1 in 2SC-1 in 2SCNew line“Enter a number “addressesStorage of Integers10CMPE12c Cyrus BazeghiMemoryAnd the program would become this eventually:.textmain: li $a0, 49 # expects an address for a stringli $v0, 4 # code for put stringsyscalllw $t1, (40) # expects an addressadd $t2, $t1, $t1 # expects “values”sw $t2, (44) # expects an address• Real machine code has addresses for variables, not labels.• Later, we will show how to store instructions and get rid of branch labels. Then the .text segment will look similar to the .data segment.11CMPE12c Cyrus BazeghiEndian IssuesConsider this code:.datan: .word 0x61626364 #ASCII for ‘a’, ‘b’, ’c’, ’d’.textmain:lb $a0, nli $v0, 11 # putc codesyscallDo you think an ‘a’ or a ‘d’ is printed?12CMPE12c Cyrus BazeghiEndian IssuesAnswer: ‘a’ since MIPS is a big Big Endian architecture.40 61 62 63 64 43addressesmemorylw $s0, n$s061626364But if we did:We would get this:031As we would expect.13CMPE12c Cyrus BazeghiBig Endian:smallest address is most significant (biggest)Little Endian:smallest address is least significant (littlest)So answer would be ‘d’If we did a lw $s1, n$s1 <- 0x61626364Endian Issues40 64 63 62 61 43addressesmemorySame as with bigendian14CMPE12c Cyrus BazeghiEndian IssuesLittle Endian – address LSB(VAX, Alpha, x86, PDP-11)Word Address Bytes MSB->LSB03 2 1 04 7 6 5 4Word Address Bytes MSB->LSB00 1 2 34 4 5 6 7Bi-Endian:Selectable data formatBig Endian – address MSB(IBM 360->390, Motorola 680x0, Sparc, MIPS)15CMPE12c Cyrus BazeghiProgrammable or bi-endian: on data only (why not instructions?)i860 (Little-endian instructions)PowerPC (Big-endian instructions)In general:When accessing values smaller than a word must alsoconsider alignment, sign extension, and effect on high bytes of register.Endian Issues16CMPE12c Cyrus BazeghiArraysArray implementation is very important• Most assembly languages have no concept of arrays• From an array, any other data structure we mightwant can be built17CMPE12c Cyrus BazeghiProperties of arrays:– Each element is the same size–Char = 1 byte– Integer = 1 word– Elements are stored contiguously– First element at the smallest memory addressIn assembly language we must– Allocate correct amount of space for an array– Map array addresses to memory addressesArrays18CMPE12c Cyrus BazeghiArraysMAL declarations of arrays within memory•To allocate a portion of memory (more than a singlevariable’s worth)variablename: type initvalue:numelements•type is as before - .byte, .word, or .float•numelements is just that, numbering starts at 0 (as in C)•initvalue is a starting value given to each element of the array19CMPE12c Cyrus BazeghiArraysNew directive:name: .space numberofbytes•.space allocates space (in bytes) within memory without giving an initial value.•The type of the data within this space cannot be inferred.20CMPE12c Cyrus BazeghiExamples:8 character elements, number 0 – 7, initialized to 0arrayname: .byte 0:818 bytes of memoryname: .space 185 integers initialized to 3numbers: .word 3:5Array Examples21CMPE12c Cyrus BazeghiArray of BytesCalculating the address of an array elementchar myarray[7] /* C */myarray: .byte 0:7 # MAL•If base address of myarray is 25•Byte address of myarray[4] = 25 + 4 = 29•Base address + distance from the first element0251234526 27 28 29 2A62BElement indexaddress22CMPE12c Cyrus BazeghiAddressing Byte ArraysIf we want the 3rdelement•It is at index 2 since indexing starts at zero.•Thus myarray[2] is the at the address of array + 2.•If the 1stelement is [0] and is at address 25, then the address of the 3rdelement is myarray[2] = 25 + 20251234526 27 28 29 30631addressindex3rdelement23CMPE12c Cyrus BazeghiHow do you get the address of myarray?• Use the “load address” instruction, “la”• Keep clear the difference between an address and the contents of an address.Addressing Byte Arrays24CMPE12c Cyrus BazeghiTo get address of myarray[4] in MAL, write the code…la $t0, myarrayadd $t1, $t0, 4If we wanted to decrement element number 5 by 1…lb $t4, ($t1)sub $t4, $t4, 1sb $t4, ($t1)Addressing Byte Arrays25CMPE12c Cyrus BazeghiArray of IntegersAn integer is 32-bits (word) and contains 4 bytesC++:int myarray[6];MAL:myarray: .word 0:6Or myarray: .space 2426CMPE12c Cyrus BazeghiSo to find the address of myarray[x] we must find:• Where the array starts (base address)• Size of an element